Local testing of message sequence charts is difficult

Bhateja, Puneet ; Gastin, Paul ; Mukund, Madhavan ; Narayan Kumar, K. (2007) Local testing of message sequence charts is difficult In: 16th International Symposium on Fundamentals of Computation Theory, FCT 2007, 27-30 Aug 2007, Budapest, Hungary.

Full text not available from this repository.

Official URL: https://link.springer.com/chapter/10.1007/978-3-54...

Related URL: http://dx.doi.org/10.1007/978-3-540-74240-1_8


Message sequence charts are an attractive formalism for specifying communicating systems. One way to test such a system is to substitute a component by a test process and observe its interaction with the rest of the system. Unfortunately, local observations can combine in unexpected ways to define implied scenarios not present in the original specification. Checking whether a scenario specification is closed with respect to implied scenarios is known to be undecidable when observations are made one process at a time. We show that even if we strengthen the observer to be able to observe multiple processes simultaneously, the problem remains undecidable. In fact, undecidability continues to hold even without message labels, provided we observe two or more processes simultaneously. On the other hand, without message labels, if we observe one process at a time, checking for implied scenarios is decidable.

Item Type:Conference or Workshop Item (Paper)
Source:Copyright of this article belongs to Springer-Verlag.
Keywords:Test Process; Local Test; Regular Language; Terminal Vertex; Message Sequence Chart
ID Code:114146
Deposited On:25 May 2018 04:55
Last Modified:25 May 2018 04:55

Repository Staff Only: item control page