Abstract Generated abstract
This note studies the problem of recognizing the final state of a finite automaton treated as a black box, with particular attention to the length of the shortest homogeneous experiment. Building on earlier worst case bounds of Hibbard and on estimates involving the degree of distinguishability, it considers reduced Mealy, Moore, and permutation automata with fixed input and output alphabet sizes as the number of states grows. The main result shows that, for almost all automata in each of these classes, the shortest homogeneous experiment has length less than 5 log_n k, a substantially smaller asymptotic bound than the general quadratic estimates. For permutation automata, the result also yields a corresponding bound for homogeneous recognition of the initial state.
Full Text
UDC 519.95
MATHEMATICS
A. D. KORSHUNOV
ON AN UPPER BOUND FOR THE LENGTHS OF SHORTEST HOMOGENEOUS EXPERIMENTS FOR RECOGNIZING THE FINAL STATE FOR ALMOST ALL AUTOMATA
(Presented by Academician S. L. Sobolev on 29 IV 1968)
In the present note we consider the problem of recognizing the final state of an automaton \((^1)\), which consists of the following. Suppose that a completely specified noninitial automaton is given, described as a “black box,” and that the experimenter can obtain information about its states only by applying input letters and observing output letters. On the basis of these observations the experimenter must determine the state in which the automaton under consideration is found, i.e., the state of the automaton after the last input letter has acted on it. This final state, generally speaking, can be determined even in the case when the initial state of the automaton remains unknown. The procedure for determining the final state of an automaton after introducing a suitable finite sequence of input letters and observing the results at the output of the automaton is called an experiment for recognizing the final state, or simply an experiment. An experiment is called homogeneous if the experimenter chooses the input sequence before the beginning of the experiment and does not change it in the course of the experiment. If, however, the input sequence is such that each successive input letter is chosen by the experimenter as a function of the preceding input and output letters, then the experiment is called inhomogeneous.
By \(u(A)\) and \(e(A)\) we shall denote, respectively, the length of the shortest homogeneous and the shortest inhomogeneous experiments (the term shortest has its obvious meaning) for recognizing the final state of an automaton \(A\).
Let \(R_1(m,n,k)\) be the set of all distinct reduced automata (i.e., automata with pairwise distinguishable states) of Mealy \((^2)\) with input letters \(x_1, x_2, \ldots, x_m\), output letters \(y_1, y_2, \ldots, y_n\), and states \(q_1, q_2, \ldots, q_k\). By \(R_2(m,n,k)\) we denote the subset of the set \(R_1(m,n,k)\) consisting of Moore automata, i.e., such automata in which the output depends only on the state and does not depend on the current input. The set of those automata from \(R_1(m,n,k)\) in which any pair of distinct states, under the action of each input letter, passes into distinct states will be denoted by \(R_3(m,n,k)\). Automata from \(R_3(m,n,k)\) are called permutation automata \((^{3,4})\).
The study of the lengths of shortest experiments (both homogeneous and inhomogeneous) for recognizing the final state of automata from the classes \(R_1(m,n,k)\) and \(R_2(m,n,k)\) is the subject of the works \((^{1,3,5–7})\).
The most definitive results were obtained by Hibbard \((^6)\). He proved the following assertions:
1) For any automaton \(A \in R_1(m,n,k)\)
\[ u(A) \leq k(k-1)/2; \]
at the same time, in the class \(R_1(m = k - 1, 2, k)\) there exists at least one permutation automaton \(A\) such that \(e(A) \geq k(k-1)/2\).
2) For any automaton \(A \in R_2(m,n,k)\)
\[ u(A)\le (k-1)(k-2)/2+1; \]
at the same time, in the class \(R_2(m=k-2,2,k)\) there is at least one permutation automaton \(A\) such that
\[ e(A)\ge (k-1)(k-2)/2+1. \]
The following question arises. Does there exist a sequence of such subclasses \(\{\widetilde R_i(m,n,k)\}_{k=1}^{\infty}\), \(i=1,2,3\), such that \(\widetilde R_i(m,n,k)\) contains “almost all” automata* from \(R_i(m,n,k)\), and for any automaton \(A\in \widetilde R_i(m,n,k)\) the length of the shortest homogeneous (or, in the worst case, inhomogeneous) experiment for recognizing the final state would be substantially less than the upper bound established by Hibbard.
A positive answer to this question follows from the following facts. It is known that if the degree of distinguishability \((^8)\) of an automaton \(A\in R_1(m,n,k)\) is equal to \(h\), then
\[ e(A)\le \sum_{i=1}^{h} i+(k-h-1)h<kh. \]
At the same time it is known \((^{4,9})\) that if \(m=\mathrm{const}\ge 2\) and \(n=\mathrm{const}\ge 2\), then for almost all automata \(A\in R_i(m,n,k)\), \(i=1,2,3\), the degree of distinguishability does not exceed \(\log_m\log_n k+4\).
Thus, for any \(m=\mathrm{const}\ge 2\) and \(n=\mathrm{const}\ge 2\), for almost all automata \(A\in R_i(m,n,k)\), \(i=1,2,3\), the relation
\[ e(A)<k(\log_m\log_n k+4) \]
holds.
It turns out that in fact the following stronger fact holds, for the formulation of which the present note has been written.
Theorem. For any \(m=\mathrm{const}\ge 2\) and \(n=\mathrm{const}\ge 2\), for almost all automata \(A\in R_i(m,n,k)\), \(i=1,2,3\), the length of the shortest homogeneous experiment for recognizing the final state satisfies the relation
\[ u(A)<5\log_n k. \]
Remark. An essential point in the proof of this theorem is the establishment of the fact that, for almost all automata from \(R_i(m,n,k)\), \(i=1,2,3\), \(m=\mathrm{const}\ge 2\), \(n=\mathrm{const}\ge 2\), as homogeneous experiments (generally speaking, not shortest ones) for recognizing the final state, one can use one and the same input sequence of the form \(x_1^r x_2 x_1^r\), where \(x_1^r=x_1x_1\ldots x_1\) (\(r\) times), and \(r=[2.5\log_n k]-1\).
It is easy to see that any permutation automaton \(A\) has the following property: when the input and output sequences and the final state of this automaton are known, it is always possible to determine in which initial state the automaton \(A\) was.
From this fact and the theorem formulated above we obtain
Corollary. For any \(m=\mathrm{const}\ge 2\) and \(n=\mathrm{const}\ge 2\), for almost all automata \(A\in R_3(m,n,k)\), the length of the shortest homogeneous experiment for recognizing the initial state does not exceed \(5\log_n k\).
Institute of Mathematics
Siberian Branch of the Academy of Sciences of the USSR
Received
12 IV 1968
REFERENCES
\(^1\) E. F. Moore, in: Automata, IL, 1956.
\(^2\) V. M. Glushkov, Synthesis of Digital Automata, Moscow, 1962.
\(^3\) S. Ginsburg, J. Assoc. Comput. Math., 5, No. 3, 266 (1958).
\(^4\) A. D. Korshunov, DAN, 182, No. 2 (1968).
\(^5\) A. A. Karatsuba, UMN, 15, issue 3, 157 (1960).
\(^6\) T. H. Hibbard, J. Assoc. Comput. Math., 8, No. 4, 601 (1961).
\(^7\) Z. Bavel, Switching Circuit Theory and Logical Design, N. Y., 1964, p. 234.
\(^8\) N. E. Kobrinskii, B. A. Trakhtenbrot, Introduction to the Theory of Finite Automata, Moscow, 1962.
\(^9\) A. D. Korshunov, Discrete Analysis, issue 10, 39 (1967).
* We say that almost all automata of the class \(R_i(m,n,k)\), \(i=1,2,3\), are contained in \(\widetilde R_i(m,n,k)\) if the ratio of the number of automata in \(\widetilde R_i(m,n,k)\) to the number of automata in \(R_i(m,n,k)\) tends to one as \(k\to\infty\).