Operational Semantics for the Petri Box Calculus

The Petri Box Calculus (PBC), based on Milner’s CCS, has been developed to provide a compositional semantics of high level programming constructs in terms of a class of Petri nets with interfaces, called Petri Boxes. In this paper we present a structural operational semantics for Box expressions which provide the syntax for the PBC. We show that the use of equations in addition to action rules leads to a uniform theory consisting essentially of a single action rule, a set of context rules, and a set of equations. To capture what is basically the standard Petri net transition rule, we introduce an overbarring and underbarring technique which is related to that used in the event systems due to Boudol and Castellani. We define step sequence rules and show their consistency and completeness with respect to the counterparts from net theory. The results hold also for expressions involving unguarded recursion.