Undecidability in the homomorphic quasiorder of finite labelled forests

被引：12

作者：

Kudinov, Oleg V. ^{[1
]}

Selivanov, Victor L. ^{[2
,3
]}

机构：

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

[2] Univ Wurzburg, D-97070 Wurzburg, Germany

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

来源：

JOURNAL OF LOGIC AND COMPUTATION | 2007年 / 17卷 / 06期

关键词：

labelled tree; forest; homomorphic quasiorder; undecidability; theory;

D O I：

10.1093/logcom/exm038

中图分类号：

TP301 [理论、方法];

学科分类号：

081202 ;

摘要：

We prove that the homomorphic quasiorder of finite k-labelled forests has a hereditary undecidable first-order theory for k >= 3, in contrast to the known decidability result for k = 2. We establish also hereditary undecidability (again for every k >= 3) of first-order theories of two other relevant structures: the homomorphic quasiorder of finite k-labelled trees, and of finite k-labelled trees with a fixed label of the root element. Finally, all three first-order theories are shown to be computably isomorphic to the first-order arithmetic.

引用

页码：1135 / 1151

页数：17

共 15 条

[1]

Davey B.A., 1994, INTRO LATTICES ORDER

[2]

ERSHOV YL, 1965, DOKL AKAD NAUK SSSR+, V161, P27

[3]

Ershov Yu. L., 1965, USP MAT NAUK, V20, P37

[4]

HERTLING P, 1993, TOPOLOGISCHE KOMPLEX

[5]

Kosub S, 2000, LECT NOTES COMPUT SC, V1770, P157

[6]

KOSUB S, 2000, LECT NOTES COMPUTER, V1893, P467

[7]

Kruskal Joseph, 1972, J COMBINATORIAL TH A, V13, P297, DOI DOI 10.1016/0097-3165(72)90063-5

[8] Undecidability in the homomorphic quasiorder of finite labeled forests [J].

Kudinov, Oleg V. ;

Selivanov, Victor L. .

LOGICAL APPROACHES TO COMPUTATIONAL BARRIERS, PROCEEDINGS, 2006, 3988 :289-+

[9]

KUSKE D, 2006, THEORETICAL INFORM A, V40, P53

[10]

ROGERS H, 1967, THOERY RECURSIVE FUN

← 1 2 →