E重なりのある単純右線形項書き換えシステムの合流性について

スポンサーリンク

概要

• 論文の詳細を見る

• A term rewriting system (TRS) is said to be simple-right-linear if 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 reduction sequence δ : M ←→ N of length ≤ n such that no E-overlapping sequences occur in δ. Next, some sufficient conditions for this sequence-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-Oyamaguchi, 1993].

著者

• 大山口 通夫

  Department Of Information Engineering Faculty Of Engineering Mie University

• 外山 芳人

  School of Information Science, JAIST

関連論文

• プロセス間通信に基づく並列処理言語の表示的意味記述について
• NVNF-sequentiality of Left-linear Term Rewriting Systems
• E重なりのある単純右線形項書き換えシステムの合流性について

スポンサーリンク