/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 g : [o] --> o np : [o] --> o pair : [o * o] --> o s : [o] --> o sp : [o] --> o fib(0) => 0 fib(s(0)) => s(0) fib(s(s(0))) => s(0) fib(s(s(X))) => sp(g(X)) g(0) => pair(s(0), 0) g(s(0)) => pair(s(0), s(0)) g(s(X)) => np(g(X)) sp(pair(X, Y)) => !plus(X, Y) np(pair(X, Y)) => pair(!plus(X, Y), 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(0))) >? s(0) fib(s(s(X))) >? sp(g(X)) g(0) >? pair(s(0), 0) g(s(0)) >? pair(s(0), s(0)) g(s(X)) >? np(g(X)) sp(pair(X, Y)) >? !plus(X, Y) np(pair(X, Y)) >? pair(!plus(X, Y), 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, g, np, pair, s, sp}, and the following precedence: fib > g > np > pair > sp > !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(_|_))) >= s(_|_) fib(s(s(X))) >= sp(g(X)) g(_|_) >= pair(s(_|_), _|_) g(s(_|_)) >= pair(s(_|_), s(_|_)) g(s(X)) >= np(g(X)) sp(pair(X, Y)) >= !plus(X, Y) np(pair(X, Y)) > pair(!plus(X, Y), X) !plus(X, _|_) >= X !plus(X, s(Y)) >= s(!plus(X, Y)) With these choices, we have: 1] fib(_|_) >= _|_ by (Bot) 2] fib(s(_|_)) >= s(_|_) because [3], by (Star) 3] fib*(s(_|_)) >= s(_|_) because fib > s and [4], by (Copy) 4] fib*(s(_|_)) >= _|_ by (Bot) 5] fib(s(s(_|_))) >= s(_|_) because [6], by (Star) 6] fib*(s(s(_|_))) >= s(_|_) because fib > s and [7], by (Copy) 7] fib*(s(s(_|_))) >= _|_ by (Bot) 8] fib(s(s(X))) >= sp(g(X)) because [9], by (Star) 9] fib*(s(s(X))) >= sp(g(X)) because fib > sp and [10], by (Copy) 10] fib*(s(s(X))) >= g(X) because fib > g and [11], by (Copy) 11] fib*(s(s(X))) >= X because [12], by (Select) 12] s(s(X)) >= X because [13], by (Star) 13] s*(s(X)) >= X because [14], by (Select) 14] s(X) >= X because [15], by (Star) 15] s*(X) >= X because [16], by (Select) 16] X >= X by (Meta) 17] g(_|_) >= pair(s(_|_), _|_) because [18], by (Star) 18] g*(_|_) >= pair(s(_|_), _|_) because g > pair, [19] and [20], by (Copy) 19] g*(_|_) >= s(_|_) because g > s and [20], by (Copy) 20] g*(_|_) >= _|_ by (Bot) 21] g(s(_|_)) >= pair(s(_|_), s(_|_)) because [22], by (Star) 22] g*(s(_|_)) >= pair(s(_|_), s(_|_)) because g > pair, [23] and [23], by (Copy) 23] g*(s(_|_)) >= s(_|_) because [24], by (Select) 24] s(_|_) >= s(_|_) because s in Mul and [25], by (Fun) 25] _|_ >= _|_ by (Bot) 26] g(s(X)) >= np(g(X)) because [27], by (Star) 27] g*(s(X)) >= np(g(X)) because g > np and [28], by (Copy) 28] g*(s(X)) >= g(X) because g in Mul and [29], by (Stat) 29] s(X) > X because [30], by definition 30] s*(X) >= X because [16], by (Select) 31] sp(pair(X, Y)) >= !plus(X, Y) because [32], by (Star) 32] sp*(pair(X, Y)) >= !plus(X, Y) because sp > !plus, [33] and [36], by (Copy) 33] sp*(pair(X, Y)) >= X because [34], by (Select) 34] pair(X, Y) >= X because [35], by (Star) 35] pair*(X, Y) >= X because [16], by (Select) 36] sp*(pair(X, Y)) >= Y because [37], by (Select) 37] pair(X, Y) >= Y because [38], by (Star) 38] pair*(X, Y) >= Y because [39], by (Select) 39] Y >= Y by (Meta) 40] np(pair(X, Y)) > pair(!plus(X, Y), X) because [41], by definition 41] np*(pair(X, Y)) >= pair(!plus(X, Y), X) because np > pair, [42] and [43], by (Copy) 42] np*(pair(X, Y)) >= !plus(X, Y) because np > !plus, [43] and [44], by (Copy) 43] np*(pair(X, Y)) >= X because [34], by (Select) 44] np*(pair(X, Y)) >= Y because [37], by (Select) 45] !plus(X, _|_) >= X because [46], by (Star) 46] !plus*(X, _|_) >= X because [16], by (Select) 47] !plus(X, s(Y)) >= s(!plus(X, Y)) because [48], by (Star) 48] !plus*(X, s(Y)) >= s(!plus(X, Y)) because !plus > s and [49], by (Copy) 49] !plus*(X, s(Y)) >= !plus(X, Y) because !plus in Mul, [50] and [51], by (Stat) 50] X >= X by (Meta) 51] s(Y) > Y because [52], by definition 52] s*(Y) >= Y because [39], by (Select) We can thus remove the following rules: np(pair(X, Y)) => pair(!plus(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]): fib(0) >? 0 fib(s(0)) >? s(0) fib(s(s(0))) >? s(0) fib(s(s(X))) >? sp(g(X)) g(0) >? pair(s(0), 0) g(s(0)) >? pair(s(0), s(0)) g(s(X)) >? np(g(X)) sp(pair(X, Y)) >? !plus(X, Y) !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.y1 + 2y0 0 = 0 fib = \y0.3 + 3y0 g = \y0.y0 np = \y0.y0 pair = \y0y1.y1 + 2y0 s = \y0.y0 sp = \y0.2 + y0 Using this interpretation, the requirements translate to: [[fib(0)]] = 3 > 0 = [[0]] [[fib(s(0))]] = 3 > 0 = [[s(0)]] [[fib(s(s(0)))]] = 3 > 0 = [[s(0)]] [[fib(s(s(_x0)))]] = 3 + 3x0 > 2 + x0 = [[sp(g(_x0))]] [[g(0)]] = 0 >= 0 = [[pair(s(0), 0)]] [[g(s(0))]] = 0 >= 0 = [[pair(s(0), s(0))]] [[g(s(_x0))]] = x0 >= x0 = [[np(g(_x0))]] [[sp(pair(_x0, _x1))]] = 2 + x1 + 2x0 > x1 + 2x0 = [[!plus(_x0, _x1)]] [[!plus(_x0, 0)]] = 2x0 >= x0 = [[_x0]] [[!plus(_x0, s(_x1))]] = x1 + 2x0 >= x1 + 2x0 = [[s(!plus(_x0, _x1))]] We can thus remove the following rules: fib(0) => 0 fib(s(0)) => s(0) fib(s(s(0))) => s(0) fib(s(s(X))) => sp(g(X)) sp(pair(X, Y)) => !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]): g(0) >? pair(s(0), 0) g(s(0)) >? pair(s(0), s(0)) g(s(X)) >? np(g(X)) !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.y0 + 3y1 0 = 0 g = \y0.1 + y0 np = \y0.y0 pair = \y0y1.y0 + y1 s = \y0.1 + y0 Using this interpretation, the requirements translate to: [[g(0)]] = 1 >= 1 = [[pair(s(0), 0)]] [[g(s(0))]] = 2 >= 2 = [[pair(s(0), s(0))]] [[g(s(_x0))]] = 2 + x0 > 1 + x0 = [[np(g(_x0))]] [[!plus(_x0, 0)]] = x0 >= x0 = [[_x0]] [[!plus(_x0, s(_x1))]] = 3 + x0 + 3x1 > 1 + x0 + 3x1 = [[s(!plus(_x0, _x1))]] We can thus remove the following rules: g(s(X)) => np(g(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]): g(0) >? pair(s(0), 0) g(s(0)) >? pair(s(0), s(0)) !plus(X, 0) >? X We orient these requirements with a polynomial interpretation in the natural numbers. The following interpretation satisfies the requirements: !plus = \y0y1.3 + y0 + y1 0 = 0 g = \y0.3 + 3y0 pair = \y0y1.y0 + y1 s = \y0.y0 Using this interpretation, the requirements translate to: [[g(0)]] = 3 > 0 = [[pair(s(0), 0)]] [[g(s(0))]] = 3 > 0 = [[pair(s(0), s(0))]] [[!plus(_x0, 0)]] = 3 + x0 > x0 = [[_x0]] We can thus remove the following rules: g(0) => pair(s(0), 0) g(s(0)) => pair(s(0), s(0)) !plus(X, 0) => 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.