Solvability of the Problem of Completeness of Automaton Basis Depending on its Boolean Part
Dmitry Nikolaevich Babin · Moscow University Mathematics Bulletin · 2019
We consider the problem of completeness of systems of automaton functions with operations of superposition and feedback of the formΦ ∪ ν , where Φ ⊆ P 2 , and ν is finite. The solution of this problem leads to separation of the lattice of closed Post classes into strong ones (whose presence in the system under consideration guarantees the solvability of the completeness problem of finite bases) and weak ones (whose presence in the system under consideration does not guarantee this solvability). It turns out that the classifications of bases by completeness and A -completeness properties coincide. The paper describes this classification.