/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. 0 : [] --> o active : [o] --> o cons : [o * o] --> o incr : [o] --> o mark : [o] --> o nil : [] --> o oddNs : [] --> o pair : [o * o] --> o pairNs : [] --> o repItems : [o] --> o s : [o] --> o tail : [o] --> o take : [o * o] --> o zip : [o * o] --> o active(pairNs) => mark(cons(0, incr(oddNs))) active(oddNs) => mark(incr(pairNs)) active(incr(cons(X, Y))) => mark(cons(s(X), incr(Y))) active(take(0, X)) => mark(nil) active(take(s(X), cons(Y, Z))) => mark(cons(Y, take(X, Z))) active(zip(nil, X)) => mark(nil) active(zip(X, nil)) => mark(nil) active(zip(cons(X, Y), cons(Z, U))) => mark(cons(pair(X, Z), zip(Y, U))) active(tail(cons(X, Y))) => mark(Y) active(repItems(nil)) => mark(nil) active(repItems(cons(X, Y))) => mark(cons(X, cons(X, repItems(Y)))) mark(pairNs) => active(pairNs) mark(cons(X, Y)) => active(cons(mark(X), Y)) mark(0) => active(0) mark(incr(X)) => active(incr(mark(X))) mark(oddNs) => active(oddNs) mark(s(X)) => active(s(mark(X))) mark(take(X, Y)) => active(take(mark(X), mark(Y))) mark(nil) => active(nil) mark(zip(X, Y)) => active(zip(mark(X), mark(Y))) mark(pair(X, Y)) => active(pair(mark(X), mark(Y))) mark(tail(X)) => active(tail(mark(X))) mark(repItems(X)) => active(repItems(mark(X))) cons(mark(X), Y) => cons(X, Y) cons(X, mark(Y)) => cons(X, Y) cons(active(X), Y) => cons(X, Y) cons(X, active(Y)) => cons(X, Y) incr(mark(X)) => incr(X) incr(active(X)) => incr(X) s(mark(X)) => s(X) s(active(X)) => s(X) take(mark(X), Y) => take(X, Y) take(X, mark(Y)) => take(X, Y) take(active(X), Y) => take(X, Y) take(X, active(Y)) => take(X, Y) zip(mark(X), Y) => zip(X, Y) zip(X, mark(Y)) => zip(X, Y) zip(active(X), Y) => zip(X, Y) zip(X, active(Y)) => zip(X, Y) pair(mark(X), Y) => pair(X, Y) pair(X, mark(Y)) => pair(X, Y) pair(active(X), Y) => pair(X, Y) pair(X, active(Y)) => pair(X, Y) tail(mark(X)) => tail(X) tail(active(X)) => tail(X) repItems(mark(X)) => repItems(X) repItems(active(X)) => repItems(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(pairNs) >? mark(cons(0, incr(oddNs))) active(oddNs) >? mark(incr(pairNs)) active(incr(cons(X, Y))) >? mark(cons(s(X), incr(Y))) active(take(0, X)) >? mark(nil) active(take(s(X), cons(Y, Z))) >? mark(cons(Y, take(X, Z))) active(zip(nil, X)) >? mark(nil) active(zip(X, nil)) >? mark(nil) active(zip(cons(X, Y), cons(Z, U))) >? mark(cons(pair(X, Z), zip(Y, U))) active(tail(cons(X, Y))) >? mark(Y) active(repItems(nil)) >? mark(nil) active(repItems(cons(X, Y))) >? mark(cons(X, cons(X, repItems(Y)))) mark(pairNs) >? active(pairNs) mark(cons(X, Y)) >? active(cons(mark(X), Y)) mark(0) >? active(0) mark(incr(X)) >? active(incr(mark(X))) mark(oddNs) >? active(oddNs) mark(s(X)) >? active(s(mark(X))) mark(take(X, Y)) >? active(take(mark(X), mark(Y))) mark(nil) >? active(nil) mark(zip(X, Y)) >? active(zip(mark(X), mark(Y))) mark(pair(X, Y)) >? active(pair(mark(X), mark(Y))) mark(tail(X)) >? active(tail(mark(X))) mark(repItems(X)) >? active(repItems(mark(X))) cons(mark(X), Y) >? cons(X, Y) cons(X, mark(Y)) >? cons(X, Y) cons(active(X), Y) >? cons(X, Y) cons(X, active(Y)) >? cons(X, Y) incr(mark(X)) >? incr(X) incr(active(X)) >? incr(X) s(mark(X)) >? s(X) s(active(X)) >? s(X) take(mark(X), Y) >? take(X, Y) take(X, mark(Y)) >? take(X, Y) take(active(X), Y) >? take(X, Y) take(X, active(Y)) >? take(X, Y) zip(mark(X), Y) >? zip(X, Y) zip(X, mark(Y)) >? zip(X, Y) zip(active(X), Y) >? zip(X, Y) zip(X, active(Y)) >? zip(X, Y) pair(mark(X), Y) >? pair(X, Y) pair(X, mark(Y)) >? pair(X, Y) pair(active(X), Y) >? pair(X, Y) pair(X, active(Y)) >? pair(X, Y) tail(mark(X)) >? tail(X) tail(active(X)) >? tail(X) repItems(mark(X)) >? repItems(X) repItems(active(X)) >? repItems(X) We orient these requirements with a polynomial interpretation in the natural numbers. The following interpretation satisfies the requirements: 0 = 0 active = \y0.y0 cons = \y0y1.y0 + y1 incr = \y0.2y0 mark = \y0.y0 nil = 1 oddNs = 0 pair = \y0y1.y0 + y1 pairNs = 0 repItems = \y0.2y0 s = \y0.2y0 tail = \y0.y0 take = \y0y1.1 + y1 + 2y0 zip = \y0y1.y0 + y1 Using this interpretation, the requirements translate to: [[active(pairNs)]] = 0 >= 0 = [[mark(cons(0, incr(oddNs)))]] [[active(oddNs)]] = 0 >= 0 = [[mark(incr(pairNs))]] [[active(incr(cons(_x0, _x1)))]] = 2x0 + 2x1 >= 2x0 + 2x1 = [[mark(cons(s(_x0), incr(_x1)))]] [[active(take(0, _x0))]] = 1 + x0 >= 1 = [[mark(nil)]] [[active(take(s(_x0), cons(_x1, _x2)))]] = 1 + x1 + x2 + 4x0 >= 1 + x1 + x2 + 2x0 = [[mark(cons(_x1, take(_x0, _x2)))]] [[active(zip(nil, _x0))]] = 1 + x0 >= 1 = [[mark(nil)]] [[active(zip(_x0, nil))]] = 1 + x0 >= 1 = [[mark(nil)]] [[active(zip(cons(_x0, _x1), cons(_x2, _x3)))]] = x0 + x1 + x2 + x3 >= x0 + x1 + x2 + x3 = [[mark(cons(pair(_x0, _x2), zip(_x1, _x3)))]] [[active(tail(cons(_x0, _x1)))]] = x0 + x1 >= x1 = [[mark(_x1)]] [[active(repItems(nil))]] = 2 > 1 = [[mark(nil)]] [[active(repItems(cons(_x0, _x1)))]] = 2x0 + 2x1 >= 2x0 + 2x1 = [[mark(cons(_x0, cons(_x0, repItems(_x1))))]] [[mark(pairNs)]] = 0 >= 0 = [[active(pairNs)]] [[mark(cons(_x0, _x1))]] = x0 + x1 >= x0 + x1 = [[active(cons(mark(_x0), _x1))]] [[mark(0)]] = 0 >= 0 = [[active(0)]] [[mark(incr(_x0))]] = 2x0 >= 2x0 = [[active(incr(mark(_x0)))]] [[mark(oddNs)]] = 0 >= 0 = [[active(oddNs)]] [[mark(s(_x0))]] = 2x0 >= 2x0 = [[active(s(mark(_x0)))]] [[mark(take(_x0, _x1))]] = 1 + x1 + 2x0 >= 1 + x1 + 2x0 = [[active(take(mark(_x0), mark(_x1)))]] [[mark(nil)]] = 1 >= 1 = [[active(nil)]] [[mark(zip(_x0, _x1))]] = x0 + x1 >= x0 + x1 = [[active(zip(mark(_x0), mark(_x1)))]] [[mark(pair(_x0, _x1))]] = x0 + x1 >= x0 + x1 = [[active(pair(mark(_x0), mark(_x1)))]] [[mark(tail(_x0))]] = x0 >= x0 = [[active(tail(mark(_x0)))]] [[mark(repItems(_x0))]] = 2x0 >= 2x0 = [[active(repItems(mark(_x0)))]] [[cons(mark(_x0), _x1)]] = x0 + x1 >= x0 + x1 = [[cons(_x0, _x1)]] [[cons(_x0, mark(_x1))]] = x0 + x1 >= x0 + x1 = [[cons(_x0, _x1)]] [[cons(active(_x0), _x1)]] = x0 + x1 >= x0 + x1 = [[cons(_x0, _x1)]] [[cons(_x0, active(_x1))]] = x0 + x1 >= x0 + x1 = [[cons(_x0, _x1)]] [[incr(mark(_x0))]] = 2x0 >= 2x0 = [[incr(_x0)]] [[incr(active(_x0))]] = 2x0 >= 2x0 = [[incr(_x0)]] [[s(mark(_x0))]] = 2x0 >= 2x0 = [[s(_x0)]] [[s(active(_x0))]] = 2x0 >= 2x0 = [[s(_x0)]] [[take(mark(_x0), _x1)]] = 1 + x1 + 2x0 >= 1 + x1 + 2x0 = [[take(_x0, _x1)]] [[take(_x0, mark(_x1))]] = 1 + x1 + 2x0 >= 1 + x1 + 2x0 = [[take(_x0, _x1)]] [[take(active(_x0), _x1)]] = 1 + x1 + 2x0 >= 1 + x1 + 2x0 = [[take(_x0, _x1)]] [[take(_x0, active(_x1))]] = 1 + x1 + 2x0 >= 1 + x1 + 2x0 = [[take(_x0, _x1)]] [[zip(mark(_x0), _x1)]] = x0 + x1 >= x0 + x1 = [[zip(_x0, _x1)]] [[zip(_x0, mark(_x1))]] = x0 + x1 >= x0 + x1 = [[zip(_x0, _x1)]] [[zip(active(_x0), _x1)]] = x0 + x1 >= x0 + x1 = [[zip(_x0, _x1)]] [[zip(_x0, active(_x1))]] = x0 + x1 >= x0 + x1 = [[zip(_x0, _x1)]] [[pair(mark(_x0), _x1)]] = x0 + x1 >= x0 + x1 = [[pair(_x0, _x1)]] [[pair(_x0, mark(_x1))]] = x0 + x1 >= x0 + x1 = [[pair(_x0, _x1)]] [[pair(active(_x0), _x1)]] = x0 + x1 >= x0 + x1 = [[pair(_x0, _x1)]] [[pair(_x0, active(_x1))]] = x0 + x1 >= x0 + x1 = [[pair(_x0, _x1)]] [[tail(mark(_x0))]] = x0 >= x0 = [[tail(_x0)]] [[tail(active(_x0))]] = x0 >= x0 = [[tail(_x0)]] [[repItems(mark(_x0))]] = 2x0 >= 2x0 = [[repItems(_x0)]] [[repItems(active(_x0))]] = 2x0 >= 2x0 = [[repItems(_x0)]] We can thus remove the following rules: active(repItems(nil)) => mark(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]): active(pairNs) >? mark(cons(0, incr(oddNs))) active(oddNs) >? mark(incr(pairNs)) active(incr(cons(X, Y))) >? mark(cons(s(X), incr(Y))) active(take(0, X)) >? mark(nil) active(take(s(X), cons(Y, Z))) >? mark(cons(Y, take(X, Z))) active(zip(nil, X)) >? mark(nil) active(zip(X, nil)) >? mark(nil) active(zip(cons(X, Y), cons(Z, U))) >? mark(cons(pair(X, Z), zip(Y, U))) active(tail(cons(X, Y))) >? mark(Y) active(repItems(cons(X, Y))) >? mark(cons(X, cons(X, repItems(Y)))) mark(pairNs) >? active(pairNs) mark(cons(X, Y)) >? active(cons(mark(X), Y)) mark(0) >? active(0) mark(incr(X)) >? active(incr(mark(X))) mark(oddNs) >? active(oddNs) mark(s(X)) >? active(s(mark(X))) mark(take(X, Y)) >? active(take(mark(X), mark(Y))) mark(nil) >? active(nil) mark(zip(X, Y)) >? active(zip(mark(X), mark(Y))) mark(pair(X, Y)) >? active(pair(mark(X), mark(Y))) mark(tail(X)) >? active(tail(mark(X))) mark(repItems(X)) >? active(repItems(mark(X))) cons(mark(X), Y) >? cons(X, Y) cons(X, mark(Y)) >? cons(X, Y) cons(active(X), Y) >? cons(X, Y) cons(X, active(Y)) >? cons(X, Y) incr(mark(X)) >? incr(X) incr(active(X)) >? incr(X) s(mark(X)) >? s(X) s(active(X)) >? s(X) take(mark(X), Y) >? take(X, Y) take(X, mark(Y)) >? take(X, Y) take(active(X), Y) >? take(X, Y) take(X, active(Y)) >? take(X, Y) zip(mark(X), Y) >? zip(X, Y) zip(X, mark(Y)) >? zip(X, Y) zip(active(X), Y) >? zip(X, Y) zip(X, active(Y)) >? zip(X, Y) pair(mark(X), Y) >? pair(X, Y) pair(X, mark(Y)) >? pair(X, Y) pair(active(X), Y) >? pair(X, Y) pair(X, active(Y)) >? pair(X, Y) tail(mark(X)) >? tail(X) tail(active(X)) >? tail(X) repItems(mark(X)) >? repItems(X) repItems(active(X)) >? repItems(X) We orient these requirements with a polynomial interpretation in the natural numbers. The following interpretation satisfies the requirements: 0 = 0 active = \y0.y0 cons = \y0y1.y0 + y1 incr = \y0.2y0 mark = \y0.y0 nil = 0 oddNs = 0 pair = \y0y1.y0 + y1 pairNs = 0 repItems = \y0.2y0 s = \y0.y0 tail = \y0.2 + 2y0 take = \y0y1.2y0 + 2y1 zip = \y0y1.y0 + 2y1 Using this interpretation, the requirements translate to: [[active(pairNs)]] = 0 >= 0 = [[mark(cons(0, incr(oddNs)))]] [[active(oddNs)]] = 0 >= 0 = [[mark(incr(pairNs))]] [[active(incr(cons(_x0, _x1)))]] = 2x0 + 2x1 >= x0 + 2x1 = [[mark(cons(s(_x0), incr(_x1)))]] [[active(take(0, _x0))]] = 2x0 >= 0 = [[mark(nil)]] [[active(take(s(_x0), cons(_x1, _x2)))]] = 2x0 + 2x1 + 2x2 >= x1 + 2x0 + 2x2 = [[mark(cons(_x1, take(_x0, _x2)))]] [[active(zip(nil, _x0))]] = 2x0 >= 0 = [[mark(nil)]] [[active(zip(_x0, nil))]] = x0 >= 0 = [[mark(nil)]] [[active(zip(cons(_x0, _x1), cons(_x2, _x3)))]] = x0 + x1 + 2x2 + 2x3 >= x0 + x1 + x2 + 2x3 = [[mark(cons(pair(_x0, _x2), zip(_x1, _x3)))]] [[active(tail(cons(_x0, _x1)))]] = 2 + 2x0 + 2x1 > x1 = [[mark(_x1)]] [[active(repItems(cons(_x0, _x1)))]] = 2x0 + 2x1 >= 2x0 + 2x1 = [[mark(cons(_x0, cons(_x0, repItems(_x1))))]] [[mark(pairNs)]] = 0 >= 0 = [[active(pairNs)]] [[mark(cons(_x0, _x1))]] = x0 + x1 >= x0 + x1 = [[active(cons(mark(_x0), _x1))]] [[mark(0)]] = 0 >= 0 = [[active(0)]] [[mark(incr(_x0))]] = 2x0 >= 2x0 = [[active(incr(mark(_x0)))]] [[mark(oddNs)]] = 0 >= 0 = [[active(oddNs)]] [[mark(s(_x0))]] = x0 >= x0 = [[active(s(mark(_x0)))]] [[mark(take(_x0, _x1))]] = 2x0 + 2x1 >= 2x0 + 2x1 = [[active(take(mark(_x0), mark(_x1)))]] [[mark(nil)]] = 0 >= 0 = [[active(nil)]] [[mark(zip(_x0, _x1))]] = x0 + 2x1 >= x0 + 2x1 = [[active(zip(mark(_x0), mark(_x1)))]] [[mark(pair(_x0, _x1))]] = x0 + x1 >= x0 + x1 = [[active(pair(mark(_x0), mark(_x1)))]] [[mark(tail(_x0))]] = 2 + 2x0 >= 2 + 2x0 = [[active(tail(mark(_x0)))]] [[mark(repItems(_x0))]] = 2x0 >= 2x0 = [[active(repItems(mark(_x0)))]] [[cons(mark(_x0), _x1)]] = x0 + x1 >= x0 + x1 = [[cons(_x0, _x1)]] [[cons(_x0, mark(_x1))]] = x0 + x1 >= x0 + x1 = [[cons(_x0, _x1)]] [[cons(active(_x0), _x1)]] = x0 + x1 >= x0 + x1 = [[cons(_x0, _x1)]] [[cons(_x0, active(_x1))]] = x0 + x1 >= x0 + x1 = [[cons(_x0, _x1)]] [[incr(mark(_x0))]] = 2x0 >= 2x0 = [[incr(_x0)]] [[incr(active(_x0))]] = 2x0 >= 2x0 = [[incr(_x0)]] [[s(mark(_x0))]] = x0 >= x0 = [[s(_x0)]] [[s(active(_x0))]] = x0 >= x0 = [[s(_x0)]] [[take(mark(_x0), _x1)]] = 2x0 + 2x1 >= 2x0 + 2x1 = [[take(_x0, _x1)]] [[take(_x0, mark(_x1))]] = 2x0 + 2x1 >= 2x0 + 2x1 = [[take(_x0, _x1)]] [[take(active(_x0), _x1)]] = 2x0 + 2x1 >= 2x0 + 2x1 = [[take(_x0, _x1)]] [[take(_x0, active(_x1))]] = 2x0 + 2x1 >= 2x0 + 2x1 = [[take(_x0, _x1)]] [[zip(mark(_x0), _x1)]] = x0 + 2x1 >= x0 + 2x1 = [[zip(_x0, _x1)]] [[zip(_x0, mark(_x1))]] = x0 + 2x1 >= x0 + 2x1 = [[zip(_x0, _x1)]] [[zip(active(_x0), _x1)]] = x0 + 2x1 >= x0 + 2x1 = [[zip(_x0, _x1)]] [[zip(_x0, active(_x1))]] = x0 + 2x1 >= x0 + 2x1 = [[zip(_x0, _x1)]] [[pair(mark(_x0), _x1)]] = x0 + x1 >= x0 + x1 = [[pair(_x0, _x1)]] [[pair(_x0, mark(_x1))]] = x0 + x1 >= x0 + x1 = [[pair(_x0, _x1)]] [[pair(active(_x0), _x1)]] = x0 + x1 >= x0 + x1 = [[pair(_x0, _x1)]] [[pair(_x0, active(_x1))]] = x0 + x1 >= x0 + x1 = [[pair(_x0, _x1)]] [[tail(mark(_x0))]] = 2 + 2x0 >= 2 + 2x0 = [[tail(_x0)]] [[tail(active(_x0))]] = 2 + 2x0 >= 2 + 2x0 = [[tail(_x0)]] [[repItems(mark(_x0))]] = 2x0 >= 2x0 = [[repItems(_x0)]] [[repItems(active(_x0))]] = 2x0 >= 2x0 = [[repItems(_x0)]] We can thus remove the following rules: active(tail(cons(X, Y))) => mark(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(pairNs) >? mark(cons(0, incr(oddNs))) active(oddNs) >? mark(incr(pairNs)) active(incr(cons(X, Y))) >? mark(cons(s(X), incr(Y))) active(take(0, X)) >? mark(nil) active(take(s(X), cons(Y, Z))) >? mark(cons(Y, take(X, Z))) active(zip(nil, X)) >? mark(nil) active(zip(X, nil)) >? mark(nil) active(zip(cons(X, Y), cons(Z, U))) >? mark(cons(pair(X, Z), zip(Y, U))) active(repItems(cons(X, Y))) >? mark(cons(X, cons(X, repItems(Y)))) mark(pairNs) >? active(pairNs) mark(cons(X, Y)) >? active(cons(mark(X), Y)) mark(0) >? active(0) mark(incr(X)) >? active(incr(mark(X))) mark(oddNs) >? active(oddNs) mark(s(X)) >? active(s(mark(X))) mark(take(X, Y)) >? active(take(mark(X), mark(Y))) mark(nil) >? active(nil) mark(zip(X, Y)) >? active(zip(mark(X), mark(Y))) mark(pair(X, Y)) >? active(pair(mark(X), mark(Y))) mark(tail(X)) >? active(tail(mark(X))) mark(repItems(X)) >? active(repItems(mark(X))) cons(mark(X), Y) >? cons(X, Y) cons(X, mark(Y)) >? cons(X, Y) cons(active(X), Y) >? cons(X, Y) cons(X, active(Y)) >? cons(X, Y) incr(mark(X)) >? incr(X) incr(active(X)) >? incr(X) s(mark(X)) >? s(X) s(active(X)) >? s(X) take(mark(X), Y) >? take(X, Y) take(X, mark(Y)) >? take(X, Y) take(active(X), Y) >? take(X, Y) take(X, active(Y)) >? take(X, Y) zip(mark(X), Y) >? zip(X, Y) zip(X, mark(Y)) >? zip(X, Y) zip(active(X), Y) >? zip(X, Y) zip(X, active(Y)) >? zip(X, Y) pair(mark(X), Y) >? pair(X, Y) pair(X, mark(Y)) >? pair(X, Y) pair(active(X), Y) >? pair(X, Y) pair(X, active(Y)) >? pair(X, Y) tail(mark(X)) >? tail(X) tail(active(X)) >? tail(X) repItems(mark(X)) >? repItems(X) repItems(active(X)) >? repItems(X) We orient these requirements with a polynomial interpretation in the natural numbers. The following interpretation satisfies the requirements: 0 = 0 active = \y0.y0 cons = \y0y1.y1 + 2y0 incr = \y0.y0 mark = \y0.y0 nil = 0 oddNs = 0 pair = \y0y1.y0 + y1 pairNs = 0 repItems = \y0.2y0 s = \y0.y0 tail = \y0.2y0 take = \y0y1.2y0 + 2y1 zip = \y0y1.1 + y0 + 2y1 Using this interpretation, the requirements translate to: [[active(pairNs)]] = 0 >= 0 = [[mark(cons(0, incr(oddNs)))]] [[active(oddNs)]] = 0 >= 0 = [[mark(incr(pairNs))]] [[active(incr(cons(_x0, _x1)))]] = x1 + 2x0 >= x1 + 2x0 = [[mark(cons(s(_x0), incr(_x1)))]] [[active(take(0, _x0))]] = 2x0 >= 0 = [[mark(nil)]] [[active(take(s(_x0), cons(_x1, _x2)))]] = 2x0 + 2x2 + 4x1 >= 2x0 + 2x1 + 2x2 = [[mark(cons(_x1, take(_x0, _x2)))]] [[active(zip(nil, _x0))]] = 1 + 2x0 > 0 = [[mark(nil)]] [[active(zip(_x0, nil))]] = 1 + x0 > 0 = [[mark(nil)]] [[active(zip(cons(_x0, _x1), cons(_x2, _x3)))]] = 1 + x1 + 2x0 + 2x3 + 4x2 >= 1 + x1 + 2x0 + 2x2 + 2x3 = [[mark(cons(pair(_x0, _x2), zip(_x1, _x3)))]] [[active(repItems(cons(_x0, _x1)))]] = 2x1 + 4x0 >= 2x1 + 4x0 = [[mark(cons(_x0, cons(_x0, repItems(_x1))))]] [[mark(pairNs)]] = 0 >= 0 = [[active(pairNs)]] [[mark(cons(_x0, _x1))]] = x1 + 2x0 >= x1 + 2x0 = [[active(cons(mark(_x0), _x1))]] [[mark(0)]] = 0 >= 0 = [[active(0)]] [[mark(incr(_x0))]] = x0 >= x0 = [[active(incr(mark(_x0)))]] [[mark(oddNs)]] = 0 >= 0 = [[active(oddNs)]] [[mark(s(_x0))]] = x0 >= x0 = [[active(s(mark(_x0)))]] [[mark(take(_x0, _x1))]] = 2x0 + 2x1 >= 2x0 + 2x1 = [[active(take(mark(_x0), mark(_x1)))]] [[mark(nil)]] = 0 >= 0 = [[active(nil)]] [[mark(zip(_x0, _x1))]] = 1 + x0 + 2x1 >= 1 + x0 + 2x1 = [[active(zip(mark(_x0), mark(_x1)))]] [[mark(pair(_x0, _x1))]] = x0 + x1 >= x0 + x1 = [[active(pair(mark(_x0), mark(_x1)))]] [[mark(tail(_x0))]] = 2x0 >= 2x0 = [[active(tail(mark(_x0)))]] [[mark(repItems(_x0))]] = 2x0 >= 2x0 = [[active(repItems(mark(_x0)))]] [[cons(mark(_x0), _x1)]] = x1 + 2x0 >= x1 + 2x0 = [[cons(_x0, _x1)]] [[cons(_x0, mark(_x1))]] = x1 + 2x0 >= x1 + 2x0 = [[cons(_x0, _x1)]] [[cons(active(_x0), _x1)]] = x1 + 2x0 >= x1 + 2x0 = [[cons(_x0, _x1)]] [[cons(_x0, active(_x1))]] = x1 + 2x0 >= x1 + 2x0 = [[cons(_x0, _x1)]] [[incr(mark(_x0))]] = x0 >= x0 = [[incr(_x0)]] [[incr(active(_x0))]] = x0 >= x0 = [[incr(_x0)]] [[s(mark(_x0))]] = x0 >= x0 = [[s(_x0)]] [[s(active(_x0))]] = x0 >= x0 = [[s(_x0)]] [[take(mark(_x0), _x1)]] = 2x0 + 2x1 >= 2x0 + 2x1 = [[take(_x0, _x1)]] [[take(_x0, mark(_x1))]] = 2x0 + 2x1 >= 2x0 + 2x1 = [[take(_x0, _x1)]] [[take(active(_x0), _x1)]] = 2x0 + 2x1 >= 2x0 + 2x1 = [[take(_x0, _x1)]] [[take(_x0, active(_x1))]] = 2x0 + 2x1 >= 2x0 + 2x1 = [[take(_x0, _x1)]] [[zip(mark(_x0), _x1)]] = 1 + x0 + 2x1 >= 1 + x0 + 2x1 = [[zip(_x0, _x1)]] [[zip(_x0, mark(_x1))]] = 1 + x0 + 2x1 >= 1 + x0 + 2x1 = [[zip(_x0, _x1)]] [[zip(active(_x0), _x1)]] = 1 + x0 + 2x1 >= 1 + x0 + 2x1 = [[zip(_x0, _x1)]] [[zip(_x0, active(_x1))]] = 1 + x0 + 2x1 >= 1 + x0 + 2x1 = [[zip(_x0, _x1)]] [[pair(mark(_x0), _x1)]] = x0 + x1 >= x0 + x1 = [[pair(_x0, _x1)]] [[pair(_x0, mark(_x1))]] = x0 + x1 >= x0 + x1 = [[pair(_x0, _x1)]] [[pair(active(_x0), _x1)]] = x0 + x1 >= x0 + x1 = [[pair(_x0, _x1)]] [[pair(_x0, active(_x1))]] = x0 + x1 >= x0 + x1 = [[pair(_x0, _x1)]] [[tail(mark(_x0))]] = 2x0 >= 2x0 = [[tail(_x0)]] [[tail(active(_x0))]] = 2x0 >= 2x0 = [[tail(_x0)]] [[repItems(mark(_x0))]] = 2x0 >= 2x0 = [[repItems(_x0)]] [[repItems(active(_x0))]] = 2x0 >= 2x0 = [[repItems(_x0)]] We can thus remove the following rules: active(zip(nil, X)) => mark(nil) active(zip(X, nil)) => mark(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]): active(pairNs) >? mark(cons(0, incr(oddNs))) active(oddNs) >? mark(incr(pairNs)) active(incr(cons(X, Y))) >? mark(cons(s(X), incr(Y))) active(take(0, X)) >? mark(nil) active(take(s(X), cons(Y, Z))) >? mark(cons(Y, take(X, Z))) active(zip(cons(X, Y), cons(Z, U))) >? mark(cons(pair(X, Z), zip(Y, U))) active(repItems(cons(X, Y))) >? mark(cons(X, cons(X, repItems(Y)))) mark(pairNs) >? active(pairNs) mark(cons(X, Y)) >? active(cons(mark(X), Y)) mark(0) >? active(0) mark(incr(X)) >? active(incr(mark(X))) mark(oddNs) >? active(oddNs) mark(s(X)) >? active(s(mark(X))) mark(take(X, Y)) >? active(take(mark(X), mark(Y))) mark(nil) >? active(nil) mark(zip(X, Y)) >? active(zip(mark(X), mark(Y))) mark(pair(X, Y)) >? active(pair(mark(X), mark(Y))) mark(tail(X)) >? active(tail(mark(X))) mark(repItems(X)) >? active(repItems(mark(X))) cons(mark(X), Y) >? cons(X, Y) cons(X, mark(Y)) >? cons(X, Y) cons(active(X), Y) >? cons(X, Y) cons(X, active(Y)) >? cons(X, Y) incr(mark(X)) >? incr(X) incr(active(X)) >? incr(X) s(mark(X)) >? s(X) s(active(X)) >? s(X) take(mark(X), Y) >? take(X, Y) take(X, mark(Y)) >? take(X, Y) take(active(X), Y) >? take(X, Y) take(X, active(Y)) >? take(X, Y) zip(mark(X), Y) >? zip(X, Y) zip(X, mark(Y)) >? zip(X, Y) zip(active(X), Y) >? zip(X, Y) zip(X, active(Y)) >? zip(X, Y) pair(mark(X), Y) >? pair(X, Y) pair(X, mark(Y)) >? pair(X, Y) pair(active(X), Y) >? pair(X, Y) pair(X, active(Y)) >? pair(X, Y) tail(mark(X)) >? tail(X) tail(active(X)) >? tail(X) repItems(mark(X)) >? repItems(X) repItems(active(X)) >? repItems(X) We orient these requirements with a polynomial interpretation in the natural numbers. The following interpretation satisfies the requirements: 0 = 0 active = \y0.y0 cons = \y0y1.y0 + y1 incr = \y0.y0 mark = \y0.y0 nil = 0 oddNs = 1 pair = \y0y1.y0 + y1 pairNs = 1 repItems = \y0.2y0 s = \y0.y0 tail = \y0.1 + y0 take = \y0y1.1 + y0 + 2y1 zip = \y0y1.y1 + 2y0 Using this interpretation, the requirements translate to: [[active(pairNs)]] = 1 >= 1 = [[mark(cons(0, incr(oddNs)))]] [[active(oddNs)]] = 1 >= 1 = [[mark(incr(pairNs))]] [[active(incr(cons(_x0, _x1)))]] = x0 + x1 >= x0 + x1 = [[mark(cons(s(_x0), incr(_x1)))]] [[active(take(0, _x0))]] = 1 + 2x0 > 0 = [[mark(nil)]] [[active(take(s(_x0), cons(_x1, _x2)))]] = 1 + x0 + 2x1 + 2x2 >= 1 + x0 + x1 + 2x2 = [[mark(cons(_x1, take(_x0, _x2)))]] [[active(zip(cons(_x0, _x1), cons(_x2, _x3)))]] = x2 + x3 + 2x0 + 2x1 >= x0 + x2 + x3 + 2x1 = [[mark(cons(pair(_x0, _x2), zip(_x1, _x3)))]] [[active(repItems(cons(_x0, _x1)))]] = 2x0 + 2x1 >= 2x0 + 2x1 = [[mark(cons(_x0, cons(_x0, repItems(_x1))))]] [[mark(pairNs)]] = 1 >= 1 = [[active(pairNs)]] [[mark(cons(_x0, _x1))]] = x0 + x1 >= x0 + x1 = [[active(cons(mark(_x0), _x1))]] [[mark(0)]] = 0 >= 0 = [[active(0)]] [[mark(incr(_x0))]] = x0 >= x0 = [[active(incr(mark(_x0)))]] [[mark(oddNs)]] = 1 >= 1 = [[active(oddNs)]] [[mark(s(_x0))]] = x0 >= x0 = [[active(s(mark(_x0)))]] [[mark(take(_x0, _x1))]] = 1 + x0 + 2x1 >= 1 + x0 + 2x1 = [[active(take(mark(_x0), mark(_x1)))]] [[mark(nil)]] = 0 >= 0 = [[active(nil)]] [[mark(zip(_x0, _x1))]] = x1 + 2x0 >= x1 + 2x0 = [[active(zip(mark(_x0), mark(_x1)))]] [[mark(pair(_x0, _x1))]] = x0 + x1 >= x0 + x1 = [[active(pair(mark(_x0), mark(_x1)))]] [[mark(tail(_x0))]] = 1 + x0 >= 1 + x0 = [[active(tail(mark(_x0)))]] [[mark(repItems(_x0))]] = 2x0 >= 2x0 = [[active(repItems(mark(_x0)))]] [[cons(mark(_x0), _x1)]] = x0 + x1 >= x0 + x1 = [[cons(_x0, _x1)]] [[cons(_x0, mark(_x1))]] = x0 + x1 >= x0 + x1 = [[cons(_x0, _x1)]] [[cons(active(_x0), _x1)]] = x0 + x1 >= x0 + x1 = [[cons(_x0, _x1)]] [[cons(_x0, active(_x1))]] = x0 + x1 >= x0 + x1 = [[cons(_x0, _x1)]] [[incr(mark(_x0))]] = x0 >= x0 = [[incr(_x0)]] [[incr(active(_x0))]] = x0 >= x0 = [[incr(_x0)]] [[s(mark(_x0))]] = x0 >= x0 = [[s(_x0)]] [[s(active(_x0))]] = x0 >= x0 = [[s(_x0)]] [[take(mark(_x0), _x1)]] = 1 + x0 + 2x1 >= 1 + x0 + 2x1 = [[take(_x0, _x1)]] [[take(_x0, mark(_x1))]] = 1 + x0 + 2x1 >= 1 + x0 + 2x1 = [[take(_x0, _x1)]] [[take(active(_x0), _x1)]] = 1 + x0 + 2x1 >= 1 + x0 + 2x1 = [[take(_x0, _x1)]] [[take(_x0, active(_x1))]] = 1 + x0 + 2x1 >= 1 + x0 + 2x1 = [[take(_x0, _x1)]] [[zip(mark(_x0), _x1)]] = x1 + 2x0 >= x1 + 2x0 = [[zip(_x0, _x1)]] [[zip(_x0, mark(_x1))]] = x1 + 2x0 >= x1 + 2x0 = [[zip(_x0, _x1)]] [[zip(active(_x0), _x1)]] = x1 + 2x0 >= x1 + 2x0 = [[zip(_x0, _x1)]] [[zip(_x0, active(_x1))]] = x1 + 2x0 >= x1 + 2x0 = [[zip(_x0, _x1)]] [[pair(mark(_x0), _x1)]] = x0 + x1 >= x0 + x1 = [[pair(_x0, _x1)]] [[pair(_x0, mark(_x1))]] = x0 + x1 >= x0 + x1 = [[pair(_x0, _x1)]] [[pair(active(_x0), _x1)]] = x0 + x1 >= x0 + x1 = [[pair(_x0, _x1)]] [[pair(_x0, active(_x1))]] = x0 + x1 >= x0 + x1 = [[pair(_x0, _x1)]] [[tail(mark(_x0))]] = 1 + x0 >= 1 + x0 = [[tail(_x0)]] [[tail(active(_x0))]] = 1 + x0 >= 1 + x0 = [[tail(_x0)]] [[repItems(mark(_x0))]] = 2x0 >= 2x0 = [[repItems(_x0)]] [[repItems(active(_x0))]] = 2x0 >= 2x0 = [[repItems(_x0)]] We can thus remove the following rules: active(take(0, X)) => mark(nil) We use the dependency pair framework as described in [Kop12, Ch. 6/7], with static dependency pairs (see [KusIsoSakBla09] and the adaptation for AFSMs in [Kop12, Ch. 7.8]). We thus obtain the following dependency pair problem (P_0, R_0, minimal, formative): Dependency Pairs P_0: 0] active#(pairNs) =#> mark#(cons(0, incr(oddNs))) 1] active#(pairNs) =#> cons#(0, incr(oddNs)) 2] active#(pairNs) =#> incr#(oddNs) 3] active#(oddNs) =#> mark#(incr(pairNs)) 4] active#(oddNs) =#> incr#(pairNs) 5] active#(incr(cons(X, Y))) =#> mark#(cons(s(X), incr(Y))) 6] active#(incr(cons(X, Y))) =#> cons#(s(X), incr(Y)) 7] active#(incr(cons(X, Y))) =#> s#(X) 8] active#(incr(cons(X, Y))) =#> incr#(Y) 9] active#(take(s(X), cons(Y, Z))) =#> mark#(cons(Y, take(X, Z))) 10] active#(take(s(X), cons(Y, Z))) =#> cons#(Y, take(X, Z)) 11] active#(take(s(X), cons(Y, Z))) =#> take#(X, Z) 12] active#(zip(cons(X, Y), cons(Z, U))) =#> mark#(cons(pair(X, Z), zip(Y, U))) 13] active#(zip(cons(X, Y), cons(Z, U))) =#> cons#(pair(X, Z), zip(Y, U)) 14] active#(zip(cons(X, Y), cons(Z, U))) =#> pair#(X, Z) 15] active#(zip(cons(X, Y), cons(Z, U))) =#> zip#(Y, U) 16] active#(repItems(cons(X, Y))) =#> mark#(cons(X, cons(X, repItems(Y)))) 17] active#(repItems(cons(X, Y))) =#> cons#(X, cons(X, repItems(Y))) 18] active#(repItems(cons(X, Y))) =#> cons#(X, repItems(Y)) 19] active#(repItems(cons(X, Y))) =#> repItems#(Y) 20] mark#(pairNs) =#> active#(pairNs) 21] mark#(cons(X, Y)) =#> active#(cons(mark(X), Y)) 22] mark#(cons(X, Y)) =#> cons#(mark(X), Y) 23] mark#(cons(X, Y)) =#> mark#(X) 24] mark#(0) =#> active#(0) 25] mark#(incr(X)) =#> active#(incr(mark(X))) 26] mark#(incr(X)) =#> incr#(mark(X)) 27] mark#(incr(X)) =#> mark#(X) 28] mark#(oddNs) =#> active#(oddNs) 29] mark#(s(X)) =#> active#(s(mark(X))) 30] mark#(s(X)) =#> s#(mark(X)) 31] mark#(s(X)) =#> mark#(X) 32] mark#(take(X, Y)) =#> active#(take(mark(X), mark(Y))) 33] mark#(take(X, Y)) =#> take#(mark(X), mark(Y)) 34] mark#(take(X, Y)) =#> mark#(X) 35] mark#(take(X, Y)) =#> mark#(Y) 36] mark#(nil) =#> active#(nil) 37] mark#(zip(X, Y)) =#> active#(zip(mark(X), mark(Y))) 38] mark#(zip(X, Y)) =#> zip#(mark(X), mark(Y)) 39] mark#(zip(X, Y)) =#> mark#(X) 40] mark#(zip(X, Y)) =#> mark#(Y) 41] mark#(pair(X, Y)) =#> active#(pair(mark(X), mark(Y))) 42] mark#(pair(X, Y)) =#> pair#(mark(X), mark(Y)) 43] mark#(pair(X, Y)) =#> mark#(X) 44] mark#(pair(X, Y)) =#> mark#(Y) 45] mark#(tail(X)) =#> active#(tail(mark(X))) 46] mark#(tail(X)) =#> tail#(mark(X)) 47] mark#(tail(X)) =#> mark#(X) 48] mark#(repItems(X)) =#> active#(repItems(mark(X))) 49] mark#(repItems(X)) =#> repItems#(mark(X)) 50] mark#(repItems(X)) =#> mark#(X) 51] cons#(mark(X), Y) =#> cons#(X, Y) 52] cons#(X, mark(Y)) =#> cons#(X, Y) 53] cons#(active(X), Y) =#> cons#(X, Y) 54] cons#(X, active(Y)) =#> cons#(X, Y) 55] incr#(mark(X)) =#> incr#(X) 56] incr#(active(X)) =#> incr#(X) 57] s#(mark(X)) =#> s#(X) 58] s#(active(X)) =#> s#(X) 59] take#(mark(X), Y) =#> take#(X, Y) 60] take#(X, mark(Y)) =#> take#(X, Y) 61] take#(active(X), Y) =#> take#(X, Y) 62] take#(X, active(Y)) =#> take#(X, Y) 63] zip#(mark(X), Y) =#> zip#(X, Y) 64] zip#(X, mark(Y)) =#> zip#(X, Y) 65] zip#(active(X), Y) =#> zip#(X, Y) 66] zip#(X, active(Y)) =#> zip#(X, Y) 67] pair#(mark(X), Y) =#> pair#(X, Y) 68] pair#(X, mark(Y)) =#> pair#(X, Y) 69] pair#(active(X), Y) =#> pair#(X, Y) 70] pair#(X, active(Y)) =#> pair#(X, Y) 71] tail#(mark(X)) =#> tail#(X) 72] tail#(active(X)) =#> tail#(X) 73] repItems#(mark(X)) =#> repItems#(X) 74] repItems#(active(X)) =#> repItems#(X) Rules R_0: active(pairNs) => mark(cons(0, incr(oddNs))) active(oddNs) => mark(incr(pairNs)) active(incr(cons(X, Y))) => mark(cons(s(X), incr(Y))) active(take(s(X), cons(Y, Z))) => mark(cons(Y, take(X, Z))) active(zip(cons(X, Y), cons(Z, U))) => mark(cons(pair(X, Z), zip(Y, U))) active(repItems(cons(X, Y))) => mark(cons(X, cons(X, repItems(Y)))) mark(pairNs) => active(pairNs) mark(cons(X, Y)) => active(cons(mark(X), Y)) mark(0) => active(0) mark(incr(X)) => active(incr(mark(X))) mark(oddNs) => active(oddNs) mark(s(X)) => active(s(mark(X))) mark(take(X, Y)) => active(take(mark(X), mark(Y))) mark(nil) => active(nil) mark(zip(X, Y)) => active(zip(mark(X), mark(Y))) mark(pair(X, Y)) => active(pair(mark(X), mark(Y))) mark(tail(X)) => active(tail(mark(X))) mark(repItems(X)) => active(repItems(mark(X))) cons(mark(X), Y) => cons(X, Y) cons(X, mark(Y)) => cons(X, Y) cons(active(X), Y) => cons(X, Y) cons(X, active(Y)) => cons(X, Y) incr(mark(X)) => incr(X) incr(active(X)) => incr(X) s(mark(X)) => s(X) s(active(X)) => s(X) take(mark(X), Y) => take(X, Y) take(X, mark(Y)) => take(X, Y) take(active(X), Y) => take(X, Y) take(X, active(Y)) => take(X, Y) zip(mark(X), Y) => zip(X, Y) zip(X, mark(Y)) => zip(X, Y) zip(active(X), Y) => zip(X, Y) zip(X, active(Y)) => zip(X, Y) pair(mark(X), Y) => pair(X, Y) pair(X, mark(Y)) => pair(X, Y) pair(active(X), Y) => pair(X, Y) pair(X, active(Y)) => pair(X, Y) tail(mark(X)) => tail(X) tail(active(X)) => tail(X) repItems(mark(X)) => repItems(X) repItems(active(X)) => repItems(X) Thus, the original system is terminating if (P_0, R_0, minimal, formative) is finite. We consider the dependency pair problem (P_0, R_0, minimal, formative). We place the elements of P in a dependency graph approximation G (see e.g. [Kop12, Thm. 7.27, 7.29], as follows: * 0 : 21, 22, 23 * 1 : * 2 : * 3 : 25, 26, 27 * 4 : * 5 : 21, 22, 23 * 6 : * 7 : 57, 58 * 8 : 55, 56 * 9 : 21, 22, 23 * 10 : 51, 53 * 11 : 59, 60, 61, 62 * 12 : 21, 22, 23 * 13 : * 14 : 67, 68, 69, 70 * 15 : 63, 64, 65, 66 * 16 : 21, 22, 23 * 17 : 51, 53 * 18 : 51, 53 * 19 : 73, 74 * 20 : 0, 1, 2 * 21 : * 22 : 51, 52, 53, 54 * 23 : 20, 21, 22, 23, 24, 25, 26, 27, 28, 29, 30, 31, 32, 33, 34, 35, 36, 37, 38, 39, 40, 41, 42, 43, 44, 45, 46, 47, 48, 49, 50 * 24 : * 25 : 5, 6, 7, 8 * 26 : 55, 56 * 27 : 20, 21, 22, 23, 24, 25, 26, 27, 28, 29, 30, 31, 32, 33, 34, 35, 36, 37, 38, 39, 40, 41, 42, 43, 44, 45, 46, 47, 48, 49, 50 * 28 : 3, 4 * 29 : * 30 : 57, 58 * 31 : 20, 21, 22, 23, 24, 25, 26, 27, 28, 29, 30, 31, 32, 33, 34, 35, 36, 37, 38, 39, 40, 41, 42, 43, 44, 45, 46, 47, 48, 49, 50 * 32 : 9, 10, 11 * 33 : 59, 60, 61, 62 * 34 : 20, 21, 22, 23, 24, 25, 26, 27, 28, 29, 30, 31, 32, 33, 34, 35, 36, 37, 38, 39, 40, 41, 42, 43, 44, 45, 46, 47, 48, 49, 50 * 35 : 20, 21, 22, 23, 24, 25, 26, 27, 28, 29, 30, 31, 32, 33, 34, 35, 36, 37, 38, 39, 40, 41, 42, 43, 44, 45, 46, 47, 48, 49, 50 * 36 : * 37 : 12, 13, 14, 15 * 38 : 63, 64, 65, 66 * 39 : 20, 21, 22, 23, 24, 25, 26, 27, 28, 29, 30, 31, 32, 33, 34, 35, 36, 37, 38, 39, 40, 41, 42, 43, 44, 45, 46, 47, 48, 49, 50 * 40 : 20, 21, 22, 23, 24, 25, 26, 27, 28, 29, 30, 31, 32, 33, 34, 35, 36, 37, 38, 39, 40, 41, 42, 43, 44, 45, 46, 47, 48, 49, 50 * 41 : * 42 : 67, 68, 69, 70 * 43 : 20, 21, 22, 23, 24, 25, 26, 27, 28, 29, 30, 31, 32, 33, 34, 35, 36, 37, 38, 39, 40, 41, 42, 43, 44, 45, 46, 47, 48, 49, 50 * 44 : 20, 21, 22, 23, 24, 25, 26, 27, 28, 29, 30, 31, 32, 33, 34, 35, 36, 37, 38, 39, 40, 41, 42, 43, 44, 45, 46, 47, 48, 49, 50 * 45 : * 46 : 71, 72 * 47 : 20, 21, 22, 23, 24, 25, 26, 27, 28, 29, 30, 31, 32, 33, 34, 35, 36, 37, 38, 39, 40, 41, 42, 43, 44, 45, 46, 47, 48, 49, 50 * 48 : 16, 17, 18, 19 * 49 : 73, 74 * 50 : 20, 21, 22, 23, 24, 25, 26, 27, 28, 29, 30, 31, 32, 33, 34, 35, 36, 37, 38, 39, 40, 41, 42, 43, 44, 45, 46, 47, 48, 49, 50 * 51 : 51, 52, 53, 54 * 52 : 51, 52, 53, 54 * 53 : 51, 52, 53, 54 * 54 : 51, 52, 53, 54 * 55 : 55, 56 * 56 : 55, 56 * 57 : 57, 58 * 58 : 57, 58 * 59 : 59, 60, 61, 62 * 60 : 59, 60, 61, 62 * 61 : 59, 60, 61, 62 * 62 : 59, 60, 61, 62 * 63 : 63, 64, 65, 66 * 64 : 63, 64, 65, 66 * 65 : 63, 64, 65, 66 * 66 : 63, 64, 65, 66 * 67 : 67, 68, 69, 70 * 68 : 67, 68, 69, 70 * 69 : 67, 68, 69, 70 * 70 : 67, 68, 69, 70 * 71 : 71, 72 * 72 : 71, 72 * 73 : 73, 74 * 74 : 73, 74 This graph has the following strongly connected components: P_1: active#(pairNs) =#> mark#(cons(0, incr(oddNs))) active#(oddNs) =#> mark#(incr(pairNs)) active#(incr(cons(X, Y))) =#> mark#(cons(s(X), incr(Y))) active#(take(s(X), cons(Y, Z))) =#> mark#(cons(Y, take(X, Z))) active#(zip(cons(X, Y), cons(Z, U))) =#> mark#(cons(pair(X, Z), zip(Y, U))) active#(repItems(cons(X, Y))) =#> mark#(cons(X, cons(X, repItems(Y)))) mark#(pairNs) =#> active#(pairNs) mark#(cons(X, Y)) =#> mark#(X) mark#(incr(X)) =#> active#(incr(mark(X))) mark#(incr(X)) =#> mark#(X) mark#(oddNs) =#> active#(oddNs) mark#(s(X)) =#> mark#(X) mark#(take(X, Y)) =#> active#(take(mark(X), mark(Y))) mark#(take(X, Y)) =#> mark#(X) mark#(take(X, Y)) =#> mark#(Y) mark#(zip(X, Y)) =#> active#(zip(mark(X), mark(Y))) mark#(zip(X, Y)) =#> mark#(X) mark#(zip(X, Y)) =#> mark#(Y) mark#(pair(X, Y)) =#> mark#(X) mark#(pair(X, Y)) =#> mark#(Y) mark#(tail(X)) =#> mark#(X) mark#(repItems(X)) =#> active#(repItems(mark(X))) mark#(repItems(X)) =#> mark#(X) P_2: cons#(mark(X), Y) =#> cons#(X, Y) cons#(X, mark(Y)) =#> cons#(X, Y) cons#(active(X), Y) =#> cons#(X, Y) cons#(X, active(Y)) =#> cons#(X, Y) P_3: incr#(mark(X)) =#> incr#(X) incr#(active(X)) =#> incr#(X) P_4: s#(mark(X)) =#> s#(X) s#(active(X)) =#> s#(X) P_5: take#(mark(X), Y) =#> take#(X, Y) take#(X, mark(Y)) =#> take#(X, Y) take#(active(X), Y) =#> take#(X, Y) take#(X, active(Y)) =#> take#(X, Y) P_6: zip#(mark(X), Y) =#> zip#(X, Y) zip#(X, mark(Y)) =#> zip#(X, Y) zip#(active(X), Y) =#> zip#(X, Y) zip#(X, active(Y)) =#> zip#(X, Y) P_7: pair#(mark(X), Y) =#> pair#(X, Y) pair#(X, mark(Y)) =#> pair#(X, Y) pair#(active(X), Y) =#> pair#(X, Y) pair#(X, active(Y)) =#> pair#(X, Y) P_8: tail#(mark(X)) =#> tail#(X) tail#(active(X)) =#> tail#(X) P_9: repItems#(mark(X)) =#> repItems#(X) repItems#(active(X)) =#> repItems#(X) By [Kop12, Thm. 7.31], we may replace any dependency pair problem (P_0, R_0, m, f) by (P_1, R_0, m, f), (P_2, R_0, m, f), (P_3, R_0, m, f), (P_4, R_0, m, f), (P_5, R_0, m, f), (P_6, R_0, m, f), (P_7, R_0, m, f), (P_8, R_0, m, f) and (P_9, R_0, m, f). Thus, the original system is terminating if each of (P_1, R_0, minimal, formative), (P_2, R_0, minimal, formative), (P_3, R_0, minimal, formative), (P_4, R_0, minimal, formative), (P_5, R_0, minimal, formative), (P_6, R_0, minimal, formative), (P_7, R_0, minimal, formative), (P_8, R_0, minimal, formative) and (P_9, R_0, minimal, formative) is finite. We consider the dependency pair problem (P_9, R_0, minimal, formative). We apply the subterm criterion with the following projection function: nu(repItems#) = 1 Thus, we can orient the dependency pairs as follows: nu(repItems#(mark(X))) = mark(X) |> X = nu(repItems#(X)) nu(repItems#(active(X))) = active(X) |> X = nu(repItems#(X)) By [Kop12, Thm. 7.35], we may replace a dependency pair problem (P_9, R_0, minimal, f) by ({}, R_0, minimal, f). By the empty set processor [Kop12, Thm. 7.15] this problem may be immediately removed. Thus, the original system is terminating if each of (P_1, R_0, minimal, formative), (P_2, R_0, minimal, formative), (P_3, R_0, minimal, formative), (P_4, R_0, minimal, formative), (P_5, R_0, minimal, formative), (P_6, R_0, minimal, formative), (P_7, R_0, minimal, formative) and (P_8, R_0, minimal, formative) is finite. We consider the dependency pair problem (P_8, R_0, minimal, formative). We apply the subterm criterion with the following projection function: nu(tail#) = 1 Thus, we can orient the dependency pairs as follows: nu(tail#(mark(X))) = mark(X) |> X = nu(tail#(X)) nu(tail#(active(X))) = active(X) |> X = nu(tail#(X)) By [Kop12, Thm. 7.35], we may replace a dependency pair problem (P_8, R_0, minimal, f) by ({}, R_0, minimal, f). By the empty set processor [Kop12, Thm. 7.15] this problem may be immediately removed. Thus, the original system is terminating if each of (P_1, R_0, minimal, formative), (P_2, R_0, minimal, formative), (P_3, R_0, minimal, formative), (P_4, R_0, minimal, formative), (P_5, R_0, minimal, formative), (P_6, R_0, minimal, formative) and (P_7, R_0, minimal, formative) is finite. We consider the dependency pair problem (P_7, R_0, minimal, formative). We apply the subterm criterion with the following projection function: nu(pair#) = 1 Thus, we can orient the dependency pairs as follows: nu(pair#(mark(X), Y)) = mark(X) |> X = nu(pair#(X, Y)) nu(pair#(X, mark(Y))) = X = X = nu(pair#(X, Y)) nu(pair#(active(X), Y)) = active(X) |> X = nu(pair#(X, Y)) nu(pair#(X, active(Y))) = X = X = nu(pair#(X, Y)) By [Kop12, Thm. 7.35], we may replace a dependency pair problem (P_7, R_0, minimal, f) by (P_10, R_0, minimal, f), where P_10 contains: pair#(X, mark(Y)) =#> pair#(X, Y) pair#(X, active(Y)) =#> pair#(X, Y) Thus, the original system is terminating if each of (P_1, R_0, minimal, formative), (P_2, R_0, minimal, formative), (P_3, R_0, minimal, formative), (P_4, R_0, minimal, formative), (P_5, R_0, minimal, formative), (P_6, R_0, minimal, formative) and (P_10, R_0, minimal, formative) is finite. We consider the dependency pair problem (P_10, R_0, minimal, formative). We apply the subterm criterion with the following projection function: nu(pair#) = 2 Thus, we can orient the dependency pairs as follows: nu(pair#(X, mark(Y))) = mark(Y) |> Y = nu(pair#(X, Y)) nu(pair#(X, active(Y))) = active(Y) |> Y = nu(pair#(X, Y)) By [Kop12, Thm. 7.35], we may replace a dependency pair problem (P_10, R_0, minimal, f) by ({}, R_0, minimal, f). By the empty set processor [Kop12, Thm. 7.15] this problem may be immediately removed. Thus, the original system is terminating if each of (P_1, R_0, minimal, formative), (P_2, R_0, minimal, formative), (P_3, R_0, minimal, formative), (P_4, R_0, minimal, formative), (P_5, R_0, minimal, formative) and (P_6, R_0, minimal, formative) is finite. We consider the dependency pair problem (P_6, R_0, minimal, formative). We apply the subterm criterion with the following projection function: nu(zip#) = 1 Thus, we can orient the dependency pairs as follows: nu(zip#(mark(X), Y)) = mark(X) |> X = nu(zip#(X, Y)) nu(zip#(X, mark(Y))) = X = X = nu(zip#(X, Y)) nu(zip#(active(X), Y)) = active(X) |> X = nu(zip#(X, Y)) nu(zip#(X, active(Y))) = X = X = nu(zip#(X, Y)) By [Kop12, Thm. 7.35], we may replace a dependency pair problem (P_6, R_0, minimal, f) by (P_11, R_0, minimal, f), where P_11 contains: zip#(X, mark(Y)) =#> zip#(X, Y) zip#(X, active(Y)) =#> zip#(X, Y) Thus, the original system is terminating if each of (P_1, R_0, minimal, formative), (P_2, R_0, minimal, formative), (P_3, R_0, minimal, formative), (P_4, R_0, minimal, formative), (P_5, R_0, minimal, formative) and (P_11, R_0, minimal, formative) is finite. We consider the dependency pair problem (P_11, R_0, minimal, formative). We apply the subterm criterion with the following projection function: nu(zip#) = 2 Thus, we can orient the dependency pairs as follows: nu(zip#(X, mark(Y))) = mark(Y) |> Y = nu(zip#(X, Y)) nu(zip#(X, active(Y))) = active(Y) |> Y = nu(zip#(X, Y)) By [Kop12, Thm. 7.35], we may replace a dependency pair problem (P_11, R_0, minimal, f) by ({}, R_0, minimal, f). By the empty set processor [Kop12, Thm. 7.15] this problem may be immediately removed. Thus, the original system is terminating if each of (P_1, R_0, minimal, formative), (P_2, R_0, minimal, formative), (P_3, R_0, minimal, formative), (P_4, R_0, minimal, formative) and (P_5, R_0, minimal, formative) is finite. We consider the dependency pair problem (P_5, R_0, minimal, formative). We apply the subterm criterion with the following projection function: nu(take#) = 1 Thus, we can orient the dependency pairs as follows: nu(take#(mark(X), Y)) = mark(X) |> X = nu(take#(X, Y)) nu(take#(X, mark(Y))) = X = X = nu(take#(X, Y)) nu(take#(active(X), Y)) = active(X) |> X = nu(take#(X, Y)) nu(take#(X, active(Y))) = X = X = nu(take#(X, Y)) By [Kop12, Thm. 7.35], we may replace a dependency pair problem (P_5, R_0, minimal, f) by (P_12, R_0, minimal, f), where P_12 contains: take#(X, mark(Y)) =#> take#(X, Y) take#(X, active(Y)) =#> take#(X, Y) Thus, the original system is terminating if each of (P_1, R_0, minimal, formative), (P_2, R_0, minimal, formative), (P_3, R_0, minimal, formative), (P_4, R_0, minimal, formative) and (P_12, R_0, minimal, formative) is finite. We consider the dependency pair problem (P_12, R_0, minimal, formative). We apply the subterm criterion with the following projection function: nu(take#) = 2 Thus, we can orient the dependency pairs as follows: nu(take#(X, mark(Y))) = mark(Y) |> Y = nu(take#(X, Y)) nu(take#(X, active(Y))) = active(Y) |> Y = nu(take#(X, Y)) By [Kop12, Thm. 7.35], we may replace a dependency pair problem (P_12, R_0, minimal, f) by ({}, R_0, minimal, f). By the empty set processor [Kop12, Thm. 7.15] this problem may be immediately removed. Thus, the original system is terminating if each of (P_1, R_0, minimal, formative), (P_2, R_0, minimal, formative), (P_3, R_0, minimal, formative) and (P_4, R_0, minimal, formative) is finite. We consider the dependency pair problem (P_4, R_0, minimal, formative). We apply the subterm criterion with the following projection function: nu(s#) = 1 Thus, we can orient the dependency pairs as follows: nu(s#(mark(X))) = mark(X) |> X = nu(s#(X)) nu(s#(active(X))) = active(X) |> X = nu(s#(X)) By [Kop12, Thm. 7.35], we may replace a dependency pair problem (P_4, R_0, minimal, f) by ({}, R_0, minimal, f). By the empty set processor [Kop12, Thm. 7.15] this problem may be immediately removed. Thus, the original system is terminating if each of (P_1, R_0, minimal, formative), (P_2, R_0, minimal, formative) and (P_3, R_0, minimal, formative) is finite. We consider the dependency pair problem (P_3, R_0, minimal, formative). We apply the subterm criterion with the following projection function: nu(incr#) = 1 Thus, we can orient the dependency pairs as follows: nu(incr#(mark(X))) = mark(X) |> X = nu(incr#(X)) nu(incr#(active(X))) = active(X) |> X = nu(incr#(X)) By [Kop12, Thm. 7.35], we may replace a dependency pair problem (P_3, R_0, minimal, f) by ({}, R_0, minimal, f). By the empty set processor [Kop12, Thm. 7.15] this problem may be immediately removed. Thus, the original system is terminating if each of (P_1, R_0, minimal, formative) and (P_2, R_0, minimal, formative) is finite. We consider the dependency pair problem (P_2, R_0, minimal, formative). We apply the subterm criterion with the following projection function: nu(cons#) = 1 Thus, we can orient the dependency pairs as follows: nu(cons#(mark(X), Y)) = mark(X) |> X = nu(cons#(X, Y)) nu(cons#(X, mark(Y))) = X = X = nu(cons#(X, Y)) nu(cons#(active(X), Y)) = active(X) |> X = nu(cons#(X, Y)) nu(cons#(X, active(Y))) = X = X = nu(cons#(X, Y)) By [Kop12, Thm. 7.35], we may replace a dependency pair problem (P_2, R_0, minimal, f) by (P_13, R_0, minimal, f), where P_13 contains: cons#(X, mark(Y)) =#> cons#(X, Y) cons#(X, active(Y)) =#> cons#(X, Y) Thus, the original system is terminating if each of (P_1, R_0, minimal, formative) and (P_13, R_0, minimal, formative) is finite. We consider the dependency pair problem (P_13, R_0, minimal, formative). We apply the subterm criterion with the following projection function: nu(cons#) = 2 Thus, we can orient the dependency pairs as follows: nu(cons#(X, mark(Y))) = mark(Y) |> Y = nu(cons#(X, Y)) nu(cons#(X, active(Y))) = active(Y) |> Y = nu(cons#(X, Y)) By [Kop12, Thm. 7.35], we may replace a dependency pair problem (P_13, R_0, minimal, f) by ({}, R_0, minimal, f). By the empty set processor [Kop12, Thm. 7.15] this problem may be immediately removed. Thus, the original system is terminating if (P_1, R_0, minimal, formative) is finite. We consider the dependency pair problem (P_1, R_0, minimal, formative). We will use the reduction pair processor [Kop12, Thm. 7.16]. It suffices to find a standard reduction pair [Kop12, Def. 6.69]. Thus, we must orient: active#(pairNs) >? mark#(cons(0, incr(oddNs))) active#(oddNs) >? mark#(incr(pairNs)) active#(incr(cons(X, Y))) >? mark#(cons(s(X), incr(Y))) active#(take(s(X), cons(Y, Z))) >? mark#(cons(Y, take(X, Z))) active#(zip(cons(X, Y), cons(Z, U))) >? mark#(cons(pair(X, Z), zip(Y, U))) active#(repItems(cons(X, Y))) >? mark#(cons(X, cons(X, repItems(Y)))) mark#(pairNs) >? active#(pairNs) mark#(cons(X, Y)) >? mark#(X) mark#(incr(X)) >? active#(incr(mark(X))) mark#(incr(X)) >? mark#(X) mark#(oddNs) >? active#(oddNs) mark#(s(X)) >? mark#(X) mark#(take(X, Y)) >? active#(take(mark(X), mark(Y))) mark#(take(X, Y)) >? mark#(X) mark#(take(X, Y)) >? mark#(Y) mark#(zip(X, Y)) >? active#(zip(mark(X), mark(Y))) mark#(zip(X, Y)) >? mark#(X) mark#(zip(X, Y)) >? mark#(Y) mark#(pair(X, Y)) >? mark#(X) mark#(pair(X, Y)) >? mark#(Y) mark#(tail(X)) >? mark#(X) mark#(repItems(X)) >? active#(repItems(mark(X))) mark#(repItems(X)) >? mark#(X) active(pairNs) >= mark(cons(0, incr(oddNs))) active(oddNs) >= mark(incr(pairNs)) active(incr(cons(X, Y))) >= mark(cons(s(X), incr(Y))) active(take(s(X), cons(Y, Z))) >= mark(cons(Y, take(X, Z))) active(zip(cons(X, Y), cons(Z, U))) >= mark(cons(pair(X, Z), zip(Y, U))) active(repItems(cons(X, Y))) >= mark(cons(X, cons(X, repItems(Y)))) mark(pairNs) >= active(pairNs) mark(cons(X, Y)) >= active(cons(mark(X), Y)) mark(0) >= active(0) mark(incr(X)) >= active(incr(mark(X))) mark(oddNs) >= active(oddNs) mark(s(X)) >= active(s(mark(X))) mark(take(X, Y)) >= active(take(mark(X), mark(Y))) mark(nil) >= active(nil) mark(zip(X, Y)) >= active(zip(mark(X), mark(Y))) mark(pair(X, Y)) >= active(pair(mark(X), mark(Y))) mark(tail(X)) >= active(tail(mark(X))) mark(repItems(X)) >= active(repItems(mark(X))) cons(mark(X), Y) >= cons(X, Y) cons(X, mark(Y)) >= cons(X, Y) cons(active(X), Y) >= cons(X, Y) cons(X, active(Y)) >= cons(X, Y) incr(mark(X)) >= incr(X) incr(active(X)) >= incr(X) s(mark(X)) >= s(X) s(active(X)) >= s(X) take(mark(X), Y) >= take(X, Y) take(X, mark(Y)) >= take(X, Y) take(active(X), Y) >= take(X, Y) take(X, active(Y)) >= take(X, Y) zip(mark(X), Y) >= zip(X, Y) zip(X, mark(Y)) >= zip(X, Y) zip(active(X), Y) >= zip(X, Y) zip(X, active(Y)) >= zip(X, Y) pair(mark(X), Y) >= pair(X, Y) pair(X, mark(Y)) >= pair(X, Y) pair(active(X), Y) >= pair(X, Y) pair(X, active(Y)) >= pair(X, Y) tail(mark(X)) >= tail(X) tail(active(X)) >= tail(X) repItems(mark(X)) >= repItems(X) repItems(active(X)) >= repItems(X) We orient these requirements with a polynomial interpretation in the natural numbers. The following interpretation satisfies the requirements: 0 = 0 active = \y0.y0 active# = \y0.2y0 cons = \y0y1.y0 incr = \y0.2y0 mark = \y0.y0 mark# = \y0.2y0 nil = 0 oddNs = 1 pair = \y0y1.y0 + y1 pairNs = 0 repItems = \y0.y0 s = \y0.y0 tail = \y0.y0 take = \y0y1.y0 + y1 zip = \y0y1.y0 + y1 Using this interpretation, the requirements translate to: [[active#(pairNs)]] = 0 >= 0 = [[mark#(cons(0, incr(oddNs)))]] [[active#(oddNs)]] = 2 > 0 = [[mark#(incr(pairNs))]] [[active#(incr(cons(_x0, _x1)))]] = 4x0 >= 2x0 = [[mark#(cons(s(_x0), incr(_x1)))]] [[active#(take(s(_x0), cons(_x1, _x2)))]] = 2x0 + 2x1 >= 2x1 = [[mark#(cons(_x1, take(_x0, _x2)))]] [[active#(zip(cons(_x0, _x1), cons(_x2, _x3)))]] = 2x0 + 2x2 >= 2x0 + 2x2 = [[mark#(cons(pair(_x0, _x2), zip(_x1, _x3)))]] [[active#(repItems(cons(_x0, _x1)))]] = 2x0 >= 2x0 = [[mark#(cons(_x0, cons(_x0, repItems(_x1))))]] [[mark#(pairNs)]] = 0 >= 0 = [[active#(pairNs)]] [[mark#(cons(_x0, _x1))]] = 2x0 >= 2x0 = [[mark#(_x0)]] [[mark#(incr(_x0))]] = 4x0 >= 4x0 = [[active#(incr(mark(_x0)))]] [[mark#(incr(_x0))]] = 4x0 >= 2x0 = [[mark#(_x0)]] [[mark#(oddNs)]] = 2 >= 2 = [[active#(oddNs)]] [[mark#(s(_x0))]] = 2x0 >= 2x0 = [[mark#(_x0)]] [[mark#(take(_x0, _x1))]] = 2x0 + 2x1 >= 2x0 + 2x1 = [[active#(take(mark(_x0), mark(_x1)))]] [[mark#(take(_x0, _x1))]] = 2x0 + 2x1 >= 2x0 = [[mark#(_x0)]] [[mark#(take(_x0, _x1))]] = 2x0 + 2x1 >= 2x1 = [[mark#(_x1)]] [[mark#(zip(_x0, _x1))]] = 2x0 + 2x1 >= 2x0 + 2x1 = [[active#(zip(mark(_x0), mark(_x1)))]] [[mark#(zip(_x0, _x1))]] = 2x0 + 2x1 >= 2x0 = [[mark#(_x0)]] [[mark#(zip(_x0, _x1))]] = 2x0 + 2x1 >= 2x1 = [[mark#(_x1)]] [[mark#(pair(_x0, _x1))]] = 2x0 + 2x1 >= 2x0 = [[mark#(_x0)]] [[mark#(pair(_x0, _x1))]] = 2x0 + 2x1 >= 2x1 = [[mark#(_x1)]] [[mark#(tail(_x0))]] = 2x0 >= 2x0 = [[mark#(_x0)]] [[mark#(repItems(_x0))]] = 2x0 >= 2x0 = [[active#(repItems(mark(_x0)))]] [[mark#(repItems(_x0))]] = 2x0 >= 2x0 = [[mark#(_x0)]] [[active(pairNs)]] = 0 >= 0 = [[mark(cons(0, incr(oddNs)))]] [[active(oddNs)]] = 1 >= 0 = [[mark(incr(pairNs))]] [[active(incr(cons(_x0, _x1)))]] = 2x0 >= x0 = [[mark(cons(s(_x0), incr(_x1)))]] [[active(take(s(_x0), cons(_x1, _x2)))]] = x0 + x1 >= x1 = [[mark(cons(_x1, take(_x0, _x2)))]] [[active(zip(cons(_x0, _x1), cons(_x2, _x3)))]] = x0 + x2 >= x0 + x2 = [[mark(cons(pair(_x0, _x2), zip(_x1, _x3)))]] [[active(repItems(cons(_x0, _x1)))]] = x0 >= x0 = [[mark(cons(_x0, cons(_x0, repItems(_x1))))]] [[mark(pairNs)]] = 0 >= 0 = [[active(pairNs)]] [[mark(cons(_x0, _x1))]] = x0 >= x0 = [[active(cons(mark(_x0), _x1))]] [[mark(0)]] = 0 >= 0 = [[active(0)]] [[mark(incr(_x0))]] = 2x0 >= 2x0 = [[active(incr(mark(_x0)))]] [[mark(oddNs)]] = 1 >= 1 = [[active(oddNs)]] [[mark(s(_x0))]] = x0 >= x0 = [[active(s(mark(_x0)))]] [[mark(take(_x0, _x1))]] = x0 + x1 >= x0 + x1 = [[active(take(mark(_x0), mark(_x1)))]] [[mark(nil)]] = 0 >= 0 = [[active(nil)]] [[mark(zip(_x0, _x1))]] = x0 + x1 >= x0 + x1 = [[active(zip(mark(_x0), mark(_x1)))]] [[mark(pair(_x0, _x1))]] = x0 + x1 >= x0 + x1 = [[active(pair(mark(_x0), mark(_x1)))]] [[mark(tail(_x0))]] = x0 >= x0 = [[active(tail(mark(_x0)))]] [[mark(repItems(_x0))]] = x0 >= x0 = [[active(repItems(mark(_x0)))]] [[cons(mark(_x0), _x1)]] = x0 >= x0 = [[cons(_x0, _x1)]] [[cons(_x0, mark(_x1))]] = x0 >= x0 = [[cons(_x0, _x1)]] [[cons(active(_x0), _x1)]] = x0 >= x0 = [[cons(_x0, _x1)]] [[cons(_x0, active(_x1))]] = x0 >= x0 = [[cons(_x0, _x1)]] [[incr(mark(_x0))]] = 2x0 >= 2x0 = [[incr(_x0)]] [[incr(active(_x0))]] = 2x0 >= 2x0 = [[incr(_x0)]] [[s(mark(_x0))]] = x0 >= x0 = [[s(_x0)]] [[s(active(_x0))]] = x0 >= x0 = [[s(_x0)]] [[take(mark(_x0), _x1)]] = x0 + x1 >= x0 + x1 = [[take(_x0, _x1)]] [[take(_x0, mark(_x1))]] = x0 + x1 >= x0 + x1 = [[take(_x0, _x1)]] [[take(active(_x0), _x1)]] = x0 + x1 >= x0 + x1 = [[take(_x0, _x1)]] [[take(_x0, active(_x1))]] = x0 + x1 >= x0 + x1 = [[take(_x0, _x1)]] [[zip(mark(_x0), _x1)]] = x0 + x1 >= x0 + x1 = [[zip(_x0, _x1)]] [[zip(_x0, mark(_x1))]] = x0 + x1 >= x0 + x1 = [[zip(_x0, _x1)]] [[zip(active(_x0), _x1)]] = x0 + x1 >= x0 + x1 = [[zip(_x0, _x1)]] [[zip(_x0, active(_x1))]] = x0 + x1 >= x0 + x1 = [[zip(_x0, _x1)]] [[pair(mark(_x0), _x1)]] = x0 + x1 >= x0 + x1 = [[pair(_x0, _x1)]] [[pair(_x0, mark(_x1))]] = x0 + x1 >= x0 + x1 = [[pair(_x0, _x1)]] [[pair(active(_x0), _x1)]] = x0 + x1 >= x0 + x1 = [[pair(_x0, _x1)]] [[pair(_x0, active(_x1))]] = x0 + x1 >= x0 + x1 = [[pair(_x0, _x1)]] [[tail(mark(_x0))]] = x0 >= x0 = [[tail(_x0)]] [[tail(active(_x0))]] = x0 >= x0 = [[tail(_x0)]] [[repItems(mark(_x0))]] = x0 >= x0 = [[repItems(_x0)]] [[repItems(active(_x0))]] = x0 >= x0 = [[repItems(_x0)]] By the observations in [Kop12, Sec. 6.6], this reduction pair suffices; we may thus replace the dependency pair problem (P_1, R_0, minimal, formative) by (P_14, R_0, minimal, formative), where P_14 consists of: active#(pairNs) =#> mark#(cons(0, incr(oddNs))) active#(incr(cons(X, Y))) =#> mark#(cons(s(X), incr(Y))) active#(take(s(X), cons(Y, Z))) =#> mark#(cons(Y, take(X, Z))) active#(zip(cons(X, Y), cons(Z, U))) =#> mark#(cons(pair(X, Z), zip(Y, U))) active#(repItems(cons(X, Y))) =#> mark#(cons(X, cons(X, repItems(Y)))) mark#(pairNs) =#> active#(pairNs) mark#(cons(X, Y)) =#> mark#(X) mark#(incr(X)) =#> active#(incr(mark(X))) mark#(incr(X)) =#> mark#(X) mark#(oddNs) =#> active#(oddNs) mark#(s(X)) =#> mark#(X) mark#(take(X, Y)) =#> active#(take(mark(X), mark(Y))) mark#(take(X, Y)) =#> mark#(X) mark#(take(X, Y)) =#> mark#(Y) mark#(zip(X, Y)) =#> active#(zip(mark(X), mark(Y))) mark#(zip(X, Y)) =#> mark#(X) mark#(zip(X, Y)) =#> mark#(Y) mark#(pair(X, Y)) =#> mark#(X) mark#(pair(X, Y)) =#> mark#(Y) mark#(tail(X)) =#> mark#(X) mark#(repItems(X)) =#> active#(repItems(mark(X))) mark#(repItems(X)) =#> mark#(X) Thus, the original system is terminating if (P_14, R_0, minimal, formative) is finite. We consider the dependency pair problem (P_14, R_0, minimal, formative). We place the elements of P in a dependency graph approximation G (see e.g. [Kop12, Thm. 7.27, 7.29], as follows: * 0 : 6 * 1 : 6 * 2 : 6 * 3 : 6 * 4 : 6 * 5 : 0 * 6 : 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19, 20, 21 * 7 : 1 * 8 : 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19, 20, 21 * 9 : * 10 : 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19, 20, 21 * 11 : 2 * 12 : 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19, 20, 21 * 13 : 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19, 20, 21 * 14 : 3 * 15 : 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19, 20, 21 * 16 : 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19, 20, 21 * 17 : 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19, 20, 21 * 18 : 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19, 20, 21 * 19 : 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19, 20, 21 * 20 : 4 * 21 : 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19, 20, 21 This graph has the following strongly connected components: P_15: active#(pairNs) =#> mark#(cons(0, incr(oddNs))) active#(incr(cons(X, Y))) =#> mark#(cons(s(X), incr(Y))) active#(take(s(X), cons(Y, Z))) =#> mark#(cons(Y, take(X, Z))) active#(zip(cons(X, Y), cons(Z, U))) =#> mark#(cons(pair(X, Z), zip(Y, U))) active#(repItems(cons(X, Y))) =#> mark#(cons(X, cons(X, repItems(Y)))) mark#(pairNs) =#> active#(pairNs) mark#(cons(X, Y)) =#> mark#(X) mark#(incr(X)) =#> active#(incr(mark(X))) mark#(incr(X)) =#> mark#(X) mark#(s(X)) =#> mark#(X) mark#(take(X, Y)) =#> active#(take(mark(X), mark(Y))) mark#(take(X, Y)) =#> mark#(X) mark#(take(X, Y)) =#> mark#(Y) mark#(zip(X, Y)) =#> active#(zip(mark(X), mark(Y))) mark#(zip(X, Y)) =#> mark#(X) mark#(zip(X, Y)) =#> mark#(Y) mark#(pair(X, Y)) =#> mark#(X) mark#(pair(X, Y)) =#> mark#(Y) mark#(tail(X)) =#> mark#(X) mark#(repItems(X)) =#> active#(repItems(mark(X))) mark#(repItems(X)) =#> mark#(X) By [Kop12, Thm. 7.31], we may replace any dependency pair problem (P_14, R_0, m, f) by (P_15, R_0, m, f). Thus, the original system is terminating if (P_15, R_0, minimal, formative) is finite. We consider the dependency pair problem (P_15, R_0, minimal, formative). We will use the reduction pair processor [Kop12, Thm. 7.16]. It suffices to find a standard reduction pair [Kop12, Def. 6.69]. Thus, we must orient: active#(pairNs) >? mark#(cons(0, incr(oddNs))) active#(incr(cons(X, Y))) >? mark#(cons(s(X), incr(Y))) active#(take(s(X), cons(Y, Z))) >? mark#(cons(Y, take(X, Z))) active#(zip(cons(X, Y), cons(Z, U))) >? mark#(cons(pair(X, Z), zip(Y, U))) active#(repItems(cons(X, Y))) >? mark#(cons(X, cons(X, repItems(Y)))) mark#(pairNs) >? active#(pairNs) mark#(cons(X, Y)) >? mark#(X) mark#(incr(X)) >? active#(incr(mark(X))) mark#(incr(X)) >? mark#(X) mark#(s(X)) >? mark#(X) mark#(take(X, Y)) >? active#(take(mark(X), mark(Y))) mark#(take(X, Y)) >? mark#(X) mark#(take(X, Y)) >? mark#(Y) mark#(zip(X, Y)) >? active#(zip(mark(X), mark(Y))) mark#(zip(X, Y)) >? mark#(X) mark#(zip(X, Y)) >? mark#(Y) mark#(pair(X, Y)) >? mark#(X) mark#(pair(X, Y)) >? mark#(Y) mark#(tail(X)) >? mark#(X) mark#(repItems(X)) >? active#(repItems(mark(X))) mark#(repItems(X)) >? mark#(X) active(pairNs) >= mark(cons(0, incr(oddNs))) active(oddNs) >= mark(incr(pairNs)) active(incr(cons(X, Y))) >= mark(cons(s(X), incr(Y))) active(take(s(X), cons(Y, Z))) >= mark(cons(Y, take(X, Z))) active(zip(cons(X, Y), cons(Z, U))) >= mark(cons(pair(X, Z), zip(Y, U))) active(repItems(cons(X, Y))) >= mark(cons(X, cons(X, repItems(Y)))) mark(pairNs) >= active(pairNs) mark(cons(X, Y)) >= active(cons(mark(X), Y)) mark(0) >= active(0) mark(incr(X)) >= active(incr(mark(X))) mark(oddNs) >= active(oddNs) mark(s(X)) >= active(s(mark(X))) mark(take(X, Y)) >= active(take(mark(X), mark(Y))) mark(nil) >= active(nil) mark(zip(X, Y)) >= active(zip(mark(X), mark(Y))) mark(pair(X, Y)) >= active(pair(mark(X), mark(Y))) mark(tail(X)) >= active(tail(mark(X))) mark(repItems(X)) >= active(repItems(mark(X))) cons(mark(X), Y) >= cons(X, Y) cons(X, mark(Y)) >= cons(X, Y) cons(active(X), Y) >= cons(X, Y) cons(X, active(Y)) >= cons(X, Y) incr(mark(X)) >= incr(X) incr(active(X)) >= incr(X) s(mark(X)) >= s(X) s(active(X)) >= s(X) take(mark(X), Y) >= take(X, Y) take(X, mark(Y)) >= take(X, Y) take(active(X), Y) >= take(X, Y) take(X, active(Y)) >= take(X, Y) zip(mark(X), Y) >= zip(X, Y) zip(X, mark(Y)) >= zip(X, Y) zip(active(X), Y) >= zip(X, Y) zip(X, active(Y)) >= zip(X, Y) pair(mark(X), Y) >= pair(X, Y) pair(X, mark(Y)) >= pair(X, Y) pair(active(X), Y) >= pair(X, Y) pair(X, active(Y)) >= pair(X, Y) tail(mark(X)) >= tail(X) tail(active(X)) >= tail(X) repItems(mark(X)) >= repItems(X) repItems(active(X)) >= repItems(X) We orient these requirements with a polynomial interpretation in the natural numbers. The following interpretation satisfies the requirements: 0 = 0 active = \y0.y0 active# = \y0.2y0 cons = \y0y1.2y0 incr = \y0.y0 mark = \y0.y0 mark# = \y0.2y0 nil = 0 oddNs = 0 pair = \y0y1.y0 + 2y1 pairNs = 0 repItems = \y0.1 + y0 s = \y0.y0 tail = \y0.y0 take = \y0y1.y0 + 2y1 zip = \y0y1.y0 + 2y1 Using this interpretation, the requirements translate to: [[active#(pairNs)]] = 0 >= 0 = [[mark#(cons(0, incr(oddNs)))]] [[active#(incr(cons(_x0, _x1)))]] = 4x0 >= 4x0 = [[mark#(cons(s(_x0), incr(_x1)))]] [[active#(take(s(_x0), cons(_x1, _x2)))]] = 2x0 + 8x1 >= 4x1 = [[mark#(cons(_x1, take(_x0, _x2)))]] [[active#(zip(cons(_x0, _x1), cons(_x2, _x3)))]] = 4x0 + 8x2 >= 4x0 + 8x2 = [[mark#(cons(pair(_x0, _x2), zip(_x1, _x3)))]] [[active#(repItems(cons(_x0, _x1)))]] = 2 + 4x0 > 4x0 = [[mark#(cons(_x0, cons(_x0, repItems(_x1))))]] [[mark#(pairNs)]] = 0 >= 0 = [[active#(pairNs)]] [[mark#(cons(_x0, _x1))]] = 4x0 >= 2x0 = [[mark#(_x0)]] [[mark#(incr(_x0))]] = 2x0 >= 2x0 = [[active#(incr(mark(_x0)))]] [[mark#(incr(_x0))]] = 2x0 >= 2x0 = [[mark#(_x0)]] [[mark#(s(_x0))]] = 2x0 >= 2x0 = [[mark#(_x0)]] [[mark#(take(_x0, _x1))]] = 2x0 + 4x1 >= 2x0 + 4x1 = [[active#(take(mark(_x0), mark(_x1)))]] [[mark#(take(_x0, _x1))]] = 2x0 + 4x1 >= 2x0 = [[mark#(_x0)]] [[mark#(take(_x0, _x1))]] = 2x0 + 4x1 >= 2x1 = [[mark#(_x1)]] [[mark#(zip(_x0, _x1))]] = 2x0 + 4x1 >= 2x0 + 4x1 = [[active#(zip(mark(_x0), mark(_x1)))]] [[mark#(zip(_x0, _x1))]] = 2x0 + 4x1 >= 2x0 = [[mark#(_x0)]] [[mark#(zip(_x0, _x1))]] = 2x0 + 4x1 >= 2x1 = [[mark#(_x1)]] [[mark#(pair(_x0, _x1))]] = 2x0 + 4x1 >= 2x0 = [[mark#(_x0)]] [[mark#(pair(_x0, _x1))]] = 2x0 + 4x1 >= 2x1 = [[mark#(_x1)]] [[mark#(tail(_x0))]] = 2x0 >= 2x0 = [[mark#(_x0)]] [[mark#(repItems(_x0))]] = 2 + 2x0 >= 2 + 2x0 = [[active#(repItems(mark(_x0)))]] [[mark#(repItems(_x0))]] = 2 + 2x0 > 2x0 = [[mark#(_x0)]] [[active(pairNs)]] = 0 >= 0 = [[mark(cons(0, incr(oddNs)))]] [[active(oddNs)]] = 0 >= 0 = [[mark(incr(pairNs))]] [[active(incr(cons(_x0, _x1)))]] = 2x0 >= 2x0 = [[mark(cons(s(_x0), incr(_x1)))]] [[active(take(s(_x0), cons(_x1, _x2)))]] = x0 + 4x1 >= 2x1 = [[mark(cons(_x1, take(_x0, _x2)))]] [[active(zip(cons(_x0, _x1), cons(_x2, _x3)))]] = 2x0 + 4x2 >= 2x0 + 4x2 = [[mark(cons(pair(_x0, _x2), zip(_x1, _x3)))]] [[active(repItems(cons(_x0, _x1)))]] = 1 + 2x0 >= 2x0 = [[mark(cons(_x0, cons(_x0, repItems(_x1))))]] [[mark(pairNs)]] = 0 >= 0 = [[active(pairNs)]] [[mark(cons(_x0, _x1))]] = 2x0 >= 2x0 = [[active(cons(mark(_x0), _x1))]] [[mark(0)]] = 0 >= 0 = [[active(0)]] [[mark(incr(_x0))]] = x0 >= x0 = [[active(incr(mark(_x0)))]] [[mark(oddNs)]] = 0 >= 0 = [[active(oddNs)]] [[mark(s(_x0))]] = x0 >= x0 = [[active(s(mark(_x0)))]] [[mark(take(_x0, _x1))]] = x0 + 2x1 >= x0 + 2x1 = [[active(take(mark(_x0), mark(_x1)))]] [[mark(nil)]] = 0 >= 0 = [[active(nil)]] [[mark(zip(_x0, _x1))]] = x0 + 2x1 >= x0 + 2x1 = [[active(zip(mark(_x0), mark(_x1)))]] [[mark(pair(_x0, _x1))]] = x0 + 2x1 >= x0 + 2x1 = [[active(pair(mark(_x0), mark(_x1)))]] [[mark(tail(_x0))]] = x0 >= x0 = [[active(tail(mark(_x0)))]] [[mark(repItems(_x0))]] = 1 + x0 >= 1 + x0 = [[active(repItems(mark(_x0)))]] [[cons(mark(_x0), _x1)]] = 2x0 >= 2x0 = [[cons(_x0, _x1)]] [[cons(_x0, mark(_x1))]] = 2x0 >= 2x0 = [[cons(_x0, _x1)]] [[cons(active(_x0), _x1)]] = 2x0 >= 2x0 = [[cons(_x0, _x1)]] [[cons(_x0, active(_x1))]] = 2x0 >= 2x0 = [[cons(_x0, _x1)]] [[incr(mark(_x0))]] = x0 >= x0 = [[incr(_x0)]] [[incr(active(_x0))]] = x0 >= x0 = [[incr(_x0)]] [[s(mark(_x0))]] = x0 >= x0 = [[s(_x0)]] [[s(active(_x0))]] = x0 >= x0 = [[s(_x0)]] [[take(mark(_x0), _x1)]] = x0 + 2x1 >= x0 + 2x1 = [[take(_x0, _x1)]] [[take(_x0, mark(_x1))]] = x0 + 2x1 >= x0 + 2x1 = [[take(_x0, _x1)]] [[take(active(_x0), _x1)]] = x0 + 2x1 >= x0 + 2x1 = [[take(_x0, _x1)]] [[take(_x0, active(_x1))]] = x0 + 2x1 >= x0 + 2x1 = [[take(_x0, _x1)]] [[zip(mark(_x0), _x1)]] = x0 + 2x1 >= x0 + 2x1 = [[zip(_x0, _x1)]] [[zip(_x0, mark(_x1))]] = x0 + 2x1 >= x0 + 2x1 = [[zip(_x0, _x1)]] [[zip(active(_x0), _x1)]] = x0 + 2x1 >= x0 + 2x1 = [[zip(_x0, _x1)]] [[zip(_x0, active(_x1))]] = x0 + 2x1 >= x0 + 2x1 = [[zip(_x0, _x1)]] [[pair(mark(_x0), _x1)]] = x0 + 2x1 >= x0 + 2x1 = [[pair(_x0, _x1)]] [[pair(_x0, mark(_x1))]] = x0 + 2x1 >= x0 + 2x1 = [[pair(_x0, _x1)]] [[pair(active(_x0), _x1)]] = x0 + 2x1 >= x0 + 2x1 = [[pair(_x0, _x1)]] [[pair(_x0, active(_x1))]] = x0 + 2x1 >= x0 + 2x1 = [[pair(_x0, _x1)]] [[tail(mark(_x0))]] = x0 >= x0 = [[tail(_x0)]] [[tail(active(_x0))]] = x0 >= x0 = [[tail(_x0)]] [[repItems(mark(_x0))]] = 1 + x0 >= 1 + x0 = [[repItems(_x0)]] [[repItems(active(_x0))]] = 1 + x0 >= 1 + x0 = [[repItems(_x0)]] By the observations in [Kop12, Sec. 6.6], this reduction pair suffices; we may thus replace the dependency pair problem (P_15, R_0, minimal, formative) by (P_16, R_0, minimal, formative), where P_16 consists of: active#(pairNs) =#> mark#(cons(0, incr(oddNs))) active#(incr(cons(X, Y))) =#> mark#(cons(s(X), incr(Y))) active#(take(s(X), cons(Y, Z))) =#> mark#(cons(Y, take(X, Z))) active#(zip(cons(X, Y), cons(Z, U))) =#> mark#(cons(pair(X, Z), zip(Y, U))) mark#(pairNs) =#> active#(pairNs) mark#(cons(X, Y)) =#> mark#(X) mark#(incr(X)) =#> active#(incr(mark(X))) mark#(incr(X)) =#> mark#(X) mark#(s(X)) =#> mark#(X) mark#(take(X, Y)) =#> active#(take(mark(X), mark(Y))) mark#(take(X, Y)) =#> mark#(X) mark#(take(X, Y)) =#> mark#(Y) mark#(zip(X, Y)) =#> active#(zip(mark(X), mark(Y))) mark#(zip(X, Y)) =#> mark#(X) mark#(zip(X, Y)) =#> mark#(Y) mark#(pair(X, Y)) =#> mark#(X) mark#(pair(X, Y)) =#> mark#(Y) mark#(tail(X)) =#> mark#(X) mark#(repItems(X)) =#> active#(repItems(mark(X))) Thus, the original system is terminating if (P_16, R_0, minimal, formative) is finite. We consider the dependency pair problem (P_16, R_0, minimal, formative). We place the elements of P in a dependency graph approximation G (see e.g. [Kop12, Thm. 7.27, 7.29], as follows: * 0 : 5 * 1 : 5 * 2 : 5 * 3 : 5 * 4 : 0 * 5 : 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18 * 6 : 1 * 7 : 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18 * 8 : 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18 * 9 : 2 * 10 : 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18 * 11 : 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18 * 12 : 3 * 13 : 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18 * 14 : 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18 * 15 : 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18 * 16 : 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18 * 17 : 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18 * 18 : This graph has the following strongly connected components: P_17: active#(pairNs) =#> mark#(cons(0, incr(oddNs))) active#(incr(cons(X, Y))) =#> mark#(cons(s(X), incr(Y))) active#(take(s(X), cons(Y, Z))) =#> mark#(cons(Y, take(X, Z))) active#(zip(cons(X, Y), cons(Z, U))) =#> mark#(cons(pair(X, Z), zip(Y, U))) mark#(pairNs) =#> active#(pairNs) mark#(cons(X, Y)) =#> mark#(X) mark#(incr(X)) =#> active#(incr(mark(X))) mark#(incr(X)) =#> mark#(X) mark#(s(X)) =#> mark#(X) mark#(take(X, Y)) =#> active#(take(mark(X), mark(Y))) mark#(take(X, Y)) =#> mark#(X) mark#(take(X, Y)) =#> mark#(Y) mark#(zip(X, Y)) =#> active#(zip(mark(X), mark(Y))) mark#(zip(X, Y)) =#> mark#(X) mark#(zip(X, Y)) =#> mark#(Y) mark#(pair(X, Y)) =#> mark#(X) mark#(pair(X, Y)) =#> mark#(Y) mark#(tail(X)) =#> mark#(X) By [Kop12, Thm. 7.31], we may replace any dependency pair problem (P_16, R_0, m, f) by (P_17, R_0, m, f). Thus, the original system is terminating if (P_17, R_0, minimal, formative) is finite. We consider the dependency pair problem (P_17, R_0, minimal, formative). The formative rules of (P_17, R_0) are R_1 ::= active(pairNs) => mark(cons(0, incr(oddNs))) active(oddNs) => mark(incr(pairNs)) active(incr(cons(X, Y))) => mark(cons(s(X), incr(Y))) active(take(s(X), cons(Y, Z))) => mark(cons(Y, take(X, Z))) active(zip(cons(X, Y), cons(Z, U))) => mark(cons(pair(X, Z), zip(Y, U))) active(repItems(cons(X, Y))) => mark(cons(X, cons(X, repItems(Y)))) mark(pairNs) => active(pairNs) mark(cons(X, Y)) => active(cons(mark(X), Y)) mark(0) => active(0) mark(incr(X)) => active(incr(mark(X))) mark(oddNs) => active(oddNs) mark(s(X)) => active(s(mark(X))) mark(take(X, Y)) => active(take(mark(X), mark(Y))) mark(nil) => active(nil) mark(zip(X, Y)) => active(zip(mark(X), mark(Y))) mark(pair(X, Y)) => active(pair(mark(X), mark(Y))) mark(tail(X)) => active(tail(mark(X))) mark(repItems(X)) => active(repItems(mark(X))) cons(mark(X), Y) => cons(X, Y) cons(X, mark(Y)) => cons(X, Y) cons(active(X), Y) => cons(X, Y) cons(X, active(Y)) => cons(X, Y) incr(mark(X)) => incr(X) incr(active(X)) => incr(X) s(mark(X)) => s(X) s(active(X)) => s(X) take(mark(X), Y) => take(X, Y) take(X, mark(Y)) => take(X, Y) take(active(X), Y) => take(X, Y) take(X, active(Y)) => take(X, Y) zip(mark(X), Y) => zip(X, Y) zip(X, mark(Y)) => zip(X, Y) zip(active(X), Y) => zip(X, Y) zip(X, active(Y)) => zip(X, Y) pair(mark(X), Y) => pair(X, Y) pair(X, mark(Y)) => pair(X, Y) pair(active(X), Y) => pair(X, Y) pair(X, active(Y)) => pair(X, Y) tail(mark(X)) => tail(X) tail(active(X)) => tail(X) By [Kop12, Thm. 7.17], we may replace the dependency pair problem (P_17, R_0, minimal, formative) by (P_17, R_1, minimal, formative). Thus, the original system is terminating if (P_17, R_1, minimal, formative) is finite. We consider the dependency pair problem (P_17, R_1, minimal, formative). We will use the reduction pair processor [Kop12, Thm. 7.16]. It suffices to find a standard reduction pair [Kop12, Def. 6.69]. Thus, we must orient: active#(pairNs) >? mark#(cons(0, incr(oddNs))) active#(incr(cons(X, Y))) >? mark#(cons(s(X), incr(Y))) active#(take(s(X), cons(Y, Z))) >? mark#(cons(Y, take(X, Z))) active#(zip(cons(X, Y), cons(Z, U))) >? mark#(cons(pair(X, Z), zip(Y, U))) mark#(pairNs) >? active#(pairNs) mark#(cons(X, Y)) >? mark#(X) mark#(incr(X)) >? active#(incr(mark(X))) mark#(incr(X)) >? mark#(X) mark#(s(X)) >? mark#(X) mark#(take(X, Y)) >? active#(take(mark(X), mark(Y))) mark#(take(X, Y)) >? mark#(X) mark#(take(X, Y)) >? mark#(Y) mark#(zip(X, Y)) >? active#(zip(mark(X), mark(Y))) mark#(zip(X, Y)) >? mark#(X) mark#(zip(X, Y)) >? mark#(Y) mark#(pair(X, Y)) >? mark#(X) mark#(pair(X, Y)) >? mark#(Y) mark#(tail(X)) >? mark#(X) active(pairNs) >= mark(cons(0, incr(oddNs))) active(oddNs) >= mark(incr(pairNs)) active(incr(cons(X, Y))) >= mark(cons(s(X), incr(Y))) active(take(s(X), cons(Y, Z))) >= mark(cons(Y, take(X, Z))) active(zip(cons(X, Y), cons(Z, U))) >= mark(cons(pair(X, Z), zip(Y, U))) active(repItems(cons(X, Y))) >= mark(cons(X, cons(X, repItems(Y)))) mark(pairNs) >= active(pairNs) mark(cons(X, Y)) >= active(cons(mark(X), Y)) mark(0) >= active(0) mark(incr(X)) >= active(incr(mark(X))) mark(oddNs) >= active(oddNs) mark(s(X)) >= active(s(mark(X))) mark(take(X, Y)) >= active(take(mark(X), mark(Y))) mark(nil) >= active(nil) mark(zip(X, Y)) >= active(zip(mark(X), mark(Y))) mark(pair(X, Y)) >= active(pair(mark(X), mark(Y))) mark(tail(X)) >= active(tail(mark(X))) mark(repItems(X)) >= active(repItems(mark(X))) cons(mark(X), Y) >= cons(X, Y) cons(X, mark(Y)) >= cons(X, Y) cons(active(X), Y) >= cons(X, Y) cons(X, active(Y)) >= cons(X, Y) incr(mark(X)) >= incr(X) incr(active(X)) >= incr(X) s(mark(X)) >= s(X) s(active(X)) >= s(X) take(mark(X), Y) >= take(X, Y) take(X, mark(Y)) >= take(X, Y) take(active(X), Y) >= take(X, Y) take(X, active(Y)) >= take(X, Y) zip(mark(X), Y) >= zip(X, Y) zip(X, mark(Y)) >= zip(X, Y) zip(active(X), Y) >= zip(X, Y) zip(X, active(Y)) >= zip(X, Y) pair(mark(X), Y) >= pair(X, Y) pair(X, mark(Y)) >= pair(X, Y) pair(active(X), Y) >= pair(X, Y) pair(X, active(Y)) >= pair(X, Y) tail(mark(X)) >= tail(X) tail(active(X)) >= tail(X) We orient these requirements with a polynomial interpretation in the natural numbers. The following interpretation satisfies the requirements: 0 = 0 active = \y0.y0 active# = \y0.y0 cons = \y0y1.y0 incr = \y0.2 + y0 mark = \y0.y0 mark# = \y0.y0 nil = 0 oddNs = 3 pair = \y0y1.3 + y0 + y1 pairNs = 1 repItems = \y0.2y0 s = \y0.y0 tail = \y0.2y0 take = \y0y1.2y0 + 2y1 zip = \y0y1.3 + y0 + y1 Using this interpretation, the requirements translate to: [[active#(pairNs)]] = 1 > 0 = [[mark#(cons(0, incr(oddNs)))]] [[active#(incr(cons(_x0, _x1)))]] = 2 + x0 > x0 = [[mark#(cons(s(_x0), incr(_x1)))]] [[active#(take(s(_x0), cons(_x1, _x2)))]] = 2x0 + 2x1 >= x1 = [[mark#(cons(_x1, take(_x0, _x2)))]] [[active#(zip(cons(_x0, _x1), cons(_x2, _x3)))]] = 3 + x0 + x2 >= 3 + x0 + x2 = [[mark#(cons(pair(_x0, _x2), zip(_x1, _x3)))]] [[mark#(pairNs)]] = 1 >= 1 = [[active#(pairNs)]] [[mark#(cons(_x0, _x1))]] = x0 >= x0 = [[mark#(_x0)]] [[mark#(incr(_x0))]] = 2 + x0 >= 2 + x0 = [[active#(incr(mark(_x0)))]] [[mark#(incr(_x0))]] = 2 + x0 > x0 = [[mark#(_x0)]] [[mark#(s(_x0))]] = x0 >= x0 = [[mark#(_x0)]] [[mark#(take(_x0, _x1))]] = 2x0 + 2x1 >= 2x0 + 2x1 = [[active#(take(mark(_x0), mark(_x1)))]] [[mark#(take(_x0, _x1))]] = 2x0 + 2x1 >= x0 = [[mark#(_x0)]] [[mark#(take(_x0, _x1))]] = 2x0 + 2x1 >= x1 = [[mark#(_x1)]] [[mark#(zip(_x0, _x1))]] = 3 + x0 + x1 >= 3 + x0 + x1 = [[active#(zip(mark(_x0), mark(_x1)))]] [[mark#(zip(_x0, _x1))]] = 3 + x0 + x1 > x0 = [[mark#(_x0)]] [[mark#(zip(_x0, _x1))]] = 3 + x0 + x1 > x1 = [[mark#(_x1)]] [[mark#(pair(_x0, _x1))]] = 3 + x0 + x1 > x0 = [[mark#(_x0)]] [[mark#(pair(_x0, _x1))]] = 3 + x0 + x1 > x1 = [[mark#(_x1)]] [[mark#(tail(_x0))]] = 2x0 >= x0 = [[mark#(_x0)]] [[active(pairNs)]] = 1 >= 0 = [[mark(cons(0, incr(oddNs)))]] [[active(oddNs)]] = 3 >= 3 = [[mark(incr(pairNs))]] [[active(incr(cons(_x0, _x1)))]] = 2 + x0 >= x0 = [[mark(cons(s(_x0), incr(_x1)))]] [[active(take(s(_x0), cons(_x1, _x2)))]] = 2x0 + 2x1 >= x1 = [[mark(cons(_x1, take(_x0, _x2)))]] [[active(zip(cons(_x0, _x1), cons(_x2, _x3)))]] = 3 + x0 + x2 >= 3 + x0 + x2 = [[mark(cons(pair(_x0, _x2), zip(_x1, _x3)))]] [[active(repItems(cons(_x0, _x1)))]] = 2x0 >= x0 = [[mark(cons(_x0, cons(_x0, repItems(_x1))))]] [[mark(pairNs)]] = 1 >= 1 = [[active(pairNs)]] [[mark(cons(_x0, _x1))]] = x0 >= x0 = [[active(cons(mark(_x0), _x1))]] [[mark(0)]] = 0 >= 0 = [[active(0)]] [[mark(incr(_x0))]] = 2 + x0 >= 2 + x0 = [[active(incr(mark(_x0)))]] [[mark(oddNs)]] = 3 >= 3 = [[active(oddNs)]] [[mark(s(_x0))]] = x0 >= x0 = [[active(s(mark(_x0)))]] [[mark(take(_x0, _x1))]] = 2x0 + 2x1 >= 2x0 + 2x1 = [[active(take(mark(_x0), mark(_x1)))]] [[mark(nil)]] = 0 >= 0 = [[active(nil)]] [[mark(zip(_x0, _x1))]] = 3 + x0 + x1 >= 3 + x0 + x1 = [[active(zip(mark(_x0), mark(_x1)))]] [[mark(pair(_x0, _x1))]] = 3 + x0 + x1 >= 3 + x0 + x1 = [[active(pair(mark(_x0), mark(_x1)))]] [[mark(tail(_x0))]] = 2x0 >= 2x0 = [[active(tail(mark(_x0)))]] [[mark(repItems(_x0))]] = 2x0 >= 2x0 = [[active(repItems(mark(_x0)))]] [[cons(mark(_x0), _x1)]] = x0 >= x0 = [[cons(_x0, _x1)]] [[cons(_x0, mark(_x1))]] = x0 >= x0 = [[cons(_x0, _x1)]] [[cons(active(_x0), _x1)]] = x0 >= x0 = [[cons(_x0, _x1)]] [[cons(_x0, active(_x1))]] = x0 >= x0 = [[cons(_x0, _x1)]] [[incr(mark(_x0))]] = 2 + x0 >= 2 + x0 = [[incr(_x0)]] [[incr(active(_x0))]] = 2 + x0 >= 2 + x0 = [[incr(_x0)]] [[s(mark(_x0))]] = x0 >= x0 = [[s(_x0)]] [[s(active(_x0))]] = x0 >= x0 = [[s(_x0)]] [[take(mark(_x0), _x1)]] = 2x0 + 2x1 >= 2x0 + 2x1 = [[take(_x0, _x1)]] [[take(_x0, mark(_x1))]] = 2x0 + 2x1 >= 2x0 + 2x1 = [[take(_x0, _x1)]] [[take(active(_x0), _x1)]] = 2x0 + 2x1 >= 2x0 + 2x1 = [[take(_x0, _x1)]] [[take(_x0, active(_x1))]] = 2x0 + 2x1 >= 2x0 + 2x1 = [[take(_x0, _x1)]] [[zip(mark(_x0), _x1)]] = 3 + x0 + x1 >= 3 + x0 + x1 = [[zip(_x0, _x1)]] [[zip(_x0, mark(_x1))]] = 3 + x0 + x1 >= 3 + x0 + x1 = [[zip(_x0, _x1)]] [[zip(active(_x0), _x1)]] = 3 + x0 + x1 >= 3 + x0 + x1 = [[zip(_x0, _x1)]] [[zip(_x0, active(_x1))]] = 3 + x0 + x1 >= 3 + x0 + x1 = [[zip(_x0, _x1)]] [[pair(mark(_x0), _x1)]] = 3 + x0 + x1 >= 3 + x0 + x1 = [[pair(_x0, _x1)]] [[pair(_x0, mark(_x1))]] = 3 + x0 + x1 >= 3 + x0 + x1 = [[pair(_x0, _x1)]] [[pair(active(_x0), _x1)]] = 3 + x0 + x1 >= 3 + x0 + x1 = [[pair(_x0, _x1)]] [[pair(_x0, active(_x1))]] = 3 + x0 + x1 >= 3 + x0 + x1 = [[pair(_x0, _x1)]] [[tail(mark(_x0))]] = 2x0 >= 2x0 = [[tail(_x0)]] [[tail(active(_x0))]] = 2x0 >= 2x0 = [[tail(_x0)]] By the observations in [Kop12, Sec. 6.6], this reduction pair suffices; we may thus replace the dependency pair problem (P_17, R_1, minimal, formative) by (P_18, R_1, minimal, formative), where P_18 consists of: active#(take(s(X), cons(Y, Z))) =#> mark#(cons(Y, take(X, Z))) active#(zip(cons(X, Y), cons(Z, U))) =#> mark#(cons(pair(X, Z), zip(Y, U))) mark#(pairNs) =#> active#(pairNs) mark#(cons(X, Y)) =#> mark#(X) mark#(incr(X)) =#> active#(incr(mark(X))) mark#(s(X)) =#> mark#(X) mark#(take(X, Y)) =#> active#(take(mark(X), mark(Y))) mark#(take(X, Y)) =#> mark#(X) mark#(take(X, Y)) =#> mark#(Y) mark#(zip(X, Y)) =#> active#(zip(mark(X), mark(Y))) mark#(tail(X)) =#> mark#(X) Thus, the original system is terminating if (P_18, R_1, minimal, formative) is finite. We consider the dependency pair problem (P_18, R_1, minimal, formative). We place the elements of P in a dependency graph approximation G (see e.g. [Kop12, Thm. 7.27, 7.29], as follows: * 0 : 3 * 1 : 3 * 2 : * 3 : 2, 3, 4, 5, 6, 7, 8, 9, 10 * 4 : * 5 : 2, 3, 4, 5, 6, 7, 8, 9, 10 * 6 : 0 * 7 : 2, 3, 4, 5, 6, 7, 8, 9, 10 * 8 : 2, 3, 4, 5, 6, 7, 8, 9, 10 * 9 : 1 * 10 : 2, 3, 4, 5, 6, 7, 8, 9, 10 This graph has the following strongly connected components: P_19: active#(take(s(X), cons(Y, Z))) =#> mark#(cons(Y, take(X, Z))) active#(zip(cons(X, Y), cons(Z, U))) =#> mark#(cons(pair(X, Z), zip(Y, U))) mark#(cons(X, Y)) =#> mark#(X) mark#(s(X)) =#> mark#(X) mark#(take(X, Y)) =#> active#(take(mark(X), mark(Y))) mark#(take(X, Y)) =#> mark#(X) mark#(take(X, Y)) =#> mark#(Y) mark#(zip(X, Y)) =#> active#(zip(mark(X), mark(Y))) mark#(tail(X)) =#> mark#(X) By [Kop12, Thm. 7.31], we may replace any dependency pair problem (P_18, R_1, m, f) by (P_19, R_1, m, f). Thus, the original system is terminating if (P_19, R_1, minimal, formative) is finite. We consider the dependency pair problem (P_19, R_1, minimal, formative). The formative rules of (P_19, R_1) are R_2 ::= active(pairNs) => mark(cons(0, incr(oddNs))) active(oddNs) => mark(incr(pairNs)) active(incr(cons(X, Y))) => mark(cons(s(X), incr(Y))) active(take(s(X), cons(Y, Z))) => mark(cons(Y, take(X, Z))) active(zip(cons(X, Y), cons(Z, U))) => mark(cons(pair(X, Z), zip(Y, U))) active(repItems(cons(X, Y))) => mark(cons(X, cons(X, repItems(Y)))) mark(pairNs) => active(pairNs) mark(cons(X, Y)) => active(cons(mark(X), Y)) mark(0) => active(0) mark(incr(X)) => active(incr(mark(X))) mark(oddNs) => active(oddNs) mark(s(X)) => active(s(mark(X))) mark(take(X, Y)) => active(take(mark(X), mark(Y))) mark(nil) => active(nil) mark(zip(X, Y)) => active(zip(mark(X), mark(Y))) mark(pair(X, Y)) => active(pair(mark(X), mark(Y))) mark(tail(X)) => active(tail(mark(X))) mark(repItems(X)) => active(repItems(mark(X))) cons(mark(X), Y) => cons(X, Y) cons(X, mark(Y)) => cons(X, Y) cons(active(X), Y) => cons(X, Y) cons(X, active(Y)) => cons(X, Y) s(mark(X)) => s(X) s(active(X)) => s(X) take(mark(X), Y) => take(X, Y) take(X, mark(Y)) => take(X, Y) take(active(X), Y) => take(X, Y) take(X, active(Y)) => take(X, Y) zip(mark(X), Y) => zip(X, Y) zip(X, mark(Y)) => zip(X, Y) zip(active(X), Y) => zip(X, Y) zip(X, active(Y)) => zip(X, Y) tail(mark(X)) => tail(X) tail(active(X)) => tail(X) By [Kop12, Thm. 7.17], we may replace the dependency pair problem (P_19, R_1, minimal, formative) by (P_19, R_2, minimal, formative). Thus, the original system is terminating if (P_19, R_2, minimal, formative) is finite. We consider the dependency pair problem (P_19, R_2, minimal, formative). We will use the reduction pair processor [Kop12, Thm. 7.16]. It suffices to find a standard reduction pair [Kop12, Def. 6.69]. Thus, we must orient: active#(take(s(X), cons(Y, Z))) >? mark#(cons(Y, take(X, Z))) active#(zip(cons(X, Y), cons(Z, U))) >? mark#(cons(pair(X, Z), zip(Y, U))) mark#(cons(X, Y)) >? mark#(X) mark#(s(X)) >? mark#(X) mark#(take(X, Y)) >? active#(take(mark(X), mark(Y))) mark#(take(X, Y)) >? mark#(X) mark#(take(X, Y)) >? mark#(Y) mark#(zip(X, Y)) >? active#(zip(mark(X), mark(Y))) mark#(tail(X)) >? mark#(X) active(pairNs) >= mark(cons(0, incr(oddNs))) active(oddNs) >= mark(incr(pairNs)) active(incr(cons(X, Y))) >= mark(cons(s(X), incr(Y))) active(take(s(X), cons(Y, Z))) >= mark(cons(Y, take(X, Z))) active(zip(cons(X, Y), cons(Z, U))) >= mark(cons(pair(X, Z), zip(Y, U))) active(repItems(cons(X, Y))) >= mark(cons(X, cons(X, repItems(Y)))) mark(pairNs) >= active(pairNs) mark(cons(X, Y)) >= active(cons(mark(X), Y)) mark(0) >= active(0) mark(incr(X)) >= active(incr(mark(X))) mark(oddNs) >= active(oddNs) mark(s(X)) >= active(s(mark(X))) mark(take(X, Y)) >= active(take(mark(X), mark(Y))) mark(nil) >= active(nil) mark(zip(X, Y)) >= active(zip(mark(X), mark(Y))) mark(pair(X, Y)) >= active(pair(mark(X), mark(Y))) mark(tail(X)) >= active(tail(mark(X))) mark(repItems(X)) >= active(repItems(mark(X))) cons(mark(X), Y) >= cons(X, Y) cons(X, mark(Y)) >= cons(X, Y) cons(active(X), Y) >= cons(X, Y) cons(X, active(Y)) >= cons(X, Y) s(mark(X)) >= s(X) s(active(X)) >= s(X) take(mark(X), Y) >= take(X, Y) take(X, mark(Y)) >= take(X, Y) take(active(X), Y) >= take(X, Y) take(X, active(Y)) >= take(X, Y) zip(mark(X), Y) >= zip(X, Y) zip(X, mark(Y)) >= zip(X, Y) zip(active(X), Y) >= zip(X, Y) zip(X, active(Y)) >= zip(X, Y) tail(mark(X)) >= tail(X) tail(active(X)) >= tail(X) We orient these requirements with a polynomial interpretation in the natural numbers. The following interpretation satisfies the requirements: 0 = 0 active = \y0.y0 active# = \y0.y0 cons = \y0y1.y0 incr = \y0.1 + y0 mark = \y0.y0 mark# = \y0.2y0 nil = 0 oddNs = 1 pair = \y0y1.0 pairNs = 0 repItems = \y0.y0 s = \y0.1 + y0 tail = \y0.y0 take = \y0y1.2y0 + 2y1 zip = \y0y1.0 Using this interpretation, the requirements translate to: [[active#(take(s(_x0), cons(_x1, _x2)))]] = 2 + 2x0 + 2x1 > 2x1 = [[mark#(cons(_x1, take(_x0, _x2)))]] [[active#(zip(cons(_x0, _x1), cons(_x2, _x3)))]] = 0 >= 0 = [[mark#(cons(pair(_x0, _x2), zip(_x1, _x3)))]] [[mark#(cons(_x0, _x1))]] = 2x0 >= 2x0 = [[mark#(_x0)]] [[mark#(s(_x0))]] = 2 + 2x0 > 2x0 = [[mark#(_x0)]] [[mark#(take(_x0, _x1))]] = 4x0 + 4x1 >= 2x0 + 2x1 = [[active#(take(mark(_x0), mark(_x1)))]] [[mark#(take(_x0, _x1))]] = 4x0 + 4x1 >= 2x0 = [[mark#(_x0)]] [[mark#(take(_x0, _x1))]] = 4x0 + 4x1 >= 2x1 = [[mark#(_x1)]] [[mark#(zip(_x0, _x1))]] = 0 >= 0 = [[active#(zip(mark(_x0), mark(_x1)))]] [[mark#(tail(_x0))]] = 2x0 >= 2x0 = [[mark#(_x0)]] [[active(pairNs)]] = 0 >= 0 = [[mark(cons(0, incr(oddNs)))]] [[active(oddNs)]] = 1 >= 1 = [[mark(incr(pairNs))]] [[active(incr(cons(_x0, _x1)))]] = 1 + x0 >= 1 + x0 = [[mark(cons(s(_x0), incr(_x1)))]] [[active(take(s(_x0), cons(_x1, _x2)))]] = 2 + 2x0 + 2x1 >= x1 = [[mark(cons(_x1, take(_x0, _x2)))]] [[active(zip(cons(_x0, _x1), cons(_x2, _x3)))]] = 0 >= 0 = [[mark(cons(pair(_x0, _x2), zip(_x1, _x3)))]] [[active(repItems(cons(_x0, _x1)))]] = x0 >= x0 = [[mark(cons(_x0, cons(_x0, repItems(_x1))))]] [[mark(pairNs)]] = 0 >= 0 = [[active(pairNs)]] [[mark(cons(_x0, _x1))]] = x0 >= x0 = [[active(cons(mark(_x0), _x1))]] [[mark(0)]] = 0 >= 0 = [[active(0)]] [[mark(incr(_x0))]] = 1 + x0 >= 1 + x0 = [[active(incr(mark(_x0)))]] [[mark(oddNs)]] = 1 >= 1 = [[active(oddNs)]] [[mark(s(_x0))]] = 1 + x0 >= 1 + x0 = [[active(s(mark(_x0)))]] [[mark(take(_x0, _x1))]] = 2x0 + 2x1 >= 2x0 + 2x1 = [[active(take(mark(_x0), mark(_x1)))]] [[mark(nil)]] = 0 >= 0 = [[active(nil)]] [[mark(zip(_x0, _x1))]] = 0 >= 0 = [[active(zip(mark(_x0), mark(_x1)))]] [[mark(pair(_x0, _x1))]] = 0 >= 0 = [[active(pair(mark(_x0), mark(_x1)))]] [[mark(tail(_x0))]] = x0 >= x0 = [[active(tail(mark(_x0)))]] [[mark(repItems(_x0))]] = x0 >= x0 = [[active(repItems(mark(_x0)))]] [[cons(mark(_x0), _x1)]] = x0 >= x0 = [[cons(_x0, _x1)]] [[cons(_x0, mark(_x1))]] = x0 >= x0 = [[cons(_x0, _x1)]] [[cons(active(_x0), _x1)]] = x0 >= x0 = [[cons(_x0, _x1)]] [[cons(_x0, active(_x1))]] = x0 >= x0 = [[cons(_x0, _x1)]] [[s(mark(_x0))]] = 1 + x0 >= 1 + x0 = [[s(_x0)]] [[s(active(_x0))]] = 1 + x0 >= 1 + x0 = [[s(_x0)]] [[take(mark(_x0), _x1)]] = 2x0 + 2x1 >= 2x0 + 2x1 = [[take(_x0, _x1)]] [[take(_x0, mark(_x1))]] = 2x0 + 2x1 >= 2x0 + 2x1 = [[take(_x0, _x1)]] [[take(active(_x0), _x1)]] = 2x0 + 2x1 >= 2x0 + 2x1 = [[take(_x0, _x1)]] [[take(_x0, active(_x1))]] = 2x0 + 2x1 >= 2x0 + 2x1 = [[take(_x0, _x1)]] [[zip(mark(_x0), _x1)]] = 0 >= 0 = [[zip(_x0, _x1)]] [[zip(_x0, mark(_x1))]] = 0 >= 0 = [[zip(_x0, _x1)]] [[zip(active(_x0), _x1)]] = 0 >= 0 = [[zip(_x0, _x1)]] [[zip(_x0, active(_x1))]] = 0 >= 0 = [[zip(_x0, _x1)]] [[tail(mark(_x0))]] = x0 >= x0 = [[tail(_x0)]] [[tail(active(_x0))]] = x0 >= x0 = [[tail(_x0)]] By the observations in [Kop12, Sec. 6.6], this reduction pair suffices; we may thus replace the dependency pair problem (P_19, R_2, minimal, formative) by (P_20, R_2, minimal, formative), where P_20 consists of: active#(zip(cons(X, Y), cons(Z, U))) =#> mark#(cons(pair(X, Z), zip(Y, U))) mark#(cons(X, Y)) =#> mark#(X) mark#(take(X, Y)) =#> active#(take(mark(X), mark(Y))) mark#(take(X, Y)) =#> mark#(X) mark#(take(X, Y)) =#> mark#(Y) mark#(zip(X, Y)) =#> active#(zip(mark(X), mark(Y))) mark#(tail(X)) =#> mark#(X) Thus, the original system is terminating if (P_20, R_2, minimal, formative) is finite. We consider the dependency pair problem (P_20, R_2, minimal, formative). We place the elements of P in a dependency graph approximation G (see e.g. [Kop12, Thm. 7.27, 7.29], as follows: * 0 : 1 * 1 : 1, 2, 3, 4, 5, 6 * 2 : * 3 : 1, 2, 3, 4, 5, 6 * 4 : 1, 2, 3, 4, 5, 6 * 5 : 0 * 6 : 1, 2, 3, 4, 5, 6 This graph has the following strongly connected components: P_21: active#(zip(cons(X, Y), cons(Z, U))) =#> mark#(cons(pair(X, Z), zip(Y, U))) mark#(cons(X, Y)) =#> mark#(X) mark#(take(X, Y)) =#> mark#(X) mark#(take(X, Y)) =#> mark#(Y) mark#(zip(X, Y)) =#> active#(zip(mark(X), mark(Y))) mark#(tail(X)) =#> mark#(X) By [Kop12, Thm. 7.31], we may replace any dependency pair problem (P_20, R_2, m, f) by (P_21, R_2, m, f). Thus, the original system is terminating if (P_21, R_2, minimal, formative) is finite. We consider the dependency pair problem (P_21, R_2, minimal, formative). The formative rules of (P_21, R_2) are R_3 ::= active(pairNs) => mark(cons(0, incr(oddNs))) active(oddNs) => mark(incr(pairNs)) active(incr(cons(X, Y))) => mark(cons(s(X), incr(Y))) active(take(s(X), cons(Y, Z))) => mark(cons(Y, take(X, Z))) active(zip(cons(X, Y), cons(Z, U))) => mark(cons(pair(X, Z), zip(Y, U))) active(repItems(cons(X, Y))) => mark(cons(X, cons(X, repItems(Y)))) mark(pairNs) => active(pairNs) mark(cons(X, Y)) => active(cons(mark(X), Y)) mark(0) => active(0) mark(incr(X)) => active(incr(mark(X))) mark(oddNs) => active(oddNs) mark(s(X)) => active(s(mark(X))) mark(take(X, Y)) => active(take(mark(X), mark(Y))) mark(nil) => active(nil) mark(zip(X, Y)) => active(zip(mark(X), mark(Y))) mark(pair(X, Y)) => active(pair(mark(X), mark(Y))) mark(tail(X)) => active(tail(mark(X))) mark(repItems(X)) => active(repItems(mark(X))) cons(mark(X), Y) => cons(X, Y) cons(X, mark(Y)) => cons(X, Y) cons(active(X), Y) => cons(X, Y) cons(X, active(Y)) => cons(X, Y) take(mark(X), Y) => take(X, Y) take(X, mark(Y)) => take(X, Y) take(active(X), Y) => take(X, Y) take(X, active(Y)) => take(X, Y) zip(mark(X), Y) => zip(X, Y) zip(X, mark(Y)) => zip(X, Y) zip(active(X), Y) => zip(X, Y) zip(X, active(Y)) => zip(X, Y) tail(mark(X)) => tail(X) tail(active(X)) => tail(X) By [Kop12, Thm. 7.17], we may replace the dependency pair problem (P_21, R_2, minimal, formative) by (P_21, R_3, minimal, formative). Thus, the original system is terminating if (P_21, R_3, minimal, formative) is finite. We consider the dependency pair problem (P_21, R_3, minimal, formative). We will use the reduction pair processor [Kop12, Thm. 7.16]. It suffices to find a standard reduction pair [Kop12, Def. 6.69]. Thus, we must orient: active#(zip(cons(X, Y), cons(Z, U))) >? mark#(cons(pair(X, Z), zip(Y, U))) mark#(cons(X, Y)) >? mark#(X) mark#(take(X, Y)) >? mark#(X) mark#(take(X, Y)) >? mark#(Y) mark#(zip(X, Y)) >? active#(zip(mark(X), mark(Y))) mark#(tail(X)) >? mark#(X) active(pairNs) >= mark(cons(0, incr(oddNs))) active(oddNs) >= mark(incr(pairNs)) active(incr(cons(X, Y))) >= mark(cons(s(X), incr(Y))) active(take(s(X), cons(Y, Z))) >= mark(cons(Y, take(X, Z))) active(zip(cons(X, Y), cons(Z, U))) >= mark(cons(pair(X, Z), zip(Y, U))) active(repItems(cons(X, Y))) >= mark(cons(X, cons(X, repItems(Y)))) mark(pairNs) >= active(pairNs) mark(cons(X, Y)) >= active(cons(mark(X), Y)) mark(0) >= active(0) mark(incr(X)) >= active(incr(mark(X))) mark(oddNs) >= active(oddNs) mark(s(X)) >= active(s(mark(X))) mark(take(X, Y)) >= active(take(mark(X), mark(Y))) mark(nil) >= active(nil) mark(zip(X, Y)) >= active(zip(mark(X), mark(Y))) mark(pair(X, Y)) >= active(pair(mark(X), mark(Y))) mark(tail(X)) >= active(tail(mark(X))) mark(repItems(X)) >= active(repItems(mark(X))) cons(mark(X), Y) >= cons(X, Y) cons(X, mark(Y)) >= cons(X, Y) cons(active(X), Y) >= cons(X, Y) cons(X, active(Y)) >= cons(X, Y) take(mark(X), Y) >= take(X, Y) take(X, mark(Y)) >= take(X, Y) take(active(X), Y) >= take(X, Y) take(X, active(Y)) >= take(X, Y) zip(mark(X), Y) >= zip(X, Y) zip(X, mark(Y)) >= zip(X, Y) zip(active(X), Y) >= zip(X, Y) zip(X, active(Y)) >= zip(X, Y) tail(mark(X)) >= tail(X) tail(active(X)) >= tail(X) We orient these requirements with a polynomial interpretation in the natural numbers. We consider usable_rules with respect to the following argument filtering: active#(x_1) = active#() cons(x_1,x_2) = cons(x_1) This leaves the following ordering requirements: active#(zip(cons(X, Y), cons(Z, U))) >= mark#(cons(pair(X, Z), zip(Y, U))) mark#(cons(X, Y)) >= mark#(X) mark#(take(X, Y)) >= mark#(X) mark#(take(X, Y)) >= mark#(Y) mark#(zip(X, Y)) > active#(zip(mark(X), mark(Y))) mark#(tail(X)) >= mark#(X) cons(mark(X), Y) >= cons(X, Y) cons(X, mark(Y)) >= cons(X, Y) cons(active(X), Y) >= cons(X, Y) cons(X, active(Y)) >= cons(X, Y) The following interpretation satisfies the requirements: 0 = 0 active = \y0.2y0 active# = \y0.0 cons = \y0y1.2y0 incr = \y0.0 mark = \y0.y0 mark# = \y0.y0 nil = 0 oddNs = 0 pair = \y0y1.0 pairNs = 0 repItems = \y0.0 s = \y0.0 tail = \y0.y0 take = \y0y1.2y0 + 2y1 zip = \y0y1.1 Using this interpretation, the requirements translate to: [[active#(zip(cons(_x0, _x1), cons(_x2, _x3)))]] = 0 >= 0 = [[mark#(cons(pair(_x0, _x2), zip(_x1, _x3)))]] [[mark#(cons(_x0, _x1))]] = 2x0 >= x0 = [[mark#(_x0)]] [[mark#(take(_x0, _x1))]] = 2x0 + 2x1 >= x0 = [[mark#(_x0)]] [[mark#(take(_x0, _x1))]] = 2x0 + 2x1 >= x1 = [[mark#(_x1)]] [[mark#(zip(_x0, _x1))]] = 1 > 0 = [[active#(zip(mark(_x0), mark(_x1)))]] [[mark#(tail(_x0))]] = x0 >= x0 = [[mark#(_x0)]] [[cons(mark(_x0), _x1)]] = 2x0 >= 2x0 = [[cons(_x0, _x1)]] [[cons(_x0, mark(_x1))]] = 2x0 >= 2x0 = [[cons(_x0, _x1)]] [[cons(active(_x0), _x1)]] = 4x0 >= 2x0 = [[cons(_x0, _x1)]] [[cons(_x0, active(_x1))]] = 2x0 >= 2x0 = [[cons(_x0, _x1)]] By the observations in [Kop12, Sec. 6.6], this reduction pair suffices; we may thus replace the dependency pair problem (P_21, R_3, minimal, formative) by (P_22, R_3, minimal, formative), where P_22 consists of: active#(zip(cons(X, Y), cons(Z, U))) =#> mark#(cons(pair(X, Z), zip(Y, U))) mark#(cons(X, Y)) =#> mark#(X) mark#(take(X, Y)) =#> mark#(X) mark#(take(X, Y)) =#> mark#(Y) mark#(tail(X)) =#> mark#(X) Thus, the original system is terminating if (P_22, R_3, minimal, formative) is finite. We consider the dependency pair problem (P_22, R_3, minimal, formative). We place the elements of P in a dependency graph approximation G (see e.g. [Kop12, Thm. 7.27, 7.29], as follows: * 0 : 1 * 1 : 1, 2, 3, 4 * 2 : 1, 2, 3, 4 * 3 : 1, 2, 3, 4 * 4 : 1, 2, 3, 4 This graph has the following strongly connected components: P_23: mark#(cons(X, Y)) =#> mark#(X) mark#(take(X, Y)) =#> mark#(X) mark#(take(X, Y)) =#> mark#(Y) mark#(tail(X)) =#> mark#(X) By [Kop12, Thm. 7.31], we may replace any dependency pair problem (P_22, R_3, m, f) by (P_23, R_3, m, f). Thus, the original system is terminating if (P_23, R_3, minimal, formative) is finite. We consider the dependency pair problem (P_23, R_3, minimal, formative). We apply the subterm criterion with the following projection function: nu(mark#) = 1 Thus, we can orient the dependency pairs as follows: nu(mark#(cons(X, Y))) = cons(X, Y) |> X = nu(mark#(X)) nu(mark#(take(X, Y))) = take(X, Y) |> X = nu(mark#(X)) nu(mark#(take(X, Y))) = take(X, Y) |> Y = nu(mark#(Y)) nu(mark#(tail(X))) = tail(X) |> X = nu(mark#(X)) By [Kop12, Thm. 7.35], we may replace a dependency pair problem (P_23, R_3, minimal, f) by ({}, R_3, minimal, f). By the empty set processor [Kop12, Thm. 7.15] this problem may be immediately removed. As all dependency pair problems were succesfully simplified with sound (and complete) processors until nothing remained, we conclude termination. +++ Citations +++ [Kop12] C. Kop. Higher Order Termination. PhD Thesis, 2012. [KusIsoSakBla09] K. Kusakari, Y. Isogai, M. Sakai, and F. Blanqui. Static Dependency Pair Method Based On Strong Computability for Higher-Order Rewrite Systems. In volume 92(10) of IEICE Transactions on Information and Systems. 2007--2015, 2009.