Computing Publications

Publications Home » Modal and Mixed Specifications: K...

Modal and Mixed Specifications: Key Decision Problems and their Complexities

Adam Antonik, Michael Huth, Kim Larsen, Ulrik Nyman, Andrzej Wasowski

Journal Article
Mathematical Structures in Computer Science
Cambridge University Press

Modal and mixed transition systems are specification formalisms that allow 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 a sole specification has an implementation, and whether all implementations of one specification are implementations of another one. For each of these decision problems we investigate the worst-case computational complexity for the modal and mixed case. We show that the first decision problem is EXPTIME-complete for modal as well as for mixed specifications. We prove that the second decision problem is EXPTIME-complete for mixed specifications (while it is known to be trivial for modal ones). The third decision problem is furthermore demonstrated to be EXPTIME-complete for mixed specifications.

PDF of full publication (408 kilobytes)
(need help viewing PDF files?)
BibTEX file for the publication
Copyright notice

This is a preliminary version of a paper that has been accepted in the above journal.

Conditions for downloading publications from this site. built & maintained by Ashok Argent-Katwala.