Problema minimă de gramatică

În teoria limbajelor formale , problema celei mai mici gramatici este problema găsirii celei mai mici gramatici fără context care generează o secvență unică de caractere. Mărimea gramaticii de către o parte a autorilor este determinată de numărul de caractere din partea dreaptă a regulilor de inferență. [1] Dar uneori este inclus și numărul de reguli. [2]

Note

1. ↑ Charikar, Moise; Lehman, Eric; Liu, Ding; Panigrahy, Rina; Prabhakaran, Manoj; Sahai, Amit; Shelat, Abhi. Cea mai mică problemă de gramatică  // IEEE  Transactions on Information Theory : jurnal. - 2005. - Vol. 51 . - P. 2554-2576 . - doi : 10.1109/TIT.2005.850116 .
2. ↑ Florian Benz și Timo Kötzing, „O euristică eficientă pentru cea mai mică problemă de gramatică”, Proceedings of the fifteenth annual conference on Genetic and evolutionary computation Conference - GECCO '13, 2013. ISBN 978-1-4503-1963-8 doi : 10.111 /2463372.2463441

Literatură

• Charikar, Moise; Lehman, Eric; Liu, Ding; Panigrahy, Rina; Prabhakaran, Manoj; Rasala, aprilie; Sahai, Amit; Shelat, Abhi. Aproximarea celei mai mici gramatici: complexitatea Kolmogorov în modelele naturale // Proceedings of the34th annual ACM symposium on theory of computing (STOC 2002), Montreal, Quebec, Canada, May 19–21, 2002  (English) . - New York, NY: Association for Computing Machinery , 2002. - P. 792-801. — ISBN 1-581-13495-9 . - doi : 10.1145/509907.510021 .