Return to search

Decidability and coincidence of equivalences for concurrency

The main aim of this thesis is to gain insights into the decidability problem for hhpb, and to analyse when it coincides with hpb; less technically, we might say, to analyse the power of the interplay between concurrency, causality, and conflict. We first examine the backtracking condition, and see that it has to dimensions: the number of transitions over which one may backtrack, and the number of backtracking moves. These dimensions translate into two hierarchies of bisimilarities; we find that both of them are strict, and that each of their levels is decidable. Our second approach is to analyse which behavioural properties of concurrent systems are crucial to the increased power of hhpb. After establishing a minimum of behavioural situations necessary to keep hpb and hhpb distinct, we study two aspects of the interplay of causality, concurrency, and conflict: a kind of synchronization, and the notion of confusion. With the help of a composition and decomposition result we prove that synchronization is essential for non-coincidence (for finite-state systems). However, we show that this is not so for confusion, which disproves the long-standing conjecture that hpb and hhpb coincide for confusion-free systems. We continue by studying two structural system classes with promising behavioural properties. First we consider basic parallel processes (BPP), with a suitable partial order semantics. These systems are infinite-state, but they restrict synchronization. Using the tableau technique, we prove the decidability and coincidence of hpb and hhpb for ‘full standard form’ BPP. The two bisimilarities do not coincide for the complete BPP class, but we separately achieve decidability of both (a known result for hpb, but not for hhpb). The second structural class is (safe) free-choice systems, an important class in Petri net theory. These systems have a controlled interplay of concurrency and conflict, and thereby exclude confusion. Having shown that hpb and hhpb do not coincide here, we identify another interesting candidate: live and strict free-choice systems. For this class, we prove that an auxiliary bisimilarity coincides with a ‘half’-hereditary version. As a consequence we put forward the coincidence of hpb and hhpb for live buffered and strict free choice systems: the only known positive result for a class with a reasonable amount of interplay between concurrency, causality and conflict.

Identiferoai:union.ndltd.org:bl.uk/oai:ethos.bl.uk:651148
Date January 2004
CreatorsFröschle, Sibylle
PublisherUniversity of Edinburgh
Source SetsEthos UK
Detected LanguageEnglish
TypeElectronic Thesis or Dissertation
Sourcehttp://hdl.handle.net/1842/24593

Page generated in 0.0022 seconds