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.
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. This paper explores how to extend the dependency pair technique for proving termination of higher-order rewrite systems. We show that the termination property of higher-order rewrite systems can be checked by the non-existence of an infinite R-chain, which is an extension of Arts’ and Giesl’s result for the first-order case. It is clarified that the subterm property of the quasi-ordering, used for proving termination automatically, is indispensable. Arts and Giesl proved that the termination of a first-order rewrite system can be reduced to the study of its dependency pairs''. We extend these results to rewrite systems on simply typed lambda-terms by using Tait's computability technique.