A coalgebraic view on reachability

Thorsten Wißmann; Stefan Milius; Shin-ya Katsumata; Jérémy Dubut

Commentationes Mathematicae Universitatis Carolinae (2019)

  • Volume: 60, Issue: 4, page 605-638
  • ISSN: 0010-2628

Abstract

top
Coalgebras for an endofunctor provide a category theoretic framework for modeling a wide range of state-based systems of various types. We provide an iterative construction of the reachable part of a given pointed coalgebra that is inspired by and resembles the standard breadth-first search procedure to compute the reachable part of a graph. We also study coalgebras in Kleisli categories: for a functor extending a functor on the base category, we show that the reachable part of a given pointed coalgebra can be computed in that base category.

How to cite

top

Wißmann, Thorsten, et al. "A coalgebraic view on reachability." Commentationes Mathematicae Universitatis Carolinae 60.4 (2019): 605-638. <http://eudml.org/doc/295060>.

@article{Wißmann2019,
abstract = {Coalgebras for an endofunctor provide a category theoretic framework for modeling a wide range of state-based systems of various types. We provide an iterative construction of the reachable part of a given pointed coalgebra that is inspired by and resembles the standard breadth-first search procedure to compute the reachable part of a graph. We also study coalgebras in Kleisli categories: for a functor extending a functor on the base category, we show that the reachable part of a given pointed coalgebra can be computed in that base category.},
author = {Wißmann, Thorsten, Milius, Stefan, Katsumata, Shin-ya, Dubut, Jérémy},
journal = {Commentationes Mathematicae Universitatis Carolinae},
keywords = {coalgebra; reachability; Kleisli category},
language = {eng},
number = {4},
pages = {605-638},
publisher = {Charles University in Prague, Faculty of Mathematics and Physics},
title = {A coalgebraic view on reachability},
url = {http://eudml.org/doc/295060},
volume = {60},
year = {2019},
}

TY - JOUR
AU - Wißmann, Thorsten
AU - Milius, Stefan
AU - Katsumata, Shin-ya
AU - Dubut, Jérémy
TI - A coalgebraic view on reachability
JO - Commentationes Mathematicae Universitatis Carolinae
PY - 2019
PB - Charles University in Prague, Faculty of Mathematics and Physics
VL - 60
IS - 4
SP - 605
EP - 638
AB - Coalgebras for an endofunctor provide a category theoretic framework for modeling a wide range of state-based systems of various types. We provide an iterative construction of the reachable part of a given pointed coalgebra that is inspired by and resembles the standard breadth-first search procedure to compute the reachable part of a graph. We also study coalgebras in Kleisli categories: for a functor extending a functor on the base category, we show that the reachable part of a given pointed coalgebra can be computed in that base category.
LA - eng
KW - coalgebra; reachability; Kleisli category
UR - http://eudml.org/doc/295060
ER -

References

top
  1. Adámek J., Herrlich H., Strecker G. E., Abstract and Concrete Categories: The Joy of Cats, Repr. Theory Appl. Categ., 17, 2006. MR2240597
  2. Adámek J., Milius S., Bowler N., Levy P. B., Coproducts of monads on 𝖲𝖾𝗍 , Proc. of the 2012 27th Annual IEEE Symp. on Logic in Computer Science, Los Alamitos 2012, IEEE, 45–54. MR3050425
  3. Adámek J., Milius S., Moss L. S., 10.1016/j.jlamp.2017.11.003, J. Log. Algebr. Methods Program. 95 (2018), 41–81. MR3759517DOI10.1016/j.jlamp.2017.11.003
  4. Adámek J., Milius S., Moss L. S., Sousa L., Well-pointed coalgebras, Log. Methods Comput. Sci., Selected papers of “Foundations of Software Science and Computation Structures”: FOSSACS 2012 9 (2013), 3:2, 51 pages. MR3091735
  5. Adámek J., Milius S., Sousa L., Wißmann T., On finitary functors, available at arXiv:1902.05788v3 [math.CT] (2019), 31 pages. MR4027294
  6. Adámek J., Rosický J., Locally Presentable and Accessible Categories, London Mathematical Society Lecture Note Series, 189, Cambridge University Press, Cambridge, 1994. MR1294136
  7. Adámek J., Trnková V., Automata and Algebras in Categories, Mathematics and Its Applications (East European Series) 37, Kluwer Academic Publishers Group, Dordrecht, 1990. MR1071169
  8. Barlocco S., Kupke C., Rot J., Coalgebra learning via duality, Foundations of Software Science and Computation Structures, Lecture Notes in Comput. Sci., 11425, Springer, Cham, 2019, pages 62–78. MR3944008
  9. Barr M., 10.1016/0304-3975(93)90076-6, Theoret. Comput. Sci. 114 (1993), no. 2, 299–315. MR1228862DOI10.1016/0304-3975(93)90076-6
  10. Blok A., Interaction, Observation and Denotation, MSc Thesis, Universiteit van Amsterdam, Amsterdam, 2012. 
  11. Carboni A., Lack S., Walters R. F. C., 10.1016/0022-4049(93)90035-R, J. Pure and Appl. Algebra 84 (1993), no. 2, 145–158. MR1201048DOI10.1016/0022-4049(93)90035-R
  12. Gabbay M., Pitts A., A new approach to abstract syntax involving binders, Proc. of the 14th Symp. on Logic in Computer Science, Trento 1999, IEEE Computer Soc., Los Alamitos, 1999, 214–224. MR1943416
  13. Gumm H. P., From T -coalgebras to filter structures and transition systems, Proc. of the 1st Conf. Algebra and Coalgebra in Computer Science, Lecture Notes in Comput. Sci., 3629, Springer, Berlin, 2005, 194–212. MR2205008
  14. Hasuo I., Jacobs B., Sokolova A., 10.2168/LMCS-3(4:11)2007, Log. Methods Comput. Sci. 3 (2007), no. 4, 4:11, 36 pages. MR2357498DOI10.2168/LMCS-3(4:11)2007
  15. Jacobs B., 10.1017/S096012950200378X, Math. Structures Comput. Sci. 12 (2002), no. 6, 875–903. MR1947808DOI10.1017/S096012950200378X
  16. Joyal A., Nielsen M., Winskel G., 10.1006/inco.1996.0057, Inform. and Comput. 127 (1996), no. 2, 164–185. MR1407994DOI10.1006/inco.1996.0057
  17. Kurz A., Petrişan D., Severi P., de Vries F.-J., 10.2168/LMCS-9(4:20)2013, Log. Methods Comput. Sci. 9 (2013), no. 4, 4:20, 52 pages. MR3145058DOI10.2168/LMCS-9(4:20)2013
  18. Lasota S., 10.1016/S0304-3975(01)00023-8, Theoret. Comput. Sci. 280 (2002), no. 1–2, 123–135. MR1905223DOI10.1016/S0304-3975(01)00023-8
  19. Manna Z., Pnueli A., The Temporal Logic of Reactive and Concurrent Systems: Specification, Springer, New York, 1992. MR1156076
  20. Milius S., Schröder L., Wißmann T., 10.1007/s10485-016-9457-8, Appl. Categ. Structures 24 (2016), no. 5, 663–701. MR3546507DOI10.1007/s10485-016-9457-8
  21. Milius S., Wißmann T., Finitary corecursion for the infinitary lambda calculus, Proc. of the 6th Conf. on Algebra and Coalgebra in Computer Science, LIPIcs. Leibniz Int. Proc. Inform., 35, 2015, 336–351. MR3453807
  22. Pitts A. M., Nominal Sets. Names and Symmetry in Computer Science, Cambridge Tracts in Theoretical Computer Science, 57, Cambridge University Press, Cambridge, 2013. MR3113350
  23. Rutten J. J. M. M., 10.1016/S0304-3975(00)00056-6, Theoret. Comput. Sci. 249 (2000), no. 1, 3–80. MR1791953DOI10.1016/S0304-3975(00)00056-6
  24. Schröder L., Kozen D., Milius S., Wißmann T., Nominal automata with name binding, Proc. of the 20th International Conf. on Foundations of Software Science and Computation Structures, available at arXiv:1603.01455v3 [cs.FL] (2017), 43 pages. MR3655539
  25. Trnková V., Some properties of set functors, Comment. Math. Univ. Carolinae 10 (1969), no. 2, 323–352. MR0252474
  26. Trnková V., On a descriptive classification of set functors. I, Comment. Math. Univ. Carolinae 12 (1971), no. 1, 143–174. MR0294445
  27. Wißmann T., Dubut J., Katsumata S.-Y., Hasuo I., Path category for free - Open morphisms from coalgebras with non-deterministic branching, Proc. of the 22nd International Conf. on Foundations of Software Science and Computation Structures, available at arXiv:1811.12294v2 [cs.FL] (2018), 40 pages. MR3944034

NotesEmbed ?

top

You must be logged in to post comments.