Logical Approaches to Computational Barriers

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 |