El problema gramatical más pequeño

En compresión de datos y teoría de lenguajes formales , el problema de la gramática más pequeña consiste en encontrar la gramática libre de contexto más pequeña que genere una cadena de caracteres dada (pero ninguna otra). Algunos autores definen el tamaño de una gramática como el número de símbolos en el lado derecho de las reglas de producción. ^{[ 1 ]} Otros también suman el número de reglas. ^{[ 2 ]} Una gramática que genera una sola cadena, como se requiere para la solución de este problema, se denomina gramática lineal . ^{[ 3 ]}

Cada cadena binaria de longitud${\displaystyle n}$tiene una gramática de longitud${\displaystyle O(n/\log n)}$, como se expresa usando la notación de la gran O. ^{[ 3 ]} Para secuencias binarias de De Bruijn , no es posible una longitud mejor. ^{[ 4 ]}

El problema de gramática más pequeño (versión de decisión) es NP-completo . ^{[ 1 ]} Se puede aproximar en tiempo polinomial con una razón de aproximación logarítmica ; más precisamente, la razón es${\displaystyle O(\log {\tfrac {n}{g}})}$dónde${\displaystyle n}$es la longitud de la cadena dada y${\displaystyle g}$es el tamaño de su gramática más pequeña. Es difícil aproximarlo dentro de una razón de aproximación constante. Una mejora de la razón de aproximación a${\displaystyle o(\log n/\log \log n)}$También mejoraría ciertos algoritmos para cadenas de suma aproximadas . ^{[ 5 ]}

• Código basado en gramática
• complejidad de Kolmogorov
• Compresión de datos sin pérdidas

• "La complejidad CFG-Kolm se basa en conjuntos singleton con Lance y Bill" . Complejidad Computacional . 9 de junio de 2024.