Lars Kristiansen

• Ben-Amram, Amir & Kristiansen, Lars (2025). A Degree Structure on Representations of Irrational Numbers. Journal of Logic and Analysis. 17, s. 1–22. doi: 10.4115/jla.2025.17.FDS2. Fulltekst i vitenarkiv Vis sammendrag

  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, s. 222–236. doi: 10.1007/978-3-031-95908-0_16. Fulltekst i vitenarkiv
• 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), s. 515–589. doi: 10.1017/bsl.2025.10085. Fulltekst i vitenarkiv Vis sammendrag

  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. I Patey, Ludovic Levy; Pimentel, Elaine; Galeotti, Lorenzo & Manea, Florin (Red.), Twenty Years of Theoretical and Practical Synergies. Springer Nature. ISSN 9783031643088. s. 390–404. doi: 10.1007/978-3-031-64309-5_31. Fulltekst i vitenarkiv Vis sammendrag

  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. Fulltekst i vitenarkiv Vis sammendrag

  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. Fulltekst i vitenarkiv Vis sammendrag

  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. Fulltekst i vitenarkiv Vis sammendrag

  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, s. 308–317. doi: 10.1007/978-3-030-80049-9_28. Fulltekst i vitenarkiv Vis sammendrag

  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. Fulltekst i vitenarkiv
• 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. Fulltekst i vitenarkiv
• 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. Fulltekst i vitenarkiv Vis sammendrag

  We introduce two essentially undecidable first-order theories WT and T. The intended model for the theories is a term model. We prove that WT is mutually interpretable with Robinson’s R. Moreover, we prove that Robinson’s Q is interpretable in T.

• 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. Fulltekst i vitenarkiv
• 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. Fulltekst i vitenarkiv Vis sammendrag

  We argue that there is a link between implicit computational complexity theory and the theory of reversible computation. We show that the complexity classes ETIME and P can be captured by inherently reversible programming languages.

• 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. Fulltekst i vitenarkiv Vis sammendrag

  We study first-order concatenation theory with bounded quantifiers. We give axiomatizations with interesting properties, and we prove some normal-form results. Finally, we prove a number of decidability and undecidability results.

• 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. Fulltekst i vitenarkiv
• Kristiansen, Lars & Murwanashyaka, Juvenal (2018). Notes on Fragments of First-Order Concatenation Theory. arXiv.org. ISSN 2331-8422. doi: 10.1007/978-3-319-94418-0_25. Fulltekst i vitenarkiv
• Georgiev, Ivan; Kristiansen, Lars & Stephan, Frank (2018). Subrecursive Approximations of Irrational Numbers by Variable Base Sums. arXiv.org. ISSN 2331-8422. Fulltekst i vitenarkiv
• Georgiev, Ivan; Kristiansen, Lars & Stephan, Frank (2018). On General Sum Approximations of Irrational Numbers. I Manea, Florin; Miller, Russel G. & Nowotka, Dirk (Red.), Sailing Routes in the World of Computation. Springer Nature. ISSN 9783319944173. s. 194–203. doi: 10.1007/978-3-319-94418-0_20. Fulltekst i vitenarkiv
• Kristiansen, Lars & Murwanashyaka, Juvenal (2018). Decidable and Undecidable Fragments of First-Order Concatenation Theory. I Manea, Florin; Miller, Russel G. & Nowotka, Dirk (Red.), Sailing Routes in the World of Computation. Springer Nature. ISSN 9783319944173. s. 244–253. doi: 10.1007/978-3-319-94418-0_25. Fulltekst i vitenarkiv Vis sammendrag

  We identify a number of decidable and undecidable fragments of first-order concatenation theory. We also give a purely universal axiomatization which is complete for the fragments we identify. Furthermore, we prove some normal-form results. This is a post-peer-review, pre-copyedit version of an article. The final authenticated version is available online at: https://link.springer.com/

