Synchronization of finite automata

M. V. Volkov

Trudy Matematicheskogo Instituta imeni V.A. Steklova, Tome 77 (2022) no. 5, pp. 819-891

Résumé

A survey of the state-of-the-art of the theory of synchronizing automata is given in its part concerned with the case of complete deterministic automata. Algorithmic and complexity-theoretic aspects are considered, the existing results related to Černý's conjecture and methods for their derivation are presented. Bibliography: 193 titles.

Détail

Keywords: finite automaton, synchronizability, algorithm, computational complexity, reset threshold
Mots-clés : Černý's conjecture.

Bibliographie

[1] R. L. Adler, L. W. Goodwyn, and B. Weiss, “Equivalence of topological Markov shifts”, Israel J. Math., 27:1 (1977), 49–63 | DOI | MR | Zbl

[2] P. Ageev, “Implementation of the algorithm for testing an automaton for synchronization in linear expected time”, J. Autom. Lang. Comb., 24:2-4 (2019), 139–152 | DOI | MR | Zbl

[3] J. Almeida, S. Margolis, B. Steinberg, and M. Volkov, “Representation theory of finite semigroups, semigroup radicals and formal language theory”, Trans. Amer. Math. Soc., 361:3 (2009), 1429–1461 | DOI | MR | Zbl

[4] J. Almeida and E. Rodaro, “Semisimple synchronizing automata and the Wedderburn–Artin theory”, Internat. J. Found. Comput. Sci., 27:2 (2016), 127–145 | DOI | MR | Zbl

[5] J. Almeida and B. Steinberg, “Matrix mortality and the Černý–Pin conjecture”, Developments in language theory, Lecture Notes in Comput. Sci., 5583, Springer, Berlin, 2009, 67–80 | DOI | MR | Zbl

[6] J. Almeida and M. V. Volkov, “Profinite identities for finite semigroups whose subgroups belong to a given pseudovariety”, J. Algebra Appl., 2:2 (2003), 137–163 | DOI | MR | Zbl

[7] D. S. Ananichev, “The annulation threshold for partially monotonic automata”, Izv. Vysh. Uchebn. Zaved. Mat., 2010, no. 1, 3–13 ; English transl. in Russian Math. (Iz. VUZ), 54:1 (2010), 1–9 | MR | Zbl | DOI

[8] D. S. Ananichev and V. V. Gusev, “Approximation of reset thresholds with greedy algorithms”, Fund. Inform., 145:3 (2016), 221–227 | DOI | MR | Zbl

[9] D. S. Ananichev, I. V. Petrov, and M. V. Volkov, “Collapsing words: a progress report”, Internat. J. Found. Comput. Sci., 17:3 (2006), 507–518 | DOI | MR | Zbl

[10] D. S. Ananichev and M. V. Volkov, “Some results on Černý type problems for transformation semigroups”, Semigroups and languages, World Sci. Publ., River Edge, NJ, 2004, 23–42 | DOI | MR | Zbl

[11] D. S. Ananichev and M. V. Volkov, “Synchronizing monotonic automata”, Theoret. Comput. Sci., 327:3 (2004), 225–239 | DOI | MR | Zbl

[12] D. S. Ananichev and M. V. Volkov, “Synchronizing generalized monotonic automata”, Theoret. Comput. Sci., 330:1 (2005), 3–13 | DOI | MR | Zbl

[13] D. S. Ananichev, M. V. Volkov, and V. V. Gusev, “Primitive digraphs with large exponents and slowly synchronizing automata”, Combinatorics and graph theory. IV, Zap. Nauchn. Semin. S.-Peterburg. Otdel. Mat. Inst. Steklov. (POMI), 402, St. Petersburg Department of Steklov Mathematoical Institute, St. Petersburg, 2012, 9–39 ; English transl. in J. Math. Sci. (N. Y.), 192:3 (2013), 263–278 | MR | Zbl | DOI

[14] D. Ananichev and V. Vorel, “A new lower bound for reset threshold of binary synchronizing automata with sink”, J. Autom. Lang. Comb., 24:2-4 (2019), 153–164 | DOI | MR | Zbl

[15] J. Araújo, P. Cameron, and B. Steinberg, “Between primitive and 2-transitive: synchronization and its friends”, EMS Surv. Math. Sci., 4:2 (2017), 101–184 | DOI | MR | Zbl

[16] F. Arnold and B. Steinberg, “Synchronizing groups and automata”, Theoret. Comput. Sci., 359:1-3 (2006), 101–110 | DOI | MR | Zbl

[17] W. R. Ashby, An introduction to cybernetics, Chapman and Hall, Ltd., London, 1956, ix+295 pp. | MR | Zbl

[18] M.-P. Béal, M. V. Berlinkov, and D. Perrin, “A quadratic upper bound on the size of a synchronizing word in one-cluster automata”, Internat. J. Found. Comput. Sci., 22:2 (2011), 277–288 | DOI | MR | Zbl

[19] M.-P. Béal and D. Perrin, “A quadratic upper bound on the size of a synchronizing word in one-cluster automata”, Developments in language theory, Lecture Notes in Comput. Sci., 5583, Springer, Berlin, 2009, 81–90 | DOI | MR | Zbl

[20] Y. Benenson, R. Adar, T. Paz-Elizur, Z. Livneh, and E. Shapiro, “DNA molecule provides a computing machine with both data and fuel”, Proc. Natl. Acad. Sci. USA, 100:5 (2003), 2191–2196 | DOI

