IFIP Logo
Sign in for Members and Observers

IFIP WG1.3 Foundations of System Specification


Talk "Reachability for Coalgebras"

by Stefan Milius

Sat, 06 April 2019 at 03:00 pm in Prague, Czech Republic

Joint work with: Thorsten Wißmann, Jeremy Dubut, Shin-ya Katsumata

Abstract: Coalgebras for an endofunctor provide a category-theoretic framework for modeling a wide range of state-based systems of various types. This talk shows how the notion of reachability can be formulated for coalgebras. Moreover, for an endofunctor preserving all intersections on a complete and well-powered category, we provide an iterative construction of the reachable part of a given pointed coalgebra. The construction is inspired by and resembles the standard breadth-first search procedure to compute the reachable part of a graph. In fact, the reachable part occurs via the least fixed point for a coalgebraic 'previous time' operator on the subobjects of the carrier of the given coalgebra. If, in addition, F preserves inverse images, the reachable part is a coreflection into the full subcategory given by reachable coalgebras for F.

Paper