Path: utzoo!utgpu!news-server.csri.toronto.edu!cs.utexas.edu!uunet!brunix!ajm
From: ajm@cs.brown.edu (Alain Mayer)
Newsgroups: comp.theory
Subject: Ineq. of reg. expr. with intersection
Message-ID: <62539@brunix.UUCP>
Date: 25 Jan 91 18:33:35 GMT
Sender: news@brunix.UUCP
Reply-To: ajm@cs.brown.edu (Alain Mayer)
Organization: Brown University Department of Computer Science
Lines: 21


Hi,
I am interested in the inequivalence problem for regular expression
with intersection, or, formally in the language:

  L = { (E1, E2) / E1, E2 are r.e. with intersection, L(E1) \= L(E2) }

I would like to know membership and hardness of L wrt to a complexity
class.

In "Design and Analysis of Computer Algorithms" by Aho, Hopcroft, and Ullman 
it is only shown (pp 410 - 419) that any algorithm needs exponential space io, 
but it is not a hardness proof.  


Thanks in advance,

Alain Mayer (ajm@cs.brown.edu)
Dept of Computer Science
Brown University
Providence, RI 02912