<  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 and Shouguang Wang

Article (2019)

Published Version
Terms of Use: Creative Commons Attribution .
Download (7MB)
Cite this document: 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, p. 155805-155817. doi:10.1109/access.2019.2948986
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

Open Access document in PolyPublie
Subjects: 2700 Technologie de l'information > 2706 Génie logiciel
Department: Département de génie informatique et génie logiciel
Research Center: Autre
Funders: Zhejiang Provincial Key Research and Development Program of China
Grant number: 2018C01084
Date Deposited: 12 May 2021 11:38
Last Modified: 13 May 2021 01:20
PolyPublie URL: https://publications.polymtl.ca/4849/
Document issued by the official publisher
Journal Title: IEEE Access (vol. 7)
Publisher: IEEE
Official URL: https://doi.org/10.1109/access.2019.2948986


Total downloads

Downloads per month in the last year

Origin of downloads


Repository Staff Only