Namespaces
Variants
Actions

Difference between revisions of "Automata, homomorphism of"

From Encyclopedia of Mathematics
Jump to: navigation, search
(Importing text file)
 
m (tex encoded by computer)
 
Line 1: Line 1:
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" />
+
<!--
 +
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.
 +
-->
  
<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>
+
{{TEX|auto}}
 +
{{TEX|done}}
  
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" />:
+
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} $
  
<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>
+
$$
 +
h _ {1} : A _ {1}  \rightarrow  A _ {2} ,\  h _ {2} : S _ {1}  \rightarrow  S _ {2} ,
 +
\  h _ {3} : B _ {1}  \rightarrow  B _ {2} ,
 +
$$
  
<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>
+
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 <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]]).
+
$$
 +
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
How to Cite This Entry:
Automata, homomorphism of. Encyclopedia of Mathematics. URL: http://encyclopediaofmath.org/index.php?title=Automata,_homomorphism_of&oldid=12330
This article was adapted from an original article by A.A. Letichevskii (originator), which appeared in Encyclopedia of Mathematics - ISBN 1402006098. See original article