* Step 1: Sum WORST_CASE(?,O(n^1))
+ Considered Problem:
- Strict TRS:
U11(tt(),N,XS) -> U12(tt(),activate(N),activate(XS))
U12(tt(),N,XS) -> snd(splitAt(activate(N),activate(XS)))
U21(tt(),X) -> U22(tt(),activate(X))
U22(tt(),X) -> activate(X)
U31(tt(),N) -> U32(tt(),activate(N))
U32(tt(),N) -> activate(N)
U41(tt(),N,XS) -> U42(tt(),activate(N),activate(XS))
U42(tt(),N,XS) -> head(afterNth(activate(N),activate(XS)))
U51(tt(),Y) -> U52(tt(),activate(Y))
U52(tt(),Y) -> activate(Y)
U61(tt(),N,X,XS) -> U62(tt(),activate(N),activate(X),activate(XS))
U62(tt(),N,X,XS) -> U63(tt(),activate(N),activate(X),activate(XS))
U63(tt(),N,X,XS) -> U64(splitAt(activate(N),activate(XS)),activate(X))
U64(pair(YS,ZS),X) -> pair(cons(activate(X),YS),ZS)
U71(tt(),XS) -> U72(tt(),activate(XS))
U72(tt(),XS) -> activate(XS)
U81(tt(),N,XS) -> U82(tt(),activate(N),activate(XS))
U82(tt(),N,XS) -> fst(splitAt(activate(N),activate(XS)))
activate(X) -> X
activate(n__natsFrom(X)) -> natsFrom(X)
afterNth(N,XS) -> U11(tt(),N,XS)
fst(pair(X,Y)) -> U21(tt(),X)
head(cons(N,XS)) -> U31(tt(),N)
natsFrom(N) -> cons(N,n__natsFrom(s(N)))
natsFrom(X) -> n__natsFrom(X)
sel(N,XS) -> U41(tt(),N,XS)
snd(pair(X,Y)) -> U51(tt(),Y)
splitAt(0(),XS) -> pair(nil(),XS)
splitAt(s(N),cons(X,XS)) -> U61(tt(),N,X,activate(XS))
tail(cons(N,XS)) -> U71(tt(),activate(XS))
take(N,XS) -> U81(tt(),N,XS)
- Signature:
{U11/3,U12/3,U21/2,U22/2,U31/2,U32/2,U41/3,U42/3,U51/2,U52/2,U61/4,U62/4,U63/4,U64/2,U71/2,U72/2,U81/3,U82/3
,activate/1,afterNth/2,fst/1,head/1,natsFrom/1,sel/2,snd/1,splitAt/2,tail/1,take/2} / {0/0,cons/2
,n__natsFrom/1,nil/0,pair/2,s/1,tt/0}
- Obligation:
innermost runtime complexity wrt. defined symbols {U11,U12,U21,U22,U31,U32,U41,U42,U51,U52,U61,U62,U63,U64
,U71,U72,U81,U82,activate,afterNth,fst,head,natsFrom,sel,snd,splitAt,tail,take} and constructors {0,cons
,n__natsFrom,nil,pair,s,tt}
+ Applied Processor:
Sum {left = someStrategy, right = someStrategy}
+ Details:
()
* Step 2: DependencyPairs WORST_CASE(?,O(n^1))
+ Considered Problem:
- Strict TRS:
U11(tt(),N,XS) -> U12(tt(),activate(N),activate(XS))
U12(tt(),N,XS) -> snd(splitAt(activate(N),activate(XS)))
U21(tt(),X) -> U22(tt(),activate(X))
U22(tt(),X) -> activate(X)
U31(tt(),N) -> U32(tt(),activate(N))
U32(tt(),N) -> activate(N)
U41(tt(),N,XS) -> U42(tt(),activate(N),activate(XS))
U42(tt(),N,XS) -> head(afterNth(activate(N),activate(XS)))
U51(tt(),Y) -> U52(tt(),activate(Y))
U52(tt(),Y) -> activate(Y)
U61(tt(),N,X,XS) -> U62(tt(),activate(N),activate(X),activate(XS))
U62(tt(),N,X,XS) -> U63(tt(),activate(N),activate(X),activate(XS))
U63(tt(),N,X,XS) -> U64(splitAt(activate(N),activate(XS)),activate(X))
U64(pair(YS,ZS),X) -> pair(cons(activate(X),YS),ZS)
U71(tt(),XS) -> U72(tt(),activate(XS))
U72(tt(),XS) -> activate(XS)
U81(tt(),N,XS) -> U82(tt(),activate(N),activate(XS))
U82(tt(),N,XS) -> fst(splitAt(activate(N),activate(XS)))
activate(X) -> X
activate(n__natsFrom(X)) -> natsFrom(X)
afterNth(N,XS) -> U11(tt(),N,XS)
fst(pair(X,Y)) -> U21(tt(),X)
head(cons(N,XS)) -> U31(tt(),N)
natsFrom(N) -> cons(N,n__natsFrom(s(N)))
natsFrom(X) -> n__natsFrom(X)
sel(N,XS) -> U41(tt(),N,XS)
snd(pair(X,Y)) -> U51(tt(),Y)
splitAt(0(),XS) -> pair(nil(),XS)
splitAt(s(N),cons(X,XS)) -> U61(tt(),N,X,activate(XS))
tail(cons(N,XS)) -> U71(tt(),activate(XS))
take(N,XS) -> U81(tt(),N,XS)
- Signature:
{U11/3,U12/3,U21/2,U22/2,U31/2,U32/2,U41/3,U42/3,U51/2,U52/2,U61/4,U62/4,U63/4,U64/2,U71/2,U72/2,U81/3,U82/3
,activate/1,afterNth/2,fst/1,head/1,natsFrom/1,sel/2,snd/1,splitAt/2,tail/1,take/2} / {0/0,cons/2
,n__natsFrom/1,nil/0,pair/2,s/1,tt/0}
- Obligation:
innermost runtime complexity wrt. defined symbols {U11,U12,U21,U22,U31,U32,U41,U42,U51,U52,U61,U62,U63,U64
,U71,U72,U81,U82,activate,afterNth,fst,head,natsFrom,sel,snd,splitAt,tail,take} and constructors {0,cons
,n__natsFrom,nil,pair,s,tt}
+ Applied Processor:
DependencyPairs {dpKind_ = DT}
+ Details:
We add the following dependency tuples:
Strict DPs
U11#(tt(),N,XS) -> c_1(U12#(tt(),activate(N),activate(XS)),activate#(N),activate#(XS))
U12#(tt(),N,XS) -> c_2(snd#(splitAt(activate(N),activate(XS)))
,splitAt#(activate(N),activate(XS))
,activate#(N)
,activate#(XS))
U21#(tt(),X) -> c_3(U22#(tt(),activate(X)),activate#(X))
U22#(tt(),X) -> c_4(activate#(X))
U31#(tt(),N) -> c_5(U32#(tt(),activate(N)),activate#(N))
U32#(tt(),N) -> c_6(activate#(N))
U41#(tt(),N,XS) -> c_7(U42#(tt(),activate(N),activate(XS)),activate#(N),activate#(XS))
U42#(tt(),N,XS) -> c_8(head#(afterNth(activate(N),activate(XS)))
,afterNth#(activate(N),activate(XS))
,activate#(N)
,activate#(XS))
U51#(tt(),Y) -> c_9(U52#(tt(),activate(Y)),activate#(Y))
U52#(tt(),Y) -> c_10(activate#(Y))
U61#(tt(),N,X,XS) -> c_11(U62#(tt(),activate(N),activate(X),activate(XS))
,activate#(N)
,activate#(X)
,activate#(XS))
U62#(tt(),N,X,XS) -> c_12(U63#(tt(),activate(N),activate(X),activate(XS))
,activate#(N)
,activate#(X)
,activate#(XS))
U63#(tt(),N,X,XS) -> c_13(U64#(splitAt(activate(N),activate(XS)),activate(X))
,splitAt#(activate(N),activate(XS))
,activate#(N)
,activate#(XS)
,activate#(X))
U64#(pair(YS,ZS),X) -> c_14(activate#(X))
U71#(tt(),XS) -> c_15(U72#(tt(),activate(XS)),activate#(XS))
U72#(tt(),XS) -> c_16(activate#(XS))
U81#(tt(),N,XS) -> c_17(U82#(tt(),activate(N),activate(XS)),activate#(N),activate#(XS))
U82#(tt(),N,XS) -> c_18(fst#(splitAt(activate(N),activate(XS)))
,splitAt#(activate(N),activate(XS))
,activate#(N)
,activate#(XS))
activate#(X) -> c_19()
activate#(n__natsFrom(X)) -> c_20(natsFrom#(X))
afterNth#(N,XS) -> c_21(U11#(tt(),N,XS))
fst#(pair(X,Y)) -> c_22(U21#(tt(),X))
head#(cons(N,XS)) -> c_23(U31#(tt(),N))
natsFrom#(N) -> c_24()
natsFrom#(X) -> c_25()
sel#(N,XS) -> c_26(U41#(tt(),N,XS))
snd#(pair(X,Y)) -> c_27(U51#(tt(),Y))
splitAt#(0(),XS) -> c_28()
splitAt#(s(N),cons(X,XS)) -> c_29(U61#(tt(),N,X,activate(XS)),activate#(XS))
tail#(cons(N,XS)) -> c_30(U71#(tt(),activate(XS)),activate#(XS))
take#(N,XS) -> c_31(U81#(tt(),N,XS))
Weak DPs
and mark the set of starting terms.
* Step 3: UsableRules WORST_CASE(?,O(n^1))
+ Considered Problem:
- Strict DPs:
U11#(tt(),N,XS) -> c_1(U12#(tt(),activate(N),activate(XS)),activate#(N),activate#(XS))
U12#(tt(),N,XS) -> c_2(snd#(splitAt(activate(N),activate(XS)))
,splitAt#(activate(N),activate(XS))
,activate#(N)
,activate#(XS))
U21#(tt(),X) -> c_3(U22#(tt(),activate(X)),activate#(X))
U22#(tt(),X) -> c_4(activate#(X))
U31#(tt(),N) -> c_5(U32#(tt(),activate(N)),activate#(N))
U32#(tt(),N) -> c_6(activate#(N))
U41#(tt(),N,XS) -> c_7(U42#(tt(),activate(N),activate(XS)),activate#(N),activate#(XS))
U42#(tt(),N,XS) -> c_8(head#(afterNth(activate(N),activate(XS)))
,afterNth#(activate(N),activate(XS))
,activate#(N)
,activate#(XS))
U51#(tt(),Y) -> c_9(U52#(tt(),activate(Y)),activate#(Y))
U52#(tt(),Y) -> c_10(activate#(Y))
U61#(tt(),N,X,XS) -> c_11(U62#(tt(),activate(N),activate(X),activate(XS))
,activate#(N)
,activate#(X)
,activate#(XS))
U62#(tt(),N,X,XS) -> c_12(U63#(tt(),activate(N),activate(X),activate(XS))
,activate#(N)
,activate#(X)
,activate#(XS))
U63#(tt(),N,X,XS) -> c_13(U64#(splitAt(activate(N),activate(XS)),activate(X))
,splitAt#(activate(N),activate(XS))
,activate#(N)
,activate#(XS)
,activate#(X))
U64#(pair(YS,ZS),X) -> c_14(activate#(X))
U71#(tt(),XS) -> c_15(U72#(tt(),activate(XS)),activate#(XS))
U72#(tt(),XS) -> c_16(activate#(XS))
U81#(tt(),N,XS) -> c_17(U82#(tt(),activate(N),activate(XS)),activate#(N),activate#(XS))
U82#(tt(),N,XS) -> c_18(fst#(splitAt(activate(N),activate(XS)))
,splitAt#(activate(N),activate(XS))
,activate#(N)
,activate#(XS))
activate#(X) -> c_19()
activate#(n__natsFrom(X)) -> c_20(natsFrom#(X))
afterNth#(N,XS) -> c_21(U11#(tt(),N,XS))
fst#(pair(X,Y)) -> c_22(U21#(tt(),X))
head#(cons(N,XS)) -> c_23(U31#(tt(),N))
natsFrom#(N) -> c_24()
natsFrom#(X) -> c_25()
sel#(N,XS) -> c_26(U41#(tt(),N,XS))
snd#(pair(X,Y)) -> c_27(U51#(tt(),Y))
splitAt#(0(),XS) -> c_28()
splitAt#(s(N),cons(X,XS)) -> c_29(U61#(tt(),N,X,activate(XS)),activate#(XS))
tail#(cons(N,XS)) -> c_30(U71#(tt(),activate(XS)),activate#(XS))
take#(N,XS) -> c_31(U81#(tt(),N,XS))
- Weak TRS:
U11(tt(),N,XS) -> U12(tt(),activate(N),activate(XS))
U12(tt(),N,XS) -> snd(splitAt(activate(N),activate(XS)))
U21(tt(),X) -> U22(tt(),activate(X))
U22(tt(),X) -> activate(X)
U31(tt(),N) -> U32(tt(),activate(N))
U32(tt(),N) -> activate(N)
U41(tt(),N,XS) -> U42(tt(),activate(N),activate(XS))
U42(tt(),N,XS) -> head(afterNth(activate(N),activate(XS)))
U51(tt(),Y) -> U52(tt(),activate(Y))
U52(tt(),Y) -> activate(Y)
U61(tt(),N,X,XS) -> U62(tt(),activate(N),activate(X),activate(XS))
U62(tt(),N,X,XS) -> U63(tt(),activate(N),activate(X),activate(XS))
U63(tt(),N,X,XS) -> U64(splitAt(activate(N),activate(XS)),activate(X))
U64(pair(YS,ZS),X) -> pair(cons(activate(X),YS),ZS)
U71(tt(),XS) -> U72(tt(),activate(XS))
U72(tt(),XS) -> activate(XS)
U81(tt(),N,XS) -> U82(tt(),activate(N),activate(XS))
U82(tt(),N,XS) -> fst(splitAt(activate(N),activate(XS)))
activate(X) -> X
activate(n__natsFrom(X)) -> natsFrom(X)
afterNth(N,XS) -> U11(tt(),N,XS)
fst(pair(X,Y)) -> U21(tt(),X)
head(cons(N,XS)) -> U31(tt(),N)
natsFrom(N) -> cons(N,n__natsFrom(s(N)))
natsFrom(X) -> n__natsFrom(X)
sel(N,XS) -> U41(tt(),N,XS)
snd(pair(X,Y)) -> U51(tt(),Y)
splitAt(0(),XS) -> pair(nil(),XS)
splitAt(s(N),cons(X,XS)) -> U61(tt(),N,X,activate(XS))
tail(cons(N,XS)) -> U71(tt(),activate(XS))
take(N,XS) -> U81(tt(),N,XS)
- Signature:
{U11/3,U12/3,U21/2,U22/2,U31/2,U32/2,U41/3,U42/3,U51/2,U52/2,U61/4,U62/4,U63/4,U64/2,U71/2,U72/2,U81/3,U82/3
,activate/1,afterNth/2,fst/1,head/1,natsFrom/1,sel/2,snd/1,splitAt/2,tail/1,take/2,U11#/3,U12#/3,U21#/2
,U22#/2,U31#/2,U32#/2,U41#/3,U42#/3,U51#/2,U52#/2,U61#/4,U62#/4,U63#/4,U64#/2,U71#/2,U72#/2,U81#/3,U82#/3
,activate#/1,afterNth#/2,fst#/1,head#/1,natsFrom#/1,sel#/2,snd#/1,splitAt#/2,tail#/1,take#/2} / {0/0,cons/2
,n__natsFrom/1,nil/0,pair/2,s/1,tt/0,c_1/3,c_2/4,c_3/2,c_4/1,c_5/2,c_6/1,c_7/3,c_8/4,c_9/2,c_10/1,c_11/4
,c_12/4,c_13/5,c_14/1,c_15/2,c_16/1,c_17/3,c_18/4,c_19/0,c_20/1,c_21/1,c_22/1,c_23/1,c_24/0,c_25/0,c_26/1
,c_27/1,c_28/0,c_29/2,c_30/2,c_31/1}
- Obligation:
innermost runtime complexity wrt. defined symbols {U11#,U12#,U21#,U22#,U31#,U32#,U41#,U42#,U51#,U52#,U61#
,U62#,U63#,U64#,U71#,U72#,U81#,U82#,activate#,afterNth#,fst#,head#,natsFrom#,sel#,snd#,splitAt#,tail#
,take#} and constructors {0,cons,n__natsFrom,nil,pair,s,tt}
+ Applied Processor:
UsableRules
+ Details:
We replace rewrite rules by usable rules:
U11(tt(),N,XS) -> U12(tt(),activate(N),activate(XS))
U12(tt(),N,XS) -> snd(splitAt(activate(N),activate(XS)))
U51(tt(),Y) -> U52(tt(),activate(Y))
U52(tt(),Y) -> activate(Y)
U61(tt(),N,X,XS) -> U62(tt(),activate(N),activate(X),activate(XS))
U62(tt(),N,X,XS) -> U63(tt(),activate(N),activate(X),activate(XS))
U63(tt(),N,X,XS) -> U64(splitAt(activate(N),activate(XS)),activate(X))
U64(pair(YS,ZS),X) -> pair(cons(activate(X),YS),ZS)
activate(X) -> X
activate(n__natsFrom(X)) -> natsFrom(X)
afterNth(N,XS) -> U11(tt(),N,XS)
natsFrom(N) -> cons(N,n__natsFrom(s(N)))
natsFrom(X) -> n__natsFrom(X)
snd(pair(X,Y)) -> U51(tt(),Y)
splitAt(0(),XS) -> pair(nil(),XS)
splitAt(s(N),cons(X,XS)) -> U61(tt(),N,X,activate(XS))
U11#(tt(),N,XS) -> c_1(U12#(tt(),activate(N),activate(XS)),activate#(N),activate#(XS))
U12#(tt(),N,XS) -> c_2(snd#(splitAt(activate(N),activate(XS)))
,splitAt#(activate(N),activate(XS))
,activate#(N)
,activate#(XS))
U21#(tt(),X) -> c_3(U22#(tt(),activate(X)),activate#(X))
U22#(tt(),X) -> c_4(activate#(X))
U31#(tt(),N) -> c_5(U32#(tt(),activate(N)),activate#(N))
U32#(tt(),N) -> c_6(activate#(N))
U41#(tt(),N,XS) -> c_7(U42#(tt(),activate(N),activate(XS)),activate#(N),activate#(XS))
U42#(tt(),N,XS) -> c_8(head#(afterNth(activate(N),activate(XS)))
,afterNth#(activate(N),activate(XS))
,activate#(N)
,activate#(XS))
U51#(tt(),Y) -> c_9(U52#(tt(),activate(Y)),activate#(Y))
U52#(tt(),Y) -> c_10(activate#(Y))
U61#(tt(),N,X,XS) -> c_11(U62#(tt(),activate(N),activate(X),activate(XS))
,activate#(N)
,activate#(X)
,activate#(XS))
U62#(tt(),N,X,XS) -> c_12(U63#(tt(),activate(N),activate(X),activate(XS))
,activate#(N)
,activate#(X)
,activate#(XS))
U63#(tt(),N,X,XS) -> c_13(U64#(splitAt(activate(N),activate(XS)),activate(X))
,splitAt#(activate(N),activate(XS))
,activate#(N)
,activate#(XS)
,activate#(X))
U64#(pair(YS,ZS),X) -> c_14(activate#(X))
U71#(tt(),XS) -> c_15(U72#(tt(),activate(XS)),activate#(XS))
U72#(tt(),XS) -> c_16(activate#(XS))
U81#(tt(),N,XS) -> c_17(U82#(tt(),activate(N),activate(XS)),activate#(N),activate#(XS))
U82#(tt(),N,XS) -> c_18(fst#(splitAt(activate(N),activate(XS)))
,splitAt#(activate(N),activate(XS))
,activate#(N)
,activate#(XS))
activate#(X) -> c_19()
activate#(n__natsFrom(X)) -> c_20(natsFrom#(X))
afterNth#(N,XS) -> c_21(U11#(tt(),N,XS))
fst#(pair(X,Y)) -> c_22(U21#(tt(),X))
head#(cons(N,XS)) -> c_23(U31#(tt(),N))
natsFrom#(N) -> c_24()
natsFrom#(X) -> c_25()
sel#(N,XS) -> c_26(U41#(tt(),N,XS))
snd#(pair(X,Y)) -> c_27(U51#(tt(),Y))
splitAt#(0(),XS) -> c_28()
splitAt#(s(N),cons(X,XS)) -> c_29(U61#(tt(),N,X,activate(XS)),activate#(XS))
tail#(cons(N,XS)) -> c_30(U71#(tt(),activate(XS)),activate#(XS))
take#(N,XS) -> c_31(U81#(tt(),N,XS))
* Step 4: PredecessorEstimation WORST_CASE(?,O(n^1))
+ Considered Problem:
- Strict DPs:
U11#(tt(),N,XS) -> c_1(U12#(tt(),activate(N),activate(XS)),activate#(N),activate#(XS))
U12#(tt(),N,XS) -> c_2(snd#(splitAt(activate(N),activate(XS)))
,splitAt#(activate(N),activate(XS))
,activate#(N)
,activate#(XS))
U21#(tt(),X) -> c_3(U22#(tt(),activate(X)),activate#(X))
U22#(tt(),X) -> c_4(activate#(X))
U31#(tt(),N) -> c_5(U32#(tt(),activate(N)),activate#(N))
U32#(tt(),N) -> c_6(activate#(N))
U41#(tt(),N,XS) -> c_7(U42#(tt(),activate(N),activate(XS)),activate#(N),activate#(XS))
U42#(tt(),N,XS) -> c_8(head#(afterNth(activate(N),activate(XS)))
,afterNth#(activate(N),activate(XS))
,activate#(N)
,activate#(XS))
U51#(tt(),Y) -> c_9(U52#(tt(),activate(Y)),activate#(Y))
U52#(tt(),Y) -> c_10(activate#(Y))
U61#(tt(),N,X,XS) -> c_11(U62#(tt(),activate(N),activate(X),activate(XS))
,activate#(N)
,activate#(X)
,activate#(XS))
U62#(tt(),N,X,XS) -> c_12(U63#(tt(),activate(N),activate(X),activate(XS))
,activate#(N)
,activate#(X)
,activate#(XS))
U63#(tt(),N,X,XS) -> c_13(U64#(splitAt(activate(N),activate(XS)),activate(X))
,splitAt#(activate(N),activate(XS))
,activate#(N)
,activate#(XS)
,activate#(X))
U64#(pair(YS,ZS),X) -> c_14(activate#(X))
U71#(tt(),XS) -> c_15(U72#(tt(),activate(XS)),activate#(XS))
U72#(tt(),XS) -> c_16(activate#(XS))
U81#(tt(),N,XS) -> c_17(U82#(tt(),activate(N),activate(XS)),activate#(N),activate#(XS))
U82#(tt(),N,XS) -> c_18(fst#(splitAt(activate(N),activate(XS)))
,splitAt#(activate(N),activate(XS))
,activate#(N)
,activate#(XS))
activate#(X) -> c_19()
activate#(n__natsFrom(X)) -> c_20(natsFrom#(X))
afterNth#(N,XS) -> c_21(U11#(tt(),N,XS))
fst#(pair(X,Y)) -> c_22(U21#(tt(),X))
head#(cons(N,XS)) -> c_23(U31#(tt(),N))
natsFrom#(N) -> c_24()
natsFrom#(X) -> c_25()
sel#(N,XS) -> c_26(U41#(tt(),N,XS))
snd#(pair(X,Y)) -> c_27(U51#(tt(),Y))
splitAt#(0(),XS) -> c_28()
splitAt#(s(N),cons(X,XS)) -> c_29(U61#(tt(),N,X,activate(XS)),activate#(XS))
tail#(cons(N,XS)) -> c_30(U71#(tt(),activate(XS)),activate#(XS))
take#(N,XS) -> c_31(U81#(tt(),N,XS))
- Weak TRS:
U11(tt(),N,XS) -> U12(tt(),activate(N),activate(XS))
U12(tt(),N,XS) -> snd(splitAt(activate(N),activate(XS)))
U51(tt(),Y) -> U52(tt(),activate(Y))
U52(tt(),Y) -> activate(Y)
U61(tt(),N,X,XS) -> U62(tt(),activate(N),activate(X),activate(XS))
U62(tt(),N,X,XS) -> U63(tt(),activate(N),activate(X),activate(XS))
U63(tt(),N,X,XS) -> U64(splitAt(activate(N),activate(XS)),activate(X))
U64(pair(YS,ZS),X) -> pair(cons(activate(X),YS),ZS)
activate(X) -> X
activate(n__natsFrom(X)) -> natsFrom(X)
afterNth(N,XS) -> U11(tt(),N,XS)
natsFrom(N) -> cons(N,n__natsFrom(s(N)))
natsFrom(X) -> n__natsFrom(X)
snd(pair(X,Y)) -> U51(tt(),Y)
splitAt(0(),XS) -> pair(nil(),XS)
splitAt(s(N),cons(X,XS)) -> U61(tt(),N,X,activate(XS))
- Signature:
{U11/3,U12/3,U21/2,U22/2,U31/2,U32/2,U41/3,U42/3,U51/2,U52/2,U61/4,U62/4,U63/4,U64/2,U71/2,U72/2,U81/3,U82/3
,activate/1,afterNth/2,fst/1,head/1,natsFrom/1,sel/2,snd/1,splitAt/2,tail/1,take/2,U11#/3,U12#/3,U21#/2
,U22#/2,U31#/2,U32#/2,U41#/3,U42#/3,U51#/2,U52#/2,U61#/4,U62#/4,U63#/4,U64#/2,U71#/2,U72#/2,U81#/3,U82#/3
,activate#/1,afterNth#/2,fst#/1,head#/1,natsFrom#/1,sel#/2,snd#/1,splitAt#/2,tail#/1,take#/2} / {0/0,cons/2
,n__natsFrom/1,nil/0,pair/2,s/1,tt/0,c_1/3,c_2/4,c_3/2,c_4/1,c_5/2,c_6/1,c_7/3,c_8/4,c_9/2,c_10/1,c_11/4
,c_12/4,c_13/5,c_14/1,c_15/2,c_16/1,c_17/3,c_18/4,c_19/0,c_20/1,c_21/1,c_22/1,c_23/1,c_24/0,c_25/0,c_26/1
,c_27/1,c_28/0,c_29/2,c_30/2,c_31/1}
- Obligation:
innermost runtime complexity wrt. defined symbols {U11#,U12#,U21#,U22#,U31#,U32#,U41#,U42#,U51#,U52#,U61#
,U62#,U63#,U64#,U71#,U72#,U81#,U82#,activate#,afterNth#,fst#,head#,natsFrom#,sel#,snd#,splitAt#,tail#
,take#} and constructors {0,cons,n__natsFrom,nil,pair,s,tt}
+ Applied Processor:
PredecessorEstimation {onSelection = all simple predecessor estimation selector}
+ Details:
We estimate the number of application of
{19,24,25,28}
by application of
Pre({19,24,25,28}) = {1,2,3,4,5,6,7,8,9,10,11,12,13,14,15,16,17,18,20,29,30}.
Here rules are labelled as follows:
1: U11#(tt(),N,XS) -> c_1(U12#(tt(),activate(N),activate(XS)),activate#(N),activate#(XS))
2: U12#(tt(),N,XS) -> c_2(snd#(splitAt(activate(N),activate(XS)))
,splitAt#(activate(N),activate(XS))
,activate#(N)
,activate#(XS))
3: U21#(tt(),X) -> c_3(U22#(tt(),activate(X)),activate#(X))
4: U22#(tt(),X) -> c_4(activate#(X))
5: U31#(tt(),N) -> c_5(U32#(tt(),activate(N)),activate#(N))
6: U32#(tt(),N) -> c_6(activate#(N))
7: U41#(tt(),N,XS) -> c_7(U42#(tt(),activate(N),activate(XS)),activate#(N),activate#(XS))
8: U42#(tt(),N,XS) -> c_8(head#(afterNth(activate(N),activate(XS)))
,afterNth#(activate(N),activate(XS))
,activate#(N)
,activate#(XS))
9: U51#(tt(),Y) -> c_9(U52#(tt(),activate(Y)),activate#(Y))
10: U52#(tt(),Y) -> c_10(activate#(Y))
11: U61#(tt(),N,X,XS) -> c_11(U62#(tt(),activate(N),activate(X),activate(XS))
,activate#(N)
,activate#(X)
,activate#(XS))
12: U62#(tt(),N,X,XS) -> c_12(U63#(tt(),activate(N),activate(X),activate(XS))
,activate#(N)
,activate#(X)
,activate#(XS))
13: U63#(tt(),N,X,XS) -> c_13(U64#(splitAt(activate(N),activate(XS)),activate(X))
,splitAt#(activate(N),activate(XS))
,activate#(N)
,activate#(XS)
,activate#(X))
14: U64#(pair(YS,ZS),X) -> c_14(activate#(X))
15: U71#(tt(),XS) -> c_15(U72#(tt(),activate(XS)),activate#(XS))
16: U72#(tt(),XS) -> c_16(activate#(XS))
17: U81#(tt(),N,XS) -> c_17(U82#(tt(),activate(N),activate(XS)),activate#(N),activate#(XS))
18: U82#(tt(),N,XS) -> c_18(fst#(splitAt(activate(N),activate(XS)))
,splitAt#(activate(N),activate(XS))
,activate#(N)
,activate#(XS))
19: activate#(X) -> c_19()
20: activate#(n__natsFrom(X)) -> c_20(natsFrom#(X))
21: afterNth#(N,XS) -> c_21(U11#(tt(),N,XS))
22: fst#(pair(X,Y)) -> c_22(U21#(tt(),X))
23: head#(cons(N,XS)) -> c_23(U31#(tt(),N))
24: natsFrom#(N) -> c_24()
25: natsFrom#(X) -> c_25()
26: sel#(N,XS) -> c_26(U41#(tt(),N,XS))
27: snd#(pair(X,Y)) -> c_27(U51#(tt(),Y))
28: splitAt#(0(),XS) -> c_28()
29: splitAt#(s(N),cons(X,XS)) -> c_29(U61#(tt(),N,X,activate(XS)),activate#(XS))
30: tail#(cons(N,XS)) -> c_30(U71#(tt(),activate(XS)),activate#(XS))
31: take#(N,XS) -> c_31(U81#(tt(),N,XS))
* Step 5: PredecessorEstimation WORST_CASE(?,O(n^1))
+ Considered Problem:
- Strict DPs:
U11#(tt(),N,XS) -> c_1(U12#(tt(),activate(N),activate(XS)),activate#(N),activate#(XS))
U12#(tt(),N,XS) -> c_2(snd#(splitAt(activate(N),activate(XS)))
,splitAt#(activate(N),activate(XS))
,activate#(N)
,activate#(XS))
U21#(tt(),X) -> c_3(U22#(tt(),activate(X)),activate#(X))
U22#(tt(),X) -> c_4(activate#(X))
U31#(tt(),N) -> c_5(U32#(tt(),activate(N)),activate#(N))
U32#(tt(),N) -> c_6(activate#(N))
U41#(tt(),N,XS) -> c_7(U42#(tt(),activate(N),activate(XS)),activate#(N),activate#(XS))
U42#(tt(),N,XS) -> c_8(head#(afterNth(activate(N),activate(XS)))
,afterNth#(activate(N),activate(XS))
,activate#(N)
,activate#(XS))
U51#(tt(),Y) -> c_9(U52#(tt(),activate(Y)),activate#(Y))
U52#(tt(),Y) -> c_10(activate#(Y))
U61#(tt(),N,X,XS) -> c_11(U62#(tt(),activate(N),activate(X),activate(XS))
,activate#(N)
,activate#(X)
,activate#(XS))
U62#(tt(),N,X,XS) -> c_12(U63#(tt(),activate(N),activate(X),activate(XS))
,activate#(N)
,activate#(X)
,activate#(XS))
U63#(tt(),N,X,XS) -> c_13(U64#(splitAt(activate(N),activate(XS)),activate(X))
,splitAt#(activate(N),activate(XS))
,activate#(N)
,activate#(XS)
,activate#(X))
U64#(pair(YS,ZS),X) -> c_14(activate#(X))
U71#(tt(),XS) -> c_15(U72#(tt(),activate(XS)),activate#(XS))
U72#(tt(),XS) -> c_16(activate#(XS))
U81#(tt(),N,XS) -> c_17(U82#(tt(),activate(N),activate(XS)),activate#(N),activate#(XS))
U82#(tt(),N,XS) -> c_18(fst#(splitAt(activate(N),activate(XS)))
,splitAt#(activate(N),activate(XS))
,activate#(N)
,activate#(XS))
activate#(n__natsFrom(X)) -> c_20(natsFrom#(X))
afterNth#(N,XS) -> c_21(U11#(tt(),N,XS))
fst#(pair(X,Y)) -> c_22(U21#(tt(),X))
head#(cons(N,XS)) -> c_23(U31#(tt(),N))
sel#(N,XS) -> c_26(U41#(tt(),N,XS))
snd#(pair(X,Y)) -> c_27(U51#(tt(),Y))
splitAt#(s(N),cons(X,XS)) -> c_29(U61#(tt(),N,X,activate(XS)),activate#(XS))
tail#(cons(N,XS)) -> c_30(U71#(tt(),activate(XS)),activate#(XS))
take#(N,XS) -> c_31(U81#(tt(),N,XS))
- Weak DPs:
activate#(X) -> c_19()
natsFrom#(N) -> c_24()
natsFrom#(X) -> c_25()
splitAt#(0(),XS) -> c_28()
- Weak TRS:
U11(tt(),N,XS) -> U12(tt(),activate(N),activate(XS))
U12(tt(),N,XS) -> snd(splitAt(activate(N),activate(XS)))
U51(tt(),Y) -> U52(tt(),activate(Y))
U52(tt(),Y) -> activate(Y)
U61(tt(),N,X,XS) -> U62(tt(),activate(N),activate(X),activate(XS))
U62(tt(),N,X,XS) -> U63(tt(),activate(N),activate(X),activate(XS))
U63(tt(),N,X,XS) -> U64(splitAt(activate(N),activate(XS)),activate(X))
U64(pair(YS,ZS),X) -> pair(cons(activate(X),YS),ZS)
activate(X) -> X
activate(n__natsFrom(X)) -> natsFrom(X)
afterNth(N,XS) -> U11(tt(),N,XS)
natsFrom(N) -> cons(N,n__natsFrom(s(N)))
natsFrom(X) -> n__natsFrom(X)
snd(pair(X,Y)) -> U51(tt(),Y)
splitAt(0(),XS) -> pair(nil(),XS)
splitAt(s(N),cons(X,XS)) -> U61(tt(),N,X,activate(XS))
- Signature:
{U11/3,U12/3,U21/2,U22/2,U31/2,U32/2,U41/3,U42/3,U51/2,U52/2,U61/4,U62/4,U63/4,U64/2,U71/2,U72/2,U81/3,U82/3
,activate/1,afterNth/2,fst/1,head/1,natsFrom/1,sel/2,snd/1,splitAt/2,tail/1,take/2,U11#/3,U12#/3,U21#/2
,U22#/2,U31#/2,U32#/2,U41#/3,U42#/3,U51#/2,U52#/2,U61#/4,U62#/4,U63#/4,U64#/2,U71#/2,U72#/2,U81#/3,U82#/3
,activate#/1,afterNth#/2,fst#/1,head#/1,natsFrom#/1,sel#/2,snd#/1,splitAt#/2,tail#/1,take#/2} / {0/0,cons/2
,n__natsFrom/1,nil/0,pair/2,s/1,tt/0,c_1/3,c_2/4,c_3/2,c_4/1,c_5/2,c_6/1,c_7/3,c_8/4,c_9/2,c_10/1,c_11/4
,c_12/4,c_13/5,c_14/1,c_15/2,c_16/1,c_17/3,c_18/4,c_19/0,c_20/1,c_21/1,c_22/1,c_23/1,c_24/0,c_25/0,c_26/1
,c_27/1,c_28/0,c_29/2,c_30/2,c_31/1}
- Obligation:
innermost runtime complexity wrt. defined symbols {U11#,U12#,U21#,U22#,U31#,U32#,U41#,U42#,U51#,U52#,U61#
,U62#,U63#,U64#,U71#,U72#,U81#,U82#,activate#,afterNth#,fst#,head#,natsFrom#,sel#,snd#,splitAt#,tail#
,take#} and constructors {0,cons,n__natsFrom,nil,pair,s,tt}
+ Applied Processor:
PredecessorEstimation {onSelection = all simple predecessor estimation selector}
+ Details:
We estimate the number of application of
{19}
by application of
Pre({19}) = {1,2,3,4,5,6,7,8,9,10,11,12,13,14,15,16,17,18,25,26}.
Here rules are labelled as follows:
1: U11#(tt(),N,XS) -> c_1(U12#(tt(),activate(N),activate(XS)),activate#(N),activate#(XS))
2: U12#(tt(),N,XS) -> c_2(snd#(splitAt(activate(N),activate(XS)))
,splitAt#(activate(N),activate(XS))
,activate#(N)
,activate#(XS))
3: U21#(tt(),X) -> c_3(U22#(tt(),activate(X)),activate#(X))
4: U22#(tt(),X) -> c_4(activate#(X))
5: U31#(tt(),N) -> c_5(U32#(tt(),activate(N)),activate#(N))
6: U32#(tt(),N) -> c_6(activate#(N))
7: U41#(tt(),N,XS) -> c_7(U42#(tt(),activate(N),activate(XS)),activate#(N),activate#(XS))
8: U42#(tt(),N,XS) -> c_8(head#(afterNth(activate(N),activate(XS)))
,afterNth#(activate(N),activate(XS))
,activate#(N)
,activate#(XS))
9: U51#(tt(),Y) -> c_9(U52#(tt(),activate(Y)),activate#(Y))
10: U52#(tt(),Y) -> c_10(activate#(Y))
11: U61#(tt(),N,X,XS) -> c_11(U62#(tt(),activate(N),activate(X),activate(XS))
,activate#(N)
,activate#(X)
,activate#(XS))
12: U62#(tt(),N,X,XS) -> c_12(U63#(tt(),activate(N),activate(X),activate(XS))
,activate#(N)
,activate#(X)
,activate#(XS))
13: U63#(tt(),N,X,XS) -> c_13(U64#(splitAt(activate(N),activate(XS)),activate(X))
,splitAt#(activate(N),activate(XS))
,activate#(N)
,activate#(XS)
,activate#(X))
14: U64#(pair(YS,ZS),X) -> c_14(activate#(X))
15: U71#(tt(),XS) -> c_15(U72#(tt(),activate(XS)),activate#(XS))
16: U72#(tt(),XS) -> c_16(activate#(XS))
17: U81#(tt(),N,XS) -> c_17(U82#(tt(),activate(N),activate(XS)),activate#(N),activate#(XS))
18: U82#(tt(),N,XS) -> c_18(fst#(splitAt(activate(N),activate(XS)))
,splitAt#(activate(N),activate(XS))
,activate#(N)
,activate#(XS))
19: activate#(n__natsFrom(X)) -> c_20(natsFrom#(X))
20: afterNth#(N,XS) -> c_21(U11#(tt(),N,XS))
21: fst#(pair(X,Y)) -> c_22(U21#(tt(),X))
22: head#(cons(N,XS)) -> c_23(U31#(tt(),N))
23: sel#(N,XS) -> c_26(U41#(tt(),N,XS))
24: snd#(pair(X,Y)) -> c_27(U51#(tt(),Y))
25: splitAt#(s(N),cons(X,XS)) -> c_29(U61#(tt(),N,X,activate(XS)),activate#(XS))
26: tail#(cons(N,XS)) -> c_30(U71#(tt(),activate(XS)),activate#(XS))
27: take#(N,XS) -> c_31(U81#(tt(),N,XS))
28: activate#(X) -> c_19()
29: natsFrom#(N) -> c_24()
30: natsFrom#(X) -> c_25()
31: splitAt#(0(),XS) -> c_28()
* Step 6: PredecessorEstimation WORST_CASE(?,O(n^1))
+ Considered Problem:
- Strict DPs:
U11#(tt(),N,XS) -> c_1(U12#(tt(),activate(N),activate(XS)),activate#(N),activate#(XS))
U12#(tt(),N,XS) -> c_2(snd#(splitAt(activate(N),activate(XS)))
,splitAt#(activate(N),activate(XS))
,activate#(N)
,activate#(XS))
U21#(tt(),X) -> c_3(U22#(tt(),activate(X)),activate#(X))
U22#(tt(),X) -> c_4(activate#(X))
U31#(tt(),N) -> c_5(U32#(tt(),activate(N)),activate#(N))
U32#(tt(),N) -> c_6(activate#(N))
U41#(tt(),N,XS) -> c_7(U42#(tt(),activate(N),activate(XS)),activate#(N),activate#(XS))
U42#(tt(),N,XS) -> c_8(head#(afterNth(activate(N),activate(XS)))
,afterNth#(activate(N),activate(XS))
,activate#(N)
,activate#(XS))
U51#(tt(),Y) -> c_9(U52#(tt(),activate(Y)),activate#(Y))
U52#(tt(),Y) -> c_10(activate#(Y))
U61#(tt(),N,X,XS) -> c_11(U62#(tt(),activate(N),activate(X),activate(XS))
,activate#(N)
,activate#(X)
,activate#(XS))
U62#(tt(),N,X,XS) -> c_12(U63#(tt(),activate(N),activate(X),activate(XS))
,activate#(N)
,activate#(X)
,activate#(XS))
U63#(tt(),N,X,XS) -> c_13(U64#(splitAt(activate(N),activate(XS)),activate(X))
,splitAt#(activate(N),activate(XS))
,activate#(N)
,activate#(XS)
,activate#(X))
U64#(pair(YS,ZS),X) -> c_14(activate#(X))
U71#(tt(),XS) -> c_15(U72#(tt(),activate(XS)),activate#(XS))
U72#(tt(),XS) -> c_16(activate#(XS))
U81#(tt(),N,XS) -> c_17(U82#(tt(),activate(N),activate(XS)),activate#(N),activate#(XS))
U82#(tt(),N,XS) -> c_18(fst#(splitAt(activate(N),activate(XS)))
,splitAt#(activate(N),activate(XS))
,activate#(N)
,activate#(XS))
afterNth#(N,XS) -> c_21(U11#(tt(),N,XS))
fst#(pair(X,Y)) -> c_22(U21#(tt(),X))
head#(cons(N,XS)) -> c_23(U31#(tt(),N))
sel#(N,XS) -> c_26(U41#(tt(),N,XS))
snd#(pair(X,Y)) -> c_27(U51#(tt(),Y))
splitAt#(s(N),cons(X,XS)) -> c_29(U61#(tt(),N,X,activate(XS)),activate#(XS))
tail#(cons(N,XS)) -> c_30(U71#(tt(),activate(XS)),activate#(XS))
take#(N,XS) -> c_31(U81#(tt(),N,XS))
- Weak DPs:
activate#(X) -> c_19()
activate#(n__natsFrom(X)) -> c_20(natsFrom#(X))
natsFrom#(N) -> c_24()
natsFrom#(X) -> c_25()
splitAt#(0(),XS) -> c_28()
- Weak TRS:
U11(tt(),N,XS) -> U12(tt(),activate(N),activate(XS))
U12(tt(),N,XS) -> snd(splitAt(activate(N),activate(XS)))
U51(tt(),Y) -> U52(tt(),activate(Y))
U52(tt(),Y) -> activate(Y)
U61(tt(),N,X,XS) -> U62(tt(),activate(N),activate(X),activate(XS))
U62(tt(),N,X,XS) -> U63(tt(),activate(N),activate(X),activate(XS))
U63(tt(),N,X,XS) -> U64(splitAt(activate(N),activate(XS)),activate(X))
U64(pair(YS,ZS),X) -> pair(cons(activate(X),YS),ZS)
activate(X) -> X
activate(n__natsFrom(X)) -> natsFrom(X)
afterNth(N,XS) -> U11(tt(),N,XS)
natsFrom(N) -> cons(N,n__natsFrom(s(N)))
natsFrom(X) -> n__natsFrom(X)
snd(pair(X,Y)) -> U51(tt(),Y)
splitAt(0(),XS) -> pair(nil(),XS)
splitAt(s(N),cons(X,XS)) -> U61(tt(),N,X,activate(XS))
- Signature:
{U11/3,U12/3,U21/2,U22/2,U31/2,U32/2,U41/3,U42/3,U51/2,U52/2,U61/4,U62/4,U63/4,U64/2,U71/2,U72/2,U81/3,U82/3
,activate/1,afterNth/2,fst/1,head/1,natsFrom/1,sel/2,snd/1,splitAt/2,tail/1,take/2,U11#/3,U12#/3,U21#/2
,U22#/2,U31#/2,U32#/2,U41#/3,U42#/3,U51#/2,U52#/2,U61#/4,U62#/4,U63#/4,U64#/2,U71#/2,U72#/2,U81#/3,U82#/3
,activate#/1,afterNth#/2,fst#/1,head#/1,natsFrom#/1,sel#/2,snd#/1,splitAt#/2,tail#/1,take#/2} / {0/0,cons/2
,n__natsFrom/1,nil/0,pair/2,s/1,tt/0,c_1/3,c_2/4,c_3/2,c_4/1,c_5/2,c_6/1,c_7/3,c_8/4,c_9/2,c_10/1,c_11/4
,c_12/4,c_13/5,c_14/1,c_15/2,c_16/1,c_17/3,c_18/4,c_19/0,c_20/1,c_21/1,c_22/1,c_23/1,c_24/0,c_25/0,c_26/1
,c_27/1,c_28/0,c_29/2,c_30/2,c_31/1}
- Obligation:
innermost runtime complexity wrt. defined symbols {U11#,U12#,U21#,U22#,U31#,U32#,U41#,U42#,U51#,U52#,U61#
,U62#,U63#,U64#,U71#,U72#,U81#,U82#,activate#,afterNth#,fst#,head#,natsFrom#,sel#,snd#,splitAt#,tail#
,take#} and constructors {0,cons,n__natsFrom,nil,pair,s,tt}
+ Applied Processor:
PredecessorEstimation {onSelection = all simple predecessor estimation selector}
+ Details:
We estimate the number of application of
{4,6,10,14,16}
by application of
Pre({4,6,10,14,16}) = {3,5,9,13,15}.
Here rules are labelled as follows:
1: U11#(tt(),N,XS) -> c_1(U12#(tt(),activate(N),activate(XS)),activate#(N),activate#(XS))
2: U12#(tt(),N,XS) -> c_2(snd#(splitAt(activate(N),activate(XS)))
,splitAt#(activate(N),activate(XS))
,activate#(N)
,activate#(XS))
3: U21#(tt(),X) -> c_3(U22#(tt(),activate(X)),activate#(X))
4: U22#(tt(),X) -> c_4(activate#(X))
5: U31#(tt(),N) -> c_5(U32#(tt(),activate(N)),activate#(N))
6: U32#(tt(),N) -> c_6(activate#(N))
7: U41#(tt(),N,XS) -> c_7(U42#(tt(),activate(N),activate(XS)),activate#(N),activate#(XS))
8: U42#(tt(),N,XS) -> c_8(head#(afterNth(activate(N),activate(XS)))
,afterNth#(activate(N),activate(XS))
,activate#(N)
,activate#(XS))
9: U51#(tt(),Y) -> c_9(U52#(tt(),activate(Y)),activate#(Y))
10: U52#(tt(),Y) -> c_10(activate#(Y))
11: U61#(tt(),N,X,XS) -> c_11(U62#(tt(),activate(N),activate(X),activate(XS))
,activate#(N)
,activate#(X)
,activate#(XS))
12: U62#(tt(),N,X,XS) -> c_12(U63#(tt(),activate(N),activate(X),activate(XS))
,activate#(N)
,activate#(X)
,activate#(XS))
13: U63#(tt(),N,X,XS) -> c_13(U64#(splitAt(activate(N),activate(XS)),activate(X))
,splitAt#(activate(N),activate(XS))
,activate#(N)
,activate#(XS)
,activate#(X))
14: U64#(pair(YS,ZS),X) -> c_14(activate#(X))
15: U71#(tt(),XS) -> c_15(U72#(tt(),activate(XS)),activate#(XS))
16: U72#(tt(),XS) -> c_16(activate#(XS))
17: U81#(tt(),N,XS) -> c_17(U82#(tt(),activate(N),activate(XS)),activate#(N),activate#(XS))
18: U82#(tt(),N,XS) -> c_18(fst#(splitAt(activate(N),activate(XS)))
,splitAt#(activate(N),activate(XS))
,activate#(N)
,activate#(XS))
19: afterNth#(N,XS) -> c_21(U11#(tt(),N,XS))
20: fst#(pair(X,Y)) -> c_22(U21#(tt(),X))
21: head#(cons(N,XS)) -> c_23(U31#(tt(),N))
22: sel#(N,XS) -> c_26(U41#(tt(),N,XS))
23: snd#(pair(X,Y)) -> c_27(U51#(tt(),Y))
24: splitAt#(s(N),cons(X,XS)) -> c_29(U61#(tt(),N,X,activate(XS)),activate#(XS))
25: tail#(cons(N,XS)) -> c_30(U71#(tt(),activate(XS)),activate#(XS))
26: take#(N,XS) -> c_31(U81#(tt(),N,XS))
27: activate#(X) -> c_19()
28: activate#(n__natsFrom(X)) -> c_20(natsFrom#(X))
29: natsFrom#(N) -> c_24()
30: natsFrom#(X) -> c_25()
31: splitAt#(0(),XS) -> c_28()
* Step 7: PredecessorEstimation WORST_CASE(?,O(n^1))
+ Considered Problem:
- Strict DPs:
U11#(tt(),N,XS) -> c_1(U12#(tt(),activate(N),activate(XS)),activate#(N),activate#(XS))
U12#(tt(),N,XS) -> c_2(snd#(splitAt(activate(N),activate(XS)))
,splitAt#(activate(N),activate(XS))
,activate#(N)
,activate#(XS))
U21#(tt(),X) -> c_3(U22#(tt(),activate(X)),activate#(X))
U31#(tt(),N) -> c_5(U32#(tt(),activate(N)),activate#(N))
U41#(tt(),N,XS) -> c_7(U42#(tt(),activate(N),activate(XS)),activate#(N),activate#(XS))
U42#(tt(),N,XS) -> c_8(head#(afterNth(activate(N),activate(XS)))
,afterNth#(activate(N),activate(XS))
,activate#(N)
,activate#(XS))
U51#(tt(),Y) -> c_9(U52#(tt(),activate(Y)),activate#(Y))
U61#(tt(),N,X,XS) -> c_11(U62#(tt(),activate(N),activate(X),activate(XS))
,activate#(N)
,activate#(X)
,activate#(XS))
U62#(tt(),N,X,XS) -> c_12(U63#(tt(),activate(N),activate(X),activate(XS))
,activate#(N)
,activate#(X)
,activate#(XS))
U63#(tt(),N,X,XS) -> c_13(U64#(splitAt(activate(N),activate(XS)),activate(X))
,splitAt#(activate(N),activate(XS))
,activate#(N)
,activate#(XS)
,activate#(X))
U71#(tt(),XS) -> c_15(U72#(tt(),activate(XS)),activate#(XS))
U81#(tt(),N,XS) -> c_17(U82#(tt(),activate(N),activate(XS)),activate#(N),activate#(XS))
U82#(tt(),N,XS) -> c_18(fst#(splitAt(activate(N),activate(XS)))
,splitAt#(activate(N),activate(XS))
,activate#(N)
,activate#(XS))
afterNth#(N,XS) -> c_21(U11#(tt(),N,XS))
fst#(pair(X,Y)) -> c_22(U21#(tt(),X))
head#(cons(N,XS)) -> c_23(U31#(tt(),N))
sel#(N,XS) -> c_26(U41#(tt(),N,XS))
snd#(pair(X,Y)) -> c_27(U51#(tt(),Y))
splitAt#(s(N),cons(X,XS)) -> c_29(U61#(tt(),N,X,activate(XS)),activate#(XS))
tail#(cons(N,XS)) -> c_30(U71#(tt(),activate(XS)),activate#(XS))
take#(N,XS) -> c_31(U81#(tt(),N,XS))
- Weak DPs:
U22#(tt(),X) -> c_4(activate#(X))
U32#(tt(),N) -> c_6(activate#(N))
U52#(tt(),Y) -> c_10(activate#(Y))
U64#(pair(YS,ZS),X) -> c_14(activate#(X))
U72#(tt(),XS) -> c_16(activate#(XS))
activate#(X) -> c_19()
activate#(n__natsFrom(X)) -> c_20(natsFrom#(X))
natsFrom#(N) -> c_24()
natsFrom#(X) -> c_25()
splitAt#(0(),XS) -> c_28()
- Weak TRS:
U11(tt(),N,XS) -> U12(tt(),activate(N),activate(XS))
U12(tt(),N,XS) -> snd(splitAt(activate(N),activate(XS)))
U51(tt(),Y) -> U52(tt(),activate(Y))
U52(tt(),Y) -> activate(Y)
U61(tt(),N,X,XS) -> U62(tt(),activate(N),activate(X),activate(XS))
U62(tt(),N,X,XS) -> U63(tt(),activate(N),activate(X),activate(XS))
U63(tt(),N,X,XS) -> U64(splitAt(activate(N),activate(XS)),activate(X))
U64(pair(YS,ZS),X) -> pair(cons(activate(X),YS),ZS)
activate(X) -> X
activate(n__natsFrom(X)) -> natsFrom(X)
afterNth(N,XS) -> U11(tt(),N,XS)
natsFrom(N) -> cons(N,n__natsFrom(s(N)))
natsFrom(X) -> n__natsFrom(X)
snd(pair(X,Y)) -> U51(tt(),Y)
splitAt(0(),XS) -> pair(nil(),XS)
splitAt(s(N),cons(X,XS)) -> U61(tt(),N,X,activate(XS))
- Signature:
{U11/3,U12/3,U21/2,U22/2,U31/2,U32/2,U41/3,U42/3,U51/2,U52/2,U61/4,U62/4,U63/4,U64/2,U71/2,U72/2,U81/3,U82/3
,activate/1,afterNth/2,fst/1,head/1,natsFrom/1,sel/2,snd/1,splitAt/2,tail/1,take/2,U11#/3,U12#/3,U21#/2
,U22#/2,U31#/2,U32#/2,U41#/3,U42#/3,U51#/2,U52#/2,U61#/4,U62#/4,U63#/4,U64#/2,U71#/2,U72#/2,U81#/3,U82#/3
,activate#/1,afterNth#/2,fst#/1,head#/1,natsFrom#/1,sel#/2,snd#/1,splitAt#/2,tail#/1,take#/2} / {0/0,cons/2
,n__natsFrom/1,nil/0,pair/2,s/1,tt/0,c_1/3,c_2/4,c_3/2,c_4/1,c_5/2,c_6/1,c_7/3,c_8/4,c_9/2,c_10/1,c_11/4
,c_12/4,c_13/5,c_14/1,c_15/2,c_16/1,c_17/3,c_18/4,c_19/0,c_20/1,c_21/1,c_22/1,c_23/1,c_24/0,c_25/0,c_26/1
,c_27/1,c_28/0,c_29/2,c_30/2,c_31/1}
- Obligation:
innermost runtime complexity wrt. defined symbols {U11#,U12#,U21#,U22#,U31#,U32#,U41#,U42#,U51#,U52#,U61#
,U62#,U63#,U64#,U71#,U72#,U81#,U82#,activate#,afterNth#,fst#,head#,natsFrom#,sel#,snd#,splitAt#,tail#
,take#} and constructors {0,cons,n__natsFrom,nil,pair,s,tt}
+ Applied Processor:
PredecessorEstimation {onSelection = all simple predecessor estimation selector}
+ Details:
We estimate the number of application of
{3,4,7,11}
by application of
Pre({3,4,7,11}) = {15,16,18,20}.
Here rules are labelled as follows:
1: U11#(tt(),N,XS) -> c_1(U12#(tt(),activate(N),activate(XS)),activate#(N),activate#(XS))
2: U12#(tt(),N,XS) -> c_2(snd#(splitAt(activate(N),activate(XS)))
,splitAt#(activate(N),activate(XS))
,activate#(N)
,activate#(XS))
3: U21#(tt(),X) -> c_3(U22#(tt(),activate(X)),activate#(X))
4: U31#(tt(),N) -> c_5(U32#(tt(),activate(N)),activate#(N))
5: U41#(tt(),N,XS) -> c_7(U42#(tt(),activate(N),activate(XS)),activate#(N),activate#(XS))
6: U42#(tt(),N,XS) -> c_8(head#(afterNth(activate(N),activate(XS)))
,afterNth#(activate(N),activate(XS))
,activate#(N)
,activate#(XS))
7: U51#(tt(),Y) -> c_9(U52#(tt(),activate(Y)),activate#(Y))
8: U61#(tt(),N,X,XS) -> c_11(U62#(tt(),activate(N),activate(X),activate(XS))
,activate#(N)
,activate#(X)
,activate#(XS))
9: U62#(tt(),N,X,XS) -> c_12(U63#(tt(),activate(N),activate(X),activate(XS))
,activate#(N)
,activate#(X)
,activate#(XS))
10: U63#(tt(),N,X,XS) -> c_13(U64#(splitAt(activate(N),activate(XS)),activate(X))
,splitAt#(activate(N),activate(XS))
,activate#(N)
,activate#(XS)
,activate#(X))
11: U71#(tt(),XS) -> c_15(U72#(tt(),activate(XS)),activate#(XS))
12: U81#(tt(),N,XS) -> c_17(U82#(tt(),activate(N),activate(XS)),activate#(N),activate#(XS))
13: U82#(tt(),N,XS) -> c_18(fst#(splitAt(activate(N),activate(XS)))
,splitAt#(activate(N),activate(XS))
,activate#(N)
,activate#(XS))
14: afterNth#(N,XS) -> c_21(U11#(tt(),N,XS))
15: fst#(pair(X,Y)) -> c_22(U21#(tt(),X))
16: head#(cons(N,XS)) -> c_23(U31#(tt(),N))
17: sel#(N,XS) -> c_26(U41#(tt(),N,XS))
18: snd#(pair(X,Y)) -> c_27(U51#(tt(),Y))
19: splitAt#(s(N),cons(X,XS)) -> c_29(U61#(tt(),N,X,activate(XS)),activate#(XS))
20: tail#(cons(N,XS)) -> c_30(U71#(tt(),activate(XS)),activate#(XS))
21: take#(N,XS) -> c_31(U81#(tt(),N,XS))
22: U22#(tt(),X) -> c_4(activate#(X))
23: U32#(tt(),N) -> c_6(activate#(N))
24: U52#(tt(),Y) -> c_10(activate#(Y))
25: U64#(pair(YS,ZS),X) -> c_14(activate#(X))
26: U72#(tt(),XS) -> c_16(activate#(XS))
27: activate#(X) -> c_19()
28: activate#(n__natsFrom(X)) -> c_20(natsFrom#(X))
29: natsFrom#(N) -> c_24()
30: natsFrom#(X) -> c_25()
31: splitAt#(0(),XS) -> c_28()
* Step 8: PredecessorEstimation WORST_CASE(?,O(n^1))
+ Considered Problem:
- Strict DPs:
U11#(tt(),N,XS) -> c_1(U12#(tt(),activate(N),activate(XS)),activate#(N),activate#(XS))
U12#(tt(),N,XS) -> c_2(snd#(splitAt(activate(N),activate(XS)))
,splitAt#(activate(N),activate(XS))
,activate#(N)
,activate#(XS))
U41#(tt(),N,XS) -> c_7(U42#(tt(),activate(N),activate(XS)),activate#(N),activate#(XS))
U42#(tt(),N,XS) -> c_8(head#(afterNth(activate(N),activate(XS)))
,afterNth#(activate(N),activate(XS))
,activate#(N)
,activate#(XS))
U61#(tt(),N,X,XS) -> c_11(U62#(tt(),activate(N),activate(X),activate(XS))
,activate#(N)
,activate#(X)
,activate#(XS))
U62#(tt(),N,X,XS) -> c_12(U63#(tt(),activate(N),activate(X),activate(XS))
,activate#(N)
,activate#(X)
,activate#(XS))
U63#(tt(),N,X,XS) -> c_13(U64#(splitAt(activate(N),activate(XS)),activate(X))
,splitAt#(activate(N),activate(XS))
,activate#(N)
,activate#(XS)
,activate#(X))
U81#(tt(),N,XS) -> c_17(U82#(tt(),activate(N),activate(XS)),activate#(N),activate#(XS))
U82#(tt(),N,XS) -> c_18(fst#(splitAt(activate(N),activate(XS)))
,splitAt#(activate(N),activate(XS))
,activate#(N)
,activate#(XS))
afterNth#(N,XS) -> c_21(U11#(tt(),N,XS))
fst#(pair(X,Y)) -> c_22(U21#(tt(),X))
head#(cons(N,XS)) -> c_23(U31#(tt(),N))
sel#(N,XS) -> c_26(U41#(tt(),N,XS))
snd#(pair(X,Y)) -> c_27(U51#(tt(),Y))
splitAt#(s(N),cons(X,XS)) -> c_29(U61#(tt(),N,X,activate(XS)),activate#(XS))
tail#(cons(N,XS)) -> c_30(U71#(tt(),activate(XS)),activate#(XS))
take#(N,XS) -> c_31(U81#(tt(),N,XS))
- Weak DPs:
U21#(tt(),X) -> c_3(U22#(tt(),activate(X)),activate#(X))
U22#(tt(),X) -> c_4(activate#(X))
U31#(tt(),N) -> c_5(U32#(tt(),activate(N)),activate#(N))
U32#(tt(),N) -> c_6(activate#(N))
U51#(tt(),Y) -> c_9(U52#(tt(),activate(Y)),activate#(Y))
U52#(tt(),Y) -> c_10(activate#(Y))
U64#(pair(YS,ZS),X) -> c_14(activate#(X))
U71#(tt(),XS) -> c_15(U72#(tt(),activate(XS)),activate#(XS))
U72#(tt(),XS) -> c_16(activate#(XS))
activate#(X) -> c_19()
activate#(n__natsFrom(X)) -> c_20(natsFrom#(X))
natsFrom#(N) -> c_24()
natsFrom#(X) -> c_25()
splitAt#(0(),XS) -> c_28()
- Weak TRS:
U11(tt(),N,XS) -> U12(tt(),activate(N),activate(XS))
U12(tt(),N,XS) -> snd(splitAt(activate(N),activate(XS)))
U51(tt(),Y) -> U52(tt(),activate(Y))
U52(tt(),Y) -> activate(Y)
U61(tt(),N,X,XS) -> U62(tt(),activate(N),activate(X),activate(XS))
U62(tt(),N,X,XS) -> U63(tt(),activate(N),activate(X),activate(XS))
U63(tt(),N,X,XS) -> U64(splitAt(activate(N),activate(XS)),activate(X))
U64(pair(YS,ZS),X) -> pair(cons(activate(X),YS),ZS)
activate(X) -> X
activate(n__natsFrom(X)) -> natsFrom(X)
afterNth(N,XS) -> U11(tt(),N,XS)
natsFrom(N) -> cons(N,n__natsFrom(s(N)))
natsFrom(X) -> n__natsFrom(X)
snd(pair(X,Y)) -> U51(tt(),Y)
splitAt(0(),XS) -> pair(nil(),XS)
splitAt(s(N),cons(X,XS)) -> U61(tt(),N,X,activate(XS))
- Signature:
{U11/3,U12/3,U21/2,U22/2,U31/2,U32/2,U41/3,U42/3,U51/2,U52/2,U61/4,U62/4,U63/4,U64/2,U71/2,U72/2,U81/3,U82/3
,activate/1,afterNth/2,fst/1,head/1,natsFrom/1,sel/2,snd/1,splitAt/2,tail/1,take/2,U11#/3,U12#/3,U21#/2
,U22#/2,U31#/2,U32#/2,U41#/3,U42#/3,U51#/2,U52#/2,U61#/4,U62#/4,U63#/4,U64#/2,U71#/2,U72#/2,U81#/3,U82#/3
,activate#/1,afterNth#/2,fst#/1,head#/1,natsFrom#/1,sel#/2,snd#/1,splitAt#/2,tail#/1,take#/2} / {0/0,cons/2
,n__natsFrom/1,nil/0,pair/2,s/1,tt/0,c_1/3,c_2/4,c_3/2,c_4/1,c_5/2,c_6/1,c_7/3,c_8/4,c_9/2,c_10/1,c_11/4
,c_12/4,c_13/5,c_14/1,c_15/2,c_16/1,c_17/3,c_18/4,c_19/0,c_20/1,c_21/1,c_22/1,c_23/1,c_24/0,c_25/0,c_26/1
,c_27/1,c_28/0,c_29/2,c_30/2,c_31/1}
- Obligation:
innermost runtime complexity wrt. defined symbols {U11#,U12#,U21#,U22#,U31#,U32#,U41#,U42#,U51#,U52#,U61#
,U62#,U63#,U64#,U71#,U72#,U81#,U82#,activate#,afterNth#,fst#,head#,natsFrom#,sel#,snd#,splitAt#,tail#
,take#} and constructors {0,cons,n__natsFrom,nil,pair,s,tt}
+ Applied Processor:
PredecessorEstimation {onSelection = all simple predecessor estimation selector}
+ Details:
We estimate the number of application of
{11,12,14,16}
by application of
Pre({11,12,14,16}) = {2,4,9}.
Here rules are labelled as follows:
1: U11#(tt(),N,XS) -> c_1(U12#(tt(),activate(N),activate(XS)),activate#(N),activate#(XS))
2: U12#(tt(),N,XS) -> c_2(snd#(splitAt(activate(N),activate(XS)))
,splitAt#(activate(N),activate(XS))
,activate#(N)
,activate#(XS))
3: U41#(tt(),N,XS) -> c_7(U42#(tt(),activate(N),activate(XS)),activate#(N),activate#(XS))
4: U42#(tt(),N,XS) -> c_8(head#(afterNth(activate(N),activate(XS)))
,afterNth#(activate(N),activate(XS))
,activate#(N)
,activate#(XS))
5: U61#(tt(),N,X,XS) -> c_11(U62#(tt(),activate(N),activate(X),activate(XS))
,activate#(N)
,activate#(X)
,activate#(XS))
6: U62#(tt(),N,X,XS) -> c_12(U63#(tt(),activate(N),activate(X),activate(XS))
,activate#(N)
,activate#(X)
,activate#(XS))
7: U63#(tt(),N,X,XS) -> c_13(U64#(splitAt(activate(N),activate(XS)),activate(X))
,splitAt#(activate(N),activate(XS))
,activate#(N)
,activate#(XS)
,activate#(X))
8: U81#(tt(),N,XS) -> c_17(U82#(tt(),activate(N),activate(XS)),activate#(N),activate#(XS))
9: U82#(tt(),N,XS) -> c_18(fst#(splitAt(activate(N),activate(XS)))
,splitAt#(activate(N),activate(XS))
,activate#(N)
,activate#(XS))
10: afterNth#(N,XS) -> c_21(U11#(tt(),N,XS))
11: fst#(pair(X,Y)) -> c_22(U21#(tt(),X))
12: head#(cons(N,XS)) -> c_23(U31#(tt(),N))
13: sel#(N,XS) -> c_26(U41#(tt(),N,XS))
14: snd#(pair(X,Y)) -> c_27(U51#(tt(),Y))
15: splitAt#(s(N),cons(X,XS)) -> c_29(U61#(tt(),N,X,activate(XS)),activate#(XS))
16: tail#(cons(N,XS)) -> c_30(U71#(tt(),activate(XS)),activate#(XS))
17: take#(N,XS) -> c_31(U81#(tt(),N,XS))
18: U21#(tt(),X) -> c_3(U22#(tt(),activate(X)),activate#(X))
19: U22#(tt(),X) -> c_4(activate#(X))
20: U31#(tt(),N) -> c_5(U32#(tt(),activate(N)),activate#(N))
21: U32#(tt(),N) -> c_6(activate#(N))
22: U51#(tt(),Y) -> c_9(U52#(tt(),activate(Y)),activate#(Y))
23: U52#(tt(),Y) -> c_10(activate#(Y))
24: U64#(pair(YS,ZS),X) -> c_14(activate#(X))
25: U71#(tt(),XS) -> c_15(U72#(tt(),activate(XS)),activate#(XS))
26: U72#(tt(),XS) -> c_16(activate#(XS))
27: activate#(X) -> c_19()
28: activate#(n__natsFrom(X)) -> c_20(natsFrom#(X))
29: natsFrom#(N) -> c_24()
30: natsFrom#(X) -> c_25()
31: splitAt#(0(),XS) -> c_28()
* Step 9: RemoveWeakSuffixes WORST_CASE(?,O(n^1))
+ Considered Problem:
- Strict DPs:
U11#(tt(),N,XS) -> c_1(U12#(tt(),activate(N),activate(XS)),activate#(N),activate#(XS))
U12#(tt(),N,XS) -> c_2(snd#(splitAt(activate(N),activate(XS)))
,splitAt#(activate(N),activate(XS))
,activate#(N)
,activate#(XS))
U41#(tt(),N,XS) -> c_7(U42#(tt(),activate(N),activate(XS)),activate#(N),activate#(XS))
U42#(tt(),N,XS) -> c_8(head#(afterNth(activate(N),activate(XS)))
,afterNth#(activate(N),activate(XS))
,activate#(N)
,activate#(XS))
U61#(tt(),N,X,XS) -> c_11(U62#(tt(),activate(N),activate(X),activate(XS))
,activate#(N)
,activate#(X)
,activate#(XS))
U62#(tt(),N,X,XS) -> c_12(U63#(tt(),activate(N),activate(X),activate(XS))
,activate#(N)
,activate#(X)
,activate#(XS))
U63#(tt(),N,X,XS) -> c_13(U64#(splitAt(activate(N),activate(XS)),activate(X))
,splitAt#(activate(N),activate(XS))
,activate#(N)
,activate#(XS)
,activate#(X))
U81#(tt(),N,XS) -> c_17(U82#(tt(),activate(N),activate(XS)),activate#(N),activate#(XS))
U82#(tt(),N,XS) -> c_18(fst#(splitAt(activate(N),activate(XS)))
,splitAt#(activate(N),activate(XS))
,activate#(N)
,activate#(XS))
afterNth#(N,XS) -> c_21(U11#(tt(),N,XS))
sel#(N,XS) -> c_26(U41#(tt(),N,XS))
splitAt#(s(N),cons(X,XS)) -> c_29(U61#(tt(),N,X,activate(XS)),activate#(XS))
take#(N,XS) -> c_31(U81#(tt(),N,XS))
- Weak DPs:
U21#(tt(),X) -> c_3(U22#(tt(),activate(X)),activate#(X))
U22#(tt(),X) -> c_4(activate#(X))
U31#(tt(),N) -> c_5(U32#(tt(),activate(N)),activate#(N))
U32#(tt(),N) -> c_6(activate#(N))
U51#(tt(),Y) -> c_9(U52#(tt(),activate(Y)),activate#(Y))
U52#(tt(),Y) -> c_10(activate#(Y))
U64#(pair(YS,ZS),X) -> c_14(activate#(X))
U71#(tt(),XS) -> c_15(U72#(tt(),activate(XS)),activate#(XS))
U72#(tt(),XS) -> c_16(activate#(XS))
activate#(X) -> c_19()
activate#(n__natsFrom(X)) -> c_20(natsFrom#(X))
fst#(pair(X,Y)) -> c_22(U21#(tt(),X))
head#(cons(N,XS)) -> c_23(U31#(tt(),N))
natsFrom#(N) -> c_24()
natsFrom#(X) -> c_25()
snd#(pair(X,Y)) -> c_27(U51#(tt(),Y))
splitAt#(0(),XS) -> c_28()
tail#(cons(N,XS)) -> c_30(U71#(tt(),activate(XS)),activate#(XS))
- Weak TRS:
U11(tt(),N,XS) -> U12(tt(),activate(N),activate(XS))
U12(tt(),N,XS) -> snd(splitAt(activate(N),activate(XS)))
U51(tt(),Y) -> U52(tt(),activate(Y))
U52(tt(),Y) -> activate(Y)
U61(tt(),N,X,XS) -> U62(tt(),activate(N),activate(X),activate(XS))
U62(tt(),N,X,XS) -> U63(tt(),activate(N),activate(X),activate(XS))
U63(tt(),N,X,XS) -> U64(splitAt(activate(N),activate(XS)),activate(X))
U64(pair(YS,ZS),X) -> pair(cons(activate(X),YS),ZS)
activate(X) -> X
activate(n__natsFrom(X)) -> natsFrom(X)
afterNth(N,XS) -> U11(tt(),N,XS)
natsFrom(N) -> cons(N,n__natsFrom(s(N)))
natsFrom(X) -> n__natsFrom(X)
snd(pair(X,Y)) -> U51(tt(),Y)
splitAt(0(),XS) -> pair(nil(),XS)
splitAt(s(N),cons(X,XS)) -> U61(tt(),N,X,activate(XS))
- Signature:
{U11/3,U12/3,U21/2,U22/2,U31/2,U32/2,U41/3,U42/3,U51/2,U52/2,U61/4,U62/4,U63/4,U64/2,U71/2,U72/2,U81/3,U82/3
,activate/1,afterNth/2,fst/1,head/1,natsFrom/1,sel/2,snd/1,splitAt/2,tail/1,take/2,U11#/3,U12#/3,U21#/2
,U22#/2,U31#/2,U32#/2,U41#/3,U42#/3,U51#/2,U52#/2,U61#/4,U62#/4,U63#/4,U64#/2,U71#/2,U72#/2,U81#/3,U82#/3
,activate#/1,afterNth#/2,fst#/1,head#/1,natsFrom#/1,sel#/2,snd#/1,splitAt#/2,tail#/1,take#/2} / {0/0,cons/2
,n__natsFrom/1,nil/0,pair/2,s/1,tt/0,c_1/3,c_2/4,c_3/2,c_4/1,c_5/2,c_6/1,c_7/3,c_8/4,c_9/2,c_10/1,c_11/4
,c_12/4,c_13/5,c_14/1,c_15/2,c_16/1,c_17/3,c_18/4,c_19/0,c_20/1,c_21/1,c_22/1,c_23/1,c_24/0,c_25/0,c_26/1
,c_27/1,c_28/0,c_29/2,c_30/2,c_31/1}
- Obligation:
innermost runtime complexity wrt. defined symbols {U11#,U12#,U21#,U22#,U31#,U32#,U41#,U42#,U51#,U52#,U61#
,U62#,U63#,U64#,U71#,U72#,U81#,U82#,activate#,afterNth#,fst#,head#,natsFrom#,sel#,snd#,splitAt#,tail#
,take#} and constructors {0,cons,n__natsFrom,nil,pair,s,tt}
+ Applied Processor:
RemoveWeakSuffixes
+ Details:
Consider the dependency graph
1:S:U11#(tt(),N,XS) -> c_1(U12#(tt(),activate(N),activate(XS)),activate#(N),activate#(XS))
-->_3 activate#(n__natsFrom(X)) -> c_20(natsFrom#(X)):24
-->_2 activate#(n__natsFrom(X)) -> c_20(natsFrom#(X)):24
-->_1 U12#(tt(),N,XS) -> c_2(snd#(splitAt(activate(N),activate(XS)))
,splitAt#(activate(N),activate(XS))
,activate#(N)
,activate#(XS)):2
-->_3 activate#(X) -> c_19():23
-->_2 activate#(X) -> c_19():23
2:S:U12#(tt(),N,XS) -> c_2(snd#(splitAt(activate(N),activate(XS)))
,splitAt#(activate(N),activate(XS))
,activate#(N)
,activate#(XS))
-->_1 snd#(pair(X,Y)) -> c_27(U51#(tt(),Y)):29
-->_4 activate#(n__natsFrom(X)) -> c_20(natsFrom#(X)):24
-->_3 activate#(n__natsFrom(X)) -> c_20(natsFrom#(X)):24
-->_2 splitAt#(s(N),cons(X,XS)) -> c_29(U61#(tt(),N,X,activate(XS)),activate#(XS)):12
-->_2 splitAt#(0(),XS) -> c_28():30
-->_4 activate#(X) -> c_19():23
-->_3 activate#(X) -> c_19():23
3:S:U41#(tt(),N,XS) -> c_7(U42#(tt(),activate(N),activate(XS)),activate#(N),activate#(XS))
-->_3 activate#(n__natsFrom(X)) -> c_20(natsFrom#(X)):24
-->_2 activate#(n__natsFrom(X)) -> c_20(natsFrom#(X)):24
-->_1 U42#(tt(),N,XS) -> c_8(head#(afterNth(activate(N),activate(XS)))
,afterNth#(activate(N),activate(XS))
,activate#(N)
,activate#(XS)):4
-->_3 activate#(X) -> c_19():23
-->_2 activate#(X) -> c_19():23
4:S:U42#(tt(),N,XS) -> c_8(head#(afterNth(activate(N),activate(XS)))
,afterNth#(activate(N),activate(XS))
,activate#(N)
,activate#(XS))
-->_1 head#(cons(N,XS)) -> c_23(U31#(tt(),N)):26
-->_4 activate#(n__natsFrom(X)) -> c_20(natsFrom#(X)):24
-->_3 activate#(n__natsFrom(X)) -> c_20(natsFrom#(X)):24
-->_2 afterNth#(N,XS) -> c_21(U11#(tt(),N,XS)):10
-->_4 activate#(X) -> c_19():23
-->_3 activate#(X) -> c_19():23
5:S:U61#(tt(),N,X,XS) -> c_11(U62#(tt(),activate(N),activate(X),activate(XS))
,activate#(N)
,activate#(X)
,activate#(XS))
-->_4 activate#(n__natsFrom(X)) -> c_20(natsFrom#(X)):24
-->_3 activate#(n__natsFrom(X)) -> c_20(natsFrom#(X)):24
-->_2 activate#(n__natsFrom(X)) -> c_20(natsFrom#(X)):24
-->_1 U62#(tt(),N,X,XS) -> c_12(U63#(tt(),activate(N),activate(X),activate(XS))
,activate#(N)
,activate#(X)
,activate#(XS)):6
-->_4 activate#(X) -> c_19():23
-->_3 activate#(X) -> c_19():23
-->_2 activate#(X) -> c_19():23
6:S:U62#(tt(),N,X,XS) -> c_12(U63#(tt(),activate(N),activate(X),activate(XS))
,activate#(N)
,activate#(X)
,activate#(XS))
-->_4 activate#(n__natsFrom(X)) -> c_20(natsFrom#(X)):24
-->_3 activate#(n__natsFrom(X)) -> c_20(natsFrom#(X)):24
-->_2 activate#(n__natsFrom(X)) -> c_20(natsFrom#(X)):24
-->_1 U63#(tt(),N,X,XS) -> c_13(U64#(splitAt(activate(N),activate(XS)),activate(X))
,splitAt#(activate(N),activate(XS))
,activate#(N)
,activate#(XS)
,activate#(X)):7
-->_4 activate#(X) -> c_19():23
-->_3 activate#(X) -> c_19():23
-->_2 activate#(X) -> c_19():23
7:S:U63#(tt(),N,X,XS) -> c_13(U64#(splitAt(activate(N),activate(XS)),activate(X))
,splitAt#(activate(N),activate(XS))
,activate#(N)
,activate#(XS)
,activate#(X))
-->_5 activate#(n__natsFrom(X)) -> c_20(natsFrom#(X)):24
-->_4 activate#(n__natsFrom(X)) -> c_20(natsFrom#(X)):24
-->_3 activate#(n__natsFrom(X)) -> c_20(natsFrom#(X)):24
-->_1 U64#(pair(YS,ZS),X) -> c_14(activate#(X)):20
-->_2 splitAt#(s(N),cons(X,XS)) -> c_29(U61#(tt(),N,X,activate(XS)),activate#(XS)):12
-->_2 splitAt#(0(),XS) -> c_28():30
-->_5 activate#(X) -> c_19():23
-->_4 activate#(X) -> c_19():23
-->_3 activate#(X) -> c_19():23
8:S:U81#(tt(),N,XS) -> c_17(U82#(tt(),activate(N),activate(XS)),activate#(N),activate#(XS))
-->_3 activate#(n__natsFrom(X)) -> c_20(natsFrom#(X)):24
-->_2 activate#(n__natsFrom(X)) -> c_20(natsFrom#(X)):24
-->_1 U82#(tt(),N,XS) -> c_18(fst#(splitAt(activate(N),activate(XS)))
,splitAt#(activate(N),activate(XS))
,activate#(N)
,activate#(XS)):9
-->_3 activate#(X) -> c_19():23
-->_2 activate#(X) -> c_19():23
9:S:U82#(tt(),N,XS) -> c_18(fst#(splitAt(activate(N),activate(XS)))
,splitAt#(activate(N),activate(XS))
,activate#(N)
,activate#(XS))
-->_1 fst#(pair(X,Y)) -> c_22(U21#(tt(),X)):25
-->_4 activate#(n__natsFrom(X)) -> c_20(natsFrom#(X)):24
-->_3 activate#(n__natsFrom(X)) -> c_20(natsFrom#(X)):24
-->_2 splitAt#(s(N),cons(X,XS)) -> c_29(U61#(tt(),N,X,activate(XS)),activate#(XS)):12
-->_2 splitAt#(0(),XS) -> c_28():30
-->_4 activate#(X) -> c_19():23
-->_3 activate#(X) -> c_19():23
10:S:afterNth#(N,XS) -> c_21(U11#(tt(),N,XS))
-->_1 U11#(tt(),N,XS) -> c_1(U12#(tt(),activate(N),activate(XS)),activate#(N),activate#(XS)):1
11:S:sel#(N,XS) -> c_26(U41#(tt(),N,XS))
-->_1 U41#(tt(),N,XS) -> c_7(U42#(tt(),activate(N),activate(XS)),activate#(N),activate#(XS)):3
12:S:splitAt#(s(N),cons(X,XS)) -> c_29(U61#(tt(),N,X,activate(XS)),activate#(XS))
-->_2 activate#(n__natsFrom(X)) -> c_20(natsFrom#(X)):24
-->_2 activate#(X) -> c_19():23
-->_1 U61#(tt(),N,X,XS) -> c_11(U62#(tt(),activate(N),activate(X),activate(XS))
,activate#(N)
,activate#(X)
,activate#(XS)):5
13:S:take#(N,XS) -> c_31(U81#(tt(),N,XS))
-->_1 U81#(tt(),N,XS) -> c_17(U82#(tt(),activate(N),activate(XS)),activate#(N),activate#(XS)):8
14:W:U21#(tt(),X) -> c_3(U22#(tt(),activate(X)),activate#(X))
-->_2 activate#(n__natsFrom(X)) -> c_20(natsFrom#(X)):24
-->_1 U22#(tt(),X) -> c_4(activate#(X)):15
-->_2 activate#(X) -> c_19():23
15:W:U22#(tt(),X) -> c_4(activate#(X))
-->_1 activate#(n__natsFrom(X)) -> c_20(natsFrom#(X)):24
-->_1 activate#(X) -> c_19():23
16:W:U31#(tt(),N) -> c_5(U32#(tt(),activate(N)),activate#(N))
-->_2 activate#(n__natsFrom(X)) -> c_20(natsFrom#(X)):24
-->_1 U32#(tt(),N) -> c_6(activate#(N)):17
-->_2 activate#(X) -> c_19():23
17:W:U32#(tt(),N) -> c_6(activate#(N))
-->_1 activate#(n__natsFrom(X)) -> c_20(natsFrom#(X)):24
-->_1 activate#(X) -> c_19():23
18:W:U51#(tt(),Y) -> c_9(U52#(tt(),activate(Y)),activate#(Y))
-->_2 activate#(n__natsFrom(X)) -> c_20(natsFrom#(X)):24
-->_1 U52#(tt(),Y) -> c_10(activate#(Y)):19
-->_2 activate#(X) -> c_19():23
19:W:U52#(tt(),Y) -> c_10(activate#(Y))
-->_1 activate#(n__natsFrom(X)) -> c_20(natsFrom#(X)):24
-->_1 activate#(X) -> c_19():23
20:W:U64#(pair(YS,ZS),X) -> c_14(activate#(X))
-->_1 activate#(n__natsFrom(X)) -> c_20(natsFrom#(X)):24
-->_1 activate#(X) -> c_19():23
21:W:U71#(tt(),XS) -> c_15(U72#(tt(),activate(XS)),activate#(XS))
-->_2 activate#(n__natsFrom(X)) -> c_20(natsFrom#(X)):24
-->_1 U72#(tt(),XS) -> c_16(activate#(XS)):22
-->_2 activate#(X) -> c_19():23
22:W:U72#(tt(),XS) -> c_16(activate#(XS))
-->_1 activate#(n__natsFrom(X)) -> c_20(natsFrom#(X)):24
-->_1 activate#(X) -> c_19():23
23:W:activate#(X) -> c_19()
24:W:activate#(n__natsFrom(X)) -> c_20(natsFrom#(X))
-->_1 natsFrom#(X) -> c_25():28
-->_1 natsFrom#(N) -> c_24():27
25:W:fst#(pair(X,Y)) -> c_22(U21#(tt(),X))
-->_1 U21#(tt(),X) -> c_3(U22#(tt(),activate(X)),activate#(X)):14
26:W:head#(cons(N,XS)) -> c_23(U31#(tt(),N))
-->_1 U31#(tt(),N) -> c_5(U32#(tt(),activate(N)),activate#(N)):16
27:W:natsFrom#(N) -> c_24()
28:W:natsFrom#(X) -> c_25()
29:W:snd#(pair(X,Y)) -> c_27(U51#(tt(),Y))
-->_1 U51#(tt(),Y) -> c_9(U52#(tt(),activate(Y)),activate#(Y)):18
30:W:splitAt#(0(),XS) -> c_28()
31:W:tail#(cons(N,XS)) -> c_30(U71#(tt(),activate(XS)),activate#(XS))
-->_2 activate#(n__natsFrom(X)) -> c_20(natsFrom#(X)):24
-->_2 activate#(X) -> c_19():23
-->_1 U71#(tt(),XS) -> c_15(U72#(tt(),activate(XS)),activate#(XS)):21
The following weak DPs constitute a sub-graph of the DG that is closed under successors. The DPs are removed.
31: tail#(cons(N,XS)) -> c_30(U71#(tt(),activate(XS)),activate#(XS))
21: U71#(tt(),XS) -> c_15(U72#(tt(),activate(XS)),activate#(XS))
22: U72#(tt(),XS) -> c_16(activate#(XS))
25: fst#(pair(X,Y)) -> c_22(U21#(tt(),X))
14: U21#(tt(),X) -> c_3(U22#(tt(),activate(X)),activate#(X))
15: U22#(tt(),X) -> c_4(activate#(X))
26: head#(cons(N,XS)) -> c_23(U31#(tt(),N))
16: U31#(tt(),N) -> c_5(U32#(tt(),activate(N)),activate#(N))
17: U32#(tt(),N) -> c_6(activate#(N))
30: splitAt#(0(),XS) -> c_28()
20: U64#(pair(YS,ZS),X) -> c_14(activate#(X))
29: snd#(pair(X,Y)) -> c_27(U51#(tt(),Y))
18: U51#(tt(),Y) -> c_9(U52#(tt(),activate(Y)),activate#(Y))
19: U52#(tt(),Y) -> c_10(activate#(Y))
23: activate#(X) -> c_19()
24: activate#(n__natsFrom(X)) -> c_20(natsFrom#(X))
27: natsFrom#(N) -> c_24()
28: natsFrom#(X) -> c_25()
* Step 10: SimplifyRHS WORST_CASE(?,O(n^1))
+ Considered Problem:
- Strict DPs:
U11#(tt(),N,XS) -> c_1(U12#(tt(),activate(N),activate(XS)),activate#(N),activate#(XS))
U12#(tt(),N,XS) -> c_2(snd#(splitAt(activate(N),activate(XS)))
,splitAt#(activate(N),activate(XS))
,activate#(N)
,activate#(XS))
U41#(tt(),N,XS) -> c_7(U42#(tt(),activate(N),activate(XS)),activate#(N),activate#(XS))
U42#(tt(),N,XS) -> c_8(head#(afterNth(activate(N),activate(XS)))
,afterNth#(activate(N),activate(XS))
,activate#(N)
,activate#(XS))
U61#(tt(),N,X,XS) -> c_11(U62#(tt(),activate(N),activate(X),activate(XS))
,activate#(N)
,activate#(X)
,activate#(XS))
U62#(tt(),N,X,XS) -> c_12(U63#(tt(),activate(N),activate(X),activate(XS))
,activate#(N)
,activate#(X)
,activate#(XS))
U63#(tt(),N,X,XS) -> c_13(U64#(splitAt(activate(N),activate(XS)),activate(X))
,splitAt#(activate(N),activate(XS))
,activate#(N)
,activate#(XS)
,activate#(X))
U81#(tt(),N,XS) -> c_17(U82#(tt(),activate(N),activate(XS)),activate#(N),activate#(XS))
U82#(tt(),N,XS) -> c_18(fst#(splitAt(activate(N),activate(XS)))
,splitAt#(activate(N),activate(XS))
,activate#(N)
,activate#(XS))
afterNth#(N,XS) -> c_21(U11#(tt(),N,XS))
sel#(N,XS) -> c_26(U41#(tt(),N,XS))
splitAt#(s(N),cons(X,XS)) -> c_29(U61#(tt(),N,X,activate(XS)),activate#(XS))
take#(N,XS) -> c_31(U81#(tt(),N,XS))
- Weak TRS:
U11(tt(),N,XS) -> U12(tt(),activate(N),activate(XS))
U12(tt(),N,XS) -> snd(splitAt(activate(N),activate(XS)))
U51(tt(),Y) -> U52(tt(),activate(Y))
U52(tt(),Y) -> activate(Y)
U61(tt(),N,X,XS) -> U62(tt(),activate(N),activate(X),activate(XS))
U62(tt(),N,X,XS) -> U63(tt(),activate(N),activate(X),activate(XS))
U63(tt(),N,X,XS) -> U64(splitAt(activate(N),activate(XS)),activate(X))
U64(pair(YS,ZS),X) -> pair(cons(activate(X),YS),ZS)
activate(X) -> X
activate(n__natsFrom(X)) -> natsFrom(X)
afterNth(N,XS) -> U11(tt(),N,XS)
natsFrom(N) -> cons(N,n__natsFrom(s(N)))
natsFrom(X) -> n__natsFrom(X)
snd(pair(X,Y)) -> U51(tt(),Y)
splitAt(0(),XS) -> pair(nil(),XS)
splitAt(s(N),cons(X,XS)) -> U61(tt(),N,X,activate(XS))
- Signature:
{U11/3,U12/3,U21/2,U22/2,U31/2,U32/2,U41/3,U42/3,U51/2,U52/2,U61/4,U62/4,U63/4,U64/2,U71/2,U72/2,U81/3,U82/3
,activate/1,afterNth/2,fst/1,head/1,natsFrom/1,sel/2,snd/1,splitAt/2,tail/1,take/2,U11#/3,U12#/3,U21#/2
,U22#/2,U31#/2,U32#/2,U41#/3,U42#/3,U51#/2,U52#/2,U61#/4,U62#/4,U63#/4,U64#/2,U71#/2,U72#/2,U81#/3,U82#/3
,activate#/1,afterNth#/2,fst#/1,head#/1,natsFrom#/1,sel#/2,snd#/1,splitAt#/2,tail#/1,take#/2} / {0/0,cons/2
,n__natsFrom/1,nil/0,pair/2,s/1,tt/0,c_1/3,c_2/4,c_3/2,c_4/1,c_5/2,c_6/1,c_7/3,c_8/4,c_9/2,c_10/1,c_11/4
,c_12/4,c_13/5,c_14/1,c_15/2,c_16/1,c_17/3,c_18/4,c_19/0,c_20/1,c_21/1,c_22/1,c_23/1,c_24/0,c_25/0,c_26/1
,c_27/1,c_28/0,c_29/2,c_30/2,c_31/1}
- Obligation:
innermost runtime complexity wrt. defined symbols {U11#,U12#,U21#,U22#,U31#,U32#,U41#,U42#,U51#,U52#,U61#
,U62#,U63#,U64#,U71#,U72#,U81#,U82#,activate#,afterNth#,fst#,head#,natsFrom#,sel#,snd#,splitAt#,tail#
,take#} and constructors {0,cons,n__natsFrom,nil,pair,s,tt}
+ Applied Processor:
SimplifyRHS
+ Details:
Consider the dependency graph
1:S:U11#(tt(),N,XS) -> c_1(U12#(tt(),activate(N),activate(XS)),activate#(N),activate#(XS))
-->_1 U12#(tt(),N,XS) -> c_2(snd#(splitAt(activate(N),activate(XS)))
,splitAt#(activate(N),activate(XS))
,activate#(N)
,activate#(XS)):2
2:S:U12#(tt(),N,XS) -> c_2(snd#(splitAt(activate(N),activate(XS)))
,splitAt#(activate(N),activate(XS))
,activate#(N)
,activate#(XS))
-->_2 splitAt#(s(N),cons(X,XS)) -> c_29(U61#(tt(),N,X,activate(XS)),activate#(XS)):12
3:S:U41#(tt(),N,XS) -> c_7(U42#(tt(),activate(N),activate(XS)),activate#(N),activate#(XS))
-->_1 U42#(tt(),N,XS) -> c_8(head#(afterNth(activate(N),activate(XS)))
,afterNth#(activate(N),activate(XS))
,activate#(N)
,activate#(XS)):4
4:S:U42#(tt(),N,XS) -> c_8(head#(afterNth(activate(N),activate(XS)))
,afterNth#(activate(N),activate(XS))
,activate#(N)
,activate#(XS))
-->_2 afterNth#(N,XS) -> c_21(U11#(tt(),N,XS)):10
5:S:U61#(tt(),N,X,XS) -> c_11(U62#(tt(),activate(N),activate(X),activate(XS))
,activate#(N)
,activate#(X)
,activate#(XS))
-->_1 U62#(tt(),N,X,XS) -> c_12(U63#(tt(),activate(N),activate(X),activate(XS))
,activate#(N)
,activate#(X)
,activate#(XS)):6
6:S:U62#(tt(),N,X,XS) -> c_12(U63#(tt(),activate(N),activate(X),activate(XS))
,activate#(N)
,activate#(X)
,activate#(XS))
-->_1 U63#(tt(),N,X,XS) -> c_13(U64#(splitAt(activate(N),activate(XS)),activate(X))
,splitAt#(activate(N),activate(XS))
,activate#(N)
,activate#(XS)
,activate#(X)):7
7:S:U63#(tt(),N,X,XS) -> c_13(U64#(splitAt(activate(N),activate(XS)),activate(X))
,splitAt#(activate(N),activate(XS))
,activate#(N)
,activate#(XS)
,activate#(X))
-->_2 splitAt#(s(N),cons(X,XS)) -> c_29(U61#(tt(),N,X,activate(XS)),activate#(XS)):12
8:S:U81#(tt(),N,XS) -> c_17(U82#(tt(),activate(N),activate(XS)),activate#(N),activate#(XS))
-->_1 U82#(tt(),N,XS) -> c_18(fst#(splitAt(activate(N),activate(XS)))
,splitAt#(activate(N),activate(XS))
,activate#(N)
,activate#(XS)):9
9:S:U82#(tt(),N,XS) -> c_18(fst#(splitAt(activate(N),activate(XS)))
,splitAt#(activate(N),activate(XS))
,activate#(N)
,activate#(XS))
-->_2 splitAt#(s(N),cons(X,XS)) -> c_29(U61#(tt(),N,X,activate(XS)),activate#(XS)):12
10:S:afterNth#(N,XS) -> c_21(U11#(tt(),N,XS))
-->_1 U11#(tt(),N,XS) -> c_1(U12#(tt(),activate(N),activate(XS)),activate#(N),activate#(XS)):1
11:S:sel#(N,XS) -> c_26(U41#(tt(),N,XS))
-->_1 U41#(tt(),N,XS) -> c_7(U42#(tt(),activate(N),activate(XS)),activate#(N),activate#(XS)):3
12:S:splitAt#(s(N),cons(X,XS)) -> c_29(U61#(tt(),N,X,activate(XS)),activate#(XS))
-->_1 U61#(tt(),N,X,XS) -> c_11(U62#(tt(),activate(N),activate(X),activate(XS))
,activate#(N)
,activate#(X)
,activate#(XS)):5
13:S:take#(N,XS) -> c_31(U81#(tt(),N,XS))
-->_1 U81#(tt(),N,XS) -> c_17(U82#(tt(),activate(N),activate(XS)),activate#(N),activate#(XS)):8
Due to missing edges in the depndency graph, the right-hand sides of following rules could be simplified:
U11#(tt(),N,XS) -> c_1(U12#(tt(),activate(N),activate(XS)))
U12#(tt(),N,XS) -> c_2(splitAt#(activate(N),activate(XS)))
U41#(tt(),N,XS) -> c_7(U42#(tt(),activate(N),activate(XS)))
U42#(tt(),N,XS) -> c_8(afterNth#(activate(N),activate(XS)))
U61#(tt(),N,X,XS) -> c_11(U62#(tt(),activate(N),activate(X),activate(XS)))
U62#(tt(),N,X,XS) -> c_12(U63#(tt(),activate(N),activate(X),activate(XS)))
U63#(tt(),N,X,XS) -> c_13(splitAt#(activate(N),activate(XS)))
U81#(tt(),N,XS) -> c_17(U82#(tt(),activate(N),activate(XS)))
U82#(tt(),N,XS) -> c_18(splitAt#(activate(N),activate(XS)))
splitAt#(s(N),cons(X,XS)) -> c_29(U61#(tt(),N,X,activate(XS)))
* Step 11: UsableRules WORST_CASE(?,O(n^1))
+ Considered Problem:
- Strict DPs:
U11#(tt(),N,XS) -> c_1(U12#(tt(),activate(N),activate(XS)))
U12#(tt(),N,XS) -> c_2(splitAt#(activate(N),activate(XS)))
U41#(tt(),N,XS) -> c_7(U42#(tt(),activate(N),activate(XS)))
U42#(tt(),N,XS) -> c_8(afterNth#(activate(N),activate(XS)))
U61#(tt(),N,X,XS) -> c_11(U62#(tt(),activate(N),activate(X),activate(XS)))
U62#(tt(),N,X,XS) -> c_12(U63#(tt(),activate(N),activate(X),activate(XS)))
U63#(tt(),N,X,XS) -> c_13(splitAt#(activate(N),activate(XS)))
U81#(tt(),N,XS) -> c_17(U82#(tt(),activate(N),activate(XS)))
U82#(tt(),N,XS) -> c_18(splitAt#(activate(N),activate(XS)))
afterNth#(N,XS) -> c_21(U11#(tt(),N,XS))
sel#(N,XS) -> c_26(U41#(tt(),N,XS))
splitAt#(s(N),cons(X,XS)) -> c_29(U61#(tt(),N,X,activate(XS)))
take#(N,XS) -> c_31(U81#(tt(),N,XS))
- Weak TRS:
U11(tt(),N,XS) -> U12(tt(),activate(N),activate(XS))
U12(tt(),N,XS) -> snd(splitAt(activate(N),activate(XS)))
U51(tt(),Y) -> U52(tt(),activate(Y))
U52(tt(),Y) -> activate(Y)
U61(tt(),N,X,XS) -> U62(tt(),activate(N),activate(X),activate(XS))
U62(tt(),N,X,XS) -> U63(tt(),activate(N),activate(X),activate(XS))
U63(tt(),N,X,XS) -> U64(splitAt(activate(N),activate(XS)),activate(X))
U64(pair(YS,ZS),X) -> pair(cons(activate(X),YS),ZS)
activate(X) -> X
activate(n__natsFrom(X)) -> natsFrom(X)
afterNth(N,XS) -> U11(tt(),N,XS)
natsFrom(N) -> cons(N,n__natsFrom(s(N)))
natsFrom(X) -> n__natsFrom(X)
snd(pair(X,Y)) -> U51(tt(),Y)
splitAt(0(),XS) -> pair(nil(),XS)
splitAt(s(N),cons(X,XS)) -> U61(tt(),N,X,activate(XS))
- Signature:
{U11/3,U12/3,U21/2,U22/2,U31/2,U32/2,U41/3,U42/3,U51/2,U52/2,U61/4,U62/4,U63/4,U64/2,U71/2,U72/2,U81/3,U82/3
,activate/1,afterNth/2,fst/1,head/1,natsFrom/1,sel/2,snd/1,splitAt/2,tail/1,take/2,U11#/3,U12#/3,U21#/2
,U22#/2,U31#/2,U32#/2,U41#/3,U42#/3,U51#/2,U52#/2,U61#/4,U62#/4,U63#/4,U64#/2,U71#/2,U72#/2,U81#/3,U82#/3
,activate#/1,afterNth#/2,fst#/1,head#/1,natsFrom#/1,sel#/2,snd#/1,splitAt#/2,tail#/1,take#/2} / {0/0,cons/2
,n__natsFrom/1,nil/0,pair/2,s/1,tt/0,c_1/1,c_2/1,c_3/2,c_4/1,c_5/2,c_6/1,c_7/1,c_8/1,c_9/2,c_10/1,c_11/1
,c_12/1,c_13/1,c_14/1,c_15/2,c_16/1,c_17/1,c_18/1,c_19/0,c_20/1,c_21/1,c_22/1,c_23/1,c_24/0,c_25/0,c_26/1
,c_27/1,c_28/0,c_29/1,c_30/2,c_31/1}
- Obligation:
innermost runtime complexity wrt. defined symbols {U11#,U12#,U21#,U22#,U31#,U32#,U41#,U42#,U51#,U52#,U61#
,U62#,U63#,U64#,U71#,U72#,U81#,U82#,activate#,afterNth#,fst#,head#,natsFrom#,sel#,snd#,splitAt#,tail#
,take#} and constructors {0,cons,n__natsFrom,nil,pair,s,tt}
+ Applied Processor:
UsableRules
+ Details:
We replace rewrite rules by usable rules:
activate(X) -> X
activate(n__natsFrom(X)) -> natsFrom(X)
natsFrom(N) -> cons(N,n__natsFrom(s(N)))
natsFrom(X) -> n__natsFrom(X)
U11#(tt(),N,XS) -> c_1(U12#(tt(),activate(N),activate(XS)))
U12#(tt(),N,XS) -> c_2(splitAt#(activate(N),activate(XS)))
U41#(tt(),N,XS) -> c_7(U42#(tt(),activate(N),activate(XS)))
U42#(tt(),N,XS) -> c_8(afterNth#(activate(N),activate(XS)))
U61#(tt(),N,X,XS) -> c_11(U62#(tt(),activate(N),activate(X),activate(XS)))
U62#(tt(),N,X,XS) -> c_12(U63#(tt(),activate(N),activate(X),activate(XS)))
U63#(tt(),N,X,XS) -> c_13(splitAt#(activate(N),activate(XS)))
U81#(tt(),N,XS) -> c_17(U82#(tt(),activate(N),activate(XS)))
U82#(tt(),N,XS) -> c_18(splitAt#(activate(N),activate(XS)))
afterNth#(N,XS) -> c_21(U11#(tt(),N,XS))
sel#(N,XS) -> c_26(U41#(tt(),N,XS))
splitAt#(s(N),cons(X,XS)) -> c_29(U61#(tt(),N,X,activate(XS)))
take#(N,XS) -> c_31(U81#(tt(),N,XS))
* Step 12: RemoveHeads WORST_CASE(?,O(n^1))
+ Considered Problem:
- Strict DPs:
U11#(tt(),N,XS) -> c_1(U12#(tt(),activate(N),activate(XS)))
U12#(tt(),N,XS) -> c_2(splitAt#(activate(N),activate(XS)))
U41#(tt(),N,XS) -> c_7(U42#(tt(),activate(N),activate(XS)))
U42#(tt(),N,XS) -> c_8(afterNth#(activate(N),activate(XS)))
U61#(tt(),N,X,XS) -> c_11(U62#(tt(),activate(N),activate(X),activate(XS)))
U62#(tt(),N,X,XS) -> c_12(U63#(tt(),activate(N),activate(X),activate(XS)))
U63#(tt(),N,X,XS) -> c_13(splitAt#(activate(N),activate(XS)))
U81#(tt(),N,XS) -> c_17(U82#(tt(),activate(N),activate(XS)))
U82#(tt(),N,XS) -> c_18(splitAt#(activate(N),activate(XS)))
afterNth#(N,XS) -> c_21(U11#(tt(),N,XS))
sel#(N,XS) -> c_26(U41#(tt(),N,XS))
splitAt#(s(N),cons(X,XS)) -> c_29(U61#(tt(),N,X,activate(XS)))
take#(N,XS) -> c_31(U81#(tt(),N,XS))
- Weak TRS:
activate(X) -> X
activate(n__natsFrom(X)) -> natsFrom(X)
natsFrom(N) -> cons(N,n__natsFrom(s(N)))
natsFrom(X) -> n__natsFrom(X)
- Signature:
{U11/3,U12/3,U21/2,U22/2,U31/2,U32/2,U41/3,U42/3,U51/2,U52/2,U61/4,U62/4,U63/4,U64/2,U71/2,U72/2,U81/3,U82/3
,activate/1,afterNth/2,fst/1,head/1,natsFrom/1,sel/2,snd/1,splitAt/2,tail/1,take/2,U11#/3,U12#/3,U21#/2
,U22#/2,U31#/2,U32#/2,U41#/3,U42#/3,U51#/2,U52#/2,U61#/4,U62#/4,U63#/4,U64#/2,U71#/2,U72#/2,U81#/3,U82#/3
,activate#/1,afterNth#/2,fst#/1,head#/1,natsFrom#/1,sel#/2,snd#/1,splitAt#/2,tail#/1,take#/2} / {0/0,cons/2
,n__natsFrom/1,nil/0,pair/2,s/1,tt/0,c_1/1,c_2/1,c_3/2,c_4/1,c_5/2,c_6/1,c_7/1,c_8/1,c_9/2,c_10/1,c_11/1
,c_12/1,c_13/1,c_14/1,c_15/2,c_16/1,c_17/1,c_18/1,c_19/0,c_20/1,c_21/1,c_22/1,c_23/1,c_24/0,c_25/0,c_26/1
,c_27/1,c_28/0,c_29/1,c_30/2,c_31/1}
- Obligation:
innermost runtime complexity wrt. defined symbols {U11#,U12#,U21#,U22#,U31#,U32#,U41#,U42#,U51#,U52#,U61#
,U62#,U63#,U64#,U71#,U72#,U81#,U82#,activate#,afterNth#,fst#,head#,natsFrom#,sel#,snd#,splitAt#,tail#
,take#} and constructors {0,cons,n__natsFrom,nil,pair,s,tt}
+ Applied Processor:
RemoveHeads
+ Details:
Consider the dependency graph
1:S:U11#(tt(),N,XS) -> c_1(U12#(tt(),activate(N),activate(XS)))
-->_1 U12#(tt(),N,XS) -> c_2(splitAt#(activate(N),activate(XS))):2
2:S:U12#(tt(),N,XS) -> c_2(splitAt#(activate(N),activate(XS)))
-->_1 splitAt#(s(N),cons(X,XS)) -> c_29(U61#(tt(),N,X,activate(XS))):12
3:S:U41#(tt(),N,XS) -> c_7(U42#(tt(),activate(N),activate(XS)))
-->_1 U42#(tt(),N,XS) -> c_8(afterNth#(activate(N),activate(XS))):4
4:S:U42#(tt(),N,XS) -> c_8(afterNth#(activate(N),activate(XS)))
-->_1 afterNth#(N,XS) -> c_21(U11#(tt(),N,XS)):10
5:S:U61#(tt(),N,X,XS) -> c_11(U62#(tt(),activate(N),activate(X),activate(XS)))
-->_1 U62#(tt(),N,X,XS) -> c_12(U63#(tt(),activate(N),activate(X),activate(XS))):6
6:S:U62#(tt(),N,X,XS) -> c_12(U63#(tt(),activate(N),activate(X),activate(XS)))
-->_1 U63#(tt(),N,X,XS) -> c_13(splitAt#(activate(N),activate(XS))):7
7:S:U63#(tt(),N,X,XS) -> c_13(splitAt#(activate(N),activate(XS)))
-->_1 splitAt#(s(N),cons(X,XS)) -> c_29(U61#(tt(),N,X,activate(XS))):12
8:S:U81#(tt(),N,XS) -> c_17(U82#(tt(),activate(N),activate(XS)))
-->_1 U82#(tt(),N,XS) -> c_18(splitAt#(activate(N),activate(XS))):9
9:S:U82#(tt(),N,XS) -> c_18(splitAt#(activate(N),activate(XS)))
-->_1 splitAt#(s(N),cons(X,XS)) -> c_29(U61#(tt(),N,X,activate(XS))):12
10:S:afterNth#(N,XS) -> c_21(U11#(tt(),N,XS))
-->_1 U11#(tt(),N,XS) -> c_1(U12#(tt(),activate(N),activate(XS))):1
11:S:sel#(N,XS) -> c_26(U41#(tt(),N,XS))
-->_1 U41#(tt(),N,XS) -> c_7(U42#(tt(),activate(N),activate(XS))):3
12:S:splitAt#(s(N),cons(X,XS)) -> c_29(U61#(tt(),N,X,activate(XS)))
-->_1 U61#(tt(),N,X,XS) -> c_11(U62#(tt(),activate(N),activate(X),activate(XS))):5
13:S:take#(N,XS) -> c_31(U81#(tt(),N,XS))
-->_1 U81#(tt(),N,XS) -> c_17(U82#(tt(),activate(N),activate(XS))):8
Following roots of the dependency graph are removed, as the considered set of starting terms is closed under reduction with respect to these rules (modulo compound contexts).
[(11,sel#(N,XS) -> c_26(U41#(tt(),N,XS))),(13,take#(N,XS) -> c_31(U81#(tt(),N,XS)))]
* Step 13: Decompose WORST_CASE(?,O(n^1))
+ Considered Problem:
- Strict DPs:
U11#(tt(),N,XS) -> c_1(U12#(tt(),activate(N),activate(XS)))
U12#(tt(),N,XS) -> c_2(splitAt#(activate(N),activate(XS)))
U41#(tt(),N,XS) -> c_7(U42#(tt(),activate(N),activate(XS)))
U42#(tt(),N,XS) -> c_8(afterNth#(activate(N),activate(XS)))
U61#(tt(),N,X,XS) -> c_11(U62#(tt(),activate(N),activate(X),activate(XS)))
U62#(tt(),N,X,XS) -> c_12(U63#(tt(),activate(N),activate(X),activate(XS)))
U63#(tt(),N,X,XS) -> c_13(splitAt#(activate(N),activate(XS)))
U81#(tt(),N,XS) -> c_17(U82#(tt(),activate(N),activate(XS)))
U82#(tt(),N,XS) -> c_18(splitAt#(activate(N),activate(XS)))
afterNth#(N,XS) -> c_21(U11#(tt(),N,XS))
splitAt#(s(N),cons(X,XS)) -> c_29(U61#(tt(),N,X,activate(XS)))
- Weak TRS:
activate(X) -> X
activate(n__natsFrom(X)) -> natsFrom(X)
natsFrom(N) -> cons(N,n__natsFrom(s(N)))
natsFrom(X) -> n__natsFrom(X)
- Signature:
{U11/3,U12/3,U21/2,U22/2,U31/2,U32/2,U41/3,U42/3,U51/2,U52/2,U61/4,U62/4,U63/4,U64/2,U71/2,U72/2,U81/3,U82/3
,activate/1,afterNth/2,fst/1,head/1,natsFrom/1,sel/2,snd/1,splitAt/2,tail/1,take/2,U11#/3,U12#/3,U21#/2
,U22#/2,U31#/2,U32#/2,U41#/3,U42#/3,U51#/2,U52#/2,U61#/4,U62#/4,U63#/4,U64#/2,U71#/2,U72#/2,U81#/3,U82#/3
,activate#/1,afterNth#/2,fst#/1,head#/1,natsFrom#/1,sel#/2,snd#/1,splitAt#/2,tail#/1,take#/2} / {0/0,cons/2
,n__natsFrom/1,nil/0,pair/2,s/1,tt/0,c_1/1,c_2/1,c_3/2,c_4/1,c_5/2,c_6/1,c_7/1,c_8/1,c_9/2,c_10/1,c_11/1
,c_12/1,c_13/1,c_14/1,c_15/2,c_16/1,c_17/1,c_18/1,c_19/0,c_20/1,c_21/1,c_22/1,c_23/1,c_24/0,c_25/0,c_26/1
,c_27/1,c_28/0,c_29/1,c_30/2,c_31/1}
- Obligation:
innermost runtime complexity wrt. defined symbols {U11#,U12#,U21#,U22#,U31#,U32#,U41#,U42#,U51#,U52#,U61#
,U62#,U63#,U64#,U71#,U72#,U81#,U82#,activate#,afterNth#,fst#,head#,natsFrom#,sel#,snd#,splitAt#,tail#
,take#} and constructors {0,cons,n__natsFrom,nil,pair,s,tt}
+ Applied Processor:
Decompose {onSelection = all cycle independent sub-graph, withBound = RelativeAdd}
+ Details:
We analyse the complexity of following sub-problems (R) and (S).
Problem (S) is obtained from the input problem by shifting strict rules from (R) into the weak component.
Problem (R)
- Strict DPs:
U11#(tt(),N,XS) -> c_1(U12#(tt(),activate(N),activate(XS)))
U12#(tt(),N,XS) -> c_2(splitAt#(activate(N),activate(XS)))
U61#(tt(),N,X,XS) -> c_11(U62#(tt(),activate(N),activate(X),activate(XS)))
U62#(tt(),N,X,XS) -> c_12(U63#(tt(),activate(N),activate(X),activate(XS)))
U63#(tt(),N,X,XS) -> c_13(splitAt#(activate(N),activate(XS)))
splitAt#(s(N),cons(X,XS)) -> c_29(U61#(tt(),N,X,activate(XS)))
- Weak DPs:
U41#(tt(),N,XS) -> c_7(U42#(tt(),activate(N),activate(XS)))
U42#(tt(),N,XS) -> c_8(afterNth#(activate(N),activate(XS)))
U81#(tt(),N,XS) -> c_17(U82#(tt(),activate(N),activate(XS)))
U82#(tt(),N,XS) -> c_18(splitAt#(activate(N),activate(XS)))
afterNth#(N,XS) -> c_21(U11#(tt(),N,XS))
- Weak TRS:
activate(X) -> X
activate(n__natsFrom(X)) -> natsFrom(X)
natsFrom(N) -> cons(N,n__natsFrom(s(N)))
natsFrom(X) -> n__natsFrom(X)
- Signature:
{U11/3,U12/3,U21/2,U22/2,U31/2,U32/2,U41/3,U42/3,U51/2,U52/2,U61/4,U62/4,U63/4,U64/2,U71/2,U72/2,U81/3
,U82/3,activate/1,afterNth/2,fst/1,head/1,natsFrom/1,sel/2,snd/1,splitAt/2,tail/1,take/2,U11#/3,U12#/3
,U21#/2,U22#/2,U31#/2,U32#/2,U41#/3,U42#/3,U51#/2,U52#/2,U61#/4,U62#/4,U63#/4,U64#/2,U71#/2,U72#/2,U81#/3
,U82#/3,activate#/1,afterNth#/2,fst#/1,head#/1,natsFrom#/1,sel#/2,snd#/1,splitAt#/2,tail#/1
,take#/2} / {0/0,cons/2,n__natsFrom/1,nil/0,pair/2,s/1,tt/0,c_1/1,c_2/1,c_3/2,c_4/1,c_5/2,c_6/1,c_7/1
,c_8/1,c_9/2,c_10/1,c_11/1,c_12/1,c_13/1,c_14/1,c_15/2,c_16/1,c_17/1,c_18/1,c_19/0,c_20/1,c_21/1,c_22/1
,c_23/1,c_24/0,c_25/0,c_26/1,c_27/1,c_28/0,c_29/1,c_30/2,c_31/1}
- Obligation:
innermost runtime complexity wrt. defined symbols {U11#,U12#,U21#,U22#,U31#,U32#,U41#,U42#,U51#,U52#,U61#
,U62#,U63#,U64#,U71#,U72#,U81#,U82#,activate#,afterNth#,fst#,head#,natsFrom#,sel#,snd#,splitAt#,tail#
,take#} and constructors {0,cons,n__natsFrom,nil,pair,s,tt}
Problem (S)
- Strict DPs:
U41#(tt(),N,XS) -> c_7(U42#(tt(),activate(N),activate(XS)))
U42#(tt(),N,XS) -> c_8(afterNth#(activate(N),activate(XS)))
U81#(tt(),N,XS) -> c_17(U82#(tt(),activate(N),activate(XS)))
U82#(tt(),N,XS) -> c_18(splitAt#(activate(N),activate(XS)))
afterNth#(N,XS) -> c_21(U11#(tt(),N,XS))
- Weak DPs:
U11#(tt(),N,XS) -> c_1(U12#(tt(),activate(N),activate(XS)))
U12#(tt(),N,XS) -> c_2(splitAt#(activate(N),activate(XS)))
U61#(tt(),N,X,XS) -> c_11(U62#(tt(),activate(N),activate(X),activate(XS)))
U62#(tt(),N,X,XS) -> c_12(U63#(tt(),activate(N),activate(X),activate(XS)))
U63#(tt(),N,X,XS) -> c_13(splitAt#(activate(N),activate(XS)))
splitAt#(s(N),cons(X,XS)) -> c_29(U61#(tt(),N,X,activate(XS)))
- Weak TRS:
activate(X) -> X
activate(n__natsFrom(X)) -> natsFrom(X)
natsFrom(N) -> cons(N,n__natsFrom(s(N)))
natsFrom(X) -> n__natsFrom(X)
- Signature:
{U11/3,U12/3,U21/2,U22/2,U31/2,U32/2,U41/3,U42/3,U51/2,U52/2,U61/4,U62/4,U63/4,U64/2,U71/2,U72/2,U81/3
,U82/3,activate/1,afterNth/2,fst/1,head/1,natsFrom/1,sel/2,snd/1,splitAt/2,tail/1,take/2,U11#/3,U12#/3
,U21#/2,U22#/2,U31#/2,U32#/2,U41#/3,U42#/3,U51#/2,U52#/2,U61#/4,U62#/4,U63#/4,U64#/2,U71#/2,U72#/2,U81#/3
,U82#/3,activate#/1,afterNth#/2,fst#/1,head#/1,natsFrom#/1,sel#/2,snd#/1,splitAt#/2,tail#/1
,take#/2} / {0/0,cons/2,n__natsFrom/1,nil/0,pair/2,s/1,tt/0,c_1/1,c_2/1,c_3/2,c_4/1,c_5/2,c_6/1,c_7/1
,c_8/1,c_9/2,c_10/1,c_11/1,c_12/1,c_13/1,c_14/1,c_15/2,c_16/1,c_17/1,c_18/1,c_19/0,c_20/1,c_21/1,c_22/1
,c_23/1,c_24/0,c_25/0,c_26/1,c_27/1,c_28/0,c_29/1,c_30/2,c_31/1}
- Obligation:
innermost runtime complexity wrt. defined symbols {U11#,U12#,U21#,U22#,U31#,U32#,U41#,U42#,U51#,U52#,U61#
,U62#,U63#,U64#,U71#,U72#,U81#,U82#,activate#,afterNth#,fst#,head#,natsFrom#,sel#,snd#,splitAt#,tail#
,take#} and constructors {0,cons,n__natsFrom,nil,pair,s,tt}
** Step 13.a:1: PredecessorEstimationCP WORST_CASE(?,O(n^1))
+ Considered Problem:
- Strict DPs:
U11#(tt(),N,XS) -> c_1(U12#(tt(),activate(N),activate(XS)))
U12#(tt(),N,XS) -> c_2(splitAt#(activate(N),activate(XS)))
U61#(tt(),N,X,XS) -> c_11(U62#(tt(),activate(N),activate(X),activate(XS)))
U62#(tt(),N,X,XS) -> c_12(U63#(tt(),activate(N),activate(X),activate(XS)))
U63#(tt(),N,X,XS) -> c_13(splitAt#(activate(N),activate(XS)))
splitAt#(s(N),cons(X,XS)) -> c_29(U61#(tt(),N,X,activate(XS)))
- Weak DPs:
U41#(tt(),N,XS) -> c_7(U42#(tt(),activate(N),activate(XS)))
U42#(tt(),N,XS) -> c_8(afterNth#(activate(N),activate(XS)))
U81#(tt(),N,XS) -> c_17(U82#(tt(),activate(N),activate(XS)))
U82#(tt(),N,XS) -> c_18(splitAt#(activate(N),activate(XS)))
afterNth#(N,XS) -> c_21(U11#(tt(),N,XS))
- Weak TRS:
activate(X) -> X
activate(n__natsFrom(X)) -> natsFrom(X)
natsFrom(N) -> cons(N,n__natsFrom(s(N)))
natsFrom(X) -> n__natsFrom(X)
- Signature:
{U11/3,U12/3,U21/2,U22/2,U31/2,U32/2,U41/3,U42/3,U51/2,U52/2,U61/4,U62/4,U63/4,U64/2,U71/2,U72/2,U81/3,U82/3
,activate/1,afterNth/2,fst/1,head/1,natsFrom/1,sel/2,snd/1,splitAt/2,tail/1,take/2,U11#/3,U12#/3,U21#/2
,U22#/2,U31#/2,U32#/2,U41#/3,U42#/3,U51#/2,U52#/2,U61#/4,U62#/4,U63#/4,U64#/2,U71#/2,U72#/2,U81#/3,U82#/3
,activate#/1,afterNth#/2,fst#/1,head#/1,natsFrom#/1,sel#/2,snd#/1,splitAt#/2,tail#/1,take#/2} / {0/0,cons/2
,n__natsFrom/1,nil/0,pair/2,s/1,tt/0,c_1/1,c_2/1,c_3/2,c_4/1,c_5/2,c_6/1,c_7/1,c_8/1,c_9/2,c_10/1,c_11/1
,c_12/1,c_13/1,c_14/1,c_15/2,c_16/1,c_17/1,c_18/1,c_19/0,c_20/1,c_21/1,c_22/1,c_23/1,c_24/0,c_25/0,c_26/1
,c_27/1,c_28/0,c_29/1,c_30/2,c_31/1}
- Obligation:
innermost runtime complexity wrt. defined symbols {U11#,U12#,U21#,U22#,U31#,U32#,U41#,U42#,U51#,U52#,U61#
,U62#,U63#,U64#,U71#,U72#,U81#,U82#,activate#,afterNth#,fst#,head#,natsFrom#,sel#,snd#,splitAt#,tail#
,take#} and constructors {0,cons,n__natsFrom,nil,pair,s,tt}
+ Applied Processor:
PredecessorEstimationCP {onSelectionCP = any intersect of rules of CDG leaf and strict-rules, withComplexityPair = NaturalMI {miDimension = 1, miDegree = 1, miKind = Algebraic, uargs = UArgs, urules = URules, selector = Nothing}}
+ Details:
We first use the processor NaturalMI {miDimension = 1, miDegree = 1, miKind = Algebraic, uargs = UArgs, urules = URules, selector = Nothing} to orient following rules strictly:
1: U11#(tt(),N,XS) -> c_1(U12#(tt(),activate(N),activate(XS)))
2: U12#(tt(),N,XS) -> c_2(splitAt#(activate(N),activate(XS)))
5: U61#(tt(),N,X,XS) -> c_11(U62#(tt(),activate(N),activate(X),activate(XS)))
12: splitAt#(s(N),cons(X,XS)) -> c_29(U61#(tt(),N,X,activate(XS)))
Consider the set of all dependency pairs
1: U11#(tt(),N,XS) -> c_1(U12#(tt(),activate(N),activate(XS)))
2: U12#(tt(),N,XS) -> c_2(splitAt#(activate(N),activate(XS)))
3: U41#(tt(),N,XS) -> c_7(U42#(tt(),activate(N),activate(XS)))
4: U42#(tt(),N,XS) -> c_8(afterNth#(activate(N),activate(XS)))
5: U61#(tt(),N,X,XS) -> c_11(U62#(tt(),activate(N),activate(X),activate(XS)))
6: U62#(tt(),N,X,XS) -> c_12(U63#(tt(),activate(N),activate(X),activate(XS)))
7: U63#(tt(),N,X,XS) -> c_13(splitAt#(activate(N),activate(XS)))
8: U81#(tt(),N,XS) -> c_17(U82#(tt(),activate(N),activate(XS)))
9: U82#(tt(),N,XS) -> c_18(splitAt#(activate(N),activate(XS)))
10: afterNth#(N,XS) -> c_21(U11#(tt(),N,XS))
12: splitAt#(s(N),cons(X,XS)) -> c_29(U61#(tt(),N,X,activate(XS)))
Processor NaturalMI {miDimension = 1, miDegree = 1, miKind = Algebraic, uargs = UArgs, urules = URules, selector = Nothing}induces the complexity certificateTIME (?,O(n^1))
SPACE(?,?)on application of the dependency pairs
{1,2,5,12}
These cover all (indirect) predecessors of dependency pairs
{1,2,3,4,5,6,7,8,9,10,12}
their number of applications is equally bounded.
The dependency pairs are shifted into the weak component.
*** Step 13.a:1.a:1: NaturalMI WORST_CASE(?,O(n^1))
+ Considered Problem:
- Strict DPs:
U11#(tt(),N,XS) -> c_1(U12#(tt(),activate(N),activate(XS)))
U12#(tt(),N,XS) -> c_2(splitAt#(activate(N),activate(XS)))
U61#(tt(),N,X,XS) -> c_11(U62#(tt(),activate(N),activate(X),activate(XS)))
U62#(tt(),N,X,XS) -> c_12(U63#(tt(),activate(N),activate(X),activate(XS)))
U63#(tt(),N,X,XS) -> c_13(splitAt#(activate(N),activate(XS)))
splitAt#(s(N),cons(X,XS)) -> c_29(U61#(tt(),N,X,activate(XS)))
- Weak DPs:
U41#(tt(),N,XS) -> c_7(U42#(tt(),activate(N),activate(XS)))
U42#(tt(),N,XS) -> c_8(afterNth#(activate(N),activate(XS)))
U81#(tt(),N,XS) -> c_17(U82#(tt(),activate(N),activate(XS)))
U82#(tt(),N,XS) -> c_18(splitAt#(activate(N),activate(XS)))
afterNth#(N,XS) -> c_21(U11#(tt(),N,XS))
- Weak TRS:
activate(X) -> X
activate(n__natsFrom(X)) -> natsFrom(X)
natsFrom(N) -> cons(N,n__natsFrom(s(N)))
natsFrom(X) -> n__natsFrom(X)
- Signature:
{U11/3,U12/3,U21/2,U22/2,U31/2,U32/2,U41/3,U42/3,U51/2,U52/2,U61/4,U62/4,U63/4,U64/2,U71/2,U72/2,U81/3,U82/3
,activate/1,afterNth/2,fst/1,head/1,natsFrom/1,sel/2,snd/1,splitAt/2,tail/1,take/2,U11#/3,U12#/3,U21#/2
,U22#/2,U31#/2,U32#/2,U41#/3,U42#/3,U51#/2,U52#/2,U61#/4,U62#/4,U63#/4,U64#/2,U71#/2,U72#/2,U81#/3,U82#/3
,activate#/1,afterNth#/2,fst#/1,head#/1,natsFrom#/1,sel#/2,snd#/1,splitAt#/2,tail#/1,take#/2} / {0/0,cons/2
,n__natsFrom/1,nil/0,pair/2,s/1,tt/0,c_1/1,c_2/1,c_3/2,c_4/1,c_5/2,c_6/1,c_7/1,c_8/1,c_9/2,c_10/1,c_11/1
,c_12/1,c_13/1,c_14/1,c_15/2,c_16/1,c_17/1,c_18/1,c_19/0,c_20/1,c_21/1,c_22/1,c_23/1,c_24/0,c_25/0,c_26/1
,c_27/1,c_28/0,c_29/1,c_30/2,c_31/1}
- Obligation:
innermost runtime complexity wrt. defined symbols {U11#,U12#,U21#,U22#,U31#,U32#,U41#,U42#,U51#,U52#,U61#
,U62#,U63#,U64#,U71#,U72#,U81#,U82#,activate#,afterNth#,fst#,head#,natsFrom#,sel#,snd#,splitAt#,tail#
,take#} and constructors {0,cons,n__natsFrom,nil,pair,s,tt}
+ Applied Processor:
NaturalMI {miDimension = 1, miDegree = 1, miKind = Algebraic, uargs = UArgs, urules = URules, selector = Just first alternative for predecessorEstimation on any intersect of rules of CDG leaf and strict-rules}
+ Details:
We apply a matrix interpretation of kind constructor based matrix interpretation:
The following argument positions are considered usable:
uargs(c_1) = {1},
uargs(c_2) = {1},
uargs(c_7) = {1},
uargs(c_8) = {1},
uargs(c_11) = {1},
uargs(c_12) = {1},
uargs(c_13) = {1},
uargs(c_17) = {1},
uargs(c_18) = {1},
uargs(c_21) = {1},
uargs(c_29) = {1}
Following symbols are considered usable:
{activate,natsFrom,U11#,U12#,U21#,U22#,U31#,U32#,U41#,U42#,U51#,U52#,U61#,U62#,U63#,U64#,U71#,U72#,U81#
,U82#,activate#,afterNth#,fst#,head#,natsFrom#,sel#,snd#,splitAt#,tail#,take#}
TcT has computed the following interpretation:
p(0) = [0]
p(U11) = [2] x1 + [1] x2 + [1] x3 + [0]
p(U12) = [1] x3 + [2]
p(U21) = [1] x2 + [0]
p(U22) = [1] x1 + [0]
p(U31) = [2] x2 + [0]
p(U32) = [2] x1 + [2] x2 + [1]
p(U41) = [2] x2 + [1] x3 + [0]
p(U42) = [1] x3 + [1]
p(U51) = [2] x2 + [4]
p(U52) = [1] x1 + [2]
p(U61) = [1] x2 + [0]
p(U62) = [1] x2 + [2] x3 + [1] x4 + [1]
p(U63) = [1] x2 + [4] x3 + [0]
p(U64) = [1] x2 + [1]
p(U71) = [1] x1 + [1]
p(U72) = [1] x2 + [2]
p(U81) = [2] x1 + [1] x2 + [4] x3 + [0]
p(U82) = [1] x2 + [0]
p(activate) = [1] x1 + [0]
p(afterNth) = [0]
p(cons) = [0]
p(fst) = [1]
p(head) = [0]
p(n__natsFrom) = [0]
p(natsFrom) = [0]
p(nil) = [0]
p(pair) = [1] x1 + [4]
p(s) = [1] x1 + [2]
p(sel) = [1] x1 + [1] x2 + [1]
p(snd) = [0]
p(splitAt) = [4] x2 + [1]
p(tail) = [2] x1 + [0]
p(take) = [1]
p(tt) = [1]
p(U11#) = [1] x1 + [4] x2 + [6]
p(U12#) = [6] x1 + [4] x2 + [0]
p(U21#) = [1] x1 + [0]
p(U22#) = [2] x2 + [4]
p(U31#) = [1] x2 + [1]
p(U32#) = [0]
p(U41#) = [5] x1 + [4] x2 + [6]
p(U42#) = [1] x1 + [4] x2 + [6]
p(U51#) = [1] x1 + [2]
p(U52#) = [4] x1 + [0]
p(U61#) = [4] x1 + [4] x2 + [3]
p(U62#) = [4] x1 + [4] x2 + [1]
p(U63#) = [1] x1 + [4] x2 + [4]
p(U64#) = [1] x2 + [1]
p(U71#) = [4] x1 + [0]
p(U72#) = [2]
p(U81#) = [4] x1 + [4] x2 + [1] x3 + [6]
p(U82#) = [4] x2 + [6]
p(activate#) = [2]
p(afterNth#) = [4] x1 + [7]
p(fst#) = [0]
p(head#) = [1]
p(natsFrom#) = [0]
p(sel#) = [1] x1 + [4]
p(snd#) = [4] x1 + [0]
p(splitAt#) = [4] x1 + [5]
p(tail#) = [1] x1 + [0]
p(take#) = [0]
p(c_1) = [1] x1 + [0]
p(c_2) = [1] x1 + [0]
p(c_3) = [1] x1 + [4]
p(c_4) = [4]
p(c_5) = [2] x2 + [1]
p(c_6) = [1]
p(c_7) = [1] x1 + [4]
p(c_8) = [1] x1 + [0]
p(c_9) = [1] x1 + [4] x2 + [4]
p(c_10) = [4] x1 + [0]
p(c_11) = [1] x1 + [0]
p(c_12) = [1] x1 + [0]
p(c_13) = [1] x1 + [0]
p(c_14) = [0]
p(c_15) = [0]
p(c_16) = [1] x1 + [0]
p(c_17) = [1] x1 + [4]
p(c_18) = [1] x1 + [0]
p(c_19) = [0]
p(c_20) = [1]
p(c_21) = [1] x1 + [0]
p(c_22) = [1]
p(c_23) = [1] x1 + [4]
p(c_24) = [1]
p(c_25) = [0]
p(c_26) = [1] x1 + [1]
p(c_27) = [1] x1 + [0]
p(c_28) = [1]
p(c_29) = [1] x1 + [5]
p(c_30) = [2]
p(c_31) = [1] x1 + [0]
Following rules are strictly oriented:
U11#(tt(),N,XS) = [4] N + [7]
> [4] N + [6]
= c_1(U12#(tt(),activate(N),activate(XS)))
U12#(tt(),N,XS) = [4] N + [6]
> [4] N + [5]
= c_2(splitAt#(activate(N),activate(XS)))
U61#(tt(),N,X,XS) = [4] N + [7]
> [4] N + [5]
= c_11(U62#(tt(),activate(N),activate(X),activate(XS)))
splitAt#(s(N),cons(X,XS)) = [4] N + [13]
> [4] N + [12]
= c_29(U61#(tt(),N,X,activate(XS)))
Following rules are (at-least) weakly oriented:
U41#(tt(),N,XS) = [4] N + [11]
>= [4] N + [11]
= c_7(U42#(tt(),activate(N),activate(XS)))
U42#(tt(),N,XS) = [4] N + [7]
>= [4] N + [7]
= c_8(afterNth#(activate(N),activate(XS)))
U62#(tt(),N,X,XS) = [4] N + [5]
>= [4] N + [5]
= c_12(U63#(tt(),activate(N),activate(X),activate(XS)))
U63#(tt(),N,X,XS) = [4] N + [5]
>= [4] N + [5]
= c_13(splitAt#(activate(N),activate(XS)))
U81#(tt(),N,XS) = [4] N + [1] XS + [10]
>= [4] N + [10]
= c_17(U82#(tt(),activate(N),activate(XS)))
U82#(tt(),N,XS) = [4] N + [6]
>= [4] N + [5]
= c_18(splitAt#(activate(N),activate(XS)))
afterNth#(N,XS) = [4] N + [7]
>= [4] N + [7]
= c_21(U11#(tt(),N,XS))
activate(X) = [1] X + [0]
>= [1] X + [0]
= X
activate(n__natsFrom(X)) = [0]
>= [0]
= natsFrom(X)
natsFrom(N) = [0]
>= [0]
= cons(N,n__natsFrom(s(N)))
natsFrom(X) = [0]
>= [0]
= n__natsFrom(X)
*** Step 13.a:1.a:2: Assumption WORST_CASE(?,O(1))
+ Considered Problem:
- Strict DPs:
U62#(tt(),N,X,XS) -> c_12(U63#(tt(),activate(N),activate(X),activate(XS)))
U63#(tt(),N,X,XS) -> c_13(splitAt#(activate(N),activate(XS)))
- Weak DPs:
U11#(tt(),N,XS) -> c_1(U12#(tt(),activate(N),activate(XS)))
U12#(tt(),N,XS) -> c_2(splitAt#(activate(N),activate(XS)))
U41#(tt(),N,XS) -> c_7(U42#(tt(),activate(N),activate(XS)))
U42#(tt(),N,XS) -> c_8(afterNth#(activate(N),activate(XS)))
U61#(tt(),N,X,XS) -> c_11(U62#(tt(),activate(N),activate(X),activate(XS)))
U81#(tt(),N,XS) -> c_17(U82#(tt(),activate(N),activate(XS)))
U82#(tt(),N,XS) -> c_18(splitAt#(activate(N),activate(XS)))
afterNth#(N,XS) -> c_21(U11#(tt(),N,XS))
splitAt#(s(N),cons(X,XS)) -> c_29(U61#(tt(),N,X,activate(XS)))
- Weak TRS:
activate(X) -> X
activate(n__natsFrom(X)) -> natsFrom(X)
natsFrom(N) -> cons(N,n__natsFrom(s(N)))
natsFrom(X) -> n__natsFrom(X)
- Signature:
{U11/3,U12/3,U21/2,U22/2,U31/2,U32/2,U41/3,U42/3,U51/2,U52/2,U61/4,U62/4,U63/4,U64/2,U71/2,U72/2,U81/3,U82/3
,activate/1,afterNth/2,fst/1,head/1,natsFrom/1,sel/2,snd/1,splitAt/2,tail/1,take/2,U11#/3,U12#/3,U21#/2
,U22#/2,U31#/2,U32#/2,U41#/3,U42#/3,U51#/2,U52#/2,U61#/4,U62#/4,U63#/4,U64#/2,U71#/2,U72#/2,U81#/3,U82#/3
,activate#/1,afterNth#/2,fst#/1,head#/1,natsFrom#/1,sel#/2,snd#/1,splitAt#/2,tail#/1,take#/2} / {0/0,cons/2
,n__natsFrom/1,nil/0,pair/2,s/1,tt/0,c_1/1,c_2/1,c_3/2,c_4/1,c_5/2,c_6/1,c_7/1,c_8/1,c_9/2,c_10/1,c_11/1
,c_12/1,c_13/1,c_14/1,c_15/2,c_16/1,c_17/1,c_18/1,c_19/0,c_20/1,c_21/1,c_22/1,c_23/1,c_24/0,c_25/0,c_26/1
,c_27/1,c_28/0,c_29/1,c_30/2,c_31/1}
- Obligation:
innermost runtime complexity wrt. defined symbols {U11#,U12#,U21#,U22#,U31#,U32#,U41#,U42#,U51#,U52#,U61#
,U62#,U63#,U64#,U71#,U72#,U81#,U82#,activate#,afterNth#,fst#,head#,natsFrom#,sel#,snd#,splitAt#,tail#
,take#} and constructors {0,cons,n__natsFrom,nil,pair,s,tt}
+ Applied Processor:
Assumption {assumed = Certificate {spaceUB = Unknown, spaceLB = Unknown, timeUB = Poly (Just 0), timeLB = Unknown}}
+ Details:
()
*** Step 13.a:1.b:1: RemoveWeakSuffixes WORST_CASE(?,O(1))
+ Considered Problem:
- Weak DPs:
U11#(tt(),N,XS) -> c_1(U12#(tt(),activate(N),activate(XS)))
U12#(tt(),N,XS) -> c_2(splitAt#(activate(N),activate(XS)))
U41#(tt(),N,XS) -> c_7(U42#(tt(),activate(N),activate(XS)))
U42#(tt(),N,XS) -> c_8(afterNth#(activate(N),activate(XS)))
U61#(tt(),N,X,XS) -> c_11(U62#(tt(),activate(N),activate(X),activate(XS)))
U62#(tt(),N,X,XS) -> c_12(U63#(tt(),activate(N),activate(X),activate(XS)))
U63#(tt(),N,X,XS) -> c_13(splitAt#(activate(N),activate(XS)))
U81#(tt(),N,XS) -> c_17(U82#(tt(),activate(N),activate(XS)))
U82#(tt(),N,XS) -> c_18(splitAt#(activate(N),activate(XS)))
afterNth#(N,XS) -> c_21(U11#(tt(),N,XS))
splitAt#(s(N),cons(X,XS)) -> c_29(U61#(tt(),N,X,activate(XS)))
- Weak TRS:
activate(X) -> X
activate(n__natsFrom(X)) -> natsFrom(X)
natsFrom(N) -> cons(N,n__natsFrom(s(N)))
natsFrom(X) -> n__natsFrom(X)
- Signature:
{U11/3,U12/3,U21/2,U22/2,U31/2,U32/2,U41/3,U42/3,U51/2,U52/2,U61/4,U62/4,U63/4,U64/2,U71/2,U72/2,U81/3,U82/3
,activate/1,afterNth/2,fst/1,head/1,natsFrom/1,sel/2,snd/1,splitAt/2,tail/1,take/2,U11#/3,U12#/3,U21#/2
,U22#/2,U31#/2,U32#/2,U41#/3,U42#/3,U51#/2,U52#/2,U61#/4,U62#/4,U63#/4,U64#/2,U71#/2,U72#/2,U81#/3,U82#/3
,activate#/1,afterNth#/2,fst#/1,head#/1,natsFrom#/1,sel#/2,snd#/1,splitAt#/2,tail#/1,take#/2} / {0/0,cons/2
,n__natsFrom/1,nil/0,pair/2,s/1,tt/0,c_1/1,c_2/1,c_3/2,c_4/1,c_5/2,c_6/1,c_7/1,c_8/1,c_9/2,c_10/1,c_11/1
,c_12/1,c_13/1,c_14/1,c_15/2,c_16/1,c_17/1,c_18/1,c_19/0,c_20/1,c_21/1,c_22/1,c_23/1,c_24/0,c_25/0,c_26/1
,c_27/1,c_28/0,c_29/1,c_30/2,c_31/1}
- Obligation:
innermost runtime complexity wrt. defined symbols {U11#,U12#,U21#,U22#,U31#,U32#,U41#,U42#,U51#,U52#,U61#
,U62#,U63#,U64#,U71#,U72#,U81#,U82#,activate#,afterNth#,fst#,head#,natsFrom#,sel#,snd#,splitAt#,tail#
,take#} and constructors {0,cons,n__natsFrom,nil,pair,s,tt}
+ Applied Processor:
RemoveWeakSuffixes
+ Details:
Consider the dependency graph
1:W:U11#(tt(),N,XS) -> c_1(U12#(tt(),activate(N),activate(XS)))
-->_1 U12#(tt(),N,XS) -> c_2(splitAt#(activate(N),activate(XS))):2
2:W:U12#(tt(),N,XS) -> c_2(splitAt#(activate(N),activate(XS)))
-->_1 splitAt#(s(N),cons(X,XS)) -> c_29(U61#(tt(),N,X,activate(XS))):11
3:W:U41#(tt(),N,XS) -> c_7(U42#(tt(),activate(N),activate(XS)))
-->_1 U42#(tt(),N,XS) -> c_8(afterNth#(activate(N),activate(XS))):4
4:W:U42#(tt(),N,XS) -> c_8(afterNth#(activate(N),activate(XS)))
-->_1 afterNth#(N,XS) -> c_21(U11#(tt(),N,XS)):10
5:W:U61#(tt(),N,X,XS) -> c_11(U62#(tt(),activate(N),activate(X),activate(XS)))
-->_1 U62#(tt(),N,X,XS) -> c_12(U63#(tt(),activate(N),activate(X),activate(XS))):6
6:W:U62#(tt(),N,X,XS) -> c_12(U63#(tt(),activate(N),activate(X),activate(XS)))
-->_1 U63#(tt(),N,X,XS) -> c_13(splitAt#(activate(N),activate(XS))):7
7:W:U63#(tt(),N,X,XS) -> c_13(splitAt#(activate(N),activate(XS)))
-->_1 splitAt#(s(N),cons(X,XS)) -> c_29(U61#(tt(),N,X,activate(XS))):11
8:W:U81#(tt(),N,XS) -> c_17(U82#(tt(),activate(N),activate(XS)))
-->_1 U82#(tt(),N,XS) -> c_18(splitAt#(activate(N),activate(XS))):9
9:W:U82#(tt(),N,XS) -> c_18(splitAt#(activate(N),activate(XS)))
-->_1 splitAt#(s(N),cons(X,XS)) -> c_29(U61#(tt(),N,X,activate(XS))):11
10:W:afterNth#(N,XS) -> c_21(U11#(tt(),N,XS))
-->_1 U11#(tt(),N,XS) -> c_1(U12#(tt(),activate(N),activate(XS))):1
11:W:splitAt#(s(N),cons(X,XS)) -> c_29(U61#(tt(),N,X,activate(XS)))
-->_1 U61#(tt(),N,X,XS) -> c_11(U62#(tt(),activate(N),activate(X),activate(XS))):5
The following weak DPs constitute a sub-graph of the DG that is closed under successors. The DPs are removed.
8: U81#(tt(),N,XS) -> c_17(U82#(tt(),activate(N),activate(XS)))
9: U82#(tt(),N,XS) -> c_18(splitAt#(activate(N),activate(XS)))
3: U41#(tt(),N,XS) -> c_7(U42#(tt(),activate(N),activate(XS)))
4: U42#(tt(),N,XS) -> c_8(afterNth#(activate(N),activate(XS)))
10: afterNth#(N,XS) -> c_21(U11#(tt(),N,XS))
1: U11#(tt(),N,XS) -> c_1(U12#(tt(),activate(N),activate(XS)))
2: U12#(tt(),N,XS) -> c_2(splitAt#(activate(N),activate(XS)))
11: splitAt#(s(N),cons(X,XS)) -> c_29(U61#(tt(),N,X,activate(XS)))
7: U63#(tt(),N,X,XS) -> c_13(splitAt#(activate(N),activate(XS)))
6: U62#(tt(),N,X,XS) -> c_12(U63#(tt(),activate(N),activate(X),activate(XS)))
5: U61#(tt(),N,X,XS) -> c_11(U62#(tt(),activate(N),activate(X),activate(XS)))
*** Step 13.a:1.b:2: EmptyProcessor WORST_CASE(?,O(1))
+ Considered Problem:
- Weak TRS:
activate(X) -> X
activate(n__natsFrom(X)) -> natsFrom(X)
natsFrom(N) -> cons(N,n__natsFrom(s(N)))
natsFrom(X) -> n__natsFrom(X)
- Signature:
{U11/3,U12/3,U21/2,U22/2,U31/2,U32/2,U41/3,U42/3,U51/2,U52/2,U61/4,U62/4,U63/4,U64/2,U71/2,U72/2,U81/3,U82/3
,activate/1,afterNth/2,fst/1,head/1,natsFrom/1,sel/2,snd/1,splitAt/2,tail/1,take/2,U11#/3,U12#/3,U21#/2
,U22#/2,U31#/2,U32#/2,U41#/3,U42#/3,U51#/2,U52#/2,U61#/4,U62#/4,U63#/4,U64#/2,U71#/2,U72#/2,U81#/3,U82#/3
,activate#/1,afterNth#/2,fst#/1,head#/1,natsFrom#/1,sel#/2,snd#/1,splitAt#/2,tail#/1,take#/2} / {0/0,cons/2
,n__natsFrom/1,nil/0,pair/2,s/1,tt/0,c_1/1,c_2/1,c_3/2,c_4/1,c_5/2,c_6/1,c_7/1,c_8/1,c_9/2,c_10/1,c_11/1
,c_12/1,c_13/1,c_14/1,c_15/2,c_16/1,c_17/1,c_18/1,c_19/0,c_20/1,c_21/1,c_22/1,c_23/1,c_24/0,c_25/0,c_26/1
,c_27/1,c_28/0,c_29/1,c_30/2,c_31/1}
- Obligation:
innermost runtime complexity wrt. defined symbols {U11#,U12#,U21#,U22#,U31#,U32#,U41#,U42#,U51#,U52#,U61#
,U62#,U63#,U64#,U71#,U72#,U81#,U82#,activate#,afterNth#,fst#,head#,natsFrom#,sel#,snd#,splitAt#,tail#
,take#} and constructors {0,cons,n__natsFrom,nil,pair,s,tt}
+ Applied Processor:
EmptyProcessor
+ Details:
The problem is already closed. The intended complexity is O(1).
** Step 13.b:1: PredecessorEstimation WORST_CASE(?,O(1))
+ Considered Problem:
- Strict DPs:
U41#(tt(),N,XS) -> c_7(U42#(tt(),activate(N),activate(XS)))
U42#(tt(),N,XS) -> c_8(afterNth#(activate(N),activate(XS)))
U81#(tt(),N,XS) -> c_17(U82#(tt(),activate(N),activate(XS)))
U82#(tt(),N,XS) -> c_18(splitAt#(activate(N),activate(XS)))
afterNth#(N,XS) -> c_21(U11#(tt(),N,XS))
- Weak DPs:
U11#(tt(),N,XS) -> c_1(U12#(tt(),activate(N),activate(XS)))
U12#(tt(),N,XS) -> c_2(splitAt#(activate(N),activate(XS)))
U61#(tt(),N,X,XS) -> c_11(U62#(tt(),activate(N),activate(X),activate(XS)))
U62#(tt(),N,X,XS) -> c_12(U63#(tt(),activate(N),activate(X),activate(XS)))
U63#(tt(),N,X,XS) -> c_13(splitAt#(activate(N),activate(XS)))
splitAt#(s(N),cons(X,XS)) -> c_29(U61#(tt(),N,X,activate(XS)))
- Weak TRS:
activate(X) -> X
activate(n__natsFrom(X)) -> natsFrom(X)
natsFrom(N) -> cons(N,n__natsFrom(s(N)))
natsFrom(X) -> n__natsFrom(X)
- Signature:
{U11/3,U12/3,U21/2,U22/2,U31/2,U32/2,U41/3,U42/3,U51/2,U52/2,U61/4,U62/4,U63/4,U64/2,U71/2,U72/2,U81/3,U82/3
,activate/1,afterNth/2,fst/1,head/1,natsFrom/1,sel/2,snd/1,splitAt/2,tail/1,take/2,U11#/3,U12#/3,U21#/2
,U22#/2,U31#/2,U32#/2,U41#/3,U42#/3,U51#/2,U52#/2,U61#/4,U62#/4,U63#/4,U64#/2,U71#/2,U72#/2,U81#/3,U82#/3
,activate#/1,afterNth#/2,fst#/1,head#/1,natsFrom#/1,sel#/2,snd#/1,splitAt#/2,tail#/1,take#/2} / {0/0,cons/2
,n__natsFrom/1,nil/0,pair/2,s/1,tt/0,c_1/1,c_2/1,c_3/2,c_4/1,c_5/2,c_6/1,c_7/1,c_8/1,c_9/2,c_10/1,c_11/1
,c_12/1,c_13/1,c_14/1,c_15/2,c_16/1,c_17/1,c_18/1,c_19/0,c_20/1,c_21/1,c_22/1,c_23/1,c_24/0,c_25/0,c_26/1
,c_27/1,c_28/0,c_29/1,c_30/2,c_31/1}
- Obligation:
innermost runtime complexity wrt. defined symbols {U11#,U12#,U21#,U22#,U31#,U32#,U41#,U42#,U51#,U52#,U61#
,U62#,U63#,U64#,U71#,U72#,U81#,U82#,activate#,afterNth#,fst#,head#,natsFrom#,sel#,snd#,splitAt#,tail#
,take#} and constructors {0,cons,n__natsFrom,nil,pair,s,tt}
+ Applied Processor:
PredecessorEstimation {onSelection = all simple predecessor estimation selector}
+ Details:
We estimate the number of application of
{4,5}
by application of
Pre({4,5}) = {2,3}.
Here rules are labelled as follows:
1: U41#(tt(),N,XS) -> c_7(U42#(tt(),activate(N),activate(XS)))
2: U42#(tt(),N,XS) -> c_8(afterNth#(activate(N),activate(XS)))
3: U81#(tt(),N,XS) -> c_17(U82#(tt(),activate(N),activate(XS)))
4: U82#(tt(),N,XS) -> c_18(splitAt#(activate(N),activate(XS)))
5: afterNth#(N,XS) -> c_21(U11#(tt(),N,XS))
6: U11#(tt(),N,XS) -> c_1(U12#(tt(),activate(N),activate(XS)))
7: U12#(tt(),N,XS) -> c_2(splitAt#(activate(N),activate(XS)))
8: U61#(tt(),N,X,XS) -> c_11(U62#(tt(),activate(N),activate(X),activate(XS)))
9: U62#(tt(),N,X,XS) -> c_12(U63#(tt(),activate(N),activate(X),activate(XS)))
10: U63#(tt(),N,X,XS) -> c_13(splitAt#(activate(N),activate(XS)))
11: splitAt#(s(N),cons(X,XS)) -> c_29(U61#(tt(),N,X,activate(XS)))
** Step 13.b:2: PredecessorEstimation WORST_CASE(?,O(1))
+ Considered Problem:
- Strict DPs:
U41#(tt(),N,XS) -> c_7(U42#(tt(),activate(N),activate(XS)))
U42#(tt(),N,XS) -> c_8(afterNth#(activate(N),activate(XS)))
U81#(tt(),N,XS) -> c_17(U82#(tt(),activate(N),activate(XS)))
- Weak DPs:
U11#(tt(),N,XS) -> c_1(U12#(tt(),activate(N),activate(XS)))
U12#(tt(),N,XS) -> c_2(splitAt#(activate(N),activate(XS)))
U61#(tt(),N,X,XS) -> c_11(U62#(tt(),activate(N),activate(X),activate(XS)))
U62#(tt(),N,X,XS) -> c_12(U63#(tt(),activate(N),activate(X),activate(XS)))
U63#(tt(),N,X,XS) -> c_13(splitAt#(activate(N),activate(XS)))
U82#(tt(),N,XS) -> c_18(splitAt#(activate(N),activate(XS)))
afterNth#(N,XS) -> c_21(U11#(tt(),N,XS))
splitAt#(s(N),cons(X,XS)) -> c_29(U61#(tt(),N,X,activate(XS)))
- Weak TRS:
activate(X) -> X
activate(n__natsFrom(X)) -> natsFrom(X)
natsFrom(N) -> cons(N,n__natsFrom(s(N)))
natsFrom(X) -> n__natsFrom(X)
- Signature:
{U11/3,U12/3,U21/2,U22/2,U31/2,U32/2,U41/3,U42/3,U51/2,U52/2,U61/4,U62/4,U63/4,U64/2,U71/2,U72/2,U81/3,U82/3
,activate/1,afterNth/2,fst/1,head/1,natsFrom/1,sel/2,snd/1,splitAt/2,tail/1,take/2,U11#/3,U12#/3,U21#/2
,U22#/2,U31#/2,U32#/2,U41#/3,U42#/3,U51#/2,U52#/2,U61#/4,U62#/4,U63#/4,U64#/2,U71#/2,U72#/2,U81#/3,U82#/3
,activate#/1,afterNth#/2,fst#/1,head#/1,natsFrom#/1,sel#/2,snd#/1,splitAt#/2,tail#/1,take#/2} / {0/0,cons/2
,n__natsFrom/1,nil/0,pair/2,s/1,tt/0,c_1/1,c_2/1,c_3/2,c_4/1,c_5/2,c_6/1,c_7/1,c_8/1,c_9/2,c_10/1,c_11/1
,c_12/1,c_13/1,c_14/1,c_15/2,c_16/1,c_17/1,c_18/1,c_19/0,c_20/1,c_21/1,c_22/1,c_23/1,c_24/0,c_25/0,c_26/1
,c_27/1,c_28/0,c_29/1,c_30/2,c_31/1}
- Obligation:
innermost runtime complexity wrt. defined symbols {U11#,U12#,U21#,U22#,U31#,U32#,U41#,U42#,U51#,U52#,U61#
,U62#,U63#,U64#,U71#,U72#,U81#,U82#,activate#,afterNth#,fst#,head#,natsFrom#,sel#,snd#,splitAt#,tail#
,take#} and constructors {0,cons,n__natsFrom,nil,pair,s,tt}
+ Applied Processor:
PredecessorEstimation {onSelection = all simple predecessor estimation selector}
+ Details:
We estimate the number of application of
{2,3}
by application of
Pre({2,3}) = {1}.
Here rules are labelled as follows:
1: U41#(tt(),N,XS) -> c_7(U42#(tt(),activate(N),activate(XS)))
2: U42#(tt(),N,XS) -> c_8(afterNth#(activate(N),activate(XS)))
3: U81#(tt(),N,XS) -> c_17(U82#(tt(),activate(N),activate(XS)))
4: U11#(tt(),N,XS) -> c_1(U12#(tt(),activate(N),activate(XS)))
5: U12#(tt(),N,XS) -> c_2(splitAt#(activate(N),activate(XS)))
6: U61#(tt(),N,X,XS) -> c_11(U62#(tt(),activate(N),activate(X),activate(XS)))
7: U62#(tt(),N,X,XS) -> c_12(U63#(tt(),activate(N),activate(X),activate(XS)))
8: U63#(tt(),N,X,XS) -> c_13(splitAt#(activate(N),activate(XS)))
9: U82#(tt(),N,XS) -> c_18(splitAt#(activate(N),activate(XS)))
10: afterNth#(N,XS) -> c_21(U11#(tt(),N,XS))
11: splitAt#(s(N),cons(X,XS)) -> c_29(U61#(tt(),N,X,activate(XS)))
** Step 13.b:3: PredecessorEstimation WORST_CASE(?,O(1))
+ Considered Problem:
- Strict DPs:
U41#(tt(),N,XS) -> c_7(U42#(tt(),activate(N),activate(XS)))
- Weak DPs:
U11#(tt(),N,XS) -> c_1(U12#(tt(),activate(N),activate(XS)))
U12#(tt(),N,XS) -> c_2(splitAt#(activate(N),activate(XS)))
U42#(tt(),N,XS) -> c_8(afterNth#(activate(N),activate(XS)))
U61#(tt(),N,X,XS) -> c_11(U62#(tt(),activate(N),activate(X),activate(XS)))
U62#(tt(),N,X,XS) -> c_12(U63#(tt(),activate(N),activate(X),activate(XS)))
U63#(tt(),N,X,XS) -> c_13(splitAt#(activate(N),activate(XS)))
U81#(tt(),N,XS) -> c_17(U82#(tt(),activate(N),activate(XS)))
U82#(tt(),N,XS) -> c_18(splitAt#(activate(N),activate(XS)))
afterNth#(N,XS) -> c_21(U11#(tt(),N,XS))
splitAt#(s(N),cons(X,XS)) -> c_29(U61#(tt(),N,X,activate(XS)))
- Weak TRS:
activate(X) -> X
activate(n__natsFrom(X)) -> natsFrom(X)
natsFrom(N) -> cons(N,n__natsFrom(s(N)))
natsFrom(X) -> n__natsFrom(X)
- Signature:
{U11/3,U12/3,U21/2,U22/2,U31/2,U32/2,U41/3,U42/3,U51/2,U52/2,U61/4,U62/4,U63/4,U64/2,U71/2,U72/2,U81/3,U82/3
,activate/1,afterNth/2,fst/1,head/1,natsFrom/1,sel/2,snd/1,splitAt/2,tail/1,take/2,U11#/3,U12#/3,U21#/2
,U22#/2,U31#/2,U32#/2,U41#/3,U42#/3,U51#/2,U52#/2,U61#/4,U62#/4,U63#/4,U64#/2,U71#/2,U72#/2,U81#/3,U82#/3
,activate#/1,afterNth#/2,fst#/1,head#/1,natsFrom#/1,sel#/2,snd#/1,splitAt#/2,tail#/1,take#/2} / {0/0,cons/2
,n__natsFrom/1,nil/0,pair/2,s/1,tt/0,c_1/1,c_2/1,c_3/2,c_4/1,c_5/2,c_6/1,c_7/1,c_8/1,c_9/2,c_10/1,c_11/1
,c_12/1,c_13/1,c_14/1,c_15/2,c_16/1,c_17/1,c_18/1,c_19/0,c_20/1,c_21/1,c_22/1,c_23/1,c_24/0,c_25/0,c_26/1
,c_27/1,c_28/0,c_29/1,c_30/2,c_31/1}
- Obligation:
innermost runtime complexity wrt. defined symbols {U11#,U12#,U21#,U22#,U31#,U32#,U41#,U42#,U51#,U52#,U61#
,U62#,U63#,U64#,U71#,U72#,U81#,U82#,activate#,afterNth#,fst#,head#,natsFrom#,sel#,snd#,splitAt#,tail#
,take#} and constructors {0,cons,n__natsFrom,nil,pair,s,tt}
+ Applied Processor:
PredecessorEstimation {onSelection = all simple predecessor estimation selector}
+ Details:
We estimate the number of application of
{1}
by application of
Pre({1}) = {}.
Here rules are labelled as follows:
1: U41#(tt(),N,XS) -> c_7(U42#(tt(),activate(N),activate(XS)))
2: U11#(tt(),N,XS) -> c_1(U12#(tt(),activate(N),activate(XS)))
3: U12#(tt(),N,XS) -> c_2(splitAt#(activate(N),activate(XS)))
4: U42#(tt(),N,XS) -> c_8(afterNth#(activate(N),activate(XS)))
5: U61#(tt(),N,X,XS) -> c_11(U62#(tt(),activate(N),activate(X),activate(XS)))
6: U62#(tt(),N,X,XS) -> c_12(U63#(tt(),activate(N),activate(X),activate(XS)))
7: U63#(tt(),N,X,XS) -> c_13(splitAt#(activate(N),activate(XS)))
8: U81#(tt(),N,XS) -> c_17(U82#(tt(),activate(N),activate(XS)))
9: U82#(tt(),N,XS) -> c_18(splitAt#(activate(N),activate(XS)))
10: afterNth#(N,XS) -> c_21(U11#(tt(),N,XS))
11: splitAt#(s(N),cons(X,XS)) -> c_29(U61#(tt(),N,X,activate(XS)))
** Step 13.b:4: RemoveWeakSuffixes WORST_CASE(?,O(1))
+ Considered Problem:
- Weak DPs:
U11#(tt(),N,XS) -> c_1(U12#(tt(),activate(N),activate(XS)))
U12#(tt(),N,XS) -> c_2(splitAt#(activate(N),activate(XS)))
U41#(tt(),N,XS) -> c_7(U42#(tt(),activate(N),activate(XS)))
U42#(tt(),N,XS) -> c_8(afterNth#(activate(N),activate(XS)))
U61#(tt(),N,X,XS) -> c_11(U62#(tt(),activate(N),activate(X),activate(XS)))
U62#(tt(),N,X,XS) -> c_12(U63#(tt(),activate(N),activate(X),activate(XS)))
U63#(tt(),N,X,XS) -> c_13(splitAt#(activate(N),activate(XS)))
U81#(tt(),N,XS) -> c_17(U82#(tt(),activate(N),activate(XS)))
U82#(tt(),N,XS) -> c_18(splitAt#(activate(N),activate(XS)))
afterNth#(N,XS) -> c_21(U11#(tt(),N,XS))
splitAt#(s(N),cons(X,XS)) -> c_29(U61#(tt(),N,X,activate(XS)))
- Weak TRS:
activate(X) -> X
activate(n__natsFrom(X)) -> natsFrom(X)
natsFrom(N) -> cons(N,n__natsFrom(s(N)))
natsFrom(X) -> n__natsFrom(X)
- Signature:
{U11/3,U12/3,U21/2,U22/2,U31/2,U32/2,U41/3,U42/3,U51/2,U52/2,U61/4,U62/4,U63/4,U64/2,U71/2,U72/2,U81/3,U82/3
,activate/1,afterNth/2,fst/1,head/1,natsFrom/1,sel/2,snd/1,splitAt/2,tail/1,take/2,U11#/3,U12#/3,U21#/2
,U22#/2,U31#/2,U32#/2,U41#/3,U42#/3,U51#/2,U52#/2,U61#/4,U62#/4,U63#/4,U64#/2,U71#/2,U72#/2,U81#/3,U82#/3
,activate#/1,afterNth#/2,fst#/1,head#/1,natsFrom#/1,sel#/2,snd#/1,splitAt#/2,tail#/1,take#/2} / {0/0,cons/2
,n__natsFrom/1,nil/0,pair/2,s/1,tt/0,c_1/1,c_2/1,c_3/2,c_4/1,c_5/2,c_6/1,c_7/1,c_8/1,c_9/2,c_10/1,c_11/1
,c_12/1,c_13/1,c_14/1,c_15/2,c_16/1,c_17/1,c_18/1,c_19/0,c_20/1,c_21/1,c_22/1,c_23/1,c_24/0,c_25/0,c_26/1
,c_27/1,c_28/0,c_29/1,c_30/2,c_31/1}
- Obligation:
innermost runtime complexity wrt. defined symbols {U11#,U12#,U21#,U22#,U31#,U32#,U41#,U42#,U51#,U52#,U61#
,U62#,U63#,U64#,U71#,U72#,U81#,U82#,activate#,afterNth#,fst#,head#,natsFrom#,sel#,snd#,splitAt#,tail#
,take#} and constructors {0,cons,n__natsFrom,nil,pair,s,tt}
+ Applied Processor:
RemoveWeakSuffixes
+ Details:
Consider the dependency graph
1:W:U11#(tt(),N,XS) -> c_1(U12#(tt(),activate(N),activate(XS)))
-->_1 U12#(tt(),N,XS) -> c_2(splitAt#(activate(N),activate(XS))):2
2:W:U12#(tt(),N,XS) -> c_2(splitAt#(activate(N),activate(XS)))
-->_1 splitAt#(s(N),cons(X,XS)) -> c_29(U61#(tt(),N,X,activate(XS))):11
3:W:U41#(tt(),N,XS) -> c_7(U42#(tt(),activate(N),activate(XS)))
-->_1 U42#(tt(),N,XS) -> c_8(afterNth#(activate(N),activate(XS))):4
4:W:U42#(tt(),N,XS) -> c_8(afterNth#(activate(N),activate(XS)))
-->_1 afterNth#(N,XS) -> c_21(U11#(tt(),N,XS)):10
5:W:U61#(tt(),N,X,XS) -> c_11(U62#(tt(),activate(N),activate(X),activate(XS)))
-->_1 U62#(tt(),N,X,XS) -> c_12(U63#(tt(),activate(N),activate(X),activate(XS))):6
6:W:U62#(tt(),N,X,XS) -> c_12(U63#(tt(),activate(N),activate(X),activate(XS)))
-->_1 U63#(tt(),N,X,XS) -> c_13(splitAt#(activate(N),activate(XS))):7
7:W:U63#(tt(),N,X,XS) -> c_13(splitAt#(activate(N),activate(XS)))
-->_1 splitAt#(s(N),cons(X,XS)) -> c_29(U61#(tt(),N,X,activate(XS))):11
8:W:U81#(tt(),N,XS) -> c_17(U82#(tt(),activate(N),activate(XS)))
-->_1 U82#(tt(),N,XS) -> c_18(splitAt#(activate(N),activate(XS))):9
9:W:U82#(tt(),N,XS) -> c_18(splitAt#(activate(N),activate(XS)))
-->_1 splitAt#(s(N),cons(X,XS)) -> c_29(U61#(tt(),N,X,activate(XS))):11
10:W:afterNth#(N,XS) -> c_21(U11#(tt(),N,XS))
-->_1 U11#(tt(),N,XS) -> c_1(U12#(tt(),activate(N),activate(XS))):1
11:W:splitAt#(s(N),cons(X,XS)) -> c_29(U61#(tt(),N,X,activate(XS)))
-->_1 U61#(tt(),N,X,XS) -> c_11(U62#(tt(),activate(N),activate(X),activate(XS))):5
The following weak DPs constitute a sub-graph of the DG that is closed under successors. The DPs are removed.
8: U81#(tt(),N,XS) -> c_17(U82#(tt(),activate(N),activate(XS)))
9: U82#(tt(),N,XS) -> c_18(splitAt#(activate(N),activate(XS)))
3: U41#(tt(),N,XS) -> c_7(U42#(tt(),activate(N),activate(XS)))
4: U42#(tt(),N,XS) -> c_8(afterNth#(activate(N),activate(XS)))
10: afterNth#(N,XS) -> c_21(U11#(tt(),N,XS))
1: U11#(tt(),N,XS) -> c_1(U12#(tt(),activate(N),activate(XS)))
2: U12#(tt(),N,XS) -> c_2(splitAt#(activate(N),activate(XS)))
11: splitAt#(s(N),cons(X,XS)) -> c_29(U61#(tt(),N,X,activate(XS)))
7: U63#(tt(),N,X,XS) -> c_13(splitAt#(activate(N),activate(XS)))
6: U62#(tt(),N,X,XS) -> c_12(U63#(tt(),activate(N),activate(X),activate(XS)))
5: U61#(tt(),N,X,XS) -> c_11(U62#(tt(),activate(N),activate(X),activate(XS)))
** Step 13.b:5: EmptyProcessor WORST_CASE(?,O(1))
+ Considered Problem:
- Weak TRS:
activate(X) -> X
activate(n__natsFrom(X)) -> natsFrom(X)
natsFrom(N) -> cons(N,n__natsFrom(s(N)))
natsFrom(X) -> n__natsFrom(X)
- Signature:
{U11/3,U12/3,U21/2,U22/2,U31/2,U32/2,U41/3,U42/3,U51/2,U52/2,U61/4,U62/4,U63/4,U64/2,U71/2,U72/2,U81/3,U82/3
,activate/1,afterNth/2,fst/1,head/1,natsFrom/1,sel/2,snd/1,splitAt/2,tail/1,take/2,U11#/3,U12#/3,U21#/2
,U22#/2,U31#/2,U32#/2,U41#/3,U42#/3,U51#/2,U52#/2,U61#/4,U62#/4,U63#/4,U64#/2,U71#/2,U72#/2,U81#/3,U82#/3
,activate#/1,afterNth#/2,fst#/1,head#/1,natsFrom#/1,sel#/2,snd#/1,splitAt#/2,tail#/1,take#/2} / {0/0,cons/2
,n__natsFrom/1,nil/0,pair/2,s/1,tt/0,c_1/1,c_2/1,c_3/2,c_4/1,c_5/2,c_6/1,c_7/1,c_8/1,c_9/2,c_10/1,c_11/1
,c_12/1,c_13/1,c_14/1,c_15/2,c_16/1,c_17/1,c_18/1,c_19/0,c_20/1,c_21/1,c_22/1,c_23/1,c_24/0,c_25/0,c_26/1
,c_27/1,c_28/0,c_29/1,c_30/2,c_31/1}
- Obligation:
innermost runtime complexity wrt. defined symbols {U11#,U12#,U21#,U22#,U31#,U32#,U41#,U42#,U51#,U52#,U61#
,U62#,U63#,U64#,U71#,U72#,U81#,U82#,activate#,afterNth#,fst#,head#,natsFrom#,sel#,snd#,splitAt#,tail#
,take#} and constructors {0,cons,n__natsFrom,nil,pair,s,tt}
+ Applied Processor:
EmptyProcessor
+ Details:
The problem is already closed. The intended complexity is O(1).
WORST_CASE(?,O(n^1))