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