YES We show the termination of the TRS R: D(t()) -> |1|() D(constant()) -> |0|() D(+(x,y)) -> +(D(x),D(y)) D(*(x,y)) -> +(*(y,D(x)),*(x,D(y))) D(-(x,y)) -> -(D(x),D(y)) D(minus(x)) -> minus(D(x)) D(div(x,y)) -> -(div(D(x),y),div(*(x,D(y)),pow(y,|2|()))) D(ln(x)) -> div(D(x),x) D(pow(x,y)) -> +(*(*(y,pow(x,-(y,|1|()))),D(x)),*(*(pow(x,y),ln(x)),D(y))) -- SCC decomposition. Consider the dependency pair problem (P, R), where P consists of p1: D#(+(x,y)) -> D#(x) p2: D#(+(x,y)) -> D#(y) p3: D#(*(x,y)) -> D#(x) p4: D#(*(x,y)) -> D#(y) p5: D#(-(x,y)) -> D#(x) p6: D#(-(x,y)) -> D#(y) p7: D#(minus(x)) -> D#(x) p8: D#(div(x,y)) -> D#(x) p9: D#(div(x,y)) -> D#(y) p10: D#(ln(x)) -> D#(x) p11: D#(pow(x,y)) -> D#(x) p12: D#(pow(x,y)) -> D#(y) and R consists of: r1: D(t()) -> |1|() r2: D(constant()) -> |0|() r3: D(+(x,y)) -> +(D(x),D(y)) r4: D(*(x,y)) -> +(*(y,D(x)),*(x,D(y))) r5: D(-(x,y)) -> -(D(x),D(y)) r6: D(minus(x)) -> minus(D(x)) r7: D(div(x,y)) -> -(div(D(x),y),div(*(x,D(y)),pow(y,|2|()))) r8: D(ln(x)) -> div(D(x),x) r9: D(pow(x,y)) -> +(*(*(y,pow(x,-(y,|1|()))),D(x)),*(*(pow(x,y),ln(x)),D(y))) The estimated dependency graph contains the following SCCs: {p1, p2, p3, p4, p5, p6, p7, p8, p9, p10, p11, p12} -- Reduction pair. Consider the dependency pair problem (P, R), where P consists of p1: D#(+(x,y)) -> D#(x) p2: D#(pow(x,y)) -> D#(y) p3: D#(pow(x,y)) -> D#(x) p4: D#(ln(x)) -> D#(x) p5: D#(div(x,y)) -> D#(y) p6: D#(div(x,y)) -> D#(x) p7: D#(minus(x)) -> D#(x) p8: D#(-(x,y)) -> D#(y) p9: D#(-(x,y)) -> D#(x) p10: D#(*(x,y)) -> D#(y) p11: D#(*(x,y)) -> D#(x) p12: D#(+(x,y)) -> D#(y) and R consists of: r1: D(t()) -> |1|() r2: D(constant()) -> |0|() r3: D(+(x,y)) -> +(D(x),D(y)) r4: D(*(x,y)) -> +(*(y,D(x)),*(x,D(y))) r5: D(-(x,y)) -> -(D(x),D(y)) r6: D(minus(x)) -> minus(D(x)) r7: D(div(x,y)) -> -(div(D(x),y),div(*(x,D(y)),pow(y,|2|()))) r8: D(ln(x)) -> div(D(x),x) r9: D(pow(x,y)) -> +(*(*(y,pow(x,-(y,|1|()))),D(x)),*(*(pow(x,y),ln(x)),D(y))) The set of usable rules consists of r1 Take the reduction pair: generalized weighted path order (>=MG, >G) base order 1: matrix interpretation with standard point-wise order: carrier: N^1 order: standard order interpretations: D#_A(x1) = 1 +_A(x1,x2) = 2 pow_A(x1,x2) = x1 + 3 ln_A(x1) = 0 div_A(x1,x2) = x1 + x2 + 5 minus_A(x1) = 2 -_A(x1,x2) = 4 *_A(x1,x2) = x1 + x2 D_A(x1) = 2 t_A() = 2 |1|_A() = 1 base order 2: marked-algebra reduction triple (>=A, >=A!, >A!): max/plus interpretation on natural numbers: D#_A(x1) = max{0, x1 - 122} +_A(x1,x2) = max{231, x1 + 110, x2 + 110} pow_A(x1,x2) = max{x1 + 18, x2 + 36} ln_A(x1) = max{127, x1 + 37} div_A(x1,x2) = max{x1, x2 + 12} minus_A(x1) = max{231, x1 + 73} -_A(x1,x2) = max{x1 + 73, x2 + 73} *_A(x1,x2) = max{x1 + 121, x2 + 12} D_A(x1) = max{230, x1 - 31} t_A = 15 |1|_A = 0 D#!_A(x1) = max{55, x1 + 19} +!_A(x1,x2) = max{56, x2 - 383} pow!_A(x1,x2) = max{x1 + 57, x2 + 20} ln!_A(x1) = 57 div!_A(x1,x2) = max{x1 + 18, x2 - 21} minus!_A(x1) = max{57, x1 - 231} -!_A(x1,x2) = max{21, x1 - 233, x2 - 464} *!_A(x1,x2) = max{2, x1 - 140} D!_A(x1) = max{58, x1 - 14} t!_A = 58 |1|!_A = 57 partial status: pi(D#) = [] pi(+) = [] pi(pow) = [1] pi(ln) = [] pi(div) = [2] pi(minus) = [] pi(-) = [] pi(*) = [] pi(D) = [] pi(t) = [] pi(|1|) = [] The following rules are removed: p1, p4, p7, p8, p9, p10, p11, p12 -- SCC decomposition. Consider the dependency pair problem (P, R), where P consists of p1: D#(pow(x,y)) -> D#(y) p2: D#(pow(x,y)) -> D#(x) p3: D#(div(x,y)) -> D#(y) p4: D#(div(x,y)) -> D#(x) and R consists of: r1: D(t()) -> |1|() r2: D(constant()) -> |0|() r3: D(+(x,y)) -> +(D(x),D(y)) r4: D(*(x,y)) -> +(*(y,D(x)),*(x,D(y))) r5: D(-(x,y)) -> -(D(x),D(y)) r6: D(minus(x)) -> minus(D(x)) r7: D(div(x,y)) -> -(div(D(x),y),div(*(x,D(y)),pow(y,|2|()))) r8: D(ln(x)) -> div(D(x),x) r9: D(pow(x,y)) -> +(*(*(y,pow(x,-(y,|1|()))),D(x)),*(*(pow(x,y),ln(x)),D(y))) The estimated dependency graph contains the following SCCs: {p1, p2, p3, p4} -- Reduction pair. Consider the dependency pair problem (P, R), where P consists of p1: D#(pow(x,y)) -> D#(y) p2: D#(div(x,y)) -> D#(x) p3: D#(div(x,y)) -> D#(y) p4: D#(pow(x,y)) -> D#(x) and R consists of: r1: D(t()) -> |1|() r2: D(constant()) -> |0|() r3: D(+(x,y)) -> +(D(x),D(y)) r4: D(*(x,y)) -> +(*(y,D(x)),*(x,D(y))) r5: D(-(x,y)) -> -(D(x),D(y)) r6: D(minus(x)) -> minus(D(x)) r7: D(div(x,y)) -> -(div(D(x),y),div(*(x,D(y)),pow(y,|2|()))) r8: D(ln(x)) -> div(D(x),x) r9: D(pow(x,y)) -> +(*(*(y,pow(x,-(y,|1|()))),D(x)),*(*(pow(x,y),ln(x)),D(y))) The set of usable rules consists of (no rules) Take the reduction pair: generalized weighted path order (>=MG, >G) base order 1: matrix interpretation with standard point-wise order: carrier: N^1 order: standard order interpretations: D#_A(x1) = x1 pow_A(x1,x2) = x1 + x2 + 3 div_A(x1,x2) = x1 + x2 + 5 base order 2: marked-algebra reduction triple (>=A, >=A!, >A!): max/plus interpretation on natural numbers: D#_A(x1) = max{0, x1 - 269} pow_A(x1,x2) = max{82, x1 + 76, x2} div_A(x1,x2) = max{431, x1 + 233, x2 + 268} D#!_A(x1) = max{1, x1 - 432} pow!_A(x1,x2) = max{4, x2 - 134} div!_A(x1,x2) = max{5, x1 - 228, x2 - 120} partial status: pi(D#) = [1] pi(pow) = [] pi(div) = [] The following rules are removed: p1, p2, p3, p4 Then no dependency pair remains.