过程日志修复算法实现+文献综述(4)
3 基本概念
3.1 Petri网
Petri网（Petri net）的概念最早由德国学者Carl Adam Petri在其博士论文《自动机通信》中提出，是一种用来描述事件和条件关系的网络[11]。这种系统模型后来以Petri为名广为流传。现在Petri网一词既指这种模型，又指以这种模型为基础发展起来的网论。Petri网的应用极为广泛。任何系统都可抽象为状态、事件及其之间关系的三元结构[12]。在Petri网中，状态用库所（place）表示，活动用变迁（transition）表示，变迁可以改变状态，库所能决定变迁是否可以发生，二者之间的依赖关系用流关系来表示。
一个Petri网是一个三元组：PN=（P,T,F），其中P是一个由库所结点构成的集合，T是一个由变迁结点构成的集合，F是有向弧的集合，通常弧的一端是库所结点，另一端是变迁结点。
对每个结点x，其前集与后集有如下定义：
前集：•x ={ y | (y,x)∈F }
后集：x• ={ y | (x,y)∈F }
前集与后集也称输入集与输出集。
令牌（Token）是库所结点中的动态对象，可以从一个库所结点转移到另一个库所结点。根据整个Petri网内各库所结点中令牌的存在情况可以用来判断此时整个系统处于什么样的状态。如果一个变迁结点的前集中的每个库所结点中都至少有一个令牌，那么这个变迁就可以发生。变迁发生时，会消耗前集中每个库所结点中的一个令牌，后集中每个库所结点会增加一个令牌。
Petri网通常有以下三种结构：
（1）不含选择与循环的Petri网。这种Petri网是最简单的Petri网，后面提到的Casual网（见3.5）就是这种情况。这种情况由于比较简单，在后面的修复工作中也比较容易进行，不需进行分解与判断循环次数的操作过程。
（2）含选择结构的Petri网。这种情况的Petri网比起上一种要复杂一些。在进行修复工作之前，要先进行Petri网的分解。分解成多个Petri网之后，再根据具体序列的情况判断实际要用到哪个分解出来的Petri网，执行算法。这里要注意选择结构与并行结构的区别。选择结构是Petri网中库所结点后集中有多个元素导致分支的情况（不包含循环情况），并行结构是Petri网中变迁结点后集中有多个元素导致分支的情况。选择结构只选择分支中的一条路径执行，并行结构要执行所有分支路径。
（3）含循环结构的Petri网。与选择结构相比，循环结构在处理上更加复杂。与选择结构一样，循环结构也是某个库所结点后集中有多个结点，但是，分支的路径会通往前面的结点中，构成循环。在执行修复算法前，需要计算循环次数，作为算法的一个输入项。具体执行过程见第4章内容。
下面我们举一个具体实例来说明这些概念。
例1.图3.1中就是一个Petri网，可以看出库所集合P={psource,p1,p2,p3,p4,p5,p6,psink},变迁集合T={t1,t2,t3,t4,t5,t6}。对于结点p1 ，其前后集分别为 •p1={t1}，p1•={t2}。这个Petri网不含选择与循环结构，属于最简单的Petri网。
下一篇：基于图模型的图像标注+文献综述