/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 U21 : [o * o] --> o U22 : [o] --> o U31 : [o] --> o U41 : [o * o] --> o U42 : [o] --> o U51 : [o * o] --> o U52 : [o] --> o U61 : [o] --> o U71 : [o * o] --> o U72 : [o] --> o U81 : [o] --> o a : [] --> o active : [o] --> o e : [] --> o i : [] --> o isList : [o] --> o isNeList : [o] --> o isNePal : [o] --> o isPal : [o] --> o isQid : [o] --> o mark : [o] --> o nil : [] --> o o : [] --> o tt : [] --> o u : [] --> o active(!6220!6220(!6220!6220(X, Y), Z)) => mark(!6220!6220(X, !6220!6220(Y, Z))) active(!6220!6220(X, nil)) => mark(X) active(!6220!6220(nil, X)) => mark(X) active(U11(tt)) => mark(tt) active(U21(tt, X)) => mark(U22(isList(X))) active(U22(tt)) => mark(tt) active(U31(tt)) => mark(tt) active(U41(tt, X)) => mark(U42(isNeList(X))) active(U42(tt)) => mark(tt) active(U51(tt, X)) => mark(U52(isList(X))) active(U52(tt)) => mark(tt) active(U61(tt)) => mark(tt) active(U71(tt, X)) => mark(U72(isPal(X))) active(U72(tt)) => mark(tt) active(U81(tt)) => mark(tt) active(isList(X)) => mark(U11(isNeList(X))) active(isList(nil)) => mark(tt) active(isList(!6220!6220(X, Y))) => mark(U21(isList(X), Y)) active(isNeList(X)) => mark(U31(isQid(X))) active(isNeList(!6220!6220(X, Y))) => mark(U41(isList(X), Y)) active(isNeList(!6220!6220(X, Y))) => mark(U51(isNeList(X), Y)) active(isNePal(X)) => mark(U61(isQid(X))) active(isNePal(!6220!6220(X, !6220!6220(Y, X)))) => mark(U71(isQid(X), Y)) active(isPal(X)) => mark(U81(isNePal(X))) active(isPal(nil)) => mark(tt) active(isQid(a)) => mark(tt) active(isQid(e)) => mark(tt) active(isQid(i)) => mark(tt) active(isQid(o)) => mark(tt) active(isQid(u)) => mark(tt) mark(!6220!6220(X, Y)) => active(!6220!6220(mark(X), mark(Y))) mark(nil) => active(nil) mark(U11(X)) => active(U11(mark(X))) mark(tt) => active(tt) mark(U21(X, Y)) => active(U21(mark(X), Y)) mark(U22(X)) => active(U22(mark(X))) mark(isList(X)) => active(isList(X)) mark(U31(X)) => active(U31(mark(X))) mark(U41(X, Y)) => active(U41(mark(X), Y)) mark(U42(X)) => active(U42(mark(X))) mark(isNeList(X)) => active(isNeList(X)) mark(U51(X, Y)) => active(U51(mark(X), Y)) mark(U52(X)) => active(U52(mark(X))) mark(U61(X)) => active(U61(mark(X))) mark(U71(X, Y)) => active(U71(mark(X), Y)) mark(U72(X)) => active(U72(mark(X))) mark(isPal(X)) => active(isPal(X)) mark(U81(X)) => active(U81(mark(X))) mark(isQid(X)) => active(isQid(X)) mark(isNePal(X)) => active(isNePal(X)) mark(a) => active(a) mark(e) => active(e) mark(i) => active(i) mark(o) => active(o) mark(u) => active(u) !6220!6220(mark(X), Y) => !6220!6220(X, Y) !6220!6220(X, mark(Y)) => !6220!6220(X, Y) !6220!6220(active(X), Y) => !6220!6220(X, Y) !6220!6220(X, active(Y)) => !6220!6220(X, Y) U11(mark(X)) => U11(X) U11(active(X)) => U11(X) U21(mark(X), Y) => U21(X, Y) U21(X, mark(Y)) => U21(X, Y) U21(active(X), Y) => U21(X, Y) U21(X, active(Y)) => U21(X, Y) U22(mark(X)) => U22(X) U22(active(X)) => U22(X) isList(mark(X)) => isList(X) isList(active(X)) => isList(X) U31(mark(X)) => U31(X) U31(active(X)) => U31(X) U41(mark(X), Y) => U41(X, Y) U41(X, mark(Y)) => U41(X, Y) U41(active(X), Y) => U41(X, Y) U41(X, active(Y)) => U41(X, Y) U42(mark(X)) => U42(X) U42(active(X)) => U42(X) isNeList(mark(X)) => isNeList(X) isNeList(active(X)) => isNeList(X) U51(mark(X), Y) => U51(X, Y) U51(X, mark(Y)) => U51(X, Y) U51(active(X), Y) => U51(X, Y) U51(X, active(Y)) => U51(X, Y) U52(mark(X)) => U52(X) U52(active(X)) => U52(X) U61(mark(X)) => U61(X) U61(active(X)) => U61(X) U71(mark(X), Y) => U71(X, Y) U71(X, mark(Y)) => U71(X, Y) U71(active(X), Y) => U71(X, Y) U71(X, active(Y)) => U71(X, Y) U72(mark(X)) => U72(X) U72(active(X)) => U72(X) isPal(mark(X)) => isPal(X) isPal(active(X)) => isPal(X) U81(mark(X)) => U81(X) U81(active(X)) => U81(X) isQid(mark(X)) => isQid(X) isQid(active(X)) => isQid(X) isNePal(mark(X)) => isNePal(X) isNePal(active(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]): active(!6220!6220(!6220!6220(X, Y), Z)) >? mark(!6220!6220(X, !6220!6220(Y, Z))) active(!6220!6220(X, nil)) >? mark(X) active(!6220!6220(nil, X)) >? mark(X) active(U11(tt)) >? mark(tt) active(U21(tt, X)) >? mark(U22(isList(X))) active(U22(tt)) >? mark(tt) active(U31(tt)) >? mark(tt) active(U41(tt, X)) >? mark(U42(isNeList(X))) active(U42(tt)) >? mark(tt) active(U51(tt, X)) >? mark(U52(isList(X))) active(U52(tt)) >? mark(tt) active(U61(tt)) >? mark(tt) active(U71(tt, X)) >? mark(U72(isPal(X))) active(U72(tt)) >? mark(tt) active(U81(tt)) >? mark(tt) active(isList(X)) >? mark(U11(isNeList(X))) active(isList(nil)) >? mark(tt) active(isList(!6220!6220(X, Y))) >? mark(U21(isList(X), Y)) active(isNeList(X)) >? mark(U31(isQid(X))) active(isNeList(!6220!6220(X, Y))) >? mark(U41(isList(X), Y)) active(isNeList(!6220!6220(X, Y))) >? mark(U51(isNeList(X), Y)) active(isNePal(X)) >? mark(U61(isQid(X))) active(isNePal(!6220!6220(X, !6220!6220(Y, X)))) >? mark(U71(isQid(X), Y)) active(isPal(X)) >? mark(U81(isNePal(X))) active(isPal(nil)) >? mark(tt) active(isQid(a)) >? mark(tt) active(isQid(e)) >? mark(tt) active(isQid(i)) >? mark(tt) active(isQid(o)) >? mark(tt) active(isQid(u)) >? mark(tt) mark(!6220!6220(X, Y)) >? active(!6220!6220(mark(X), mark(Y))) mark(nil) >? active(nil) mark(U11(X)) >? active(U11(mark(X))) mark(tt) >? active(tt) mark(U21(X, Y)) >? active(U21(mark(X), Y)) mark(U22(X)) >? active(U22(mark(X))) mark(isList(X)) >? active(isList(X)) mark(U31(X)) >? active(U31(mark(X))) mark(U41(X, Y)) >? active(U41(mark(X), Y)) mark(U42(X)) >? active(U42(mark(X))) mark(isNeList(X)) >? active(isNeList(X)) mark(U51(X, Y)) >? active(U51(mark(X), Y)) mark(U52(X)) >? active(U52(mark(X))) mark(U61(X)) >? active(U61(mark(X))) mark(U71(X, Y)) >? active(U71(mark(X), Y)) mark(U72(X)) >? active(U72(mark(X))) mark(isPal(X)) >? active(isPal(X)) mark(U81(X)) >? active(U81(mark(X))) mark(isQid(X)) >? active(isQid(X)) mark(isNePal(X)) >? active(isNePal(X)) mark(a) >? active(a) mark(e) >? active(e) mark(i) >? active(i) mark(o) >? active(o) mark(u) >? active(u) !6220!6220(mark(X), Y) >? !6220!6220(X, Y) !6220!6220(X, mark(Y)) >? !6220!6220(X, Y) !6220!6220(active(X), Y) >? !6220!6220(X, Y) !6220!6220(X, active(Y)) >? !6220!6220(X, Y) U11(mark(X)) >? U11(X) U11(active(X)) >? U11(X) U21(mark(X), Y) >? U21(X, Y) U21(X, mark(Y)) >? U21(X, Y) U21(active(X), Y) >? U21(X, Y) U21(X, active(Y)) >? U21(X, Y) U22(mark(X)) >? U22(X) U22(active(X)) >? U22(X) isList(mark(X)) >? isList(X) isList(active(X)) >? isList(X) U31(mark(X)) >? U31(X) U31(active(X)) >? U31(X) U41(mark(X), Y) >? U41(X, Y) U41(X, mark(Y)) >? U41(X, Y) U41(active(X), Y) >? U41(X, Y) U41(X, active(Y)) >? U41(X, Y) U42(mark(X)) >? U42(X) U42(active(X)) >? U42(X) isNeList(mark(X)) >? isNeList(X) isNeList(active(X)) >? isNeList(X) U51(mark(X), Y) >? U51(X, Y) U51(X, mark(Y)) >? U51(X, Y) U51(active(X), Y) >? U51(X, Y) U51(X, active(Y)) >? U51(X, Y) U52(mark(X)) >? U52(X) U52(active(X)) >? U52(X) U61(mark(X)) >? U61(X) U61(active(X)) >? U61(X) U71(mark(X), Y) >? U71(X, Y) U71(X, mark(Y)) >? U71(X, Y) U71(active(X), Y) >? U71(X, Y) U71(X, active(Y)) >? U71(X, Y) U72(mark(X)) >? U72(X) U72(active(X)) >? U72(X) isPal(mark(X)) >? isPal(X) isPal(active(X)) >? isPal(X) U81(mark(X)) >? U81(X) U81(active(X)) >? U81(X) isQid(mark(X)) >? isQid(X) isQid(active(X)) >? isQid(X) isNePal(mark(X)) >? isNePal(X) isNePal(active(X)) >? isNePal(X) We orient these requirements with a polynomial interpretation in the natural numbers. The following interpretation satisfies the requirements: !6220!6220 = \y0y1.1 + y1 + 2y0 U11 = \y0.y0 U21 = \y0y1.y0 + y1 U22 = \y0.y0 U31 = \y0.y0 U41 = \y0y1.1 + y1 + 2y0 U42 = \y0.y0 U51 = \y0y1.y0 + y1 U52 = \y0.y0 U61 = \y0.y0 U71 = \y0y1.y0 + 2y1 U72 = \y0.y0 U81 = \y0.y0 a = 0 active = \y0.y0 e = 1 i = 1 isList = \y0.y0 isNeList = \y0.y0 isNePal = \y0.2y0 isPal = \y0.2y0 isQid = \y0.y0 mark = \y0.y0 nil = 0 o = 0 tt = 0 u = 0 Using this interpretation, the requirements translate to: [[active(!6220!6220(!6220!6220(_x0, _x1), _x2))]] = 3 + x2 + 2x1 + 4x0 > 2 + x2 + 2x0 + 2x1 = [[mark(!6220!6220(_x0, !6220!6220(_x1, _x2)))]] [[active(!6220!6220(_x0, nil))]] = 1 + 2x0 > x0 = [[mark(_x0)]] [[active(!6220!6220(nil, _x0))]] = 1 + x0 > x0 = [[mark(_x0)]] [[active(U11(tt))]] = 0 >= 0 = [[mark(tt)]] [[active(U21(tt, _x0))]] = x0 >= x0 = [[mark(U22(isList(_x0)))]] [[active(U22(tt))]] = 0 >= 0 = [[mark(tt)]] [[active(U31(tt))]] = 0 >= 0 = [[mark(tt)]] [[active(U41(tt, _x0))]] = 1 + x0 > x0 = [[mark(U42(isNeList(_x0)))]] [[active(U42(tt))]] = 0 >= 0 = [[mark(tt)]] [[active(U51(tt, _x0))]] = x0 >= x0 = [[mark(U52(isList(_x0)))]] [[active(U52(tt))]] = 0 >= 0 = [[mark(tt)]] [[active(U61(tt))]] = 0 >= 0 = [[mark(tt)]] [[active(U71(tt, _x0))]] = 2x0 >= 2x0 = [[mark(U72(isPal(_x0)))]] [[active(U72(tt))]] = 0 >= 0 = [[mark(tt)]] [[active(U81(tt))]] = 0 >= 0 = [[mark(tt)]] [[active(isList(_x0))]] = x0 >= x0 = [[mark(U11(isNeList(_x0)))]] [[active(isList(nil))]] = 0 >= 0 = [[mark(tt)]] [[active(isList(!6220!6220(_x0, _x1)))]] = 1 + x1 + 2x0 > x0 + x1 = [[mark(U21(isList(_x0), _x1))]] [[active(isNeList(_x0))]] = x0 >= x0 = [[mark(U31(isQid(_x0)))]] [[active(isNeList(!6220!6220(_x0, _x1)))]] = 1 + x1 + 2x0 >= 1 + x1 + 2x0 = [[mark(U41(isList(_x0), _x1))]] [[active(isNeList(!6220!6220(_x0, _x1)))]] = 1 + x1 + 2x0 > x0 + x1 = [[mark(U51(isNeList(_x0), _x1))]] [[active(isNePal(_x0))]] = 2x0 >= x0 = [[mark(U61(isQid(_x0)))]] [[active(isNePal(!6220!6220(_x0, !6220!6220(_x1, _x0))))]] = 4 + 4x1 + 6x0 > x0 + 2x1 = [[mark(U71(isQid(_x0), _x1))]] [[active(isPal(_x0))]] = 2x0 >= 2x0 = [[mark(U81(isNePal(_x0)))]] [[active(isPal(nil))]] = 0 >= 0 = [[mark(tt)]] [[active(isQid(a))]] = 0 >= 0 = [[mark(tt)]] [[active(isQid(e))]] = 1 > 0 = [[mark(tt)]] [[active(isQid(i))]] = 1 > 0 = [[mark(tt)]] [[active(isQid(o))]] = 0 >= 0 = [[mark(tt)]] [[active(isQid(u))]] = 0 >= 0 = [[mark(tt)]] [[mark(!6220!6220(_x0, _x1))]] = 1 + x1 + 2x0 >= 1 + x1 + 2x0 = [[active(!6220!6220(mark(_x0), mark(_x1)))]] [[mark(nil)]] = 0 >= 0 = [[active(nil)]] [[mark(U11(_x0))]] = x0 >= x0 = [[active(U11(mark(_x0)))]] [[mark(tt)]] = 0 >= 0 = [[active(tt)]] [[mark(U21(_x0, _x1))]] = x0 + x1 >= x0 + x1 = [[active(U21(mark(_x0), _x1))]] [[mark(U22(_x0))]] = x0 >= x0 = [[active(U22(mark(_x0)))]] [[mark(isList(_x0))]] = x0 >= x0 = [[active(isList(_x0))]] [[mark(U31(_x0))]] = x0 >= x0 = [[active(U31(mark(_x0)))]] [[mark(U41(_x0, _x1))]] = 1 + x1 + 2x0 >= 1 + x1 + 2x0 = [[active(U41(mark(_x0), _x1))]] [[mark(U42(_x0))]] = x0 >= x0 = [[active(U42(mark(_x0)))]] [[mark(isNeList(_x0))]] = x0 >= x0 = [[active(isNeList(_x0))]] [[mark(U51(_x0, _x1))]] = x0 + x1 >= x0 + x1 = [[active(U51(mark(_x0), _x1))]] [[mark(U52(_x0))]] = x0 >= x0 = [[active(U52(mark(_x0)))]] [[mark(U61(_x0))]] = x0 >= x0 = [[active(U61(mark(_x0)))]] [[mark(U71(_x0, _x1))]] = x0 + 2x1 >= x0 + 2x1 = [[active(U71(mark(_x0), _x1))]] [[mark(U72(_x0))]] = x0 >= x0 = [[active(U72(mark(_x0)))]] [[mark(isPal(_x0))]] = 2x0 >= 2x0 = [[active(isPal(_x0))]] [[mark(U81(_x0))]] = x0 >= x0 = [[active(U81(mark(_x0)))]] [[mark(isQid(_x0))]] = x0 >= x0 = [[active(isQid(_x0))]] [[mark(isNePal(_x0))]] = 2x0 >= 2x0 = [[active(isNePal(_x0))]] [[mark(a)]] = 0 >= 0 = [[active(a)]] [[mark(e)]] = 1 >= 1 = [[active(e)]] [[mark(i)]] = 1 >= 1 = [[active(i)]] [[mark(o)]] = 0 >= 0 = [[active(o)]] [[mark(u)]] = 0 >= 0 = [[active(u)]] [[!6220!6220(mark(_x0), _x1)]] = 1 + x1 + 2x0 >= 1 + x1 + 2x0 = [[!6220!6220(_x0, _x1)]] [[!6220!6220(_x0, mark(_x1))]] = 1 + x1 + 2x0 >= 1 + x1 + 2x0 = [[!6220!6220(_x0, _x1)]] [[!6220!6220(active(_x0), _x1)]] = 1 + x1 + 2x0 >= 1 + x1 + 2x0 = [[!6220!6220(_x0, _x1)]] [[!6220!6220(_x0, active(_x1))]] = 1 + x1 + 2x0 >= 1 + x1 + 2x0 = [[!6220!6220(_x0, _x1)]] [[U11(mark(_x0))]] = x0 >= x0 = [[U11(_x0)]] [[U11(active(_x0))]] = x0 >= x0 = [[U11(_x0)]] [[U21(mark(_x0), _x1)]] = x0 + x1 >= x0 + x1 = [[U21(_x0, _x1)]] [[U21(_x0, mark(_x1))]] = x0 + x1 >= x0 + x1 = [[U21(_x0, _x1)]] [[U21(active(_x0), _x1)]] = x0 + x1 >= x0 + x1 = [[U21(_x0, _x1)]] [[U21(_x0, active(_x1))]] = x0 + x1 >= x0 + x1 = [[U21(_x0, _x1)]] [[U22(mark(_x0))]] = x0 >= x0 = [[U22(_x0)]] [[U22(active(_x0))]] = x0 >= x0 = [[U22(_x0)]] [[isList(mark(_x0))]] = x0 >= x0 = [[isList(_x0)]] [[isList(active(_x0))]] = x0 >= x0 = [[isList(_x0)]] [[U31(mark(_x0))]] = x0 >= x0 = [[U31(_x0)]] [[U31(active(_x0))]] = x0 >= x0 = [[U31(_x0)]] [[U41(mark(_x0), _x1)]] = 1 + x1 + 2x0 >= 1 + x1 + 2x0 = [[U41(_x0, _x1)]] [[U41(_x0, mark(_x1))]] = 1 + x1 + 2x0 >= 1 + x1 + 2x0 = [[U41(_x0, _x1)]] [[U41(active(_x0), _x1)]] = 1 + x1 + 2x0 >= 1 + x1 + 2x0 = [[U41(_x0, _x1)]] [[U41(_x0, active(_x1))]] = 1 + x1 + 2x0 >= 1 + x1 + 2x0 = [[U41(_x0, _x1)]] [[U42(mark(_x0))]] = x0 >= x0 = [[U42(_x0)]] [[U42(active(_x0))]] = x0 >= x0 = [[U42(_x0)]] [[isNeList(mark(_x0))]] = x0 >= x0 = [[isNeList(_x0)]] [[isNeList(active(_x0))]] = x0 >= x0 = [[isNeList(_x0)]] [[U51(mark(_x0), _x1)]] = x0 + x1 >= x0 + x1 = [[U51(_x0, _x1)]] [[U51(_x0, mark(_x1))]] = x0 + x1 >= x0 + x1 = [[U51(_x0, _x1)]] [[U51(active(_x0), _x1)]] = x0 + x1 >= x0 + x1 = [[U51(_x0, _x1)]] [[U51(_x0, active(_x1))]] = x0 + x1 >= x0 + x1 = [[U51(_x0, _x1)]] [[U52(mark(_x0))]] = x0 >= x0 = [[U52(_x0)]] [[U52(active(_x0))]] = x0 >= x0 = [[U52(_x0)]] [[U61(mark(_x0))]] = x0 >= x0 = [[U61(_x0)]] [[U61(active(_x0))]] = x0 >= x0 = [[U61(_x0)]] [[U71(mark(_x0), _x1)]] = x0 + 2x1 >= x0 + 2x1 = [[U71(_x0, _x1)]] [[U71(_x0, mark(_x1))]] = x0 + 2x1 >= x0 + 2x1 = [[U71(_x0, _x1)]] [[U71(active(_x0), _x1)]] = x0 + 2x1 >= x0 + 2x1 = [[U71(_x0, _x1)]] [[U71(_x0, active(_x1))]] = x0 + 2x1 >= x0 + 2x1 = [[U71(_x0, _x1)]] [[U72(mark(_x0))]] = x0 >= x0 = [[U72(_x0)]] [[U72(active(_x0))]] = x0 >= x0 = [[U72(_x0)]] [[isPal(mark(_x0))]] = 2x0 >= 2x0 = [[isPal(_x0)]] [[isPal(active(_x0))]] = 2x0 >= 2x0 = [[isPal(_x0)]] [[U81(mark(_x0))]] = x0 >= x0 = [[U81(_x0)]] [[U81(active(_x0))]] = x0 >= x0 = [[U81(_x0)]] [[isQid(mark(_x0))]] = x0 >= x0 = [[isQid(_x0)]] [[isQid(active(_x0))]] = x0 >= x0 = [[isQid(_x0)]] [[isNePal(mark(_x0))]] = 2x0 >= 2x0 = [[isNePal(_x0)]] [[isNePal(active(_x0))]] = 2x0 >= 2x0 = [[isNePal(_x0)]] We can thus remove the following rules: active(!6220!6220(!6220!6220(X, Y), Z)) => mark(!6220!6220(X, !6220!6220(Y, Z))) active(!6220!6220(X, nil)) => mark(X) active(!6220!6220(nil, X)) => mark(X) active(U41(tt, X)) => mark(U42(isNeList(X))) active(isList(!6220!6220(X, Y))) => mark(U21(isList(X), Y)) active(isNeList(!6220!6220(X, Y))) => mark(U51(isNeList(X), Y)) active(isNePal(!6220!6220(X, !6220!6220(Y, X)))) => mark(U71(isQid(X), Y)) active(isQid(e)) => mark(tt) active(isQid(i)) => mark(tt) We use rule removal, following [Kop12, Theorem 2.23]. This gives the following requirements (possibly using Theorems 2.25 and 2.26 in [Kop12]): active(U11(tt)) >? mark(tt) active(U21(tt, X)) >? mark(U22(isList(X))) active(U22(tt)) >? mark(tt) active(U31(tt)) >? mark(tt) active(U42(tt)) >? mark(tt) active(U51(tt, X)) >? mark(U52(isList(X))) active(U52(tt)) >? mark(tt) active(U61(tt)) >? mark(tt) active(U71(tt, X)) >? mark(U72(isPal(X))) active(U72(tt)) >? mark(tt) active(U81(tt)) >? mark(tt) active(isList(X)) >? mark(U11(isNeList(X))) active(isList(nil)) >? mark(tt) active(isNeList(X)) >? mark(U31(isQid(X))) active(isNeList(!6220!6220(X, Y))) >? mark(U41(isList(X), Y)) active(isNePal(X)) >? mark(U61(isQid(X))) active(isPal(X)) >? mark(U81(isNePal(X))) active(isPal(nil)) >? mark(tt) active(isQid(a)) >? mark(tt) active(isQid(o)) >? mark(tt) active(isQid(u)) >? mark(tt) mark(!6220!6220(X, Y)) >? active(!6220!6220(mark(X), mark(Y))) mark(nil) >? active(nil) mark(U11(X)) >? active(U11(mark(X))) mark(tt) >? active(tt) mark(U21(X, Y)) >? active(U21(mark(X), Y)) mark(U22(X)) >? active(U22(mark(X))) mark(isList(X)) >? active(isList(X)) mark(U31(X)) >? active(U31(mark(X))) mark(U41(X, Y)) >? active(U41(mark(X), Y)) mark(U42(X)) >? active(U42(mark(X))) mark(isNeList(X)) >? active(isNeList(X)) mark(U51(X, Y)) >? active(U51(mark(X), Y)) mark(U52(X)) >? active(U52(mark(X))) mark(U61(X)) >? active(U61(mark(X))) mark(U71(X, Y)) >? active(U71(mark(X), Y)) mark(U72(X)) >? active(U72(mark(X))) mark(isPal(X)) >? active(isPal(X)) mark(U81(X)) >? active(U81(mark(X))) mark(isQid(X)) >? active(isQid(X)) mark(isNePal(X)) >? active(isNePal(X)) mark(a) >? active(a) mark(e) >? active(e) mark(i) >? active(i) mark(o) >? active(o) mark(u) >? active(u) !6220!6220(mark(X), Y) >? !6220!6220(X, Y) !6220!6220(X, mark(Y)) >? !6220!6220(X, Y) !6220!6220(active(X), Y) >? !6220!6220(X, Y) !6220!6220(X, active(Y)) >? !6220!6220(X, Y) U11(mark(X)) >? U11(X) U11(active(X)) >? U11(X) U21(mark(X), Y) >? U21(X, Y) U21(X, mark(Y)) >? U21(X, Y) U21(active(X), Y) >? U21(X, Y) U21(X, active(Y)) >? U21(X, Y) U22(mark(X)) >? U22(X) U22(active(X)) >? U22(X) isList(mark(X)) >? isList(X) isList(active(X)) >? isList(X) U31(mark(X)) >? U31(X) U31(active(X)) >? U31(X) U41(mark(X), Y) >? U41(X, Y) U41(X, mark(Y)) >? U41(X, Y) U41(active(X), Y) >? U41(X, Y) U41(X, active(Y)) >? U41(X, Y) U42(mark(X)) >? U42(X) U42(active(X)) >? U42(X) isNeList(mark(X)) >? isNeList(X) isNeList(active(X)) >? isNeList(X) U51(mark(X), Y) >? U51(X, Y) U51(X, mark(Y)) >? U51(X, Y) U51(active(X), Y) >? U51(X, Y) U51(X, active(Y)) >? U51(X, Y) U52(mark(X)) >? U52(X) U52(active(X)) >? U52(X) U61(mark(X)) >? U61(X) U61(active(X)) >? U61(X) U71(mark(X), Y) >? U71(X, Y) U71(X, mark(Y)) >? U71(X, Y) U71(active(X), Y) >? U71(X, Y) U71(X, active(Y)) >? U71(X, Y) U72(mark(X)) >? U72(X) U72(active(X)) >? U72(X) isPal(mark(X)) >? isPal(X) isPal(active(X)) >? isPal(X) U81(mark(X)) >? U81(X) U81(active(X)) >? U81(X) isQid(mark(X)) >? isQid(X) isQid(active(X)) >? isQid(X) isNePal(mark(X)) >? isNePal(X) isNePal(active(X)) >? isNePal(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 = \y0.y0 U21 = \y0y1.2y0 + 2y1 U22 = \y0.2y0 U31 = \y0.y0 U41 = \y0y1.y1 + 2y0 U42 = \y0.1 + y0 U51 = \y0y1.3 + y0 + y1 U52 = \y0.3 + y0 U61 = \y0.y0 U71 = \y0y1.y0 + y1 U72 = \y0.y0 U81 = \y0.y0 a = 1 active = \y0.y0 e = 0 i = 0 isList = \y0.y0 isNeList = \y0.y0 isNePal = \y0.y0 isPal = \y0.y0 isQid = \y0.y0 mark = \y0.y0 nil = 0 o = 0 tt = 0 u = 0 Using this interpretation, the requirements translate to: [[active(U11(tt))]] = 0 >= 0 = [[mark(tt)]] [[active(U21(tt, _x0))]] = 2x0 >= 2x0 = [[mark(U22(isList(_x0)))]] [[active(U22(tt))]] = 0 >= 0 = [[mark(tt)]] [[active(U31(tt))]] = 0 >= 0 = [[mark(tt)]] [[active(U42(tt))]] = 1 > 0 = [[mark(tt)]] [[active(U51(tt, _x0))]] = 3 + x0 >= 3 + x0 = [[mark(U52(isList(_x0)))]] [[active(U52(tt))]] = 3 > 0 = [[mark(tt)]] [[active(U61(tt))]] = 0 >= 0 = [[mark(tt)]] [[active(U71(tt, _x0))]] = x0 >= x0 = [[mark(U72(isPal(_x0)))]] [[active(U72(tt))]] = 0 >= 0 = [[mark(tt)]] [[active(U81(tt))]] = 0 >= 0 = [[mark(tt)]] [[active(isList(_x0))]] = x0 >= x0 = [[mark(U11(isNeList(_x0)))]] [[active(isList(nil))]] = 0 >= 0 = [[mark(tt)]] [[active(isNeList(_x0))]] = x0 >= x0 = [[mark(U31(isQid(_x0)))]] [[active(isNeList(!6220!6220(_x0, _x1)))]] = x1 + 2x0 >= x1 + 2x0 = [[mark(U41(isList(_x0), _x1))]] [[active(isNePal(_x0))]] = x0 >= x0 = [[mark(U61(isQid(_x0)))]] [[active(isPal(_x0))]] = x0 >= x0 = [[mark(U81(isNePal(_x0)))]] [[active(isPal(nil))]] = 0 >= 0 = [[mark(tt)]] [[active(isQid(a))]] = 1 > 0 = [[mark(tt)]] [[active(isQid(o))]] = 0 >= 0 = [[mark(tt)]] [[active(isQid(u))]] = 0 >= 0 = [[mark(tt)]] [[mark(!6220!6220(_x0, _x1))]] = x1 + 2x0 >= x1 + 2x0 = [[active(!6220!6220(mark(_x0), mark(_x1)))]] [[mark(nil)]] = 0 >= 0 = [[active(nil)]] [[mark(U11(_x0))]] = x0 >= x0 = [[active(U11(mark(_x0)))]] [[mark(tt)]] = 0 >= 0 = [[active(tt)]] [[mark(U21(_x0, _x1))]] = 2x0 + 2x1 >= 2x0 + 2x1 = [[active(U21(mark(_x0), _x1))]] [[mark(U22(_x0))]] = 2x0 >= 2x0 = [[active(U22(mark(_x0)))]] [[mark(isList(_x0))]] = x0 >= x0 = [[active(isList(_x0))]] [[mark(U31(_x0))]] = x0 >= x0 = [[active(U31(mark(_x0)))]] [[mark(U41(_x0, _x1))]] = x1 + 2x0 >= x1 + 2x0 = [[active(U41(mark(_x0), _x1))]] [[mark(U42(_x0))]] = 1 + x0 >= 1 + x0 = [[active(U42(mark(_x0)))]] [[mark(isNeList(_x0))]] = x0 >= x0 = [[active(isNeList(_x0))]] [[mark(U51(_x0, _x1))]] = 3 + x0 + x1 >= 3 + x0 + x1 = [[active(U51(mark(_x0), _x1))]] [[mark(U52(_x0))]] = 3 + x0 >= 3 + x0 = [[active(U52(mark(_x0)))]] [[mark(U61(_x0))]] = x0 >= x0 = [[active(U61(mark(_x0)))]] [[mark(U71(_x0, _x1))]] = x0 + x1 >= x0 + x1 = [[active(U71(mark(_x0), _x1))]] [[mark(U72(_x0))]] = x0 >= x0 = [[active(U72(mark(_x0)))]] [[mark(isPal(_x0))]] = x0 >= x0 = [[active(isPal(_x0))]] [[mark(U81(_x0))]] = x0 >= x0 = [[active(U81(mark(_x0)))]] [[mark(isQid(_x0))]] = x0 >= x0 = [[active(isQid(_x0))]] [[mark(isNePal(_x0))]] = x0 >= x0 = [[active(isNePal(_x0))]] [[mark(a)]] = 1 >= 1 = [[active(a)]] [[mark(e)]] = 0 >= 0 = [[active(e)]] [[mark(i)]] = 0 >= 0 = [[active(i)]] [[mark(o)]] = 0 >= 0 = [[active(o)]] [[mark(u)]] = 0 >= 0 = [[active(u)]] [[!6220!6220(mark(_x0), _x1)]] = x1 + 2x0 >= x1 + 2x0 = [[!6220!6220(_x0, _x1)]] [[!6220!6220(_x0, mark(_x1))]] = x1 + 2x0 >= x1 + 2x0 = [[!6220!6220(_x0, _x1)]] [[!6220!6220(active(_x0), _x1)]] = x1 + 2x0 >= x1 + 2x0 = [[!6220!6220(_x0, _x1)]] [[!6220!6220(_x0, active(_x1))]] = x1 + 2x0 >= x1 + 2x0 = [[!6220!6220(_x0, _x1)]] [[U11(mark(_x0))]] = x0 >= x0 = [[U11(_x0)]] [[U11(active(_x0))]] = x0 >= x0 = [[U11(_x0)]] [[U21(mark(_x0), _x1)]] = 2x0 + 2x1 >= 2x0 + 2x1 = [[U21(_x0, _x1)]] [[U21(_x0, mark(_x1))]] = 2x0 + 2x1 >= 2x0 + 2x1 = [[U21(_x0, _x1)]] [[U21(active(_x0), _x1)]] = 2x0 + 2x1 >= 2x0 + 2x1 = [[U21(_x0, _x1)]] [[U21(_x0, active(_x1))]] = 2x0 + 2x1 >= 2x0 + 2x1 = [[U21(_x0, _x1)]] [[U22(mark(_x0))]] = 2x0 >= 2x0 = [[U22(_x0)]] [[U22(active(_x0))]] = 2x0 >= 2x0 = [[U22(_x0)]] [[isList(mark(_x0))]] = x0 >= x0 = [[isList(_x0)]] [[isList(active(_x0))]] = x0 >= x0 = [[isList(_x0)]] [[U31(mark(_x0))]] = x0 >= x0 = [[U31(_x0)]] [[U31(active(_x0))]] = x0 >= x0 = [[U31(_x0)]] [[U41(mark(_x0), _x1)]] = x1 + 2x0 >= x1 + 2x0 = [[U41(_x0, _x1)]] [[U41(_x0, mark(_x1))]] = x1 + 2x0 >= x1 + 2x0 = [[U41(_x0, _x1)]] [[U41(active(_x0), _x1)]] = x1 + 2x0 >= x1 + 2x0 = [[U41(_x0, _x1)]] [[U41(_x0, active(_x1))]] = x1 + 2x0 >= x1 + 2x0 = [[U41(_x0, _x1)]] [[U42(mark(_x0))]] = 1 + x0 >= 1 + x0 = [[U42(_x0)]] [[U42(active(_x0))]] = 1 + x0 >= 1 + x0 = [[U42(_x0)]] [[isNeList(mark(_x0))]] = x0 >= x0 = [[isNeList(_x0)]] [[isNeList(active(_x0))]] = x0 >= x0 = [[isNeList(_x0)]] [[U51(mark(_x0), _x1)]] = 3 + x0 + x1 >= 3 + x0 + x1 = [[U51(_x0, _x1)]] [[U51(_x0, mark(_x1))]] = 3 + x0 + x1 >= 3 + x0 + x1 = [[U51(_x0, _x1)]] [[U51(active(_x0), _x1)]] = 3 + x0 + x1 >= 3 + x0 + x1 = [[U51(_x0, _x1)]] [[U51(_x0, active(_x1))]] = 3 + x0 + x1 >= 3 + x0 + x1 = [[U51(_x0, _x1)]] [[U52(mark(_x0))]] = 3 + x0 >= 3 + x0 = [[U52(_x0)]] [[U52(active(_x0))]] = 3 + x0 >= 3 + x0 = [[U52(_x0)]] [[U61(mark(_x0))]] = x0 >= x0 = [[U61(_x0)]] [[U61(active(_x0))]] = x0 >= x0 = [[U61(_x0)]] [[U71(mark(_x0), _x1)]] = x0 + x1 >= x0 + x1 = [[U71(_x0, _x1)]] [[U71(_x0, mark(_x1))]] = x0 + x1 >= x0 + x1 = [[U71(_x0, _x1)]] [[U71(active(_x0), _x1)]] = x0 + x1 >= x0 + x1 = [[U71(_x0, _x1)]] [[U71(_x0, active(_x1))]] = x0 + x1 >= x0 + x1 = [[U71(_x0, _x1)]] [[U72(mark(_x0))]] = x0 >= x0 = [[U72(_x0)]] [[U72(active(_x0))]] = x0 >= x0 = [[U72(_x0)]] [[isPal(mark(_x0))]] = x0 >= x0 = [[isPal(_x0)]] [[isPal(active(_x0))]] = x0 >= x0 = [[isPal(_x0)]] [[U81(mark(_x0))]] = x0 >= x0 = [[U81(_x0)]] [[U81(active(_x0))]] = x0 >= x0 = [[U81(_x0)]] [[isQid(mark(_x0))]] = x0 >= x0 = [[isQid(_x0)]] [[isQid(active(_x0))]] = x0 >= x0 = [[isQid(_x0)]] [[isNePal(mark(_x0))]] = x0 >= x0 = [[isNePal(_x0)]] [[isNePal(active(_x0))]] = x0 >= x0 = [[isNePal(_x0)]] We can thus remove the following rules: active(U42(tt)) => mark(tt) active(U52(tt)) => mark(tt) active(isQid(a)) => mark(tt) We use rule removal, following [Kop12, Theorem 2.23]. This gives the following requirements (possibly using Theorems 2.25 and 2.26 in [Kop12]): active(U11(tt)) >? mark(tt) active(U21(tt, X)) >? mark(U22(isList(X))) active(U22(tt)) >? mark(tt) active(U31(tt)) >? mark(tt) active(U51(tt, X)) >? mark(U52(isList(X))) active(U61(tt)) >? mark(tt) active(U71(tt, X)) >? mark(U72(isPal(X))) active(U72(tt)) >? mark(tt) active(U81(tt)) >? mark(tt) active(isList(X)) >? mark(U11(isNeList(X))) active(isList(nil)) >? mark(tt) active(isNeList(X)) >? mark(U31(isQid(X))) active(isNeList(!6220!6220(X, Y))) >? mark(U41(isList(X), Y)) active(isNePal(X)) >? mark(U61(isQid(X))) active(isPal(X)) >? mark(U81(isNePal(X))) active(isPal(nil)) >? mark(tt) active(isQid(o)) >? mark(tt) active(isQid(u)) >? mark(tt) mark(!6220!6220(X, Y)) >? active(!6220!6220(mark(X), mark(Y))) mark(nil) >? active(nil) mark(U11(X)) >? active(U11(mark(X))) mark(tt) >? active(tt) mark(U21(X, Y)) >? active(U21(mark(X), Y)) mark(U22(X)) >? active(U22(mark(X))) mark(isList(X)) >? active(isList(X)) mark(U31(X)) >? active(U31(mark(X))) mark(U41(X, Y)) >? active(U41(mark(X), Y)) mark(U42(X)) >? active(U42(mark(X))) mark(isNeList(X)) >? active(isNeList(X)) mark(U51(X, Y)) >? active(U51(mark(X), Y)) mark(U52(X)) >? active(U52(mark(X))) mark(U61(X)) >? active(U61(mark(X))) mark(U71(X, Y)) >? active(U71(mark(X), Y)) mark(U72(X)) >? active(U72(mark(X))) mark(isPal(X)) >? active(isPal(X)) mark(U81(X)) >? active(U81(mark(X))) mark(isQid(X)) >? active(isQid(X)) mark(isNePal(X)) >? active(isNePal(X)) mark(a) >? active(a) mark(e) >? active(e) mark(i) >? active(i) mark(o) >? active(o) mark(u) >? active(u) !6220!6220(mark(X), Y) >? !6220!6220(X, Y) !6220!6220(X, mark(Y)) >? !6220!6220(X, Y) !6220!6220(active(X), Y) >? !6220!6220(X, Y) !6220!6220(X, active(Y)) >? !6220!6220(X, Y) U11(mark(X)) >? U11(X) U11(active(X)) >? U11(X) U21(mark(X), Y) >? U21(X, Y) U21(X, mark(Y)) >? U21(X, Y) U21(active(X), Y) >? U21(X, Y) U21(X, active(Y)) >? U21(X, Y) U22(mark(X)) >? U22(X) U22(active(X)) >? U22(X) isList(mark(X)) >? isList(X) isList(active(X)) >? isList(X) U31(mark(X)) >? U31(X) U31(active(X)) >? U31(X) U41(mark(X), Y) >? U41(X, Y) U41(X, mark(Y)) >? U41(X, Y) U41(active(X), Y) >? U41(X, Y) U41(X, active(Y)) >? U41(X, Y) U42(mark(X)) >? U42(X) U42(active(X)) >? U42(X) isNeList(mark(X)) >? isNeList(X) isNeList(active(X)) >? isNeList(X) U51(mark(X), Y) >? U51(X, Y) U51(X, mark(Y)) >? U51(X, Y) U51(active(X), Y) >? U51(X, Y) U51(X, active(Y)) >? U51(X, Y) U52(mark(X)) >? U52(X) U52(active(X)) >? U52(X) U61(mark(X)) >? U61(X) U61(active(X)) >? U61(X) U71(mark(X), Y) >? U71(X, Y) U71(X, mark(Y)) >? U71(X, Y) U71(active(X), Y) >? U71(X, Y) U71(X, active(Y)) >? U71(X, Y) U72(mark(X)) >? U72(X) U72(active(X)) >? U72(X) isPal(mark(X)) >? isPal(X) isPal(active(X)) >? isPal(X) U81(mark(X)) >? U81(X) U81(active(X)) >? U81(X) isQid(mark(X)) >? isQid(X) isQid(active(X)) >? isQid(X) isNePal(mark(X)) >? isNePal(X) isNePal(active(X)) >? isNePal(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 = \y0.y0 U21 = \y0y1.y0 + y1 U22 = \y0.y0 U31 = \y0.y0 U41 = \y0y1.y0 + y1 U42 = \y0.y0 U51 = \y0y1.1 + y0 + 2y1 U52 = \y0.2y0 U61 = \y0.y0 U71 = \y0y1.1 + y0 + 2y1 U72 = \y0.y0 U81 = \y0.y0 a = 1 active = \y0.y0 e = 0 i = 0 isList = \y0.y0 isNeList = \y0.y0 isNePal = \y0.1 + y0 isPal = \y0.1 + y0 isQid = \y0.y0 mark = \y0.y0 nil = 0 o = 0 tt = 0 u = 0 Using this interpretation, the requirements translate to: [[active(U11(tt))]] = 0 >= 0 = [[mark(tt)]] [[active(U21(tt, _x0))]] = x0 >= x0 = [[mark(U22(isList(_x0)))]] [[active(U22(tt))]] = 0 >= 0 = [[mark(tt)]] [[active(U31(tt))]] = 0 >= 0 = [[mark(tt)]] [[active(U51(tt, _x0))]] = 1 + 2x0 > 2x0 = [[mark(U52(isList(_x0)))]] [[active(U61(tt))]] = 0 >= 0 = [[mark(tt)]] [[active(U71(tt, _x0))]] = 1 + 2x0 >= 1 + x0 = [[mark(U72(isPal(_x0)))]] [[active(U72(tt))]] = 0 >= 0 = [[mark(tt)]] [[active(U81(tt))]] = 0 >= 0 = [[mark(tt)]] [[active(isList(_x0))]] = x0 >= x0 = [[mark(U11(isNeList(_x0)))]] [[active(isList(nil))]] = 0 >= 0 = [[mark(tt)]] [[active(isNeList(_x0))]] = x0 >= x0 = [[mark(U31(isQid(_x0)))]] [[active(isNeList(!6220!6220(_x0, _x1)))]] = x0 + x1 >= x0 + x1 = [[mark(U41(isList(_x0), _x1))]] [[active(isNePal(_x0))]] = 1 + x0 > x0 = [[mark(U61(isQid(_x0)))]] [[active(isPal(_x0))]] = 1 + x0 >= 1 + x0 = [[mark(U81(isNePal(_x0)))]] [[active(isPal(nil))]] = 1 > 0 = [[mark(tt)]] [[active(isQid(o))]] = 0 >= 0 = [[mark(tt)]] [[active(isQid(u))]] = 0 >= 0 = [[mark(tt)]] [[mark(!6220!6220(_x0, _x1))]] = x0 + x1 >= x0 + x1 = [[active(!6220!6220(mark(_x0), mark(_x1)))]] [[mark(nil)]] = 0 >= 0 = [[active(nil)]] [[mark(U11(_x0))]] = x0 >= x0 = [[active(U11(mark(_x0)))]] [[mark(tt)]] = 0 >= 0 = [[active(tt)]] [[mark(U21(_x0, _x1))]] = x0 + x1 >= x0 + x1 = [[active(U21(mark(_x0), _x1))]] [[mark(U22(_x0))]] = x0 >= x0 = [[active(U22(mark(_x0)))]] [[mark(isList(_x0))]] = x0 >= x0 = [[active(isList(_x0))]] [[mark(U31(_x0))]] = x0 >= x0 = [[active(U31(mark(_x0)))]] [[mark(U41(_x0, _x1))]] = x0 + x1 >= x0 + x1 = [[active(U41(mark(_x0), _x1))]] [[mark(U42(_x0))]] = x0 >= x0 = [[active(U42(mark(_x0)))]] [[mark(isNeList(_x0))]] = x0 >= x0 = [[active(isNeList(_x0))]] [[mark(U51(_x0, _x1))]] = 1 + x0 + 2x1 >= 1 + x0 + 2x1 = [[active(U51(mark(_x0), _x1))]] [[mark(U52(_x0))]] = 2x0 >= 2x0 = [[active(U52(mark(_x0)))]] [[mark(U61(_x0))]] = x0 >= x0 = [[active(U61(mark(_x0)))]] [[mark(U71(_x0, _x1))]] = 1 + x0 + 2x1 >= 1 + x0 + 2x1 = [[active(U71(mark(_x0), _x1))]] [[mark(U72(_x0))]] = x0 >= x0 = [[active(U72(mark(_x0)))]] [[mark(isPal(_x0))]] = 1 + x0 >= 1 + x0 = [[active(isPal(_x0))]] [[mark(U81(_x0))]] = x0 >= x0 = [[active(U81(mark(_x0)))]] [[mark(isQid(_x0))]] = x0 >= x0 = [[active(isQid(_x0))]] [[mark(isNePal(_x0))]] = 1 + x0 >= 1 + x0 = [[active(isNePal(_x0))]] [[mark(a)]] = 1 >= 1 = [[active(a)]] [[mark(e)]] = 0 >= 0 = [[active(e)]] [[mark(i)]] = 0 >= 0 = [[active(i)]] [[mark(o)]] = 0 >= 0 = [[active(o)]] [[mark(u)]] = 0 >= 0 = [[active(u)]] [[!6220!6220(mark(_x0), _x1)]] = x0 + x1 >= x0 + x1 = [[!6220!6220(_x0, _x1)]] [[!6220!6220(_x0, mark(_x1))]] = x0 + x1 >= x0 + x1 = [[!6220!6220(_x0, _x1)]] [[!6220!6220(active(_x0), _x1)]] = x0 + x1 >= x0 + x1 = [[!6220!6220(_x0, _x1)]] [[!6220!6220(_x0, active(_x1))]] = x0 + x1 >= x0 + x1 = [[!6220!6220(_x0, _x1)]] [[U11(mark(_x0))]] = x0 >= x0 = [[U11(_x0)]] [[U11(active(_x0))]] = x0 >= x0 = [[U11(_x0)]] [[U21(mark(_x0), _x1)]] = x0 + x1 >= x0 + x1 = [[U21(_x0, _x1)]] [[U21(_x0, mark(_x1))]] = x0 + x1 >= x0 + x1 = [[U21(_x0, _x1)]] [[U21(active(_x0), _x1)]] = x0 + x1 >= x0 + x1 = [[U21(_x0, _x1)]] [[U21(_x0, active(_x1))]] = x0 + x1 >= x0 + x1 = [[U21(_x0, _x1)]] [[U22(mark(_x0))]] = x0 >= x0 = [[U22(_x0)]] [[U22(active(_x0))]] = x0 >= x0 = [[U22(_x0)]] [[isList(mark(_x0))]] = x0 >= x0 = [[isList(_x0)]] [[isList(active(_x0))]] = x0 >= x0 = [[isList(_x0)]] [[U31(mark(_x0))]] = x0 >= x0 = [[U31(_x0)]] [[U31(active(_x0))]] = x0 >= x0 = [[U31(_x0)]] [[U41(mark(_x0), _x1)]] = x0 + x1 >= x0 + x1 = [[U41(_x0, _x1)]] [[U41(_x0, mark(_x1))]] = x0 + x1 >= x0 + x1 = [[U41(_x0, _x1)]] [[U41(active(_x0), _x1)]] = x0 + x1 >= x0 + x1 = [[U41(_x0, _x1)]] [[U41(_x0, active(_x1))]] = x0 + x1 >= x0 + x1 = [[U41(_x0, _x1)]] [[U42(mark(_x0))]] = x0 >= x0 = [[U42(_x0)]] [[U42(active(_x0))]] = x0 >= x0 = [[U42(_x0)]] [[isNeList(mark(_x0))]] = x0 >= x0 = [[isNeList(_x0)]] [[isNeList(active(_x0))]] = x0 >= x0 = [[isNeList(_x0)]] [[U51(mark(_x0), _x1)]] = 1 + x0 + 2x1 >= 1 + x0 + 2x1 = [[U51(_x0, _x1)]] [[U51(_x0, mark(_x1))]] = 1 + x0 + 2x1 >= 1 + x0 + 2x1 = [[U51(_x0, _x1)]] [[U51(active(_x0), _x1)]] = 1 + x0 + 2x1 >= 1 + x0 + 2x1 = [[U51(_x0, _x1)]] [[U51(_x0, active(_x1))]] = 1 + x0 + 2x1 >= 1 + x0 + 2x1 = [[U51(_x0, _x1)]] [[U52(mark(_x0))]] = 2x0 >= 2x0 = [[U52(_x0)]] [[U52(active(_x0))]] = 2x0 >= 2x0 = [[U52(_x0)]] [[U61(mark(_x0))]] = x0 >= x0 = [[U61(_x0)]] [[U61(active(_x0))]] = x0 >= x0 = [[U61(_x0)]] [[U71(mark(_x0), _x1)]] = 1 + x0 + 2x1 >= 1 + x0 + 2x1 = [[U71(_x0, _x1)]] [[U71(_x0, mark(_x1))]] = 1 + x0 + 2x1 >= 1 + x0 + 2x1 = [[U71(_x0, _x1)]] [[U71(active(_x0), _x1)]] = 1 + x0 + 2x1 >= 1 + x0 + 2x1 = [[U71(_x0, _x1)]] [[U71(_x0, active(_x1))]] = 1 + x0 + 2x1 >= 1 + x0 + 2x1 = [[U71(_x0, _x1)]] [[U72(mark(_x0))]] = x0 >= x0 = [[U72(_x0)]] [[U72(active(_x0))]] = x0 >= x0 = [[U72(_x0)]] [[isPal(mark(_x0))]] = 1 + x0 >= 1 + x0 = [[isPal(_x0)]] [[isPal(active(_x0))]] = 1 + x0 >= 1 + x0 = [[isPal(_x0)]] [[U81(mark(_x0))]] = x0 >= x0 = [[U81(_x0)]] [[U81(active(_x0))]] = x0 >= x0 = [[U81(_x0)]] [[isQid(mark(_x0))]] = x0 >= x0 = [[isQid(_x0)]] [[isQid(active(_x0))]] = x0 >= x0 = [[isQid(_x0)]] [[isNePal(mark(_x0))]] = 1 + x0 >= 1 + x0 = [[isNePal(_x0)]] [[isNePal(active(_x0))]] = 1 + x0 >= 1 + x0 = [[isNePal(_x0)]] We can thus remove the following rules: active(U51(tt, X)) => mark(U52(isList(X))) active(isNePal(X)) => mark(U61(isQid(X))) active(isPal(nil)) => mark(tt) We use rule removal, following [Kop12, Theorem 2.23]. This gives the following requirements (possibly using Theorems 2.25 and 2.26 in [Kop12]): active(U11(tt)) >? mark(tt) active(U21(tt, X)) >? mark(U22(isList(X))) active(U22(tt)) >? mark(tt) active(U31(tt)) >? mark(tt) active(U61(tt)) >? mark(tt) active(U71(tt, X)) >? mark(U72(isPal(X))) active(U72(tt)) >? mark(tt) active(U81(tt)) >? mark(tt) active(isList(X)) >? mark(U11(isNeList(X))) active(isList(nil)) >? mark(tt) active(isNeList(X)) >? mark(U31(isQid(X))) active(isNeList(!6220!6220(X, Y))) >? mark(U41(isList(X), Y)) active(isPal(X)) >? mark(U81(isNePal(X))) active(isQid(o)) >? mark(tt) active(isQid(u)) >? mark(tt) mark(!6220!6220(X, Y)) >? active(!6220!6220(mark(X), mark(Y))) mark(nil) >? active(nil) mark(U11(X)) >? active(U11(mark(X))) mark(tt) >? active(tt) mark(U21(X, Y)) >? active(U21(mark(X), Y)) mark(U22(X)) >? active(U22(mark(X))) mark(isList(X)) >? active(isList(X)) mark(U31(X)) >? active(U31(mark(X))) mark(U41(X, Y)) >? active(U41(mark(X), Y)) mark(U42(X)) >? active(U42(mark(X))) mark(isNeList(X)) >? active(isNeList(X)) mark(U51(X, Y)) >? active(U51(mark(X), Y)) mark(U52(X)) >? active(U52(mark(X))) mark(U61(X)) >? active(U61(mark(X))) mark(U71(X, Y)) >? active(U71(mark(X), Y)) mark(U72(X)) >? active(U72(mark(X))) mark(isPal(X)) >? active(isPal(X)) mark(U81(X)) >? active(U81(mark(X))) mark(isQid(X)) >? active(isQid(X)) mark(isNePal(X)) >? active(isNePal(X)) mark(a) >? active(a) mark(e) >? active(e) mark(i) >? active(i) mark(o) >? active(o) mark(u) >? active(u) !6220!6220(mark(X), Y) >? !6220!6220(X, Y) !6220!6220(X, mark(Y)) >? !6220!6220(X, Y) !6220!6220(active(X), Y) >? !6220!6220(X, Y) !6220!6220(X, active(Y)) >? !6220!6220(X, Y) U11(mark(X)) >? U11(X) U11(active(X)) >? U11(X) U21(mark(X), Y) >? U21(X, Y) U21(X, mark(Y)) >? U21(X, Y) U21(active(X), Y) >? U21(X, Y) U21(X, active(Y)) >? U21(X, Y) U22(mark(X)) >? U22(X) U22(active(X)) >? U22(X) isList(mark(X)) >? isList(X) isList(active(X)) >? isList(X) U31(mark(X)) >? U31(X) U31(active(X)) >? U31(X) U41(mark(X), Y) >? U41(X, Y) U41(X, mark(Y)) >? U41(X, Y) U41(active(X), Y) >? U41(X, Y) U41(X, active(Y)) >? U41(X, Y) U42(mark(X)) >? U42(X) U42(active(X)) >? U42(X) isNeList(mark(X)) >? isNeList(X) isNeList(active(X)) >? isNeList(X) U51(mark(X), Y) >? U51(X, Y) U51(X, mark(Y)) >? U51(X, Y) U51(active(X), Y) >? U51(X, Y) U51(X, active(Y)) >? U51(X, Y) U52(mark(X)) >? U52(X) U52(active(X)) >? U52(X) U61(mark(X)) >? U61(X) U61(active(X)) >? U61(X) U71(mark(X), Y) >? U71(X, Y) U71(X, mark(Y)) >? U71(X, Y) U71(active(X), Y) >? U71(X, Y) U71(X, active(Y)) >? U71(X, Y) U72(mark(X)) >? U72(X) U72(active(X)) >? U72(X) isPal(mark(X)) >? isPal(X) isPal(active(X)) >? isPal(X) U81(mark(X)) >? U81(X) U81(active(X)) >? U81(X) isQid(mark(X)) >? isQid(X) isQid(active(X)) >? isQid(X) isNePal(mark(X)) >? isNePal(X) isNePal(active(X)) >? isNePal(X) We orient these requirements with a polynomial interpretation in the natural numbers. The following interpretation satisfies the requirements: !6220!6220 = \y0y1.2 + y1 + 2y0 U11 = \y0.y0 U21 = \y0y1.3 + 2y0 + 3y1 U22 = \y0.y0 U31 = \y0.y0 U41 = \y0y1.y1 + 2y0 U42 = \y0.y0 U51 = \y0y1.y0 + y1 U52 = \y0.y0 U61 = \y0.y0 U71 = \y0y1.1 + y0 + 2y1 U72 = \y0.y0 U81 = \y0.y0 a = 0 active = \y0.y0 e = 0 i = 0 isList = \y0.2 + 3y0 isNeList = \y0.2 + 3y0 isNePal = \y0.2y0 isPal = \y0.2y0 isQid = \y0.2 + 2y0 mark = \y0.y0 nil = 0 o = 1 tt = 0 u = 0 Using this interpretation, the requirements translate to: [[active(U11(tt))]] = 0 >= 0 = [[mark(tt)]] [[active(U21(tt, _x0))]] = 3 + 3x0 > 2 + 3x0 = [[mark(U22(isList(_x0)))]] [[active(U22(tt))]] = 0 >= 0 = [[mark(tt)]] [[active(U31(tt))]] = 0 >= 0 = [[mark(tt)]] [[active(U61(tt))]] = 0 >= 0 = [[mark(tt)]] [[active(U71(tt, _x0))]] = 1 + 2x0 > 2x0 = [[mark(U72(isPal(_x0)))]] [[active(U72(tt))]] = 0 >= 0 = [[mark(tt)]] [[active(U81(tt))]] = 0 >= 0 = [[mark(tt)]] [[active(isList(_x0))]] = 2 + 3x0 >= 2 + 3x0 = [[mark(U11(isNeList(_x0)))]] [[active(isList(nil))]] = 2 > 0 = [[mark(tt)]] [[active(isNeList(_x0))]] = 2 + 3x0 >= 2 + 2x0 = [[mark(U31(isQid(_x0)))]] [[active(isNeList(!6220!6220(_x0, _x1)))]] = 8 + 3x1 + 6x0 > 4 + x1 + 6x0 = [[mark(U41(isList(_x0), _x1))]] [[active(isPal(_x0))]] = 2x0 >= 2x0 = [[mark(U81(isNePal(_x0)))]] [[active(isQid(o))]] = 4 > 0 = [[mark(tt)]] [[active(isQid(u))]] = 2 > 0 = [[mark(tt)]] [[mark(!6220!6220(_x0, _x1))]] = 2 + x1 + 2x0 >= 2 + x1 + 2x0 = [[active(!6220!6220(mark(_x0), mark(_x1)))]] [[mark(nil)]] = 0 >= 0 = [[active(nil)]] [[mark(U11(_x0))]] = x0 >= x0 = [[active(U11(mark(_x0)))]] [[mark(tt)]] = 0 >= 0 = [[active(tt)]] [[mark(U21(_x0, _x1))]] = 3 + 2x0 + 3x1 >= 3 + 2x0 + 3x1 = [[active(U21(mark(_x0), _x1))]] [[mark(U22(_x0))]] = x0 >= x0 = [[active(U22(mark(_x0)))]] [[mark(isList(_x0))]] = 2 + 3x0 >= 2 + 3x0 = [[active(isList(_x0))]] [[mark(U31(_x0))]] = x0 >= x0 = [[active(U31(mark(_x0)))]] [[mark(U41(_x0, _x1))]] = x1 + 2x0 >= x1 + 2x0 = [[active(U41(mark(_x0), _x1))]] [[mark(U42(_x0))]] = x0 >= x0 = [[active(U42(mark(_x0)))]] [[mark(isNeList(_x0))]] = 2 + 3x0 >= 2 + 3x0 = [[active(isNeList(_x0))]] [[mark(U51(_x0, _x1))]] = x0 + x1 >= x0 + x1 = [[active(U51(mark(_x0), _x1))]] [[mark(U52(_x0))]] = x0 >= x0 = [[active(U52(mark(_x0)))]] [[mark(U61(_x0))]] = x0 >= x0 = [[active(U61(mark(_x0)))]] [[mark(U71(_x0, _x1))]] = 1 + x0 + 2x1 >= 1 + x0 + 2x1 = [[active(U71(mark(_x0), _x1))]] [[mark(U72(_x0))]] = x0 >= x0 = [[active(U72(mark(_x0)))]] [[mark(isPal(_x0))]] = 2x0 >= 2x0 = [[active(isPal(_x0))]] [[mark(U81(_x0))]] = x0 >= x0 = [[active(U81(mark(_x0)))]] [[mark(isQid(_x0))]] = 2 + 2x0 >= 2 + 2x0 = [[active(isQid(_x0))]] [[mark(isNePal(_x0))]] = 2x0 >= 2x0 = [[active(isNePal(_x0))]] [[mark(a)]] = 0 >= 0 = [[active(a)]] [[mark(e)]] = 0 >= 0 = [[active(e)]] [[mark(i)]] = 0 >= 0 = [[active(i)]] [[mark(o)]] = 1 >= 1 = [[active(o)]] [[mark(u)]] = 0 >= 0 = [[active(u)]] [[!6220!6220(mark(_x0), _x1)]] = 2 + x1 + 2x0 >= 2 + x1 + 2x0 = [[!6220!6220(_x0, _x1)]] [[!6220!6220(_x0, mark(_x1))]] = 2 + x1 + 2x0 >= 2 + x1 + 2x0 = [[!6220!6220(_x0, _x1)]] [[!6220!6220(active(_x0), _x1)]] = 2 + x1 + 2x0 >= 2 + x1 + 2x0 = [[!6220!6220(_x0, _x1)]] [[!6220!6220(_x0, active(_x1))]] = 2 + x1 + 2x0 >= 2 + x1 + 2x0 = [[!6220!6220(_x0, _x1)]] [[U11(mark(_x0))]] = x0 >= x0 = [[U11(_x0)]] [[U11(active(_x0))]] = x0 >= x0 = [[U11(_x0)]] [[U21(mark(_x0), _x1)]] = 3 + 2x0 + 3x1 >= 3 + 2x0 + 3x1 = [[U21(_x0, _x1)]] [[U21(_x0, mark(_x1))]] = 3 + 2x0 + 3x1 >= 3 + 2x0 + 3x1 = [[U21(_x0, _x1)]] [[U21(active(_x0), _x1)]] = 3 + 2x0 + 3x1 >= 3 + 2x0 + 3x1 = [[U21(_x0, _x1)]] [[U21(_x0, active(_x1))]] = 3 + 2x0 + 3x1 >= 3 + 2x0 + 3x1 = [[U21(_x0, _x1)]] [[U22(mark(_x0))]] = x0 >= x0 = [[U22(_x0)]] [[U22(active(_x0))]] = x0 >= x0 = [[U22(_x0)]] [[isList(mark(_x0))]] = 2 + 3x0 >= 2 + 3x0 = [[isList(_x0)]] [[isList(active(_x0))]] = 2 + 3x0 >= 2 + 3x0 = [[isList(_x0)]] [[U31(mark(_x0))]] = x0 >= x0 = [[U31(_x0)]] [[U31(active(_x0))]] = x0 >= x0 = [[U31(_x0)]] [[U41(mark(_x0), _x1)]] = x1 + 2x0 >= x1 + 2x0 = [[U41(_x0, _x1)]] [[U41(_x0, mark(_x1))]] = x1 + 2x0 >= x1 + 2x0 = [[U41(_x0, _x1)]] [[U41(active(_x0), _x1)]] = x1 + 2x0 >= x1 + 2x0 = [[U41(_x0, _x1)]] [[U41(_x0, active(_x1))]] = x1 + 2x0 >= x1 + 2x0 = [[U41(_x0, _x1)]] [[U42(mark(_x0))]] = x0 >= x0 = [[U42(_x0)]] [[U42(active(_x0))]] = x0 >= x0 = [[U42(_x0)]] [[isNeList(mark(_x0))]] = 2 + 3x0 >= 2 + 3x0 = [[isNeList(_x0)]] [[isNeList(active(_x0))]] = 2 + 3x0 >= 2 + 3x0 = [[isNeList(_x0)]] [[U51(mark(_x0), _x1)]] = x0 + x1 >= x0 + x1 = [[U51(_x0, _x1)]] [[U51(_x0, mark(_x1))]] = x0 + x1 >= x0 + x1 = [[U51(_x0, _x1)]] [[U51(active(_x0), _x1)]] = x0 + x1 >= x0 + x1 = [[U51(_x0, _x1)]] [[U51(_x0, active(_x1))]] = x0 + x1 >= x0 + x1 = [[U51(_x0, _x1)]] [[U52(mark(_x0))]] = x0 >= x0 = [[U52(_x0)]] [[U52(active(_x0))]] = x0 >= x0 = [[U52(_x0)]] [[U61(mark(_x0))]] = x0 >= x0 = [[U61(_x0)]] [[U61(active(_x0))]] = x0 >= x0 = [[U61(_x0)]] [[U71(mark(_x0), _x1)]] = 1 + x0 + 2x1 >= 1 + x0 + 2x1 = [[U71(_x0, _x1)]] [[U71(_x0, mark(_x1))]] = 1 + x0 + 2x1 >= 1 + x0 + 2x1 = [[U71(_x0, _x1)]] [[U71(active(_x0), _x1)]] = 1 + x0 + 2x1 >= 1 + x0 + 2x1 = [[U71(_x0, _x1)]] [[U71(_x0, active(_x1))]] = 1 + x0 + 2x1 >= 1 + x0 + 2x1 = [[U71(_x0, _x1)]] [[U72(mark(_x0))]] = x0 >= x0 = [[U72(_x0)]] [[U72(active(_x0))]] = x0 >= x0 = [[U72(_x0)]] [[isPal(mark(_x0))]] = 2x0 >= 2x0 = [[isPal(_x0)]] [[isPal(active(_x0))]] = 2x0 >= 2x0 = [[isPal(_x0)]] [[U81(mark(_x0))]] = x0 >= x0 = [[U81(_x0)]] [[U81(active(_x0))]] = x0 >= x0 = [[U81(_x0)]] [[isQid(mark(_x0))]] = 2 + 2x0 >= 2 + 2x0 = [[isQid(_x0)]] [[isQid(active(_x0))]] = 2 + 2x0 >= 2 + 2x0 = [[isQid(_x0)]] [[isNePal(mark(_x0))]] = 2x0 >= 2x0 = [[isNePal(_x0)]] [[isNePal(active(_x0))]] = 2x0 >= 2x0 = [[isNePal(_x0)]] We can thus remove the following rules: active(U21(tt, X)) => mark(U22(isList(X))) active(U71(tt, X)) => mark(U72(isPal(X))) active(isList(nil)) => mark(tt) active(isNeList(!6220!6220(X, Y))) => mark(U41(isList(X), Y)) active(isQid(o)) => mark(tt) active(isQid(u)) => mark(tt) We use rule removal, following [Kop12, Theorem 2.23]. This gives the following requirements (possibly using Theorems 2.25 and 2.26 in [Kop12]): active(U11(tt)) >? mark(tt) active(U22(tt)) >? mark(tt) active(U31(tt)) >? mark(tt) active(U61(tt)) >? mark(tt) active(U72(tt)) >? mark(tt) active(U81(tt)) >? mark(tt) active(isList(X)) >? mark(U11(isNeList(X))) active(isNeList(X)) >? mark(U31(isQid(X))) active(isPal(X)) >? mark(U81(isNePal(X))) mark(!6220!6220(X, Y)) >? active(!6220!6220(mark(X), mark(Y))) mark(nil) >? active(nil) mark(U11(X)) >? active(U11(mark(X))) mark(tt) >? active(tt) mark(U21(X, Y)) >? active(U21(mark(X), Y)) mark(U22(X)) >? active(U22(mark(X))) mark(isList(X)) >? active(isList(X)) mark(U31(X)) >? active(U31(mark(X))) mark(U41(X, Y)) >? active(U41(mark(X), Y)) mark(U42(X)) >? active(U42(mark(X))) mark(isNeList(X)) >? active(isNeList(X)) mark(U51(X, Y)) >? active(U51(mark(X), Y)) mark(U52(X)) >? active(U52(mark(X))) mark(U61(X)) >? active(U61(mark(X))) mark(U71(X, Y)) >? active(U71(mark(X), Y)) mark(U72(X)) >? active(U72(mark(X))) mark(isPal(X)) >? active(isPal(X)) mark(U81(X)) >? active(U81(mark(X))) mark(isQid(X)) >? active(isQid(X)) mark(isNePal(X)) >? active(isNePal(X)) mark(a) >? active(a) mark(e) >? active(e) mark(i) >? active(i) mark(o) >? active(o) mark(u) >? active(u) !6220!6220(mark(X), Y) >? !6220!6220(X, Y) !6220!6220(X, mark(Y)) >? !6220!6220(X, Y) !6220!6220(active(X), Y) >? !6220!6220(X, Y) !6220!6220(X, active(Y)) >? !6220!6220(X, Y) U11(mark(X)) >? U11(X) U11(active(X)) >? U11(X) U21(mark(X), Y) >? U21(X, Y) U21(X, mark(Y)) >? U21(X, Y) U21(active(X), Y) >? U21(X, Y) U21(X, active(Y)) >? U21(X, Y) U22(mark(X)) >? U22(X) U22(active(X)) >? U22(X) isList(mark(X)) >? isList(X) isList(active(X)) >? isList(X) U31(mark(X)) >? U31(X) U31(active(X)) >? U31(X) U41(mark(X), Y) >? U41(X, Y) U41(X, mark(Y)) >? U41(X, Y) U41(active(X), Y) >? U41(X, Y) U41(X, active(Y)) >? U41(X, Y) U42(mark(X)) >? U42(X) U42(active(X)) >? U42(X) isNeList(mark(X)) >? isNeList(X) isNeList(active(X)) >? isNeList(X) U51(mark(X), Y) >? U51(X, Y) U51(X, mark(Y)) >? U51(X, Y) U51(active(X), Y) >? U51(X, Y) U51(X, active(Y)) >? U51(X, Y) U52(mark(X)) >? U52(X) U52(active(X)) >? U52(X) U61(mark(X)) >? U61(X) U61(active(X)) >? U61(X) U71(mark(X), Y) >? U71(X, Y) U71(X, mark(Y)) >? U71(X, Y) U71(active(X), Y) >? U71(X, Y) U71(X, active(Y)) >? U71(X, Y) U72(mark(X)) >? U72(X) U72(active(X)) >? U72(X) isPal(mark(X)) >? isPal(X) isPal(active(X)) >? isPal(X) U81(mark(X)) >? U81(X) U81(active(X)) >? U81(X) isQid(mark(X)) >? isQid(X) isQid(active(X)) >? isQid(X) isNePal(mark(X)) >? isNePal(X) isNePal(active(X)) >? isNePal(X) We orient these requirements with a polynomial interpretation in the natural numbers. The following interpretation satisfies the requirements: !6220!6220 = \y0y1.1 + y0 + y1 U11 = \y0.y0 U21 = \y0y1.y0 + y1 U22 = \y0.1 + y0 U31 = \y0.y0 U41 = \y0y1.y0 + 2y1 U42 = \y0.y0 U51 = \y0y1.1 + y0 + y1 U52 = \y0.y0 U61 = \y0.y0 U71 = \y0y1.y0 + y1 U72 = \y0.y0 U81 = \y0.y0 a = 0 active = \y0.y0 e = 0 i = 3 isList = \y0.y0 isNeList = \y0.y0 isNePal = \y0.y0 isPal = \y0.2y0 isQid = \y0.y0 mark = \y0.y0 nil = 0 o = 0 tt = 0 u = 0 Using this interpretation, the requirements translate to: [[active(U11(tt))]] = 0 >= 0 = [[mark(tt)]] [[active(U22(tt))]] = 1 > 0 = [[mark(tt)]] [[active(U31(tt))]] = 0 >= 0 = [[mark(tt)]] [[active(U61(tt))]] = 0 >= 0 = [[mark(tt)]] [[active(U72(tt))]] = 0 >= 0 = [[mark(tt)]] [[active(U81(tt))]] = 0 >= 0 = [[mark(tt)]] [[active(isList(_x0))]] = x0 >= x0 = [[mark(U11(isNeList(_x0)))]] [[active(isNeList(_x0))]] = x0 >= x0 = [[mark(U31(isQid(_x0)))]] [[active(isPal(_x0))]] = 2x0 >= x0 = [[mark(U81(isNePal(_x0)))]] [[mark(!6220!6220(_x0, _x1))]] = 1 + x0 + x1 >= 1 + x0 + x1 = [[active(!6220!6220(mark(_x0), mark(_x1)))]] [[mark(nil)]] = 0 >= 0 = [[active(nil)]] [[mark(U11(_x0))]] = x0 >= x0 = [[active(U11(mark(_x0)))]] [[mark(tt)]] = 0 >= 0 = [[active(tt)]] [[mark(U21(_x0, _x1))]] = x0 + x1 >= x0 + x1 = [[active(U21(mark(_x0), _x1))]] [[mark(U22(_x0))]] = 1 + x0 >= 1 + x0 = [[active(U22(mark(_x0)))]] [[mark(isList(_x0))]] = x0 >= x0 = [[active(isList(_x0))]] [[mark(U31(_x0))]] = x0 >= x0 = [[active(U31(mark(_x0)))]] [[mark(U41(_x0, _x1))]] = x0 + 2x1 >= x0 + 2x1 = [[active(U41(mark(_x0), _x1))]] [[mark(U42(_x0))]] = x0 >= x0 = [[active(U42(mark(_x0)))]] [[mark(isNeList(_x0))]] = x0 >= x0 = [[active(isNeList(_x0))]] [[mark(U51(_x0, _x1))]] = 1 + x0 + x1 >= 1 + x0 + x1 = [[active(U51(mark(_x0), _x1))]] [[mark(U52(_x0))]] = x0 >= x0 = [[active(U52(mark(_x0)))]] [[mark(U61(_x0))]] = x0 >= x0 = [[active(U61(mark(_x0)))]] [[mark(U71(_x0, _x1))]] = x0 + x1 >= x0 + x1 = [[active(U71(mark(_x0), _x1))]] [[mark(U72(_x0))]] = x0 >= x0 = [[active(U72(mark(_x0)))]] [[mark(isPal(_x0))]] = 2x0 >= 2x0 = [[active(isPal(_x0))]] [[mark(U81(_x0))]] = x0 >= x0 = [[active(U81(mark(_x0)))]] [[mark(isQid(_x0))]] = x0 >= x0 = [[active(isQid(_x0))]] [[mark(isNePal(_x0))]] = x0 >= x0 = [[active(isNePal(_x0))]] [[mark(a)]] = 0 >= 0 = [[active(a)]] [[mark(e)]] = 0 >= 0 = [[active(e)]] [[mark(i)]] = 3 >= 3 = [[active(i)]] [[mark(o)]] = 0 >= 0 = [[active(o)]] [[mark(u)]] = 0 >= 0 = [[active(u)]] [[!6220!6220(mark(_x0), _x1)]] = 1 + x0 + x1 >= 1 + x0 + x1 = [[!6220!6220(_x0, _x1)]] [[!6220!6220(_x0, mark(_x1))]] = 1 + x0 + x1 >= 1 + x0 + x1 = [[!6220!6220(_x0, _x1)]] [[!6220!6220(active(_x0), _x1)]] = 1 + x0 + x1 >= 1 + x0 + x1 = [[!6220!6220(_x0, _x1)]] [[!6220!6220(_x0, active(_x1))]] = 1 + x0 + x1 >= 1 + x0 + x1 = [[!6220!6220(_x0, _x1)]] [[U11(mark(_x0))]] = x0 >= x0 = [[U11(_x0)]] [[U11(active(_x0))]] = x0 >= x0 = [[U11(_x0)]] [[U21(mark(_x0), _x1)]] = x0 + x1 >= x0 + x1 = [[U21(_x0, _x1)]] [[U21(_x0, mark(_x1))]] = x0 + x1 >= x0 + x1 = [[U21(_x0, _x1)]] [[U21(active(_x0), _x1)]] = x0 + x1 >= x0 + x1 = [[U21(_x0, _x1)]] [[U21(_x0, active(_x1))]] = x0 + x1 >= x0 + x1 = [[U21(_x0, _x1)]] [[U22(mark(_x0))]] = 1 + x0 >= 1 + x0 = [[U22(_x0)]] [[U22(active(_x0))]] = 1 + x0 >= 1 + x0 = [[U22(_x0)]] [[isList(mark(_x0))]] = x0 >= x0 = [[isList(_x0)]] [[isList(active(_x0))]] = x0 >= x0 = [[isList(_x0)]] [[U31(mark(_x0))]] = x0 >= x0 = [[U31(_x0)]] [[U31(active(_x0))]] = x0 >= x0 = [[U31(_x0)]] [[U41(mark(_x0), _x1)]] = x0 + 2x1 >= x0 + 2x1 = [[U41(_x0, _x1)]] [[U41(_x0, mark(_x1))]] = x0 + 2x1 >= x0 + 2x1 = [[U41(_x0, _x1)]] [[U41(active(_x0), _x1)]] = x0 + 2x1 >= x0 + 2x1 = [[U41(_x0, _x1)]] [[U41(_x0, active(_x1))]] = x0 + 2x1 >= x0 + 2x1 = [[U41(_x0, _x1)]] [[U42(mark(_x0))]] = x0 >= x0 = [[U42(_x0)]] [[U42(active(_x0))]] = x0 >= x0 = [[U42(_x0)]] [[isNeList(mark(_x0))]] = x0 >= x0 = [[isNeList(_x0)]] [[isNeList(active(_x0))]] = x0 >= x0 = [[isNeList(_x0)]] [[U51(mark(_x0), _x1)]] = 1 + x0 + x1 >= 1 + x0 + x1 = [[U51(_x0, _x1)]] [[U51(_x0, mark(_x1))]] = 1 + x0 + x1 >= 1 + x0 + x1 = [[U51(_x0, _x1)]] [[U51(active(_x0), _x1)]] = 1 + x0 + x1 >= 1 + x0 + x1 = [[U51(_x0, _x1)]] [[U51(_x0, active(_x1))]] = 1 + x0 + x1 >= 1 + x0 + x1 = [[U51(_x0, _x1)]] [[U52(mark(_x0))]] = x0 >= x0 = [[U52(_x0)]] [[U52(active(_x0))]] = x0 >= x0 = [[U52(_x0)]] [[U61(mark(_x0))]] = x0 >= x0 = [[U61(_x0)]] [[U61(active(_x0))]] = x0 >= x0 = [[U61(_x0)]] [[U71(mark(_x0), _x1)]] = x0 + x1 >= x0 + x1 = [[U71(_x0, _x1)]] [[U71(_x0, mark(_x1))]] = x0 + x1 >= x0 + x1 = [[U71(_x0, _x1)]] [[U71(active(_x0), _x1)]] = x0 + x1 >= x0 + x1 = [[U71(_x0, _x1)]] [[U71(_x0, active(_x1))]] = x0 + x1 >= x0 + x1 = [[U71(_x0, _x1)]] [[U72(mark(_x0))]] = x0 >= x0 = [[U72(_x0)]] [[U72(active(_x0))]] = x0 >= x0 = [[U72(_x0)]] [[isPal(mark(_x0))]] = 2x0 >= 2x0 = [[isPal(_x0)]] [[isPal(active(_x0))]] = 2x0 >= 2x0 = [[isPal(_x0)]] [[U81(mark(_x0))]] = x0 >= x0 = [[U81(_x0)]] [[U81(active(_x0))]] = x0 >= x0 = [[U81(_x0)]] [[isQid(mark(_x0))]] = x0 >= x0 = [[isQid(_x0)]] [[isQid(active(_x0))]] = x0 >= x0 = [[isQid(_x0)]] [[isNePal(mark(_x0))]] = x0 >= x0 = [[isNePal(_x0)]] [[isNePal(active(_x0))]] = x0 >= x0 = [[isNePal(_x0)]] We can thus remove the following rules: active(U22(tt)) => mark(tt) We use rule removal, following [Kop12, Theorem 2.23]. This gives the following requirements (possibly using Theorems 2.25 and 2.26 in [Kop12]): active(U11(tt)) >? mark(tt) active(U31(tt)) >? mark(tt) active(U61(tt)) >? mark(tt) active(U72(tt)) >? mark(tt) active(U81(tt)) >? mark(tt) active(isList(X)) >? mark(U11(isNeList(X))) active(isNeList(X)) >? mark(U31(isQid(X))) active(isPal(X)) >? mark(U81(isNePal(X))) mark(!6220!6220(X, Y)) >? active(!6220!6220(mark(X), mark(Y))) mark(nil) >? active(nil) mark(U11(X)) >? active(U11(mark(X))) mark(tt) >? active(tt) mark(U21(X, Y)) >? active(U21(mark(X), Y)) mark(U22(X)) >? active(U22(mark(X))) mark(isList(X)) >? active(isList(X)) mark(U31(X)) >? active(U31(mark(X))) mark(U41(X, Y)) >? active(U41(mark(X), Y)) mark(U42(X)) >? active(U42(mark(X))) mark(isNeList(X)) >? active(isNeList(X)) mark(U51(X, Y)) >? active(U51(mark(X), Y)) mark(U52(X)) >? active(U52(mark(X))) mark(U61(X)) >? active(U61(mark(X))) mark(U71(X, Y)) >? active(U71(mark(X), Y)) mark(U72(X)) >? active(U72(mark(X))) mark(isPal(X)) >? active(isPal(X)) mark(U81(X)) >? active(U81(mark(X))) mark(isQid(X)) >? active(isQid(X)) mark(isNePal(X)) >? active(isNePal(X)) mark(a) >? active(a) mark(e) >? active(e) mark(i) >? active(i) mark(o) >? active(o) mark(u) >? active(u) !6220!6220(mark(X), Y) >? !6220!6220(X, Y) !6220!6220(X, mark(Y)) >? !6220!6220(X, Y) !6220!6220(active(X), Y) >? !6220!6220(X, Y) !6220!6220(X, active(Y)) >? !6220!6220(X, Y) U11(mark(X)) >? U11(X) U11(active(X)) >? U11(X) U21(mark(X), Y) >? U21(X, Y) U21(X, mark(Y)) >? U21(X, Y) U21(active(X), Y) >? U21(X, Y) U21(X, active(Y)) >? U21(X, Y) U22(mark(X)) >? U22(X) U22(active(X)) >? U22(X) isList(mark(X)) >? isList(X) isList(active(X)) >? isList(X) U31(mark(X)) >? U31(X) U31(active(X)) >? U31(X) U41(mark(X), Y) >? U41(X, Y) U41(X, mark(Y)) >? U41(X, Y) U41(active(X), Y) >? U41(X, Y) U41(X, active(Y)) >? U41(X, Y) U42(mark(X)) >? U42(X) U42(active(X)) >? U42(X) isNeList(mark(X)) >? isNeList(X) isNeList(active(X)) >? isNeList(X) U51(mark(X), Y) >? U51(X, Y) U51(X, mark(Y)) >? U51(X, Y) U51(active(X), Y) >? U51(X, Y) U51(X, active(Y)) >? U51(X, Y) U52(mark(X)) >? U52(X) U52(active(X)) >? U52(X) U61(mark(X)) >? U61(X) U61(active(X)) >? U61(X) U71(mark(X), Y) >? U71(X, Y) U71(X, mark(Y)) >? U71(X, Y) U71(active(X), Y) >? U71(X, Y) U71(X, active(Y)) >? U71(X, Y) U72(mark(X)) >? U72(X) U72(active(X)) >? U72(X) isPal(mark(X)) >? isPal(X) isPal(active(X)) >? isPal(X) U81(mark(X)) >? U81(X) U81(active(X)) >? U81(X) isQid(mark(X)) >? isQid(X) isQid(active(X)) >? isQid(X) isNePal(mark(X)) >? isNePal(X) isNePal(active(X)) >? isNePal(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 = \y0.y0 U21 = \y0y1.y0 + y1 U22 = \y0.y0 U31 = \y0.1 + y0 U41 = \y0y1.y0 + y1 U42 = \y0.y0 U51 = \y0y1.y0 + y1 U52 = \y0.y0 U61 = \y0.y0 U71 = \y0y1.y0 + y1 U72 = \y0.y0 U81 = \y0.2y0 a = 0 active = \y0.y0 e = 0 i = 0 isList = \y0.2 + 2y0 isNeList = \y0.2 + 2y0 isNePal = \y0.y0 isPal = \y0.2y0 isQid = \y0.2y0 mark = \y0.y0 nil = 0 o = 0 tt = 0 u = 0 Using this interpretation, the requirements translate to: [[active(U11(tt))]] = 0 >= 0 = [[mark(tt)]] [[active(U31(tt))]] = 1 > 0 = [[mark(tt)]] [[active(U61(tt))]] = 0 >= 0 = [[mark(tt)]] [[active(U72(tt))]] = 0 >= 0 = [[mark(tt)]] [[active(U81(tt))]] = 0 >= 0 = [[mark(tt)]] [[active(isList(_x0))]] = 2 + 2x0 >= 2 + 2x0 = [[mark(U11(isNeList(_x0)))]] [[active(isNeList(_x0))]] = 2 + 2x0 > 1 + 2x0 = [[mark(U31(isQid(_x0)))]] [[active(isPal(_x0))]] = 2x0 >= 2x0 = [[mark(U81(isNePal(_x0)))]] [[mark(!6220!6220(_x0, _x1))]] = x0 + x1 >= x0 + x1 = [[active(!6220!6220(mark(_x0), mark(_x1)))]] [[mark(nil)]] = 0 >= 0 = [[active(nil)]] [[mark(U11(_x0))]] = x0 >= x0 = [[active(U11(mark(_x0)))]] [[mark(tt)]] = 0 >= 0 = [[active(tt)]] [[mark(U21(_x0, _x1))]] = x0 + x1 >= x0 + x1 = [[active(U21(mark(_x0), _x1))]] [[mark(U22(_x0))]] = x0 >= x0 = [[active(U22(mark(_x0)))]] [[mark(isList(_x0))]] = 2 + 2x0 >= 2 + 2x0 = [[active(isList(_x0))]] [[mark(U31(_x0))]] = 1 + x0 >= 1 + x0 = [[active(U31(mark(_x0)))]] [[mark(U41(_x0, _x1))]] = x0 + x1 >= x0 + x1 = [[active(U41(mark(_x0), _x1))]] [[mark(U42(_x0))]] = x0 >= x0 = [[active(U42(mark(_x0)))]] [[mark(isNeList(_x0))]] = 2 + 2x0 >= 2 + 2x0 = [[active(isNeList(_x0))]] [[mark(U51(_x0, _x1))]] = x0 + x1 >= x0 + x1 = [[active(U51(mark(_x0), _x1))]] [[mark(U52(_x0))]] = x0 >= x0 = [[active(U52(mark(_x0)))]] [[mark(U61(_x0))]] = x0 >= x0 = [[active(U61(mark(_x0)))]] [[mark(U71(_x0, _x1))]] = x0 + x1 >= x0 + x1 = [[active(U71(mark(_x0), _x1))]] [[mark(U72(_x0))]] = x0 >= x0 = [[active(U72(mark(_x0)))]] [[mark(isPal(_x0))]] = 2x0 >= 2x0 = [[active(isPal(_x0))]] [[mark(U81(_x0))]] = 2x0 >= 2x0 = [[active(U81(mark(_x0)))]] [[mark(isQid(_x0))]] = 2x0 >= 2x0 = [[active(isQid(_x0))]] [[mark(isNePal(_x0))]] = x0 >= x0 = [[active(isNePal(_x0))]] [[mark(a)]] = 0 >= 0 = [[active(a)]] [[mark(e)]] = 0 >= 0 = [[active(e)]] [[mark(i)]] = 0 >= 0 = [[active(i)]] [[mark(o)]] = 0 >= 0 = [[active(o)]] [[mark(u)]] = 0 >= 0 = [[active(u)]] [[!6220!6220(mark(_x0), _x1)]] = x0 + x1 >= x0 + x1 = [[!6220!6220(_x0, _x1)]] [[!6220!6220(_x0, mark(_x1))]] = x0 + x1 >= x0 + x1 = [[!6220!6220(_x0, _x1)]] [[!6220!6220(active(_x0), _x1)]] = x0 + x1 >= x0 + x1 = [[!6220!6220(_x0, _x1)]] [[!6220!6220(_x0, active(_x1))]] = x0 + x1 >= x0 + x1 = [[!6220!6220(_x0, _x1)]] [[U11(mark(_x0))]] = x0 >= x0 = [[U11(_x0)]] [[U11(active(_x0))]] = x0 >= x0 = [[U11(_x0)]] [[U21(mark(_x0), _x1)]] = x0 + x1 >= x0 + x1 = [[U21(_x0, _x1)]] [[U21(_x0, mark(_x1))]] = x0 + x1 >= x0 + x1 = [[U21(_x0, _x1)]] [[U21(active(_x0), _x1)]] = x0 + x1 >= x0 + x1 = [[U21(_x0, _x1)]] [[U21(_x0, active(_x1))]] = x0 + x1 >= x0 + x1 = [[U21(_x0, _x1)]] [[U22(mark(_x0))]] = x0 >= x0 = [[U22(_x0)]] [[U22(active(_x0))]] = x0 >= x0 = [[U22(_x0)]] [[isList(mark(_x0))]] = 2 + 2x0 >= 2 + 2x0 = [[isList(_x0)]] [[isList(active(_x0))]] = 2 + 2x0 >= 2 + 2x0 = [[isList(_x0)]] [[U31(mark(_x0))]] = 1 + x0 >= 1 + x0 = [[U31(_x0)]] [[U31(active(_x0))]] = 1 + x0 >= 1 + x0 = [[U31(_x0)]] [[U41(mark(_x0), _x1)]] = x0 + x1 >= x0 + x1 = [[U41(_x0, _x1)]] [[U41(_x0, mark(_x1))]] = x0 + x1 >= x0 + x1 = [[U41(_x0, _x1)]] [[U41(active(_x0), _x1)]] = x0 + x1 >= x0 + x1 = [[U41(_x0, _x1)]] [[U41(_x0, active(_x1))]] = x0 + x1 >= x0 + x1 = [[U41(_x0, _x1)]] [[U42(mark(_x0))]] = x0 >= x0 = [[U42(_x0)]] [[U42(active(_x0))]] = x0 >= x0 = [[U42(_x0)]] [[isNeList(mark(_x0))]] = 2 + 2x0 >= 2 + 2x0 = [[isNeList(_x0)]] [[isNeList(active(_x0))]] = 2 + 2x0 >= 2 + 2x0 = [[isNeList(_x0)]] [[U51(mark(_x0), _x1)]] = x0 + x1 >= x0 + x1 = [[U51(_x0, _x1)]] [[U51(_x0, mark(_x1))]] = x0 + x1 >= x0 + x1 = [[U51(_x0, _x1)]] [[U51(active(_x0), _x1)]] = x0 + x1 >= x0 + x1 = [[U51(_x0, _x1)]] [[U51(_x0, active(_x1))]] = x0 + x1 >= x0 + x1 = [[U51(_x0, _x1)]] [[U52(mark(_x0))]] = x0 >= x0 = [[U52(_x0)]] [[U52(active(_x0))]] = x0 >= x0 = [[U52(_x0)]] [[U61(mark(_x0))]] = x0 >= x0 = [[U61(_x0)]] [[U61(active(_x0))]] = x0 >= x0 = [[U61(_x0)]] [[U71(mark(_x0), _x1)]] = x0 + x1 >= x0 + x1 = [[U71(_x0, _x1)]] [[U71(_x0, mark(_x1))]] = x0 + x1 >= x0 + x1 = [[U71(_x0, _x1)]] [[U71(active(_x0), _x1)]] = x0 + x1 >= x0 + x1 = [[U71(_x0, _x1)]] [[U71(_x0, active(_x1))]] = x0 + x1 >= x0 + x1 = [[U71(_x0, _x1)]] [[U72(mark(_x0))]] = x0 >= x0 = [[U72(_x0)]] [[U72(active(_x0))]] = x0 >= x0 = [[U72(_x0)]] [[isPal(mark(_x0))]] = 2x0 >= 2x0 = [[isPal(_x0)]] [[isPal(active(_x0))]] = 2x0 >= 2x0 = [[isPal(_x0)]] [[U81(mark(_x0))]] = 2x0 >= 2x0 = [[U81(_x0)]] [[U81(active(_x0))]] = 2x0 >= 2x0 = [[U81(_x0)]] [[isQid(mark(_x0))]] = 2x0 >= 2x0 = [[isQid(_x0)]] [[isQid(active(_x0))]] = 2x0 >= 2x0 = [[isQid(_x0)]] [[isNePal(mark(_x0))]] = x0 >= x0 = [[isNePal(_x0)]] [[isNePal(active(_x0))]] = x0 >= x0 = [[isNePal(_x0)]] We can thus remove the following rules: active(U31(tt)) => mark(tt) active(isNeList(X)) => mark(U31(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]): active(U11(tt)) >? mark(tt) active(U61(tt)) >? mark(tt) active(U72(tt)) >? mark(tt) active(U81(tt)) >? mark(tt) active(isList(X)) >? mark(U11(isNeList(X))) active(isPal(X)) >? mark(U81(isNePal(X))) mark(!6220!6220(X, Y)) >? active(!6220!6220(mark(X), mark(Y))) mark(nil) >? active(nil) mark(U11(X)) >? active(U11(mark(X))) mark(tt) >? active(tt) mark(U21(X, Y)) >? active(U21(mark(X), Y)) mark(U22(X)) >? active(U22(mark(X))) mark(isList(X)) >? active(isList(X)) mark(U31(X)) >? active(U31(mark(X))) mark(U41(X, Y)) >? active(U41(mark(X), Y)) mark(U42(X)) >? active(U42(mark(X))) mark(isNeList(X)) >? active(isNeList(X)) mark(U51(X, Y)) >? active(U51(mark(X), Y)) mark(U52(X)) >? active(U52(mark(X))) mark(U61(X)) >? active(U61(mark(X))) mark(U71(X, Y)) >? active(U71(mark(X), Y)) mark(U72(X)) >? active(U72(mark(X))) mark(isPal(X)) >? active(isPal(X)) mark(U81(X)) >? active(U81(mark(X))) mark(isQid(X)) >? active(isQid(X)) mark(isNePal(X)) >? active(isNePal(X)) mark(a) >? active(a) mark(e) >? active(e) mark(i) >? active(i) mark(o) >? active(o) mark(u) >? active(u) !6220!6220(mark(X), Y) >? !6220!6220(X, Y) !6220!6220(X, mark(Y)) >? !6220!6220(X, Y) !6220!6220(active(X), Y) >? !6220!6220(X, Y) !6220!6220(X, active(Y)) >? !6220!6220(X, Y) U11(mark(X)) >? U11(X) U11(active(X)) >? U11(X) U21(mark(X), Y) >? U21(X, Y) U21(X, mark(Y)) >? U21(X, Y) U21(active(X), Y) >? U21(X, Y) U21(X, active(Y)) >? U21(X, Y) U22(mark(X)) >? U22(X) U22(active(X)) >? U22(X) isList(mark(X)) >? isList(X) isList(active(X)) >? isList(X) U31(mark(X)) >? U31(X) U31(active(X)) >? U31(X) U41(mark(X), Y) >? U41(X, Y) U41(X, mark(Y)) >? U41(X, Y) U41(active(X), Y) >? U41(X, Y) U41(X, active(Y)) >? U41(X, Y) U42(mark(X)) >? U42(X) U42(active(X)) >? U42(X) isNeList(mark(X)) >? isNeList(X) isNeList(active(X)) >? isNeList(X) U51(mark(X), Y) >? U51(X, Y) U51(X, mark(Y)) >? U51(X, Y) U51(active(X), Y) >? U51(X, Y) U51(X, active(Y)) >? U51(X, Y) U52(mark(X)) >? U52(X) U52(active(X)) >? U52(X) U61(mark(X)) >? U61(X) U61(active(X)) >? U61(X) U71(mark(X), Y) >? U71(X, Y) U71(X, mark(Y)) >? U71(X, Y) U71(active(X), Y) >? U71(X, Y) U71(X, active(Y)) >? U71(X, Y) U72(mark(X)) >? U72(X) U72(active(X)) >? U72(X) isPal(mark(X)) >? isPal(X) isPal(active(X)) >? isPal(X) U81(mark(X)) >? U81(X) U81(active(X)) >? U81(X) isQid(mark(X)) >? isQid(X) isQid(active(X)) >? isQid(X) isNePal(mark(X)) >? isNePal(X) isNePal(active(X)) >? isNePal(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 = \y0.y0 U21 = \y0y1.y0 + 2y1 U22 = \y0.2 + y0 U31 = \y0.2 + y0 U41 = \y0y1.y0 + 2y1 U42 = \y0.y0 U51 = \y0y1.y0 + 2y1 U52 = \y0.y0 U61 = \y0.y0 U71 = \y0y1.2y0 + 2y1 U72 = \y0.2 + y0 U81 = \y0.y0 a = 0 active = \y0.y0 e = 0 i = 1 isList = \y0.1 + 2y0 isNeList = \y0.y0 isNePal = \y0.y0 isPal = \y0.2y0 isQid = \y0.y0 mark = \y0.2y0 nil = 1 o = 1 tt = 0 u = 0 Using this interpretation, the requirements translate to: [[active(U11(tt))]] = 0 >= 0 = [[mark(tt)]] [[active(U61(tt))]] = 0 >= 0 = [[mark(tt)]] [[active(U72(tt))]] = 2 > 0 = [[mark(tt)]] [[active(U81(tt))]] = 0 >= 0 = [[mark(tt)]] [[active(isList(_x0))]] = 1 + 2x0 > 2x0 = [[mark(U11(isNeList(_x0)))]] [[active(isPal(_x0))]] = 2x0 >= 2x0 = [[mark(U81(isNePal(_x0)))]] [[mark(!6220!6220(_x0, _x1))]] = 2x0 + 2x1 >= 2x0 + 2x1 = [[active(!6220!6220(mark(_x0), mark(_x1)))]] [[mark(nil)]] = 2 > 1 = [[active(nil)]] [[mark(U11(_x0))]] = 2x0 >= 2x0 = [[active(U11(mark(_x0)))]] [[mark(tt)]] = 0 >= 0 = [[active(tt)]] [[mark(U21(_x0, _x1))]] = 2x0 + 4x1 >= 2x0 + 2x1 = [[active(U21(mark(_x0), _x1))]] [[mark(U22(_x0))]] = 4 + 2x0 > 2 + 2x0 = [[active(U22(mark(_x0)))]] [[mark(isList(_x0))]] = 2 + 4x0 > 1 + 2x0 = [[active(isList(_x0))]] [[mark(U31(_x0))]] = 4 + 2x0 > 2 + 2x0 = [[active(U31(mark(_x0)))]] [[mark(U41(_x0, _x1))]] = 2x0 + 4x1 >= 2x0 + 2x1 = [[active(U41(mark(_x0), _x1))]] [[mark(U42(_x0))]] = 2x0 >= 2x0 = [[active(U42(mark(_x0)))]] [[mark(isNeList(_x0))]] = 2x0 >= x0 = [[active(isNeList(_x0))]] [[mark(U51(_x0, _x1))]] = 2x0 + 4x1 >= 2x0 + 2x1 = [[active(U51(mark(_x0), _x1))]] [[mark(U52(_x0))]] = 2x0 >= 2x0 = [[active(U52(mark(_x0)))]] [[mark(U61(_x0))]] = 2x0 >= 2x0 = [[active(U61(mark(_x0)))]] [[mark(U71(_x0, _x1))]] = 4x0 + 4x1 >= 2x1 + 4x0 = [[active(U71(mark(_x0), _x1))]] [[mark(U72(_x0))]] = 4 + 2x0 > 2 + 2x0 = [[active(U72(mark(_x0)))]] [[mark(isPal(_x0))]] = 4x0 >= 2x0 = [[active(isPal(_x0))]] [[mark(U81(_x0))]] = 2x0 >= 2x0 = [[active(U81(mark(_x0)))]] [[mark(isQid(_x0))]] = 2x0 >= x0 = [[active(isQid(_x0))]] [[mark(isNePal(_x0))]] = 2x0 >= x0 = [[active(isNePal(_x0))]] [[mark(a)]] = 0 >= 0 = [[active(a)]] [[mark(e)]] = 0 >= 0 = [[active(e)]] [[mark(i)]] = 2 > 1 = [[active(i)]] [[mark(o)]] = 2 > 1 = [[active(o)]] [[mark(u)]] = 0 >= 0 = [[active(u)]] [[!6220!6220(mark(_x0), _x1)]] = x1 + 2x0 >= x0 + x1 = [[!6220!6220(_x0, _x1)]] [[!6220!6220(_x0, mark(_x1))]] = x0 + 2x1 >= x0 + x1 = [[!6220!6220(_x0, _x1)]] [[!6220!6220(active(_x0), _x1)]] = x0 + x1 >= x0 + x1 = [[!6220!6220(_x0, _x1)]] [[!6220!6220(_x0, active(_x1))]] = x0 + x1 >= x0 + x1 = [[!6220!6220(_x0, _x1)]] [[U11(mark(_x0))]] = 2x0 >= x0 = [[U11(_x0)]] [[U11(active(_x0))]] = x0 >= x0 = [[U11(_x0)]] [[U21(mark(_x0), _x1)]] = 2x0 + 2x1 >= x0 + 2x1 = [[U21(_x0, _x1)]] [[U21(_x0, mark(_x1))]] = x0 + 4x1 >= x0 + 2x1 = [[U21(_x0, _x1)]] [[U21(active(_x0), _x1)]] = x0 + 2x1 >= x0 + 2x1 = [[U21(_x0, _x1)]] [[U21(_x0, active(_x1))]] = x0 + 2x1 >= x0 + 2x1 = [[U21(_x0, _x1)]] [[U22(mark(_x0))]] = 2 + 2x0 >= 2 + x0 = [[U22(_x0)]] [[U22(active(_x0))]] = 2 + x0 >= 2 + x0 = [[U22(_x0)]] [[isList(mark(_x0))]] = 1 + 4x0 >= 1 + 2x0 = [[isList(_x0)]] [[isList(active(_x0))]] = 1 + 2x0 >= 1 + 2x0 = [[isList(_x0)]] [[U31(mark(_x0))]] = 2 + 2x0 >= 2 + x0 = [[U31(_x0)]] [[U31(active(_x0))]] = 2 + x0 >= 2 + x0 = [[U31(_x0)]] [[U41(mark(_x0), _x1)]] = 2x0 + 2x1 >= x0 + 2x1 = [[U41(_x0, _x1)]] [[U41(_x0, mark(_x1))]] = x0 + 4x1 >= x0 + 2x1 = [[U41(_x0, _x1)]] [[U41(active(_x0), _x1)]] = x0 + 2x1 >= x0 + 2x1 = [[U41(_x0, _x1)]] [[U41(_x0, active(_x1))]] = x0 + 2x1 >= x0 + 2x1 = [[U41(_x0, _x1)]] [[U42(mark(_x0))]] = 2x0 >= x0 = [[U42(_x0)]] [[U42(active(_x0))]] = x0 >= x0 = [[U42(_x0)]] [[isNeList(mark(_x0))]] = 2x0 >= x0 = [[isNeList(_x0)]] [[isNeList(active(_x0))]] = x0 >= x0 = [[isNeList(_x0)]] [[U51(mark(_x0), _x1)]] = 2x0 + 2x1 >= x0 + 2x1 = [[U51(_x0, _x1)]] [[U51(_x0, mark(_x1))]] = x0 + 4x1 >= x0 + 2x1 = [[U51(_x0, _x1)]] [[U51(active(_x0), _x1)]] = x0 + 2x1 >= x0 + 2x1 = [[U51(_x0, _x1)]] [[U51(_x0, active(_x1))]] = x0 + 2x1 >= x0 + 2x1 = [[U51(_x0, _x1)]] [[U52(mark(_x0))]] = 2x0 >= x0 = [[U52(_x0)]] [[U52(active(_x0))]] = x0 >= x0 = [[U52(_x0)]] [[U61(mark(_x0))]] = 2x0 >= x0 = [[U61(_x0)]] [[U61(active(_x0))]] = x0 >= x0 = [[U61(_x0)]] [[U71(mark(_x0), _x1)]] = 2x1 + 4x0 >= 2x0 + 2x1 = [[U71(_x0, _x1)]] [[U71(_x0, mark(_x1))]] = 2x0 + 4x1 >= 2x0 + 2x1 = [[U71(_x0, _x1)]] [[U71(active(_x0), _x1)]] = 2x0 + 2x1 >= 2x0 + 2x1 = [[U71(_x0, _x1)]] [[U71(_x0, active(_x1))]] = 2x0 + 2x1 >= 2x0 + 2x1 = [[U71(_x0, _x1)]] [[U72(mark(_x0))]] = 2 + 2x0 >= 2 + x0 = [[U72(_x0)]] [[U72(active(_x0))]] = 2 + x0 >= 2 + x0 = [[U72(_x0)]] [[isPal(mark(_x0))]] = 4x0 >= 2x0 = [[isPal(_x0)]] [[isPal(active(_x0))]] = 2x0 >= 2x0 = [[isPal(_x0)]] [[U81(mark(_x0))]] = 2x0 >= x0 = [[U81(_x0)]] [[U81(active(_x0))]] = x0 >= x0 = [[U81(_x0)]] [[isQid(mark(_x0))]] = 2x0 >= x0 = [[isQid(_x0)]] [[isQid(active(_x0))]] = x0 >= x0 = [[isQid(_x0)]] [[isNePal(mark(_x0))]] = 2x0 >= x0 = [[isNePal(_x0)]] [[isNePal(active(_x0))]] = x0 >= x0 = [[isNePal(_x0)]] We can thus remove the following rules: active(U72(tt)) => mark(tt) active(isList(X)) => mark(U11(isNeList(X))) mark(nil) => active(nil) mark(U22(X)) => active(U22(mark(X))) mark(isList(X)) => active(isList(X)) mark(U31(X)) => active(U31(mark(X))) mark(U72(X)) => active(U72(mark(X))) mark(i) => active(i) mark(o) => active(o) We use rule removal, following [Kop12, Theorem 2.23]. This gives the following requirements (possibly using Theorems 2.25 and 2.26 in [Kop12]): active(U11(tt)) >? mark(tt) active(U61(tt)) >? mark(tt) active(U81(tt)) >? mark(tt) active(isPal(X)) >? mark(U81(isNePal(X))) mark(!6220!6220(X, Y)) >? active(!6220!6220(mark(X), mark(Y))) mark(U11(X)) >? active(U11(mark(X))) mark(tt) >? active(tt) mark(U21(X, Y)) >? active(U21(mark(X), Y)) mark(U41(X, Y)) >? active(U41(mark(X), Y)) mark(U42(X)) >? active(U42(mark(X))) mark(isNeList(X)) >? active(isNeList(X)) mark(U51(X, Y)) >? active(U51(mark(X), Y)) mark(U52(X)) >? active(U52(mark(X))) mark(U61(X)) >? active(U61(mark(X))) mark(U71(X, Y)) >? active(U71(mark(X), Y)) mark(isPal(X)) >? active(isPal(X)) mark(U81(X)) >? active(U81(mark(X))) mark(isQid(X)) >? active(isQid(X)) mark(isNePal(X)) >? active(isNePal(X)) mark(a) >? active(a) mark(e) >? active(e) mark(u) >? active(u) !6220!6220(mark(X), Y) >? !6220!6220(X, Y) !6220!6220(X, mark(Y)) >? !6220!6220(X, Y) !6220!6220(active(X), Y) >? !6220!6220(X, Y) !6220!6220(X, active(Y)) >? !6220!6220(X, Y) U11(mark(X)) >? U11(X) U11(active(X)) >? U11(X) U21(mark(X), Y) >? U21(X, Y) U21(X, mark(Y)) >? U21(X, Y) U21(active(X), Y) >? U21(X, Y) U21(X, active(Y)) >? U21(X, Y) U22(mark(X)) >? U22(X) U22(active(X)) >? U22(X) isList(mark(X)) >? isList(X) isList(active(X)) >? isList(X) U31(mark(X)) >? U31(X) U31(active(X)) >? U31(X) U41(mark(X), Y) >? U41(X, Y) U41(X, mark(Y)) >? U41(X, Y) U41(active(X), Y) >? U41(X, Y) U41(X, active(Y)) >? U41(X, Y) U42(mark(X)) >? U42(X) U42(active(X)) >? U42(X) isNeList(mark(X)) >? isNeList(X) isNeList(active(X)) >? isNeList(X) U51(mark(X), Y) >? U51(X, Y) U51(X, mark(Y)) >? U51(X, Y) U51(active(X), Y) >? U51(X, Y) U51(X, active(Y)) >? U51(X, Y) U52(mark(X)) >? U52(X) U52(active(X)) >? U52(X) U61(mark(X)) >? U61(X) U61(active(X)) >? U61(X) U71(mark(X), Y) >? U71(X, Y) U71(X, mark(Y)) >? U71(X, Y) U71(active(X), Y) >? U71(X, Y) U71(X, active(Y)) >? U71(X, Y) U72(mark(X)) >? U72(X) U72(active(X)) >? U72(X) isPal(mark(X)) >? isPal(X) isPal(active(X)) >? isPal(X) U81(mark(X)) >? U81(X) U81(active(X)) >? U81(X) isQid(mark(X)) >? isQid(X) isQid(active(X)) >? isQid(X) isNePal(mark(X)) >? isNePal(X) isNePal(active(X)) >? isNePal(X) We orient these requirements with a polynomial interpretation in the natural numbers. The following interpretation satisfies the requirements: !6220!6220 = \y0y1.1 + y0 + y1 U11 = \y0.y0 U21 = \y0y1.y0 + 2y1 U22 = \y0.y0 U31 = \y0.y0 U41 = \y0y1.2 + y0 + y1 U42 = \y0.1 + y0 U51 = \y0y1.y0 + 2y1 U52 = \y0.y0 U61 = \y0.1 + y0 U71 = \y0y1.1 + y0 + 2y1 U72 = \y0.y0 U81 = \y0.y0 a = 2 active = \y0.y0 e = 0 isList = \y0.y0 isNeList = \y0.1 + 2y0 isNePal = \y0.y0 isPal = \y0.2y0 isQid = \y0.y0 mark = \y0.2y0 tt = 0 u = 2 Using this interpretation, the requirements translate to: [[active(U11(tt))]] = 0 >= 0 = [[mark(tt)]] [[active(U61(tt))]] = 1 > 0 = [[mark(tt)]] [[active(U81(tt))]] = 0 >= 0 = [[mark(tt)]] [[active(isPal(_x0))]] = 2x0 >= 2x0 = [[mark(U81(isNePal(_x0)))]] [[mark(!6220!6220(_x0, _x1))]] = 2 + 2x0 + 2x1 > 1 + 2x0 + 2x1 = [[active(!6220!6220(mark(_x0), mark(_x1)))]] [[mark(U11(_x0))]] = 2x0 >= 2x0 = [[active(U11(mark(_x0)))]] [[mark(tt)]] = 0 >= 0 = [[active(tt)]] [[mark(U21(_x0, _x1))]] = 2x0 + 4x1 >= 2x0 + 2x1 = [[active(U21(mark(_x0), _x1))]] [[mark(U41(_x0, _x1))]] = 4 + 2x0 + 2x1 > 2 + x1 + 2x0 = [[active(U41(mark(_x0), _x1))]] [[mark(U42(_x0))]] = 2 + 2x0 > 1 + 2x0 = [[active(U42(mark(_x0)))]] [[mark(isNeList(_x0))]] = 2 + 4x0 > 1 + 2x0 = [[active(isNeList(_x0))]] [[mark(U51(_x0, _x1))]] = 2x0 + 4x1 >= 2x0 + 2x1 = [[active(U51(mark(_x0), _x1))]] [[mark(U52(_x0))]] = 2x0 >= 2x0 = [[active(U52(mark(_x0)))]] [[mark(U61(_x0))]] = 2 + 2x0 > 1 + 2x0 = [[active(U61(mark(_x0)))]] [[mark(U71(_x0, _x1))]] = 2 + 2x0 + 4x1 > 1 + 2x0 + 2x1 = [[active(U71(mark(_x0), _x1))]] [[mark(isPal(_x0))]] = 4x0 >= 2x0 = [[active(isPal(_x0))]] [[mark(U81(_x0))]] = 2x0 >= 2x0 = [[active(U81(mark(_x0)))]] [[mark(isQid(_x0))]] = 2x0 >= x0 = [[active(isQid(_x0))]] [[mark(isNePal(_x0))]] = 2x0 >= x0 = [[active(isNePal(_x0))]] [[mark(a)]] = 4 > 2 = [[active(a)]] [[mark(e)]] = 0 >= 0 = [[active(e)]] [[mark(u)]] = 4 > 2 = [[active(u)]] [[!6220!6220(mark(_x0), _x1)]] = 1 + x1 + 2x0 >= 1 + x0 + x1 = [[!6220!6220(_x0, _x1)]] [[!6220!6220(_x0, mark(_x1))]] = 1 + x0 + 2x1 >= 1 + x0 + x1 = [[!6220!6220(_x0, _x1)]] [[!6220!6220(active(_x0), _x1)]] = 1 + x0 + x1 >= 1 + x0 + x1 = [[!6220!6220(_x0, _x1)]] [[!6220!6220(_x0, active(_x1))]] = 1 + x0 + x1 >= 1 + x0 + x1 = [[!6220!6220(_x0, _x1)]] [[U11(mark(_x0))]] = 2x0 >= x0 = [[U11(_x0)]] [[U11(active(_x0))]] = x0 >= x0 = [[U11(_x0)]] [[U21(mark(_x0), _x1)]] = 2x0 + 2x1 >= x0 + 2x1 = [[U21(_x0, _x1)]] [[U21(_x0, mark(_x1))]] = x0 + 4x1 >= x0 + 2x1 = [[U21(_x0, _x1)]] [[U21(active(_x0), _x1)]] = x0 + 2x1 >= x0 + 2x1 = [[U21(_x0, _x1)]] [[U21(_x0, active(_x1))]] = x0 + 2x1 >= x0 + 2x1 = [[U21(_x0, _x1)]] [[U22(mark(_x0))]] = 2x0 >= x0 = [[U22(_x0)]] [[U22(active(_x0))]] = x0 >= x0 = [[U22(_x0)]] [[isList(mark(_x0))]] = 2x0 >= x0 = [[isList(_x0)]] [[isList(active(_x0))]] = x0 >= x0 = [[isList(_x0)]] [[U31(mark(_x0))]] = 2x0 >= x0 = [[U31(_x0)]] [[U31(active(_x0))]] = x0 >= x0 = [[U31(_x0)]] [[U41(mark(_x0), _x1)]] = 2 + x1 + 2x0 >= 2 + x0 + x1 = [[U41(_x0, _x1)]] [[U41(_x0, mark(_x1))]] = 2 + x0 + 2x1 >= 2 + x0 + x1 = [[U41(_x0, _x1)]] [[U41(active(_x0), _x1)]] = 2 + x0 + x1 >= 2 + x0 + x1 = [[U41(_x0, _x1)]] [[U41(_x0, active(_x1))]] = 2 + x0 + x1 >= 2 + x0 + x1 = [[U41(_x0, _x1)]] [[U42(mark(_x0))]] = 1 + 2x0 >= 1 + x0 = [[U42(_x0)]] [[U42(active(_x0))]] = 1 + x0 >= 1 + x0 = [[U42(_x0)]] [[isNeList(mark(_x0))]] = 1 + 4x0 >= 1 + 2x0 = [[isNeList(_x0)]] [[isNeList(active(_x0))]] = 1 + 2x0 >= 1 + 2x0 = [[isNeList(_x0)]] [[U51(mark(_x0), _x1)]] = 2x0 + 2x1 >= x0 + 2x1 = [[U51(_x0, _x1)]] [[U51(_x0, mark(_x1))]] = x0 + 4x1 >= x0 + 2x1 = [[U51(_x0, _x1)]] [[U51(active(_x0), _x1)]] = x0 + 2x1 >= x0 + 2x1 = [[U51(_x0, _x1)]] [[U51(_x0, active(_x1))]] = x0 + 2x1 >= x0 + 2x1 = [[U51(_x0, _x1)]] [[U52(mark(_x0))]] = 2x0 >= x0 = [[U52(_x0)]] [[U52(active(_x0))]] = x0 >= x0 = [[U52(_x0)]] [[U61(mark(_x0))]] = 1 + 2x0 >= 1 + x0 = [[U61(_x0)]] [[U61(active(_x0))]] = 1 + x0 >= 1 + x0 = [[U61(_x0)]] [[U71(mark(_x0), _x1)]] = 1 + 2x0 + 2x1 >= 1 + x0 + 2x1 = [[U71(_x0, _x1)]] [[U71(_x0, mark(_x1))]] = 1 + x0 + 4x1 >= 1 + x0 + 2x1 = [[U71(_x0, _x1)]] [[U71(active(_x0), _x1)]] = 1 + x0 + 2x1 >= 1 + x0 + 2x1 = [[U71(_x0, _x1)]] [[U71(_x0, active(_x1))]] = 1 + x0 + 2x1 >= 1 + x0 + 2x1 = [[U71(_x0, _x1)]] [[U72(mark(_x0))]] = 2x0 >= x0 = [[U72(_x0)]] [[U72(active(_x0))]] = x0 >= x0 = [[U72(_x0)]] [[isPal(mark(_x0))]] = 4x0 >= 2x0 = [[isPal(_x0)]] [[isPal(active(_x0))]] = 2x0 >= 2x0 = [[isPal(_x0)]] [[U81(mark(_x0))]] = 2x0 >= x0 = [[U81(_x0)]] [[U81(active(_x0))]] = x0 >= x0 = [[U81(_x0)]] [[isQid(mark(_x0))]] = 2x0 >= x0 = [[isQid(_x0)]] [[isQid(active(_x0))]] = x0 >= x0 = [[isQid(_x0)]] [[isNePal(mark(_x0))]] = 2x0 >= x0 = [[isNePal(_x0)]] [[isNePal(active(_x0))]] = x0 >= x0 = [[isNePal(_x0)]] We can thus remove the following rules: active(U61(tt)) => mark(tt) mark(!6220!6220(X, Y)) => active(!6220!6220(mark(X), mark(Y))) mark(U41(X, Y)) => active(U41(mark(X), Y)) mark(U42(X)) => active(U42(mark(X))) mark(isNeList(X)) => active(isNeList(X)) mark(U61(X)) => active(U61(mark(X))) mark(U71(X, Y)) => active(U71(mark(X), Y)) mark(a) => active(a) mark(u) => active(u) We use rule removal, following [Kop12, Theorem 2.23]. This gives the following requirements (possibly using Theorems 2.25 and 2.26 in [Kop12]): active(U11(tt)) >? mark(tt) active(U81(tt)) >? mark(tt) active(isPal(X)) >? mark(U81(isNePal(X))) mark(U11(X)) >? active(U11(mark(X))) mark(tt) >? active(tt) mark(U21(X, Y)) >? active(U21(mark(X), Y)) mark(U51(X, Y)) >? active(U51(mark(X), Y)) mark(U52(X)) >? active(U52(mark(X))) mark(isPal(X)) >? active(isPal(X)) mark(U81(X)) >? active(U81(mark(X))) mark(isQid(X)) >? active(isQid(X)) mark(isNePal(X)) >? active(isNePal(X)) mark(e) >? active(e) !6220!6220(mark(X), Y) >? !6220!6220(X, Y) !6220!6220(X, mark(Y)) >? !6220!6220(X, Y) !6220!6220(active(X), Y) >? !6220!6220(X, Y) !6220!6220(X, active(Y)) >? !6220!6220(X, Y) U11(mark(X)) >? U11(X) U11(active(X)) >? U11(X) U21(mark(X), Y) >? U21(X, Y) U21(X, mark(Y)) >? U21(X, Y) U21(active(X), Y) >? U21(X, Y) U21(X, active(Y)) >? U21(X, Y) U22(mark(X)) >? U22(X) U22(active(X)) >? U22(X) isList(mark(X)) >? isList(X) isList(active(X)) >? isList(X) U31(mark(X)) >? U31(X) U31(active(X)) >? U31(X) U41(mark(X), Y) >? U41(X, Y) U41(X, mark(Y)) >? U41(X, Y) U41(active(X), Y) >? U41(X, Y) U41(X, active(Y)) >? U41(X, Y) U42(mark(X)) >? U42(X) U42(active(X)) >? U42(X) isNeList(mark(X)) >? isNeList(X) isNeList(active(X)) >? isNeList(X) U51(mark(X), Y) >? U51(X, Y) U51(X, mark(Y)) >? U51(X, Y) U51(active(X), Y) >? U51(X, Y) U51(X, active(Y)) >? U51(X, Y) U52(mark(X)) >? U52(X) U52(active(X)) >? U52(X) U61(mark(X)) >? U61(X) U61(active(X)) >? U61(X) U71(mark(X), Y) >? U71(X, Y) U71(X, mark(Y)) >? U71(X, Y) U71(active(X), Y) >? U71(X, Y) U71(X, active(Y)) >? U71(X, Y) U72(mark(X)) >? U72(X) U72(active(X)) >? U72(X) isPal(mark(X)) >? isPal(X) isPal(active(X)) >? isPal(X) U81(mark(X)) >? U81(X) U81(active(X)) >? U81(X) isQid(mark(X)) >? isQid(X) isQid(active(X)) >? isQid(X) isNePal(mark(X)) >? isNePal(X) isNePal(active(X)) >? isNePal(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 = \y0.1 + y0 U21 = \y0y1.y0 + 2y1 U22 = \y0.y0 U31 = \y0.y0 U41 = \y0y1.y1 + 2y0 U42 = \y0.y0 U51 = \y0y1.y0 + y1 U52 = \y0.y0 U61 = \y0.y0 U71 = \y0y1.y0 + y1 U72 = \y0.y0 U81 = \y0.y0 active = \y0.y0 e = 0 isList = \y0.y0 isNeList = \y0.y0 isNePal = \y0.y0 isPal = \y0.1 + 2y0 isQid = \y0.2y0 mark = \y0.2y0 tt = 0 Using this interpretation, the requirements translate to: [[active(U11(tt))]] = 1 > 0 = [[mark(tt)]] [[active(U81(tt))]] = 0 >= 0 = [[mark(tt)]] [[active(isPal(_x0))]] = 1 + 2x0 > 2x0 = [[mark(U81(isNePal(_x0)))]] [[mark(U11(_x0))]] = 2 + 2x0 > 1 + 2x0 = [[active(U11(mark(_x0)))]] [[mark(tt)]] = 0 >= 0 = [[active(tt)]] [[mark(U21(_x0, _x1))]] = 2x0 + 4x1 >= 2x0 + 2x1 = [[active(U21(mark(_x0), _x1))]] [[mark(U51(_x0, _x1))]] = 2x0 + 2x1 >= x1 + 2x0 = [[active(U51(mark(_x0), _x1))]] [[mark(U52(_x0))]] = 2x0 >= 2x0 = [[active(U52(mark(_x0)))]] [[mark(isPal(_x0))]] = 2 + 4x0 > 1 + 2x0 = [[active(isPal(_x0))]] [[mark(U81(_x0))]] = 2x0 >= 2x0 = [[active(U81(mark(_x0)))]] [[mark(isQid(_x0))]] = 4x0 >= 2x0 = [[active(isQid(_x0))]] [[mark(isNePal(_x0))]] = 2x0 >= x0 = [[active(isNePal(_x0))]] [[mark(e)]] = 0 >= 0 = [[active(e)]] [[!6220!6220(mark(_x0), _x1)]] = x1 + 2x0 >= x0 + x1 = [[!6220!6220(_x0, _x1)]] [[!6220!6220(_x0, mark(_x1))]] = x0 + 2x1 >= x0 + x1 = [[!6220!6220(_x0, _x1)]] [[!6220!6220(active(_x0), _x1)]] = x0 + x1 >= x0 + x1 = [[!6220!6220(_x0, _x1)]] [[!6220!6220(_x0, active(_x1))]] = x0 + x1 >= x0 + x1 = [[!6220!6220(_x0, _x1)]] [[U11(mark(_x0))]] = 1 + 2x0 >= 1 + x0 = [[U11(_x0)]] [[U11(active(_x0))]] = 1 + x0 >= 1 + x0 = [[U11(_x0)]] [[U21(mark(_x0), _x1)]] = 2x0 + 2x1 >= x0 + 2x1 = [[U21(_x0, _x1)]] [[U21(_x0, mark(_x1))]] = x0 + 4x1 >= x0 + 2x1 = [[U21(_x0, _x1)]] [[U21(active(_x0), _x1)]] = x0 + 2x1 >= x0 + 2x1 = [[U21(_x0, _x1)]] [[U21(_x0, active(_x1))]] = x0 + 2x1 >= x0 + 2x1 = [[U21(_x0, _x1)]] [[U22(mark(_x0))]] = 2x0 >= x0 = [[U22(_x0)]] [[U22(active(_x0))]] = x0 >= x0 = [[U22(_x0)]] [[isList(mark(_x0))]] = 2x0 >= x0 = [[isList(_x0)]] [[isList(active(_x0))]] = x0 >= x0 = [[isList(_x0)]] [[U31(mark(_x0))]] = 2x0 >= x0 = [[U31(_x0)]] [[U31(active(_x0))]] = x0 >= x0 = [[U31(_x0)]] [[U41(mark(_x0), _x1)]] = x1 + 4x0 >= x1 + 2x0 = [[U41(_x0, _x1)]] [[U41(_x0, mark(_x1))]] = 2x0 + 2x1 >= x1 + 2x0 = [[U41(_x0, _x1)]] [[U41(active(_x0), _x1)]] = x1 + 2x0 >= x1 + 2x0 = [[U41(_x0, _x1)]] [[U41(_x0, active(_x1))]] = x1 + 2x0 >= x1 + 2x0 = [[U41(_x0, _x1)]] [[U42(mark(_x0))]] = 2x0 >= x0 = [[U42(_x0)]] [[U42(active(_x0))]] = x0 >= x0 = [[U42(_x0)]] [[isNeList(mark(_x0))]] = 2x0 >= x0 = [[isNeList(_x0)]] [[isNeList(active(_x0))]] = x0 >= x0 = [[isNeList(_x0)]] [[U51(mark(_x0), _x1)]] = x1 + 2x0 >= x0 + x1 = [[U51(_x0, _x1)]] [[U51(_x0, mark(_x1))]] = x0 + 2x1 >= x0 + x1 = [[U51(_x0, _x1)]] [[U51(active(_x0), _x1)]] = x0 + x1 >= x0 + x1 = [[U51(_x0, _x1)]] [[U51(_x0, active(_x1))]] = x0 + x1 >= x0 + x1 = [[U51(_x0, _x1)]] [[U52(mark(_x0))]] = 2x0 >= x0 = [[U52(_x0)]] [[U52(active(_x0))]] = x0 >= x0 = [[U52(_x0)]] [[U61(mark(_x0))]] = 2x0 >= x0 = [[U61(_x0)]] [[U61(active(_x0))]] = x0 >= x0 = [[U61(_x0)]] [[U71(mark(_x0), _x1)]] = x1 + 2x0 >= x0 + x1 = [[U71(_x0, _x1)]] [[U71(_x0, mark(_x1))]] = x0 + 2x1 >= x0 + x1 = [[U71(_x0, _x1)]] [[U71(active(_x0), _x1)]] = x0 + x1 >= x0 + x1 = [[U71(_x0, _x1)]] [[U71(_x0, active(_x1))]] = x0 + x1 >= x0 + x1 = [[U71(_x0, _x1)]] [[U72(mark(_x0))]] = 2x0 >= x0 = [[U72(_x0)]] [[U72(active(_x0))]] = x0 >= x0 = [[U72(_x0)]] [[isPal(mark(_x0))]] = 1 + 4x0 >= 1 + 2x0 = [[isPal(_x0)]] [[isPal(active(_x0))]] = 1 + 2x0 >= 1 + 2x0 = [[isPal(_x0)]] [[U81(mark(_x0))]] = 2x0 >= x0 = [[U81(_x0)]] [[U81(active(_x0))]] = x0 >= x0 = [[U81(_x0)]] [[isQid(mark(_x0))]] = 4x0 >= 2x0 = [[isQid(_x0)]] [[isQid(active(_x0))]] = 2x0 >= 2x0 = [[isQid(_x0)]] [[isNePal(mark(_x0))]] = 2x0 >= x0 = [[isNePal(_x0)]] [[isNePal(active(_x0))]] = x0 >= x0 = [[isNePal(_x0)]] We can thus remove the following rules: active(U11(tt)) => mark(tt) active(isPal(X)) => mark(U81(isNePal(X))) mark(U11(X)) => active(U11(mark(X))) mark(isPal(X)) => active(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]): active(U81(tt)) >? mark(tt) mark(tt) >? active(tt) mark(U21(X, Y)) >? active(U21(mark(X), Y)) mark(U51(X, Y)) >? active(U51(mark(X), Y)) mark(U52(X)) >? active(U52(mark(X))) mark(U81(X)) >? active(U81(mark(X))) mark(isQid(X)) >? active(isQid(X)) mark(isNePal(X)) >? active(isNePal(X)) mark(e) >? active(e) !6220!6220(mark(X), Y) >? !6220!6220(X, Y) !6220!6220(X, mark(Y)) >? !6220!6220(X, Y) !6220!6220(active(X), Y) >? !6220!6220(X, Y) !6220!6220(X, active(Y)) >? !6220!6220(X, Y) U11(mark(X)) >? U11(X) U11(active(X)) >? U11(X) U21(mark(X), Y) >? U21(X, Y) U21(X, mark(Y)) >? U21(X, Y) U21(active(X), Y) >? U21(X, Y) U21(X, active(Y)) >? U21(X, Y) U22(mark(X)) >? U22(X) U22(active(X)) >? U22(X) isList(mark(X)) >? isList(X) isList(active(X)) >? isList(X) U31(mark(X)) >? U31(X) U31(active(X)) >? U31(X) U41(mark(X), Y) >? U41(X, Y) U41(X, mark(Y)) >? U41(X, Y) U41(active(X), Y) >? U41(X, Y) U41(X, active(Y)) >? U41(X, Y) U42(mark(X)) >? U42(X) U42(active(X)) >? U42(X) isNeList(mark(X)) >? isNeList(X) isNeList(active(X)) >? isNeList(X) U51(mark(X), Y) >? U51(X, Y) U51(X, mark(Y)) >? U51(X, Y) U51(active(X), Y) >? U51(X, Y) U51(X, active(Y)) >? U51(X, Y) U52(mark(X)) >? U52(X) U52(active(X)) >? U52(X) U61(mark(X)) >? U61(X) U61(active(X)) >? U61(X) U71(mark(X), Y) >? U71(X, Y) U71(X, mark(Y)) >? U71(X, Y) U71(active(X), Y) >? U71(X, Y) U71(X, active(Y)) >? U71(X, Y) U72(mark(X)) >? U72(X) U72(active(X)) >? U72(X) isPal(mark(X)) >? isPal(X) isPal(active(X)) >? isPal(X) U81(mark(X)) >? U81(X) U81(active(X)) >? U81(X) isQid(mark(X)) >? isQid(X) isQid(active(X)) >? isQid(X) isNePal(mark(X)) >? isNePal(X) isNePal(active(X)) >? isNePal(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 = \y0.2y0 U21 = \y0y1.1 + y0 + 2y1 U22 = \y0.y0 U31 = \y0.y0 U41 = \y0y1.2y0 + 2y1 U42 = \y0.y0 U51 = \y0y1.y0 + 2y1 U52 = \y0.1 + y0 U61 = \y0.y0 U71 = \y0y1.y0 + y1 U72 = \y0.2y0 U81 = \y0.y0 active = \y0.y0 e = 2 isList = \y0.2y0 isNeList = \y0.y0 isNePal = \y0.y0 isPal = \y0.2y0 isQid = \y0.y0 mark = \y0.2y0 tt = 0 Using this interpretation, the requirements translate to: [[active(U81(tt))]] = 0 >= 0 = [[mark(tt)]] [[mark(tt)]] = 0 >= 0 = [[active(tt)]] [[mark(U21(_x0, _x1))]] = 2 + 2x0 + 4x1 > 1 + 2x0 + 2x1 = [[active(U21(mark(_x0), _x1))]] [[mark(U51(_x0, _x1))]] = 2x0 + 4x1 >= 2x0 + 2x1 = [[active(U51(mark(_x0), _x1))]] [[mark(U52(_x0))]] = 2 + 2x0 > 1 + 2x0 = [[active(U52(mark(_x0)))]] [[mark(U81(_x0))]] = 2x0 >= 2x0 = [[active(U81(mark(_x0)))]] [[mark(isQid(_x0))]] = 2x0 >= x0 = [[active(isQid(_x0))]] [[mark(isNePal(_x0))]] = 2x0 >= x0 = [[active(isNePal(_x0))]] [[mark(e)]] = 4 > 2 = [[active(e)]] [[!6220!6220(mark(_x0), _x1)]] = x1 + 4x0 >= x1 + 2x0 = [[!6220!6220(_x0, _x1)]] [[!6220!6220(_x0, mark(_x1))]] = 2x0 + 2x1 >= x1 + 2x0 = [[!6220!6220(_x0, _x1)]] [[!6220!6220(active(_x0), _x1)]] = x1 + 2x0 >= x1 + 2x0 = [[!6220!6220(_x0, _x1)]] [[!6220!6220(_x0, active(_x1))]] = x1 + 2x0 >= x1 + 2x0 = [[!6220!6220(_x0, _x1)]] [[U11(mark(_x0))]] = 4x0 >= 2x0 = [[U11(_x0)]] [[U11(active(_x0))]] = 2x0 >= 2x0 = [[U11(_x0)]] [[U21(mark(_x0), _x1)]] = 1 + 2x0 + 2x1 >= 1 + x0 + 2x1 = [[U21(_x0, _x1)]] [[U21(_x0, mark(_x1))]] = 1 + x0 + 4x1 >= 1 + x0 + 2x1 = [[U21(_x0, _x1)]] [[U21(active(_x0), _x1)]] = 1 + x0 + 2x1 >= 1 + x0 + 2x1 = [[U21(_x0, _x1)]] [[U21(_x0, active(_x1))]] = 1 + x0 + 2x1 >= 1 + x0 + 2x1 = [[U21(_x0, _x1)]] [[U22(mark(_x0))]] = 2x0 >= x0 = [[U22(_x0)]] [[U22(active(_x0))]] = x0 >= x0 = [[U22(_x0)]] [[isList(mark(_x0))]] = 4x0 >= 2x0 = [[isList(_x0)]] [[isList(active(_x0))]] = 2x0 >= 2x0 = [[isList(_x0)]] [[U31(mark(_x0))]] = 2x0 >= x0 = [[U31(_x0)]] [[U31(active(_x0))]] = x0 >= x0 = [[U31(_x0)]] [[U41(mark(_x0), _x1)]] = 2x1 + 4x0 >= 2x0 + 2x1 = [[U41(_x0, _x1)]] [[U41(_x0, mark(_x1))]] = 2x0 + 4x1 >= 2x0 + 2x1 = [[U41(_x0, _x1)]] [[U41(active(_x0), _x1)]] = 2x0 + 2x1 >= 2x0 + 2x1 = [[U41(_x0, _x1)]] [[U41(_x0, active(_x1))]] = 2x0 + 2x1 >= 2x0 + 2x1 = [[U41(_x0, _x1)]] [[U42(mark(_x0))]] = 2x0 >= x0 = [[U42(_x0)]] [[U42(active(_x0))]] = x0 >= x0 = [[U42(_x0)]] [[isNeList(mark(_x0))]] = 2x0 >= x0 = [[isNeList(_x0)]] [[isNeList(active(_x0))]] = x0 >= x0 = [[isNeList(_x0)]] [[U51(mark(_x0), _x1)]] = 2x0 + 2x1 >= x0 + 2x1 = [[U51(_x0, _x1)]] [[U51(_x0, mark(_x1))]] = x0 + 4x1 >= x0 + 2x1 = [[U51(_x0, _x1)]] [[U51(active(_x0), _x1)]] = x0 + 2x1 >= x0 + 2x1 = [[U51(_x0, _x1)]] [[U51(_x0, active(_x1))]] = x0 + 2x1 >= x0 + 2x1 = [[U51(_x0, _x1)]] [[U52(mark(_x0))]] = 1 + 2x0 >= 1 + x0 = [[U52(_x0)]] [[U52(active(_x0))]] = 1 + x0 >= 1 + x0 = [[U52(_x0)]] [[U61(mark(_x0))]] = 2x0 >= x0 = [[U61(_x0)]] [[U61(active(_x0))]] = x0 >= x0 = [[U61(_x0)]] [[U71(mark(_x0), _x1)]] = x1 + 2x0 >= x0 + x1 = [[U71(_x0, _x1)]] [[U71(_x0, mark(_x1))]] = x0 + 2x1 >= x0 + x1 = [[U71(_x0, _x1)]] [[U71(active(_x0), _x1)]] = x0 + x1 >= x0 + x1 = [[U71(_x0, _x1)]] [[U71(_x0, active(_x1))]] = x0 + x1 >= x0 + x1 = [[U71(_x0, _x1)]] [[U72(mark(_x0))]] = 4x0 >= 2x0 = [[U72(_x0)]] [[U72(active(_x0))]] = 2x0 >= 2x0 = [[U72(_x0)]] [[isPal(mark(_x0))]] = 4x0 >= 2x0 = [[isPal(_x0)]] [[isPal(active(_x0))]] = 2x0 >= 2x0 = [[isPal(_x0)]] [[U81(mark(_x0))]] = 2x0 >= x0 = [[U81(_x0)]] [[U81(active(_x0))]] = x0 >= x0 = [[U81(_x0)]] [[isQid(mark(_x0))]] = 2x0 >= x0 = [[isQid(_x0)]] [[isQid(active(_x0))]] = x0 >= x0 = [[isQid(_x0)]] [[isNePal(mark(_x0))]] = 2x0 >= x0 = [[isNePal(_x0)]] [[isNePal(active(_x0))]] = x0 >= x0 = [[isNePal(_x0)]] We can thus remove the following rules: mark(U21(X, Y)) => active(U21(mark(X), Y)) mark(U52(X)) => active(U52(mark(X))) mark(e) => active(e) We use rule removal, following [Kop12, Theorem 2.23]. This gives the following requirements (possibly using Theorems 2.25 and 2.26 in [Kop12]): active(U81(tt)) >? mark(tt) mark(tt) >? active(tt) mark(U51(X, Y)) >? active(U51(mark(X), Y)) mark(U81(X)) >? active(U81(mark(X))) mark(isQid(X)) >? active(isQid(X)) mark(isNePal(X)) >? active(isNePal(X)) !6220!6220(mark(X), Y) >? !6220!6220(X, Y) !6220!6220(X, mark(Y)) >? !6220!6220(X, Y) !6220!6220(active(X), Y) >? !6220!6220(X, Y) !6220!6220(X, active(Y)) >? !6220!6220(X, Y) U11(mark(X)) >? U11(X) U11(active(X)) >? U11(X) U21(mark(X), Y) >? U21(X, Y) U21(X, mark(Y)) >? U21(X, Y) U21(active(X), Y) >? U21(X, Y) U21(X, active(Y)) >? U21(X, Y) U22(mark(X)) >? U22(X) U22(active(X)) >? U22(X) isList(mark(X)) >? isList(X) isList(active(X)) >? isList(X) U31(mark(X)) >? U31(X) U31(active(X)) >? U31(X) U41(mark(X), Y) >? U41(X, Y) U41(X, mark(Y)) >? U41(X, Y) U41(active(X), Y) >? U41(X, Y) U41(X, active(Y)) >? U41(X, Y) U42(mark(X)) >? U42(X) U42(active(X)) >? U42(X) isNeList(mark(X)) >? isNeList(X) isNeList(active(X)) >? isNeList(X) U51(mark(X), Y) >? U51(X, Y) U51(X, mark(Y)) >? U51(X, Y) U51(active(X), Y) >? U51(X, Y) U51(X, active(Y)) >? U51(X, Y) U52(mark(X)) >? U52(X) U52(active(X)) >? U52(X) U61(mark(X)) >? U61(X) U61(active(X)) >? U61(X) U71(mark(X), Y) >? U71(X, Y) U71(X, mark(Y)) >? U71(X, Y) U71(active(X), Y) >? U71(X, Y) U71(X, active(Y)) >? U71(X, Y) U72(mark(X)) >? U72(X) U72(active(X)) >? U72(X) isPal(mark(X)) >? isPal(X) isPal(active(X)) >? isPal(X) U81(mark(X)) >? U81(X) U81(active(X)) >? U81(X) isQid(mark(X)) >? isQid(X) isQid(active(X)) >? isQid(X) isNePal(mark(X)) >? isNePal(X) isNePal(active(X)) >? isNePal(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 = \y0.y0 U21 = \y0y1.y0 + y1 U22 = \y0.y0 U31 = \y0.y0 U41 = \y0y1.y0 + y1 U42 = \y0.y0 U51 = \y0y1.y0 + y1 U52 = \y0.y0 U61 = \y0.y0 U71 = \y0y1.y0 + y1 U72 = \y0.y0 U81 = \y0.1 + y0 active = \y0.y0 isList = \y0.y0 isNeList = \y0.y0 isNePal = \y0.y0 isPal = \y0.2y0 isQid = \y0.y0 mark = \y0.2y0 tt = 0 Using this interpretation, the requirements translate to: [[active(U81(tt))]] = 1 > 0 = [[mark(tt)]] [[mark(tt)]] = 0 >= 0 = [[active(tt)]] [[mark(U51(_x0, _x1))]] = 2x0 + 2x1 >= x1 + 2x0 = [[active(U51(mark(_x0), _x1))]] [[mark(U81(_x0))]] = 2 + 2x0 > 1 + 2x0 = [[active(U81(mark(_x0)))]] [[mark(isQid(_x0))]] = 2x0 >= x0 = [[active(isQid(_x0))]] [[mark(isNePal(_x0))]] = 2x0 >= x0 = [[active(isNePal(_x0))]] [[!6220!6220(mark(_x0), _x1)]] = x1 + 4x0 >= x1 + 2x0 = [[!6220!6220(_x0, _x1)]] [[!6220!6220(_x0, mark(_x1))]] = 2x0 + 2x1 >= x1 + 2x0 = [[!6220!6220(_x0, _x1)]] [[!6220!6220(active(_x0), _x1)]] = x1 + 2x0 >= x1 + 2x0 = [[!6220!6220(_x0, _x1)]] [[!6220!6220(_x0, active(_x1))]] = x1 + 2x0 >= x1 + 2x0 = [[!6220!6220(_x0, _x1)]] [[U11(mark(_x0))]] = 2x0 >= x0 = [[U11(_x0)]] [[U11(active(_x0))]] = x0 >= x0 = [[U11(_x0)]] [[U21(mark(_x0), _x1)]] = x1 + 2x0 >= x0 + x1 = [[U21(_x0, _x1)]] [[U21(_x0, mark(_x1))]] = x0 + 2x1 >= x0 + x1 = [[U21(_x0, _x1)]] [[U21(active(_x0), _x1)]] = x0 + x1 >= x0 + x1 = [[U21(_x0, _x1)]] [[U21(_x0, active(_x1))]] = x0 + x1 >= x0 + x1 = [[U21(_x0, _x1)]] [[U22(mark(_x0))]] = 2x0 >= x0 = [[U22(_x0)]] [[U22(active(_x0))]] = x0 >= x0 = [[U22(_x0)]] [[isList(mark(_x0))]] = 2x0 >= x0 = [[isList(_x0)]] [[isList(active(_x0))]] = x0 >= x0 = [[isList(_x0)]] [[U31(mark(_x0))]] = 2x0 >= x0 = [[U31(_x0)]] [[U31(active(_x0))]] = x0 >= x0 = [[U31(_x0)]] [[U41(mark(_x0), _x1)]] = x1 + 2x0 >= x0 + x1 = [[U41(_x0, _x1)]] [[U41(_x0, mark(_x1))]] = x0 + 2x1 >= x0 + x1 = [[U41(_x0, _x1)]] [[U41(active(_x0), _x1)]] = x0 + x1 >= x0 + x1 = [[U41(_x0, _x1)]] [[U41(_x0, active(_x1))]] = x0 + x1 >= x0 + x1 = [[U41(_x0, _x1)]] [[U42(mark(_x0))]] = 2x0 >= x0 = [[U42(_x0)]] [[U42(active(_x0))]] = x0 >= x0 = [[U42(_x0)]] [[isNeList(mark(_x0))]] = 2x0 >= x0 = [[isNeList(_x0)]] [[isNeList(active(_x0))]] = x0 >= x0 = [[isNeList(_x0)]] [[U51(mark(_x0), _x1)]] = x1 + 2x0 >= x0 + x1 = [[U51(_x0, _x1)]] [[U51(_x0, mark(_x1))]] = x0 + 2x1 >= x0 + x1 = [[U51(_x0, _x1)]] [[U51(active(_x0), _x1)]] = x0 + x1 >= x0 + x1 = [[U51(_x0, _x1)]] [[U51(_x0, active(_x1))]] = x0 + x1 >= x0 + x1 = [[U51(_x0, _x1)]] [[U52(mark(_x0))]] = 2x0 >= x0 = [[U52(_x0)]] [[U52(active(_x0))]] = x0 >= x0 = [[U52(_x0)]] [[U61(mark(_x0))]] = 2x0 >= x0 = [[U61(_x0)]] [[U61(active(_x0))]] = x0 >= x0 = [[U61(_x0)]] [[U71(mark(_x0), _x1)]] = x1 + 2x0 >= x0 + x1 = [[U71(_x0, _x1)]] [[U71(_x0, mark(_x1))]] = x0 + 2x1 >= x0 + x1 = [[U71(_x0, _x1)]] [[U71(active(_x0), _x1)]] = x0 + x1 >= x0 + x1 = [[U71(_x0, _x1)]] [[U71(_x0, active(_x1))]] = x0 + x1 >= x0 + x1 = [[U71(_x0, _x1)]] [[U72(mark(_x0))]] = 2x0 >= x0 = [[U72(_x0)]] [[U72(active(_x0))]] = x0 >= x0 = [[U72(_x0)]] [[isPal(mark(_x0))]] = 4x0 >= 2x0 = [[isPal(_x0)]] [[isPal(active(_x0))]] = 2x0 >= 2x0 = [[isPal(_x0)]] [[U81(mark(_x0))]] = 1 + 2x0 >= 1 + x0 = [[U81(_x0)]] [[U81(active(_x0))]] = 1 + x0 >= 1 + x0 = [[U81(_x0)]] [[isQid(mark(_x0))]] = 2x0 >= x0 = [[isQid(_x0)]] [[isQid(active(_x0))]] = x0 >= x0 = [[isQid(_x0)]] [[isNePal(mark(_x0))]] = 2x0 >= x0 = [[isNePal(_x0)]] [[isNePal(active(_x0))]] = x0 >= x0 = [[isNePal(_x0)]] We can thus remove the following rules: active(U81(tt)) => mark(tt) mark(U81(X)) => active(U81(mark(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(tt) >? active(tt) mark(U51(X, Y)) >? active(U51(mark(X), Y)) mark(isQid(X)) >? active(isQid(X)) mark(isNePal(X)) >? active(isNePal(X)) !6220!6220(mark(X), Y) >? !6220!6220(X, Y) !6220!6220(X, mark(Y)) >? !6220!6220(X, Y) !6220!6220(active(X), Y) >? !6220!6220(X, Y) !6220!6220(X, active(Y)) >? !6220!6220(X, Y) U11(mark(X)) >? U11(X) U11(active(X)) >? U11(X) U21(mark(X), Y) >? U21(X, Y) U21(X, mark(Y)) >? U21(X, Y) U21(active(X), Y) >? U21(X, Y) U21(X, active(Y)) >? U21(X, Y) U22(mark(X)) >? U22(X) U22(active(X)) >? U22(X) isList(mark(X)) >? isList(X) isList(active(X)) >? isList(X) U31(mark(X)) >? U31(X) U31(active(X)) >? U31(X) U41(mark(X), Y) >? U41(X, Y) U41(X, mark(Y)) >? U41(X, Y) U41(active(X), Y) >? U41(X, Y) U41(X, active(Y)) >? U41(X, Y) U42(mark(X)) >? U42(X) U42(active(X)) >? U42(X) isNeList(mark(X)) >? isNeList(X) isNeList(active(X)) >? isNeList(X) U51(mark(X), Y) >? U51(X, Y) U51(X, mark(Y)) >? U51(X, Y) U51(active(X), Y) >? U51(X, Y) U51(X, active(Y)) >? U51(X, Y) U52(mark(X)) >? U52(X) U52(active(X)) >? U52(X) U61(mark(X)) >? U61(X) U61(active(X)) >? U61(X) U71(mark(X), Y) >? U71(X, Y) U71(X, mark(Y)) >? U71(X, Y) U71(active(X), Y) >? U71(X, Y) U71(X, active(Y)) >? U71(X, Y) U72(mark(X)) >? U72(X) U72(active(X)) >? U72(X) isPal(mark(X)) >? isPal(X) isPal(active(X)) >? isPal(X) U81(mark(X)) >? U81(X) U81(active(X)) >? U81(X) isQid(mark(X)) >? isQid(X) isQid(active(X)) >? isQid(X) isNePal(mark(X)) >? isNePal(X) isNePal(active(X)) >? isNePal(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 = \y0.2y0 U21 = \y0y1.y0 + 2y1 U22 = \y0.y0 U31 = \y0.2y0 U41 = \y0y1.y1 + 2y0 U42 = \y0.y0 U51 = \y0y1.y0 + y1 U52 = \y0.y0 U61 = \y0.y0 U71 = \y0y1.y0 + 2y1 U72 = \y0.y0 U81 = \y0.y0 active = \y0.y0 isList = \y0.y0 isNeList = \y0.2y0 isNePal = \y0.2y0 isPal = \y0.2y0 isQid = \y0.2 + y0 mark = \y0.2y0 tt = 0 Using this interpretation, the requirements translate to: [[mark(tt)]] = 0 >= 0 = [[active(tt)]] [[mark(U51(_x0, _x1))]] = 2x0 + 2x1 >= x1 + 2x0 = [[active(U51(mark(_x0), _x1))]] [[mark(isQid(_x0))]] = 4 + 2x0 > 2 + x0 = [[active(isQid(_x0))]] [[mark(isNePal(_x0))]] = 4x0 >= 2x0 = [[active(isNePal(_x0))]] [[!6220!6220(mark(_x0), _x1)]] = x1 + 4x0 >= x1 + 2x0 = [[!6220!6220(_x0, _x1)]] [[!6220!6220(_x0, mark(_x1))]] = 2x0 + 2x1 >= x1 + 2x0 = [[!6220!6220(_x0, _x1)]] [[!6220!6220(active(_x0), _x1)]] = x1 + 2x0 >= x1 + 2x0 = [[!6220!6220(_x0, _x1)]] [[!6220!6220(_x0, active(_x1))]] = x1 + 2x0 >= x1 + 2x0 = [[!6220!6220(_x0, _x1)]] [[U11(mark(_x0))]] = 4x0 >= 2x0 = [[U11(_x0)]] [[U11(active(_x0))]] = 2x0 >= 2x0 = [[U11(_x0)]] [[U21(mark(_x0), _x1)]] = 2x0 + 2x1 >= x0 + 2x1 = [[U21(_x0, _x1)]] [[U21(_x0, mark(_x1))]] = x0 + 4x1 >= x0 + 2x1 = [[U21(_x0, _x1)]] [[U21(active(_x0), _x1)]] = x0 + 2x1 >= x0 + 2x1 = [[U21(_x0, _x1)]] [[U21(_x0, active(_x1))]] = x0 + 2x1 >= x0 + 2x1 = [[U21(_x0, _x1)]] [[U22(mark(_x0))]] = 2x0 >= x0 = [[U22(_x0)]] [[U22(active(_x0))]] = x0 >= x0 = [[U22(_x0)]] [[isList(mark(_x0))]] = 2x0 >= x0 = [[isList(_x0)]] [[isList(active(_x0))]] = x0 >= x0 = [[isList(_x0)]] [[U31(mark(_x0))]] = 4x0 >= 2x0 = [[U31(_x0)]] [[U31(active(_x0))]] = 2x0 >= 2x0 = [[U31(_x0)]] [[U41(mark(_x0), _x1)]] = x1 + 4x0 >= x1 + 2x0 = [[U41(_x0, _x1)]] [[U41(_x0, mark(_x1))]] = 2x0 + 2x1 >= x1 + 2x0 = [[U41(_x0, _x1)]] [[U41(active(_x0), _x1)]] = x1 + 2x0 >= x1 + 2x0 = [[U41(_x0, _x1)]] [[U41(_x0, active(_x1))]] = x1 + 2x0 >= x1 + 2x0 = [[U41(_x0, _x1)]] [[U42(mark(_x0))]] = 2x0 >= x0 = [[U42(_x0)]] [[U42(active(_x0))]] = x0 >= x0 = [[U42(_x0)]] [[isNeList(mark(_x0))]] = 4x0 >= 2x0 = [[isNeList(_x0)]] [[isNeList(active(_x0))]] = 2x0 >= 2x0 = [[isNeList(_x0)]] [[U51(mark(_x0), _x1)]] = x1 + 2x0 >= x0 + x1 = [[U51(_x0, _x1)]] [[U51(_x0, mark(_x1))]] = x0 + 2x1 >= x0 + x1 = [[U51(_x0, _x1)]] [[U51(active(_x0), _x1)]] = x0 + x1 >= x0 + x1 = [[U51(_x0, _x1)]] [[U51(_x0, active(_x1))]] = x0 + x1 >= x0 + x1 = [[U51(_x0, _x1)]] [[U52(mark(_x0))]] = 2x0 >= x0 = [[U52(_x0)]] [[U52(active(_x0))]] = x0 >= x0 = [[U52(_x0)]] [[U61(mark(_x0))]] = 2x0 >= x0 = [[U61(_x0)]] [[U61(active(_x0))]] = x0 >= x0 = [[U61(_x0)]] [[U71(mark(_x0), _x1)]] = 2x0 + 2x1 >= x0 + 2x1 = [[U71(_x0, _x1)]] [[U71(_x0, mark(_x1))]] = x0 + 4x1 >= x0 + 2x1 = [[U71(_x0, _x1)]] [[U71(active(_x0), _x1)]] = x0 + 2x1 >= x0 + 2x1 = [[U71(_x0, _x1)]] [[U71(_x0, active(_x1))]] = x0 + 2x1 >= x0 + 2x1 = [[U71(_x0, _x1)]] [[U72(mark(_x0))]] = 2x0 >= x0 = [[U72(_x0)]] [[U72(active(_x0))]] = x0 >= x0 = [[U72(_x0)]] [[isPal(mark(_x0))]] = 4x0 >= 2x0 = [[isPal(_x0)]] [[isPal(active(_x0))]] = 2x0 >= 2x0 = [[isPal(_x0)]] [[U81(mark(_x0))]] = 2x0 >= x0 = [[U81(_x0)]] [[U81(active(_x0))]] = x0 >= x0 = [[U81(_x0)]] [[isQid(mark(_x0))]] = 2 + 2x0 >= 2 + x0 = [[isQid(_x0)]] [[isQid(active(_x0))]] = 2 + x0 >= 2 + x0 = [[isQid(_x0)]] [[isNePal(mark(_x0))]] = 4x0 >= 2x0 = [[isNePal(_x0)]] [[isNePal(active(_x0))]] = 2x0 >= 2x0 = [[isNePal(_x0)]] We can thus remove the following rules: mark(isQid(X)) => active(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]): mark(tt) >? active(tt) mark(U51(X, Y)) >? active(U51(mark(X), Y)) mark(isNePal(X)) >? active(isNePal(X)) !6220!6220(mark(X), Y) >? !6220!6220(X, Y) !6220!6220(X, mark(Y)) >? !6220!6220(X, Y) !6220!6220(active(X), Y) >? !6220!6220(X, Y) !6220!6220(X, active(Y)) >? !6220!6220(X, Y) U11(mark(X)) >? U11(X) U11(active(X)) >? U11(X) U21(mark(X), Y) >? U21(X, Y) U21(X, mark(Y)) >? U21(X, Y) U21(active(X), Y) >? U21(X, Y) U21(X, active(Y)) >? U21(X, Y) U22(mark(X)) >? U22(X) U22(active(X)) >? U22(X) isList(mark(X)) >? isList(X) isList(active(X)) >? isList(X) U31(mark(X)) >? U31(X) U31(active(X)) >? U31(X) U41(mark(X), Y) >? U41(X, Y) U41(X, mark(Y)) >? U41(X, Y) U41(active(X), Y) >? U41(X, Y) U41(X, active(Y)) >? U41(X, Y) U42(mark(X)) >? U42(X) U42(active(X)) >? U42(X) isNeList(mark(X)) >? isNeList(X) isNeList(active(X)) >? isNeList(X) U51(mark(X), Y) >? U51(X, Y) U51(X, mark(Y)) >? U51(X, Y) U51(active(X), Y) >? U51(X, Y) U51(X, active(Y)) >? U51(X, Y) U52(mark(X)) >? U52(X) U52(active(X)) >? U52(X) U61(mark(X)) >? U61(X) U61(active(X)) >? U61(X) U71(mark(X), Y) >? U71(X, Y) U71(X, mark(Y)) >? U71(X, Y) U71(active(X), Y) >? U71(X, Y) U71(X, active(Y)) >? U71(X, Y) U72(mark(X)) >? U72(X) U72(active(X)) >? U72(X) isPal(mark(X)) >? isPal(X) isPal(active(X)) >? isPal(X) U81(mark(X)) >? U81(X) U81(active(X)) >? U81(X) isQid(mark(X)) >? isQid(X) isQid(active(X)) >? isQid(X) isNePal(mark(X)) >? isNePal(X) isNePal(active(X)) >? isNePal(X) We orient these requirements with a polynomial interpretation in the natural numbers. The following interpretation satisfies the requirements: !6220!6220 = \y0y1.y0 + 2y1 U11 = \y0.2y0 U21 = \y0y1.y0 + y1 U22 = \y0.y0 U31 = \y0.y0 U41 = \y0y1.y0 + 2y1 U42 = \y0.y0 U51 = \y0y1.y1 + 2y0 U52 = \y0.y0 U61 = \y0.y0 U71 = \y0y1.y0 + y1 U72 = \y0.y0 U81 = \y0.y0 active = \y0.y0 isList = \y0.y0 isNeList = \y0.y0 isNePal = \y0.2 + 2y0 isPal = \y0.y0 isQid = \y0.y0 mark = \y0.2y0 tt = 0 Using this interpretation, the requirements translate to: [[mark(tt)]] = 0 >= 0 = [[active(tt)]] [[mark(U51(_x0, _x1))]] = 2x1 + 4x0 >= x1 + 4x0 = [[active(U51(mark(_x0), _x1))]] [[mark(isNePal(_x0))]] = 4 + 4x0 > 2 + 2x0 = [[active(isNePal(_x0))]] [[!6220!6220(mark(_x0), _x1)]] = 2x0 + 2x1 >= x0 + 2x1 = [[!6220!6220(_x0, _x1)]] [[!6220!6220(_x0, mark(_x1))]] = x0 + 4x1 >= x0 + 2x1 = [[!6220!6220(_x0, _x1)]] [[!6220!6220(active(_x0), _x1)]] = x0 + 2x1 >= x0 + 2x1 = [[!6220!6220(_x0, _x1)]] [[!6220!6220(_x0, active(_x1))]] = x0 + 2x1 >= x0 + 2x1 = [[!6220!6220(_x0, _x1)]] [[U11(mark(_x0))]] = 4x0 >= 2x0 = [[U11(_x0)]] [[U11(active(_x0))]] = 2x0 >= 2x0 = [[U11(_x0)]] [[U21(mark(_x0), _x1)]] = x1 + 2x0 >= x0 + x1 = [[U21(_x0, _x1)]] [[U21(_x0, mark(_x1))]] = x0 + 2x1 >= x0 + x1 = [[U21(_x0, _x1)]] [[U21(active(_x0), _x1)]] = x0 + x1 >= x0 + x1 = [[U21(_x0, _x1)]] [[U21(_x0, active(_x1))]] = x0 + x1 >= x0 + x1 = [[U21(_x0, _x1)]] [[U22(mark(_x0))]] = 2x0 >= x0 = [[U22(_x0)]] [[U22(active(_x0))]] = x0 >= x0 = [[U22(_x0)]] [[isList(mark(_x0))]] = 2x0 >= x0 = [[isList(_x0)]] [[isList(active(_x0))]] = x0 >= x0 = [[isList(_x0)]] [[U31(mark(_x0))]] = 2x0 >= x0 = [[U31(_x0)]] [[U31(active(_x0))]] = x0 >= x0 = [[U31(_x0)]] [[U41(mark(_x0), _x1)]] = 2x0 + 2x1 >= x0 + 2x1 = [[U41(_x0, _x1)]] [[U41(_x0, mark(_x1))]] = x0 + 4x1 >= x0 + 2x1 = [[U41(_x0, _x1)]] [[U41(active(_x0), _x1)]] = x0 + 2x1 >= x0 + 2x1 = [[U41(_x0, _x1)]] [[U41(_x0, active(_x1))]] = x0 + 2x1 >= x0 + 2x1 = [[U41(_x0, _x1)]] [[U42(mark(_x0))]] = 2x0 >= x0 = [[U42(_x0)]] [[U42(active(_x0))]] = x0 >= x0 = [[U42(_x0)]] [[isNeList(mark(_x0))]] = 2x0 >= x0 = [[isNeList(_x0)]] [[isNeList(active(_x0))]] = x0 >= x0 = [[isNeList(_x0)]] [[U51(mark(_x0), _x1)]] = x1 + 4x0 >= x1 + 2x0 = [[U51(_x0, _x1)]] [[U51(_x0, mark(_x1))]] = 2x0 + 2x1 >= x1 + 2x0 = [[U51(_x0, _x1)]] [[U51(active(_x0), _x1)]] = x1 + 2x0 >= x1 + 2x0 = [[U51(_x0, _x1)]] [[U51(_x0, active(_x1))]] = x1 + 2x0 >= x1 + 2x0 = [[U51(_x0, _x1)]] [[U52(mark(_x0))]] = 2x0 >= x0 = [[U52(_x0)]] [[U52(active(_x0))]] = x0 >= x0 = [[U52(_x0)]] [[U61(mark(_x0))]] = 2x0 >= x0 = [[U61(_x0)]] [[U61(active(_x0))]] = x0 >= x0 = [[U61(_x0)]] [[U71(mark(_x0), _x1)]] = x1 + 2x0 >= x0 + x1 = [[U71(_x0, _x1)]] [[U71(_x0, mark(_x1))]] = x0 + 2x1 >= x0 + x1 = [[U71(_x0, _x1)]] [[U71(active(_x0), _x1)]] = x0 + x1 >= x0 + x1 = [[U71(_x0, _x1)]] [[U71(_x0, active(_x1))]] = x0 + x1 >= x0 + x1 = [[U71(_x0, _x1)]] [[U72(mark(_x0))]] = 2x0 >= x0 = [[U72(_x0)]] [[U72(active(_x0))]] = x0 >= x0 = [[U72(_x0)]] [[isPal(mark(_x0))]] = 2x0 >= x0 = [[isPal(_x0)]] [[isPal(active(_x0))]] = x0 >= x0 = [[isPal(_x0)]] [[U81(mark(_x0))]] = 2x0 >= x0 = [[U81(_x0)]] [[U81(active(_x0))]] = x0 >= x0 = [[U81(_x0)]] [[isQid(mark(_x0))]] = 2x0 >= x0 = [[isQid(_x0)]] [[isQid(active(_x0))]] = x0 >= x0 = [[isQid(_x0)]] [[isNePal(mark(_x0))]] = 2 + 4x0 >= 2 + 2x0 = [[isNePal(_x0)]] [[isNePal(active(_x0))]] = 2 + 2x0 >= 2 + 2x0 = [[isNePal(_x0)]] We can thus remove the following rules: mark(isNePal(X)) => active(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]): mark(tt) >? active(tt) mark(U51(X, Y)) >? active(U51(mark(X), Y)) !6220!6220(mark(X), Y) >? !6220!6220(X, Y) !6220!6220(X, mark(Y)) >? !6220!6220(X, Y) !6220!6220(active(X), Y) >? !6220!6220(X, Y) !6220!6220(X, active(Y)) >? !6220!6220(X, Y) U11(mark(X)) >? U11(X) U11(active(X)) >? U11(X) U21(mark(X), Y) >? U21(X, Y) U21(X, mark(Y)) >? U21(X, Y) U21(active(X), Y) >? U21(X, Y) U21(X, active(Y)) >? U21(X, Y) U22(mark(X)) >? U22(X) U22(active(X)) >? U22(X) isList(mark(X)) >? isList(X) isList(active(X)) >? isList(X) U31(mark(X)) >? U31(X) U31(active(X)) >? U31(X) U41(mark(X), Y) >? U41(X, Y) U41(X, mark(Y)) >? U41(X, Y) U41(active(X), Y) >? U41(X, Y) U41(X, active(Y)) >? U41(X, Y) U42(mark(X)) >? U42(X) U42(active(X)) >? U42(X) isNeList(mark(X)) >? isNeList(X) isNeList(active(X)) >? isNeList(X) U51(mark(X), Y) >? U51(X, Y) U51(X, mark(Y)) >? U51(X, Y) U51(active(X), Y) >? U51(X, Y) U51(X, active(Y)) >? U51(X, Y) U52(mark(X)) >? U52(X) U52(active(X)) >? U52(X) U61(mark(X)) >? U61(X) U61(active(X)) >? U61(X) U71(mark(X), Y) >? U71(X, Y) U71(X, mark(Y)) >? U71(X, Y) U71(active(X), Y) >? U71(X, Y) U71(X, active(Y)) >? U71(X, Y) U72(mark(X)) >? U72(X) U72(active(X)) >? U72(X) isPal(mark(X)) >? isPal(X) isPal(active(X)) >? isPal(X) U81(mark(X)) >? U81(X) U81(active(X)) >? U81(X) isQid(mark(X)) >? isQid(X) isQid(active(X)) >? isQid(X) isNePal(mark(X)) >? isNePal(X) isNePal(active(X)) >? isNePal(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 = \y0.2y0 U21 = \y0y1.y0 + 2y1 U22 = \y0.y0 U31 = \y0.y0 U41 = \y0y1.y0 + y1 U42 = \y0.y0 U51 = \y0y1.y0 + 2y1 U52 = \y0.y0 U61 = \y0.y0 U71 = \y0y1.y0 + y1 U72 = \y0.y0 U81 = \y0.y0 active = \y0.y0 isList = \y0.y0 isNeList = \y0.2y0 isNePal = \y0.y0 isPal = \y0.y0 isQid = \y0.y0 mark = \y0.2 + 2y0 tt = 0 Using this interpretation, the requirements translate to: [[mark(tt)]] = 2 > 0 = [[active(tt)]] [[mark(U51(_x0, _x1))]] = 2 + 2x0 + 4x1 >= 2 + 2x0 + 2x1 = [[active(U51(mark(_x0), _x1))]] [[!6220!6220(mark(_x0), _x1)]] = 2 + x1 + 2x0 > x0 + x1 = [[!6220!6220(_x0, _x1)]] [[!6220!6220(_x0, mark(_x1))]] = 2 + x0 + 2x1 > x0 + x1 = [[!6220!6220(_x0, _x1)]] [[!6220!6220(active(_x0), _x1)]] = x0 + x1 >= x0 + x1 = [[!6220!6220(_x0, _x1)]] [[!6220!6220(_x0, active(_x1))]] = x0 + x1 >= x0 + x1 = [[!6220!6220(_x0, _x1)]] [[U11(mark(_x0))]] = 4 + 4x0 > 2x0 = [[U11(_x0)]] [[U11(active(_x0))]] = 2x0 >= 2x0 = [[U11(_x0)]] [[U21(mark(_x0), _x1)]] = 2 + 2x0 + 2x1 > x0 + 2x1 = [[U21(_x0, _x1)]] [[U21(_x0, mark(_x1))]] = 4 + x0 + 4x1 > x0 + 2x1 = [[U21(_x0, _x1)]] [[U21(active(_x0), _x1)]] = x0 + 2x1 >= x0 + 2x1 = [[U21(_x0, _x1)]] [[U21(_x0, active(_x1))]] = x0 + 2x1 >= x0 + 2x1 = [[U21(_x0, _x1)]] [[U22(mark(_x0))]] = 2 + 2x0 > x0 = [[U22(_x0)]] [[U22(active(_x0))]] = x0 >= x0 = [[U22(_x0)]] [[isList(mark(_x0))]] = 2 + 2x0 > x0 = [[isList(_x0)]] [[isList(active(_x0))]] = x0 >= x0 = [[isList(_x0)]] [[U31(mark(_x0))]] = 2 + 2x0 > x0 = [[U31(_x0)]] [[U31(active(_x0))]] = x0 >= x0 = [[U31(_x0)]] [[U41(mark(_x0), _x1)]] = 2 + x1 + 2x0 > x0 + x1 = [[U41(_x0, _x1)]] [[U41(_x0, mark(_x1))]] = 2 + x0 + 2x1 > x0 + x1 = [[U41(_x0, _x1)]] [[U41(active(_x0), _x1)]] = x0 + x1 >= x0 + x1 = [[U41(_x0, _x1)]] [[U41(_x0, active(_x1))]] = x0 + x1 >= x0 + x1 = [[U41(_x0, _x1)]] [[U42(mark(_x0))]] = 2 + 2x0 > x0 = [[U42(_x0)]] [[U42(active(_x0))]] = x0 >= x0 = [[U42(_x0)]] [[isNeList(mark(_x0))]] = 4 + 4x0 > 2x0 = [[isNeList(_x0)]] [[isNeList(active(_x0))]] = 2x0 >= 2x0 = [[isNeList(_x0)]] [[U51(mark(_x0), _x1)]] = 2 + 2x0 + 2x1 > x0 + 2x1 = [[U51(_x0, _x1)]] [[U51(_x0, mark(_x1))]] = 4 + x0 + 4x1 > x0 + 2x1 = [[U51(_x0, _x1)]] [[U51(active(_x0), _x1)]] = x0 + 2x1 >= x0 + 2x1 = [[U51(_x0, _x1)]] [[U51(_x0, active(_x1))]] = x0 + 2x1 >= x0 + 2x1 = [[U51(_x0, _x1)]] [[U52(mark(_x0))]] = 2 + 2x0 > x0 = [[U52(_x0)]] [[U52(active(_x0))]] = x0 >= x0 = [[U52(_x0)]] [[U61(mark(_x0))]] = 2 + 2x0 > x0 = [[U61(_x0)]] [[U61(active(_x0))]] = x0 >= x0 = [[U61(_x0)]] [[U71(mark(_x0), _x1)]] = 2 + x1 + 2x0 > x0 + x1 = [[U71(_x0, _x1)]] [[U71(_x0, mark(_x1))]] = 2 + x0 + 2x1 > x0 + x1 = [[U71(_x0, _x1)]] [[U71(active(_x0), _x1)]] = x0 + x1 >= x0 + x1 = [[U71(_x0, _x1)]] [[U71(_x0, active(_x1))]] = x0 + x1 >= x0 + x1 = [[U71(_x0, _x1)]] [[U72(mark(_x0))]] = 2 + 2x0 > x0 = [[U72(_x0)]] [[U72(active(_x0))]] = x0 >= x0 = [[U72(_x0)]] [[isPal(mark(_x0))]] = 2 + 2x0 > x0 = [[isPal(_x0)]] [[isPal(active(_x0))]] = x0 >= x0 = [[isPal(_x0)]] [[U81(mark(_x0))]] = 2 + 2x0 > x0 = [[U81(_x0)]] [[U81(active(_x0))]] = x0 >= x0 = [[U81(_x0)]] [[isQid(mark(_x0))]] = 2 + 2x0 > x0 = [[isQid(_x0)]] [[isQid(active(_x0))]] = x0 >= x0 = [[isQid(_x0)]] [[isNePal(mark(_x0))]] = 2 + 2x0 > x0 = [[isNePal(_x0)]] [[isNePal(active(_x0))]] = x0 >= x0 = [[isNePal(_x0)]] We can thus remove the following rules: mark(tt) => active(tt) !6220!6220(mark(X), Y) => !6220!6220(X, Y) !6220!6220(X, mark(Y)) => !6220!6220(X, Y) U11(mark(X)) => U11(X) U21(mark(X), Y) => U21(X, Y) U21(X, mark(Y)) => U21(X, Y) U22(mark(X)) => U22(X) isList(mark(X)) => isList(X) U31(mark(X)) => U31(X) U41(mark(X), Y) => U41(X, Y) U41(X, mark(Y)) => U41(X, Y) U42(mark(X)) => U42(X) isNeList(mark(X)) => isNeList(X) U51(mark(X), Y) => U51(X, Y) U51(X, mark(Y)) => U51(X, Y) U52(mark(X)) => U52(X) U61(mark(X)) => U61(X) U71(mark(X), Y) => U71(X, Y) U71(X, mark(Y)) => U71(X, Y) U72(mark(X)) => U72(X) isPal(mark(X)) => isPal(X) U81(mark(X)) => U81(X) isQid(mark(X)) => isQid(X) isNePal(mark(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]): mark(U51(X, Y)) >? active(U51(mark(X), Y)) !6220!6220(active(X), Y) >? !6220!6220(X, Y) !6220!6220(X, active(Y)) >? !6220!6220(X, Y) U11(active(X)) >? U11(X) U21(active(X), Y) >? U21(X, Y) U21(X, active(Y)) >? U21(X, Y) U22(active(X)) >? U22(X) isList(active(X)) >? isList(X) U31(active(X)) >? U31(X) U41(active(X), Y) >? U41(X, Y) U41(X, active(Y)) >? U41(X, Y) U42(active(X)) >? U42(X) isNeList(active(X)) >? isNeList(X) U51(active(X), Y) >? U51(X, Y) U51(X, active(Y)) >? U51(X, Y) U52(active(X)) >? U52(X) U61(active(X)) >? U61(X) U71(active(X), Y) >? U71(X, Y) U71(X, active(Y)) >? U71(X, Y) U72(active(X)) >? U72(X) isPal(active(X)) >? isPal(X) U81(active(X)) >? U81(X) isQid(active(X)) >? isQid(X) isNePal(active(X)) >? isNePal(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 = \y0.y0 U21 = \y0y1.y0 + y1 U22 = \y0.y0 U31 = \y0.y0 U41 = \y0y1.y0 + y1 U42 = \y0.y0 U51 = \y0y1.1 + y0 + y1 U52 = \y0.y0 U61 = \y0.y0 U71 = \y0y1.y0 + y1 U72 = \y0.y0 U81 = \y0.y0 active = \y0.y0 isList = \y0.y0 isNeList = \y0.y0 isNePal = \y0.y0 isPal = \y0.y0 isQid = \y0.2y0 mark = \y0.2y0 Using this interpretation, the requirements translate to: [[mark(U51(_x0, _x1))]] = 2 + 2x0 + 2x1 > 1 + x1 + 2x0 = [[active(U51(mark(_x0), _x1))]] [[!6220!6220(active(_x0), _x1)]] = x0 + x1 >= x0 + x1 = [[!6220!6220(_x0, _x1)]] [[!6220!6220(_x0, active(_x1))]] = x0 + x1 >= x0 + x1 = [[!6220!6220(_x0, _x1)]] [[U11(active(_x0))]] = x0 >= x0 = [[U11(_x0)]] [[U21(active(_x0), _x1)]] = x0 + x1 >= x0 + x1 = [[U21(_x0, _x1)]] [[U21(_x0, active(_x1))]] = x0 + x1 >= x0 + x1 = [[U21(_x0, _x1)]] [[U22(active(_x0))]] = x0 >= x0 = [[U22(_x0)]] [[isList(active(_x0))]] = x0 >= x0 = [[isList(_x0)]] [[U31(active(_x0))]] = x0 >= x0 = [[U31(_x0)]] [[U41(active(_x0), _x1)]] = x0 + x1 >= x0 + x1 = [[U41(_x0, _x1)]] [[U41(_x0, active(_x1))]] = x0 + x1 >= x0 + x1 = [[U41(_x0, _x1)]] [[U42(active(_x0))]] = x0 >= x0 = [[U42(_x0)]] [[isNeList(active(_x0))]] = x0 >= x0 = [[isNeList(_x0)]] [[U51(active(_x0), _x1)]] = 1 + x0 + x1 >= 1 + x0 + x1 = [[U51(_x0, _x1)]] [[U51(_x0, active(_x1))]] = 1 + x0 + x1 >= 1 + x0 + x1 = [[U51(_x0, _x1)]] [[U52(active(_x0))]] = x0 >= x0 = [[U52(_x0)]] [[U61(active(_x0))]] = x0 >= x0 = [[U61(_x0)]] [[U71(active(_x0), _x1)]] = x0 + x1 >= x0 + x1 = [[U71(_x0, _x1)]] [[U71(_x0, active(_x1))]] = x0 + x1 >= x0 + x1 = [[U71(_x0, _x1)]] [[U72(active(_x0))]] = x0 >= x0 = [[U72(_x0)]] [[isPal(active(_x0))]] = x0 >= x0 = [[isPal(_x0)]] [[U81(active(_x0))]] = x0 >= x0 = [[U81(_x0)]] [[isQid(active(_x0))]] = 2x0 >= 2x0 = [[isQid(_x0)]] [[isNePal(active(_x0))]] = x0 >= x0 = [[isNePal(_x0)]] We can thus remove the following rules: mark(U51(X, Y)) => active(U51(mark(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]): !6220!6220(active(X), Y) >? !6220!6220(X, Y) !6220!6220(X, active(Y)) >? !6220!6220(X, Y) U11(active(X)) >? U11(X) U21(active(X), Y) >? U21(X, Y) U21(X, active(Y)) >? U21(X, Y) U22(active(X)) >? U22(X) isList(active(X)) >? isList(X) U31(active(X)) >? U31(X) U41(active(X), Y) >? U41(X, Y) U41(X, active(Y)) >? U41(X, Y) U42(active(X)) >? U42(X) isNeList(active(X)) >? isNeList(X) U51(active(X), Y) >? U51(X, Y) U51(X, active(Y)) >? U51(X, Y) U52(active(X)) >? U52(X) U61(active(X)) >? U61(X) U71(active(X), Y) >? U71(X, Y) U71(X, active(Y)) >? U71(X, Y) U72(active(X)) >? U72(X) isPal(active(X)) >? isPal(X) U81(active(X)) >? U81(X) isQid(active(X)) >? isQid(X) isNePal(active(X)) >? isNePal(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 = \y0.y0 U21 = \y0y1.y0 + y1 U22 = \y0.y0 U31 = \y0.y0 U41 = \y0y1.y0 + y1 U42 = \y0.y0 U51 = \y0y1.y0 + y1 U52 = \y0.y0 U61 = \y0.y0 U71 = \y0y1.y0 + y1 U72 = \y0.y0 U81 = \y0.y0 active = \y0.3 + 3y0 isList = \y0.y0 isNeList = \y0.y0 isNePal = \y0.y0 isPal = \y0.y0 isQid = \y0.y0 Using this interpretation, the requirements translate to: [[!6220!6220(active(_x0), _x1)]] = 3 + x1 + 3x0 > x0 + x1 = [[!6220!6220(_x0, _x1)]] [[!6220!6220(_x0, active(_x1))]] = 3 + x0 + 3x1 > x0 + x1 = [[!6220!6220(_x0, _x1)]] [[U11(active(_x0))]] = 3 + 3x0 > x0 = [[U11(_x0)]] [[U21(active(_x0), _x1)]] = 3 + x1 + 3x0 > x0 + x1 = [[U21(_x0, _x1)]] [[U21(_x0, active(_x1))]] = 3 + x0 + 3x1 > x0 + x1 = [[U21(_x0, _x1)]] [[U22(active(_x0))]] = 3 + 3x0 > x0 = [[U22(_x0)]] [[isList(active(_x0))]] = 3 + 3x0 > x0 = [[isList(_x0)]] [[U31(active(_x0))]] = 3 + 3x0 > x0 = [[U31(_x0)]] [[U41(active(_x0), _x1)]] = 3 + x1 + 3x0 > x0 + x1 = [[U41(_x0, _x1)]] [[U41(_x0, active(_x1))]] = 3 + x0 + 3x1 > x0 + x1 = [[U41(_x0, _x1)]] [[U42(active(_x0))]] = 3 + 3x0 > x0 = [[U42(_x0)]] [[isNeList(active(_x0))]] = 3 + 3x0 > x0 = [[isNeList(_x0)]] [[U51(active(_x0), _x1)]] = 3 + x1 + 3x0 > x0 + x1 = [[U51(_x0, _x1)]] [[U51(_x0, active(_x1))]] = 3 + x0 + 3x1 > x0 + x1 = [[U51(_x0, _x1)]] [[U52(active(_x0))]] = 3 + 3x0 > x0 = [[U52(_x0)]] [[U61(active(_x0))]] = 3 + 3x0 > x0 = [[U61(_x0)]] [[U71(active(_x0), _x1)]] = 3 + x1 + 3x0 > x0 + x1 = [[U71(_x0, _x1)]] [[U71(_x0, active(_x1))]] = 3 + x0 + 3x1 > x0 + x1 = [[U71(_x0, _x1)]] [[U72(active(_x0))]] = 3 + 3x0 > x0 = [[U72(_x0)]] [[isPal(active(_x0))]] = 3 + 3x0 > x0 = [[isPal(_x0)]] [[U81(active(_x0))]] = 3 + 3x0 > x0 = [[U81(_x0)]] [[isQid(active(_x0))]] = 3 + 3x0 > x0 = [[isQid(_x0)]] [[isNePal(active(_x0))]] = 3 + 3x0 > x0 = [[isNePal(_x0)]] We can thus remove the following rules: !6220!6220(active(X), Y) => !6220!6220(X, Y) !6220!6220(X, active(Y)) => !6220!6220(X, Y) U11(active(X)) => U11(X) U21(active(X), Y) => U21(X, Y) U21(X, active(Y)) => U21(X, Y) U22(active(X)) => U22(X) isList(active(X)) => isList(X) U31(active(X)) => U31(X) U41(active(X), Y) => U41(X, Y) U41(X, active(Y)) => U41(X, Y) U42(active(X)) => U42(X) isNeList(active(X)) => isNeList(X) U51(active(X), Y) => U51(X, Y) U51(X, active(Y)) => U51(X, Y) U52(active(X)) => U52(X) U61(active(X)) => U61(X) U71(active(X), Y) => U71(X, Y) U71(X, active(Y)) => U71(X, Y) U72(active(X)) => U72(X) isPal(active(X)) => isPal(X) U81(active(X)) => U81(X) isQid(active(X)) => isQid(X) isNePal(active(X)) => isNePal(X) All rules were succesfully removed. Thus, termination of the original system has been reduced to termination of the beta-rule, which is well-known to hold. +++ Citations +++ [Kop12] C. Kop. Higher Order Termination. PhD Thesis, 2012.