単純右線形項書換えシステムの合流性について

太田 義勝  大山口 通夫  外山 芳人  

誌名
電子情報通信学会論文誌 D   Vol.J78-D1    No.3    pp.263-268
発行日: 1995/03/25
Online ISSN: 
DOI: 
Print ISSN: 0915-1915
論文種別: 論文
専門分野: オートマン,言語理論,計算論
キーワード: 
項書換えシステム,  合流性,  チャーチロッサ性,  非E重なり,  単純右線形TRS,  

本文: PDF(411.5KB)>>
論文を購入



あらまし: 
項書換えシステム(TRS)の重要な性質の一つに合流性(またはChurch-Rosser性)があり,これまで主に停止性を満たすTRSまたは線形TRSについて研究が行われてきた.非線形TRSの合流性について,筆者らにより,右定項TRSは非E重なりならば合流性を満たすことが示されている.本論文では,文献(10)で提案したE-グラフの解析手法を自然に拡張することにより,右定項TRSを含むより大きなクラスである単純右線形TRSが非E重なりならば合流性を満たすことを示す.ここで,TRSが単純右線形であるとは,右線形,かつ,すべての書換え規則について,規則の左辺に2度以上現れる変数が右辺に現れないことを言う.