A Note on an Expressiveness Hierarchy for Multi-exit Iteration

Luca Aceto
Willem Jan Fokkink
Anna Ingólfsdóttir

September 2002


Multi-exit iteration is a generalization of the standard binary Kleene star operation that allows for the specification of agents that, up to bisimulation equivalence, are solutions of systems of recursion equations of the form

\begin{eqnarray*}X_1 & \stackrel{\mbox{\tiny def}}{=} & P_1 X_2 +
Q_1 \\ & \vdots & \\ X_n & \stackrel{\mbox{\tiny def}}{=} & P_n X_1 + Q_n

where $n$ is a positive integer, and the $P_i$ and the $Q_i$ are process terms. The addition of multi-exit iteration to Basic Process Algebra (BPA) yields a more expressive language than that obtained by augmenting BPA with the standard binary Kleene star. This note offers an expressiveness hierarchy, modulo bisimulation equivalence, for the family of multi-exit iteration operators proposed by Bergstra, Bethke and Ponse

Available as PostScript, PDF, DVI.


Last modified: 2003-06-08 by webmaster.