The CFG Complexity of Singleton Sets
<|reference_start|>The CFG Complexity of Singleton Sets: Let G be a context-free grammar (CFG) in Chomsky normal form. We take the number of rules in G to be the size of G. We also assume all CFGs are in Chomsky normal form.   We consider the question of, given a string w of length n, what is the smallest CFG such that L(G)={w}? We show the following:   1) For all w, |w|=n, there is a CFG of size with O(n/log n) rules, such that L(G)={w}.   2) There exists a string w, |w|=n, such that every CFG G with L(G)={w} is of size Omega(n/log n). We give two proofs of: one nonconstructive, the other constructive.<|reference_end|>
@article{fortnow2024the,
    title={The CFG Complexity of Singleton Sets},
    author={Lance Fortnow and William Gasarch},
    journal={arXiv preprint arXiv:2405.20026},
    year={2024},
    archivePrefix={arXiv},
    eprint={2405.20026},
    primaryClass={cs.FL}
}