Time complexity of derivative-based regex matchers

Question

Regex matching using the Brzozowski derivative without any caching or expression-simplifying takes exponential time and space because of the product rule.

In Brzozowski's original paper, Brzozowski shows how to generate a DFA using the derivative operation. The upper bound he finds on the size of that DFA is an iterated exponential. So going on the upper bound alone, transforming a regex to a DFA via differentiation is less efficient than "running" the regex "directly".

In a later paper "Regular-expression derivatives reexamined", the authors show how to use automatic expression-simplifying to speed up Brzozowski's algorithm; but nothing is proven about the worst-case complexity.

Also, the theory of Brzozowski differentiations works just as well on ordinary regexes as it does on Extended Regexes, which feature intersection and complement. If deciding whether an Extended Regex expresses the Empty language were possible to do efficiently, then that would imply that derivative-based matching must be worst-case inefficient.

So what is the time-complexity of Brzozowski derivative-based matchers if automatic expression-simplifying is used?

Answer 1

In Theorem 5.2 of his paper, Brzozowski shows that every regular expression has a finite number of dissimilar derivatives, where two regular expressions $r$ and $r'$ are similar if they are ACU-equivalent at the outermost level. That is, consider the equivalence relation generated by the following equivalences:

$$ \array{ r \vee r & \equiv & r \\ r \vee r' & \equiv & r' \vee r \\ (r \vee r') \vee r'' & \equiv & r \vee (r' \vee r'') \\ r \vee \bot & \equiv & r \\} $$

(Notice the absence of congruence rules in this definition -- in particular, $a\cdot(r \vee r') \not\equiv a\cdot(r' \vee r)$.) It turns out there are at most $O(2^{|r|})$ many dissimilar word Brzozowski derivatives. So the worst case of matching with Brzozowski derivatives is the same as any other method.

A nice proof of this fact takes a detour through Antimirov partial derivatives. The one-character Antimirov derivative function is defined as follows:

$$ \array{ a_c(\bot) & = & \emptyset \\ a_c(r \vee r') & = & a_c(r) \cup a_c(r') \\ a_c(\epsilon) & = & \emptyset \\ a_c(c') & = & \emptyset \\ a_c(c) & = & \{ \epsilon \} \\ a_c(r_1 \cdot r_2) & = & \{ r'_1 \cdot r_2 \;|\; r'_1 \in a_c(r_1) \} \\ & & \cup \; (\mbox{if}\;\mbox{nullable}(r_1)\;\mbox{then}\; a_c(r_2) \;\mbox{else}\;\emptyset) \\ a_c(r\ast) & = & \{ r' \cdot r\ast \;|\; r' \in a_c(r) \} } $$

Basically, instead of returning a single derivative, the Antimirov derivative returns a set of partial derivatives, whose union adds up to the Brzozowski derivative. Now, we can make the following observations:

1. Up to similarity, the union of the set of Antimirov partial derivatives of a regular expression and the Brzozowski derivative are one and the same.

2. It's also easy to prove that given a regular expression $r$, the number of Antimirov word derivatives is linear in the size of $r$.

3. Since a Brzozowski derivative is formed from a union of Antimirov derivatives, there can be at most $O(2^{|r|})$ possible Brzozowski derivatives of a regular expression (up to similarity).

As defined, the Antimirov derivative doesn't work with intersection. Pascal Caron, Jean-Marc Champarnaud and Ludovic Mignot had a LATA 2011 paper, Partial Derivatives of an Extended Regular Expression, which extended this approach to cover extended regular expressions. Their idea is to define a new partial derivative operation returning a set of sets of partial derivatives (corresponding to DNF), and they show that this has a worst-case exponential size. Intuitively, this corresponds to the fact that implementing intersection on automata uses a product construction.

Anyway, the takeaway (IMO) should be that derivatives are not alternatives to the standard automata-theoretic constructions, but rather are a conceptual explanation of them.