/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 0 : [] --> o 1 : [] --> o fac : [o] --> o floop : [o * o] --> o s : [o] --> o fac(0) => 1 fac(s(X)) => !times(s(X), fac(X)) floop(0, X) => X floop(s(X), Y) => floop(X, !times(s(X), Y)) !times(X, 0) => 0 !times(X, s(Y)) => !plus(!times(X, Y), X) !plus(X, 0) => X !plus(X, s(Y)) => s(!plus(X, Y)) 1 => s(0) fac(0) => 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]): fac(0) >? 1 fac(s(X)) >? !times(s(X), fac(X)) floop(0, X) >? X floop(s(X), Y) >? floop(X, !times(s(X), Y)) !times(X, 0) >? 0 !times(X, s(Y)) >? !plus(!times(X, Y), X) !plus(X, 0) >? X !plus(X, s(Y)) >? s(!plus(X, Y)) 1 >? s(0) fac(0) >? s(0) about to try horpo We use a recursive path ordering as defined in [Kop12, Chapter 5]. Argument functions: [[0]] = _|_ We choose Lex = {floop} and Mul = {!plus, !times, 1, fac, s}, and the following precedence: fac > 1 > floop > !times > !plus > s Taking the argument function into account, and fixing the greater / greater equal choices, the constraints can be denoted as follows: fac(_|_) >= 1 fac(s(X)) >= !times(s(X), fac(X)) floop(_|_, X) >= X floop(s(X), Y) >= floop(X, !times(s(X), Y)) !times(X, _|_) >= _|_ !times(X, s(Y)) > !plus(!times(X, Y), X) !plus(X, _|_) >= X !plus(X, s(Y)) >= s(!plus(X, Y)) 1 >= s(_|_) fac(_|_) >= s(_|_) With these choices, we have: 1] fac(_|_) >= 1 because [2], by (Star) 2] fac*(_|_) >= 1 because fac > 1, by (Copy) 3] fac(s(X)) >= !times(s(X), fac(X)) because [4], by (Star) 4] fac*(s(X)) >= !times(s(X), fac(X)) because fac > !times, [5] and [8], by (Copy) 5] fac*(s(X)) >= s(X) because [6], by (Select) 6] s(X) >= s(X) because s in Mul and [7], by (Fun) 7] X >= X by (Meta) 8] fac*(s(X)) >= fac(X) because fac in Mul and [9], by (Stat) 9] s(X) > X because [10], by definition 10] s*(X) >= X because [7], by (Select) 11] floop(_|_, X) >= X because [12], by (Star) 12] floop*(_|_, X) >= X because [13], by (Select) 13] X >= X by (Meta) 14] floop(s(X), Y) >= floop(X, !times(s(X), Y)) because [15], by (Star) 15] floop*(s(X), Y) >= floop(X, !times(s(X), Y)) because [9], [16] and [18], by (Stat) 16] floop*(s(X), Y) >= X because [17], by (Select) 17] s(X) >= X because [10], by (Star) 18] floop*(s(X), Y) >= !times(s(X), Y) because floop > !times, [19] and [20], by (Copy) 19] floop*(s(X), Y) >= s(X) because floop > s and [16], by (Copy) 20] floop*(s(X), Y) >= Y because [13], by (Select) 21] !times(X, _|_) >= _|_ by (Bot) 22] !times(X, s(Y)) > !plus(!times(X, Y), X) because [23], by definition 23] !times*(X, s(Y)) >= !plus(!times(X, Y), X) because !times > !plus, [24] and [27], by (Copy) 24] !times*(X, s(Y)) >= !times(X, Y) because !times in Mul, [7] and [25], by (Stat) 25] s(Y) > Y because [26], by definition 26] s*(Y) >= Y because [13], by (Select) 27] !times*(X, s(Y)) >= X because [7], by (Select) 28] !plus(X, _|_) >= X because [29], by (Star) 29] !plus*(X, _|_) >= X because [7], by (Select) 30] !plus(X, s(Y)) >= s(!plus(X, Y)) because [31], by (Star) 31] !plus*(X, s(Y)) >= s(!plus(X, Y)) because !plus > s and [32], by (Copy) 32] !plus*(X, s(Y)) >= !plus(X, Y) because !plus in Mul, [7] and [25], by (Stat) 33] 1 >= s(_|_) because [34], by (Star) 34] 1* >= s(_|_) because 1 > s and [35], by (Copy) 35] 1* >= _|_ by (Bot) 36] fac(_|_) >= s(_|_) because [37], by (Star) 37] fac*(_|_) >= s(_|_) because fac > s and [38], by (Copy) 38] fac*(_|_) >= _|_ by (Bot) We can thus remove the following rules: !times(X, s(Y)) => !plus(!times(X, Y), 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]): fac(0) >? 1 fac(s(X)) >? !times(s(X), fac(X)) floop(0, X) >? X floop(s(X), Y) >? floop(X, !times(s(X), Y)) !times(X, 0) >? 0 !plus(X, 0) >? X !plus(X, s(Y)) >? s(!plus(X, Y)) 1 >? s(0) fac(0) >? s(0) about to try horpo We use a recursive path ordering as defined in [Kop12, Chapter 5]. We choose Lex = {fac, floop} and Mul = {!plus, !times, 0, 1, s}, and the following precedence: fac > 1 > floop > !times > 0 > !plus > s With these choices, we have: 1] fac(0) > 1 because [2], by definition 2] fac*(0) >= 1 because fac > 1, by (Copy) 3] fac(s(X)) >= !times(s(X), fac(X)) because [4], by (Star) 4] fac*(s(X)) >= !times(s(X), fac(X)) because fac > !times, [5] and [10], by (Copy) 5] fac*(s(X)) >= s(X) because fac > s and [6], by (Copy) 6] fac*(s(X)) >= X because [7], by (Select) 7] s(X) >= X because [8], by (Star) 8] s*(X) >= X because [9], by (Select) 9] X >= X by (Meta) 10] fac*(s(X)) >= fac(X) because [11] and [6], by (Stat) 11] s(X) > X because [12], by definition 12] s*(X) >= X because [9], by (Select) 13] floop(0, X) >= X because [14], by (Star) 14] floop*(0, X) >= X because [15], by (Select) 15] X >= X by (Meta) 16] floop(s(X), Y) >= floop(X, !times(s(X), Y)) because [17], by (Star) 17] floop*(s(X), Y) >= floop(X, !times(s(X), Y)) because [11], [18] and [19], by (Stat) 18] floop*(s(X), Y) >= X because [7], by (Select) 19] floop*(s(X), Y) >= !times(s(X), Y) because floop > !times, [20] and [21], by (Copy) 20] floop*(s(X), Y) >= s(X) because floop > s and [18], by (Copy) 21] floop*(s(X), Y) >= Y because [15], by (Select) 22] !times(X, 0) >= 0 because [23], by (Star) 23] !times*(X, 0) >= 0 because !times > 0, by (Copy) 24] !plus(X, 0) >= X because [25], by (Star) 25] !plus*(X, 0) >= X because [9], by (Select) 26] !plus(X, s(Y)) >= s(!plus(X, Y)) because [27], by (Star) 27] !plus*(X, s(Y)) >= s(!plus(X, Y)) because !plus > s and [28], by (Copy) 28] !plus*(X, s(Y)) >= !plus(X, Y) because !plus in Mul, [29] and [30], by (Stat) 29] X >= X by (Meta) 30] s(Y) > Y because [31], by definition 31] s*(Y) >= Y because [15], by (Select) 32] 1 > s(0) because [33], by definition 33] 1* >= s(0) because 1 > s and [34], by (Copy) 34] 1* >= 0 because 1 > 0, by (Copy) 35] fac(0) >= s(0) because [36], by (Star) 36] fac*(0) >= s(0) because fac > s and [37], by (Copy) 37] fac*(0) >= 0 because [38], by (Select) 38] 0 >= 0 by (Fun) We can thus remove the following rules: fac(0) => 1 1 => 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]): fac(s(X)) >? !times(s(X), fac(X)) floop(0, X) >? X floop(s(X), Y) >? floop(X, !times(s(X), Y)) !times(X, 0) >? 0 !plus(X, 0) >? X !plus(X, s(Y)) >? s(!plus(X, Y)) fac(0) >? s(0) about to try horpo We use a recursive path ordering as defined in [Kop12, Chapter 5]. Argument functions: [[0]] = _|_ We choose Lex = {floop} and Mul = {!plus, !times, fac, s}, and the following precedence: !plus > fac = s > floop > !times Taking the argument function into account, and fixing the greater / greater equal choices, the constraints can be denoted as follows: fac(s(X)) > !times(s(X), fac(X)) floop(_|_, X) > X floop(s(X), Y) >= floop(X, !times(s(X), Y)) !times(X, _|_) >= _|_ !plus(X, _|_) >= X !plus(X, s(Y)) >= s(!plus(X, Y)) fac(_|_) >= s(_|_) With these choices, we have: 1] fac(s(X)) > !times(s(X), fac(X)) because [2], by definition 2] fac*(s(X)) >= !times(s(X), fac(X)) because fac > !times, [3] and [6], by (Copy) 3] fac*(s(X)) >= s(X) because [4], by (Select) 4] s(X) >= s(X) because s in Mul and [5], by (Fun) 5] X >= X by (Meta) 6] fac*(s(X)) >= fac(X) because [7], by (Select) 7] s(X) >= fac(X) because s = fac, s in Mul and [5], by (Fun) 8] floop(_|_, X) > X because [9], by definition 9] floop*(_|_, X) >= X because [10], by (Select) 10] X >= X by (Meta) 11] floop(s(X), Y) >= floop(X, !times(s(X), Y)) because [12], by (Star) 12] floop*(s(X), Y) >= floop(X, !times(s(X), Y)) because [13], [15] and [17], by (Stat) 13] s(X) > X because [14], by definition 14] s*(X) >= X because [5], by (Select) 15] floop*(s(X), Y) >= X because [16], by (Select) 16] s(X) >= X because [14], by (Star) 17] floop*(s(X), Y) >= !times(s(X), Y) because floop > !times, [18] and [19], by (Copy) 18] floop*(s(X), Y) >= s(X) because [4], by (Select) 19] floop*(s(X), Y) >= Y because [10], by (Select) 20] !times(X, _|_) >= _|_ by (Bot) 21] !plus(X, _|_) >= X because [22], by (Star) 22] !plus*(X, _|_) >= X because [5], by (Select) 23] !plus(X, s(Y)) >= s(!plus(X, Y)) because [24], by (Star) 24] !plus*(X, s(Y)) >= s(!plus(X, Y)) because !plus > s and [25], by (Copy) 25] !plus*(X, s(Y)) >= !plus(X, Y) because !plus in Mul, [5] and [26], by (Stat) 26] s(Y) > Y because [27], by definition 27] s*(Y) >= Y because [10], by (Select) 28] fac(_|_) >= s(_|_) because fac = s, fac in Mul and [29], by (Fun) 29] _|_ >= _|_ by (Bot) We can thus remove the following rules: fac(s(X)) => !times(s(X), fac(X)) floop(0, 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]): floop(s(X), Y) >? floop(X, !times(s(X), Y)) !times(X, 0) >? 0 !plus(X, 0) >? X !plus(X, s(Y)) >? s(!plus(X, Y)) fac(0) >? s(0) about to try horpo We use a recursive path ordering as defined in [Kop12, Chapter 5]. Argument functions: [[0]] = _|_ We choose Lex = {floop} and Mul = {!plus, !times, fac, s}, and the following precedence: !plus > fac > floop > !times > s Taking the argument function into account, and fixing the greater / greater equal choices, the constraints can be denoted as follows: floop(s(X), Y) >= floop(X, !times(s(X), Y)) !times(X, _|_) > _|_ !plus(X, _|_) >= X !plus(X, s(Y)) >= s(!plus(X, Y)) fac(_|_) >= s(_|_) With these choices, we have: 1] floop(s(X), Y) >= floop(X, !times(s(X), Y)) because [2], by (Star) 2] floop*(s(X), Y) >= floop(X, !times(s(X), Y)) because [3], [6] and [8], by (Stat) 3] s(X) > X because [4], by definition 4] s*(X) >= X because [5], by (Select) 5] X >= X by (Meta) 6] floop*(s(X), Y) >= X because [7], by (Select) 7] s(X) >= X because [4], by (Star) 8] floop*(s(X), Y) >= !times(s(X), Y) because floop > !times, [9] and [12], by (Copy) 9] floop*(s(X), Y) >= s(X) because [10], by (Select) 10] s(X) >= s(X) because s in Mul and [11], by (Fun) 11] X >= X by (Meta) 12] floop*(s(X), Y) >= Y because [13], by (Select) 13] Y >= Y by (Meta) 14] !times(X, _|_) > _|_ because [15], by definition 15] !times*(X, _|_) >= _|_ by (Bot) 16] !plus(X, _|_) >= X because [17], by (Star) 17] !plus*(X, _|_) >= X because [11], by (Select) 18] !plus(X, s(Y)) >= s(!plus(X, Y)) because [19], by (Star) 19] !plus*(X, s(Y)) >= s(!plus(X, Y)) because !plus > s and [20], by (Copy) 20] !plus*(X, s(Y)) >= !plus(X, Y) because !plus in Mul, [11] and [21], by (Stat) 21] s(Y) > Y because [22], by definition 22] s*(Y) >= Y because [13], by (Select) 23] fac(_|_) >= s(_|_) because [24], by (Star) 24] fac*(_|_) >= s(_|_) because fac > s and [25], by (Copy) 25] fac*(_|_) >= _|_ by (Bot) We can thus remove the following rules: !times(X, 0) => 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]): floop(s(X), Y) >? floop(X, !times(s(X), Y)) !plus(X, 0) >? X !plus(X, s(Y)) >? s(!plus(X, Y)) fac(0) >? s(0) about to try horpo We use a recursive path ordering as defined in [Kop12, Chapter 5]. Argument functions: [[!plus(x_1, x_2)]] = !plus(x_2, x_1) We choose Lex = {!plus, floop} and Mul = {!times, 0, fac, s}, and the following precedence: fac > 0 > !plus > floop > !times > s Taking the argument function into account, and fixing the greater / greater equal choices, the constraints can be denoted as follows: floop(s(X), Y) > floop(X, !times(s(X), Y)) !plus(X, 0) >= X !plus(X, s(Y)) >= s(!plus(X, Y)) fac(0) >= s(0) With these choices, we have: 1] floop(s(X), Y) > floop(X, !times(s(X), Y)) because [2], by definition 2] floop*(s(X), Y) >= floop(X, !times(s(X), Y)) because [3], [6] and [8], by (Stat) 3] s(X) > X because [4], by definition 4] s*(X) >= X because [5], by (Select) 5] X >= X by (Meta) 6] floop*(s(X), Y) >= X because [7], by (Select) 7] s(X) >= X because [4], by (Star) 8] floop*(s(X), Y) >= !times(s(X), Y) because floop > !times, [9] and [10], by (Copy) 9] floop*(s(X), Y) >= s(X) because floop > s and [6], by (Copy) 10] floop*(s(X), Y) >= Y because [11], by (Select) 11] Y >= Y by (Meta) 12] !plus(X, 0) >= X because [13], by (Star) 13] !plus*(X, 0) >= X because [5], by (Select) 14] !plus(X, s(Y)) >= s(!plus(X, Y)) because [15], by (Star) 15] !plus*(X, s(Y)) >= s(!plus(X, Y)) because !plus > s and [16], by (Copy) 16] !plus*(X, s(Y)) >= !plus(X, Y) because [17], [19] and [20], by (Stat) 17] s(Y) > Y because [18], by definition 18] s*(Y) >= Y because [11], by (Select) 19] !plus*(X, s(Y)) >= X because [5], by (Select) 20] !plus*(X, s(Y)) >= Y because [21], by (Select) 21] s(Y) >= Y because [18], by (Star) 22] fac(0) >= s(0) because [23], by (Star) 23] fac*(0) >= s(0) because fac > s and [24], by (Copy) 24] fac*(0) >= 0 because fac > 0, by (Copy) We can thus remove the following rules: floop(s(X), Y) => floop(X, !times(s(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]): !plus(X, 0) >? X !plus(X, s(Y)) >? s(!plus(X, Y)) fac(0) >? s(0) We orient these requirements with a polynomial interpretation in the natural numbers. The following interpretation satisfies the requirements: !plus = \y0y1.3 + y0 + 3y1 0 = 3 fac = \y0.3 + 3y0 s = \y0.y0 Using this interpretation, the requirements translate to: [[!plus(_x0, 0)]] = 12 + x0 > x0 = [[_x0]] [[!plus(_x0, s(_x1))]] = 3 + x0 + 3x1 >= 3 + x0 + 3x1 = [[s(!plus(_x0, _x1))]] [[fac(0)]] = 12 > 3 = [[s(0)]] We can thus remove the following rules: !plus(X, 0) => X fac(0) => 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, s(Y)) >? s(!plus(X, Y)) We orient these requirements with a polynomial interpretation in the natural numbers. The following interpretation satisfies the requirements: !plus = \y0y1.y0 + 3y1 s = \y0.1 + y0 Using this interpretation, the requirements translate to: [[!plus(_x0, s(_x1))]] = 3 + x0 + 3x1 > 1 + x0 + 3x1 = [[s(!plus(_x0, _x1))]] We can thus remove the following rules: !plus(X, s(Y)) => s(!plus(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.