Abstract:
We consider the problem of the completeness of systems of automaton functions with operations of superposition and feedback of the form $\Phi \cup \nu$, where $\Phi \subseteq P_k$ , $\nu$ is finite. For $k = 2$, the solution of this problem leads to the separation of the lattice of closed Post classes into strong ones (whose presence in the system under study guarantees the solvability of the completeness problem of finite bases) and weak ones (which does not guarantee this in the system under study). For $k = 2$ this problem was solved for systems of automaton functions of arbitrary form (Babin DN 1998). In this paper, we investigate corollaries and possible extensions of this problem, as well as some results for $P_k$ , $k > 2$.
Keywords:Boolean function, finite automaton, algorithmic solvalibility of functions by formulas.