Abstract
The Hybrid Černý-Road coloring problem is investigated for graphs with Hamiltonian paths. We prove that if an aperiodic, strongly connected digraph of costant outdegree with n vertices has an Hamiltonian path, then it admits a synchronizing coloring with a reset word of length 2(n − 2)(n − 1) + 1. The proof is based upon some new results concerning locally strongly transitive automata.
This work was partially supported by MIUR project ”Aspetti matematici e applicazioni emergenti degli automi e dei linguaggi formali” and by fundings ”Facoltà di Scienze MM. FF. NN. 2008” of the University of Rome ”La Sapienza”.
Access provided by Autonomous University of Puebla. Download to read the full chapter text
Chapter PDF
Similar content being viewed by others
References
Adler, R.L., Goodwyn, L.W., Weiss, B.: Equivalence of topological Markov shifts. Israel J. Math. 27, 49–63 (1977)
Ananichev, D.S., Volkov, M.V.: Synchronizing generalized monotonic automata. Theoret. Comput. Sci. 330(1), 3–13 (2005)
Béal, M.-P.: A note on Černý’s Conjecture and rational series, technical report, Institut Gaspard Monge, Université de Marne-la-Vallée (2003)
Béal, M.-P., Perrin, D.: A quadratic upper bound on the size of a synchronizing word in one-cluster automata. In: Diekert, V., Nowotka, D. (eds.) DLT 2009. LNCS, vol. 5583, pp. 81–90. Springer, Heidelberg (2009)
Béal, M.-P., Berlinkov, M.V., Perrin, D.: A quadratic upper bound on the size of a synchronizing word in one-cluster automata. International Journal of Foundations of Computer Science (to appear 2010)
Berstel, J., Reutenauer, C.: Rational series and their languages. Springer, Heidelberg (1988)
Carpi, A.: On synchronizing unambiguous automata. Theoret. Comput. Sci. 60, 285–296 (1988)
Carpi, A., D’Alessandro, F.: Strongly transitive automata and the Černý conjecture. Acta Informatica 46, 591–607 (2009)
Carpi, A., D’Alessandro, F.: The synchronization problem for locally strongly transitive automata. In: Královič, R., Niwiński, D. (eds.) MFCS 2009. LNCS, vol. 5734, pp. 211–222. Springer, Heidelberg (2009)
Černý, J.: Poznámka k. homogénnym experimenton s konečnými automatmi. Mat. fyz. cas SAV 14, 208–215 (1964)
Culik II, K., Karhumäki, J., Kari, J.: A note on synchronized automata and road coloring problem. Internat. J. Found. Comput. Sci. 13, 459–471 (2002)
Dubuc, L.: Sur les automates circulaires et la conjecture de Cerny. RAIRO Inform. Théor. Appl. 32, 21–34 (1998)
Eilenberg, S.: Automata, Languages and Machines, vol. A. Academic Press, London (1974)
Frankl, P.: An extremal problem for two families of sets. Eur. J. Comb. 3, 125–127 (1982)
Kari, J.: Synchronizing finite automata on Eulerian digraphs. Theoret. Comput. Sci. 295, 223–232 (2003)
Pin, J.E.: Le problème de la synchronization et la conjecture de Cerny, Thèse de 3ème cycle, Université de Paris 6 (1978)
Pin, J.E.: Sur un cas particulier de la conjecture de Cerny. In: Ausiello, G., Böhm, C. (eds.) ICALP 1978. LNCS, vol. 62, pp. 345–352. Springer, Heidelberg (1978)
Rystov, I.: Almost optimal bound of recurrent word length for regular automata. Cybern. Syst. Anal. 31(5), 669–674 (1995)
Steinberg, B.: The averaging trick and the Černý conjecture, Preprint arXiv: 0910.0410v2 (2010)
Trahtman, A.N.: The Cerny conjecture for aperiodic automata. Discrete Math. and Theor. Comput. Sci. 9(2), 3–10 (2007)
Trahtman, A.N.: The road coloring problem. Israel J. Math. 172, 51–60 (2009)
Volkov, M.V.: Communication. In: Around the Černý conjecture, International Workshop, University of Wroclaw, Poland (June 2008)
Volkov, M.V.: Synchronizing automata and the Cerny conjecture. In: Martín-Vide, C., Otto, F., Fernau, H. (eds.) LATA 2008. LNCS, vol. 5196, pp. 11–27. Springer, Heidelberg (2008)
Author information
Authors and Affiliations
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2010 Springer-Verlag Berlin Heidelberg
About this paper
Cite this paper
Carpi, A., D’Alessandro, F. (2010). On the Hybrid Černý-Road Coloring Problem and Hamiltonian Paths. In: Gao, Y., Lu, H., Seki, S., Yu, S. (eds) Developments in Language Theory. DLT 2010. Lecture Notes in Computer Science, vol 6224. Springer, Berlin, Heidelberg. https://doi.org/10.1007/978-3-642-14455-4_13
Download citation
DOI: https://doi.org/10.1007/978-3-642-14455-4_13
Publisher Name: Springer, Berlin, Heidelberg
Print ISBN: 978-3-642-14454-7
Online ISBN: 978-3-642-14455-4
eBook Packages: Computer ScienceComputer Science (R0)