Standard
Liouville Numbers and the Computational Complexity of Changing Bases. / Jakobsen, Sune Kristian; 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. 50-62 (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
Jakobsen, SK
& Simonsen, JG 2020,
Liouville Numbers and the Computational Complexity of Changing Bases. 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. 50-62, 16th Conference on Computability in Europe, CiE 2020, Fisciano, Italy,
29/06/2020.
https://doi.org/10.1007/978-3-030-51466-2_5APA
Jakobsen, S. K.
, & Simonsen, J. G. (2020).
Liouville Numbers and the Computational Complexity of Changing Bases. 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. 50-62). 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_5Vancouver
Jakobsen SK
, Simonsen JG.
Liouville Numbers and the Computational Complexity of Changing Bases. 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. 50-62. (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_5Author
Jakobsen, Sune Kristian ; Simonsen, Jakob Grue. / Liouville Numbers and the Computational Complexity of Changing Bases. 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. 50-62 (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics), Vol. 12098 LNCS).
Bibtex
@inproceedings{e11a44b1e74146bd8a555868f1e7cefc,
title = "Liouville Numbers and the Computational Complexity of Changing Bases",
abstract = "We study the computational complexity of uniformly converting the base-a expansion of an irrational numbers to the base-b expansion. In particular, we are interested in subsets of the irrationals where such conversion can be performed with little overhead. We show that such conversion is possible, essentially with polynomial overhead, for the set of irrationals that are not Liouville numbers. Furthermore, it is known that there are irrational numbers x such that the expansion of x in one integer base is efficiently computable, but the expansion of x in certain other integer bases is not. We prove that any such number must be a Liouville number.",
keywords = "Computability, Computational complexity, Diophantine approximation, Number theory",
author = "Jakobsen, {Sune Kristian} and Simonsen, {Jakob Grue}",
year = "2020",
doi = "10.1007/978-3-030-51466-2_5",
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 = "50--62",
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 - Liouville Numbers and the Computational Complexity of Changing Bases
AU - Jakobsen, Sune Kristian
AU - Simonsen, Jakob Grue
PY - 2020
Y1 - 2020
N2 - We study the computational complexity of uniformly converting the base-a expansion of an irrational numbers to the base-b expansion. In particular, we are interested in subsets of the irrationals where such conversion can be performed with little overhead. We show that such conversion is possible, essentially with polynomial overhead, for the set of irrationals that are not Liouville numbers. Furthermore, it is known that there are irrational numbers x such that the expansion of x in one integer base is efficiently computable, but the expansion of x in certain other integer bases is not. We prove that any such number must be a Liouville number.
AB - We study the computational complexity of uniformly converting the base-a expansion of an irrational numbers to the base-b expansion. In particular, we are interested in subsets of the irrationals where such conversion can be performed with little overhead. We show that such conversion is possible, essentially with polynomial overhead, for the set of irrationals that are not Liouville numbers. Furthermore, it is known that there are irrational numbers x such that the expansion of x in one integer base is efficiently computable, but the expansion of x in certain other integer bases is not. We prove that any such number must be a Liouville number.
KW - Computability
KW - Computational complexity
KW - Diophantine approximation
KW - Number theory
UR - http://www.scopus.com/inward/record.url?scp=85088208927&partnerID=8YFLogxK
U2 - 10.1007/978-3-030-51466-2_5
DO - 10.1007/978-3-030-51466-2_5
M3 - Article in proceedings
AN - SCOPUS:85088208927
SN - 9783030514655
T3 - Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
SP - 50
EP - 62
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 -
