Automaton

A control system, which is usually understood to mean a finite automaton (cf. Automaton, finite) or one of its modifications obtained by changing components or the mode of operation. The principal concept — a finite automaton — originated in the mid-20th century in connection with attempts to describe, in mathematical language, the functioning of nervous systems, of universal computers and of other real automata. The first such efforts are due to W. McCulloch and W. Pitts (1943), S.C. Kleene (1951), A.W. Burks and J. Wright (1954), and others. A characteristic feature of such a description is the discrete character of the corresponding mathematical models and the finiteness of the domain of their parameter values, which accounts for the name "finite" automaton. The external effects, reactions and states are considered to be letters of three alphabets named, respectively, the input alphabet, the output alphabet and the alphabet of states. The relations governing their interactions may then be given by two functions — a transition function and an output function — which map the pair "state-input letter" into "state letter" and the pair "state-output letter" into "output letter" , respectively. At each discrete moment of time the system, being in a given state, receives an input signal (a letter of the input alphabet), emits an output signal (a letter of the output alphabet, determined by the output function) and passes into a new state determined by the transition function. Studies of finite automata are supplemented by studies of their various generalizations and modifications which reflect various features of real systems. In the case of a finite automaton $ (A, S, B, \phi , \psi ) $ the existing modifications may be subdivided into the following three main groups. The first group includes automata some alphabets $ A, S $ or $ B $ of which are infinite, and such automata are said to be infinite. The second group includes automata in which the functions $ \psi $ and $ \phi $ are replaced by arbitrary relationships or by random functions. These are partial, non-deterministic, probabilistic and other automata. The third group includes automata with specific sets of input objects. These are automata with a variable structure, automata over terms (or tree automata, cf. Automata, algebraic theory of). There are automata belonging to several groups at the same time, e.g. fuzzy automata belong to all three groups. Special subclasses of finite automata are very important; these include, for instance, memoryless automata, autonomous automata, reversible automata, etc. In addition, the use of concepts and methods of other branches of mathematics also generates specific classes of automata and related problems. For instance, if algebraic methods are employed there result the concepts of automata over terms, as well as linear, group, free and other automata (cf. Automata, algebraic theory of); problems in coding theory generate the concepts of self-regulating automata, reversible automata, etc. (cf. Automaton, probabilistic). Structural automata also have several generalizations, mainly consisting in permitting infinite networks and altering the interconnections between the elements during the operation. This leads to the concept of a growing automaton. The principal modifications and subclasses of finite automata, together with their most important properties, are described below.

Macro approach.

1) Infinite automata (first group) differ from finite automata only by the fact that their alphabets $ A, B $ or $ S $( input, output and set of states) may be infinite. Most concepts and problems connected with finite automata are naturally extended to infinite automata. Alphabets of higher cardinality extend the computational capacities of automata. For instance, while finite automata realize finitely-determined (sequential) functions (cf. Finitely-determined function), infinite automata may be used to realize any determined function. Moreover, using infinite automata it is possible to describe the functioning of any automaton and machine. At the same time, this very general nature of infinite automata impairs their significance, so that most studies concern only special subclasses of infinite automata, connected with specific models of control systems.

2) Non-deterministic and asynchronous automata (second group). A non-deterministic automaton is formally defined as a system $ (A, S, B, \chi ) $, where $ A, S $ and $ B $ are alphabets in the sense explained above, while $ \chi \subseteq S \times A \times S \times B $ is a transition-to-output relation. If the relation $ \chi $ is a function mapping $ S \times A $ into $ S \times B $, the non-deterministic automaton is called a deterministic automaton and is in fact identical with a finite automaton, since in such a case $ \chi $ may be considered as the pair of functions $ \phi , \psi $ which map $ S \times A $ into $ S $ and $ B $, respectively. As distinct from a finite automaton, an initialized non-deterministic automaton $ \mathfrak A _ {S _ {1} } $ has several initial states, which form a subset $ S _ {1} $ of the set $ S $. The behaviour of $ \mathfrak A _ {S _ {1} } $ is usually understood to mean one of the following generalizations of the behaviour of a finite automaton.

a) Instead of a function $ f $, an automaton $ \mathfrak A _ {S _ {1} } $ realizes a relation $ f ^ { \prime } $, consisting of all pairs of words $ ( a _ {1} \dots a _ {n} , b _ {1} \dots b _ {n} ) \in A ^ {*} \times B ^ {*} $ such that there are states $ s _ {1} \dots s _ {n+1} $, for which $ s _ {1} \in S _ {1} $ and $ (s _ {i} a _ {i} s _ {i+1} b _ {i} ) \in \chi $ is true for any $ i = 1 \dots n $. The class of relations realized by initialized non-deterministic automata coincides with the class of finitely-determined relations (cf. Finitely-determined function).

