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 (no rules) Take the reduction pair: generalized weighted path order (>=MG, >G) base order 1: trivial reduction triple (T x T, T x T, Φ) base order 2: lexicographic combination of reduction triples: 1. marked-algebra reduction triple (>=A, >=A!, >A!): max/plus interpretation on natural numbers: D#_A(x1) = max{0, x1 - 236} +_A(x1,x2) = max{74, x1 + 14, x2 + 14} pow_A(x1,x2) = max{72, x1 + 14, x2 + 17} ln_A(x1) = max{74, x1 + 7} div_A(x1,x2) = max{x1 + 235, x2 + 175} minus_A(x1) = max{74, x1 + 14} -_A(x1,x2) = max{74, x1 + 14, x2 + 14} *_A(x1,x2) = max{x1 + 14, x2 + 79} D#!_A(x1) = max{3, x1 - 3} +!_A(x1,x2) = 4 pow!_A(x1,x2) = max{76, x1 - 2, x2 + 1} ln!_A(x1) = max{77, x1 - 3} div!_A(x1,x2) = max{161, x1 - 52, x2 + 28} minus!_A(x1) = 100 -!_A(x1,x2) = max{x1 + 14, x2 - 300} *!_A(x1,x2) = x2 + 161 2. marked-algebra reduction triple (>=A, >=A!, >A!): matrix interpretation with standard point-wise order: carrier: N^1 order: standard order interpretations: D#_A(x1) = 0 +_A(x1,x2) = 0 pow_A(x1,x2) = x1 + 1 ln_A(x1) = 1 div_A(x1,x2) = 3 minus_A(x1) = 1 -_A(x1,x2) = 5 *_A(x1,x2) = x2 + 1 D#!_A(x1) = 1 +!_A(x1,x2) = 4 pow!_A(x1,x2) = 2 ln!_A(x1) = x1 + 6 div!_A(x1,x2) = 4 minus!_A(x1) = 0 -!_A(x1,x2) = x1 + 6 *!_A(x1,x2) = 3 partial status: pi(D#) = [] pi(+) = [1] pi(pow) = [2] pi(ln) = [1] pi(div) = [1, 2] pi(minus) = [1] pi(-) = [1] pi(*) = [] The following rules are removed: p1, p2, p3, p4, p5, p6, p7, p8, p9, p10, p11, p12 Then no dependency pair remains.