Standard

Turing computable embeddings, computable infinitary equivalence, and linear orders. / Bazhenov, Nikolay.

Unveiling Dynamics and Complexity - 13th Conference on Computability in Europe, CiE 2017, Proceedings. ред. / J Kari; F Manea; Petre. Том 10307 LNCS Springer-Verlag GmbH and Co. KG, 2017. стр. 141-151 (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); Том 10307 LNCS).

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

Harvard

Bazhenov, N 2017, Turing computable embeddings, computable infinitary equivalence, and linear orders. в J Kari, F Manea & Petre (ред.), Unveiling Dynamics and Complexity - 13th Conference on Computability in Europe, CiE 2017, Proceedings. Том. 10307 LNCS, Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics), Том. 10307 LNCS, Springer-Verlag GmbH and Co. KG, стр. 141-151, 13th Conference on Computability in Europe, CiE 2017, Turku, Финляндия, 12.06.2017. https://doi.org/10.1007/978-3-319-58741-7_15

APA

Bazhenov, N. (2017). Turing computable embeddings, computable infinitary equivalence, and linear orders. в J. Kari, F. Manea, & Petre (Ред.), Unveiling Dynamics and Complexity - 13th Conference on Computability in Europe, CiE 2017, Proceedings (Том 10307 LNCS, стр. 141-151). (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); Том 10307 LNCS). Springer-Verlag GmbH and Co. KG. https://doi.org/10.1007/978-3-319-58741-7_15

Vancouver

Bazhenov N. Turing computable embeddings, computable infinitary equivalence, and linear orders. в Kari J, Manea F, Petre, Редакторы, Unveiling Dynamics and Complexity - 13th Conference on Computability in Europe, CiE 2017, Proceedings. Том 10307 LNCS. Springer-Verlag GmbH and Co. KG. 2017. стр. 141-151. (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)). doi: 10.1007/978-3-319-58741-7_15

Author

Bazhenov, Nikolay. / Turing computable embeddings, computable infinitary equivalence, and linear orders. Unveiling Dynamics and Complexity - 13th Conference on Computability in Europe, CiE 2017, Proceedings. Редактор / J Kari ; F Manea ; Petre. Том 10307 LNCS Springer-Verlag GmbH and Co. KG, 2017. стр. 141-151 (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)).

BibTeX

@inproceedings{1ceaa447f0cc49de9b1cd81c9c08a051,
title = "Turing computable embeddings, computable infinitary equivalence, and linear orders",
abstract = "We study Turing computable embeddings for various classes of linear orders. The concept of a Turing computable embedding (or tc-embedding for short) was developed by Calvert, Cummins, Knight, and Miller as an effective counterpart for Borel embeddings. We are focused on tc-embeddings for classes equipped with computable infinitary Σα equivalence, denoted by ∼c α. In this paper, we isolate a natural subclass of linear orders, denoted by WMB, such that (WMB, ≅) is not universal under tc-embeddings, but for any computable ordinal α ≥ 5, (WMB, ∼c α) is universal under tc-embeddings. Informally speaking, WMB is not tc-universal, but it becomes tc-universal if one imposes some natural restrictions on the effective complexity of the syntax. We also give a complete syntactic characterization for classes (K, ≅) that are Turing computably embeddable into some specific classes (C, ≅) of well-orders. This extends the similar result of Knight, Miller, and Vanden Boom for the class of all finite linear orders Cfin.",
keywords = "Computable infinitary equivalence, Computable structure, Linear order, Ordinal, Turing computable embedding, ALGEBRAIC STRUCTURES, RECURSIVE STRUCTURES",
author = "Nikolay Bazhenov",
note = "Publisher Copyright: {\textcopyright} Springer International Publishing AG 2017.; 13th Conference on Computability in Europe, CiE 2017 ; Conference date: 12-06-2017 Through 16-06-2017",
year = "2017",
month = jan,
day = "1",
doi = "10.1007/978-3-319-58741-7_15",
language = "English",
isbn = "9783319587400",
volume = "10307 LNCS",
series = "Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)",
publisher = "Springer-Verlag GmbH and Co. KG",
pages = "141--151",
editor = "J Kari and F Manea and Petre",
booktitle = "Unveiling Dynamics and Complexity - 13th Conference on Computability in Europe, CiE 2017, Proceedings",
address = "Germany",

}

RIS

TY - GEN

T1 - Turing computable embeddings, computable infinitary equivalence, and linear orders

AU - Bazhenov, Nikolay

N1 - Publisher Copyright: © Springer International Publishing AG 2017.

PY - 2017/1/1

Y1 - 2017/1/1

N2 - We study Turing computable embeddings for various classes of linear orders. The concept of a Turing computable embedding (or tc-embedding for short) was developed by Calvert, Cummins, Knight, and Miller as an effective counterpart for Borel embeddings. We are focused on tc-embeddings for classes equipped with computable infinitary Σα equivalence, denoted by ∼c α. In this paper, we isolate a natural subclass of linear orders, denoted by WMB, such that (WMB, ≅) is not universal under tc-embeddings, but for any computable ordinal α ≥ 5, (WMB, ∼c α) is universal under tc-embeddings. Informally speaking, WMB is not tc-universal, but it becomes tc-universal if one imposes some natural restrictions on the effective complexity of the syntax. We also give a complete syntactic characterization for classes (K, ≅) that are Turing computably embeddable into some specific classes (C, ≅) of well-orders. This extends the similar result of Knight, Miller, and Vanden Boom for the class of all finite linear orders Cfin.

AB - We study Turing computable embeddings for various classes of linear orders. The concept of a Turing computable embedding (or tc-embedding for short) was developed by Calvert, Cummins, Knight, and Miller as an effective counterpart for Borel embeddings. We are focused on tc-embeddings for classes equipped with computable infinitary Σα equivalence, denoted by ∼c α. In this paper, we isolate a natural subclass of linear orders, denoted by WMB, such that (WMB, ≅) is not universal under tc-embeddings, but for any computable ordinal α ≥ 5, (WMB, ∼c α) is universal under tc-embeddings. Informally speaking, WMB is not tc-universal, but it becomes tc-universal if one imposes some natural restrictions on the effective complexity of the syntax. We also give a complete syntactic characterization for classes (K, ≅) that are Turing computably embeddable into some specific classes (C, ≅) of well-orders. This extends the similar result of Knight, Miller, and Vanden Boom for the class of all finite linear orders Cfin.

KW - Computable infinitary equivalence

KW - Computable structure

KW - Linear order

KW - Ordinal

KW - Turing computable embedding

KW - ALGEBRAIC STRUCTURES

KW - RECURSIVE STRUCTURES

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

U2 - 10.1007/978-3-319-58741-7_15

DO - 10.1007/978-3-319-58741-7_15

M3 - Conference contribution

AN - SCOPUS:85020849158

SN - 9783319587400

VL - 10307 LNCS

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

SP - 141

EP - 151

BT - Unveiling Dynamics and Complexity - 13th Conference on Computability in Europe, CiE 2017, Proceedings

A2 - Kari, J

A2 - Manea, F

A2 - Petre, null

PB - Springer-Verlag GmbH and Co. KG

T2 - 13th Conference on Computability in Europe, CiE 2017

Y2 - 12 June 2017 through 16 June 2017

ER -

ID: 10184739