Norwegian version of this page

Lars Kristiansen

Professor II - Several Complex Variables, Logic and Operator algebras

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 1053 Blindern 0316 Oslo

Other affiliations Data and Knowledge Management

Press photo Download business card

I recommend this textbook on mathematical logic (see also AIM ):

Leary, C. C. and Kristiansen, L.: A friendly introduction to mathematical logic.

The book is available here.

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

Computable Analysis (selected papers):

Amir Ben-Amram, Lars Kristiansen and Jakob Grue Simonsen: On representations of irrational numbers and the computational complexity of converting between such representations. Bulletin of Symbolic Logic , pp. 1 - 77. doi: 10.1017/bsl.2025.10085
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
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.

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.

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: Science of Computer Programming (2021). doi: 10.1016/j.scico.2021.102723
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

Ben-Amram, Amir & Kristiansen, Lars (2025). A Degree Structure on Representations of Irrational Numbers. Journal of Logic and Analysis. 17, p. 1–22. doi: 10.4115/jla.2025.17.FDS2. Full text in Research Archive 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.
Georgiev, Ivan & Kristiansen, Lars (2025). On S-Degrees of some Representations of Irrational Numbers. Lecture Notes in Computer Science (LNCS). ISSN 0302-9743. 15764, p. 222–236. doi: 10.1007/978-3-031-95908-0_16. Full text in Research Archive
Ben-Amram, Amir; Kristiansen, Lars & Simonsen, Jakob Grue (2025). On representations of irrational numbers and the computational complexity of converting between such representations. Bulletin of Symbolic Logic. ISSN 1079-8986. 31(4), p. 515–589. doi: 10.1017/bsl.2025.10085. Full text in Research Archive Show summary
We study the computational complexity of converting between different representations of irrational numbers. Typical examples of representations are Cauchy sequences, base-10 expansions, Dedekind cuts and continued fractions.
Kristiansen, Lars & Murwanashyaka, Juvenal (2024). A Weak First-Order Theory of Sequences. In Patey, Ludovic Levy; Pimentel, Elaine; Galeotti, Lorenzo & Manea, Florin (Ed.), Twenty Years of Theoretical and Practical Synergies. Springer Nature. ISSN 9783031643088. p. 390–404. doi: 10.1007/978-3-031-64309-5_31. Full text in Research Archive 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 Seg consists of sequences. We prove that Seq directly interprets the adjunctive set theory AST, and we prove that Seq interprets the tree theory T and the set theory AST+EXT.
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. Full text in Research Archive 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.
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. Full text in Research Archive 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 Show summary
We argue that there is a link between implicit computational complexity theory and reversible computation. We introduce inherently reversible programming languages which capture the complexity classes etime and Image 1. Furthermore, we discuss and analyze higher-order versions of our reversible programming languages.
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 & Murwanashyaka, Juvenal (2020). First-Order Concatenation Theory with Bounded Quantifiers (Preprint). arXiv.org. ISSN 2331-8422. doi: 10.1007/s00153-020-00735-6. Full text in Research Archive

View all works in NVA

Kristiansen, Lars (2025). On S-Degrees of some Representations of Irrational Numbers. Full text in Research Archive
Kristiansen, Lars (2025). Representing real numbers in irrational bases. Full text in Research Archive
Kristiansen, Lars (2024). . A Weak First-Order Theory of Sequences. Full text in Research Archive
Kristiansen, Lars (2024). Real numbers and their representations. Full text in Research Archive
Kristiansen, Lars (2023). On a Lattice of Degrees of Representations of Irrational Numbers. Full text in Research Archive
Kristiansen, Lars (2022). On Various Week First-Order Theories. Full text in Research Archive
Kristiansen, Lars (2021). Classic representations of irrational numbers seen from a computability and complexity-theoretic perspective. Full text in Research Archive
Kristiansen, Lars (2021). Implicit characterisations of complexity classes by inherently reversible programming languages. Full text in Research Archive
Kristiansen, Lars (2021). On Representations of Irrational Numbers: A Degree Structure. Full text in Research Archive
Kristiansen, Lars (2021). On subrecursive representation of irrational numbers: Contractors and Baire sequences. Full text in Research Archive