inria-00589714, version 1
Realizability of Dynamic MSC Languages
Benedikt Bollig
1Loic Helouet a, 2
International Computer Science Symposium in Russia (2010)
Résumé : 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.
- a – INRIA
- 1 : Laboratoire Spécification et Vérification [Cachan] (LSV)
- CNRS : UMR8643 – INRIA – École normale supérieure de Cachan - ENS Cachan
- 2 : DISTRIBCOM (INRIA - IRISA)
- CNRS : UMR6074 – INRIA – École normale supérieure de Cachan - ENS Cachan – INSA Rennes – Université de Rennes 1
- Domaine : Informatique/Système multi-agents
- Mots-clés : Sceanrios – dynamic models – implementation
- inria-00589714, version 1
- http://hal.inria.fr/inria-00589714
- oai:hal.inria.fr:inria-00589714
- Contributeur : Loic Helouet
- Soumis le : Samedi 30 Avril 2011, 23:01:20
- Dernière modification le : Mardi 3 Mai 2011, 09:00:51
Documents associés
Exporter