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