Deciding Universality of ptNFAs is PSpace-Complete

0485287 - MÚ 2019 RIV CH eng C - Conference Paper (international conference)
Masopust, Tomáš - Krötzsch, M.
Deciding Universality of ptNFAs is PSpace-Complete.
SOFSEM 2018: Theory and Practice of Computer Science. Cham: Springer, 2018 - (Tjoa, A.; Bellatreche, L.; Biffl, S.; van Leeuwen, J.; Wiedermann, J.), s. 413-427. Lecture Notes in Computer Science, 10706. ISBN 978-3-319-73116-2. ISSN 0302-9743.
[Sofsem 2018. International Conference on Current Trends in Theory and Practice of Computer Science /44./. Krems (AT), 29.01.2018-02.02.2018]
Institutional support: RVO:67985840
Keywords : nondeterministic automata * partial order * universality
OECD category: Computer sciences, information science, bioinformathics (hardware development to be 2.2, social aspect to be 5.8)
https://link.springer.com/chapter/10.1007%2F978-3-319-73117-9_29

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.
Permanent Link: http://hdl.handle.net/11104/0280357