Undecidability in the homomorphic quasiorder of finite labeled forests

被引：11

作者：

Kudinov, Oleg V. ^{[1
]}

Selivanov, Victor L.

机构：

[1] Russian Acad Sci, SL Sobolev Inst Math, Siberian Div, Novosibirsk 630090, Russia

[2] Russian Acad Sci, AP Ershov Inst Informat Syst, Siberian Div, Moscow 117901, Russia

来源：

LOGICAL APPROACHES TO COMPUTATIONAL BARRIERS, PROCEEDINGS | 2006年 / 3988卷

关键词：

tree; labeled tree; forest; homomorphic quasiorder; undecidability; elementary theory;

D O I：

10.1007/11780342_31

中图分类号：

TP301 [理论、方法];

学科分类号：

081202 ;

摘要：

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.

引用

页码：289 / +

页数：2