/export/starexec/sandbox2/solver/bin/starexec_run_FirstOrder /export/starexec/sandbox2/benchmark/theBenchmark.xml /export/starexec/sandbox2/output/output_files -------------------------------------------------------------------------------- YES We consider the system theBenchmark. We are asked to determine termination of the following first-order TRS. !6220!6220 : [o * o] --> o a : [] --> o active : [o] --> o and : [o * 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(and(tt, X)) => mark(X) active(isList(X)) => mark(isNeList(X)) active(isList(nil)) => mark(tt) active(isList(!6220!6220(X, Y))) => mark(and(isList(X), isList(Y))) active(isNeList(X)) => mark(isQid(X)) active(isNeList(!6220!6220(X, Y))) => mark(and(isList(X), isNeList(Y))) active(isNeList(!6220!6220(X, Y))) => mark(and(isNeList(X), isList(Y))) active(isNePal(X)) => mark(isQid(X)) active(isNePal(!6220!6220(X, !6220!6220(Y, X)))) => mark(and(isQid(X), isPal(Y))) active(isPal(X)) => mark(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(and(X, Y)) => active(and(mark(X), Y)) mark(tt) => active(tt) mark(isList(X)) => active(isList(X)) mark(isNeList(X)) => active(isNeList(X)) mark(isQid(X)) => active(isQid(X)) mark(isNePal(X)) => active(isNePal(X)) mark(isPal(X)) => active(isPal(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) and(mark(X), Y) => and(X, Y) and(X, mark(Y)) => and(X, Y) and(active(X), Y) => and(X, Y) and(X, active(Y)) => and(X, Y) isList(mark(X)) => isList(X) isList(active(X)) => isList(X) isNeList(mark(X)) => isNeList(X) isNeList(active(X)) => isNeList(X) isQid(mark(X)) => isQid(X) isQid(active(X)) => isQid(X) isNePal(mark(X)) => isNePal(X) isNePal(active(X)) => isNePal(X) isPal(mark(X)) => isPal(X) isPal(active(X)) => isPal(X) We use rule removal, following [Kop12, Theorem 2.23]. This gives the following requirements (possibly using Theorems 2.25 and 2.26 in [Kop12]): 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(and(tt, X)) >? mark(X) active(isList(X)) >? mark(isNeList(X)) active(isList(nil)) >? mark(tt) active(isList(!6220!6220(X, Y))) >? mark(and(isList(X), isList(Y))) active(isNeList(X)) >? mark(isQid(X)) active(isNeList(!6220!6220(X, Y))) >? mark(and(isList(X), isNeList(Y))) active(isNeList(!6220!6220(X, Y))) >? mark(and(isNeList(X), isList(Y))) active(isNePal(X)) >? mark(isQid(X)) active(isNePal(!6220!6220(X, !6220!6220(Y, X)))) >? mark(and(isQid(X), isPal(Y))) active(isPal(X)) >? mark(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(and(X, Y)) >? active(and(mark(X), Y)) mark(tt) >? active(tt) mark(isList(X)) >? active(isList(X)) mark(isNeList(X)) >? active(isNeList(X)) mark(isQid(X)) >? active(isQid(X)) mark(isNePal(X)) >? active(isNePal(X)) mark(isPal(X)) >? active(isPal(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) and(mark(X), Y) >? and(X, Y) and(X, mark(Y)) >? and(X, Y) and(active(X), Y) >? and(X, Y) and(X, active(Y)) >? and(X, Y) isList(mark(X)) >? isList(X) isList(active(X)) >? isList(X) isNeList(mark(X)) >? isNeList(X) isNeList(active(X)) >? isNeList(X) isQid(mark(X)) >? isQid(X) isQid(active(X)) >? isQid(X) isNePal(mark(X)) >? isNePal(X) isNePal(active(X)) >? isNePal(X) isPal(mark(X)) >? isPal(X) isPal(active(X)) >? isPal(X) We orient these requirements with a polynomial interpretation in the natural numbers. The following interpretation satisfies the requirements: !6220!6220 = \y0y1.y1 + 2y0 a = 1 active = \y0.y0 and = \y0y1.y1 + 2y0 e = 0 i = 0 isList = \y0.2y0 isNeList = \y0.2y0 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))]] = x2 + 2x1 + 4x0 >= x2 + 2x0 + 2x1 = [[mark(!6220!6220(_x0, !6220!6220(_x1, _x2)))]] [[active(!6220!6220(_x0, nil))]] = 2x0 >= x0 = [[mark(_x0)]] [[active(!6220!6220(nil, _x0))]] = x0 >= x0 = [[mark(_x0)]] [[active(and(tt, _x0))]] = x0 >= x0 = [[mark(_x0)]] [[active(isList(_x0))]] = 2x0 >= 2x0 = [[mark(isNeList(_x0))]] [[active(isList(nil))]] = 0 >= 0 = [[mark(tt)]] [[active(isList(!6220!6220(_x0, _x1)))]] = 2x1 + 4x0 >= 2x1 + 4x0 = [[mark(and(isList(_x0), isList(_x1)))]] [[active(isNeList(_x0))]] = 2x0 >= x0 = [[mark(isQid(_x0))]] [[active(isNeList(!6220!6220(_x0, _x1)))]] = 2x1 + 4x0 >= 2x1 + 4x0 = [[mark(and(isList(_x0), isNeList(_x1)))]] [[active(isNeList(!6220!6220(_x0, _x1)))]] = 2x1 + 4x0 >= 2x1 + 4x0 = [[mark(and(isNeList(_x0), isList(_x1)))]] [[active(isNePal(_x0))]] = 2x0 >= x0 = [[mark(isQid(_x0))]] [[active(isNePal(!6220!6220(_x0, !6220!6220(_x1, _x0))))]] = 4x1 + 6x0 >= 2x0 + 2x1 = [[mark(and(isQid(_x0), isPal(_x1)))]] [[active(isPal(_x0))]] = 2x0 >= 2x0 = [[mark(isNePal(_x0))]] [[active(isPal(nil))]] = 0 >= 0 = [[mark(tt)]] [[active(isQid(a))]] = 1 > 0 = [[mark(tt)]] [[active(isQid(e))]] = 0 >= 0 = [[mark(tt)]] [[active(isQid(i))]] = 0 >= 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(and(_x0, _x1))]] = x1 + 2x0 >= x1 + 2x0 = [[active(and(mark(_x0), _x1))]] [[mark(tt)]] = 0 >= 0 = [[active(tt)]] [[mark(isList(_x0))]] = 2x0 >= 2x0 = [[active(isList(_x0))]] [[mark(isNeList(_x0))]] = 2x0 >= 2x0 = [[active(isNeList(_x0))]] [[mark(isQid(_x0))]] = x0 >= x0 = [[active(isQid(_x0))]] [[mark(isNePal(_x0))]] = 2x0 >= 2x0 = [[active(isNePal(_x0))]] [[mark(isPal(_x0))]] = 2x0 >= 2x0 = [[active(isPal(_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)]] [[and(mark(_x0), _x1)]] = x1 + 2x0 >= x1 + 2x0 = [[and(_x0, _x1)]] [[and(_x0, mark(_x1))]] = x1 + 2x0 >= x1 + 2x0 = [[and(_x0, _x1)]] [[and(active(_x0), _x1)]] = x1 + 2x0 >= x1 + 2x0 = [[and(_x0, _x1)]] [[and(_x0, active(_x1))]] = x1 + 2x0 >= x1 + 2x0 = [[and(_x0, _x1)]] [[isList(mark(_x0))]] = 2x0 >= 2x0 = [[isList(_x0)]] [[isList(active(_x0))]] = 2x0 >= 2x0 = [[isList(_x0)]] [[isNeList(mark(_x0))]] = 2x0 >= 2x0 = [[isNeList(_x0)]] [[isNeList(active(_x0))]] = 2x0 >= 2x0 = [[isNeList(_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)]] [[isPal(mark(_x0))]] = 2x0 >= 2x0 = [[isPal(_x0)]] [[isPal(active(_x0))]] = 2x0 >= 2x0 = [[isPal(_x0)]] We can thus remove the following rules: 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(!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(and(tt, X)) >? mark(X) active(isList(X)) >? mark(isNeList(X)) active(isList(nil)) >? mark(tt) active(isList(!6220!6220(X, Y))) >? mark(and(isList(X), isList(Y))) active(isNeList(X)) >? mark(isQid(X)) active(isNeList(!6220!6220(X, Y))) >? mark(and(isList(X), isNeList(Y))) active(isNeList(!6220!6220(X, Y))) >? mark(and(isNeList(X), isList(Y))) active(isNePal(X)) >? mark(isQid(X)) active(isNePal(!6220!6220(X, !6220!6220(Y, X)))) >? mark(and(isQid(X), isPal(Y))) active(isPal(X)) >? mark(isNePal(X)) active(isPal(nil)) >? 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(and(X, Y)) >? active(and(mark(X), Y)) mark(tt) >? active(tt) mark(isList(X)) >? active(isList(X)) mark(isNeList(X)) >? active(isNeList(X)) mark(isQid(X)) >? active(isQid(X)) mark(isNePal(X)) >? active(isNePal(X)) mark(isPal(X)) >? active(isPal(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) and(mark(X), Y) >? and(X, Y) and(X, mark(Y)) >? and(X, Y) and(active(X), Y) >? and(X, Y) and(X, active(Y)) >? and(X, Y) isList(mark(X)) >? isList(X) isList(active(X)) >? isList(X) isNeList(mark(X)) >? isNeList(X) isNeList(active(X)) >? isNeList(X) isQid(mark(X)) >? isQid(X) isQid(active(X)) >? isQid(X) isNePal(mark(X)) >? isNePal(X) isNePal(active(X)) >? isNePal(X) isPal(mark(X)) >? isPal(X) isPal(active(X)) >? isPal(X) We orient these requirements with a polynomial interpretation in the natural numbers. The following interpretation satisfies the requirements: !6220!6220 = \y0y1.y0 + y1 a = 0 active = \y0.y0 and = \y0y1.y0 + y1 e = 1 i = 0 isList = \y0.2y0 isNeList = \y0.2y0 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(!6220!6220(!6220!6220(_x0, _x1), _x2))]] = x0 + x1 + x2 >= x0 + x1 + x2 = [[mark(!6220!6220(_x0, !6220!6220(_x1, _x2)))]] [[active(!6220!6220(_x0, nil))]] = x0 >= x0 = [[mark(_x0)]] [[active(!6220!6220(nil, _x0))]] = x0 >= x0 = [[mark(_x0)]] [[active(and(tt, _x0))]] = x0 >= x0 = [[mark(_x0)]] [[active(isList(_x0))]] = 2x0 >= 2x0 = [[mark(isNeList(_x0))]] [[active(isList(nil))]] = 0 >= 0 = [[mark(tt)]] [[active(isList(!6220!6220(_x0, _x1)))]] = 2x0 + 2x1 >= 2x0 + 2x1 = [[mark(and(isList(_x0), isList(_x1)))]] [[active(isNeList(_x0))]] = 2x0 >= x0 = [[mark(isQid(_x0))]] [[active(isNeList(!6220!6220(_x0, _x1)))]] = 2x0 + 2x1 >= 2x0 + 2x1 = [[mark(and(isList(_x0), isNeList(_x1)))]] [[active(isNeList(!6220!6220(_x0, _x1)))]] = 2x0 + 2x1 >= 2x0 + 2x1 = [[mark(and(isNeList(_x0), isList(_x1)))]] [[active(isNePal(_x0))]] = x0 >= x0 = [[mark(isQid(_x0))]] [[active(isNePal(!6220!6220(_x0, !6220!6220(_x1, _x0))))]] = x1 + 2x0 >= x0 + x1 = [[mark(and(isQid(_x0), isPal(_x1)))]] [[active(isPal(_x0))]] = x0 >= x0 = [[mark(isNePal(_x0))]] [[active(isPal(nil))]] = 0 >= 0 = [[mark(tt)]] [[active(isQid(e))]] = 1 > 0 = [[mark(tt)]] [[active(isQid(i))]] = 0 >= 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(and(_x0, _x1))]] = x0 + x1 >= x0 + x1 = [[active(and(mark(_x0), _x1))]] [[mark(tt)]] = 0 >= 0 = [[active(tt)]] [[mark(isList(_x0))]] = 2x0 >= 2x0 = [[active(isList(_x0))]] [[mark(isNeList(_x0))]] = 2x0 >= 2x0 = [[active(isNeList(_x0))]] [[mark(isQid(_x0))]] = x0 >= x0 = [[active(isQid(_x0))]] [[mark(isNePal(_x0))]] = x0 >= x0 = [[active(isNePal(_x0))]] [[mark(isPal(_x0))]] = x0 >= x0 = [[active(isPal(_x0))]] [[mark(a)]] = 0 >= 0 = [[active(a)]] [[mark(e)]] = 1 >= 1 = [[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)]] [[and(mark(_x0), _x1)]] = x0 + x1 >= x0 + x1 = [[and(_x0, _x1)]] [[and(_x0, mark(_x1))]] = x0 + x1 >= x0 + x1 = [[and(_x0, _x1)]] [[and(active(_x0), _x1)]] = x0 + x1 >= x0 + x1 = [[and(_x0, _x1)]] [[and(_x0, active(_x1))]] = x0 + x1 >= x0 + x1 = [[and(_x0, _x1)]] [[isList(mark(_x0))]] = 2x0 >= 2x0 = [[isList(_x0)]] [[isList(active(_x0))]] = 2x0 >= 2x0 = [[isList(_x0)]] [[isNeList(mark(_x0))]] = 2x0 >= 2x0 = [[isNeList(_x0)]] [[isNeList(active(_x0))]] = 2x0 >= 2x0 = [[isNeList(_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)]] [[isPal(mark(_x0))]] = x0 >= x0 = [[isPal(_x0)]] [[isPal(active(_x0))]] = x0 >= x0 = [[isPal(_x0)]] We can thus remove the following rules: active(isQid(e)) => 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(!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(and(tt, X)) >? mark(X) active(isList(X)) >? mark(isNeList(X)) active(isList(nil)) >? mark(tt) active(isList(!6220!6220(X, Y))) >? mark(and(isList(X), isList(Y))) active(isNeList(X)) >? mark(isQid(X)) active(isNeList(!6220!6220(X, Y))) >? mark(and(isList(X), isNeList(Y))) active(isNeList(!6220!6220(X, Y))) >? mark(and(isNeList(X), isList(Y))) active(isNePal(X)) >? mark(isQid(X)) active(isNePal(!6220!6220(X, !6220!6220(Y, X)))) >? mark(and(isQid(X), isPal(Y))) active(isPal(X)) >? mark(isNePal(X)) active(isPal(nil)) >? 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(and(X, Y)) >? active(and(mark(X), Y)) mark(tt) >? active(tt) mark(isList(X)) >? active(isList(X)) mark(isNeList(X)) >? active(isNeList(X)) mark(isQid(X)) >? active(isQid(X)) mark(isNePal(X)) >? active(isNePal(X)) mark(isPal(X)) >? active(isPal(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) and(mark(X), Y) >? and(X, Y) and(X, mark(Y)) >? and(X, Y) and(active(X), Y) >? and(X, Y) and(X, active(Y)) >? and(X, Y) isList(mark(X)) >? isList(X) isList(active(X)) >? isList(X) isNeList(mark(X)) >? isNeList(X) isNeList(active(X)) >? isNeList(X) isQid(mark(X)) >? isQid(X) isQid(active(X)) >? isQid(X) isNePal(mark(X)) >? isNePal(X) isNePal(active(X)) >? isNePal(X) isPal(mark(X)) >? isPal(X) isPal(active(X)) >? isPal(X) We orient these requirements with a polynomial interpretation in the natural numbers. The following interpretation satisfies the requirements: !6220!6220 = \y0y1.y0 + y1 a = 0 active = \y0.y0 and = \y0y1.y0 + y1 e = 0 i = 0 isList = \y0.2y0 isNeList = \y0.2y0 isNePal = \y0.2y0 isPal = \y0.2y0 isQid = \y0.2y0 mark = \y0.y0 nil = 0 o = 2 tt = 0 u = 0 Using this interpretation, the requirements translate to: [[active(!6220!6220(!6220!6220(_x0, _x1), _x2))]] = x0 + x1 + x2 >= x0 + x1 + x2 = [[mark(!6220!6220(_x0, !6220!6220(_x1, _x2)))]] [[active(!6220!6220(_x0, nil))]] = x0 >= x0 = [[mark(_x0)]] [[active(!6220!6220(nil, _x0))]] = x0 >= x0 = [[mark(_x0)]] [[active(and(tt, _x0))]] = x0 >= x0 = [[mark(_x0)]] [[active(isList(_x0))]] = 2x0 >= 2x0 = [[mark(isNeList(_x0))]] [[active(isList(nil))]] = 0 >= 0 = [[mark(tt)]] [[active(isList(!6220!6220(_x0, _x1)))]] = 2x0 + 2x1 >= 2x0 + 2x1 = [[mark(and(isList(_x0), isList(_x1)))]] [[active(isNeList(_x0))]] = 2x0 >= 2x0 = [[mark(isQid(_x0))]] [[active(isNeList(!6220!6220(_x0, _x1)))]] = 2x0 + 2x1 >= 2x0 + 2x1 = [[mark(and(isList(_x0), isNeList(_x1)))]] [[active(isNeList(!6220!6220(_x0, _x1)))]] = 2x0 + 2x1 >= 2x0 + 2x1 = [[mark(and(isNeList(_x0), isList(_x1)))]] [[active(isNePal(_x0))]] = 2x0 >= 2x0 = [[mark(isQid(_x0))]] [[active(isNePal(!6220!6220(_x0, !6220!6220(_x1, _x0))))]] = 2x1 + 4x0 >= 2x0 + 2x1 = [[mark(and(isQid(_x0), isPal(_x1)))]] [[active(isPal(_x0))]] = 2x0 >= 2x0 = [[mark(isNePal(_x0))]] [[active(isPal(nil))]] = 0 >= 0 = [[mark(tt)]] [[active(isQid(i))]] = 0 >= 0 = [[mark(tt)]] [[active(isQid(o))]] = 4 > 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(and(_x0, _x1))]] = x0 + x1 >= x0 + x1 = [[active(and(mark(_x0), _x1))]] [[mark(tt)]] = 0 >= 0 = [[active(tt)]] [[mark(isList(_x0))]] = 2x0 >= 2x0 = [[active(isList(_x0))]] [[mark(isNeList(_x0))]] = 2x0 >= 2x0 = [[active(isNeList(_x0))]] [[mark(isQid(_x0))]] = 2x0 >= 2x0 = [[active(isQid(_x0))]] [[mark(isNePal(_x0))]] = 2x0 >= 2x0 = [[active(isNePal(_x0))]] [[mark(isPal(_x0))]] = 2x0 >= 2x0 = [[active(isPal(_x0))]] [[mark(a)]] = 0 >= 0 = [[active(a)]] [[mark(e)]] = 0 >= 0 = [[active(e)]] [[mark(i)]] = 0 >= 0 = [[active(i)]] [[mark(o)]] = 2 >= 2 = [[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)]] [[and(mark(_x0), _x1)]] = x0 + x1 >= x0 + x1 = [[and(_x0, _x1)]] [[and(_x0, mark(_x1))]] = x0 + x1 >= x0 + x1 = [[and(_x0, _x1)]] [[and(active(_x0), _x1)]] = x0 + x1 >= x0 + x1 = [[and(_x0, _x1)]] [[and(_x0, active(_x1))]] = x0 + x1 >= x0 + x1 = [[and(_x0, _x1)]] [[isList(mark(_x0))]] = 2x0 >= 2x0 = [[isList(_x0)]] [[isList(active(_x0))]] = 2x0 >= 2x0 = [[isList(_x0)]] [[isNeList(mark(_x0))]] = 2x0 >= 2x0 = [[isNeList(_x0)]] [[isNeList(active(_x0))]] = 2x0 >= 2x0 = [[isNeList(_x0)]] [[isQid(mark(_x0))]] = 2x0 >= 2x0 = [[isQid(_x0)]] [[isQid(active(_x0))]] = 2x0 >= 2x0 = [[isQid(_x0)]] [[isNePal(mark(_x0))]] = 2x0 >= 2x0 = [[isNePal(_x0)]] [[isNePal(active(_x0))]] = 2x0 >= 2x0 = [[isNePal(_x0)]] [[isPal(mark(_x0))]] = 2x0 >= 2x0 = [[isPal(_x0)]] [[isPal(active(_x0))]] = 2x0 >= 2x0 = [[isPal(_x0)]] We can thus remove the following rules: active(isQid(o)) => 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(!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(and(tt, X)) >? mark(X) active(isList(X)) >? mark(isNeList(X)) active(isList(nil)) >? mark(tt) active(isList(!6220!6220(X, Y))) >? mark(and(isList(X), isList(Y))) active(isNeList(X)) >? mark(isQid(X)) active(isNeList(!6220!6220(X, Y))) >? mark(and(isList(X), isNeList(Y))) active(isNeList(!6220!6220(X, Y))) >? mark(and(isNeList(X), isList(Y))) active(isNePal(X)) >? mark(isQid(X)) active(isNePal(!6220!6220(X, !6220!6220(Y, X)))) >? mark(and(isQid(X), isPal(Y))) active(isPal(X)) >? mark(isNePal(X)) active(isPal(nil)) >? mark(tt) active(isQid(i)) >? mark(tt) active(isQid(u)) >? mark(tt) mark(!6220!6220(X, Y)) >? active(!6220!6220(mark(X), mark(Y))) mark(nil) >? active(nil) mark(and(X, Y)) >? active(and(mark(X), Y)) mark(tt) >? active(tt) mark(isList(X)) >? active(isList(X)) mark(isNeList(X)) >? active(isNeList(X)) mark(isQid(X)) >? active(isQid(X)) mark(isNePal(X)) >? active(isNePal(X)) mark(isPal(X)) >? active(isPal(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) and(mark(X), Y) >? and(X, Y) and(X, mark(Y)) >? and(X, Y) and(active(X), Y) >? and(X, Y) and(X, active(Y)) >? and(X, Y) isList(mark(X)) >? isList(X) isList(active(X)) >? isList(X) isNeList(mark(X)) >? isNeList(X) isNeList(active(X)) >? isNeList(X) isQid(mark(X)) >? isQid(X) isQid(active(X)) >? isQid(X) isNePal(mark(X)) >? isNePal(X) isNePal(active(X)) >? isNePal(X) isPal(mark(X)) >? isPal(X) isPal(active(X)) >? isPal(X) We orient these requirements with a polynomial interpretation in the natural numbers. The following interpretation satisfies the requirements: !6220!6220 = \y0y1.y1 + 2y0 a = 0 active = \y0.y0 and = \y0y1.y0 + y1 e = 0 i = 3 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(!6220!6220(!6220!6220(_x0, _x1), _x2))]] = x2 + 2x1 + 4x0 >= x2 + 2x0 + 2x1 = [[mark(!6220!6220(_x0, !6220!6220(_x1, _x2)))]] [[active(!6220!6220(_x0, nil))]] = 2x0 >= x0 = [[mark(_x0)]] [[active(!6220!6220(nil, _x0))]] = x0 >= x0 = [[mark(_x0)]] [[active(and(tt, _x0))]] = x0 >= x0 = [[mark(_x0)]] [[active(isList(_x0))]] = x0 >= x0 = [[mark(isNeList(_x0))]] [[active(isList(nil))]] = 0 >= 0 = [[mark(tt)]] [[active(isList(!6220!6220(_x0, _x1)))]] = x1 + 2x0 >= x0 + x1 = [[mark(and(isList(_x0), isList(_x1)))]] [[active(isNeList(_x0))]] = x0 >= x0 = [[mark(isQid(_x0))]] [[active(isNeList(!6220!6220(_x0, _x1)))]] = x1 + 2x0 >= x0 + x1 = [[mark(and(isList(_x0), isNeList(_x1)))]] [[active(isNeList(!6220!6220(_x0, _x1)))]] = x1 + 2x0 >= x0 + x1 = [[mark(and(isNeList(_x0), isList(_x1)))]] [[active(isNePal(_x0))]] = x0 >= x0 = [[mark(isQid(_x0))]] [[active(isNePal(!6220!6220(_x0, !6220!6220(_x1, _x0))))]] = 2x1 + 3x0 >= x0 + x1 = [[mark(and(isQid(_x0), isPal(_x1)))]] [[active(isPal(_x0))]] = x0 >= x0 = [[mark(isNePal(_x0))]] [[active(isPal(nil))]] = 0 >= 0 = [[mark(tt)]] [[active(isQid(i))]] = 3 > 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(and(_x0, _x1))]] = x0 + x1 >= x0 + x1 = [[active(and(mark(_x0), _x1))]] [[mark(tt)]] = 0 >= 0 = [[active(tt)]] [[mark(isList(_x0))]] = x0 >= x0 = [[active(isList(_x0))]] [[mark(isNeList(_x0))]] = x0 >= x0 = [[active(isNeList(_x0))]] [[mark(isQid(_x0))]] = x0 >= x0 = [[active(isQid(_x0))]] [[mark(isNePal(_x0))]] = x0 >= x0 = [[active(isNePal(_x0))]] [[mark(isPal(_x0))]] = x0 >= x0 = [[active(isPal(_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)]] = 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)]] [[and(mark(_x0), _x1)]] = x0 + x1 >= x0 + x1 = [[and(_x0, _x1)]] [[and(_x0, mark(_x1))]] = x0 + x1 >= x0 + x1 = [[and(_x0, _x1)]] [[and(active(_x0), _x1)]] = x0 + x1 >= x0 + x1 = [[and(_x0, _x1)]] [[and(_x0, active(_x1))]] = x0 + x1 >= x0 + x1 = [[and(_x0, _x1)]] [[isList(mark(_x0))]] = x0 >= x0 = [[isList(_x0)]] [[isList(active(_x0))]] = x0 >= x0 = [[isList(_x0)]] [[isNeList(mark(_x0))]] = x0 >= x0 = [[isNeList(_x0)]] [[isNeList(active(_x0))]] = x0 >= x0 = [[isNeList(_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)]] [[isPal(mark(_x0))]] = x0 >= x0 = [[isPal(_x0)]] [[isPal(active(_x0))]] = x0 >= x0 = [[isPal(_x0)]] We can thus remove the following rules: 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(!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(and(tt, X)) >? mark(X) active(isList(X)) >? mark(isNeList(X)) active(isList(nil)) >? mark(tt) active(isList(!6220!6220(X, Y))) >? mark(and(isList(X), isList(Y))) active(isNeList(X)) >? mark(isQid(X)) active(isNeList(!6220!6220(X, Y))) >? mark(and(isList(X), isNeList(Y))) active(isNeList(!6220!6220(X, Y))) >? mark(and(isNeList(X), isList(Y))) active(isNePal(X)) >? mark(isQid(X)) active(isNePal(!6220!6220(X, !6220!6220(Y, X)))) >? mark(and(isQid(X), isPal(Y))) active(isPal(X)) >? mark(isNePal(X)) active(isPal(nil)) >? mark(tt) active(isQid(u)) >? mark(tt) mark(!6220!6220(X, Y)) >? active(!6220!6220(mark(X), mark(Y))) mark(nil) >? active(nil) mark(and(X, Y)) >? active(and(mark(X), Y)) mark(tt) >? active(tt) mark(isList(X)) >? active(isList(X)) mark(isNeList(X)) >? active(isNeList(X)) mark(isQid(X)) >? active(isQid(X)) mark(isNePal(X)) >? active(isNePal(X)) mark(isPal(X)) >? active(isPal(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) and(mark(X), Y) >? and(X, Y) and(X, mark(Y)) >? and(X, Y) and(active(X), Y) >? and(X, Y) and(X, active(Y)) >? and(X, Y) isList(mark(X)) >? isList(X) isList(active(X)) >? isList(X) isNeList(mark(X)) >? isNeList(X) isNeList(active(X)) >? isNeList(X) isQid(mark(X)) >? isQid(X) isQid(active(X)) >? isQid(X) isNePal(mark(X)) >? isNePal(X) isNePal(active(X)) >? isNePal(X) isPal(mark(X)) >? isPal(X) isPal(active(X)) >? isPal(X) We orient these requirements with a polynomial interpretation in the natural numbers. The following interpretation satisfies the requirements: !6220!6220 = \y0y1.y1 + 2y0 a = 1 active = \y0.y0 and = \y0y1.y0 + y1 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 = 2 Using this interpretation, the requirements translate to: [[active(!6220!6220(!6220!6220(_x0, _x1), _x2))]] = x2 + 2x1 + 4x0 >= x2 + 2x0 + 2x1 = [[mark(!6220!6220(_x0, !6220!6220(_x1, _x2)))]] [[active(!6220!6220(_x0, nil))]] = 2x0 >= x0 = [[mark(_x0)]] [[active(!6220!6220(nil, _x0))]] = x0 >= x0 = [[mark(_x0)]] [[active(and(tt, _x0))]] = x0 >= x0 = [[mark(_x0)]] [[active(isList(_x0))]] = x0 >= x0 = [[mark(isNeList(_x0))]] [[active(isList(nil))]] = 0 >= 0 = [[mark(tt)]] [[active(isList(!6220!6220(_x0, _x1)))]] = x1 + 2x0 >= x0 + x1 = [[mark(and(isList(_x0), isList(_x1)))]] [[active(isNeList(_x0))]] = x0 >= x0 = [[mark(isQid(_x0))]] [[active(isNeList(!6220!6220(_x0, _x1)))]] = x1 + 2x0 >= x0 + x1 = [[mark(and(isList(_x0), isNeList(_x1)))]] [[active(isNeList(!6220!6220(_x0, _x1)))]] = x1 + 2x0 >= x0 + x1 = [[mark(and(isNeList(_x0), isList(_x1)))]] [[active(isNePal(_x0))]] = x0 >= x0 = [[mark(isQid(_x0))]] [[active(isNePal(!6220!6220(_x0, !6220!6220(_x1, _x0))))]] = 2x1 + 3x0 >= x0 + x1 = [[mark(and(isQid(_x0), isPal(_x1)))]] [[active(isPal(_x0))]] = x0 >= x0 = [[mark(isNePal(_x0))]] [[active(isPal(nil))]] = 0 >= 0 = [[mark(tt)]] [[active(isQid(u))]] = 2 > 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(and(_x0, _x1))]] = x0 + x1 >= x0 + x1 = [[active(and(mark(_x0), _x1))]] [[mark(tt)]] = 0 >= 0 = [[active(tt)]] [[mark(isList(_x0))]] = x0 >= x0 = [[active(isList(_x0))]] [[mark(isNeList(_x0))]] = x0 >= x0 = [[active(isNeList(_x0))]] [[mark(isQid(_x0))]] = x0 >= x0 = [[active(isQid(_x0))]] [[mark(isNePal(_x0))]] = x0 >= x0 = [[active(isNePal(_x0))]] [[mark(isPal(_x0))]] = x0 >= x0 = [[active(isPal(_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)]] = 2 >= 2 = [[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)]] [[and(mark(_x0), _x1)]] = x0 + x1 >= x0 + x1 = [[and(_x0, _x1)]] [[and(_x0, mark(_x1))]] = x0 + x1 >= x0 + x1 = [[and(_x0, _x1)]] [[and(active(_x0), _x1)]] = x0 + x1 >= x0 + x1 = [[and(_x0, _x1)]] [[and(_x0, active(_x1))]] = x0 + x1 >= x0 + x1 = [[and(_x0, _x1)]] [[isList(mark(_x0))]] = x0 >= x0 = [[isList(_x0)]] [[isList(active(_x0))]] = x0 >= x0 = [[isList(_x0)]] [[isNeList(mark(_x0))]] = x0 >= x0 = [[isNeList(_x0)]] [[isNeList(active(_x0))]] = x0 >= x0 = [[isNeList(_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)]] [[isPal(mark(_x0))]] = x0 >= x0 = [[isPal(_x0)]] [[isPal(active(_x0))]] = x0 >= x0 = [[isPal(_x0)]] We can thus remove the following rules: 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(!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(and(tt, X)) >? mark(X) active(isList(X)) >? mark(isNeList(X)) active(isList(nil)) >? mark(tt) active(isList(!6220!6220(X, Y))) >? mark(and(isList(X), isList(Y))) active(isNeList(X)) >? mark(isQid(X)) active(isNeList(!6220!6220(X, Y))) >? mark(and(isList(X), isNeList(Y))) active(isNeList(!6220!6220(X, Y))) >? mark(and(isNeList(X), isList(Y))) active(isNePal(X)) >? mark(isQid(X)) active(isNePal(!6220!6220(X, !6220!6220(Y, X)))) >? mark(and(isQid(X), isPal(Y))) active(isPal(X)) >? mark(isNePal(X)) active(isPal(nil)) >? mark(tt) mark(!6220!6220(X, Y)) >? active(!6220!6220(mark(X), mark(Y))) mark(nil) >? active(nil) mark(and(X, Y)) >? active(and(mark(X), Y)) mark(tt) >? active(tt) mark(isList(X)) >? active(isList(X)) mark(isNeList(X)) >? active(isNeList(X)) mark(isQid(X)) >? active(isQid(X)) mark(isNePal(X)) >? active(isNePal(X)) mark(isPal(X)) >? active(isPal(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) and(mark(X), Y) >? and(X, Y) and(X, mark(Y)) >? and(X, Y) and(active(X), Y) >? and(X, Y) and(X, active(Y)) >? and(X, Y) isList(mark(X)) >? isList(X) isList(active(X)) >? isList(X) isNeList(mark(X)) >? isNeList(X) isNeList(active(X)) >? isNeList(X) isQid(mark(X)) >? isQid(X) isQid(active(X)) >? isQid(X) isNePal(mark(X)) >? isNePal(X) isNePal(active(X)) >? isNePal(X) isPal(mark(X)) >? isPal(X) isPal(active(X)) >? isPal(X) We orient these requirements with a polynomial interpretation in the natural numbers. The following interpretation satisfies the requirements: !6220!6220 = \y0y1.y1 + 2y0 a = 0 active = \y0.y0 and = \y0y1.y1 + 2y0 e = 0 i = 0 isList = \y0.y0 isNeList = \y0.y0 isNePal = \y0.1 + 2y0 isPal = \y0.1 + 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))]] = x2 + 2x1 + 4x0 >= x2 + 2x0 + 2x1 = [[mark(!6220!6220(_x0, !6220!6220(_x1, _x2)))]] [[active(!6220!6220(_x0, nil))]] = 2x0 >= x0 = [[mark(_x0)]] [[active(!6220!6220(nil, _x0))]] = x0 >= x0 = [[mark(_x0)]] [[active(and(tt, _x0))]] = x0 >= x0 = [[mark(_x0)]] [[active(isList(_x0))]] = x0 >= x0 = [[mark(isNeList(_x0))]] [[active(isList(nil))]] = 0 >= 0 = [[mark(tt)]] [[active(isList(!6220!6220(_x0, _x1)))]] = x1 + 2x0 >= x1 + 2x0 = [[mark(and(isList(_x0), isList(_x1)))]] [[active(isNeList(_x0))]] = x0 >= x0 = [[mark(isQid(_x0))]] [[active(isNeList(!6220!6220(_x0, _x1)))]] = x1 + 2x0 >= x1 + 2x0 = [[mark(and(isList(_x0), isNeList(_x1)))]] [[active(isNeList(!6220!6220(_x0, _x1)))]] = x1 + 2x0 >= x1 + 2x0 = [[mark(and(isNeList(_x0), isList(_x1)))]] [[active(isNePal(_x0))]] = 1 + 2x0 > x0 = [[mark(isQid(_x0))]] [[active(isNePal(!6220!6220(_x0, !6220!6220(_x1, _x0))))]] = 1 + 4x1 + 6x0 >= 1 + 2x0 + 2x1 = [[mark(and(isQid(_x0), isPal(_x1)))]] [[active(isPal(_x0))]] = 1 + 2x0 >= 1 + 2x0 = [[mark(isNePal(_x0))]] [[active(isPal(nil))]] = 1 > 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(and(_x0, _x1))]] = x1 + 2x0 >= x1 + 2x0 = [[active(and(mark(_x0), _x1))]] [[mark(tt)]] = 0 >= 0 = [[active(tt)]] [[mark(isList(_x0))]] = x0 >= x0 = [[active(isList(_x0))]] [[mark(isNeList(_x0))]] = x0 >= x0 = [[active(isNeList(_x0))]] [[mark(isQid(_x0))]] = x0 >= x0 = [[active(isQid(_x0))]] [[mark(isNePal(_x0))]] = 1 + 2x0 >= 1 + 2x0 = [[active(isNePal(_x0))]] [[mark(isPal(_x0))]] = 1 + 2x0 >= 1 + 2x0 = [[active(isPal(_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)]] = 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)]] [[and(mark(_x0), _x1)]] = x1 + 2x0 >= x1 + 2x0 = [[and(_x0, _x1)]] [[and(_x0, mark(_x1))]] = x1 + 2x0 >= x1 + 2x0 = [[and(_x0, _x1)]] [[and(active(_x0), _x1)]] = x1 + 2x0 >= x1 + 2x0 = [[and(_x0, _x1)]] [[and(_x0, active(_x1))]] = x1 + 2x0 >= x1 + 2x0 = [[and(_x0, _x1)]] [[isList(mark(_x0))]] = x0 >= x0 = [[isList(_x0)]] [[isList(active(_x0))]] = x0 >= x0 = [[isList(_x0)]] [[isNeList(mark(_x0))]] = x0 >= x0 = [[isNeList(_x0)]] [[isNeList(active(_x0))]] = x0 >= x0 = [[isNeList(_x0)]] [[isQid(mark(_x0))]] = x0 >= x0 = [[isQid(_x0)]] [[isQid(active(_x0))]] = x0 >= x0 = [[isQid(_x0)]] [[isNePal(mark(_x0))]] = 1 + 2x0 >= 1 + 2x0 = [[isNePal(_x0)]] [[isNePal(active(_x0))]] = 1 + 2x0 >= 1 + 2x0 = [[isNePal(_x0)]] [[isPal(mark(_x0))]] = 1 + 2x0 >= 1 + 2x0 = [[isPal(_x0)]] [[isPal(active(_x0))]] = 1 + 2x0 >= 1 + 2x0 = [[isPal(_x0)]] We can thus remove the following rules: active(isNePal(X)) => mark(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(!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(and(tt, X)) >? mark(X) active(isList(X)) >? mark(isNeList(X)) active(isList(nil)) >? mark(tt) active(isList(!6220!6220(X, Y))) >? mark(and(isList(X), isList(Y))) active(isNeList(X)) >? mark(isQid(X)) active(isNeList(!6220!6220(X, Y))) >? mark(and(isList(X), isNeList(Y))) active(isNeList(!6220!6220(X, Y))) >? mark(and(isNeList(X), isList(Y))) active(isNePal(!6220!6220(X, !6220!6220(Y, X)))) >? mark(and(isQid(X), isPal(Y))) active(isPal(X)) >? mark(isNePal(X)) mark(!6220!6220(X, Y)) >? active(!6220!6220(mark(X), mark(Y))) mark(nil) >? active(nil) mark(and(X, Y)) >? active(and(mark(X), Y)) mark(tt) >? active(tt) mark(isList(X)) >? active(isList(X)) mark(isNeList(X)) >? active(isNeList(X)) mark(isQid(X)) >? active(isQid(X)) mark(isNePal(X)) >? active(isNePal(X)) mark(isPal(X)) >? active(isPal(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) and(mark(X), Y) >? and(X, Y) and(X, mark(Y)) >? and(X, Y) and(active(X), Y) >? and(X, Y) and(X, active(Y)) >? and(X, Y) isList(mark(X)) >? isList(X) isList(active(X)) >? isList(X) isNeList(mark(X)) >? isNeList(X) isNeList(active(X)) >? isNeList(X) isQid(mark(X)) >? isQid(X) isQid(active(X)) >? isQid(X) isNePal(mark(X)) >? isNePal(X) isNePal(active(X)) >? isNePal(X) isPal(mark(X)) >? isPal(X) isPal(active(X)) >? isPal(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 a = 0 active = \y0.y0 and = \y0y1.y0 + y1 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(!6220!6220(!6220!6220(_x0, _x1), _x2))]] = 2 + x0 + x1 + x2 >= 2 + x0 + x1 + x2 = [[mark(!6220!6220(_x0, !6220!6220(_x1, _x2)))]] [[active(!6220!6220(_x0, nil))]] = 1 + x0 > x0 = [[mark(_x0)]] [[active(!6220!6220(nil, _x0))]] = 1 + x0 > x0 = [[mark(_x0)]] [[active(and(tt, _x0))]] = x0 >= x0 = [[mark(_x0)]] [[active(isList(_x0))]] = x0 >= x0 = [[mark(isNeList(_x0))]] [[active(isList(nil))]] = 0 >= 0 = [[mark(tt)]] [[active(isList(!6220!6220(_x0, _x1)))]] = 1 + x0 + x1 > x0 + x1 = [[mark(and(isList(_x0), isList(_x1)))]] [[active(isNeList(_x0))]] = x0 >= x0 = [[mark(isQid(_x0))]] [[active(isNeList(!6220!6220(_x0, _x1)))]] = 1 + x0 + x1 > x0 + x1 = [[mark(and(isList(_x0), isNeList(_x1)))]] [[active(isNeList(!6220!6220(_x0, _x1)))]] = 1 + x0 + x1 > x0 + x1 = [[mark(and(isNeList(_x0), isList(_x1)))]] [[active(isNePal(!6220!6220(_x0, !6220!6220(_x1, _x0))))]] = 2 + x1 + 2x0 > x0 + x1 = [[mark(and(isQid(_x0), isPal(_x1)))]] [[active(isPal(_x0))]] = x0 >= x0 = [[mark(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(and(_x0, _x1))]] = x0 + x1 >= x0 + x1 = [[active(and(mark(_x0), _x1))]] [[mark(tt)]] = 0 >= 0 = [[active(tt)]] [[mark(isList(_x0))]] = x0 >= x0 = [[active(isList(_x0))]] [[mark(isNeList(_x0))]] = x0 >= x0 = [[active(isNeList(_x0))]] [[mark(isQid(_x0))]] = x0 >= x0 = [[active(isQid(_x0))]] [[mark(isNePal(_x0))]] = x0 >= x0 = [[active(isNePal(_x0))]] [[mark(isPal(_x0))]] = x0 >= x0 = [[active(isPal(_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)]] = 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)]] [[and(mark(_x0), _x1)]] = x0 + x1 >= x0 + x1 = [[and(_x0, _x1)]] [[and(_x0, mark(_x1))]] = x0 + x1 >= x0 + x1 = [[and(_x0, _x1)]] [[and(active(_x0), _x1)]] = x0 + x1 >= x0 + x1 = [[and(_x0, _x1)]] [[and(_x0, active(_x1))]] = x0 + x1 >= x0 + x1 = [[and(_x0, _x1)]] [[isList(mark(_x0))]] = x0 >= x0 = [[isList(_x0)]] [[isList(active(_x0))]] = x0 >= x0 = [[isList(_x0)]] [[isNeList(mark(_x0))]] = x0 >= x0 = [[isNeList(_x0)]] [[isNeList(active(_x0))]] = x0 >= x0 = [[isNeList(_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)]] [[isPal(mark(_x0))]] = x0 >= x0 = [[isPal(_x0)]] [[isPal(active(_x0))]] = x0 >= x0 = [[isPal(_x0)]] We can thus remove the following rules: active(!6220!6220(X, nil)) => mark(X) active(!6220!6220(nil, X)) => mark(X) active(isList(!6220!6220(X, Y))) => mark(and(isList(X), isList(Y))) active(isNeList(!6220!6220(X, Y))) => mark(and(isList(X), isNeList(Y))) active(isNeList(!6220!6220(X, Y))) => mark(and(isNeList(X), isList(Y))) active(isNePal(!6220!6220(X, !6220!6220(Y, X)))) => mark(and(isQid(X), isPal(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]): active(!6220!6220(!6220!6220(X, Y), Z)) >? mark(!6220!6220(X, !6220!6220(Y, Z))) active(and(tt, X)) >? mark(X) active(isList(X)) >? mark(isNeList(X)) active(isList(nil)) >? mark(tt) active(isNeList(X)) >? mark(isQid(X)) active(isPal(X)) >? mark(isNePal(X)) mark(!6220!6220(X, Y)) >? active(!6220!6220(mark(X), mark(Y))) mark(nil) >? active(nil) mark(and(X, Y)) >? active(and(mark(X), Y)) mark(tt) >? active(tt) mark(isList(X)) >? active(isList(X)) mark(isNeList(X)) >? active(isNeList(X)) mark(isQid(X)) >? active(isQid(X)) mark(isNePal(X)) >? active(isNePal(X)) mark(isPal(X)) >? active(isPal(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) and(mark(X), Y) >? and(X, Y) and(X, mark(Y)) >? and(X, Y) and(active(X), Y) >? and(X, Y) and(X, active(Y)) >? and(X, Y) isList(mark(X)) >? isList(X) isList(active(X)) >? isList(X) isNeList(mark(X)) >? isNeList(X) isNeList(active(X)) >? isNeList(X) isQid(mark(X)) >? isQid(X) isQid(active(X)) >? isQid(X) isNePal(mark(X)) >? isNePal(X) isNePal(active(X)) >? isNePal(X) isPal(mark(X)) >? isPal(X) isPal(active(X)) >? isPal(X) We orient these requirements with a polynomial interpretation in the natural numbers. The following interpretation satisfies the requirements: !6220!6220 = \y0y1.y0 + y1 a = 0 active = \y0.y0 and = \y0y1.y0 + y1 e = 0 i = 0 isList = \y0.1 + y0 isNeList = \y0.y0 isNePal = \y0.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(!6220!6220(!6220!6220(_x0, _x1), _x2))]] = x0 + x1 + x2 >= x0 + x1 + x2 = [[mark(!6220!6220(_x0, !6220!6220(_x1, _x2)))]] [[active(and(tt, _x0))]] = x0 >= x0 = [[mark(_x0)]] [[active(isList(_x0))]] = 1 + x0 > x0 = [[mark(isNeList(_x0))]] [[active(isList(nil))]] = 1 > 0 = [[mark(tt)]] [[active(isNeList(_x0))]] = x0 >= x0 = [[mark(isQid(_x0))]] [[active(isPal(_x0))]] = 1 + x0 > x0 = [[mark(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(and(_x0, _x1))]] = x0 + x1 >= x0 + x1 = [[active(and(mark(_x0), _x1))]] [[mark(tt)]] = 0 >= 0 = [[active(tt)]] [[mark(isList(_x0))]] = 1 + x0 >= 1 + x0 = [[active(isList(_x0))]] [[mark(isNeList(_x0))]] = x0 >= x0 = [[active(isNeList(_x0))]] [[mark(isQid(_x0))]] = x0 >= x0 = [[active(isQid(_x0))]] [[mark(isNePal(_x0))]] = x0 >= x0 = [[active(isNePal(_x0))]] [[mark(isPal(_x0))]] = 1 + x0 >= 1 + x0 = [[active(isPal(_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)]] [[and(mark(_x0), _x1)]] = x0 + x1 >= x0 + x1 = [[and(_x0, _x1)]] [[and(_x0, mark(_x1))]] = x0 + x1 >= x0 + x1 = [[and(_x0, _x1)]] [[and(active(_x0), _x1)]] = x0 + x1 >= x0 + x1 = [[and(_x0, _x1)]] [[and(_x0, active(_x1))]] = x0 + x1 >= x0 + x1 = [[and(_x0, _x1)]] [[isList(mark(_x0))]] = 1 + x0 >= 1 + x0 = [[isList(_x0)]] [[isList(active(_x0))]] = 1 + x0 >= 1 + x0 = [[isList(_x0)]] [[isNeList(mark(_x0))]] = x0 >= x0 = [[isNeList(_x0)]] [[isNeList(active(_x0))]] = x0 >= x0 = [[isNeList(_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)]] [[isPal(mark(_x0))]] = 1 + x0 >= 1 + x0 = [[isPal(_x0)]] [[isPal(active(_x0))]] = 1 + x0 >= 1 + x0 = [[isPal(_x0)]] We can thus remove the following rules: active(isList(X)) => mark(isNeList(X)) active(isList(nil)) => mark(tt) active(isPal(X)) => mark(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(and(tt, X)) >? mark(X) active(isNeList(X)) >? mark(isQid(X)) mark(!6220!6220(X, Y)) >? active(!6220!6220(mark(X), mark(Y))) mark(nil) >? active(nil) mark(and(X, Y)) >? active(and(mark(X), Y)) mark(tt) >? active(tt) mark(isList(X)) >? active(isList(X)) mark(isNeList(X)) >? active(isNeList(X)) mark(isQid(X)) >? active(isQid(X)) mark(isNePal(X)) >? active(isNePal(X)) mark(isPal(X)) >? active(isPal(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) and(mark(X), Y) >? and(X, Y) and(X, mark(Y)) >? and(X, Y) and(active(X), Y) >? and(X, Y) and(X, active(Y)) >? and(X, Y) isList(mark(X)) >? isList(X) isList(active(X)) >? isList(X) isNeList(mark(X)) >? isNeList(X) isNeList(active(X)) >? isNeList(X) isQid(mark(X)) >? isQid(X) isQid(active(X)) >? isQid(X) isNePal(mark(X)) >? isNePal(X) isNePal(active(X)) >? isNePal(X) isPal(mark(X)) >? isPal(X) isPal(active(X)) >? isPal(X) We orient these requirements with a polynomial interpretation in the natural numbers. The following interpretation satisfies the requirements: !6220!6220 = \y0y1.y1 + 2y0 a = 0 active = \y0.y0 and = \y0y1.y0 + y1 e = 0 i = 0 isList = \y0.y0 isNeList = \y0.1 + 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(!6220!6220(!6220!6220(_x0, _x1), _x2))]] = x2 + 2x1 + 4x0 >= x2 + 2x0 + 2x1 = [[mark(!6220!6220(_x0, !6220!6220(_x1, _x2)))]] [[active(and(tt, _x0))]] = x0 >= x0 = [[mark(_x0)]] [[active(isNeList(_x0))]] = 1 + x0 > x0 = [[mark(isQid(_x0))]] [[mark(!6220!6220(_x0, _x1))]] = x1 + 2x0 >= x1 + 2x0 = [[active(!6220!6220(mark(_x0), mark(_x1)))]] [[mark(nil)]] = 0 >= 0 = [[active(nil)]] [[mark(and(_x0, _x1))]] = x0 + x1 >= x0 + x1 = [[active(and(mark(_x0), _x1))]] [[mark(tt)]] = 0 >= 0 = [[active(tt)]] [[mark(isList(_x0))]] = x0 >= x0 = [[active(isList(_x0))]] [[mark(isNeList(_x0))]] = 1 + x0 >= 1 + x0 = [[active(isNeList(_x0))]] [[mark(isQid(_x0))]] = x0 >= x0 = [[active(isQid(_x0))]] [[mark(isNePal(_x0))]] = x0 >= x0 = [[active(isNePal(_x0))]] [[mark(isPal(_x0))]] = x0 >= x0 = [[active(isPal(_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)]] = 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)]] [[and(mark(_x0), _x1)]] = x0 + x1 >= x0 + x1 = [[and(_x0, _x1)]] [[and(_x0, mark(_x1))]] = x0 + x1 >= x0 + x1 = [[and(_x0, _x1)]] [[and(active(_x0), _x1)]] = x0 + x1 >= x0 + x1 = [[and(_x0, _x1)]] [[and(_x0, active(_x1))]] = x0 + x1 >= x0 + x1 = [[and(_x0, _x1)]] [[isList(mark(_x0))]] = x0 >= x0 = [[isList(_x0)]] [[isList(active(_x0))]] = x0 >= x0 = [[isList(_x0)]] [[isNeList(mark(_x0))]] = 1 + x0 >= 1 + x0 = [[isNeList(_x0)]] [[isNeList(active(_x0))]] = 1 + x0 >= 1 + x0 = [[isNeList(_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)]] [[isPal(mark(_x0))]] = x0 >= x0 = [[isPal(_x0)]] [[isPal(active(_x0))]] = x0 >= x0 = [[isPal(_x0)]] We can thus remove the following rules: active(isNeList(X)) => mark(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(!6220!6220(!6220!6220(X, Y), Z)) >? mark(!6220!6220(X, !6220!6220(Y, Z))) active(and(tt, X)) >? mark(X) mark(!6220!6220(X, Y)) >? active(!6220!6220(mark(X), mark(Y))) mark(nil) >? active(nil) mark(and(X, Y)) >? active(and(mark(X), Y)) mark(tt) >? active(tt) mark(isList(X)) >? active(isList(X)) mark(isNeList(X)) >? active(isNeList(X)) mark(isQid(X)) >? active(isQid(X)) mark(isNePal(X)) >? active(isNePal(X)) mark(isPal(X)) >? active(isPal(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) and(mark(X), Y) >? and(X, Y) and(X, mark(Y)) >? and(X, Y) and(active(X), Y) >? and(X, Y) and(X, active(Y)) >? and(X, Y) isList(mark(X)) >? isList(X) isList(active(X)) >? isList(X) isNeList(mark(X)) >? isNeList(X) isNeList(active(X)) >? isNeList(X) isQid(mark(X)) >? isQid(X) isQid(active(X)) >? isQid(X) isNePal(mark(X)) >? isNePal(X) isNePal(active(X)) >? isNePal(X) isPal(mark(X)) >? isPal(X) isPal(active(X)) >? isPal(X) We orient these requirements with a polynomial interpretation in the natural numbers. The following interpretation satisfies the requirements: !6220!6220 = \y0y1.y0 + y1 a = 0 active = \y0.y0 and = \y0y1.1 + y1 + 2y0 e = 1 i = 0 isList = \y0.3 + 2y0 isNeList = \y0.y0 isNePal = \y0.3 + 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(!6220!6220(!6220!6220(_x0, _x1), _x2))]] = x0 + x1 + x2 >= x0 + x1 + x2 = [[mark(!6220!6220(_x0, !6220!6220(_x1, _x2)))]] [[active(and(tt, _x0))]] = 1 + x0 > x0 = [[mark(_x0)]] [[mark(!6220!6220(_x0, _x1))]] = x0 + x1 >= x0 + x1 = [[active(!6220!6220(mark(_x0), mark(_x1)))]] [[mark(nil)]] = 0 >= 0 = [[active(nil)]] [[mark(and(_x0, _x1))]] = 1 + x1 + 2x0 >= 1 + x1 + 2x0 = [[active(and(mark(_x0), _x1))]] [[mark(tt)]] = 0 >= 0 = [[active(tt)]] [[mark(isList(_x0))]] = 3 + 2x0 >= 3 + 2x0 = [[active(isList(_x0))]] [[mark(isNeList(_x0))]] = x0 >= x0 = [[active(isNeList(_x0))]] [[mark(isQid(_x0))]] = x0 >= x0 = [[active(isQid(_x0))]] [[mark(isNePal(_x0))]] = 3 + x0 >= 3 + x0 = [[active(isNePal(_x0))]] [[mark(isPal(_x0))]] = x0 >= x0 = [[active(isPal(_x0))]] [[mark(a)]] = 0 >= 0 = [[active(a)]] [[mark(e)]] = 1 >= 1 = [[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)]] [[and(mark(_x0), _x1)]] = 1 + x1 + 2x0 >= 1 + x1 + 2x0 = [[and(_x0, _x1)]] [[and(_x0, mark(_x1))]] = 1 + x1 + 2x0 >= 1 + x1 + 2x0 = [[and(_x0, _x1)]] [[and(active(_x0), _x1)]] = 1 + x1 + 2x0 >= 1 + x1 + 2x0 = [[and(_x0, _x1)]] [[and(_x0, active(_x1))]] = 1 + x1 + 2x0 >= 1 + x1 + 2x0 = [[and(_x0, _x1)]] [[isList(mark(_x0))]] = 3 + 2x0 >= 3 + 2x0 = [[isList(_x0)]] [[isList(active(_x0))]] = 3 + 2x0 >= 3 + 2x0 = [[isList(_x0)]] [[isNeList(mark(_x0))]] = x0 >= x0 = [[isNeList(_x0)]] [[isNeList(active(_x0))]] = x0 >= x0 = [[isNeList(_x0)]] [[isQid(mark(_x0))]] = x0 >= x0 = [[isQid(_x0)]] [[isQid(active(_x0))]] = x0 >= x0 = [[isQid(_x0)]] [[isNePal(mark(_x0))]] = 3 + x0 >= 3 + x0 = [[isNePal(_x0)]] [[isNePal(active(_x0))]] = 3 + x0 >= 3 + x0 = [[isNePal(_x0)]] [[isPal(mark(_x0))]] = x0 >= x0 = [[isPal(_x0)]] [[isPal(active(_x0))]] = x0 >= x0 = [[isPal(_x0)]] We can thus remove the following rules: active(and(tt, X)) => 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]): active(!6220!6220(!6220!6220(X, Y), Z)) >? mark(!6220!6220(X, !6220!6220(Y, Z))) mark(!6220!6220(X, Y)) >? active(!6220!6220(mark(X), mark(Y))) mark(nil) >? active(nil) mark(and(X, Y)) >? active(and(mark(X), Y)) mark(tt) >? active(tt) mark(isList(X)) >? active(isList(X)) mark(isNeList(X)) >? active(isNeList(X)) mark(isQid(X)) >? active(isQid(X)) mark(isNePal(X)) >? active(isNePal(X)) mark(isPal(X)) >? active(isPal(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) and(mark(X), Y) >? and(X, Y) and(X, mark(Y)) >? and(X, Y) and(active(X), Y) >? and(X, Y) and(X, active(Y)) >? and(X, Y) isList(mark(X)) >? isList(X) isList(active(X)) >? isList(X) isNeList(mark(X)) >? isNeList(X) isNeList(active(X)) >? isNeList(X) isQid(mark(X)) >? isQid(X) isQid(active(X)) >? isQid(X) isNePal(mark(X)) >? isNePal(X) isNePal(active(X)) >? isNePal(X) isPal(mark(X)) >? isPal(X) isPal(active(X)) >? isPal(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 a = 0 active = \y0.y0 and = \y0y1.y0 + y1 e = 0 i = 0 isList = \y0.3 + 2y0 isNeList = \y0.3 + 2y0 isNePal = \y0.2y0 isPal = \y0.y0 isQid = \y0.3 + 2y0 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)))]] [[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(and(_x0, _x1))]] = x0 + x1 >= x0 + x1 = [[active(and(mark(_x0), _x1))]] [[mark(tt)]] = 0 >= 0 = [[active(tt)]] [[mark(isList(_x0))]] = 3 + 2x0 >= 3 + 2x0 = [[active(isList(_x0))]] [[mark(isNeList(_x0))]] = 3 + 2x0 >= 3 + 2x0 = [[active(isNeList(_x0))]] [[mark(isQid(_x0))]] = 3 + 2x0 >= 3 + 2x0 = [[active(isQid(_x0))]] [[mark(isNePal(_x0))]] = 2x0 >= 2x0 = [[active(isNePal(_x0))]] [[mark(isPal(_x0))]] = x0 >= x0 = [[active(isPal(_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)]] = 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)]] [[and(mark(_x0), _x1)]] = x0 + x1 >= x0 + x1 = [[and(_x0, _x1)]] [[and(_x0, mark(_x1))]] = x0 + x1 >= x0 + x1 = [[and(_x0, _x1)]] [[and(active(_x0), _x1)]] = x0 + x1 >= x0 + x1 = [[and(_x0, _x1)]] [[and(_x0, active(_x1))]] = x0 + x1 >= x0 + x1 = [[and(_x0, _x1)]] [[isList(mark(_x0))]] = 3 + 2x0 >= 3 + 2x0 = [[isList(_x0)]] [[isList(active(_x0))]] = 3 + 2x0 >= 3 + 2x0 = [[isList(_x0)]] [[isNeList(mark(_x0))]] = 3 + 2x0 >= 3 + 2x0 = [[isNeList(_x0)]] [[isNeList(active(_x0))]] = 3 + 2x0 >= 3 + 2x0 = [[isNeList(_x0)]] [[isQid(mark(_x0))]] = 3 + 2x0 >= 3 + 2x0 = [[isQid(_x0)]] [[isQid(active(_x0))]] = 3 + 2x0 >= 3 + 2x0 = [[isQid(_x0)]] [[isNePal(mark(_x0))]] = 2x0 >= 2x0 = [[isNePal(_x0)]] [[isNePal(active(_x0))]] = 2x0 >= 2x0 = [[isNePal(_x0)]] [[isPal(mark(_x0))]] = x0 >= x0 = [[isPal(_x0)]] [[isPal(active(_x0))]] = x0 >= x0 = [[isPal(_x0)]] We can thus remove the following rules: active(!6220!6220(!6220!6220(X, Y), Z)) => mark(!6220!6220(X, !6220!6220(Y, Z))) 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(!6220!6220(X, Y)) >? active(!6220!6220(mark(X), mark(Y))) mark(nil) >? active(nil) mark(and(X, Y)) >? active(and(mark(X), Y)) mark(tt) >? active(tt) mark(isList(X)) >? active(isList(X)) mark(isNeList(X)) >? active(isNeList(X)) mark(isQid(X)) >? active(isQid(X)) mark(isNePal(X)) >? active(isNePal(X)) mark(isPal(X)) >? active(isPal(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) and(mark(X), Y) >? and(X, Y) and(X, mark(Y)) >? and(X, Y) and(active(X), Y) >? and(X, Y) and(X, active(Y)) >? and(X, Y) isList(mark(X)) >? isList(X) isList(active(X)) >? isList(X) isNeList(mark(X)) >? isNeList(X) isNeList(active(X)) >? isNeList(X) isQid(mark(X)) >? isQid(X) isQid(active(X)) >? isQid(X) isNePal(mark(X)) >? isNePal(X) isNePal(active(X)) >? isNePal(X) isPal(mark(X)) >? isPal(X) isPal(active(X)) >? isPal(X) We orient these requirements with a polynomial interpretation in the natural numbers. The following interpretation satisfies the requirements: !6220!6220 = \y0y1.y0 + 2y1 a = 0 active = \y0.y0 and = \y0y1.2 + y0 + 2y1 e = 2 i = 0 isList = \y0.y0 isNeList = \y0.2y0 isNePal = \y0.2y0 isPal = \y0.2y0 isQid = \y0.y0 mark = \y0.2y0 nil = 0 o = 0 tt = 0 u = 0 Using this interpretation, the requirements translate to: [[mark(!6220!6220(_x0, _x1))]] = 2x0 + 4x1 >= 2x0 + 4x1 = [[active(!6220!6220(mark(_x0), mark(_x1)))]] [[mark(nil)]] = 0 >= 0 = [[active(nil)]] [[mark(and(_x0, _x1))]] = 4 + 2x0 + 4x1 > 2 + 2x0 + 2x1 = [[active(and(mark(_x0), _x1))]] [[mark(tt)]] = 0 >= 0 = [[active(tt)]] [[mark(isList(_x0))]] = 2x0 >= x0 = [[active(isList(_x0))]] [[mark(isNeList(_x0))]] = 4x0 >= 2x0 = [[active(isNeList(_x0))]] [[mark(isQid(_x0))]] = 2x0 >= x0 = [[active(isQid(_x0))]] [[mark(isNePal(_x0))]] = 4x0 >= 2x0 = [[active(isNePal(_x0))]] [[mark(isPal(_x0))]] = 4x0 >= 2x0 = [[active(isPal(_x0))]] [[mark(a)]] = 0 >= 0 = [[active(a)]] [[mark(e)]] = 4 > 2 = [[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)]] = 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)]] [[and(mark(_x0), _x1)]] = 2 + 2x0 + 2x1 >= 2 + x0 + 2x1 = [[and(_x0, _x1)]] [[and(_x0, mark(_x1))]] = 2 + x0 + 4x1 >= 2 + x0 + 2x1 = [[and(_x0, _x1)]] [[and(active(_x0), _x1)]] = 2 + x0 + 2x1 >= 2 + x0 + 2x1 = [[and(_x0, _x1)]] [[and(_x0, active(_x1))]] = 2 + x0 + 2x1 >= 2 + x0 + 2x1 = [[and(_x0, _x1)]] [[isList(mark(_x0))]] = 2x0 >= x0 = [[isList(_x0)]] [[isList(active(_x0))]] = x0 >= x0 = [[isList(_x0)]] [[isNeList(mark(_x0))]] = 4x0 >= 2x0 = [[isNeList(_x0)]] [[isNeList(active(_x0))]] = 2x0 >= 2x0 = [[isNeList(_x0)]] [[isQid(mark(_x0))]] = 2x0 >= x0 = [[isQid(_x0)]] [[isQid(active(_x0))]] = x0 >= x0 = [[isQid(_x0)]] [[isNePal(mark(_x0))]] = 4x0 >= 2x0 = [[isNePal(_x0)]] [[isNePal(active(_x0))]] = 2x0 >= 2x0 = [[isNePal(_x0)]] [[isPal(mark(_x0))]] = 4x0 >= 2x0 = [[isPal(_x0)]] [[isPal(active(_x0))]] = 2x0 >= 2x0 = [[isPal(_x0)]] We can thus remove the following rules: mark(and(X, Y)) => active(and(mark(X), Y)) 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]): mark(!6220!6220(X, Y)) >? active(!6220!6220(mark(X), mark(Y))) mark(nil) >? active(nil) mark(tt) >? active(tt) mark(isList(X)) >? active(isList(X)) mark(isNeList(X)) >? active(isNeList(X)) mark(isQid(X)) >? active(isQid(X)) mark(isNePal(X)) >? active(isNePal(X)) mark(isPal(X)) >? active(isPal(X)) mark(a) >? active(a) 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) and(mark(X), Y) >? and(X, Y) and(X, mark(Y)) >? and(X, Y) and(active(X), Y) >? and(X, Y) and(X, active(Y)) >? and(X, Y) isList(mark(X)) >? isList(X) isList(active(X)) >? isList(X) isNeList(mark(X)) >? isNeList(X) isNeList(active(X)) >? isNeList(X) isQid(mark(X)) >? isQid(X) isQid(active(X)) >? isQid(X) isNePal(mark(X)) >? isNePal(X) isNePal(active(X)) >? isNePal(X) isPal(mark(X)) >? isPal(X) isPal(active(X)) >? isPal(X) We orient these requirements with a polynomial interpretation in the natural numbers. The following interpretation satisfies the requirements: !6220!6220 = \y0y1.y0 + y1 a = 0 active = \y0.y0 and = \y0y1.y0 + y1 i = 0 isList = \y0.y0 isNeList = \y0.2 + y0 isNePal = \y0.y0 isPal = \y0.y0 isQid = \y0.y0 mark = \y0.2y0 nil = 0 o = 0 tt = 0 u = 0 Using this interpretation, the requirements translate to: [[mark(!6220!6220(_x0, _x1))]] = 2x0 + 2x1 >= 2x0 + 2x1 = [[active(!6220!6220(mark(_x0), mark(_x1)))]] [[mark(nil)]] = 0 >= 0 = [[active(nil)]] [[mark(tt)]] = 0 >= 0 = [[active(tt)]] [[mark(isList(_x0))]] = 2x0 >= x0 = [[active(isList(_x0))]] [[mark(isNeList(_x0))]] = 4 + 2x0 > 2 + x0 = [[active(isNeList(_x0))]] [[mark(isQid(_x0))]] = 2x0 >= x0 = [[active(isQid(_x0))]] [[mark(isNePal(_x0))]] = 2x0 >= x0 = [[active(isNePal(_x0))]] [[mark(isPal(_x0))]] = 2x0 >= x0 = [[active(isPal(_x0))]] [[mark(a)]] = 0 >= 0 = [[active(a)]] [[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 >= 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)]] [[and(mark(_x0), _x1)]] = x1 + 2x0 >= x0 + x1 = [[and(_x0, _x1)]] [[and(_x0, mark(_x1))]] = x0 + 2x1 >= x0 + x1 = [[and(_x0, _x1)]] [[and(active(_x0), _x1)]] = x0 + x1 >= x0 + x1 = [[and(_x0, _x1)]] [[and(_x0, active(_x1))]] = x0 + x1 >= x0 + x1 = [[and(_x0, _x1)]] [[isList(mark(_x0))]] = 2x0 >= x0 = [[isList(_x0)]] [[isList(active(_x0))]] = x0 >= x0 = [[isList(_x0)]] [[isNeList(mark(_x0))]] = 2 + 2x0 >= 2 + x0 = [[isNeList(_x0)]] [[isNeList(active(_x0))]] = 2 + x0 >= 2 + x0 = [[isNeList(_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)]] [[isPal(mark(_x0))]] = 2x0 >= x0 = [[isPal(_x0)]] [[isPal(active(_x0))]] = x0 >= x0 = [[isPal(_x0)]] We can thus remove the following rules: mark(isNeList(X)) => active(isNeList(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(!6220!6220(X, Y)) >? active(!6220!6220(mark(X), mark(Y))) mark(nil) >? active(nil) mark(tt) >? active(tt) mark(isList(X)) >? active(isList(X)) mark(isQid(X)) >? active(isQid(X)) mark(isNePal(X)) >? active(isNePal(X)) mark(isPal(X)) >? active(isPal(X)) mark(a) >? active(a) 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) and(mark(X), Y) >? and(X, Y) and(X, mark(Y)) >? and(X, Y) and(active(X), Y) >? and(X, Y) and(X, active(Y)) >? and(X, Y) isList(mark(X)) >? isList(X) isList(active(X)) >? isList(X) isNeList(mark(X)) >? isNeList(X) isNeList(active(X)) >? isNeList(X) isQid(mark(X)) >? isQid(X) isQid(active(X)) >? isQid(X) isNePal(mark(X)) >? isNePal(X) isNePal(active(X)) >? isNePal(X) isPal(mark(X)) >? isPal(X) isPal(active(X)) >? isPal(X) We orient these requirements with a polynomial interpretation in the natural numbers. The following interpretation satisfies the requirements: !6220!6220 = \y0y1.y0 + y1 a = 3 active = \y0.y0 and = \y0y1.2y0 + 2y1 i = 2 isList = \y0.y0 isNeList = \y0.y0 isNePal = \y0.1 + y0 isPal = \y0.2y0 isQid = \y0.1 + 2y0 mark = \y0.2y0 nil = 0 o = 0 tt = 0 u = 3 Using this interpretation, the requirements translate to: [[mark(!6220!6220(_x0, _x1))]] = 2x0 + 2x1 >= 2x0 + 2x1 = [[active(!6220!6220(mark(_x0), mark(_x1)))]] [[mark(nil)]] = 0 >= 0 = [[active(nil)]] [[mark(tt)]] = 0 >= 0 = [[active(tt)]] [[mark(isList(_x0))]] = 2x0 >= x0 = [[active(isList(_x0))]] [[mark(isQid(_x0))]] = 2 + 4x0 > 1 + 2x0 = [[active(isQid(_x0))]] [[mark(isNePal(_x0))]] = 2 + 2x0 > 1 + x0 = [[active(isNePal(_x0))]] [[mark(isPal(_x0))]] = 4x0 >= 2x0 = [[active(isPal(_x0))]] [[mark(a)]] = 6 > 3 = [[active(a)]] [[mark(i)]] = 4 > 2 = [[active(i)]] [[mark(o)]] = 0 >= 0 = [[active(o)]] [[mark(u)]] = 6 > 3 = [[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)]] [[and(mark(_x0), _x1)]] = 2x1 + 4x0 >= 2x0 + 2x1 = [[and(_x0, _x1)]] [[and(_x0, mark(_x1))]] = 2x0 + 4x1 >= 2x0 + 2x1 = [[and(_x0, _x1)]] [[and(active(_x0), _x1)]] = 2x0 + 2x1 >= 2x0 + 2x1 = [[and(_x0, _x1)]] [[and(_x0, active(_x1))]] = 2x0 + 2x1 >= 2x0 + 2x1 = [[and(_x0, _x1)]] [[isList(mark(_x0))]] = 2x0 >= x0 = [[isList(_x0)]] [[isList(active(_x0))]] = x0 >= x0 = [[isList(_x0)]] [[isNeList(mark(_x0))]] = 2x0 >= x0 = [[isNeList(_x0)]] [[isNeList(active(_x0))]] = x0 >= x0 = [[isNeList(_x0)]] [[isQid(mark(_x0))]] = 1 + 4x0 >= 1 + 2x0 = [[isQid(_x0)]] [[isQid(active(_x0))]] = 1 + 2x0 >= 1 + 2x0 = [[isQid(_x0)]] [[isNePal(mark(_x0))]] = 1 + 2x0 >= 1 + x0 = [[isNePal(_x0)]] [[isNePal(active(_x0))]] = 1 + x0 >= 1 + x0 = [[isNePal(_x0)]] [[isPal(mark(_x0))]] = 4x0 >= 2x0 = [[isPal(_x0)]] [[isPal(active(_x0))]] = 2x0 >= 2x0 = [[isPal(_x0)]] We can thus remove the following rules: mark(isQid(X)) => active(isQid(X)) mark(isNePal(X)) => active(isNePal(X)) mark(a) => active(a) mark(i) => active(i) 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]): mark(!6220!6220(X, Y)) >? active(!6220!6220(mark(X), mark(Y))) mark(nil) >? active(nil) mark(tt) >? active(tt) mark(isList(X)) >? active(isList(X)) mark(isPal(X)) >? active(isPal(X)) mark(o) >? active(o) !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) and(mark(X), Y) >? and(X, Y) and(X, mark(Y)) >? and(X, Y) and(active(X), Y) >? and(X, Y) and(X, active(Y)) >? and(X, Y) isList(mark(X)) >? isList(X) isList(active(X)) >? isList(X) isNeList(mark(X)) >? isNeList(X) isNeList(active(X)) >? isNeList(X) isQid(mark(X)) >? isQid(X) isQid(active(X)) >? isQid(X) isNePal(mark(X)) >? isNePal(X) isNePal(active(X)) >? isNePal(X) isPal(mark(X)) >? isPal(X) isPal(active(X)) >? isPal(X) We orient these requirements with a polynomial interpretation in the natural numbers. The following interpretation satisfies the requirements: !6220!6220 = \y0y1.y0 + y1 active = \y0.y0 and = \y0y1.y0 + 2y1 isList = \y0.y0 isNeList = \y0.y0 isNePal = \y0.y0 isPal = \y0.y0 isQid = \y0.y0 mark = \y0.2y0 nil = 1 o = 0 tt = 0 Using this interpretation, the requirements translate to: [[mark(!6220!6220(_x0, _x1))]] = 2x0 + 2x1 >= 2x0 + 2x1 = [[active(!6220!6220(mark(_x0), mark(_x1)))]] [[mark(nil)]] = 2 > 1 = [[active(nil)]] [[mark(tt)]] = 0 >= 0 = [[active(tt)]] [[mark(isList(_x0))]] = 2x0 >= x0 = [[active(isList(_x0))]] [[mark(isPal(_x0))]] = 2x0 >= x0 = [[active(isPal(_x0))]] [[mark(o)]] = 0 >= 0 = [[active(o)]] [[!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)]] [[and(mark(_x0), _x1)]] = 2x0 + 2x1 >= x0 + 2x1 = [[and(_x0, _x1)]] [[and(_x0, mark(_x1))]] = x0 + 4x1 >= x0 + 2x1 = [[and(_x0, _x1)]] [[and(active(_x0), _x1)]] = x0 + 2x1 >= x0 + 2x1 = [[and(_x0, _x1)]] [[and(_x0, active(_x1))]] = x0 + 2x1 >= x0 + 2x1 = [[and(_x0, _x1)]] [[isList(mark(_x0))]] = 2x0 >= x0 = [[isList(_x0)]] [[isList(active(_x0))]] = x0 >= x0 = [[isList(_x0)]] [[isNeList(mark(_x0))]] = 2x0 >= x0 = [[isNeList(_x0)]] [[isNeList(active(_x0))]] = x0 >= x0 = [[isNeList(_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)]] [[isPal(mark(_x0))]] = 2x0 >= x0 = [[isPal(_x0)]] [[isPal(active(_x0))]] = x0 >= x0 = [[isPal(_x0)]] We can thus remove the following rules: mark(nil) => active(nil) We use rule removal, following [Kop12, Theorem 2.23]. This gives the following requirements (possibly using Theorems 2.25 and 2.26 in [Kop12]): mark(!6220!6220(X, Y)) >? active(!6220!6220(mark(X), mark(Y))) mark(tt) >? active(tt) mark(isList(X)) >? active(isList(X)) mark(isPal(X)) >? active(isPal(X)) mark(o) >? active(o) !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) and(mark(X), Y) >? and(X, Y) and(X, mark(Y)) >? and(X, Y) and(active(X), Y) >? and(X, Y) and(X, active(Y)) >? and(X, Y) isList(mark(X)) >? isList(X) isList(active(X)) >? isList(X) isNeList(mark(X)) >? isNeList(X) isNeList(active(X)) >? isNeList(X) isQid(mark(X)) >? isQid(X) isQid(active(X)) >? isQid(X) isNePal(mark(X)) >? isNePal(X) isNePal(active(X)) >? isNePal(X) isPal(mark(X)) >? isPal(X) isPal(active(X)) >? isPal(X) We orient these requirements with a polynomial interpretation in the natural numbers. The following interpretation satisfies the requirements: !6220!6220 = \y0y1.y0 + 2y1 active = \y0.y0 and = \y0y1.2y0 + 2y1 isList = \y0.2 + 2y0 isNeList = \y0.2y0 isNePal = \y0.y0 isPal = \y0.2y0 isQid = \y0.y0 mark = \y0.2y0 o = 0 tt = 0 Using this interpretation, the requirements translate to: [[mark(!6220!6220(_x0, _x1))]] = 2x0 + 4x1 >= 2x0 + 4x1 = [[active(!6220!6220(mark(_x0), mark(_x1)))]] [[mark(tt)]] = 0 >= 0 = [[active(tt)]] [[mark(isList(_x0))]] = 4 + 4x0 > 2 + 2x0 = [[active(isList(_x0))]] [[mark(isPal(_x0))]] = 4x0 >= 2x0 = [[active(isPal(_x0))]] [[mark(o)]] = 0 >= 0 = [[active(o)]] [[!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)]] [[and(mark(_x0), _x1)]] = 2x1 + 4x0 >= 2x0 + 2x1 = [[and(_x0, _x1)]] [[and(_x0, mark(_x1))]] = 2x0 + 4x1 >= 2x0 + 2x1 = [[and(_x0, _x1)]] [[and(active(_x0), _x1)]] = 2x0 + 2x1 >= 2x0 + 2x1 = [[and(_x0, _x1)]] [[and(_x0, active(_x1))]] = 2x0 + 2x1 >= 2x0 + 2x1 = [[and(_x0, _x1)]] [[isList(mark(_x0))]] = 2 + 4x0 >= 2 + 2x0 = [[isList(_x0)]] [[isList(active(_x0))]] = 2 + 2x0 >= 2 + 2x0 = [[isList(_x0)]] [[isNeList(mark(_x0))]] = 4x0 >= 2x0 = [[isNeList(_x0)]] [[isNeList(active(_x0))]] = 2x0 >= 2x0 = [[isNeList(_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)]] [[isPal(mark(_x0))]] = 4x0 >= 2x0 = [[isPal(_x0)]] [[isPal(active(_x0))]] = 2x0 >= 2x0 = [[isPal(_x0)]] We can thus remove the following rules: mark(isList(X)) => active(isList(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(!6220!6220(X, Y)) >? active(!6220!6220(mark(X), mark(Y))) mark(tt) >? active(tt) mark(isPal(X)) >? active(isPal(X)) mark(o) >? active(o) !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) and(mark(X), Y) >? and(X, Y) and(X, mark(Y)) >? and(X, Y) and(active(X), Y) >? and(X, Y) and(X, active(Y)) >? and(X, Y) isList(mark(X)) >? isList(X) isList(active(X)) >? isList(X) isNeList(mark(X)) >? isNeList(X) isNeList(active(X)) >? isNeList(X) isQid(mark(X)) >? isQid(X) isQid(active(X)) >? isQid(X) isNePal(mark(X)) >? isNePal(X) isNePal(active(X)) >? isNePal(X) isPal(mark(X)) >? isPal(X) isPal(active(X)) >? isPal(X) We orient these requirements with a polynomial interpretation in the natural numbers. The following interpretation satisfies the requirements: !6220!6220 = \y0y1.y0 + y1 active = \y0.y0 and = \y0y1.y0 + 2y1 isList = \y0.2y0 isNeList = \y0.y0 isNePal = \y0.y0 isPal = \y0.2 + 2y0 isQid = \y0.2y0 mark = \y0.2y0 o = 0 tt = 0 Using this interpretation, the requirements translate to: [[mark(!6220!6220(_x0, _x1))]] = 2x0 + 2x1 >= 2x0 + 2x1 = [[active(!6220!6220(mark(_x0), mark(_x1)))]] [[mark(tt)]] = 0 >= 0 = [[active(tt)]] [[mark(isPal(_x0))]] = 4 + 4x0 > 2 + 2x0 = [[active(isPal(_x0))]] [[mark(o)]] = 0 >= 0 = [[active(o)]] [[!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)]] [[and(mark(_x0), _x1)]] = 2x0 + 2x1 >= x0 + 2x1 = [[and(_x0, _x1)]] [[and(_x0, mark(_x1))]] = x0 + 4x1 >= x0 + 2x1 = [[and(_x0, _x1)]] [[and(active(_x0), _x1)]] = x0 + 2x1 >= x0 + 2x1 = [[and(_x0, _x1)]] [[and(_x0, active(_x1))]] = x0 + 2x1 >= x0 + 2x1 = [[and(_x0, _x1)]] [[isList(mark(_x0))]] = 4x0 >= 2x0 = [[isList(_x0)]] [[isList(active(_x0))]] = 2x0 >= 2x0 = [[isList(_x0)]] [[isNeList(mark(_x0))]] = 2x0 >= x0 = [[isNeList(_x0)]] [[isNeList(active(_x0))]] = x0 >= x0 = [[isNeList(_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)]] [[isPal(mark(_x0))]] = 2 + 4x0 >= 2 + 2x0 = [[isPal(_x0)]] [[isPal(active(_x0))]] = 2 + 2x0 >= 2 + 2x0 = [[isPal(_x0)]] We can thus remove the following rules: 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]): mark(!6220!6220(X, Y)) >? active(!6220!6220(mark(X), mark(Y))) mark(tt) >? active(tt) mark(o) >? active(o) !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) and(mark(X), Y) >? and(X, Y) and(X, mark(Y)) >? and(X, Y) and(active(X), Y) >? and(X, Y) and(X, active(Y)) >? and(X, Y) isList(mark(X)) >? isList(X) isList(active(X)) >? isList(X) isNeList(mark(X)) >? isNeList(X) isNeList(active(X)) >? isNeList(X) isQid(mark(X)) >? isQid(X) isQid(active(X)) >? isQid(X) isNePal(mark(X)) >? isNePal(X) isNePal(active(X)) >? isNePal(X) isPal(mark(X)) >? isPal(X) isPal(active(X)) >? isPal(X) We orient these requirements with a polynomial interpretation in the natural numbers. The following interpretation satisfies the requirements: !6220!6220 = \y0y1.2y0 + 2y1 active = \y0.y0 and = \y0y1.2y0 + 2y1 isList = \y0.y0 isNeList = \y0.y0 isNePal = \y0.y0 isPal = \y0.y0 isQid = \y0.y0 mark = \y0.2y0 o = 2 tt = 0 Using this interpretation, the requirements translate to: [[mark(!6220!6220(_x0, _x1))]] = 4x0 + 4x1 >= 4x0 + 4x1 = [[active(!6220!6220(mark(_x0), mark(_x1)))]] [[mark(tt)]] = 0 >= 0 = [[active(tt)]] [[mark(o)]] = 4 > 2 = [[active(o)]] [[!6220!6220(mark(_x0), _x1)]] = 2x1 + 4x0 >= 2x0 + 2x1 = [[!6220!6220(_x0, _x1)]] [[!6220!6220(_x0, mark(_x1))]] = 2x0 + 4x1 >= 2x0 + 2x1 = [[!6220!6220(_x0, _x1)]] [[!6220!6220(active(_x0), _x1)]] = 2x0 + 2x1 >= 2x0 + 2x1 = [[!6220!6220(_x0, _x1)]] [[!6220!6220(_x0, active(_x1))]] = 2x0 + 2x1 >= 2x0 + 2x1 = [[!6220!6220(_x0, _x1)]] [[and(mark(_x0), _x1)]] = 2x1 + 4x0 >= 2x0 + 2x1 = [[and(_x0, _x1)]] [[and(_x0, mark(_x1))]] = 2x0 + 4x1 >= 2x0 + 2x1 = [[and(_x0, _x1)]] [[and(active(_x0), _x1)]] = 2x0 + 2x1 >= 2x0 + 2x1 = [[and(_x0, _x1)]] [[and(_x0, active(_x1))]] = 2x0 + 2x1 >= 2x0 + 2x1 = [[and(_x0, _x1)]] [[isList(mark(_x0))]] = 2x0 >= x0 = [[isList(_x0)]] [[isList(active(_x0))]] = x0 >= x0 = [[isList(_x0)]] [[isNeList(mark(_x0))]] = 2x0 >= x0 = [[isNeList(_x0)]] [[isNeList(active(_x0))]] = x0 >= x0 = [[isNeList(_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)]] [[isPal(mark(_x0))]] = 2x0 >= x0 = [[isPal(_x0)]] [[isPal(active(_x0))]] = x0 >= x0 = [[isPal(_x0)]] We can thus remove the following rules: 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]): mark(!6220!6220(X, Y)) >? active(!6220!6220(mark(X), mark(Y))) mark(tt) >? active(tt) !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) and(mark(X), Y) >? and(X, Y) and(X, mark(Y)) >? and(X, Y) and(active(X), Y) >? and(X, Y) and(X, active(Y)) >? and(X, Y) isList(mark(X)) >? isList(X) isList(active(X)) >? isList(X) isNeList(mark(X)) >? isNeList(X) isNeList(active(X)) >? isNeList(X) isQid(mark(X)) >? isQid(X) isQid(active(X)) >? isQid(X) isNePal(mark(X)) >? isNePal(X) isNePal(active(X)) >? isNePal(X) isPal(mark(X)) >? isPal(X) isPal(active(X)) >? isPal(X) We orient these requirements with a polynomial interpretation in the natural numbers. The following interpretation satisfies the requirements: !6220!6220 = \y0y1.3 + y1 + 2y0 active = \y0.1 + y0 and = \y0y1.y0 + y1 isList = \y0.y0 isNeList = \y0.y0 isNePal = \y0.y0 isPal = \y0.2y0 isQid = \y0.y0 mark = \y0.2y0 tt = 1 Using this interpretation, the requirements translate to: [[mark(!6220!6220(_x0, _x1))]] = 6 + 2x1 + 4x0 > 4 + 2x1 + 4x0 = [[active(!6220!6220(mark(_x0), mark(_x1)))]] [[mark(tt)]] = 2 >= 2 = [[active(tt)]] [[!6220!6220(mark(_x0), _x1)]] = 3 + x1 + 4x0 >= 3 + x1 + 2x0 = [[!6220!6220(_x0, _x1)]] [[!6220!6220(_x0, mark(_x1))]] = 3 + 2x0 + 2x1 >= 3 + x1 + 2x0 = [[!6220!6220(_x0, _x1)]] [[!6220!6220(active(_x0), _x1)]] = 5 + x1 + 2x0 > 3 + x1 + 2x0 = [[!6220!6220(_x0, _x1)]] [[!6220!6220(_x0, active(_x1))]] = 4 + x1 + 2x0 > 3 + x1 + 2x0 = [[!6220!6220(_x0, _x1)]] [[and(mark(_x0), _x1)]] = x1 + 2x0 >= x0 + x1 = [[and(_x0, _x1)]] [[and(_x0, mark(_x1))]] = x0 + 2x1 >= x0 + x1 = [[and(_x0, _x1)]] [[and(active(_x0), _x1)]] = 1 + x0 + x1 > x0 + x1 = [[and(_x0, _x1)]] [[and(_x0, active(_x1))]] = 1 + x0 + x1 > x0 + x1 = [[and(_x0, _x1)]] [[isList(mark(_x0))]] = 2x0 >= x0 = [[isList(_x0)]] [[isList(active(_x0))]] = 1 + x0 > x0 = [[isList(_x0)]] [[isNeList(mark(_x0))]] = 2x0 >= x0 = [[isNeList(_x0)]] [[isNeList(active(_x0))]] = 1 + x0 > x0 = [[isNeList(_x0)]] [[isQid(mark(_x0))]] = 2x0 >= x0 = [[isQid(_x0)]] [[isQid(active(_x0))]] = 1 + x0 > x0 = [[isQid(_x0)]] [[isNePal(mark(_x0))]] = 2x0 >= x0 = [[isNePal(_x0)]] [[isNePal(active(_x0))]] = 1 + x0 > x0 = [[isNePal(_x0)]] [[isPal(mark(_x0))]] = 4x0 >= 2x0 = [[isPal(_x0)]] [[isPal(active(_x0))]] = 2 + 2x0 > 2x0 = [[isPal(_x0)]] We can thus remove the following rules: mark(!6220!6220(X, Y)) => active(!6220!6220(mark(X), mark(Y))) !6220!6220(active(X), Y) => !6220!6220(X, Y) !6220!6220(X, active(Y)) => !6220!6220(X, Y) and(active(X), Y) => and(X, Y) and(X, active(Y)) => and(X, Y) isList(active(X)) => isList(X) isNeList(active(X)) => isNeList(X) isQid(active(X)) => isQid(X) isNePal(active(X)) => isNePal(X) isPal(active(X)) => isPal(X) We use rule removal, following [Kop12, Theorem 2.23]. This gives the following requirements (possibly using Theorems 2.25 and 2.26 in [Kop12]): mark(tt) >? active(tt) !6220!6220(mark(X), Y) >? !6220!6220(X, Y) !6220!6220(X, mark(Y)) >? !6220!6220(X, Y) and(mark(X), Y) >? and(X, Y) and(X, mark(Y)) >? and(X, Y) isList(mark(X)) >? isList(X) isNeList(mark(X)) >? isNeList(X) isQid(mark(X)) >? isQid(X) isNePal(mark(X)) >? isNePal(X) isPal(mark(X)) >? isPal(X) We orient these requirements with a polynomial interpretation in the natural numbers. The following interpretation satisfies the requirements: !6220!6220 = \y0y1.y0 + y1 active = \y0.y0 and = \y0y1.y0 + y1 isList = \y0.y0 isNeList = \y0.y0 isNePal = \y0.y0 isPal = \y0.y0 isQid = \y0.y0 mark = \y0.3 + 3y0 tt = 0 Using this interpretation, the requirements translate to: [[mark(tt)]] = 3 > 0 = [[active(tt)]] [[!6220!6220(mark(_x0), _x1)]] = 3 + x1 + 3x0 > x0 + x1 = [[!6220!6220(_x0, _x1)]] [[!6220!6220(_x0, mark(_x1))]] = 3 + x0 + 3x1 > x0 + x1 = [[!6220!6220(_x0, _x1)]] [[and(mark(_x0), _x1)]] = 3 + x1 + 3x0 > x0 + x1 = [[and(_x0, _x1)]] [[and(_x0, mark(_x1))]] = 3 + x0 + 3x1 > x0 + x1 = [[and(_x0, _x1)]] [[isList(mark(_x0))]] = 3 + 3x0 > x0 = [[isList(_x0)]] [[isNeList(mark(_x0))]] = 3 + 3x0 > x0 = [[isNeList(_x0)]] [[isQid(mark(_x0))]] = 3 + 3x0 > x0 = [[isQid(_x0)]] [[isNePal(mark(_x0))]] = 3 + 3x0 > x0 = [[isNePal(_x0)]] [[isPal(mark(_x0))]] = 3 + 3x0 > x0 = [[isPal(_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) and(mark(X), Y) => and(X, Y) and(X, mark(Y)) => and(X, Y) isList(mark(X)) => isList(X) isNeList(mark(X)) => isNeList(X) isQid(mark(X)) => isQid(X) isNePal(mark(X)) => isNePal(X) isPal(mark(X)) => isPal(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.