1143.13/291.51 WORST_CASE(Omega(n^1), O(n^2)) 1159.94/295.76 proof of /export/starexec/sandbox/benchmark/theBenchmark.xml 1159.94/295.76 # AProVE Commit ID: 48fb2092695e11cc9f56e44b17a92a5f88ffb256 marcel 20180622 unpublished dirty 1159.94/295.76 1159.94/295.76 1159.94/295.76 The Runtime Complexity (innermost) of the given CpxTRS could be proven to be BOUNDS(n^1, n^2). 1159.94/295.76 1159.94/295.76 (0) CpxTRS 1159.94/295.76 (1) RelTrsToWeightedTrsProof [BOTH BOUNDS(ID, ID), 0 ms] 1159.94/295.76 (2) CpxWeightedTrs 1159.94/295.76 (3) TypeInferenceProof [BOTH BOUNDS(ID, ID), 0 ms] 1159.94/295.76 (4) CpxTypedWeightedTrs 1159.94/295.76 (5) CompletionProof [UPPER BOUND(ID), 0 ms] 1159.94/295.76 (6) CpxTypedWeightedCompleteTrs 1159.94/295.76 (7) NarrowingProof [BOTH BOUNDS(ID, ID), 0 ms] 1159.94/295.76 (8) CpxTypedWeightedCompleteTrs 1159.94/295.76 (9) CpxTypedWeightedTrsToRntsProof [UPPER BOUND(ID), 7 ms] 1159.94/295.76 (10) CpxRNTS 1159.94/295.76 (11) InliningProof [UPPER BOUND(ID), 630 ms] 1159.94/295.76 (12) CpxRNTS 1159.94/295.76 (13) SimplificationProof [BOTH BOUNDS(ID, ID), 0 ms] 1159.94/295.76 (14) CpxRNTS 1159.94/295.76 (15) CpxRntsAnalysisOrderProof [BOTH BOUNDS(ID, ID), 0 ms] 1159.94/295.76 (16) CpxRNTS 1159.94/295.76 (17) ResultPropagationProof [UPPER BOUND(ID), 0 ms] 1159.94/295.76 (18) CpxRNTS 1159.94/295.76 (19) IntTrsBoundProof [UPPER BOUND(ID), 102 ms] 1159.94/295.76 (20) CpxRNTS 1159.94/295.76 (21) IntTrsBoundProof [UPPER BOUND(ID), 6 ms] 1159.94/295.76 (22) CpxRNTS 1159.94/295.76 (23) ResultPropagationProof [UPPER BOUND(ID), 0 ms] 1159.94/295.76 (24) CpxRNTS 1159.94/295.76 (25) IntTrsBoundProof [UPPER BOUND(ID), 324 ms] 1159.94/295.76 (26) CpxRNTS 1159.94/295.76 (27) IntTrsBoundProof [UPPER BOUND(ID), 176 ms] 1159.94/295.76 (28) CpxRNTS 1159.94/295.76 (29) ResultPropagationProof [UPPER BOUND(ID), 0 ms] 1159.94/295.76 (30) CpxRNTS 1159.94/295.76 (31) IntTrsBoundProof [UPPER BOUND(ID), 255 ms] 1159.94/295.76 (32) CpxRNTS 1159.94/295.76 (33) IntTrsBoundProof [UPPER BOUND(ID), 85 ms] 1159.94/295.76 (34) CpxRNTS 1159.94/295.76 (35) ResultPropagationProof [UPPER BOUND(ID), 0 ms] 1159.94/295.76 (36) CpxRNTS 1159.94/295.76 (37) IntTrsBoundProof [UPPER BOUND(ID), 5112 ms] 1159.94/295.76 (38) CpxRNTS 1159.94/295.76 (39) IntTrsBoundProof [UPPER BOUND(ID), 2087 ms] 1159.94/295.76 (40) CpxRNTS 1159.94/295.76 (41) FinalProof [FINISHED, 0 ms] 1159.94/295.76 (42) BOUNDS(1, n^2) 1159.94/295.76 (43) RelTrsToDecreasingLoopProblemProof [LOWER BOUND(ID), 0 ms] 1159.94/295.76 (44) TRS for Loop Detection 1159.94/295.76 (45) DecreasingLoopProof [LOWER BOUND(ID), 0 ms] 1159.94/295.76 (46) BEST 1159.94/295.76 (47) proven lower bound 1159.94/295.76 (48) LowerBoundPropagationProof [FINISHED, 0 ms] 1159.94/295.76 (49) BOUNDS(n^1, INF) 1159.94/295.76 (50) TRS for Loop Detection 1159.94/295.76 1159.94/295.76 1159.94/295.76 ---------------------------------------- 1159.94/295.76 1159.94/295.76 (0) 1159.94/295.76 Obligation: 1159.94/295.76 The Runtime Complexity (innermost) of the given CpxTRS could be proven to be BOUNDS(n^1, n^2). 1159.94/295.76 1159.94/295.76 1159.94/295.76 The TRS R consists of the following rules: 1159.94/295.76 1159.94/295.76 cond1(true, x, y, z) -> cond2(gr(x, 0), x, y, z) 1159.94/295.76 cond2(true, x, y, z) -> cond1(or(gr(x, z), gr(y, z)), p(x), y, z) 1159.94/295.76 cond2(false, x, y, z) -> cond3(gr(y, 0), x, y, z) 1159.94/295.76 cond3(true, x, y, z) -> cond1(or(gr(x, z), gr(y, z)), x, p(y), z) 1159.94/295.76 cond3(false, x, y, z) -> cond1(or(gr(x, z), gr(y, z)), x, y, z) 1159.94/295.76 gr(0, x) -> false 1159.94/295.76 gr(s(x), 0) -> true 1159.94/295.76 gr(s(x), s(y)) -> gr(x, y) 1159.94/295.76 or(false, false) -> false 1159.94/295.76 or(true, x) -> true 1159.94/295.76 or(x, true) -> true 1159.94/295.76 p(0) -> 0 1159.94/295.76 p(s(x)) -> x 1159.94/295.76 1159.94/295.76 S is empty. 1159.94/295.76 Rewrite Strategy: INNERMOST 1159.94/295.76 ---------------------------------------- 1159.94/295.76 1159.94/295.76 (1) RelTrsToWeightedTrsProof (BOTH BOUNDS(ID, ID)) 1159.94/295.76 Transformed relative TRS to weighted TRS 1159.94/295.76 ---------------------------------------- 1159.94/295.76 1159.94/295.76 (2) 1159.94/295.76 Obligation: 1159.94/295.76 The Runtime Complexity (innermost) of the given CpxWeightedTrs could be proven to be BOUNDS(1, n^2). 1159.94/295.76 1159.94/295.76 1159.94/295.76 The TRS R consists of the following rules: 1159.94/295.76 1159.94/295.76 cond1(true, x, y, z) -> cond2(gr(x, 0), x, y, z) [1] 1159.94/295.76 cond2(true, x, y, z) -> cond1(or(gr(x, z), gr(y, z)), p(x), y, z) [1] 1159.94/295.76 cond2(false, x, y, z) -> cond3(gr(y, 0), x, y, z) [1] 1159.94/295.76 cond3(true, x, y, z) -> cond1(or(gr(x, z), gr(y, z)), x, p(y), z) [1] 1159.94/295.76 cond3(false, x, y, z) -> cond1(or(gr(x, z), gr(y, z)), x, y, z) [1] 1159.94/295.76 gr(0, x) -> false [1] 1159.94/295.76 gr(s(x), 0) -> true [1] 1159.94/295.76 gr(s(x), s(y)) -> gr(x, y) [1] 1159.94/295.76 or(false, false) -> false [1] 1159.94/295.76 or(true, x) -> true [1] 1159.94/295.76 or(x, true) -> true [1] 1159.94/295.76 p(0) -> 0 [1] 1159.94/295.76 p(s(x)) -> x [1] 1159.94/295.76 1159.94/295.76 Rewrite Strategy: INNERMOST 1159.94/295.76 ---------------------------------------- 1159.94/295.76 1159.94/295.76 (3) TypeInferenceProof (BOTH BOUNDS(ID, ID)) 1159.94/295.76 Infered types. 1159.94/295.76 ---------------------------------------- 1159.94/295.76 1159.94/295.76 (4) 1159.94/295.76 Obligation: 1159.94/295.76 Runtime Complexity Weighted TRS with Types. 1159.94/295.76 The TRS R consists of the following rules: 1159.94/295.76 1159.94/295.76 cond1(true, x, y, z) -> cond2(gr(x, 0), x, y, z) [1] 1159.94/295.76 cond2(true, x, y, z) -> cond1(or(gr(x, z), gr(y, z)), p(x), y, z) [1] 1159.94/295.76 cond2(false, x, y, z) -> cond3(gr(y, 0), x, y, z) [1] 1159.94/295.76 cond3(true, x, y, z) -> cond1(or(gr(x, z), gr(y, z)), x, p(y), z) [1] 1159.94/295.76 cond3(false, x, y, z) -> cond1(or(gr(x, z), gr(y, z)), x, y, z) [1] 1159.94/295.76 gr(0, x) -> false [1] 1159.94/295.76 gr(s(x), 0) -> true [1] 1159.94/295.76 gr(s(x), s(y)) -> gr(x, y) [1] 1159.94/295.76 or(false, false) -> false [1] 1159.94/295.76 or(true, x) -> true [1] 1159.94/295.76 or(x, true) -> true [1] 1159.94/295.76 p(0) -> 0 [1] 1159.94/295.76 p(s(x)) -> x [1] 1159.94/295.76 1159.94/295.76 The TRS has the following type information: 1159.94/295.76 cond1 :: true:false -> 0:s -> 0:s -> 0:s -> cond1:cond2:cond3 1159.94/295.76 true :: true:false 1159.94/295.76 cond2 :: true:false -> 0:s -> 0:s -> 0:s -> cond1:cond2:cond3 1159.94/295.76 gr :: 0:s -> 0:s -> true:false 1159.94/295.76 0 :: 0:s 1159.94/295.76 or :: true:false -> true:false -> true:false 1159.94/295.76 p :: 0:s -> 0:s 1159.94/295.76 false :: true:false 1159.94/295.76 cond3 :: true:false -> 0:s -> 0:s -> 0:s -> cond1:cond2:cond3 1159.94/295.76 s :: 0:s -> 0:s 1159.94/295.76 1159.94/295.76 Rewrite Strategy: INNERMOST 1159.94/295.76 ---------------------------------------- 1159.94/295.76 1159.94/295.76 (5) CompletionProof (UPPER BOUND(ID)) 1159.94/295.76 The transformation into a RNTS is sound, since: 1159.94/295.76 1159.94/295.76 (a) The obligation is a constructor system where every type has a constant constructor, 1159.94/295.76 1159.94/295.76 (b) The following defined symbols do not have to be completely defined, as they can never occur inside other defined symbols: 1159.94/295.76 1159.94/295.76 cond1_4 1159.94/295.76 cond2_4 1159.94/295.76 cond3_4 1159.94/295.76 1159.94/295.76 (c) The following functions are completely defined: 1159.94/295.76 1159.94/295.76 or_2 1159.94/295.76 gr_2 1159.94/295.76 p_1 1159.94/295.76 1159.94/295.76 Due to the following rules being added: 1159.94/295.76 none 1159.94/295.76 1159.94/295.76 And the following fresh constants: const 1159.94/295.76 1159.94/295.76 ---------------------------------------- 1159.94/295.76 1159.94/295.76 (6) 1159.94/295.76 Obligation: 1159.94/295.76 Runtime Complexity Weighted TRS where critical functions are completely defined. The underlying TRS is: 1159.94/295.76 1159.94/295.76 Runtime Complexity Weighted TRS with Types. 1159.94/295.76 The TRS R consists of the following rules: 1159.94/295.76 1159.94/295.76 cond1(true, x, y, z) -> cond2(gr(x, 0), x, y, z) [1] 1159.94/295.76 cond2(true, x, y, z) -> cond1(or(gr(x, z), gr(y, z)), p(x), y, z) [1] 1159.94/295.76 cond2(false, x, y, z) -> cond3(gr(y, 0), x, y, z) [1] 1159.94/295.76 cond3(true, x, y, z) -> cond1(or(gr(x, z), gr(y, z)), x, p(y), z) [1] 1159.94/295.76 cond3(false, x, y, z) -> cond1(or(gr(x, z), gr(y, z)), x, y, z) [1] 1159.94/295.76 gr(0, x) -> false [1] 1159.94/295.76 gr(s(x), 0) -> true [1] 1159.94/295.76 gr(s(x), s(y)) -> gr(x, y) [1] 1159.94/295.76 or(false, false) -> false [1] 1159.94/295.76 or(true, x) -> true [1] 1159.94/295.76 or(x, true) -> true [1] 1159.94/295.76 p(0) -> 0 [1] 1159.94/295.76 p(s(x)) -> x [1] 1159.94/295.76 1159.94/295.76 The TRS has the following type information: 1159.94/295.76 cond1 :: true:false -> 0:s -> 0:s -> 0:s -> cond1:cond2:cond3 1159.94/295.76 true :: true:false 1159.94/295.76 cond2 :: true:false -> 0:s -> 0:s -> 0:s -> cond1:cond2:cond3 1159.94/295.76 gr :: 0:s -> 0:s -> true:false 1159.94/295.76 0 :: 0:s 1159.94/295.76 or :: true:false -> true:false -> true:false 1159.94/295.76 p :: 0:s -> 0:s 1159.94/295.76 false :: true:false 1159.94/295.76 cond3 :: true:false -> 0:s -> 0:s -> 0:s -> cond1:cond2:cond3 1159.94/295.76 s :: 0:s -> 0:s 1159.94/295.76 const :: cond1:cond2:cond3 1159.94/295.76 1159.94/295.76 Rewrite Strategy: INNERMOST 1159.94/295.76 ---------------------------------------- 1159.94/295.76 1159.94/295.76 (7) NarrowingProof (BOTH BOUNDS(ID, ID)) 1159.94/295.76 Narrowed the inner basic terms of all right-hand sides by a single narrowing step. 1159.94/295.76 ---------------------------------------- 1159.94/295.76 1159.94/295.76 (8) 1159.94/295.76 Obligation: 1159.94/295.76 Runtime Complexity Weighted TRS where critical functions are completely defined. The underlying TRS is: 1159.94/295.76 1159.94/295.76 Runtime Complexity Weighted TRS with Types. 1159.94/295.76 The TRS R consists of the following rules: 1159.94/295.76 1159.94/295.76 cond1(true, 0, y, z) -> cond2(false, 0, y, z) [2] 1159.94/295.76 cond1(true, s(x'), y, z) -> cond2(true, s(x'), y, z) [2] 1159.94/295.76 cond2(true, 0, 0, z) -> cond1(or(false, false), 0, 0, z) [4] 1159.94/295.76 cond2(true, 0, s(x2), 0) -> cond1(or(false, true), 0, s(x2), 0) [4] 1159.94/295.76 cond2(true, 0, s(x3), s(y'')) -> cond1(or(false, gr(x3, y'')), 0, s(x3), s(y'')) [4] 1159.94/295.76 cond2(true, s(x''), 0, 0) -> cond1(or(true, false), x'', 0, 0) [4] 1159.94/295.76 cond2(true, s(x''), s(x4), 0) -> cond1(or(true, true), x'', s(x4), 0) [4] 1159.94/295.76 cond2(true, s(x1), 0, s(y')) -> cond1(or(gr(x1, y'), false), x1, 0, s(y')) [4] 1159.94/295.76 cond2(true, s(x1), s(x5), s(y')) -> cond1(or(gr(x1, y'), gr(x5, y')), x1, s(x5), s(y')) [4] 1159.94/295.76 cond2(false, x, 0, z) -> cond3(false, x, 0, z) [2] 1159.94/295.76 cond2(false, x, s(x6), z) -> cond3(true, x, s(x6), z) [2] 1159.94/295.76 cond3(true, 0, 0, z) -> cond1(or(false, false), 0, 0, z) [4] 1159.94/295.76 cond3(true, 0, s(x9), 0) -> cond1(or(false, true), 0, x9, 0) [4] 1159.94/295.76 cond3(true, 0, s(x10), s(y2)) -> cond1(or(false, gr(x10, y2)), 0, x10, s(y2)) [4] 1159.94/295.76 cond3(true, s(x7), 0, 0) -> cond1(or(true, false), s(x7), 0, 0) [4] 1159.94/295.76 cond3(true, s(x7), s(x11), 0) -> cond1(or(true, true), s(x7), x11, 0) [4] 1159.94/295.76 cond3(true, s(x8), 0, s(y1)) -> cond1(or(gr(x8, y1), false), s(x8), 0, s(y1)) [4] 1159.94/295.76 cond3(true, s(x8), s(x12), s(y1)) -> cond1(or(gr(x8, y1), gr(x12, y1)), s(x8), x12, s(y1)) [4] 1159.94/295.76 cond3(false, 0, 0, z) -> cond1(or(false, false), 0, 0, z) [3] 1159.94/295.76 cond3(false, 0, s(x15), 0) -> cond1(or(false, true), 0, s(x15), 0) [3] 1159.94/295.76 cond3(false, 0, s(x16), s(y4)) -> cond1(or(false, gr(x16, y4)), 0, s(x16), s(y4)) [3] 1159.94/295.76 cond3(false, s(x13), 0, 0) -> cond1(or(true, false), s(x13), 0, 0) [3] 1159.94/295.76 cond3(false, s(x13), s(x17), 0) -> cond1(or(true, true), s(x13), s(x17), 0) [3] 1159.94/295.76 cond3(false, s(x14), 0, s(y3)) -> cond1(or(gr(x14, y3), false), s(x14), 0, s(y3)) [3] 1159.94/295.76 cond3(false, s(x14), s(x18), s(y3)) -> cond1(or(gr(x14, y3), gr(x18, y3)), s(x14), s(x18), s(y3)) [3] 1159.94/295.76 gr(0, x) -> false [1] 1159.94/295.76 gr(s(x), 0) -> true [1] 1159.94/295.76 gr(s(x), s(y)) -> gr(x, y) [1] 1159.94/295.76 or(false, false) -> false [1] 1159.94/295.76 or(true, x) -> true [1] 1159.94/295.76 or(x, true) -> true [1] 1159.94/295.76 p(0) -> 0 [1] 1159.94/295.76 p(s(x)) -> x [1] 1159.94/295.76 1159.94/295.76 The TRS has the following type information: 1159.94/295.76 cond1 :: true:false -> 0:s -> 0:s -> 0:s -> cond1:cond2:cond3 1159.94/295.76 true :: true:false 1159.94/295.76 cond2 :: true:false -> 0:s -> 0:s -> 0:s -> cond1:cond2:cond3 1159.94/295.76 gr :: 0:s -> 0:s -> true:false 1159.94/295.76 0 :: 0:s 1159.94/295.76 or :: true:false -> true:false -> true:false 1159.94/295.76 p :: 0:s -> 0:s 1159.94/295.76 false :: true:false 1159.94/295.76 cond3 :: true:false -> 0:s -> 0:s -> 0:s -> cond1:cond2:cond3 1159.94/295.76 s :: 0:s -> 0:s 1159.94/295.76 const :: cond1:cond2:cond3 1159.94/295.76 1159.94/295.76 Rewrite Strategy: INNERMOST 1159.94/295.76 ---------------------------------------- 1159.94/295.76 1159.94/295.76 (9) CpxTypedWeightedTrsToRntsProof (UPPER BOUND(ID)) 1159.94/295.76 Transformed the TRS into an over-approximating RNTS by (improved) Size Abstraction. 1159.94/295.76 The constant constructors are abstracted as follows: 1159.94/295.76 1159.94/295.76 true => 1 1159.94/295.76 0 => 0 1159.94/295.76 false => 0 1159.94/295.76 const => 0 1159.94/295.76 1159.94/295.76 ---------------------------------------- 1159.94/295.76 1159.94/295.76 (10) 1159.94/295.76 Obligation: 1159.94/295.76 Complexity RNTS consisting of the following rules: 1159.94/295.76 1159.94/295.76 cond1(z', z'', z1, z2) -{ 2 }-> cond2(1, 1 + x', y, z) :|: z1 = y, z >= 0, z'' = 1 + x', z2 = z, x' >= 0, y >= 0, z' = 1 1159.94/295.76 cond1(z', z'', z1, z2) -{ 2 }-> cond2(0, 0, y, z) :|: z'' = 0, z1 = y, z >= 0, z2 = z, y >= 0, z' = 1 1159.94/295.76 cond2(z', z'', z1, z2) -{ 2 }-> cond3(1, x, 1 + x6, z) :|: z >= 0, z2 = z, x >= 0, x6 >= 0, z'' = x, z1 = 1 + x6, z' = 0 1159.94/295.76 cond2(z', z'', z1, z2) -{ 2 }-> cond3(0, x, 0, z) :|: z1 = 0, z >= 0, z2 = z, x >= 0, z'' = x, z' = 0 1159.94/295.76 cond2(z', z'', z1, z2) -{ 4 }-> cond1(or(gr(x1, y'), gr(x5, y')), x1, 1 + x5, 1 + y') :|: x1 >= 0, x5 >= 0, z'' = 1 + x1, y' >= 0, z2 = 1 + y', z' = 1, z1 = 1 + x5 1159.94/295.76 cond2(z', z'', z1, z2) -{ 4 }-> cond1(or(gr(x1, y'), 0), x1, 0, 1 + y') :|: z1 = 0, x1 >= 0, z'' = 1 + x1, y' >= 0, z2 = 1 + y', z' = 1 1159.94/295.76 cond2(z', z'', z1, z2) -{ 4 }-> cond1(or(1, 1), x'', 1 + x4, 0) :|: x4 >= 0, z2 = 0, z1 = 1 + x4, z' = 1, z'' = 1 + x'', x'' >= 0 1159.94/295.76 cond2(z', z'', z1, z2) -{ 4 }-> cond1(or(1, 0), x'', 0, 0) :|: z1 = 0, z2 = 0, z' = 1, z'' = 1 + x'', x'' >= 0 1159.94/295.76 cond2(z', z'', z1, z2) -{ 4 }-> cond1(or(0, gr(x3, y'')), 0, 1 + x3, 1 + y'') :|: z'' = 0, z2 = 1 + y'', y'' >= 0, z' = 1, z1 = 1 + x3, x3 >= 0 1159.94/295.76 cond2(z', z'', z1, z2) -{ 4 }-> cond1(or(0, 1), 0, 1 + x2, 0) :|: z'' = 0, z2 = 0, z' = 1, x2 >= 0, z1 = 1 + x2 1159.94/295.76 cond2(z', z'', z1, z2) -{ 4 }-> cond1(or(0, 0), 0, 0, z) :|: z'' = 0, z1 = 0, z >= 0, z2 = z, z' = 1 1159.94/295.76 cond3(z', z'', z1, z2) -{ 3 }-> cond1(or(gr(x14, y3), gr(x18, y3)), 1 + x14, 1 + x18, 1 + y3) :|: z1 = 1 + x18, z2 = 1 + y3, y3 >= 0, x14 >= 0, x18 >= 0, z'' = 1 + x14, z' = 0 1159.94/295.76 cond3(z', z'', z1, z2) -{ 3 }-> cond1(or(gr(x14, y3), 0), 1 + x14, 0, 1 + y3) :|: z1 = 0, z2 = 1 + y3, y3 >= 0, x14 >= 0, z'' = 1 + x14, z' = 0 1159.94/295.76 cond3(z', z'', z1, z2) -{ 4 }-> cond1(or(gr(x8, y1), gr(x12, y1)), 1 + x8, x12, 1 + y1) :|: y1 >= 0, z2 = 1 + y1, x8 >= 0, z1 = 1 + x12, x12 >= 0, z'' = 1 + x8, z' = 1 1159.94/295.76 cond3(z', z'', z1, z2) -{ 4 }-> cond1(or(gr(x8, y1), 0), 1 + x8, 0, 1 + y1) :|: y1 >= 0, z2 = 1 + y1, z1 = 0, x8 >= 0, z'' = 1 + x8, z' = 1 1159.94/295.76 cond3(z', z'', z1, z2) -{ 3 }-> cond1(or(1, 1), 1 + x13, 1 + x17, 0) :|: x13 >= 0, x17 >= 0, z1 = 1 + x17, z2 = 0, z'' = 1 + x13, z' = 0 1159.94/295.76 cond3(z', z'', z1, z2) -{ 4 }-> cond1(or(1, 1), 1 + x7, x11, 0) :|: z1 = 1 + x11, x7 >= 0, z2 = 0, z'' = 1 + x7, x11 >= 0, z' = 1 1159.94/295.76 cond3(z', z'', z1, z2) -{ 3 }-> cond1(or(1, 0), 1 + x13, 0, 0) :|: x13 >= 0, z1 = 0, z2 = 0, z'' = 1 + x13, z' = 0 1159.94/295.76 cond3(z', z'', z1, z2) -{ 4 }-> cond1(or(1, 0), 1 + x7, 0, 0) :|: z1 = 0, x7 >= 0, z2 = 0, z'' = 1 + x7, z' = 1 1159.94/295.76 cond3(z', z'', z1, z2) -{ 4 }-> cond1(or(0, gr(x10, y2)), 0, x10, 1 + y2) :|: z'' = 0, z2 = 1 + y2, z' = 1, z1 = 1 + x10, x10 >= 0, y2 >= 0 1159.94/295.76 cond3(z', z'', z1, z2) -{ 3 }-> cond1(or(0, gr(x16, y4)), 0, 1 + x16, 1 + y4) :|: z'' = 0, z1 = 1 + x16, z2 = 1 + y4, y4 >= 0, x16 >= 0, z' = 0 1159.94/295.76 cond3(z', z'', z1, z2) -{ 4 }-> cond1(or(0, 1), 0, x9, 0) :|: z'' = 0, z2 = 0, z1 = 1 + x9, z' = 1, x9 >= 0 1159.94/295.76 cond3(z', z'', z1, z2) -{ 3 }-> cond1(or(0, 1), 0, 1 + x15, 0) :|: z'' = 0, z1 = 1 + x15, z2 = 0, x15 >= 0, z' = 0 1159.94/295.76 cond3(z', z'', z1, z2) -{ 4 }-> cond1(or(0, 0), 0, 0, z) :|: z'' = 0, z1 = 0, z >= 0, z2 = z, z' = 1 1159.94/295.76 cond3(z', z'', z1, z2) -{ 3 }-> cond1(or(0, 0), 0, 0, z) :|: z'' = 0, z1 = 0, z >= 0, z2 = z, z' = 0 1159.94/295.76 gr(z', z'') -{ 1 }-> gr(x, y) :|: z' = 1 + x, x >= 0, y >= 0, z'' = 1 + y 1159.94/295.76 gr(z', z'') -{ 1 }-> 1 :|: z'' = 0, z' = 1 + x, x >= 0 1159.94/295.76 gr(z', z'') -{ 1 }-> 0 :|: x >= 0, z'' = x, z' = 0 1159.94/295.76 or(z', z'') -{ 1 }-> 1 :|: x >= 0, z'' = x, z' = 1 1159.94/295.76 or(z', z'') -{ 1 }-> 1 :|: z' = x, x >= 0, z'' = 1 1159.94/295.76 or(z', z'') -{ 1 }-> 0 :|: z'' = 0, z' = 0 1159.94/295.76 p(z') -{ 1 }-> x :|: z' = 1 + x, x >= 0 1159.94/295.76 p(z') -{ 1 }-> 0 :|: z' = 0 1159.94/295.76 1159.94/295.76 1159.94/295.76 ---------------------------------------- 1159.94/295.76 1159.94/295.76 (11) InliningProof (UPPER BOUND(ID)) 1159.94/295.76 Inlined the following terminating rules on right-hand sides where appropriate: 1159.94/295.76 1159.94/295.76 or(z', z'') -{ 1 }-> 0 :|: z'' = 0, z' = 0 1159.94/295.76 or(z', z'') -{ 1 }-> 1 :|: x >= 0, z'' = x, z' = 1 1159.94/295.76 or(z', z'') -{ 1 }-> 1 :|: z' = x, x >= 0, z'' = 1 1159.94/295.76 1159.94/295.76 ---------------------------------------- 1159.94/295.76 1159.94/295.76 (12) 1159.94/295.76 Obligation: 1159.94/295.76 Complexity RNTS consisting of the following rules: 1159.94/295.76 1159.94/295.76 cond1(z', z'', z1, z2) -{ 2 }-> cond2(1, 1 + x', y, z) :|: z1 = y, z >= 0, z'' = 1 + x', z2 = z, x' >= 0, y >= 0, z' = 1 1159.94/295.76 cond1(z', z'', z1, z2) -{ 2 }-> cond2(0, 0, y, z) :|: z'' = 0, z1 = y, z >= 0, z2 = z, y >= 0, z' = 1 1159.94/295.76 cond2(z', z'', z1, z2) -{ 2 }-> cond3(1, x, 1 + x6, z) :|: z >= 0, z2 = z, x >= 0, x6 >= 0, z'' = x, z1 = 1 + x6, z' = 0 1159.94/295.76 cond2(z', z'', z1, z2) -{ 2 }-> cond3(0, x, 0, z) :|: z1 = 0, z >= 0, z2 = z, x >= 0, z'' = x, z' = 0 1159.94/295.76 cond2(z', z'', z1, z2) -{ 4 }-> cond1(or(gr(x1, y'), gr(x5, y')), x1, 1 + x5, 1 + y') :|: x1 >= 0, x5 >= 0, z'' = 1 + x1, y' >= 0, z2 = 1 + y', z' = 1, z1 = 1 + x5 1159.94/295.76 cond2(z', z'', z1, z2) -{ 4 }-> cond1(or(gr(x1, y'), 0), x1, 0, 1 + y') :|: z1 = 0, x1 >= 0, z'' = 1 + x1, y' >= 0, z2 = 1 + y', z' = 1 1159.94/295.76 cond2(z', z'', z1, z2) -{ 4 }-> cond1(or(0, gr(x3, y'')), 0, 1 + x3, 1 + y'') :|: z'' = 0, z2 = 1 + y'', y'' >= 0, z' = 1, z1 = 1 + x3, x3 >= 0 1159.94/295.76 cond2(z', z'', z1, z2) -{ 5 }-> cond1(1, x'', 0, 0) :|: z1 = 0, z2 = 0, z' = 1, z'' = 1 + x'', x'' >= 0, x >= 0, 0 = x, 1 = 1 1159.94/295.76 cond2(z', z'', z1, z2) -{ 5 }-> cond1(1, x'', 1 + x4, 0) :|: x4 >= 0, z2 = 0, z1 = 1 + x4, z' = 1, z'' = 1 + x'', x'' >= 0, x >= 0, 1 = x, 1 = 1 1159.94/295.76 cond2(z', z'', z1, z2) -{ 5 }-> cond1(1, 0, 1 + x2, 0) :|: z'' = 0, z2 = 0, z' = 1, x2 >= 0, z1 = 1 + x2, 0 = x, x >= 0, 1 = 1 1159.94/295.76 cond2(z', z'', z1, z2) -{ 5 }-> cond1(0, 0, 0, z) :|: z'' = 0, z1 = 0, z >= 0, z2 = z, z' = 1, 0 = 0 1159.94/295.76 cond3(z', z'', z1, z2) -{ 3 }-> cond1(or(gr(x14, y3), gr(x18, y3)), 1 + x14, 1 + x18, 1 + y3) :|: z1 = 1 + x18, z2 = 1 + y3, y3 >= 0, x14 >= 0, x18 >= 0, z'' = 1 + x14, z' = 0 1159.94/295.76 cond3(z', z'', z1, z2) -{ 3 }-> cond1(or(gr(x14, y3), 0), 1 + x14, 0, 1 + y3) :|: z1 = 0, z2 = 1 + y3, y3 >= 0, x14 >= 0, z'' = 1 + x14, z' = 0 1159.94/295.76 cond3(z', z'', z1, z2) -{ 4 }-> cond1(or(gr(x8, y1), gr(x12, y1)), 1 + x8, x12, 1 + y1) :|: y1 >= 0, z2 = 1 + y1, x8 >= 0, z1 = 1 + x12, x12 >= 0, z'' = 1 + x8, z' = 1 1159.94/295.76 cond3(z', z'', z1, z2) -{ 4 }-> cond1(or(gr(x8, y1), 0), 1 + x8, 0, 1 + y1) :|: y1 >= 0, z2 = 1 + y1, z1 = 0, x8 >= 0, z'' = 1 + x8, z' = 1 1159.94/295.76 cond3(z', z'', z1, z2) -{ 4 }-> cond1(or(0, gr(x10, y2)), 0, x10, 1 + y2) :|: z'' = 0, z2 = 1 + y2, z' = 1, z1 = 1 + x10, x10 >= 0, y2 >= 0 1159.94/295.77 cond3(z', z'', z1, z2) -{ 3 }-> cond1(or(0, gr(x16, y4)), 0, 1 + x16, 1 + y4) :|: z'' = 0, z1 = 1 + x16, z2 = 1 + y4, y4 >= 0, x16 >= 0, z' = 0 1159.94/295.77 cond3(z', z'', z1, z2) -{ 5 }-> cond1(1, 0, x9, 0) :|: z'' = 0, z2 = 0, z1 = 1 + x9, z' = 1, x9 >= 0, 0 = x, x >= 0, 1 = 1 1159.94/295.77 cond3(z', z'', z1, z2) -{ 4 }-> cond1(1, 0, 1 + x15, 0) :|: z'' = 0, z1 = 1 + x15, z2 = 0, x15 >= 0, z' = 0, 0 = x, x >= 0, 1 = 1 1159.94/295.77 cond3(z', z'', z1, z2) -{ 4 }-> cond1(1, 1 + x13, 0, 0) :|: x13 >= 0, z1 = 0, z2 = 0, z'' = 1 + x13, z' = 0, x >= 0, 0 = x, 1 = 1 1159.94/295.77 cond3(z', z'', z1, z2) -{ 4 }-> cond1(1, 1 + x13, 1 + x17, 0) :|: x13 >= 0, x17 >= 0, z1 = 1 + x17, z2 = 0, z'' = 1 + x13, z' = 0, x >= 0, 1 = x, 1 = 1 1159.94/295.77 cond3(z', z'', z1, z2) -{ 5 }-> cond1(1, 1 + x7, x11, 0) :|: z1 = 1 + x11, x7 >= 0, z2 = 0, z'' = 1 + x7, x11 >= 0, z' = 1, x >= 0, 1 = x, 1 = 1 1159.94/295.77 cond3(z', z'', z1, z2) -{ 5 }-> cond1(1, 1 + x7, 0, 0) :|: z1 = 0, x7 >= 0, z2 = 0, z'' = 1 + x7, z' = 1, x >= 0, 0 = x, 1 = 1 1159.94/295.77 cond3(z', z'', z1, z2) -{ 5 }-> cond1(0, 0, 0, z) :|: z'' = 0, z1 = 0, z >= 0, z2 = z, z' = 1, 0 = 0 1159.94/295.77 cond3(z', z'', z1, z2) -{ 4 }-> cond1(0, 0, 0, z) :|: z'' = 0, z1 = 0, z >= 0, z2 = z, z' = 0, 0 = 0 1159.94/295.77 gr(z', z'') -{ 1 }-> gr(x, y) :|: z' = 1 + x, x >= 0, y >= 0, z'' = 1 + y 1159.94/295.77 gr(z', z'') -{ 1 }-> 1 :|: z'' = 0, z' = 1 + x, x >= 0 1159.94/295.77 gr(z', z'') -{ 1 }-> 0 :|: x >= 0, z'' = x, z' = 0 1159.94/295.77 or(z', z'') -{ 1 }-> 1 :|: x >= 0, z'' = x, z' = 1 1159.94/295.77 or(z', z'') -{ 1 }-> 1 :|: z' = x, x >= 0, z'' = 1 1159.94/295.77 or(z', z'') -{ 1 }-> 0 :|: z'' = 0, z' = 0 1159.94/295.77 p(z') -{ 1 }-> x :|: z' = 1 + x, x >= 0 1159.94/295.77 p(z') -{ 1 }-> 0 :|: z' = 0 1159.94/295.77 1159.94/295.77 1159.94/295.77 ---------------------------------------- 1159.94/295.77 1159.94/295.77 (13) SimplificationProof (BOTH BOUNDS(ID, ID)) 1159.94/295.77 Simplified the RNTS by moving equalities from the constraints into the right-hand sides. 1159.94/295.77 ---------------------------------------- 1159.94/295.77 1159.94/295.77 (14) 1159.94/295.77 Obligation: 1159.94/295.77 Complexity RNTS consisting of the following rules: 1159.94/295.77 1159.94/295.77 cond1(z', z'', z1, z2) -{ 2 }-> cond2(1, 1 + (z'' - 1), z1, z2) :|: z2 >= 0, z'' - 1 >= 0, z1 >= 0, z' = 1 1159.94/295.77 cond1(z', z'', z1, z2) -{ 2 }-> cond2(0, 0, z1, z2) :|: z'' = 0, z2 >= 0, z1 >= 0, z' = 1 1159.94/295.77 cond2(z', z'', z1, z2) -{ 2 }-> cond3(1, z'', 1 + (z1 - 1), z2) :|: z2 >= 0, z'' >= 0, z1 - 1 >= 0, z' = 0 1159.94/295.77 cond2(z', z'', z1, z2) -{ 2 }-> cond3(0, z'', 0, z2) :|: z1 = 0, z2 >= 0, z'' >= 0, z' = 0 1159.94/295.77 cond2(z', z'', z1, z2) -{ 4 }-> cond1(or(gr(z'' - 1, z2 - 1), gr(z1 - 1, z2 - 1)), z'' - 1, 1 + (z1 - 1), 1 + (z2 - 1)) :|: z'' - 1 >= 0, z1 - 1 >= 0, z2 - 1 >= 0, z' = 1 1159.94/295.77 cond2(z', z'', z1, z2) -{ 4 }-> cond1(or(gr(z'' - 1, z2 - 1), 0), z'' - 1, 0, 1 + (z2 - 1)) :|: z1 = 0, z'' - 1 >= 0, z2 - 1 >= 0, z' = 1 1159.94/295.77 cond2(z', z'', z1, z2) -{ 4 }-> cond1(or(0, gr(z1 - 1, z2 - 1)), 0, 1 + (z1 - 1), 1 + (z2 - 1)) :|: z'' = 0, z2 - 1 >= 0, z' = 1, z1 - 1 >= 0 1159.94/295.77 cond2(z', z'', z1, z2) -{ 5 }-> cond1(1, 0, 1 + (z1 - 1), 0) :|: z'' = 0, z2 = 0, z' = 1, z1 - 1 >= 0, 0 = x, x >= 0, 1 = 1 1159.94/295.77 cond2(z', z'', z1, z2) -{ 5 }-> cond1(1, z'' - 1, 0, 0) :|: z1 = 0, z2 = 0, z' = 1, z'' - 1 >= 0, x >= 0, 0 = x, 1 = 1 1159.94/295.77 cond2(z', z'', z1, z2) -{ 5 }-> cond1(1, z'' - 1, 1 + (z1 - 1), 0) :|: z1 - 1 >= 0, z2 = 0, z' = 1, z'' - 1 >= 0, x >= 0, 1 = x, 1 = 1 1159.94/295.77 cond2(z', z'', z1, z2) -{ 5 }-> cond1(0, 0, 0, z2) :|: z'' = 0, z1 = 0, z2 >= 0, z' = 1, 0 = 0 1159.94/295.77 cond3(z', z'', z1, z2) -{ 4 }-> cond1(or(gr(z'' - 1, z2 - 1), gr(z1 - 1, z2 - 1)), 1 + (z'' - 1), z1 - 1, 1 + (z2 - 1)) :|: z2 - 1 >= 0, z'' - 1 >= 0, z1 - 1 >= 0, z' = 1 1159.94/295.77 cond3(z', z'', z1, z2) -{ 3 }-> cond1(or(gr(z'' - 1, z2 - 1), gr(z1 - 1, z2 - 1)), 1 + (z'' - 1), 1 + (z1 - 1), 1 + (z2 - 1)) :|: z2 - 1 >= 0, z'' - 1 >= 0, z1 - 1 >= 0, z' = 0 1159.94/295.77 cond3(z', z'', z1, z2) -{ 4 }-> cond1(or(gr(z'' - 1, z2 - 1), 0), 1 + (z'' - 1), 0, 1 + (z2 - 1)) :|: z2 - 1 >= 0, z1 = 0, z'' - 1 >= 0, z' = 1 1159.94/295.77 cond3(z', z'', z1, z2) -{ 3 }-> cond1(or(gr(z'' - 1, z2 - 1), 0), 1 + (z'' - 1), 0, 1 + (z2 - 1)) :|: z1 = 0, z2 - 1 >= 0, z'' - 1 >= 0, z' = 0 1159.94/295.77 cond3(z', z'', z1, z2) -{ 4 }-> cond1(or(0, gr(z1 - 1, z2 - 1)), 0, z1 - 1, 1 + (z2 - 1)) :|: z'' = 0, z' = 1, z1 - 1 >= 0, z2 - 1 >= 0 1159.94/295.77 cond3(z', z'', z1, z2) -{ 3 }-> cond1(or(0, gr(z1 - 1, z2 - 1)), 0, 1 + (z1 - 1), 1 + (z2 - 1)) :|: z'' = 0, z2 - 1 >= 0, z1 - 1 >= 0, z' = 0 1159.94/295.77 cond3(z', z'', z1, z2) -{ 5 }-> cond1(1, 0, z1 - 1, 0) :|: z'' = 0, z2 = 0, z' = 1, z1 - 1 >= 0, 0 = x, x >= 0, 1 = 1 1159.94/295.77 cond3(z', z'', z1, z2) -{ 4 }-> cond1(1, 0, 1 + (z1 - 1), 0) :|: z'' = 0, z2 = 0, z1 - 1 >= 0, z' = 0, 0 = x, x >= 0, 1 = 1 1159.94/295.77 cond3(z', z'', z1, z2) -{ 5 }-> cond1(1, 1 + (z'' - 1), 0, 0) :|: z1 = 0, z'' - 1 >= 0, z2 = 0, z' = 1, x >= 0, 0 = x, 1 = 1 1159.94/295.77 cond3(z', z'', z1, z2) -{ 4 }-> cond1(1, 1 + (z'' - 1), 0, 0) :|: z'' - 1 >= 0, z1 = 0, z2 = 0, z' = 0, x >= 0, 0 = x, 1 = 1 1159.94/295.77 cond3(z', z'', z1, z2) -{ 5 }-> cond1(1, 1 + (z'' - 1), z1 - 1, 0) :|: z'' - 1 >= 0, z2 = 0, z1 - 1 >= 0, z' = 1, x >= 0, 1 = x, 1 = 1 1159.94/295.77 cond3(z', z'', z1, z2) -{ 4 }-> cond1(1, 1 + (z'' - 1), 1 + (z1 - 1), 0) :|: z'' - 1 >= 0, z1 - 1 >= 0, z2 = 0, z' = 0, x >= 0, 1 = x, 1 = 1 1159.94/295.77 cond3(z', z'', z1, z2) -{ 5 }-> cond1(0, 0, 0, z2) :|: z'' = 0, z1 = 0, z2 >= 0, z' = 1, 0 = 0 1159.94/295.77 cond3(z', z'', z1, z2) -{ 4 }-> cond1(0, 0, 0, z2) :|: z'' = 0, z1 = 0, z2 >= 0, z' = 0, 0 = 0 1159.94/295.77 gr(z', z'') -{ 1 }-> gr(z' - 1, z'' - 1) :|: z' - 1 >= 0, z'' - 1 >= 0 1159.94/295.77 gr(z', z'') -{ 1 }-> 1 :|: z'' = 0, z' - 1 >= 0 1159.94/295.77 gr(z', z'') -{ 1 }-> 0 :|: z'' >= 0, z' = 0 1159.94/295.77 or(z', z'') -{ 1 }-> 1 :|: z'' >= 0, z' = 1 1159.94/295.77 or(z', z'') -{ 1 }-> 1 :|: z' >= 0, z'' = 1 1159.94/295.77 or(z', z'') -{ 1 }-> 0 :|: z'' = 0, z' = 0 1159.94/295.77 p(z') -{ 1 }-> 0 :|: z' = 0 1159.94/295.77 p(z') -{ 1 }-> z' - 1 :|: z' - 1 >= 0 1159.94/295.77 1159.94/295.77 1159.94/295.77 ---------------------------------------- 1159.94/295.77 1159.94/295.77 (15) CpxRntsAnalysisOrderProof (BOTH BOUNDS(ID, ID)) 1159.94/295.77 Found the following analysis order by SCC decomposition: 1159.94/295.77 1159.94/295.77 { p } 1159.94/295.77 { gr } 1159.94/295.77 { or } 1159.94/295.77 { cond1, cond2, cond3 } 1159.94/295.77 1159.94/295.77 ---------------------------------------- 1159.94/295.77 1159.94/295.77 (16) 1159.94/295.77 Obligation: 1159.94/295.77 Complexity RNTS consisting of the following rules: 1159.94/295.77 1159.94/295.77 cond1(z', z'', z1, z2) -{ 2 }-> cond2(1, 1 + (z'' - 1), z1, z2) :|: z2 >= 0, z'' - 1 >= 0, z1 >= 0, z' = 1 1159.94/295.77 cond1(z', z'', z1, z2) -{ 2 }-> cond2(0, 0, z1, z2) :|: z'' = 0, z2 >= 0, z1 >= 0, z' = 1 1159.94/295.77 cond2(z', z'', z1, z2) -{ 2 }-> cond3(1, z'', 1 + (z1 - 1), z2) :|: z2 >= 0, z'' >= 0, z1 - 1 >= 0, z' = 0 1159.94/295.77 cond2(z', z'', z1, z2) -{ 2 }-> cond3(0, z'', 0, z2) :|: z1 = 0, z2 >= 0, z'' >= 0, z' = 0 1159.94/295.77 cond2(z', z'', z1, z2) -{ 4 }-> cond1(or(gr(z'' - 1, z2 - 1), gr(z1 - 1, z2 - 1)), z'' - 1, 1 + (z1 - 1), 1 + (z2 - 1)) :|: z'' - 1 >= 0, z1 - 1 >= 0, z2 - 1 >= 0, z' = 1 1159.94/295.77 cond2(z', z'', z1, z2) -{ 4 }-> cond1(or(gr(z'' - 1, z2 - 1), 0), z'' - 1, 0, 1 + (z2 - 1)) :|: z1 = 0, z'' - 1 >= 0, z2 - 1 >= 0, z' = 1 1159.94/295.77 cond2(z', z'', z1, z2) -{ 4 }-> cond1(or(0, gr(z1 - 1, z2 - 1)), 0, 1 + (z1 - 1), 1 + (z2 - 1)) :|: z'' = 0, z2 - 1 >= 0, z' = 1, z1 - 1 >= 0 1159.94/295.77 cond2(z', z'', z1, z2) -{ 5 }-> cond1(1, 0, 1 + (z1 - 1), 0) :|: z'' = 0, z2 = 0, z' = 1, z1 - 1 >= 0, 0 = x, x >= 0, 1 = 1 1159.94/295.77 cond2(z', z'', z1, z2) -{ 5 }-> cond1(1, z'' - 1, 0, 0) :|: z1 = 0, z2 = 0, z' = 1, z'' - 1 >= 0, x >= 0, 0 = x, 1 = 1 1159.94/295.77 cond2(z', z'', z1, z2) -{ 5 }-> cond1(1, z'' - 1, 1 + (z1 - 1), 0) :|: z1 - 1 >= 0, z2 = 0, z' = 1, z'' - 1 >= 0, x >= 0, 1 = x, 1 = 1 1159.94/295.77 cond2(z', z'', z1, z2) -{ 5 }-> cond1(0, 0, 0, z2) :|: z'' = 0, z1 = 0, z2 >= 0, z' = 1, 0 = 0 1159.94/295.77 cond3(z', z'', z1, z2) -{ 4 }-> cond1(or(gr(z'' - 1, z2 - 1), gr(z1 - 1, z2 - 1)), 1 + (z'' - 1), z1 - 1, 1 + (z2 - 1)) :|: z2 - 1 >= 0, z'' - 1 >= 0, z1 - 1 >= 0, z' = 1 1159.94/295.77 cond3(z', z'', z1, z2) -{ 3 }-> cond1(or(gr(z'' - 1, z2 - 1), gr(z1 - 1, z2 - 1)), 1 + (z'' - 1), 1 + (z1 - 1), 1 + (z2 - 1)) :|: z2 - 1 >= 0, z'' - 1 >= 0, z1 - 1 >= 0, z' = 0 1159.94/295.77 cond3(z', z'', z1, z2) -{ 4 }-> cond1(or(gr(z'' - 1, z2 - 1), 0), 1 + (z'' - 1), 0, 1 + (z2 - 1)) :|: z2 - 1 >= 0, z1 = 0, z'' - 1 >= 0, z' = 1 1159.94/295.77 cond3(z', z'', z1, z2) -{ 3 }-> cond1(or(gr(z'' - 1, z2 - 1), 0), 1 + (z'' - 1), 0, 1 + (z2 - 1)) :|: z1 = 0, z2 - 1 >= 0, z'' - 1 >= 0, z' = 0 1159.94/295.77 cond3(z', z'', z1, z2) -{ 4 }-> cond1(or(0, gr(z1 - 1, z2 - 1)), 0, z1 - 1, 1 + (z2 - 1)) :|: z'' = 0, z' = 1, z1 - 1 >= 0, z2 - 1 >= 0 1159.94/295.77 cond3(z', z'', z1, z2) -{ 3 }-> cond1(or(0, gr(z1 - 1, z2 - 1)), 0, 1 + (z1 - 1), 1 + (z2 - 1)) :|: z'' = 0, z2 - 1 >= 0, z1 - 1 >= 0, z' = 0 1159.94/295.77 cond3(z', z'', z1, z2) -{ 5 }-> cond1(1, 0, z1 - 1, 0) :|: z'' = 0, z2 = 0, z' = 1, z1 - 1 >= 0, 0 = x, x >= 0, 1 = 1 1159.94/295.77 cond3(z', z'', z1, z2) -{ 4 }-> cond1(1, 0, 1 + (z1 - 1), 0) :|: z'' = 0, z2 = 0, z1 - 1 >= 0, z' = 0, 0 = x, x >= 0, 1 = 1 1159.94/295.77 cond3(z', z'', z1, z2) -{ 5 }-> cond1(1, 1 + (z'' - 1), 0, 0) :|: z1 = 0, z'' - 1 >= 0, z2 = 0, z' = 1, x >= 0, 0 = x, 1 = 1 1159.94/295.77 cond3(z', z'', z1, z2) -{ 4 }-> cond1(1, 1 + (z'' - 1), 0, 0) :|: z'' - 1 >= 0, z1 = 0, z2 = 0, z' = 0, x >= 0, 0 = x, 1 = 1 1159.94/295.77 cond3(z', z'', z1, z2) -{ 5 }-> cond1(1, 1 + (z'' - 1), z1 - 1, 0) :|: z'' - 1 >= 0, z2 = 0, z1 - 1 >= 0, z' = 1, x >= 0, 1 = x, 1 = 1 1159.94/295.77 cond3(z', z'', z1, z2) -{ 4 }-> cond1(1, 1 + (z'' - 1), 1 + (z1 - 1), 0) :|: z'' - 1 >= 0, z1 - 1 >= 0, z2 = 0, z' = 0, x >= 0, 1 = x, 1 = 1 1159.94/295.77 cond3(z', z'', z1, z2) -{ 5 }-> cond1(0, 0, 0, z2) :|: z'' = 0, z1 = 0, z2 >= 0, z' = 1, 0 = 0 1159.94/295.77 cond3(z', z'', z1, z2) -{ 4 }-> cond1(0, 0, 0, z2) :|: z'' = 0, z1 = 0, z2 >= 0, z' = 0, 0 = 0 1159.94/295.77 gr(z', z'') -{ 1 }-> gr(z' - 1, z'' - 1) :|: z' - 1 >= 0, z'' - 1 >= 0 1159.94/295.77 gr(z', z'') -{ 1 }-> 1 :|: z'' = 0, z' - 1 >= 0 1159.94/295.77 gr(z', z'') -{ 1 }-> 0 :|: z'' >= 0, z' = 0 1159.94/295.77 or(z', z'') -{ 1 }-> 1 :|: z'' >= 0, z' = 1 1159.94/295.77 or(z', z'') -{ 1 }-> 1 :|: z' >= 0, z'' = 1 1159.94/295.77 or(z', z'') -{ 1 }-> 0 :|: z'' = 0, z' = 0 1159.94/295.77 p(z') -{ 1 }-> 0 :|: z' = 0 1159.94/295.77 p(z') -{ 1 }-> z' - 1 :|: z' - 1 >= 0 1159.94/295.77 1159.94/295.77 Function symbols to be analyzed: {p}, {gr}, {or}, {cond1,cond2,cond3} 1159.94/295.77 1159.94/295.77 ---------------------------------------- 1159.94/295.77 1159.94/295.77 (17) ResultPropagationProof (UPPER BOUND(ID)) 1159.94/295.77 Applied inner abstraction using the recently inferred runtime/size bounds where possible. 1159.94/295.77 ---------------------------------------- 1159.94/295.77 1159.94/295.77 (18) 1159.94/295.77 Obligation: 1159.94/295.77 Complexity RNTS consisting of the following rules: 1159.94/295.77 1159.94/295.77 cond1(z', z'', z1, z2) -{ 2 }-> cond2(1, 1 + (z'' - 1), z1, z2) :|: z2 >= 0, z'' - 1 >= 0, z1 >= 0, z' = 1 1159.94/295.77 cond1(z', z'', z1, z2) -{ 2 }-> cond2(0, 0, z1, z2) :|: z'' = 0, z2 >= 0, z1 >= 0, z' = 1 1159.94/295.77 cond2(z', z'', z1, z2) -{ 2 }-> cond3(1, z'', 1 + (z1 - 1), z2) :|: z2 >= 0, z'' >= 0, z1 - 1 >= 0, z' = 0 1159.94/295.77 cond2(z', z'', z1, z2) -{ 2 }-> cond3(0, z'', 0, z2) :|: z1 = 0, z2 >= 0, z'' >= 0, z' = 0 1159.94/295.77 cond2(z', z'', z1, z2) -{ 4 }-> cond1(or(gr(z'' - 1, z2 - 1), gr(z1 - 1, z2 - 1)), z'' - 1, 1 + (z1 - 1), 1 + (z2 - 1)) :|: z'' - 1 >= 0, z1 - 1 >= 0, z2 - 1 >= 0, z' = 1 1159.94/295.77 cond2(z', z'', z1, z2) -{ 4 }-> cond1(or(gr(z'' - 1, z2 - 1), 0), z'' - 1, 0, 1 + (z2 - 1)) :|: z1 = 0, z'' - 1 >= 0, z2 - 1 >= 0, z' = 1 1159.94/295.77 cond2(z', z'', z1, z2) -{ 4 }-> cond1(or(0, gr(z1 - 1, z2 - 1)), 0, 1 + (z1 - 1), 1 + (z2 - 1)) :|: z'' = 0, z2 - 1 >= 0, z' = 1, z1 - 1 >= 0 1159.94/295.77 cond2(z', z'', z1, z2) -{ 5 }-> cond1(1, 0, 1 + (z1 - 1), 0) :|: z'' = 0, z2 = 0, z' = 1, z1 - 1 >= 0, 0 = x, x >= 0, 1 = 1 1159.94/295.77 cond2(z', z'', z1, z2) -{ 5 }-> cond1(1, z'' - 1, 0, 0) :|: z1 = 0, z2 = 0, z' = 1, z'' - 1 >= 0, x >= 0, 0 = x, 1 = 1 1159.94/295.77 cond2(z', z'', z1, z2) -{ 5 }-> cond1(1, z'' - 1, 1 + (z1 - 1), 0) :|: z1 - 1 >= 0, z2 = 0, z' = 1, z'' - 1 >= 0, x >= 0, 1 = x, 1 = 1 1159.94/295.77 cond2(z', z'', z1, z2) -{ 5 }-> cond1(0, 0, 0, z2) :|: z'' = 0, z1 = 0, z2 >= 0, z' = 1, 0 = 0 1159.94/295.77 cond3(z', z'', z1, z2) -{ 4 }-> cond1(or(gr(z'' - 1, z2 - 1), gr(z1 - 1, z2 - 1)), 1 + (z'' - 1), z1 - 1, 1 + (z2 - 1)) :|: z2 - 1 >= 0, z'' - 1 >= 0, z1 - 1 >= 0, z' = 1 1159.94/295.77 cond3(z', z'', z1, z2) -{ 3 }-> cond1(or(gr(z'' - 1, z2 - 1), gr(z1 - 1, z2 - 1)), 1 + (z'' - 1), 1 + (z1 - 1), 1 + (z2 - 1)) :|: z2 - 1 >= 0, z'' - 1 >= 0, z1 - 1 >= 0, z' = 0 1159.94/295.77 cond3(z', z'', z1, z2) -{ 4 }-> cond1(or(gr(z'' - 1, z2 - 1), 0), 1 + (z'' - 1), 0, 1 + (z2 - 1)) :|: z2 - 1 >= 0, z1 = 0, z'' - 1 >= 0, z' = 1 1159.94/295.77 cond3(z', z'', z1, z2) -{ 3 }-> cond1(or(gr(z'' - 1, z2 - 1), 0), 1 + (z'' - 1), 0, 1 + (z2 - 1)) :|: z1 = 0, z2 - 1 >= 0, z'' - 1 >= 0, z' = 0 1159.94/295.77 cond3(z', z'', z1, z2) -{ 4 }-> cond1(or(0, gr(z1 - 1, z2 - 1)), 0, z1 - 1, 1 + (z2 - 1)) :|: z'' = 0, z' = 1, z1 - 1 >= 0, z2 - 1 >= 0 1159.94/295.77 cond3(z', z'', z1, z2) -{ 3 }-> cond1(or(0, gr(z1 - 1, z2 - 1)), 0, 1 + (z1 - 1), 1 + (z2 - 1)) :|: z'' = 0, z2 - 1 >= 0, z1 - 1 >= 0, z' = 0 1159.94/295.77 cond3(z', z'', z1, z2) -{ 5 }-> cond1(1, 0, z1 - 1, 0) :|: z'' = 0, z2 = 0, z' = 1, z1 - 1 >= 0, 0 = x, x >= 0, 1 = 1 1159.94/295.77 cond3(z', z'', z1, z2) -{ 4 }-> cond1(1, 0, 1 + (z1 - 1), 0) :|: z'' = 0, z2 = 0, z1 - 1 >= 0, z' = 0, 0 = x, x >= 0, 1 = 1 1159.94/295.77 cond3(z', z'', z1, z2) -{ 5 }-> cond1(1, 1 + (z'' - 1), 0, 0) :|: z1 = 0, z'' - 1 >= 0, z2 = 0, z' = 1, x >= 0, 0 = x, 1 = 1 1159.94/295.77 cond3(z', z'', z1, z2) -{ 4 }-> cond1(1, 1 + (z'' - 1), 0, 0) :|: z'' - 1 >= 0, z1 = 0, z2 = 0, z' = 0, x >= 0, 0 = x, 1 = 1 1159.94/295.77 cond3(z', z'', z1, z2) -{ 5 }-> cond1(1, 1 + (z'' - 1), z1 - 1, 0) :|: z'' - 1 >= 0, z2 = 0, z1 - 1 >= 0, z' = 1, x >= 0, 1 = x, 1 = 1 1159.94/295.77 cond3(z', z'', z1, z2) -{ 4 }-> cond1(1, 1 + (z'' - 1), 1 + (z1 - 1), 0) :|: z'' - 1 >= 0, z1 - 1 >= 0, z2 = 0, z' = 0, x >= 0, 1 = x, 1 = 1 1159.94/295.77 cond3(z', z'', z1, z2) -{ 5 }-> cond1(0, 0, 0, z2) :|: z'' = 0, z1 = 0, z2 >= 0, z' = 1, 0 = 0 1159.94/295.77 cond3(z', z'', z1, z2) -{ 4 }-> cond1(0, 0, 0, z2) :|: z'' = 0, z1 = 0, z2 >= 0, z' = 0, 0 = 0 1159.94/295.77 gr(z', z'') -{ 1 }-> gr(z' - 1, z'' - 1) :|: z' - 1 >= 0, z'' - 1 >= 0 1159.94/295.77 gr(z', z'') -{ 1 }-> 1 :|: z'' = 0, z' - 1 >= 0 1159.94/295.77 gr(z', z'') -{ 1 }-> 0 :|: z'' >= 0, z' = 0 1159.94/295.77 or(z', z'') -{ 1 }-> 1 :|: z'' >= 0, z' = 1 1159.94/295.77 or(z', z'') -{ 1 }-> 1 :|: z' >= 0, z'' = 1 1159.94/295.77 or(z', z'') -{ 1 }-> 0 :|: z'' = 0, z' = 0 1159.94/295.77 p(z') -{ 1 }-> 0 :|: z' = 0 1159.94/295.77 p(z') -{ 1 }-> z' - 1 :|: z' - 1 >= 0 1159.94/295.77 1159.94/295.77 Function symbols to be analyzed: {p}, {gr}, {or}, {cond1,cond2,cond3} 1159.94/295.77 1159.94/295.77 ---------------------------------------- 1159.94/295.77 1159.94/295.77 (19) IntTrsBoundProof (UPPER BOUND(ID)) 1159.94/295.77 1159.94/295.77 Computed SIZE bound using KoAT for: p 1159.94/295.77 after applying outer abstraction to obtain an ITS, 1159.94/295.77 resulting in: O(n^1) with polynomial bound: z' 1159.94/295.77 1159.94/295.77 ---------------------------------------- 1159.94/295.77 1159.94/295.77 (20) 1159.94/295.77 Obligation: 1159.94/295.77 Complexity RNTS consisting of the following rules: 1159.94/295.77 1159.94/295.77 cond1(z', z'', z1, z2) -{ 2 }-> cond2(1, 1 + (z'' - 1), z1, z2) :|: z2 >= 0, z'' - 1 >= 0, z1 >= 0, z' = 1 1159.94/295.77 cond1(z', z'', z1, z2) -{ 2 }-> cond2(0, 0, z1, z2) :|: z'' = 0, z2 >= 0, z1 >= 0, z' = 1 1159.94/295.77 cond2(z', z'', z1, z2) -{ 2 }-> cond3(1, z'', 1 + (z1 - 1), z2) :|: z2 >= 0, z'' >= 0, z1 - 1 >= 0, z' = 0 1159.94/295.77 cond2(z', z'', z1, z2) -{ 2 }-> cond3(0, z'', 0, z2) :|: z1 = 0, z2 >= 0, z'' >= 0, z' = 0 1159.94/295.77 cond2(z', z'', z1, z2) -{ 4 }-> cond1(or(gr(z'' - 1, z2 - 1), gr(z1 - 1, z2 - 1)), z'' - 1, 1 + (z1 - 1), 1 + (z2 - 1)) :|: z'' - 1 >= 0, z1 - 1 >= 0, z2 - 1 >= 0, z' = 1 1159.94/295.77 cond2(z', z'', z1, z2) -{ 4 }-> cond1(or(gr(z'' - 1, z2 - 1), 0), z'' - 1, 0, 1 + (z2 - 1)) :|: z1 = 0, z'' - 1 >= 0, z2 - 1 >= 0, z' = 1 1159.94/295.77 cond2(z', z'', z1, z2) -{ 4 }-> cond1(or(0, gr(z1 - 1, z2 - 1)), 0, 1 + (z1 - 1), 1 + (z2 - 1)) :|: z'' = 0, z2 - 1 >= 0, z' = 1, z1 - 1 >= 0 1159.94/295.77 cond2(z', z'', z1, z2) -{ 5 }-> cond1(1, 0, 1 + (z1 - 1), 0) :|: z'' = 0, z2 = 0, z' = 1, z1 - 1 >= 0, 0 = x, x >= 0, 1 = 1 1159.94/295.77 cond2(z', z'', z1, z2) -{ 5 }-> cond1(1, z'' - 1, 0, 0) :|: z1 = 0, z2 = 0, z' = 1, z'' - 1 >= 0, x >= 0, 0 = x, 1 = 1 1159.94/295.77 cond2(z', z'', z1, z2) -{ 5 }-> cond1(1, z'' - 1, 1 + (z1 - 1), 0) :|: z1 - 1 >= 0, z2 = 0, z' = 1, z'' - 1 >= 0, x >= 0, 1 = x, 1 = 1 1159.94/295.77 cond2(z', z'', z1, z2) -{ 5 }-> cond1(0, 0, 0, z2) :|: z'' = 0, z1 = 0, z2 >= 0, z' = 1, 0 = 0 1159.94/295.77 cond3(z', z'', z1, z2) -{ 4 }-> cond1(or(gr(z'' - 1, z2 - 1), gr(z1 - 1, z2 - 1)), 1 + (z'' - 1), z1 - 1, 1 + (z2 - 1)) :|: z2 - 1 >= 0, z'' - 1 >= 0, z1 - 1 >= 0, z' = 1 1159.94/295.77 cond3(z', z'', z1, z2) -{ 3 }-> cond1(or(gr(z'' - 1, z2 - 1), gr(z1 - 1, z2 - 1)), 1 + (z'' - 1), 1 + (z1 - 1), 1 + (z2 - 1)) :|: z2 - 1 >= 0, z'' - 1 >= 0, z1 - 1 >= 0, z' = 0 1159.94/295.77 cond3(z', z'', z1, z2) -{ 4 }-> cond1(or(gr(z'' - 1, z2 - 1), 0), 1 + (z'' - 1), 0, 1 + (z2 - 1)) :|: z2 - 1 >= 0, z1 = 0, z'' - 1 >= 0, z' = 1 1159.94/295.77 cond3(z', z'', z1, z2) -{ 3 }-> cond1(or(gr(z'' - 1, z2 - 1), 0), 1 + (z'' - 1), 0, 1 + (z2 - 1)) :|: z1 = 0, z2 - 1 >= 0, z'' - 1 >= 0, z' = 0 1159.94/295.77 cond3(z', z'', z1, z2) -{ 4 }-> cond1(or(0, gr(z1 - 1, z2 - 1)), 0, z1 - 1, 1 + (z2 - 1)) :|: z'' = 0, z' = 1, z1 - 1 >= 0, z2 - 1 >= 0 1159.94/295.77 cond3(z', z'', z1, z2) -{ 3 }-> cond1(or(0, gr(z1 - 1, z2 - 1)), 0, 1 + (z1 - 1), 1 + (z2 - 1)) :|: z'' = 0, z2 - 1 >= 0, z1 - 1 >= 0, z' = 0 1159.94/295.77 cond3(z', z'', z1, z2) -{ 5 }-> cond1(1, 0, z1 - 1, 0) :|: z'' = 0, z2 = 0, z' = 1, z1 - 1 >= 0, 0 = x, x >= 0, 1 = 1 1159.94/295.77 cond3(z', z'', z1, z2) -{ 4 }-> cond1(1, 0, 1 + (z1 - 1), 0) :|: z'' = 0, z2 = 0, z1 - 1 >= 0, z' = 0, 0 = x, x >= 0, 1 = 1 1159.94/295.77 cond3(z', z'', z1, z2) -{ 5 }-> cond1(1, 1 + (z'' - 1), 0, 0) :|: z1 = 0, z'' - 1 >= 0, z2 = 0, z' = 1, x >= 0, 0 = x, 1 = 1 1159.94/295.77 cond3(z', z'', z1, z2) -{ 4 }-> cond1(1, 1 + (z'' - 1), 0, 0) :|: z'' - 1 >= 0, z1 = 0, z2 = 0, z' = 0, x >= 0, 0 = x, 1 = 1 1159.94/295.77 cond3(z', z'', z1, z2) -{ 5 }-> cond1(1, 1 + (z'' - 1), z1 - 1, 0) :|: z'' - 1 >= 0, z2 = 0, z1 - 1 >= 0, z' = 1, x >= 0, 1 = x, 1 = 1 1159.94/295.77 cond3(z', z'', z1, z2) -{ 4 }-> cond1(1, 1 + (z'' - 1), 1 + (z1 - 1), 0) :|: z'' - 1 >= 0, z1 - 1 >= 0, z2 = 0, z' = 0, x >= 0, 1 = x, 1 = 1 1159.94/295.77 cond3(z', z'', z1, z2) -{ 5 }-> cond1(0, 0, 0, z2) :|: z'' = 0, z1 = 0, z2 >= 0, z' = 1, 0 = 0 1159.94/295.77 cond3(z', z'', z1, z2) -{ 4 }-> cond1(0, 0, 0, z2) :|: z'' = 0, z1 = 0, z2 >= 0, z' = 0, 0 = 0 1159.94/295.77 gr(z', z'') -{ 1 }-> gr(z' - 1, z'' - 1) :|: z' - 1 >= 0, z'' - 1 >= 0 1159.94/295.77 gr(z', z'') -{ 1 }-> 1 :|: z'' = 0, z' - 1 >= 0 1159.94/295.77 gr(z', z'') -{ 1 }-> 0 :|: z'' >= 0, z' = 0 1159.94/295.77 or(z', z'') -{ 1 }-> 1 :|: z'' >= 0, z' = 1 1159.94/295.77 or(z', z'') -{ 1 }-> 1 :|: z' >= 0, z'' = 1 1159.94/295.77 or(z', z'') -{ 1 }-> 0 :|: z'' = 0, z' = 0 1159.94/295.77 p(z') -{ 1 }-> 0 :|: z' = 0 1159.94/295.77 p(z') -{ 1 }-> z' - 1 :|: z' - 1 >= 0 1159.94/295.77 1159.94/295.77 Function symbols to be analyzed: {p}, {gr}, {or}, {cond1,cond2,cond3} 1159.94/295.77 Previous analysis results are: 1159.94/295.77 p: runtime: ?, size: O(n^1) [z'] 1159.94/295.77 1159.94/295.77 ---------------------------------------- 1159.94/295.77 1159.94/295.77 (21) IntTrsBoundProof (UPPER BOUND(ID)) 1159.94/295.77 1159.94/295.77 Computed RUNTIME bound using CoFloCo for: p 1159.94/295.77 after applying outer abstraction to obtain an ITS, 1159.94/295.77 resulting in: O(1) with polynomial bound: 1 1159.94/295.77 1159.94/295.77 ---------------------------------------- 1159.94/295.77 1159.94/295.77 (22) 1159.94/295.77 Obligation: 1159.94/295.77 Complexity RNTS consisting of the following rules: 1159.94/295.77 1159.94/295.77 cond1(z', z'', z1, z2) -{ 2 }-> cond2(1, 1 + (z'' - 1), z1, z2) :|: z2 >= 0, z'' - 1 >= 0, z1 >= 0, z' = 1 1159.94/295.77 cond1(z', z'', z1, z2) -{ 2 }-> cond2(0, 0, z1, z2) :|: z'' = 0, z2 >= 0, z1 >= 0, z' = 1 1159.94/295.77 cond2(z', z'', z1, z2) -{ 2 }-> cond3(1, z'', 1 + (z1 - 1), z2) :|: z2 >= 0, z'' >= 0, z1 - 1 >= 0, z' = 0 1159.94/295.77 cond2(z', z'', z1, z2) -{ 2 }-> cond3(0, z'', 0, z2) :|: z1 = 0, z2 >= 0, z'' >= 0, z' = 0 1159.94/295.77 cond2(z', z'', z1, z2) -{ 4 }-> cond1(or(gr(z'' - 1, z2 - 1), gr(z1 - 1, z2 - 1)), z'' - 1, 1 + (z1 - 1), 1 + (z2 - 1)) :|: z'' - 1 >= 0, z1 - 1 >= 0, z2 - 1 >= 0, z' = 1 1159.94/295.77 cond2(z', z'', z1, z2) -{ 4 }-> cond1(or(gr(z'' - 1, z2 - 1), 0), z'' - 1, 0, 1 + (z2 - 1)) :|: z1 = 0, z'' - 1 >= 0, z2 - 1 >= 0, z' = 1 1159.94/295.77 cond2(z', z'', z1, z2) -{ 4 }-> cond1(or(0, gr(z1 - 1, z2 - 1)), 0, 1 + (z1 - 1), 1 + (z2 - 1)) :|: z'' = 0, z2 - 1 >= 0, z' = 1, z1 - 1 >= 0 1159.94/295.77 cond2(z', z'', z1, z2) -{ 5 }-> cond1(1, 0, 1 + (z1 - 1), 0) :|: z'' = 0, z2 = 0, z' = 1, z1 - 1 >= 0, 0 = x, x >= 0, 1 = 1 1159.94/295.77 cond2(z', z'', z1, z2) -{ 5 }-> cond1(1, z'' - 1, 0, 0) :|: z1 = 0, z2 = 0, z' = 1, z'' - 1 >= 0, x >= 0, 0 = x, 1 = 1 1159.94/295.77 cond2(z', z'', z1, z2) -{ 5 }-> cond1(1, z'' - 1, 1 + (z1 - 1), 0) :|: z1 - 1 >= 0, z2 = 0, z' = 1, z'' - 1 >= 0, x >= 0, 1 = x, 1 = 1 1159.94/295.77 cond2(z', z'', z1, z2) -{ 5 }-> cond1(0, 0, 0, z2) :|: z'' = 0, z1 = 0, z2 >= 0, z' = 1, 0 = 0 1159.94/295.77 cond3(z', z'', z1, z2) -{ 4 }-> cond1(or(gr(z'' - 1, z2 - 1), gr(z1 - 1, z2 - 1)), 1 + (z'' - 1), z1 - 1, 1 + (z2 - 1)) :|: z2 - 1 >= 0, z'' - 1 >= 0, z1 - 1 >= 0, z' = 1 1159.94/295.77 cond3(z', z'', z1, z2) -{ 3 }-> cond1(or(gr(z'' - 1, z2 - 1), gr(z1 - 1, z2 - 1)), 1 + (z'' - 1), 1 + (z1 - 1), 1 + (z2 - 1)) :|: z2 - 1 >= 0, z'' - 1 >= 0, z1 - 1 >= 0, z' = 0 1159.94/295.77 cond3(z', z'', z1, z2) -{ 4 }-> cond1(or(gr(z'' - 1, z2 - 1), 0), 1 + (z'' - 1), 0, 1 + (z2 - 1)) :|: z2 - 1 >= 0, z1 = 0, z'' - 1 >= 0, z' = 1 1159.94/295.77 cond3(z', z'', z1, z2) -{ 3 }-> cond1(or(gr(z'' - 1, z2 - 1), 0), 1 + (z'' - 1), 0, 1 + (z2 - 1)) :|: z1 = 0, z2 - 1 >= 0, z'' - 1 >= 0, z' = 0 1159.94/295.77 cond3(z', z'', z1, z2) -{ 4 }-> cond1(or(0, gr(z1 - 1, z2 - 1)), 0, z1 - 1, 1 + (z2 - 1)) :|: z'' = 0, z' = 1, z1 - 1 >= 0, z2 - 1 >= 0 1159.94/295.77 cond3(z', z'', z1, z2) -{ 3 }-> cond1(or(0, gr(z1 - 1, z2 - 1)), 0, 1 + (z1 - 1), 1 + (z2 - 1)) :|: z'' = 0, z2 - 1 >= 0, z1 - 1 >= 0, z' = 0 1159.94/295.77 cond3(z', z'', z1, z2) -{ 5 }-> cond1(1, 0, z1 - 1, 0) :|: z'' = 0, z2 = 0, z' = 1, z1 - 1 >= 0, 0 = x, x >= 0, 1 = 1 1159.94/295.77 cond3(z', z'', z1, z2) -{ 4 }-> cond1(1, 0, 1 + (z1 - 1), 0) :|: z'' = 0, z2 = 0, z1 - 1 >= 0, z' = 0, 0 = x, x >= 0, 1 = 1 1159.94/295.77 cond3(z', z'', z1, z2) -{ 5 }-> cond1(1, 1 + (z'' - 1), 0, 0) :|: z1 = 0, z'' - 1 >= 0, z2 = 0, z' = 1, x >= 0, 0 = x, 1 = 1 1159.94/295.77 cond3(z', z'', z1, z2) -{ 4 }-> cond1(1, 1 + (z'' - 1), 0, 0) :|: z'' - 1 >= 0, z1 = 0, z2 = 0, z' = 0, x >= 0, 0 = x, 1 = 1 1159.94/295.77 cond3(z', z'', z1, z2) -{ 5 }-> cond1(1, 1 + (z'' - 1), z1 - 1, 0) :|: z'' - 1 >= 0, z2 = 0, z1 - 1 >= 0, z' = 1, x >= 0, 1 = x, 1 = 1 1159.94/295.77 cond3(z', z'', z1, z2) -{ 4 }-> cond1(1, 1 + (z'' - 1), 1 + (z1 - 1), 0) :|: z'' - 1 >= 0, z1 - 1 >= 0, z2 = 0, z' = 0, x >= 0, 1 = x, 1 = 1 1159.94/295.77 cond3(z', z'', z1, z2) -{ 5 }-> cond1(0, 0, 0, z2) :|: z'' = 0, z1 = 0, z2 >= 0, z' = 1, 0 = 0 1159.94/295.77 cond3(z', z'', z1, z2) -{ 4 }-> cond1(0, 0, 0, z2) :|: z'' = 0, z1 = 0, z2 >= 0, z' = 0, 0 = 0 1159.94/295.77 gr(z', z'') -{ 1 }-> gr(z' - 1, z'' - 1) :|: z' - 1 >= 0, z'' - 1 >= 0 1159.94/295.77 gr(z', z'') -{ 1 }-> 1 :|: z'' = 0, z' - 1 >= 0 1159.94/295.77 gr(z', z'') -{ 1 }-> 0 :|: z'' >= 0, z' = 0 1159.94/295.77 or(z', z'') -{ 1 }-> 1 :|: z'' >= 0, z' = 1 1159.94/295.77 or(z', z'') -{ 1 }-> 1 :|: z' >= 0, z'' = 1 1159.94/295.77 or(z', z'') -{ 1 }-> 0 :|: z'' = 0, z' = 0 1159.94/295.77 p(z') -{ 1 }-> 0 :|: z' = 0 1159.94/295.77 p(z') -{ 1 }-> z' - 1 :|: z' - 1 >= 0 1159.94/295.77 1159.94/295.77 Function symbols to be analyzed: {gr}, {or}, {cond1,cond2,cond3} 1159.94/295.77 Previous analysis results are: 1159.94/295.77 p: runtime: O(1) [1], size: O(n^1) [z'] 1159.94/295.77 1159.94/295.77 ---------------------------------------- 1159.94/295.77 1159.94/295.77 (23) ResultPropagationProof (UPPER BOUND(ID)) 1159.94/295.77 Applied inner abstraction using the recently inferred runtime/size bounds where possible. 1159.94/295.77 ---------------------------------------- 1159.94/295.77 1159.94/295.77 (24) 1159.94/295.77 Obligation: 1159.94/295.77 Complexity RNTS consisting of the following rules: 1159.94/295.77 1159.94/295.77 cond1(z', z'', z1, z2) -{ 2 }-> cond2(1, 1 + (z'' - 1), z1, z2) :|: z2 >= 0, z'' - 1 >= 0, z1 >= 0, z' = 1 1159.94/295.77 cond1(z', z'', z1, z2) -{ 2 }-> cond2(0, 0, z1, z2) :|: z'' = 0, z2 >= 0, z1 >= 0, z' = 1 1159.94/295.77 cond2(z', z'', z1, z2) -{ 2 }-> cond3(1, z'', 1 + (z1 - 1), z2) :|: z2 >= 0, z'' >= 0, z1 - 1 >= 0, z' = 0 1159.94/295.77 cond2(z', z'', z1, z2) -{ 2 }-> cond3(0, z'', 0, z2) :|: z1 = 0, z2 >= 0, z'' >= 0, z' = 0 1159.94/295.77 cond2(z', z'', z1, z2) -{ 4 }-> cond1(or(gr(z'' - 1, z2 - 1), gr(z1 - 1, z2 - 1)), z'' - 1, 1 + (z1 - 1), 1 + (z2 - 1)) :|: z'' - 1 >= 0, z1 - 1 >= 0, z2 - 1 >= 0, z' = 1 1159.94/295.77 cond2(z', z'', z1, z2) -{ 4 }-> cond1(or(gr(z'' - 1, z2 - 1), 0), z'' - 1, 0, 1 + (z2 - 1)) :|: z1 = 0, z'' - 1 >= 0, z2 - 1 >= 0, z' = 1 1159.94/295.77 cond2(z', z'', z1, z2) -{ 4 }-> cond1(or(0, gr(z1 - 1, z2 - 1)), 0, 1 + (z1 - 1), 1 + (z2 - 1)) :|: z'' = 0, z2 - 1 >= 0, z' = 1, z1 - 1 >= 0 1159.94/295.77 cond2(z', z'', z1, z2) -{ 5 }-> cond1(1, 0, 1 + (z1 - 1), 0) :|: z'' = 0, z2 = 0, z' = 1, z1 - 1 >= 0, 0 = x, x >= 0, 1 = 1 1159.94/295.77 cond2(z', z'', z1, z2) -{ 5 }-> cond1(1, z'' - 1, 0, 0) :|: z1 = 0, z2 = 0, z' = 1, z'' - 1 >= 0, x >= 0, 0 = x, 1 = 1 1159.94/295.77 cond2(z', z'', z1, z2) -{ 5 }-> cond1(1, z'' - 1, 1 + (z1 - 1), 0) :|: z1 - 1 >= 0, z2 = 0, z' = 1, z'' - 1 >= 0, x >= 0, 1 = x, 1 = 1 1159.94/295.77 cond2(z', z'', z1, z2) -{ 5 }-> cond1(0, 0, 0, z2) :|: z'' = 0, z1 = 0, z2 >= 0, z' = 1, 0 = 0 1159.94/295.77 cond3(z', z'', z1, z2) -{ 4 }-> cond1(or(gr(z'' - 1, z2 - 1), gr(z1 - 1, z2 - 1)), 1 + (z'' - 1), z1 - 1, 1 + (z2 - 1)) :|: z2 - 1 >= 0, z'' - 1 >= 0, z1 - 1 >= 0, z' = 1 1159.94/295.77 cond3(z', z'', z1, z2) -{ 3 }-> cond1(or(gr(z'' - 1, z2 - 1), gr(z1 - 1, z2 - 1)), 1 + (z'' - 1), 1 + (z1 - 1), 1 + (z2 - 1)) :|: z2 - 1 >= 0, z'' - 1 >= 0, z1 - 1 >= 0, z' = 0 1159.94/295.77 cond3(z', z'', z1, z2) -{ 4 }-> cond1(or(gr(z'' - 1, z2 - 1), 0), 1 + (z'' - 1), 0, 1 + (z2 - 1)) :|: z2 - 1 >= 0, z1 = 0, z'' - 1 >= 0, z' = 1 1159.94/295.77 cond3(z', z'', z1, z2) -{ 3 }-> cond1(or(gr(z'' - 1, z2 - 1), 0), 1 + (z'' - 1), 0, 1 + (z2 - 1)) :|: z1 = 0, z2 - 1 >= 0, z'' - 1 >= 0, z' = 0 1159.94/295.77 cond3(z', z'', z1, z2) -{ 4 }-> cond1(or(0, gr(z1 - 1, z2 - 1)), 0, z1 - 1, 1 + (z2 - 1)) :|: z'' = 0, z' = 1, z1 - 1 >= 0, z2 - 1 >= 0 1159.94/295.77 cond3(z', z'', z1, z2) -{ 3 }-> cond1(or(0, gr(z1 - 1, z2 - 1)), 0, 1 + (z1 - 1), 1 + (z2 - 1)) :|: z'' = 0, z2 - 1 >= 0, z1 - 1 >= 0, z' = 0 1159.94/295.77 cond3(z', z'', z1, z2) -{ 5 }-> cond1(1, 0, z1 - 1, 0) :|: z'' = 0, z2 = 0, z' = 1, z1 - 1 >= 0, 0 = x, x >= 0, 1 = 1 1159.94/295.77 cond3(z', z'', z1, z2) -{ 4 }-> cond1(1, 0, 1 + (z1 - 1), 0) :|: z'' = 0, z2 = 0, z1 - 1 >= 0, z' = 0, 0 = x, x >= 0, 1 = 1 1159.94/295.77 cond3(z', z'', z1, z2) -{ 5 }-> cond1(1, 1 + (z'' - 1), 0, 0) :|: z1 = 0, z'' - 1 >= 0, z2 = 0, z' = 1, x >= 0, 0 = x, 1 = 1 1159.94/295.77 cond3(z', z'', z1, z2) -{ 4 }-> cond1(1, 1 + (z'' - 1), 0, 0) :|: z'' - 1 >= 0, z1 = 0, z2 = 0, z' = 0, x >= 0, 0 = x, 1 = 1 1159.94/295.77 cond3(z', z'', z1, z2) -{ 5 }-> cond1(1, 1 + (z'' - 1), z1 - 1, 0) :|: z'' - 1 >= 0, z2 = 0, z1 - 1 >= 0, z' = 1, x >= 0, 1 = x, 1 = 1 1159.94/295.77 cond3(z', z'', z1, z2) -{ 4 }-> cond1(1, 1 + (z'' - 1), 1 + (z1 - 1), 0) :|: z'' - 1 >= 0, z1 - 1 >= 0, z2 = 0, z' = 0, x >= 0, 1 = x, 1 = 1 1159.94/295.77 cond3(z', z'', z1, z2) -{ 5 }-> cond1(0, 0, 0, z2) :|: z'' = 0, z1 = 0, z2 >= 0, z' = 1, 0 = 0 1159.94/295.77 cond3(z', z'', z1, z2) -{ 4 }-> cond1(0, 0, 0, z2) :|: z'' = 0, z1 = 0, z2 >= 0, z' = 0, 0 = 0 1159.94/295.77 gr(z', z'') -{ 1 }-> gr(z' - 1, z'' - 1) :|: z' - 1 >= 0, z'' - 1 >= 0 1159.94/295.77 gr(z', z'') -{ 1 }-> 1 :|: z'' = 0, z' - 1 >= 0 1159.94/295.77 gr(z', z'') -{ 1 }-> 0 :|: z'' >= 0, z' = 0 1159.94/295.77 or(z', z'') -{ 1 }-> 1 :|: z'' >= 0, z' = 1 1159.94/295.77 or(z', z'') -{ 1 }-> 1 :|: z' >= 0, z'' = 1 1159.94/295.77 or(z', z'') -{ 1 }-> 0 :|: z'' = 0, z' = 0 1159.94/295.77 p(z') -{ 1 }-> 0 :|: z' = 0 1159.94/295.77 p(z') -{ 1 }-> z' - 1 :|: z' - 1 >= 0 1159.94/295.77 1159.94/295.77 Function symbols to be analyzed: {gr}, {or}, {cond1,cond2,cond3} 1159.94/295.77 Previous analysis results are: 1159.94/295.77 p: runtime: O(1) [1], size: O(n^1) [z'] 1159.94/295.77 1159.94/295.77 ---------------------------------------- 1159.94/295.77 1159.94/295.77 (25) IntTrsBoundProof (UPPER BOUND(ID)) 1159.94/295.77 1159.94/295.77 Computed SIZE bound using CoFloCo for: gr 1159.94/295.77 after applying outer abstraction to obtain an ITS, 1159.94/295.77 resulting in: O(1) with polynomial bound: 1 1159.94/295.77 1159.94/295.77 ---------------------------------------- 1159.94/295.77 1159.94/295.77 (26) 1159.94/295.77 Obligation: 1159.94/295.77 Complexity RNTS consisting of the following rules: 1159.94/295.77 1159.94/295.77 cond1(z', z'', z1, z2) -{ 2 }-> cond2(1, 1 + (z'' - 1), z1, z2) :|: z2 >= 0, z'' - 1 >= 0, z1 >= 0, z' = 1 1159.94/295.77 cond1(z', z'', z1, z2) -{ 2 }-> cond2(0, 0, z1, z2) :|: z'' = 0, z2 >= 0, z1 >= 0, z' = 1 1159.94/295.77 cond2(z', z'', z1, z2) -{ 2 }-> cond3(1, z'', 1 + (z1 - 1), z2) :|: z2 >= 0, z'' >= 0, z1 - 1 >= 0, z' = 0 1159.94/295.77 cond2(z', z'', z1, z2) -{ 2 }-> cond3(0, z'', 0, z2) :|: z1 = 0, z2 >= 0, z'' >= 0, z' = 0 1159.94/295.77 cond2(z', z'', z1, z2) -{ 4 }-> cond1(or(gr(z'' - 1, z2 - 1), gr(z1 - 1, z2 - 1)), z'' - 1, 1 + (z1 - 1), 1 + (z2 - 1)) :|: z'' - 1 >= 0, z1 - 1 >= 0, z2 - 1 >= 0, z' = 1 1159.94/295.77 cond2(z', z'', z1, z2) -{ 4 }-> cond1(or(gr(z'' - 1, z2 - 1), 0), z'' - 1, 0, 1 + (z2 - 1)) :|: z1 = 0, z'' - 1 >= 0, z2 - 1 >= 0, z' = 1 1159.94/295.77 cond2(z', z'', z1, z2) -{ 4 }-> cond1(or(0, gr(z1 - 1, z2 - 1)), 0, 1 + (z1 - 1), 1 + (z2 - 1)) :|: z'' = 0, z2 - 1 >= 0, z' = 1, z1 - 1 >= 0 1159.94/295.77 cond2(z', z'', z1, z2) -{ 5 }-> cond1(1, 0, 1 + (z1 - 1), 0) :|: z'' = 0, z2 = 0, z' = 1, z1 - 1 >= 0, 0 = x, x >= 0, 1 = 1 1159.94/295.77 cond2(z', z'', z1, z2) -{ 5 }-> cond1(1, z'' - 1, 0, 0) :|: z1 = 0, z2 = 0, z' = 1, z'' - 1 >= 0, x >= 0, 0 = x, 1 = 1 1159.94/295.77 cond2(z', z'', z1, z2) -{ 5 }-> cond1(1, z'' - 1, 1 + (z1 - 1), 0) :|: z1 - 1 >= 0, z2 = 0, z' = 1, z'' - 1 >= 0, x >= 0, 1 = x, 1 = 1 1159.94/295.77 cond2(z', z'', z1, z2) -{ 5 }-> cond1(0, 0, 0, z2) :|: z'' = 0, z1 = 0, z2 >= 0, z' = 1, 0 = 0 1159.94/295.77 cond3(z', z'', z1, z2) -{ 4 }-> cond1(or(gr(z'' - 1, z2 - 1), gr(z1 - 1, z2 - 1)), 1 + (z'' - 1), z1 - 1, 1 + (z2 - 1)) :|: z2 - 1 >= 0, z'' - 1 >= 0, z1 - 1 >= 0, z' = 1 1159.94/295.77 cond3(z', z'', z1, z2) -{ 3 }-> cond1(or(gr(z'' - 1, z2 - 1), gr(z1 - 1, z2 - 1)), 1 + (z'' - 1), 1 + (z1 - 1), 1 + (z2 - 1)) :|: z2 - 1 >= 0, z'' - 1 >= 0, z1 - 1 >= 0, z' = 0 1159.94/295.77 cond3(z', z'', z1, z2) -{ 4 }-> cond1(or(gr(z'' - 1, z2 - 1), 0), 1 + (z'' - 1), 0, 1 + (z2 - 1)) :|: z2 - 1 >= 0, z1 = 0, z'' - 1 >= 0, z' = 1 1159.94/295.77 cond3(z', z'', z1, z2) -{ 3 }-> cond1(or(gr(z'' - 1, z2 - 1), 0), 1 + (z'' - 1), 0, 1 + (z2 - 1)) :|: z1 = 0, z2 - 1 >= 0, z'' - 1 >= 0, z' = 0 1159.94/295.77 cond3(z', z'', z1, z2) -{ 4 }-> cond1(or(0, gr(z1 - 1, z2 - 1)), 0, z1 - 1, 1 + (z2 - 1)) :|: z'' = 0, z' = 1, z1 - 1 >= 0, z2 - 1 >= 0 1159.94/295.77 cond3(z', z'', z1, z2) -{ 3 }-> cond1(or(0, gr(z1 - 1, z2 - 1)), 0, 1 + (z1 - 1), 1 + (z2 - 1)) :|: z'' = 0, z2 - 1 >= 0, z1 - 1 >= 0, z' = 0 1159.94/295.77 cond3(z', z'', z1, z2) -{ 5 }-> cond1(1, 0, z1 - 1, 0) :|: z'' = 0, z2 = 0, z' = 1, z1 - 1 >= 0, 0 = x, x >= 0, 1 = 1 1159.94/295.77 cond3(z', z'', z1, z2) -{ 4 }-> cond1(1, 0, 1 + (z1 - 1), 0) :|: z'' = 0, z2 = 0, z1 - 1 >= 0, z' = 0, 0 = x, x >= 0, 1 = 1 1159.94/295.77 cond3(z', z'', z1, z2) -{ 5 }-> cond1(1, 1 + (z'' - 1), 0, 0) :|: z1 = 0, z'' - 1 >= 0, z2 = 0, z' = 1, x >= 0, 0 = x, 1 = 1 1159.94/295.77 cond3(z', z'', z1, z2) -{ 4 }-> cond1(1, 1 + (z'' - 1), 0, 0) :|: z'' - 1 >= 0, z1 = 0, z2 = 0, z' = 0, x >= 0, 0 = x, 1 = 1 1159.94/295.77 cond3(z', z'', z1, z2) -{ 5 }-> cond1(1, 1 + (z'' - 1), z1 - 1, 0) :|: z'' - 1 >= 0, z2 = 0, z1 - 1 >= 0, z' = 1, x >= 0, 1 = x, 1 = 1 1159.94/295.77 cond3(z', z'', z1, z2) -{ 4 }-> cond1(1, 1 + (z'' - 1), 1 + (z1 - 1), 0) :|: z'' - 1 >= 0, z1 - 1 >= 0, z2 = 0, z' = 0, x >= 0, 1 = x, 1 = 1 1159.94/295.77 cond3(z', z'', z1, z2) -{ 5 }-> cond1(0, 0, 0, z2) :|: z'' = 0, z1 = 0, z2 >= 0, z' = 1, 0 = 0 1159.94/295.77 cond3(z', z'', z1, z2) -{ 4 }-> cond1(0, 0, 0, z2) :|: z'' = 0, z1 = 0, z2 >= 0, z' = 0, 0 = 0 1159.94/295.77 gr(z', z'') -{ 1 }-> gr(z' - 1, z'' - 1) :|: z' - 1 >= 0, z'' - 1 >= 0 1159.94/295.77 gr(z', z'') -{ 1 }-> 1 :|: z'' = 0, z' - 1 >= 0 1159.94/295.77 gr(z', z'') -{ 1 }-> 0 :|: z'' >= 0, z' = 0 1159.94/295.77 or(z', z'') -{ 1 }-> 1 :|: z'' >= 0, z' = 1 1159.94/295.77 or(z', z'') -{ 1 }-> 1 :|: z' >= 0, z'' = 1 1159.94/295.77 or(z', z'') -{ 1 }-> 0 :|: z'' = 0, z' = 0 1159.94/295.77 p(z') -{ 1 }-> 0 :|: z' = 0 1159.94/295.77 p(z') -{ 1 }-> z' - 1 :|: z' - 1 >= 0 1159.94/295.77 1159.94/295.77 Function symbols to be analyzed: {gr}, {or}, {cond1,cond2,cond3} 1159.94/295.77 Previous analysis results are: 1159.94/295.77 p: runtime: O(1) [1], size: O(n^1) [z'] 1159.94/295.77 gr: runtime: ?, size: O(1) [1] 1159.94/295.77 1159.94/295.77 ---------------------------------------- 1159.94/295.77 1159.94/295.77 (27) IntTrsBoundProof (UPPER BOUND(ID)) 1159.94/295.77 1159.94/295.77 Computed RUNTIME bound using KoAT for: gr 1159.94/295.77 after applying outer abstraction to obtain an ITS, 1159.94/295.77 resulting in: O(n^1) with polynomial bound: 2 + z'' 1159.94/295.77 1159.94/295.77 ---------------------------------------- 1159.94/295.77 1159.94/295.77 (28) 1159.94/295.77 Obligation: 1159.94/295.77 Complexity RNTS consisting of the following rules: 1159.94/295.77 1159.94/295.77 cond1(z', z'', z1, z2) -{ 2 }-> cond2(1, 1 + (z'' - 1), z1, z2) :|: z2 >= 0, z'' - 1 >= 0, z1 >= 0, z' = 1 1159.94/295.77 cond1(z', z'', z1, z2) -{ 2 }-> cond2(0, 0, z1, z2) :|: z'' = 0, z2 >= 0, z1 >= 0, z' = 1 1159.94/295.77 cond2(z', z'', z1, z2) -{ 2 }-> cond3(1, z'', 1 + (z1 - 1), z2) :|: z2 >= 0, z'' >= 0, z1 - 1 >= 0, z' = 0 1159.94/295.77 cond2(z', z'', z1, z2) -{ 2 }-> cond3(0, z'', 0, z2) :|: z1 = 0, z2 >= 0, z'' >= 0, z' = 0 1159.94/295.77 cond2(z', z'', z1, z2) -{ 4 }-> cond1(or(gr(z'' - 1, z2 - 1), gr(z1 - 1, z2 - 1)), z'' - 1, 1 + (z1 - 1), 1 + (z2 - 1)) :|: z'' - 1 >= 0, z1 - 1 >= 0, z2 - 1 >= 0, z' = 1 1159.94/295.77 cond2(z', z'', z1, z2) -{ 4 }-> cond1(or(gr(z'' - 1, z2 - 1), 0), z'' - 1, 0, 1 + (z2 - 1)) :|: z1 = 0, z'' - 1 >= 0, z2 - 1 >= 0, z' = 1 1159.94/295.77 cond2(z', z'', z1, z2) -{ 4 }-> cond1(or(0, gr(z1 - 1, z2 - 1)), 0, 1 + (z1 - 1), 1 + (z2 - 1)) :|: z'' = 0, z2 - 1 >= 0, z' = 1, z1 - 1 >= 0 1159.94/295.77 cond2(z', z'', z1, z2) -{ 5 }-> cond1(1, 0, 1 + (z1 - 1), 0) :|: z'' = 0, z2 = 0, z' = 1, z1 - 1 >= 0, 0 = x, x >= 0, 1 = 1 1159.94/295.77 cond2(z', z'', z1, z2) -{ 5 }-> cond1(1, z'' - 1, 0, 0) :|: z1 = 0, z2 = 0, z' = 1, z'' - 1 >= 0, x >= 0, 0 = x, 1 = 1 1159.94/295.77 cond2(z', z'', z1, z2) -{ 5 }-> cond1(1, z'' - 1, 1 + (z1 - 1), 0) :|: z1 - 1 >= 0, z2 = 0, z' = 1, z'' - 1 >= 0, x >= 0, 1 = x, 1 = 1 1159.94/295.77 cond2(z', z'', z1, z2) -{ 5 }-> cond1(0, 0, 0, z2) :|: z'' = 0, z1 = 0, z2 >= 0, z' = 1, 0 = 0 1159.94/295.77 cond3(z', z'', z1, z2) -{ 4 }-> cond1(or(gr(z'' - 1, z2 - 1), gr(z1 - 1, z2 - 1)), 1 + (z'' - 1), z1 - 1, 1 + (z2 - 1)) :|: z2 - 1 >= 0, z'' - 1 >= 0, z1 - 1 >= 0, z' = 1 1159.94/295.77 cond3(z', z'', z1, z2) -{ 3 }-> cond1(or(gr(z'' - 1, z2 - 1), gr(z1 - 1, z2 - 1)), 1 + (z'' - 1), 1 + (z1 - 1), 1 + (z2 - 1)) :|: z2 - 1 >= 0, z'' - 1 >= 0, z1 - 1 >= 0, z' = 0 1159.94/295.77 cond3(z', z'', z1, z2) -{ 4 }-> cond1(or(gr(z'' - 1, z2 - 1), 0), 1 + (z'' - 1), 0, 1 + (z2 - 1)) :|: z2 - 1 >= 0, z1 = 0, z'' - 1 >= 0, z' = 1 1159.94/295.77 cond3(z', z'', z1, z2) -{ 3 }-> cond1(or(gr(z'' - 1, z2 - 1), 0), 1 + (z'' - 1), 0, 1 + (z2 - 1)) :|: z1 = 0, z2 - 1 >= 0, z'' - 1 >= 0, z' = 0 1159.94/295.77 cond3(z', z'', z1, z2) -{ 4 }-> cond1(or(0, gr(z1 - 1, z2 - 1)), 0, z1 - 1, 1 + (z2 - 1)) :|: z'' = 0, z' = 1, z1 - 1 >= 0, z2 - 1 >= 0 1159.94/295.77 cond3(z', z'', z1, z2) -{ 3 }-> cond1(or(0, gr(z1 - 1, z2 - 1)), 0, 1 + (z1 - 1), 1 + (z2 - 1)) :|: z'' = 0, z2 - 1 >= 0, z1 - 1 >= 0, z' = 0 1159.94/295.77 cond3(z', z'', z1, z2) -{ 5 }-> cond1(1, 0, z1 - 1, 0) :|: z'' = 0, z2 = 0, z' = 1, z1 - 1 >= 0, 0 = x, x >= 0, 1 = 1 1159.94/295.78 cond3(z', z'', z1, z2) -{ 4 }-> cond1(1, 0, 1 + (z1 - 1), 0) :|: z'' = 0, z2 = 0, z1 - 1 >= 0, z' = 0, 0 = x, x >= 0, 1 = 1 1159.94/295.78 cond3(z', z'', z1, z2) -{ 5 }-> cond1(1, 1 + (z'' - 1), 0, 0) :|: z1 = 0, z'' - 1 >= 0, z2 = 0, z' = 1, x >= 0, 0 = x, 1 = 1 1159.94/295.78 cond3(z', z'', z1, z2) -{ 4 }-> cond1(1, 1 + (z'' - 1), 0, 0) :|: z'' - 1 >= 0, z1 = 0, z2 = 0, z' = 0, x >= 0, 0 = x, 1 = 1 1159.94/295.78 cond3(z', z'', z1, z2) -{ 5 }-> cond1(1, 1 + (z'' - 1), z1 - 1, 0) :|: z'' - 1 >= 0, z2 = 0, z1 - 1 >= 0, z' = 1, x >= 0, 1 = x, 1 = 1 1159.94/295.78 cond3(z', z'', z1, z2) -{ 4 }-> cond1(1, 1 + (z'' - 1), 1 + (z1 - 1), 0) :|: z'' - 1 >= 0, z1 - 1 >= 0, z2 = 0, z' = 0, x >= 0, 1 = x, 1 = 1 1159.94/295.78 cond3(z', z'', z1, z2) -{ 5 }-> cond1(0, 0, 0, z2) :|: z'' = 0, z1 = 0, z2 >= 0, z' = 1, 0 = 0 1159.94/295.78 cond3(z', z'', z1, z2) -{ 4 }-> cond1(0, 0, 0, z2) :|: z'' = 0, z1 = 0, z2 >= 0, z' = 0, 0 = 0 1159.94/295.78 gr(z', z'') -{ 1 }-> gr(z' - 1, z'' - 1) :|: z' - 1 >= 0, z'' - 1 >= 0 1159.94/295.78 gr(z', z'') -{ 1 }-> 1 :|: z'' = 0, z' - 1 >= 0 1159.94/295.78 gr(z', z'') -{ 1 }-> 0 :|: z'' >= 0, z' = 0 1159.94/295.78 or(z', z'') -{ 1 }-> 1 :|: z'' >= 0, z' = 1 1159.94/295.78 or(z', z'') -{ 1 }-> 1 :|: z' >= 0, z'' = 1 1159.94/295.78 or(z', z'') -{ 1 }-> 0 :|: z'' = 0, z' = 0 1159.94/295.78 p(z') -{ 1 }-> 0 :|: z' = 0 1159.94/295.78 p(z') -{ 1 }-> z' - 1 :|: z' - 1 >= 0 1159.94/295.78 1159.94/295.78 Function symbols to be analyzed: {or}, {cond1,cond2,cond3} 1159.94/295.78 Previous analysis results are: 1159.94/295.78 p: runtime: O(1) [1], size: O(n^1) [z'] 1159.94/295.78 gr: runtime: O(n^1) [2 + z''], size: O(1) [1] 1159.94/295.78 1159.94/295.78 ---------------------------------------- 1159.94/295.78 1159.94/295.78 (29) ResultPropagationProof (UPPER BOUND(ID)) 1159.94/295.78 Applied inner abstraction using the recently inferred runtime/size bounds where possible. 1159.94/295.78 ---------------------------------------- 1159.94/295.78 1159.94/295.78 (30) 1159.94/295.78 Obligation: 1159.94/295.78 Complexity RNTS consisting of the following rules: 1159.94/295.78 1159.94/295.78 cond1(z', z'', z1, z2) -{ 2 }-> cond2(1, 1 + (z'' - 1), z1, z2) :|: z2 >= 0, z'' - 1 >= 0, z1 >= 0, z' = 1 1159.94/295.78 cond1(z', z'', z1, z2) -{ 2 }-> cond2(0, 0, z1, z2) :|: z'' = 0, z2 >= 0, z1 >= 0, z' = 1 1159.94/295.78 cond2(z', z'', z1, z2) -{ 2 }-> cond3(1, z'', 1 + (z1 - 1), z2) :|: z2 >= 0, z'' >= 0, z1 - 1 >= 0, z' = 0 1159.94/295.78 cond2(z', z'', z1, z2) -{ 2 }-> cond3(0, z'', 0, z2) :|: z1 = 0, z2 >= 0, z'' >= 0, z' = 0 1159.94/295.78 cond2(z', z'', z1, z2) -{ 5 + z2 }-> cond1(or(s'', 0), z'' - 1, 0, 1 + (z2 - 1)) :|: s'' >= 0, s'' <= 1, z1 = 0, z'' - 1 >= 0, z2 - 1 >= 0, z' = 1 1159.94/295.78 cond2(z', z'', z1, z2) -{ 6 + 2*z2 }-> cond1(or(s1, s2), z'' - 1, 1 + (z1 - 1), 1 + (z2 - 1)) :|: s1 >= 0, s1 <= 1, s2 >= 0, s2 <= 1, z'' - 1 >= 0, z1 - 1 >= 0, z2 - 1 >= 0, z' = 1 1159.94/295.78 cond2(z', z'', z1, z2) -{ 5 + z2 }-> cond1(or(0, s'), 0, 1 + (z1 - 1), 1 + (z2 - 1)) :|: s' >= 0, s' <= 1, z'' = 0, z2 - 1 >= 0, z' = 1, z1 - 1 >= 0 1159.94/295.78 cond2(z', z'', z1, z2) -{ 5 }-> cond1(1, 0, 1 + (z1 - 1), 0) :|: z'' = 0, z2 = 0, z' = 1, z1 - 1 >= 0, 0 = x, x >= 0, 1 = 1 1159.94/295.78 cond2(z', z'', z1, z2) -{ 5 }-> cond1(1, z'' - 1, 0, 0) :|: z1 = 0, z2 = 0, z' = 1, z'' - 1 >= 0, x >= 0, 0 = x, 1 = 1 1159.94/295.78 cond2(z', z'', z1, z2) -{ 5 }-> cond1(1, z'' - 1, 1 + (z1 - 1), 0) :|: z1 - 1 >= 0, z2 = 0, z' = 1, z'' - 1 >= 0, x >= 0, 1 = x, 1 = 1 1159.94/295.78 cond2(z', z'', z1, z2) -{ 5 }-> cond1(0, 0, 0, z2) :|: z'' = 0, z1 = 0, z2 >= 0, z' = 1, 0 = 0 1159.94/295.78 cond3(z', z'', z1, z2) -{ 5 + z2 }-> cond1(or(s4, 0), 1 + (z'' - 1), 0, 1 + (z2 - 1)) :|: s4 >= 0, s4 <= 1, z2 - 1 >= 0, z1 = 0, z'' - 1 >= 0, z' = 1 1159.94/295.78 cond3(z', z'', z1, z2) -{ 6 + 2*z2 }-> cond1(or(s5, s6), 1 + (z'' - 1), z1 - 1, 1 + (z2 - 1)) :|: s5 >= 0, s5 <= 1, s6 >= 0, s6 <= 1, z2 - 1 >= 0, z'' - 1 >= 0, z1 - 1 >= 0, z' = 1 1159.94/295.78 cond3(z', z'', z1, z2) -{ 4 + z2 }-> cond1(or(s8, 0), 1 + (z'' - 1), 0, 1 + (z2 - 1)) :|: s8 >= 0, s8 <= 1, z1 = 0, z2 - 1 >= 0, z'' - 1 >= 0, z' = 0 1159.94/295.78 cond3(z', z'', z1, z2) -{ 5 + 2*z2 }-> cond1(or(s9, s10), 1 + (z'' - 1), 1 + (z1 - 1), 1 + (z2 - 1)) :|: s9 >= 0, s9 <= 1, s10 >= 0, s10 <= 1, z2 - 1 >= 0, z'' - 1 >= 0, z1 - 1 >= 0, z' = 0 1159.94/295.78 cond3(z', z'', z1, z2) -{ 5 + z2 }-> cond1(or(0, s3), 0, z1 - 1, 1 + (z2 - 1)) :|: s3 >= 0, s3 <= 1, z'' = 0, z' = 1, z1 - 1 >= 0, z2 - 1 >= 0 1159.94/295.78 cond3(z', z'', z1, z2) -{ 4 + z2 }-> cond1(or(0, s7), 0, 1 + (z1 - 1), 1 + (z2 - 1)) :|: s7 >= 0, s7 <= 1, z'' = 0, z2 - 1 >= 0, z1 - 1 >= 0, z' = 0 1159.94/295.78 cond3(z', z'', z1, z2) -{ 5 }-> cond1(1, 0, z1 - 1, 0) :|: z'' = 0, z2 = 0, z' = 1, z1 - 1 >= 0, 0 = x, x >= 0, 1 = 1 1159.94/295.78 cond3(z', z'', z1, z2) -{ 4 }-> cond1(1, 0, 1 + (z1 - 1), 0) :|: z'' = 0, z2 = 0, z1 - 1 >= 0, z' = 0, 0 = x, x >= 0, 1 = 1 1159.94/295.78 cond3(z', z'', z1, z2) -{ 5 }-> cond1(1, 1 + (z'' - 1), 0, 0) :|: z1 = 0, z'' - 1 >= 0, z2 = 0, z' = 1, x >= 0, 0 = x, 1 = 1 1159.94/295.78 cond3(z', z'', z1, z2) -{ 4 }-> cond1(1, 1 + (z'' - 1), 0, 0) :|: z'' - 1 >= 0, z1 = 0, z2 = 0, z' = 0, x >= 0, 0 = x, 1 = 1 1159.94/295.78 cond3(z', z'', z1, z2) -{ 5 }-> cond1(1, 1 + (z'' - 1), z1 - 1, 0) :|: z'' - 1 >= 0, z2 = 0, z1 - 1 >= 0, z' = 1, x >= 0, 1 = x, 1 = 1 1159.94/295.78 cond3(z', z'', z1, z2) -{ 4 }-> cond1(1, 1 + (z'' - 1), 1 + (z1 - 1), 0) :|: z'' - 1 >= 0, z1 - 1 >= 0, z2 = 0, z' = 0, x >= 0, 1 = x, 1 = 1 1159.94/295.78 cond3(z', z'', z1, z2) -{ 5 }-> cond1(0, 0, 0, z2) :|: z'' = 0, z1 = 0, z2 >= 0, z' = 1, 0 = 0 1159.94/295.78 cond3(z', z'', z1, z2) -{ 4 }-> cond1(0, 0, 0, z2) :|: z'' = 0, z1 = 0, z2 >= 0, z' = 0, 0 = 0 1159.94/295.78 gr(z', z'') -{ 2 + z'' }-> s :|: s >= 0, s <= 1, z' - 1 >= 0, z'' - 1 >= 0 1159.94/295.78 gr(z', z'') -{ 1 }-> 1 :|: z'' = 0, z' - 1 >= 0 1159.94/295.78 gr(z', z'') -{ 1 }-> 0 :|: z'' >= 0, z' = 0 1159.94/295.78 or(z', z'') -{ 1 }-> 1 :|: z'' >= 0, z' = 1 1159.94/295.78 or(z', z'') -{ 1 }-> 1 :|: z' >= 0, z'' = 1 1159.94/295.78 or(z', z'') -{ 1 }-> 0 :|: z'' = 0, z' = 0 1159.94/295.78 p(z') -{ 1 }-> 0 :|: z' = 0 1159.94/295.78 p(z') -{ 1 }-> z' - 1 :|: z' - 1 >= 0 1159.94/295.78 1159.94/295.78 Function symbols to be analyzed: {or}, {cond1,cond2,cond3} 1159.94/295.78 Previous analysis results are: 1159.94/295.78 p: runtime: O(1) [1], size: O(n^1) [z'] 1159.94/295.78 gr: runtime: O(n^1) [2 + z''], size: O(1) [1] 1159.94/295.78 1159.94/295.78 ---------------------------------------- 1159.94/295.78 1159.94/295.78 (31) IntTrsBoundProof (UPPER BOUND(ID)) 1159.94/295.78 1159.94/295.78 Computed SIZE bound using CoFloCo for: or 1159.94/295.78 after applying outer abstraction to obtain an ITS, 1159.94/295.78 resulting in: O(1) with polynomial bound: 1 1159.94/295.78 1159.94/295.78 ---------------------------------------- 1159.94/295.78 1159.94/295.78 (32) 1159.94/295.78 Obligation: 1159.94/295.78 Complexity RNTS consisting of the following rules: 1159.94/295.78 1159.94/295.78 cond1(z', z'', z1, z2) -{ 2 }-> cond2(1, 1 + (z'' - 1), z1, z2) :|: z2 >= 0, z'' - 1 >= 0, z1 >= 0, z' = 1 1159.94/295.78 cond1(z', z'', z1, z2) -{ 2 }-> cond2(0, 0, z1, z2) :|: z'' = 0, z2 >= 0, z1 >= 0, z' = 1 1159.94/295.78 cond2(z', z'', z1, z2) -{ 2 }-> cond3(1, z'', 1 + (z1 - 1), z2) :|: z2 >= 0, z'' >= 0, z1 - 1 >= 0, z' = 0 1159.94/295.78 cond2(z', z'', z1, z2) -{ 2 }-> cond3(0, z'', 0, z2) :|: z1 = 0, z2 >= 0, z'' >= 0, z' = 0 1159.94/295.78 cond2(z', z'', z1, z2) -{ 5 + z2 }-> cond1(or(s'', 0), z'' - 1, 0, 1 + (z2 - 1)) :|: s'' >= 0, s'' <= 1, z1 = 0, z'' - 1 >= 0, z2 - 1 >= 0, z' = 1 1159.94/295.78 cond2(z', z'', z1, z2) -{ 6 + 2*z2 }-> cond1(or(s1, s2), z'' - 1, 1 + (z1 - 1), 1 + (z2 - 1)) :|: s1 >= 0, s1 <= 1, s2 >= 0, s2 <= 1, z'' - 1 >= 0, z1 - 1 >= 0, z2 - 1 >= 0, z' = 1 1159.94/295.78 cond2(z', z'', z1, z2) -{ 5 + z2 }-> cond1(or(0, s'), 0, 1 + (z1 - 1), 1 + (z2 - 1)) :|: s' >= 0, s' <= 1, z'' = 0, z2 - 1 >= 0, z' = 1, z1 - 1 >= 0 1159.94/295.78 cond2(z', z'', z1, z2) -{ 5 }-> cond1(1, 0, 1 + (z1 - 1), 0) :|: z'' = 0, z2 = 0, z' = 1, z1 - 1 >= 0, 0 = x, x >= 0, 1 = 1 1159.94/295.78 cond2(z', z'', z1, z2) -{ 5 }-> cond1(1, z'' - 1, 0, 0) :|: z1 = 0, z2 = 0, z' = 1, z'' - 1 >= 0, x >= 0, 0 = x, 1 = 1 1159.94/295.78 cond2(z', z'', z1, z2) -{ 5 }-> cond1(1, z'' - 1, 1 + (z1 - 1), 0) :|: z1 - 1 >= 0, z2 = 0, z' = 1, z'' - 1 >= 0, x >= 0, 1 = x, 1 = 1 1159.94/295.78 cond2(z', z'', z1, z2) -{ 5 }-> cond1(0, 0, 0, z2) :|: z'' = 0, z1 = 0, z2 >= 0, z' = 1, 0 = 0 1159.94/295.78 cond3(z', z'', z1, z2) -{ 5 + z2 }-> cond1(or(s4, 0), 1 + (z'' - 1), 0, 1 + (z2 - 1)) :|: s4 >= 0, s4 <= 1, z2 - 1 >= 0, z1 = 0, z'' - 1 >= 0, z' = 1 1159.94/295.78 cond3(z', z'', z1, z2) -{ 6 + 2*z2 }-> cond1(or(s5, s6), 1 + (z'' - 1), z1 - 1, 1 + (z2 - 1)) :|: s5 >= 0, s5 <= 1, s6 >= 0, s6 <= 1, z2 - 1 >= 0, z'' - 1 >= 0, z1 - 1 >= 0, z' = 1 1159.94/295.78 cond3(z', z'', z1, z2) -{ 4 + z2 }-> cond1(or(s8, 0), 1 + (z'' - 1), 0, 1 + (z2 - 1)) :|: s8 >= 0, s8 <= 1, z1 = 0, z2 - 1 >= 0, z'' - 1 >= 0, z' = 0 1159.94/295.78 cond3(z', z'', z1, z2) -{ 5 + 2*z2 }-> cond1(or(s9, s10), 1 + (z'' - 1), 1 + (z1 - 1), 1 + (z2 - 1)) :|: s9 >= 0, s9 <= 1, s10 >= 0, s10 <= 1, z2 - 1 >= 0, z'' - 1 >= 0, z1 - 1 >= 0, z' = 0 1159.94/295.78 cond3(z', z'', z1, z2) -{ 5 + z2 }-> cond1(or(0, s3), 0, z1 - 1, 1 + (z2 - 1)) :|: s3 >= 0, s3 <= 1, z'' = 0, z' = 1, z1 - 1 >= 0, z2 - 1 >= 0 1159.94/295.81 cond3(z', z'', z1, z2) -{ 4 + z2 }-> cond1(or(0, s7), 0, 1 + (z1 - 1), 1 + (z2 - 1)) :|: s7 >= 0, s7 <= 1, z'' = 0, z2 - 1 >= 0, z1 - 1 >= 0, z' = 0 1159.94/295.81 cond3(z', z'', z1, z2) -{ 5 }-> cond1(1, 0, z1 - 1, 0) :|: z'' = 0, z2 = 0, z' = 1, z1 - 1 >= 0, 0 = x, x >= 0, 1 = 1 1159.94/295.81 cond3(z', z'', z1, z2) -{ 4 }-> cond1(1, 0, 1 + (z1 - 1), 0) :|: z'' = 0, z2 = 0, z1 - 1 >= 0, z' = 0, 0 = x, x >= 0, 1 = 1 1159.94/295.81 cond3(z', z'', z1, z2) -{ 5 }-> cond1(1, 1 + (z'' - 1), 0, 0) :|: z1 = 0, z'' - 1 >= 0, z2 = 0, z' = 1, x >= 0, 0 = x, 1 = 1 1159.94/295.81 cond3(z', z'', z1, z2) -{ 4 }-> cond1(1, 1 + (z'' - 1), 0, 0) :|: z'' - 1 >= 0, z1 = 0, z2 = 0, z' = 0, x >= 0, 0 = x, 1 = 1 1159.94/295.81 cond3(z', z'', z1, z2) -{ 5 }-> cond1(1, 1 + (z'' - 1), z1 - 1, 0) :|: z'' - 1 >= 0, z2 = 0, z1 - 1 >= 0, z' = 1, x >= 0, 1 = x, 1 = 1 1159.94/295.81 cond3(z', z'', z1, z2) -{ 4 }-> cond1(1, 1 + (z'' - 1), 1 + (z1 - 1), 0) :|: z'' - 1 >= 0, z1 - 1 >= 0, z2 = 0, z' = 0, x >= 0, 1 = x, 1 = 1 1159.94/295.81 cond3(z', z'', z1, z2) -{ 5 }-> cond1(0, 0, 0, z2) :|: z'' = 0, z1 = 0, z2 >= 0, z' = 1, 0 = 0 1159.94/295.81 cond3(z', z'', z1, z2) -{ 4 }-> cond1(0, 0, 0, z2) :|: z'' = 0, z1 = 0, z2 >= 0, z' = 0, 0 = 0 1159.94/295.81 gr(z', z'') -{ 2 + z'' }-> s :|: s >= 0, s <= 1, z' - 1 >= 0, z'' - 1 >= 0 1159.94/295.81 gr(z', z'') -{ 1 }-> 1 :|: z'' = 0, z' - 1 >= 0 1159.94/295.81 gr(z', z'') -{ 1 }-> 0 :|: z'' >= 0, z' = 0 1159.94/295.81 or(z', z'') -{ 1 }-> 1 :|: z'' >= 0, z' = 1 1159.94/295.81 or(z', z'') -{ 1 }-> 1 :|: z' >= 0, z'' = 1 1159.94/295.81 or(z', z'') -{ 1 }-> 0 :|: z'' = 0, z' = 0 1159.94/295.81 p(z') -{ 1 }-> 0 :|: z' = 0 1159.94/295.81 p(z') -{ 1 }-> z' - 1 :|: z' - 1 >= 0 1159.94/295.81 1159.94/295.81 Function symbols to be analyzed: {or}, {cond1,cond2,cond3} 1159.94/295.81 Previous analysis results are: 1159.94/295.81 p: runtime: O(1) [1], size: O(n^1) [z'] 1159.94/295.81 gr: runtime: O(n^1) [2 + z''], size: O(1) [1] 1159.94/295.81 or: runtime: ?, size: O(1) [1] 1159.94/295.81 1159.94/295.81 ---------------------------------------- 1159.94/295.81 1159.94/295.81 (33) IntTrsBoundProof (UPPER BOUND(ID)) 1159.94/295.81 1159.94/295.81 Computed RUNTIME bound using CoFloCo for: or 1159.94/295.81 after applying outer abstraction to obtain an ITS, 1159.94/295.81 resulting in: O(1) with polynomial bound: 1 1159.94/295.81 1159.94/295.81 ---------------------------------------- 1159.94/295.81 1159.94/295.81 (34) 1159.94/295.81 Obligation: 1159.94/295.81 Complexity RNTS consisting of the following rules: 1159.94/295.81 1159.94/295.81 cond1(z', z'', z1, z2) -{ 2 }-> cond2(1, 1 + (z'' - 1), z1, z2) :|: z2 >= 0, z'' - 1 >= 0, z1 >= 0, z' = 1 1159.94/295.81 cond1(z', z'', z1, z2) -{ 2 }-> cond2(0, 0, z1, z2) :|: z'' = 0, z2 >= 0, z1 >= 0, z' = 1 1159.94/295.81 cond2(z', z'', z1, z2) -{ 2 }-> cond3(1, z'', 1 + (z1 - 1), z2) :|: z2 >= 0, z'' >= 0, z1 - 1 >= 0, z' = 0 1159.94/295.81 cond2(z', z'', z1, z2) -{ 2 }-> cond3(0, z'', 0, z2) :|: z1 = 0, z2 >= 0, z'' >= 0, z' = 0 1159.94/295.81 cond2(z', z'', z1, z2) -{ 5 + z2 }-> cond1(or(s'', 0), z'' - 1, 0, 1 + (z2 - 1)) :|: s'' >= 0, s'' <= 1, z1 = 0, z'' - 1 >= 0, z2 - 1 >= 0, z' = 1 1159.94/295.81 cond2(z', z'', z1, z2) -{ 6 + 2*z2 }-> cond1(or(s1, s2), z'' - 1, 1 + (z1 - 1), 1 + (z2 - 1)) :|: s1 >= 0, s1 <= 1, s2 >= 0, s2 <= 1, z'' - 1 >= 0, z1 - 1 >= 0, z2 - 1 >= 0, z' = 1 1159.94/295.81 cond2(z', z'', z1, z2) -{ 5 + z2 }-> cond1(or(0, s'), 0, 1 + (z1 - 1), 1 + (z2 - 1)) :|: s' >= 0, s' <= 1, z'' = 0, z2 - 1 >= 0, z' = 1, z1 - 1 >= 0 1159.94/295.81 cond2(z', z'', z1, z2) -{ 5 }-> cond1(1, 0, 1 + (z1 - 1), 0) :|: z'' = 0, z2 = 0, z' = 1, z1 - 1 >= 0, 0 = x, x >= 0, 1 = 1 1159.94/295.81 cond2(z', z'', z1, z2) -{ 5 }-> cond1(1, z'' - 1, 0, 0) :|: z1 = 0, z2 = 0, z' = 1, z'' - 1 >= 0, x >= 0, 0 = x, 1 = 1 1159.94/295.81 cond2(z', z'', z1, z2) -{ 5 }-> cond1(1, z'' - 1, 1 + (z1 - 1), 0) :|: z1 - 1 >= 0, z2 = 0, z' = 1, z'' - 1 >= 0, x >= 0, 1 = x, 1 = 1 1159.94/295.81 cond2(z', z'', z1, z2) -{ 5 }-> cond1(0, 0, 0, z2) :|: z'' = 0, z1 = 0, z2 >= 0, z' = 1, 0 = 0 1159.94/295.81 cond3(z', z'', z1, z2) -{ 5 + z2 }-> cond1(or(s4, 0), 1 + (z'' - 1), 0, 1 + (z2 - 1)) :|: s4 >= 0, s4 <= 1, z2 - 1 >= 0, z1 = 0, z'' - 1 >= 0, z' = 1 1159.94/295.81 cond3(z', z'', z1, z2) -{ 6 + 2*z2 }-> cond1(or(s5, s6), 1 + (z'' - 1), z1 - 1, 1 + (z2 - 1)) :|: s5 >= 0, s5 <= 1, s6 >= 0, s6 <= 1, z2 - 1 >= 0, z'' - 1 >= 0, z1 - 1 >= 0, z' = 1 1159.94/295.81 cond3(z', z'', z1, z2) -{ 4 + z2 }-> cond1(or(s8, 0), 1 + (z'' - 1), 0, 1 + (z2 - 1)) :|: s8 >= 0, s8 <= 1, z1 = 0, z2 - 1 >= 0, z'' - 1 >= 0, z' = 0 1159.94/295.81 cond3(z', z'', z1, z2) -{ 5 + 2*z2 }-> cond1(or(s9, s10), 1 + (z'' - 1), 1 + (z1 - 1), 1 + (z2 - 1)) :|: s9 >= 0, s9 <= 1, s10 >= 0, s10 <= 1, z2 - 1 >= 0, z'' - 1 >= 0, z1 - 1 >= 0, z' = 0 1159.94/295.81 cond3(z', z'', z1, z2) -{ 5 + z2 }-> cond1(or(0, s3), 0, z1 - 1, 1 + (z2 - 1)) :|: s3 >= 0, s3 <= 1, z'' = 0, z' = 1, z1 - 1 >= 0, z2 - 1 >= 0 1159.94/295.81 cond3(z', z'', z1, z2) -{ 4 + z2 }-> cond1(or(0, s7), 0, 1 + (z1 - 1), 1 + (z2 - 1)) :|: s7 >= 0, s7 <= 1, z'' = 0, z2 - 1 >= 0, z1 - 1 >= 0, z' = 0 1159.94/295.81 cond3(z', z'', z1, z2) -{ 5 }-> cond1(1, 0, z1 - 1, 0) :|: z'' = 0, z2 = 0, z' = 1, z1 - 1 >= 0, 0 = x, x >= 0, 1 = 1 1159.94/295.81 cond3(z', z'', z1, z2) -{ 4 }-> cond1(1, 0, 1 + (z1 - 1), 0) :|: z'' = 0, z2 = 0, z1 - 1 >= 0, z' = 0, 0 = x, x >= 0, 1 = 1 1159.94/295.81 cond3(z', z'', z1, z2) -{ 5 }-> cond1(1, 1 + (z'' - 1), 0, 0) :|: z1 = 0, z'' - 1 >= 0, z2 = 0, z' = 1, x >= 0, 0 = x, 1 = 1 1159.94/295.81 cond3(z', z'', z1, z2) -{ 4 }-> cond1(1, 1 + (z'' - 1), 0, 0) :|: z'' - 1 >= 0, z1 = 0, z2 = 0, z' = 0, x >= 0, 0 = x, 1 = 1 1159.94/295.81 cond3(z', z'', z1, z2) -{ 5 }-> cond1(1, 1 + (z'' - 1), z1 - 1, 0) :|: z'' - 1 >= 0, z2 = 0, z1 - 1 >= 0, z' = 1, x >= 0, 1 = x, 1 = 1 1159.94/295.81 cond3(z', z'', z1, z2) -{ 4 }-> cond1(1, 1 + (z'' - 1), 1 + (z1 - 1), 0) :|: z'' - 1 >= 0, z1 - 1 >= 0, z2 = 0, z' = 0, x >= 0, 1 = x, 1 = 1 1159.94/295.81 cond3(z', z'', z1, z2) -{ 5 }-> cond1(0, 0, 0, z2) :|: z'' = 0, z1 = 0, z2 >= 0, z' = 1, 0 = 0 1159.94/295.81 cond3(z', z'', z1, z2) -{ 4 }-> cond1(0, 0, 0, z2) :|: z'' = 0, z1 = 0, z2 >= 0, z' = 0, 0 = 0 1159.94/295.81 gr(z', z'') -{ 2 + z'' }-> s :|: s >= 0, s <= 1, z' - 1 >= 0, z'' - 1 >= 0 1159.94/295.81 gr(z', z'') -{ 1 }-> 1 :|: z'' = 0, z' - 1 >= 0 1159.94/295.81 gr(z', z'') -{ 1 }-> 0 :|: z'' >= 0, z' = 0 1159.94/295.81 or(z', z'') -{ 1 }-> 1 :|: z'' >= 0, z' = 1 1159.94/295.81 or(z', z'') -{ 1 }-> 1 :|: z' >= 0, z'' = 1 1159.94/295.81 or(z', z'') -{ 1 }-> 0 :|: z'' = 0, z' = 0 1159.94/295.81 p(z') -{ 1 }-> 0 :|: z' = 0 1159.94/295.81 p(z') -{ 1 }-> z' - 1 :|: z' - 1 >= 0 1159.94/295.81 1159.94/295.81 Function symbols to be analyzed: {cond1,cond2,cond3} 1159.94/295.81 Previous analysis results are: 1159.94/295.81 p: runtime: O(1) [1], size: O(n^1) [z'] 1159.94/295.81 gr: runtime: O(n^1) [2 + z''], size: O(1) [1] 1159.94/295.81 or: runtime: O(1) [1], size: O(1) [1] 1159.94/295.81 1159.94/295.81 ---------------------------------------- 1159.94/295.81 1159.94/295.81 (35) ResultPropagationProof (UPPER BOUND(ID)) 1159.94/295.81 Applied inner abstraction using the recently inferred runtime/size bounds where possible. 1159.94/295.81 ---------------------------------------- 1159.94/295.81 1159.94/295.81 (36) 1159.94/295.81 Obligation: 1159.94/295.81 Complexity RNTS consisting of the following rules: 1159.94/295.81 1159.94/295.81 cond1(z', z'', z1, z2) -{ 2 }-> cond2(1, 1 + (z'' - 1), z1, z2) :|: z2 >= 0, z'' - 1 >= 0, z1 >= 0, z' = 1 1159.94/295.81 cond1(z', z'', z1, z2) -{ 2 }-> cond2(0, 0, z1, z2) :|: z'' = 0, z2 >= 0, z1 >= 0, z' = 1 1159.94/295.81 cond2(z', z'', z1, z2) -{ 2 }-> cond3(1, z'', 1 + (z1 - 1), z2) :|: z2 >= 0, z'' >= 0, z1 - 1 >= 0, z' = 0 1159.94/295.81 cond2(z', z'', z1, z2) -{ 2 }-> cond3(0, z'', 0, z2) :|: z1 = 0, z2 >= 0, z'' >= 0, z' = 0 1159.94/295.81 cond2(z', z'', z1, z2) -{ 6 + z2 }-> cond1(s11, 0, 1 + (z1 - 1), 1 + (z2 - 1)) :|: s11 >= 0, s11 <= 1, s' >= 0, s' <= 1, z'' = 0, z2 - 1 >= 0, z' = 1, z1 - 1 >= 0 1159.94/295.81 cond2(z', z'', z1, z2) -{ 6 + z2 }-> cond1(s12, z'' - 1, 0, 1 + (z2 - 1)) :|: s12 >= 0, s12 <= 1, s'' >= 0, s'' <= 1, z1 = 0, z'' - 1 >= 0, z2 - 1 >= 0, z' = 1 1159.94/295.81 cond2(z', z'', z1, z2) -{ 7 + 2*z2 }-> cond1(s13, z'' - 1, 1 + (z1 - 1), 1 + (z2 - 1)) :|: s13 >= 0, s13 <= 1, s1 >= 0, s1 <= 1, s2 >= 0, s2 <= 1, z'' - 1 >= 0, z1 - 1 >= 0, z2 - 1 >= 0, z' = 1 1159.94/295.81 cond2(z', z'', z1, z2) -{ 5 }-> cond1(1, 0, 1 + (z1 - 1), 0) :|: z'' = 0, z2 = 0, z' = 1, z1 - 1 >= 0, 0 = x, x >= 0, 1 = 1 1159.94/295.81 cond2(z', z'', z1, z2) -{ 5 }-> cond1(1, z'' - 1, 0, 0) :|: z1 = 0, z2 = 0, z' = 1, z'' - 1 >= 0, x >= 0, 0 = x, 1 = 1 1159.94/295.81 cond2(z', z'', z1, z2) -{ 5 }-> cond1(1, z'' - 1, 1 + (z1 - 1), 0) :|: z1 - 1 >= 0, z2 = 0, z' = 1, z'' - 1 >= 0, x >= 0, 1 = x, 1 = 1 1159.94/295.81 cond2(z', z'', z1, z2) -{ 5 }-> cond1(0, 0, 0, z2) :|: z'' = 0, z1 = 0, z2 >= 0, z' = 1, 0 = 0 1159.94/295.81 cond3(z', z'', z1, z2) -{ 6 + z2 }-> cond1(s14, 0, z1 - 1, 1 + (z2 - 1)) :|: s14 >= 0, s14 <= 1, s3 >= 0, s3 <= 1, z'' = 0, z' = 1, z1 - 1 >= 0, z2 - 1 >= 0 1159.94/295.81 cond3(z', z'', z1, z2) -{ 6 + z2 }-> cond1(s15, 1 + (z'' - 1), 0, 1 + (z2 - 1)) :|: s15 >= 0, s15 <= 1, s4 >= 0, s4 <= 1, z2 - 1 >= 0, z1 = 0, z'' - 1 >= 0, z' = 1 1159.94/295.81 cond3(z', z'', z1, z2) -{ 7 + 2*z2 }-> cond1(s16, 1 + (z'' - 1), z1 - 1, 1 + (z2 - 1)) :|: s16 >= 0, s16 <= 1, s5 >= 0, s5 <= 1, s6 >= 0, s6 <= 1, z2 - 1 >= 0, z'' - 1 >= 0, z1 - 1 >= 0, z' = 1 1159.94/295.81 cond3(z', z'', z1, z2) -{ 5 + z2 }-> cond1(s17, 0, 1 + (z1 - 1), 1 + (z2 - 1)) :|: s17 >= 0, s17 <= 1, s7 >= 0, s7 <= 1, z'' = 0, z2 - 1 >= 0, z1 - 1 >= 0, z' = 0 1159.94/295.81 cond3(z', z'', z1, z2) -{ 5 + z2 }-> cond1(s18, 1 + (z'' - 1), 0, 1 + (z2 - 1)) :|: s18 >= 0, s18 <= 1, s8 >= 0, s8 <= 1, z1 = 0, z2 - 1 >= 0, z'' - 1 >= 0, z' = 0 1159.94/295.81 cond3(z', z'', z1, z2) -{ 6 + 2*z2 }-> cond1(s19, 1 + (z'' - 1), 1 + (z1 - 1), 1 + (z2 - 1)) :|: s19 >= 0, s19 <= 1, s9 >= 0, s9 <= 1, s10 >= 0, s10 <= 1, z2 - 1 >= 0, z'' - 1 >= 0, z1 - 1 >= 0, z' = 0 1159.94/295.81 cond3(z', z'', z1, z2) -{ 5 }-> cond1(1, 0, z1 - 1, 0) :|: z'' = 0, z2 = 0, z' = 1, z1 - 1 >= 0, 0 = x, x >= 0, 1 = 1 1159.94/295.81 cond3(z', z'', z1, z2) -{ 4 }-> cond1(1, 0, 1 + (z1 - 1), 0) :|: z'' = 0, z2 = 0, z1 - 1 >= 0, z' = 0, 0 = x, x >= 0, 1 = 1 1159.94/295.81 cond3(z', z'', z1, z2) -{ 5 }-> cond1(1, 1 + (z'' - 1), 0, 0) :|: z1 = 0, z'' - 1 >= 0, z2 = 0, z' = 1, x >= 0, 0 = x, 1 = 1 1159.94/295.81 cond3(z', z'', z1, z2) -{ 4 }-> cond1(1, 1 + (z'' - 1), 0, 0) :|: z'' - 1 >= 0, z1 = 0, z2 = 0, z' = 0, x >= 0, 0 = x, 1 = 1 1159.94/295.81 cond3(z', z'', z1, z2) -{ 5 }-> cond1(1, 1 + (z'' - 1), z1 - 1, 0) :|: z'' - 1 >= 0, z2 = 0, z1 - 1 >= 0, z' = 1, x >= 0, 1 = x, 1 = 1 1159.94/295.81 cond3(z', z'', z1, z2) -{ 4 }-> cond1(1, 1 + (z'' - 1), 1 + (z1 - 1), 0) :|: z'' - 1 >= 0, z1 - 1 >= 0, z2 = 0, z' = 0, x >= 0, 1 = x, 1 = 1 1159.94/295.81 cond3(z', z'', z1, z2) -{ 5 }-> cond1(0, 0, 0, z2) :|: z'' = 0, z1 = 0, z2 >= 0, z' = 1, 0 = 0 1159.94/295.81 cond3(z', z'', z1, z2) -{ 4 }-> cond1(0, 0, 0, z2) :|: z'' = 0, z1 = 0, z2 >= 0, z' = 0, 0 = 0 1159.94/295.81 gr(z', z'') -{ 2 + z'' }-> s :|: s >= 0, s <= 1, z' - 1 >= 0, z'' - 1 >= 0 1159.94/295.81 gr(z', z'') -{ 1 }-> 1 :|: z'' = 0, z' - 1 >= 0 1159.94/295.81 gr(z', z'') -{ 1 }-> 0 :|: z'' >= 0, z' = 0 1159.94/295.81 or(z', z'') -{ 1 }-> 1 :|: z'' >= 0, z' = 1 1159.94/295.81 or(z', z'') -{ 1 }-> 1 :|: z' >= 0, z'' = 1 1159.94/295.81 or(z', z'') -{ 1 }-> 0 :|: z'' = 0, z' = 0 1159.94/295.81 p(z') -{ 1 }-> 0 :|: z' = 0 1159.94/295.81 p(z') -{ 1 }-> z' - 1 :|: z' - 1 >= 0 1159.94/295.81 1159.94/295.81 Function symbols to be analyzed: {cond1,cond2,cond3} 1159.94/295.81 Previous analysis results are: 1159.94/295.81 p: runtime: O(1) [1], size: O(n^1) [z'] 1159.94/295.81 gr: runtime: O(n^1) [2 + z''], size: O(1) [1] 1159.94/295.81 or: runtime: O(1) [1], size: O(1) [1] 1159.94/295.81 1159.94/295.81 ---------------------------------------- 1159.94/295.81 1159.94/295.81 (37) IntTrsBoundProof (UPPER BOUND(ID)) 1159.94/295.81 1159.94/295.81 Computed SIZE bound using CoFloCo for: cond1 1159.94/295.81 after applying outer abstraction to obtain an ITS, 1159.94/295.81 resulting in: O(1) with polynomial bound: 0 1159.94/295.81 1159.94/295.81 Computed SIZE bound using CoFloCo for: cond2 1159.94/295.81 after applying outer abstraction to obtain an ITS, 1159.94/295.81 resulting in: O(1) with polynomial bound: 0 1159.94/295.81 1159.94/295.81 Computed SIZE bound using CoFloCo for: cond3 1159.94/295.81 after applying outer abstraction to obtain an ITS, 1159.94/295.81 resulting in: O(1) with polynomial bound: 0 1159.94/295.81 1159.94/295.81 ---------------------------------------- 1159.94/295.81 1159.94/295.81 (38) 1159.94/295.81 Obligation: 1159.94/295.81 Complexity RNTS consisting of the following rules: 1159.94/295.81 1159.94/295.81 cond1(z', z'', z1, z2) -{ 2 }-> cond2(1, 1 + (z'' - 1), z1, z2) :|: z2 >= 0, z'' - 1 >= 0, z1 >= 0, z' = 1 1159.94/295.81 cond1(z', z'', z1, z2) -{ 2 }-> cond2(0, 0, z1, z2) :|: z'' = 0, z2 >= 0, z1 >= 0, z' = 1 1159.94/295.81 cond2(z', z'', z1, z2) -{ 2 }-> cond3(1, z'', 1 + (z1 - 1), z2) :|: z2 >= 0, z'' >= 0, z1 - 1 >= 0, z' = 0 1159.94/295.81 cond2(z', z'', z1, z2) -{ 2 }-> cond3(0, z'', 0, z2) :|: z1 = 0, z2 >= 0, z'' >= 0, z' = 0 1159.94/295.81 cond2(z', z'', z1, z2) -{ 6 + z2 }-> cond1(s11, 0, 1 + (z1 - 1), 1 + (z2 - 1)) :|: s11 >= 0, s11 <= 1, s' >= 0, s' <= 1, z'' = 0, z2 - 1 >= 0, z' = 1, z1 - 1 >= 0 1159.94/295.81 cond2(z', z'', z1, z2) -{ 6 + z2 }-> cond1(s12, z'' - 1, 0, 1 + (z2 - 1)) :|: s12 >= 0, s12 <= 1, s'' >= 0, s'' <= 1, z1 = 0, z'' - 1 >= 0, z2 - 1 >= 0, z' = 1 1159.94/295.81 cond2(z', z'', z1, z2) -{ 7 + 2*z2 }-> cond1(s13, z'' - 1, 1 + (z1 - 1), 1 + (z2 - 1)) :|: s13 >= 0, s13 <= 1, s1 >= 0, s1 <= 1, s2 >= 0, s2 <= 1, z'' - 1 >= 0, z1 - 1 >= 0, z2 - 1 >= 0, z' = 1 1159.94/295.81 cond2(z', z'', z1, z2) -{ 5 }-> cond1(1, 0, 1 + (z1 - 1), 0) :|: z'' = 0, z2 = 0, z' = 1, z1 - 1 >= 0, 0 = x, x >= 0, 1 = 1 1159.94/295.81 cond2(z', z'', z1, z2) -{ 5 }-> cond1(1, z'' - 1, 0, 0) :|: z1 = 0, z2 = 0, z' = 1, z'' - 1 >= 0, x >= 0, 0 = x, 1 = 1 1159.94/295.81 cond2(z', z'', z1, z2) -{ 5 }-> cond1(1, z'' - 1, 1 + (z1 - 1), 0) :|: z1 - 1 >= 0, z2 = 0, z' = 1, z'' - 1 >= 0, x >= 0, 1 = x, 1 = 1 1159.94/295.81 cond2(z', z'', z1, z2) -{ 5 }-> cond1(0, 0, 0, z2) :|: z'' = 0, z1 = 0, z2 >= 0, z' = 1, 0 = 0 1159.94/295.81 cond3(z', z'', z1, z2) -{ 6 + z2 }-> cond1(s14, 0, z1 - 1, 1 + (z2 - 1)) :|: s14 >= 0, s14 <= 1, s3 >= 0, s3 <= 1, z'' = 0, z' = 1, z1 - 1 >= 0, z2 - 1 >= 0 1159.94/295.81 cond3(z', z'', z1, z2) -{ 6 + z2 }-> cond1(s15, 1 + (z'' - 1), 0, 1 + (z2 - 1)) :|: s15 >= 0, s15 <= 1, s4 >= 0, s4 <= 1, z2 - 1 >= 0, z1 = 0, z'' - 1 >= 0, z' = 1 1159.94/295.81 cond3(z', z'', z1, z2) -{ 7 + 2*z2 }-> cond1(s16, 1 + (z'' - 1), z1 - 1, 1 + (z2 - 1)) :|: s16 >= 0, s16 <= 1, s5 >= 0, s5 <= 1, s6 >= 0, s6 <= 1, z2 - 1 >= 0, z'' - 1 >= 0, z1 - 1 >= 0, z' = 1 1159.94/295.81 cond3(z', z'', z1, z2) -{ 5 + z2 }-> cond1(s17, 0, 1 + (z1 - 1), 1 + (z2 - 1)) :|: s17 >= 0, s17 <= 1, s7 >= 0, s7 <= 1, z'' = 0, z2 - 1 >= 0, z1 - 1 >= 0, z' = 0 1159.94/295.81 cond3(z', z'', z1, z2) -{ 5 + z2 }-> cond1(s18, 1 + (z'' - 1), 0, 1 + (z2 - 1)) :|: s18 >= 0, s18 <= 1, s8 >= 0, s8 <= 1, z1 = 0, z2 - 1 >= 0, z'' - 1 >= 0, z' = 0 1159.94/295.81 cond3(z', z'', z1, z2) -{ 6 + 2*z2 }-> cond1(s19, 1 + (z'' - 1), 1 + (z1 - 1), 1 + (z2 - 1)) :|: s19 >= 0, s19 <= 1, s9 >= 0, s9 <= 1, s10 >= 0, s10 <= 1, z2 - 1 >= 0, z'' - 1 >= 0, z1 - 1 >= 0, z' = 0 1159.94/295.81 cond3(z', z'', z1, z2) -{ 5 }-> cond1(1, 0, z1 - 1, 0) :|: z'' = 0, z2 = 0, z' = 1, z1 - 1 >= 0, 0 = x, x >= 0, 1 = 1 1159.94/295.81 cond3(z', z'', z1, z2) -{ 4 }-> cond1(1, 0, 1 + (z1 - 1), 0) :|: z'' = 0, z2 = 0, z1 - 1 >= 0, z' = 0, 0 = x, x >= 0, 1 = 1 1159.94/295.81 cond3(z', z'', z1, z2) -{ 5 }-> cond1(1, 1 + (z'' - 1), 0, 0) :|: z1 = 0, z'' - 1 >= 0, z2 = 0, z' = 1, x >= 0, 0 = x, 1 = 1 1159.94/295.81 cond3(z', z'', z1, z2) -{ 4 }-> cond1(1, 1 + (z'' - 1), 0, 0) :|: z'' - 1 >= 0, z1 = 0, z2 = 0, z' = 0, x >= 0, 0 = x, 1 = 1 1159.94/295.81 cond3(z', z'', z1, z2) -{ 5 }-> cond1(1, 1 + (z'' - 1), z1 - 1, 0) :|: z'' - 1 >= 0, z2 = 0, z1 - 1 >= 0, z' = 1, x >= 0, 1 = x, 1 = 1 1159.94/295.81 cond3(z', z'', z1, z2) -{ 4 }-> cond1(1, 1 + (z'' - 1), 1 + (z1 - 1), 0) :|: z'' - 1 >= 0, z1 - 1 >= 0, z2 = 0, z' = 0, x >= 0, 1 = x, 1 = 1 1159.94/295.81 cond3(z', z'', z1, z2) -{ 5 }-> cond1(0, 0, 0, z2) :|: z'' = 0, z1 = 0, z2 >= 0, z' = 1, 0 = 0 1159.94/295.81 cond3(z', z'', z1, z2) -{ 4 }-> cond1(0, 0, 0, z2) :|: z'' = 0, z1 = 0, z2 >= 0, z' = 0, 0 = 0 1159.94/295.81 gr(z', z'') -{ 2 + z'' }-> s :|: s >= 0, s <= 1, z' - 1 >= 0, z'' - 1 >= 0 1159.94/295.81 gr(z', z'') -{ 1 }-> 1 :|: z'' = 0, z' - 1 >= 0 1159.94/295.81 gr(z', z'') -{ 1 }-> 0 :|: z'' >= 0, z' = 0 1159.94/295.81 or(z', z'') -{ 1 }-> 1 :|: z'' >= 0, z' = 1 1159.94/295.81 or(z', z'') -{ 1 }-> 1 :|: z' >= 0, z'' = 1 1159.94/295.81 or(z', z'') -{ 1 }-> 0 :|: z'' = 0, z' = 0 1159.94/295.81 p(z') -{ 1 }-> 0 :|: z' = 0 1159.94/295.81 p(z') -{ 1 }-> z' - 1 :|: z' - 1 >= 0 1159.94/295.81 1159.94/295.81 Function symbols to be analyzed: {cond1,cond2,cond3} 1159.94/295.81 Previous analysis results are: 1159.94/295.81 p: runtime: O(1) [1], size: O(n^1) [z'] 1159.94/295.81 gr: runtime: O(n^1) [2 + z''], size: O(1) [1] 1159.94/295.81 or: runtime: O(1) [1], size: O(1) [1] 1159.94/295.81 cond1: runtime: ?, size: O(1) [0] 1159.94/295.81 cond2: runtime: ?, size: O(1) [0] 1159.94/295.81 cond3: runtime: ?, size: O(1) [0] 1159.94/295.81 1159.94/295.81 ---------------------------------------- 1159.94/295.81 1159.94/295.81 (39) IntTrsBoundProof (UPPER BOUND(ID)) 1159.94/295.81 1159.94/295.81 Computed RUNTIME bound using CoFloCo for: cond1 1159.94/295.81 after applying outer abstraction to obtain an ITS, 1159.94/295.82 resulting in: O(n^2) with polynomial bound: 14 + 9*z'' + 2*z''*z2 + 10*z1 + z1*z2 + 2*z2 1159.94/295.82 1159.94/295.82 Computed RUNTIME bound using KoAT for: cond2 1159.94/295.82 after applying outer abstraction to obtain an ITS, 1159.94/295.82 resulting in: O(n^2) with polynomial bound: 199 + 72*z'' + 8*z''*z2 + 80*z1 + 4*z1*z2 + 18*z2 1159.94/295.82 1159.94/295.82 Computed RUNTIME bound using KoAT for: cond3 1159.94/295.82 after applying outer abstraction to obtain an ITS, 1159.94/295.82 resulting in: O(n^2) with polynomial bound: 227 + 72*z'' + 8*z''*z2 + 80*z1 + 4*z1*z2 + 22*z2 1159.94/295.82 1159.94/295.82 ---------------------------------------- 1159.94/295.82 1159.94/295.82 (40) 1159.94/295.82 Obligation: 1159.94/295.82 Complexity RNTS consisting of the following rules: 1159.94/295.82 1159.94/295.82 cond1(z', z'', z1, z2) -{ 2 }-> cond2(1, 1 + (z'' - 1), z1, z2) :|: z2 >= 0, z'' - 1 >= 0, z1 >= 0, z' = 1 1159.94/295.82 cond1(z', z'', z1, z2) -{ 2 }-> cond2(0, 0, z1, z2) :|: z'' = 0, z2 >= 0, z1 >= 0, z' = 1 1159.94/295.82 cond2(z', z'', z1, z2) -{ 2 }-> cond3(1, z'', 1 + (z1 - 1), z2) :|: z2 >= 0, z'' >= 0, z1 - 1 >= 0, z' = 0 1159.94/295.82 cond2(z', z'', z1, z2) -{ 2 }-> cond3(0, z'', 0, z2) :|: z1 = 0, z2 >= 0, z'' >= 0, z' = 0 1159.94/295.82 cond2(z', z'', z1, z2) -{ 6 + z2 }-> cond1(s11, 0, 1 + (z1 - 1), 1 + (z2 - 1)) :|: s11 >= 0, s11 <= 1, s' >= 0, s' <= 1, z'' = 0, z2 - 1 >= 0, z' = 1, z1 - 1 >= 0 1159.94/295.82 cond2(z', z'', z1, z2) -{ 6 + z2 }-> cond1(s12, z'' - 1, 0, 1 + (z2 - 1)) :|: s12 >= 0, s12 <= 1, s'' >= 0, s'' <= 1, z1 = 0, z'' - 1 >= 0, z2 - 1 >= 0, z' = 1 1159.94/295.82 cond2(z', z'', z1, z2) -{ 7 + 2*z2 }-> cond1(s13, z'' - 1, 1 + (z1 - 1), 1 + (z2 - 1)) :|: s13 >= 0, s13 <= 1, s1 >= 0, s1 <= 1, s2 >= 0, s2 <= 1, z'' - 1 >= 0, z1 - 1 >= 0, z2 - 1 >= 0, z' = 1 1159.94/295.82 cond2(z', z'', z1, z2) -{ 5 }-> cond1(1, 0, 1 + (z1 - 1), 0) :|: z'' = 0, z2 = 0, z' = 1, z1 - 1 >= 0, 0 = x, x >= 0, 1 = 1 1159.94/295.82 cond2(z', z'', z1, z2) -{ 5 }-> cond1(1, z'' - 1, 0, 0) :|: z1 = 0, z2 = 0, z' = 1, z'' - 1 >= 0, x >= 0, 0 = x, 1 = 1 1159.94/295.82 cond2(z', z'', z1, z2) -{ 5 }-> cond1(1, z'' - 1, 1 + (z1 - 1), 0) :|: z1 - 1 >= 0, z2 = 0, z' = 1, z'' - 1 >= 0, x >= 0, 1 = x, 1 = 1 1159.94/295.82 cond2(z', z'', z1, z2) -{ 5 }-> cond1(0, 0, 0, z2) :|: z'' = 0, z1 = 0, z2 >= 0, z' = 1, 0 = 0 1159.94/295.82 cond3(z', z'', z1, z2) -{ 6 + z2 }-> cond1(s14, 0, z1 - 1, 1 + (z2 - 1)) :|: s14 >= 0, s14 <= 1, s3 >= 0, s3 <= 1, z'' = 0, z' = 1, z1 - 1 >= 0, z2 - 1 >= 0 1159.94/295.82 cond3(z', z'', z1, z2) -{ 6 + z2 }-> cond1(s15, 1 + (z'' - 1), 0, 1 + (z2 - 1)) :|: s15 >= 0, s15 <= 1, s4 >= 0, s4 <= 1, z2 - 1 >= 0, z1 = 0, z'' - 1 >= 0, z' = 1 1159.94/295.82 cond3(z', z'', z1, z2) -{ 7 + 2*z2 }-> cond1(s16, 1 + (z'' - 1), z1 - 1, 1 + (z2 - 1)) :|: s16 >= 0, s16 <= 1, s5 >= 0, s5 <= 1, s6 >= 0, s6 <= 1, z2 - 1 >= 0, z'' - 1 >= 0, z1 - 1 >= 0, z' = 1 1159.94/295.82 cond3(z', z'', z1, z2) -{ 5 + z2 }-> cond1(s17, 0, 1 + (z1 - 1), 1 + (z2 - 1)) :|: s17 >= 0, s17 <= 1, s7 >= 0, s7 <= 1, z'' = 0, z2 - 1 >= 0, z1 - 1 >= 0, z' = 0 1159.94/295.82 cond3(z', z'', z1, z2) -{ 5 + z2 }-> cond1(s18, 1 + (z'' - 1), 0, 1 + (z2 - 1)) :|: s18 >= 0, s18 <= 1, s8 >= 0, s8 <= 1, z1 = 0, z2 - 1 >= 0, z'' - 1 >= 0, z' = 0 1159.94/295.82 cond3(z', z'', z1, z2) -{ 6 + 2*z2 }-> cond1(s19, 1 + (z'' - 1), 1 + (z1 - 1), 1 + (z2 - 1)) :|: s19 >= 0, s19 <= 1, s9 >= 0, s9 <= 1, s10 >= 0, s10 <= 1, z2 - 1 >= 0, z'' - 1 >= 0, z1 - 1 >= 0, z' = 0 1159.94/295.82 cond3(z', z'', z1, z2) -{ 5 }-> cond1(1, 0, z1 - 1, 0) :|: z'' = 0, z2 = 0, z' = 1, z1 - 1 >= 0, 0 = x, x >= 0, 1 = 1 1159.94/295.82 cond3(z', z'', z1, z2) -{ 4 }-> cond1(1, 0, 1 + (z1 - 1), 0) :|: z'' = 0, z2 = 0, z1 - 1 >= 0, z' = 0, 0 = x, x >= 0, 1 = 1 1159.94/295.82 cond3(z', z'', z1, z2) -{ 5 }-> cond1(1, 1 + (z'' - 1), 0, 0) :|: z1 = 0, z'' - 1 >= 0, z2 = 0, z' = 1, x >= 0, 0 = x, 1 = 1 1159.94/295.82 cond3(z', z'', z1, z2) -{ 4 }-> cond1(1, 1 + (z'' - 1), 0, 0) :|: z'' - 1 >= 0, z1 = 0, z2 = 0, z' = 0, x >= 0, 0 = x, 1 = 1 1159.94/295.82 cond3(z', z'', z1, z2) -{ 5 }-> cond1(1, 1 + (z'' - 1), z1 - 1, 0) :|: z'' - 1 >= 0, z2 = 0, z1 - 1 >= 0, z' = 1, x >= 0, 1 = x, 1 = 1 1159.94/295.82 cond3(z', z'', z1, z2) -{ 4 }-> cond1(1, 1 + (z'' - 1), 1 + (z1 - 1), 0) :|: z'' - 1 >= 0, z1 - 1 >= 0, z2 = 0, z' = 0, x >= 0, 1 = x, 1 = 1 1159.94/295.82 cond3(z', z'', z1, z2) -{ 5 }-> cond1(0, 0, 0, z2) :|: z'' = 0, z1 = 0, z2 >= 0, z' = 1, 0 = 0 1159.94/295.82 cond3(z', z'', z1, z2) -{ 4 }-> cond1(0, 0, 0, z2) :|: z'' = 0, z1 = 0, z2 >= 0, z' = 0, 0 = 0 1159.94/295.82 gr(z', z'') -{ 2 + z'' }-> s :|: s >= 0, s <= 1, z' - 1 >= 0, z'' - 1 >= 0 1159.94/295.82 gr(z', z'') -{ 1 }-> 1 :|: z'' = 0, z' - 1 >= 0 1159.94/295.82 gr(z', z'') -{ 1 }-> 0 :|: z'' >= 0, z' = 0 1159.94/295.82 or(z', z'') -{ 1 }-> 1 :|: z'' >= 0, z' = 1 1159.94/295.82 or(z', z'') -{ 1 }-> 1 :|: z' >= 0, z'' = 1 1159.94/295.82 or(z', z'') -{ 1 }-> 0 :|: z'' = 0, z' = 0 1159.94/295.82 p(z') -{ 1 }-> 0 :|: z' = 0 1159.94/295.82 p(z') -{ 1 }-> z' - 1 :|: z' - 1 >= 0 1159.94/295.82 1159.94/295.82 Function symbols to be analyzed: 1159.94/295.82 Previous analysis results are: 1159.94/295.82 p: runtime: O(1) [1], size: O(n^1) [z'] 1159.94/295.82 gr: runtime: O(n^1) [2 + z''], size: O(1) [1] 1159.94/295.82 or: runtime: O(1) [1], size: O(1) [1] 1159.94/295.82 cond1: runtime: O(n^2) [14 + 9*z'' + 2*z''*z2 + 10*z1 + z1*z2 + 2*z2], size: O(1) [0] 1159.94/295.82 cond2: runtime: O(n^2) [199 + 72*z'' + 8*z''*z2 + 80*z1 + 4*z1*z2 + 18*z2], size: O(1) [0] 1159.94/295.82 cond3: runtime: O(n^2) [227 + 72*z'' + 8*z''*z2 + 80*z1 + 4*z1*z2 + 22*z2], size: O(1) [0] 1159.94/295.82 1159.94/295.82 ---------------------------------------- 1159.94/295.82 1159.94/295.82 (41) FinalProof (FINISHED) 1159.94/295.82 Computed overall runtime complexity 1159.94/295.82 ---------------------------------------- 1159.94/295.82 1159.94/295.82 (42) 1159.94/295.82 BOUNDS(1, n^2) 1159.94/295.82 1159.94/295.82 ---------------------------------------- 1159.94/295.82 1159.94/295.82 (43) RelTrsToDecreasingLoopProblemProof (LOWER BOUND(ID)) 1159.94/295.82 Transformed a relative TRS into a decreasing-loop problem. 1159.94/295.82 ---------------------------------------- 1159.94/295.82 1159.94/295.82 (44) 1159.94/295.82 Obligation: 1159.94/295.82 Analyzing the following TRS for decreasing loops: 1159.94/295.82 1159.94/295.82 The Runtime Complexity (innermost) of the given CpxTRS could be proven to be BOUNDS(n^1, n^2). 1159.94/295.82 1159.94/295.82 1159.94/295.82 The TRS R consists of the following rules: 1159.94/295.82 1159.94/295.82 cond1(true, x, y, z) -> cond2(gr(x, 0), x, y, z) 1159.94/295.82 cond2(true, x, y, z) -> cond1(or(gr(x, z), gr(y, z)), p(x), y, z) 1159.94/295.82 cond2(false, x, y, z) -> cond3(gr(y, 0), x, y, z) 1159.94/295.82 cond3(true, x, y, z) -> cond1(or(gr(x, z), gr(y, z)), x, p(y), z) 1159.94/295.82 cond3(false, x, y, z) -> cond1(or(gr(x, z), gr(y, z)), x, y, z) 1159.94/295.82 gr(0, x) -> false 1159.94/295.82 gr(s(x), 0) -> true 1159.94/295.82 gr(s(x), s(y)) -> gr(x, y) 1159.94/295.82 or(false, false) -> false 1159.94/295.82 or(true, x) -> true 1159.94/295.82 or(x, true) -> true 1159.94/295.82 p(0) -> 0 1159.94/295.82 p(s(x)) -> x 1159.94/295.82 1159.94/295.82 S is empty. 1159.94/295.82 Rewrite Strategy: INNERMOST 1159.94/295.82 ---------------------------------------- 1159.94/295.82 1159.94/295.82 (45) DecreasingLoopProof (LOWER BOUND(ID)) 1159.94/295.82 The following loop(s) give(s) rise to the lower bound Omega(n^1): 1159.94/295.82 1159.94/295.82 The rewrite sequence 1159.94/295.82 1159.94/295.82 gr(s(x), s(y)) ->^+ gr(x, y) 1159.94/295.82 1159.94/295.82 gives rise to a decreasing loop by considering the right hand sides subterm at position []. 1159.94/295.82 1159.94/295.82 The pumping substitution is [x / s(x), y / s(y)]. 1159.94/295.82 1159.94/295.82 The result substitution is [ ]. 1159.94/295.82 1159.94/295.82 1159.94/295.82 1159.94/295.82 1159.94/295.82 ---------------------------------------- 1159.94/295.82 1159.94/295.82 (46) 1159.94/295.82 Complex Obligation (BEST) 1159.94/295.82 1159.94/295.82 ---------------------------------------- 1159.94/295.82 1159.94/295.82 (47) 1159.94/295.82 Obligation: 1159.94/295.82 Proved the lower bound n^1 for the following obligation: 1159.94/295.82 1159.94/295.82 The Runtime Complexity (innermost) of the given CpxTRS could be proven to be BOUNDS(n^1, n^2). 1159.94/295.82 1159.94/295.82 1159.94/295.82 The TRS R consists of the following rules: 1159.94/295.82 1159.94/295.82 cond1(true, x, y, z) -> cond2(gr(x, 0), x, y, z) 1159.94/295.82 cond2(true, x, y, z) -> cond1(or(gr(x, z), gr(y, z)), p(x), y, z) 1159.94/295.82 cond2(false, x, y, z) -> cond3(gr(y, 0), x, y, z) 1159.94/295.82 cond3(true, x, y, z) -> cond1(or(gr(x, z), gr(y, z)), x, p(y), z) 1159.94/295.82 cond3(false, x, y, z) -> cond1(or(gr(x, z), gr(y, z)), x, y, z) 1159.94/295.82 gr(0, x) -> false 1159.94/295.82 gr(s(x), 0) -> true 1159.94/295.82 gr(s(x), s(y)) -> gr(x, y) 1159.94/295.82 or(false, false) -> false 1159.94/295.82 or(true, x) -> true 1159.94/295.82 or(x, true) -> true 1159.94/295.82 p(0) -> 0 1159.94/295.82 p(s(x)) -> x 1159.94/295.82 1159.94/295.82 S is empty. 1159.94/295.82 Rewrite Strategy: INNERMOST 1159.94/295.82 ---------------------------------------- 1159.94/295.82 1159.94/295.82 (48) LowerBoundPropagationProof (FINISHED) 1159.94/295.82 Propagated lower bound. 1159.94/295.82 ---------------------------------------- 1159.94/295.82 1159.94/295.82 (49) 1159.94/295.82 BOUNDS(n^1, INF) 1159.94/295.82 1159.94/295.82 ---------------------------------------- 1159.94/295.82 1159.94/295.82 (50) 1159.94/295.82 Obligation: 1159.94/295.82 Analyzing the following TRS for decreasing loops: 1159.94/295.82 1159.94/295.82 The Runtime Complexity (innermost) of the given CpxTRS could be proven to be BOUNDS(n^1, n^2). 1159.94/295.82 1159.94/295.82 1159.94/295.82 The TRS R consists of the following rules: 1159.94/295.82 1159.94/295.82 cond1(true, x, y, z) -> cond2(gr(x, 0), x, y, z) 1159.94/295.82 cond2(true, x, y, z) -> cond1(or(gr(x, z), gr(y, z)), p(x), y, z) 1159.94/295.82 cond2(false, x, y, z) -> cond3(gr(y, 0), x, y, z) 1159.94/295.82 cond3(true, x, y, z) -> cond1(or(gr(x, z), gr(y, z)), x, p(y), z) 1159.94/295.82 cond3(false, x, y, z) -> cond1(or(gr(x, z), gr(y, z)), x, y, z) 1159.94/295.82 gr(0, x) -> false 1159.94/295.82 gr(s(x), 0) -> true 1159.94/295.82 gr(s(x), s(y)) -> gr(x, y) 1159.94/295.82 or(false, false) -> false 1159.94/295.82 or(true, x) -> true 1159.94/295.82 or(x, true) -> true 1159.94/295.82 p(0) -> 0 1159.94/295.82 p(s(x)) -> x 1159.94/295.82 1159.94/295.82 S is empty. 1159.94/295.82 Rewrite Strategy: INNERMOST 1160.32/295.92 EOF