On the classification of bases in $P_k$ according to the decidability of the completeness problem for automata

D. N. Babin

Fundamentalʹnaâ i prikladnaâ matematika, Tome 15 (2009) no. 3, pp. 33-47

Résumé

The completeness problem for bases of the form $\Phi\cup\nu$, where $\Phi\subseteq P_k$ and $\nu$ is a finite system of automaton functions, is considered. Previously, the problem for $k=2$ was solved by the author; it was also shown that there is an algorithm for determining the completeness of the system $\Phi\cup\nu$ when $[\Phi]=P_k$. The article is concerned with the case where $[\Phi]$ is the maximal (precomplete) class in $P_k$. The problem of completeness for systems $\Phi\cup\nu$ is shown to be undecidable if $\Phi$ is embedded in a Slupecki class and algorithmically decidable if $\Phi$ contains the preserving class of all constants. Thus, the bases in $P_k$, $k\ge3$, can be classified according to their ability to guarantee the decidability of the completeness problem for automaton functions.