Logical Approaches to Computational Barriers

Undecidability in the Homomorphic Quasiorder of Finite Labeled Forests

Speaker:
| Victor Selivanov |

Author(s): |
Oleg Kudinov and Victor Selivanov |

Slot: |
Array, 14:50-15:10, 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 |