zbMATH — the first resource for mathematics

On decidability of the completeness problem for special systems of automaton functions. (English. Russian original) Zbl 0870.03014
Discrete Math. Appl. 6, No. 5, 491-504 (1996); translation from Diskretn. Mat. 8, No. 4, 79-91 (1996).
Consider systems of automaton functions of the form \(\Phi\cup \nu\), where \(\Phi\) is a Post class and \(\nu\) is a finite system of automaton functions. In a previous paper [Discrete Math. Appl. 5, No. 1, 31-42 (1995); translation from Diskretn. Mat. 7, No. 1, 52-65 (1995; Zbl 0851.03009)], the author proved that if \(\Phi\) is a Post class of the type \(F^{\infty}\), \(S\), \(P\), or \(O\), then the completeness problem and the \(A\)-completeness problem are algorithmically undecidable. This paper proves that for \(\Phi \in \{ M_1,M_2,M_3,M_4,D_1,D_2,D_3,C_1,C_2,C_3,C_4, F^2_i, i=1,\ldots,8 \}\) the completeness problem and the \(A\)-completeness problem are algorithmically decidable.

03D05 Automata and formal grammars in connection with logical questions
68Q45 Formal languages and automata
03B25 Decidability of theories and sets of sentences
94C10 Switching theory, application of Boolean algebra; Boolean functions (MSC2010)
Full Text: DOI