Abstract
An automaton is synchronizable if there exists an input that drives it into a definite state from any other state. This notion has been studied for various types of automata. In this work, we investigate notions of synchronizability for Parikh automata (PAs). A Parikh automaton is an automaton with counters that are checked against a semilinear set at the end of the computation. We consider several notions of synchronizability (or directability) for PAs and show that they lead to decidable and PSPACE-complete problems, even for deterministic and complete Parikh automata (DCPAs) on letters. Then, we demonstrate that for DCPAs on letters, the synchronization problems are NP-complete over a unary alphabet, and NP-complete and solvable in polynomial time over a binary and a unary alphabet, respectively, if the dimension is fixed and numbers are encoded in unary. For a unary alphabet, we also provide other restrictions that ensure polynomial-time solvability. We then show that for partially ordered Parikh automata whose semilinear constraint sets have a regular Parikh-inverse image, deciding \(\exists \forall \)-\(D_3\)-directability is NP-complete. Additionally, we prove that deciding \(D_3\)-directability for partially ordered nondeterministic complete word automata is in AC\(^0\).
Data Availability
No datasets were generated or analysed during the current study.
Notes
By the emptiness problem for a set we denote the decision problem to decide whether the set is empty.
One mistake regards usage of an automaton to represent the semilinear set, and using a factorization of words accepted by the automaton w.r.t. sequences of vectors whose sum is in the semilinear set that is, in general, not possible. Another mistake concerns a construction that actually yields a double-exponential blow-up (which was not noticed in the conference version), whereas the construction from the present work is altered such that only a single-exponential blow-up results; this is briefly discussed in the proof of Theorem 3.2. The last mistake was the exclusion of the empty set in the definition of \(E_2\) in the proof of Theorem 3.2.
We interpret \((S_1, \ldots , S_n, \vec {d}_1, \ldots , \vec {d}_{0})\) as \((S_1, \ldots , S_n)\).
We set \(v_1 \cdots v_0 = \varepsilon \) and \(\vec {c}_1 + \cdots + \vec {c}_0\) equal to the zero vector.
References
Büchi, J.R.: Weak second-order arithmetic and finite automata. Math. Log. Q. 6(1–6), 66–92 (1960). https://doi.org/10.1002/malq.19600060105
Elgot, C.C.: Decision problems of finite automata design and related arithmetics. Trans. Am. Math. Soc. 98(1), 21–51 (1961). https://doi.org/10.1090/S0002-9947-1961-0139530-9
Trakhtenbrot, B.A.: Finite automata and the logic of one-place predicates. Sibirskii Matematicheskii Zhurnal. 3(1), 103–131 (1962). (in Russian, English translation in Twelve Papers on Logic and Algebra, N. I. Feldman, A. V. Kuznecov, Ju. I. Manin, I. R. Šafarević, E. G. Šulgeĭfer, A. D. Taimanov, B. A. Trahtenbrot and A. I. Vinogradov, American Mathematical Society Translations: Series 2 (1966) 59 ISBN 978-0-8218-1759-9 (print); 978-1-4704-3270-6 (online) https://doi.org/10.1090/trans2/059
Vardi, M.Y.: An automata-theoretic approach to linear temporal logic. In: Logics for Concurrency, pp. 238–266. Lecture Notes in Computer Science (1996)
Vardi, M.Y., Wolper, P.: An automata-theoretic approach to automatic program verification (Preliminary Report). In: Proceedings of the Symposium on Logic in Computer Science (LICS ’86), USA, pp. 332–344. Cambridge, Massachusetts, USA, IEEE Computer Society (1986)
Straubing, H., Weil, P.: An introduction to finite automata and their connection to logic. In: D’Souza, D., Shankar, P., (eds.) Modern Applications of Automata Theory vol. 2 of IISc Research Monographs Series, pp. 3–44. 5 Toh Tuck Link, Singapore 596224: World Scientific (2012)
Schüle, T.: Verification of infinite state systems using Presburger arithmetic [Ph.D. thesis]. University of Kaiserslautern (2007). Available from: https://d-nb.info/985380225
Thomas, W.: Languages, automata, and logic. In: Rozenberg, G., Salomaa, A., (eds.) Handbook of Formal Languages, Volume 3: Beyond Words, pp. 389–455. Berlin, Heidelberg, Springer (1997). Available from: https://doi.org/10.1007/978-3-642-59126-6_7
Klarlund N, Møller A.: MONA Version 1.4 User Manual. Notes Series NS-01-1. Available from http://www.brics.dk/mona/
Basin, D.A., Friedrich, S.: Combining WS1S and HOL. In: Gabbay, D.M., de Rijke, M., (eds.) Frontiers of Combining Systems, Second International Workshop, FroCoS 1998, October 2-4, 1998, Proceedings, pp. 39–56. Amsterdam, The Netherlands: Research Studies Press/Wiley (1998)
Owre, S., Rueß, H.: Integrating WS1S with PVS. In: Emerson, E.A., Sistla, A.P., (eds.) Computer Aided Verification, 12th International Conference, CAV 2000, Chicago, IL, USA, July 15-19, 2000, Proceedings. vol. 1855 of Lecture Notes in Computer Science, pp. 548–551. Berlin, Heidelberg, Springer (2000). Available from:https://doi.org/10.1007/10722167_42
Gómez, R., Bowman, H.: Discrete timed automata and MONA: Description, specification and verification of a multimedia stream. In: König, H., Heiner, M., Wolisz, A., (eds.) Formal Techniques for Networked and Distributed Systems - FORTE 2003, 23rd IFIP WG 6.1 International Conference, September 29 - October 2, 2003, Proceedings. vol. 2767 of Lecture Notes in Computer Science, pp. 177–192. Berlin, Germany, Springer (2003). Available from:https://doi.org/10.1007/978-3-540-39979-7_12
Parikh, R.: On context-free languages. J. ACM 13(4), 570–581 (1966). https://doi.org/10.1145/321356.321364
Ginsburg, S., Spanier, E.H.: Bounded ALGOL-like languages. Trans. Am. Math. Soc. 113(2), 333–368 (1964). https://doi.org/10.1090/S0002-9947-1964-0181500-1
Chomsky, N.: Context-free grammars and pushdown storage. MIT Research Laboratory Electronics Quarterly Progress Report. 65, 187–194 (1962)
Ibarra, O.H.: Reversal-bounded multicounter machines and their decision problems. J. ACM 25(1), 116–133 (1978). https://doi.org/10.1145/322047.322058
Ibarra, O.H., McQuillan, I.: Semilinearity of families of languages. Int. J. Found. Comput. Sci. 31(8), 1179–1198 (2020). https://doi.org/10.1142/S0129054120420095
Ibarra, O.H., Su, J., Dang, Z., Bultan, T., Kemmerer, R.A.: Counter machines and verification problems. Theoret. Comput. Sci. 289(1), 165–189 (2002). https://doi.org/10.1016/S0304-3975(01)00268-7
Ibarra, O.H., Bultan, T., Su, J.: Reachability analysis for some models of infinite-state transition systems. In: Palamidessi, C. (ed.) CONCUR 2000 - Concurrency Theory, 11th International Conference, University Park, PA, USA, August 22-25, 2000, Proceedings. vol. 1877 of Lecture Notes in Computer Science, pp. 183–198. Berlin, Heidelberg, Springer (2000). Available from: https://doi.org/10.1007/3-540-44618-4_15
Bouajjani, A., Habermehl, P.: Constrained properties, semilinear systems, and petri nets. In: Montanari, U., Sassone, V. (eds.) CONCUR ’96, Concurrency Theory, 7th International Conference, Pisa, Italy, August 26-29, 1996, Proceedings. vol. 1119 of Lecture Notes in Computer Science, pp. 481–497. Berlin, Heidelberg, Springer (1996). Available from: https://doi.org/10.1007/3-540-61604-7_71
Klaedtke, F., Rueß, H.: Monadic second-order logics with cardinalities. In: Baeten, J.C.M., Lenstra, J.K., Parrow, J., Woeginger, G.J. (eds.) Automata, Languages and Programming, 30th International Colloquium, ICALP 2003, Eindhoven, The Netherlands, June 30 - July 4, 2003. Proceedings. vol. 2719 of Lecture Notes in Computer Science, pp. 681–696. Berlin, Heidelberg, Springer, (2003). Available fromhttps://doi.org/10.1007/3-540-45061-0_54
Figueira, D., Libkin, L.: Path logics for querying graphs: Combining expressiveness and efficiency. In: 30th Annual ACM/IEEE Symposium on Logic in Computer Science, LICS 2015, Kyoto, Japan, July 6-10, 2015, pp. 329–340. IEEE Computer Society, (2015). Available from:https://doi.org/10.1109/LICS.2015.39
Cadilhac, M., Finkel, A., McKenzie, P.: Bounded Parikh automata. Int. J. Found. Comput. Sci. 23(8), 1691–1710 (2012). https://doi.org/10.1142/S0129054112400709
Cadilhac, M., Finkel, A., McKenzie, P.: Affine Parikh automata. RAIRO - Theor. Inform. Appl. 46(4), 511–545 (2012). https://doi.org/10.1051/ita/2012013
Klaedtke, F., Rueß, H.: Parikh automata and monadic second-order logics with linear cardinality constraints. Albert-Ludwigs-Universität Freiburg 177 (2002)
Clemente, L., Czerwinski, W., Lasota, S., Paperman, C.: Regular separability of Parikh automata. In: Chatzigiannakis, I., Indyk, P., Kuhn, F., Muscholl, A. (eds.) 44th International Colloquium on Automata, Languages, and Programming, ICALP 2017, July 10-14, 2017, Warsaw, Poland. vol. 80 of LIPIcs, pp. 117:1 – 11713. Schloss Dagstuhl - Leibniz-Zentrum für Informatik, (2017). Available from: https://doi.org/10.4230/LIPIcs.ICALP.2017.117
Collins, E.R., Köcher, C., Zetzsche, G.: The complexity of separability for semilinear sets and Parikh automata (2024). arXiv:abs/2410.00548. https://doi.org/10.48550/ARXIV.2410.00548
Karianto, W.: Parikh automata with pushdown stack [Diplomarbeit]. RWTH Aachen, (2004). Available from: https://old.automata.rwth-aachen.de/download/papers/karianto/ka04.pdf
Filiot, E., Guha, S., Mazzocchi, N.: Two-way Parikh automata. In: Chattopadhyay, A., Gastin, P. (eds.) 39th IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science, FSTTCS 2019, December 11-13, 2019. vol. 150 of LIPIcs, pp. 40:1–40:14. Schloss Dagstuhl - Leibniz-Zentrum für Informatik, (2019). Available from: https://doi.org/10.4230/LIPIcs.FSTTCS.2019.40
Dartois, L., Filiot, E, Talbot J. Two-Way Parikh Automata with a Visibly Pushdown Stack. In: Bojanczyk M, Simpson A, editors. Foundations of Software Science and Computation Structures - 22nd International Conference, FOSSACS 2019, Held as Part of the European Joint Conferences on Theory and Practice of Software, ETAPS 2019, Prague, Czech Republic, April 6-11, 2019, Proceedings. vol. 11425 of Lecture Notes in Computer Science, pp. 189–206. Springer, (2019). Available from: https://doi.org/10.1007/978-3-030-17127-8_11
Guha, S., Jecker, I., Lehtinen, K., Zimmermann, M.: Parikh Automata over Infinite Words. In: Dawar, A., Guruswami, V. (eds.) 42nd IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science, FSTTCS 2022, December 18-20, 2022, IIT Madras, Chennai, India. vol. 250 of LIPIcs, pp. 40:1–40:20. Schloss Dagstuhl - Leibniz-Zentrum für Informatik; (2022). Available from:https://doi.org/10.4230/LIPIcs.FSTTCS.2022.40
Grobler, M., Sabellek, L., Siebertz, S.: Remarks on Parikh-recognizable omega-languages. In: Murano, A., Silva, A. (eds.) 32nd EACSL Annual Conference on Computer Science Logic, CSL 2024, February 19-23, 2024, Naples, Italy. vol. 288 of LIPIcs, pp. 31:1–31:21. Schloss Dagstuhl - Leibniz-Zentrum für Informatik (2024). Available from: https://doi.org/10.4230/LIPIcs.CSL.2024.31
Grobler, M., Siebertz, S.: Deterministic Parikh automata on infinite words (2024). arXiv:2401.14737. https://doi.org/10.48550/ARXIV.2401.14737
Bostan, A., Carayol, A., Koechlin, F., Nicaud, C.: Weakly-Unambiguous Parikh Automata and Their Link to Holonomic Series. In: Czumaj, A., Dawar, A., Merelli, E. (eds.) 47th International Colloquium on Automata, Languages, and Programming, ICALP 2020, July 8-11, 2020. vol. 168 of LIPIcs, pp. 114:1–114:16. Saarbrücken, Germany (Virtual Conference): Schloss Dagstuhl - Leibniz-Zentrum für Informatik, (2020). Available from: https://doi.org/10.4230/LIPIcs.ICALP.2020.114
Erlich, E., Guha, S., Jecker, I., Lehtinen, K., Zimmermann, M.: History-deterministic Parikh Automata. In: Pérez, G.A., Raskin, J. (eds.). 34th International Conference on Concurrency Theory, CONCUR 2023, September 18-23, 2023, Antwerp, Belgium. vol. 279 of LIPIcs, pp. 31:1–31:16. Schloss Dagstuhl - Leibniz-Zentrum für Informatik, (2023). Available from: https://doi.org/10.4230/LIPIcs.CONCUR.2023.31
Herrmann, L., Peth, V., Rudolph, S.: Decidable (Ac)counting with Parikh and Muller: Adding Presburger arithmetic to monadic second-order logic over tree-interpretable structures. In: Murano A, Silva A, editors. 32nd EACSL Annual Conference on Computer Science Logic, CSL 2024, February 19-23, 2024, Naples, Italy. vol. 288 of LIPIcs, pp. 33:1–33:19. Schloss Dagstuhl - Leibniz-Zentrum für Informatik, (2024). Available from: https://doi.org/10.4230/LIPIcs.CSL.2024.33
Herrmann, L., Osterholzer, J.: Non-global Parikh tree automata. In: Manea, F., Pighizzini, G. (eds.) Proceedings 14th International Workshop on Non-Classical Models of Automata and Applications (NCMA 2024), NCMA 2024, Göttingen, Germany, 12-13 August 2024. vol. 407 of EPTCS, pp. 100–117 (2024). Available from: https://doi.org/10.4204/EPTCS.407.8
Cadilhac, M., Krebs, A., McKenzie, P.: The algebraic theory of Parikh automata. Theoret. Comput. Sci. 62(5), 1241–1268 (2018). https://doi.org/10.1007/S00224-017-9817-2
Sandberg, S.: Homing and Synchronizing Sequences. In: Brøy, M., Jonsson, B., Katoen, J., Leucker, M., Pretschner, A. (eds.) Model-Based Testing of Reactive Systems, Advanced Lectures [The volume is the outcome of a research seminar that was held in Schloss Dagstuhl in January 2004]. vol. 3472 of Lecture Notes in Computer Science, pp. 5–33. Springer, Heidelberg, Springer (2004). Available from: https://doi.org/10.1007/11498490_2
Kari, J., Volkov, M.V.: Černý’s conjecture and the road colouring problem. In: Pin, J.É. (eds.) Handbook of Automata Theory, Volume I. European Mathematical Society Publishing House pp. 525–565 (2021)
Černý, J., Poznámka, K.: Homogénnym Experimentom s Konečnými Automatami. Matematicko-fyzikálny časopis 14(3), 208–216 (1964). (Translation: A Note on Homogeneous Experiments with Finite Automata. Journal of Automata, Languages and Combinatorics 24 (2019) 2-4, 123–132.https://doi.org/10.25596/jalc-2019-123
Liu, C.L.: Some memory aspects of finite automata. Research Lab. Electronics, Massachusetts Inst., MIT Res. Lab. Electronics, Cambridge, MA 411 (1963)
Laemmel, A.E.: Study on application of coding theory. Dept. Electrophysics, Microwave Research Inst., Polytechnic Inst., Brooklyn, NY 1963A; (1963). PIBMRI-895.5-63
Volkov, M.V.: Synchronization of Finite Automata. Russ. Math. Surv. 77(5), 819–891 (2022). https://doi.org/10.4213/rm10005e
Martyugin, P.: Computational complexity of certain problems related to carefully synchronizing words for partial automata and directing words for nondeterministic automata. Theory Comput. Syst. 54(2), 293–304 (2014). https://doi.org/10.1007/s00224-013-9516-6
Imreh, B., Steinby, M.: Directable Nondeterministic Automata. Acta Cybern. 14(1), 105–115 (1999)
Doyen, L., Juhl, L., Larsen, K.G., Markey, N., Shirmohammadi, M.: Synchronizing Words for Weighted and Timed Automata. In: Raman, V., Suresh, S.P. (eds.) 34th International Conference on Foundation of Software Technology and Theoretical Computer Science, FSTTCS 2014, December 15-17, 2014, New Delhi, India. vol. 29 of LIPIcs, pp. 121–132. Schloss Dagstuhl - Leibniz-Zentrum für Informatik; (2014). Available from: https://doi.org/10.4230/LIPIcs.FSTTCS.2014.121
Quaas, K., Shirmohammadi, M.: Synchronizing data words for register automata. ACM Trans. Comput. Log. 20(2), 1–27 (2019). https://doi.org/10.1145/3309760
Chistikov, D., Martyugin, P., Shirmohammadi, M.: Synchronizing automata over nested words. J. Autom. Lang. Comb. 24(2–4), 219–251 (2019). https://doi.org/10.25596/jalc-2019-219
Doyen, L., Massart, T., Shirmohammadi, M.: The complexity of synchronizing Markov decision processes. J. Comput. Syst. Sci. 100, 96–129 (2019). https://doi.org/10.1016/j.jcss.2018.09.004
Doyen, L., Massart, T., Shirmohammadi, M.: Infinite synchronizing words for probabilistic automata. In: Murlak, F., Sankowski, P. (eds.) Mathematical Foundations of Computer Science 2011 - 36th International Symposium, MFCS 2011, Warsaw, Poland, August 22-26, 2011, pp. 278–289.. Proceedings. vol. 6907 of Lecture Notes in Computer Science. Springer (2011). Available from: https://doi.org/10.1007/978-3-642-22993-0_27
Kfoury, D.J.: Synchronizing sequences for probabilistic automata. Stud. Appl. Math. 49, 101–103 (1970). https://doi.org/10.1002/sapm1970491101
Doyen, L., Massart, T., Shirmohammadi, M.: Infinite synchronizing words for probabilistic automata (Erratum). arXiv:1206.0995 (2012)
Balasubramanian, A.R., Thejaswini, K.S.: Adaptive synchronisation of pushdown automata. In: Haddad, S., Varacca, D. (eds.) 32nd International Conference on Concurrency Theory, CONCUR 2021, August 24-27, 2021. vol. 203 of LIPIcs, pp. 17:1–17:15. Virtual Conference: Schloss Dagstuhl - Leibniz-Zentrum für Informatik (2021). Available from: https://doi.org/10.4230/LIPIcs.CONCUR.2021.17
Fernau, H., Wolf, P.: Synchronization of deterministic visibly push-down automata. In: Saxena, N., Simon, S. (eds.) 40th IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science, FSTTCS 2020, December 14-18, 2020, BITS Pilani, K K Birla Goa Campus, Goa, India (Virtual Conference). vol. 182 of LIPIcs, pp. 45:1–45:15. Schloss Dagstuhl - Leibniz-Zentrum für Informatik, (2020). Available from: https://doi.org/10.4230/LIPIcs.FSTTCS.2020.45
Fernau, H., Wolf, P., Yamakami, T.: Synchronizing deterministic push-down automata can be really hard. Inf. Comput. 295(Part B), 105089 (2023). https://doi.org/10.1016/J.IC.2023.105089
Fominykh, F.M., Martyugin, P.V., Volkov, M.V.: P(l)aying for Synchronization. Int. J. Found. Comput. Sci. 24(6), 765–780 (2013). https://doi.org/10.1142/S0129054113400170
Chatterjee, K., Doyen, L.: Computation Tree Logic for Synchronization Properties. In: Chatzigiannakis, I., Mitzenmacher, M., Rabani, Y., Sangiorgi, D., (eds.) 43rd International Colloquium on Automata, Languages, and Programming, ICALP 2016, July 11-15, 2016, Rome, Italy. vol. 55 of LIPIcs, pp. 98:1–98:14. Schloss Dagstuhl - Leibniz-Zentrum für Informatik; (2016). Available from: https://doi.org/10.4230/LIPIcs.ICALP.2016.98
Eppstein, D.: Reset sequences for monotonic automata. SIAM J. Comput. 19(3), 500–510 (1990). https://doi.org/10.1137/0219033
Rystsov, I.K.: On minimizing the length of synchronizing words for finite automata. In: Theory of designing of computing systems. Institute of Cybernetics of Ukrainian Acad. Sci. pp. 75–82. (1980) (in Russian)
Hoffmann, S.: Synchronization of Parikh Automata. In: Drewes, F., Volkov, M. (eds.) Developments in Language Theory - 27th International Conference, DLT 2023, Umeå, Sweden, June 12-16, 2023, Proceedings. vol. 13911 of Lecture Notes in Computer Science, pp. 113–127. Cham: Springer (2023). Available from: https://doi.org/10.1007/978-3-031-33264-7_10
Hopcroft, J.E., Ullman, J.D.: Introduction to automata theory, languages, and computation. Addison-Wesley Publishing Company (1979)
Vollmer, H.: Introduction to circuit complexity - a uniform approach. Texts in Theoretical Computer Science. An EATCS Series. Springer (1999). Available from:https://doi.org/10.1007/978-3-662-03927-4
Chistikov, D., Haase, C.: The taming of the semi-linear set. In: Chatzigiannakis, I., Mitzenmacher, M., Rabani, Y., Sangiorgi, D. (eds.) 43rd International Colloquium on Automata, Languages, and Programming, ICALP 2016, July 11-15, 2016, Rome, Italy. vol. 55 of LIPIcs, pp. 128:1–128:13. Schloss Dagstuhl - Leibniz-Zentrum für Informatik, (2016). Available from: https://doi.org/10.4230/LIPIcs.ICALP.2016.128
Pottier, L.: Minimal solutions of linear diophantine systems: Bounds and Algorithms. In: Book, R.V. (ed) Rewriting techniques and applications, 4th International Conference, RTA-91, Como, Italy, April 10-12, 1991, Proceedings. vol. 488 of Lecture Notes in Computer Science, pp. 162–173. Springer (1991). Available from: https://doi.org/10.1007/3-540-53904-2_94
Domenjoud, E.: Solving systems of linear diophantine equations: An Algebraic Approach. In: Tarlecki, A. (ed.) Mathematical Foundations of Computer Science 1991, 16th International Symposium, MFCS’91, Kazimierz Dolny, Poland, September 9-13, 1991, Proceedings. vol. 520 of Lecture Notes in Computer Science, pp. 141–150. Springer (1991). Available from:https://doi.org/10.1007/3-540-54345-7_57
Beier, S., Holzer, M., Kutrib, M.: On the descriptional complexity of operations on semilinear sets. In: Csuhaj-Varjú, E., Dömösi, P., Vaszil, G. (eds.) Proceedings 15th International Conference on Automata and Formal Languages, AFL 2017, Debrecen, Hungary, September 4-6, 2017. vol. 252 of EPTCS, pp. 41–55 (2017). Available from:https://doi.org/10.4204/EPTCS.252.8
Kopczynski, E., To, A.W.: Parikh images of grammars: Complexity and applications. In: Proceedings of the 25th Annual IEEE Symposium on Logic in Computer Science, LICS 2010, 11-14 July 2010, pp. 80–89. Edinburgh, UK: IEEE Computer Society (2010). Available from: https://doi.org/10.1109/LICS.2010.21
To, A.W.: Model checking infinite-state systems: Generic and specific approaches [Ph.D. thesis]. University of Edinburgh; 2010. Available from: http://hdl.handle.net/1842/4671
Fernau, H., Gusev, V.V., Hoffmann, S., Holzer, M., Volkov, M.V., Wolf, P.: Computational complexity of synchronization under regular constraints. In: Rossmanith, P., Heggernes, P., Katoen, J. (eds.) 44th International Symposium on Mathematical Foundations of Computer Science, MFCS 2019, August 26-30, 2019, Aachen, Germany. vol. 138 of LIPIcs, pp. 63:1–63:14. Schloss Dagstuhl - Leibniz-Zentrum für Informatik (2019). Available from: https://doi.org/10.4230/LIPIcs.MFCS.2019.63
Hoffmann, S.: Constrained synchronization and commutativity. Theoret. Comput. Sci. 890, 147–170 (2021). https://doi.org/10.1016/j.tcs.2021.08.030
Savitch, W.J.: Relationships between nondeterministic and deterministic tape complexities. J. Comput. Syst. Sci. 4(2), 177–192 (1970). https://doi.org/10.1016/S0022-0000(70)80006-X
Frankl, P.: An extremal problem for two families of sets. Eur. J. Comb. 3, 125–127 (1982). https://doi.org/10.1016/S0195-6698(82)80025-5
Pin, J.É.: On two combinatorial problems arising from automata theory. Ann. Discrete Math. 17, 535–548 (1983). https://doi.org/10.1016/S0304-0208(08)73432-7
Klyachko, A.A,, Rystsov, I.K., Spivak, M.A.: An extremal combinatorial problem associated with the bound on the length of a synchronizing word in an automaton. Kibernetika. 1987;2:16–20. In Russian; Engl. translation: Cybernetics and Systems Analysis 23 (1987) 165–171. https://doi.org/10.1007/BF01071771
Papadimitriou, C.H.: On the complexity of integer programming. J. ACM 28(4), 765–768 (1981). https://doi.org/10.1145/322276.322287
Huynh, T.: The Complexity of semilinear sets. In: de Bakker, J.W., van Leeuwen, J. (eds.) Automata, Languages and Programming, 7th Colloquium, Noordweijkerhout, The Netherlands, July 14-18, 1980, Proceedings. vol. 85 of Lecture Notes in Computer Science, pp. 324–337. Berlin, Heidelberg: Springer, 1980. Available from: https://doi.org/10.1007/3-540-10003-2_81
Huynh, T.: The complexity of semilinear sets. Elektronische Informationsverarbeitung und Kybernetik/Journal of Information Processing and Cybernetics (now Journal of Automata, Languages and Combinatorics) 18(6), 291–338 (1982)
Ibarra, O.H., Ravikumar, B.: On the Parikh Membership Problem for FAs, PDAs, and CMs. In: Dediu, A., Martín-Vide, C., Sierra-Rodríguez, J.L., Truthe, B. (eds.) Language and Automata Theory and Applications - 8th International Conference, LATA 2014, Madrid, Spain, March 10-14, 2014. Proceedings. vol. 8370 of Lecture Notes in Computer Science, pp. 14–31. Cham: Springer (2014). Available from:https://doi.org/10.1007/978-3-319-04921-2_2
Eisenbrand, F., Weismantel, R.: Proximity results and faster algorithms for integer programming using the Steinitz lemma. ACM Trans. Algorithms 16(1) (2019).https://doi.org/10.1145/3340322
Gathen, J., Sieveking, M.: A bound on solutions of linear integer equalities and inequalities. Proc. Am. Math. Soc. 10(72), 155–155 (1978). https://doi.org/10.2307/2042554
Lenstra, H.W., Jr.: Integer programming with a fixed number of variables. Math. Oper. Res. 8(4), 538–548 (1983). https://doi.org/10.1287/MOOR.8.4.538
Ryzhikov, A.: Synchronization problems in automata without non-trivial cycles. Theor. Comput. Sci. 787, 77–88 (2019). https://doi.org/10.1016/j.tcs.2018.12.026
Schwentick, T., Thérien, D., Vollmer, H.: Partially-ordered two-way automata: A new characterization of DA. In: Kuich, W., Rozenberg, G., Salomaa, A. (eds.) Developments in language theory, 5th International Conference, DLT 2001, Vienna, Austria, July 16-21, 2001, Revised Papers. vol. 2295 of Lecture Notes in Computer Science, pp. 239–250. Berlin, Heidelberg: Springer (2001). Available from: https://doi.org/10.1007/3-540-46011-X_20
Brzozowski, J.A., Fich, F.E.: Languages of R-trivial monoids. J. Comput. Syst. Sci. 20(1), 32–49 (1980). https://doi.org/10.1016/0022-0000(80)90003-3
Eilenberg, S.: Automata, Languages, and Machines, vol. A. Academic Press Inc, Orlando, FL, USA (1974)
Mezei, J.E., Wright, J.B.: Algebraic automata and context-free sets. Inf. Comput. 11(1/2), 3–29 (1967). https://doi.org/10.1016/S0019-9958(67)90353-1
Hoffmann, S.: Constrained synchronization and subset synchronization problems for weakly acyclic automata. In: Moreira, N., Reis, R. (eds.) Developments in Language Theory - 25th International Conference, DLT 2021, Porto, Portugal, August 16-20, 2021, Proceedings. vol. 12811 of Lecture Notes in Computer Science, pp. 204–216. Cham: Springer (2021). Available from: https://doi.org/10.1007/978-3-030-81508-0_17
Hoffmann, S.: Subset Mapping Problems in Solvable Automata. J. Autom. Lang. Comb. 29(2-4), 199–236 (2024). https://doi.org/10.25596/JALC-2024-199
Immerman, N.: Descriptive complexity. Graduate Texts in Computer Science. Springer (1999)
Mehlhorn, K.: Pebbling mountain ranges and its application of DCFL-recognition. In: de Bakker, J.W., van Leeuwen, J. (eds.) Automata, Languages and Programming, 7th Colloquium, Noordweijkerhout, The Netherlands, July 14-18, 1980, Proceedings. vol. 85 of Lecture Notes in Computer Science, pp. 422–435. Berlin, Heidelberg: Springer (1980). Available from:https://doi.org/10.1007/3-540-10003-2_89
Friedman, E.P.: The inclusion problem for simple languages. Theoret. Comput. Sci. 1(4), 297–316 (1976). https://doi.org/10.1016/0304-3975(76)90074-8
Alur, R., Madhusudan, P.: Visibly pushdown languages. In: Babai, L. (ed.) Proceedings of the 36th Annual ACM Symposium on Theory of Computing, June 13-16, 2004, pp. 202–211. Chicago, IL, USA: ACM (2004). Available from: https://doi.org/10.1145/1007352.1007390
Okhotin, A., Salomaa, K.: Complexity of input-driven pushdown automata. SIGACT News. 45(2), 47–67 (2014). https://doi.org/10.1145/2636805.2636821
Holzer, M., Jakobi, S.: On the computational complexity of problems related to distinguishability sets. Inf. Comput. 259(2), 225–236 (2018). https://doi.org/10.1016/j.ic.2017.09.003
Ginsburg, S., Spanier, E.H.: Semigroups, Presburger formulas, and languages. Pac. J. Math. 16(2), 285–296 (1966). https://doi.org/pjm/1102994974
Haase, C.: A survival guide to Presburger arithmetic. ACM SIGLOG News. 5(3), 67–82 (2018). https://doi.org/10.1145/3242953.3242964
Acknowledgements
I thank all referees for pointing to unclear formulations or making numerous comments that helped in simplifying proofs. The notion of language-synchronization was pointed out to me by a referee of the conference version [61].
Author information
Authors and Affiliations
Contributions
Stefan Hoffmann did all the research and write-up.
Corresponding author
Ethics declarations
Competing Interests
The authors declare no competing interests.
Additional information
Publisher's Note
Springer Nature remains neutral with regard to jurisdictional claims in published maps and institutional affiliations.
Rights and permissions
Springer Nature or its licensor (e.g. a society or other partner) holds exclusive rights to this article under a publishing agreement with the author(s) or other rightsholder(s); author self-archiving of the accepted manuscript version of this article is solely governed by the terms of such publishing agreement and applicable law.
About this article
Cite this article
Hoffmann, S. Synchronization of Parikh Automata. Theory Comput Syst 70, 46 (2026). https://doi.org/10.1007/s00224-025-10225-y
Accepted:
Published:
Version of record:
DOI: https://doi.org/10.1007/s00224-025-10225-y
Facts Only
* Stefan Hoffmann conducted the research and wrote the paper.
* The research investigates synchronizability for Parikh automata (PAs).
* Parikh automata are automata with counters checked against a semilinear set at the end of computation.
* Synchronization problems for deterministic and complete Parikh automata (DCPAs) on letters are PSPACE-complete.
* For DCPAs on letters over a unary alphabet, synchronization problems are NP-complete.
* For DCPAs on letters over a binary and unary alphabet with fixed dimension and unary encoding, problems are NP-complete and solvable in polynomial time, respectively.
* Deciding $\exists \forall$-$D3$-directability for partially ordered Parikh automata with regular Parikh-inverse images is NP-complete.
* Deciding $D3$-directability for partially ordered nondeterministic complete word automata is in AC$^0$.
* The work includes corrections to a previous conference version regarding semilinear set representation and construction blow-up.
* The research is published in Theory of Computing Systems, volume 70, article 46, dated 2026.
Executive Summary
Synchronizability in Parikh automata (PAs) involves determining if a specific input can drive an automaton into a definite state regardless of its starting point. This research explores various notions of this property, specifically focusing on deterministic and complete Parikh automata (DCPAs). The findings establish that these synchronization problems are generally PSPACE-complete, though complexity varies significantly based on the alphabet size, dimension, and encoding methods used.
The analysis differentiates between various automata types, including partially ordered nondeterministic complete word automata and those with specific semilinear constraint sets. While some problems remain NP-complete, others are shown to be solvable in polynomial time or reside within the AC$^0$ complexity class. These results provide a formal map of the computational boundaries for synchronization in automata that utilize counters and semilinear constraints, refining earlier conference-level findings by correcting errors in construction efficiency and set definitions.
Full Take
This scholarship operates within the rigorous domain of theoretical computer science, specifically automata theory and computational complexity. The methodology relies on reductions to establish complexity classes (PSPACE, NP, AC$^0$), a standard and sound approach in the field. A peer reviewer would likely focus on the specifics of the "double-exponential" to "single-exponential" blow-up correction mentioned in the notes, as the efficiency of these constructions is central to the claimed complexity bounds. The author’s transparency regarding previous errors suggests a high degree of intellectual honesty.
The claims are proportionate to the mathematical evidence provided. By isolating variables—such as alphabet size (unary vs. binary) and encoding (unary)—the research successfully maps the "phase transitions" where a problem shifts from being tractable to intractable. This extends existing knowledge of finite automata synchronization to the more complex realm of Parikh automata, where the addition of counters and semilinear constraints introduces new dimensions of difficulty.
For these findings to matter outside the theoretical lab, one must consider the application of PAs in formal verification and the analysis of infinite-state systems. If the synchronization of such systems is PSPACE-complete, it implies a fundamental limit on the efficiency of tools designed to "reset" or "stabilize" these systems.
Bridge Questions:
1. How does the transition from a unary to a binary alphabet fundamentally change the state-space reachability in Parikh automata?
2. Could the polynomial-time solvability for fixed dimensions be leveraged to create approximation algorithms for higher-dimensional systems?
3. What is the practical impact of the $D3$-directability being in AC$^0$ for the design of partially ordered word automata?
Counterstrike Scan: The content is a standard academic contribution to formal language theory; it does not match any coordinated influence pattern.