| 電子情報通信学会 研究会発表申込システム 講演論文 詳細 |
技報閲覧サービス [ログイン] 技報アーカイブ |
| トップに戻る | 前のページに戻る | [Japanese] / [English] |
| 講演抄録／キーワード | ||
| 講演名 | 2007-12-17 10:45 組合せ子の非循環性について ○岩見宗弘（島根大）  SS2007-41 |
|
| 抄録 | （和） | Sumllyanは，書換え規則 L x y -> x (y y)を持つ組合せ子 $L$と書換え規則 O x y -> y (x y)を持つ組合せ子 Oを 提案した． 本稿では, 組合せ子の非循環性に対する十分条件を与える. 最初に, Bergstraらの手法を一般化した組合せ子の非循環性 に対する十分条件を与える. その十分条件を用いて, 組合せ子 LとOの非循環性を示す. また, 組合せ子 O は, Oのみから成る項上で停止性を持たないことを示す. 次に, Waldmannと同様の手法により, 組合せ子 Oは非基礎 ループ性を持つことを示す. 最後に, 書換え規則 L x y -> x (y y)による書換え -> の逆関係 ->^-1が停止性を持つことを示し, %%書換え規則 $L x y \ra x (y y)$を持つ 組合せ子 Lの非循環性の簡潔な証明を与える. さらに, 組合せ子 Lが基礎ループを持つことを示す. |
| （英） | Sumllyan proposed that combinator L with rewrite rule L x y -> x (y y) and combinator O with rewrite rule O x y -> y (x y). In this paper, we give the sufficient condition for acyclicity of combinators. First, we give the sufficient condition for acyclicity of combinators using the generalized method of Bergstra et al. We show that acyclicity of combinators L and O using this condition. Furthermore, we show that combinator O is not terminating on terms consisted of only O. Next, we show that non-ground loopingness of combinator O by similar method of Waldmann. Finally, we show that reverse relation ->^-1 of rewrite step -> by rewrite rule L x y -> x (y y) is terminating and we give the simple proof of acyclicity of combinator L. Furthermore, we show that combinator L has the ground loop. |
|
| キーワード | （和） | 項書換えシステム / 組合せ子 / 組合せ子論理 / 非循環性 / ラムダ計算 / / / |
| （英） | term rewriting system / combinator / combinatory logic / acyclicity / lambda calculus / / / | |
| 文献情報 | 信学技報, vol. 107, no. 392, SS2007-41, pp. 19-24, 2007年12月. | |
| 資料番号 | SS2007-41 | |
| 発行日 | 2007-12-10 (SS) | |
| ISSN | Print edition: ISSN 0913-5685 Online edition: ISSN 2432-6380 | |
| 著作権に ついて |
技術研究報告に掲載された論文の著作権は電子情報通信学会に帰属します．(許諾番号：10GA0019/12GB0052/13GB0056/17GB0034/18GB0034) | |
| PDFダウンロード | SS2007-41 |
|
| 研究会情報 | |
| 研究会 | SS |
| 開催期間 | 2007-12-17 - 2007-12-18 |
| 開催地（和） | 島根大学 |
| 開催地（英） | Shimane Univ. |
| テーマ（和） | 一般 |
| テーマ（英） | general |
| 講演論文情報の詳細 | |
| 申込み研究会 | SS |
| 会議コード | 2007-12-SS |
| 本文の言語 | 日本語 |
| タイトル（和） | 組合せ子の非循環性について |
| サブタイトル（和） | |
| タイトル（英） | On the Acyclicity of Combinators |
| サブタイトル（英） | |
| キーワード(1)（和/英） | 項書換えシステム / term rewriting system |
| キーワード(2)（和/英） | 組合せ子 / combinator |
| キーワード(3)（和/英） | 組合せ子論理 / combinatory logic |
| キーワード(4)（和/英） | 非循環性 / acyclicity |
| キーワード(5)（和/英） | ラムダ計算 / lambda calculus |
| キーワード(6)（和/英） | / |
| キーワード(7)（和/英） | / |
| キーワード(8)（和/英） | / |
| 第1著者 氏名（和/英/ヨミ） | 岩見 宗弘 / Munehiro Iwami / イワミ ムネヒロ |
| 第1著者 所属（和/英） | 島根大学 (略称： 島根大) Shimane University (略称： Shimane Univ.) |
| 講演者 | 第1著者 |
| 発表日時 | 2007-12-17 10:45:00 |
| 発表時間 | 30分 |
| 申込先研究会 | SS |
| 資料番号 | SS2007-41 |
| 巻番号（vol） | vol.107 |
| 号番号（no） | no.392 |
| ページ範囲 | pp.19-24 |
| ページ数 | 6 |
| 発行日 | 2007-12-10 (SS) |
[研究会発表申込システムのトップページに戻る]