Weighted Path Orders Are Semantic Path Orders
Open Access
- 13 September 2023
- book chapter
- Published by Springer Nature
- p. 63-80
Abstract
We explore the relationship between weighted path orders and (monotonic) semantic path orders. Our findings reveal that weighted path orders can be considered instances of a variant of semantic path orders that comprise order pairs. This observation leads to a generalization of weighted path orders that does not impose simplicity on their underlying algebras. As a result, the generalized version is capable of proving termination of term rewrite systems beyond the realm of simple termination. In order to assess practicality we provide experimental data comparing generalized weighted path orders with the original ones as well as other well-known classes of reduction orders.Keywords
This publication has 19 references indexed in Scilit:
- KBO OrientabilityJournal of Automated Reasoning, 2009
- Z3: An Efficient SMT Solver2008
- Termination of S-Expression Rewriting Systems: Lexicographic Path Ordering for Higher-Order TermsLecture Notes in Computer Science, 2004
- Termination of term rewriting using dependency pairsTheoretical Computer Science, 2000
- Complete Monotonic Semantic Path OrderingsLecture Notes in Computer Science, 2000
- Simple termination of rewrite systemsTheoretical Computer Science, 1997
- An Improved General Path OrderApplicable Algebra in Engineering, Communication and Computing, 1996
- Proof-theoretic analysis of termination proofsAnnals of Pure and Applied Logic, 1995
- Natural terminationTheoretical Computer Science, 1995
- Orderings for term-rewriting systemsTheoretical Computer Science, 1982