Linear logic by levels and bounded time complexity

DOI10.1016/j.tcs.2009.09.015zbMath1187.68246OpenAlexW2091581695MaRDI QIDQ1044841

Damiano Mazza, Patrick Baillot

Publication date: 15 December 2009

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

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

zbMATH Keywords

implicit computational complexitylight linear logicstype systems for polynomial time

Mathematics Subject Classification ID

Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17)

Related Items (11)

Paths-based criteria and application to linear logic subsystems characterizing polynomial time ⋮ On Paths-Based Criteria for Polynomial Time Complexity in Proof-Nets ⋮ Complete and tractable machine-independent characterizations of second-order polytime ⋮ Proof theory for functional modal logic ⋮ Unnamed Item ⋮ Unnamed Item ⋮ Unary Resolution: Characterizing Ptime ⋮ Some Complexity and Expressiveness Results on Multimodal and Stratified Proof Nets ⋮ Proof-Theoretic Semantics and Feasibility ⋮ An abstract approach to stratification in linear logic ⋮ Implicit computation complexity in higher-order programming languages

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Linear logic
• Bounded linear logic: A modular approach to polynomial-time computability
• A new recursion-theoretic characterization of the polytime functions
• 2-sequent calculus: A proof theory of modalities
• Light linear logic
• A foundational delineation of poly-time
• Additives of linear logic and normalization. I: A (restricted) Church-Rosser property.
• Linear logic and elementary time
• Stratified coherence spaces: A denotational semantics for light linear logic
• Soft linear logic and polynomial time
• On an interpretation of safe recursion in light affine logic
• Light affine set theory: A naive set theory of polynomial time
• A logical account of pspace
• Linear logic and polynomial time
• A Soft Type Assignment System for λ-Calculus
• Predicative Analysis of Feasibility and Diagonalization
• PREDICATE AND SET-THEORETIC CALCULI BASED ON LOGIC WITHOUT CONTRACTIONS
• An analysis of (linear) exponentials based on extended sequents
• Optimizing optimal reduction
• Verification of Ptime Reducibility for system F Terms: Type Inference in Dual Light Affine Logic
• Intuitionistic Light Affine Logic
• Theoretical Computer Science

This page was built for publication: Linear logic by levels and bounded time complexity