講演名 | 1999/4/23 直交メタ項書換え計算のデベロップメントと合流性 洪 順姫, 酒井 正彦, 坂部 俊樹, |
---|---|
PDFダウンロードページ | PDFダウンロードページへ |
抄録(和) | メタ項書換え計算は、項書換え系の解析・生成・変換を記述・実行するための計算モデルである。計算モデルにとって合流性は、計算結果の一意性を保証する重要な性質であるが、メタ項書換え計算(MRC)はその定義から明らかに合流性はない。そこで本論文では、MRCのサブセットとして単純MRCを定義し、単純MRCの項が合流性を持つための十分条件を明らかにする。さらに、ラムダ計算や高階書換え系の合流性の証明に使われているデベロップメントの概念をMRC向けに改良することによって、直交性を持つ単純MRCが合流性を持つことを示す。 |
抄録(英) | In this paper, we prove that the statically orthogonal simple Metaterm Rewriting Calculus (MRC) is confluent, where MRC is a rewriting based computation model intended to describe and analyze those algorithms which process term rewriting systems. Outline of the proof is as follows: We first introduce the development reduction on simple MRC and then prove that it has the diamond property. |
キーワード(和) | 項書換え系 / 合流性 / 直交性 / デベロップメント |
キーワード(英) | Term Rewriting System / Confluence / Orthogonality / Development |
資料番号 | Comp99-9 |
発行日 |
研究会情報 | |
研究会 | COMP |
---|---|
開催期間 | 1999/4/23(から1日開催) |
開催地(和) | |
開催地(英) | |
テーマ(和) | |
テーマ(英) | |
委員長氏名(和) | |
委員長氏名(英) | |
副委員長氏名(和) | |
副委員長氏名(英) | |
幹事氏名(和) | |
幹事氏名(英) | |
幹事補佐氏名(和) | |
幹事補佐氏名(英) |
講演論文情報詳細 | |
申込み研究会 | Theoretical Foundations of Computing (COMP) |
---|---|
本文の言語 | JPN |
タイトル(和) | 直交メタ項書換え計算のデベロップメントと合流性 |
サブタイトル(和) | |
タイトル(英) | Development Reduction and Confluence of Orthogonal Metaterm Rewriting Calculus |
サブタイトル(和) | |
キーワード(1)(和/英) | 項書換え系 / Term Rewriting System |
キーワード(2)(和/英) | 合流性 / Confluence |
キーワード(3)(和/英) | 直交性 / Orthogonality |
キーワード(4)(和/英) | デベロップメント / Development |
第 1 著者 氏名(和/英) | 洪 順姫 / Sun Hui Hong |
第 1 著者 所属(和/英) | 名古屋大学大学院工学研究科情報工学専攻 Department of Information Engineering, Graduate School of Engineering, Nagoya University |
第 2 著者 氏名(和/英) | 酒井 正彦 / Masahiko Sakai |
第 2 著者 所属(和/英) | 名古屋大学大学院工学研究科情報工学専攻 Department of Information Engineering, Graduate School of Engineering, Nagoya University |
第 3 著者 氏名(和/英) | 坂部 俊樹 / Toshiki Sakabe |
第 3 著者 所属(和/英) | 名古屋大学大学院工学研究科情報工学専攻 Department of Information Engineering, Graduate School of Engineering, Nagoya University |
発表年月日 | 1999/4/23 |
資料番号 | Comp99-9 |
巻番号(vol) | vol.99 |
号番号(no) | 30 |
ページ範囲 | pp.- |
ページ数 | 6 |
発行日 |