<p>Finding the answer to your question is not overly difficult, if one is used to proving PSPACE upper bounds. But I think one cannot find an answer to your question in the literature, so here it is:</p>

<p>Given a regular expression r of alphabetic width n, i.e. with n alphabetic letters, you can enumerate all regular expressions of alphabetic width 1,2,3, one by one (see the paper by Gruber et al. 2012), and test for each such candidate expression c whether L(c) = L(r). The first expression where the test succeeds is clearly of minimum alphabetic width.</p>

<p>Apart from the test for language equivalence, this can be implemented using "only" linear space (and using exponential time).</p>

<p>The regular expression equivalence test can be done by converting r and c each to a nondeterministic finite automaton, and check if these automata are equivalent. The latter can be done in PSPACE as follows (this algorithm is mentioned in the paper by Bonchi and Pous 2013): For each word $w$ of length at most $2^n$, test whether $w \in L(r)$ if and only if $w \in L(s)$. If all these $2^{n+1}-1$ tests are successful, then $L(r)=L(s)$. </p>

<p><strong>Notes</strong></p>

<p>The paper by Gruber et al. (2012) also covers the computation of the number of regular languages whose minimal regular expression is of size n for small values of n. This actually uses an implementation of regular expression minimization. The test for language equivalence is not done in polynomial space as described above, but by computing the minimal DFA. This requires exponential space in the worst case. But there are more practical ways (all practical approaches seem to use exponential space) for testing the equivalence of NFAs, see 
<a href="http://languageinclusion.org/" rel="noreferrer">http://languageinclusion.org/</a></p>

<p><strong>References</strong></p>

<ul>
<li>Hermann Gruber, Jonathan Lee, Jeffrey Shallit: Enumerating regular expressions and their languages, arXiv:1204.4982 [cs.FL]</li>
<li>Filippo Bonchi, Damien Pous: Checking NFA equivalence with bisimulations up to congruence. POPL 2013.</li>
</ul>

CC BY-SA 3.0
2015-05-31T06:00:34.483Z
Okay, except for the equivalence test, this is certainly straight-forward. I actually thought in that direction but somehow didn't manage to put it together. Thanks! (Btw., there is an icy wind blowing here in terms of downvotes... )
lukas.coenig
CC BY-SA 3.0
2015-05-30T21:28:28.050Z
2015-05-30T21:28:28.050Z
Hermann Gruber
<p>Minimizing regular expressions (in terms of number of symbols) is PSPACE-complete
<br>
(for example as discussed here: <a href="https://cstheory.stackexchange.com/questions/12361/minimizing-size-of-regular-expression">minimizing size of regular expression</a>).</p>

<p>But how do you actually do that (i.e., what does an algorithm
<br>
for minimizing regular expressions in PSPACE look like)?</p>

<p>There are many results showing that it's hard in different contexts (such as when
<br>
an equivalent DFA is available), but I found none showing how it's actually done.
<br>
Probably it's so easy that I'm the only one not getting it. :-)</p>

<regular-expressions><pspace>
How can one ACTUALLY minimize a regular expression?
lukas.coenig
# How can one ACTUALLY minimize a regular expression?

(Asked by: username_0 on 2015-05-30)

Minimizing regular expressions (in terms of number of symbols) is PSPACE-complete
  
(for example as discussed here: [minimizing size of regular expression](https://cstheory.stackexchange.com/questions/12361/minimizing-size-of-regular-expression)).

But how do you actually do that (i.e., what does an algorithm
  
for minimizing regular expressions in PSPACE look like)?

There are many results showing that it's hard in different contexts (such as when
  
an equivalent DFA is available), but I found none showing how it's actually done.
  
Probably it's so easy that I'm the only one not getting it. :-)

**Tags:** regular-expressions, pspace


---

## 1 answers

### Answer by username_1 on 2015-05-30. Score: 6 | Accepted answer

Finding the answer to your question is not overly difficult, if one is used to proving PSPACE upper bounds. But I think one cannot find an answer to your question in the literature, so here it is:

Given a regular expression r of alphabetic width n, i.e. with n alphabetic letters, you can enumerate all regular expressions of alphabetic width 1,2,3, one by one (see the paper by Gruber et al. 2012), and test for each such candidate expression c whether L(c) = L(r). The first expression where the test succeeds is clearly of minimum alphabetic width.

Apart from the test for language equivalence, this can be implemented using "only" linear space (and using exponential time).

The regular expression equivalence test can be done by converting r and c each to a nondeterministic finite automaton, and check if these automata are equivalent. The latter can be done in PSPACE as follows (this algorithm is mentioned in the paper by Bonchi and Pous 2013): For each word $w$ of length at most $2^n$, test whether $w \in L(r)$ if and only if $w \in L(s)$. If all these $2^{n+1}-1$ tests are successful, then $L(r)=L(s)$.

**Notes**

The paper by Gruber et al. (2012) also covers the computation of the number of regular languages whose minimal regular expression is of size n for small values of n. This actually uses an implementation of regular expression minimization. The test for language equivalence is not done in polynomial space as described above, but by computing the minimal DFA. This requires exponential space in the worst case. But there are more practical ways (all practical approaches seem to use exponential space) for testing the equivalence of NFAs, see
<http://languageinclusion.org/>

**References**

* username_1, Jonathan Lee, Jeffrey Shallit: Enumerating regular expressions and their languages, arXiv:1204.4982 [cs.FL]
* Filippo Bonchi, Damien Pous: Checking NFA equivalence with bisimulations up to congruence. POPL 2013.

> **Comments:**
> **username_0**: Okay, except for the equivalence test, this is certainly straight-forward. I actually thought in that direction but somehow didn't manage to put it together. Thanks! (Btw., there is an icy wind blowing here in terms of downvotes... )  

---

