On light logics, uniform encodings and polynomial time

DOI10.1017/S0960129506005421zbMATH Open1103.03060OpenAlexW2109174418MaRDI QIDQ5482265FDOQ5482265

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

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

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)

Cited In (11)

• Title not available (Why is that?)
• Title not available (Why is that?)
• Polynomial time in untyped elementary linear logic
• Theoretical Computer Science
• The role of polymorphism in the characterisation of complexity by soft types
• On the expressivity of elementary linear logic: characterizing Ptime and an exponential time hierarchy
• Implicit computation complexity in higher-order programming languages
• Characterizing polynomial and exponential complexity classes in elementary lambda-calculus
• Light affine set theory: A naive set theory of polynomial time
• A Semantic Proof of Polytime Soundness of Light Affine Logic
• Light logics and optimal reduction: completeness and complexity

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)