Deterministic regular expressions in linear time.

Benoît Groz Sebastian Maneth Slawek Staworko

Published in: PODS (2012)

Keyphrases

regular expressions
deterministic finite automata
pattern matching
finite automata
semistructured data
query language
regular languages
tree automata
xml schema
regular path queries
worst case
finite state machines
matching algorithm
query evaluation
domain specific
domain ontology
np complete
database systems