Concurrency is concerned with systems of multiple computing agents that interact with each other. Bisimilarity is one of the main representatives of these. Concurrent Constrain Programming (ccp) is a formalism that combines the traditional and algebraic view of process calculi with a declarative one based upon first-order logic. The standard definition of bisimilarity is not completely satisfactory for ccp since it yields an equivalence that is too fine grained. By building upon recent foundational investigations, we introduce a labeled transition semantics and a novel notion of bisimilarity that is fully abstract w.r.t. the observational equivalence in ccp. When the state space of a system is finite, the ordinary notion of bisimilarity can be computed via the partition refinement algorithm, but unfortunately, this algorithm does not work for ccp bisimilarity. Hence, we provide an algorithm that allows us to verify strong bisimilarity for ccp, modifying the algorithm by using a pre-refinement and a partition function based on the irredundant bisimilarity. Weak bisimilarity is a central behavioral equivalence in process calculi and it is obtained from the strong case by taking into account only the actions that are observable in the system. Typically the standard partition refinement can also be used for deciding weak bisimilarity simply by using Milner's reduction from weak to strong; a technique referred to as saturation. We demonstrate that the above-mentioned saturation technique does not work for ccp. We give a reduction that allows us to use the ccp partition refinement algorithm for deciding this equivalence.
| Identifer | oai:union.ndltd.org:CCSD/oai:pastel.archives-ouvertes.fr:pastel-00755356 |
| Date | 17 October 2012 |
| Creators | Please Erase This Article, Thank You, Please Erase This Article, Thank You |
| Publisher | Ecole Polytechnique X |
| Source Sets | CCSD theses-EN-ligne, France |
| Language | English |
| Detected Language | English |
| Type | PhD thesis |
Page generated in 0.0016 seconds