Standard

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

Programs, Proofs, Processes (CiE 2010). 2010. стр. 246-255 (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); Том 6158).

Результаты исследований: Публикации в книгах, отчётах, сборниках, трудах конференций › статья в сборнике материалов конференции › научная › Рецензирование

Harvard

Kudinov, OV, Selivanov, VL & Yartseva, LV 2010, Definability in the subword order. в Programs, Proofs, Processes (CiE 2010). Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics), Том. 6158, стр. 246-255, 6th Conference on Computability in Europe, CiE 2010, Ponta Delgada, Azores, Португалия, 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. в Programs, Proofs, Processes (CiE 2010) (стр. 246-255). (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); Том 6158). https://doi.org/10.1007/978-3-642-13962-8_28

Vancouver

Kudinov OV, Selivanov VL, Yartseva LV. Definability in the subword order. в Programs, Proofs, Processes (CiE 2010). 2010. стр. 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. стр. 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