|
|
||||||||
|
|||||||||
|
Technical Report: DCC-2007-07Testing the equivalence of regular expressionsMarco Almeida, Nelma Moreira, Rogério ReisDCC-FC, Universidade do PortoR. do Campo Alegre 1021/1055 , 4169-007 Porto, Portugal Phone: +351 220402919 , Fax: 351 22 402 950 E-mail: {mfa,nam,rvr}@fc.up.pt AbstractAntimirov and Mosses presented a rewrite system for deciding the equivalence of two (extended) regular expressions and argued that this method could lead to a better average-case algorithm than those based on the comparison of the equivalent minimal \dfas. In this paper we present a functional approach of a variant of that method, prove its correctness and give some experimental comparative results. Although being a refutation method, our preliminary results lead to the conclusion that indeed this method is feasible and it is, almost always, faster than the classical methods. |
||||||||
|