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. [1] Otros también agregan el número de reglas a eso. [2] La (versión de decisión del) problema es NP-completo . [1] 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 .[ cita requerida ]
Ver también
Referencias
- ^ a b Charikar, Moisés; Lehman, Eric; Liu, Ding; Panigrahy, Rina; Prabhakaran, Manoj; Sahai, Amit; Shelat, Abhi (2005). "El problema de gramática más pequeño" (PDF) . Transacciones IEEE sobre teoría de la información . 51 (7): 2554-2576. CiteSeerX 10.1.1.185.2130 . doi : 10.1109 / TIT.2005.850116 . Zbl 1296.68086 .
- ^ Florian Benz y Timo Kötzing, "Una heurística eficaz para el problema gramatical más pequeño", Actas de la decimoquinta conferencia anual sobre la conferencia de computación genética y evolutiva - GECCO '13, 2013. ISBN 978-1-4503-1963-8 doi : 10.1145 / 2463372.2463441
- 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 .