Hostname: page-component-6bf8c574d5-b4m5d Total loading time: 0 Render date: 2025-02-20T23:40:43.788Z Has data issue: false hasContentIssue false

Iterative algebras at work

Published online by Cambridge University Press:  01 November 2006

JIŘÍ ADÁMEK
Affiliation:
Institute of Theoretical Computer Science, Technical University, P.O. Box 3329, D-38023 Braunschweig, Germany Email: adamek@iti.cs.tu-bs.de, milius@iti.cs.tu-bs.de
STEFAN MILIUS
Affiliation:
Institute of Theoretical Computer Science, Technical University, P.O. Box 3329, D-38023 Braunschweig, Germany Email: adamek@iti.cs.tu-bs.de, milius@iti.cs.tu-bs.de
JIŘÍ VELEBIL
Affiliation:
Faculty of Electrical Engineering, Technical University, Technická 2, 16627 Prague 6, Czech Republic Email: velebil@math.feld.cvut.cz
Rights & Permissions [Opens in a new window]

Abstract

Core share and HTML view are not available for this content. However, as you have access to this content, a full PDF is available via the ‘Save PDF’ action button.

Iterative theories, which were introduced by Calvin Elgot, formalise potentially infinite computations as unique solutions of recursive equations. One of the main results of Elgot and his coauthors is a description of a free iterative theory as the theory of all rational trees. Their algebraic proof of this fact is extremely complicated. In our paper we show that by starting with ‘iterative algebras’, that is, algebras admitting a unique solution of all systems of flat recursive equations, a free iterative theory is obtained as the theory of free iterative algebras. The (coalgebraic) proof we present is dramatically simpler than the original algebraic one. Despite this, our result is much more general: we describe a free iterative theory on any finitary endofunctor of every locally presentable category $\cal{A}$.

Reportedly, a blow from the welterweight boxer Norman Selby, also known as Kid McCoy, left one victim proclaiming,

It's the real McCoy!’.

Type
Paper
Copyright
2006 Cambridge University Press