Document Open Access Logo

Explorable Automata

Authors Emile Hazard, Denis Kuperberg

PDF
Thumbnail PDF

File

LIPIcs.CSL.2023.24.pdf
  • Filesize: 0.73 MB
  • 18 pages

Document Identifiers

Author Details

Emile Hazard
  • CNRS, LIP, ENS Lyon, France
Denis Kuperberg
  • CNRS, LIP, ENS Lyon, France

Cite As Get BibTex

Emile Hazard and Denis Kuperberg. Explorable Automata. In 31st EACSL Annual Conference on Computer Science Logic (CSL 2023). Leibniz International Proceedings in Informatics (LIPIcs), Volume 252, pp. 24:1-24:18, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2023) https://doi.org/10.4230/LIPIcs.CSL.2023.24

Abstract

We define the class of explorable automata on finite or infinite words. This is a generalization of History-Deterministic (HD) automata, where this time non-deterministic choices can be resolved by building finitely many simultaneous runs instead of just one. We show that recognizing HD parity automata of fixed index among explorable ones is in PTime, thereby giving a strong link between the two notions. We then show that recognizing explorable automata is ExpTime-complete, in the case of finite words or Büchi automata. Additionally, we define the notion of ω-explorable automata on infinite words, where countably many runs can be used to resolve the non-deterministic choices. We show that all reachability automata are ω-explorable, but this is not the case for safety ones. We finally show ExpTime-completeness for ω-explorability of automata on infinite words for the safety and co-Büchi acceptance conditions.

Subject Classification

ACM Subject Classification
  • Theory of computation → Formal languages and automata theory
Keywords
  • Nondeterminism
  • automata
  • complexity

Metrics

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

Related Versions

