PSL可满足问题的计算复杂度OACSTPCD
Computational Complexity of Satisfiability Problems for PSL
PSL是一种用于描述并行系统的属性规约语言,包括线性时序逻辑FL和分支时序逻辑OBE两部分.由于OBE就是CTL,因此论文重点研究FL逻辑.理论上已证明许多难解的问题都可多项式变换为"可满足性"问题,"可满足性"同题是研究时序逻辑的核心问题之一,并已成为程序验证的一种有力工具;而计算复杂度是"可满足性"问题需要解决的最深刻的方向之一,其研究意义在于它可作为解决一类问题的难度的标准.文中在利用"铺砖模型"基础上,推导并得出FL的"可满足性"问题的计…查看全部>>
虞蕾
国防科学技术大学,计算机学院,湖南,长沙,410073;第二炮兵工程学院,计算机系,陕西,西安,710025
信息技术与安全科学
PSL可满足性问题计算复杂度
《计算机技术与发展》 2010 (2)
16-20,24,6
中国博士后科学基金(20080431401)
评论