CIS 720 - A List of Papers

A List of Papers

The following is the initial list of papers I intend to cover in the course.
This list will be revised as the course progresses.
The green text indicates that the paper has been used in class.


  1. S. Bellantoni and S. Cook, A new recursion-theoretic characterization of the polytime functions, Computational Complexity 2 (1992) 97-110.

  2. S. Cook and B. Kapron, Characterizations of the basic feasible functions of finite type, in Feasible Mathematics: A Mathematical Sciences Institute Workshop, (S. Buss and P. Scott, eds.), Birkhauser, 1990, pp. 71-95.

  3. S. Cook, Computability and complexity of higher type functions, in Logic from Computer Science (Y.N. Moschovakis, ed.), Springer-Verlag, 1991, pp. 51-72.

  4. R. Gandy and J. Hyland, Computable and recursively countable functions of higher type, in Logic Colloquium 76, North-Holland, 1977, pp. 407-438.

  5. B. Kapron and S. Cook, A new characterization of type 2 feasibility, SIAM Journal on Computing 25 (1996) 117-132.

  6. D. Leivant, Ramified Recurrence and Computational Complexity I: Word Recurrence and Poly-time, in Feasible Mathematics II, (P. Clote and J. Remmel, eds.) Birkhauser, 1995, pp. 320-343.

  7. H. Mairson, A Simple Proof of a Theorem of Statman, Theoretical Computer Science 103 (1992) 387-394.

  8. J. Royer, Semantics vs. syntax vs. computations: Machine models for type-2 polynomial-time bounded functionals, J. Comput. and Syst. Science, to appear.

  9. H. Schwichtenberg, Functions definable in the simply-typed lambda calculus, Arch. Math Logik 17 (1976) pp. 113-114. See RJ Irwin's translation of this.

  10. H. Schwichtenberg, Density and choice for total continuous functionals, in Kreiseliana (P. Odifreddi, ed.), A.K. Peters, 1996, pp. 335-362.

  11. H. Schwichtenberg, Type Theory, lecture notes from a course given at Universität München, 1994.

  12. D. Scott, A type-theoretical alternative to ISWIM, CUCH, and OWHY, Theoretical Computer Science 121 (1993) 411-440, Originally written in 1969.

  13. A. Seth, Complexity Theory of Higher Type Functionals, Ph.D. Thesis, University of Bombay, 1994.


Supplementary Books

  1. C. Gunther, Semantics of Programming Languages, MIT Press, 1992.
  2. P. Odifreddi, Classical Recursion Theory, North Holland, 1989.
  3. C. Papadimitriou, Computational Complexity, Addison-Wesley, 1994.
  4. H. Rogers, Theory of Recursive Functions and Effective Computability, McGraw-Hill, 1969.

Back to the course homepage