データ列に対する各種アルゴリズムの逆変換に基づく統一的導出

概要

論文の詳細を見る
本発表では,ソーティングや最大共通部分列などの入力データ列に関するアルゴリズムを,ある条件を満たすデータ列 (目的データ列という) から入力データ列への変換の逆変換として統一的に導出する.たとえば,ソーティングのアルゴリズムは,順序付けられた目的データ列から入力データ列への変換の逆変換として導出することができる.また 2 つの入力データ列の共通部分列を求めるアルゴリズムは,共通部分列である目的データ列から 2 つの入力データ列を生成する変換の逆変換として導出することができる.本発表では,ソーティングや最大共通部分列のアルゴリズムを例として,目的データ列から入力データ列への変換を,目的データ列と入力記号を開始記号と終端記号の相続属性とする属性文法 (構文記号に属性値が定義される文脈自由文法) として定式化し,求めるアルゴリズム (入力データ列から目的データ列を求めるアルゴリズム) を属性評価関数の逆関数を用いて,この属性文法の構文解析アルゴリズムとして定式化する.さらに本発表では,属性文法の構文規則からアルゴリズムが導出されるための条件やそのアルゴリズムが効率的であるための条件を述べる.
2009-03-23