Computing Publications

Publications Home » Reverse Bisimulations on Stable C...

Reverse Bisimulations on Stable Configuration Structures

Iain Phillips, Irek Ulidowski

Conference or Workshop Paper
Structural Operational Semantics 2009
Electronic Proceedings in Theoretical Computer Science

The relationships between various equivalences on configuration structures, including interleaving bisimulation (IB), step bisimulation (SB) and hereditary history-preserving (HH) bisimulation, have been investigated by van Glabbeek and Goltz (and later Fecher). Since HH bisimulation may be characterised by the use of reverse as well as forward transitions, it is of interest to investigate forms of IB and SB where both forward and reverse transitions are allowed. Bednarczyk asked whether SB with reverse steps (which we shall call reverse SB) is as strong as HH bisimulation. This question remains open. We give various characterisations of reverse SB, showing that forward steps do not add extra power. We strengthen Bednarczyk's result that, in the absence of auto-concurrency, reverse IB is as strong as HH bisimulation, by showing that we need only exclude auto-concurrent events at the same depth in the configuration.

BibTEX file for the publication built & maintained by Ashok Argent-Katwala.