On the behaviour of coalgebras with side effects and algebras with effectful iteration

Adamek J, Milius S, Urbat H (2021)

Publication Type: Journal article

Publication year: 2021

Journal

Journal of Logic and Computation Oxford University Press (OUP): Policy A - Oxford Open Option A

Book Volume: 31

Pages Range: 1429-1481

Journal Issue: 6

DOI: 10.1093/logcom/exab049

Abstract

For every finitary monad T on sets and every endofunctor F on the category of T-algebras, we introduce the concept of an ffg-Elgot algebra for F, i.e. an algebra admitting coherent solutions for finite systems of recursive equations with effects represented by the monad T. The goal is to study the existence and construction of free ffg-Elgot algebras. To this end, we investigate the locally ffg fixed point phi(F), i.e. the colimit of all F-coalgebras with free finitely generated carrier, which is shown to be the initial ffg-Elgot algebra. This is the technical foundation for our main result: the category of ffg-Elgot algebras is monadic over the category of T-algebras.

Authors with CRIS profile

Stefan Milius Lehrstuhl für Informatik 8 (Theoretische Informatik) Henning Urbat Lehrstuhl für Informatik 8 (Theoretische Informatik)

Involved external institutions

Czech Technical University in Prague / České vysoké učení technické v Praze CZ Czech Republic (CZ)

How to cite

APA:

Adamek, J., Milius, S., & Urbat, H. (2021). On the behaviour of coalgebras with side effects and algebras with effectful iteration. Journal of Logic and Computation, 31(6), 1429-1481. https://dx.doi.org/10.1093/logcom/exab049

MLA:

Adamek, Jiri, Stefan Milius, and Henning Urbat. "On the behaviour of coalgebras with side effects and algebras with effectful iteration." Journal of Logic and Computation 31.6 (2021): 1429-1481.

BibTeX: Download