文献

J-GLOBAL ID：201202212410217435   整理番号：12A0394674

多項式サイズ正規形を保証する項書き換えシステムの経路順序

A Path Ordering for Term Rewriting Systems with Polynomial Size Normal Forms

著者 (3件)： 磯部耕己 (日立INSソフトウェア株式会社ソフトウェア開発本部アプリケーション開発部) ,  青戸等人 (東北大学電気通信研究所) ,  外山芳人 (東北大学電気通信研究所)
資料名： コンピュータソフトウェア  (Computer Software)
巻： 29  号： 1  ページ： 1.176-1.190 (J-STAGE)  発行年： 2012年 
JST資料番号： Y0628A  ISSN： 0289-6540  資料種別： 逐次刊行物 (A)
記事区分： 原著論文  発行国： 日本 (JPN)  言語： 日本語 (JA)

抄録/ポイント： 項書き換えシステムを用いて記述したプログラムが,多項式時間で計算可能であることを示す様々な手法が知られている.Marion (2003)は多項式サイズ正規形を保証する軽多重集合経路順序を提案し,この順序により方向付け可能な項書き換えシステムにおいては,任意の項は多項式時間で評価可能であることを示した.また,多項式時間で計算可能な任意の関数は,この軽多重集合経路順序によって方向付けが可能であるような項書き換えシステムによって記述できることも示されている.しかしながら,一般に項書き換えシステムを与えたとき,多項式サイズ正規形が保証される場合でも,軽多重集合経路順序で方向付けができないことがある.このため,より一般的な経路順序によって多項式サイズ正規形を保証できることが望ましい.本論文では,軽多重集合経路順序を拡張し,より一般的な項書き換えシステムに対して多項式サイズ正規形を保証する新しい経路順序を提案する.(著者抄録)

シソーラス用語： *項書換え系 ,  多項式 ,  *計算可能性 ,  経路選定 ,  通信操作
準シソーラス用語： 経路順序 ,  *項書換えシステム

分類 (1件)： 計算理論  (JB02000A)

タイトルに関連する用語 (6件)： 多項式 ,  サイズ ,  保証 ,  項書き換えシステム ,  経路 ,  順序