条件付き項書換え系の合流性について

高橋 宜孝  酒井 正彦  外山 芳人  

誌名
電子情報通信学会論文誌 D   Vol.J79-D1    No.11    pp.897-902
発行日: 1996/11/25
Online ISSN: 
DOI: 
Print ISSN: 0915-1915
論文種別: 論文
専門分野: オートマン,言語理論,計算論
キーワード: 
条件付き項書換え系,  合流性,  危険対,  不能性,  

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



あらまし: 
条件付き項書換え系(CTRS)の合流条件はこれまで盛んに研究されてきた.しかし,これらの合流条件の多くは,CTRSの停止性を仮定している.停止性を仮定しない場合の合流条件に関しては,CTRSが左線形で危険対をもたないときに合流するというKlopとBergstraの結果以外はほとんど知られていない.しかし,CTRSの中に危険対が存在していてもそれらがすべて不能であれば,CTRSは危険対をもたないシステムと同様に振舞うことが示される.本研究では,Kaplanによって提案された危険対の不能性という概念を利用して,KlopとBergstraによって示された合流条件を拡張する.