A P-Time completeness proof for light logics

DOI10.1007/3-540-48168-0_33MaRDI QIDQ4945245zbMATH OpenFDO

Authors Luca Roversi

Publication date 23 March 2000

Published in Lecture Notes in Computer Science (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1007/3-540-48168-0_33

zbMATH Keywords

Light Affine LogicLight Linear LogicP-Time completenessprogramming with feasible functions

Mathematics Subject Classification ID

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

Recommendations

• A semantic proof of polytime soundness of light affine logic
• A Semantic Proof of Polytime Soundness of Light Affine Logic
• Light logics and optimal reduction: completeness and complexity
• scientific article; zbMATH DE number 2061714
• On p-optimal proof systems and logics for PTIME
• On light logics, uniform encodings and polynomial time
• Weak completeness theorem for propositional linear time temporal logic
• Completeness proofs for propositional logic with polynomial-time connectives
• A logic for PTIME and a parameterized halting problem
• A hierarchical completeness proof for propositional temporal logic

Cited in

(11)

• Linear logic by levels and bounded time complexity
• Soft linear logic and polynomial time
• On an interpretation of safe recursion in light affine logic
• A type-assignment of linear erasure and duplication
• Light Linear Logic with Controlled Weakening
• Light linear logics with controlled weakening: expressibility, confluent strong normalization
• Encodings of Turing machines in linear logic
• Implicit computation complexity in higher-order programming languages
• Type inference for light affine logic via constraints on words
• Light affine lambda calculus and polynomial time strong normalization
• A semantic proof of polytime soundness of light affine logic

This page was built for publication: A P-Time completeness proof for light logics

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