LIPIcs.CONCUR.2023.33.pdf
- Filesize: 0.83 MB
- 17 pages
Document
Complexity of Membership and Non-Emptiness Problems in Unbounded Memory Automata
Authors
Clément Bertrand 
,
Cinzia Di Giusto ,
Hanna Klaudel ,
Damien Regnault
-
Part of:
Volume:
34th International Conference on Concurrency Theory (CONCUR 2023)
Series: Leibniz International Proceedings in Informatics (LIPIcs)
Conference: International Conference on Concurrency Theory (CONCUR) - License:
Creative Commons Attribution 4.0 International license
- Publication Date: 2023-09-07
File
Document Identifiers
Author Details
Acknowledgements
We want to thank the anonymous reviewers for the careful reviews and insightful comments.
Cite AsGet BibTex
Clément Bertrand, Cinzia Di Giusto, Hanna Klaudel, and Damien Regnault. Complexity of Membership and Non-Emptiness Problems in Unbounded Memory Automata. In 34th International Conference on Concurrency Theory (CONCUR 2023). Leibniz International Proceedings in Informatics (LIPIcs), Volume 279, pp. 33:1-33:17, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2023)
https://doi.org/10.4230/LIPIcs.CONCUR.2023.33
https://doi.org/10.4230/LIPIcs.CONCUR.2023.33
Abstract
We study the complexity relationship between three models of unbounded memory automata: nu-automata (ν-A), Layered Memory Automata (LaMA)and History-Register Automata (HRA). These are all extensions of finite state automata with unbounded memory over infinite alphabets. We prove that the membership problem is NP-complete for all of them, while they fall into different classes for what concerns non-emptiness. The problem of non-emptiness is known to be Ackermann-complete for HRA, we prove that it is PSPACE-complete for ν-A.
Subject Classification
ACM Subject Classification
- Theory of computation → Automata over infinite objects
- Theory of computation → Problems, reductions and completeness
Keywords
- memory automata
- ν-automata
- LaMA
- HRA
- complexity
- non-emptiness
- membership
Metrics
- Access Statistics
-
Total Accesses (updated on a weekly basis)
0PDF Downloads
References
- S. Arora and B. Barak. Computational Complexity: A Modern Approach. Cambridge University Press, 2006. URL: https://theory.cs.princeton.edu/complexity/book.pdf.
- Clement Bertrand. Reconnaissance de motifs dynamiques par automates temporisés à mémoire. Theses, Université Paris-Saclay, December 2020. URL: https://theses.hal.science/tel-03172600.
- Clément Bertrand, Cinzia Di Giusto, Hanna Klaudel, and Damien Regnault. Complexity of Membership and Non-Emptiness Problems in Unbounded Memory Automata. Technical report, Université Côte d'Azur, CNRS, I3S, France ; IBISC, Univ. Evry, Université Paris-Saclay, France ; Scalian Digital Systems, Valbonne, France, 2023. URL: https://hal.science/hal-04155339.
- Clément Bertrand, Hanna Klaudel, and Frédéric Peschanski. Layered memory automata: Recognizers for quasi-regular languages with unbounded memory. In Luca Bernardinello and Laure Petrucci, editors, Application and Theory of Petri Nets and Concurrency - 43rd International Conference, PETRI NETS 2022, Bergen, Norway, June 19-24, 2022, Proceedings, volume 13288 of Lecture Notes in Computer Science, pages 43-63. Springer, 2022. URL: https://doi.org/10.1007/978-3-031-06653-5_3.
- Clément Bertrand, Frédéric Peschanski, Hanna Klaudel, and Matthieu Latapy. Pattern matching in link streams: Timed-automata with finite memory. Sci. Ann. Comput. Sci., 28(2):161-198, 2018. URL: http://www.info.uaic.ro/bin/Annals/Article?v=XXVIII2&a=1.
- Henrik Björklund and Thomas Schwentick. On notions of regularity for data languages. Theoretical Computer Science, 411(4):702-715, 2010. Fundamentals of Computation Theory. URL: https://doi.org/10.1016/j.tcs.2009.10.009.
- Mikolaj Bojanczyk, Claire David, Anca Muscholl, Thomas Schwentick, and Luc Segoufin. Two-variable logic on data words. ACM Trans. Comput. Log., 12(4):27:1-27:26, 2011. URL: https://doi.org/10.1145/1970398.1970403.
- Aurélien Deharbe. Analyse de ressources pour les systèmes concurrents dynamiques. PhD thesis, Université Pierre et Marie Curie, France, September 2016. URL: https://tel.archives-ouvertes.fr/tel-01523979.
- Aurelien Deharbe and Frédéric Peschanski. The omniscient garbage collector: A resource analysis framework. In 14th International Conference on Application of Concurrency to System Design, ACSD 2014, Tunis La Marsa, Tunisia, June 23-27, 2014, pages 102-111. IEEE Computer Society, 2014. URL: https://doi.org/10.1109/ACSD.2014.18.
- Stéphane Demri and Ranko Lazić. LTL with the freeze quantifier and register automata. ACM Trans. Comput. Logic, 10(3), April 2009. URL: https://doi.org/10.1145/1507244.1507246.
- Radu Grigore and Nikos Tzevelekos. History-register automata. Log. Methods Comput. Sci., 12(1), 2016. URL: https://doi.org/10.2168/LMCS-12(1:7)2016.
- Orna Grumberg, Orna Kupferman, and Sarai Sheinvald. Variable automata over infinite alphabets. In Adrian-Horia Dediu, Henning Fernau, and Carlos Martín-Vide, editors, Language and Automata Theory and Applications, 4th International Conference, LATA 2010, Trier, Germany, May 24-28, 2010. Proceedings, volume 6031 of Lecture Notes in Computer Science, pages 561-572. Springer, 2010. URL: https://doi.org/10.1007/978-3-642-13089-2_47.
- Michael Kaminski and Nissim Francez. Finite-memory automata. Theor. Comput. Sci., 134(2):329-363, 1994. URL: https://doi.org/10.1016/0304-3975(94)90242-9.
- Michael Kaminski and Daniel Zeitlin. Finite-memory automata with non-deterministic reassignment. Int. J. Found. Comput. Sci., 21(5):741-760, 2010. URL: https://doi.org/10.1142/S0129054110007532.
- Ahmet Kara. Logics on data words: Expressivity, satisfiability, model checking. PhD thesis, Technical University of Dortmund, Germany, 2016. URL: http://hdl.handle.net/2003/35216.
- Andrzej S. Murawski, Steven J. Ramsay, and Nikos Tzevelekos. Polynomial-time equivalence testing for deterministic fresh-register automata. In Igor Potapov, Paul G. Spirakis, and James Worrell, editors, 43rd International Symposium on Mathematical Foundations of Computer Science, MFCS 2018, August 27-31, 2018, Liverpool, UK, volume 117 of LIPIcs, pages 72:1-72:14. Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2018. URL: https://doi.org/10.4230/LIPIcs.MFCS.2018.72.
- Frank Neven, Thomas Schwentick, and Victor Vianu. Finite state machines for strings over infinite alphabets. ACM Trans. Comput. Logic, 5(3):403-435, July 2004. URL: https://doi.org/10.1145/1013560.1013562.
- Hiroshi Sakamoto and Daisuke Ikeda. Intractability of decision problems for finite-memory automata. Theoretical Computer Science, 231(2):297-308, 2000. URL: https://doi.org/10.1016/S0304-3975(99)00105-X.
- Nikos Tzevelekos. Fresh-register automata. In Thomas Ball and Mooly Sagiv, editors, Proceedings of the 38th ACM SIGPLAN-SIGACT Symposium on Principles of Programming Languages, POPL 2011, Austin, TX, USA, January 26-28, 2011, pages 295-306. ACM, 2011. URL: https://doi.org/10.1145/1926385.1926420.