/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. !plus : [o * o] --> o !times : [o * o] --> o 1 : [] --> o a : [o * o * o * o] --> o h : [] --> o s : [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 !times(h, X) => h !times(X, h) => h !times(s(X), s(Y)) => s(!plus(!plus(!times(X, Y), 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]): 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 !times(h, X) >? h !times(X, h) >? h !times(s(X), s(Y)) >? s(!plus(!plus(!times(X, Y), X), Y)) about to try horpo We use a recursive path ordering as defined in [Kop12, Chapter 5]. Argument functions: [[1]] = _|_ We choose Lex = {!plus, a} and Mul = {!times, h, s}, and the following precedence: a > !times > !plus > h = s Taking the argument function into account, and fixing the greater / greater equal choices, the constraints can be denoted as follows: 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) >= _|_ !times(h, X) >= h !times(X, h) >= h !times(s(X), s(Y)) >= s(!plus(!plus(!times(X, Y), X), Y)) With these choices, we have: 1] a(h, h, h, X) >= s(X) because [2], by (Star) 2] a*(h, h, h, X) >= s(X) because a > s and [3], by (Copy) 3] a*(h, h, h, X) >= X because [4], by (Select) 4] X >= X by (Meta) 5] a(X, Y, s(Z), h) > a(X, Y, Z, s(h)) because [6], by definition 6] a*(X, Y, s(Z), h) >= a(X, Y, Z, s(h)) 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), h) >= X because [7], by (Select) 13] a*(X, Y, s(Z), h) >= Y because [8], by (Select) 14] a*(X, Y, s(Z), h) >= Z because [15], by (Select) 15] s(Z) >= Z because [10], by (Star) 16] a*(X, Y, s(Z), h) >= s(h) because a > s and [17], by (Copy) 17] a*(X, Y, s(Z), h) >= h because [18], by (Select) 18] s(Z) >= h because [19], by (Star) 19] s*(Z) >= h because s = h and s in Mul, by (Stat) 20] a(X, Y, s(Z), s(U)) >= a(X, Y, Z, a(X, Y, s(Z), U)) because [21], by (Star) 21] a*(X, Y, s(Z), s(U)) >= a(X, Y, Z, a(X, Y, s(Z), U)) because [7], [8], [9], [22], [23], [24] and [25], by (Stat) 22] a*(X, Y, s(Z), s(U)) >= X because [7], by (Select) 23] a*(X, Y, s(Z), s(U)) >= Y because [8], by (Select) 24] a*(X, Y, s(Z), s(U)) >= Z because [15], by (Select) 25] a*(X, Y, s(Z), s(U)) >= a(X, Y, s(Z), U) because [7], [8], [26], [28], [22], [23], [31] and [32], by (Stat) 26] s(Z) >= s(Z) because s in Mul and [27], by (Fun) 27] Z >= Z by (Meta) 28] s(U) > U because [29], by definition 29] s*(U) >= U because [30], by (Select) 30] U >= U by (Meta) 31] a*(X, Y, s(Z), s(U)) >= s(Z) because [26], by (Select) 32] a*(X, Y, s(Z), s(U)) >= U because [33], by (Select) 33] s(U) >= U because [29], by (Star) 34] a(X, s(Y), h, Z) > a(X, Y, Z, Z) because [35], by definition 35] a*(X, s(Y), h, Z) >= a(X, Y, Z, Z) because [7], [36], [38], [39], [41] and [41], by (Stat) 36] s(Y) > Y because [37], by definition 37] s*(Y) >= Y because [8], by (Select) 38] a*(X, s(Y), h, Z) >= X because [7], by (Select) 39] a*(X, s(Y), h, Z) >= Y because [40], by (Select) 40] s(Y) >= Y because [37], by (Star) 41] a*(X, s(Y), h, Z) >= Z because [30], by (Select) 42] a(s(X), h, h, Y) >= a(X, Y, h, Y) because [43], by (Star) 43] a*(s(X), h, h, Y) >= a(X, Y, h, Y) because [44], [46], [48], [49] and [48], by (Stat) 44] s(X) > X because [45], by definition 45] s*(X) >= X because [7], by (Select) 46] a*(s(X), h, h, Y) >= X because [47], by (Select) 47] s(X) >= X because [45], by (Star) 48] a*(s(X), h, h, Y) >= Y because [30], by (Select) 49] a*(s(X), h, h, Y) >= h because a > h, by (Copy) 50] !plus(X, h) > X because [51], by definition 51] !plus*(X, h) >= X because [8], by (Select) 52] !plus(h, X) > X because [53], by definition 53] !plus*(h, X) >= X because [8], by (Select) 54] !plus(s(X), s(Y)) > s(s(!plus(X, Y))) because [55], by definition 55] !plus*(s(X), s(Y)) >= s(s(!plus(X, Y))) because !plus > s and [56], by (Copy) 56] !plus*(s(X), s(Y)) >= s(!plus(X, Y)) because !plus > s and [57], by (Copy) 57] !plus*(s(X), s(Y)) >= !plus(X, Y) because [36], [58] and [59], by (Stat) 58] !plus*(s(X), s(Y)) >= X because [40], by (Select) 59] !plus*(s(X), s(Y)) >= Y because [15], by (Select) 60] !plus(!plus(X, Y), Z) >= !plus(X, !plus(Y, Z)) because [61], by (Star) 61] !plus*(!plus(X, Y), Z) >= !plus(X, !plus(Y, Z)) because [62], [64] and [66], by (Stat) 62] !plus(X, Y) > X because [63], by definition 63] !plus*(X, Y) >= X because [8], by (Select) 64] !plus*(!plus(X, Y), Z) >= X because [65], by (Select) 65] !plus(X, Y) >= X because [63], by (Star) 66] !plus*(!plus(X, Y), Z) >= !plus(Y, Z) because [67], [69] and [71], by (Stat) 67] !plus(X, Y) > Y because [68], by definition 68] !plus*(X, Y) >= Y because [27], by (Select) 69] !plus*(!plus(X, Y), Z) >= Y because [70], by (Select) 70] !plus(X, Y) >= Y because [68], by (Star) 71] !plus*(!plus(X, Y), Z) >= Z because [30], by (Select) 72] s(h) >= _|_ by (Bot) 73] !times(h, X) >= h because [74], by (Star) 74] !times*(h, X) >= h because !times > h, by (Copy) 75] !times(X, h) >= h because [76], by (Star) 76] !times*(X, h) >= h because !times > h, by (Copy) 77] !times(s(X), s(Y)) >= s(!plus(!plus(!times(X, Y), X), Y)) because [78], by (Star) 78] !times*(s(X), s(Y)) >= s(!plus(!plus(!times(X, Y), X), Y)) because !times > s and [79], by (Copy) 79] !times*(s(X), s(Y)) >= !plus(!plus(!times(X, Y), X), Y) because !times > !plus, [80] and [84], by (Copy) 80] !times*(s(X), s(Y)) >= !plus(!times(X, Y), X) because !times > !plus, [81] and [83], by (Copy) 81] !times*(s(X), s(Y)) >= !times(X, Y) because !times in Mul, [36] and [82], by (Stat) 82] s(Y) >= Y because [10], by (Star) 83] !times*(s(X), s(Y)) >= X because [40], by (Select) 84] !times*(s(X), s(Y)) >= Y because [82], by (Select) We can thus remove the following rules: a(X, Y, s(Z), h) => a(X, Y, Z, s(h)) a(X, s(Y), h, Z) => a(X, Y, Z, Z) !plus(X, h) => X !plus(h, X) => X !plus(s(X), s(Y)) => s(s(!plus(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]): a(h, h, h, X) >? s(X) a(X, Y, s(Z), s(U)) >? a(X, Y, Z, a(X, Y, s(Z), U)) a(s(X), h, h, Y) >? a(X, Y, h, Y) !plus(!plus(X, Y), Z) >? !plus(X, !plus(Y, Z)) s(h) >? 1 !times(h, X) >? h !times(X, h) >? h !times(s(X), s(Y)) >? s(!plus(!plus(!times(X, Y), X), Y)) 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_1, x_3, x_4, x_2) We choose Lex = {!plus, a} and Mul = {!times, h, s}, and the following precedence: !times > a > s > h > !plus Taking the argument function into account, and fixing the greater / greater equal choices, the constraints can be denoted as follows: a(h, h, h, X) >= s(X) a(X, Y, s(Z), s(U)) >= a(X, Y, Z, a(X, Y, s(Z), U)) a(s(X), h, h, Y) >= a(X, Y, h, Y) !plus(!plus(X, Y), Z) >= !plus(X, !plus(Y, Z)) s(h) >= _|_ !times(h, X) > h !times(X, h) >= h !times(s(X), s(Y)) >= s(!plus(!plus(!times(X, Y), X), Y)) With these choices, we have: 1] a(h, h, h, X) >= s(X) because [2], by (Star) 2] a*(h, h, h, X) >= s(X) because a > s and [3], by (Copy) 3] a*(h, h, h, X) >= X because [4], by (Select) 4] X >= X by (Meta) 5] a(X, Y, s(Z), s(U)) >= a(X, Y, Z, a(X, Y, s(Z), U)) because [6], by (Star) 6] a*(X, Y, s(Z), s(U)) >= a(X, Y, Z, a(X, Y, s(Z), U)) because [7], [8], [11], [12], [13] and [15], by (Stat) 7] X >= X by (Meta) 8] s(Z) > Z because [9], by definition 9] s*(Z) >= Z because [10], by (Select) 10] Z >= Z by (Meta) 11] a*(X, Y, s(Z), s(U)) >= X because [7], by (Select) 12] a*(X, Y, s(Z), s(U)) >= Y because [4], by (Select) 13] a*(X, Y, s(Z), s(U)) >= Z because [14], by (Select) 14] s(Z) >= Z because [9], by (Star) 15] a*(X, Y, s(Z), s(U)) >= a(X, Y, s(Z), U) because [7], [16], [18], [11], [12], [21] and [22], by (Stat) 16] s(Z) >= s(Z) because s in Mul and [17], by (Fun) 17] Z >= Z by (Meta) 18] s(U) > U because [19], by definition 19] s*(U) >= U because [20], by (Select) 20] U >= U by (Meta) 21] a*(X, Y, s(Z), s(U)) >= s(Z) because a > s and [13], by (Copy) 22] a*(X, Y, s(Z), s(U)) >= U because [23], by (Select) 23] s(U) >= U because [19], by (Star) 24] a(s(X), h, h, Y) >= a(X, Y, h, Y) because [25], by (Star) 25] a*(s(X), h, h, Y) >= a(X, Y, h, Y) because [26], [28], [30], [31] and [30], by (Stat) 26] s(X) > X because [27], by definition 27] s*(X) >= X because [7], by (Select) 28] a*(s(X), h, h, Y) >= X because [29], by (Select) 29] s(X) >= X because [27], by (Star) 30] a*(s(X), h, h, Y) >= Y because [20], by (Select) 31] a*(s(X), h, h, Y) >= h because [32], by (Select) 32] s(X) >= h because [33], by (Star) 33] s*(X) >= h because s > h, by (Copy) 34] !plus(!plus(X, Y), Z) >= !plus(X, !plus(Y, Z)) because [35], by (Star) 35] !plus*(!plus(X, Y), Z) >= !plus(X, !plus(Y, Z)) because [36], [38] and [40], by (Stat) 36] !plus(X, Y) > X because [37], by definition 37] !plus*(X, Y) >= X because [4], by (Select) 38] !plus*(!plus(X, Y), Z) >= X because [39], by (Select) 39] !plus(X, Y) >= X because [37], by (Star) 40] !plus*(!plus(X, Y), Z) >= !plus(Y, Z) because [41], [43] and [45], by (Stat) 41] !plus(X, Y) > Y because [42], by definition 42] !plus*(X, Y) >= Y because [17], by (Select) 43] !plus*(!plus(X, Y), Z) >= Y because [44], by (Select) 44] !plus(X, Y) >= Y because [42], by (Star) 45] !plus*(!plus(X, Y), Z) >= Z because [20], by (Select) 46] s(h) >= _|_ by (Bot) 47] !times(h, X) > h because [48], by definition 48] !times*(h, X) >= h because !times > h, by (Copy) 49] !times(X, h) >= h because [50], by (Star) 50] !times*(X, h) >= h because !times > h, by (Copy) 51] !times(s(X), s(Y)) >= s(!plus(!plus(!times(X, Y), X), Y)) because [52], by (Star) 52] !times*(s(X), s(Y)) >= s(!plus(!plus(!times(X, Y), X), Y)) because !times > s and [53], by (Copy) 53] !times*(s(X), s(Y)) >= !plus(!plus(!times(X, Y), X), Y) because !times > !plus, [54] and [61], by (Copy) 54] !times*(s(X), s(Y)) >= !plus(!times(X, Y), X) because !times > !plus, [55] and [59], by (Copy) 55] !times*(s(X), s(Y)) >= !times(X, Y) because !times in Mul, [56] and [58], by (Stat) 56] s(X) > X because [57], by definition 57] s*(X) >= X because [4], by (Select) 58] s(Y) >= Y because [9], by (Star) 59] !times*(s(X), s(Y)) >= X because [60], by (Select) 60] s(X) >= X because [57], by (Star) 61] !times*(s(X), s(Y)) >= Y because [58], by (Select) We can thus remove the following rules: !times(h, X) => h 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), s(U)) >? a(X, Y, Z, a(X, Y, s(Z), U)) a(s(X), h, h, Y) >? a(X, Y, h, Y) !plus(!plus(X, Y), Z) >? !plus(X, !plus(Y, Z)) s(h) >? 1 !times(X, h) >? h !times(s(X), s(Y)) >? s(!plus(!plus(!times(X, Y), X), Y)) 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_1, x_3, x_4, x_2) We choose Lex = {!plus, a} and Mul = {!times, h, s}, and the following precedence: !times > !plus > h > a > s Taking the argument function into account, and fixing the greater / greater equal choices, the constraints can be denoted as follows: a(h, h, h, X) > s(X) a(X, Y, s(Z), s(U)) >= a(X, Y, Z, a(X, Y, s(Z), U)) a(s(X), h, h, Y) > a(X, Y, h, Y) !plus(!plus(X, Y), Z) > !plus(X, !plus(Y, Z)) s(h) >= _|_ !times(X, h) > h !times(s(X), s(Y)) >= s(!plus(!plus(!times(X, Y), X), Y)) With these choices, we have: 1] a(h, h, h, X) > s(X) because [2], by definition 2] a*(h, h, h, X) >= s(X) because a > s and [3], by (Copy) 3] a*(h, h, h, X) >= X because [4], by (Select) 4] X >= X by (Meta) 5] a(X, Y, s(Z), s(U)) >= a(X, Y, Z, a(X, Y, s(Z), U)) because [6], by (Star) 6] a*(X, Y, s(Z), s(U)) >= a(X, Y, Z, a(X, Y, s(Z), U)) because [7], [8], [11], [12], [13] and [15], by (Stat) 7] X >= X by (Meta) 8] s(Z) > Z because [9], by definition 9] s*(Z) >= Z because [10], by (Select) 10] Z >= Z by (Meta) 11] a*(X, Y, s(Z), s(U)) >= X because [7], by (Select) 12] a*(X, Y, s(Z), s(U)) >= Y because [4], by (Select) 13] a*(X, Y, s(Z), s(U)) >= Z because [14], by (Select) 14] s(Z) >= Z because [9], by (Star) 15] a*(X, Y, s(Z), s(U)) >= a(X, Y, s(Z), U) because [7], [16], [18], [11], [12], [21] and [22], by (Stat) 16] s(Z) >= s(Z) because s in Mul and [17], by (Fun) 17] Z >= Z by (Meta) 18] s(U) > U because [19], by definition 19] s*(U) >= U because [20], by (Select) 20] U >= U by (Meta) 21] a*(X, Y, s(Z), s(U)) >= s(Z) because a > s and [13], by (Copy) 22] a*(X, Y, s(Z), s(U)) >= U because [23], by (Select) 23] s(U) >= U because [19], by (Star) 24] a(s(X), h, h, Y) > a(X, Y, h, Y) because [25], by definition 25] a*(s(X), h, h, Y) >= a(X, Y, h, Y) because [26], [28], [30], [31] and [30], by (Stat) 26] s(X) > X because [27], by definition 27] s*(X) >= X because [7], by (Select) 28] a*(s(X), h, h, Y) >= X because [29], by (Select) 29] s(X) >= X because [27], by (Star) 30] a*(s(X), h, h, Y) >= Y because [20], by (Select) 31] a*(s(X), h, h, Y) >= h because [32], by (Select) 32] h >= h by (Fun) 33] !plus(!plus(X, Y), Z) > !plus(X, !plus(Y, Z)) because [34], by definition 34] !plus*(!plus(X, Y), Z) >= !plus(X, !plus(Y, Z)) because [35], [37] and [39], by (Stat) 35] !plus(X, Y) > X because [36], by definition 36] !plus*(X, Y) >= X because [4], by (Select) 37] !plus*(!plus(X, Y), Z) >= X because [38], by (Select) 38] !plus(X, Y) >= X because [36], by (Star) 39] !plus*(!plus(X, Y), Z) >= !plus(Y, Z) because [40], [42] and [44], by (Stat) 40] !plus(X, Y) > Y because [41], by definition 41] !plus*(X, Y) >= Y because [17], by (Select) 42] !plus*(!plus(X, Y), Z) >= Y because [43], by (Select) 43] !plus(X, Y) >= Y because [41], by (Star) 44] !plus*(!plus(X, Y), Z) >= Z because [20], by (Select) 45] s(h) >= _|_ by (Bot) 46] !times(X, h) > h because [47], by definition 47] !times*(X, h) >= h because !times > h, by (Copy) 48] !times(s(X), s(Y)) >= s(!plus(!plus(!times(X, Y), X), Y)) because [49], by (Star) 49] !times*(s(X), s(Y)) >= s(!plus(!plus(!times(X, Y), X), Y)) because !times > s and [50], by (Copy) 50] !times*(s(X), s(Y)) >= !plus(!plus(!times(X, Y), X), Y) because !times > !plus, [51] and [56], by (Copy) 51] !times*(s(X), s(Y)) >= !plus(!times(X, Y), X) because !times > !plus, [52] and [55], by (Copy) 52] !times*(s(X), s(Y)) >= !times(X, Y) because !times in Mul, [53] and [8], by (Stat) 53] s(X) >= X because [54], by (Star) 54] s*(X) >= X because [4], by (Select) 55] !times*(s(X), s(Y)) >= X because [53], by (Select) 56] !times*(s(X), s(Y)) >= Y because [14], by (Select) We can thus remove the following rules: a(h, h, h, X) => s(X) a(s(X), h, h, Y) => a(X, Y, h, Y) !plus(!plus(X, Y), Z) => !plus(X, !plus(Y, Z)) !times(X, h) => h 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)) s(h) >? 1 !times(s(X), s(Y)) >? s(!plus(!plus(!times(X, Y), X), Y)) 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_2, x_4, x_1) We choose Lex = {a} and Mul = {!plus, !times, h, s}, and the following precedence: h > a > !times > !plus > 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)) s(h) > _|_ !times(s(X), s(Y)) >= s(!plus(!plus(!times(X, Y), X), Y)) 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], [16], [6], [8], [19] and [20], by (Stat) 13] Y >= Y 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] s(h) > _|_ because [23], by definition 23] s*(h) >= _|_ by (Bot) 24] !times(s(X), s(Y)) >= s(!plus(!plus(!times(X, Y), X), Y)) because [25], by (Star) 25] !times*(s(X), s(Y)) >= s(!plus(!plus(!times(X, Y), X), Y)) because !times > s and [26], by (Copy) 26] !times*(s(X), s(Y)) >= !plus(!plus(!times(X, Y), X), Y) because !times > !plus, [27] and [32], by (Copy) 27] !times*(s(X), s(Y)) >= !plus(!times(X, Y), X) because !times > !plus, [28] and [31], by (Copy) 28] !times*(s(X), s(Y)) >= !times(X, Y) because !times in Mul, [29] and [3], by (Stat) 29] s(X) >= X because [30], by (Star) 30] s*(X) >= X because [13], by (Select) 31] !times*(s(X), s(Y)) >= X because [29], by (Select) 32] !times*(s(X), s(Y)) >= Y because [11], by (Select) We can thus remove the following rules: 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)) !times(s(X), s(Y)) >? s(!plus(!plus(!times(X, Y), X), Y)) 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) We choose Lex = {a} and Mul = {!plus, !times, s}, and the following precedence: !times > a > s > !plus 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)) !times(s(X), s(Y)) > s(!plus(!plus(!times(X, Y), X), Y)) 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], [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 [14], by (Select) 20] a*(X, Y, s(Z), s(U)) >= U because [21], by (Select) 21] s(U) >= U because [17], by (Star) 22] !times(s(X), s(Y)) > s(!plus(!plus(!times(X, Y), X), Y)) because [23], by definition 23] !times*(s(X), s(Y)) >= s(!plus(!plus(!times(X, Y), X), Y)) because !times > s and [24], by (Copy) 24] !times*(s(X), s(Y)) >= !plus(!plus(!times(X, Y), X), Y) because !times > !plus, [25] and [30], by (Copy) 25] !times*(s(X), s(Y)) >= !plus(!times(X, Y), X) because !times > !plus, [26] and [29], by (Copy) 26] !times*(s(X), s(Y)) >= !times(X, Y) because !times in Mul, [27] and [3], by (Stat) 27] s(X) >= X because [28], by (Star) 28] s*(X) >= X because [9], by (Select) 29] !times*(s(X), s(Y)) >= X because [27], by (Select) 30] !times*(s(X), s(Y)) >= Y because [11], by (Select) We can thus remove the following rules: !times(s(X), s(Y)) => s(!plus(!plus(!times(X, Y), 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]): a(X, Y, s(Z), s(U)) >? a(X, Y, Z, a(X, Y, s(Z), U)) 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_4, x_2, x_1) We choose Lex = {a} and Mul = {s}, and the following precedence: s > a 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)) 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], [15], [6], [8], [18] and [19], by (Stat) 13] s(Z) >= s(Z) because s in Mul and [14], by (Fun) 14] Z >= Z by (Meta) 15] s(U) > U because [16], by definition 16] s*(U) >= U because [17], by (Select) 17] U >= U by (Meta) 18] a*(X, Y, s(Z), s(U)) >= s(Z) because [13], by (Select) 19] a*(X, Y, s(Z), s(U)) >= U because [20], by (Select) 20] s(U) >= U because [16], 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)) 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.