Linear logic and elementary time

DOI10.1016/S0890-5401(03)00010-5MaRDI QIDQ1401946zbMATH OpenOpenAlexFDO

Authors Vincent Danos, Jean-Baptiste Joinet

Publication date 19 August 2003

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

Full work available at URL https://doi.org/10.1016/s0890-5401(03)00010-5

zbMATH Keywords

elementary linear logicelementary recursive functions

Mathematics Subject Classification ID

Cut-elimination and normal-form theorems (03F05) Proof-theoretic aspects of linear logic and other substructural logics (03F52)

Recommendations

• scientific article; zbMATH DE number 1231531
• On the expressivity of elementary linear logic: characterizing Ptime and an exponential time hierarchy
• Polynomial time in untyped elementary linear logic
• Linear logic by levels and bounded time complexity
• Linear logic and polynomial time

Cites work

• A new constructive logic: classic logic
• A new deconstructive logic: linear logic
• Additives of linear logic and normalization. I: A (restricted) Church-Rosser property.
• Elementary complexity and geometry of interaction
• scientific article; zbMATH DE number 3857078 (Why is no real title available?)
• scientific article; zbMATH DE number 1231574 (Why is no real title available?)
• scientific article; zbMATH DE number 1392281 (Why is no real title available?)
• Linear logic
• Stratified coherence spaces: A denotational semantics for light linear logic

Cited in

(33)

• Linear logic by levels and bounded time complexity
• The structure of multiplicatives
• Paths-based criteria and application to linear logic subsystems characterizing polynomial time
• Characterizing polynomial and exponential complexity classes in elementary lambda-calculus
• Stratified coherence spaces: A denotational semantics for light linear logic
• The additive multiboxes
• Combining linear logic and size types for implicit complexity
• Polynomial time in untyped elementary linear logic
• A type-assignment of linear erasure and duplication
• On the expressivity of elementary linear logic: characterizing Ptime and an exponential time hierarchy
• Logarithmic space and permutations
• Bounded combinatory logic and lower complexity
• Unary resolution: characterizing \textsc{Ptime}
• An elementary affine -calculus with multithreading and side effects
• On paths-based criteria for polynomial time complexity in proof-nets
• Linear Recursive Functions
• scientific article; zbMATH DE number 4033710 (Why is no real title available?)
• scientific article; zbMATH DE number 6917940 (Why is no real title available?)
• Combining linear logic and size types for implicit complexity
• scientific article; zbMATH DE number 7561616 (Why is no real title available?)
• Dual-context calculi for modal logic
• Proofs, reasoning and the metamorphosis of logic
• Free-cut elimination in linear logic and an application to a feasible arithmetic
• Characterizingco-NLby a group action
• Implicit computation complexity in higher-order programming languages
• Bounded Linear Logic, Revisited
• Phase semantics and decidability of elementary affine logic
• Exponentials as Substitutions and the Cost of Cut Elimination in Linear Logic
• Exponentials as substitutions and the cost of cut elimination in linear logic
• Super exponentials in linear logic
• Infinitary cut-elimination via finite approximations
• Type inference for light affine logic via constraints on words
• Light affine lambda calculus and polynomial time strong normalization

This page was built for publication: Linear logic and elementary time

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