Deciding Universality of ptNFAs is PSpace-Complete
Research output: Contribution to book/conference proceedings/anthology/report › Conference contribution › Contributed › peer-review
Contributors
Abstract
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.
Details
Original language | English |
---|---|
Title of host publication | SOFSEM 2018: Theory and Practice of Computer Science |
Editors | A Min Tjoa, Ladjel Bellatreche, Stefan Biffl, Jan van Leeuwen, Jiří Wiedermann |
Pages | 413–427 |
ISBN (electronic) | 978-3-319-73117-9 |
Publication status | Published - 2018 |
Peer-reviewed | Yes |
Publication series
Series | Lecture Notes in Computer Science |
---|---|
Volume | 10706 |
ISSN | 0302-9743 |