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