Abstract
We consider decision problems for modal and mixed transition systems used as specifications: the common implementation problem (whether a set of specifications has a common implementation), the consistency problem (whether a single specification has an implementation), and the thorough refinement problem (whether all implementations of one specification are also implementations of another one). Common implementation and thorough refinement are shown to be PSPACE-hard for modal, and so also for mixed, specifications. Consistency is PSPACE-hard
for mixed, while trivial for modal specifications. We also supply upper bounds suggesting strong links between these problems.
for mixed, while trivial for modal specifications. We also supply upper bounds suggesting strong links between these problems.
Originalsprog | Engelsk |
---|---|
Bogserie | Lecture Notes in Computer Science |
Sider (fra-til) | 112-126 |
ISSN | 0302-9743 |
DOI | |
Status | Udgivet - 2008 |
Begivenhed | 11th International Conference, FOSSACS 2008:Held as Part of the Joint European Conferences on Theory and Practice of Software, ETAPS 2008, Budapest, Hungary, March 29 - April 6, 2008. - Budapest, Ungarn Varighed: 29 mar. 2008 → 6 apr. 2008 Konferencens nummer: 11 |
Konference
Konference | 11th International Conference, FOSSACS 2008:Held as Part of the Joint European Conferences on Theory and Practice of Software, ETAPS 2008, Budapest, Hungary, March 29 - April 6, 2008. |
---|---|
Nummer | 11 |
Land/Område | Ungarn |
By | Budapest |
Periode | 29/03/2008 → 06/04/2008 |
Emneord
- Modal Specifications
- Mixed Transition Systems
- Common Implementation
- Thorough Refinement
- Consistency Problem