2008-07-09 [長年日記]
λ. 文脈自由文法のパーサの計算量
文脈自由文法のパーサで良く知られているのは CYK algorithm や Earley parser で、これらの計算量は O(m3) なのだけど、文脈自由文法の計算量は O(m2.???) だという話を以前に向井先生から聞いたことがあった。 これはどうやるんだろうなぁとずっと思っていたが、Boolean Matrix Multiplication (BMM) というものを使うそうだ。
(後で書くかも)
参考: Fast context-free grammar parsing requires fast boolean matrix multiplication
[ツッコミを入れる]
