データ圧縮と形式文法理論において、最小文法問題（さいしょうぶんぽうもんだい、英語: smallest grammar problem）は、与えられた文字列を生成する最小の文脈自由文法を見つける問題である。文法のサイズは、生成規則の右側のシンボルの数として定義するとしている者[1]や、それに規則の数を加えるとする者[2]もいる。この問題（の決定版）はNP完全である[1]。
関連項目
脚注
- ^ a b Charikar, Moses; Lehman, Eric; Liu, Ding; Panigrahy, Rina; Prabhakaran, Manoj; Sahai, Amit; Shelat, Abhi (2005). “The Smallest Grammar Problem”. IEEE Transactions on Information Theory 51 (7): 2554–2576. doi:10.1109/TIT.2005.850116. Zbl 1296.68086.
- ^ Florian Benz and Timo Kötzing, “An effective heuristic for the smallest grammar problem,” Proceeding of the fifteenth annual conference on Genetic and evolutionary computation conference - GECCO ’13, 2013. ISBN (978-1-4503-1963-8) doi:10.1145/2463372.2463441
- Charikar, Moses; Lehman, Eric; Liu, Ding; Panigrahy, Rina; Prabhakaran, Manoj; Rasala, April; Sahai, Amit; Shelat, Abhi (2002). “Approximating the Smallest Grammar: Kolmogorov Complexity in Natural Models”. Proceedings of the thirty-fourth annual ACM symposium on theory of computing (STOC 2002), Montreal, Quebec, Canada, May 19–21, 2002. New York, NY: ACM Press. pp. 792–801. doi:10.1145/509907.510021. ISBN (1-581-13495-9). Zbl 1192.68397