Simulations and Bisimulations For Coalgebraic Modal Logics
Author(s): Gorin D, Schröder L
Title edited volumes: Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
Publishing place: Berlin
Publication year: 2013
Conference Proceedings Title: 5th Conference on Algebra and Coalgebra in Computer Science, CALCO 2013
Pages range: 253-266
Event: 5th International Conference on Algebra and Coalgebra in Computer Science, CALCO 2013
Event location: Warsaw
Start date of the event: 03/09/2013
End date of the event: 06/09/2013
Simulations serve as a proof tool to compare the behaviour of reactive systems. We define a notion of Λ-simulation for coalgebraic modal logics, parametric in the choice of a set Λ of monotone predicate liftings for a functor T. That is, we obtain a generic notion of simulation that can be flexibly instantiated to a large variety of systems and logics, in particular in settings that semantically go beyond the classical relational setup, such as probabilistic, game-based, or neighbourhood-based systems. We show that this notion is adequate in several ways: i) Λ-simulations preserve truth of positive formulas, ii) for Λ a separating set of monotone predicate liftings, the associated notion of Λ-bisimulation corresponds to T-behavioural equivalence (moreover, this correspondence extends to the respective finite-lookahead counterparts), and iii) Λ-bisimulations remain sound when taken up to difunctional closure. In essence, we arrive at a modular notion of equivalence that, when used with a separating set of monotone predicate liftings, coincides with T-behavioural equivalence regardless of whether T preserves weak pullbacks. That is, for finitary set-based coalgebras, Λ-bisimulation works under strictly more general assumptions than T-bisimulation in the sense of Aczel and Mendler. © 2013 Springer-Verlag Berlin Heidelberg.
FAU Authors / FAU Editors How to cite
APA: Gorin, D., & Schröder, L. (2013). Simulations and Bisimulations For Coalgebraic Modal Logics. In 5th Conference on Algebra and Coalgebra in Computer Science, CALCO 2013 (pp. 253-266). Berlin: Springer-verlag.
MLA: Gorin, Daniel, and Lutz Schröder. "Simulations and Bisimulations For Coalgebraic Modal Logics." Proceedings of the 5th International Conference on Algebra and Coalgebra in Computer Science, CALCO 2013, Warsaw Berlin: Springer-verlag, 2013. 253-266.