nmm@cl.cam.ac.uk (Nick Maclaren) (02/05/91)
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.uksabry@helma.rice.edu (Amr Sabry) (02/06/91)
In article <1991Feb4.164723.12310@cl.cam.ac.uk>, nmm@cl.cam.ac.uk (Nick Maclaren) writes: |> |> 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. |> It is known that testing whether a regular expression is equal to $\Sigma^*$ is P-Space complete. Your second problem falls into this category (see Proof) so I would not try to find an efficient algorithm to solve it. Proof: Assume you have an efficient (polynomial time) algorithm $A$ to answer $r_1 \subseteq r_2$. I will use this algorithm to solve "Is $r = \Sigma^* ?" by asking whether $\Sigma^* \subseteq r$. So I can solve $r = \Sigma^*$ in polynomial time. A contradiction.