Lars Kristiansen

Professor - Programming
Professor II - Department of Mathematics
Image of Lars Kristiansen
Norwegian version of this page
Email larsk@math.uio.no
Phone +47 22855897
Mobile phone +4792210527 +47 922 10 527
Room B705
Username
Visiting address 0851 OSLO Niels Henrik Abels hus Moltke Moes vei 35
Postal address Postboks 1080 0316 OSLO
Tags: Complexity Theory, Computability Theory, Mathematical Logic

Publications

  • Kristiansen, Lars & Murwanashyaka, Juvenal (2020). First-Order Concatenation Theory with Bounded Quantifiers. Archive for Mathematical Logic.  ISSN 0933-5846.
  • 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.
  • Kristiansen, Lars & Murwanashyaka, Juvenal (2018). Decidable and Undecidable Fragments of First-Order Concatenation Theory, 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 244 - 253
  • Kristiansen, Lars & Murwanashyaka, Juvenal (2018). Notes on Fragments of First-Order Concatenation Theory. arXiv.org.  ISSN 2331-8422.
  • Kristiansen, Lars (2017). On subrecursive representability of irrational numbers. Computability - The Journal of the Assosiation.  ISSN 2211-3568.  6(3), s 249- 276 . doi: 10.3233/COM-160063
  • Kristiansen, Lars (2016). On subrecursive representability of irrational numbers.. Computability - The Journal of the Assosiation.  ISSN 2211-3568.  6, s 249- 276 . doi: 10.3233/COM-160063 Full text in Research Archive.
  • 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
  • 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
  • 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
  • Kristiansen, Lars; Lubarsky, Robert; Schlage-Puchta, J.-C. & Weiermann, Andreas (2012). On the structure of honest elementary degrees, In Sy-David Friedman; Martin Koerwien & Moritz Muller (ed.),  The Infinity Project.A 2009–2011 Research Programme.  Centre de Recerca Matematica.  ISBN 978-84-616-3307-4.  On the structure of honest elementary degrees..  s 255 - 279
  • 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
  • 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
  • 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
  • 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
  • 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
  • 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
  • Burgess, Mark & Kristiansen, Lars (2008). On the complexity of determining autonomic policy constrained behaviour, In Markus Brunner; Carlos B. Westphall & Lisandro Z. Granville (ed.),  Network Operations and Management Symposium, 2008. NOMS 2008. IEEE.  IEEE conference proceedings.  ISBN 978-1-4244-2066-7.  On the complexity of determining autonomic policy constrained behaviour.  s 295 - 301
  • 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
  • Kristiansen, Lars (2008). Recursion in Higher Types and Resource Bounded Turing Machines, In Arnold* Beckmann; Costas Dimitracopoulos & Benedikt Löwe (ed.),  Logic and Theory of Algorithms.  Springer.  ISBN 978-3-540-69405-2.  Recursion in Higher Types and Resource Bounded Turing Machines..  s 336 - 348
  • Kristiansen, Lars; Ben-Amram, Amir & Jones, Neil D. (2008). Linear, Polynomial or Exponential? Complexity Inference in Polynomial Time, In Arnold* Beckmann; Costas Dimitracopoulos & Benedikt Löwe (ed.),  Logic and Theory of Algorithms.  Springer.  ISBN 978-3-540-69405-2.  Linear, Polynomial or Exponential? Complexity Inference in Polynomial Time.  s 67 - 76
  • Kristiansen, Lars & Jones, Neil D. (2008). A flow calculus of mwp-bounds for complexity analysis. ACM Transactions on Computational Logic.  ISSN 1529-3785.
  • Kristiansen, Lars & Voda, Paul (2008). The Structure of Detour Degrees, In Manindra Agrawal; Dingzhu Du; Zhenhua Duan & Angsheng Li (ed.),  Theory and Applications of Models of Computation.  Springer Science+Business Media B.V..  ISBN 978-3-540-79227-7.  The Structure of Detour Degrees.  s 148 - 159
  • Barra, G. Mathias; Kristiansen, Lars & Voda, Paul J. (2007). Nondeterminism without Turing Machines, In S Barry Cooper; Thomas F Kenth; Benedikt Love & Andrea Sorbi (ed.),  Computation and Logic in the Real World.  CiE 2007.  artikkel.  s 71 - 78
  • Kristiansen, Lars (2007). Complexity Analysis of Programs: Methods and Challenges, In Robert Gluck & M Hagiya (ed.),  Proceedings of the 3rd DIKU-IST Joint Workshop on Foundations of Software.  Dept. of Computer Science, University of Copenhagen.  artikkel.  s 126 - 136
  • 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
  • Kristiansen, Lars & Burgess, Mark (2007). Complexity of Change and Configuration Management, In Jan Bergstra & Mark Burgess (ed.),  Handbook of Network and System Administration.  Elsevier.  ISBN 978-0-444-52198-9.  6. 2..
  • Kristiansen, Lars (2006). Complexity-Thoretic Hierarchies. Lecture Notes in Computer Science (LNCS).  ISSN 0302-9743.  3988, s 279- 288
  • Kristiansen, Lars (2006). Complexity-theoretic hierarchies. Lecture Notes in Computer Science (LNCS).  ISSN 0302-9743.  3988, s 279- 288
  • Kristiansen, Lars & Jones, Neil D. (2006). Static Complexity Analysis of Programs, In Arne Løkketangen (ed.),  Norsk informatikkonferanse NIK 2006.  Tapir Akademisk Forlag.  ISBN 82-519-2186-4.  Static Complexity Analysis of Programs..  s 65 - 76
  • 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
  • Kristiansen, Lars & Barra, G. Mathias (2005). The small Grzegorczyk classes and the typed lambda-calculus, In S. Barry Cooper; Benedikt Lowe & Leen Torenvliet (ed.),  New computational paradigms.  Springer.  ISBN 3-540-26179-6.  pp. 252-262.  s 252 - 262
  • Kristiansen, Lars & Jones, Neil D. (2005). The flow of data and the complexity of algorithms, In S. Barry Cooper; Benedikt Lowe & Leen Torenvliet (ed.),  New computational paradigms.  Springer.  ISBN 3-540-26179-6.  pp. 263-274.  s 263 - 274
  • Kristiansen, Lars & Voda, Paul J. (2005). Programming languages capturing complexity classes. Nordic Journal of Computing.  ISSN 1236-6064.  12, s 89- 115
  • Kristiansen, Lars (2005). Neat function algebraic characterizations of LOGSPACE and LINSPACE. Computational Complexity.  ISSN 1016-3328.  14, s 72- 88
  • Kristiansen, Lars (2005). Programming languages capturing complexity classes. Nordic Journal of Computing.  ISSN 1236-6064.  (Vol. 12, no. 2), s 89- 115
  • Kristiansen, Lars & Barra, Georg Mathias Honore (2005). The small Grzegorczyk classes and the typed lambda-calculus. Lecture Notes in Computer Science (LNCS).  ISSN 0302-9743.  3526
  • Kristiansen, Lars & Jones, ND (2005). The flow of data and the complexity of algorithms. Lecture Notes in Computer Science (LNCS).  ISSN 0302-9743.  3526
  • Kristiansen, Lars (2004). On the computational complexity of imperative programming languages. Theoretical Computer Science.  ISSN 0304-3975.  318, s 139- 161 . doi: 10.1016/j.tcs2003.10.016
  • Kristiansen, Lars & Niggl, KH (2004). On the computational complexity of imperative programming languages. Theoretical Computer Science.  ISSN 0304-3975.  318, s 139- 161
  • Kristiansen, Lars (2003). Complexity classes and fragments of C. Information Processing Letters.  ISSN 0020-0190.  88, s 213- 218 . doi: 10.1016/j.ipl2003.08.010
  • Kristiansen, Lars (2001). Subrecursive Degrees and Fragments of Peano Arithmetic. Archive for Mathematical Logic.  ISSN 0933-5846.  40(5), s 365- 397
  • Kristiansen, Lars (1998). A jump operator on honest subrecursive degrees. Archive for Mathematical Logic.  ISSN 0933-5846.  37, s 105- 125

