Petri网系统的可达性研究
假定m元非负整数行向量σ是σ的变迁实施计数向量，亦即σ的第i元素表示变迁i从M0到M转换过程中的实施次数，则有:
M=M0+ C×σ 于是有下面定理: 定理1-2：
一个n维向量X是∑的一个S-不变量当且仅当 MTX=M0TX，其中M0是∑的初始标识，M∈[M0>。 证明：“?”
因为x是∑的一个S-不变量，所以有CTX=0；又有M∈[M0>，所以 M=M0+ C×σ，即MT= M0T+σT×CT，所以MTX=M0TX＋σT×CTX，得 MTX=M0TX。
―?‖
M∈[M0> ? MT= M0T+σT×CT, MTX=M0TX＋σT×CTX，又有MTX=M0TX
σT×CTX=0; 由M的任意性可知CTX=0。 ?
同样有下面的定理。 定理 1-3：
一个m维向量X≥0是∑的一个T-不变量当且仅当存在∑的一个标识
M∈[M0>（M0是∑的初始标识）和一个变迁实施序列σ从M回到M，亦即，M?M，σ的实施计数向量σ等于X。
第二章 Petri网与代数系统的关系
§2.1 Petri网模型映射到代数系统
除了用关联矩阵，各种向量的方法来表示Petri网系统的状态和系统变化的过程以外，还有其他的数学描述方法来刻划和定量分析Petri网系统的性质。1995年Olga Caprotti, Alois Ferscha, Hoon Hong[2]提出利用代数系统来描述Petri网系统的性质。下面将介绍Petri网系统的多项式的描述方法。 一．映射的直观描述
1．系统状态映射成多元多项式环上的单项式。
系统位置Pi?Xi
Pi中的token数?Xi的方次 系统状态M ?一个单项式a 2．变迁条件映射成双项式
根据ti的输入输出的连接位置及弧的权值，将变迁条件映射成双项式。 ti ? fi
3．变迁过程映射成多项式除法。
ti在状态M下可施实等价于 ?ci ,使得a=ci LT ( fi ) , a是M对应的单项式，ci 是单项式，LT(fi)表示 fi的第一项，ST(fi)表示 fi的第二项。 后继状态＝a－cifi＝ci ST ( fi ) 。
ci 的实际意义是ti变迁没用到的资源；
6
第二章 Petri网与代数系统的关系
LT(fi) 的实际意义是ti变迁消耗的资源； ST(fi) 的实际意义是ti变迁产生的资源。
比如：
t1 P1 2 1 P3 1 2 t2 P2 P4 P5
2 2 系统状态为：x13x2x5
Pol(t1)＝x12x2－x3x42 = f1 Pol(t2)＝x42－x52 = f2
很明显，系统状态与多元多项式环上的单项式一一对应。
这时t1是可施实的，t1实施后系统状态变为：
P1 2 1 P3
1 2 P4 P5 P2 2 2
变迁过程的代数表达:
x1x3x42x5=x13x2x5－x1x5f1＝x13x2x5－x1x5(x12x2－x3x42)
=x13x2x5－x13x2x5 + x1x3x42x5
二．映射的形式化描述
Petri网系统到Petri网代数系统。
定义2-1：给定一个Petri网系统PN=(S,T,F; W,M0) 都可以生成一个Petri网代数系统PNA=(X,H,a0)。
I. X={x1,x2,?,xn} 系统位置Pi?xi
II. H={hi | hi 为型如 x1e1x2e2?xnen － x1d1x2d2?xndn 的双项式}
对tj∈T, 对应的双项式
hj ：x1e1x2e2?xnen － x1d1x2d2?xndn 其中:
?W(pi,tj)ei???0if(pi,tj)?F其它
7
Petri网系统的可达性研究
?W(tj,pi)di???0if(tj,pi)?F其它
III. a0 = x1k1x2k2?xnkn ki 表示 M0 状态下Pi中的token数。
三．可达性的代数表达 定理2-1：
对于P/T网系统，∑=（S,T；F, K,W, M0），σ=M0t1M1t2…tnMn是∑的一个有限实施序列，其中，Mi对应的状态单项式为ai，ti对应的变迁双向式为gi，则：a0－an=∑cigi , ci为多项式
证明：M0[t1>M1 对应的代数表示为：a1=a0 – c1g1
M1[t2>M2 对应的代数表示为：a2=a1 – c2g2=a0 – c1g1– c2g2
??
M0[σ>Mn 对应的代数表示为：an＝a0－∑cigi ，即a0－an=∑cigi 。
定理2-2：对于P/T网系统，从M1可变迁到M2?存在a0－an的一组正表示即
a0－an=∑cigi，并且ci为正多项式。
证明：充分性上面已经证明，下面证明其必要性。
a0－an=∑cigi，并且ci为正多项式，可以将各项拆开，a0－an=∑digi d1是正单项式, 当然gi可能有重复，digi是双项式,记为：xi－yi
等式左边为两个正单项式之差，右边必存在xi1＝a0，将xi1－yi1移到左边 a0－(xi1－yi1) －an＝yi1－an , 令yi1=a1 , 重复上面的工作，最后得到一组正 单项式{a1 , … , an-1 },也就构造出M1变迁到M2的过程。
我们将可达性问题转化为了一个多项式是否属于某个理想的问题，要研究该问题必须用到计算代数的相关知识。
§2.2 基于Grobner基的Petri网系统性质分析 一．计算代数基本概念[13]
定义2-2 在T(x1,x2,?,xn) 上满足下列条件的线序≤叫做T(x1,x2,?,xn)上的单项式序。
1、?t?T(x1,x2,?,xn)1?t;
2、对每个s,t1,t2?T(x1,x2,?,xn),t1?t2?t1?s?t2?s
关于单项式序的例子有很多，比如最常用的有字典序: 定义2-3 在T(x1,x2,?,xn)中，定义x1?xn(d1,?,dn)?(e1,?en)或者存在1?i?nd1dn?x11?xnn当且仅当
ee使得dj?ej,1?j?i?1并且 di?ei。这种
序被称为字典序，我们常用?lex表示。
很容易验证字典序是单项式序。我们可以给出一些例子。
8
第二章 Petri网与代数系统的关系
1．x1x22?lexx23x32。
2．x1x23x36?lexx1x23x34;按照字典序我们有x1?lexx2?lex??lexxn, 另一方面，在变元x1,x2,?,xn中任意给定一个次序，也可诱导出上
T(x1,x2,?,xn)的一个字典序。假如设变元是
x, y，如果规定x>y，则在T(x, y)
中给出一个字典序，但是如果规定y?x，则在T(x, y)中给出了另一个字典序，这两个序是不同的。一般的，在n个变元的情况下，我们可以给出n!种不同的字典序。
研究多项式时，很多时候研究多项式的首项，下面给出相关的几个概念。 定义2-4. 假设≤是T上的单项式序。对于非零的多项式f?k?x1,?xn?，称(T(f),
?)中的最大项为
f的首项，用HT?f?表示。称(M(f), ?)中的最大项为f的首单
项式用HM?f?表示。首单项式HM?f?的系数称为首系数，用HC?f?表示。显然有
HM?f?= HC?f??HT?f?
对于给定的单项式序≤，如果f≠0，并且HC?f?=1，则称f是首1的多项式。
有了单项式的序就可以自然诱导出多项式的序，单项式序的诸多性质也为化简多项式提供了计算的方向和可计算的保证。
定义2-5 假设k是数域，令f,g,p?k?x1,x2,?xn? ，其中f,p?0，设≤是
T(x1,x2,?,xn)上的单项式序，P
是k?x1,x2,?xn?的子集，
?p?P,p?0我们有
1、如果t?T(f),并且存在s?T(x1,?,xn），使得s?HT(p)?t，而且
g?f?aHC(p)?s?p, 其中a是t在f中的系数
2、如果存在t ?T(f)使得f?pg?t?, 则称f模p约化到g记做：f?pg。 3、如果存在p?P,使得f?pg，则称f模P约化到g记做：f?Pg 4、如果存在g?k?x1,?,xn?,g?f使得f?Pg，则称f模P可约化。
9
Petri网系统的可达性研究
如果一个多项式f可以经过一系列约化步骤得到g，(即存在g1,g2,?,gn
?Pg表示。 使得f?Pg1,g1?Pg2,?,gn?1?Pgn?g)。我们用f?如果一个多项式f模P是不可约化的，则称f模P的范式。很明显，只有当T(f)中的每一项都不能被{HT(p) | p?P} 中的任一项整除时，f模P才是不可约化的。
对于每个多项式f,都存在一个多项式g使得：f?Pg 其中g是f模P是不可约化的，我们称g是f是模P的范式。
定理2-2 假设P=p1,p2,?,ps是k?x1,x2,?xn?的有限序列，f∈k?x1,x2,?xn?,则存在f模P的范式g，和一组多项式{a1,a2,…,as}?k?x1,x2,?xn?
s满足f??ai?1ipi?g，并且 max{HT(aipi) | 1≤i≤s, aipi≠0}≤HT(f)。
有了存在性人们自然要研究它的唯一性，可惜在一般情况下不能保证范式的唯一
性，下面就是一个简单的反例。
例 设f(x,y)?xy2?x?k?x,y?,p1(x,y)?y2?1，p2(x,y)?xy?1
令P={p1(x,y)，p2(x,y)}, ≤是T(x,y)上的字典序。
我们有f(x,y)?p0
12 另一方面又有f(x,y)?p(?x?y)
这里0，(?x?y)都是f(x,y)模{p1(x,y)，p2(x,y)}的范式，但它们是不同的。
二．Grobner基及其算法
为了研究多项式环，就必须研究环上的理想，研究理想的结构，基是一个有力的工具，第一个要问的问题就是基的个数，有限还是无穷。下面的定理给出了一个明确的普遍而深刻的回答。
定理(Hilbert基定理) 每个理想I?k?x1,x2,?xn?都有一个有限基，即存在
f1,f2,?,ft?I使得I?f1,f2,?,ft。这个有限集G??f1,f2,?,ft?称为I的
Grobner基。(详细证明请见[13],[22])
Hilbert基定理给出了有限基的存在性，接着下一个问题就是如何找到。要想找到，首先必须知道目标的“样子”，也就是Grobner基有什么样的性质。 Grobner基性质定理 设G是k?x1,x2,?xn?的有限子集，给定单项式序≤，则下列性质等价：
10