Pienin kielioppiongelma

Formaalisten kielten teoriassa pienimmän kieliopin ongelma on ongelma löytää pienin yhteydetön kielioppi , joka tuottaa ainutlaatuisen merkkijonon. Osan tekijöiden kieliopin koko määräytyy päättelysääntöjen oikealla puolella olevien merkkien lukumäärän mukaan. [1] Mutta joskus sääntöjen määrä sisältyy mukaan. [2]

Muistiinpanot

1. ↑ Charikar, Mooses; Lehman, Eric; Liu, Ding; Panigrahy, Rina; Prabhakaran, Manoj; Sahai, Amit; Shelat, Abhi. Pienin kielioppiongelma  // IEEE  Transactions on Information Theory : päiväkirja. - 2005. - Voi. 51 . - P. 2554-2576 . - doi : 10.1109/TIT.2005.850116 .
2. ↑ Florian Benz ja Timo Kötzing, "Tehokas heuristiikka pienimpään kielioppiongelmaan", 15. vuosittaisen geneettisen ja evolutionaarisen laskennan konferenssin julkaisut - GECCO '13, 2013. ISBN 978-1-4503-1963-1963-18 doi . /2463372.2463441

Kirjallisuus

• Charikar, Mooses; Lehman, Eric; Liu, Ding; Panigrahy, Rina; Prabhakaran, Manoj; Rasala, huhtikuu; Sahai, Amit; Shelat, Abhi. Pienimmän kieliopin lähentäminen: Kolmogorov-monimutkaisuus luonnollisissa malleissa // Proceedings of the 34. vuotuinen ACM-symposium on theory of computing (STOC 2002), Montreal, Quebec, Kanada, 19.–21. toukokuuta 2002  (englanniksi) . - New York, NY: Association for Computing Machinery , 2002. - P. 792-801. — ISBN 1-581-13495-9 . - doi : 10.1145/509907.510021 .