Some Programming Languages for Logspace and Ptime

1. Jones, N.D.: LOGSPACE and PTIME characterized by programming languages. Theoretical Computer Science 228, 151–174 (1999)

   Article  MATH  MathSciNet  Google Scholar 

2. Cook, S.: Characterizations of pushdown machines in terms of time-bounded computers. Journal of the ACM 18(1), 4–18 (1971)

   Article  MATH  Google Scholar 

3. Wadler, P.: Deforestation: Transforming programs to eliminate trees. In: Ganzinger, H. (ed.) ESOP 1988. LNCS, vol. 300, pp. 344–358. Springer, Heidelberg (1988)

   Google Scholar 

4. Marion, J.-Y., Moyen, J.-Y.: Efficient first order functional program interpreter with time bound certifications. In: Parigot, M., Voronkov, A. (eds.) LPAR 2000. LNCS (LNAI), vol. 1955, pp. 25–42. Springer, Heidelberg (2000)

   Chapter  Google Scholar 

5. Bonfante, G., Marion, J.Y., Moyen, J.Y.: On lexicographic termination ordering with space bound certifications. In: Bjørner, D., Broy, M., Zamulin, A.V. (eds.) PSI 2001. LNCS, vol. 2244, Springer, Heidelberg (2001)

   Chapter  Google Scholar 

6. Bonfante, G., Marion, J.Y., Moyen, J.Y.: Quasi-Interpretations and Small Space Bounds. In: Giesl, J. (ed.) RTA 2005. LNCS, vol. 3467, pp. 150–164. Springer, Heidelberg (2005)

   Chapter  Google Scholar 

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

   Article  MATH  MathSciNet  Google Scholar 

8. Leivant, D., Marion, J.Y.: Lambda calculus characterizations of poly-time. Fundamenta Informaticae 19, 167 (1993)

   MATH  MathSciNet  Google Scholar 

9. Leivant, D., Marion, J.Y.: Predicative functional recurrence and poly-space. In: Bidoit, M., Dauchet, M. (eds.) CAAP 1997, FASE 1997, and TAPSOFT 1997. LNCS, vol. 1214, pp. 369–380. Springer, Heidelberg (1997)

   Chapter  Google Scholar 

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

    Article  MathSciNet  Google Scholar 

11. Neergaard, P.: A functional language for logarithmic space. In: Chin, W.-N. (ed.) APLAS 2004. LNCS, vol. 3302, Springer, Heidelberg (2004)

    Chapter  Google Scholar 

12. Hofmann, M.: Linear types and non-size-increasing polynomial time computation. In: Proceedings of the Fourteenth IEEE Symposium on Logic in Computer Science (LICS 1999), pp. 464–473 (1999)

    Google Scholar 

13. Hofmann, M.: The strength of non size-increasing computation. In: Notices, A.S. (ed.) POPL 2002, vol. 37, pp. 260–269 (2002)

    Google Scholar 

14. Baillot, P., Terui, K.: Light types for polynomial time computation in lambda-calculus. IEEE Computer Society Press, Los Alamitos (2004)

    Google Scholar 

15. Oitavem, I.: Characterizing nc with tier 0 pointers. Archive for Mathematical Logic 41, 35–47 (2002)

    Article  MATH  MathSciNet  Google Scholar 

16. Oitavem, I.: A term rewriting characterization of the functions computable in polynomial space. Archive for Mathematical Logic 41(1), 35–47 (2002)

    Article  MATH  MathSciNet  Google Scholar 

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

    MATH  Google Scholar 

18. Grädel, E., Gurevich, Y.: Tailoring recursion for complexity. Journal of Symbolic Logic 60(3), 952–969 (1995)

    Article  MATH  MathSciNet  Google Scholar 

Download references