A Note on an Expressiveness Hierarchy for Multi-exit Iteration

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 \end{eqnarray*}$

where

is a positive integer, and the

and the

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

Abstract: