Undecidability of the completeness and \(A\)-completeness problems for some systems of automaton functions.

*(English. Russian original)*Zbl 0851.03009
Discrete Math. Appl. 5, No. 1, 31-42 (1995); translation from Diskretn. Mat. 7, No. 1, 52-65 (1995).

In this paper, an automaton function \((a\)-function) means a function determined by a (finite) automaton and its initial state which transforms input superwords to output superwords. For any set \(M\) of \(a\)-functions, \(M\) is called complete if the set of all \(a\)-functions can be obtained from \(M\) by superposition and feedback operations. The so-called completeness problem means to describe all complete sets. Restricting \(a\)-functions to the set of all words of fixed length, the concept of an \(A\)-complete set is defined. The \(A\)-completeness problem means to describe all \(A\)-complete sets.

Let \(P^{(1)}\) be the set of all truth functions. It is known that for the systems of automata of the form \(P^{(1)} \cup N\), where \(N\) is a finite set, the completeness problem [the author, Diskretn. Mat. 4, No. 4, 41-55 (1992; Zbl 0815.94025)] and the \(A\)-completeness problem [V. A. Buevich, Conditions of the \(A\)-completeness for finite automata (Moscow Univ. Press, Moscow, 1986) (in Russian)] are algorithmically decidable. Let \(\Phi \subseteq P^{(1)}\) be a closed class of truth functions. The completeness problem and the \(A\)-completeness problem for systems of the form \(\Phi \cup N\) are called \(\Phi\)-completeness problem and \(\Phi\)-\(A\)-completeness problem, respectively. The following results are proved in this paper: For every class \(\Phi\) of type \(F^\infty\), \(S\), \(P\), or \(O\), the \(\Phi\)-completeness problem and \(\Phi\)-\(A\)-completeness problem are algorithmically undecidable.

Let \(P^{(1)}\) be the set of all truth functions. It is known that for the systems of automata of the form \(P^{(1)} \cup N\), where \(N\) is a finite set, the completeness problem [the author, Diskretn. Mat. 4, No. 4, 41-55 (1992; Zbl 0815.94025)] and the \(A\)-completeness problem [V. A. Buevich, Conditions of the \(A\)-completeness for finite automata (Moscow Univ. Press, Moscow, 1986) (in Russian)] are algorithmically decidable. Let \(\Phi \subseteq P^{(1)}\) be a closed class of truth functions. The completeness problem and the \(A\)-completeness problem for systems of the form \(\Phi \cup N\) are called \(\Phi\)-completeness problem and \(\Phi\)-\(A\)-completeness problem, respectively. The following results are proved in this paper: For every class \(\Phi\) of type \(F^\infty\), \(S\), \(P\), or \(O\), the \(\Phi\)-completeness problem and \(\Phi\)-\(A\)-completeness problem are algorithmically undecidable.

Reviewer: Tao Renji (Beijing)

##### MSC:

03D05 | Automata and formal grammars in connection with logical questions |

03D35 | Undecidability and degrees of sets of sentences |

68Q45 | Formal languages and automata |

94C10 | Switching theory, application of Boolean algebra; Boolean functions (MSC2010) |