首页    期刊浏览 2025年07月08日 星期二
登录注册

文章基本信息

  • 标题:多項式サイズ正規形を保証する項書き換えシステムの経路順序
  • 本地全文:下载
  • 作者:磯部 耕己 ; 青戸 等人 ; 外山 芳人
  • 期刊名称:コンピュータ ソフトウェア
  • 印刷版ISSN:0289-6540
  • 出版年度:2012
  • 卷号:29
  • 期号:1
  • 页码:1_176-1_190
  • DOI:10.11309/jssst.29.1_176
  • 出版社:Japan Society for Software Science and Technology
  • 摘要:

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

国家哲学社会科学文献中心版权所有