文章基本信息

标题：Existential Length Universality
本地全文：下载
作者：PaweÅ, Gawrychowski ; Martin Lange ; Narad Rampersad 等
期刊名称：LIPIcs : Leibniz International Proceedings in Informatics
电子版ISSN：1868-8969
出版年度：2020
卷号：154
页码：16:1-16:14
DOI：10.4230/LIPIcs.STACS.2020.16
出版社：Schloss Dagstuhl -- Leibniz-Zentrum fuer Informatik
摘要：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 Î£^ð" âS 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^{â^S{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.
关键词：decision problem; deterministic automaton; nondeterministic automaton; pushdown automaton; regular expression; regular language; universality