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 is a tribasic algebra, i.e. an algebra with three sets of elements and and two operations and . On the other hand, a transition system , where is the input alphabet, is the set of states (cf. Automaton, finite) can be regarded as an algebra with unary operations, denoted by the letters of the input alphabet, such that . 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 of a semi-group of transformations of the set (under the composition operation), generated by the operations , so that for any arbitrary , from and from one puts

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

For any state the congruence is the maximal subcongruence of the relation

This means, in particular, that an event which can be represented by the initial acceptor is a union of certain -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 is said to be a linear automaton if and are linear spaces over some field ,

where are, respectively, linear mappings of into , into , into , and into . It is usually assumed that the field is finite, and that the spaces and 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