ア***ロセッサによる文脈自由言語の並列認識アルゴリズム

概要

論文の詳細を見る
文脈自由言語の認識アルゴリズム(与えられた終端記号列が文脈自由文法で受理されるか否かを判定するアルゴリズム)は、1960年代後半頃に盛んに研究された。よく知られたアルゴリズムには、CYK (Cocke-Younger-Kasami)法とEarley法がある。両アルゴリズムとも、終端記号列の長さをnとすると、計算時間はO(n^3)である。Valiantにより、O(n^2.81)時間のアルゴリズムも考案されている。これらは逐次型のアルゴリズムであったが、近年、計算機パワーの増大を背景に、並列型のアルゴリズムが注目され始めた。近年提案されているアルゴリズムでは、P-RAM (Parallel Random Access Machine)のような理想的な計算モデルを想定し、O(n)の計算時間を達成している。しかし、現実のハードウェアでは、共有メモリを複数のプロセスから同時にアクセスしたり、任意のプロセス間で同時に通信したりするのには、非常に強い制約がある。したがって、メモリアクセスやプロセス間通信がボトルネックとなって、実際にはO(n)時間では動作しない可能性がある。そこで、本稿では、共有メモリは設けず、限定されたプロセス間での通信だけで、文脈自由言語の認識を行なう並列型のアルゴリズムを示す。
一般社団法人情報処理学会の論文
1990-03-14

ア***ロセッサによる文脈自由言語の並列認識アルゴリズム

スポンサーリンク

概要

著者

関連論文

スポンサーリンク