[21] Y. Benenson, T. Paz-Elizur, R. Adar, E. Keinan, Z. Livneh, and E. Shapiro, “Programmable and autonomous computing machine made of biomolecules”, Nature, 414:6862 (2001), 430–434 | DOI

[22] M. V. Berlinkov, “On a conjecture by Carpi and D'{A}lessandro”, Internat. J. Found. Comput. Sci., 22:7 (2011), 1565–1576 | DOI | MR | Zbl

[23] M. V. Berlinkov, “Synchronizing quasi-{E}ulerian and quasi-one-cluster automata”, Internat. J. Found. Comput. Sci., 24:6 (2013), 729–745 | DOI | MR | Zbl

[24] M. V. Berlinkov, “Approximating the minimum length of synchronizing words is hard”, Theory Comput. Syst., 54:2 (2014), 211–223 | DOI | MR | Zbl

[25] M. V. Berlinkov, “On two algorithmic problems about synchronizing automata”, Developments in language theory, Lecture Notes in Comput. Sci., 8633, Springer, Cham, 2014, 61–67 | DOI | MR | Zbl

[26] M. V. Berlinkov, “On the probability of being synchronizable”, Algorithms and discrete applied mathematics, Lecture Notes in Comput. Sci., 9602, Springer, Cham, 2016, 73–84 | DOI | MR | Zbl

[27] M. V. Berlinkov, R. Ferens, and M. Szykuła, “Preimage problems for deterministic finite automata”, J. Comput. System Sci., 115 (2021), 214–234 | DOI | MR | Zbl

[28] M. V. Berlinkov and M. Szykuła, “Algebraic synchronization criterion and computing reset words”, Inform. Sci., 369 (2016), 718–730 | DOI | Zbl

[29] J. Berstel, D. Perrin, and C. Reutenauer, Codes and automata, Encyclopedia Math. Appl., 129, Cambridge Univ. Press, Cambridge, 2010, xiv+619 pp. | DOI | MR | Zbl

[30] M. T. Biskup, Error resilience in compressed data – selected topics, Ph.D. thesis, Inst. of Informatics, Univ. of Warsaw, 2008, 136 pp., pp. http://www.mimuw.edu.pl/sites/default/files/marek_biskup_mb-praca.pdf

[31] M. T. Biskup, “Guaranteed synchronization of Huffman codes”, Data compression conference (DCC 2008) (Snowbird, UT 2008), IEEE, 2008, 462–471 | DOI

[32] M. T. Biskup and W. Plandowski, “Guaranteed synchronization of Huffman codes with known position of decoder”, Data compression conference (DCC 2009) (Snowbird, UT 2009), IEEE, 2009, 33–42 | DOI

[33] M. T. Biskup and W. Plandowski, “Shortest synchronizing strings for Huffman codes”, Theoret. Comput. Sci., 410:38-40 (2009), 3925–3941 | DOI | MR | Zbl

[34] S. Bogdanović, B. Imreh, M. Ćirić, and T. Petković, “Directable automata and their generalizations: a survey”, Novi Sad J. Math., 29:2 (1999), 29–69 | MR | Zbl

[35] P. Bonizzoni and N. Jonoska, “Existence of constants in regular splicing languages”, Inform. and Comput., 242 (2015), 340–353 | DOI | MR | Zbl

[36] V. Boppana, S. P. Rajan, K. Takayama, and M. Fujita, “Model checking based on sequential ATPG”, Computer aided verification, Lecture Notes in Comput. Sci., 1633, Springer-Verlag, Berlin, 1999, 418–430 | DOI | MR | Zbl

[37] R. A. Brualdi and H. J. Ryser, Combinatorial matrix theory, Encyclopedia Math. Appl., 39, Cambridge Univ. Press, Cambridge, 1991, x+367 pp. | DOI | MR | Zbl

[38] P. J. Cameron, “Dixon's theorem and random synchronization”, Discrete Math., 313:11 (2013), 1233–1236 | DOI | MR | Zbl

[39] R. M. Capocelli, L. Gargano, and U. Vaccaro, “On the characterization of statistically synchronizable variable-length codes”, IEEE Trans. Inform. Theory, 34:4 (1988), 817–825 | DOI | MR | Zbl

[40] A. Carpi and F. D'Alessandro, “Strongly transitive automata and the Černý conjecture”, Acta Inform., 46:8 (2009), 591–607 | DOI | MR | Zbl

[41] A. Carpi and F. D'Alessandro, “The synchronization problem for locally strongly transitive automata”, Mathematical foundations of computer science 2009, Lecture Notes in Comput. Sci., 5734, Springer, Berlin, 2009, 211–222 | DOI | MR | Zbl

[42] A. Carpi and F. D'Alessandro, “Independent sets of words and the synchronization problem”, Adv. in Appl. Math., 50:3 (2013), 339–355 | DOI | MR | Zbl

[43] A. Carpi and F. D'Alessandro, “Locally strongly transitive automata in the Černý conjecture and related problems”, J. Autom. Lang. Comb., 24:2-4 (2019), 165–184 | DOI | MR | Zbl

[44] J. Černý, “Poznámka k homogénnym eksperimentom s konečnými automatami”, Mat.-Fyz. Časopis Sloven. Akad. Vied., 14:3 (1964), 208–216 ; English transl. J. Černý, “A note on homogeneous experiments with finite automata”, J. Autom. Lang. Comb., 24:2-4 (2019), 123–132 | MR | Zbl | DOI | MR | Zbl

[45] J. Černý, A. Pirická, and B. Rosenauerová, “On directable automata”, Kybernetika (Prague), 7:4 (1971), 289–298 | MR | Zbl

