RAIRO-Theor. Inf. Appl.
Volume 37, Number 4, October-December 2003Fixed Points in Computer Science (FICS'02)
|Page(s)||315 - 336|
|Published online||15 January 2004|
Inst. of Cybernetics, Tallinn Technical Univ.,
Akadeemia tee 21, EE-12618 Tallinn, Estonia;
2 The work was largely done during the author's postdoctoral leave to Dep. de Informática, Univ. do Minho, Braga, Portugal.
Accepted: 13 August 2003
It is well known that, given an endofunctor H on a category C , the initial (A+H-)-algebras (if existing), i.e. , the algebras of (wellfounded) H-terms over different variable supplies A, give rise to a monad with substitution as the extension operation (the free monad induced by the functor H). Moss  and Aczel, Adámek, Milius and Velebil  have shown that a similar monad, which even enjoys the additional special property of having iterations for all guarded substitution rules (complete iterativeness), arises from the inverses of the final (A+H-)-coalgebras (if existing), i.e. , the algebras of non-wellfounded H-terms. We show that, upon an appropriate generalization of the notion of substitution, the same can more generally be said about the initial T'(A,-)-algebras resp. the inverses of the final T'(A,-)-coalgebras for any endobifunctor T' on any category C such that the functors T'(-,X) uniformly carry a monad structure.
Mathematics Subject Classification: 08B20 / 18C15 / 18C50
Key words: Algebras of terms / non-wellfounded terms / substitution / iteration of guarded substitution rules / monads / hyperfunctions / finitely or possibly infinitely branching trees.
© EDP Sciences, 2003
Current usage metrics show cumulative count of Article Views (full-text article views including HTML views, PDF and ePub downloads, according to the available data) and Abstracts Views on Vision4Press platform.
Data correspond to usage on the plateform after 2015. The current usage metrics is available 48-96 hours after online publication and is updated daily on week days.
Initial download of the metrics may take a while.