Path: utzoo!utgpu!news-server.csri.toronto.edu!cs.utexas.edu!usc!elroy.jpl.nasa.gov!sdd.hp.com!think.com!snorkelwacker.mit.edu!mit-eddie!uw-beaver!rice!helma.rice.edu!sabry
From: sabry@helma.rice.edu (Amr Sabry)
Newsgroups: comp.theory
Subject: Re: Comparison of regular expressions
Message-ID: <1991Feb5.193557.25431@rice.edu>
Date: 5 Feb 91 19:35:57 GMT
References: <1991Feb4.164723.12310@cl.cam.ac.uk>
Sender: news@rice.edu (News)
Reply-To: sabry@helma.rice.edu (Amr Sabry)
Organization: Rice University
Lines: 18

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.