Technical Report: DCC-2013-11

Manipulation of Extended Regular Expressions with Derivatives

Rafaela Bastos, Nelma Moreira, Rogério Reis

DCC-FC & CMUP, Universidade do Porto
September 2013


The use of derivatives for efficiently deciding equivalence and membership in regular languages has been a major topic of recent research. To ensure termination, regular expressions must be considered modulo some algebraic properties such as associativity, commutativity, and idempotence of union (ACI). In this paper we describe an implementation of regular expressions modulo ACI and several derivative based methods within the FAdo system. Although regular languages are trivially closed for boolean operations, the manipulation of intersection and complementation with regular expressions or non-deterministic finite automata is non trivial and leads to an exponential blow up. However, due to several applications where extended regular expressions (\XRE) are used to represent information, it is important the extension of derivative based methods to those operations. Continuing work of Caron et al., we present new algorithms for computing the (extended) equation automaton and deciding membership and equivalence of \XRE using (partial) derivatives.