[46] Y.-B. Chen and D. J. Ierardi, “The complexity of oblivious plans for orienting and distinguishing polygonal parts”, Algorithmica, 14:5 (1995), 367–397 | DOI | MR | Zbl

[47] A. Cherubini, “Synchronizing and collapsing words”, Milan J. Math., 75:1 (2007), 305–321 | DOI | MR

[48] A. Cherubini, A. Frigeri, and Z. Liu, “Composing short 3-compressing words on a 2-letter alphabet”, Discrete Math. Theor. Comput. Sci., 19:1 (2017), 17, 35 pp. | DOI | MR | Zbl

[49] A. Cherubini and A. Kisielewicz, “Collapsing words, permutation conditions and coherent colorings of trees”, Theoret. Comput. Sci., 410:21-23 (2009), 2135–2147 | DOI | MR | Zbl

[50] A. Cherubini and A. Kisielewicz, “Recognizing 3-collapsing words over a binary alphabet”, Theoret. Comput. Sci., 629 (2016), 64–79 | DOI | MR | Zbl

[51] A. Cherubini, A. Kisielewicz, and B. Piochi, “On the length of shortest 2-collapsing words”, Discrete Math. Theor. Comput. Sci., 11:1 (2009), 33–44 | DOI | MR | Zbl

[52] K. Chmiel and A. Roman, “COMPAS – a computing package for synchronization”, Implementation and application of automata, Lecture Notes in Comput. Sci., 6482, Springer, Berlin, 2011, 79–86 | DOI | MR | Zbl

[53] Hyunwoo Cho, S.-W. Jeong, F. Somenzi, and C. Pixley, “Multiple observation time single reference test generation using synchronizing sequences”, 1993 European conference on design automation with the European event in ASIC design (Paris 1993), IEEE, 1993, 494–498 | DOI

[54] Hyunwoo Cho, S.-W. Jeong, F. Somenzi, and C. Pixley, “Synchronizing sequences and symbolic traversal techniques in test generation”, J. Electronic Testing, 4 (1993), 19–31 | DOI

[55] Th. H. Cormen, Ch. E. Leiserson, R. L. Rivest, and C. Stein, Introduction to algorithms, 3rd ed., MIT Press, Cambridge, MA, 2009, xx+1292 pp. | MR | Zbl

[56] Z. H. Cui, Y. He, and S. Y. Sun, “Synchronizing bounded partially ordered automata”, (Chinese), Chinese J. Comput., 42:3 (2019), 610–623 | MR

[57] M. de Bondt, A short proof of a theorem of J.-E. Pin, 2018, 12 pp., arXiv: 1811.11660

[58] M. de Bondt, H. Don, and H. Zantema, “DFAs and PFAs with long shortest synchronizing word length”, Developments in language theory, Lecture Notes in Comput. Sci., 10396, Springer, Cham, 2017, 122–133 | DOI | MR | Zbl

[59] F. M. Dekking, “The spectrum of dynamical systems arising from substitutions of constant length”, Z. Wahrscheinlichkeitstheorie und Verw. Gebiete, 41:3 (1978), 221–239 | DOI | MR | Zbl

[60] H. Don and H. Zantema, “Finding DFAs with maximal shortest synchronizing word length”, Language and automata theory and applications, Lecture Notes in Comput. Sci., 10168, Springer, Cham, 2017, 249–260 | DOI | MR | Zbl

[61] H. Don and H. Zantema, “Counting symbol switches in synchronizing automata”, J. Autom. Lang. Comb., 24:2-4 (2019), 253–286 | DOI | MR | Zbl

[62] L. Dubuc, “Sur les automates circulaires et la conjecture de Černý”, RAIRO Inform. Théor. Appl., 32:1-3 (1998), 21–34 | DOI | MR

[63] M. Dżyga, R. Ferens, V. V. Gusev, and M. Szykuła, “Attainable values of reset thresholds”, 42nd international symposium on mathematical foundations of computer science, LIPIcs. Leibniz Int. Proc. Inform., 83, Schloss Dagstuhl. Leibniz-Zent. Inform., Wadern, 2017, 40, 14 pp. | DOI | MR | Zbl

[64] D. Eppstein, “Reset sequences for monotonic automata”, SIAM J. Comput., 19:3 (1990), 500–510 | DOI | MR | Zbl

[65] D. Eppstein and J.-C. Falmagne, “Algorithms for media”, Discrete Appl. Math., 156:8 (2008), 1308–1320 | DOI | MR | Zbl

[66] H. Fernau, V. V. Gusev, S. Hoffmann, M. Holzer, M. V. Volkov, and P. Wolf, “Computational complexity of synchronization under regular constraints”, 44th international symposium on mathematical foundations of computer science, LIPIcs. Leibniz Int. Proc. Inform., 138, Schloss Dagstuhl. Leibniz-Zent. Inform., Wadern, 2019, 63, 14 pp. | DOI | MR | Zbl

[67] H. Fernau, P. Heggernes, and Y. Villanger, “A multi-parameter analysis of hard problems on deterministic finite automata”, J. Comput. System Sci., 81:4 (2015), 747–765 | DOI | MR | Zbl

[68] H. Fernau and A. Krebs, “Problems on finite automata and the exponential time hypothesis”, Algorithms (Basel), 10:1 (2017), 24, 25 pp. | DOI | MR | Zbl

[69] M. A. Fischler and M. Tannenbaum, “Synchronizing and representation problems for sequential machines with masked outputs”, 11th annual symposium on switching and automata theory (SWAT 1970), IEEE, 1970, 97–103 | DOI

