2.07/2.09 YES 2.26/2.30 We consider the system theBenchmark. 2.26/2.30 2.26/2.30 Alphabet: 2.26/2.30 2.26/2.30 !facminus : [a * a] --> a 2.26/2.30 !facplus : [a * a] --> a 2.26/2.30 !factimes : [a * a] --> a 2.26/2.30 0 : [] --> a 2.26/2.30 1 : [] --> a 2.26/2.30 2 : [] --> a 2.26/2.30 D : [a] --> a 2.26/2.30 cons : [c * d] --> d 2.26/2.30 constant : [] --> a 2.26/2.30 div : [a * a] --> a 2.26/2.30 false : [] --> b 2.26/2.30 filter : [c -> b * d] --> d 2.26/2.30 filter2 : [b * c -> b * c * d] --> d 2.26/2.30 ln : [a] --> a 2.26/2.30 map : [c -> c * d] --> d 2.26/2.30 minus : [a] --> a 2.26/2.30 nil : [] --> d 2.26/2.30 pow : [a * a] --> a 2.26/2.30 t : [] --> a 2.26/2.30 true : [] --> b 2.26/2.30 2.26/2.30 Rules: 2.26/2.30 2.26/2.30 D(t) => 1 2.26/2.30 D(constant) => 0 2.26/2.30 D(!facplus(x, y)) => !facplus(D(x), D(y)) 2.26/2.30 D(!factimes(x, y)) => !facplus(!factimes(y, D(x)), !factimes(x, D(y))) 2.26/2.30 D(!facminus(x, y)) => !facminus(D(x), D(y)) 2.26/2.30 D(minus(x)) => minus(D(x)) 2.26/2.30 D(div(x, y)) => !facminus(div(D(x), y), div(!factimes(x, D(y)), pow(y, 2))) 2.26/2.30 D(ln(x)) => div(D(x), x) 2.26/2.30 D(pow(x, y)) => !facplus(!factimes(!factimes(y, pow(x, !facminus(y, 1))), D(x)), !factimes(!factimes(pow(x, y), ln(x)), D(y))) 2.26/2.30 map(f, nil) => nil 2.26/2.30 map(f, cons(x, y)) => cons(f x, map(f, y)) 2.26/2.30 filter(f, nil) => nil 2.26/2.30 filter(f, cons(x, y)) => filter2(f x, f, x, y) 2.26/2.30 filter2(true, f, x, y) => cons(x, filter(f, y)) 2.26/2.30 filter2(false, f, x, y) => filter(f, y) 2.26/2.30 2.26/2.30 This AFS is converted to an AFSM simply by replacing all free variables by meta-variables (with arity 0). 2.26/2.30 2.26/2.30 We use rule removal, following [Kop12, Theorem 2.23]. 2.26/2.30 2.26/2.30 This gives the following requirements (possibly using Theorems 2.25 and 2.26 in [Kop12]): 2.26/2.30 2.26/2.30 D(t) >? 1 2.26/2.30 D(constant) >? 0 2.26/2.30 D(!facplus(X, Y)) >? !facplus(D(X), D(Y)) 2.26/2.30 D(!factimes(X, Y)) >? !facplus(!factimes(Y, D(X)), !factimes(X, D(Y))) 2.26/2.30 D(!facminus(X, Y)) >? !facminus(D(X), D(Y)) 2.26/2.30 D(minus(X)) >? minus(D(X)) 2.26/2.30 D(div(X, Y)) >? !facminus(div(D(X), Y), div(!factimes(X, D(Y)), pow(Y, 2))) 2.26/2.30 D(ln(X)) >? div(D(X), X) 2.26/2.30 D(pow(X, Y)) >? !facplus(!factimes(!factimes(Y, pow(X, !facminus(Y, 1))), D(X)), !factimes(!factimes(pow(X, Y), ln(X)), D(Y))) 2.26/2.30 map(F, nil) >? nil 2.26/2.30 map(F, cons(X, Y)) >? cons(F X, map(F, Y)) 2.26/2.30 filter(F, nil) >? nil 2.26/2.30 filter(F, cons(X, Y)) >? filter2(F X, F, X, Y) 2.26/2.30 filter2(true, F, X, Y) >? cons(X, filter(F, Y)) 2.26/2.30 filter2(false, F, X, Y) >? filter(F, Y) 2.26/2.30 2.26/2.30 We use a recursive path ordering as defined in [Kop12, Chapter 5]. 2.26/2.30 2.26/2.30 Argument functions: 2.26/2.30 2.26/2.30 [[0]] = _|_ 2.26/2.30 [[1]] = _|_ 2.26/2.30 [[2]] = _|_ 2.26/2.30 [[@_{o -> o}(x_1, x_2)]] = @_{o -> o}(x_2, x_1) 2.26/2.30 [[filter(x_1, x_2)]] = filter(x_2, x_1) 2.26/2.30 [[filter2(x_1, x_2, x_3, x_4)]] = filter2(x_4, x_2, x_1, x_3) 2.26/2.30 [[nil]] = _|_ 2.26/2.30 2.26/2.30 We choose Lex = {@_{o -> o}, filter, filter2} and Mul = {!facminus, !facplus, !factimes, D, cons, constant, div, false, ln, map, minus, pow, t, true}, and the following precedence: false > D > !facplus > !factimes > div > pow > ln > map > !facminus > t > constant > @_{o -> o} = filter = filter2 > cons > minus > true 2.26/2.30 2.26/2.30 Taking the argument function into account, and fixing the greater / greater equal choices, the constraints can be denoted as follows: 2.26/2.30 2.26/2.30 D(t) >= _|_ 2.26/2.30 D(constant) >= _|_ 2.26/2.30 D(!facplus(X, Y)) > !facplus(D(X), D(Y)) 2.26/2.30 D(!factimes(X, Y)) >= !facplus(!factimes(Y, D(X)), !factimes(X, D(Y))) 2.26/2.30 D(!facminus(X, Y)) > !facminus(D(X), D(Y)) 2.26/2.30 D(minus(X)) >= minus(D(X)) 2.26/2.30 D(div(X, Y)) >= !facminus(div(D(X), Y), div(!factimes(X, D(Y)), pow(Y, _|_))) 2.26/2.30 D(ln(X)) >= div(D(X), X) 2.26/2.30 D(pow(X, Y)) > !facplus(!factimes(!factimes(Y, pow(X, !facminus(Y, _|_))), D(X)), !factimes(!factimes(pow(X, Y), ln(X)), D(Y))) 2.26/2.30 map(F, _|_) >= _|_ 2.26/2.30 map(F, cons(X, Y)) > cons(@_{o -> o}(F, X), map(F, Y)) 2.26/2.30 filter(F, _|_) >= _|_ 2.26/2.30 filter(F, cons(X, Y)) >= filter2(@_{o -> o}(F, X), F, X, Y) 2.26/2.30 filter2(true, F, X, Y) >= cons(X, filter(F, Y)) 2.26/2.30 filter2(false, F, X, Y) > filter(F, Y) 2.26/2.30 2.26/2.30 With these choices, we have: 2.26/2.30 2.26/2.30 1] D(t) >= _|_ by (Bot) 2.26/2.30 2.26/2.30 2] D(constant) >= _|_ by (Bot) 2.26/2.30 2.26/2.30 3] D(!facplus(X, Y)) > !facplus(D(X), D(Y)) because [4], by definition 2.26/2.30 4] D*(!facplus(X, Y)) >= !facplus(D(X), D(Y)) because D > !facplus, [5] and [9], by (Copy) 2.26/2.30 5] D*(!facplus(X, Y)) >= D(X) because D in Mul and [6], by (Stat) 2.26/2.30 6] !facplus(X, Y) > X because [7], by definition 2.26/2.30 7] !facplus*(X, Y) >= X because [8], by (Select) 2.26/2.30 8] X >= X by (Meta) 2.26/2.30 9] D*(!facplus(X, Y)) >= D(Y) because D in Mul and [10], by (Stat) 2.26/2.30 10] !facplus(X, Y) > Y because [11], by definition 2.26/2.30 11] !facplus*(X, Y) >= Y because [12], by (Select) 2.26/2.30 12] Y >= Y by (Meta) 2.26/2.30 2.26/2.30 13] D(!factimes(X, Y)) >= !facplus(!factimes(Y, D(X)), !factimes(X, D(Y))) because [14], by (Star) 2.26/2.30 14] D*(!factimes(X, Y)) >= !facplus(!factimes(Y, D(X)), !factimes(X, D(Y))) because D > !facplus, [15] and [24], by (Copy) 2.26/2.30 15] D*(!factimes(X, Y)) >= !factimes(Y, D(X)) because D > !factimes, [16] and [20], by (Copy) 2.26/2.30 16] D*(!factimes(X, Y)) >= Y because [17], by (Select) 2.26/2.30 17] !factimes(X, Y) >= Y because [18], by (Star) 2.26/2.30 18] !factimes*(X, Y) >= Y because [19], by (Select) 2.26/2.30 19] Y >= Y by (Meta) 2.26/2.30 20] D*(!factimes(X, Y)) >= D(X) because D in Mul and [21], by (Stat) 2.26/2.30 21] !factimes(X, Y) > X because [22], by definition 2.26/2.30 22] !factimes*(X, Y) >= X because [23], by (Select) 2.26/2.30 23] X >= X by (Meta) 2.26/2.30 24] D*(!factimes(X, Y)) >= !factimes(X, D(Y)) because D > !factimes, [25] and [27], by (Copy) 2.26/2.30 25] D*(!factimes(X, Y)) >= X because [26], by (Select) 2.26/2.30 26] !factimes(X, Y) >= X because [22], by (Star) 2.26/2.30 27] D*(!factimes(X, Y)) >= D(Y) because D in Mul and [28], by (Stat) 2.26/2.30 28] !factimes(X, Y) > Y because [29], by definition 2.26/2.30 29] !factimes*(X, Y) >= Y because [19], by (Select) 2.26/2.30 2.26/2.30 30] D(!facminus(X, Y)) > !facminus(D(X), D(Y)) because [31], by definition 2.26/2.30 31] D*(!facminus(X, Y)) >= !facminus(D(X), D(Y)) because D > !facminus, [32] and [36], by (Copy) 2.26/2.30 32] D*(!facminus(X, Y)) >= D(X) because D in Mul and [33], by (Stat) 2.26/2.30 33] !facminus(X, Y) > X because [34], by definition 2.26/2.30 34] !facminus*(X, Y) >= X because [35], by (Select) 2.26/2.30 35] X >= X by (Meta) 2.26/2.30 36] D*(!facminus(X, Y)) >= D(Y) because D in Mul and [37], by (Stat) 2.26/2.30 37] !facminus(X, Y) > Y because [38], by definition 2.26/2.30 38] !facminus*(X, Y) >= Y because [39], by (Select) 2.26/2.30 39] Y >= Y by (Meta) 2.26/2.30 2.26/2.30 40] D(minus(X)) >= minus(D(X)) because [41], by (Star) 2.26/2.30 41] D*(minus(X)) >= minus(D(X)) because D > minus and [42], by (Copy) 2.26/2.30 42] D*(minus(X)) >= D(X) because D in Mul and [43], by (Stat) 2.26/2.30 43] minus(X) > X because [44], by definition 2.26/2.30 44] minus*(X) >= X because [45], by (Select) 2.26/2.30 45] X >= X by (Meta) 2.26/2.30 2.26/2.30 46] D(div(X, Y)) >= !facminus(div(D(X), Y), div(!factimes(X, D(Y)), pow(Y, _|_))) because [47], by (Star) 2.26/2.30 47] D*(div(X, Y)) >= !facminus(div(D(X), Y), div(!factimes(X, D(Y)), pow(Y, _|_))) because D > !facminus, [48] and [57], by (Copy) 2.26/2.30 48] D*(div(X, Y)) >= div(D(X), Y) because D > div, [49] and [53], by (Copy) 2.26/2.30 49] D*(div(X, Y)) >= D(X) because D in Mul and [50], by (Stat) 2.26/2.30 50] div(X, Y) > X because [51], by definition 2.26/2.30 51] div*(X, Y) >= X because [52], by (Select) 2.26/2.30 52] X >= X by (Meta) 2.26/2.30 53] D*(div(X, Y)) >= Y because [54], by (Select) 2.26/2.30 54] div(X, Y) >= Y because [55], by (Star) 2.26/2.30 55] div*(X, Y) >= Y because [56], by (Select) 2.26/2.30 56] Y >= Y by (Meta) 2.26/2.30 57] D*(div(X, Y)) >= div(!factimes(X, D(Y)), pow(Y, _|_)) because D > div, [58] and [64], by (Copy) 2.26/2.30 58] D*(div(X, Y)) >= !factimes(X, D(Y)) because D > !factimes, [59] and [61], by (Copy) 2.26/2.30 59] D*(div(X, Y)) >= X because [60], by (Select) 2.26/2.30 60] div(X, Y) >= X because [51], by (Star) 2.26/2.30 61] D*(div(X, Y)) >= D(Y) because D in Mul and [62], by (Stat) 2.26/2.30 62] div(X, Y) > Y because [63], by definition 2.26/2.30 63] div*(X, Y) >= Y because [56], by (Select) 2.26/2.30 64] D*(div(X, Y)) >= pow(Y, _|_) because D > pow, [53] and [65], by (Copy) 2.26/2.30 65] D*(div(X, Y)) >= _|_ by (Bot) 2.26/2.30 2.26/2.30 66] D(ln(X)) >= div(D(X), X) because [67], by (Star) 2.26/2.30 67] D*(ln(X)) >= div(D(X), X) because D > div, [68] and [72], by (Copy) 2.26/2.30 68] D*(ln(X)) >= D(X) because D in Mul and [69], by (Stat) 2.26/2.30 69] ln(X) > X because [70], by definition 2.26/2.30 70] ln*(X) >= X because [71], by (Select) 2.26/2.30 71] X >= X by (Meta) 2.26/2.30 72] D*(ln(X)) >= X because [73], by (Select) 2.26/2.30 73] ln(X) >= X because [70], by (Star) 2.26/2.30 2.26/2.30 74] D(pow(X, Y)) > !facplus(!factimes(!factimes(Y, pow(X, !facminus(Y, _|_))), D(X)), !factimes(!factimes(pow(X, Y), ln(X)), D(Y))) because [75], by definition 2.26/2.30 75] D*(pow(X, Y)) >= !facplus(!factimes(!factimes(Y, pow(X, !facminus(Y, _|_))), D(X)), !factimes(!factimes(pow(X, Y), ln(X)), D(Y))) because D > !facplus, [76] and [95], by (Copy) 2.26/2.30 76] D*(pow(X, Y)) >= !factimes(!factimes(Y, pow(X, !facminus(Y, _|_))), D(X)) because D > !factimes, [77] and [92], by (Copy) 2.26/2.30 77] D*(pow(X, Y)) >= !factimes(Y, pow(X, !facminus(Y, _|_))) because D > !factimes, [78] and [82], by (Copy) 2.26/2.30 78] D*(pow(X, Y)) >= Y because [79], by (Select) 2.26/2.30 79] pow(X, Y) >= Y because [80], by (Star) 2.26/2.30 80] pow*(X, Y) >= Y because [81], by (Select) 2.26/2.30 81] Y >= Y by (Meta) 2.26/2.30 82] D*(pow(X, Y)) >= pow(X, !facminus(Y, _|_)) because D > pow, [83] and [87], by (Copy) 2.26/2.30 83] D*(pow(X, Y)) >= X because [84], by (Select) 2.26/2.30 84] pow(X, Y) >= X because [85], by (Star) 2.26/2.30 85] pow*(X, Y) >= X because [86], by (Select) 2.26/2.30 86] X >= X by (Meta) 2.26/2.30 87] D*(pow(X, Y)) >= !facminus(Y, _|_) because [88], by (Select) 2.26/2.30 88] pow(X, Y) >= !facminus(Y, _|_) because [89], by (Star) 2.26/2.30 89] pow*(X, Y) >= !facminus(Y, _|_) because pow > !facminus, [90] and [91], by (Copy) 2.26/2.30 90] pow*(X, Y) >= Y because [81], by (Select) 2.26/2.30 91] pow*(X, Y) >= _|_ by (Bot) 2.26/2.30 92] D*(pow(X, Y)) >= D(X) because D in Mul and [93], by (Stat) 2.26/2.30 93] pow(X, Y) > X because [94], by definition 2.26/2.30 94] pow*(X, Y) >= X because [86], by (Select) 2.26/2.30 95] D*(pow(X, Y)) >= !factimes(!factimes(pow(X, Y), ln(X)), D(Y)) because D > !factimes, [96] and [99], by (Copy) 2.26/2.30 96] D*(pow(X, Y)) >= !factimes(pow(X, Y), ln(X)) because D > !factimes, [97] and [98], by (Copy) 2.26/2.30 97] D*(pow(X, Y)) >= pow(X, Y) because D > pow, [83] and [78], by (Copy) 2.26/2.30 98] D*(pow(X, Y)) >= ln(X) because D > ln and [83], by (Copy) 2.26/2.30 99] D*(pow(X, Y)) >= D(Y) because D in Mul and [100], by (Stat) 2.26/2.30 100] pow(X, Y) > Y because [90], by definition 2.26/2.30 2.26/2.30 101] map(F, _|_) >= _|_ by (Bot) 2.26/2.30 2.26/2.30 102] map(F, cons(X, Y)) > cons(@_{o -> o}(F, X), map(F, Y)) because [103], by definition 2.26/2.30 103] map*(F, cons(X, Y)) >= cons(@_{o -> o}(F, X), map(F, Y)) because map > cons, [104] and [111], by (Copy) 2.26/2.30 104] map*(F, cons(X, Y)) >= @_{o -> o}(F, X) because map > @_{o -> o}, [105] and [107], by (Copy) 2.26/2.30 105] map*(F, cons(X, Y)) >= F because [106], by (Select) 2.26/2.30 106] F >= F by (Meta) 2.26/2.30 107] map*(F, cons(X, Y)) >= X because [108], by (Select) 2.26/2.30 108] cons(X, Y) >= X because [109], by (Star) 2.26/2.30 109] cons*(X, Y) >= X because [110], by (Select) 2.26/2.30 110] X >= X by (Meta) 2.26/2.30 111] map*(F, cons(X, Y)) >= map(F, Y) because map in Mul, [112] and [113], by (Stat) 2.26/2.30 112] F >= F by (Meta) 2.26/2.30 113] cons(X, Y) > Y because [114], by definition 2.26/2.30 114] cons*(X, Y) >= Y because [115], by (Select) 2.26/2.30 115] Y >= Y by (Meta) 2.26/2.30 2.26/2.30 116] filter(F, _|_) >= _|_ by (Bot) 2.26/2.30 2.26/2.30 117] filter(F, cons(X, Y)) >= filter2(@_{o -> o}(F, X), F, X, Y) because [118], by (Star) 2.26/2.30 118] filter*(F, cons(X, Y)) >= filter2(@_{o -> o}(F, X), F, X, Y) because filter = filter2, [119], [122], [126], [128] and [130], by (Stat) 2.26/2.30 119] cons(X, Y) > Y because [120], by definition 2.26/2.30 120] cons*(X, Y) >= Y because [121], by (Select) 2.26/2.30 121] Y >= Y by (Meta) 2.26/2.30 122] filter*(F, cons(X, Y)) >= @_{o -> o}(F, X) because filter = @_{o -> o}, [123], [126] and [128], by (Stat) 2.26/2.30 123] cons(X, Y) > X because [124], by definition 2.26/2.30 124] cons*(X, Y) >= X because [125], by (Select) 2.26/2.30 125] X >= X by (Meta) 2.26/2.30 126] filter*(F, cons(X, Y)) >= F because [127], by (Select) 2.26/2.30 127] F >= F by (Meta) 2.26/2.30 128] filter*(F, cons(X, Y)) >= X because [129], by (Select) 2.26/2.30 129] cons(X, Y) >= X because [124], by (Star) 2.26/2.30 130] filter*(F, cons(X, Y)) >= Y because [131], by (Select) 2.26/2.30 131] cons(X, Y) >= Y because [120], by (Star) 2.26/2.30 2.26/2.30 132] filter2(true, F, X, Y) >= cons(X, filter(F, Y)) because [133], by (Star) 2.26/2.30 133] filter2*(true, F, X, Y) >= cons(X, filter(F, Y)) because filter2 > cons, [134] and [136], by (Copy) 2.26/2.30 134] filter2*(true, F, X, Y) >= X because [135], by (Select) 2.26/2.30 135] X >= X by (Meta) 2.26/2.30 136] filter2*(true, F, X, Y) >= filter(F, Y) because filter2 = filter, [137], [138], [139] and [140], by (Stat) 2.26/2.30 137] F >= F by (Meta) 2.26/2.30 138] Y >= Y by (Meta) 2.26/2.30 139] filter2*(true, F, X, Y) >= F because [137], by (Select) 2.26/2.30 140] filter2*(true, F, X, Y) >= Y because [138], by (Select) 2.26/2.30 2.26/2.30 141] filter2(false, F, X, Y) > filter(F, Y) because [142], by definition 2.26/2.30 142] filter2*(false, F, X, Y) >= filter(F, Y) because filter2 = filter, [143], [144], [145] and [146], by (Stat) 2.26/2.30 143] F >= F by (Meta) 2.26/2.30 144] Y >= Y by (Meta) 2.26/2.30 145] filter2*(false, F, X, Y) >= F because [143], by (Select) 2.26/2.30 146] filter2*(false, F, X, Y) >= Y because [144], by (Select) 2.26/2.30 2.26/2.30 We can thus remove the following rules: 2.26/2.30 2.26/2.30 D(!facplus(X, Y)) => !facplus(D(X), D(Y)) 2.26/2.30 D(!facminus(X, Y)) => !facminus(D(X), D(Y)) 2.26/2.30 D(pow(X, Y)) => !facplus(!factimes(!factimes(Y, pow(X, !facminus(Y, 1))), D(X)), !factimes(!factimes(pow(X, Y), ln(X)), D(Y))) 2.26/2.30 map(F, cons(X, Y)) => cons(F X, map(F, Y)) 2.26/2.30 filter2(false, F, X, Y) => filter(F, Y) 2.26/2.30 2.26/2.30 We use rule removal, following [Kop12, Theorem 2.23]. 2.26/2.30 2.26/2.30 This gives the following requirements (possibly using Theorems 2.25 and 2.26 in [Kop12]): 2.26/2.30 2.26/2.30 D(t) >? 1 2.26/2.30 D(constant) >? 0 2.26/2.30 D(!factimes(X, Y)) >? !facplus(!factimes(Y, D(X)), !factimes(X, D(Y))) 2.26/2.30 D(minus(X)) >? minus(D(X)) 2.26/2.30 D(div(X, Y)) >? !facminus(div(D(X), Y), div(!factimes(X, D(Y)), pow(Y, 2))) 2.26/2.30 D(ln(X)) >? div(D(X), X) 2.26/2.30 map(F, nil) >? nil 2.26/2.30 filter(F, nil) >? nil 2.26/2.30 filter(F, cons(X, Y)) >? filter2(F X, F, X, Y) 2.26/2.30 filter2(true, F, X, Y) >? cons(X, filter(F, Y)) 2.26/2.30 2.26/2.30 We use a recursive path ordering as defined in [Kop12, Chapter 5]. 2.26/2.30 2.26/2.30 Argument functions: 2.26/2.30 2.26/2.30 [[0]] = _|_ 2.26/2.30 [[1]] = _|_ 2.26/2.30 [[2]] = _|_ 2.26/2.30 [[filter2(x_1, x_2, x_3, x_4)]] = filter2(x_2, x_4, x_3, x_1) 2.26/2.30 [[nil]] = _|_ 2.26/2.30 2.26/2.30 We choose Lex = {filter, filter2} and Mul = {!facminus, !facplus, !factimes, @_{o -> o}, D, cons, constant, div, ln, map, minus, pow, t, true}, and the following precedence: constant > map > t > D = minus > pow > div > ln > !facplus > !factimes > !facminus > filter = filter2 > true > cons > @_{o -> o} 2.26/2.30 2.26/2.30 Taking the argument function into account, and fixing the greater / greater equal choices, the constraints can be denoted as follows: 2.26/2.30 2.26/2.30 D(t) >= _|_ 2.26/2.30 D(constant) >= _|_ 2.26/2.30 D(!factimes(X, Y)) >= !facplus(!factimes(Y, D(X)), !factimes(X, D(Y))) 2.26/2.30 D(minus(X)) >= minus(D(X)) 2.26/2.30 D(div(X, Y)) >= !facminus(div(D(X), Y), div(!factimes(X, D(Y)), pow(Y, _|_))) 2.26/2.30 D(ln(X)) > div(D(X), X) 2.26/2.30 map(F, _|_) > _|_ 2.26/2.30 filter(F, _|_) >= _|_ 2.26/2.30 filter(F, cons(X, Y)) >= filter2(@_{o -> o}(F, X), F, X, Y) 2.26/2.30 filter2(true, F, X, Y) >= cons(X, filter(F, Y)) 2.26/2.30 2.26/2.30 With these choices, we have: 2.26/2.30 2.26/2.30 1] D(t) >= _|_ by (Bot) 2.26/2.30 2.26/2.30 2] D(constant) >= _|_ by (Bot) 2.26/2.30 2.26/2.30 3] D(!factimes(X, Y)) >= !facplus(!factimes(Y, D(X)), !factimes(X, D(Y))) because [4], by (Star) 2.26/2.30 4] D*(!factimes(X, Y)) >= !facplus(!factimes(Y, D(X)), !factimes(X, D(Y))) because D > !facplus, [5] and [14], by (Copy) 2.26/2.30 5] D*(!factimes(X, Y)) >= !factimes(Y, D(X)) because D > !factimes, [6] and [10], by (Copy) 2.26/2.30 6] D*(!factimes(X, Y)) >= Y because [7], by (Select) 2.26/2.30 7] !factimes(X, Y) >= Y because [8], by (Star) 2.26/2.30 8] !factimes*(X, Y) >= Y because [9], by (Select) 2.26/2.30 9] Y >= Y by (Meta) 2.26/2.30 10] D*(!factimes(X, Y)) >= D(X) because D in Mul and [11], by (Stat) 2.26/2.30 11] !factimes(X, Y) > X because [12], by definition 2.26/2.30 12] !factimes*(X, Y) >= X because [13], by (Select) 2.26/2.30 13] X >= X by (Meta) 2.26/2.30 14] D*(!factimes(X, Y)) >= !factimes(X, D(Y)) because D > !factimes, [15] and [17], by (Copy) 2.26/2.30 15] D*(!factimes(X, Y)) >= X because [16], by (Select) 2.26/2.30 16] !factimes(X, Y) >= X because [12], by (Star) 2.26/2.30 17] D*(!factimes(X, Y)) >= D(Y) because D in Mul and [18], by (Stat) 2.26/2.30 18] !factimes(X, Y) > Y because [19], by definition 2.26/2.30 19] !factimes*(X, Y) >= Y because [9], by (Select) 2.26/2.30 2.26/2.30 20] D(minus(X)) >= minus(D(X)) because D = minus, D in Mul and [21], by (Fun) 2.26/2.30 21] minus(X) >= D(X) because minus = D, minus in Mul and [22], by (Fun) 2.26/2.30 22] X >= X by (Meta) 2.26/2.30 2.26/2.30 23] D(div(X, Y)) >= !facminus(div(D(X), Y), div(!factimes(X, D(Y)), pow(Y, _|_))) because [24], by (Star) 2.26/2.30 24] D*(div(X, Y)) >= !facminus(div(D(X), Y), div(!factimes(X, D(Y)), pow(Y, _|_))) because D > !facminus, [25] and [34], by (Copy) 2.26/2.30 25] D*(div(X, Y)) >= div(D(X), Y) because D > div, [26] and [30], by (Copy) 2.26/2.30 26] D*(div(X, Y)) >= D(X) because D in Mul and [27], by (Stat) 2.26/2.30 27] div(X, Y) > X because [28], by definition 2.26/2.30 28] div*(X, Y) >= X because [29], by (Select) 2.26/2.30 29] X >= X by (Meta) 2.26/2.30 30] D*(div(X, Y)) >= Y because [31], by (Select) 2.26/2.30 31] div(X, Y) >= Y because [32], by (Star) 2.26/2.30 32] div*(X, Y) >= Y because [33], by (Select) 2.26/2.30 33] Y >= Y by (Meta) 2.26/2.30 34] D*(div(X, Y)) >= div(!factimes(X, D(Y)), pow(Y, _|_)) because D > div, [35] and [41], by (Copy) 2.26/2.30 35] D*(div(X, Y)) >= !factimes(X, D(Y)) because D > !factimes, [36] and [38], by (Copy) 2.26/2.30 36] D*(div(X, Y)) >= X because [37], by (Select) 2.26/2.30 37] div(X, Y) >= X because [28], by (Star) 2.26/2.30 38] D*(div(X, Y)) >= D(Y) because D in Mul and [39], by (Stat) 2.26/2.30 39] div(X, Y) > Y because [40], by definition 2.26/2.30 40] div*(X, Y) >= Y because [33], by (Select) 2.26/2.30 41] D*(div(X, Y)) >= pow(Y, _|_) because D > pow, [30] and [42], by (Copy) 2.26/2.30 42] D*(div(X, Y)) >= _|_ by (Bot) 2.26/2.30 2.26/2.30 43] D(ln(X)) > div(D(X), X) because [44], by definition 2.26/2.30 44] D*(ln(X)) >= div(D(X), X) because D > div, [45] and [49], by (Copy) 2.26/2.30 45] D*(ln(X)) >= D(X) because D in Mul and [46], by (Stat) 2.26/2.30 46] ln(X) > X because [47], by definition 2.26/2.30 47] ln*(X) >= X because [48], by (Select) 2.26/2.30 48] X >= X by (Meta) 2.26/2.30 49] D*(ln(X)) >= X because [50], by (Select) 2.26/2.30 50] ln(X) >= X because [47], by (Star) 2.26/2.30 2.26/2.30 51] map(F, _|_) > _|_ because [52], by definition 2.26/2.30 52] map*(F, _|_) >= _|_ by (Bot) 2.26/2.30 2.26/2.30 53] filter(F, _|_) >= _|_ by (Bot) 2.26/2.30 2.26/2.30 54] filter(F, cons(X, Y)) >= filter2(@_{o -> o}(F, X), F, X, Y) because [55], by (Star) 2.26/2.30 55] filter*(F, cons(X, Y)) >= filter2(@_{o -> o}(F, X), F, X, Y) because filter = filter2, [56], [57], [60], [61], [62] and [66], by (Stat) 2.26/2.30 56] F >= F by (Meta) 2.26/2.30 57] cons(X, Y) > Y because [58], by definition 2.26/2.30 58] cons*(X, Y) >= Y because [59], by (Select) 2.26/2.30 59] Y >= Y by (Meta) 2.26/2.30 60] filter*(F, cons(X, Y)) >= @_{o -> o}(F, X) because filter > @_{o -> o}, [61] and [62], by (Copy) 2.26/2.30 61] filter*(F, cons(X, Y)) >= F because [56], by (Select) 2.26/2.30 62] filter*(F, cons(X, Y)) >= X because [63], by (Select) 2.26/2.30 63] cons(X, Y) >= X because [64], by (Star) 2.26/2.30 64] cons*(X, Y) >= X because [65], by (Select) 2.26/2.30 65] X >= X by (Meta) 2.26/2.30 66] filter*(F, cons(X, Y)) >= Y because [67], by (Select) 2.26/2.30 67] cons(X, Y) >= Y because [58], by (Star) 2.26/2.30 2.26/2.30 68] filter2(true, F, X, Y) >= cons(X, filter(F, Y)) because [69], by (Star) 2.26/2.30 69] filter2*(true, F, X, Y) >= cons(X, filter(F, Y)) because filter2 > cons, [70] and [72], by (Copy) 2.26/2.30 70] filter2*(true, F, X, Y) >= X because [71], by (Select) 2.26/2.30 71] X >= X by (Meta) 2.26/2.30 72] filter2*(true, F, X, Y) >= filter(F, Y) because filter2 = filter, [73], [74], [75] and [76], by (Stat) 2.26/2.30 73] F >= F by (Meta) 2.26/2.30 74] Y >= Y by (Meta) 2.26/2.30 75] filter2*(true, F, X, Y) >= F because [73], by (Select) 2.26/2.30 76] filter2*(true, F, X, Y) >= Y because [74], by (Select) 2.26/2.30 2.26/2.30 We can thus remove the following rules: 2.26/2.30 2.26/2.30 D(ln(X)) => div(D(X), X) 2.26/2.30 map(F, nil) => nil 2.26/2.30 2.26/2.30 We use rule removal, following [Kop12, Theorem 2.23]. 2.26/2.30 2.26/2.30 This gives the following requirements (possibly using Theorems 2.25 and 2.26 in [Kop12]): 2.26/2.30 2.26/2.30 D(t) >? 1 2.26/2.30 D(constant) >? 0 2.26/2.30 D(!factimes(X, Y)) >? !facplus(!factimes(Y, D(X)), !factimes(X, D(Y))) 2.26/2.30 D(minus(X)) >? minus(D(X)) 2.26/2.30 D(div(X, Y)) >? !facminus(div(D(X), Y), div(!factimes(X, D(Y)), pow(Y, 2))) 2.26/2.30 filter(F, nil) >? nil 2.26/2.30 filter(F, cons(X, Y)) >? filter2(F X, F, X, Y) 2.26/2.30 filter2(true, F, X, Y) >? cons(X, filter(F, Y)) 2.26/2.30 2.26/2.30 We use a recursive path ordering as defined in [Kop12, Chapter 5]. 2.26/2.30 2.26/2.30 Argument functions: 2.26/2.30 2.26/2.30 [[0]] = _|_ 2.26/2.30 [[1]] = _|_ 2.26/2.30 [[2]] = _|_ 2.26/2.30 [[filter(x_1, x_2)]] = filter(x_2, x_1) 2.26/2.30 [[filter2(x_1, x_2, x_3, x_4)]] = filter2(x_4, x_2, x_1, x_3) 2.26/2.30 [[nil]] = _|_ 2.26/2.30 2.26/2.30 We choose Lex = {filter, filter2} and Mul = {!facminus, !facplus, !factimes, @_{o -> o}, D, cons, constant, div, minus, pow, t, true}, and the following precedence: constant > filter = filter2 > @_{o -> o} > cons > D = minus > !facminus > !facplus > div = pow > !factimes > t > true 2.26/2.30 2.26/2.30 Taking the argument function into account, and fixing the greater / greater equal choices, the constraints can be denoted as follows: 2.26/2.30 2.26/2.30 D(t) >= _|_ 2.26/2.30 D(constant) >= _|_ 2.26/2.30 D(!factimes(X, Y)) >= !facplus(!factimes(Y, D(X)), !factimes(X, D(Y))) 2.26/2.30 D(minus(X)) >= minus(D(X)) 2.26/2.30 D(div(X, Y)) >= !facminus(div(D(X), Y), div(!factimes(X, D(Y)), pow(Y, _|_))) 2.26/2.30 filter(F, _|_) >= _|_ 2.26/2.30 filter(F, cons(X, Y)) > filter2(@_{o -> o}(F, X), F, X, Y) 2.26/2.30 filter2(true, F, X, Y) > cons(X, filter(F, Y)) 2.26/2.30 2.26/2.30 With these choices, we have: 2.26/2.30 2.26/2.30 1] D(t) >= _|_ by (Bot) 2.26/2.30 2.26/2.30 2] D(constant) >= _|_ by (Bot) 2.26/2.30 2.26/2.30 3] D(!factimes(X, Y)) >= !facplus(!factimes(Y, D(X)), !factimes(X, D(Y))) because [4], by (Star) 2.26/2.30 4] D*(!factimes(X, Y)) >= !facplus(!factimes(Y, D(X)), !factimes(X, D(Y))) because D > !facplus, [5] and [14], by (Copy) 2.26/2.30 5] D*(!factimes(X, Y)) >= !factimes(Y, D(X)) because D > !factimes, [6] and [10], by (Copy) 2.26/2.30 6] D*(!factimes(X, Y)) >= Y because [7], by (Select) 2.26/2.30 7] !factimes(X, Y) >= Y because [8], by (Star) 2.26/2.30 8] !factimes*(X, Y) >= Y because [9], by (Select) 2.26/2.30 9] Y >= Y by (Meta) 2.26/2.30 10] D*(!factimes(X, Y)) >= D(X) because D in Mul and [11], by (Stat) 2.26/2.30 11] !factimes(X, Y) > X because [12], by definition 2.26/2.30 12] !factimes*(X, Y) >= X because [13], by (Select) 2.26/2.30 13] X >= X by (Meta) 2.26/2.30 14] D*(!factimes(X, Y)) >= !factimes(X, D(Y)) because D > !factimes, [15] and [17], by (Copy) 2.26/2.30 15] D*(!factimes(X, Y)) >= X because [16], by (Select) 2.26/2.30 16] !factimes(X, Y) >= X because [12], by (Star) 2.26/2.30 17] D*(!factimes(X, Y)) >= D(Y) because D in Mul and [18], by (Stat) 2.26/2.30 18] !factimes(X, Y) > Y because [19], by definition 2.26/2.30 19] !factimes*(X, Y) >= Y because [9], by (Select) 2.26/2.30 2.26/2.30 20] D(minus(X)) >= minus(D(X)) because D = minus, D in Mul and [21], by (Fun) 2.26/2.30 21] minus(X) >= D(X) because minus = D, minus in Mul and [22], by (Fun) 2.26/2.30 22] X >= X by (Meta) 2.26/2.30 2.26/2.30 23] D(div(X, Y)) >= !facminus(div(D(X), Y), div(!factimes(X, D(Y)), pow(Y, _|_))) because [24], by (Star) 2.26/2.30 24] D*(div(X, Y)) >= !facminus(div(D(X), Y), div(!factimes(X, D(Y)), pow(Y, _|_))) because D > !facminus, [25] and [34], by (Copy) 2.26/2.30 25] D*(div(X, Y)) >= div(D(X), Y) because D > div, [26] and [30], by (Copy) 2.26/2.30 26] D*(div(X, Y)) >= D(X) because D in Mul and [27], by (Stat) 2.26/2.30 27] div(X, Y) > X because [28], by definition 2.26/2.30 28] div*(X, Y) >= X because [29], by (Select) 2.26/2.30 29] X >= X by (Meta) 2.26/2.30 30] D*(div(X, Y)) >= Y because [31], by (Select) 2.26/2.30 31] div(X, Y) >= Y because [32], by (Star) 2.26/2.30 32] div*(X, Y) >= Y because [33], by (Select) 2.26/2.30 33] Y >= Y by (Meta) 2.26/2.30 34] D*(div(X, Y)) >= div(!factimes(X, D(Y)), pow(Y, _|_)) because D > div, [35] and [41], by (Copy) 2.26/2.30 35] D*(div(X, Y)) >= !factimes(X, D(Y)) because D > !factimes, [36] and [38], by (Copy) 2.26/2.30 36] D*(div(X, Y)) >= X because [37], by (Select) 2.26/2.30 37] div(X, Y) >= X because [28], by (Star) 2.26/2.30 38] D*(div(X, Y)) >= D(Y) because D in Mul and [39], by (Stat) 2.26/2.30 39] div(X, Y) > Y because [40], by definition 2.26/2.30 40] div*(X, Y) >= Y because [33], by (Select) 2.26/2.30 41] D*(div(X, Y)) >= pow(Y, _|_) because [42], by (Select) 2.26/2.30 42] div(X, Y) >= pow(Y, _|_) because div = pow, div in Mul, [43] and [44], by (Fun) 2.26/2.30 43] X >= _|_ by (Bot) 2.26/2.30 44] Y >= Y by (Meta) 2.26/2.30 2.26/2.30 45] filter(F, _|_) >= _|_ by (Bot) 2.26/2.30 2.26/2.30 46] filter(F, cons(X, Y)) > filter2(@_{o -> o}(F, X), F, X, Y) because [47], by definition 2.26/2.30 47] filter*(F, cons(X, Y)) >= filter2(@_{o -> o}(F, X), F, X, Y) because filter = filter2, [48], [51], [52], [54] and [58], by (Stat) 2.26/2.30 48] cons(X, Y) > Y because [49], by definition 2.26/2.30 49] cons*(X, Y) >= Y because [50], by (Select) 2.26/2.30 50] Y >= Y by (Meta) 2.26/2.30 51] filter*(F, cons(X, Y)) >= @_{o -> o}(F, X) because filter > @_{o -> o}, [52] and [54], by (Copy) 2.26/2.30 52] filter*(F, cons(X, Y)) >= F because [53], by (Select) 2.26/2.30 53] F >= F by (Meta) 2.26/2.30 54] filter*(F, cons(X, Y)) >= X because [55], by (Select) 2.26/2.30 55] cons(X, Y) >= X because [56], by (Star) 2.26/2.30 56] cons*(X, Y) >= X because [57], by (Select) 2.26/2.30 57] X >= X by (Meta) 2.26/2.30 58] filter*(F, cons(X, Y)) >= Y because [59], by (Select) 2.26/2.30 59] cons(X, Y) >= Y because [49], by (Star) 2.26/2.30 2.26/2.30 60] filter2(true, F, X, Y) > cons(X, filter(F, Y)) because [61], by definition 2.26/2.30 61] filter2*(true, F, X, Y) >= cons(X, filter(F, Y)) because filter2 > cons, [62] and [64], by (Copy) 2.26/2.30 62] filter2*(true, F, X, Y) >= X because [63], by (Select) 2.26/2.30 63] X >= X by (Meta) 2.26/2.30 64] filter2*(true, F, X, Y) >= filter(F, Y) because filter2 = filter, [65], [66], [67] and [68], by (Stat) 2.26/2.30 65] F >= F by (Meta) 2.26/2.30 66] Y >= Y by (Meta) 2.26/2.30 67] filter2*(true, F, X, Y) >= F because [65], by (Select) 2.26/2.30 68] filter2*(true, F, X, Y) >= Y because [66], by (Select) 2.26/2.30 2.26/2.30 We can thus remove the following rules: 2.26/2.30 2.26/2.30 filter(F, cons(X, Y)) => filter2(F X, F, X, Y) 2.26/2.30 filter2(true, F, X, Y) => cons(X, filter(F, Y)) 2.26/2.30 2.26/2.30 We use rule removal, following [Kop12, Theorem 2.23]. 2.26/2.30 2.26/2.30 This gives the following requirements (possibly using Theorems 2.25 and 2.26 in [Kop12]): 2.26/2.30 2.26/2.30 D(t) >? 1 2.26/2.30 D(constant) >? 0 2.26/2.30 D(!factimes(X, Y)) >? !facplus(!factimes(Y, D(X)), !factimes(X, D(Y))) 2.26/2.30 D(minus(X)) >? minus(D(X)) 2.26/2.30 D(div(X, Y)) >? !facminus(div(D(X), Y), div(!factimes(X, D(Y)), pow(Y, 2))) 2.26/2.30 filter(F, nil) >? nil 2.26/2.30 2.26/2.30 We use a recursive path ordering as defined in [Kop12, Chapter 5]. 2.26/2.30 2.26/2.30 Argument functions: 2.26/2.30 2.26/2.30 [[0]] = _|_ 2.26/2.30 [[1]] = _|_ 2.26/2.30 [[2]] = _|_ 2.26/2.30 [[nil]] = _|_ 2.26/2.30 2.26/2.30 We choose Lex = {} and Mul = {!facminus, !facplus, !factimes, D, constant, div, filter, minus, pow, t}, and the following precedence: D = minus > filter > !facminus > !facplus > t > pow > !factimes > div > constant 2.26/2.30 2.26/2.30 Taking the argument function into account, and fixing the greater / greater equal choices, the constraints can be denoted as follows: 2.26/2.30 2.26/2.30 D(t) >= _|_ 2.26/2.30 D(constant) >= _|_ 2.26/2.30 D(!factimes(X, Y)) > !facplus(!factimes(Y, D(X)), !factimes(X, D(Y))) 2.26/2.30 D(minus(X)) >= minus(D(X)) 2.26/2.30 D(div(X, Y)) > !facminus(div(D(X), Y), div(!factimes(X, D(Y)), pow(Y, _|_))) 2.26/2.30 filter(F, _|_) >= _|_ 2.26/2.30 2.26/2.30 With these choices, we have: 2.26/2.30 2.26/2.30 1] D(t) >= _|_ by (Bot) 2.26/2.30 2.26/2.30 2] D(constant) >= _|_ by (Bot) 2.26/2.30 2.26/2.30 3] D(!factimes(X, Y)) > !facplus(!factimes(Y, D(X)), !factimes(X, D(Y))) because [4], by definition 2.26/2.30 4] D*(!factimes(X, Y)) >= !facplus(!factimes(Y, D(X)), !factimes(X, D(Y))) because D > !facplus, [5] and [14], by (Copy) 2.26/2.30 5] D*(!factimes(X, Y)) >= !factimes(Y, D(X)) because D > !factimes, [6] and [10], by (Copy) 2.26/2.30 6] D*(!factimes(X, Y)) >= Y because [7], by (Select) 2.26/2.30 7] !factimes(X, Y) >= Y because [8], by (Star) 2.26/2.30 8] !factimes*(X, Y) >= Y because [9], by (Select) 2.26/2.30 9] Y >= Y by (Meta) 2.26/2.30 10] D*(!factimes(X, Y)) >= D(X) because D in Mul and [11], by (Stat) 2.26/2.30 11] !factimes(X, Y) > X because [12], by definition 2.26/2.30 12] !factimes*(X, Y) >= X because [13], by (Select) 2.26/2.30 13] X >= X by (Meta) 2.26/2.30 14] D*(!factimes(X, Y)) >= !factimes(X, D(Y)) because D > !factimes, [15] and [17], by (Copy) 2.26/2.30 15] D*(!factimes(X, Y)) >= X because [16], by (Select) 2.26/2.30 16] !factimes(X, Y) >= X because [12], by (Star) 2.26/2.30 17] D*(!factimes(X, Y)) >= D(Y) because D in Mul and [18], by (Stat) 2.26/2.30 18] !factimes(X, Y) > Y because [19], by definition 2.26/2.30 19] !factimes*(X, Y) >= Y because [9], by (Select) 2.26/2.30 2.26/2.30 20] D(minus(X)) >= minus(D(X)) because D = minus, D in Mul and [21], by (Fun) 2.26/2.30 21] minus(X) >= D(X) because minus = D, minus in Mul and [22], by (Fun) 2.26/2.30 22] X >= X by (Meta) 2.26/2.30 2.26/2.30 23] D(div(X, Y)) > !facminus(div(D(X), Y), div(!factimes(X, D(Y)), pow(Y, _|_))) because [24], by definition 2.26/2.30 24] D*(div(X, Y)) >= !facminus(div(D(X), Y), div(!factimes(X, D(Y)), pow(Y, _|_))) because D > !facminus, [25] and [34], by (Copy) 2.26/2.30 25] D*(div(X, Y)) >= div(D(X), Y) because D > div, [26] and [30], by (Copy) 2.26/2.30 26] D*(div(X, Y)) >= D(X) because D in Mul and [27], by (Stat) 2.26/2.30 27] div(X, Y) > X because [28], by definition 2.26/2.30 28] div*(X, Y) >= X because [29], by (Select) 2.26/2.30 29] X >= X by (Meta) 2.26/2.30 30] D*(div(X, Y)) >= Y because [31], by (Select) 2.26/2.30 31] div(X, Y) >= Y because [32], by (Star) 2.26/2.30 32] div*(X, Y) >= Y because [33], by (Select) 2.26/2.30 33] Y >= Y by (Meta) 2.26/2.30 34] D*(div(X, Y)) >= div(!factimes(X, D(Y)), pow(Y, _|_)) because D > div, [35] and [41], by (Copy) 2.26/2.30 35] D*(div(X, Y)) >= !factimes(X, D(Y)) because D > !factimes, [36] and [38], by (Copy) 2.26/2.30 36] D*(div(X, Y)) >= X because [37], by (Select) 2.26/2.30 37] div(X, Y) >= X because [28], by (Star) 2.26/2.30 38] D*(div(X, Y)) >= D(Y) because D in Mul and [39], by (Stat) 2.26/2.30 39] div(X, Y) > Y because [40], by definition 2.26/2.30 40] div*(X, Y) >= Y because [33], by (Select) 2.26/2.30 41] D*(div(X, Y)) >= pow(Y, _|_) because D > pow, [30] and [42], by (Copy) 2.26/2.30 42] D*(div(X, Y)) >= _|_ by (Bot) 2.26/2.30 2.26/2.30 43] filter(F, _|_) >= _|_ by (Bot) 2.26/2.30 2.26/2.30 We can thus remove the following rules: 2.26/2.30 2.26/2.30 D(!factimes(X, Y)) => !facplus(!factimes(Y, D(X)), !factimes(X, D(Y))) 2.26/2.30 D(div(X, Y)) => !facminus(div(D(X), Y), div(!factimes(X, D(Y)), pow(Y, 2))) 2.26/2.30 2.26/2.30 We use rule removal, following [Kop12, Theorem 2.23]. 2.26/2.30 2.26/2.30 This gives the following requirements (possibly using Theorems 2.25 and 2.26 in [Kop12]): 2.26/2.30 2.26/2.30 D(t) >? 1 2.26/2.30 D(constant) >? 0 2.26/2.30 D(minus(X)) >? minus(D(X)) 2.26/2.30 filter(F, nil) >? nil 2.26/2.30 2.26/2.30 We orient these requirements with a polynomial interpretation in the natural numbers. 2.26/2.30 2.26/2.30 The following interpretation satisfies the requirements: 2.26/2.30 2.26/2.30 0 = 0 2.26/2.30 1 = 0 2.26/2.30 D = \y0.3y0 2.26/2.30 constant = 3 2.26/2.30 filter = \G0y1.3 + 3y1 + G0(0) 2.26/2.30 minus = \y0.3 + y0 2.26/2.30 nil = 0 2.26/2.30 t = 3 2.26/2.30 2.26/2.30 Using this interpretation, the requirements translate to: 2.26/2.30 2.26/2.30 [[D(t)]] = 9 > 0 = [[1]] 2.26/2.30 [[D(constant)]] = 9 > 0 = [[0]] 2.26/2.30 [[D(minus(_x0))]] = 9 + 3x0 > 3 + 3x0 = [[minus(D(_x0))]] 2.26/2.30 [[filter(_F0, nil)]] = 3 + F0(0) > 0 = [[nil]] 2.26/2.30 2.26/2.30 We can thus remove the following rules: 2.26/2.30 2.26/2.30 D(t) => 1 2.26/2.30 D(constant) => 0 2.26/2.30 D(minus(X)) => minus(D(X)) 2.26/2.30 filter(F, nil) => nil 2.26/2.30 2.26/2.30 All rules were succesfully removed. Thus, termination of the original system has been reduced to termination of the beta-rule, which is well-known to hold. 2.26/2.30 2.26/2.30 2.26/2.30 +++ Citations +++ 2.26/2.30 2.26/2.30 [Kop12] C. Kop. Higher Order Termination. PhD Thesis, 2012. 2.26/2.30 EOF