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