• 検索結果がありません。

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

N/A
N/A
Protected

Academic year: 2021

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

Copied!
1
0
0

読み込み中.... (全文を見る)

全文

(1)情報処理学会論文誌. プログラミング. Vol. 2. No. 2. 180 (Mar. 2009). 発表概要. データ列に対する各種アルゴリズムの 逆変換に基づく統一的導出 森. 本. 真. quences and input data are represented as (inherited) attributes for the start symbol and tokens respectively. From such attribute grammars, algorithms that convert input data sequences to target data sequences are derived from parsing algorithms of these grammars with reverse functions of semantic functions for attributes. Furthermore, we also state conditions to derive algorithms from attribute grammars and to improve time complexities of algorithms.. (平成 20 年 10 月 29 日発表). 一†1. 本発表では,ソーティングや最大共通部分列などの入力データ列に関するアルゴリ ズムを,ある条件を満たすデータ列(目的データ列という)から入力データ列への変 換の逆変換として統一的に導出する.たとえば,ソーティングのアルゴリズムは,順 序付けられた目的データ列から入力データ列への変換の逆変換として導出することが できる.また 2 つの入力データ列の共通部分列を求めるアルゴリズムは,共通部分列 である目的データ列から 2 つの入力データ列を生成する変換の逆変換として導出する ことができる.本発表では,ソーティングや最大共通部分列のアルゴリズムを例とし て,目的データ列から入力データ列への変換を,目的データ列と入力記号を開始記号 と終端記号の相続属性とする属性文法(構文記号に属性値が定義される文脈自由文法) として定式化し,求めるアルゴリズム(入力データ列から目的データ列を求めるアル ゴリズム)を属性評価関数の逆関数を用いて,この属性文法の構文解析アルゴリズム として定式化する.さらに本発表では,属性文法の構文規則からアルゴリズムが導出 されるための条件やそのアルゴリズムが効率的であるための条件を述べる.. Systematic Derivation of Various Algorithms for Data Sequences Based on Reverse Conversion Shin-ichi Morimoto†1 In this presentation, we derive various algorithms for data sequences such as sorting and LCS (Longest Common Subsequences) algorithms as reverse conversions from target data sequences to input data sequences. Sorting algorithms can be regarded as reverse conversions of conversions from sorted sequences to input sequences. LCS algorithms can be regarded as reverse conversions of conversions from the common sequence to input sequences. In this presentation, conversions from target data sequences to input data sequences are described as attribute grammars, which are context-free grammars whose syntax symbols are associated with attributes. In these attribute grammars, target data se-. 180. †1 株式会社日本電気航空宇宙システム NEC Aerospace Systems, Ltd.. c 2009 Information Processing Society of Japan .

(2)

参照

関連したドキュメント

Cycle premodules are roughly said functors on elds which have transfer, are modules over Milnor's K -theory, are equipped with residue maps for discrete valuations and satisfy

Comparing the Gauss-Jordan-based algorithm and the algorithm presented in [5], which is based on the LU factorization of the Laplacian matrix, we note that despite the fact that

In the present §3, we establish functorial “group-theoretic” algorithms for reconstruct- ing various objects related to the geometry of the stable models of proper hyperbolic

This article demonstrates a systematic derivation of stochastic Taylor methods for solving stochastic delay differential equations (SDDEs) with a constant time lag, r > 0..

In this section we look at spectral sequences for calculating the homology of the bar and cobar constructions on operads and cooperads in based spaces or spectra.. It turns out that

We presented simple and data-guided lexisearch algorithms that use path representation method for representing a tour for the benchmark asymmetric traveling salesman problem to

Here we purpose, firstly, to establish analogous results for collocation with respect to Chebyshev nodes of first kind (and to compare them with the results of [7]) and, secondly,

All three problems (1*, 2*.1 2*.2) are open; there are conjectures which would provide complete answers to these problems and some partial results supporting these conjectures