Geodesic
Functional aspects of the completeness problem for some classes of automaton functions
Diskretnaya Matematika, Tome 12 (2000) no. 2, pp. 103-117
Cet article a éte moissonné depuis la source Math-Net.Ru

Voir la notice de l'article

For a closed class $Q$ of Boolean functions, $\mathcal A(Q)$ denotes the closed class of all finite-automaton functions computable by finite automata which realise a function of $Q$ in each state. It is shown that if $Q_1$, $Q_2$ are closed classes of Boolean functions, $O_1\subseteq Q_1\subset Q_2$, then the family of classes which are precomplete in $\mathcal A(Q_2)$ and contain the class $\mathcal A(Q_1)$ is of the continuum cardinality. We denote by $\mathbf C_\varphi$ the set of all functions which are defined and uniformly continuous on the Baire space $E_2^\infty$ with the modulus of continuity $\varphi$. It is established that if a closed class of functions continuous on $E_2^\infty$ can be represented in the form of a countable union of the classes $\mathbf C_{\varphi_i}$, where $\varphi_1(t)=2t$, then the family of Słupecki classes in it is of the hypercontinuum cardinality. The research was supported by the Russian Foundation for Basic Research, grant 97–01–00989. 
@article{DM_2000_12_2_a8,
     author = {S. S. Marchenkov},
     title = {Functional aspects of the completeness problem for some classes of automaton functions},
     journal = {Diskretnaya Matematika},
     pages = {103--117},
     year = {2000},
     volume = {12},
     number = {2},
     language = {ru},
     url = {http://geodesic.mathdoc.fr/item/DM_2000_12_2_a8/}
}
TY  - JOUR
AU  - S. S. Marchenkov
TI  - Functional aspects of the completeness problem for some classes of automaton functions
JO  - Diskretnaya Matematika
PY  - 2000
SP  - 103
EP  - 117
VL  - 12
IS  - 2
UR  - http://geodesic.mathdoc.fr/item/DM_2000_12_2_a8/
LA  - ru
ID  - DM_2000_12_2_a8
ER  - 
%0 Journal Article
%A S. S. Marchenkov
%T Functional aspects of the completeness problem for some classes of automaton functions
%J Diskretnaya Matematika
%D 2000
%P 103-117
%V 12
%N 2
%U http://geodesic.mathdoc.fr/item/DM_2000_12_2_a8/
%G ru
%F DM_2000_12_2_a8
S. S. Marchenkov. Functional aspects of the completeness problem for some classes of automaton functions. Diskretnaya Matematika, Tome 12 (2000) no. 2, pp. 103-117. http://geodesic.mathdoc.fr/item/DM_2000_12_2_a8/

[1] Kudryavtsev V. B., “Otnositelno funktsionalnykh sistem”, Problemy kibernetiki, 41 (1984), 5–40 | MR | Zbl

[2] Kon G., Universalnaya algebra, Mir, Moskva, 1968 | MR

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

[4] Kudryavtsev V. B., “O moschnostyakh mnozhestv predpolnykh mnozhestv nekotorykh funktsionalnykh sistem, svyazannykh s avtomatami”, Problemy kibernetiki, 13 (1965), 45–74

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

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

[7] Marchenkov S. S., “Ob odnom metode analiza superpozitsii nepreryvnykh funktsii”, Problemy kibernetiki, 37 (1980), 5–17 | MR | Zbl

[8] Trakhtenbrot B. A., Barzdin Ya. M., Konechnye avtomaty, Nauka, Moskva, 1970.

[9] Yablonskii S. V., Gavrilov G. P., Kudryavtsev V. B., Funktsii algebry logiki i klassy Posta, Nauka, Moskva, 1966 | MR | Zbl