TY - GEN

T1 - Undecidability in the homomorphic quasiorder of finite labeled forests

AU - Kudinov, Oleg V.

AU - Selivanov, Victor L.

PY - 2006/1/1

Y1 - 2006/1/1

N2 - We prove that the homomorphic quasiorder of finite k-labeled 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 finite k-labeled trees with a fixed label of the root element. © Springer-Verlag Berlin Heidelberg 2006.

AB - We prove that the homomorphic quasiorder of finite k-labeled 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 finite k-labeled trees with a fixed label of the root element. © Springer-Verlag Berlin Heidelberg 2006.

KW - Elementary theory

KW - Forest

KW - Homomorphic quasiorder

KW - Labeled tree

KW - Tree

KW - Undecidability

UR - http://www.scopus.com/inward/record.url?scp=33746089931&partnerID=8YFLogxK

U2 - 10.1007/11780342_31

DO - 10.1007/11780342_31

M3 - Conference contribution

AN - SCOPUS:33746089931

T3 - Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)

SP - 289

EP - 296

BT - Logical Approaches to Computational Barriers (CiE 2006)

T2 - computability in europe-2006

Y2 - 30 June 2006

ER -