Descriptional Complexity of Deterministic Regular Expressions.

Katja Losemann Wim Martens Matthias Niewerth

Published in: MFCS (2012)

Keyphrases

regular expressions
deterministic finite automata
pattern matching
finite automata
query language

semistructured data
regular languages
tree automata
xml schema
regular path queries

matching algorithm
database
graph databases
conjunctive regular path queries
bit parallel

context free grammars
query evaluation
expressive power
lower bound