| 講演名 | 1994/7/25 E重なりのある単純右線形項書き換えシステムの合流性について 大山口 通夫, 外山 芳人, |
|---|---|
| PDFダウンロードページ | PDFダウンロードページへ |
| 抄録(和) | 項書き換えシステム(TRS)が単純右線形であるとき、すべての書き換え規則に対して、その右辺が線形であり、且つ右辺に出現する変数はその左辺に2度以上出現しないときである。本論文では、まず、単純右線形TRSが系列正規化可能性(即ち、任意の書き換え系列γ:M〓^*Nに対して、γの長さ以下で、且つE重なりのない系列δ:M〓^*Nが存在する)を満たせば、そのTRSは合流性を満たすことを示す。次に、系列正規化可能性を保証する幾つかの十分条件を示し、これらの十分条件が[大山口,1992]と[外山-大山口,1993]による2つの異なった手法を用いて得られた、合流性を保証する十分条件の一般化又は拡張となっていることを示す。 |
| 抄録(英) | A term rewriting system (TRS) is said to be simple-right-linear it for any rewrite rule,the right-hand-side term is linear and no variables occuring more than once in the left-hand-side occur in the right-hand-side.This paper shows that a simple-right-linear TRS is Church-Rosser (i.e.,confluent) if it satisfies the following condition (called the sequence-normalizing property): for any reduction sequence γ:M〓^*N of length n,there exists a red uction sequence δ:M〓^*N of lenght 〓 n such that no E-overlapping sequences occur in δ.Next,some sufficienct conditions for this se quence-normalizing property are presented and shown to be a generalization of those for Church-Rosser obtained by two different approaches proposed in £Oyamaguchi,1992! and £Toyama-Oy amaguchi,1993!. |
| キーワード(和) | 項書き換えシステム / 合流性 / E重なり / 単純右線形 |
| キーワード(英) | term-rewriting system / Church-Rosser / E-overlapping / simple- right-linear |
| 資料番号 | COMP94-29 |
| 発行日 |
| 研究会情報 | |
| 研究会 | COMP |
|---|---|
| 開催期間 | 1994/7/25(から1日開催) |
| 開催地（和） | |
| 開催地（英） | |
| テーマ（和） | |
| テーマ（英） | |
| 委員長氏名（和） | |
| 委員長氏名（英） | |
| 副委員長氏名（和） | |
| 副委員長氏名（英） | |
| 幹事氏名（和） | |
| 幹事氏名（英） | |
| 幹事補佐氏名（和） | |
| 幹事補佐氏名（英） | |
| 講演論文情報詳細 | |
| 申込み研究会 | Theoretical Foundations of Computing (COMP) |
|---|---|
| 本文の言語 | ENG |
| タイトル（和） | E重なりのある単純右線形項書き換えシステムの合流性について |
| サブタイトル（和） | |
| タイトル（英） | On the Church-Rosser property of E-overlapping and simple-right-linear TRS's |
| サブタイトル（和） | |
| キーワード(1)（和/英） | 項書き換えシステム / term-rewriting system |
| キーワード(2)（和/英） | 合流性 / Church-Rosser |
| キーワード(3)（和/英） | E重なり / E-overlapping |
| キーワード(4)（和/英） | 単純右線形 / simple- right-linear |
| 第 1 著者 氏名（和/英） | 大山口 通夫 / Michio Oyamaguchi |
| 第 1 著者 所属（和/英） | 三重大学工学部 Faculty of Engineering,Mie University |
| 第 2 著者 氏名（和/英） | 外山 芳人 / Yoshihito Toyama |
| 第 2 著者 所属（和/英） | 北陸先端科学技術大学院大学 Japan Advanced Institute of Science and Technology,Hokuriku |
| 発表年月日 | 1994/7/25 |
| 資料番号 | COMP94-29 |
| 巻番号（vol） | vol.94 |
| 号番号（no） | 181 |
| ページ範囲 | pp.- |
| ページ数 | 10 |
| 発行日 | |