情報科学セミナー

タイトル：Reverse Bisimulations on Stable Event Structures

概要：

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 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.

主催：名古屋大学情報科学研究科

連絡先：情報システム学　結縁 yuen-at-is.nagoya-u.ac.jp (内線３６４９)