View all works in Cristin

  • Leary, Christopher C. & Kristiansen, Lars (2015). A Friendly Introduction to Mathematical Logic. Milne Library, SUNY Geneseo.  ISBN 978-1-942341-07-9.  380 s.

View all works in Cristin

  • 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..
  • Kristiansen, Lars (2017). On Resource Analysis of Imperative Programs. Electronic Proceedings in Theoretical Computer Science.  ISSN 2075-2180.  248 . doi: 10.4204/EPTCS.248
  • Kristiansen, Lars (2017). On Resource Analysis of Imperative Programs.
  • Kristiansen, Lars (2016). On Subrecursive Representability of Irrational Numbers.
  • Kristiansen, Lars (2016). On Subrecursive Representability of Irrational Numbers..
  • Kristiansen, Lars (2016). Subrecursive Sum Approximations of Irrational Numbers.
  • Kristiansen, Lars (2015). Subrecursive Dedekind and Cauchy reals..
  • 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.
  • Kristiansen, Lars (2012). Degrees of Total Algorithms versus Degrees of Honest Functions.
  • Ben-Amram, Amir & Kristiansen, Lars (2011). Decidable and undecidable problems related to complexity analysis of loop programs.
  • Kristiansen, Lars (2011). Honest subrecursive degree theory and provability in Peano Arithmetic.
  • 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
  • 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
  • Kristiansen, Lars (2011). Subrecursive degrees of honest functions and provably recursive functions.
  • Kristiansen, Lars (2010). Honest degree theory and statements independent of Peano Arithmetic.
  • Kristiansen, Lars & Mender, Bedeho (2010). Two notions of non-determinism in Gödel's system T.
  • Kristiansen, Lars; Weiermann, Andreas & Schlage-Puchta, Jan-Christoph (2010). Subrecursive degrees and statements independent of Peano Arithmetic.
  • Kristiansen, Lars (2009). Complexity Analysis of Imperative Programs.
  • Kristiansen, Lars (2009). Implicit Computational Complexity: Moving on from the Extensional to the Intentional.
  • Kristiansen, Lars & Ben-Amram, Amir (2009). The limits of decidability and tractability in growth-rate analysis for programs.
  • Kristiansen, Lars & Mender, Bedeho (2009). The Semantics and Complexity of Successor-Free Nondeterministic Gödel's T and PCF.
  • Kristiansen, Lars & Mender, Bedeho (2009). The Semantics and Complexity of Successor-free Nondeterministic Gôdel’s T and PCF.
  • Burgess, Mark & Kristiansen, Lars (2008). On the Complexity of Determining Autonomic Policy Constrained behaviour.
  • Kristiansen, Lars (2008). Implicit Characterisations of Complexity Classes and Recursion in Higher Types.
  • Kristiansen, Lars (2008). Recursion in Higher Types and Resource Bounded Turing machines.
  • Kristiansen, Lars (2008). The Structure of Detour Degrees.
  • Kristiansen, Lars (2007). Beregnbarhet, kompleksitet og typeteori.
  • Kristiansen, Lars (2007). Complexity Analysis of Programs: Methods and Challenges.
  • Kristiansen, Lars (2007). Complexity theory and Gödel's T.
  • Kristiansen, Lars (2007). Neil Jones: The early years.
  • 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
  • Kristiansen, Lars (2006). Complexity-Theoretic Hierarchies.
  • Kristiansen, Lars (2006). Complexity-Theoretic Hierarchies.
  • Kristiansen, Lars (2006). Fragments of Godel's T, Complexity Classes and Rewriting Systems.
  • Kristiansen, Lars (2006). $T^-$-hierarchies and the Trade-off Theorem.
  • Kristiansen, Lars & Jones, Neil D. (2006). Static Complexity Ananlysis of Programs.
  • Kristiansen, Lars & Voda, Paul J. (2006). The Trade-off theorem and fragments of and Gödel's T.
  • Kristiansen, Lars (2005). Computational Complexity and Natural Programming Languages.
  • Kristiansen, Lars (2005). Det tellbare og det overtellbare. Normat.  ISSN 0801-3500.  53(3), s 118- 129
  • Kristiansen, Lars (2005). Lambda-kalkyle og kompleksitetsteoretiske hierarkier.
  • Kristiansen, Lars (2005). Programmeringsspråk og kompleksitetsklasser.
  • Kristiansen, Lars & Aanderaa, Stål (2005). Løsninger av ligningen x^3 - y^2 = k.
  • Kristiansen, Lars & Jones, Neil D. (2005). Feasible programs and natural programming languages.
  • Kristiansen, Lars & Jones, Neil D. (2005). The Flow of Data and the Complexity of Algorithms.
  • Kristiansen, Lars & Voda, Paul J. (2005). Kleene-Kreisel Functionals and Computational Complexity.
  • Kristiansen, Lars (2004). Characterization of Complexity Classes and Complexity Analysis of Programs.
  • Kristiansen, Lars (2004). Complexity Classes and Higher Types.
  • Kristiansen, Lars (2004). Programming Languages Capturing Complexity Classes.
  • Kristiansen, Lars (2004). Small complexity classes and fragments of Gödel's system T.
  • Kristiansen, Lars (2004). The flow of data and the complexity of algorithms - an introduction.
  • Kristiansen, Lars (2004). The flow of data and the complexity of algorithms - some technical proofs.
  • Kristiansen, Lars (2004). The small Grzegorczyk classes and the typed lambda-calculus.
  • Kristiansen, Lars (2003). Computing without the Successor Function.
  • Kristiansen, Lars (2003). The Garland Measure and Computational Complexity of Stack Programs.
  • Kristiansen, Lars (2003). The surprising power of restricted programs and Gödel's functionals.
  • Kristiansen, Lars (1999). Et kritisk blikk på Curch-Turings tese.
  • Kristiansen, Lars (1999). Low<SUB>n</SUB>, high <SUB>n</SUB>, and intermediate subrecursive degrees.

View all works in Cristin

Published Oct. 16, 2013 12:09 PM - Last modified Dec. 9, 2016 10:31 AM

Research groups

Personal Hompage:

http://folk.uio.no/larsk/