Polynomial time in untyped elementary linear logic

DOI10.1016/J.TCS.2019.10.002zbMath1481.03067OpenAlexW2979384293WikidataQ127091685 ScholiaQ127091685MaRDI QIDQ1989326

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

proof netsstrong normalizationimplicit computational complexityelementary linear logicpolynomial-time computation

Mathematics Subject Classification ID

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

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• A semantic measure of the execution time in linear logic
• Linear logic
• The structure of multiplicatives
• Light linear logic
• Linear logic and elementary time
• Stratified coherence spaces: A denotational semantics for light linear logic
• Soft linear logic and polynomial time
• On the expressivity of elementary linear logic: characterizing Ptime and an exponential time hierarchy
• Context semantics, linear logic, and computational complexity
• An Implicit Characterization of PSPACE
• On light logics, uniform encodings and polynomial time
• Intuitionistic Light Affine Logic
• Theoretical Computer Science

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