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

[Sebastian Fischer]

>>> 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

     http://www.cs.rice.edu/~vardi/papers/sigcse06t1.pdf.gz

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  
equivalence.

Sebastian

-- 
Underestimating the novelty of the future is a time-honored tradition.
(D.G.)