Nejmenší gramatický problém - Smallest grammar problem
v komprese dat a teorie formální jazyky, nejmenší gramatická úloha je problém najít nejmenší bezkontextová gramatika který generuje daný tětiva znaků (ale žádný jiný řetězec). Velikost gramatiky je definována některými autory jako počet symbolů na pravé straně pravidel produkce.[1]Jiní k tomu přidávají také počet pravidel.[2] Problém (rozhodovací verze) je NP-kompletní.[1]Nejmenší bezkontextová gramatika, která generuje daný řetězec, je vždy a přímá gramatika bez zbytečná pravidla.[Citace je zapotřebí ]
Viz také
Reference
- ^ A b Charikar, Mojžíš; Lehman, Eric; Liu, Ding; Panigrahy, Rina; Prabhakaran, Manoj; Sahai, Amit; Shelat, Abhi (2005). „Nejmenší gramatický problém“ (PDF). Transakce IEEE na teorii informací. 51 (7): 2554–2576. CiteSeerX 10.1.1.185.2130. doi:10.1109 / TIT.2005.850116. Zbl 1296.68086.
- ^ Florian Benz a Timo Kötzing, „Efektivní heuristika pro nejmenší gramatický problém,“ Sborník z patnáctého ročníku konference o konferenci Genetické a evoluční výpočty - GECCO ’13, 2013. ISBN 978-1-4503-1963-8 doi:10.1145/2463372.2463441
- Charikar, Mojžíš; Lehman, Eric; Liu, Ding; Panigrahy, Rina; Prabhakaran, Manoj; Rasala, duben; Sahai, Amit; Shelat, Abhi (2002). „Aproximace nejmenší gramatiky: Kolmogorovova složitost v přírodních modelech“ (PDF). Sborník z třicátého čtvrtého ročníku sympózia ACM o teorii výpočetní techniky (STOC 2002), Montreal, Quebec, Kanada, 19. – 21. Května 2002. New York, NY: ACM Press. 792–801. doi:10.1145/509907.510021. ISBN 978-1-581-13495-7. Zbl 1192.68397.
 | Tento algoritmy nebo datové struktury související článek je a pahýl. Wikipedii můžete pomoci pomocí rozšiřovat to. |