|
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.
Citation:
V. B. Kudryavtsev, D. N. Babin, “Classification of bases in $P_k$ by the property of decidability of the completeness for automata”, Intelligent systems. Theory and applications, 23:1 (2019), 137–145
Linking options:
https://www.mathnet.ru/eng/ista223 https://www.mathnet.ru/eng/ista/v23/i1/p137
|
Statistics & downloads: |
Abstract page: | 134 | Full-text PDF : | 45 | References: | 21 |
|