Building Bridges Between Sets of Partial Orders

Hernan Ponce de Leon 1, 2 Andrey Mokhov 3
1 MEXICO - Modeling and Exploitation of Interaction and Concurrency
LSV - Laboratoire Spécification et Vérification [Cachan], ENS Cachan - École normale supérieure - Cachan, Inria Saclay - Ile de France, CNRS - Centre National de la Recherche Scientifique : UMR8643
Abstract : Partial orders are a fundamental mathematical structure capable of rep- resenting 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 formal- ism 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.
Type de document :
Communication dans un congrès
International Conference on Language and Automata Theory and Applications, Mar 2015, Nice, France. 2015
Liste complète des métadonnées

Littérature citée [11 références]  Voir  Masquer  Télécharger

https://hal.inria.fr/hal-01060449
Contributeur : Hernan Ponce de Leon <>
Soumis le : lundi 8 décembre 2014 - 18:04:07
Dernière modification le : jeudi 11 janvier 2018 - 06:23:37
Document(s) archivé(s) le : lundi 9 mars 2015 - 12:26:20

Fichier

lata2015.pdf
Fichiers produits par l'(les) auteur(s)

Identifiants

  • HAL Id : hal-01060449, version 5

Citation

Hernan Ponce de Leon, Andrey Mokhov. Building Bridges Between Sets of Partial Orders. International Conference on Language and Automata Theory and Applications, Mar 2015, Nice, France. 2015. 〈hal-01060449v5〉

Partager

Métriques

Consultations de la notice

154

Téléchargements de fichiers

107