El problema de gramática mínima

En la teoría de los lenguajes formales , el problema de la gramática más pequeña es el problema de encontrar la gramática libre de contexto más pequeña que genera una secuencia única de caracteres. El tamaño de la gramática por parte de los autores está determinado por el número de caracteres en el lado derecho de las reglas de inferencia. [1] Pero a veces se incluye el número de reglas. [2]

Notas

  1. ↑ Charikar, Moisés; Lehman, Eric; Liu, Ding; Panigrahy, Rina; Prabhakaran, Manoj; Sahai, Amit; Shelat, Abhi. El problema gramatical más pequeño  //  Transacciones IEEE sobre teoría de la información : diario. - 2005. - vol. 51 . - P. 2554-2576 . -doi : 10.1109/ TIT.2005.850116 .
  2. ↑ 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

Literatura