Computability in Europe 2006
Logical Approaches to Computational Barriers

Regular Talk:
The Algebra of Labeled Forests  Modulo Homomorphic Equivalence

Speaker: Victor Selivanov
Slot: Array, 14:30-14:50, col. 2


We introduce and study some natural operations on the homomorphic
quasiorder  of finite labeled forests which is of central
interest for extending the difference hierarchy to the case of
partitions. It is shown that the corresponding algebra is the simplest
nontrivial semilattice with discrete closures. The algebra is also
characterized as a free algebra in some quasivariety. Some of results
are generalized to countable labeled forests without infinite chains. 

websites: Arnold Beckmann 2006-04-21