The CFG Complexity of Singleton Sets
| Autor: | Fortnow, Lance, Gasarch, William |
|---|---|
| Rok vydání: | 2024 |
| Předmět: | |
| Druh dokumentu: | Working Paper |
| Popis: | 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. Comment: Most results already known |
| Databáze: | arXiv |
| Externí odkaz: |
|