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

バックトラックのないマッチングオートマトンを用いたXML変換のためのアルゴリズム

N/A
N/A
Protected

Academic year: 2021

シェア "バックトラックのないマッチングオートマトンを用いたXML変換のためのアルゴリズム"

Copied!
1
0
0

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

全文

(1)情報処理学会論文誌. プログラミング. Vol. 3. No. 4. 63 (Sep. 2010). 発表概要. バックトラックのないマッチングオートマトンを用いた XML 変換のためのアルゴリズム 柴 田 裕 哉†1. 鈴. 木. 大. 郎†2. track from a given term rewriting system. In pattern matching of hedges, new methods for excluding back-track are needed because the length of a sequence substituted for variables is not clear. Therefore, we explain methods for excluding back-track in this presentation. The algorithm 2 is based on the adaptive strategy, variant of a lazy evaluation strategy used in lazy functional languages such as Haskell. In adopting the adaptive strategy, XML transformation based on lazy evaluation is possible.. (平成 22 年 3 月 16 日発表). XML 文書をヘッジとして扱い,ヘッジを対象とした書き換え系に基づく,XML 変 換のためのアルゴリズムの設計を行った.このアルゴリズムは,1) ヘッジ書き換え規 則間の優先順位を考慮したヘッジ書き換え系をマッチングオートマトンに変換するア ルゴリズム,2) オートマトンを効率良く運用するための書き換えアルゴリズムの 2 種 類のアルゴリズムから成り立っている.1) のアルゴリズムは,Nedja らによる項書 き換え系からバックトラックを排除したマッチングオートマトンを生成する方法を拡 張してヘッジ書き換え系のための,決定性マッチングオートマトンを生成するアルゴ リズムである.ヘッジのパターン照合では,変数に代入できる列の長さがあらかじめ 分からないため,バックトラックを排除するための新たな手法が必要となる.本発表 では変数を含むパターンとヘッジとのパターンマッチングでバックトラックを排除す るための手法について述べる.2) のアルゴリズムは,1) のアルゴリズムによって生 成されるマッチングオートマトンを効率良く運用するための,適用戦略を基にした書 き換えアルゴリズムである.適用戦略とは,Haskell らの関数型言語に用いられるの と同様な遅延評価型の戦略である.適用戦略を採用することで,遅延評価に基づいた XML 変換が可能になる.. Algorithm for XML Transformation Based on a Matching Automaton without Backtrack Yuya Shibata†1 and Taro Suzuki†2 We design an algorithm for XML transformation based on hedge rewriting systems. This algorithm consists of two parts: 1) the algorithm that transforms a hedge rewriting system into a matching automaton taking account of priorities and 2) the algorithm for efficient operation of the matching automaton in order to perform rewriting of hedges. The algorithm 1 genetrates a deterministic matching automaton for hedge rewriting system based on the method proposed by Nedja, which generates a matching automaton that excludes back-. 63. †1 会津大学大学院コンピュータ理工学研究科コンピュータ情報システム学専攻 Graduate School of Computer Science and Engineering, Department of Computer and Information Systems, The University of Aizu †2 会津大学コンピュータ理工学部 The School of Computer Science and Engineering, The University of Aizu. c 2010 Information Processing Society of Japan .

(2)

参照

関連したドキュメント

5 used an improved version of particle swarm optimization algorithm in order to solve the economic emissions load dispatch problem for a test system of 6 power generators, for

Using right instead of left singular vectors for these examples leads to the same number of blocks in the first example, although of different size and, hence, with a different

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

1 Miko laj Marciniak was supported by Narodowe Centrum Nauki, grant number 2017/26/A/ST1/00189 and.. Narodowe Centrum Bada´ n i Rozwoju, grant

The main idea of computing approximate, rational Krylov subspaces without inversion is to start with a large Krylov subspace and then apply special similarity transformations to H

modular proof of soundness using U-simulations.. & RIMS, Kyoto U.). Equivalence

As we saw before, the first important object for computing the Gr¨ obner region is the convex hull of a set of n > 2 points, which is the frontier of N ew(f ).. The basic

A common method in solving ill-posed problems is to substitute the original problem by a family of well-posed i.e., with a unique solution regularized problems.. We will use this