Algebra and Coalgebra in Computer Science

DOI10.1007/11548133MaRDI QIDQ5492828zbMATH OpenOpenAlexFDO

Authors Stefan Milius, Lawrence S. Moss

Publication date 20 October 2006

Published in Lecture Notes in Computer Science (Search for Journal in Brave)

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

Mathematics Subject Classification ID

Mathematical aspects of software engineering (specification, verification, metrics, requirements, etc.) (68N30) Categorical semantics of formal languages (18C50)

Abstract: This paper provides a general account of the notion of recursive program schemes, studying both uninterpreted and interpreted solutions. It can be regarded as the category-theoretic version of the classical area of algebraic semantics. The overall assumptions needed are small indeed: working only in categories with "enough final coalgebras" we show how to formulate, solve, and study recursive program schemes. Our general theory is algebraic and so avoids using ordered, or metric structures. Our work generalizes the previous approaches which do use this extra structure by isolating the key concepts needed to study substitution in infinite trees, including second-order substitution. As special cases of our interpreted solutions we obtain the usual denotational semantics using complete partial orders, and the one using complete metric spaces. Our theory also encompasses implicitly defined objects which are not usually taken to be related to recursive program schemes. For example, the classical Cantor two-thirds set falls out as an interpreted solution (in our sense) of a recursive program scheme.

Recommendations

• The category-theoretic solution of recursive program schemes
• A category theoretic view of nondeterministic recursive program schemes
• Corrigendum to: ``The category theoretic solution of recursive program schemes [Theoret. Comput. Sci. 366 (2006) 3-59]
• scientific article; zbMATH DE number 5994844
• Categorification, term rewriting and the Knuth-Bendix procedure
• A category-theoretic account of program modules
• A category-theoretic account of program modules
• Programs as Diagrams
• Aspects of categorical recursion theory
• Categorical comprehensions and recursion

Cited in

(17)

• A category theoretic view of nondeterministic recursive program schemes
• Towards a geometry of recursion
• Algebraic solutions to recursion schemes
• scientific article; zbMATH DE number 5572668 (Why is no real title available?)
• The category-theoretic solution of recursive program schemes
• Recursive program schemes and context-free monads
• Categorial generalization of algebraic recursion theory
• A categorical framework for code evaluation method
• scientific article; zbMATH DE number 177429 (Why is no real title available?)
• scientific article; zbMATH DE number 3940702 (Why is no real title available?)
• A Mezei-Wright theorem for categorical algebras
• scientific article; zbMATH DE number 1752463 (Why is no real title available?)
• All solutions of a system of recursion equations in infinite trees and other contraction theories
• R-fuzzy computation
• Corrigendum to: ``The category theoretic solution of recursive program schemes [Theoret. Comput. Sci. 366 (2006) 3-59]
• The bicategory-theoretic solution of recursive domain equations
• Tail recursion through universal invariants

This page was built for publication: Algebra and Coalgebra in Computer Science

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