Experiments on Synchronizing Automata

• Autorzy: Roman A.
• Języki publikacji: EN

Abstrakty

EN

This work is motivated by the Černy Conjecture - an old unsolved problem in the automata theory. We describe the results of the experiments on synchronizing automata, which have led us to two interesting results. The first one is that the size of an automaton alphabet may play an important role in the issue of synchronization: we have found a 5-state automaton over a 3-letter alphabet which attains the upper bound from the Černy Conjecture, while there is no such automaton (except Černy automaton C5) over a binary alphabet. The second result emerging from the experiments is a theorem describing the dependencies between the automaton structure S expressed in terms of the so-called merging system and the maximal length of all minimal synchronizing words for automata of type S.

• Wydawca: Wydawnictwo Uniwersytetu Jagiellońskiego
• Czasopismo: Schedae Informaticae
• Rocznik: 2010
• Tom: Vol. 19
• Strony: 35--51
• Opis fizyczny: Bibliogr. 23 poz., rys.

Twórcy

autor

Roman A.

Bibliografia

• [1] Ananichev D., Volkov M.; Collapsing words vs. synchronizing words, Lecture Notes in Computer Science 2295, 2001, pp. 166-174.
• [2] Ananichev D., Volkov M.; Synchronizing monotonic automata, Lecture Notes in Computer Science 2710, 2003, pp. 111-121.
• [3] Ananichev D.S., Volkov M.V.; Synchronizing Generalized Monotonic Automata, Workshop on Synchronizing Automata, Turku, Finland, 2004.
• [4] Benenson Y., Adar R., Paz-Elizur T., Livneh L., Shapiro E.; DNA molecule provides a computing machine with both data and fuel, Proceedings of the National Academy of Sciences 100, 2003, pp. 2191-2196.
• [5] Černy J.; Poznámka k. homogennym experimentom s konecnymi automatmi, Mat. fyz. cas SAV 14, 1964, pp. 208-215.
• [6] Černy J., Pirická A., Rosenauerova B.; On directable automata, Kybernetica 7, 1971, pp. 289-298.
• [7] Dubuc L.; Sur les automates circulaires et la conjecture de Černy, RAIRO Informatique Theorique et Applications 32, 1998, pp. 21-34 [in French].
• [8] Eppstein D.; Reset sequences for monotonic automata, SIAM Journal on Computing 19, 1990, pp. 500-510.
• [9] Franki P.; An extremal problem for two families of sets, European Journal of Combinatorics 3, 1982, pp. 125- 127.
• [10] Kari J.; A counter example to a conjecture concerning synchronizing words in finite automata, EATCS Bulletin 73, 2001, p. 146.
• [11] Kari J.; Synchronizing finite automata on Eulerian digraphs, Lecture Notes in Computer Science 2136, 2001, pp. 432-438.
• [12] Kari J.; Synchronization and Stability of Finite Automata, Journal of Universal Computer Science 8(2), 2002, pp. 270-277.
• [13] Kljachko A., Rystsov I.K., Spivak M.A.; An extremely combinatorial problem connected with the bound on the length of a recurrent word in an automata, Kybernetika 2, 1987, pp. 16-25.
• [14] Natarajan B.K.; An algorithmic Approach to the Automated Design of Parts Orienters, Proceedings of the 27th Annual Symposium on Foundations of Computer Science, IEEE, 1986, pp. 132-142.
• [15] Pin J.-E.; Le probleme de la synchronisation et la conjecture de Černy, These de 3eme cycle, Universite Paris VI, 1978.
• [16] Pin J.-E.; On two combinatorial problems arising from automata theory, Annals of Discrete Mathematics 17, 1983, pp. 535-548.
• [17] Roman A.; www.ii.uj.edu.pl/~roman/publications.html
• [18] Roman A., Forys W.; Lower Bound for the Length of Synchronizing Words in Partially-Synchronizing Automata, Lecture Notes in Computer Science 4910, 2008, pp. 448-459 .
• [19] Roman A.; Synchronizing Finite Automata with Short Reset Words, Applied Mathematics and Computation 209, 2009, pp. 125-136.
• [20] Salomaa A.; Compositions over a Finite Domain: from Completeness to Synchronizable Automata, Turku Centre for Computer Science, Technical Report No 350, 2000.
• [21] Trahtman A.N.; An efficient algorithm finds noticeable trends and examples concerning the Cerny conjecture, Lecture Notes in Computer Science 4162, 2006, pp. 789-800.
• [22] Trahtman A.N.; Some results of implemented algorithms of synchronization, 10th Journees Montoises d'Informatique Theorique, Liege, Belgium, September 8-11, 2004.
• [23] Trahtman A.N.; Computations of some examples and notable trends concerning the synchronization, 4th Workshop in Applied and Computational Mathematics, Tel-Aviv 2006.