<  Back to the Polytechnique Montréal portal

Maximal good step graph methods for reducing the generation of the state space

Hao Dou, Kamel Barkaoui, Hanifa Boucheneb, Xiaoning Jiang, Shouguang Wang

Article (2019)

Open Acess document in PolyPublie and at official publisher
Open Access to the full text of this document
Published Version
Terms of Use: Creative Commons Attribution
Download (1MB)
Show abstract
Hide abstract


This paper proposes an effective method based on the two main partial order techniques which are persistent sets and covering step graph techniques, to deal with the state explosion problem. First, we introduce a new definition of sound steps, the firing of which enables to extremely reduce the state space. Then, we propose a weaker sufficient condition about how to find the set of sound steps at each current marking. Next, we illustrate the relation between maximal sound steps and persistent sets, and propose a concept of good steps. Based on the maximal sound steps and good steps, a construction algorithm for generating a maximal good step graph (MGSG) of a Petri net (PN) is established. This algorithm first computes the maximal good step at each marking if there exists one, otherwise maximal sound steps are fired at the marking. Furthermore, we have proven that an MGSG can effectively preserve deadlocks of a Petri net. Finally, the change performance evaluation is made to demonstrate the superiority of our proposed method, compared with other related partial order techniques.

Uncontrolled Keywords

Petri nets, state explosion problem, covering step graph methods, persistent sets

Subjects: 2700 Information technology > 2706 Software engineering
Department: Department of Computer Engineering and Software Engineering
Research Center: Other
Funders: Zhejiang Provincial Key Research and Development Program of China
Grant number: 2018C01084
PolyPublie URL: https://publications.polymtl.ca/4849/
Journal Title: IEEE Access (vol. 7)
Publisher: IEEE
DOI: 10.1109/access.2019.2948986
Official URL: https://doi.org/10.1109/access.2019.2948986
Date Deposited: 12 May 2021 11:38
Last Modified: 11 Nov 2022 14:04
Cite in APA 7: Dou, H., Barkaoui, K., Boucheneb, H., Jiang, X., & Wang, S. (2019). Maximal good step graph methods for reducing the generation of the state space. IEEE Access, 7, 155805-155817. https://doi.org/10.1109/access.2019.2948986


Total downloads

Downloads per month in the last year

Origin of downloads


Repository Staff Only

View Item View Item