Abstract:
We introduce and study some natural operations on a structure of finite labeled forests, which is crucial in extending the difference hierarchy to the case of partitions. It is shown that the corresponding quotient algebra modulo the so-called h-equivalence is the simplest non-trivial semilattice with discrete closures. The algebra is also characterized as a free algebra in some quasivariety. Part of the results is generalized to countable labeled forests with finite chains.
Citation:
V. L. Selivanov, “The quotient algebra of labeled forests modulo h-equivalence”, Algebra Logika, 46:2 (2007), 217–243; Algebra and Logic, 46:2 (2007), 120–133
Victor Selivanov, Trends in Logic, 53, Well-Quasi Orders in Computation, Logic, Language and Reasoning, 2020, 271
Selivanov V., “Towards a Descriptive Theory of Cb(0)-Spaces”, Math. Struct. Comput. Sci., 27:8 (2017), 1553–1580
Victor L. Selivanov, Lecture Notes in Computer Science, 10307, Unveiling Dynamics and Complexity, 2017, 387
Spreen D., “the Life and Work of Victor l. Selivanov”, Logic, Computation, Hierarchies, Ontos Mathematical Logic, 4, ed. Brattka V. Diener H. Spreen D., Walter de Gruyter Gmbh, 2014, 1–8
Victor Selivanov, Lecture Notes in Computer Science, 6735, Models of Computation in Context, 2011, 260
Selivanov V.L., “On the Wadge reducibility of k-partitions”, J. Log. Algebr. Program., 79:1 (2010), 92–102
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
Selivanov V.L., “Fine hierarchies and m-reducibilities in theoretical computer science”, Theoret. Comput. Sci., 405:1-2 (2008), 116–163
Victor Selivanov, “On the Difference Hierarchy in Countably Based T0-Spaces”, Electronic Notes in Theoretical Computer Science, 221 (2008), 257
Citation in format AMSBIB
Contact us: