A coalgebraic view on reachability

Authors :: Shin-ya Katsumata
Stefan Milius
Thorsten Wißmann
Jérémy Dubut
Friedrich-Alexander Universität Erlangen-Nürnberg (FAU)
National Institute of Informatics (NII)
Japanese French Laboratory for Informatics (JFLI)
National Institute of Informatics (NII)-The University of Tokyo (UTokyo)-Sorbonne Université (SU)-Centre National de la Recherche Scientifique (CNRS)
Source :: Commentationes Mathematicae Universitatis Carolinae, Commentationes Mathematicae Universitatis Carolinae, 2019, 60 (4), pp.605-638. ⟨10.14712/1213-7243.2019.026⟩
Publication Year :: 2020
Publisher :: Charles University in Prague, Karolinum Press, 2020.
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.