Computing Publications

Publications Home » EXPTIME-complete Decision Problem...

EXPTIME-complete Decision Problems for Mixed and Modal Specifications

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

Conference or Workshop Paper
15th International Workshop on Expressiveness in Concurrency
Electronic Notes in Theoretical Computer Science
August, 2008
DOI 10.1016/j.entcs.2009.06.011

Mixed and modal transition systems are formalisms allowing mixing of over- and under-approximation in a single specification. We show EXPTIME-completeness of three fundamental decision problems for such specifications: whether a set of mixed or modal specifications has a common implementation, whether a sole mixed specification has an implementation, and whether all implementations of one mixed specification are implementations of another mixed or modal one. These results are obtained by a chain of reductions starting with the acceptance problem for linearly bounded alternating Turing machines.

PDF of full publication (313 kilobytes)
(need help viewing PDF files?)
BibTEX file for the publication
Conditions for downloading publications from this site. built & maintained by Ashok Argent-Katwala.