Maximal Conflict Set Enumeration Algorithm Based on Locality of Petri Nets

doi:10.3969/j.issn.0372-2112.2016.08.013

您当前的位置：

首页 >

文章列表页 >

Maximal Conflict Set Enumeration Algorithm Based on Locality of Petri Nets

更新时间：2025-07-08

- Maximal Conflict Set Enumeration Algorithm Based on Locality of Petri Nets
- Acta Electronica Sinica Vol. 44, Issue 8, Pages: 1858-1863(2016)
- 作者机构：
  
  1. 湖南理工学院信息与通信工程学院,湖南,岳阳,414006
  2. 华东理工大学信息科学与工程学院,上海,200237
  3. 江西省电力公司信息通信分公司,江西,南昌,330077
  4. 湖南理工学院信息与通信工程学院,湖南,岳阳,414006
  5. 华东理工大学信息科学与工程学院,上海,200237
  6. 江西省电力公司信息通信分公司,江西,南昌,330077
- 作者简介：
- 基金信息：
  
  National Natural Science Foundation of China (No.61473118);Research Fund of Education Department of Hunan Province (No.15A079);Science and Technology Project of Hunan Province (No.2014GK3026);Science and Technology Project of Jiangxi Electric Power Company (No.5218351400A1)
- DOI：10.3969/j.issn.0372-2112.2016.08.013
  CLC： TP301
- Published：2016
- 稿件说明：
移动端阅览
Maximal Conflict Set Enumeration Algorithm Based on Locality of Petri Nets[J]. Acta Electronica Sinica, 2016, 44(8): 1858-1863.
DOI：

Maximal Conflict Set Enumeration Algorithm Based on Locality of Petri Nets[J]. Acta Electronica Sinica, 2016, 44(8): 1858-1863. DOI： 10.3969/j.issn.0372-2112.2016.08.013.

摘要

冲突是Petri网研究的重要主题.目前Petri网冲突研究主要集中于冲突建模和冲突消解策略，而对冲突问题本身的计算复杂性却很少关注.提出Petri网的冲突集问题，并证明冲突集问题是NP（Non-deterministic Polynomial）完全的.提出极大冲突集动态枚举算法，该算法基于当前标识的所有极大冲突集，利用Petri网实施局部性，仅计算下一标识中受局部性影响的极大冲突集，从而避免重新枚举所有极大冲突集.该算法时间复杂度为

（

），

是当前标识的极大冲突集数目，

是变迁数.最后证明自由选择网、非对称选择网的极大冲突集枚举算法复杂度可降至

（

）.极大冲突集枚举算法研究将为Petri网冲突问题的算法求解提供理论参考.

Abstract

Conflict is an essential concept in Petri net theory.The existing research focuses on the modelling and resolution strategies of conflict problems

but less on the computational complexity of the problems theirselves.In this paper

we propose the conflict set problem for Petri nets

and prove that the conflict set problem is NP-complete.Furthermore

we present a dynamic algorithm for the maximal conflict set enumeration.Our algorithm only computes those conflict sets that are affected by local firing

which avoids enumerating all maximal conflict sets at each marking.The algorithm needs time O(m2n) where m is the number of maximal conflict sets at the current marking and n is the number of transitions.Finally

we show that the maximal conflict set enumeration problem can be solved in O(n2) for free-choice nets and asymmetric choice nets.The results on complexity of thel conflict set problem provide a theoretical reference for solving conflict problems of Petri nets.

关键词

Keywords

references

Views

下载量

CSCD

Alert me when the article has been cited

提交

Tools

Publicity Resources

Modeling and Analysis of Grid Computing Application Based Price Timed Petri Net

Method for Computing Performance of a Kind of Workflow Models Nested by Basic Model

Reachability Analysis Methods of E-Commerce Business Process Net

Process Similarity Algorithm Based on Weighted Flow Relationship

Related Author

LIU Wei-dong

SONG Jia-xing

LIN Chuang

TIAN Li-qin

LIN Chuang

YU Wang-yang

HUANG Zhao

FANG Xian-wen

Related Institution

Department of Computer Science and Technology, Tsinghua University

陕西师范大学现代教学技术教育部重点实验室

陕西师范大学计算机科学学院

同济大学嵌入式系统与服务计算教育部重点实验室

安徽理工大学理学院

⁰