Record Details

A theory of regular MSC languages

DSpace at IIT Bombay

View Archive Info
 
 
Field Value
 
Title A theory of regular MSC languages
 
Creator HENRIKSEN, JESPER G
MUKUND, MADHAVAN
NARAYAN KUMAR, K
SOHONI, MILIND
THIAGARAJAN, PS
 
Subject automata theory
computer software
message sequence chart
telecommunication
 
Description 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. It is fruitful to have mechanisms for specifying and reasoning about collections of MSCs so that errors can be detected even at the requirements level. We propose, accordingly, a notion of regularity for collections of MSCs and explore its basic properties. In particular, we provide an automata-theoretic characterization of regular MSC languages in terms of finite-state distributed automata called bounded message-passing automata. These automata consist of a set of sequential processes that communicate with each other by sending and receiving messages over bounded FIFO channels. We also provide a logical characterization in terms of a natural monadic second-order logic interpreted over MSCs. A commonly used technique to generate a collection of MSCs is to use a hierarchical message sequence chart (HMSC). We show that the class of languages arising from the so-called bounded HMSCs constitute a proper subclass of the class of regular MSC languages. In fact, we characterize the bounded HMSC languages as the subclass of regular MSC languages that are finitely generated.
 
Publisher Elsevier
 
Date 2009-09-19T07:10:11Z
2011-11-25T15:28:09Z
2011-12-26T13:04:51Z
2011-12-27T05:50:52Z
2009-09-19T07:10:11Z
2011-11-25T15:28:09Z
2011-12-26T13:04:51Z
2011-12-27T05:50:52Z
2005
 
Type Article
 
Identifier Information and Computation 202(1), 1-38
0890-5401
10.1016/j.ic.2004.08.004
http://hdl.handle.net/10054/1643
http://dspace.library.iitb.ac.in/xmlui/handle/10054/1643
 
Language en