/export/starexec/sandbox2/solver/bin/starexec_run_FirstOrder /export/starexec/sandbox2/benchmark/theBenchmark.xml /export/starexec/sandbox2/output/output_files -------------------------------------------------------------------------------- YES We consider the system theBenchmark. We are asked to determine termination of the following first-order TRS. 0 : [] --> o U11 : [o * o] --> o U21 : [o * o * o] --> o activate : [o] --> o and : [o * o] --> o isNat : [o] --> o n!6220!62200 : [] --> o n!6220!6220isNat : [o] --> o n!6220!6220plus : [o * o] --> o n!6220!6220s : [o] --> o plus : [o * o] --> o s : [o] --> o tt : [] --> o U11(tt, X) => activate(X) U21(tt, X, Y) => s(plus(activate(Y), activate(X))) and(tt, X) => activate(X) isNat(n!6220!62200) => tt isNat(n!6220!6220plus(X, Y)) => and(isNat(activate(X)), n!6220!6220isNat(activate(Y))) isNat(n!6220!6220s(X)) => isNat(activate(X)) plus(X, 0) => U11(isNat(X), X) plus(X, s(Y)) => U21(and(isNat(Y), n!6220!6220isNat(X)), Y, X) 0 => n!6220!62200 plus(X, Y) => n!6220!6220plus(X, Y) isNat(X) => n!6220!6220isNat(X) s(X) => n!6220!6220s(X) activate(n!6220!62200) => 0 activate(n!6220!6220plus(X, Y)) => plus(X, Y) activate(n!6220!6220isNat(X)) => isNat(X) activate(n!6220!6220s(X)) => s(X) 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]): U11(tt, X) >? activate(X) U21(tt, X, Y) >? s(plus(activate(Y), activate(X))) and(tt, X) >? activate(X) isNat(n!6220!62200) >? tt isNat(n!6220!6220plus(X, Y)) >? and(isNat(activate(X)), n!6220!6220isNat(activate(Y))) isNat(n!6220!6220s(X)) >? isNat(activate(X)) plus(X, 0) >? U11(isNat(X), X) plus(X, s(Y)) >? U21(and(isNat(Y), n!6220!6220isNat(X)), Y, X) 0 >? n!6220!62200 plus(X, Y) >? n!6220!6220plus(X, Y) isNat(X) >? n!6220!6220isNat(X) s(X) >? n!6220!6220s(X) activate(n!6220!62200) >? 0 activate(n!6220!6220plus(X, Y)) >? plus(X, Y) activate(n!6220!6220isNat(X)) >? isNat(X) activate(n!6220!6220s(X)) >? s(X) activate(X) >? X about to try horpo We use a recursive path ordering as defined in [Kop12, Chapter 5]. Argument functions: [[0]] = _|_ [[U21(x_1, x_2, x_3)]] = U21(x_3, x_2, x_1) [[activate(x_1)]] = x_1 [[n!6220!62200]] = _|_ [[tt]] = _|_ We choose Lex = {U21, n!6220!6220plus, plus} and Mul = {U11, and, isNat, n!6220!6220isNat, n!6220!6220s, s}, and the following precedence: U21 = n!6220!6220plus = plus > isNat = n!6220!6220isNat > and > n!6220!6220s = s > U11 Taking the argument function into account, and fixing the greater / greater equal choices, the constraints can be denoted as follows: U11(_|_, X) >= X U21(_|_, X, Y) >= s(plus(Y, X)) and(_|_, X) >= X isNat(_|_) > _|_ isNat(n!6220!6220plus(X, Y)) >= and(isNat(X), n!6220!6220isNat(Y)) isNat(n!6220!6220s(X)) >= isNat(X) plus(X, _|_) >= U11(isNat(X), X) plus(X, s(Y)) >= U21(and(isNat(Y), n!6220!6220isNat(X)), Y, X) _|_ >= _|_ plus(X, Y) >= n!6220!6220plus(X, Y) isNat(X) >= n!6220!6220isNat(X) s(X) >= n!6220!6220s(X) _|_ >= _|_ n!6220!6220plus(X, Y) >= plus(X, Y) n!6220!6220isNat(X) >= isNat(X) n!6220!6220s(X) >= s(X) X >= X With these choices, we have: 1] U11(_|_, X) >= X because [2], by (Star) 2] U11*(_|_, X) >= X because [3], by (Select) 3] X >= X by (Meta) 4] U21(_|_, X, Y) >= s(plus(Y, X)) because [5], by (Star) 5] U21*(_|_, X, Y) >= s(plus(Y, X)) because U21 > s and [6], by (Copy) 6] U21*(_|_, X, Y) >= plus(Y, X) because U21 = plus, [7], [8], [9] and [10], by (Stat) 7] X >= X by (Meta) 8] Y >= Y by (Meta) 9] U21*(_|_, X, Y) >= Y because [8], by (Select) 10] U21*(_|_, X, Y) >= X because [7], by (Select) 11] and(_|_, X) >= X because [12], by (Star) 12] and*(_|_, X) >= X because [13], by (Select) 13] X >= X by (Meta) 14] isNat(_|_) > _|_ because [15], by definition 15] isNat*(_|_) >= _|_ by (Bot) 16] isNat(n!6220!6220plus(X, Y)) >= and(isNat(X), n!6220!6220isNat(Y)) because [17], by (Star) 17] isNat*(n!6220!6220plus(X, Y)) >= and(isNat(X), n!6220!6220isNat(Y)) because isNat > and, [18] and [23], by (Copy) 18] isNat*(n!6220!6220plus(X, Y)) >= isNat(X) because [19], by (Select) 19] n!6220!6220plus(X, Y) >= isNat(X) because [20], by (Star) 20] n!6220!6220plus*(X, Y) >= isNat(X) because n!6220!6220plus > isNat and [21], by (Copy) 21] n!6220!6220plus*(X, Y) >= X because [22], by (Select) 22] X >= X by (Meta) 23] isNat*(n!6220!6220plus(X, Y)) >= n!6220!6220isNat(Y) because [24], by (Select) 24] n!6220!6220plus(X, Y) >= n!6220!6220isNat(Y) because [25], by (Star) 25] n!6220!6220plus*(X, Y) >= n!6220!6220isNat(Y) because n!6220!6220plus > n!6220!6220isNat and [26], by (Copy) 26] n!6220!6220plus*(X, Y) >= Y because [27], by (Select) 27] Y >= Y by (Meta) 28] isNat(n!6220!6220s(X)) >= isNat(X) because [29], by (Star) 29] isNat*(n!6220!6220s(X)) >= isNat(X) because isNat in Mul and [30], by (Stat) 30] n!6220!6220s(X) > X because [31], by definition 31] n!6220!6220s*(X) >= X because [22], by (Select) 32] plus(X, _|_) >= U11(isNat(X), X) because [33], by (Star) 33] plus*(X, _|_) >= U11(isNat(X), X) because plus > U11, [34] and [35], by (Copy) 34] plus*(X, _|_) >= isNat(X) because plus > isNat and [35], by (Copy) 35] plus*(X, _|_) >= X because [8], by (Select) 36] plus(X, s(Y)) >= U21(and(isNat(Y), n!6220!6220isNat(X)), Y, X) because [37], by (Star) 37] plus*(X, s(Y)) >= U21(and(isNat(Y), n!6220!6220isNat(X)), Y, X) because plus = U21, [8], [38], [40], [42] and [45], by (Stat) 38] s(Y) > Y because [39], by definition 39] s*(Y) >= Y because [7], by (Select) 40] plus*(X, s(Y)) >= and(isNat(Y), n!6220!6220isNat(X)) because plus > and, [41] and [44], by (Copy) 41] plus*(X, s(Y)) >= isNat(Y) because plus > isNat and [42], by (Copy) 42] plus*(X, s(Y)) >= Y because [43], by (Select) 43] s(Y) >= Y because [39], by (Star) 44] plus*(X, s(Y)) >= n!6220!6220isNat(X) because plus > n!6220!6220isNat and [45], by (Copy) 45] plus*(X, s(Y)) >= X because [8], by (Select) 46] _|_ >= _|_ by (Bot) 47] plus(X, Y) >= n!6220!6220plus(X, Y) because plus = n!6220!6220plus, [48] and [49], by (Fun) 48] X >= X by (Meta) 49] Y >= Y by (Meta) 50] isNat(X) >= n!6220!6220isNat(X) because isNat = n!6220!6220isNat, isNat in Mul and [51], by (Fun) 51] X >= X by (Meta) 52] s(X) >= n!6220!6220s(X) because s = n!6220!6220s, s in Mul and [51], by (Fun) 53] _|_ >= _|_ by (Bot) 54] n!6220!6220plus(X, Y) >= plus(X, Y) because n!6220!6220plus = plus, [48] and [49], by (Fun) 55] n!6220!6220isNat(X) >= isNat(X) because n!6220!6220isNat = isNat, n!6220!6220isNat in Mul and [51], by (Fun) 56] n!6220!6220s(X) >= s(X) because n!6220!6220s = s, n!6220!6220s in Mul and [51], by (Fun) 57] X >= X by (Meta) We can thus remove the following rules: isNat(n!6220!62200) => tt We use rule removal, following [Kop12, Theorem 2.23]. This gives the following requirements (possibly using Theorems 2.25 and 2.26 in [Kop12]): U11(tt, X) >? activate(X) U21(tt, X, Y) >? s(plus(activate(Y), activate(X))) and(tt, X) >? activate(X) isNat(n!6220!6220plus(X, Y)) >? and(isNat(activate(X)), n!6220!6220isNat(activate(Y))) isNat(n!6220!6220s(X)) >? isNat(activate(X)) plus(X, 0) >? U11(isNat(X), X) plus(X, s(Y)) >? U21(and(isNat(Y), n!6220!6220isNat(X)), Y, X) 0 >? n!6220!62200 plus(X, Y) >? n!6220!6220plus(X, Y) isNat(X) >? n!6220!6220isNat(X) s(X) >? n!6220!6220s(X) activate(n!6220!62200) >? 0 activate(n!6220!6220plus(X, Y)) >? plus(X, Y) activate(n!6220!6220isNat(X)) >? isNat(X) activate(n!6220!6220s(X)) >? s(X) activate(X) >? X about to try horpo We use a recursive path ordering as defined in [Kop12, Chapter 5]. Argument functions: [[0]] = _|_ [[U21(x_1, x_2, x_3)]] = U21(x_3, x_2, x_1) [[activate(x_1)]] = x_1 [[n!6220!62200]] = _|_ We choose Lex = {U21, n!6220!6220plus, plus} and Mul = {U11, and, isNat, n!6220!6220isNat, n!6220!6220s, s, tt}, and the following precedence: U21 = n!6220!6220plus = plus > and > n!6220!6220s = s > U11 > isNat = n!6220!6220isNat > tt Taking the argument function into account, and fixing the greater / greater equal choices, the constraints can be denoted as follows: U11(tt, X) > X U21(tt, X, Y) > s(plus(Y, X)) and(tt, X) >= X isNat(n!6220!6220plus(X, Y)) > and(isNat(X), n!6220!6220isNat(Y)) isNat(n!6220!6220s(X)) > isNat(X) plus(X, _|_) >= U11(isNat(X), X) plus(X, s(Y)) > U21(and(isNat(Y), n!6220!6220isNat(X)), Y, X) _|_ >= _|_ plus(X, Y) >= n!6220!6220plus(X, Y) isNat(X) >= n!6220!6220isNat(X) s(X) >= n!6220!6220s(X) _|_ >= _|_ n!6220!6220plus(X, Y) >= plus(X, Y) n!6220!6220isNat(X) >= isNat(X) n!6220!6220s(X) >= s(X) X >= X With these choices, we have: 1] U11(tt, X) > X because [2], by definition 2] U11*(tt, X) >= X because [3], by (Select) 3] X >= X by (Meta) 4] U21(tt, X, Y) > s(plus(Y, X)) because [5], by definition 5] U21*(tt, X, Y) >= s(plus(Y, X)) because U21 > s and [6], by (Copy) 6] U21*(tt, X, Y) >= plus(Y, X) because U21 = plus, [7], [8], [9] and [10], by (Stat) 7] X >= X by (Meta) 8] Y >= Y by (Meta) 9] U21*(tt, X, Y) >= Y because [8], by (Select) 10] U21*(tt, X, Y) >= X because [7], by (Select) 11] and(tt, X) >= X because [12], by (Star) 12] and*(tt, X) >= X because [13], by (Select) 13] X >= X by (Meta) 14] isNat(n!6220!6220plus(X, Y)) > and(isNat(X), n!6220!6220isNat(Y)) because [15], by definition 15] isNat*(n!6220!6220plus(X, Y)) >= and(isNat(X), n!6220!6220isNat(Y)) because [16], by (Select) 16] n!6220!6220plus(X, Y) >= and(isNat(X), n!6220!6220isNat(Y)) because [17], by (Star) 17] n!6220!6220plus*(X, Y) >= and(isNat(X), n!6220!6220isNat(Y)) because n!6220!6220plus > and, [18] and [21], by (Copy) 18] n!6220!6220plus*(X, Y) >= isNat(X) because n!6220!6220plus > isNat and [19], by (Copy) 19] n!6220!6220plus*(X, Y) >= X because [20], by (Select) 20] X >= X by (Meta) 21] n!6220!6220plus*(X, Y) >= n!6220!6220isNat(Y) because n!6220!6220plus > n!6220!6220isNat and [22], by (Copy) 22] n!6220!6220plus*(X, Y) >= Y because [23], by (Select) 23] Y >= Y by (Meta) 24] isNat(n!6220!6220s(X)) > isNat(X) because [25], by definition 25] isNat*(n!6220!6220s(X)) >= isNat(X) because isNat in Mul and [26], by (Stat) 26] n!6220!6220s(X) > X because [27], by definition 27] n!6220!6220s*(X) >= X because [20], by (Select) 28] plus(X, _|_) >= U11(isNat(X), X) because [29], by (Star) 29] plus*(X, _|_) >= U11(isNat(X), X) because plus > U11, [30] and [31], by (Copy) 30] plus*(X, _|_) >= isNat(X) because plus > isNat and [31], by (Copy) 31] plus*(X, _|_) >= X because [8], by (Select) 32] plus(X, s(Y)) > U21(and(isNat(Y), n!6220!6220isNat(X)), Y, X) because [33], by definition 33] plus*(X, s(Y)) >= U21(and(isNat(Y), n!6220!6220isNat(X)), Y, X) because plus = U21, [8], [34], [36], [38] and [41], by (Stat) 34] s(Y) > Y because [35], by definition 35] s*(Y) >= Y because [7], by (Select) 36] plus*(X, s(Y)) >= and(isNat(Y), n!6220!6220isNat(X)) because plus > and, [37] and [40], by (Copy) 37] plus*(X, s(Y)) >= isNat(Y) because plus > isNat and [38], by (Copy) 38] plus*(X, s(Y)) >= Y because [39], by (Select) 39] s(Y) >= Y because [35], by (Star) 40] plus*(X, s(Y)) >= n!6220!6220isNat(X) because plus > n!6220!6220isNat and [41], by (Copy) 41] plus*(X, s(Y)) >= X because [8], by (Select) 42] _|_ >= _|_ by (Bot) 43] plus(X, Y) >= n!6220!6220plus(X, Y) because plus = n!6220!6220plus, [44] and [45], by (Fun) 44] X >= X by (Meta) 45] Y >= Y by (Meta) 46] isNat(X) >= n!6220!6220isNat(X) because isNat = n!6220!6220isNat, isNat in Mul and [47], by (Fun) 47] X >= X by (Meta) 48] s(X) >= n!6220!6220s(X) because s = n!6220!6220s, s in Mul and [47], by (Fun) 49] _|_ >= _|_ by (Bot) 50] n!6220!6220plus(X, Y) >= plus(X, Y) because n!6220!6220plus = plus, [44] and [45], by (Fun) 51] n!6220!6220isNat(X) >= isNat(X) because n!6220!6220isNat = isNat, n!6220!6220isNat in Mul and [47], by (Fun) 52] n!6220!6220s(X) >= s(X) because n!6220!6220s = s, n!6220!6220s in Mul and [47], by (Fun) 53] X >= X by (Meta) We can thus remove the following rules: U11(tt, X) => activate(X) U21(tt, X, Y) => s(plus(activate(Y), activate(X))) isNat(n!6220!6220plus(X, Y)) => and(isNat(activate(X)), n!6220!6220isNat(activate(Y))) isNat(n!6220!6220s(X)) => isNat(activate(X)) plus(X, s(Y)) => U21(and(isNat(Y), n!6220!6220isNat(X)), Y, 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]): and(tt, X) >? activate(X) plus(X, 0) >? U11(isNat(X), X) 0 >? n!6220!62200 plus(X, Y) >? n!6220!6220plus(X, Y) isNat(X) >? n!6220!6220isNat(X) s(X) >? n!6220!6220s(X) activate(n!6220!62200) >? 0 activate(n!6220!6220plus(X, Y)) >? plus(X, Y) activate(n!6220!6220isNat(X)) >? isNat(X) activate(n!6220!6220s(X)) >? s(X) activate(X) >? X We orient these requirements with a polynomial interpretation in the natural numbers. The following interpretation satisfies the requirements: 0 = 2 U11 = \y0y1.y0 + y1 activate = \y0.2 + 3y0 and = \y0y1.3 + 3y0 + 3y1 isNat = \y0.2y0 n!6220!62200 = 1 n!6220!6220isNat = \y0.2y0 n!6220!6220plus = \y0y1.y1 + 2y0 n!6220!6220s = \y0.y0 plus = \y0y1.1 + y1 + 3y0 s = \y0.y0 tt = 3 Using this interpretation, the requirements translate to: [[and(tt, _x0)]] = 12 + 3x0 > 2 + 3x0 = [[activate(_x0)]] [[plus(_x0, 0)]] = 3 + 3x0 > 3x0 = [[U11(isNat(_x0), _x0)]] [[0]] = 2 > 1 = [[n!6220!62200]] [[plus(_x0, _x1)]] = 1 + x1 + 3x0 > x1 + 2x0 = [[n!6220!6220plus(_x0, _x1)]] [[isNat(_x0)]] = 2x0 >= 2x0 = [[n!6220!6220isNat(_x0)]] [[s(_x0)]] = x0 >= x0 = [[n!6220!6220s(_x0)]] [[activate(n!6220!62200)]] = 5 > 2 = [[0]] [[activate(n!6220!6220plus(_x0, _x1))]] = 2 + 3x1 + 6x0 > 1 + x1 + 3x0 = [[plus(_x0, _x1)]] [[activate(n!6220!6220isNat(_x0))]] = 2 + 6x0 > 2x0 = [[isNat(_x0)]] [[activate(n!6220!6220s(_x0))]] = 2 + 3x0 > x0 = [[s(_x0)]] [[activate(_x0)]] = 2 + 3x0 > x0 = [[_x0]] We can thus remove the following rules: and(tt, X) => activate(X) plus(X, 0) => U11(isNat(X), X) 0 => n!6220!62200 plus(X, Y) => n!6220!6220plus(X, Y) activate(n!6220!62200) => 0 activate(n!6220!6220plus(X, Y)) => plus(X, Y) activate(n!6220!6220isNat(X)) => isNat(X) activate(n!6220!6220s(X)) => s(X) 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]): isNat(X) >? n!6220!6220isNat(X) s(X) >? n!6220!6220s(X) We orient these requirements with a polynomial interpretation in the natural numbers. The following interpretation satisfies the requirements: isNat = \y0.3 + y0 n!6220!6220isNat = \y0.y0 n!6220!6220s = \y0.y0 s = \y0.3 + y0 Using this interpretation, the requirements translate to: [[isNat(_x0)]] = 3 + x0 > x0 = [[n!6220!6220isNat(_x0)]] [[s(_x0)]] = 3 + x0 > x0 = [[n!6220!6220s(_x0)]] We can thus remove the following rules: isNat(X) => n!6220!6220isNat(X) s(X) => n!6220!6220s(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.