Structural Petri Net Equivalence
An equivalence relation, called structural bisimilarity, is given for
labeled Place-Transition nets.
In contrast to behavioral bisimilarity of nets, this equivalence only depends
upon the structure of the nets considered, that is, their places and
transitions and the way these are connected.
It does not involve any conversion to transition systems.
Algorithms are given for reducing a net to its normal form and deciding whether
two given nets are bisimilar.
The paper concludes by giving a behavioral characterization of structural net
bisimilarity. A given net induces an ordered process space by considering
markings as states, steps as transitions and bag inclusion as the partial
ordering. Structural bisimilarity of nets is
equivalent to order-preserving (noninterleaving) bisimilarity of their induced
process spaces.
The ideas and algorithms are similar to Autant/Schnoebelen: Place Bisimulations in Petri Nets, Proceedings ATPN '92, LNCS 616. pp 45-61.