A survey of petri nets slicing

Yasir Imtiaz Khan; Alexandros Konios; Nicolas Guelfi

doi:10.1145/3241736

A survey of petri nets slicing

Yasir Imtiaz Khan, Alexandros Konios, Nicolas Guelfi

University of Luxembourg

Research output: Contribution to journal › Article › peer-review

6 Citations (Scopus)

137 Downloads (Pure)

Abstract

Petri nets slicing is a technique that aims to improve the verification of systems modeled in Petri nets. Petri nets slicing was first developed to facilitate debugging, but then was used for the alleviation of the state space explosion problem for the model checking of Petri nets. In this article, different slicing techniques are studied along with their algorithms introducing: (i) a classification of Petri nets slicing algorithms based on their construction methodology and objective (such as improving state space analysis or testing); (ii) a qualitative and quantitative discussion and comparison of major differences such as accuracy and efficiency: (iii) a syntactic unification of slicing algorithms that improve state space analysis for easy and clear understanding; and (iv) applications of slicing for multiple perspectives. Furthermore, some recent improvements to slicing algorithms are presented, which can certainly reduce the slice size even for strongly connected nets. A noteworthy use of this survey is for the selection and improvement of slicing techniques for optimizing the verification of state event models.

Original language	English
Article number	109
Number of pages	26
Journal	ACM Computing Surveys (CSUR)
Volume	51
Issue number	5
DOIs	https://doi.org/10.1145/3241736
Publication status	Published - 23 Jan 2019

Bibliographical note

© ACM, 2018. This is the author's version of the work. It is posted here by permission of ACM for your personal use. Not for redistribution. The definitive version was published in ACM Computing Surveys (CSUR), [VOL 51, ISS 5], (December 2018) http://doi.acm.org/10.1145/3241736

Copyright © and Moral Rights are retained by the author(s) and/ or other copyright owners. A copy can be downloaded for personal non-commercial research or study, without prior permission or charge. This item cannot be reproduced or quoted extensively from without first obtaining permission in writing from the copyright holder(s). The content must not be changed in any way or sold commercially in any format or medium without the formal permission of the copyright holders.

Keywords

Model checking
Petri nets
Slicing
Testing

ASJC Scopus subject areas

Theoretical Computer Science
General Computer Science

Access to Document

10.1145/3241736

Post-PrintAccepted author manuscript, 731 KBLicence: Unspecified

Cite this

@article{d758b0c3f1d841b1b9ec1d8984c4e5ba,

title = "A survey of petri nets slicing",

abstract = "Petri nets slicing is a technique that aims to improve the verification of systems modeled in Petri nets. Petri nets slicing was first developed to facilitate debugging, but then was used for the alleviation of the state space explosion problem for the model checking of Petri nets. In this article, different slicing techniques are studied along with their algorithms introducing: (i) a classification of Petri nets slicing algorithms based on their construction methodology and objective (such as improving state space analysis or testing); (ii) a qualitative and quantitative discussion and comparison of major differences such as accuracy and efficiency: (iii) a syntactic unification of slicing algorithms that improve state space analysis for easy and clear understanding; and (iv) applications of slicing for multiple perspectives. Furthermore, some recent improvements to slicing algorithms are presented, which can certainly reduce the slice size even for strongly connected nets. A noteworthy use of this survey is for the selection and improvement of slicing techniques for optimizing the verification of state event models.",

keywords = "Model checking, Petri nets, Slicing, Testing",

author = "Khan, {Yasir Imtiaz} and Alexandros Konios and Nicolas Guelfi",

note = "{\textcopyright} ACM, 2018. This is the author's version of the work. It is posted here by permission of ACM for your personal use. Not for redistribution. The definitive version was published in ACM Computing Surveys (CSUR), [VOL 51, ISS 5], (December 2018) http://doi.acm.org/10.1145/3241736 Copyright {\textcopyright} and Moral Rights are retained by the author(s) and/ or other copyright owners. A copy can be downloaded for personal non-commercial research or study, without prior permission or charge. This item cannot be reproduced or quoted extensively from without first obtaining permission in writing from the copyright holder(s). The content must not be changed in any way or sold commercially in any format or medium without the formal permission of the copyright holders. ",

year = "2019",

month = jan,

day = "23",

doi = "10.1145/3241736",

language = "English",

volume = "51",

journal = "ACM Computing Surveys (CSUR)",

issn = "0360-0300",

publisher = "ACM",

number = "5",

}

TY - JOUR

T1 - A survey of petri nets slicing

AU - Khan, Yasir Imtiaz

AU - Konios, Alexandros

AU - Guelfi, Nicolas

N1 - © ACM, 2018. This is the author's version of the work. It is posted here by permission of ACM for your personal use. Not for redistribution. The definitive version was published in ACM Computing Surveys (CSUR), [VOL 51, ISS 5], (December 2018) http://doi.acm.org/10.1145/3241736 Copyright © and Moral Rights are retained by the author(s) and/ or other copyright owners. A copy can be downloaded for personal non-commercial research or study, without prior permission or charge. This item cannot be reproduced or quoted extensively from without first obtaining permission in writing from the copyright holder(s). The content must not be changed in any way or sold commercially in any format or medium without the formal permission of the copyright holders.

PY - 2019/1/23

Y1 - 2019/1/23

N2 - Petri nets slicing is a technique that aims to improve the verification of systems modeled in Petri nets. Petri nets slicing was first developed to facilitate debugging, but then was used for the alleviation of the state space explosion problem for the model checking of Petri nets. In this article, different slicing techniques are studied along with their algorithms introducing: (i) a classification of Petri nets slicing algorithms based on their construction methodology and objective (such as improving state space analysis or testing); (ii) a qualitative and quantitative discussion and comparison of major differences such as accuracy and efficiency: (iii) a syntactic unification of slicing algorithms that improve state space analysis for easy and clear understanding; and (iv) applications of slicing for multiple perspectives. Furthermore, some recent improvements to slicing algorithms are presented, which can certainly reduce the slice size even for strongly connected nets. A noteworthy use of this survey is for the selection and improvement of slicing techniques for optimizing the verification of state event models.

AB - Petri nets slicing is a technique that aims to improve the verification of systems modeled in Petri nets. Petri nets slicing was first developed to facilitate debugging, but then was used for the alleviation of the state space explosion problem for the model checking of Petri nets. In this article, different slicing techniques are studied along with their algorithms introducing: (i) a classification of Petri nets slicing algorithms based on their construction methodology and objective (such as improving state space analysis or testing); (ii) a qualitative and quantitative discussion and comparison of major differences such as accuracy and efficiency: (iii) a syntactic unification of slicing algorithms that improve state space analysis for easy and clear understanding; and (iv) applications of slicing for multiple perspectives. Furthermore, some recent improvements to slicing algorithms are presented, which can certainly reduce the slice size even for strongly connected nets. A noteworthy use of this survey is for the selection and improvement of slicing techniques for optimizing the verification of state event models.

KW - Model checking

KW - Petri nets

KW - Slicing

KW - Testing

UR - http://www.scopus.com/inward/record.url?scp=85061455838&partnerID=8YFLogxK

U2 - 10.1145/3241736

DO - 10.1145/3241736

M3 - Article

SN - 0360-0300

VL - 51

JO - ACM Computing Surveys (CSUR)

JF - ACM Computing Surveys (CSUR)

IS - 5

M1 - 109

ER -

A survey of petri nets slicing

Abstract

Bibliographical note

Keywords

ASJC Scopus subject areas

Access to Document

Other files and links

Fingerprint

Cite this