Deciding Universality of ptNFAs is PSpace-Complete

Tomáš MasopustTomáš Masopust, Markus KrötzschMarkus Krötzsch

ISBN: 978-3-319-73116-2
Download
DOI Link

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. Springer

Details
Bibtex

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: Cfaed, DIAMOND, HAEC B08
Forschungsgruppe:Research Group: Wissensbasierte SystemeKnowledge-Based Systems

The final publication is available at Springer via http://dx.doi.org/10.1007/978-3-319-73117-9_29.

@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 = {Springer},
  year      = {2018},
  pages     = {413-427},
  doi       = {10.1007/978-3-319-73117-9_29}
}