<p>Given an alphabet <span class="math-container">$\Sigma$</span> and a fixed nonempty string <span class="math-container">$w$</span>, consider the problem of finding a minimum regular expression <span class="math-container">$R(\Sigma, w)$</span> for all strings in <span class="math-container">$\Sigma^\star$</span> that do <em>not</em> contain <span class="math-container">$w$</span> as a substring.
Clearly such a regular expression exists, but I'm interested in the size of <span class="math-container">$R(\Sigma, w)$</span>; I'll interpret the size here as number of operations + number of single characters + parentheses.
The only operations are union, concat, and star (i.e., no complement/intersection, which would make the problem more-or-less trivial).</p>
<p>I'm interested in exact results if known, and upper bounds/asymptotics if not, and partial results for different alphabet sizes if als known.
One bound is to start with a regex for all strings that <em>do</em> contain <span class="math-container">$w$</span>, and then perform the usual regex <span class="math-container">$\to$</span> minimum-size DFA <span class="math-container">$\to$</span> complemented DFA <span class="math-container">$\to$</span> regex conversions.
Of course this bound can be exponential in <span class="math-container">$|\Sigma|, |w|$</span>.</p>
<p>One partial result: if <span class="math-container">$\Sigma = \{a, b\}$</span> and <span class="math-container">$w$</span> is of the form <span class="math-container">$axa$</span> for some non-empty string <span class="math-container">$x$</span> of <span class="math-container">$b$</span>'s, then one can make <span class="math-container">$R(\Sigma, w)$</span> as follows: <span class="math-container">$b^\star (a(\epsilon | b | \ldots | b^{|x|-1} | b^{|x|+1}b^\star))^\star a^\star$</span>, which is of size <span class="math-container">$O(|w|^2)$</span>.</p>

CC BY-SA 4.0
2024-08-29T04:10:18.467Z
I assume that your notion of  regular expression does not  contain complement
and intersection.
Martin Berger
CC BY-SA 4.0
2024-08-29T13:00:28.440Z
@MartinBerger correct.
Ryan Dougherty
CC BY-SA 4.0
2024-08-29T15:38:42.057Z
It looks like there's a typo in your last example. You’ve opened two parentheses but only closed one, which makes it unclear how the star is meant to apply.
Mojtaba Valizadeh
CC BY-SA 4.0
2024-08-29T21:12:29.157Z
@MojtabaValizadeh thanks! Fixed.
Ryan Dougherty
CC BY-SA 4.0
2024-08-30T09:44:31.627Z
I have no quantitative bounds, but plain regular expressions have
no succinct way of expressing what is *not* in their language. They
only talk about what *is* in the language. So I expect that the bounds
will be big. You can run some experiments with our tool
https://github.com/MojtabaValizadeh/paresy by taking a string $w$ and crafting suitable $(P, N)$ sets. Then the tool will give you a guaranteed minimal expression (or run OOM). That could give you hints for theorems to prove.
Martin Berger
<reference-request><regular-expressions>
Minimum Regular Expression for Strings not Containing Substring?
Ryan Dougherty
# Minimum Regular Expression for Strings not Containing Substring?

(Asked by: username_0 on 2024-08-28)

Given an alphabet $\Sigma$ and a fixed nonempty string $w$, consider the problem of finding a minimum regular expression $R(\Sigma, w)$ for all strings in $\Sigma^\star$ that do *not* contain $w$ as a substring.
Clearly such a regular expression exists, but I'm interested in the size of $R(\Sigma, w)$; I'll interpret the size here as number of operations + number of single characters + parentheses.
The only operations are union, concat, and star (i.e., no complement/intersection, which would make the problem more-or-less trivial).

I'm interested in exact results if known, and upper bounds/asymptotics if not, and partial results for different alphabet sizes if als known.
One bound is to start with a regex for all strings that *do* contain $w$, and then perform the usual regex $\to$ minimum-size DFA $\to$ complemented DFA $\to$ regex conversions.
Of course this bound can be exponential in $|\Sigma|, |w|$.

One partial result: if $\Sigma = \{a, b\}$ and $w$ is of the form $axa$ for some non-empty string $x$ of $b$'s, then one can make $R(\Sigma, w)$ as follows: $b^\star (a(\epsilon | b | \ldots | b^{|x|-1} | b^{|x|+1}b^\star))^\star a^\star$, which is of size $O(|w|^2)$.

**Tags:** reference-request, regular-expressions

> **Comments:**
> **username_1**: I assume that your notion of  regular expression does not  contain complement and intersection.  
> **username_0**: @MartinBerger correct.  
> **username_2**: It looks like there's a typo in your last example. You’ve opened two parentheses but only closed one, which makes it unclear how the star is meant to apply.  
> **username_0**: @MojtabaValizadeh thanks! Fixed.  
> **username_1**: I have no quantitative bounds, but plain regular expressions have no succinct way of expressing what is *not* in their language. They only talk about what *is* in the language. So I expect that the bounds will be big. You can run some experiments with our tool https://github.com/MojtabaValizadeh/paresy by taking a string $w$ and crafting suitable $(P, N)$ sets. Then the tool will give you a guaranteed minimal expression (or run OOM). That could give you hints for theorems to prove.  

---

## 0 answers

