Namespaces
Variants
Actions

Difference between revisions of "Automata, algebraic theory of"

From Encyclopedia of Mathematics
Jump to: navigation, search
(Importing text file)
 
m (tex encoded by computer)
 
Line 1: Line 1:
 +
<!--
 +
a0140001.png
 +
$#A+1 = 59 n = 0
 +
$#C+1 = 59 : ~/encyclopedia/old_files/data/A014/A.0104000 Automata, algebraic theory 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 branch of the theory of automata (cf. [[Automata, theory of|Automata, theory of]]) in which algebraic tools are employed in the study of automata. The algebraic theory of automata is based on the fact that automata can be regarded as special algebras or algebraic systems. In addition, events which are representable by finite automata form an algebra with respect to the operations of union, composition and iteration, generated by a finite set of so-called elementary events, each one of which consists of a one-letter or empty word. The algebraic approach makes it possible to utilize algebraic results in the theory of automata directly, and in certain cases aids in establishing a connection between the theory of automata and other branches of mathematics. E.g., the theory of automata was used to obtain a proof of the solvability of certain second-order arithmetical theories, and also to obtain a new, simpler solution of the [[Burnside problem|Burnside problem]].
 
A branch of the theory of automata (cf. [[Automata, theory of|Automata, theory of]]) in which algebraic tools are employed in the study of automata. The algebraic theory of automata is based on the fact that automata can be regarded as special algebras or algebraic systems. In addition, events which are representable by finite automata form an algebra with respect to the operations of union, composition and iteration, generated by a finite set of so-called elementary events, each one of which consists of a one-letter or empty word. The algebraic approach makes it possible to utilize algebraic results in the theory of automata directly, and in certain cases aids in establishing a connection between the theory of automata and other branches of mathematics. E.g., the theory of automata was used to obtain a proof of the solvability of certain second-order arithmetical theories, and also to obtain a new, simpler solution of the [[Burnside problem|Burnside problem]].
  
From the algebraic point of view, a finite or infinite automata <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/a/a014/a014000/a0140001.png" /> is a tribasic algebra, i.e. an algebra with three sets of elements <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/a/a014/a014000/a0140002.png" /> and <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/a/a014/a014000/a0140003.png" /> and two operations <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/a/a014/a014000/a0140004.png" /> and <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/a/a014/a014000/a0140005.png" />. On the other hand, a transition system <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/a/a014/a014000/a0140006.png" />, where <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/a/a014/a014000/a0140007.png" /> is the input alphabet, <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/a/a014/a014000/a0140008.png" /> is the set of states (cf. [[Automaton, finite|Automaton, finite]]) can be regarded as an algebra <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/a/a014/a014000/a0140009.png" /> with unary operations, denoted by the letters <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/a/a014/a014000/a01400010.png" /> of the input alphabet, such that <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/a/a014/a014000/a01400011.png" />. Concepts such as a homomorphism of automata (cf. [[Automata, homomorphism of|Automata, homomorphism of]]), an isomorphism, a sub-automaton, etc., as applied to automata, are thus naturally defined. This approach also permits the assignment to the automaton <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/a/a014/a014000/a01400012.png" /> of a semi-group of transformations of the set <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/a/a014/a014000/a01400013.png" /> (under the composition operation), generated by the operations <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/a/a014/a014000/a01400014.png" />, so that for any arbitrary <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/a/a014/a014000/a01400015.png" />, <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/a/a014/a014000/a01400016.png" /> from <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/a/a014/a014000/a01400017.png" /> and <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/a/a014/a014000/a01400018.png" /> from <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/a/a014/a014000/a01400019.png" /> one puts
+
From the algebraic point of view, a finite or infinite automata $  \mathfrak A = (A, S, B, \phi , \psi ) $
 +
is a tribasic algebra, i.e. an algebra with three sets of elements $  A, S $
 +
and $  B $
 +
and two operations $  \phi : S \times A \rightarrow S $
 +
