Realizability models and implicit complexity

DOI10.1016/J.TCS.2010.12.025MaRDI QIDQ534712zbMATH OpenOpenAlexFDO

Authors Ugo Dal Lago, Martin Hofmann

Publication date 10 May 2011

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

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

zbMATH Keywords

implicit computational complexitylinear logicmodalityrealizabilitypolymorphisminductive datatypes

Mathematics Subject Classification ID

Logic in computer science (03B70) Proof-theoretic aspects of linear logic and other substructural logics (03F52) Complexity of computation (including implicit computational complexity) (03D15)

Recommendations

• FSTTCS 2005: Foundations of Software Technology and Theoretical Computer Science
• A semantic proof of polytime soundness of light affine logic
• A Semantic Proof of Polytime Soundness of Light Affine Logic
• Realizability models for BLL-like languages
• Linear logic and polynomial time

Cites work

• scientific article; zbMATH DE number 1722649 (Why is no real title available?)
• scientific article; zbMATH DE number 3889501 (Why is no real title available?)
• scientific article; zbMATH DE number 4049849 (Why is no real title available?)
• scientific article; zbMATH DE number 42059 (Why is no real title available?)
• scientific article; zbMATH DE number 1142308 (Why is no real title available?)
• scientific article; zbMATH DE number 3216998 (Why is no real title available?)
• scientific article; zbMATH DE number 4189687 (Why is no real title available?)
• A semantic proof of polytime soundness of light affine logic
• A small complete category
• FSTTCS 2005: Foundations of Software Technology and Theoretical Computer Science
• Foundations of Software Science and Computation Structures
• Functional interpretations of feasibly constructive arithmetic
• Higher type recursion, ramification and polynomial time
• Intuitionistic light affine logic
• Light linear logic
• Linear types and non-size-increasing polynomial time computation.
• Realizability models for BLL-like languages
• Safe recursion with higher types and BCK-algebra
• Soft linear logic and polynomial time
• The weak lambda calculus as a reasonable machine

Cited in

(11)

• Higher-order interpretations and program complexity
• Probabilistic termination by monadic affine sized typing
• Implicit computation complexity in higher-order programming languages
• FSTTCS 2005: Foundations of Software Technology and Theoretical Computer Science
• Elementary complexity and geometry of interaction
• Quantitative classical realizability
• scientific article; zbMATH DE number 7561616 (Why is no real title available?)
• A quantitative model for simply typed λ-calculus
• Realizability Models Separating Various Fan Theorems
• On basic feasible functionals and the interpretation method
• Realizability models for a linear dependent PCF

This page was built for publication: Realizability models and implicit complexity

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