弱文脈依存に属する形式文法の性質の解明と高速な認識アルゴリズムの開発

弱上下文相关形式语法的性质阐明和高速识别算法的开发

基本信息

批准号：
17700004
负责人：
藤芳明生
金额：
$ 1.6万
依托单位：
Ibaraki University
依托单位国家：
日本
项目类别：
Grant-in-Aid for Young Scientists (B)
财政年份：
2005
资助国家：
日本
起止时间：
2005 至 2007
项目状态：
已结题

项目摘要

本研究は、Tree Adjoining Grammar(TAG)に代表されるような木構造を生成する木文法に注目し、弱文脈依存に属する形式文法の性質を解明すると共に高速な認識アルゴリズムの開発を行うことを目的としている。特に、TAGと同じ文字列言語のクラスを生成するSpine GrammarおよびLinear Monadic Context-Free Tree Grammarに注目して、研究を進めている。今年度は、前年度に開発した、入力の大きさの3乗のオーダーでLinear Monadic Context-Free Tree Grammarの生成する木構造を認識するアルゴリズムの応用を行った。具体的には、数式OCRの認識精度を向上させるため、OCRに認識結果の検証アルゴリズムの開発を行った。開発したアルゴリズムは様々な高速化の工夫を行い、大変高速に動作する。数学論文のデータベースを利用し、評価実験を行い、本研究が開発したアルゴリズムの有効性を確認することができた。また、決定性・線形プッシュダウン木オートマトンに注目し、それが受理する言語のクラスについて研究を行った。まず、3つの決定性・線形プッシュダウン木オートマトンのバリエーションの定義を行った。それら3つの決定性・線形プッシュダウン木オートマトンが受理する木構造の言語のクラスについて階層が存在すること、また、対応するイールド言語のクラスについては、すべてが一致し、さらには非決定性のものとも一致することが証明された。

这项研究的重点是产生树结构的树语法，例如毗邻语法的树（TAG），旨在阐明属于弱上下文依赖性的形式语法的特性并开发快速识别算法。特别是，我们正在进行研究，重点是脊柱语法和线性单语上下文语法，该语法以与TAG相同的字符串语言生成类。今年，我们应用了上一年开发的一种算法来识别由无上下文的无上下文的树木语法产生的树结构，该算法是按照立方输入大小的顺序创建的。具体而言，为了提高公式OCR的识别精度，我们开发了一种用于验证OCR识别结果的算法。开发的算法旨在提高系统速度并以非常高速运行。使用数学论文数据库，我们进行了评估实验，以确认本研究开发的算法的有效性。我们还专注于确定性和线性下降树自动机，并对他们接受的语言类别进行了研究。首先，我们定义了确定性线性下降树自动机的三种变体。已经证明，存在这三个确定性线性俯卧撑树自动机接受的树结构类别的层次结构，相应的产量语言的类别都是一致甚至不确定性的。