As stated in the title, I need a decision procedure for the problem of regular expression equivalence with not. Wikipedia states the problem is in the NONELEMENTARY complexity class. All I really need is link to the paper that describes the problem and its solution. This is NOT a homework problem. I need the procedure for a program static analysis tool.
Thanks!
Stockmeyer and Meyer, "Word problems requiring exponential time", Proc. 5th ACM Symposium on the Theory of Computing, pp 1-9, 1973.
The derivation is fairly intuitive: every negation in the regular expression 'somehow' requires conversion to a DFA, and a lower bound of $\Theta(2^n)$ states guaranteed for conversion. Nest your $\neg$'s and you get a stack of exponentials.