Linear logic and polynomial time

DOI10.1017/S0960129506005688zbMath1114.03051OpenAlexW2168736143MaRDI QIDQ3419785

Damiano Mazza

Publication date: 7 February 2007

Published in: Mathematical Structures in Computer Science (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1017/s0960129506005688

zbMATH Keywords

Elementary Linear LogicLight Linear Logicpolytime computation

Mathematics Subject Classification ID

Complexity of computation (including implicit computational complexity) (03D15) Proof-theoretic aspects of linear logic and other substructural logics (03F52)

Related Items (10)

Characterizing polynomial and exponential complexity classes in elementary lambda-calculus ⋮ A By-Level Analysis of Multiplicative Exponential Linear Logic ⋮ Light linear logics with controlled weakening: expressibility, confluent strong normalization ⋮ The relational model is injective for multiplicative exponential linear logic (without weakenings) ⋮ Light Linear Logic with Controlled Weakening ⋮ Light types for polynomial time computation in lambda calculus ⋮ Linear logic by levels and bounded time complexity ⋮ On the expressivity of elementary linear logic: characterizing Ptime and an exponential time hierarchy ⋮ An abstract approach to stratification in linear logic ⋮ Implicit computation complexity in higher-order programming languages

This page was built for publication: Linear logic and polynomial time