and $  \psi : S \times A \rightarrow B $.  
 +
On the other hand, a transition system $  (A, S, \phi ) $,  
 +
where $  A = \{ a _ {1} \dots a _ {n} \} $
 +
is the input alphabet, $  S $
 +
is the set of states (cf. [[Automaton, finite|Automaton, finite]]) can be regarded as an algebra $  \langle  S, a _ {1} \dots a _ {n} \rangle $
 +
with unary operations, denoted by the letters a _ {i} $
 +
of the input alphabet, such that $  a _ {i} s _ {j} = \phi ( s _ {j} , a _ {i} ) $.  
 +
Concepts such as a homomorphism of automata (cf. [[Automata, homomorphism of|Automata, homomorphism of]]), an isomorphism, a sub-automaton, etc., as applied to automata, are thus naturally defined. This approach also permits the assignment to the automaton $  \mathfrak A = (A, S, B, \phi , \psi ) $
 +
of a semi-group of transformations of the set $  S $(
 +
under the composition operation), generated by the operations a _ {i} $,  
 +
so that for any arbitrary a _ {i} $,  
 +
a _ {j} $
 +
from $  A $
 +
and $  s $
 +
from $  S $
 +
one puts
  
<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/a014000/a01400020.png" /></td> </tr></table>
+
$$
 +
a _ {i} a _ {j} S  = \phi ( \phi ( s , a _ {i} ) , a _ {j} ).
 +
$$
  
This semi-group is known as the semi-group of the automaton <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/a/a014/a014000/a01400021.png" /> and is used as a means of describing certain properties of automata (classification, decomposability, isomorphism, etc.) in algebraic language. Also, to any semi-group <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/a/a014/a014000/a01400022.png" /> with a unit element there may be assigned an automaton with a given input alphabet <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/a/a014/a014000/a01400023.png" /> and a set of states <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/a/a014/a014000/a01400024.png" /> as follows. To each letter <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/a/a014/a014000/a01400025.png" /> of <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/a/a014/a014000/a01400026.png" /> is assigned some element <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/a/a014/a014000/a01400027.png" /> from <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/a/a014/a014000/a01400028.png" />, and the transition function is then defined as <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/a/a014/a014000/a01400029.png" />. The semi-group of such an automaton is isomorphic to the sub-semi-group of <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/a/a014/a014000/a01400030.png" /> generated by the elements <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/a/a014/a014000/a01400031.png" />, which means that if <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/a/a014/a014000/a01400032.png" /> are generators of <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/a/a014/a014000/a01400033.png" />, then the semi-group of the automaton is isomorphic to the original semi-group <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/a/a014/a014000/a01400034.png" />. The semi-group of an automaton is clearly isomorphic to a quotient semi-group of the input semi-group <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/a/a014/a014000/a01400035.png" /> of all words over the alphabet <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/a/a014/a014000/a01400036.png" /> with the operation of successive union (concatenation) of words according to the congruence
+
This semi-group is known as the semi-group of the automaton $  \mathfrak A $
 +
and is used as a means of describing certain properties of automata (classification, decomposability, isomorphism, etc.) in algebraic language. Also, to any semi-group $  Q $
 +
with a unit element there may be assigned an automaton with a given input alphabet $  A = \{ a _ {1} \dots a _ {n} \} $
 +
and a set of states $  Q $
 +
as follows. To each letter a _ {i} $
 +
of $  A $
 +
is assigned some element $  q _ {i} $
 +
from $  Q $,  
 +
and the transition function is then defined as $  \phi (q, a _ {i} ) = qq _ {i} $.  
 +
The semi-group of such an automaton is isomorphic to the sub-semi-group of $  Q $
 +
generated by the elements $  q _ {1} \dots q _ {n} $,  
 +
which means that if $  q _ {1} \dots q _ {n} $
 +
are generators of $  Q $,  
 +
then the semi-group of the automaton is isomorphic to the original semi-group $  Q $.  
 +
