Advertisement

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.

Preview

Unable to display preview. Download preview PDF.

Unable to display preview. Download preview PDF.

References

  1. 1.
    Reichel, H.: An approach to object semantics based on terminal co-algebras. Mathematical Structures in Computer Science 5, 129–152 (1995)zbMATHCrossRefMathSciNetGoogle Scholar
  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)zbMATHCrossRefMathSciNetGoogle Scholar
  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)zbMATHGoogle Scholar
  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)CrossRefGoogle Scholar
  7. 7.
    Birkhoff, G.: On the structure of abstract algebras. Proceedings of the Cambridge Philosophical Society 31, 433–454 (1935)CrossRefGoogle Scholar
  8. 8.
    Hennessy, M., Milner, R.: Algebraic laws for nondeterminism and concurrency. Journal of the Association for Computing Machinery 32, 137–161 (1985)zbMATHMathSciNetGoogle Scholar
  9. 9.
    Goldblatt, R.: A comonadic account of behavioural covarieties of coalgebras. Mathematical Structures in Computer Science 15, 243–269 (2005)zbMATHCrossRefMathSciNetGoogle Scholar
  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)zbMATHCrossRefMathSciNetGoogle Scholar
  14. 14.
    Banaschewski, B., Herrlich, H.: Subcategories defined by implications. Houston Journal of Mathematics 2, 149–171 (1976)zbMATHMathSciNetGoogle Scholar
  15. 15.
    Adámek, J., Porst, H.E.: On varieties and covarieties in a category. Mathematical Structures in Computer Science 13, 201–232 (2003)zbMATHCrossRefGoogle Scholar
  16. 16.
    Borceux, F.: Handbook of Categorical Algebra 2. Categories and Structures. Cambridge University Press, Cambridge (1994)zbMATHCrossRefGoogle Scholar
  17. 17.
    Barr, M., Wells, C.: Toposes, Triples and Theories. Springer, Heidelberg (1985)zbMATHGoogle Scholar
  18. 18.
    Mac Lane, S.: Categories for the Working Mathematician. Springer, Heidelberg (1971)zbMATHGoogle Scholar
  19. 19.
    Herrlich, H., Strecker, G.: Category Theory. Allyn and Bacon, Newton (1973)zbMATHGoogle Scholar
  20. 20.
    Wyler, O.: Lecture Notes on Topoi and Quasitopoi. World Scientific, Singapore (1991)zbMATHGoogle Scholar
  21. 21.
    Kurz, A.: Logics for Coalgebras and Applications to Computer Science. PhD thesis, Ludwig-Maximilians-Universität München (2000)Google Scholar

Copyright information

© Springer-Verlag Berlin Heidelberg 2005

Authors and Affiliations

  • Ranald Clouston
    • 1
  • Robert Goldblatt
    • 1
  1. 1.Centre for Logic, Language and ComputationVictoria University of WellingtonNew Zealand

Personalised recommendations