<p>apparently lacking an exact known answer or a better one than this, heres a near/recent ref on research specifically on the subj of minimizing REs (which is an apparently uncommon angle):</p>

<p><a href="http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.60.5056" rel="nofollow">Minimizing NFA's and Regular Expressions (2005)</a>
by Gregor Gramlich, Georg Schnitger </p>

<blockquote>
  <p>We show inapproximability results concerning minimization of nondeterministic finite automata (nfa's) as well as regular expressions relative to given nfa's, regular expressions or deterministic finite automata (dfa's). We show that it is impossible to efficiently minimize a given nfa or regular expression with n states, transitions, resp. symbols within the factor o(n), unless P = PSPACE. Our inapproximability results for a given dfa with n states are based on cryptographic assumptions and we show that any efficient algorithm will have an approximation factor of at least poly(log n) . Our setup also allows us to analyze the minimum consistent dfa problem.</p>
</blockquote>

CC BY-SA 3.0
2013-03-13T23:32:37.500Z
This question was asked specifically because of this paper doesn't address what happens when the language is finite.
Chao Xu
CC BY-SA 3.0
2013-03-14T02:49:36.753Z
fine then it serves as [relevant/nec] bkg. but note that if the other question has no [published] answer, its certainly not surprising this one doesnt either, a near variant angle might not help much. also [_mea culpa_] didnt notice the paper was cited by MdB on the other question.
vzn
CC BY-SA 3.0
2013-03-13T23:04:23.080Z
2013-03-13T23:10:13.780Z
2013-03-13T23:10:13.780Z
vzn
<p><strong>Update (10/09/21):</strong></p>
<p>The problem is coNP-hard, and impossible to approximate within <span class="math-container">$O(s^{1-\delta})$</span> for every <span class="math-container">$\delta&gt;0$</span>.
With Markus Holzer and Simon Wolfsteiner, we have an upcoming paper &quot;<a href="http://www.hermann-gruber.com/papers.html" rel="nofollow noreferrer">On Minimizing Regular Expressions Without Kleene Star</a>&quot;
that will be presented next monday at FCT 2021.
We also have a few fine-grained upper and lower bounds that show a tight tradeoff between (quasipolynomial up to exponential)
running time and approximation guarantees.</p>
<p><strong>End of Update</strong></p>
<p>The following argument is essentially from (<a href="http://www.hermann-gruber.com/data/lata07-final.pdf" rel="nofollow noreferrer">4</a>): The decision versions of the two problems are contained in the second level of the <a href="http://en.wikipedia.org/wiki/Polynomial_hierarchy" rel="nofollow noreferrer" title="polynomial hierarchy">polynomial hierarchy</a> (more precisely: in the complexity class <span class="math-container">$\Sigma^P_2$</span>), as follows. Guess a regular expression of size at most <span class="math-container">$k$</span>, and check if it is equivalent to the given deterministic finite automaton (respectively: to the language given as a list of words).</p>
<p>I believe that no further results regarding your problems are known. For a similar-looking optimization problem, where the objective is to find a minimum equivalent nondeterministic finite automaton instead of a regular expression, the following results are known:</p>
<ul>
<li>For input described as DFA, the minimum equivalent NFA problem is <span class="math-container">${\bf DP}$</span>-hard, see (<a href="http://www.hermann-gruber.com/data/lata07-final.pdf" rel="nofollow noreferrer">4</a>). Here, <span class="math-container">${\bf DP}$</span> stands for &quot;difference polynomial time&quot;; this is the &quot;Sigma&quot; complexity class at the second level of the <a href="http://en.wikipedia.org/wiki/Boolean_hierarchy" rel="nofollow noreferrer" title="Boolean hierarchy">Boolean hierarchy</a>.</li>
<li>For input described as a list of words, the minimum equivalent NFA problem is <span class="math-container">${\bf NP}$</span>-hard, see (<a href="http://www.hermann-gruber.com/data/dlt07-final.pdf" rel="nofollow noreferrer">7</a>).</li>
<li>For <span class="math-container">$L \subseteq \{0,1\}^m$</span> and input described as a truth table, the minimum equivalent NFA problem is <span class="math-container">${\bf NP}$</span>-complete, see (<a href="http://www.hermann-gruber.com/data/dlt07-final.pdf" rel="nofollow noreferrer">7</a>).</li>
</ul>
<p><em>Beware:</em> Unlike the setting of infinite languages, I do not see a straightforward reduction from the NFA minimization case to the problems from your question.</p>
<p><strong>References:</strong></p>
<p>(1) Hermann Gruber and Markus Holzer. <a href="http://www.hermann-gruber.com/data/lata07-final.pdf" rel="nofollow noreferrer">Computational Complexity of NFA Minimization for Finite and Unary Languages</a>. In: 1st International Conference on Language and Automata Theory and Applications (LATA 2007), pp. 261-272, 2007.</p>
<p>(2) Hermann Gruber and Markus Holzer. <a href="http://www.hermann-gruber.com/data/dlt07-final.pdf" rel="nofollow noreferrer">Inapproximability of Nondeterministic State and Transition Complexity Assuming P &lt;&gt; NP</a>. In: 11th International Conference on Developments in Language Theory (DLT 2007), LNCS 4588, pp. 205-216, 2007.</p>
<p><strong>Edit:</strong>
I think that grammar based codes are not so closely related: in that setup, the given language is a singleton set. But for such a singleton language <span class="math-container">$L=\{w\}$</span>, the minimum size regular expression is (trivially) given by <span class="math-container">$w$</span>.</p>

CC BY-SA 4.0
2013-03-17T22:14:38.150Z
2021-09-14T05:38:06.457Z
2021-09-14T05:38:06.457Z
Hermann Gruber
<p>It is known that minimizing the size of a regular expression is <a href="https://cstheory.stackexchange.com/questions/12361/minimizing-size-of-regular-expression">PSPACE-complete even if we have a DFA as the language's specification</a>. </p>

<p>What are the results if the language is finite? </p>

<p>One can consider this problem in two models:</p>

<ol>
<li>The input is all the strings in the language, and we measure the input size by the sum of the length of all strings.</li>
<li>The input is a DFA, and we measure the input size by the number of states of the DFA. </li>
</ol>

<p>Kleene star is not useful in the finite case, so only $()$, $|$ and $\cdot$(concatenation) are used in the expression. Of course, the length of a regular expression seems arbitrary. Instead, one can give weight to each operation(include adding parenthesis), and ask to minimize the weight of the regular expression. </p>

<p><strong>Edit:</strong> As adrianN noted, it's related to grammar based codes. It's NP-complete to produce the minimum length context free grammar to describe a finite set. It's not clear why minimum size context free grammar can imply much about minimum size regular expression. Maybe a clever rewrite rule can related these two, and prove that in the first model, the problem is in NP. </p>

CC BY-SA 3.0
2013-03-13T11:58:50.747Z
This seems related to [grammar based codes](http://en.wikipedia.org/wiki/Grammar-based_code).
adrianN
CC BY-SA 3.0
2013-03-13T15:48:18.613Z
suppose input size is limited. then kleene star could be valid. so it makes sense to define if input size is (naturally) limited to longest string in the finite language. & also if kleene star is still excluded in that case. also, as a (obvious?) heuristic, minimizing the DFA & constructing a RE from that is one strategy... also note that REs (with variable substitution) have a DAG-like structure and there are not many (strong) thms known about minimizing DAG-like structures.... REs without variable substitution are treelike (formulas) & may be easier to work with....
vzn
CC BY-SA 3.0
2013-03-13T20:31:12.297Z
other angle. RE "derivatives" introduced by brzozowski are known to be useful for converting REs directly into DFAs see eg [Regular-expression derivatives reexamined](http://www.ccs.neu.edu/home/turon/re-deriv.pdf) by Owens, Reppy, Turon. maybe there is some way to use the same structure for the inverse problem. anyway though overall it appears to be an open problem....
vzn
<cc.complexity-theory><reference-request><fl.formal-languages><regular-expressions><dfa>
minimizing size of regular expression for finite sets
Chao Xu
# minimizing size of regular expression for finite sets

(Asked by: username_0 on 2013-03-12)

It is known that minimizing the size of a regular expression is [PSPACE-complete even if we have a DFA as the language's specification](https://cstheory.stackexchange.com/questions/12361/minimizing-size-of-regular-expression).

What are the results if the language is finite?

One can consider this problem in two models:

1. The input is all the strings in the language, and we measure the input size by the sum of the length of all strings.
2. The input is a DFA, and we measure the input size by the number of states of the DFA.

Kleene star is not useful in the finite case, so only $()$, $|$ and $\cdot$(concatenation) are used in the expression. Of course, the length of a regular expression seems arbitrary. Instead, one can give weight to each operation(include adding parenthesis), and ask to minimize the weight of the regular expression.

**Edit:** As adrianN noted, it's related to grammar based codes. It's NP-complete to produce the minimum length context free grammar to describe a finite set. It's not clear why minimum size context free grammar can imply much about minimum size regular expression. Maybe a clever rewrite rule can related these two, and prove that in the first model, the problem is in NP.

**Tags:** cc.complexity-theory, reference-request, fl.formal-languages, regular-expressions, dfa
> **Comments:**
> **username_1**: This seems related to [grammar based codes](http://en.wikipedia.org/wiki/Grammar-based_code).  
> **username_2**: suppose input size is limited. then kleene star could be valid. so it makes sense to define if input size is (naturally) limited to longest string in the finite language. & also if kleene star is still excluded in that case. also, as a (obvious?) heuristic, minimizing the DFA & constructing a RE from that is one strategy... also note that REs (with variable substitution) have a DAG-like structure and there are not many (strong) thms known about minimizing DAG-like structures.... REs without variable substitution are treelike (formulas) & may be easier to work with....  
> **username_2**: other angle. RE "derivatives" introduced by brzozowski are known to be useful for converting REs directly into DFAs see eg [Regular-expression derivatives reexamined](http://www.ccs.neu.edu/home/turon/re-deriv.pdf) by Owens, Reppy, Turon. maybe there is some way to use the same structure for the inverse problem. anyway though overall it appears to be an open problem....  

---

## 2 answers

### Answer by username_3 on 2013-03-17. Score: 7 | Accepted answer

**Update (10/09/21):**

The problem is coNP-hard, and impossible to approximate within $O(s^{1-\delta})$ for every $\delta>0$.
With Markus Holzer and Simon Wolfsteiner, we have an upcoming paper "[On Minimizing Regular Expressions Without Kleene Star](http://www.hermann-gruber.com/papers.html)"
that will be presented next monday at FCT 2021.
We also have a few fine-grained upper and lower bounds that show a tight tradeoff between (quasipolynomial up to exponential)
running time and approximation guarantees.

**End of Update**

The following argument is essentially from ([4](http://www.hermann-gruber.com/data/lata07-final.pdf)): The decision versions of the two problems are contained in the second level of the [polynomial hierarchy](http://en.wikipedia.org/wiki/Polynomial_hierarchy "polynomial hierarchy") (more precisely: in the complexity class $\Sigma^P\_2$), as follows. Guess a regular expression of size at most $k$, and check if it is equivalent to the given deterministic finite automaton (respectively: to the language given as a list of words).

I believe that no further results regarding your problems are known. For a similar-looking optimization problem, where the objective is to find a minimum equivalent nondeterministic finite automaton instead of a regular expression, the following results are known:

* For input described as DFA, the minimum equivalent NFA problem is ${\bf DP}$-hard, see ([4](http://www.hermann-gruber.com/data/lata07-final.pdf)). Here, ${\bf DP}$ stands for "difference polynomial time"; this is the "Sigma" complexity class at the second level of the [Boolean hierarchy](http://en.wikipedia.org/wiki/Boolean_hierarchy "Boolean hierarchy").
* For input described as a list of words, the minimum equivalent NFA problem is ${\bf NP}$-hard, see ([7](http://www.hermann-gruber.com/data/dlt07-final.pdf)).
* For $L \subseteq \{0,1\}^m$ and input described as a truth table, the minimum equivalent NFA problem is ${\bf NP}$-complete, see ([7](http://www.hermann-gruber.com/data/dlt07-final.pdf)).

*Beware:* Unlike the setting of infinite languages, I do not see a straightforward reduction from the NFA minimization case to the problems from your question.

**References:**

(1) Hermann Gruber and Markus Holzer. [Computational Complexity of NFA Minimization for Finite and Unary Languages](http://www.hermann-gruber.com/data/lata07-final.pdf). In: 1st International Conference on Language and Automata Theory and Applications (LATA 2007), pp. 261-272, 2007.

(2) Hermann Gruber and Markus Holzer. [Inapproximability of Nondeterministic State and Transition Complexity Assuming P <> NP](http://www.hermann-gruber.com/data/dlt07-final.pdf). In: 11th International Conference on Developments in Language Theory (DLT 2007), LNCS 4588, pp. 205-216, 2007.

**Edit:**
I think that grammar based codes are not so closely related: in that setup, the given language is a singleton set. But for such a singleton language $L=\{w\}$, the minimum size regular expression is (trivially) given by $w$.


---

### Answer by username_2 on 2013-03-13. Score: -6

apparently lacking an exact known answer or a better one than this, heres a near/recent ref on research specifically on the subj of minimizing REs (which is an apparently uncommon angle):

[Minimizing NFA's and Regular Expressions (2005)](http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.60.5056)
by Gregor Gramlich, Georg Schnitger

> We show inapproximability results concerning minimization of nondeterministic finite automata (nfa's) as well as regular expressions relative to given nfa's, regular expressions or deterministic finite automata (dfa's). We show that it is impossible to efficiently minimize a given nfa or regular expression with n states, transitions, resp. symbols within the factor o(n), unless P = PSPACE. Our inapproximability results for a given dfa with n states are based on cryptographic assumptions and we show that any efficient algorithm will have an approximation factor of at least poly(log n) . Our setup also allows us to analyze the minimum consistent dfa problem.

> **Comments:**
> **username_0**: This question was asked specifically because of this paper doesn't address what happens when the language is finite.  
> **username_2**: fine then it serves as [relevant/nec] bkg. but note that if the other question has no [published] answer, its certainly not surprising this one doesnt either, a near variant angle might not help much. also [_mea culpa_] didnt notice the paper was cited by MdB on the other question.  

---

