# Covarieties of Coalgebras: Comonads and Coequations

• Ranald Clouston
• Robert Goldblatt
Conference paper
Part of the Lecture Notes in Computer Science book series (LNCS, volume 3722)

## Abstract

Coalgebras provide effective models of data structures and state-transition systems. A virtual covariety is a class of coalgebras closed under coproducts, images of coalgebraic morphisms, and subcoalgebras defined by split equalisers. A covariety has the stronger property of closure under all subcoalgebras, and is behavioural if it is closed under domains of morphisms, or equivalently under images of bisimulations. There are many computationally interesting properties that define classes of these kinds.

We identify conditions on the underlying category of a comonad $$\mathbb{G}$$ which ensure that there is an exact correspondence between (behavioural/virtual) covarieties of $$\mathbb{G}$$-coalgebras and subcomonads of $$\mathbb{G}$$ defined by comonad morphisms to $$\mathbb{G}$$ with natural categorical properties. We also relate this analysis to notions of coequationally defined classes of coalgebras.

## Keywords

Inverse Image Full Subcategory Universal Algebra Free Algebra Label Transition System
These keywords were added by machine and not by the authors. This process is experimental and the keywords may be updated as the learning algorithm improves.

## References

1. 1.
Reichel, H.: An approach to object semantics based on terminal co-algebras. Mathematical Structures in Computer Science 5, 129–152 (1995)
2. 2.
Jacobs, B.: Objects and classes, coalgebraically. In: Freitag, B., Jones, C.B., Lengauer, C., Schek, H.J. (eds.) Object-Orientation with Parallelism and Persistence, pp. 83–103. Kluwer Academic Publishers, Dordrecht (1996)Google Scholar
3. 3.
Rutten, J.J.M.M.: A calculus of transition systems (towards universal coalgebra). In: Ponse, A., de Rijke, M., Venema, Y. (eds.) Modal Logic and Process Algebra. CSLI Lecture Notes No. 53, pp. 231–256. CSLI Publications, Stanford (1995)Google Scholar
4. 4.
Rutten, J.: Universal coalgebra: a theory of systems. Theoretical Computer Science 249, 3–80 (2000)
5. 5.
Jacobs, B., Rutten, J.: A tutorial on (co)algebras and (co)induction. Bulletin of the European Association for Theoretical Computer Science 62, 222–259 (1997)
6. 6.
Jacobs, B.: Exercises in coalgebraic specification. In Backhouse. In: Blackhouse, R., Crole, R.L., Gibbons, J. (eds.) Algebraic and Coalgebraic Methods in the Mathematics of Program Construction. LNCS, vol. 2297, pp. 237–280. Springer, Heidelberg (2002)
7. 7.
Birkhoff, G.: On the structure of abstract algebras. Proceedings of the Cambridge Philosophical Society 31, 433–454 (1935)
8. 8.
Hennessy, M., Milner, R.: Algebraic laws for nondeterminism and concurrency. Journal of the Association for Computing Machinery 32, 137–161 (1985)
9. 9.
Goldblatt, R.: A comonadic account of behavioural covarieties of coalgebras. Mathematical Structures in Computer Science 15, 243–269 (2005)
10. 10.
Gumm, H.P., Schröder, T.: Coalgebraic structure from weak limit preserving functors. Electronic Notes in Theoretical Computer Science 33 (2000)Google Scholar
11. 11.
Awodey, S., Hughes, J.: The coalgebraic dual of Birkhoff’s variety theorem. Technical Report CMU-PHIL-109, Department of Philosophy, Carnegie Mellon University (2000)Google Scholar
12. 12.
Hughes, J.: A Study of Categories of Algebras and Coalgebras. PhD thesis, Carnegie Mellon University (2001)Google Scholar
13. 13.
Awodey, S., Hughes, J.: Modal operators and the formal dual of Birkhoff’s completeness theorem. Mathematical Structures in Computer Science 13, 233–258 (2003)
14. 14.
Banaschewski, B., Herrlich, H.: Subcategories defined by implications. Houston Journal of Mathematics 2, 149–171 (1976)
15. 15.
Adámek, J., Porst, H.E.: On varieties and covarieties in a category. Mathematical Structures in Computer Science 13, 201–232 (2003)
16. 16.
Borceux, F.: Handbook of Categorical Algebra 2. Categories and Structures. Cambridge University Press, Cambridge (1994)
17. 17.
Barr, M., Wells, C.: Toposes, Triples and Theories. Springer, Heidelberg (1985)
18. 18.
Mac Lane, S.: Categories for the Working Mathematician. Springer, Heidelberg (1971)
19. 19.
Herrlich, H., Strecker, G.: Category Theory. Allyn and Bacon, Newton (1973)
20. 20.
Wyler, O.: Lecture Notes on Topoi and Quasitopoi. World Scientific, Singapore (1991)
21. 21.
Kurz, A.: Logics for Coalgebras and Applications to Computer Science. PhD thesis, Ludwig-Maximilians-Universität München (2000)Google Scholar