非線形TRSのE重なり性について

松浦 邦博  大山口 通夫  太田 義勝  小川 瑞史  

誌名
電子情報通信学会論文誌 D   Vol.J80-D1   No.11   pp.847-855
発行日: 1997/11/25
Online ISSN: 
DOI: 
Print ISSN: 0915-1915
論文種別: 論文
専門分野: オートマン,言語理論,計算論
キーワード: 
項書換えシステム,  深さ保存,  非E重なり,  非ω重なり,  右定項TRS,  

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




あらまし: 
項書換えシステム(TRS)の重要な性質の一つに合流性があり,最近,非線形TRSにおいては非E重なり性がその合流性と密接に関係していることが報告された.しかし,非E重なり性は一般に非可解な問題である.本論文では,まず「深さ保存」の概念を導入し,TRSが深さ保存的であるとき,非ω重なりならば非E重なりであることを示す.非ω重なり性は判定可能な性質であることから,この結果を用いて,合流性を保証する判定可能な十分条件をいくつか導くことができることを示す.次に,右定項TRSのクラスに限定すれば非E重なり性判定問題が可解であることを明らかにする.