Categorical comprehensions and recursion

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

Authors: 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

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

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)

Cited In (7)

• Safe recursion revisited. I: Categorical semantics for lower complexity
• Title not available (Why is that?)
• 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
• Title not available (Why is that?)

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)