Standard
On the Complexity of Conversion Between Classic Real Number Representations. / Kristiansen, Lars; Simonsen, Jakob Grue.
Beyond the Horizon of Computability - 16th Conference on Computability in Europe, CiE 2020, Proceedings. ed. / Marcella Anselmo; Gianluca Della Vedova; Florin Manea; Arno Pauly. Springer VS, 2020. p. 75-86 (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics), Vol. 12098 LNCS).
Research output: Chapter in Book/Report/Conference proceeding › Article in proceedings › Research › peer-review
Harvard
Kristiansen, L
& Simonsen, JG 2020,
On the Complexity of Conversion Between Classic Real Number Representations. in M Anselmo, G Della Vedova, F Manea & A Pauly (eds),
Beyond the Horizon of Computability - 16th Conference on Computability in Europe, CiE 2020, Proceedings. Springer VS, Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics), vol. 12098 LNCS, pp. 75-86, 16th Conference on Computability in Europe, CiE 2020, Fisciano, Italy,
29/06/2020.
https://doi.org/10.1007/978-3-030-51466-2_7APA
Kristiansen, L.
, & Simonsen, J. G. (2020).
On the Complexity of Conversion Between Classic Real Number Representations. In M. Anselmo, G. Della Vedova, F. Manea, & A. Pauly (Eds.),
Beyond the Horizon of Computability - 16th Conference on Computability in Europe, CiE 2020, Proceedings (pp. 75-86). Springer VS. Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics) Vol. 12098 LNCS
https://doi.org/10.1007/978-3-030-51466-2_7Vancouver
Kristiansen L
, Simonsen JG.
On the Complexity of Conversion Between Classic Real Number Representations. In Anselmo M, Della Vedova G, Manea F, Pauly A, editors, Beyond the Horizon of Computability - 16th Conference on Computability in Europe, CiE 2020, Proceedings. Springer VS. 2020. p. 75-86. (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics), Vol. 12098 LNCS).
https://doi.org/10.1007/978-3-030-51466-2_7Author
Kristiansen, Lars ; Simonsen, Jakob Grue. / On the Complexity of Conversion Between Classic Real Number Representations. Beyond the Horizon of Computability - 16th Conference on Computability in Europe, CiE 2020, Proceedings. editor / Marcella Anselmo ; Gianluca Della Vedova ; Florin Manea ; Arno Pauly. Springer VS, 2020. pp. 75-86 (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics), Vol. 12098 LNCS).
Bibtex
@inproceedings{9fba61302c0244e49c2be3cba86ba75d,
title = "On the Complexity of Conversion Between Classic Real Number Representations",
abstract = "It is known that while it is possible to convert between many different representations of irrational numbers (e.g., between Dedekind cuts and Cauchy sequences), it is in general not possible to do so subrecursively: conversions in general need to perform unbounded search. This raises the question of categorizing the pairs of representations between which either subrecursive conversion is possible, or is not possible. The purpose of this paper is to prove the following positive result: for a number of well-known representations (Beatty sequences, Dedekind cuts, General base expansions, Hurwitz characteristics, and Locators) conversion between the representations can be performed effectively and with good subrecursive bounds.",
keywords = "Computable analysis, Computational complexity, Representation of irrational numbers, Subrecursion",
author = "Lars Kristiansen and Simonsen, {Jakob Grue}",
year = "2020",
doi = "10.1007/978-3-030-51466-2_7",
language = "English",
isbn = "9783030514655",
series = "Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)",
publisher = "Springer VS",
pages = "75--86",
editor = "Marcella Anselmo and {Della Vedova}, Gianluca and Florin Manea and Arno Pauly",
booktitle = "Beyond the Horizon of Computability - 16th Conference on Computability in Europe, CiE 2020, Proceedings",
note = "16th Conference on Computability in Europe, CiE 2020 ; Conference date: 29-06-2020 Through 03-07-2020",
}
RIS
TY - GEN
T1 - On the Complexity of Conversion Between Classic Real Number Representations
AU - Kristiansen, Lars
AU - Simonsen, Jakob Grue
PY - 2020
Y1 - 2020
N2 - It is known that while it is possible to convert between many different representations of irrational numbers (e.g., between Dedekind cuts and Cauchy sequences), it is in general not possible to do so subrecursively: conversions in general need to perform unbounded search. This raises the question of categorizing the pairs of representations between which either subrecursive conversion is possible, or is not possible. The purpose of this paper is to prove the following positive result: for a number of well-known representations (Beatty sequences, Dedekind cuts, General base expansions, Hurwitz characteristics, and Locators) conversion between the representations can be performed effectively and with good subrecursive bounds.
AB - It is known that while it is possible to convert between many different representations of irrational numbers (e.g., between Dedekind cuts and Cauchy sequences), it is in general not possible to do so subrecursively: conversions in general need to perform unbounded search. This raises the question of categorizing the pairs of representations between which either subrecursive conversion is possible, or is not possible. The purpose of this paper is to prove the following positive result: for a number of well-known representations (Beatty sequences, Dedekind cuts, General base expansions, Hurwitz characteristics, and Locators) conversion between the representations can be performed effectively and with good subrecursive bounds.
KW - Computable analysis
KW - Computational complexity
KW - Representation of irrational numbers
KW - Subrecursion
UR - http://www.scopus.com/inward/record.url?scp=85088210085&partnerID=8YFLogxK
U2 - 10.1007/978-3-030-51466-2_7
DO - 10.1007/978-3-030-51466-2_7
M3 - Article in proceedings
AN - SCOPUS:85088210085
SN - 9783030514655
T3 - Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
SP - 75
EP - 86
BT - Beyond the Horizon of Computability - 16th Conference on Computability in Europe, CiE 2020, Proceedings
A2 - Anselmo, Marcella
A2 - Della Vedova, Gianluca
A2 - Manea, Florin
A2 - Pauly, Arno
PB - Springer VS
T2 - 16th Conference on Computability in Europe, CiE 2020
Y2 - 29 June 2020 through 3 July 2020
ER -
