Paper Info
Title
Pattern Matching and Membership for Hierarchical Message Sequence Charts
Abstract
Several formalisms and tools for software development use hierarchy for system design, for instance statecharts and diagrams in UML. Message sequence charts are an ITU standardized notation for asynchronously communicating processes. The standard Z.120 allows (high-level) MSC-references that correspond to the use of macros. We consider in this paper two basic verification tasks for hierarchical MSCs (nested high-level MSCs, nHMSC), the membership and the pattern matching problem. We show that the membership problem for nHMSCs is PSPACE-complete, even using a weaker semantics for nMSCs than the partial-order semantics. For pattern matching nMSCs M, N we exhibit a polynomial algorithm of time O(|M|2 驴 |N|2. We use here techniques stemming from algorithms on compressed texts.
Year
DOI
Venue
2002
10.1007/s00224-007-9054-1
Theory of Computing Systems \/ Mathematical Systems Theory
Keywords
DocType
Volume
Hierarchical specifications,MSC,Complexity
Conference
42
Issue
ISSN
Citations 
4
1432-4350
13
PageRank 
References 
Authors
0.75
16
2
Name
Order
Citations
PageRank
Blaise Genest130425.09
Anca Muscholl2117974.92