RUS  ENG
Full version
JOURNALS // Vestnik Moskovskogo Universiteta. Seriya 1. Matematika. Mekhanika // Archive

Vestnik Moskov. Univ. Ser. 1. Mat. Mekh., 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.

UDC: 511

Received: 20.04.2018


 English version:
Moscow University Mathematics Bulletin, Moscow University Måchanics Bulletin, 2019, 74:1, 32–34

Bibliographic databases:


© Steklov Math. Inst. of RAS, 2024