Abstract
Modal and mixed transition systems are specification formalisms that allow the mixing of over- and under-approximation. We discuss three fundamental decision problems for such specifications:
— whether a set of specifications has a common implementation;
— whether an individual specification has an implementation; and
— whether all implementations of an individual specification are implementations of another one.
For each of these decision problems we investigate the worst-case computational complexity for the modal and mixed cases. We show that the first decision problem is EXPTIME-complete for both modal and mixed specifications. We prove that the second decision problem is EXPTIME-complete for mixed specifications (it is known to be trivial for modal ones). The third decision problem is also shown to be EXPTIME-complete for mixed specifications.
— whether a set of specifications has a common implementation;
— whether an individual specification has an implementation; and
— whether all implementations of an individual specification are implementations of another one.
For each of these decision problems we investigate the worst-case computational complexity for the modal and mixed cases. We show that the first decision problem is EXPTIME-complete for both modal and mixed specifications. We prove that the second decision problem is EXPTIME-complete for mixed specifications (it is known to be trivial for modal ones). The third decision problem is also shown to be EXPTIME-complete for mixed specifications.
Originalsprog | Engelsk |
---|---|
Tidsskrift | Mathematical Structures in Computer Science |
Vol/bind | 20 |
Sider (fra-til) | 75-103 |
ISSN | 0960-1295 |
Status | Udgivet - 2010 |
Emneord
- Modal Transition Systems
- Mixed Transition Systems
- Specification Formalisms
- EXPTIME-complete
- Decision Problems