弱互模拟等价类算法改进

大量的硬件和软件系统广泛应用在一些重要的领域，在许多情况下错误和失效是不可接受的。需要提供方法来检验软硬件的正确性，增强我们对软硬件系统的信心。形式化验证提供了提高软硬件可靠性的方法。 互模拟等价类和弱互模拟等价类可以用来降低形式化验证中模型的规模。弱互模拟等价类有两种算法：一种是先计算迁移关系的自反传递闭包，然后调用互模拟等价类的算法。另一种是作为IGPTPartEF的一个特例，直接在原图上用划分精化的方法计算。针对这些计算弱互模拟等价类的算法，我们提出两种改进算法。 首先，我们观察到有些状态在划分精化的过程中不会被再次切分，可以事先将它们归类到一个组，在划分精化过程中以这些组为基本单位进行切分，可以在很大程度上减小算法花费的时间。我们用该思想给设计出了改进算法一。 然后，我们观察在Paige-Tarjan算法中引入了“处理比较小的一半”的思想来改进计算互模拟等价类的算法，它使得计算互模拟等价类的算法的时间复杂度从O(mn)（其中m是边数，n是顶点数）改进到O(mlgn)，而在前面所述的弱互模拟等价类算法中并没有引入“处理比较小的一半”。我们引入这一思想，设计出了改进算法二。 之后，我们设计实现了原型工具，并进行了数据实验来证实算法在时间上与原算法相比有明显改进。

模态逻辑公式为见证的互模拟等价判定

判定两个进程是否具有某种等价关系，是形式化验证的重要组成部分，很多种等价关系被定义出来以满足不同的验证需求，强互模拟等价和分支互模拟等价是其中两个重要的两种等价关系。强互模拟等价可以用HML(Hennessy-Milner Logic)逻辑刻画，分支互模 拟等价可以用HMLU(HML with Until)等逻辑刻画。两个模型不能强互模拟等价或者分支互模拟等价时，存在一个作为见证的相应逻辑描述的公式，该公式只能被其中一个模型满足，称之为诊断公式。诊断公式的意义在于有助于分析理解模型为什么不具有相应的等价关系，给出诊断公式是对判定算法有意义的扩充。修改后的PT(Paige-Tarjan)算法可以用于计算有限状态进程之间的强互模 拟等价关系，修改后的GV(Groote-Vaandrager)算法可以用于计算分支互模拟，对它们相应的扩充可以为不能强互模拟等价或分支互模拟等价的进程生成诊断公式。 主要工作如下：分析为强互模拟等价和分支互模拟等价生成诊断公式的方法。设计处理有限状态进程表达式并将其转化为标号迁移系统的算法。扩展PT 算法，使其适用于标号迁移系统，并在判定强互模拟等价的过程中为不能强互模拟的进程生成HML 描述的诊断公式。扩展GV 算法，使其能够在判定标号迁移系统上分支互模拟的同时，为不能分支互模拟的进程生成HMLU 描述的诊断公式。

弱互模拟等价类算法改进

大量的硬件和软件系统广泛应用在一些重要的领域，在许多情况下错误和失效是不可接受的。需要提供方法来检验软硬件的正确性，增强我们对软硬件系统的信心。形式化验证提供了提高软硬件可靠性的方法。 互模拟等价类和弱互模拟等价类可以用来降低形式化验证中模型的规模。弱互模拟等价类有两种算法：一种是先计算迁移关系的自反传递闭包，然后调用互模拟等价类的算法。另一种是作为IGPTPartEF的一个特例，直接在原图上用划分精化的方法计算。针对这些计算弱互模拟等价类的算法，我们提出两种改进算法。 首先，我们观察到有些状态在划分精化的过程中不会被再次切分，可以事先将它们归类到一个组，在划分精化过程中以这些组为基本单位进行切分，可以在很大程度上减小算法花费的时间。我们用该思想给设计出了改进算法一。 然后，我们观察在Paige-Tarjan算法中引入了“处理比较小的一半”的思想来改进计算互模拟等价类的算法，它使得计算互模拟等价类的算法的时间复杂度从O(mn)（其中m是边数，n是顶点数）改进到O(mlgn)，而在前面所述的弱互模拟等价类算法中并没有引入“处理比较小的一半”。我们引入这一思想，设计出了改进算法二。 之后，我们设计实现了原型工具，并进行了数据实验来证实算法在时间上与原算法相比有明显改进。

生成诊断公式的有限状态进程等价验证

分析有限状态进程互模拟等价判定技术,探讨了诊断公式的生成问题。给出了将有限状态进程转化为带标号的迁移系统,修改了Paige和Trajan求解最粗划分的算法,使其适用于带标号的迁移系统。给出生成Hennessy-Milner逻辑描述的诊断公式的算法,当两个进程不能互模拟时,产生两个诊断公式。算法的时间复杂度为O(mlogn),空间复杂度为O(m+n)。