| Title:
|
A coalgebraic view on reachability (English) |
| Author:
|
Wißmann, Thorsten |
| Author:
|
Milius, Stefan |
| Author:
|
Katsumata, Shin-ya |
| Author:
|
Dubut, Jérémy |
| Language:
|
English |
| Journal:
|
Commentationes Mathematicae Universitatis Carolinae |
| ISSN:
|
0010-2628 (print) |
| ISSN:
|
1213-7243 (online) |
| Volume:
|
60 |
| Issue:
|
4 |
| Year:
|
2019 |
| Pages:
|
605-638 |
| Summary lang:
|
English |
| . |
| Category:
|
math |
| . |
| Summary:
|
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. (English) |
| Keyword:
|
coalgebra |
| Keyword:
|
reachability |
| Keyword:
|
Kleisli category |
| MSC:
|
18A99 |
| MSC:
|
18B20 |
| MSC:
|
68Q99 |
| idZBL:
|
Zbl 07177892 |
| idMR:
|
MR4061365 |
| DOI:
|
10.14712/1213-7243.2019.026 |
| . |
| Date available:
|
2020-02-10T16:51:02Z |
| Last updated:
|
2022-01-03 |
| Stable URL:
|
http://hdl.handle.net/10338.dmlcz/147977 |
| . |
| Reference:
|
[1] Adámek J., Herrlich H., Strecker G. E.: Abstract and Concrete Categories: The Joy of Cats.Repr. Theory Appl. Categ., 17, 2006. MR 2240597 |
| Reference:
|
[2] Adámek J., Milius S., Bowler N., Levy P. B.: Coproducts of monads on $\mathsf{Set}$.Proc. of the 2012 27th Annual IEEE Symp. on Logic in Computer Science, Los Alamitos 2012, IEEE, 45–54. MR 3050425 |
| Reference:
|
[3] Adámek J., Milius S., Moss L. S.: Fixed points of functors.J. Log. Algebr. Methods Program. 95 (2018), 41–81. MR 3759517, 10.1016/j.jlamp.2017.11.003 |
| Reference:
|
[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. MR 3091735 |
| Reference:
|
[5] Adámek J., Milius S., Sousa L., Wißmann T.: On finitary functors.available at arXiv:1902.05788v3 [math.CT] (2019), 31 pages. MR 4027294 |
| Reference:
|
[6] Adámek J., Rosický J.: Locally Presentable and Accessible Categories.London Mathematical Society Lecture Note Series, 189, Cambridge University Press, Cambridge, 1994. MR 1294136 |
| Reference:
|
[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. MR 1071169 |
| Reference:
|
[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. MR 3944008 |
| Reference:
|
[9] Barr M.: Terminal coalgebras in well-founded set theory.Theoret. Comput. Sci. 114 (1993), no. 2, 299–315. MR 1228862, 10.1016/0304-3975(93)90076-6 |
| Reference:
|
[10] Blok A.: Interaction, Observation and Denotation.MSc Thesis, Universiteit van Amsterdam, Amsterdam, 2012. |
| Reference:
|
[11] Carboni A., Lack S., Walters R. F. C.: Introduction to extensive and distributive categories.J. Pure and Appl. Algebra 84 (1993), no. 2, 145–158. MR 1201048, 10.1016/0022-4049(93)90035-R |
| Reference:
|
[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. MR 1943416 |
| Reference:
|
[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. MR 2205008 |
| Reference:
|
[14] Hasuo I., Jacobs B., Sokolova A.: Generic trace semantics via coinduction.Log. Methods Comput. Sci. 3 (2007), no. 4, 4:11, 36 pages. MR 2357498, 10.2168/LMCS-3(4:11)2007 |
| Reference:
|
[15] Jacobs B.: The temporal logic of coalgebras via Galois algebras.Math. Structures Comput. Sci. 12 (2002), no. 6, 875–903. MR 1947808, 10.1017/S096012950200378X |
| Reference:
|
[16] Joyal A., Nielsen M., Winskel G.: Bisimulation from open maps.Inform. and Comput. 127 (1996), no. 2, 164–185. MR 1407994, 10.1006/inco.1996.0057 |
| Reference:
|
[17] Kurz A., Petrişan D., Severi P., de Vries F.-J.: Nominal coalgebraic data types with applications to lambda calculus.Log. Methods Comput. Sci. 9 (2013), no. 4, 4:20, 52 pages. MR 3145058, 10.2168/LMCS-9(4:20)2013 |
| Reference:
|
[18] Lasota S.: Coalgebra morphisms subsume open maps.Theoret. Comput. Sci. 280 (2002), no. 1–2, 123–135. MR 1905223, 10.1016/S0304-3975(01)00023-8 |
| Reference:
|
[19] Manna Z., Pnueli A.: The Temporal Logic of Reactive and Concurrent Systems: Specification.Springer, New York, 1992. MR 1156076 |
| Reference:
|
[20] Milius S., Schröder L., Wißmann T.: Regular behaviours with names: On rational fixpoints of endofunctors on nominal sets.Appl. Categ. Structures 24 (2016), no. 5, 663–701. MR 3546507, 10.1007/s10485-016-9457-8 |
| Reference:
|
[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. MR 3453807 |
| Reference:
|
[22] Pitts A. M.: Nominal Sets. Names and Symmetry in Computer Science.Cambridge Tracts in Theoretical Computer Science, 57, Cambridge University Press, Cambridge, 2013. MR 3113350 |
| Reference:
|
[23] Rutten J. J. M. M.: Universal coalgebra: a theory of systems.Theoret. Comput. Sci. 249 (2000), no. 1, 3–80. MR 1791953, 10.1016/S0304-3975(00)00056-6 |
| Reference:
|
[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. MR 3655539 |
| Reference:
|
[25] Trnková V.: Some properties of set functors.Comment. Math. Univ. Carolinae 10 (1969), no. 2, 323–352. MR 0252474 |
| Reference:
|
[26] Trnková V.: On a descriptive classification of set functors. I.Comment. Math. Univ. Carolinae 12 (1971), no. 1, 143–174. MR 0294445 |
| Reference:
|
[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. MR 3944034 |
| . |