[70] P. Frankl, “An extremal problem for two families of sets”, European J. Combin., 3:2 (1982), 125–127 | DOI | MR | Zbl

[71] D. Frettlöh and B. Sing, “Computing modular coincidences for substitution tilings and point sets”, Discrete Comput. Geom., 37:3 (2007), 381–407 | DOI | MR | Zbl

[72] A. Frigeri and E. Rodaro, “Missing factors of ideals and synchronizing automata”, J. Autom. Lang. Comb., 24:2-4 (2019), 309–320 | DOI | MR | Zbl

[73] P. Gawrychowski, Complexity of shortest synchronizing word, preprint, 2008

[74] P. Gawrychowski and D. Straszak, “Strong inapproximability of the shortest reset word”, Mathematical foundations of computer science 2015, Part I, Lecture Notes in Comput. Sci., 9234, Springer, Heidelberg, 2015, 243–255 | DOI | MR | Zbl

[75] M. Gerbush and B. Heeringa, “Approximating minimum reset sequences”, Implementation and application of automata, Lecture Notes in Comput. Sci., 6482, Springer, Berlin, 2011, 154–162 | DOI | MR | Zbl

[76] A. Gill, “State-identification experiments in finite automata”, Information and Control, 4:2-3 (1961), 132–154 | DOI | DOI | MR

[77] S. Ginsburg, “On the length of the smallest uniform experiment which distinguishes the terminal states of a machine”, J. Assoc. Comput. Mach., 5:3 (1958), 266–280 | DOI | MR | Zbl

[78] S. Ginsburg, An introduction to mathematical machine theory, Addison-Wesley Publishing Co., Inc., Reading, MA–Palo Alto, CA–London, 1962, ix+147 pp. | MR | Zbl

[79] K. Y. Goldberg, “Orienting polygonal parts without sensors”, Algorithmica, 10:2-4 (1993), 201–225 | DOI | MR | Zbl

[80] F. Gonze, V. V. Gusev, R. M. Jungers, B. Gerencsér, and M. V. Volkov, “On the interplay between Černý and {B}abai's conjectures”, Internat. J. Found. Comput. Sci., 30:1 (2019), 93–114 | DOI | MR | Zbl

[81] F. Gonze, R. M. Jungers, and A. N. Trahtman, “A note on a recent attempt to improve the Pin–Frankl bound”, Discrete Math. Theor. Comput. Sci., 17:1 (2015), 307–308 | DOI | MR | Zbl

[82] P. Goralčík and V. Koubek, “Rank problems for composite transformations”, Internat. J. Algebra Comput., 5:3 (1995), 309–316 | DOI | MR | Zbl

[83] R. L. Graham, D. E. Knuth, and O. Patashnik, Concrete mathematics. A foundation for computer science, 2nd ed., Addison-Wesley Publ. Co., Reading, MA, 2006, xiv+657 pp. | MR | Zbl

[84] M. Grech and A. Kisielewicz, “The Černý conjecture for automata respecting intervals of a directed graph”, Discrete Math. Theor. Comput. Sci., 15:3 (2013), 61–72 | DOI | MR | Zbl

[85] M. Grech and A. Kisielewicz, “Synchronizing sequences for road colored digraphs”, Discrete Appl. Math., 285 (2020), 128–140 | DOI | MR | Zbl

[86] V. V. Gusev, “Lower bounds for the length of reset words in Eulerian automata”, Reachability problems, Lecture Notes in Comput. Sci., 6945, Springer, Berlin, 2011, 180–190 | DOI | Zbl

[87] V. V. Gusev, R. M. Jungers, and D. Průša, “Dynamics of the independence number and automata synchronization”, Developments in language theory, Lecture Notes in Comput. Sci., 11088, Springer, Cham, 2018, 379–391 | DOI | MR | Zbl

[88] V. V. Gusev, M. I. Maslennikova, and E. V. Pribavkina, “Principal ideal languages and synchronizing automata”, Fund. Inform., 132:1 (2014), 95–108 | DOI | MR | Zbl

[89] V. V. Gusev and E. V. Pribavkina, “On codeword lengths guaranteeing synchronization”, Combinatorics on words, Lecture Notes in Comput. Sci., 11682, Springer, Cham, 2019, 207–216 | DOI | MR | Zbl

[90] J. Håstad, “Clique is hard to approximate within $n^{1-\varepsilon}$ ”, Acta Math., 182:1 (1999), 105–142 | DOI | MR | Zbl

[91] S. Hoffmann, “On a class of constrained synchronization problems in NP”, Proceedings of the 21st Italian conference on theoretical computer science (Ischia 2020), CEUR Workshop Proceedings, 2756, 2020, 145–157 http://ceur-ws.org/Vol-2756/

[92] S. Hoffmann, “Completely reachable automata, primitive groups and the state complexity of the set of synchronizing words”, Language and automata theory and applications, Lecture Notes in Comput. Sci., 12638, Springer, Cham, 2021, 305–317 | DOI | MR | Zbl

[93] S. Hoffmann, “State complexity of the set of synchronizing words for circular automata and automata over binary alphabets”, Language and automata theory and applications, Lecture Notes in Comput. Sci., 12638, Springer, Cham, 2021, 318–330 | DOI | MR | Zbl

[94] S. Hoffmann, “Constrained synchronization and subset synchronization problems for weakly acyclic automata”, Developments in language theory, Lecture Notes in Comput. Sci., 12811, Springer, Cham, 2021, 204–216 | DOI | MR | Zbl

