bisimulation-as-a-logical-relation.pdf (1.67 MB)
Bisimulation as a logical relation
journal contribution
posted on 2023-06-10, 06:24 authored by Claudio Hermida, Uday Reddy, Edmund Robinson, Alessio SantamariaWe investigate how various forms of bisimulation can be characterised using the technology of logical relations. The approach taken is that each form of bisimulation corresponds to an algebraic structure derived from a transition system, and the general result is that a relation R between two transition systems on state spaces S and T is a bisimulation if and only if the derived algebraic structures are in the logical relation automatically generated from R. We show that this approach works for the original Park-Milner bisimulation and that it extends to weak bisimulation, and branching and semi-branching bisimulation. The paper concludes with a discussion of probabilistic bisimulation, where the situation is slightly more complex, partly owing to the need to encompass bisimulations that are not just relations.
History
Publication status
- Published
File Version
- Published version
Journal
Mathematical Structures in Computer ScienceISSN
0960-1295Publisher
Cambridge University Press (CUP)External DOI
Issue
4Volume
32Page range
442-471Department affiliated with
- Informatics Publications
Full text available
- Yes
Peer reviewed?
- Yes
Legacy Posted Date
2023-03-02First Open Access (FOA) Date
2023-03-02First Compliant Deposit (FCD) Date
2023-03-02Usage metrics
Categories
No categories selectedKeywords
Licence
Exports
RefWorks
BibTeX
Ref. manager
Endnote
DataCite
NLM
DC