|
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
e-mail: rafa.bastos12@gmail.com,{nam,rvr}@dcc.fc.up.pt,
September 2013
Abstract
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.
|