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