Standard
Well-Orders Realized by C.E. Equivalence Relations. / Bazhenov, Nikolay; Zubkov, Maxim.
Revolutions and Revelations in Computability - 18th Conference on Computability in Europe, CiE 2022, Proceedings. ed. / Ulrich Berger; Arno Pauly; Johanna N.Y. Franklin; Florin Manea. Springer Science and Business Media Deutschland GmbH, 2022. p. 13-23 (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); Vol. 13359 LNCS).
Research output: Chapter in Book/Report/Conference proceeding › Conference contribution › Research › peer-review
Harvard
Bazhenov, N & Zubkov, M 2022,
Well-Orders Realized by C.E. Equivalence Relations. in U Berger, A Pauly, JNY Franklin & F Manea (eds),
Revolutions and Revelations in Computability - 18th Conference on Computability in Europe, CiE 2022, Proceedings. Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics), vol. 13359 LNCS, Springer Science and Business Media Deutschland GmbH, pp. 13-23, 18th Conference on Computability in Europe, CiE 2022, Swansea, United Kingdom,
11.07.2022.
https://doi.org/10.1007/978-3-031-08740-0_2
APA
Bazhenov, N., & Zubkov, M. (2022).
Well-Orders Realized by C.E. Equivalence Relations. In U. Berger, A. Pauly, J. N. Y. Franklin, & F. Manea (Eds.),
Revolutions and Revelations in Computability - 18th Conference on Computability in Europe, CiE 2022, Proceedings (pp. 13-23). (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); Vol. 13359 LNCS). Springer Science and Business Media Deutschland GmbH.
https://doi.org/10.1007/978-3-031-08740-0_2
Vancouver
Bazhenov N, Zubkov M.
Well-Orders Realized by C.E. Equivalence Relations. In Berger U, Pauly A, Franklin JNY, Manea F, editors, Revolutions and Revelations in Computability - 18th Conference on Computability in Europe, CiE 2022, Proceedings. Springer Science and Business Media Deutschland GmbH. 2022. p. 13-23. (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)). doi: 10.1007/978-3-031-08740-0_2
Author
Bazhenov, Nikolay ; Zubkov, Maxim. /
Well-Orders Realized by C.E. Equivalence Relations. Revolutions and Revelations in Computability - 18th Conference on Computability in Europe, CiE 2022, Proceedings. editor / Ulrich Berger ; Arno Pauly ; Johanna N.Y. Franklin ; Florin Manea. Springer Science and Business Media Deutschland GmbH, 2022. pp. 13-23 (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)).
BibTeX
@inproceedings{a97fd96869ae4a8badd859bc319fdac7,
title = "Well-Orders Realized by C.E. Equivalence Relations",
abstract = "We study countable linear orders realized by computably enumerable equivalence relations (ceers). A ceer E realizes a linear order L if there exists a computably enumerable binary relation ⊴ respecting E such that the induced quotient structure (N/ E, ⊴ ) is isomorphic to L. In this line of research, there are many nontrivial results demonstrating complex interplay between the computability-theoretic properties of a ceer E and the isomorphism types of orders L realizable by E. For example, Gavryushkin, Khoussainov, and Stephan proved that there is a ceer E realizing only one order type—the type of ω+ 1 + ω∗. In this paper, we obtain a complete characterization of well-orders L realizable by a given ceer E for the case when E realizes some ordinal α< ω3. Informally speaking, our proofs develop methods of fine-tuning the behavior of limit points of L via computability-theoretic properties of E.",
keywords = "Computable ordinal, Computable structure theory, Computably enumerable structure, Equivalence relation, Well-order",
author = "Nikolay Bazhenov and Maxim Zubkov",
note = "Funding Information: The work of N. Bazhenov was supported by the Russian Science Foundation (project no. 18-11-00028). The work of M. Zubkov was supported by the Russian Science Foundation (project no. 18-11-00028) and performed under the development program of the Volga Region Mathematical Center (agreement no. 075-02-2020-1478). Publisher Copyright: {\textcopyright} 2022, The Author(s), under exclusive license to Springer Nature Switzerland AG.; 18th Conference on Computability in Europe, CiE 2022 ; Conference date: 11-07-2022 Through 15-07-2022",
year = "2022",
doi = "10.1007/978-3-031-08740-0_2",
language = "English",
isbn = "9783031087394",
series = "Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)",
publisher = "Springer Science and Business Media Deutschland GmbH",
pages = "13--23",
editor = "Ulrich Berger and Arno Pauly and Franklin, {Johanna N.Y.} and Florin Manea",
booktitle = "Revolutions and Revelations in Computability - 18th Conference on Computability in Europe, CiE 2022, Proceedings",
address = "Germany",
}
RIS
TY - GEN
T1 - Well-Orders Realized by C.E. Equivalence Relations
AU - Bazhenov, Nikolay
AU - Zubkov, Maxim
N1 - Funding Information:
The work of N. Bazhenov was supported by the Russian Science Foundation (project no. 18-11-00028). The work of M. Zubkov was supported by the Russian Science Foundation (project no. 18-11-00028) and performed under the development program of the Volga Region Mathematical Center (agreement no. 075-02-2020-1478).
Publisher Copyright:
© 2022, The Author(s), under exclusive license to Springer Nature Switzerland AG.
PY - 2022
Y1 - 2022
N2 - We study countable linear orders realized by computably enumerable equivalence relations (ceers). A ceer E realizes a linear order L if there exists a computably enumerable binary relation ⊴ respecting E such that the induced quotient structure (N/ E, ⊴ ) is isomorphic to L. In this line of research, there are many nontrivial results demonstrating complex interplay between the computability-theoretic properties of a ceer E and the isomorphism types of orders L realizable by E. For example, Gavryushkin, Khoussainov, and Stephan proved that there is a ceer E realizing only one order type—the type of ω+ 1 + ω∗. In this paper, we obtain a complete characterization of well-orders L realizable by a given ceer E for the case when E realizes some ordinal α< ω3. Informally speaking, our proofs develop methods of fine-tuning the behavior of limit points of L via computability-theoretic properties of E.
AB - We study countable linear orders realized by computably enumerable equivalence relations (ceers). A ceer E realizes a linear order L if there exists a computably enumerable binary relation ⊴ respecting E such that the induced quotient structure (N/ E, ⊴ ) is isomorphic to L. In this line of research, there are many nontrivial results demonstrating complex interplay between the computability-theoretic properties of a ceer E and the isomorphism types of orders L realizable by E. For example, Gavryushkin, Khoussainov, and Stephan proved that there is a ceer E realizing only one order type—the type of ω+ 1 + ω∗. In this paper, we obtain a complete characterization of well-orders L realizable by a given ceer E for the case when E realizes some ordinal α< ω3. Informally speaking, our proofs develop methods of fine-tuning the behavior of limit points of L via computability-theoretic properties of E.
KW - Computable ordinal
KW - Computable structure theory
KW - Computably enumerable structure
KW - Equivalence relation
KW - Well-order
UR - http://www.scopus.com/inward/record.url?scp=85134154492&partnerID=8YFLogxK
UR - https://www.mendeley.com/catalogue/de5da316-c2dc-3b43-b93a-90bca0e530a7/
U2 - 10.1007/978-3-031-08740-0_2
DO - 10.1007/978-3-031-08740-0_2
M3 - Conference contribution
AN - SCOPUS:85134154492
SN - 9783031087394
T3 - Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
SP - 13
EP - 23
BT - Revolutions and Revelations in Computability - 18th Conference on Computability in Europe, CiE 2022, Proceedings
A2 - Berger, Ulrich
A2 - Pauly, Arno
A2 - Franklin, Johanna N.Y.
A2 - Manea, Florin
PB - Springer Science and Business Media Deutschland GmbH
T2 - 18th Conference on Computability in Europe, CiE 2022
Y2 - 11 July 2022 through 15 July 2022
ER -
