Difference between revisions of "Automata, experiments with"
(→References: Conway (1971)) |
Ulf Rehmann (talk | contribs) m (tex encoded by computer) |
||
| Line 1: | Line 1: | ||
| + | <!-- | ||
| + | a0140401.png | ||
| + | $#A+1 = 70 n = 0 | ||
| + | $#C+1 = 70 : ~/encyclopedia/old_files/data/A014/A.0104040 Automata, experiments with | ||
| + | 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 method of obtaining information about the internal structure of an automaton from its behaviour as can be deduced from external experiments (that is, experiments where input words are fed into an automaton, the corresponding sequence of output words is examined and conclusions are drawn on the basis of these observations). | A method of obtaining information about the internal structure of an automaton from its behaviour as can be deduced from external experiments (that is, experiments where input words are fed into an automaton, the corresponding sequence of output words is examined and conclusions are drawn on the basis of these observations). | ||
| Line 13: | Line 25: | ||
5) The problem of identifying an automaton from a given class (deciphering). Knowing that the automaton, viewed as a "black box" , belongs to a given set, it is required to find out which element the automaton is. | 5) The problem of identifying an automaton from a given class (deciphering). Knowing that the automaton, viewed as a "black box" , belongs to a given set, it is required to find out which element the automaton is. | ||
| − | Let | + | Let $ \mathfrak A $ |
| + | be a class of initialized automata with input alphabet $ X $ | ||
| + | and output alphabet $ Y $. | ||
| + | Next, let $ X ^ {*} $ | ||
| + | be the collection of all words in $ X $, | ||
| + | let $ \alpha \in X ^ {*} $ | ||
| + | and let $ A \subseteq \mathfrak A $. | ||
| + | An experiment with the automaton $ A $ | ||
| + | is a set $ [ \alpha , A ] $ | ||
| + | of all pairs of the form $ ( x , y ) $ | ||
| + | such that $ x \subset \alpha $ | ||
| + | and $ y $ | ||
| + | is a word into which $ A $ | ||
| + | produces $ x $. | ||
==The classification of experiments.== | ==The classification of experiments.== | ||
The following types of experiments are usually considered: | The following types of experiments are usually considered: | ||
| − | 1) A simple unconditional experiment — a set | + | 1) A simple unconditional experiment — a set $ [ \alpha , A ] $, |
| + | where $ \alpha $ | ||
| + | consists of a single word. In the process of experimenting the single element $ \alpha $ | ||
| + | is fed into the input of the automaton and the resulting output is some word from $ Y ^ {*} $. | ||
| − | 2) A simple conditional experiment — a set | + | 2) A simple conditional experiment — a set $ [ \alpha , A ] $, |
| + | where $ \alpha $ | ||
| + | consists of a single word $ X = ( X (1) \dots X ( \tau ) ) $ | ||
| + | and where for any $ j \in \{ 1 \dots \tau \} $ | ||
| + | the values $ X (j) $ | ||
| + | depend on $ [ \alpha ^ \prime , A ] $, | ||
| + | $ \alpha ^ \prime = ( X (1) \dots X ( j - 1 ) ) $. | ||
| + | Thus, in the process of experimenting with automata every subsequent letter of the input word depends on the output word obtained earlier. | ||
| − | 3) A multiple unconditional experiment — a generalization of a simple unconditional experiment to the case when the set | + | 3) A multiple unconditional experiment — a generalization of a simple unconditional experiment to the case when the set $ [ \alpha , A ] $ |
| + | is such that $ \alpha $ | ||
| + | consists of more than one word. It is usually assumed that in the process of execution of the given experiment there is more than one specimen of the automaton $ A $, | ||
| + | or that the automaton can be reset in its initial state. | ||
| − | 4) A multiple conditional experiment — a generalization of a simple conditional experiment to the case when the set | + | 4) A multiple conditional experiment — a generalization of a simple conditional experiment to the case when the set $ [ \alpha , A ] $ |
| + | is such that $ \alpha $ | ||
| + | consists of more than one word: | ||
| − | + | $$ | |
| + | \alpha = \{ ( X _ {1} (1) \dots X _ {1} ( \tau _ {1} ) ) \dots | ||
| + | ( X _ {s} (1) \dots X _ {s} ( \tau _ {s} ) ) \} . | ||
| + | $$ | ||
| − | Moreover, two possibilities can be distinguished here: a) for any | + | Moreover, two possibilities can be distinguished here: a) for any $ i \in \{ 1 \dots s \} $ |
| + | and $ j \in \{ 1 \dots \tau _ {i} \} $ | ||
| + | the value of $ X _ {i} (j) $ | ||
| + | depends only on $ [ \alpha ^ \prime , A ] $, | ||
| + | where $ \alpha ^ \prime $ | ||
| + | consists of the single word $ ( X _ {i} (1) \dots X _ {i} ( j - 1 ) ) $; | ||
| + | or b) for any $ i \in \{ 1 \dots s \} $ | ||
| + | and $ j \in \{ 1 \dots \tau _ {i} \} $ | ||
| + | the value of $ X _ {i} (j) $ | ||
| + | depends on $ [ \alpha ^ {\prime\prime} , A ] $, | ||
| + | where $ \alpha ^ {\prime\prime} $ | ||
| + | is the set consisting of the collections $ \{ ( X _ {1} (1) \dots X _ {1} ( t _ {j} ^ {1} ) ) \dots ( X _ {s} (1) \dots X _ {s} ( t _ {j} ^ {s} )) \} $ | ||
| + | and the index $ t _ {j} ^ {i} $ | ||
| + | for $ i \in \{ 1 \dots s \} $ | ||
| + | coincides with $ \tau _ {i} $ | ||
| + | if $ j -1 > \tau _ {i} $ | ||
| + | or with $ j - 1 $ | ||
| + | if $ j - 1 \leq \tau _ {i} $. | ||
==Measures of the complexity of experiments.== | ==Measures of the complexity of experiments.== | ||
| Line 34: | Line 94: | ||
===Some results.=== | ===Some results.=== | ||
| − | A Moore automaton | + | A Moore automaton $ A $ |
| + | with $ r $ | ||
| + | states, $ m $ | ||
| + | input and $ p $ | ||
| + | output symbols is called an $ ( r , m , p ) $- | ||
| + | automaton. The following theorem on the distinguishability of states by a simple experiment holds: If $ A $ | ||
| + | is an $ ( r , m , p ) $- | ||
| + | automaton with all states distinct, then the distinguishability of any two states can be established by means of a simple experiment of length $ r - 1 $, | ||
| + | and the bound $ r - 1 $ | ||
| + | cannot be lowered (see [[#References|[4]]]). | ||
| − | The problem of determining the initial state of an automaton can be solved by means of a simple unconditional experiment of length | + | The problem of determining the initial state of an automaton can be solved by means of a simple unconditional experiment of length $ \lambda $, |
| + | where | ||
| − | < | + | $$ |
| + | 3 ^ {r ( 1 + \epsilon _ {1} ) / 6 } \leq \lambda | ||
| + | < 3 ^ {r ( 1 + \epsilon _ {2} ) / 6 } \ \ | ||
| + | ( \epsilon _ {1} , \epsilon _ {2} \rightarrow 0 \ | ||
| + | \textrm{ as } r \rightarrow \infty ) . | ||
| + | $$ | ||
| − | Adjustment for an automaton with | + | Adjustment for an automaton with $ r $ |
| + | states of which $ k $ | ||
| + | are admissible can always be solved by means of a simple unconditional experiment of length $ \lambda $, | ||
| + | where $ \lambda \leq ( 2 r - k ) ( k - 1 ) / 2 $, | ||
| + | and this bound cannot be improved. | ||
| − | As a rule, the above estimates are exact only for a small number of automata. It has been established (see [[#References|[4]]]) that the problem of determining the initial state for almost-all | + | As a rule, the above estimates are exact only for a small number of automata. It has been established (see [[#References|[4]]]) that the problem of determining the initial state for almost-all $ ( r , m , p ) $- |
| + | automata with two admissible states can be solved by means of a simple unconditional experiment of length $ \lambda $, | ||
| + | where $ \lambda \leq \mathop{\rm log} _ {m} \mathop{\rm log} _ {p} r + 4 $, | ||
| + | and the adjustment problem for almost-all $ ( r , m , p ) $- | ||
| + | automata by means of a simple unconditional experiment of length $ \lambda $, | ||
| + | where $ \lambda < 5 \mathop{\rm log} _ {p} r $. | ||
There is no algorithm that would permit the decyphering of initialized Mealy automata with unknown number of states. However, it turns out that a great part of such automata can nevertheless be decyphered. | There is no algorithm that would permit the decyphering of initialized Mealy automata with unknown number of states. However, it turns out that a great part of such automata can nevertheless be decyphered. | ||
Latest revision as of 18:49, 5 April 2020
A method of obtaining information about the internal structure of an automaton from its behaviour as can be deduced from external experiments (that is, experiments where input words are fed into an automaton, the corresponding sequence of output words is examined and conclusions are drawn on the basis of these observations).
Experiments with automata can be used to seek approaches to the solution of the following problems:
1) Given that an automaton is in an initial state it is required to determine this state.
2) The construction of an experiment that transfers an automaton from any state to some pre-assigned state (the adjustment problem).
3) The verification of the correct functioning of an automaton. It is required to find out by means of an experiment if a given automaton functions correctly.
4) The diagnostic of an automaton. It is required to find out not only if an automaton is in good working order, but also what kind of malfunction occurs.
5) The problem of identifying an automaton from a given class (deciphering). Knowing that the automaton, viewed as a "black box" , belongs to a given set, it is required to find out which element the automaton is.
Let $ \mathfrak A $ be a class of initialized automata with input alphabet $ X $ and output alphabet $ Y $. Next, let $ X ^ {*} $ be the collection of all words in $ X $, let $ \alpha \in X ^ {*} $ and let $ A \subseteq \mathfrak A $. An experiment with the automaton $ A $ is a set $ [ \alpha , A ] $ of all pairs of the form $ ( x , y ) $ such that $ x \subset \alpha $ and $ y $ is a word into which $ A $ produces $ x $.
The classification of experiments.
The following types of experiments are usually considered:
1) A simple unconditional experiment — a set $ [ \alpha , A ] $, where $ \alpha $ consists of a single word. In the process of experimenting the single element $ \alpha $ is fed into the input of the automaton and the resulting output is some word from $ Y ^ {*} $.
2) A simple conditional experiment — a set $ [ \alpha , A ] $, where $ \alpha $ consists of a single word $ X = ( X (1) \dots X ( \tau ) ) $ and where for any $ j \in \{ 1 \dots \tau \} $ the values $ X (j) $ depend on $ [ \alpha ^ \prime , A ] $, $ \alpha ^ \prime = ( X (1) \dots X ( j - 1 ) ) $. Thus, in the process of experimenting with automata every subsequent letter of the input word depends on the output word obtained earlier.
3) A multiple unconditional experiment — a generalization of a simple unconditional experiment to the case when the set $ [ \alpha , A ] $ is such that $ \alpha $ consists of more than one word. It is usually assumed that in the process of execution of the given experiment there is more than one specimen of the automaton $ A $, or that the automaton can be reset in its initial state.
4) A multiple conditional experiment — a generalization of a simple conditional experiment to the case when the set $ [ \alpha , A ] $ is such that $ \alpha $ consists of more than one word:
$$ \alpha = \{ ( X _ {1} (1) \dots X _ {1} ( \tau _ {1} ) ) \dots ( X _ {s} (1) \dots X _ {s} ( \tau _ {s} ) ) \} . $$
Moreover, two possibilities can be distinguished here: a) for any $ i \in \{ 1 \dots s \} $ and $ j \in \{ 1 \dots \tau _ {i} \} $ the value of $ X _ {i} (j) $ depends only on $ [ \alpha ^ \prime , A ] $, where $ \alpha ^ \prime $ consists of the single word $ ( X _ {i} (1) \dots X _ {i} ( j - 1 ) ) $; or b) for any $ i \in \{ 1 \dots s \} $ and $ j \in \{ 1 \dots \tau _ {i} \} $ the value of $ X _ {i} (j) $ depends on $ [ \alpha ^ {\prime\prime} , A ] $, where $ \alpha ^ {\prime\prime} $ is the set consisting of the collections $ \{ ( X _ {1} (1) \dots X _ {1} ( t _ {j} ^ {1} ) ) \dots ( X _ {s} (1) \dots X _ {s} ( t _ {j} ^ {s} )) \} $ and the index $ t _ {j} ^ {i} $ for $ i \in \{ 1 \dots s \} $ coincides with $ \tau _ {i} $ if $ j -1 > \tau _ {i} $ or with $ j - 1 $ if $ j - 1 \leq \tau _ {i} $.
Measures of the complexity of experiments.
These are some numerical characteristics that estimate the degree of complexity of an experiment. For a multiple experiment the usual measures of complexity are the height of the experiment — the number of symbols of the largest input word, the multiplicity — the number of input words, and the length — the total number of symbols in all the input words. It is considered that the measure of complexity of a simple experiment is its length (the number of symbols of the input word used).
Some results.
A Moore automaton $ A $ with $ r $ states, $ m $ input and $ p $ output symbols is called an $ ( r , m , p ) $- automaton. The following theorem on the distinguishability of states by a simple experiment holds: If $ A $ is an $ ( r , m , p ) $- automaton with all states distinct, then the distinguishability of any two states can be established by means of a simple experiment of length $ r - 1 $, and the bound $ r - 1 $ cannot be lowered (see [4]).
The problem of determining the initial state of an automaton can be solved by means of a simple unconditional experiment of length $ \lambda $, where
$$ 3 ^ {r ( 1 + \epsilon _ {1} ) / 6 } \leq \lambda < 3 ^ {r ( 1 + \epsilon _ {2} ) / 6 } \ \ ( \epsilon _ {1} , \epsilon _ {2} \rightarrow 0 \ \textrm{ as } r \rightarrow \infty ) . $$
Adjustment for an automaton with $ r $ states of which $ k $ are admissible can always be solved by means of a simple unconditional experiment of length $ \lambda $, where $ \lambda \leq ( 2 r - k ) ( k - 1 ) / 2 $, and this bound cannot be improved.
As a rule, the above estimates are exact only for a small number of automata. It has been established (see [4]) that the problem of determining the initial state for almost-all $ ( r , m , p ) $- automata with two admissible states can be solved by means of a simple unconditional experiment of length $ \lambda $, where $ \lambda \leq \mathop{\rm log} _ {m} \mathop{\rm log} _ {p} r + 4 $, and the adjustment problem for almost-all $ ( r , m , p ) $- automata by means of a simple unconditional experiment of length $ \lambda $, where $ \lambda < 5 \mathop{\rm log} _ {p} r $.
There is no algorithm that would permit the decyphering of initialized Mealy automata with unknown number of states. However, it turns out that a great part of such automata can nevertheless be decyphered.
Experiments with automata are also used as tools for the control of the functioning of automata. A unified approach has been developed to problems of control of automata, which makes it possible to indicate fundamental methods for their solution. An effective algorithm has been constructed for finding all dead-end multiple experiments for various automata (see [2]).
References
| [1] | E.F. Moore, "Gedanken-experiments on sequential machines" C.E. Shannon (ed.) J. McCarthy (ed.) , Automata studies , Princeton Univ. Press (1956) pp. 179–210 |
| [2] | S.V. Yablonskii, "Mathematical logic, theory of algorithms and theory of sets" Trudy Mat. Inst. Steklov. , 133 pp. 263–272 (In Russian) |
| [3] | B.A. Trakhtenbrot, Ya.M. Bardzdin', "Finite automata. Behaviour and synthesis" , North-Holland (1973) |
| [4] | T.N. Hibbard, "Lower upper bounds on minimal terminal state experiments for two classes of sequential machines" J. Assoc. Comput. Mach. , 8 : 4 (1961) pp. 601–612 |
References
| [a1] | John H. Conway, Regular Algebra and Finite Machines, Chapman & Hall (1971) |
Automata, experiments with. Encyclopedia of Mathematics. URL: http://encyclopediaofmath.org/index.php?title=Automata,_experiments_with&oldid=45250