Geodesic
On the classification of bases in $P_k$ according to the decidability of the completeness problem for automata
Fundamentalʹnaâ i prikladnaâ matematika, Tome 15 (2009) no. 3, pp. 33-47 
D. N. Babin. On the classification of bases in $P_k$ according to the decidability of the completeness problem for automata. Fundamentalʹnaâ i prikladnaâ matematika, Tome 15 (2009) no. 3, pp. 33-47. http://geodesic.mathdoc.fr/item/FPM_2009_15_3_a4/
@article{FPM_2009_15_3_a4,
     author = {D. N. Babin},
     title = {On the classification of bases in $P_k$ according to the decidability of the completeness problem for automata},
     journal = {Fundamentalʹna\^a i prikladna\^a matematika},
     pages = {33--47},
     year = {2009},
     volume = {15},
     number = {3},
     language = {ru},
     url = {http://geodesic.mathdoc.fr/item/FPM_2009_15_3_a4/}
}
TY  - JOUR
AU  - D. N. Babin
TI  - On the classification of bases in $P_k$ according to the decidability of the completeness problem for automata
JO  - Fundamentalʹnaâ i prikladnaâ matematika
PY  - 2009
SP  - 33
EP  - 47
VL  - 15
IS  - 3
UR  - http://geodesic.mathdoc.fr/item/FPM_2009_15_3_a4/
LA  - ru
ID  - FPM_2009_15_3_a4
ER  - 
%0 Journal Article
%A D. N. Babin
%T On the classification of bases in $P_k$ according to the decidability of the completeness problem for automata
%J Fundamentalʹnaâ i prikladnaâ matematika
%D 2009
%P 33-47
%V 15
%N 3
%U http://geodesic.mathdoc.fr/item/FPM_2009_15_3_a4/
%G ru
%F FPM_2009_15_3_a4

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

The completeness problem for bases of the form $\Phi\cup\nu$, where $\Phi\subseteq P_k$ and $\nu$ is a finite system of automaton functions, is considered. Previously, the problem for $k=2$ was solved by the author; it was also shown that there is an algorithm for determining the completeness of the system $\Phi\cup\nu$ when $[\Phi]=P_k$. The article is concerned with the case where $[\Phi]$ is the maximal (precomplete) class in $P_k$. The problem of completeness for systems $\Phi\cup\nu$ is shown to be undecidable if $\Phi$ is embedded in a Slupecki class and algorithmically decidable if $\Phi$ contains the preserving class of all constants. Thus, the bases in $P_k$, $k\ge3$, can be classified according to their ability to guarantee the decidability of the completeness problem for automaton functions.

[1] Babin D. N., “Razreshimyi sluchai zadachi o polnote avtomatnykh funktsii”, Diskret. mat., 4:4 (1992), 41–55 | MR | Zbl

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

[3] Buevich V. A., Usloviya A-polnoty dlya avtomatov, Izd-vo Mosk. un-ta, M., 1986

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

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

[6] Kudryavtsev V. B., Alëshin S. V., Podkolzin A. S., Vvedenie v teoriyu avtomatov, Nauka, M., 1985 | MR | Zbl

[7] Letichevskii A. A., “Usloviya polnoty dlya konechnykh avtomatov”, ZhVM i MF, 1961, no. 4, 702–710

[8] Maltsev A. I., Algoritmy i rekursivnye funktsii, Nauka, M., 1986 | MR | Zbl

[9] Chasovskikh A. A., “O polnote v klasse lineinykh avtomatov”, Mat. voprosy kibernetiki, 3, 1991, 140–166 | MR | Zbl

[10] Yablonskii S. V., “Funktsionalnye postroeniya v $k$-znachnoi logike”, Tr. Mat. in-ta im. V. A. Steklova AN SSSR, 51, 1958, 5–142 | MR | Zbl