Geodesic
Boolean Hierarchies of Partitions over a~Reducible Base
Algebra i logika, Tome 43 (2004) no. 1, pp. 77-109.

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

The Boolean hierarchy of partitions was introduced and studied by Kosub and Wagner, primarily over the lattice of $NP$-sets. Here, this hierarchy is treated over lattices with the reduction property, showing that it has a much simpler structure in this instance. A complete characterization is given for the hierarchy over some important lattices, in particular, over the lattices of recursively enumerable sets and of open sets in the Baire space
Keywords: Boolean hierarchy of partitions, lattice with the reduction property, lattice of recursively enumerable sets, lattice of open sets of the Baire space. 
@article{AL_2004_43_1_a3,
     author = {V. L. Selivanov},
     title = {Boolean {Hierarchies} of {Partitions} over {a~Reducible} {Base}},
     journal = {Algebra i logika},
     pages = {77--109},
     publisher = {mathdoc},
     volume = {43},
     number = {1},
     year = {2004},
     language = {ru},
     url = {http://geodesic.mathdoc.fr/item/AL_2004_43_1_a3/}
}
TY  - JOUR
AU  - V. L. Selivanov
TI  - Boolean Hierarchies of Partitions over a~Reducible Base
JO  - Algebra i logika
PY  - 2004
SP  - 77
EP  - 109
VL  - 43
IS  - 1
PB  - mathdoc
UR  - http://geodesic.mathdoc.fr/item/AL_2004_43_1_a3/
LA  - ru
ID  - AL_2004_43_1_a3
ER  - 
%0 Journal Article
%A V. L. Selivanov
%T Boolean Hierarchies of Partitions over a~Reducible Base
%J Algebra i logika
%D 2004
%P 77-109
%V 43
%N 1
%I mathdoc
%U http://geodesic.mathdoc.fr/item/AL_2004_43_1_a3/
%G ru
%F AL_2004_43_1_a3
V. L. Selivanov. Boolean Hierarchies of Partitions over a~Reducible Base. Algebra i logika, Tome 43 (2004) no. 1, pp. 77-109. http://geodesic.mathdoc.fr/item/AL_2004_43_1_a3/

[1] S. Kosub, K. Wagner, The boolean hierarchy of partitions, Technical Report 233, Institut für Informatik, Univ. Würzburg, 1999

[2] S. Kosub, K. Wagner, “The boolean hierarchy of $NP$-partitions”, Proc. 17th Symp. Theor. Aspects Comp. Sci., Lect. Notes Comput. Sci., 1770, Springer-Verlag, Berlin, 2000, 157–168 | MR | Zbl

[3] S. Kosub, “On $NP$-partitions over posets with an application of reducing the set of solutions of $NP$ problems”, Proc. 25th Symp. Math. Found. Comp. Sci., Lect. Notes Comput. Sci., 1893, Springer-Verlag, Berlin, 2000, 467–476 | MR | Zbl

[4] S. Kosub, Complexity and partitions, PhD Thesis, Würzburg, 2000

[5] V. L. Selivanov, “O strukture stepenei obobschennykh indeksnykh mnozhestv”, Algebra i logika, 21:4 (1982), 472–491 | MR

[6] V. L. Selivanov, “Tonkaya ierarkhiya arifmeticheskikh mnozhestv i opredelimye indeksnye mnozhestva”, Matematicheskaya logika i algoritmicheskie problemy, Trudy In-ta matem. SO AN SSSR, 12, 1989, 165–185 | MR | Zbl

[7] V. L. Selivanov, Ierarkhicheskaya klassifikatsiya arifmeticheskikh mnozhestv i indeksnye mnozhestva, dokt. disser., In-t matem. SO AN SSSR, Novosibirsk, 1989

[8] B. A. Davey, H. A. Priestley, Introduction to lattices and order, Cambridge Univ. Press, Cambridge, 1994 | MR | Zbl

[9] J. B. Kruskal, “The theory of well-quasi-ordering: a frequently discovered concept”, J. Comb. Theory, Ser. A, 13:3 (1972), 297–305 | DOI | MR | Zbl

[10] J. B. Kruskal, “Well-quasi-ordering, the tree theorem, and Varzsonyi's conjecture”, Trans. Am. Math. Soc., 95:2 (1960), 210–225 | DOI | MR | Zbl

[11] Yu. L. Ershov, Teoriya numeratsii, Nauka, M., 1977 | MR

[12] V. L. Selivanov, “Fine hierarchies and Boolean terms”, J. Symb. Log., 60:1 (1995), 289–317 | DOI | MR | Zbl

[13] H. Rogers, Theory of recursive functions and effective computability, McGrow Hill, New York, 1967 | MR | Zbl

[14] Y. L. Ershov, “Theorie der Numerierungen I”, Z. math. Log. Grundl. Math., 19:4 (1973), 289–388 | MR

[15] Y. L. Ershov, “Theorie der Numerierungen II”, Z. math. Log. Grundl. Math., 21:6 (1975), 473–584 | MR | Zbl

[16] Yu. L. Ershov, “Ob odnoi ierarkhii mnozhestv III”, Algebra i logika, 9:1 (1970), 34–51 | MR | Zbl

[17] Y. N. Moschovakis, Descriptive set theory, North-Holland, Amsterdam, 1980 | MR | Zbl

[18] V. L. Selivanov, Hierarchies, numerations, index sets, handwritten notes, Novosibirsk, 1992

[19] V. L. Selivanov, “Fine hierarchy of regular $\omega$-languages”, Theor. Comput. Sci., 191:1–2 (1998), 37–59 | DOI | MR | Zbl

[20] V. L. Selivanov, Boolean hierarchy of partitions over reducible bases, Technical report 276, Institut für Informatik, Univ. Würzburg, 2001