/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!6220add : [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, n!6220!6220add(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) add(X, Y) => n!6220!6220add(X, Y) activate(n!6220!6220fib1(X, Y)) => fib1(activate(X), activate(Y)) activate(n!6220!6220add(X, Y)) => add(activate(X), activate(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, n!6220!6220add(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) add(X, Y) >? n!6220!6220add(X, Y) activate(n!6220!6220fib1(X, Y)) >? fib1(activate(X), activate(Y)) activate(n!6220!6220add(X, Y)) >? add(activate(X), activate(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!6220add, n!6220!6220fib1, s}, and the following precedence: fib > sel > activate > add > fib1 > cons > n!6220!6220add > 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, n!6220!6220add(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) add(X, Y) > n!6220!6220add(X, Y) activate(n!6220!6220fib1(X, Y)) > fib1(activate(X), activate(Y)) activate(n!6220!6220add(X, Y)) >= add(activate(X), activate(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, n!6220!6220add(X, Y))) because [9], by (Star) 9] fib1*(X, Y) >= cons(X, n!6220!6220fib1(Y, n!6220!6220add(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, n!6220!6220add(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) >= n!6220!6220add(X, Y) because fib1 > n!6220!6220add, [10] and [13], by (Copy) 16] add(_|_, X) >= X because [17], by (Star) 17] add*(_|_, X) >= X because [11], by (Select) 18] add(s(X), Y) > s(add(X, Y)) because [19], by definition 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 definition 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 definition 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] add(X, Y) > n!6220!6220add(X, Y) because [46], by definition 46] add*(X, Y) >= n!6220!6220add(X, Y) because add > n!6220!6220add, [47] and [48], by (Copy) 47] add*(X, Y) >= X because [42], by (Select) 48] add*(X, Y) >= Y because [44], by (Select) 49] activate(n!6220!6220fib1(X, Y)) > fib1(activate(X), activate(Y)) because [50], by definition 50] activate*(n!6220!6220fib1(X, Y)) >= fib1(activate(X), activate(Y)) because activate > fib1, [51] and [54], by (Copy) 51] activate*(n!6220!6220fib1(X, Y)) >= activate(X) because activate in Mul and [52], by (Stat) 52] n!6220!6220fib1(X, Y) > X because [53], by definition 53] n!6220!6220fib1*(X, Y) >= X because [42], by (Select) 54] activate*(n!6220!6220fib1(X, Y)) >= activate(Y) because activate in Mul and [55], by (Stat) 55] n!6220!6220fib1(X, Y) > Y because [56], by definition 56] n!6220!6220fib1*(X, Y) >= Y because [44], by (Select) 57] activate(n!6220!6220add(X, Y)) >= add(activate(X), activate(Y)) because [58], by (Star) 58] activate*(n!6220!6220add(X, Y)) >= add(activate(X), activate(Y)) because activate > add, [59] and [62], by (Copy) 59] activate*(n!6220!6220add(X, Y)) >= activate(X) because activate in Mul and [60], by (Stat) 60] n!6220!6220add(X, Y) > X because [61], by definition 61] n!6220!6220add*(X, Y) >= X because [42], by (Select) 62] activate*(n!6220!6220add(X, Y)) >= activate(Y) because activate in Mul and [63], by (Stat) 63] n!6220!6220add(X, Y) > Y because [64], by definition 64] n!6220!6220add*(X, Y) >= Y because [44], by (Select) 65] activate(X) >= X because [66], by (Star) 66] activate*(X) >= X because [11], by (Select) We can thus remove the following rules: 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) add(X, Y) => n!6220!6220add(X, Y) activate(n!6220!6220fib1(X, Y)) => fib1(activate(X), activate(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, n!6220!6220add(X, Y))) add(0, X) >? X activate(n!6220!6220add(X, Y)) >? add(activate(X), activate(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.y0 add = \y0y1.y0 + y1 cons = \y0y1.y0 + y1 fib = \y0.3 + 3y0 fib1 = \y0y1.1 + 2y0 + 2y1 n!6220!6220add = \y0y1.y0 + y1 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, n!6220!6220add(_x0, _x1)))]] [[add(0, _x0)]] = x0 >= x0 = [[_x0]] [[activate(n!6220!6220add(_x0, _x1))]] = x0 + x1 >= x0 + x1 = [[add(activate(_x0), activate(_x1))]] [[activate(_x0)]] = x0 >= 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, n!6220!6220add(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]): add(0, X) >? X activate(n!6220!6220add(X, Y)) >? add(activate(X), activate(Y)) activate(X) >? X We orient these requirements with a polynomial interpretation in the natural numbers. The following interpretation satisfies the requirements: 0 = 3 activate = \y0.3y0 add = \y0y1.y0 + y1 n!6220!6220add = \y0y1.3 + 3y0 + 3y1 Using this interpretation, the requirements translate to: [[add(0, _x0)]] = 3 + x0 > x0 = [[_x0]] [[activate(n!6220!6220add(_x0, _x1))]] = 9 + 9x0 + 9x1 > 3x0 + 3x1 = [[add(activate(_x0), activate(_x1))]] [[activate(_x0)]] = 3x0 >= x0 = [[_x0]] We can thus remove the following rules: add(0, X) => X activate(n!6220!6220add(X, Y)) => add(activate(X), activate(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]): activate(X) >? X We orient these requirements with a polynomial interpretation in the natural numbers. The following interpretation satisfies the requirements: activate = \y0.1 + y0 Using this interpretation, the requirements translate to: [[activate(_x0)]] = 1 + x0 > x0 = [[_x0]] We can thus remove the following rules: activate(X) => 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.