CONCUR 2004 START ConferenceManager    

The pros and cons of netcharts

Nicolas BAUDRU & Remi MORIN

Presented at Fifteenth International Conference on Concurrency Theory (CONCUR 2004), London, England, 31 August - 3 September, 2004


Netcharts have been introduced recently by Mukund et al. at CONCUR'03. This new appealing approach to the specification of collections of message sequence chart scenarios (MSCs) benefits from a graphical description, a formal semantics, and an appropriate expressive power. As opposed to high-level MSCs, any regular MSC language is the language of some netchart. Motivated by two open problems raised in [Mukund03], we establish in this paper that the questions (i) whether a given netchart describes a regular MSC language (ii) whether a given high-level MSC describes some netchart language (iii) whether a given netchart is equivalent to some high-level MSC are undecidable. These facts are closely related to our main positive result: We prove that netchart languages are exactly the MSC languages that are implementable by FIFO message passing automata (MPAs) up to some refinement of message contents. However, we observe that this nice relationship fails with non-FIFO MPAs. Finally, we show how to check whether a netchart is FIFO ---that is, whether its executions correspond to all firing sequences of its low-level Petri net. Moreover, for these FIFO netcharts, we show that regularity becomes decidable.

START Conference Manager (V2.47.4)