Regular MSC Languages

Benedikt Bollig, Martin Leucker, Thomas Noll

In this paper we establish the concept of regularity for languages
consisting of Message Sequence Charts (MSCs) under the aspect of
realisability. To this aim we characterise their behaviour by string
languages, and we give a natural definition of regularity in terms
of appropriate right congruences. Moreover, we present a class of
accepting automata, and, using this characterisation, establish several
decidability and closure properties of MSC languages. We also provide
a logical characterisation in terms of a monadic second order logic
interpreted over MSCs. In contrast to existing work on regular MSC
languages, our approach is not tailored to a fixed communication medium
(as a FIFO channel, for example) but is applicable to a broad range of
channel types like mixtures of stacks and FIFOs.