/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 U21 : [o * o * o] --> o U22 : [o * o] --> o U23 : [o] --> o U31 : [o * o] --> o U32 : [o] --> o U41 : [o * o * o] --> o U42 : [o * o] --> o U43 : [o] --> o U51 : [o * o * o] --> o U52 : [o * o] --> o U53 : [o] --> o U61 : [o * o] --> o U62 : [o] --> o U71 : [o * o] --> o U72 : [o] --> o a : [] --> o activate : [o] --> o and : [o * 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!6220and : [o * o] --> o n!6220!6220e : [] --> o n!6220!6220i : [] --> o n!6220!6220isPal : [o] --> o n!6220!6220isPalListKind : [o] --> 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(isNeList(activate(X))) U12(tt) => tt U21(tt, X, Y) => U22(isList(activate(X)), activate(Y)) U22(tt, X) => U23(isList(activate(X))) U23(tt) => tt U31(tt, X) => U32(isQid(activate(X))) U32(tt) => tt U41(tt, X, Y) => U42(isList(activate(X)), activate(Y)) U42(tt, X) => U43(isNeList(activate(X))) U43(tt) => tt U51(tt, X, Y) => U52(isNeList(activate(X)), activate(Y)) U52(tt, X) => U53(isList(activate(X))) U53(tt) => tt U61(tt, X) => U62(isQid(activate(X))) U62(tt) => tt U71(tt, X) => U72(isNePal(activate(X))) U72(tt) => tt and(tt, X) => activate(X) isList(X) => U11(isPalListKind(activate(X)), activate(X)) isList(n!6220!6220nil) => tt isList(n!6220!6220!6220!6220(X, Y)) => U21(and(isPalListKind(activate(X)), n!6220!6220isPalListKind(activate(Y))), activate(X), activate(Y)) isNeList(X) => U31(isPalListKind(activate(X)), activate(X)) isNeList(n!6220!6220!6220!6220(X, Y)) => U41(and(isPalListKind(activate(X)), n!6220!6220isPalListKind(activate(Y))), activate(X), activate(Y)) isNeList(n!6220!6220!6220!6220(X, Y)) => U51(and(isPalListKind(activate(X)), n!6220!6220isPalListKind(activate(Y))), 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))) => and(and(isQid(activate(X)), n!6220!6220isPalListKind(activate(X))), n!6220!6220and(n!6220!6220isPal(activate(Y)), n!6220!6220isPalListKind(activate(Y)))) isPal(X) => U71(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)) => and(isPalListKind(activate(X)), n!6220!6220isPalListKind(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) isPalListKind(X) => n!6220!6220isPalListKind(X) and(X, Y) => n!6220!6220and(X, Y) isPal(X) => n!6220!6220isPal(X) 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!6220isPalListKind(X)) => isPalListKind(X) activate(n!6220!6220and(X, Y)) => and(activate(X), Y) activate(n!6220!6220isPal(X)) => isPal(X) 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(isNeList(activate(X))) U12(tt) >? tt U21(tt, X, Y) >? U22(isList(activate(X)), activate(Y)) U22(tt, X) >? U23(isList(activate(X))) U23(tt) >? tt U31(tt, X) >? U32(isQid(activate(X))) U32(tt) >? tt U41(tt, X, Y) >? U42(isList(activate(X)), activate(Y)) U42(tt, X) >? U43(isNeList(activate(X))) U43(tt) >? tt U51(tt, X, Y) >? U52(isNeList(activate(X)), activate(Y)) U52(tt, X) >? U53(isList(activate(X))) U53(tt) >? tt U61(tt, X) >? U62(isQid(activate(X))) U62(tt) >? tt U71(tt, X) >? U72(isNePal(activate(X))) U72(tt) >? tt and(tt, X) >? activate(X) isList(X) >? U11(isPalListKind(activate(X)), activate(X)) isList(n!6220!6220nil) >? tt isList(n!6220!6220!6220!6220(X, Y)) >? U21(and(isPalListKind(activate(X)), n!6220!6220isPalListKind(activate(Y))), activate(X), activate(Y)) isNeList(X) >? U31(isPalListKind(activate(X)), activate(X)) isNeList(n!6220!6220!6220!6220(X, Y)) >? U41(and(isPalListKind(activate(X)), n!6220!6220isPalListKind(activate(Y))), activate(X), activate(Y)) isNeList(n!6220!6220!6220!6220(X, Y)) >? U51(and(isPalListKind(activate(X)), n!6220!6220isPalListKind(activate(Y))), 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))) >? and(and(isQid(activate(X)), n!6220!6220isPalListKind(activate(X))), n!6220!6220and(n!6220!6220isPal(activate(Y)), n!6220!6220isPalListKind(activate(Y)))) isPal(X) >? U71(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)) >? and(isPalListKind(activate(X)), n!6220!6220isPalListKind(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) isPalListKind(X) >? n!6220!6220isPalListKind(X) and(X, Y) >? n!6220!6220and(X, Y) isPal(X) >? n!6220!6220isPal(X) 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!6220isPalListKind(X)) >? isPalListKind(X) activate(n!6220!6220and(X, Y)) >? and(activate(X), Y) activate(n!6220!6220isPal(X)) >? isPal(X) 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: [[U12(x_1)]] = x_1 [[U43(x_1)]] = x_1 [[U53(x_1)]] = x_1 [[U62(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!6220nil]] = _|_ [[nil]] = _|_ [[tt]] = _|_ We choose Lex = {!6220!6220, n!6220!6220!6220!6220} and Mul = {U11, U21, U22, U23, U31, U32, U41, U42, U51, U52, U61, U71, U72, and, isList, isNeList, isNePal, isPal, isPalListKind, n!6220!6220and, n!6220!6220isPal, n!6220!6220isPalListKind, n!6220!6220o, n!6220!6220u, o, u}, and the following precedence: n!6220!6220o = o > !6220!6220 = n!6220!6220!6220!6220 > U51 > U21 > U22 > U23 > U41 > n!6220!6220u = u > U52 = isList > and = n!6220!6220and > isPal = n!6220!6220isPal > U71 > U11 > U72 > isNePal > U61 > U42 = isNeList > U31 > U32 > isPalListKind = n!6220!6220isPalListKind 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) >= isNeList(X) _|_ >= _|_ U21(_|_, X, Y) >= U22(isList(X), Y) U22(_|_, X) > U23(isList(X)) U23(_|_) >= _|_ U31(_|_, X) > U32(X) U32(_|_) >= _|_ U41(_|_, X, Y) >= U42(isList(X), Y) U42(_|_, X) >= isNeList(X) _|_ >= _|_ U51(_|_, X, Y) > U52(isNeList(X), Y) U52(_|_, X) > isList(X) _|_ >= _|_ U61(_|_, X) >= X _|_ >= _|_ U71(_|_, X) > U72(isNePal(X)) U72(_|_) >= _|_ and(_|_, X) >= X isList(X) > U11(isPalListKind(X), X) isList(_|_) >= _|_ isList(n!6220!6220!6220!6220(X, Y)) > U21(and(isPalListKind(X), n!6220!6220isPalListKind(Y)), X, Y) isNeList(X) >= U31(isPalListKind(X), X) isNeList(n!6220!6220!6220!6220(X, Y)) > U41(and(isPalListKind(X), n!6220!6220isPalListKind(Y)), X, Y) isNeList(n!6220!6220!6220!6220(X, Y)) >= U51(and(isPalListKind(X), n!6220!6220isPalListKind(Y)), X, Y) isNePal(X) > U61(isPalListKind(X), X) isNePal(n!6220!6220!6220!6220(X, n!6220!6220!6220!6220(Y, X))) > and(and(X, n!6220!6220isPalListKind(X)), n!6220!6220and(n!6220!6220isPal(Y), n!6220!6220isPalListKind(Y))) isPal(X) > U71(isPalListKind(X), X) isPal(_|_) >= _|_ isPalListKind(_|_) >= _|_ isPalListKind(_|_) >= _|_ isPalListKind(_|_) >= _|_ isPalListKind(_|_) >= _|_ isPalListKind(n!6220!6220o) >= _|_ isPalListKind(n!6220!6220u) >= _|_ isPalListKind(n!6220!6220!6220!6220(X, Y)) >= and(isPalListKind(X), n!6220!6220isPalListKind(Y)) _|_ >= _|_ _|_ >= _|_ _|_ >= _|_ n!6220!6220o > _|_ n!6220!6220u >= _|_ _|_ >= _|_ !6220!6220(X, Y) >= n!6220!6220!6220!6220(X, Y) isPalListKind(X) >= n!6220!6220isPalListKind(X) and(X, Y) >= n!6220!6220and(X, Y) isPal(X) >= n!6220!6220isPal(X) _|_ >= _|_ _|_ >= _|_ _|_ >= _|_ o >= n!6220!6220o u >= n!6220!6220u _|_ >= _|_ n!6220!6220!6220!6220(X, Y) >= !6220!6220(X, Y) n!6220!6220isPalListKind(X) >= isPalListKind(X) n!6220!6220and(X, Y) >= and(X, Y) n!6220!6220isPal(X) >= isPal(X) _|_ >= _|_ _|_ >= _|_ _|_ >= _|_ n!6220!6220o >= o n!6220!6220u >= u 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, _|_) >= X because [17], by (Star) 17] !6220!6220*(X, _|_) >= X because [5], by (Select) 18] !6220!6220(_|_, X) > X because [19], by definition 19] !6220!6220*(_|_, X) >= X because [5], by (Select) 20] U11(_|_, X) >= isNeList(X) because [21], by (Star) 21] U11*(_|_, X) >= isNeList(X) because U11 > isNeList and [22], by (Copy) 22] U11*(_|_, X) >= X because [23], by (Select) 23] X >= X by (Meta) 24] _|_ >= _|_ by (Bot) 25] U21(_|_, X, Y) >= U22(isList(X), Y) because [26], by (Star) 26] U21*(_|_, X, Y) >= U22(isList(X), Y) because U21 > U22, [27] and [30], by (Copy) 27] U21*(_|_, X, Y) >= isList(X) because U21 > isList and [28], by (Copy) 28] U21*(_|_, X, Y) >= X because [29], by (Select) 29] X >= X by (Meta) 30] U21*(_|_, X, Y) >= Y because [31], by (Select) 31] Y >= Y by (Meta) 32] U22(_|_, X) > U23(isList(X)) because [33], by definition 33] U22*(_|_, X) >= U23(isList(X)) because U22 > U23 and [34], by (Copy) 34] U22*(_|_, X) >= isList(X) because U22 > isList and [35], by (Copy) 35] U22*(_|_, X) >= X because [31], by (Select) 36] U23(_|_) >= _|_ by (Bot) 37] U31(_|_, X) > U32(X) because [38], by definition 38] U31*(_|_, X) >= U32(X) because U31 > U32 and [39], by (Copy) 39] U31*(_|_, X) >= X because [23], by (Select) 40] U32(_|_) >= _|_ by (Bot) 41] U41(_|_, X, Y) >= U42(isList(X), Y) because [42], by (Star) 42] U41*(_|_, X, Y) >= U42(isList(X), Y) because U41 > U42, [43] and [45], by (Copy) 43] U41*(_|_, X, Y) >= isList(X) because U41 > isList and [44], by (Copy) 44] U41*(_|_, X, Y) >= X because [29], by (Select) 45] U41*(_|_, X, Y) >= Y because [31], by (Select) 46] U42(_|_, X) >= isNeList(X) because [47], by (Star) 47] U42*(_|_, X) >= isNeList(X) because U42 = isNeList, U42 in Mul and [48], by (Stat) 48] X >= X by (Meta) 49] _|_ >= _|_ by (Bot) 50] U51(_|_, X, Y) > U52(isNeList(X), Y) because [51], by definition 51] U51*(_|_, X, Y) >= U52(isNeList(X), Y) because U51 > U52, [52] and [54], by (Copy) 52] U51*(_|_, X, Y) >= isNeList(X) because U51 > isNeList and [53], by (Copy) 53] U51*(_|_, X, Y) >= X because [29], by (Select) 54] U51*(_|_, X, Y) >= Y because [48], by (Select) 55] U52(_|_, X) > isList(X) because [56], by definition 56] U52*(_|_, X) >= isList(X) because U52 = isList, U52 in Mul and [48], by (Stat) 57] _|_ >= _|_ by (Bot) 58] U61(_|_, X) >= X because [59], by (Star) 59] U61*(_|_, X) >= X because [23], by (Select) 60] _|_ >= _|_ by (Bot) 61] U71(_|_, X) > U72(isNePal(X)) because [62], by definition 62] U71*(_|_, X) >= U72(isNePal(X)) because U71 > U72 and [63], by (Copy) 63] U71*(_|_, X) >= isNePal(X) because U71 > isNePal and [64], by (Copy) 64] U71*(_|_, X) >= X because [23], by (Select) 65] U72(_|_) >= _|_ by (Bot) 66] and(_|_, X) >= X because [67], by (Star) 67] and*(_|_, X) >= X because [5], by (Select) 68] isList(X) > U11(isPalListKind(X), X) because [69], by definition 69] isList*(X) >= U11(isPalListKind(X), X) because isList > U11, [70] and [71], by (Copy) 70] isList*(X) >= isPalListKind(X) because isList > isPalListKind and [71], by (Copy) 71] isList*(X) >= X because [23], by (Select) 72] isList(_|_) >= _|_ by (Bot) 73] isList(n!6220!6220!6220!6220(X, Y)) > U21(and(isPalListKind(X), n!6220!6220isPalListKind(Y)), X, Y) because [74], by definition 74] isList*(n!6220!6220!6220!6220(X, Y)) >= U21(and(isPalListKind(X), n!6220!6220isPalListKind(Y)), X, Y) because [75], by (Select) 75] n!6220!6220!6220!6220(X, Y) >= U21(and(isPalListKind(X), n!6220!6220isPalListKind(Y)), X, Y) because [76], by (Star) 76] n!6220!6220!6220!6220*(X, Y) >= U21(and(isPalListKind(X), n!6220!6220isPalListKind(Y)), X, Y) because n!6220!6220!6220!6220 > U21, [77], [79] and [81], by (Copy) 77] n!6220!6220!6220!6220*(X, Y) >= and(isPalListKind(X), n!6220!6220isPalListKind(Y)) because n!6220!6220!6220!6220 > and, [78] and [80], by (Copy) 78] n!6220!6220!6220!6220*(X, Y) >= isPalListKind(X) because n!6220!6220!6220!6220 > isPalListKind and [79], by (Copy) 79] n!6220!6220!6220!6220*(X, Y) >= X because [29], by (Select) 80] n!6220!6220!6220!6220*(X, Y) >= n!6220!6220isPalListKind(Y) because n!6220!6220!6220!6220 > n!6220!6220isPalListKind and [81], by (Copy) 81] n!6220!6220!6220!6220*(X, Y) >= Y because [48], by (Select) 82] isNeList(X) >= U31(isPalListKind(X), X) because [83], by (Star) 83] isNeList*(X) >= U31(isPalListKind(X), X) because isNeList > U31, [84] and [85], by (Copy) 84] isNeList*(X) >= isPalListKind(X) because isNeList > isPalListKind and [85], by (Copy) 85] isNeList*(X) >= X because [23], by (Select) 86] isNeList(n!6220!6220!6220!6220(X, Y)) > U41(and(isPalListKind(X), n!6220!6220isPalListKind(Y)), X, Y) because [87], by definition 87] isNeList*(n!6220!6220!6220!6220(X, Y)) >= U41(and(isPalListKind(X), n!6220!6220isPalListKind(Y)), X, Y) because [88], by (Select) 88] n!6220!6220!6220!6220(X, Y) >= U41(and(isPalListKind(X), n!6220!6220isPalListKind(Y)), X, Y) because [89], by (Star) 89] n!6220!6220!6220!6220*(X, Y) >= U41(and(isPalListKind(X), n!6220!6220isPalListKind(Y)), X, Y) because n!6220!6220!6220!6220 > U41, [77], [79] and [81], by (Copy) 90] isNeList(n!6220!6220!6220!6220(X, Y)) >= U51(and(isPalListKind(X), n!6220!6220isPalListKind(Y)), X, Y) because [91], by (Star) 91] isNeList*(n!6220!6220!6220!6220(X, Y)) >= U51(and(isPalListKind(X), n!6220!6220isPalListKind(Y)), X, Y) because [92], by (Select) 92] n!6220!6220!6220!6220(X, Y) >= U51(and(isPalListKind(X), n!6220!6220isPalListKind(Y)), X, Y) because [93], by (Star) 93] n!6220!6220!6220!6220*(X, Y) >= U51(and(isPalListKind(X), n!6220!6220isPalListKind(Y)), X, Y) because n!6220!6220!6220!6220 > U51, [77], [79] and [81], by (Copy) 94] isNePal(X) > U61(isPalListKind(X), X) because [95], by definition 95] isNePal*(X) >= U61(isPalListKind(X), X) because isNePal > U61, [96] and [97], by (Copy) 96] isNePal*(X) >= isPalListKind(X) because isNePal > isPalListKind and [97], by (Copy) 97] isNePal*(X) >= X because [23], by (Select) 98] isNePal(n!6220!6220!6220!6220(X, n!6220!6220!6220!6220(Y, X))) > and(and(X, n!6220!6220isPalListKind(X)), n!6220!6220and(n!6220!6220isPal(Y), n!6220!6220isPalListKind(Y))) because [99], by definition 99] isNePal*(n!6220!6220!6220!6220(X, n!6220!6220!6220!6220(Y, X))) >= and(and(X, n!6220!6220isPalListKind(X)), n!6220!6220and(n!6220!6220isPal(Y), n!6220!6220isPalListKind(Y))) because [100], by (Select) 100] n!6220!6220!6220!6220(X, n!6220!6220!6220!6220(Y, X)) >= and(and(X, n!6220!6220isPalListKind(X)), n!6220!6220and(n!6220!6220isPal(Y), n!6220!6220isPalListKind(Y))) because [101], by (Star) 101] n!6220!6220!6220!6220*(X, n!6220!6220!6220!6220(Y, X)) >= and(and(X, n!6220!6220isPalListKind(X)), n!6220!6220and(n!6220!6220isPal(Y), n!6220!6220isPalListKind(Y))) because [102], by (Select) 102] n!6220!6220!6220!6220(Y, X) >= and(and(X, n!6220!6220isPalListKind(X)), n!6220!6220and(n!6220!6220isPal(Y), n!6220!6220isPalListKind(Y))) because [103], by (Star) 103] n!6220!6220!6220!6220*(Y, X) >= and(and(X, n!6220!6220isPalListKind(X)), n!6220!6220and(n!6220!6220isPal(Y), n!6220!6220isPalListKind(Y))) because n!6220!6220!6220!6220 > and, [104] and [108], by (Copy) 104] n!6220!6220!6220!6220*(Y, X) >= and(X, n!6220!6220isPalListKind(X)) because n!6220!6220!6220!6220 > and, [105] and [107], by (Copy) 105] n!6220!6220!6220!6220*(Y, X) >= X because [106], by (Select) 106] X >= X by (Meta) 107] n!6220!6220!6220!6220*(Y, X) >= n!6220!6220isPalListKind(X) because n!6220!6220!6220!6220 > n!6220!6220isPalListKind and [105], by (Copy) 108] n!6220!6220!6220!6220*(Y, X) >= n!6220!6220and(n!6220!6220isPal(Y), n!6220!6220isPalListKind(Y)) because n!6220!6220!6220!6220 > n!6220!6220and, [109] and [112], by (Copy) 109] n!6220!6220!6220!6220*(Y, X) >= n!6220!6220isPal(Y) because n!6220!6220!6220!6220 > n!6220!6220isPal and [110], by (Copy) 110] n!6220!6220!6220!6220*(Y, X) >= Y because [111], by (Select) 111] Y >= Y by (Meta) 112] n!6220!6220!6220!6220*(Y, X) >= n!6220!6220isPalListKind(Y) because n!6220!6220!6220!6220 > n!6220!6220isPalListKind and [110], by (Copy) 113] isPal(X) > U71(isPalListKind(X), X) because [114], by definition 114] isPal*(X) >= U71(isPalListKind(X), X) because isPal > U71, [115] and [116], by (Copy) 115] isPal*(X) >= isPalListKind(X) because isPal > isPalListKind and [116], by (Copy) 116] isPal*(X) >= X because [23], by (Select) 117] isPal(_|_) >= _|_ by (Bot) 118] isPalListKind(_|_) >= _|_ by (Bot) 119] isPalListKind(_|_) >= _|_ by (Bot) 120] isPalListKind(_|_) >= _|_ by (Bot) 121] isPalListKind(_|_) >= _|_ by (Bot) 122] isPalListKind(n!6220!6220o) >= _|_ by (Bot) 123] isPalListKind(n!6220!6220u) >= _|_ by (Bot) 124] isPalListKind(n!6220!6220!6220!6220(X, Y)) >= and(isPalListKind(X), n!6220!6220isPalListKind(Y)) because [125], by (Star) 125] isPalListKind*(n!6220!6220!6220!6220(X, Y)) >= and(isPalListKind(X), n!6220!6220isPalListKind(Y)) because [126], by (Select) 126] n!6220!6220!6220!6220(X, Y) >= and(isPalListKind(X), n!6220!6220isPalListKind(Y)) because [77], by (Star) 127] _|_ >= _|_ by (Bot) 128] _|_ >= _|_ by (Bot) 129] _|_ >= _|_ by (Bot) 130] n!6220!6220o > _|_ because [131], by definition 131] n!6220!6220o* >= _|_ by (Bot) 132] n!6220!6220u >= _|_ by (Bot) 133] _|_ >= _|_ by (Bot) 134] !6220!6220(X, Y) >= n!6220!6220!6220!6220(X, Y) because !6220!6220 = n!6220!6220!6220!6220, [135] and [136], by (Fun) 135] X >= X by (Meta) 136] Y >= Y by (Meta) 137] isPalListKind(X) >= n!6220!6220isPalListKind(X) because isPalListKind = n!6220!6220isPalListKind, isPalListKind in Mul and [138], by (Fun) 138] X >= X by (Meta) 139] and(X, Y) >= n!6220!6220and(X, Y) because and = n!6220!6220and, and in Mul, [135] and [136], by (Fun) 140] isPal(X) >= n!6220!6220isPal(X) because isPal = n!6220!6220isPal, isPal in Mul and [138], by (Fun) 141] _|_ >= _|_ by (Bot) 142] _|_ >= _|_ by (Bot) 143] _|_ >= _|_ by (Bot) 144] o >= n!6220!6220o because o = n!6220!6220o, by (Fun) 145] u >= n!6220!6220u because u = n!6220!6220u, by (Fun) 146] _|_ >= _|_ by (Bot) 147] n!6220!6220!6220!6220(X, Y) >= !6220!6220(X, Y) because n!6220!6220!6220!6220 = !6220!6220, [148] and [149], by (Fun) 148] X >= X by (Meta) 149] Y >= Y by (Meta) 150] n!6220!6220isPalListKind(X) >= isPalListKind(X) because n!6220!6220isPalListKind = isPalListKind, n!6220!6220isPalListKind in Mul and [138], by (Fun) 151] n!6220!6220and(X, Y) >= and(X, Y) because n!6220!6220and = and, n!6220!6220and in Mul, [148] and [149], by (Fun) 152] n!6220!6220isPal(X) >= isPal(X) because n!6220!6220isPal = isPal, n!6220!6220isPal in Mul and [138], by (Fun) 153] _|_ >= _|_ by (Bot) 154] _|_ >= _|_ by (Bot) 155] _|_ >= _|_ by (Bot) 156] n!6220!6220o >= o because n!6220!6220o = o, by (Fun) 157] n!6220!6220u >= u because n!6220!6220u = u, by (Fun) 158] 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)) !6220!6220(nil, X) => X U22(tt, X) => U23(isList(activate(X))) U31(tt, X) => U32(isQid(activate(X))) U51(tt, X, Y) => U52(isNeList(activate(X)), activate(Y)) U52(tt, X) => U53(isList(activate(X))) U71(tt, X) => U72(isNePal(activate(X))) isList(X) => U11(isPalListKind(activate(X)), activate(X)) isList(n!6220!6220!6220!6220(X, Y)) => U21(and(isPalListKind(activate(X)), n!6220!6220isPalListKind(activate(Y))), activate(X), activate(Y)) isNeList(n!6220!6220!6220!6220(X, Y)) => U41(and(isPalListKind(activate(X)), n!6220!6220isPalListKind(activate(Y))), 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))) => and(and(isQid(activate(X)), n!6220!6220isPalListKind(activate(X))), n!6220!6220and(n!6220!6220isPal(activate(Y)), n!6220!6220isPalListKind(activate(Y)))) isPal(X) => U71(isPalListKind(activate(X)), activate(X)) 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(X, nil) >? X U11(tt, X) >? U12(isNeList(activate(X))) U12(tt) >? tt U21(tt, X, Y) >? U22(isList(activate(X)), activate(Y)) U23(tt) >? tt U32(tt) >? tt U41(tt, X, Y) >? U42(isList(activate(X)), activate(Y)) U42(tt, X) >? U43(isNeList(activate(X))) U43(tt) >? tt U53(tt) >? tt U61(tt, X) >? U62(isQid(activate(X))) U62(tt) >? tt U72(tt) >? tt and(tt, X) >? activate(X) isList(n!6220!6220nil) >? tt isNeList(X) >? U31(isPalListKind(activate(X)), activate(X)) isNeList(n!6220!6220!6220!6220(X, Y)) >? U51(and(isPalListKind(activate(X)), n!6220!6220isPalListKind(activate(Y))), activate(X), activate(Y)) 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)) >? and(isPalListKind(activate(X)), n!6220!6220isPalListKind(activate(Y))) isQid(n!6220!6220a) >? tt isQid(n!6220!6220e) >? tt isQid(n!6220!6220i) >? tt isQid(n!6220!6220u) >? tt nil >? n!6220!6220nil !6220!6220(X, Y) >? n!6220!6220!6220!6220(X, Y) isPalListKind(X) >? n!6220!6220isPalListKind(X) and(X, Y) >? n!6220!6220and(X, Y) isPal(X) >? n!6220!6220isPal(X) 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!6220isPalListKind(X)) >? isPalListKind(X) activate(n!6220!6220and(X, Y)) >? and(activate(X), Y) activate(n!6220!6220isPal(X)) >? isPal(X) 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.1 + y1 + 2y0 U11 = \y0y1.3 + 3y0 + 3y1 U12 = \y0.y0 U21 = \y0y1y2.3 + 3y0 + 3y1 + 3y2 U22 = \y0y1.y0 + y1 U23 = \y0.3 + 3y0 U31 = \y0y1.y0 + y1 U32 = \y0.3 + 3y0 U41 = \y0y1y2.3 + 3y0 + 3y1 + 3y2 U42 = \y0y1.1 + y0 + 2y1 U43 = \y0.y0 U51 = \y0y1y2.y0 + y1 + y2 U53 = \y0.3 + 3y0 U61 = \y0y1.3 + 3y0 + 3y1 U62 = \y0.y0 U72 = \y0.3 + 3y0 a = 0 activate = \y0.y0 and = \y0y1.y1 + 2y0 e = 0 i = 0 isList = \y0.y0 isNeList = \y0.2y0 isPal = \y0.y0 isPalListKind = \y0.y0 isQid = \y0.y0 n!6220!6220!6220!6220 = \y0y1.1 + y1 + 2y0 n!6220!6220a = 0 n!6220!6220and = \y0y1.y1 + 2y0 n!6220!6220e = 0 n!6220!6220i = 0 n!6220!6220isPal = \y0.y0 n!6220!6220isPalListKind = \y0.y0 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(_x0, nil)]] = 1 + 2x0 > x0 = [[_x0]] [[U11(tt, _x0)]] = 3 + 3x0 > 2x0 = [[U12(isNeList(activate(_x0)))]] [[U12(tt)]] = 0 >= 0 = [[tt]] [[U21(tt, _x0, _x1)]] = 3 + 3x0 + 3x1 > x0 + x1 = [[U22(isList(activate(_x0)), activate(_x1))]] [[U23(tt)]] = 3 > 0 = [[tt]] [[U32(tt)]] = 3 > 0 = [[tt]] [[U41(tt, _x0, _x1)]] = 3 + 3x0 + 3x1 > 1 + x0 + 2x1 = [[U42(isList(activate(_x0)), activate(_x1))]] [[U42(tt, _x0)]] = 1 + 2x0 > 2x0 = [[U43(isNeList(activate(_x0)))]] [[U43(tt)]] = 0 >= 0 = [[tt]] [[U53(tt)]] = 3 > 0 = [[tt]] [[U61(tt, _x0)]] = 3 + 3x0 > x0 = [[U62(isQid(activate(_x0)))]] [[U62(tt)]] = 0 >= 0 = [[tt]] [[U72(tt)]] = 3 > 0 = [[tt]] [[and(tt, _x0)]] = x0 >= x0 = [[activate(_x0)]] [[isList(n!6220!6220nil)]] = 0 >= 0 = [[tt]] [[isNeList(_x0)]] = 2x0 >= 2x0 = [[U31(isPalListKind(activate(_x0)), activate(_x0))]] [[isNeList(n!6220!6220!6220!6220(_x0, _x1))]] = 2 + 2x1 + 4x0 > 2x1 + 3x0 = [[U51(and(isPalListKind(activate(_x0)), n!6220!6220isPalListKind(activate(_x1))), activate(_x0), activate(_x1))]] [[isPal(n!6220!6220nil)]] = 0 >= 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)]] = 1 > 0 = [[tt]] [[isPalListKind(n!6220!6220!6220!6220(_x0, _x1))]] = 1 + x1 + 2x0 > x1 + 2x0 = [[and(isPalListKind(activate(_x0)), n!6220!6220isPalListKind(activate(_x1)))]] [[isQid(n!6220!6220a)]] = 0 >= 0 = [[tt]] [[isQid(n!6220!6220e)]] = 0 >= 0 = [[tt]] [[isQid(n!6220!6220i)]] = 0 >= 0 = [[tt]] [[isQid(n!6220!6220u)]] = 1 > 0 = [[tt]] [[nil]] = 0 >= 0 = [[n!6220!6220nil]] [[!6220!6220(_x0, _x1)]] = 1 + x1 + 2x0 >= 1 + x1 + 2x0 = [[n!6220!6220!6220!6220(_x0, _x1)]] [[isPalListKind(_x0)]] = x0 >= x0 = [[n!6220!6220isPalListKind(_x0)]] [[and(_x0, _x1)]] = x1 + 2x0 >= x1 + 2x0 = [[n!6220!6220and(_x0, _x1)]] [[isPal(_x0)]] = x0 >= x0 = [[n!6220!6220isPal(_x0)]] [[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]] = 1 >= 1 = [[n!6220!6220u]] [[activate(n!6220!6220nil)]] = 0 >= 0 = [[nil]] [[activate(n!6220!6220!6220!6220(_x0, _x1))]] = 1 + x1 + 2x0 >= 1 + x1 + 2x0 = [[!6220!6220(activate(_x0), activate(_x1))]] [[activate(n!6220!6220isPalListKind(_x0))]] = x0 >= x0 = [[isPalListKind(_x0)]] [[activate(n!6220!6220and(_x0, _x1))]] = x1 + 2x0 >= x1 + 2x0 = [[and(activate(_x0), _x1)]] [[activate(n!6220!6220isPal(_x0))]] = x0 >= x0 = [[isPal(_x0)]] [[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)]] = 1 >= 1 = [[u]] [[activate(_x0)]] = x0 >= x0 = [[_x0]] We can thus remove the following rules: !6220!6220(X, nil) => X U11(tt, X) => U12(isNeList(activate(X))) U21(tt, X, Y) => U22(isList(activate(X)), activate(Y)) U23(tt) => tt U32(tt) => tt U41(tt, X, Y) => U42(isList(activate(X)), activate(Y)) U42(tt, X) => U43(isNeList(activate(X))) U53(tt) => tt U61(tt, X) => U62(isQid(activate(X))) U72(tt) => tt isNeList(n!6220!6220!6220!6220(X, Y)) => U51(and(isPalListKind(activate(X)), n!6220!6220isPalListKind(activate(Y))), activate(X), activate(Y)) isPalListKind(n!6220!6220u) => tt isPalListKind(n!6220!6220!6220!6220(X, Y)) => and(isPalListKind(activate(X)), n!6220!6220isPalListKind(activate(Y))) 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]): U12(tt) >? tt U43(tt) >? tt U62(tt) >? tt and(tt, X) >? activate(X) isList(n!6220!6220nil) >? tt isNeList(X) >? U31(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 isQid(n!6220!6220a) >? tt isQid(n!6220!6220e) >? tt isQid(n!6220!6220i) >? tt nil >? n!6220!6220nil !6220!6220(X, Y) >? n!6220!6220!6220!6220(X, Y) isPalListKind(X) >? n!6220!6220isPalListKind(X) and(X, Y) >? n!6220!6220and(X, Y) isPal(X) >? n!6220!6220isPal(X) 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!6220isPalListKind(X)) >? isPalListKind(X) activate(n!6220!6220and(X, Y)) >? and(activate(X), Y) activate(n!6220!6220isPal(X)) >? isPal(X) 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 U12 = \y0.3 + 3y0 U31 = \y0y1.y0 + y1 U43 = \y0.3 + 3y0 U62 = \y0.3 + 3y0 a = 0 activate = \y0.y0 and = \y0y1.1 + y0 + y1 e = 0 i = 0 isList = \y0.3 + 3y0 isNeList = \y0.3 + 3y0 isPal = \y0.2y0 isPalListKind = \y0.y0 isQid = \y0.3 + 3y0 n!6220!6220!6220!6220 = \y0y1.y1 + 2y0 n!6220!6220a = 0 n!6220!6220and = \y0y1.1 + y0 + y1 n!6220!6220e = 0 n!6220!6220i = 0 n!6220!6220isPal = \y0.2y0 n!6220!6220isPalListKind = \y0.y0 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: [[U12(tt)]] = 3 > 0 = [[tt]] [[U43(tt)]] = 3 > 0 = [[tt]] [[U62(tt)]] = 3 > 0 = [[tt]] [[and(tt, _x0)]] = 1 + x0 > x0 = [[activate(_x0)]] [[isList(n!6220!6220nil)]] = 3 > 0 = [[tt]] [[isNeList(_x0)]] = 3 + 3x0 > 2x0 = [[U31(isPalListKind(activate(_x0)), activate(_x0))]] [[isPal(n!6220!6220nil)]] = 0 >= 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]] [[isQid(n!6220!6220a)]] = 3 > 0 = [[tt]] [[isQid(n!6220!6220e)]] = 3 > 0 = [[tt]] [[isQid(n!6220!6220i)]] = 3 > 0 = [[tt]] [[nil]] = 0 >= 0 = [[n!6220!6220nil]] [[!6220!6220(_x0, _x1)]] = x1 + 2x0 >= x1 + 2x0 = [[n!6220!6220!6220!6220(_x0, _x1)]] [[isPalListKind(_x0)]] = x0 >= x0 = [[n!6220!6220isPalListKind(_x0)]] [[and(_x0, _x1)]] = 1 + x0 + x1 >= 1 + x0 + x1 = [[n!6220!6220and(_x0, _x1)]] [[isPal(_x0)]] = 2x0 >= 2x0 = [[n!6220!6220isPal(_x0)]] [[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!6220isPalListKind(_x0))]] = x0 >= x0 = [[isPalListKind(_x0)]] [[activate(n!6220!6220and(_x0, _x1))]] = 1 + x0 + x1 >= 1 + x0 + x1 = [[and(activate(_x0), _x1)]] [[activate(n!6220!6220isPal(_x0))]] = 2x0 >= 2x0 = [[isPal(_x0)]] [[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: U12(tt) => tt U43(tt) => tt U62(tt) => tt and(tt, X) => activate(X) isList(n!6220!6220nil) => tt isNeList(X) => U31(isPalListKind(activate(X)), activate(X)) isQid(n!6220!6220a) => tt isQid(n!6220!6220e) => tt isQid(n!6220!6220i) => 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]): 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 nil >? n!6220!6220nil !6220!6220(X, Y) >? n!6220!6220!6220!6220(X, Y) isPalListKind(X) >? n!6220!6220isPalListKind(X) and(X, Y) >? n!6220!6220and(X, Y) isPal(X) >? n!6220!6220isPal(X) 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!6220isPalListKind(X)) >? isPalListKind(X) activate(n!6220!6220and(X, Y)) >? and(activate(X), Y) activate(n!6220!6220isPal(X)) >? isPal(X) 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 = 0 activate = \y0.y0 and = \y0y1.y0 + y1 e = 0 i = 0 isPal = \y0.y0 isPalListKind = \y0.1 + 2y0 n!6220!6220!6220!6220 = \y0y1.y0 + 2y1 n!6220!6220a = 0 n!6220!6220and = \y0y1.y0 + y1 n!6220!6220e = 0 n!6220!6220i = 0 n!6220!6220isPal = \y0.y0 n!6220!6220isPalListKind = \y0.1 + 2y0 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: [[isPal(n!6220!6220nil)]] = 0 >= 0 = [[tt]] [[isPalListKind(n!6220!6220a)]] = 1 > 0 = [[tt]] [[isPalListKind(n!6220!6220e)]] = 1 > 0 = [[tt]] [[isPalListKind(n!6220!6220i)]] = 1 > 0 = [[tt]] [[isPalListKind(n!6220!6220nil)]] = 1 > 0 = [[tt]] [[isPalListKind(n!6220!6220o)]] = 1 > 0 = [[tt]] [[nil]] = 0 >= 0 = [[n!6220!6220nil]] [[!6220!6220(_x0, _x1)]] = x0 + 2x1 >= x0 + 2x1 = [[n!6220!6220!6220!6220(_x0, _x1)]] [[isPalListKind(_x0)]] = 1 + 2x0 >= 1 + 2x0 = [[n!6220!6220isPalListKind(_x0)]] [[and(_x0, _x1)]] = x0 + x1 >= x0 + x1 = [[n!6220!6220and(_x0, _x1)]] [[isPal(_x0)]] = x0 >= x0 = [[n!6220!6220isPal(_x0)]] [[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]] = 1 >= 1 = [[n!6220!6220u]] [[activate(n!6220!6220nil)]] = 0 >= 0 = [[nil]] [[activate(n!6220!6220!6220!6220(_x0, _x1))]] = x0 + 2x1 >= x0 + 2x1 = [[!6220!6220(activate(_x0), activate(_x1))]] [[activate(n!6220!6220isPalListKind(_x0))]] = 1 + 2x0 >= 1 + 2x0 = [[isPalListKind(_x0)]] [[activate(n!6220!6220and(_x0, _x1))]] = x0 + x1 >= x0 + x1 = [[and(activate(_x0), _x1)]] [[activate(n!6220!6220isPal(_x0))]] = x0 >= x0 = [[isPal(_x0)]] [[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)]] = 1 >= 1 = [[u]] [[activate(_x0)]] = x0 >= x0 = [[_x0]] We can thus remove the following rules: 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 We use rule removal, following [Kop12, Theorem 2.23]. This gives the following requirements (possibly using Theorems 2.25 and 2.26 in [Kop12]): isPal(n!6220!6220nil) >? tt nil >? n!6220!6220nil !6220!6220(X, Y) >? n!6220!6220!6220!6220(X, Y) isPalListKind(X) >? n!6220!6220isPalListKind(X) and(X, Y) >? n!6220!6220and(X, Y) isPal(X) >? n!6220!6220isPal(X) 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!6220isPalListKind(X)) >? isPalListKind(X) activate(n!6220!6220and(X, Y)) >? and(activate(X), Y) activate(n!6220!6220isPal(X)) >? isPal(X) 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 a = 0 activate = \y0.y0 and = \y0y1.y1 + 2y0 e = 0 i = 0 isPal = \y0.1 + y0 isPalListKind = \y0.y0 n!6220!6220!6220!6220 = \y0y1.2y0 + 2y1 n!6220!6220a = 0 n!6220!6220and = \y0y1.y1 + 2y0 n!6220!6220e = 0 n!6220!6220i = 0 n!6220!6220isPal = \y0.1 + y0 n!6220!6220isPalListKind = \y0.y0 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: [[isPal(n!6220!6220nil)]] = 1 > 0 = [[tt]] [[nil]] = 0 >= 0 = [[n!6220!6220nil]] [[!6220!6220(_x0, _x1)]] = 2x0 + 2x1 >= 2x0 + 2x1 = [[n!6220!6220!6220!6220(_x0, _x1)]] [[isPalListKind(_x0)]] = x0 >= x0 = [[n!6220!6220isPalListKind(_x0)]] [[and(_x0, _x1)]] = x1 + 2x0 >= x1 + 2x0 = [[n!6220!6220and(_x0, _x1)]] [[isPal(_x0)]] = 1 + x0 >= 1 + x0 = [[n!6220!6220isPal(_x0)]] [[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))]] = 2x0 + 2x1 >= 2x0 + 2x1 = [[!6220!6220(activate(_x0), activate(_x1))]] [[activate(n!6220!6220isPalListKind(_x0))]] = x0 >= x0 = [[isPalListKind(_x0)]] [[activate(n!6220!6220and(_x0, _x1))]] = x1 + 2x0 >= x1 + 2x0 = [[and(activate(_x0), _x1)]] [[activate(n!6220!6220isPal(_x0))]] = 1 + x0 >= 1 + x0 = [[isPal(_x0)]] [[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: 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]): nil >? n!6220!6220nil !6220!6220(X, Y) >? n!6220!6220!6220!6220(X, Y) isPalListKind(X) >? n!6220!6220isPalListKind(X) and(X, Y) >? n!6220!6220and(X, Y) isPal(X) >? n!6220!6220isPal(X) 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!6220isPalListKind(X)) >? isPalListKind(X) activate(n!6220!6220and(X, Y)) >? and(activate(X), Y) activate(n!6220!6220isPal(X)) >? isPal(X) 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 a = 0 activate = \y0.2y0 and = \y0y1.2y0 + 2y1 e = 0 i = 0 isPal = \y0.3 + 2y0 isPalListKind = \y0.2y0 n!6220!6220!6220!6220 = \y0y1.2y0 + 2y1 n!6220!6220a = 0 n!6220!6220and = \y0y1.y1 + 2y0 n!6220!6220e = 0 n!6220!6220i = 0 n!6220!6220isPal = \y0.2 + 2y0 n!6220!6220isPalListKind = \y0.2y0 n!6220!6220nil = 0 n!6220!6220o = 0 n!6220!6220u = 0 nil = 0 o = 0 u = 0 Using this interpretation, the requirements translate to: [[nil]] = 0 >= 0 = [[n!6220!6220nil]] [[!6220!6220(_x0, _x1)]] = 2x0 + 2x1 >= 2x0 + 2x1 = [[n!6220!6220!6220!6220(_x0, _x1)]] [[isPalListKind(_x0)]] = 2x0 >= 2x0 = [[n!6220!6220isPalListKind(_x0)]] [[and(_x0, _x1)]] = 2x0 + 2x1 >= x1 + 2x0 = [[n!6220!6220and(_x0, _x1)]] [[isPal(_x0)]] = 3 + 2x0 > 2 + 2x0 = [[n!6220!6220isPal(_x0)]] [[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))]] = 4x0 + 4x1 >= 4x0 + 4x1 = [[!6220!6220(activate(_x0), activate(_x1))]] [[activate(n!6220!6220isPalListKind(_x0))]] = 4x0 >= 2x0 = [[isPalListKind(_x0)]] [[activate(n!6220!6220and(_x0, _x1))]] = 2x1 + 4x0 >= 2x1 + 4x0 = [[and(activate(_x0), _x1)]] [[activate(n!6220!6220isPal(_x0))]] = 4 + 4x0 > 3 + 2x0 = [[isPal(_x0)]] [[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: isPal(X) => n!6220!6220isPal(X) activate(n!6220!6220isPal(X)) => isPal(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]): nil >? n!6220!6220nil !6220!6220(X, Y) >? n!6220!6220!6220!6220(X, Y) isPalListKind(X) >? n!6220!6220isPalListKind(X) and(X, Y) >? n!6220!6220and(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!6220isPalListKind(X)) >? isPalListKind(X) activate(n!6220!6220and(X, Y)) >? and(activate(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 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 and = \y0y1.y1 + 2y0 e = 0 i = 0 isPalListKind = \y0.y0 n!6220!6220!6220!6220 = \y0y1.y0 + y1 n!6220!6220a = 0 n!6220!6220and = \y0y1.y1 + 2y0 n!6220!6220e = 0 n!6220!6220i = 0 n!6220!6220isPalListKind = \y0.y0 n!6220!6220nil = 0 n!6220!6220o = 0 n!6220!6220u = 1 nil = 0 o = 0 u = 2 Using this interpretation, the requirements translate to: [[nil]] = 0 >= 0 = [[n!6220!6220nil]] [[!6220!6220(_x0, _x1)]] = x0 + x1 >= x0 + x1 = [[n!6220!6220!6220!6220(_x0, _x1)]] [[isPalListKind(_x0)]] = x0 >= x0 = [[n!6220!6220isPalListKind(_x0)]] [[and(_x0, _x1)]] = x1 + 2x0 >= x1 + 2x0 = [[n!6220!6220and(_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]] = 2 > 1 = [[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!6220isPalListKind(_x0))]] = 2x0 >= x0 = [[isPalListKind(_x0)]] [[activate(n!6220!6220and(_x0, _x1))]] = 2x1 + 4x0 >= x1 + 4x0 = [[and(activate(_x0), _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)]] = 2 >= 2 = [[u]] [[activate(_x0)]] = 2x0 >= x0 = [[_x0]] We can thus remove the following rules: u => n!6220!6220u 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) isPalListKind(X) >? n!6220!6220isPalListKind(X) and(X, Y) >? n!6220!6220and(X, Y) a >? n!6220!6220a e >? n!6220!6220e i >? n!6220!6220i o >? n!6220!6220o activate(n!6220!6220nil) >? nil activate(n!6220!6220!6220!6220(X, Y)) >? !6220!6220(activate(X), activate(Y)) activate(n!6220!6220isPalListKind(X)) >? isPalListKind(X) activate(n!6220!6220and(X, Y)) >? and(activate(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 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 and = \y0y1.y1 + 2y0 e = 0 i = 0 isPalListKind = \y0.y0 n!6220!6220!6220!6220 = \y0y1.y0 + y1 n!6220!6220a = 0 n!6220!6220and = \y0y1.y1 + 2y0 n!6220!6220e = 0 n!6220!6220i = 0 n!6220!6220isPalListKind = \y0.y0 n!6220!6220nil = 0 n!6220!6220o = 0 n!6220!6220u = 3 nil = 0 o = 0 u = 0 Using this interpretation, the requirements translate to: [[nil]] = 0 >= 0 = [[n!6220!6220nil]] [[!6220!6220(_x0, _x1)]] = x0 + x1 >= x0 + x1 = [[n!6220!6220!6220!6220(_x0, _x1)]] [[isPalListKind(_x0)]] = x0 >= x0 = [[n!6220!6220isPalListKind(_x0)]] [[and(_x0, _x1)]] = x1 + 2x0 >= x1 + 2x0 = [[n!6220!6220and(_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]] [[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!6220isPalListKind(_x0))]] = x0 >= x0 = [[isPalListKind(_x0)]] [[activate(n!6220!6220and(_x0, _x1))]] = x1 + 2x0 >= x1 + 2x0 = [[and(activate(_x0), _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)]] = 3 > 0 = [[u]] [[activate(_x0)]] = x0 >= x0 = [[_x0]] We can thus remove the following rules: 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 !6220!6220(X, Y) >? n!6220!6220!6220!6220(X, Y) isPalListKind(X) >? n!6220!6220isPalListKind(X) and(X, Y) >? n!6220!6220and(X, Y) a >? n!6220!6220a e >? n!6220!6220e i >? n!6220!6220i o >? n!6220!6220o activate(n!6220!6220nil) >? nil activate(n!6220!6220!6220!6220(X, Y)) >? !6220!6220(activate(X), activate(Y)) activate(n!6220!6220isPalListKind(X)) >? isPalListKind(X) activate(n!6220!6220and(X, Y)) >? and(activate(X), Y) activate(n!6220!6220a) >? a activate(n!6220!6220e) >? e activate(n!6220!6220i) >? i activate(n!6220!6220o) >? o 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 and = \y0y1.y0 + 2y1 e = 0 i = 0 isPalListKind = \y0.3 + 2y0 n!6220!6220!6220!6220 = \y0y1.y0 + y1 n!6220!6220a = 0 n!6220!6220and = \y0y1.y0 + 2y1 n!6220!6220e = 0 n!6220!6220i = 0 n!6220!6220isPalListKind = \y0.2 + 2y0 n!6220!6220nil = 0 n!6220!6220o = 0 nil = 0 o = 0 Using this interpretation, the requirements translate to: [[nil]] = 0 >= 0 = [[n!6220!6220nil]] [[!6220!6220(_x0, _x1)]] = x0 + x1 >= x0 + x1 = [[n!6220!6220!6220!6220(_x0, _x1)]] [[isPalListKind(_x0)]] = 3 + 2x0 > 2 + 2x0 = [[n!6220!6220isPalListKind(_x0)]] [[and(_x0, _x1)]] = x0 + 2x1 >= x0 + 2x1 = [[n!6220!6220and(_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]] [[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!6220isPalListKind(_x0))]] = 4 + 4x0 > 3 + 2x0 = [[isPalListKind(_x0)]] [[activate(n!6220!6220and(_x0, _x1))]] = 2x0 + 4x1 >= 2x0 + 2x1 = [[and(activate(_x0), _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(_x0)]] = 2x0 >= x0 = [[_x0]] We can thus remove the following rules: isPalListKind(X) => n!6220!6220isPalListKind(X) activate(n!6220!6220isPalListKind(X)) => isPalListKind(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]): nil >? n!6220!6220nil !6220!6220(X, Y) >? n!6220!6220!6220!6220(X, Y) and(X, Y) >? n!6220!6220and(X, Y) a >? n!6220!6220a e >? n!6220!6220e i >? n!6220!6220i o >? n!6220!6220o activate(n!6220!6220nil) >? nil activate(n!6220!6220!6220!6220(X, Y)) >? !6220!6220(activate(X), activate(Y)) activate(n!6220!6220and(X, Y)) >? and(activate(X), Y) activate(n!6220!6220a) >? a activate(n!6220!6220e) >? e activate(n!6220!6220i) >? i activate(n!6220!6220o) >? o activate(X) >? X We orient these requirements with a polynomial interpretation in the natural numbers. The following interpretation satisfies the requirements: !6220!6220 = \y0y1.3 + y0 + y1 a = 0 activate = \y0.2y0 and = \y0y1.2y0 + 2y1 e = 0 i = 0 n!6220!6220!6220!6220 = \y0y1.2 + y0 + y1 n!6220!6220a = 0 n!6220!6220and = \y0y1.2y0 + 2y1 n!6220!6220e = 0 n!6220!6220i = 0 n!6220!6220nil = 1 n!6220!6220o = 0 nil = 1 o = 0 Using this interpretation, the requirements translate to: [[nil]] = 1 >= 1 = [[n!6220!6220nil]] [[!6220!6220(_x0, _x1)]] = 3 + x0 + x1 > 2 + x0 + x1 = [[n!6220!6220!6220!6220(_x0, _x1)]] [[and(_x0, _x1)]] = 2x0 + 2x1 >= 2x0 + 2x1 = [[n!6220!6220and(_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]] [[activate(n!6220!6220nil)]] = 2 > 1 = [[nil]] [[activate(n!6220!6220!6220!6220(_x0, _x1))]] = 4 + 2x0 + 2x1 > 3 + 2x0 + 2x1 = [[!6220!6220(activate(_x0), activate(_x1))]] [[activate(n!6220!6220and(_x0, _x1))]] = 4x0 + 4x1 >= 2x1 + 4x0 = [[and(activate(_x0), _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(_x0)]] = 2x0 >= x0 = [[_x0]] We can thus remove the following rules: !6220!6220(X, Y) => n!6220!6220!6220!6220(X, Y) activate(n!6220!6220nil) => nil 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]): nil >? n!6220!6220nil and(X, Y) >? n!6220!6220and(X, Y) a >? n!6220!6220a e >? n!6220!6220e i >? n!6220!6220i o >? n!6220!6220o activate(n!6220!6220and(X, Y)) >? and(activate(X), Y) activate(n!6220!6220a) >? a activate(n!6220!6220e) >? e activate(n!6220!6220i) >? i activate(n!6220!6220o) >? o activate(X) >? X We orient these requirements with a polynomial interpretation in the natural numbers. The following interpretation satisfies the requirements: a = 0 activate = \y0.2 + y0 and = \y0y1.y0 + 2y1 e = 0 i = 1 n!6220!6220a = 0 n!6220!6220and = \y0y1.y0 + 2y1 n!6220!6220e = 0 n!6220!6220i = 0 n!6220!6220nil = 0 n!6220!6220o = 0 nil = 3 o = 0 Using this interpretation, the requirements translate to: [[nil]] = 3 > 0 = [[n!6220!6220nil]] [[and(_x0, _x1)]] = x0 + 2x1 >= x0 + 2x1 = [[n!6220!6220and(_x0, _x1)]] [[a]] = 0 >= 0 = [[n!6220!6220a]] [[e]] = 0 >= 0 = [[n!6220!6220e]] [[i]] = 1 > 0 = [[n!6220!6220i]] [[o]] = 0 >= 0 = [[n!6220!6220o]] [[activate(n!6220!6220and(_x0, _x1))]] = 2 + x0 + 2x1 >= 2 + x0 + 2x1 = [[and(activate(_x0), _x1)]] [[activate(n!6220!6220a)]] = 2 > 0 = [[a]] [[activate(n!6220!6220e)]] = 2 > 0 = [[e]] [[activate(n!6220!6220i)]] = 2 > 1 = [[i]] [[activate(n!6220!6220o)]] = 2 > 0 = [[o]] [[activate(_x0)]] = 2 + x0 > x0 = [[_x0]] We can thus remove the following rules: nil => n!6220!6220nil i => n!6220!6220i activate(n!6220!6220a) => a activate(n!6220!6220e) => e activate(n!6220!6220i) => i activate(n!6220!6220o) => o 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]): and(X, Y) >? n!6220!6220and(X, Y) a >? n!6220!6220a e >? n!6220!6220e o >? n!6220!6220o activate(n!6220!6220and(X, Y)) >? and(activate(X), Y) We orient these requirements with a polynomial interpretation in the natural numbers. The following interpretation satisfies the requirements: a = 3 activate = \y0.y0 and = \y0y1.2y0 + 2y1 e = 3 n!6220!6220a = 0 n!6220!6220and = \y0y1.2y0 + 2y1 n!6220!6220e = 0 n!6220!6220o = 0 o = 3 Using this interpretation, the requirements translate to: [[and(_x0, _x1)]] = 2x0 + 2x1 >= 2x0 + 2x1 = [[n!6220!6220and(_x0, _x1)]] [[a]] = 3 > 0 = [[n!6220!6220a]] [[e]] = 3 > 0 = [[n!6220!6220e]] [[o]] = 3 > 0 = [[n!6220!6220o]] [[activate(n!6220!6220and(_x0, _x1))]] = 2x0 + 2x1 >= 2x0 + 2x1 = [[and(activate(_x0), _x1)]] We can thus remove the following rules: a => n!6220!6220a e => n!6220!6220e o => n!6220!6220o We use rule removal, following [Kop12, Theorem 2.23]. This gives the following requirements (possibly using Theorems 2.25 and 2.26 in [Kop12]): and(X, Y) >? n!6220!6220and(X, Y) activate(n!6220!6220and(X, Y)) >? and(activate(X), Y) We orient these requirements with a polynomial interpretation in the natural numbers. The following interpretation satisfies the requirements: activate = \y0.2y0 and = \y0y1.2 + 2y0 + 2y1 n!6220!6220and = \y0y1.1 + y1 + 2y0 Using this interpretation, the requirements translate to: [[and(_x0, _x1)]] = 2 + 2x0 + 2x1 > 1 + x1 + 2x0 = [[n!6220!6220and(_x0, _x1)]] [[activate(n!6220!6220and(_x0, _x1))]] = 2 + 2x1 + 4x0 >= 2 + 2x1 + 4x0 = [[and(activate(_x0), _x1)]] We can thus remove the following rules: and(X, Y) => n!6220!6220and(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!6220and(X, Y)) >? and(activate(X), Y) We orient these requirements with a polynomial interpretation in the natural numbers. The following interpretation satisfies the requirements: activate = \y0.3y0 and = \y0y1.y0 + y1 n!6220!6220and = \y0y1.3 + 3y0 + 3y1 Using this interpretation, the requirements translate to: [[activate(n!6220!6220and(_x0, _x1))]] = 9 + 9x0 + 9x1 > x1 + 3x0 = [[and(activate(_x0), _x1)]] We can thus remove the following rules: activate(n!6220!6220and(X, Y)) => and(activate(X), Y) All rules were succesfully removed. Thus, termination of the original system has been reduced to termination of the beta-rule, which is well-known to hold. +++ Citations +++ [Kop12] C. Kop. Higher Order Termination. PhD Thesis, 2012.