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






Personal entry:
Login:
Password:
Save password
Enter
Forgotten password?
Register


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

This article is cited in 25 scientific papers (total in 25 papers)

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
Received: 11.09.2001
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}


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

    SHARE: VKontakte.ru FaceBook Twitter Mail.ru Livejournal Memori.ru


    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  mathnet  mathscinet  zmath
    2. Lehtonen E., “Descending chains and antichains of the unary, linear, and monotone subfunction relations”, Order, 23:2-3 (2006), 129–142  crossref  mathscinet  zmath  isi  scopus
    3. Selivanov V.L., “Towards a descriptive set theory for domain-like structures”, Theoret. Comput. Sci., 365:3 (2006), 258–282  crossref  mathscinet  zmath  isi  elib  scopus
    4. Kuske D., “Theories of orders on the set of words”, Theor. Inform. Appl., 40:1 (2006), 53–74  crossref  mathscinet  zmath  isi  scopus
    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  crossref  zmath  isi  scopus
    6. V. L. Selivanov, “The quotient algebra of labeled forests modulo $h$-equivalence”, Algebra and Logic, 46:2 (2007), 120–133  mathnet  crossref  mathscinet  zmath  isi  elib  elib
    7. Z. G. Khisamiev, “Distributive lattices of numberings”, Algebra and Logic, 46:1 (2007), 50–61  mathnet  crossref  mathscinet  zmath  isi
    8. Kudinov O.V., Selivanov V.L., “Undecidability in the homomorphic quasiorder of finite labelled forests”, J. Logic Comput., 17:6 (2007), 1135–1151  crossref  mathscinet  zmath  isi  elib  scopus
    9. Selivanov V.L., “Hierarchies of $\Delta^0_2$-measurable $k$-partitions”, MLQ Math. Log. Q., 53:4-5 (2007), 446–461  crossref  mathscinet  zmath  isi  scopus
    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  crossref  mathscinet  zmath  isi  scopus
    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  crossref  mathscinet  zmath  isi  scopus
    12. Selivanov V.L., “Fine hierarchies and m-reducibilities in theoretical computer science”, Theoret. Comput. Sci., 405:1-2 (2008), 116–163  crossref  mathscinet  zmath  isi  elib  scopus
    13. Kosub S., Wagner K.W., “The boolean hierarchy of NP-partitions”, Inform. and Comput., 206:5 (2008), 538–568  crossref  mathscinet  zmath  isi  scopus
    14. Lehtonen E., “Labeled posets are universal”, European J. Combin., 29:2 (2008), 493–506  crossref  mathscinet  zmath  isi  elib  scopus
    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  crossref  mathscinet  zmath  isi  elib  scopus
    16. Selivanov V.L., “Undecidability of some structures related to computation theory”, J. Logic Comput., 19:1 (2009), 177–197  crossref  mathscinet  zmath  isi  elib  scopus
    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  crossref  mathscinet  zmath  isi  scopus
    18. Selivanov V.L., “On the Wadge reducibility of $k$-partitions”, J. Log. Algebr. Program., 79:1 (2010), 92–102  crossref  mathscinet  zmath  isi  scopus
    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  mathnet  crossref  mathscinet  zmath  isi
    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  crossref  mathscinet  zmath  adsnasa  isi  scopus
    21. Kwuida L., Lehtonen E., “On the Homomorphism Order of Labeled Posets”, Order, 28:2 (2011), 251–265  crossref  mathscinet  zmath  isi  scopus
    22. Selivanov V., “Fine Hierarchies via Priestley Duality”, Ann. Pure Appl. Log., 163:8, SI (2012), 1075–1107  crossref  mathscinet  zmath  isi  elib  scopus
    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  mathscinet  isi
    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  mathscinet  isi
    25. Selivanov V., “Q-Wadge Degrees as Free Structures”, Computability, 9:3-4 (2020), 327–341  crossref  mathscinet  zmath  isi  scopus
  • Алгебра и логика Algebra and Logic
    Number of views:
    This page:361
    Full text:108
    References:46
    First page:1

     
    Contact us:
     Terms of Use  Registration to the website  Logotypes © Steklov Mathematical Institute RAS, 2022