Realizability of Dynamic MSC Languages
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.
Domaines
Système multi-agents [cs.MA]
Origine : Fichiers produits par l'(les) auteur(s)