Congruences on Automata
Andrei Kelarev · 2003
Let G = (V,E) be a graph, and let Alg(G)1 = Alg(G) U {1} denote its graph algebra with the identity element 1 adjoined. We take a subset T of Alg(G) U {1}, an arbitrary mapping /: X —► Alg(G) U {1}, and define the following right automaton Atmr(G,T): • the set of states of Atmr(G,T) is V(G) U {1}; • 1 is the initial state; • T is the set of terminal states; • the next-state function is given by a x = a f(x ), for all a G V (G)U{1}, Hence the eventual-state function is defined by a • (x xx2 •••«!») = (••• {(a>f(xi))f(x2) ) . . . )/(s»), for a € Alg(G)1 and x i ,x 2, . . . ,x n £ X. The transition diagram of this automaton is a labeled Cayley graph of Alg(G).