Automata, homomorphism of

A mapping of the input and output alphabets and of the set of states of an automaton into analogous sets of a second automaton that preserves the transition and output functions. More precisely, a homomorphism of an automaton $\mathfrak A _ {1} = (A _ {1} , S _ {1} , B _ {1} , \phi _ {1} , \psi _ {1} )$ into an automaton $\mathfrak A _ {2} = (A _ {2} , S _ {2} , B _ {2} , \phi _ {2} , \psi _ {2} )$( cf. Automaton, finite) is a mapping $h = ( h _ {1} , h _ {2} , h _ {3} )$ of the set $A _ {1} \times S _ {1} \times B _ {1}$ into the set $A _ {2} \times S _ {2} \times B _ {2}$

$$h _ {1} : A _ {1} \rightarrow A _ {2} ,\ h _ {2} : S _ {1} \rightarrow S _ {2} , \ h _ {3} : B _ {1} \rightarrow B _ {2} ,$$

such that the following equalities are valid for any $s$ from $S _ {1}$ and $a$ from $A _ {1}$:

$$h _ {2} \phi _ {1} ( s , a ) = \phi _ {2} ( h _ {2} ( s ),\ h _ {1} ( a ) ),$$

$$h _ {3} \psi _ {1} ( s , a ) = \psi _ {2} ( h _ {2} ( s ), h _ {1} ( a ) ).$$

Initialized automata are subject to the additional requirement that $h$ maps the initial state to the initial state. The automata $\mathfrak A _ {1}$ and $\mathfrak A _ {2}$ are said to be homomorphic if there exists a homomorphism $h$ of automata mapping $A _ {1} \times S _ {1} \times B _ {1}$ into $A _ {2} \times S _ {2} \times B _ {2}$. If, in addition, $h$ is one-to-one, $h$ is called an isomorphism, and the automata $\mathfrak A _ {1}$ and $\mathfrak A _ {2}$ are said to be isomorphic automata. If the alphabets $A _ {1}$ and $A _ {2}$, and also the alphabets $B _ {1}$ and $B _ {2}$, are identical and the mappings $h _ {1}$ and $h _ {3}$ are the identity mappings, the homomorphism (isomorphism) $h$ is known as a state homomorphism (state isomorphism). Input and output homomorphisms (isomorphisms) are defined in a similar manner. State-isomorphic automata and state-homomorphic initialized automata are equivalent (cf. Automata, equivalence of).

The concept of a homomorphism of automata is used in the context of problems concerning minimization, decomposition and completeness of automata, among others.

References

[1]	V.M. Glushkov, "The abstract theory of automata" Russian Math. Surveys , 16 : 5 (1961) pp. 1–53 Uspekhi Mat. Nauk , 16 : 5 (1961) pp. 3–62