New answers tagged approximation-hardness
4
votes
Finding a minimal context free grammar that recognizes a finite set of strings of bounded length
The following inapproximability result is known (Theorem 17 in Gruber/Holzer/Wolfsteiner, DLT 2018):
Given a context-free grammar of size $s$ generating a finite
language $L$, it is impossible to ...
- 5,840
Top 50 recent answers are included