Polynomial time in untyped elementary linear logic

DOI10.1016/J.TCS.2019.10.002MaRDI QIDQ1989326zbMATH OpenOpenAlexWikidataFDO

Authors Olivier Laurent

Publication date 21 April 2020

Published in Theoretical Computer Science (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1016/j.tcs.2019.10.002

zbMATH Keywords

elementary linear logicimplicit computational complexitypolynomial-time computationproof netsstrong normalization

Mathematics Subject Classification ID

Proof-theoretic aspects of linear logic and other substructural logics (03F52) Complexity classes (hierarchies, relations among complexity classes, etc.) (68Q15)

Recommendations

• Linear logic and polynomial time
• Linear logic by levels and bounded time complexity
• Bounded linear logic: A modular approach to polynomial-time computability
• Light affine lambda calculus and polynomial time strong normalization
• On the expressivity of elementary linear logic: characterizing Ptime and an exponential time hierarchy

Cites work

• A semantic measure of the execution time in linear logic
• An implicit characterization of PSPACE
• Context semantics, linear logic, and computational complexity
• scientific article; zbMATH DE number 42059 (Why is no real title available?)
• scientific article; zbMATH DE number 1889386 (Why is no real title available?)
• scientific article; zbMATH DE number 1392281 (Why is no real title available?)
• Intuitionistic light affine logic
• Light linear logic
• Linear logic
• Linear logic and elementary time
• On light logics, uniform encodings and polynomial time
• On the categorical semantics of elementary linear logic
• On the computational complexity of cut-elimination in linear logic.
• On the expressivity of elementary linear logic: characterizing Ptime and an exponential time hierarchy
• Soft linear logic and polynomial time
• Stratified coherence spaces: A denotational semantics for light linear logic
• The structure of multiplicatives

Cited in

(9)

• Linear logic and elementary time
• Unary resolution: characterizing \textsc{Ptime}
• Primal Infon Logic: Derivability in Polynomial Time
• From Proof-Nets to Linear Logic Type Systems for Polynomial Time Computing
• scientific article; zbMATH DE number 176206 (Why is no real title available?)
• Is there a logic for polynomial time?
• scientific article; zbMATH DE number 2182488 (Why is no real title available?)
• Exponentially handsome proof nets and their normalization
• Implicit automata in typed -calculi I: aperiodicity in a non-commutative logic

This page was built for publication: Polynomial time in untyped elementary linear logic

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