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 - 104} +_A(x1,x2) = max{103, x1 + 21, x2 + 2} pow_A(x1,x2) = max{x1 + 23, x2 + 1} ln_A(x1) = max{19, x1} div_A(x1,x2) = max{103, x1 + 74, x2 + 78} minus_A(x1) = x1 + 103 -_A(x1,x2) = max{63, x1 + 47, x2 + 2} *_A(x1,x2) = max{x1 + 1, x2 + 3} D#!_A(x1) = max{2, x1 - 104} +!_A(x1,x2) = max{4, x1 - 90, x2 - 110} pow!_A(x1,x2) = max{5, x1 - 229, x2 - 278} ln!_A(x1) = max{3, x1 - 228} div!_A(x1,x2) = max{4, x1 - 105, x2 - 179} minus!_A(x1) = max{5, x1 - 8} -!_A(x1,x2) = max{1, x1 - 279, x2 - 281} *!_A(x1,x2) = max{1, x1 - 231, x2 - 58} 2. marked-algebra reduction triple (>=A, >=A!, >A!): max/plus interpretation on natural numbers: D#_A(x1) = max{0, x1 - 218} +_A(x1,x2) = max{245, x1 + 217, x2 + 107} pow_A(x1,x2) = max{x1 + 19, x2 + 134} ln_A(x1) = x1 + 86 div_A(x1,x2) = max{130, x1 + 87, x2 + 1} minus_A(x1) = max{245, x1 + 1} -_A(x1,x2) = max{38, x1 + 1, x2 + 11} *_A(x1,x2) = max{x1 + 11, x2 + 28} D#!_A(x1) = max{4, x1 - 240} +!_A(x1,x2) = max{6, x1 - 212, x2 - 239} pow!_A(x1,x2) = max{5, x1 - 445, x2 - 460} ln!_A(x1) = max{2, x1 - 304} div!_A(x1,x2) = max{6, x1 - 57, x2 - 135} minus!_A(x1) = max{114, x1 - 131} -!_A(x1,x2) = max{1, x1 - 461, x2 - 156} *!_A(x1,x2) = max{3, x1 - 459, x2 - 198} partial status: pi(D#) = [] pi(+) = [] pi(pow) = [1, 2] pi(ln) = [] pi(div) = [1] pi(minus) = [1] pi(-) = [] pi(*) = [] The following rules are removed: p1, p7, 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#(ln(x)) -> D#(x) p4: D#(div(x,y)) -> D#(y) p5: D#(div(x,y)) -> D#(x) p6: D#(-(x,y)) -> D#(y) p7: D#(-(x,y)) -> D#(x) p8: D#(*(x,y)) -> D#(y) p9: D#(*(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, p5, p6, p7, p8, p9} -- Reduction pair. Consider the dependency pair problem (P, R), where P consists of p1: D#(pow(x,y)) -> D#(y) p2: D#(*(x,y)) -> D#(x) p3: D#(*(x,y)) -> D#(y) p4: D#(-(x,y)) -> D#(x) p5: D#(-(x,y)) -> D#(y) p6: D#(div(x,y)) -> D#(x) p7: D#(div(x,y)) -> D#(y) p8: D#(ln(x)) -> D#(x) p9: 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: 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 - 16} pow_A(x1,x2) = max{x1 + 15, x2 + 2} *_A(x1,x2) = max{x1 + 6, x2 + 1} -_A(x1,x2) = max{x1 + 3, x2 + 3} div_A(x1,x2) = max{13, x1 + 8, x2 + 6} ln_A(x1) = max{13, x1 + 1} D#!_A(x1) = max{5, x1 - 104} pow!_A(x1,x2) = max{2, x1 - 105, x2 - 109} *!_A(x1,x2) = max{4, x1 - 71, x2 - 36} -!_A(x1,x2) = max{4, x1 - 48, x2 - 22} div!_A(x1,x2) = max{7, x1 - 24, x2 - 28} ln!_A(x1) = max{6, x1 - 67} 2. marked-algebra reduction triple (>=A, >=A!, >A!): max/plus interpretation on natural numbers: D#_A(x1) = max{0, x1 - 64} pow_A(x1,x2) = max{x1 + 47, x2 + 1} *_A(x1,x2) = max{73, x1 + 23, x2 + 15} -_A(x1,x2) = max{54, x1 + 14, x2 + 1} div_A(x1,x2) = max{117, x1 + 63, x2 + 47} ln_A(x1) = max{55, x1} D#!_A(x1) = max{7, x1 - 264} pow!_A(x1,x2) = max{1, x1 - 403, x2 - 463} *!_A(x1,x2) = max{4, x1 - 71, x2 - 63} -!_A(x1,x2) = max{6, x1 - 316, x2 - 263} div!_A(x1,x2) = max{5, x1 - 266, x2 - 200} ln!_A(x1) = max{8, x1 - 213} partial status: pi(D#) = [1] pi(pow) = [1, 2] pi(*) = [1, 2] pi(-) = [1, 2] pi(div) = [1, 2] pi(ln) = [1] The following rules are removed: p1, p2, p3, p4, p5, p6, p7, p8, p9 Then no dependency pair remains.