Categorical comprehensions and recursion

DOI10.1093/LOGCOM/EXW020zbMATH Open1406.03054arXiv1501.06889OpenAlexW2964285400MaRDI QIDQ3133177

Joaquín Díaz-Boïls

Publication date: 13 February 2018

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

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.

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)

Related Items (3)

Categorical characterizations of the natural numbers require primitive recursion ⋮ Algebra and Coalgebra in Computer Science ⋮ The Recursion Scheme from the Cofree Recursive Comonad

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)