Regular collections of message sequence charts

Henriksen, Jesper G. ; Mukund, Madhavan ; Narayan Kumar, K. ; Thiagarajan, P. S. (2001) Regular collections of message sequence charts In: 25th International Symposium on Mathematical Foundations of Computer Science (MFCS 2000), 28 Aug - 01 Sep 2000, Bratislava, Slovakia.

Full text not available from this repository.

Official URL:

Related URL:


Message Sequence Charts (MSCs) are an attractive visual formalism used during the early stages of design in domains such as telecommunication software. A popular mechanism for generating a collection of MSCs is a Hierarchical Message Sequence Chart (HMSC). However, not all HMSCs describe collections of MSCs that can be “realized” as a finite-state device. Our main goal is to pin down this notion of realizability. We propose an independent notion of regularity for collections of MSCs and explore its basic properties. In particular, we characterize regular collections of MSCs in terms of finite-state distributed automata called bounded message-passing automata, in which a set of sequential processes communicate with each other asynchronously over bounded FIFO channels. We also provide a logical characterization in terms of a natural monadic second-order logic interpreted over MSCs. It turns out that realizable collections of MSCs as specified by HMSCs constitute a strict subclass of the regular collections of MSCs.

Item Type:Conference or Workshop Item (Paper)
Source:Copyright of this article belongs to Springer-Verlag.
Keywords:Message Sequence Chart; Logical Characterization; Regular Subset; Asynchronous Automaton; Regular Collection
ID Code:114217
Deposited On:25 May 2018 04:57
Last Modified:25 May 2018 04:57

Repository Staff Only: item control page