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"
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): 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 (4). 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 (7).
- For $L \subseteq \{0,1\}^m$ and input described as a truth table, the minimum equivalent NFA problem is ${\bf NP}$-complete, see (7).
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$.
