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.
The definitions for HRSs @cite_37 @cite_5 do not immediately carry over to AFSs, since AFSs may have rules of functional type, and @math -reduction is a separate rewrite step. A short paper by Blanqui @cite_12 introduces static dependency pairs on a form of rewriting which includes AFSs, but it poses some restrictions, such as base-type rules. The present work considers dynamic dependency pairs for AFSs and is most related to @cite_37 , but is adapted for the different formalism. Our method conservatively extends the one for first-order rewriting and provides a characterisation of termination for left-linear AFSs. We have chosen for a dynamic rather than a static approach because, although the static approach is stronger when applicable, the dynamic definitions can be given without restrictions. The restrictions we do provide, to weaken the subterm property and enable for instance argument filterings, are optional. We will say some words about integrating the static and dynamic approaches in .
@cite_5 @cite_37 @cite_12
2119852735 1548902908 1495662220 2091226256
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). We present a termination method for left-linear Higher-order Rewrite Systems (HRSs) that are algebraic using a higher-order generalization of dependency pairs with argument filterings. 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.