RUS  ENG
Full version
JOURNALS // Intelligent systems. Theory and applications // Archive

Intelligent systems. Theory and applications, 2019 Volume 23, Issue 1, Pages 137–145 (Mi ista223)

Part 3. Mathematical models

Classification of bases in $P_k$ by the property of decidability of the completeness for automata

V. B. Kudryavtsev, D. N. Babin


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.



© Steklov Math. Inst. of RAS, 2024