×

Coalgebraic coinduction in (hyper)set-theoretic categories. (English) Zbl 0963.18002

Reichel, Horst (ed.), CMCS 2000. Coalgebraic methods in computer science, Berlin, Germany, March 25-26, 2000. Amsterdam: Elsevier, Electronic Notes in Theoretical Computer Science. 33, 28 p., electronic only (2000).
Summary: This paper is a contribution to the foundations of coinductive types and coiterative functions, in (hyper)set-theoretical categories, in terms of coalgebras. We consider atoms as first class citizens. First of all, we give a sharpening, in the way of cardinality, of Aczel’s special final coalgebra theorem, which allows for good estimates of the cardinality of the final coalgebra. To these end, we introduce the notion of \(\kappa\)-\(Y\)-uniform functor, which subsumes Aczel’s original notion. We give also an \(n\)-ary version of it, and we show that the resulting class of functors is closed under many interesting operations used in final semantics. We define also canonical wellfounded versions of the final coalgebras of functors uniform on maps. This leads to a reduction of coiteration to ordinal induction, giving a possible answer to a question raised by Moss and Danner. Finally, we introduce a generalization of the notion of \(F\)-bisimulation inspired by Aczel’s notion of precongruence, and we show that it allows to extend the theory of categorical bisimulations also to functors non-weakly preserving pullbacks. Examples, non-examples, and open questions are frequent in the paper.
For the entire collection see [Zbl 0942.00060].

MSC:

18C50 Categorical semantics of formal languages
68Q55 Semantics in the theory of computing
18A30 Limits and colimits (products, sums, directed limits, pushouts, fiber products, equalizers, kernels, ends and coends, etc.)
PDFBibTeX XMLCite