1116.16/291.52 WORST_CASE(Omega(n^1), ?) 1116.16/291.53 proof of /export/starexec/sandbox/benchmark/theBenchmark.xml 1116.16/291.53 # AProVE Commit ID: 48fb2092695e11cc9f56e44b17a92a5f88ffb256 marcel 20180622 unpublished dirty 1116.16/291.53 1116.16/291.53 1116.16/291.53 The Runtime Complexity (innermost) of the given CpxTRS could be proven to be BOUNDS(n^1, INF). 1116.16/291.53 1116.16/291.53 (0) CpxTRS 1116.16/291.53 (1) RelTrsToDecreasingLoopProblemProof [LOWER BOUND(ID), 0 ms] 1116.16/291.53 (2) TRS for Loop Detection 1116.16/291.53 (3) DecreasingLoopProof [LOWER BOUND(ID), 0 ms] 1116.16/291.53 (4) BEST 1116.16/291.53 (5) proven lower bound 1116.16/291.53 (6) LowerBoundPropagationProof [FINISHED, 0 ms] 1116.16/291.53 (7) BOUNDS(n^1, INF) 1116.16/291.53 (8) TRS for Loop Detection 1116.16/291.53 1116.16/291.53 1116.16/291.53 ---------------------------------------- 1116.16/291.53 1116.16/291.53 (0) 1116.16/291.53 Obligation: 1116.16/291.53 The Runtime Complexity (innermost) of the given CpxTRS could be proven to be BOUNDS(n^1, INF). 1116.16/291.53 1116.16/291.53 1116.16/291.53 The TRS R consists of the following rules: 1116.16/291.53 1116.16/291.53 fibs_2#1(zipwith_l, plus, tail_l, x3) -> ConsL(S(0), zipwith_l#3(fibs, fibs_2(zipwith_l, plus, tail_l))) 1116.16/291.53 cond_take_l_n_xs(ConsL(x16, x18), 0) -> Nil 1116.16/291.53 cond_take_l_n_xs(ConsL(x7, fibs_2(x4, x8, x12)), S(x16)) -> Cons(x7, cond_take_l_n_xs(fibs_2#1(x4, x8, x12, bot[0]), x16)) 1116.16/291.53 cond_take_l_n_xs(ConsL(x7, zipwith_l_f_xs_ys(x4, x8, x12)), S(x16)) -> Cons(x7, cond_take_l_n_xs(zipwith_l_f_xs_ys#1(x4, x8, x12, bot[0]), x16)) 1116.16/291.53 plus#2(0, x12) -> x12 1116.16/291.53 plus#2(S(x4), x2) -> S(plus#2(x4, x2)) 1116.16/291.53 cond_zipwith_l_f_xs_ys_1(ConsL(x4, x3), x2, x1) -> ConsL(plus#2(x2, x4), zipwith_l#3(x1, x3)) 1116.16/291.53 cond_zipwith_l_f_xs_ys(ConsL(x5, x4), zipwith_l_f_xs_ys(x1, x2, x3)) -> cond_zipwith_l_f_xs_ys_1(zipwith_l_f_xs_ys#1(x1, x2, x3, bot[6]), x5, x4) 1116.16/291.53 cond_zipwith_l_f_xs_ys(ConsL(x5, x4), fibs_2(x1, x2, x3)) -> cond_zipwith_l_f_xs_ys_1(fibs_2#1(x1, x2, x3, bot[6]), x5, x4) 1116.16/291.53 zipwith_l_f_xs_ys#1(plus, fibs, x5, x3) -> cond_zipwith_l_f_xs_ys(ConsL(0, fibs_2(zipwith_l, plus, tail_l)), x5) 1116.16/291.53 zipwith_l_f_xs_ys#1(plus, fibs_2(x3, x4, x5), x2, x1) -> cond_zipwith_l_f_xs_ys(fibs_2#1(x3, x4, x5, bot[7]), x2) 1116.16/291.53 zipwith_l_f_xs_ys#1(plus, zipwith_l_f_xs_ys(x3, x4, x5), x2, x1) -> cond_zipwith_l_f_xs_ys(zipwith_l_f_xs_ys#1(x3, x4, x5, bot[7]), x2) 1116.16/291.53 zipwith_l#3(x8, x4) -> zipwith_l_f_xs_ys(plus, x8, x4) 1116.16/291.53 main(x12) -> cond_take_l_n_xs(ConsL(0, fibs_2(zipwith_l, plus, tail_l)), x12) 1116.16/291.53 1116.16/291.53 S is empty. 1116.16/291.53 Rewrite Strategy: INNERMOST 1116.16/291.53 ---------------------------------------- 1116.16/291.53 1116.16/291.53 (1) RelTrsToDecreasingLoopProblemProof (LOWER BOUND(ID)) 1116.16/291.53 Transformed a relative TRS into a decreasing-loop problem. 1116.16/291.53 ---------------------------------------- 1116.16/291.53 1116.16/291.53 (2) 1116.16/291.53 Obligation: 1116.16/291.53 Analyzing the following TRS for decreasing loops: 1116.16/291.53 1116.16/291.53 The Runtime Complexity (innermost) of the given CpxTRS could be proven to be BOUNDS(n^1, INF). 1116.16/291.53 1116.16/291.53 1116.16/291.53 The TRS R consists of the following rules: 1116.16/291.53 1116.16/291.53 fibs_2#1(zipwith_l, plus, tail_l, x3) -> ConsL(S(0), zipwith_l#3(fibs, fibs_2(zipwith_l, plus, tail_l))) 1116.16/291.53 cond_take_l_n_xs(ConsL(x16, x18), 0) -> Nil 1116.16/291.53 cond_take_l_n_xs(ConsL(x7, fibs_2(x4, x8, x12)), S(x16)) -> Cons(x7, cond_take_l_n_xs(fibs_2#1(x4, x8, x12, bot[0]), x16)) 1116.16/291.53 cond_take_l_n_xs(ConsL(x7, zipwith_l_f_xs_ys(x4, x8, x12)), S(x16)) -> Cons(x7, cond_take_l_n_xs(zipwith_l_f_xs_ys#1(x4, x8, x12, bot[0]), x16)) 1116.16/291.53 plus#2(0, x12) -> x12 1116.16/291.53 plus#2(S(x4), x2) -> S(plus#2(x4, x2)) 1116.16/291.53 cond_zipwith_l_f_xs_ys_1(ConsL(x4, x3), x2, x1) -> ConsL(plus#2(x2, x4), zipwith_l#3(x1, x3)) 1116.16/291.53 cond_zipwith_l_f_xs_ys(ConsL(x5, x4), zipwith_l_f_xs_ys(x1, x2, x3)) -> cond_zipwith_l_f_xs_ys_1(zipwith_l_f_xs_ys#1(x1, x2, x3, bot[6]), x5, x4) 1116.16/291.53 cond_zipwith_l_f_xs_ys(ConsL(x5, x4), fibs_2(x1, x2, x3)) -> cond_zipwith_l_f_xs_ys_1(fibs_2#1(x1, x2, x3, bot[6]), x5, x4) 1116.16/291.53 zipwith_l_f_xs_ys#1(plus, fibs, x5, x3) -> cond_zipwith_l_f_xs_ys(ConsL(0, fibs_2(zipwith_l, plus, tail_l)), x5) 1116.16/291.53 zipwith_l_f_xs_ys#1(plus, fibs_2(x3, x4, x5), x2, x1) -> cond_zipwith_l_f_xs_ys(fibs_2#1(x3, x4, x5, bot[7]), x2) 1116.16/291.53 zipwith_l_f_xs_ys#1(plus, zipwith_l_f_xs_ys(x3, x4, x5), x2, x1) -> cond_zipwith_l_f_xs_ys(zipwith_l_f_xs_ys#1(x3, x4, x5, bot[7]), x2) 1116.16/291.53 zipwith_l#3(x8, x4) -> zipwith_l_f_xs_ys(plus, x8, x4) 1116.16/291.53 main(x12) -> cond_take_l_n_xs(ConsL(0, fibs_2(zipwith_l, plus, tail_l)), x12) 1116.16/291.53 1116.16/291.53 S is empty. 1116.16/291.53 Rewrite Strategy: INNERMOST 1116.16/291.53 ---------------------------------------- 1116.16/291.53 1116.16/291.53 (3) DecreasingLoopProof (LOWER BOUND(ID)) 1116.16/291.53 The following loop(s) give(s) rise to the lower bound Omega(n^1): 1116.16/291.53 1116.16/291.53 The rewrite sequence 1116.16/291.53 1116.16/291.53 plus#2(S(x4), x2) ->^+ S(plus#2(x4, x2)) 1116.16/291.53 1116.16/291.53 gives rise to a decreasing loop by considering the right hand sides subterm at position [0]. 1116.16/291.53 1116.16/291.53 The pumping substitution is [x4 / S(x4)]. 1116.16/291.53 1116.16/291.53 The result substitution is [ ]. 1116.16/291.53 1116.16/291.53 1116.16/291.53 1116.16/291.53 1116.16/291.53 ---------------------------------------- 1116.16/291.53 1116.16/291.53 (4) 1116.16/291.53 Complex Obligation (BEST) 1116.16/291.53 1116.16/291.53 ---------------------------------------- 1116.16/291.53 1116.16/291.53 (5) 1116.16/291.53 Obligation: 1116.16/291.53 Proved the lower bound n^1 for the following obligation: 1116.16/291.53 1116.16/291.53 The Runtime Complexity (innermost) of the given CpxTRS could be proven to be BOUNDS(n^1, INF). 1116.16/291.53 1116.16/291.53 1116.16/291.53 The TRS R consists of the following rules: 1116.16/291.53 1116.16/291.53 fibs_2#1(zipwith_l, plus, tail_l, x3) -> ConsL(S(0), zipwith_l#3(fibs, fibs_2(zipwith_l, plus, tail_l))) 1116.16/291.53 cond_take_l_n_xs(ConsL(x16, x18), 0) -> Nil 1116.16/291.53 cond_take_l_n_xs(ConsL(x7, fibs_2(x4, x8, x12)), S(x16)) -> Cons(x7, cond_take_l_n_xs(fibs_2#1(x4, x8, x12, bot[0]), x16)) 1116.16/291.53 cond_take_l_n_xs(ConsL(x7, zipwith_l_f_xs_ys(x4, x8, x12)), S(x16)) -> Cons(x7, cond_take_l_n_xs(zipwith_l_f_xs_ys#1(x4, x8, x12, bot[0]), x16)) 1116.16/291.53 plus#2(0, x12) -> x12 1116.16/291.53 plus#2(S(x4), x2) -> S(plus#2(x4, x2)) 1116.16/291.53 cond_zipwith_l_f_xs_ys_1(ConsL(x4, x3), x2, x1) -> ConsL(plus#2(x2, x4), zipwith_l#3(x1, x3)) 1116.16/291.53 cond_zipwith_l_f_xs_ys(ConsL(x5, x4), zipwith_l_f_xs_ys(x1, x2, x3)) -> cond_zipwith_l_f_xs_ys_1(zipwith_l_f_xs_ys#1(x1, x2, x3, bot[6]), x5, x4) 1116.16/291.53 cond_zipwith_l_f_xs_ys(ConsL(x5, x4), fibs_2(x1, x2, x3)) -> cond_zipwith_l_f_xs_ys_1(fibs_2#1(x1, x2, x3, bot[6]), x5, x4) 1116.16/291.53 zipwith_l_f_xs_ys#1(plus, fibs, x5, x3) -> cond_zipwith_l_f_xs_ys(ConsL(0, fibs_2(zipwith_l, plus, tail_l)), x5) 1116.16/291.53 zipwith_l_f_xs_ys#1(plus, fibs_2(x3, x4, x5), x2, x1) -> cond_zipwith_l_f_xs_ys(fibs_2#1(x3, x4, x5, bot[7]), x2) 1116.16/291.53 zipwith_l_f_xs_ys#1(plus, zipwith_l_f_xs_ys(x3, x4, x5), x2, x1) -> cond_zipwith_l_f_xs_ys(zipwith_l_f_xs_ys#1(x3, x4, x5, bot[7]), x2) 1116.16/291.53 zipwith_l#3(x8, x4) -> zipwith_l_f_xs_ys(plus, x8, x4) 1116.16/291.53 main(x12) -> cond_take_l_n_xs(ConsL(0, fibs_2(zipwith_l, plus, tail_l)), x12) 1116.16/291.53 1116.16/291.53 S is empty. 1116.16/291.53 Rewrite Strategy: INNERMOST 1116.16/291.53 ---------------------------------------- 1116.16/291.53 1116.16/291.53 (6) LowerBoundPropagationProof (FINISHED) 1116.16/291.53 Propagated lower bound. 1116.16/291.53 ---------------------------------------- 1116.16/291.53 1116.16/291.53 (7) 1116.16/291.53 BOUNDS(n^1, INF) 1116.16/291.53 1116.16/291.53 ---------------------------------------- 1116.16/291.53 1116.16/291.53 (8) 1116.16/291.53 Obligation: 1116.16/291.53 Analyzing the following TRS for decreasing loops: 1116.16/291.53 1116.16/291.53 The Runtime Complexity (innermost) of the given CpxTRS could be proven to be BOUNDS(n^1, INF). 1116.16/291.53 1116.16/291.53 1116.16/291.53 The TRS R consists of the following rules: 1116.16/291.53 1116.16/291.53 fibs_2#1(zipwith_l, plus, tail_l, x3) -> ConsL(S(0), zipwith_l#3(fibs, fibs_2(zipwith_l, plus, tail_l))) 1116.16/291.53 cond_take_l_n_xs(ConsL(x16, x18), 0) -> Nil 1116.16/291.53 cond_take_l_n_xs(ConsL(x7, fibs_2(x4, x8, x12)), S(x16)) -> Cons(x7, cond_take_l_n_xs(fibs_2#1(x4, x8, x12, bot[0]), x16)) 1116.16/291.53 cond_take_l_n_xs(ConsL(x7, zipwith_l_f_xs_ys(x4, x8, x12)), S(x16)) -> Cons(x7, cond_take_l_n_xs(zipwith_l_f_xs_ys#1(x4, x8, x12, bot[0]), x16)) 1116.16/291.53 plus#2(0, x12) -> x12 1116.16/291.53 plus#2(S(x4), x2) -> S(plus#2(x4, x2)) 1116.16/291.53 cond_zipwith_l_f_xs_ys_1(ConsL(x4, x3), x2, x1) -> ConsL(plus#2(x2, x4), zipwith_l#3(x1, x3)) 1116.16/291.53 cond_zipwith_l_f_xs_ys(ConsL(x5, x4), zipwith_l_f_xs_ys(x1, x2, x3)) -> cond_zipwith_l_f_xs_ys_1(zipwith_l_f_xs_ys#1(x1, x2, x3, bot[6]), x5, x4) 1116.16/291.53 cond_zipwith_l_f_xs_ys(ConsL(x5, x4), fibs_2(x1, x2, x3)) -> cond_zipwith_l_f_xs_ys_1(fibs_2#1(x1, x2, x3, bot[6]), x5, x4) 1116.16/291.53 zipwith_l_f_xs_ys#1(plus, fibs, x5, x3) -> cond_zipwith_l_f_xs_ys(ConsL(0, fibs_2(zipwith_l, plus, tail_l)), x5) 1116.16/291.53 zipwith_l_f_xs_ys#1(plus, fibs_2(x3, x4, x5), x2, x1) -> cond_zipwith_l_f_xs_ys(fibs_2#1(x3, x4, x5, bot[7]), x2) 1116.16/291.53 zipwith_l_f_xs_ys#1(plus, zipwith_l_f_xs_ys(x3, x4, x5), x2, x1) -> cond_zipwith_l_f_xs_ys(zipwith_l_f_xs_ys#1(x3, x4, x5, bot[7]), x2) 1116.16/291.53 zipwith_l#3(x8, x4) -> zipwith_l_f_xs_ys(plus, x8, x4) 1116.16/291.53 main(x12) -> cond_take_l_n_xs(ConsL(0, fibs_2(zipwith_l, plus, tail_l)), x12) 1116.16/291.53 1116.16/291.53 S is empty. 1116.16/291.53 Rewrite Strategy: INNERMOST 1116.41/291.67 EOF