Krötzsch, Markus ;
Masopust, Tomás ;
Thomazo, Michaël
On the Complexity of Universality for Partially Ordered NFAs
Abstract
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 selfloops on a single state. A poNFA is universal if it accepts all words over its input alphabet.
Deciding universality is \PSpacecomplete 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 selfloops into longer cycles. A lower coNPcomplete complexity bound can be obtained if we require that all selfloops 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 Rtrivial languages, and we establish the complexity of deciding if the language of an NFA is Rtrivial. Nevertheless, the limitation to fixed alphabets turns out to be essential even in the restricted case: deciding universality of rpoNFAs with unbounded alphabets is PSPACEcomplete. Our results also prove the complexity of the inclusion and equivalence problems, since universality provides the lower bound, while the upper bound is mostly known or proved in the paper.
BibTeX  Entry
@InProceedings{krtzsch_et_al:LIPIcs:2016:6473,
author = {Markus Kr{\"o}tzsch and Tom{\'a}s Masopust and Micha{\"e}l Thomazo},
title = {{On the Complexity of Universality for Partially Ordered NFAs}},
booktitle = {41st International Symposium on Mathematical Foundations of Computer Science (MFCS 2016)},
pages = {61:161:14},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {9783959770163},
ISSN = {18688969},
year = {2016},
volume = {58},
editor = {Piotr Faliszewski and Anca Muscholl and Rolf Niedermeier},
publisher = {Schloss DagstuhlLeibnizZentrum fuer Informatik},
address = {Dagstuhl, Germany},
URL = {http://drops.dagstuhl.de/opus/volltexte/2016/6473},
URN = {urn:nbn:de:0030drops64738},
doi = {10.4230/LIPIcs.MFCS.2016.61},
annote = {Keywords: automata, nondeterminism, partial order, universality}
}
2016
Keywords: 

automata, nondeterminism, partial order, universality 
Seminar: 

41st International Symposium on Mathematical Foundations of Computer Science (MFCS 2016)

Issue date: 

2016 
Date of publication: 

2016 