Given a set of regexps and given a wanted logical concatenation (lets start with AND,OR) of
these regexps, is there any mechanism to create a smaller, more eficient set of regexps that will have the same effect?
Very unlikely given the power of Perl regular expressions.
One of the questions that you would need to answer is whether
two grammars (I use grammar here instead of regular expression
to avoid confusion later on) are equivalent; that is, whether
the will match the same language (where a language is the set
of all strings matched by a grammar). For regular expressions
(not Perl regular expressions, but for traditional ones) this
question is decidable. But for more powerful grammars on the
Chomsky hierarchy, this question is undecidable.
However, Perl regular expressions are hard to place on the
Chomsky hierarchy. Without (?{ }) or (??{ }),
Perl regular expressions cannot be used to create all context
free grammars (take the language of strings with balanced parenthesis
for instance). On the other hand, it can be used to create
grammars that are context sensitive on the Chomsky hierarchy.
(With (?{ }) it could very well be that Perl
regular expressions are at least as powerful as context free
grammars, but I don't see an obvious proof.)
My guts say that such a mechanism does not exist, that the
problem is unsolvable. If the problem is solvable, it's
going to be incredibly hard.
Abigail