A technique for generating the reduced reachability graph of petri net models

Farooq Ahmad; Hejiao Huang; Xiao Long Wang; Waqas Anwer

doi:10.1109/ICSMC.2008.4811863

A technique for generating the reduced reachability graph of petri net models

Farooq Ahmad^*
, Hejiao Huang
, Xiao Long Wang
, Waqas Anwer

^*Corresponding author for this work

Harbin Institute of Technology Shenzhen

Research output: Contribution to journal › Conference article › peer-review

4 Scopus citations

Abstract

The reachability graph technology is the basic and important method of analysis and verification of a system but it suffers from state explosion problem. To cope with this problem, this paper introduces transition vectors which can detect all the enabled transitions at given state of system and identify them as dependent or independent. Transition vectors have been found useful and functional for simultaneous execution of concurrently enabled transitions. An efficient algorithm based on transition vectors has been presented to generate the reduced reachability graph and compared with the reduced reachability graph constructed by stubborn set method.

Original language	English
Article number	4811863
Pages (from-to)	3636-3641
Number of pages	6
Journal	Conference Proceedings - IEEE International Conference on Systems, Man and Cybernetics
DOIs	https://doi.org/10.1109/ICSMC.2008.4811863
State	Published - 2008
Externally published	Yes
Event	2008 IEEE International Conference on Systems, Man and Cybernetics, SMC 2008 - Singapore, Singapore Duration: 12 Oct 2008 → 15 Oct 2008

Keywords

Concurrent enabling
Petri nets
Reachability graph
Transition vectors

Access to Document

10.1109/ICSMC.2008.4811863

Cite this

@article{35a155af1b0d459b8b18af0243df4a1e,

title = "A technique for generating the reduced reachability graph of petri net models",

abstract = "The reachability graph technology is the basic and important method of analysis and verification of a system but it suffers from state explosion problem. To cope with this problem, this paper introduces transition vectors which can detect all the enabled transitions at given state of system and identify them as dependent or independent. Transition vectors have been found useful and functional for simultaneous execution of concurrently enabled transitions. An efficient algorithm based on transition vectors has been presented to generate the reduced reachability graph and compared with the reduced reachability graph constructed by stubborn set method.",

keywords = "Concurrent enabling, Petri nets, Reachability graph, Transition vectors",

author = "Farooq Ahmad and Hejiao Huang and Wang, \{Xiao Long\} and Waqas Anwer",

year = "2008",

doi = "10.1109/ICSMC.2008.4811863",

language = "英语",

pages = "3636--3641",

journal = "Conference Proceedings - IEEE International Conference on Systems, Man and Cybernetics",

issn = "1062-922X",

publisher = "Institute of Electrical and Electronics Engineers Inc.",

note = "2008 IEEE International Conference on Systems, Man and Cybernetics, SMC 2008 ; Conference date: 12-10-2008 Through 15-10-2008",

}

TY - JOUR

T1 - A technique for generating the reduced reachability graph of petri net models

AU - Ahmad, Farooq

AU - Huang, Hejiao

AU - Wang, Xiao Long

AU - Anwer, Waqas

PY - 2008

Y1 - 2008

N2 - The reachability graph technology is the basic and important method of analysis and verification of a system but it suffers from state explosion problem. To cope with this problem, this paper introduces transition vectors which can detect all the enabled transitions at given state of system and identify them as dependent or independent. Transition vectors have been found useful and functional for simultaneous execution of concurrently enabled transitions. An efficient algorithm based on transition vectors has been presented to generate the reduced reachability graph and compared with the reduced reachability graph constructed by stubborn set method.

AB - The reachability graph technology is the basic and important method of analysis and verification of a system but it suffers from state explosion problem. To cope with this problem, this paper introduces transition vectors which can detect all the enabled transitions at given state of system and identify them as dependent or independent. Transition vectors have been found useful and functional for simultaneous execution of concurrently enabled transitions. An efficient algorithm based on transition vectors has been presented to generate the reduced reachability graph and compared with the reduced reachability graph constructed by stubborn set method.

KW - Concurrent enabling

KW - Petri nets

KW - Reachability graph

KW - Transition vectors

UR - https://www.scopus.com/pages/publications/69949139036

U2 - 10.1109/ICSMC.2008.4811863

DO - 10.1109/ICSMC.2008.4811863

M3 - 会议文章

AN - SCOPUS:69949139036

SN - 1062-922X

SP - 3636

EP - 3641

JO - Conference Proceedings - IEEE International Conference on Systems, Man and Cybernetics

JF - Conference Proceedings - IEEE International Conference on Systems, Man and Cybernetics

M1 - 4811863

T2 - 2008 IEEE International Conference on Systems, Man and Cybernetics, SMC 2008

Y2 - 12 October 2008 through 15 October 2008

ER -

A technique for generating the reduced reachability graph of petri net models

Abstract

Keywords

Access to Document

Other files and links

Fingerprint

Cite this