398.55/291.51 WORST_CASE(Omega(n^1), O(n^5)) 398.55/291.53 proof of /export/starexec/sandbox/benchmark/theBenchmark.xml 398.55/291.53 # AProVE Commit ID: 48fb2092695e11cc9f56e44b17a92a5f88ffb256 marcel 20180622 unpublished dirty 398.55/291.53 398.55/291.53 398.55/291.53 The Runtime Complexity (innermost) of the given CpxTRS could be proven to be BOUNDS(n^1, n^5). 398.55/291.53 398.55/291.53 (0) CpxTRS 398.55/291.53 (1) RelTrsToWeightedTrsProof [BOTH BOUNDS(ID, ID), 0 ms] 398.55/291.53 (2) CpxWeightedTrs 398.55/291.53 (3) TypeInferenceProof [BOTH BOUNDS(ID, ID), 0 ms] 398.55/291.53 (4) CpxTypedWeightedTrs 398.55/291.53 (5) CompletionProof [UPPER BOUND(ID), 0 ms] 398.55/291.53 (6) CpxTypedWeightedCompleteTrs 398.55/291.53 (7) NarrowingProof [BOTH BOUNDS(ID, ID), 0 ms] 398.55/291.53 (8) CpxTypedWeightedCompleteTrs 398.55/291.53 (9) CpxTypedWeightedTrsToRntsProof [UPPER BOUND(ID), 0 ms] 398.55/291.53 (10) CpxRNTS 398.55/291.53 (11) InliningProof [UPPER BOUND(ID), 32 ms] 398.55/291.53 (12) CpxRNTS 398.55/291.53 (13) SimplificationProof [BOTH BOUNDS(ID, ID), 4 ms] 398.55/291.53 (14) CpxRNTS 398.55/291.53 (15) CpxRntsAnalysisOrderProof [BOTH BOUNDS(ID, ID), 0 ms] 398.55/291.53 (16) CpxRNTS 398.55/291.53 (17) ResultPropagationProof [UPPER BOUND(ID), 0 ms] 398.55/291.53 (18) CpxRNTS 398.55/291.53 (19) IntTrsBoundProof [UPPER BOUND(ID), 82 ms] 398.55/291.53 (20) CpxRNTS 398.55/291.53 (21) IntTrsBoundProof [UPPER BOUND(ID), 7 ms] 398.55/291.53 (22) CpxRNTS 398.55/291.53 (23) ResultPropagationProof [UPPER BOUND(ID), 0 ms] 398.55/291.53 (24) CpxRNTS 398.55/291.53 (25) IntTrsBoundProof [UPPER BOUND(ID), 170 ms] 398.55/291.53 (26) CpxRNTS 398.55/291.53 (27) IntTrsBoundProof [UPPER BOUND(ID), 73 ms] 398.55/291.53 (28) CpxRNTS 398.55/291.53 (29) ResultPropagationProof [UPPER BOUND(ID), 0 ms] 398.55/291.53 (30) CpxRNTS 398.55/291.53 (31) IntTrsBoundProof [UPPER BOUND(ID), 36 ms] 398.55/291.53 (32) CpxRNTS 398.55/291.53 (33) IntTrsBoundProof [UPPER BOUND(ID), 5 ms] 398.55/291.53 (34) CpxRNTS 398.55/291.53 (35) ResultPropagationProof [UPPER BOUND(ID), 0 ms] 398.55/291.53 (36) CpxRNTS 398.55/291.53 (37) IntTrsBoundProof [UPPER BOUND(ID), 160 ms] 398.55/291.53 (38) CpxRNTS 398.55/291.53 (39) IntTrsBoundProof [UPPER BOUND(ID), 95 ms] 398.55/291.53 (40) CpxRNTS 398.55/291.53 (41) ResultPropagationProof [UPPER BOUND(ID), 0 ms] 398.55/291.53 (42) CpxRNTS 398.55/291.53 (43) IntTrsBoundProof [UPPER BOUND(ID), 107 ms] 398.55/291.53 (44) CpxRNTS 398.55/291.53 (45) IntTrsBoundProof [UPPER BOUND(ID), 0 ms] 398.55/291.53 (46) CpxRNTS 398.55/291.53 (47) ResultPropagationProof [UPPER BOUND(ID), 0 ms] 398.55/291.53 (48) CpxRNTS 398.55/291.53 (49) IntTrsBoundProof [UPPER BOUND(ID), 188 ms] 398.55/291.53 (50) CpxRNTS 398.55/291.53 (51) IntTrsBoundProof [UPPER BOUND(ID), 22 ms] 398.55/291.53 (52) CpxRNTS 398.55/291.53 (53) ResultPropagationProof [UPPER BOUND(ID), 0 ms] 398.55/291.53 (54) CpxRNTS 398.55/291.53 (55) IntTrsBoundProof [UPPER BOUND(ID), 86 ms] 398.55/291.53 (56) CpxRNTS 398.55/291.53 (57) IntTrsBoundProof [UPPER BOUND(ID), 0 ms] 398.55/291.53 (58) CpxRNTS 398.55/291.53 (59) ResultPropagationProof [UPPER BOUND(ID), 0 ms] 398.55/291.53 (60) CpxRNTS 398.55/291.53 (61) IntTrsBoundProof [UPPER BOUND(ID), 208 ms] 398.55/291.53 (62) CpxRNTS 398.55/291.53 (63) IntTrsBoundProof [UPPER BOUND(ID), 12 ms] 398.55/291.53 (64) CpxRNTS 398.55/291.53 (65) ResultPropagationProof [UPPER BOUND(ID), 0 ms] 398.55/291.53 (66) CpxRNTS 398.55/291.53 (67) IntTrsBoundProof [UPPER BOUND(ID), 147 ms] 398.55/291.53 (68) CpxRNTS 398.55/291.53 (69) IntTrsBoundProof [UPPER BOUND(ID), 0 ms] 398.55/291.53 (70) CpxRNTS 398.55/291.53 (71) ResultPropagationProof [UPPER BOUND(ID), 0 ms] 398.55/291.53 (72) CpxRNTS 398.55/291.53 (73) IntTrsBoundProof [UPPER BOUND(ID), 168 ms] 398.55/291.53 (74) CpxRNTS 398.55/291.53 (75) IntTrsBoundProof [UPPER BOUND(ID), 0 ms] 398.55/291.53 (76) CpxRNTS 398.55/291.53 (77) ResultPropagationProof [UPPER BOUND(ID), 0 ms] 398.55/291.53 (78) CpxRNTS 398.55/291.53 (79) IntTrsBoundProof [UPPER BOUND(ID), 95 ms] 398.55/291.53 (80) CpxRNTS 398.55/291.53 (81) IntTrsBoundProof [UPPER BOUND(ID), 0 ms] 398.55/291.53 (82) CpxRNTS 398.55/291.53 (83) FinalProof [FINISHED, 0 ms] 398.55/291.53 (84) BOUNDS(1, n^5) 398.55/291.53 (85) RelTrsToDecreasingLoopProblemProof [LOWER BOUND(ID), 0 ms] 398.55/291.53 (86) TRS for Loop Detection 398.55/291.53 (87) DecreasingLoopProof [LOWER BOUND(ID), 0 ms] 398.55/291.53 (88) BEST 398.55/291.53 (89) proven lower bound 398.55/291.53 (90) LowerBoundPropagationProof [FINISHED, 0 ms] 398.55/291.53 (91) BOUNDS(n^1, INF) 398.55/291.53 (92) TRS for Loop Detection 398.55/291.53 398.55/291.53 398.55/291.53 ---------------------------------------- 398.55/291.53 398.55/291.53 (0) 398.55/291.53 Obligation: 398.55/291.53 The Runtime Complexity (innermost) of the given CpxTRS could be proven to be BOUNDS(n^1, n^5). 398.55/291.53 398.55/291.53 398.55/291.53 The TRS R consists of the following rules: 398.55/291.53 398.55/291.53 f_0(x) -> a 398.55/291.53 f_1(x) -> g_1(x, x) 398.55/291.53 g_1(s(x), y) -> b(f_0(y), g_1(x, y)) 398.55/291.53 f_2(x) -> g_2(x, x) 398.55/291.53 g_2(s(x), y) -> b(f_1(y), g_2(x, y)) 398.55/291.53 f_3(x) -> g_3(x, x) 398.55/291.53 g_3(s(x), y) -> b(f_2(y), g_3(x, y)) 398.55/291.53 f_4(x) -> g_4(x, x) 398.55/291.53 g_4(s(x), y) -> b(f_3(y), g_4(x, y)) 398.55/291.53 f_5(x) -> g_5(x, x) 398.55/291.53 g_5(s(x), y) -> b(f_4(y), g_5(x, y)) 398.55/291.53 398.55/291.53 S is empty. 398.55/291.53 Rewrite Strategy: INNERMOST 398.55/291.53 ---------------------------------------- 398.55/291.53 398.55/291.53 (1) RelTrsToWeightedTrsProof (BOTH BOUNDS(ID, ID)) 398.55/291.53 Transformed relative TRS to weighted TRS 398.55/291.53 ---------------------------------------- 398.55/291.53 398.55/291.53 (2) 398.55/291.53 Obligation: 398.55/291.53 The Runtime Complexity (innermost) of the given CpxWeightedTrs could be proven to be BOUNDS(1, n^5). 398.55/291.53 398.55/291.53 398.55/291.53 The TRS R consists of the following rules: 398.55/291.53 398.55/291.53 f_0(x) -> a [1] 398.55/291.53 f_1(x) -> g_1(x, x) [1] 398.55/291.53 g_1(s(x), y) -> b(f_0(y), g_1(x, y)) [1] 398.55/291.53 f_2(x) -> g_2(x, x) [1] 398.55/291.53 g_2(s(x), y) -> b(f_1(y), g_2(x, y)) [1] 398.55/291.53 f_3(x) -> g_3(x, x) [1] 398.55/291.53 g_3(s(x), y) -> b(f_2(y), g_3(x, y)) [1] 398.55/291.53 f_4(x) -> g_4(x, x) [1] 398.55/291.53 g_4(s(x), y) -> b(f_3(y), g_4(x, y)) [1] 398.55/291.53 f_5(x) -> g_5(x, x) [1] 398.55/291.53 g_5(s(x), y) -> b(f_4(y), g_5(x, y)) [1] 398.55/291.53 398.55/291.53 Rewrite Strategy: INNERMOST 398.55/291.53 ---------------------------------------- 398.55/291.53 398.55/291.53 (3) TypeInferenceProof (BOTH BOUNDS(ID, ID)) 398.55/291.53 Infered types. 398.55/291.53 ---------------------------------------- 398.55/291.53 398.55/291.53 (4) 398.55/291.53 Obligation: 398.55/291.53 Runtime Complexity Weighted TRS with Types. 398.55/291.53 The TRS R consists of the following rules: 398.55/291.53 398.55/291.53 f_0(x) -> a [1] 398.55/291.53 f_1(x) -> g_1(x, x) [1] 398.55/291.53 g_1(s(x), y) -> b(f_0(y), g_1(x, y)) [1] 398.55/291.53 f_2(x) -> g_2(x, x) [1] 398.55/291.53 g_2(s(x), y) -> b(f_1(y), g_2(x, y)) [1] 398.55/291.53 f_3(x) -> g_3(x, x) [1] 398.55/291.53 g_3(s(x), y) -> b(f_2(y), g_3(x, y)) [1] 398.55/291.53 f_4(x) -> g_4(x, x) [1] 398.55/291.53 g_4(s(x), y) -> b(f_3(y), g_4(x, y)) [1] 398.55/291.53 f_5(x) -> g_5(x, x) [1] 398.55/291.53 g_5(s(x), y) -> b(f_4(y), g_5(x, y)) [1] 398.55/291.53 398.55/291.53 The TRS has the following type information: 398.55/291.53 f_0 :: s -> a:b 398.55/291.53 a :: a:b 398.55/291.53 f_1 :: s -> a:b 398.55/291.53 g_1 :: s -> s -> a:b 398.55/291.53 s :: s -> s 398.55/291.53 b :: a:b -> a:b -> a:b 398.55/291.53 f_2 :: s -> a:b 398.55/291.53 g_2 :: s -> s -> a:b 398.55/291.53 f_3 :: s -> a:b 398.55/291.53 g_3 :: s -> s -> a:b 398.55/291.53 f_4 :: s -> a:b 398.55/291.53 g_4 :: s -> s -> a:b 398.55/291.53 f_5 :: s -> a:b 398.55/291.53 g_5 :: s -> s -> a:b 398.55/291.53 398.55/291.53 Rewrite Strategy: INNERMOST 398.55/291.53 ---------------------------------------- 398.55/291.53 398.55/291.53 (5) CompletionProof (UPPER BOUND(ID)) 398.55/291.53 The transformation into a RNTS is sound, since: 398.55/291.53 398.55/291.53 (a) The obligation is a constructor system where every type has a constant constructor, 398.55/291.53 398.55/291.53 (b) The following defined symbols do not have to be completely defined, as they can never occur inside other defined symbols: 398.55/291.53 398.55/291.53 f_0_1 398.55/291.53 f_1_1 398.55/291.53 g_1_2 398.55/291.53 f_2_1 398.55/291.53 g_2_2 398.55/291.53 f_3_1 398.55/291.53 g_3_2 398.55/291.53 f_4_1 398.55/291.53 g_4_2 398.55/291.53 f_5_1 398.55/291.53 g_5_2 398.55/291.53 398.55/291.53 (c) The following functions are completely defined: 398.55/291.53 none 398.55/291.53 398.55/291.53 Due to the following rules being added: 398.55/291.53 none 398.55/291.53 398.55/291.53 And the following fresh constants: const 398.55/291.53 398.55/291.53 ---------------------------------------- 398.55/291.53 398.55/291.53 (6) 398.55/291.53 Obligation: 398.55/291.53 Runtime Complexity Weighted TRS where critical functions are completely defined. The underlying TRS is: 398.55/291.53 398.55/291.53 Runtime Complexity Weighted TRS with Types. 398.55/291.53 The TRS R consists of the following rules: 398.55/291.53 398.55/291.53 f_0(x) -> a [1] 398.55/291.53 f_1(x) -> g_1(x, x) [1] 398.55/291.53 g_1(s(x), y) -> b(f_0(y), g_1(x, y)) [1] 398.55/291.53 f_2(x) -> g_2(x, x) [1] 398.55/291.53 g_2(s(x), y) -> b(f_1(y), g_2(x, y)) [1] 398.55/291.53 f_3(x) -> g_3(x, x) [1] 398.55/291.53 g_3(s(x), y) -> b(f_2(y), g_3(x, y)) [1] 398.55/291.53 f_4(x) -> g_4(x, x) [1] 398.55/291.53 g_4(s(x), y) -> b(f_3(y), g_4(x, y)) [1] 398.55/291.53 f_5(x) -> g_5(x, x) [1] 398.55/291.53 g_5(s(x), y) -> b(f_4(y), g_5(x, y)) [1] 398.55/291.53 398.55/291.53 The TRS has the following type information: 398.55/291.53 f_0 :: s -> a:b 398.55/291.53 a :: a:b 398.55/291.53 f_1 :: s -> a:b 398.55/291.53 g_1 :: s -> s -> a:b 398.55/291.53 s :: s -> s 398.55/291.54 b :: a:b -> a:b -> a:b 398.55/291.54 f_2 :: s -> a:b 398.55/291.54 g_2 :: s -> s -> a:b 398.55/291.54 f_3 :: s -> a:b 398.55/291.54 g_3 :: s -> s -> a:b 398.55/291.54 f_4 :: s -> a:b 398.55/291.54 g_4 :: s -> s -> a:b 398.55/291.54 f_5 :: s -> a:b 398.55/291.54 g_5 :: s -> s -> a:b 398.55/291.54 const :: s 398.55/291.54 398.55/291.54 Rewrite Strategy: INNERMOST 398.55/291.54 ---------------------------------------- 398.55/291.54 398.55/291.54 (7) NarrowingProof (BOTH BOUNDS(ID, ID)) 398.55/291.54 Narrowed the inner basic terms of all right-hand sides by a single narrowing step. 398.55/291.54 ---------------------------------------- 398.55/291.54 398.55/291.54 (8) 398.55/291.54 Obligation: 398.55/291.54 Runtime Complexity Weighted TRS where critical functions are completely defined. The underlying TRS is: 398.55/291.54 398.55/291.54 Runtime Complexity Weighted TRS with Types. 398.55/291.54 The TRS R consists of the following rules: 398.55/291.54 398.55/291.54 f_0(x) -> a [1] 398.55/291.54 f_1(x) -> g_1(x, x) [1] 398.55/291.54 g_1(s(x), y) -> b(f_0(y), g_1(x, y)) [1] 398.55/291.54 f_2(x) -> g_2(x, x) [1] 398.55/291.54 g_2(s(x), y) -> b(f_1(y), g_2(x, y)) [1] 398.55/291.54 f_3(x) -> g_3(x, x) [1] 398.55/291.54 g_3(s(x), y) -> b(f_2(y), g_3(x, y)) [1] 398.55/291.54 f_4(x) -> g_4(x, x) [1] 398.55/291.54 g_4(s(x), y) -> b(f_3(y), g_4(x, y)) [1] 398.55/291.54 f_5(x) -> g_5(x, x) [1] 398.55/291.54 g_5(s(x), y) -> b(f_4(y), g_5(x, y)) [1] 398.55/291.54 398.55/291.54 The TRS has the following type information: 398.55/291.54 f_0 :: s -> a:b 398.55/291.54 a :: a:b 398.55/291.54 f_1 :: s -> a:b 398.55/291.54 g_1 :: s -> s -> a:b 398.55/291.54 s :: s -> s 398.55/291.54 b :: a:b -> a:b -> a:b 398.55/291.54 f_2 :: s -> a:b 398.55/291.54 g_2 :: s -> s -> a:b 398.55/291.54 f_3 :: s -> a:b 398.55/291.54 g_3 :: s -> s -> a:b 398.55/291.54 f_4 :: s -> a:b 398.55/291.54 g_4 :: s -> s -> a:b 398.55/291.54 f_5 :: s -> a:b 398.55/291.54 g_5 :: s -> s -> a:b 398.55/291.54 const :: s 398.55/291.54 398.55/291.54 Rewrite Strategy: INNERMOST 398.55/291.54 ---------------------------------------- 398.55/291.54 398.55/291.54 (9) CpxTypedWeightedTrsToRntsProof (UPPER BOUND(ID)) 398.55/291.54 Transformed the TRS into an over-approximating RNTS by (improved) Size Abstraction. 398.55/291.54 The constant constructors are abstracted as follows: 398.55/291.54 398.55/291.54 a => 0 398.55/291.54 const => 0 398.55/291.54 398.55/291.54 ---------------------------------------- 398.55/291.54 398.55/291.54 (10) 398.55/291.54 Obligation: 398.55/291.54 Complexity RNTS consisting of the following rules: 398.55/291.54 398.55/291.54 f_0(z) -{ 1 }-> 0 :|: x >= 0, z = x 398.55/291.54 f_1(z) -{ 1 }-> g_1(x, x) :|: x >= 0, z = x 398.55/291.54 f_2(z) -{ 1 }-> g_2(x, x) :|: x >= 0, z = x 398.55/291.54 f_3(z) -{ 1 }-> g_3(x, x) :|: x >= 0, z = x 398.55/291.54 f_4(z) -{ 1 }-> g_4(x, x) :|: x >= 0, z = x 398.55/291.54 f_5(z) -{ 1 }-> g_5(x, x) :|: x >= 0, z = x 398.55/291.54 g_1(z, z') -{ 1 }-> 1 + f_0(y) + g_1(x, y) :|: x >= 0, y >= 0, z = 1 + x, z' = y 398.55/291.54 g_2(z, z') -{ 1 }-> 1 + f_1(y) + g_2(x, y) :|: x >= 0, y >= 0, z = 1 + x, z' = y 398.55/291.54 g_3(z, z') -{ 1 }-> 1 + f_2(y) + g_3(x, y) :|: x >= 0, y >= 0, z = 1 + x, z' = y 398.55/291.54 g_4(z, z') -{ 1 }-> 1 + f_3(y) + g_4(x, y) :|: x >= 0, y >= 0, z = 1 + x, z' = y 398.55/291.54 g_5(z, z') -{ 1 }-> 1 + f_4(y) + g_5(x, y) :|: x >= 0, y >= 0, z = 1 + x, z' = y 398.55/291.54 398.55/291.54 398.55/291.54 ---------------------------------------- 398.55/291.54 398.55/291.54 (11) InliningProof (UPPER BOUND(ID)) 398.55/291.54 Inlined the following terminating rules on right-hand sides where appropriate: 398.55/291.54 398.55/291.54 f_0(z) -{ 1 }-> 0 :|: x >= 0, z = x 398.55/291.54 398.55/291.54 ---------------------------------------- 398.55/291.54 398.55/291.54 (12) 398.55/291.54 Obligation: 398.55/291.54 Complexity RNTS consisting of the following rules: 398.55/291.54 398.55/291.54 f_0(z) -{ 1 }-> 0 :|: x >= 0, z = x 398.55/291.54 f_1(z) -{ 1 }-> g_1(x, x) :|: x >= 0, z = x 398.55/291.54 f_2(z) -{ 1 }-> g_2(x, x) :|: x >= 0, z = x 398.55/291.54 f_3(z) -{ 1 }-> g_3(x, x) :|: x >= 0, z = x 398.55/291.54 f_4(z) -{ 1 }-> g_4(x, x) :|: x >= 0, z = x 398.55/291.54 f_5(z) -{ 1 }-> g_5(x, x) :|: x >= 0, z = x 398.55/291.54 g_1(z, z') -{ 2 }-> 1 + 0 + g_1(x, y) :|: x >= 0, y >= 0, z = 1 + x, z' = y, x' >= 0, y = x' 398.55/291.54 g_2(z, z') -{ 1 }-> 1 + f_1(y) + g_2(x, y) :|: x >= 0, y >= 0, z = 1 + x, z' = y 398.55/291.54 g_3(z, z') -{ 1 }-> 1 + f_2(y) + g_3(x, y) :|: x >= 0, y >= 0, z = 1 + x, z' = y 398.55/291.54 g_4(z, z') -{ 1 }-> 1 + f_3(y) + g_4(x, y) :|: x >= 0, y >= 0, z = 1 + x, z' = y 398.55/291.54 g_5(z, z') -{ 1 }-> 1 + f_4(y) + g_5(x, y) :|: x >= 0, y >= 0, z = 1 + x, z' = y 398.55/291.54 398.55/291.54 398.55/291.54 ---------------------------------------- 398.55/291.54 398.55/291.54 (13) SimplificationProof (BOTH BOUNDS(ID, ID)) 398.55/291.54 Simplified the RNTS by moving equalities from the constraints into the right-hand sides. 398.55/291.54 ---------------------------------------- 398.55/291.54 398.55/291.54 (14) 398.55/291.54 Obligation: 398.55/291.54 Complexity RNTS consisting of the following rules: 398.55/291.54 398.55/291.54 f_0(z) -{ 1 }-> 0 :|: z >= 0 398.55/291.54 f_1(z) -{ 1 }-> g_1(z, z) :|: z >= 0 398.55/291.54 f_2(z) -{ 1 }-> g_2(z, z) :|: z >= 0 398.55/291.54 f_3(z) -{ 1 }-> g_3(z, z) :|: z >= 0 398.55/291.54 f_4(z) -{ 1 }-> g_4(z, z) :|: z >= 0 398.55/291.54 f_5(z) -{ 1 }-> g_5(z, z) :|: z >= 0 398.55/291.54 g_1(z, z') -{ 2 }-> 1 + 0 + g_1(z - 1, z') :|: z - 1 >= 0, z' >= 0 398.55/291.54 g_2(z, z') -{ 1 }-> 1 + f_1(z') + g_2(z - 1, z') :|: z - 1 >= 0, z' >= 0 398.55/291.54 g_3(z, z') -{ 1 }-> 1 + f_2(z') + g_3(z - 1, z') :|: z - 1 >= 0, z' >= 0 398.55/291.54 g_4(z, z') -{ 1 }-> 1 + f_3(z') + g_4(z - 1, z') :|: z - 1 >= 0, z' >= 0 398.55/291.54 g_5(z, z') -{ 1 }-> 1 + f_4(z') + g_5(z - 1, z') :|: z - 1 >= 0, z' >= 0 398.55/291.54 398.55/291.54 398.55/291.54 ---------------------------------------- 398.55/291.54 398.55/291.54 (15) CpxRntsAnalysisOrderProof (BOTH BOUNDS(ID, ID)) 398.55/291.54 Found the following analysis order by SCC decomposition: 398.55/291.54 398.55/291.54 { f_0 } 398.55/291.54 { g_1 } 398.55/291.54 { f_1 } 398.55/291.54 { g_2 } 398.55/291.54 { f_2 } 398.55/291.54 { g_3 } 398.55/291.54 { f_3 } 398.55/291.54 { g_4 } 398.55/291.54 { f_4 } 398.55/291.54 { g_5 } 398.55/291.54 { f_5 } 398.55/291.54 398.55/291.54 ---------------------------------------- 398.55/291.54 398.55/291.54 (16) 398.55/291.54 Obligation: 398.55/291.54 Complexity RNTS consisting of the following rules: 398.55/291.54 398.55/291.54 f_0(z) -{ 1 }-> 0 :|: z >= 0 398.55/291.54 f_1(z) -{ 1 }-> g_1(z, z) :|: z >= 0 398.55/291.54 f_2(z) -{ 1 }-> g_2(z, z) :|: z >= 0 398.55/291.54 f_3(z) -{ 1 }-> g_3(z, z) :|: z >= 0 398.55/291.54 f_4(z) -{ 1 }-> g_4(z, z) :|: z >= 0 398.55/291.54 f_5(z) -{ 1 }-> g_5(z, z) :|: z >= 0 398.55/291.54 g_1(z, z') -{ 2 }-> 1 + 0 + g_1(z - 1, z') :|: z - 1 >= 0, z' >= 0 398.55/291.54 g_2(z, z') -{ 1 }-> 1 + f_1(z') + g_2(z - 1, z') :|: z - 1 >= 0, z' >= 0 398.55/291.54 g_3(z, z') -{ 1 }-> 1 + f_2(z') + g_3(z - 1, z') :|: z - 1 >= 0, z' >= 0 398.55/291.54 g_4(z, z') -{ 1 }-> 1 + f_3(z') + g_4(z - 1, z') :|: z - 1 >= 0, z' >= 0 398.55/291.54 g_5(z, z') -{ 1 }-> 1 + f_4(z') + g_5(z - 1, z') :|: z - 1 >= 0, z' >= 0 398.55/291.54 398.55/291.54 Function symbols to be analyzed: {f_0}, {g_1}, {f_1}, {g_2}, {f_2}, {g_3}, {f_3}, {g_4}, {f_4}, {g_5}, {f_5} 398.55/291.54 398.55/291.54 ---------------------------------------- 398.55/291.54 398.55/291.54 (17) ResultPropagationProof (UPPER BOUND(ID)) 398.55/291.54 Applied inner abstraction using the recently inferred runtime/size bounds where possible. 398.55/291.54 ---------------------------------------- 398.55/291.54 398.55/291.54 (18) 398.55/291.54 Obligation: 398.55/291.54 Complexity RNTS consisting of the following rules: 398.55/291.54 398.55/291.54 f_0(z) -{ 1 }-> 0 :|: z >= 0 398.55/291.54 f_1(z) -{ 1 }-> g_1(z, z) :|: z >= 0 398.55/291.54 f_2(z) -{ 1 }-> g_2(z, z) :|: z >= 0 398.55/291.54 f_3(z) -{ 1 }-> g_3(z, z) :|: z >= 0 398.55/291.54 f_4(z) -{ 1 }-> g_4(z, z) :|: z >= 0 398.55/291.54 f_5(z) -{ 1 }-> g_5(z, z) :|: z >= 0 398.55/291.54 g_1(z, z') -{ 2 }-> 1 + 0 + g_1(z - 1, z') :|: z - 1 >= 0, z' >= 0 398.55/291.54 g_2(z, z') -{ 1 }-> 1 + f_1(z') + g_2(z - 1, z') :|: z - 1 >= 0, z' >= 0 398.55/291.54 g_3(z, z') -{ 1 }-> 1 + f_2(z') + g_3(z - 1, z') :|: z - 1 >= 0, z' >= 0 398.55/291.54 g_4(z, z') -{ 1 }-> 1 + f_3(z') + g_4(z - 1, z') :|: z - 1 >= 0, z' >= 0 398.55/291.54 g_5(z, z') -{ 1 }-> 1 + f_4(z') + g_5(z - 1, z') :|: z - 1 >= 0, z' >= 0 398.55/291.54 398.55/291.54 Function symbols to be analyzed: {f_0}, {g_1}, {f_1}, {g_2}, {f_2}, {g_3}, {f_3}, {g_4}, {f_4}, {g_5}, {f_5} 398.55/291.54 398.55/291.54 ---------------------------------------- 398.55/291.54 398.55/291.54 (19) IntTrsBoundProof (UPPER BOUND(ID)) 398.55/291.54 398.55/291.54 Computed SIZE bound using CoFloCo for: f_0 398.55/291.54 after applying outer abstraction to obtain an ITS, 398.55/291.54 resulting in: O(1) with polynomial bound: 0 398.55/291.54 398.55/291.54 ---------------------------------------- 398.55/291.54 398.55/291.54 (20) 398.55/291.54 Obligation: 398.55/291.54 Complexity RNTS consisting of the following rules: 398.55/291.54 398.55/291.54 f_0(z) -{ 1 }-> 0 :|: z >= 0 398.55/291.54 f_1(z) -{ 1 }-> g_1(z, z) :|: z >= 0 398.55/291.54 f_2(z) -{ 1 }-> g_2(z, z) :|: z >= 0 398.55/291.54 f_3(z) -{ 1 }-> g_3(z, z) :|: z >= 0 398.55/291.54 f_4(z) -{ 1 }-> g_4(z, z) :|: z >= 0 398.55/291.54 f_5(z) -{ 1 }-> g_5(z, z) :|: z >= 0 398.55/291.54 g_1(z, z') -{ 2 }-> 1 + 0 + g_1(z - 1, z') :|: z - 1 >= 0, z' >= 0 398.55/291.54 g_2(z, z') -{ 1 }-> 1 + f_1(z') + g_2(z - 1, z') :|: z - 1 >= 0, z' >= 0 398.55/291.54 g_3(z, z') -{ 1 }-> 1 + f_2(z') + g_3(z - 1, z') :|: z - 1 >= 0, z' >= 0 398.55/291.54 g_4(z, z') -{ 1 }-> 1 + f_3(z') + g_4(z - 1, z') :|: z - 1 >= 0, z' >= 0 398.55/291.54 g_5(z, z') -{ 1 }-> 1 + f_4(z') + g_5(z - 1, z') :|: z - 1 >= 0, z' >= 0 398.55/291.54 398.55/291.54 Function symbols to be analyzed: {f_0}, {g_1}, {f_1}, {g_2}, {f_2}, {g_3}, {f_3}, {g_4}, {f_4}, {g_5}, {f_5} 398.55/291.54 Previous analysis results are: 398.55/291.54 f_0: runtime: ?, size: O(1) [0] 398.55/291.54 398.55/291.54 ---------------------------------------- 398.55/291.54 398.55/291.54 (21) IntTrsBoundProof (UPPER BOUND(ID)) 398.55/291.54 398.55/291.54 Computed RUNTIME bound using CoFloCo for: f_0 398.55/291.54 after applying outer abstraction to obtain an ITS, 398.55/291.54 resulting in: O(1) with polynomial bound: 1 398.55/291.54 398.55/291.54 ---------------------------------------- 398.55/291.54 398.55/291.54 (22) 398.55/291.54 Obligation: 398.55/291.54 Complexity RNTS consisting of the following rules: 398.55/291.54 398.55/291.54 f_0(z) -{ 1 }-> 0 :|: z >= 0 398.55/291.54 f_1(z) -{ 1 }-> g_1(z, z) :|: z >= 0 398.55/291.54 f_2(z) -{ 1 }-> g_2(z, z) :|: z >= 0 398.55/291.54 f_3(z) -{ 1 }-> g_3(z, z) :|: z >= 0 398.55/291.54 f_4(z) -{ 1 }-> g_4(z, z) :|: z >= 0 398.55/291.54 f_5(z) -{ 1 }-> g_5(z, z) :|: z >= 0 398.55/291.54 g_1(z, z') -{ 2 }-> 1 + 0 + g_1(z - 1, z') :|: z - 1 >= 0, z' >= 0 398.55/291.54 g_2(z, z') -{ 1 }-> 1 + f_1(z') + g_2(z - 1, z') :|: z - 1 >= 0, z' >= 0 398.55/291.54 g_3(z, z') -{ 1 }-> 1 + f_2(z') + g_3(z - 1, z') :|: z - 1 >= 0, z' >= 0 398.55/291.54 g_4(z, z') -{ 1 }-> 1 + f_3(z') + g_4(z - 1, z') :|: z - 1 >= 0, z' >= 0 398.55/291.54 g_5(z, z') -{ 1 }-> 1 + f_4(z') + g_5(z - 1, z') :|: z - 1 >= 0, z' >= 0 398.55/291.54 398.55/291.54 Function symbols to be analyzed: {g_1}, {f_1}, {g_2}, {f_2}, {g_3}, {f_3}, {g_4}, {f_4}, {g_5}, {f_5} 398.55/291.54 Previous analysis results are: 398.55/291.54 f_0: runtime: O(1) [1], size: O(1) [0] 398.55/291.54 398.55/291.54 ---------------------------------------- 398.55/291.54 398.55/291.54 (23) ResultPropagationProof (UPPER BOUND(ID)) 398.55/291.54 Applied inner abstraction using the recently inferred runtime/size bounds where possible. 398.55/291.54 ---------------------------------------- 398.55/291.54 398.55/291.54 (24) 398.55/291.54 Obligation: 398.55/291.54 Complexity RNTS consisting of the following rules: 398.55/291.54 398.55/291.54 f_0(z) -{ 1 }-> 0 :|: z >= 0 398.55/291.54 f_1(z) -{ 1 }-> g_1(z, z) :|: z >= 0 398.55/291.54 f_2(z) -{ 1 }-> g_2(z, z) :|: z >= 0 398.55/291.54 f_3(z) -{ 1 }-> g_3(z, z) :|: z >= 0 398.55/291.54 f_4(z) -{ 1 }-> g_4(z, z) :|: z >= 0 398.55/291.54 f_5(z) -{ 1 }-> g_5(z, z) :|: z >= 0 398.55/291.54 g_1(z, z') -{ 2 }-> 1 + 0 + g_1(z - 1, z') :|: z - 1 >= 0, z' >= 0 398.55/291.54 g_2(z, z') -{ 1 }-> 1 + f_1(z') + g_2(z - 1, z') :|: z - 1 >= 0, z' >= 0 398.55/291.54 g_3(z, z') -{ 1 }-> 1 + f_2(z') + g_3(z - 1, z') :|: z - 1 >= 0, z' >= 0 398.55/291.54 g_4(z, z') -{ 1 }-> 1 + f_3(z') + g_4(z - 1, z') :|: z - 1 >= 0, z' >= 0 398.55/291.54 g_5(z, z') -{ 1 }-> 1 + f_4(z') + g_5(z - 1, z') :|: z - 1 >= 0, z' >= 0 398.55/291.54 398.55/291.54 Function symbols to be analyzed: {g_1}, {f_1}, {g_2}, {f_2}, {g_3}, {f_3}, {g_4}, {f_4}, {g_5}, {f_5} 398.55/291.54 Previous analysis results are: 398.55/291.54 f_0: runtime: O(1) [1], size: O(1) [0] 398.55/291.54 398.55/291.54 ---------------------------------------- 398.55/291.54 398.55/291.54 (25) IntTrsBoundProof (UPPER BOUND(ID)) 398.55/291.54 398.55/291.54 Computed SIZE bound using CoFloCo for: g_1 398.55/291.54 after applying outer abstraction to obtain an ITS, 398.55/291.54 resulting in: O(1) with polynomial bound: 0 398.55/291.54 398.55/291.54 ---------------------------------------- 398.55/291.54 398.55/291.54 (26) 398.55/291.54 Obligation: 398.55/291.54 Complexity RNTS consisting of the following rules: 398.55/291.54 398.55/291.54 f_0(z) -{ 1 }-> 0 :|: z >= 0 398.55/291.54 f_1(z) -{ 1 }-> g_1(z, z) :|: z >= 0 398.55/291.54 f_2(z) -{ 1 }-> g_2(z, z) :|: z >= 0 398.55/291.54 f_3(z) -{ 1 }-> g_3(z, z) :|: z >= 0 398.55/291.54 f_4(z) -{ 1 }-> g_4(z, z) :|: z >= 0 398.55/291.54 f_5(z) -{ 1 }-> g_5(z, z) :|: z >= 0 398.55/291.54 g_1(z, z') -{ 2 }-> 1 + 0 + g_1(z - 1, z') :|: z - 1 >= 0, z' >= 0 398.55/291.54 g_2(z, z') -{ 1 }-> 1 + f_1(z') + g_2(z - 1, z') :|: z - 1 >= 0, z' >= 0 398.55/291.54 g_3(z, z') -{ 1 }-> 1 + f_2(z') + g_3(z - 1, z') :|: z - 1 >= 0, z' >= 0 398.55/291.54 g_4(z, z') -{ 1 }-> 1 + f_3(z') + g_4(z - 1, z') :|: z - 1 >= 0, z' >= 0 398.55/291.54 g_5(z, z') -{ 1 }-> 1 + f_4(z') + g_5(z - 1, z') :|: z - 1 >= 0, z' >= 0 398.55/291.54 398.55/291.54 Function symbols to be analyzed: {g_1}, {f_1}, {g_2}, {f_2}, {g_3}, {f_3}, {g_4}, {f_4}, {g_5}, {f_5} 398.55/291.54 Previous analysis results are: 398.55/291.54 f_0: runtime: O(1) [1], size: O(1) [0] 398.55/291.54 g_1: runtime: ?, size: O(1) [0] 398.55/291.54 398.55/291.54 ---------------------------------------- 398.55/291.54 398.55/291.54 (27) IntTrsBoundProof (UPPER BOUND(ID)) 398.55/291.54 398.55/291.54 Computed RUNTIME bound using CoFloCo for: g_1 398.55/291.54 after applying outer abstraction to obtain an ITS, 398.55/291.54 resulting in: O(n^1) with polynomial bound: 2*z 398.55/291.54 398.55/291.54 ---------------------------------------- 398.55/291.54 398.55/291.54 (28) 398.55/291.54 Obligation: 398.55/291.54 Complexity RNTS consisting of the following rules: 398.55/291.54 398.55/291.54 f_0(z) -{ 1 }-> 0 :|: z >= 0 398.55/291.54 f_1(z) -{ 1 }-> g_1(z, z) :|: z >= 0 398.55/291.54 f_2(z) -{ 1 }-> g_2(z, z) :|: z >= 0 398.55/291.54 f_3(z) -{ 1 }-> g_3(z, z) :|: z >= 0 398.55/291.54 f_4(z) -{ 1 }-> g_4(z, z) :|: z >= 0 398.55/291.54 f_5(z) -{ 1 }-> g_5(z, z) :|: z >= 0 398.55/291.54 g_1(z, z') -{ 2 }-> 1 + 0 + g_1(z - 1, z') :|: z - 1 >= 0, z' >= 0 398.55/291.54 g_2(z, z') -{ 1 }-> 1 + f_1(z') + g_2(z - 1, z') :|: z - 1 >= 0, z' >= 0 398.55/291.54 g_3(z, z') -{ 1 }-> 1 + f_2(z') + g_3(z - 1, z') :|: z - 1 >= 0, z' >= 0 398.55/291.54 g_4(z, z') -{ 1 }-> 1 + f_3(z') + g_4(z - 1, z') :|: z - 1 >= 0, z' >= 0 398.55/291.54 g_5(z, z') -{ 1 }-> 1 + f_4(z') + g_5(z - 1, z') :|: z - 1 >= 0, z' >= 0 398.55/291.54 398.55/291.54 Function symbols to be analyzed: {f_1}, {g_2}, {f_2}, {g_3}, {f_3}, {g_4}, {f_4}, {g_5}, {f_5} 398.55/291.54 Previous analysis results are: 398.55/291.54 f_0: runtime: O(1) [1], size: O(1) [0] 398.55/291.54 g_1: runtime: O(n^1) [2*z], size: O(1) [0] 398.55/291.54 398.55/291.54 ---------------------------------------- 398.55/291.54 398.55/291.54 (29) ResultPropagationProof (UPPER BOUND(ID)) 398.55/291.54 Applied inner abstraction using the recently inferred runtime/size bounds where possible. 398.55/291.54 ---------------------------------------- 398.55/291.54 398.55/291.54 (30) 398.55/291.54 Obligation: 398.55/291.54 Complexity RNTS consisting of the following rules: 398.55/291.54 398.55/291.54 f_0(z) -{ 1 }-> 0 :|: z >= 0 398.55/291.54 f_1(z) -{ 1 + 2*z }-> s :|: s >= 0, s <= 0, z >= 0 398.55/291.54 f_2(z) -{ 1 }-> g_2(z, z) :|: z >= 0 398.55/291.54 f_3(z) -{ 1 }-> g_3(z, z) :|: z >= 0 398.55/291.54 f_4(z) -{ 1 }-> g_4(z, z) :|: z >= 0 398.55/291.54 f_5(z) -{ 1 }-> g_5(z, z) :|: z >= 0 398.55/291.54 g_1(z, z') -{ 2*z }-> 1 + 0 + s' :|: s' >= 0, s' <= 0, z - 1 >= 0, z' >= 0 398.55/291.54 g_2(z, z') -{ 1 }-> 1 + f_1(z') + g_2(z - 1, z') :|: z - 1 >= 0, z' >= 0 398.55/291.54 g_3(z, z') -{ 1 }-> 1 + f_2(z') + g_3(z - 1, z') :|: z - 1 >= 0, z' >= 0 398.55/291.54 g_4(z, z') -{ 1 }-> 1 + f_3(z') + g_4(z - 1, z') :|: z - 1 >= 0, z' >= 0 398.55/291.54 g_5(z, z') -{ 1 }-> 1 + f_4(z') + g_5(z - 1, z') :|: z - 1 >= 0, z' >= 0 398.55/291.54 398.55/291.54 Function symbols to be analyzed: {f_1}, {g_2}, {f_2}, {g_3}, {f_3}, {g_4}, {f_4}, {g_5}, {f_5} 398.55/291.54 Previous analysis results are: 398.55/291.54 f_0: runtime: O(1) [1], size: O(1) [0] 398.55/291.54 g_1: runtime: O(n^1) [2*z], size: O(1) [0] 398.55/291.54 398.55/291.54 ---------------------------------------- 398.55/291.54 398.55/291.54 (31) IntTrsBoundProof (UPPER BOUND(ID)) 398.55/291.54 398.55/291.54 Computed SIZE bound using CoFloCo for: f_1 398.55/291.54 after applying outer abstraction to obtain an ITS, 398.55/291.54 resulting in: O(1) with polynomial bound: 0 398.55/291.54 398.55/291.54 ---------------------------------------- 398.55/291.54 398.55/291.54 (32) 398.55/291.54 Obligation: 398.55/291.54 Complexity RNTS consisting of the following rules: 398.55/291.54 398.55/291.54 f_0(z) -{ 1 }-> 0 :|: z >= 0 398.55/291.54 f_1(z) -{ 1 + 2*z }-> s :|: s >= 0, s <= 0, z >= 0 398.55/291.54 f_2(z) -{ 1 }-> g_2(z, z) :|: z >= 0 398.55/291.54 f_3(z) -{ 1 }-> g_3(z, z) :|: z >= 0 398.55/291.54 f_4(z) -{ 1 }-> g_4(z, z) :|: z >= 0 398.55/291.54 f_5(z) -{ 1 }-> g_5(z, z) :|: z >= 0 398.55/291.54 g_1(z, z') -{ 2*z }-> 1 + 0 + s' :|: s' >= 0, s' <= 0, z - 1 >= 0, z' >= 0 398.55/291.54 g_2(z, z') -{ 1 }-> 1 + f_1(z') + g_2(z - 1, z') :|: z - 1 >= 0, z' >= 0 398.55/291.54 g_3(z, z') -{ 1 }-> 1 + f_2(z') + g_3(z - 1, z') :|: z - 1 >= 0, z' >= 0 398.55/291.54 g_4(z, z') -{ 1 }-> 1 + f_3(z') + g_4(z - 1, z') :|: z - 1 >= 0, z' >= 0 398.55/291.54 g_5(z, z') -{ 1 }-> 1 + f_4(z') + g_5(z - 1, z') :|: z - 1 >= 0, z' >= 0 398.55/291.54 398.55/291.54 Function symbols to be analyzed: {f_1}, {g_2}, {f_2}, {g_3}, {f_3}, {g_4}, {f_4}, {g_5}, {f_5} 398.55/291.54 Previous analysis results are: 398.55/291.54 f_0: runtime: O(1) [1], size: O(1) [0] 398.55/291.54 g_1: runtime: O(n^1) [2*z], size: O(1) [0] 398.55/291.54 f_1: runtime: ?, size: O(1) [0] 398.55/291.54 398.55/291.54 ---------------------------------------- 398.55/291.54 398.55/291.54 (33) IntTrsBoundProof (UPPER BOUND(ID)) 398.55/291.54 398.55/291.54 Computed RUNTIME bound using CoFloCo for: f_1 398.55/291.54 after applying outer abstraction to obtain an ITS, 398.55/291.54 resulting in: O(n^1) with polynomial bound: 1 + 2*z 398.55/291.54 398.55/291.54 ---------------------------------------- 398.55/291.54 398.55/291.54 (34) 398.55/291.54 Obligation: 398.55/291.54 Complexity RNTS consisting of the following rules: 398.55/291.54 398.55/291.54 f_0(z) -{ 1 }-> 0 :|: z >= 0 398.55/291.54 f_1(z) -{ 1 + 2*z }-> s :|: s >= 0, s <= 0, z >= 0 398.55/291.54 f_2(z) -{ 1 }-> g_2(z, z) :|: z >= 0 398.55/291.54 f_3(z) -{ 1 }-> g_3(z, z) :|: z >= 0 398.55/291.54 f_4(z) -{ 1 }-> g_4(z, z) :|: z >= 0 398.55/291.54 f_5(z) -{ 1 }-> g_5(z, z) :|: z >= 0 398.55/291.54 g_1(z, z') -{ 2*z }-> 1 + 0 + s' :|: s' >= 0, s' <= 0, z - 1 >= 0, z' >= 0 398.55/291.54 g_2(z, z') -{ 1 }-> 1 + f_1(z') + g_2(z - 1, z') :|: z - 1 >= 0, z' >= 0 398.55/291.54 g_3(z, z') -{ 1 }-> 1 + f_2(z') + g_3(z - 1, z') :|: z - 1 >= 0, z' >= 0 398.55/291.54 g_4(z, z') -{ 1 }-> 1 + f_3(z') + g_4(z - 1, z') :|: z - 1 >= 0, z' >= 0 398.55/291.54 g_5(z, z') -{ 1 }-> 1 + f_4(z') + g_5(z - 1, z') :|: z - 1 >= 0, z' >= 0 398.55/291.54 398.55/291.54 Function symbols to be analyzed: {g_2}, {f_2}, {g_3}, {f_3}, {g_4}, {f_4}, {g_5}, {f_5} 398.55/291.54 Previous analysis results are: 398.55/291.54 f_0: runtime: O(1) [1], size: O(1) [0] 398.55/291.54 g_1: runtime: O(n^1) [2*z], size: O(1) [0] 398.55/291.54 f_1: runtime: O(n^1) [1 + 2*z], size: O(1) [0] 398.55/291.54 398.55/291.54 ---------------------------------------- 398.55/291.54 398.55/291.54 (35) ResultPropagationProof (UPPER BOUND(ID)) 398.55/291.54 Applied inner abstraction using the recently inferred runtime/size bounds where possible. 398.55/291.54 ---------------------------------------- 398.55/291.54 398.55/291.54 (36) 398.55/291.54 Obligation: 398.55/291.54 Complexity RNTS consisting of the following rules: 398.55/291.54 398.55/291.54 f_0(z) -{ 1 }-> 0 :|: z >= 0 398.55/291.54 f_1(z) -{ 1 + 2*z }-> s :|: s >= 0, s <= 0, z >= 0 398.55/291.54 f_2(z) -{ 1 }-> g_2(z, z) :|: z >= 0 398.55/291.54 f_3(z) -{ 1 }-> g_3(z, z) :|: z >= 0 398.55/291.54 f_4(z) -{ 1 }-> g_4(z, z) :|: z >= 0 398.55/291.54 f_5(z) -{ 1 }-> g_5(z, z) :|: z >= 0 398.55/291.54 g_1(z, z') -{ 2*z }-> 1 + 0 + s' :|: s' >= 0, s' <= 0, z - 1 >= 0, z' >= 0 398.55/291.54 g_2(z, z') -{ 2 + 2*z' }-> 1 + s'' + g_2(z - 1, z') :|: s'' >= 0, s'' <= 0, z - 1 >= 0, z' >= 0 398.55/291.54 g_3(z, z') -{ 1 }-> 1 + f_2(z') + g_3(z - 1, z') :|: z - 1 >= 0, z' >= 0 398.55/291.54 g_4(z, z') -{ 1 }-> 1 + f_3(z') + g_4(z - 1, z') :|: z - 1 >= 0, z' >= 0 398.55/291.54 g_5(z, z') -{ 1 }-> 1 + f_4(z') + g_5(z - 1, z') :|: z - 1 >= 0, z' >= 0 398.55/291.54 398.55/291.54 Function symbols to be analyzed: {g_2}, {f_2}, {g_3}, {f_3}, {g_4}, {f_4}, {g_5}, {f_5} 398.55/291.54 Previous analysis results are: 398.55/291.54 f_0: runtime: O(1) [1], size: O(1) [0] 398.55/291.54 g_1: runtime: O(n^1) [2*z], size: O(1) [0] 398.55/291.54 f_1: runtime: O(n^1) [1 + 2*z], size: O(1) [0] 398.55/291.54 398.55/291.54 ---------------------------------------- 398.55/291.54 398.55/291.54 (37) IntTrsBoundProof (UPPER BOUND(ID)) 398.55/291.54 398.55/291.54 Computed SIZE bound using CoFloCo for: g_2 398.55/291.54 after applying outer abstraction to obtain an ITS, 398.55/291.54 resulting in: O(1) with polynomial bound: 0 398.55/291.54 398.55/291.54 ---------------------------------------- 398.55/291.54 398.55/291.54 (38) 398.55/291.54 Obligation: 398.55/291.54 Complexity RNTS consisting of the following rules: 398.55/291.54 398.55/291.54 f_0(z) -{ 1 }-> 0 :|: z >= 0 398.55/291.54 f_1(z) -{ 1 + 2*z }-> s :|: s >= 0, s <= 0, z >= 0 398.55/291.54 f_2(z) -{ 1 }-> g_2(z, z) :|: z >= 0 398.55/291.54 f_3(z) -{ 1 }-> g_3(z, z) :|: z >= 0 398.55/291.54 f_4(z) -{ 1 }-> g_4(z, z) :|: z >= 0 398.55/291.54 f_5(z) -{ 1 }-> g_5(z, z) :|: z >= 0 398.55/291.54 g_1(z, z') -{ 2*z }-> 1 + 0 + s' :|: s' >= 0, s' <= 0, z - 1 >= 0, z' >= 0 398.55/291.54 g_2(z, z') -{ 2 + 2*z' }-> 1 + s'' + g_2(z - 1, z') :|: s'' >= 0, s'' <= 0, z - 1 >= 0, z' >= 0 398.55/291.54 g_3(z, z') -{ 1 }-> 1 + f_2(z') + g_3(z - 1, z') :|: z - 1 >= 0, z' >= 0 398.55/291.54 g_4(z, z') -{ 1 }-> 1 + f_3(z') + g_4(z - 1, z') :|: z - 1 >= 0, z' >= 0 398.55/291.54 g_5(z, z') -{ 1 }-> 1 + f_4(z') + g_5(z - 1, z') :|: z - 1 >= 0, z' >= 0 398.55/291.54 398.55/291.54 Function symbols to be analyzed: {g_2}, {f_2}, {g_3}, {f_3}, {g_4}, {f_4}, {g_5}, {f_5} 398.55/291.54 Previous analysis results are: 398.55/291.54 f_0: runtime: O(1) [1], size: O(1) [0] 398.55/291.54 g_1: runtime: O(n^1) [2*z], size: O(1) [0] 398.55/291.54 f_1: runtime: O(n^1) [1 + 2*z], size: O(1) [0] 398.55/291.54 g_2: runtime: ?, size: O(1) [0] 398.55/291.54 398.55/291.54 ---------------------------------------- 398.55/291.54 398.55/291.54 (39) IntTrsBoundProof (UPPER BOUND(ID)) 398.55/291.54 398.55/291.54 Computed RUNTIME bound using CoFloCo for: g_2 398.55/291.54 after applying outer abstraction to obtain an ITS, 398.55/291.54 resulting in: O(n^2) with polynomial bound: 2*z + 2*z*z' 398.55/291.54 398.55/291.54 ---------------------------------------- 398.55/291.54 398.55/291.54 (40) 398.55/291.54 Obligation: 398.55/291.54 Complexity RNTS consisting of the following rules: 398.55/291.54 398.55/291.54 f_0(z) -{ 1 }-> 0 :|: z >= 0 398.55/291.54 f_1(z) -{ 1 + 2*z }-> s :|: s >= 0, s <= 0, z >= 0 398.55/291.54 f_2(z) -{ 1 }-> g_2(z, z) :|: z >= 0 398.55/291.54 f_3(z) -{ 1 }-> g_3(z, z) :|: z >= 0 398.55/291.54 f_4(z) -{ 1 }-> g_4(z, z) :|: z >= 0 398.55/291.54 f_5(z) -{ 1 }-> g_5(z, z) :|: z >= 0 398.55/291.54 g_1(z, z') -{ 2*z }-> 1 + 0 + s' :|: s' >= 0, s' <= 0, z - 1 >= 0, z' >= 0 398.55/291.54 g_2(z, z') -{ 2 + 2*z' }-> 1 + s'' + g_2(z - 1, z') :|: s'' >= 0, s'' <= 0, z - 1 >= 0, z' >= 0 398.55/291.54 g_3(z, z') -{ 1 }-> 1 + f_2(z') + g_3(z - 1, z') :|: z - 1 >= 0, z' >= 0 398.55/291.54 g_4(z, z') -{ 1 }-> 1 + f_3(z') + g_4(z - 1, z') :|: z - 1 >= 0, z' >= 0 398.55/291.54 g_5(z, z') -{ 1 }-> 1 + f_4(z') + g_5(z - 1, z') :|: z - 1 >= 0, z' >= 0 398.55/291.54 398.55/291.54 Function symbols to be analyzed: {f_2}, {g_3}, {f_3}, {g_4}, {f_4}, {g_5}, {f_5} 398.55/291.54 Previous analysis results are: 398.55/291.54 f_0: runtime: O(1) [1], size: O(1) [0] 398.55/291.54 g_1: runtime: O(n^1) [2*z], size: O(1) [0] 398.55/291.54 f_1: runtime: O(n^1) [1 + 2*z], size: O(1) [0] 398.55/291.54 g_2: runtime: O(n^2) [2*z + 2*z*z'], size: O(1) [0] 398.55/291.54 398.55/291.54 ---------------------------------------- 398.55/291.54 398.55/291.54 (41) ResultPropagationProof (UPPER BOUND(ID)) 398.55/291.54 Applied inner abstraction using the recently inferred runtime/size bounds where possible. 398.55/291.54 ---------------------------------------- 398.55/291.54 398.55/291.54 (42) 398.55/291.54 Obligation: 398.55/291.54 Complexity RNTS consisting of the following rules: 398.55/291.54 398.55/291.54 f_0(z) -{ 1 }-> 0 :|: z >= 0 398.55/291.54 f_1(z) -{ 1 + 2*z }-> s :|: s >= 0, s <= 0, z >= 0 398.55/291.54 f_2(z) -{ 1 + 2*z + 2*z^2 }-> s1 :|: s1 >= 0, s1 <= 0, z >= 0 398.55/291.54 f_3(z) -{ 1 }-> g_3(z, z) :|: z >= 0 398.55/291.54 f_4(z) -{ 1 }-> g_4(z, z) :|: z >= 0 398.55/291.54 f_5(z) -{ 1 }-> g_5(z, z) :|: z >= 0 398.55/291.54 g_1(z, z') -{ 2*z }-> 1 + 0 + s' :|: s' >= 0, s' <= 0, z - 1 >= 0, z' >= 0 398.55/291.54 g_2(z, z') -{ 2*z + 2*z*z' }-> 1 + s'' + s2 :|: s2 >= 0, s2 <= 0, s'' >= 0, s'' <= 0, z - 1 >= 0, z' >= 0 398.55/291.54 g_3(z, z') -{ 1 }-> 1 + f_2(z') + g_3(z - 1, z') :|: z - 1 >= 0, z' >= 0 398.55/291.54 g_4(z, z') -{ 1 }-> 1 + f_3(z') + g_4(z - 1, z') :|: z - 1 >= 0, z' >= 0 398.55/291.54 g_5(z, z') -{ 1 }-> 1 + f_4(z') + g_5(z - 1, z') :|: z - 1 >= 0, z' >= 0 398.55/291.54 398.55/291.54 Function symbols to be analyzed: {f_2}, {g_3}, {f_3}, {g_4}, {f_4}, {g_5}, {f_5} 398.55/291.54 Previous analysis results are: 398.55/291.54 f_0: runtime: O(1) [1], size: O(1) [0] 398.55/291.54 g_1: runtime: O(n^1) [2*z], size: O(1) [0] 398.55/291.54 f_1: runtime: O(n^1) [1 + 2*z], size: O(1) [0] 398.55/291.54 g_2: runtime: O(n^2) [2*z + 2*z*z'], size: O(1) [0] 398.55/291.54 398.55/291.54 ---------------------------------------- 398.55/291.54 398.55/291.54 (43) IntTrsBoundProof (UPPER BOUND(ID)) 398.55/291.54 398.55/291.54 Computed SIZE bound using CoFloCo for: f_2 398.55/291.54 after applying outer abstraction to obtain an ITS, 398.55/291.54 resulting in: O(1) with polynomial bound: 0 398.55/291.54 398.55/291.54 ---------------------------------------- 398.55/291.54 398.55/291.54 (44) 398.55/291.54 Obligation: 398.55/291.54 Complexity RNTS consisting of the following rules: 398.55/291.54 398.55/291.54 f_0(z) -{ 1 }-> 0 :|: z >= 0 398.55/291.54 f_1(z) -{ 1 + 2*z }-> s :|: s >= 0, s <= 0, z >= 0 398.55/291.54 f_2(z) -{ 1 + 2*z + 2*z^2 }-> s1 :|: s1 >= 0, s1 <= 0, z >= 0 398.55/291.54 f_3(z) -{ 1 }-> g_3(z, z) :|: z >= 0 398.55/291.54 f_4(z) -{ 1 }-> g_4(z, z) :|: z >= 0 398.55/291.54 f_5(z) -{ 1 }-> g_5(z, z) :|: z >= 0 398.55/291.54 g_1(z, z') -{ 2*z }-> 1 + 0 + s' :|: s' >= 0, s' <= 0, z - 1 >= 0, z' >= 0 398.55/291.54 g_2(z, z') -{ 2*z + 2*z*z' }-> 1 + s'' + s2 :|: s2 >= 0, s2 <= 0, s'' >= 0, s'' <= 0, z - 1 >= 0, z' >= 0 398.55/291.54 g_3(z, z') -{ 1 }-> 1 + f_2(z') + g_3(z - 1, z') :|: z - 1 >= 0, z' >= 0 398.55/291.54 g_4(z, z') -{ 1 }-> 1 + f_3(z') + g_4(z - 1, z') :|: z - 1 >= 0, z' >= 0 398.55/291.54 g_5(z, z') -{ 1 }-> 1 + f_4(z') + g_5(z - 1, z') :|: z - 1 >= 0, z' >= 0 398.55/291.54 398.55/291.54 Function symbols to be analyzed: {f_2}, {g_3}, {f_3}, {g_4}, {f_4}, {g_5}, {f_5} 398.55/291.54 Previous analysis results are: 398.55/291.54 f_0: runtime: O(1) [1], size: O(1) [0] 398.55/291.54 g_1: runtime: O(n^1) [2*z], size: O(1) [0] 398.55/291.54 f_1: runtime: O(n^1) [1 + 2*z], size: O(1) [0] 398.55/291.54 g_2: runtime: O(n^2) [2*z + 2*z*z'], size: O(1) [0] 398.55/291.54 f_2: runtime: ?, size: O(1) [0] 398.55/291.54 398.55/291.54 ---------------------------------------- 398.55/291.54 398.55/291.54 (45) IntTrsBoundProof (UPPER BOUND(ID)) 398.55/291.54 398.55/291.54 Computed RUNTIME bound using KoAT for: f_2 398.55/291.54 after applying outer abstraction to obtain an ITS, 398.55/291.54 resulting in: O(n^2) with polynomial bound: 1 + 2*z + 2*z^2 398.55/291.54 398.55/291.54 ---------------------------------------- 398.55/291.54 398.55/291.54 (46) 398.55/291.54 Obligation: 398.55/291.54 Complexity RNTS consisting of the following rules: 398.55/291.54 398.55/291.54 f_0(z) -{ 1 }-> 0 :|: z >= 0 398.55/291.54 f_1(z) -{ 1 + 2*z }-> s :|: s >= 0, s <= 0, z >= 0 398.55/291.54 f_2(z) -{ 1 + 2*z + 2*z^2 }-> s1 :|: s1 >= 0, s1 <= 0, z >= 0 398.55/291.54 f_3(z) -{ 1 }-> g_3(z, z) :|: z >= 0 398.55/291.54 f_4(z) -{ 1 }-> g_4(z, z) :|: z >= 0 398.55/291.54 f_5(z) -{ 1 }-> g_5(z, z) :|: z >= 0 398.55/291.54 g_1(z, z') -{ 2*z }-> 1 + 0 + s' :|: s' >= 0, s' <= 0, z - 1 >= 0, z' >= 0 398.55/291.54 g_2(z, z') -{ 2*z + 2*z*z' }-> 1 + s'' + s2 :|: s2 >= 0, s2 <= 0, s'' >= 0, s'' <= 0, z - 1 >= 0, z' >= 0 398.55/291.54 g_3(z, z') -{ 1 }-> 1 + f_2(z') + g_3(z - 1, z') :|: z - 1 >= 0, z' >= 0 398.55/291.54 g_4(z, z') -{ 1 }-> 1 + f_3(z') + g_4(z - 1, z') :|: z - 1 >= 0, z' >= 0 398.55/291.54 g_5(z, z') -{ 1 }-> 1 + f_4(z') + g_5(z - 1, z') :|: z - 1 >= 0, z' >= 0 398.55/291.54 398.55/291.54 Function symbols to be analyzed: {g_3}, {f_3}, {g_4}, {f_4}, {g_5}, {f_5} 398.55/291.54 Previous analysis results are: 398.55/291.54 f_0: runtime: O(1) [1], size: O(1) [0] 398.55/291.54 g_1: runtime: O(n^1) [2*z], size: O(1) [0] 398.55/291.54 f_1: runtime: O(n^1) [1 + 2*z], size: O(1) [0] 398.55/291.54 g_2: runtime: O(n^2) [2*z + 2*z*z'], size: O(1) [0] 398.55/291.54 f_2: runtime: O(n^2) [1 + 2*z + 2*z^2], size: O(1) [0] 398.55/291.54 398.55/291.54 ---------------------------------------- 398.55/291.54 398.55/291.54 (47) ResultPropagationProof (UPPER BOUND(ID)) 398.55/291.54 Applied inner abstraction using the recently inferred runtime/size bounds where possible. 398.55/291.54 ---------------------------------------- 398.55/291.54 398.55/291.54 (48) 398.55/291.54 Obligation: 398.55/291.54 Complexity RNTS consisting of the following rules: 398.55/291.54 398.55/291.54 f_0(z) -{ 1 }-> 0 :|: z >= 0 398.55/291.54 f_1(z) -{ 1 + 2*z }-> s :|: s >= 0, s <= 0, z >= 0 398.55/291.54 f_2(z) -{ 1 + 2*z + 2*z^2 }-> s1 :|: s1 >= 0, s1 <= 0, z >= 0 398.55/291.54 f_3(z) -{ 1 }-> g_3(z, z) :|: z >= 0 398.55/291.54 f_4(z) -{ 1 }-> g_4(z, z) :|: z >= 0 398.55/291.54 f_5(z) -{ 1 }-> g_5(z, z) :|: z >= 0 398.55/291.54 g_1(z, z') -{ 2*z }-> 1 + 0 + s' :|: s' >= 0, s' <= 0, z - 1 >= 0, z' >= 0 398.55/291.54 g_2(z, z') -{ 2*z + 2*z*z' }-> 1 + s'' + s2 :|: s2 >= 0, s2 <= 0, s'' >= 0, s'' <= 0, z - 1 >= 0, z' >= 0 398.55/291.54 g_3(z, z') -{ 2 + 2*z' + 2*z'^2 }-> 1 + s3 + g_3(z - 1, z') :|: s3 >= 0, s3 <= 0, z - 1 >= 0, z' >= 0 398.55/291.54 g_4(z, z') -{ 1 }-> 1 + f_3(z') + g_4(z - 1, z') :|: z - 1 >= 0, z' >= 0 398.55/291.54 g_5(z, z') -{ 1 }-> 1 + f_4(z') + g_5(z - 1, z') :|: z - 1 >= 0, z' >= 0 398.55/291.54 398.55/291.54 Function symbols to be analyzed: {g_3}, {f_3}, {g_4}, {f_4}, {g_5}, {f_5} 398.55/291.54 Previous analysis results are: 398.55/291.54 f_0: runtime: O(1) [1], size: O(1) [0] 398.55/291.54 g_1: runtime: O(n^1) [2*z], size: O(1) [0] 398.55/291.54 f_1: runtime: O(n^1) [1 + 2*z], size: O(1) [0] 398.55/291.54 g_2: runtime: O(n^2) [2*z + 2*z*z'], size: O(1) [0] 398.55/291.54 f_2: runtime: O(n^2) [1 + 2*z + 2*z^2], size: O(1) [0] 398.55/291.54 398.55/291.54 ---------------------------------------- 398.55/291.54 398.55/291.54 (49) IntTrsBoundProof (UPPER BOUND(ID)) 398.55/291.54 398.55/291.54 Computed SIZE bound using CoFloCo for: g_3 398.55/291.54 after applying outer abstraction to obtain an ITS, 398.55/291.54 resulting in: O(1) with polynomial bound: 0 398.55/291.54 398.55/291.54 ---------------------------------------- 398.55/291.54 398.55/291.54 (50) 398.55/291.54 Obligation: 398.55/291.54 Complexity RNTS consisting of the following rules: 398.55/291.54 398.55/291.54 f_0(z) -{ 1 }-> 0 :|: z >= 0 398.55/291.54 f_1(z) -{ 1 + 2*z }-> s :|: s >= 0, s <= 0, z >= 0 398.55/291.54 f_2(z) -{ 1 + 2*z + 2*z^2 }-> s1 :|: s1 >= 0, s1 <= 0, z >= 0 398.55/291.54 f_3(z) -{ 1 }-> g_3(z, z) :|: z >= 0 398.55/291.54 f_4(z) -{ 1 }-> g_4(z, z) :|: z >= 0 398.55/291.54 f_5(z) -{ 1 }-> g_5(z, z) :|: z >= 0 398.55/291.54 g_1(z, z') -{ 2*z }-> 1 + 0 + s' :|: s' >= 0, s' <= 0, z - 1 >= 0, z' >= 0 398.55/291.54 g_2(z, z') -{ 2*z + 2*z*z' }-> 1 + s'' + s2 :|: s2 >= 0, s2 <= 0, s'' >= 0, s'' <= 0, z - 1 >= 0, z' >= 0 398.55/291.54 g_3(z, z') -{ 2 + 2*z' + 2*z'^2 }-> 1 + s3 + g_3(z - 1, z') :|: s3 >= 0, s3 <= 0, z - 1 >= 0, z' >= 0 398.55/291.54 g_4(z, z') -{ 1 }-> 1 + f_3(z') + g_4(z - 1, z') :|: z - 1 >= 0, z' >= 0 398.55/291.54 g_5(z, z') -{ 1 }-> 1 + f_4(z') + g_5(z - 1, z') :|: z - 1 >= 0, z' >= 0 398.55/291.54 398.55/291.54 Function symbols to be analyzed: {g_3}, {f_3}, {g_4}, {f_4}, {g_5}, {f_5} 398.55/291.54 Previous analysis results are: 398.55/291.54 f_0: runtime: O(1) [1], size: O(1) [0] 398.55/291.54 g_1: runtime: O(n^1) [2*z], size: O(1) [0] 398.55/291.54 f_1: runtime: O(n^1) [1 + 2*z], size: O(1) [0] 398.55/291.54 g_2: runtime: O(n^2) [2*z + 2*z*z'], size: O(1) [0] 398.55/291.54 f_2: runtime: O(n^2) [1 + 2*z + 2*z^2], size: O(1) [0] 398.55/291.54 g_3: runtime: ?, size: O(1) [0] 398.55/291.54 398.55/291.54 ---------------------------------------- 398.55/291.54 398.55/291.54 (51) IntTrsBoundProof (UPPER BOUND(ID)) 398.55/291.54 398.55/291.54 Computed RUNTIME bound using KoAT for: g_3 398.55/291.54 after applying outer abstraction to obtain an ITS, 398.55/291.54 resulting in: O(n^3) with polynomial bound: 2*z + 2*z*z' + 2*z*z'^2 398.55/291.54 398.55/291.54 ---------------------------------------- 398.55/291.54 398.55/291.54 (52) 398.55/291.54 Obligation: 398.55/291.54 Complexity RNTS consisting of the following rules: 398.55/291.54 398.55/291.54 f_0(z) -{ 1 }-> 0 :|: z >= 0 398.55/291.54 f_1(z) -{ 1 + 2*z }-> s :|: s >= 0, s <= 0, z >= 0 398.55/291.54 f_2(z) -{ 1 + 2*z + 2*z^2 }-> s1 :|: s1 >= 0, s1 <= 0, z >= 0 398.55/291.54 f_3(z) -{ 1 }-> g_3(z, z) :|: z >= 0 398.55/291.54 f_4(z) -{ 1 }-> g_4(z, z) :|: z >= 0 398.55/291.54 f_5(z) -{ 1 }-> g_5(z, z) :|: z >= 0 398.55/291.54 g_1(z, z') -{ 2*z }-> 1 + 0 + s' :|: s' >= 0, s' <= 0, z - 1 >= 0, z' >= 0 398.55/291.54 g_2(z, z') -{ 2*z + 2*z*z' }-> 1 + s'' + s2 :|: s2 >= 0, s2 <= 0, s'' >= 0, s'' <= 0, z - 1 >= 0, z' >= 0 398.55/291.54 g_3(z, z') -{ 2 + 2*z' + 2*z'^2 }-> 1 + s3 + g_3(z - 1, z') :|: s3 >= 0, s3 <= 0, z - 1 >= 0, z' >= 0 398.55/291.54 g_4(z, z') -{ 1 }-> 1 + f_3(z') + g_4(z - 1, z') :|: z - 1 >= 0, z' >= 0 398.55/291.54 g_5(z, z') -{ 1 }-> 1 + f_4(z') + g_5(z - 1, z') :|: z - 1 >= 0, z' >= 0 398.55/291.54 398.55/291.54 Function symbols to be analyzed: {f_3}, {g_4}, {f_4}, {g_5}, {f_5} 398.55/291.54 Previous analysis results are: 398.55/291.54 f_0: runtime: O(1) [1], size: O(1) [0] 398.55/291.54 g_1: runtime: O(n^1) [2*z], size: O(1) [0] 398.55/291.54 f_1: runtime: O(n^1) [1 + 2*z], size: O(1) [0] 398.55/291.54 g_2: runtime: O(n^2) [2*z + 2*z*z'], size: O(1) [0] 398.55/291.54 f_2: runtime: O(n^2) [1 + 2*z + 2*z^2], size: O(1) [0] 398.55/291.54 g_3: runtime: O(n^3) [2*z + 2*z*z' + 2*z*z'^2], size: O(1) [0] 398.55/291.54 398.55/291.54 ---------------------------------------- 398.55/291.54 398.55/291.54 (53) ResultPropagationProof (UPPER BOUND(ID)) 398.55/291.54 Applied inner abstraction using the recently inferred runtime/size bounds where possible. 398.55/291.54 ---------------------------------------- 398.55/291.54 398.55/291.54 (54) 398.55/291.54 Obligation: 398.55/291.54 Complexity RNTS consisting of the following rules: 398.55/291.54 398.55/291.54 f_0(z) -{ 1 }-> 0 :|: z >= 0 398.55/291.54 f_1(z) -{ 1 + 2*z }-> s :|: s >= 0, s <= 0, z >= 0 398.55/291.54 f_2(z) -{ 1 + 2*z + 2*z^2 }-> s1 :|: s1 >= 0, s1 <= 0, z >= 0 398.55/291.54 f_3(z) -{ 1 + 2*z + 2*z^2 + 2*z^3 }-> s4 :|: s4 >= 0, s4 <= 0, z >= 0 398.55/291.54 f_4(z) -{ 1 }-> g_4(z, z) :|: z >= 0 398.55/291.54 f_5(z) -{ 1 }-> g_5(z, z) :|: z >= 0 398.55/291.54 g_1(z, z') -{ 2*z }-> 1 + 0 + s' :|: s' >= 0, s' <= 0, z - 1 >= 0, z' >= 0 398.55/291.54 g_2(z, z') -{ 2*z + 2*z*z' }-> 1 + s'' + s2 :|: s2 >= 0, s2 <= 0, s'' >= 0, s'' <= 0, z - 1 >= 0, z' >= 0 398.55/291.54 g_3(z, z') -{ 2*z + 2*z*z' + 2*z*z'^2 }-> 1 + s3 + s5 :|: s5 >= 0, s5 <= 0, s3 >= 0, s3 <= 0, z - 1 >= 0, z' >= 0 398.55/291.54 g_4(z, z') -{ 1 }-> 1 + f_3(z') + g_4(z - 1, z') :|: z - 1 >= 0, z' >= 0 398.55/291.54 g_5(z, z') -{ 1 }-> 1 + f_4(z') + g_5(z - 1, z') :|: z - 1 >= 0, z' >= 0 398.55/291.54 398.55/291.54 Function symbols to be analyzed: {f_3}, {g_4}, {f_4}, {g_5}, {f_5} 398.55/291.54 Previous analysis results are: 398.55/291.54 f_0: runtime: O(1) [1], size: O(1) [0] 398.55/291.54 g_1: runtime: O(n^1) [2*z], size: O(1) [0] 398.55/291.54 f_1: runtime: O(n^1) [1 + 2*z], size: O(1) [0] 398.55/291.54 g_2: runtime: O(n^2) [2*z + 2*z*z'], size: O(1) [0] 398.55/291.54 f_2: runtime: O(n^2) [1 + 2*z + 2*z^2], size: O(1) [0] 398.55/291.54 g_3: runtime: O(n^3) [2*z + 2*z*z' + 2*z*z'^2], size: O(1) [0] 398.55/291.54 398.55/291.54 ---------------------------------------- 398.55/291.54 398.55/291.54 (55) IntTrsBoundProof (UPPER BOUND(ID)) 398.55/291.54 398.55/291.54 Computed SIZE bound using CoFloCo for: f_3 398.55/291.54 after applying outer abstraction to obtain an ITS, 398.55/291.54 resulting in: O(1) with polynomial bound: 0 398.55/291.54 398.55/291.54 ---------------------------------------- 398.55/291.54 398.55/291.54 (56) 398.55/291.54 Obligation: 398.55/291.54 Complexity RNTS consisting of the following rules: 398.55/291.54 398.55/291.54 f_0(z) -{ 1 }-> 0 :|: z >= 0 398.55/291.54 f_1(z) -{ 1 + 2*z }-> s :|: s >= 0, s <= 0, z >= 0 398.55/291.54 f_2(z) -{ 1 + 2*z + 2*z^2 }-> s1 :|: s1 >= 0, s1 <= 0, z >= 0 398.55/291.54 f_3(z) -{ 1 + 2*z + 2*z^2 + 2*z^3 }-> s4 :|: s4 >= 0, s4 <= 0, z >= 0 398.55/291.54 f_4(z) -{ 1 }-> g_4(z, z) :|: z >= 0 398.55/291.54 f_5(z) -{ 1 }-> g_5(z, z) :|: z >= 0 398.55/291.54 g_1(z, z') -{ 2*z }-> 1 + 0 + s' :|: s' >= 0, s' <= 0, z - 1 >= 0, z' >= 0 398.55/291.54 g_2(z, z') -{ 2*z + 2*z*z' }-> 1 + s'' + s2 :|: s2 >= 0, s2 <= 0, s'' >= 0, s'' <= 0, z - 1 >= 0, z' >= 0 398.55/291.54 g_3(z, z') -{ 2*z + 2*z*z' + 2*z*z'^2 }-> 1 + s3 + s5 :|: s5 >= 0, s5 <= 0, s3 >= 0, s3 <= 0, z - 1 >= 0, z' >= 0 398.55/291.54 g_4(z, z') -{ 1 }-> 1 + f_3(z') + g_4(z - 1, z') :|: z - 1 >= 0, z' >= 0 398.55/291.54 g_5(z, z') -{ 1 }-> 1 + f_4(z') + g_5(z - 1, z') :|: z - 1 >= 0, z' >= 0 398.55/291.54 398.55/291.54 Function symbols to be analyzed: {f_3}, {g_4}, {f_4}, {g_5}, {f_5} 398.55/291.54 Previous analysis results are: 398.55/291.54 f_0: runtime: O(1) [1], size: O(1) [0] 398.55/291.54 g_1: runtime: O(n^1) [2*z], size: O(1) [0] 398.55/291.54 f_1: runtime: O(n^1) [1 + 2*z], size: O(1) [0] 398.55/291.54 g_2: runtime: O(n^2) [2*z + 2*z*z'], size: O(1) [0] 398.55/291.54 f_2: runtime: O(n^2) [1 + 2*z + 2*z^2], size: O(1) [0] 398.55/291.54 g_3: runtime: O(n^3) [2*z + 2*z*z' + 2*z*z'^2], size: O(1) [0] 398.55/291.54 f_3: runtime: ?, size: O(1) [0] 398.55/291.54 398.55/291.54 ---------------------------------------- 398.55/291.54 398.55/291.54 (57) IntTrsBoundProof (UPPER BOUND(ID)) 398.55/291.54 398.55/291.54 Computed RUNTIME bound using KoAT for: f_3 398.55/291.54 after applying outer abstraction to obtain an ITS, 398.55/291.54 resulting in: O(n^3) with polynomial bound: 1 + 2*z + 2*z^2 + 2*z^3 398.55/291.54 398.55/291.54 ---------------------------------------- 398.55/291.54 398.55/291.54 (58) 398.55/291.54 Obligation: 398.55/291.54 Complexity RNTS consisting of the following rules: 398.55/291.54 398.55/291.54 f_0(z) -{ 1 }-> 0 :|: z >= 0 398.55/291.54 f_1(z) -{ 1 + 2*z }-> s :|: s >= 0, s <= 0, z >= 0 398.55/291.54 f_2(z) -{ 1 + 2*z + 2*z^2 }-> s1 :|: s1 >= 0, s1 <= 0, z >= 0 398.55/291.54 f_3(z) -{ 1 + 2*z + 2*z^2 + 2*z^3 }-> s4 :|: s4 >= 0, s4 <= 0, z >= 0 398.55/291.54 f_4(z) -{ 1 }-> g_4(z, z) :|: z >= 0 398.55/291.54 f_5(z) -{ 1 }-> g_5(z, z) :|: z >= 0 398.55/291.54 g_1(z, z') -{ 2*z }-> 1 + 0 + s' :|: s' >= 0, s' <= 0, z - 1 >= 0, z' >= 0 398.55/291.54 g_2(z, z') -{ 2*z + 2*z*z' }-> 1 + s'' + s2 :|: s2 >= 0, s2 <= 0, s'' >= 0, s'' <= 0, z - 1 >= 0, z' >= 0 398.55/291.54 g_3(z, z') -{ 2*z + 2*z*z' + 2*z*z'^2 }-> 1 + s3 + s5 :|: s5 >= 0, s5 <= 0, s3 >= 0, s3 <= 0, z - 1 >= 0, z' >= 0 398.55/291.54 g_4(z, z') -{ 1 }-> 1 + f_3(z') + g_4(z - 1, z') :|: z - 1 >= 0, z' >= 0 398.55/291.54 g_5(z, z') -{ 1 }-> 1 + f_4(z') + g_5(z - 1, z') :|: z - 1 >= 0, z' >= 0 398.55/291.54 398.55/291.54 Function symbols to be analyzed: {g_4}, {f_4}, {g_5}, {f_5} 398.55/291.54 Previous analysis results are: 398.55/291.54 f_0: runtime: O(1) [1], size: O(1) [0] 398.55/291.54 g_1: runtime: O(n^1) [2*z], size: O(1) [0] 398.55/291.54 f_1: runtime: O(n^1) [1 + 2*z], size: O(1) [0] 398.55/291.54 g_2: runtime: O(n^2) [2*z + 2*z*z'], size: O(1) [0] 398.55/291.54 f_2: runtime: O(n^2) [1 + 2*z + 2*z^2], size: O(1) [0] 398.55/291.54 g_3: runtime: O(n^3) [2*z + 2*z*z' + 2*z*z'^2], size: O(1) [0] 398.55/291.54 f_3: runtime: O(n^3) [1 + 2*z + 2*z^2 + 2*z^3], size: O(1) [0] 398.55/291.54 398.55/291.54 ---------------------------------------- 398.55/291.54 398.55/291.54 (59) ResultPropagationProof (UPPER BOUND(ID)) 398.55/291.54 Applied inner abstraction using the recently inferred runtime/size bounds where possible. 398.55/291.54 ---------------------------------------- 398.55/291.54 398.55/291.54 (60) 398.55/291.54 Obligation: 398.55/291.54 Complexity RNTS consisting of the following rules: 398.55/291.54 398.55/291.54 f_0(z) -{ 1 }-> 0 :|: z >= 0 398.55/291.54 f_1(z) -{ 1 + 2*z }-> s :|: s >= 0, s <= 0, z >= 0 398.55/291.54 f_2(z) -{ 1 + 2*z + 2*z^2 }-> s1 :|: s1 >= 0, s1 <= 0, z >= 0 398.55/291.54 f_3(z) -{ 1 + 2*z + 2*z^2 + 2*z^3 }-> s4 :|: s4 >= 0, s4 <= 0, z >= 0 398.55/291.54 f_4(z) -{ 1 }-> g_4(z, z) :|: z >= 0 398.55/291.54 f_5(z) -{ 1 }-> g_5(z, z) :|: z >= 0 398.55/291.54 g_1(z, z') -{ 2*z }-> 1 + 0 + s' :|: s' >= 0, s' <= 0, z - 1 >= 0, z' >= 0 398.55/291.54 g_2(z, z') -{ 2*z + 2*z*z' }-> 1 + s'' + s2 :|: s2 >= 0, s2 <= 0, s'' >= 0, s'' <= 0, z - 1 >= 0, z' >= 0 398.55/291.54 g_3(z, z') -{ 2*z + 2*z*z' + 2*z*z'^2 }-> 1 + s3 + s5 :|: s5 >= 0, s5 <= 0, s3 >= 0, s3 <= 0, z - 1 >= 0, z' >= 0 398.55/291.54 g_4(z, z') -{ 2 + 2*z' + 2*z'^2 + 2*z'^3 }-> 1 + s6 + g_4(z - 1, z') :|: s6 >= 0, s6 <= 0, z - 1 >= 0, z' >= 0 398.55/291.54 g_5(z, z') -{ 1 }-> 1 + f_4(z') + g_5(z - 1, z') :|: z - 1 >= 0, z' >= 0 398.55/291.54 398.55/291.54 Function symbols to be analyzed: {g_4}, {f_4}, {g_5}, {f_5} 398.55/291.54 Previous analysis results are: 398.55/291.54 f_0: runtime: O(1) [1], size: O(1) [0] 398.55/291.54 g_1: runtime: O(n^1) [2*z], size: O(1) [0] 398.55/291.54 f_1: runtime: O(n^1) [1 + 2*z], size: O(1) [0] 398.55/291.54 g_2: runtime: O(n^2) [2*z + 2*z*z'], size: O(1) [0] 398.55/291.54 f_2: runtime: O(n^2) [1 + 2*z + 2*z^2], size: O(1) [0] 398.55/291.54 g_3: runtime: O(n^3) [2*z + 2*z*z' + 2*z*z'^2], size: O(1) [0] 398.55/291.54 f_3: runtime: O(n^3) [1 + 2*z + 2*z^2 + 2*z^3], size: O(1) [0] 398.55/291.54 398.55/291.54 ---------------------------------------- 398.55/291.54 398.55/291.54 (61) IntTrsBoundProof (UPPER BOUND(ID)) 398.55/291.54 398.55/291.54 Computed SIZE bound using CoFloCo for: g_4 398.55/291.54 after applying outer abstraction to obtain an ITS, 398.55/291.54 resulting in: O(1) with polynomial bound: 0 398.55/291.54 398.55/291.54 ---------------------------------------- 398.55/291.54 398.55/291.54 (62) 398.55/291.54 Obligation: 398.55/291.54 Complexity RNTS consisting of the following rules: 398.55/291.54 398.55/291.54 f_0(z) -{ 1 }-> 0 :|: z >= 0 398.55/291.54 f_1(z) -{ 1 + 2*z }-> s :|: s >= 0, s <= 0, z >= 0 398.55/291.54 f_2(z) -{ 1 + 2*z + 2*z^2 }-> s1 :|: s1 >= 0, s1 <= 0, z >= 0 398.55/291.54 f_3(z) -{ 1 + 2*z + 2*z^2 + 2*z^3 }-> s4 :|: s4 >= 0, s4 <= 0, z >= 0 398.55/291.54 f_4(z) -{ 1 }-> g_4(z, z) :|: z >= 0 398.55/291.54 f_5(z) -{ 1 }-> g_5(z, z) :|: z >= 0 398.55/291.54 g_1(z, z') -{ 2*z }-> 1 + 0 + s' :|: s' >= 0, s' <= 0, z - 1 >= 0, z' >= 0 398.55/291.54 g_2(z, z') -{ 2*z + 2*z*z' }-> 1 + s'' + s2 :|: s2 >= 0, s2 <= 0, s'' >= 0, s'' <= 0, z - 1 >= 0, z' >= 0 398.55/291.54 g_3(z, z') -{ 2*z + 2*z*z' + 2*z*z'^2 }-> 1 + s3 + s5 :|: s5 >= 0, s5 <= 0, s3 >= 0, s3 <= 0, z - 1 >= 0, z' >= 0 398.55/291.54 g_4(z, z') -{ 2 + 2*z' + 2*z'^2 + 2*z'^3 }-> 1 + s6 + g_4(z - 1, z') :|: s6 >= 0, s6 <= 0, z - 1 >= 0, z' >= 0 398.55/291.54 g_5(z, z') -{ 1 }-> 1 + f_4(z') + g_5(z - 1, z') :|: z - 1 >= 0, z' >= 0 398.55/291.54 398.55/291.54 Function symbols to be analyzed: {g_4}, {f_4}, {g_5}, {f_5} 398.55/291.54 Previous analysis results are: 398.55/291.54 f_0: runtime: O(1) [1], size: O(1) [0] 398.55/291.54 g_1: runtime: O(n^1) [2*z], size: O(1) [0] 398.55/291.54 f_1: runtime: O(n^1) [1 + 2*z], size: O(1) [0] 398.55/291.54 g_2: runtime: O(n^2) [2*z + 2*z*z'], size: O(1) [0] 398.55/291.54 f_2: runtime: O(n^2) [1 + 2*z + 2*z^2], size: O(1) [0] 398.55/291.54 g_3: runtime: O(n^3) [2*z + 2*z*z' + 2*z*z'^2], size: O(1) [0] 398.55/291.54 f_3: runtime: O(n^3) [1 + 2*z + 2*z^2 + 2*z^3], size: O(1) [0] 398.55/291.54 g_4: runtime: ?, size: O(1) [0] 398.55/291.54 398.55/291.54 ---------------------------------------- 398.55/291.54 398.55/291.54 (63) IntTrsBoundProof (UPPER BOUND(ID)) 398.55/291.54 398.55/291.54 Computed RUNTIME bound using KoAT for: g_4 398.55/291.54 after applying outer abstraction to obtain an ITS, 398.55/291.54 resulting in: O(n^4) with polynomial bound: 2*z + 2*z*z' + 2*z*z'^2 + 2*z*z'^3 398.55/291.54 398.55/291.54 ---------------------------------------- 398.55/291.54 398.55/291.54 (64) 398.55/291.54 Obligation: 398.55/291.54 Complexity RNTS consisting of the following rules: 398.55/291.54 398.55/291.54 f_0(z) -{ 1 }-> 0 :|: z >= 0 398.55/291.54 f_1(z) -{ 1 + 2*z }-> s :|: s >= 0, s <= 0, z >= 0 398.55/291.54 f_2(z) -{ 1 + 2*z + 2*z^2 }-> s1 :|: s1 >= 0, s1 <= 0, z >= 0 398.55/291.54 f_3(z) -{ 1 + 2*z + 2*z^2 + 2*z^3 }-> s4 :|: s4 >= 0, s4 <= 0, z >= 0 398.55/291.54 f_4(z) -{ 1 }-> g_4(z, z) :|: z >= 0 398.55/291.54 f_5(z) -{ 1 }-> g_5(z, z) :|: z >= 0 398.55/291.54 g_1(z, z') -{ 2*z }-> 1 + 0 + s' :|: s' >= 0, s' <= 0, z - 1 >= 0, z' >= 0 398.55/291.54 g_2(z, z') -{ 2*z + 2*z*z' }-> 1 + s'' + s2 :|: s2 >= 0, s2 <= 0, s'' >= 0, s'' <= 0, z - 1 >= 0, z' >= 0 398.55/291.54 g_3(z, z') -{ 2*z + 2*z*z' + 2*z*z'^2 }-> 1 + s3 + s5 :|: s5 >= 0, s5 <= 0, s3 >= 0, s3 <= 0, z - 1 >= 0, z' >= 0 398.55/291.54 g_4(z, z') -{ 2 + 2*z' + 2*z'^2 + 2*z'^3 }-> 1 + s6 + g_4(z - 1, z') :|: s6 >= 0, s6 <= 0, z - 1 >= 0, z' >= 0 398.55/291.54 g_5(z, z') -{ 1 }-> 1 + f_4(z') + g_5(z - 1, z') :|: z - 1 >= 0, z' >= 0 398.55/291.54 398.55/291.54 Function symbols to be analyzed: {f_4}, {g_5}, {f_5} 398.55/291.54 Previous analysis results are: 398.55/291.54 f_0: runtime: O(1) [1], size: O(1) [0] 398.55/291.54 g_1: runtime: O(n^1) [2*z], size: O(1) [0] 398.55/291.54 f_1: runtime: O(n^1) [1 + 2*z], size: O(1) [0] 398.55/291.54 g_2: runtime: O(n^2) [2*z + 2*z*z'], size: O(1) [0] 398.55/291.54 f_2: runtime: O(n^2) [1 + 2*z + 2*z^2], size: O(1) [0] 398.55/291.54 g_3: runtime: O(n^3) [2*z + 2*z*z' + 2*z*z'^2], size: O(1) [0] 398.55/291.54 f_3: runtime: O(n^3) [1 + 2*z + 2*z^2 + 2*z^3], size: O(1) [0] 398.55/291.54 g_4: runtime: O(n^4) [2*z + 2*z*z' + 2*z*z'^2 + 2*z*z'^3], size: O(1) [0] 398.55/291.54 398.55/291.54 ---------------------------------------- 398.55/291.54 398.55/291.54 (65) ResultPropagationProof (UPPER BOUND(ID)) 398.55/291.54 Applied inner abstraction using the recently inferred runtime/size bounds where possible. 398.55/291.54 ---------------------------------------- 398.55/291.54 398.55/291.54 (66) 398.55/291.54 Obligation: 398.55/291.54 Complexity RNTS consisting of the following rules: 398.55/291.54 398.55/291.54 f_0(z) -{ 1 }-> 0 :|: z >= 0 398.55/291.54 f_1(z) -{ 1 + 2*z }-> s :|: s >= 0, s <= 0, z >= 0 398.55/291.54 f_2(z) -{ 1 + 2*z + 2*z^2 }-> s1 :|: s1 >= 0, s1 <= 0, z >= 0 398.55/291.54 f_3(z) -{ 1 + 2*z + 2*z^2 + 2*z^3 }-> s4 :|: s4 >= 0, s4 <= 0, z >= 0 398.55/291.54 f_4(z) -{ 1 + 2*z + 2*z^2 + 2*z^3 + 2*z^4 }-> s7 :|: s7 >= 0, s7 <= 0, z >= 0 398.55/291.54 f_5(z) -{ 1 }-> g_5(z, z) :|: z >= 0 398.55/291.54 g_1(z, z') -{ 2*z }-> 1 + 0 + s' :|: s' >= 0, s' <= 0, z - 1 >= 0, z' >= 0 398.55/291.54 g_2(z, z') -{ 2*z + 2*z*z' }-> 1 + s'' + s2 :|: s2 >= 0, s2 <= 0, s'' >= 0, s'' <= 0, z - 1 >= 0, z' >= 0 398.55/291.54 g_3(z, z') -{ 2*z + 2*z*z' + 2*z*z'^2 }-> 1 + s3 + s5 :|: s5 >= 0, s5 <= 0, s3 >= 0, s3 <= 0, z - 1 >= 0, z' >= 0 398.55/291.54 g_4(z, z') -{ 2*z + 2*z*z' + 2*z*z'^2 + 2*z*z'^3 }-> 1 + s6 + s8 :|: s8 >= 0, s8 <= 0, s6 >= 0, s6 <= 0, z - 1 >= 0, z' >= 0 398.55/291.54 g_5(z, z') -{ 1 }-> 1 + f_4(z') + g_5(z - 1, z') :|: z - 1 >= 0, z' >= 0 398.55/291.54 398.55/291.54 Function symbols to be analyzed: {f_4}, {g_5}, {f_5} 398.55/291.54 Previous analysis results are: 398.55/291.54 f_0: runtime: O(1) [1], size: O(1) [0] 398.55/291.54 g_1: runtime: O(n^1) [2*z], size: O(1) [0] 398.55/291.54 f_1: runtime: O(n^1) [1 + 2*z], size: O(1) [0] 398.55/291.54 g_2: runtime: O(n^2) [2*z + 2*z*z'], size: O(1) [0] 398.55/291.54 f_2: runtime: O(n^2) [1 + 2*z + 2*z^2], size: O(1) [0] 398.55/291.54 g_3: runtime: O(n^3) [2*z + 2*z*z' + 2*z*z'^2], size: O(1) [0] 398.55/291.54 f_3: runtime: O(n^3) [1 + 2*z + 2*z^2 + 2*z^3], size: O(1) [0] 398.55/291.54 g_4: runtime: O(n^4) [2*z + 2*z*z' + 2*z*z'^2 + 2*z*z'^3], size: O(1) [0] 398.55/291.54 398.55/291.54 ---------------------------------------- 398.55/291.54 398.55/291.54 (67) IntTrsBoundProof (UPPER BOUND(ID)) 398.55/291.54 398.55/291.54 Computed SIZE bound using CoFloCo for: f_4 398.55/291.54 after applying outer abstraction to obtain an ITS, 398.55/291.54 resulting in: O(1) with polynomial bound: 0 398.55/291.54 398.55/291.54 ---------------------------------------- 398.55/291.54 398.55/291.54 (68) 398.55/291.54 Obligation: 398.55/291.54 Complexity RNTS consisting of the following rules: 398.55/291.54 398.55/291.54 f_0(z) -{ 1 }-> 0 :|: z >= 0 398.55/291.54 f_1(z) -{ 1 + 2*z }-> s :|: s >= 0, s <= 0, z >= 0 398.55/291.54 f_2(z) -{ 1 + 2*z + 2*z^2 }-> s1 :|: s1 >= 0, s1 <= 0, z >= 0 398.55/291.54 f_3(z) -{ 1 + 2*z + 2*z^2 + 2*z^3 }-> s4 :|: s4 >= 0, s4 <= 0, z >= 0 398.55/291.54 f_4(z) -{ 1 + 2*z + 2*z^2 + 2*z^3 + 2*z^4 }-> s7 :|: s7 >= 0, s7 <= 0, z >= 0 398.55/291.54 f_5(z) -{ 1 }-> g_5(z, z) :|: z >= 0 398.55/291.54 g_1(z, z') -{ 2*z }-> 1 + 0 + s' :|: s' >= 0, s' <= 0, z - 1 >= 0, z' >= 0 398.55/291.54 g_2(z, z') -{ 2*z + 2*z*z' }-> 1 + s'' + s2 :|: s2 >= 0, s2 <= 0, s'' >= 0, s'' <= 0, z - 1 >= 0, z' >= 0 398.55/291.54 g_3(z, z') -{ 2*z + 2*z*z' + 2*z*z'^2 }-> 1 + s3 + s5 :|: s5 >= 0, s5 <= 0, s3 >= 0, s3 <= 0, z - 1 >= 0, z' >= 0 398.55/291.54 g_4(z, z') -{ 2*z + 2*z*z' + 2*z*z'^2 + 2*z*z'^3 }-> 1 + s6 + s8 :|: s8 >= 0, s8 <= 0, s6 >= 0, s6 <= 0, z - 1 >= 0, z' >= 0 398.55/291.54 g_5(z, z') -{ 1 }-> 1 + f_4(z') + g_5(z - 1, z') :|: z - 1 >= 0, z' >= 0 398.55/291.54 398.55/291.54 Function symbols to be analyzed: {f_4}, {g_5}, {f_5} 398.55/291.54 Previous analysis results are: 398.55/291.54 f_0: runtime: O(1) [1], size: O(1) [0] 398.55/291.54 g_1: runtime: O(n^1) [2*z], size: O(1) [0] 398.55/291.54 f_1: runtime: O(n^1) [1 + 2*z], size: O(1) [0] 398.55/291.54 g_2: runtime: O(n^2) [2*z + 2*z*z'], size: O(1) [0] 398.55/291.54 f_2: runtime: O(n^2) [1 + 2*z + 2*z^2], size: O(1) [0] 398.55/291.54 g_3: runtime: O(n^3) [2*z + 2*z*z' + 2*z*z'^2], size: O(1) [0] 398.55/291.54 f_3: runtime: O(n^3) [1 + 2*z + 2*z^2 + 2*z^3], size: O(1) [0] 398.55/291.54 g_4: runtime: O(n^4) [2*z + 2*z*z' + 2*z*z'^2 + 2*z*z'^3], size: O(1) [0] 398.55/291.54 f_4: runtime: ?, size: O(1) [0] 398.55/291.54 398.55/291.54 ---------------------------------------- 398.55/291.54 398.55/291.54 (69) IntTrsBoundProof (UPPER BOUND(ID)) 398.55/291.54 398.55/291.54 Computed RUNTIME bound using KoAT for: f_4 398.55/291.54 after applying outer abstraction to obtain an ITS, 398.55/291.54 resulting in: O(n^4) with polynomial bound: 1 + 2*z + 2*z^2 + 2*z^3 + 2*z^4 398.55/291.54 398.55/291.54 ---------------------------------------- 398.55/291.54 398.55/291.54 (70) 398.55/291.54 Obligation: 398.55/291.54 Complexity RNTS consisting of the following rules: 398.55/291.54 398.55/291.54 f_0(z) -{ 1 }-> 0 :|: z >= 0 398.55/291.54 f_1(z) -{ 1 + 2*z }-> s :|: s >= 0, s <= 0, z >= 0 398.55/291.54 f_2(z) -{ 1 + 2*z + 2*z^2 }-> s1 :|: s1 >= 0, s1 <= 0, z >= 0 398.55/291.54 f_3(z) -{ 1 + 2*z + 2*z^2 + 2*z^3 }-> s4 :|: s4 >= 0, s4 <= 0, z >= 0 398.55/291.54 f_4(z) -{ 1 + 2*z + 2*z^2 + 2*z^3 + 2*z^4 }-> s7 :|: s7 >= 0, s7 <= 0, z >= 0 398.55/291.54 f_5(z) -{ 1 }-> g_5(z, z) :|: z >= 0 398.55/291.54 g_1(z, z') -{ 2*z }-> 1 + 0 + s' :|: s' >= 0, s' <= 0, z - 1 >= 0, z' >= 0 398.55/291.54 g_2(z, z') -{ 2*z + 2*z*z' }-> 1 + s'' + s2 :|: s2 >= 0, s2 <= 0, s'' >= 0, s'' <= 0, z - 1 >= 0, z' >= 0 398.55/291.54 g_3(z, z') -{ 2*z + 2*z*z' + 2*z*z'^2 }-> 1 + s3 + s5 :|: s5 >= 0, s5 <= 0, s3 >= 0, s3 <= 0, z - 1 >= 0, z' >= 0 398.55/291.54 g_4(z, z') -{ 2*z + 2*z*z' + 2*z*z'^2 + 2*z*z'^3 }-> 1 + s6 + s8 :|: s8 >= 0, s8 <= 0, s6 >= 0, s6 <= 0, z - 1 >= 0, z' >= 0 398.55/291.54 g_5(z, z') -{ 1 }-> 1 + f_4(z') + g_5(z - 1, z') :|: z - 1 >= 0, z' >= 0 398.55/291.54 398.55/291.54 Function symbols to be analyzed: {g_5}, {f_5} 398.55/291.54 Previous analysis results are: 398.55/291.54 f_0: runtime: O(1) [1], size: O(1) [0] 398.55/291.54 g_1: runtime: O(n^1) [2*z], size: O(1) [0] 398.55/291.54 f_1: runtime: O(n^1) [1 + 2*z], size: O(1) [0] 398.55/291.54 g_2: runtime: O(n^2) [2*z + 2*z*z'], size: O(1) [0] 398.55/291.54 f_2: runtime: O(n^2) [1 + 2*z + 2*z^2], size: O(1) [0] 398.55/291.54 g_3: runtime: O(n^3) [2*z + 2*z*z' + 2*z*z'^2], size: O(1) [0] 398.55/291.54 f_3: runtime: O(n^3) [1 + 2*z + 2*z^2 + 2*z^3], size: O(1) [0] 398.55/291.54 g_4: runtime: O(n^4) [2*z + 2*z*z' + 2*z*z'^2 + 2*z*z'^3], size: O(1) [0] 398.55/291.54 f_4: runtime: O(n^4) [1 + 2*z + 2*z^2 + 2*z^3 + 2*z^4], size: O(1) [0] 398.55/291.54 398.55/291.54 ---------------------------------------- 398.55/291.54 398.55/291.54 (71) ResultPropagationProof (UPPER BOUND(ID)) 398.55/291.54 Applied inner abstraction using the recently inferred runtime/size bounds where possible. 398.55/291.54 ---------------------------------------- 398.55/291.54 398.55/291.54 (72) 398.55/291.54 Obligation: 398.55/291.54 Complexity RNTS consisting of the following rules: 398.55/291.54 398.55/291.54 f_0(z) -{ 1 }-> 0 :|: z >= 0 398.55/291.54 f_1(z) -{ 1 + 2*z }-> s :|: s >= 0, s <= 0, z >= 0 398.55/291.54 f_2(z) -{ 1 + 2*z + 2*z^2 }-> s1 :|: s1 >= 0, s1 <= 0, z >= 0 398.55/291.54 f_3(z) -{ 1 + 2*z + 2*z^2 + 2*z^3 }-> s4 :|: s4 >= 0, s4 <= 0, z >= 0 398.55/291.54 f_4(z) -{ 1 + 2*z + 2*z^2 + 2*z^3 + 2*z^4 }-> s7 :|: s7 >= 0, s7 <= 0, z >= 0 398.55/291.54 f_5(z) -{ 1 }-> g_5(z, z) :|: z >= 0 398.55/291.54 g_1(z, z') -{ 2*z }-> 1 + 0 + s' :|: s' >= 0, s' <= 0, z - 1 >= 0, z' >= 0 398.55/291.54 g_2(z, z') -{ 2*z + 2*z*z' }-> 1 + s'' + s2 :|: s2 >= 0, s2 <= 0, s'' >= 0, s'' <= 0, z - 1 >= 0, z' >= 0 398.55/291.54 g_3(z, z') -{ 2*z + 2*z*z' + 2*z*z'^2 }-> 1 + s3 + s5 :|: s5 >= 0, s5 <= 0, s3 >= 0, s3 <= 0, z - 1 >= 0, z' >= 0 398.55/291.54 g_4(z, z') -{ 2*z + 2*z*z' + 2*z*z'^2 + 2*z*z'^3 }-> 1 + s6 + s8 :|: s8 >= 0, s8 <= 0, s6 >= 0, s6 <= 0, z - 1 >= 0, z' >= 0 398.55/291.54 g_5(z, z') -{ 2 + 2*z' + 2*z'^2 + 2*z'^3 + 2*z'^4 }-> 1 + s9 + g_5(z - 1, z') :|: s9 >= 0, s9 <= 0, z - 1 >= 0, z' >= 0 398.55/291.54 398.55/291.54 Function symbols to be analyzed: {g_5}, {f_5} 398.55/291.54 Previous analysis results are: 398.55/291.54 f_0: runtime: O(1) [1], size: O(1) [0] 398.55/291.54 g_1: runtime: O(n^1) [2*z], size: O(1) [0] 398.55/291.54 f_1: runtime: O(n^1) [1 + 2*z], size: O(1) [0] 398.55/291.54 g_2: runtime: O(n^2) [2*z + 2*z*z'], size: O(1) [0] 398.55/291.54 f_2: runtime: O(n^2) [1 + 2*z + 2*z^2], size: O(1) [0] 398.55/291.54 g_3: runtime: O(n^3) [2*z + 2*z*z' + 2*z*z'^2], size: O(1) [0] 398.55/291.54 f_3: runtime: O(n^3) [1 + 2*z + 2*z^2 + 2*z^3], size: O(1) [0] 398.55/291.54 g_4: runtime: O(n^4) [2*z + 2*z*z' + 2*z*z'^2 + 2*z*z'^3], size: O(1) [0] 398.55/291.54 f_4: runtime: O(n^4) [1 + 2*z + 2*z^2 + 2*z^3 + 2*z^4], size: O(1) [0] 398.55/291.54 398.55/291.54 ---------------------------------------- 398.55/291.54 398.55/291.54 (73) IntTrsBoundProof (UPPER BOUND(ID)) 398.55/291.54 398.55/291.54 Computed SIZE bound using CoFloCo for: g_5 398.55/291.54 after applying outer abstraction to obtain an ITS, 398.55/291.54 resulting in: O(1) with polynomial bound: 0 398.55/291.54 398.55/291.54 ---------------------------------------- 398.55/291.54 398.55/291.54 (74) 398.55/291.54 Obligation: 398.55/291.54 Complexity RNTS consisting of the following rules: 398.55/291.54 398.55/291.54 f_0(z) -{ 1 }-> 0 :|: z >= 0 398.55/291.54 f_1(z) -{ 1 + 2*z }-> s :|: s >= 0, s <= 0, z >= 0 398.55/291.54 f_2(z) -{ 1 + 2*z + 2*z^2 }-> s1 :|: s1 >= 0, s1 <= 0, z >= 0 398.55/291.54 f_3(z) -{ 1 + 2*z + 2*z^2 + 2*z^3 }-> s4 :|: s4 >= 0, s4 <= 0, z >= 0 398.55/291.54 f_4(z) -{ 1 + 2*z + 2*z^2 + 2*z^3 + 2*z^4 }-> s7 :|: s7 >= 0, s7 <= 0, z >= 0 398.55/291.54 f_5(z) -{ 1 }-> g_5(z, z) :|: z >= 0 398.55/291.54 g_1(z, z') -{ 2*z }-> 1 + 0 + s' :|: s' >= 0, s' <= 0, z - 1 >= 0, z' >= 0 398.55/291.54 g_2(z, z') -{ 2*z + 2*z*z' }-> 1 + s'' + s2 :|: s2 >= 0, s2 <= 0, s'' >= 0, s'' <= 0, z - 1 >= 0, z' >= 0 398.55/291.54 g_3(z, z') -{ 2*z + 2*z*z' + 2*z*z'^2 }-> 1 + s3 + s5 :|: s5 >= 0, s5 <= 0, s3 >= 0, s3 <= 0, z - 1 >= 0, z' >= 0 398.55/291.54 g_4(z, z') -{ 2*z + 2*z*z' + 2*z*z'^2 + 2*z*z'^3 }-> 1 + s6 + s8 :|: s8 >= 0, s8 <= 0, s6 >= 0, s6 <= 0, z - 1 >= 0, z' >= 0 398.55/291.54 g_5(z, z') -{ 2 + 2*z' + 2*z'^2 + 2*z'^3 + 2*z'^4 }-> 1 + s9 + g_5(z - 1, z') :|: s9 >= 0, s9 <= 0, z - 1 >= 0, z' >= 0 398.55/291.54 398.55/291.54 Function symbols to be analyzed: {g_5}, {f_5} 398.55/291.54 Previous analysis results are: 398.55/291.54 f_0: runtime: O(1) [1], size: O(1) [0] 398.55/291.54 g_1: runtime: O(n^1) [2*z], size: O(1) [0] 398.55/291.54 f_1: runtime: O(n^1) [1 + 2*z], size: O(1) [0] 398.55/291.54 g_2: runtime: O(n^2) [2*z + 2*z*z'], size: O(1) [0] 398.55/291.54 f_2: runtime: O(n^2) [1 + 2*z + 2*z^2], size: O(1) [0] 398.55/291.54 g_3: runtime: O(n^3) [2*z + 2*z*z' + 2*z*z'^2], size: O(1) [0] 398.55/291.54 f_3: runtime: O(n^3) [1 + 2*z + 2*z^2 + 2*z^3], size: O(1) [0] 398.55/291.54 g_4: runtime: O(n^4) [2*z + 2*z*z' + 2*z*z'^2 + 2*z*z'^3], size: O(1) [0] 398.55/291.54 f_4: runtime: O(n^4) [1 + 2*z + 2*z^2 + 2*z^3 + 2*z^4], size: O(1) [0] 398.55/291.54 g_5: runtime: ?, size: O(1) [0] 398.55/291.54 398.55/291.54 ---------------------------------------- 398.55/291.54 398.55/291.54 (75) IntTrsBoundProof (UPPER BOUND(ID)) 398.55/291.54 398.55/291.54 Computed RUNTIME bound using KoAT for: g_5 398.55/291.54 after applying outer abstraction to obtain an ITS, 398.55/291.54 resulting in: O(n^5) with polynomial bound: 2*z + 2*z*z' + 2*z*z'^2 + 2*z*z'^3 + 2*z*z'^4 398.55/291.54 398.55/291.54 ---------------------------------------- 398.55/291.54 398.55/291.54 (76) 398.55/291.54 Obligation: 398.55/291.54 Complexity RNTS consisting of the following rules: 398.55/291.54 398.55/291.54 f_0(z) -{ 1 }-> 0 :|: z >= 0 398.55/291.54 f_1(z) -{ 1 + 2*z }-> s :|: s >= 0, s <= 0, z >= 0 398.55/291.54 f_2(z) -{ 1 + 2*z + 2*z^2 }-> s1 :|: s1 >= 0, s1 <= 0, z >= 0 398.55/291.54 f_3(z) -{ 1 + 2*z + 2*z^2 + 2*z^3 }-> s4 :|: s4 >= 0, s4 <= 0, z >= 0 398.55/291.54 f_4(z) -{ 1 + 2*z + 2*z^2 + 2*z^3 + 2*z^4 }-> s7 :|: s7 >= 0, s7 <= 0, z >= 0 398.55/291.54 f_5(z) -{ 1 }-> g_5(z, z) :|: z >= 0 398.55/291.54 g_1(z, z') -{ 2*z }-> 1 + 0 + s' :|: s' >= 0, s' <= 0, z - 1 >= 0, z' >= 0 398.55/291.54 g_2(z, z') -{ 2*z + 2*z*z' }-> 1 + s'' + s2 :|: s2 >= 0, s2 <= 0, s'' >= 0, s'' <= 0, z - 1 >= 0, z' >= 0 398.55/291.54 g_3(z, z') -{ 2*z + 2*z*z' + 2*z*z'^2 }-> 1 + s3 + s5 :|: s5 >= 0, s5 <= 0, s3 >= 0, s3 <= 0, z - 1 >= 0, z' >= 0 398.55/291.54 g_4(z, z') -{ 2*z + 2*z*z' + 2*z*z'^2 + 2*z*z'^3 }-> 1 + s6 + s8 :|: s8 >= 0, s8 <= 0, s6 >= 0, s6 <= 0, z - 1 >= 0, z' >= 0 398.55/291.54 g_5(z, z') -{ 2 + 2*z' + 2*z'^2 + 2*z'^3 + 2*z'^4 }-> 1 + s9 + g_5(z - 1, z') :|: s9 >= 0, s9 <= 0, z - 1 >= 0, z' >= 0 398.55/291.54 398.55/291.54 Function symbols to be analyzed: {f_5} 398.55/291.54 Previous analysis results are: 398.55/291.54 f_0: runtime: O(1) [1], size: O(1) [0] 398.55/291.54 g_1: runtime: O(n^1) [2*z], size: O(1) [0] 398.55/291.54 f_1: runtime: O(n^1) [1 + 2*z], size: O(1) [0] 398.55/291.54 g_2: runtime: O(n^2) [2*z + 2*z*z'], size: O(1) [0] 398.55/291.54 f_2: runtime: O(n^2) [1 + 2*z + 2*z^2], size: O(1) [0] 398.55/291.54 g_3: runtime: O(n^3) [2*z + 2*z*z' + 2*z*z'^2], size: O(1) [0] 398.55/291.54 f_3: runtime: O(n^3) [1 + 2*z + 2*z^2 + 2*z^3], size: O(1) [0] 398.55/291.54 g_4: runtime: O(n^4) [2*z + 2*z*z' + 2*z*z'^2 + 2*z*z'^3], size: O(1) [0] 398.55/291.54 f_4: runtime: O(n^4) [1 + 2*z + 2*z^2 + 2*z^3 + 2*z^4], size: O(1) [0] 398.55/291.54 g_5: runtime: O(n^5) [2*z + 2*z*z' + 2*z*z'^2 + 2*z*z'^3 + 2*z*z'^4], size: O(1) [0] 398.55/291.54 398.55/291.54 ---------------------------------------- 398.55/291.54 398.55/291.54 (77) ResultPropagationProof (UPPER BOUND(ID)) 398.55/291.54 Applied inner abstraction using the recently inferred runtime/size bounds where possible. 398.55/291.54 ---------------------------------------- 398.55/291.54 398.55/291.54 (78) 398.55/291.54 Obligation: 398.55/291.54 Complexity RNTS consisting of the following rules: 398.55/291.54 398.55/291.54 f_0(z) -{ 1 }-> 0 :|: z >= 0 398.55/291.54 f_1(z) -{ 1 + 2*z }-> s :|: s >= 0, s <= 0, z >= 0 398.55/291.54 f_2(z) -{ 1 + 2*z + 2*z^2 }-> s1 :|: s1 >= 0, s1 <= 0, z >= 0 398.55/291.54 f_3(z) -{ 1 + 2*z + 2*z^2 + 2*z^3 }-> s4 :|: s4 >= 0, s4 <= 0, z >= 0 398.55/291.54 f_4(z) -{ 1 + 2*z + 2*z^2 + 2*z^3 + 2*z^4 }-> s7 :|: s7 >= 0, s7 <= 0, z >= 0 398.55/291.54 f_5(z) -{ 1 + 2*z + 2*z^2 + 2*z^3 + 2*z^4 + 2*z^5 }-> s10 :|: s10 >= 0, s10 <= 0, z >= 0 398.55/291.54 g_1(z, z') -{ 2*z }-> 1 + 0 + s' :|: s' >= 0, s' <= 0, z - 1 >= 0, z' >= 0 398.55/291.54 g_2(z, z') -{ 2*z + 2*z*z' }-> 1 + s'' + s2 :|: s2 >= 0, s2 <= 0, s'' >= 0, s'' <= 0, z - 1 >= 0, z' >= 0 398.55/291.54 g_3(z, z') -{ 2*z + 2*z*z' + 2*z*z'^2 }-> 1 + s3 + s5 :|: s5 >= 0, s5 <= 0, s3 >= 0, s3 <= 0, z - 1 >= 0, z' >= 0 398.55/291.54 g_4(z, z') -{ 2*z + 2*z*z' + 2*z*z'^2 + 2*z*z'^3 }-> 1 + s6 + s8 :|: s8 >= 0, s8 <= 0, s6 >= 0, s6 <= 0, z - 1 >= 0, z' >= 0 398.55/291.54 g_5(z, z') -{ 2*z + 2*z*z' + 2*z*z'^2 + 2*z*z'^3 + 2*z*z'^4 }-> 1 + s9 + s11 :|: s11 >= 0, s11 <= 0, s9 >= 0, s9 <= 0, z - 1 >= 0, z' >= 0 398.55/291.54 398.55/291.54 Function symbols to be analyzed: {f_5} 398.55/291.54 Previous analysis results are: 398.55/291.54 f_0: runtime: O(1) [1], size: O(1) [0] 398.55/291.54 g_1: runtime: O(n^1) [2*z], size: O(1) [0] 398.55/291.54 f_1: runtime: O(n^1) [1 + 2*z], size: O(1) [0] 398.55/291.54 g_2: runtime: O(n^2) [2*z + 2*z*z'], size: O(1) [0] 398.55/291.54 f_2: runtime: O(n^2) [1 + 2*z + 2*z^2], size: O(1) [0] 398.55/291.54 g_3: runtime: O(n^3) [2*z + 2*z*z' + 2*z*z'^2], size: O(1) [0] 398.55/291.54 f_3: runtime: O(n^3) [1 + 2*z + 2*z^2 + 2*z^3], size: O(1) [0] 398.55/291.54 g_4: runtime: O(n^4) [2*z + 2*z*z' + 2*z*z'^2 + 2*z*z'^3], size: O(1) [0] 398.55/291.54 f_4: runtime: O(n^4) [1 + 2*z + 2*z^2 + 2*z^3 + 2*z^4], size: O(1) [0] 398.55/291.54 g_5: runtime: O(n^5) [2*z + 2*z*z' + 2*z*z'^2 + 2*z*z'^3 + 2*z*z'^4], size: O(1) [0] 398.55/291.54 398.55/291.54 ---------------------------------------- 398.55/291.54 398.55/291.54 (79) IntTrsBoundProof (UPPER BOUND(ID)) 398.55/291.54 398.55/291.54 Computed SIZE bound using CoFloCo for: f_5 398.55/291.54 after applying outer abstraction to obtain an ITS, 398.55/291.54 resulting in: O(1) with polynomial bound: 0 398.55/291.54 398.55/291.54 ---------------------------------------- 398.55/291.54 398.55/291.54 (80) 398.55/291.54 Obligation: 398.55/291.54 Complexity RNTS consisting of the following rules: 398.55/291.54 398.55/291.54 f_0(z) -{ 1 }-> 0 :|: z >= 0 398.55/291.54 f_1(z) -{ 1 + 2*z }-> s :|: s >= 0, s <= 0, z >= 0 398.55/291.54 f_2(z) -{ 1 + 2*z + 2*z^2 }-> s1 :|: s1 >= 0, s1 <= 0, z >= 0 398.55/291.54 f_3(z) -{ 1 + 2*z + 2*z^2 + 2*z^3 }-> s4 :|: s4 >= 0, s4 <= 0, z >= 0 398.55/291.54 f_4(z) -{ 1 + 2*z + 2*z^2 + 2*z^3 + 2*z^4 }-> s7 :|: s7 >= 0, s7 <= 0, z >= 0 398.55/291.54 f_5(z) -{ 1 + 2*z + 2*z^2 + 2*z^3 + 2*z^4 + 2*z^5 }-> s10 :|: s10 >= 0, s10 <= 0, z >= 0 398.55/291.54 g_1(z, z') -{ 2*z }-> 1 + 0 + s' :|: s' >= 0, s' <= 0, z - 1 >= 0, z' >= 0 398.55/291.54 g_2(z, z') -{ 2*z + 2*z*z' }-> 1 + s'' + s2 :|: s2 >= 0, s2 <= 0, s'' >= 0, s'' <= 0, z - 1 >= 0, z' >= 0 398.55/291.54 g_3(z, z') -{ 2*z + 2*z*z' + 2*z*z'^2 }-> 1 + s3 + s5 :|: s5 >= 0, s5 <= 0, s3 >= 0, s3 <= 0, z - 1 >= 0, z' >= 0 398.55/291.54 g_4(z, z') -{ 2*z + 2*z*z' + 2*z*z'^2 + 2*z*z'^3 }-> 1 + s6 + s8 :|: s8 >= 0, s8 <= 0, s6 >= 0, s6 <= 0, z - 1 >= 0, z' >= 0 398.55/291.54 g_5(z, z') -{ 2*z + 2*z*z' + 2*z*z'^2 + 2*z*z'^3 + 2*z*z'^4 }-> 1 + s9 + s11 :|: s11 >= 0, s11 <= 0, s9 >= 0, s9 <= 0, z - 1 >= 0, z' >= 0 398.55/291.54 398.55/291.54 Function symbols to be analyzed: {f_5} 398.55/291.54 Previous analysis results are: 398.55/291.54 f_0: runtime: O(1) [1], size: O(1) [0] 398.55/291.54 g_1: runtime: O(n^1) [2*z], size: O(1) [0] 398.55/291.54 f_1: runtime: O(n^1) [1 + 2*z], size: O(1) [0] 398.55/291.54 g_2: runtime: O(n^2) [2*z + 2*z*z'], size: O(1) [0] 398.55/291.54 f_2: runtime: O(n^2) [1 + 2*z + 2*z^2], size: O(1) [0] 398.55/291.54 g_3: runtime: O(n^3) [2*z + 2*z*z' + 2*z*z'^2], size: O(1) [0] 398.55/291.54 f_3: runtime: O(n^3) [1 + 2*z + 2*z^2 + 2*z^3], size: O(1) [0] 398.55/291.54 g_4: runtime: O(n^4) [2*z + 2*z*z' + 2*z*z'^2 + 2*z*z'^3], size: O(1) [0] 398.55/291.54 f_4: runtime: O(n^4) [1 + 2*z + 2*z^2 + 2*z^3 + 2*z^4], size: O(1) [0] 398.55/291.54 g_5: runtime: O(n^5) [2*z + 2*z*z' + 2*z*z'^2 + 2*z*z'^3 + 2*z*z'^4], size: O(1) [0] 398.55/291.54 f_5: runtime: ?, size: O(1) [0] 398.55/291.54 398.55/291.54 ---------------------------------------- 398.55/291.54 398.55/291.54 (81) IntTrsBoundProof (UPPER BOUND(ID)) 398.55/291.54 398.55/291.54 Computed RUNTIME bound using KoAT for: f_5 398.55/291.54 after applying outer abstraction to obtain an ITS, 398.55/291.54 resulting in: O(n^5) with polynomial bound: 1 + 2*z + 2*z^2 + 2*z^3 + 2*z^4 + 2*z^5 398.55/291.54 398.55/291.54 ---------------------------------------- 398.55/291.54 398.55/291.54 (82) 398.55/291.54 Obligation: 398.55/291.54 Complexity RNTS consisting of the following rules: 398.55/291.54 398.55/291.54 f_0(z) -{ 1 }-> 0 :|: z >= 0 398.55/291.54 f_1(z) -{ 1 + 2*z }-> s :|: s >= 0, s <= 0, z >= 0 398.55/291.54 f_2(z) -{ 1 + 2*z + 2*z^2 }-> s1 :|: s1 >= 0, s1 <= 0, z >= 0 398.55/291.54 f_3(z) -{ 1 + 2*z + 2*z^2 + 2*z^3 }-> s4 :|: s4 >= 0, s4 <= 0, z >= 0 398.55/291.54 f_4(z) -{ 1 + 2*z + 2*z^2 + 2*z^3 + 2*z^4 }-> s7 :|: s7 >= 0, s7 <= 0, z >= 0 398.55/291.54 f_5(z) -{ 1 + 2*z + 2*z^2 + 2*z^3 + 2*z^4 + 2*z^5 }-> s10 :|: s10 >= 0, s10 <= 0, z >= 0 398.55/291.54 g_1(z, z') -{ 2*z }-> 1 + 0 + s' :|: s' >= 0, s' <= 0, z - 1 >= 0, z' >= 0 398.55/291.54 g_2(z, z') -{ 2*z + 2*z*z' }-> 1 + s'' + s2 :|: s2 >= 0, s2 <= 0, s'' >= 0, s'' <= 0, z - 1 >= 0, z' >= 0 398.55/291.54 g_3(z, z') -{ 2*z + 2*z*z' + 2*z*z'^2 }-> 1 + s3 + s5 :|: s5 >= 0, s5 <= 0, s3 >= 0, s3 <= 0, z - 1 >= 0, z' >= 0 398.55/291.54 g_4(z, z') -{ 2*z + 2*z*z' + 2*z*z'^2 + 2*z*z'^3 }-> 1 + s6 + s8 :|: s8 >= 0, s8 <= 0, s6 >= 0, s6 <= 0, z - 1 >= 0, z' >= 0 398.55/291.54 g_5(z, z') -{ 2*z + 2*z*z' + 2*z*z'^2 + 2*z*z'^3 + 2*z*z'^4 }-> 1 + s9 + s11 :|: s11 >= 0, s11 <= 0, s9 >= 0, s9 <= 0, z - 1 >= 0, z' >= 0 398.55/291.54 398.55/291.54 Function symbols to be analyzed: 398.55/291.54 Previous analysis results are: 398.55/291.54 f_0: runtime: O(1) [1], size: O(1) [0] 398.55/291.54 g_1: runtime: O(n^1) [2*z], size: O(1) [0] 398.55/291.54 f_1: runtime: O(n^1) [1 + 2*z], size: O(1) [0] 398.55/291.54 g_2: runtime: O(n^2) [2*z + 2*z*z'], size: O(1) [0] 398.55/291.54 f_2: runtime: O(n^2) [1 + 2*z + 2*z^2], size: O(1) [0] 398.55/291.54 g_3: runtime: O(n^3) [2*z + 2*z*z' + 2*z*z'^2], size: O(1) [0] 398.55/291.54 f_3: runtime: O(n^3) [1 + 2*z + 2*z^2 + 2*z^3], size: O(1) [0] 398.55/291.54 g_4: runtime: O(n^4) [2*z + 2*z*z' + 2*z*z'^2 + 2*z*z'^3], size: O(1) [0] 398.55/291.54 f_4: runtime: O(n^4) [1 + 2*z + 2*z^2 + 2*z^3 + 2*z^4], size: O(1) [0] 398.55/291.54 g_5: runtime: O(n^5) [2*z + 2*z*z' + 2*z*z'^2 + 2*z*z'^3 + 2*z*z'^4], size: O(1) [0] 398.55/291.54 f_5: runtime: O(n^5) [1 + 2*z + 2*z^2 + 2*z^3 + 2*z^4 + 2*z^5], size: O(1) [0] 398.55/291.54 398.55/291.54 ---------------------------------------- 398.55/291.54 398.55/291.54 (83) FinalProof (FINISHED) 398.55/291.54 Computed overall runtime complexity 398.55/291.54 ---------------------------------------- 398.55/291.54 398.55/291.54 (84) 398.55/291.54 BOUNDS(1, n^5) 398.55/291.54 398.55/291.54 ---------------------------------------- 398.55/291.54 398.55/291.54 (85) RelTrsToDecreasingLoopProblemProof (LOWER BOUND(ID)) 398.55/291.54 Transformed a relative TRS into a decreasing-loop problem. 398.55/291.54 ---------------------------------------- 398.55/291.54 398.55/291.54 (86) 398.55/291.54 Obligation: 398.55/291.54 Analyzing the following TRS for decreasing loops: 398.55/291.54 398.55/291.54 The Runtime Complexity (innermost) of the given CpxTRS could be proven to be BOUNDS(n^1, n^5). 398.55/291.54 398.55/291.54 398.55/291.54 The TRS R consists of the following rules: 398.55/291.54 398.55/291.54 f_0(x) -> a 398.55/291.54 f_1(x) -> g_1(x, x) 398.55/291.54 g_1(s(x), y) -> b(f_0(y), g_1(x, y)) 398.55/291.54 f_2(x) -> g_2(x, x) 398.55/291.54 g_2(s(x), y) -> b(f_1(y), g_2(x, y)) 398.55/291.54 f_3(x) -> g_3(x, x) 398.55/291.54 g_3(s(x), y) -> b(f_2(y), g_3(x, y)) 398.55/291.54 f_4(x) -> g_4(x, x) 398.55/291.54 g_4(s(x), y) -> b(f_3(y), g_4(x, y)) 398.55/291.54 f_5(x) -> g_5(x, x) 398.55/291.54 g_5(s(x), y) -> b(f_4(y), g_5(x, y)) 398.55/291.54 398.55/291.54 S is empty. 398.55/291.54 Rewrite Strategy: INNERMOST 398.55/291.54 ---------------------------------------- 398.55/291.54 398.55/291.54 (87) DecreasingLoopProof (LOWER BOUND(ID)) 398.55/291.54 The following loop(s) give(s) rise to the lower bound Omega(n^1): 398.55/291.54 398.55/291.54 The rewrite sequence 398.55/291.54 398.55/291.54 g_2(s(x), y) ->^+ b(f_1(y), g_2(x, y)) 398.55/291.54 398.55/291.54 gives rise to a decreasing loop by considering the right hand sides subterm at position [1]. 398.55/291.54 398.55/291.54 The pumping substitution is [x / s(x)]. 398.55/291.54 398.55/291.54 The result substitution is [ ]. 398.55/291.54 398.55/291.54 398.55/291.54 398.55/291.54 398.55/291.54 ---------------------------------------- 398.55/291.54 398.55/291.54 (88) 398.55/291.54 Complex Obligation (BEST) 398.55/291.54 398.55/291.54 ---------------------------------------- 398.55/291.54 398.55/291.54 (89) 398.55/291.54 Obligation: 398.55/291.54 Proved the lower bound n^1 for the following obligation: 398.55/291.54 398.55/291.54 The Runtime Complexity (innermost) of the given CpxTRS could be proven to be BOUNDS(n^1, n^5). 398.55/291.54 398.55/291.54 398.55/291.54 The TRS R consists of the following rules: 398.55/291.54 398.55/291.54 f_0(x) -> a 398.55/291.54 f_1(x) -> g_1(x, x) 398.55/291.54 g_1(s(x), y) -> b(f_0(y), g_1(x, y)) 398.55/291.54 f_2(x) -> g_2(x, x) 398.55/291.54 g_2(s(x), y) -> b(f_1(y), g_2(x, y)) 398.55/291.54 f_3(x) -> g_3(x, x) 398.55/291.54 g_3(s(x), y) -> b(f_2(y), g_3(x, y)) 398.55/291.54 f_4(x) -> g_4(x, x) 398.55/291.54 g_4(s(x), y) -> b(f_3(y), g_4(x, y)) 398.55/291.54 f_5(x) -> g_5(x, x) 398.55/291.54 g_5(s(x), y) -> b(f_4(y), g_5(x, y)) 398.55/291.54 398.55/291.54 S is empty. 398.55/291.54 Rewrite Strategy: INNERMOST 398.55/291.54 ---------------------------------------- 398.55/291.54 398.55/291.54 (90) LowerBoundPropagationProof (FINISHED) 398.55/291.54 Propagated lower bound. 398.55/291.54 ---------------------------------------- 398.55/291.54 398.55/291.54 (91) 398.55/291.54 BOUNDS(n^1, INF) 398.55/291.54 398.55/291.54 ---------------------------------------- 398.55/291.54 398.55/291.54 (92) 398.55/291.54 Obligation: 398.55/291.54 Analyzing the following TRS for decreasing loops: 398.55/291.54 398.55/291.54 The Runtime Complexity (innermost) of the given CpxTRS could be proven to be BOUNDS(n^1, n^5). 398.55/291.54 398.55/291.54 398.55/291.54 The TRS R consists of the following rules: 398.55/291.54 398.55/291.54 f_0(x) -> a 398.55/291.54 f_1(x) -> g_1(x, x) 398.55/291.54 g_1(s(x), y) -> b(f_0(y), g_1(x, y)) 398.55/291.54 f_2(x) -> g_2(x, x) 398.55/291.54 g_2(s(x), y) -> b(f_1(y), g_2(x, y)) 398.55/291.54 f_3(x) -> g_3(x, x) 398.55/291.54 g_3(s(x), y) -> b(f_2(y), g_3(x, y)) 398.55/291.54 f_4(x) -> g_4(x, x) 398.55/291.54 g_4(s(x), y) -> b(f_3(y), g_4(x, y)) 398.55/291.54 f_5(x) -> g_5(x, x) 398.55/291.54 g_5(s(x), y) -> b(f_4(y), g_5(x, y)) 398.55/291.54 398.55/291.54 S is empty. 398.55/291.54 Rewrite Strategy: INNERMOST 398.67/291.58 EOF