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