regular language - Determining whether a regex is a subset of another

Question

I have a large collection of regular expression that when matched call a particular http handler. Some of the older regex's are unreachable (e.g. a.c* ? abc*) and I'd like to prune them.

Is there a library that given two regex's will tell me if the second is subset of the first?

I wasn't sure this was decidable at first (it smelled like the halting problem by a different name). But it turns out it's decidable.

Answer 1

Trying to find the complexity of this problem lead me to this paper.

The formal definition of the problem can be found within: this is generally called the inclusion problem

The inclusion problem for R, is to test for two given expressions r, r′ ∈ R, whether r ? r′.

That paper has some great information (summary: all but the simplest expressions are fairly complex), however searching for information on the inclusion problem leads one directly back to StackOverflow. That answer already had a link to a paper describing a passable polynomial time algorithm which should cover a lot of common cases.