Vietoris Bisimulations
- 22 December 2008
- journal article
- research article
- Published by Oxford University Press (OUP) in Journal of Logic and Computation
- Vol. 20 (5) , 1017-1040
Abstract
Building on the fact that descriptive frames are coalgebras for the Vietoris functor on the category of Stone spaces, we introduce and study the concept of a Vietoris bisimulation between two descriptive modal models, together with the associated notion of bisimilarity. We prove that our notion of bisimilarity, which is defined in terms of relation lifting, coincides with Kripke bisimilarity (with respect to the underlying Kripke models), with behavioural equivalence, and with modal equivalence, but not with Aczel–Mendler bisimilarity. As a corollary, we obtain that the Vietoris functor does not preserve weak pullbacks. Comparing Vietoris bisimulations between descriptive models to Kripke bisimulations on the underlying Kripke models, we prove that the closure of such a Kripke bisimulation is a Vietoris bisimulation. As a corollary, we show that the collection of Vietoris bisimulations between two descriptive models forms a complete lattice. Finally, we provide a game-theoretic characterization of Vietoris bisimilarity.Keywords
This publication has 7 references indexed in Scilit:
- Coalgebraic modal logic of finite rankMathematical Structures in Computer Science, 2005
- Stone coalgebrasTheoretical Computer Science, 2004
- Bisimulation for Labelled Markov ProcessesInformation and Computation, 2002
- Universal coalgebra: a theory of systemsTheoretical Computer Science, 2000
- Structural Induction and Coinduction in a Fibrational SettingInformation and Computation, 1998
- Algebraic laws for nondeterminism and concurrencyJournal of the ACM, 1985
- Semantic analysis of tense logicsThe Journal of Symbolic Logic, 1972