smallest grammar problem

In data compression and the theory of formal languages, the smallest grammar problem is the problem of finding the smallest context-free grammar that generates a given string of characters (but no other string). The size of a grammar is defined by some authors as the number of symbols on the right side of the production rules.

Others also add the number of rules to that.Florian Benz and Timo Kötzing, “An effective heuristic for the smallest grammar problem,” Proceedings of the fifteenth annual conference on Genetic and evolutionary computation conference - GECCO ’13, 2013. {{isbn|978-1-4503-1963-8}} {{doi|10.1145/2463372.2463441}} A grammar that generates only a single string, as required for the solution to this problem, is called a straight-line grammar.{{cite journal

| last = Lohrey | first = Markus

| doi = 10.1515/GCC-2012-0016

| issue = 2

| journal = Groups Complexity Cryptology

| pages = 241–299

| title = Algorithmics on SLP-compressed strings: A survey

| url = https://www.eti.uni-siegen.de/ti/veroeffentlichungen/12-survey.pdf

| volume = 4

| year = 2012}}

Every binary string of length $n$ has a grammar of length $O(n/\backslash log\; n)$, as expressed using big O notation. For binary de Bruijn sequences, no better length is possible.{{cite journal

| last1 = Domaratzki | first1 = Michael

| last2 = Pighizzini | first2 = Giovanni

| last3 = Shallit | first3 = Jeffrey

| doi = 10.1016/S0020-0190(02)00316-2

| issue = 6

| journal = Information Processing Letters

| mr = 1937222

| pages = 339–344

| title = Simulating finite automata with context-free grammars

| volume = 84

| year = 2002}}

The (decision version of the) smallest grammar problem is NP-complete.{{cite journal | title=The Smallest Grammar Problem| journal=IEEE Transactions on Information Theory| year=2005|url=https://scholar.archive.org/work/kkxmd4etnzahze4vi35kkhnwze | doi=10.1109/TIT.2005.850116 | last1=Charikar | first1=Moses | last2=Lehman | first2=Eric | last3=Liu | first3=Ding | last4=Panigrahy | first4=Rina | last5=Prabhakaran | first5=Manoj | last6=Sahai | first6=Amit | last7=Shelat | first7=Abhi | zbl=1296.68086 | volume=51 | number=7 | pages=2554–2576 | citeseerx=10.1.1.185.2130| s2cid=6900082}}

It can be approximated in polynomial time to within a logarithmic approximation ratio; more precisely, the ratio is $O(\backslash log\backslash tfrac\{n\}\{g\})$ where $n$ is the length of the given string and $g$ is the size of its smallest grammar. It is hard to approximate to within a constant approximation ratio. An improvement of the approximation ratio to $o(\backslash log\; n/\backslash log\backslash log\; n)$ would also improve certain algorithms for approximate addition chains.{{cite book| last1=Charikar | first1=Moses | last2=Lehman | first2=Eric | last3=Liu | first3=Ding | last4=Panigrahy | first4=Rina | last5=Prabhakaran | first5=Manoj | last6=Rasala | first6=April | last7=Sahai | first7=Amit | last8=Shelat | first8=Abhi| chapter=Approximating the Smallest Grammar: Kolmogorov Complexity in Natural Models| chapter-url=http://theory.lcs.mit.edu/~arasala/papers/grammar.pdf | zbl=1192.68397 | title=Proceedings of the thirty-fourth annual ACM symposium on theory of computing (STOC 2002), Montreal, Quebec, Canada, May 19–21, 2002 | location=New York, NY | publisher=ACM Press | isbn=978-1-581-13495-7 | pages=792–801 | year=2002 | doi=10.1145/509907.510021 | s2cid=282489 }}