Realizability of Dynamic MSC Languages

Benedikt Bollig 1 Loic Helouet 2
2 DISTRIBCOM - Distributed and Iterative Algorithms for the Management of Telecommunications Systems
IRISA - Institut de Recherche en Informatique et Systèmes Aléatoires, Inria Rennes – Bretagne Atlantique
Abstract : We introduce dynamic communicating automata (DCA), an extension of communicating finite-state machines that allows for dynamic creation of processes. Their behavior can be described as sets of message sequence charts (MSCs). We consider the realizability problem for DCA: given a dynamic MSC grammar (a high-level MSC specification), is there a DCA defining the same set of MSCs? We show that this problem is EXPTIME-complete. Moreover, we identify a class of realizable grammars that can be implemented by finite DCA.
Type de document :
Communication dans un congrès
International Computer Science Symposium in Russia, Jun 2010, Kazan, Russia. 2010
Liste complète des métadonnées

https://hal.inria.fr/inria-00589714
Contributeur : Loic Helouet <>
Soumis le : samedi 30 avril 2011 - 23:01:20
Dernière modification le : mercredi 11 avril 2018 - 01:54:16
Document(s) archivé(s) le : dimanche 31 juillet 2011 - 02:34:11

Fichier

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

Identifiants

  • HAL Id : inria-00589714, version 1

Citation

Benedikt Bollig, Loic Helouet. Realizability of Dynamic MSC Languages. International Computer Science Symposium in Russia, Jun 2010, Kazan, Russia. 2010. 〈inria-00589714〉

Partager

Métriques

Consultations de la notice

209

Téléchargements de fichiers

90