On functors preserving coproducts and algebras with iterativity

Adamek J, Milius S (2019)

Publication Type: Journal article

Publication year: 2019

Journal

Theoretical Computer Science Elsevier

Book Volume: 763

Pages Range: 66-87

DOI: 10.1016/j.tcs.2019.01.018

Abstract

An algebra for a functor H is called completely iterative (cia, for short) if every flat recursive equation in it has a unique solution. Every cia is corecursive, i.e., it admits a unique coalgebra-to-algebra morphism from every coalgebra. If the converse also holds, H is called a cia functor. We prove that whenever the base category is hyper-extensive (i.e. countable coproducts are 'well-behaved') and H preserves countable coproducts, then H is a cia functor. Surprisingly few cia functors exist among standard finitary set functors: in fact, the only ones are those preserving coproducts; they are given by X bar right arrow W x (-) + Y for some sets W and Y. (C) 2019 Elsevier B.V. All rights reserved.

Authors with CRIS profile

Stefan Milius 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. (2019). On functors preserving coproducts and algebras with iterativity. Theoretical Computer Science, 763, 66-87. https://dx.doi.org/10.1016/j.tcs.2019.01.018

MLA:

Adamek, Jiri, and Stefan Milius. "On functors preserving coproducts and algebras with iterativity." Theoretical Computer Science 763 (2019): 66-87.

BibTeX: Download