WEKO3
アイテム
木準同型写像を用いた項パターンマッチング
https://ipsj.ixsq.nii.ac.jp/records/16648
https://ipsj.ixsq.nii.ac.jp/records/1664818d3c781-2713-4dee-bdd3-5f25be0b1b60
| 名前 / ファイル | ライセンス | アクション |
|---|---|---|
IPSJ-TPRO4601016.pdf (29.6 kB)
|
Copyright (c) 2005 by the Information Processing Society of Japan
|
|
| オープンアクセス | ||
| Item type | Trans(1) | |||||||
|---|---|---|---|---|---|---|---|---|
| 公開日 | 2005-01-15 | |||||||
| タイトル | ||||||||
| タイトル | 木準同型写像を用いた項パターンマッチング | |||||||
| タイトル | ||||||||
| 言語 | en | |||||||
| タイトル | Term Pattern Matching with Tree Homomorphism | |||||||
| 言語 | ||||||||
| 言語 | jpn | |||||||
| キーワード | ||||||||
| 主題Scheme | Other | |||||||
| 主題 | 発表概要 | |||||||
| 資源タイプ | ||||||||
| 資源タイプ識別子 | http://purl.org/coar/resource_type/c_6501 | |||||||
| 資源タイプ | journal article | |||||||
| 著者所属 | ||||||||
| 東北大学電気通信研究所 | ||||||||
| 著者所属 | ||||||||
| 東北大学電気通信研究所 | ||||||||
| 著者所属 | ||||||||
| 東北大学電気通信研究所 | ||||||||
| 著者所属(英) | ||||||||
| en | ||||||||
| Research Institute of Electrical Communication, Tohoku University | ||||||||
| 著者所属(英) | ||||||||
| en | ||||||||
| Research Institute of Electrical Communication, Tohoku University | ||||||||
| 著者所属(英) | ||||||||
| en | ||||||||
| Research Institute of Electrical Communication, Tohoku University | ||||||||
| 著者名 |
千葉, 勇輝
青戸, 等人
外山, 芳人
× 千葉, 勇輝 青戸, 等人 外山, 芳人
|
|||||||
| 著者名(英) |
Yuki, Chiba
Takahito, Aoto
Yoshihito, Toyama
× Yuki, Chiba Takahito, Aoto Yoshihito, Toyama
|
|||||||
| 論文抄録 | ||||||||
| 内容記述タイプ | Other | |||||||
| 内容記述 | ラムダ計算のパターンマッチングに基づくプログラム自動変換法の枠組みがHuet-Lang (1978) によって提案されている．本発表では，項書き換えシステムに基づくパターンマッチングを実現するために木準同形写像の概念を導入する．はじめに，項パターンマッチングを実現するためのアルゴリズムを提案し，アルゴリズムの正当性を示す．さらに，項パターンマッチングアルゴリズムを項書き換えシステムに適用し，木準同形写像がリダクション関係を保存することを証明する．また，正規形が保存されるべきクラスを示し，木準同形写像によってそのクラスの正規形が保存されるための十分条件を示す．本発表におけるパターンマッチングアルゴリズムは，操作的意味論に基づくプログラム変換の正当性を示す第一歩となると期待される． | |||||||
| 論文抄録(英) | ||||||||
| 内容記述タイプ | Other | |||||||
| 内容記述 | Huet and Lang (1978) developed a framework of automated program transformation using second-order matching algorithm of lambda terms. In this paper, we present a second-order matching algorithm based on term rewriting in which higher-order substitutions are represented by tree homomorphisms. We present term pattern matching algorithm and show its correctness; we then apply the algorithm to match term rewriting systems on term patterns with term rewriting systems. We then show reduction is preserved by tree homomorphisms and give a sufficient condition of tree homomorphisms that map suitable normal patterns to normal terms. Our matching algorithm is a first step to study the correctness of program transformations based on the operational semantics. | |||||||
| 書誌レコードID | ||||||||
| 収録物識別子タイプ | NCID | |||||||
| 収録物識別子 | AA11464814 | |||||||
| 書誌情報 |
情報処理学会論文誌プログラミング（PRO） 巻 46, 号 SIG1(PRO24), p. 151-151, 発行日 2005-01-15 |
|||||||
| ISSN | ||||||||
| 収録物識別子タイプ | ISSN | |||||||
| 収録物識別子 | 1882-7802 | |||||||
| 出版者 | ||||||||
| 言語 | ja | |||||||
| 出版者 | 情報処理学会 | |||||||
