×

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.

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