2024-03-30T13:38:37Zhttps://ipsj.ixsq.nii.ac.jp/ej/?action=repository_oaipmhoai:ipsj.ixsq.nii.ac.jp:001183742023-11-17T02:17:36Z06504:07974:07977
多重文脈自由文法のある部分クラスに対する効率の良い構文解析法についてAn Efficient Parsing Algorithm for a Subclass of Multiple Context-free Grammarsjpnhttp://id.nii.ac.jp/1001/00118491/Conference Paperhttps://ipsj.ixsq.nii.ac.jp/ej/?action=repository_action_common_download&item_id=118374&item_no=1&attribute_id=1&file_no=1大阪大学 基礎工学部 情報工学科大阪大学 基礎工学部 情報工学科大阪大学 教養部大阪大学 基礎工学部 情報工学科中西, 隆一関, 浩之藤井, 護嵩, 忠雄自然言語の構文記述のための形式文法として,多重文脈自由文法(以下mcfgと略記)が提案されている.mcfgでは,respectively文や倒置文のような互いに割り込んだ構文を自然に記述することができる.その生成能力は,文脈自由文法(以下cfgと略記)や,同じく自然言語の構文記述のためにPollardによって導入されたhead grammarよりも真に大きく,文脈規定文法よりも真に小さい.また,mcfg Gに対して,入力系列αがGの生成する言語に属するかどうかを判定する時間計算量0(n^e)(nは入力系列長)のアルゴリズムが提案されている.ここで,eはGのみに依存して定まる定数であるが,その上界は知られていない.本稿では,mcfgのある部分クラスに対する時間計算量0(n^2)の構文解析アルゴリズムを提案する.この部分クラスに属するmcfgの生成する言語のクラスは,あいまいでないcfgの生成する言語をすべて含み,言語{a_1^pb_1^qa_2^pb_2^q…a_m^pb_m^q|p,q≧1}(m≧1),{wcw|∈{O,1}^+}等も含む.AN00349328全国大会講演論文集第40回人工知能及び認知科学3353361990-03-142015-01-20