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/

[1] Marchenkov S. S., Zamknutye klassy bulevykh funktsii, Fizmatlit, M., 2000, 126 pp. | MR | Zbl

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

[3] Marchenkov S. S., “Konechnaya porozhdaemost zamknutykh klassov bulevykh funktsii”, Diskret. analiz i issled. operatsii. Ser. 1, 12:1 (2005), 101–118 | MR | Zbl

[4] Marchenkov S. S., “O stroenii chastichno uporyadochennykh mnozhestv bulevykh stepenei”, Diskret. matematika, 18:1 (2006), 63–75 | DOI | MR | Zbl

[5] Marchenkov S. S., “Polnye i nepolnye bulevy stepeni”, Probl. peredachi inform., 46:4 (2010), 83–90 | MR | Zbl

[6] Marchenkov S. S., Matveev S. A., “Bulevy stepeni, opredelyaemye klassami lineinykh funktsii i kon'yunktsii”, Mat. voprosy kibernetiki, 14, Fizmatlit, M., 2005, 35–48

[7] Reina G., “Stepeni avtomatnykh preobrazovanii”, Kibernet. sb., 14, Mir, M., 1977, 95–106

[8] Rodzhers Kh., Teoriya rekursivnykh funktsii i effektivnaya vychislimost, Mir, M., 1972, 624 pp. | MR