これに対し, 本論文では論理行列の積を利用した O(ne'-3i'+1・M(ni')) 時間の アルゴリズムを提案する. ここで, e', i' は G のみに依 存して決まる定数であり, e'≦ e, i'≧ 0 を満たす. そして M(k) は k×k 論理行列の積を求めるのに要する時間である. M(k) の値として O(k2.376) の値が知られているので, e'=e, i=0 の場合を除いて, 本アルゴリズムの時間計算量は既知のものよりも小さい. また, PMCFG を拡張した, 拡張並列多重文脈自由文法(E-PMCFG)を提案した. その生成能力は PMCFG より大きく, 文脈規定文法(CSG)より小さい. そして, E-PMCFG G に対して, G の認識問題を解く, O(n2m(e-1)+1) 時間の 認識アルゴリズムを提案した. ここで, e, m はG のみに依存 して決まる定数である.