Input TRS: 1: a__natsFrom(N) -> cons(mark(N),natsFrom(s(N))) 2: a__fst(pair(XS,YS)) -> mark(XS) 3: a__snd(pair(XS,YS)) -> mark(YS) 4: a__splitAt(0(),XS) -> pair(nil(),mark(XS)) 5: a__splitAt(s(N),cons(X,XS)) -> a__u(a__splitAt(mark(N),mark(XS)),N,X,XS) 6: a__u(pair(YS,ZS),N,X,XS) -> pair(cons(mark(X),YS),mark(ZS)) 7: a__head(cons(N,XS)) -> mark(N) 8: a__tail(cons(N,XS)) -> mark(XS) 9: a__sel(N,XS) -> a__head(a__afterNth(mark(N),mark(XS))) 10: a__take(N,XS) -> a__fst(a__splitAt(mark(N),mark(XS))) 11: a__afterNth(N,XS) -> a__snd(a__splitAt(mark(N),mark(XS))) 12: mark(natsFrom(X)) -> a__natsFrom(mark(X)) 13: mark(fst(X)) -> a__fst(mark(X)) 14: mark(snd(X)) -> a__snd(mark(X)) 15: mark(splitAt(X1,X2)) -> a__splitAt(mark(X1),mark(X2)) 16: mark(u(X1,X2,X3,X4)) -> a__u(mark(X1),X2,X3,X4) 17: mark(head(X)) -> a__head(mark(X)) 18: mark(tail(X)) -> a__tail(mark(X)) 19: mark(sel(X1,X2)) -> a__sel(mark(X1),mark(X2)) 20: mark(afterNth(X1,X2)) -> a__afterNth(mark(X1),mark(X2)) 21: mark(take(X1,X2)) -> a__take(mark(X1),mark(X2)) 22: mark(cons(X1,X2)) -> cons(mark(X1),X2) 23: mark(s(X)) -> s(mark(X)) 24: mark(pair(X1,X2)) -> pair(mark(X1),mark(X2)) 25: mark(0()) -> 0() 26: mark(nil()) -> nil() 27: a__natsFrom(X) -> natsFrom(X) 28: a__fst(X) -> fst(X) 29: a__snd(X) -> snd(X) 30: a__splitAt(X1,X2) -> splitAt(X1,X2) 31: a__u(X1,X2,X3,X4) -> u(X1,X2,X3,X4) 32: a__head(X) -> head(X) 33: a__tail(X) -> tail(X) 34: a__sel(X1,X2) -> sel(X1,X2) 35: a__afterNth(X1,X2) -> afterNth(X1,X2) 36: a__take(X1,X2) -> take(X1,X2) Number of strict rules: 36 Direct Order(PosReal,>,Poly) ... failed. Freezing ... failed. Dependency Pairs: #1: #a__fst(pair(XS,YS)) -> #mark(XS) #2: #a__u(pair(YS,ZS),N,X,XS) -> #mark(X) #3: #a__u(pair(YS,ZS),N,X,XS) -> #mark(ZS) #4: #mark(fst(X)) -> #a__fst(mark(X)) #5: #mark(fst(X)) -> #mark(X) #6: #a__sel(N,XS) -> #a__head(a__afterNth(mark(N),mark(XS))) #7: #a__sel(N,XS) -> #a__afterNth(mark(N),mark(XS)) #8: #a__sel(N,XS) -> #mark(N) #9: #a__sel(N,XS) -> #mark(XS) #10: #a__afterNth(N,XS) -> #a__snd(a__splitAt(mark(N),mark(XS))) #11: #a__afterNth(N,XS) -> #a__splitAt(mark(N),mark(XS)) #12: #a__afterNth(N,XS) -> #mark(N) #13: #a__afterNth(N,XS) -> #mark(XS) #14: #mark(pair(X1,X2)) -> #mark(X1) #15: #mark(pair(X1,X2)) -> #mark(X2) #16: #mark(s(X)) -> #mark(X) #17: #mark(natsFrom(X)) -> #a__natsFrom(mark(X)) #18: #mark(natsFrom(X)) -> #mark(X) #19: #mark(snd(X)) -> #a__snd(mark(X)) #20: #mark(snd(X)) -> #mark(X) #21: #mark(afterNth(X1,X2)) -> #a__afterNth(mark(X1),mark(X2)) #22: #mark(afterNth(X1,X2)) -> #mark(X1) #23: #mark(afterNth(X1,X2)) -> #mark(X2) #24: #a__head(cons(N,XS)) -> #mark(N) #25: #a__take(N,XS) -> #a__fst(a__splitAt(mark(N),mark(XS))) #26: #a__take(N,XS) -> #a__splitAt(mark(N),mark(XS)) #27: #a__take(N,XS) -> #mark(N) #28: #a__take(N,XS) -> #mark(XS) #29: #a__splitAt(s(N),cons(X,XS)) -> #a__u(a__splitAt(mark(N),mark(XS)),N,X,XS) #30: #a__splitAt(s(N),cons(X,XS)) -> #a__splitAt(mark(N),mark(XS)) #31: #a__splitAt(s(N),cons(X,XS)) -> #mark(N) #32: #a__splitAt(s(N),cons(X,XS)) -> #mark(XS) #33: #mark(cons(X1,X2)) -> #mark(X1) #34: #mark(head(X)) -> #a__head(mark(X)) #35: #mark(head(X)) -> #mark(X) #36: #mark(sel(X1,X2)) -> #a__sel(mark(X1),mark(X2)) #37: #mark(sel(X1,X2)) -> #mark(X1) #38: #mark(sel(X1,X2)) -> #mark(X2) #39: #mark(take(X1,X2)) -> #a__take(mark(X1),mark(X2)) #40: #mark(take(X1,X2)) -> #mark(X1) #41: #mark(take(X1,X2)) -> #mark(X2) #42: #mark(u(X1,X2,X3,X4)) -> #a__u(mark(X1),X2,X3,X4) #43: #mark(u(X1,X2,X3,X4)) -> #mark(X1) #44: #a__snd(pair(XS,YS)) -> #mark(YS) #45: #a__natsFrom(N) -> #mark(N) #46: #a__tail(cons(N,XS)) -> #mark(XS) #47: #mark(splitAt(X1,X2)) -> #a__splitAt(mark(X1),mark(X2)) #48: #mark(splitAt(X1,X2)) -> #mark(X1) #49: #mark(splitAt(X1,X2)) -> #mark(X2) #50: #a__splitAt(0(),XS) -> #mark(XS) #51: #mark(tail(X)) -> #a__tail(mark(X)) #52: #mark(tail(X)) -> #mark(X) Number of SCCs: 1, DPs: 52, edges: 1000 SCC { #1..52 } Removing DPs: Order(PosReal,>,Sum)... Order(PosReal,>,Max)... succeeded. s(x1) weight: x1 #a__head(x1) weight: x1 #a__natsFrom(x1) weight: (/ 1 4) + x1 #a__snd(x1) weight: (/ 1 8) + x1 a__afterNth(x1,x2) weight: max{(/ 31843 2) + x2, (/ 127371 8) + x1} u(x1,x2,x3,x4) weight: max{0, (/ 1 4) + x3, (/ 1 4) + x2, x1} take(x1,x2) weight: max{(/ 31843 2) + x2, (/ 127373 8) + x1} pair(x1,x2) weight: max{x2, x1} fst(x1) weight: (/ 1 8) + x1 natsFrom(x1) weight: (/ 1 4) + x1 a__snd(x1) weight: (/ 1 8) + x1 splitAt(x1,x2) weight: max{(/ 127371 8) + x2, (/ 63685 4) + x1} #a__take(x1,x2) weight: max{(/ 31843 2) + x2, (/ 127371 8) + x1} a__natsFrom(x1) weight: (/ 1 4) + x1 a__fst(x1) weight: (/ 1 8) + x1 tail(x1) weight: (/ 1 8) + x1 #mark(x1) weight: (/ 1 8) + x1 0() weight: (/ 1 8) a__u(x1,x2,x3,x4) weight: max{0, (/ 1 4) + x3, (/ 1 4) + x2, x1} sel(x1,x2) weight: max{(/ 127373 8) + x2, (/ 63687 4) + x1} afterNth(x1,x2) weight: max{(/ 31843 2) + x2, (/ 127371 8) + x1} nil() weight: (/ 1 8) a__splitAt(x1,x2) weight: max{(/ 127371 8) + x2, (/ 63685 4) + x1} #a__sel(x1,x2) weight: max{(/ 63687 4) + x2, (/ 127375 8) + x1} mark(x1) weight: x1 a__sel(x1,x2) weight: max{(/ 127373 8) + x2, (/ 63687 4) + x1} head(x1) weight: (/ 1 8) + x1 #a__afterNth(x1,x2) weight: max{(/ 127373 8) + x2, (/ 127371 8) + x1} #a__splitAt(x1,x2) weight: max{(/ 31843 2) + x2, (/ 127371 8) + x1} cons(x1,x2) weight: max{x2, (/ 1 4) + x1} snd(x1) weight: (/ 1 8) + x1 #a__u(x1,x2,x3,x4) weight: max{0, (/ 1 8) + x3, (/ 1 8) + x1} a__take(x1,x2) weight: max{(/ 31843 2) + x2, (/ 127373 8) + x1} #a__fst(x1) weight: (/ 1 8) + x1 a__tail(x1) weight: (/ 1 8) + x1 #a__tail(x1) weight: (/ 1 8) + x1 a__head(x1) weight: (/ 1 8) + x1 Usable rules: { 1..36 } Removed DPs: #4..9 #12 #13 #17..20 #22..24 #27 #28 #31..35 #37..41 #45 #48..52 Number of SCCs: 1, DPs: 14, edges: 62 SCC { #2 #3 #10 #11 #14..16 #21 #29 #30 #42..44 #47 } Removing DPs: Order(PosReal,>,Sum)... Order(PosReal,>,Max)... succeeded. s(x1) weight: x1 #a__head(x1) weight: x1 #a__natsFrom(x1) weight: (/ 1 8) + x1 #a__snd(x1) weight: (/ 3 16) + x1 a__afterNth(x1,x2) weight: max{(/ 3 8) + x2, (/ 1 4) + x1} u(x1,x2,x3,x4) weight: max{0, (/ 1 4) + x3, (/ 1 16) + x2, x1} take(x1,x2) weight: max{(/ 63685 4) + x2, (/ 254741 16) + x1} pair(x1,x2) weight: max{x2, x1} fst(x1) weight: (/ 1 16) + x1 natsFrom(x1) weight: (/ 1 16) + x1 a__snd(x1) weight: (/ 3 16) + x1 splitAt(x1,x2) weight: max{(/ 3 16) + x2, (/ 1 16) + x1} #a__take(x1,x2) weight: max{(/ 63685 4) + x2, (/ 254739 16) + x1} a__natsFrom(x1) weight: (/ 1 16) + x1 a__fst(x1) weight: (/ 1 16) + x1 tail(x1) weight: (/ 1 16) + x1 #mark(x1) weight: (/ 1 16) + x1 0() weight: (/ 1 16) a__u(x1,x2,x3,x4) weight: max{0, (/ 1 4) + x3, (/ 1 16) + x2, x1} sel(x1,x2) weight: max{(/ 7 16) + x2, (/ 1 2) + x1} afterNth(x1,x2) weight: max{(/ 3 8) + x2, (/ 1 4) + x1} nil() weight: (/ 1 16) a__splitAt(x1,x2) weight: max{(/ 3 16) + x2, (/ 1 16) + x1} #a__sel(x1,x2) weight: max{(/ 127371 8) + x2, (/ 254743 16) + x1} mark(x1) weight: x1 a__sel(x1,x2) weight: max{(/ 7 16) + x2, (/ 1 2) + x1} head(x1) weight: (/ 1 16) + x1 #a__afterNth(x1,x2) weight: max{(/ 7 16) + x2, (/ 5 16) + x1} #a__splitAt(x1,x2) weight: max{(/ 1 4) + x2, (/ 1 8) + x1} cons(x1,x2) weight: max{x2, (/ 1 16) + x1} snd(x1) weight: (/ 3 16) + x1 #a__u(x1,x2,x3,x4) weight: max{0, (/ 5 16) + x3, (/ 1 16) + x1} a__take(x1,x2) weight: max{(/ 63685 4) + x2, (/ 254741 16) + x1} #a__fst(x1) weight: (/ 1 16) + x1 a__tail(x1) weight: (/ 1 16) + x1 #a__tail(x1) weight: (/ 1 16) + x1 a__head(x1) weight: (/ 1 16) + x1 Usable rules: { 1..36 } Removed DPs: #2 #10 #11 #44 Number of SCCs: 1, DPs: 9, edges: 36 SCC { #3 #14..16 #29 #30 #42 #43 #47 } Removing DPs: Order(PosReal,>,Sum)... Order(PosReal,>,Max)... succeeded. s(x1) weight: x1 #a__head(x1) weight: x1 #a__natsFrom(x1) weight: (/ 1 4) + x1 #a__snd(x1) weight: (/ 3 8) + x1 a__afterNth(x1,x2) weight: max{2961 + x2, (/ 23687 8) + x1} u(x1,x2,x3,x4) weight: max{0, 2961 + x3, (/ 11843 4) + x2, x1} take(x1,x2) weight: max{(/ 31843 2) + x2, (/ 127373 8) + x1} pair(x1,x2) weight: max{(/ 11843 4) + x2, x1} fst(x1) weight: (/ 1 8) + x1 natsFrom(x1) weight: (/ 1 8) + x1 a__snd(x1) weight: (/ 1 8) + x1 splitAt(x1,x2) weight: max{(/ 23687 8) + x2, (/ 11843 4) + x1} #a__take(x1,x2) weight: max{(/ 31843 2) + x2, (/ 127371 8) + x1} a__natsFrom(x1) weight: (/ 1 8) + x1 a__fst(x1) weight: (/ 1 8) + x1 tail(x1) weight: (/ 1 8) + x1 #mark(x1) weight: (/ 3 4) + x1 0() weight: (/ 1 8) a__u(x1,x2,x3,x4) weight: max{0, 2961 + x3, (/ 11843 4) + x2, x1} sel(x1,x2) weight: max{(/ 23689 8) + x2, (/ 11845 4) + x1} afterNth(x1,x2) weight: max{2961 + x2, (/ 23687 8) + x1} nil() weight: (/ 1 8) a__splitAt(x1,x2) weight: max{(/ 23687 8) + x2, (/ 11843 4) + x1} #a__sel(x1,x2) weight: max{(/ 63687 4) + x2, (/ 127375 8) + x1} mark(x1) weight: x1 a__sel(x1,x2) weight: max{(/ 23689 8) + x2, (/ 11845 4) + x1} head(x1) weight: (/ 1 8) + x1 #a__afterNth(x1,x2) weight: max{(/ 7 8) + x2, (/ 5 8) + x1} #a__splitAt(x1,x2) weight: max{(/ 23689 8) + x2, (/ 23691 8) + x1} cons(x1,x2) weight: max{x2, (/ 1 8) + x1} snd(x1) weight: (/ 1 8) + x1 #a__u(x1,x2,x3,x4) weight: max{0, (/ 1 8) + x1} a__take(x1,x2) weight: max{(/ 31843 2) + x2, (/ 127373 8) + x1} #a__fst(x1) weight: (/ 1 8) + x1 a__tail(x1) weight: (/ 1 8) + x1 #a__tail(x1) weight: (/ 1 8) + x1 a__head(x1) weight: (/ 1 8) + x1 Usable rules: { 1..36 } Removed DPs: #3 #15 #29 #42 #47 Number of SCCs: 2, DPs: 4, edges: 10 SCC { #30 } Removing DPs: Order(PosReal,>,Sum)... Order(PosReal,>,Max)... QLPOpS... Order(PosReal,>,MaxSum)... succeeded. s(x1) weight: max{0, (/ 3 8) + x1} #a__head(x1) weight: 0 #a__natsFrom(x1) weight: 0 #a__snd(x1) weight: 0 a__afterNth(x1,x2) weight: max{0, (- (/ 1 8)) + x2 + x1} u(x1,x2,x3,x4) weight: max{0, x1, (- (/ 1 4)) + x2, (/ 1 16) + x3} take(x1,x2) weight: max{0, (/ 1 2) + x2 + x1} pair(x1,x2) weight: max{0, (- (/ 3 16)) + x1, (/ 1 8) + x2} fst(x1) weight: max{0, (/ 1 2) + x1} natsFrom(x1) weight: max{0, (/ 7 16) + x1} a__snd(x1) weight: max{0, (- (/ 1 16)) + x1} splitAt(x1,x2) weight: max{0, (- (/ 7 16)) + x2 + x1} #a__take(x1,x2) weight: 0 a__natsFrom(x1) weight: max{0, (/ 7 16) + x1} a__fst(x1) weight: max{0, (/ 1 2) + x1} tail(x1) weight: max{0, (/ 3 8) + x1} #mark(x1) weight: 0 0() weight: (/ 9 16) a__u(x1,x2,x3,x4) weight: max{0, x1, (- (/ 1 4)) + x2, (/ 1 16) + x3} sel(x1,x2) weight: max{0, (/ 3 16) + x2 + x1} afterNth(x1,x2) weight: max{0, (- (/ 1 8)) + x2 + x1} nil() weight: (/ 1 8) a__splitAt(x1,x2) weight: max{0, (- (/ 7 16)) + x2 + x1} #a__sel(x1,x2) weight: 0 mark(x1) weight: max{0, x1} a__sel(x1,x2) weight: max{0, (/ 3 16) + x2 + x1} head(x1) weight: max{0, (/ 3 16) + x1} #a__afterNth(x1,x2) weight: 0 #a__splitAt(x1,x2) weight: max{0, (- (/ 1 16)) + x1} cons(x1,x2) weight: max{0, (/ 1 8) + x1, (- (/ 3 8)) + x2} snd(x1) weight: max{0, (- (/ 1 16)) + x1} #a__u(x1,x2,x3,x4) weight: 0 a__take(x1,x2) weight: max{0, (/ 1 2) + x2 + x1} #a__fst(x1) weight: 0 a__tail(x1) weight: max{0, (/ 3 8) + x1} #a__tail(x1) weight: 0 a__head(x1) weight: max{0, (/ 3 16) + x1} Usable rules: { 1..36 } Removed DPs: #30 Number of SCCs: 1, DPs: 3, edges: 9 SCC { #14 #16 #43 } Removing DPs: Order(PosReal,>,Sum)... succeeded. s(x1) weight: (/ 1 8) + x1 #a__head(x1) weight: 0 #a__natsFrom(x1) weight: 0 #a__snd(x1) weight: 0 a__afterNth(x1,x2) weight: x1 + x2 u(x1,x2,x3,x4) weight: (/ 3 4) + x1 + x3 + x4 take(x1,x2) weight: (/ 1 8) + x2 pair(x1,x2) weight: (/ 5 8) + x1 fst(x1) weight: (/ 1 8) + x1 natsFrom(x1) weight: (/ 1 8) a__snd(x1) weight: (/ 1 4) + x1 splitAt(x1,x2) weight: (/ 1 8) #a__take(x1,x2) weight: 0 a__natsFrom(x1) weight: (/ 1 2) a__fst(x1) weight: (/ 1 4) + x1 tail(x1) weight: (/ 1 8) + x1 #mark(x1) weight: (/ 3 8) + x1 0() weight: 0 a__u(x1,x2,x3,x4) weight: (/ 5 8) + x2 + x3 sel(x1,x2) weight: (/ 1 8) + x1 + x2 afterNth(x1,x2) weight: (/ 1 8) + x1 + x2 nil() weight: 0 a__splitAt(x1,x2) weight: (/ 1 2) #a__sel(x1,x2) weight: 0 mark(x1) weight: (/ 1 4) + x1 a__sel(x1,x2) weight: 0 head(x1) weight: (/ 1 8) + x1 #a__afterNth(x1,x2) weight: 0 #a__splitAt(x1,x2) weight: 0 cons(x1,x2) weight: (/ 5 8) snd(x1) weight: (/ 1 8) + x1 #a__u(x1,x2,x3,x4) weight: (/ 1 8) a__take(x1,x2) weight: 0 #a__fst(x1) weight: 0 a__tail(x1) weight: x1 #a__tail(x1) weight: 0 a__head(x1) weight: x1 Usable rules: { } Removed DPs: #14 #16 #43 Number of SCCs: 0, DPs: 0, edges: 0 YES