A Note on an Expressiveness Hierarchy for Multi-exit Iteration

Luca Aceto, Willem Jan Fokkink, Anna Ingólfsdóttir


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
X_1 = P_1 X_2 + Q_1

X_n = 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.

Full Text:


DOI: http://dx.doi.org/10.7146/brics.v9i40.21755
This website uses cookies to allow us to see how the site is used. The cookies cannot identify you or any content at your own computer.

ISSN: 0909-0878 

Hosted by the State and University Library and Aarhus University Library