A semantic proof of polytime soundness of light affine logic

DOI10.1007/S00224-009-9210-XzbMATH1205.68169OpenAlexW1967535898MaRDI QIDQ987375FDOQ987375

Authors Ugo Dal Lago, Martin Hofmann

Publication date 13 August 2010

Published in Theory of Computing Systems (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1007/s00224-009-9210-x

zbMATH Keywords

implicit computational complexitylinear logicrealizability

Mathematics Subject Classification ID

Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17)

Recommendations

• A Semantic Proof of Polytime Soundness of Light Affine Logic
• Theoretical Computer Science
• FSTTCS 2005: Foundations of Software Technology and Theoretical Computer Science
• Intuitionistic light affine logic
• On light logics, uniform encodings and polynomial time

Cites work

• scientific article; zbMATH DE number 1670494 (Why is no real title available?)
• scientific article; zbMATH DE number 1722649 (Why is no real title available?)
• scientific article; zbMATH DE number 4055576 (Why is no real title available?)
• scientific article; zbMATH DE number 1142308 (Why is no real title available?)
• scientific article; zbMATH DE number 2061700 (Why is no real title available?)
• scientific article; zbMATH DE number 1424054 (Why is no real title available?)
• scientific article; zbMATH DE number 3216998 (Why is no real title available?)
• FSTTCS 2005: Foundations of Software Technology and Theoretical Computer Science
• Functional interpretations of feasibly constructive arithmetic
• Higher type recursion, ramification and polynomial time
• Light linear logic
• Phase semantics and decidability of elementary affine logic
• Realizability models for BLL-like languages
• Safe recursion with higher types and BCK-algebra
• Soft linear logic and polynomial time
• The lambda calculus. Its syntax and semantics. Rev. ed.
• The weak lambda calculus as a reasonable machine

Cited in

(15)

• Theoretical Computer Science
• A Semantic Proof of Polytime Soundness of Light Affine Logic
• Realizability models and implicit complexity
• Implicit computation complexity in higher-order programming languages
• scientific article; zbMATH DE number 1670494 (Why is no real title available?)
• Realizability models for BLL-like languages
• FSTTCS 2005: Foundations of Software Technology and Theoretical Computer Science
• Quantitative classical realizability
• On light logics, uniform encodings and polynomial time
• A quantitative model for simply typed λ-calculus
• On an interpretation of safe recursion in light affine logic
• scientific article; zbMATH DE number 1424054 (Why is no real title available?)
• Phase semantics and decidability of elementary affine logic
• Intuitionistic light affine logic
• Light affine set theory: A naive set theory of polynomial time

This page was built for publication: A semantic proof of polytime soundness of light affine logic

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