Synchronizing deterministic push-down automata can be really hard. (English) Zbl 07559404
Esparza, Javier (ed.) et al., 45th international symposium on mathematical foundations of computer science, MFCS 2020, August 25–26, 2020, Prague, Czech Republic. Proceedings. Wadern: Schloss Dagstuhl – Leibniz Zentrum für Informatik. LIPIcs – Leibniz Int. Proc. Inform. 170, Article 33, 15 p. (2020).
Summary: The question if a deterministic finite automaton admits a software reset in the form of a so-called synchronizing word can be answered in polynomial time. In this paper, we extend this algorithmic question to deterministic automata beyond finite automata. We prove that the question of synchronizability becomes undecidable even when looking at deterministic one-counter automata. This is also true for another classical mild extension of regularity, namely that of deterministic one-turn push-down automata. However, when we combine both restrictions, we arrive at scenarios with a PSPACE-complete (and hence decidable) synchronizability problem. Likewise, we arrive at a decidable synchronizability problem for (partially) blind deterministic counter automata.
There are several interpretations of what synchronizability should mean for deterministic push-down automata. This is depending on the role of the stack: should it be empty on synchronization, should it be always the same or is it arbitrary? For the automata classes studied in this paper, the complexity or decidability status of the synchronizability problem is mostly independent of this technicality, but we also discuss one class of automata where this makes a difference.
For the entire collection see [Zbl 1445.68013].
There are several interpretations of what synchronizability should mean for deterministic push-down automata. This is depending on the role of the stack: should it be empty on synchronization, should it be always the same or is it arbitrary? For the automata classes studied in this paper, the complexity or decidability status of the synchronizability problem is mostly independent of this technicality, but we also discuss one class of automata where this makes a difference.
For the entire collection see [Zbl 1445.68013].
MSC:
| 68Qxx | Theory of computing |
Keywords:
synchronizing automaton; reset sequence; real-time deterministic push-down automaton; finite-turn push-down automaton; computability; computational complexityReferences:
| [1] | Laurent Doyen, Line Juhl, Kim Guldstrand Larsen, Nicolas Markey, and Mahsa Shirmo-hammadi. Synchronizing Words for Weighted and Timed Automata. In 34th International Conference on Foundation of Software Technology and Theoretical Computer Science, FSTTCS 2014, December 15-17, 2014, New Delhi, India, pages 121-132, 2014. · Zbl 1360.68552 |
| [2] | David Eppstein. Reset Sequences for Monotonic Automata. SIAM Journal on Computing, 19(3):500-510, 1990. · Zbl 0698.68058 |
| [3] | Henning Fernau and Petra Wolf. Synchronization of Deterministic Visibly Push-Down Au-tomata. CoRR, abs/2005.01374, 2020. arXiv:2005.01374. |
| [4] | Emily P. Friedman. The Inclusion Problem for Simple Languages. Theoretical Computer Science, 1(4):297-316, 1976. · Zbl 0349.68032 |
| [5] | Seymour Ginsburg. The Mathematical Theory of Context-Free Languages. McGraw-Hill, 1966. · Zbl 0195.02301 |
| [6] | Seymour Ginsburg and Edwin H Spanier. Finite-Turn Pushdown Automata. SIAM Journal on Control, 4(3):429-453, 1966. · Zbl 0147.25302 |
| [7] | Sheila A. Greibach. Remarks on Blind and Partially Blind One-Way Multicounter Machines. Theoretical Computer Science, 7:311-324, 1978. · Zbl 0389.68030 |
| [8] | Timothy V. Griffiths. The unsolvability of the equivalence problem for lambda-free nondeter-ministic generalized machines. J. ACM, 15(3):409-413, 1968. doi:10.1145/321466.321473. · Zbl 0162.02302 · doi:10.1145/321466.321473 |
| [9] | Eitan M. Gurari and Oscar H. Ibarra. The Complexity of Decision Problems for Finite-Turn Multicounter Machines. Journal of Computer and System Sciences, 22(2):220-229, 1981. · Zbl 0458.68011 |
| [10] | Ken Higuchi, Mitsuo Wakatsuki, and Etsuji Tomita. A Polynomial-Time Algorithm for Checking the Inclusion for Real-Time Deterministic Restricted One-Counter Automata Which Accept by Final State. IEICE Transactions on Information and Systems, 78-D(8):939-950, 1995. |
| [11] | Oscar H. Ibarra. The unsolvability of the equivalence problem for epsilon-free ngsm’s with unary input (output) alphabet and applications. SIAM J. Comput., 7(4):524-532, 1978. doi:10.1137/0207042. · Zbl 0386.68054 · doi:10.1137/0207042 |
| [12] | Balázs Imreh and Magnus Steinby. Directable Nondeterministic Automata. Acta Cybernetica, 14(1):105-115, 1999. · Zbl 0959.68060 |
| [13] | Szabolcs Iván. Synchronizing weighted automata. In Zoltán Ésik and Zoltán Fülöp, editors, Proceedings 14th International Conference on Automata and Formal Languages, AFL 2014, Szeged, Hungary, May 27-29, 2014, volume 151 of EPTCS, pages 301-313, 2014. doi: 10.4204/EPTCS.151.21. · Zbl 1464.68172 · doi:10.4204/EPTCS.151.21 |
| [14] | Changwook Kim. Quasi-Rocking Real-Time Pushdown Automata. Theoretical Computer Science, 412(48):6720-6735, 2011. · Zbl 1227.68060 |
| [15] | Zvi Kohavi and Niraj K. Jha. Switching and Finite Automata Theory. Cambridge University Press, 3rd edition, 2009. · Zbl 1222.94047 |
| [16] | S. Rao Kosaraju. Decidability of Reachability in Vector Addition Systems (Preliminary Version). In Harry R. Lewis, Barbara B. Simons, Walter A. Burkhard, and Lawrence H. |
| [17] | Landweber, editors, Proceedings of the 14th Annual ACM Symposium on Theory of Computing, May 5-7, 1982, San Francisco, California, USA, pages 267-281. ACM, 1982. |
| [18] | Pavel Martyugin. Computational Complexity of Certain Problems Related to Carefully Syn-chronizing Words for Partial Automata and Directing Words for Nondeterministic Automata. Theory of Computing Systems, 54(2):293-304, 2014. · Zbl 1380.68257 |
| [19] | Yuri V. Matiyasevich and Géraud Sénizergues. Decision Problems for Semi-Thue Systems with a few Rules. Theoretical Computer Science, 330(1):145-169, 2005. · Zbl 1078.03033 |
| [20] | Ernst W. Mayr. An Algorithm for the General Petri Net Reachability Problem. In Proceedings of the 13th Annual ACM Symposium on Theory of Computing, May 11-13, 1981, Milwaukee, Wisconsin, USA, pages 238-246. ACM, 1981. |
| [21] | Kurt Mehlhorn. Pebbling Moutain Ranges and its Application of DCFL-Recognition. In J. W. de Bakker and Jan van Leeuwen, editors, Automata, Languages and Programming, 7th 33:15 · Zbl 0445.68033 |
| [22] | Colloquium, Noordweijkerhout, The Netherlands, July 14-18, 1980, Proceedings, volume 85 of Lecture Notes in Computer Science, pages 422-435. Springer, 1980. · Zbl 0426.00014 |
| [23] | Eitatsu Mikami and Tomoyuki Yamakami. Synchronizing Pushdown Automata and Reset Words, 2020. An article appeared in Japanese as Technical Report of the Institute of Electronics, Information and Communication Engineers, COMP2019-54(2020-03), pp. 57-63. An English translation is in preparation. |
| [24] | Marvin L Minsky. Recursive Unsolvability of Post’s Problem of “Tag” and Other Topics in Theory of Turing Machines. Annals of Mathematics, pages 437-455, 1961. · Zbl 0105.00802 |
| [25] | Turlough Neary. Undecidability in Binary Tag Systems and the Post Correspondence Problem for Five Pairs of Words. In Ernst W. Mayr and Nicolas Ollinger, editors, 32nd International Symposium on Theoretical Aspects of Computer Science, STACS 2015, March 4-7, 2015, Garching, Germany, volume 30 of LIPIcs, pages 649-661. Schloss Dagstuhl -Leibniz-Zentrum für Informatik, 2015. · Zbl 1356.68068 |
| [26] | Emil L. Post. A Variant of a Recursively Unsolvable Problem. Bulletin of the American Mathematical Society, 52(4):264-268, 1946. · Zbl 0063.06329 |
| [27] | I. K. Rystsov. On Minimizing the Length of Synchronizing Words for Finite Automata. In Theory of Designing of Computing Systems, pages 75-82. Institute of Cybernetics of Ukrainian Acad. Sci., 1980. (in Russian). |
| [28] | I. K. Rystsov. Polynomial Complete Problems in Automata Theory. Information Processing Letters, 16(3):147-151, 1983. · Zbl 0508.68030 |
| [29] | Sven Sandberg. Homing and Synchronizing Sequences. In Manfred Broy, Bengt Jonsson, Joost-Pieter Katoen, Martin Leucker, and Alexander Pretschner, editors, Model-Based Testing of Reactive Systems, Advanced Lectures, volume 3472 of LNCS, pages 5-33. Springer, 2005. · Zbl 1070.68088 |
| [30] | Géraud Sénizergues. The Equivalence and Inclusion Problems for NTS Languages. Journal of Computer and System Sciences, 31(3):303-331, 1985. · Zbl 0604.68086 |
| [31] | Mahsa Shirmohammadi. Qualitative Analysis of Synchronizing Probabilistic Systems. (Analyse qualitative des systèmes probabilistes synchronisants). PhD thesis, École normale supérieure de Cachan, France, 2014. URL: https://tel.archives-ouvertes.fr/tel-01153942. |
| [32] | Yaroslav Shitov. An Improvement to a Recent Upper Bound for Synchronizing Words of Finite Automata. Journal of Automata, Languages and Combinatorics, 24(2-4):367-373, 2019. · Zbl 1447.68007 |
| [33] | Peter H. Starke. Eine Bemerkung über homogene Experimente. Elektronische Informationsver-arbeitung und Kybernetik, 2(4):257-259, 1966. · Zbl 0166.27003 |
| [34] | Peter H. Starke. A Remark About Homogeneous Experiments. Journal of Automata, Languages and Combinatorics, 24(2-4):133-137, 2019. · Zbl 1429.68134 |
| [35] | Marek Szykuła. Improving the Upper Bound on the Length of the Shortest Reset Word. In Rolf Niedermeier and Brigitte Vallée, editors, 35th Symposium on Theoretical Aspects of Computer Science, STACS 2018, February 28 to March 3, 2018, Caen, France, volume 96 of LIPIcs, pages 56:1-56:13. Schloss Dagstuhl -Leibniz-Zentrum für Informatik, 2018. · Zbl 1440.68164 |
| [36] | Leslie G. Valiant. Decision Procedures for Families of Deterministic Pushdown Automata. PhD thesis, University of Warwick, Coventry, UK, 1973. URL: http://wrap.warwick.ac.uk/ 34701/. |
| [37] | Mikhail V. Volkov. Synchronizing Automata and the Černý Conjecture. In Carlos Martín-Vide, Friedrich Otto, and Henning Fernau, editors, Language and Automata Theory and Applications, Second International Conference, LATA, volume 5196 of LNCS, pages 11-27. Springer, 2008. · Zbl 1156.68466 |
| [38] | Mitsuo Wakatsuki and Etsuji Tomita. A Fast Algorithm for Checking the Inclusion for Very Simple Deterministic Pushdown Automata. IEICE Transactions on Information and Systems, 76-D(10):1224-1233, 1993. |
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.
