PROCESS ALGEBRA WITH ITERATION AND NESTING

We introduce iteration in process algebra by means of (the original, b inary version of) Kleene's star operation: xy is the process that cho oses between x and y, and upon termination of x has this choice again. We add this operation to a whole range of process algebra axiom syste ms, starting from BPA (Basic Process Algebra). In the case of the most complex system under consideration, ACP(tau), every regular process c an be defined with handshaking (two-party communication) and auxiliary actions. Next we introduce nesting in process algebra: x(#)y is defin ed by the equation x(#)y = x(x(#)y)x+y. We show that and # are not i nterdefinable in most of the axiom systems we regard. The extension wi th #, and the extension with and # of the systems considered also gi ve a genuine hierarchy in expressivity. Finally, it is argued that eac h finitely branching, computable graph can be defined in ACP, extended with and #, and using handshaking and auxiliary actions.