We extend the higher-order termination method of dynamic dependency pairs to Algebraic Functional Systems (AFSs). In this setting, simply typed lambda-terms with algebraic reduction and separate -steps are considered. For left-linear AFSs, the method is shown to be complete. For so-called local AFSs we dene a variation of usable rules and an extension of argument lterings. All these techniques have been implemented in the higher-order termination tool WANDA.
Static Dependency Pairs for HRSs The static approach in @cite_21 is moved to the setting of HRSs in @cite_5 , and extended with argument filterings and usable rules in @cite_27 . The static approach omits dependency pairs @math with @math a variable, which avoids the need for a subterm property, but it allows bound variables to become free in the right-hand side of a dependency pair. The technique is restricted to HRSs. A system with for instance the (terminating) rule @math cannot be handled. Moreover, the approach is not complete: a terminating AFS may have a static dependency chain.
@cite_5 @cite_27 @cite_21
2119852735 1548902908 2091226256 2162899660
Higher-order rewrite systems (HRSs) and simply-typed term rewriting systems (STRSs) are computational models of functional programs. We recently proposed an extremely powerful method, the static dependency pair method, which is based on the notion of strong computability, in order to prove termination in STRSs. In this paper, we extend the method to HRSs. Since HRSs include λ-abstraction but STRSs do not, we restructure the static dependency pair method to allow λ-abstraction, and show that the static dependency pair method also works well on HRSs without new restrictions. We extend the termination method using dynamic dependency pairs to higher order rewriting systems with beta as a rewrite step, also called Algebraic Functional Systems (AFSs). We introduce a variation of usable rules, and use monotone algebras to solve the constraints generated by dependency pairs. This approach differs in several respects from those dealing with higher order rewriting modulo beta (e.g. HRSs). The static dependency pair method is a method for proving the termination of higher-order rewrite systems a la Nipkow. It combines the dependency pair method introduced for first-order rewrite systems with the notion of strong computability introduced for typed lambda-calculi. Argument filterings and usable rules are two important methods of the dependency pair framework used by current state-of-the-art first-order automated termination provers. In this paper, we extend the class of higher-order systems on which the static dependency pair method can be applied. Then, we extend argument filterings and usable rules to higher-order rewriting, hence providing the basis for a powerful automated termination prover for higher-order rewrite systems. This paper deals with termination proofs for Higher-Order Rewrite Systems (HRSs), introduced in [12]. This formalism combines the computational aspects of term rewriting and simply typed lambda calculus. The result is a proof technique for the termination of a HRS, similar to the proof technique “Termination by interpretation in a well-founded monotone algebra”, described in [8, 19]. The resulting technique is as follows: Choose a higher-order algebra with operations for each function symbol in the HRS, equipped with some well-founded partial ordering. The operations must be strictly monotonic in this ordering. This choice generates a model for the HRS. If the choice can be made in such a way that for each rule the interpretation of the left hand side is greater than the interpretation of the right hand side, then the HRS is terminating. At the end of the paper some applications of this technique are given, which show that this technique is natural and can easily be applied.