Please use this identifier to cite or link to this item: https://doi.org/10.1016/j.ic.2004.08.004
Title: A theory of regular MSC languages
Authors: Henriksen, J.G.
Mukund, M.
Kumar, K.N.
Sohoni, M.
Thiagarajan, P.S. 
Keywords: Message sequence charts
Message-passing systems
Monadic second-order logic
Realizability
Regularity
Synthesis
Issue Date: 2005
Source: Henriksen, J.G., Mukund, M., Kumar, K.N., Sohoni, M., Thiagarajan, P.S. (2005). A theory of regular MSC languages. Information and Computation 202 (1) : 1-38. ScholarBank@NUS Repository. https://doi.org/10.1016/j.ic.2004.08.004
Abstract: 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. © 2005 Elsevier Inc. All rights reserved.
Source Title: Information and Computation
URI: http://scholarbank.nus.edu.sg/handle/10635/39782
ISSN: 08905401
DOI: 10.1016/j.ic.2004.08.004
Appears in Collections:Staff Publications

Show full item record
Files in This Item:
There are no files associated with this item.

SCOPUSTM   
Citations

63
checked on Dec 13, 2017

WEB OF SCIENCETM
Citations

46
checked on Dec 13, 2017

Page view(s)

61
checked on Dec 9, 2017

Google ScholarTM

Check

Altmetric


Items in DSpace are protected by copyright, with all rights reserved, unless otherwise indicated.