Document Open Access Logo

History-Deterministic Parikh Automata

Authors Enzo Erlich, Shibashis Guha , Ismaël Jecker , Karoliina Lehtinen , Martin Zimmermann

PDF
Thumbnail PDF

File

LIPIcs.CONCUR.2023.31.pdf
  • Filesize: 0.72 MB
  • 16 pages

Document Identifiers

Author Details

Enzo Erlich
  • ENS Rennes, France
Shibashis Guha
  • Tata Institute of Fundamental Research, Mumbai, India
Ismaël Jecker
  • University of Warsaw, Poland
Karoliina Lehtinen
  • CNRS, Aix-Marseille University, LIS, France
Martin Zimmermann
  • Aalborg University, Denmark

Funding

  • Guha, Shibashis: Supported by Indian Science and Engineering Research Board (SERB) grant SRG/2021/000466.
  • Jecker, Ismaël: Supported by the ERC grant 950398 (INFSYS).
  • Zimmermann, Martin: Supported by DIREC - Digital Research Centre Denmark.

Cite As Get BibTex

Enzo Erlich, Shibashis Guha, Ismaël Jecker, Karoliina Lehtinen, and Martin Zimmermann. History-Deterministic Parikh Automata. In 34th International Conference on Concurrency Theory (CONCUR 2023). Leibniz International Proceedings in Informatics (LIPIcs), Volume 279, pp. 31:1-31:16, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2023) https://doi.org/10.4230/LIPIcs.CONCUR.2023.31

Abstract

Parikh automata extend finite automata by counters that can be tested for membership in a semilinear set, but only at the end of a run. Thereby, they preserve many of the desirable properties of finite automata. Deterministic Parikh automata are strictly weaker than nondeterministic ones, but enjoy better closure and algorithmic properties.
This state of affairs motivates the study of intermediate forms of nondeterminism. Here, we investigate history-deterministic Parikh automata, i.e., automata whose nondeterminism can be resolved on the fly. This restricted form of nondeterminism is well-suited for applications which classically call for determinism, e.g., solving games and composition.
We show that history-deterministic Parikh automata are strictly more expressive than deterministic ones, incomparable to unambiguous ones, and enjoy almost all of the closure properties of deterministic automata.

Subject Classification

ACM Subject Classification
  • Theory of computation → Formal languages and automata theory
Keywords
  • Parikh automata
  • History-determinism
  • Reversal-bounded Counter Machines

Metrics

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

Related Versions