References

  1. Bader Abu Radi and Orna Kupferman. Minimization and canonization of GFG transition-based automata. CoRR, abs/2106.06745, 2021. Google Scholar
  2. Bader Abu Radi, Orna Kupferman, and Ofer Leshkowitz. A hierarchy of nondeterminism. In 46th International Symposium on Mathematical Foundations of Computer Science, MFCS 2021, LIPIcs. Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2021. Google Scholar
  3. Marc Bagnol and Denis Kuperberg. Büchi good-for-games automata are efficiently recognizable. In 38th IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science, FSTTCS 2018, LIPIcs. Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2018. Google Scholar
  4. Nathalie Bertrand, Miheer Dewaskar, Blaise Genest, Hugo Gimbert, and Adwait Amit Godbole. Controlling a population. Log. Methods Comput. Sci., 15(3), 2019. Google Scholar
  5. Udi Boker. Between deterministic and nondeterministic quantitative automata (invited talk). In Florin Manea and Alex Simpson, editors, 30th EACSL Annual Conference on Computer Science Logic, CSL 2022, February 14-19, 2022, Göttingen, Germany (Virtual Conference), LIPIcs. Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2022. Google Scholar
  6. Udi Boker, Denis Kuperberg, Orna Kupferman, and MichałSkrzypczak. Nondeterminism in the presence of a diverse or unknown future. In Automata, Languages, and Programming - 40th International Colloquium, ICALP 2013, Lecture Notes in Computer Science. Springer, 2013. Google Scholar
  7. Udi Boker, Denis Kuperberg, Karoliina Lehtinen, and MichałSkrzypczak. On the succinctness of alternating parity good-for-games automata. In 40th IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science, FSTTCS 2020, LIPIcs. Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2020. Google Scholar
  8. Udi Boker and Karoliina Lehtinen. History determinism vs. good for gameness in quantitative automata. In 41st IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science, FSTTCS 2021, LIPIcs. Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2021. Google Scholar
  9. Udi Boker and Karoliina Lehtinen. Token games and history-deterministic quantitative automata. In Foundations of Software Science and Computation Structures - 25th International Conference, FOSSACS 2022, Lecture Notes in Computer Science. Springer, 2022. Google Scholar
  10. Cristian S. Calude, Sanjay Jain, Bakhadyr Khoussainov, Wei Li, and Frank Stephan. Deciding parity games in quasipolynomial time. In Proceedings of the 49th Annual ACM SIGACT Symposium on Theory of Computing, STOC 2017, pages 252-263. ACM, 2017. Google Scholar
  11. Thomas Colcombet. The theory of stabilisation monoids and regular cost functions. In Automata, languages and programming. Part II, volume 5556 of Lecture Notes in Comput. Sci., pages 139-150, Berlin, 2009. Springer. Google Scholar
  12. Thomas Colcombet. Forms of determinism for automata (invited talk). In 29th International Symposium on Theoretical Aspects of Computer Science, STACS 2012, LIPIcs. Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2012. Google Scholar
  13. Thomas Colcombet and Nathanaël Fijalkow. Universal graphs and good for games automata: New tools for infinite duration games. In Foundations of Software Science and Computation Structures - 22nd International Conference, FOSSACS 2019, Lecture Notes in Computer Science. Springer, 2019. Google Scholar
  14. E. Allen Emerson and Charanjit S. Jutla. Tree automata, mu-calculus and determinacy (extended abstract). In 32nd Annual Symposium on Foundations of Computer Science, San Juan, Puerto Rico, 1-4 October 1991, pages 368-377. IEEE Computer Society, 1991. Google Scholar
  15. Erich Grädel, Wolfgang Thomas, and Thomas Wilke, editors. Automata, Logics, and Infinite Games: A Guide to Current Research [outcome of a Dagstuhl seminar, February 2001], volume 2500 of Lecture Notes in Computer Science. Springer, 2002. Google Scholar
  16. Thomas A. Henzinger and Nir Piterman. Solving games without determinization. In Computer Science Logic, 20th International Workshop, CSL 2006, 2006. Google Scholar
  17. Juraj Hromkovic, Juhani Karhumäki, Hartmut Klauck, Georg Schnitger, and Sebastian Seibert. Measures of nondeterminism in finite automata. Electronic Colloquium on Computational Complexity (ECCC), 7, January 2000. Google Scholar
  18. Denis Kuperberg and Anirban Majumdar. Computing the width of non-deterministic automata. Log. Methods Comput. Sci. (LMCS), 15(4), 2019. Google Scholar
  19. Denis Kuperberg and MichałSkrzypczak. On determinisation of good-for-games automata. In Automata, Languages, and Programming - 42nd International Colloquium, ICALP 2015, Lecture Notes in Computer Science. Springer, 2015. Google Scholar
  20. Karoliina Lehtinen and Martin Zimmermann. Good-for-games ω-pushdown automata. In LICS 2020: 35th Annual ACM/IEEE Symposium on Logic in Computer Science, pages 689-702. ACM, 2020. Google Scholar
  21. Satoru Miyano and Takeshi Hayashi. Alternating finite automata on ω-words. Theoret. Comput. Sci., 32(3):321-330, 1984. Google Scholar
  22. Damian Niwiński. On the cardinality of sets of infinite trees recognizable by finite automata. In Mathematical Foundations of Computer Science 1991, 16th International Symposium, MFCS'91, Lecture Notes in Computer Science. Springer, 1991. Google Scholar
  23. Alexandros Palioudakis, Kai Salomaa, and Selim G. Akl. Worst case branching and other measures of nondeterminism. Int. J. Found. Comput. Sci., 28(3):195-210, 2017. Google Scholar
  24. Sven Schewe. Minimising good-for-games automata is NP-complete. In 40th IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science, FSTTCS 2020, LIPIcs. Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2020. Google Scholar
  25. Andreas Weber and Helmut Seidl. On the degree of ambiguity of finite automata. Theor. Comput. Sci., 88(2):325-349, 1991. Google Scholar
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 About DROPS Imprint Privacy Contact