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