Аннотация:
Булева иерархия разбиений была введена и изучалась К. Вагнером и С. Косубом, в основном над решеткой NP-множеств. Эта иерархия рассматривается над решетками со свойством редукции и показывается, что в этом случае иерархия устроена намного проще. Дается полная характеризация этой иерархии над некоторыми важными решетками, в частности, над решеткой рекурсивно перечислимых множеств и над решеткой открытых множеств бэровского пространства.
Ключевые слова:
булева иерархия разбиений, решетка со свойством редукции, решетка рекурсивно перечислимых множеств, решетка открытых множеств бэровского пространства.
Образец цитирования:
В. Л. Селиванов, “Булевы иерархии разбиений над редуцируемой базой”, Алгебра и логика, 43:1 (2004), 77–109; Algebra and Logic, 43:1 (2004), 44–61
Vladimir Podolskii, Victor Selivanov, “Complexity Aspects of the Extension of Wagner's Hierarchy to k-Partitions”, Electron. Proc. Theor. Comput. Sci., 407 (2024), 186
RAPHAËL CARROY, LUCA MOTTO ROS, SALVATORE SCAMPERTI, “A CLASSIFICATION OF THE WADGE HIERARCHIES ON ZERO-DIMENSIONAL POLISH SPACES”, J. symb. log., 2023, 1
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
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
Selivanov V., “Fine Hierarchies via Priestley Duality”, Ann. Pure Appl. Log., 163:8, SI (2012), 1075–1107
Kwuida L., Lehtonen E., “On the Homomorphism Order of Labeled Posets”, Order, 28:2 (2011), 251–265
Victor Selivanov, Lecture Notes in Computer Science, 6735, Models of Computation in Context, 2011, 260
Peter Hertling, Victor Selivanov, Lecture Notes in Computer Science, 6735, Models of Computation in Context, 2011, 112
Selivanov V.L., “On the Wadge reducibility of $k$-partitions”, J. Log. Algebr. Program., 79:1 (2010), 92–102
А. В. Жуков, О. В. Кудинов, В. Л. Селиванов, “Определимость операций замыкания в $h$-предпорядке размеченных лесов”, Алгебра и логика, 49:2 (2010), 181–194; 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
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
Selivanov V.L., “Undecidability of some structures related to computation theory”, J. Logic Comput., 19:1 (2009), 177–197
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
Selivanov V.L., “Fine hierarchies and m-reducibilities in theoretical computer science”, Theoret. Comput. Sci., 405:1-2 (2008), 116–163
Kosub S., Wagner K.W., “The boolean hierarchy of NP-partitions”, Inform. and Comput., 206:5 (2008), 538–568
Lehtonen E., “Labeled posets are universal”, European J. Combin., 29:2 (2008), 493–506
Victor Selivanov, “On the Difference Hierarchy in Countably Based T0-Spaces”, Electronic Notes in Theoretical Computer Science, 221 (2008), 257
Victor Selivanov, “On the Wadge Reducibility of k-Partitions”, Electronic Notes in Theoretical Computer Science, 202 (2008), 59
Цитирование в формате AMSBIB
Обратная связь: