An Equational Axiomatization for Multi-Exit Iteration

Authors

  • Luca Aceto
  • Willem Jan Fokkink

DOI:

https://doi.org/10.7146/brics.v3i22.19985

Abstract

This paper presents an equational axiomatization of bisimulation equivalence over the language of Basic Process Algebra (BPA) with 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

X1 = P1 X2 + Q1
...
Xn = Pn X1 + Qn

where n is a positive integer, and the Pi and the Qi are process terms. The addition
of multi-exit iteration to BPA yields a more expressive language than that obtained by augmenting BPA with the standard binary Kleene star (BPA). As a
consequence, the proof of completeness of the proposed equational axiomatization
for this language, although standard in its general structure, is much more involved
than that for BPA. An expressiveness hierarchy for the family of k-exit iteration operators proposed by Bergstra, Bethke and Ponse is also offered.

 

Downloads

Published

1996-01-22

How to Cite

Aceto, L., & Fokkink, W. J. (1996). An Equational Axiomatization for Multi-Exit Iteration. BRICS Report Series, 3(22). https://doi.org/10.7146/brics.v3i22.19985