Re: Regexp Speed Concerns

Just a note: if memory serves, regexp equivalence is not an easy question in general and thats why the compiler is unlikely to give the exact same output.

That is, it is hard to say whether two regexps are equivalent.

(is it in NP? someone can surely fill up on that)

Comment on Re: Regexp Speed Concerns

Replies are listed 'Best First'.
Re: Regexp Speed Concerns by Dominus (Parson) on Jan 12, 2001 at 20:45 UTC
Says fundflow: if memory serves, regexp equivalence is not an easy question You are absolutely right. Very little is known about regexes. What little is known indicates that the problems are all very hard. (is it in NP? someone can surely fill up on that) It is probably not in NP, but nobody knows for sure. Regex inequivalence ("Given two regexes, do they represent different languages?") is known to be PSPACE-complete. PSPACE-complete problems are at least has hard as NP-complete problems, but probably harder. If the regexes contain only the concatenation and `\|` operators (no ``'s), the problem is "only" NP-complete. See (of course) Garey & Johnson Computers and Intractibility*, p. 267.	[reply]
Re: Regexp Speed Concerns by Dominus (Parson) on Jan 13, 2001 at 07:09 UTC
Here's an interesting development. A related problem which is PSPACE-complete is the problem: Given a regex R, is there any string that R will not match? Now, it's not known for sure that PSPACE-complete problems are intractible, although it's very likely. (And in particular, PSPACE-complete problems are at least as hard as NP-complete problems.) But here's the interesting part. Normally, in computer science, regex notations only include literal symbols, concatenation, `\|`, ``, and parenthese for grouping. If you extend thge regex notation to allow `{2}` as well, the problem becomes provably intractible* and can be shown to require an exponential amount of space.	[reply]