Abstract本研究で得られた成果は以下の(1)(2)である。(1)多重文脈自由言語(mcfl)に対する従来のものより時間計算量の小さい認識アルゴリズムを提案した。(mcfgG)が与えられた時、既存の最速認識アルゴリズムの時間計算量はO(n^e)である。ここで、nは入力系列長で、eはGのみに依存する定数で、Gの自由度と呼はれる。これに対して、本研究で提案した認識アルゴリズムの時間計算量はO(n^<e'-0.624i'+1>)である。equal】i'<e'を満たす。(pmcfg)が提案されている。本研究ではpmcfgに対する従来のものより時間計算量の小さい認識アルゴリズムを提案した。pmcfgGが与えられた時、既存の最速認識アルゴリズムの時間計算量はO(n^<e+1>)である。ここで、nは入力系列長で、eはGのみに依存する定数で、Gの自由度と呼ばれる。これに対して、本研究で提案した認識アルゴリズムの時間計算最はO(n^<e'-0.624i'+1>)である。equal】i'<e'を満たす。mcfgGに対してGと等価なpmcfgG'は常に存在する。G'の自由度はGの自由度以下であり、真に小さい場合もある。