Computability in Europe 2006
Logical Approaches to Computational Barriers
Logical Approaches to Computational Barriers
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) |
Abstract
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
|