The semi-group of an automaton is clearly isomorphic to a quotient semi-group of the input semi-group $  A  ^ {*} $
 +
of all words over the alphabet $  A $
 +
with the operation of successive union (concatenation) of words according to the congruence
  
<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/a014000/a01400037.png" /></td> </tr></table>
+
$$
 +
= \{ {( \alpha , \beta ) } : {\alpha , \beta \in A  ^ {*}
 +
\textrm{ and  for  all  }  s \in S ( \phi ( s, \alpha ) = \phi ( s, \beta )) } \} .
 +
$$
  
For any state <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/a/a014/a014000/a01400038.png" /> the congruence <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/a/a014/a014000/a01400039.png" /> is the maximal subcongruence of the relation
+
For any state $  s \in S $
 +
the congruence $  R $
 +
is the maximal subcongruence of the relation
  
<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/a014000/a01400040.png" /></td> </tr></table>
+
$$
 +
R _ {s}  = \{ {( \alpha , \beta ) } : {\alpha , \beta \in A  ^ {*}
 +
\textrm{ and }  \phi ( s , \alpha ) = \phi ( s , \beta ) } \}
 +
.
 +
$$
  
This means, in particular, that an event which can be represented by the initial acceptor <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/a/a014/a014000/a01400041.png" /> is a union of certain <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/a/a014/a014000/a01400042.png" />-classes. Since the semi-group of an automaton characterizes it up to an isomorphism, various classes of semi-groups have their own classes of automata. If the semi-group of an automaton is free, Abelian, cyclic, nilpotent, etc., or is itself a group, the automaton is known, respectively, as a free, Abelian, cyclic, nilpotent or a group automaton; these last are also called permutation automata. Another approach, connected with the algebraic classification of transition and output functions, leads to the classes of linear, substitution and other automata (cf. [[Automaton|Automaton]]). Substitution automata realize one-to-one functions and are used in coding theory. Linear automata are of interest because of their simple structure.
+
This means, in particular, that an event which can be represented by the initial acceptor $  \mathfrak A _ {s} = (A, S, \phi , S ^ { \prime } ) $
 +
is a union of certain $  R $-
 +
classes. Since the semi-group of an automaton characterizes it up to an isomorphism, various classes of semi-groups have their own classes of automata. If the semi-group of an automaton is free, Abelian, cyclic, nilpotent, etc., or is itself a group, the automaton is known, respectively, as a free, Abelian, cyclic, nilpotent or a group automaton; these last are also called permutation automata. Another approach, connected with the algebraic classification of transition and output functions, leads to the classes of linear, substitution and other automata (cf. [[Automaton|Automaton]]). Substitution automata realize one-to-one functions and are used in coding theory. Linear automata are of interest because of their simple structure.
  
An automaton <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/a/a014/a014000/a01400043.png" /> is said to be a linear automaton if <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/a/a014/a014000/a01400044.png" /> and <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/a/a014/a014000/a01400045.png" /> are linear spaces over some field <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/a/a014/a014000/a01400046.png" />,
+
An automaton $  (A, S, B, \phi , \psi ) $
 +
is said to be a linear automaton if $  A, S $
 +
and $  B $
 +
are linear spaces over some field $  P $,
  
<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/a014000/a01400047.png" /></td> </tr></table>
+
$$
 +
\phi ( s , a )  = \phi _ {1} ( s ) + \phi _ {2} ( a ) ,\ \
 +
\psi ( s , a )  = \psi _ {1} ( s ) + \psi _ {2} ( a ) ,
 +
$$
  
