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