Deciding Universality of ptNFAs is PSpace-Complete
The result's identifiers
Result code in IS VaVaI
<a href="https://www.isvavai.cz/riv?ss=detail&h=RIV%2F67985840%3A_____%2F18%3A00485287" target="_blank" >RIV/67985840:_____/18:00485287 - isvavai.cz</a>
Result on the web
<a href="http://dx.doi.org/10.1007/978-3-319-73117-9_29" target="_blank" >http://dx.doi.org/10.1007/978-3-319-73117-9_29</a>
DOI - Digital Object Identifier
<a href="http://dx.doi.org/10.1007/978-3-319-73117-9_29" target="_blank" >10.1007/978-3-319-73117-9_29</a>
Alternative languages
Result language
angličtina
Original language name
Deciding Universality of ptNFAs is PSpace-Complete
Original language description
An automaton is partially ordered if the only cycles in its transition diagram are self-loops. We study the universality problem for ptNFAs, a class of partially ordered NFAs recognizing piecewise testable languages. The universality problem asks if an automaton accepts all words over its alphabet. Deciding universality for both NFAs and partially ordered NFAs is PSpace-complete. For ptNFAs, the complexity drops to coNP-complete if the alphabet is fixed but is open if the alphabet may grow. We show, using a novel and nontrivial construction, that the problem is PSpace-complete if the alphabet may grow polynomially.
Czech name
—
Czech description
—
Classification
Type
D - Article in proceedings
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
2018
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
Article name in the collection
SOFSEM 2018: Theory and Practice of Computer Science
ISBN
978-3-319-73116-2
ISSN
0302-9743
e-ISSN
—
Number of pages
15
Pages from-to
413-427
Publisher name
Springer
Place of publication
Cham
Event location
Krems
Event date
Jan 29, 2018
Type of event by nationality
WRD - Celosvětová akce
UT code for WoS article
—