Phase semantics and decidability of elementary affine logic

DOI10.1016/j.tcs.2004.02.037zbMath1047.03048OpenAlexW2070294436MaRDI QIDQ596037

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

Linear logicLight linear logicOptimal reductionSoft linear logic

Mathematics Subject Classification ID

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

Related Items (3)

Observational and behavioural equivalences for soft concurrent constraint programming ⋮ A semantic proof of polytime soundness of light affine logic ⋮ Towards a theory of resource: an approach based on soft exponentials

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Linear logic
• Decision problems for propositional linear logic
• Bounded linear logic: A modular approach to polynomial-time computability
• Light linear logic
• Phase semantics for light linear logic
• Linear logic and elementary time
• Phase semantic cut-elimination and normalization proofs of first- and higher-order linear logic
• A uniform semantic proof for cut-elimination and completeness of various first and higher order logics.
• Soft linear logic and polynomial time
• Decidability of linear affine logic
• The finite model property for various fragments of intuitionistic linear logic
• The finite model property for various fragments of linear logic
• (Optimal) duplication is not elementary recursive
• Intuitionistic Light Affine Logic

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