Automating the dependency pair method

Developing automatable methods for proving termination of term rewrite systems that resist traditional techniques based on simplification orders has become an active research area in the past few years. The dependency pair method of Arts and Giesl is one of the most popular such methods. However, there are several obstacles that hamper its automation. In this paper we present new ideas to overcome these obstacles. We provide ample numerical data supporting our ideas.

Authors

• Nao Hirokawa
• Aart Middeldorp

Keywords

• Term rewriting
• Termination
• Dependency pair method