重なりを持つTRSにおける最外戦略の完全性について  [in Japanese] On Completeness of Outermost Strategy for Overlapping TRSs  [in Japanese]

Search this Article

Author(s)

Abstract

項書換え系(TRS)において, 戦略は与えられた項の書換え可能な位置のうち書換えるべき位置を指示する.重なりを持つTRSでは, 一般に項は複数の正規形を持つため, 与えられた項のすべての正規形が求められる完全な戦略が望まれる.本稿では, 重なりを持つTRSにおいて最外戦略が完全であるための十分条件を与える.また, 与えられたTRSを, この条件を満たすように等価変換する方法についても論ずる.

Strategies in term rewriting systems (TRSs) indicate a position of a given term to be reduced. Since a term generally has more than one normal forms in overlapping systems, it is desired to find a complete strategy, which can search all normal forms of a given term. This paper gives a sufficient condition that guarantees the completeness of the outermost strategy for overlapping TRSs. We also discuss an equivalent transformation of TRSs in order to obtain ones that satisfy the sufficient condition.

Journal

  • IEICE technical report

    IEICE technical report 105(331), 39-44, 2005-10-13

    The Institute of Electronics, Information and Communication Engineers

References:  8

Codes

  • NII Article ID (NAID)
    110003498383
  • NII NACSIS-CAT ID (NCID)
    AN10013287
  • Text Lang
    JPN
  • Article Type
    ART
  • ISSN
    09135685
  • NDL Article ID
    7699948
  • NDL Source Classification
    ZN33(科学技術--電気工学・電気機械工業--電子工学・電気通信)
  • NDL Call No.
    Z16-940
  • Data Source
    CJP  NDL  NII-ELS 
Page Top