A semantic proof of polytime soundness of light affine logic

DOI10.1007/S00224-009-9210-XzbMATH Open1205.68169OpenAlexW1967535898MaRDI QIDQ987375FDOQ987375

Martin Hofmann, Ugo Dal Lago

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)

Cites Work

• The lambda calculus. Its syntax and semantics. Rev. ed.
• Light linear logic
• Higher type recursion, ramification and polynomial time
• Safe recursion with higher types and BCK-algebra
• Soft linear logic and polynomial time
• Title not available (Why is that?)
• Title not available (Why is that?)
• Title not available (Why is that?)
• Title not available (Why is that?)
• Realizability models for BLL-like languages
• Title not available (Why is that?)
• Title not available (Why is that?)
• FSTTCS 2005: Foundations of Software Technology and Theoretical Computer Science
• Functional interpretations of feasibly constructive arithmetic
• The weak lambda calculus as a reasonable machine
• Title not available (Why is that?)
• Phase semantics and decidability of elementary affine logic

Cited In (12)

• Title not available (Why is that?)
• Theoretical Computer Science
• Realizability models and implicit complexity
• Quantitative classical realizability
• Implicit computation complexity in higher-order programming languages
• Realizability models for BLL-like languages
• Phase semantics and decidability of elementary affine logic
• On an interpretation of safe recursion in light affine logic
• Light affine set theory: A naive set theory of polynomial time
• A Semantic Proof of Polytime Soundness of Light Affine Logic
• Title not available (Why is that?)
• A quantitative model for simply typed λ-calculus

   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 👍 👎

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)