On an interpretation of safe recursion in light affine logic

DOI10.1016/J.TCS.2003.10.017MaRDI QIDQ1827399zbMATH OpenOpenAlexFDO

Authors Yanyan Li

Publication date 6 August 2004

Published in Theoretical Computer Science (Search for Journal in Brave)

Full work available at URL https://ora.ox.ac.uk/objects/uuid:1ecaf989-a3be-4dd6-9255-c5f3679209e4

zbMATH Keywords

Computational complexityLight affine logicPolynomial-time computability

Mathematics Subject Classification ID

Complexity of computation (including implicit computational complexity) (03D15) Recursive functions and relations, subrecursive hierarchies (03D20) Proof-theoretic aspects of linear logic and other substructural logics (03F52) Complexity classes (hierarchies, relations among complexity classes, etc.) (68Q15) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17)

Recommendations

• Theoretical Computer Science
• Safe recursion with higher types and BCK-algebra
• A semantic proof of polytime soundness of light affine logic
• A Semantic Proof of Polytime Soundness of Light Affine Logic
• scientific article; zbMATH DE number 1223626

Cites work

• A new recursion-theoretic characterization of the polytime functions
• scientific article; zbMATH DE number 1497809 (Why is no real title available?)
• scientific article; zbMATH DE number 1392281 (Why is no real title available?)
• scientific article; zbMATH DE number 1424054 (Why is no real title available?)
• Light linear logic
• Linear types and non-size-increasing polynomial time computation.

Cited in

(13)

• Light types for polynomial time computation in lambda calculus
• Linear logic by levels and bounded time complexity
• Safe operators: Brackets closed forever. Optimizing optimal -calculus implementations
• Light Linear Logic with Controlled Weakening
• Some Complexity and Expressiveness Results on Multimodal and Stratified Proof Nets
• Light linear logics with controlled weakening: expressibility, confluent strong normalization
• scientific article; zbMATH DE number 1223626 (Why is no real title available?)
• Proof-theoretic semantics and feasibility
• Implicit computation complexity in higher-order programming languages
• Theoretical Computer Science
• Bounded Linear Logic, Revisited
• Light affine lambda calculus and polynomial time strong normalization
• Soft linear set theory

This page was built for publication: On an interpretation of safe recursion in light affine logic

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