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