REGEX equivalence is EXPSPACE-complete

Why squaring? Because a regex with squaring can describe languages requiring exponential-size minimal DFA — pushing the equivalence test to exponential space.

• Plain regex equivalence is PSPACE-complete; with squaring it's EXPSPACE-complete. One extra operator pushes the class up by an exponential.
• "Squaring" R² ≡ RR is shorthand. Iterated squaring R^(2^k) writes a regex of polynomial size but describes exponentially long strings.
• Real regex engines with backreferences are even worse. Backrefs add Turing-power; matching becomes NP-hard. Pathological backtracking can run for years.

• Q1. Why is plain regex equivalence in PSPACE?
  Convert each regex to an NFA (polynomial blow-up via Thompson's construction). Equivalence ⇔ symmetric difference is empty. Determinise via the subset construction (exponential states in worst case, but only PSPACE workspace needed). Check emptiness in space proportional to states.
• Q2. What does squaring add?
  R² doubles the language length. Iterated squaring R^(2^k) creates exponentially long languages from polynomial-size regex. This forces the equivalence test into exponential space — EXPSPACE-complete (Stockmeyer–Meyer 1973).
• Q3. Practical implication?
  Real-world regex engines avoid squaring/back-references for this reason. POSIX regex stays in P; Perl/Java/Python regex with backrefs is NP-hard for matching, and pathological cases (catastrophic backtracking) can run for years on simple-looking inputs.
• Q4. Where does EXPSPACE sit?
  EXPSPACE = ⋃_k SPACE(2^nk). Above PSPACE, above EXPTIME, below 2-EXPTIME. PSPACE ⊊ EXPSPACE by Space Hierarchy.

Sipser: §9.3. Stockmeyer–Meyer 1973 paper. Lecture notes: Module 7 slide 6. Companion problems: P12 (decidable trio), P57 (EXPTIME vs PSPACE).