第二章 Petri网与代数系统的关系
（1） G是理想G的Grobner基； （2） 对每个f?G,f模G的范式为0；
（3） 对每个非零的多项式f?G，f模G是可约的。
定义2-6 设g1,g2?k?x1,x2,?xn?, 是两个非零多项式。 如果HT(g1)?x1ax2a?xna，HT(g2)?x1bx2b?xnb12n1212nn 令cii=1,?,n,?max{ai,bi}，
则称xc?x1cx2c?xnc为HT(g1)和HT(g2)的最小公倍式， 记作： LCM(HT(g1),HT(g2))。
设ti?HT(gi),ai?HC(gi), i=1,2并且t?siti?LCM(t1,t2),其中si?T(x1,?,xn) 则称：S(g1,g2)?a2s1g1?a1s2g2为g1, g2的S-多项式
例1. 设f?x3y2?x2y3?x,g?3x4y?y2?R?x,y?, 单项式序是分次字典 序，则LCM(HT(f),HT(g))?x4y2, S(f,g)?3x?f?y?g??3x3y3?3x2?y3 定理2-3 假设G是k?x1,x2,?xn?的有限子集，并且0?G,则下列性质等价： (1) G是理想〈G〉的Grobner基； (2) ?g1,g2?G, S?g1,g2??0
G?有了这些性质，我们就可以计算Grobner基。
Grobner基算法[34]：
设F??f1,f2,?,ft??k?x1,x2,?xn?, 理想I?f1,f2,?,ft，则下列算法可计算理想I的Grobner基G。
Input: F={f1,f2,…,fs}
Output: G={g1,g2,…,gt}?F, G is Grobner basis of〈F〉 Begin G:=F
B:={{g1,g2}| g1,g2∈G,g1≠g2} While B≠Φ do Choose {g1,g2}∈B B:=B－{{g1,g2}}
h:= S(g1,g2) h0:= S(g1,g2)G
11
Petri网系统的可达性研究
if h0≠0 then B:=B∪{{g,h0}| g∈G} G:=G∪{h0} End
根据上面的算法和变迁多项式的形式，我们有下面的定理。 定理2-4
变迁多项式的Grobner基仍保持两单项式相减的形式，每项系数为1(或-1) 。 证明：由上面的算法，G先赋值为F每一项是两单项式相减的形式，
h:= S(g1,g2)＝S(g1,g2)?a2s1g1?a1s2g2，消掉两项，剩下的保持两单项式相减的形式。又h0:= hG 约化时每次同时消掉两项，剩下的保持两单项式相减的形式。所以添加到G中的多项式都是两单项式相减的双项式。 同理可得计算过程保持每项系数为1(或-1)。
由于在计算过程中有此形式，所以计算量比通常的求Grobner基的计算量小。 根据以上的理论，Petri网可达性等行为特征就可以用Grobner基来表述，因为用Grobner基的方法很容易判断一个多项式是否属于某个理想，所以根据定理 对于完全可逆Petri网，Grobner基的方法是一个完全的判准；但对于不可逆Petri网，它只是状态可达的一个必要条件。 §2.3 Maple符号计算软件介绍[14]
一．Maple简介
Maple 是加拿大Waterloo University 发展起来的一种数学软件, 它那无与伦比的符号运算能力，已使Maple在国际通用数学软件的激烈竞争中独占熬头。不仅使国外学生中广为流行的\科学便笺式\软件Mathcad靠Maple实现符号运算，就连首屈一指的数值计算软件MATLAB在扩展其符号运算能力时，也借助了Maple的威力。Maple V版本提供数学函数2000余种（现在更新的版本有Maple 7.X），其涉及范围：基本代数学、欧几里德几何学、数论、有理函数、微积分、线性代数及矩阵论、微分方程、图形学、离散数学、群论、以及数学的其它许多领域。Maple是一个开放的系统，它提供一套内部的编程语言，使用户可以开发自己的应用程序。事实上 Maple 所提供的2000多种函数种，绝大部分是用这种语言编写的。
二. Maple的工作窗口
Maple V Release 2有基于Dos 和 Windows 的两个版本，可以在80386或80486以上的微机上运行。基本运行环境要求硬盘有至少15MB的空间、4MB的内存，其中Windows 版需要 MS-windows3.1 以上版本（中西文版本均可）均可.Maple V for windows 启动后会出现一个Maple 工作区空白窗口. 此时，用户就可以在 Maple 工作区内出现的提示符号―>‖后，输入命令，进行工作。需要说明的是：输入表达式后面必须用分号\；\结尾，以表示命令的结束，然后按回车键进行运算。如若结尾缺少\；\，那么Maple 认为命令没有结束，而处于等待状态。
12
第二章 Petri网与代数系统的关系
三. 符号运算
Maple最主要的功能是符号运算，其功能强大是举世公认的.符号运算的魅力在于：运算时，无需事先对独立变量赋值，而所得得结果以标准得符号形式表达。在符号表达式中得数字都是不含任何机器精度误差得绝对精确值（如：2/3就绝不会表示成0.66666.....).这是任何数值计算所无法实现的。
四．Grobner基软件包
我们所使用的Maple版本是Maple V Release 2。
在进入Maple系统后，只需键入： > with (grobner)；
即可调入Grobner基软件包。（其中>是Maple系统的提示符，所有的Maple命令都以分号结束）。当Grobner基软件包被调入后就可以计算Grobner基，范式，S-多项式等。在上一节我们介绍了几种单项式的序，在Maple系统中可以使用字典序和分次逆字典序。Maple系统用plex表示字典序，用tdeg表示分次逆字典序。单项式序还与变元的排列次序有关，因此必需给出变元的排列次序。比如：为了告诉Maple系统使用字典序，变元排列次序为x>y>z，需要输入plex和[x,y,z]，Maple系统的缺省单项式序是tdeg。
在Maple的Grobner基软件包中最常用的命令是gbasis,可用来计算一组多项式的Grobner基，用法是:
> gbasis(polylist,termorder)；
其中：polylist表示生成理想的多项式组，termorder表示变元的排列次序及单项式序。例如：
> with(Grobner):
WL:=[x^2-2*x*z+5,x*y^2+y*z^3,3*y^2-8*z^3]: GB:=gbasis(WL,plex(y,x,z));
GB := [240z???1600z???9z???96z,640xz???9z???120z???96z,x???2xz???5,80yz???3z???32z???40z,3y???8z]387523639838572
> gbasis(WL,tdeg(x,y,z));
[x???2xz???5,?3y???8z,8xy???3y,9y???48zy???320y]22323432
在Maple的Grobner基软件包中另一个在Maple的Grobner基软件包中另一个最常用的命令是normalf，可以用来计算多项式f模理想I的范式。 它的用法是：
> normalf(f,polylist,termorder)；
其中：polylist表示生成理想的多项式组，termorder表示变元的排列次序及单项式序。
例如：
> q:=x^2-x*z^3+y^3+y*z: normalf(q,GB,plex(x,y,z));
13
Petri网系统的可达性研究
2xz???yz???73640z???87360z???77348z???5
5
在Grobner基软件包中其他常用命令有：
? leadmon 计算多项式f的首单项式HM(f). ? spoly 计算多项式f,g的S-多项式.
? solvable 判断多项式方程组{f1,f2,…,fn}在代数封闭域K上是否有
解。
? finite 判断多项式方程组{f1,f2,…,fn}在代数封闭域K上是否有
有限解。
? gsolve 可以求出多项式方程组{f1,f2,…,fn}在代数封闭域K上是
否有解。
§2.4 计算代数方法的局限性
通过上述的分析，我们知道计算代数方法，在处理可达性的时候有个强假设就是该Petri网系统可逆，但对于实际问题，你事先根本不知道该Petri网系统是否可逆。问题的关键在于Petri网系统的变迁条件与过程是有方向的，也就是在变迁多项式（双项式）前乘上的系数必须为正，而理想中的元素被基所表示时不能有效的反应这种性质。要判断可逆性就必须判断某种状态是否能回到初状态，又回到可达性问题了，所以只能作一个必要条件用，这一问题始终不能解决。 其次，即使Petri网系统是可逆的，用计算代数方法只能判断是否可达而不能构造出变迁过程。而在分析系统性质时状态变迁过程是必要的。
当然就Grobner基方法本身也存在一些问题，从现在已知最好的算法来看，计算一个理想的Grobner基，也需要花费很长的时间和大量的存储空间，主要原因是：在Grobner基的计算过程中，我们需要生成大量的中间多项式。
当然除了Grobner基方法还有其它的计算代数方法，比如：吴方法[26]，Dixon结式方法[31]，相对单纯分解方法[23]，聚筛方法[32]。在计算效率上比Grobner基方法高，但是这些方法都着眼于多项式组的零点问题，而不是理想的归属问题。由Hilbert 零点定理[22]，代数簇与理想不是一一对应，而与根理想一一对应，所以在用于Petri网系统的可达性分析时有些不方便，仅仅可作为可达性分析的一个比较弱的必要条件。 所以我们有必要找到一个有效的方法来解决以上计算代数方法的不足。通过第二章第二节的内容，我们知道Petri网系统的状态与n维线形空间的第一象限的整点有自然的对应，同样变迁对应于对点作平移变换，可达性问题可以化为点对点的平移变换序列的存在性，但变换是有限制的，就是只能在第一象限做变换。这种限制可以通过能量优化的方法表现。下面我们将介绍能量优化模型和模型的神经网络解法。
14
第三章 能量优化模型
第三章 能量优化模型
能量优化模型的引入主要基于用矩阵描述变迁过程和用罚函数处理约束的思想，每个变换步骤对应一个能量，整个变换过程只能在第一象限，一旦“出界”对能量函数加上一个足够大的惩罚，这样只要存在一个解使得总能量充分小就能说明该解满足约束条件。
§3.1 Petri网系统映射到线性空间
一．Petri网到线性空间的映射规则
给定一个Petri网系统PN=(S,T,F;K,W,M0) 都可以生成一个Petri网线性空间PNL=(LP+,TS,V0)。
1．系统状态空间映射成LP+，n维线形空间第一象限的符合容量函数K限制
的整点集，
系统位置Pi?xi ，n维线形空间的第i个分量，
系统状态Mi?Vi , n维线形空间的一个各分量为非负整数的符合容量函数K限制地状态点; 2．变迁映射成平移变换集TS={fi | fi 是n维线形空间中各分量为整数的向量} 对tj∈T,
A. 当没有位置是同时某个变迁的输入和输出时， 对应的平移变换fj ：(x1,x2,?,xn) 其中:
?W(tj,pi)?xi???W(pi,tj)??0如果(tj,pi)?F并且(pi,tj)?F如果(pi,tj)?F并且(tj,pi)?F 其它B. 当有位置是同时某个变迁的输入和输出时，
对应两个平移变换fj＋：(x1,x2,?,xn) 和 fj－：(y1,y2,?,yn) 其中:
?W(tj,pi)xi???0??W(pi,tj)yi???0如果(tj,pi)?F其它如果(pi,tj)?F其它
3．tj在状态M下施实条件映射成：
A. 当没有位置是同时某个变迁的输入和输出时，
对于V+fj 的每一个分量xi 都满足,0≦xi≦K(xi) , 而且V+fj就是tj在状态M下的施实结果。
15