Categorial generalization of algebraic recursion theory
type: Item
instance of: scholarly article
title: Categorial generalization of algebraic recursion theory
zbMATH Open document ID: 0867.03015
DOI: 10.1016/0022-4049(93)E0184-6
author: Yanyan Li
published in: Journal of Pure and Applied Algebra
publication date: 1997-08-11T00:00:00Z
review text: A categorical generalization of a point-free presentation of recursion theory, called ``algebraic recursion theory'', is presented. Algebraic recursion theory studies least fixpoints (least solutions of systems of inequalities) in partially ordered universal algebras (poalgebras) with operations, monotone in each argument. The categorical generalization of this approach uses instead of a poalgebra a category \(C\) with a set of multi-endofunctors, and an appropriate generalization of inequalities; least fixpoints are taken in the sense of \textit{J. Lambek} [``A fixpoint theorem for complete categories'', Math. Z. 103, 151-161 (1968; Zbl 0149.26105)]. The problem to be solved is formulated in the following way: given such \(C\), find a simple set \(B\) of inductively definable multi-endofunctors, such that for every \(F:C^{n+m}\to C^m\) (a) the least fixpoint of \(F\) exists and (b) is explicitly expressible by means of basic multi-endofunctors and these form \(B\). This problem is solved for so called DM-categories, suggested by the author. They are categorical generalizations of ``operation spaces'' [\textit{L. L. Ivanov}, Algebraic recursion theory (1986; Zbl 0613.03018)]. Their structure is a combination of monoidal and Cartesian structure. There are three main examples; one is defined using a category of all categories with certain properties (initial object, direct limits of \(\omega\)-sequences, etc.); two others are the category of abstract programs and correctness proofs and the category of logical programs and correctness proofs.
Mathematics Subject Classification ID: 03D75
Mathematics Subject Classification ID: 03G30
Mathematics Subject Classification ID: 03B70
Mathematics Subject Classification ID: 18C10
zbMATH DE Number: 797260
zbMATH Keywords: fixpoints in categories
zbMATH Keywords: operation spaces
zbMATH Keywords: point-free recursion theory
zbMATH Keywords: least fixpoints
zbMATH Keywords: multi-endofunctors
zbMATH Keywords: category of abstract programs and correctness proofs
zbMATH Keywords: category of logical programs and correctness proofs
reviewed by: Serguei V. Solov'ev
MaRDI profile type: Publication
cites work: Q3753993
cites work: A fixpoint theorem for complete categories
cites work: Q5639839
cites work: Q5632554
cites work: Q4093428
cites work: Q3898488
cites work: Q4003236
cites work: Q3333024
cites work: Q3800024
cites work: Q4694257
cites work: Q4039125
cites work: Q4325153
Recommended article: Q4325153
Recommended article: Q3679367
Recommended article: Q3720582
Recommended article: Algebra and Coalgebra in Computer Science
Recommended article: Q3744154
Recommended article: Algebraic solutions to recursion schemes
Recommended article: The category-theoretic solution of recursive program schemes
Recommended article: Categorical Büchi and parity conditions via alternating fixed points of functors
Recommended article: Algebras, polynomials and programs
Recommended article: Q3365537
description: scientific article; zbMATH DE number 797260