Identifying Duplicates in Large Collections of Petri Nets and Nested-Unit Petri Nets

Pierre Bouvier and Hubert Garavel

Proceedings of the 45th International Conference on Application and Theory of Petri Nets and Concurrency (PETRI NETS'24), Genève, Switzerland, June 2024

Abstract:

We propose efficient techniques for detecting isomorphism between nets, i.e., for identifying, in large collections of (safe) Petri nets or Nested-Unit Petri Nets, all the nets that are identical modulo a permutation of places, a permutation of transitions, and/or a permutation of units. Our approach relies upon the successive application of diverse algorithms of increasing complexities: net signatures, net canonizations, and characterization of isomorphic nets in terms of isomorphic graphs. We implemented this approach in a complete tool chain that we successfully assessed on four collections, the largest of which comprises 241,000+ nets with many duplicates.

24 pages

PDF

PostScript

Slides of H. Garavel's lecture at the Petri Net 2024 conference

PDF