  Combining the the results of A.R. Meyer and L.J. Stockmeyer "The Equivalence
Problem for Regular Expressions with Squaring Requires Exponential Space", and
K.S. Booth "Isomorphism testing for graphs, semigroups, and finite automata are
polynomiamlly equivalent problems" shows that graph isomorphism is
PSPACE-complete.