[95] S. Hoffmann, “Computational complexity of synchronization under sparse regular constraints”, Fundamentals of computation theory, Lecture Notes in Comput. Sci., 12867, Springer, Cham, 2021, 272–286 | DOI | MR | Zbl

[96] S. Hoffmann, “Ideal separation and general theorems for constrained synchronization and their application to small constraint automata”, Computing and combinatorics, Lecture Notes in Comput. Sci., 13025, Springer, Cham, 2021, 176–188 | DOI | MR | Zbl

[97] S. Hoffmann, “Constrained synchronization and commutativity”, Theoret. Comput. Sci., 890 (2021), 147–170 | DOI | MR | Zbl

[98] H. J{ü}rgensen, “Synchronization”, Inform. and Comput., 206:9-10 (2008), 1033–1044 | DOI | MR | Zbl

[99] J. Kari, “A counter example to a conjecture concerning synchronizing words in finite automata”, Bull. Eur. Assoc. Theor. Comput. Sci., 73 (2001), 146 | MR | Zbl

[100] J. Kari, “Synchronizing finite automata on {E}ulerian digraphs”, Theoret. Comput. Sci., 295:1-3 (2003), 223–232 | DOI | MR | Zbl

[101] J. Kari and M. Volkov, “Černý's conjecture and the road colouring problem”, Handbook of automata theory, Ch. 15, v. I, Theoretical foundations, EMS Press, Berlin, 2021, 525–565 | DOI | MR | Zbl

[102] A. Kisielewicz, J. Kowalski, and M. Szykuła, “Computing the shortest reset words of synchronizing automata”, J. Comb. Optim., 29:1 (2015), 88–124 | DOI | MR | Zbl

[103] A. Kisielewicz, J. Kowalski, and M. Szykuła, “Experiments with synchronizing automata”, Implementation and application of automata, Lecture Notes in Comput. Sci., 9705, Springer, Cham, 2016, 176–188 | DOI | MR | Zbl

[104] A. Kisielewicz and M. Szykuła, “Generating small automata and the Černý conjecture”, Implementation and application of automata, Lecture Notes in Comput. Sci., 7982, Springer, Heidelberg, 2013, 340–348 | DOI | MR | Zbl

[105] A. Kisielewicz and M. Szykuła, “Synchronizing automata with extremal properties”, Mathematical foundations of computer science 2015, Part 1, Lecture Notes in Comput. Sci., 9234, Springer, Heidelberg, 2015, 331–343 | DOI | MR | Zbl

[106] S. C. Kleene, “Representation of events in nerve nets and finite automata”, Automata studies, Ann. of Math. Stud., 34, Princeton Univ. Press, Princeton, NJ, 1956, 3–41 | DOI | MR | Zbl

[107] A. A. Klyachko, I. K. Rystsov, and M. A. Spivak, “An extremal combinatorial problem associated with the bound of the length of a synchronizing word in an automaton”, Kibernetika, 25:2 (1987), 16–20 ; English transl. in Cybernetics, 23:2 (1987), 165–171 | MR | Zbl | DOI

[108] Z. Kohavi and J. Winograd, “Bounds on the length of synchronizing sequences and the order of information losslessness”, Theory of machines and computations, Academic Press, New York, 1971, 197–206 | DOI | MR | Zbl

[109] Z. Kohavi and J. Winograd, “Establishing certain bounds concerning finite automata”, J. Comput. System Sci., 7:3 (1973), 288–299 | DOI | MR | Zbl

[110] D. Kozen, “Lower bounds for natural proof systems”, 18th annual symposium on foundations of computer science (Providence, RI 1977), IEEE Comput. Sci., Long Beach, CA, 1977, 254–266 | DOI | MR | Zbl

[111] M. W. Krentel, “The complexity of optimization problems”, J. Comput. System Sci., 36:3 (1988), 490–509 | DOI | MR | Zbl

[112] A. E. Laemmel, A general class of discrete codes and certain of their properties, Res. rep. R-459-55, PIB-389, Microwave Research Inst., Polytechnic Inst., Brooklyn, NY, 1956

[113] A. E. Laemmel, Study on application of coding theory, Tech. rep. PIBMRI-895.5-63, Dept. Electrophysics, Microwave Research Inst., Polytechnic Inst., Brooklyn, NY, 1963

[114] A. E. Laemmel and B. Rudner, Study of the application of coding theory, Tech. rep. PIBEP-69-034, Dept. Electrophysics, Polytechnic Inst., Brooklyn, Farmingdale, NY, 1969

[115] V. I. Levenshteĭn, “Self-adaptive automata for decoding messages”, Dokl. Akad. Nauk SSSR, 141:6 (1961), 1320–1323 ; English transl. in Soviet Physics Dokl., 6 (1961), 1042–1045 | MR | Zbl

[116] C. L. Liu, “Determination of the final state of an automaton whose initial state is unknown”, IEEE Trans. Electronic Computers, EC-12:6 (1963), 918–920 | DOI

[117] C. L. Liu, Some memory aspects of finite automata, Tech. rep. 411, Research Lab. Electronics, Massachusetts Inst., MIT Res. Lab. Electronics, Cambridge, MA, 1963, 71 pp. http://hdl.handle.net/1721.1/4414

[118] P. V. Martugin, “A series of slowly synchronizing automata with a zero state over a small alphabet”, Inform. and Comput., 206:9-10 (2008), 1197–1203 | DOI | MR | Zbl

[119] M. Maslennikova, “Reset complexity of ideal languages over a binary alphabet”, Internat. J. Found. Comput. Sci., 30:6-7 (2019), 1177–1196 | DOI | MR | Zbl

