Semigroups and the generalized road coloring problem (Q706042)

Consider a finite automaton having a finite set \(X\) of states, a finite set of inputs \({\mathcal A}\) and a state transition function \(\delta \). The semigroup \(S\) generated under composition by \(\{R_{a}:a\in {\mathcal A}\}\) is called the semigroup of the automaton, where \(R_{a}(x)=\delta (x,a)\). For any digraph \(G=(V,E)\) such that all vertices have the same outdegree, any labeling of the edges with members of \({\mathcal A}\) such that all the edges issuing from any given vertex have distinct labelings is called a coloring of the digraph. Any coloring uniquely determines an automaton, where \(R_{a}(x)=xa\) is the terminal point of the directed edge with initial point \(x\) and label \(a\) and we refer to the semigroup \(S\) as the coloring semigroup. The main result of this paper is the following: Let \(G\) be a strongly connected digraph such that all vertices have the same outdegree and \(S=\{R_{a}:a\in {\mathcal A}\}\) be a minimal coloring semigroup with kernel \(K\). If \(K\) is a right group with rank(\(K)=t\), then \(G\) is periodic of order \(t\).