15
$\begingroup$

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.

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.

Improve this question
$\endgroup$
3
  • 3
    $\begingroup$ This seems related to grammar based codes. $\endgroup$ – adrianN Mar 13 '13 at 11:58
  • $\begingroup$ 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.... $\endgroup$ – vzn Mar 13 '13 at 15:48
  • $\begingroup$ other angle. RE "derivatives" introduced by brzozowski are known to be useful for converting REs directly into DFAs see eg Regular-expression derivatives reexamined 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.... $\endgroup$ – vzn Mar 13 '13 at 20:31
4
$\begingroup$

The following argument is essentially from (1): The decision versions of the two problems are contained in the second level of the 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 (1). Here, ${\bf DP}$ stands for "difference polynomial time"; this is the "Sigma" complexity class at the second level of the Boolean hierarchy.
  • For input described as a list of words, the minimum equivalent NFA problem is ${\bf NP}$-hard, see (2).
  • For $L \subseteq \{0,1\}^m$ and input described as a truth table, the minimum equivalent NFA problem is ${\bf NP}$-complete, see (2).

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. 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. 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$.

Improve this answer
$\endgroup$
-6
$\begingroup$

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) 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.

Improve this answer
$\endgroup$
2
  • 4
    $\begingroup$ This question was asked specifically because of this paper doesn't address what happens when the language is finite. $\endgroup$ – Chao Xu Mar 13 '13 at 23:32
  • 1
    $\begingroup$ 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. $\endgroup$ – vzn Mar 14 '13 at 2:49

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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