zbMATH — the first resource for mathematics

Building bridges between sets of partial orders. (English) Zbl 1451.68193
Dediu, Adrian-Horia (ed.) et al., Language and automata theory and applications. 9th international conference, LATA 2015, Nice, France, March 2–6, 2015. Proceedings. Berlin: Springer. Lect. Notes Comput. Sci. 8977, 145-160 (2015).
Summary: Partial orders are a fundamental mathematical structure capable of representing true concurrency and causality on a set of atomic events. In this paper we study two mathematical formalisms capable of the compressed representation of sets of partial orders: labeled event structures (LESs) and conditional partial order graphs (CPOGs). We demonstrate their advantages and disadvantages and propose efficient algorithms for transforming a set of partial orders from a given compressed representation in one formalism into an equivalent representation in another formalism without the explicit enumeration of each scenario. These transformations reveal the superior expressive power of CPOGs as well as the cost of this expressive power. The proposed algorithms make use of an intermediate mathematical formalism, called conditional labeled event structures (CLESs), which combines the advantages of LESs and CPOGs. All three formalisms are compared on a number of benchmarks.
For the entire collection see [Zbl 1331.68009].

68Q85 Models and methods for concurrent and distributed computing (process algebras, bisimulation, transition nets, etc.)
06A06 Partial orders, general
Full Text: DOI