/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. !6220!6220 : [o * o] --> o U11 : [o * o] --> o U12 : [o * o] --> o U13 : [o] --> o U21 : [o * o * o] --> o U22 : [o * o * o] --> o U23 : [o * o * o] --> o U24 : [o * o * o] --> o U25 : [o * o] --> o U26 : [o] --> o U31 : [o * o] --> o U32 : [o * o] --> o U33 : [o] --> o U41 : [o * o * o] --> o U42 : [o * o * o] --> o U43 : [o * o * o] --> o U44 : [o * o * o] --> o U45 : [o * o] --> o U46 : [o] --> o U51 : [o * o * o] --> o U52 : [o * o * o] --> o U53 : [o * o * o] --> o U54 : [o * o * o] --> o U55 : [o * o] --> o U56 : [o] --> o U61 : [o * o] --> o U62 : [o * o] --> o U63 : [o] --> o U71 : [o * o * o] --> o U72 : [o * o] --> o U73 : [o * o] --> o U74 : [o] --> o U81 : [o * o] --> o U82 : [o * o] --> o U83 : [o] --> o U91 : [o * o] --> o U92 : [o] --> o a : [] --> o activate : [o] --> o e : [] --> o i : [] --> o isList : [o] --> o isNeList : [o] --> o isNePal : [o] --> o isPal : [o] --> o isPalListKind : [o] --> o isQid : [o] --> o n!6220!6220!6220!6220 : [o * o] --> o n!6220!6220a : [] --> o n!6220!6220e : [] --> o n!6220!6220i : [] --> o n!6220!6220nil : [] --> o n!6220!6220o : [] --> o n!6220!6220u : [] --> o nil : [] --> o o : [] --> o tt : [] --> o u : [] --> o !6220!6220(!6220!6220(X, Y), Z) => !6220!6220(X, !6220!6220(Y, Z)) !6220!6220(X, nil) => X !6220!6220(nil, X) => X U11(tt, X) => U12(isPalListKind(activate(X)), activate(X)) U12(tt, X) => U13(isNeList(activate(X))) U13(tt) => tt U21(tt, X, Y) => U22(isPalListKind(activate(X)), activate(X), activate(Y)) U22(tt, X, Y) => U23(isPalListKind(activate(Y)), activate(X), activate(Y)) U23(tt, X, Y) => U24(isPalListKind(activate(Y)), activate(X), activate(Y)) U24(tt, X, Y) => U25(isList(activate(X)), activate(Y)) U25(tt, X) => U26(isList(activate(X))) U26(tt) => tt U31(tt, X) => U32(isPalListKind(activate(X)), activate(X)) U32(tt, X) => U33(isQid(activate(X))) U33(tt) => tt U41(tt, X, Y) => U42(isPalListKind(activate(X)), activate(X), activate(Y)) U42(tt, X, Y) => U43(isPalListKind(activate(Y)), activate(X), activate(Y)) U43(tt, X, Y) => U44(isPalListKind(activate(Y)), activate(X), activate(Y)) U44(tt, X, Y) => U45(isList(activate(X)), activate(Y)) U45(tt, X) => U46(isNeList(activate(X))) U46(tt) => tt U51(tt, X, Y) => U52(isPalListKind(activate(X)), activate(X), activate(Y)) U52(tt, X, Y) => U53(isPalListKind(activate(Y)), activate(X), activate(Y)) U53(tt, X, Y) => U54(isPalListKind(activate(Y)), activate(X), activate(Y)) U54(tt, X, Y) => U55(isNeList(activate(X)), activate(Y)) U55(tt, X) => U56(isList(activate(X))) U56(tt) => tt U61(tt, X) => U62(isPalListKind(activate(X)), activate(X)) U62(tt, X) => U63(isQid(activate(X))) U63(tt) => tt U71(tt, X, Y) => U72(isPalListKind(activate(X)), activate(Y)) U72(tt, X) => U73(isPal(activate(X)), activate(X)) U73(tt, X) => U74(isPalListKind(activate(X))) U74(tt) => tt U81(tt, X) => U82(isPalListKind(activate(X)), activate(X)) U82(tt, X) => U83(isNePal(activate(X))) U83(tt) => tt U91(tt, X) => U92(isPalListKind(activate(X))) U92(tt) => tt isList(X) => U11(isPalListKind(activate(X)), activate(X)) isList(n!6220!6220nil) => tt isList(n!6220!6220!6220!6220(X, Y)) => U21(isPalListKind(activate(X)), activate(X), activate(Y)) isNeList(X) => U31(isPalListKind(activate(X)), activate(X)) isNeList(n!6220!6220!6220!6220(X, Y)) => U41(isPalListKind(activate(X)), activate(X), activate(Y)) isNeList(n!6220!6220!6220!6220(X, Y)) => U51(isPalListKind(activate(X)), activate(X), activate(Y)) isNePal(X) => U61(isPalListKind(activate(X)), activate(X)) isNePal(n!6220!6220!6220!6220(X, n!6220!6220!6220!6220(Y, X))) => U71(isQid(activate(X)), activate(X), activate(Y)) isPal(X) => U81(isPalListKind(activate(X)), activate(X)) isPal(n!6220!6220nil) => tt isPalListKind(n!6220!6220a) => tt isPalListKind(n!6220!6220e) => tt isPalListKind(n!6220!6220i) => tt isPalListKind(n!6220!6220nil) => tt isPalListKind(n!6220!6220o) => tt isPalListKind(n!6220!6220u) => tt isPalListKind(n!6220!6220!6220!6220(X, Y)) => U91(isPalListKind(activate(X)), activate(Y)) isQid(n!6220!6220a) => tt isQid(n!6220!6220e) => tt isQid(n!6220!6220i) => tt isQid(n!6220!6220o) => tt isQid(n!6220!6220u) => tt nil => n!6220!6220nil !6220!6220(X, Y) => n!6220!6220!6220!6220(X, Y) a => n!6220!6220a e => n!6220!6220e i => n!6220!6220i o => n!6220!6220o u => n!6220!6220u activate(n!6220!6220nil) => nil activate(n!6220!6220!6220!6220(X, Y)) => !6220!6220(activate(X), activate(Y)) activate(n!6220!6220a) => a activate(n!6220!6220e) => e activate(n!6220!6220i) => i activate(n!6220!6220o) => o activate(n!6220!6220u) => u activate(X) => X We use rule removal, following [Kop12, Theorem 2.23]. This gives the following requirements (possibly using Theorems 2.25 and 2.26 in [Kop12]): !6220!6220(!6220!6220(X, Y), Z) >? !6220!6220(X, !6220!6220(Y, Z)) !6220!6220(X, nil) >? X !6220!6220(nil, X) >? X U11(tt, X) >? U12(isPalListKind(activate(X)), activate(X)) U12(tt, X) >? U13(isNeList(activate(X))) U13(tt) >? tt U21(tt, X, Y) >? U22(isPalListKind(activate(X)), activate(X), activate(Y)) U22(tt, X, Y) >? U23(isPalListKind(activate(Y)), activate(X), activate(Y)) U23(tt, X, Y) >? U24(isPalListKind(activate(Y)), activate(X), activate(Y)) U24(tt, X, Y) >? U25(isList(activate(X)), activate(Y)) U25(tt, X) >? U26(isList(activate(X))) U26(tt) >? tt U31(tt, X) >? U32(isPalListKind(activate(X)), activate(X)) U32(tt, X) >? U33(isQid(activate(X))) U33(tt) >? tt U41(tt, X, Y) >? U42(isPalListKind(activate(X)), activate(X), activate(Y)) U42(tt, X, Y) >? U43(isPalListKind(activate(Y)), activate(X), activate(Y)) U43(tt, X, Y) >? U44(isPalListKind(activate(Y)), activate(X), activate(Y)) U44(tt, X, Y) >? U45(isList(activate(X)), activate(Y)) U45(tt, X) >? U46(isNeList(activate(X))) U46(tt) >? tt U51(tt, X, Y) >? U52(isPalListKind(activate(X)), activate(X), activate(Y)) U52(tt, X, Y) >? U53(isPalListKind(activate(Y)), activate(X), activate(Y)) U53(tt, X, Y) >? U54(isPalListKind(activate(Y)), activate(X), activate(Y)) U54(tt, X, Y) >? U55(isNeList(activate(X)), activate(Y)) U55(tt, X) >? U56(isList(activate(X))) U56(tt) >? tt U61(tt, X) >? U62(isPalListKind(activate(X)), activate(X)) U62(tt, X) >? U63(isQid(activate(X))) U63(tt) >? tt U71(tt, X, Y) >? U72(isPalListKind(activate(X)), activate(Y)) U72(tt, X) >? U73(isPal(activate(X)), activate(X)) U73(tt, X) >? U74(isPalListKind(activate(X))) U74(tt) >? tt U81(tt, X) >? U82(isPalListKind(activate(X)), activate(X)) U82(tt, X) >? U83(isNePal(activate(X))) U83(tt) >? tt U91(tt, X) >? U92(isPalListKind(activate(X))) U92(tt) >? tt isList(X) >? U11(isPalListKind(activate(X)), activate(X)) isList(n!6220!6220nil) >? tt isList(n!6220!6220!6220!6220(X, Y)) >? U21(isPalListKind(activate(X)), activate(X), activate(Y)) isNeList(X) >? U31(isPalListKind(activate(X)), activate(X)) isNeList(n!6220!6220!6220!6220(X, Y)) >? U41(isPalListKind(activate(X)), activate(X), activate(Y)) isNeList(n!6220!6220!6220!6220(X, Y)) >? U51(isPalListKind(activate(X)), activate(X), activate(Y)) isNePal(X) >? U61(isPalListKind(activate(X)), activate(X)) isNePal(n!6220!6220!6220!6220(X, n!6220!6220!6220!6220(Y, X))) >? U71(isQid(activate(X)), activate(X), activate(Y)) isPal(X) >? U81(isPalListKind(activate(X)), activate(X)) isPal(n!6220!6220nil) >? tt isPalListKind(n!6220!6220a) >? tt isPalListKind(n!6220!6220e) >? tt isPalListKind(n!6220!6220i) >? tt isPalListKind(n!6220!6220nil) >? tt isPalListKind(n!6220!6220o) >? tt isPalListKind(n!6220!6220u) >? tt isPalListKind(n!6220!6220!6220!6220(X, Y)) >? U91(isPalListKind(activate(X)), activate(Y)) isQid(n!6220!6220a) >? tt isQid(n!6220!6220e) >? tt isQid(n!6220!6220i) >? tt isQid(n!6220!6220o) >? tt isQid(n!6220!6220u) >? tt nil >? n!6220!6220nil !6220!6220(X, Y) >? n!6220!6220!6220!6220(X, Y) a >? n!6220!6220a e >? n!6220!6220e i >? n!6220!6220i o >? n!6220!6220o u >? n!6220!6220u activate(n!6220!6220nil) >? nil activate(n!6220!6220!6220!6220(X, Y)) >? !6220!6220(activate(X), activate(Y)) activate(n!6220!6220a) >? a activate(n!6220!6220e) >? e activate(n!6220!6220i) >? i activate(n!6220!6220o) >? o activate(n!6220!6220u) >? u activate(X) >? X about to try horpo We use a recursive path ordering as defined in [Kop12, Chapter 5]. Argument functions: [[U13(x_1)]] = x_1 [[U26(x_1)]] = x_1 [[U33(x_1)]] = x_1 [[U46(x_1)]] = x_1 [[U56(x_1)]] = x_1 [[U71(x_1, x_2, x_3)]] = U71(x_2, x_3, x_1) [[U74(x_1)]] = x_1 [[U83(x_1)]] = x_1 [[U92(x_1)]] = x_1 [[a]] = _|_ [[activate(x_1)]] = x_1 [[e]] = _|_ [[i]] = _|_ [[isQid(x_1)]] = x_1 [[n!6220!6220a]] = _|_ [[n!6220!6220e]] = _|_ [[n!6220!6220i]] = _|_ [[n!6220!6220u]] = _|_ [[tt]] = _|_ [[u]] = _|_ We choose Lex = {!6220!6220, U71, n!6220!6220!6220!6220} and Mul = {U11, U12, U21, U22, U23, U24, U25, U31, U32, U41, U42, U43, U44, U45, U51, U52, U53, U54, U55, U61, U62, U63, U72, U73, U81, U82, U91, isList, isNeList, isNePal, isPal, isPalListKind, n!6220!6220nil, n!6220!6220o, nil, o}, and the following precedence: n!6220!6220nil = nil > !6220!6220 = U71 = n!6220!6220!6220!6220 > U51 > U72 > isPal > U52 > U81 > U82 > isNePal > U61 > U62 > U21 > U63 > U41 > U42 > U43 > U44 > U22 > U23 > U53 > U24 > U25 > U54 > U55 > U45 > isList > U73 > U11 > U12 > U91 > isNeList > U31 > isPalListKind > U32 > n!6220!6220o = o Taking the argument function into account, and fixing the greater / greater equal choices, the constraints can be denoted as follows: !6220!6220(!6220!6220(X, Y), Z) > !6220!6220(X, !6220!6220(Y, Z)) !6220!6220(X, nil) >= X !6220!6220(nil, X) >= X U11(_|_, X) >= U12(isPalListKind(X), X) U12(_|_, X) >= isNeList(X) _|_ >= _|_ U21(_|_, X, Y) >= U22(isPalListKind(X), X, Y) U22(_|_, X, Y) > U23(isPalListKind(Y), X, Y) U23(_|_, X, Y) > U24(isPalListKind(Y), X, Y) U24(_|_, X, Y) >= U25(isList(X), Y) U25(_|_, X) > isList(X) _|_ >= _|_ U31(_|_, X) > U32(isPalListKind(X), X) U32(_|_, X) > X _|_ >= _|_ U41(_|_, X, Y) >= U42(isPalListKind(X), X, Y) U42(_|_, X, Y) > U43(isPalListKind(Y), X, Y) U43(_|_, X, Y) > U44(isPalListKind(Y), X, Y) U44(_|_, X, Y) >= U45(isList(X), Y) U45(_|_, X) > isNeList(X) _|_ >= _|_ U51(_|_, X, Y) >= U52(isPalListKind(X), X, Y) U52(_|_, X, Y) >= U53(isPalListKind(Y), X, Y) U53(_|_, X, Y) > U54(isPalListKind(Y), X, Y) U54(_|_, X, Y) >= U55(isNeList(X), Y) U55(_|_, X) >= isList(X) _|_ >= _|_ U61(_|_, X) >= U62(isPalListKind(X), X) U62(_|_, X) >= U63(X) U63(_|_) >= _|_ U71(_|_, X, Y) > U72(isPalListKind(X), Y) U72(_|_, X) >= U73(isPal(X), X) U73(_|_, X) > isPalListKind(X) _|_ >= _|_ U81(_|_, X) > U82(isPalListKind(X), X) U82(_|_, X) >= isNePal(X) _|_ >= _|_ U91(_|_, X) >= isPalListKind(X) _|_ >= _|_ isList(X) > U11(isPalListKind(X), X) isList(n!6220!6220nil) >= _|_ isList(n!6220!6220!6220!6220(X, Y)) >= U21(isPalListKind(X), X, Y) isNeList(X) > U31(isPalListKind(X), X) isNeList(n!6220!6220!6220!6220(X, Y)) >= U41(isPalListKind(X), X, Y) isNeList(n!6220!6220!6220!6220(X, Y)) > U51(isPalListKind(X), X, Y) isNePal(X) > U61(isPalListKind(X), X) isNePal(n!6220!6220!6220!6220(X, n!6220!6220!6220!6220(Y, X))) >= U71(X, X, Y) isPal(X) >= U81(isPalListKind(X), X) isPal(n!6220!6220nil) >= _|_ isPalListKind(_|_) >= _|_ isPalListKind(_|_) >= _|_ isPalListKind(_|_) >= _|_ isPalListKind(n!6220!6220nil) >= _|_ isPalListKind(n!6220!6220o) >= _|_ isPalListKind(_|_) >= _|_ isPalListKind(n!6220!6220!6220!6220(X, Y)) > U91(isPalListKind(X), Y) _|_ >= _|_ _|_ >= _|_ _|_ >= _|_ n!6220!6220o >= _|_ _|_ >= _|_ nil >= n!6220!6220nil !6220!6220(X, Y) >= n!6220!6220!6220!6220(X, Y) _|_ >= _|_ _|_ >= _|_ _|_ >= _|_ o >= n!6220!6220o _|_ >= _|_ n!6220!6220nil >= nil n!6220!6220!6220!6220(X, Y) >= !6220!6220(X, Y) _|_ >= _|_ _|_ >= _|_ _|_ >= _|_ n!6220!6220o >= o _|_ >= _|_ X >= X With these choices, we have: 1] !6220!6220(!6220!6220(X, Y), Z) > !6220!6220(X, !6220!6220(Y, Z)) because [2], by definition 2] !6220!6220*(!6220!6220(X, Y), Z) >= !6220!6220(X, !6220!6220(Y, Z)) because [3], [6] and [8], by (Stat) 3] !6220!6220(X, Y) > X because [4], by definition 4] !6220!6220*(X, Y) >= X because [5], by (Select) 5] X >= X by (Meta) 6] !6220!6220*(!6220!6220(X, Y), Z) >= X because [7], by (Select) 7] !6220!6220(X, Y) >= X because [4], by (Star) 8] !6220!6220*(!6220!6220(X, Y), Z) >= !6220!6220(Y, Z) because [9], [12] and [14], by (Stat) 9] !6220!6220(X, Y) > Y because [10], by definition 10] !6220!6220*(X, Y) >= Y because [11], by (Select) 11] Y >= Y by (Meta) 12] !6220!6220*(!6220!6220(X, Y), Z) >= Y because [13], by (Select) 13] !6220!6220(X, Y) >= Y because [10], by (Star) 14] !6220!6220*(!6220!6220(X, Y), Z) >= Z because [15], by (Select) 15] Z >= Z by (Meta) 16] !6220!6220(X, nil) >= X because [17], by (Star) 17] !6220!6220*(X, nil) >= X because [5], by (Select) 18] !6220!6220(nil, X) >= X because [19], by (Star) 19] !6220!6220*(nil, X) >= X because [5], by (Select) 20] U11(_|_, X) >= U12(isPalListKind(X), X) because [21], by (Star) 21] U11*(_|_, X) >= U12(isPalListKind(X), X) because U11 > U12, [22] and [23], by (Copy) 22] U11*(_|_, X) >= isPalListKind(X) because U11 > isPalListKind and [23], by (Copy) 23] U11*(_|_, X) >= X because [24], by (Select) 24] X >= X by (Meta) 25] U12(_|_, X) >= isNeList(X) because [26], by (Star) 26] U12*(_|_, X) >= isNeList(X) because U12 > isNeList and [27], by (Copy) 27] U12*(_|_, X) >= X because [24], by (Select) 28] _|_ >= _|_ by (Bot) 29] U21(_|_, X, Y) >= U22(isPalListKind(X), X, Y) because [30], by (Star) 30] U21*(_|_, X, Y) >= U22(isPalListKind(X), X, Y) because U21 > U22, [31], [32] and [34], by (Copy) 31] U21*(_|_, X, Y) >= isPalListKind(X) because U21 > isPalListKind and [32], by (Copy) 32] U21*(_|_, X, Y) >= X because [33], by (Select) 33] X >= X by (Meta) 34] U21*(_|_, X, Y) >= Y because [35], by (Select) 35] Y >= Y by (Meta) 36] U22(_|_, X, Y) > U23(isPalListKind(Y), X, Y) because [37], by definition 37] U22*(_|_, X, Y) >= U23(isPalListKind(Y), X, Y) because U22 > U23, [38], [40] and [39], by (Copy) 38] U22*(_|_, X, Y) >= isPalListKind(Y) because U22 > isPalListKind and [39], by (Copy) 39] U22*(_|_, X, Y) >= Y because [35], by (Select) 40] U22*(_|_, X, Y) >= X because [33], by (Select) 41] U23(_|_, X, Y) > U24(isPalListKind(Y), X, Y) because [42], by definition 42] U23*(_|_, X, Y) >= U24(isPalListKind(Y), X, Y) because U23 > U24, [43], [45] and [44], by (Copy) 43] U23*(_|_, X, Y) >= isPalListKind(Y) because U23 > isPalListKind and [44], by (Copy) 44] U23*(_|_, X, Y) >= Y because [35], by (Select) 45] U23*(_|_, X, Y) >= X because [33], by (Select) 46] U24(_|_, X, Y) >= U25(isList(X), Y) because [47], by (Star) 47] U24*(_|_, X, Y) >= U25(isList(X), Y) because U24 > U25, [48] and [50], by (Copy) 48] U24*(_|_, X, Y) >= isList(X) because U24 > isList and [49], by (Copy) 49] U24*(_|_, X, Y) >= X because [33], by (Select) 50] U24*(_|_, X, Y) >= Y because [35], by (Select) 51] U25(_|_, X) > isList(X) because [52], by definition 52] U25*(_|_, X) >= isList(X) because U25 > isList and [53], by (Copy) 53] U25*(_|_, X) >= X because [35], by (Select) 54] _|_ >= _|_ by (Bot) 55] U31(_|_, X) > U32(isPalListKind(X), X) because [56], by definition 56] U31*(_|_, X) >= U32(isPalListKind(X), X) because U31 > U32, [57] and [58], by (Copy) 57] U31*(_|_, X) >= isPalListKind(X) because U31 > isPalListKind and [58], by (Copy) 58] U31*(_|_, X) >= X because [24], by (Select) 59] U32(_|_, X) > X because [60], by definition 60] U32*(_|_, X) >= X because [24], by (Select) 61] _|_ >= _|_ by (Bot) 62] U41(_|_, X, Y) >= U42(isPalListKind(X), X, Y) because [63], by (Star) 63] U41*(_|_, X, Y) >= U42(isPalListKind(X), X, Y) because U41 > U42, [64], [65] and [66], by (Copy) 64] U41*(_|_, X, Y) >= isPalListKind(X) because U41 > isPalListKind and [65], by (Copy) 65] U41*(_|_, X, Y) >= X because [33], by (Select) 66] U41*(_|_, X, Y) >= Y because [35], by (Select) 67] U42(_|_, X, Y) > U43(isPalListKind(Y), X, Y) because [68], by definition 68] U42*(_|_, X, Y) >= U43(isPalListKind(Y), X, Y) because U42 > U43, [69], [71] and [70], by (Copy) 69] U42*(_|_, X, Y) >= isPalListKind(Y) because U42 > isPalListKind and [70], by (Copy) 70] U42*(_|_, X, Y) >= Y because [35], by (Select) 71] U42*(_|_, X, Y) >= X because [33], by (Select) 72] U43(_|_, X, Y) > U44(isPalListKind(Y), X, Y) because [73], by definition 73] U43*(_|_, X, Y) >= U44(isPalListKind(Y), X, Y) because U43 > U44, [74], [76] and [75], by (Copy) 74] U43*(_|_, X, Y) >= isPalListKind(Y) because U43 > isPalListKind and [75], by (Copy) 75] U43*(_|_, X, Y) >= Y because [35], by (Select) 76] U43*(_|_, X, Y) >= X because [33], by (Select) 77] U44(_|_, X, Y) >= U45(isList(X), Y) because [78], by (Star) 78] U44*(_|_, X, Y) >= U45(isList(X), Y) because U44 > U45, [79] and [81], by (Copy) 79] U44*(_|_, X, Y) >= isList(X) because U44 > isList and [80], by (Copy) 80] U44*(_|_, X, Y) >= X because [33], by (Select) 81] U44*(_|_, X, Y) >= Y because [35], by (Select) 82] U45(_|_, X) > isNeList(X) because [83], by definition 83] U45*(_|_, X) >= isNeList(X) because U45 > isNeList and [84], by (Copy) 84] U45*(_|_, X) >= X because [35], by (Select) 85] _|_ >= _|_ by (Bot) 86] U51(_|_, X, Y) >= U52(isPalListKind(X), X, Y) because [87], by (Star) 87] U51*(_|_, X, Y) >= U52(isPalListKind(X), X, Y) because U51 > U52, [88], [89] and [90], by (Copy) 88] U51*(_|_, X, Y) >= isPalListKind(X) because U51 > isPalListKind and [89], by (Copy) 89] U51*(_|_, X, Y) >= X because [33], by (Select) 90] U51*(_|_, X, Y) >= Y because [35], by (Select) 91] U52(_|_, X, Y) >= U53(isPalListKind(Y), X, Y) because [92], by (Star) 92] U52*(_|_, X, Y) >= U53(isPalListKind(Y), X, Y) because U52 > U53, [93], [95] and [94], by (Copy) 93] U52*(_|_, X, Y) >= isPalListKind(Y) because U52 > isPalListKind and [94], by (Copy) 94] U52*(_|_, X, Y) >= Y because [35], by (Select) 95] U52*(_|_, X, Y) >= X because [33], by (Select) 96] U53(_|_, X, Y) > U54(isPalListKind(Y), X, Y) because [97], by definition 97] U53*(_|_, X, Y) >= U54(isPalListKind(Y), X, Y) because U53 > U54, [98], [100] and [99], by (Copy) 98] U53*(_|_, X, Y) >= isPalListKind(Y) because U53 > isPalListKind and [99], by (Copy) 99] U53*(_|_, X, Y) >= Y because [35], by (Select) 100] U53*(_|_, X, Y) >= X because [33], by (Select) 101] U54(_|_, X, Y) >= U55(isNeList(X), Y) because [102], by (Star) 102] U54*(_|_, X, Y) >= U55(isNeList(X), Y) because U54 > U55, [103] and [105], by (Copy) 103] U54*(_|_, X, Y) >= isNeList(X) because U54 > isNeList and [104], by (Copy) 104] U54*(_|_, X, Y) >= X because [33], by (Select) 105] U54*(_|_, X, Y) >= Y because [35], by (Select) 106] U55(_|_, X) >= isList(X) because [107], by (Star) 107] U55*(_|_, X) >= isList(X) because U55 > isList and [108], by (Copy) 108] U55*(_|_, X) >= X because [35], by (Select) 109] _|_ >= _|_ by (Bot) 110] U61(_|_, X) >= U62(isPalListKind(X), X) because [111], by (Star) 111] U61*(_|_, X) >= U62(isPalListKind(X), X) because U61 > U62, [112] and [113], by (Copy) 112] U61*(_|_, X) >= isPalListKind(X) because U61 > isPalListKind and [113], by (Copy) 113] U61*(_|_, X) >= X because [24], by (Select) 114] U62(_|_, X) >= U63(X) because [115], by (Star) 115] U62*(_|_, X) >= U63(X) because U62 > U63 and [116], by (Copy) 116] U62*(_|_, X) >= X because [24], by (Select) 117] U63(_|_) >= _|_ by (Bot) 118] U71(_|_, X, Y) > U72(isPalListKind(X), Y) because [119], by definition 119] U71*(_|_, X, Y) >= U72(isPalListKind(X), Y) because U71 > U72, [120] and [123], by (Copy) 120] U71*(_|_, X, Y) >= isPalListKind(X) because U71 > isPalListKind and [121], by (Copy) 121] U71*(_|_, X, Y) >= X because [122], by (Select) 122] X >= X by (Meta) 123] U71*(_|_, X, Y) >= Y because [124], by (Select) 124] Y >= Y by (Meta) 125] U72(_|_, X) >= U73(isPal(X), X) because [126], by (Star) 126] U72*(_|_, X) >= U73(isPal(X), X) because U72 > U73, [127] and [128], by (Copy) 127] U72*(_|_, X) >= isPal(X) because U72 > isPal and [128], by (Copy) 128] U72*(_|_, X) >= X because [124], by (Select) 129] U73(_|_, X) > isPalListKind(X) because [130], by definition 130] U73*(_|_, X) >= isPalListKind(X) because U73 > isPalListKind and [131], by (Copy) 131] U73*(_|_, X) >= X because [124], by (Select) 132] _|_ >= _|_ by (Bot) 133] U81(_|_, X) > U82(isPalListKind(X), X) because [134], by definition 134] U81*(_|_, X) >= U82(isPalListKind(X), X) because U81 > U82, [135] and [136], by (Copy) 135] U81*(_|_, X) >= isPalListKind(X) because U81 > isPalListKind and [136], by (Copy) 136] U81*(_|_, X) >= X because [24], by (Select) 137] U82(_|_, X) >= isNePal(X) because [138], by (Star) 138] U82*(_|_, X) >= isNePal(X) because U82 > isNePal and [139], by (Copy) 139] U82*(_|_, X) >= X because [24], by (Select) 140] _|_ >= _|_ by (Bot) 141] U91(_|_, X) >= isPalListKind(X) because [142], by (Star) 142] U91*(_|_, X) >= isPalListKind(X) because U91 > isPalListKind and [143], by (Copy) 143] U91*(_|_, X) >= X because [35], by (Select) 144] _|_ >= _|_ by (Bot) 145] isList(X) > U11(isPalListKind(X), X) because [146], by definition 146] isList*(X) >= U11(isPalListKind(X), X) because isList > U11, [147] and [148], by (Copy) 147] isList*(X) >= isPalListKind(X) because isList > isPalListKind and [148], by (Copy) 148] isList*(X) >= X because [24], by (Select) 149] isList(n!6220!6220nil) >= _|_ by (Bot) 150] isList(n!6220!6220!6220!6220(X, Y)) >= U21(isPalListKind(X), X, Y) because [151], by (Star) 151] isList*(n!6220!6220!6220!6220(X, Y)) >= U21(isPalListKind(X), X, Y) because [152], by (Select) 152] n!6220!6220!6220!6220(X, Y) >= U21(isPalListKind(X), X, Y) because [153], by (Star) 153] n!6220!6220!6220!6220*(X, Y) >= U21(isPalListKind(X), X, Y) because n!6220!6220!6220!6220 > U21, [154], [155] and [156], by (Copy) 154] n!6220!6220!6220!6220*(X, Y) >= isPalListKind(X) because n!6220!6220!6220!6220 > isPalListKind and [155], by (Copy) 155] n!6220!6220!6220!6220*(X, Y) >= X because [33], by (Select) 156] n!6220!6220!6220!6220*(X, Y) >= Y because [35], by (Select) 157] isNeList(X) > U31(isPalListKind(X), X) because [158], by definition 158] isNeList*(X) >= U31(isPalListKind(X), X) because isNeList > U31, [159] and [160], by (Copy) 159] isNeList*(X) >= isPalListKind(X) because isNeList > isPalListKind and [160], by (Copy) 160] isNeList*(X) >= X because [24], by (Select) 161] isNeList(n!6220!6220!6220!6220(X, Y)) >= U41(isPalListKind(X), X, Y) because [162], by (Star) 162] isNeList*(n!6220!6220!6220!6220(X, Y)) >= U41(isPalListKind(X), X, Y) because [163], by (Select) 163] n!6220!6220!6220!6220(X, Y) >= U41(isPalListKind(X), X, Y) because [164], by (Star) 164] n!6220!6220!6220!6220*(X, Y) >= U41(isPalListKind(X), X, Y) because n!6220!6220!6220!6220 > U41, [154], [155] and [156], by (Copy) 165] isNeList(n!6220!6220!6220!6220(X, Y)) > U51(isPalListKind(X), X, Y) because [166], by definition 166] isNeList*(n!6220!6220!6220!6220(X, Y)) >= U51(isPalListKind(X), X, Y) because [167], by (Select) 167] n!6220!6220!6220!6220(X, Y) >= U51(isPalListKind(X), X, Y) because [168], by (Star) 168] n!6220!6220!6220!6220*(X, Y) >= U51(isPalListKind(X), X, Y) because n!6220!6220!6220!6220 > U51, [154], [155] and [156], by (Copy) 169] isNePal(X) > U61(isPalListKind(X), X) because [170], by definition 170] isNePal*(X) >= U61(isPalListKind(X), X) because isNePal > U61, [171] and [172], by (Copy) 171] isNePal*(X) >= isPalListKind(X) because isNePal > isPalListKind and [172], by (Copy) 172] isNePal*(X) >= X because [24], by (Select) 173] isNePal(n!6220!6220!6220!6220(X, n!6220!6220!6220!6220(Y, X))) >= U71(X, X, Y) because [174], by (Star) 174] isNePal*(n!6220!6220!6220!6220(X, n!6220!6220!6220!6220(Y, X))) >= U71(X, X, Y) because [175], by (Select) 175] n!6220!6220!6220!6220(X, n!6220!6220!6220!6220(Y, X)) >= U71(X, X, Y) because [176], by (Star) 176] n!6220!6220!6220!6220*(X, n!6220!6220!6220!6220(Y, X)) >= U71(X, X, Y) because n!6220!6220!6220!6220 = U71, [177], [178], [180], [180] and [181], by (Stat) 177] X >= X by (Meta) 178] n!6220!6220!6220!6220(Y, X) > Y because [179], by definition 179] n!6220!6220!6220!6220*(Y, X) >= Y because [124], by (Select) 180] n!6220!6220!6220!6220*(X, n!6220!6220!6220!6220(Y, X)) >= X because [177], by (Select) 181] n!6220!6220!6220!6220*(X, n!6220!6220!6220!6220(Y, X)) >= Y because [182], by (Select) 182] n!6220!6220!6220!6220(Y, X) >= Y because [179], by (Star) 183] isPal(X) >= U81(isPalListKind(X), X) because [184], by (Star) 184] isPal*(X) >= U81(isPalListKind(X), X) because isPal > U81, [185] and [186], by (Copy) 185] isPal*(X) >= isPalListKind(X) because isPal > isPalListKind and [186], by (Copy) 186] isPal*(X) >= X because [24], by (Select) 187] isPal(n!6220!6220nil) >= _|_ by (Bot) 188] isPalListKind(_|_) >= _|_ by (Bot) 189] isPalListKind(_|_) >= _|_ by (Bot) 190] isPalListKind(_|_) >= _|_ by (Bot) 191] isPalListKind(n!6220!6220nil) >= _|_ by (Bot) 192] isPalListKind(n!6220!6220o) >= _|_ by (Bot) 193] isPalListKind(_|_) >= _|_ by (Bot) 194] isPalListKind(n!6220!6220!6220!6220(X, Y)) > U91(isPalListKind(X), Y) because [195], by definition 195] isPalListKind*(n!6220!6220!6220!6220(X, Y)) >= U91(isPalListKind(X), Y) because [196], by (Select) 196] n!6220!6220!6220!6220(X, Y) >= U91(isPalListKind(X), Y) because [197], by (Star) 197] n!6220!6220!6220!6220*(X, Y) >= U91(isPalListKind(X), Y) because n!6220!6220!6220!6220 > U91, [154] and [156], by (Copy) 198] _|_ >= _|_ by (Bot) 199] _|_ >= _|_ by (Bot) 200] _|_ >= _|_ by (Bot) 201] n!6220!6220o >= _|_ by (Bot) 202] _|_ >= _|_ by (Bot) 203] nil >= n!6220!6220nil because nil = n!6220!6220nil, by (Fun) 204] !6220!6220(X, Y) >= n!6220!6220!6220!6220(X, Y) because !6220!6220 = n!6220!6220!6220!6220, [205] and [206], by (Fun) 205] X >= X by (Meta) 206] Y >= Y by (Meta) 207] _|_ >= _|_ by (Bot) 208] _|_ >= _|_ by (Bot) 209] _|_ >= _|_ by (Bot) 210] o >= n!6220!6220o because o = n!6220!6220o, by (Fun) 211] _|_ >= _|_ by (Bot) 212] n!6220!6220nil >= nil because n!6220!6220nil = nil, by (Fun) 213] n!6220!6220!6220!6220(X, Y) >= !6220!6220(X, Y) because n!6220!6220!6220!6220 = !6220!6220, [214] and [215], by (Fun) 214] X >= X by (Meta) 215] Y >= Y by (Meta) 216] _|_ >= _|_ by (Bot) 217] _|_ >= _|_ by (Bot) 218] _|_ >= _|_ by (Bot) 219] n!6220!6220o >= o because n!6220!6220o = o, by (Fun) 220] _|_ >= _|_ by (Bot) 221] X >= X by (Meta) We can thus remove the following rules: !6220!6220(!6220!6220(X, Y), Z) => !6220!6220(X, !6220!6220(Y, Z)) U22(tt, X, Y) => U23(isPalListKind(activate(Y)), activate(X), activate(Y)) U23(tt, X, Y) => U24(isPalListKind(activate(Y)), activate(X), activate(Y)) U25(tt, X) => U26(isList(activate(X))) U31(tt, X) => U32(isPalListKind(activate(X)), activate(X)) U32(tt, X) => U33(isQid(activate(X))) U42(tt, X, Y) => U43(isPalListKind(activate(Y)), activate(X), activate(Y)) U43(tt, X, Y) => U44(isPalListKind(activate(Y)), activate(X), activate(Y)) U45(tt, X) => U46(isNeList(activate(X))) U53(tt, X, Y) => U54(isPalListKind(activate(Y)), activate(X), activate(Y)) U71(tt, X, Y) => U72(isPalListKind(activate(X)), activate(Y)) U73(tt, X) => U74(isPalListKind(activate(X))) U81(tt, X) => U82(isPalListKind(activate(X)), activate(X)) isList(X) => U11(isPalListKind(activate(X)), activate(X)) isNeList(X) => U31(isPalListKind(activate(X)), activate(X)) isNeList(n!6220!6220!6220!6220(X, Y)) => U51(isPalListKind(activate(X)), activate(X), activate(Y)) isNePal(X) => U61(isPalListKind(activate(X)), activate(X)) isPalListKind(n!6220!6220!6220!6220(X, Y)) => U91(isPalListKind(activate(X)), activate(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]): !6220!6220(X, nil) >? X !6220!6220(nil, X) >? X U11(tt, X) >? U12(isPalListKind(activate(X)), activate(X)) U12(tt, X) >? U13(isNeList(activate(X))) U13(tt) >? tt U21(tt, X, Y) >? U22(isPalListKind(activate(X)), activate(X), activate(Y)) U24(tt, X, Y) >? U25(isList(activate(X)), activate(Y)) U26(tt) >? tt U33(tt) >? tt U41(tt, X, Y) >? U42(isPalListKind(activate(X)), activate(X), activate(Y)) U44(tt, X, Y) >? U45(isList(activate(X)), activate(Y)) U46(tt) >? tt U51(tt, X, Y) >? U52(isPalListKind(activate(X)), activate(X), activate(Y)) U52(tt, X, Y) >? U53(isPalListKind(activate(Y)), activate(X), activate(Y)) U54(tt, X, Y) >? U55(isNeList(activate(X)), activate(Y)) U55(tt, X) >? U56(isList(activate(X))) U56(tt) >? tt U61(tt, X) >? U62(isPalListKind(activate(X)), activate(X)) U62(tt, X) >? U63(isQid(activate(X))) U63(tt) >? tt U72(tt, X) >? U73(isPal(activate(X)), activate(X)) U74(tt) >? tt U82(tt, X) >? U83(isNePal(activate(X))) U83(tt) >? tt U91(tt, X) >? U92(isPalListKind(activate(X))) U92(tt) >? tt isList(n!6220!6220nil) >? tt isList(n!6220!6220!6220!6220(X, Y)) >? U21(isPalListKind(activate(X)), activate(X), activate(Y)) isNeList(n!6220!6220!6220!6220(X, Y)) >? U41(isPalListKind(activate(X)), activate(X), activate(Y)) isNePal(n!6220!6220!6220!6220(X, n!6220!6220!6220!6220(Y, X))) >? U71(isQid(activate(X)), activate(X), activate(Y)) isPal(X) >? U81(isPalListKind(activate(X)), activate(X)) isPal(n!6220!6220nil) >? tt isPalListKind(n!6220!6220a) >? tt isPalListKind(n!6220!6220e) >? tt isPalListKind(n!6220!6220i) >? tt isPalListKind(n!6220!6220nil) >? tt isPalListKind(n!6220!6220o) >? tt isPalListKind(n!6220!6220u) >? tt isQid(n!6220!6220a) >? tt isQid(n!6220!6220e) >? tt isQid(n!6220!6220i) >? tt isQid(n!6220!6220o) >? tt isQid(n!6220!6220u) >? tt nil >? n!6220!6220nil !6220!6220(X, Y) >? n!6220!6220!6220!6220(X, Y) a >? n!6220!6220a e >? n!6220!6220e i >? n!6220!6220i o >? n!6220!6220o u >? n!6220!6220u activate(n!6220!6220nil) >? nil activate(n!6220!6220!6220!6220(X, Y)) >? !6220!6220(activate(X), activate(Y)) activate(n!6220!6220a) >? a activate(n!6220!6220e) >? e activate(n!6220!6220i) >? i activate(n!6220!6220o) >? o activate(n!6220!6220u) >? u activate(X) >? X We orient these requirements with a polynomial interpretation in the natural numbers. The following interpretation satisfies the requirements: !6220!6220 = \y0y1.y1 + 2y0 U11 = \y0y1.3 + 3y0 + 3y1 U12 = \y0y1.2 + y0 + 2y1 U13 = \y0.y0 U21 = \y0y1y2.y0 + y2 + 2y1 U22 = \y0y1y2.y0 + y1 + y2 U24 = \y0y1y2.3 + 3y0 + 3y1 + 3y2 U25 = \y0y1.y0 + y1 U26 = \y0.3 + 3y0 U33 = \y0.3 + 3y0 U41 = \y0y1y2.y0 + y2 + 2y1 U42 = \y0y1y2.y0 + y1 + y2 U44 = \y0y1y2.3 + 3y0 + 3y1 + 3y2 U45 = \y0y1.y0 + y1 U46 = \y0.3 + 3y0 U51 = \y0y1y2.3 + 3y0 + 3y1 + 3y2 U52 = \y0y1y2.y0 + y1 + 2y2 U53 = \y0y1y2.y0 + y1 + y2 U54 = \y0y1y2.3 + 3y0 + 3y1 + 3y2 U55 = \y0y1.y0 + 2y1 U56 = \y0.y0 U61 = \y0y1.3 + 3y0 + 3y1 U62 = \y0y1.1 + y1 + 2y0 U63 = \y0.y0 U71 = \y0y1y2.y0 + y1 + y2 U72 = \y0y1.3 + 3y0 + 3y1 U73 = \y0y1.y0 + y1 U74 = \y0.3 + 3y0 U81 = \y0y1.y0 + y1 U82 = \y0y1.3 + 3y0 + 3y1 U83 = \y0.2 + y0 U91 = \y0y1.3 + 3y0 + 3y1 U92 = \y0.2 + y0 a = 0 activate = \y0.y0 e = 0 i = 0 isList = \y0.2y0 isNeList = \y0.2y0 isNePal = \y0.2y0 isPal = \y0.1 + 2y0 isPalListKind = \y0.y0 isQid = \y0.y0 n!6220!6220!6220!6220 = \y0y1.y1 + 2y0 n!6220!6220a = 0 n!6220!6220e = 0 n!6220!6220i = 0 n!6220!6220nil = 0 n!6220!6220o = 0 n!6220!6220u = 0 nil = 0 o = 0 tt = 0 u = 0 Using this interpretation, the requirements translate to: [[!6220!6220(_x0, nil)]] = 2x0 >= x0 = [[_x0]] [[!6220!6220(nil, _x0)]] = x0 >= x0 = [[_x0]] [[U11(tt, _x0)]] = 3 + 3x0 > 2 + 3x0 = [[U12(isPalListKind(activate(_x0)), activate(_x0))]] [[U12(tt, _x0)]] = 2 + 2x0 > 2x0 = [[U13(isNeList(activate(_x0)))]] [[U13(tt)]] = 0 >= 0 = [[tt]] [[U21(tt, _x0, _x1)]] = x1 + 2x0 >= x1 + 2x0 = [[U22(isPalListKind(activate(_x0)), activate(_x0), activate(_x1))]] [[U24(tt, _x0, _x1)]] = 3 + 3x0 + 3x1 > x1 + 2x0 = [[U25(isList(activate(_x0)), activate(_x1))]] [[U26(tt)]] = 3 > 0 = [[tt]] [[U33(tt)]] = 3 > 0 = [[tt]] [[U41(tt, _x0, _x1)]] = x1 + 2x0 >= x1 + 2x0 = [[U42(isPalListKind(activate(_x0)), activate(_x0), activate(_x1))]] [[U44(tt, _x0, _x1)]] = 3 + 3x0 + 3x1 > x1 + 2x0 = [[U45(isList(activate(_x0)), activate(_x1))]] [[U46(tt)]] = 3 > 0 = [[tt]] [[U51(tt, _x0, _x1)]] = 3 + 3x0 + 3x1 > 2x0 + 2x1 = [[U52(isPalListKind(activate(_x0)), activate(_x0), activate(_x1))]] [[U52(tt, _x0, _x1)]] = x0 + 2x1 >= x0 + 2x1 = [[U53(isPalListKind(activate(_x1)), activate(_x0), activate(_x1))]] [[U54(tt, _x0, _x1)]] = 3 + 3x0 + 3x1 > 2x0 + 2x1 = [[U55(isNeList(activate(_x0)), activate(_x1))]] [[U55(tt, _x0)]] = 2x0 >= 2x0 = [[U56(isList(activate(_x0)))]] [[U56(tt)]] = 0 >= 0 = [[tt]] [[U61(tt, _x0)]] = 3 + 3x0 > 1 + 3x0 = [[U62(isPalListKind(activate(_x0)), activate(_x0))]] [[U62(tt, _x0)]] = 1 + x0 > x0 = [[U63(isQid(activate(_x0)))]] [[U63(tt)]] = 0 >= 0 = [[tt]] [[U72(tt, _x0)]] = 3 + 3x0 > 1 + 3x0 = [[U73(isPal(activate(_x0)), activate(_x0))]] [[U74(tt)]] = 3 > 0 = [[tt]] [[U82(tt, _x0)]] = 3 + 3x0 > 2 + 2x0 = [[U83(isNePal(activate(_x0)))]] [[U83(tt)]] = 2 > 0 = [[tt]] [[U91(tt, _x0)]] = 3 + 3x0 > 2 + x0 = [[U92(isPalListKind(activate(_x0)))]] [[U92(tt)]] = 2 > 0 = [[tt]] [[isList(n!6220!6220nil)]] = 0 >= 0 = [[tt]] [[isList(n!6220!6220!6220!6220(_x0, _x1))]] = 2x1 + 4x0 >= x1 + 3x0 = [[U21(isPalListKind(activate(_x0)), activate(_x0), activate(_x1))]] [[isNeList(n!6220!6220!6220!6220(_x0, _x1))]] = 2x1 + 4x0 >= x1 + 3x0 = [[U41(isPalListKind(activate(_x0)), activate(_x0), activate(_x1))]] [[isNePal(n!6220!6220!6220!6220(_x0, n!6220!6220!6220!6220(_x1, _x0)))]] = 4x1 + 6x0 >= x1 + 2x0 = [[U71(isQid(activate(_x0)), activate(_x0), activate(_x1))]] [[isPal(_x0)]] = 1 + 2x0 > 2x0 = [[U81(isPalListKind(activate(_x0)), activate(_x0))]] [[isPal(n!6220!6220nil)]] = 1 > 0 = [[tt]] [[isPalListKind(n!6220!6220a)]] = 0 >= 0 = [[tt]] [[isPalListKind(n!6220!6220e)]] = 0 >= 0 = [[tt]] [[isPalListKind(n!6220!6220i)]] = 0 >= 0 = [[tt]] [[isPalListKind(n!6220!6220nil)]] = 0 >= 0 = [[tt]] [[isPalListKind(n!6220!6220o)]] = 0 >= 0 = [[tt]] [[isPalListKind(n!6220!6220u)]] = 0 >= 0 = [[tt]] [[isQid(n!6220!6220a)]] = 0 >= 0 = [[tt]] [[isQid(n!6220!6220e)]] = 0 >= 0 = [[tt]] [[isQid(n!6220!6220i)]] = 0 >= 0 = [[tt]] [[isQid(n!6220!6220o)]] = 0 >= 0 = [[tt]] [[isQid(n!6220!6220u)]] = 0 >= 0 = [[tt]] [[nil]] = 0 >= 0 = [[n!6220!6220nil]] [[!6220!6220(_x0, _x1)]] = x1 + 2x0 >= x1 + 2x0 = [[n!6220!6220!6220!6220(_x0, _x1)]] [[a]] = 0 >= 0 = [[n!6220!6220a]] [[e]] = 0 >= 0 = [[n!6220!6220e]] [[i]] = 0 >= 0 = [[n!6220!6220i]] [[o]] = 0 >= 0 = [[n!6220!6220o]] [[u]] = 0 >= 0 = [[n!6220!6220u]] [[activate(n!6220!6220nil)]] = 0 >= 0 = [[nil]] [[activate(n!6220!6220!6220!6220(_x0, _x1))]] = x1 + 2x0 >= x1 + 2x0 = [[!6220!6220(activate(_x0), activate(_x1))]] [[activate(n!6220!6220a)]] = 0 >= 0 = [[a]] [[activate(n!6220!6220e)]] = 0 >= 0 = [[e]] [[activate(n!6220!6220i)]] = 0 >= 0 = [[i]] [[activate(n!6220!6220o)]] = 0 >= 0 = [[o]] [[activate(n!6220!6220u)]] = 0 >= 0 = [[u]] [[activate(_x0)]] = x0 >= x0 = [[_x0]] We can thus remove the following rules: U11(tt, X) => U12(isPalListKind(activate(X)), activate(X)) U12(tt, X) => U13(isNeList(activate(X))) U24(tt, X, Y) => U25(isList(activate(X)), activate(Y)) U26(tt) => tt U33(tt) => tt U44(tt, X, Y) => U45(isList(activate(X)), activate(Y)) U46(tt) => tt U51(tt, X, Y) => U52(isPalListKind(activate(X)), activate(X), activate(Y)) U54(tt, X, Y) => U55(isNeList(activate(X)), activate(Y)) U61(tt, X) => U62(isPalListKind(activate(X)), activate(X)) U62(tt, X) => U63(isQid(activate(X))) U72(tt, X) => U73(isPal(activate(X)), activate(X)) U74(tt) => tt U82(tt, X) => U83(isNePal(activate(X))) U83(tt) => tt U91(tt, X) => U92(isPalListKind(activate(X))) U92(tt) => tt isPal(X) => U81(isPalListKind(activate(X)), activate(X)) isPal(n!6220!6220nil) => 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]): !6220!6220(X, nil) >? X !6220!6220(nil, X) >? X U13(tt) >? tt U21(tt, X, Y) >? U22(isPalListKind(activate(X)), activate(X), activate(Y)) U41(tt, X, Y) >? U42(isPalListKind(activate(X)), activate(X), activate(Y)) U52(tt, X, Y) >? U53(isPalListKind(activate(Y)), activate(X), activate(Y)) U55(tt, X) >? U56(isList(activate(X))) U56(tt) >? tt U63(tt) >? tt isList(n!6220!6220nil) >? tt isList(n!6220!6220!6220!6220(X, Y)) >? U21(isPalListKind(activate(X)), activate(X), activate(Y)) isNeList(n!6220!6220!6220!6220(X, Y)) >? U41(isPalListKind(activate(X)), activate(X), activate(Y)) isNePal(n!6220!6220!6220!6220(X, n!6220!6220!6220!6220(Y, X))) >? U71(isQid(activate(X)), activate(X), activate(Y)) isPalListKind(n!6220!6220a) >? tt isPalListKind(n!6220!6220e) >? tt isPalListKind(n!6220!6220i) >? tt isPalListKind(n!6220!6220nil) >? tt isPalListKind(n!6220!6220o) >? tt isPalListKind(n!6220!6220u) >? tt isQid(n!6220!6220a) >? tt isQid(n!6220!6220e) >? tt isQid(n!6220!6220i) >? tt isQid(n!6220!6220o) >? tt isQid(n!6220!6220u) >? tt nil >? n!6220!6220nil !6220!6220(X, Y) >? n!6220!6220!6220!6220(X, Y) a >? n!6220!6220a e >? n!6220!6220e i >? n!6220!6220i o >? n!6220!6220o u >? n!6220!6220u activate(n!6220!6220nil) >? nil activate(n!6220!6220!6220!6220(X, Y)) >? !6220!6220(activate(X), activate(Y)) activate(n!6220!6220a) >? a activate(n!6220!6220e) >? e activate(n!6220!6220i) >? i activate(n!6220!6220o) >? o activate(n!6220!6220u) >? u activate(X) >? X We orient these requirements with a polynomial interpretation in the natural numbers. The following interpretation satisfies the requirements: !6220!6220 = \y0y1.y0 + y1 U13 = \y0.3 + 3y0 U21 = \y0y1y2.y0 + y2 + 2y1 U22 = \y0y1y2.y0 + y1 + y2 U41 = \y0y1y2.y0 + y2 + 2y1 U42 = \y0y1y2.y0 + y1 + y2 U52 = \y0y1y2.3 + 3y0 + 3y1 + 3y2 U53 = \y0y1y2.y0 + y1 + y2 U55 = \y0y1.3 + 3y0 + 3y1 U56 = \y0.y0 U63 = \y0.3 + 3y0 U71 = \y0y1y2.y0 + y1 + y2 a = 0 activate = \y0.y0 e = 1 i = 0 isList = \y0.3y0 isNeList = \y0.3 + 3y0 isNePal = \y0.3 + 3y0 isPalListKind = \y0.y0 isQid = \y0.y0 n!6220!6220!6220!6220 = \y0y1.y0 + y1 n!6220!6220a = 0 n!6220!6220e = 1 n!6220!6220i = 0 n!6220!6220nil = 0 n!6220!6220o = 0 n!6220!6220u = 0 nil = 0 o = 0 tt = 0 u = 0 Using this interpretation, the requirements translate to: [[!6220!6220(_x0, nil)]] = x0 >= x0 = [[_x0]] [[!6220!6220(nil, _x0)]] = x0 >= x0 = [[_x0]] [[U13(tt)]] = 3 > 0 = [[tt]] [[U21(tt, _x0, _x1)]] = x1 + 2x0 >= x1 + 2x0 = [[U22(isPalListKind(activate(_x0)), activate(_x0), activate(_x1))]] [[U41(tt, _x0, _x1)]] = x1 + 2x0 >= x1 + 2x0 = [[U42(isPalListKind(activate(_x0)), activate(_x0), activate(_x1))]] [[U52(tt, _x0, _x1)]] = 3 + 3x0 + 3x1 > x0 + 2x1 = [[U53(isPalListKind(activate(_x1)), activate(_x0), activate(_x1))]] [[U55(tt, _x0)]] = 3 + 3x0 > 3x0 = [[U56(isList(activate(_x0)))]] [[U56(tt)]] = 0 >= 0 = [[tt]] [[U63(tt)]] = 3 > 0 = [[tt]] [[isList(n!6220!6220nil)]] = 0 >= 0 = [[tt]] [[isList(n!6220!6220!6220!6220(_x0, _x1))]] = 3x0 + 3x1 >= x1 + 3x0 = [[U21(isPalListKind(activate(_x0)), activate(_x0), activate(_x1))]] [[isNeList(n!6220!6220!6220!6220(_x0, _x1))]] = 3 + 3x0 + 3x1 > x1 + 3x0 = [[U41(isPalListKind(activate(_x0)), activate(_x0), activate(_x1))]] [[isNePal(n!6220!6220!6220!6220(_x0, n!6220!6220!6220!6220(_x1, _x0)))]] = 3 + 3x1 + 6x0 > x1 + 2x0 = [[U71(isQid(activate(_x0)), activate(_x0), activate(_x1))]] [[isPalListKind(n!6220!6220a)]] = 0 >= 0 = [[tt]] [[isPalListKind(n!6220!6220e)]] = 1 > 0 = [[tt]] [[isPalListKind(n!6220!6220i)]] = 0 >= 0 = [[tt]] [[isPalListKind(n!6220!6220nil)]] = 0 >= 0 = [[tt]] [[isPalListKind(n!6220!6220o)]] = 0 >= 0 = [[tt]] [[isPalListKind(n!6220!6220u)]] = 0 >= 0 = [[tt]] [[isQid(n!6220!6220a)]] = 0 >= 0 = [[tt]] [[isQid(n!6220!6220e)]] = 1 > 0 = [[tt]] [[isQid(n!6220!6220i)]] = 0 >= 0 = [[tt]] [[isQid(n!6220!6220o)]] = 0 >= 0 = [[tt]] [[isQid(n!6220!6220u)]] = 0 >= 0 = [[tt]] [[nil]] = 0 >= 0 = [[n!6220!6220nil]] [[!6220!6220(_x0, _x1)]] = x0 + x1 >= x0 + x1 = [[n!6220!6220!6220!6220(_x0, _x1)]] [[a]] = 0 >= 0 = [[n!6220!6220a]] [[e]] = 1 >= 1 = [[n!6220!6220e]] [[i]] = 0 >= 0 = [[n!6220!6220i]] [[o]] = 0 >= 0 = [[n!6220!6220o]] [[u]] = 0 >= 0 = [[n!6220!6220u]] [[activate(n!6220!6220nil)]] = 0 >= 0 = [[nil]] [[activate(n!6220!6220!6220!6220(_x0, _x1))]] = x0 + x1 >= x0 + x1 = [[!6220!6220(activate(_x0), activate(_x1))]] [[activate(n!6220!6220a)]] = 0 >= 0 = [[a]] [[activate(n!6220!6220e)]] = 1 >= 1 = [[e]] [[activate(n!6220!6220i)]] = 0 >= 0 = [[i]] [[activate(n!6220!6220o)]] = 0 >= 0 = [[o]] [[activate(n!6220!6220u)]] = 0 >= 0 = [[u]] [[activate(_x0)]] = x0 >= x0 = [[_x0]] We can thus remove the following rules: U13(tt) => tt U52(tt, X, Y) => U53(isPalListKind(activate(Y)), activate(X), activate(Y)) U55(tt, X) => U56(isList(activate(X))) U63(tt) => tt isNeList(n!6220!6220!6220!6220(X, Y)) => U41(isPalListKind(activate(X)), activate(X), activate(Y)) isNePal(n!6220!6220!6220!6220(X, n!6220!6220!6220!6220(Y, X))) => U71(isQid(activate(X)), activate(X), activate(Y)) isPalListKind(n!6220!6220e) => tt isQid(n!6220!6220e) => 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]): !6220!6220(X, nil) >? X !6220!6220(nil, X) >? X U21(tt, X, Y) >? U22(isPalListKind(activate(X)), activate(X), activate(Y)) U41(tt, X, Y) >? U42(isPalListKind(activate(X)), activate(X), activate(Y)) U56(tt) >? tt isList(n!6220!6220nil) >? tt isList(n!6220!6220!6220!6220(X, Y)) >? U21(isPalListKind(activate(X)), activate(X), activate(Y)) isPalListKind(n!6220!6220a) >? tt isPalListKind(n!6220!6220i) >? tt isPalListKind(n!6220!6220nil) >? tt isPalListKind(n!6220!6220o) >? tt isPalListKind(n!6220!6220u) >? tt isQid(n!6220!6220a) >? tt isQid(n!6220!6220i) >? tt isQid(n!6220!6220o) >? tt isQid(n!6220!6220u) >? tt nil >? n!6220!6220nil !6220!6220(X, Y) >? n!6220!6220!6220!6220(X, Y) a >? n!6220!6220a e >? n!6220!6220e i >? n!6220!6220i o >? n!6220!6220o u >? n!6220!6220u activate(n!6220!6220nil) >? nil activate(n!6220!6220!6220!6220(X, Y)) >? !6220!6220(activate(X), activate(Y)) activate(n!6220!6220a) >? a activate(n!6220!6220e) >? e activate(n!6220!6220i) >? i activate(n!6220!6220o) >? o activate(n!6220!6220u) >? u activate(X) >? X We orient these requirements with a polynomial interpretation in the natural numbers. The following interpretation satisfies the requirements: !6220!6220 = \y0y1.2y0 + 2y1 U21 = \y0y1y2.1 + y0 + y2 + 2y1 U22 = \y0y1y2.y0 + y1 + y2 U41 = \y0y1y2.3 + 3y0 + 3y1 + 3y2 U42 = \y0y1y2.y0 + y1 + y2 U56 = \y0.3 + 3y0 a = 0 activate = \y0.y0 e = 0 i = 0 isList = \y0.3 + 3y0 isPalListKind = \y0.y0 isQid = \y0.3 + 3y0 n!6220!6220!6220!6220 = \y0y1.2y0 + 2y1 n!6220!6220a = 0 n!6220!6220e = 0 n!6220!6220i = 0 n!6220!6220nil = 0 n!6220!6220o = 3 n!6220!6220u = 0 nil = 0 o = 3 tt = 0 u = 0 Using this interpretation, the requirements translate to: [[!6220!6220(_x0, nil)]] = 2x0 >= x0 = [[_x0]] [[!6220!6220(nil, _x0)]] = 2x0 >= x0 = [[_x0]] [[U21(tt, _x0, _x1)]] = 1 + x1 + 2x0 > x1 + 2x0 = [[U22(isPalListKind(activate(_x0)), activate(_x0), activate(_x1))]] [[U41(tt, _x0, _x1)]] = 3 + 3x0 + 3x1 > x1 + 2x0 = [[U42(isPalListKind(activate(_x0)), activate(_x0), activate(_x1))]] [[U56(tt)]] = 3 > 0 = [[tt]] [[isList(n!6220!6220nil)]] = 3 > 0 = [[tt]] [[isList(n!6220!6220!6220!6220(_x0, _x1))]] = 3 + 6x0 + 6x1 > 1 + x1 + 3x0 = [[U21(isPalListKind(activate(_x0)), activate(_x0), activate(_x1))]] [[isPalListKind(n!6220!6220a)]] = 0 >= 0 = [[tt]] [[isPalListKind(n!6220!6220i)]] = 0 >= 0 = [[tt]] [[isPalListKind(n!6220!6220nil)]] = 0 >= 0 = [[tt]] [[isPalListKind(n!6220!6220o)]] = 3 > 0 = [[tt]] [[isPalListKind(n!6220!6220u)]] = 0 >= 0 = [[tt]] [[isQid(n!6220!6220a)]] = 3 > 0 = [[tt]] [[isQid(n!6220!6220i)]] = 3 > 0 = [[tt]] [[isQid(n!6220!6220o)]] = 12 > 0 = [[tt]] [[isQid(n!6220!6220u)]] = 3 > 0 = [[tt]] [[nil]] = 0 >= 0 = [[n!6220!6220nil]] [[!6220!6220(_x0, _x1)]] = 2x0 + 2x1 >= 2x0 + 2x1 = [[n!6220!6220!6220!6220(_x0, _x1)]] [[a]] = 0 >= 0 = [[n!6220!6220a]] [[e]] = 0 >= 0 = [[n!6220!6220e]] [[i]] = 0 >= 0 = [[n!6220!6220i]] [[o]] = 3 >= 3 = [[n!6220!6220o]] [[u]] = 0 >= 0 = [[n!6220!6220u]] [[activate(n!6220!6220nil)]] = 0 >= 0 = [[nil]] [[activate(n!6220!6220!6220!6220(_x0, _x1))]] = 2x0 + 2x1 >= 2x0 + 2x1 = [[!6220!6220(activate(_x0), activate(_x1))]] [[activate(n!6220!6220a)]] = 0 >= 0 = [[a]] [[activate(n!6220!6220e)]] = 0 >= 0 = [[e]] [[activate(n!6220!6220i)]] = 0 >= 0 = [[i]] [[activate(n!6220!6220o)]] = 3 >= 3 = [[o]] [[activate(n!6220!6220u)]] = 0 >= 0 = [[u]] [[activate(_x0)]] = x0 >= x0 = [[_x0]] We can thus remove the following rules: U21(tt, X, Y) => U22(isPalListKind(activate(X)), activate(X), activate(Y)) U41(tt, X, Y) => U42(isPalListKind(activate(X)), activate(X), activate(Y)) U56(tt) => tt isList(n!6220!6220nil) => tt isList(n!6220!6220!6220!6220(X, Y)) => U21(isPalListKind(activate(X)), activate(X), activate(Y)) isPalListKind(n!6220!6220o) => tt isQid(n!6220!6220a) => tt isQid(n!6220!6220i) => tt isQid(n!6220!6220o) => tt isQid(n!6220!6220u) => 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]): !6220!6220(X, nil) >? X !6220!6220(nil, X) >? X isPalListKind(n!6220!6220a) >? tt isPalListKind(n!6220!6220i) >? tt isPalListKind(n!6220!6220nil) >? tt isPalListKind(n!6220!6220u) >? tt nil >? n!6220!6220nil !6220!6220(X, Y) >? n!6220!6220!6220!6220(X, Y) a >? n!6220!6220a e >? n!6220!6220e i >? n!6220!6220i o >? n!6220!6220o u >? n!6220!6220u activate(n!6220!6220nil) >? nil activate(n!6220!6220!6220!6220(X, Y)) >? !6220!6220(activate(X), activate(Y)) activate(n!6220!6220a) >? a activate(n!6220!6220e) >? e activate(n!6220!6220i) >? i activate(n!6220!6220o) >? o activate(n!6220!6220u) >? u activate(X) >? X We orient these requirements with a polynomial interpretation in the natural numbers. The following interpretation satisfies the requirements: !6220!6220 = \y0y1.y0 + y1 a = 0 activate = \y0.2y0 e = 0 i = 0 isPalListKind = \y0.3 + 3y0 n!6220!6220!6220!6220 = \y0y1.y0 + y1 n!6220!6220a = 0 n!6220!6220e = 0 n!6220!6220i = 0 n!6220!6220nil = 1 n!6220!6220o = 0 n!6220!6220u = 0 nil = 1 o = 0 tt = 0 u = 0 Using this interpretation, the requirements translate to: [[!6220!6220(_x0, nil)]] = 1 + x0 > x0 = [[_x0]] [[!6220!6220(nil, _x0)]] = 1 + x0 > x0 = [[_x0]] [[isPalListKind(n!6220!6220a)]] = 3 > 0 = [[tt]] [[isPalListKind(n!6220!6220i)]] = 3 > 0 = [[tt]] [[isPalListKind(n!6220!6220nil)]] = 6 > 0 = [[tt]] [[isPalListKind(n!6220!6220u)]] = 3 > 0 = [[tt]] [[nil]] = 1 >= 1 = [[n!6220!6220nil]] [[!6220!6220(_x0, _x1)]] = x0 + x1 >= x0 + x1 = [[n!6220!6220!6220!6220(_x0, _x1)]] [[a]] = 0 >= 0 = [[n!6220!6220a]] [[e]] = 0 >= 0 = [[n!6220!6220e]] [[i]] = 0 >= 0 = [[n!6220!6220i]] [[o]] = 0 >= 0 = [[n!6220!6220o]] [[u]] = 0 >= 0 = [[n!6220!6220u]] [[activate(n!6220!6220nil)]] = 2 > 1 = [[nil]] [[activate(n!6220!6220!6220!6220(_x0, _x1))]] = 2x0 + 2x1 >= 2x0 + 2x1 = [[!6220!6220(activate(_x0), activate(_x1))]] [[activate(n!6220!6220a)]] = 0 >= 0 = [[a]] [[activate(n!6220!6220e)]] = 0 >= 0 = [[e]] [[activate(n!6220!6220i)]] = 0 >= 0 = [[i]] [[activate(n!6220!6220o)]] = 0 >= 0 = [[o]] [[activate(n!6220!6220u)]] = 0 >= 0 = [[u]] [[activate(_x0)]] = 2x0 >= x0 = [[_x0]] We can thus remove the following rules: !6220!6220(X, nil) => X !6220!6220(nil, X) => X isPalListKind(n!6220!6220a) => tt isPalListKind(n!6220!6220i) => tt isPalListKind(n!6220!6220nil) => tt isPalListKind(n!6220!6220u) => tt activate(n!6220!6220nil) => nil We use rule removal, following [Kop12, Theorem 2.23]. This gives the following requirements (possibly using Theorems 2.25 and 2.26 in [Kop12]): nil >? n!6220!6220nil !6220!6220(X, Y) >? n!6220!6220!6220!6220(X, Y) a >? n!6220!6220a e >? n!6220!6220e i >? n!6220!6220i o >? n!6220!6220o u >? n!6220!6220u activate(n!6220!6220!6220!6220(X, Y)) >? !6220!6220(activate(X), activate(Y)) activate(n!6220!6220a) >? a activate(n!6220!6220e) >? e activate(n!6220!6220i) >? i activate(n!6220!6220o) >? o activate(n!6220!6220u) >? u activate(X) >? X We orient these requirements with a polynomial interpretation in the natural numbers. The following interpretation satisfies the requirements: !6220!6220 = \y0y1.y0 + y1 a = 0 activate = \y0.y0 e = 0 i = 0 n!6220!6220!6220!6220 = \y0y1.y0 + y1 n!6220!6220a = 0 n!6220!6220e = 0 n!6220!6220i = 0 n!6220!6220nil = 0 n!6220!6220o = 0 n!6220!6220u = 0 nil = 3 o = 0 u = 0 Using this interpretation, the requirements translate to: [[nil]] = 3 > 0 = [[n!6220!6220nil]] [[!6220!6220(_x0, _x1)]] = x0 + x1 >= x0 + x1 = [[n!6220!6220!6220!6220(_x0, _x1)]] [[a]] = 0 >= 0 = [[n!6220!6220a]] [[e]] = 0 >= 0 = [[n!6220!6220e]] [[i]] = 0 >= 0 = [[n!6220!6220i]] [[o]] = 0 >= 0 = [[n!6220!6220o]] [[u]] = 0 >= 0 = [[n!6220!6220u]] [[activate(n!6220!6220!6220!6220(_x0, _x1))]] = x0 + x1 >= x0 + x1 = [[!6220!6220(activate(_x0), activate(_x1))]] [[activate(n!6220!6220a)]] = 0 >= 0 = [[a]] [[activate(n!6220!6220e)]] = 0 >= 0 = [[e]] [[activate(n!6220!6220i)]] = 0 >= 0 = [[i]] [[activate(n!6220!6220o)]] = 0 >= 0 = [[o]] [[activate(n!6220!6220u)]] = 0 >= 0 = [[u]] [[activate(_x0)]] = x0 >= x0 = [[_x0]] We can thus remove the following rules: nil => n!6220!6220nil We use rule removal, following [Kop12, Theorem 2.23]. This gives the following requirements (possibly using Theorems 2.25 and 2.26 in [Kop12]): !6220!6220(X, Y) >? n!6220!6220!6220!6220(X, Y) a >? n!6220!6220a e >? n!6220!6220e i >? n!6220!6220i o >? n!6220!6220o u >? n!6220!6220u activate(n!6220!6220!6220!6220(X, Y)) >? !6220!6220(activate(X), activate(Y)) activate(n!6220!6220a) >? a activate(n!6220!6220e) >? e activate(n!6220!6220i) >? i activate(n!6220!6220o) >? o activate(n!6220!6220u) >? u activate(X) >? X We orient these requirements with a polynomial interpretation in the natural numbers. The following interpretation satisfies the requirements: !6220!6220 = \y0y1.y0 + 2y1 a = 1 activate = \y0.2y0 e = 3 i = 1 n!6220!6220!6220!6220 = \y0y1.y0 + 2y1 n!6220!6220a = 1 n!6220!6220e = 2 n!6220!6220i = 1 n!6220!6220o = 2 n!6220!6220u = 1 o = 3 u = 2 Using this interpretation, the requirements translate to: [[!6220!6220(_x0, _x1)]] = x0 + 2x1 >= x0 + 2x1 = [[n!6220!6220!6220!6220(_x0, _x1)]] [[a]] = 1 >= 1 = [[n!6220!6220a]] [[e]] = 3 > 2 = [[n!6220!6220e]] [[i]] = 1 >= 1 = [[n!6220!6220i]] [[o]] = 3 > 2 = [[n!6220!6220o]] [[u]] = 2 > 1 = [[n!6220!6220u]] [[activate(n!6220!6220!6220!6220(_x0, _x1))]] = 2x0 + 4x1 >= 2x0 + 4x1 = [[!6220!6220(activate(_x0), activate(_x1))]] [[activate(n!6220!6220a)]] = 2 > 1 = [[a]] [[activate(n!6220!6220e)]] = 4 > 3 = [[e]] [[activate(n!6220!6220i)]] = 2 > 1 = [[i]] [[activate(n!6220!6220o)]] = 4 > 3 = [[o]] [[activate(n!6220!6220u)]] = 2 >= 2 = [[u]] [[activate(_x0)]] = 2x0 >= x0 = [[_x0]] We can thus remove the following rules: e => n!6220!6220e o => n!6220!6220o u => n!6220!6220u activate(n!6220!6220a) => a activate(n!6220!6220e) => e activate(n!6220!6220i) => i activate(n!6220!6220o) => o We use rule removal, following [Kop12, Theorem 2.23]. This gives the following requirements (possibly using Theorems 2.25 and 2.26 in [Kop12]): !6220!6220(X, Y) >? n!6220!6220!6220!6220(X, Y) a >? n!6220!6220a i >? n!6220!6220i activate(n!6220!6220!6220!6220(X, Y)) >? !6220!6220(activate(X), activate(Y)) activate(n!6220!6220u) >? u activate(X) >? X We orient these requirements with a polynomial interpretation in the natural numbers. The following interpretation satisfies the requirements: !6220!6220 = \y0y1.y0 + y1 a = 3 activate = \y0.y0 i = 3 n!6220!6220!6220!6220 = \y0y1.y0 + y1 n!6220!6220a = 0 n!6220!6220i = 0 n!6220!6220u = 3 u = 0 Using this interpretation, the requirements translate to: [[!6220!6220(_x0, _x1)]] = x0 + x1 >= x0 + x1 = [[n!6220!6220!6220!6220(_x0, _x1)]] [[a]] = 3 > 0 = [[n!6220!6220a]] [[i]] = 3 > 0 = [[n!6220!6220i]] [[activate(n!6220!6220!6220!6220(_x0, _x1))]] = x0 + x1 >= x0 + x1 = [[!6220!6220(activate(_x0), activate(_x1))]] [[activate(n!6220!6220u)]] = 3 > 0 = [[u]] [[activate(_x0)]] = x0 >= x0 = [[_x0]] We can thus remove the following rules: a => n!6220!6220a i => n!6220!6220i activate(n!6220!6220u) => u We use rule removal, following [Kop12, Theorem 2.23]. This gives the following requirements (possibly using Theorems 2.25 and 2.26 in [Kop12]): !6220!6220(X, Y) >? n!6220!6220!6220!6220(X, Y) activate(n!6220!6220!6220!6220(X, Y)) >? !6220!6220(activate(X), activate(Y)) activate(X) >? X We orient these requirements with a polynomial interpretation in the natural numbers. The following interpretation satisfies the requirements: !6220!6220 = \y0y1.2 + y0 + 2y1 activate = \y0.2y0 n!6220!6220!6220!6220 = \y0y1.1 + y0 + 2y1 Using this interpretation, the requirements translate to: [[!6220!6220(_x0, _x1)]] = 2 + x0 + 2x1 > 1 + x0 + 2x1 = [[n!6220!6220!6220!6220(_x0, _x1)]] [[activate(n!6220!6220!6220!6220(_x0, _x1))]] = 2 + 2x0 + 4x1 >= 2 + 2x0 + 4x1 = [[!6220!6220(activate(_x0), activate(_x1))]] [[activate(_x0)]] = 2x0 >= x0 = [[_x0]] We can thus remove the following rules: !6220!6220(X, Y) => n!6220!6220!6220!6220(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]): activate(n!6220!6220!6220!6220(X, Y)) >? !6220!6220(activate(X), activate(Y)) activate(X) >? X We orient these requirements with a polynomial interpretation in the natural numbers. The following interpretation satisfies the requirements: !6220!6220 = \y0y1.y0 + y1 activate = \y0.3y0 n!6220!6220!6220!6220 = \y0y1.3 + 3y0 + 3y1 Using this interpretation, the requirements translate to: [[activate(n!6220!6220!6220!6220(_x0, _x1))]] = 9 + 9x0 + 9x1 > 3x0 + 3x1 = [[!6220!6220(activate(_x0), activate(_x1))]] [[activate(_x0)]] = 3x0 >= x0 = [[_x0]] We can thus remove the following rules: activate(n!6220!6220!6220!6220(X, Y)) => !6220!6220(activate(X), activate(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]): activate(X) >? X We orient these requirements with a polynomial interpretation in the natural numbers. The following interpretation satisfies the requirements: activate = \y0.1 + y0 Using this interpretation, the requirements translate to: [[activate(_x0)]] = 1 + x0 > x0 = [[_x0]] We can thus remove the following rules: activate(X) => 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.