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