×

Finite behaviours and finitary corecursion. (English) Zbl 1433.68207

Bonchi, Filippo (ed.) et al., 7th conference on algebra and coalgebra in computer science, CALCO 2017, June 14–16, 2017, Ljubljana, Slovenia. Wadern: Schloss Dagstuhl – Leibniz Zentrum für Informatik. LIPIcs – Leibniz Int. Proc. Inform. 72, Article 24, 16 p. (2017).
Summary: In the coalgebraic approach to state-based systems, semantics is captured up to behavioural equivalence by special coalgebras such as the final coalgebra, the final locally finitely presentable coalgebra (Adámek, Milius, and Velebil), or the final locally finitely generated coalgebra (Milius, Pattinson, and Wißmann). The choice of the proper semantic domain is determined by finiteness restrictions imposed on the systems of interest. We propose a unifying perspective by introducing the concept of a final locally \((\mathbb{I},{\mathcal M})\)-presentable coalgebra, where the two parameters \(\mathbb{I}\) and \({\mathcal M}\) determine what a “finite” system is. Under suitable conditions on the categories and type functors, we show that the final locally \((\mathbb{I},{\mathcal M})\)-presentable coalgebra exists and coincides with the initial \((\mathbb{I},{\mathcal M})\)-iterative algebra, thereby putting a common roof over several results on iterative, fg-iterative and completely iterative algebras that were given a separate treatment before.
For the entire collection see [Zbl 1376.68006].

MSC:

68Q55 Semantics in the theory of computing
18C50 Categorical semantics of formal languages
PDFBibTeX XMLCite
Full Text: DOI