[Haskell-cafe] Re: ANN: weighted-regexp-

Sebastian Fischer sebf at informatik.uni-kiel.de
Wed Jul 28 11:41:27 EDT 2010

>>> Oh, by the way, with noMatch, eps, alt and seq_ RegExp is itself a
>>> Semiring,
>> Yes, but it's hard to define an Eq instance for arbitrary regular
>> expressions that reflects equivalence of regexps.
> How hard is this exactly?

The standard algorithm to decide regexp equivalence transforms both  
expressions into DFAs and checks whether they are equivalent. DFAs can  
be checked for equivalence by forming their in-equivalence-product and  
checking whether the result DFA does not accept any input. See


This algorithm is quadratic in the sizes of the DFAs but they can  
themselves be exponentially large in the sizes of the regexps.

I don't know whether there is more efficient way to decide regexp  


Underestimating the novelty of the future is a time-honored tradition.

More information about the Haskell-Cafe mailing list