Petri网系统的弱公平性判定

本文首先给出了一个Petri网系统的有效可重复向量的两个性质.随后,又给出了用有效可重复向量判断Petri网系统弱公平性相关问题的一个充分必要条件.在一个Petri网系统中,任意的两个变迁ti,tj,则tj弱公平依赖于ti,当且仅当不存在这样的有效可重复向量X,使得X(j)0且X(i)=0.最后,用一个实例展示结论的应用过程.     

Petri网系统中的有效本原可重复向量集

基于有效可重复向量,可以判定一个标准Petri网产生的语言是否为正规语言,或者是否为上下文无关语言.文章提出了Petri网系统(N,M0)中的有效本原可重复向量集(记为SEPRV(N,M0))的概念.文中分析了有效可重复向量的性质,并且指出SEPRV(N,M0)可以代表所有的有效可重复向量.     

合法变迁引发序列判定中的T-不变量添加

Petri网的合法变迁引发序列(Legal Firing Sequence,简称LFS)问题是Petri网可达性问题的子问题,目前已有较多的研究成果。通过反例指出,对于Petri网(N,M0)状态方程的任意一个非负整数解X,和N的任意一个T-不变量,LFS(N,M0,X)不一定等于LFS(N,M0,X+Y)。在一般情况下,不能在待判定的解向量X中添加T-不变量。这是Petri网合法变迁引发序列判定的一个性质。     

Petri网死锁的求解算法

本文对Petri网的基础知识作了相关的介绍,以及对Petri网的结构性质进行一定的介绍与分析,其中主要介绍的结构性质是可重复向量和死锁,并适当的通过举例来说明问题.根据Petri网的相关结构性质,初步得出了T-不变量、可重复向量、死锁的关系,给出了T-不变量和可重复向量的求解算法,以及对Petri网进行结构变化的基础上,给出相应算法去求解一个网的死锁.最后还给出了利用真值表求解死锁的方法.     

若干图广义字典积的星全色数

设G是具有顶点集C(G)={t0,…tn-1}(n≥2)的图,hn=(Hi)i∈{0.1,…n-1}是不相交图的序列,其中Hi的顶点集为V(Hi)={(ti,yl),…,(ti,yx)},x≥1.称G[hn]为G与hn=(Hi)i∈{0.1,…,n-1}的广义字典积,其中G[hn]的顶点集为V(G[hn])=Un-1i=0V(Hi),且两个顶点(ti,yp)与(tj,yq)相邻当且仅当ti=tj且(ti,yp)(ti,yq)∈E(Hi)或(ti,tj)∈E(G).关于G与hn=(Hi)i∈{0.1,…n-1}的广义字典积G[hn]的星全色数,我们得到了文中的两个重要结果.     

温控系统的时序Petri网建模与验证

基于时序Petri网对温控系统进行建模和性质描述.利用可达图、Büchi自动机和ω-正则表达式理论三者相结合的方法分析得到温控系统时序Petri网模型变迁引发序列集合的ω-正则表达式,进一步分析证明该ω-正则表达式满足温控系统的功能性需求说明,从形式上验证了温控系统时序Petri网模型与需求说明一致.结果表明,时序Petri网可用来描述和验证具有时序关系和因果关系的并发系统模型,是一种并发系统形式化描述和分析的有效工具.     

关于r-(P_0,…,P_(t-1))—泛圈图

若G中长为r+tj+i的圈恰好有Pi(0≤i≤t-1)个,其中r+tj+t-1≤n,j是P_0,…,P_(t-1)重复的次数,则称G为r-(P_0,…,P_(t-1))-泛圈图.主要采用构造法,给出当t=8时r-(P_0,…,P_7)-泛圈图的一些结果 .即设n≥14,≥6若2-3+-3≤n2-2+-2且n-(r_((n,)-1))=s(mod8),s=0,1,…,7时,那么存在一个n阶r-(4,4,4,4,5,5,5,5)泛圈图,其中r=r_(0, λ)+s=﹛2~(λ-4)+3+s,当n≤3·2~(λ-4)+2时n-2~(λ-3)+1+s当n3·2~(λ-4)+2时同时,利用类似的方法证明了r-(1,1,3,3,4,4,5,5)—泛圈图、r-(4,4,4,4,5,5,5,5)—奇(偶)泛圈图以及r-(1,1,3,3,4,4,5,5)奇(偶)泛圈图.进一步,给出相应圈长分布的最小可能边数.     

一类r-(d0,d1,…,dt-1)-泛圈图的结果

设r,t,j是正整数,若对每一个r+tj+i(r+tj+i≤n),n阶简单图G中长为r+tj+i的圈恰好有di个,0≤i≤t?1,其中t是di的周期数,j是t重复的次数,则称图G为r-(d0,…,dt?1)-泛圈图.主要讨论了r-(6?2μ1,6?2μ1,8?2μ1,6?2μ1)-泛圈图,r-(6?2μ1,8?2μ1,...     

长圈的邻域并条件的推广

本文证明了若G为一个k(k≥2)连通简单图,最小度为,δV(G)=n≥3,X 1,X 2,……,X k是顶点集合V的子集,X=X1∪X2∪…∪Xk,且对于Xi(i=1,2……k)中任意两个不相邻点u,v,都有N(u)∪N(v)≥n-δ,则X在G中可圈。并给出几个相关推论.     

与泛圈图有关的一些结果

设r,t,j是正整数,对于n阶哈密顿图G,若对每一个r+tj+i(r+tj+i≤n),G中长为r+i+j的圈恰好有di个,0≤i≤t-1,其中t是di的周期,j是t重复的次数,则称图G为r-(d0,…, dt-1)-泛圈图.本文讨论了r-(3,3,4,3,4,3,3,3)-泛圈图,r-(3,5,5,3)-奇(偶)泛圈图,以及g(0,0,6,…,6)的界.