PSL构造双向交换自动机及非确定自动机的方法

• 作者: 虞蕾 陈火旺
• 来源期刊: 软件学报
• 学科: 工学
• 关键词: PSL(property specification language) FL(foundation language) 双向交换自动机 非确定自动机 模型检验
• 年，卷（期）: 2010,（1）
• 所属期刊栏目: 理论计算机科学
• 页码范围: 34-46
• 页数: 13页
• 分类号: TP301
• 字数: 10524字
• 语种: 中文
• DOI: 10.3724/SP.J.1001.2010.03456

摘要

PSL(property specification language)是一种用于描述并行系统的属性规约语言,包括线性时序逻辑FL(foundation language)和分支时序逻辑OBE(optional branching extension)两部分.由于OBE就是CTL(computation tree logic),并且具有时钟声明的公式很容易改写成非时钟公式,因此重点研究了非时钟FL逻辑.为便于进行模型检验,每个FL公式必须转化成为一种可验证形式,通常是自动机(非确定自动机).构造非确定自动机的过程主要是通过中间构建交换自动机来实现.详细给出了由非时钟FL构造双向交换自动机的构造规则.构造规则的核心逻辑不仅仅局限于是在LTL(linear temporal logic)基础上的正规表达式,而且全面而充分地考虑了各种FL操作算子的可能性.并且给出了将双向交换自动机转化为非确定自动机的一种方法.最后,编写了将PSL转化为上述自动机的实现工具.FL双向交换自动机的构造规则计算复杂度仅是FL公式长度的线性表达式,验证了构造规则的正确性.在此基础上,证明了双向交换自动机与其转化的等价的非确定自动机接受的语言相同.上述工作对解决复杂并行系统建模和模型验证问题具有重要的理论意义和应用价值.