The Equivalence Problem for Regular Expressions with Squaring Requires Exponential Space

Albert R. Meyer Larry J. Stockmeyer

Published in: SWAT (1972)

Keyphrases

regular expressions
pattern matching
query language
finite automata
semistructured data
tree automata
deterministic finite automata
matching algorithm
graph databases
xml schema
query containment
database systems
object oriented
regular path queries