We provide a finite equational axiomatization for bisimulation equivalence of nondeterministic interpretation of regular expressions. Our axiomatization is heavily based on the one by Salomaa, that provided an implicative axiomatization for a large subset of regular expressions, namely all those that satisfy the non-empty word property (i.e. without 1 summands at the top level) in *-contexts. Our restriction is similar, it essentially amounts to recursively requiring that the non-empty word property be satisfied not just at top level but at any depth. We also discuss the impact on the axiomatization of different interpretations of the 0 term, interpreted either as a null process or as a deadlock.
An equational axiomatization of bisimulation over regular expressions / F., Corradini; R., De Nicola; Labella, Anna. - In: JOURNAL OF LOGIC AND COMPUTATION. - ISSN 0955-792X. - STAMPA. - 12:2(2002), pp. 301-320. (Intervento presentato al convegno Meeting on Fixed Points in Computer Science (FICS 2000) tenutosi a PARIS, FRANCE nel JUL 22-23, 2000) [10.1093/logcom/12.2.301].
An equational axiomatization of bisimulation over regular expressions
LABELLA, Anna
2002
Abstract
We provide a finite equational axiomatization for bisimulation equivalence of nondeterministic interpretation of regular expressions. Our axiomatization is heavily based on the one by Salomaa, that provided an implicative axiomatization for a large subset of regular expressions, namely all those that satisfy the non-empty word property (i.e. without 1 summands at the top level) in *-contexts. Our restriction is similar, it essentially amounts to recursively requiring that the non-empty word property be satisfied not just at top level but at any depth. We also discuss the impact on the axiomatization of different interpretations of the 0 term, interpreted either as a null process or as a deadlock.I documenti in IRIS sono protetti da copyright e tutti i diritti sono riservati, salvo diversa indicazione.
