View source for 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 <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/a/a014/a014050/a0140501.png" /> into an automaton <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/a/a014/a014050/a0140502.png" /> (cf. [[Automaton, finite|Automaton, finite]]) is a mapping <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/a/a014/a014050/a0140503.png" /> of the set <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/a/a014/a014050/a0140504.png" /> into the set <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/a/a014/a014050/a0140505.png" />

<table class="eq" style="width:100%;"> <tr><td valign="top" style="width:94%;text-align:center;"><img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/a/a014/a014050/a0140506.png" /></td> </tr></table>

such that the following equalities are valid for any <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/a/a014/a014050/a0140507.png" /> from <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/a/a014/a014050/a0140508.png" /> and <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/a/a014/a014050/a0140509.png" /> from <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/a/a014/a014050/a01405010.png" />:

<table class="eq" style="width:100%;"> <tr><td valign="top" style="width:94%;text-align:center;"><img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/a/a014/a014050/a01405011.png" /></td> </tr></table>

<table class="eq" style="width:100%;"> <tr><td valign="top" style="width:94%;text-align:center;"><img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/a/a014/a014050/a01405012.png" /></td> </tr></table>

Initialized automata are subject to the additional requirement that <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/a/a014/a014050/a01405013.png" /> maps the initial state to the initial state. The automata <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/a/a014/a014050/a01405014.png" /> and <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/a/a014/a014050/a01405015.png" /> are said to be homomorphic if there exists a homomorphism <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/a/a014/a014050/a01405016.png" /> of automata mapping <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/a/a014/a014050/a01405017.png" /> into <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/a/a014/a014050/a01405018.png" />. If, in addition, <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/a/a014/a014050/a01405019.png" /> is one-to-one, <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/a/a014/a014050/a01405020.png" /> is called an isomorphism, and the automata <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/a/a014/a014050/a01405021.png" /> and <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/a/a014/a014050/a01405022.png" /> are said to be isomorphic automata. If the alphabets <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/a/a014/a014050/a01405023.png" /> and <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/a/a014/a014050/a01405024.png" />, and also the alphabets <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/a/a014/a014050/a01405025.png" /> and <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/a/a014/a014050/a01405026.png" />, are identical and the mappings <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/a/a014/a014050/a01405027.png" /> and <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/a/a014/a014050/a01405028.png" /> are the identity mappings, the homomorphism (isomorphism) <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/a/a014/a014050/a01405029.png" /> 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|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====
<table><TR><TD valign="top">[1]</TD> <TD valign="top">  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</TD></TR></table>