Problema de gramática más pequeño - Smallest grammar problem
En la compresión de datos y la teoría de los lenguajes formales , el problema gramatical más pequeño es el problema de encontrar la gramática libre de contexto más pequeña que genere una determinada cadena de caracteres (pero ninguna otra cadena). 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. Otros también agregan la cantidad de reglas a eso. La (versión de decisión del) problema es NP-completo . La gramática libre de contexto más pequeña que genera una cadena dada es siempre una gramática de línea recta sin reglas inútiles .
Ver también
Referencias
- Charikar, Moisés; Lehman, Eric; Liu, Ding; Panigrahy, Rina; Prabhakaran, Manoj; Rasala, abril; Sahai, Amit; Shelat, Abhi (2002). "Aproximación de la gramática más pequeña: complejidad de Kolmogorov en modelos naturales" (PDF) . Actas del trigésimo cuarto simposio anual de ACM sobre teoría de la computación (STOC 2002), Montreal, Quebec, Canadá, 19-21 de mayo de 2002 . Nueva York, NY: ACM Press. págs. 792–801. doi : 10.1145 / 509907.510021 . ISBN 978-1-581-13495-7. Zbl 1192.68397 .
 |
Este artículo relacionado con algoritmos o estructuras de datos es un fragmento . Puedes ayudar a Wikipedia expandiéndolo . |