Lars Kristiansen

Professor II - Programming

Norwegian version of this page

Email larsk@math.uio.no

Mobile phone +47 922 10 527

Username

Visiting address Niels Henrik Abels hus Moltke Moes vei 35 0851 OSLO

Postal address Postboks 1080 Blindern 0316 Oslo

Other affiliations Department of Mathematics

Press photo Download business card

NEW PREPRINT: On representations of real numbers and the computational complexity of converting between such representations.

I recommend this textbook on mathematical logic (see also AIM ). The book is available here.

Below you find a list over my current research interests together with some selected papers.

Weak First-Order Theories (selected papers):

Kristiansen, L. & Murwanashyaka, J.: First-Order Concatenation Theory with Bounded Quantifiers. Archive for Mathematical Logic (2020). doi: 10.1007/s00153-020-00735-6
Kristiansen, L. & Murwanashyaka, J.: On Interpretability Between some Weak Essentially Undecidable Theories. LNCS (2020). doi: 10.1007/978-3-030-51466-2_6

You can read more about first-order theories in Wikipedia.

Computable Analysis (selected papers):

Georgiev, I., Kristiansen, L. & Stephan, F.: Computable Irrational Numbers with Representations of Surprising Complexity. Annals of Pure and Applied Logic (2020). doi: 10.1016/j.apal.2020.102893 Preprint.
Kristiansen, L.: On Subrecursive Representability of Irrational Numbers, Part II. Computability (2018) . doi: 10.3233/COM-170081
Kristiansen, L.: On Subrecursive Representability of Irrational Numbers. Computability (2017). doi: 10.3233/COM-160063

You can read more about computable analysis in Wikipedia.

Subrecursive Degree Theory (selected papers):

Kristiansen, L., Schlage-Puchta, J. & Weiermann, A: Streamlined Subrecursive Degree Theory. Annals of Pure and Applied Logic (2012). doi: 10.1016/j.apal.2011.11.004
Kristiansen, L.: A Jump Operator on Honest Subrecursive Degrees. Archive for Mathematical Logic (1998). doi: 10.1007/s001530050086

You cannot read more about subrecursive degree theory in Wikipedia. But you can read about the Grzegorczyk hierarchy. Subrecursive degrees are in some sense a generalization of the Grzegorczyk hierarchy.

Implicit Computational Complexity and related stuff (selected papers):

Kristiansen, L.: Reversible Computing and Implicit Computational Complexity. link: https://doi.org/10.1016/j.scico.2021.102723 Science of Computer Programming (2021)
Kristiansen, L., Ben-Amram, A. & Jones, N. D.: Linear, Polynomial or Exponential? Complexity Inference in Polynomial Time. LNCS (2008). See here
Kristiansen, L.: Neat function Algebraic Characterizations of LOGSPACE and LINSPACE. Computational Complexity (2005). doi: 10.1007/s00037-005-0191-0
Kristiansen, L. & Niggl, K.-H.: On the Computational Complexity of Imperative Programming Languages. Theoretical Computer Science (2004). doi: 10.1016/j.tcs.2003.10.016

You can read more about implicit computational complexity in Wikipedia.

Tags: Mathematical Logic, Computability Theory, Complexity Theory, Computable Analysis

