zbMATH — the first resource for mathematics

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.

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)
PDF BibTeX Cite
Full Text: DOI