Geodesic
On maximal and minimal elements in partially ordered sets of Boolean degrees
Diskretnyj analiz i issledovanie operacij, Tome 20 (2013) no. 2, pp. 88-101

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

The weakest variant of algorithmic reducibility called Boolean reducibility is considered. For various closed classes $Q$, the partially ordered sets $\mathcal L_Q$ of Boolean degrees are analyzed. It is proved that for many closed classes $Q$ the corresponding sets $\mathcal L_Q$ have no maximal elements. Examples of sufficiently large classes $Q$ are given for which the sets $\mathcal L_Q$ contain uncountably many maximal elements. It is established that for closed classes $T_{01}$ and $S$M the corresponding sets of degrees have uncountably many minimal elements. Bibliogr. 8.
Keywords: Boolean reducibility, closed classes of Boolean functions. 
@article{DA_2013_20_2_a6,
     author = {S. S. Marchenkov},
     title = {On maximal and minimal elements in partially ordered sets of {Boolean} degrees},
     journal = {Diskretnyj analiz i issledovanie operacij},
     pages = {88--101},
     publisher = {mathdoc},
     volume = {20},
     number = {2},
     year = {2013},
     language = {ru},
     url = {http://geodesic.mathdoc.fr/item/DA_2013_20_2_a6/}
}
TY  - JOUR
AU  - S. S. Marchenkov
TI  - On maximal and minimal elements in partially ordered sets of Boolean degrees
JO  - Diskretnyj analiz i issledovanie operacij
PY  - 2013
SP  - 88
EP  - 101
VL  - 20
IS  - 2
PB  - mathdoc
UR  - http://geodesic.mathdoc.fr/item/DA_2013_20_2_a6/
LA  - ru
ID  - DA_2013_20_2_a6
ER  - 
%0 Journal Article
%A S. S. Marchenkov
%T On maximal and minimal elements in partially ordered sets of Boolean degrees
%J Diskretnyj analiz i issledovanie operacij
%D 2013
%P 88-101
%V 20
%N 2
%I mathdoc
%U http://geodesic.mathdoc.fr/item/DA_2013_20_2_a6/
%G ru
%F DA_2013_20_2_a6
S. S. Marchenkov. On maximal and minimal elements in partially ordered sets of Boolean degrees. Diskretnyj analiz i issledovanie operacij, Tome 20 (2013) no. 2, pp. 88-101. http://geodesic.mathdoc.fr/item/DA_2013_20_2_a6/