Axiomatizing net computations and processes
Pierpaolo Degano, José Meseguer, Ugo Montanari · 2003
An algebraic axiomatization is proposed, where, given a net N, a term algebra P(N) with two operations of parallel and sequential composition is defined. The congruence classes generated by a few simple axioms are proved isomorphic to a slight refinement of classical processes. Actually, P(N) is a symmetric monoidal category, parallel composition is the monoidal operation on morphisms and sequential composition is morphism composition. Besides P(N), the authors introduce a category S(N) containing the classical occurrence and step sequences. The term algebras of P(N) and S(N) are in general incomparable, and thus they introduce two more categories, K(N) and T(N), providing a most concrete and a most abstract extremum, respectively. The morphisms of T(N) are proved isomorphic to the processes recently defined in terms of the swap transformation by E. Best and R. Devillers (Theor. Comput. Sci., vol.55, pp.87-136, 1987). Thus the diamond of the four categories gives a full account in algebraic terms of the relations between interleaving and partial ordering observations of place/transition net computations.>