WORST_CASE(?,O(n^1)) * Step 1: Ara WORST_CASE(?,O(n^1)) + Considered Problem: - Strict TRS: activate(X) -> X activate(n__natsFrom(X)) -> natsFrom(X) afterNth(N,XS) -> snd(splitAt(N,XS)) fst(pair(XS,YS)) -> XS head(cons(N,XS)) -> N natsFrom(N) -> cons(N,n__natsFrom(s(N))) natsFrom(X) -> n__natsFrom(X) sel(N,XS) -> head(afterNth(N,XS)) snd(pair(XS,YS)) -> YS splitAt(0(),XS) -> pair(nil(),XS) splitAt(s(N),cons(X,XS)) -> u(splitAt(N,activate(XS)),N,X,activate(XS)) tail(cons(N,XS)) -> activate(XS) take(N,XS) -> fst(splitAt(N,XS)) u(pair(YS,ZS),N,X,XS) -> pair(cons(activate(X),YS),ZS) - Signature: {activate/1,afterNth/2,fst/1,head/1,natsFrom/1,sel/2,snd/1,splitAt/2,tail/1,take/2,u/4} / {0/0,cons/2 ,n__natsFrom/1,nil/0,pair/2,s/1} - Obligation: innermost runtime complexity wrt. defined symbols {activate,afterNth,fst,head,natsFrom,sel,snd,splitAt,tail ,take,u} and constructors {0,cons,n__natsFrom,nil,pair,s} + Applied Processor: Ara {heuristics_ = NoHeuristics, minDegree = 1, maxDegree = 1, araTimeout = 15, araFindStrictRules = Just 1} + Details: Signatures used: ---------------- 0 :: [] -(0)-> A(26) activate :: [A(0)] -(1)-> A(0) afterNth :: [A(30) x A(8)] -(25)-> A(0) cons :: [A(0) x A(0)] -(0)-> A(0) cons :: [A(0) x A(0)] -(0)-> A(1) cons :: [A(0) x A(0)] -(0)-> A(6) fst :: [A(28)] -(1)-> A(0) head :: [A(0)] -(0)-> A(0) n__natsFrom :: [A(0)] -(0)-> A(0) natsFrom :: [A(0)] -(1)-> A(0) nil :: [] -(0)-> A(28) pair :: [A(0) x A(0)] -(0)-> A(28) pair :: [A(0) x A(0)] -(0)-> A(7) pair :: [A(0) x A(0)] -(0)-> A(5) pair :: [A(0) x A(0)] -(0)-> A(30) s :: [A(26)] -(26)-> A(26) s :: [A(0)] -(0)-> A(0) sel :: [A(30) x A(22)] -(31)-> A(0) snd :: [A(7)] -(4)-> A(0) splitAt :: [A(26) x A(0)] -(2)-> A(28) tail :: [A(1)] -(31)-> A(0) take :: [A(28) x A(14)] -(17)-> A(0) u :: [A(5) x A(0) x A(0) x A(0)] -(9)-> A(30) Cost-free Signatures used: -------------------------- 0 :: [] -(0)-> A_cf(0) activate :: [A_cf(0)] -(0)-> A_cf(0) cons :: [A_cf(0) x A_cf(0)] -(0)-> A_cf(0) n__natsFrom :: [A_cf(0)] -(0)-> A_cf(0) natsFrom :: [A_cf(0)] -(0)-> A_cf(0) nil :: [] -(0)-> A_cf(0) pair :: [A_cf(0) x A_cf(0)] -(0)-> A_cf(0) s :: [A_cf(0)] -(0)-> A_cf(0) splitAt :: [A_cf(0) x A_cf(0)] -(0)-> A_cf(0) u :: [A_cf(0) x A_cf(0) x A_cf(0) x A_cf(0)] -(0)-> A_cf(0) Base Constructor Signatures used: --------------------------------- 0_A :: [] -(0)-> A(1) cons_A :: [A(0) x A(0)] -(0)-> A(1) n__natsFrom_A :: [A(0)] -(0)-> A(1) nil_A :: [] -(0)-> A(1) pair_A :: [A(0) x A(0)] -(0)-> A(1) s_A :: [A(1)] -(1)-> A(1) Following Still Strict Rules were Typed as: ------------------------------------------- 1. Strict: activate(X) -> X snd(pair(XS,YS)) -> YS splitAt(s(N),cons(X,XS)) -> u(splitAt(N,activate(XS)),N,X,activate(XS)) 2. Weak: activate(n__natsFrom(X)) -> natsFrom(X) afterNth(N,XS) -> snd(splitAt(N,XS)) fst(pair(XS,YS)) -> XS head(cons(N,XS)) -> N natsFrom(N) -> cons(N,n__natsFrom(s(N))) natsFrom(X) -> n__natsFrom(X) sel(N,XS) -> head(afterNth(N,XS)) splitAt(0(),XS) -> pair(nil(),XS) tail(cons(N,XS)) -> activate(XS) take(N,XS) -> fst(splitAt(N,XS)) u(pair(YS,ZS),N,X,XS) -> pair(cons(activate(X),YS),ZS) * Step 2: Ara WORST_CASE(?,O(n^1)) + Considered Problem: - Strict TRS: activate(n__natsFrom(X)) -> natsFrom(X) afterNth(N,XS) -> snd(splitAt(N,XS)) fst(pair(XS,YS)) -> XS head(cons(N,XS)) -> N natsFrom(N) -> cons(N,n__natsFrom(s(N))) natsFrom(X) -> n__natsFrom(X) sel(N,XS) -> head(afterNth(N,XS)) splitAt(0(),XS) -> pair(nil(),XS) tail(cons(N,XS)) -> activate(XS) take(N,XS) -> fst(splitAt(N,XS)) u(pair(YS,ZS),N,X,XS) -> pair(cons(activate(X),YS),ZS) - Weak TRS: activate(X) -> X snd(pair(XS,YS)) -> YS splitAt(s(N),cons(X,XS)) -> u(splitAt(N,activate(XS)),N,X,activate(XS)) - Signature: {activate/1,afterNth/2,fst/1,head/1,natsFrom/1,sel/2,snd/1,splitAt/2,tail/1,take/2,u/4} / {0/0,cons/2 ,n__natsFrom/1,nil/0,pair/2,s/1} - Obligation: innermost runtime complexity wrt. defined symbols {activate,afterNth,fst,head,natsFrom,sel,snd,splitAt,tail ,take,u} and constructors {0,cons,n__natsFrom,nil,pair,s} + Applied Processor: Ara {heuristics_ = NoHeuristics, minDegree = 1, maxDegree = 1, araTimeout = 15, araFindStrictRules = Just 1} + Details: Signatures used: ---------------- 0 :: [] -(0)-> A(28) activate :: [A(0)] -(7)-> A(0) afterNth :: [A(28) x A(8)] -(31)-> A(0) cons :: [A(0) x A(0)] -(0)-> A(0) cons :: [A(0) x A(20)] -(0)-> A(20) cons :: [A(0) x A(30)] -(0)-> A(30) cons :: [A(0) x A(15)] -(0)-> A(15) fst :: [A(12)] -(15)-> A(12) head :: [A(0)] -(0)-> A(0) n__natsFrom :: [A(0)] -(0)-> A(0) n__natsFrom :: [A(0)] -(0)-> A(30) natsFrom :: [A(0)] -(6)-> A(6) nil :: [] -(0)-> A(30) pair :: [A(12) x A(0)] -(12)-> A(12) pair :: [A(15) x A(0)] -(15)-> A(15) pair :: [A(1) x A(0)] -(1)-> A(1) s :: [A(28)] -(28)-> A(28) s :: [A(0)] -(0)-> A(0) sel :: [A(30) x A(22)] -(31)-> A(0) snd :: [A(1)] -(1)-> A(0) splitAt :: [A(28) x A(0)] -(15)-> A(15) tail :: [A(20)] -(29)-> A(0) take :: [A(30) x A(6)] -(30)-> A(2) u :: [A(15) x A(0) x A(0) x A(0)] -(7)-> A(15) Cost-free Signatures used: -------------------------- 0 :: [] -(0)-> A_cf(0) activate :: [A_cf(0)] -(0)-> A_cf(0) cons :: [A_cf(0) x A_cf(0)] -(0)-> A_cf(0) n__natsFrom :: [A_cf(0)] -(0)-> A_cf(0) natsFrom :: [A_cf(0)] -(0)-> A_cf(0) nil :: [] -(0)-> A_cf(0) pair :: [A_cf(0) x A_cf(0)] -(0)-> A_cf(0) s :: [A_cf(0)] -(0)-> A_cf(0) splitAt :: [A_cf(0) x A_cf(0)] -(0)-> A_cf(0) u :: [A_cf(0) x A_cf(0) x A_cf(0) x A_cf(0)] -(0)-> A_cf(0) Base Constructor Signatures used: --------------------------------- 0_A :: [] -(0)-> A(1) cons_A :: [A(0) x A(1)] -(0)-> A(1) n__natsFrom_A :: [A(0)] -(0)-> A(1) nil_A :: [] -(0)-> A(1) pair_A :: [A(1) x A(0)] -(1)-> A(1) s_A :: [A(1)] -(1)-> A(1) Following Still Strict Rules were Typed as: ------------------------------------------- 1. Strict: natsFrom(N) -> cons(N,n__natsFrom(s(N))) natsFrom(X) -> n__natsFrom(X) tail(cons(N,XS)) -> activate(XS) 2. Weak: activate(n__natsFrom(X)) -> natsFrom(X) afterNth(N,XS) -> snd(splitAt(N,XS)) fst(pair(XS,YS)) -> XS head(cons(N,XS)) -> N sel(N,XS) -> head(afterNth(N,XS)) splitAt(0(),XS) -> pair(nil(),XS) take(N,XS) -> fst(splitAt(N,XS)) u(pair(YS,ZS),N,X,XS) -> pair(cons(activate(X),YS),ZS) * Step 3: Ara WORST_CASE(?,O(n^1)) + Considered Problem: - Strict TRS: activate(n__natsFrom(X)) -> natsFrom(X) afterNth(N,XS) -> snd(splitAt(N,XS)) fst(pair(XS,YS)) -> XS head(cons(N,XS)) -> N sel(N,XS) -> head(afterNth(N,XS)) splitAt(0(),XS) -> pair(nil(),XS) take(N,XS) -> fst(splitAt(N,XS)) u(pair(YS,ZS),N,X,XS) -> pair(cons(activate(X),YS),ZS) - Weak TRS: activate(X) -> X natsFrom(N) -> cons(N,n__natsFrom(s(N))) natsFrom(X) -> n__natsFrom(X) snd(pair(XS,YS)) -> YS splitAt(s(N),cons(X,XS)) -> u(splitAt(N,activate(XS)),N,X,activate(XS)) tail(cons(N,XS)) -> activate(XS) - Signature: {activate/1,afterNth/2,fst/1,head/1,natsFrom/1,sel/2,snd/1,splitAt/2,tail/1,take/2,u/4} / {0/0,cons/2 ,n__natsFrom/1,nil/0,pair/2,s/1} - Obligation: innermost runtime complexity wrt. defined symbols {activate,afterNth,fst,head,natsFrom,sel,snd,splitAt,tail ,take,u} and constructors {0,cons,n__natsFrom,nil,pair,s} + Applied Processor: Ara {heuristics_ = NoHeuristics, minDegree = 1, maxDegree = 1, araTimeout = 15, araFindStrictRules = Just 1} + Details: Signatures used: ---------------- 0 :: [] -(0)-> A(15) activate :: [A(0)] -(0)-> A(0) afterNth :: [A(15) x A(4)] -(15)-> A(0) cons :: [A(0) x A(0)] -(0)-> A(0) cons :: [A(0) x A(0)] -(0)-> A(15) cons :: [A(0) x A(0)] -(0)-> A(12) cons :: [A(0) x A(0)] -(0)-> A(3) fst :: [A(0)] -(7)-> A(0) head :: [A(0)] -(0)-> A(0) n__natsFrom :: [A(0)] -(0)-> A(0) natsFrom :: [A(0)] -(0)-> A(0) nil :: [] -(0)-> A(14) pair :: [A(0) x A(0)] -(0)-> A(0) pair :: [A(0) x A(0)] -(0)-> A(4) pair :: [A(0) x A(0)] -(0)-> A(7) pair :: [A(0) x A(0)] -(0)-> A(6) s :: [A(15)] -(15)-> A(15) s :: [A(0)] -(0)-> A(0) sel :: [A(15) x A(10)] -(15)-> A(0) snd :: [A(0)] -(2)-> A(0) splitAt :: [A(15) x A(0)] -(5)-> A(4) tail :: [A(15)] -(12)-> A(0) take :: [A(15) x A(6)] -(15)-> A(0) u :: [A(4) x A(0) x A(0) x A(0)] -(3)-> A(6) Cost-free Signatures used: -------------------------- 0 :: [] -(0)-> A_cf(0) activate :: [A_cf(0)] -(0)-> A_cf(0) cons :: [A_cf(0) x A_cf(0)] -(0)-> A_cf(0) n__natsFrom :: [A_cf(0)] -(0)-> A_cf(0) natsFrom :: [A_cf(0)] -(0)-> A_cf(0) nil :: [] -(0)-> A_cf(0) pair :: [A_cf(0) x A_cf(0)] -(0)-> A_cf(0) s :: [A_cf(0)] -(0)-> A_cf(0) splitAt :: [A_cf(0) x A_cf(0)] -(0)-> A_cf(0) u :: [A_cf(0) x A_cf(0) x A_cf(0) x A_cf(0)] -(0)-> A_cf(0) Base Constructor Signatures used: --------------------------------- 0_A :: [] -(0)-> A(1) cons_A :: [A(0) x A(0)] -(0)-> A(1) n__natsFrom_A :: [A(0)] -(0)-> A(1) nil_A :: [] -(0)-> A(1) pair_A :: [A(0) x A(0)] -(0)-> A(1) s_A :: [A(1)] -(1)-> A(1) Following Still Strict Rules were Typed as: ------------------------------------------- 1. Strict: splitAt(0(),XS) -> pair(nil(),XS) 2. Weak: activate(n__natsFrom(X)) -> natsFrom(X) afterNth(N,XS) -> snd(splitAt(N,XS)) fst(pair(XS,YS)) -> XS head(cons(N,XS)) -> N sel(N,XS) -> head(afterNth(N,XS)) take(N,XS) -> fst(splitAt(N,XS)) u(pair(YS,ZS),N,X,XS) -> pair(cons(activate(X),YS),ZS) * Step 4: Ara WORST_CASE(?,O(n^1)) + Considered Problem: - Strict TRS: activate(n__natsFrom(X)) -> natsFrom(X) afterNth(N,XS) -> snd(splitAt(N,XS)) fst(pair(XS,YS)) -> XS head(cons(N,XS)) -> N sel(N,XS) -> head(afterNth(N,XS)) take(N,XS) -> fst(splitAt(N,XS)) u(pair(YS,ZS),N,X,XS) -> pair(cons(activate(X),YS),ZS) - Weak TRS: activate(X) -> X natsFrom(N) -> cons(N,n__natsFrom(s(N))) natsFrom(X) -> n__natsFrom(X) snd(pair(XS,YS)) -> YS splitAt(0(),XS) -> pair(nil(),XS) splitAt(s(N),cons(X,XS)) -> u(splitAt(N,activate(XS)),N,X,activate(XS)) tail(cons(N,XS)) -> activate(XS) - Signature: {activate/1,afterNth/2,fst/1,head/1,natsFrom/1,sel/2,snd/1,splitAt/2,tail/1,take/2,u/4} / {0/0,cons/2 ,n__natsFrom/1,nil/0,pair/2,s/1} - Obligation: innermost runtime complexity wrt. defined symbols {activate,afterNth,fst,head,natsFrom,sel,snd,splitAt,tail ,take,u} and constructors {0,cons,n__natsFrom,nil,pair,s} + Applied Processor: Ara {heuristics_ = NoHeuristics, minDegree = 1, maxDegree = 1, araTimeout = 15, araFindStrictRules = Just 1} + Details: Signatures used: ---------------- 0 :: [] -(0)-> A(10) activate :: [A(0)] -(0)-> A(0) afterNth :: [A(14) x A(4)] -(14)-> A(0) cons :: [A(0) x A(0)] -(0)-> A(0) cons :: [A(0) x A(1)] -(1)-> A(1) fst :: [A(2)] -(3)-> A(0) head :: [A(0)] -(0)-> A(0) n__natsFrom :: [A(0)] -(0)-> A(0) natsFrom :: [A(0)] -(0)-> A(0) nil :: [] -(0)-> A(14) pair :: [A(0) x A(0)] -(2)-> A(2) pair :: [A(0) x A(0)] -(5)-> A(5) s :: [A(10)] -(10)-> A(10) s :: [A(0)] -(0)-> A(0) sel :: [A(14) x A(10)] -(15)-> A(0) snd :: [A(2)] -(6)-> A(0) splitAt :: [A(10) x A(0)] -(5)-> A(5) tail :: [A(1)] -(11)-> A(0) take :: [A(12) x A(6)] -(14)-> A(0) u :: [A(5) x A(0) x A(0) x A(0)] -(2)-> A(5) Cost-free Signatures used: -------------------------- 0 :: [] -(0)-> A_cf(0) activate :: [A_cf(0)] -(0)-> A_cf(0) cons :: [A_cf(0) x A_cf(0)] -(0)-> A_cf(0) n__natsFrom :: [A_cf(0)] -(0)-> A_cf(0) natsFrom :: [A_cf(0)] -(0)-> A_cf(0) nil :: [] -(0)-> A_cf(0) pair :: [A_cf(0) x A_cf(0)] -(0)-> A_cf(0) s :: [A_cf(0)] -(0)-> A_cf(0) splitAt :: [A_cf(0) x A_cf(0)] -(0)-> A_cf(0) u :: [A_cf(0) x A_cf(0) x A_cf(0) x A_cf(0)] -(0)-> A_cf(0) Base Constructor Signatures used: --------------------------------- 0_A :: [] -(0)-> A(1) cons_A :: [A(0) x A(1)] -(1)-> A(1) n__natsFrom_A :: [A(0)] -(0)-> A(1) nil_A :: [] -(0)-> A(1) pair_A :: [A(0) x A(0)] -(1)-> A(1) s_A :: [A(1)] -(1)-> A(1) Following Still Strict Rules were Typed as: ------------------------------------------- 1. Strict: afterNth(N,XS) -> snd(splitAt(N,XS)) take(N,XS) -> fst(splitAt(N,XS)) 2. Weak: activate(n__natsFrom(X)) -> natsFrom(X) fst(pair(XS,YS)) -> XS head(cons(N,XS)) -> N sel(N,XS) -> head(afterNth(N,XS)) u(pair(YS,ZS),N,X,XS) -> pair(cons(activate(X),YS),ZS) * Step 5: Ara WORST_CASE(?,O(n^1)) + Considered Problem: - Strict TRS: activate(n__natsFrom(X)) -> natsFrom(X) fst(pair(XS,YS)) -> XS head(cons(N,XS)) -> N sel(N,XS) -> head(afterNth(N,XS)) u(pair(YS,ZS),N,X,XS) -> pair(cons(activate(X),YS),ZS) - Weak TRS: activate(X) -> X afterNth(N,XS) -> snd(splitAt(N,XS)) natsFrom(N) -> cons(N,n__natsFrom(s(N))) natsFrom(X) -> n__natsFrom(X) snd(pair(XS,YS)) -> YS splitAt(0(),XS) -> pair(nil(),XS) splitAt(s(N),cons(X,XS)) -> u(splitAt(N,activate(XS)),N,X,activate(XS)) tail(cons(N,XS)) -> activate(XS) take(N,XS) -> fst(splitAt(N,XS)) - Signature: {activate/1,afterNth/2,fst/1,head/1,natsFrom/1,sel/2,snd/1,splitAt/2,tail/1,take/2,u/4} / {0/0,cons/2 ,n__natsFrom/1,nil/0,pair/2,s/1} - Obligation: innermost runtime complexity wrt. defined symbols {activate,afterNth,fst,head,natsFrom,sel,snd,splitAt,tail ,take,u} and constructors {0,cons,n__natsFrom,nil,pair,s} + Applied Processor: Ara {heuristics_ = NoHeuristics, minDegree = 1, maxDegree = 1, araTimeout = 15, araFindStrictRules = Just 1} + Details: Signatures used: ---------------- 0 :: [] -(0)-> A(15) activate :: [A(0)] -(3)-> A(0) afterNth :: [A(15) x A(4)] -(9)-> A(0) cons :: [A(0) x A(0)] -(0)-> A(0) cons :: [A(0) x A(15)] -(0)-> A(15) cons :: [A(0) x A(3)] -(0)-> A(3) cons :: [A(0) x A(2)] -(0)-> A(2) fst :: [A(1)] -(0)-> A(1) head :: [A(0)] -(2)-> A(0) n__natsFrom :: [A(0)] -(0)-> A(0) n__natsFrom :: [A(0)] -(0)-> A(4) natsFrom :: [A(0)] -(3)-> A(0) nil :: [] -(0)-> A(15) pair :: [A(1) x A(0)] -(1)-> A(1) pair :: [A(3) x A(0)] -(3)-> A(3) pair :: [A(7) x A(0)] -(7)-> A(7) s :: [A(15)] -(15)-> A(15) s :: [A(0)] -(0)-> A(0) sel :: [A(15) x A(10)] -(15)-> A(0) snd :: [A(1)] -(0)-> A(0) splitAt :: [A(15) x A(0)] -(9)-> A(3) tail :: [A(15)] -(15)-> A(0) take :: [A(15) x A(2)] -(14)-> A(0) u :: [A(3) x A(0) x A(0) x A(0)] -(3)-> A(3) Cost-free Signatures used: -------------------------- 0 :: [] -(0)-> A_cf(0) activate :: [A_cf(0)] -(0)-> A_cf(0) cons :: [A_cf(0) x A_cf(0)] -(0)-> A_cf(0) n__natsFrom :: [A_cf(0)] -(0)-> A_cf(0) natsFrom :: [A_cf(0)] -(0)-> A_cf(0) nil :: [] -(0)-> A_cf(0) pair :: [A_cf(0) x A_cf(0)] -(0)-> A_cf(0) s :: [A_cf(0)] -(0)-> A_cf(0) splitAt :: [A_cf(0) x A_cf(0)] -(0)-> A_cf(0) u :: [A_cf(0) x A_cf(0) x A_cf(0) x A_cf(0)] -(0)-> A_cf(0) Base Constructor Signatures used: --------------------------------- 0_A :: [] -(0)-> A(1) cons_A :: [A(0) x A(1)] -(0)-> A(1) n__natsFrom_A :: [A(0)] -(0)-> A(1) nil_A :: [] -(0)-> A(1) pair_A :: [A(1) x A(0)] -(1)-> A(1) s_A :: [A(1)] -(1)-> A(1) Following Still Strict Rules were Typed as: ------------------------------------------- 1. Strict: head(cons(N,XS)) -> N 2. Weak: activate(n__natsFrom(X)) -> natsFrom(X) fst(pair(XS,YS)) -> XS sel(N,XS) -> head(afterNth(N,XS)) u(pair(YS,ZS),N,X,XS) -> pair(cons(activate(X),YS),ZS) * Step 6: Ara WORST_CASE(?,O(n^1)) + Considered Problem: - Strict TRS: activate(n__natsFrom(X)) -> natsFrom(X) fst(pair(XS,YS)) -> XS sel(N,XS) -> head(afterNth(N,XS)) u(pair(YS,ZS),N,X,XS) -> pair(cons(activate(X),YS),ZS) - Weak TRS: activate(X) -> X afterNth(N,XS) -> snd(splitAt(N,XS)) head(cons(N,XS)) -> N natsFrom(N) -> cons(N,n__natsFrom(s(N))) natsFrom(X) -> n__natsFrom(X) snd(pair(XS,YS)) -> YS splitAt(0(),XS) -> pair(nil(),XS) splitAt(s(N),cons(X,XS)) -> u(splitAt(N,activate(XS)),N,X,activate(XS)) tail(cons(N,XS)) -> activate(XS) take(N,XS) -> fst(splitAt(N,XS)) - Signature: {activate/1,afterNth/2,fst/1,head/1,natsFrom/1,sel/2,snd/1,splitAt/2,tail/1,take/2,u/4} / {0/0,cons/2 ,n__natsFrom/1,nil/0,pair/2,s/1} - Obligation: innermost runtime complexity wrt. defined symbols {activate,afterNth,fst,head,natsFrom,sel,snd,splitAt,tail ,take,u} and constructors {0,cons,n__natsFrom,nil,pair,s} + Applied Processor: Ara {heuristics_ = NoHeuristics, minDegree = 1, maxDegree = 1, araTimeout = 15, araFindStrictRules = Just 1} + Details: Signatures used: ---------------- 0 :: [] -(0)-> A(15) activate :: [A(0)] -(0)-> A(0) afterNth :: [A(15) x A(4)] -(4)-> A(0) cons :: [A(0) x A(0)] -(0)-> A(0) cons :: [A(0) x A(0)] -(0)-> A(15) cons :: [A(0) x A(0)] -(0)-> A(13) cons :: [A(0) x A(0)] -(0)-> A(1) fst :: [A(1)] -(0)-> A(1) head :: [A(0)] -(2)-> A(0) n__natsFrom :: [A(0)] -(0)-> A(0) natsFrom :: [A(0)] -(0)-> A(0) nil :: [] -(0)-> A(13) pair :: [A(1) x A(0)] -(1)-> A(1) pair :: [A(3) x A(0)] -(3)-> A(3) pair :: [A(0) x A(0)] -(0)-> A(0) pair :: [A(4) x A(0)] -(4)-> A(4) s :: [A(15)] -(15)-> A(15) s :: [A(0)] -(0)-> A(0) sel :: [A(15) x A(10)] -(11)-> A(0) snd :: [A(0)] -(0)-> A(0) splitAt :: [A(15) x A(0)] -(3)-> A(3) tail :: [A(15)] -(12)-> A(0) take :: [A(15) x A(6)] -(10)-> A(0) u :: [A(3) x A(0) x A(0) x A(0)] -(6)-> A(4) Cost-free Signatures used: -------------------------- 0 :: [] -(0)-> A_cf(0) activate :: [A_cf(0)] -(0)-> A_cf(0) cons :: [A_cf(0) x A_cf(0)] -(0)-> A_cf(0) n__natsFrom :: [A_cf(0)] -(0)-> A_cf(0) natsFrom :: [A_cf(0)] -(0)-> A_cf(0) nil :: [] -(0)-> A_cf(0) pair :: [A_cf(0) x A_cf(0)] -(0)-> A_cf(0) s :: [A_cf(0)] -(0)-> A_cf(0) splitAt :: [A_cf(0) x A_cf(0)] -(0)-> A_cf(0) u :: [A_cf(0) x A_cf(0) x A_cf(0) x A_cf(0)] -(0)-> A_cf(0) Base Constructor Signatures used: --------------------------------- 0_A :: [] -(0)-> A(1) cons_A :: [A(0) x A(0)] -(0)-> A(1) n__natsFrom_A :: [A(0)] -(1)-> A(1) nil_A :: [] -(0)-> A(1) pair_A :: [A(1) x A(0)] -(1)-> A(1) s_A :: [A(1)] -(1)-> A(1) Following Still Strict Rules were Typed as: ------------------------------------------- 1. Strict: fst(pair(XS,YS)) -> XS 2. Weak: activate(n__natsFrom(X)) -> natsFrom(X) sel(N,XS) -> head(afterNth(N,XS)) u(pair(YS,ZS),N,X,XS) -> pair(cons(activate(X),YS),ZS) * Step 7: Ara WORST_CASE(?,O(n^1)) + Considered Problem: - Strict TRS: activate(n__natsFrom(X)) -> natsFrom(X) sel(N,XS) -> head(afterNth(N,XS)) u(pair(YS,ZS),N,X,XS) -> pair(cons(activate(X),YS),ZS) - Weak TRS: activate(X) -> X afterNth(N,XS) -> snd(splitAt(N,XS)) fst(pair(XS,YS)) -> XS head(cons(N,XS)) -> N natsFrom(N) -> cons(N,n__natsFrom(s(N))) natsFrom(X) -> n__natsFrom(X) snd(pair(XS,YS)) -> YS splitAt(0(),XS) -> pair(nil(),XS) splitAt(s(N),cons(X,XS)) -> u(splitAt(N,activate(XS)),N,X,activate(XS)) tail(cons(N,XS)) -> activate(XS) take(N,XS) -> fst(splitAt(N,XS)) - Signature: {activate/1,afterNth/2,fst/1,head/1,natsFrom/1,sel/2,snd/1,splitAt/2,tail/1,take/2,u/4} / {0/0,cons/2 ,n__natsFrom/1,nil/0,pair/2,s/1} - Obligation: innermost runtime complexity wrt. defined symbols {activate,afterNth,fst,head,natsFrom,sel,snd,splitAt,tail ,take,u} and constructors {0,cons,n__natsFrom,nil,pair,s} + Applied Processor: Ara {heuristics_ = NoHeuristics, minDegree = 1, maxDegree = 1, araTimeout = 15, araFindStrictRules = Just 1} + Details: Signatures used: ---------------- 0 :: [] -(0)-> A(15) activate :: [A(0)] -(0)-> A(0) afterNth :: [A(15) x A(2)] -(13)-> A(0) cons :: [A(0) x A(0)] -(0)-> A(0) cons :: [A(0) x A(1)] -(1)-> A(1) fst :: [A(0)] -(0)-> A(0) head :: [A(0)] -(1)-> A(0) n__natsFrom :: [A(0)] -(0)-> A(0) natsFrom :: [A(0)] -(0)-> A(0) nil :: [] -(0)-> A(14) pair :: [A(0) x A(0)] -(0)-> A(0) pair :: [A(0) x A(0)] -(1)-> A(1) pair :: [A(0) x A(0)] -(9)-> A(9) s :: [A(15)] -(15)-> A(15) s :: [A(0)] -(0)-> A(0) sel :: [A(15) x A(12)] -(15)-> A(0) snd :: [A(0)] -(0)-> A(0) splitAt :: [A(15) x A(0)] -(13)-> A(0) tail :: [A(1)] -(11)-> A(0) take :: [A(15) x A(6)] -(15)-> A(0) u :: [A(0) x A(0) x A(0) x A(0)] -(14)-> A(1) Cost-free Signatures used: -------------------------- 0 :: [] -(0)-> A_cf(0) activate :: [A_cf(0)] -(0)-> A_cf(0) cons :: [A_cf(0) x A_cf(0)] -(0)-> A_cf(0) n__natsFrom :: [A_cf(0)] -(0)-> A_cf(0) natsFrom :: [A_cf(0)] -(0)-> A_cf(0) nil :: [] -(0)-> A_cf(0) pair :: [A_cf(0) x A_cf(0)] -(0)-> A_cf(0) s :: [A_cf(0)] -(0)-> A_cf(0) splitAt :: [A_cf(0) x A_cf(0)] -(0)-> A_cf(0) u :: [A_cf(0) x A_cf(0) x A_cf(0) x A_cf(0)] -(0)-> A_cf(0) Base Constructor Signatures used: --------------------------------- 0_A :: [] -(0)-> A(1) cons_A :: [A(0) x A(1)] -(1)-> A(1) n__natsFrom_A :: [A(0)] -(1)-> A(1) nil_A :: [] -(0)-> A(1) pair_A :: [A(0) x A(0)] -(1)-> A(1) s_A :: [A(1)] -(1)-> A(1) Following Still Strict Rules were Typed as: ------------------------------------------- 1. Strict: sel(N,XS) -> head(afterNth(N,XS)) 2. Weak: activate(n__natsFrom(X)) -> natsFrom(X) u(pair(YS,ZS),N,X,XS) -> pair(cons(activate(X),YS),ZS) * Step 8: Ara WORST_CASE(?,O(n^1)) + Considered Problem: - Strict TRS: activate(n__natsFrom(X)) -> natsFrom(X) u(pair(YS,ZS),N,X,XS) -> pair(cons(activate(X),YS),ZS) - Weak TRS: activate(X) -> X afterNth(N,XS) -> snd(splitAt(N,XS)) fst(pair(XS,YS)) -> XS head(cons(N,XS)) -> N natsFrom(N) -> cons(N,n__natsFrom(s(N))) natsFrom(X) -> n__natsFrom(X) sel(N,XS) -> head(afterNth(N,XS)) snd(pair(XS,YS)) -> YS splitAt(0(),XS) -> pair(nil(),XS) splitAt(s(N),cons(X,XS)) -> u(splitAt(N,activate(XS)),N,X,activate(XS)) tail(cons(N,XS)) -> activate(XS) take(N,XS) -> fst(splitAt(N,XS)) - Signature: {activate/1,afterNth/2,fst/1,head/1,natsFrom/1,sel/2,snd/1,splitAt/2,tail/1,take/2,u/4} / {0/0,cons/2 ,n__natsFrom/1,nil/0,pair/2,s/1} - Obligation: innermost runtime complexity wrt. defined symbols {activate,afterNth,fst,head,natsFrom,sel,snd,splitAt,tail ,take,u} and constructors {0,cons,n__natsFrom,nil,pair,s} + Applied Processor: Ara {heuristics_ = NoHeuristics, minDegree = 1, maxDegree = 1, araTimeout = 15, araFindStrictRules = Just 1} + Details: Signatures used: ---------------- 0 :: [] -(0)-> A(12) activate :: [A(0)] -(0)-> A(0) afterNth :: [A(12) x A(14)] -(13)-> A(0) cons :: [A(0) x A(0)] -(0)-> A(0) cons :: [A(0) x A(0)] -(0)-> A(15) cons :: [A(0) x A(0)] -(0)-> A(2) fst :: [A(3)] -(0)-> A(0) head :: [A(0)] -(0)-> A(0) n__natsFrom :: [A(0)] -(0)-> A(0) natsFrom :: [A(0)] -(0)-> A(0) nil :: [] -(0)-> A(14) pair :: [A(0) x A(0)] -(7)-> A(7) pair :: [A(0) x A(0)] -(3)-> A(3) pair :: [A(0) x A(0)] -(0)-> A(0) s :: [A(12)] -(12)-> A(12) s :: [A(0)] -(0)-> A(0) sel :: [A(14) x A(14)] -(15)-> A(0) snd :: [A(0)] -(0)-> A(0) splitAt :: [A(12) x A(0)] -(13)-> A(7) tail :: [A(15)] -(12)-> A(0) take :: [A(14) x A(6)] -(15)-> A(0) u :: [A(7) x A(0) x A(0) x A(0)] -(7)-> A(7) Cost-free Signatures used: -------------------------- 0 :: [] -(0)-> A_cf(0) activate :: [A_cf(0)] -(0)-> A_cf(0) cons :: [A_cf(0) x A_cf(0)] -(0)-> A_cf(0) n__natsFrom :: [A_cf(0)] -(0)-> A_cf(0) natsFrom :: [A_cf(0)] -(0)-> A_cf(0) nil :: [] -(0)-> A_cf(0) pair :: [A_cf(0) x A_cf(0)] -(0)-> A_cf(0) s :: [A_cf(0)] -(0)-> A_cf(0) splitAt :: [A_cf(0) x A_cf(0)] -(0)-> A_cf(0) u :: [A_cf(0) x A_cf(0) x A_cf(0) x A_cf(0)] -(0)-> A_cf(0) Base Constructor Signatures used: --------------------------------- 0_A :: [] -(0)-> A(1) cons_A :: [A(0) x A(0)] -(0)-> A(1) n__natsFrom_A :: [A(0)] -(1)-> A(1) nil_A :: [] -(0)-> A(1) pair_A :: [A(0) x A(0)] -(1)-> A(1) s_A :: [A(1)] -(1)-> A(1) Following Still Strict Rules were Typed as: ------------------------------------------- 1. Strict: u(pair(YS,ZS),N,X,XS) -> pair(cons(activate(X),YS),ZS) 2. Weak: activate(n__natsFrom(X)) -> natsFrom(X) * Step 9: Ara WORST_CASE(?,O(n^1)) + Considered Problem: - Strict TRS: activate(n__natsFrom(X)) -> natsFrom(X) - Weak TRS: activate(X) -> X afterNth(N,XS) -> snd(splitAt(N,XS)) fst(pair(XS,YS)) -> XS head(cons(N,XS)) -> N natsFrom(N) -> cons(N,n__natsFrom(s(N))) natsFrom(X) -> n__natsFrom(X) sel(N,XS) -> head(afterNth(N,XS)) snd(pair(XS,YS)) -> YS splitAt(0(),XS) -> pair(nil(),XS) splitAt(s(N),cons(X,XS)) -> u(splitAt(N,activate(XS)),N,X,activate(XS)) tail(cons(N,XS)) -> activate(XS) take(N,XS) -> fst(splitAt(N,XS)) u(pair(YS,ZS),N,X,XS) -> pair(cons(activate(X),YS),ZS) - Signature: {activate/1,afterNth/2,fst/1,head/1,natsFrom/1,sel/2,snd/1,splitAt/2,tail/1,take/2,u/4} / {0/0,cons/2 ,n__natsFrom/1,nil/0,pair/2,s/1} - Obligation: innermost runtime complexity wrt. defined symbols {activate,afterNth,fst,head,natsFrom,sel,snd,splitAt,tail ,take,u} and constructors {0,cons,n__natsFrom,nil,pair,s} + Applied Processor: Ara {heuristics_ = NoHeuristics, minDegree = 1, maxDegree = 1, araTimeout = 15, araFindStrictRules = Just 1} + Details: Signatures used: ---------------- 0 :: [] -(0)-> A(13) activate :: [A(0)] -(1)-> A(0) afterNth :: [A(13) x A(4)] -(9)-> A(0) cons :: [A(0) x A(0)] -(0)-> A(0) cons :: [A(0) x A(3)] -(3)-> A(3) fst :: [A(1)] -(0)-> A(0) head :: [A(0)] -(0)-> A(0) n__natsFrom :: [A(0)] -(0)-> A(0) natsFrom :: [A(0)] -(0)-> A(0) nil :: [] -(0)-> A(14) pair :: [A(0) x A(0)] -(0)-> A(1) pair :: [A(0) x A(0)] -(0)-> A(0) pair :: [A(0) x A(0)] -(0)-> A(12) s :: [A(13)] -(13)-> A(13) s :: [A(0)] -(0)-> A(0) sel :: [A(15) x A(10)] -(15)-> A(0) snd :: [A(0)] -(1)-> A(0) splitAt :: [A(13) x A(0)] -(1)-> A(1) tail :: [A(3)] -(11)-> A(0) take :: [A(15) x A(2)] -(14)-> A(0) u :: [A(1) x A(0) x A(0) x A(0)] -(2)-> A(10) Cost-free Signatures used: -------------------------- 0 :: [] -(0)-> A_cf(0) activate :: [A_cf(0)] -(0)-> A_cf(0) cons :: [A_cf(0) x A_cf(0)] -(0)-> A_cf(0) n__natsFrom :: [A_cf(0)] -(0)-> A_cf(0) natsFrom :: [A_cf(0)] -(0)-> A_cf(0) nil :: [] -(0)-> A_cf(0) pair :: [A_cf(0) x A_cf(0)] -(0)-> A_cf(0) s :: [A_cf(0)] -(0)-> A_cf(0) splitAt :: [A_cf(0) x A_cf(0)] -(0)-> A_cf(0) u :: [A_cf(0) x A_cf(0) x A_cf(0) x A_cf(0)] -(0)-> A_cf(0) Base Constructor Signatures used: --------------------------------- 0_A :: [] -(0)-> A(1) cons_A :: [A(0) x A(1)] -(1)-> A(1) n__natsFrom_A :: [A(0)] -(1)-> A(1) nil_A :: [] -(0)-> A(1) pair_A :: [A(0) x A(0)] -(0)-> A(1) s_A :: [A(1)] -(1)-> A(1) Following Still Strict Rules were Typed as: ------------------------------------------- 1. Strict: activate(n__natsFrom(X)) -> natsFrom(X) 2. Weak: * Step 10: EmptyProcessor WORST_CASE(?,O(1)) + Considered Problem: - Weak TRS: activate(X) -> X activate(n__natsFrom(X)) -> natsFrom(X) afterNth(N,XS) -> snd(splitAt(N,XS)) fst(pair(XS,YS)) -> XS head(cons(N,XS)) -> N natsFrom(N) -> cons(N,n__natsFrom(s(N))) natsFrom(X) -> n__natsFrom(X) sel(N,XS) -> head(afterNth(N,XS)) snd(pair(XS,YS)) -> YS splitAt(0(),XS) -> pair(nil(),XS) splitAt(s(N),cons(X,XS)) -> u(splitAt(N,activate(XS)),N,X,activate(XS)) tail(cons(N,XS)) -> activate(XS) take(N,XS) -> fst(splitAt(N,XS)) u(pair(YS,ZS),N,X,XS) -> pair(cons(activate(X),YS),ZS) - Signature: {activate/1,afterNth/2,fst/1,head/1,natsFrom/1,sel/2,snd/1,splitAt/2,tail/1,take/2,u/4} / {0/0,cons/2 ,n__natsFrom/1,nil/0,pair/2,s/1} - Obligation: innermost runtime complexity wrt. defined symbols {activate,afterNth,fst,head,natsFrom,sel,snd,splitAt,tail ,take,u} and constructors {0,cons,n__natsFrom,nil,pair,s} + Applied Processor: EmptyProcessor + Details: The problem is already closed. The intended complexity is O(1). WORST_CASE(?,O(n^1))