Geodesic
Solvability of the problem of completeness of automaton basis depending on its boolean part
Vestnik Moskovskogo universiteta. Matematika, mehanika, no. 1 (2019), pp. 52-54 
D. N. Babin. Solvability of the problem of completeness of automaton basis depending on its boolean part. Vestnik Moskovskogo universiteta. Matematika, mehanika, no. 1 (2019), pp. 52-54. http://geodesic.mathdoc.fr/item/VMUMM_2019_1_a8/
@article{VMUMM_2019_1_a8,
     author = {D. N. Babin},
     title = {Solvability of the problem of completeness of automaton basis depending on its boolean part},
     journal = {Vestnik Moskovskogo universiteta. Matematika, mehanika},
     pages = {52--54},
     year = {2019},
     number = {1},
     language = {ru},
     url = {http://geodesic.mathdoc.fr/item/VMUMM_2019_1_a8/}
}
TY  - JOUR
AU  - D. N. Babin
TI  - Solvability of the problem of completeness of automaton basis depending on its boolean part
JO  - Vestnik Moskovskogo universiteta. Matematika, mehanika
PY  - 2019
SP  - 52
EP  - 54
IS  - 1
UR  - http://geodesic.mathdoc.fr/item/VMUMM_2019_1_a8/
LA  - ru
ID  - VMUMM_2019_1_a8
ER  - 
%0 Journal Article
%A D. N. Babin
%T Solvability of the problem of completeness of automaton basis depending on its boolean part
%J Vestnik Moskovskogo universiteta. Matematika, mehanika
%D 2019
%P 52-54
%N 1
%U http://geodesic.mathdoc.fr/item/VMUMM_2019_1_a8/
%G ru
%F VMUMM_2019_1_a8

Voir la notice de l'article provenant de la source Math-Net.Ru

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.

[1] Post E. L., Two-valued iterative systems of mathematical logik, Ann. Math. Stud., 5, 1941 | MR

[2] Yablonskii S. V., Gavrilov G. P., Kudryavtsev V. B., Funktsii algebry logiki i klassy Posta, Nauka, M., 1966

[3] Kudryavtsev V. B., “O moschnostyakh mnozhestv predpolnykh klassov nekotorykh funktsionalnykh sistem, svyazannykh s avtomatami”, Dokl. AN SSSR, 151:3 (1963), 493–496

[4] Kratko M. I., “Algoritmicheskaya nerazreshimost problemy raspoznavaniya polnoty dlya konechnykh avtomatov”, Dokl. AN SSSR, 155:1 (1964), 35–37 | MR | Zbl

[5] Letichevskii A. A., “Usloviya polnoty dlya konechnykh avtomatov”, Vychisl. matem. i matem. fiz., 4:1 (1961), 702–710

[6] Buevich V. A., Usloviya A-polnoty dlya avtomatov, Izd-vo MGU, M., 1986

[7] Babin D. N., “Razreshimyi sluchai zadachi o polnote avtomatnykh funktsii”, Diskretn. matem., 4:4 (1992), 41–56 | MR

[8] Babin D. N., “O klassifikatsii avtomatnykh bazisov Posta po razreshimosti svoistv polnoty i A-polnoty”, Dokl. RAN, 367:4 (1999), 439–441 | MR | Zbl

[9] Babin D. N., “O klassifikatsii bazisov v $P_k$ po razreshimosti problemy polnoty dlya avtomatov”, Fund. i prikl. matem., 15:3 (2010), 33–47 | Zbl

[10] Kudryavtsev V. B., Aleshin S. V., Podkolzin A. S., Vvedenie v teoriyu avtomatov, Nauka, M., 1985 | MR