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.)
_______________________________________________
Haskell-Cafe mailing list
Haskell-Cafe@haskell.org
http://www.haskell.org/mailman/listinfo/haskell-cafe
