Complexity Measures for Regular Expressions

Andrzej Ehrenfeucht H. Paul Zeiger

Published in: STOC (1974)

Keyphrases

regular expressions
complexity measures
pattern matching
query language
lower bound
xml schema
nearest neighbor classifier
regular languages
regular path queries
matching algorithm
deterministic finite automata
learning paradigms
query evaluation
neural network
conceptual model
context free grammars
xml data