コンテンツにスキップ

英文维基 | 中文维基 | 日文维基 | 草榴社区

最小文法問題

出典: フリー百科事典『ウィキペディア(Wikipedia)』

データ圧縮形式文法理論において、最小文法問題(さいしょうぶんぽうもんだい、英語: smallest grammar problem)は、与えられた文字列を生成する最小の文脈自由文法を見つける問題である。文法のサイズは、生成規則の右側のシンボルの数として定義するとしている者[1]や、それに規則の数を加えるとする者[2]もいる。この問題(の決定版)はNP完全である[1]

関連項目

[編集]

脚注

[編集]
  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. http://www.cs.virginia.edu/~shelat/papers/GrammarIEEE.pdf. 
  2. ^ 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