A Dichotomy for Regular Expression Membership Testing.

Karl Bringmann Allan Grønlund Kasper Green Larsen

Published in: FOCS (2017)

Keyphrases

regular expressions
pattern matching
query language
finite automata
semistructured data
cost model
xml schema
deterministic finite automata
query evaluation
test cases
static analysis
string matching
building blocks
regular path queries
databases
graph databases
approximate matching