Fourth Annual IEEE Symposium on

Logic in Computer Science (LICS 1989)

Paper: Axiomatizing net computations and processes (at LICS 1989)

Authors: Degano, P. Meseguer, J. Montanari, U.


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


    author = 	 {Degano, P. and Meseguer, J. and Montanari, U.},
    title = 	 {Axiomatizing net computations and processes},
    booktitle =  {Proceedings of the Fourth Annual IEEE Symp. on Logic in Computer Science, {LICS} 1989},
    year =	 1989,
    editor =	 {Rohit Parikh},
    month =	 {June}, 
    pages =      {175--185},
    location =   {Pacific Grove, CA, USA}, 
    publisher =	 {IEEE Computer Society Press}