On an interpretation of safe recursion in light affine logic

DOI10.1016/j.tcs.2003.10.017zbMath1048.03049OpenAlexW2076030590MaRDI QIDQ1827399

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) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Complexity classes (hierarchies, relations among complexity classes, etc.) (68Q15) Recursive functions and relations, subrecursive hierarchies (03D20) Proof-theoretic aspects of linear logic and other substructural logics (03F52)

Related Items

Light affine lambda calculus and polynomial time strong normalization ⋮ Light linear logics with controlled weakening: expressibility, confluent strong normalization ⋮ Soft linear set theory ⋮ Light Linear Logic with Controlled Weakening ⋮ Light types for polynomial time computation in lambda calculus ⋮ Bounded Linear Logic, Revisited ⋮ Some Complexity and Expressiveness Results on Multimodal and Stratified Proof Nets ⋮ Linear logic by levels and bounded time complexity ⋮ Proof-Theoretic Semantics and Feasibility ⋮ Implicit computation complexity in higher-order programming languages

Cites Work

• A new recursion-theoretic characterization of the polytime functions
• Light linear logic
• Linear types and non-size-increasing polynomial time computation.
• Unnamed Item
• Unnamed Item
• Unnamed Item