• Kristiansen, Lars (2018). On subrecursive representability of irrational numbers, part II. Computability. ISSN 2211-3568. 8(1), s. 43–65. doi: 10.3233/COM-170081. Fulltekst i vitenarkiv Vis sammendrag

  The final publication is available at IOS Press through http://dx.doi.org/10.3233/COM-170081

• Kristiansen, Lars (2017). On subrecursive representability of irrational numbers. Computability. ISSN 2211-3568. 6(3), s. 249–276. doi: 10.3233/COM-160063. Fulltekst i vitenarkiv
• Kristiansen, Lars (2016). On subrecursive representability of irrational numbers. Computability. ISSN 2211-3568. 6, s. 249–276. doi: 10.3233/COM-160063. Fulltekst i vitenarkiv Vis sammendrag

  The final publication is available at IOS Press.

• Kristiansen, Lars & Mender, Bedeho (2012). Non-determinism in Gödel's System T. Theory of Computing Systems. ISSN 1432-4350. 51(1), s. 85–105. doi: 10.1007/s00224-011-9377-9. Fulltekst i vitenarkiv
• Kristiansen, Lars; Lubarsky, Robert; Schlage-Puchta, J.-C. & Weiermann, Andreas (2012). On the structure of honest elementary degrees. I Friedman, Sy-David; Koerwien, Martin & Muller, Moritz (Red.), The Infinity Project.A 2009–2011 Research Programme. Centre de Recerca Matematica. ISSN 9788461633074. s. 255–279. Fulltekst i vitenarkiv
• Kristiansen, Lars (2012). Degrees of Total Algorithms versus Degrees of Honest Functions. Lecture Notes in Computer Science (LNCS). ISSN 0302-9743. 7318, s. 442–431. doi: 10.1007/978-3-642-30870-3_43. Fulltekst i vitenarkiv
• Ben-Amram, Amir & Kristiansen, Lars (2012). On the edge of decidability in complexity analysis of loop programs. International Journal of Foundations of Computer Science. ISSN 0129-0541. 23(7), s. 1451–1464. doi: 10.1142/S0129054112400588. Fulltekst i vitenarkiv
• Kristiansen, Lars; Schlage-Puchta, Jan-Christoph & Weiermann, Andreas (2012). Streamlined subrecursive degree theory. Annals of Pure and Applied Logic. ISSN 0168-0072. 163(6), s. 698–716. doi: 10.1016/j.apal.2011.11.004. Fulltekst i vitenarkiv
• Kristiansen, Lars (2012). Higher Types, Finite Domains and Resource-bounded Turing Machines. Journal of Logic and Computation. ISSN 0955-792X. 22(2), s. 281–304. doi: 10.1093/logcom/exq009. Fulltekst i vitenarkiv
• Kristiansen, Lars & Mender, Bedeho (2011). Non-determinism in Gödel's system T. Theory of Computing Systems. ISSN 1432-4350. doi: 10.1007/s00224-011-9377-9. Fulltekst i vitenarkiv
• Kristiansen, Lars (2010). Higher types, finite domains and resource bounded Turing machines. Journal of Logic and Computation. ISSN 0955-792X. doi: 10.1093/logcom/exq009. Fulltekst i vitenarkiv
• Avery, James; Kristiansen, Lars & Moyen, Jean-Yves (2010). Static Complexity Analysis of Higher Order Programs. Lecture Notes in Computer Science (LNCS). ISSN 0302-9743. 6324, s. 84–99. Fulltekst i vitenarkiv
• Jones, Neil D. & Kristiansen, Lars (2009). A Flow Calculus of mwp-Bounds for Complexity Analysis. ACM Transactions on Computational Logic. ISSN 1529-3785. 10(4). doi: 10.1145/1555746.1555752. Fulltekst i vitenarkiv
• Kristiansen, Lars (2008). Complexity-Theoretic Hierarchies Induced by Fragments of Godel's T. Theory of Computing Systems. ISSN 1432-4350. 43(3-4), s. 516–541. doi: 10.1007/s00224-007-9021-x. Fulltekst i vitenarkiv
• Kristiansen, Lars & Jones, Neil D. (2008). A flow calculus of mwp-bounds for complexity analysis. ACM Transactions on Computational Logic. ISSN 1529-3785. Fulltekst i vitenarkiv
• Kristiansen, Lars; Ben-Amram, Amir & Jones, Neil D. (2008). Linear, Polynomial or Exponential? Complexity Inference in Polynomial Time. I Beckmann, Arnold*; Dimitracopoulos, Costas & Löwe, Benedikt (Red.), Logic and Theory of Algorithms. Springer. ISSN 9783540694052. s. 67–76. Fulltekst i vitenarkiv
• Kristiansen, Lars (2008). Recursion in Higher Types and Resource Bounded Turing Machines. I Beckmann, Arnold*; Dimitracopoulos, Costas & Löwe, Benedikt (Red.), Logic and Theory of Algorithms. Springer. ISSN 9783540694052. s. 336–348. Fulltekst i vitenarkiv
• Kristiansen, Lars & Voda, Paul (2008). The Structure of Detour Degrees. I Agrawal, Manindra; Du, Dingzhu; Duan, Zhenhua & Li, Angsheng (Red.), Theory and Applications of Models of Computation. Springer Science+Business Media B.V.. ISSN 9783540792277. s. 148–159. Fulltekst i vitenarkiv
• Burgess, Mark & Kristiansen, Lars (2008). On the complexity of determining autonomic policy constrained behaviour. I Brunner, Markus; Westphall, Carlos B. & Granville, Lisandro Z. (Red.), Network Operations and Management Symposium, 2008. NOMS 2008. IEEE. IEEE (Institute of Electrical and Electronics Engineers). ISSN 9781424420667. s. 295–301. Fulltekst i vitenarkiv
• Kristiansen, Lars (2007). Complexity-theoretic hierarchies induced by fragments of Gödel's T. Theory of Computing Systems. ISSN 1432-4350. doi: 10.1007/s00224-007-9021-x. Fulltekst i vitenarkiv
• Kristiansen, Lars (2007). Complexity Analysis of Programs: Methods and Challenges. I Gluck, Robert & Hagiya, M (Red.), Proceedings of the 3rd DIKU-IST Joint Workshop on Foundations of Software. Dept. of Computer Science, University of Copenhagen. s. 126–136. Fulltekst i vitenarkiv
• Barra, G. Mathias; Kristiansen, Lars & Voda, Paul J. (2007). Nondeterminism without Turing Machines. I Cooper, S Barry; Kenth, Thomas F; Love, Benedikt & Sorbi, Andrea (Red.), Computation and Logic in the Real World. CiE 2007. s. 71–78. Fulltekst i vitenarkiv
• Kristiansen, Lars & Burgess, Mark (2007). Complexity of Change and Configuration Management. I Bergstra, Jan & Burgess, Mark (Red.), Handbook of Network and System Administration. Elsevier. ISSN 9780444521989. Fulltekst i vitenarkiv
• Kristiansen, Lars (2006). Complexity-theoretic hierarchies. Lecture Notes in Computer Science (LNCS). ISSN 0302-9743. 3988, s. 279–288. Fulltekst i vitenarkiv
• Kristiansen, Lars (2006). Complexity-Thoretic Hierarchies. Lecture Notes in Computer Science (LNCS). ISSN 0302-9743. 3988, s. 279–288. Fulltekst i vitenarkiv
• Kristiansen, Lars & Voda, Paul J. (2006). The Trade-off theorem and fragments of and Gödel's T. Lecture Notes in Computer Science (LNCS). ISSN 0302-9743. 3959. Fulltekst i vitenarkiv

