Input TRS: 1: active(pairNs()) -> mark(cons(0(),incr(oddNs()))) 2: active(oddNs()) -> mark(incr(pairNs())) 3: active(incr(cons(X,XS))) -> mark(cons(s(X),incr(XS))) 4: active(take(0(),XS)) -> mark(nil()) 5: active(take(s(N),cons(X,XS))) -> mark(cons(X,take(N,XS))) 6: active(zip(nil(),XS)) -> mark(nil()) 7: active(zip(X,nil())) -> mark(nil()) 8: active(zip(cons(X,XS),cons(Y,YS))) -> mark(cons(pair(X,Y),zip(XS,YS))) 9: active(tail(cons(X,XS))) -> mark(XS) 10: active(repItems(nil())) -> mark(nil()) 11: active(repItems(cons(X,XS))) -> mark(cons(X,cons(X,repItems(XS)))) 12: mark(pairNs()) -> active(pairNs()) 13: mark(cons(X1,X2)) -> active(cons(mark(X1),X2)) 14: mark(0()) -> active(0()) 15: mark(incr(X)) -> active(incr(mark(X))) 16: mark(oddNs()) -> active(oddNs()) 17: mark(s(X)) -> active(s(mark(X))) 18: mark(take(X1,X2)) -> active(take(mark(X1),mark(X2))) 19: mark(nil()) -> active(nil()) 20: mark(zip(X1,X2)) -> active(zip(mark(X1),mark(X2))) 21: mark(pair(X1,X2)) -> active(pair(mark(X1),mark(X2))) 22: mark(tail(X)) -> active(tail(mark(X))) 23: mark(repItems(X)) -> active(repItems(mark(X))) 24: cons(mark(X1),X2) -> cons(X1,X2) 25: cons(X1,mark(X2)) -> cons(X1,X2) 26: cons(active(X1),X2) -> cons(X1,X2) 27: cons(X1,active(X2)) -> cons(X1,X2) 28: incr(mark(X)) -> incr(X) 29: incr(active(X)) -> incr(X) 30: s(mark(X)) -> s(X) 31: s(active(X)) -> s(X) 32: take(mark(X1),X2) -> take(X1,X2) 33: take(X1,mark(X2)) -> take(X1,X2) 34: take(active(X1),X2) -> take(X1,X2) 35: take(X1,active(X2)) -> take(X1,X2) 36: zip(mark(X1),X2) -> zip(X1,X2) 37: zip(X1,mark(X2)) -> zip(X1,X2) 38: zip(active(X1),X2) -> zip(X1,X2) 39: zip(X1,active(X2)) -> zip(X1,X2) 40: pair(mark(X1),X2) -> pair(X1,X2) 41: pair(X1,mark(X2)) -> pair(X1,X2) 42: pair(active(X1),X2) -> pair(X1,X2) 43: pair(X1,active(X2)) -> pair(X1,X2) 44: tail(mark(X)) -> tail(X) 45: tail(active(X)) -> tail(X) 46: repItems(mark(X)) -> repItems(X) 47: repItems(active(X)) -> repItems(X) Number of strict rules: 47 Direct Order(PosReal,>,Poly) ... removes: 4 10 7 9 6 repItems(x1) weight: (/ 1 16) + 2 * x1 incr(x1) weight: x1 s(x1) weight: x1 take(x1,x2) weight: (/ 1 16) + x1 + x2 pair(x1,x2) weight: x1 + x2 tail(x1) weight: (/ 3 32) + 2 * x1 0() weight: 0 nil() weight: 0 mark(x1) weight: x1 pairNs() weight: 0 oddNs() weight: 0 active(x1) weight: x1 cons(x1,x2) weight: x1 + x2 zip(x1,x2) weight: (/ 1 16) + x1 + x2 Number of strict rules: 42 Direct Order(PosReal,>,Poly) ... failed. Freezing ... failed. Dependency Pairs: #1: #active(oddNs()) -> #mark(incr(pairNs())) #2: #active(oddNs()) -> #incr(pairNs()) #3: #pair(X1,active(X2)) -> #pair(X1,X2) #4: #incr(active(X)) -> #incr(X) #5: #take(X1,active(X2)) -> #take(X1,X2) #6: #repItems(mark(X)) -> #repItems(X) #7: #pair(active(X1),X2) -> #pair(X1,X2) #8: #pair(X1,mark(X2)) -> #pair(X1,X2) #9: #zip(X1,mark(X2)) -> #zip(X1,X2) #10: #repItems(active(X)) -> #repItems(X) #11: #zip(active(X1),X2) -> #zip(X1,X2) #12: #pair(mark(X1),X2) -> #pair(X1,X2) #13: #mark(cons(X1,X2)) -> #active(cons(mark(X1),X2)) #14: #mark(cons(X1,X2)) -> #cons(mark(X1),X2) #15: #mark(cons(X1,X2)) -> #mark(X1) #16: #active(repItems(cons(X,XS))) -> #mark(cons(X,cons(X,repItems(XS)))) #17: #active(repItems(cons(X,XS))) -> #cons(X,cons(X,repItems(XS))) #18: #active(repItems(cons(X,XS))) -> #cons(X,repItems(XS)) #19: #active(repItems(cons(X,XS))) -> #repItems(XS) #20: #cons(mark(X1),X2) -> #cons(X1,X2) #21: #mark(repItems(X)) -> #active(repItems(mark(X))) #22: #mark(repItems(X)) -> #repItems(mark(X)) #23: #mark(repItems(X)) -> #mark(X) #24: #tail(active(X)) -> #tail(X) #25: #mark(pairNs()) -> #active(pairNs()) #26: #s(active(X)) -> #s(X) #27: #mark(0()) -> #active(0()) #28: #s(mark(X)) -> #s(X) #29: #cons(X1,mark(X2)) -> #cons(X1,X2) #30: #mark(zip(X1,X2)) -> #active(zip(mark(X1),mark(X2))) #31: #mark(zip(X1,X2)) -> #zip(mark(X1),mark(X2)) #32: #mark(zip(X1,X2)) -> #mark(X1) #33: #mark(zip(X1,X2)) -> #mark(X2) #34: #zip(X1,active(X2)) -> #zip(X1,X2) #35: #take(X1,mark(X2)) -> #take(X1,X2) #36: #active(take(s(N),cons(X,XS))) -> #mark(cons(X,take(N,XS))) #37: #active(take(s(N),cons(X,XS))) -> #cons(X,take(N,XS)) #38: #active(take(s(N),cons(X,XS))) -> #take(N,XS) #39: #tail(mark(X)) -> #tail(X) #40: #incr(mark(X)) -> #incr(X) #41: #mark(tail(X)) -> #active(tail(mark(X))) #42: #mark(tail(X)) -> #tail(mark(X)) #43: #mark(tail(X)) -> #mark(X) #44: #take(active(X1),X2) -> #take(X1,X2) #45: #cons(X1,active(X2)) -> #cons(X1,X2) #46: #mark(s(X)) -> #active(s(mark(X))) #47: #mark(s(X)) -> #s(mark(X)) #48: #mark(s(X)) -> #mark(X) #49: #take(mark(X1),X2) -> #take(X1,X2) #50: #mark(nil()) -> #active(nil()) #51: #cons(active(X1),X2) -> #cons(X1,X2) #52: #zip(mark(X1),X2) -> #zip(X1,X2) #53: #mark(pair(X1,X2)) -> #active(pair(mark(X1),mark(X2))) #54: #mark(pair(X1,X2)) -> #pair(mark(X1),mark(X2)) #55: #mark(pair(X1,X2)) -> #mark(X1) #56: #mark(pair(X1,X2)) -> #mark(X2) #57: #mark(oddNs()) -> #active(oddNs()) #58: #active(incr(cons(X,XS))) -> #mark(cons(s(X),incr(XS))) #59: #active(incr(cons(X,XS))) -> #cons(s(X),incr(XS)) #60: #active(incr(cons(X,XS))) -> #s(X) #61: #active(incr(cons(X,XS))) -> #incr(XS) #62: #active(pairNs()) -> #mark(cons(0(),incr(oddNs()))) #63: #active(pairNs()) -> #cons(0(),incr(oddNs())) #64: #active(pairNs()) -> #incr(oddNs()) #65: #active(zip(cons(X,XS),cons(Y,YS))) -> #mark(cons(pair(X,Y),zip(XS,YS))) #66: #active(zip(cons(X,XS),cons(Y,YS))) -> #cons(pair(X,Y),zip(XS,YS)) #67: #active(zip(cons(X,XS),cons(Y,YS))) -> #pair(X,Y) #68: #active(zip(cons(X,XS),cons(Y,YS))) -> #zip(XS,YS) #69: #mark(incr(X)) -> #active(incr(mark(X))) #70: #mark(incr(X)) -> #incr(mark(X)) #71: #mark(incr(X)) -> #mark(X) #72: #mark(take(X1,X2)) -> #active(take(mark(X1),mark(X2))) #73: #mark(take(X1,X2)) -> #take(mark(X1),mark(X2)) #74: #mark(take(X1,X2)) -> #mark(X1) #75: #mark(take(X1,X2)) -> #mark(X2) Number of SCCs: 9, DPs: 47, edges: 280 SCC { #4 #40 } Removing DPs: Order(PosReal,>,Sum)... succeeded. repItems(x1) weight: 0 incr(x1) weight: 0 #cons(x1,x2) weight: 0 s(x1) weight: 0 #take(x1,x2) weight: 0 take(x1,x2) weight: 0 pair(x1,x2) weight: 0 #zip(x1,x2) weight: 0 tail(x1) weight: 0 #mark(x1) weight: 0 0() weight: 0 #s(x1) weight: 0 nil() weight: 0 #tail(x1) weight: 0 mark(x1) weight: (/ 1 2) + x1 #incr(x1) weight: x1 pairNs() weight: 0 oddNs() weight: 0 #repItems(x1) weight: 0 active(x1) weight: (/ 1 2) + x1 cons(x1,x2) weight: 0 #active(x1) weight: 0 #pair(x1,x2) weight: 0 zip(x1,x2) weight: 0 Usable rules: { } Removed DPs: #4 #40 Number of SCCs: 8, DPs: 45, edges: 276 SCC { #26 #28 } Removing DPs: Order(PosReal,>,Sum)... succeeded. repItems(x1) weight: 0 incr(x1) weight: 0 #cons(x1,x2) weight: 0 s(x1) weight: 0 #take(x1,x2) weight: 0 take(x1,x2) weight: 0 pair(x1,x2) weight: 0 #zip(x1,x2) weight: 0 tail(x1) weight: 0 #mark(x1) weight: 0 0() weight: 0 #s(x1) weight: x1 nil() weight: 0 #tail(x1) weight: 0 mark(x1) weight: (/ 1 2) + x1 #incr(x1) weight: 0 pairNs() weight: 0 oddNs() weight: 0 #repItems(x1) weight: 0 active(x1) weight: (/ 1 2) + x1 cons(x1,x2) weight: 0 #active(x1) weight: 0 #pair(x1,x2) weight: 0 zip(x1,x2) weight: 0 Usable rules: { } Removed DPs: #26 #28 Number of SCCs: 7, DPs: 43, edges: 272 SCC { #24 #39 } Removing DPs: Order(PosReal,>,Sum)... succeeded. repItems(x1) weight: 0 incr(x1) weight: 0 #cons(x1,x2) weight: 0 s(x1) weight: 0 #take(x1,x2) weight: 0 take(x1,x2) weight: 0 pair(x1,x2) weight: 0 #zip(x1,x2) weight: 0 tail(x1) weight: 0 #mark(x1) weight: 0 0() weight: 0 #s(x1) weight: 0 nil() weight: 0 #tail(x1) weight: x1 mark(x1) weight: (/ 1 2) + x1 #incr(x1) weight: 0 pairNs() weight: 0 oddNs() weight: 0 #repItems(x1) weight: 0 active(x1) weight: (/ 1 2) + x1 cons(x1,x2) weight: 0 #active(x1) weight: 0 #pair(x1,x2) weight: 0 zip(x1,x2) weight: 0 Usable rules: { } Removed DPs: #24 #39 Number of SCCs: 6, DPs: 41, edges: 268 SCC { #6 #10 } Removing DPs: Order(PosReal,>,Sum)... succeeded. repItems(x1) weight: 0 incr(x1) weight: 0 #cons(x1,x2) weight: 0 s(x1) weight: 0 #take(x1,x2) weight: 0 take(x1,x2) weight: 0 pair(x1,x2) weight: 0 #zip(x1,x2) weight: 0 tail(x1) weight: 0 #mark(x1) weight: 0 0() weight: 0 #s(x1) weight: 0 nil() weight: 0 #tail(x1) weight: 0 mark(x1) weight: (/ 1 2) + x1 #incr(x1) weight: 0 pairNs() weight: 0 oddNs() weight: 0 #repItems(x1) weight: x1 active(x1) weight: (/ 1 2) + x1 cons(x1,x2) weight: 0 #active(x1) weight: 0 #pair(x1,x2) weight: 0 zip(x1,x2) weight: 0 Usable rules: { } Removed DPs: #6 #10 Number of SCCs: 5, DPs: 39, edges: 264 SCC { #20 #29 #45 #51 } Removing DPs: Order(PosReal,>,Sum)... succeeded. repItems(x1) weight: 0 incr(x1) weight: 0 #cons(x1,x2) weight: x2 s(x1) weight: 0 #take(x1,x2) weight: 0 take(x1,x2) weight: 0 pair(x1,x2) weight: 0 #zip(x1,x2) weight: 0 tail(x1) weight: 0 #mark(x1) weight: 0 0() weight: 0 #s(x1) weight: 0 nil() weight: 0 #tail(x1) weight: 0 mark(x1) weight: (/ 1 2) + x1 #incr(x1) weight: 0 pairNs() weight: 0 oddNs() weight: 0 #repItems(x1) weight: 0 active(x1) weight: (/ 1 2) + x1 cons(x1,x2) weight: 0 #active(x1) weight: 0 #pair(x1,x2) weight: 0 zip(x1,x2) weight: 0 Usable rules: { } Removed DPs: #29 #45 Number of SCCs: 5, DPs: 37, edges: 252 SCC { #20 #51 } Removing DPs: Order(PosReal,>,Sum)... succeeded. repItems(x1) weight: 0 incr(x1) weight: 0 #cons(x1,x2) weight: x1 s(x1) weight: 0 #take(x1,x2) weight: 0 take(x1,x2) weight: 0 pair(x1,x2) weight: 0 #zip(x1,x2) weight: 0 tail(x1) weight: 0 #mark(x1) weight: 0 0() weight: 0 #s(x1) weight: 0 nil() weight: 0 #tail(x1) weight: 0 mark(x1) weight: (/ 1 2) + x1 #incr(x1) weight: 0 pairNs() weight: 0 oddNs() weight: 0 #repItems(x1) weight: 0 active(x1) weight: (/ 1 2) + x1 cons(x1,x2) weight: 0 #active(x1) weight: 0 #pair(x1,x2) weight: 0 zip(x1,x2) weight: 0 Usable rules: { } Removed DPs: #20 #51 Number of SCCs: 4, DPs: 35, edges: 248 SCC { #5 #35 #44 #49 } Removing DPs: Order(PosReal,>,Sum)... succeeded. repItems(x1) weight: 0 incr(x1) weight: 0 #cons(x1,x2) weight: 0 s(x1) weight: 0 #take(x1,x2) weight: x1 take(x1,x2) weight: 0 pair(x1,x2) weight: 0 #zip(x1,x2) weight: 0 tail(x1) weight: 0 #mark(x1) weight: 0 0() weight: 0 #s(x1) weight: 0 nil() weight: 0 #tail(x1) weight: 0 mark(x1) weight: (/ 1 2) + x1 #incr(x1) weight: 0 pairNs() weight: 0 oddNs() weight: 0 #repItems(x1) weight: 0 active(x1) weight: (/ 1 2) + x1 cons(x1,x2) weight: 0 #active(x1) weight: 0 #pair(x1,x2) weight: 0 zip(x1,x2) weight: 0 Usable rules: { } Removed DPs: #44 #49 Number of SCCs: 5, DPs: 33, edges: 236 SCC { #5 #35 } Removing DPs: Order(PosReal,>,Sum)... succeeded. repItems(x1) weight: 0 incr(x1) weight: 0 #cons(x1,x2) weight: 0 s(x1) weight: 0 #take(x1,x2) weight: x2 take(x1,x2) weight: 0 pair(x1,x2) weight: 0 #zip(x1,x2) weight: 0 tail(x1) weight: 0 #mark(x1) weight: 0 0() weight: 0 #s(x1) weight: 0 nil() weight: 0 #tail(x1) weight: 0 mark(x1) weight: (/ 1 2) + x1 #incr(x1) weight: 0 pairNs() weight: 0 oddNs() weight: 0 #repItems(x1) weight: 0 active(x1) weight: (/ 1 2) + x1 cons(x1,x2) weight: 0 #active(x1) weight: 0 #pair(x1,x2) weight: 0 zip(x1,x2) weight: 0 Usable rules: { } Removed DPs: #5 #35 Number of SCCs: 4, DPs: 31, edges: 232 SCC { #3 #7 #8 #12 } Removing DPs: Order(PosReal,>,Sum)... succeeded. repItems(x1) weight: 0 incr(x1) weight: 0 #cons(x1,x2) weight: 0 s(x1) weight: 0 #take(x1,x2) weight: 0 take(x1,x2) weight: 0 pair(x1,x2) weight: 0 #zip(x1,x2) weight: 0 tail(x1) weight: 0 #mark(x1) weight: 0 0() weight: 0 #s(x1) weight: 0 nil() weight: 0 #tail(x1) weight: 0 mark(x1) weight: (/ 1 2) + x1 #incr(x1) weight: 0 pairNs() weight: 0 oddNs() weight: 0 #repItems(x1) weight: 0 active(x1) weight: (/ 1 2) + x1 cons(x1,x2) weight: 0 #active(x1) weight: 0 #pair(x1,x2) weight: x2 zip(x1,x2) weight: 0 Usable rules: { } Removed DPs: #3 #8 Number of SCCs: 5, DPs: 29, edges: 220 SCC { #7 #12 } Removing DPs: Order(PosReal,>,Sum)... succeeded. repItems(x1) weight: 0 incr(x1) weight: 0 #cons(x1,x2) weight: 0 s(x1) weight: 0 #take(x1,x2) weight: 0 take(x1,x2) weight: 0 pair(x1,x2) weight: 0 #zip(x1,x2) weight: 0 tail(x1) weight: 0 #mark(x1) weight: 0 0() weight: 0 #s(x1) weight: 0 nil() weight: 0 #tail(x1) weight: 0 mark(x1) weight: (/ 1 2) + x1 #incr(x1) weight: 0 pairNs() weight: 0 oddNs() weight: 0 #repItems(x1) weight: 0 active(x1) weight: (/ 1 2) + x1 cons(x1,x2) weight: 0 #active(x1) weight: 0 #pair(x1,x2) weight: x1 zip(x1,x2) weight: 0 Usable rules: { } Removed DPs: #7 #12 Number of SCCs: 4, DPs: 27, edges: 216 SCC { #9 #11 #34 #52 } Removing DPs: Order(PosReal,>,Sum)... succeeded. repItems(x1) weight: 0 incr(x1) weight: 0 #cons(x1,x2) weight: 0 s(x1) weight: 0 #take(x1,x2) weight: 0 take(x1,x2) weight: 0 pair(x1,x2) weight: 0 #zip(x1,x2) weight: x1 tail(x1) weight: 0 #mark(x1) weight: 0 0() weight: 0 #s(x1) weight: 0 nil() weight: 0 #tail(x1) weight: 0 mark(x1) weight: (/ 1 2) + x1 #incr(x1) weight: 0 pairNs() weight: 0 oddNs() weight: 0 #repItems(x1) weight: 0 active(x1) weight: (/ 1 2) + x1 cons(x1,x2) weight: 0 #active(x1) weight: 0 #pair(x1,x2) weight: 0 zip(x1,x2) weight: 0 Usable rules: { } Removed DPs: #11 #52 Number of SCCs: 5, DPs: 25, edges: 204 SCC { #9 #34 } Removing DPs: Order(PosReal,>,Sum)... succeeded. repItems(x1) weight: 0 incr(x1) weight: 0 #cons(x1,x2) weight: 0 s(x1) weight: 0 #take(x1,x2) weight: 0 take(x1,x2) weight: 0 pair(x1,x2) weight: 0 #zip(x1,x2) weight: x2 tail(x1) weight: 0 #mark(x1) weight: 0 0() weight: 0 #s(x1) weight: 0 nil() weight: 0 #tail(x1) weight: 0 mark(x1) weight: (/ 1 2) + x1 #incr(x1) weight: 0 pairNs() weight: 0 oddNs() weight: 0 #repItems(x1) weight: 0 active(x1) weight: (/ 1 2) + x1 cons(x1,x2) weight: 0 #active(x1) weight: 0 #pair(x1,x2) weight: 0 zip(x1,x2) weight: 0 Usable rules: { } Removed DPs: #9 #34 Number of SCCs: 4, DPs: 23, edges: 200 SCC { #1 #15 #16 #21 #23 #25 #30 #32 #33 #36 #43 #48 #55..58 #62 #65 #69 #71 #72 #74 #75 } Removing DPs: Order(PosReal,>,Sum)... succeeded. repItems(x1) weight: (/ 1 4) + x1 incr(x1) weight: x1 #cons(x1,x2) weight: 0 s(x1) weight: x1 #take(x1,x2) weight: 0 take(x1,x2) weight: (/ 1 4) + x1 + x2 pair(x1,x2) weight: (/ 1 4) + x1 + x2 #zip(x1,x2) weight: 0 tail(x1) weight: (/ 1 4) + x1 #mark(x1) weight: x1 0() weight: 0 #s(x1) weight: 0 nil() weight: 0 #tail(x1) weight: 0 mark(x1) weight: x1 #incr(x1) weight: 0 pairNs() weight: 0 oddNs() weight: 0 #repItems(x1) weight: 0 active(x1) weight: x1 cons(x1,x2) weight: x1 #active(x1) weight: x1 #pair(x1,x2) weight: 0 zip(x1,x2) weight: (/ 1 2) + x1 + x2 Usable rules: { 1..3 5 8 11..47 } Removed DPs: #16 #23 #32 #33 #36 #43 #55 #56 #65 #74 #75 Number of SCCs: 5, DPs: 9, edges: 25 SCC { #1 #15 #25 #48 #57 #58 #62 #69 #71 } Removing DPs: Order(PosReal,>,Sum)... Order(PosReal,>,Max)... succeeded. repItems(x1) weight: (/ 1 16) + x1 incr(x1) weight: (/ 3 8) + x1 #cons(x1,x2) weight: 0 s(x1) weight: (/ 1 16) + x1 #take(x1,x2) weight: 0 take(x1,x2) weight: max{(/ 1 8) + x2, (/ 1 16) + x1} pair(x1,x2) weight: max{(/ 1 16) + x2, (/ 1 8) + x1} #zip(x1,x2) weight: 0 tail(x1) weight: (/ 1 16) #mark(x1) weight: (/ 1 8) + x1 0() weight: (/ 1 16) #s(x1) weight: 0 nil() weight: (/ 1 16) #tail(x1) weight: 0 mark(x1) weight: (/ 1 16) + x1 #incr(x1) weight: 0 pairNs() weight: (/ 3 8) oddNs() weight: (/ 15 16) #repItems(x1) weight: 0 active(x1) weight: x1 cons(x1,x2) weight: max{0, (/ 1 8) + x1} #active(x1) weight: x1 #pair(x1,x2) weight: 0 zip(x1,x2) weight: max{(/ 1 8) + x2, (/ 3 16) + x1} Usable rules: { 1..3 5 8 11..47 } Removed DPs: #1 #15 #25 #48 #57 #58 #62 #69 #71 Number of SCCs: 4, DPs: 0, edges: 0 YES