/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] --> o U12 : [o * o] --> o U13 : [o] --> o U21 : [o * o] --> o U22 : [o] --> o U31 : [o * o] --> o U41 : [o * o * o] --> o activate : [o] --> o and : [o * o] --> o isNat : [o] --> o isNatKind : [o] --> o n!6220!62200 : [] --> o n!6220!6220and : [o * o] --> o n!6220!6220isNat : [o] --> o n!6220!6220isNatKind : [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, Y) => U12(isNat(activate(X)), activate(Y)) U12(tt, X) => U13(isNat(activate(X))) U13(tt) => tt U21(tt, X) => U22(isNat(activate(X))) U22(tt) => tt U31(tt, X) => activate(X) U41(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)) => U11(and(isNatKind(activate(X)), n!6220!6220isNatKind(activate(Y))), activate(X), activate(Y)) isNat(n!6220!6220s(X)) => U21(isNatKind(activate(X)), activate(X)) isNatKind(n!6220!62200) => tt isNatKind(n!6220!6220plus(X, Y)) => and(isNatKind(activate(X)), n!6220!6220isNatKind(activate(Y))) isNatKind(n!6220!6220s(X)) => isNatKind(activate(X)) plus(X, 0) => U31(and(isNat(X), n!6220!6220isNatKind(X)), X) plus(X, s(Y)) => U41(and(and(isNat(Y), n!6220!6220isNatKind(Y)), n!6220!6220and(n!6220!6220isNat(X), n!6220!6220isNatKind(X))), Y, X) 0 => n!6220!62200 plus(X, Y) => n!6220!6220plus(X, Y) isNatKind(X) => n!6220!6220isNatKind(X) s(X) => n!6220!6220s(X) and(X, Y) => n!6220!6220and(X, Y) isNat(X) => n!6220!6220isNat(X) activate(n!6220!62200) => 0 activate(n!6220!6220plus(X, Y)) => plus(activate(X), activate(Y)) activate(n!6220!6220isNatKind(X)) => isNatKind(X) activate(n!6220!6220s(X)) => s(activate(X)) activate(n!6220!6220and(X, Y)) => and(activate(X), Y) activate(n!6220!6220isNat(X)) => isNat(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, Y) >? U12(isNat(activate(X)), activate(Y)) U12(tt, X) >? U13(isNat(activate(X))) U13(tt) >? tt U21(tt, X) >? U22(isNat(activate(X))) U22(tt) >? tt U31(tt, X) >? activate(X) U41(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)) >? U11(and(isNatKind(activate(X)), n!6220!6220isNatKind(activate(Y))), activate(X), activate(Y)) isNat(n!6220!6220s(X)) >? U21(isNatKind(activate(X)), activate(X)) isNatKind(n!6220!62200) >? tt isNatKind(n!6220!6220plus(X, Y)) >? and(isNatKind(activate(X)), n!6220!6220isNatKind(activate(Y))) isNatKind(n!6220!6220s(X)) >? isNatKind(activate(X)) plus(X, 0) >? U31(and(isNat(X), n!6220!6220isNatKind(X)), X) plus(X, s(Y)) >? U41(and(and(isNat(Y), n!6220!6220isNatKind(Y)), n!6220!6220and(n!6220!6220isNat(X), n!6220!6220isNatKind(X))), Y, X) 0 >? n!6220!62200 plus(X, Y) >? n!6220!6220plus(X, Y) isNatKind(X) >? n!6220!6220isNatKind(X) s(X) >? n!6220!6220s(X) and(X, Y) >? n!6220!6220and(X, Y) isNat(X) >? n!6220!6220isNat(X) activate(n!6220!62200) >? 0 activate(n!6220!6220plus(X, Y)) >? plus(activate(X), activate(Y)) activate(n!6220!6220isNatKind(X)) >? isNatKind(X) activate(n!6220!6220s(X)) >? s(activate(X)) activate(n!6220!6220and(X, Y)) >? and(activate(X), Y) activate(n!6220!6220isNat(X)) >? isNat(X) activate(X) >? X about to try horpo We use a recursive path ordering as defined in [Kop12, Chapter 5]. Argument functions: [[0]] = _|_ [[U13(x_1)]] = x_1 [[U22(x_1)]] = x_1 [[U41(x_1, x_2, x_3)]] = U41(x_2, x_3, x_1) [[activate(x_1)]] = x_1 [[n!6220!62200]] = _|_ [[n!6220!6220plus(x_1, x_2)]] = n!6220!6220plus(x_2, x_1) [[plus(x_1, x_2)]] = plus(x_2, x_1) [[tt]] = _|_ We choose Lex = {U41, n!6220!6220plus, plus} and Mul = {U11, U12, U21, U31, and, isNat, isNatKind, n!6220!6220and, n!6220!6220isNat, n!6220!6220isNatKind, n!6220!6220s, s}, and the following precedence: U41 = n!6220!6220plus = plus > U11 > U12 > n!6220!6220s = s > U21 > isNatKind = n!6220!6220isNatKind > U31 > and = n!6220!6220and > isNat = n!6220!6220isNat Taking the argument function into account, and fixing the greater / greater equal choices, the constraints can be denoted as follows: U11(_|_, X, Y) > U12(isNat(X), Y) U12(_|_, X) > isNat(X) _|_ >= _|_ U21(_|_, X) >= isNat(X) _|_ >= _|_ U31(_|_, X) >= X U41(_|_, X, Y) >= s(plus(Y, X)) and(_|_, X) > X isNat(_|_) >= _|_ isNat(n!6220!6220plus(X, Y)) > U11(and(isNatKind(X), n!6220!6220isNatKind(Y)), X, Y) isNat(n!6220!6220s(X)) > U21(isNatKind(X), X) isNatKind(_|_) >= _|_ isNatKind(n!6220!6220plus(X, Y)) >= and(isNatKind(X), n!6220!6220isNatKind(Y)) isNatKind(n!6220!6220s(X)) >= isNatKind(X) plus(X, _|_) >= U31(and(isNat(X), n!6220!6220isNatKind(X)), X) plus(X, s(Y)) > U41(and(and(isNat(Y), n!6220!6220isNatKind(Y)), n!6220!6220and(n!6220!6220isNat(X), n!6220!6220isNatKind(X))), Y, X) _|_ >= _|_ plus(X, Y) >= n!6220!6220plus(X, Y) isNatKind(X) >= n!6220!6220isNatKind(X) s(X) >= n!6220!6220s(X) and(X, Y) >= n!6220!6220and(X, Y) isNat(X) >= n!6220!6220isNat(X) _|_ >= _|_ n!6220!6220plus(X, Y) >= plus(X, Y) n!6220!6220isNatKind(X) >= isNatKind(X) n!6220!6220s(X) >= s(X) n!6220!6220and(X, Y) >= and(X, Y) n!6220!6220isNat(X) >= isNat(X) X >= X With these choices, we have: 1] U11(_|_, X, Y) > U12(isNat(X), Y) because [2], by definition 2] U11*(_|_, X, Y) >= U12(isNat(X), Y) because U11 > U12, [3] and [6], by (Copy) 3] U11*(_|_, X, Y) >= isNat(X) because U11 > isNat and [4], by (Copy) 4] U11*(_|_, X, Y) >= X because [5], by (Select) 5] X >= X by (Meta) 6] U11*(_|_, X, Y) >= Y because [7], by (Select) 7] Y >= Y by (Meta) 8] U12(_|_, X) > isNat(X) because [9], by definition 9] U12*(_|_, X) >= isNat(X) because U12 > isNat and [10], by (Copy) 10] U12*(_|_, X) >= X because [7], by (Select) 11] _|_ >= _|_ by (Bot) 12] U21(_|_, X) >= isNat(X) because [13], by (Star) 13] U21*(_|_, X) >= isNat(X) because U21 > isNat and [14], by (Copy) 14] U21*(_|_, X) >= X because [5], by (Select) 15] _|_ >= _|_ by (Bot) 16] U31(_|_, X) >= X because [17], by (Star) 17] U31*(_|_, X) >= X because [18], by (Select) 18] X >= X by (Meta) 19] U41(_|_, X, Y) >= s(plus(Y, X)) because [20], by (Star) 20] U41*(_|_, X, Y) >= s(plus(Y, X)) because U41 > s and [21], by (Copy) 21] U41*(_|_, X, Y) >= plus(Y, X) because U41 = plus, [22], [23], [24] and [25], by (Stat) 22] X >= X by (Meta) 23] Y >= Y by (Meta) 24] U41*(_|_, X, Y) >= Y because [23], by (Select) 25] U41*(_|_, X, Y) >= X because [22], by (Select) 26] and(_|_, X) > X because [27], by definition 27] and*(_|_, X) >= X because [28], by (Select) 28] X >= X by (Meta) 29] isNat(_|_) >= _|_ by (Bot) 30] isNat(n!6220!6220plus(X, Y)) > U11(and(isNatKind(X), n!6220!6220isNatKind(Y)), X, Y) because [31], by definition 31] isNat*(n!6220!6220plus(X, Y)) >= U11(and(isNatKind(X), n!6220!6220isNatKind(Y)), X, Y) because [32], by (Select) 32] n!6220!6220plus(X, Y) >= U11(and(isNatKind(X), n!6220!6220isNatKind(Y)), X, Y) because [33], by (Star) 33] n!6220!6220plus*(X, Y) >= U11(and(isNatKind(X), n!6220!6220isNatKind(Y)), X, Y) because n!6220!6220plus > U11, [34], [36] and [38], by (Copy) 34] n!6220!6220plus*(X, Y) >= and(isNatKind(X), n!6220!6220isNatKind(Y)) because n!6220!6220plus > and, [35] and [37], by (Copy) 35] n!6220!6220plus*(X, Y) >= isNatKind(X) because n!6220!6220plus > isNatKind and [36], by (Copy) 36] n!6220!6220plus*(X, Y) >= X because [5], by (Select) 37] n!6220!6220plus*(X, Y) >= n!6220!6220isNatKind(Y) because n!6220!6220plus > n!6220!6220isNatKind and [38], by (Copy) 38] n!6220!6220plus*(X, Y) >= Y because [7], by (Select) 39] isNat(n!6220!6220s(X)) > U21(isNatKind(X), X) because [40], by definition 40] isNat*(n!6220!6220s(X)) >= U21(isNatKind(X), X) because [41], by (Select) 41] n!6220!6220s(X) >= U21(isNatKind(X), X) because [42], by (Star) 42] n!6220!6220s*(X) >= U21(isNatKind(X), X) because n!6220!6220s > U21, [43] and [44], by (Copy) 43] n!6220!6220s*(X) >= isNatKind(X) because n!6220!6220s > isNatKind and [44], by (Copy) 44] n!6220!6220s*(X) >= X because [5], by (Select) 45] isNatKind(_|_) >= _|_ by (Bot) 46] isNatKind(n!6220!6220plus(X, Y)) >= and(isNatKind(X), n!6220!6220isNatKind(Y)) because [47], by (Star) 47] isNatKind*(n!6220!6220plus(X, Y)) >= and(isNatKind(X), n!6220!6220isNatKind(Y)) because isNatKind > and, [48] and [50], by (Copy) 48] isNatKind*(n!6220!6220plus(X, Y)) >= isNatKind(X) because [49], by (Select) 49] n!6220!6220plus(X, Y) >= isNatKind(X) because [35], by (Star) 50] isNatKind*(n!6220!6220plus(X, Y)) >= n!6220!6220isNatKind(Y) because [51], by (Select) 51] n!6220!6220plus(X, Y) >= n!6220!6220isNatKind(Y) because [37], by (Star) 52] isNatKind(n!6220!6220s(X)) >= isNatKind(X) because isNatKind in Mul and [53], by (Fun) 53] n!6220!6220s(X) >= X because [44], by (Star) 54] plus(X, _|_) >= U31(and(isNat(X), n!6220!6220isNatKind(X)), X) because [55], by (Star) 55] plus*(X, _|_) >= U31(and(isNat(X), n!6220!6220isNatKind(X)), X) because plus > U31, [56] and [58], by (Copy) 56] plus*(X, _|_) >= and(isNat(X), n!6220!6220isNatKind(X)) because plus > and, [57] and [59], by (Copy) 57] plus*(X, _|_) >= isNat(X) because plus > isNat and [58], by (Copy) 58] plus*(X, _|_) >= X because [23], by (Select) 59] plus*(X, _|_) >= n!6220!6220isNatKind(X) because plus > n!6220!6220isNatKind and [58], by (Copy) 60] plus(X, s(Y)) > U41(and(and(isNat(Y), n!6220!6220isNatKind(Y)), n!6220!6220and(n!6220!6220isNat(X), n!6220!6220isNatKind(X))), Y, X) because [61], by definition 61] plus*(X, s(Y)) >= U41(and(and(isNat(Y), n!6220!6220isNatKind(Y)), n!6220!6220and(n!6220!6220isNat(X), n!6220!6220isNatKind(X))), Y, X) because plus = U41, [62], [64], [74] and [72], by (Stat) 62] s(Y) > Y because [63], by definition 63] s*(Y) >= Y because [22], by (Select) 64] plus*(X, s(Y)) >= and(and(isNat(Y), n!6220!6220isNatKind(Y)), n!6220!6220and(n!6220!6220isNat(X), n!6220!6220isNatKind(X))) because plus > and, [65] and [70], by (Copy) 65] plus*(X, s(Y)) >= and(isNat(Y), n!6220!6220isNatKind(Y)) because [66], by (Select) 66] s(Y) >= and(isNat(Y), n!6220!6220isNatKind(Y)) because [67], by (Star) 67] s*(Y) >= and(isNat(Y), n!6220!6220isNatKind(Y)) because s > and, [68] and [69], by (Copy) 68] s*(Y) >= isNat(Y) because s > isNat and [63], by (Copy) 69] s*(Y) >= n!6220!6220isNatKind(Y) because s > n!6220!6220isNatKind and [63], by (Copy) 70] plus*(X, s(Y)) >= n!6220!6220and(n!6220!6220isNat(X), n!6220!6220isNatKind(X)) because plus > n!6220!6220and, [71] and [73], by (Copy) 71] plus*(X, s(Y)) >= n!6220!6220isNat(X) because plus > n!6220!6220isNat and [72], by (Copy) 72] plus*(X, s(Y)) >= X because [23], by (Select) 73] plus*(X, s(Y)) >= n!6220!6220isNatKind(X) because plus > n!6220!6220isNatKind and [72], by (Copy) 74] plus*(X, s(Y)) >= Y because [75], by (Select) 75] s(Y) >= Y because [63], by (Star) 76] _|_ >= _|_ by (Bot) 77] plus(X, Y) >= n!6220!6220plus(X, Y) because plus = n!6220!6220plus, [78] and [79], by (Fun) 78] X >= X by (Meta) 79] Y >= Y by (Meta) 80] isNatKind(X) >= n!6220!6220isNatKind(X) because isNatKind = n!6220!6220isNatKind, isNatKind in Mul and [81], by (Fun) 81] X >= X by (Meta) 82] s(X) >= n!6220!6220s(X) because s = n!6220!6220s, s in Mul and [81], by (Fun) 83] and(X, Y) >= n!6220!6220and(X, Y) because and = n!6220!6220and, and in Mul, [78] and [79], by (Fun) 84] isNat(X) >= n!6220!6220isNat(X) because isNat = n!6220!6220isNat, isNat in Mul and [81], by (Fun) 85] _|_ >= _|_ by (Bot) 86] n!6220!6220plus(X, Y) >= plus(X, Y) because n!6220!6220plus = plus, [87] and [88], by (Fun) 87] X >= X by (Meta) 88] Y >= Y by (Meta) 89] n!6220!6220isNatKind(X) >= isNatKind(X) because n!6220!6220isNatKind = isNatKind, n!6220!6220isNatKind in Mul and [81], by (Fun) 90] n!6220!6220s(X) >= s(X) because n!6220!6220s = s, n!6220!6220s in Mul and [91], by (Fun) 91] X >= X by (Meta) 92] n!6220!6220and(X, Y) >= and(X, Y) because n!6220!6220and = and, n!6220!6220and in Mul, [87] and [88], by (Fun) 93] n!6220!6220isNat(X) >= isNat(X) because n!6220!6220isNat = isNat, n!6220!6220isNat in Mul and [91], by (Fun) 94] X >= X by (Meta) We can thus remove the following rules: U11(tt, X, Y) => U12(isNat(activate(X)), activate(Y)) U12(tt, X) => U13(isNat(activate(X))) and(tt, X) => activate(X) isNat(n!6220!6220plus(X, Y)) => U11(and(isNatKind(activate(X)), n!6220!6220isNatKind(activate(Y))), activate(X), activate(Y)) isNat(n!6220!6220s(X)) => U21(isNatKind(activate(X)), activate(X)) plus(X, s(Y)) => U41(and(and(isNat(Y), n!6220!6220isNatKind(Y)), n!6220!6220and(n!6220!6220isNat(X), n!6220!6220isNatKind(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]): U13(tt) >? tt U21(tt, X) >? U22(isNat(activate(X))) U22(tt) >? tt U31(tt, X) >? activate(X) U41(tt, X, Y) >? s(plus(activate(Y), activate(X))) isNat(n!6220!62200) >? tt isNatKind(n!6220!62200) >? tt isNatKind(n!6220!6220plus(X, Y)) >? and(isNatKind(activate(X)), n!6220!6220isNatKind(activate(Y))) isNatKind(n!6220!6220s(X)) >? isNatKind(activate(X)) plus(X, 0) >? U31(and(isNat(X), n!6220!6220isNatKind(X)), X) 0 >? n!6220!62200 plus(X, Y) >? n!6220!6220plus(X, Y) isNatKind(X) >? n!6220!6220isNatKind(X) s(X) >? n!6220!6220s(X) and(X, Y) >? n!6220!6220and(X, Y) isNat(X) >? n!6220!6220isNat(X) activate(n!6220!62200) >? 0 activate(n!6220!6220plus(X, Y)) >? plus(activate(X), activate(Y)) activate(n!6220!6220isNatKind(X)) >? isNatKind(X) activate(n!6220!6220s(X)) >? s(activate(X)) activate(n!6220!6220and(X, Y)) >? and(activate(X), Y) activate(n!6220!6220isNat(X)) >? isNat(X) activate(X) >? X We orient these requirements with a polynomial interpretation in the natural numbers. The following interpretation satisfies the requirements: 0 = 1 U13 = \y0.3 + 3y0 U21 = \y0y1.3 + 3y0 + 3y1 U22 = \y0.y0 U31 = \y0y1.y0 + y1 U41 = \y0y1y2.3 + 3y0 + 3y1 + 3y2 activate = \y0.y0 and = \y0y1.y0 + y1 isNat = \y0.y0 isNatKind = \y0.y0 n!6220!62200 = 1 n!6220!6220and = \y0y1.y0 + y1 n!6220!6220isNat = \y0.y0 n!6220!6220isNatKind = \y0.y0 n!6220!6220plus = \y0y1.y1 + 3y0 n!6220!6220s = \y0.y0 plus = \y0y1.y1 + 3y0 s = \y0.y0 tt = 0 Using this interpretation, the requirements translate to: [[U13(tt)]] = 3 > 0 = [[tt]] [[U21(tt, _x0)]] = 3 + 3x0 > x0 = [[U22(isNat(activate(_x0)))]] [[U22(tt)]] = 0 >= 0 = [[tt]] [[U31(tt, _x0)]] = x0 >= x0 = [[activate(_x0)]] [[U41(tt, _x0, _x1)]] = 3 + 3x0 + 3x1 > x0 + 3x1 = [[s(plus(activate(_x1), activate(_x0)))]] [[isNat(n!6220!62200)]] = 1 > 0 = [[tt]] [[isNatKind(n!6220!62200)]] = 1 > 0 = [[tt]] [[isNatKind(n!6220!6220plus(_x0, _x1))]] = x1 + 3x0 >= x0 + x1 = [[and(isNatKind(activate(_x0)), n!6220!6220isNatKind(activate(_x1)))]] [[isNatKind(n!6220!6220s(_x0))]] = x0 >= x0 = [[isNatKind(activate(_x0))]] [[plus(_x0, 0)]] = 1 + 3x0 > 3x0 = [[U31(and(isNat(_x0), n!6220!6220isNatKind(_x0)), _x0)]] [[0]] = 1 >= 1 = [[n!6220!62200]] [[plus(_x0, _x1)]] = x1 + 3x0 >= x1 + 3x0 = [[n!6220!6220plus(_x0, _x1)]] [[isNatKind(_x0)]] = x0 >= x0 = [[n!6220!6220isNatKind(_x0)]] [[s(_x0)]] = x0 >= x0 = [[n!6220!6220s(_x0)]] [[and(_x0, _x1)]] = x0 + x1 >= x0 + x1 = [[n!6220!6220and(_x0, _x1)]] [[isNat(_x0)]] = x0 >= x0 = [[n!6220!6220isNat(_x0)]] [[activate(n!6220!62200)]] = 1 >= 1 = [[0]] [[activate(n!6220!6220plus(_x0, _x1))]] = x1 + 3x0 >= x1 + 3x0 = [[plus(activate(_x0), activate(_x1))]] [[activate(n!6220!6220isNatKind(_x0))]] = x0 >= x0 = [[isNatKind(_x0)]] [[activate(n!6220!6220s(_x0))]] = x0 >= x0 = [[s(activate(_x0))]] [[activate(n!6220!6220and(_x0, _x1))]] = x0 + x1 >= x0 + x1 = [[and(activate(_x0), _x1)]] [[activate(n!6220!6220isNat(_x0))]] = x0 >= x0 = [[isNat(_x0)]] [[activate(_x0)]] = x0 >= x0 = [[_x0]] We can thus remove the following rules: U13(tt) => tt U21(tt, X) => U22(isNat(activate(X))) U41(tt, X, Y) => s(plus(activate(Y), activate(X))) isNat(n!6220!62200) => tt isNatKind(n!6220!62200) => tt plus(X, 0) => U31(and(isNat(X), n!6220!6220isNatKind(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]): U22(tt) >? tt U31(tt, X) >? activate(X) isNatKind(n!6220!6220plus(X, Y)) >? and(isNatKind(activate(X)), n!6220!6220isNatKind(activate(Y))) isNatKind(n!6220!6220s(X)) >? isNatKind(activate(X)) 0 >? n!6220!62200 plus(X, Y) >? n!6220!6220plus(X, Y) isNatKind(X) >? n!6220!6220isNatKind(X) s(X) >? n!6220!6220s(X) and(X, Y) >? n!6220!6220and(X, Y) isNat(X) >? n!6220!6220isNat(X) activate(n!6220!62200) >? 0 activate(n!6220!6220plus(X, Y)) >? plus(activate(X), activate(Y)) activate(n!6220!6220isNatKind(X)) >? isNatKind(X) activate(n!6220!6220s(X)) >? s(activate(X)) activate(n!6220!6220and(X, Y)) >? and(activate(X), Y) activate(n!6220!6220isNat(X)) >? isNat(X) activate(X) >? X We orient these requirements with a polynomial interpretation in the natural numbers. The following interpretation satisfies the requirements: 0 = 0 U22 = \y0.3 + 3y0 U31 = \y0y1.3 + 3y0 + 3y1 activate = \y0.2y0 and = \y0y1.y0 + y1 isNat = \y0.2y0 isNatKind = \y0.y0 n!6220!62200 = 0 n!6220!6220and = \y0y1.y0 + y1 n!6220!6220isNat = \y0.y0 n!6220!6220isNatKind = \y0.y0 n!6220!6220plus = \y0y1.2 + 2y0 + 2y1 n!6220!6220s = \y0.2y0 plus = \y0y1.3 + 2y0 + 2y1 s = \y0.2y0 tt = 1 Using this interpretation, the requirements translate to: [[U22(tt)]] = 6 > 1 = [[tt]] [[U31(tt, _x0)]] = 6 + 3x0 > 2x0 = [[activate(_x0)]] [[isNatKind(n!6220!6220plus(_x0, _x1))]] = 2 + 2x0 + 2x1 > 2x0 + 2x1 = [[and(isNatKind(activate(_x0)), n!6220!6220isNatKind(activate(_x1)))]] [[isNatKind(n!6220!6220s(_x0))]] = 2x0 >= 2x0 = [[isNatKind(activate(_x0))]] [[0]] = 0 >= 0 = [[n!6220!62200]] [[plus(_x0, _x1)]] = 3 + 2x0 + 2x1 > 2 + 2x0 + 2x1 = [[n!6220!6220plus(_x0, _x1)]] [[isNatKind(_x0)]] = x0 >= x0 = [[n!6220!6220isNatKind(_x0)]] [[s(_x0)]] = 2x0 >= 2x0 = [[n!6220!6220s(_x0)]] [[and(_x0, _x1)]] = x0 + x1 >= x0 + x1 = [[n!6220!6220and(_x0, _x1)]] [[isNat(_x0)]] = 2x0 >= x0 = [[n!6220!6220isNat(_x0)]] [[activate(n!6220!62200)]] = 0 >= 0 = [[0]] [[activate(n!6220!6220plus(_x0, _x1))]] = 4 + 4x0 + 4x1 > 3 + 4x0 + 4x1 = [[plus(activate(_x0), activate(_x1))]] [[activate(n!6220!6220isNatKind(_x0))]] = 2x0 >= x0 = [[isNatKind(_x0)]] [[activate(n!6220!6220s(_x0))]] = 4x0 >= 4x0 = [[s(activate(_x0))]] [[activate(n!6220!6220and(_x0, _x1))]] = 2x0 + 2x1 >= x1 + 2x0 = [[and(activate(_x0), _x1)]] [[activate(n!6220!6220isNat(_x0))]] = 2x0 >= 2x0 = [[isNat(_x0)]] [[activate(_x0)]] = 2x0 >= x0 = [[_x0]] We can thus remove the following rules: U22(tt) => tt U31(tt, X) => activate(X) isNatKind(n!6220!6220plus(X, Y)) => and(isNatKind(activate(X)), n!6220!6220isNatKind(activate(Y))) plus(X, Y) => n!6220!6220plus(X, Y) activate(n!6220!6220plus(X, Y)) => plus(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]): isNatKind(n!6220!6220s(X)) >? isNatKind(activate(X)) 0 >? n!6220!62200 isNatKind(X) >? n!6220!6220isNatKind(X) s(X) >? n!6220!6220s(X) and(X, Y) >? n!6220!6220and(X, Y) isNat(X) >? n!6220!6220isNat(X) activate(n!6220!62200) >? 0 activate(n!6220!6220isNatKind(X)) >? isNatKind(X) activate(n!6220!6220s(X)) >? s(activate(X)) activate(n!6220!6220and(X, Y)) >? and(activate(X), Y) activate(n!6220!6220isNat(X)) >? isNat(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 and = \y0y1.y1 + 2y0 isNat = \y0.y0 isNatKind = \y0.y0 n!6220!62200 = 0 n!6220!6220and = \y0y1.y1 + 2y0 n!6220!6220isNat = \y0.y0 n!6220!6220isNatKind = \y0.y0 n!6220!6220s = \y0.1 + y0 s = \y0.1 + y0 Using this interpretation, the requirements translate to: [[isNatKind(n!6220!6220s(_x0))]] = 1 + x0 > x0 = [[isNatKind(activate(_x0))]] [[0]] = 0 >= 0 = [[n!6220!62200]] [[isNatKind(_x0)]] = x0 >= x0 = [[n!6220!6220isNatKind(_x0)]] [[s(_x0)]] = 1 + x0 >= 1 + x0 = [[n!6220!6220s(_x0)]] [[and(_x0, _x1)]] = x1 + 2x0 >= x1 + 2x0 = [[n!6220!6220and(_x0, _x1)]] [[isNat(_x0)]] = x0 >= x0 = [[n!6220!6220isNat(_x0)]] [[activate(n!6220!62200)]] = 0 >= 0 = [[0]] [[activate(n!6220!6220isNatKind(_x0))]] = x0 >= x0 = [[isNatKind(_x0)]] [[activate(n!6220!6220s(_x0))]] = 1 + x0 >= 1 + x0 = [[s(activate(_x0))]] [[activate(n!6220!6220and(_x0, _x1))]] = x1 + 2x0 >= x1 + 2x0 = [[and(activate(_x0), _x1)]] [[activate(n!6220!6220isNat(_x0))]] = x0 >= x0 = [[isNat(_x0)]] [[activate(_x0)]] = x0 >= x0 = [[_x0]] We can thus remove the following rules: isNatKind(n!6220!6220s(X)) => isNatKind(activate(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]): 0 >? n!6220!62200 isNatKind(X) >? n!6220!6220isNatKind(X) s(X) >? n!6220!6220s(X) and(X, Y) >? n!6220!6220and(X, Y) isNat(X) >? n!6220!6220isNat(X) activate(n!6220!62200) >? 0 activate(n!6220!6220isNatKind(X)) >? isNatKind(X) activate(n!6220!6220s(X)) >? s(activate(X)) activate(n!6220!6220and(X, Y)) >? and(activate(X), Y) activate(n!6220!6220isNat(X)) >? isNat(X) activate(X) >? X We orient these requirements with a polynomial interpretation in the natural numbers. The following interpretation satisfies the requirements: 0 = 2 activate = \y0.2y0 and = \y0y1.y0 + 2y1 isNat = \y0.2y0 isNatKind = \y0.2y0 n!6220!62200 = 2 n!6220!6220and = \y0y1.y0 + y1 n!6220!6220isNat = \y0.2y0 n!6220!6220isNatKind = \y0.2y0 n!6220!6220s = \y0.y0 s = \y0.y0 Using this interpretation, the requirements translate to: [[0]] = 2 >= 2 = [[n!6220!62200]] [[isNatKind(_x0)]] = 2x0 >= 2x0 = [[n!6220!6220isNatKind(_x0)]] [[s(_x0)]] = x0 >= x0 = [[n!6220!6220s(_x0)]] [[and(_x0, _x1)]] = x0 + 2x1 >= x0 + x1 = [[n!6220!6220and(_x0, _x1)]] [[isNat(_x0)]] = 2x0 >= 2x0 = [[n!6220!6220isNat(_x0)]] [[activate(n!6220!62200)]] = 4 > 2 = [[0]] [[activate(n!6220!6220isNatKind(_x0))]] = 4x0 >= 2x0 = [[isNatKind(_x0)]] [[activate(n!6220!6220s(_x0))]] = 2x0 >= 2x0 = [[s(activate(_x0))]] [[activate(n!6220!6220and(_x0, _x1))]] = 2x0 + 2x1 >= 2x0 + 2x1 = [[and(activate(_x0), _x1)]] [[activate(n!6220!6220isNat(_x0))]] = 4x0 >= 2x0 = [[isNat(_x0)]] [[activate(_x0)]] = 2x0 >= x0 = [[_x0]] We can thus remove the following rules: activate(n!6220!62200) => 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]): 0 >? n!6220!62200 isNatKind(X) >? n!6220!6220isNatKind(X) s(X) >? n!6220!6220s(X) and(X, Y) >? n!6220!6220and(X, Y) isNat(X) >? n!6220!6220isNat(X) activate(n!6220!6220isNatKind(X)) >? isNatKind(X) activate(n!6220!6220s(X)) >? s(activate(X)) activate(n!6220!6220and(X, Y)) >? and(activate(X), Y) activate(n!6220!6220isNat(X)) >? isNat(X) 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 and = \y0y1.y0 + y1 isNat = \y0.y0 isNatKind = \y0.2y0 n!6220!62200 = 0 n!6220!6220and = \y0y1.y0 + y1 n!6220!6220isNat = \y0.y0 n!6220!6220isNatKind = \y0.2y0 n!6220!6220s = \y0.y0 s = \y0.y0 Using this interpretation, the requirements translate to: [[0]] = 3 > 0 = [[n!6220!62200]] [[isNatKind(_x0)]] = 2x0 >= 2x0 = [[n!6220!6220isNatKind(_x0)]] [[s(_x0)]] = x0 >= x0 = [[n!6220!6220s(_x0)]] [[and(_x0, _x1)]] = x0 + x1 >= x0 + x1 = [[n!6220!6220and(_x0, _x1)]] [[isNat(_x0)]] = x0 >= x0 = [[n!6220!6220isNat(_x0)]] [[activate(n!6220!6220isNatKind(_x0))]] = 2x0 >= 2x0 = [[isNatKind(_x0)]] [[activate(n!6220!6220s(_x0))]] = x0 >= x0 = [[s(activate(_x0))]] [[activate(n!6220!6220and(_x0, _x1))]] = x0 + x1 >= x0 + x1 = [[and(activate(_x0), _x1)]] [[activate(n!6220!6220isNat(_x0))]] = x0 >= x0 = [[isNat(_x0)]] [[activate(_x0)]] = x0 >= x0 = [[_x0]] We can thus remove the following rules: 0 => n!6220!62200 We use rule removal, following [Kop12, Theorem 2.23]. This gives the following requirements (possibly using Theorems 2.25 and 2.26 in [Kop12]): isNatKind(X) >? n!6220!6220isNatKind(X) s(X) >? n!6220!6220s(X) and(X, Y) >? n!6220!6220and(X, Y) isNat(X) >? n!6220!6220isNat(X) activate(n!6220!6220isNatKind(X)) >? isNatKind(X) activate(n!6220!6220s(X)) >? s(activate(X)) activate(n!6220!6220and(X, Y)) >? and(activate(X), Y) activate(n!6220!6220isNat(X)) >? isNat(X) 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 and = \y0y1.3 + y0 + 2y1 isNat = \y0.y0 isNatKind = \y0.y0 n!6220!6220and = \y0y1.3 + y0 + 2y1 n!6220!6220isNat = \y0.y0 n!6220!6220isNatKind = \y0.y0 n!6220!6220s = \y0.y0 s = \y0.y0 Using this interpretation, the requirements translate to: [[isNatKind(_x0)]] = x0 >= x0 = [[n!6220!6220isNatKind(_x0)]] [[s(_x0)]] = x0 >= x0 = [[n!6220!6220s(_x0)]] [[and(_x0, _x1)]] = 3 + x0 + 2x1 >= 3 + x0 + 2x1 = [[n!6220!6220and(_x0, _x1)]] [[isNat(_x0)]] = x0 >= x0 = [[n!6220!6220isNat(_x0)]] [[activate(n!6220!6220isNatKind(_x0))]] = 1 + x0 > x0 = [[isNatKind(_x0)]] [[activate(n!6220!6220s(_x0))]] = 1 + x0 >= 1 + x0 = [[s(activate(_x0))]] [[activate(n!6220!6220and(_x0, _x1))]] = 4 + x0 + 2x1 >= 4 + x0 + 2x1 = [[and(activate(_x0), _x1)]] [[activate(n!6220!6220isNat(_x0))]] = 1 + x0 > x0 = [[isNat(_x0)]] [[activate(_x0)]] = 1 + x0 > x0 = [[_x0]] We can thus remove the following rules: activate(n!6220!6220isNatKind(X)) => isNatKind(X) activate(n!6220!6220isNat(X)) => isNat(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]): isNatKind(X) >? n!6220!6220isNatKind(X) s(X) >? n!6220!6220s(X) and(X, Y) >? n!6220!6220and(X, Y) isNat(X) >? n!6220!6220isNat(X) activate(n!6220!6220s(X)) >? s(activate(X)) activate(n!6220!6220and(X, Y)) >? and(activate(X), Y) We orient these requirements with a polynomial interpretation in the natural numbers. The following interpretation satisfies the requirements: activate = \y0.y0 and = \y0y1.y0 + 2y1 isNat = \y0.3 + y0 isNatKind = \y0.3 + y0 n!6220!6220and = \y0y1.y0 + 2y1 n!6220!6220isNat = \y0.y0 n!6220!6220isNatKind = \y0.y0 n!6220!6220s = \y0.2y0 s = \y0.2y0 Using this interpretation, the requirements translate to: [[isNatKind(_x0)]] = 3 + x0 > x0 = [[n!6220!6220isNatKind(_x0)]] [[s(_x0)]] = 2x0 >= 2x0 = [[n!6220!6220s(_x0)]] [[and(_x0, _x1)]] = x0 + 2x1 >= x0 + 2x1 = [[n!6220!6220and(_x0, _x1)]] [[isNat(_x0)]] = 3 + x0 > x0 = [[n!6220!6220isNat(_x0)]] [[activate(n!6220!6220s(_x0))]] = 2x0 >= 2x0 = [[s(activate(_x0))]] [[activate(n!6220!6220and(_x0, _x1))]] = x0 + 2x1 >= x0 + 2x1 = [[and(activate(_x0), _x1)]] We can thus remove the following rules: isNatKind(X) => n!6220!6220isNatKind(X) isNat(X) => n!6220!6220isNat(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]): s(X) >? n!6220!6220s(X) and(X, Y) >? n!6220!6220and(X, Y) activate(n!6220!6220s(X)) >? s(activate(X)) activate(n!6220!6220and(X, Y)) >? and(activate(X), Y) We orient these requirements with a polynomial interpretation in the natural numbers. The following interpretation satisfies the requirements: activate = \y0.2y0 and = \y0y1.1 + 2y0 + 2y1 n!6220!6220and = \y0y1.1 + y1 + 2y0 n!6220!6220s = \y0.2y0 s = \y0.2y0 Using this interpretation, the requirements translate to: [[s(_x0)]] = 2x0 >= 2x0 = [[n!6220!6220s(_x0)]] [[and(_x0, _x1)]] = 1 + 2x0 + 2x1 >= 1 + x1 + 2x0 = [[n!6220!6220and(_x0, _x1)]] [[activate(n!6220!6220s(_x0))]] = 4x0 >= 4x0 = [[s(activate(_x0))]] [[activate(n!6220!6220and(_x0, _x1))]] = 2 + 2x1 + 4x0 > 1 + 2x1 + 4x0 = [[and(activate(_x0), _x1)]] We can thus remove the following rules: activate(n!6220!6220and(X, Y)) => and(activate(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]): s(X) >? n!6220!6220s(X) and(X, Y) >? n!6220!6220and(X, Y) activate(n!6220!6220s(X)) >? s(activate(X)) We orient these requirements with a polynomial interpretation in the natural numbers. The following interpretation satisfies the requirements: activate = \y0.2y0 and = \y0y1.3 + y0 + y1 n!6220!6220and = \y0y1.y0 + y1 n!6220!6220s = \y0.1 + y0 s = \y0.2 + y0 Using this interpretation, the requirements translate to: [[s(_x0)]] = 2 + x0 > 1 + x0 = [[n!6220!6220s(_x0)]] [[and(_x0, _x1)]] = 3 + x0 + x1 > x0 + x1 = [[n!6220!6220and(_x0, _x1)]] [[activate(n!6220!6220s(_x0))]] = 2 + 2x0 >= 2 + 2x0 = [[s(activate(_x0))]] We can thus remove the following rules: s(X) => n!6220!6220s(X) and(X, Y) => n!6220!6220and(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]): activate(n!6220!6220s(X)) >? s(activate(X)) We orient these requirements with a polynomial interpretation in the natural numbers. The following interpretation satisfies the requirements: activate = \y0.3y0 n!6220!6220s = \y0.3 + 3y0 s = \y0.y0 Using this interpretation, the requirements translate to: [[activate(n!6220!6220s(_x0))]] = 9 + 9x0 > 3x0 = [[s(activate(_x0))]] We can thus remove the following rules: activate(n!6220!6220s(X)) => s(activate(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.