Comparing two Regex *Patterns*

Hi,

for an XSLT-based up-translation engine that I'm writing, I
am using ORO matcher. Works very well (and better than the
other two options), thanks!

Now I wonder about the following and wanted some input from
experts on theory of regular expressions and their compilers
and matchers: is there some algebraic way of comparing two
regex patterns (not a string with a pattern, but two patterns.)
The point is to figure out if one pattern is (partially)
contained in another pattern and if strings matched by one
pattern are also matched by another pattern (i.e. the set
of strings mathing pattern 2 is a subset of the set of
strings matching pattern 1.) The use case for this is to
find ambiguities between rules using such related patterns
such that one can test these patterns in groups (or, for
XSLT, assign higher priority to the more specific pattern.)
The point is that the computer should make this analysis
not the guy who defines a transformation using many regexes.

Generally evaluating such similarity relationships could be
fairly involved. But I think this question should be part of
any theoretical discussion of regexes, and if anyone knows
of some information about this please holler. Actually I am
just now searching through the Annals of the ACM and there
are a few pertinent articles that feel like this is a hard
problem. Anyone knows of any implementations of any of this?
Do people here feel that comparison operations between Patterns
would be a good addition to ORO (if it is feasible)?

thanks,
-Gunther Schadow

PS: I would appreciate if you could put my personal email
address on your replies. Thanks.



-- 
Gunther Schadow, M.D., Ph.D.                    [email protected]
Medical Information Scientist      Regenstrief Institute for Health Care
Adjunct Assistant Professor        Indiana University School of Medicine
tel:1(317)630-7960                         http://aurora.regenstrief.org