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