================================================================================
P9314b  J.A. Bergstra, I. Bethke & A. Ponse
        "Process algebra with iteration and nesting"
        (revised version of P9314)


ABSTRACT
We introduce iteration in process algebra by means of (the original,
binary version of) Kleene's star operation:  x * y is the process that
chooses 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
systems, starting from BPA. In the case of the most complex system
under consideration, ACP_\tau, every regular process can be defined
with handshaking (two-party communication) and auxiliary actions.

Next we introduce nesting in process algebra: x # y is defined by the
equation x # y = x(x # y)x + y. We show that  * and  # are not
interdefinable in most of the axiom systems we regard.  The extension
with  #, and the extension with  * and  # of the systems considered
also give a genuine hierarchy in expressivity. Finally, it is argued
that each finitely branching, computable graph can be defined in
ACP_\tau extended with  * and  #, and using handshaking and auxiliary
actions.



APPEARED AS

@article{P9314b,
        author =        {J.A. Bergstra and I. Bethke and A. Ponse},
        year =          {1994},
        journal =       {The Computer Journal},
        number =        {4},
        volume =        {37},
        pages =         {243--258},
        title =         {Process algebra with iteration and nesting}
}