The CFG Complexity of Singleton Sets
Fuente:
arXiv
Gespeichert in:
| Hauptverfasser: | , |
|---|---|
| Format: | Preprint |
| Veröffentlicht: |
2024
|
| Schlagworte: | |
| Online-Zugang: | |
| Tags: |
Tag hinzufügen
Keine Tags, Fügen Sie den ersten Tag hinzu!
|
| _version_ | 1866913373097033728 |
|---|---|
| author | Fortnow, Lance Gasarch, William |
| author_facet | Fortnow, Lance Gasarch, William |
| contents | 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. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2405_20026 |
| institution | arXiv |
| publishDate | 2024 |
| record_format | arxiv |
| spellingShingle | The CFG Complexity of Singleton Sets Fortnow, Lance Gasarch, William Formal Languages and Automata Theory F.4 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. |
| title | The CFG Complexity of Singleton Sets |
| topic | Formal Languages and Automata Theory F.4 |
| url | https://arxiv.org/abs/2405.20026 |