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

• 磯部 耕己

  日立INSソフトウェア株式会社ソフトウェア開発本部アプリケーション開発部

• 青戸 等人

  東北大学電気通信研究所

• 外山 芳人

  東北大学電気通信研究所

書誌事項

タイトル別名

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

抄録

Numbers of methods have been proposed to guarantee polynomial time computability of programs represented by term rewriting systems. Marion (2003) proposes the light multiset path ordering to guarantee polynomial size normal forms and shows that in term rewriting systems which can be oriented by this ordering any term can be evaluated in polynomial time. It is also shown that any polynomial time computable function can be encoded by term rewriting systems that can be oriented by this ordering. In general, however, there are term rewriting systems whose normal forms can be evaluated in polynomial time but which can not be oriented by this ordering. Thus a more general path ordering which guarantees polynomial time normal form is preferred. In this paper, we give an extension of the light multiset path ordering so that polynomial size normal form is guaranteed for more general class of term rewriting systems.

収録刊行物

• コンピュータ ソフトウェア

  コンピュータ ソフトウェア 29 (1), 176-190, 2012

  日本ソフトウェア科学会

詳細情報

• CRID: 1390282679713893248
• NII論文ID: 130004549256
• DOI: 10.11309/jssst.29.1_176
• ISSN: 02896540
• データソース種別:
  • JaLC
  • CiNii Articles
  • KAKEN
• 抄録ライセンスフラグ: 使用不可