/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. !plus : [o * o] --> o 1 : [] --> o a : [o * o * o * o] --> o app : [o * o] --> o cons : [o * o] --> o h : [] --> o nil : [] --> o s : [o] --> o sum : [o] --> o a(h, h, h, X) => s(X) a(X, Y, s(Z), h) => a(X, Y, Z, s(h)) a(X, Y, s(Z), s(U)) => a(X, Y, Z, a(X, Y, s(Z), U)) a(X, s(Y), h, Z) => a(X, Y, Z, Z) a(s(X), h, h, Y) => a(X, Y, h, Y) !plus(X, h) => X !plus(h, X) => X !plus(s(X), s(Y)) => s(s(!plus(X, Y))) !plus(!plus(X, Y), Z) => !plus(X, !plus(Y, Z)) s(h) => 1 app(nil, X) => X app(X, nil) => X app(cons(X, Y), Z) => cons(X, app(Y, Z)) sum(cons(X, nil)) => cons(X, nil) sum(cons(X, cons(Y, Z))) => sum(cons(a(X, Y, h, h), Z)) We use rule removal, following [Kop12, Theorem 2.23]. This gives the following requirements (possibly using Theorems 2.25 and 2.26 in [Kop12]): a(h, h, h, X) >? s(X) a(X, Y, s(Z), h) >? a(X, Y, Z, s(h)) a(X, Y, s(Z), s(U)) >? a(X, Y, Z, a(X, Y, s(Z), U)) a(X, s(Y), h, Z) >? a(X, Y, Z, Z) a(s(X), h, h, Y) >? a(X, Y, h, Y) !plus(X, h) >? X !plus(h, X) >? X !plus(s(X), s(Y)) >? s(s(!plus(X, Y))) !plus(!plus(X, Y), Z) >? !plus(X, !plus(Y, Z)) s(h) >? 1 app(nil, X) >? X app(X, nil) >? X app(cons(X, Y), Z) >? cons(X, app(Y, Z)) sum(cons(X, nil)) >? cons(X, nil) sum(cons(X, cons(Y, Z))) >? sum(cons(a(X, Y, h, h), Z)) about to try horpo We use a recursive path ordering as defined in [Kop12, Chapter 5]. Argument functions: [[1]] = _|_ [[cons(x_1, x_2)]] = cons(x_2, x_1) [[h]] = _|_ We choose Lex = {!plus, a, cons} and Mul = {app, nil, s, sum}, and the following precedence: sum > !plus > nil > app > cons > a > s Taking the argument function into account, and fixing the greater / greater equal choices, the constraints can be denoted as follows: a(_|_, _|_, _|_, X) > s(X) a(X, Y, s(Z), _|_) >= a(X, Y, Z, s(_|_)) a(X, Y, s(Z), s(U)) >= a(X, Y, Z, a(X, Y, s(Z), U)) a(X, s(Y), _|_, Z) > a(X, Y, Z, Z) a(s(X), _|_, _|_, Y) > a(X, Y, _|_, Y) !plus(X, _|_) > X !plus(_|_, X) > X !plus(s(X), s(Y)) > s(s(!plus(X, Y))) !plus(!plus(X, Y), Z) >= !plus(X, !plus(Y, Z)) s(_|_) >= _|_ app(nil, X) >= X app(X, nil) > X app(cons(X, Y), Z) >= cons(X, app(Y, Z)) sum(cons(X, nil)) >= cons(X, nil) sum(cons(X, cons(Y, Z))) >= sum(cons(a(X, Y, _|_, _|_), Z)) With these choices, we have: 1] a(_|_, _|_, _|_, X) > s(X) because [2], by definition 2] a*(_|_, _|_, _|_, X) >= s(X) because a > s and [3], by (Copy) 3] a*(_|_, _|_, _|_, X) >= X because [4], by (Select) 4] X >= X by (Meta) 5] a(X, Y, s(Z), _|_) >= a(X, Y, Z, s(_|_)) because [6], by (Star) 6] a*(X, Y, s(Z), _|_) >= a(X, Y, Z, s(_|_)) because [7], [8], [9], [12], [13], [14] and [16], by (Stat) 7] X >= X by (Meta) 8] Y >= Y by (Meta) 9] s(Z) > Z because [10], by definition 10] s*(Z) >= Z because [11], by (Select) 11] Z >= Z by (Meta) 12] a*(X, Y, s(Z), _|_) >= X because [7], by (Select) 13] a*(X, Y, s(Z), _|_) >= Y because [8], by (Select) 14] a*(X, Y, s(Z), _|_) >= Z because [15], by (Select) 15] s(Z) >= Z because [10], by (Star) 16] a*(X, Y, s(Z), _|_) >= s(_|_) because a > s and [17], by (Copy) 17] a*(X, Y, s(Z), _|_) >= _|_ by (Bot) 18] a(X, Y, s(Z), s(U)) >= a(X, Y, Z, a(X, Y, s(Z), U)) because [19], by (Star) 19] a*(X, Y, s(Z), s(U)) >= a(X, Y, Z, a(X, Y, s(Z), U)) because [7], [8], [9], [20], [21], [22] and [23], by (Stat) 20] a*(X, Y, s(Z), s(U)) >= X because [7], by (Select) 21] a*(X, Y, s(Z), s(U)) >= Y because [8], by (Select) 22] a*(X, Y, s(Z), s(U)) >= Z because [15], by (Select) 23] a*(X, Y, s(Z), s(U)) >= a(X, Y, s(Z), U) because [7], [8], [24], [26], [20], [21], [29] and [30], by (Stat) 24] s(Z) >= s(Z) because s in Mul and [25], by (Fun) 25] Z >= Z by (Meta) 26] s(U) > U because [27], by definition 27] s*(U) >= U because [28], by (Select) 28] U >= U by (Meta) 29] a*(X, Y, s(Z), s(U)) >= s(Z) because a > s and [22], by (Copy) 30] a*(X, Y, s(Z), s(U)) >= U because [31], by (Select) 31] s(U) >= U because [27], by (Star) 32] a(X, s(Y), _|_, Z) > a(X, Y, Z, Z) because [33], by definition 33] a*(X, s(Y), _|_, Z) >= a(X, Y, Z, Z) because [7], [34], [36], [37], [39] and [39], by (Stat) 34] s(Y) > Y because [35], by definition 35] s*(Y) >= Y because [8], by (Select) 36] a*(X, s(Y), _|_, Z) >= X because [7], by (Select) 37] a*(X, s(Y), _|_, Z) >= Y because [38], by (Select) 38] s(Y) >= Y because [35], by (Star) 39] a*(X, s(Y), _|_, Z) >= Z because [28], by (Select) 40] a(s(X), _|_, _|_, Y) > a(X, Y, _|_, Y) because [41], by definition 41] a*(s(X), _|_, _|_, Y) >= a(X, Y, _|_, Y) because [42], [44], [46], [47] and [46], by (Stat) 42] s(X) > X because [43], by definition 43] s*(X) >= X because [7], by (Select) 44] a*(s(X), _|_, _|_, Y) >= X because [45], by (Select) 45] s(X) >= X because [43], by (Star) 46] a*(s(X), _|_, _|_, Y) >= Y because [28], by (Select) 47] a*(s(X), _|_, _|_, Y) >= _|_ by (Bot) 48] !plus(X, _|_) > X because [49], by definition 49] !plus*(X, _|_) >= X because [8], by (Select) 50] !plus(_|_, X) > X because [51], by definition 51] !plus*(_|_, X) >= X because [8], by (Select) 52] !plus(s(X), s(Y)) > s(s(!plus(X, Y))) because [53], by definition 53] !plus*(s(X), s(Y)) >= s(s(!plus(X, Y))) because !plus > s and [54], by (Copy) 54] !plus*(s(X), s(Y)) >= s(!plus(X, Y)) because !plus > s and [55], by (Copy) 55] !plus*(s(X), s(Y)) >= !plus(X, Y) because [34], [56] and [57], by (Stat) 56] !plus*(s(X), s(Y)) >= X because [38], by (Select) 57] !plus*(s(X), s(Y)) >= Y because [15], by (Select) 58] !plus(!plus(X, Y), Z) >= !plus(X, !plus(Y, Z)) because [59], by (Star) 59] !plus*(!plus(X, Y), Z) >= !plus(X, !plus(Y, Z)) because [60], [62] and [64], by (Stat) 60] !plus(X, Y) > X because [61], by definition 61] !plus*(X, Y) >= X because [8], by (Select) 62] !plus*(!plus(X, Y), Z) >= X because [63], by (Select) 63] !plus(X, Y) >= X because [61], by (Star) 64] !plus*(!plus(X, Y), Z) >= !plus(Y, Z) because [65], [67] and [69], by (Stat) 65] !plus(X, Y) > Y because [66], by definition 66] !plus*(X, Y) >= Y because [25], by (Select) 67] !plus*(!plus(X, Y), Z) >= Y because [68], by (Select) 68] !plus(X, Y) >= Y because [66], by (Star) 69] !plus*(!plus(X, Y), Z) >= Z because [28], by (Select) 70] s(_|_) >= _|_ by (Bot) 71] app(nil, X) >= X because [72], by (Star) 72] app*(nil, X) >= X because [73], by (Select) 73] X >= X by (Meta) 74] app(X, nil) > X because [75], by definition 75] app*(X, nil) >= X because [7], by (Select) 76] app(cons(X, Y), Z) >= cons(X, app(Y, Z)) because [77], by (Star) 77] app*(cons(X, Y), Z) >= cons(X, app(Y, Z)) because app > cons, [78] and [81], by (Copy) 78] app*(cons(X, Y), Z) >= X because [79], by (Select) 79] cons(X, Y) >= X because [80], by (Star) 80] cons*(X, Y) >= X because [8], by (Select) 81] app*(cons(X, Y), Z) >= app(Y, Z) because app in Mul, [82] and [84], by (Stat) 82] cons(X, Y) > Y because [83], by definition 83] cons*(X, Y) >= Y because [7], by (Select) 84] Z >= Z by (Meta) 85] sum(cons(X, nil)) >= cons(X, nil) because [86], by (Star) 86] sum*(cons(X, nil)) >= cons(X, nil) because [87], by (Select) 87] cons(X, nil) >= cons(X, nil) because [8] and [88], by (Fun) 88] nil >= nil by (Fun) 89] sum(cons(X, cons(Y, Z))) >= sum(cons(a(X, Y, _|_, _|_), Z)) because sum in Mul and [90], by (Fun) 90] cons(X, cons(Y, Z)) >= cons(a(X, Y, _|_, _|_), Z) because [91], by (Star) 91] cons*(X, cons(Y, Z)) >= cons(a(X, Y, _|_, _|_), Z) because [92], [94] and [100], by (Stat) 92] cons(Y, Z) > Z because [93], by definition 93] cons*(Y, Z) >= Z because [7], by (Select) 94] cons*(X, cons(Y, Z)) >= a(X, Y, _|_, _|_) because cons > a, [95], [96], [99] and [99], by (Copy) 95] cons*(X, cons(Y, Z)) >= X because [8], by (Select) 96] cons*(X, cons(Y, Z)) >= Y because [97], by (Select) 97] cons(Y, Z) >= Y because [98], by (Star) 98] cons*(Y, Z) >= Y because [25], by (Select) 99] cons*(X, cons(Y, Z)) >= _|_ by (Bot) 100] cons*(X, cons(Y, Z)) >= Z because [101], by (Select) 101] cons(Y, Z) >= Z because [93], by (Star) We can thus remove the following rules: a(h, h, h, X) => s(X) a(X, s(Y), h, Z) => a(X, Y, Z, Z) a(s(X), h, h, Y) => a(X, Y, h, Y) !plus(X, h) => X !plus(h, X) => X !plus(s(X), s(Y)) => s(s(!plus(X, Y))) app(X, nil) => 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]): a(X, Y, s(Z), h) >? a(X, Y, Z, s(h)) a(X, Y, s(Z), s(U)) >? a(X, Y, Z, a(X, Y, s(Z), U)) !plus(!plus(X, Y), Z) >? !plus(X, !plus(Y, Z)) s(h) >? 1 app(nil, X) >? X app(cons(X, Y), Z) >? cons(X, app(Y, Z)) sum(cons(X, nil)) >? cons(X, nil) sum(cons(X, cons(Y, Z))) >? sum(cons(a(X, Y, h, h), Z)) about to try horpo We use a recursive path ordering as defined in [Kop12, Chapter 5]. Argument functions: [[1]] = _|_ [[a(x_1, x_2, x_3, x_4)]] = a(x_3, x_4, x_1, x_2) [[cons(x_1, x_2)]] = cons(x_2, x_1) [[h]] = _|_ [[nil]] = _|_ We choose Lex = {!plus, a, cons} and Mul = {app, s, sum}, and the following precedence: sum > !plus > app > cons > a > s Taking the argument function into account, and fixing the greater / greater equal choices, the constraints can be denoted as follows: a(X, Y, s(Z), _|_) > a(X, Y, Z, s(_|_)) a(X, Y, s(Z), s(U)) >= a(X, Y, Z, a(X, Y, s(Z), U)) !plus(!plus(X, Y), Z) >= !plus(X, !plus(Y, Z)) s(_|_) > _|_ app(_|_, X) >= X app(cons(X, Y), Z) >= cons(X, app(Y, Z)) sum(cons(X, _|_)) >= cons(X, _|_) sum(cons(X, cons(Y, Z))) >= sum(cons(a(X, Y, _|_, _|_), Z)) With these choices, we have: 1] a(X, Y, s(Z), _|_) > a(X, Y, Z, s(_|_)) because [2], by definition 2] a*(X, Y, s(Z), _|_) >= a(X, Y, Z, s(_|_)) because [3], [6], [8], [10] and [12], by (Stat) 3] s(Z) > Z because [4], by definition 4] s*(Z) >= Z because [5], by (Select) 5] Z >= Z by (Meta) 6] a*(X, Y, s(Z), _|_) >= X because [7], by (Select) 7] X >= X by (Meta) 8] a*(X, Y, s(Z), _|_) >= Y because [9], by (Select) 9] Y >= Y by (Meta) 10] a*(X, Y, s(Z), _|_) >= Z because [11], by (Select) 11] s(Z) >= Z because [4], by (Star) 12] a*(X, Y, s(Z), _|_) >= s(_|_) because a > s and [13], by (Copy) 13] a*(X, Y, s(Z), _|_) >= _|_ by (Bot) 14] a(X, Y, s(Z), s(U)) >= a(X, Y, Z, a(X, Y, s(Z), U)) because [15], by (Star) 15] a*(X, Y, s(Z), s(U)) >= a(X, Y, Z, a(X, Y, s(Z), U)) because [3], [16], [17], [18] and [19], by (Stat) 16] a*(X, Y, s(Z), s(U)) >= X because [7], by (Select) 17] a*(X, Y, s(Z), s(U)) >= Y because [9], by (Select) 18] a*(X, Y, s(Z), s(U)) >= Z because [11], by (Select) 19] a*(X, Y, s(Z), s(U)) >= a(X, Y, s(Z), U) because [20], [22], [16], [17], [25] and [26], by (Stat) 20] s(Z) >= s(Z) because s in Mul and [21], by (Fun) 21] Z >= Z by (Meta) 22] s(U) > U because [23], by definition 23] s*(U) >= U because [24], by (Select) 24] U >= U by (Meta) 25] a*(X, Y, s(Z), s(U)) >= s(Z) because a > s and [18], by (Copy) 26] a*(X, Y, s(Z), s(U)) >= U because [27], by (Select) 27] s(U) >= U because [23], by (Star) 28] !plus(!plus(X, Y), Z) >= !plus(X, !plus(Y, Z)) because [29], by (Star) 29] !plus*(!plus(X, Y), Z) >= !plus(X, !plus(Y, Z)) because [30], [32] and [34], by (Stat) 30] !plus(X, Y) > X because [31], by definition 31] !plus*(X, Y) >= X because [9], by (Select) 32] !plus*(!plus(X, Y), Z) >= X because [33], by (Select) 33] !plus(X, Y) >= X because [31], by (Star) 34] !plus*(!plus(X, Y), Z) >= !plus(Y, Z) because [35], [37] and [39], by (Stat) 35] !plus(X, Y) > Y because [36], by definition 36] !plus*(X, Y) >= Y because [21], by (Select) 37] !plus*(!plus(X, Y), Z) >= Y because [38], by (Select) 38] !plus(X, Y) >= Y because [36], by (Star) 39] !plus*(!plus(X, Y), Z) >= Z because [24], by (Select) 40] s(_|_) > _|_ because [41], by definition 41] s*(_|_) >= _|_ by (Bot) 42] app(_|_, X) >= X because [43], by (Star) 43] app*(_|_, X) >= X because [44], by (Select) 44] X >= X by (Meta) 45] app(cons(X, Y), Z) >= cons(X, app(Y, Z)) because [46], by (Star) 46] app*(cons(X, Y), Z) >= cons(X, app(Y, Z)) because app > cons, [47] and [50], by (Copy) 47] app*(cons(X, Y), Z) >= X because [48], by (Select) 48] cons(X, Y) >= X because [49], by (Star) 49] cons*(X, Y) >= X because [9], by (Select) 50] app*(cons(X, Y), Z) >= app(Y, Z) because app in Mul, [51] and [53], by (Stat) 51] cons(X, Y) > Y because [52], by definition 52] cons*(X, Y) >= Y because [7], by (Select) 53] Z >= Z by (Meta) 54] sum(cons(X, _|_)) >= cons(X, _|_) because [55], by (Star) 55] sum*(cons(X, _|_)) >= cons(X, _|_) because sum > cons, [56] and [59], by (Copy) 56] sum*(cons(X, _|_)) >= X because [57], by (Select) 57] cons(X, _|_) >= X because [58], by (Star) 58] cons*(X, _|_) >= X because [9], by (Select) 59] sum*(cons(X, _|_)) >= _|_ by (Bot) 60] sum(cons(X, cons(Y, Z))) >= sum(cons(a(X, Y, _|_, _|_), Z)) because sum in Mul and [61], by (Fun) 61] cons(X, cons(Y, Z)) >= cons(a(X, Y, _|_, _|_), Z) because [62], by (Star) 62] cons*(X, cons(Y, Z)) >= cons(a(X, Y, _|_, _|_), Z) because [63], [65] and [71], by (Stat) 63] cons(Y, Z) > Z because [64], by definition 64] cons*(Y, Z) >= Z because [7], by (Select) 65] cons*(X, cons(Y, Z)) >= a(X, Y, _|_, _|_) because cons > a, [66], [67], [70] and [70], by (Copy) 66] cons*(X, cons(Y, Z)) >= X because [9], by (Select) 67] cons*(X, cons(Y, Z)) >= Y because [68], by (Select) 68] cons(Y, Z) >= Y because [69], by (Star) 69] cons*(Y, Z) >= Y because [21], by (Select) 70] cons*(X, cons(Y, Z)) >= _|_ by (Bot) 71] cons*(X, cons(Y, Z)) >= Z because [72], by (Select) 72] cons(Y, Z) >= Z because [64], by (Star) We can thus remove the following rules: a(X, Y, s(Z), h) => a(X, Y, Z, s(h)) s(h) => 1 We use rule removal, following [Kop12, Theorem 2.23]. This gives the following requirements (possibly using Theorems 2.25 and 2.26 in [Kop12]): a(X, Y, s(Z), s(U)) >? a(X, Y, Z, a(X, Y, s(Z), U)) !plus(!plus(X, Y), Z) >? !plus(X, !plus(Y, Z)) app(nil, X) >? X app(cons(X, Y), Z) >? cons(X, app(Y, Z)) sum(cons(X, nil)) >? cons(X, nil) sum(cons(X, cons(Y, Z))) >? sum(cons(a(X, Y, h, h), Z)) about to try horpo We use a recursive path ordering as defined in [Kop12, Chapter 5]. Argument functions: [[a(x_1, x_2, x_3, x_4)]] = a(x_3, x_2, x_1, x_4) [[cons(x_1, x_2)]] = cons(x_2, x_1) [[h]] = _|_ [[nil]] = _|_ We choose Lex = {!plus, a, cons} and Mul = {app, s, sum}, and the following precedence: sum > !plus > app > a = cons > s Taking the argument function into account, and fixing the greater / greater equal choices, the constraints can be denoted as follows: a(X, Y, s(Z), s(U)) >= a(X, Y, Z, a(X, Y, s(Z), U)) !plus(!plus(X, Y), Z) > !plus(X, !plus(Y, Z)) app(_|_, X) >= X app(cons(X, Y), Z) >= cons(X, app(Y, Z)) sum(cons(X, _|_)) >= cons(X, _|_) sum(cons(X, cons(Y, Z))) >= sum(cons(a(X, Y, _|_, _|_), Z)) With these choices, we have: 1] a(X, Y, s(Z), s(U)) >= a(X, Y, Z, a(X, Y, s(Z), U)) because [2], by (Star) 2] a*(X, Y, s(Z), s(U)) >= a(X, Y, Z, a(X, Y, s(Z), U)) because [3], [6], [8], [10] and [12], by (Stat) 3] s(Z) > Z because [4], by definition 4] s*(Z) >= Z because [5], by (Select) 5] Z >= Z by (Meta) 6] a*(X, Y, s(Z), s(U)) >= X because [7], by (Select) 7] X >= X by (Meta) 8] a*(X, Y, s(Z), s(U)) >= Y because [9], by (Select) 9] Y >= Y by (Meta) 10] a*(X, Y, s(Z), s(U)) >= Z because [11], by (Select) 11] s(Z) >= Z because [4], by (Star) 12] a*(X, Y, s(Z), s(U)) >= a(X, Y, s(Z), U) because [13], [14], [15], [17], [6], [8], [20] and [21], by (Stat) 13] X >= X by (Meta) 14] Y >= Y by (Meta) 15] s(Z) >= s(Z) because s in Mul and [16], by (Fun) 16] Z >= Z by (Meta) 17] s(U) > U because [18], by definition 18] s*(U) >= U because [19], by (Select) 19] U >= U by (Meta) 20] a*(X, Y, s(Z), s(U)) >= s(Z) because [15], by (Select) 21] a*(X, Y, s(Z), s(U)) >= U because [22], by (Select) 22] s(U) >= U because [18], by (Star) 23] !plus(!plus(X, Y), Z) > !plus(X, !plus(Y, Z)) because [24], by definition 24] !plus*(!plus(X, Y), Z) >= !plus(X, !plus(Y, Z)) because [25], [27] and [29], by (Stat) 25] !plus(X, Y) > X because [26], by definition 26] !plus*(X, Y) >= X because [14], by (Select) 27] !plus*(!plus(X, Y), Z) >= X because [28], by (Select) 28] !plus(X, Y) >= X because [26], by (Star) 29] !plus*(!plus(X, Y), Z) >= !plus(Y, Z) because [30], [32] and [34], by (Stat) 30] !plus(X, Y) > Y because [31], by definition 31] !plus*(X, Y) >= Y because [16], by (Select) 32] !plus*(!plus(X, Y), Z) >= Y because [33], by (Select) 33] !plus(X, Y) >= Y because [31], by (Star) 34] !plus*(!plus(X, Y), Z) >= Z because [19], by (Select) 35] app(_|_, X) >= X because [36], by (Star) 36] app*(_|_, X) >= X because [37], by (Select) 37] X >= X by (Meta) 38] app(cons(X, Y), Z) >= cons(X, app(Y, Z)) because [39], by (Star) 39] app*(cons(X, Y), Z) >= cons(X, app(Y, Z)) because app > cons, [40] and [43], by (Copy) 40] app*(cons(X, Y), Z) >= X because [41], by (Select) 41] cons(X, Y) >= X because [42], by (Star) 42] cons*(X, Y) >= X because [14], by (Select) 43] app*(cons(X, Y), Z) >= app(Y, Z) because app in Mul, [44] and [46], by (Stat) 44] cons(X, Y) > Y because [45], by definition 45] cons*(X, Y) >= Y because [13], by (Select) 46] Z >= Z by (Meta) 47] sum(cons(X, _|_)) >= cons(X, _|_) because [48], by (Star) 48] sum*(cons(X, _|_)) >= cons(X, _|_) because [49], by (Select) 49] cons(X, _|_) >= cons(X, _|_) because [14] and [50], by (Fun) 50] _|_ >= _|_ by (Bot) 51] sum(cons(X, cons(Y, Z))) >= sum(cons(a(X, Y, _|_, _|_), Z)) because [52], by (Star) 52] sum*(cons(X, cons(Y, Z))) >= sum(cons(a(X, Y, _|_, _|_), Z)) because sum in Mul and [53], by (Stat) 53] cons(X, cons(Y, Z)) > cons(a(X, Y, _|_, _|_), Z) because [54], by definition 54] cons*(X, cons(Y, Z)) >= cons(a(X, Y, _|_, _|_), Z) because [55], [57] and [65], by (Stat) 55] cons(Y, Z) > Z because [56], by definition 56] cons*(Y, Z) >= Z because [13], by (Select) 57] cons*(X, cons(Y, Z)) >= a(X, Y, _|_, _|_) because cons = a, [58], [60], [61], [64] and [64], by (Stat) 58] cons(Y, Z) > _|_ because [59], by definition 59] cons*(Y, Z) >= _|_ by (Bot) 60] cons*(X, cons(Y, Z)) >= X because [14], by (Select) 61] cons*(X, cons(Y, Z)) >= Y because [62], by (Select) 62] cons(Y, Z) >= Y because [63], by (Star) 63] cons*(Y, Z) >= Y because [16], by (Select) 64] cons*(X, cons(Y, Z)) >= _|_ by (Bot) 65] cons*(X, cons(Y, Z)) >= Z because [66], by (Select) 66] cons(Y, Z) >= Z because [56], by (Star) We can thus remove the following rules: !plus(!plus(X, Y), Z) => !plus(X, !plus(Y, Z)) We use rule removal, following [Kop12, Theorem 2.23]. This gives the following requirements (possibly using Theorems 2.25 and 2.26 in [Kop12]): a(X, Y, s(Z), s(U)) >? a(X, Y, Z, a(X, Y, s(Z), U)) app(nil, X) >? X app(cons(X, Y), Z) >? cons(X, app(Y, Z)) sum(cons(X, nil)) >? cons(X, nil) sum(cons(X, cons(Y, Z))) >? sum(cons(a(X, Y, h, h), Z)) about to try horpo We use a recursive path ordering as defined in [Kop12, Chapter 5]. Argument functions: [[a(x_1, x_2, x_3, x_4)]] = a(x_3, x_1, x_4, x_2) [[cons(x_1, x_2)]] = cons(x_2, x_1) [[h]] = _|_ [[sum(x_1)]] = x_1 We choose Lex = {a, cons} and Mul = {app, nil, s}, and the following precedence: nil > app > cons > a > s Taking the argument function into account, and fixing the greater / greater equal choices, the constraints can be denoted as follows: a(X, Y, s(Z), s(U)) > a(X, Y, Z, a(X, Y, s(Z), U)) app(nil, X) >= X app(cons(X, Y), Z) > cons(X, app(Y, Z)) cons(X, nil) >= cons(X, nil) cons(X, cons(Y, Z)) >= cons(a(X, Y, _|_, _|_), Z) With these choices, we have: 1] a(X, Y, s(Z), s(U)) > a(X, Y, Z, a(X, Y, s(Z), U)) because [2], by definition 2] a*(X, Y, s(Z), s(U)) >= a(X, Y, Z, a(X, Y, s(Z), U)) because [3], [6], [8], [10] and [12], by (Stat) 3] s(Z) > Z because [4], by definition 4] s*(Z) >= Z because [5], by (Select) 5] Z >= Z by (Meta) 6] a*(X, Y, s(Z), s(U)) >= X because [7], by (Select) 7] X >= X by (Meta) 8] a*(X, Y, s(Z), s(U)) >= Y because [9], by (Select) 9] Y >= Y by (Meta) 10] a*(X, Y, s(Z), s(U)) >= Z because [11], by (Select) 11] s(Z) >= Z because [4], by (Star) 12] a*(X, Y, s(Z), s(U)) >= a(X, Y, s(Z), U) because [13], [14], [16], [6], [8], [19] and [20], by (Stat) 13] X >= X by (Meta) 14] s(Z) >= s(Z) because s in Mul and [15], by (Fun) 15] Z >= Z by (Meta) 16] s(U) > U because [17], by definition 17] s*(U) >= U because [18], by (Select) 18] U >= U by (Meta) 19] a*(X, Y, s(Z), s(U)) >= s(Z) because a > s and [10], by (Copy) 20] a*(X, Y, s(Z), s(U)) >= U because [21], by (Select) 21] s(U) >= U because [17], by (Star) 22] app(nil, X) >= X because [23], by (Star) 23] app*(nil, X) >= X because [24], by (Select) 24] X >= X by (Meta) 25] app(cons(X, Y), Z) > cons(X, app(Y, Z)) because [26], by definition 26] app*(cons(X, Y), Z) >= cons(X, app(Y, Z)) because app > cons, [27] and [30], by (Copy) 27] app*(cons(X, Y), Z) >= X because [28], by (Select) 28] cons(X, Y) >= X because [29], by (Star) 29] cons*(X, Y) >= X because [9], by (Select) 30] app*(cons(X, Y), Z) >= app(Y, Z) because app in Mul, [31] and [33], by (Stat) 31] cons(X, Y) > Y because [32], by definition 32] cons*(X, Y) >= Y because [13], by (Select) 33] Z >= Z by (Meta) 34] cons(X, nil) >= cons(X, nil) because [35] and [36], by (Fun) 35] X >= X by (Meta) 36] nil >= nil by (Fun) 37] cons(X, cons(Y, Z)) >= cons(a(X, Y, _|_, _|_), Z) because [38], by (Star) 38] cons*(X, cons(Y, Z)) >= cons(a(X, Y, _|_, _|_), Z) because [39], [41] and [47], by (Stat) 39] cons(Y, Z) > Z because [40], by definition 40] cons*(Y, Z) >= Z because [13], by (Select) 41] cons*(X, cons(Y, Z)) >= a(X, Y, _|_, _|_) because cons > a, [42], [43], [46] and [46], by (Copy) 42] cons*(X, cons(Y, Z)) >= X because [35], by (Select) 43] cons*(X, cons(Y, Z)) >= Y because [44], by (Select) 44] cons(Y, Z) >= Y because [45], by (Star) 45] cons*(Y, Z) >= Y because [15], by (Select) 46] cons*(X, cons(Y, Z)) >= _|_ by (Bot) 47] cons*(X, cons(Y, Z)) >= Z because [48], by (Select) 48] cons(Y, Z) >= Z because [40], by (Star) We can thus remove the following rules: a(X, Y, s(Z), s(U)) => a(X, Y, Z, a(X, Y, s(Z), U)) app(cons(X, Y), Z) => cons(X, app(Y, Z)) We use rule removal, following [Kop12, Theorem 2.23]. This gives the following requirements (possibly using Theorems 2.25 and 2.26 in [Kop12]): app(nil, X) >? X sum(cons(X, nil)) >? cons(X, nil) sum(cons(X, cons(Y, Z))) >? sum(cons(a(X, Y, h, h), Z)) We orient these requirements with a polynomial interpretation in the natural numbers. The following interpretation satisfies the requirements: a = \y0y1y2y3.y0 + y1 + y2 + y3 app = \y0y1.3 + y0 + y1 cons = \y0y1.2y0 + 2y1 h = 0 nil = 2 sum = \y0.3 + 2y0 Using this interpretation, the requirements translate to: [[app(nil, _x0)]] = 5 + x0 > x0 = [[_x0]] [[sum(cons(_x0, nil))]] = 11 + 4x0 > 4 + 2x0 = [[cons(_x0, nil)]] [[sum(cons(_x0, cons(_x1, _x2)))]] = 3 + 4x0 + 8x1 + 8x2 >= 3 + 4x0 + 4x1 + 4x2 = [[sum(cons(a(_x0, _x1, h, h), _x2))]] We can thus remove the following rules: app(nil, X) => X sum(cons(X, nil)) => cons(X, 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]): sum(cons(X, cons(Y, Z))) >? sum(cons(a(X, Y, h, h), Z)) We orient these requirements with a polynomial interpretation in the natural numbers. The following interpretation satisfies the requirements: a = \y0y1y2y3.y0 + y1 + y2 + y3 cons = \y0y1.3 + 3y0 + 3y1 h = 0 sum = \y0.y0 Using this interpretation, the requirements translate to: [[sum(cons(_x0, cons(_x1, _x2)))]] = 12 + 3x0 + 9x1 + 9x2 > 3 + 3x0 + 3x1 + 3x2 = [[sum(cons(a(_x0, _x1, h, h), _x2))]] We can thus remove the following rules: sum(cons(X, cons(Y, Z))) => sum(cons(a(X, Y, h, h), Z)) 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.