Standard

Definability in the subword order. / Kudinov, Oleg V.; Selivanov, Victor L.; Yartseva, Lyudmila V.

Programs, Proofs, Processes (CiE 2010). 2010. p. 246-255 (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); Vol. 6158).

Research output: Chapter in Book/Report/Conference proceeding › Conference contribution › Research › peer-review

Harvard

Kudinov, OV, Selivanov, VL & Yartseva, LV 2010, Definability in the subword order. in Programs, Proofs, Processes (CiE 2010). Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics), vol. 6158, pp. 246-255, 6th Conference on Computability in Europe, CiE 2010, Ponta Delgada, Azores, Portugal, 30/06/10. https://doi.org/10.1007/978-3-642-13962-8_28

APA

Kudinov, O. V., Selivanov, V. L., & Yartseva, L. V. (2010). Definability in the subword order. In Programs, Proofs, Processes (CiE 2010) (pp. 246-255). (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); Vol. 6158). https://doi.org/10.1007/978-3-642-13962-8_28

Vancouver

Kudinov OV, Selivanov VL, Yartseva LV. Definability in the subword order. In Programs, Proofs, Processes (CiE 2010). 2010. p. 246-255. (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)). https://doi.org/10.1007/978-3-642-13962-8_28

Author

Kudinov, Oleg V. ; Selivanov, Victor L. ; Yartseva, Lyudmila V. / Definability in the subword order. Programs, Proofs, Processes (CiE 2010). 2010. pp. 246-255 (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)).

BibTeX

@inproceedings{1e1051ee7de243a8a6c7508b32b59e80,
title = "Definability in the subword order",
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 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 any arithmetical predicate invariant under the automorphisms of the structure is definable in the structure. {\textcopyright} 2010 Springer-Verlag Berlin Heidelberg.",
keywords = "automorphism, biinterpretability, definability, first-order theory, infix order, least fixed point, Subword order",
author = "Kudinov, {Oleg V.} and Selivanov, {Victor L.} and Yartseva, {Lyudmila V.}",
year = "2010",
month = jul,
day = "29",
doi = "10.1007/978-3-642-13962-8_28",
language = "English",
series = "Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)",
publisher = "Springer Nature",
pages = "246--255",
booktitle = "Programs, Proofs, Processes (CiE 2010)",
note = "6th Conference on Computability in Europe, CiE 2010 ; Conference date: 30-06-2010 Through 04-07-2010",

}

RIS

TY - GEN

T1 - Definability in the subword order

AU - Kudinov, Oleg V.

AU - Selivanov, Victor L.

AU - Yartseva, Lyudmila V.

PY - 2010/7/29

Y1 - 2010/7/29

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 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 any arithmetical predicate invariant under the automorphisms of the structure is definable in the structure. © 2010 Springer-Verlag Berlin Heidelberg.

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 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 any arithmetical predicate invariant under the automorphisms of the structure is definable in the structure. © 2010 Springer-Verlag Berlin Heidelberg.

KW - automorphism

KW - biinterpretability

KW - definability

KW - first-order theory

KW - infix order

KW - least fixed point

KW - Subword order

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

U2 - 10.1007/978-3-642-13962-8_28

DO - 10.1007/978-3-642-13962-8_28

M3 - Conference contribution

AN - SCOPUS:77954873164

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

SP - 246

EP - 255

BT - Programs, Proofs, Processes (CiE 2010)

T2 - 6th Conference on Computability in Europe, CiE 2010

Y2 - 30 June 2010 through 4 July 2010

ER -

ID: 127086235