Merging States and Synchronization Problem

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

Abstrakty

EN

In this paper we introduce the notion of merging states and merging systems and we use it for the classification of finite de- terministic automata without initial and final states. We investigate the dependencies between the structure of an automaton described by merging systems and maximal lengths of minimal synchronizing words for automata which structures belong to the given class of merging sys- tems. Numerical results for certain classes of automata are presented. We also give some properties of merging systems themselves. The work is motivated by the famous, unsolved Cerny Conjecture. The aim of this paper is to propose the use of merging systems in the research on the Conjecture.

Słowa kluczowe

EN

synchronization; Cerny Conjecture; merging states

• Wydawca: Wydawnictwo Uniwersytetu Jagiellońskiego
• Czasopismo: Schedae Informaticae
• Rocznik: 2006
• Tom: Vol. 15
• Strony: 95--108
• Opis fizyczny: Bibliogr. 16 poz., rys.

Twórcy

autor

Roman A.

• Jagiellonian University, Institute of Computer Science Nawojki 11, 30-072 Kraków, Poland,

Bibliografia

• [1] Ananichev D., Volkov M.; Synchronizing monotonic automata, DLT 2003, Lecture Notes in Computer Science, Vol. 2710, 2003, pp. 111-121.
• [2] Ananichev D.S., Volkov M.V.; Synchronizing Generalized Monotonic Automata, in: Workshop on Synchronizing Automata, Turku, Finland, 2004.
• [3] Benenson Y., Adar R., Paz-Elizur T., Livneh L., Shapiro E.; DNA molecule provides a computing machine with both data and fuel, Proc. National Acad.Sci. USA, 100, 2003, pp. 2191-2196.
• [4] Černy J.; Poznámka k. homogénnym experimentom s konecnymi automatmi, Mat. fyz. cas SAV, 14, 1964, pp. 208-215.
• [5] Černy J., Pirick A., Rosenauerova B.; On directable automata, Kybernetica, 7,1971, pp. 289-298.
• [6] Dubuc L.; Sur les automates circulaires et la conjecture de Černy, RAIRO Inform. Theor. Appl., 32, 1998, pp. 21-34 [in French].
• [7] Eppstein D.; Reset sequences for monotonic automata, SIAM J. Comput., 19, 1990, pp. 500-510.
• [8] Kari J.; A counter example to a conjecture concerning synchronizing words in finite automata, EATCS Bulletin, 73, 2001, p. 146.
• [9] Kari J.; Synchronizing finite automata on Eulerian digraphs, Mathematical Foundations of Computer Science; 26th Internat. Symp., Marianske Lazne, 2001, Lecture Notes in Computer Science, Vol. 2136, 2001, pp. 432-438.
• [10] Kari J.; Synchronization and Stability of Finite Automata, JUCS, 8,2, 2002, pp. 270-277.
• [11] 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.
• [12] Natarajan B. K.; An algorithmic Approach to the Automated Design of Parts Orienters, in: Proceedings 27th Annual Symp. Foundations of Computer Science, IEEE, 1986, pp. 132-142.
• [13] Pin J.-E.; On two combinatorial problems arising from automata theory, Annals of Discrete Mathematics, 17, 1983, pp. 535-548.
• [14] Salomaa A.; Generation of constants and synchronization of finite automata, J. of Univers. Comput. Sci., 8, 2002, pp. 332-347.
• [15] Trahtman A.N.; The existence of synchronising word and Černy conjecture for some finite automata, to appear in Discrete Appl. Math, 2002.
• [16] Trahtman A.N.; Some results of implemented algorithms of synchronization, 10-th Journees Montoises d'Inform. Theor., Liege, Belgia, September 8-11, 2004.