where <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/a/a014/a014000/a01400048.png" /> are, respectively, linear mappings of <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/a/a014/a014000/a01400049.png" /> into <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/a/a014/a014000/a01400050.png" />, <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/a/a014/a014000/a01400051.png" /> into <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/a/a014/a014000/a01400052.png" />, <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/a/a014/a014000/a01400053.png" /> into <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/a/a014/a014000/a01400054.png" />, and <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/a/a014/a014000/a01400055.png" /> into <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/a/a014/a014000/a01400056.png" />. It is usually assumed that the field <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/a/a014/a014000/a01400057.png" /> is finite, and that the spaces <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/a/a014/a014000/a01400058.png" /> and <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/a/a014/a014000/a01400059.png" /> are finite-dimensional; in such a case a linear automaton is a finite automaton. If multiple operations are permitted in the representation of a finite acceptor as an algebra whose operations are letters of the input alphabet, the resulting generalization is known as an automaton over terms (automaton over trees; generalized automaton). Such automata are used to prove the solvability of certain second-order mathematical theories.
+
where $  \phi _ {1} , \phi _ {2} , \psi _ {1} , \psi _ {2} $
 +
are, respectively, linear mappings of $  S $
 +
into $  S $,  
 +
$  A $
 +
into $  S $,  
 +
$  S $
 +
into $  B $,  
 +
and $  A $
 +
into $  B $.  
 +
It is usually assumed that the field $  P $
 +
is finite, and that the spaces $  A, S $
 +
and $  B $
 +
are finite-dimensional; in such a case a linear automaton is a finite automaton. If multiple operations are permitted in the representation of a finite acceptor as an algebra whose operations are letters of the input alphabet, the resulting generalization is known as an automaton over terms (automaton over trees; generalized automaton). Such automata are used to prove the solvability of certain second-order mathematical theories.
  
 
See also the references to [[Automaton|Automaton]].
 
See also the references to [[Automaton|Automaton]].

Latest revision as of 18:48, 5 April 2020


A branch of the theory of automata (cf. Automata, theory of) in which algebraic tools are employed in the study of automata. The algebraic theory of automata is based on the fact that automata can be regarded as special algebras or algebraic systems. In addition, events which are representable by finite automata form an algebra with respect to the operations of union, composition and iteration, generated by a finite set of so-called elementary events, each one of which consists of a one-letter or empty word. The algebraic approach makes it possible to utilize algebraic results in the theory of automata directly, and in certain cases aids in establishing a connection between the theory of automata and other branches of mathematics. E.g., the theory of automata was used to obtain a proof of the solvability of certain second-order arithmetical theories, and also to obtain a new, simpler solution of the Burnside problem.

From the algebraic point of view, a finite or infinite automata $ \mathfrak A = (A, S, B, \phi , \psi ) $ is a tribasic algebra, i.e. an algebra with three sets of elements $ A, S $ and $ B $ and two operations $ \phi : S \times A \rightarrow S $ and $ \psi : S \times A \rightarrow B $. On the other hand, a transition system $ (A, S, \phi ) $, where $ A = \{ a _ {1} \dots a _ {n} \} $ is the input alphabet, $ S $ is the set of states (cf. Automaton, finite) can be regarded as an algebra $ \langle S, a _ {1} \dots a _ {n} \rangle $ with unary operations, denoted by the letters $ a _ {i} $ of the input alphabet, such that $ a _ {i} s _ {j} = \phi ( s _ {j} , a _ {i} ) $. Concepts such as a homomorphism of automata (cf. Automata, homomorphism of), an isomorphism, a sub-automaton, etc., as applied to automata, are thus naturally defined. This approach also permits the assignment to the automaton $ \mathfrak A = (A, S, B, \phi , \psi ) $ of a semi-group of transformations of the set $ S $( under the composition operation), generated by the operations $ a _ {i} $, so that for any arbitrary $ a _ {i} $, $ a _ {j} $ from $ A $ and $ s $ from $ S $ one puts

$$ a _ {i} a _ {j} S = \phi ( \phi ( s , a _ {i} ) , a _ {j} ). $$

