Beefy Boxes and Bandwidth Generously Provided by pair Networks
laziness, impatience, and hubris
 
PerlMonks  

Re: Halting problem? Sheesh, I hope not.

by demerphq (Chancellor)
on Jan 19, 2005 at 22:01 UTC ( [id://423520]=note: print w/replies, xml ) Need Help??


in reply to Halting problem? Sheesh, I hope not.
in thread Comparative satisfiability of regexps.

Well if it isnt the the halting problem exactly i suspect its damn near as hard. How about these two:

/aaaa(bc|bd|be|(b|b)(a(a(a(a)))|baba|aaaa)/ /aaaab?aaaa/

I suspects its a lot easier to show that regex E can produce something that regex R wont accept, but saying for sure that R will accept all patterns producable by E isnt so easy. And IMO neither are approachable problems at all. Id be thinking of alternate solutions. One possibility is to produce something that generates random data from the E pattern and then hammer the R pattern with the products to see but obviously this wont be a proof, just a strong argument.

/me wonders if he still has his data from regex code...

---
demerphq

Log In?
Username:
Password:

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

How do I use this?Last hourOther CB clients
Other Users?
Others perusing the Monastery: (5)
As of 2024-03-28 15:22 GMT
Sections?
Information?
Find Nodes?
Leftovers?
    Voting Booth?

    No recent polls found