# On the Complexity of Universality for Partially Ordered NFAs

From International Center for Computational Logic

# On the Complexity of Universality for Partially Ordered NFAs

*Talk by Tomáš Masopust*

- Location: APB 3027
- Start: 6. July 2016 at 2:50 pm
- End: 6. July 2016 at 3:50 pm
- Research group: Knowledge-Based Systems
- Event series: KBS Seminar
- iCal

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

- More info at: https://iccl.inf.tu-dresden.de/web/Inproceedings3086/en