YES We show the termination of the TRS R: times(x,plus(y,|1|())) -> plus(times(x,plus(y,times(|1|(),|0|()))),x) times(x,|1|()) -> x plus(x,|0|()) -> x times(x,|0|()) -> |0|() -- SCC decomposition. Consider the dependency pair problem (P, R), where P consists of p1: times#(x,plus(y,|1|())) -> plus#(times(x,plus(y,times(|1|(),|0|()))),x) p2: times#(x,plus(y,|1|())) -> times#(x,plus(y,times(|1|(),|0|()))) p3: times#(x,plus(y,|1|())) -> plus#(y,times(|1|(),|0|())) p4: times#(x,plus(y,|1|())) -> times#(|1|(),|0|()) and R consists of: r1: times(x,plus(y,|1|())) -> plus(times(x,plus(y,times(|1|(),|0|()))),x) r2: times(x,|1|()) -> x r3: plus(x,|0|()) -> x r4: times(x,|0|()) -> |0|() The estimated dependency graph contains the following SCCs: {p2} -- Reduction pair. Consider the dependency pair problem (P, R), where P consists of p1: times#(x,plus(y,|1|())) -> times#(x,plus(y,times(|1|(),|0|()))) and R consists of: r1: times(x,plus(y,|1|())) -> plus(times(x,plus(y,times(|1|(),|0|()))),x) r2: times(x,|1|()) -> x r3: plus(x,|0|()) -> x r4: times(x,|0|()) -> |0|() The set of usable rules consists of r3, r4 Take the reduction pair: generalized weighted path order (>=MG, >MG) base order 1: matrix interpretation with standard point-wise order: carrier: N^1 order: standard order interpretations: times#_A(x1,x2) = x1 + x2 plus_A(x1,x2) = x1 + x2 + 2 |1|_A() = 4 times_A(x1,x2) = 3 |0|_A() = 2 base order 2: precedence: times# = plus = |1| = times > |0| partial status: pi(times#) = [1] pi(plus) = [1] pi(|1|) = [] pi(times) = [] pi(|0|) = [] The following rules are removed: p1 Then no dependency pair remains.