/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 f : [o * o * o * o * o * o * o * o * o * o] --> o s : [o] --> o f(s(X), Y, Z, U, V, W, Q, R, S, T) => f(X, Y, Z, U, V, W, Q, R, S, T) f(0, s(X), Y, Z, U, V, W, Q, R, S) => f(X, X, Y, Z, U, V, W, Q, R, S) f(0, 0, s(X), Y, Z, U, V, W, Q, R) => f(X, X, X, Y, Z, U, V, W, Q, R) f(0, 0, 0, s(X), Y, Z, U, V, W, Q) => f(X, X, X, X, Y, Z, U, V, W, Q) f(0, 0, 0, 0, s(X), Y, Z, U, V, W) => f(X, X, X, X, X, Y, Z, U, V, W) f(0, 0, 0, 0, 0, s(X), Y, Z, U, V) => f(X, X, X, X, X, X, Y, Z, U, V) f(0, 0, 0, 0, 0, 0, s(X), Y, Z, U) => f(X, X, X, X, X, X, X, Y, Z, U) f(0, 0, 0, 0, 0, 0, 0, s(X), Y, Z) => f(X, X, X, X, X, X, X, X, Y, Z) f(0, 0, 0, 0, 0, 0, 0, 0, s(X), Y) => f(X, X, X, X, X, X, X, X, X, Y) f(0, 0, 0, 0, 0, 0, 0, 0, 0, s(X)) => f(X, X, X, X, X, X, X, X, X, X) f(0, 0, 0, 0, 0, 0, 0, 0, 0, 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]): f(s(X), Y, Z, U, V, W, Q, R, S, T) >? f(X, Y, Z, U, V, W, Q, R, S, T) f(0, s(X), Y, Z, U, V, W, Q, R, S) >? f(X, X, Y, Z, U, V, W, Q, R, S) f(0, 0, s(X), Y, Z, U, V, W, Q, R) >? f(X, X, X, Y, Z, U, V, W, Q, R) f(0, 0, 0, s(X), Y, Z, U, V, W, Q) >? f(X, X, X, X, Y, Z, U, V, W, Q) f(0, 0, 0, 0, s(X), Y, Z, U, V, W) >? f(X, X, X, X, X, Y, Z, U, V, W) f(0, 0, 0, 0, 0, s(X), Y, Z, U, V) >? f(X, X, X, X, X, X, Y, Z, U, V) f(0, 0, 0, 0, 0, 0, s(X), Y, Z, U) >? f(X, X, X, X, X, X, X, Y, Z, U) f(0, 0, 0, 0, 0, 0, 0, s(X), Y, Z) >? f(X, X, X, X, X, X, X, X, Y, Z) f(0, 0, 0, 0, 0, 0, 0, 0, s(X), Y) >? f(X, X, X, X, X, X, X, X, X, Y) f(0, 0, 0, 0, 0, 0, 0, 0, 0, s(X)) >? f(X, X, X, X, X, X, X, X, X, X) f(0, 0, 0, 0, 0, 0, 0, 0, 0, 0) >? 0 about to try horpo We use a recursive path ordering as defined in [Kop12, Chapter 5]. Argument functions: [[0]] = _|_ We choose Lex = {} and Mul = {f, s}, and the following precedence: s > f Taking the argument function into account, and fixing the greater / greater equal choices, the constraints can be denoted as follows: f(s(X), Y, Z, U, V, W, Q, R, S, T) >= f(X, Y, Z, U, V, W, Q, R, S, T) f(_|_, s(X), Y, Z, U, V, W, Q, R, S) > f(X, X, Y, Z, U, V, W, Q, R, S) f(_|_, _|_, s(X), Y, Z, U, V, W, Q, R) > f(X, X, X, Y, Z, U, V, W, Q, R) f(_|_, _|_, _|_, s(X), Y, Z, U, V, W, Q) > f(X, X, X, X, Y, Z, U, V, W, Q) f(_|_, _|_, _|_, _|_, s(X), Y, Z, U, V, W) > f(X, X, X, X, X, Y, Z, U, V, W) f(_|_, _|_, _|_, _|_, _|_, s(X), Y, Z, U, V) >= f(X, X, X, X, X, X, Y, Z, U, V) f(_|_, _|_, _|_, _|_, _|_, _|_, s(X), Y, Z, U) >= f(X, X, X, X, X, X, X, Y, Z, U) f(_|_, _|_, _|_, _|_, _|_, _|_, _|_, s(X), Y, Z) > f(X, X, X, X, X, X, X, X, Y, Z) f(_|_, _|_, _|_, _|_, _|_, _|_, _|_, _|_, s(X), Y) > f(X, X, X, X, X, X, X, X, X, Y) f(_|_, _|_, _|_, _|_, _|_, _|_, _|_, _|_, _|_, s(X)) >= f(X, X, X, X, X, X, X, X, X, X) f(_|_, _|_, _|_, _|_, _|_, _|_, _|_, _|_, _|_, _|_) >= _|_ With these choices, we have: 1] f(s(X), Y, Z, U, V, W, Q, R, S, T) >= f(X, Y, Z, U, V, W, Q, R, S, T) because f in Mul, [2], [5], [6], [7], [8], [9], [10], [11], [12] and [13], by (Fun) 2] s(X) >= X because [3], by (Star) 3] s*(X) >= X because [4], by (Select) 4] X >= X by (Meta) 5] Y >= Y by (Meta) 6] Z >= Z by (Meta) 7] U >= U by (Meta) 8] V >= V by (Meta) 9] W >= W by (Meta) 10] Q >= Q by (Meta) 11] R >= R by (Meta) 12] S >= S by (Meta) 13] T >= T by (Meta) 14] f(_|_, s(X), Y, Z, U, V, W, Q, R, S) > f(X, X, Y, Z, U, V, W, Q, R, S) because [15], by definition 15] f*(_|_, s(X), Y, Z, U, V, W, Q, R, S) >= f(X, X, Y, Z, U, V, W, Q, R, S) because f in Mul, [16], [16], [6], [7], [8], [9], [10], [11], [12] and [13], by (Stat) 16] s(X) > X because [17], by definition 17] s*(X) >= X because [5], by (Select) 18] f(_|_, _|_, s(X), Y, Z, U, V, W, Q, R) > f(X, X, X, Y, Z, U, V, W, Q, R) because [19], by definition 19] f*(_|_, _|_, s(X), Y, Z, U, V, W, Q, R) >= f(X, X, X, Y, Z, U, V, W, Q, R) because f in Mul, [20], [20], [20], [7], [8], [9], [10], [11], [12] and [13], by (Stat) 20] s(X) > X because [21], by definition 21] s*(X) >= X because [6], by (Select) 22] f(_|_, _|_, _|_, s(X), Y, Z, U, V, W, Q) > f(X, X, X, X, Y, Z, U, V, W, Q) because [23], by definition 23] f*(_|_, _|_, _|_, s(X), Y, Z, U, V, W, Q) >= f(X, X, X, X, Y, Z, U, V, W, Q) because f in Mul, [24], [24], [24], [24], [8], [9], [10], [11], [12] and [13], by (Stat) 24] s(X) > X because [25], by definition 25] s*(X) >= X because [7], by (Select) 26] f(_|_, _|_, _|_, _|_, s(X), Y, Z, U, V, W) > f(X, X, X, X, X, Y, Z, U, V, W) because [27], by definition 27] f*(_|_, _|_, _|_, _|_, s(X), Y, Z, U, V, W) >= f(X, X, X, X, X, Y, Z, U, V, W) because f in Mul, [28], [28], [28], [28], [28], [9], [10], [11], [12] and [13], by (Stat) 28] s(X) > X because [29], by definition 29] s*(X) >= X because [8], by (Select) 30] f(_|_, _|_, _|_, _|_, _|_, s(X), Y, Z, U, V) >= f(X, X, X, X, X, X, Y, Z, U, V) because [31], by (Star) 31] f*(_|_, _|_, _|_, _|_, _|_, s(X), Y, Z, U, V) >= f(X, X, X, X, X, X, Y, Z, U, V) because f in Mul, [32], [32], [32], [32], [32], [32], [10], [11], [12] and [13], by (Stat) 32] s(X) > X because [33], by definition 33] s*(X) >= X because [9], by (Select) 34] f(_|_, _|_, _|_, _|_, _|_, _|_, s(X), Y, Z, U) >= f(X, X, X, X, X, X, X, Y, Z, U) because [35], by (Star) 35] f*(_|_, _|_, _|_, _|_, _|_, _|_, s(X), Y, Z, U) >= f(X, X, X, X, X, X, X, Y, Z, U) because f in Mul, [36], [36], [36], [36], [36], [36], [36], [11], [12] and [13], by (Stat) 36] s(X) > X because [37], by definition 37] s*(X) >= X because [10], by (Select) 38] f(_|_, _|_, _|_, _|_, _|_, _|_, _|_, s(X), Y, Z) > f(X, X, X, X, X, X, X, X, Y, Z) because [39], by definition 39] f*(_|_, _|_, _|_, _|_, _|_, _|_, _|_, s(X), Y, Z) >= f(X, X, X, X, X, X, X, X, Y, Z) because f in Mul, [40], [40], [40], [40], [40], [40], [40], [40], [12] and [13], by (Stat) 40] s(X) > X because [41], by definition 41] s*(X) >= X because [11], by (Select) 42] f(_|_, _|_, _|_, _|_, _|_, _|_, _|_, _|_, s(X), Y) > f(X, X, X, X, X, X, X, X, X, Y) because [43], by definition 43] f*(_|_, _|_, _|_, _|_, _|_, _|_, _|_, _|_, s(X), Y) >= f(X, X, X, X, X, X, X, X, X, Y) because f in Mul, [44], [44], [44], [44], [44], [44], [44], [44], [44] and [13], by (Stat) 44] s(X) > X because [45], by definition 45] s*(X) >= X because [12], by (Select) 46] f(_|_, _|_, _|_, _|_, _|_, _|_, _|_, _|_, _|_, s(X)) >= f(X, X, X, X, X, X, X, X, X, X) because [47], by (Star) 47] f*(_|_, _|_, _|_, _|_, _|_, _|_, _|_, _|_, _|_, s(X)) >= f(X, X, X, X, X, X, X, X, X, X) because [48], by (Select) 48] s(X) >= f(X, X, X, X, X, X, X, X, X, X) because [49], by (Star) 49] s*(X) >= f(X, X, X, X, X, X, X, X, X, X) because s > f, [50], [50], [50], [50], [50], [50], [50], [50], [50] and [50], by (Copy) 50] s*(X) >= X because [13], by (Select) 51] f(_|_, _|_, _|_, _|_, _|_, _|_, _|_, _|_, _|_, _|_) >= _|_ by (Bot) We can thus remove the following rules: f(0, s(X), Y, Z, U, V, W, Q, R, S) => f(X, X, Y, Z, U, V, W, Q, R, S) f(0, 0, s(X), Y, Z, U, V, W, Q, R) => f(X, X, X, Y, Z, U, V, W, Q, R) f(0, 0, 0, s(X), Y, Z, U, V, W, Q) => f(X, X, X, X, Y, Z, U, V, W, Q) f(0, 0, 0, 0, s(X), Y, Z, U, V, W) => f(X, X, X, X, X, Y, Z, U, V, W) f(0, 0, 0, 0, 0, 0, 0, s(X), Y, Z) => f(X, X, X, X, X, X, X, X, Y, Z) f(0, 0, 0, 0, 0, 0, 0, 0, s(X), Y) => f(X, X, X, X, X, X, X, X, 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]): f(s(X), Y, Z, U, V, W, Q, R, S, T) >? f(X, Y, Z, U, V, W, Q, R, S, T) f(0, 0, 0, 0, 0, s(X), Y, Z, U, V) >? f(X, X, X, X, X, X, Y, Z, U, V) f(0, 0, 0, 0, 0, 0, s(X), Y, Z, U) >? f(X, X, X, X, X, X, X, Y, Z, U) f(0, 0, 0, 0, 0, 0, 0, 0, 0, s(X)) >? f(X, X, X, X, X, X, X, X, X, X) f(0, 0, 0, 0, 0, 0, 0, 0, 0, 0) >? 0 about to try horpo We use a recursive path ordering as defined in [Kop12, Chapter 5]. We choose Lex = {} and Mul = {0, f, s}, and the following precedence: s > f > 0 With these choices, we have: 1] f(s(X), Y, Z, U, V, W, Q, R, S, T) >= f(X, Y, Z, U, V, W, Q, R, S, T) because f in Mul, [2], [5], [6], [7], [8], [9], [10], [11], [12] and [13], by (Fun) 2] s(X) >= X because [3], by (Star) 3] s*(X) >= X because [4], by (Select) 4] X >= X by (Meta) 5] Y >= Y by (Meta) 6] Z >= Z by (Meta) 7] U >= U by (Meta) 8] V >= V by (Meta) 9] W >= W by (Meta) 10] Q >= Q by (Meta) 11] R >= R by (Meta) 12] S >= S by (Meta) 13] T >= T by (Meta) 14] f(0, 0, 0, 0, 0, s(X), Y, Z, U, V) > f(X, X, X, X, X, X, Y, Z, U, V) because [15], by definition 15] f*(0, 0, 0, 0, 0, s(X), Y, Z, U, V) >= f(X, X, X, X, X, X, Y, Z, U, V) because f in Mul, [16], [16], [16], [16], [16], [16], [10], [11], [12] and [13], by (Stat) 16] s(X) > X because [17], by definition 17] s*(X) >= X because [9], by (Select) 18] f(0, 0, 0, 0, 0, 0, s(X), Y, Z, U) >= f(X, X, X, X, X, X, X, Y, Z, U) because [19], by (Star) 19] f*(0, 0, 0, 0, 0, 0, s(X), Y, Z, U) >= f(X, X, X, X, X, X, X, Y, Z, U) because f in Mul, [20], [20], [20], [20], [20], [20], [20], [11], [12] and [13], by (Stat) 20] s(X) > X because [21], by definition 21] s*(X) >= X because [10], by (Select) 22] f(0, 0, 0, 0, 0, 0, 0, 0, 0, s(X)) >= f(X, X, X, X, X, X, X, X, X, X) because [23], by (Star) 23] f*(0, 0, 0, 0, 0, 0, 0, 0, 0, s(X)) >= f(X, X, X, X, X, X, X, X, X, X) because [24], by (Select) 24] s(X) >= f(X, X, X, X, X, X, X, X, X, X) because [25], by (Star) 25] s*(X) >= f(X, X, X, X, X, X, X, X, X, X) because s > f, [26], [26], [26], [26], [26], [26], [26], [26], [26] and [26], by (Copy) 26] s*(X) >= X because [13], by (Select) 27] f(0, 0, 0, 0, 0, 0, 0, 0, 0, 0) >= 0 because [28], by (Star) 28] f*(0, 0, 0, 0, 0, 0, 0, 0, 0, 0) >= 0 because f > 0, by (Copy) We can thus remove the following rules: f(0, 0, 0, 0, 0, s(X), Y, Z, U, V) => f(X, X, X, X, X, X, Y, Z, U, V) We use rule removal, following [Kop12, Theorem 2.23]. This gives the following requirements (possibly using Theorems 2.25 and 2.26 in [Kop12]): f(s(X), Y, Z, U, V, W, Q, R, S, T) >? f(X, Y, Z, U, V, W, Q, R, S, T) f(0, 0, 0, 0, 0, 0, s(X), Y, Z, U) >? f(X, X, X, X, X, X, X, Y, Z, U) f(0, 0, 0, 0, 0, 0, 0, 0, 0, s(X)) >? f(X, X, X, X, X, X, X, X, X, X) f(0, 0, 0, 0, 0, 0, 0, 0, 0, 0) >? 0 about to try horpo We use a recursive path ordering as defined in [Kop12, Chapter 5]. Argument functions: [[0]] = _|_ We choose Lex = {} and Mul = {f, s}, and the following precedence: s > f Taking the argument function into account, and fixing the greater / greater equal choices, the constraints can be denoted as follows: f(s(X), Y, Z, U, V, W, Q, R, S, T) >= f(X, Y, Z, U, V, W, Q, R, S, T) f(_|_, _|_, _|_, _|_, _|_, _|_, s(X), Y, Z, U) >= f(X, X, X, X, X, X, X, Y, Z, U) f(_|_, _|_, _|_, _|_, _|_, _|_, _|_, _|_, _|_, s(X)) > f(X, X, X, X, X, X, X, X, X, X) f(_|_, _|_, _|_, _|_, _|_, _|_, _|_, _|_, _|_, _|_) >= _|_ With these choices, we have: 1] f(s(X), Y, Z, U, V, W, Q, R, S, T) >= f(X, Y, Z, U, V, W, Q, R, S, T) because f in Mul, [2], [5], [6], [7], [8], [9], [10], [11], [12] and [13], by (Fun) 2] s(X) >= X because [3], by (Star) 3] s*(X) >= X because [4], by (Select) 4] X >= X by (Meta) 5] Y >= Y by (Meta) 6] Z >= Z by (Meta) 7] U >= U by (Meta) 8] V >= V by (Meta) 9] W >= W by (Meta) 10] Q >= Q by (Meta) 11] R >= R by (Meta) 12] S >= S by (Meta) 13] T >= T by (Meta) 14] f(_|_, _|_, _|_, _|_, _|_, _|_, s(X), Y, Z, U) >= f(X, X, X, X, X, X, X, Y, Z, U) because [15], by (Star) 15] f*(_|_, _|_, _|_, _|_, _|_, _|_, s(X), Y, Z, U) >= f(X, X, X, X, X, X, X, Y, Z, U) because f in Mul, [16], [16], [16], [16], [16], [16], [16], [11], [12] and [13], by (Stat) 16] s(X) > X because [17], by definition 17] s*(X) >= X because [10], by (Select) 18] f(_|_, _|_, _|_, _|_, _|_, _|_, _|_, _|_, _|_, s(X)) > f(X, X, X, X, X, X, X, X, X, X) because [19], by definition 19] f*(_|_, _|_, _|_, _|_, _|_, _|_, _|_, _|_, _|_, s(X)) >= f(X, X, X, X, X, X, X, X, X, X) because [20], by (Select) 20] s(X) >= f(X, X, X, X, X, X, X, X, X, X) because [21], by (Star) 21] s*(X) >= f(X, X, X, X, X, X, X, X, X, X) because s > f, [22], [22], [22], [22], [22], [22], [22], [22], [22] and [22], by (Copy) 22] s*(X) >= X because [13], by (Select) 23] f(_|_, _|_, _|_, _|_, _|_, _|_, _|_, _|_, _|_, _|_) >= _|_ by (Bot) We can thus remove the following rules: f(0, 0, 0, 0, 0, 0, 0, 0, 0, s(X)) => f(X, X, X, X, X, X, X, X, 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]): f(s(X), Y, Z, U, V, W, Q, R, S, T) >? f(X, Y, Z, U, V, W, Q, R, S, T) f(0, 0, 0, 0, 0, 0, s(X), Y, Z, U) >? f(X, X, X, X, X, X, X, Y, Z, U) f(0, 0, 0, 0, 0, 0, 0, 0, 0, 0) >? 0 We orient these requirements with a polynomial interpretation in the natural numbers. The following interpretation satisfies the requirements: 0 = 0 f = \y0y1y2y3y4y5y6y7y8y9.3 + y0 + y1 + y2 + y3 + y4 + y5 + 3y6 + 3y7 + 3y8 + 3y9 s = \y0.3 + 3y0 Using this interpretation, the requirements translate to: [[f(s(_x0), _x1, _x2, _x3, _x4, _x5, _x6, _x7, _x8, _x9)]] = 6 + x1 + x2 + x3 + x4 + x5 + 3x0 + 3x6 + 3x7 + 3x8 + 3x9 > 3 + x0 + x1 + x2 + x3 + x4 + x5 + 3x6 + 3x7 + 3x8 + 3x9 = [[f(_x0, _x1, _x2, _x3, _x4, _x5, _x6, _x7, _x8, _x9)]] [[f(0, 0, 0, 0, 0, 0, s(_x0), _x1, _x2, _x3)]] = 12 + 3x1 + 3x2 + 3x3 + 9x0 > 3 + 3x1 + 3x2 + 3x3 + 9x0 = [[f(_x0, _x0, _x0, _x0, _x0, _x0, _x0, _x1, _x2, _x3)]] [[f(0, 0, 0, 0, 0, 0, 0, 0, 0, 0)]] = 3 > 0 = [[0]] We can thus remove the following rules: f(s(X), Y, Z, U, V, W, Q, R, S, T) => f(X, Y, Z, U, V, W, Q, R, S, T) f(0, 0, 0, 0, 0, 0, s(X), Y, Z, U) => f(X, X, X, X, X, X, X, Y, Z, U) f(0, 0, 0, 0, 0, 0, 0, 0, 0, 0) => 0 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.