b) An initialized non-deterministic automaton $ \mathfrak A _ {S _ {1} } $ in which a set $ S ^ { \prime } $ of final states has been indicated, while the alphabet $ B $ is empty (i.e. $ \chi \subseteq S \times A \times S $), represents the event $ L _ {S} ^ \prime $ consisting of all words $ a _ {1} \dots a _ {n} \in A ^ {*} $ such that there are states $ s _ {1} \dots s _ {n+1} $ for which $ s _ {1} \in S _ {1} $, $ s _ {n+1} \in S ^ { \prime } $ and $ ( s _ {i} a _ {i} s _ {i+1} ) \in \chi $ is true for any $ i = 1 \dots n $. The class of events that can be represented by the automaton $ \mathfrak A _ {S _ {1} } $ is identical with the class of regular events, i.e. with respect to these aspects of their behaviour non-deterministic automata are equivalent to finite automata. However, the highly general nature of the concept of a non-deterministic automaton is reflected in the fact that a different number of states may be necessary to represent the same event using a non-deterministic automaton and using a finite automaton. There are events which are representable by a non-deterministic automaton with $ m $ states and by a finite automaton with $ 2 ^ {m} $ states, but not by any finite automaton with a smaller number of states.

A special subclass of non-deterministic automata is formed by the so-called partial automata, in which the relation $ \chi $ is a partial function mapping the set $ S \times A $ into $ S \times B $, and which realize partial finitely-determined functions.

The term "asynchronous automaton" usually denotes one of the two following types of automata. The first type comprises automata of type $ ( A, S, B, \phi , \psi ) $, in which the output function $ \psi $ maps the set $ S \times A $ into $ B ^ {*} $( for a finite automaton $ \psi $ maps $ S \times A $ into $ B $). These automata are mainly used in coding theory. The second type comprises finite automata whose transition function $ \phi $ has the following property: $ \phi (s, aa) = \phi (s, a) $ for all $ s $ and $ a $. These automata are used in coding theory and also in modelling certain systems in technology and biology.

3) Automata with a variable structure (third group) are finite automata $ \mathfrak A = (A \times A, S, B, \phi , \psi ) $ with two input channels, together with some fixed infinite sequence $ \alpha $( a superword) in the alphabet $ A $. Arbitrary words in the alphabet $ A $ are sent to the first input (channel) of such an automaton, while initial segments of the same length of the sequence $ \alpha $ are sent to the second input (channel). This imposes a restriction on the set of pairs of input words. If the automaton with a variable structure is considered as an automaton having only the first input (into which any word of $ A $ can be fed), its transition and its output functions will depend on the length of the input word which was fed in. In its behaviour, an automaton with a variable structure is equivalent to an infinite automaton with finite input and output alphabets and with a countable set of states.

4) Fuzzy automata constitute a generalization of the concept of a finite automaton, obtained by replacing the transition and output functions by fuzzy relations. A fuzzy subset of a set $ M $ is defined as a function which maps $ M $ into the segment $ [0, 1] $. Accordingly, in a fuzzy automaton, the transition and the output functions are replaced by functions mapping the sets $ S \times A \times S $ and $ S \times A \times B $ into $ [0, 1] $, where $ S $ is the set of states, $ A $ is the input alphabet and $ B $ is the output alphabet. The basic concepts and problems typical of finite automata have natural generalizations to fuzzy automata; this applies, in particular, to the representation of fuzzy events and the realization of fuzzy relations. Fuzzy automata are mathematical models for certain recognition mechanisms, and are used in pattern recognition.

5) Special classes of finite automata.

Automata without memory are single-state finite automata or automata equivalent to them. In such automata each output letter is fully determined by the input letter which is fed in at that moment. Such automata are frequently referred to as functional elements and are extensively used in problems of synthesis of automata.

Automata with a finite storage space (or automata with a finite memory) are finite automata in which each output letter is fully determined by a bounded segment of the input word fed in during the preceding moments of time, irrespective of the initial state. For automata with a finite memory and with $ n $ states the length of such a segment does not exceed $ n(n - 1)/2 $, and this maximum value is in fact attained for some automata. Automata with a finite memory are called self-regulating if, at a given time $ t $, the output letter at any moment $ \tau \geq t $ is independent of the initial state. Such automata are used in coding theory (cf. Coding and decoding), and the modification of the automata usually employed in such cases satisfies the above condition not for the set of all input words, but only for some subset of this set. Automata with a finite memory are realized by logical networks without feedback.

Reverse automata or automata without loss of information are finite automata which realize one-to-one functions. Such automata are also used in coding theory.

Micro-approach.

