[The web pages finally moved to a new layout and automated generation of HTML code. Please report any problems to tr-admin@informatik.rwth-aachen.de!] The following technical report is available from http://aib.informatik.rwth-aachen.de/: Benedikt Bollig, Martin Leucker, Thomas Noll Generalised Regular MSC Languages 2002-03 Abstract: 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 MSCs with message overtaking and is thus applicable to a broad range of channel types like mixtures of stacks and FIFOs. Regards, Volker Stolz -- Wonderful \hbox (0.80312pt too nice) in paragraph at lines 16--18 Volker Stolz * stolz@i2.informatik.rwth-aachen.de Please use PGP or S/MIME for correspondence!