𝔖 Bobbio Scriptorium
✦   LIBER   ✦

A Coalgebraic View of Infinite Trees and Iteration

✍ Scribed by Peter Aczel; Jiří Adámek; Jiří Velebil

Publisher
Elsevier Science
Year
2001
Tongue
English
Weight
255 KB
Volume
44
Category
Article
ISSN
1571-0661

No coin nor oath required. For personal study only.

✦ Synopsis

The algebra of infinite trees is, as proved by C. Elgot, completely iterative, i.e., all ideal recursive equations are uniquely solvable. This is proved here to be a general coalgebraic phenomenon: let H be an endofunctor such that for every object X a final coalgebra, T X, of H( )+X exists. Then T X is an object-part of a monad which is completely iterative. Moreover, a similar contruction of a "completely iterative monoid" is possible in every monoidal category satisfying mild side conditions.

📜 SIMILAR VOLUMES

Infinite trees and completely iterative
Infinite trees and completely iterative theories: a coalgebraic view
✍ Peter Aczel; Jiřı́ Adámek; Stefan Milius; Jiřı́ Velebil 📂 Article 📅 2003 🏛 Elsevier Science 🌐 English ⚖ 533 KB

Inÿnite trees form a free completely iterative theory over any given signature-this fact, proved by Elgot, Bloom and Tindell, turns out to be a special case of a much more general categorical result exhibited in the present paper. We prove that whenever an endofunctor H of a category has ÿnal coalge

Agent searching in a tree and the optima
Agent searching in a tree and the optimality of iterative deepening
✍ Pallab Dasgupta; P.P. Chakrabarti; S.C. DeSarkar 📂 Article 📅 1994 🏛 Elsevier Science 🌐 English ⚖ 695 KB

The agent searching framework models the effort of a search strategy in terms of the distance traversed by an agent while exploring the search space. The framework has been found to be useful in modeling search problems where the cost of backtracking and retracing search paths is important in determ