zbMATH — the first resource for mathematics

Generalised regular MSC languages. (English) Zbl 1077.68666
Nielsen, Mogens (ed.) et al., Foundations of software science and computation structures. 5th international conference, FOSSACS 2002, held as part of the joint European conferences on theory and practice of software, ETAPS 2002, Grenoble, France, April 8–12, 2002. Proceedings. Berlin: Springer (ISBN 3-540-43366-X). Lect. Notes Comput. Sci. 2303, 52-66 (2002).
Summary: We establish the concept of regularity for languages consisting of Message Sequence Charts (MSCs). To this aim, we formalise their behaviour by string languages and give a natural definition of regularity in terms of an appropriate Nerode right congruence. Moreover, we present a class of accepting automata and establish several decidability and closure properties of MSC languages. We also provide a logical characterisation by a monadic second-order logic interpreted over MSCs. In contrast to existing work on regular MSC languages, our approach is neither restricted to a certain class of MSCs nor tailored to a fixed communication medium (such as a FIFO channel). It explicitly allows for MSCs with message overtaking and is thus applicable to a broad range of channel types like mixtures of stacks and FIFOs.
For the entire collection see [Zbl 0989.00051].

68Q45 Formal languages and automata
03D05 Automata and formal grammars in connection with logical questions
Full Text: Link