Namespaces
Variants
Actions

Difference between revisions of "Automaton, behaviour of an"

From Encyclopedia of Mathematics
Jump to: navigation, search
(Importing text file)
 
m (tex encoded by computer)
 
Line 1: Line 1:
 +
<!--
 +
a0141301.png
 +
$#A+1 = 53 n = 0
 +
$#C+1 = 53 : ~/encyclopedia/old_files/data/A014/A.0104130 Automaton, behaviour of an
 +
Automatically converted into TeX, above some diagnostics.
 +
Please remove this comment and the {{TEX|auto}} line below,
 +
if TeX found to be correct.
 +
-->
 +
 +
{{TEX|auto}}
 +
{{TEX|done}}
 +
 
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.
 
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" />.
+
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 <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
+
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|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>
+
$$
 +
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 <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
+
is defined, where $  \sigma _ {i} $
 +
is the sum of the final probabilities of all the states which determine the output letter $  b _ {i} $.  
 +
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>
+
$$
 +
\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 <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
+
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
  
<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>
+
$$
 +
W ( \mathfrak A, \mathfrak B )  = W _ {0}  =
 +
\frac{2}{k}
 +
\sum _ {i = 1 } ^ { k }  p _ {i} - 1 .
 +
$$
  
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" />:
+
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 $:
  
<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>
+
$$
 +
\phi ( s _ {ij} , 1 )  = s _ {i, j + 1 }  ,\  \textrm{ if }
 +
j = 1 \dots n - 1,
 +
$$
  
<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>
+
$$
 +
\phi ( s _ {in} , 1 )  = s _ {in} ,\  \phi ( s _ {ij} , 0 )  = s _ {i, j - 1 }  ,\  \textrm{ if }  j = 2 \dots n,
 +
$$
  
<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>
+
$$
 +
\phi ( s _ {i1} , 0 = s _ {i + 1, 1 }  ,\  \psi ( s _ {ij} , a )  =  b _ {i} ,
 +
$$
  
<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>
+
$$
 +
= 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 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.
Line 31: Line 108:
 
====References====
 
====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>
 
<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====
 
====Comments====
 
See the Editorial Comment to the article [[Automata, equivalence of|Automata, equivalence of]].
 
See the Editorial Comment to the article [[Automata, equivalence of|Automata, equivalence of]].

Latest revision as of 10:01, 25 April 2020


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.

How to Cite This Entry:
Automaton, behaviour of an. Encyclopedia of Mathematics. URL: http://encyclopediaofmath.org/index.php?title=Automaton,_behaviour_of_an&oldid=15570
This article was adapted from an original article by V.B. KudryavtsevYu.I. Yanov (originator), which appeared in Encyclopedia of Mathematics - ISBN 1402006098. See original article