| 講演名 | 2006-02-03 関数プログラムの停止性証明のための辞書式経路順序 星野 由美, 草刈 圭一朗, 酒井 正彦, 坂部 俊樹, 西田 直樹, |
|---|---|
| PDFダウンロードページ |  PDFダウンロードページへ |
| 抄録(和) | 項書き換え系は関数プログラムの計算モデルであり,停止性はその重要な性質の一つである.停止性証明法の一つに簡約化順序によって順序付ける方法がある.代表的な簡約化順序としては辞書式経路順序が知られており,その整礎性は単純化順序の概念を用いて保証される.本稿では,高階関数を扱うことができるように拡張した辞書式経路順序を3種類提案する.そして,様々な項の集合上でそれらが持つ性質を明らかにする. |
| 抄録(英) | Term rewriting system is a computational model of functional programs, and termination is one of the important properties. Reduction order is an important tool for proving termination. As typical reduction orders, we know lexicographic path orderings whose well-foundedness are ensured by the notion of simplification order. In this paper, we propose three extended lexicographic path orderings in order to deal with higher-order functions. Additionally, we analyze their properties under several constraints. |
| キーワード(和) | 辞書式経路順序 / 簡約化順序 / 単純化順序 / 停止性 / 高階関数 |
| キーワード(英) | Lexicographic Path Ordering / Reduction Order / Simplification Order / Termination / Higher-Order Function |
| 資料番号 | SS2005-85 |
| 発行日 |
| 研究会情報 | |
| 研究会 | SS |
|---|---|
| 開催期間 | 2006/1/27(から1日開催) |
| 開催地（和） | |
| 開催地（英） | |
| テーマ（和） | |
| テーマ（英） | |
| 委員長氏名（和） | |
| 委員長氏名（英） | |
| 副委員長氏名（和） | |
| 副委員長氏名（英） | |
| 幹事氏名（和） | |
| 幹事氏名（英） | |
| 幹事補佐氏名（和） | |
| 幹事補佐氏名（英） | |
| 講演論文情報詳細 | |
| 申込み研究会 | Software Science (SS) |
|---|---|
| 本文の言語 | JPN |
| タイトル（和） | 関数プログラムの停止性証明のための辞書式経路順序 |
| サブタイトル（和） | |
| タイトル（英） | Lexicographic Path Ordering for Proving Termination of Functional Programs |
| サブタイトル（和） | |
| キーワード(1)（和/英） | 辞書式経路順序 / Lexicographic Path Ordering |
| キーワード(2)（和/英） | 簡約化順序 / Reduction Order |
| キーワード(3)（和/英） | 単純化順序 / Simplification Order |
| キーワード(4)（和/英） | 停止性 / Termination |
| キーワード(5)（和/英） | 高階関数 / Higher-Order Function |
| 第 1 著者 氏名（和/英） | 星野 由美 / Yumi HOSHINO |
| 第 1 著者 所属（和/英） | 名古屋大学工学部電気電子・情報工学科 Department of Information Engineering, School of Engineering, Nagoya University |
| 第 2 著者 氏名（和/英） | 草刈 圭一朗 / Keiichirou KUSAKARI |
| 第 2 著者 所属（和/英） | 名古屋大学大学院情報科学研究科 Graduate School of Information Science, Nagoya University |
| 第 3 著者 氏名（和/英） | 酒井 正彦 / Masahiko SAKAI |
| 第 3 著者 所属（和/英） | 名古屋大学大学院情報科学研究科 Graduate School of Information Science, Nagoya University |
| 第 4 著者 氏名（和/英） | 坂部 俊樹 / Toshiki SAKABE |
| 第 4 著者 所属（和/英） | 名古屋大学大学院情報科学研究科 Graduate School of Information Science, Nagoya University |
| 第 5 著者 氏名（和/英） | 西田 直樹 / Naoki NISHIDA |
| 第 5 著者 所属（和/英） | 名古屋大学大学院情報科学研究科 Graduate School of Information Science, Nagoya University |
| 発表年月日 | 2006-02-03 |
| 資料番号 | SS2005-85 |
| 巻番号（vol） | vol.105 |
| 号番号（no） | 597 |
| ページ範囲 | pp.- |
| ページ数 | 6 |
| 発行日 | |