Definability in the structure of words with the inclusion relation

Standard

Definability in the structure of words with the inclusion relation. / Kudinov, Oleg V.; Selivanov, Victor L.; Yartseva, Lyudmila V.

In: Siberian Mathematical Journal, Vol. 51, No. 3, 01.07.2010, p. 456-462.

Research output: Contribution to journal › Article › peer-review

Author

Kudinov, Oleg V. ; Selivanov, Victor L. ; Yartseva, Lyudmila V. / Definability in the structure of words with the inclusion relation. In: Siberian Mathematical Journal. 2010 ; Vol. 51, No. 3. pp. 456-462.

BibTeX

@article{f683982e3bf349a183bb10be770fed04,

title = "Definability in the structure of words with the inclusion relation",

abstract = "We develop a theory of (first-order) definability in the subword partial order in parallel with similar theories for the h-quasiorder of finite k-labeled forests and for the infix order. In particular, any element is definable (provided that the words of length 1 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 every predicate invariant under the automorphisms of the structure is definable in the structure. {\textcopyright} 2010 Pleiades Publishing, Ltd.",

keywords = "Automorphism, Bi-interpretability, Definability, First-order theory, Infix order, Least fixed point, Subword",

author = "Kudinov, {Oleg V.} and Selivanov, {Victor L.} and Yartseva, {Lyudmila V.}",

year = "2010",

month = jul,

day = "1",

doi = "10.1007/s11202-010-0047-y",

language = "English",

volume = "51",

pages = "456--462",

journal = "Siberian Mathematical Journal",

issn = "0037-4466",

publisher = "Springer Nature",

number = "3",

}

RIS

TY - JOUR

T1 - Definability in the structure of words with the inclusion relation

AU - Kudinov, Oleg V.

AU - Selivanov, Victor L.

AU - Yartseva, Lyudmila V.

PY - 2010/7/1

Y1 - 2010/7/1

N2 - We develop a theory of (first-order) definability in the subword partial order in parallel with similar theories for the h-quasiorder of finite k-labeled forests and for the infix order. In particular, any element is definable (provided that the words of length 1 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 every predicate invariant under the automorphisms of the structure is definable in the structure. © 2010 Pleiades Publishing, Ltd.

AB - We develop a theory of (first-order) definability in the subword partial order in parallel with similar theories for the h-quasiorder of finite k-labeled forests and for the infix order. In particular, any element is definable (provided that the words of length 1 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 every predicate invariant under the automorphisms of the structure is definable in the structure. © 2010 Pleiades Publishing, Ltd.

KW - Automorphism

KW - Bi-interpretability

KW - Definability

KW - First-order theory

KW - Infix order

KW - Least fixed point

KW - Subword

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

U2 - 10.1007/s11202-010-0047-y

DO - 10.1007/s11202-010-0047-y

M3 - Article

AN - SCOPUS:77954001507

VL - 51

SP - 456

EP - 462

JO - Siberian Mathematical Journal

JF - Siberian Mathematical Journal

SN - 0037-4466

IS - 3

ER -

ID: 127086587