/export/starexec/sandbox2/solver/bin/starexec_run_FirstOrder /export/starexec/sandbox2/benchmark/theBenchmark.xml /export/starexec/sandbox2/output/output_files -------------------------------------------------------------------------------- YES We consider the system theBenchmark. We are asked to determine termination of the following first-order TRS. 0 : [] --> o 2ndsneg : [o * o] --> o 2ndspos : [o * o] --> o activate : [o] --> o cons : [o * o] --> o from : [o] --> o n!6220!6220cons : [o * o] --> o n!6220!6220from : [o] --> o negrecip : [o] --> o pi : [o] --> o plus : [o * o] --> o posrecip : [o] --> o rcons : [o * o] --> o rnil : [] --> o s : [o] --> o square : [o] --> o times : [o * o] --> o from(X) => cons(X, n!6220!6220from(s(X))) 2ndspos(0, X) => rnil 2ndspos(s(X), cons(Y, n!6220!6220cons(Z, U))) => rcons(posrecip(activate(Z)), 2ndsneg(X, activate(U))) 2ndsneg(0, X) => rnil 2ndsneg(s(X), cons(Y, n!6220!6220cons(Z, U))) => rcons(negrecip(activate(Z)), 2ndspos(X, activate(U))) pi(X) => 2ndspos(X, from(0)) plus(0, X) => X plus(s(X), Y) => s(plus(X, Y)) times(0, X) => 0 times(s(X), Y) => plus(Y, times(X, Y)) square(X) => times(X, X) from(X) => n!6220!6220from(X) cons(X, Y) => n!6220!6220cons(X, Y) activate(n!6220!6220from(X)) => from(X) activate(n!6220!6220cons(X, Y)) => cons(X, Y) activate(X) => X We use rule removal, following [Kop12, Theorem 2.23]. This gives the following requirements (possibly using Theorems 2.25 and 2.26 in [Kop12]): from(X) >? cons(X, n!6220!6220from(s(X))) 2ndspos(0, X) >? rnil 2ndspos(s(X), cons(Y, n!6220!6220cons(Z, U))) >? rcons(posrecip(activate(Z)), 2ndsneg(X, activate(U))) 2ndsneg(0, X) >? rnil 2ndsneg(s(X), cons(Y, n!6220!6220cons(Z, U))) >? rcons(negrecip(activate(Z)), 2ndspos(X, activate(U))) pi(X) >? 2ndspos(X, from(0)) plus(0, X) >? X plus(s(X), Y) >? s(plus(X, Y)) times(0, X) >? 0 times(s(X), Y) >? plus(Y, times(X, Y)) square(X) >? times(X, X) from(X) >? n!6220!6220from(X) cons(X, Y) >? n!6220!6220cons(X, Y) activate(n!6220!6220from(X)) >? from(X) activate(n!6220!6220cons(X, Y)) >? cons(X, Y) activate(X) >? X about to try horpo We use a recursive path ordering as defined in [Kop12, Chapter 5]. Argument functions: [[0]] = _|_ [[negrecip(x_1)]] = x_1 [[rnil]] = _|_ We choose Lex = {2ndsneg, 2ndspos} and Mul = {activate, cons, from, n!6220!6220cons, n!6220!6220from, pi, plus, posrecip, rcons, s, square, times}, and the following precedence: pi > square > times > 2ndsneg = 2ndspos > activate = from > plus > posrecip > rcons > cons > n!6220!6220from > n!6220!6220cons > s Taking the argument function into account, and fixing the greater / greater equal choices, the constraints can be denoted as follows: from(X) > cons(X, n!6220!6220from(s(X))) 2ndspos(_|_, X) >= _|_ 2ndspos(s(X), cons(Y, n!6220!6220cons(Z, U))) > rcons(posrecip(activate(Z)), 2ndsneg(X, activate(U))) 2ndsneg(_|_, X) >= _|_ 2ndsneg(s(X), cons(Y, n!6220!6220cons(Z, U))) >= rcons(activate(Z), 2ndspos(X, activate(U))) pi(X) > 2ndspos(X, from(_|_)) plus(_|_, X) > X plus(s(X), Y) >= s(plus(X, Y)) times(_|_, X) > _|_ times(s(X), Y) >= plus(Y, times(X, Y)) square(X) > times(X, X) from(X) >= n!6220!6220from(X) cons(X, Y) > n!6220!6220cons(X, Y) activate(n!6220!6220from(X)) >= from(X) activate(n!6220!6220cons(X, Y)) > cons(X, Y) activate(X) >= X With these choices, we have: 1] from(X) > cons(X, n!6220!6220from(s(X))) because [2], by definition 2] from*(X) >= cons(X, n!6220!6220from(s(X))) because from > cons, [3] and [5], by (Copy) 3] from*(X) >= X because [4], by (Select) 4] X >= X by (Meta) 5] from*(X) >= n!6220!6220from(s(X)) because from > n!6220!6220from and [6], by (Copy) 6] from*(X) >= s(X) because from > s and [3], by (Copy) 7] 2ndspos(_|_, X) >= _|_ by (Bot) 8] 2ndspos(s(X), cons(Y, n!6220!6220cons(Z, U))) > rcons(posrecip(activate(Z)), 2ndsneg(X, activate(U))) because [9], by definition 9] 2ndspos*(s(X), cons(Y, n!6220!6220cons(Z, U))) >= rcons(posrecip(activate(Z)), 2ndsneg(X, activate(U))) because 2ndspos > rcons, [10] and [18], by (Copy) 10] 2ndspos*(s(X), cons(Y, n!6220!6220cons(Z, U))) >= posrecip(activate(Z)) because 2ndspos > posrecip and [11], by (Copy) 11] 2ndspos*(s(X), cons(Y, n!6220!6220cons(Z, U))) >= activate(Z) because 2ndspos > activate and [12], by (Copy) 12] 2ndspos*(s(X), cons(Y, n!6220!6220cons(Z, U))) >= Z because [13], by (Select) 13] cons(Y, n!6220!6220cons(Z, U)) >= Z because [14], by (Star) 14] cons*(Y, n!6220!6220cons(Z, U)) >= Z because [15], by (Select) 15] n!6220!6220cons(Z, U) >= Z because [16], by (Star) 16] n!6220!6220cons*(Z, U) >= Z because [17], by (Select) 17] Z >= Z by (Meta) 18] 2ndspos*(s(X), cons(Y, n!6220!6220cons(Z, U))) >= 2ndsneg(X, activate(U)) because 2ndspos = 2ndsneg, [19], [22] and [24], by (Stat) 19] s(X) > X because [20], by definition 20] s*(X) >= X because [21], by (Select) 21] X >= X by (Meta) 22] 2ndspos*(s(X), cons(Y, n!6220!6220cons(Z, U))) >= X because [23], by (Select) 23] s(X) >= X because [20], by (Star) 24] 2ndspos*(s(X), cons(Y, n!6220!6220cons(Z, U))) >= activate(U) because 2ndspos > activate and [25], by (Copy) 25] 2ndspos*(s(X), cons(Y, n!6220!6220cons(Z, U))) >= U because [26], by (Select) 26] cons(Y, n!6220!6220cons(Z, U)) >= U because [27], by (Star) 27] cons*(Y, n!6220!6220cons(Z, U)) >= U because [28], by (Select) 28] n!6220!6220cons(Z, U) >= U because [29], by (Star) 29] n!6220!6220cons*(Z, U) >= U because [30], by (Select) 30] U >= U by (Meta) 31] 2ndsneg(_|_, X) >= _|_ by (Bot) 32] 2ndsneg(s(X), cons(Y, n!6220!6220cons(Z, U))) >= rcons(activate(Z), 2ndspos(X, activate(U))) because [33], by (Star) 33] 2ndsneg*(s(X), cons(Y, n!6220!6220cons(Z, U))) >= rcons(activate(Z), 2ndspos(X, activate(U))) because 2ndsneg > rcons, [34] and [36], by (Copy) 34] 2ndsneg*(s(X), cons(Y, n!6220!6220cons(Z, U))) >= activate(Z) because 2ndsneg > activate and [35], by (Copy) 35] 2ndsneg*(s(X), cons(Y, n!6220!6220cons(Z, U))) >= Z because [13], by (Select) 36] 2ndsneg*(s(X), cons(Y, n!6220!6220cons(Z, U))) >= 2ndspos(X, activate(U)) because 2ndsneg = 2ndspos, [19], [37] and [38], by (Stat) 37] 2ndsneg*(s(X), cons(Y, n!6220!6220cons(Z, U))) >= X because [23], by (Select) 38] 2ndsneg*(s(X), cons(Y, n!6220!6220cons(Z, U))) >= activate(U) because 2ndsneg > activate and [39], by (Copy) 39] 2ndsneg*(s(X), cons(Y, n!6220!6220cons(Z, U))) >= U because [26], by (Select) 40] pi(X) > 2ndspos(X, from(_|_)) because [41], by definition 41] pi*(X) >= 2ndspos(X, from(_|_)) because pi > 2ndspos, [42] and [43], by (Copy) 42] pi*(X) >= X because [4], by (Select) 43] pi*(X) >= from(_|_) because pi > from and [44], by (Copy) 44] pi*(X) >= _|_ by (Bot) 45] plus(_|_, X) > X because [46], by definition 46] plus*(_|_, X) >= X because [17], by (Select) 47] plus(s(X), Y) >= s(plus(X, Y)) because [48], by (Star) 48] plus*(s(X), Y) >= s(plus(X, Y)) because plus > s and [49], by (Copy) 49] plus*(s(X), Y) >= plus(X, Y) because plus in Mul, [50] and [52], by (Stat) 50] s(X) > X because [51], by definition 51] s*(X) >= X because [4], by (Select) 52] Y >= Y by (Meta) 53] times(_|_, X) > _|_ because [54], by definition 54] times*(_|_, X) >= _|_ by (Bot) 55] times(s(X), Y) >= plus(Y, times(X, Y)) because [56], by (Star) 56] times*(s(X), Y) >= plus(Y, times(X, Y)) because times > plus, [57] and [58], by (Copy) 57] times*(s(X), Y) >= Y because [52], by (Select) 58] times*(s(X), Y) >= times(X, Y) because times in Mul, [50] and [52], by (Stat) 59] square(X) > times(X, X) because [60], by definition 60] square*(X) >= times(X, X) because square > times, [61] and [61], by (Copy) 61] square*(X) >= X because [4], by (Select) 62] from(X) >= n!6220!6220from(X) because [63], by (Star) 63] from*(X) >= n!6220!6220from(X) because from > n!6220!6220from and [3], by (Copy) 64] cons(X, Y) > n!6220!6220cons(X, Y) because [65], by definition 65] cons*(X, Y) >= n!6220!6220cons(X, Y) because cons > n!6220!6220cons, [66] and [68], by (Copy) 66] cons*(X, Y) >= X because [67], by (Select) 67] X >= X by (Meta) 68] cons*(X, Y) >= Y because [69], by (Select) 69] Y >= Y by (Meta) 70] activate(n!6220!6220from(X)) >= from(X) because activate = from, activate in Mul and [71], by (Fun) 71] n!6220!6220from(X) >= X because [72], by (Star) 72] n!6220!6220from*(X) >= X because [4], by (Select) 73] activate(n!6220!6220cons(X, Y)) > cons(X, Y) because [74], by definition 74] activate*(n!6220!6220cons(X, Y)) >= cons(X, Y) because activate > cons, [75] and [78], by (Copy) 75] activate*(n!6220!6220cons(X, Y)) >= X because [76], by (Select) 76] n!6220!6220cons(X, Y) >= X because [77], by (Star) 77] n!6220!6220cons*(X, Y) >= X because [67], by (Select) 78] activate*(n!6220!6220cons(X, Y)) >= Y because [79], by (Select) 79] n!6220!6220cons(X, Y) >= Y because [80], by (Star) 80] n!6220!6220cons*(X, Y) >= Y because [69], by (Select) 81] activate(X) >= X because [82], by (Star) 82] activate*(X) >= X because [4], by (Select) We can thus remove the following rules: from(X) => cons(X, n!6220!6220from(s(X))) 2ndspos(s(X), cons(Y, n!6220!6220cons(Z, U))) => rcons(posrecip(activate(Z)), 2ndsneg(X, activate(U))) pi(X) => 2ndspos(X, from(0)) plus(0, X) => X times(0, X) => 0 square(X) => times(X, X) cons(X, Y) => n!6220!6220cons(X, Y) activate(n!6220!6220cons(X, Y)) => cons(X, 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]): 2ndspos(0, X) >? rnil 2ndsneg(0, X) >? rnil 2ndsneg(s(X), cons(Y, n!6220!6220cons(Z, U))) >? rcons(negrecip(activate(Z)), 2ndspos(X, activate(U))) plus(s(X), Y) >? s(plus(X, Y)) times(s(X), Y) >? plus(Y, times(X, Y)) from(X) >? n!6220!6220from(X) activate(n!6220!6220from(X)) >? from(X) activate(X) >? X about to try horpo We use a recursive path ordering as defined in [Kop12, Chapter 5]. Argument functions: [[rnil]] = _|_ We choose Lex = {} and Mul = {0, 2ndsneg, 2ndspos, activate, cons, from, n!6220!6220cons, n!6220!6220from, negrecip, plus, rcons, s, times}, and the following precedence: 0 > from = n!6220!6220from > 2ndsneg > rcons > negrecip > times > activate > plus > s > cons > n!6220!6220cons > 2ndspos Taking the argument function into account, and fixing the greater / greater equal choices, the constraints can be denoted as follows: 2ndspos(0, X) >= _|_ 2ndsneg(0, X) >= _|_ 2ndsneg(s(X), cons(Y, n!6220!6220cons(Z, U))) >= rcons(negrecip(activate(Z)), 2ndspos(X, activate(U))) plus(s(X), Y) >= s(plus(X, Y)) times(s(X), Y) >= plus(Y, times(X, Y)) from(X) >= n!6220!6220from(X) activate(n!6220!6220from(X)) > from(X) activate(X) >= X With these choices, we have: 1] 2ndspos(0, X) >= _|_ by (Bot) 2] 2ndsneg(0, X) >= _|_ by (Bot) 3] 2ndsneg(s(X), cons(Y, n!6220!6220cons(Z, U))) >= rcons(negrecip(activate(Z)), 2ndspos(X, activate(U))) because [4], by (Star) 4] 2ndsneg*(s(X), cons(Y, n!6220!6220cons(Z, U))) >= rcons(negrecip(activate(Z)), 2ndspos(X, activate(U))) because 2ndsneg > rcons, [5] and [13], by (Copy) 5] 2ndsneg*(s(X), cons(Y, n!6220!6220cons(Z, U))) >= negrecip(activate(Z)) because 2ndsneg > negrecip and [6], by (Copy) 6] 2ndsneg*(s(X), cons(Y, n!6220!6220cons(Z, U))) >= activate(Z) because 2ndsneg > activate and [7], by (Copy) 7] 2ndsneg*(s(X), cons(Y, n!6220!6220cons(Z, U))) >= Z because [8], by (Select) 8] cons(Y, n!6220!6220cons(Z, U)) >= Z because [9], by (Star) 9] cons*(Y, n!6220!6220cons(Z, U)) >= Z because [10], by (Select) 10] n!6220!6220cons(Z, U) >= Z because [11], by (Star) 11] n!6220!6220cons*(Z, U) >= Z because [12], by (Select) 12] Z >= Z by (Meta) 13] 2ndsneg*(s(X), cons(Y, n!6220!6220cons(Z, U))) >= 2ndspos(X, activate(U)) because 2ndsneg > 2ndspos, [14] and [18], by (Copy) 14] 2ndsneg*(s(X), cons(Y, n!6220!6220cons(Z, U))) >= X because [15], by (Select) 15] s(X) >= X because [16], by (Star) 16] s*(X) >= X because [17], by (Select) 17] X >= X by (Meta) 18] 2ndsneg*(s(X), cons(Y, n!6220!6220cons(Z, U))) >= activate(U) because 2ndsneg > activate and [19], by (Copy) 19] 2ndsneg*(s(X), cons(Y, n!6220!6220cons(Z, U))) >= U because [20], by (Select) 20] cons(Y, n!6220!6220cons(Z, U)) >= U because [21], by (Star) 21] cons*(Y, n!6220!6220cons(Z, U)) >= U because [22], by (Select) 22] n!6220!6220cons(Z, U) >= U because [23], by (Star) 23] n!6220!6220cons*(Z, U) >= U because [24], by (Select) 24] U >= U by (Meta) 25] plus(s(X), Y) >= s(plus(X, Y)) because [26], by (Star) 26] plus*(s(X), Y) >= s(plus(X, Y)) because plus > s and [27], by (Copy) 27] plus*(s(X), Y) >= plus(X, Y) because plus in Mul, [28] and [31], by (Stat) 28] s(X) > X because [29], by definition 29] s*(X) >= X because [30], by (Select) 30] X >= X by (Meta) 31] Y >= Y by (Meta) 32] times(s(X), Y) >= plus(Y, times(X, Y)) because [33], by (Star) 33] times*(s(X), Y) >= plus(Y, times(X, Y)) because times > plus, [34] and [35], by (Copy) 34] times*(s(X), Y) >= Y because [31], by (Select) 35] times*(s(X), Y) >= times(X, Y) because times in Mul, [28] and [31], by (Stat) 36] from(X) >= n!6220!6220from(X) because from = n!6220!6220from, from in Mul and [37], by (Fun) 37] X >= X by (Meta) 38] activate(n!6220!6220from(X)) > from(X) because [39], by definition 39] activate*(n!6220!6220from(X)) >= from(X) because [40], by (Select) 40] n!6220!6220from(X) >= from(X) because n!6220!6220from = from, n!6220!6220from in Mul and [37], by (Fun) 41] activate(X) >= X because [42], by (Star) 42] activate*(X) >= X because [37], by (Select) We can thus remove the following rules: activate(n!6220!6220from(X)) => from(X) We use rule removal, following [Kop12, Theorem 2.23]. This gives the following requirements (possibly using Theorems 2.25 and 2.26 in [Kop12]): 2ndspos(0, X) >? rnil 2ndsneg(0, X) >? rnil 2ndsneg(s(X), cons(Y, n!6220!6220cons(Z, U))) >? rcons(negrecip(activate(Z)), 2ndspos(X, activate(U))) plus(s(X), Y) >? s(plus(X, Y)) times(s(X), Y) >? plus(Y, times(X, Y)) from(X) >? n!6220!6220from(X) activate(X) >? X about to try horpo We use a recursive path ordering as defined in [Kop12, Chapter 5]. Argument functions: [[n!6220!6220from(x_1)]] = x_1 [[rnil]] = _|_ We choose Lex = {} and Mul = {0, 2ndsneg, 2ndspos, activate, cons, from, n!6220!6220cons, negrecip, plus, rcons, s, times}, and the following precedence: 0 > 2ndsneg > n!6220!6220cons > rcons > 2ndspos > times > plus > negrecip > s > activate > cons > from Taking the argument function into account, and fixing the greater / greater equal choices, the constraints can be denoted as follows: 2ndspos(0, X) >= _|_ 2ndsneg(0, X) > _|_ 2ndsneg(s(X), cons(Y, n!6220!6220cons(Z, U))) >= rcons(negrecip(activate(Z)), 2ndspos(X, activate(U))) plus(s(X), Y) >= s(plus(X, Y)) times(s(X), Y) > plus(Y, times(X, Y)) from(X) >= X activate(X) >= X With these choices, we have: 1] 2ndspos(0, X) >= _|_ by (Bot) 2] 2ndsneg(0, X) > _|_ because [3], by definition 3] 2ndsneg*(0, X) >= _|_ by (Bot) 4] 2ndsneg(s(X), cons(Y, n!6220!6220cons(Z, U))) >= rcons(negrecip(activate(Z)), 2ndspos(X, activate(U))) because [5], by (Star) 5] 2ndsneg*(s(X), cons(Y, n!6220!6220cons(Z, U))) >= rcons(negrecip(activate(Z)), 2ndspos(X, activate(U))) because 2ndsneg > rcons, [6] and [14], by (Copy) 6] 2ndsneg*(s(X), cons(Y, n!6220!6220cons(Z, U))) >= negrecip(activate(Z)) because [7], by (Select) 7] cons(Y, n!6220!6220cons(Z, U)) >= negrecip(activate(Z)) because [8], by (Star) 8] cons*(Y, n!6220!6220cons(Z, U)) >= negrecip(activate(Z)) because [9], by (Select) 9] n!6220!6220cons(Z, U) >= negrecip(activate(Z)) because [10], by (Star) 10] n!6220!6220cons*(Z, U) >= negrecip(activate(Z)) because n!6220!6220cons > negrecip and [11], by (Copy) 11] n!6220!6220cons*(Z, U) >= activate(Z) because n!6220!6220cons > activate and [12], by (Copy) 12] n!6220!6220cons*(Z, U) >= Z because [13], by (Select) 13] Z >= Z by (Meta) 14] 2ndsneg*(s(X), cons(Y, n!6220!6220cons(Z, U))) >= 2ndspos(X, activate(U)) because 2ndsneg > 2ndspos, [15] and [19], by (Copy) 15] 2ndsneg*(s(X), cons(Y, n!6220!6220cons(Z, U))) >= X because [16], by (Select) 16] s(X) >= X because [17], by (Star) 17] s*(X) >= X because [18], by (Select) 18] X >= X by (Meta) 19] 2ndsneg*(s(X), cons(Y, n!6220!6220cons(Z, U))) >= activate(U) because 2ndsneg > activate and [20], by (Copy) 20] 2ndsneg*(s(X), cons(Y, n!6220!6220cons(Z, U))) >= U because [21], by (Select) 21] cons(Y, n!6220!6220cons(Z, U)) >= U because [22], by (Star) 22] cons*(Y, n!6220!6220cons(Z, U)) >= U because [23], by (Select) 23] n!6220!6220cons(Z, U) >= U because [24], by (Star) 24] n!6220!6220cons*(Z, U) >= U because [25], by (Select) 25] U >= U by (Meta) 26] plus(s(X), Y) >= s(plus(X, Y)) because [27], by (Star) 27] plus*(s(X), Y) >= s(plus(X, Y)) because plus > s and [28], by (Copy) 28] plus*(s(X), Y) >= plus(X, Y) because plus in Mul, [29] and [32], by (Stat) 29] s(X) > X because [30], by definition 30] s*(X) >= X because [31], by (Select) 31] X >= X by (Meta) 32] Y >= Y by (Meta) 33] times(s(X), Y) > plus(Y, times(X, Y)) because [34], by definition 34] times*(s(X), Y) >= plus(Y, times(X, Y)) because times > plus, [35] and [36], by (Copy) 35] times*(s(X), Y) >= Y because [32], by (Select) 36] times*(s(X), Y) >= times(X, Y) because times in Mul, [29] and [32], by (Stat) 37] from(X) >= X because [38], by (Star) 38] from*(X) >= X because [31], by (Select) 39] activate(X) >= X because [40], by (Star) 40] activate*(X) >= X because [31], by (Select) We can thus remove the following rules: 2ndsneg(0, X) => rnil times(s(X), Y) => plus(Y, times(X, 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]): 2ndspos(0, X) >? rnil 2ndsneg(s(X), cons(Y, n!6220!6220cons(Z, U))) >? rcons(negrecip(activate(Z)), 2ndspos(X, activate(U))) plus(s(X), Y) >? s(plus(X, Y)) from(X) >? n!6220!6220from(X) activate(X) >? X We orient these requirements with a polynomial interpretation in the natural numbers. The following interpretation satisfies the requirements: 0 = 3 2ndsneg = \y0y1.3 + 3y0 + 3y1 2ndspos = \y0y1.y0 + y1 activate = \y0.y0 cons = \y0y1.3 + y0 + 3y1 from = \y0.3 + 3y0 n!6220!6220cons = \y0y1.3 + 3y0 + 3y1 n!6220!6220from = \y0.y0 negrecip = \y0.y0 plus = \y0y1.y1 + 3y0 rcons = \y0y1.y0 + y1 rnil = 0 s = \y0.3 + y0 Using this interpretation, the requirements translate to: [[2ndspos(0, _x0)]] = 3 + x0 > 0 = [[rnil]] [[2ndsneg(s(_x0), cons(_x1, n!6220!6220cons(_x2, _x3)))]] = 48 + 3x0 + 3x1 + 27x2 + 27x3 > x0 + x2 + x3 = [[rcons(negrecip(activate(_x2)), 2ndspos(_x0, activate(_x3)))]] [[plus(s(_x0), _x1)]] = 9 + x1 + 3x0 > 3 + x1 + 3x0 = [[s(plus(_x0, _x1))]] [[from(_x0)]] = 3 + 3x0 > x0 = [[n!6220!6220from(_x0)]] [[activate(_x0)]] = x0 >= x0 = [[_x0]] We can thus remove the following rules: 2ndspos(0, X) => rnil 2ndsneg(s(X), cons(Y, n!6220!6220cons(Z, U))) => rcons(negrecip(activate(Z)), 2ndspos(X, activate(U))) plus(s(X), Y) => s(plus(X, Y)) from(X) => n!6220!6220from(X) We use rule removal, following [Kop12, Theorem 2.23]. This gives the following requirements (possibly using Theorems 2.25 and 2.26 in [Kop12]): activate(X) >? X We orient these requirements with a polynomial interpretation in the natural numbers. The following interpretation satisfies the requirements: activate = \y0.1 + y0 Using this interpretation, the requirements translate to: [[activate(_x0)]] = 1 + x0 > x0 = [[_x0]] We can thus remove the following rules: activate(X) => X 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.