On the Complexity of Universality for Partially Ordered NFAs

Markus KrötzschMarkus Krötzsch, Tomáš MasopustTomáš Masopust, Michaël ThomazoMichaël Thomazo

ISBN: 978-3-95977-016-3
ISSN: 1868-8969
Download
DOI Link

Markus Krötzsch, Tomáš Masopust, Michaël Thomazo
On the Complexity of Universality for Partially Ordered NFAs
In Piotr Faliszewski, Anca Muscholl, Rolf Niedermeier, eds., Proceedings of the 41st International Symposium on Mathematical Foundations of Computer Science (MFCS 2016), volume 58 of Leibniz International Proceedings in Informatics, 61:1--61:14, 2016. Schloss Dagstuhl - Leibniz-Zentrum fuer Informatik

Details
Bibtex

KurzfassungAbstract
Partially ordered nondeterminsitic finite automata (poNFAs) are NFAs whose transition relation induces a partial order on states, i.e., for which cycles occur only in the form of self-loops on a single state. A poNFA is universal if it accepts all words over its input alphabet. Deciding universality is PSpace-complete for poNFAs, and we show that this remains true even when restricting to a fixed alphabet. This is nontrivial since standard encodings of alphabet symbols in, e.g., binary can turn self-loops into longer cycles. A lower coNP-complete complexity bound can be obtained if we require that all self-loops in the poNFA are deterministic, in the sense that the symbol read in the loop cannot occur in any other transition from that state. We find that such restricted poNFAs (rpoNFAs) characterise the class of R-trivial languages, and we establish the complexity of deciding if the language of an NFA is R-trivial. Nevertheless, the limitation to fixed alphabets turns out to be essential even in the restricted case: deciding universality of rpoNFAs with unbounded alphabets is PSpace-complete.
Projekt:Project: DIAMOND, HAEC B08
Forschungsgruppe:Research Group: Wissensbasierte SystemeKnowledge-Based Systems

@inproceedings{KMT2016,
  author    = {Markus Kr{\"{o}}tzsch and Tom{\'{a}}{\v{s}} Masopust and
               Micha{\"{e}}l Thomazo},
  title     = {On the Complexity of Universality for Partially Ordered {NFAs}},
  editor    = {Piotr Faliszewski and Anca Muscholl and Rolf Niedermeier},
  booktitle = {Proceedings of the 41st International Symposium on Mathematical
               Foundations of Computer Science (MFCS 2016)},
  series    = {Leibniz International Proceedings in Informatics},
  volume    = {58},
  publisher = {Schloss Dagstuhl - Leibniz-Zentrum fuer Informatik},
  year      = {2016},
  pages     = {61:1--61:14},
  doi       = {10.4230/LIPIcs.MFCS.2016.61}
}