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

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.