Complexity of universality and related problems for partially ordered NFAs
The result's identifiers
Result code in IS VaVaI
<a href="https://www.isvavai.cz/riv?ss=detail&h=RIV%2F67985840%3A_____%2F17%3A00476953" target="_blank" >RIV/67985840:_____/17:00476953 - isvavai.cz</a>
Result on the web
<a href="http://dx.doi.org/10.1016/j.ic.2017.06.004" target="_blank" >http://dx.doi.org/10.1016/j.ic.2017.06.004</a>
DOI - Digital Object Identifier
<a href="http://dx.doi.org/10.1016/j.ic.2017.06.004" target="_blank" >10.1016/j.ic.2017.06.004</a>
Alternative languages
Result language
angličtina
Original language name
Complexity of universality and related problems for partially ordered NFAs
Original language description
Partially ordered NFAs (poNFAs) are NFAs where cycles occur only in the form of self-loops. A poNFA is universal if it accepts all words over its alphabet. Deciding universality is PSpace-complete for poNFAs. We show that this remains true when restricting to fixed alphabets. This is nontrivial since standard encodings of symbols in, e.g., binary can turn self-loops into longer cycles. A lower coNP-complete complexity bound is obtained if all self-loops in the poNFA are deterministic. We find that such restricted poNFAs (rpoNFAs) characterize R-trivial languages, and establish the complexity of deciding if the language of an NFA is R-trivial. The limitation to fixed alphabets is essential even in the restricted case: deciding universality of rpoNFAs with unbounded alphabets is PSpace-complete. Consequently, we obtain the complexity results for inclusion and equivalence problems. Finally, we show that the languages of rpoNFAs are definable by deterministic regular expressions.
Czech name
—
Czech description
—
Classification
Type
J<sub>imp</sub> - Article in a specialist periodical, which is included in the Web of Science database
CEP classification
—
OECD FORD branch
10201 - Computer sciences, information science, bioinformathics (hardware development to be 2.2, social aspect to be 5.8)
Result continuities
Project
—
Continuities
I - Institucionalni podpora na dlouhodoby koncepcni rozvoj vyzkumne organizace
Others
Publication year
2017
Confidentiality
S - Úplné a pravdivé údaje o projektu nepodléhají ochraně podle zvláštních právních předpisů
Data specific for result type
Name of the periodical
Information and Computation
ISSN
0890-5401
e-ISSN
—
Volume of the periodical
255
Issue of the periodical within the volume
1
Country of publishing house
US - UNITED STATES
Number of pages
16
Pages from-to
177-192
UT code for WoS article
000407658600009
EID of the result in the Scopus database
2-s2.0-85022196483