A class of semisimple automata (Q2704387)

All graphs here are finite directed graphs without multiple edges but possibly with loops. The graph algebra \(\text{Alg}(G)\) of a graph \(G\) is the set \(V(G)\bigcup \{\infty\} \) with the multiplication: \(xy=x\) iff \((x,y)\in E(G)\) and \(xy=\infty \) otherwise. Denote by \(\text{Alg}(G)^1\) the algebra \(\text{Alg}(G)\) with identity \(1\) adjoined. An automaton of the graph algebra \(\text{Alg}(G)\) is a map \(f:X\rightarrow \text{Alg}(G)^1\) and a subset \(T\) of \(\text{Alg}(G)^1\) where \(\text{Alg}(G)^1\) is the set of states, \(1\) is the initial state, \(T\) is the set of terminal states and the next state function is defined by \(a.x=af(x)\). Theorem: Every automaton of the graph algebra of a graph \(G\) satisfies the following semisimplicity properties: 1) The automaton has no proper essential congruences, 2) The Nerode congruence is a join of minimal congruences, 3) Every congruence is a direct summand. The authors characterize the languages recognized by automata of graph algebras and also give explicit regular expressions.