A new foundation for finitary corecursion and iterative algebras

Wißmann T, Pattinson D, Milius S (2019)


Publication Type: Journal article

Publication year: 2019

Journal

Article Number: 104456

DOI: 10.1016/j.ic.2019.104456

Abstract

This paper contributes to a generic theory of behaviour of “finite-state” systems. Systems are coalgebras with a finitely generated carrier for an endofunctor on a locally finitely presentable category. Their behaviour gives rise to the locally finite fixpoint (LFF), a new fixpoint of the endofunctor. The LFF exists provided that the endofunctor is finitary and preserves monomorphisms, is a subcoalgebra of the final coalgebra, i.e. it is fully abstract w.r.t. behavioural equivalence, and it is characterized by two universal properties: as the final locally finitely generated coalgebra, and as the initial fg-iterative algebra. Instances of the LFF are: regular languages, rational streams, rational formal power-series, regular trees etc. Moreover, we obtain e.g. (realtime deterministic resp. non-deterministic) context-free languages, constructively S-algebraic formal power-series (in general, the behaviour of finite coalgebras under the coalgebraic language semantics arising from the generalized powerset construction by Silva, Bonchi, Bonsangue, and Rutten), and the monad of Courcelle's algebraic trees.

Authors with CRIS profile

Involved external institutions

How to cite

APA:

Wißmann, T., Pattinson, D., & Milius, S. (2019). A new foundation for finitary corecursion and iterative algebras. Information and Computation. https://dx.doi.org/10.1016/j.ic.2019.104456

MLA:

Wißmann, Thorsten, Dirk Pattinson, and Stefan Milius. "A new foundation for finitary corecursion and iterative algebras." Information and Computation (2019).

BibTeX: Download