Optimal Lower Bounds on Regular Expression Size Using Communication Complexity.
Hermann GruberJan JohannsenPublished in: FoSSaCS (2008)
Keyphrases
- regular expressions
- lower bound
- worst case
- pattern matching
- upper bound
- constant factor
- optimal cost
- space complexity
- computational complexity
- optimal solution
- finite automata
- np hard
- memory requirements
- xml schema
- expected error
- approximate matching
- deterministic finite automata
- cost model
- objective function
- semistructured data
- matching algorithm
- dynamic programming
- domain knowledge