Lars Kristiansen

Professor - Programming

Adjunct Professor - Department of Mathematics

Norwegian version of this page

Email larsk@math.uio.no

Mobile phone +4792210527 +47 922 10 527

Username

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

Postal address Postboks 1053 Blindern 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 Programming Languages Capturing Complexity Classes. LNCS (2020) doi: 10.1007/978-3-030-52482-1_6
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 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, s 111- 127 . doi: 10.1007/978-3-030-52482-1_6 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), s 77- 104 . doi: 10.1007/s00153-020-00735-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). On Interpretability between some weak essentially undecidable theories. Lecture Notes in Computer Science (LNCS). ISSN 0302-9743. 12098, s 63- 74 . doi: 10.1007/978-3-030-51466-2_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, s 75- 86 . doi: 10.1007/978-3-030-51466-2_7
Aanderaa, Stål; Kristiansen, Lars & Ruud, Hans-Kristian (2018). Search for Good Examples of Hall's Conjecture. Mathematics of Computation. ISSN 0025-5718. 87(314), s 2903- 2914 . doi: 10.1090/mcom/3298 Full text in Research Archive.
Georgiev, Ivan; Kristiansen, Lars & Stephan, Frank (2018). On General Sum Approximations of Irrational Numbers, In Florin Manea; Russel G. Miller & Dirk Nowotka (ed.), Sailing Routes in the World of Computation. Springer Nature. ISBN 978-3-319-94417-3. kapittel. s 194 - 203
Georgiev, Ivan; Kristiansen, Lars & Stephan, Frank (2018). Subrecursive Approximations of Irrational Numbers by Variable Base Sums. arXiv.org. ISSN 2331-8422.
Kristiansen, Lars (2018). On subrecursive representability of irrational numbers, part II. Computability - The Journal of the Assosiation. ISSN 2211-3568. 8(1), s 43- 65 . doi: 10.3233/COM-170081 Full text in Research Archive.

View all works in Cristin

Kristiansen, Lars (2021). Classic representations of irrational numbers seen from a computability and complexity-theoretic perspective.
Kristiansen, Lars (2020). Reversible Programming Languages Capturing Complexity Classes.
Kristiansen, Lars (2020). On Interpretability Between some Weak Essentially Undecidable Theories.
Kristiansen, Lars (2019). Best Approximations, Contractions Maps and Continued Fractions.
Kristiansen, Lars (2019). On Subrecursive Representability of Irrational Numbers: Continued Fractions and Contraction maps..
Kristiansen, Lars (2018). Decidable and Undecidable Fragments of First-Order Concatenation Theory..
Kristiansen, Lars (2018). First-order concatenation vs. first-order number theory..
Kristiansen, Lars (2018). On General Sum Approximations of Irrational Numbers..
Kristiansen, Lars (2018). On b-adic Representations of Irrational Numbers..

View all works in Cristin

Published Oct. 16, 2013 12:09 PM - Last modified Oct. 10, 2020 4:39 PM

Lars Kristiansen

Weak First-Order Theories (selected papers):

Computable Analysis (selected papers):

Subrecursive Degree Theory (selected papers):

Implicit Computational Complexity and related stuff (selected papers):

Publications

Research groups

Visiting address

Mail address

Phone, fax, e-mail