A coalgebraic view on reachability. (English) Zbl 07177892

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.


18A99 General theory of categories and functors
18B20 Categories of machines, automata
68Q99 Theory of computing
Full Text: DOI arXiv


[1] Adámek J.; Herrlich H.; Strecker G. E., Abstract and Concrete Categories: The Joy of Cats, Repr. Theory Appl. Categ., 17, 2006 · Zbl 1113.18001
[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 · Zbl 1364.18001
[3] Adámek J.; Milius S.; Moss L. S., Fixed points of functors, J. Log. Algebr. Methods Program. 95 (2018), 41-81
[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 · Zbl 1272.18002
[5] Adámek J.; Milius S.; Sousa L.; Wißmann T., On finitary functors, available at arXiv:1902.05788v3 [math.CT] (2019), 31 pages · Zbl 1470.18006
[6] Adámek J.; Rosický J., Locally Presentable and Accessible Categories, London Mathematical Society Lecture Note Series, 189, Cambridge University Press, Cambridge, 1994 · Zbl 0795.18007
[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 · Zbl 0698.18001
[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 · Zbl 1524.68158
[9] Barr M., Terminal coalgebras in well-founded set theory, Theoret. Comput. Sci. 114 (1993), no. 2, 299-315 · Zbl 0779.18004
[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 · Zbl 0784.18001
[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
[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 · Zbl 1151.18001
[14] Hasuo I.; Jacobs B.; Sokolova A., Generic trace semantics via coinduction, Log. Methods Comput. Sci. 3 (2007), no. 4, 4:11, 36 pages · Zbl 1131.68058
[15] Jacobs B., The temporal logic of coalgebras via Galois algebras, Math. Structures Comput. Sci. 12 (2002), no. 6, 875-903 · Zbl 1030.03017
[16] Joyal A.; Nielsen M.; Winskel G., Bisimulation from open maps, Inform. and Comput. 127 (1996), no. 2, 164-185 · Zbl 0856.68067
[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 · Zbl 1314.68189
[18] Lasota S., Coalgebra morphisms subsume open maps, Theoret. Comput. Sci. 280 (2002), no. 1-2, 123-135 · Zbl 1014.68106
[19] Manna Z.; Pnueli A., The Temporal Logic of Reactive and Concurrent Systems: Specification, Springer, New York, 1992
[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 · Zbl 1375.18029
[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 · Zbl 1366.03172
[22] Pitts A. M., Nominal Sets. Names and Symmetry in Computer Science, Cambridge Tracts in Theoretical Computer Science, 57, Cambridge University Press, Cambridge, 2013 · Zbl 1297.68008
[23] Rutten J. J. M. M., Universal coalgebra: a theory of systems, Theoret. Comput. Sci. 249 (2000), no. 1, 3-80 · Zbl 0951.68038
[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 · Zbl 1486.68097
[25] Trnková V., Some properties of set functors, Comment. Math. Univ. Carolinae 10 (1969), no. 2, 323-352 · Zbl 0183.30401
[26] Trnková V., On a descriptive classification of set functors. I, Comment. Math. Univ. Carolinae 12 (1971), no. 1, 143-174 · Zbl 0232.18004
[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
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.