|Perl: the Markov chain saw|
Comparative satisfiability of regexps.by Meowse (Beadle)
|on Jan 19, 2005 at 20:06 UTC||Need Help??|
Meowse has asked for the
wisdom of the Perl Monks concerning the following question:
This isn't exactly a Perl question, but Perl gurus do regexps better than anyone else I know, so I humbly request your wisdom.
The challenge: given two regexps A and B, determine (ideally in polynomial time) whether all strings that match A will also match B.
The motivation: to determine whether a process whose output is characterized by regexp A can guarantee to correctly drive a process whose input is characterized by regexp B.
The details: mildly crippled subsets of regexp are acceptable, if full-strength regexps make the problem computationally intractable or impossible. Execution time is not a huge issue; the regexps in question will be short, and the evaluation will be done at design time rather than at runtime (thus "ideally in polynomial time" above).