Back to Search
Start Over
Realizability of high-level message sequence charts: closing the gaps
- Source :
-
Theoretical Computer Science . Dec2003, Vol. 309 Issue 1-3, p529. 26p. - Publication Year :
- 2003
-
Abstract
- We study the notion of safe realizability for high-level message sequence charts (HMSCs) (Proceedings of the 28th International Colloquium on Automata, Languages and Programming (ICALP 2001), Crete (Greece), Lecture Notes in Computer Science, Vol. 2076, Springer, Berlin, 2001, pp. 797–808). We show that safe realizability is EXPSPACE-complete for bounded HMSCs but undecidable for the class of all HMSCs. This solves two open problems from Alur et al. Moreover we prove that safe realizability is also EXPSPACE-complete for the larger class of globally-cooperative HMSCs. [Copyright &y& Elsevier]
- Subjects :
- *MACHINE theory
*COMPUTATIONAL complexity
Subjects
Details
- Language :
- English
- ISSN :
- 03043975
- Volume :
- 309
- Issue :
- 1-3
- Database :
- Academic Search Index
- Journal :
- Theoretical Computer Science
- Publication Type :
- Academic Journal
- Accession number :
- 11402171
- Full Text :
- https://doi.org/10.1016/j.tcs.2003.08.002