/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 !times : [o * o] --> o 0 : [] --> o cons : [o * o] --> o nil : [] --> o prod : [o] --> o s : [o] --> o sum : [o] --> o !plus(X, 0) => X !plus(0, X) => X !plus(s(X), s(Y)) => s(s(!plus(X, Y))) !plus(!plus(X, Y), Z) => !plus(X, !plus(Y, Z)) !times(X, 0) => 0 !times(0, X) => 0 !times(s(X), s(Y)) => s(!plus(!times(X, Y), !plus(X, Y))) !times(!times(X, Y), Z) => !times(X, !times(Y, Z)) sum(nil) => 0 sum(cons(X, Y)) => !plus(X, sum(Y)) prod(nil) => s(0) prod(cons(X, Y)) => !times(X, prod(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]): !plus(X, 0) >? X !plus(0, X) >? X !plus(s(X), s(Y)) >? s(s(!plus(X, Y))) !plus(!plus(X, Y), Z) >? !plus(X, !plus(Y, Z)) !times(X, 0) >? 0 !times(0, X) >? 0 !times(s(X), s(Y)) >? s(!plus(!times(X, Y), !plus(X, Y))) !times(!times(X, Y), Z) >? !times(X, !times(Y, Z)) sum(nil) >? 0 sum(cons(X, Y)) >? !plus(X, sum(Y)) prod(nil) >? s(0) prod(cons(X, Y)) >? !times(X, prod(Y)) about to try horpo We use a recursive path ordering as defined in [Kop12, Chapter 5]. Argument functions: [[0]] = _|_ We choose Lex = {!plus, !times} and Mul = {cons, nil, prod, s, sum}, and the following precedence: cons > nil > prod > !times > !plus > s > sum Taking the argument function into account, and fixing the greater / greater equal choices, the constraints can be denoted as follows: !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)) !times(X, _|_) >= _|_ !times(_|_, X) >= _|_ !times(s(X), s(Y)) >= s(!plus(!times(X, Y), !plus(X, Y))) !times(!times(X, Y), Z) > !times(X, !times(Y, Z)) sum(nil) >= _|_ sum(cons(X, Y)) > !plus(X, sum(Y)) prod(nil) > s(_|_) prod(cons(X, Y)) >= !times(X, prod(Y)) With these choices, we have: 1] !plus(X, _|_) >= X because [2], by (Star) 2] !plus*(X, _|_) >= X because [3], by (Select) 3] X >= X by (Meta) 4] !plus(_|_, X) > X because [5], by definition 5] !plus*(_|_, X) >= X because [3], by (Select) 6] !plus(s(X), s(Y)) > s(s(!plus(X, Y))) because [7], by definition 7] !plus*(s(X), s(Y)) >= s(s(!plus(X, Y))) because !plus > s and [8], by (Copy) 8] !plus*(s(X), s(Y)) >= s(!plus(X, Y)) because !plus > s and [9], by (Copy) 9] !plus*(s(X), s(Y)) >= !plus(X, Y) because [10], [12] and [14], by (Stat) 10] s(X) > X because [11], by definition 11] s*(X) >= X because [3], by (Select) 12] !plus*(s(X), s(Y)) >= X because [13], by (Select) 13] s(X) >= X because [11], by (Star) 14] !plus*(s(X), s(Y)) >= Y because [15], by (Select) 15] s(Y) >= Y because [16], by (Star) 16] s*(Y) >= Y because [17], by (Select) 17] Y >= Y by (Meta) 18] !plus(!plus(X, Y), Z) >= !plus(X, !plus(Y, Z)) because [19], by (Star) 19] !plus*(!plus(X, Y), Z) >= !plus(X, !plus(Y, Z)) because [20], [22] and [24], by (Stat) 20] !plus(X, Y) > X because [21], by definition 21] !plus*(X, Y) >= X because [3], by (Select) 22] !plus*(!plus(X, Y), Z) >= X because [23], by (Select) 23] !plus(X, Y) >= X because [21], by (Star) 24] !plus*(!plus(X, Y), Z) >= !plus(Y, Z) because [25], [27] and [29], by (Stat) 25] !plus(X, Y) > Y because [26], by definition 26] !plus*(X, Y) >= Y because [17], by (Select) 27] !plus*(!plus(X, Y), Z) >= Y because [28], by (Select) 28] !plus(X, Y) >= Y because [26], by (Star) 29] !plus*(!plus(X, Y), Z) >= Z because [30], by (Select) 30] Z >= Z by (Meta) 31] !times(X, _|_) >= _|_ by (Bot) 32] !times(_|_, X) >= _|_ by (Bot) 33] !times(s(X), s(Y)) >= s(!plus(!times(X, Y), !plus(X, Y))) because [34], by (Star) 34] !times*(s(X), s(Y)) >= s(!plus(!times(X, Y), !plus(X, Y))) because !times > s and [35], by (Copy) 35] !times*(s(X), s(Y)) >= !plus(!times(X, Y), !plus(X, Y)) because !times > !plus, [36] and [39], by (Copy) 36] !times*(s(X), s(Y)) >= !times(X, Y) because [10], [37] and [38], by (Stat) 37] !times*(s(X), s(Y)) >= X because [13], by (Select) 38] !times*(s(X), s(Y)) >= Y because [15], by (Select) 39] !times*(s(X), s(Y)) >= !plus(X, Y) because !times > !plus, [37] and [38], by (Copy) 40] !times(!times(X, Y), Z) > !times(X, !times(Y, Z)) because [41], by definition 41] !times*(!times(X, Y), Z) >= !times(X, !times(Y, Z)) because [42], [44] and [46], by (Stat) 42] !times(X, Y) > X because [43], by definition 43] !times*(X, Y) >= X because [3], by (Select) 44] !times*(!times(X, Y), Z) >= X because [45], by (Select) 45] !times(X, Y) >= X because [43], by (Star) 46] !times*(!times(X, Y), Z) >= !times(Y, Z) because [47], [49] and [51], by (Stat) 47] !times(X, Y) > Y because [48], by definition 48] !times*(X, Y) >= Y because [17], by (Select) 49] !times*(!times(X, Y), Z) >= Y because [50], by (Select) 50] !times(X, Y) >= Y because [48], by (Star) 51] !times*(!times(X, Y), Z) >= Z because [30], by (Select) 52] sum(nil) >= _|_ by (Bot) 53] sum(cons(X, Y)) > !plus(X, sum(Y)) because [54], by definition 54] sum*(cons(X, Y)) >= !plus(X, sum(Y)) because [55], by (Select) 55] cons(X, Y) >= !plus(X, sum(Y)) because [56], by (Star) 56] cons*(X, Y) >= !plus(X, sum(Y)) because cons > !plus, [57] and [58], by (Copy) 57] cons*(X, Y) >= X because [3], by (Select) 58] cons*(X, Y) >= sum(Y) because cons > sum and [59], by (Copy) 59] cons*(X, Y) >= Y because [60], by (Select) 60] Y >= Y by (Meta) 61] prod(nil) > s(_|_) because [62], by definition 62] prod*(nil) >= s(_|_) because prod > s and [63], by (Copy) 63] prod*(nil) >= _|_ by (Bot) 64] prod(cons(X, Y)) >= !times(X, prod(Y)) because [65], by (Star) 65] prod*(cons(X, Y)) >= !times(X, prod(Y)) because prod > !times, [66] and [68], by (Copy) 66] prod*(cons(X, Y)) >= X because [67], by (Select) 67] cons(X, Y) >= X because [57], by (Star) 68] prod*(cons(X, Y)) >= prod(Y) because [69], by (Select) 69] cons(X, Y) >= prod(Y) because [70], by (Star) 70] cons*(X, Y) >= prod(Y) because cons > prod and [59], by (Copy) We can thus remove the following rules: !plus(0, X) => X !plus(s(X), s(Y)) => s(s(!plus(X, Y))) !times(!times(X, Y), Z) => !times(X, !times(Y, Z)) sum(cons(X, Y)) => !plus(X, sum(Y)) prod(nil) => s(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]): !plus(X, 0) >? X !plus(!plus(X, Y), Z) >? !plus(X, !plus(Y, Z)) !times(X, 0) >? 0 !times(0, X) >? 0 !times(s(X), s(Y)) >? s(!plus(!times(X, Y), !plus(X, Y))) sum(nil) >? 0 prod(cons(X, Y)) >? !times(X, prod(Y)) about to try horpo We use a recursive path ordering as defined in [Kop12, Chapter 5]. Argument functions: [[0]] = _|_ [[sum(x_1)]] = x_1 We choose Lex = {!plus} and Mul = {!times, cons, nil, prod, s}, and the following precedence: nil > cons = prod > !times > !plus > s Taking the argument function into account, and fixing the greater / greater equal choices, the constraints can be denoted as follows: !plus(X, _|_) >= X !plus(!plus(X, Y), Z) >= !plus(X, !plus(Y, Z)) !times(X, _|_) >= _|_ !times(_|_, X) >= _|_ !times(s(X), s(Y)) > s(!plus(!times(X, Y), !plus(X, Y))) nil >= _|_ prod(cons(X, Y)) > !times(X, prod(Y)) With these choices, we have: 1] !plus(X, _|_) >= X because [2], by (Star) 2] !plus*(X, _|_) >= X because [3], by (Select) 3] X >= X by (Meta) 4] !plus(!plus(X, Y), Z) >= !plus(X, !plus(Y, Z)) because [5], by (Star) 5] !plus*(!plus(X, Y), Z) >= !plus(X, !plus(Y, Z)) because [6], [8] and [10], by (Stat) 6] !plus(X, Y) > X because [7], by definition 7] !plus*(X, Y) >= X because [3], by (Select) 8] !plus*(!plus(X, Y), Z) >= X because [9], by (Select) 9] !plus(X, Y) >= X because [7], by (Star) 10] !plus*(!plus(X, Y), Z) >= !plus(Y, Z) because [11], [14] and [16], by (Stat) 11] !plus(X, Y) > Y because [12], by definition 12] !plus*(X, Y) >= Y because [13], by (Select) 13] Y >= Y by (Meta) 14] !plus*(!plus(X, Y), Z) >= Y because [15], by (Select) 15] !plus(X, Y) >= Y because [12], by (Star) 16] !plus*(!plus(X, Y), Z) >= Z because [17], by (Select) 17] Z >= Z by (Meta) 18] !times(X, _|_) >= _|_ by (Bot) 19] !times(_|_, X) >= _|_ by (Bot) 20] !times(s(X), s(Y)) > s(!plus(!times(X, Y), !plus(X, Y))) because [21], by definition 21] !times*(s(X), s(Y)) >= s(!plus(!times(X, Y), !plus(X, Y))) because !times > s and [22], by (Copy) 22] !times*(s(X), s(Y)) >= !plus(!times(X, Y), !plus(X, Y)) because !times > !plus, [23] and [28], by (Copy) 23] !times*(s(X), s(Y)) >= !times(X, Y) because !times in Mul, [24] and [26], by (Stat) 24] s(X) >= X because [25], by (Star) 25] s*(X) >= X because [3], by (Select) 26] s(Y) > Y because [27], by definition 27] s*(Y) >= Y because [13], by (Select) 28] !times*(s(X), s(Y)) >= !plus(X, Y) because !times > !plus, [29] and [30], by (Copy) 29] !times*(s(X), s(Y)) >= X because [24], by (Select) 30] !times*(s(X), s(Y)) >= Y because [31], by (Select) 31] s(Y) >= Y because [27], by (Star) 32] nil >= _|_ by (Bot) 33] prod(cons(X, Y)) > !times(X, prod(Y)) because [34], by definition 34] prod*(cons(X, Y)) >= !times(X, prod(Y)) because prod > !times, [35] and [38], by (Copy) 35] prod*(cons(X, Y)) >= X because [36], by (Select) 36] cons(X, Y) >= X because [37], by (Star) 37] cons*(X, Y) >= X because [3], by (Select) 38] prod*(cons(X, Y)) >= prod(Y) because [39], by (Select) 39] cons(X, Y) >= prod(Y) because [40], by (Star) 40] cons*(X, Y) >= prod(Y) because cons = prod, cons in Mul and [41], by (Stat) 41] Y >= Y by (Meta) We can thus remove the following rules: !times(s(X), s(Y)) => s(!plus(!times(X, Y), !plus(X, Y))) prod(cons(X, Y)) => !times(X, prod(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]): !plus(X, 0) >? X !plus(!plus(X, Y), Z) >? !plus(X, !plus(Y, Z)) !times(X, 0) >? 0 !times(0, X) >? 0 sum(nil) >? 0 We orient these requirements with a polynomial interpretation in the natural numbers. The following interpretation satisfies the requirements: !plus = \y0y1.3 + y1 + 3y0 !times = \y0y1.3 + 3y0 + 3y1 0 = 0 nil = 3 sum = \y0.3 + 3y0 Using this interpretation, the requirements translate to: [[!plus(_x0, 0)]] = 3 + 3x0 > x0 = [[_x0]] [[!plus(!plus(_x0, _x1), _x2)]] = 12 + x2 + 3x1 + 9x0 > 6 + x2 + 3x0 + 3x1 = [[!plus(_x0, !plus(_x1, _x2))]] [[!times(_x0, 0)]] = 3 + 3x0 > 0 = [[0]] [[!times(0, _x0)]] = 3 + 3x0 > 0 = [[0]] [[sum(nil)]] = 12 > 0 = [[0]] We can thus remove the following rules: !plus(X, 0) => X !plus(!plus(X, Y), Z) => !plus(X, !plus(Y, Z)) !times(X, 0) => 0 !times(0, X) => 0 sum(nil) => 0 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.