Lars Kristiansen

Professor - Programming

Adjunct Professor - Department of Mathematics

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

Press photo Download business card

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 (2021). On subrecursive representation of irrational numbers: Contractors and Baire sequences. Lecture Notes in Computer Science (LNCS). ISSN 0302-9743. 12813. doi: 10.1007/978-3-030-80049-9_28. Full text in Research Archive
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 & 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 & 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 (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 & 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
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. 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 (2021). On Representations of Irrational Numbers: A Degree Structure.
Kristiansen, Lars (2021). On subrecursive representation of irrational numbers: Contractors and Baire sequences.
Kristiansen, Lars (2021). Classic representations of irrational numbers seen from a computability and complexity-theoretic perspective.
Kristiansen, Lars (2021). Implicit characterisations of complexity classes by inherently reversible programming languages.
Kristiansen, Lars (2020). On Interpretability Between some Weak Essentially Undecidable Theories.
Kristiansen, Lars (2020). Reversible Programming Languages Capturing Complexity Classes.
Kristiansen, Lars (2019). On Subrecursive Representability of Irrational Numbers: Continued Fractions and Contraction maps.
Kristiansen, Lars (2019). Best Approximations, Contractions Maps and Continued Fractions.
Kristiansen, Lars (2018). Decidable and Undecidable Fragments of First-Order Concatenation Theory. .
Kristiansen, Lars (2018). On b-adic Representations of Irrational Numbers. .
Kristiansen, Lars (2018). First-order concatenation vs. first-order number theory. .
Kristiansen, Lars (2018). On General Sum Approximations of Irrational Numbers. .