References

  1. Marc Bagnol and Denis Kuperberg. Büchi good-for-games automata are efficiently recognizable. In Sumit Ganguly and Paritosh Pandya, editors, FSTTCS 2018, volume 122 of LIPIcs, pages 16:1-16:14. Schloss Dagstuhl-Leibniz-Zentrum für Informatik, 2018. URL: https://doi.org/10.4230/LIPIcs.FSTTCS.2018.16.
  2. Udi Boker and Karoliina Lehtinen. History determinism vs. good for gameness in quantitative automata. In Mikołaj Bojańczy and Chandra Chekuri, editors, FSTTCS 2021, volume 213 of LIPIcs, pages 38:1-38:20, Dagstuhl, Germany, 2021. Schloss Dagstuhl - Leibniz-Zentrum für Informatik. URL: https://doi.org/10.4230/LIPIcs.FSTTCS.2021.38.
  3. Udi Boker and Karoliina Lehtinen. Token games and history-deterministic quantitative automata. In Patricia Bouyer and Lutz Schröder, editors, FOSSACS 2022, volume 13242 of LNCS, pages 120-139. Springer, 2022. URL: https://doi.org/10.1007/978-3-030-99253-8_7.
  4. Alin Bostan, Arnaud Carayol, Florent Koechlin, and Cyril Nicaud. Weakly-unambiguous Parikh automata and their link to holonomic series. In Artur Czumaj, Anuj Dawar, and Emanuela Merelli, editors, ICALP 2020, volume 168 of LIPIcs, pages 114:1-114:16. Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2020. URL: https://doi.org/10.4230/LIPIcs.ICALP.2020.114.
  5. Michaël Cadilhac, Alain Finkel, and Pierre McKenzie. On the expressiveness of Parikh automata and related models. In Rudolf Freund, Markus Holzer, Carlo Mereghetti, Friedrich Otto, and Beatrice Palano, editors, NCMA 2011, volume 282 of books@ocg.at, pages 103-119. Austrian Computer Society, 2011. Google Scholar
  6. Michaël Cadilhac, Alain Finkel, and Pierre McKenzie. Unambiguous constrained automata. Int. J. Found. Comput. Sci., 24(7):1099-1116, 2013. URL: https://doi.org/10.1142/S0129054113400339.
  7. Giusi Castiglione and Paolo Massazza. On a class of languages with holonomic generating functions. Theor. Comput. Sci., 658:74-84, 2017. URL: https://doi.org/10.1016/j.tcs.2016.07.022.
  8. Lorenzo Clemente, Wojciech Czerwinski, Slawomir Lasota, and Charles Paperman. Regular Separability of Parikh Automata. In Ioannis Chatzigiannakis, Piotr Indyk, Fabian Kuhn, and Anca Muscholl, editors, ICALP 2017, volume 80 of LIPIcs, pages 117:1-117:13. Schloss Dagstuhl-Leibniz-Zentrum für Informatik, 2017. URL: https://doi.org/10.4230/LIPIcs.ICALP.2017.117.
  9. Thomas Colcombet. The theory of stabilisation monoids and regular cost functions. In Susanne Albers, Alberto Marchetti-Spaccamela, Yossi Matias, Sotiris E. Nikoletseas, and Wolfgang Thomas, editors, ICALP 2009, (Part II), volume 5556 of LNCS, pages 139-150. Springer, 2009. URL: https://doi.org/10.1007/978-3-642-02930-1_12.
  10. Luc Dartois, Emmanuel Filiot, and Jean-Marc Talbot. Two-way Parikh automata with a visibly pushdown stack. In Mikolaj Bojanczyk and Alex Simpson, editors, FOSSACS 2019, volume 11425 of LNCS, pages 189-206. Springer, 2019. URL: https://doi.org/10.1007/978-3-030-17127-8_11.
  11. Jürgen Dassow and Victor Mitrana. Finite automata over free groups. Int. J. Algebra Comput., 10(6):725-738, 2000. URL: https://doi.org/10.1142/S0218196700000315.
  12. François Denis, Aurélien Lemay, and Alain Terlutte. Residual finite state automata. In Afonso Ferreira and Horst Reichel, editors, STACS 2001, volume 2010 of LNCS, pages 144-157. Springer, 2001. Google Scholar
  13. Enzo Erlich, Shibashis Guha, Ismaël Jecker, Karoliina Lehtinen, and Martin Zimmermann. History-deterministic parikh automata. arXiv, 2209.07745, 2022. URL: https://arxiv.org/abs/2209.07745.
  14. Diego Figueira and Leonid Libkin. Path logics for querying graphs: Combining expressiveness and efficiency. In LICS 2015, pages 329-340. IEEE Computer Society, 2015. URL: https://doi.org/10.1109/LICS.2015.39.
  15. Emmanuel Filiot, Shibashis Guha, and Nicolas Mazzocchi. Two-way Parikh automata. In Arkadev Chattopadhyay and Paul Gastin, editors, FSTTCS 2019, volume 150 of LIPIcs, pages 40:1-40:14. Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2019. Google Scholar
  16. Emmanuel Filiot, Nicolas Mazzocchi, and Jean-François Raskin. A pattern logic for automata with outputs. Int. J. Found. Comput. Sci., 31(6):711-748, 2020. Google Scholar
  17. Seymour Ginsburg and Edwin H. Spanier. Semigroups, Presburger formulas, and languages. Pacific Journal of Mathematics, 16(2):285-296, 1966. URL: https://doi.org/pjm/1102994974.
  18. Mario Grobler, Leif Sabellek, and Sebastian Siebertz. Parikh automata on infinite words. arXiv, 2301.08969, 2023. URL: https://doi.org/10.48550/arXiv.2301.08969.
  19. Mario Grobler and Sebastian Siebertz. Büchi-like characterizations for parikh-recognizable omega-languages. arxiv, 2302.04087, 2023. URL: https://doi.org/10.48550/arXiv.2302.04087.
  20. Shibashis Guha, Ismaël Jecker, Karoliina Lehtinen, and Martin Zimmermann. A bit of nondeterminism makes pushdown automata expressive and succinct. arXiv, 2105.02611, 2021. URL: https://doi.org/10.48550/arXiv.2105.02611.
  21. Shibashis Guha, Ismaël Jecker, Karoliina Lehtinen, and Martin Zimmermann. Parikh automata over infinite words. arXiv, 2207.07694, 2022. URL: https://doi.org/10.48550/arXiv.2207.07694.
  22. Shibashis Guha, Ismaël Jecker, Karoliina Lehtinen, and Martin Zimmermann. A bit of nondeterminism makes pushdown automata expressive and succinct. In Filippo Bonchi and Simon J. Puglisi, editors, MFCS 2021, volume 202 of LIPIcs, pages 53:1-53:20. Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2021. URL: https://doi.org/10.4230/LIPIcs.MFCS.2021.53.
  23. Thomas A. Henzinger, Karoliina Lehtinen, and Patrick Totzke. History-deterministic timed automata. In CONCUR 2022, 2022. To appear. Google Scholar
  24. Thomas A. Henzinger and Nir Piterman. Solving games without determinization. In Zoltán Ésik, editor, CSL 2006, volume 4207 of LNCS, pages 395-410. Springer, 2006. URL: https://doi.org/10.1007/11874683_26.
  25. John E. Hopcroft and Jeffrey D. Ullman. Introduction to Automata Theory, Languages and Computation. Addison-Wesley, 1979. Google Scholar
  26. Oscar H. Ibarra. Reversal-bounded multicounter machines and their decision problems. J. ACM, 25(1):116-133, 1978. URL: https://doi.org/10.1145/322047.322058.
  27. Felix Klaedtke and Harald Rueß. Monadic second-order logics with cardinalities. In Jos C. M. Baeten, Jan Karel Lenstra, Joachim Parrow, and Gerhard J. Woeginger, editors, ICALP 2003, volume 2719 of LNCS, pages 681-696. Springer, 2003. URL: https://doi.org/10.1007/3-540-45061-0_54.
  28. Denis Kuperberg and Michal Skrzypczak. On determinisation of good-for-games automata. In Magnús M. Halldórsson, Kazuo Iwama, Naoki Kobayashi, and Bettina Speckmann, editors, ICALP 2015 (Part II), volume 9135 of LNCS, pages 299-310. Springer, 2015. URL: https://doi.org/10.1007/978-3-662-47666-6_24.
  29. Karoliina Lehtinen and Martin Zimmermann. Good-for-games ω-pushdown automata. LMCS, 18(1), 2022. URL: https://doi.org/10.46298/lmcs-18(1:3)2022.
  30. Marvin L. Minsky. Computation: Finite and Infinite Machines. Prentice-Hall, 1967. Google Scholar
  31. Victor Mitrana and Ralf Stiebe. Extended finite automata over groups. Discret. Appl. Math., 108(3):287-300, 2001. URL: https://doi.org/10.1016/S0166-218X(00)00200-6.
  32. Karianto Wong. Parikh automata with pushdown stack, 2004. Diploma thesis, RWTH Aachen University. URL: https://old.automata.rwth-aachen.de/download/papers/karianto/ka04.pdf.
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