Causal Message Sequence charts

Abstract : Properties of scenario languages (Message Sequence Charts, Live Sequence Charts, UML's sequence diagrams) have been widely studied in the last decade. Scenario languages embed the expressive power of Mazurkiewicz traces, and consequently, several problems such as model checking are undecidable for these languages. Despite their expressive power, most of scenario languages can only model finitely generated behaviors that can be described as the concatenation of patterns from a finite set. However, non-finitely generated behaviors such as sliding windows frequently occur in asynchronous distributed systems. Several extensions of Message Sequence Charts have been proposed to capture non-finitely generated behaviors, but these variants embed the expressive power of automata communicating via unbounded channels (and thus of Turing Machines), making their analysis even more intractable. We propose a new extension of Message Sequence Charts that can model non-finitely generated MSC languages without embedding the expressive power of communicating automata, and study its properties.
Type de document :
Rapport
[Research Report] RR-6301, INRIA. 2007, pp.39
Liste complète des métadonnées

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

https://hal.inria.fr/inria-00173529
Contributeur : Loic Helouet <>
Soumis le : mardi 30 octobre 2007 - 11:15:07
Dernière modification le : jeudi 11 janvier 2018 - 06:20:08
Document(s) archivé(s) le : mardi 21 septembre 2010 - 14:58:39

Fichier

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

Identifiants

  • HAL Id : inria-00173529, version 2

Citation

Thomas Gazagnaire, Shaofa Yang, Loïc Hélouët, Blaise Genest, P.S. Thiagarajan. Causal Message Sequence charts. [Research Report] RR-6301, INRIA. 2007, pp.39. 〈inria-00173529v2〉

Partager

Métriques

Consultations de la notice

176

Téléchargements de fichiers

89