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