On Modal Refinement and Consistency
Almost 20 years after the original conception, we revisit several fundamental question about modal transition systems. First, we demonstrate the incompleteness of the standard modal refinement using a counterexmnple due to Huttel. Deciding any refinement, complete with respect to the standard notions of implementation, is shown to be computationally hard (co-NP hard). Second, we consider four forms of consistency (existence of implementations) ibr modal specifications. We characterize each operationally, giving algorithms for deciding, and for synthesizing implementations, together with their complexities.