Characterizing polynomial and exponential complexity classes in elementary lambda-calculus
type: Item
instance of: scholarly article
title: Characterizing polynomial and exponential complexity classes in elementary lambda-calculus
zbMATH Open document ID: 1395.68135
author: Patrick Baillot
author: Erika De Benedetti
author: Simona Ronchi Della Rocca
published in: Information and Computation
publication date: 2018-06-14T00:00:00Z
full work available at URL: 978-3-662-44602-7 13 Chapter.pdf
Mathematics Subject Classification ID: 68Q15
Mathematics Subject Classification ID: 03B40
Mathematics Subject Classification ID: 03F52
zbMATH DE Number: 6889846
zbMATH Keywords: implicit computational complexity
zbMATH Keywords: linear logic
zbMATH Keywords: lambda-calculus
Wikidata QID: Q115574493
MaRDI profile type: Publication
OpenAlex ID: W2804330401
cites work: Q4265595
cites work: The expressive power of higher-order types or, life without CONS
cites work: Q4850553
cites work: Q3142166
cites work: Light linear logic
cites work: Programming languages and systems. 9th Asian symposium, APLAS 2011, Kenting, Taiwan, December 5--7, 2011. Proceedings
cites work: Linear logic and elementary time
cites work: Linear logic and polynomial time
cites work: Context semantics, linear logic, and computational complexity
cites work: Light affine lambda calculus and polynomial time strong normalization
cites work: An Elementary Affine λ-Calculus with Multithreading and Side Effects
cites work: Light Logics and the Call-by-Value Lambda Calculus
cites work: Lambda calculus and intuitionistic linear logic
cites work: Quantum implicit computational complexity
cites work: Characterizing Polynomial and Exponential Complexity Classes in Elementary Lambda-Calculus
cites work: Descendants and origins in term rewriting.
cites work: The parametric lambda calculus. A metamodel for computation.
cites work: Stratified coherence spaces: A denotational semantics for light linear logic
cites work: On light logics, uniform encodings and polynomial time
cites work: Q3392273
DOI: 10.1016/J.IC.2018.05.005
description: scientific article; zbMATH DE number 6889846