On light logics, uniform encodings and polynomial time

DOI10.1017/S0960129506005421zbMath1103.03060OpenAlexW2109174418MaRDI QIDQ5482265

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)

Related Items (6)

The role of polymorphism in the characterisation of complexity by soft types ⋮ Characterizing polynomial and exponential complexity classes in elementary lambda-calculus ⋮ Light logics and optimal reduction: completeness and complexity ⋮ Polynomial time in untyped elementary linear logic ⋮ On the expressivity of elementary linear logic: characterizing Ptime and an exponential time hierarchy ⋮ Implicit computation complexity in higher-order programming languages

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