Geodesic
On the structure of partially ordered sets of Boolean degrees
Diskretnaya Matematika, Tome 18 (2006) no. 1, pp. 63-75
Cet article a éte moissonné depuis la source Math-Net.Ru

Voir la notice de l'article

On the set of all infinite binary sequences, we consider the simplest form of algorithmic reducibility, namely, the Boolean reducibility. Each set $Q$ of Boolean functions which contains a selector function and is closed with respect to the superposition operation of special kind generates the $Q$-reducibility and $Q$-degrees, the sets of $Q$-equivalent sequences. The $Q$-degree of a sequence $\alpha$ characterises the relative ‘informational complexity’ of the sequence $\alpha$, in a sense, $Q$ is a set of operators of information retrieval from infinite sequences. In this paper, we study the partially ordered sets $\mathcal L_Q$ of all $Q$-degrees for the most important classes $Q$ of Boolean functions. We investigate the positions of periodic and narrow $Q$-degrees in $\mathcal L_Q$, find the number of minimal elements and atoms and also the initial segments isomorphic to given finite lattices. This research was supported by the Russian Foundation for Basic Research, grant 03–01–00783. 
@article{DM_2006_18_1_a4,
     author = {S. S. Marchenkov},
     title = {On the structure of partially ordered sets of {Boolean} degrees},
     journal = {Diskretnaya Matematika},
     pages = {63--75},
     year = {2006},
     volume = {18},
     number = {1},
     language = {ru},
     url = {http://geodesic.mathdoc.fr/item/DM_2006_18_1_a4/}
}
TY  - JOUR
AU  - S. S. Marchenkov
TI  - On the structure of partially ordered sets of Boolean degrees
JO  - Diskretnaya Matematika
PY  - 2006
SP  - 63
EP  - 75
VL  - 18
IS  - 1
UR  - http://geodesic.mathdoc.fr/item/DM_2006_18_1_a4/
LA  - ru
ID  - DM_2006_18_1_a4
ER  - 
%0 Journal Article
%A S. S. Marchenkov
%T On the structure of partially ordered sets of Boolean degrees
%J Diskretnaya Matematika
%D 2006
%P 63-75
%V 18
%N 1
%U http://geodesic.mathdoc.fr/item/DM_2006_18_1_a4/
%G ru
%F DM_2006_18_1_a4
S. S. Marchenkov. On the structure of partially ordered sets of Boolean degrees. Diskretnaya Matematika, Tome 18 (2006) no. 1, pp. 63-75. http://geodesic.mathdoc.fr/item/DM_2006_18_1_a4/

[1] Rodzhers Kh., Teoriya rekursivnykh funktsii i effektivnaya vychislimost, Mir, Moskva, 1972 | MR

[2] Reina G., “Stepeni avtomatnykh preobrazovanii”, Kibern. sb., 14 (1977), 95–106

[3] Marchenkov S. S., “Buleva svodimost”, Diskretnaya matematika, 15:3 (2003), 40–53 | MR | Zbl

[4] Gordon H. G., “Complete degrees of finite-state transformability”, Information and Control, 32 (1976), 169–187 | DOI | MR | Zbl

[5] Bairasheva V. R., “Strukturnye svoistva avtomatnykh preobrazovanii”, Izvestiya vuzov. Matematika, 7 (1988), 34–39 | MR

[6] Marchenkov S. S., “Konechnye nachalnye segmenty verkhnei polureshetki konechno-avtomatnykh stepenei”, Diskretnaya matematika, 1:3 (1989), 96–103 | MR | Zbl

[7] Solovev V. D., “Struktura raspredeleniya informatsii v beskonechnoi posledovatelnosti”, Diskretnaya matematika, 8:2 (1996), 97–107 | MR

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

[9] Marchenkov S. S., Zamknutye klassy bulevykh funktsii, Fizmatlit, Moskva, 2000 | MR | Zbl