Analyzing Matching Time Behavior of Backtracking Regular Expression Matchers by Using Ambiguity of NFA
We apply results from ambiguity of non deterministic finite automata to the problem of determining the asymptotic worst case matching time, as a function of the length of the input strings, when attempting to match input strings with a given regular expression, where the matcher being used is a backtracking regular expression matcher.
CIAA