×

zbMATH — the first resource for mathematics

Finiteness of the set of automaton Post bases with solvable completeness problem. (English. Russian original) Zbl 0965.03053
Discrete Math. Appl. 8, No. 5, 475-482 (1998); translation from Diskretn. Mat. 10, No. 3, 57-63 (1998).
Summary: The bases under consideration are those of the form \(M= \Phi\cup\nu\), where \(\Phi\) is a Post class and \(\nu\) is a finite system of automaton functions. It is shown that the sets of Post classes \(\Phi\) for which the completeness problem for \(\Phi\cup\nu\) is solvable, respectively, the \(A\)-completeness problem for \(\Phi\cup\nu\) is solvable, are finite.
MSC:
03D05 Automata and formal grammars in connection with logical questions
94C10 Switching theory, application of Boolean algebra; Boolean functions (MSC2010)
PDF BibTeX Cite
Full Text: DOI