講演名	1996/10/31 左線形項書換えシステムのチャーチ・ロッサー性に対する新しいParallel Closed条件 大山口 通夫, 太田 義勝,
PDFダウンロードページ	PDFダウンロードページへ
抄録(和)	G.Huet (1980)により左線形項書換えシステム(TRS)はすべての危険対がP↛Qを満たせばチャーチ・ロッサー性を満たす(CR)ことが示された. ここで, P↛QはPからQへの並列簡約である. しかし, すべての危険対がQ↛Pを満たす時にCRがどうかは未解決であった. 本稿では, この問題に対する部分的な解決を与える. すなわち, 左線形TRSは, すべての危険対に対してQ↛^^WPならばCRであることを示す. ここで, Q↛^^WPは簡約位置の集合がWであるような並列簡約であり, 出現位置uで重なる規則対によって危険対が生成されたならばすべてのω∈ Wに対して長さが|v|≥|w|を満たす. さらに, 左線形TRSは, すべての危険対に対してQ↛^^WPまたはP↛^^εQならばCRであることを示す.
抄録(英)	G.Huet (1980) showed that a left-linear term-rewriting system (TRS) is Church-Rosser (CR) if P↛Q for every critical pair where P↛Q is a parallel reduction from P to Q. But, it remains open whether it is CR when Q↛P for every critical pair . In this paper, we give a partial solution to this problem, that is, a left-linear TRS is CR if Q↛^^WP for every critical pair where Q↛^^WP is a parallel reduction with the set W of redex occurrences satisfying that if the critical pair is generated from two rules overlapping at an occurrence u, then the length |u|≥|w| for every ω∈ W. Furthermore, a, left-linear TRS is CR if Q↛^^WP or P↛^^εQ for every critical pair .
キーワード(和)	Parallel Closed条件 / チャーチ・ロッサー性 / 左線形項書換えシステム / 危険対 / 完備化手続き
キーワード(英)	Parallel Closed Condition / Church-Rosser / Left-Linear TRS / Critical Pair / Completion Procedure
資料番号	COMP96-35
発行日

研究会情報
研究会	COMP
開催期間	1996/10/31(から1日開催)
開催地（和）
開催地（英）
テーマ（和）
テーマ（英）
委員長氏名（和）
委員長氏名（英）
副委員長氏名（和）
副委員長氏名（英）
幹事氏名（和）
幹事氏名（英）
幹事補佐氏名（和）
幹事補佐氏名（英）

講演論文情報詳細
申込み研究会	Theoretical Foundations of Computing (COMP)
本文の言語	ENG
タイトル（和）	左線形項書換えシステムのチャーチ・ロッサー性に対する新しいParallel Closed条件
サブタイトル（和）
タイトル（英）	A New Parallel Closed Condition for Church-Rosser of Left-Linear Term Rewriting Systems
サブタイトル（和）
キーワード(1)（和/英）	Parallel Closed条件 / Parallel Closed Condition
キーワード(2)（和/英）	チャーチ・ロッサー性 / Church-Rosser
キーワード(3)（和/英）	左線形項書換えシステム / Left-Linear TRS
キーワード(4)（和/英）	危険対 / Critical Pair
キーワード(5)（和/英）	完備化手続き / Completion Procedure
第 1 著者 氏名（和/英）	大山口 通夫 / Michio Oyamaguchi
第 1 著者 所属（和/英）	三重大学工学部情報工学科 Faculty of Engineering, Mie University
第 2 著者 氏名（和/英）	太田 義勝 / Yoshikatsu Ohta
第 2 著者 所属（和/英）	三重大学工学部情報工学科 Faculty of Engineering, Mie University
発表年月日	1996/10/31
資料番号	COMP96-35
巻番号（vol）	vol.96
号番号（no）	343
ページ範囲	pp.-
ページ数	10
発行日