Namespaces
Variants
Actions

Automata, homomorphism of

From Encyclopedia of Mathematics
Revision as of 18:49, 5 April 2020 by Ulf Rehmann (talk | contribs) (tex encoded by computer)
(diff) ← Older revision | Latest revision (diff) | Newer revision → (diff)
Jump to: navigation, search


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
How to Cite This Entry:
Automata, homomorphism of. Encyclopedia of Mathematics. URL: http://encyclopediaofmath.org/index.php?title=Automata,_homomorphism_of&oldid=45251
This article was adapted from an original article by A.A. Letichevskii (originator), which appeared in Encyclopedia of Mathematics - ISBN 1402006098. See original article