The Box Algebra 1/2: Refinement and Recursion

In the early days of parallel computing theory, Petri nets have been competing with process algebras for the attention of computer science theorists. These two models are distinguished by their inheritance: Petri nets stem from automata theory, and process algebras are abstractions from programming languages. As a consequence, while Petri nets cannot, in general, easily be constructed in a modular fashion out of small building blocks by well-defined syntactic rules, process-algebraic expressions can. Because both models feature concurrency (Petri nets implicitly, and process algebras explicitly, usually by an operation of parallel composition), multiple efforts have been underway ever since to find connections between them. This chapter and the next describe some key aspects of a particular one of these efforts (entitled the “box algebra”). This highlights, in a pars pro toto way, some issues (and limitations) that such efforts are likely to encounter. The present chapter concentrates on basic operations and on recursion, while the next chapter adds iteration and the treatment of data.