項書換え系とその保存的拡大における代数的意味論と動作意味論の関連について

直井 徹  稲垣 康善  

誌名
電子情報通信学会論文誌 D   Vol.J71-D   No.10   pp.1893-1900
発行日: 1988/10/25
Online ISSN: 
DOI: 
Print ISSN: 0913-5713
論文種別: 論文
専門分野: オートマトン,言語理論,計算論
キーワード: 


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




あらまし: 
項書換え系の動作意味論を定式化し,筆者らが既に提案した代数的意味論との関係を明らかにする.無あいまい線形項書換え系においては,動作意味論から項の集合上に導かれる合同関係の方が,代数的意味論から導かれるそれよりも大きいという関係があること,しかし,保存的拡大と呼ばれる基準によって書換え規則の追加を行うと,動作意味論は局所的に代数的意味論に一致することを示す.また,保存的拡大の概念を用いて項書換え系における項の可解性を定義し,代数的意味論から見たときの「未定義性」を特徴づける.