Phase semantics and decidability of elementary affine logic

DOI10.1016/J.TCS.2004.02.037MaRDI QIDQ596037zbMATH OpenOpenAlexFDO

Authors Ugo Dal Lago, Simone Martini

Publication date 10 August 2004

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

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

zbMATH Keywords

Light linear logicLinear logicOptimal reductionSoft linear logic

Mathematics Subject Classification ID

Decidability of theories and sets of sentences (03B25) Cut-elimination and normal-form theorems (03F05) Proof-theoretic aspects of linear logic and other substructural logics (03F52) Complexity classes (hierarchies, relations among complexity classes, etc.) (68Q15) Descriptive complexity and finite models (68Q19)

Recommendations

• Decidability of linear affine logic
• The finite model property for various fragments of linear logic
• A semantic proof of polytime soundness of light affine logic
• Phase semantics for light linear logic
• scientific article; zbMATH DE number 2182488

Cites work

• (Optimal) duplication is not elementary recursive
• A uniform semantic proof for cut-elimination and completeness of various first and higher order logics.
• Bounded linear logic: A modular approach to polynomial-time computability
• Decidability of linear affine logic
• Decision problems for propositional linear logic
• scientific article; zbMATH DE number 1722649 (Why is no real title available?)
• scientific article; zbMATH DE number 1231526 (Why is no real title available?)
• scientific article; zbMATH DE number 2061704 (Why is no real title available?)
• scientific article; zbMATH DE number 1392281 (Why is no real title available?)
• Intuitionistic light affine logic
• Light linear logic
• Linear logic
• Linear logic and elementary time
• Phase semantic cut-elimination and normalization proofs of first- and higher-order linear logic
• Phase semantics for light linear logic
• Soft linear logic and polynomial time
• The finite model property for various fragments of intuitionistic linear logic
• The finite model property for various fragments of linear logic
• The optimal implementation of functional programming languages

Cited in

(6)

• Decidability of linear affine logic
• On phase semantics and denotational semantics in multiplicative-additive linear logic
• Observational and behavioural equivalences for soft concurrent constraint programming
• Towards a theory of resource: an approach based on soft exponentials
• scientific article; zbMATH DE number 1078383 (Why is no real title available?)
• A semantic proof of polytime soundness of light affine logic

This page was built for publication: Phase semantics and decidability of elementary affine logic

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