Se alle arbeider i NVA

• Leary, Christopher C. & Kristiansen, Lars (2015). A Friendly Introduction to Mathematical Logic. Milne Library, SUNY Geneseo. ISBN 9781942341079. 380 s. Fulltekst i vitenarkiv

Se alle arbeider i NVA

• Kristiansen, Lars (2025). On S-Degrees of some Representations of Irrational Numbers. Fulltekst i vitenarkiv
• Kristiansen, Lars (2025). Representing real numbers in irrational bases. Fulltekst i vitenarkiv
• Kristiansen, Lars (2024). . A Weak First-Order Theory of Sequences. Fulltekst i vitenarkiv
• Kristiansen, Lars (2024). Real numbers and their representations. Fulltekst i vitenarkiv
• Kristiansen, Lars (2023). On a Lattice of Degrees of Representations of Irrational Numbers. Fulltekst i vitenarkiv
• Kristiansen, Lars (2022). On Various Week First-Order Theories. Fulltekst i vitenarkiv
• Kristiansen, Lars (2021). Classic representations of irrational numbers seen from a computability and complexity-theoretic perspective. Fulltekst i vitenarkiv
• Kristiansen, Lars (2021). Implicit characterisations of complexity classes by inherently reversible programming languages. Fulltekst i vitenarkiv
• Kristiansen, Lars (2021). On Representations of Irrational Numbers: A Degree Structure. Fulltekst i vitenarkiv
• Kristiansen, Lars (2021). On subrecursive representation of irrational numbers: Contractors and Baire sequences. Fulltekst i vitenarkiv
• Kristiansen, Lars (2020). On Interpretability Between some Weak Essentially Undecidable Theories. Fulltekst i vitenarkiv
• Kristiansen, Lars (2020). Reversible Programming Languages Capturing Complexity Classes. Fulltekst i vitenarkiv
• Kristiansen, Lars (2019). Best Approximations, Contractions Maps and Continued Fractions. Fulltekst i vitenarkiv
• Kristiansen, Lars (2019). On Subrecursive Representability of Irrational Numbers: Continued Fractions and Contraction maps. Fulltekst i vitenarkiv
• Kristiansen, Lars (2018). Decidable and Undecidable Fragments of First-Order Concatenation Theory. Fulltekst i vitenarkiv
• Kristiansen, Lars (2018). On General Sum Approximations of Irrational Numbers. Fulltekst i vitenarkiv
• Kristiansen, Lars (2018). First-order concatenation vs. first-order number theory. Fulltekst i vitenarkiv
• Kristiansen, Lars (2018). On b-adic Representations of Irrational Numbers. Fulltekst i vitenarkiv
• Kristiansen, Lars (2017). On Resource Analysis of Imperative Programs. Electronic Proceedings in Theoretical Computer Science (EPTCS). 248. doi: 10.4204/EPTCS.248. Fulltekst i vitenarkiv
• Kristiansen, Lars (2017). On Resource Analysis of Imperative Programs. Fulltekst i vitenarkiv
• Kristiansen, Lars (2016). On Subrecursive Representability of Irrational Numbers. Fulltekst i vitenarkiv
• Kristiansen, Lars (2016). On Subrecursive Representability of Irrational Numbers. Fulltekst i vitenarkiv
• Kristiansen, Lars (2016). Subrecursive Sum Approximations of Irrational Numbers. Fulltekst i vitenarkiv
• Kristiansen, Lars (2015). Subrecursive Dedekind and Cauchy reals. Fulltekst i vitenarkiv
• Kristiansen, Lars; Aanderaa, Stål & Ruud, Hans-Kristian (2014). A Preliminary Report on Search for Good Examples of Hall's Conjecture. arXiv.org. ISSN 2331-8422. Fulltekst i vitenarkiv
• Kristiansen, Lars (2012). Degrees of Total Algorithms versus Degrees of Honest Functions. Fulltekst i vitenarkiv
• Kristiansen, Lars (2011). Review of the book "New Computational Paradigms (eds.: Cooper, Löwe, Sorbi)". Studia Logica: An International Journal for Symbolic Logic. ISSN 0039-3215. 97, s. 313–316. Fulltekst i vitenarkiv
• Kristiansen, Lars (2011). Subrecursive degrees of honest functions and provably recursive functions. Fulltekst i vitenarkiv
• Kristiansen, Lars (2011). Honest subrecursive degree theory and provability in Peano Arithmetic. Fulltekst i vitenarkiv
• Ben-Amram, Amir & Kristiansen, Lars (2011). Decidable and undecidable problems related to complexity analysis of loop programs. Fulltekst i vitenarkiv
• Kristiansen, Lars (2011). New computational paradigms. Studia Logica: An International Journal for Symbolic Logic. ISSN 0039-3215. 97(2), s. 313–316. doi: 10.1007/s11225-011-9308-4. Fulltekst i vitenarkiv
• Kristiansen, Lars (2010). Honest degree theory and statements independent of Peano Arithmetic. Fulltekst i vitenarkiv
• Kristiansen, Lars; Weiermann, Andreas & Schlage-Puchta, Jan-Christoph (2010). Subrecursive degrees and statements independent of Peano Arithmetic. Fulltekst i vitenarkiv
• Kristiansen, Lars & Mender, Bedeho (2010). Two notions of non-determinism in Gödel's system T. Fulltekst i vitenarkiv
• Kristiansen, Lars & Ben-Amram, Amir (2009). The limits of decidability and tractability in growth-rate analysis for programs. Fulltekst i vitenarkiv
• Kristiansen, Lars (2009). Complexity Analysis of Imperative Programs. Fulltekst i vitenarkiv
• Kristiansen, Lars & Mender, Bedeho (2009). The Semantics and Complexity of Successor-Free Nondeterministic Gödel's T and PCF. Fulltekst i vitenarkiv
• Kristiansen, Lars (2009). Implicit Computational Complexity: Moving on from the Extensional to the Intentional. Fulltekst i vitenarkiv
• Kristiansen, Lars & Mender, Bedeho (2009). The Semantics and Complexity of Successor-free Nondeterministic Gôdel’s T and PCF. Fulltekst i vitenarkiv
• Kristiansen, Lars (2008). The Structure of Detour Degrees. Fulltekst i vitenarkiv
• Burgess, Mark & Kristiansen, Lars (2008). On the Complexity of Determining Autonomic Policy Constrained behaviour. Fulltekst i vitenarkiv
• Kristiansen, Lars (2008). Recursion in Higher Types and Resource Bounded Turing machines. Fulltekst i vitenarkiv
• Kristiansen, Lars (2008). Implicit Characterisations of Complexity Classes and Recursion in Higher Types. Fulltekst i vitenarkiv
• Kristiansen, Lars (2007). Review of S.B. Cooper's book "Computability Theory". Studia Logica: An International Journal for Symbolic Logic. ISSN 0039-3215. 86, s. 145–146. Fulltekst i vitenarkiv
• Kristiansen, Lars (2007). Complexity Analysis of Programs: Methods and Challenges. Fulltekst i vitenarkiv
• Kristiansen, Lars (2007). Neil Jones: The early years. Fulltekst i vitenarkiv
• Kristiansen, Lars (2007). Complexity theory and Gödel's T. Fulltekst i vitenarkiv
• Kristiansen, Lars (2007). Beregnbarhet, kompleksitet og typeteori. Fulltekst i vitenarkiv
• Kristiansen, Lars & Voda, Paul J. (2006). The Trade-off theorem and fragments of and Gödel's T. Fulltekst i vitenarkiv
• Kristiansen, Lars (2006). $T^-$-hierarchies and the Trade-off Theorem. Fulltekst i vitenarkiv
• Kristiansen, Lars (2006). Complexity-Theoretic Hierarchies. Fulltekst i vitenarkiv
• Kristiansen, Lars & Jones, Neil D. (2006). Static Complexity Ananlysis of Programs. Fulltekst i vitenarkiv
• Kristiansen, Lars (2006). Fragments of Godel's T, Complexity Classes and Rewriting Systems. Fulltekst i vitenarkiv
• Kristiansen, Lars (2006). Complexity-Theoretic Hierarchies. Fulltekst i vitenarkiv

Se alle arbeider i NVA