A Categorical Setting for Lower Complexity

DOI10.1016/j.entcs.2010.08.017zbMath1342.68128OpenAlexW1978419421MaRDI QIDQ3178259

Brian F. Redmond, J. Robin B. Cockett

Publication date: 8 July 2016

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

Full work available at URL: https://doi.org/10.1016/j.entcs.2010.08.017

zbMATH Keywords

complexityfibrationspolarized categoriesrecursion principles

Mathematics Subject Classification ID

Complexity of computation (including implicit computational complexity) (03D15)

Related Items

Bounded combinatory logic and lower complexity, Timed Sets, Functional Complexity, and Computability, Safe recursion revisited. I: Categorical semantics for lower complexity

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Safe recursion revisited. I: Categorical semantics for lower complexity
• 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 new constructive logic: classic logic
• FSTTCS 2005: Foundations of Software Technology and Theoretical Computer Science