Computing Publications

Publications Home » Complexity of decision problems f...

Complexity of decision problems for mixed and modal transition systems

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

Conference or Workshop Paper
FOSSACS 2008
Lecture Notes in Computer Science
March, 2008
Springer Verlag
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.

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

The PDF is a preliminary version of the final paper.

N.B.
Conditions for downloading publications from this site.
 

pubs.doc.ic.ac.uk: built & maintained by Ashok Argent-Katwala.