Characterizing polynomial and exponential complexity classes in elementary lambda-calculus
DOI10.1016/j.ic.2018.05.005zbMath1395.68135OpenAlexW2804330401WikidataQ115574493 ScholiaQ115574493MaRDI QIDQ1640981
Patrick Baillot, Erika De Benedetti, Simonetta Ronchi della Rocca
Publication date: 14 June 2018
Published in: Information and Computation (Search for Journal in Brave)
Full work available at URL: https://hal.inria.fr/hal-01015171v2/file/978-3-662-44602-7_13_Chapter.pdf
Complexity classes (hierarchies, relations among complexity classes, etc.) (68Q15) Proof-theoretic aspects of linear logic and other substructural logics (03F52) Combinatory logic and lambda calculus (03B40)
Related Items (1)
Cites Work
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Programming languages and systems. 9th Asian symposium, APLAS 2011, Kenting, Taiwan, December 5--7, 2011. Proceedings
- The parametric lambda calculus. A metamodel for computation.
- Light affine lambda calculus and polynomial time strong normalization
- Quantum implicit computational complexity
- Light linear logic
- Lambda calculus and intuitionistic linear logic
- Linear logic and elementary time
- Stratified coherence spaces: A denotational semantics for light linear logic
- Descendants and origins in term rewriting.
- The expressive power of higher-order types or, life without CONS
- Context semantics, linear logic, and computational complexity
- An Elementary Affine λ-Calculus with Multithreading and Side Effects
- Characterizing Polynomial and Exponential Complexity Classes in Elementary Lambda-Calculus
- Linear logic and polynomial time
- Light Logics and the Call-by-Value Lambda Calculus
- On light logics, uniform encodings and polynomial time
This page was built for publication: Characterizing polynomial and exponential complexity classes in elementary lambda-calculus
