On light logics, uniform encodings and polynomial time

DOI10.1017/S0960129506005421MaRDI QIDQ5482265zbMATH OpenOpenAlexFDO

Authors Ugo Dal Lago, Patrick Baillot

Publication date 28 August 2006

Published in Mathematical Structures in Computer Science (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1017/s0960129506005421

zbMATH Keywords

Curry-Howard correspondencesecond-order quantifierslight affine logicextensional expressive powerpolytime completenesspolytime soundness

Mathematics Subject Classification ID

Logic in computer science (03B70) Proof-theoretic aspects of linear logic and other substructural logics (03F52)

Recommendations

• Theoretical Computer Science
• A Semantic Proof of Polytime Soundness of Light Affine Logic
• Linear logic and polynomial time
• A semantic proof of polytime soundness of light affine logic
• Intuitionistic light affine logic

Cited in

(13)

• Theoretical Computer Science
• Light logics and optimal reduction: completeness and complexity
• A Semantic Proof of Polytime Soundness of Light Affine Logic
• The role of polymorphism in the characterisation of complexity by soft types
• scientific article; zbMATH DE number 2061714 (Why is no real title available?)
• Implicit computation complexity in higher-order programming languages
• Polynomial time in untyped elementary linear logic
• FSTTCS 2005: Foundations of Software Technology and Theoretical Computer Science
• On the expressivity of elementary linear logic: characterizing Ptime and an exponential time hierarchy
• scientific article; zbMATH DE number 1424054 (Why is no real title available?)
• Characterizing polynomial and exponential complexity classes in elementary lambda-calculus
• A semantic proof of polytime soundness of light affine logic
• Light affine set theory: A naive set theory of polynomial time

This page was built for publication: On light logics, uniform encodings and polynomial time

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