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