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