|
Vestnik Moskovskogo Universiteta. Seriya 1. Matematika. Mekhanika, 2019, Number 1, Pages 52–54
(Mi vmumm600)
|
|
|
|
Short notes
Solvability of the problem of completeness of automaton basis depending on its boolean part
D. N. Babin Lomonosov Moscow State University, Faculty of Mechanics and Mathematics
Abstract:
We consider the problem of completeness of systems of automaton functions with operations of superposition and feedback of the form
$\Phi\cup\nu,$ where $\Phi\subseteq P_2$, $\nu$ is finite. The solution of this problem leads to separation of the lattice of closed Post classes into strong ones (whose presence in the studied system guarantees the solvability of the completeness problem of finite bases) and weak ones (whose presence in the studied system does not guarantee this). It turns out that the classifications of bases by the properties of completeness and A-completeness coincide. The paper describes this classification.
Key words:
finite automaton, superposition, feedback, closed class.
Received: 20.04.2018
Citation:
D. N. Babin, “Solvability of the problem of completeness of automaton basis depending on its boolean part”, Vestnik Moskov. Univ. Ser. 1. Mat. Mekh., 2019, no. 1, 52–54; Moscow University Mathematics Bulletin, 74:1 (2019), 32–34
Linking options:
https://www.mathnet.ru/eng/vmumm600 https://www.mathnet.ru/eng/vmumm/y2019/i1/p52
|
Statistics & downloads: |
Abstract page: | 120 | Full-text PDF : | 25 | References: | 23 |
|