Subset Synchronization in Monotonic Automata

• Autorzy: Ryzhikov A. , Shemyakov A.

Identyfikatory

DOI

10.3233/FI-2018-1721

• Konferencja: RuFiDiM Conference, Russian-Finnish Symposium in Discrete Mathematics (5; 16-19.05. 2017; Turku; Finland)
• Języki publikacji: EN

Abstrakty

EN

We study extremal and algorithmic questions of subset and careful synchronization in monotonic automata. We show that several synchronization problems that are hard in general automata can be solved in polynomial time in monotonic automata, even without knowing a linear order of the states preserved by the transitions. We provide asymptotically tight bounds on the maximum length of a shortest word synchronizing a subset of states in a monotonic automaton and a shortest word carefully synchronizing a partial monotonic automaton. We provide a complexity framework for dealing with problems for monotonic weakly acyclic automata over a three-letter alphabet, and use it to prove NP-completeness and inapproximability of problems such as FINITE AUTOMATA INTERSECTION and the problem of computing the rank of a subset of states in this class. We also show that checking whether a monotonic partial automaton over a four-letter alphabet is carefully synchronizing is NP-hard. Finally, we give a simple necessary and sufficient condition when a strongly connected digraph with a selected subset of vertices can be transformed into a deterministic automaton where the corresponding subset of states is synchronizing.

Słowa kluczowe

EN

synchronizing automaton; subset synchronization; careful synchronization; monotonic automaton

• Wydawca: IOS Press
• Czasopismo: Fundamenta Informaticae
• Rocznik: 2018
• Tom: Vol. 162, nr 2/3
• Strony: 205--221
• Opis fizyczny: Bibliogr. 32 poz., rys.

Twórcy

autor

Ryzhikov A.

• LIGM, Université Paris-Est, 77455 Marne-la-Vallée, France
• Laboratoire G-SCOP, Université Grenoble Alpes, 38031 Grenoble, France
• United Institute of Informatics Problems of NASB, 220012 Minsk, Belarus

autor

Shemyakov A.

• Belarusian State University, 220030 Minsk, Belarus

Bibliografia

