最小文法問題
出典: フリー百科事典『ウィキペディア（Wikipedia）』 (2022/10/30 21:03 UTC 版)
データ圧縮と形式文法理論において、最小文法問題（さいしょうぶんぽうもんだい、英語: 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
[続きの解説]
「最小文法問題」の続きの解説一覧
- 1 最小文法問題とは
- 2 最小文法問題の概要
- 最小文法問題のページへのリンク
