2026-07-24T23:29:59Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:11877 2024-03-06T10:48:54Z ddc:004 open_access

Existential Length Universality Gawrychowski, Paweł Lange, Martin Rampersad, Narad Shallit, Jeffrey Szykuła, Marek decision problem deterministic automaton nondeterministic automaton pushdown automaton regular expression regular language universality We study the following natural variation on the classical universality problem: given a language L(M) represented by M (e.g., a DFA/RE/NFA/PDA), does there exist an integer ? ≥ 0 such that Σ^? ⊆ L(M)? In the case of an NFA, we show that this problem is NEXPTIME-complete, and the smallest such ? can be doubly exponential in the number of states. This particular case was formulated as an open problem in 2009, and our solution uses a novel and involved construction. In the case of a PDA, we show that it is recursively unsolvable, while the smallest such ? is not bounded by any computable function of the number of states. In the case of a DFA, we show that the problem is NP-complete, and e^{√{n log n} (1+o(1))} is an asymptotically tight upper bound for the smallest such ?, where n is the number of states. Finally, we prove that in all these cases, the problem becomes computationally easier when the length ? is also given in binary in the input: it is polynomially solvable for a DFA, PSPACE-complete for an NFA, and co-NEXPTIME-complete for a PDA. Schloss Dagstuhl – Leibniz-Zentrum für Informatik Paweł Gawrychowski and Martin Lange and Narad Rampersad and Jeffrey Shallit and Marek Szykuła 2020 Is Part Of LIPIcs, Volume 154, 37th International Symposium on Theoretical Aspects of Computer Science (STACS 2020) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.STACS.2020.16 urn:nbn:de:0030-drops-118770 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.STACS.2020.16 eng https://creativecommons.org/licenses/by/3.0/legalcode