Unifying Semantic Path Order and Weighted Path Order
Teppei Saito, Nao Hirokawa · 2026
Read Unifying Semantic Path Order and Weighted Path Order by Teppei Saito, Nao Hirokawa (2026) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2605-29393.txt.
Introduction
Teppei Saito and Nao Hirokawa present a simple union of monotonic semantic path orders and weighted path orders as reduction orders and reduction pairs. Both are strong reduction orders for proving termination of term rewrite systems. The paper also discusses their use as ground total reduction orders. This gives termination provers a single unified framework in place of two separate orders.
Catalog record
| CREATOR | Teppei Saito, Nao Hirokawa |
|---|---|
| YEAR | 2026 |
| COLLECTION | PAPERS |
| FORMAT | TXT |
| FILE SIZE | 24807 |
| LICENSE | http://creativecommons.org/licenses/by/4.0/ |
| RIGHTS | CC BY |
| SOURCE | arXiv |
Source: https://arxiv.org/abs/2605.29393
Browse the full library · About the Tower of Babel
Full text
The opening of the work, from the library's hosted text:
Unifying Semantic Path Order and Weighted Path Order Teppei Saito, Nao Hirokawa Abstract Monotonic semantic path orders and weighted path orders are powerful reduction orders for proving termination of term rewrite systems. In this paper we present their simple unification as reduction orders and reduction pairs. We also discuss the use of it as ground total reduction orders. JAIST, Japan [email protected] https://orcid.org/0009-0001-9786-0044 JSPS KAKENHI Grant Number JP25KJ1363 JAIST, Japan [email protected] https://orcid.org/0000-0002-8499-0501 We thank René Thiemann and Akihisa Yamada for the valuable feedbacks on our work. We also thank Jürgen Giesl for his valuable questions at WST 2023 and FroCoS 2023. ccs Theory of computation Equational logic and rewriting keywords term rewriting, termination, weighted path orders, semantic path orders † † runningauthor: T. Saito and N. Hirokawa † † copyright: Teppei Saito and Nao Hirokawa † † editors: John Q. Open and Joan R. Access † † event-title: 42nd Conference on Very Important Topics (CVIT 2016) † † event-shorttitle: CVIT 2016 † † event-acronym: CVIT † † year: 2016 † † event-date: December 24–27, 2016 † † event-location: Little Whinging, United Kingdom † † series-volume: 42 † † articleno: 23 1 Introduction We present a generalization of monotonic semantic path orders (MSPOs) [ 2 ] and weighted path orders (WPOs) [ 8 ] . In the FroCoS 2023 paper [ 7 ] we showed that WPOs as reduction orders are instances of MSPOs. In this note we adopt the opposite approach: First we introduce a generalization of WPOs dubbed GWPOs, and then show that MSPOs are instances of GWPOs. We see that desirable properties of WPO carry over to GWPOs. Full details on these contributions are found in the first author’s dissertation [ 6 ] . 2 Reduction Orders This section considers reduction orders , which are well-founded orders on terms that are closed under contexts and substitutions. It is known that a TRS \mathcal{R} is terminating if and only if there exists a reduction order > with \mathcal{R}\subseteq{>} . The basic ingredient of our unified orders (GWPOs) is reduction triples , originally introduced for MSPOs. Formally, a triple ({\geqslant},{\sqsupseteq},{\sqsupset}) is a reduction triple if \geqslant is a rewrite preorder on terms, ({\sqsupseteq},{\sqsupset}) is a stable order pair on terms with \sqsupset well-founded, and \sqsupseteq is harmonious to \geqslant . Here, rewrite preorder means preorder (or quasi-order) closed under substitutions and contexts; the stability condition means that \sqsupseteq and \sqsupset are both closed under substitutions; and the harmony condition means that t_{i}\geqslant u implies f(t_{1},\ldots,t_{i},\ldots,t_{n})\sqsupseteq f(t_{1},\ldots,u,\ldots,t_{n}) for all n -ary function symbols f , terms t_{1},\ldots,t_{n},u and integers 1\leqslant i\leqslant n . For example, given a reduction pair ({\geqslant},{>}) (which is a key notion in the dependency pair method [ 1 ] ), the triple ({\geqslant},{\geqslant},{>}) is a reduction triple. Also, given a weakly monotone and well-founded algebra \mathcal{A} (say, a linear polynomial interpretation on natural numbers), the triple ({\geqslant_{\mathcal{A}}},{\geqslant_{\mathcal{A}}},{>_{\mathcal{A}}}) is a reduction triple. Moreover, given a precedence \succeq , the triple ({\mathcal{T}\times\mathcal{T}},{\sqsupseteq},{\sqsupset}) is a reduction triple. Here, \mathcal{T}\times\mathcal{T} is the universal relation relating every pair of terms, and \sqsupseteq and \sqsupset are defined as comparison of head symbols w.r.t. \succeq . We are ready to define the unified order GWPO. Note that it generalizes GWPO in the sense of our earlier paper [ 7 ] . Definition 1 . Let ({\sqsupseteq_{A}},{\sqsupset_{A}}) and ({\sqsupseteq_{B}},{\sqsupset_{B}}) be pairs of relations on terms. The generalized weighted path order >_{\mathsf{G}} (GWPO) is defined as follows: s>_{\mathsf{G}}t if 1. s\sqsupset_{A}t , or 2. s=f({s_{1}},\dots,{s_{m}})\sqsupseteq_{A}t and one of the following conditions holds: a. s_{i}=t or s_{i}>_{\mathsf{G}}t for some 1\leqslant i\leqslant m . b. t=g({t_{1}},\dots,{t_{n}}) , s>_{\mathsf{G}}t_{j} for all 1\leqslant j\leqslant n , and moreover i. s\sqsupset_{B}t , or ii. s\sqsupseteq_{B}t and ({s_{1}},\dots,{s_{m}})>_{\mathsf{G}}^{\mathsf{lex}}({t_{1}},\dots,{t_{n}}) . Now, let ({\geqslant_{A}},{\sqsupseteq_{A}},{\sqsupset_{A}}) and ({\geqslant_{B}},{\sqsupseteq_{B}},{\sqsupset_{B}}) be triples of relations on terms. The monotonic generalized weighted path order (MGWPO) >_{\mathsf{MG}} is the intersection {\geqslant_{A}}\cap{\geqslant_{B}}\cap{>_{\mathsf{G}}} where >_{\mathsf{G}} is induced by ({\sqsupseteq_{A}},{\sqsupset_{A}}) and ({\sqsupseteq_{B}},{\sqsupset_{B}}) . Technically, we take the intersection {\geqslant_{A}}\cap{\geqslant_{B}}\cap{>_{\mathsf{G}}} because >_{\mathsf{G}} may not be closed under contexts. This technique is due to Borralleras, Ferreira and Rubio [ 2 ] . To simplify the presentation, we globally assume that the signature is finite. A relation \leadsto on terms is said to have the subterm property if s\leadsto t holds whenever t is a proper subterm of s . Theorem 2 . For reduction triples ({\geqslant_{A}},{\sqsupseteq_{A}},{\sqsupset_{A}}) and ({\geqslant_{B}},{\sqsupseteq_{B}},{\sqsupset_{B}}) with \sqsupseteq_{A} having the subterm property, the induced MGWPO >_{\mathsf{MG}} is a reduction order. Example 3 . We show the termination of the TRS \mathcal{R}=\{\mathsf{p}(\mathsf{s}(x))\to x,\mathsf{f}(\mathsf{s}(x))\to\mathsf{f}(\mathsf{p}(\mathsf{s}(x)))\} . Let \mathcal{A} and \mathcal{B} be the algebras on \mathbb{N} with \mathsf{p}_{\mathcal{A}}(x)=\mathsf{f}_{\mathcal{A}}(x)=x , \mathsf{s}_{\mathcal{A}}(x)=\mathsf{f}_{\mathcal{B}}(x)=\mathsf{s}_{\mathcal{B}}(x)=x+1 , and \mathsf{p}_{\mathcal{B}}(x)=\max\{0,x-1\} . Then ({\geqslant_{\mathcal{A}}},{\geqslant_{\mathcal{A}}},{>_{\mathcal{A}}}) and ({\geqslant_{\mathcal{B}}},{\geqslant_{\mathcal{B}}},{>_{\mathcal{B}}}) are reduction triples and {\geqslant_{\mathcal{A}}} has the subterm property. We conclude that \mathcal{R} is terminating because the induced MGWPO satisfies \mathcal{R}\subseteq{>_{\mathsf{MG}}} . A WPO is parameterized by an algebra \mathcal{A} (assumed weakly simple), and a precedence \succeq . The WPO is identical to the MGWPO whose reduction triple A is induced from \mathcal{A} and B is induced by \succeq . (So actually, the subterm property of \sqsupseteq_{A} assumed in \cref thm:mgwpo is an analog of the weak simplicity of \mathcal{A} required by the WPO.) The same goes for the MSPO: An MSPO is parameterized by a single reduction triple ({\geqslant},{\sqsupseteq},{\sqsupset}) . The MSPO is identical to the MGWPO whose reduction triple A is the trivial one ({\mathcal{T}\times\mathcal{T}},{\mathcal{T}\times\mathcal{T}},{\varnothing}) and B is ({\geqslant},{\sqsupseteq},{\sqsupset}) . Equivalently, the MSPO can be defined as follows. Definition 4 . Let ({\sqsupseteq},{\sqsupset}) be a pair of relations on terms. The semantic path order >_{\mathsf{S}} is defined on terms as follows: s>_{\mathsf{S}}t if s=f({s_{1}},\dots,{s_{m}}) and one of the next conditions holds. a. s_{i}=t or s_{i}>_{\mathsf{S}}t for some 1\leqslant i\leqslant m . b. t=g({t_{1}},\dots,{t_{n}}) and s>_{\mathsf{S}}t_{j} for all 1\leqslant j\leqslant n , and moreover i. s\sqsupset t , or ii. s\sqsupseteq t and ({s_{1}},\dots,{s_{m}})>_{\mathsf{S}}^{\mathsf{lex}}({t_{1}},\dots,{t_{n}}) . For a reduction triple ({\geqslant},{\sqsupseteq},{\sqsupset}) , The monotonic semantic path order s>_{\mathsf{MS}}t is defined as the intersection {\geqslant}\cap{>_{\mathsf{S}}} , where >_{\mathsf{S}} is induced by ({\sqsupseteq},{\sqsupset}) . Theorem 5 ( [ 2 ] ) . Every MSPO is a reduction order. Conversely, MGWPOs can be seen as instances of MSPOs. Theorem 6 . Let >_{\mathsf{MG}} be the MGWPO induced by reduction triples ({\geqslant_{A}},{\sqsupseteq_{A}},{\sqsupset_{A}}) and ({\geqslant_{B}},{\sqsupseteq_{B}},{\sqsupset_{B}}) with the subterm property of \sqsupseteq_{A} . Then >_{\mathsf{MG}} and the MSPO >_{\mathsf{MS}} are identical, where >_{\mathsf{MS}} is induced by ({\geqslant_{A}\cap\geqslant_{B}},{\sqsupseteq_{AB}},{\sqsupset_{AB}}) and ({\sqsupseteq_{AB}},{\sqsupset_{AB}}) is the lexicographic combination of ({\sqsupseteq_{A}},{\sqsupset_{A}}) and ({\sqsupseteq_{B}},{\sqsupset_{B}}) . This is an analog of a main result of the FroCoS paper stating that WPOs are MSPOs [ 7 ] . In fact, this result can be traced back to Geser’s observation ( [ 4 , Theorem 5] ) that a version of the Knuth–Bendix order can be simulated by the semantic path order (SPO) [ 5 ] . What is the point of having the unified order? One way of defending our GWPO concerns ground totality , which is a crucial property for theorem proving methods like the superposition calculus. On one hand, every WPO >_{\mathsf{W}} satisfying totality of the precedence and the ordered algebra is ground total, meaning that either s>_{\mathsf{W}}t or t>_{\mathsf{W}}s holds for all terms s\neq t . On the other hand, this does not go naturally for the MSPO. Based on this observation, we