Re: Regexp Speed Concerns

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.

Comment on Re: Regexp Speed Concerns

Replies are listed 'Best First'.
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]

Replies are listed 'Best First'.

Re: Regexp Speed Concerns
by Dominus (Parson) on Jan 13, 2001 at 07:09 UTC

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]