Linear logic and polynomial time

DOI10.1017/S0960129506005688zbMATH Open1114.03051OpenAlexW2168736143MaRDI QIDQ3419785FDOQ3419785

Authors: 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

Recommendations

• Linear logic by levels and bounded time complexity
• Bounded linear logic: A modular approach to polynomial-time computability
• A polytime functional language from light linear logic
• Phase semantics for light linear logic
• Light linear logics with controlled weakening: expressibility, confluent strong normalization

zbMATH Keywords

Elementary Linear LogicLight Linear Logicpolytime computation

Mathematics Subject Classification ID

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

Cited In (31)

• Title not available (Why is that?)
• An abstract approach to stratification in linear logic
• FSTTCS 2005: Foundations of Software Technology and Theoretical Computer Science
• Light linear logics with controlled weakening: expressibility, confluent strong normalization
• Bounded linear logic, revisited
• The relational model is injective for multiplicative exponential linear logic (without weakenings)
• On the expressivity of elementary linear logic: characterizing Ptime and an exponential time hierarchy
• On light logics, uniform encodings and polynomial time
• Realizability models and implicit complexity
• Title not available (Why is that?)
• Title not available (Why is that?)
• Light types for polynomial time computation in lambda calculus
• Implicit computation complexity in higher-order programming languages
• Phase semantics for light linear logic
• Bounded linear logic: A modular approach to polynomial-time computability
• Linear logic and elementary time
• Characterizing polynomial and exponential complexity classes in elementary lambda-calculus
• A By-Level Analysis of Multiplicative Exponential Linear Logic
• A polytime functional language from light linear logic
• On the computational complexity of cut-elimination in linear logic.
• Title not available (Why is that?)
• Primal Infon Logic: Derivability in Polynomial Time
• From Proof-Nets to Linear Logic Type Systems for Polynomial Time Computing
• Polynomial time calculi.
• Linear logic by levels and bounded time complexity
• Light Linear Logic with Controlled Weakening
• Title not available (Why is that?)
• Polynomial algorithm of limited propositional deduction
• Bounded Linear Logic, Revisited
• Is there a logic for polynomial time?
• Title not available (Why is that?)

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

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q3419785)