75.73/20.44 WORST_CASE(Omega(n^1), O(n^1)) 75.95/20.48 proof of /export/starexec/sandbox2/benchmark/theBenchmark.xml 75.95/20.48 # AProVE Commit ID: 48fb2092695e11cc9f56e44b17a92a5f88ffb256 marcel 20180622 unpublished dirty 75.95/20.48 75.95/20.48 75.95/20.48 The Runtime Complexity (innermost) of the given CpxTRS could be proven to be BOUNDS(n^1, n^1). 75.95/20.48 75.95/20.48 (0) CpxTRS 75.95/20.48 (1) RelTrsToWeightedTrsProof [BOTH BOUNDS(ID, ID), 0 ms] 75.95/20.48 (2) CpxWeightedTrs 75.95/20.48 (3) TypeInferenceProof [BOTH BOUNDS(ID, ID), 0 ms] 75.95/20.48 (4) CpxTypedWeightedTrs 75.95/20.48 (5) CompletionProof [UPPER BOUND(ID), 0 ms] 75.95/20.48 (6) CpxTypedWeightedCompleteTrs 75.95/20.48 (7) NarrowingProof [BOTH BOUNDS(ID, ID), 0 ms] 75.95/20.48 (8) CpxTypedWeightedCompleteTrs 75.95/20.48 (9) CpxTypedWeightedTrsToRntsProof [UPPER BOUND(ID), 0 ms] 75.95/20.48 (10) CpxRNTS 75.95/20.48 (11) InliningProof [UPPER BOUND(ID), 639 ms] 75.95/20.48 (12) CpxRNTS 75.95/20.48 (13) SimplificationProof [BOTH BOUNDS(ID, ID), 0 ms] 75.95/20.48 (14) CpxRNTS 75.95/20.48 (15) CpxRntsAnalysisOrderProof [BOTH BOUNDS(ID, ID), 0 ms] 75.95/20.48 (16) CpxRNTS 75.95/20.48 (17) ResultPropagationProof [UPPER BOUND(ID), 0 ms] 75.95/20.48 (18) CpxRNTS 75.95/20.48 (19) IntTrsBoundProof [UPPER BOUND(ID), 3925 ms] 75.95/20.48 (20) CpxRNTS 75.95/20.48 (21) IntTrsBoundProof [UPPER BOUND(ID), 1898 ms] 75.95/20.48 (22) CpxRNTS 75.95/20.48 (23) ResultPropagationProof [UPPER BOUND(ID), 0 ms] 75.95/20.48 (24) CpxRNTS 75.95/20.48 (25) IntTrsBoundProof [UPPER BOUND(ID), 148 ms] 75.95/20.48 (26) CpxRNTS 75.95/20.48 (27) IntTrsBoundProof [UPPER BOUND(ID), 52 ms] 75.95/20.48 (28) CpxRNTS 75.95/20.48 (29) ResultPropagationProof [UPPER BOUND(ID), 0 ms] 75.95/20.48 (30) CpxRNTS 75.95/20.48 (31) IntTrsBoundProof [UPPER BOUND(ID), 388 ms] 75.95/20.48 (32) CpxRNTS 75.95/20.48 (33) IntTrsBoundProof [UPPER BOUND(ID), 114 ms] 75.95/20.48 (34) CpxRNTS 75.95/20.48 (35) ResultPropagationProof [UPPER BOUND(ID), 0 ms] 75.95/20.48 (36) CpxRNTS 75.95/20.48 (37) IntTrsBoundProof [UPPER BOUND(ID), 118 ms] 75.95/20.48 (38) CpxRNTS 75.95/20.48 (39) IntTrsBoundProof [UPPER BOUND(ID), 72 ms] 75.95/20.48 (40) CpxRNTS 75.95/20.48 (41) FinalProof [FINISHED, 0 ms] 75.95/20.48 (42) BOUNDS(1, n^1) 75.95/20.48 (43) RenamingProof [BOTH BOUNDS(ID, ID), 0 ms] 75.95/20.48 (44) CpxTRS 75.95/20.48 (45) TypeInferenceProof [BOTH BOUNDS(ID, ID), 0 ms] 75.95/20.48 (46) typed CpxTrs 75.95/20.48 (47) OrderProof [LOWER BOUND(ID), 0 ms] 75.95/20.48 (48) typed CpxTrs 75.95/20.48 (49) RewriteLemmaProof [LOWER BOUND(ID), 293 ms] 75.95/20.48 (50) BEST 75.95/20.48 (51) proven lower bound 75.95/20.48 (52) LowerBoundPropagationProof [FINISHED, 0 ms] 75.95/20.48 (53) BOUNDS(n^1, INF) 75.95/20.48 (54) typed CpxTrs 75.95/20.48 75.95/20.48 75.95/20.48 ---------------------------------------- 75.95/20.48 75.95/20.48 (0) 75.95/20.48 Obligation: 75.95/20.48 The Runtime Complexity (innermost) of the given CpxTRS could be proven to be BOUNDS(n^1, n^1). 75.95/20.48 75.95/20.48 75.95/20.48 The TRS R consists of the following rules: 75.95/20.48 75.95/20.48 cond1(true, x, y) -> cond2(gr(x, 0), x, y) 75.95/20.48 cond2(true, x, y) -> cond1(or(gr(x, 0), gr(y, 0)), p(x), y) 75.95/20.48 cond2(false, x, y) -> cond3(gr(y, 0), x, y) 75.95/20.48 cond3(true, x, y) -> cond1(or(gr(x, 0), gr(y, 0)), x, p(y)) 75.95/20.48 cond3(false, x, y) -> cond1(or(gr(x, 0), gr(y, 0)), x, y) 75.95/20.48 gr(0, x) -> false 75.95/20.48 gr(s(x), 0) -> true 75.95/20.48 gr(s(x), s(y)) -> gr(x, y) 75.95/20.48 or(false, false) -> false 75.95/20.48 or(true, x) -> true 75.95/20.48 or(x, true) -> true 75.95/20.48 p(0) -> 0 75.95/20.48 p(s(x)) -> x 75.95/20.48 75.95/20.48 S is empty. 75.95/20.48 Rewrite Strategy: INNERMOST 75.95/20.48 ---------------------------------------- 75.95/20.48 75.95/20.48 (1) RelTrsToWeightedTrsProof (BOTH BOUNDS(ID, ID)) 75.95/20.48 Transformed relative TRS to weighted TRS 75.95/20.48 ---------------------------------------- 75.95/20.48 75.95/20.48 (2) 75.95/20.48 Obligation: 75.95/20.48 The Runtime Complexity (innermost) of the given CpxWeightedTrs could be proven to be BOUNDS(1, n^1). 75.95/20.48 75.95/20.48 75.95/20.48 The TRS R consists of the following rules: 75.95/20.48 75.95/20.48 cond1(true, x, y) -> cond2(gr(x, 0), x, y) [1] 75.95/20.48 cond2(true, x, y) -> cond1(or(gr(x, 0), gr(y, 0)), p(x), y) [1] 75.95/20.48 cond2(false, x, y) -> cond3(gr(y, 0), x, y) [1] 75.95/20.48 cond3(true, x, y) -> cond1(or(gr(x, 0), gr(y, 0)), x, p(y)) [1] 75.95/20.48 cond3(false, x, y) -> cond1(or(gr(x, 0), gr(y, 0)), x, y) [1] 75.95/20.48 gr(0, x) -> false [1] 75.95/20.48 gr(s(x), 0) -> true [1] 75.95/20.48 gr(s(x), s(y)) -> gr(x, y) [1] 75.95/20.48 or(false, false) -> false [1] 75.95/20.48 or(true, x) -> true [1] 75.95/20.48 or(x, true) -> true [1] 75.95/20.48 p(0) -> 0 [1] 75.95/20.48 p(s(x)) -> x [1] 75.95/20.48 75.95/20.48 Rewrite Strategy: INNERMOST 75.95/20.48 ---------------------------------------- 75.95/20.48 75.95/20.48 (3) TypeInferenceProof (BOTH BOUNDS(ID, ID)) 75.95/20.48 Infered types. 75.95/20.48 ---------------------------------------- 75.95/20.48 75.95/20.48 (4) 75.95/20.48 Obligation: 75.95/20.48 Runtime Complexity Weighted TRS with Types. 75.95/20.48 The TRS R consists of the following rules: 75.95/20.48 75.95/20.48 cond1(true, x, y) -> cond2(gr(x, 0), x, y) [1] 75.95/20.48 cond2(true, x, y) -> cond1(or(gr(x, 0), gr(y, 0)), p(x), y) [1] 75.95/20.48 cond2(false, x, y) -> cond3(gr(y, 0), x, y) [1] 75.95/20.48 cond3(true, x, y) -> cond1(or(gr(x, 0), gr(y, 0)), x, p(y)) [1] 75.95/20.48 cond3(false, x, y) -> cond1(or(gr(x, 0), gr(y, 0)), x, y) [1] 75.95/20.48 gr(0, x) -> false [1] 75.95/20.48 gr(s(x), 0) -> true [1] 75.95/20.48 gr(s(x), s(y)) -> gr(x, y) [1] 75.95/20.48 or(false, false) -> false [1] 75.95/20.48 or(true, x) -> true [1] 75.95/20.48 or(x, true) -> true [1] 75.95/20.48 p(0) -> 0 [1] 75.95/20.48 p(s(x)) -> x [1] 75.95/20.48 75.95/20.48 The TRS has the following type information: 75.95/20.48 cond1 :: true:false -> 0:s -> 0:s -> cond1:cond2:cond3 75.95/20.48 true :: true:false 75.95/20.48 cond2 :: true:false -> 0:s -> 0:s -> cond1:cond2:cond3 75.95/20.48 gr :: 0:s -> 0:s -> true:false 75.95/20.48 0 :: 0:s 75.95/20.48 or :: true:false -> true:false -> true:false 75.95/20.48 p :: 0:s -> 0:s 75.95/20.48 false :: true:false 75.95/20.48 cond3 :: true:false -> 0:s -> 0:s -> cond1:cond2:cond3 75.95/20.48 s :: 0:s -> 0:s 75.95/20.48 75.95/20.48 Rewrite Strategy: INNERMOST 75.95/20.48 ---------------------------------------- 75.95/20.48 75.95/20.48 (5) CompletionProof (UPPER BOUND(ID)) 75.95/20.48 The transformation into a RNTS is sound, since: 75.95/20.48 75.95/20.48 (a) The obligation is a constructor system where every type has a constant constructor, 75.95/20.48 75.95/20.48 (b) The following defined symbols do not have to be completely defined, as they can never occur inside other defined symbols: 75.95/20.48 75.95/20.48 cond1_3 75.95/20.48 cond2_3 75.95/20.48 cond3_3 75.95/20.48 75.95/20.48 (c) The following functions are completely defined: 75.95/20.48 75.95/20.48 or_2 75.95/20.48 gr_2 75.95/20.48 p_1 75.95/20.48 75.95/20.48 Due to the following rules being added: 75.95/20.48 none 75.95/20.48 75.95/20.48 And the following fresh constants: const 75.95/20.48 75.95/20.48 ---------------------------------------- 75.95/20.48 75.95/20.48 (6) 75.95/20.48 Obligation: 75.95/20.48 Runtime Complexity Weighted TRS where critical functions are completely defined. The underlying TRS is: 75.95/20.48 75.95/20.48 Runtime Complexity Weighted TRS with Types. 75.95/20.48 The TRS R consists of the following rules: 75.95/20.48 75.95/20.48 cond1(true, x, y) -> cond2(gr(x, 0), x, y) [1] 75.95/20.48 cond2(true, x, y) -> cond1(or(gr(x, 0), gr(y, 0)), p(x), y) [1] 75.95/20.48 cond2(false, x, y) -> cond3(gr(y, 0), x, y) [1] 75.95/20.48 cond3(true, x, y) -> cond1(or(gr(x, 0), gr(y, 0)), x, p(y)) [1] 75.95/20.48 cond3(false, x, y) -> cond1(or(gr(x, 0), gr(y, 0)), x, y) [1] 75.95/20.48 gr(0, x) -> false [1] 75.95/20.48 gr(s(x), 0) -> true [1] 75.95/20.48 gr(s(x), s(y)) -> gr(x, y) [1] 75.95/20.48 or(false, false) -> false [1] 75.95/20.48 or(true, x) -> true [1] 75.95/20.48 or(x, true) -> true [1] 75.95/20.48 p(0) -> 0 [1] 75.95/20.48 p(s(x)) -> x [1] 75.95/20.48 75.95/20.48 The TRS has the following type information: 75.95/20.48 cond1 :: true:false -> 0:s -> 0:s -> cond1:cond2:cond3 75.95/20.48 true :: true:false 75.95/20.48 cond2 :: true:false -> 0:s -> 0:s -> cond1:cond2:cond3 75.95/20.48 gr :: 0:s -> 0:s -> true:false 75.95/20.48 0 :: 0:s 75.95/20.48 or :: true:false -> true:false -> true:false 75.95/20.48 p :: 0:s -> 0:s 75.95/20.48 false :: true:false 75.95/20.48 cond3 :: true:false -> 0:s -> 0:s -> cond1:cond2:cond3 75.95/20.48 s :: 0:s -> 0:s 75.95/20.48 const :: cond1:cond2:cond3 75.95/20.48 75.95/20.48 Rewrite Strategy: INNERMOST 75.95/20.48 ---------------------------------------- 75.95/20.48 75.95/20.48 (7) NarrowingProof (BOTH BOUNDS(ID, ID)) 75.95/20.48 Narrowed the inner basic terms of all right-hand sides by a single narrowing step. 75.95/20.48 ---------------------------------------- 75.95/20.48 75.95/20.48 (8) 75.95/20.48 Obligation: 75.95/20.48 Runtime Complexity Weighted TRS where critical functions are completely defined. The underlying TRS is: 75.95/20.48 75.95/20.48 Runtime Complexity Weighted TRS with Types. 75.95/20.48 The TRS R consists of the following rules: 75.95/20.48 75.95/20.48 cond1(true, 0, y) -> cond2(false, 0, y) [2] 75.95/20.48 cond1(true, s(x'), y) -> cond2(true, s(x'), y) [2] 75.95/20.48 cond2(true, 0, 0) -> cond1(or(false, false), 0, 0) [4] 75.95/20.48 cond2(true, 0, s(x1)) -> cond1(or(false, true), 0, s(x1)) [4] 75.95/20.48 cond2(true, s(x''), 0) -> cond1(or(true, false), x'', 0) [4] 75.95/20.48 cond2(true, s(x''), s(x2)) -> cond1(or(true, true), x'', s(x2)) [4] 75.95/20.48 cond2(false, x, 0) -> cond3(false, x, 0) [2] 75.95/20.48 cond2(false, x, s(x3)) -> cond3(true, x, s(x3)) [2] 75.95/20.48 cond3(true, 0, 0) -> cond1(or(false, false), 0, 0) [4] 75.95/20.48 cond3(true, 0, s(x5)) -> cond1(or(false, true), 0, x5) [4] 75.95/20.48 cond3(true, s(x4), 0) -> cond1(or(true, false), s(x4), 0) [4] 75.95/20.48 cond3(true, s(x4), s(x6)) -> cond1(or(true, true), s(x4), x6) [4] 75.95/20.48 cond3(false, 0, 0) -> cond1(or(false, false), 0, 0) [3] 75.95/20.48 cond3(false, 0, s(x8)) -> cond1(or(false, true), 0, s(x8)) [3] 75.95/20.48 cond3(false, s(x7), 0) -> cond1(or(true, false), s(x7), 0) [3] 75.95/20.48 cond3(false, s(x7), s(x9)) -> cond1(or(true, true), s(x7), s(x9)) [3] 75.95/20.48 gr(0, x) -> false [1] 75.95/20.48 gr(s(x), 0) -> true [1] 75.95/20.48 gr(s(x), s(y)) -> gr(x, y) [1] 75.95/20.48 or(false, false) -> false [1] 75.95/20.49 or(true, x) -> true [1] 75.95/20.49 or(x, true) -> true [1] 75.95/20.49 p(0) -> 0 [1] 75.95/20.49 p(s(x)) -> x [1] 75.95/20.49 75.95/20.49 The TRS has the following type information: 75.95/20.49 cond1 :: true:false -> 0:s -> 0:s -> cond1:cond2:cond3 75.95/20.49 true :: true:false 75.95/20.49 cond2 :: true:false -> 0:s -> 0:s -> cond1:cond2:cond3 75.95/20.49 gr :: 0:s -> 0:s -> true:false 75.95/20.49 0 :: 0:s 75.95/20.49 or :: true:false -> true:false -> true:false 75.95/20.49 p :: 0:s -> 0:s 75.95/20.49 false :: true:false 75.95/20.49 cond3 :: true:false -> 0:s -> 0:s -> cond1:cond2:cond3 75.95/20.49 s :: 0:s -> 0:s 75.95/20.49 const :: cond1:cond2:cond3 75.95/20.49 75.95/20.49 Rewrite Strategy: INNERMOST 75.95/20.49 ---------------------------------------- 75.95/20.49 75.95/20.49 (9) CpxTypedWeightedTrsToRntsProof (UPPER BOUND(ID)) 75.95/20.49 Transformed the TRS into an over-approximating RNTS by (improved) Size Abstraction. 75.95/20.49 The constant constructors are abstracted as follows: 75.95/20.49 75.95/20.49 true => 1 75.95/20.49 0 => 0 75.95/20.49 false => 0 75.95/20.49 const => 0 75.95/20.49 75.95/20.49 ---------------------------------------- 75.95/20.49 75.95/20.49 (10) 75.95/20.49 Obligation: 75.95/20.49 Complexity RNTS consisting of the following rules: 75.95/20.49 75.95/20.49 cond1(z, z', z'') -{ 2 }-> cond2(1, 1 + x', y) :|: z' = 1 + x', z'' = y, z = 1, x' >= 0, y >= 0 75.95/20.49 cond1(z, z', z'') -{ 2 }-> cond2(0, 0, y) :|: z'' = y, z = 1, y >= 0, z' = 0 75.95/20.49 cond2(z, z', z'') -{ 2 }-> cond3(1, x, 1 + x3) :|: z' = x, z'' = 1 + x3, x >= 0, z = 0, x3 >= 0 75.95/20.49 cond2(z, z', z'') -{ 2 }-> cond3(0, x, 0) :|: z'' = 0, z' = x, x >= 0, z = 0 75.95/20.49 cond2(z, z', z'') -{ 4 }-> cond1(or(1, 1), x'', 1 + x2) :|: z' = 1 + x'', z = 1, z'' = 1 + x2, x'' >= 0, x2 >= 0 75.95/20.49 cond2(z, z', z'') -{ 4 }-> cond1(or(1, 0), x'', 0) :|: z'' = 0, z' = 1 + x'', z = 1, x'' >= 0 75.95/20.49 cond2(z, z', z'') -{ 4 }-> cond1(or(0, 1), 0, 1 + x1) :|: x1 >= 0, z = 1, z'' = 1 + x1, z' = 0 75.95/20.49 cond2(z, z', z'') -{ 4 }-> cond1(or(0, 0), 0, 0) :|: z'' = 0, z = 1, z' = 0 75.95/20.49 cond3(z, z', z'') -{ 4 }-> cond1(or(1, 1), 1 + x4, x6) :|: x4 >= 0, z = 1, z' = 1 + x4, x6 >= 0, z'' = 1 + x6 75.95/20.49 cond3(z, z', z'') -{ 3 }-> cond1(or(1, 1), 1 + x7, 1 + x9) :|: z' = 1 + x7, x7 >= 0, z = 0, x9 >= 0, z'' = 1 + x9 75.95/20.49 cond3(z, z', z'') -{ 4 }-> cond1(or(1, 0), 1 + x4, 0) :|: z'' = 0, x4 >= 0, z = 1, z' = 1 + x4 75.95/20.49 cond3(z, z', z'') -{ 3 }-> cond1(or(1, 0), 1 + x7, 0) :|: z' = 1 + x7, z'' = 0, x7 >= 0, z = 0 75.95/20.49 cond3(z, z', z'') -{ 4 }-> cond1(or(0, 1), 0, x5) :|: x5 >= 0, z = 1, z'' = 1 + x5, z' = 0 75.95/20.49 cond3(z, z', z'') -{ 3 }-> cond1(or(0, 1), 0, 1 + x8) :|: x8 >= 0, z'' = 1 + x8, z = 0, z' = 0 75.95/20.49 cond3(z, z', z'') -{ 4 }-> cond1(or(0, 0), 0, 0) :|: z'' = 0, z = 1, z' = 0 75.95/20.49 cond3(z, z', z'') -{ 3 }-> cond1(or(0, 0), 0, 0) :|: z'' = 0, z = 0, z' = 0 75.95/20.49 gr(z, z') -{ 1 }-> gr(x, y) :|: z' = 1 + y, x >= 0, y >= 0, z = 1 + x 75.95/20.49 gr(z, z') -{ 1 }-> 1 :|: x >= 0, z = 1 + x, z' = 0 75.95/20.49 gr(z, z') -{ 1 }-> 0 :|: z' = x, x >= 0, z = 0 75.95/20.49 or(z, z') -{ 1 }-> 1 :|: z' = x, z = 1, x >= 0 75.95/20.49 or(z, z') -{ 1 }-> 1 :|: x >= 0, z' = 1, z = x 75.95/20.49 or(z, z') -{ 1 }-> 0 :|: z = 0, z' = 0 75.95/20.49 p(z) -{ 1 }-> x :|: x >= 0, z = 1 + x 75.95/20.49 p(z) -{ 1 }-> 0 :|: z = 0 75.95/20.49 75.95/20.49 75.95/20.49 ---------------------------------------- 75.95/20.49 75.95/20.49 (11) InliningProof (UPPER BOUND(ID)) 75.95/20.49 Inlined the following terminating rules on right-hand sides where appropriate: 75.95/20.49 75.95/20.49 or(z, z') -{ 1 }-> 0 :|: z = 0, z' = 0 75.95/20.49 or(z, z') -{ 1 }-> 1 :|: z' = x, z = 1, x >= 0 75.95/20.49 or(z, z') -{ 1 }-> 1 :|: x >= 0, z' = 1, z = x 75.95/20.49 75.95/20.49 ---------------------------------------- 75.95/20.49 75.95/20.49 (12) 75.95/20.49 Obligation: 75.95/20.49 Complexity RNTS consisting of the following rules: 75.95/20.49 75.95/20.49 cond1(z, z', z'') -{ 2 }-> cond2(1, 1 + x', y) :|: z' = 1 + x', z'' = y, z = 1, x' >= 0, y >= 0 75.95/20.49 cond1(z, z', z'') -{ 2 }-> cond2(0, 0, y) :|: z'' = y, z = 1, y >= 0, z' = 0 75.95/20.49 cond2(z, z', z'') -{ 2 }-> cond3(1, x, 1 + x3) :|: z' = x, z'' = 1 + x3, x >= 0, z = 0, x3 >= 0 75.95/20.49 cond2(z, z', z'') -{ 2 }-> cond3(0, x, 0) :|: z'' = 0, z' = x, x >= 0, z = 0 75.95/20.49 cond2(z, z', z'') -{ 5 }-> cond1(1, x'', 0) :|: z'' = 0, z' = 1 + x'', z = 1, x'' >= 0, 0 = x, 1 = 1, x >= 0 75.95/20.49 cond2(z, z', z'') -{ 5 }-> cond1(1, x'', 1 + x2) :|: z' = 1 + x'', z = 1, z'' = 1 + x2, x'' >= 0, x2 >= 0, 1 = x, 1 = 1, x >= 0 75.95/20.49 cond2(z, z', z'') -{ 5 }-> cond1(1, 0, 1 + x1) :|: x1 >= 0, z = 1, z'' = 1 + x1, z' = 0, x >= 0, 1 = 1, 0 = x 75.95/20.49 cond2(z, z', z'') -{ 5 }-> cond1(0, 0, 0) :|: z'' = 0, z = 1, z' = 0, 0 = 0 75.95/20.49 cond3(z, z', z'') -{ 5 }-> cond1(1, 0, x5) :|: x5 >= 0, z = 1, z'' = 1 + x5, z' = 0, x >= 0, 1 = 1, 0 = x 75.95/20.49 cond3(z, z', z'') -{ 4 }-> cond1(1, 0, 1 + x8) :|: x8 >= 0, z'' = 1 + x8, z = 0, z' = 0, x >= 0, 1 = 1, 0 = x 75.95/20.49 cond3(z, z', z'') -{ 5 }-> cond1(1, 1 + x4, x6) :|: x4 >= 0, z = 1, z' = 1 + x4, x6 >= 0, z'' = 1 + x6, 1 = x, 1 = 1, x >= 0 75.95/20.49 cond3(z, z', z'') -{ 5 }-> cond1(1, 1 + x4, 0) :|: z'' = 0, x4 >= 0, z = 1, z' = 1 + x4, 0 = x, 1 = 1, x >= 0 75.95/20.49 cond3(z, z', z'') -{ 4 }-> cond1(1, 1 + x7, 0) :|: z' = 1 + x7, z'' = 0, x7 >= 0, z = 0, 0 = x, 1 = 1, x >= 0 75.95/20.49 cond3(z, z', z'') -{ 4 }-> cond1(1, 1 + x7, 1 + x9) :|: z' = 1 + x7, x7 >= 0, z = 0, x9 >= 0, z'' = 1 + x9, 1 = x, 1 = 1, x >= 0 75.95/20.49 cond3(z, z', z'') -{ 5 }-> cond1(0, 0, 0) :|: z'' = 0, z = 1, z' = 0, 0 = 0 75.95/20.49 cond3(z, z', z'') -{ 4 }-> cond1(0, 0, 0) :|: z'' = 0, z = 0, z' = 0, 0 = 0 75.95/20.49 gr(z, z') -{ 1 }-> gr(x, y) :|: z' = 1 + y, x >= 0, y >= 0, z = 1 + x 75.95/20.49 gr(z, z') -{ 1 }-> 1 :|: x >= 0, z = 1 + x, z' = 0 75.95/20.49 gr(z, z') -{ 1 }-> 0 :|: z' = x, x >= 0, z = 0 75.95/20.49 or(z, z') -{ 1 }-> 1 :|: z' = x, z = 1, x >= 0 75.95/20.50 or(z, z') -{ 1 }-> 1 :|: x >= 0, z' = 1, z = x 75.95/20.50 or(z, z') -{ 1 }-> 0 :|: z = 0, z' = 0 75.95/20.50 p(z) -{ 1 }-> x :|: x >= 0, z = 1 + x 75.95/20.50 p(z) -{ 1 }-> 0 :|: z = 0 75.95/20.50 75.95/20.50 75.95/20.50 ---------------------------------------- 75.95/20.50 75.95/20.50 (13) SimplificationProof (BOTH BOUNDS(ID, ID)) 75.95/20.50 Simplified the RNTS by moving equalities from the constraints into the right-hand sides. 75.95/20.50 ---------------------------------------- 75.95/20.50 75.95/20.50 (14) 75.95/20.50 Obligation: 75.95/20.50 Complexity RNTS consisting of the following rules: 75.95/20.50 75.95/20.50 cond1(z, z', z'') -{ 2 }-> cond2(1, 1 + (z' - 1), z'') :|: z = 1, z' - 1 >= 0, z'' >= 0 75.95/20.50 cond1(z, z', z'') -{ 2 }-> cond2(0, 0, z'') :|: z = 1, z'' >= 0, z' = 0 75.95/20.50 cond2(z, z', z'') -{ 2 }-> cond3(1, z', 1 + (z'' - 1)) :|: z' >= 0, z = 0, z'' - 1 >= 0 75.95/20.50 cond2(z, z', z'') -{ 2 }-> cond3(0, z', 0) :|: z'' = 0, z' >= 0, z = 0 75.95/20.50 cond2(z, z', z'') -{ 5 }-> cond1(1, 0, 1 + (z'' - 1)) :|: z'' - 1 >= 0, z = 1, z' = 0, x >= 0, 1 = 1, 0 = x 75.95/20.50 cond2(z, z', z'') -{ 5 }-> cond1(1, z' - 1, 0) :|: z'' = 0, z = 1, z' - 1 >= 0, 0 = x, 1 = 1, x >= 0 75.95/20.50 cond2(z, z', z'') -{ 5 }-> cond1(1, z' - 1, 1 + (z'' - 1)) :|: z = 1, z' - 1 >= 0, z'' - 1 >= 0, 1 = x, 1 = 1, x >= 0 75.95/20.50 cond2(z, z', z'') -{ 5 }-> cond1(0, 0, 0) :|: z'' = 0, z = 1, z' = 0, 0 = 0 75.95/20.50 cond3(z, z', z'') -{ 5 }-> cond1(1, 0, z'' - 1) :|: z'' - 1 >= 0, z = 1, z' = 0, x >= 0, 1 = 1, 0 = x 75.95/20.50 cond3(z, z', z'') -{ 4 }-> cond1(1, 0, 1 + (z'' - 1)) :|: z'' - 1 >= 0, z = 0, z' = 0, x >= 0, 1 = 1, 0 = x 75.95/20.50 cond3(z, z', z'') -{ 5 }-> cond1(1, 1 + (z' - 1), 0) :|: z'' = 0, z' - 1 >= 0, z = 1, 0 = x, 1 = 1, x >= 0 75.95/20.50 cond3(z, z', z'') -{ 4 }-> cond1(1, 1 + (z' - 1), 0) :|: z'' = 0, z' - 1 >= 0, z = 0, 0 = x, 1 = 1, x >= 0 75.95/20.50 cond3(z, z', z'') -{ 5 }-> cond1(1, 1 + (z' - 1), z'' - 1) :|: z' - 1 >= 0, z = 1, z'' - 1 >= 0, 1 = x, 1 = 1, x >= 0 75.95/20.50 cond3(z, z', z'') -{ 4 }-> cond1(1, 1 + (z' - 1), 1 + (z'' - 1)) :|: z' - 1 >= 0, z = 0, z'' - 1 >= 0, 1 = x, 1 = 1, x >= 0 75.95/20.50 cond3(z, z', z'') -{ 5 }-> cond1(0, 0, 0) :|: z'' = 0, z = 1, z' = 0, 0 = 0 75.95/20.50 cond3(z, z', z'') -{ 4 }-> cond1(0, 0, 0) :|: z'' = 0, z = 0, z' = 0, 0 = 0 75.95/20.50 gr(z, z') -{ 1 }-> gr(z - 1, z' - 1) :|: z - 1 >= 0, z' - 1 >= 0 75.95/20.50 gr(z, z') -{ 1 }-> 1 :|: z - 1 >= 0, z' = 0 75.95/20.50 gr(z, z') -{ 1 }-> 0 :|: z' >= 0, z = 0 75.95/20.50 or(z, z') -{ 1 }-> 1 :|: z = 1, z' >= 0 75.95/20.50 or(z, z') -{ 1 }-> 1 :|: z >= 0, z' = 1 75.95/20.50 or(z, z') -{ 1 }-> 0 :|: z = 0, z' = 0 75.95/20.50 p(z) -{ 1 }-> 0 :|: z = 0 75.95/20.50 p(z) -{ 1 }-> z - 1 :|: z - 1 >= 0 75.95/20.50 75.95/20.50 75.95/20.50 ---------------------------------------- 75.95/20.50 75.95/20.50 (15) CpxRntsAnalysisOrderProof (BOTH BOUNDS(ID, ID)) 75.95/20.50 Found the following analysis order by SCC decomposition: 75.95/20.50 75.95/20.50 { cond2, cond1, cond3 } 75.95/20.50 { p } 75.95/20.50 { gr } 75.95/20.50 { or } 75.95/20.50 75.95/20.50 ---------------------------------------- 75.95/20.50 75.95/20.50 (16) 75.95/20.50 Obligation: 75.95/20.50 Complexity RNTS consisting of the following rules: 75.95/20.50 75.95/20.50 cond1(z, z', z'') -{ 2 }-> cond2(1, 1 + (z' - 1), z'') :|: z = 1, z' - 1 >= 0, z'' >= 0 75.95/20.50 cond1(z, z', z'') -{ 2 }-> cond2(0, 0, z'') :|: z = 1, z'' >= 0, z' = 0 75.95/20.50 cond2(z, z', z'') -{ 2 }-> cond3(1, z', 1 + (z'' - 1)) :|: z' >= 0, z = 0, z'' - 1 >= 0 75.95/20.50 cond2(z, z', z'') -{ 2 }-> cond3(0, z', 0) :|: z'' = 0, z' >= 0, z = 0 75.95/20.50 cond2(z, z', z'') -{ 5 }-> cond1(1, 0, 1 + (z'' - 1)) :|: z'' - 1 >= 0, z = 1, z' = 0, x >= 0, 1 = 1, 0 = x 75.95/20.50 cond2(z, z', z'') -{ 5 }-> cond1(1, z' - 1, 0) :|: z'' = 0, z = 1, z' - 1 >= 0, 0 = x, 1 = 1, x >= 0 75.95/20.50 cond2(z, z', z'') -{ 5 }-> cond1(1, z' - 1, 1 + (z'' - 1)) :|: z = 1, z' - 1 >= 0, z'' - 1 >= 0, 1 = x, 1 = 1, x >= 0 75.95/20.50 cond2(z, z', z'') -{ 5 }-> cond1(0, 0, 0) :|: z'' = 0, z = 1, z' = 0, 0 = 0 75.95/20.50 cond3(z, z', z'') -{ 5 }-> cond1(1, 0, z'' - 1) :|: z'' - 1 >= 0, z = 1, z' = 0, x >= 0, 1 = 1, 0 = x 75.95/20.50 cond3(z, z', z'') -{ 4 }-> cond1(1, 0, 1 + (z'' - 1)) :|: z'' - 1 >= 0, z = 0, z' = 0, x >= 0, 1 = 1, 0 = x 75.95/20.50 cond3(z, z', z'') -{ 5 }-> cond1(1, 1 + (z' - 1), 0) :|: z'' = 0, z' - 1 >= 0, z = 1, 0 = x, 1 = 1, x >= 0 75.95/20.50 cond3(z, z', z'') -{ 4 }-> cond1(1, 1 + (z' - 1), 0) :|: z'' = 0, z' - 1 >= 0, z = 0, 0 = x, 1 = 1, x >= 0 75.95/20.50 cond3(z, z', z'') -{ 5 }-> cond1(1, 1 + (z' - 1), z'' - 1) :|: z' - 1 >= 0, z = 1, z'' - 1 >= 0, 1 = x, 1 = 1, x >= 0 75.95/20.50 cond3(z, z', z'') -{ 4 }-> cond1(1, 1 + (z' - 1), 1 + (z'' - 1)) :|: z' - 1 >= 0, z = 0, z'' - 1 >= 0, 1 = x, 1 = 1, x >= 0 75.95/20.50 cond3(z, z', z'') -{ 5 }-> cond1(0, 0, 0) :|: z'' = 0, z = 1, z' = 0, 0 = 0 75.95/20.50 cond3(z, z', z'') -{ 4 }-> cond1(0, 0, 0) :|: z'' = 0, z = 0, z' = 0, 0 = 0 75.95/20.50 gr(z, z') -{ 1 }-> gr(z - 1, z' - 1) :|: z - 1 >= 0, z' - 1 >= 0 75.95/20.50 gr(z, z') -{ 1 }-> 1 :|: z - 1 >= 0, z' = 0 75.95/20.50 gr(z, z') -{ 1 }-> 0 :|: z' >= 0, z = 0 75.95/20.50 or(z, z') -{ 1 }-> 1 :|: z = 1, z' >= 0 75.95/20.50 or(z, z') -{ 1 }-> 1 :|: z >= 0, z' = 1 75.95/20.50 or(z, z') -{ 1 }-> 0 :|: z = 0, z' = 0 75.95/20.50 p(z) -{ 1 }-> 0 :|: z = 0 75.95/20.50 p(z) -{ 1 }-> z - 1 :|: z - 1 >= 0 75.95/20.50 75.95/20.50 Function symbols to be analyzed: {cond2,cond1,cond3}, {p}, {gr}, {or} 75.95/20.50 75.95/20.50 ---------------------------------------- 75.95/20.50 75.95/20.50 (17) ResultPropagationProof (UPPER BOUND(ID)) 75.95/20.50 Applied inner abstraction using the recently inferred runtime/size bounds where possible. 75.95/20.50 ---------------------------------------- 75.95/20.50 75.95/20.50 (18) 75.95/20.50 Obligation: 75.95/20.50 Complexity RNTS consisting of the following rules: 75.95/20.50 75.95/20.50 cond1(z, z', z'') -{ 2 }-> cond2(1, 1 + (z' - 1), z'') :|: z = 1, z' - 1 >= 0, z'' >= 0 75.95/20.50 cond1(z, z', z'') -{ 2 }-> cond2(0, 0, z'') :|: z = 1, z'' >= 0, z' = 0 75.95/20.50 cond2(z, z', z'') -{ 2 }-> cond3(1, z', 1 + (z'' - 1)) :|: z' >= 0, z = 0, z'' - 1 >= 0 75.95/20.50 cond2(z, z', z'') -{ 2 }-> cond3(0, z', 0) :|: z'' = 0, z' >= 0, z = 0 75.95/20.50 cond2(z, z', z'') -{ 5 }-> cond1(1, 0, 1 + (z'' - 1)) :|: z'' - 1 >= 0, z = 1, z' = 0, x >= 0, 1 = 1, 0 = x 75.95/20.50 cond2(z, z', z'') -{ 5 }-> cond1(1, z' - 1, 0) :|: z'' = 0, z = 1, z' - 1 >= 0, 0 = x, 1 = 1, x >= 0 75.95/20.50 cond2(z, z', z'') -{ 5 }-> cond1(1, z' - 1, 1 + (z'' - 1)) :|: z = 1, z' - 1 >= 0, z'' - 1 >= 0, 1 = x, 1 = 1, x >= 0 75.95/20.50 cond2(z, z', z'') -{ 5 }-> cond1(0, 0, 0) :|: z'' = 0, z = 1, z' = 0, 0 = 0 75.95/20.50 cond3(z, z', z'') -{ 5 }-> cond1(1, 0, z'' - 1) :|: z'' - 1 >= 0, z = 1, z' = 0, x >= 0, 1 = 1, 0 = x 75.95/20.50 cond3(z, z', z'') -{ 4 }-> cond1(1, 0, 1 + (z'' - 1)) :|: z'' - 1 >= 0, z = 0, z' = 0, x >= 0, 1 = 1, 0 = x 75.95/20.50 cond3(z, z', z'') -{ 5 }-> cond1(1, 1 + (z' - 1), 0) :|: z'' = 0, z' - 1 >= 0, z = 1, 0 = x, 1 = 1, x >= 0 75.95/20.50 cond3(z, z', z'') -{ 4 }-> cond1(1, 1 + (z' - 1), 0) :|: z'' = 0, z' - 1 >= 0, z = 0, 0 = x, 1 = 1, x >= 0 75.95/20.50 cond3(z, z', z'') -{ 5 }-> cond1(1, 1 + (z' - 1), z'' - 1) :|: z' - 1 >= 0, z = 1, z'' - 1 >= 0, 1 = x, 1 = 1, x >= 0 75.95/20.50 cond3(z, z', z'') -{ 4 }-> cond1(1, 1 + (z' - 1), 1 + (z'' - 1)) :|: z' - 1 >= 0, z = 0, z'' - 1 >= 0, 1 = x, 1 = 1, x >= 0 75.95/20.50 cond3(z, z', z'') -{ 5 }-> cond1(0, 0, 0) :|: z'' = 0, z = 1, z' = 0, 0 = 0 75.95/20.50 cond3(z, z', z'') -{ 4 }-> cond1(0, 0, 0) :|: z'' = 0, z = 0, z' = 0, 0 = 0 75.95/20.50 gr(z, z') -{ 1 }-> gr(z - 1, z' - 1) :|: z - 1 >= 0, z' - 1 >= 0 75.95/20.50 gr(z, z') -{ 1 }-> 1 :|: z - 1 >= 0, z' = 0 75.95/20.50 gr(z, z') -{ 1 }-> 0 :|: z' >= 0, z = 0 75.95/20.50 or(z, z') -{ 1 }-> 1 :|: z = 1, z' >= 0 75.95/20.50 or(z, z') -{ 1 }-> 1 :|: z >= 0, z' = 1 75.95/20.50 or(z, z') -{ 1 }-> 0 :|: z = 0, z' = 0 75.95/20.50 p(z) -{ 1 }-> 0 :|: z = 0 75.95/20.50 p(z) -{ 1 }-> z - 1 :|: z - 1 >= 0 75.95/20.50 75.95/20.50 Function symbols to be analyzed: {cond2,cond1,cond3}, {p}, {gr}, {or} 75.95/20.50 75.95/20.50 ---------------------------------------- 75.95/20.50 75.95/20.50 (19) IntTrsBoundProof (UPPER BOUND(ID)) 75.95/20.50 75.95/20.50 Computed SIZE bound using CoFloCo for: cond2 75.95/20.50 after applying outer abstraction to obtain an ITS, 75.95/20.50 resulting in: O(1) with polynomial bound: 0 75.95/20.50 75.95/20.50 Computed SIZE bound using CoFloCo for: cond1 75.95/20.50 after applying outer abstraction to obtain an ITS, 75.95/20.50 resulting in: O(1) with polynomial bound: 0 75.95/20.50 75.95/20.50 Computed SIZE bound using CoFloCo for: cond3 75.95/20.50 after applying outer abstraction to obtain an ITS, 75.95/20.50 resulting in: O(1) with polynomial bound: 0 75.95/20.50 75.95/20.50 ---------------------------------------- 75.95/20.50 75.95/20.50 (20) 75.95/20.50 Obligation: 75.95/20.50 Complexity RNTS consisting of the following rules: 75.95/20.50 75.95/20.50 cond1(z, z', z'') -{ 2 }-> cond2(1, 1 + (z' - 1), z'') :|: z = 1, z' - 1 >= 0, z'' >= 0 75.95/20.50 cond1(z, z', z'') -{ 2 }-> cond2(0, 0, z'') :|: z = 1, z'' >= 0, z' = 0 75.95/20.50 cond2(z, z', z'') -{ 2 }-> cond3(1, z', 1 + (z'' - 1)) :|: z' >= 0, z = 0, z'' - 1 >= 0 75.95/20.50 cond2(z, z', z'') -{ 2 }-> cond3(0, z', 0) :|: z'' = 0, z' >= 0, z = 0 75.95/20.50 cond2(z, z', z'') -{ 5 }-> cond1(1, 0, 1 + (z'' - 1)) :|: z'' - 1 >= 0, z = 1, z' = 0, x >= 0, 1 = 1, 0 = x 75.95/20.50 cond2(z, z', z'') -{ 5 }-> cond1(1, z' - 1, 0) :|: z'' = 0, z = 1, z' - 1 >= 0, 0 = x, 1 = 1, x >= 0 75.95/20.50 cond2(z, z', z'') -{ 5 }-> cond1(1, z' - 1, 1 + (z'' - 1)) :|: z = 1, z' - 1 >= 0, z'' - 1 >= 0, 1 = x, 1 = 1, x >= 0 75.95/20.50 cond2(z, z', z'') -{ 5 }-> cond1(0, 0, 0) :|: z'' = 0, z = 1, z' = 0, 0 = 0 75.95/20.50 cond3(z, z', z'') -{ 5 }-> cond1(1, 0, z'' - 1) :|: z'' - 1 >= 0, z = 1, z' = 0, x >= 0, 1 = 1, 0 = x 75.95/20.50 cond3(z, z', z'') -{ 4 }-> cond1(1, 0, 1 + (z'' - 1)) :|: z'' - 1 >= 0, z = 0, z' = 0, x >= 0, 1 = 1, 0 = x 75.95/20.50 cond3(z, z', z'') -{ 5 }-> cond1(1, 1 + (z' - 1), 0) :|: z'' = 0, z' - 1 >= 0, z = 1, 0 = x, 1 = 1, x >= 0 75.95/20.50 cond3(z, z', z'') -{ 4 }-> cond1(1, 1 + (z' - 1), 0) :|: z'' = 0, z' - 1 >= 0, z = 0, 0 = x, 1 = 1, x >= 0 75.95/20.50 cond3(z, z', z'') -{ 5 }-> cond1(1, 1 + (z' - 1), z'' - 1) :|: z' - 1 >= 0, z = 1, z'' - 1 >= 0, 1 = x, 1 = 1, x >= 0 75.95/20.50 cond3(z, z', z'') -{ 4 }-> cond1(1, 1 + (z' - 1), 1 + (z'' - 1)) :|: z' - 1 >= 0, z = 0, z'' - 1 >= 0, 1 = x, 1 = 1, x >= 0 75.95/20.50 cond3(z, z', z'') -{ 5 }-> cond1(0, 0, 0) :|: z'' = 0, z = 1, z' = 0, 0 = 0 75.95/20.50 cond3(z, z', z'') -{ 4 }-> cond1(0, 0, 0) :|: z'' = 0, z = 0, z' = 0, 0 = 0 75.95/20.50 gr(z, z') -{ 1 }-> gr(z - 1, z' - 1) :|: z - 1 >= 0, z' - 1 >= 0 75.95/20.50 gr(z, z') -{ 1 }-> 1 :|: z - 1 >= 0, z' = 0 75.95/20.50 gr(z, z') -{ 1 }-> 0 :|: z' >= 0, z = 0 75.95/20.50 or(z, z') -{ 1 }-> 1 :|: z = 1, z' >= 0 75.95/20.50 or(z, z') -{ 1 }-> 1 :|: z >= 0, z' = 1 75.95/20.50 or(z, z') -{ 1 }-> 0 :|: z = 0, z' = 0 75.95/20.50 p(z) -{ 1 }-> 0 :|: z = 0 75.95/20.50 p(z) -{ 1 }-> z - 1 :|: z - 1 >= 0 75.95/20.50 75.95/20.50 Function symbols to be analyzed: {cond2,cond1,cond3}, {p}, {gr}, {or} 75.95/20.50 Previous analysis results are: 75.95/20.50 cond2: runtime: ?, size: O(1) [0] 75.95/20.50 cond1: runtime: ?, size: O(1) [0] 75.95/20.50 cond3: runtime: ?, size: O(1) [0] 75.95/20.50 75.95/20.50 ---------------------------------------- 75.95/20.50 75.95/20.50 (21) IntTrsBoundProof (UPPER BOUND(ID)) 75.95/20.50 75.95/20.50 Computed RUNTIME bound using CoFloCo for: cond2 75.95/20.50 after applying outer abstraction to obtain an ITS, 75.95/20.50 resulting in: O(n^1) with polynomial bound: 48 + 7*z' + 9*z'' 75.95/20.50 75.95/20.50 Computed RUNTIME bound using CoFloCo for: cond1 75.95/20.50 after applying outer abstraction to obtain an ITS, 75.95/20.50 resulting in: O(n^1) with polynomial bound: 50 + 7*z' + 9*z'' 75.95/20.50 75.95/20.50 Computed RUNTIME bound using CoFloCo for: cond3 75.95/20.50 after applying outer abstraction to obtain an ITS, 75.95/20.50 resulting in: O(n^1) with polynomial bound: 55 + 7*z' + 9*z'' 75.95/20.50 75.95/20.50 ---------------------------------------- 75.95/20.50 75.95/20.50 (22) 75.95/20.50 Obligation: 75.95/20.50 Complexity RNTS consisting of the following rules: 75.95/20.50 75.95/20.50 cond1(z, z', z'') -{ 2 }-> cond2(1, 1 + (z' - 1), z'') :|: z = 1, z' - 1 >= 0, z'' >= 0 75.95/20.50 cond1(z, z', z'') -{ 2 }-> cond2(0, 0, z'') :|: z = 1, z'' >= 0, z' = 0 75.95/20.50 cond2(z, z', z'') -{ 2 }-> cond3(1, z', 1 + (z'' - 1)) :|: z' >= 0, z = 0, z'' - 1 >= 0 75.95/20.50 cond2(z, z', z'') -{ 2 }-> cond3(0, z', 0) :|: z'' = 0, z' >= 0, z = 0 75.95/20.50 cond2(z, z', z'') -{ 5 }-> cond1(1, 0, 1 + (z'' - 1)) :|: z'' - 1 >= 0, z = 1, z' = 0, x >= 0, 1 = 1, 0 = x 75.95/20.50 cond2(z, z', z'') -{ 5 }-> cond1(1, z' - 1, 0) :|: z'' = 0, z = 1, z' - 1 >= 0, 0 = x, 1 = 1, x >= 0 75.95/20.50 cond2(z, z', z'') -{ 5 }-> cond1(1, z' - 1, 1 + (z'' - 1)) :|: z = 1, z' - 1 >= 0, z'' - 1 >= 0, 1 = x, 1 = 1, x >= 0 75.95/20.50 cond2(z, z', z'') -{ 5 }-> cond1(0, 0, 0) :|: z'' = 0, z = 1, z' = 0, 0 = 0 75.95/20.50 cond3(z, z', z'') -{ 5 }-> cond1(1, 0, z'' - 1) :|: z'' - 1 >= 0, z = 1, z' = 0, x >= 0, 1 = 1, 0 = x 75.95/20.50 cond3(z, z', z'') -{ 4 }-> cond1(1, 0, 1 + (z'' - 1)) :|: z'' - 1 >= 0, z = 0, z' = 0, x >= 0, 1 = 1, 0 = x 75.95/20.50 cond3(z, z', z'') -{ 5 }-> cond1(1, 1 + (z' - 1), 0) :|: z'' = 0, z' - 1 >= 0, z = 1, 0 = x, 1 = 1, x >= 0 75.95/20.50 cond3(z, z', z'') -{ 4 }-> cond1(1, 1 + (z' - 1), 0) :|: z'' = 0, z' - 1 >= 0, z = 0, 0 = x, 1 = 1, x >= 0 75.95/20.50 cond3(z, z', z'') -{ 5 }-> cond1(1, 1 + (z' - 1), z'' - 1) :|: z' - 1 >= 0, z = 1, z'' - 1 >= 0, 1 = x, 1 = 1, x >= 0 75.95/20.50 cond3(z, z', z'') -{ 4 }-> cond1(1, 1 + (z' - 1), 1 + (z'' - 1)) :|: z' - 1 >= 0, z = 0, z'' - 1 >= 0, 1 = x, 1 = 1, x >= 0 75.95/20.50 cond3(z, z', z'') -{ 5 }-> cond1(0, 0, 0) :|: z'' = 0, z = 1, z' = 0, 0 = 0 75.95/20.50 cond3(z, z', z'') -{ 4 }-> cond1(0, 0, 0) :|: z'' = 0, z = 0, z' = 0, 0 = 0 75.95/20.50 gr(z, z') -{ 1 }-> gr(z - 1, z' - 1) :|: z - 1 >= 0, z' - 1 >= 0 75.95/20.50 gr(z, z') -{ 1 }-> 1 :|: z - 1 >= 0, z' = 0 75.95/20.50 gr(z, z') -{ 1 }-> 0 :|: z' >= 0, z = 0 75.95/20.50 or(z, z') -{ 1 }-> 1 :|: z = 1, z' >= 0 75.95/20.50 or(z, z') -{ 1 }-> 1 :|: z >= 0, z' = 1 75.95/20.50 or(z, z') -{ 1 }-> 0 :|: z = 0, z' = 0 75.95/20.50 p(z) -{ 1 }-> 0 :|: z = 0 75.95/20.50 p(z) -{ 1 }-> z - 1 :|: z - 1 >= 0 75.95/20.50 75.95/20.50 Function symbols to be analyzed: {p}, {gr}, {or} 75.95/20.50 Previous analysis results are: 75.95/20.50 cond2: runtime: O(n^1) [48 + 7*z' + 9*z''], size: O(1) [0] 75.95/20.50 cond1: runtime: O(n^1) [50 + 7*z' + 9*z''], size: O(1) [0] 75.95/20.50 cond3: runtime: O(n^1) [55 + 7*z' + 9*z''], size: O(1) [0] 75.95/20.50 75.95/20.50 ---------------------------------------- 75.95/20.50 75.95/20.50 (23) ResultPropagationProof (UPPER BOUND(ID)) 75.95/20.50 Applied inner abstraction using the recently inferred runtime/size bounds where possible. 75.95/20.50 ---------------------------------------- 75.95/20.50 75.95/20.50 (24) 75.95/20.50 Obligation: 75.95/20.50 Complexity RNTS consisting of the following rules: 75.95/20.50 75.95/20.50 cond1(z, z', z'') -{ 50 + 9*z'' }-> s :|: s >= 0, s <= 0, z = 1, z'' >= 0, z' = 0 75.95/20.50 cond1(z, z', z'') -{ 50 + 7*z' + 9*z'' }-> s' :|: s' >= 0, s' <= 0, z = 1, z' - 1 >= 0, z'' >= 0 75.95/20.50 cond2(z, z', z'') -{ 57 + 7*z' }-> s'' :|: s'' >= 0, s'' <= 0, z'' = 0, z' >= 0, z = 0 75.95/20.50 cond2(z, z', z'') -{ 57 + 7*z' + 9*z'' }-> s1 :|: s1 >= 0, s1 <= 0, z' >= 0, z = 0, z'' - 1 >= 0 75.95/20.50 cond2(z, z', z'') -{ 55 }-> s2 :|: s2 >= 0, s2 <= 0, z'' = 0, z = 1, z' = 0, 0 = 0 75.95/20.50 cond2(z, z', z'') -{ 55 + 9*z'' }-> s3 :|: s3 >= 0, s3 <= 0, z'' - 1 >= 0, z = 1, z' = 0, x >= 0, 1 = 1, 0 = x 75.95/20.50 cond2(z, z', z'') -{ 48 + 7*z' }-> s4 :|: s4 >= 0, s4 <= 0, z'' = 0, z = 1, z' - 1 >= 0, 0 = x, 1 = 1, x >= 0 75.95/20.50 cond2(z, z', z'') -{ 48 + 7*z' + 9*z'' }-> s5 :|: s5 >= 0, s5 <= 0, z = 1, z' - 1 >= 0, z'' - 1 >= 0, 1 = x, 1 = 1, x >= 0 75.95/20.50 cond3(z, z', z'') -{ 54 }-> s10 :|: s10 >= 0, s10 <= 0, z'' = 0, z = 0, z' = 0, 0 = 0 75.95/20.50 cond3(z, z', z'') -{ 54 + 9*z'' }-> s11 :|: s11 >= 0, s11 <= 0, z'' - 1 >= 0, z = 0, z' = 0, x >= 0, 1 = 1, 0 = x 75.95/20.50 cond3(z, z', z'') -{ 54 + 7*z' }-> s12 :|: s12 >= 0, s12 <= 0, z'' = 0, z' - 1 >= 0, z = 0, 0 = x, 1 = 1, x >= 0 75.95/20.50 cond3(z, z', z'') -{ 54 + 7*z' + 9*z'' }-> s13 :|: s13 >= 0, s13 <= 0, z' - 1 >= 0, z = 0, z'' - 1 >= 0, 1 = x, 1 = 1, x >= 0 75.95/20.50 cond3(z, z', z'') -{ 55 }-> s6 :|: s6 >= 0, s6 <= 0, z'' = 0, z = 1, z' = 0, 0 = 0 75.95/20.50 cond3(z, z', z'') -{ 46 + 9*z'' }-> s7 :|: s7 >= 0, s7 <= 0, z'' - 1 >= 0, z = 1, z' = 0, x >= 0, 1 = 1, 0 = x 75.95/20.50 cond3(z, z', z'') -{ 55 + 7*z' }-> s8 :|: s8 >= 0, s8 <= 0, z'' = 0, z' - 1 >= 0, z = 1, 0 = x, 1 = 1, x >= 0 75.95/20.50 cond3(z, z', z'') -{ 46 + 7*z' + 9*z'' }-> s9 :|: s9 >= 0, s9 <= 0, z' - 1 >= 0, z = 1, z'' - 1 >= 0, 1 = x, 1 = 1, x >= 0 75.95/20.50 gr(z, z') -{ 1 }-> gr(z - 1, z' - 1) :|: z - 1 >= 0, z' - 1 >= 0 75.95/20.50 gr(z, z') -{ 1 }-> 1 :|: z - 1 >= 0, z' = 0 75.95/20.50 gr(z, z') -{ 1 }-> 0 :|: z' >= 0, z = 0 75.95/20.50 or(z, z') -{ 1 }-> 1 :|: z = 1, z' >= 0 75.95/20.50 or(z, z') -{ 1 }-> 1 :|: z >= 0, z' = 1 75.95/20.50 or(z, z') -{ 1 }-> 0 :|: z = 0, z' = 0 75.95/20.50 p(z) -{ 1 }-> 0 :|: z = 0 75.95/20.50 p(z) -{ 1 }-> z - 1 :|: z - 1 >= 0 75.95/20.50 75.95/20.50 Function symbols to be analyzed: {p}, {gr}, {or} 75.95/20.50 Previous analysis results are: 75.95/20.50 cond2: runtime: O(n^1) [48 + 7*z' + 9*z''], size: O(1) [0] 75.95/20.50 cond1: runtime: O(n^1) [50 + 7*z' + 9*z''], size: O(1) [0] 75.95/20.50 cond3: runtime: O(n^1) [55 + 7*z' + 9*z''], size: O(1) [0] 75.95/20.50 75.95/20.50 ---------------------------------------- 75.95/20.50 75.95/20.50 (25) IntTrsBoundProof (UPPER BOUND(ID)) 75.95/20.50 75.95/20.50 Computed SIZE bound using KoAT for: p 75.95/20.50 after applying outer abstraction to obtain an ITS, 75.95/20.50 resulting in: O(n^1) with polynomial bound: z 75.95/20.50 75.95/20.50 ---------------------------------------- 75.95/20.50 75.95/20.50 (26) 75.95/20.50 Obligation: 75.95/20.50 Complexity RNTS consisting of the following rules: 75.95/20.50 75.95/20.50 cond1(z, z', z'') -{ 50 + 9*z'' }-> s :|: s >= 0, s <= 0, z = 1, z'' >= 0, z' = 0 75.95/20.50 cond1(z, z', z'') -{ 50 + 7*z' + 9*z'' }-> s' :|: s' >= 0, s' <= 0, z = 1, z' - 1 >= 0, z'' >= 0 75.95/20.50 cond2(z, z', z'') -{ 57 + 7*z' }-> s'' :|: s'' >= 0, s'' <= 0, z'' = 0, z' >= 0, z = 0 75.95/20.50 cond2(z, z', z'') -{ 57 + 7*z' + 9*z'' }-> s1 :|: s1 >= 0, s1 <= 0, z' >= 0, z = 0, z'' - 1 >= 0 75.95/20.50 cond2(z, z', z'') -{ 55 }-> s2 :|: s2 >= 0, s2 <= 0, z'' = 0, z = 1, z' = 0, 0 = 0 75.95/20.50 cond2(z, z', z'') -{ 55 + 9*z'' }-> s3 :|: s3 >= 0, s3 <= 0, z'' - 1 >= 0, z = 1, z' = 0, x >= 0, 1 = 1, 0 = x 75.95/20.50 cond2(z, z', z'') -{ 48 + 7*z' }-> s4 :|: s4 >= 0, s4 <= 0, z'' = 0, z = 1, z' - 1 >= 0, 0 = x, 1 = 1, x >= 0 75.95/20.50 cond2(z, z', z'') -{ 48 + 7*z' + 9*z'' }-> s5 :|: s5 >= 0, s5 <= 0, z = 1, z' - 1 >= 0, z'' - 1 >= 0, 1 = x, 1 = 1, x >= 0 75.95/20.50 cond3(z, z', z'') -{ 54 }-> s10 :|: s10 >= 0, s10 <= 0, z'' = 0, z = 0, z' = 0, 0 = 0 75.95/20.50 cond3(z, z', z'') -{ 54 + 9*z'' }-> s11 :|: s11 >= 0, s11 <= 0, z'' - 1 >= 0, z = 0, z' = 0, x >= 0, 1 = 1, 0 = x 75.95/20.50 cond3(z, z', z'') -{ 54 + 7*z' }-> s12 :|: s12 >= 0, s12 <= 0, z'' = 0, z' - 1 >= 0, z = 0, 0 = x, 1 = 1, x >= 0 75.95/20.50 cond3(z, z', z'') -{ 54 + 7*z' + 9*z'' }-> s13 :|: s13 >= 0, s13 <= 0, z' - 1 >= 0, z = 0, z'' - 1 >= 0, 1 = x, 1 = 1, x >= 0 75.95/20.50 cond3(z, z', z'') -{ 55 }-> s6 :|: s6 >= 0, s6 <= 0, z'' = 0, z = 1, z' = 0, 0 = 0 75.95/20.50 cond3(z, z', z'') -{ 46 + 9*z'' }-> s7 :|: s7 >= 0, s7 <= 0, z'' - 1 >= 0, z = 1, z' = 0, x >= 0, 1 = 1, 0 = x 75.95/20.50 cond3(z, z', z'') -{ 55 + 7*z' }-> s8 :|: s8 >= 0, s8 <= 0, z'' = 0, z' - 1 >= 0, z = 1, 0 = x, 1 = 1, x >= 0 75.95/20.50 cond3(z, z', z'') -{ 46 + 7*z' + 9*z'' }-> s9 :|: s9 >= 0, s9 <= 0, z' - 1 >= 0, z = 1, z'' - 1 >= 0, 1 = x, 1 = 1, x >= 0 75.95/20.50 gr(z, z') -{ 1 }-> gr(z - 1, z' - 1) :|: z - 1 >= 0, z' - 1 >= 0 75.95/20.50 gr(z, z') -{ 1 }-> 1 :|: z - 1 >= 0, z' = 0 75.95/20.50 gr(z, z') -{ 1 }-> 0 :|: z' >= 0, z = 0 75.95/20.50 or(z, z') -{ 1 }-> 1 :|: z = 1, z' >= 0 75.95/20.50 or(z, z') -{ 1 }-> 1 :|: z >= 0, z' = 1 75.95/20.50 or(z, z') -{ 1 }-> 0 :|: z = 0, z' = 0 75.95/20.50 p(z) -{ 1 }-> 0 :|: z = 0 75.95/20.50 p(z) -{ 1 }-> z - 1 :|: z - 1 >= 0 75.95/20.50 75.95/20.50 Function symbols to be analyzed: {p}, {gr}, {or} 75.95/20.50 Previous analysis results are: 75.95/20.50 cond2: runtime: O(n^1) [48 + 7*z' + 9*z''], size: O(1) [0] 75.95/20.50 cond1: runtime: O(n^1) [50 + 7*z' + 9*z''], size: O(1) [0] 75.95/20.50 cond3: runtime: O(n^1) [55 + 7*z' + 9*z''], size: O(1) [0] 75.95/20.50 p: runtime: ?, size: O(n^1) [z] 75.95/20.50 75.95/20.50 ---------------------------------------- 75.95/20.50 75.95/20.50 (27) IntTrsBoundProof (UPPER BOUND(ID)) 75.95/20.50 75.95/20.50 Computed RUNTIME bound using CoFloCo for: p 75.95/20.50 after applying outer abstraction to obtain an ITS, 75.95/20.50 resulting in: O(1) with polynomial bound: 1 75.95/20.50 75.95/20.50 ---------------------------------------- 75.95/20.50 75.95/20.50 (28) 75.95/20.50 Obligation: 75.95/20.50 Complexity RNTS consisting of the following rules: 75.95/20.50 75.95/20.50 cond1(z, z', z'') -{ 50 + 9*z'' }-> s :|: s >= 0, s <= 0, z = 1, z'' >= 0, z' = 0 75.95/20.50 cond1(z, z', z'') -{ 50 + 7*z' + 9*z'' }-> s' :|: s' >= 0, s' <= 0, z = 1, z' - 1 >= 0, z'' >= 0 75.95/20.50 cond2(z, z', z'') -{ 57 + 7*z' }-> s'' :|: s'' >= 0, s'' <= 0, z'' = 0, z' >= 0, z = 0 75.95/20.50 cond2(z, z', z'') -{ 57 + 7*z' + 9*z'' }-> s1 :|: s1 >= 0, s1 <= 0, z' >= 0, z = 0, z'' - 1 >= 0 75.95/20.50 cond2(z, z', z'') -{ 55 }-> s2 :|: s2 >= 0, s2 <= 0, z'' = 0, z = 1, z' = 0, 0 = 0 75.95/20.50 cond2(z, z', z'') -{ 55 + 9*z'' }-> s3 :|: s3 >= 0, s3 <= 0, z'' - 1 >= 0, z = 1, z' = 0, x >= 0, 1 = 1, 0 = x 75.95/20.50 cond2(z, z', z'') -{ 48 + 7*z' }-> s4 :|: s4 >= 0, s4 <= 0, z'' = 0, z = 1, z' - 1 >= 0, 0 = x, 1 = 1, x >= 0 75.95/20.50 cond2(z, z', z'') -{ 48 + 7*z' + 9*z'' }-> s5 :|: s5 >= 0, s5 <= 0, z = 1, z' - 1 >= 0, z'' - 1 >= 0, 1 = x, 1 = 1, x >= 0 75.95/20.50 cond3(z, z', z'') -{ 54 }-> s10 :|: s10 >= 0, s10 <= 0, z'' = 0, z = 0, z' = 0, 0 = 0 75.95/20.50 cond3(z, z', z'') -{ 54 + 9*z'' }-> s11 :|: s11 >= 0, s11 <= 0, z'' - 1 >= 0, z = 0, z' = 0, x >= 0, 1 = 1, 0 = x 75.95/20.50 cond3(z, z', z'') -{ 54 + 7*z' }-> s12 :|: s12 >= 0, s12 <= 0, z'' = 0, z' - 1 >= 0, z = 0, 0 = x, 1 = 1, x >= 0 76.19/20.52 cond3(z, z', z'') -{ 54 + 7*z' + 9*z'' }-> s13 :|: s13 >= 0, s13 <= 0, z' - 1 >= 0, z = 0, z'' - 1 >= 0, 1 = x, 1 = 1, x >= 0 76.19/20.52 cond3(z, z', z'') -{ 55 }-> s6 :|: s6 >= 0, s6 <= 0, z'' = 0, z = 1, z' = 0, 0 = 0 76.19/20.52 cond3(z, z', z'') -{ 46 + 9*z'' }-> s7 :|: s7 >= 0, s7 <= 0, z'' - 1 >= 0, z = 1, z' = 0, x >= 0, 1 = 1, 0 = x 76.19/20.52 cond3(z, z', z'') -{ 55 + 7*z' }-> s8 :|: s8 >= 0, s8 <= 0, z'' = 0, z' - 1 >= 0, z = 1, 0 = x, 1 = 1, x >= 0 76.19/20.52 cond3(z, z', z'') -{ 46 + 7*z' + 9*z'' }-> s9 :|: s9 >= 0, s9 <= 0, z' - 1 >= 0, z = 1, z'' - 1 >= 0, 1 = x, 1 = 1, x >= 0 76.19/20.52 gr(z, z') -{ 1 }-> gr(z - 1, z' - 1) :|: z - 1 >= 0, z' - 1 >= 0 76.19/20.52 gr(z, z') -{ 1 }-> 1 :|: z - 1 >= 0, z' = 0 76.19/20.52 gr(z, z') -{ 1 }-> 0 :|: z' >= 0, z = 0 76.19/20.52 or(z, z') -{ 1 }-> 1 :|: z = 1, z' >= 0 76.19/20.52 or(z, z') -{ 1 }-> 1 :|: z >= 0, z' = 1 76.19/20.52 or(z, z') -{ 1 }-> 0 :|: z = 0, z' = 0 76.19/20.52 p(z) -{ 1 }-> 0 :|: z = 0 76.19/20.52 p(z) -{ 1 }-> z - 1 :|: z - 1 >= 0 76.19/20.52 76.19/20.52 Function symbols to be analyzed: {gr}, {or} 76.19/20.52 Previous analysis results are: 76.19/20.52 cond2: runtime: O(n^1) [48 + 7*z' + 9*z''], size: O(1) [0] 76.19/20.52 cond1: runtime: O(n^1) [50 + 7*z' + 9*z''], size: O(1) [0] 76.19/20.52 cond3: runtime: O(n^1) [55 + 7*z' + 9*z''], size: O(1) [0] 76.19/20.52 p: runtime: O(1) [1], size: O(n^1) [z] 76.19/20.52 76.19/20.52 ---------------------------------------- 76.19/20.52 76.19/20.52 (29) ResultPropagationProof (UPPER BOUND(ID)) 76.19/20.52 Applied inner abstraction using the recently inferred runtime/size bounds where possible. 76.19/20.52 ---------------------------------------- 76.19/20.52 76.19/20.52 (30) 76.19/20.52 Obligation: 76.19/20.52 Complexity RNTS consisting of the following rules: 76.19/20.52 76.19/20.52 cond1(z, z', z'') -{ 50 + 9*z'' }-> s :|: s >= 0, s <= 0, z = 1, z'' >= 0, z' = 0 76.19/20.52 cond1(z, z', z'') -{ 50 + 7*z' + 9*z'' }-> s' :|: s' >= 0, s' <= 0, z = 1, z' - 1 >= 0, z'' >= 0 76.19/20.52 cond2(z, z', z'') -{ 57 + 7*z' }-> s'' :|: s'' >= 0, s'' <= 0, z'' = 0, z' >= 0, z = 0 76.19/20.52 cond2(z, z', z'') -{ 57 + 7*z' + 9*z'' }-> s1 :|: s1 >= 0, s1 <= 0, z' >= 0, z = 0, z'' - 1 >= 0 76.19/20.52 cond2(z, z', z'') -{ 55 }-> s2 :|: s2 >= 0, s2 <= 0, z'' = 0, z = 1, z' = 0, 0 = 0 76.19/20.52 cond2(z, z', z'') -{ 55 + 9*z'' }-> s3 :|: s3 >= 0, s3 <= 0, z'' - 1 >= 0, z = 1, z' = 0, x >= 0, 1 = 1, 0 = x 76.19/20.52 cond2(z, z', z'') -{ 48 + 7*z' }-> s4 :|: s4 >= 0, s4 <= 0, z'' = 0, z = 1, z' - 1 >= 0, 0 = x, 1 = 1, x >= 0 76.19/20.52 cond2(z, z', z'') -{ 48 + 7*z' + 9*z'' }-> s5 :|: s5 >= 0, s5 <= 0, z = 1, z' - 1 >= 0, z'' - 1 >= 0, 1 = x, 1 = 1, x >= 0 76.19/20.52 cond3(z, z', z'') -{ 54 }-> s10 :|: s10 >= 0, s10 <= 0, z'' = 0, z = 0, z' = 0, 0 = 0 76.19/20.52 cond3(z, z', z'') -{ 54 + 9*z'' }-> s11 :|: s11 >= 0, s11 <= 0, z'' - 1 >= 0, z = 0, z' = 0, x >= 0, 1 = 1, 0 = x 76.19/20.52 cond3(z, z', z'') -{ 54 + 7*z' }-> s12 :|: s12 >= 0, s12 <= 0, z'' = 0, z' - 1 >= 0, z = 0, 0 = x, 1 = 1, x >= 0 76.19/20.52 cond3(z, z', z'') -{ 54 + 7*z' + 9*z'' }-> s13 :|: s13 >= 0, s13 <= 0, z' - 1 >= 0, z = 0, z'' - 1 >= 0, 1 = x, 1 = 1, x >= 0 76.19/20.52 cond3(z, z', z'') -{ 55 }-> s6 :|: s6 >= 0, s6 <= 0, z'' = 0, z = 1, z' = 0, 0 = 0 76.19/20.52 cond3(z, z', z'') -{ 46 + 9*z'' }-> s7 :|: s7 >= 0, s7 <= 0, z'' - 1 >= 0, z = 1, z' = 0, x >= 0, 1 = 1, 0 = x 76.19/20.52 cond3(z, z', z'') -{ 55 + 7*z' }-> s8 :|: s8 >= 0, s8 <= 0, z'' = 0, z' - 1 >= 0, z = 1, 0 = x, 1 = 1, x >= 0 76.19/20.52 cond3(z, z', z'') -{ 46 + 7*z' + 9*z'' }-> s9 :|: s9 >= 0, s9 <= 0, z' - 1 >= 0, z = 1, z'' - 1 >= 0, 1 = x, 1 = 1, x >= 0 76.19/20.52 gr(z, z') -{ 1 }-> gr(z - 1, z' - 1) :|: z - 1 >= 0, z' - 1 >= 0 76.19/20.52 gr(z, z') -{ 1 }-> 1 :|: z - 1 >= 0, z' = 0 76.19/20.52 gr(z, z') -{ 1 }-> 0 :|: z' >= 0, z = 0 76.19/20.52 or(z, z') -{ 1 }-> 1 :|: z = 1, z' >= 0 76.19/20.52 or(z, z') -{ 1 }-> 1 :|: z >= 0, z' = 1 76.19/20.52 or(z, z') -{ 1 }-> 0 :|: z = 0, z' = 0 76.19/20.52 p(z) -{ 1 }-> 0 :|: z = 0 76.19/20.52 p(z) -{ 1 }-> z - 1 :|: z - 1 >= 0 76.19/20.52 76.19/20.52 Function symbols to be analyzed: {gr}, {or} 76.19/20.52 Previous analysis results are: 76.19/20.52 cond2: runtime: O(n^1) [48 + 7*z' + 9*z''], size: O(1) [0] 76.19/20.52 cond1: runtime: O(n^1) [50 + 7*z' + 9*z''], size: O(1) [0] 76.19/20.52 cond3: runtime: O(n^1) [55 + 7*z' + 9*z''], size: O(1) [0] 76.19/20.52 p: runtime: O(1) [1], size: O(n^1) [z] 76.19/20.52 76.19/20.52 ---------------------------------------- 76.19/20.52 76.19/20.52 (31) IntTrsBoundProof (UPPER BOUND(ID)) 76.19/20.52 76.19/20.52 Computed SIZE bound using CoFloCo for: gr 76.19/20.52 after applying outer abstraction to obtain an ITS, 76.19/20.52 resulting in: O(1) with polynomial bound: 1 76.19/20.52 76.19/20.52 ---------------------------------------- 76.19/20.52 76.19/20.52 (32) 76.19/20.52 Obligation: 76.19/20.52 Complexity RNTS consisting of the following rules: 76.19/20.52 76.19/20.52 cond1(z, z', z'') -{ 50 + 9*z'' }-> s :|: s >= 0, s <= 0, z = 1, z'' >= 0, z' = 0 76.19/20.52 cond1(z, z', z'') -{ 50 + 7*z' + 9*z'' }-> s' :|: s' >= 0, s' <= 0, z = 1, z' - 1 >= 0, z'' >= 0 76.19/20.52 cond2(z, z', z'') -{ 57 + 7*z' }-> s'' :|: s'' >= 0, s'' <= 0, z'' = 0, z' >= 0, z = 0 76.19/20.52 cond2(z, z', z'') -{ 57 + 7*z' + 9*z'' }-> s1 :|: s1 >= 0, s1 <= 0, z' >= 0, z = 0, z'' - 1 >= 0 76.19/20.52 cond2(z, z', z'') -{ 55 }-> s2 :|: s2 >= 0, s2 <= 0, z'' = 0, z = 1, z' = 0, 0 = 0 76.19/20.52 cond2(z, z', z'') -{ 55 + 9*z'' }-> s3 :|: s3 >= 0, s3 <= 0, z'' - 1 >= 0, z = 1, z' = 0, x >= 0, 1 = 1, 0 = x 76.19/20.52 cond2(z, z', z'') -{ 48 + 7*z' }-> s4 :|: s4 >= 0, s4 <= 0, z'' = 0, z = 1, z' - 1 >= 0, 0 = x, 1 = 1, x >= 0 76.19/20.52 cond2(z, z', z'') -{ 48 + 7*z' + 9*z'' }-> s5 :|: s5 >= 0, s5 <= 0, z = 1, z' - 1 >= 0, z'' - 1 >= 0, 1 = x, 1 = 1, x >= 0 76.19/20.52 cond3(z, z', z'') -{ 54 }-> s10 :|: s10 >= 0, s10 <= 0, z'' = 0, z = 0, z' = 0, 0 = 0 76.19/20.52 cond3(z, z', z'') -{ 54 + 9*z'' }-> s11 :|: s11 >= 0, s11 <= 0, z'' - 1 >= 0, z = 0, z' = 0, x >= 0, 1 = 1, 0 = x 76.19/20.52 cond3(z, z', z'') -{ 54 + 7*z' }-> s12 :|: s12 >= 0, s12 <= 0, z'' = 0, z' - 1 >= 0, z = 0, 0 = x, 1 = 1, x >= 0 76.19/20.52 cond3(z, z', z'') -{ 54 + 7*z' + 9*z'' }-> s13 :|: s13 >= 0, s13 <= 0, z' - 1 >= 0, z = 0, z'' - 1 >= 0, 1 = x, 1 = 1, x >= 0 76.19/20.52 cond3(z, z', z'') -{ 55 }-> s6 :|: s6 >= 0, s6 <= 0, z'' = 0, z = 1, z' = 0, 0 = 0 76.19/20.52 cond3(z, z', z'') -{ 46 + 9*z'' }-> s7 :|: s7 >= 0, s7 <= 0, z'' - 1 >= 0, z = 1, z' = 0, x >= 0, 1 = 1, 0 = x 76.19/20.52 cond3(z, z', z'') -{ 55 + 7*z' }-> s8 :|: s8 >= 0, s8 <= 0, z'' = 0, z' - 1 >= 0, z = 1, 0 = x, 1 = 1, x >= 0 76.19/20.52 cond3(z, z', z'') -{ 46 + 7*z' + 9*z'' }-> s9 :|: s9 >= 0, s9 <= 0, z' - 1 >= 0, z = 1, z'' - 1 >= 0, 1 = x, 1 = 1, x >= 0 76.19/20.52 gr(z, z') -{ 1 }-> gr(z - 1, z' - 1) :|: z - 1 >= 0, z' - 1 >= 0 76.19/20.52 gr(z, z') -{ 1 }-> 1 :|: z - 1 >= 0, z' = 0 76.19/20.52 gr(z, z') -{ 1 }-> 0 :|: z' >= 0, z = 0 76.19/20.52 or(z, z') -{ 1 }-> 1 :|: z = 1, z' >= 0 76.19/20.52 or(z, z') -{ 1 }-> 1 :|: z >= 0, z' = 1 76.19/20.52 or(z, z') -{ 1 }-> 0 :|: z = 0, z' = 0 76.19/20.52 p(z) -{ 1 }-> 0 :|: z = 0 76.19/20.52 p(z) -{ 1 }-> z - 1 :|: z - 1 >= 0 76.19/20.52 76.19/20.52 Function symbols to be analyzed: {gr}, {or} 76.19/20.52 Previous analysis results are: 76.19/20.52 cond2: runtime: O(n^1) [48 + 7*z' + 9*z''], size: O(1) [0] 76.19/20.52 cond1: runtime: O(n^1) [50 + 7*z' + 9*z''], size: O(1) [0] 76.19/20.52 cond3: runtime: O(n^1) [55 + 7*z' + 9*z''], size: O(1) [0] 76.19/20.52 p: runtime: O(1) [1], size: O(n^1) [z] 76.19/20.52 gr: runtime: ?, size: O(1) [1] 76.19/20.52 76.19/20.52 ---------------------------------------- 76.19/20.52 76.19/20.52 (33) IntTrsBoundProof (UPPER BOUND(ID)) 76.19/20.52 76.19/20.52 Computed RUNTIME bound using KoAT for: gr 76.19/20.52 after applying outer abstraction to obtain an ITS, 76.19/20.52 resulting in: O(n^1) with polynomial bound: 2 + z' 76.19/20.52 76.19/20.52 ---------------------------------------- 76.19/20.52 76.19/20.52 (34) 76.19/20.52 Obligation: 76.19/20.52 Complexity RNTS consisting of the following rules: 76.19/20.52 76.19/20.52 cond1(z, z', z'') -{ 50 + 9*z'' }-> s :|: s >= 0, s <= 0, z = 1, z'' >= 0, z' = 0 76.19/20.52 cond1(z, z', z'') -{ 50 + 7*z' + 9*z'' }-> s' :|: s' >= 0, s' <= 0, z = 1, z' - 1 >= 0, z'' >= 0 76.19/20.52 cond2(z, z', z'') -{ 57 + 7*z' }-> s'' :|: s'' >= 0, s'' <= 0, z'' = 0, z' >= 0, z = 0 76.19/20.52 cond2(z, z', z'') -{ 57 + 7*z' + 9*z'' }-> s1 :|: s1 >= 0, s1 <= 0, z' >= 0, z = 0, z'' - 1 >= 0 76.19/20.52 cond2(z, z', z'') -{ 55 }-> s2 :|: s2 >= 0, s2 <= 0, z'' = 0, z = 1, z' = 0, 0 = 0 76.19/20.52 cond2(z, z', z'') -{ 55 + 9*z'' }-> s3 :|: s3 >= 0, s3 <= 0, z'' - 1 >= 0, z = 1, z' = 0, x >= 0, 1 = 1, 0 = x 76.19/20.52 cond2(z, z', z'') -{ 48 + 7*z' }-> s4 :|: s4 >= 0, s4 <= 0, z'' = 0, z = 1, z' - 1 >= 0, 0 = x, 1 = 1, x >= 0 76.19/20.52 cond2(z, z', z'') -{ 48 + 7*z' + 9*z'' }-> s5 :|: s5 >= 0, s5 <= 0, z = 1, z' - 1 >= 0, z'' - 1 >= 0, 1 = x, 1 = 1, x >= 0 76.19/20.52 cond3(z, z', z'') -{ 54 }-> s10 :|: s10 >= 0, s10 <= 0, z'' = 0, z = 0, z' = 0, 0 = 0 76.19/20.52 cond3(z, z', z'') -{ 54 + 9*z'' }-> s11 :|: s11 >= 0, s11 <= 0, z'' - 1 >= 0, z = 0, z' = 0, x >= 0, 1 = 1, 0 = x 76.19/20.52 cond3(z, z', z'') -{ 54 + 7*z' }-> s12 :|: s12 >= 0, s12 <= 0, z'' = 0, z' - 1 >= 0, z = 0, 0 = x, 1 = 1, x >= 0 76.19/20.52 cond3(z, z', z'') -{ 54 + 7*z' + 9*z'' }-> s13 :|: s13 >= 0, s13 <= 0, z' - 1 >= 0, z = 0, z'' - 1 >= 0, 1 = x, 1 = 1, x >= 0 76.19/20.52 cond3(z, z', z'') -{ 55 }-> s6 :|: s6 >= 0, s6 <= 0, z'' = 0, z = 1, z' = 0, 0 = 0 76.19/20.52 cond3(z, z', z'') -{ 46 + 9*z'' }-> s7 :|: s7 >= 0, s7 <= 0, z'' - 1 >= 0, z = 1, z' = 0, x >= 0, 1 = 1, 0 = x 76.19/20.52 cond3(z, z', z'') -{ 55 + 7*z' }-> s8 :|: s8 >= 0, s8 <= 0, z'' = 0, z' - 1 >= 0, z = 1, 0 = x, 1 = 1, x >= 0 76.19/20.52 cond3(z, z', z'') -{ 46 + 7*z' + 9*z'' }-> s9 :|: s9 >= 0, s9 <= 0, z' - 1 >= 0, z = 1, z'' - 1 >= 0, 1 = x, 1 = 1, x >= 0 76.19/20.52 gr(z, z') -{ 1 }-> gr(z - 1, z' - 1) :|: z - 1 >= 0, z' - 1 >= 0 76.19/20.52 gr(z, z') -{ 1 }-> 1 :|: z - 1 >= 0, z' = 0 76.19/20.52 gr(z, z') -{ 1 }-> 0 :|: z' >= 0, z = 0 76.19/20.52 or(z, z') -{ 1 }-> 1 :|: z = 1, z' >= 0 76.19/20.52 or(z, z') -{ 1 }-> 1 :|: z >= 0, z' = 1 76.19/20.52 or(z, z') -{ 1 }-> 0 :|: z = 0, z' = 0 76.19/20.52 p(z) -{ 1 }-> 0 :|: z = 0 76.19/20.52 p(z) -{ 1 }-> z - 1 :|: z - 1 >= 0 76.19/20.52 76.19/20.52 Function symbols to be analyzed: {or} 76.19/20.52 Previous analysis results are: 76.19/20.52 cond2: runtime: O(n^1) [48 + 7*z' + 9*z''], size: O(1) [0] 76.19/20.52 cond1: runtime: O(n^1) [50 + 7*z' + 9*z''], size: O(1) [0] 76.19/20.52 cond3: runtime: O(n^1) [55 + 7*z' + 9*z''], size: O(1) [0] 76.19/20.52 p: runtime: O(1) [1], size: O(n^1) [z] 76.19/20.52 gr: runtime: O(n^1) [2 + z'], size: O(1) [1] 76.19/20.52 76.19/20.52 ---------------------------------------- 76.19/20.52 76.19/20.52 (35) ResultPropagationProof (UPPER BOUND(ID)) 76.19/20.52 Applied inner abstraction using the recently inferred runtime/size bounds where possible. 76.19/20.52 ---------------------------------------- 76.19/20.52 76.19/20.52 (36) 76.19/20.52 Obligation: 76.19/20.52 Complexity RNTS consisting of the following rules: 76.19/20.52 76.19/20.52 cond1(z, z', z'') -{ 50 + 9*z'' }-> s :|: s >= 0, s <= 0, z = 1, z'' >= 0, z' = 0 76.19/20.52 cond1(z, z', z'') -{ 50 + 7*z' + 9*z'' }-> s' :|: s' >= 0, s' <= 0, z = 1, z' - 1 >= 0, z'' >= 0 76.19/20.52 cond2(z, z', z'') -{ 57 + 7*z' }-> s'' :|: s'' >= 0, s'' <= 0, z'' = 0, z' >= 0, z = 0 76.19/20.52 cond2(z, z', z'') -{ 57 + 7*z' + 9*z'' }-> s1 :|: s1 >= 0, s1 <= 0, z' >= 0, z = 0, z'' - 1 >= 0 76.19/20.52 cond2(z, z', z'') -{ 55 }-> s2 :|: s2 >= 0, s2 <= 0, z'' = 0, z = 1, z' = 0, 0 = 0 76.19/20.52 cond2(z, z', z'') -{ 55 + 9*z'' }-> s3 :|: s3 >= 0, s3 <= 0, z'' - 1 >= 0, z = 1, z' = 0, x >= 0, 1 = 1, 0 = x 76.19/20.52 cond2(z, z', z'') -{ 48 + 7*z' }-> s4 :|: s4 >= 0, s4 <= 0, z'' = 0, z = 1, z' - 1 >= 0, 0 = x, 1 = 1, x >= 0 76.19/20.52 cond2(z, z', z'') -{ 48 + 7*z' + 9*z'' }-> s5 :|: s5 >= 0, s5 <= 0, z = 1, z' - 1 >= 0, z'' - 1 >= 0, 1 = x, 1 = 1, x >= 0 76.19/20.52 cond3(z, z', z'') -{ 54 }-> s10 :|: s10 >= 0, s10 <= 0, z'' = 0, z = 0, z' = 0, 0 = 0 76.19/20.52 cond3(z, z', z'') -{ 54 + 9*z'' }-> s11 :|: s11 >= 0, s11 <= 0, z'' - 1 >= 0, z = 0, z' = 0, x >= 0, 1 = 1, 0 = x 76.19/20.52 cond3(z, z', z'') -{ 54 + 7*z' }-> s12 :|: s12 >= 0, s12 <= 0, z'' = 0, z' - 1 >= 0, z = 0, 0 = x, 1 = 1, x >= 0 76.19/20.52 cond3(z, z', z'') -{ 54 + 7*z' + 9*z'' }-> s13 :|: s13 >= 0, s13 <= 0, z' - 1 >= 0, z = 0, z'' - 1 >= 0, 1 = x, 1 = 1, x >= 0 76.19/20.52 cond3(z, z', z'') -{ 55 }-> s6 :|: s6 >= 0, s6 <= 0, z'' = 0, z = 1, z' = 0, 0 = 0 76.19/20.52 cond3(z, z', z'') -{ 46 + 9*z'' }-> s7 :|: s7 >= 0, s7 <= 0, z'' - 1 >= 0, z = 1, z' = 0, x >= 0, 1 = 1, 0 = x 76.19/20.52 cond3(z, z', z'') -{ 55 + 7*z' }-> s8 :|: s8 >= 0, s8 <= 0, z'' = 0, z' - 1 >= 0, z = 1, 0 = x, 1 = 1, x >= 0 76.19/20.52 cond3(z, z', z'') -{ 46 + 7*z' + 9*z'' }-> s9 :|: s9 >= 0, s9 <= 0, z' - 1 >= 0, z = 1, z'' - 1 >= 0, 1 = x, 1 = 1, x >= 0 76.19/20.52 gr(z, z') -{ 2 + z' }-> s14 :|: s14 >= 0, s14 <= 1, z - 1 >= 0, z' - 1 >= 0 76.19/20.52 gr(z, z') -{ 1 }-> 1 :|: z - 1 >= 0, z' = 0 76.19/20.52 gr(z, z') -{ 1 }-> 0 :|: z' >= 0, z = 0 76.19/20.52 or(z, z') -{ 1 }-> 1 :|: z = 1, z' >= 0 76.19/20.52 or(z, z') -{ 1 }-> 1 :|: z >= 0, z' = 1 76.19/20.52 or(z, z') -{ 1 }-> 0 :|: z = 0, z' = 0 76.19/20.52 p(z) -{ 1 }-> 0 :|: z = 0 76.19/20.52 p(z) -{ 1 }-> z - 1 :|: z - 1 >= 0 76.19/20.52 76.19/20.52 Function symbols to be analyzed: {or} 76.19/20.52 Previous analysis results are: 76.19/20.52 cond2: runtime: O(n^1) [48 + 7*z' + 9*z''], size: O(1) [0] 76.19/20.52 cond1: runtime: O(n^1) [50 + 7*z' + 9*z''], size: O(1) [0] 76.19/20.52 cond3: runtime: O(n^1) [55 + 7*z' + 9*z''], size: O(1) [0] 76.19/20.52 p: runtime: O(1) [1], size: O(n^1) [z] 76.19/20.52 gr: runtime: O(n^1) [2 + z'], size: O(1) [1] 76.19/20.52 76.19/20.52 ---------------------------------------- 76.19/20.52 76.19/20.52 (37) IntTrsBoundProof (UPPER BOUND(ID)) 76.19/20.52 76.19/20.52 Computed SIZE bound using CoFloCo for: or 76.19/20.52 after applying outer abstraction to obtain an ITS, 76.19/20.52 resulting in: O(1) with polynomial bound: 1 76.19/20.52 76.19/20.52 ---------------------------------------- 76.19/20.52 76.19/20.52 (38) 76.19/20.52 Obligation: 76.19/20.52 Complexity RNTS consisting of the following rules: 76.19/20.52 76.19/20.52 cond1(z, z', z'') -{ 50 + 9*z'' }-> s :|: s >= 0, s <= 0, z = 1, z'' >= 0, z' = 0 76.19/20.52 cond1(z, z', z'') -{ 50 + 7*z' + 9*z'' }-> s' :|: s' >= 0, s' <= 0, z = 1, z' - 1 >= 0, z'' >= 0 76.19/20.52 cond2(z, z', z'') -{ 57 + 7*z' }-> s'' :|: s'' >= 0, s'' <= 0, z'' = 0, z' >= 0, z = 0 76.19/20.52 cond2(z, z', z'') -{ 57 + 7*z' + 9*z'' }-> s1 :|: s1 >= 0, s1 <= 0, z' >= 0, z = 0, z'' - 1 >= 0 76.19/20.52 cond2(z, z', z'') -{ 55 }-> s2 :|: s2 >= 0, s2 <= 0, z'' = 0, z = 1, z' = 0, 0 = 0 76.19/20.52 cond2(z, z', z'') -{ 55 + 9*z'' }-> s3 :|: s3 >= 0, s3 <= 0, z'' - 1 >= 0, z = 1, z' = 0, x >= 0, 1 = 1, 0 = x 76.19/20.52 cond2(z, z', z'') -{ 48 + 7*z' }-> s4 :|: s4 >= 0, s4 <= 0, z'' = 0, z = 1, z' - 1 >= 0, 0 = x, 1 = 1, x >= 0 76.19/20.52 cond2(z, z', z'') -{ 48 + 7*z' + 9*z'' }-> s5 :|: s5 >= 0, s5 <= 0, z = 1, z' - 1 >= 0, z'' - 1 >= 0, 1 = x, 1 = 1, x >= 0 76.19/20.52 cond3(z, z', z'') -{ 54 }-> s10 :|: s10 >= 0, s10 <= 0, z'' = 0, z = 0, z' = 0, 0 = 0 76.19/20.52 cond3(z, z', z'') -{ 54 + 9*z'' }-> s11 :|: s11 >= 0, s11 <= 0, z'' - 1 >= 0, z = 0, z' = 0, x >= 0, 1 = 1, 0 = x 76.19/20.52 cond3(z, z', z'') -{ 54 + 7*z' }-> s12 :|: s12 >= 0, s12 <= 0, z'' = 0, z' - 1 >= 0, z = 0, 0 = x, 1 = 1, x >= 0 76.19/20.52 cond3(z, z', z'') -{ 54 + 7*z' + 9*z'' }-> s13 :|: s13 >= 0, s13 <= 0, z' - 1 >= 0, z = 0, z'' - 1 >= 0, 1 = x, 1 = 1, x >= 0 76.19/20.52 cond3(z, z', z'') -{ 55 }-> s6 :|: s6 >= 0, s6 <= 0, z'' = 0, z = 1, z' = 0, 0 = 0 76.19/20.52 cond3(z, z', z'') -{ 46 + 9*z'' }-> s7 :|: s7 >= 0, s7 <= 0, z'' - 1 >= 0, z = 1, z' = 0, x >= 0, 1 = 1, 0 = x 76.19/20.52 cond3(z, z', z'') -{ 55 + 7*z' }-> s8 :|: s8 >= 0, s8 <= 0, z'' = 0, z' - 1 >= 0, z = 1, 0 = x, 1 = 1, x >= 0 76.19/20.52 cond3(z, z', z'') -{ 46 + 7*z' + 9*z'' }-> s9 :|: s9 >= 0, s9 <= 0, z' - 1 >= 0, z = 1, z'' - 1 >= 0, 1 = x, 1 = 1, x >= 0 76.19/20.52 gr(z, z') -{ 2 + z' }-> s14 :|: s14 >= 0, s14 <= 1, z - 1 >= 0, z' - 1 >= 0 76.19/20.52 gr(z, z') -{ 1 }-> 1 :|: z - 1 >= 0, z' = 0 76.19/20.52 gr(z, z') -{ 1 }-> 0 :|: z' >= 0, z = 0 76.19/20.52 or(z, z') -{ 1 }-> 1 :|: z = 1, z' >= 0 76.19/20.52 or(z, z') -{ 1 }-> 1 :|: z >= 0, z' = 1 76.19/20.52 or(z, z') -{ 1 }-> 0 :|: z = 0, z' = 0 76.19/20.52 p(z) -{ 1 }-> 0 :|: z = 0 76.19/20.52 p(z) -{ 1 }-> z - 1 :|: z - 1 >= 0 76.19/20.52 76.19/20.52 Function symbols to be analyzed: {or} 76.19/20.52 Previous analysis results are: 76.19/20.52 cond2: runtime: O(n^1) [48 + 7*z' + 9*z''], size: O(1) [0] 76.19/20.52 cond1: runtime: O(n^1) [50 + 7*z' + 9*z''], size: O(1) [0] 76.19/20.52 cond3: runtime: O(n^1) [55 + 7*z' + 9*z''], size: O(1) [0] 76.19/20.52 p: runtime: O(1) [1], size: O(n^1) [z] 76.19/20.52 gr: runtime: O(n^1) [2 + z'], size: O(1) [1] 76.19/20.52 or: runtime: ?, size: O(1) [1] 76.19/20.52 76.19/20.52 ---------------------------------------- 76.19/20.52 76.19/20.52 (39) IntTrsBoundProof (UPPER BOUND(ID)) 76.19/20.52 76.19/20.52 Computed RUNTIME bound using CoFloCo for: or 76.19/20.52 after applying outer abstraction to obtain an ITS, 76.19/20.52 resulting in: O(1) with polynomial bound: 1 76.19/20.52 76.19/20.52 ---------------------------------------- 76.19/20.52 76.19/20.52 (40) 76.19/20.52 Obligation: 76.19/20.52 Complexity RNTS consisting of the following rules: 76.19/20.52 76.19/20.52 cond1(z, z', z'') -{ 50 + 9*z'' }-> s :|: s >= 0, s <= 0, z = 1, z'' >= 0, z' = 0 76.19/20.52 cond1(z, z', z'') -{ 50 + 7*z' + 9*z'' }-> s' :|: s' >= 0, s' <= 0, z = 1, z' - 1 >= 0, z'' >= 0 76.19/20.52 cond2(z, z', z'') -{ 57 + 7*z' }-> s'' :|: s'' >= 0, s'' <= 0, z'' = 0, z' >= 0, z = 0 76.19/20.52 cond2(z, z', z'') -{ 57 + 7*z' + 9*z'' }-> s1 :|: s1 >= 0, s1 <= 0, z' >= 0, z = 0, z'' - 1 >= 0 76.19/20.52 cond2(z, z', z'') -{ 55 }-> s2 :|: s2 >= 0, s2 <= 0, z'' = 0, z = 1, z' = 0, 0 = 0 76.19/20.52 cond2(z, z', z'') -{ 55 + 9*z'' }-> s3 :|: s3 >= 0, s3 <= 0, z'' - 1 >= 0, z = 1, z' = 0, x >= 0, 1 = 1, 0 = x 76.19/20.52 cond2(z, z', z'') -{ 48 + 7*z' }-> s4 :|: s4 >= 0, s4 <= 0, z'' = 0, z = 1, z' - 1 >= 0, 0 = x, 1 = 1, x >= 0 76.19/20.52 cond2(z, z', z'') -{ 48 + 7*z' + 9*z'' }-> s5 :|: s5 >= 0, s5 <= 0, z = 1, z' - 1 >= 0, z'' - 1 >= 0, 1 = x, 1 = 1, x >= 0 76.19/20.52 cond3(z, z', z'') -{ 54 }-> s10 :|: s10 >= 0, s10 <= 0, z'' = 0, z = 0, z' = 0, 0 = 0 76.19/20.52 cond3(z, z', z'') -{ 54 + 9*z'' }-> s11 :|: s11 >= 0, s11 <= 0, z'' - 1 >= 0, z = 0, z' = 0, x >= 0, 1 = 1, 0 = x 76.19/20.52 cond3(z, z', z'') -{ 54 + 7*z' }-> s12 :|: s12 >= 0, s12 <= 0, z'' = 0, z' - 1 >= 0, z = 0, 0 = x, 1 = 1, x >= 0 76.19/20.52 cond3(z, z', z'') -{ 54 + 7*z' + 9*z'' }-> s13 :|: s13 >= 0, s13 <= 0, z' - 1 >= 0, z = 0, z'' - 1 >= 0, 1 = x, 1 = 1, x >= 0 76.19/20.52 cond3(z, z', z'') -{ 55 }-> s6 :|: s6 >= 0, s6 <= 0, z'' = 0, z = 1, z' = 0, 0 = 0 76.19/20.52 cond3(z, z', z'') -{ 46 + 9*z'' }-> s7 :|: s7 >= 0, s7 <= 0, z'' - 1 >= 0, z = 1, z' = 0, x >= 0, 1 = 1, 0 = x 76.19/20.52 cond3(z, z', z'') -{ 55 + 7*z' }-> s8 :|: s8 >= 0, s8 <= 0, z'' = 0, z' - 1 >= 0, z = 1, 0 = x, 1 = 1, x >= 0 76.19/20.52 cond3(z, z', z'') -{ 46 + 7*z' + 9*z'' }-> s9 :|: s9 >= 0, s9 <= 0, z' - 1 >= 0, z = 1, z'' - 1 >= 0, 1 = x, 1 = 1, x >= 0 76.19/20.52 gr(z, z') -{ 2 + z' }-> s14 :|: s14 >= 0, s14 <= 1, z - 1 >= 0, z' - 1 >= 0 76.19/20.52 gr(z, z') -{ 1 }-> 1 :|: z - 1 >= 0, z' = 0 76.19/20.52 gr(z, z') -{ 1 }-> 0 :|: z' >= 0, z = 0 76.19/20.52 or(z, z') -{ 1 }-> 1 :|: z = 1, z' >= 0 76.19/20.52 or(z, z') -{ 1 }-> 1 :|: z >= 0, z' = 1 76.19/20.52 or(z, z') -{ 1 }-> 0 :|: z = 0, z' = 0 76.19/20.52 p(z) -{ 1 }-> 0 :|: z = 0 76.19/20.52 p(z) -{ 1 }-> z - 1 :|: z - 1 >= 0 76.19/20.52 76.19/20.52 Function symbols to be analyzed: 76.19/20.52 Previous analysis results are: 76.19/20.52 cond2: runtime: O(n^1) [48 + 7*z' + 9*z''], size: O(1) [0] 76.19/20.52 cond1: runtime: O(n^1) [50 + 7*z' + 9*z''], size: O(1) [0] 76.19/20.52 cond3: runtime: O(n^1) [55 + 7*z' + 9*z''], size: O(1) [0] 76.19/20.52 p: runtime: O(1) [1], size: O(n^1) [z] 76.19/20.52 gr: runtime: O(n^1) [2 + z'], size: O(1) [1] 76.19/20.52 or: runtime: O(1) [1], size: O(1) [1] 76.19/20.52 76.19/20.52 ---------------------------------------- 76.19/20.52 76.19/20.52 (41) FinalProof (FINISHED) 76.19/20.52 Computed overall runtime complexity 76.19/20.52 ---------------------------------------- 76.19/20.52 76.19/20.52 (42) 76.19/20.52 BOUNDS(1, n^1) 76.19/20.52 76.19/20.52 ---------------------------------------- 76.19/20.52 76.19/20.52 (43) RenamingProof (BOTH BOUNDS(ID, ID)) 76.19/20.52 Renamed function symbols to avoid clashes with predefined symbol. 76.19/20.52 ---------------------------------------- 76.19/20.52 76.19/20.52 (44) 76.19/20.52 Obligation: 76.19/20.52 The Runtime Complexity (innermost) of the given CpxTRS could be proven to be BOUNDS(n^1, INF). 76.19/20.52 76.19/20.52 76.19/20.52 The TRS R consists of the following rules: 76.19/20.52 76.19/20.52 cond1(true, x, y) -> cond2(gr(x, 0'), x, y) 76.19/20.52 cond2(true, x, y) -> cond1(or(gr(x, 0'), gr(y, 0')), p(x), y) 76.19/20.52 cond2(false, x, y) -> cond3(gr(y, 0'), x, y) 76.19/20.52 cond3(true, x, y) -> cond1(or(gr(x, 0'), gr(y, 0')), x, p(y)) 76.19/20.52 cond3(false, x, y) -> cond1(or(gr(x, 0'), gr(y, 0')), x, y) 76.19/20.52 gr(0', x) -> false 76.19/20.52 gr(s(x), 0') -> true 76.19/20.52 gr(s(x), s(y)) -> gr(x, y) 76.19/20.52 or(false, false) -> false 76.19/20.52 or(true, x) -> true 76.19/20.52 or(x, true) -> true 76.19/20.52 p(0') -> 0' 76.19/20.52 p(s(x)) -> x 76.19/20.52 76.19/20.52 S is empty. 76.19/20.52 Rewrite Strategy: INNERMOST 76.19/20.52 ---------------------------------------- 76.19/20.52 76.19/20.52 (45) TypeInferenceProof (BOTH BOUNDS(ID, ID)) 76.19/20.52 Infered types. 76.19/20.52 ---------------------------------------- 76.19/20.52 76.19/20.52 (46) 76.19/20.52 Obligation: 76.19/20.52 Innermost TRS: 76.19/20.52 Rules: 76.19/20.52 cond1(true, x, y) -> cond2(gr(x, 0'), x, y) 76.19/20.52 cond2(true, x, y) -> cond1(or(gr(x, 0'), gr(y, 0')), p(x), y) 76.19/20.52 cond2(false, x, y) -> cond3(gr(y, 0'), x, y) 76.19/20.52 cond3(true, x, y) -> cond1(or(gr(x, 0'), gr(y, 0')), x, p(y)) 76.19/20.52 cond3(false, x, y) -> cond1(or(gr(x, 0'), gr(y, 0')), x, y) 76.19/20.52 gr(0', x) -> false 76.19/20.52 gr(s(x), 0') -> true 76.19/20.52 gr(s(x), s(y)) -> gr(x, y) 76.19/20.52 or(false, false) -> false 76.19/20.52 or(true, x) -> true 76.19/20.52 or(x, true) -> true 76.19/20.52 p(0') -> 0' 76.19/20.52 p(s(x)) -> x 76.19/20.52 76.19/20.52 Types: 76.19/20.52 cond1 :: true:false -> 0':s -> 0':s -> cond1:cond2:cond3 76.19/20.52 true :: true:false 76.19/20.52 cond2 :: true:false -> 0':s -> 0':s -> cond1:cond2:cond3 76.19/20.52 gr :: 0':s -> 0':s -> true:false 76.19/20.52 0' :: 0':s 76.19/20.52 or :: true:false -> true:false -> true:false 76.19/20.52 p :: 0':s -> 0':s 76.19/20.52 false :: true:false 76.19/20.52 cond3 :: true:false -> 0':s -> 0':s -> cond1:cond2:cond3 76.19/20.52 s :: 0':s -> 0':s 76.19/20.52 hole_cond1:cond2:cond31_0 :: cond1:cond2:cond3 76.19/20.52 hole_true:false2_0 :: true:false 76.19/20.52 hole_0':s3_0 :: 0':s 76.19/20.52 gen_0':s4_0 :: Nat -> 0':s 76.19/20.52 76.19/20.52 ---------------------------------------- 76.19/20.52 76.19/20.52 (47) OrderProof (LOWER BOUND(ID)) 76.19/20.52 Heuristically decided to analyse the following defined symbols: 76.19/20.52 cond1, cond2, gr, cond3 76.19/20.52 76.19/20.52 They will be analysed ascendingly in the following order: 76.19/20.52 cond1 = cond2 76.19/20.52 gr < cond1 76.19/20.52 cond1 = cond3 76.19/20.52 gr < cond2 76.19/20.52 cond2 = cond3 76.19/20.52 gr < cond3 76.19/20.52 76.19/20.52 ---------------------------------------- 76.19/20.52 76.19/20.52 (48) 76.19/20.52 Obligation: 76.19/20.52 Innermost TRS: 76.19/20.52 Rules: 76.19/20.52 cond1(true, x, y) -> cond2(gr(x, 0'), x, y) 76.19/20.52 cond2(true, x, y) -> cond1(or(gr(x, 0'), gr(y, 0')), p(x), y) 76.19/20.52 cond2(false, x, y) -> cond3(gr(y, 0'), x, y) 76.19/20.52 cond3(true, x, y) -> cond1(or(gr(x, 0'), gr(y, 0')), x, p(y)) 76.19/20.52 cond3(false, x, y) -> cond1(or(gr(x, 0'), gr(y, 0')), x, y) 76.19/20.52 gr(0', x) -> false 76.19/20.52 gr(s(x), 0') -> true 76.19/20.52 gr(s(x), s(y)) -> gr(x, y) 76.19/20.52 or(false, false) -> false 76.19/20.52 or(true, x) -> true 76.19/20.52 or(x, true) -> true 76.19/20.52 p(0') -> 0' 76.19/20.52 p(s(x)) -> x 76.19/20.52 76.19/20.52 Types: 76.19/20.52 cond1 :: true:false -> 0':s -> 0':s -> cond1:cond2:cond3 76.19/20.52 true :: true:false 76.19/20.52 cond2 :: true:false -> 0':s -> 0':s -> cond1:cond2:cond3 76.19/20.52 gr :: 0':s -> 0':s -> true:false 76.19/20.52 0' :: 0':s 76.19/20.52 or :: true:false -> true:false -> true:false 76.19/20.52 p :: 0':s -> 0':s 76.19/20.52 false :: true:false 76.19/20.52 cond3 :: true:false -> 0':s -> 0':s -> cond1:cond2:cond3 76.19/20.52 s :: 0':s -> 0':s 76.19/20.52 hole_cond1:cond2:cond31_0 :: cond1:cond2:cond3 76.19/20.52 hole_true:false2_0 :: true:false 76.19/20.52 hole_0':s3_0 :: 0':s 76.19/20.52 gen_0':s4_0 :: Nat -> 0':s 76.19/20.52 76.19/20.52 76.19/20.52 Generator Equations: 76.19/20.52 gen_0':s4_0(0) <=> 0' 76.19/20.52 gen_0':s4_0(+(x, 1)) <=> s(gen_0':s4_0(x)) 76.19/20.52 76.19/20.52 76.19/20.52 The following defined symbols remain to be analysed: 76.19/20.52 gr, cond1, cond2, cond3 76.19/20.52 76.19/20.52 They will be analysed ascendingly in the following order: 76.19/20.52 cond1 = cond2 76.19/20.52 gr < cond1 76.19/20.52 cond1 = cond3 76.19/20.52 gr < cond2 76.19/20.52 cond2 = cond3 76.19/20.52 gr < cond3 76.19/20.52 76.19/20.52 ---------------------------------------- 76.19/20.52 76.19/20.52 (49) RewriteLemmaProof (LOWER BOUND(ID)) 76.19/20.52 Proved the following rewrite lemma: 76.19/20.52 gr(gen_0':s4_0(n6_0), gen_0':s4_0(n6_0)) -> false, rt in Omega(1 + n6_0) 76.19/20.52 76.19/20.52 Induction Base: 76.19/20.52 gr(gen_0':s4_0(0), gen_0':s4_0(0)) ->_R^Omega(1) 76.19/20.53 false 76.19/20.53 76.19/20.53 Induction Step: 76.19/20.53 gr(gen_0':s4_0(+(n6_0, 1)), gen_0':s4_0(+(n6_0, 1))) ->_R^Omega(1) 76.19/20.53 gr(gen_0':s4_0(n6_0), gen_0':s4_0(n6_0)) ->_IH 76.19/20.53 false 76.19/20.53 76.19/20.53 We have rt in Omega(n^1) and sz in O(n). Thus, we have irc_R in Omega(n). 76.19/20.53 ---------------------------------------- 76.19/20.53 76.19/20.53 (50) 76.19/20.53 Complex Obligation (BEST) 76.19/20.53 76.19/20.53 ---------------------------------------- 76.19/20.53 76.19/20.53 (51) 76.19/20.53 Obligation: 76.19/20.53 Proved the lower bound n^1 for the following obligation: 76.19/20.53 76.19/20.53 Innermost TRS: 76.19/20.53 Rules: 76.19/20.53 cond1(true, x, y) -> cond2(gr(x, 0'), x, y) 76.19/20.53 cond2(true, x, y) -> cond1(or(gr(x, 0'), gr(y, 0')), p(x), y) 76.19/20.53 cond2(false, x, y) -> cond3(gr(y, 0'), x, y) 76.19/20.53 cond3(true, x, y) -> cond1(or(gr(x, 0'), gr(y, 0')), x, p(y)) 76.19/20.53 cond3(false, x, y) -> cond1(or(gr(x, 0'), gr(y, 0')), x, y) 76.19/20.53 gr(0', x) -> false 76.19/20.53 gr(s(x), 0') -> true 76.19/20.53 gr(s(x), s(y)) -> gr(x, y) 76.19/20.53 or(false, false) -> false 76.19/20.53 or(true, x) -> true 76.19/20.53 or(x, true) -> true 76.19/20.53 p(0') -> 0' 76.19/20.53 p(s(x)) -> x 76.19/20.53 76.19/20.53 Types: 76.19/20.53 cond1 :: true:false -> 0':s -> 0':s -> cond1:cond2:cond3 76.19/20.53 true :: true:false 76.19/20.53 cond2 :: true:false -> 0':s -> 0':s -> cond1:cond2:cond3 76.19/20.53 gr :: 0':s -> 0':s -> true:false 76.19/20.53 0' :: 0':s 76.19/20.53 or :: true:false -> true:false -> true:false 76.19/20.53 p :: 0':s -> 0':s 76.19/20.53 false :: true:false 76.19/20.53 cond3 :: true:false -> 0':s -> 0':s -> cond1:cond2:cond3 76.19/20.53 s :: 0':s -> 0':s 76.19/20.53 hole_cond1:cond2:cond31_0 :: cond1:cond2:cond3 76.19/20.53 hole_true:false2_0 :: true:false 76.19/20.53 hole_0':s3_0 :: 0':s 76.19/20.53 gen_0':s4_0 :: Nat -> 0':s 76.19/20.53 76.19/20.53 76.19/20.53 Generator Equations: 76.19/20.53 gen_0':s4_0(0) <=> 0' 76.19/20.53 gen_0':s4_0(+(x, 1)) <=> s(gen_0':s4_0(x)) 76.19/20.53 76.19/20.53 76.19/20.53 The following defined symbols remain to be analysed: 76.19/20.53 gr, cond1, cond2, cond3 76.19/20.53 76.19/20.53 They will be analysed ascendingly in the following order: 76.19/20.53 cond1 = cond2 76.19/20.53 gr < cond1 76.19/20.53 cond1 = cond3 76.19/20.53 gr < cond2 76.19/20.53 cond2 = cond3 76.19/20.53 gr < cond3 76.19/20.53 76.19/20.53 ---------------------------------------- 76.19/20.53 76.19/20.53 (52) LowerBoundPropagationProof (FINISHED) 76.19/20.53 Propagated lower bound. 76.19/20.53 ---------------------------------------- 76.19/20.53 76.19/20.53 (53) 76.19/20.53 BOUNDS(n^1, INF) 76.19/20.53 76.19/20.53 ---------------------------------------- 76.19/20.53 76.19/20.53 (54) 76.19/20.53 Obligation: 76.19/20.53 Innermost TRS: 76.19/20.53 Rules: 76.19/20.53 cond1(true, x, y) -> cond2(gr(x, 0'), x, y) 76.19/20.53 cond2(true, x, y) -> cond1(or(gr(x, 0'), gr(y, 0')), p(x), y) 76.19/20.53 cond2(false, x, y) -> cond3(gr(y, 0'), x, y) 76.19/20.53 cond3(true, x, y) -> cond1(or(gr(x, 0'), gr(y, 0')), x, p(y)) 76.19/20.53 cond3(false, x, y) -> cond1(or(gr(x, 0'), gr(y, 0')), x, y) 76.19/20.53 gr(0', x) -> false 76.19/20.53 gr(s(x), 0') -> true 76.19/20.53 gr(s(x), s(y)) -> gr(x, y) 76.19/20.53 or(false, false) -> false 76.19/20.53 or(true, x) -> true 76.19/20.53 or(x, true) -> true 76.19/20.53 p(0') -> 0' 76.19/20.53 p(s(x)) -> x 76.19/20.53 76.19/20.53 Types: 76.19/20.53 cond1 :: true:false -> 0':s -> 0':s -> cond1:cond2:cond3 76.19/20.53 true :: true:false 76.19/20.53 cond2 :: true:false -> 0':s -> 0':s -> cond1:cond2:cond3 76.19/20.53 gr :: 0':s -> 0':s -> true:false 76.19/20.53 0' :: 0':s 76.19/20.53 or :: true:false -> true:false -> true:false 76.19/20.53 p :: 0':s -> 0':s 76.19/20.53 false :: true:false 76.19/20.53 cond3 :: true:false -> 0':s -> 0':s -> cond1:cond2:cond3 76.19/20.53 s :: 0':s -> 0':s 76.19/20.53 hole_cond1:cond2:cond31_0 :: cond1:cond2:cond3 76.19/20.53 hole_true:false2_0 :: true:false 76.19/20.53 hole_0':s3_0 :: 0':s 76.19/20.53 gen_0':s4_0 :: Nat -> 0':s 76.19/20.53 76.19/20.53 76.19/20.53 Lemmas: 76.19/20.53 gr(gen_0':s4_0(n6_0), gen_0':s4_0(n6_0)) -> false, rt in Omega(1 + n6_0) 76.19/20.53 76.19/20.53 76.19/20.53 Generator Equations: 76.19/20.53 gen_0':s4_0(0) <=> 0' 76.19/20.53 gen_0':s4_0(+(x, 1)) <=> s(gen_0':s4_0(x)) 76.19/20.53 76.19/20.53 76.19/20.53 The following defined symbols remain to be analysed: 76.19/20.53 cond2, cond1, cond3 76.19/20.53 76.19/20.53 They will be analysed ascendingly in the following order: 76.19/20.53 cond1 = cond2 76.19/20.53 cond1 = cond3 76.19/20.53 cond2 = cond3 76.36/20.61 EOF