RUS  ENG
Full version
JOURNALS // Algebra i logika

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

Boolean Hierarchies of Partitions over a Reducible Base
V. L. Selivanov

References

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  mathscinet  zmath
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  mathscinet  zmath
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  mathnet  mathscinet
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  mathscinet  zmath
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  mathscinet  zmath
9. J. B. Kruskal, “The theory of well-quasi-ordering: a frequently discovered concept”, J. Comb. Theory, Ser. A, 13:3 (1972), 297–305  crossref  mathscinet  zmath
10. J. B. Kruskal, “Well-quasi-ordering, the tree theorem, and Varzsonyi's conjecture”, Trans. Am. Math. Soc., 95:2 (1960), 210–225  crossref  mathscinet  zmath
11. Yu. L. Ershov, Teoriya numeratsii, Nauka, M., 1977  mathscinet
12. V. L. Selivanov, “Fine hierarchies and Boolean terms”, J. Symb. Log., 60:1 (1995), 289–317  crossref  mathscinet  zmath
13. H. Rogers, Theory of recursive functions and effective computability, McGrow Hill, New York, 1967  mathscinet  zmath
14. Y. L. Ershov, “Theorie der Numerierungen I”, Z. math. Log. Grundl. Math., 19:4 (1973), 289–388  mathscinet
15. Y. L. Ershov, “Theorie der Numerierungen II”, Z. math. Log. Grundl. Math., 21:6 (1975), 473–584  mathscinet  zmath
16. Yu. L. Ershov, “Ob odnoi ierarkhii mnozhestv III”, Algebra i logika, 9:1 (1970), 34–51  mathnet  mathscinet  zmath
17. Y. N. Moschovakis, Descriptive set theory, North-Holland, Amsterdam, 1980  mathscinet  zmath
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  crossref  mathscinet  zmath
20. V. L. Selivanov, Boolean hierarchy of partitions over reducible bases, Technical report 276, Institut für Informatik, Univ. Würzburg, 2001


© Steklov Math. Inst. of RAS, 2025