Definability in the Infix Order on Words

被引：0

作者：

Kudinov, Oleg V. ^{[1
]}

Selivanov, Victor L. ^{[2
]}

机构：

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

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

来源：

DEVELOPMENTS IN LANGUAGE THEORY, PROCEEDINGS | 2009年 / 5583卷

关键词：

Infix order; definability; automorphism; least fixed point; first-order theory; biinterpretability; HOMOMORPHIC QUASIORDER;

D O I：

暂无

中图分类号：

TP301 [理论、方法];

学科分类号：

081202 ;

摘要：

We develop a theory of (first-order) definabitity in the infix partial order on words in parallel with a similar theory for the h-quasiorder of finite k-labeled forests. In particular, any element is definable (provided that words of length I or 2 are taken as parameters), the first-order theory of the structure is atomic and computably isomorphic to the first-order arithmetic. We also characterize the automorphism group of the structure and show that any arithmetical predicate invariant under the automorphisms of the structure is definable in the structure.

引用

页码：454 / +

页数：3

共 17 条

[1]

[Anonymous], 1996, Definability and Computability

[2]

[Anonymous], 1990, HDB THEORETICAL COMP

[3]

[Anonymous], 1993, ENCY MATH APPL, DOI DOI 10.1017/CBO9780511551574

[4]

Barwise J., 1975, Admissible Sets and Structures, V7

[5]

Hertling P., 1993, TOPOLOGISCHE KOMPLEX, V152

[6] Elementary theory of free non-abelian groups [J].

Kharlampovich, Olga ;

Myasnikov, Alexei .

JOURNAL OF ALGEBRA, 2006, 302 (02) :451-552

[7] Undecidability in the homomorphic quasiorder of finite labelled forests [J].

Kudinov, Oleg V. ;

Selivanov, Victor L. .

JOURNAL OF LOGIC AND COMPUTATION, 2007, 17 (06) :1135-1151

[8]

Kudinov OV, 2007, LECT NOTES COMPUT SC, V4497, P436

[9] Definability in the h-quasiorder of labeled forests [J].

Kudinov, Oleg V. ;

Selivanov, Victor L. ;

Zhukov, Anton V. .

ANNALS OF PURE AND APPLIED LOGIC, 2009, 159 (03) :318-332

[10]

KUDINOV OV, 2009, LNCS VOLUME IN PRESS

← 1 2 →