Duality for Logics of Transition Systems

Abstract

We present a general framework for logics of transition systems based on Stone duality. Transition systems are modelled as coalgebras for a functor T on a category χ. The propositional logic used to reason about state spaces from χ is modelled by the Stone dual ${\mathcal A}$ of χ (e.g. if χ is Stone spaces then ${\mathcal A}$ is Boolean algebras and the propositional logic is the classical one). In order to obtain a modal logic for transition systems (i.e. for T-coalgebras) we consider the functor L on ${\mathcal A}$ that is dual to T. An adequate modal logic for T-coalgebras is then obtained from the category of L-algebras which is, by construction, dual to the category of T-coalgebras. The logical meaning of the duality is that the logic is sound and complete and expressive (or fully abstract) in the sense that non-bisimilar states are distinguished by some formula.

We apply the framework to Vietoris coalgebras on topological spaces, using the duality between spaces and observation frames, to obtain adequate logics for transition systems on posets, sets, spectral spaces and Stone spaces.