计算机科学与探索 ›› 2016, Vol. 10 ›› Issue (10): 1475-1481.DOI: 10.3778/j.issn.1673-9418.1507053

• 理论与算法 • 上一篇    下一篇

广义可能性计算树逻辑的两种范式

赵  杰,李永明+   

  1. 陕西师范大学 计算机科学学院,西安 710019
  • 出版日期:2016-10-01 发布日期:2016-09-29

Two Normal Forms Based on Generalized Possibilistic Computation Tree Logic

ZHAO Jie, LI Yongming+   

  1. College of Computer Science, Shaanxi Normal University, Xi’an 710019, China
  • Online:2016-10-01 Published:2016-09-29

摘要: 计算树逻辑(computation tree logic,CTL)的范式在模型检测方法中具有重要意义,但基于广义可能性测度的计算树逻辑的范式尚未有系统研究。为了进一步完善广义可能性计算树(generalized possibilistic computation tree logic,GPoCTL)理论,在现有的广义可能性计算树逻辑理论的基础上,参考经典计算树逻辑的范式,给出了广义可能性计算树逻辑的两种不同的范式——正态范式(positive normal form,PNF)和存在范式(existential normal form,ENF),及其对应的语构和语义解释。最后利用归纳假设法证明了任意的广义可能性计算树逻辑公式都有与之等价的PNF公式和ENF公式。

关键词: 广义可能性测度, 计算树逻辑, 范式, 模型检测

Abstract: Normal form of computation tree logic (CTL) plays an important role in model checking. But the normal forms of computation tree logic based on generalized possibilistic measure have not been researched systematically. For improving the generalized possibilistic computation tree logic (GPoCTL) theory, according to existing generalized possibilistic computation tree logic theory and normal forms of classical computation tree logic, this paper defines two normal forms—positive normal form (PNF) and existential normal form (ENF) based on generalized possibilistic computation tree logic, and gives the corresponding language structure and semantic interpretation. Finally, using inductive method, this paper proves that any GPoCTL formula can write into a normal form in PNF or ENF respectively.

Key words: generalized possibility measure, computation tree logic, normal form, model checking