On the Complexity of Universality for Partially Ordered NFAs

Kód výsledku v IS VaVaI

<a href="https://www.isvavai.cz/riv?ss=detail&h=RIV%2F67985840%3A_____%2F16%3A00462042" target="_blank" >RIV/67985840:_____/16:00462042 - isvavai.cz</a>

Výsledek na webu

<a href="http://dx.doi.org/10.4230/LIPIcs.MFCS.2016.61" target="_blank" >http://dx.doi.org/10.4230/LIPIcs.MFCS.2016.61</a>

DOI - Digital Object Identifier

<a href="http://dx.doi.org/10.4230/LIPIcs.MFCS.2016.61" target="_blank" >10.4230/LIPIcs.MFCS.2016.61</a>

Jazyk výsledku

angličtina

Název v původním jazyce

On the Complexity of Universality for Partially Ordered NFAs

Popis výsledku v původním jazyce

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

Název v anglickém jazyce

On the Complexity of Universality for Partially Ordered NFAs

Popis výsledku anglicky

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

Druh

D - Stať ve sborníku

CEP obor

BA - Obecná matematika

OECD FORD obor

—

Projekt

—

Návaznosti

I - Institucionalni podpora na dlouhodoby koncepcni rozvoj vyzkumne organizace

Rok uplatnění

2016

Kód důvěrnosti údajů

S - Úplné a pravdivé údaje o projektu nepodléhají ochraně podle zvláštních právních předpisů

Název statě ve sborníku

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

ISBN

978-3-95977-016-3

ISSN

1868-8969

e-ISSN

—

Počet stran výsledku

14

Strana od-do

—

Název nakladatele

Schloss Dagstuhl, Leibniz-Zentrum fuer Informatik

Místo vydání

Dagstuhl

Místo konání akce

Krakow

Datum konání akce

22. 8. 2016

Typ akce podle státní příslušnosti

WRD - Celosvětová akce

Kód UT WoS článku

—