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
2
votes
What is the current state of the art in black-box grammar induction?
Note that there is now a replication study (coauthored by Rahul Gopinath) of the 2017 paper Synthesizing Program Input Grammars, see https://publications.cispa.saarland/3607/1/pldi2022glade.pdf
Two ...
- 11.4k
1
vote
Pumping lemma for CFL intersection
The language $L_t=\{a_1^na_2^n\dots a_t^n:n\ge 0, a_i=a$ for odd $i$ and $a_i=b$ for even $i\}$ is the intersection of two CFL's, even $\cup_t~L_t$ is, and it is hard to imagine what kind of pumping ...
- 13.9k
1
vote
Is it known if $\mathrm{CFL} \subseteq\mathrm{ NSPACE}(o(log^2(n)))$?
It is not known whether CFL is contained in space o(log^2(n)). If CFL were contained in space o(log^2(n)), then NL would also be contained in space o(log^2(n)). The question whether NL is contained in ...
- 19
Only top scored, non community-wiki answers of a minimum length are eligible