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