[120] M. Maslennikova and E. Rodaro, “Representation of (left) ideal regular languages by synchronizing automata”, Computer science – theory and applications, Lecture Notes in Comput. Sci., 9139, Springer, Cham, 2015, 325–338 | DOI | MR | Zbl

[121] M. Maslennikova and E. Rodaro, “Trim strongly connected synchronizing automata and ideal languages”, Fund. Inform., 162:2-3 (2018), 183–203 | DOI | MR | Zbl

[122] A. Mateescu and A. Salomaa, “Many-valued truth functions, Černý's conjecture, and road coloring”, Current trends in theoretical computer science. Entering the 21th century, World Sci. Publ., River Edge, NJ, 2001, 693–707 | DOI | MR | Zbl

[123] Yu. T. Medvedev, “On the class of events representable in a finite automaton”, Automata, Inostrannaya Literatura, Moscow, 1956, 385–401; English transl. in Sequential machines — Selected papers, ed. E.F. Moore, Addison Wesley, Boston, MA, 1964

[124] E. F. Moore, “Gedanken-experiments on sequential machines”, Automata studies, Ann. of Math. Stud., 34, Princeton Univ. Press, Princeton, NJ, 1956, 129–153 | DOI | MR | Zbl

[125] E. H. Moore, “On certain crinkly curves”, Trans. Amer. Math. Soc., 1:1 (1900), 72–90 ; “Errata”, Trans. Amer. Math. Soc., 1 (1900), 507 | DOI | MR | Zbl | DOI | MR

[126] B. K. Natarajan, “An algorithmic approach to the automated design of parts orienters”, 27th annual symposium on foundations of computer science (SFCS 1986) (Toronto, ON 1986), IEEE, 1986, 132–142 | DOI

[127] B. K. Natarajan, “Some paradigms for the automated design of parts feeders”, Int. J. Robot. Res., 8:6 (1989), 98–109 | DOI

[128] C. Nicaud, “The Černý conjecture holds with high probability”, J. Autom. Lang. Comb., 24:2-4 (2019), 343–365 | DOI | MR | Zbl

[129] J. Olschewski and M. Ummels, “The complexity of finding reset words in finite automata”, Mathematical foundations of computer science 2010, Lecture Notes in Comput. Sci., 6281, Springer, Berlin, 2010, 568–579 | DOI | MR | Zbl

[130] C. H. Papadimitriou, Computational complexity, Addison-Wesley Publishing Co., Reading, MA, 1994, xvi+523 pp. | MR | Zbl

[131] C. H. Papadimitriou and M. Yannakakis, “The complexity of facets (and some facets of complexity)”, J. Comput. System Sci., 28:2 (1984), 244–259 | DOI | MR | Zbl

[132] J.-E. Pin, Le problème de la synchronisation et la conjecture de Černý, Thèse de 3ème cycle, Univ. Paris VI, 1978

[133] J.-E. Pin, “Sur un cas particulier de la conjecture de Cerny”, Automata, languages and programming (Udine 1978), Lecture Notes in Comput. Sci., 62, Springer, Berlin–New York, 1978, 345–352 | DOI | MR | Zbl

[134] J.-E. Pin, “Utilisation de l'algèbre linéaire en théorie des automates”, Actes du 1er colloque AFCET-SMF de mathématiques appliquées (Palaiseau 1978), AFCET, 1978, 85–92 https://hal.archives-ouvertes.fr/hal-00340773

[135] J. E. Pin, “On two combinatorial problems arising from automata theory”, Combinatorial mathematics (Marseille–Luminy 1981), North-Holland Math. Stud., 75, Ann. Discrete Math., 17, North-Holland, Amsterdam, 1983, 535–548 | DOI | MR | Zbl

[136] C. Pixley, S.-W. Jeong, and G. D. Hachtel, “Exact calculation of synchronizing sequences based on binary decision diagrams”, IEEE Trans. Comput.-Aided Des. Integr. Circuits Syst., 13:8 (1994), 1024–1034 | DOI

[137] R. Pöschel, M. V. Sapir, N. V. Sauer, M. G. Stone, and M. V. Volkov, “Identities in full transformation semigroups”, Algebra Universalis, 31:4 (1994), 580–588 | DOI | MR | Zbl

[138] E. V. Pribavkina, “Slowly synchronizing automata with zero and noncomplete sets”, Mat. Zametki, 90:3 (2011), 422–430 ; English transl. in Math. Notes, 90:3 (2011), 411–417 | DOI | MR | Zbl | DOI

[139] E. V. Pribavkina and E. Rodaro, “Synchronizing automata with finitely many minimal synchronizing words”, Inform. and Comput., 209:3 (2011), 568–579 | DOI | MR | Zbl

[140] N. Pytheas Fogg, Substitutions in dynamics, arithmetics and combinatorics, Lecture Notes in Math., 1794, eds. V. Berthé, S. Ferenczi, C. Mauduit, A. Siegel, Springer-Verlag, Berlin, 2002 | DOI | MR | Zbl

[141] M. O. Rabin and D. Scott, “Finite automata and their decision problems”, IBM J. Res. Develop., 3:2 (1959), 114–125 | DOI | MR | Zbl

[142] J. L. Ramírez Alfonsín, The Diophantine Frobenius problem, Oxford Lecture Ser. Math. Appl., 30, Oxford Univ. Press, Oxford, 2005, xvi+243 pp. | MR | Zbl

[143] A. S. Rao and K. Y. Goldberg, “Manipulating algebraic parts in the plane”, IEEE Trans. Robotics Autom., 11:4 (1995), 598–602 | DOI

