Programming Research Group  -  University of Amsterdam  -  TR P9808


   Two Recursive Generalizations of Iteration in Process Algebra

			  Jan A. Bergstra
			    Alban Ponse


The process  algebraic  framework ACP with  abstraction  is extended
with two  recursive  generalizations  of  iteration:  the  push-down
operation  $, defined by x $ y= x(x $ y)(x $ y) + y, and the nesting
operation  #,  defined  by x # y=  x(x  #  y)x  + y.  With  help  of
auxiliary actions, handshaking  communication on these, and one of $
or #  we  provide  simple  definitions  of  the  following  standard
processes:  stack,  context-free   process,  bag,  and  queue.  This
supports  the  equational  founding  of  process  algebra:  standard
processes can be represented as terms.

Key  words  &  Phrases:  Concurrency,  process  algebra,  iteration,
Kleene star, nesting operation, push-down operation, expressivity.