<p>As noted in the question, <em>question 1</em> has already been answered on this site.</p>
<p>Regarding <em>question 2</em>, if <span class="math-container">$Q$</span> is any language quotient of <span class="math-container">$L(r)$</span>, then there is a regular expression of at most at most quadratic size, i.e., <span class="math-container">$O(|r^2|)$</span>.
Here the size of a regular expression can be measured by alphabetic width, or reverse polish length (the minimum sizes are linearly related). Since each derivative is a language quotient of <span class="math-container">$L(r)$</span>, the quadratic bound in particular holds for the special case of derivatives.</p>
<p>The bound follows by an amortized analysis of the standard construction of canonical derivatives on <em>linear</em> expresssions (i.e. marked regular expressions, where every alphabet symbol appears at most once). Then we apply the length-preserving homomorphism that erases the markings again, which preserves the alphabetic width.</p>
<blockquote>
<p>Hermann Gruber, Markus Holzer, <a href="https://doi.org/10.1016/j.tcs.2009.04.009" rel="nofollow noreferrer">Language operations with regular
expressions of polynomial size</a>, Theoretical Computer Science 410(35),
2009.</p>
</blockquote>
<p>Improving the upper bounds (also for the special case of derivatives), or obtaining nontrivial lower bounds remains an open problem.</p>
<p>Regarding the last question, the strong star normal form proposed in the following paper removes more redundancies than ACI-similarity:</p>
<blockquote>
<p>Gruber, H., Gulan, S. (2010). <a href="https://doi.org/10.1007/978-3-642-13089-2_24" rel="nofollow noreferrer">Simplifying Regular Expressions. A
Quantitative Perspective</a> In: Dediu, AH., Fernau, H., Martín-Vide,
C. (eds) Language and Automata Theory and Applications. LATA 2010.
Lecture Notes in Computer Science, vol 6031. Springer, Berlin,
Heidelberg.</p>
</blockquote>
<p>Some advanced reduction rules are given in the following paper (they are more demanding to compute as well, and probably go beyond &quot;simple syntactic congruences&quot;):</p>
<blockquote>
<p>Stefan Kahrs, Colin Runciman,  <a href="https://doi.org/10.1016/j.jsc.2021.08.003" rel="nofollow noreferrer">Simplifying regular expressions
further</a>, Journal of Symbolic Computation 109 (March-April), 2022,
pp. 124-143.</p>
</blockquote>
<p>Final remark regarding question 1: It may be of interest that Brzozowski in his late works, some 50 years later, used the term &quot;quotient complexity&quot; of a regular language to denote the state complexity, i.e. the number of states of the minimal DFA. He explains that the state complexity is equal to the number of dissimilar derivatives here:</p>
<blockquote>
<p>Janusz Brzozowski: <a href="https://arxiv.org/abs/0907.4547" rel="nofollow noreferrer">Quotient Complexity of Regular Languages</a>. In
J. Dassow, G. Pighizzini, B. Truthe (Eds.). 11th International
Workshop on Descriptional Complexity of Formal Systems (DCFS 2009)
EPTCS 3, 2009, pp. 17–28, doi:10.4204/EPTCS.3.2</p>
</blockquote>

CC BY-SA 4.0
2024-11-26T01:03:59.113Z
"the quadratic bound in particular holds for the special case of derivatives." Can this upperbound be achieved using ACI simplification?
Agnishom Chattopadhyay
CC BY-SA 4.0
2024-11-26T07:20:54.183Z
Yes, Lemma 1 in the paper with that proof refers to "reduced" regular expressions, a notion explained there. That notion makes use of ACI equivalence. I recommend you to read that paper, at least the part related to quotients. If you have further questions afterwards, I'm happy to help.
Hermann Gruber
CC BY-SA 4.0
2024-11-27T01:31:28.893Z
Thanks, I did read the paper. From what I understood, the definition of "reduced" involves addition simplification. For example, it involves rewriting r · ε to r, which is not a consequence of the ACI rules.
Agnishom Chattopadhyay
CC BY-SA 4.0
2024-11-27T14:49:13.147Z
Yes, correct. So the upper bound relies on the notion of "reduced regular expression", which is not encompassed by ACI equivalence.
Hermann Gruber
CC BY-SA 4.0
2024-11-25T20:31:56.993Z
2024-11-25T20:54:10.487Z
2024-11-25T20:54:10.487Z
Hermann Gruber
<p>In Brzozowski's original paper [1], he considers two expressions ACI-equivalent, if they can be simplified into one another using the following axioms:</p>
<ul>
<li>Associativity: <span class="math-container">$r + (s + t) \equiv (r + s) + t$</span></li>
<li>Commutativity: <span class="math-container">$r + s \equiv s + r$</span></li>
<li>Idempotence: <span class="math-container">$r + r \equiv r$</span></li>
</ul>
<p>Consider a regular expression <span class="math-container">$r$</span>. The set of Brzozowski derivatives of <span class="math-container">$r$</span> are all <span class="math-container">$r'$</span> such that <span class="math-container">$r'$</span> is <span class="math-container">$\text{derivative}(w, r) = r'$</span>. In [1], Brzozowski shows that the set of Brzozowski derivatives is finite when considered modulo ACI-equivalence.</p>
<ol>
<li>How many derivatives are there (modulo ACI-equivalence)? [EDIT: It seems that this question is already answered <a href="https://cstheory.stackexchange.com/a/41945/48690">here</a>]</li>
<li>What is the maximum size of the minimal representative of these classes, with respect to the regex <span class="math-container">$r$</span>?</li>
</ol>
<p>In [1], Brzozowski includes a proof of finiteness, but following this proof does not lead to a great upper-bound. Besides, he says that &quot;Note that we are finding upper-bounds to show the finiteness, but such bounds do not necessarily have to be achieved.&quot;</p>
<ol start="3">
<li>Are there other simple syntactic equivalences that have been added to the ACI-axioms which yield smaller derivatives?</li>
</ol>
<hr />
<p>[1] Janusz A. Brzozowski. 1964. Derivatives of Regular Expressions. J. ACM 11, 4 (Oct. 1964), 481–494. <a href="https://doi.org/10.1145/321239.321249" rel="nofollow noreferrer">https://doi.org/10.1145/321239.321249</a></p>

