<p>It is PSPACE-complete to decide whether an expression accepts all words, i.e. is equivalent to <span class="math-container">$(a|b|c|...)^*$</span>. It is not hard to get convinced that in this proof of PSPACE-completeness (see e.g. <a href="https://cstheory.stackexchange.com/a/40250/8953">https://cstheory.stackexchange.com/a/40250/8953</a>), when the expression does not accept all words, then it cannot be equivalent to an even shorter expression. Indeed, in this case it must accept everything except a long word that represents a valid encoding of a run of a PSPACE Turing machine. Therefore, minimization of regular expressions is PSPACE-hard.</p>
<p>Conversely, equivalence of expressions can be tested in PSPACE, so we can guess an expression of minimal size, and verify that it is correct in PSPACE (which is the same as Nondeterministic PSPACE). Therefore, the minimization problem is in PSPACE as well, and so it is PSPACE-complete.</p>

CC BY-SA 4.0
2022-03-18T14:29:06.620Z
2022-03-18T14:29:06.620Z
Denis
<p>Suppose we have a regular language specified by a regex, for example, (ab|ac)* and we wish to find an equivalent regex with the minimal number of symbols, (a(b|c))*. Is there any efficient way to do this? From what I've read, minimizing the number of states in a DFA is easy, but minimizing a NFA is PSPACE-Complete, and I'm not sure which if either of these it falls under. If it's not tractable, are there any good approximation algorithms or special cases under which it can be done efficiently?</p>

<p>Note: By minimizing the number of symbols, I mean the number of times symbols in the alphabet (a,b,c in the example) appear in the regular expression. The number of parenthesis, | and *s don't matter.</p>

<p>Motivation - this idea comes from the challenge of minimizing program code size, given that if and while statements are the only allowable control flow. The possible paths through the control flow graph correspond to a regular language, with if being union, while being the Kleene star, and symbols representing primitive statements that don't transfer control.</p>

CC BY-SA 3.0
2012-08-20T18:55:09.040Z
what about converting some symbol strings to new symbols? does it have a meaning in your context? disallowed? it would seem to be equivalent to refactoring a particular path into a subroutine? this sounds similar to a compiler code optimization problem...
vzn
CC BY-SA 3.0
2012-08-20T23:33:18.400Z
I read only the abstract, but perhaps this paper is relevant: [Minimizing NFA's and Regular Expressions](http://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.60.5056&rep=rep1&type=pdf). In particular: "... Jiang and Ravikumar [7] show moreover that the minimization problem for nfa's or regular
expressions remains PSPACE-complete, even when specifying the regular language by a dfa ..."
Marzio De Biasi
CC BY-SA 3.0
2012-08-21T00:20:09.730Z
Relevant information: http://en.wikipedia.org/wiki/PSPACE-complete#Determining_if_a_regular_expression_generates_all_strings
Tsuyoshi Ito
CC BY-SA 3.0
2012-08-21T03:47:15.580Z
I guess it is PSPACE complete and not approximable. Oh well, at least the question's been answered.
Antimony
CC BY-SA 3.0
2012-08-21T16:53:36.363Z
the technical meaning of "approximation" may not match what you might think. if you are interested in "application of theory" it may be reasonable to approach it as a compression or optimization problem for which there are heuristics etc. see "grammar compression", it seems to be a special case where the compression is limited to regexps, optimizing by size
vzn
CC BY-SA 3.0
2012-08-21T21:07:09.527Z
I think that regexes are not a suitable representation for program minimization after all. Working with the control flow graph directly is easier.
Antimony
CC BY-SA 3.0
2012-08-21T21:47:36.593Z
there is likely std research & algorithms for optimizing the control flow graph as you have sketched out in compiler optimization literature. but thats another question than the one above. as you note this problem is probably closely related to your question above, [finding the minimal NFA of a DFA](http://cstheory.stackexchange.com/questions/10829/computing-the-minimal-nfa-for-a-dfa)
vzn
CC BY-SA 3.0
2012-08-22T19:00:04.307Z
As you said, I think the control flow chart is more suitable for your needs.
Would it work to treat the graph as a DFA, and run known DFA state minimization algorithms on it in order to identify removable states ? EDIT : sorry, this should really be a comment but, being a noob, I can only post answers
Manuel Lafond
<ds.algorithms><fl.formal-languages><regular-language>
minimizing size of regular expression
Antimony
# minimizing size of regular expression

(Asked by: username_0 on 2012-08-20)

Suppose we have a regular language specified by a regex, for example, (ab|ac)\* and we wish to find an equivalent regex with the minimal number of symbols, (a(b|c))\*. Is there any efficient way to do this? From what I've read, minimizing the number of states in a DFA is easy, but minimizing a NFA is PSPACE-Complete, and I'm not sure which if either of these it falls under. If it's not tractable, are there any good approximation algorithms or special cases under which it can be done efficiently?

Note: By minimizing the number of symbols, I mean the number of times symbols in the alphabet (a,b,c in the example) appear in the regular expression. The number of parenthesis, | and \*s don't matter.

Motivation - this idea comes from the challenge of minimizing program code size, given that if and while statements are the only allowable control flow. The possible paths through the control flow graph correspond to a regular language, with if being union, while being the Kleene star, and symbols representing primitive statements that don't transfer control.

**Tags:** ds.algorithms, fl.formal-languages, regular-language

> **Comments:**
> **username_1**: what about converting some symbol strings to new symbols? does it have a meaning in your context? disallowed? it would seem to be equivalent to refactoring a particular path into a subroutine? this sounds similar to a compiler code optimization problem...  
> **username_2**: I read only the abstract, but perhaps this paper is relevant: [Minimizing NFA's and Regular Expressions](http://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.60.5056&rep=rep1&type=pdf). In particular: "... Jiang and Ravikumar [7] show moreover that the minimization problem for nfa's or regular expressions remains PSPACE-complete, even when specifying the regular language by a dfa ..."  
> **username_3**: Relevant information: http://en.wikipedia.org/wiki/PSPACE-complete#Determining_if_a_regular_expression_generates_all_strings  
> **username_0**: I guess it is PSPACE complete and not approximable. Oh well, at least the question's been answered.  
> **username_1**: the technical meaning of "approximation" may not match what you might think. if you are interested in "application of theory" it may be reasonable to approach it as a compression or optimization problem for which there are heuristics etc. see "grammar compression", it seems to be a special case where the compression is limited to regexps, optimizing by size  
> **username_0**: I think that regexes are not a suitable representation for program minimization after all. Working with the control flow graph directly is easier.  
> **username_1**: there is likely std research & algorithms for optimizing the control flow graph as you have sketched out in compiler optimization literature. but thats another question than the one above. as you note this problem is probably closely related to your question above, [finding the minimal NFA of a DFA](http://cstheory.stackexchange.com/questions/10829/computing-the-minimal-nfa-for-a-dfa)  
> **username_4**: As you said, I think the control flow chart is more suitable for your needs. Would it work to treat the graph as a DFA, and run known DFA state minimization algorithms on it in order to identify removable states ? EDIT : sorry, this should really be a comment but, being a noob, I can only post answers  

---

## 1 answers

### Answer by username_5 on 2022-03-18. Score: 6

It is PSPACE-complete to decide whether an expression accepts all words, i.e. is equivalent to $(a|b|c|...)^\*$. It is not hard to get convinced that in this proof of PSPACE-completeness (see e.g. <https://cstheory.stackexchange.com/a/40250/8953>), when the expression does not accept all words, then it cannot be equivalent to an even shorter expression. Indeed, in this case it must accept everything except a long word that represents a valid encoding of a run of a PSPACE Turing machine. Therefore, minimization of regular expressions is PSPACE-hard.

Conversely, equivalence of expressions can be tested in PSPACE, so we can guess an expression of minimal size, and verify that it is correct in PSPACE (which is the same as Nondeterministic PSPACE). Therefore, the minimization problem is in PSPACE as well, and so it is PSPACE-complete.


---

