/export/starexec/sandbox/solver/bin/starexec_run_FirstOrder /export/starexec/sandbox/benchmark/theBenchmark.xml /export/starexec/sandbox/output/output_files -------------------------------------------------------------------------------- YES We consider the system theBenchmark. We are asked to determine termination of the following first-order TRS. 0 : [] --> o 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 active : [o] --> o and : [o * o] --> o isNat : [o] --> o isNatKind : [o] --> o mark : [o] --> o ok : [o] --> o plus : [o * o] --> o proper : [o] --> o s : [o] --> o top : [o] --> o tt : [] --> o x : [o * o] --> o active(U11(tt, X, Y)) => mark(U12(isNat(X), Y)) active(U12(tt, X)) => mark(U13(isNat(X))) active(U13(tt)) => mark(tt) active(U21(tt, X)) => mark(U22(isNat(X))) active(U22(tt)) => mark(tt) active(U31(tt, X, Y)) => mark(U32(isNat(X), Y)) active(U32(tt, X)) => mark(U33(isNat(X))) active(U33(tt)) => mark(tt) active(U41(tt, X)) => mark(X) active(U51(tt, X, Y)) => mark(s(plus(Y, X))) active(U61(tt)) => mark(0) active(U71(tt, X, Y)) => mark(plus(x(Y, X), Y)) active(and(tt, X)) => mark(X) active(isNat(0)) => mark(tt) active(isNat(plus(X, Y))) => mark(U11(and(isNatKind(X), isNatKind(Y)), X, Y)) active(isNat(s(X))) => mark(U21(isNatKind(X), X)) active(isNat(x(X, Y))) => mark(U31(and(isNatKind(X), isNatKind(Y)), X, Y)) active(isNatKind(0)) => mark(tt) active(isNatKind(plus(X, Y))) => mark(and(isNatKind(X), isNatKind(Y))) active(isNatKind(s(X))) => mark(isNatKind(X)) active(isNatKind(x(X, Y))) => mark(and(isNatKind(X), isNatKind(Y))) active(plus(X, 0)) => mark(U41(and(isNat(X), isNatKind(X)), X)) active(plus(X, s(Y))) => mark(U51(and(and(isNat(Y), isNatKind(Y)), and(isNat(X), isNatKind(X))), Y, X)) active(x(X, 0)) => mark(U61(and(isNat(X), isNatKind(X)))) active(x(X, s(Y))) => mark(U71(and(and(isNat(Y), isNatKind(Y)), and(isNat(X), isNatKind(X))), Y, X)) active(U11(X, Y, Z)) => U11(active(X), Y, Z) active(U12(X, Y)) => U12(active(X), Y) active(U13(X)) => U13(active(X)) active(U21(X, Y)) => U21(active(X), Y) active(U22(X)) => U22(active(X)) active(U31(X, Y, Z)) => U31(active(X), Y, Z) active(U32(X, Y)) => U32(active(X), Y) active(U33(X)) => U33(active(X)) active(U41(X, Y)) => U41(active(X), Y) active(U51(X, Y, Z)) => U51(active(X), Y, Z) active(s(X)) => s(active(X)) active(plus(X, Y)) => plus(active(X), Y) active(plus(X, Y)) => plus(X, active(Y)) active(U61(X)) => U61(active(X)) active(U71(X, Y, Z)) => U71(active(X), Y, Z) active(x(X, Y)) => x(active(X), Y) active(x(X, Y)) => x(X, active(Y)) active(and(X, Y)) => and(active(X), Y) U11(mark(X), Y, Z) => mark(U11(X, Y, Z)) U12(mark(X), Y) => mark(U12(X, Y)) U13(mark(X)) => mark(U13(X)) U21(mark(X), Y) => mark(U21(X, Y)) U22(mark(X)) => mark(U22(X)) U31(mark(X), Y, Z) => mark(U31(X, Y, Z)) U32(mark(X), Y) => mark(U32(X, Y)) U33(mark(X)) => mark(U33(X)) U41(mark(X), Y) => mark(U41(X, Y)) U51(mark(X), Y, Z) => mark(U51(X, Y, Z)) s(mark(X)) => mark(s(X)) plus(mark(X), Y) => mark(plus(X, Y)) plus(X, mark(Y)) => mark(plus(X, Y)) U61(mark(X)) => mark(U61(X)) U71(mark(X), Y, Z) => mark(U71(X, Y, Z)) x(mark(X), Y) => mark(x(X, Y)) x(X, mark(Y)) => mark(x(X, Y)) and(mark(X), Y) => mark(and(X, Y)) proper(U11(X, Y, Z)) => U11(proper(X), proper(Y), proper(Z)) proper(tt) => ok(tt) proper(U12(X, Y)) => U12(proper(X), proper(Y)) proper(isNat(X)) => isNat(proper(X)) proper(U13(X)) => U13(proper(X)) proper(U21(X, Y)) => U21(proper(X), proper(Y)) proper(U22(X)) => U22(proper(X)) proper(U31(X, Y, Z)) => U31(proper(X), proper(Y), proper(Z)) proper(U32(X, Y)) => U32(proper(X), proper(Y)) proper(U33(X)) => U33(proper(X)) proper(U41(X, Y)) => U41(proper(X), proper(Y)) proper(U51(X, Y, Z)) => U51(proper(X), proper(Y), proper(Z)) proper(s(X)) => s(proper(X)) proper(plus(X, Y)) => plus(proper(X), proper(Y)) proper(U61(X)) => U61(proper(X)) proper(0) => ok(0) proper(U71(X, Y, Z)) => U71(proper(X), proper(Y), proper(Z)) proper(x(X, Y)) => x(proper(X), proper(Y)) proper(and(X, Y)) => and(proper(X), proper(Y)) proper(isNatKind(X)) => isNatKind(proper(X)) U11(ok(X), ok(Y), ok(Z)) => ok(U11(X, Y, Z)) U12(ok(X), ok(Y)) => ok(U12(X, Y)) isNat(ok(X)) => ok(isNat(X)) U13(ok(X)) => ok(U13(X)) U21(ok(X), ok(Y)) => ok(U21(X, Y)) U22(ok(X)) => ok(U22(X)) U31(ok(X), ok(Y), ok(Z)) => ok(U31(X, Y, Z)) U32(ok(X), ok(Y)) => ok(U32(X, Y)) U33(ok(X)) => ok(U33(X)) U41(ok(X), ok(Y)) => ok(U41(X, Y)) U51(ok(X), ok(Y), ok(Z)) => ok(U51(X, Y, Z)) s(ok(X)) => ok(s(X)) plus(ok(X), ok(Y)) => ok(plus(X, Y)) U61(ok(X)) => ok(U61(X)) U71(ok(X), ok(Y), ok(Z)) => ok(U71(X, Y, Z)) x(ok(X), ok(Y)) => ok(x(X, Y)) and(ok(X), ok(Y)) => ok(and(X, Y)) isNatKind(ok(X)) => ok(isNatKind(X)) top(mark(X)) => top(proper(X)) top(ok(X)) => top(active(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]): active(U11(tt, X, Y)) >? mark(U12(isNat(X), Y)) active(U12(tt, X)) >? mark(U13(isNat(X))) active(U13(tt)) >? mark(tt) active(U21(tt, X)) >? mark(U22(isNat(X))) active(U22(tt)) >? mark(tt) active(U31(tt, X, Y)) >? mark(U32(isNat(X), Y)) active(U32(tt, X)) >? mark(U33(isNat(X))) active(U33(tt)) >? mark(tt) active(U41(tt, X)) >? mark(X) active(U51(tt, X, Y)) >? mark(s(plus(Y, X))) active(U61(tt)) >? mark(0) active(U71(tt, X, Y)) >? mark(plus(x(Y, X), Y)) active(and(tt, X)) >? mark(X) active(isNat(0)) >? mark(tt) active(isNat(plus(X, Y))) >? mark(U11(and(isNatKind(X), isNatKind(Y)), X, Y)) active(isNat(s(X))) >? mark(U21(isNatKind(X), X)) active(isNat(x(X, Y))) >? mark(U31(and(isNatKind(X), isNatKind(Y)), X, Y)) active(isNatKind(0)) >? mark(tt) active(isNatKind(plus(X, Y))) >? mark(and(isNatKind(X), isNatKind(Y))) active(isNatKind(s(X))) >? mark(isNatKind(X)) active(isNatKind(x(X, Y))) >? mark(and(isNatKind(X), isNatKind(Y))) active(plus(X, 0)) >? mark(U41(and(isNat(X), isNatKind(X)), X)) active(plus(X, s(Y))) >? mark(U51(and(and(isNat(Y), isNatKind(Y)), and(isNat(X), isNatKind(X))), Y, X)) active(x(X, 0)) >? mark(U61(and(isNat(X), isNatKind(X)))) active(x(X, s(Y))) >? mark(U71(and(and(isNat(Y), isNatKind(Y)), and(isNat(X), isNatKind(X))), Y, X)) active(U11(X, Y, Z)) >? U11(active(X), Y, Z) active(U12(X, Y)) >? U12(active(X), Y) active(U13(X)) >? U13(active(X)) active(U21(X, Y)) >? U21(active(X), Y) active(U22(X)) >? U22(active(X)) active(U31(X, Y, Z)) >? U31(active(X), Y, Z) active(U32(X, Y)) >? U32(active(X), Y) active(U33(X)) >? U33(active(X)) active(U41(X, Y)) >? U41(active(X), Y) active(U51(X, Y, Z)) >? U51(active(X), Y, Z) active(s(X)) >? s(active(X)) active(plus(X, Y)) >? plus(active(X), Y) active(plus(X, Y)) >? plus(X, active(Y)) active(U61(X)) >? U61(active(X)) active(U71(X, Y, Z)) >? U71(active(X), Y, Z) active(x(X, Y)) >? x(active(X), Y) active(x(X, Y)) >? x(X, active(Y)) active(and(X, Y)) >? and(active(X), Y) U11(mark(X), Y, Z) >? mark(U11(X, Y, Z)) U12(mark(X), Y) >? mark(U12(X, Y)) U13(mark(X)) >? mark(U13(X)) U21(mark(X), Y) >? mark(U21(X, Y)) U22(mark(X)) >? mark(U22(X)) U31(mark(X), Y, Z) >? mark(U31(X, Y, Z)) U32(mark(X), Y) >? mark(U32(X, Y)) U33(mark(X)) >? mark(U33(X)) U41(mark(X), Y) >? mark(U41(X, Y)) U51(mark(X), Y, Z) >? mark(U51(X, Y, Z)) s(mark(X)) >? mark(s(X)) plus(mark(X), Y) >? mark(plus(X, Y)) plus(X, mark(Y)) >? mark(plus(X, Y)) U61(mark(X)) >? mark(U61(X)) U71(mark(X), Y, Z) >? mark(U71(X, Y, Z)) x(mark(X), Y) >? mark(x(X, Y)) x(X, mark(Y)) >? mark(x(X, Y)) and(mark(X), Y) >? mark(and(X, Y)) proper(U11(X, Y, Z)) >? U11(proper(X), proper(Y), proper(Z)) proper(tt) >? ok(tt) proper(U12(X, Y)) >? U12(proper(X), proper(Y)) proper(isNat(X)) >? isNat(proper(X)) proper(U13(X)) >? U13(proper(X)) proper(U21(X, Y)) >? U21(proper(X), proper(Y)) proper(U22(X)) >? U22(proper(X)) proper(U31(X, Y, Z)) >? U31(proper(X), proper(Y), proper(Z)) proper(U32(X, Y)) >? U32(proper(X), proper(Y)) proper(U33(X)) >? U33(proper(X)) proper(U41(X, Y)) >? U41(proper(X), proper(Y)) proper(U51(X, Y, Z)) >? U51(proper(X), proper(Y), proper(Z)) proper(s(X)) >? s(proper(X)) proper(plus(X, Y)) >? plus(proper(X), proper(Y)) proper(U61(X)) >? U61(proper(X)) proper(0) >? ok(0) proper(U71(X, Y, Z)) >? U71(proper(X), proper(Y), proper(Z)) proper(x(X, Y)) >? x(proper(X), proper(Y)) proper(and(X, Y)) >? and(proper(X), proper(Y)) proper(isNatKind(X)) >? isNatKind(proper(X)) U11(ok(X), ok(Y), ok(Z)) >? ok(U11(X, Y, Z)) U12(ok(X), ok(Y)) >? ok(U12(X, Y)) isNat(ok(X)) >? ok(isNat(X)) U13(ok(X)) >? ok(U13(X)) U21(ok(X), ok(Y)) >? ok(U21(X, Y)) U22(ok(X)) >? ok(U22(X)) U31(ok(X), ok(Y), ok(Z)) >? ok(U31(X, Y, Z)) U32(ok(X), ok(Y)) >? ok(U32(X, Y)) U33(ok(X)) >? ok(U33(X)) U41(ok(X), ok(Y)) >? ok(U41(X, Y)) U51(ok(X), ok(Y), ok(Z)) >? ok(U51(X, Y, Z)) s(ok(X)) >? ok(s(X)) plus(ok(X), ok(Y)) >? ok(plus(X, Y)) U61(ok(X)) >? ok(U61(X)) U71(ok(X), ok(Y), ok(Z)) >? ok(U71(X, Y, Z)) x(ok(X), ok(Y)) >? ok(x(X, Y)) and(ok(X), ok(Y)) >? ok(and(X, Y)) isNatKind(ok(X)) >? ok(isNatKind(X)) top(mark(X)) >? top(proper(X)) top(ok(X)) >? top(active(X)) about to try horpo We use a recursive path ordering as defined in [Kop12, Chapter 5]. Argument functions: [[U13(x_1)]] = x_1 [[U22(x_1)]] = x_1 [[U51(x_1, x_2, x_3)]] = U51(x_3, x_2, x_1) [[U71(x_1, x_2, x_3)]] = U71(x_2, x_3, x_1) [[active(x_1)]] = x_1 [[mark(x_1)]] = x_1 [[ok(x_1)]] = x_1 [[proper(x_1)]] = x_1 [[x(x_1, x_2)]] = x(x_2, x_1) We choose Lex = {U51, U71, plus, x} and Mul = {0, U11, U12, U21, U31, U32, U33, U41, U61, and, isNat, isNatKind, s, top, tt}, and the following precedence: top > U71 = x > U31 > U61 > 0 > U51 = plus > U11 > U12 > U32 > U33 > U41 > and > s > isNatKind > U21 > isNat > tt Taking the argument function into account, and fixing the greater / greater equal choices, the constraints can be denoted as follows: U11(tt, X, Y) >= U12(isNat(X), Y) U12(tt, X) >= isNat(X) tt >= tt U21(tt, X) >= isNat(X) tt >= tt U31(tt, X, Y) >= U32(isNat(X), Y) U32(tt, X) >= U33(isNat(X)) U33(tt) > tt U41(tt, X) > X U51(tt, X, Y) >= s(plus(Y, X)) U61(tt) >= 0 U71(tt, X, Y) >= plus(x(Y, X), Y) and(tt, X) >= X isNat(0) >= tt isNat(plus(X, Y)) >= U11(and(isNatKind(X), isNatKind(Y)), X, Y) isNat(s(X)) >= U21(isNatKind(X), X) isNat(x(X, Y)) > U31(and(isNatKind(X), isNatKind(Y)), X, Y) isNatKind(0) >= tt isNatKind(plus(X, Y)) > and(isNatKind(X), isNatKind(Y)) isNatKind(s(X)) > isNatKind(X) isNatKind(x(X, Y)) >= and(isNatKind(X), isNatKind(Y)) plus(X, 0) >= U41(and(isNat(X), isNatKind(X)), X) plus(X, s(Y)) >= U51(and(and(isNat(Y), isNatKind(Y)), and(isNat(X), isNatKind(X))), Y, X) x(X, 0) >= U61(and(isNat(X), isNatKind(X))) x(X, s(Y)) >= U71(and(and(isNat(Y), isNatKind(Y)), and(isNat(X), isNatKind(X))), Y, X) U11(X, Y, Z) >= U11(X, Y, Z) U12(X, Y) >= U12(X, Y) X >= X U21(X, Y) >= U21(X, Y) X >= X U31(X, Y, Z) >= U31(X, Y, Z) U32(X, Y) >= U32(X, Y) U33(X) >= U33(X) U41(X, Y) >= U41(X, Y) U51(X, Y, Z) >= U51(X, Y, Z) s(X) >= s(X) plus(X, Y) >= plus(X, Y) plus(X, Y) >= plus(X, Y) U61(X) >= U61(X) U71(X, Y, Z) >= U71(X, Y, Z) x(X, Y) >= x(X, Y) x(X, Y) >= x(X, Y) and(X, Y) >= and(X, Y) U11(X, Y, Z) >= U11(X, Y, Z) U12(X, Y) >= U12(X, Y) X >= X U21(X, Y) >= U21(X, Y) X >= X U31(X, Y, Z) >= U31(X, Y, Z) U32(X, Y) >= U32(X, Y) U33(X) >= U33(X) U41(X, Y) >= U41(X, Y) U51(X, Y, Z) >= U51(X, Y, Z) s(X) >= s(X) plus(X, Y) >= plus(X, Y) plus(X, Y) >= plus(X, Y) U61(X) >= U61(X) U71(X, Y, Z) >= U71(X, Y, Z) x(X, Y) >= x(X, Y) x(X, Y) >= x(X, Y) and(X, Y) >= and(X, Y) U11(X, Y, Z) >= U11(X, Y, Z) tt >= tt U12(X, Y) >= U12(X, Y) isNat(X) >= isNat(X) X >= X U21(X, Y) >= U21(X, Y) X >= X U31(X, Y, Z) >= U31(X, Y, Z) U32(X, Y) >= U32(X, Y) U33(X) >= U33(X) U41(X, Y) >= U41(X, Y) U51(X, Y, Z) >= U51(X, Y, Z) s(X) >= s(X) plus(X, Y) >= plus(X, Y) U61(X) >= U61(X) 0 >= 0 U71(X, Y, Z) >= U71(X, Y, Z) x(X, Y) >= x(X, Y) and(X, Y) >= and(X, Y) isNatKind(X) >= isNatKind(X) U11(X, Y, Z) >= U11(X, Y, Z) U12(X, Y) >= U12(X, Y) isNat(X) >= isNat(X) X >= X U21(X, Y) >= U21(X, Y) X >= X U31(X, Y, Z) >= U31(X, Y, Z) U32(X, Y) >= U32(X, Y) U33(X) >= U33(X) U41(X, Y) >= U41(X, Y) U51(X, Y, Z) >= U51(X, Y, Z) s(X) >= s(X) plus(X, Y) >= plus(X, Y) U61(X) >= U61(X) U71(X, Y, Z) >= U71(X, Y, Z) x(X, Y) >= x(X, Y) and(X, Y) >= and(X, Y) isNatKind(X) >= isNatKind(X) top(X) >= top(X) top(X) >= top(X) With these choices, we have: 1] U11(tt, X, Y) >= U12(isNat(X), Y) because [2], by (Star) 2] U11*(tt, X, Y) >= U12(isNat(X), Y) because U11 > U12, [3] and [6], by (Copy) 3] U11*(tt, X, Y) >= isNat(X) because U11 > isNat and [4], by (Copy) 4] U11*(tt, X, Y) >= X because [5], by (Select) 5] X >= X by (Meta) 6] U11*(tt, X, Y) >= Y because [7], by (Select) 7] Y >= Y by (Meta) 8] U12(tt, X) >= isNat(X) because [9], by (Star) 9] U12*(tt, X) >= isNat(X) because U12 > isNat and [10], by (Copy) 10] U12*(tt, X) >= X because [7], by (Select) 11] tt >= tt by (Fun) 12] U21(tt, X) >= isNat(X) because [13], by (Star) 13] U21*(tt, X) >= isNat(X) because U21 > isNat and [14], by (Copy) 14] U21*(tt, X) >= X because [5], by (Select) 15] tt >= tt by (Fun) 16] U31(tt, X, Y) >= U32(isNat(X), Y) because [17], by (Star) 17] U31*(tt, X, Y) >= U32(isNat(X), Y) because U31 > U32, [18] and [20], by (Copy) 18] U31*(tt, X, Y) >= isNat(X) because U31 > isNat and [19], by (Copy) 19] U31*(tt, X, Y) >= X because [5], by (Select) 20] U31*(tt, X, Y) >= Y because [7], by (Select) 21] U32(tt, X) >= U33(isNat(X)) because [22], by (Star) 22] U32*(tt, X) >= U33(isNat(X)) because U32 > U33 and [23], by (Copy) 23] U32*(tt, X) >= isNat(X) because U32 > isNat and [24], by (Copy) 24] U32*(tt, X) >= X because [7], by (Select) 25] U33(tt) > tt because [26], by definition 26] U33*(tt) >= tt because U33 > tt, by (Copy) 27] U41(tt, X) > X because [28], by definition 28] U41*(tt, X) >= X because [29], by (Select) 29] X >= X by (Meta) 30] U51(tt, X, Y) >= s(plus(Y, X)) because [31], by (Star) 31] U51*(tt, X, Y) >= s(plus(Y, X)) because U51 > s and [32], by (Copy) 32] U51*(tt, X, Y) >= plus(Y, X) because U51 = plus, [33], [34], [35] and [36], by (Stat) 33] X >= X by (Meta) 34] Y >= Y by (Meta) 35] U51*(tt, X, Y) >= Y because [34], by (Select) 36] U51*(tt, X, Y) >= X because [33], by (Select) 37] U61(tt) >= 0 because [38], by (Star) 38] U61*(tt) >= 0 because U61 > 0, by (Copy) 39] U71(tt, X, Y) >= plus(x(Y, X), Y) because [40], by (Star) 40] U71*(tt, X, Y) >= plus(x(Y, X), Y) because U71 > plus, [41] and [42], by (Copy) 41] U71*(tt, X, Y) >= x(Y, X) because U71 = x, [33], [34], [42] and [43], by (Stat) 42] U71*(tt, X, Y) >= Y because [34], by (Select) 43] U71*(tt, X, Y) >= X because [33], by (Select) 44] and(tt, X) >= X because [45], by (Star) 45] and*(tt, X) >= X because [46], by (Select) 46] X >= X by (Meta) 47] isNat(0) >= tt because [48], by (Star) 48] isNat*(0) >= tt because isNat > tt, by (Copy) 49] isNat(plus(X, Y)) >= U11(and(isNatKind(X), isNatKind(Y)), X, Y) because [50], by (Star) 50] isNat*(plus(X, Y)) >= U11(and(isNatKind(X), isNatKind(Y)), X, Y) because [51], by (Select) 51] plus(X, Y) >= U11(and(isNatKind(X), isNatKind(Y)), X, Y) because [52], by (Star) 52] plus*(X, Y) >= U11(and(isNatKind(X), isNatKind(Y)), X, Y) because plus > U11, [53], [55] and [57], by (Copy) 53] plus*(X, Y) >= and(isNatKind(X), isNatKind(Y)) because plus > and, [54] and [56], by (Copy) 54] plus*(X, Y) >= isNatKind(X) because plus > isNatKind and [55], by (Copy) 55] plus*(X, Y) >= X because [5], by (Select) 56] plus*(X, Y) >= isNatKind(Y) because plus > isNatKind and [57], by (Copy) 57] plus*(X, Y) >= Y because [7], by (Select) 58] isNat(s(X)) >= U21(isNatKind(X), X) because [59], by (Star) 59] isNat*(s(X)) >= U21(isNatKind(X), X) because [60], by (Select) 60] s(X) >= U21(isNatKind(X), X) because [61], by (Star) 61] s*(X) >= U21(isNatKind(X), X) because s > U21, [62] and [63], by (Copy) 62] s*(X) >= isNatKind(X) because s > isNatKind and [63], by (Copy) 63] s*(X) >= X because [5], by (Select) 64] isNat(x(X, Y)) > U31(and(isNatKind(X), isNatKind(Y)), X, Y) because [65], by definition 65] isNat*(x(X, Y)) >= U31(and(isNatKind(X), isNatKind(Y)), X, Y) because [66], by (Select) 66] x(X, Y) >= U31(and(isNatKind(X), isNatKind(Y)), X, Y) because [67], by (Star) 67] x*(X, Y) >= U31(and(isNatKind(X), isNatKind(Y)), X, Y) because x > U31, [68], [70] and [72], by (Copy) 68] x*(X, Y) >= and(isNatKind(X), isNatKind(Y)) because x > and, [69] and [71], by (Copy) 69] x*(X, Y) >= isNatKind(X) because x > isNatKind and [70], by (Copy) 70] x*(X, Y) >= X because [5], by (Select) 71] x*(X, Y) >= isNatKind(Y) because x > isNatKind and [72], by (Copy) 72] x*(X, Y) >= Y because [7], by (Select) 73] isNatKind(0) >= tt because [74], by (Star) 74] isNatKind*(0) >= tt because isNatKind > tt, by (Copy) 75] isNatKind(plus(X, Y)) > and(isNatKind(X), isNatKind(Y)) because [76], by definition 76] isNatKind*(plus(X, Y)) >= and(isNatKind(X), isNatKind(Y)) because [77], by (Select) 77] plus(X, Y) >= and(isNatKind(X), isNatKind(Y)) because [53], by (Star) 78] isNatKind(s(X)) > isNatKind(X) because [79], by definition 79] isNatKind*(s(X)) >= isNatKind(X) because isNatKind in Mul and [80], by (Stat) 80] s(X) > X because [63], by definition 81] isNatKind(x(X, Y)) >= and(isNatKind(X), isNatKind(Y)) because [82], by (Star) 82] isNatKind*(x(X, Y)) >= and(isNatKind(X), isNatKind(Y)) because [83], by (Select) 83] x(X, Y) >= and(isNatKind(X), isNatKind(Y)) because [68], by (Star) 84] plus(X, 0) >= U41(and(isNat(X), isNatKind(X)), X) because [85], by (Star) 85] plus*(X, 0) >= U41(and(isNat(X), isNatKind(X)), X) because plus > U41, [86] and [88], by (Copy) 86] plus*(X, 0) >= and(isNat(X), isNatKind(X)) because plus > and, [87] and [89], by (Copy) 87] plus*(X, 0) >= isNat(X) because plus > isNat and [88], by (Copy) 88] plus*(X, 0) >= X because [34], by (Select) 89] plus*(X, 0) >= isNatKind(X) because plus > isNatKind and [88], by (Copy) 90] plus(X, s(Y)) >= U51(and(and(isNat(Y), isNatKind(Y)), and(isNat(X), isNatKind(X))), Y, X) because [91], by (Star) 91] plus*(X, s(Y)) >= U51(and(and(isNat(Y), isNatKind(Y)), and(isNat(X), isNatKind(X))), Y, X) because plus = U51, [34], [92], [94], [100] and [104], by (Stat) 92] s(Y) > Y because [93], by definition 93] s*(Y) >= Y because [33], by (Select) 94] plus*(X, s(Y)) >= and(and(isNat(Y), isNatKind(Y)), and(isNat(X), isNatKind(X))) because plus > and, [95] and [102], by (Copy) 95] plus*(X, s(Y)) >= and(isNat(Y), isNatKind(Y)) because plus > and, [96] and [99], by (Copy) 96] plus*(X, s(Y)) >= isNat(Y) because [97], by (Select) 97] s(Y) >= isNat(Y) because [98], by (Star) 98] s*(Y) >= isNat(Y) because s > isNat and [93], by (Copy) 99] plus*(X, s(Y)) >= isNatKind(Y) because plus > isNatKind and [100], by (Copy) 100] plus*(X, s(Y)) >= Y because [101], by (Select) 101] s(Y) >= Y because [93], by (Star) 102] plus*(X, s(Y)) >= and(isNat(X), isNatKind(X)) because plus > and, [103] and [105], by (Copy) 103] plus*(X, s(Y)) >= isNat(X) because plus > isNat and [104], by (Copy) 104] plus*(X, s(Y)) >= X because [34], by (Select) 105] plus*(X, s(Y)) >= isNatKind(X) because plus > isNatKind and [104], by (Copy) 106] x(X, 0) >= U61(and(isNat(X), isNatKind(X))) because [107], by (Star) 107] x*(X, 0) >= U61(and(isNat(X), isNatKind(X))) because x > U61 and [108], by (Copy) 108] x*(X, 0) >= and(isNat(X), isNatKind(X)) because x > and, [109] and [111], by (Copy) 109] x*(X, 0) >= isNat(X) because x > isNat and [110], by (Copy) 110] x*(X, 0) >= X because [34], by (Select) 111] x*(X, 0) >= isNatKind(X) because x > isNatKind and [110], by (Copy) 112] x(X, s(Y)) >= U71(and(and(isNat(Y), isNatKind(Y)), and(isNat(X), isNatKind(X))), Y, X) because [113], by (Star) 113] x*(X, s(Y)) >= U71(and(and(isNat(Y), isNatKind(Y)), and(isNat(X), isNatKind(X))), Y, X) because x = U71, [92], [114], [118] and [121], by (Stat) 114] x*(X, s(Y)) >= and(and(isNat(Y), isNatKind(Y)), and(isNat(X), isNatKind(X))) because x > and, [115] and [119], by (Copy) 115] x*(X, s(Y)) >= and(isNat(Y), isNatKind(Y)) because x > and, [116] and [117], by (Copy) 116] x*(X, s(Y)) >= isNat(Y) because [97], by (Select) 117] x*(X, s(Y)) >= isNatKind(Y) because x > isNatKind and [118], by (Copy) 118] x*(X, s(Y)) >= Y because [101], by (Select) 119] x*(X, s(Y)) >= and(isNat(X), isNatKind(X)) because x > and, [120] and [122], by (Copy) 120] x*(X, s(Y)) >= isNat(X) because x > isNat and [121], by (Copy) 121] x*(X, s(Y)) >= X because [34], by (Select) 122] x*(X, s(Y)) >= isNatKind(X) because x > isNatKind and [121], by (Copy) 123] U11(X, Y, Z) >= U11(X, Y, Z) because U11 in Mul, [124], [125] and [126], by (Fun) 124] X >= X by (Meta) 125] Y >= Y by (Meta) 126] Z >= Z by (Meta) 127] U12(X, Y) >= U12(X, Y) because U12 in Mul, [124] and [125], by (Fun) 128] X >= X by (Meta) 129] U21(X, Y) >= U21(X, Y) because U21 in Mul, [124] and [125], by (Fun) 130] X >= X by (Meta) 131] U31(X, Y, Z) >= U31(X, Y, Z) because U31 in Mul, [124], [125] and [126], by (Fun) 132] U32(X, Y) >= U32(X, Y) because U32 in Mul, [124] and [125], by (Fun) 133] U33(X) >= U33(X) because U33 in Mul and [134], by (Fun) 134] X >= X by (Meta) 135] U41(X, Y) >= U41(X, Y) because U41 in Mul, [124] and [125], by (Fun) 136] U51(X, Y, Z) >= U51(X, Y, Z) because [124], [125] and [126], by (Fun) 137] s(X) >= s(X) because s in Mul and [134], by (Fun) 138] plus(X, Y) >= plus(X, Y) because [124] and [125], by (Fun) 139] plus(X, Y) >= plus(X, Y) because [124] and [140], by (Fun) 140] Y >= Y by (Meta) 141] U61(X) >= U61(X) because U61 in Mul and [134], by (Fun) 142] U71(X, Y, Z) >= U71(X, Y, Z) because [124], [140] and [126], by (Fun) 143] x(X, Y) >= x(X, Y) because [124] and [140], by (Fun) 144] x(X, Y) >= x(X, Y) because [124] and [140], by (Fun) 145] and(X, Y) >= and(X, Y) because and in Mul, [124] and [140], by (Fun) 146] U11(X, Y, Z) >= U11(X, Y, Z) because U11 in Mul, [147], [140] and [126], by (Fun) 147] X >= X by (Meta) 148] U12(X, Y) >= U12(X, Y) because U12 in Mul, [147] and [140], by (Fun) 149] X >= X by (Meta) 150] U21(X, Y) >= U21(X, Y) because U21 in Mul, [147] and [140], by (Fun) 151] X >= X by (Meta) 152] U31(X, Y, Z) >= U31(X, Y, Z) because U31 in Mul, [147], [140] and [126], by (Fun) 153] U32(X, Y) >= U32(X, Y) because U32 in Mul, [147] and [140], by (Fun) 154] U33(X) >= U33(X) because U33 in Mul and [155], by (Fun) 155] X >= X by (Meta) 156] U41(X, Y) >= U41(X, Y) because U41 in Mul, [147] and [140], by (Fun) 157] U51(X, Y, Z) >= U51(X, Y, Z) because [147], [140] and [126], by (Fun) 158] s(X) >= s(X) because s in Mul and [155], by (Fun) 159] plus(X, Y) >= plus(X, Y) because [147] and [140], by (Fun) 160] plus(X, Y) >= plus(X, Y) because [124] and [161], by (Fun) 161] Y >= Y by (Meta) 162] U61(X) >= U61(X) because U61 in Mul and [155], by (Fun) 163] U71(X, Y, Z) >= U71(X, Y, Z) because [147], [140] and [126], by (Fun) 164] x(X, Y) >= x(X, Y) because [147] and [140], by (Fun) 165] x(X, Y) >= x(X, Y) because [124] and [161], by (Fun) 166] and(X, Y) >= and(X, Y) because and in Mul, [147] and [140], by (Fun) 167] U11(X, Y, Z) >= U11(X, Y, Z) because U11 in Mul, [168], [169] and [170], by (Fun) 168] X >= X by (Meta) 169] Y >= Y by (Meta) 170] Z >= Z by (Meta) 171] tt >= tt by (Fun) 172] U12(X, Y) >= U12(X, Y) because U12 in Mul, [168] and [169], by (Fun) 173] isNat(X) >= isNat(X) because isNat in Mul and [174], by (Fun) 174] X >= X by (Meta) 175] X >= X by (Meta) 176] U21(X, Y) >= U21(X, Y) because U21 in Mul, [168] and [169], by (Fun) 177] X >= X by (Meta) 178] U31(X, Y, Z) >= U31(X, Y, Z) because U31 in Mul, [168], [169] and [170], by (Fun) 179] U32(X, Y) >= U32(X, Y) because U32 in Mul, [168] and [169], by (Fun) 180] U33(X) >= U33(X) because U33 in Mul and [174], by (Fun) 181] U41(X, Y) >= U41(X, Y) because U41 in Mul, [168] and [169], by (Fun) 182] U51(X, Y, Z) >= U51(X, Y, Z) because [168], [169] and [170], by (Fun) 183] s(X) >= s(X) because s in Mul and [174], by (Fun) 184] plus(X, Y) >= plus(X, Y) because [168] and [169], by (Fun) 185] U61(X) >= U61(X) because U61 in Mul and [174], by (Fun) 186] 0 >= 0 by (Fun) 187] U71(X, Y, Z) >= U71(X, Y, Z) because [168], [169] and [170], by (Fun) 188] x(X, Y) >= x(X, Y) because [168] and [169], by (Fun) 189] and(X, Y) >= and(X, Y) because and in Mul, [168] and [169], by (Fun) 190] isNatKind(X) >= isNatKind(X) because isNatKind in Mul and [174], by (Fun) 191] U11(X, Y, Z) >= U11(X, Y, Z) because U11 in Mul, [192], [193] and [194], by (Fun) 192] X >= X by (Meta) 193] Y >= Y by (Meta) 194] Z >= Z by (Meta) 195] U12(X, Y) >= U12(X, Y) because U12 in Mul, [192] and [193], by (Fun) 196] isNat(X) >= isNat(X) because isNat in Mul and [197], by (Fun) 197] X >= X by (Meta) 198] X >= X by (Meta) 199] U21(X, Y) >= U21(X, Y) because U21 in Mul, [192] and [193], by (Fun) 200] X >= X by (Meta) 201] U31(X, Y, Z) >= U31(X, Y, Z) because U31 in Mul, [192], [193] and [194], by (Fun) 202] U32(X, Y) >= U32(X, Y) because U32 in Mul, [192] and [193], by (Fun) 203] U33(X) >= U33(X) because U33 in Mul and [197], by (Fun) 204] U41(X, Y) >= U41(X, Y) because U41 in Mul, [192] and [193], by (Fun) 205] U51(X, Y, Z) >= U51(X, Y, Z) because [192], [193] and [194], by (Fun) 206] s(X) >= s(X) because s in Mul and [197], by (Fun) 207] plus(X, Y) >= plus(X, Y) because [192] and [193], by (Fun) 208] U61(X) >= U61(X) because U61 in Mul and [197], by (Fun) 209] U71(X, Y, Z) >= U71(X, Y, Z) because [192], [193] and [194], by (Fun) 210] x(X, Y) >= x(X, Y) because [192] and [193], by (Fun) 211] and(X, Y) >= and(X, Y) because and in Mul, [192] and [193], by (Fun) 212] isNatKind(X) >= isNatKind(X) because isNatKind in Mul and [197], by (Fun) 213] top(X) >= top(X) because top in Mul and [214], by (Fun) 214] X >= X by (Meta) 215] top(X) >= top(X) because top in Mul and [216], by (Fun) 216] X >= X by (Meta) We can thus remove the following rules: active(U33(tt)) => mark(tt) active(U41(tt, X)) => mark(X) active(isNat(x(X, Y))) => mark(U31(and(isNatKind(X), isNatKind(Y)), X, Y)) active(isNatKind(plus(X, Y))) => mark(and(isNatKind(X), isNatKind(Y))) active(isNatKind(s(X))) => mark(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]): active(U11(tt, X, Y)) >? mark(U12(isNat(X), Y)) active(U12(tt, X)) >? mark(U13(isNat(X))) active(U13(tt)) >? mark(tt) active(U21(tt, X)) >? mark(U22(isNat(X))) active(U22(tt)) >? mark(tt) active(U31(tt, X, Y)) >? mark(U32(isNat(X), Y)) active(U32(tt, X)) >? mark(U33(isNat(X))) active(U51(tt, X, Y)) >? mark(s(plus(Y, X))) active(U61(tt)) >? mark(0) active(U71(tt, X, Y)) >? mark(plus(x(Y, X), Y)) active(and(tt, X)) >? mark(X) active(isNat(0)) >? mark(tt) active(isNat(plus(X, Y))) >? mark(U11(and(isNatKind(X), isNatKind(Y)), X, Y)) active(isNat(s(X))) >? mark(U21(isNatKind(X), X)) active(isNatKind(0)) >? mark(tt) active(isNatKind(x(X, Y))) >? mark(and(isNatKind(X), isNatKind(Y))) active(plus(X, 0)) >? mark(U41(and(isNat(X), isNatKind(X)), X)) active(plus(X, s(Y))) >? mark(U51(and(and(isNat(Y), isNatKind(Y)), and(isNat(X), isNatKind(X))), Y, X)) active(x(X, 0)) >? mark(U61(and(isNat(X), isNatKind(X)))) active(x(X, s(Y))) >? mark(U71(and(and(isNat(Y), isNatKind(Y)), and(isNat(X), isNatKind(X))), Y, X)) active(U11(X, Y, Z)) >? U11(active(X), Y, Z) active(U12(X, Y)) >? U12(active(X), Y) active(U13(X)) >? U13(active(X)) active(U21(X, Y)) >? U21(active(X), Y) active(U22(X)) >? U22(active(X)) active(U31(X, Y, Z)) >? U31(active(X), Y, Z) active(U32(X, Y)) >? U32(active(X), Y) active(U33(X)) >? U33(active(X)) active(U41(X, Y)) >? U41(active(X), Y) active(U51(X, Y, Z)) >? U51(active(X), Y, Z) active(s(X)) >? s(active(X)) active(plus(X, Y)) >? plus(active(X), Y) active(plus(X, Y)) >? plus(X, active(Y)) active(U61(X)) >? U61(active(X)) active(U71(X, Y, Z)) >? U71(active(X), Y, Z) active(x(X, Y)) >? x(active(X), Y) active(x(X, Y)) >? x(X, active(Y)) active(and(X, Y)) >? and(active(X), Y) U11(mark(X), Y, Z) >? mark(U11(X, Y, Z)) U12(mark(X), Y) >? mark(U12(X, Y)) U13(mark(X)) >? mark(U13(X)) U21(mark(X), Y) >? mark(U21(X, Y)) U22(mark(X)) >? mark(U22(X)) U31(mark(X), Y, Z) >? mark(U31(X, Y, Z)) U32(mark(X), Y) >? mark(U32(X, Y)) U33(mark(X)) >? mark(U33(X)) U41(mark(X), Y) >? mark(U41(X, Y)) U51(mark(X), Y, Z) >? mark(U51(X, Y, Z)) s(mark(X)) >? mark(s(X)) plus(mark(X), Y) >? mark(plus(X, Y)) plus(X, mark(Y)) >? mark(plus(X, Y)) U61(mark(X)) >? mark(U61(X)) U71(mark(X), Y, Z) >? mark(U71(X, Y, Z)) x(mark(X), Y) >? mark(x(X, Y)) x(X, mark(Y)) >? mark(x(X, Y)) and(mark(X), Y) >? mark(and(X, Y)) proper(U11(X, Y, Z)) >? U11(proper(X), proper(Y), proper(Z)) proper(tt) >? ok(tt) proper(U12(X, Y)) >? U12(proper(X), proper(Y)) proper(isNat(X)) >? isNat(proper(X)) proper(U13(X)) >? U13(proper(X)) proper(U21(X, Y)) >? U21(proper(X), proper(Y)) proper(U22(X)) >? U22(proper(X)) proper(U31(X, Y, Z)) >? U31(proper(X), proper(Y), proper(Z)) proper(U32(X, Y)) >? U32(proper(X), proper(Y)) proper(U33(X)) >? U33(proper(X)) proper(U41(X, Y)) >? U41(proper(X), proper(Y)) proper(U51(X, Y, Z)) >? U51(proper(X), proper(Y), proper(Z)) proper(s(X)) >? s(proper(X)) proper(plus(X, Y)) >? plus(proper(X), proper(Y)) proper(U61(X)) >? U61(proper(X)) proper(0) >? ok(0) proper(U71(X, Y, Z)) >? U71(proper(X), proper(Y), proper(Z)) proper(x(X, Y)) >? x(proper(X), proper(Y)) proper(and(X, Y)) >? and(proper(X), proper(Y)) proper(isNatKind(X)) >? isNatKind(proper(X)) U11(ok(X), ok(Y), ok(Z)) >? ok(U11(X, Y, Z)) U12(ok(X), ok(Y)) >? ok(U12(X, Y)) isNat(ok(X)) >? ok(isNat(X)) U13(ok(X)) >? ok(U13(X)) U21(ok(X), ok(Y)) >? ok(U21(X, Y)) U22(ok(X)) >? ok(U22(X)) U31(ok(X), ok(Y), ok(Z)) >? ok(U31(X, Y, Z)) U32(ok(X), ok(Y)) >? ok(U32(X, Y)) U33(ok(X)) >? ok(U33(X)) U41(ok(X), ok(Y)) >? ok(U41(X, Y)) U51(ok(X), ok(Y), ok(Z)) >? ok(U51(X, Y, Z)) s(ok(X)) >? ok(s(X)) plus(ok(X), ok(Y)) >? ok(plus(X, Y)) U61(ok(X)) >? ok(U61(X)) U71(ok(X), ok(Y), ok(Z)) >? ok(U71(X, Y, Z)) x(ok(X), ok(Y)) >? ok(x(X, Y)) and(ok(X), ok(Y)) >? ok(and(X, Y)) isNatKind(ok(X)) >? ok(isNatKind(X)) top(mark(X)) >? top(proper(X)) top(ok(X)) >? top(active(X)) about to try horpo We use a recursive path ordering as defined in [Kop12, Chapter 5]. Argument functions: [[U33(x_1)]] = x_1 [[U51(x_1, x_2, x_3)]] = U51(x_2, x_3, x_1) [[U71(x_1, x_2, x_3)]] = U71(x_3, x_2, x_1) [[active(x_1)]] = x_1 [[ok(x_1)]] = x_1 [[plus(x_1, x_2)]] = plus(x_2, x_1) [[proper(x_1)]] = x_1 We choose Lex = {U51, U71, plus, x} and Mul = {0, U11, U12, U13, U21, U22, U31, U32, U41, U61, and, isNat, isNatKind, mark, s, top, tt}, and the following precedence: 0 = tt > U71 = x > U51 = plus > U11 > U41 > U31 > U32 > U12 = U21 = isNat > U22 > s > U13 > and = isNatKind > top > U61 = mark Taking the argument function into account, and fixing the greater / greater equal choices, the constraints can be denoted as follows: U11(tt, X, Y) > mark(U12(isNat(X), Y)) U12(tt, X) > mark(U13(isNat(X))) U13(tt) >= mark(tt) U21(tt, X) > mark(U22(isNat(X))) U22(tt) > mark(tt) U31(tt, X, Y) >= mark(U32(isNat(X), Y)) U32(tt, X) > mark(isNat(X)) U51(tt, X, Y) >= mark(s(plus(Y, X))) U61(tt) >= mark(0) U71(tt, X, Y) >= mark(plus(x(Y, X), Y)) and(tt, X) > mark(X) isNat(0) >= mark(tt) isNat(plus(X, Y)) > mark(U11(and(isNatKind(X), isNatKind(Y)), X, Y)) isNat(s(X)) > mark(U21(isNatKind(X), X)) isNatKind(0) > mark(tt) isNatKind(x(X, Y)) > mark(and(isNatKind(X), isNatKind(Y))) plus(X, 0) > mark(U41(and(isNat(X), isNatKind(X)), X)) plus(X, s(Y)) > mark(U51(and(and(isNat(Y), isNatKind(Y)), and(isNat(X), isNatKind(X))), Y, X)) x(X, 0) >= mark(U61(and(isNat(X), isNatKind(X)))) x(X, s(Y)) > mark(U71(and(and(isNat(Y), isNatKind(Y)), and(isNat(X), isNatKind(X))), Y, X)) U11(X, Y, Z) >= U11(X, Y, Z) U12(X, Y) >= U12(X, Y) U13(X) >= U13(X) U21(X, Y) >= U21(X, Y) U22(X) >= U22(X) U31(X, Y, Z) >= U31(X, Y, Z) U32(X, Y) >= U32(X, Y) X >= X U41(X, Y) >= U41(X, Y) U51(X, Y, Z) >= U51(X, Y, Z) s(X) >= s(X) plus(X, Y) >= plus(X, Y) plus(X, Y) >= plus(X, Y) U61(X) >= U61(X) U71(X, Y, Z) >= U71(X, Y, Z) x(X, Y) >= x(X, Y) x(X, Y) >= x(X, Y) and(X, Y) >= and(X, Y) U11(mark(X), Y, Z) >= mark(U11(X, Y, Z)) U12(mark(X), Y) > mark(U12(X, Y)) U13(mark(X)) >= mark(U13(X)) U21(mark(X), Y) >= mark(U21(X, Y)) U22(mark(X)) > mark(U22(X)) U31(mark(X), Y, Z) >= mark(U31(X, Y, Z)) U32(mark(X), Y) > mark(U32(X, Y)) mark(X) >= mark(X) U41(mark(X), Y) >= mark(U41(X, Y)) U51(mark(X), Y, Z) > mark(U51(X, Y, Z)) s(mark(X)) >= mark(s(X)) plus(mark(X), Y) > mark(plus(X, Y)) plus(X, mark(Y)) > mark(plus(X, Y)) U61(mark(X)) >= mark(U61(X)) U71(mark(X), Y, Z) >= mark(U71(X, Y, Z)) x(mark(X), Y) >= mark(x(X, Y)) x(X, mark(Y)) > mark(x(X, Y)) and(mark(X), Y) > mark(and(X, Y)) U11(X, Y, Z) >= U11(X, Y, Z) tt >= tt U12(X, Y) >= U12(X, Y) isNat(X) >= isNat(X) U13(X) >= U13(X) U21(X, Y) >= U21(X, Y) U22(X) >= U22(X) U31(X, Y, Z) >= U31(X, Y, Z) U32(X, Y) >= U32(X, Y) X >= X U41(X, Y) >= U41(X, Y) U51(X, Y, Z) >= U51(X, Y, Z) s(X) >= s(X) plus(X, Y) >= plus(X, Y) U61(X) >= U61(X) 0 >= 0 U71(X, Y, Z) >= U71(X, Y, Z) x(X, Y) >= x(X, Y) and(X, Y) >= and(X, Y) isNatKind(X) >= isNatKind(X) U11(X, Y, Z) >= U11(X, Y, Z) U12(X, Y) >= U12(X, Y) isNat(X) >= isNat(X) U13(X) >= U13(X) U21(X, Y) >= U21(X, Y) U22(X) >= U22(X) U31(X, Y, Z) >= U31(X, Y, Z) U32(X, Y) >= U32(X, Y) X >= X U41(X, Y) >= U41(X, Y) U51(X, Y, Z) >= U51(X, Y, Z) s(X) >= s(X) plus(X, Y) >= plus(X, Y) U61(X) >= U61(X) U71(X, Y, Z) >= U71(X, Y, Z) x(X, Y) >= x(X, Y) and(X, Y) >= and(X, Y) isNatKind(X) >= isNatKind(X) top(mark(X)) > top(X) top(X) >= top(X) With these choices, we have: 1] U11(tt, X, Y) > mark(U12(isNat(X), Y)) because [2], by definition 2] U11*(tt, X, Y) >= mark(U12(isNat(X), Y)) because U11 > mark and [3], by (Copy) 3] U11*(tt, X, Y) >= U12(isNat(X), Y) because U11 > U12, [4] and [7], by (Copy) 4] U11*(tt, X, Y) >= isNat(X) because U11 > isNat and [5], by (Copy) 5] U11*(tt, X, Y) >= X because [6], by (Select) 6] X >= X by (Meta) 7] U11*(tt, X, Y) >= Y because [8], by (Select) 8] Y >= Y by (Meta) 9] U12(tt, X) > mark(U13(isNat(X))) because [10], by definition 10] U12*(tt, X) >= mark(U13(isNat(X))) because U12 > mark and [11], by (Copy) 11] U12*(tt, X) >= U13(isNat(X)) because U12 > U13 and [12], by (Copy) 12] U12*(tt, X) >= isNat(X) because U12 = isNat, U12 in Mul and [13], by (Stat) 13] X >= X by (Meta) 14] U13(tt) >= mark(tt) because [15], by (Star) 15] U13*(tt) >= mark(tt) because U13 > mark and [16], by (Copy) 16] U13*(tt) >= tt because [17], by (Select) 17] tt >= tt by (Fun) 18] U21(tt, X) > mark(U22(isNat(X))) because [19], by definition 19] U21*(tt, X) >= mark(U22(isNat(X))) because U21 > mark and [20], by (Copy) 20] U21*(tt, X) >= U22(isNat(X)) because U21 > U22 and [21], by (Copy) 21] U21*(tt, X) >= isNat(X) because U21 = isNat, U21 in Mul and [22], by (Stat) 22] X >= X by (Meta) 23] U22(tt) > mark(tt) because [24], by definition 24] U22*(tt) >= mark(tt) because U22 > mark and [25], by (Copy) 25] U22*(tt) >= tt because [17], by (Select) 26] U31(tt, X, Y) >= mark(U32(isNat(X), Y)) because [27], by (Star) 27] U31*(tt, X, Y) >= mark(U32(isNat(X), Y)) because U31 > mark and [28], by (Copy) 28] U31*(tt, X, Y) >= U32(isNat(X), Y) because U31 > U32, [29] and [31], by (Copy) 29] U31*(tt, X, Y) >= isNat(X) because U31 > isNat and [30], by (Copy) 30] U31*(tt, X, Y) >= X because [22], by (Select) 31] U31*(tt, X, Y) >= Y because [13], by (Select) 32] U32(tt, X) > mark(isNat(X)) because [33], by definition 33] U32*(tt, X) >= mark(isNat(X)) because U32 > mark and [34], by (Copy) 34] U32*(tt, X) >= isNat(X) because U32 > isNat and [35], by (Copy) 35] U32*(tt, X) >= X because [13], by (Select) 36] U51(tt, X, Y) >= mark(s(plus(Y, X))) because [37], by (Star) 37] U51*(tt, X, Y) >= mark(s(plus(Y, X))) because U51 > mark and [38], by (Copy) 38] U51*(tt, X, Y) >= s(plus(Y, X)) because U51 > s and [39], by (Copy) 39] U51*(tt, X, Y) >= plus(Y, X) because U51 = plus, [40], [41], [42] and [43], by (Stat) 40] X >= X by (Meta) 41] Y >= Y by (Meta) 42] U51*(tt, X, Y) >= Y because [41], by (Select) 43] U51*(tt, X, Y) >= X because [40], by (Select) 44] U61(tt) >= mark(0) because U61 = mark, U61 in Mul and [45], by (Fun) 45] tt >= 0 because tt = 0, by (Fun) 46] U71(tt, X, Y) >= mark(plus(x(Y, X), Y)) because [47], by (Star) 47] U71*(tt, X, Y) >= mark(plus(x(Y, X), Y)) because U71 > mark and [48], by (Copy) 48] U71*(tt, X, Y) >= plus(x(Y, X), Y) because U71 > plus, [49] and [50], by (Copy) 49] U71*(tt, X, Y) >= x(Y, X) because U71 = x, [40], [41], [50] and [51], by (Stat) 50] U71*(tt, X, Y) >= Y because [41], by (Select) 51] U71*(tt, X, Y) >= X because [40], by (Select) 52] and(tt, X) > mark(X) because [53], by definition 53] and*(tt, X) >= mark(X) because and > mark and [54], by (Copy) 54] and*(tt, X) >= X because [55], by (Select) 55] X >= X by (Meta) 56] isNat(0) >= mark(tt) because [57], by (Star) 57] isNat*(0) >= mark(tt) because isNat > mark and [58], by (Copy) 58] isNat*(0) >= tt because [59], by (Select) 59] 0 >= tt because 0 = tt, by (Fun) 60] isNat(plus(X, Y)) > mark(U11(and(isNatKind(X), isNatKind(Y)), X, Y)) because [61], by definition 61] isNat*(plus(X, Y)) >= mark(U11(and(isNatKind(X), isNatKind(Y)), X, Y)) because [62], by (Select) 62] plus(X, Y) >= mark(U11(and(isNatKind(X), isNatKind(Y)), X, Y)) because [63], by (Star) 63] plus*(X, Y) >= mark(U11(and(isNatKind(X), isNatKind(Y)), X, Y)) because plus > mark and [64], by (Copy) 64] plus*(X, Y) >= U11(and(isNatKind(X), isNatKind(Y)), X, Y) because plus > U11, [65], [67] and [69], by (Copy) 65] plus*(X, Y) >= and(isNatKind(X), isNatKind(Y)) because plus > and, [66] and [68], by (Copy) 66] plus*(X, Y) >= isNatKind(X) because plus > isNatKind and [67], by (Copy) 67] plus*(X, Y) >= X because [22], by (Select) 68] plus*(X, Y) >= isNatKind(Y) because plus > isNatKind and [69], by (Copy) 69] plus*(X, Y) >= Y because [13], by (Select) 70] isNat(s(X)) > mark(U21(isNatKind(X), X)) because [71], by definition 71] isNat*(s(X)) >= mark(U21(isNatKind(X), X)) because isNat > mark and [72], by (Copy) 72] isNat*(s(X)) >= U21(isNatKind(X), X) because isNat = U21, isNat in Mul, [73] and [76], by (Stat) 73] s(X) > isNatKind(X) because [74], by definition 74] s*(X) >= isNatKind(X) because s > isNatKind and [75], by (Copy) 75] s*(X) >= X because [22], by (Select) 76] s(X) > X because [75], by definition 77] isNatKind(0) > mark(tt) because [78], by definition 78] isNatKind*(0) >= mark(tt) because isNatKind > mark and [79], by (Copy) 79] isNatKind*(0) >= tt because [59], by (Select) 80] isNatKind(x(X, Y)) > mark(and(isNatKind(X), isNatKind(Y))) because [81], by definition 81] isNatKind*(x(X, Y)) >= mark(and(isNatKind(X), isNatKind(Y))) because isNatKind > mark and [82], by (Copy) 82] isNatKind*(x(X, Y)) >= and(isNatKind(X), isNatKind(Y)) because isNatKind = and, isNatKind in Mul, [83] and [86], by (Stat) 83] x(X, Y) > isNatKind(X) because [84], by definition 84] x*(X, Y) >= isNatKind(X) because x > isNatKind and [85], by (Copy) 85] x*(X, Y) >= X because [22], by (Select) 86] x(X, Y) > isNatKind(Y) because [87], by definition 87] x*(X, Y) >= isNatKind(Y) because x > isNatKind and [88], by (Copy) 88] x*(X, Y) >= Y because [13], by (Select) 89] plus(X, 0) > mark(U41(and(isNat(X), isNatKind(X)), X)) because [90], by definition 90] plus*(X, 0) >= mark(U41(and(isNat(X), isNatKind(X)), X)) because plus > mark and [91], by (Copy) 91] plus*(X, 0) >= U41(and(isNat(X), isNatKind(X)), X) because plus > U41, [92] and [94], by (Copy) 92] plus*(X, 0) >= and(isNat(X), isNatKind(X)) because plus > and, [93] and [95], by (Copy) 93] plus*(X, 0) >= isNat(X) because plus > isNat and [94], by (Copy) 94] plus*(X, 0) >= X because [41], by (Select) 95] plus*(X, 0) >= isNatKind(X) because plus > isNatKind and [94], by (Copy) 96] plus(X, s(Y)) > mark(U51(and(and(isNat(Y), isNatKind(Y)), and(isNat(X), isNatKind(X))), Y, X)) because [97], by definition 97] plus*(X, s(Y)) >= mark(U51(and(and(isNat(Y), isNatKind(Y)), and(isNat(X), isNatKind(X))), Y, X)) because plus > mark and [98], by (Copy) 98] plus*(X, s(Y)) >= U51(and(and(isNat(Y), isNatKind(Y)), and(isNat(X), isNatKind(X))), Y, X) because plus = U51, [99], [101], [104] and [109], by (Stat) 99] s(Y) > Y because [100], by definition 100] s*(Y) >= Y because [40], by (Select) 101] plus*(X, s(Y)) >= and(and(isNat(Y), isNatKind(Y)), and(isNat(X), isNatKind(X))) because plus > and, [102] and [107], by (Copy) 102] plus*(X, s(Y)) >= and(isNat(Y), isNatKind(Y)) because plus > and, [103] and [106], by (Copy) 103] plus*(X, s(Y)) >= isNat(Y) because plus > isNat and [104], by (Copy) 104] plus*(X, s(Y)) >= Y because [105], by (Select) 105] s(Y) >= Y because [100], by (Star) 106] plus*(X, s(Y)) >= isNatKind(Y) because plus > isNatKind and [104], by (Copy) 107] plus*(X, s(Y)) >= and(isNat(X), isNatKind(X)) because plus > and, [108] and [110], by (Copy) 108] plus*(X, s(Y)) >= isNat(X) because plus > isNat and [109], by (Copy) 109] plus*(X, s(Y)) >= X because [41], by (Select) 110] plus*(X, s(Y)) >= isNatKind(X) because plus > isNatKind and [109], by (Copy) 111] x(X, 0) >= mark(U61(and(isNat(X), isNatKind(X)))) because [112], by (Star) 112] x*(X, 0) >= mark(U61(and(isNat(X), isNatKind(X)))) because x > mark and [113], by (Copy) 113] x*(X, 0) >= U61(and(isNat(X), isNatKind(X))) because x > U61 and [114], by (Copy) 114] x*(X, 0) >= and(isNat(X), isNatKind(X)) because x > and, [115] and [117], by (Copy) 115] x*(X, 0) >= isNat(X) because x > isNat and [116], by (Copy) 116] x*(X, 0) >= X because [41], by (Select) 117] x*(X, 0) >= isNatKind(X) because x > isNatKind and [116], by (Copy) 118] x(X, s(Y)) > mark(U71(and(and(isNat(Y), isNatKind(Y)), and(isNat(X), isNatKind(X))), Y, X)) because [119], by definition 119] x*(X, s(Y)) >= mark(U71(and(and(isNat(Y), isNatKind(Y)), and(isNat(X), isNatKind(X))), Y, X)) because x > mark and [120], by (Copy) 120] x*(X, s(Y)) >= U71(and(and(isNat(Y), isNatKind(Y)), and(isNat(X), isNatKind(X))), Y, X) because x = U71, [41], [99], [121], [124] and [128], by (Stat) 121] x*(X, s(Y)) >= and(and(isNat(Y), isNatKind(Y)), and(isNat(X), isNatKind(X))) because x > and, [122] and [126], by (Copy) 122] x*(X, s(Y)) >= and(isNat(Y), isNatKind(Y)) because x > and, [123] and [125], by (Copy) 123] x*(X, s(Y)) >= isNat(Y) because x > isNat and [124], by (Copy) 124] x*(X, s(Y)) >= Y because [105], by (Select) 125] x*(X, s(Y)) >= isNatKind(Y) because x > isNatKind and [124], by (Copy) 126] x*(X, s(Y)) >= and(isNat(X), isNatKind(X)) because x > and, [127] and [129], by (Copy) 127] x*(X, s(Y)) >= isNat(X) because x > isNat and [128], by (Copy) 128] x*(X, s(Y)) >= X because [41], by (Select) 129] x*(X, s(Y)) >= isNatKind(X) because x > isNatKind and [128], by (Copy) 130] U11(X, Y, Z) >= U11(X, Y, Z) because U11 in Mul, [131], [132] and [133], by (Fun) 131] X >= X by (Meta) 132] Y >= Y by (Meta) 133] Z >= Z by (Meta) 134] U12(X, Y) >= U12(X, Y) because U12 in Mul, [131] and [132], by (Fun) 135] U13(X) >= U13(X) because U13 in Mul and [136], by (Fun) 136] X >= X by (Meta) 137] U21(X, Y) >= U21(X, Y) because U21 in Mul, [131] and [132], by (Fun) 138] U22(X) >= U22(X) because U22 in Mul and [136], by (Fun) 139] U31(X, Y, Z) >= U31(X, Y, Z) because U31 in Mul, [131], [132] and [133], by (Fun) 140] U32(X, Y) >= U32(X, Y) because U32 in Mul, [131] and [132], by (Fun) 141] X >= X by (Meta) 142] U41(X, Y) >= U41(X, Y) because U41 in Mul, [131] and [132], by (Fun) 143] U51(X, Y, Z) >= U51(X, Y, Z) because [131], [132] and [133], by (Fun) 144] s(X) >= s(X) because s in Mul and [136], by (Fun) 145] plus(X, Y) >= plus(X, Y) because [131] and [132], by (Fun) 146] plus(X, Y) >= plus(X, Y) because [131] and [147], by (Fun) 147] Y >= Y by (Meta) 148] U61(X) >= U61(X) because U61 in Mul and [136], by (Fun) 149] U71(X, Y, Z) >= U71(X, Y, Z) because [131], [147] and [133], by (Fun) 150] x(X, Y) >= x(X, Y) because [131] and [147], by (Fun) 151] x(X, Y) >= x(X, Y) because [131] and [147], by (Fun) 152] and(X, Y) >= and(X, Y) because and in Mul, [131] and [147], by (Fun) 153] U11(mark(X), Y, Z) >= mark(U11(X, Y, Z)) because [154], by (Star) 154] U11*(mark(X), Y, Z) >= mark(U11(X, Y, Z)) because U11 > mark and [155], by (Copy) 155] U11*(mark(X), Y, Z) >= U11(X, Y, Z) because U11 in Mul, [156], [147] and [133], by (Stat) 156] mark(X) > X because [157], by definition 157] mark*(X) >= X because [131], by (Select) 158] U12(mark(X), Y) > mark(U12(X, Y)) because [159], by definition 159] U12*(mark(X), Y) >= mark(U12(X, Y)) because U12 > mark and [160], by (Copy) 160] U12*(mark(X), Y) >= U12(X, Y) because U12 in Mul, [156] and [147], by (Stat) 161] U13(mark(X)) >= mark(U13(X)) because [162], by (Star) 162] U13*(mark(X)) >= mark(U13(X)) because U13 > mark and [163], by (Copy) 163] U13*(mark(X)) >= U13(X) because U13 in Mul and [164], by (Stat) 164] mark(X) > X because [165], by definition 165] mark*(X) >= X because [141], by (Select) 166] U21(mark(X), Y) >= mark(U21(X, Y)) because [167], by (Star) 167] U21*(mark(X), Y) >= mark(U21(X, Y)) because U21 > mark and [168], by (Copy) 168] U21*(mark(X), Y) >= U21(X, Y) because U21 in Mul, [156] and [147], by (Stat) 169] U22(mark(X)) > mark(U22(X)) because [170], by definition 170] U22*(mark(X)) >= mark(U22(X)) because U22 > mark and [171], by (Copy) 171] U22*(mark(X)) >= U22(X) because U22 in Mul and [164], by (Stat) 172] U31(mark(X), Y, Z) >= mark(U31(X, Y, Z)) because [173], by (Star) 173] U31*(mark(X), Y, Z) >= mark(U31(X, Y, Z)) because U31 > mark and [174], by (Copy) 174] U31*(mark(X), Y, Z) >= U31(X, Y, Z) because U31 in Mul, [156], [147] and [133], by (Stat) 175] U32(mark(X), Y) > mark(U32(X, Y)) because [176], by definition 176] U32*(mark(X), Y) >= mark(U32(X, Y)) because U32 > mark and [177], by (Copy) 177] U32*(mark(X), Y) >= U32(X, Y) because U32 in Mul, [156] and [147], by (Stat) 178] mark(X) >= mark(X) because mark in Mul and [179], by (Fun) 179] X >= X by (Meta) 180] U41(mark(X), Y) >= mark(U41(X, Y)) because [181], by (Star) 181] U41*(mark(X), Y) >= mark(U41(X, Y)) because U41 > mark and [182], by (Copy) 182] U41*(mark(X), Y) >= U41(X, Y) because U41 in Mul, [156] and [147], by (Stat) 183] U51(mark(X), Y, Z) > mark(U51(X, Y, Z)) because [184], by definition 184] U51*(mark(X), Y, Z) >= mark(U51(X, Y, Z)) because U51 > mark and [185], by (Copy) 185] U51*(mark(X), Y, Z) >= U51(X, Y, Z) because [156], [147], [133], [186], [188] and [189], by (Stat) 186] U51*(mark(X), Y, Z) >= X because [187], by (Select) 187] mark(X) >= X because [157], by (Star) 188] U51*(mark(X), Y, Z) >= Y because [147], by (Select) 189] U51*(mark(X), Y, Z) >= Z because [133], by (Select) 190] s(mark(X)) >= mark(s(X)) because [191], by (Star) 191] s*(mark(X)) >= mark(s(X)) because s > mark and [192], by (Copy) 192] s*(mark(X)) >= s(X) because s in Mul and [164], by (Stat) 193] plus(mark(X), Y) > mark(plus(X, Y)) because [194], by definition 194] plus*(mark(X), Y) >= mark(plus(X, Y)) because plus > mark and [195], by (Copy) 195] plus*(mark(X), Y) >= plus(X, Y) because [156], [147], [196] and [197], by (Stat) 196] plus*(mark(X), Y) >= X because [187], by (Select) 197] plus*(mark(X), Y) >= Y because [147], by (Select) 198] plus(X, mark(Y)) > mark(plus(X, Y)) because [199], by definition 199] plus*(X, mark(Y)) >= mark(plus(X, Y)) because plus > mark and [200], by (Copy) 200] plus*(X, mark(Y)) >= plus(X, Y) because [201], [203] and [204], by (Stat) 201] mark(Y) > Y because [202], by definition 202] mark*(Y) >= Y because [147], by (Select) 203] plus*(X, mark(Y)) >= X because [131], by (Select) 204] plus*(X, mark(Y)) >= Y because [205], by (Select) 205] mark(Y) >= Y because [202], by (Star) 206] U61(mark(X)) >= mark(U61(X)) because U61 = mark, U61 in Mul and [207], by (Fun) 207] mark(X) >= U61(X) because mark = U61, mark in Mul and [179], by (Fun) 208] U71(mark(X), Y, Z) >= mark(U71(X, Y, Z)) because [209], by (Star) 209] U71*(mark(X), Y, Z) >= mark(U71(X, Y, Z)) because U71 > mark and [210], by (Copy) 210] U71*(mark(X), Y, Z) >= U71(X, Y, Z) because [156], [147], [133], [211], [212] and [213], by (Stat) 211] U71*(mark(X), Y, Z) >= X because [187], by (Select) 212] U71*(mark(X), Y, Z) >= Y because [147], by (Select) 213] U71*(mark(X), Y, Z) >= Z because [133], by (Select) 214] x(mark(X), Y) >= mark(x(X, Y)) because [215], by (Star) 215] x*(mark(X), Y) >= mark(x(X, Y)) because x > mark and [216], by (Copy) 216] x*(mark(X), Y) >= x(X, Y) because [156], [217] and [218], by (Stat) 217] x*(mark(X), Y) >= X because [187], by (Select) 218] x*(mark(X), Y) >= Y because [147], by (Select) 219] x(X, mark(Y)) > mark(x(X, Y)) because [220], by definition 220] x*(X, mark(Y)) >= mark(x(X, Y)) because x > mark and [221], by (Copy) 221] x*(X, mark(Y)) >= x(X, Y) because [131], [201], [222] and [223], by (Stat) 222] x*(X, mark(Y)) >= X because [131], by (Select) 223] x*(X, mark(Y)) >= Y because [205], by (Select) 224] and(mark(X), Y) > mark(and(X, Y)) because [225], by definition 225] and*(mark(X), Y) >= mark(and(X, Y)) because and > mark and [226], by (Copy) 226] and*(mark(X), Y) >= and(X, Y) because and in Mul, [156] and [147], by (Stat) 227] U11(X, Y, Z) >= U11(X, Y, Z) because U11 in Mul, [228], [229] and [230], by (Fun) 228] X >= X by (Meta) 229] Y >= Y by (Meta) 230] Z >= Z by (Meta) 231] tt >= tt by (Fun) 232] U12(X, Y) >= U12(X, Y) because U12 in Mul, [228] and [229], by (Fun) 233] isNat(X) >= isNat(X) because isNat in Mul and [234], by (Fun) 234] X >= X by (Meta) 235] U13(X) >= U13(X) because U13 in Mul and [234], by (Fun) 236] U21(X, Y) >= U21(X, Y) because U21 in Mul, [228] and [229], by (Fun) 237] U22(X) >= U22(X) because U22 in Mul and [234], by (Fun) 238] U31(X, Y, Z) >= U31(X, Y, Z) because U31 in Mul, [228], [229] and [230], by (Fun) 239] U32(X, Y) >= U32(X, Y) because U32 in Mul, [228] and [229], by (Fun) 240] X >= X by (Meta) 241] U41(X, Y) >= U41(X, Y) because U41 in Mul, [228] and [229], by (Fun) 242] U51(X, Y, Z) >= U51(X, Y, Z) because [228], [229] and [230], by (Fun) 243] s(X) >= s(X) because s in Mul and [234], by (Fun) 244] plus(X, Y) >= plus(X, Y) because [228] and [229], by (Fun) 245] U61(X) >= U61(X) because U61 in Mul and [234], by (Fun) 246] 0 >= 0 by (Fun) 247] U71(X, Y, Z) >= U71(X, Y, Z) because [228], [229] and [230], by (Fun) 248] x(X, Y) >= x(X, Y) because [228] and [229], by (Fun) 249] and(X, Y) >= and(X, Y) because and in Mul, [228] and [229], by (Fun) 250] isNatKind(X) >= isNatKind(X) because isNatKind in Mul and [234], by (Fun) 251] U11(X, Y, Z) >= U11(X, Y, Z) because U11 in Mul, [252], [253] and [254], by (Fun) 252] X >= X by (Meta) 253] Y >= Y by (Meta) 254] Z >= Z by (Meta) 255] U12(X, Y) >= U12(X, Y) because U12 in Mul, [252] and [253], by (Fun) 256] isNat(X) >= isNat(X) because isNat in Mul and [257], by (Fun) 257] X >= X by (Meta) 258] U13(X) >= U13(X) because U13 in Mul and [257], by (Fun) 259] U21(X, Y) >= U21(X, Y) because U21 in Mul, [252] and [253], by (Fun) 260] U22(X) >= U22(X) because U22 in Mul and [257], by (Fun) 261] U31(X, Y, Z) >= U31(X, Y, Z) because U31 in Mul, [252], [253] and [254], by (Fun) 262] U32(X, Y) >= U32(X, Y) because U32 in Mul, [252] and [253], by (Fun) 263] X >= X by (Meta) 264] U41(X, Y) >= U41(X, Y) because U41 in Mul, [252] and [253], by (Fun) 265] U51(X, Y, Z) >= U51(X, Y, Z) because [252], [253] and [254], by (Fun) 266] s(X) >= s(X) because s in Mul and [257], by (Fun) 267] plus(X, Y) >= plus(X, Y) because [252] and [253], by (Fun) 268] U61(X) >= U61(X) because U61 in Mul and [257], by (Fun) 269] U71(X, Y, Z) >= U71(X, Y, Z) because [252], [253] and [254], by (Fun) 270] x(X, Y) >= x(X, Y) because [252] and [253], by (Fun) 271] and(X, Y) >= and(X, Y) because and in Mul, [252] and [253], by (Fun) 272] isNatKind(X) >= isNatKind(X) because isNatKind in Mul and [257], by (Fun) 273] top(mark(X)) > top(X) because [274], by definition 274] top*(mark(X)) >= top(X) because top in Mul and [275], by (Stat) 275] mark(X) > X because [276], by definition 276] mark*(X) >= X because [263], by (Select) 277] top(X) >= top(X) because top in Mul and [278], by (Fun) 278] X >= X by (Meta) We can thus remove the following rules: active(U11(tt, X, Y)) => mark(U12(isNat(X), Y)) active(U12(tt, X)) => mark(U13(isNat(X))) active(U21(tt, X)) => mark(U22(isNat(X))) active(U22(tt)) => mark(tt) active(U32(tt, X)) => mark(U33(isNat(X))) active(and(tt, X)) => mark(X) active(isNat(plus(X, Y))) => mark(U11(and(isNatKind(X), isNatKind(Y)), X, Y)) active(isNat(s(X))) => mark(U21(isNatKind(X), X)) active(isNatKind(0)) => mark(tt) active(isNatKind(x(X, Y))) => mark(and(isNatKind(X), isNatKind(Y))) active(plus(X, 0)) => mark(U41(and(isNat(X), isNatKind(X)), X)) active(plus(X, s(Y))) => mark(U51(and(and(isNat(Y), isNatKind(Y)), and(isNat(X), isNatKind(X))), Y, X)) active(x(X, s(Y))) => mark(U71(and(and(isNat(Y), isNatKind(Y)), and(isNat(X), isNatKind(X))), Y, X)) U12(mark(X), Y) => mark(U12(X, Y)) U22(mark(X)) => mark(U22(X)) U32(mark(X), Y) => mark(U32(X, Y)) U51(mark(X), Y, Z) => mark(U51(X, Y, Z)) plus(mark(X), Y) => mark(plus(X, Y)) plus(X, mark(Y)) => mark(plus(X, Y)) x(X, mark(Y)) => mark(x(X, Y)) and(mark(X), Y) => mark(and(X, Y)) top(mark(X)) => top(proper(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]): active(U13(tt)) >? mark(tt) active(U31(tt, X, Y)) >? mark(U32(isNat(X), Y)) active(U51(tt, X, Y)) >? mark(s(plus(Y, X))) active(U61(tt)) >? mark(0) active(U71(tt, X, Y)) >? mark(plus(x(Y, X), Y)) active(isNat(0)) >? mark(tt) active(x(X, 0)) >? mark(U61(and(isNat(X), isNatKind(X)))) active(U11(X, Y, Z)) >? U11(active(X), Y, Z) active(U12(X, Y)) >? U12(active(X), Y) active(U13(X)) >? U13(active(X)) active(U21(X, Y)) >? U21(active(X), Y) active(U22(X)) >? U22(active(X)) active(U31(X, Y, Z)) >? U31(active(X), Y, Z) active(U32(X, Y)) >? U32(active(X), Y) active(U33(X)) >? U33(active(X)) active(U41(X, Y)) >? U41(active(X), Y) active(U51(X, Y, Z)) >? U51(active(X), Y, Z) active(s(X)) >? s(active(X)) active(plus(X, Y)) >? plus(active(X), Y) active(plus(X, Y)) >? plus(X, active(Y)) active(U61(X)) >? U61(active(X)) active(U71(X, Y, Z)) >? U71(active(X), Y, Z) active(x(X, Y)) >? x(active(X), Y) active(x(X, Y)) >? x(X, active(Y)) active(and(X, Y)) >? and(active(X), Y) U11(mark(X), Y, Z) >? mark(U11(X, Y, Z)) U13(mark(X)) >? mark(U13(X)) U21(mark(X), Y) >? mark(U21(X, Y)) U31(mark(X), Y, Z) >? mark(U31(X, Y, Z)) U33(mark(X)) >? mark(U33(X)) U41(mark(X), Y) >? mark(U41(X, Y)) s(mark(X)) >? mark(s(X)) U61(mark(X)) >? mark(U61(X)) U71(mark(X), Y, Z) >? mark(U71(X, Y, Z)) x(mark(X), Y) >? mark(x(X, Y)) proper(U11(X, Y, Z)) >? U11(proper(X), proper(Y), proper(Z)) proper(tt) >? ok(tt) proper(U12(X, Y)) >? U12(proper(X), proper(Y)) proper(isNat(X)) >? isNat(proper(X)) proper(U13(X)) >? U13(proper(X)) proper(U21(X, Y)) >? U21(proper(X), proper(Y)) proper(U22(X)) >? U22(proper(X)) proper(U31(X, Y, Z)) >? U31(proper(X), proper(Y), proper(Z)) proper(U32(X, Y)) >? U32(proper(X), proper(Y)) proper(U33(X)) >? U33(proper(X)) proper(U41(X, Y)) >? U41(proper(X), proper(Y)) proper(U51(X, Y, Z)) >? U51(proper(X), proper(Y), proper(Z)) proper(s(X)) >? s(proper(X)) proper(plus(X, Y)) >? plus(proper(X), proper(Y)) proper(U61(X)) >? U61(proper(X)) proper(0) >? ok(0) proper(U71(X, Y, Z)) >? U71(proper(X), proper(Y), proper(Z)) proper(x(X, Y)) >? x(proper(X), proper(Y)) proper(and(X, Y)) >? and(proper(X), proper(Y)) proper(isNatKind(X)) >? isNatKind(proper(X)) U11(ok(X), ok(Y), ok(Z)) >? ok(U11(X, Y, Z)) U12(ok(X), ok(Y)) >? ok(U12(X, Y)) isNat(ok(X)) >? ok(isNat(X)) U13(ok(X)) >? ok(U13(X)) U21(ok(X), ok(Y)) >? ok(U21(X, Y)) U22(ok(X)) >? ok(U22(X)) U31(ok(X), ok(Y), ok(Z)) >? ok(U31(X, Y, Z)) U32(ok(X), ok(Y)) >? ok(U32(X, Y)) U33(ok(X)) >? ok(U33(X)) U41(ok(X), ok(Y)) >? ok(U41(X, Y)) U51(ok(X), ok(Y), ok(Z)) >? ok(U51(X, Y, Z)) s(ok(X)) >? ok(s(X)) plus(ok(X), ok(Y)) >? ok(plus(X, Y)) U61(ok(X)) >? ok(U61(X)) U71(ok(X), ok(Y), ok(Z)) >? ok(U71(X, Y, Z)) x(ok(X), ok(Y)) >? ok(x(X, Y)) and(ok(X), ok(Y)) >? ok(and(X, Y)) isNatKind(ok(X)) >? ok(isNatKind(X)) top(ok(X)) >? top(active(X)) We orient these requirements with a polynomial interpretation in the natural numbers. The following interpretation satisfies the requirements: 0 = 1 U11 = \y0y1y2.y1 + y2 + 2y0 U12 = \y0y1.2 + y1 + 2y0 U13 = \y0.y0 U21 = \y0y1.y0 + y1 U22 = \y0.2y0 U31 = \y0y1y2.y0 + y2 + 2y1 U32 = \y0y1.y0 + y1 U33 = \y0.2y0 U41 = \y0y1.y1 + 2y0 U51 = \y0y1y2.y0 + y2 + 2y1 U61 = \y0.y0 U71 = \y0y1y2.2y0 + 2y1 + 3y2 active = \y0.y0 and = \y0y1.y0 + y1 isNat = \y0.y0 isNatKind = \y0.y0 mark = \y0.y0 ok = \y0.y0 plus = \y0y1.y0 + y1 proper = \y0.3y0 s = \y0.y0 top = \y0.y0 tt = 1 x = \y0y1.y1 + 2y0 Using this interpretation, the requirements translate to: [[active(U13(tt))]] = 1 >= 1 = [[mark(tt)]] [[active(U31(tt, _x0, _x1))]] = 1 + x1 + 2x0 > x0 + x1 = [[mark(U32(isNat(_x0), _x1))]] [[active(U51(tt, _x0, _x1))]] = 1 + x1 + 2x0 > x0 + x1 = [[mark(s(plus(_x1, _x0)))]] [[active(U61(tt))]] = 1 >= 1 = [[mark(0)]] [[active(U71(tt, _x0, _x1))]] = 2 + 2x0 + 3x1 > x0 + 3x1 = [[mark(plus(x(_x1, _x0), _x1))]] [[active(isNat(0))]] = 1 >= 1 = [[mark(tt)]] [[active(x(_x0, 0))]] = 1 + 2x0 > 2x0 = [[mark(U61(and(isNat(_x0), isNatKind(_x0))))]] [[active(U11(_x0, _x1, _x2))]] = x1 + x2 + 2x0 >= x1 + x2 + 2x0 = [[U11(active(_x0), _x1, _x2)]] [[active(U12(_x0, _x1))]] = 2 + x1 + 2x0 >= 2 + x1 + 2x0 = [[U12(active(_x0), _x1)]] [[active(U13(_x0))]] = x0 >= x0 = [[U13(active(_x0))]] [[active(U21(_x0, _x1))]] = x0 + x1 >= x0 + x1 = [[U21(active(_x0), _x1)]] [[active(U22(_x0))]] = 2x0 >= 2x0 = [[U22(active(_x0))]] [[active(U31(_x0, _x1, _x2))]] = x0 + x2 + 2x1 >= x0 + x2 + 2x1 = [[U31(active(_x0), _x1, _x2)]] [[active(U32(_x0, _x1))]] = x0 + x1 >= x0 + x1 = [[U32(active(_x0), _x1)]] [[active(U33(_x0))]] = 2x0 >= 2x0 = [[U33(active(_x0))]] [[active(U41(_x0, _x1))]] = x1 + 2x0 >= x1 + 2x0 = [[U41(active(_x0), _x1)]] [[active(U51(_x0, _x1, _x2))]] = x0 + x2 + 2x1 >= x0 + x2 + 2x1 = [[U51(active(_x0), _x1, _x2)]] [[active(s(_x0))]] = x0 >= x0 = [[s(active(_x0))]] [[active(plus(_x0, _x1))]] = x0 + x1 >= x0 + x1 = [[plus(active(_x0), _x1)]] [[active(plus(_x0, _x1))]] = x0 + x1 >= x0 + x1 = [[plus(_x0, active(_x1))]] [[active(U61(_x0))]] = x0 >= x0 = [[U61(active(_x0))]] [[active(U71(_x0, _x1, _x2))]] = 2x0 + 2x1 + 3x2 >= 2x0 + 2x1 + 3x2 = [[U71(active(_x0), _x1, _x2)]] [[active(x(_x0, _x1))]] = x1 + 2x0 >= x1 + 2x0 = [[x(active(_x0), _x1)]] [[active(x(_x0, _x1))]] = x1 + 2x0 >= x1 + 2x0 = [[x(_x0, active(_x1))]] [[active(and(_x0, _x1))]] = x0 + x1 >= x0 + x1 = [[and(active(_x0), _x1)]] [[U11(mark(_x0), _x1, _x2)]] = x1 + x2 + 2x0 >= x1 + x2 + 2x0 = [[mark(U11(_x0, _x1, _x2))]] [[U13(mark(_x0))]] = x0 >= x0 = [[mark(U13(_x0))]] [[U21(mark(_x0), _x1)]] = x0 + x1 >= x0 + x1 = [[mark(U21(_x0, _x1))]] [[U31(mark(_x0), _x1, _x2)]] = x0 + x2 + 2x1 >= x0 + x2 + 2x1 = [[mark(U31(_x0, _x1, _x2))]] [[U33(mark(_x0))]] = 2x0 >= 2x0 = [[mark(U33(_x0))]] [[U41(mark(_x0), _x1)]] = x1 + 2x0 >= x1 + 2x0 = [[mark(U41(_x0, _x1))]] [[s(mark(_x0))]] = x0 >= x0 = [[mark(s(_x0))]] [[U61(mark(_x0))]] = x0 >= x0 = [[mark(U61(_x0))]] [[U71(mark(_x0), _x1, _x2)]] = 2x0 + 2x1 + 3x2 >= 2x0 + 2x1 + 3x2 = [[mark(U71(_x0, _x1, _x2))]] [[x(mark(_x0), _x1)]] = x1 + 2x0 >= x1 + 2x0 = [[mark(x(_x0, _x1))]] [[proper(U11(_x0, _x1, _x2))]] = 3x1 + 3x2 + 6x0 >= 3x1 + 3x2 + 6x0 = [[U11(proper(_x0), proper(_x1), proper(_x2))]] [[proper(tt)]] = 3 > 1 = [[ok(tt)]] [[proper(U12(_x0, _x1))]] = 6 + 3x1 + 6x0 > 2 + 3x1 + 6x0 = [[U12(proper(_x0), proper(_x1))]] [[proper(isNat(_x0))]] = 3x0 >= 3x0 = [[isNat(proper(_x0))]] [[proper(U13(_x0))]] = 3x0 >= 3x0 = [[U13(proper(_x0))]] [[proper(U21(_x0, _x1))]] = 3x0 + 3x1 >= 3x0 + 3x1 = [[U21(proper(_x0), proper(_x1))]] [[proper(U22(_x0))]] = 6x0 >= 6x0 = [[U22(proper(_x0))]] [[proper(U31(_x0, _x1, _x2))]] = 3x0 + 3x2 + 6x1 >= 3x0 + 3x2 + 6x1 = [[U31(proper(_x0), proper(_x1), proper(_x2))]] [[proper(U32(_x0, _x1))]] = 3x0 + 3x1 >= 3x0 + 3x1 = [[U32(proper(_x0), proper(_x1))]] [[proper(U33(_x0))]] = 6x0 >= 6x0 = [[U33(proper(_x0))]] [[proper(U41(_x0, _x1))]] = 3x1 + 6x0 >= 3x1 + 6x0 = [[U41(proper(_x0), proper(_x1))]] [[proper(U51(_x0, _x1, _x2))]] = 3x0 + 3x2 + 6x1 >= 3x0 + 3x2 + 6x1 = [[U51(proper(_x0), proper(_x1), proper(_x2))]] [[proper(s(_x0))]] = 3x0 >= 3x0 = [[s(proper(_x0))]] [[proper(plus(_x0, _x1))]] = 3x0 + 3x1 >= 3x0 + 3x1 = [[plus(proper(_x0), proper(_x1))]] [[proper(U61(_x0))]] = 3x0 >= 3x0 = [[U61(proper(_x0))]] [[proper(0)]] = 3 > 1 = [[ok(0)]] [[proper(U71(_x0, _x1, _x2))]] = 6x0 + 6x1 + 9x2 >= 6x0 + 6x1 + 9x2 = [[U71(proper(_x0), proper(_x1), proper(_x2))]] [[proper(x(_x0, _x1))]] = 3x1 + 6x0 >= 3x1 + 6x0 = [[x(proper(_x0), proper(_x1))]] [[proper(and(_x0, _x1))]] = 3x0 + 3x1 >= 3x0 + 3x1 = [[and(proper(_x0), proper(_x1))]] [[proper(isNatKind(_x0))]] = 3x0 >= 3x0 = [[isNatKind(proper(_x0))]] [[U11(ok(_x0), ok(_x1), ok(_x2))]] = x1 + x2 + 2x0 >= x1 + x2 + 2x0 = [[ok(U11(_x0, _x1, _x2))]] [[U12(ok(_x0), ok(_x1))]] = 2 + x1 + 2x0 >= 2 + x1 + 2x0 = [[ok(U12(_x0, _x1))]] [[isNat(ok(_x0))]] = x0 >= x0 = [[ok(isNat(_x0))]] [[U13(ok(_x0))]] = x0 >= x0 = [[ok(U13(_x0))]] [[U21(ok(_x0), ok(_x1))]] = x0 + x1 >= x0 + x1 = [[ok(U21(_x0, _x1))]] [[U22(ok(_x0))]] = 2x0 >= 2x0 = [[ok(U22(_x0))]] [[U31(ok(_x0), ok(_x1), ok(_x2))]] = x0 + x2 + 2x1 >= x0 + x2 + 2x1 = [[ok(U31(_x0, _x1, _x2))]] [[U32(ok(_x0), ok(_x1))]] = x0 + x1 >= x0 + x1 = [[ok(U32(_x0, _x1))]] [[U33(ok(_x0))]] = 2x0 >= 2x0 = [[ok(U33(_x0))]] [[U41(ok(_x0), ok(_x1))]] = x1 + 2x0 >= x1 + 2x0 = [[ok(U41(_x0, _x1))]] [[U51(ok(_x0), ok(_x1), ok(_x2))]] = x0 + x2 + 2x1 >= x0 + x2 + 2x1 = [[ok(U51(_x0, _x1, _x2))]] [[s(ok(_x0))]] = x0 >= x0 = [[ok(s(_x0))]] [[plus(ok(_x0), ok(_x1))]] = x0 + x1 >= x0 + x1 = [[ok(plus(_x0, _x1))]] [[U61(ok(_x0))]] = x0 >= x0 = [[ok(U61(_x0))]] [[U71(ok(_x0), ok(_x1), ok(_x2))]] = 2x0 + 2x1 + 3x2 >= 2x0 + 2x1 + 3x2 = [[ok(U71(_x0, _x1, _x2))]] [[x(ok(_x0), ok(_x1))]] = x1 + 2x0 >= x1 + 2x0 = [[ok(x(_x0, _x1))]] [[and(ok(_x0), ok(_x1))]] = x0 + x1 >= x0 + x1 = [[ok(and(_x0, _x1))]] [[isNatKind(ok(_x0))]] = x0 >= x0 = [[ok(isNatKind(_x0))]] [[top(ok(_x0))]] = x0 >= x0 = [[top(active(_x0))]] We can thus remove the following rules: active(U31(tt, X, Y)) => mark(U32(isNat(X), Y)) active(U51(tt, X, Y)) => mark(s(plus(Y, X))) active(U71(tt, X, Y)) => mark(plus(x(Y, X), Y)) active(x(X, 0)) => mark(U61(and(isNat(X), isNatKind(X)))) proper(tt) => ok(tt) proper(U12(X, Y)) => U12(proper(X), proper(Y)) proper(0) => ok(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]): active(U13(tt)) >? mark(tt) active(U61(tt)) >? mark(0) active(isNat(0)) >? mark(tt) active(U11(X, Y, Z)) >? U11(active(X), Y, Z) active(U12(X, Y)) >? U12(active(X), Y) active(U13(X)) >? U13(active(X)) active(U21(X, Y)) >? U21(active(X), Y) active(U22(X)) >? U22(active(X)) active(U31(X, Y, Z)) >? U31(active(X), Y, Z) active(U32(X, Y)) >? U32(active(X), Y) active(U33(X)) >? U33(active(X)) active(U41(X, Y)) >? U41(active(X), Y) active(U51(X, Y, Z)) >? U51(active(X), Y, Z) active(s(X)) >? s(active(X)) active(plus(X, Y)) >? plus(active(X), Y) active(plus(X, Y)) >? plus(X, active(Y)) active(U61(X)) >? U61(active(X)) active(U71(X, Y, Z)) >? U71(active(X), Y, Z) active(x(X, Y)) >? x(active(X), Y) active(x(X, Y)) >? x(X, active(Y)) active(and(X, Y)) >? and(active(X), Y) U11(mark(X), Y, Z) >? mark(U11(X, Y, Z)) U13(mark(X)) >? mark(U13(X)) U21(mark(X), Y) >? mark(U21(X, Y)) U31(mark(X), Y, Z) >? mark(U31(X, Y, Z)) U33(mark(X)) >? mark(U33(X)) U41(mark(X), Y) >? mark(U41(X, Y)) s(mark(X)) >? mark(s(X)) U61(mark(X)) >? mark(U61(X)) U71(mark(X), Y, Z) >? mark(U71(X, Y, Z)) x(mark(X), Y) >? mark(x(X, Y)) proper(U11(X, Y, Z)) >? U11(proper(X), proper(Y), proper(Z)) proper(isNat(X)) >? isNat(proper(X)) proper(U13(X)) >? U13(proper(X)) proper(U21(X, Y)) >? U21(proper(X), proper(Y)) proper(U22(X)) >? U22(proper(X)) proper(U31(X, Y, Z)) >? U31(proper(X), proper(Y), proper(Z)) proper(U32(X, Y)) >? U32(proper(X), proper(Y)) proper(U33(X)) >? U33(proper(X)) proper(U41(X, Y)) >? U41(proper(X), proper(Y)) proper(U51(X, Y, Z)) >? U51(proper(X), proper(Y), proper(Z)) proper(s(X)) >? s(proper(X)) proper(plus(X, Y)) >? plus(proper(X), proper(Y)) proper(U61(X)) >? U61(proper(X)) proper(U71(X, Y, Z)) >? U71(proper(X), proper(Y), proper(Z)) proper(x(X, Y)) >? x(proper(X), proper(Y)) proper(and(X, Y)) >? and(proper(X), proper(Y)) proper(isNatKind(X)) >? isNatKind(proper(X)) U11(ok(X), ok(Y), ok(Z)) >? ok(U11(X, Y, Z)) U12(ok(X), ok(Y)) >? ok(U12(X, Y)) isNat(ok(X)) >? ok(isNat(X)) U13(ok(X)) >? ok(U13(X)) U21(ok(X), ok(Y)) >? ok(U21(X, Y)) U22(ok(X)) >? ok(U22(X)) U31(ok(X), ok(Y), ok(Z)) >? ok(U31(X, Y, Z)) U32(ok(X), ok(Y)) >? ok(U32(X, Y)) U33(ok(X)) >? ok(U33(X)) U41(ok(X), ok(Y)) >? ok(U41(X, Y)) U51(ok(X), ok(Y), ok(Z)) >? ok(U51(X, Y, Z)) s(ok(X)) >? ok(s(X)) plus(ok(X), ok(Y)) >? ok(plus(X, Y)) U61(ok(X)) >? ok(U61(X)) U71(ok(X), ok(Y), ok(Z)) >? ok(U71(X, Y, Z)) x(ok(X), ok(Y)) >? ok(x(X, Y)) and(ok(X), ok(Y)) >? ok(and(X, Y)) isNatKind(ok(X)) >? ok(isNatKind(X)) top(ok(X)) >? top(active(X)) We orient these requirements with a polynomial interpretation in the natural numbers. The following interpretation satisfies the requirements: 0 = 1 U11 = \y0y1y2.y0 + y2 + 2y1 U12 = \y0y1.y0 + 2y1 U13 = \y0.2y0 U21 = \y0y1.2y0 + 2y1 U22 = \y0.2y0 U31 = \y0y1y2.y0 + y1 + y2 U32 = \y0y1.2y0 + 2y1 U33 = \y0.2y0 U41 = \y0y1.y1 + 2y0 U51 = \y0y1y2.y1 + 2y0 + 2y2 U61 = \y0.y0 U71 = \y0y1y2.y1 + y2 + 2y0 active = \y0.2y0 and = \y0y1.y1 + 2y0 isNat = \y0.2y0 isNatKind = \y0.y0 mark = \y0.y0 ok = \y0.2y0 plus = \y0y1.y0 + y1 proper = \y0.3y0 s = \y0.2y0 top = \y0.y0 tt = 1 x = \y0y1.y0 + y1 Using this interpretation, the requirements translate to: [[active(U13(tt))]] = 4 > 1 = [[mark(tt)]] [[active(U61(tt))]] = 2 > 1 = [[mark(0)]] [[active(isNat(0))]] = 4 > 1 = [[mark(tt)]] [[active(U11(_x0, _x1, _x2))]] = 2x0 + 2x2 + 4x1 >= x2 + 2x0 + 2x1 = [[U11(active(_x0), _x1, _x2)]] [[active(U12(_x0, _x1))]] = 2x0 + 4x1 >= 2x0 + 2x1 = [[U12(active(_x0), _x1)]] [[active(U13(_x0))]] = 4x0 >= 4x0 = [[U13(active(_x0))]] [[active(U21(_x0, _x1))]] = 4x0 + 4x1 >= 2x1 + 4x0 = [[U21(active(_x0), _x1)]] [[active(U22(_x0))]] = 4x0 >= 4x0 = [[U22(active(_x0))]] [[active(U31(_x0, _x1, _x2))]] = 2x0 + 2x1 + 2x2 >= x1 + x2 + 2x0 = [[U31(active(_x0), _x1, _x2)]] [[active(U32(_x0, _x1))]] = 4x0 + 4x1 >= 2x1 + 4x0 = [[U32(active(_x0), _x1)]] [[active(U33(_x0))]] = 4x0 >= 4x0 = [[U33(active(_x0))]] [[active(U41(_x0, _x1))]] = 2x1 + 4x0 >= x1 + 4x0 = [[U41(active(_x0), _x1)]] [[active(U51(_x0, _x1, _x2))]] = 2x1 + 4x0 + 4x2 >= x1 + 2x2 + 4x0 = [[U51(active(_x0), _x1, _x2)]] [[active(s(_x0))]] = 4x0 >= 4x0 = [[s(active(_x0))]] [[active(plus(_x0, _x1))]] = 2x0 + 2x1 >= x1 + 2x0 = [[plus(active(_x0), _x1)]] [[active(plus(_x0, _x1))]] = 2x0 + 2x1 >= x0 + 2x1 = [[plus(_x0, active(_x1))]] [[active(U61(_x0))]] = 2x0 >= 2x0 = [[U61(active(_x0))]] [[active(U71(_x0, _x1, _x2))]] = 2x1 + 2x2 + 4x0 >= x1 + x2 + 4x0 = [[U71(active(_x0), _x1, _x2)]] [[active(x(_x0, _x1))]] = 2x0 + 2x1 >= x1 + 2x0 = [[x(active(_x0), _x1)]] [[active(x(_x0, _x1))]] = 2x0 + 2x1 >= x0 + 2x1 = [[x(_x0, active(_x1))]] [[active(and(_x0, _x1))]] = 2x1 + 4x0 >= x1 + 4x0 = [[and(active(_x0), _x1)]] [[U11(mark(_x0), _x1, _x2)]] = x0 + x2 + 2x1 >= x0 + x2 + 2x1 = [[mark(U11(_x0, _x1, _x2))]] [[U13(mark(_x0))]] = 2x0 >= 2x0 = [[mark(U13(_x0))]] [[U21(mark(_x0), _x1)]] = 2x0 + 2x1 >= 2x0 + 2x1 = [[mark(U21(_x0, _x1))]] [[U31(mark(_x0), _x1, _x2)]] = x0 + x1 + x2 >= x0 + x1 + x2 = [[mark(U31(_x0, _x1, _x2))]] [[U33(mark(_x0))]] = 2x0 >= 2x0 = [[mark(U33(_x0))]] [[U41(mark(_x0), _x1)]] = x1 + 2x0 >= x1 + 2x0 = [[mark(U41(_x0, _x1))]] [[s(mark(_x0))]] = 2x0 >= 2x0 = [[mark(s(_x0))]] [[U61(mark(_x0))]] = x0 >= x0 = [[mark(U61(_x0))]] [[U71(mark(_x0), _x1, _x2)]] = x1 + x2 + 2x0 >= x1 + x2 + 2x0 = [[mark(U71(_x0, _x1, _x2))]] [[x(mark(_x0), _x1)]] = x0 + x1 >= x0 + x1 = [[mark(x(_x0, _x1))]] [[proper(U11(_x0, _x1, _x2))]] = 3x0 + 3x2 + 6x1 >= 3x0 + 3x2 + 6x1 = [[U11(proper(_x0), proper(_x1), proper(_x2))]] [[proper(isNat(_x0))]] = 6x0 >= 6x0 = [[isNat(proper(_x0))]] [[proper(U13(_x0))]] = 6x0 >= 6x0 = [[U13(proper(_x0))]] [[proper(U21(_x0, _x1))]] = 6x0 + 6x1 >= 6x0 + 6x1 = [[U21(proper(_x0), proper(_x1))]] [[proper(U22(_x0))]] = 6x0 >= 6x0 = [[U22(proper(_x0))]] [[proper(U31(_x0, _x1, _x2))]] = 3x0 + 3x1 + 3x2 >= 3x0 + 3x1 + 3x2 = [[U31(proper(_x0), proper(_x1), proper(_x2))]] [[proper(U32(_x0, _x1))]] = 6x0 + 6x1 >= 6x0 + 6x1 = [[U32(proper(_x0), proper(_x1))]] [[proper(U33(_x0))]] = 6x0 >= 6x0 = [[U33(proper(_x0))]] [[proper(U41(_x0, _x1))]] = 3x1 + 6x0 >= 3x1 + 6x0 = [[U41(proper(_x0), proper(_x1))]] [[proper(U51(_x0, _x1, _x2))]] = 3x1 + 6x0 + 6x2 >= 3x1 + 6x0 + 6x2 = [[U51(proper(_x0), proper(_x1), proper(_x2))]] [[proper(s(_x0))]] = 6x0 >= 6x0 = [[s(proper(_x0))]] [[proper(plus(_x0, _x1))]] = 3x0 + 3x1 >= 3x0 + 3x1 = [[plus(proper(_x0), proper(_x1))]] [[proper(U61(_x0))]] = 3x0 >= 3x0 = [[U61(proper(_x0))]] [[proper(U71(_x0, _x1, _x2))]] = 3x1 + 3x2 + 6x0 >= 3x1 + 3x2 + 6x0 = [[U71(proper(_x0), proper(_x1), proper(_x2))]] [[proper(x(_x0, _x1))]] = 3x0 + 3x1 >= 3x0 + 3x1 = [[x(proper(_x0), proper(_x1))]] [[proper(and(_x0, _x1))]] = 3x1 + 6x0 >= 3x1 + 6x0 = [[and(proper(_x0), proper(_x1))]] [[proper(isNatKind(_x0))]] = 3x0 >= 3x0 = [[isNatKind(proper(_x0))]] [[U11(ok(_x0), ok(_x1), ok(_x2))]] = 2x0 + 2x2 + 4x1 >= 2x0 + 2x2 + 4x1 = [[ok(U11(_x0, _x1, _x2))]] [[U12(ok(_x0), ok(_x1))]] = 2x0 + 4x1 >= 2x0 + 4x1 = [[ok(U12(_x0, _x1))]] [[isNat(ok(_x0))]] = 4x0 >= 4x0 = [[ok(isNat(_x0))]] [[U13(ok(_x0))]] = 4x0 >= 4x0 = [[ok(U13(_x0))]] [[U21(ok(_x0), ok(_x1))]] = 4x0 + 4x1 >= 4x0 + 4x1 = [[ok(U21(_x0, _x1))]] [[U22(ok(_x0))]] = 4x0 >= 4x0 = [[ok(U22(_x0))]] [[U31(ok(_x0), ok(_x1), ok(_x2))]] = 2x0 + 2x1 + 2x2 >= 2x0 + 2x1 + 2x2 = [[ok(U31(_x0, _x1, _x2))]] [[U32(ok(_x0), ok(_x1))]] = 4x0 + 4x1 >= 4x0 + 4x1 = [[ok(U32(_x0, _x1))]] [[U33(ok(_x0))]] = 4x0 >= 4x0 = [[ok(U33(_x0))]] [[U41(ok(_x0), ok(_x1))]] = 2x1 + 4x0 >= 2x1 + 4x0 = [[ok(U41(_x0, _x1))]] [[U51(ok(_x0), ok(_x1), ok(_x2))]] = 2x1 + 4x0 + 4x2 >= 2x1 + 4x0 + 4x2 = [[ok(U51(_x0, _x1, _x2))]] [[s(ok(_x0))]] = 4x0 >= 4x0 = [[ok(s(_x0))]] [[plus(ok(_x0), ok(_x1))]] = 2x0 + 2x1 >= 2x0 + 2x1 = [[ok(plus(_x0, _x1))]] [[U61(ok(_x0))]] = 2x0 >= 2x0 = [[ok(U61(_x0))]] [[U71(ok(_x0), ok(_x1), ok(_x2))]] = 2x1 + 2x2 + 4x0 >= 2x1 + 2x2 + 4x0 = [[ok(U71(_x0, _x1, _x2))]] [[x(ok(_x0), ok(_x1))]] = 2x0 + 2x1 >= 2x0 + 2x1 = [[ok(x(_x0, _x1))]] [[and(ok(_x0), ok(_x1))]] = 2x1 + 4x0 >= 2x1 + 4x0 = [[ok(and(_x0, _x1))]] [[isNatKind(ok(_x0))]] = 2x0 >= 2x0 = [[ok(isNatKind(_x0))]] [[top(ok(_x0))]] = 2x0 >= 2x0 = [[top(active(_x0))]] We can thus remove the following rules: active(U13(tt)) => mark(tt) active(U61(tt)) => mark(0) active(isNat(0)) => mark(tt) We use rule removal, following [Kop12, Theorem 2.23]. This gives the following requirements (possibly using Theorems 2.25 and 2.26 in [Kop12]): active(U11(X, Y, Z)) >? U11(active(X), Y, Z) active(U12(X, Y)) >? U12(active(X), Y) active(U13(X)) >? U13(active(X)) active(U21(X, Y)) >? U21(active(X), Y) active(U22(X)) >? U22(active(X)) active(U31(X, Y, Z)) >? U31(active(X), Y, Z) active(U32(X, Y)) >? U32(active(X), Y) active(U33(X)) >? U33(active(X)) active(U41(X, Y)) >? U41(active(X), Y) active(U51(X, Y, Z)) >? U51(active(X), Y, Z) active(s(X)) >? s(active(X)) active(plus(X, Y)) >? plus(active(X), Y) active(plus(X, Y)) >? plus(X, active(Y)) active(U61(X)) >? U61(active(X)) active(U71(X, Y, Z)) >? U71(active(X), Y, Z) active(x(X, Y)) >? x(active(X), Y) active(x(X, Y)) >? x(X, active(Y)) active(and(X, Y)) >? and(active(X), Y) U11(mark(X), Y, Z) >? mark(U11(X, Y, Z)) U13(mark(X)) >? mark(U13(X)) U21(mark(X), Y) >? mark(U21(X, Y)) U31(mark(X), Y, Z) >? mark(U31(X, Y, Z)) U33(mark(X)) >? mark(U33(X)) U41(mark(X), Y) >? mark(U41(X, Y)) s(mark(X)) >? mark(s(X)) U61(mark(X)) >? mark(U61(X)) U71(mark(X), Y, Z) >? mark(U71(X, Y, Z)) x(mark(X), Y) >? mark(x(X, Y)) proper(U11(X, Y, Z)) >? U11(proper(X), proper(Y), proper(Z)) proper(isNat(X)) >? isNat(proper(X)) proper(U13(X)) >? U13(proper(X)) proper(U21(X, Y)) >? U21(proper(X), proper(Y)) proper(U22(X)) >? U22(proper(X)) proper(U31(X, Y, Z)) >? U31(proper(X), proper(Y), proper(Z)) proper(U32(X, Y)) >? U32(proper(X), proper(Y)) proper(U33(X)) >? U33(proper(X)) proper(U41(X, Y)) >? U41(proper(X), proper(Y)) proper(U51(X, Y, Z)) >? U51(proper(X), proper(Y), proper(Z)) proper(s(X)) >? s(proper(X)) proper(plus(X, Y)) >? plus(proper(X), proper(Y)) proper(U61(X)) >? U61(proper(X)) proper(U71(X, Y, Z)) >? U71(proper(X), proper(Y), proper(Z)) proper(x(X, Y)) >? x(proper(X), proper(Y)) proper(and(X, Y)) >? and(proper(X), proper(Y)) proper(isNatKind(X)) >? isNatKind(proper(X)) U11(ok(X), ok(Y), ok(Z)) >? ok(U11(X, Y, Z)) U12(ok(X), ok(Y)) >? ok(U12(X, Y)) isNat(ok(X)) >? ok(isNat(X)) U13(ok(X)) >? ok(U13(X)) U21(ok(X), ok(Y)) >? ok(U21(X, Y)) U22(ok(X)) >? ok(U22(X)) U31(ok(X), ok(Y), ok(Z)) >? ok(U31(X, Y, Z)) U32(ok(X), ok(Y)) >? ok(U32(X, Y)) U33(ok(X)) >? ok(U33(X)) U41(ok(X), ok(Y)) >? ok(U41(X, Y)) U51(ok(X), ok(Y), ok(Z)) >? ok(U51(X, Y, Z)) s(ok(X)) >? ok(s(X)) plus(ok(X), ok(Y)) >? ok(plus(X, Y)) U61(ok(X)) >? ok(U61(X)) U71(ok(X), ok(Y), ok(Z)) >? ok(U71(X, Y, Z)) x(ok(X), ok(Y)) >? ok(x(X, Y)) and(ok(X), ok(Y)) >? ok(and(X, Y)) isNatKind(ok(X)) >? ok(isNatKind(X)) top(ok(X)) >? top(active(X)) We orient these requirements with a polynomial interpretation in the natural numbers. The following interpretation satisfies the requirements: U11 = \y0y1y2.y1 + y2 + 2y0 U12 = \y0y1.y0 + y1 U13 = \y0.1 + 2y0 U21 = \y0y1.y1 + 2y0 U22 = \y0.y0 U31 = \y0y1y2.y0 + y1 + y2 U32 = \y0y1.y0 + 2y1 U33 = \y0.1 + y0 U41 = \y0y1.y1 + 2y0 U51 = \y0y1y2.y0 + y1 + y2 U61 = \y0.y0 U71 = \y0y1y2.y1 + y2 + 2y0 active = \y0.y0 and = \y0y1.y0 + y1 isNat = \y0.2 + y0 isNatKind = \y0.2y0 mark = \y0.y0 ok = \y0.y0 plus = \y0y1.y0 + 2y1 proper = \y0.3y0 s = \y0.2y0 top = \y0.y0 x = \y0y1.y0 + y1 Using this interpretation, the requirements translate to: [[active(U11(_x0, _x1, _x2))]] = x1 + x2 + 2x0 >= x1 + x2 + 2x0 = [[U11(active(_x0), _x1, _x2)]] [[active(U12(_x0, _x1))]] = x0 + x1 >= x0 + x1 = [[U12(active(_x0), _x1)]] [[active(U13(_x0))]] = 1 + 2x0 >= 1 + 2x0 = [[U13(active(_x0))]] [[active(U21(_x0, _x1))]] = x1 + 2x0 >= x1 + 2x0 = [[U21(active(_x0), _x1)]] [[active(U22(_x0))]] = x0 >= x0 = [[U22(active(_x0))]] [[active(U31(_x0, _x1, _x2))]] = x0 + x1 + x2 >= x0 + x1 + x2 = [[U31(active(_x0), _x1, _x2)]] [[active(U32(_x0, _x1))]] = x0 + 2x1 >= x0 + 2x1 = [[U32(active(_x0), _x1)]] [[active(U33(_x0))]] = 1 + x0 >= 1 + x0 = [[U33(active(_x0))]] [[active(U41(_x0, _x1))]] = x1 + 2x0 >= x1 + 2x0 = [[U41(active(_x0), _x1)]] [[active(U51(_x0, _x1, _x2))]] = x0 + x1 + x2 >= x0 + x1 + x2 = [[U51(active(_x0), _x1, _x2)]] [[active(s(_x0))]] = 2x0 >= 2x0 = [[s(active(_x0))]] [[active(plus(_x0, _x1))]] = x0 + 2x1 >= x0 + 2x1 = [[plus(active(_x0), _x1)]] [[active(plus(_x0, _x1))]] = x0 + 2x1 >= x0 + 2x1 = [[plus(_x0, active(_x1))]] [[active(U61(_x0))]] = x0 >= x0 = [[U61(active(_x0))]] [[active(U71(_x0, _x1, _x2))]] = x1 + x2 + 2x0 >= x1 + x2 + 2x0 = [[U71(active(_x0), _x1, _x2)]] [[active(x(_x0, _x1))]] = x0 + x1 >= x0 + x1 = [[x(active(_x0), _x1)]] [[active(x(_x0, _x1))]] = x0 + x1 >= x0 + x1 = [[x(_x0, active(_x1))]] [[active(and(_x0, _x1))]] = x0 + x1 >= x0 + x1 = [[and(active(_x0), _x1)]] [[U11(mark(_x0), _x1, _x2)]] = x1 + x2 + 2x0 >= x1 + x2 + 2x0 = [[mark(U11(_x0, _x1, _x2))]] [[U13(mark(_x0))]] = 1 + 2x0 >= 1 + 2x0 = [[mark(U13(_x0))]] [[U21(mark(_x0), _x1)]] = x1 + 2x0 >= x1 + 2x0 = [[mark(U21(_x0, _x1))]] [[U31(mark(_x0), _x1, _x2)]] = x0 + x1 + x2 >= x0 + x1 + x2 = [[mark(U31(_x0, _x1, _x2))]] [[U33(mark(_x0))]] = 1 + x0 >= 1 + x0 = [[mark(U33(_x0))]] [[U41(mark(_x0), _x1)]] = x1 + 2x0 >= x1 + 2x0 = [[mark(U41(_x0, _x1))]] [[s(mark(_x0))]] = 2x0 >= 2x0 = [[mark(s(_x0))]] [[U61(mark(_x0))]] = x0 >= x0 = [[mark(U61(_x0))]] [[U71(mark(_x0), _x1, _x2)]] = x1 + x2 + 2x0 >= x1 + x2 + 2x0 = [[mark(U71(_x0, _x1, _x2))]] [[x(mark(_x0), _x1)]] = x0 + x1 >= x0 + x1 = [[mark(x(_x0, _x1))]] [[proper(U11(_x0, _x1, _x2))]] = 3x1 + 3x2 + 6x0 >= 3x1 + 3x2 + 6x0 = [[U11(proper(_x0), proper(_x1), proper(_x2))]] [[proper(isNat(_x0))]] = 6 + 3x0 > 2 + 3x0 = [[isNat(proper(_x0))]] [[proper(U13(_x0))]] = 3 + 6x0 > 1 + 6x0 = [[U13(proper(_x0))]] [[proper(U21(_x0, _x1))]] = 3x1 + 6x0 >= 3x1 + 6x0 = [[U21(proper(_x0), proper(_x1))]] [[proper(U22(_x0))]] = 3x0 >= 3x0 = [[U22(proper(_x0))]] [[proper(U31(_x0, _x1, _x2))]] = 3x0 + 3x1 + 3x2 >= 3x0 + 3x1 + 3x2 = [[U31(proper(_x0), proper(_x1), proper(_x2))]] [[proper(U32(_x0, _x1))]] = 3x0 + 6x1 >= 3x0 + 6x1 = [[U32(proper(_x0), proper(_x1))]] [[proper(U33(_x0))]] = 3 + 3x0 > 1 + 3x0 = [[U33(proper(_x0))]] [[proper(U41(_x0, _x1))]] = 3x1 + 6x0 >= 3x1 + 6x0 = [[U41(proper(_x0), proper(_x1))]] [[proper(U51(_x0, _x1, _x2))]] = 3x0 + 3x1 + 3x2 >= 3x0 + 3x1 + 3x2 = [[U51(proper(_x0), proper(_x1), proper(_x2))]] [[proper(s(_x0))]] = 6x0 >= 6x0 = [[s(proper(_x0))]] [[proper(plus(_x0, _x1))]] = 3x0 + 6x1 >= 3x0 + 6x1 = [[plus(proper(_x0), proper(_x1))]] [[proper(U61(_x0))]] = 3x0 >= 3x0 = [[U61(proper(_x0))]] [[proper(U71(_x0, _x1, _x2))]] = 3x1 + 3x2 + 6x0 >= 3x1 + 3x2 + 6x0 = [[U71(proper(_x0), proper(_x1), proper(_x2))]] [[proper(x(_x0, _x1))]] = 3x0 + 3x1 >= 3x0 + 3x1 = [[x(proper(_x0), proper(_x1))]] [[proper(and(_x0, _x1))]] = 3x0 + 3x1 >= 3x0 + 3x1 = [[and(proper(_x0), proper(_x1))]] [[proper(isNatKind(_x0))]] = 6x0 >= 6x0 = [[isNatKind(proper(_x0))]] [[U11(ok(_x0), ok(_x1), ok(_x2))]] = x1 + x2 + 2x0 >= x1 + x2 + 2x0 = [[ok(U11(_x0, _x1, _x2))]] [[U12(ok(_x0), ok(_x1))]] = x0 + x1 >= x0 + x1 = [[ok(U12(_x0, _x1))]] [[isNat(ok(_x0))]] = 2 + x0 >= 2 + x0 = [[ok(isNat(_x0))]] [[U13(ok(_x0))]] = 1 + 2x0 >= 1 + 2x0 = [[ok(U13(_x0))]] [[U21(ok(_x0), ok(_x1))]] = x1 + 2x0 >= x1 + 2x0 = [[ok(U21(_x0, _x1))]] [[U22(ok(_x0))]] = x0 >= x0 = [[ok(U22(_x0))]] [[U31(ok(_x0), ok(_x1), ok(_x2))]] = x0 + x1 + x2 >= x0 + x1 + x2 = [[ok(U31(_x0, _x1, _x2))]] [[U32(ok(_x0), ok(_x1))]] = x0 + 2x1 >= x0 + 2x1 = [[ok(U32(_x0, _x1))]] [[U33(ok(_x0))]] = 1 + x0 >= 1 + x0 = [[ok(U33(_x0))]] [[U41(ok(_x0), ok(_x1))]] = x1 + 2x0 >= x1 + 2x0 = [[ok(U41(_x0, _x1))]] [[U51(ok(_x0), ok(_x1), ok(_x2))]] = x0 + x1 + x2 >= x0 + x1 + x2 = [[ok(U51(_x0, _x1, _x2))]] [[s(ok(_x0))]] = 2x0 >= 2x0 = [[ok(s(_x0))]] [[plus(ok(_x0), ok(_x1))]] = x0 + 2x1 >= x0 + 2x1 = [[ok(plus(_x0, _x1))]] [[U61(ok(_x0))]] = x0 >= x0 = [[ok(U61(_x0))]] [[U71(ok(_x0), ok(_x1), ok(_x2))]] = x1 + x2 + 2x0 >= x1 + x2 + 2x0 = [[ok(U71(_x0, _x1, _x2))]] [[x(ok(_x0), ok(_x1))]] = x0 + x1 >= x0 + x1 = [[ok(x(_x0, _x1))]] [[and(ok(_x0), ok(_x1))]] = x0 + x1 >= x0 + x1 = [[ok(and(_x0, _x1))]] [[isNatKind(ok(_x0))]] = 2x0 >= 2x0 = [[ok(isNatKind(_x0))]] [[top(ok(_x0))]] = x0 >= x0 = [[top(active(_x0))]] We can thus remove the following rules: proper(isNat(X)) => isNat(proper(X)) proper(U13(X)) => U13(proper(X)) proper(U33(X)) => U33(proper(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]): active(U11(X, Y, Z)) >? U11(active(X), Y, Z) active(U12(X, Y)) >? U12(active(X), Y) active(U13(X)) >? U13(active(X)) active(U21(X, Y)) >? U21(active(X), Y) active(U22(X)) >? U22(active(X)) active(U31(X, Y, Z)) >? U31(active(X), Y, Z) active(U32(X, Y)) >? U32(active(X), Y) active(U33(X)) >? U33(active(X)) active(U41(X, Y)) >? U41(active(X), Y) active(U51(X, Y, Z)) >? U51(active(X), Y, Z) active(s(X)) >? s(active(X)) active(plus(X, Y)) >? plus(active(X), Y) active(plus(X, Y)) >? plus(X, active(Y)) active(U61(X)) >? U61(active(X)) active(U71(X, Y, Z)) >? U71(active(X), Y, Z) active(x(X, Y)) >? x(active(X), Y) active(x(X, Y)) >? x(X, active(Y)) active(and(X, Y)) >? and(active(X), Y) U11(mark(X), Y, Z) >? mark(U11(X, Y, Z)) U13(mark(X)) >? mark(U13(X)) U21(mark(X), Y) >? mark(U21(X, Y)) U31(mark(X), Y, Z) >? mark(U31(X, Y, Z)) U33(mark(X)) >? mark(U33(X)) U41(mark(X), Y) >? mark(U41(X, Y)) s(mark(X)) >? mark(s(X)) U61(mark(X)) >? mark(U61(X)) U71(mark(X), Y, Z) >? mark(U71(X, Y, Z)) x(mark(X), Y) >? mark(x(X, Y)) proper(U11(X, Y, Z)) >? U11(proper(X), proper(Y), proper(Z)) proper(U21(X, Y)) >? U21(proper(X), proper(Y)) proper(U22(X)) >? U22(proper(X)) proper(U31(X, Y, Z)) >? U31(proper(X), proper(Y), proper(Z)) proper(U32(X, Y)) >? U32(proper(X), proper(Y)) proper(U41(X, Y)) >? U41(proper(X), proper(Y)) proper(U51(X, Y, Z)) >? U51(proper(X), proper(Y), proper(Z)) proper(s(X)) >? s(proper(X)) proper(plus(X, Y)) >? plus(proper(X), proper(Y)) proper(U61(X)) >? U61(proper(X)) proper(U71(X, Y, Z)) >? U71(proper(X), proper(Y), proper(Z)) proper(x(X, Y)) >? x(proper(X), proper(Y)) proper(and(X, Y)) >? and(proper(X), proper(Y)) proper(isNatKind(X)) >? isNatKind(proper(X)) U11(ok(X), ok(Y), ok(Z)) >? ok(U11(X, Y, Z)) U12(ok(X), ok(Y)) >? ok(U12(X, Y)) isNat(ok(X)) >? ok(isNat(X)) U13(ok(X)) >? ok(U13(X)) U21(ok(X), ok(Y)) >? ok(U21(X, Y)) U22(ok(X)) >? ok(U22(X)) U31(ok(X), ok(Y), ok(Z)) >? ok(U31(X, Y, Z)) U32(ok(X), ok(Y)) >? ok(U32(X, Y)) U33(ok(X)) >? ok(U33(X)) U41(ok(X), ok(Y)) >? ok(U41(X, Y)) U51(ok(X), ok(Y), ok(Z)) >? ok(U51(X, Y, Z)) s(ok(X)) >? ok(s(X)) plus(ok(X), ok(Y)) >? ok(plus(X, Y)) U61(ok(X)) >? ok(U61(X)) U71(ok(X), ok(Y), ok(Z)) >? ok(U71(X, Y, Z)) x(ok(X), ok(Y)) >? ok(x(X, Y)) and(ok(X), ok(Y)) >? ok(and(X, Y)) isNatKind(ok(X)) >? ok(isNatKind(X)) top(ok(X)) >? top(active(X)) We orient these requirements with a polynomial interpretation in the natural numbers. The following interpretation satisfies the requirements: U11 = \y0y1y2.y0 + 2y1 + 2y2 U12 = \y0y1.2y0 + 2y1 U13 = \y0.y0 U21 = \y0y1.y1 + 2y0 U22 = \y0.y0 U31 = \y0y1y2.y0 + y1 + 2y2 U32 = \y0y1.y1 + 2y0 U33 = \y0.2y0 U41 = \y0y1.y0 + 2y1 U51 = \y0y1y2.y1 + y2 + 2y0 U61 = \y0.2y0 U71 = \y0y1y2.y0 + y1 + y2 active = \y0.2y0 and = \y0y1.y1 + 2y0 isNat = \y0.3y0 isNatKind = \y0.y0 mark = \y0.1 + y0 ok = \y0.2y0 plus = \y0y1.y0 + 2y1 proper = \y0.3y0 s = \y0.2y0 top = \y0.y0 x = \y0y1.2y0 + 2y1 Using this interpretation, the requirements translate to: [[active(U11(_x0, _x1, _x2))]] = 2x0 + 4x1 + 4x2 >= 2x0 + 2x1 + 2x2 = [[U11(active(_x0), _x1, _x2)]] [[active(U12(_x0, _x1))]] = 4x0 + 4x1 >= 2x1 + 4x0 = [[U12(active(_x0), _x1)]] [[active(U13(_x0))]] = 2x0 >= 2x0 = [[U13(active(_x0))]] [[active(U21(_x0, _x1))]] = 2x1 + 4x0 >= x1 + 4x0 = [[U21(active(_x0), _x1)]] [[active(U22(_x0))]] = 2x0 >= 2x0 = [[U22(active(_x0))]] [[active(U31(_x0, _x1, _x2))]] = 2x0 + 2x1 + 4x2 >= x1 + 2x0 + 2x2 = [[U31(active(_x0), _x1, _x2)]] [[active(U32(_x0, _x1))]] = 2x1 + 4x0 >= x1 + 4x0 = [[U32(active(_x0), _x1)]] [[active(U33(_x0))]] = 4x0 >= 4x0 = [[U33(active(_x0))]] [[active(U41(_x0, _x1))]] = 2x0 + 4x1 >= 2x0 + 2x1 = [[U41(active(_x0), _x1)]] [[active(U51(_x0, _x1, _x2))]] = 2x1 + 2x2 + 4x0 >= x1 + x2 + 4x0 = [[U51(active(_x0), _x1, _x2)]] [[active(s(_x0))]] = 4x0 >= 4x0 = [[s(active(_x0))]] [[active(plus(_x0, _x1))]] = 2x0 + 4x1 >= 2x0 + 2x1 = [[plus(active(_x0), _x1)]] [[active(plus(_x0, _x1))]] = 2x0 + 4x1 >= x0 + 4x1 = [[plus(_x0, active(_x1))]] [[active(U61(_x0))]] = 4x0 >= 4x0 = [[U61(active(_x0))]] [[active(U71(_x0, _x1, _x2))]] = 2x0 + 2x1 + 2x2 >= x1 + x2 + 2x0 = [[U71(active(_x0), _x1, _x2)]] [[active(x(_x0, _x1))]] = 4x0 + 4x1 >= 2x1 + 4x0 = [[x(active(_x0), _x1)]] [[active(x(_x0, _x1))]] = 4x0 + 4x1 >= 2x0 + 4x1 = [[x(_x0, active(_x1))]] [[active(and(_x0, _x1))]] = 2x1 + 4x0 >= x1 + 4x0 = [[and(active(_x0), _x1)]] [[U11(mark(_x0), _x1, _x2)]] = 1 + x0 + 2x1 + 2x2 >= 1 + x0 + 2x1 + 2x2 = [[mark(U11(_x0, _x1, _x2))]] [[U13(mark(_x0))]] = 1 + x0 >= 1 + x0 = [[mark(U13(_x0))]] [[U21(mark(_x0), _x1)]] = 2 + x1 + 2x0 > 1 + x1 + 2x0 = [[mark(U21(_x0, _x1))]] [[U31(mark(_x0), _x1, _x2)]] = 1 + x0 + x1 + 2x2 >= 1 + x0 + x1 + 2x2 = [[mark(U31(_x0, _x1, _x2))]] [[U33(mark(_x0))]] = 2 + 2x0 > 1 + 2x0 = [[mark(U33(_x0))]] [[U41(mark(_x0), _x1)]] = 1 + x0 + 2x1 >= 1 + x0 + 2x1 = [[mark(U41(_x0, _x1))]] [[s(mark(_x0))]] = 2 + 2x0 > 1 + 2x0 = [[mark(s(_x0))]] [[U61(mark(_x0))]] = 2 + 2x0 > 1 + 2x0 = [[mark(U61(_x0))]] [[U71(mark(_x0), _x1, _x2)]] = 1 + x0 + x1 + x2 >= 1 + x0 + x1 + x2 = [[mark(U71(_x0, _x1, _x2))]] [[x(mark(_x0), _x1)]] = 2 + 2x0 + 2x1 > 1 + 2x0 + 2x1 = [[mark(x(_x0, _x1))]] [[proper(U11(_x0, _x1, _x2))]] = 3x0 + 6x1 + 6x2 >= 3x0 + 6x1 + 6x2 = [[U11(proper(_x0), proper(_x1), proper(_x2))]] [[proper(U21(_x0, _x1))]] = 3x1 + 6x0 >= 3x1 + 6x0 = [[U21(proper(_x0), proper(_x1))]] [[proper(U22(_x0))]] = 3x0 >= 3x0 = [[U22(proper(_x0))]] [[proper(U31(_x0, _x1, _x2))]] = 3x0 + 3x1 + 6x2 >= 3x0 + 3x1 + 6x2 = [[U31(proper(_x0), proper(_x1), proper(_x2))]] [[proper(U32(_x0, _x1))]] = 3x1 + 6x0 >= 3x1 + 6x0 = [[U32(proper(_x0), proper(_x1))]] [[proper(U41(_x0, _x1))]] = 3x0 + 6x1 >= 3x0 + 6x1 = [[U41(proper(_x0), proper(_x1))]] [[proper(U51(_x0, _x1, _x2))]] = 3x1 + 3x2 + 6x0 >= 3x1 + 3x2 + 6x0 = [[U51(proper(_x0), proper(_x1), proper(_x2))]] [[proper(s(_x0))]] = 6x0 >= 6x0 = [[s(proper(_x0))]] [[proper(plus(_x0, _x1))]] = 3x0 + 6x1 >= 3x0 + 6x1 = [[plus(proper(_x0), proper(_x1))]] [[proper(U61(_x0))]] = 6x0 >= 6x0 = [[U61(proper(_x0))]] [[proper(U71(_x0, _x1, _x2))]] = 3x0 + 3x1 + 3x2 >= 3x0 + 3x1 + 3x2 = [[U71(proper(_x0), proper(_x1), proper(_x2))]] [[proper(x(_x0, _x1))]] = 6x0 + 6x1 >= 6x0 + 6x1 = [[x(proper(_x0), proper(_x1))]] [[proper(and(_x0, _x1))]] = 3x1 + 6x0 >= 3x1 + 6x0 = [[and(proper(_x0), proper(_x1))]] [[proper(isNatKind(_x0))]] = 3x0 >= 3x0 = [[isNatKind(proper(_x0))]] [[U11(ok(_x0), ok(_x1), ok(_x2))]] = 2x0 + 4x1 + 4x2 >= 2x0 + 4x1 + 4x2 = [[ok(U11(_x0, _x1, _x2))]] [[U12(ok(_x0), ok(_x1))]] = 4x0 + 4x1 >= 4x0 + 4x1 = [[ok(U12(_x0, _x1))]] [[isNat(ok(_x0))]] = 6x0 >= 6x0 = [[ok(isNat(_x0))]] [[U13(ok(_x0))]] = 2x0 >= 2x0 = [[ok(U13(_x0))]] [[U21(ok(_x0), ok(_x1))]] = 2x1 + 4x0 >= 2x1 + 4x0 = [[ok(U21(_x0, _x1))]] [[U22(ok(_x0))]] = 2x0 >= 2x0 = [[ok(U22(_x0))]] [[U31(ok(_x0), ok(_x1), ok(_x2))]] = 2x0 + 2x1 + 4x2 >= 2x0 + 2x1 + 4x2 = [[ok(U31(_x0, _x1, _x2))]] [[U32(ok(_x0), ok(_x1))]] = 2x1 + 4x0 >= 2x1 + 4x0 = [[ok(U32(_x0, _x1))]] [[U33(ok(_x0))]] = 4x0 >= 4x0 = [[ok(U33(_x0))]] [[U41(ok(_x0), ok(_x1))]] = 2x0 + 4x1 >= 2x0 + 4x1 = [[ok(U41(_x0, _x1))]] [[U51(ok(_x0), ok(_x1), ok(_x2))]] = 2x1 + 2x2 + 4x0 >= 2x1 + 2x2 + 4x0 = [[ok(U51(_x0, _x1, _x2))]] [[s(ok(_x0))]] = 4x0 >= 4x0 = [[ok(s(_x0))]] [[plus(ok(_x0), ok(_x1))]] = 2x0 + 4x1 >= 2x0 + 4x1 = [[ok(plus(_x0, _x1))]] [[U61(ok(_x0))]] = 4x0 >= 4x0 = [[ok(U61(_x0))]] [[U71(ok(_x0), ok(_x1), ok(_x2))]] = 2x0 + 2x1 + 2x2 >= 2x0 + 2x1 + 2x2 = [[ok(U71(_x0, _x1, _x2))]] [[x(ok(_x0), ok(_x1))]] = 4x0 + 4x1 >= 4x0 + 4x1 = [[ok(x(_x0, _x1))]] [[and(ok(_x0), ok(_x1))]] = 2x1 + 4x0 >= 2x1 + 4x0 = [[ok(and(_x0, _x1))]] [[isNatKind(ok(_x0))]] = 2x0 >= 2x0 = [[ok(isNatKind(_x0))]] [[top(ok(_x0))]] = 2x0 >= 2x0 = [[top(active(_x0))]] We can thus remove the following rules: U21(mark(X), Y) => mark(U21(X, Y)) U33(mark(X)) => mark(U33(X)) s(mark(X)) => mark(s(X)) U61(mark(X)) => mark(U61(X)) x(mark(X), Y) => mark(x(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]): active(U11(X, Y, Z)) >? U11(active(X), Y, Z) active(U12(X, Y)) >? U12(active(X), Y) active(U13(X)) >? U13(active(X)) active(U21(X, Y)) >? U21(active(X), Y) active(U22(X)) >? U22(active(X)) active(U31(X, Y, Z)) >? U31(active(X), Y, Z) active(U32(X, Y)) >? U32(active(X), Y) active(U33(X)) >? U33(active(X)) active(U41(X, Y)) >? U41(active(X), Y) active(U51(X, Y, Z)) >? U51(active(X), Y, Z) active(s(X)) >? s(active(X)) active(plus(X, Y)) >? plus(active(X), Y) active(plus(X, Y)) >? plus(X, active(Y)) active(U61(X)) >? U61(active(X)) active(U71(X, Y, Z)) >? U71(active(X), Y, Z) active(x(X, Y)) >? x(active(X), Y) active(x(X, Y)) >? x(X, active(Y)) active(and(X, Y)) >? and(active(X), Y) U11(mark(X), Y, Z) >? mark(U11(X, Y, Z)) U13(mark(X)) >? mark(U13(X)) U31(mark(X), Y, Z) >? mark(U31(X, Y, Z)) U41(mark(X), Y) >? mark(U41(X, Y)) U71(mark(X), Y, Z) >? mark(U71(X, Y, Z)) proper(U11(X, Y, Z)) >? U11(proper(X), proper(Y), proper(Z)) proper(U21(X, Y)) >? U21(proper(X), proper(Y)) proper(U22(X)) >? U22(proper(X)) proper(U31(X, Y, Z)) >? U31(proper(X), proper(Y), proper(Z)) proper(U32(X, Y)) >? U32(proper(X), proper(Y)) proper(U41(X, Y)) >? U41(proper(X), proper(Y)) proper(U51(X, Y, Z)) >? U51(proper(X), proper(Y), proper(Z)) proper(s(X)) >? s(proper(X)) proper(plus(X, Y)) >? plus(proper(X), proper(Y)) proper(U61(X)) >? U61(proper(X)) proper(U71(X, Y, Z)) >? U71(proper(X), proper(Y), proper(Z)) proper(x(X, Y)) >? x(proper(X), proper(Y)) proper(and(X, Y)) >? and(proper(X), proper(Y)) proper(isNatKind(X)) >? isNatKind(proper(X)) U11(ok(X), ok(Y), ok(Z)) >? ok(U11(X, Y, Z)) U12(ok(X), ok(Y)) >? ok(U12(X, Y)) isNat(ok(X)) >? ok(isNat(X)) U13(ok(X)) >? ok(U13(X)) U21(ok(X), ok(Y)) >? ok(U21(X, Y)) U22(ok(X)) >? ok(U22(X)) U31(ok(X), ok(Y), ok(Z)) >? ok(U31(X, Y, Z)) U32(ok(X), ok(Y)) >? ok(U32(X, Y)) U33(ok(X)) >? ok(U33(X)) U41(ok(X), ok(Y)) >? ok(U41(X, Y)) U51(ok(X), ok(Y), ok(Z)) >? ok(U51(X, Y, Z)) s(ok(X)) >? ok(s(X)) plus(ok(X), ok(Y)) >? ok(plus(X, Y)) U61(ok(X)) >? ok(U61(X)) U71(ok(X), ok(Y), ok(Z)) >? ok(U71(X, Y, Z)) x(ok(X), ok(Y)) >? ok(x(X, Y)) and(ok(X), ok(Y)) >? ok(and(X, Y)) isNatKind(ok(X)) >? ok(isNatKind(X)) top(ok(X)) >? top(active(X)) We orient these requirements with a polynomial interpretation in the natural numbers. The following interpretation satisfies the requirements: U11 = \y0y1y2.y1 + y2 + 2y0 U12 = \y0y1.y1 + 2y0 U13 = \y0.2y0 U21 = \y0y1.y0 + y1 U22 = \y0.y0 U31 = \y0y1y2.y1 + y2 + 2y0 U32 = \y0y1.2y0 + 2y1 U33 = \y0.y0 U41 = \y0y1.2y0 + 2y1 U51 = \y0y1y2.y1 + y2 + 2y0 U61 = \y0.y0 U71 = \y0y1y2.2y0 + 2y1 + 2y2 active = \y0.2y0 and = \y0y1.2y0 + 2y1 isNat = \y0.3y0 isNatKind = \y0.y0 mark = \y0.2 + y0 ok = \y0.2y0 plus = \y0y1.y0 + 2y1 proper = \y0.3y0 s = \y0.2y0 top = \y0.y0 x = \y0y1.2y0 + 2y1 Using this interpretation, the requirements translate to: [[active(U11(_x0, _x1, _x2))]] = 2x1 + 2x2 + 4x0 >= x1 + x2 + 4x0 = [[U11(active(_x0), _x1, _x2)]] [[active(U12(_x0, _x1))]] = 2x1 + 4x0 >= x1 + 4x0 = [[U12(active(_x0), _x1)]] [[active(U13(_x0))]] = 4x0 >= 4x0 = [[U13(active(_x0))]] [[active(U21(_x0, _x1))]] = 2x0 + 2x1 >= x1 + 2x0 = [[U21(active(_x0), _x1)]] [[active(U22(_x0))]] = 2x0 >= 2x0 = [[U22(active(_x0))]] [[active(U31(_x0, _x1, _x2))]] = 2x1 + 2x2 + 4x0 >= x1 + x2 + 4x0 = [[U31(active(_x0), _x1, _x2)]] [[active(U32(_x0, _x1))]] = 4x0 + 4x1 >= 2x1 + 4x0 = [[U32(active(_x0), _x1)]] [[active(U33(_x0))]] = 2x0 >= 2x0 = [[U33(active(_x0))]] [[active(U41(_x0, _x1))]] = 4x0 + 4x1 >= 2x1 + 4x0 = [[U41(active(_x0), _x1)]] [[active(U51(_x0, _x1, _x2))]] = 2x1 + 2x2 + 4x0 >= x1 + x2 + 4x0 = [[U51(active(_x0), _x1, _x2)]] [[active(s(_x0))]] = 4x0 >= 4x0 = [[s(active(_x0))]] [[active(plus(_x0, _x1))]] = 2x0 + 4x1 >= 2x0 + 2x1 = [[plus(active(_x0), _x1)]] [[active(plus(_x0, _x1))]] = 2x0 + 4x1 >= x0 + 4x1 = [[plus(_x0, active(_x1))]] [[active(U61(_x0))]] = 2x0 >= 2x0 = [[U61(active(_x0))]] [[active(U71(_x0, _x1, _x2))]] = 4x0 + 4x1 + 4x2 >= 2x1 + 2x2 + 4x0 = [[U71(active(_x0), _x1, _x2)]] [[active(x(_x0, _x1))]] = 4x0 + 4x1 >= 2x1 + 4x0 = [[x(active(_x0), _x1)]] [[active(x(_x0, _x1))]] = 4x0 + 4x1 >= 2x0 + 4x1 = [[x(_x0, active(_x1))]] [[active(and(_x0, _x1))]] = 4x0 + 4x1 >= 2x1 + 4x0 = [[and(active(_x0), _x1)]] [[U11(mark(_x0), _x1, _x2)]] = 4 + x1 + x2 + 2x0 > 2 + x1 + x2 + 2x0 = [[mark(U11(_x0, _x1, _x2))]] [[U13(mark(_x0))]] = 4 + 2x0 > 2 + 2x0 = [[mark(U13(_x0))]] [[U31(mark(_x0), _x1, _x2)]] = 4 + x1 + x2 + 2x0 > 2 + x1 + x2 + 2x0 = [[mark(U31(_x0, _x1, _x2))]] [[U41(mark(_x0), _x1)]] = 4 + 2x0 + 2x1 > 2 + 2x0 + 2x1 = [[mark(U41(_x0, _x1))]] [[U71(mark(_x0), _x1, _x2)]] = 4 + 2x0 + 2x1 + 2x2 > 2 + 2x0 + 2x1 + 2x2 = [[mark(U71(_x0, _x1, _x2))]] [[proper(U11(_x0, _x1, _x2))]] = 3x1 + 3x2 + 6x0 >= 3x1 + 3x2 + 6x0 = [[U11(proper(_x0), proper(_x1), proper(_x2))]] [[proper(U21(_x0, _x1))]] = 3x0 + 3x1 >= 3x0 + 3x1 = [[U21(proper(_x0), proper(_x1))]] [[proper(U22(_x0))]] = 3x0 >= 3x0 = [[U22(proper(_x0))]] [[proper(U31(_x0, _x1, _x2))]] = 3x1 + 3x2 + 6x0 >= 3x1 + 3x2 + 6x0 = [[U31(proper(_x0), proper(_x1), proper(_x2))]] [[proper(U32(_x0, _x1))]] = 6x0 + 6x1 >= 6x0 + 6x1 = [[U32(proper(_x0), proper(_x1))]] [[proper(U41(_x0, _x1))]] = 6x0 + 6x1 >= 6x0 + 6x1 = [[U41(proper(_x0), proper(_x1))]] [[proper(U51(_x0, _x1, _x2))]] = 3x1 + 3x2 + 6x0 >= 3x1 + 3x2 + 6x0 = [[U51(proper(_x0), proper(_x1), proper(_x2))]] [[proper(s(_x0))]] = 6x0 >= 6x0 = [[s(proper(_x0))]] [[proper(plus(_x0, _x1))]] = 3x0 + 6x1 >= 3x0 + 6x1 = [[plus(proper(_x0), proper(_x1))]] [[proper(U61(_x0))]] = 3x0 >= 3x0 = [[U61(proper(_x0))]] [[proper(U71(_x0, _x1, _x2))]] = 6x0 + 6x1 + 6x2 >= 6x0 + 6x1 + 6x2 = [[U71(proper(_x0), proper(_x1), proper(_x2))]] [[proper(x(_x0, _x1))]] = 6x0 + 6x1 >= 6x0 + 6x1 = [[x(proper(_x0), proper(_x1))]] [[proper(and(_x0, _x1))]] = 6x0 + 6x1 >= 6x0 + 6x1 = [[and(proper(_x0), proper(_x1))]] [[proper(isNatKind(_x0))]] = 3x0 >= 3x0 = [[isNatKind(proper(_x0))]] [[U11(ok(_x0), ok(_x1), ok(_x2))]] = 2x1 + 2x2 + 4x0 >= 2x1 + 2x2 + 4x0 = [[ok(U11(_x0, _x1, _x2))]] [[U12(ok(_x0), ok(_x1))]] = 2x1 + 4x0 >= 2x1 + 4x0 = [[ok(U12(_x0, _x1))]] [[isNat(ok(_x0))]] = 6x0 >= 6x0 = [[ok(isNat(_x0))]] [[U13(ok(_x0))]] = 4x0 >= 4x0 = [[ok(U13(_x0))]] [[U21(ok(_x0), ok(_x1))]] = 2x0 + 2x1 >= 2x0 + 2x1 = [[ok(U21(_x0, _x1))]] [[U22(ok(_x0))]] = 2x0 >= 2x0 = [[ok(U22(_x0))]] [[U31(ok(_x0), ok(_x1), ok(_x2))]] = 2x1 + 2x2 + 4x0 >= 2x1 + 2x2 + 4x0 = [[ok(U31(_x0, _x1, _x2))]] [[U32(ok(_x0), ok(_x1))]] = 4x0 + 4x1 >= 4x0 + 4x1 = [[ok(U32(_x0, _x1))]] [[U33(ok(_x0))]] = 2x0 >= 2x0 = [[ok(U33(_x0))]] [[U41(ok(_x0), ok(_x1))]] = 4x0 + 4x1 >= 4x0 + 4x1 = [[ok(U41(_x0, _x1))]] [[U51(ok(_x0), ok(_x1), ok(_x2))]] = 2x1 + 2x2 + 4x0 >= 2x1 + 2x2 + 4x0 = [[ok(U51(_x0, _x1, _x2))]] [[s(ok(_x0))]] = 4x0 >= 4x0 = [[ok(s(_x0))]] [[plus(ok(_x0), ok(_x1))]] = 2x0 + 4x1 >= 2x0 + 4x1 = [[ok(plus(_x0, _x1))]] [[U61(ok(_x0))]] = 2x0 >= 2x0 = [[ok(U61(_x0))]] [[U71(ok(_x0), ok(_x1), ok(_x2))]] = 4x0 + 4x1 + 4x2 >= 4x0 + 4x1 + 4x2 = [[ok(U71(_x0, _x1, _x2))]] [[x(ok(_x0), ok(_x1))]] = 4x0 + 4x1 >= 4x0 + 4x1 = [[ok(x(_x0, _x1))]] [[and(ok(_x0), ok(_x1))]] = 4x0 + 4x1 >= 4x0 + 4x1 = [[ok(and(_x0, _x1))]] [[isNatKind(ok(_x0))]] = 2x0 >= 2x0 = [[ok(isNatKind(_x0))]] [[top(ok(_x0))]] = 2x0 >= 2x0 = [[top(active(_x0))]] We can thus remove the following rules: U11(mark(X), Y, Z) => mark(U11(X, Y, Z)) U13(mark(X)) => mark(U13(X)) U31(mark(X), Y, Z) => mark(U31(X, Y, Z)) U41(mark(X), Y) => mark(U41(X, Y)) U71(mark(X), Y, Z) => mark(U71(X, Y, Z)) We use rule removal, following [Kop12, Theorem 2.23]. This gives the following requirements (possibly using Theorems 2.25 and 2.26 in [Kop12]): active(U11(X, Y, Z)) >? U11(active(X), Y, Z) active(U12(X, Y)) >? U12(active(X), Y) active(U13(X)) >? U13(active(X)) active(U21(X, Y)) >? U21(active(X), Y) active(U22(X)) >? U22(active(X)) active(U31(X, Y, Z)) >? U31(active(X), Y, Z) active(U32(X, Y)) >? U32(active(X), Y) active(U33(X)) >? U33(active(X)) active(U41(X, Y)) >? U41(active(X), Y) active(U51(X, Y, Z)) >? U51(active(X), Y, Z) active(s(X)) >? s(active(X)) active(plus(X, Y)) >? plus(active(X), Y) active(plus(X, Y)) >? plus(X, active(Y)) active(U61(X)) >? U61(active(X)) active(U71(X, Y, Z)) >? U71(active(X), Y, Z) active(x(X, Y)) >? x(active(X), Y) active(x(X, Y)) >? x(X, active(Y)) active(and(X, Y)) >? and(active(X), Y) proper(U11(X, Y, Z)) >? U11(proper(X), proper(Y), proper(Z)) proper(U21(X, Y)) >? U21(proper(X), proper(Y)) proper(U22(X)) >? U22(proper(X)) proper(U31(X, Y, Z)) >? U31(proper(X), proper(Y), proper(Z)) proper(U32(X, Y)) >? U32(proper(X), proper(Y)) proper(U41(X, Y)) >? U41(proper(X), proper(Y)) proper(U51(X, Y, Z)) >? U51(proper(X), proper(Y), proper(Z)) proper(s(X)) >? s(proper(X)) proper(plus(X, Y)) >? plus(proper(X), proper(Y)) proper(U61(X)) >? U61(proper(X)) proper(U71(X, Y, Z)) >? U71(proper(X), proper(Y), proper(Z)) proper(x(X, Y)) >? x(proper(X), proper(Y)) proper(and(X, Y)) >? and(proper(X), proper(Y)) proper(isNatKind(X)) >? isNatKind(proper(X)) U11(ok(X), ok(Y), ok(Z)) >? ok(U11(X, Y, Z)) U12(ok(X), ok(Y)) >? ok(U12(X, Y)) isNat(ok(X)) >? ok(isNat(X)) U13(ok(X)) >? ok(U13(X)) U21(ok(X), ok(Y)) >? ok(U21(X, Y)) U22(ok(X)) >? ok(U22(X)) U31(ok(X), ok(Y), ok(Z)) >? ok(U31(X, Y, Z)) U32(ok(X), ok(Y)) >? ok(U32(X, Y)) U33(ok(X)) >? ok(U33(X)) U41(ok(X), ok(Y)) >? ok(U41(X, Y)) U51(ok(X), ok(Y), ok(Z)) >? ok(U51(X, Y, Z)) s(ok(X)) >? ok(s(X)) plus(ok(X), ok(Y)) >? ok(plus(X, Y)) U61(ok(X)) >? ok(U61(X)) U71(ok(X), ok(Y), ok(Z)) >? ok(U71(X, Y, Z)) x(ok(X), ok(Y)) >? ok(x(X, Y)) and(ok(X), ok(Y)) >? ok(and(X, Y)) isNatKind(ok(X)) >? ok(isNatKind(X)) top(ok(X)) >? top(active(X)) We orient these requirements with a polynomial interpretation in the natural numbers. The following interpretation satisfies the requirements: U11 = \y0y1y2.y1 + 2y0 + 2y2 U12 = \y0y1.y0 + y1 U13 = \y0.2y0 U21 = \y0y1.2y0 + 2y1 U22 = \y0.y0 U31 = \y0y1y2.y1 + y2 + 2y0 U32 = \y0y1.1 + y0 + 2y1 U33 = \y0.2y0 U41 = \y0y1.2y0 + 2y1 U51 = \y0y1y2.y0 + y1 + y2 U61 = \y0.2 + y0 U71 = \y0y1y2.y1 + y2 + 2y0 active = \y0.y0 and = \y0y1.y1 + 2y0 isNat = \y0.1 + 2y0 isNatKind = \y0.y0 ok = \y0.y0 plus = \y0y1.2y0 + 2y1 proper = \y0.2y0 s = \y0.1 + y0 top = \y0.y0 x = \y0y1.2y0 + 2y1 Using this interpretation, the requirements translate to: [[active(U11(_x0, _x1, _x2))]] = x1 + 2x0 + 2x2 >= x1 + 2x0 + 2x2 = [[U11(active(_x0), _x1, _x2)]] [[active(U12(_x0, _x1))]] = x0 + x1 >= x0 + x1 = [[U12(active(_x0), _x1)]] [[active(U13(_x0))]] = 2x0 >= 2x0 = [[U13(active(_x0))]] [[active(U21(_x0, _x1))]] = 2x0 + 2x1 >= 2x0 + 2x1 = [[U21(active(_x0), _x1)]] [[active(U22(_x0))]] = x0 >= x0 = [[U22(active(_x0))]] [[active(U31(_x0, _x1, _x2))]] = x1 + x2 + 2x0 >= x1 + x2 + 2x0 = [[U31(active(_x0), _x1, _x2)]] [[active(U32(_x0, _x1))]] = 1 + x0 + 2x1 >= 1 + x0 + 2x1 = [[U32(active(_x0), _x1)]] [[active(U33(_x0))]] = 2x0 >= 2x0 = [[U33(active(_x0))]] [[active(U41(_x0, _x1))]] = 2x0 + 2x1 >= 2x0 + 2x1 = [[U41(active(_x0), _x1)]] [[active(U51(_x0, _x1, _x2))]] = x0 + x1 + x2 >= x0 + x1 + x2 = [[U51(active(_x0), _x1, _x2)]] [[active(s(_x0))]] = 1 + x0 >= 1 + x0 = [[s(active(_x0))]] [[active(plus(_x0, _x1))]] = 2x0 + 2x1 >= 2x0 + 2x1 = [[plus(active(_x0), _x1)]] [[active(plus(_x0, _x1))]] = 2x0 + 2x1 >= 2x0 + 2x1 = [[plus(_x0, active(_x1))]] [[active(U61(_x0))]] = 2 + x0 >= 2 + x0 = [[U61(active(_x0))]] [[active(U71(_x0, _x1, _x2))]] = x1 + x2 + 2x0 >= x1 + x2 + 2x0 = [[U71(active(_x0), _x1, _x2)]] [[active(x(_x0, _x1))]] = 2x0 + 2x1 >= 2x0 + 2x1 = [[x(active(_x0), _x1)]] [[active(x(_x0, _x1))]] = 2x0 + 2x1 >= 2x0 + 2x1 = [[x(_x0, active(_x1))]] [[active(and(_x0, _x1))]] = x1 + 2x0 >= x1 + 2x0 = [[and(active(_x0), _x1)]] [[proper(U11(_x0, _x1, _x2))]] = 2x1 + 4x0 + 4x2 >= 2x1 + 4x0 + 4x2 = [[U11(proper(_x0), proper(_x1), proper(_x2))]] [[proper(U21(_x0, _x1))]] = 4x0 + 4x1 >= 4x0 + 4x1 = [[U21(proper(_x0), proper(_x1))]] [[proper(U22(_x0))]] = 2x0 >= 2x0 = [[U22(proper(_x0))]] [[proper(U31(_x0, _x1, _x2))]] = 2x1 + 2x2 + 4x0 >= 2x1 + 2x2 + 4x0 = [[U31(proper(_x0), proper(_x1), proper(_x2))]] [[proper(U32(_x0, _x1))]] = 2 + 2x0 + 4x1 > 1 + 2x0 + 4x1 = [[U32(proper(_x0), proper(_x1))]] [[proper(U41(_x0, _x1))]] = 4x0 + 4x1 >= 4x0 + 4x1 = [[U41(proper(_x0), proper(_x1))]] [[proper(U51(_x0, _x1, _x2))]] = 2x0 + 2x1 + 2x2 >= 2x0 + 2x1 + 2x2 = [[U51(proper(_x0), proper(_x1), proper(_x2))]] [[proper(s(_x0))]] = 2 + 2x0 > 1 + 2x0 = [[s(proper(_x0))]] [[proper(plus(_x0, _x1))]] = 4x0 + 4x1 >= 4x0 + 4x1 = [[plus(proper(_x0), proper(_x1))]] [[proper(U61(_x0))]] = 4 + 2x0 > 2 + 2x0 = [[U61(proper(_x0))]] [[proper(U71(_x0, _x1, _x2))]] = 2x1 + 2x2 + 4x0 >= 2x1 + 2x2 + 4x0 = [[U71(proper(_x0), proper(_x1), proper(_x2))]] [[proper(x(_x0, _x1))]] = 4x0 + 4x1 >= 4x0 + 4x1 = [[x(proper(_x0), proper(_x1))]] [[proper(and(_x0, _x1))]] = 2x1 + 4x0 >= 2x1 + 4x0 = [[and(proper(_x0), proper(_x1))]] [[proper(isNatKind(_x0))]] = 2x0 >= 2x0 = [[isNatKind(proper(_x0))]] [[U11(ok(_x0), ok(_x1), ok(_x2))]] = x1 + 2x0 + 2x2 >= x1 + 2x0 + 2x2 = [[ok(U11(_x0, _x1, _x2))]] [[U12(ok(_x0), ok(_x1))]] = x0 + x1 >= x0 + x1 = [[ok(U12(_x0, _x1))]] [[isNat(ok(_x0))]] = 1 + 2x0 >= 1 + 2x0 = [[ok(isNat(_x0))]] [[U13(ok(_x0))]] = 2x0 >= 2x0 = [[ok(U13(_x0))]] [[U21(ok(_x0), ok(_x1))]] = 2x0 + 2x1 >= 2x0 + 2x1 = [[ok(U21(_x0, _x1))]] [[U22(ok(_x0))]] = x0 >= x0 = [[ok(U22(_x0))]] [[U31(ok(_x0), ok(_x1), ok(_x2))]] = x1 + x2 + 2x0 >= x1 + x2 + 2x0 = [[ok(U31(_x0, _x1, _x2))]] [[U32(ok(_x0), ok(_x1))]] = 1 + x0 + 2x1 >= 1 + x0 + 2x1 = [[ok(U32(_x0, _x1))]] [[U33(ok(_x0))]] = 2x0 >= 2x0 = [[ok(U33(_x0))]] [[U41(ok(_x0), ok(_x1))]] = 2x0 + 2x1 >= 2x0 + 2x1 = [[ok(U41(_x0, _x1))]] [[U51(ok(_x0), ok(_x1), ok(_x2))]] = x0 + x1 + x2 >= x0 + x1 + x2 = [[ok(U51(_x0, _x1, _x2))]] [[s(ok(_x0))]] = 1 + x0 >= 1 + x0 = [[ok(s(_x0))]] [[plus(ok(_x0), ok(_x1))]] = 2x0 + 2x1 >= 2x0 + 2x1 = [[ok(plus(_x0, _x1))]] [[U61(ok(_x0))]] = 2 + x0 >= 2 + x0 = [[ok(U61(_x0))]] [[U71(ok(_x0), ok(_x1), ok(_x2))]] = x1 + x2 + 2x0 >= x1 + x2 + 2x0 = [[ok(U71(_x0, _x1, _x2))]] [[x(ok(_x0), ok(_x1))]] = 2x0 + 2x1 >= 2x0 + 2x1 = [[ok(x(_x0, _x1))]] [[and(ok(_x0), ok(_x1))]] = x1 + 2x0 >= x1 + 2x0 = [[ok(and(_x0, _x1))]] [[isNatKind(ok(_x0))]] = x0 >= x0 = [[ok(isNatKind(_x0))]] [[top(ok(_x0))]] = x0 >= x0 = [[top(active(_x0))]] We can thus remove the following rules: proper(U32(X, Y)) => U32(proper(X), proper(Y)) proper(s(X)) => s(proper(X)) proper(U61(X)) => U61(proper(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]): active(U11(X, Y, Z)) >? U11(active(X), Y, Z) active(U12(X, Y)) >? U12(active(X), Y) active(U13(X)) >? U13(active(X)) active(U21(X, Y)) >? U21(active(X), Y) active(U22(X)) >? U22(active(X)) active(U31(X, Y, Z)) >? U31(active(X), Y, Z) active(U32(X, Y)) >? U32(active(X), Y) active(U33(X)) >? U33(active(X)) active(U41(X, Y)) >? U41(active(X), Y) active(U51(X, Y, Z)) >? U51(active(X), Y, Z) active(s(X)) >? s(active(X)) active(plus(X, Y)) >? plus(active(X), Y) active(plus(X, Y)) >? plus(X, active(Y)) active(U61(X)) >? U61(active(X)) active(U71(X, Y, Z)) >? U71(active(X), Y, Z) active(x(X, Y)) >? x(active(X), Y) active(x(X, Y)) >? x(X, active(Y)) active(and(X, Y)) >? and(active(X), Y) proper(U11(X, Y, Z)) >? U11(proper(X), proper(Y), proper(Z)) proper(U21(X, Y)) >? U21(proper(X), proper(Y)) proper(U22(X)) >? U22(proper(X)) proper(U31(X, Y, Z)) >? U31(proper(X), proper(Y), proper(Z)) proper(U41(X, Y)) >? U41(proper(X), proper(Y)) proper(U51(X, Y, Z)) >? U51(proper(X), proper(Y), proper(Z)) proper(plus(X, Y)) >? plus(proper(X), proper(Y)) proper(U71(X, Y, Z)) >? U71(proper(X), proper(Y), proper(Z)) proper(x(X, Y)) >? x(proper(X), proper(Y)) proper(and(X, Y)) >? and(proper(X), proper(Y)) proper(isNatKind(X)) >? isNatKind(proper(X)) U11(ok(X), ok(Y), ok(Z)) >? ok(U11(X, Y, Z)) U12(ok(X), ok(Y)) >? ok(U12(X, Y)) isNat(ok(X)) >? ok(isNat(X)) U13(ok(X)) >? ok(U13(X)) U21(ok(X), ok(Y)) >? ok(U21(X, Y)) U22(ok(X)) >? ok(U22(X)) U31(ok(X), ok(Y), ok(Z)) >? ok(U31(X, Y, Z)) U32(ok(X), ok(Y)) >? ok(U32(X, Y)) U33(ok(X)) >? ok(U33(X)) U41(ok(X), ok(Y)) >? ok(U41(X, Y)) U51(ok(X), ok(Y), ok(Z)) >? ok(U51(X, Y, Z)) s(ok(X)) >? ok(s(X)) plus(ok(X), ok(Y)) >? ok(plus(X, Y)) U61(ok(X)) >? ok(U61(X)) U71(ok(X), ok(Y), ok(Z)) >? ok(U71(X, Y, Z)) x(ok(X), ok(Y)) >? ok(x(X, Y)) and(ok(X), ok(Y)) >? ok(and(X, Y)) isNatKind(ok(X)) >? ok(isNatKind(X)) top(ok(X)) >? top(active(X)) We orient these requirements with a polynomial interpretation in the natural numbers. The following interpretation satisfies the requirements: U11 = \y0y1y2.1 + y0 + y1 + y2 U12 = \y0y1.y1 + 2y0 U13 = \y0.1 + y0 U21 = \y0y1.y1 + 2y0 U22 = \y0.2y0 U31 = \y0y1y2.y1 + y2 + 2y0 U32 = \y0y1.y0 + y1 U33 = \y0.2y0 U41 = \y0y1.y0 + y1 U51 = \y0y1y2.y0 + y1 + y2 U61 = \y0.2y0 U71 = \y0y1y2.y1 + y2 + 2y0 active = \y0.y0 and = \y0y1.y1 + 2y0 isNat = \y0.2y0 isNatKind = \y0.y0 ok = \y0.y0 plus = \y0y1.y0 + 2y1 proper = \y0.2y0 s = \y0.2y0 top = \y0.2y0 x = \y0y1.y0 + 2y1 Using this interpretation, the requirements translate to: [[active(U11(_x0, _x1, _x2))]] = 1 + x0 + x1 + x2 >= 1 + x0 + x1 + x2 = [[U11(active(_x0), _x1, _x2)]] [[active(U12(_x0, _x1))]] = x1 + 2x0 >= x1 + 2x0 = [[U12(active(_x0), _x1)]] [[active(U13(_x0))]] = 1 + x0 >= 1 + x0 = [[U13(active(_x0))]] [[active(U21(_x0, _x1))]] = x1 + 2x0 >= x1 + 2x0 = [[U21(active(_x0), _x1)]] [[active(U22(_x0))]] = 2x0 >= 2x0 = [[U22(active(_x0))]] [[active(U31(_x0, _x1, _x2))]] = x1 + x2 + 2x0 >= x1 + x2 + 2x0 = [[U31(active(_x0), _x1, _x2)]] [[active(U32(_x0, _x1))]] = x0 + x1 >= x0 + x1 = [[U32(active(_x0), _x1)]] [[active(U33(_x0))]] = 2x0 >= 2x0 = [[U33(active(_x0))]] [[active(U41(_x0, _x1))]] = x0 + x1 >= x0 + x1 = [[U41(active(_x0), _x1)]] [[active(U51(_x0, _x1, _x2))]] = x0 + x1 + x2 >= x0 + x1 + x2 = [[U51(active(_x0), _x1, _x2)]] [[active(s(_x0))]] = 2x0 >= 2x0 = [[s(active(_x0))]] [[active(plus(_x0, _x1))]] = x0 + 2x1 >= x0 + 2x1 = [[plus(active(_x0), _x1)]] [[active(plus(_x0, _x1))]] = x0 + 2x1 >= x0 + 2x1 = [[plus(_x0, active(_x1))]] [[active(U61(_x0))]] = 2x0 >= 2x0 = [[U61(active(_x0))]] [[active(U71(_x0, _x1, _x2))]] = x1 + x2 + 2x0 >= x1 + x2 + 2x0 = [[U71(active(_x0), _x1, _x2)]] [[active(x(_x0, _x1))]] = x0 + 2x1 >= x0 + 2x1 = [[x(active(_x0), _x1)]] [[active(x(_x0, _x1))]] = x0 + 2x1 >= x0 + 2x1 = [[x(_x0, active(_x1))]] [[active(and(_x0, _x1))]] = x1 + 2x0 >= x1 + 2x0 = [[and(active(_x0), _x1)]] [[proper(U11(_x0, _x1, _x2))]] = 2 + 2x0 + 2x1 + 2x2 > 1 + 2x0 + 2x1 + 2x2 = [[U11(proper(_x0), proper(_x1), proper(_x2))]] [[proper(U21(_x0, _x1))]] = 2x1 + 4x0 >= 2x1 + 4x0 = [[U21(proper(_x0), proper(_x1))]] [[proper(U22(_x0))]] = 4x0 >= 4x0 = [[U22(proper(_x0))]] [[proper(U31(_x0, _x1, _x2))]] = 2x1 + 2x2 + 4x0 >= 2x1 + 2x2 + 4x0 = [[U31(proper(_x0), proper(_x1), proper(_x2))]] [[proper(U41(_x0, _x1))]] = 2x0 + 2x1 >= 2x0 + 2x1 = [[U41(proper(_x0), proper(_x1))]] [[proper(U51(_x0, _x1, _x2))]] = 2x0 + 2x1 + 2x2 >= 2x0 + 2x1 + 2x2 = [[U51(proper(_x0), proper(_x1), proper(_x2))]] [[proper(plus(_x0, _x1))]] = 2x0 + 4x1 >= 2x0 + 4x1 = [[plus(proper(_x0), proper(_x1))]] [[proper(U71(_x0, _x1, _x2))]] = 2x1 + 2x2 + 4x0 >= 2x1 + 2x2 + 4x0 = [[U71(proper(_x0), proper(_x1), proper(_x2))]] [[proper(x(_x0, _x1))]] = 2x0 + 4x1 >= 2x0 + 4x1 = [[x(proper(_x0), proper(_x1))]] [[proper(and(_x0, _x1))]] = 2x1 + 4x0 >= 2x1 + 4x0 = [[and(proper(_x0), proper(_x1))]] [[proper(isNatKind(_x0))]] = 2x0 >= 2x0 = [[isNatKind(proper(_x0))]] [[U11(ok(_x0), ok(_x1), ok(_x2))]] = 1 + x0 + x1 + x2 >= 1 + x0 + x1 + x2 = [[ok(U11(_x0, _x1, _x2))]] [[U12(ok(_x0), ok(_x1))]] = x1 + 2x0 >= x1 + 2x0 = [[ok(U12(_x0, _x1))]] [[isNat(ok(_x0))]] = 2x0 >= 2x0 = [[ok(isNat(_x0))]] [[U13(ok(_x0))]] = 1 + x0 >= 1 + x0 = [[ok(U13(_x0))]] [[U21(ok(_x0), ok(_x1))]] = x1 + 2x0 >= x1 + 2x0 = [[ok(U21(_x0, _x1))]] [[U22(ok(_x0))]] = 2x0 >= 2x0 = [[ok(U22(_x0))]] [[U31(ok(_x0), ok(_x1), ok(_x2))]] = x1 + x2 + 2x0 >= x1 + x2 + 2x0 = [[ok(U31(_x0, _x1, _x2))]] [[U32(ok(_x0), ok(_x1))]] = x0 + x1 >= x0 + x1 = [[ok(U32(_x0, _x1))]] [[U33(ok(_x0))]] = 2x0 >= 2x0 = [[ok(U33(_x0))]] [[U41(ok(_x0), ok(_x1))]] = x0 + x1 >= x0 + x1 = [[ok(U41(_x0, _x1))]] [[U51(ok(_x0), ok(_x1), ok(_x2))]] = x0 + x1 + x2 >= x0 + x1 + x2 = [[ok(U51(_x0, _x1, _x2))]] [[s(ok(_x0))]] = 2x0 >= 2x0 = [[ok(s(_x0))]] [[plus(ok(_x0), ok(_x1))]] = x0 + 2x1 >= x0 + 2x1 = [[ok(plus(_x0, _x1))]] [[U61(ok(_x0))]] = 2x0 >= 2x0 = [[ok(U61(_x0))]] [[U71(ok(_x0), ok(_x1), ok(_x2))]] = x1 + x2 + 2x0 >= x1 + x2 + 2x0 = [[ok(U71(_x0, _x1, _x2))]] [[x(ok(_x0), ok(_x1))]] = x0 + 2x1 >= x0 + 2x1 = [[ok(x(_x0, _x1))]] [[and(ok(_x0), ok(_x1))]] = x1 + 2x0 >= x1 + 2x0 = [[ok(and(_x0, _x1))]] [[isNatKind(ok(_x0))]] = x0 >= x0 = [[ok(isNatKind(_x0))]] [[top(ok(_x0))]] = 2x0 >= 2x0 = [[top(active(_x0))]] We can thus remove the following rules: proper(U11(X, Y, Z)) => U11(proper(X), proper(Y), proper(Z)) We use rule removal, following [Kop12, Theorem 2.23]. This gives the following requirements (possibly using Theorems 2.25 and 2.26 in [Kop12]): active(U11(X, Y, Z)) >? U11(active(X), Y, Z) active(U12(X, Y)) >? U12(active(X), Y) active(U13(X)) >? U13(active(X)) active(U21(X, Y)) >? U21(active(X), Y) active(U22(X)) >? U22(active(X)) active(U31(X, Y, Z)) >? U31(active(X), Y, Z) active(U32(X, Y)) >? U32(active(X), Y) active(U33(X)) >? U33(active(X)) active(U41(X, Y)) >? U41(active(X), Y) active(U51(X, Y, Z)) >? U51(active(X), Y, Z) active(s(X)) >? s(active(X)) active(plus(X, Y)) >? plus(active(X), Y) active(plus(X, Y)) >? plus(X, active(Y)) active(U61(X)) >? U61(active(X)) active(U71(X, Y, Z)) >? U71(active(X), Y, Z) active(x(X, Y)) >? x(active(X), Y) active(x(X, Y)) >? x(X, active(Y)) active(and(X, Y)) >? and(active(X), Y) proper(U21(X, Y)) >? U21(proper(X), proper(Y)) proper(U22(X)) >? U22(proper(X)) proper(U31(X, Y, Z)) >? U31(proper(X), proper(Y), proper(Z)) proper(U41(X, Y)) >? U41(proper(X), proper(Y)) proper(U51(X, Y, Z)) >? U51(proper(X), proper(Y), proper(Z)) proper(plus(X, Y)) >? plus(proper(X), proper(Y)) proper(U71(X, Y, Z)) >? U71(proper(X), proper(Y), proper(Z)) proper(x(X, Y)) >? x(proper(X), proper(Y)) proper(and(X, Y)) >? and(proper(X), proper(Y)) proper(isNatKind(X)) >? isNatKind(proper(X)) U11(ok(X), ok(Y), ok(Z)) >? ok(U11(X, Y, Z)) U12(ok(X), ok(Y)) >? ok(U12(X, Y)) isNat(ok(X)) >? ok(isNat(X)) U13(ok(X)) >? ok(U13(X)) U21(ok(X), ok(Y)) >? ok(U21(X, Y)) U22(ok(X)) >? ok(U22(X)) U31(ok(X), ok(Y), ok(Z)) >? ok(U31(X, Y, Z)) U32(ok(X), ok(Y)) >? ok(U32(X, Y)) U33(ok(X)) >? ok(U33(X)) U41(ok(X), ok(Y)) >? ok(U41(X, Y)) U51(ok(X), ok(Y), ok(Z)) >? ok(U51(X, Y, Z)) s(ok(X)) >? ok(s(X)) plus(ok(X), ok(Y)) >? ok(plus(X, Y)) U61(ok(X)) >? ok(U61(X)) U71(ok(X), ok(Y), ok(Z)) >? ok(U71(X, Y, Z)) x(ok(X), ok(Y)) >? ok(x(X, Y)) and(ok(X), ok(Y)) >? ok(and(X, Y)) isNatKind(ok(X)) >? ok(isNatKind(X)) top(ok(X)) >? top(active(X)) We orient these requirements with a polynomial interpretation in the natural numbers. The following interpretation satisfies the requirements: U11 = \y0y1y2.y2 + 2y0 + 2y1 U12 = \y0y1.y1 + 2y0 U13 = \y0.2y0 U21 = \y0y1.y0 + y1 U22 = \y0.y0 U31 = \y0y1y2.y0 + y1 + y2 U32 = \y0y1.y1 + 2y0 U33 = \y0.2y0 U41 = \y0y1.2 + y0 + y1 U51 = \y0y1y2.y0 + y1 + y2 U61 = \y0.2y0 U71 = \y0y1y2.y1 + 2y0 + 2y2 active = \y0.y0 and = \y0y1.y1 + 2y0 isNat = \y0.y0 isNatKind = \y0.y0 ok = \y0.y0 plus = \y0y1.2y0 + 2y1 proper = \y0.2y0 s = \y0.2y0 top = \y0.2y0 x = \y0y1.y1 + 2y0 Using this interpretation, the requirements translate to: [[active(U11(_x0, _x1, _x2))]] = x2 + 2x0 + 2x1 >= x2 + 2x0 + 2x1 = [[U11(active(_x0), _x1, _x2)]] [[active(U12(_x0, _x1))]] = x1 + 2x0 >= x1 + 2x0 = [[U12(active(_x0), _x1)]] [[active(U13(_x0))]] = 2x0 >= 2x0 = [[U13(active(_x0))]] [[active(U21(_x0, _x1))]] = x0 + x1 >= x0 + x1 = [[U21(active(_x0), _x1)]] [[active(U22(_x0))]] = x0 >= x0 = [[U22(active(_x0))]] [[active(U31(_x0, _x1, _x2))]] = x0 + x1 + x2 >= x0 + x1 + x2 = [[U31(active(_x0), _x1, _x2)]] [[active(U32(_x0, _x1))]] = x1 + 2x0 >= x1 + 2x0 = [[U32(active(_x0), _x1)]] [[active(U33(_x0))]] = 2x0 >= 2x0 = [[U33(active(_x0))]] [[active(U41(_x0, _x1))]] = 2 + x0 + x1 >= 2 + x0 + x1 = [[U41(active(_x0), _x1)]] [[active(U51(_x0, _x1, _x2))]] = x0 + x1 + x2 >= x0 + x1 + x2 = [[U51(active(_x0), _x1, _x2)]] [[active(s(_x0))]] = 2x0 >= 2x0 = [[s(active(_x0))]] [[active(plus(_x0, _x1))]] = 2x0 + 2x1 >= 2x0 + 2x1 = [[plus(active(_x0), _x1)]] [[active(plus(_x0, _x1))]] = 2x0 + 2x1 >= 2x0 + 2x1 = [[plus(_x0, active(_x1))]] [[active(U61(_x0))]] = 2x0 >= 2x0 = [[U61(active(_x0))]] [[active(U71(_x0, _x1, _x2))]] = x1 + 2x0 + 2x2 >= x1 + 2x0 + 2x2 = [[U71(active(_x0), _x1, _x2)]] [[active(x(_x0, _x1))]] = x1 + 2x0 >= x1 + 2x0 = [[x(active(_x0), _x1)]] [[active(x(_x0, _x1))]] = x1 + 2x0 >= x1 + 2x0 = [[x(_x0, active(_x1))]] [[active(and(_x0, _x1))]] = x1 + 2x0 >= x1 + 2x0 = [[and(active(_x0), _x1)]] [[proper(U21(_x0, _x1))]] = 2x0 + 2x1 >= 2x0 + 2x1 = [[U21(proper(_x0), proper(_x1))]] [[proper(U22(_x0))]] = 2x0 >= 2x0 = [[U22(proper(_x0))]] [[proper(U31(_x0, _x1, _x2))]] = 2x0 + 2x1 + 2x2 >= 2x0 + 2x1 + 2x2 = [[U31(proper(_x0), proper(_x1), proper(_x2))]] [[proper(U41(_x0, _x1))]] = 4 + 2x0 + 2x1 > 2 + 2x0 + 2x1 = [[U41(proper(_x0), proper(_x1))]] [[proper(U51(_x0, _x1, _x2))]] = 2x0 + 2x1 + 2x2 >= 2x0 + 2x1 + 2x2 = [[U51(proper(_x0), proper(_x1), proper(_x2))]] [[proper(plus(_x0, _x1))]] = 4x0 + 4x1 >= 4x0 + 4x1 = [[plus(proper(_x0), proper(_x1))]] [[proper(U71(_x0, _x1, _x2))]] = 2x1 + 4x0 + 4x2 >= 2x1 + 4x0 + 4x2 = [[U71(proper(_x0), proper(_x1), proper(_x2))]] [[proper(x(_x0, _x1))]] = 2x1 + 4x0 >= 2x1 + 4x0 = [[x(proper(_x0), proper(_x1))]] [[proper(and(_x0, _x1))]] = 2x1 + 4x0 >= 2x1 + 4x0 = [[and(proper(_x0), proper(_x1))]] [[proper(isNatKind(_x0))]] = 2x0 >= 2x0 = [[isNatKind(proper(_x0))]] [[U11(ok(_x0), ok(_x1), ok(_x2))]] = x2 + 2x0 + 2x1 >= x2 + 2x0 + 2x1 = [[ok(U11(_x0, _x1, _x2))]] [[U12(ok(_x0), ok(_x1))]] = x1 + 2x0 >= x1 + 2x0 = [[ok(U12(_x0, _x1))]] [[isNat(ok(_x0))]] = x0 >= x0 = [[ok(isNat(_x0))]] [[U13(ok(_x0))]] = 2x0 >= 2x0 = [[ok(U13(_x0))]] [[U21(ok(_x0), ok(_x1))]] = x0 + x1 >= x0 + x1 = [[ok(U21(_x0, _x1))]] [[U22(ok(_x0))]] = x0 >= x0 = [[ok(U22(_x0))]] [[U31(ok(_x0), ok(_x1), ok(_x2))]] = x0 + x1 + x2 >= x0 + x1 + x2 = [[ok(U31(_x0, _x1, _x2))]] [[U32(ok(_x0), ok(_x1))]] = x1 + 2x0 >= x1 + 2x0 = [[ok(U32(_x0, _x1))]] [[U33(ok(_x0))]] = 2x0 >= 2x0 = [[ok(U33(_x0))]] [[U41(ok(_x0), ok(_x1))]] = 2 + x0 + x1 >= 2 + x0 + x1 = [[ok(U41(_x0, _x1))]] [[U51(ok(_x0), ok(_x1), ok(_x2))]] = x0 + x1 + x2 >= x0 + x1 + x2 = [[ok(U51(_x0, _x1, _x2))]] [[s(ok(_x0))]] = 2x0 >= 2x0 = [[ok(s(_x0))]] [[plus(ok(_x0), ok(_x1))]] = 2x0 + 2x1 >= 2x0 + 2x1 = [[ok(plus(_x0, _x1))]] [[U61(ok(_x0))]] = 2x0 >= 2x0 = [[ok(U61(_x0))]] [[U71(ok(_x0), ok(_x1), ok(_x2))]] = x1 + 2x0 + 2x2 >= x1 + 2x0 + 2x2 = [[ok(U71(_x0, _x1, _x2))]] [[x(ok(_x0), ok(_x1))]] = x1 + 2x0 >= x1 + 2x0 = [[ok(x(_x0, _x1))]] [[and(ok(_x0), ok(_x1))]] = x1 + 2x0 >= x1 + 2x0 = [[ok(and(_x0, _x1))]] [[isNatKind(ok(_x0))]] = x0 >= x0 = [[ok(isNatKind(_x0))]] [[top(ok(_x0))]] = 2x0 >= 2x0 = [[top(active(_x0))]] We can thus remove the following rules: proper(U41(X, Y)) => U41(proper(X), proper(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]): active(U11(X, Y, Z)) >? U11(active(X), Y, Z) active(U12(X, Y)) >? U12(active(X), Y) active(U13(X)) >? U13(active(X)) active(U21(X, Y)) >? U21(active(X), Y) active(U22(X)) >? U22(active(X)) active(U31(X, Y, Z)) >? U31(active(X), Y, Z) active(U32(X, Y)) >? U32(active(X), Y) active(U33(X)) >? U33(active(X)) active(U41(X, Y)) >? U41(active(X), Y) active(U51(X, Y, Z)) >? U51(active(X), Y, Z) active(s(X)) >? s(active(X)) active(plus(X, Y)) >? plus(active(X), Y) active(plus(X, Y)) >? plus(X, active(Y)) active(U61(X)) >? U61(active(X)) active(U71(X, Y, Z)) >? U71(active(X), Y, Z) active(x(X, Y)) >? x(active(X), Y) active(x(X, Y)) >? x(X, active(Y)) active(and(X, Y)) >? and(active(X), Y) proper(U21(X, Y)) >? U21(proper(X), proper(Y)) proper(U22(X)) >? U22(proper(X)) proper(U31(X, Y, Z)) >? U31(proper(X), proper(Y), proper(Z)) proper(U51(X, Y, Z)) >? U51(proper(X), proper(Y), proper(Z)) proper(plus(X, Y)) >? plus(proper(X), proper(Y)) proper(U71(X, Y, Z)) >? U71(proper(X), proper(Y), proper(Z)) proper(x(X, Y)) >? x(proper(X), proper(Y)) proper(and(X, Y)) >? and(proper(X), proper(Y)) proper(isNatKind(X)) >? isNatKind(proper(X)) U11(ok(X), ok(Y), ok(Z)) >? ok(U11(X, Y, Z)) U12(ok(X), ok(Y)) >? ok(U12(X, Y)) isNat(ok(X)) >? ok(isNat(X)) U13(ok(X)) >? ok(U13(X)) U21(ok(X), ok(Y)) >? ok(U21(X, Y)) U22(ok(X)) >? ok(U22(X)) U31(ok(X), ok(Y), ok(Z)) >? ok(U31(X, Y, Z)) U32(ok(X), ok(Y)) >? ok(U32(X, Y)) U33(ok(X)) >? ok(U33(X)) U41(ok(X), ok(Y)) >? ok(U41(X, Y)) U51(ok(X), ok(Y), ok(Z)) >? ok(U51(X, Y, Z)) s(ok(X)) >? ok(s(X)) plus(ok(X), ok(Y)) >? ok(plus(X, Y)) U61(ok(X)) >? ok(U61(X)) U71(ok(X), ok(Y), ok(Z)) >? ok(U71(X, Y, Z)) x(ok(X), ok(Y)) >? ok(x(X, Y)) and(ok(X), ok(Y)) >? ok(and(X, Y)) isNatKind(ok(X)) >? ok(isNatKind(X)) top(ok(X)) >? top(active(X)) We orient these requirements with a polynomial interpretation in the natural numbers. The following interpretation satisfies the requirements: U11 = \y0y1y2.y1 + y2 + 2y0 U12 = \y0y1.2y0 + 2y1 U13 = \y0.y0 U21 = \y0y1.y0 + y1 U22 = \y0.y0 U31 = \y0y1y2.y1 + y2 + 2y0 U32 = \y0y1.y1 + 2y0 U33 = \y0.y0 U41 = \y0y1.y1 + 2y0 U51 = \y0y1y2.y1 + y2 + 2y0 U61 = \y0.y0 U71 = \y0y1y2.2 + y0 + y1 + y2 active = \y0.y0 and = \y0y1.y1 + 2y0 isNat = \y0.y0 isNatKind = \y0.2y0 ok = \y0.y0 plus = \y0y1.y0 + 2y1 proper = \y0.2y0 s = \y0.y0 top = \y0.y0 x = \y0y1.2y0 + 2y1 Using this interpretation, the requirements translate to: [[active(U11(_x0, _x1, _x2))]] = x1 + x2 + 2x0 >= x1 + x2 + 2x0 = [[U11(active(_x0), _x1, _x2)]] [[active(U12(_x0, _x1))]] = 2x0 + 2x1 >= 2x0 + 2x1 = [[U12(active(_x0), _x1)]] [[active(U13(_x0))]] = x0 >= x0 = [[U13(active(_x0))]] [[active(U21(_x0, _x1))]] = x0 + x1 >= x0 + x1 = [[U21(active(_x0), _x1)]] [[active(U22(_x0))]] = x0 >= x0 = [[U22(active(_x0))]] [[active(U31(_x0, _x1, _x2))]] = x1 + x2 + 2x0 >= x1 + x2 + 2x0 = [[U31(active(_x0), _x1, _x2)]] [[active(U32(_x0, _x1))]] = x1 + 2x0 >= x1 + 2x0 = [[U32(active(_x0), _x1)]] [[active(U33(_x0))]] = x0 >= x0 = [[U33(active(_x0))]] [[active(U41(_x0, _x1))]] = x1 + 2x0 >= x1 + 2x0 = [[U41(active(_x0), _x1)]] [[active(U51(_x0, _x1, _x2))]] = x1 + x2 + 2x0 >= x1 + x2 + 2x0 = [[U51(active(_x0), _x1, _x2)]] [[active(s(_x0))]] = x0 >= x0 = [[s(active(_x0))]] [[active(plus(_x0, _x1))]] = x0 + 2x1 >= x0 + 2x1 = [[plus(active(_x0), _x1)]] [[active(plus(_x0, _x1))]] = x0 + 2x1 >= x0 + 2x1 = [[plus(_x0, active(_x1))]] [[active(U61(_x0))]] = x0 >= x0 = [[U61(active(_x0))]] [[active(U71(_x0, _x1, _x2))]] = 2 + x0 + x1 + x2 >= 2 + x0 + x1 + x2 = [[U71(active(_x0), _x1, _x2)]] [[active(x(_x0, _x1))]] = 2x0 + 2x1 >= 2x0 + 2x1 = [[x(active(_x0), _x1)]] [[active(x(_x0, _x1))]] = 2x0 + 2x1 >= 2x0 + 2x1 = [[x(_x0, active(_x1))]] [[active(and(_x0, _x1))]] = x1 + 2x0 >= x1 + 2x0 = [[and(active(_x0), _x1)]] [[proper(U21(_x0, _x1))]] = 2x0 + 2x1 >= 2x0 + 2x1 = [[U21(proper(_x0), proper(_x1))]] [[proper(U22(_x0))]] = 2x0 >= 2x0 = [[U22(proper(_x0))]] [[proper(U31(_x0, _x1, _x2))]] = 2x1 + 2x2 + 4x0 >= 2x1 + 2x2 + 4x0 = [[U31(proper(_x0), proper(_x1), proper(_x2))]] [[proper(U51(_x0, _x1, _x2))]] = 2x1 + 2x2 + 4x0 >= 2x1 + 2x2 + 4x0 = [[U51(proper(_x0), proper(_x1), proper(_x2))]] [[proper(plus(_x0, _x1))]] = 2x0 + 4x1 >= 2x0 + 4x1 = [[plus(proper(_x0), proper(_x1))]] [[proper(U71(_x0, _x1, _x2))]] = 4 + 2x0 + 2x1 + 2x2 > 2 + 2x0 + 2x1 + 2x2 = [[U71(proper(_x0), proper(_x1), proper(_x2))]] [[proper(x(_x0, _x1))]] = 4x0 + 4x1 >= 4x0 + 4x1 = [[x(proper(_x0), proper(_x1))]] [[proper(and(_x0, _x1))]] = 2x1 + 4x0 >= 2x1 + 4x0 = [[and(proper(_x0), proper(_x1))]] [[proper(isNatKind(_x0))]] = 4x0 >= 4x0 = [[isNatKind(proper(_x0))]] [[U11(ok(_x0), ok(_x1), ok(_x2))]] = x1 + x2 + 2x0 >= x1 + x2 + 2x0 = [[ok(U11(_x0, _x1, _x2))]] [[U12(ok(_x0), ok(_x1))]] = 2x0 + 2x1 >= 2x0 + 2x1 = [[ok(U12(_x0, _x1))]] [[isNat(ok(_x0))]] = x0 >= x0 = [[ok(isNat(_x0))]] [[U13(ok(_x0))]] = x0 >= x0 = [[ok(U13(_x0))]] [[U21(ok(_x0), ok(_x1))]] = x0 + x1 >= x0 + x1 = [[ok(U21(_x0, _x1))]] [[U22(ok(_x0))]] = x0 >= x0 = [[ok(U22(_x0))]] [[U31(ok(_x0), ok(_x1), ok(_x2))]] = x1 + x2 + 2x0 >= x1 + x2 + 2x0 = [[ok(U31(_x0, _x1, _x2))]] [[U32(ok(_x0), ok(_x1))]] = x1 + 2x0 >= x1 + 2x0 = [[ok(U32(_x0, _x1))]] [[U33(ok(_x0))]] = x0 >= x0 = [[ok(U33(_x0))]] [[U41(ok(_x0), ok(_x1))]] = x1 + 2x0 >= x1 + 2x0 = [[ok(U41(_x0, _x1))]] [[U51(ok(_x0), ok(_x1), ok(_x2))]] = x1 + x2 + 2x0 >= x1 + x2 + 2x0 = [[ok(U51(_x0, _x1, _x2))]] [[s(ok(_x0))]] = x0 >= x0 = [[ok(s(_x0))]] [[plus(ok(_x0), ok(_x1))]] = x0 + 2x1 >= x0 + 2x1 = [[ok(plus(_x0, _x1))]] [[U61(ok(_x0))]] = x0 >= x0 = [[ok(U61(_x0))]] [[U71(ok(_x0), ok(_x1), ok(_x2))]] = 2 + x0 + x1 + x2 >= 2 + x0 + x1 + x2 = [[ok(U71(_x0, _x1, _x2))]] [[x(ok(_x0), ok(_x1))]] = 2x0 + 2x1 >= 2x0 + 2x1 = [[ok(x(_x0, _x1))]] [[and(ok(_x0), ok(_x1))]] = x1 + 2x0 >= x1 + 2x0 = [[ok(and(_x0, _x1))]] [[isNatKind(ok(_x0))]] = 2x0 >= 2x0 = [[ok(isNatKind(_x0))]] [[top(ok(_x0))]] = x0 >= x0 = [[top(active(_x0))]] We can thus remove the following rules: proper(U71(X, Y, Z)) => U71(proper(X), proper(Y), proper(Z)) We use rule removal, following [Kop12, Theorem 2.23]. This gives the following requirements (possibly using Theorems 2.25 and 2.26 in [Kop12]): active(U11(X, Y, Z)) >? U11(active(X), Y, Z) active(U12(X, Y)) >? U12(active(X), Y) active(U13(X)) >? U13(active(X)) active(U21(X, Y)) >? U21(active(X), Y) active(U22(X)) >? U22(active(X)) active(U31(X, Y, Z)) >? U31(active(X), Y, Z) active(U32(X, Y)) >? U32(active(X), Y) active(U33(X)) >? U33(active(X)) active(U41(X, Y)) >? U41(active(X), Y) active(U51(X, Y, Z)) >? U51(active(X), Y, Z) active(s(X)) >? s(active(X)) active(plus(X, Y)) >? plus(active(X), Y) active(plus(X, Y)) >? plus(X, active(Y)) active(U61(X)) >? U61(active(X)) active(U71(X, Y, Z)) >? U71(active(X), Y, Z) active(x(X, Y)) >? x(active(X), Y) active(x(X, Y)) >? x(X, active(Y)) active(and(X, Y)) >? and(active(X), Y) proper(U21(X, Y)) >? U21(proper(X), proper(Y)) proper(U22(X)) >? U22(proper(X)) proper(U31(X, Y, Z)) >? U31(proper(X), proper(Y), proper(Z)) proper(U51(X, Y, Z)) >? U51(proper(X), proper(Y), proper(Z)) proper(plus(X, Y)) >? plus(proper(X), proper(Y)) proper(x(X, Y)) >? x(proper(X), proper(Y)) proper(and(X, Y)) >? and(proper(X), proper(Y)) proper(isNatKind(X)) >? isNatKind(proper(X)) U11(ok(X), ok(Y), ok(Z)) >? ok(U11(X, Y, Z)) U12(ok(X), ok(Y)) >? ok(U12(X, Y)) isNat(ok(X)) >? ok(isNat(X)) U13(ok(X)) >? ok(U13(X)) U21(ok(X), ok(Y)) >? ok(U21(X, Y)) U22(ok(X)) >? ok(U22(X)) U31(ok(X), ok(Y), ok(Z)) >? ok(U31(X, Y, Z)) U32(ok(X), ok(Y)) >? ok(U32(X, Y)) U33(ok(X)) >? ok(U33(X)) U41(ok(X), ok(Y)) >? ok(U41(X, Y)) U51(ok(X), ok(Y), ok(Z)) >? ok(U51(X, Y, Z)) s(ok(X)) >? ok(s(X)) plus(ok(X), ok(Y)) >? ok(plus(X, Y)) U61(ok(X)) >? ok(U61(X)) U71(ok(X), ok(Y), ok(Z)) >? ok(U71(X, Y, Z)) x(ok(X), ok(Y)) >? ok(x(X, Y)) and(ok(X), ok(Y)) >? ok(and(X, Y)) isNatKind(ok(X)) >? ok(isNatKind(X)) top(ok(X)) >? top(active(X)) We orient these requirements with a polynomial interpretation in the natural numbers. The following interpretation satisfies the requirements: U11 = \y0y1y2.y0 + y1 + y2 U12 = \y0y1.y0 + y1 U13 = \y0.y0 U21 = \y0y1.y1 + 2y0 U22 = \y0.y0 U31 = \y0y1y2.y1 + y2 + 2y0 U32 = \y0y1.y1 + 2y0 U33 = \y0.y0 U41 = \y0y1.y1 + 2y0 U51 = \y0y1y2.y0 + y1 + 2y2 U61 = \y0.2y0 U71 = \y0y1y2.y0 + y1 + y2 active = \y0.y0 and = \y0y1.2y0 + 2y1 isNat = \y0.2y0 isNatKind = \y0.1 + y0 ok = \y0.y0 plus = \y0y1.y0 + 2y1 proper = \y0.2y0 s = \y0.y0 top = \y0.y0 x = \y0y1.y0 + 2y1 Using this interpretation, the requirements translate to: [[active(U11(_x0, _x1, _x2))]] = x0 + x1 + x2 >= x0 + x1 + x2 = [[U11(active(_x0), _x1, _x2)]] [[active(U12(_x0, _x1))]] = x0 + x1 >= x0 + x1 = [[U12(active(_x0), _x1)]] [[active(U13(_x0))]] = x0 >= x0 = [[U13(active(_x0))]] [[active(U21(_x0, _x1))]] = x1 + 2x0 >= x1 + 2x0 = [[U21(active(_x0), _x1)]] [[active(U22(_x0))]] = x0 >= x0 = [[U22(active(_x0))]] [[active(U31(_x0, _x1, _x2))]] = x1 + x2 + 2x0 >= x1 + x2 + 2x0 = [[U31(active(_x0), _x1, _x2)]] [[active(U32(_x0, _x1))]] = x1 + 2x0 >= x1 + 2x0 = [[U32(active(_x0), _x1)]] [[active(U33(_x0))]] = x0 >= x0 = [[U33(active(_x0))]] [[active(U41(_x0, _x1))]] = x1 + 2x0 >= x1 + 2x0 = [[U41(active(_x0), _x1)]] [[active(U51(_x0, _x1, _x2))]] = x0 + x1 + 2x2 >= x0 + x1 + 2x2 = [[U51(active(_x0), _x1, _x2)]] [[active(s(_x0))]] = x0 >= x0 = [[s(active(_x0))]] [[active(plus(_x0, _x1))]] = x0 + 2x1 >= x0 + 2x1 = [[plus(active(_x0), _x1)]] [[active(plus(_x0, _x1))]] = x0 + 2x1 >= x0 + 2x1 = [[plus(_x0, active(_x1))]] [[active(U61(_x0))]] = 2x0 >= 2x0 = [[U61(active(_x0))]] [[active(U71(_x0, _x1, _x2))]] = x0 + x1 + x2 >= x0 + x1 + x2 = [[U71(active(_x0), _x1, _x2)]] [[active(x(_x0, _x1))]] = x0 + 2x1 >= x0 + 2x1 = [[x(active(_x0), _x1)]] [[active(x(_x0, _x1))]] = x0 + 2x1 >= x0 + 2x1 = [[x(_x0, active(_x1))]] [[active(and(_x0, _x1))]] = 2x0 + 2x1 >= 2x0 + 2x1 = [[and(active(_x0), _x1)]] [[proper(U21(_x0, _x1))]] = 2x1 + 4x0 >= 2x1 + 4x0 = [[U21(proper(_x0), proper(_x1))]] [[proper(U22(_x0))]] = 2x0 >= 2x0 = [[U22(proper(_x0))]] [[proper(U31(_x0, _x1, _x2))]] = 2x1 + 2x2 + 4x0 >= 2x1 + 2x2 + 4x0 = [[U31(proper(_x0), proper(_x1), proper(_x2))]] [[proper(U51(_x0, _x1, _x2))]] = 2x0 + 2x1 + 4x2 >= 2x0 + 2x1 + 4x2 = [[U51(proper(_x0), proper(_x1), proper(_x2))]] [[proper(plus(_x0, _x1))]] = 2x0 + 4x1 >= 2x0 + 4x1 = [[plus(proper(_x0), proper(_x1))]] [[proper(x(_x0, _x1))]] = 2x0 + 4x1 >= 2x0 + 4x1 = [[x(proper(_x0), proper(_x1))]] [[proper(and(_x0, _x1))]] = 4x0 + 4x1 >= 4x0 + 4x1 = [[and(proper(_x0), proper(_x1))]] [[proper(isNatKind(_x0))]] = 2 + 2x0 > 1 + 2x0 = [[isNatKind(proper(_x0))]] [[U11(ok(_x0), ok(_x1), ok(_x2))]] = x0 + x1 + x2 >= x0 + x1 + x2 = [[ok(U11(_x0, _x1, _x2))]] [[U12(ok(_x0), ok(_x1))]] = x0 + x1 >= x0 + x1 = [[ok(U12(_x0, _x1))]] [[isNat(ok(_x0))]] = 2x0 >= 2x0 = [[ok(isNat(_x0))]] [[U13(ok(_x0))]] = x0 >= x0 = [[ok(U13(_x0))]] [[U21(ok(_x0), ok(_x1))]] = x1 + 2x0 >= x1 + 2x0 = [[ok(U21(_x0, _x1))]] [[U22(ok(_x0))]] = x0 >= x0 = [[ok(U22(_x0))]] [[U31(ok(_x0), ok(_x1), ok(_x2))]] = x1 + x2 + 2x0 >= x1 + x2 + 2x0 = [[ok(U31(_x0, _x1, _x2))]] [[U32(ok(_x0), ok(_x1))]] = x1 + 2x0 >= x1 + 2x0 = [[ok(U32(_x0, _x1))]] [[U33(ok(_x0))]] = x0 >= x0 = [[ok(U33(_x0))]] [[U41(ok(_x0), ok(_x1))]] = x1 + 2x0 >= x1 + 2x0 = [[ok(U41(_x0, _x1))]] [[U51(ok(_x0), ok(_x1), ok(_x2))]] = x0 + x1 + 2x2 >= x0 + x1 + 2x2 = [[ok(U51(_x0, _x1, _x2))]] [[s(ok(_x0))]] = x0 >= x0 = [[ok(s(_x0))]] [[plus(ok(_x0), ok(_x1))]] = x0 + 2x1 >= x0 + 2x1 = [[ok(plus(_x0, _x1))]] [[U61(ok(_x0))]] = 2x0 >= 2x0 = [[ok(U61(_x0))]] [[U71(ok(_x0), ok(_x1), ok(_x2))]] = x0 + x1 + x2 >= x0 + x1 + x2 = [[ok(U71(_x0, _x1, _x2))]] [[x(ok(_x0), ok(_x1))]] = x0 + 2x1 >= x0 + 2x1 = [[ok(x(_x0, _x1))]] [[and(ok(_x0), ok(_x1))]] = 2x0 + 2x1 >= 2x0 + 2x1 = [[ok(and(_x0, _x1))]] [[isNatKind(ok(_x0))]] = 1 + x0 >= 1 + x0 = [[ok(isNatKind(_x0))]] [[top(ok(_x0))]] = x0 >= x0 = [[top(active(_x0))]] We can thus remove the following rules: proper(isNatKind(X)) => isNatKind(proper(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]): active(U11(X, Y, Z)) >? U11(active(X), Y, Z) active(U12(X, Y)) >? U12(active(X), Y) active(U13(X)) >? U13(active(X)) active(U21(X, Y)) >? U21(active(X), Y) active(U22(X)) >? U22(active(X)) active(U31(X, Y, Z)) >? U31(active(X), Y, Z) active(U32(X, Y)) >? U32(active(X), Y) active(U33(X)) >? U33(active(X)) active(U41(X, Y)) >? U41(active(X), Y) active(U51(X, Y, Z)) >? U51(active(X), Y, Z) active(s(X)) >? s(active(X)) active(plus(X, Y)) >? plus(active(X), Y) active(plus(X, Y)) >? plus(X, active(Y)) active(U61(X)) >? U61(active(X)) active(U71(X, Y, Z)) >? U71(active(X), Y, Z) active(x(X, Y)) >? x(active(X), Y) active(x(X, Y)) >? x(X, active(Y)) active(and(X, Y)) >? and(active(X), Y) proper(U21(X, Y)) >? U21(proper(X), proper(Y)) proper(U22(X)) >? U22(proper(X)) proper(U31(X, Y, Z)) >? U31(proper(X), proper(Y), proper(Z)) proper(U51(X, Y, Z)) >? U51(proper(X), proper(Y), proper(Z)) proper(plus(X, Y)) >? plus(proper(X), proper(Y)) proper(x(X, Y)) >? x(proper(X), proper(Y)) proper(and(X, Y)) >? and(proper(X), proper(Y)) U11(ok(X), ok(Y), ok(Z)) >? ok(U11(X, Y, Z)) U12(ok(X), ok(Y)) >? ok(U12(X, Y)) isNat(ok(X)) >? ok(isNat(X)) U13(ok(X)) >? ok(U13(X)) U21(ok(X), ok(Y)) >? ok(U21(X, Y)) U22(ok(X)) >? ok(U22(X)) U31(ok(X), ok(Y), ok(Z)) >? ok(U31(X, Y, Z)) U32(ok(X), ok(Y)) >? ok(U32(X, Y)) U33(ok(X)) >? ok(U33(X)) U41(ok(X), ok(Y)) >? ok(U41(X, Y)) U51(ok(X), ok(Y), ok(Z)) >? ok(U51(X, Y, Z)) s(ok(X)) >? ok(s(X)) plus(ok(X), ok(Y)) >? ok(plus(X, Y)) U61(ok(X)) >? ok(U61(X)) U71(ok(X), ok(Y), ok(Z)) >? ok(U71(X, Y, Z)) x(ok(X), ok(Y)) >? ok(x(X, Y)) and(ok(X), ok(Y)) >? ok(and(X, Y)) isNatKind(ok(X)) >? ok(isNatKind(X)) top(ok(X)) >? top(active(X)) We orient these requirements with a polynomial interpretation in the natural numbers. The following interpretation satisfies the requirements: U11 = \y0y1y2.y0 + y1 + y2 U12 = \y0y1.y1 + 2y0 U13 = \y0.y0 U21 = \y0y1.y0 + y1 U22 = \y0.2 + y0 U31 = \y0y1y2.y1 + y2 + 2y0 U32 = \y0y1.y1 + 2y0 U33 = \y0.y0 U41 = \y0y1.y0 + y1 U51 = \y0y1y2.y0 + y1 + y2 U61 = \y0.y0 U71 = \y0y1y2.y1 + y2 + 2y0 active = \y0.y0 and = \y0y1.2y0 + 2y1 isNat = \y0.2y0 isNatKind = \y0.1 + y0 ok = \y0.y0 plus = \y0y1.1 + y0 + 2y1 proper = \y0.2y0 s = \y0.y0 top = \y0.y0 x = \y0y1.y0 + y1 Using this interpretation, the requirements translate to: [[active(U11(_x0, _x1, _x2))]] = x0 + x1 + x2 >= x0 + x1 + x2 = [[U11(active(_x0), _x1, _x2)]] [[active(U12(_x0, _x1))]] = x1 + 2x0 >= x1 + 2x0 = [[U12(active(_x0), _x1)]] [[active(U13(_x0))]] = x0 >= x0 = [[U13(active(_x0))]] [[active(U21(_x0, _x1))]] = x0 + x1 >= x0 + x1 = [[U21(active(_x0), _x1)]] [[active(U22(_x0))]] = 2 + x0 >= 2 + x0 = [[U22(active(_x0))]] [[active(U31(_x0, _x1, _x2))]] = x1 + x2 + 2x0 >= x1 + x2 + 2x0 = [[U31(active(_x0), _x1, _x2)]] [[active(U32(_x0, _x1))]] = x1 + 2x0 >= x1 + 2x0 = [[U32(active(_x0), _x1)]] [[active(U33(_x0))]] = x0 >= x0 = [[U33(active(_x0))]] [[active(U41(_x0, _x1))]] = x0 + x1 >= x0 + x1 = [[U41(active(_x0), _x1)]] [[active(U51(_x0, _x1, _x2))]] = x0 + x1 + x2 >= x0 + x1 + x2 = [[U51(active(_x0), _x1, _x2)]] [[active(s(_x0))]] = x0 >= x0 = [[s(active(_x0))]] [[active(plus(_x0, _x1))]] = 1 + x0 + 2x1 >= 1 + x0 + 2x1 = [[plus(active(_x0), _x1)]] [[active(plus(_x0, _x1))]] = 1 + x0 + 2x1 >= 1 + x0 + 2x1 = [[plus(_x0, active(_x1))]] [[active(U61(_x0))]] = x0 >= x0 = [[U61(active(_x0))]] [[active(U71(_x0, _x1, _x2))]] = x1 + x2 + 2x0 >= x1 + x2 + 2x0 = [[U71(active(_x0), _x1, _x2)]] [[active(x(_x0, _x1))]] = x0 + x1 >= x0 + x1 = [[x(active(_x0), _x1)]] [[active(x(_x0, _x1))]] = x0 + x1 >= x0 + x1 = [[x(_x0, active(_x1))]] [[active(and(_x0, _x1))]] = 2x0 + 2x1 >= 2x0 + 2x1 = [[and(active(_x0), _x1)]] [[proper(U21(_x0, _x1))]] = 2x0 + 2x1 >= 2x0 + 2x1 = [[U21(proper(_x0), proper(_x1))]] [[proper(U22(_x0))]] = 4 + 2x0 > 2 + 2x0 = [[U22(proper(_x0))]] [[proper(U31(_x0, _x1, _x2))]] = 2x1 + 2x2 + 4x0 >= 2x1 + 2x2 + 4x0 = [[U31(proper(_x0), proper(_x1), proper(_x2))]] [[proper(U51(_x0, _x1, _x2))]] = 2x0 + 2x1 + 2x2 >= 2x0 + 2x1 + 2x2 = [[U51(proper(_x0), proper(_x1), proper(_x2))]] [[proper(plus(_x0, _x1))]] = 2 + 2x0 + 4x1 > 1 + 2x0 + 4x1 = [[plus(proper(_x0), proper(_x1))]] [[proper(x(_x0, _x1))]] = 2x0 + 2x1 >= 2x0 + 2x1 = [[x(proper(_x0), proper(_x1))]] [[proper(and(_x0, _x1))]] = 4x0 + 4x1 >= 4x0 + 4x1 = [[and(proper(_x0), proper(_x1))]] [[U11(ok(_x0), ok(_x1), ok(_x2))]] = x0 + x1 + x2 >= x0 + x1 + x2 = [[ok(U11(_x0, _x1, _x2))]] [[U12(ok(_x0), ok(_x1))]] = x1 + 2x0 >= x1 + 2x0 = [[ok(U12(_x0, _x1))]] [[isNat(ok(_x0))]] = 2x0 >= 2x0 = [[ok(isNat(_x0))]] [[U13(ok(_x0))]] = x0 >= x0 = [[ok(U13(_x0))]] [[U21(ok(_x0), ok(_x1))]] = x0 + x1 >= x0 + x1 = [[ok(U21(_x0, _x1))]] [[U22(ok(_x0))]] = 2 + x0 >= 2 + x0 = [[ok(U22(_x0))]] [[U31(ok(_x0), ok(_x1), ok(_x2))]] = x1 + x2 + 2x0 >= x1 + x2 + 2x0 = [[ok(U31(_x0, _x1, _x2))]] [[U32(ok(_x0), ok(_x1))]] = x1 + 2x0 >= x1 + 2x0 = [[ok(U32(_x0, _x1))]] [[U33(ok(_x0))]] = x0 >= x0 = [[ok(U33(_x0))]] [[U41(ok(_x0), ok(_x1))]] = x0 + x1 >= x0 + x1 = [[ok(U41(_x0, _x1))]] [[U51(ok(_x0), ok(_x1), ok(_x2))]] = x0 + x1 + x2 >= x0 + x1 + x2 = [[ok(U51(_x0, _x1, _x2))]] [[s(ok(_x0))]] = x0 >= x0 = [[ok(s(_x0))]] [[plus(ok(_x0), ok(_x1))]] = 1 + x0 + 2x1 >= 1 + x0 + 2x1 = [[ok(plus(_x0, _x1))]] [[U61(ok(_x0))]] = x0 >= x0 = [[ok(U61(_x0))]] [[U71(ok(_x0), ok(_x1), ok(_x2))]] = x1 + x2 + 2x0 >= x1 + x2 + 2x0 = [[ok(U71(_x0, _x1, _x2))]] [[x(ok(_x0), ok(_x1))]] = x0 + x1 >= x0 + x1 = [[ok(x(_x0, _x1))]] [[and(ok(_x0), ok(_x1))]] = 2x0 + 2x1 >= 2x0 + 2x1 = [[ok(and(_x0, _x1))]] [[isNatKind(ok(_x0))]] = 1 + x0 >= 1 + x0 = [[ok(isNatKind(_x0))]] [[top(ok(_x0))]] = x0 >= x0 = [[top(active(_x0))]] We can thus remove the following rules: proper(U22(X)) => U22(proper(X)) proper(plus(X, Y)) => plus(proper(X), proper(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]): active(U11(X, Y, Z)) >? U11(active(X), Y, Z) active(U12(X, Y)) >? U12(active(X), Y) active(U13(X)) >? U13(active(X)) active(U21(X, Y)) >? U21(active(X), Y) active(U22(X)) >? U22(active(X)) active(U31(X, Y, Z)) >? U31(active(X), Y, Z) active(U32(X, Y)) >? U32(active(X), Y) active(U33(X)) >? U33(active(X)) active(U41(X, Y)) >? U41(active(X), Y) active(U51(X, Y, Z)) >? U51(active(X), Y, Z) active(s(X)) >? s(active(X)) active(plus(X, Y)) >? plus(active(X), Y) active(plus(X, Y)) >? plus(X, active(Y)) active(U61(X)) >? U61(active(X)) active(U71(X, Y, Z)) >? U71(active(X), Y, Z) active(x(X, Y)) >? x(active(X), Y) active(x(X, Y)) >? x(X, active(Y)) active(and(X, Y)) >? and(active(X), Y) proper(U21(X, Y)) >? U21(proper(X), proper(Y)) proper(U31(X, Y, Z)) >? U31(proper(X), proper(Y), proper(Z)) proper(U51(X, Y, Z)) >? U51(proper(X), proper(Y), proper(Z)) proper(x(X, Y)) >? x(proper(X), proper(Y)) proper(and(X, Y)) >? and(proper(X), proper(Y)) U11(ok(X), ok(Y), ok(Z)) >? ok(U11(X, Y, Z)) U12(ok(X), ok(Y)) >? ok(U12(X, Y)) isNat(ok(X)) >? ok(isNat(X)) U13(ok(X)) >? ok(U13(X)) U21(ok(X), ok(Y)) >? ok(U21(X, Y)) U22(ok(X)) >? ok(U22(X)) U31(ok(X), ok(Y), ok(Z)) >? ok(U31(X, Y, Z)) U32(ok(X), ok(Y)) >? ok(U32(X, Y)) U33(ok(X)) >? ok(U33(X)) U41(ok(X), ok(Y)) >? ok(U41(X, Y)) U51(ok(X), ok(Y), ok(Z)) >? ok(U51(X, Y, Z)) s(ok(X)) >? ok(s(X)) plus(ok(X), ok(Y)) >? ok(plus(X, Y)) U61(ok(X)) >? ok(U61(X)) U71(ok(X), ok(Y), ok(Z)) >? ok(U71(X, Y, Z)) x(ok(X), ok(Y)) >? ok(x(X, Y)) and(ok(X), ok(Y)) >? ok(and(X, Y)) isNatKind(ok(X)) >? ok(isNatKind(X)) top(ok(X)) >? top(active(X)) We orient these requirements with a polynomial interpretation in the natural numbers. The following interpretation satisfies the requirements: U11 = \y0y1y2.y1 + y2 + 2y0 U12 = \y0y1.y0 + y1 U13 = \y0.2y0 U21 = \y0y1.2 + y0 + y1 U22 = \y0.2y0 U31 = \y0y1y2.y1 + y2 + 2y0 U32 = \y0y1.y0 + y1 U33 = \y0.y0 U41 = \y0y1.y1 + 2y0 U51 = \y0y1y2.y0 + y1 + y2 U61 = \y0.2y0 U71 = \y0y1y2.y0 + y1 + y2 active = \y0.y0 and = \y0y1.y1 + 2y0 isNat = \y0.1 + 2y0 isNatKind = \y0.y0 ok = \y0.y0 plus = \y0y1.1 + 2y0 + 2y1 proper = \y0.2y0 s = \y0.2y0 top = \y0.y0 x = \y0y1.2y0 + 2y1 Using this interpretation, the requirements translate to: [[active(U11(_x0, _x1, _x2))]] = x1 + x2 + 2x0 >= x1 + x2 + 2x0 = [[U11(active(_x0), _x1, _x2)]] [[active(U12(_x0, _x1))]] = x0 + x1 >= x0 + x1 = [[U12(active(_x0), _x1)]] [[active(U13(_x0))]] = 2x0 >= 2x0 = [[U13(active(_x0))]] [[active(U21(_x0, _x1))]] = 2 + x0 + x1 >= 2 + x0 + x1 = [[U21(active(_x0), _x1)]] [[active(U22(_x0))]] = 2x0 >= 2x0 = [[U22(active(_x0))]] [[active(U31(_x0, _x1, _x2))]] = x1 + x2 + 2x0 >= x1 + x2 + 2x0 = [[U31(active(_x0), _x1, _x2)]] [[active(U32(_x0, _x1))]] = x0 + x1 >= x0 + x1 = [[U32(active(_x0), _x1)]] [[active(U33(_x0))]] = x0 >= x0 = [[U33(active(_x0))]] [[active(U41(_x0, _x1))]] = x1 + 2x0 >= x1 + 2x0 = [[U41(active(_x0), _x1)]] [[active(U51(_x0, _x1, _x2))]] = x0 + x1 + x2 >= x0 + x1 + x2 = [[U51(active(_x0), _x1, _x2)]] [[active(s(_x0))]] = 2x0 >= 2x0 = [[s(active(_x0))]] [[active(plus(_x0, _x1))]] = 1 + 2x0 + 2x1 >= 1 + 2x0 + 2x1 = [[plus(active(_x0), _x1)]] [[active(plus(_x0, _x1))]] = 1 + 2x0 + 2x1 >= 1 + 2x0 + 2x1 = [[plus(_x0, active(_x1))]] [[active(U61(_x0))]] = 2x0 >= 2x0 = [[U61(active(_x0))]] [[active(U71(_x0, _x1, _x2))]] = x0 + x1 + x2 >= x0 + x1 + x2 = [[U71(active(_x0), _x1, _x2)]] [[active(x(_x0, _x1))]] = 2x0 + 2x1 >= 2x0 + 2x1 = [[x(active(_x0), _x1)]] [[active(x(_x0, _x1))]] = 2x0 + 2x1 >= 2x0 + 2x1 = [[x(_x0, active(_x1))]] [[active(and(_x0, _x1))]] = x1 + 2x0 >= x1 + 2x0 = [[and(active(_x0), _x1)]] [[proper(U21(_x0, _x1))]] = 4 + 2x0 + 2x1 > 2 + 2x0 + 2x1 = [[U21(proper(_x0), proper(_x1))]] [[proper(U31(_x0, _x1, _x2))]] = 2x1 + 2x2 + 4x0 >= 2x1 + 2x2 + 4x0 = [[U31(proper(_x0), proper(_x1), proper(_x2))]] [[proper(U51(_x0, _x1, _x2))]] = 2x0 + 2x1 + 2x2 >= 2x0 + 2x1 + 2x2 = [[U51(proper(_x0), proper(_x1), proper(_x2))]] [[proper(x(_x0, _x1))]] = 4x0 + 4x1 >= 4x0 + 4x1 = [[x(proper(_x0), proper(_x1))]] [[proper(and(_x0, _x1))]] = 2x1 + 4x0 >= 2x1 + 4x0 = [[and(proper(_x0), proper(_x1))]] [[U11(ok(_x0), ok(_x1), ok(_x2))]] = x1 + x2 + 2x0 >= x1 + x2 + 2x0 = [[ok(U11(_x0, _x1, _x2))]] [[U12(ok(_x0), ok(_x1))]] = x0 + x1 >= x0 + x1 = [[ok(U12(_x0, _x1))]] [[isNat(ok(_x0))]] = 1 + 2x0 >= 1 + 2x0 = [[ok(isNat(_x0))]] [[U13(ok(_x0))]] = 2x0 >= 2x0 = [[ok(U13(_x0))]] [[U21(ok(_x0), ok(_x1))]] = 2 + x0 + x1 >= 2 + x0 + x1 = [[ok(U21(_x0, _x1))]] [[U22(ok(_x0))]] = 2x0 >= 2x0 = [[ok(U22(_x0))]] [[U31(ok(_x0), ok(_x1), ok(_x2))]] = x1 + x2 + 2x0 >= x1 + x2 + 2x0 = [[ok(U31(_x0, _x1, _x2))]] [[U32(ok(_x0), ok(_x1))]] = x0 + x1 >= x0 + x1 = [[ok(U32(_x0, _x1))]] [[U33(ok(_x0))]] = x0 >= x0 = [[ok(U33(_x0))]] [[U41(ok(_x0), ok(_x1))]] = x1 + 2x0 >= x1 + 2x0 = [[ok(U41(_x0, _x1))]] [[U51(ok(_x0), ok(_x1), ok(_x2))]] = x0 + x1 + x2 >= x0 + x1 + x2 = [[ok(U51(_x0, _x1, _x2))]] [[s(ok(_x0))]] = 2x0 >= 2x0 = [[ok(s(_x0))]] [[plus(ok(_x0), ok(_x1))]] = 1 + 2x0 + 2x1 >= 1 + 2x0 + 2x1 = [[ok(plus(_x0, _x1))]] [[U61(ok(_x0))]] = 2x0 >= 2x0 = [[ok(U61(_x0))]] [[U71(ok(_x0), ok(_x1), ok(_x2))]] = x0 + x1 + x2 >= x0 + x1 + x2 = [[ok(U71(_x0, _x1, _x2))]] [[x(ok(_x0), ok(_x1))]] = 2x0 + 2x1 >= 2x0 + 2x1 = [[ok(x(_x0, _x1))]] [[and(ok(_x0), ok(_x1))]] = x1 + 2x0 >= x1 + 2x0 = [[ok(and(_x0, _x1))]] [[isNatKind(ok(_x0))]] = x0 >= x0 = [[ok(isNatKind(_x0))]] [[top(ok(_x0))]] = x0 >= x0 = [[top(active(_x0))]] We can thus remove the following rules: proper(U21(X, Y)) => U21(proper(X), proper(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]): active(U11(X, Y, Z)) >? U11(active(X), Y, Z) active(U12(X, Y)) >? U12(active(X), Y) active(U13(X)) >? U13(active(X)) active(U21(X, Y)) >? U21(active(X), Y) active(U22(X)) >? U22(active(X)) active(U31(X, Y, Z)) >? U31(active(X), Y, Z) active(U32(X, Y)) >? U32(active(X), Y) active(U33(X)) >? U33(active(X)) active(U41(X, Y)) >? U41(active(X), Y) active(U51(X, Y, Z)) >? U51(active(X), Y, Z) active(s(X)) >? s(active(X)) active(plus(X, Y)) >? plus(active(X), Y) active(plus(X, Y)) >? plus(X, active(Y)) active(U61(X)) >? U61(active(X)) active(U71(X, Y, Z)) >? U71(active(X), Y, Z) active(x(X, Y)) >? x(active(X), Y) active(x(X, Y)) >? x(X, active(Y)) active(and(X, Y)) >? and(active(X), Y) proper(U31(X, Y, Z)) >? U31(proper(X), proper(Y), proper(Z)) proper(U51(X, Y, Z)) >? U51(proper(X), proper(Y), proper(Z)) proper(x(X, Y)) >? x(proper(X), proper(Y)) proper(and(X, Y)) >? and(proper(X), proper(Y)) U11(ok(X), ok(Y), ok(Z)) >? ok(U11(X, Y, Z)) U12(ok(X), ok(Y)) >? ok(U12(X, Y)) isNat(ok(X)) >? ok(isNat(X)) U13(ok(X)) >? ok(U13(X)) U21(ok(X), ok(Y)) >? ok(U21(X, Y)) U22(ok(X)) >? ok(U22(X)) U31(ok(X), ok(Y), ok(Z)) >? ok(U31(X, Y, Z)) U32(ok(X), ok(Y)) >? ok(U32(X, Y)) U33(ok(X)) >? ok(U33(X)) U41(ok(X), ok(Y)) >? ok(U41(X, Y)) U51(ok(X), ok(Y), ok(Z)) >? ok(U51(X, Y, Z)) s(ok(X)) >? ok(s(X)) plus(ok(X), ok(Y)) >? ok(plus(X, Y)) U61(ok(X)) >? ok(U61(X)) U71(ok(X), ok(Y), ok(Z)) >? ok(U71(X, Y, Z)) x(ok(X), ok(Y)) >? ok(x(X, Y)) and(ok(X), ok(Y)) >? ok(and(X, Y)) isNatKind(ok(X)) >? ok(isNatKind(X)) top(ok(X)) >? top(active(X)) We orient these requirements with a polynomial interpretation in the natural numbers. The following interpretation satisfies the requirements: U11 = \y0y1y2.y1 + y2 + 2y0 U12 = \y0y1.y0 + 2y1 U13 = \y0.2y0 U21 = \y0y1.y0 + y1 U22 = \y0.y0 U31 = \y0y1y2.y0 + y1 + y2 U32 = \y0y1.1 + y0 + y1 U33 = \y0.2y0 U41 = \y0y1.y1 + 2y0 U51 = \y0y1y2.2 + y1 + y2 + 2y0 U61 = \y0.2y0 U71 = \y0y1y2.y0 + y1 + y2 active = \y0.y0 and = \y0y1.y0 + y1 isNat = \y0.2y0 isNatKind = \y0.y0 ok = \y0.y0 plus = \y0y1.y0 + 2y1 proper = \y0.2y0 s = \y0.y0 top = \y0.2y0 x = \y0y1.2y0 + 2y1 Using this interpretation, the requirements translate to: [[active(U11(_x0, _x1, _x2))]] = x1 + x2 + 2x0 >= x1 + x2 + 2x0 = [[U11(active(_x0), _x1, _x2)]] [[active(U12(_x0, _x1))]] = x0 + 2x1 >= x0 + 2x1 = [[U12(active(_x0), _x1)]] [[active(U13(_x0))]] = 2x0 >= 2x0 = [[U13(active(_x0))]] [[active(U21(_x0, _x1))]] = x0 + x1 >= x0 + x1 = [[U21(active(_x0), _x1)]] [[active(U22(_x0))]] = x0 >= x0 = [[U22(active(_x0))]] [[active(U31(_x0, _x1, _x2))]] = x0 + x1 + x2 >= x0 + x1 + x2 = [[U31(active(_x0), _x1, _x2)]] [[active(U32(_x0, _x1))]] = 1 + x0 + x1 >= 1 + x0 + x1 = [[U32(active(_x0), _x1)]] [[active(U33(_x0))]] = 2x0 >= 2x0 = [[U33(active(_x0))]] [[active(U41(_x0, _x1))]] = x1 + 2x0 >= x1 + 2x0 = [[U41(active(_x0), _x1)]] [[active(U51(_x0, _x1, _x2))]] = 2 + x1 + x2 + 2x0 >= 2 + x1 + x2 + 2x0 = [[U51(active(_x0), _x1, _x2)]] [[active(s(_x0))]] = x0 >= x0 = [[s(active(_x0))]] [[active(plus(_x0, _x1))]] = x0 + 2x1 >= x0 + 2x1 = [[plus(active(_x0), _x1)]] [[active(plus(_x0, _x1))]] = x0 + 2x1 >= x0 + 2x1 = [[plus(_x0, active(_x1))]] [[active(U61(_x0))]] = 2x0 >= 2x0 = [[U61(active(_x0))]] [[active(U71(_x0, _x1, _x2))]] = x0 + x1 + x2 >= x0 + x1 + x2 = [[U71(active(_x0), _x1, _x2)]] [[active(x(_x0, _x1))]] = 2x0 + 2x1 >= 2x0 + 2x1 = [[x(active(_x0), _x1)]] [[active(x(_x0, _x1))]] = 2x0 + 2x1 >= 2x0 + 2x1 = [[x(_x0, active(_x1))]] [[active(and(_x0, _x1))]] = x0 + x1 >= x0 + x1 = [[and(active(_x0), _x1)]] [[proper(U31(_x0, _x1, _x2))]] = 2x0 + 2x1 + 2x2 >= 2x0 + 2x1 + 2x2 = [[U31(proper(_x0), proper(_x1), proper(_x2))]] [[proper(U51(_x0, _x1, _x2))]] = 4 + 2x1 + 2x2 + 4x0 > 2 + 2x1 + 2x2 + 4x0 = [[U51(proper(_x0), proper(_x1), proper(_x2))]] [[proper(x(_x0, _x1))]] = 4x0 + 4x1 >= 4x0 + 4x1 = [[x(proper(_x0), proper(_x1))]] [[proper(and(_x0, _x1))]] = 2x0 + 2x1 >= 2x0 + 2x1 = [[and(proper(_x0), proper(_x1))]] [[U11(ok(_x0), ok(_x1), ok(_x2))]] = x1 + x2 + 2x0 >= x1 + x2 + 2x0 = [[ok(U11(_x0, _x1, _x2))]] [[U12(ok(_x0), ok(_x1))]] = x0 + 2x1 >= x0 + 2x1 = [[ok(U12(_x0, _x1))]] [[isNat(ok(_x0))]] = 2x0 >= 2x0 = [[ok(isNat(_x0))]] [[U13(ok(_x0))]] = 2x0 >= 2x0 = [[ok(U13(_x0))]] [[U21(ok(_x0), ok(_x1))]] = x0 + x1 >= x0 + x1 = [[ok(U21(_x0, _x1))]] [[U22(ok(_x0))]] = x0 >= x0 = [[ok(U22(_x0))]] [[U31(ok(_x0), ok(_x1), ok(_x2))]] = x0 + x1 + x2 >= x0 + x1 + x2 = [[ok(U31(_x0, _x1, _x2))]] [[U32(ok(_x0), ok(_x1))]] = 1 + x0 + x1 >= 1 + x0 + x1 = [[ok(U32(_x0, _x1))]] [[U33(ok(_x0))]] = 2x0 >= 2x0 = [[ok(U33(_x0))]] [[U41(ok(_x0), ok(_x1))]] = x1 + 2x0 >= x1 + 2x0 = [[ok(U41(_x0, _x1))]] [[U51(ok(_x0), ok(_x1), ok(_x2))]] = 2 + x1 + x2 + 2x0 >= 2 + x1 + x2 + 2x0 = [[ok(U51(_x0, _x1, _x2))]] [[s(ok(_x0))]] = x0 >= x0 = [[ok(s(_x0))]] [[plus(ok(_x0), ok(_x1))]] = x0 + 2x1 >= x0 + 2x1 = [[ok(plus(_x0, _x1))]] [[U61(ok(_x0))]] = 2x0 >= 2x0 = [[ok(U61(_x0))]] [[U71(ok(_x0), ok(_x1), ok(_x2))]] = x0 + x1 + x2 >= x0 + x1 + x2 = [[ok(U71(_x0, _x1, _x2))]] [[x(ok(_x0), ok(_x1))]] = 2x0 + 2x1 >= 2x0 + 2x1 = [[ok(x(_x0, _x1))]] [[and(ok(_x0), ok(_x1))]] = x0 + x1 >= x0 + x1 = [[ok(and(_x0, _x1))]] [[isNatKind(ok(_x0))]] = x0 >= x0 = [[ok(isNatKind(_x0))]] [[top(ok(_x0))]] = 2x0 >= 2x0 = [[top(active(_x0))]] We can thus remove the following rules: proper(U51(X, Y, Z)) => U51(proper(X), proper(Y), proper(Z)) We use rule removal, following [Kop12, Theorem 2.23]. This gives the following requirements (possibly using Theorems 2.25 and 2.26 in [Kop12]): active(U11(X, Y, Z)) >? U11(active(X), Y, Z) active(U12(X, Y)) >? U12(active(X), Y) active(U13(X)) >? U13(active(X)) active(U21(X, Y)) >? U21(active(X), Y) active(U22(X)) >? U22(active(X)) active(U31(X, Y, Z)) >? U31(active(X), Y, Z) active(U32(X, Y)) >? U32(active(X), Y) active(U33(X)) >? U33(active(X)) active(U41(X, Y)) >? U41(active(X), Y) active(U51(X, Y, Z)) >? U51(active(X), Y, Z) active(s(X)) >? s(active(X)) active(plus(X, Y)) >? plus(active(X), Y) active(plus(X, Y)) >? plus(X, active(Y)) active(U61(X)) >? U61(active(X)) active(U71(X, Y, Z)) >? U71(active(X), Y, Z) active(x(X, Y)) >? x(active(X), Y) active(x(X, Y)) >? x(X, active(Y)) active(and(X, Y)) >? and(active(X), Y) proper(U31(X, Y, Z)) >? U31(proper(X), proper(Y), proper(Z)) proper(x(X, Y)) >? x(proper(X), proper(Y)) proper(and(X, Y)) >? and(proper(X), proper(Y)) U11(ok(X), ok(Y), ok(Z)) >? ok(U11(X, Y, Z)) U12(ok(X), ok(Y)) >? ok(U12(X, Y)) isNat(ok(X)) >? ok(isNat(X)) U13(ok(X)) >? ok(U13(X)) U21(ok(X), ok(Y)) >? ok(U21(X, Y)) U22(ok(X)) >? ok(U22(X)) U31(ok(X), ok(Y), ok(Z)) >? ok(U31(X, Y, Z)) U32(ok(X), ok(Y)) >? ok(U32(X, Y)) U33(ok(X)) >? ok(U33(X)) U41(ok(X), ok(Y)) >? ok(U41(X, Y)) U51(ok(X), ok(Y), ok(Z)) >? ok(U51(X, Y, Z)) s(ok(X)) >? ok(s(X)) plus(ok(X), ok(Y)) >? ok(plus(X, Y)) U61(ok(X)) >? ok(U61(X)) U71(ok(X), ok(Y), ok(Z)) >? ok(U71(X, Y, Z)) x(ok(X), ok(Y)) >? ok(x(X, Y)) and(ok(X), ok(Y)) >? ok(and(X, Y)) isNatKind(ok(X)) >? ok(isNatKind(X)) top(ok(X)) >? top(active(X)) We orient these requirements with a polynomial interpretation in the natural numbers. The following interpretation satisfies the requirements: U11 = \y0y1y2.y0 + y1 + y2 U12 = \y0y1.y1 + 2y0 U13 = \y0.y0 U21 = \y0y1.y1 + 2y0 U22 = \y0.2y0 U31 = \y0y1y2.y0 + y1 + y2 U32 = \y0y1.y0 + y1 U33 = \y0.y0 U41 = \y0y1.y1 + 2y0 U51 = \y0y1y2.y1 + 2y0 + 2y2 U61 = \y0.y0 U71 = \y0y1y2.y0 + y1 + 2y2 active = \y0.y0 and = \y0y1.2 + 2y0 + 2y1 isNat = \y0.2y0 isNatKind = \y0.2y0 ok = \y0.y0 plus = \y0y1.y0 + 2y1 proper = \y0.2y0 s = \y0.2y0 top = \y0.y0 x = \y0y1.y0 + 2y1 Using this interpretation, the requirements translate to: [[active(U11(_x0, _x1, _x2))]] = x0 + x1 + x2 >= x0 + x1 + x2 = [[U11(active(_x0), _x1, _x2)]] [[active(U12(_x0, _x1))]] = x1 + 2x0 >= x1 + 2x0 = [[U12(active(_x0), _x1)]] [[active(U13(_x0))]] = x0 >= x0 = [[U13(active(_x0))]] [[active(U21(_x0, _x1))]] = x1 + 2x0 >= x1 + 2x0 = [[U21(active(_x0), _x1)]] [[active(U22(_x0))]] = 2x0 >= 2x0 = [[U22(active(_x0))]] [[active(U31(_x0, _x1, _x2))]] = x0 + x1 + x2 >= x0 + x1 + x2 = [[U31(active(_x0), _x1, _x2)]] [[active(U32(_x0, _x1))]] = x0 + x1 >= x0 + x1 = [[U32(active(_x0), _x1)]] [[active(U33(_x0))]] = x0 >= x0 = [[U33(active(_x0))]] [[active(U41(_x0, _x1))]] = x1 + 2x0 >= x1 + 2x0 = [[U41(active(_x0), _x1)]] [[active(U51(_x0, _x1, _x2))]] = x1 + 2x0 + 2x2 >= x1 + 2x0 + 2x2 = [[U51(active(_x0), _x1, _x2)]] [[active(s(_x0))]] = 2x0 >= 2x0 = [[s(active(_x0))]] [[active(plus(_x0, _x1))]] = x0 + 2x1 >= x0 + 2x1 = [[plus(active(_x0), _x1)]] [[active(plus(_x0, _x1))]] = x0 + 2x1 >= x0 + 2x1 = [[plus(_x0, active(_x1))]] [[active(U61(_x0))]] = x0 >= x0 = [[U61(active(_x0))]] [[active(U71(_x0, _x1, _x2))]] = x0 + x1 + 2x2 >= x0 + x1 + 2x2 = [[U71(active(_x0), _x1, _x2)]] [[active(x(_x0, _x1))]] = x0 + 2x1 >= x0 + 2x1 = [[x(active(_x0), _x1)]] [[active(x(_x0, _x1))]] = x0 + 2x1 >= x0 + 2x1 = [[x(_x0, active(_x1))]] [[active(and(_x0, _x1))]] = 2 + 2x0 + 2x1 >= 2 + 2x0 + 2x1 = [[and(active(_x0), _x1)]] [[proper(U31(_x0, _x1, _x2))]] = 2x0 + 2x1 + 2x2 >= 2x0 + 2x1 + 2x2 = [[U31(proper(_x0), proper(_x1), proper(_x2))]] [[proper(x(_x0, _x1))]] = 2x0 + 4x1 >= 2x0 + 4x1 = [[x(proper(_x0), proper(_x1))]] [[proper(and(_x0, _x1))]] = 4 + 4x0 + 4x1 > 2 + 4x0 + 4x1 = [[and(proper(_x0), proper(_x1))]] [[U11(ok(_x0), ok(_x1), ok(_x2))]] = x0 + x1 + x2 >= x0 + x1 + x2 = [[ok(U11(_x0, _x1, _x2))]] [[U12(ok(_x0), ok(_x1))]] = x1 + 2x0 >= x1 + 2x0 = [[ok(U12(_x0, _x1))]] [[isNat(ok(_x0))]] = 2x0 >= 2x0 = [[ok(isNat(_x0))]] [[U13(ok(_x0))]] = x0 >= x0 = [[ok(U13(_x0))]] [[U21(ok(_x0), ok(_x1))]] = x1 + 2x0 >= x1 + 2x0 = [[ok(U21(_x0, _x1))]] [[U22(ok(_x0))]] = 2x0 >= 2x0 = [[ok(U22(_x0))]] [[U31(ok(_x0), ok(_x1), ok(_x2))]] = x0 + x1 + x2 >= x0 + x1 + x2 = [[ok(U31(_x0, _x1, _x2))]] [[U32(ok(_x0), ok(_x1))]] = x0 + x1 >= x0 + x1 = [[ok(U32(_x0, _x1))]] [[U33(ok(_x0))]] = x0 >= x0 = [[ok(U33(_x0))]] [[U41(ok(_x0), ok(_x1))]] = x1 + 2x0 >= x1 + 2x0 = [[ok(U41(_x0, _x1))]] [[U51(ok(_x0), ok(_x1), ok(_x2))]] = x1 + 2x0 + 2x2 >= x1 + 2x0 + 2x2 = [[ok(U51(_x0, _x1, _x2))]] [[s(ok(_x0))]] = 2x0 >= 2x0 = [[ok(s(_x0))]] [[plus(ok(_x0), ok(_x1))]] = x0 + 2x1 >= x0 + 2x1 = [[ok(plus(_x0, _x1))]] [[U61(ok(_x0))]] = x0 >= x0 = [[ok(U61(_x0))]] [[U71(ok(_x0), ok(_x1), ok(_x2))]] = x0 + x1 + 2x2 >= x0 + x1 + 2x2 = [[ok(U71(_x0, _x1, _x2))]] [[x(ok(_x0), ok(_x1))]] = x0 + 2x1 >= x0 + 2x1 = [[ok(x(_x0, _x1))]] [[and(ok(_x0), ok(_x1))]] = 2 + 2x0 + 2x1 >= 2 + 2x0 + 2x1 = [[ok(and(_x0, _x1))]] [[isNatKind(ok(_x0))]] = 2x0 >= 2x0 = [[ok(isNatKind(_x0))]] [[top(ok(_x0))]] = x0 >= x0 = [[top(active(_x0))]] We can thus remove the following rules: proper(and(X, Y)) => and(proper(X), proper(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]): active(U11(X, Y, Z)) >? U11(active(X), Y, Z) active(U12(X, Y)) >? U12(active(X), Y) active(U13(X)) >? U13(active(X)) active(U21(X, Y)) >? U21(active(X), Y) active(U22(X)) >? U22(active(X)) active(U31(X, Y, Z)) >? U31(active(X), Y, Z) active(U32(X, Y)) >? U32(active(X), Y) active(U33(X)) >? U33(active(X)) active(U41(X, Y)) >? U41(active(X), Y) active(U51(X, Y, Z)) >? U51(active(X), Y, Z) active(s(X)) >? s(active(X)) active(plus(X, Y)) >? plus(active(X), Y) active(plus(X, Y)) >? plus(X, active(Y)) active(U61(X)) >? U61(active(X)) active(U71(X, Y, Z)) >? U71(active(X), Y, Z) active(x(X, Y)) >? x(active(X), Y) active(x(X, Y)) >? x(X, active(Y)) active(and(X, Y)) >? and(active(X), Y) proper(U31(X, Y, Z)) >? U31(proper(X), proper(Y), proper(Z)) proper(x(X, Y)) >? x(proper(X), proper(Y)) U11(ok(X), ok(Y), ok(Z)) >? ok(U11(X, Y, Z)) U12(ok(X), ok(Y)) >? ok(U12(X, Y)) isNat(ok(X)) >? ok(isNat(X)) U13(ok(X)) >? ok(U13(X)) U21(ok(X), ok(Y)) >? ok(U21(X, Y)) U22(ok(X)) >? ok(U22(X)) U31(ok(X), ok(Y), ok(Z)) >? ok(U31(X, Y, Z)) U32(ok(X), ok(Y)) >? ok(U32(X, Y)) U33(ok(X)) >? ok(U33(X)) U41(ok(X), ok(Y)) >? ok(U41(X, Y)) U51(ok(X), ok(Y), ok(Z)) >? ok(U51(X, Y, Z)) s(ok(X)) >? ok(s(X)) plus(ok(X), ok(Y)) >? ok(plus(X, Y)) U61(ok(X)) >? ok(U61(X)) U71(ok(X), ok(Y), ok(Z)) >? ok(U71(X, Y, Z)) x(ok(X), ok(Y)) >? ok(x(X, Y)) and(ok(X), ok(Y)) >? ok(and(X, Y)) isNatKind(ok(X)) >? ok(isNatKind(X)) top(ok(X)) >? top(active(X)) We orient these requirements with a polynomial interpretation in the natural numbers. The following interpretation satisfies the requirements: U11 = \y0y1y2.2 + 2y0 + 2y1 + 2y2 U12 = \y0y1.2y0 + 2y1 U13 = \y0.y0 U21 = \y0y1.y1 + 2y0 U22 = \y0.y0 U31 = \y0y1y2.y0 + y1 + y2 U32 = \y0y1.y0 + y1 U33 = \y0.y0 U41 = \y0y1.2y0 + 2y1 U51 = \y0y1y2.y0 + y2 + 3y1 U61 = \y0.2y0 U71 = \y0y1y2.y0 + y1 + y2 active = \y0.2y0 and = \y0y1.y0 + y1 isNat = \y0.y0 isNatKind = \y0.y0 ok = \y0.1 + 2y0 plus = \y0y1.y1 + 2y0 proper = \y0.y0 s = \y0.2y0 top = \y0.2y0 x = \y0y1.y1 + 2y0 Using this interpretation, the requirements translate to: [[active(U11(_x0, _x1, _x2))]] = 4 + 4x0 + 4x1 + 4x2 > 2 + 2x1 + 2x2 + 4x0 = [[U11(active(_x0), _x1, _x2)]] [[active(U12(_x0, _x1))]] = 4x0 + 4x1 >= 2x1 + 4x0 = [[U12(active(_x0), _x1)]] [[active(U13(_x0))]] = 2x0 >= 2x0 = [[U13(active(_x0))]] [[active(U21(_x0, _x1))]] = 2x1 + 4x0 >= x1 + 4x0 = [[U21(active(_x0), _x1)]] [[active(U22(_x0))]] = 2x0 >= 2x0 = [[U22(active(_x0))]] [[active(U31(_x0, _x1, _x2))]] = 2x0 + 2x1 + 2x2 >= x1 + x2 + 2x0 = [[U31(active(_x0), _x1, _x2)]] [[active(U32(_x0, _x1))]] = 2x0 + 2x1 >= x1 + 2x0 = [[U32(active(_x0), _x1)]] [[active(U33(_x0))]] = 2x0 >= 2x0 = [[U33(active(_x0))]] [[active(U41(_x0, _x1))]] = 4x0 + 4x1 >= 2x1 + 4x0 = [[U41(active(_x0), _x1)]] [[active(U51(_x0, _x1, _x2))]] = 2x0 + 2x2 + 6x1 >= x2 + 2x0 + 3x1 = [[U51(active(_x0), _x1, _x2)]] [[active(s(_x0))]] = 4x0 >= 4x0 = [[s(active(_x0))]] [[active(plus(_x0, _x1))]] = 2x1 + 4x0 >= x1 + 4x0 = [[plus(active(_x0), _x1)]] [[active(plus(_x0, _x1))]] = 2x1 + 4x0 >= 2x0 + 2x1 = [[plus(_x0, active(_x1))]] [[active(U61(_x0))]] = 4x0 >= 4x0 = [[U61(active(_x0))]] [[active(U71(_x0, _x1, _x2))]] = 2x0 + 2x1 + 2x2 >= x1 + x2 + 2x0 = [[U71(active(_x0), _x1, _x2)]] [[active(x(_x0, _x1))]] = 2x1 + 4x0 >= x1 + 4x0 = [[x(active(_x0), _x1)]] [[active(x(_x0, _x1))]] = 2x1 + 4x0 >= 2x0 + 2x1 = [[x(_x0, active(_x1))]] [[active(and(_x0, _x1))]] = 2x0 + 2x1 >= x1 + 2x0 = [[and(active(_x0), _x1)]] [[proper(U31(_x0, _x1, _x2))]] = x0 + x1 + x2 >= x0 + x1 + x2 = [[U31(proper(_x0), proper(_x1), proper(_x2))]] [[proper(x(_x0, _x1))]] = x1 + 2x0 >= x1 + 2x0 = [[x(proper(_x0), proper(_x1))]] [[U11(ok(_x0), ok(_x1), ok(_x2))]] = 8 + 4x0 + 4x1 + 4x2 > 5 + 4x0 + 4x1 + 4x2 = [[ok(U11(_x0, _x1, _x2))]] [[U12(ok(_x0), ok(_x1))]] = 4 + 4x0 + 4x1 > 1 + 4x0 + 4x1 = [[ok(U12(_x0, _x1))]] [[isNat(ok(_x0))]] = 1 + 2x0 >= 1 + 2x0 = [[ok(isNat(_x0))]] [[U13(ok(_x0))]] = 1 + 2x0 >= 1 + 2x0 = [[ok(U13(_x0))]] [[U21(ok(_x0), ok(_x1))]] = 3 + 2x1 + 4x0 > 1 + 2x1 + 4x0 = [[ok(U21(_x0, _x1))]] [[U22(ok(_x0))]] = 1 + 2x0 >= 1 + 2x0 = [[ok(U22(_x0))]] [[U31(ok(_x0), ok(_x1), ok(_x2))]] = 3 + 2x0 + 2x1 + 2x2 > 1 + 2x0 + 2x1 + 2x2 = [[ok(U31(_x0, _x1, _x2))]] [[U32(ok(_x0), ok(_x1))]] = 2 + 2x0 + 2x1 > 1 + 2x0 + 2x1 = [[ok(U32(_x0, _x1))]] [[U33(ok(_x0))]] = 1 + 2x0 >= 1 + 2x0 = [[ok(U33(_x0))]] [[U41(ok(_x0), ok(_x1))]] = 4 + 4x0 + 4x1 > 1 + 4x0 + 4x1 = [[ok(U41(_x0, _x1))]] [[U51(ok(_x0), ok(_x1), ok(_x2))]] = 5 + 2x0 + 2x2 + 6x1 > 1 + 2x0 + 2x2 + 6x1 = [[ok(U51(_x0, _x1, _x2))]] [[s(ok(_x0))]] = 2 + 4x0 > 1 + 4x0 = [[ok(s(_x0))]] [[plus(ok(_x0), ok(_x1))]] = 3 + 2x1 + 4x0 > 1 + 2x1 + 4x0 = [[ok(plus(_x0, _x1))]] [[U61(ok(_x0))]] = 2 + 4x0 > 1 + 4x0 = [[ok(U61(_x0))]] [[U71(ok(_x0), ok(_x1), ok(_x2))]] = 3 + 2x0 + 2x1 + 2x2 > 1 + 2x0 + 2x1 + 2x2 = [[ok(U71(_x0, _x1, _x2))]] [[x(ok(_x0), ok(_x1))]] = 3 + 2x1 + 4x0 > 1 + 2x1 + 4x0 = [[ok(x(_x0, _x1))]] [[and(ok(_x0), ok(_x1))]] = 2 + 2x0 + 2x1 > 1 + 2x0 + 2x1 = [[ok(and(_x0, _x1))]] [[isNatKind(ok(_x0))]] = 1 + 2x0 >= 1 + 2x0 = [[ok(isNatKind(_x0))]] [[top(ok(_x0))]] = 2 + 4x0 > 4x0 = [[top(active(_x0))]] We can thus remove the following rules: active(U11(X, Y, Z)) => U11(active(X), Y, Z) U11(ok(X), ok(Y), ok(Z)) => ok(U11(X, Y, Z)) U12(ok(X), ok(Y)) => ok(U12(X, Y)) U21(ok(X), ok(Y)) => ok(U21(X, Y)) U31(ok(X), ok(Y), ok(Z)) => ok(U31(X, Y, Z)) U32(ok(X), ok(Y)) => ok(U32(X, Y)) U41(ok(X), ok(Y)) => ok(U41(X, Y)) U51(ok(X), ok(Y), ok(Z)) => ok(U51(X, Y, Z)) s(ok(X)) => ok(s(X)) plus(ok(X), ok(Y)) => ok(plus(X, Y)) U61(ok(X)) => ok(U61(X)) U71(ok(X), ok(Y), ok(Z)) => ok(U71(X, Y, Z)) x(ok(X), ok(Y)) => ok(x(X, Y)) and(ok(X), ok(Y)) => ok(and(X, Y)) top(ok(X)) => top(active(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]): active(U12(X, Y)) >? U12(active(X), Y) active(U13(X)) >? U13(active(X)) active(U21(X, Y)) >? U21(active(X), Y) active(U22(X)) >? U22(active(X)) active(U31(X, Y, Z)) >? U31(active(X), Y, Z) active(U32(X, Y)) >? U32(active(X), Y) active(U33(X)) >? U33(active(X)) active(U41(X, Y)) >? U41(active(X), Y) active(U51(X, Y, Z)) >? U51(active(X), Y, Z) active(s(X)) >? s(active(X)) active(plus(X, Y)) >? plus(active(X), Y) active(plus(X, Y)) >? plus(X, active(Y)) active(U61(X)) >? U61(active(X)) active(U71(X, Y, Z)) >? U71(active(X), Y, Z) active(x(X, Y)) >? x(active(X), Y) active(x(X, Y)) >? x(X, active(Y)) active(and(X, Y)) >? and(active(X), Y) proper(U31(X, Y, Z)) >? U31(proper(X), proper(Y), proper(Z)) proper(x(X, Y)) >? x(proper(X), proper(Y)) isNat(ok(X)) >? ok(isNat(X)) U13(ok(X)) >? ok(U13(X)) U22(ok(X)) >? ok(U22(X)) U33(ok(X)) >? ok(U33(X)) isNatKind(ok(X)) >? ok(isNatKind(X)) We orient these requirements with a polynomial interpretation in the natural numbers. The following interpretation satisfies the requirements: U12 = \y0y1.y0 + y1 U13 = \y0.3 + 2y0 U21 = \y0y1.y0 + y1 U22 = \y0.3 + y0 U31 = \y0y1y2.3 + y0 + y1 + y2 U32 = \y0y1.y0 + y1 U33 = \y0.3 + 2y0 U41 = \y0y1.y0 + y1 U51 = \y0y1y2.y0 + y1 + y2 U61 = \y0.y0 U71 = \y0y1y2.y0 + y1 + y2 active = \y0.3y0 and = \y0y1.y0 + y1 isNat = \y0.3y0 isNatKind = \y0.3y0 ok = \y0.2 + y0 plus = \y0y1.3 + y0 + y1 proper = \y0.1 + 3y0 s = \y0.y0 x = \y0y1.3 + y0 + y1 Using this interpretation, the requirements translate to: [[active(U12(_x0, _x1))]] = 3x0 + 3x1 >= x1 + 3x0 = [[U12(active(_x0), _x1)]] [[active(U13(_x0))]] = 9 + 6x0 > 3 + 6x0 = [[U13(active(_x0))]] [[active(U21(_x0, _x1))]] = 3x0 + 3x1 >= x1 + 3x0 = [[U21(active(_x0), _x1)]] [[active(U22(_x0))]] = 9 + 3x0 > 3 + 3x0 = [[U22(active(_x0))]] [[active(U31(_x0, _x1, _x2))]] = 9 + 3x0 + 3x1 + 3x2 > 3 + x1 + x2 + 3x0 = [[U31(active(_x0), _x1, _x2)]] [[active(U32(_x0, _x1))]] = 3x0 + 3x1 >= x1 + 3x0 = [[U32(active(_x0), _x1)]] [[active(U33(_x0))]] = 9 + 6x0 > 3 + 6x0 = [[U33(active(_x0))]] [[active(U41(_x0, _x1))]] = 3x0 + 3x1 >= x1 + 3x0 = [[U41(active(_x0), _x1)]] [[active(U51(_x0, _x1, _x2))]] = 3x0 + 3x1 + 3x2 >= x1 + x2 + 3x0 = [[U51(active(_x0), _x1, _x2)]] [[active(s(_x0))]] = 3x0 >= 3x0 = [[s(active(_x0))]] [[active(plus(_x0, _x1))]] = 9 + 3x0 + 3x1 > 3 + x1 + 3x0 = [[plus(active(_x0), _x1)]] [[active(plus(_x0, _x1))]] = 9 + 3x0 + 3x1 > 3 + x0 + 3x1 = [[plus(_x0, active(_x1))]] [[active(U61(_x0))]] = 3x0 >= 3x0 = [[U61(active(_x0))]] [[active(U71(_x0, _x1, _x2))]] = 3x0 + 3x1 + 3x2 >= x1 + x2 + 3x0 = [[U71(active(_x0), _x1, _x2)]] [[active(x(_x0, _x1))]] = 9 + 3x0 + 3x1 > 3 + x1 + 3x0 = [[x(active(_x0), _x1)]] [[active(x(_x0, _x1))]] = 9 + 3x0 + 3x1 > 3 + x0 + 3x1 = [[x(_x0, active(_x1))]] [[active(and(_x0, _x1))]] = 3x0 + 3x1 >= x1 + 3x0 = [[and(active(_x0), _x1)]] [[proper(U31(_x0, _x1, _x2))]] = 10 + 3x0 + 3x1 + 3x2 > 6 + 3x0 + 3x1 + 3x2 = [[U31(proper(_x0), proper(_x1), proper(_x2))]] [[proper(x(_x0, _x1))]] = 10 + 3x0 + 3x1 > 5 + 3x0 + 3x1 = [[x(proper(_x0), proper(_x1))]] [[isNat(ok(_x0))]] = 6 + 3x0 > 2 + 3x0 = [[ok(isNat(_x0))]] [[U13(ok(_x0))]] = 7 + 2x0 > 5 + 2x0 = [[ok(U13(_x0))]] [[U22(ok(_x0))]] = 5 + x0 >= 5 + x0 = [[ok(U22(_x0))]] [[U33(ok(_x0))]] = 7 + 2x0 > 5 + 2x0 = [[ok(U33(_x0))]] [[isNatKind(ok(_x0))]] = 6 + 3x0 > 2 + 3x0 = [[ok(isNatKind(_x0))]] We can thus remove the following rules: active(U13(X)) => U13(active(X)) active(U22(X)) => U22(active(X)) active(U31(X, Y, Z)) => U31(active(X), Y, Z) active(U33(X)) => U33(active(X)) active(plus(X, Y)) => plus(active(X), Y) active(plus(X, Y)) => plus(X, active(Y)) active(x(X, Y)) => x(active(X), Y) active(x(X, Y)) => x(X, active(Y)) proper(U31(X, Y, Z)) => U31(proper(X), proper(Y), proper(Z)) proper(x(X, Y)) => x(proper(X), proper(Y)) isNat(ok(X)) => ok(isNat(X)) U13(ok(X)) => ok(U13(X)) U33(ok(X)) => ok(U33(X)) isNatKind(ok(X)) => ok(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]): active(U12(X, Y)) >? U12(active(X), Y) active(U21(X, Y)) >? U21(active(X), Y) active(U32(X, Y)) >? U32(active(X), Y) active(U41(X, Y)) >? U41(active(X), Y) active(U51(X, Y, Z)) >? U51(active(X), Y, Z) active(s(X)) >? s(active(X)) active(U61(X)) >? U61(active(X)) active(U71(X, Y, Z)) >? U71(active(X), Y, Z) active(and(X, Y)) >? and(active(X), Y) U22(ok(X)) >? ok(U22(X)) We orient these requirements with a polynomial interpretation in the natural numbers. The following interpretation satisfies the requirements: U12 = \y0y1.y0 + y1 U21 = \y0y1.y0 + y1 U22 = \y0.3y0 U32 = \y0y1.y0 + y1 U41 = \y0y1.y0 + y1 U51 = \y0y1y2.y0 + y1 + y2 U61 = \y0.y0 U71 = \y0y1y2.y0 + y1 + y2 active = \y0.3y0 and = \y0y1.y0 + y1 ok = \y0.y0 s = \y0.2 + y0 Using this interpretation, the requirements translate to: [[active(U12(_x0, _x1))]] = 3x0 + 3x1 >= x1 + 3x0 = [[U12(active(_x0), _x1)]] [[active(U21(_x0, _x1))]] = 3x0 + 3x1 >= x1 + 3x0 = [[U21(active(_x0), _x1)]] [[active(U32(_x0, _x1))]] = 3x0 + 3x1 >= x1 + 3x0 = [[U32(active(_x0), _x1)]] [[active(U41(_x0, _x1))]] = 3x0 + 3x1 >= x1 + 3x0 = [[U41(active(_x0), _x1)]] [[active(U51(_x0, _x1, _x2))]] = 3x0 + 3x1 + 3x2 >= x1 + x2 + 3x0 = [[U51(active(_x0), _x1, _x2)]] [[active(s(_x0))]] = 6 + 3x0 > 2 + 3x0 = [[s(active(_x0))]] [[active(U61(_x0))]] = 3x0 >= 3x0 = [[U61(active(_x0))]] [[active(U71(_x0, _x1, _x2))]] = 3x0 + 3x1 + 3x2 >= x1 + x2 + 3x0 = [[U71(active(_x0), _x1, _x2)]] [[active(and(_x0, _x1))]] = 3x0 + 3x1 >= x1 + 3x0 = [[and(active(_x0), _x1)]] [[U22(ok(_x0))]] = 3x0 >= 3x0 = [[ok(U22(_x0))]] We can thus remove the following rules: active(s(X)) => s(active(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]): active(U12(X, Y)) >? U12(active(X), Y) active(U21(X, Y)) >? U21(active(X), Y) active(U32(X, Y)) >? U32(active(X), Y) active(U41(X, Y)) >? U41(active(X), Y) active(U51(X, Y, Z)) >? U51(active(X), Y, Z) active(U61(X)) >? U61(active(X)) active(U71(X, Y, Z)) >? U71(active(X), Y, Z) active(and(X, Y)) >? and(active(X), Y) U22(ok(X)) >? ok(U22(X)) We orient these requirements with a polynomial interpretation in the natural numbers. The following interpretation satisfies the requirements: U12 = \y0y1.y0 + y1 U21 = \y0y1.y0 + y1 U22 = \y0.3y0 U32 = \y0y1.y0 + y1 U41 = \y0y1.y0 + y1 U51 = \y0y1y2.y0 + y1 + y2 U61 = \y0.2 + y0 U71 = \y0y1y2.y0 + y1 + y2 active = \y0.3y0 and = \y0y1.y0 + y1 ok = \y0.y0 Using this interpretation, the requirements translate to: [[active(U12(_x0, _x1))]] = 3x0 + 3x1 >= x1 + 3x0 = [[U12(active(_x0), _x1)]] [[active(U21(_x0, _x1))]] = 3x0 + 3x1 >= x1 + 3x0 = [[U21(active(_x0), _x1)]] [[active(U32(_x0, _x1))]] = 3x0 + 3x1 >= x1 + 3x0 = [[U32(active(_x0), _x1)]] [[active(U41(_x0, _x1))]] = 3x0 + 3x1 >= x1 + 3x0 = [[U41(active(_x0), _x1)]] [[active(U51(_x0, _x1, _x2))]] = 3x0 + 3x1 + 3x2 >= x1 + x2 + 3x0 = [[U51(active(_x0), _x1, _x2)]] [[active(U61(_x0))]] = 6 + 3x0 > 2 + 3x0 = [[U61(active(_x0))]] [[active(U71(_x0, _x1, _x2))]] = 3x0 + 3x1 + 3x2 >= x1 + x2 + 3x0 = [[U71(active(_x0), _x1, _x2)]] [[active(and(_x0, _x1))]] = 3x0 + 3x1 >= x1 + 3x0 = [[and(active(_x0), _x1)]] [[U22(ok(_x0))]] = 3x0 >= 3x0 = [[ok(U22(_x0))]] We can thus remove the following rules: active(U61(X)) => U61(active(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]): active(U12(X, Y)) >? U12(active(X), Y) active(U21(X, Y)) >? U21(active(X), Y) active(U32(X, Y)) >? U32(active(X), Y) active(U41(X, Y)) >? U41(active(X), Y) active(U51(X, Y, Z)) >? U51(active(X), Y, Z) active(U71(X, Y, Z)) >? U71(active(X), Y, Z) active(and(X, Y)) >? and(active(X), Y) U22(ok(X)) >? ok(U22(X)) We orient these requirements with a polynomial interpretation in the natural numbers. The following interpretation satisfies the requirements: U12 = \y0y1.y0 + y1 U21 = \y0y1.y0 + y1 U22 = \y0.3y0 U32 = \y0y1.y0 + y1 U41 = \y0y1.y0 + y1 U51 = \y0y1y2.y0 + y1 + y2 U71 = \y0y1y2.y0 + y1 + y2 active = \y0.3y0 and = \y0y1.y0 + y1 ok = \y0.2 + y0 Using this interpretation, the requirements translate to: [[active(U12(_x0, _x1))]] = 3x0 + 3x1 >= x1 + 3x0 = [[U12(active(_x0), _x1)]] [[active(U21(_x0, _x1))]] = 3x0 + 3x1 >= x1 + 3x0 = [[U21(active(_x0), _x1)]] [[active(U32(_x0, _x1))]] = 3x0 + 3x1 >= x1 + 3x0 = [[U32(active(_x0), _x1)]] [[active(U41(_x0, _x1))]] = 3x0 + 3x1 >= x1 + 3x0 = [[U41(active(_x0), _x1)]] [[active(U51(_x0, _x1, _x2))]] = 3x0 + 3x1 + 3x2 >= x1 + x2 + 3x0 = [[U51(active(_x0), _x1, _x2)]] [[active(U71(_x0, _x1, _x2))]] = 3x0 + 3x1 + 3x2 >= x1 + x2 + 3x0 = [[U71(active(_x0), _x1, _x2)]] [[active(and(_x0, _x1))]] = 3x0 + 3x1 >= x1 + 3x0 = [[and(active(_x0), _x1)]] [[U22(ok(_x0))]] = 6 + 3x0 > 2 + 3x0 = [[ok(U22(_x0))]] We can thus remove the following rules: U22(ok(X)) => ok(U22(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]): active(U12(X, Y)) >? U12(active(X), Y) active(U21(X, Y)) >? U21(active(X), Y) active(U32(X, Y)) >? U32(active(X), Y) active(U41(X, Y)) >? U41(active(X), Y) active(U51(X, Y, Z)) >? U51(active(X), Y, Z) active(U71(X, Y, Z)) >? U71(active(X), Y, Z) active(and(X, Y)) >? and(active(X), Y) We orient these requirements with a polynomial interpretation in the natural numbers. The following interpretation satisfies the requirements: U12 = \y0y1.2 + y0 + y1 U21 = \y0y1.y0 + y1 U32 = \y0y1.y0 + y1 U41 = \y0y1.y0 + y1 U51 = \y0y1y2.y0 + y1 + y2 U71 = \y0y1y2.y0 + y1 + y2 active = \y0.3y0 and = \y0y1.y0 + y1 Using this interpretation, the requirements translate to: [[active(U12(_x0, _x1))]] = 6 + 3x0 + 3x1 > 2 + x1 + 3x0 = [[U12(active(_x0), _x1)]] [[active(U21(_x0, _x1))]] = 3x0 + 3x1 >= x1 + 3x0 = [[U21(active(_x0), _x1)]] [[active(U32(_x0, _x1))]] = 3x0 + 3x1 >= x1 + 3x0 = [[U32(active(_x0), _x1)]] [[active(U41(_x0, _x1))]] = 3x0 + 3x1 >= x1 + 3x0 = [[U41(active(_x0), _x1)]] [[active(U51(_x0, _x1, _x2))]] = 3x0 + 3x1 + 3x2 >= x1 + x2 + 3x0 = [[U51(active(_x0), _x1, _x2)]] [[active(U71(_x0, _x1, _x2))]] = 3x0 + 3x1 + 3x2 >= x1 + x2 + 3x0 = [[U71(active(_x0), _x1, _x2)]] [[active(and(_x0, _x1))]] = 3x0 + 3x1 >= x1 + 3x0 = [[and(active(_x0), _x1)]] We can thus remove the following rules: active(U12(X, Y)) => U12(active(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]): active(U21(X, Y)) >? U21(active(X), Y) active(U32(X, Y)) >? U32(active(X), Y) active(U41(X, Y)) >? U41(active(X), Y) active(U51(X, Y, Z)) >? U51(active(X), Y, Z) active(U71(X, Y, Z)) >? U71(active(X), Y, Z) active(and(X, Y)) >? and(active(X), Y) We orient these requirements with a polynomial interpretation in the natural numbers. The following interpretation satisfies the requirements: U21 = \y0y1.2 + y0 + y1 U32 = \y0y1.y0 + y1 U41 = \y0y1.y0 + y1 U51 = \y0y1y2.y0 + y1 + y2 U71 = \y0y1y2.y0 + y1 + y2 active = \y0.3y0 and = \y0y1.y0 + y1 Using this interpretation, the requirements translate to: [[active(U21(_x0, _x1))]] = 6 + 3x0 + 3x1 > 2 + x1 + 3x0 = [[U21(active(_x0), _x1)]] [[active(U32(_x0, _x1))]] = 3x0 + 3x1 >= x1 + 3x0 = [[U32(active(_x0), _x1)]] [[active(U41(_x0, _x1))]] = 3x0 + 3x1 >= x1 + 3x0 = [[U41(active(_x0), _x1)]] [[active(U51(_x0, _x1, _x2))]] = 3x0 + 3x1 + 3x2 >= x1 + x2 + 3x0 = [[U51(active(_x0), _x1, _x2)]] [[active(U71(_x0, _x1, _x2))]] = 3x0 + 3x1 + 3x2 >= x1 + x2 + 3x0 = [[U71(active(_x0), _x1, _x2)]] [[active(and(_x0, _x1))]] = 3x0 + 3x1 >= x1 + 3x0 = [[and(active(_x0), _x1)]] We can thus remove the following rules: active(U21(X, Y)) => U21(active(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]): active(U32(X, Y)) >? U32(active(X), Y) active(U41(X, Y)) >? U41(active(X), Y) active(U51(X, Y, Z)) >? U51(active(X), Y, Z) active(U71(X, Y, Z)) >? U71(active(X), Y, Z) active(and(X, Y)) >? and(active(X), Y) We orient these requirements with a polynomial interpretation in the natural numbers. The following interpretation satisfies the requirements: U32 = \y0y1.2 + y0 + y1 U41 = \y0y1.y0 + y1 U51 = \y0y1y2.y0 + y1 + y2 U71 = \y0y1y2.y0 + y1 + y2 active = \y0.3y0 and = \y0y1.y0 + y1 Using this interpretation, the requirements translate to: [[active(U32(_x0, _x1))]] = 6 + 3x0 + 3x1 > 2 + x1 + 3x0 = [[U32(active(_x0), _x1)]] [[active(U41(_x0, _x1))]] = 3x0 + 3x1 >= x1 + 3x0 = [[U41(active(_x0), _x1)]] [[active(U51(_x0, _x1, _x2))]] = 3x0 + 3x1 + 3x2 >= x1 + x2 + 3x0 = [[U51(active(_x0), _x1, _x2)]] [[active(U71(_x0, _x1, _x2))]] = 3x0 + 3x1 + 3x2 >= x1 + x2 + 3x0 = [[U71(active(_x0), _x1, _x2)]] [[active(and(_x0, _x1))]] = 3x0 + 3x1 >= x1 + 3x0 = [[and(active(_x0), _x1)]] We can thus remove the following rules: active(U32(X, Y)) => U32(active(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]): active(U41(X, Y)) >? U41(active(X), Y) active(U51(X, Y, Z)) >? U51(active(X), Y, Z) active(U71(X, Y, Z)) >? U71(active(X), Y, Z) active(and(X, Y)) >? and(active(X), Y) We orient these requirements with a polynomial interpretation in the natural numbers. The following interpretation satisfies the requirements: U41 = \y0y1.2 + y0 + y1 U51 = \y0y1y2.y0 + y1 + y2 U71 = \y0y1y2.y0 + y1 + y2 active = \y0.3y0 and = \y0y1.y0 + y1 Using this interpretation, the requirements translate to: [[active(U41(_x0, _x1))]] = 6 + 3x0 + 3x1 > 2 + x1 + 3x0 = [[U41(active(_x0), _x1)]] [[active(U51(_x0, _x1, _x2))]] = 3x0 + 3x1 + 3x2 >= x1 + x2 + 3x0 = [[U51(active(_x0), _x1, _x2)]] [[active(U71(_x0, _x1, _x2))]] = 3x0 + 3x1 + 3x2 >= x1 + x2 + 3x0 = [[U71(active(_x0), _x1, _x2)]] [[active(and(_x0, _x1))]] = 3x0 + 3x1 >= x1 + 3x0 = [[and(active(_x0), _x1)]] We can thus remove the following rules: active(U41(X, Y)) => U41(active(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]): active(U51(X, Y, Z)) >? U51(active(X), Y, Z) active(U71(X, Y, Z)) >? U71(active(X), Y, Z) active(and(X, Y)) >? and(active(X), Y) We orient these requirements with a polynomial interpretation in the natural numbers. The following interpretation satisfies the requirements: U51 = \y0y1y2.2 + y0 + y1 + y2 U71 = \y0y1y2.y0 + y1 + y2 active = \y0.3y0 and = \y0y1.y0 + y1 Using this interpretation, the requirements translate to: [[active(U51(_x0, _x1, _x2))]] = 6 + 3x0 + 3x1 + 3x2 > 2 + x1 + x2 + 3x0 = [[U51(active(_x0), _x1, _x2)]] [[active(U71(_x0, _x1, _x2))]] = 3x0 + 3x1 + 3x2 >= x1 + x2 + 3x0 = [[U71(active(_x0), _x1, _x2)]] [[active(and(_x0, _x1))]] = 3x0 + 3x1 >= x1 + 3x0 = [[and(active(_x0), _x1)]] We can thus remove the following rules: active(U51(X, Y, Z)) => U51(active(X), Y, Z) We use rule removal, following [Kop12, Theorem 2.23]. This gives the following requirements (possibly using Theorems 2.25 and 2.26 in [Kop12]): active(U71(X, Y, Z)) >? U71(active(X), Y, Z) active(and(X, Y)) >? and(active(X), Y) We orient these requirements with a polynomial interpretation in the natural numbers. The following interpretation satisfies the requirements: U71 = \y0y1y2.2 + y0 + y1 + y2 active = \y0.3y0 and = \y0y1.y0 + y1 Using this interpretation, the requirements translate to: [[active(U71(_x0, _x1, _x2))]] = 6 + 3x0 + 3x1 + 3x2 > 2 + x1 + x2 + 3x0 = [[U71(active(_x0), _x1, _x2)]] [[active(and(_x0, _x1))]] = 3x0 + 3x1 >= x1 + 3x0 = [[and(active(_x0), _x1)]] We can thus remove the following rules: active(U71(X, Y, Z)) => U71(active(X), Y, Z) We use rule removal, following [Kop12, Theorem 2.23]. This gives the following requirements (possibly using Theorems 2.25 and 2.26 in [Kop12]): active(and(X, Y)) >? and(active(X), Y) We orient these requirements with a polynomial interpretation in the natural numbers. The following interpretation satisfies the requirements: active = \y0.3y0 and = \y0y1.1 + y0 + y1 Using this interpretation, the requirements translate to: [[active(and(_x0, _x1))]] = 3 + 3x0 + 3x1 > 1 + x1 + 3x0 = [[and(active(_x0), _x1)]] We can thus remove the following rules: active(and(X, Y)) => and(active(X), Y) 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.