982.41/291.50 WORST_CASE(Omega(n^1), O(n^2)) 982.69/291.53 proof of /export/starexec/sandbox2/benchmark/theBenchmark.xml 982.69/291.53 # AProVE Commit ID: 48fb2092695e11cc9f56e44b17a92a5f88ffb256 marcel 20180622 unpublished dirty 982.69/291.53 982.69/291.53 982.69/291.53 The Runtime Complexity (innermost) of the given CpxTRS could be proven to be BOUNDS(n^1, n^2). 982.69/291.53 982.69/291.53 (0) CpxTRS 982.69/291.53 (1) RelTrsToWeightedTrsProof [BOTH BOUNDS(ID, ID), 0 ms] 982.69/291.53 (2) CpxWeightedTrs 982.69/291.53 (3) TypeInferenceProof [BOTH BOUNDS(ID, ID), 0 ms] 982.69/291.53 (4) CpxTypedWeightedTrs 982.69/291.53 (5) CompletionProof [UPPER BOUND(ID), 0 ms] 982.69/291.53 (6) CpxTypedWeightedCompleteTrs 982.69/291.53 (7) NarrowingProof [BOTH BOUNDS(ID, ID), 0 ms] 982.69/291.53 (8) CpxTypedWeightedCompleteTrs 982.69/291.53 (9) CpxTypedWeightedTrsToRntsProof [UPPER BOUND(ID), 0 ms] 982.69/291.53 (10) CpxRNTS 982.69/291.53 (11) InliningProof [UPPER BOUND(ID), 75 ms] 982.69/291.53 (12) CpxRNTS 982.69/291.53 (13) SimplificationProof [BOTH BOUNDS(ID, ID), 0 ms] 982.69/291.53 (14) CpxRNTS 982.69/291.53 (15) CpxRntsAnalysisOrderProof [BOTH BOUNDS(ID, ID), 0 ms] 982.69/291.53 (16) CpxRNTS 982.69/291.53 (17) ResultPropagationProof [UPPER BOUND(ID), 0 ms] 982.69/291.53 (18) CpxRNTS 982.69/291.53 (19) IntTrsBoundProof [UPPER BOUND(ID), 177 ms] 982.69/291.53 (20) CpxRNTS 982.69/291.53 (21) IntTrsBoundProof [UPPER BOUND(ID), 88 ms] 982.69/291.53 (22) CpxRNTS 982.69/291.53 (23) ResultPropagationProof [UPPER BOUND(ID), 0 ms] 982.69/291.53 (24) CpxRNTS 982.69/291.53 (25) IntTrsBoundProof [UPPER BOUND(ID), 177 ms] 982.69/291.53 (26) CpxRNTS 982.69/291.53 (27) IntTrsBoundProof [UPPER BOUND(ID), 75 ms] 982.69/291.53 (28) CpxRNTS 982.69/291.53 (29) ResultPropagationProof [UPPER BOUND(ID), 0 ms] 982.69/291.53 (30) CpxRNTS 982.69/291.53 (31) IntTrsBoundProof [UPPER BOUND(ID), 127 ms] 982.69/291.53 (32) CpxRNTS 982.69/291.53 (33) IntTrsBoundProof [UPPER BOUND(ID), 0 ms] 982.69/291.53 (34) CpxRNTS 982.69/291.53 (35) ResultPropagationProof [UPPER BOUND(ID), 0 ms] 982.69/291.53 (36) CpxRNTS 982.69/291.53 (37) IntTrsBoundProof [UPPER BOUND(ID), 157 ms] 982.69/291.53 (38) CpxRNTS 982.69/291.53 (39) IntTrsBoundProof [UPPER BOUND(ID), 52 ms] 982.69/291.53 (40) CpxRNTS 982.69/291.53 (41) ResultPropagationProof [UPPER BOUND(ID), 0 ms] 982.69/291.53 (42) CpxRNTS 982.69/291.53 (43) IntTrsBoundProof [UPPER BOUND(ID), 1703 ms] 982.69/291.53 (44) CpxRNTS 982.69/291.53 (45) IntTrsBoundProof [UPPER BOUND(ID), 684 ms] 982.69/291.53 (46) CpxRNTS 982.69/291.53 (47) ResultPropagationProof [UPPER BOUND(ID), 0 ms] 982.69/291.53 (48) CpxRNTS 982.69/291.53 (49) IntTrsBoundProof [UPPER BOUND(ID), 87 ms] 982.69/291.53 (50) CpxRNTS 982.69/291.53 (51) IntTrsBoundProof [UPPER BOUND(ID), 0 ms] 982.69/291.53 (52) CpxRNTS 982.69/291.53 (53) FinalProof [FINISHED, 0 ms] 982.69/291.53 (54) BOUNDS(1, n^2) 982.69/291.53 (55) RelTrsToDecreasingLoopProblemProof [LOWER BOUND(ID), 0 ms] 982.69/291.53 (56) TRS for Loop Detection 982.69/291.53 (57) DecreasingLoopProof [LOWER BOUND(ID), 0 ms] 982.69/291.53 (58) BEST 982.69/291.53 (59) proven lower bound 982.69/291.53 (60) LowerBoundPropagationProof [FINISHED, 0 ms] 982.69/291.53 (61) BOUNDS(n^1, INF) 982.69/291.53 (62) TRS for Loop Detection 982.69/291.53 982.69/291.53 982.69/291.53 ---------------------------------------- 982.69/291.53 982.69/291.53 (0) 982.69/291.53 Obligation: 982.69/291.53 The Runtime Complexity (innermost) of the given CpxTRS could be proven to be BOUNDS(n^1, n^2). 982.69/291.53 982.69/291.53 982.69/291.53 The TRS R consists of the following rules: 982.69/291.53 982.69/291.53 half(0) -> 0 982.69/291.53 half(s(0)) -> 0 982.69/291.53 half(s(s(x))) -> s(half(x)) 982.69/291.53 inc(0) -> 0 982.69/291.53 inc(s(x)) -> s(inc(x)) 982.69/291.53 zero(0) -> true 982.69/291.53 zero(s(x)) -> false 982.69/291.53 p(0) -> 0 982.69/291.53 p(s(x)) -> x 982.69/291.53 bits(x) -> bitIter(x, 0) 982.69/291.53 bitIter(x, y) -> if(zero(x), x, inc(y)) 982.69/291.53 if(true, x, y) -> p(y) 982.69/291.53 if(false, x, y) -> bitIter(half(x), y) 982.69/291.53 982.69/291.53 S is empty. 982.69/291.53 Rewrite Strategy: INNERMOST 982.69/291.53 ---------------------------------------- 982.69/291.53 982.69/291.53 (1) RelTrsToWeightedTrsProof (BOTH BOUNDS(ID, ID)) 982.69/291.53 Transformed relative TRS to weighted TRS 982.69/291.53 ---------------------------------------- 982.69/291.53 982.69/291.53 (2) 982.69/291.53 Obligation: 982.69/291.53 The Runtime Complexity (innermost) of the given CpxWeightedTrs could be proven to be BOUNDS(1, n^2). 982.69/291.53 982.69/291.53 982.69/291.53 The TRS R consists of the following rules: 982.69/291.53 982.69/291.53 half(0) -> 0 [1] 982.69/291.53 half(s(0)) -> 0 [1] 982.69/291.53 half(s(s(x))) -> s(half(x)) [1] 982.69/291.53 inc(0) -> 0 [1] 982.69/291.53 inc(s(x)) -> s(inc(x)) [1] 982.69/291.53 zero(0) -> true [1] 982.69/291.53 zero(s(x)) -> false [1] 982.69/291.53 p(0) -> 0 [1] 982.69/291.53 p(s(x)) -> x [1] 982.69/291.53 bits(x) -> bitIter(x, 0) [1] 982.69/291.53 bitIter(x, y) -> if(zero(x), x, inc(y)) [1] 982.69/291.53 if(true, x, y) -> p(y) [1] 982.69/291.53 if(false, x, y) -> bitIter(half(x), y) [1] 982.69/291.53 982.69/291.53 Rewrite Strategy: INNERMOST 982.69/291.53 ---------------------------------------- 982.69/291.53 982.69/291.53 (3) TypeInferenceProof (BOTH BOUNDS(ID, ID)) 982.69/291.53 Infered types. 982.69/291.53 ---------------------------------------- 982.69/291.53 982.69/291.53 (4) 982.69/291.53 Obligation: 982.69/291.53 Runtime Complexity Weighted TRS with Types. 982.69/291.53 The TRS R consists of the following rules: 982.69/291.53 982.69/291.53 half(0) -> 0 [1] 982.69/291.53 half(s(0)) -> 0 [1] 982.69/291.53 half(s(s(x))) -> s(half(x)) [1] 982.69/291.53 inc(0) -> 0 [1] 982.69/291.53 inc(s(x)) -> s(inc(x)) [1] 982.69/291.53 zero(0) -> true [1] 982.69/291.53 zero(s(x)) -> false [1] 982.69/291.53 p(0) -> 0 [1] 982.69/291.53 p(s(x)) -> x [1] 982.69/291.53 bits(x) -> bitIter(x, 0) [1] 982.69/291.53 bitIter(x, y) -> if(zero(x), x, inc(y)) [1] 982.69/291.53 if(true, x, y) -> p(y) [1] 982.69/291.53 if(false, x, y) -> bitIter(half(x), y) [1] 982.69/291.53 982.69/291.53 The TRS has the following type information: 982.69/291.53 half :: 0:s -> 0:s 982.69/291.53 0 :: 0:s 982.69/291.53 s :: 0:s -> 0:s 982.69/291.53 inc :: 0:s -> 0:s 982.69/291.53 zero :: 0:s -> true:false 982.69/291.53 true :: true:false 982.69/291.53 false :: true:false 982.69/291.53 p :: 0:s -> 0:s 982.69/291.53 bits :: 0:s -> 0:s 982.69/291.53 bitIter :: 0:s -> 0:s -> 0:s 982.69/291.53 if :: true:false -> 0:s -> 0:s -> 0:s 982.69/291.53 982.69/291.53 Rewrite Strategy: INNERMOST 982.69/291.53 ---------------------------------------- 982.69/291.53 982.69/291.53 (5) CompletionProof (UPPER BOUND(ID)) 982.69/291.53 The transformation into a RNTS is sound, since: 982.69/291.53 982.69/291.53 (a) The obligation is a constructor system where every type has a constant constructor, 982.69/291.53 982.69/291.53 (b) The following defined symbols do not have to be completely defined, as they can never occur inside other defined symbols: 982.69/291.53 982.69/291.53 p_1 982.69/291.53 bits_1 982.69/291.53 bitIter_2 982.69/291.53 if_3 982.69/291.53 982.69/291.53 (c) The following functions are completely defined: 982.69/291.53 982.69/291.53 zero_1 982.69/291.53 inc_1 982.69/291.53 half_1 982.69/291.53 982.69/291.53 Due to the following rules being added: 982.69/291.53 none 982.69/291.53 982.69/291.53 And the following fresh constants: none 982.69/291.53 982.69/291.53 ---------------------------------------- 982.69/291.53 982.69/291.53 (6) 982.69/291.53 Obligation: 982.69/291.53 Runtime Complexity Weighted TRS where critical functions are completely defined. The underlying TRS is: 982.69/291.53 982.69/291.53 Runtime Complexity Weighted TRS with Types. 982.69/291.53 The TRS R consists of the following rules: 982.69/291.53 982.69/291.53 half(0) -> 0 [1] 982.69/291.53 half(s(0)) -> 0 [1] 982.69/291.53 half(s(s(x))) -> s(half(x)) [1] 982.69/291.53 inc(0) -> 0 [1] 982.69/291.53 inc(s(x)) -> s(inc(x)) [1] 982.69/291.53 zero(0) -> true [1] 982.69/291.53 zero(s(x)) -> false [1] 982.69/291.53 p(0) -> 0 [1] 982.69/291.53 p(s(x)) -> x [1] 982.69/291.53 bits(x) -> bitIter(x, 0) [1] 982.69/291.53 bitIter(x, y) -> if(zero(x), x, inc(y)) [1] 982.69/291.53 if(true, x, y) -> p(y) [1] 982.69/291.53 if(false, x, y) -> bitIter(half(x), y) [1] 982.69/291.53 982.69/291.53 The TRS has the following type information: 982.69/291.53 half :: 0:s -> 0:s 982.69/291.53 0 :: 0:s 982.69/291.53 s :: 0:s -> 0:s 982.69/291.53 inc :: 0:s -> 0:s 982.69/291.53 zero :: 0:s -> true:false 982.69/291.53 true :: true:false 982.69/291.53 false :: true:false 982.69/291.53 p :: 0:s -> 0:s 982.69/291.53 bits :: 0:s -> 0:s 982.69/291.53 bitIter :: 0:s -> 0:s -> 0:s 982.69/291.53 if :: true:false -> 0:s -> 0:s -> 0:s 982.69/291.53 982.69/291.53 Rewrite Strategy: INNERMOST 982.69/291.53 ---------------------------------------- 982.69/291.53 982.69/291.53 (7) NarrowingProof (BOTH BOUNDS(ID, ID)) 982.69/291.53 Narrowed the inner basic terms of all right-hand sides by a single narrowing step. 982.69/291.53 ---------------------------------------- 982.69/291.53 982.69/291.53 (8) 982.69/291.53 Obligation: 982.69/291.53 Runtime Complexity Weighted TRS where critical functions are completely defined. The underlying TRS is: 982.69/291.53 982.69/291.53 Runtime Complexity Weighted TRS with Types. 982.69/291.53 The TRS R consists of the following rules: 982.69/291.53 982.69/291.53 half(0) -> 0 [1] 982.69/291.53 half(s(0)) -> 0 [1] 982.69/291.53 half(s(s(x))) -> s(half(x)) [1] 982.69/291.53 inc(0) -> 0 [1] 982.69/291.53 inc(s(x)) -> s(inc(x)) [1] 982.69/291.53 zero(0) -> true [1] 982.69/291.53 zero(s(x)) -> false [1] 982.69/291.53 p(0) -> 0 [1] 982.69/291.53 p(s(x)) -> x [1] 982.69/291.53 bits(x) -> bitIter(x, 0) [1] 982.69/291.53 bitIter(0, 0) -> if(true, 0, 0) [3] 982.69/291.53 bitIter(0, s(x'')) -> if(true, 0, s(inc(x''))) [3] 982.69/291.53 bitIter(s(x'), 0) -> if(false, s(x'), 0) [3] 982.69/291.53 bitIter(s(x'), s(x1)) -> if(false, s(x'), s(inc(x1))) [3] 982.69/291.53 if(true, x, y) -> p(y) [1] 982.69/291.53 if(false, 0, y) -> bitIter(0, y) [2] 982.69/291.53 if(false, s(0), y) -> bitIter(0, y) [2] 982.69/291.53 if(false, s(s(x2)), y) -> bitIter(s(half(x2)), y) [2] 982.69/291.53 982.69/291.53 The TRS has the following type information: 982.69/291.53 half :: 0:s -> 0:s 982.69/291.53 0 :: 0:s 982.69/291.53 s :: 0:s -> 0:s 982.69/291.53 inc :: 0:s -> 0:s 982.69/291.53 zero :: 0:s -> true:false 982.69/291.53 true :: true:false 982.69/291.53 false :: true:false 982.69/291.53 p :: 0:s -> 0:s 982.69/291.53 bits :: 0:s -> 0:s 982.69/291.53 bitIter :: 0:s -> 0:s -> 0:s 982.69/291.53 if :: true:false -> 0:s -> 0:s -> 0:s 982.69/291.53 982.69/291.53 Rewrite Strategy: INNERMOST 982.69/291.53 ---------------------------------------- 982.69/291.53 982.69/291.53 (9) CpxTypedWeightedTrsToRntsProof (UPPER BOUND(ID)) 982.69/291.53 Transformed the TRS into an over-approximating RNTS by (improved) Size Abstraction. 982.69/291.53 The constant constructors are abstracted as follows: 982.69/291.53 982.69/291.53 0 => 0 982.69/291.53 true => 1 982.69/291.53 false => 0 982.69/291.53 982.69/291.53 ---------------------------------------- 982.69/291.53 982.69/291.53 (10) 982.69/291.53 Obligation: 982.69/291.53 Complexity RNTS consisting of the following rules: 982.69/291.53 982.69/291.53 bitIter(z, z') -{ 3 }-> if(1, 0, 0) :|: z = 0, z' = 0 982.69/291.53 bitIter(z, z') -{ 3 }-> if(1, 0, 1 + inc(x'')) :|: z' = 1 + x'', x'' >= 0, z = 0 982.69/291.53 bitIter(z, z') -{ 3 }-> if(0, 1 + x', 0) :|: z = 1 + x', x' >= 0, z' = 0 982.69/291.53 bitIter(z, z') -{ 3 }-> if(0, 1 + x', 1 + inc(x1)) :|: z = 1 + x', x1 >= 0, x' >= 0, z' = 1 + x1 982.69/291.53 bits(z) -{ 1 }-> bitIter(x, 0) :|: x >= 0, z = x 982.69/291.53 half(z) -{ 1 }-> 0 :|: z = 0 982.69/291.53 half(z) -{ 1 }-> 0 :|: z = 1 + 0 982.69/291.53 half(z) -{ 1 }-> 1 + half(x) :|: x >= 0, z = 1 + (1 + x) 982.69/291.53 if(z, z', z'') -{ 1 }-> p(y) :|: z' = x, z'' = y, z = 1, x >= 0, y >= 0 982.69/291.53 if(z, z', z'') -{ 2 }-> bitIter(0, y) :|: z'' = y, y >= 0, z = 0, z' = 0 982.69/291.53 if(z, z', z'') -{ 2 }-> bitIter(0, y) :|: z'' = y, y >= 0, z' = 1 + 0, z = 0 982.69/291.53 if(z, z', z'') -{ 2 }-> bitIter(1 + half(x2), y) :|: z'' = y, z' = 1 + (1 + x2), y >= 0, z = 0, x2 >= 0 982.69/291.53 inc(z) -{ 1 }-> 0 :|: z = 0 982.69/291.53 inc(z) -{ 1 }-> 1 + inc(x) :|: x >= 0, z = 1 + x 982.69/291.53 p(z) -{ 1 }-> x :|: x >= 0, z = 1 + x 982.69/291.53 p(z) -{ 1 }-> 0 :|: z = 0 982.69/291.53 zero(z) -{ 1 }-> 1 :|: z = 0 982.69/291.53 zero(z) -{ 1 }-> 0 :|: x >= 0, z = 1 + x 982.69/291.53 982.69/291.53 982.69/291.53 ---------------------------------------- 982.69/291.53 982.69/291.53 (11) InliningProof (UPPER BOUND(ID)) 982.69/291.53 Inlined the following terminating rules on right-hand sides where appropriate: 982.69/291.53 982.69/291.53 p(z) -{ 1 }-> x :|: x >= 0, z = 1 + x 982.69/291.53 p(z) -{ 1 }-> 0 :|: z = 0 982.69/291.53 982.69/291.53 ---------------------------------------- 982.69/291.53 982.69/291.53 (12) 982.69/291.53 Obligation: 982.69/291.53 Complexity RNTS consisting of the following rules: 982.69/291.53 982.69/291.53 bitIter(z, z') -{ 3 }-> if(1, 0, 0) :|: z = 0, z' = 0 982.69/291.53 bitIter(z, z') -{ 3 }-> if(1, 0, 1 + inc(x'')) :|: z' = 1 + x'', x'' >= 0, z = 0 982.69/291.53 bitIter(z, z') -{ 3 }-> if(0, 1 + x', 0) :|: z = 1 + x', x' >= 0, z' = 0 982.69/291.53 bitIter(z, z') -{ 3 }-> if(0, 1 + x', 1 + inc(x1)) :|: z = 1 + x', x1 >= 0, x' >= 0, z' = 1 + x1 982.69/291.53 bits(z) -{ 1 }-> bitIter(x, 0) :|: x >= 0, z = x 982.69/291.53 half(z) -{ 1 }-> 0 :|: z = 0 982.69/291.53 half(z) -{ 1 }-> 0 :|: z = 1 + 0 982.69/291.53 half(z) -{ 1 }-> 1 + half(x) :|: x >= 0, z = 1 + (1 + x) 982.69/291.53 if(z, z', z'') -{ 2 }-> x' :|: z' = x, z'' = y, z = 1, x >= 0, y >= 0, x' >= 0, y = 1 + x' 982.69/291.53 if(z, z', z'') -{ 2 }-> bitIter(0, y) :|: z'' = y, y >= 0, z = 0, z' = 0 982.69/291.53 if(z, z', z'') -{ 2 }-> bitIter(0, y) :|: z'' = y, y >= 0, z' = 1 + 0, z = 0 982.69/291.53 if(z, z', z'') -{ 2 }-> bitIter(1 + half(x2), y) :|: z'' = y, z' = 1 + (1 + x2), y >= 0, z = 0, x2 >= 0 982.69/291.53 if(z, z', z'') -{ 2 }-> 0 :|: z' = x, z'' = y, z = 1, x >= 0, y >= 0, y = 0 982.69/291.53 inc(z) -{ 1 }-> 0 :|: z = 0 982.69/291.53 inc(z) -{ 1 }-> 1 + inc(x) :|: x >= 0, z = 1 + x 982.69/291.53 p(z) -{ 1 }-> x :|: x >= 0, z = 1 + x 982.69/291.53 p(z) -{ 1 }-> 0 :|: z = 0 982.69/291.53 zero(z) -{ 1 }-> 1 :|: z = 0 982.69/291.53 zero(z) -{ 1 }-> 0 :|: x >= 0, z = 1 + x 982.69/291.53 982.69/291.53 982.69/291.53 ---------------------------------------- 982.69/291.53 982.69/291.53 (13) SimplificationProof (BOTH BOUNDS(ID, ID)) 982.69/291.53 Simplified the RNTS by moving equalities from the constraints into the right-hand sides. 982.69/291.53 ---------------------------------------- 982.69/291.53 982.69/291.53 (14) 982.69/291.53 Obligation: 982.69/291.53 Complexity RNTS consisting of the following rules: 982.69/291.53 982.69/291.53 bitIter(z, z') -{ 3 }-> if(1, 0, 0) :|: z = 0, z' = 0 982.69/291.53 bitIter(z, z') -{ 3 }-> if(1, 0, 1 + inc(z' - 1)) :|: z' - 1 >= 0, z = 0 982.69/291.53 bitIter(z, z') -{ 3 }-> if(0, 1 + (z - 1), 0) :|: z - 1 >= 0, z' = 0 982.69/291.53 bitIter(z, z') -{ 3 }-> if(0, 1 + (z - 1), 1 + inc(z' - 1)) :|: z' - 1 >= 0, z - 1 >= 0 982.69/291.53 bits(z) -{ 1 }-> bitIter(z, 0) :|: z >= 0 982.69/291.53 half(z) -{ 1 }-> 0 :|: z = 0 982.69/291.53 half(z) -{ 1 }-> 0 :|: z = 1 + 0 982.69/291.53 half(z) -{ 1 }-> 1 + half(z - 2) :|: z - 2 >= 0 982.69/291.53 if(z, z', z'') -{ 2 }-> bitIter(0, z'') :|: z'' >= 0, z = 0, z' = 0 982.69/291.53 if(z, z', z'') -{ 2 }-> bitIter(0, z'') :|: z'' >= 0, z' = 1 + 0, z = 0 982.69/291.53 if(z, z', z'') -{ 2 }-> bitIter(1 + half(z' - 2), z'') :|: z'' >= 0, z = 0, z' - 2 >= 0 982.69/291.53 if(z, z', z'') -{ 2 }-> 0 :|: z = 1, z' >= 0, z'' >= 0, z'' = 0 982.69/291.53 if(z, z', z'') -{ 2 }-> z'' - 1 :|: z = 1, z' >= 0, z'' >= 0, z'' - 1 >= 0 982.69/291.53 inc(z) -{ 1 }-> 0 :|: z = 0 982.69/291.53 inc(z) -{ 1 }-> 1 + inc(z - 1) :|: z - 1 >= 0 982.69/291.53 p(z) -{ 1 }-> 0 :|: z = 0 982.69/291.53 p(z) -{ 1 }-> z - 1 :|: z - 1 >= 0 982.69/291.53 zero(z) -{ 1 }-> 1 :|: z = 0 982.69/291.53 zero(z) -{ 1 }-> 0 :|: z - 1 >= 0 982.69/291.53 982.69/291.53 982.69/291.53 ---------------------------------------- 982.69/291.53 982.69/291.53 (15) CpxRntsAnalysisOrderProof (BOTH BOUNDS(ID, ID)) 982.69/291.53 Found the following analysis order by SCC decomposition: 982.69/291.53 982.69/291.53 { half } 982.69/291.53 { inc } 982.69/291.53 { zero } 982.69/291.53 { p } 982.69/291.53 { if, bitIter } 982.69/291.53 { bits } 982.69/291.53 982.69/291.53 ---------------------------------------- 982.69/291.53 982.69/291.53 (16) 982.69/291.53 Obligation: 982.69/291.53 Complexity RNTS consisting of the following rules: 982.69/291.53 982.69/291.53 bitIter(z, z') -{ 3 }-> if(1, 0, 0) :|: z = 0, z' = 0 982.69/291.53 bitIter(z, z') -{ 3 }-> if(1, 0, 1 + inc(z' - 1)) :|: z' - 1 >= 0, z = 0 982.69/291.53 bitIter(z, z') -{ 3 }-> if(0, 1 + (z - 1), 0) :|: z - 1 >= 0, z' = 0 982.69/291.53 bitIter(z, z') -{ 3 }-> if(0, 1 + (z - 1), 1 + inc(z' - 1)) :|: z' - 1 >= 0, z - 1 >= 0 982.69/291.53 bits(z) -{ 1 }-> bitIter(z, 0) :|: z >= 0 982.69/291.53 half(z) -{ 1 }-> 0 :|: z = 0 982.69/291.53 half(z) -{ 1 }-> 0 :|: z = 1 + 0 982.69/291.53 half(z) -{ 1 }-> 1 + half(z - 2) :|: z - 2 >= 0 982.69/291.53 if(z, z', z'') -{ 2 }-> bitIter(0, z'') :|: z'' >= 0, z = 0, z' = 0 982.69/291.53 if(z, z', z'') -{ 2 }-> bitIter(0, z'') :|: z'' >= 0, z' = 1 + 0, z = 0 982.69/291.53 if(z, z', z'') -{ 2 }-> bitIter(1 + half(z' - 2), z'') :|: z'' >= 0, z = 0, z' - 2 >= 0 982.69/291.53 if(z, z', z'') -{ 2 }-> 0 :|: z = 1, z' >= 0, z'' >= 0, z'' = 0 982.69/291.53 if(z, z', z'') -{ 2 }-> z'' - 1 :|: z = 1, z' >= 0, z'' >= 0, z'' - 1 >= 0 982.69/291.53 inc(z) -{ 1 }-> 0 :|: z = 0 982.69/291.53 inc(z) -{ 1 }-> 1 + inc(z - 1) :|: z - 1 >= 0 982.69/291.53 p(z) -{ 1 }-> 0 :|: z = 0 982.69/291.53 p(z) -{ 1 }-> z - 1 :|: z - 1 >= 0 982.69/291.53 zero(z) -{ 1 }-> 1 :|: z = 0 982.69/291.53 zero(z) -{ 1 }-> 0 :|: z - 1 >= 0 982.69/291.53 982.69/291.53 Function symbols to be analyzed: {half}, {inc}, {zero}, {p}, {if,bitIter}, {bits} 982.69/291.53 982.69/291.53 ---------------------------------------- 982.69/291.53 982.69/291.53 (17) ResultPropagationProof (UPPER BOUND(ID)) 982.69/291.53 Applied inner abstraction using the recently inferred runtime/size bounds where possible. 982.69/291.53 ---------------------------------------- 982.69/291.53 982.69/291.53 (18) 982.69/291.53 Obligation: 982.69/291.53 Complexity RNTS consisting of the following rules: 982.69/291.53 982.69/291.53 bitIter(z, z') -{ 3 }-> if(1, 0, 0) :|: z = 0, z' = 0 982.69/291.53 bitIter(z, z') -{ 3 }-> if(1, 0, 1 + inc(z' - 1)) :|: z' - 1 >= 0, z = 0 982.69/291.53 bitIter(z, z') -{ 3 }-> if(0, 1 + (z - 1), 0) :|: z - 1 >= 0, z' = 0 982.69/291.53 bitIter(z, z') -{ 3 }-> if(0, 1 + (z - 1), 1 + inc(z' - 1)) :|: z' - 1 >= 0, z - 1 >= 0 982.69/291.53 bits(z) -{ 1 }-> bitIter(z, 0) :|: z >= 0 982.69/291.53 half(z) -{ 1 }-> 0 :|: z = 0 982.69/291.53 half(z) -{ 1 }-> 0 :|: z = 1 + 0 982.69/291.53 half(z) -{ 1 }-> 1 + half(z - 2) :|: z - 2 >= 0 982.69/291.53 if(z, z', z'') -{ 2 }-> bitIter(0, z'') :|: z'' >= 0, z = 0, z' = 0 982.69/291.53 if(z, z', z'') -{ 2 }-> bitIter(0, z'') :|: z'' >= 0, z' = 1 + 0, z = 0 982.69/291.53 if(z, z', z'') -{ 2 }-> bitIter(1 + half(z' - 2), z'') :|: z'' >= 0, z = 0, z' - 2 >= 0 982.69/291.53 if(z, z', z'') -{ 2 }-> 0 :|: z = 1, z' >= 0, z'' >= 0, z'' = 0 982.69/291.53 if(z, z', z'') -{ 2 }-> z'' - 1 :|: z = 1, z' >= 0, z'' >= 0, z'' - 1 >= 0 982.69/291.53 inc(z) -{ 1 }-> 0 :|: z = 0 982.69/291.53 inc(z) -{ 1 }-> 1 + inc(z - 1) :|: z - 1 >= 0 982.69/291.53 p(z) -{ 1 }-> 0 :|: z = 0 982.69/291.53 p(z) -{ 1 }-> z - 1 :|: z - 1 >= 0 982.69/291.53 zero(z) -{ 1 }-> 1 :|: z = 0 982.69/291.53 zero(z) -{ 1 }-> 0 :|: z - 1 >= 0 982.69/291.53 982.69/291.53 Function symbols to be analyzed: {half}, {inc}, {zero}, {p}, {if,bitIter}, {bits} 982.69/291.53 982.69/291.53 ---------------------------------------- 982.69/291.53 982.69/291.53 (19) IntTrsBoundProof (UPPER BOUND(ID)) 982.69/291.53 982.69/291.53 Computed SIZE bound using KoAT for: half 982.69/291.53 after applying outer abstraction to obtain an ITS, 982.69/291.53 resulting in: O(n^1) with polynomial bound: z 982.69/291.53 982.69/291.53 ---------------------------------------- 982.69/291.53 982.69/291.53 (20) 982.69/291.53 Obligation: 982.69/291.53 Complexity RNTS consisting of the following rules: 982.69/291.53 982.69/291.53 bitIter(z, z') -{ 3 }-> if(1, 0, 0) :|: z = 0, z' = 0 982.69/291.53 bitIter(z, z') -{ 3 }-> if(1, 0, 1 + inc(z' - 1)) :|: z' - 1 >= 0, z = 0 982.69/291.53 bitIter(z, z') -{ 3 }-> if(0, 1 + (z - 1), 0) :|: z - 1 >= 0, z' = 0 982.69/291.53 bitIter(z, z') -{ 3 }-> if(0, 1 + (z - 1), 1 + inc(z' - 1)) :|: z' - 1 >= 0, z - 1 >= 0 982.69/291.53 bits(z) -{ 1 }-> bitIter(z, 0) :|: z >= 0 982.69/291.53 half(z) -{ 1 }-> 0 :|: z = 0 982.69/291.53 half(z) -{ 1 }-> 0 :|: z = 1 + 0 982.69/291.53 half(z) -{ 1 }-> 1 + half(z - 2) :|: z - 2 >= 0 982.69/291.53 if(z, z', z'') -{ 2 }-> bitIter(0, z'') :|: z'' >= 0, z = 0, z' = 0 982.69/291.53 if(z, z', z'') -{ 2 }-> bitIter(0, z'') :|: z'' >= 0, z' = 1 + 0, z = 0 982.69/291.53 if(z, z', z'') -{ 2 }-> bitIter(1 + half(z' - 2), z'') :|: z'' >= 0, z = 0, z' - 2 >= 0 982.69/291.53 if(z, z', z'') -{ 2 }-> 0 :|: z = 1, z' >= 0, z'' >= 0, z'' = 0 982.69/291.53 if(z, z', z'') -{ 2 }-> z'' - 1 :|: z = 1, z' >= 0, z'' >= 0, z'' - 1 >= 0 982.69/291.53 inc(z) -{ 1 }-> 0 :|: z = 0 982.69/291.53 inc(z) -{ 1 }-> 1 + inc(z - 1) :|: z - 1 >= 0 982.69/291.53 p(z) -{ 1 }-> 0 :|: z = 0 982.69/291.53 p(z) -{ 1 }-> z - 1 :|: z - 1 >= 0 982.69/291.53 zero(z) -{ 1 }-> 1 :|: z = 0 982.69/291.53 zero(z) -{ 1 }-> 0 :|: z - 1 >= 0 982.69/291.53 982.69/291.53 Function symbols to be analyzed: {half}, {inc}, {zero}, {p}, {if,bitIter}, {bits} 982.69/291.53 Previous analysis results are: 982.69/291.53 half: runtime: ?, size: O(n^1) [z] 982.69/291.53 982.69/291.53 ---------------------------------------- 982.69/291.53 982.69/291.53 (21) IntTrsBoundProof (UPPER BOUND(ID)) 982.69/291.53 982.69/291.53 Computed RUNTIME bound using CoFloCo for: half 982.69/291.53 after applying outer abstraction to obtain an ITS, 982.69/291.53 resulting in: O(n^1) with polynomial bound: 2 + z 982.69/291.53 982.69/291.53 ---------------------------------------- 982.69/291.53 982.69/291.53 (22) 982.69/291.53 Obligation: 982.69/291.53 Complexity RNTS consisting of the following rules: 982.69/291.53 982.69/291.53 bitIter(z, z') -{ 3 }-> if(1, 0, 0) :|: z = 0, z' = 0 982.69/291.53 bitIter(z, z') -{ 3 }-> if(1, 0, 1 + inc(z' - 1)) :|: z' - 1 >= 0, z = 0 982.69/291.53 bitIter(z, z') -{ 3 }-> if(0, 1 + (z - 1), 0) :|: z - 1 >= 0, z' = 0 982.69/291.53 bitIter(z, z') -{ 3 }-> if(0, 1 + (z - 1), 1 + inc(z' - 1)) :|: z' - 1 >= 0, z - 1 >= 0 982.69/291.53 bits(z) -{ 1 }-> bitIter(z, 0) :|: z >= 0 982.69/291.53 half(z) -{ 1 }-> 0 :|: z = 0 982.69/291.53 half(z) -{ 1 }-> 0 :|: z = 1 + 0 982.69/291.53 half(z) -{ 1 }-> 1 + half(z - 2) :|: z - 2 >= 0 982.69/291.53 if(z, z', z'') -{ 2 }-> bitIter(0, z'') :|: z'' >= 0, z = 0, z' = 0 982.69/291.53 if(z, z', z'') -{ 2 }-> bitIter(0, z'') :|: z'' >= 0, z' = 1 + 0, z = 0 982.69/291.53 if(z, z', z'') -{ 2 }-> bitIter(1 + half(z' - 2), z'') :|: z'' >= 0, z = 0, z' - 2 >= 0 982.69/291.53 if(z, z', z'') -{ 2 }-> 0 :|: z = 1, z' >= 0, z'' >= 0, z'' = 0 982.69/291.53 if(z, z', z'') -{ 2 }-> z'' - 1 :|: z = 1, z' >= 0, z'' >= 0, z'' - 1 >= 0 982.69/291.53 inc(z) -{ 1 }-> 0 :|: z = 0 982.69/291.53 inc(z) -{ 1 }-> 1 + inc(z - 1) :|: z - 1 >= 0 982.69/291.53 p(z) -{ 1 }-> 0 :|: z = 0 982.69/291.53 p(z) -{ 1 }-> z - 1 :|: z - 1 >= 0 982.69/291.53 zero(z) -{ 1 }-> 1 :|: z = 0 982.69/291.53 zero(z) -{ 1 }-> 0 :|: z - 1 >= 0 982.69/291.53 982.69/291.53 Function symbols to be analyzed: {inc}, {zero}, {p}, {if,bitIter}, {bits} 982.69/291.53 Previous analysis results are: 982.69/291.53 half: runtime: O(n^1) [2 + z], size: O(n^1) [z] 982.69/291.53 982.69/291.53 ---------------------------------------- 982.69/291.53 982.69/291.53 (23) ResultPropagationProof (UPPER BOUND(ID)) 982.69/291.53 Applied inner abstraction using the recently inferred runtime/size bounds where possible. 982.69/291.53 ---------------------------------------- 982.69/291.53 982.69/291.53 (24) 982.69/291.53 Obligation: 982.69/291.53 Complexity RNTS consisting of the following rules: 982.69/291.53 982.69/291.53 bitIter(z, z') -{ 3 }-> if(1, 0, 0) :|: z = 0, z' = 0 982.69/291.53 bitIter(z, z') -{ 3 }-> if(1, 0, 1 + inc(z' - 1)) :|: z' - 1 >= 0, z = 0 982.69/291.53 bitIter(z, z') -{ 3 }-> if(0, 1 + (z - 1), 0) :|: z - 1 >= 0, z' = 0 982.69/291.53 bitIter(z, z') -{ 3 }-> if(0, 1 + (z - 1), 1 + inc(z' - 1)) :|: z' - 1 >= 0, z - 1 >= 0 982.69/291.53 bits(z) -{ 1 }-> bitIter(z, 0) :|: z >= 0 982.69/291.53 half(z) -{ 1 }-> 0 :|: z = 0 982.69/291.53 half(z) -{ 1 }-> 0 :|: z = 1 + 0 982.69/291.53 half(z) -{ 1 + z }-> 1 + s :|: s >= 0, s <= z - 2, z - 2 >= 0 982.69/291.53 if(z, z', z'') -{ 2 }-> bitIter(0, z'') :|: z'' >= 0, z = 0, z' = 0 982.69/291.53 if(z, z', z'') -{ 2 }-> bitIter(0, z'') :|: z'' >= 0, z' = 1 + 0, z = 0 982.69/291.53 if(z, z', z'') -{ 2 + z' }-> bitIter(1 + s', z'') :|: s' >= 0, s' <= z' - 2, z'' >= 0, z = 0, z' - 2 >= 0 982.69/291.53 if(z, z', z'') -{ 2 }-> 0 :|: z = 1, z' >= 0, z'' >= 0, z'' = 0 982.69/291.53 if(z, z', z'') -{ 2 }-> z'' - 1 :|: z = 1, z' >= 0, z'' >= 0, z'' - 1 >= 0 982.69/291.53 inc(z) -{ 1 }-> 0 :|: z = 0 982.69/291.53 inc(z) -{ 1 }-> 1 + inc(z - 1) :|: z - 1 >= 0 982.69/291.53 p(z) -{ 1 }-> 0 :|: z = 0 982.69/291.53 p(z) -{ 1 }-> z - 1 :|: z - 1 >= 0 982.69/291.53 zero(z) -{ 1 }-> 1 :|: z = 0 982.69/291.53 zero(z) -{ 1 }-> 0 :|: z - 1 >= 0 982.69/291.53 982.69/291.53 Function symbols to be analyzed: {inc}, {zero}, {p}, {if,bitIter}, {bits} 982.69/291.53 Previous analysis results are: 982.69/291.53 half: runtime: O(n^1) [2 + z], size: O(n^1) [z] 982.69/291.53 982.69/291.53 ---------------------------------------- 982.69/291.53 982.69/291.53 (25) IntTrsBoundProof (UPPER BOUND(ID)) 982.69/291.53 982.69/291.53 Computed SIZE bound using CoFloCo for: inc 982.69/291.53 after applying outer abstraction to obtain an ITS, 982.69/291.53 resulting in: O(n^1) with polynomial bound: z 982.69/291.53 982.69/291.53 ---------------------------------------- 982.69/291.53 982.69/291.53 (26) 982.69/291.53 Obligation: 982.69/291.53 Complexity RNTS consisting of the following rules: 982.69/291.53 982.69/291.53 bitIter(z, z') -{ 3 }-> if(1, 0, 0) :|: z = 0, z' = 0 982.69/291.53 bitIter(z, z') -{ 3 }-> if(1, 0, 1 + inc(z' - 1)) :|: z' - 1 >= 0, z = 0 982.69/291.53 bitIter(z, z') -{ 3 }-> if(0, 1 + (z - 1), 0) :|: z - 1 >= 0, z' = 0 982.69/291.53 bitIter(z, z') -{ 3 }-> if(0, 1 + (z - 1), 1 + inc(z' - 1)) :|: z' - 1 >= 0, z - 1 >= 0 982.69/291.53 bits(z) -{ 1 }-> bitIter(z, 0) :|: z >= 0 982.69/291.53 half(z) -{ 1 }-> 0 :|: z = 0 982.69/291.53 half(z) -{ 1 }-> 0 :|: z = 1 + 0 982.69/291.53 half(z) -{ 1 + z }-> 1 + s :|: s >= 0, s <= z - 2, z - 2 >= 0 982.69/291.53 if(z, z', z'') -{ 2 }-> bitIter(0, z'') :|: z'' >= 0, z = 0, z' = 0 982.69/291.53 if(z, z', z'') -{ 2 }-> bitIter(0, z'') :|: z'' >= 0, z' = 1 + 0, z = 0 982.69/291.53 if(z, z', z'') -{ 2 + z' }-> bitIter(1 + s', z'') :|: s' >= 0, s' <= z' - 2, z'' >= 0, z = 0, z' - 2 >= 0 982.69/291.53 if(z, z', z'') -{ 2 }-> 0 :|: z = 1, z' >= 0, z'' >= 0, z'' = 0 982.69/291.53 if(z, z', z'') -{ 2 }-> z'' - 1 :|: z = 1, z' >= 0, z'' >= 0, z'' - 1 >= 0 982.69/291.53 inc(z) -{ 1 }-> 0 :|: z = 0 982.69/291.53 inc(z) -{ 1 }-> 1 + inc(z - 1) :|: z - 1 >= 0 982.69/291.53 p(z) -{ 1 }-> 0 :|: z = 0 982.69/291.53 p(z) -{ 1 }-> z - 1 :|: z - 1 >= 0 982.69/291.53 zero(z) -{ 1 }-> 1 :|: z = 0 982.69/291.53 zero(z) -{ 1 }-> 0 :|: z - 1 >= 0 982.69/291.53 982.69/291.53 Function symbols to be analyzed: {inc}, {zero}, {p}, {if,bitIter}, {bits} 982.69/291.53 Previous analysis results are: 982.69/291.53 half: runtime: O(n^1) [2 + z], size: O(n^1) [z] 982.69/291.53 inc: runtime: ?, size: O(n^1) [z] 982.69/291.53 982.69/291.53 ---------------------------------------- 982.69/291.53 982.69/291.53 (27) IntTrsBoundProof (UPPER BOUND(ID)) 982.69/291.53 982.69/291.53 Computed RUNTIME bound using CoFloCo for: inc 982.69/291.53 after applying outer abstraction to obtain an ITS, 982.69/291.53 resulting in: O(n^1) with polynomial bound: 1 + z 982.69/291.53 982.69/291.53 ---------------------------------------- 982.69/291.53 982.69/291.53 (28) 982.69/291.53 Obligation: 982.69/291.53 Complexity RNTS consisting of the following rules: 982.69/291.53 982.69/291.53 bitIter(z, z') -{ 3 }-> if(1, 0, 0) :|: z = 0, z' = 0 982.69/291.53 bitIter(z, z') -{ 3 }-> if(1, 0, 1 + inc(z' - 1)) :|: z' - 1 >= 0, z = 0 982.69/291.53 bitIter(z, z') -{ 3 }-> if(0, 1 + (z - 1), 0) :|: z - 1 >= 0, z' = 0 982.69/291.53 bitIter(z, z') -{ 3 }-> if(0, 1 + (z - 1), 1 + inc(z' - 1)) :|: z' - 1 >= 0, z - 1 >= 0 982.69/291.53 bits(z) -{ 1 }-> bitIter(z, 0) :|: z >= 0 982.69/291.53 half(z) -{ 1 }-> 0 :|: z = 0 982.69/291.53 half(z) -{ 1 }-> 0 :|: z = 1 + 0 982.69/291.53 half(z) -{ 1 + z }-> 1 + s :|: s >= 0, s <= z - 2, z - 2 >= 0 982.69/291.53 if(z, z', z'') -{ 2 }-> bitIter(0, z'') :|: z'' >= 0, z = 0, z' = 0 982.69/291.53 if(z, z', z'') -{ 2 }-> bitIter(0, z'') :|: z'' >= 0, z' = 1 + 0, z = 0 982.69/291.53 if(z, z', z'') -{ 2 + z' }-> bitIter(1 + s', z'') :|: s' >= 0, s' <= z' - 2, z'' >= 0, z = 0, z' - 2 >= 0 982.69/291.53 if(z, z', z'') -{ 2 }-> 0 :|: z = 1, z' >= 0, z'' >= 0, z'' = 0 982.69/291.53 if(z, z', z'') -{ 2 }-> z'' - 1 :|: z = 1, z' >= 0, z'' >= 0, z'' - 1 >= 0 982.69/291.53 inc(z) -{ 1 }-> 0 :|: z = 0 982.69/291.53 inc(z) -{ 1 }-> 1 + inc(z - 1) :|: z - 1 >= 0 982.69/291.53 p(z) -{ 1 }-> 0 :|: z = 0 982.69/291.53 p(z) -{ 1 }-> z - 1 :|: z - 1 >= 0 982.69/291.53 zero(z) -{ 1 }-> 1 :|: z = 0 982.69/291.53 zero(z) -{ 1 }-> 0 :|: z - 1 >= 0 982.69/291.53 982.69/291.53 Function symbols to be analyzed: {zero}, {p}, {if,bitIter}, {bits} 982.69/291.53 Previous analysis results are: 982.69/291.53 half: runtime: O(n^1) [2 + z], size: O(n^1) [z] 982.69/291.53 inc: runtime: O(n^1) [1 + z], size: O(n^1) [z] 982.69/291.53 982.69/291.53 ---------------------------------------- 982.69/291.53 982.69/291.53 (29) ResultPropagationProof (UPPER BOUND(ID)) 982.69/291.53 Applied inner abstraction using the recently inferred runtime/size bounds where possible. 982.69/291.53 ---------------------------------------- 982.69/291.53 982.69/291.53 (30) 982.69/291.53 Obligation: 982.69/291.53 Complexity RNTS consisting of the following rules: 982.69/291.53 982.69/291.53 bitIter(z, z') -{ 3 }-> if(1, 0, 0) :|: z = 0, z' = 0 982.69/291.53 bitIter(z, z') -{ 3 + z' }-> if(1, 0, 1 + s1) :|: s1 >= 0, s1 <= z' - 1, z' - 1 >= 0, z = 0 982.69/291.53 bitIter(z, z') -{ 3 }-> if(0, 1 + (z - 1), 0) :|: z - 1 >= 0, z' = 0 982.69/291.53 bitIter(z, z') -{ 3 + z' }-> if(0, 1 + (z - 1), 1 + s2) :|: s2 >= 0, s2 <= z' - 1, z' - 1 >= 0, z - 1 >= 0 982.69/291.53 bits(z) -{ 1 }-> bitIter(z, 0) :|: z >= 0 982.69/291.53 half(z) -{ 1 }-> 0 :|: z = 0 982.69/291.53 half(z) -{ 1 }-> 0 :|: z = 1 + 0 982.69/291.53 half(z) -{ 1 + z }-> 1 + s :|: s >= 0, s <= z - 2, z - 2 >= 0 982.69/291.53 if(z, z', z'') -{ 2 }-> bitIter(0, z'') :|: z'' >= 0, z = 0, z' = 0 982.69/291.53 if(z, z', z'') -{ 2 }-> bitIter(0, z'') :|: z'' >= 0, z' = 1 + 0, z = 0 982.69/291.53 if(z, z', z'') -{ 2 + z' }-> bitIter(1 + s', z'') :|: s' >= 0, s' <= z' - 2, z'' >= 0, z = 0, z' - 2 >= 0 982.69/291.53 if(z, z', z'') -{ 2 }-> 0 :|: z = 1, z' >= 0, z'' >= 0, z'' = 0 982.69/291.53 if(z, z', z'') -{ 2 }-> z'' - 1 :|: z = 1, z' >= 0, z'' >= 0, z'' - 1 >= 0 982.69/291.53 inc(z) -{ 1 }-> 0 :|: z = 0 982.69/291.53 inc(z) -{ 1 + z }-> 1 + s'' :|: s'' >= 0, s'' <= z - 1, z - 1 >= 0 982.69/291.53 p(z) -{ 1 }-> 0 :|: z = 0 982.69/291.53 p(z) -{ 1 }-> z - 1 :|: z - 1 >= 0 982.69/291.53 zero(z) -{ 1 }-> 1 :|: z = 0 982.69/291.53 zero(z) -{ 1 }-> 0 :|: z - 1 >= 0 982.69/291.53 982.69/291.53 Function symbols to be analyzed: {zero}, {p}, {if,bitIter}, {bits} 982.69/291.53 Previous analysis results are: 982.69/291.53 half: runtime: O(n^1) [2 + z], size: O(n^1) [z] 982.69/291.53 inc: runtime: O(n^1) [1 + z], size: O(n^1) [z] 982.69/291.53 982.69/291.53 ---------------------------------------- 982.69/291.53 982.69/291.53 (31) IntTrsBoundProof (UPPER BOUND(ID)) 982.69/291.53 982.69/291.53 Computed SIZE bound using CoFloCo for: zero 982.69/291.53 after applying outer abstraction to obtain an ITS, 982.69/291.53 resulting in: O(1) with polynomial bound: 1 982.69/291.53 982.69/291.53 ---------------------------------------- 982.69/291.53 982.69/291.53 (32) 982.69/291.53 Obligation: 982.69/291.53 Complexity RNTS consisting of the following rules: 982.69/291.53 982.69/291.53 bitIter(z, z') -{ 3 }-> if(1, 0, 0) :|: z = 0, z' = 0 982.69/291.53 bitIter(z, z') -{ 3 + z' }-> if(1, 0, 1 + s1) :|: s1 >= 0, s1 <= z' - 1, z' - 1 >= 0, z = 0 982.69/291.53 bitIter(z, z') -{ 3 }-> if(0, 1 + (z - 1), 0) :|: z - 1 >= 0, z' = 0 982.69/291.53 bitIter(z, z') -{ 3 + z' }-> if(0, 1 + (z - 1), 1 + s2) :|: s2 >= 0, s2 <= z' - 1, z' - 1 >= 0, z - 1 >= 0 982.69/291.53 bits(z) -{ 1 }-> bitIter(z, 0) :|: z >= 0 982.69/291.53 half(z) -{ 1 }-> 0 :|: z = 0 982.69/291.53 half(z) -{ 1 }-> 0 :|: z = 1 + 0 982.69/291.53 half(z) -{ 1 + z }-> 1 + s :|: s >= 0, s <= z - 2, z - 2 >= 0 982.69/291.53 if(z, z', z'') -{ 2 }-> bitIter(0, z'') :|: z'' >= 0, z = 0, z' = 0 982.69/291.53 if(z, z', z'') -{ 2 }-> bitIter(0, z'') :|: z'' >= 0, z' = 1 + 0, z = 0 982.69/291.53 if(z, z', z'') -{ 2 + z' }-> bitIter(1 + s', z'') :|: s' >= 0, s' <= z' - 2, z'' >= 0, z = 0, z' - 2 >= 0 982.69/291.53 if(z, z', z'') -{ 2 }-> 0 :|: z = 1, z' >= 0, z'' >= 0, z'' = 0 982.69/291.53 if(z, z', z'') -{ 2 }-> z'' - 1 :|: z = 1, z' >= 0, z'' >= 0, z'' - 1 >= 0 982.69/291.53 inc(z) -{ 1 }-> 0 :|: z = 0 982.69/291.53 inc(z) -{ 1 + z }-> 1 + s'' :|: s'' >= 0, s'' <= z - 1, z - 1 >= 0 982.69/291.53 p(z) -{ 1 }-> 0 :|: z = 0 982.69/291.53 p(z) -{ 1 }-> z - 1 :|: z - 1 >= 0 982.69/291.53 zero(z) -{ 1 }-> 1 :|: z = 0 982.69/291.53 zero(z) -{ 1 }-> 0 :|: z - 1 >= 0 982.69/291.53 982.69/291.53 Function symbols to be analyzed: {zero}, {p}, {if,bitIter}, {bits} 982.69/291.53 Previous analysis results are: 982.69/291.53 half: runtime: O(n^1) [2 + z], size: O(n^1) [z] 982.69/291.53 inc: runtime: O(n^1) [1 + z], size: O(n^1) [z] 982.69/291.53 zero: runtime: ?, size: O(1) [1] 982.69/291.53 982.69/291.53 ---------------------------------------- 982.69/291.53 982.69/291.53 (33) IntTrsBoundProof (UPPER BOUND(ID)) 982.69/291.53 982.69/291.53 Computed RUNTIME bound using CoFloCo for: zero 982.69/291.53 after applying outer abstraction to obtain an ITS, 982.69/291.53 resulting in: O(1) with polynomial bound: 1 982.69/291.53 982.69/291.53 ---------------------------------------- 982.69/291.53 982.69/291.53 (34) 982.69/291.53 Obligation: 982.69/291.53 Complexity RNTS consisting of the following rules: 982.69/291.53 982.69/291.53 bitIter(z, z') -{ 3 }-> if(1, 0, 0) :|: z = 0, z' = 0 982.69/291.53 bitIter(z, z') -{ 3 + z' }-> if(1, 0, 1 + s1) :|: s1 >= 0, s1 <= z' - 1, z' - 1 >= 0, z = 0 982.69/291.53 bitIter(z, z') -{ 3 }-> if(0, 1 + (z - 1), 0) :|: z - 1 >= 0, z' = 0 982.69/291.53 bitIter(z, z') -{ 3 + z' }-> if(0, 1 + (z - 1), 1 + s2) :|: s2 >= 0, s2 <= z' - 1, z' - 1 >= 0, z - 1 >= 0 982.69/291.53 bits(z) -{ 1 }-> bitIter(z, 0) :|: z >= 0 982.69/291.53 half(z) -{ 1 }-> 0 :|: z = 0 982.69/291.53 half(z) -{ 1 }-> 0 :|: z = 1 + 0 982.69/291.53 half(z) -{ 1 + z }-> 1 + s :|: s >= 0, s <= z - 2, z - 2 >= 0 982.69/291.53 if(z, z', z'') -{ 2 }-> bitIter(0, z'') :|: z'' >= 0, z = 0, z' = 0 982.69/291.53 if(z, z', z'') -{ 2 }-> bitIter(0, z'') :|: z'' >= 0, z' = 1 + 0, z = 0 982.69/291.53 if(z, z', z'') -{ 2 + z' }-> bitIter(1 + s', z'') :|: s' >= 0, s' <= z' - 2, z'' >= 0, z = 0, z' - 2 >= 0 982.69/291.53 if(z, z', z'') -{ 2 }-> 0 :|: z = 1, z' >= 0, z'' >= 0, z'' = 0 982.69/291.53 if(z, z', z'') -{ 2 }-> z'' - 1 :|: z = 1, z' >= 0, z'' >= 0, z'' - 1 >= 0 982.69/291.53 inc(z) -{ 1 }-> 0 :|: z = 0 982.69/291.53 inc(z) -{ 1 + z }-> 1 + s'' :|: s'' >= 0, s'' <= z - 1, z - 1 >= 0 982.69/291.53 p(z) -{ 1 }-> 0 :|: z = 0 982.69/291.53 p(z) -{ 1 }-> z - 1 :|: z - 1 >= 0 982.69/291.53 zero(z) -{ 1 }-> 1 :|: z = 0 982.69/291.53 zero(z) -{ 1 }-> 0 :|: z - 1 >= 0 982.69/291.53 982.69/291.53 Function symbols to be analyzed: {p}, {if,bitIter}, {bits} 982.69/291.53 Previous analysis results are: 982.69/291.53 half: runtime: O(n^1) [2 + z], size: O(n^1) [z] 982.69/291.53 inc: runtime: O(n^1) [1 + z], size: O(n^1) [z] 982.69/291.53 zero: runtime: O(1) [1], size: O(1) [1] 982.69/291.53 982.69/291.53 ---------------------------------------- 982.69/291.53 982.69/291.53 (35) ResultPropagationProof (UPPER BOUND(ID)) 982.69/291.53 Applied inner abstraction using the recently inferred runtime/size bounds where possible. 982.69/291.53 ---------------------------------------- 982.69/291.53 982.69/291.53 (36) 982.69/291.53 Obligation: 982.69/291.53 Complexity RNTS consisting of the following rules: 982.69/291.53 982.69/291.53 bitIter(z, z') -{ 3 }-> if(1, 0, 0) :|: z = 0, z' = 0 982.69/291.53 bitIter(z, z') -{ 3 + z' }-> if(1, 0, 1 + s1) :|: s1 >= 0, s1 <= z' - 1, z' - 1 >= 0, z = 0 982.69/291.53 bitIter(z, z') -{ 3 }-> if(0, 1 + (z - 1), 0) :|: z - 1 >= 0, z' = 0 982.69/291.53 bitIter(z, z') -{ 3 + z' }-> if(0, 1 + (z - 1), 1 + s2) :|: s2 >= 0, s2 <= z' - 1, z' - 1 >= 0, z - 1 >= 0 982.69/291.53 bits(z) -{ 1 }-> bitIter(z, 0) :|: z >= 0 982.69/291.53 half(z) -{ 1 }-> 0 :|: z = 0 982.69/291.53 half(z) -{ 1 }-> 0 :|: z = 1 + 0 982.69/291.53 half(z) -{ 1 + z }-> 1 + s :|: s >= 0, s <= z - 2, z - 2 >= 0 982.69/291.53 if(z, z', z'') -{ 2 }-> bitIter(0, z'') :|: z'' >= 0, z = 0, z' = 0 982.69/291.53 if(z, z', z'') -{ 2 }-> bitIter(0, z'') :|: z'' >= 0, z' = 1 + 0, z = 0 982.69/291.53 if(z, z', z'') -{ 2 + z' }-> bitIter(1 + s', z'') :|: s' >= 0, s' <= z' - 2, z'' >= 0, z = 0, z' - 2 >= 0 982.69/291.53 if(z, z', z'') -{ 2 }-> 0 :|: z = 1, z' >= 0, z'' >= 0, z'' = 0 982.69/291.53 if(z, z', z'') -{ 2 }-> z'' - 1 :|: z = 1, z' >= 0, z'' >= 0, z'' - 1 >= 0 982.69/291.53 inc(z) -{ 1 }-> 0 :|: z = 0 982.69/291.53 inc(z) -{ 1 + z }-> 1 + s'' :|: s'' >= 0, s'' <= z - 1, z - 1 >= 0 982.69/291.53 p(z) -{ 1 }-> 0 :|: z = 0 982.69/291.53 p(z) -{ 1 }-> z - 1 :|: z - 1 >= 0 982.69/291.53 zero(z) -{ 1 }-> 1 :|: z = 0 982.69/291.53 zero(z) -{ 1 }-> 0 :|: z - 1 >= 0 982.69/291.53 982.69/291.53 Function symbols to be analyzed: {p}, {if,bitIter}, {bits} 982.69/291.53 Previous analysis results are: 982.69/291.53 half: runtime: O(n^1) [2 + z], size: O(n^1) [z] 982.69/291.53 inc: runtime: O(n^1) [1 + z], size: O(n^1) [z] 982.69/291.53 zero: runtime: O(1) [1], size: O(1) [1] 982.69/291.53 982.69/291.53 ---------------------------------------- 982.69/291.53 982.69/291.53 (37) IntTrsBoundProof (UPPER BOUND(ID)) 982.69/291.53 982.69/291.53 Computed SIZE bound using KoAT for: p 982.69/291.53 after applying outer abstraction to obtain an ITS, 982.69/291.53 resulting in: O(n^1) with polynomial bound: z 982.69/291.53 982.69/291.53 ---------------------------------------- 982.69/291.53 982.69/291.53 (38) 982.69/291.53 Obligation: 982.69/291.53 Complexity RNTS consisting of the following rules: 982.69/291.53 982.69/291.53 bitIter(z, z') -{ 3 }-> if(1, 0, 0) :|: z = 0, z' = 0 982.69/291.53 bitIter(z, z') -{ 3 + z' }-> if(1, 0, 1 + s1) :|: s1 >= 0, s1 <= z' - 1, z' - 1 >= 0, z = 0 982.69/291.53 bitIter(z, z') -{ 3 }-> if(0, 1 + (z - 1), 0) :|: z - 1 >= 0, z' = 0 982.69/291.53 bitIter(z, z') -{ 3 + z' }-> if(0, 1 + (z - 1), 1 + s2) :|: s2 >= 0, s2 <= z' - 1, z' - 1 >= 0, z - 1 >= 0 982.69/291.53 bits(z) -{ 1 }-> bitIter(z, 0) :|: z >= 0 982.69/291.53 half(z) -{ 1 }-> 0 :|: z = 0 982.69/291.53 half(z) -{ 1 }-> 0 :|: z = 1 + 0 982.69/291.53 half(z) -{ 1 + z }-> 1 + s :|: s >= 0, s <= z - 2, z - 2 >= 0 982.69/291.53 if(z, z', z'') -{ 2 }-> bitIter(0, z'') :|: z'' >= 0, z = 0, z' = 0 982.69/291.53 if(z, z', z'') -{ 2 }-> bitIter(0, z'') :|: z'' >= 0, z' = 1 + 0, z = 0 982.69/291.53 if(z, z', z'') -{ 2 + z' }-> bitIter(1 + s', z'') :|: s' >= 0, s' <= z' - 2, z'' >= 0, z = 0, z' - 2 >= 0 982.69/291.53 if(z, z', z'') -{ 2 }-> 0 :|: z = 1, z' >= 0, z'' >= 0, z'' = 0 982.69/291.53 if(z, z', z'') -{ 2 }-> z'' - 1 :|: z = 1, z' >= 0, z'' >= 0, z'' - 1 >= 0 982.69/291.53 inc(z) -{ 1 }-> 0 :|: z = 0 982.69/291.53 inc(z) -{ 1 + z }-> 1 + s'' :|: s'' >= 0, s'' <= z - 1, z - 1 >= 0 982.69/291.53 p(z) -{ 1 }-> 0 :|: z = 0 982.69/291.53 p(z) -{ 1 }-> z - 1 :|: z - 1 >= 0 982.69/291.53 zero(z) -{ 1 }-> 1 :|: z = 0 982.69/291.53 zero(z) -{ 1 }-> 0 :|: z - 1 >= 0 982.69/291.53 982.69/291.53 Function symbols to be analyzed: {p}, {if,bitIter}, {bits} 982.69/291.53 Previous analysis results are: 982.69/291.53 half: runtime: O(n^1) [2 + z], size: O(n^1) [z] 982.69/291.53 inc: runtime: O(n^1) [1 + z], size: O(n^1) [z] 982.69/291.53 zero: runtime: O(1) [1], size: O(1) [1] 982.69/291.53 p: runtime: ?, size: O(n^1) [z] 982.69/291.53 982.69/291.53 ---------------------------------------- 982.69/291.53 982.69/291.53 (39) IntTrsBoundProof (UPPER BOUND(ID)) 982.69/291.53 982.69/291.53 Computed RUNTIME bound using CoFloCo for: p 982.69/291.53 after applying outer abstraction to obtain an ITS, 982.69/291.53 resulting in: O(1) with polynomial bound: 1 982.69/291.53 982.69/291.53 ---------------------------------------- 982.69/291.53 982.69/291.53 (40) 982.69/291.53 Obligation: 982.69/291.53 Complexity RNTS consisting of the following rules: 982.69/291.53 982.69/291.53 bitIter(z, z') -{ 3 }-> if(1, 0, 0) :|: z = 0, z' = 0 982.69/291.53 bitIter(z, z') -{ 3 + z' }-> if(1, 0, 1 + s1) :|: s1 >= 0, s1 <= z' - 1, z' - 1 >= 0, z = 0 982.69/291.53 bitIter(z, z') -{ 3 }-> if(0, 1 + (z - 1), 0) :|: z - 1 >= 0, z' = 0 982.69/291.53 bitIter(z, z') -{ 3 + z' }-> if(0, 1 + (z - 1), 1 + s2) :|: s2 >= 0, s2 <= z' - 1, z' - 1 >= 0, z - 1 >= 0 982.69/291.53 bits(z) -{ 1 }-> bitIter(z, 0) :|: z >= 0 982.69/291.53 half(z) -{ 1 }-> 0 :|: z = 0 982.69/291.53 half(z) -{ 1 }-> 0 :|: z = 1 + 0 982.69/291.53 half(z) -{ 1 + z }-> 1 + s :|: s >= 0, s <= z - 2, z - 2 >= 0 982.69/291.53 if(z, z', z'') -{ 2 }-> bitIter(0, z'') :|: z'' >= 0, z = 0, z' = 0 982.69/291.53 if(z, z', z'') -{ 2 }-> bitIter(0, z'') :|: z'' >= 0, z' = 1 + 0, z = 0 982.69/291.53 if(z, z', z'') -{ 2 + z' }-> bitIter(1 + s', z'') :|: s' >= 0, s' <= z' - 2, z'' >= 0, z = 0, z' - 2 >= 0 982.69/291.53 if(z, z', z'') -{ 2 }-> 0 :|: z = 1, z' >= 0, z'' >= 0, z'' = 0 982.69/291.53 if(z, z', z'') -{ 2 }-> z'' - 1 :|: z = 1, z' >= 0, z'' >= 0, z'' - 1 >= 0 982.69/291.53 inc(z) -{ 1 }-> 0 :|: z = 0 982.69/291.53 inc(z) -{ 1 + z }-> 1 + s'' :|: s'' >= 0, s'' <= z - 1, z - 1 >= 0 982.69/291.53 p(z) -{ 1 }-> 0 :|: z = 0 982.69/291.53 p(z) -{ 1 }-> z - 1 :|: z - 1 >= 0 982.69/291.53 zero(z) -{ 1 }-> 1 :|: z = 0 982.69/291.53 zero(z) -{ 1 }-> 0 :|: z - 1 >= 0 982.69/291.53 982.69/291.53 Function symbols to be analyzed: {if,bitIter}, {bits} 982.69/291.53 Previous analysis results are: 982.69/291.53 half: runtime: O(n^1) [2 + z], size: O(n^1) [z] 982.69/291.53 inc: runtime: O(n^1) [1 + z], size: O(n^1) [z] 982.69/291.53 zero: runtime: O(1) [1], size: O(1) [1] 982.69/291.53 p: runtime: O(1) [1], size: O(n^1) [z] 982.69/291.53 982.69/291.53 ---------------------------------------- 982.69/291.53 982.69/291.53 (41) ResultPropagationProof (UPPER BOUND(ID)) 982.69/291.53 Applied inner abstraction using the recently inferred runtime/size bounds where possible. 982.69/291.53 ---------------------------------------- 982.69/291.53 982.69/291.53 (42) 982.69/291.53 Obligation: 982.69/291.53 Complexity RNTS consisting of the following rules: 982.69/291.53 982.69/291.53 bitIter(z, z') -{ 3 }-> if(1, 0, 0) :|: z = 0, z' = 0 982.69/291.53 bitIter(z, z') -{ 3 + z' }-> if(1, 0, 1 + s1) :|: s1 >= 0, s1 <= z' - 1, z' - 1 >= 0, z = 0 982.69/291.53 bitIter(z, z') -{ 3 }-> if(0, 1 + (z - 1), 0) :|: z - 1 >= 0, z' = 0 982.69/291.53 bitIter(z, z') -{ 3 + z' }-> if(0, 1 + (z - 1), 1 + s2) :|: s2 >= 0, s2 <= z' - 1, z' - 1 >= 0, z - 1 >= 0 982.69/291.53 bits(z) -{ 1 }-> bitIter(z, 0) :|: z >= 0 982.69/291.53 half(z) -{ 1 }-> 0 :|: z = 0 982.69/291.53 half(z) -{ 1 }-> 0 :|: z = 1 + 0 982.69/291.53 half(z) -{ 1 + z }-> 1 + s :|: s >= 0, s <= z - 2, z - 2 >= 0 982.69/291.53 if(z, z', z'') -{ 2 }-> bitIter(0, z'') :|: z'' >= 0, z = 0, z' = 0 982.69/291.53 if(z, z', z'') -{ 2 }-> bitIter(0, z'') :|: z'' >= 0, z' = 1 + 0, z = 0 982.69/291.53 if(z, z', z'') -{ 2 + z' }-> bitIter(1 + s', z'') :|: s' >= 0, s' <= z' - 2, z'' >= 0, z = 0, z' - 2 >= 0 982.69/291.53 if(z, z', z'') -{ 2 }-> 0 :|: z = 1, z' >= 0, z'' >= 0, z'' = 0 982.69/291.53 if(z, z', z'') -{ 2 }-> z'' - 1 :|: z = 1, z' >= 0, z'' >= 0, z'' - 1 >= 0 982.69/291.53 inc(z) -{ 1 }-> 0 :|: z = 0 982.69/291.53 inc(z) -{ 1 + z }-> 1 + s'' :|: s'' >= 0, s'' <= z - 1, z - 1 >= 0 982.69/291.53 p(z) -{ 1 }-> 0 :|: z = 0 982.69/291.53 p(z) -{ 1 }-> z - 1 :|: z - 1 >= 0 982.69/291.53 zero(z) -{ 1 }-> 1 :|: z = 0 982.69/291.53 zero(z) -{ 1 }-> 0 :|: z - 1 >= 0 982.69/291.53 982.69/291.53 Function symbols to be analyzed: {if,bitIter}, {bits} 982.69/291.53 Previous analysis results are: 982.69/291.53 half: runtime: O(n^1) [2 + z], size: O(n^1) [z] 982.69/291.53 inc: runtime: O(n^1) [1 + z], size: O(n^1) [z] 982.69/291.53 zero: runtime: O(1) [1], size: O(1) [1] 982.69/291.53 p: runtime: O(1) [1], size: O(n^1) [z] 982.69/291.53 982.69/291.53 ---------------------------------------- 982.69/291.53 982.69/291.53 (43) IntTrsBoundProof (UPPER BOUND(ID)) 982.69/291.53 982.69/291.53 Computed SIZE bound using KoAT for: if 982.69/291.53 after applying outer abstraction to obtain an ITS, 982.69/291.53 resulting in: O(n^1) with polynomial bound: z'' 982.69/291.54 982.69/291.54 Computed SIZE bound using CoFloCo for: bitIter 982.69/291.54 after applying outer abstraction to obtain an ITS, 982.69/291.54 resulting in: O(n^1) with polynomial bound: z' 982.69/291.54 982.69/291.54 ---------------------------------------- 982.69/291.54 982.69/291.54 (44) 982.69/291.54 Obligation: 982.69/291.54 Complexity RNTS consisting of the following rules: 982.69/291.54 982.69/291.54 bitIter(z, z') -{ 3 }-> if(1, 0, 0) :|: z = 0, z' = 0 982.69/291.54 bitIter(z, z') -{ 3 + z' }-> if(1, 0, 1 + s1) :|: s1 >= 0, s1 <= z' - 1, z' - 1 >= 0, z = 0 982.69/291.54 bitIter(z, z') -{ 3 }-> if(0, 1 + (z - 1), 0) :|: z - 1 >= 0, z' = 0 982.69/291.54 bitIter(z, z') -{ 3 + z' }-> if(0, 1 + (z - 1), 1 + s2) :|: s2 >= 0, s2 <= z' - 1, z' - 1 >= 0, z - 1 >= 0 982.69/291.54 bits(z) -{ 1 }-> bitIter(z, 0) :|: z >= 0 982.69/291.54 half(z) -{ 1 }-> 0 :|: z = 0 982.69/291.54 half(z) -{ 1 }-> 0 :|: z = 1 + 0 982.69/291.54 half(z) -{ 1 + z }-> 1 + s :|: s >= 0, s <= z - 2, z - 2 >= 0 982.69/291.54 if(z, z', z'') -{ 2 }-> bitIter(0, z'') :|: z'' >= 0, z = 0, z' = 0 982.69/291.54 if(z, z', z'') -{ 2 }-> bitIter(0, z'') :|: z'' >= 0, z' = 1 + 0, z = 0 982.69/291.54 if(z, z', z'') -{ 2 + z' }-> bitIter(1 + s', z'') :|: s' >= 0, s' <= z' - 2, z'' >= 0, z = 0, z' - 2 >= 0 982.69/291.54 if(z, z', z'') -{ 2 }-> 0 :|: z = 1, z' >= 0, z'' >= 0, z'' = 0 982.69/291.54 if(z, z', z'') -{ 2 }-> z'' - 1 :|: z = 1, z' >= 0, z'' >= 0, z'' - 1 >= 0 982.69/291.54 inc(z) -{ 1 }-> 0 :|: z = 0 982.69/291.54 inc(z) -{ 1 + z }-> 1 + s'' :|: s'' >= 0, s'' <= z - 1, z - 1 >= 0 982.69/291.54 p(z) -{ 1 }-> 0 :|: z = 0 982.69/291.54 p(z) -{ 1 }-> z - 1 :|: z - 1 >= 0 982.69/291.54 zero(z) -{ 1 }-> 1 :|: z = 0 982.69/291.54 zero(z) -{ 1 }-> 0 :|: z - 1 >= 0 982.69/291.54 982.69/291.54 Function symbols to be analyzed: {if,bitIter}, {bits} 982.69/291.54 Previous analysis results are: 982.69/291.54 half: runtime: O(n^1) [2 + z], size: O(n^1) [z] 982.69/291.54 inc: runtime: O(n^1) [1 + z], size: O(n^1) [z] 982.69/291.54 zero: runtime: O(1) [1], size: O(1) [1] 982.69/291.54 p: runtime: O(1) [1], size: O(n^1) [z] 982.69/291.54 if: runtime: ?, size: O(n^1) [z''] 982.69/291.54 bitIter: runtime: ?, size: O(n^1) [z'] 982.69/291.54 982.69/291.54 ---------------------------------------- 982.69/291.54 982.69/291.54 (45) IntTrsBoundProof (UPPER BOUND(ID)) 982.69/291.54 982.69/291.54 Computed RUNTIME bound using CoFloCo for: if 982.69/291.54 after applying outer abstraction to obtain an ITS, 982.69/291.54 resulting in: O(n^2) with polynomial bound: 12 + 7*z' + z'*z'' + z'^2 + 2*z'' 982.69/291.54 982.69/291.54 Computed RUNTIME bound using KoAT for: bitIter 982.69/291.54 after applying outer abstraction to obtain an ITS, 982.69/291.54 resulting in: O(n^2) with polynomial bound: 60 + 14*z + z*z' + 2*z^2 + 6*z' 982.69/291.54 982.69/291.54 ---------------------------------------- 982.69/291.54 982.69/291.54 (46) 982.69/291.54 Obligation: 982.69/291.54 Complexity RNTS consisting of the following rules: 982.69/291.54 982.69/291.54 bitIter(z, z') -{ 3 }-> if(1, 0, 0) :|: z = 0, z' = 0 982.69/291.54 bitIter(z, z') -{ 3 + z' }-> if(1, 0, 1 + s1) :|: s1 >= 0, s1 <= z' - 1, z' - 1 >= 0, z = 0 982.69/291.54 bitIter(z, z') -{ 3 }-> if(0, 1 + (z - 1), 0) :|: z - 1 >= 0, z' = 0 982.69/291.54 bitIter(z, z') -{ 3 + z' }-> if(0, 1 + (z - 1), 1 + s2) :|: s2 >= 0, s2 <= z' - 1, z' - 1 >= 0, z - 1 >= 0 982.69/291.54 bits(z) -{ 1 }-> bitIter(z, 0) :|: z >= 0 982.69/291.54 half(z) -{ 1 }-> 0 :|: z = 0 982.69/291.54 half(z) -{ 1 }-> 0 :|: z = 1 + 0 982.69/291.54 half(z) -{ 1 + z }-> 1 + s :|: s >= 0, s <= z - 2, z - 2 >= 0 982.69/291.54 if(z, z', z'') -{ 2 }-> bitIter(0, z'') :|: z'' >= 0, z = 0, z' = 0 982.69/291.54 if(z, z', z'') -{ 2 }-> bitIter(0, z'') :|: z'' >= 0, z' = 1 + 0, z = 0 982.69/291.54 if(z, z', z'') -{ 2 + z' }-> bitIter(1 + s', z'') :|: s' >= 0, s' <= z' - 2, z'' >= 0, z = 0, z' - 2 >= 0 982.69/291.54 if(z, z', z'') -{ 2 }-> 0 :|: z = 1, z' >= 0, z'' >= 0, z'' = 0 982.69/291.54 if(z, z', z'') -{ 2 }-> z'' - 1 :|: z = 1, z' >= 0, z'' >= 0, z'' - 1 >= 0 982.69/291.54 inc(z) -{ 1 }-> 0 :|: z = 0 982.69/291.54 inc(z) -{ 1 + z }-> 1 + s'' :|: s'' >= 0, s'' <= z - 1, z - 1 >= 0 982.69/291.54 p(z) -{ 1 }-> 0 :|: z = 0 982.69/291.54 p(z) -{ 1 }-> z - 1 :|: z - 1 >= 0 982.69/291.54 zero(z) -{ 1 }-> 1 :|: z = 0 982.69/291.54 zero(z) -{ 1 }-> 0 :|: z - 1 >= 0 982.69/291.54 982.69/291.54 Function symbols to be analyzed: {bits} 982.69/291.54 Previous analysis results are: 982.69/291.54 half: runtime: O(n^1) [2 + z], size: O(n^1) [z] 982.69/291.54 inc: runtime: O(n^1) [1 + z], size: O(n^1) [z] 982.69/291.54 zero: runtime: O(1) [1], size: O(1) [1] 982.69/291.54 p: runtime: O(1) [1], size: O(n^1) [z] 982.69/291.54 if: runtime: O(n^2) [12 + 7*z' + z'*z'' + z'^2 + 2*z''], size: O(n^1) [z''] 982.69/291.54 bitIter: runtime: O(n^2) [60 + 14*z + z*z' + 2*z^2 + 6*z'], size: O(n^1) [z'] 982.69/291.54 982.69/291.54 ---------------------------------------- 982.69/291.54 982.69/291.54 (47) ResultPropagationProof (UPPER BOUND(ID)) 982.69/291.54 Applied inner abstraction using the recently inferred runtime/size bounds where possible. 982.69/291.54 ---------------------------------------- 982.69/291.54 982.69/291.54 (48) 982.69/291.54 Obligation: 982.69/291.54 Complexity RNTS consisting of the following rules: 982.69/291.54 982.69/291.54 bitIter(z, z') -{ 15 }-> s4 :|: s4 >= 0, s4 <= 0, z = 0, z' = 0 982.69/291.54 bitIter(z, z') -{ 17 + 2*s1 + z' }-> s5 :|: s5 >= 0, s5 <= 1 + s1, s1 >= 0, s1 <= z' - 1, z' - 1 >= 0, z = 0 982.69/291.54 bitIter(z, z') -{ 15 + 7*z + z^2 }-> s6 :|: s6 >= 0, s6 <= 0, z - 1 >= 0, z' = 0 982.69/291.54 bitIter(z, z') -{ 17 + 2*s2 + s2*z + 8*z + z^2 + z' }-> s7 :|: s7 >= 0, s7 <= 1 + s2, s2 >= 0, s2 <= z' - 1, z' - 1 >= 0, z - 1 >= 0 982.69/291.54 bits(z) -{ 61 + 14*z + 2*z^2 }-> s3 :|: s3 >= 0, s3 <= 0, z >= 0 982.69/291.54 half(z) -{ 1 }-> 0 :|: z = 0 982.69/291.54 half(z) -{ 1 }-> 0 :|: z = 1 + 0 982.69/291.54 half(z) -{ 1 + z }-> 1 + s :|: s >= 0, s <= z - 2, z - 2 >= 0 982.69/291.54 if(z, z', z'') -{ 78 + 18*s' + s'*z'' + 2*s'^2 + z' + 7*z'' }-> s10 :|: s10 >= 0, s10 <= z'', s' >= 0, s' <= z' - 2, z'' >= 0, z = 0, z' - 2 >= 0 982.69/291.54 if(z, z', z'') -{ 62 + 6*z'' }-> s8 :|: s8 >= 0, s8 <= z'', z'' >= 0, z = 0, z' = 0 982.69/291.54 if(z, z', z'') -{ 62 + 6*z'' }-> s9 :|: s9 >= 0, s9 <= z'', z'' >= 0, z' = 1 + 0, z = 0 982.69/291.54 if(z, z', z'') -{ 2 }-> 0 :|: z = 1, z' >= 0, z'' >= 0, z'' = 0 982.69/291.54 if(z, z', z'') -{ 2 }-> z'' - 1 :|: z = 1, z' >= 0, z'' >= 0, z'' - 1 >= 0 982.69/291.54 inc(z) -{ 1 }-> 0 :|: z = 0 982.69/291.54 inc(z) -{ 1 + z }-> 1 + s'' :|: s'' >= 0, s'' <= z - 1, z - 1 >= 0 982.69/291.54 p(z) -{ 1 }-> 0 :|: z = 0 982.69/291.54 p(z) -{ 1 }-> z - 1 :|: z - 1 >= 0 982.69/291.54 zero(z) -{ 1 }-> 1 :|: z = 0 982.69/291.54 zero(z) -{ 1 }-> 0 :|: z - 1 >= 0 982.69/291.54 982.69/291.54 Function symbols to be analyzed: {bits} 982.69/291.54 Previous analysis results are: 982.69/291.54 half: runtime: O(n^1) [2 + z], size: O(n^1) [z] 982.69/291.54 inc: runtime: O(n^1) [1 + z], size: O(n^1) [z] 982.69/291.54 zero: runtime: O(1) [1], size: O(1) [1] 982.69/291.54 p: runtime: O(1) [1], size: O(n^1) [z] 982.69/291.54 if: runtime: O(n^2) [12 + 7*z' + z'*z'' + z'^2 + 2*z''], size: O(n^1) [z''] 982.69/291.54 bitIter: runtime: O(n^2) [60 + 14*z + z*z' + 2*z^2 + 6*z'], size: O(n^1) [z'] 982.69/291.54 982.69/291.54 ---------------------------------------- 982.69/291.54 982.69/291.54 (49) IntTrsBoundProof (UPPER BOUND(ID)) 982.69/291.54 982.69/291.54 Computed SIZE bound using CoFloCo for: bits 982.69/291.54 after applying outer abstraction to obtain an ITS, 982.69/291.54 resulting in: O(1) with polynomial bound: 0 982.69/291.54 982.69/291.54 ---------------------------------------- 982.69/291.54 982.69/291.54 (50) 982.69/291.54 Obligation: 982.69/291.54 Complexity RNTS consisting of the following rules: 982.69/291.54 982.69/291.54 bitIter(z, z') -{ 15 }-> s4 :|: s4 >= 0, s4 <= 0, z = 0, z' = 0 982.69/291.54 bitIter(z, z') -{ 17 + 2*s1 + z' }-> s5 :|: s5 >= 0, s5 <= 1 + s1, s1 >= 0, s1 <= z' - 1, z' - 1 >= 0, z = 0 982.69/291.54 bitIter(z, z') -{ 15 + 7*z + z^2 }-> s6 :|: s6 >= 0, s6 <= 0, z - 1 >= 0, z' = 0 982.69/291.54 bitIter(z, z') -{ 17 + 2*s2 + s2*z + 8*z + z^2 + z' }-> s7 :|: s7 >= 0, s7 <= 1 + s2, s2 >= 0, s2 <= z' - 1, z' - 1 >= 0, z - 1 >= 0 982.69/291.54 bits(z) -{ 61 + 14*z + 2*z^2 }-> s3 :|: s3 >= 0, s3 <= 0, z >= 0 982.69/291.54 half(z) -{ 1 }-> 0 :|: z = 0 982.69/291.54 half(z) -{ 1 }-> 0 :|: z = 1 + 0 982.69/291.54 half(z) -{ 1 + z }-> 1 + s :|: s >= 0, s <= z - 2, z - 2 >= 0 982.69/291.54 if(z, z', z'') -{ 78 + 18*s' + s'*z'' + 2*s'^2 + z' + 7*z'' }-> s10 :|: s10 >= 0, s10 <= z'', s' >= 0, s' <= z' - 2, z'' >= 0, z = 0, z' - 2 >= 0 982.69/291.54 if(z, z', z'') -{ 62 + 6*z'' }-> s8 :|: s8 >= 0, s8 <= z'', z'' >= 0, z = 0, z' = 0 982.69/291.54 if(z, z', z'') -{ 62 + 6*z'' }-> s9 :|: s9 >= 0, s9 <= z'', z'' >= 0, z' = 1 + 0, z = 0 982.69/291.54 if(z, z', z'') -{ 2 }-> 0 :|: z = 1, z' >= 0, z'' >= 0, z'' = 0 982.69/291.54 if(z, z', z'') -{ 2 }-> z'' - 1 :|: z = 1, z' >= 0, z'' >= 0, z'' - 1 >= 0 982.69/291.54 inc(z) -{ 1 }-> 0 :|: z = 0 982.69/291.54 inc(z) -{ 1 + z }-> 1 + s'' :|: s'' >= 0, s'' <= z - 1, z - 1 >= 0 982.69/291.54 p(z) -{ 1 }-> 0 :|: z = 0 982.69/291.54 p(z) -{ 1 }-> z - 1 :|: z - 1 >= 0 982.69/291.54 zero(z) -{ 1 }-> 1 :|: z = 0 982.69/291.54 zero(z) -{ 1 }-> 0 :|: z - 1 >= 0 982.69/291.54 982.69/291.54 Function symbols to be analyzed: {bits} 982.69/291.54 Previous analysis results are: 982.69/291.54 half: runtime: O(n^1) [2 + z], size: O(n^1) [z] 982.69/291.54 inc: runtime: O(n^1) [1 + z], size: O(n^1) [z] 982.69/291.54 zero: runtime: O(1) [1], size: O(1) [1] 982.69/291.54 p: runtime: O(1) [1], size: O(n^1) [z] 982.69/291.54 if: runtime: O(n^2) [12 + 7*z' + z'*z'' + z'^2 + 2*z''], size: O(n^1) [z''] 982.69/291.54 bitIter: runtime: O(n^2) [60 + 14*z + z*z' + 2*z^2 + 6*z'], size: O(n^1) [z'] 982.69/291.54 bits: runtime: ?, size: O(1) [0] 982.69/291.54 982.69/291.54 ---------------------------------------- 982.69/291.54 982.69/291.54 (51) IntTrsBoundProof (UPPER BOUND(ID)) 982.69/291.54 982.69/291.54 Computed RUNTIME bound using KoAT for: bits 982.69/291.54 after applying outer abstraction to obtain an ITS, 982.69/291.54 resulting in: O(n^2) with polynomial bound: 61 + 14*z + 2*z^2 982.69/291.54 982.69/291.54 ---------------------------------------- 982.69/291.54 982.69/291.54 (52) 982.69/291.54 Obligation: 982.69/291.54 Complexity RNTS consisting of the following rules: 982.69/291.54 982.69/291.54 bitIter(z, z') -{ 15 }-> s4 :|: s4 >= 0, s4 <= 0, z = 0, z' = 0 982.69/291.54 bitIter(z, z') -{ 17 + 2*s1 + z' }-> s5 :|: s5 >= 0, s5 <= 1 + s1, s1 >= 0, s1 <= z' - 1, z' - 1 >= 0, z = 0 982.69/291.54 bitIter(z, z') -{ 15 + 7*z + z^2 }-> s6 :|: s6 >= 0, s6 <= 0, z - 1 >= 0, z' = 0 982.69/291.54 bitIter(z, z') -{ 17 + 2*s2 + s2*z + 8*z + z^2 + z' }-> s7 :|: s7 >= 0, s7 <= 1 + s2, s2 >= 0, s2 <= z' - 1, z' - 1 >= 0, z - 1 >= 0 982.69/291.54 bits(z) -{ 61 + 14*z + 2*z^2 }-> s3 :|: s3 >= 0, s3 <= 0, z >= 0 982.69/291.54 half(z) -{ 1 }-> 0 :|: z = 0 982.69/291.54 half(z) -{ 1 }-> 0 :|: z = 1 + 0 982.69/291.54 half(z) -{ 1 + z }-> 1 + s :|: s >= 0, s <= z - 2, z - 2 >= 0 982.69/291.54 if(z, z', z'') -{ 78 + 18*s' + s'*z'' + 2*s'^2 + z' + 7*z'' }-> s10 :|: s10 >= 0, s10 <= z'', s' >= 0, s' <= z' - 2, z'' >= 0, z = 0, z' - 2 >= 0 982.69/291.54 if(z, z', z'') -{ 62 + 6*z'' }-> s8 :|: s8 >= 0, s8 <= z'', z'' >= 0, z = 0, z' = 0 982.69/291.54 if(z, z', z'') -{ 62 + 6*z'' }-> s9 :|: s9 >= 0, s9 <= z'', z'' >= 0, z' = 1 + 0, z = 0 982.69/291.54 if(z, z', z'') -{ 2 }-> 0 :|: z = 1, z' >= 0, z'' >= 0, z'' = 0 982.69/291.54 if(z, z', z'') -{ 2 }-> z'' - 1 :|: z = 1, z' >= 0, z'' >= 0, z'' - 1 >= 0 982.69/291.54 inc(z) -{ 1 }-> 0 :|: z = 0 982.69/291.54 inc(z) -{ 1 + z }-> 1 + s'' :|: s'' >= 0, s'' <= z - 1, z - 1 >= 0 982.69/291.54 p(z) -{ 1 }-> 0 :|: z = 0 982.69/291.54 p(z) -{ 1 }-> z - 1 :|: z - 1 >= 0 982.69/291.54 zero(z) -{ 1 }-> 1 :|: z = 0 982.69/291.54 zero(z) -{ 1 }-> 0 :|: z - 1 >= 0 982.69/291.54 982.69/291.54 Function symbols to be analyzed: 982.69/291.54 Previous analysis results are: 982.69/291.54 half: runtime: O(n^1) [2 + z], size: O(n^1) [z] 982.69/291.54 inc: runtime: O(n^1) [1 + z], size: O(n^1) [z] 982.69/291.54 zero: runtime: O(1) [1], size: O(1) [1] 982.69/291.54 p: runtime: O(1) [1], size: O(n^1) [z] 982.69/291.54 if: runtime: O(n^2) [12 + 7*z' + z'*z'' + z'^2 + 2*z''], size: O(n^1) [z''] 982.69/291.54 bitIter: runtime: O(n^2) [60 + 14*z + z*z' + 2*z^2 + 6*z'], size: O(n^1) [z'] 982.69/291.54 bits: runtime: O(n^2) [61 + 14*z + 2*z^2], size: O(1) [0] 982.69/291.54 982.69/291.54 ---------------------------------------- 982.69/291.54 982.69/291.54 (53) FinalProof (FINISHED) 982.69/291.54 Computed overall runtime complexity 982.69/291.54 ---------------------------------------- 982.69/291.54 982.69/291.54 (54) 982.69/291.54 BOUNDS(1, n^2) 982.69/291.54 982.69/291.54 ---------------------------------------- 982.69/291.54 982.69/291.54 (55) RelTrsToDecreasingLoopProblemProof (LOWER BOUND(ID)) 982.69/291.54 Transformed a relative TRS into a decreasing-loop problem. 982.69/291.54 ---------------------------------------- 982.69/291.54 982.69/291.54 (56) 982.69/291.54 Obligation: 982.69/291.54 Analyzing the following TRS for decreasing loops: 982.69/291.54 982.69/291.54 The Runtime Complexity (innermost) of the given CpxTRS could be proven to be BOUNDS(n^1, n^2). 982.69/291.54 982.69/291.54 982.69/291.54 The TRS R consists of the following rules: 982.69/291.54 982.69/291.54 half(0) -> 0 982.69/291.54 half(s(0)) -> 0 982.69/291.54 half(s(s(x))) -> s(half(x)) 982.69/291.54 inc(0) -> 0 982.69/291.54 inc(s(x)) -> s(inc(x)) 982.69/291.54 zero(0) -> true 982.69/291.54 zero(s(x)) -> false 982.69/291.54 p(0) -> 0 982.69/291.54 p(s(x)) -> x 982.69/291.54 bits(x) -> bitIter(x, 0) 982.69/291.54 bitIter(x, y) -> if(zero(x), x, inc(y)) 982.69/291.54 if(true, x, y) -> p(y) 982.69/291.54 if(false, x, y) -> bitIter(half(x), y) 982.69/291.54 982.69/291.54 S is empty. 982.69/291.54 Rewrite Strategy: INNERMOST 982.69/291.54 ---------------------------------------- 982.69/291.54 982.69/291.54 (57) DecreasingLoopProof (LOWER BOUND(ID)) 982.69/291.54 The following loop(s) give(s) rise to the lower bound Omega(n^1): 982.69/291.54 982.69/291.54 The rewrite sequence 982.69/291.54 982.69/291.54 half(s(s(x))) ->^+ s(half(x)) 982.69/291.54 982.69/291.54 gives rise to a decreasing loop by considering the right hand sides subterm at position [0]. 982.69/291.54 982.69/291.54 The pumping substitution is [x / s(s(x))]. 982.69/291.54 982.69/291.54 The result substitution is [ ]. 982.69/291.54 982.69/291.54 982.69/291.54 982.69/291.54 982.69/291.54 ---------------------------------------- 982.69/291.54 982.69/291.54 (58) 982.69/291.54 Complex Obligation (BEST) 982.69/291.54 982.69/291.54 ---------------------------------------- 982.69/291.54 982.69/291.54 (59) 982.69/291.54 Obligation: 982.69/291.54 Proved the lower bound n^1 for the following obligation: 982.69/291.54 982.69/291.54 The Runtime Complexity (innermost) of the given CpxTRS could be proven to be BOUNDS(n^1, n^2). 982.69/291.54 982.69/291.54 982.69/291.54 The TRS R consists of the following rules: 982.69/291.54 982.69/291.54 half(0) -> 0 982.69/291.54 half(s(0)) -> 0 982.69/291.54 half(s(s(x))) -> s(half(x)) 982.69/291.54 inc(0) -> 0 982.69/291.54 inc(s(x)) -> s(inc(x)) 982.69/291.54 zero(0) -> true 982.69/291.54 zero(s(x)) -> false 982.69/291.54 p(0) -> 0 982.69/291.54 p(s(x)) -> x 982.69/291.54 bits(x) -> bitIter(x, 0) 982.69/291.54 bitIter(x, y) -> if(zero(x), x, inc(y)) 982.69/291.54 if(true, x, y) -> p(y) 982.69/291.54 if(false, x, y) -> bitIter(half(x), y) 982.69/291.54 982.69/291.54 S is empty. 982.69/291.54 Rewrite Strategy: INNERMOST 982.69/291.54 ---------------------------------------- 982.69/291.54 982.69/291.54 (60) LowerBoundPropagationProof (FINISHED) 982.69/291.54 Propagated lower bound. 982.69/291.54 ---------------------------------------- 982.69/291.54 982.69/291.54 (61) 982.69/291.54 BOUNDS(n^1, INF) 982.69/291.54 982.69/291.54 ---------------------------------------- 982.69/291.54 982.69/291.54 (62) 982.69/291.54 Obligation: 982.69/291.54 Analyzing the following TRS for decreasing loops: 982.69/291.54 982.69/291.54 The Runtime Complexity (innermost) of the given CpxTRS could be proven to be BOUNDS(n^1, n^2). 982.69/291.54 982.69/291.54 982.69/291.54 The TRS R consists of the following rules: 982.69/291.54 982.69/291.54 half(0) -> 0 982.69/291.54 half(s(0)) -> 0 982.69/291.54 half(s(s(x))) -> s(half(x)) 982.69/291.54 inc(0) -> 0 982.69/291.54 inc(s(x)) -> s(inc(x)) 982.69/291.54 zero(0) -> true 982.69/291.54 zero(s(x)) -> false 982.69/291.54 p(0) -> 0 982.69/291.54 p(s(x)) -> x 982.69/291.54 bits(x) -> bitIter(x, 0) 982.69/291.54 bitIter(x, y) -> if(zero(x), x, inc(y)) 982.69/291.54 if(true, x, y) -> p(y) 982.69/291.54 if(false, x, y) -> bitIter(half(x), y) 982.69/291.54 982.69/291.54 S is empty. 982.69/291.54 Rewrite Strategy: INNERMOST 982.69/291.58 EOF