JOURNAL OF
ALGEBRAIC
COMBINATORICS

Home > Vol 31, No 1 (2010)

Benjamin Steinberg

Let us say that a Cayley graph Γ  of a group G of order n is a Černý Cayley graph if every synchronizing automaton containing Γ  as a subgraph with the same vertex set admits a synchronizing word of length at most ( n - 1) ². In this paper we use the representation theory of groups over the rational numbers to obtain a number of new infinite families of Černý Cayley graphs.

1. Almeida, J., Margolis, S., Steinberg, B., Volkov, M.: Representation theory of finite semigroups, semigroup radicals and formal language theory. Trans. Amer. Math. Soc. 361(3), 1429-1461 (2009)
2. Ananichev, D.S., Volkov, M.V.: Some results on \check Cerný type problems for transformation semigroups. In: Semigroups and languages, pp. 23-42. World Scientific, River Edge (2004)
3. Ananichev, D.S., Volkov, M.V.: Synchronizing generalized monotonic automata. Theoret. Comput. Sci. 330(1), 3-13 (2005)
4. Ananichev, D.S., Volkov, M.V., Zaks, Y.I.: Synchronizing automata with a letter of deficiency
2. Theoret. Comput. Sci. 376(1-2), 30-41 (2007)
5. Arnold, F., Steinberg, B.: Synchronizing groups and automata. Theoret. Comput. Sci. 359(1-3), 101- 110 (2006)
6. Béal, M.P.: A note on Cerny's conjecture and rational series (2003, unpublished)
7. Berstel, J., Reutenauer, C.: Rational series and their languages. EATCS Monographs on Theoretical Computer Science, vol.
12. Springer, Berlin (1988)
8. \check Cerný, J.: A remark on homogeneous experiments with finite automata. Mat.-Fyz. \check Casopis Sloven. Akad. Vied 14, 208-216 (1964)
9. Curtis, C.W., Reiner, I.: Representation theory of finite groups and associative algebras. Wiley Classics Library. Wiley, New York (1988). Reprint of the 1962 original, A Wiley-Interscience Publication
10. Davidoff, G., Sarnak, P., Valette, A.: Elementary number theory, group theory, and Ramanujan graphs. London Mathematical Society Student Texts, vol.
55. Cambridge University Press, Cambridge (2003)
11. Dornhoff, L.: Group representation theory. Part A: Ordinary representation theory. Pure and Applied Mathematics, vol.
7. Dekker, New York (1971)
12. Dubuc, L.: Sur les automates circulaires et la conjecture de \check Cerný. RAIRO Inform. Théor. Appl. 32(1-3), 21-34 (1998)
13. Kari, J.: A counter example to a conjecture concerning synchronizing words in finite automata. Bull. Eur. Assoc. Theor. Comput. Sci. EATCS 73, 146 (2001)
14. Kari, J.: Synchronizing finite automata on Eulerian digraphs. Theoret. Comput. Sci. 295(1-3), 223- 232 (2003). Mathematical foundations of computer science (Mariánské Lázn\check e, 2001)
15. Klyachko, A.A., Rystsov, I.C., Spivak, M.A.: On an extremal combinatorial problem connected with an estimate for the length of a reflexive word in an automaton. Kibernetika (Kiev) 2, 16-20 (1987) 25, 132,
16. Neumann, P.M.: Primitive permutation groups and their section-regular partitions. Michigan Mathematics Journal (to appear)
17. Pin, J.-E.: Sur un cas particulier de la conjecture de Cerny. In: Automata, languages and programming, Fifth Internat. Colloq., Udine,
1978. Lecture Notes in Comput. Sci., vol. 62, pp. 345-352. Springer, Berlin (1978)
18. Pin, J.-E.: On two combinatorial problems arising from automata theory. Ann. Discrete Math. 17, 535-548 (1983)
19. Rystsov, I.K.: Quasioptimal bound for the length of reset words for regular automata. Acta Cybernet. 12(2), 145-152 (1995)
20. Rystsov, I.K.: On the length of reset words for automata with simple idempotents. Kibernet. Sistem. Anal. 3, 32-39 (2000) 187,
21. Trahtman, A.N.: An efficient algorithm finds noticeable trends and examples concerning the \check Cerny conjecture. In: Mathematical foundations of computer science
2006. Lecture Notes in Comput. Sci., vol. 4162, pp. 789-800. Springer, Berlin (2006)
22. Trahtman, A.N.: The \check Cerný conjecture for aperiodic automata. Discrete Math. Theor. Comput. Sci.