Partial-order process algebra (and its relation to Petri nets)

To date, many different formalisms exist for describing and analyzing the behavior of concurrent systems. Petri nets and process algebras are two well-known classes of such formalisms. Petri-net theory is well suited for reasoning about concurrent systems in a partiaI-order framework; it handles causal relationships between actions of concurrent systems in an explicit way. Process algebras, on the other hand, often provide a total-order framework, which means that information about causalities is not always accurate. This chapter illustrates how to develop a partial-order process algebra in the style of ACP. It is shown how to extend such an algebraic theory with a causality mechanism inspired by Petri-net theory. In addition, the chapter clarifies the concepts of interleaving and non-interleaving process algebra; total-order semantics for concurrent systems are often incorrectly referred to as interleaving semantics.