From Many Places to Few: Automatic Abstraction Refinement for Petri Nets

Issue title: PETRI NETS 2007

Article type: Research Article

Authors: Ganty, Pierre | Raskin, Jean-François | Van Begin, Laurent

Affiliations: Département d'Informatique Université Libre de Bruxelles (U.L.B.), Belgium. pganty,jraskin,lvbegin@ulb.ac.be

Note: [] Address for correspondence: Département d'Informatique, Université Libre de Bruxelles (U.L.B.)

Abstract: Current algorithms for the automatic verification of Petri nets suffer from the explosion caused by the high dimensionality of the state spaces of practical examples. In this paper, we develop an abstract interpretation based analysis that reduces the dimensionality of state spaces that are explored during verification. In our approach, the dimensionality is reduced by trying to gather places that may not be important for the property to establish. If the abstraction that is obtained is too coarse, an automatic refinement is performed and a more precise abstraction is obtained. The refinement is computed by taking into account information about the inconclusive analysis. The process is iterated until the property is proved to be true or false.

Journal: Fundamenta Informaticae, vol. 88, no. 3, pp. 275-305, 2008