Building Bridges Between Sets of Partial Orders - Inria - Institut national de recherche en sciences et technologies du numérique Accéder directement au contenu
Rapport (Rapport De Recherche) Année : 2014

Building Bridges Between Sets of Partial Orders

Résumé

Partial order is a fundamental mathematical structure capable of representing true concurrency and causality on a set of atomic events. In many applications it is essential to consider multiple partial orders, each representing a particular behavioral scenario or an operating mode of a modeled system. With the exploding growth of the complexity of systems that software and hardware engineers design today, it is no longer feasible to represent each partial order of a large system explicitly, therefore compressed representations of sets of partial orders become essential for improving the scalability of design automation tools. 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 dis- advantages and propose efficient algorithms for transformation of 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, which we call Conditional Labeled Event Structures (CLESs), that combines the advantages of LESs and CPOGs. Finally, all three formalisms are compared on a number of benchmarks.
Fichier principal
Vignette du fichier
Building Bridges.pdf (303.01 Ko) Télécharger le fichier
Origine : Fichiers produits par l'(les) auteur(s)

Dates et versions

hal-01060449 , version 1 (03-09-2014)
hal-01060449 , version 2 (07-10-2014)
hal-01060449 , version 3 (16-10-2014)
hal-01060449 , version 4 (30-10-2014)
hal-01060449 , version 5 (08-12-2014)

Identifiants

  • HAL Id : hal-01060449 , version 4

Citer

Hernan Ponce de Leon, Andrey Mokhov. Building Bridges Between Sets of Partial Orders. [Research Report] INRIA and LSV. 2014. ⟨hal-01060449v4⟩
219 Consultations
250 Téléchargements

Partager

Gmail Facebook X LinkedIn More