M Mukund, K Narayan Kumar, P S Thiagarajan and Shaofa Yang
Formal Models, Languages and Applications
K.G. Subramanian, K. Rangarajan and Madhavan Mukund (eds.),
World Scientific (2006) 274-288.
We study collections of Message Sequence Charts (MSCs) defined by High-level MSCs (HMSCs) under a new type of concatenation operation called anchored concatenation. We show that there is no decision procedure for determining if the MSC language defined by an HMSC is regular and that it is undecidable if an HMSC admits an implied scenario. Further, the languages defined by locally synchronized HMSCs are precisely the finitely generated regular MSC languages. These results mirror the ones for the asynchronous case. On the other hand, the MSC language obtained by closing under implied scenarios is regular for every HMSC. Secondly, one can effectively determine whether a locally synchronized HMSC admits an implied scenario. Neither of these results hold in the asynchronous case.