# 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)
Full Text: