The Equivalence Problem for Regular Expressions with Squaring Requires Exponential Space

Albert R. Meyer, Larry J. Stockmeyer

Browse the full FOCS paper archive.