Article
Full entry |
PDF
(0.5 MB)
Feedback
PDF
(0.5 MB)
Feedback
Keywords:
coalgebra; reachability; Kleisli category
coalgebra; reachability; Kleisli category
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.
References:
[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
[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
[3] Adámek J., Milius S., Moss L. S.: Fixed points of functors. J. Log. Algebr. Methods Program. 95 (2018), 41–81. DOI 10.1016/j.jlamp.2017.11.003 | MR 3759517
[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
[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
[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
[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
[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
[9] Barr M.: Terminal coalgebras in well-founded set theory. Theoret. Comput. Sci. 114 (1993), no. 2, 299–315. DOI 10.1016/0304-3975(93)90076-6 | MR 1228862
[10] Blok A.: Interaction, Observation and Denotation. MSc Thesis, Universiteit van Amsterdam, Amsterdam, 2012.
[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. DOI 10.1016/0022-4049(93)90035-R | MR 1201048
[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
[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
[14] Hasuo I., Jacobs B., Sokolova A.: Generic trace semantics via coinduction. Log. Methods Comput. Sci. 3 (2007), no. 4, 4:11, 36 pages. DOI 10.2168/LMCS-3(4:11)2007 | MR 2357498
[15] Jacobs B.: The temporal logic of coalgebras via Galois algebras. Math. Structures Comput. Sci. 12 (2002), no. 6, 875–903. DOI 10.1017/S096012950200378X | MR 1947808
[16] Joyal A., Nielsen M., Winskel G.: Bisimulation from open maps. Inform. and Comput. 127 (1996), no. 2, 164–185. DOI 10.1006/inco.1996.0057 | MR 1407994
[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. DOI 10.2168/LMCS-9(4:20)2013 | MR 3145058
[18] Lasota S.: Coalgebra morphisms subsume open maps. Theoret. Comput. Sci. 280 (2002), no. 1–2, 123–135. DOI 10.1016/S0304-3975(01)00023-8 | MR 1905223
[19] Manna Z., Pnueli A.: The Temporal Logic of Reactive and Concurrent Systems: Specification. Springer, New York, 1992. MR 1156076
[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. DOI 10.1007/s10485-016-9457-8 | MR 3546507
[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
[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
[23] Rutten J. J. M. M.: Universal coalgebra: a theory of systems. Theoret. Comput. Sci. 249 (2000), no. 1, 3–80. DOI 10.1016/S0304-3975(00)00056-6 | MR 1791953
[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
[25] Trnková V.: Some properties of set functors. Comment. Math. Univ. Carolinae 10 (1969), no. 2, 323–352. MR 0252474
[26] Trnková V.: On a descriptive classification of set functors. I. Comment. Math. Univ. Carolinae 12 (1971), no. 1, 143–174. MR 0294445
[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
Search
Partner of
