Safe recursion revisited. I: Categorical semantics for lower complexity

DOI10.1016/j.tcs.2013.09.034zbMath1277.68115OpenAlexW2064666203MaRDI QIDQ386608

Mike Burrell, J. Robin B. Cockett, Brian F. Redmond

Publication date: 10 December 2013

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

Full work available at URL: https://doi.org/10.1016/j.tcs.2013.09.034

zbMATH Keywords

implicit computational complexitycategorical semanticssafe recursion

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Semantics in the theory of computing (68Q55) Categorical semantics of formal languages (18C50)

Related Items

Bounded combinatory logic and lower complexity, A Categorical Setting for Lower Complexity

Cites Work

• A categorical semantics for polarized MALL
• Monoidal categories with natural numbers object
• A new recursion-theoretic characterization of the polytime functions
• Structural induction and coinduction in a fibrational setting
• Linear types and non-size-increasing polynomial time computation.
• Focussing and proof construction
• Polarized games
• Strong functors and monoidal monads
• A Categorical Setting for Lower Complexity
• A new constructive logic: classic logic
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item