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