Elgot Algebras

DOI10.2168/LMCS-2(5:4)2006MaRDI QIDQ5310675zbMATH OpenFDO

Authors Jiří Adámek, Stefan Milius, Jiří Velebil

Publication date 11 October 2007

Published in Logical Methods in Computer Science (Search for Journal in Brave)

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

Mathematics Subject Classification ID

Theories (e.g., algebraic theories), structure, and semantics (18C10) Semantics in the theory of computing (68Q55) Abstract data types; algebraic specification (68Q65)

Abstract: Denotational semantics can be based on algebras with additional structure (order, metric, etc.) which makes it possible to interpret recursive specifications. It was the idea of Elgot to base denotational semantics on iterative theories instead, i.e., theories in which abstract recursive specifications are required to have unique solutions. Later Bloom and Esik studied iteration theories and iteration algebras in which a specified solution has to obey certain axioms. We propose so-called Elgot algebras as a convenient structure for semantics in the present paper. An Elgot algebra is an algebra with a specified solution for every system of flat recursive equations. That specification satisfies two simple and well motivated axioms: functoriality (stating that solutions are stable under renaming of recursion variables) and compositionality (stating how to perform simultaneous recursion). These two axioms stem canonically from Elgot's iterative theories: We prove that the category of Elgot algebras is the Eilenberg-Moore category of the monad given by a free iterative theory.

Recommendations

• Elgot algebras (extended abstract)
• Elliptic algebras
• scientific article; zbMATH DE number 742679
• scientific article; zbMATH DE number 4042121
• scientific article; zbMATH DE number 918232
• Exotic elliptic algebras
• EBL-algebras
• Gamow algebras
• Elliptic Hopf Algebras
• scientific article; zbMATH DE number 688048

Cited in

(20)

• A Mezei-Wright theorem for categorical algebras
• On functors preserving coproducts and algebras with iterativity
• Iteration and labelled iteration
• Complete Elgot monads and coalgebraic resumptions
• On algebras with effectful iteration
• Corecursive algebras in nature
• Monads for behaviour
• Elgot theories: a new perspective of iteration theories (extended abstract)
• The coinductive resumption monad
• Elgot algebras (extended abstract)
• A Description of Iterative Reflections of Monads (Extended Abstract)
• Unguarded recursion on coinductive resumptions
• Proper functors and fixed points for finite behaviour
• Eilenberg-Moore monoids and backtracking monad transformers
• Well-founded coalgebras, revisited
• Optimal coin flipping
• The Sierpinski carpet as a final coalgebra
• Uniform Elgot iteration in foundations
• Modular abstract syntax trees (MAST): substitution tensors with second-class sorts
• Corrigendum to: ``The category theoretic solution of recursive program schemes [Theoret. Comput. Sci. 366 (2006) 3-59]

This page was built for publication: Elgot Algebras

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