必須呼びが正規化戦略となるあいまいな線形項書き換えシステムのクラス

直井 徹  山下 雅史  茨木 俊秀  本多 波雄  

誌名
電子情報通信学会論文誌 D   Vol.J69-D   No.9   pp.1236-1245
発行日: 1986/09/25
Online ISSN: 
DOI: 
Print ISSN: 0913-5713
論文種別: 論文
専門分野: オートマン・言語理論
キーワード: 


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




あらまし: 
項書き換えシステムは,等式による記述を基盤とするようなプログラミング言語の実行メカニズムをはじめとして,さまざまな応用が考えられることから,近年注目を浴びている.しかしその応用に際しては,与えられた項に正規形が存在するとき必ずそれに到達することを保証する書き換えの戦略,すなわち正規化戦略が考慮されなければならない.HuetとLevyは,あいまいでない線形項書き換えシステムに対する正規化戦略として必須呼び(call by need)を提案した.本論文ではこれをあいまい性を含む場合に拡張する.まず,あいまいな線形項書き換えシステムにおいて必須呼びが正規化戦略であるための十分条件を一つ示す.これはHuetとLevyの結果を真に含むものである.次に,必須呼びが正規化戦略となっている任意の線形項書き換えシステムに対し,その性質を保存したまま新しい書き換え規則を付け加えることを可能にするような条件を示す.従って,この結果を前の結果と結びつけることにより,必須呼びが正規化戦略となるようなあいまいな項書き換えシステムの,より広いクラスが得られる.