Synchronization of finite automata

封面

如何引用文章

全文:

开放存取 开放存取
受限制的访问 ##reader.subscriptionAccessGranted##
受限制的访问 订阅存取

详细

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 Černy's conjecture and methods for their derivation are presented.Bibliography: 193 titles.

作者简介

Mikhail Volkov

Ural State University

Email: Mikhail.Volkov@usu.ru
Doctor of physico-mathematical sciences, Professor

参考

  1. R. L. Adler, L. W. Goodwyn, B. Weiss, “Equivalence of topological Markov shifts”, Israel J. Math., 27:1 (1977), 49–63
  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
  3. J. Almeida, S. Margolis, B. Steinberg, M. Volkov, “Representation theory of finite semigroups, semigroup radicals and formal language theory”, Trans. Amer. Math. Soc., 361:3 (2009), 1429–1461
  4. J. Almeida, E. Rodaro, “Semisimple synchronizing automata and the Wedderburn–Artin theory”, Internat. J. Found. Comput. Sci., 27:2 (2016), 127–145
  5. J. Almeida, B. Steinberg, “Matrix mortality and the Černy–Pin conjecture”, Developments in language theory, Lecture Notes in Comput. Sci., 5583, Springer, Berlin, 2009, 67–80
  6. J. Almeida, M. V. Volkov, “Profinite identities for finite semigroups whose subgroups belong to a given pseudovariety”, J. Algebra Appl., 2:2 (2003), 137–163
  7. Д. С. Ананичев, “Порог аннуляции для частично монотонных автоматов”, Изв. вузов. Матем, 2010, № 1, 3–13
  8. D. S. Ananichev, V. V. Gusev, “Approximation of reset thresholds with greedy algorithms”, Fund. Inform., 145:3 (2016), 221–227
  9. D. S. Ananichev, I. V. Petrov, M. V. Volkov, “Collapsing words: a progress report”, Internat. J. Found. Comput. Sci., 17:3 (2006), 507–518
  10. D. S. Ananichev, M. V. Volkov, “Some results on Černy type problems for transformation semigroups”, Semigroups and languages, World Sci. Publ., River Edge, NJ, 2004, 23–42
  11. D. S. Ananichev, M. V. Volkov, “Synchronizing monotonic automata”, Theoret. Comput. Sci., 327:3 (2004), 225–239
  12. D. S. Ananichev, M. V. Volkov, “Synchronizing generalized monotonic automata”, Theoret. Comput. Sci., 330:1 (2005), 3–13
  13. Д. С. Ананичев, М. В. Волков, В. В. Гусев, “Примитивные орграфы с большими экспонентами и медленно синхронизируемые автоматы”, Комбинаторика и теория графов. IV, Первый Российско-финский симпозиум по дискретной математике (специальный выпуск), Зап. науч. сем. ПОМИ, 402, ПОМИ, СПб., 2012, 9–39
  14. D. Ananichev, 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
  15. J. Araujo, P. Cameron, B. Steinberg, “Between primitive and 2-transitive: synchronization and its friends”, EMS Surv. Math. Sci., 4:2 (2017), 101–184
  16. F. Arnold, B. Steinberg, “Synchronizing groups and automata”, Theoret. Comput. Sci., 359:1-3 (2006), 101–110
  17. У. Р. Эшби, Введение в кибернетику, ИЛ, М., 1959, 432 с.
  18. M.-P. Beal, M. V. Berlinkov, 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
  19. M.-P. Beal, 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
  20. Y. Benenson, R. Adar, T. Paz-Elizur, Z. Livneh, E. Shapiro, “DNA molecule provides a computing machine with both data and fuel”, Proc. Natl. Acad. Sci. USA, 100:5 (2003), 2191–2196
  21. Y. Benenson, T. Paz-Elizur, R. Adar, E. Keinan, Z. Livneh, E. Shapiro, “Programmable and autonomous computing machine made of biomolecules”, Nature, 414:6862 (2001), 430–434
  22. M. V. Berlinkov, “On a conjecture by Carpi and D'Alessandro”, Internat. J. Found. Comput. Sci., 22:7 (2011), 1565–1576
  23. M. V. Berlinkov, “Synchronizing quasi-Eulerian and quasi-one-cluster automata”, Internat. J. Found. Comput. Sci., 24:6 (2013), 729–745
  24. M. V. Berlinkov, “Approximating the minimum length of synchronizing words is hard”, Theory Comput. Syst., 54:2 (2014), 211–223
  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
  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
  27. M. V. Berlinkov, R. Ferens, M. Szykula, “Preimage problems for deterministic finite automata”, J. Comput. System Sci., 115 (2021), 214–234
  28. M. V. Berlinkov, M. Szykula, “Algebraic synchronization criterion and computing reset words”, Inform. Sci., 369 (2016), 718–730
  29. J. Berstel, D. Perrin, C. Reutenauer, Codes and automata, Encyclopedia Math. Appl., 129, Cambridge Univ. Press, Cambridge, 2010, xiv+619 pp.
  30. M. T. Biskup, Error resilience in compressed data – selected topics, Ph.D. thesis, Inst. of Informatics, Univ. of Warsaw, 2008, 136 pp., par
  31. M. T. Biskup, “Guaranteed synchronization of Huffman codes”, Data compression conference (DCC 2008) (Snowbird, UT, 2008), IEEE, 2008, 462–471
  32. M. T. Biskup, W. Plandowski, “Guaranteed synchronization of Huffman codes with known position of decoder”, Data compression conference (DCC 2009) (Snowbird, UT, 2009), IEEE, 2009, 33–42
  33. M. T. Biskup, W. Plandowski, “Shortest synchronizing strings for {H}uffman codes”, Theoret. Comput. Sci., 410:38-40 (2009), 3925–3941
  34. S. Bogdanovic, B. Imreh, M. Ciric, T. Petkovic, “Directable automata and their generalizations: a survey”, Novi Sad J. Math., 29:2 (1999), 29–69
  35. P. Bonizzoni, N. Jonoska, “Existence of constants in regular splicing languages”, Inform. and Comput., 242 (2015), 340–353
  36. V. Boppana, S. P. Rajan, K. Takayama, M. Fujita, “Model checking based on sequential ATPG”, Computer aided verification, Lecture Notes in Comput. Sci., 1633, Springer-Verlag, Berlin, 1999, 418–430
  37. R. A. Brualdi, H. J. Ryser, Combinatorial matrix theory, Encyclopedia Math. Appl., 39, Cambridge Univ. Press, Cambridge, 1991, x+367 pp.
  38. P. J. Cameron, “Dixon's theorem and random synchronization”, Discrete Math., 313:11 (2013), 1233–1236
  39. R. M. Capocelli, L. Gargano, U. Vaccaro, “On the characterization of statistically synchronizable variable-length codes”, IEEE Trans. Inform. Theory, 34:4 (1988), 817–825
  40. A. Carpi, F. D'Alessandro, “Strongly transitive automata and the Černy conjecture”, Acta Inform., 46:8 (2009), 591–607
  41. A. Carpi, 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
  42. A. Carpi, F. D'Alessandro, “Independent sets of words and the synchronization problem”, Adv. in Appl. Math., 50:3 (2013), 339–355
  43. A. Carpi, F. D'Alessandro, “Locally strongly transitive automata in the Černy conjecture and related problems”, J. Autom. Lang. Comb., 24:2-4 (2019), 165–184
  44. J. Černy, “Poznamka k homogennym eksperimentom s konečnymi automatami”, Mat.-Fyz. Časopis Sloven. Akad. Vied., 14:3 (1964), 208–216
  45. J. Černy, A. Piricka, B. Rosenauerova, “On directable automata”, Kybernetika (Prague), 7:4 (1971), 289–298
  46. Yui-Bin Chen, D. J. Ierardi, “The complexity of oblivious plans for orienting and distinguishing polygonal parts”, Algorithmica, 14:5 (1995), 367–397
  47. A. Cherubini, “Synchronizing and collapsing words”, Milan J. Math., 75:1 (2007), 305–321
  48. A. Cherubini, A. Frigeri, Zuhua Liu, “Composing short 3-compressing words on a 2-letter alphabet”, Discrete Math. Theor. Comput. Sci., 19:1 (2017), 17, 35 pp.
  49. A. Cherubini, A. Kisielewicz, “Collapsing words, permutation conditions and coherent colorings of trees”, Theoret. Comput. Sci., 410:21-23 (2009), 2135–2147
  50. A. Cherubini, A. Kisielewicz, “Recognizing 3-collapsing words over a binary alphabet”, Theoret. Comput. Sci., 629 (2016), 64–79
  51. A. Cherubini, A. Kisielewicz, B. Piochi, “On the length of shortest 2-collapsing words”, Discrete Math. Theor. Comput. Sci., 11:1 (2009), 33–44
  52. K. Chmiel, A. Roman, “COMPAS – a computing package for synchronization”, Implementation and application of automata, Lecture Notes in Comput. Sci., 6482, Springer, Berlin, 2011, 79–86
  53. Hyunwoo Cho, Seh-Woong Jeong, F. Somenzi, 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
  54. Hyunwoo Cho, Seh-Woong Jeong, F. Somenzi, C. Pixley, “Synchronizing sequences and symbolic traversal techniques in test generation”, J. Electronic Testing, 4 (1993), 19–31
  55. Т. Кормен, Ч. Лейзерсон, Р. Ривест, К. Штайн, Алгоритмы: построение и анализ, 3-е изд., Вильямс, М., 2011, 1324 с.
  56. Zhen He Cui, Yong He, Shi Yuan Sun, “Synchronizing bounded partially ordered automata”, (Chinese), Chinese J. Comput., 42:3 (2019), 610–623
  57. M. de Bondt, A short proof of a theorem of J.-E. Pin, 2018, 12 pp.
  58. M. de Bondt, H. Don, 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
  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
  60. H. Don, 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
  61. H. Don, H. Zantema, “Counting symbol switches in synchronizing automata”, J. Autom. Lang. Comb., 24:2-4 (2019), 253–286
  62. L. Dubuc, “Sur les automates circulaires et la conjecture de Černy”, RAIRO Inform. Theor. Appl., 32:1-3 (1998), 21–34
  63. M. Dżyga, R. Ferens, V. V. Gusev, M. Szykula, “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.
  64. D. Eppstein, “Reset sequences for monotonic automata”, SIAM J. Comput., 19:3 (1990), 500–510
  65. D. Eppstein, J.-C. Falmagne, “Algorithms for media”, Discrete Appl. Math., 156:8 (2008), 1308–1320
  66. H. Fernau, V. V. Gusev, S. Hoffmann, M. Holzer, M. V. Volkov, 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.
  67. H. Fernau, P. Heggernes, Y. Villanger, “A multi-parameter analysis of hard problems on deterministic finite automata”, J. Comput. System Sci., 81:4 (2015), 747–765
  68. H. Fernau, A. Krebs, “Problems on finite automata and the exponential time hypothesis”, Algorithms (Basel), 10:1 (2017), 24, 25 pp.
  69. M. A. Fischler, 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
  70. P. Frankl, “An extremal problem for two families of sets”, European J. Combin., 3:2 (1982), 125–127
  71. D. Frettlöh, B. Sing, “Computing modular coincidences for substitution tilings and point sets”, Discrete Comput. Geom., 37:3 (2007), 381–407
  72. A. Frigeri, E. Rodaro, “Missing factors of ideals and synchronizing automata”, J. Autom. Lang. Comb., 24:2-4 (2019), 309–320
  73. P. Gawrychowski, Complexity of shortest synchronizing word, preprint, 2008
  74. P. Gawrychowski, 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
  75. M. Gerbush, B. Heeringa, “Approximating minimum reset sequences”, Implementation and application of automata, Lecture Notes in Comput. Sci., 6482, Springer, Berlin, 2011, 154–162
  76. A. Gill, “State-identification experiments in finite automata”, Information and Control, 4:2-3 (1961), 132–154
  77. С. Гинзбург, “О длине кратчайшего однородного эксперимента, устанавливающего конечные состояния машины”, Киберн. сб., 3, ИЛ, М., 1961, 167–186
  78. S. Ginsburg, An introduction to mathematical machine theory, Addison-Wesley Publishing Co., Inc., Reading, MA–Palo Alto, CA–London, 1962, ix+147 pp.
  79. K. Y. Goldberg, “Orienting polygonal parts without sensors”, Algorithmica, 10:2-4 (1993), 201–225
  80. F. Gonze, V. V. Gusev, R. M. Jungers, B. Gerencser, M. V. Volkov, “On the interplay between Černy and {B}abai's conjectures”, Internat. J. Found. Comput. Sci., 30:1 (2019), 93–114
  81. F. Gonze, R. M. Jungers, 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
  82. P. Goralčik, V. Koubek, “Rank problems for composite transformations”, Internat. J. Algebra Comput., 5:3 (1995), 309–316
  83. Р. Грэхем, Д. Кнут, О. Паташник, Конкретная математика. Основание информатики, 2-е изд., испр., Мир, Бином. Лаборатория знаний, М., 2006, 703 с.
  84. M. Grech, A. Kisielewicz, “The Černy conjecture for automata respecting intervals of a directed graph”, Discrete Math. Theor. Comput. Sci., 15:3 (2013), 61–72
  85. M. Grech, A. Kisielewicz, “Synchronizing sequences for road colored digraphs”, Discrete Appl. Math., 285 (2020), 128–140
  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
  87. V. V. Gusev, R. M. Jungers, 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
  88. V. V. Gusev, M. I. Maslennikova, E. V. Pribavkina, “Principal ideal languages and synchronizing automata”, Fund. Inform., 132:1 (2014), 95–108
  89. V. V. Gusev, E. V. Pribavkina, “On codeword lengths guaranteeing synchronization”, Combinatorics on words, Lecture Notes in Comput. Sci., 11682, Springer, Cham, 2019, 207–216
  90. J. Hastad, “Clique is hard to approximate within $n^{1-varepsilon}$ ”, Acta Math., 182:1 (1999), 105–142
  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
  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
  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
  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
  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
  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
  97. S. Hoffmann, “Constrained synchronization and commutativity”, Theoret. Comput. Sci., 890 (2021), 147–170
  98. H. J{ü}rgensen, “Synchronization”, Inform. and Comput., 206:9-10 (2008), 1033–1044
  99. J. Kari, “A counter example to a conjecture concerning synchronizing words in finite automata”, Bull. Eur. Assoc. Theor. Comput. Sci. EATCS, 73 (2001), 146
  100. J. Kari, “Synchronizing finite automata on Eulerian digraphs”, Theoret. Comput. Sci., 295:1-3 (2003), 223–232
  101. J. Kari, M. Volkov, “Černy's conjecture and the road colouring problem”, Handbook of automata theory, Ch. 15, v. I, Theoretical foundations, EMS Press, Berlin, 2021, 525–565
  102. A. Kisielewicz, J. Kowalski, M. Szykula, “Computing the shortest reset words of synchronizing automata”, J. Comb. Optim., 29:1 (2015), 88–124
  103. A. Kisielewicz, J. Kowalski, M. Szykula, “Experiments with synchronizing automata”, Implementation and application of automata, Lecture Notes in Comput. Sci., 9705, Springer, Cham, 2016, 176–188
  104. A. Kisielewicz, M. Szykula, “Generating small automata and the Černy conjecture”, Implementation and application of automata, Lecture Notes in Comput. Sci., 7982, Springer, Heidelberg, 2013, 340–348
  105. A. Kisielewicz, M. Szykula, “Synchronizing automata with extremal properties”, Mathematical foundations of computer science 2015, Part 1, Lecture Notes in Comput. Sci., 9234, Springer, Heidelberg, 2015, 331–343
  106. С. К. Клини, “Представление событий в нервных сетях и конечных автоматах”, Автоматы, Сб. ст., ИЛ, М., 1956, 15–67
  107. А. А. Клячко, И. К. Рысцов, М. А. Спивак, “Об одной экстремальной комбинаторной задаче, связанной с оценкой длины возвратного слова в автомате”, Кибернетика, 25:2 (1987), 16–20
  108. Z. Kohavi, 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
  109. Z. Kohavi, J. Winograd, “Establishing certain bounds concerning finite automata”, J. Comput. System Sci., 7:3 (1973), 288–299
  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
  111. M. W. Krentel, “The complexity of optimization problems”, J. Comput. System Sci., 36:3 (1988), 490–509
  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, B. Rudner, Study of the application of coding theory, Tech. rep. PIBEP-69-034, Dept. Electrophysics, Polytechnic Inst., Brooklyn, Farmingdale, NY, 1969
  115. В. И. Левенштейн, “Самонастраивающиеся автоматы для декодирования сообщений”, Докл. АН СССР, 141:6 (1961), 1320–1323
  116. Chung Laung Liu, “Determination of the final state of an automaton whose initial state is unknown”, IEEE Trans. Electronic Computers, EC-12:6 (1963), 918–920
  117. Chung Laung Liu, Some memory aspects of finite automata, Tech. rep. 411, Research Lab. Electronics, Massachusetts Inst., MIT Res. Lab. Electronics, Cambridge, MA, 1963, 71 pp.
  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
  119. M. Maslennikova, “Reset complexity of ideal languages over a binary alphabet”, Internat. J. Found. Comput. Sci., 30:6-7 (2019), 1177–1196
  120. M. Maslennikova, 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
  121. M. Maslennikova, E. Rodaro, “Trim strongly connected synchronizing automata and ideal languages”, Fund. Inform., 162:2-3 (2018), 183–203
  122. A. Mateescu, A. Salomaa, “Many-valued truth functions, Černy's conjecture, and road coloring”, Current trends in theoretical computer science. Entering the 21th century, World Sci. Publ., River Edge, NJ, 2001, 693–707
  123. Ю. Т. Медведев, “О классе событий, допускающих представление в конечном автомате”, Автоматы, Сб. ст., ИЛ, М., 1956, 385–401
  124. E. H. Moore, “On certain crinkly curves”, Trans. Amer. Math. Soc., 1:1 (1900), 72–90
  125. Э. Ф. Мур, “Умозрительные эксперименты с последовательностными машинами”, Автоматы, Сб. ст., ИЛ, М., 1956, 179–210
  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
  127. B. K. Natarajan, “Some paradigms for the automated design of parts feeders”, Int. J. Robot. Res., 8:6 (1989), 98–109
  128. C. Nicaud, “The Černy conjecture holds with high probability”, J. Autom. Lang. Comb., 24:2-4 (2019), 343–365
  129. J. Olschewski, 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
  130. C. H. Papadimitriou, Computational complexity, Addison-Wesley Publishing Co., Reading, MA, 1994, xvi+523 pp.
  131. C. H. Papadimitriou, M. Yannakakis, “The complexity of facets (and some facets of complexity)”, J. Comput. System Sci., 28:2 (1984), 244–259
  132. J.-E. Pin, Le problème de la synchronisation et la conjecture de Černy, 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
  134. J.-E. Pin, “Utilisation de l'algèbre lineaire en theorie des automates”, Actes du 1er colloque AFCET-SMF de mathematiques appliquees (Palaiseau, 1978), AFCET, 1978, 85–92
  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
  136. C. Pixley, S.-W. Jeong, 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
  137. R. Pöschel, M. V. Sapir, N. V. Sauer, M. G. Stone, M. V. Volkov, “Identities in full transformation semigroups”, Algebra Universalis, 31:4 (1994), 580–588
  138. Е. В. Прибавкина, “Медленно синхронизируемые автоматы с нулем и непокрывающие множества”, Матем. заметки, 90:3 (2011), 422–430
  139. E. V. Pribavkina, E. Rodaro, “Synchronizing automata with finitely many minimal synchronizing words”, Inform. and Comput., 209:3 (2011), 568–579
  140. N. Pytheas Fogg, Substitutions in dynamics, arithmetics and combinatorics, Lecture Notes in Math., 1794, eds. V. Berthe, S. Ferenczi, C. Mauduit, A. Siegel, Springer-Verlag, Berlin, 2002
  141. M. O. Rabin, D. Scott, “Finite automata and their decision problems”, IBM J. Res. Develop., 3:2 (1959), 114–125
  142. J. L. Ramirez Alfonsin, The Diophantine Frobenius problem, Oxford Lecture Ser. Math. Appl., 30, Oxford Univ. Press, Oxford, 2005, xvi+243 pp.
  143. A. S. Rao, K. Y. Goldberg, “Manipulating algebraic parts in the plane”, IEEE Trans. Robotics Autom., 11:4 (1995), 598–602
  144. R. Reis, E. Rodaro, “Ideal regular languages and strongly connected synchronizing automata”, Theoret. Comput. Sci., 653 (2016), 97–107
  145. June-Kyung Rho, F. Somenzi, 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
  146. E. Rodaro, “Strongly connected synchronizing automata and the language of minimal reset words”, Adv. in Appl. Math., 99 (2018), 158–173
  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
  148. A. Roman, M. Szykula, “Forward and backward synchronizing algorithms”, Expert Syst. Appl., 42:24 (2015), 9512–9527
  149. И. К. Рысцов, “Оценка длины ядерного слова для конечного автомата”, Автоматы, Межвуз. науч. сб., т. 2, Сарат. гос. ун-т, Саратов, 1977, 43–48
  150. И. К. Рысцов, “О минимизации синхронизирующих слов для конечных автоматов”, Теоретические вопросы проектирования вычислительных систем, АН УССР, Науч. совет по пробл. “Кибернетика”, Ин-т кибернетики, Киев, 1980, 75–82
  151. I. K. Rystsov, “Polynomial complete problems in automata theory”, Inform. Process. Lett., 16:3 (1983), 147–151
  152. И. К. Рысцов, “О ранге конечного автомата”, Кибернетика и системный анализ, 28:3 (1992), 3–10
  153. И. К. Рысцов, “Возвратные слова для разрешимых автоматов”, Кибернетика и системный анализ, 30:6 (1994), 21–26
  154. И. К. Рысцов, “Почти оптимальная оценка длины возвратного слова для регулярных автоматов”, Кибернетика и системный анализ, 31:5 (1995), 40–48
  155. I. K. Rystsov, “Quasioptimal bound for the length of reset words for regular automata”, Acta Cybernet., 12:2 (1995), 145–152
  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
  157. I. Rystsov, “Reset words for commutative and solvable automata”, Theoret. Comput. Sci., 172:1-2 (1997), 273–279
  158. И. К. Рысцов, “О длине возвратных слов для автоматов с простыми идемпотентами”, Кибернетика и системный анализ, 36:3 (2000), 32–39
  159. I. K. Рисцов, “Проблема Чернi для автоматiв iз простими iдемпотентами”, Кiбернетика та системний аналiз, 58:1 (2022), 3–10
  160. A. Ryzhikov, “Synchronization problems in automata without non-trivial cycles”, Theoret. Comput. Sci., 787 (2019), 77–88
  161. A. Ryzhikov, 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.
  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
  163. A. Salomaa, “Generation of constants and synchronization of finite automata”, J. UCS, 8:2 (2002), 332–347
  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
  165. A. Salomaa, “Composition sequences for functions over a finite domain”, Theoret. Comput. Sci., 292:1 (2003), 263–281
  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
  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
  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
  169. E. Skvortsov, 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
  170. P. H. Starke, “Eine Bemerkung über homogene Experimente”, Elektron. Informationsverarb. Kybernet., 2 (1966), 257–259
  171. P. H. Starke, Abstrakte Automaten, VEB Deutscher Verlag der Wissenschaften, Berlin, 1969, 392 pp.
  172. B. Steinberg, “Černy's conjecture and group representation theory”, J. Algebraic Combin., 31 (2010), 83–109
  173. B. Steinberg, “The averaging trick and the Černy conjecture”, Internat. J. Found. Comput. Sci., 22:7 (2011), 1697–1706
  174. B. Steinberg, “The Černy conjecture for one-cluster automata with prime length cycle”, Theoret. Comput. Sci., 412:39 (2011), 5487–5491
  175. M. Suomalainen, A. Q. Nilles, 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
  176. M. Szykula, Algorithms for synchronizing automata, Ph.D. thesis, Inst. of Computer Science, Univ. of Wroclaw, 2014
  177. M. Szykula, “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.
  178. M. Szykula, 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
  179. A. N. Trahtman, “An efficient algorithm finds noticeable trends and examples concerning the Černy conjecture”, Mathematical foundations of computer science 2006, Lecture Notes in Comput. Sci., 4162, Springer, Berlin, 2006, 789–800
  180. A. N. Trahtman, “The Černy conjecture for aperiodic automata”, Discrete Math. Theor. Comput. Sci., 9:2 (2007), 3–10
  181. A. Trahtman, “Some aspects of synchronization of DFA”, J. Comput. Sci. Tech., 23:5 (2008), 719–727
  182. A. N. Trahtman, “The road coloring problem”, Israel J. Math., 172:1 (2009), 51–60
  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
  184. A. N. Trahtman, The Černy conjecture, 2022 (v1 – 2012), 14 pp.
  185. A. N. Trahtman, The length of a minimal synchronizing word and the Černy conjecture, 2021 (v1 – 2014), 14 pp.
  186. A. N. Trahtman, Cerny–Starke conjecture from the sixties of XX century, 2021 (v1 – 2020), 18 pp.
  187. M. V. Volkov, “Synchronizing automata and the Černy conjecture”, Language and automata theory and applications, Lecture Notes in Comput. Sci., 5196, Springer, Berlin, 2008, 11–27
  188. M. V. Volkov, “Synchronizing automata preserving a chain of partial orders”, Theoret. Comput. Sci., 410:37 (2009), 3513–3519
  189. M. V. Volkov, “Slowly synchronizing automata with idempotent letters of low rank”, J. Autom. Lang. Comb., 24:2-4 (2019), 375–386
  190. V. Vorel, Synchronization and discontinuous input processing in transition systems, Doctoral thesis, Charles Univ., Prague, 2018, 137 pp., par
  191. V. Vorel, A. Roman, “Parameterized complexity of synchronization and road coloring”, Discrete Math. Theor. Comput. Sci., 17:1 (2015), 283–305
  192. H. Wielandt, “Unzerlegbare, nicht negative Matrizen”, Math. Z., 52 (1950), 642–648
  193. D. Zuckerman, “Linear degree extractors and the inapproximability of max clique and chromatic number”, Theory Comput., 3 (2007), 6, 103–128

