1、无限的Token如何发生？讨论Boundedness
接上一节，
无限Tokens
Place p1上的Token只要无限地执行t1、t2，那么每一次输入t2一个Token，t2都会输出各一个Token到p1和p3中去，所以Token的数目最终是无限的，同时其reachability graph也是无限延伸的。
如果一个Petri Net中的Place都是k-bounded的，那么我们称这个Petri
Net也是k-bounded的
初始有2个Token
所以上图中的Petri Net中我们可以发现p1、p2都是two bounded的，然后p3是unbounded（Unbounded可以认为是没有边界的没有界限的意思）的（因为这里的p1、p2中的Token数是不会增长的，最多只有2个！这里说明一下，如果在p2位置一个Token执行t3，那么这个Token会消失，因为没有出去的箭头）
综上，这个Petri Net也是Unbounded的！！
2、Safeness是什么？
Safeness=1-boundedness
如果一个Petri Net网中的每一个Place最多只可能包含一个Token，那么我们就称这个Petri Net为一个Safe Petri Net。
一个Safe Petri Net
但是下面这个是不安全的：
不安全
因为x位置可能出现2个Token
3、Deadlock
我们称一个marking（可以认为是一个状态）是死的，如果所有的正方形transition都不处于Enabled状态。
反之，如果一个PetriNet在任意时刻都至少有一个Transition是处于Enabled状态，那么我们就称这个Petri Net是一个deadlock-free Petri Net，如下图，反复执行t3，那么最终会出现Deadlock现象，即再没有Transition处于Enabled状态：
初始有2个Token
4、Liveness
先看如何定义一个Transition是Live即活跃的，当一个Petri Net中的一个Transition在遍历所有可能情况之后发现其中一个情况是可以被使能的（即进入Enabled状态），那么我们称这个Transition是Live的
当一个Petri Net中的所有Transition都是Live的，那么我们称这个Petri Net就是Live的！
一个Petri Net如果是live的，那么它同时也是deadlock-free的，反之，不对
deadlock-free但不是live
以一个例子总结一下：
总结
not bounded：经过t1加入p4，p4中的Tokens变成无限
not safe：因为not bounded了
not deadlock-free：因为此时这个状态t1执行完了之后，立即执行t4，那么t2这个Transition无法继续执行，因为有一个Arc是从p4进入到t2中去的
not live:因为存在一个可能有Transition没有live
下面这张图同理：
同理
5、Complete traces
从Initial state到Final State，我们把其中的一个可能画出来就是一条Complete trace了
Complete trace示意
每一个Transition System都是有好多条的complete traces和好多条的incomplete traces
下面的Petri Net，上面的是Transition System
6、Workflow Nets（WF-nets）
WF-net
上图中的WF-net可以明显的看到一个start和一个end，这是WF-net的特征。
几个常见的过程模型
7、Soudness
我们现在引入一个新的量来描述一个WF-net。
首先我们明确一个工作网中的所有Transition和所有的Place都在工作网设定的开头和结尾之间连接的一条路径上。
接着，我们现在会说一个WF-net是sound的，当且仅当满足下列条件：
- Safeness：一个Place不能同时持有多个Token
- Proper Completion：当一个Token到达最末尾的Place的时候，所有其他的Place应当是空的
- Option to Complete：无论出现什么情况，我们都能保证最后恰好有一个Token在最末尾的Place上
- Absence of Dead Parts：（这个条件有点不清楚，直接就把英文原文翻译过来了）对于任意一个Transition，都必须有一个能够使其起作用的顺序（这个规则好像就是说每一个Transition都必须不能是dead的）
这个soundness的判断非常重要！！在过程挖掘中经常会被用到！
如果Proper Completion这个条件不成立，那么Option to Complete也是不成立的，所以没必要一开始就去判断Option to Complete的条件
同时，如果Option to Complete成立，那么Proper Completion自动成立。
网友评论