On message sequence graphs and finitely generated regular MSC languages

Henriksen, Jesper G. ; Mukund, Madhavan ; Narayan Kumar, K. ; Thiagarajan, P. S. (2002) On message sequence graphs and finitely generated regular MSC languages In: 27th International Colloquium on Automata, Languages, and Programming (ICALP 2000), 09-15 Jul 2000, Geneva, Switzerland.

Full text not available from this repository.

Official URL: https://link.springer.com/chapter/10.1007%2F3-540-...

Related URL: http://dx.doi.org/10.1007/3-540-45022-X_57


Message Sequence Charts (MSCs) are an attractive visual formalism widely used to capture system requirements during the early design stages in domains such as telecommunication software. A standard method to describe multiple communication scenarios is to use message sequence graphs (MSGs). A message sequence graph allows the protocol designer to write a finite specification which combines MSCs using basic operations such as branching choice, composition and iteration. The MSC languages described by MSGs are not necessarily regular in the sense of [HM+99]. We characterize here the class of regular MSC languages that are MSG-definable in terms of a notion called finitely generated MSC languages. We show that a regular MSC language is MSG-definable if and only if it is finitely generated. In fact we show that the subclass of “bounded” MSGs defined in [AY99] exactly capture the class of finitely generated regular MSC languages.

Item Type:Conference or Workshop Item (Paper)
Source:Copyright of this article belongs to Springer-Verlag.
Keywords:Regular Language; Labelling Function; Early Design Stage; Message Sequence Chart; Single Connected Component
ID Code:114219
Deposited On:25 May 2018 04:53
Last Modified:25 May 2018 04:53

Repository Staff Only: item control page