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

<p><span class="math-container">$$
\array{
r \vee r &amp; \equiv &amp;  r \\
r \vee r' &amp; \equiv &amp; r' \vee r \\
(r \vee r') \vee r'' &amp; \equiv &amp; r \vee (r' \vee r'') \\
r \vee \bot &amp; \equiv &amp; r \\}
$$</span></p>

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

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

<p><span class="math-container">$$
\array{
a_c(\bot) &amp; = &amp; \emptyset \\
a_c(r \vee r') &amp; = &amp; a_c(r) \cup a_c(r') \\
a_c(\epsilon) &amp; = &amp; \emptyset \\ 
a_c(c')        &amp; = &amp; \emptyset \\
a_c(c)         &amp; = &amp; \{ \epsilon \}  \\
a_c(r_1 \cdot r_2) &amp; = &amp; \{ r'_1 \cdot r_2 \;|\; r'_1 \in a_c(r_1) \} \\
                   &amp;   &amp; \cup \; (\mbox{if}\;\mbox{nullable}(r_1)\;\mbox{then}\; a_c(r_2) \;\mbox{else}\;\emptyset) \\
a_c(r\ast) &amp; = &amp; \{ r' \cdot r\ast \;|\; r' \in a_c(r) \}
}
$$</span></p>

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

<ol>
<li><p>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. </p></li>
<li><p>It's also easy to prove that given a regular expression <span class="math-container">$r$</span>, the number of Antimirov word derivatives is linear in the size of <span class="math-container">$r$</span>. </p></li>
<li><p>Since a Brzozowski derivative is formed from a union of Antimirov derivatives, there can be at most <span class="math-container">$O(2^{|r|})$</span> possible Brzozowski derivatives of a regular expression (up to similarity). </p></li>
</ol>

<p>As defined, the Antimirov derivative doesn't work with intersection.     Pascal Caron, Jean-Marc Champarnaud and Ludovic Mignot had a LATA 2011 paper, <a href="https://link.springer.com/chapter/10.1007/978-3-642-21254-3_13" rel="noreferrer"><em>Partial Derivatives of an Extended Regular Expression</em></a>, 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.</p>

<p>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. </p>

CC BY-SA 4.0
2018-11-27T12:06:42.763Z
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
wlad
CC BY-SA 4.0
2018-11-27T12:11:50.430Z
Also, I'm noticing that you've only shown an *upper bound* on the worst case
wlad
CC BY-SA 4.0
2018-11-27T14:02:43.463Z
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.
Neel Krishnaswami
CC BY-SA 4.0
2018-11-27T10:55:40.807Z
2018-11-27T13:35:55.707Z
2018-11-27T13:35:55.707Z
Neel Krishnaswami
<p>Regex matching using the Brzozowski derivative without any caching or expression-simplifying takes exponential time and space because of the product rule.</p>

<p>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".</p>

<p>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.</p>

<p>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.</p>

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

<regular-expressions>
Time complexity of derivative-based regex matchers
wlad
# Time complexity of derivative-based regex matchers

(Asked by: username_0 on 2018-11-25)

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?

**Tags:** regular-expressions

---

## 1 answers

### Answer by username_1 on 2018-11-27. Score: 8 | Accepted answer

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*](https://link.springer.com/chapter/10.1007/978-3-642-21254-3_13), 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.

> **Comments:**
> **username_0**: 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  
> **username_0**: Also, I'm noticing that you've only shown an *upper bound* on the worst case  
> **username_1**: 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.  

---

