Parsimonious Types and Non-uniform Computation

1. Abramsky, S., Jagadeesan, R., Malacaria, P.: Full abstraction for PCF. Inf. Comput. 163(2), 409–470 (2000)

   Article  MATH  MathSciNet  Google Scholar 

2. Baillot, P., Terui, K.: Light types for polynomial time computation in lambda calculus. Inf. Comput. 207(1), 41–62 (2009)

   Article  MATH  MathSciNet  Google Scholar 

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

   Article  MATH  MathSciNet  Google Scholar 

4. Ehrhard, T., Regnier, L.: Differential interaction nets. Electr. Notes Theor. Comput. Sci. 123, 35–74 (2005)

   Article  MathSciNet  Google Scholar 

5. Ehrhard, T., Regnier, L.: Uniformity and the taylor expansion of ordinary lambda-terms. Theor. Comput. Sci. 403(2–3), 347–372 (2008)

   Article  MATH  MathSciNet  Google Scholar 

6. Gaboardi, M., Péchoux, R.: Upper bounds on stream I/O using semantic interpretations. In: Grädel, E., Kahle, R. (eds.) CSL 2009. LNCS, vol. 5771, pp. 271–286. Springer, Heidelberg (2009)

   Chapter  Google Scholar 

7. Ghica, D.R.: Geometry of synthesis: a structured approach to VLSI design. In: Proceedings of POPL, pp. 363–375 (2007)

   Google Scholar 

8. Girard, J.Y.: Geometry of interaction I: Interpretation of system F. Proccedings of Logic Colloquium 1988, 221–260 (1989)

   MathSciNet  Google Scholar 

9. Girard, J.Y.: Light linear logic. Inf. Comput. 143(2), 175–204 (1998)

   Article  MATH  MathSciNet  Google Scholar 

10. Kfoury, A.J.: A linearization of the lambda-calculus and consequences. J. Log. Comput. 10(3), 411–436 (2000)

    Article  MATH  MathSciNet  Google Scholar 

11. Leivant, D., Marion, J.Y.: Lambda calculus characterizations of poly-time. Fundam. Inform. 19(1/2) (1993)

    Google Scholar 

12. Mazza, D.: An infinitary affine lambda-calculus isomorphic to the full lambda-calculus. In: Proceedings of LICS, pp. 471–480 (2012)

    Google Scholar 

13. Mazza, D.: Non-uniform polytime computation in the infinitary affine lambda-calculus. In: Esparza, J., Fraigniaud, P., Husfeldt, T., Koutsoupias, E. (eds.) ICALP 2014, Part II. LNCS, vol. 8573, pp. 305–317. Springer, Heidelberg (2014)

    Google Scholar 

14. Mazza, D.: Simple parsimonious types and logarithmic space (2015), available on the author’s web page

    Google Scholar 

15. Melliès, P.A.: Asynchronous games 2: The true concurrency of innocence. Theor. Comput. Sci. 358(2–3), 200–228 (2006)

    Article  MATH  Google Scholar 

16. Melliès, P.-A., Tabareau, N., Tasson, C.: An explicit formula for the free exponential modality of linear logic. In: Albers, S., Marchetti-Spaccamela, A., Matias, Y., Nikoletseas, S., Thomas, W. (eds.) ICALP 2009, Part II. LNCS, vol. 5556, pp. 247–260. Springer, Heidelberg (2009)

    Chapter  Google Scholar 

17. Ramyaa, R., Leivant, D.: Ramified corecurrence and logspace. Electr. Notes Theor. Comput. Sci. 276, 247–261 (2011)

    Article  MathSciNet  Google Scholar 

18. Saurin, A.: Typing streams in the \(\Lambda \mu \)-calculus. ACM Trans. Comput. Log. 11(4) (2010)

    Google Scholar 

19. Terui, K.: Proof nets and boolean circuits. In: Proceedings of LICS, pp. 182–191 (2004)

    Google Scholar 

20. Vollmer, H.: Introduction to circuit complexity - a uniform approach. Texts in theoretical computer science. Springer (1999)

    Google Scholar 

Download references