Soft linear logic and polynomial complexity classes

DOI10.1016/J.ENTCS.2008.03.066MaRDI QIDQ2866738zbMATH OpenOpenAlexFDO

Authors Marco Gaboardi, Jean-Yves Marion, Simona Ronchi Della Rocca

Publication date 13 December 2013

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

Full work available at URL https://doi.org/10.1016/j.entcs.2008.03.066

zbMATH Keywords

implicit computational complexitylinear logicpolynomial spacetype assignment

Mathematics Subject Classification ID

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

Recommendations

• A Soft Type Assignment System for λ-Calculus
• Foundations of Software Science and Computation Structures
• Linear logic by levels and bounded time complexity
• On the expressivity of elementary linear logic: characterizing Ptime and an exponential time hierarchy
• Linear logic and polynomial time

Cites work

• scientific article; zbMATH DE number 2061714 (Why is no real title available?)
• scientific article; zbMATH DE number 2079048 (Why is no real title available?)
• A Soft Type Assignment System for λ-Calculus
• A call-by-name lambda-calculus machine
• A logical account of pspace
• Alternation
• Linear logic
• Relationships between nondeterministic and deterministic tape complexities
• Soft linear logic and polynomial time

Cited in

(20)

• Foundations of Software Science and Computation Structures
• An implicit characterization of PSPACE
• Combining linear logic and size types for implicit complexity
• scientific article; zbMATH DE number 2061714 (Why is no real title available?)
• Bounded combinatory logic and lower complexity
• The role of polymorphism in the characterisation of complexity by soft types
• From light logics to type assignments: a case study
• The role of polymorphism in the characterisation of complexity by soft types
• On the expressivity of elementary linear logic: characterizing Ptime and an exponential time hierarchy
• Parallelism in soft linear logic
• FUNCTIONAL PEARL Linear lambda calculus and PTIME-completeness
• scientific article; zbMATH DE number 785051 (Why is no real title available?)
• Paths-based criteria and application to linear logic subsystems characterizing polynomial time
• Multiplexor Categories and Models of Soft Linear Logic
• A type system for PSPACE derived from light linear logic
• Simple parsimonious types and logarithmic space
• Linear logic by levels and bounded time complexity
• Linear additives
• A Soft Type Assignment System for λ-Calculus
• Soft linear set theory

This page was built for publication: Soft linear logic and polynomial complexity classes

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