Soft linear logic and polynomial time
From MaRDI portal
Publication:1827397
DOI10.1016/j.tcs.2003.10.018zbMath1079.03057OpenAlexW2057183321MaRDI QIDQ1827397
Publication date: 6 August 2004
Published in: Theoretical Computer Science (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1016/j.tcs.2003.10.018
Complexity of computation (including implicit computational complexity) (03D15) Complexity classes (hierarchies, relations among complexity classes, etc.) (68Q15) Proof-theoretic aspects of linear logic and other substructural logics (03F52) Combinatory logic and lambda calculus (03B40)
Related Items (51)
The role of polymorphism in the characterisation of complexity by soft types ⋮ A type assignment for \(\lambda\)-calculus complete both for FPTIME and strong normalization ⋮ Bounded combinatory logic and lower complexity ⋮ Linear Logic Properly Displayed ⋮ Linear and affine logics with temporal, spatial and epistemic operators ⋮ A Short Introduction to Implicit Computational Complexity ⋮ Paths-based criteria and application to linear logic subsystems characterizing polynomial time ⋮ A By-Level Analysis of Multiplicative Exponential Linear Logic ⋮ On Paths-Based Criteria for Polynomial Time Complexity in Proof-Nets ⋮ Phase semantics and decidability of elementary affine logic ⋮ Jump from parallel to sequential proofs: exponentials ⋮ Computational Complexity Via Finite Types ⋮ A Characterization of NC k by First Order Functional Programs ⋮ Light linear logics with controlled weakening: expressibility, confluent strong normalization ⋮ Read/write factorizable programs ⋮ A type-assignment of linear erasure and duplication ⋮ Parsing/theorem-proving for logical grammar \textit{CatLog3} ⋮ Natural language semantics and computability ⋮ Exponentials as Substitutions and the Cost of Cut Elimination in Linear Logic ⋮ DisCoCat for Donkey Sentences ⋮ Light logics and higher-order processes ⋮ On session types and polynomial time ⋮ Infinitary action logic with multiplexing ⋮ On quantum lambda calculi: a foundational perspective ⋮ Linear Exponentials as Resource Operators: A Decidable First-order Linear Logic with Bounded Exponentials ⋮ Normal modal substructural logics with strong negation ⋮ Linear logical relations and observational equivalences for session-based concurrency ⋮ Soft linear set theory ⋮ Polynomial time in untyped elementary linear logic ⋮ Gödel's system \(\mathcal T\) revisited ⋮ Realizability models and implicit complexity ⋮ Characterizingco-NLby a group action ⋮ Type inference for light affine logic via constraints on words ⋮ A semantic proof of polytime soundness of light affine logic ⋮ Taming Modal Impredicativity: Superlazy Reduction ⋮ Light Linear Logic with Controlled Weakening ⋮ Light types for polynomial time computation in lambda calculus ⋮ The decidability of the intensional fragment of classical linear logic ⋮ Least and Greatest Fixed Points in Linear Logic ⋮ Unary Resolution: Characterizing Ptime ⋮ Bounded Linear Logic, Revisited ⋮ Type Inference for a Polynomial Lambda Calculus ⋮ Towards a theory of resource: an approach based on soft exponentials ⋮ Quantum implicit computational complexity ⋮ Linear logic by levels and bounded time complexity ⋮ Soft subexponentials and multiplexing ⋮ On the expressivity of elementary linear logic: characterizing Ptime and an exponential time hierarchy ⋮ An abstract approach to stratification in linear logic ⋮ Soft Linear Logic and Polynomial Complexity Classes ⋮ Causal computational complexity of distributed processes ⋮ Implicit computation complexity in higher-order programming languages
Cites Work
This page was built for publication: Soft linear logic and polynomial time
