Predicative Analysis of Feasibility and Diagonalization

• Ackermann, W.: Zum Hilbertschen Aufbau der reellen Zahlen. Math. annalen 99, 118–133 (1928)

  Article  Google Scholar 

• Bellantoni, S., Cook, S.: A new recursion-theoretic characterization of the poly-time functions. Computational Complexity 2, 97–110 (1992)

  Article  MATH  Google Scholar 

• Bellantoni, S., Niggl, K.-H.: Ranking primitive recursions: The low Grzegorczyk classes revisited. SIAM Journal on Computing 29(2), 401–415 (1999)

  Article  Google Scholar 

• Caporaso, S., Covino, E., Pani, G.: A predicative approach to the classification problem. J. Funct. Program. 11(1), 95–116 (2001)

  Article  MATH  Google Scholar 

• Cobham, A.: The intrinsic computational difficulty of functions. In: Bar-Hillel, Y. (ed.) Proceedings of the International Conference on Logic, Methodology, and Philosophy of Science, pp. 24–30. North-Holland, Amsterdam (1962)

  Google Scholar 

• Gödel, K.: Über eine bisher noch nicht benützte Erweiterung des finiten Standpunktes. Dialectica 12, 280–287 (1958) Republished with English translation and explanatory notes by A. S. Troelstra in Kurt Gödel: Collected Works, Vol. II. S. Feferman, ed. Oxford University Press, Oxford (1990)

  Google Scholar 

• Jones, N.: Computability and complexity, from a programming perspective. MIT Press, Cambridge (1997)

  MATH  Google Scholar 

• Dal Lago, U., Baillot, P.: Light affine logic, uniform encoding and polynomial time. Mathematical Structures in Computer Science 16(4), 713–733 (2006)

  Article  MATH  Google Scholar 

• Leivant, D.: A foundational delineation of computational feasiblity. In: LICS’91. Proceedings of the Sixth IEEE Symposium on Logic in Computer Science, IEEE Computer Society Press, Los Alamitos (1991)

  Google Scholar 

• Leivant, D.: Predicative recurrence and computational complexity I: Word recurrence and poly-time. In: Clote, P., Remmel, J. (eds.) Feasible Mathematics II, Birkhäuser, pp. 320–343 (1994)

  Google Scholar 

• Leivant, D.: Ramified recurrence and computational complexity III: Higher type recurrence and elementary complexity. Annals of Pure and Applied Logic 96(1-3), 209–229 (1999)

  Article  MATH  Google Scholar 

• Leivant, D., Marion, J.-Y.: Lambda calculus characterizations of poly-time. Fundamenta Informaticae 19(1,2), 167–184 (1993)

  MATH  Google Scholar 

• Leivant, D., Marion, J.-Y.: A characterization of alternating log time by ramified recurrence. Theoretical Computer Science 236(1-2), 192–208 (2000)

  Article  Google Scholar 

• Neergaard, P.M., Mairson, H.: Lal is square: Representation and expressivness in light affine and logic. In: Implicit Computational complexity (2002)

  Google Scholar 

• Simmon, H.: Tiering as a recursion technique. Bulletin of Symbolic Logic 11(3), 321–350 (2005)

  Article  Google Scholar 

• Simmons, H.: The realm of primitive recursion. Archive for Mathematical Logic 27, 177–188 (1988)

  Article  MATH  Google Scholar 

• Simmons, H.: Derivation and Computation. Tracts in theoretical computer science, Cambridge, vol. 51 (2000)

  Google Scholar 

• Sorensen, M., Urzyczyn, P.: Lectures on the Curry-Howard isomorphism. DIKU-rapport 98/14 (1998)

  Google Scholar 

Download references