R
Robert Inder
I'm interested in comparing the "coverage" of regular expressions.
In particular, if I have two regular expressions, I want to know
whether it is possible to construct a string that will match
both, or indeed that will match one and not the other.
So, for instance, suppose I believe that if an object has a
descripiton string matching regexp R1, it is of type A.
Someone now tells me that an object with a
descripiton string matching regexp R2 is of type B. What can I tell
about (the sets of things of type) A and B by looking at R1 and R2?
So if R1= "^a.*$" and R2 = "^b.*$", I know that A and B are disjoint.
Whereas if R1= "foo" and R2 = "foobar", I know that B is a subset of A.
But how do I formalise (i.e. program) this comparison process?
This strikes me as a very general problem/issue and there
just has to be some work on formalising and solving it. But I don't
know how to find it: Google searches for things like "regular
expression comparison" are swamped by algorithms for matching regexps
against strings and so forth, which isn't what I want.
Can anyone point me in the right direction?
Robert.
In particular, if I have two regular expressions, I want to know
whether it is possible to construct a string that will match
both, or indeed that will match one and not the other.
So, for instance, suppose I believe that if an object has a
descripiton string matching regexp R1, it is of type A.
Someone now tells me that an object with a
descripiton string matching regexp R2 is of type B. What can I tell
about (the sets of things of type) A and B by looking at R1 and R2?
So if R1= "^a.*$" and R2 = "^b.*$", I know that A and B are disjoint.
Whereas if R1= "foo" and R2 = "foobar", I know that B is a subset of A.
But how do I formalise (i.e. program) this comparison process?
This strikes me as a very general problem/issue and there
just has to be some work on formalising and solving it. But I don't
know how to find it: Google searches for things like "regular
expression comparison" are swamped by algorithms for matching regexps
against strings and so forth, which isn't what I want.
Can anyone point me in the right direction?
Robert.