Open AccessA Note on an Expressiveness Hierarchy for Multi-exit Iteration
Author(s) -
Luca Aceto,
Willem Jan Fokkink,
Anna Ingólfsdóttir
Publication year - 2002
Publication title -
brics report series
Language(s) - English
Resource type - Journals
eISSN - 1601-5355
pISSN - 0909-0878
DOI - 10.7146/brics.v9i40.21755
Subject(s) - modulo , equivalence (formal languages) , mathematics , bisimulation , recursion (computer science) , integer (computer science) , star (game theory) , generalization , discrete mathematics , algebra over a field , pure mathematics , algorithm , computer science , programming language , mathematical analysis
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.