Realizability models and implicit complexity

DOI10.1016/J.TCS.2010.12.025zbMATH Open1222.03065OpenAlexW1989703373MaRDI QIDQ534712FDOQ534712

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

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

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)

Cites Work

• Title not available (Why is that?)
• Light linear logic
• Linear types and non-size-increasing polynomial time computation.
• Higher type recursion, ramification and polynomial time
• Safe recursion with higher types and BCK-algebra
• Soft linear logic and polynomial time
• Intuitionistic Light Affine Logic
• Title not available (Why is that?)
• A small complete category
• 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?)
• Foundations of Software Science and Computation Structures
• FSTTCS 2005: Foundations of Software Technology and Theoretical Computer Science
• Functional interpretations of feasibly constructive arithmetic
• The weak lambda calculus as a reasonable machine
• A semantic proof of polytime soundness of light affine logic

Cited In (11)

• Title not available (Why is that?)
• FSTTCS 2005: Foundations of Software Technology and Theoretical Computer Science
• Higher-order interpretations and program complexity
• Realizability models for a linear dependent PCF
• Quantitative classical realizability
• Implicit computation complexity in higher-order programming languages
• Probabilistic Termination by Monadic Affine Sized Typing
• On basic feasible functionals and the interpretation method
• Elementary complexity and geometry of interaction
• Realizability Models Separating Various Fan Theorems
• A quantitative model for simply typed λ-calculus

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)