Automata, complete systems of

Special subsets of a given class $M$ of automata on which a certain set $\Omega$ of operations with values in $M$ has been defined. These subsets have the following fundamental completeness property: The set of all automata obtained by a finite number of operations from $\Omega$ to automata from a given subset $A \subseteq M$, is identical with $M$. The problem of whether a set is complete or not is known as the completeness problem for automata. It has been studied for various models of automata and operations. The range of objects of such studies includes, in order of increasing complexity, true automata, automata realizing functions with delays (i.e. functions of $k$-valued logic with a certain shift in time), finite automata, etc. The completeness problem of true automata with superposition operations (which are usually considered) is essentially the same as the completeness problem for functions of $k$-valued logic (see Many-valued logic) and has been fairly thoroughly studied. Synchronous superposition is defined as superposition of automata for which the automata realizing functions with the same delay are combined at all inputs. The criteria of completeness, found under these conditions, imply, in particular, the existence of an algorithm by means of which the completeness or incompleteness of any finite system of automata can be established. Fundamental criteria of completeness are given in terms of the so-called pre-complete classes (i.e. subsets of the class $M$ that are closed with respect to the operations from $\Omega$, each one of which forms together with any automaton not belonging to it a complete system). It has been shown that a set $A$ is complete if and only if it is not a subset of any pre-complete class. These classes, in turn, have been fully described. This approach was successfully employed in a large number of other cases. It is also applicable, in principle, to finite automata if the operation of superposition of automata and the feedback operation are chosen as $\Omega$ (cf. Automata, composition of). The criterion given above is applicable also in this case; it has been established, however, that the family of pre-complete classes is a continual class, which excludes the existence of any effective criteria in these terms. One may note that in all the cases mentioned here there exist finite complete systems, and for this reason the completeness problem for arbitrary systems of automata is reduced to the completeness problem for finite systems of automata. One must consider in this context, as above, the problem of algorithmic solvability of the completeness problem for finite systems of finite automata. The problem may be generalized as follows: To determine, for a given automaton $a$ and set $B$, whether or not $a$ may be obtained from automata in $B$ by effecting a given set of operations. One must thus study the predicate $P(x,y)$ — "the automaton $x$ is realized by means of a set $y$" . It was found that the problem of recognition of realizability is algorithmically unsolvable for any given $a$, i.e. that the one-place predicate $P(a,y)$ is non-recursive. On the other hand, for various values $B$ of the parameter $y$, the predicate $P(x,B)$ may be either recursive or non-recursive. A problem connected with the algorithmic unsolvability of the completeness problem for automata is the problem of finding classes of sets for which it has an effective solution. In particular, there exists an algorithm for the recognition of the completeness of systems consisting only of Moore automata and all true automata. A related problem is that of finding concrete complete sets of automata with given properties. It was found that, for any positive integer $n$, there exists a complete system of automata no proper subset of which is complete, and that, for a given $n$, the number of such systems is infinite. There also exists a most simple, in a certain sense, automaton with two states, two input channels and one output channel that constitutes a complete system. The completeness problem has also been studied for different generalizations of finite automata and operations performed on them; another kind of generalization concerns the introduction of various equivalence relations into the class of automata under consideration.

References

[1]	S.V. Yablonskii, "Functional constructions in $k$-placed logic" Trudy Mat. Inst. Steklov. , 51 (1958) pp. 5–142 (In Russian)
[2]	V.B. Kudryavtsev, "The completeness theorem for one class of feedback automata" Problemy Kibernet. , 8 (1958) pp. 91–115 (In Russian)
[3]	V.B. Kudryavtsev, "On the cardinality of sets of pre-complete sets of certain function systems, related to automata" Problemy Kibernet. (1965) pp. 45–74 (In Russian)
[4]	M.I. Kratko, "On the existence of non-recursive bases of finite automata" Algebra i Logika , 3 : 2 (1964) pp. 33–44 (In Russian)
[5]	A.A. Letichevskii, "Conditional completeness in the class of Moore automata" , Kiev (1963) (In Russian)
[6]	V.A. Buevich, "The construction of universal finitely-determined functions in two input variables, having two internal states" Problemy Kibernet. : 22 (1970) pp. 75–83 (In Russian)

Comments

The topic of this article is rather esoteric. The problem of completeness (in this sense) has not really been studied outside the Soviet Union and is not considered very significant in the Western literature.