There are three types of generalized structural automata, which may be considered as generalized logical networks: 1) generalized logical networks with a permanent structure, in which both the elements and the relation between them remain unchanged when the automaton is functioning; 2) generalized logical networks with a variable structure; and 3) generalized logical networks made of volume elements and connections. The main classes of such automata are described below.

1) Generalized logical networks with a permanent structure. These include mosaic structures and iterative networks, which are finite fragments of mosaic structures with a similar range of problems.

Mosaic structures are infinite unions of transition systems $ (A, S, \phi ) $( i.e. of finite automata of the type $ (A, S, S, \phi , \phi ) $, where the output function is identical with the transition function and the output alphabet is identical with the set of states). Such systems are placed at points with integer coordinates (integral points) of the $ n $- dimensional space, while for each such point there is defined a finite set of integral points, called its neighbourhood. The input alphabet of the transition system placed at a certain point is the Cartesian product of the sets of states of the transition systems placed at the points in its neighbourhood.

A mosaic structure may be regarded as an infinite automaton whose input and output alphabets as well as its set of states are equal and are the infinite Cartesian product of the sets of states of all the transition systems contained in it. This makes it possible to reduce many problems for mosaic structures to problems for infinite automata. Problems specific to mosaic structures include modelling of effective procedures; in particular, of computational processes. Mosaic structures in which arbitrary automata instead of transition systems are used are also occasionally considered.

Uniform structures form an important class of mosaic structures. If all the transition systems are identical and if the neighbourhood of any point is obtained by a parallel translation of a certain fixed neighbourhood, the mosaic structure is known as a uniform structure or a cellular automaton. It is usually assumed, in this context, that there is some "stable" state of the transitional system, which is preserved if the input word is a tuple each term of which corresponds to this state. Typical problems on uniform structures are problems of self-reproduction and the "Garden-of-Eden" problem.

At any moment the states of the transition systems located at points in an integral lattice generate a kind of spatial mosaic pattern, which is usually denoted as a configuration. A configuration containing only a finite set of transition systems whose states are unstable (the excited part) is called finite. The self-reproduction problem consists of finding out whether finite configurations exist that, during the operation of the uniform system, pass into configurations, whose excited part is the multiply iterated excited part of the original configuration. The "garden of EdenGarden of Eden" is a term denoting a configuration which cannot result from configurations different from itself. The "garden-of-Eden problemGarden-of-Eden problem" is to determine the existence of "Gardens of Eden" for a given uniform structure.

2) Generalized logical networks with a variable structure. There exist various types of such logical networks. The most general ones include mosaic structures in which both the neighbourhoods of the elements and the elements themselves vary during the operation. As an example of such a generalized logical network one may mention the one-dimensional structure simulating the functioning of a Turing machine with input. In this case one of the nodes of the one-dimensional network corresponds to the control mechanism, while the other nodes correspond to the tape cells, which are considered as transition systems in which the letters of the working alphabet of the Turing machine serve as the input letters and states. The commutation is determined by the position of the head.

Another type of generalized logical networks with a variable structure are the so-called growing automata. They are uniform structures whose excited part increases during the operation. There are a number of models of such automata, which simulate various features of real mechanisms.

3) Generalized logical networks of volume elements are distinguished by the fact that a certain volume is assigned to their elementary automata and their mutual connections. As a result there arises the problem of synthesis of automata with minimum possible volume.

The term "automaton" is also used in concepts such as two-sided, multi-tape, multi-headed, linearly bounded, etc., automata, which are in fact modifications of the Turing machine. Sometimes all abstract machines are included in the concept of automata.

References

[1]	W.S. McCulloch, W. Pitts, "A logical calculus of ideas immanent in nervous activity" Bull. Math. Biophys. , 5 (1943) pp. 115–133
[2]	S.C. Kleene, "Representation of events in nerve nets and finite automata" , Automata studies , 34 , Princeton Univ. Press (1956) pp. 3–41
[3]	A.W. Burks, J.B. Wright, "Sequence generators, graphs, and formal languages" Inform. and Control , 5 (1962) pp. 204–212
[4a]	V.M. Glushikov, "The abstract theory of automata" Russian Math. Surveys , 16 : 5 (1961) pp. 1–53 Uspekhi Mat. Nauk , 16 : 5 (1961) pp. 3–62
[4b]	V.M. Glushikov, Uspekhi Mat. Nauk , 17 : 2 (1962) pp. 270
[5]	M.O. Rabin, D. Scott, "Finite automata and their decision problems" IBM J. Res. Develop. , 3 (1959) pp. 114–125
[6]	L.A. Zadeh, "Probability measures of fuzzy events" J. Math. Anal. Appl. , 23 (1968) pp. 421–427
[7]	V.Z. Alad'ev, "On the theory of uniform structures" , Tallin (1972) (In Russian)

Comments

See the Editorial Comment to the article Automata, equivalence of.