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