Categorical comprehensions and recursion

DOI10.1093/LOGCOM/EXW020MaRDI QIDQ3133177zbMATH OpenOpenAlexFDO

Authors Joaquín Díaz-Boïls

Publication date 13 February 2018

Published in Journal Of Logic And Computation (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1501.06889

zbMATH Keywords

hierarchysymmetric monoidal categorysafe recursionprimitive recursive functionsrecursion schemeramified recursion

Mathematics Subject Classification ID

Categorical logic, topoi (03G30) Recursive functions and relations, subrecursive hierarchies (03D20)

Abstract: A new categorical setting is defined in order to characterize the subrecursive classes belonging to complexity hierarchies. This is achieved by means of coercion functors over a symmetric monoidal category endowed with certain recursion schemes that imitate the bounded recursion scheme. This gives a categorical counterpart of generalized safe composition and safe recursion.

Recommendations

• A categorial approach to the theory of computation
• scientific article; zbMATH DE number 3893382
• Publication:4333486
• Aspects of categorical recursion theory
• scientific article; zbMATH DE number 3901002

Cited in

(7)

• Safe recursion revisited. I: Categorical semantics for lower complexity
• scientific article; zbMATH DE number 3944108 (Why is no real title available?)
• A categorical setting for lower complexity
• The Recursion Scheme from the Cofree Recursive Comonad
• Categorical characterizations of the natural numbers require primitive recursion
• Algebra and Coalgebra in Computer Science
• scientific article; zbMATH DE number 3950509 (Why is no real title available?)

This page was built for publication: Categorical comprehensions and recursion

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