Deciding Universality of ptNFAs is PSpace-Complete

Aus International Center for Computational Logic
Wechseln zu:Navigation, Suche

Toggle side column

Deciding Universality of ptNFAs is PSpace-Complete

Tomáš MasopustTomáš Masopust,  Markus KrötzschMarkus Krötzsch
Deciding Universality of ptNFAs is PSpace-Complete


Tomáš Masopust, Markus Krötzsch
Deciding Universality of ptNFAs is PSpace-Complete
In A Min Tjoa, Ladjel Bellatreche, Stefan Biffl, Jan van Leeuwen, Jiri Wiedermann, eds., Proceedings of the 44th International Conference on Current Trends in Theory and Practice of Computer Science (SOFSEM 2018), volume 10706 of LNCS, 413-427, 2018. Spinger
  • KurzfassungAbstract
    An automaton is partially ordered if the only cycles in its transition diagram are self-loops. We study the universality problem for ptNFAs, a class of partially ordered NFAs recognizing piecewise testable languages. The universality problem asks if an automaton accepts all words over its alphabet. Deciding universality for both NFAs and partially ordered NFAs is PSpace-complete. For ptNFAs, the complexity drops to coNP-complete if the alphabet is fixed but is open if the alphabet may grow. We show, using a novel and nontrivial construction, that the problem is PSpace-complete if the alphabet may grow polynomially.
  • Projekt:Project: CfaedDIAMONDHAEC B08
  • Forschungsgruppe:Research Group: Wissensbasierte Systeme
@inproceedings{MK2018,
  author    = {Tom{\'{a}}{\v{s}} Masopust and Markus Kr{\"{o}}tzsch},
  title     = {Deciding Universality of {ptNFAs} is {PSpace-Complete}},
  editor    = {A Min Tjoa and Ladjel Bellatreche and Stefan Biffl and Jan van
               Leeuwen and Jiri Wiedermann},
  booktitle = {Proceedings of the 44th International Conference on Current
               Trends in Theory and Practice of Computer Science (SOFSEM 2018)},
  series    = {LNCS},
  volume    = {10706},
  publisher = {Spinger},
  year      = {2018},
  pages     = {413-427},
  doi       = {10.1007/978-3-319-73117-9_29}
}