Revisiting the Algebra of Petri Net Processes under the Collective Token Philosophy

Abstract

Revisiting the view of "Petri nets as monoids" suggested by Meseguer and Montanari, we give a direct proof of the well-known result that the class of Best/Devillers processes, which represents the behavior of Petri nets under the collective token semantics, has a sound and complete axiomatization in terms of symmetric monoidal categories. Using membership equational logic for the axiomatization, we prove the result by an explicit construction of a natural isomorphism between suitable functors. Our interest in the collective token semantics is motivated by earlier work on the use of rewriting logic as a uniform framework for different Petri net classes, especially including high-level Petri nets, where individuality of tokens can be already expressed at the system level.