Computability in Europe 2006
Logical Approaches to Computational Barriers

Print current page  Print this page

Regular Talk:
Undecidability in the Homomorphic Quasiorder  of Finite Labeled Forests

Speaker: Victor Selivanov
Author(s): Oleg Kudinov and Victor Selivanov
Slot: Tue, 14:50-15:10, Faraday B (col. 2)


We prove that the homomorphic quasiorder of finite k-labeled forests
has undecidable elementary theory for k> 2, in contrast to the known
decidability result for $k=2$. We establish also undecidablity (again
for every $k\geq 3$) of elementary theories of two other relevant
structures: the homomorphic quasiorder of finite k-labeled trees, and
of finite k-labeled trees with a fixed label of the root element. 

websites: Arnold Beckmann 2006-06-23 Valid HTML 4.01! Valid CSS! eXTReMe Tracker hit counters by