Linear logic and polynomial time

DOI10.1017/S0960129506005688MaRDI QIDQ3419785zbMATHOpenAlexFDO

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

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)

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

Cited in

(39)

• A polytime functional language from light linear logic
• scientific article; zbMATH DE number 2182488 (Why is no real title available?)
• Light types for polynomial time computation in lambda calculus
• Phase semantics for light linear logic
• Polynomial time calculi.
• Primal Infon Logic: Derivability in Polynomial Time
• On the computational complexity of cut-elimination in linear logic.
• Realizability models and implicit complexity
• scientific article; zbMATH DE number 2061714 (Why is no real title available?)
• Linear logic by levels and bounded time complexity
• Bounded linear logic, revisited
• Implicit computation complexity in higher-order programming languages
• scientific article; zbMATH DE number 1670494 (Why is no real title available?)
• Polynomial time in untyped elementary linear logic
• FSTTCS 2005: Foundations of Software Technology and Theoretical Computer Science
• Soft linear logic and polynomial complexity classes
• The relational model is injective for multiplicative exponential linear logic (without weakenings)
• Bounded linear logic: A modular approach to polynomial-time computability
• Light linear logics with controlled weakening: expressibility, confluent strong normalization
• On the expressivity of elementary linear logic: characterizing Ptime and an exponential time hierarchy
• scientific article; zbMATH DE number 3903964 (Why is no real title available?)
• On paths-based criteria for polynomial time complexity in proof-nets
• Rewriting with linear inferences in propositional logic
• Light Linear Logic with Controlled Weakening
• Bounded Linear Logic, Revisited
• Light logics and higher-order processes
• Context semantics, linear logic, and computational complexity
• scientific article; zbMATH DE number 176206 (Why is no real title available?)
• Linear logic and elementary time
• scientific article; zbMATH DE number 515724 (Why is no real title available?)
• On light logics, uniform encodings and polynomial time
• A By-Level Analysis of Multiplicative Exponential Linear Logic
• From Proof-Nets to Linear Logic Type Systems for Polynomial Time Computing
• Polynomial algorithm of limited propositional deduction
• An abstract approach to stratification in linear logic
• Characterizing polynomial and exponential complexity classes in elementary lambda-calculus
• Paths-based criteria and application to linear logic subsystems characterizing polynomial time
• Is there a logic for polynomial time?
• Graded multicategories of polynomial-time realizers

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)