Experiments on Synchronizing Automata
Choose format
RIS BIB ENDNOTEExperiments on Synchronizing Automata
Publication date: 23.03.2011
Schedae Informaticae, 2010, Volume 19, pp. 35-52
Authors
Experiments on Synchronizing Automata
This work is motivated by the ˇCern´y 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 ˇCern´y Conjecture, while there is no such automaton (except ˇCern´y 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.
Ananichev D., Volkov M.; Collapsing words vs. synchronizing words, Lecture Notes in Computer Science 2295, 2001, pp. 166–174.
Ananichev D., Volkov M.; Synchronizing monotonic automata, Lecture Notes in Computer Science 2710, 2003, pp. 111–121.
Ananichev D.S., Volkov M.V.; Synchronizing Generalized Monotonic Automata, Workshop on Synchronizing Automata, Turku, Finland, 2004.
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.
Cˇerny´ J.; Pozna´mka k. homog´ennym experimentom s konecnymi automatmi, Mat. fyz. cas SAV 14, 1964, pp. 208–215.
Cˇerny´y J., Piricka´ A., Rosenauerova B.; On directable automata, Kybernetica 7, 1971, pp. 289–298.
Dubuc L.; Sur les automates circulaires et la conjecture de Cerny, RAIRO In- formatique Theorique et Applications 32, 1998, pp. 21–34 [in French].
Eppstein D.; Reset sequences for monotonic autoamta, SIAM Journal on Computing 19, 1990, pp. 500–510.
Frankl P.; An extremal problem for two families of sets, European Journal of Combinatorics 3, 1982, pp. 125– 127.
Kari J.; A counter example to a conjecture concerning synchronizing words in nite automata, EATCS Bulletin 73, 2001, p. 146.
Kari J.; Synchronizing finite automata on Eulerian digraphs, Lecture Notes in Computer Science 2136, 2001, pp. 432–438.
Kari J.; Synchronization and Stability of Finite Automata, Journal of Universal Computer Science 8(2), 2002, pp. 270–277.
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.
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.
Pin J.-E.; Le probleme de la synchronisation et la conjecture de Cˇern´y, These de 3eme cycle, Universit´e Paris VI, 1978.
Pin J.-E.; On two combinatorial problems arising from automata theory, Annals of Discrete Mathematics 17, 1983, pp. 535–548.
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 .
Roman A.; Synchronizing Finite Automata with Short Reset Words, Applied Mathematics and Computation 209, 2009, pp. 125–136.
Salomaa A.; Compositions over a Finite Domain: from Completeness to Synchronizable Automata, Turku Centre for Computer Science, Technical Report No 350, 2000.
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.
Trahtman A.N.; Some results of implemented algorithms of synchronization, 10th Journees Montoises d'Informatique Theorique, Li`ege, Belgium, September 8–11, 2004.
Trahtman A.N.; Computations of some examples and notable trends concerning the synchronization, 4th Workshop in Applied and Computational Mathematics, Tel-Aviv 2006.
Information: Schedae Informaticae, 2010, Volume 19, pp. 35-52
Article type: Original scientific article
Published at: 23.03.2011
Article status: Open
Licence: None
Percentage share of authors:
Article corrections:
-Publication languages:
EnglishView count: 2707
Number of downloads: 1398