6
$\begingroup$

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?

$\endgroup$
4
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ Very interesting, but the LHS and RHS of the following equation are the same $(r \vee r') \vee r'' \equiv (r \vee r') \vee r''$. I'll read through this carefully later $\endgroup$ – man and laptop Nov 27 '18 at 12:06
  • $\begingroup$ Also, I'm noticing that you've only shown an upper bound on the worst case $\endgroup$ – man and laptop Nov 27 '18 at 12:11
  • $\begingroup$ In certain cases, the exponential NFA-to-DFA blowup is unavoidable, so there are no asymptotically better bounds. However, doing state construction via derivatives and similarity does not in general yield minimal automata, because you can introduce separate states for dissimilar but equivalent regular expressions. $\endgroup$ – Neel Krishnaswami Nov 27 '18 at 14:02

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.