Kristiansen, Lars & Murwanashyaka, Juvenal (2024). Notes on Interpretability between Weak First-order Theories: Theories of Sequences. arXiv.org. ISSN 2331-8422. doi: 10.48550/arXiv.2402.14286. Show summary
We introduce a first-order theory Seq which is mutually in- terpretable with Robinson’s Q. The universe of a standard model for Seq consists of sequences. We prove that Seq directly interprets the adjuctive set theory AST, and we prove that Seq interprets the tree theory T and the set theory AST + EXT. This is a long version of a paper published in the proceedings from CiE 2024.
Ben-Amram, Amir & Kristiansen, Lars (2024). A Degree Structure on Representations of Irrational Numbers. Journal of Logic and Analysis. ISSN 1759-9008. Show summary
We study a degree structure on representations of irrational numbers (typical examples of representations are Cauchy sequences, Dedekind cuts and base- 10 expansions). We prove that the structure is a distributive lattice with a least and a greatest element. The maximum degree is the degree of the representation by continued fractions. The minimum degree is the degree of the representation by Weihrauch intersections.
Kristiansen, Lars & Murwanashyaka, Juvenal (2024). A Weak First-Order Theory of Sequences. Lecture Notes in Computer Science (LNCS). ISSN 0302-9743. Show summary
We introduce a first-order theory Seq which is mutually in- terpretable with Robinson’s Q. The universe of a standard model for Seq consists of sequences. We prove that Seq directly interprets the adjunc- tive set theory AST, and we prove that Seq interprets the tree theory T and the set theory AST+EXT.
Kristiansen, Lars; Ben-Amram, Amir & Simonsen, Jakob Grue (2023). On representations of real numbers and the computational complexity of converting between such representations. arXiv. doi: 10.48550/arXiv.2304.07227. Show summary
We study the computational complexity of converting one represen- tation of real numbers into another representation. Typical examples of representations are Cauchy sequences, base-10 expansions, Dedekind cuts and continued fractions.
Kristiansen, Lars (2021). Reversible Computing and Implicit Computational Complexity. Science of Computer Programming. ISSN 0167-6423. 213. doi: 10.1016/j.scico.2021.102723. Full text in Research Archive
Kristiansen, Lars (2021). On subrecursive representation of irrational numbers: Contractors and Baire sequences. Lecture Notes in Computer Science (LNCS). ISSN 0302-9743. 12813, p. 308–317. doi: 10.1007/978-3-030-80049-9_28. Full text in Research Archive Show summary
We study the computational complexity of three representations of irrational numbers: standard Baire sequences, dual Baire sequences and contractors. Our main results: Irrationals whose standard Baire sequences are of low computational complexity might have dual Baire sequences of arbitrarily high computational complexity, and vice versa, irrationals whose dual Baire sequences are of low complexity might have standard Baire sequences of arbitrarily high complexity. Further- more, for any subrecursive class S closed under primitive recursive oper- ations, the class of irrationals that have a contractor in S is exactly the class of irrationals that have both a standard and a dual Baire sequence in S. Our results implies that a subrecursive class closed under primitive recursive operations contains the continued fraction of an irrational number α if and only if there is a contractor for α in the class.
Georgiev, Ivan; Kristiansen, Lars & Stephan, Frank (2020). Computable Irrational Numbers with Representations of Surprising Complexity. Annals of Pure and Applied Logic. ISSN 0168-0072. 172(2). doi: 10.1016/j.apal.2020.102893. Full text in Research Archive
Kristiansen, Lars (2020). Reversible programming languages capturing complexity classes. Lecture Notes in Computer Science (LNCS). ISSN 0302-9743. 12227, p. 111–127. doi: 10.1007/978-3-030-52482-1_6. Full text in Research Archive
Kristiansen, Lars & Simonsen, Jakob Grue (2020). On the Complexity of Conversion Between Classic Real Number Representations. Lecture Notes in Computer Science (LNCS). ISSN 0302-9743. 12098, p. 75–86. doi: 10.1007/978-3-030-51466-2_7.
Kristiansen, Lars & Murwanashyaka, Juvenal (2020). On Interpretability between some weak essentially undecidable theories. Lecture Notes in Computer Science (LNCS). ISSN 0302-9743. 12098, p. 63–74. doi: 10.1007/978-3-030-51466-2_6. Full text in Research Archive
Kristiansen, Lars & Murwanashyaka, Juvenal (2020). First-Order Concatenation Theory with Bounded Quantifiers (Preprint). arXiv.org. ISSN 2331-8422. doi: 10.1007/s00153-020-00735-6.
Kristiansen, Lars & Murwanashyaka, Juvenal (2020). First-Order Concatenation Theory with Bounded Quantifiers. Archive for Mathematical Logic. ISSN 0933-5846. 60(1-2), p. 77–104. doi: 10.1007/s00153-020-00735-6. Full text in Research Archive

View all works in Cristin

Kristiansen, Lars (2023). On a Lattice of Degrees of Representations of Irrational Numbers.
Kristiansen, Lars (2022). On Various Week First-Order Theories.
Kristiansen, Lars (2021). On subrecursive representation of irrational numbers: Contractors and Baire sequences.
Kristiansen, Lars (2021). On Representations of Irrational Numbers: A Degree Structure.
Kristiansen, Lars (2021). Implicit characterisations of complexity classes by inherently reversible programming languages.
Kristiansen, Lars (2021). Classic representations of irrational numbers seen from a computability and complexity-theoretic perspective.
Kristiansen, Lars (2020). On Interpretability Between some Weak Essentially Undecidable Theories.
Kristiansen, Lars (2020). Reversible Programming Languages Capturing Complexity Classes.