补充文件

附件文件
动作
1. JATS XML
下载

版权所有 © Volkov M.V., 2022

Согласие на обработку персональных данных с помощью сервиса «Яндекс.Метрика»

1. Я (далее – «Пользователь» или «Субъект персональных данных»), осуществляя использование сайта https://journals.rcsi.science/ (далее – «Сайт»), подтверждая свою полную дееспособность даю согласие на обработку персональных данных с использованием средств автоматизации Оператору - федеральному государственному бюджетному учреждению «Российский центр научной информации» (РЦНИ), далее – «Оператор», расположенному по адресу: 119991, г. Москва, Ленинский просп., д.32А, со следующими условиями.

2. Категории обрабатываемых данных: файлы «cookies» (куки-файлы). Файлы «cookie» – это небольшой текстовый файл, который веб-сервер может хранить в браузере Пользователя. Данные файлы веб-сервер загружает на устройство Пользователя при посещении им Сайта. При каждом следующем посещении Пользователем Сайта «cookie» файлы отправляются на Сайт Оператора. Данные файлы позволяют Сайту распознавать устройство Пользователя. Содержимое такого файла может как относиться, так и не относиться к персональным данным, в зависимости от того, содержит ли такой файл персональные данные или содержит обезличенные технические данные.

3. Цель обработки персональных данных: анализ пользовательской активности с помощью сервиса «Яндекс.Метрика».

