Automata, algebraic theory of

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