Paths-based criteria and application to linear logic subsystems characterizing polynomial time

DOI10.1016/j.ic.2018.05.004zbMath1394.68156arXiv1701.01413OpenAlexW2578183774MaRDI QIDQ1640980

Matthieu Perrinel

Publication date: 14 June 2018

Published in: Information and Computation (Search for Journal in Brave)

Full work available at URL: https://arxiv.org/abs/1701.01413

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
• Light types for polynomial time computation in lambda calculus
• Linear logic by levels and bounded time complexity
• Bounded linear logic: A modular approach to polynomial-time computability
• Light linear logic
• Linear logic and elementary time
• Soft linear logic and polynomial time
• Formal security proofs with minimal fuss: implicit computational complexity at work
• Context semantics, linear logic, and computational complexity
• An Elementary Affine λ-Calculus with Multithreading and Side Effects
• On Paths-Based Criteria for Polynomial Time Complexity in Proof-Nets
• A PolyTime Functional Language from Light Linear Logic
• The Computational SLR: A Logic for Reasoning about Computational Indistinguishability
• Some Complexity and Expressiveness Results on Multimodal and Stratified Proof Nets
• On context semantics and interaction nets
• Verification of Ptime Reducibility for system F Terms: Type Inference in Dual Light Affine Logic
• A Local Criterion for Polynomial-Time Stratified Computations
• Bounded Linear Logic, Revisited