講演抄録/キーワード |
講演名 |
2015-03-10 09:30
木構造データを扱う関数の逆Unfold問題の発見的解法 ○加藤友郁・長島正憲・酒井正彦・西田直樹・坂部俊樹(名大) SS2014-69 |
抄録 |
(和) |
Unfold/Fold変換はプログラム変換や定理証明などに広く利用されている.
Unfold変換とFold変換はそれぞれの逆変換の関係にはなく,多くの場合において一方の変換結果を他方の変換で元に戻すことはできない.
そのため,Unfold変換の逆変換を行うことを目的とすることは意味があり,逆Unfold問題とその発見的解法が提案された.
しかし,この発見的解法では自然数やリストなどの線形なデータ構造を引数に取る関数に対する逆Unfold問題しか解くことができない.
本稿では,発見的解法の手順の一つであるタグ付けの手法を拡張することで,二分木などの非線形なデータ構造を引数に取る関数に対しても逆Unfold問題を解くことができるようにする. |
(英) |
Unfold/Fold transformations have been widely used for program transformation, theorem proving, and so on.
Unfold and Fold are not in the inverse relation of each other, and a transformational result of Unfold is generally not restorable by Fold, and vice versa.
Therefore, the inverse Unfolding problem make sense and a heuristic solving for it have been proposed.
The method, however, only covers the inverse Unfolding problem for functions with linear data structures (e.g. natural numbers, lists).
This paper extends the tagging method used in the heuristic to functions with non-linear data structures (e.g. binary trees). |
キーワード |
(和) |
Unfold/Fold変換 / 項書換え系 / / / / / / |
(英) |
Unfold/Fold transformation / term rewriting system / / / / / / |
文献情報 |
信学技報, vol. 114, no. 510, SS2014-69, pp. 85-90, 2015年3月. |
資料番号 |
SS2014-69 |
発行日 |
2015-03-02 (SS) |
ISSN |
Print edition: ISSN 0913-5685 Online edition: ISSN 2432-6380 |
著作権に ついて |
技術研究報告に掲載された論文の著作権は電子情報通信学会に帰属します.(許諾番号:10GA0019/12GB0052/13GB0056/17GB0034/18GB0034) |
PDFダウンロード |
SS2014-69 |