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: max/plus interpretation on natural numbers: times#_A(x1,x2) = max{11, x2} plus_A(x1,x2) = max{11, x1 + 9, x2 + 2} |1|_A = 5 times_A(x1,x2) = max{4, x1 - 8, x2} |0|_A = 1 base order 2: precedence: |1| > plus = times > times# > |0| partial status: pi(times#) = [2] pi(plus) = [2] pi(|1|) = [] pi(times) = [2] pi(|0|) = [] The following rules are removed: p1 Then no dependency pair remains.