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
Access Full Article
topAbstract
topHow to cite
topWiß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- Adámek J., Herrlich H., Strecker G. E., Abstract and Concrete Categories: The Joy of Cats, Repr. Theory Appl. Categ., 17, 2006. MR2240597
- 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
- 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
- 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
- Adámek J., Milius S., Sousa L., Wißmann T., On finitary functors, available at arXiv:1902.05788v3 [math.CT] (2019), 31 pages. MR4027294
- Adámek J., Rosický J., Locally Presentable and Accessible Categories, London Mathematical Society Lecture Note Series, 189, Cambridge University Press, Cambridge, 1994. MR1294136
- 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
- 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
- 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
- Blok A., Interaction, Observation and Denotation, MSc Thesis, Universiteit van Amsterdam, Amsterdam, 2012.
- 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
- 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
- Gumm H. P., From -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
- 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
- Jacobs B., 10.1017/S096012950200378X, Math. Structures Comput. Sci. 12 (2002), no. 6, 875–903. MR1947808DOI10.1017/S096012950200378X
- 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
- 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
- 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
- Manna Z., Pnueli A., The Temporal Logic of Reactive and Concurrent Systems: Specification, Springer, New York, 1992. MR1156076
- 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
- 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
- Pitts A. M., Nominal Sets. Names and Symmetry in Computer Science, Cambridge Tracts in Theoretical Computer Science, 57, Cambridge University Press, Cambridge, 2013. MR3113350
- 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
- 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
- Trnková V., Some properties of set functors, Comment. Math. Univ. Carolinae 10 (1969), no. 2, 323–352. MR0252474
- Trnková V., On a descriptive classification of set functors. I, Comment. Math. Univ. Carolinae 12 (1971), no. 1, 143–174. MR0294445
- 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 ?
topTo embed these notes on your page include the following JavaScript code on your page where you want the notes to appear.