Automaton, behaviour of an

A mathematical concept describing the interaction of the automaton with its external environment. Thus, for a finite automaton (cf. Automaton, finite) the external environment usually is the set of input words, while its behaviour is the word function generated by the automaton or the event (sometimes the super-event) represented by it. For an automaton over terms (see Automata, algebraic theory of), the set of constant terms is the environment; its behaviour is the class of terms whose values, calculated using the automaton, belong to the isolated subset of elements of the corresponding algebra. For a mosaic structure the environment is the set of initial configurations, while its behaviour consists of the sequences of configurations generated at the various moments of the time set. In general, the concept of the behaviour of (more general) automata is similar to, or is essentially a slight modification of, the concept of the behaviour of finite automata.

The so-called behaviour of an automaton in a random medium is a special case. Here, "medium" is understood to mean a probabilistic automaton $ \mathfrak B $, which transforms the output signals of the automaton $ \mathfrak A $ under consideration to input signals for $ \mathfrak A $. Thus, it may be assumed that the automaton $ \mathfrak A $ in the random medium $ \mathfrak B $ is an autonomous logical network, constructed out of the automata $ \mathfrak A $ and $ \mathfrak B $ by connecting the output of each automaton with the input of the other. The behaviour of the automaton $ \mathfrak A $ in the random medium $ \mathfrak B $ may then be regarded as the functioning of this autonomous logical network. The medium $ \mathfrak B $ is said to be stationary if it is a single-state automaton. If the output signals of the automaton $ \mathfrak B $ are regarded as "rewards" or "punishments" for the automaton $ \mathfrak A $, the natural problem arises of how to construct an automaton $ \mathfrak A $ whose behaviour in the medium $ \mathfrak B $ would be optimal, i.e. would yield the highest possible gain in that medium. It is usually assumed that the output alphabet of the medium $ \mathfrak B $ consists of the letters 0 and 1 and that, as a response to the output signals $ b _ {1} \dots b _ {k} $ of the automaton $ \mathfrak A $, the letter 1 is put out, respectively, with probabilities $ p _ {1} \dots p _ {k} $. Only the letter 1 is considered to be the "reward" of the automaton $ \mathfrak A $.

If the medium $ \mathfrak B $ is stationary, the set of states of the autonomous logical network becomes identical with the set of states of the automaton $ \mathfrak A $. If, in addition, the output letter of the automaton $ \mathfrak A $ is unambiguously determined by its state, the functioning of this logical network may be described by a stochastic matrix $ Q $ of state transitions. The case which is usually considered is that of an ergodic matrix (cf. Ergodicity). Then the function

$$ W ( \mathfrak A , \mathfrak B ) = \sum _ {i=1 } ^ { k } \sigma _ {i} p _ {i} - \sum _ {i = 1 } ^ { k } \sigma _ {i} ( 1 - p _ {i} ) = \sum _ {i = 1 } ^ { k } \sigma _ {i} ( 2 p _ {i} - 1 ) $$

is defined, where $ \sigma _ {i} $ is the sum of the final probabilities of all the states which determine the output letter $ b _ {i} $. Then

$$ \mathop{\rm min} _ { i } ( 2 p _ {i} - 1 ) \leq W ( \mathfrak A, \mathfrak B ) \leq \ \max _ { i } ( 2 p _ {i} - 1 ). $$

If the output signals of the automaton $ \mathfrak A $ do not depend on the effects of the medium and if they are equally probable, i.e. if $ \sigma _ {1} = \dots = \sigma _ {k} = 1/k $, one has

$$ W ( \mathfrak A, \mathfrak B ) = W _ {0} = \frac{2}{k} \sum _ {i = 1 } ^ { k } p _ {i} - 1 . $$

The function $ W ( \mathfrak A , \mathfrak B) $ is the mathematical expectation of a variable called the gain of the automaton $ \mathfrak A $ in the medium $ \mathfrak B $. One says that the behaviour of the automaton $ \mathfrak A $ in a medium $ \mathfrak B $ is goal-conforming if $ W( \mathfrak A , \mathfrak B) > W _ {0} $. The problem of optimal behaviour in a random medium can now be stated as follows. One has to construct a so-called asymptotically optimal sequence of automata $ \mathfrak A _ {1} , \mathfrak A _ {2} \dots $ such that the mathematical expectation of the gain of automaton $ \mathfrak A _ {n} $ tends to the maximum possible gain in this medium, which is $ d _ \max = \max _ {i} \{ {2p _ {i} -1 } : { {}i = 1 \dots k } \} $ as $ n $ increases. In the case here considered such a sequence is formed by so-called automata with linear tactics under the condition that $ d _ \max \geq 1/2 $. (An automaton $ \mathfrak A _ {n} $ with a linear tactic, with an output alphabet of $ k $ letters, has $ kn $ states $ s _ {ij} $, $ i = 1 \dots k $, $ j = 1 \dots n $, and the following transition function $ \phi $ and output function $ \psi $:

$$ \phi ( s _ {ij} , 1 ) = s _ {i, j + 1 } ,\ \textrm{ if } j = 1 \dots n - 1, $$

$$ \phi ( s _ {in} , 1 ) = s _ {in} ,\ \phi ( s _ {ij} , 0 ) = s _ {i, j - 1 } ,\ \textrm{ if } j = 2 \dots n, $$

$$ \phi ( s _ {i1} , 0 ) = s _ {i + 1, 1 } ,\ \psi ( s _ {ij} , a ) = b _ {i} , $$

$$ i = 1 \dots k,\ j = 1 \dots n.) $$

The rules governing asymptotically optimal behaviour in a stationary random medium were first studied in mathematical statistics. However, the results obtained in that field can obviously be translated into the language of the theory of automata.

The behaviour of automata is also studied in more complex media, as is the behaviour of collectives of automata in random media. In the latter case the automata are considered to be players, and the rules of the game played by the automata are considered as the medium.

References

[1]	Ya.M. Barzdin', B.A. Trakhtenbrot, "Finite automata: behavior and synthesis" , North-Holland (1973) (Translated from Russian)
[2]	M.L. Tsetlin, "Studies on the theory of automata and modelling of biological systems" , Moscow (1969) (In Russian)
[3]	H. Robbins, "Sequential decision problems with a finite memory" Proc. Nat. Acad. Sci. USA , 42 : 12 (1956) pp. 920–923

Comments

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