<regular-language><regular-expressions><upper-bounds>
How large are the Brzozowski Derivatives?
Agnishom Chattopadhyay
# How large are the Brzozowski Derivatives?

(Asked by: username_0 on 2024-07-01)

In Brzozowski's original paper [1], he considers two expressions ACI-equivalent, if they can be simplified into one another using the following axioms:

* Associativity: $r + (s + t) \equiv (r + s) + t$
* Commutativity: $r + s \equiv s + r$
* Idempotence: $r + r \equiv r$

Consider a regular expression $r$. The set of Brzozowski derivatives of $r$ are all $r'$ such that $r'$ is $\text{derivative}(w, r) = r'$. In [1], Brzozowski shows that the set of Brzozowski derivatives is finite when considered modulo ACI-equivalence.

1. How many derivatives are there (modulo ACI-equivalence)? [EDIT: It seems that this question is already answered [here](https://cstheory.stackexchange.com/a/41945/48690)]
2. What is the maximum size of the minimal representative of these classes, with respect to the regex $r$?

In [1], Brzozowski includes a proof of finiteness, but following this proof does not lead to a great upper-bound. Besides, he says that "Note that we are finding upper-bounds to show the finiteness, but such bounds do not necessarily have to be achieved."

3. Are there other simple syntactic equivalences that have been added to the ACI-axioms which yield smaller derivatives?

---

[1] Janusz A. Brzozowski. 1964. Derivatives of Regular Expressions. J. ACM 11, 4 (Oct. 1964), 481–494. <https://doi.org/10.1145/321239.321249>

**Tags:** regular-language, regular-expressions, upper-bounds


---

## 1 answers

### Answer by username_1 on 2024-11-25. Score: 2

As noted in the question, *question 1* has already been answered on this site.

Regarding *question 2*, if $Q$ is any language quotient of $L(r)$, then there is a regular expression of at most at most quadratic size, i.e., $O(|r^2|)$.
Here the size of a regular expression can be measured by alphabetic width, or reverse polish length (the minimum sizes are linearly related). Since each derivative is a language quotient of $L(r)$, the quadratic bound in particular holds for the special case of derivatives.

The bound follows by an amortized analysis of the standard construction of canonical derivatives on *linear* expresssions (i.e. marked regular expressions, where every alphabet symbol appears at most once). Then we apply the length-preserving homomorphism that erases the markings again, which preserves the alphabetic width.

> username_1, Markus Holzer, [Language operations with regular
> expressions of polynomial size](https://doi.org/10.1016/j.tcs.2009.04.009), Theoretical Computer Science 410(35),
> 2009.

Improving the upper bounds (also for the special case of derivatives), or obtaining nontrivial lower bounds remains an open problem.

Regarding the last question, the strong star normal form proposed in the following paper removes more redundancies than ACI-similarity:

> Gruber, H., Gulan, S. (2010). [Simplifying Regular Expressions. A
> Quantitative Perspective](https://doi.org/10.1007/978-3-642-13089-2_24) In: Dediu, AH., Fernau, H., Martín-Vide,
> C. (eds) Language and Automata Theory and Applications. LATA 2010.
> Lecture Notes in Computer Science, vol 6031. Springer, Berlin,
> Heidelberg.

Some advanced reduction rules are given in the following paper (they are more demanding to compute as well, and probably go beyond "simple syntactic congruences"):

> Stefan Kahrs, Colin Runciman, [Simplifying regular expressions
> further](https://doi.org/10.1016/j.jsc.2021.08.003), Journal of Symbolic Computation 109 (March-April), 2022,
> pp. 124-143.

Final remark regarding question 1: It may be of interest that Brzozowski in his late works, some 50 years later, used the term "quotient complexity" of a regular language to denote the state complexity, i.e. the number of states of the minimal DFA. He explains that the state complexity is equal to the number of dissimilar derivatives here:

> Janusz Brzozowski: [Quotient Complexity of Regular Languages](https://arxiv.org/abs/0907.4547). In
> J. Dassow, G. Pighizzini, B. Truthe (Eds.). 11th International
> Workshop on Descriptional Complexity of Formal Systems (DCFS 2009)
> EPTCS 3, 2009, pp. 17–28, doi:10.4204/EPTCS.3.2

> **Comments:**
> **username_0**: "the quadratic bound in particular holds for the special case of derivatives." Can this upperbound be achieved using ACI simplification?  
> **username_1**: Yes, Lemma 1 in the paper with that proof refers to "reduced" regular expressions, a notion explained there. That notion makes use of ACI equivalence. I recommend you to read that paper, at least the part related to quotients. If you have further questions afterwards, I'm happy to help.  
> **username_0**: Thanks, I did read the paper. From what I understood, the definition of "reduced" involves addition simplification. For example, it involves rewriting r · ε to r, which is not a consequence of the ACI rules.  
> **username_1**: Yes, correct. So the upper bound relies on the notion of "reduced regular expression", which is not encompassed by ACI equivalence.  

---

