The Equivalence Problem for Regular Expressions with Squaring Requires Exponential Space

Meyer, A. R., & Stockmeyer, L. J. (1972). The Equivalence Problem for Regular Expressions with Squaring Requires Exponential Space. 13th Annual Symposium on Switching and Automata Theory, 125-129.

Type

Conference paper

Intellectual base

Primary research

Year

1972

Link

no authoritative link yet

Cited by

1 citation across 1 artifact.

Domain-specific

• EXPSPACE
  • … with squaring is a classical EXPSPACE-complete problem under standard encodings and reductions. to A configuration graph for an exponentially space-bounded computation can have doubly exponentially many configurations while each configuration itself is representable in exponential space. demonstrates that continuity.

Verification

This reference passed the adversarial substantiation pipeline: it was checked to exist and to support the claim it is attached to. See how references were verified.

Registry ID ref:65e135d6370f · see in the full table