Document Open Access Logo

Existential Length Universality

Authors Paweł Gawrychowski, Martin Lange, Narad Rampersad, Jeffrey Shallit, Marek Szykuła

PDF
Thumbnail PDF

File

LIPIcs.STACS.2020.16.pdf
  • Filesize: 0.58 MB
  • 14 pages

Document Identifiers

Author Details

Paweł Gawrychowski
  • Institute of Computer Science, University of Wrocław, Wrocław, Poland
Martin Lange
  • School of Electr. Eng. and Comp. Sc., University of Kassel, Kassel, Germany
Narad Rampersad
  • Department of Math/Stats, University of Winnipeg, Winnipeg, Canada
Jeffrey Shallit
  • School of Computer Science, University of Waterloo, Waterloo, Canada
Marek Szykuła
  • Institute of Computer Science, University of Wrocław, Wrocław, Poland

Funding

  • Rampersad, Narad: Supported in part by a grant from NSERC.
  • Shallit, Jeffrey: Supported in part by a grant from NSERC.
  • Szykuła, Marek: Supported in part by the National Science Centre, Poland under project number 2017/25/B/ST6/01920.

Cite AsGet BibTex

Paweł Gawrychowski, Martin Lange, Narad Rampersad, Jeffrey Shallit, and Marek Szykuła. Existential Length Universality. In 37th International Symposium on Theoretical Aspects of Computer Science (STACS 2020). Leibniz International Proceedings in Informatics (LIPIcs), Volume 154, pp. 16:1-16:14, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2020)
https://doi.org/10.4230/LIPIcs.STACS.2020.16

Abstract

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.

Subject Classification

ACM Subject Classification
  • Theory of computation → Problems, reductions and completeness
  • Theory of computation → Formal languages and automata theory
Keywords
  • decision problem
  • deterministic automaton
  • nondeterministic automaton
  • pushdown automaton
  • regular expression
  • regular language
  • universality

Metrics

  • Access Statistics
  • Total Accesses (updated on a weekly basis)
    0
    PDF Downloads
    0
    Metadata Views

Related Versions

References

  1. A. V. Aho and J. E. Hopcroft. The Design and Analysis of Computer Algorithms. Addison-Wesley Longman Publishing Co., Inc., 1st edition, 1974. Google Scholar
  2. R. Alur and P. Madhusudan. Visibly pushdown languages. In Proc. of the 36th Annual ACM Symposium on Theory of Computing, STOC 2004, pages 202-211. ACM, 2004. Google Scholar
  3. N. Bertrand, P. Bouyer, T. Brihaye, and A. Stainer. Emptiness and universality problems in timed automata with positive frequency. In Proceedings of the 38th International Conference on Automata, Languages and Programming - Volume Part II, ICALP 2011, pages 246-257. Springer, 2011. Google Scholar
  4. L. Doyen and J.-F. Raskin. Games with imperfect information: theory and algorithms. In Krzysztof R. Apt and Erich Grädel, editors, Lectures in Game Theory for Computer Scientists, pages 185-212. Cambridge University Press, 2011. Google Scholar
  5. L. Fleischer and M. Kufleitner. Green’s relations in finite transformation semigroups. In Pascal Weil, editor, CSR, pages 112-125. Springer, 2017. Google Scholar
  6. O. Friedmann and M. Lange. Ramsey-Based Analysis of Parity Automata. In TACAS, volume 7214 of LNCS, pages 64-78. Springer, 2012. Google Scholar
  7. E. Grädel. Dominoes and the Complexity of Subclasses of Logical Theories. Annals of Pure and Applied Logic, 43(1):1-30, 1989. Google Scholar
  8. C. Haase. Subclasses of Presburger Arithmetic and the Weak EXP Hierarchy. In CSL-LICS, CSL-LICS, pages 47:1-47:10. ACM, 2014. Google Scholar
  9. J. E. Hopcroft and J. D. Ullman. Introduction to Automata Theory, Languages, and Computation. Addison-Wesley, 1979. Google Scholar
  10. N. D. Jones. Space-bounded reducibility among combinatorial problems. Journal of Computer and System Sciences, 11(1):68-85, 1975. Google Scholar
  11. M. Krötzsch, T. Masopust, and M. Thomazo. On the complexity of universality for partially ordered NFAs. In MFCS, pages 61:1-61:14, 2016. Google Scholar
  12. J. Mazoyer. A six-state minimal time solution to the firing squad synchronization problem. Theoretical Computer Science, 50(2):183-238, 1987. Google Scholar
  13. F. R. Moore and G. G Langdon. A generalized firing squad problem. Information and Control, 12(3):212-220, 1968. Google Scholar
  14. N. Rampersad, J. Shallit, and Z. Xu. The computational complexity of universality problems for prefixes, suffixes, factors, and subwords of regular languages. Fundamenta Informaticae, 116(1-4):223-236, 2012. Google Scholar
  15. J. Shallit. Open problems in automata theory: an idiosyncratic view, LMS Keynote Address in Discrete Mathematics, BCTCS 2014, April 10 2014, Loughborough, England. URL: https://cs.uwaterloo.ca/~shallit/Talks/bc4.pdf.
  16. P. van Emde Boas. The convenience of tilings. In Complexity, Logic, and Recursion Theory, pages 331-363. Marcel Dekker Inc., 1997. Google Scholar
  17. M. Y. Vardi and P. Wolper. Reasoning About Infinite Computations. Information and Computation, 115(1):1-37, 1994. Google Scholar
  18. G. Zetzsche. The complexity of downward closure comparisons. https://arxiv.org/abs/1605.03149, 2016. URL: https://arxiv.org/abs/1605.03149.
Questions / Remarks / Feedback
X

Feedback for Dagstuhl Publishing


Thanks for your feedback!

Feedback submitted

Could not send message

Please try again later or send an E-mail
© 2023-2024 Schloss Dagstuhl – LZI GmbH Imprint Privacy Contact