佩特里网

✍ dations ◷ 2025-08-08 20:30:33 #并行流计算,计算模型,图表,建模语言

佩特里网(英语:Petri net),又译为裴氏网、派翠网络,是对离散并行系统的数学表示。佩特里网属于离散事件动态系统,是1960年代由卡尔·亚当·佩特里发明的,适合于描述异步的、并发的计算机系统模型。佩特里网既有严格的数学表述方式,也有直观的图形表达方式。

由于佩特里网能表达并发的事件,被认为是自动化理论的一种。研究领域趋向认为佩特里网是所有流程定义语言之母。

卡尔·亚当·佩特里是一名物理学家,他发明佩特里网主要是从物理的角度去描述并发现象的。据佩特里本人所述,他认为60年代计算机科学的概念构架由于缺乏并发不适合于描述物理系统。其中一个重要的概念,就是佩特里网里面不存在所谓的“全局时间”的概念,因为这跟狭义相对论是冲突的。相反,佩特里网可以描述每一个节点的时序。

从狭义相对论的观点出发,两个时空点之间如果没有因果关系把它们连接起来(或者说“类空”的),它们就是独立的,不能说其中一个发生在前另一个在后或者相反。因此,佩特里网里面的两种变迁(见下文)如果都有发生的条件,则不能认为其执行顺序有任何关系。然而,佩特里网旨在描述变迁之间的因果关系,并由此构造时序。

经典的佩特里网是简单的过程模型,由两种节点:库所和变迁,有向弧,以及令牌等元素组成的。

PetriNet.JPG

佩特里网的元素:

佩特里网的规则是:

如果一个变迁的每个输入库所(input place)都拥有数量足够的令牌时,该变迁即为被允许(enable)。一个变迁被允许时,变迁将发生(fire),输入库所(input place)的令牌被消耗,同时为输出库所(output place)产生令牌。

注意:

两个变迁争夺一个令牌的情形被称之为冲突。当发生冲突的时候,由于佩特里网的时序是不确定的,因此具体哪个变迁得以发生也是不确定的。实际应用中,往往需要避免这种情形。用于描述现象的佩特里网也可能自然出现冲突,这表明我们对于变迁发生的条件没有完全了解。

多个弧连接两个节点的情况。在输入库所和变迁之间的弧的个数决定了该变迁变为被允许需要的令牌的个数。弧的个数决定了消耗/产生的令牌的个数。

一个经典的佩特里网由四元组(库所,变迁,输入函数,输出函数)组成。任何图都可以映射到这样一个四元组上,反之亦然。

被允许的形式化 变迁发生的形式化佩特里网 到变迁系统的映射 可达性图

佩特里网是一个三元组(P,T,F)

F(P X T)U(T X P)是弧的集合

一个流程的状态是由在场所中的令牌建模的,状态的变迁是由变迁建模的。令牌表示事物(人,货物,机器),信息,条件,或对象的状态;库所代表库所,通道或地理位置;变迁代表事件,转化或运输

一个流程(Flow)有当前状态,可达状态,不可达状态。

为了压缩经典佩特里网中的重复结构,提高佩特里网的建模能力,高级佩特里网应运而生。高级佩特里网包括有色佩特里网和谓词/变迁系统。这类网系统的特点是通过折叠来减少网的网元,压缩网的规模。

一个有色的令牌(托肯)通常代表具有一个可以标识的对象,从而避免相同网络结构的重复建模,如一个令牌可以取值“令牌A”,另一个令牌取值“令牌B”。当有色令牌的标识符取值(颜色)可以使用复杂的复合类型时,因此令牌拥有取值(颜色)代表由令牌建模的对象的具体特征,如一个令牌代表一个工人(张三,28岁,经验3级)。


为了扩展佩特里网的建模能力,很多研究学者在多个方面对Petri网进行了扩展:

为了进行分析,我们需要建模期间,延迟等,因此可以为每一个令牌附加一个时间戳,由变迁决定生产出的令牌的延迟。常用的时间佩特里网可分为Timed Petri Net 和 Time Petri Net。

增加时序逻辑的定义,更好的描述行为过程。

构造一个复杂性与数据流图相当的佩特里网的机制。层次佩特里网是由库所,变迁和子网构成的网络。佩特里网的层次化具有多种实现形式,例如高层次佩特里网中的一个变迁可以代表一个子佩特里网。


相关

  • 鸟虫书陶文 ‧ 甲骨文 ‧ 金文 ‧ 古文 ‧ 石鼓文籀文 ‧ 鸟虫书 ‧ 篆书(大篆 ‧  小篆)隶书 ‧ 楷书 ‧ 行书 ‧ 草书漆书 ‧  书法 ‧ 飞白书笔画 ‧ 
  • 牙列齿列(亦作牙列、齿系、牙系)指的是动物口腔中全套牙齿的发育和排列模式。除单孔目、贫齿目、穿山甲属和鲸目以外,所有哺乳动物都具备四种类型的牙齿,而且每一类型的牙齿,与物种相
  • 加拉巴哥象龟C. n. nigra (指名亚种)C. n. abingdoniC. n. beckiC. n. chathamensisC. n. darwiniC. n. duncanensisC. n. hoodensisC. n. phantasticaC. n. porteriC. n. vicinaChelono
  • 火山矽肺病超微粒硅酸盐尘埃沉着症(英语:Pneumonoultramicroscopicsilicovolcanoconiosis),简称火山矽肺病,是肺尘病的一种。矽肺病越来越多地成为许多行业的关键健康话题,因为其职业原因已
  • 孟子 (书)四配 颜回 · 孟子 · 曾参 · 孔伋日本 藤原惺窝 · 林罗山 · 室鸠巢 新井白石 · 雨森芳洲朝鲜 薛聪 · 权近 · 吉再 · 安珦 · 李穑 李滉 · 王仁 · 李
  • 仲昌仲昌(?-1459年),字显夫,南京应天府溧阳(今江苏溧阳市)人,明朝政治人物、进士出身。永乐二年,登进士,担任安平县、泗水县知县,后升任刑部主事、刑部郎中,官至南京太仆寺卿。
  • 曼彻斯特轻铁曼彻斯特轻铁(英语:Manchester Metrolink)为英国大曼彻斯特郡的轻轨电车,以曼彻斯特市中心为中心,开往奥尔特灵厄姆、阿什顿安德莱恩、伯里、Didsbury、Eccles、曼彻斯特机场和罗
  • 郑瑞郑瑞为中国清朝武官官员,本籍浙江。1782年(乾隆47年)奉旨接任张继勋担任台湾镇总兵。是台湾清治时期此期间,受台湾道制约的台湾地区最高军事首长。翌年,因无法制止漳泉分类械斗,被
  • 卡尔利亚斯塞里卡尔利亚斯塞里(Kalliasseri),是印度喀拉拉邦Kannur县的一个城镇。总人口28066(2001年)。该地2001年总人口28066人,其中男性13247人,女性14819人;0—6岁人口2824人,其中男1454人,女137
  • 巴塔拉巴塔拉(Batala),是印度旁遮普邦Gurdaspur县的一个城镇。总人口126646(2001年)。该地2001年总人口126646人,其中男性67026人,女性59620人;0—6岁人口14272人,其中男8109人,女6163人;识字