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