4. Категории субъектов персональных данных: все Пользователи Сайта, которые дали согласие на обработку файлов «cookie».

5. Способы обработки: сбор, запись, систематизация, накопление, хранение, уточнение (обновление, изменение), извлечение, использование, передача (доступ, предоставление), блокирование, удаление, уничтожение персональных данных.

6. Срок обработки и хранения: до получения от Субъекта персональных данных требования о прекращении обработки/отзыва согласия.

7. Способ отзыва: заявление об отзыве в письменном виде путём его направления на адрес электронной почты Оператора: info@rcsi.science или путем письменного обращения по юридическому адресу: 119991, г. Москва, Ленинский просп., д.32А

8. Субъект персональных данных вправе запретить своему оборудованию прием этих данных или ограничить прием этих данных. При отказе от получения таких данных или при ограничении приема данных некоторые функции Сайта могут работать некорректно. Субъект персональных данных обязуется сам настроить свое оборудование таким способом, чтобы оно обеспечивало адекватный его желаниям режим работы и уровень защиты данных файлов «cookie», Оператор не предоставляет технологических и правовых консультаций на темы подобного характера.

9. Порядок уничтожения персональных данных при достижении цели их обработки или при наступлении иных законных оснований определяется Оператором в соответствии с законодательством Российской Федерации.

10. Я согласен/согласна квалифицировать в качестве своей простой электронной подписи под настоящим Согласием и под Политикой обработки персональных данных выполнение мною следующего действия на сайте: https://journals.rcsi.science/ нажатие мною на интерфейсе с текстом: «Сайт использует сервис «Яндекс.Метрика» (который использует файлы «cookie») на элемент с текстом «Принять и продолжить».