14
$\begingroup$

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.

Improve this question
$\endgroup$
8
  • $\begingroup$ 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... $\endgroup$
    – vzn
    Commented Aug 20, 2012 at 18:55
  • 5
    $\begingroup$ I read only the abstract, but perhaps this paper is relevant: Minimizing NFA's and Regular Expressions. 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 ..." $\endgroup$
    – Marzio De Biasi
    Commented Aug 20, 2012 at 23:33
  • 1
    $\begingroup$ Relevant information: en.wikipedia.org/wiki/… $\endgroup$
    – Tsuyoshi Ito
    Commented Aug 21, 2012 at 0:20
  • 1
    $\begingroup$ I think that regexes are not a suitable representation for program minimization after all. Working with the control flow graph directly is easier. $\endgroup$
    – Antimony
    Commented Aug 21, 2012 at 21:07
  • 1
    $\begingroup$ 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 $\endgroup$
    – Manuel Lafond
    Commented Aug 22, 2012 at 19:00

1 Answer 1

Reset to default
6
$\begingroup$

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.

Improve this answer
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.