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