并发理论研究并发现象,即多个独立运行的计算主体(进程)相互间通过交换信息(通信)实现协作,以共同完成预定的任务的计算现象。自六七十年代起各种并发理论相继提出并得到广泛研究,例如,Petri Net、进程代数、模态逻辑等。本文的工作主要集中于传值进程理论和移动界程理论上。 模型检测是一种针对并发系统的自动分析与验证技术。其基本原理是用状态迁移图S表示要分析的系统,用模态/时序逻辑公式φ描述要检查的性质。系统是否具有所要求的性质就转化为S是否满足φ,对有限状态系统这个问题是可判定的。和其他验证方法(如:模拟、测试、机器证明等)相比模型检测方法具有两项突出的优点:其一,验证过程完全自动化:其二,当抽象模型不满足逻辑公式时,检测工具会自动产生一个反例来说明为什么不满足,以用于查错和修改。 本文的研究工作主要由传值系统的模型检测方法和移动系统的模型检测方法两部分组成。 在传值进程系统中,本文的工作主要包括三方面:首先本文讨论谓词μ演算和模态图之间的语义等价问题。模态图是谓词μ演算的一种图形表示形式,它的提出是为了克服线性谓词μ演算公式复杂难懂,不利于机器处理的缺点;将谓词μ演算应用到传值进程的模型检测中。本文通过定义嵌套谓词等式系来建立两者之间的联系。提出了从文本公式到模态图的转换算法并证明了转换的正确性。其次,本文研究了传值进程模型检测中诊断信息的生成问题,引入两种有效的诊断信息表示结构:证明图和示例;提出了相应的诊断信息生成算法并予以实现。此外,为了对付模型检测的状态爆炸问题,本文研究了弱谓词μ演算和弱互模拟之间的关系。定义基于STGA的惰性迁移的概念,并证明惰性迁移的前后状态是弱互模拟的,并且在象有限的模型下,它们满足相同的弱谓词μ演算性质。在此基础上提出了传值进程模型检测的一种偏序归约方法,并将该方法集成到已实现的自动检测工具中。 在移动进程系统方面,本文的工作主要是实现了移动界程的模型检测系统。主要工作包括提出移动界程的底层de Bruijn表示;并将其应用到有限控制移动界程的范式表示上,提出了移动界程的有效的底层表示方法。在此基础上实现了带不动点算子的界程逻辑的模型检测算法。该工具是首个能检测带递归性质的移动界程模型检测系统。