Path: utzoo!utgpu!news-server.csri.toronto.edu!bonnie.concordia.ca!uunet!mcsun!ukc!cam-cl!news
From: nmm@cl.cam.ac.uk (Nick Maclaren)
Newsgroups: comp.theory
Subject: Comparison of regular expressions
Message-ID: <1991Feb4.164723.12310@cl.cam.ac.uk>
Date: 4 Feb 91 16:47:23 GMT
Reply-To: nmm@cl.cam.ac.uk (Nick Maclaren)
Organization: U of Cambridge Comp Lab, UK
Lines: 28


I have a requirement to do the following:

    1) Test if two REs have a non-null intersection.

    2) Test if one RE is a superset of another.

Several books by various combinations of Aho, Hopcroft and Ullman give an
efficient algorithm for DFAs, but this is possibly exponential in the
size of the REs.  I need something that is much more efficient.

I have an algorithm for (1) that is O(A*B) in space and O((A*B)^2) in time
(where the REs are O(A) and O(B) respectively).  While I can modify this
to solve (2), it is both very messy and potentially slightly less efficient.
Please note that I am NOT interested in the intersection or difference;
I need just the answer yes or no.

If anyone can help with the following questions, I would be grateful:

    A) Is this a known, solved problem and, if so, where can I find a
reference?

    B) Is there a civilized and efficient algorithm to produce the
complement of a RE or NFA (I can use either form)?

Nick Maclaren
University of Cambridge Computer Laboratory
nmm@cl.cam.ac.uk