(sigemb-info 488) Talk by Irek Ulidowski at RIMS, Kyoto U, Thu 10 Dec 2009

[Ichiro Hasuo <ichiro@xxxxxxxxxxxxxxxxxxxx>]

Dear colleagues,

On Dec 10 at 11.00am Irek Ulidowski from Leicester, UK
is visiting RIMS, Kyoto University and giving a talk.
No registration necessary. See you there!

Best regards,
Ichiro Hasuo
---
RIMS-CS website
http://www.kurims.kyoto-u.ac.jp/~cs/


=====
Irek Ulidowski (Univ. Leicester) http://www.cs.le.ac.uk/people/iu3/
Reverse Bisimulations on Stable Event Structures

11.00 - 12.00, Thursday 10 December 2009
Room 203P, Faculty of Science Bldg. No. 6  理学部6号館 203P号室
(see http://www.kyoto-u.ac.jp/en/access/campus/north.htm
http://www.kyoto-u.ac.jp/ja/access/campus/map6r_n.htm for direction)

Abstract:
 The relationships between various equivalences on stable event
structures, including interleaving bisimulation (IB), step
bisimulation (SB) and hereditary history-preserving (HH) bisimulation,
have been investigated by van Glabbeek and Goltz. 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 (and other more complex bisimulations) where both forward and
reverse transitions are allowed.

Bednarczyk asked whether SB with reverse steps (which we shall call
reverse SB and write RSB) is as strong as HH bisimulation. This
question remained open until very recently. We give various
characterisations of RSB, 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. Finally, we present a lattice of many
forms of bisimulations where both forward and reverse observations are
allowed. The lattice has HH at the top and IB at the bottom, and we
briefly explain the relationships between other forms of
bisimulations.