/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 0 : [] --> o double : [o] --> o s : [o] --> o sqr : [o] --> o sqr(0) => 0 sqr(s(X)) => !plus(sqr(X), s(double(X))) double(0) => 0 double(s(X)) => s(s(double(X))) !plus(X, 0) => X !plus(X, s(Y)) => s(!plus(X, Y)) sqr(s(X)) => s(!plus(sqr(X), double(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]): sqr(0) >? 0 sqr(s(X)) >? !plus(sqr(X), s(double(X))) double(0) >? 0 double(s(X)) >? s(s(double(X))) !plus(X, 0) >? X !plus(X, s(Y)) >? s(!plus(X, Y)) sqr(s(X)) >? s(!plus(sqr(X), double(X))) 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, double, s, sqr}, and the following precedence: double = sqr > !plus > s Taking the argument function into account, and fixing the greater / greater equal choices, the constraints can be denoted as follows: sqr(_|_) >= _|_ sqr(s(X)) > !plus(sqr(X), s(double(X))) double(_|_) >= _|_ double(s(X)) > s(s(double(X))) !plus(X, _|_) > X !plus(X, s(Y)) >= s(!plus(X, Y)) sqr(s(X)) >= s(!plus(sqr(X), double(X))) With these choices, we have: 1] sqr(_|_) >= _|_ by (Bot) 2] sqr(s(X)) > !plus(sqr(X), s(double(X))) because [3], by definition 3] sqr*(s(X)) >= !plus(sqr(X), s(double(X))) because sqr > !plus, [4] and [8], by (Copy) 4] sqr*(s(X)) >= sqr(X) because sqr in Mul and [5], by (Stat) 5] s(X) > X because [6], by definition 6] s*(X) >= X because [7], by (Select) 7] X >= X by (Meta) 8] sqr*(s(X)) >= s(double(X)) because sqr > s and [9], by (Copy) 9] sqr*(s(X)) >= double(X) because sqr = double, sqr in Mul and [5], by (Stat) 10] double(_|_) >= _|_ by (Bot) 11] double(s(X)) > s(s(double(X))) because [12], by definition 12] double*(s(X)) >= s(s(double(X))) because double > s and [13], by (Copy) 13] double*(s(X)) >= s(double(X)) because double > s and [14], by (Copy) 14] double*(s(X)) >= double(X) because double in Mul and [5], by (Stat) 15] !plus(X, _|_) > X because [16], by definition 16] !plus*(X, _|_) >= X because [7], by (Select) 17] !plus(X, s(Y)) >= s(!plus(X, Y)) because [18], by (Star) 18] !plus*(X, s(Y)) >= s(!plus(X, Y)) because !plus > s and [19], by (Copy) 19] !plus*(X, s(Y)) >= !plus(X, Y) because !plus in Mul, [20] and [21], by (Stat) 20] X >= X by (Meta) 21] s(Y) > Y because [22], by definition 22] s*(Y) >= Y because [23], by (Select) 23] Y >= Y by (Meta) 24] sqr(s(X)) >= s(!plus(sqr(X), double(X))) because [25], by (Star) 25] sqr*(s(X)) >= s(!plus(sqr(X), double(X))) because sqr > s and [26], by (Copy) 26] sqr*(s(X)) >= !plus(sqr(X), double(X)) because sqr > !plus, [4] and [9], by (Copy) We can thus remove the following rules: sqr(s(X)) => !plus(sqr(X), s(double(X))) double(s(X)) => s(s(double(X))) !plus(X, 0) => 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]): sqr(0) >? 0 double(0) >? 0 !plus(X, s(Y)) >? s(!plus(X, Y)) sqr(s(X)) >? s(!plus(sqr(X), double(X))) about to try horpo We use a recursive path ordering as defined in [Kop12, Chapter 5]. Argument functions: [[0]] = _|_ [[double(x_1)]] = x_1 We choose Lex = {} and Mul = {!plus, s, sqr}, and the following precedence: sqr > !plus > s Taking the argument function into account, and fixing the greater / greater equal choices, the constraints can be denoted as follows: sqr(_|_) > _|_ _|_ >= _|_ !plus(X, s(Y)) >= s(!plus(X, Y)) sqr(s(X)) >= s(!plus(sqr(X), X)) With these choices, we have: 1] sqr(_|_) > _|_ because [2], by definition 2] sqr*(_|_) >= _|_ by (Bot) 3] _|_ >= _|_ by (Bot) 4] !plus(X, s(Y)) >= s(!plus(X, Y)) because [5], by (Star) 5] !plus*(X, s(Y)) >= s(!plus(X, Y)) because !plus > s and [6], by (Copy) 6] !plus*(X, s(Y)) >= !plus(X, Y) because !plus in Mul, [7] and [8], by (Stat) 7] X >= X by (Meta) 8] s(Y) > Y because [9], by definition 9] s*(Y) >= Y because [10], by (Select) 10] Y >= Y by (Meta) 11] sqr(s(X)) >= s(!plus(sqr(X), X)) because [12], by (Star) 12] sqr*(s(X)) >= s(!plus(sqr(X), X)) because sqr > s and [13], by (Copy) 13] sqr*(s(X)) >= !plus(sqr(X), X) because sqr > !plus, [14] and [17], by (Copy) 14] sqr*(s(X)) >= sqr(X) because sqr in Mul and [15], by (Stat) 15] s(X) > X because [16], by definition 16] s*(X) >= X because [7], by (Select) 17] sqr*(s(X)) >= X because [18], by (Select) 18] s(X) >= X because [16], by (Star) We can thus remove the following rules: sqr(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]): double(0) >? 0 !plus(X, s(Y)) >? s(!plus(X, Y)) sqr(s(X)) >? s(!plus(sqr(X), double(X))) about to try horpo We use a recursive path ordering as defined in [Kop12, Chapter 5]. We choose Lex = {} and Mul = {!plus, 0, double, s, sqr}, and the following precedence: sqr > !plus > double = s > 0 With these choices, we have: 1] double(0) > 0 because [2], by definition 2] double*(0) >= 0 because double > 0, by (Copy) 3] !plus(X, s(Y)) >= s(!plus(X, Y)) because [4], by (Star) 4] !plus*(X, s(Y)) >= s(!plus(X, Y)) because !plus > s and [5], by (Copy) 5] !plus*(X, s(Y)) >= !plus(X, Y) because !plus in Mul, [6] and [7], by (Stat) 6] X >= X by (Meta) 7] s(Y) > Y because [8], by definition 8] s*(Y) >= Y because [9], by (Select) 9] Y >= Y by (Meta) 10] sqr(s(X)) >= s(!plus(sqr(X), double(X))) because [11], by (Star) 11] sqr*(s(X)) >= s(!plus(sqr(X), double(X))) because sqr > s and [12], by (Copy) 12] sqr*(s(X)) >= !plus(sqr(X), double(X)) because sqr > !plus, [13] and [16], by (Copy) 13] sqr*(s(X)) >= sqr(X) because sqr in Mul and [14], by (Stat) 14] s(X) > X because [15], by definition 15] s*(X) >= X because [6], by (Select) 16] sqr*(s(X)) >= double(X) because [17], by (Select) 17] s(X) >= double(X) because s = double, s in Mul and [6], by (Fun) We can thus remove the following rules: double(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]): !plus(X, s(Y)) >? s(!plus(X, Y)) sqr(s(X)) >? s(!plus(sqr(X), double(X))) about to try horpo We use a recursive path ordering as defined in [Kop12, Chapter 5]. We choose Lex = {} and Mul = {!plus, double, s, sqr}, and the following precedence: double = sqr > !plus > s With these choices, we have: 1] !plus(X, s(Y)) > s(!plus(X, Y)) because [2], by definition 2] !plus*(X, s(Y)) >= s(!plus(X, Y)) because !plus > s and [3], by (Copy) 3] !plus*(X, s(Y)) >= !plus(X, Y) because !plus in Mul, [4] and [5], by (Stat) 4] X >= X by (Meta) 5] s(Y) > Y because [6], by definition 6] s*(Y) >= Y because [7], by (Select) 7] Y >= Y by (Meta) 8] sqr(s(X)) > s(!plus(sqr(X), double(X))) because [9], by definition 9] sqr*(s(X)) >= s(!plus(sqr(X), double(X))) because sqr > s and [10], by (Copy) 10] sqr*(s(X)) >= !plus(sqr(X), double(X)) because sqr > !plus, [11] and [14], by (Copy) 11] sqr*(s(X)) >= sqr(X) because sqr in Mul and [12], by (Stat) 12] s(X) > X because [13], by definition 13] s*(X) >= X because [4], by (Select) 14] sqr*(s(X)) >= double(X) because sqr = double, sqr in Mul and [12], by (Stat) We can thus remove the following rules: !plus(X, s(Y)) => s(!plus(X, Y)) sqr(s(X)) => s(!plus(sqr(X), double(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.