Geodesic
The completeness criterion for systems containing all one-place bounded-determinate functions
Diskretnaya Matematika, Tome 12 (2000) no. 4, pp. 138-158 
V. A. Buevich. The completeness criterion for systems containing all one-place bounded-determinate functions. Diskretnaya Matematika, Tome 12 (2000) no. 4, pp. 138-158. http://geodesic.mathdoc.fr/item/DM_2000_12_4_a10/
@article{DM_2000_12_4_a10,
     author = {V. A. Buevich},
     title = {The completeness criterion for systems containing all one-place bounded-determinate functions},
     journal = {Diskretnaya Matematika},
     pages = {138--158},
     year = {2000},
     volume = {12},
     number = {4},
     language = {ru},
     url = {http://geodesic.mathdoc.fr/item/DM_2000_12_4_a10/}
}
TY  - JOUR
AU  - V. A. Buevich
TI  - The completeness criterion for systems containing all one-place bounded-determinate functions
JO  - Diskretnaya Matematika
PY  - 2000
SP  - 138
EP  - 158
VL  - 12
IS  - 4
UR  - http://geodesic.mathdoc.fr/item/DM_2000_12_4_a10/
LA  - ru
ID  - DM_2000_12_4_a10
ER  - 
%0 Journal Article
%A V. A. Buevich
%T The completeness criterion for systems containing all one-place bounded-determinate functions
%J Diskretnaya Matematika
%D 2000
%P 138-158
%V 12
%N 4
%U http://geodesic.mathdoc.fr/item/DM_2000_12_4_a10/
%G ru
%F DM_2000_12_4_a10

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

We consider the completeness problem for the functional system $\mathrm P$ whose elements are finite-automaton functions (f.-a. functions) and the only operations are the operations of superposition. It is known that $\mathrm P$ does not contain finite complete systems. However D. N. Babin constructed an example of a finite set of f.-a. functions which together with the set $\mathrm P(1)$ of all one-place f.-a. functions forms a complete system in $\mathrm P$. In this paper, the completeness criterion of systems of f.-a. functions which contain $\mathrm P(1)$ is given. It allows us to construct nontrivial examples of complete systems. The research was supported by the Russian Foundation for Basic Research, grant 00–01–00374.

[1] Yablonskii S. V., Vvedenie v diskretnuyu matematiku, Nauka, Moskva, 1986 | MR

[2] Yablonskii S. V., “Funktsionalnye postroeniya v $k$-znachnoi logike”, Trudy Matem. in-ta im. V. A. Steklova, 51, 1958, 5–142 | Zbl

[3] Kudryavtsev V. B., Funktsionalnye sistemy, Izd-vo MGU, Moskva, 1982 | Zbl

[4] Gavrilov G. P., “O funktsionalnoi polnote v schetnoznachnoi logike”, Problemy kibernetiki, 15 (1965), 5–64 | MR | Zbl

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

[6] Babin D. N., “O polnote dvumestnykh o.-d. funktsii otnositelno superpozitsii”, Diskretnaya matematika, 1:4 (1989), 86–95 | MR

[7] Marchenkov S. S., “O klassakh Slupetskogo dlya determinirovannykh funktsii”, Diskretnaya matematika, 10:2 (1998), 128–136 | MR | Zbl

[8] Buevich V. A., Usloviya $A$-polnoty dlya konechnykh avtomatov, Chast I, Izd-vo MGU, Moskva, 1986

[9] Buevich V. A., Usloviya $A$-polnoty dlya konechnykh avtomatov, Chast II, Izd-vo MGU, Moskva, 1987