• [1] Adler RL, Goodwyn LW, Weiss B. Equivalence of topological Markov shifts, Israel Journal of Mathematics, 1977;27(1):49-63.
• [2] Ananichev DS. The Mortality Threshold for Partially Monotonic Automata, DLT 2005. LNCS, vol. 3572 (C. De Felice, A. Restivo, Eds.), Springer, Berlin, Heidelberg, 2005 pp. 112-121. doi:10.1007/11505877_10.
• [3] Ananichev DS, Volkov MV. Synchronizing monotonic automata, Theoretical Computer Science, 2004; 327(3):225-239. doi:10.1016/j.tcs.2004.03.068.
• [4] Béal M, Perrin D. A quadratic algorithm for road coloring, Discrete Applied Mathematics, 2014;169:15-29. URL https://doi.org/10.1016/j.dam.2013.12.002.
• [5] Bell J, Stevens B. A survey of known results and research areas for N-queens, Discrete Mathematics, 2009;309(1):1-31. URL https://doi.org/10.1016/j.disc.2007.12.043.
• [6] Blondin M, Krebs A, McKenzie P. The complexity of intersecting finite automata having few final states, computational complexity, 2016;25(4):775-814. doi:10.1007/s00037-014-0089-9.
• [7] de Bondt M, Don H, Zantema H. DFAs and PFAs with Long Shortest Synchronizing Word Length, DLT 2017, LNCS vol. 10396 (É. Charlier, J. Leroy, M. Rigo, Eds.), Springer International Publishing, Cham, 2017. doi:10.1007/978-3-319-62809-7_8.
• [8] Cormen TH, Leiserson CE, Rivest RL, Stein C. Introduction to Algorithms, 3rd edition, MIT Press, 2009.
• [9] Eppstein D. Reset Sequences for Monotonic Automata, SIAM J. Comput, 1990;19(3):500-510. URL https://doi.org/10.1137/0219033.
• [10] Fernau H, Krebs A. Problems on Finite Automata and the Exponential Time Hypothesis, CIAA 2016, LNCS vol. 9705 (Y.-S. Han, K. Salomaa, Eds.), Springer International Publishing, Cham, 2016. doi:10.1007/978-3-319-40946-7_8.
• [11] Friedman, J.: On the road coloring problem, Proceedings of the American Mathematical Society, 110, 1990, 1133-1135.
• [12] Gawrychowski P, Straszak D. Strong Inapproximability of the Shortest Reset Word, MFCS 2015. LNCS, vol. 9234 (F. G. Italiano, G. Pighizzini, T. D. Sannella, Eds.), Springer, Heidelberg, 2015. doi:10.1007/978-3-662-48057-1_19.
• [13] Håstad J. Some Optimal Inapproximability Results, Journal of the ACM, 2001;48(4):798-859. doi:10.1145/502090.502098.
• [14] Holzer M, Kutrib M. Descriptional and computational complexity of finite automata - A survey, Information and Computation, 2011;209(3):456-470, ISSN 0890-5401.
• [15] Kopczyński E. Half-Positional Determinacy of Infinite Games, ICALP 2006. LNCS, vol. 4052 (M. Bugliesi, B. Preneel, V. Sassone, I. Wegener, Eds.), Springer, Berlin, Heidelberg, 2006. doi:10.1007/11787006_29.
• [16] Kopczyński E. Half-Positional Determinacy of Infinite Games, Ph.D. Thesis, Warsaw University, Poland, 2008.
• [17] Kozen D. Lower Bounds for Natural Proof Systems, in: Proceedings of the 18th Annual Symposium on Foundations of Computer Science, IEEE Computer Society, 1977, pp. 254-266.
• [18] Martyugin PV. Complexity of Problems Concerning Carefully Synchronizing Words for PFA and Directing Words for NFA, CSR 2010. LNCS, vol. 6072 (F. Ablayev, E. W. Mayr, Eds.), Springer, Heidelberg, 2010. doi:10.1007/978-3-642-13182-0_27.
• [19] Martyugin PV. A lower bound for the length of the shortest carefully synchronizing words, Russian Mathematics, 2010;54(1):46-54. doi:10.3103/S1066369X10010056.
• [20] Pin J. On two combinatorial problems arising from automata theory, Annals of Discrete Mathematics, 1983;17:535-548.
• [21] Rystsov IK. Asymptotic estimate of the length of a diagnostic word for a finite automaton, Cybernetics, 1980;16(2):194-198, ISSN:1573-8337.
• [22] Ryzhikov A. Synchronization Problems in Automata Without Non-trivial Cycles, CIAA 2017, LNCS, vol. 10329 (A. Carayol, C. Nicaud, Eds.), Springer, Cham, 2017. doi:10.1007/978-3-319-60134-2_16.
• [23] Ryzhikov A, Shemyakov A. Subset Synchronization in Monotonic Automata, Proceedings of the Fourth Russian Finnish Symposium on Discrete Mathematics, TUCS Lecture Notes 26 (J. Karhumäki, A. Saarela, Eds.), 2017. URL https://doi.org/10.1142/S0129054116500167.
• [24] Shcherbak T. The Interval Rank of Monotonic Automata, CIAA 2005. LNCS, vol. 3845 (J. Farré, I. Litovsky, S. Schmitz, Eds.), Springer, Berlin, Heidelberg, 2006. doi:10.1007/11605157_23.
• [25] Sipser M. Introduction to the Theory of Computation, 3rd edition, Cengage Learning, 2012. ISBN-10:113318779X.
• [26] Szykuła M. Checking Whether an Automaton Is Monotonic Is NP-complete, CIAA 2015. LNCS, vol. 9223 (F. Drewes, Ed.), Springer, Cham, 2015. doi:10.1007/978-3-319-22360-5_23.
• [27] Szykuła M. Improving the Upper Bound on the Length of the Shortest Reset Word, 35th Symposium on Theoretical Aspects of Computer Science (STACS 2018) (R. Niedermeier, B. Vallée, Eds.), 96, Schloss Dagstuhl-Leibniz-Zentrum fuer Informatik, Dagstuhl, Germany, 2018. URL: http://drops.dagstuhl.de/opus/volltexte/2018/8516/.
• [28] Trahtman AN. The road coloring problem, Israel Journal of Mathematics, 2009;172(1):51-60. doi:10.1007/s11856-009-0062-5.
• [29] Türker UC, Yenigün H. Complexities of Some Problems Related to Synchronizing, Non-Synchronizing and Monotonic Automata, International Journal of Foundations of Computer Science, 2015;26(01):99-121. doi:10.1142/S0129054115500057.
• [30] Volkov MV. Synchronizing Automata and the Černý Conjecture, LATA 2008. LNCS, vol. 5196 (C.Martín-Vide, F. Otto, H. Fernau, Eds.), Springer, Heidelberg, 2008. doi:10.1007/978-3-540-88282-4_4.
• [31] Vorel V. Subset Synchronization and Careful Synchronization of Binary Finite Automata, International Journal of Foundations of Computer Science, 2016;27(5):557-578. URL https://doi.org/10.1142/S0129054116500167.
• [32] Wehar M. Hardness Results for Intersection Non-Emptiness, Automata, Languages, and Programming: 41st International Colloquium, ICALP 2014, Copenhagen, Denmark, July 8-11, 2014, Proceedings, Part II (J. Esparza, P. Fraigniaud, T. Husfeldt, E. Koutsoupias, Eds.), Springer Berlin Heidelberg, Berlin, Heidelberg, 2014. doi:10.1007/978-3-662-43951-7_30.