Difference between revisions of "Automata, homomorphism of"
(Importing text file) |
Ulf Rehmann (talk | contribs) m (tex encoded by computer) |
||
| Line 1: | Line 1: | ||
| − | + | <!-- | |
| + | a0140501.png | ||
| + | $#A+1 = 29 n = 0 | ||
| + | $#C+1 = 29 : ~/encyclopedia/old_files/data/A014/A.0104050 Automata, homomorphism of | ||
| + | Automatically converted into TeX, above some diagnostics. | ||
| + | Please remove this comment and the {{TEX|auto}} line below, | ||
| + | if TeX found to be correct. | ||
| + | --> | ||
| − | + | {{TEX|auto}} | |
| + | {{TEX|done}} | ||
| − | + | 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|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} $: | ||
| − | Initialized automata are subject to the additional requirement that | + | $$ |
| + | 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|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. | The concept of a homomorphism of automata is used in the context of problems concerning minimization, decomposition and completeness of automata, among others. | ||
Latest revision as of 18:49, 5 April 2020
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 |
Automata, homomorphism of. Encyclopedia of Mathematics. URL: http://encyclopediaofmath.org/index.php?title=Automata,_homomorphism_of&oldid=12330