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