Welcome!
To use the personalized features of this site, please log in or register.
If you have forgotten your username or password, we can help.
|
 |
Message Sequence Graphs and Decision Problems on Mazurkiewicz Traces
| |
|
Message Sequence Graphs and Decision Problems on Mazurkiewicz Traces
Anca Muscholl5 and Doron Peled6, 7
| (5) |
Institut für Informatik, Universität Stuttgart, Breitwiesenstr. 20-22, 70565 Stuttgart, Germany |
| (6) |
Department of Computer Science Technion, Israel Institute of Technology, 32000 Haifa, Israel |
| (7) |
Bell Laboratories, 600 Mountain Ave., Murray Hill, NJ 07974, USA |
Abstract
Message sequence charts (MSC) are a graphical specification language widely used for designing communication protocols. Our
starting point are two decision problems concerning the correctness and the consistency of a design based by MSC graphs. Both
problems are shown to be undecidable, in general. Using a natural connectivity assumption from Mazurkiewicz trace theory we
show both problems to be EXPSPACE-complete for locally synchronized graphs. The results are based on new complexity results
for star-connected rational trace languages.
Keywords Message sequence graphs - Mazurkiewicz semi-traces - automata theory - universality problem
The results were partly supported by Bell Labs and DIMACS.
Fulltext Preview (Small, Large)
 References secured to subscribers.
|
|
|
|
|
|