概率纤维化模态逻辑的计算复杂性研究

摘要

将不同的逻辑系统进行组合,能够以更加精细的方式来描述现实世界。不同的组合技术,如交融(Fusion),直积(Product),纤维化(Fibring)相继被提出,其中纤维化特别适合于对模态逻辑进行组合,因此备受关注。
　　 本文从计算复杂性的视角,分析了一大类由正规模态逻辑通过纤维组合之后所得到的逻辑系统,分别证明了相关的可满足性问题的计算复杂性。与此同时本文证明了将两个s5系统通过纤维方法进行组合后,其中一个特殊的片段的可满足性问题的计算复杂性是NP-Complete的。本文的另一个重要贡献在于,介绍了一种对模态逻辑逻辑进行概率化的方式,并成功证明了概率化S5逻辑属于NP-complete,概率纤维化S5逻辑属于PSPACE-complete。最后本文同样找出了一个概率纤维化S5系统的某一个计算复杂性为NP-complete的片段。
　　 这些研究结果的意义在于,尽管纤维化方法已经提出了很长时间,但是主要的研究工作大多关注如何使纤维化逻辑的重要性质得到保持的问题,本工作是为数较少的从计算复杂性的角度研究纤维化模态逻辑以及概率化模态逻辑的计算复杂性。这些结果一方面可以帮助明晰通过纤维方法组合逻辑的计算尺度,同时从更加实用的角度考虑,它们有助于实现描述能力和表达能力的平衡。