Cerny's conjecture, synchronizing automata, group representation theory

Abstract

Let us say that a Cayley graph $\Gamma$ of a group $G$ of order $n$ is a Cerny Cayley graph if every synchronizing automaton containing $\Gamma$ as a subgraph with the same vertex set admits a synchronizing word of length at most $(n-1{)}^2$. 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.

References in corpus (1)

• Representation Theory of Finite Semigroups, Semigroup Radicals and Formal Language Theory