Complexity of Decision Problems for Mixed and Modal Specifications
Complexity of Decision Problems for Mixed and Modal Specifications
复制标题
混合和模态规范决策问题的复杂性
DOI：
10.1007/978-3-540-78499-9_9
复制
发表时间：
2008
期刊：
影响因子：
--
通讯作者：
A. Wąsowski
中科院分区：
文献类型：
--
作者：
Adam Antonik;M. Huth;K. Larsen;Ulrik Nyman;A. Wąsowski
我们认为决策问题的模态和混合转换系统作为规范：共同的实现问题（是否一组规范有一个共同的实现），一致性问题（是否一个单一的规范有一个实现），和彻底的细化问题（是否所有的实现一个规范也实现另一个）。常见的实现和彻底的改进被证明是PSPACE的模式，所以也为混合，规范。一致性对于混合规范是PSPACE困难的，而对于模态规范则是微不足道的。我们还提供上限，这些问题之间的强联系。
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 PSPACEhard for mixed, while trivial for modal specifications. We also supply upper bounds suggesting strong links between these problems.