[144] R. Reis and E. Rodaro, “Ideal regular languages and strongly connected synchronizing automata”, Theoret. Comput. Sci., 653 (2016), 97–107 | DOI | MR | Zbl

[145] J.-K. Rho, F. Somenzi, and C. Pixley, “Minimum length synchronizing sequences of finite state machine”, 30th ACM/IEEE design automation conference (Dallas, TX 1993), ACM, New York, NY, 1993, 463–468 | DOI

[146] E. Rodaro, “Strongly connected synchronizing automata and the language of minimal reset words”, Adv. in Appl. Math., 99 (2018), 158–173 | DOI | MR | Zbl

[147] E. Rodaro, “A bound for the length of the shortest reset words for semisimple synchronizing automata via the packing number”, J. Algebraic Combin., 50:3 (2019), 237–253 | DOI | MR | Zbl

[148] A. Roman and M. Szykuła, “Forward and backward synchronizing algorithms”, Expert Syst. Appl., 42:24 (2015), 9512–9527 | DOI

[149] I. K. Rystsov, “An estimate of the length of a nuclear word for a finite automaton”, Automata, v. 2, Saratov State University, Saratov, 1977, 43–48 | MR | Zbl

[150] I. K. Rystsov, “Minimization of the length of synchronizing words for finite automata”, Theoretical questions of design of computer systems, Akad. Nauk Ukr.SSR, Cybernetics Institute, Kiev, 1980, 75–82 (Russian) | MR | Zbl

[151] I. K. Rystsov, “Polynomial complete problems in automata theory”, Inform. Process. Lett., 16:3 (1983), 147–151 (Russian) | DOI | MR | Zbl

[152] I. K. Rystsov, “Rank of a finite automaton”, Kibernetika i Sistemnyi Anal., 28:3 (1992), 3–10 ; English transl. in Cybernet. Systems Anal., 28:3 (1992), 323–328 | MR | Zbl | DOI

[153] I. K. Rystsov, “Resetting words for decidable automata”, Kibernetika i Sistemnyi Anal., 30:6 (1994), 21–26 ; English transl, in Cybernet. Systems Anal., 30:6 (1992), 807–811 | MR | Zbl | DOI

[154] I. K. Rystsov, “Almost optimal bound of reccurent word length for regular automata”, Kiberenetika Sistemnyi Anal., 31:5 (1995), 40–48 ; English transl. in Cybernet. Systems Anal., 31:5 (1995), 669–674 | MR | Zbl | DOI

[155] I. K. Rystsov, “Quasioptimal bound for the length of reset words for regular automata”, Acta Cybernet., 12:2 (1995), 145–152 | MR | Zbl

[156] I. Rystsov, “Exact linear bound for the length of reset words in commutative automata”, Publ. Math. Debrecen, 48:3-4, suppl. (1996), 405–409 | MR | Zbl

[157] I. Rystsov, “Reset words for commutative and solvable automata”, Theoret. Comput. Sci., 172:1-2 (1997), 273–279 | DOI | MR | Zbl

[158] I. K. Rystsov, “Estimation of the length of reset words for automata with simple idempotents”, Kibernetika Sistemnyi Anal., 36:3 (2000), 32–39 ; English transl. in Cybernet. Systems Anal., 36:3 (2000), 339–344 | MR | Zbl | DOI

[159] I. K. Rystsov, “Cerny's conjecture for automata with simple idempotents”, Kibernet. Sistem. Anal., 58:1 (2022), 3–10 ; English transl, in Cybernet. Systems Anal., 58:1 (2022), 1–7 | MR | Zbl | DOI

[160] A. Ryzhikov, “Synchronization problems in automata without non-trivial cycles”, Theoret. Comput. Sci., 787 (2019), 77–88 | DOI | MR | Zbl

[161] A. Ryzhikov and M. Szykula, “Finding short synchronizing words for prefix codes”, 43rd international symposium on mathematical foundations of computer science (Liverpool, UK 2018), LIPIcs. Leibniz Int. Proc. Inform., 117, Schloss Dagstuhl. Leibniz-Zent. Inform., Wadern, 2018, 21, 14 pp. | DOI | MR | Zbl

[162] A. Salomaa, “Compositions over a finite domain: from completeness to synchronizable automata”, A half-century of automata theory. Celebration and inspiration (London, ON 2000), World Sci. Publ., River Edge, NJ, 2001, 131–143 | DOI | MR | Zbl

[163] A. Salomaa, “Generation of constants and synchronization of finite automata”, J. UCS, 8:2 (2002), 332–347 | MR | Zbl

[164] A. Salomaa, “Synchronization of finite automata: contributions to an old problem”, The essence of computation. Complexity, analysis, transformation, Essays dedicated to N. D. Jones [on occasion of his 60th birthday], Lecture Notes in Comput. Sci., 2566, Springer, Berlin, 2002, 37–59 | DOI | Zbl

[165] A. Salomaa, “Composition sequences for functions over a finite domain”, Theoret. Comput. Sci., 292:1 (2003), 263–281 | DOI | MR | Zbl

[166] S. Sandberg, “Homing and synchronizing sequences”, Model-based testing of reactive systems. Advanced lectures, Lecture Notes in Comput. Sci., 3472, Springer-Verlag, Berlin, 2005, 5–33 | DOI | MR | Zbl

[167] M. Sch{ü}tzenberger, “On an application of semi groups methods to some problems in coding”, IRE Trans. Inform. Theory, 2:3 (1956), 47–60 | DOI

