Output details

A hierarchy of reverse bisimulations on stable configuration structures

<10>Bednarczyk introduced hereditary history-preserving bisimulation on true-concurrency structures in 1991. He left an open question: can it be characterised by concurrent moves (steps) in forwards and reverse directions? We answer this in the negative. We also provide the first improvement on his result that his equivalence can be captured by forward and reverse moves (with no auto-concurrency). We study in detail the hierarchy of reverse equivalences. Our work marks a step towards solving the still open question of the appropriate semantic equivalence for reversible computation (e.g. rollbacks in database transactions, fault-tolerant systems, quantum computation, etc.).