[comp.theory] Ineq. of reg. expr. with intersection

ajm@cs.brown.edu (Alain Mayer) (01/26/91)

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