一种基于同步合成构造petri网进程表达式方法

《一种基于同步合成构造petri网进程表达式方法》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、-一种基于同步合成构造Petri网进程表达式的方法＊本课题得到国家自然科学基金(60603090和60673053)，山东省“泰山学者”专项基金和山东省自然优秀中青年科学家奖励基金(2006BS01019)的资助。曾庆田，男，1976年生，博士，副教授，研究兴趣包括：Petri网理论与应用、过程挖掘、本体与知识工程等，Email：qtzeng@sdust.edu.cn。曾庆田（山东科技大学信息科学与工程学院青岛266510）摘要Petri网的进程是用于系统行为和状态描述的有效工具，Petri网的进程表达式可以给出系统全部进程的描述，但是对于

2、任意无界Petri网而言求取其进程表达式十分困难。本文首先考察结构简单的S-网的进程行为，给出各种类型的S-网的进程表达式的描述方法。然后拓展了Petri网同步合成的概念，分析了同步合成过程中基本进程段集之间的关系，并利用同步混排给出了进程表达式之间的关系。随后证明了一个Petri网可以通过一组S-网同步合成得到，利用S-网的进程表达式给出了构造Petri网的进程表达式的方法。关键词Petri网，S-网，同步合成，同步混排，进程，进程表达式1引言进程是Petri网众多的分析方法中对系统行为描述和分析的最有力工具，因为进程将状态和变迁并重，把

3、系统中发生的变化和引起的状态改变如实记录下来，它可以很清楚地反映出网系统运行中的变迁之间的顺序、并发、同步等现象[1,2,3,4]。然而，一个进程只能反映Petri网的一种可能运行情况。一个Petri网往往有许多（可能无限多个）进程，可能无法一一列举。这就为利用进程分析Petri网的行为带来了许多困难。为此，国内外学者先后提出了P/R网[5]、进程网系统[6]、进程表达式[7,8,9]等理论和方法用于描述Petri网的进程行为。文[7]定义了有界Petri网的进程表达式并给出了具体求解方法。文[8]给出了无界公平Petri网的进程表达式的求

4、取方法。对于任意无界Petri网，需要首先建立其特征可达树求取基本进程段集，然后构造其进程网系统，将其进程描述问题转换成进程网系统的语言描述问题[6,9]。文[9]中给出了通过分解的方法描述进程网系统的语言行为的方法，从而给出原Petri网的进程表达式的求取方法。可见，结构复杂的Petri网进程描述是非常复杂的，目前所给出的方法和结果也仅限于进程行为的约束语义描述[6,7,8,9]。Petri网的同步合成是研究复杂系统的一种有效方法[10,11,12,13]，文[11]研究了同步合成网的进程特征，考察了Petri网同步合成过程中，基本进程语

5、言的合成关系，以及与之有关的线集、切集等性质。本文在文[11]已有的部分结果的基础上，对同步合成Petri网的进程特性进行更深入的研究。本文首先考察一类结构简单的Petri网—S-网的进程行为，给出各种类型的S-网的进程表达式的求取方法。为了适应大规模系统分析的需要，将Petri网同步合成的概念拓展到多个子网的情形，分析了同步合成过程中基本进程段集之间的关系，并利用同步混排运算给出了进程表达式之间的关系。证明了一个Petri网可以通过一组S-网同步合成得到，将求取Petri网进程表达式的问题转化成求取S-网的进程表达式问题。利用同步混排运算

6、，可以由S-网的进程表达式给出Petri网的进程表达式，由此给出利用同步合成构造Petri网的进程表达式的方法。本文第2节介绍了与本文讨论有关的Petri网进程的基本概念，第3节首先分析了S-网的进程特性并给出了S-网的进程表达式的求取方法。第4节拓展了Petri网同步合成的概念，并着重分析了同步合成过程中基本进程段之间以及进程表达式之间满足的关系。第5节证明了一个Petri网可以通过一组S-网同步合成得到，给出了Petri网进程表达式的求取方法。第6节给出了一个例子，并将本文的方法与已有的工作做了比较。2Petri网进程的基本概念本文假设

7、读者对Petri网及其进程的概念有所了解[1,2,3,4].---，这里只对与本文讨论有关的基本概念、术语和记号做一下简述或约定。为使定义尽量简洁，我们只讨论P/T网的进程，假定和。定义2.1.[1]设为一个网，如果：（1）；（2），则称为一个出现网，其中表示流关系的传递闭包。定义2.2.[1]设为一个网，为一个出现网，若映射满足：(1)；(2)；(3)；则称定义了到的一个映射，记为。定义2.3.[1]设为一个Petri网，为一个出现网，如果满足条件(1)若则：且；(2)；则称为的一个进程。为了讨论问题的方便，我们给出Petri网的满进程的

8、概念。所谓满进程是指其每个S-切都对应着Petri网的一个可达标识的那一类进程。定义2.4.[7]设为出现网到Petri网的一个网映射，如果：(1)：；(2)；则称为的一个满进程