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