This semi-group is known as the semi-group of the automaton $ \mathfrak A $ and is used as a means of describing certain properties of automata (classification, decomposability, isomorphism, etc.) in algebraic language. Also, to any semi-group $ Q $ with a unit element there may be assigned an automaton with a given input alphabet $ A = \{ a _ {1} \dots a _ {n} \} $ and a set of states $ Q $ as follows. To each letter $ a _ {i} $ of $ A $ is assigned some element $ q _ {i} $ from $ Q $, and the transition function is then defined as $ \phi (q, a _ {i} ) = qq _ {i} $. The semi-group of such an automaton is isomorphic to the sub-semi-group of $ Q $ generated by the elements $ q _ {1} \dots q _ {n} $, which means that if $ q _ {1} \dots q _ {n} $ are generators of $ Q $, then the semi-group of the automaton is isomorphic to the original semi-group $ Q $. The semi-group of an automaton is clearly isomorphic to a quotient semi-group of the input semi-group $ A ^ {*} $ of all words over the alphabet $ A $ with the operation of successive union (concatenation) of words according to the congruence

$$ R = \{ {( \alpha , \beta ) } : {\alpha , \beta \in A ^ {*} \textrm{ and for all } s \in S ( \phi ( s, \alpha ) = \phi ( s, \beta )) } \} . $$

For any state $ s \in S $ the congruence $ R $ is the maximal subcongruence of the relation

$$ R _ {s} = \{ {( \alpha , \beta ) } : {\alpha , \beta \in A ^ {*} \textrm{ and } \phi ( s , \alpha ) = \phi ( s , \beta ) } \} . $$

This means, in particular, that an event which can be represented by the initial acceptor $ \mathfrak A _ {s} = (A, S, \phi , S ^ { \prime } ) $ is a union of certain $ R $- classes. Since the semi-group of an automaton characterizes it up to an isomorphism, various classes of semi-groups have their own classes of automata. If the semi-group of an automaton is free, Abelian, cyclic, nilpotent, etc., or is itself a group, the automaton is known, respectively, as a free, Abelian, cyclic, nilpotent or a group automaton; these last are also called permutation automata. Another approach, connected with the algebraic classification of transition and output functions, leads to the classes of linear, substitution and other automata (cf. Automaton). Substitution automata realize one-to-one functions and are used in coding theory. Linear automata are of interest because of their simple structure.

An automaton $ (A, S, B, \phi , \psi ) $ is said to be a linear automaton if $ A, S $ and $ B $ are linear spaces over some field $ P $,

$$ \phi ( s , a ) = \phi _ {1} ( s ) + \phi _ {2} ( a ) ,\ \ \psi ( s , a ) = \psi _ {1} ( s ) + \psi _ {2} ( a ) , $$

where $ \phi _ {1} , \phi _ {2} , \psi _ {1} , \psi _ {2} $ are, respectively, linear mappings of $ S $ into $ S $, $ A $ into $ S $, $ S $ into $ B $, and $ A $ into $ B $. It is usually assumed that the field $ P $ is finite, and that the spaces $ A, S $ and $ B $ are finite-dimensional; in such a case a linear automaton is a finite automaton. If multiple operations are permitted in the representation of a finite acceptor as an algebra whose operations are letters of the input alphabet, the resulting generalization is known as an automaton over terms (automaton over trees; generalized automaton). Such automata are used to prove the solvability of certain second-order mathematical theories.

See also the references to Automaton.

References

[1] , The algebraic theory of automata, languages and semi-groups , Moscow (1975) (In Russian; translated from English)
[2] 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
[3] J.W. Thatcher, J.B. Wright, Kibernet. Sb. , 6 (1969) pp. 112–114
How to Cite This Entry:
Automata, algebraic theory of. Encyclopedia of Mathematics. URL: http://encyclopediaofmath.org/index.php?title=Automata,_algebraic_theory_of&oldid=45248
This article was adapted from an original article by V.B. KudryavtsevYu.I. Yanov (originator), which appeared in Encyclopedia of Mathematics - ISBN 1402006098. See original article