Semigroups and the generalized road coloring problem (Q706042)
From MaRDI portal
scientific article
Language | Label | Description | Also known as |
---|---|---|---|
English | Semigroups and the generalized road coloring problem |
scientific article |
Statements
Semigroups and the generalized road coloring problem (English)
0 references
16 February 2005
0 references
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\).
0 references
digraph
0 references
coloring semigroups
0 references
completely simple semigroups
0 references