| PSL可满足问题的计算复杂度 |
| |
| 引用本文： | 虞蕾.PSL可满足问题的计算复杂度[J].计算机技术与发展,2010,20(2):16-20,24. |
| |
| 作者姓名： | 虞蕾 |
| |
| 作者单位： | 国防科学技术大学,计算机学院,湖南,长沙,410073;第二炮兵工程学院,计算机系,陕西,西安,710025 |
| |
| 摘 要： | PSL是一种用于描述并行系统的属性规约语言，包括线性时序逻辑FL和分支时序逻辑OBE两部分。由于OBE就是CTL，因此论文重点研究FL逻辑。理论上已证明许多难解的问题都可多项式变换为“可满足性”问题，“可满足性”问题是研究时序逻辑的核心问题之一，并已成为程序验证的一种有力工具；而计算复杂度是“可满足性”问题需要解决的最深刻的方向之一，其研究意义在于它可作为解决一类问题的难度的标准。文中在利用“铺砖模型”基础上，推导并得出FL的“可满足性”问题的计算复杂度为EXPSPACE—hard，这对正确评价解决该问题的各种算法的效率，进而确定对已有算法的改进余地具有重要的指导意义。
|
| 关 键 词： | PSL 可满足性问题 计算复杂度 |
Computational Complexity of Satisfiability Problems for PSL |
| |
| YU Lei.Computational Complexity of Satisfiability Problems for PSL[J].Computer Technology and Development,2010,20(2):16-20,24. |
| |
| Authors: | YU Lei |
| |
| Abstract: | |
| |
| Keywords: | PSL |
| 本文献已被 维普 万方数据 等数据库收录！ |
|
