右定項-項書換えシステムの合流性について

大山口 通夫  太田 義勝  

誌名
電子情報通信学会論文誌 D   Vol.J76-D1    No.2    pp.39-45
発行日: 1993/02/25
Online ISSN: 
DOI: 
Print ISSN: 0915-1915
論文種別: 論文
専門分野: オートマン,言語理論,計算論
キーワード: 
項書換えシステム,  合流性,  E重なり,  右定項システム,  

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



あらまし: 
項書換えシステム(TRS)の重要な性質の一つに合流性(またはChurch-Rosser性)があり,TRSの合流性に関する研究がこれまで盛んに行われてきた.しかし,これまでの研究は主に停止性を満たすTRSまたは線形TRSの場合について行われ,停止性を満たさない非線形TRSの合流性についてはあまり研究されずに今日に至っている.本論文では,後者の場合の研究を発展させることを目的として,非線形TRSの最も小さいクラスの一つである右定項システム,すなわち,すべての書換え規則の右辺が定項であるTRSの合流性について考察する.右定項システムは非線形TRSのため,非重なりのときでも合流性を満たさない場合があることが知られていたが,本論文において,非重なりよりも強い条件である非E重なりの性質を満たせば,合流性を満たすことを示す.この証明のために,本論文では書換え系列の自然な拡張であるE-グラフの概念を導入し,E-グラフの合流性を証明することによって,上記の結果を得ている.