304.02/291.57 WORST_CASE(Omega(n^1), ?) 304.02/291.58 proof of /export/starexec/sandbox/benchmark/theBenchmark.xml 304.02/291.58 # AProVE Commit ID: 48fb2092695e11cc9f56e44b17a92a5f88ffb256 marcel 20180622 unpublished dirty 304.02/291.58 304.02/291.58 304.02/291.58 The Runtime Complexity (full) of the given CpxTRS could be proven to be BOUNDS(n^1, INF). 304.02/291.58 304.02/291.58 (0) CpxTRS 304.02/291.58 (1) RelTrsToDecreasingLoopProblemProof [LOWER BOUND(ID), 0 ms] 304.02/291.58 (2) TRS for Loop Detection 304.02/291.58 (3) DecreasingLoopProof [LOWER BOUND(ID), 59.3 s] 304.02/291.58 (4) BEST 304.02/291.58 (5) proven lower bound 304.02/291.58 (6) LowerBoundPropagationProof [FINISHED, 0 ms] 304.02/291.58 (7) BOUNDS(n^1, INF) 304.02/291.58 (8) TRS for Loop Detection 304.02/291.58 304.02/291.58 304.02/291.58 ---------------------------------------- 304.02/291.58 304.02/291.58 (0) 304.02/291.58 Obligation: 304.02/291.58 The Runtime Complexity (full) of the given CpxTRS could be proven to be BOUNDS(n^1, INF). 304.02/291.58 304.02/291.58 304.02/291.58 The TRS R consists of the following rules: 304.02/291.58 304.02/291.58 U11(tt, N, XS) -> U12(tt, activate(N), activate(XS)) 304.02/291.58 U12(tt, N, XS) -> snd(splitAt(activate(N), activate(XS))) 304.02/291.58 U21(tt, X) -> U22(tt, activate(X)) 304.02/291.58 U22(tt, X) -> activate(X) 304.02/291.58 U31(tt, N) -> U32(tt, activate(N)) 304.02/291.58 U32(tt, N) -> activate(N) 304.02/291.58 U41(tt, N, XS) -> U42(tt, activate(N), activate(XS)) 304.02/291.58 U42(tt, N, XS) -> head(afterNth(activate(N), activate(XS))) 304.02/291.58 U51(tt, Y) -> U52(tt, activate(Y)) 304.02/291.58 U52(tt, Y) -> activate(Y) 304.02/291.58 U61(tt, N, X, XS) -> U62(tt, activate(N), activate(X), activate(XS)) 304.02/291.58 U62(tt, N, X, XS) -> U63(tt, activate(N), activate(X), activate(XS)) 304.02/291.58 U63(tt, N, X, XS) -> U64(splitAt(activate(N), activate(XS)), activate(X)) 304.02/291.58 U64(pair(YS, ZS), X) -> pair(cons(activate(X), YS), ZS) 304.02/291.58 U71(tt, XS) -> U72(tt, activate(XS)) 304.02/291.58 U72(tt, XS) -> activate(XS) 304.02/291.58 U81(tt, N, XS) -> U82(tt, activate(N), activate(XS)) 304.02/291.58 U82(tt, N, XS) -> fst(splitAt(activate(N), activate(XS))) 304.02/291.58 afterNth(N, XS) -> U11(tt, N, XS) 304.02/291.58 fst(pair(X, Y)) -> U21(tt, X) 304.02/291.58 head(cons(N, XS)) -> U31(tt, N) 304.02/291.58 natsFrom(N) -> cons(N, n__natsFrom(s(N))) 304.02/291.58 sel(N, XS) -> U41(tt, N, XS) 304.02/291.58 snd(pair(X, Y)) -> U51(tt, Y) 304.02/291.58 splitAt(0, XS) -> pair(nil, XS) 304.02/291.58 splitAt(s(N), cons(X, XS)) -> U61(tt, N, X, activate(XS)) 304.02/291.58 tail(cons(N, XS)) -> U71(tt, activate(XS)) 304.02/291.58 take(N, XS) -> U81(tt, N, XS) 304.02/291.58 natsFrom(X) -> n__natsFrom(X) 304.02/291.58 activate(n__natsFrom(X)) -> natsFrom(X) 304.02/291.58 activate(X) -> X 304.02/291.58 304.02/291.58 S is empty. 304.02/291.58 Rewrite Strategy: FULL 304.02/291.58 ---------------------------------------- 304.02/291.58 304.02/291.58 (1) RelTrsToDecreasingLoopProblemProof (LOWER BOUND(ID)) 304.02/291.58 Transformed a relative TRS into a decreasing-loop problem. 304.02/291.58 ---------------------------------------- 304.02/291.58 304.02/291.58 (2) 304.02/291.58 Obligation: 304.02/291.58 Analyzing the following TRS for decreasing loops: 304.02/291.58 304.02/291.58 The Runtime Complexity (full) of the given CpxTRS could be proven to be BOUNDS(n^1, INF). 304.02/291.58 304.02/291.58 304.02/291.58 The TRS R consists of the following rules: 304.02/291.58 304.02/291.58 U11(tt, N, XS) -> U12(tt, activate(N), activate(XS)) 304.02/291.58 U12(tt, N, XS) -> snd(splitAt(activate(N), activate(XS))) 304.02/291.58 U21(tt, X) -> U22(tt, activate(X)) 304.02/291.58 U22(tt, X) -> activate(X) 304.02/291.58 U31(tt, N) -> U32(tt, activate(N)) 304.02/291.58 U32(tt, N) -> activate(N) 304.02/291.58 U41(tt, N, XS) -> U42(tt, activate(N), activate(XS)) 304.02/291.58 U42(tt, N, XS) -> head(afterNth(activate(N), activate(XS))) 304.02/291.58 U51(tt, Y) -> U52(tt, activate(Y)) 304.02/291.58 U52(tt, Y) -> activate(Y) 304.02/291.58 U61(tt, N, X, XS) -> U62(tt, activate(N), activate(X), activate(XS)) 304.02/291.58 U62(tt, N, X, XS) -> U63(tt, activate(N), activate(X), activate(XS)) 304.02/291.58 U63(tt, N, X, XS) -> U64(splitAt(activate(N), activate(XS)), activate(X)) 304.02/291.58 U64(pair(YS, ZS), X) -> pair(cons(activate(X), YS), ZS) 304.02/291.58 U71(tt, XS) -> U72(tt, activate(XS)) 304.02/291.58 U72(tt, XS) -> activate(XS) 304.02/291.58 U81(tt, N, XS) -> U82(tt, activate(N), activate(XS)) 304.02/291.58 U82(tt, N, XS) -> fst(splitAt(activate(N), activate(XS))) 304.02/291.58 afterNth(N, XS) -> U11(tt, N, XS) 304.02/291.58 fst(pair(X, Y)) -> U21(tt, X) 304.02/291.58 head(cons(N, XS)) -> U31(tt, N) 304.02/291.58 natsFrom(N) -> cons(N, n__natsFrom(s(N))) 304.02/291.58 sel(N, XS) -> U41(tt, N, XS) 304.02/291.58 snd(pair(X, Y)) -> U51(tt, Y) 304.02/291.58 splitAt(0, XS) -> pair(nil, XS) 304.02/291.58 splitAt(s(N), cons(X, XS)) -> U61(tt, N, X, activate(XS)) 304.02/291.58 tail(cons(N, XS)) -> U71(tt, activate(XS)) 304.02/291.58 take(N, XS) -> U81(tt, N, XS) 304.02/291.58 natsFrom(X) -> n__natsFrom(X) 304.02/291.58 activate(n__natsFrom(X)) -> natsFrom(X) 304.02/291.58 activate(X) -> X 304.02/291.58 304.02/291.58 S is empty. 304.02/291.58 Rewrite Strategy: FULL 304.02/291.58 ---------------------------------------- 304.02/291.58 304.02/291.58 (3) DecreasingLoopProof (LOWER BOUND(ID)) 304.02/291.58 The following loop(s) give(s) rise to the lower bound Omega(n^1): 304.02/291.58 304.02/291.58 The rewrite sequence 304.02/291.58 304.02/291.58 U63(tt, s(N1_0), X, cons(X2_0, XS3_0)) ->^+ U64(U63(tt, N1_0, activate(activate(X2_0)), XS3_0), activate(X)) 304.02/291.58 304.02/291.58 gives rise to a decreasing loop by considering the right hand sides subterm at position [0]. 304.02/291.58 304.02/291.58 The pumping substitution is [N1_0 / s(N1_0), XS3_0 / cons(X2_0, XS3_0)]. 304.02/291.58 304.02/291.58 The result substitution is [X / activate(activate(X2_0))]. 304.02/291.58 304.02/291.58 304.02/291.58 304.02/291.58 304.02/291.58 ---------------------------------------- 304.02/291.58 304.02/291.58 (4) 304.02/291.58 Complex Obligation (BEST) 304.02/291.58 304.02/291.58 ---------------------------------------- 304.02/291.58 304.02/291.58 (5) 304.02/291.58 Obligation: 304.02/291.58 Proved the lower bound n^1 for the following obligation: 304.02/291.58 304.02/291.58 The Runtime Complexity (full) of the given CpxTRS could be proven to be BOUNDS(n^1, INF). 304.02/291.58 304.02/291.58 304.02/291.58 The TRS R consists of the following rules: 304.02/291.58 304.02/291.58 U11(tt, N, XS) -> U12(tt, activate(N), activate(XS)) 304.02/291.58 U12(tt, N, XS) -> snd(splitAt(activate(N), activate(XS))) 304.02/291.58 U21(tt, X) -> U22(tt, activate(X)) 304.02/291.58 U22(tt, X) -> activate(X) 304.02/291.58 U31(tt, N) -> U32(tt, activate(N)) 304.02/291.58 U32(tt, N) -> activate(N) 304.02/291.58 U41(tt, N, XS) -> U42(tt, activate(N), activate(XS)) 304.02/291.58 U42(tt, N, XS) -> head(afterNth(activate(N), activate(XS))) 304.02/291.58 U51(tt, Y) -> U52(tt, activate(Y)) 304.02/291.58 U52(tt, Y) -> activate(Y) 304.02/291.58 U61(tt, N, X, XS) -> U62(tt, activate(N), activate(X), activate(XS)) 304.02/291.58 U62(tt, N, X, XS) -> U63(tt, activate(N), activate(X), activate(XS)) 304.02/291.58 U63(tt, N, X, XS) -> U64(splitAt(activate(N), activate(XS)), activate(X)) 304.02/291.58 U64(pair(YS, ZS), X) -> pair(cons(activate(X), YS), ZS) 304.02/291.58 U71(tt, XS) -> U72(tt, activate(XS)) 304.02/291.58 U72(tt, XS) -> activate(XS) 304.02/291.58 U81(tt, N, XS) -> U82(tt, activate(N), activate(XS)) 304.02/291.58 U82(tt, N, XS) -> fst(splitAt(activate(N), activate(XS))) 304.02/291.58 afterNth(N, XS) -> U11(tt, N, XS) 304.02/291.58 fst(pair(X, Y)) -> U21(tt, X) 304.02/291.58 head(cons(N, XS)) -> U31(tt, N) 304.02/291.58 natsFrom(N) -> cons(N, n__natsFrom(s(N))) 304.02/291.58 sel(N, XS) -> U41(tt, N, XS) 304.02/291.58 snd(pair(X, Y)) -> U51(tt, Y) 304.02/291.58 splitAt(0, XS) -> pair(nil, XS) 304.02/291.58 splitAt(s(N), cons(X, XS)) -> U61(tt, N, X, activate(XS)) 304.02/291.58 tail(cons(N, XS)) -> U71(tt, activate(XS)) 304.02/291.58 take(N, XS) -> U81(tt, N, XS) 304.02/291.58 natsFrom(X) -> n__natsFrom(X) 304.02/291.58 activate(n__natsFrom(X)) -> natsFrom(X) 304.02/291.58 activate(X) -> X 304.02/291.58 304.02/291.58 S is empty. 304.02/291.58 Rewrite Strategy: FULL 304.02/291.58 ---------------------------------------- 304.02/291.58 304.02/291.58 (6) LowerBoundPropagationProof (FINISHED) 304.02/291.58 Propagated lower bound. 304.02/291.58 ---------------------------------------- 304.02/291.58 304.02/291.58 (7) 304.02/291.58 BOUNDS(n^1, INF) 304.02/291.58 304.02/291.58 ---------------------------------------- 304.02/291.58 304.02/291.58 (8) 304.02/291.58 Obligation: 304.02/291.58 Analyzing the following TRS for decreasing loops: 304.02/291.58 304.02/291.58 The Runtime Complexity (full) of the given CpxTRS could be proven to be BOUNDS(n^1, INF). 304.02/291.58 304.02/291.58 304.02/291.58 The TRS R consists of the following rules: 304.02/291.58 304.02/291.58 U11(tt, N, XS) -> U12(tt, activate(N), activate(XS)) 304.02/291.58 U12(tt, N, XS) -> snd(splitAt(activate(N), activate(XS))) 304.02/291.58 U21(tt, X) -> U22(tt, activate(X)) 304.02/291.58 U22(tt, X) -> activate(X) 304.02/291.58 U31(tt, N) -> U32(tt, activate(N)) 304.02/291.58 U32(tt, N) -> activate(N) 304.02/291.58 U41(tt, N, XS) -> U42(tt, activate(N), activate(XS)) 304.02/291.58 U42(tt, N, XS) -> head(afterNth(activate(N), activate(XS))) 304.02/291.58 U51(tt, Y) -> U52(tt, activate(Y)) 304.02/291.58 U52(tt, Y) -> activate(Y) 304.02/291.58 U61(tt, N, X, XS) -> U62(tt, activate(N), activate(X), activate(XS)) 304.02/291.58 U62(tt, N, X, XS) -> U63(tt, activate(N), activate(X), activate(XS)) 304.02/291.58 U63(tt, N, X, XS) -> U64(splitAt(activate(N), activate(XS)), activate(X)) 304.02/291.58 U64(pair(YS, ZS), X) -> pair(cons(activate(X), YS), ZS) 304.02/291.58 U71(tt, XS) -> U72(tt, activate(XS)) 304.02/291.58 U72(tt, XS) -> activate(XS) 304.02/291.58 U81(tt, N, XS) -> U82(tt, activate(N), activate(XS)) 304.02/291.58 U82(tt, N, XS) -> fst(splitAt(activate(N), activate(XS))) 304.02/291.58 afterNth(N, XS) -> U11(tt, N, XS) 304.02/291.58 fst(pair(X, Y)) -> U21(tt, X) 304.02/291.58 head(cons(N, XS)) -> U31(tt, N) 304.02/291.58 natsFrom(N) -> cons(N, n__natsFrom(s(N))) 304.02/291.58 sel(N, XS) -> U41(tt, N, XS) 304.02/291.58 snd(pair(X, Y)) -> U51(tt, Y) 304.02/291.58 splitAt(0, XS) -> pair(nil, XS) 304.02/291.58 splitAt(s(N), cons(X, XS)) -> U61(tt, N, X, activate(XS)) 304.02/291.58 tail(cons(N, XS)) -> U71(tt, activate(XS)) 304.02/291.58 take(N, XS) -> U81(tt, N, XS) 304.02/291.58 natsFrom(X) -> n__natsFrom(X) 304.02/291.58 activate(n__natsFrom(X)) -> natsFrom(X) 304.02/291.58 activate(X) -> X 304.02/291.58 304.02/291.58 S is empty. 304.02/291.58 Rewrite Strategy: FULL 304.08/291.62 EOF