[168] Y. Shitov, “An improvement to a recent upper bound for synchronizing words of finite automata”, J. Autom. Lang. Comb., 24:2-4 (2019), 367–373 | DOI | MR | Zbl

[169] E. Skvortsov and E. Tipikin, “Experimental study of the shortest reset word of random automata”, Implementation and application of automata, Lecture Notes in Comput. Sci., 6807, Springer, Heidelberg, 2011, 290–298 | DOI | MR | Zbl

[170] P. H. Starke, “Eine Bemerkung über homogene Experimente”, Elektron. Informationsverarb. Kybernet., 2 (1966), 257–259 ; English transl. P. H. Starke, “A remark about homogeneous experiments”, J. Autom. Lang. Comb., 24:2-4 (2019), 133–137 | Zbl | DOI | MR | Zbl

[171] P. H. Starke, Abstrakte Automaten, VEB Deutscher Verlag der Wissenschaften, Berlin, 1969, 392 pp. ; English transl. P. H. Starke, Abstract automata, North-Holland Publishing Co., Amsterdam–London; American Elsevier Publishing Co., Inc., New York, 1972, 419 pp. | MR | Zbl | MR | Zbl

[172] B. Steinberg, “Černý's conjecture and group representation theory”, J. Algebraic Combin., 31 (2010), 83–109 | DOI | MR | Zbl

[173] B. Steinberg, “The averaging trick and the Černý conjecture”, Internat. J. Found. Comput. Sci., 22:7 (2011), 1697–1706 | DOI | MR | Zbl

[174] B. Steinberg, “The Černý conjecture for one-cluster automata with prime length cycle”, Theoret. Comput. Sci., 412:39 (2011), 5487–5491 | DOI | MR | Zbl

[175] M. Suomalainen, A. Q. Nilles, and S. M. LaValle, “Virtual reality for robots”, 2020 IEEE/RSJ international conference on intelligent robots and systems (IROS) (Las Vegas, NV 2020), IEEE, 2020, 11458–11465 | DOI

[176] M. Szykuła, Algorithms for synchronizing automata, Ph.D. thesis, Inst. of Computer Science, Univ. of Wrocław, 2014

[177] M. Szykuła, “Improving the upper bound on the length of the shortest reset word”, 35th symposium on theoretical aspects of computer science, LIPIcs. Leibniz Int. Proc. Inform., 96, Schloss Dagstuhl. Leibniz-Zent. Inform., Wadern, 2018, 56, 13 pp. | DOI | MR | Zbl

[178] M. Szykuła and V. Vorel, “An extremal series of {E}ulerian synchronizing automata”, Developments in language theory, Lecture Notes in Comput. Sci., 9840, Springer, Berlin, 2016, 380–392 | DOI | MR | Zbl

[179] A. N. Trahtman, “An efficient algorithm finds noticeable trends and examples concerning the Černý conjecture”, Mathematical foundations of computer science 2006, Lecture Notes in Comput. Sci., 4162, Springer, Berlin, 2006, 789–800 | DOI | MR | Zbl

[180] A. N. Trahtman, “The Černý conjecture for aperiodic automata”, Discrete Math. Theor. Comput. Sci., 9:2 (2007), 3–10 | DOI | MR | Zbl

[181] A. Trahtman, “Some aspects of synchronization of DFA”, J. Comput. Sci. Tech., 23:5 (2008), 719–727 | DOI | MR

[182] A. N. Trahtman, “The road coloring problem”, Israel J. Math., 172:1 (2009), 51–60 | DOI | MR | Zbl

[183] A. N. Trahtman, “Modifying the upper bound on the length of minimal synchronizing word”, Fundamentals of computation theory, Lecture Notes in Comput. Sci., 6914, Springer, Heidelberg, 2011, 173–180 | DOI | MR | Zbl

[184] A. N. Trahtman, The Černy conjecture, 2022 (v1 – 2012), 14 pp., arXiv: 1202.4626

[185] A. N. Trahtman, The length of a minimal synchronizing word and the Černy conjecture, 2021 (v1 – 2014), 14 pp., arXiv: 1405.2435

[186] A. N. Trahtman, Cerny–Starke conjecture from the sixties of XX century, 2021 (v1 – 2020), 18 pp., arXiv: 2003.06177

[187] M. V. Volkov, “Synchronizing automata and the Černý conjecture”, Language and automata theory and applications, Lecture Notes in Comput. Sci., 5196, Springer, Berlin, 2008, 11–27 | DOI | MR | Zbl

[188] M. V. Volkov, “Synchronizing automata preserving a chain of partial orders”, Theoret. Comput. Sci., 410:37 (2009), 3513–3519 | DOI | MR | Zbl

[189] M. V. Volkov, “Slowly synchronizing automata with idempotent letters of low rank”, J. Autom. Lang. Comb., 24:2-4 (2019), 375–386 | DOI | MR | Zbl

[190] V. Vorel, Synchronization and discontinuous input processing in transition systems, Doctoral thesis, Charles Univ., Prague, 2018, 137 pp., pp. https://dspace.cuni.cz/handle/20.500.11956/104303

[191] V. Vorel and A. Roman, “Parameterized complexity of synchronization and road coloring”, Discrete Math. Theor. Comput. Sci., 17:1 (2015), 283–305 | DOI | MR | Zbl

[192] H. Wielandt, “Unzerlegbare, nicht negative Matrizen”, Math. Z., 52 (1950), 642–648 | DOI | MR | Zbl

[193] D. Zuckerman, “Linear degree extractors and the inapproximability of max clique and chromatic number”, Theory Comput., 3 (2007), 6, 103–128 | DOI | MR | Zbl