View source for 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|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|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 <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/a/a014/a014130/a0141301.png" />, which transforms the output signals of the automaton <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/a/a014/a014130/a0141302.png" /> under consideration to input signals for <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/a/a014/a014130/a0141303.png" />. Thus, it may be assumed that the automaton <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/a/a014/a014130/a0141304.png" /> in the random medium <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/a/a014/a014130/a0141305.png" /> is an autonomous logical network, constructed out of the automata <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/a/a014/a014130/a0141306.png" /> and <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/a/a014/a014130/a0141307.png" /> by connecting the output of each automaton with the input of the other. The behaviour of the automaton <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/a/a014/a014130/a0141308.png" /> in the random medium <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/a/a014/a014130/a0141309.png" /> may then be regarded as the functioning of this autonomous logical network. The medium <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/a/a014/a014130/a01413010.png" /> is said to be stationary if it is a single-state automaton. If the output signals of the automaton <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/a/a014/a014130/a01413011.png" /> are regarded as  "rewards"  or  "punishments"  for the automaton <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/a/a014/a014130/a01413012.png" />, the natural problem arises of how to construct an automaton <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/a/a014/a014130/a01413013.png" /> whose behaviour in the medium <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/a/a014/a014130/a01413014.png" /> 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 <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/a/a014/a014130/a01413015.png" /> consists of the letters 0 and 1 and that, as a response to the output signals <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/a/a014/a014130/a01413016.png" /> of the automaton <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/a/a014/a014130/a01413017.png" />, the letter 1 is put out, respectively, with probabilities <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/a/a014/a014130/a01413018.png" />. Only the letter 1 is considered to be the  "reward"  of the automaton <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/a/a014/a014130/a01413019.png" />.

If the medium <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/a/a014/a014130/a01413020.png" /> is stationary, the set of states of the autonomous logical network becomes identical with the set of states of the automaton <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/a/a014/a014130/a01413021.png" />. If, in addition, the output letter of the automaton <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/a/a014/a014130/a01413022.png" /> is unambiguously determined by its state, the functioning of this logical network may be described by a stochastic matrix <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/a/a014/a014130/a01413023.png" /> of state transitions. The case which is usually considered is that of an ergodic matrix (cf. [[Ergodicity|Ergodicity]]). Then the function

<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/a014130/a01413024.png" /></td> </tr></table>

is defined, where <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/a/a014/a014130/a01413025.png" /> is the sum of the final probabilities of all the states which determine the output letter <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/a/a014/a014130/a01413026.png" />. Then

<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/a014130/a01413027.png" /></td> </tr></table>

If the output signals of the automaton <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/a/a014/a014130/a01413028.png" /> do not depend on the effects of the medium and if they are equally probable, i.e. if <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/a/a014/a014130/a01413029.png" />, one has

<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/a014130/a01413030.png" /></td> </tr></table>

The function <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/a/a014/a014130/a01413031.png" /> is the mathematical expectation of a variable called the gain of the automaton <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/a/a014/a014130/a01413032.png" /> in the medium <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/a/a014/a014130/a01413033.png" />. One says that the behaviour of the automaton <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/a/a014/a014130/a01413034.png" /> in a medium <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/a/a014/a014130/a01413035.png" /> is goal-conforming if <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/a/a014/a014130/a01413036.png" />. 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 <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/a/a014/a014130/a01413037.png" /> such that the mathematical expectation of the gain of automaton <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/a/a014/a014130/a01413038.png" /> tends to the maximum possible gain in this medium, which is <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/a/a014/a014130/a01413039.png" /> as <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/a/a014/a014130/a01413040.png" /> increases. In the case here considered such a sequence is formed by so-called automata with linear tactics under the condition that <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/a/a014/a014130/a01413041.png" />. (An automaton <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/a/a014/a014130/a01413042.png" /> with a linear tactic, with an output alphabet of <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/a/a014/a014130/a01413043.png" /> letters, has <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/a/a014/a014130/a01413044.png" /> states <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/a/a014/a014130/a01413045.png" />, <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/a/a014/a014130/a01413046.png" />, <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/a/a014/a014130/a01413047.png" />, and the following transition function <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/a/a014/a014130/a01413048.png" /> and output function <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/a/a014/a014130/a01413049.png" />:

<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/a014130/a01413050.png" /></td> </tr></table>

<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/a014130/a01413051.png" /></td> </tr></table>

<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/a014130/a01413052.png" /></td> </tr></table>

<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/a014130/a01413053.png" /></td> </tr></table>

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



====Comments====
See the Editorial Comment to the article [[Automata, equivalence of|Automata, equivalence of]].