データ列に関するアルゴリズムの属性文法の逆変換に基づく導出
スポンサーリンク
概要
- 論文の詳細を見る
本発表では,ソーティングや最長上昇部分列などの入力データ列の変換に関するアルゴリズムを,属性文法の逆変換として導出する方法を述べる.この方法では,求めるアルゴリズムを入力データ列からある条件を満たすデータ(目的データという)への変換と考え,目的データから入力データ列への変換を属性文法として記述する.この属性文法の各属性評価関数の逆関数を考えることにより,求めるアルゴリズムをこの属性文法の逆変換として導出する.たとえば,ソーティングのアルゴリズムでは,まず目的データであるソートされたデータ列から入力データ列への変換を,目的データを開始記号の相続属性とし,入力データ列の各要素を終端記号の相続属性とする.開始記号から終端記号列を生成する属性文法として表現する.この属性文法の各属性評価関数の逆関数を考えることにより,この属性文法の逆変換つまり終端記号列の構文解析時に入力データの各要素の合成属性から開始記号の合成属性として目的データを求める属性文法としてソーティングアルゴリズムを導出できる.本発表では,ある条件を満たす属性評価関数からその逆関数を対応させる方法および本方式と動的計画法の関連について述べる.さらに本発表では,導出されたアルゴリズムの時間計算量の向上および構造的帰納法や構成的アルゴリズム論などの他のプログラム変換方式との関連について述べる.
- 2009-11-20
著者
関連論文
- データ列に関するアルゴリズムの逆変換に基づく導出
- データ列に対する各種アルゴリズムの逆変換に基づく統一的導出
- データ列に関するアルゴリズムの属性文法の逆変換に基づく導出
- データ列に関するアルゴリズムの属性文法の逆変換に基づく導出
- 枝刈り式構文解析法の効率化と自然言語解析への応用
- あいまい性が強い文脈自由文法の枝刈りに基づく効率的な構文解析
- カテゴリ理論による構文解析アルゴリズムの導出
- カテゴリ理論による構文解析アルゴリズムの導出