Beefy Boxes and Bandwidth Generously Provided by pair Networks
Perl-Sensitive Sunglasses
 
PerlMonks  

Re: Regexp Speed Concerns

by fundflow (Chaplain)
on Jan 12, 2001 at 07:28 UTC ( [id://51287]=note: print w/replies, xml ) Need Help??


in reply to 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)

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.

      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.

Log In?
Username:
Password:

What's my password?
Create A New User
Domain Nodelet?
Node Status?
node history
Node Type: note [id://51287]
help
Chatterbox?
and the web crawler heard nothing...

How do I use this?Last hourOther CB clients
Other Users?
Others sharing their wisdom with the Monastery: (11)
As of 2024-03-28 09:37 GMT
Sections?
Information?
Find Nodes?
Leftovers?
    Voting Booth?

    No recent polls found