Lexicographic Combination of Reduction Pairs
Open Access
- 30 July 2025
- book chapter
- Published by Springer Nature
- p. 167-186
Abstract
We present a simple criterion for combining reduction pairs lexicographically. The criterion is applicable to arbitrary classes of reduction pairs, such as the polynomial interpretation, the matrix interpretation, and the Knuth–Bendix order. In addition, we investigate a variant of the matrix interpretation where the lexicographic order is employed instead of the usual component-wise order. Effectiveness is demonstrated by experiments and examples, including Touzet’s Hydra Battle.Keywords
This publication has 27 references indexed in Scilit:
- A Dependency Pair Framework for Relative Termination of Term Rewriting2024
- Nagoya Termination Tool2014
- Improved Matrix Interpretation2010
- Arctic Termination ...Below Zero2008
- Z3: An Efficient SMT Solver2008
- The Hydra Battle Revisited2007
- The Dependency Pair Framework: Combining Techniques for Automated Termination Proofs2005
- Improved Modular Termination Proofs Using Dependency Pairs2004
- Modular Termination Proofs for Rewriting Using Dependency PairsJournal of Symbolic Computation, 2002
- Encoding the hydra battle as a rewrite system1998