Soft linear logic and polynomial time
DOI10.1016/J.TCS.2003.10.018zbMATH Open1079.03057OpenAlexW2057183321MaRDI QIDQ1827397FDOQ1827397
Authors: Yves Lafont 
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 classes (hierarchies, relations among complexity classes, etc.) (68Q15) Combinatory logic and lambda calculus (03B40) Proof-theoretic aspects of linear logic and other substructural logics (03F52) Complexity of computation (including implicit computational complexity) (03D15)
Cites Work
Cited In (55)
- Exponentials as Substitutions and the Cost of Cut Elimination in Linear Logic
- DisCoCat for Donkey Sentences
- Exponentials as substitutions and the cost of cut elimination in linear logic
- Exponentially handsome proof nets and their normalization
- Super exponentials in linear logic
- Polynomial time in untyped elementary linear logic
- An abstract approach to stratification in linear logic
- Parsing/theorem-proving for logical grammar \textit{CatLog3}
- Least and Greatest Fixed Points in Linear Logic
- Light linear logics with controlled weakening: expressibility, confluent strong normalization
- Causal computational complexity of distributed processes
- Jump from parallel to sequential proofs: exponentials
- A type assignment for \(\lambda\)-calculus complete both for FPTIME and strong normalization
- Bounded combinatory logic and lower complexity
- The role of polymorphism in the characterisation of complexity by soft types
- A semantic proof of polytime soundness of light affine logic
- On the expressivity of elementary linear logic: characterizing Ptime and an exponential time hierarchy
- Type inference for light affine logic via constraints on words
- Realizability models and implicit complexity
- Unary Resolution: Characterizing Ptime
- Computational Complexity Via Finite Types
- Light types for polynomial time computation in lambda calculus
- Implicit computation complexity in higher-order programming languages
- Normal modal substructural logics with strong negation
- Light logics and higher-order processes
- On session types and polynomial time
- A Characterization of NC k by First Order Functional Programs
- Paths-based criteria and application to linear logic subsystems characterizing polynomial time
- Phase semantics and decidability of elementary affine logic
- A By-Level Analysis of Multiplicative Exponential Linear Logic
- Soft subexponentials and multiplexing
- Gödel's system \(\mathcal T\) revisited
- A Short Introduction to Implicit Computational Complexity
- Linear and affine logics with temporal, spatial and epistemic operators
- Towards a theory of resource: an approach based on soft exponentials
- A Splitting Algorithm Based on Soft Constraints for the Computation of Truth Degree in Quantitative Logic
- The decidability of the intensional fragment of classical linear logic
- Natural language semantics and computability
- Linear logical relations and observational equivalences for session-based concurrency
- Taming Modal Impredicativity: Superlazy Reduction
- On quantum lambda calculi: a foundational perspective
- Linear Logic Properly Displayed
- Characterizingco-NLby a group action
- Linear logic by levels and bounded time complexity
- Quantum implicit computational complexity
- Soft linear logic and polynomial complexity classes
- Linear Exponentials as Resource Operators: A Decidable First-order Linear Logic with Bounded Exponentials
- On Paths-Based Criteria for Polynomial Time Complexity in Proof-Nets
- Light Linear Logic with Controlled Weakening
- A type-assignment of linear erasure and duplication
- Type Inference for a Polynomial Lambda Calculus
- Read/write factorizable programs
- Infinitary action logic with multiplexing
- Soft linear set theory
- Bounded Linear Logic, Revisited
This page was built for publication: Soft linear logic and polynomial time
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1827397)
