Undecidability in the Homomorphic Quasiorder of Finite Labeled Forests

摘要

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