complexity of equivalence of two star-free regular expressions

Question

Given regular expressions s,t that do not contain the Kleene star $.^*$, what is the complexity of deciding whether they define the same language?

I am sure this can be done in NP-time; but is it NP-complete?

If the star is allowed, the problem is PSPACE-complete.

Thanks for any help.

Answer 1

That might depend on the definition of what regular expressions you are examining.

If it is just concatenation and alternatives |, it seems easy to come up with the resulting languages and then it is just comparing two sets.

If you allow parentheses (, ) one might nest alternatives, which makes the computation of the resulting language a bit more complicated, because the tree of alternatives has to be generated.

Answer 2

Yes, this problem is NP-Complete. More precisely, check theorem 2.7 of this article where they denote $RINEQ-(\cup,\cdot)$ the set of regular expressions that do not contain *.