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