Algebra i logika
 RUS  ENG JOURNALS   PEOPLE   ORGANISATIONS   CONFERENCES   SEMINARS   VIDEO LIBRARY   PACKAGE AMSBIB
 General information Latest issue Archive Impact factor Subscription Search papers Search references RSS Latest issue Current issues Archive issues What is RSS

 Algebra Logika: Year: Volume: Issue: Page: Find

 Algebra Logika, 2004, Volume 43, Number 1, Pages 77–109 (Mi al58)

Boolean Hierarchies of Partitions over a Reducible Base

V. L. Selivanov

Novosibirsk State Pedagogical University

Abstract: 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.

Full text: PDF file (331 kB)
References: PDF file   HTML file

English version:
Algebra and Logic, 2004, 43:1, 44–61

Bibliographic databases:

UDC: 510.532+510.54
Revised: 03.09.2003

Citation: V. L. Selivanov, “Boolean Hierarchies of Partitions over a Reducible Base”, Algebra Logika, 43:1 (2004), 77–109; Algebra and Logic, 43:1 (2004), 44–61

Citation in format AMSBIB
\Bibitem{Sel04} \by V.~L.~Selivanov \paper Boolean Hierarchies of Partitions over a~Reducible Base \jour Algebra Logika \yr 2004 \vol 43 \issue 1 \pages 77--109 \mathnet{http://mi.mathnet.ru/al58} \mathscinet{http://www.ams.org/mathscinet-getitem?mr=2073446} \zmath{https://zbmath.org/?q=an:1061.03044} \transl \jour Algebra and Logic \yr 2004 \vol 43 \issue 1 \pages 44--61 \crossref{https://doi.org/10.1023/B:ALLO.0000015130.31054.b3} \scopus{https://www.scopus.com/record/display.url?origin=inward&eid=2-s2.0-33750048402} 

• http://mi.mathnet.ru/eng/al58
• http://mi.mathnet.ru/eng/al/v43/i1/p77

 SHARE:

Citing articles on Google Scholar: Russian citations, English citations
Related articles on Google Scholar: Russian articles, English articles

This publication is cited in the following articles:
1. V. L. Selivanov, “Variations on the Wadge Reducibility”, Siberian Adv. Math., 15:3 (2005), 44–80
2. Lehtonen E., “Descending chains and antichains of the unary, linear, and monotone subfunction relations”, Order, 23:2-3 (2006), 129–142
3. Selivanov V.L., “Towards a descriptive set theory for domain-like structures”, Theoret. Comput. Sci., 365:3 (2006), 258–282
4. Kuske D., “Theories of orders on the set of words”, Theor. Inform. Appl., 40:1 (2006), 53–74
5. Kudinov O.V., Selivanov V.L., “Undecidability in the homomorphic quasiorder of finite labeled forests”, Logical approaches to computational barriers, Second conference on computability in Europe, CiE 2006 (Swansea, UK, June 30–July 5, 2006), Proceedings, Lecture Notes in Comput. Sci., 3988, Springer, Berlin, 2006, 289–296
6. V. L. Selivanov, “The quotient algebra of labeled forests modulo $h$-equivalence”, Algebra and Logic, 46:2 (2007), 120–133
7. Z. G. Khisamiev, “Distributive lattices of numberings”, Algebra and Logic, 46:1 (2007), 50–61
8. Kudinov O.V., Selivanov V.L., “Undecidability in the homomorphic quasiorder of finite labelled forests”, J. Logic Comput., 17:6 (2007), 1135–1151
9. Selivanov V.L., “Hierarchies of $\Delta^0_2$-measurable $k$-partitions”, MLQ Math. Log. Q., 53:4-5 (2007), 446–461
10. Kudinov O.V., Selivanov V.L., “Definability in the homomorphic quasiorder of finite labeled forests”, Computation and Logic in the Real World, Proceedings, Lecture Notes in Computer Science, 4497, 2007, 436–445
11. Selivanov V.L., “A useful undecidable theory”, Computation and Logic in the Real World, Proceedings, Lecture Notes in Computer Science, 4497, 2007, 685–694
12. Selivanov V.L., “Fine hierarchies and m-reducibilities in theoretical computer science”, Theoret. Comput. Sci., 405:1-2 (2008), 116–163
13. Kosub S., Wagner K.W., “The boolean hierarchy of NP-partitions”, Inform. and Comput., 206:5 (2008), 538–568
14. Lehtonen E., “Labeled posets are universal”, European J. Combin., 29:2 (2008), 493–506
15. Kudinov O.V., Selivanov V.L., Zhukov A.V., “Definability in the $h$-quasiorder of labeled forests”, Ann. Pure Appl. Logic, 159:3 (2009), 318–332
16. Selivanov V.L., “Undecidability of some structures related to computation theory”, J. Logic Comput., 19:1 (2009), 177–197
17. Kudinov O.V., Selivanov V.L., “A Gandy Theorem for Abstract Structures and Applications to First-Order Definability”, Mathematical Theory and Computational Practice, Lecture Notes in Computer Science, 5635, 2009, 290–299
18. Selivanov V.L., “On the Wadge reducibility of $k$-partitions”, J. Log. Algebr. Program., 79:1 (2010), 92–102
19. A. V. Zhukov, O. V. Kudinov, V. L. Selivanov, “Definability of closure operations in the $h$-quasiorder of labeled forests”, Algebra and Logic, 49:2 (2010), 120–129
20. Kudinov O.V., Selivanov V.L., Zhukov A.V., “Undecidability in Weihrauch Degrees”, Programs, Proofs, Processes, Lecture Notes in Computer Science, 6158, 2010, 256–265
21. Kwuida L., Lehtonen E., “On the Homomorphism Order of Labeled Posets”, Order, 28:2 (2011), 251–265
22. Selivanov V., “Fine Hierarchies via Priestley Duality”, Ann. Pure Appl. Log., 163:8, SI (2012), 1075–1107
23. Hertling P., Selivanov V., “Complexity Issues For Preorders on Finite Labeled Forests”, Logic, Computation, Hierarchies, Ontos Mathematical Logic, 4, eds. Brattka V., Diener H., Spreen D., Walter de Gruyter Gmbh, 2014, 165–189
24. Zhukov A.V., “Some Notes on the Universality of Three-Orders on Finite Labeled Posets”, Logic, Computation, Hierarchies, Ontos Mathematical Logic, 4, eds. Brattka V., Diener H., Spreen D., Walter de Gruyter Gmbh, 2014, 393–409
25. Selivanov V., “Q-Wadge Degrees as Free Structures”, Computability, 9:3-4 (2020), 327–341
•  Number of views: This page: 361 Full text: 108 References: 46 First page: 1