/export/starexec/sandbox2/solver/bin/starexec_run_complexity /export/starexec/sandbox2/benchmark/theBenchmark.xml /export/starexec/sandbox2/output/output_files


--------------------------------------------------------------------------------


WORST_CASE(Omega(n^1), O(n^5))
proof of /export/starexec/sandbox2/benchmark/theBenchmark.xml
# AProVE Commit ID: 794c25de1cacf0d048858bcd21c9a779e1221865 marcel 20200619 unpublished dirty


The Runtime Complexity (full) of the given CpxTRS could be proven to be BOUNDS(n^1, n^5).

(0) CpxTRS
(1) RcToIrcProof [BOTH BOUNDS(ID, ID), 4 ms]
(2) CpxTRS
    (3) RelTrsToWeightedTrsProof [BOTH BOUNDS(ID, ID), 0 ms]
    (4) CpxWeightedTrs
    (5) TypeInferenceProof [BOTH BOUNDS(ID, ID), 0 ms]
    (6) CpxTypedWeightedTrs
    (7) CompletionProof [UPPER BOUND(ID), 0 ms]
    (8) CpxTypedWeightedCompleteTrs
    (9) NarrowingProof [BOTH BOUNDS(ID, ID), 0 ms]
    (10) CpxTypedWeightedCompleteTrs
    (11) CpxTypedWeightedTrsToRntsProof [UPPER BOUND(ID), 0 ms]
    (12) CpxRNTS
    (13) InliningProof [UPPER BOUND(ID), 27 ms]
    (14) CpxRNTS
    (15) SimplificationProof [BOTH BOUNDS(ID, ID), 0 ms]
    (16) CpxRNTS
    (17) CpxRntsAnalysisOrderProof [BOTH BOUNDS(ID, ID), 0 ms]
    (18) CpxRNTS
    (19) ResultPropagationProof [UPPER BOUND(ID), 0 ms]
    (20) CpxRNTS
    (21) IntTrsBoundProof [UPPER BOUND(ID), 128 ms]
    (22) CpxRNTS
    (23) IntTrsBoundProof [UPPER BOUND(ID), 44 ms]
    (24) CpxRNTS
    (25) ResultPropagationProof [UPPER BOUND(ID), 0 ms]
    (26) CpxRNTS
    (27) IntTrsBoundProof [UPPER BOUND(ID), 138 ms]
    (28) CpxRNTS
    (29) IntTrsBoundProof [UPPER BOUND(ID), 62 ms]
    (30) CpxRNTS
    (31) ResultPropagationProof [UPPER BOUND(ID), 0 ms]
    (32) CpxRNTS
    (33) IntTrsBoundProof [UPPER BOUND(ID), 106 ms]
    (34) CpxRNTS
    (35) IntTrsBoundProof [UPPER BOUND(ID), 52 ms]
    (36) CpxRNTS
    (37) ResultPropagationProof [UPPER BOUND(ID), 0 ms]
    (38) CpxRNTS
    (39) IntTrsBoundProof [UPPER BOUND(ID), 147 ms]
    (40) CpxRNTS
    (41) IntTrsBoundProof [UPPER BOUND(ID), 92 ms]
    (42) CpxRNTS
    (43) ResultPropagationProof [UPPER BOUND(ID), 0 ms]
    (44) CpxRNTS
    (45) IntTrsBoundProof [UPPER BOUND(ID), 126 ms]
    (46) CpxRNTS
    (47) IntTrsBoundProof [UPPER BOUND(ID), 0 ms]
    (48) CpxRNTS
    (49) ResultPropagationProof [UPPER BOUND(ID), 0 ms]
    (50) CpxRNTS
    (51) IntTrsBoundProof [UPPER BOUND(ID), 147 ms]
    (52) CpxRNTS
    (53) IntTrsBoundProof [UPPER BOUND(ID), 2 ms]
    (54) CpxRNTS
    (55) ResultPropagationProof [UPPER BOUND(ID), 0 ms]
    (56) CpxRNTS
    (57) IntTrsBoundProof [UPPER BOUND(ID), 76 ms]
    (58) CpxRNTS
    (59) IntTrsBoundProof [UPPER BOUND(ID), 0 ms]
    (60) CpxRNTS
    (61) ResultPropagationProof [UPPER BOUND(ID), 0 ms]
    (62) CpxRNTS
    (63) IntTrsBoundProof [UPPER BOUND(ID), 78 ms]
    (64) CpxRNTS
    (65) IntTrsBoundProof [UPPER BOUND(ID), 0 ms]
    (66) CpxRNTS
    (67) ResultPropagationProof [UPPER BOUND(ID), 0 ms]
    (68) CpxRNTS
    (69) IntTrsBoundProof [UPPER BOUND(ID), 68 ms]
    (70) CpxRNTS
    (71) IntTrsBoundProof [UPPER BOUND(ID), 0 ms]
    (72) CpxRNTS
    (73) ResultPropagationProof [UPPER BOUND(ID), 0 ms]
    (74) CpxRNTS
    (75) IntTrsBoundProof [UPPER BOUND(ID), 178 ms]
    (76) CpxRNTS
    (77) IntTrsBoundProof [UPPER BOUND(ID), 3 ms]
    (78) CpxRNTS
    (79) ResultPropagationProof [UPPER BOUND(ID), 0 ms]
    (80) CpxRNTS
    (81) IntTrsBoundProof [UPPER BOUND(ID), 77 ms]
    (82) CpxRNTS
    (83) IntTrsBoundProof [UPPER BOUND(ID), 0 ms]
    (84) CpxRNTS
    (85) FinalProof [FINISHED, 0 ms]
    (86) BOUNDS(1, n^5)
(87) RenamingProof [BOTH BOUNDS(ID, ID), 0 ms]
(88) CpxTRS
    (89) SlicingProof [LOWER BOUND(ID), 0 ms]
    (90) CpxTRS
    (91) TypeInferenceProof [BOTH BOUNDS(ID, ID), 0 ms]
    (92) typed CpxTrs
    (93) OrderProof [LOWER BOUND(ID), 0 ms]
    (94) typed CpxTrs
    (95) RewriteLemmaProof [LOWER BOUND(ID), 423 ms]
    (96) BEST
        (97) proven lower bound
            (98) LowerBoundPropagationProof [FINISHED, 0 ms]
            (99) BOUNDS(n^1, INF)
        (100) typed CpxTrs


----------------------------------------

(0)
Obligation:
The Runtime Complexity (full) of the given CpxTRS could be proven to be BOUNDS(n^1, n^5).


The TRS R consists of the following rules:

   f_0(x) -> a
   f_1(x) -> g_1(x, x)
   g_1(s(x), y) -> b(f_0(y), g_1(x, y))
   f_2(x) -> g_2(x, x)
   g_2(s(x), y) -> b(f_1(y), g_2(x, y))
   f_3(x) -> g_3(x, x)
   g_3(s(x), y) -> b(f_2(y), g_3(x, y))
   f_4(x) -> g_4(x, x)
   g_4(s(x), y) -> b(f_3(y), g_4(x, y))
   f_5(x) -> g_5(x, x)
   g_5(s(x), y) -> b(f_4(y), g_5(x, y))

S is empty.
Rewrite Strategy: FULL
----------------------------------------

(1) RcToIrcProof (BOTH BOUNDS(ID, ID))
Converted rc-obligation to irc-obligation.

As the TRS does not nest defined symbols, we have rc = irc.
----------------------------------------

(2)
Obligation:
The Runtime Complexity (innermost) of the given CpxTRS could be proven to be BOUNDS(1, n^5).


The TRS R consists of the following rules:

   f_0(x) -> a
   f_1(x) -> g_1(x, x)
   g_1(s(x), y) -> b(f_0(y), g_1(x, y))
   f_2(x) -> g_2(x, x)
   g_2(s(x), y) -> b(f_1(y), g_2(x, y))
   f_3(x) -> g_3(x, x)
   g_3(s(x), y) -> b(f_2(y), g_3(x, y))
   f_4(x) -> g_4(x, x)
   g_4(s(x), y) -> b(f_3(y), g_4(x, y))
   f_5(x) -> g_5(x, x)
   g_5(s(x), y) -> b(f_4(y), g_5(x, y))

S is empty.
Rewrite Strategy: INNERMOST
----------------------------------------

(3) RelTrsToWeightedTrsProof (BOTH BOUNDS(ID, ID))
Transformed relative TRS to weighted TRS
----------------------------------------

(4)
Obligation:
The Runtime Complexity (innermost) of the given CpxWeightedTrs could be proven to be BOUNDS(1, n^5).


The TRS R consists of the following rules:

   f_0(x) -> a [1]
   f_1(x) -> g_1(x, x) [1]
   g_1(s(x), y) -> b(f_0(y), g_1(x, y)) [1]
   f_2(x) -> g_2(x, x) [1]
   g_2(s(x), y) -> b(f_1(y), g_2(x, y)) [1]
   f_3(x) -> g_3(x, x) [1]
   g_3(s(x), y) -> b(f_2(y), g_3(x, y)) [1]
   f_4(x) -> g_4(x, x) [1]
   g_4(s(x), y) -> b(f_3(y), g_4(x, y)) [1]
   f_5(x) -> g_5(x, x) [1]
   g_5(s(x), y) -> b(f_4(y), g_5(x, y)) [1]

Rewrite Strategy: INNERMOST
----------------------------------------

(5) TypeInferenceProof (BOTH BOUNDS(ID, ID))
Infered types.
----------------------------------------

(6)
Obligation:
Runtime Complexity Weighted TRS with Types.
The TRS R consists of the following rules:

   f_0(x) -> a [1]
   f_1(x) -> g_1(x, x) [1]
   g_1(s(x), y) -> b(f_0(y), g_1(x, y)) [1]
   f_2(x) -> g_2(x, x) [1]
   g_2(s(x), y) -> b(f_1(y), g_2(x, y)) [1]
   f_3(x) -> g_3(x, x) [1]
   g_3(s(x), y) -> b(f_2(y), g_3(x, y)) [1]
   f_4(x) -> g_4(x, x) [1]
   g_4(s(x), y) -> b(f_3(y), g_4(x, y)) [1]
   f_5(x) -> g_5(x, x) [1]
   g_5(s(x), y) -> b(f_4(y), g_5(x, y)) [1]

The TRS has the following type information:
f_0 :: s -> a:b
a :: a:b
f_1 :: s -> a:b
g_1 :: s -> s -> a:b
s :: s -> s
b :: a:b -> a:b -> a:b
f_2 :: s -> a:b
g_2 :: s -> s -> a:b
f_3 :: s -> a:b
g_3 :: s -> s -> a:b
f_4 :: s -> a:b
g_4 :: s -> s -> a:b
f_5 :: s -> a:b
g_5 :: s -> s -> a:b

Rewrite Strategy: INNERMOST
----------------------------------------

(7) CompletionProof (UPPER BOUND(ID))
The transformation into a RNTS is sound, since:

(a) The obligation is a constructor system where every type has a constant constructor,

(b) The following defined symbols do not have to be completely defined, as they can never occur inside other defined symbols:

   f_0_1
   f_1_1
   g_1_2
   f_2_1
   g_2_2
   f_3_1
   g_3_2
   f_4_1
   g_4_2
   f_5_1
   g_5_2

(c) The following functions are completely defined:
none

Due to the following rules being added:
none

And the following fresh constants:    const

----------------------------------------

(8)
Obligation:
Runtime Complexity Weighted TRS where critical functions are completely defined. The underlying TRS is:

Runtime Complexity Weighted TRS with Types.
The TRS R consists of the following rules:

   f_0(x) -> a [1]
   f_1(x) -> g_1(x, x) [1]
   g_1(s(x), y) -> b(f_0(y), g_1(x, y)) [1]
   f_2(x) -> g_2(x, x) [1]
   g_2(s(x), y) -> b(f_1(y), g_2(x, y)) [1]
   f_3(x) -> g_3(x, x) [1]
   g_3(s(x), y) -> b(f_2(y), g_3(x, y)) [1]
   f_4(x) -> g_4(x, x) [1]
   g_4(s(x), y) -> b(f_3(y), g_4(x, y)) [1]
   f_5(x) -> g_5(x, x) [1]
   g_5(s(x), y) -> b(f_4(y), g_5(x, y)) [1]

The TRS has the following type information:
f_0 :: s -> a:b
a :: a:b
f_1 :: s -> a:b
g_1 :: s -> s -> a:b
s :: s -> s
b :: a:b -> a:b -> a:b
f_2 :: s -> a:b
g_2 :: s -> s -> a:b
f_3 :: s -> a:b
g_3 :: s -> s -> a:b
f_4 :: s -> a:b
g_4 :: s -> s -> a:b
f_5 :: s -> a:b
g_5 :: s -> s -> a:b
const :: s

Rewrite Strategy: INNERMOST
----------------------------------------

(9) NarrowingProof (BOTH BOUNDS(ID, ID))
Narrowed the inner basic terms of all right-hand sides by a single narrowing step.
----------------------------------------

(10)
Obligation:
Runtime Complexity Weighted TRS where critical functions are completely defined. The underlying TRS is:

Runtime Complexity Weighted TRS with Types.
The TRS R consists of the following rules:

   f_0(x) -> a [1]
   f_1(x) -> g_1(x, x) [1]
   g_1(s(x), y) -> b(f_0(y), g_1(x, y)) [1]
   f_2(x) -> g_2(x, x) [1]
   g_2(s(x), y) -> b(f_1(y), g_2(x, y)) [1]
   f_3(x) -> g_3(x, x) [1]
   g_3(s(x), y) -> b(f_2(y), g_3(x, y)) [1]
   f_4(x) -> g_4(x, x) [1]
   g_4(s(x), y) -> b(f_3(y), g_4(x, y)) [1]
   f_5(x) -> g_5(x, x) [1]
   g_5(s(x), y) -> b(f_4(y), g_5(x, y)) [1]

The TRS has the following type information:
f_0 :: s -> a:b
a :: a:b
f_1 :: s -> a:b
g_1 :: s -> s -> a:b
s :: s -> s
b :: a:b -> a:b -> a:b
f_2 :: s -> a:b
g_2 :: s -> s -> a:b
f_3 :: s -> a:b
g_3 :: s -> s -> a:b
f_4 :: s -> a:b
g_4 :: s -> s -> a:b
f_5 :: s -> a:b
g_5 :: s -> s -> a:b
const :: s

Rewrite Strategy: INNERMOST
----------------------------------------

(11) CpxTypedWeightedTrsToRntsProof (UPPER BOUND(ID))
Transformed the TRS into an over-approximating RNTS by (improved) Size Abstraction.
The constant constructors are abstracted as follows:

   a => 0
   const => 0

----------------------------------------

(12)
Obligation:
Complexity RNTS consisting of the following rules:

   f_0(z) -{ 1 }-> 0 :|: x >= 0, z = x
   f_1(z) -{ 1 }-> g_1(x, x) :|: x >= 0, z = x
   f_2(z) -{ 1 }-> g_2(x, x) :|: x >= 0, z = x
   f_3(z) -{ 1 }-> g_3(x, x) :|: x >= 0, z = x
   f_4(z) -{ 1 }-> g_4(x, x) :|: x >= 0, z = x
   f_5(z) -{ 1 }-> g_5(x, x) :|: x >= 0, z = x
   g_1(z, z') -{ 1 }-> 1 + f_0(y) + g_1(x, y) :|: x >= 0, y >= 0, z = 1 + x, z' = y
   g_2(z, z') -{ 1 }-> 1 + f_1(y) + g_2(x, y) :|: x >= 0, y >= 0, z = 1 + x, z' = y
   g_3(z, z') -{ 1 }-> 1 + f_2(y) + g_3(x, y) :|: x >= 0, y >= 0, z = 1 + x, z' = y
   g_4(z, z') -{ 1 }-> 1 + f_3(y) + g_4(x, y) :|: x >= 0, y >= 0, z = 1 + x, z' = y
   g_5(z, z') -{ 1 }-> 1 + f_4(y) + g_5(x, y) :|: x >= 0, y >= 0, z = 1 + x, z' = y


----------------------------------------

(13) InliningProof (UPPER BOUND(ID))
Inlined the following terminating rules on right-hand sides where appropriate:

   f_0(z) -{ 1 }-> 0 :|: x >= 0, z = x

----------------------------------------

(14)
Obligation:
Complexity RNTS consisting of the following rules:

   f_0(z) -{ 1 }-> 0 :|: x >= 0, z = x
   f_1(z) -{ 1 }-> g_1(x, x) :|: x >= 0, z = x
   f_2(z) -{ 1 }-> g_2(x, x) :|: x >= 0, z = x
   f_3(z) -{ 1 }-> g_3(x, x) :|: x >= 0, z = x
   f_4(z) -{ 1 }-> g_4(x, x) :|: x >= 0, z = x
   f_5(z) -{ 1 }-> g_5(x, x) :|: x >= 0, z = x
   g_1(z, z') -{ 2 }-> 1 + 0 + g_1(x, y) :|: x >= 0, y >= 0, z = 1 + x, z' = y, x' >= 0, y = x'
   g_2(z, z') -{ 1 }-> 1 + f_1(y) + g_2(x, y) :|: x >= 0, y >= 0, z = 1 + x, z' = y
   g_3(z, z') -{ 1 }-> 1 + f_2(y) + g_3(x, y) :|: x >= 0, y >= 0, z = 1 + x, z' = y
   g_4(z, z') -{ 1 }-> 1 + f_3(y) + g_4(x, y) :|: x >= 0, y >= 0, z = 1 + x, z' = y
   g_5(z, z') -{ 1 }-> 1 + f_4(y) + g_5(x, y) :|: x >= 0, y >= 0, z = 1 + x, z' = y


----------------------------------------

(15) SimplificationProof (BOTH BOUNDS(ID, ID))
Simplified the RNTS by moving equalities from the constraints into the right-hand sides.
----------------------------------------

(16)
Obligation:
Complexity RNTS consisting of the following rules:

   f_0(z) -{ 1 }-> 0 :|: z >= 0
   f_1(z) -{ 1 }-> g_1(z, z) :|: z >= 0
   f_2(z) -{ 1 }-> g_2(z, z) :|: z >= 0
   f_3(z) -{ 1 }-> g_3(z, z) :|: z >= 0
   f_4(z) -{ 1 }-> g_4(z, z) :|: z >= 0
   f_5(z) -{ 1 }-> g_5(z, z) :|: z >= 0
   g_1(z, z') -{ 2 }-> 1 + 0 + g_1(z - 1, z') :|: z - 1 >= 0, z' >= 0
   g_2(z, z') -{ 1 }-> 1 + f_1(z') + g_2(z - 1, z') :|: z - 1 >= 0, z' >= 0
   g_3(z, z') -{ 1 }-> 1 + f_2(z') + g_3(z - 1, z') :|: z - 1 >= 0, z' >= 0
   g_4(z, z') -{ 1 }-> 1 + f_3(z') + g_4(z - 1, z') :|: z - 1 >= 0, z' >= 0
   g_5(z, z') -{ 1 }-> 1 + f_4(z') + g_5(z - 1, z') :|: z - 1 >= 0, z' >= 0


----------------------------------------

(17) CpxRntsAnalysisOrderProof (BOTH BOUNDS(ID, ID))
Found the following analysis order by SCC decomposition:

   { f_0 }
   { g_1 }
   { f_1 }
   { g_2 }
   { f_2 }
   { g_3 }
   { f_3 }
   { g_4 }
   { f_4 }
   { g_5 }
   { f_5 }

----------------------------------------

(18)
Obligation:
Complexity RNTS consisting of the following rules:

   f_0(z) -{ 1 }-> 0 :|: z >= 0
   f_1(z) -{ 1 }-> g_1(z, z) :|: z >= 0
   f_2(z) -{ 1 }-> g_2(z, z) :|: z >= 0
   f_3(z) -{ 1 }-> g_3(z, z) :|: z >= 0
   f_4(z) -{ 1 }-> g_4(z, z) :|: z >= 0
   f_5(z) -{ 1 }-> g_5(z, z) :|: z >= 0
   g_1(z, z') -{ 2 }-> 1 + 0 + g_1(z - 1, z') :|: z - 1 >= 0, z' >= 0
   g_2(z, z') -{ 1 }-> 1 + f_1(z') + g_2(z - 1, z') :|: z - 1 >= 0, z' >= 0
   g_3(z, z') -{ 1 }-> 1 + f_2(z') + g_3(z - 1, z') :|: z - 1 >= 0, z' >= 0
   g_4(z, z') -{ 1 }-> 1 + f_3(z') + g_4(z - 1, z') :|: z - 1 >= 0, z' >= 0
   g_5(z, z') -{ 1 }-> 1 + f_4(z') + g_5(z - 1, z') :|: z - 1 >= 0, z' >= 0

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}

----------------------------------------

(19) ResultPropagationProof (UPPER BOUND(ID))
Applied inner abstraction using the recently inferred runtime/size bounds where possible.
----------------------------------------

(20)
Obligation:
Complexity RNTS consisting of the following rules:

   f_0(z) -{ 1 }-> 0 :|: z >= 0
   f_1(z) -{ 1 }-> g_1(z, z) :|: z >= 0
   f_2(z) -{ 1 }-> g_2(z, z) :|: z >= 0
   f_3(z) -{ 1 }-> g_3(z, z) :|: z >= 0
   f_4(z) -{ 1 }-> g_4(z, z) :|: z >= 0
   f_5(z) -{ 1 }-> g_5(z, z) :|: z >= 0
   g_1(z, z') -{ 2 }-> 1 + 0 + g_1(z - 1, z') :|: z - 1 >= 0, z' >= 0
   g_2(z, z') -{ 1 }-> 1 + f_1(z') + g_2(z - 1, z') :|: z - 1 >= 0, z' >= 0
   g_3(z, z') -{ 1 }-> 1 + f_2(z') + g_3(z - 1, z') :|: z - 1 >= 0, z' >= 0
   g_4(z, z') -{ 1 }-> 1 + f_3(z') + g_4(z - 1, z') :|: z - 1 >= 0, z' >= 0
   g_5(z, z') -{ 1 }-> 1 + f_4(z') + g_5(z - 1, z') :|: z - 1 >= 0, z' >= 0

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}

----------------------------------------

(21) IntTrsBoundProof (UPPER BOUND(ID))

Computed SIZE bound using CoFloCo for: f_0
after applying outer abstraction to obtain an ITS,
resulting in: O(1) with polynomial bound: 0

----------------------------------------

(22)
Obligation:
Complexity RNTS consisting of the following rules:

   f_0(z) -{ 1 }-> 0 :|: z >= 0
   f_1(z) -{ 1 }-> g_1(z, z) :|: z >= 0
   f_2(z) -{ 1 }-> g_2(z, z) :|: z >= 0
   f_3(z) -{ 1 }-> g_3(z, z) :|: z >= 0
   f_4(z) -{ 1 }-> g_4(z, z) :|: z >= 0
   f_5(z) -{ 1 }-> g_5(z, z) :|: z >= 0
   g_1(z, z') -{ 2 }-> 1 + 0 + g_1(z - 1, z') :|: z - 1 >= 0, z' >= 0
   g_2(z, z') -{ 1 }-> 1 + f_1(z') + g_2(z - 1, z') :|: z - 1 >= 0, z' >= 0
   g_3(z, z') -{ 1 }-> 1 + f_2(z') + g_3(z - 1, z') :|: z - 1 >= 0, z' >= 0
   g_4(z, z') -{ 1 }-> 1 + f_3(z') + g_4(z - 1, z') :|: z - 1 >= 0, z' >= 0
   g_5(z, z') -{ 1 }-> 1 + f_4(z') + g_5(z - 1, z') :|: z - 1 >= 0, z' >= 0

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}
Previous analysis results are:
  f_0: runtime: ?, size: O(1) [0]

----------------------------------------

(23) IntTrsBoundProof (UPPER BOUND(ID))

Computed RUNTIME bound using CoFloCo for: f_0
after applying outer abstraction to obtain an ITS,
resulting in: O(1) with polynomial bound: 1

----------------------------------------

(24)
Obligation:
Complexity RNTS consisting of the following rules:

   f_0(z) -{ 1 }-> 0 :|: z >= 0
   f_1(z) -{ 1 }-> g_1(z, z) :|: z >= 0
   f_2(z) -{ 1 }-> g_2(z, z) :|: z >= 0
   f_3(z) -{ 1 }-> g_3(z, z) :|: z >= 0
   f_4(z) -{ 1 }-> g_4(z, z) :|: z >= 0
   f_5(z) -{ 1 }-> g_5(z, z) :|: z >= 0
   g_1(z, z') -{ 2 }-> 1 + 0 + g_1(z - 1, z') :|: z - 1 >= 0, z' >= 0
   g_2(z, z') -{ 1 }-> 1 + f_1(z') + g_2(z - 1, z') :|: z - 1 >= 0, z' >= 0
   g_3(z, z') -{ 1 }-> 1 + f_2(z') + g_3(z - 1, z') :|: z - 1 >= 0, z' >= 0
   g_4(z, z') -{ 1 }-> 1 + f_3(z') + g_4(z - 1, z') :|: z - 1 >= 0, z' >= 0
   g_5(z, z') -{ 1 }-> 1 + f_4(z') + g_5(z - 1, z') :|: z - 1 >= 0, z' >= 0

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}
Previous analysis results are:
  f_0: runtime: O(1) [1], size: O(1) [0]

----------------------------------------

(25) ResultPropagationProof (UPPER BOUND(ID))
Applied inner abstraction using the recently inferred runtime/size bounds where possible.
----------------------------------------

(26)
Obligation:
Complexity RNTS consisting of the following rules:

   f_0(z) -{ 1 }-> 0 :|: z >= 0
   f_1(z) -{ 1 }-> g_1(z, z) :|: z >= 0
   f_2(z) -{ 1 }-> g_2(z, z) :|: z >= 0
   f_3(z) -{ 1 }-> g_3(z, z) :|: z >= 0
   f_4(z) -{ 1 }-> g_4(z, z) :|: z >= 0
   f_5(z) -{ 1 }-> g_5(z, z) :|: z >= 0
   g_1(z, z') -{ 2 }-> 1 + 0 + g_1(z - 1, z') :|: z - 1 >= 0, z' >= 0
   g_2(z, z') -{ 1 }-> 1 + f_1(z') + g_2(z - 1, z') :|: z - 1 >= 0, z' >= 0
   g_3(z, z') -{ 1 }-> 1 + f_2(z') + g_3(z - 1, z') :|: z - 1 >= 0, z' >= 0
   g_4(z, z') -{ 1 }-> 1 + f_3(z') + g_4(z - 1, z') :|: z - 1 >= 0, z' >= 0
   g_5(z, z') -{ 1 }-> 1 + f_4(z') + g_5(z - 1, z') :|: z - 1 >= 0, z' >= 0

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}
Previous analysis results are:
  f_0: runtime: O(1) [1], size: O(1) [0]

----------------------------------------

(27) IntTrsBoundProof (UPPER BOUND(ID))

Computed SIZE bound using CoFloCo for: g_1
after applying outer abstraction to obtain an ITS,
resulting in: O(1) with polynomial bound: 0

----------------------------------------

(28)
Obligation:
Complexity RNTS consisting of the following rules:

   f_0(z) -{ 1 }-> 0 :|: z >= 0
   f_1(z) -{ 1 }-> g_1(z, z) :|: z >= 0
   f_2(z) -{ 1 }-> g_2(z, z) :|: z >= 0
   f_3(z) -{ 1 }-> g_3(z, z) :|: z >= 0
   f_4(z) -{ 1 }-> g_4(z, z) :|: z >= 0
   f_5(z) -{ 1 }-> g_5(z, z) :|: z >= 0
   g_1(z, z') -{ 2 }-> 1 + 0 + g_1(z - 1, z') :|: z - 1 >= 0, z' >= 0
   g_2(z, z') -{ 1 }-> 1 + f_1(z') + g_2(z - 1, z') :|: z - 1 >= 0, z' >= 0
   g_3(z, z') -{ 1 }-> 1 + f_2(z') + g_3(z - 1, z') :|: z - 1 >= 0, z' >= 0
   g_4(z, z') -{ 1 }-> 1 + f_3(z') + g_4(z - 1, z') :|: z - 1 >= 0, z' >= 0
   g_5(z, z') -{ 1 }-> 1 + f_4(z') + g_5(z - 1, z') :|: z - 1 >= 0, z' >= 0

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}
Previous analysis results are:
  f_0: runtime: O(1) [1], size: O(1) [0]
  g_1: runtime: ?, size: O(1) [0]

----------------------------------------

(29) IntTrsBoundProof (UPPER BOUND(ID))

Computed RUNTIME bound using CoFloCo for: g_1
after applying outer abstraction to obtain an ITS,
resulting in: O(n^1) with polynomial bound: 2*z

----------------------------------------

(30)
Obligation:
Complexity RNTS consisting of the following rules:

   f_0(z) -{ 1 }-> 0 :|: z >= 0
   f_1(z) -{ 1 }-> g_1(z, z) :|: z >= 0
   f_2(z) -{ 1 }-> g_2(z, z) :|: z >= 0
   f_3(z) -{ 1 }-> g_3(z, z) :|: z >= 0
   f_4(z) -{ 1 }-> g_4(z, z) :|: z >= 0
   f_5(z) -{ 1 }-> g_5(z, z) :|: z >= 0
   g_1(z, z') -{ 2 }-> 1 + 0 + g_1(z - 1, z') :|: z - 1 >= 0, z' >= 0
   g_2(z, z') -{ 1 }-> 1 + f_1(z') + g_2(z - 1, z') :|: z - 1 >= 0, z' >= 0
   g_3(z, z') -{ 1 }-> 1 + f_2(z') + g_3(z - 1, z') :|: z - 1 >= 0, z' >= 0
   g_4(z, z') -{ 1 }-> 1 + f_3(z') + g_4(z - 1, z') :|: z - 1 >= 0, z' >= 0
   g_5(z, z') -{ 1 }-> 1 + f_4(z') + g_5(z - 1, z') :|: z - 1 >= 0, z' >= 0

Function symbols to be analyzed: {f_1}, {g_2}, {f_2}, {g_3}, {f_3}, {g_4}, {f_4}, {g_5}, {f_5}
Previous analysis results are:
  f_0: runtime: O(1) [1], size: O(1) [0]
  g_1: runtime: O(n^1) [2*z], size: O(1) [0]

----------------------------------------

(31) ResultPropagationProof (UPPER BOUND(ID))
Applied inner abstraction using the recently inferred runtime/size bounds where possible.
----------------------------------------

(32)
Obligation:
Complexity RNTS consisting of the following rules:

   f_0(z) -{ 1 }-> 0 :|: z >= 0
   f_1(z) -{ 1 + 2*z }-> s :|: s >= 0, s <= 0, z >= 0
   f_2(z) -{ 1 }-> g_2(z, z) :|: z >= 0
   f_3(z) -{ 1 }-> g_3(z, z) :|: z >= 0
   f_4(z) -{ 1 }-> g_4(z, z) :|: z >= 0
   f_5(z) -{ 1 }-> g_5(z, z) :|: z >= 0
   g_1(z, z') -{ 2*z }-> 1 + 0 + s' :|: s' >= 0, s' <= 0, z - 1 >= 0, z' >= 0
   g_2(z, z') -{ 1 }-> 1 + f_1(z') + g_2(z - 1, z') :|: z - 1 >= 0, z' >= 0
   g_3(z, z') -{ 1 }-> 1 + f_2(z') + g_3(z - 1, z') :|: z - 1 >= 0, z' >= 0
   g_4(z, z') -{ 1 }-> 1 + f_3(z') + g_4(z - 1, z') :|: z - 1 >= 0, z' >= 0
   g_5(z, z') -{ 1 }-> 1 + f_4(z') + g_5(z - 1, z') :|: z - 1 >= 0, z' >= 0

Function symbols to be analyzed: {f_1}, {g_2}, {f_2}, {g_3}, {f_3}, {g_4}, {f_4}, {g_5}, {f_5}
Previous analysis results are:
  f_0: runtime: O(1) [1], size: O(1) [0]
  g_1: runtime: O(n^1) [2*z], size: O(1) [0]

----------------------------------------

(33) IntTrsBoundProof (UPPER BOUND(ID))

Computed SIZE bound using CoFloCo for: f_1
after applying outer abstraction to obtain an ITS,
resulting in: O(1) with polynomial bound: 0

----------------------------------------

(34)
Obligation:
Complexity RNTS consisting of the following rules:

   f_0(z) -{ 1 }-> 0 :|: z >= 0
   f_1(z) -{ 1 + 2*z }-> s :|: s >= 0, s <= 0, z >= 0
   f_2(z) -{ 1 }-> g_2(z, z) :|: z >= 0
   f_3(z) -{ 1 }-> g_3(z, z) :|: z >= 0
   f_4(z) -{ 1 }-> g_4(z, z) :|: z >= 0
   f_5(z) -{ 1 }-> g_5(z, z) :|: z >= 0
   g_1(z, z') -{ 2*z }-> 1 + 0 + s' :|: s' >= 0, s' <= 0, z - 1 >= 0, z' >= 0
   g_2(z, z') -{ 1 }-> 1 + f_1(z') + g_2(z - 1, z') :|: z - 1 >= 0, z' >= 0
   g_3(z, z') -{ 1 }-> 1 + f_2(z') + g_3(z - 1, z') :|: z - 1 >= 0, z' >= 0
   g_4(z, z') -{ 1 }-> 1 + f_3(z') + g_4(z - 1, z') :|: z - 1 >= 0, z' >= 0
   g_5(z, z') -{ 1 }-> 1 + f_4(z') + g_5(z - 1, z') :|: z - 1 >= 0, z' >= 0

Function symbols to be analyzed: {f_1}, {g_2}, {f_2}, {g_3}, {f_3}, {g_4}, {f_4}, {g_5}, {f_5}
Previous analysis results are:
  f_0: runtime: O(1) [1], size: O(1) [0]
  g_1: runtime: O(n^1) [2*z], size: O(1) [0]
  f_1: runtime: ?, size: O(1) [0]

----------------------------------------

(35) IntTrsBoundProof (UPPER BOUND(ID))

Computed RUNTIME bound using CoFloCo for: f_1
after applying outer abstraction to obtain an ITS,
resulting in: O(n^1) with polynomial bound: 1 + 2*z

----------------------------------------

(36)
Obligation:
Complexity RNTS consisting of the following rules:

   f_0(z) -{ 1 }-> 0 :|: z >= 0
   f_1(z) -{ 1 + 2*z }-> s :|: s >= 0, s <= 0, z >= 0
   f_2(z) -{ 1 }-> g_2(z, z) :|: z >= 0
   f_3(z) -{ 1 }-> g_3(z, z) :|: z >= 0
   f_4(z) -{ 1 }-> g_4(z, z) :|: z >= 0
   f_5(z) -{ 1 }-> g_5(z, z) :|: z >= 0
   g_1(z, z') -{ 2*z }-> 1 + 0 + s' :|: s' >= 0, s' <= 0, z - 1 >= 0, z' >= 0
   g_2(z, z') -{ 1 }-> 1 + f_1(z') + g_2(z - 1, z') :|: z - 1 >= 0, z' >= 0
   g_3(z, z') -{ 1 }-> 1 + f_2(z') + g_3(z - 1, z') :|: z - 1 >= 0, z' >= 0
   g_4(z, z') -{ 1 }-> 1 + f_3(z') + g_4(z - 1, z') :|: z - 1 >= 0, z' >= 0
   g_5(z, z') -{ 1 }-> 1 + f_4(z') + g_5(z - 1, z') :|: z - 1 >= 0, z' >= 0

Function symbols to be analyzed: {g_2}, {f_2}, {g_3}, {f_3}, {g_4}, {f_4}, {g_5}, {f_5}
Previous analysis results are:
  f_0: runtime: O(1) [1], size: O(1) [0]
  g_1: runtime: O(n^1) [2*z], size: O(1) [0]
  f_1: runtime: O(n^1) [1 + 2*z], size: O(1) [0]

----------------------------------------

(37) ResultPropagationProof (UPPER BOUND(ID))
Applied inner abstraction using the recently inferred runtime/size bounds where possible.
----------------------------------------

(38)
Obligation:
Complexity RNTS consisting of the following rules:

   f_0(z) -{ 1 }-> 0 :|: z >= 0
   f_1(z) -{ 1 + 2*z }-> s :|: s >= 0, s <= 0, z >= 0
   f_2(z) -{ 1 }-> g_2(z, z) :|: z >= 0
   f_3(z) -{ 1 }-> g_3(z, z) :|: z >= 0
   f_4(z) -{ 1 }-> g_4(z, z) :|: z >= 0
   f_5(z) -{ 1 }-> g_5(z, z) :|: z >= 0
   g_1(z, z') -{ 2*z }-> 1 + 0 + s' :|: s' >= 0, s' <= 0, z - 1 >= 0, z' >= 0
   g_2(z, z') -{ 2 + 2*z' }-> 1 + s'' + g_2(z - 1, z') :|: s'' >= 0, s'' <= 0, z - 1 >= 0, z' >= 0
   g_3(z, z') -{ 1 }-> 1 + f_2(z') + g_3(z - 1, z') :|: z - 1 >= 0, z' >= 0
   g_4(z, z') -{ 1 }-> 1 + f_3(z') + g_4(z - 1, z') :|: z - 1 >= 0, z' >= 0
   g_5(z, z') -{ 1 }-> 1 + f_4(z') + g_5(z - 1, z') :|: z - 1 >= 0, z' >= 0

Function symbols to be analyzed: {g_2}, {f_2}, {g_3}, {f_3}, {g_4}, {f_4}, {g_5}, {f_5}
Previous analysis results are:
  f_0: runtime: O(1) [1], size: O(1) [0]
  g_1: runtime: O(n^1) [2*z], size: O(1) [0]
  f_1: runtime: O(n^1) [1 + 2*z], size: O(1) [0]

----------------------------------------

(39) IntTrsBoundProof (UPPER BOUND(ID))

Computed SIZE bound using CoFloCo for: g_2
after applying outer abstraction to obtain an ITS,
resulting in: O(1) with polynomial bound: 0

----------------------------------------

(40)
Obligation:
Complexity RNTS consisting of the following rules:

   f_0(z) -{ 1 }-> 0 :|: z >= 0
   f_1(z) -{ 1 + 2*z }-> s :|: s >= 0, s <= 0, z >= 0
   f_2(z) -{ 1 }-> g_2(z, z) :|: z >= 0
   f_3(z) -{ 1 }-> g_3(z, z) :|: z >= 0
   f_4(z) -{ 1 }-> g_4(z, z) :|: z >= 0
   f_5(z) -{ 1 }-> g_5(z, z) :|: z >= 0
   g_1(z, z') -{ 2*z }-> 1 + 0 + s' :|: s' >= 0, s' <= 0, z - 1 >= 0, z' >= 0
   g_2(z, z') -{ 2 + 2*z' }-> 1 + s'' + g_2(z - 1, z') :|: s'' >= 0, s'' <= 0, z - 1 >= 0, z' >= 0
   g_3(z, z') -{ 1 }-> 1 + f_2(z') + g_3(z - 1, z') :|: z - 1 >= 0, z' >= 0
   g_4(z, z') -{ 1 }-> 1 + f_3(z') + g_4(z - 1, z') :|: z - 1 >= 0, z' >= 0
   g_5(z, z') -{ 1 }-> 1 + f_4(z') + g_5(z - 1, z') :|: z - 1 >= 0, z' >= 0

Function symbols to be analyzed: {g_2}, {f_2}, {g_3}, {f_3}, {g_4}, {f_4}, {g_5}, {f_5}
Previous analysis results are:
  f_0: runtime: O(1) [1], size: O(1) [0]
  g_1: runtime: O(n^1) [2*z], size: O(1) [0]
  f_1: runtime: O(n^1) [1 + 2*z], size: O(1) [0]
  g_2: runtime: ?, size: O(1) [0]

----------------------------------------

(41) IntTrsBoundProof (UPPER BOUND(ID))

Computed RUNTIME bound using CoFloCo for: g_2
after applying outer abstraction to obtain an ITS,
resulting in: O(n^2) with polynomial bound: 2*z + 2*z*z'

----------------------------------------

(42)
Obligation:
Complexity RNTS consisting of the following rules:

   f_0(z) -{ 1 }-> 0 :|: z >= 0
   f_1(z) -{ 1 + 2*z }-> s :|: s >= 0, s <= 0, z >= 0
   f_2(z) -{ 1 }-> g_2(z, z) :|: z >= 0
   f_3(z) -{ 1 }-> g_3(z, z) :|: z >= 0
   f_4(z) -{ 1 }-> g_4(z, z) :|: z >= 0
   f_5(z) -{ 1 }-> g_5(z, z) :|: z >= 0
   g_1(z, z') -{ 2*z }-> 1 + 0 + s' :|: s' >= 0, s' <= 0, z - 1 >= 0, z' >= 0
   g_2(z, z') -{ 2 + 2*z' }-> 1 + s'' + g_2(z - 1, z') :|: s'' >= 0, s'' <= 0, z - 1 >= 0, z' >= 0
   g_3(z, z') -{ 1 }-> 1 + f_2(z') + g_3(z - 1, z') :|: z - 1 >= 0, z' >= 0
   g_4(z, z') -{ 1 }-> 1 + f_3(z') + g_4(z - 1, z') :|: z - 1 >= 0, z' >= 0
   g_5(z, z') -{ 1 }-> 1 + f_4(z') + g_5(z - 1, z') :|: z - 1 >= 0, z' >= 0

Function symbols to be analyzed: {f_2}, {g_3}, {f_3}, {g_4}, {f_4}, {g_5}, {f_5}
Previous analysis results are:
  f_0: runtime: O(1) [1], size: O(1) [0]
  g_1: runtime: O(n^1) [2*z], size: O(1) [0]
  f_1: runtime: O(n^1) [1 + 2*z], size: O(1) [0]
  g_2: runtime: O(n^2) [2*z + 2*z*z'], size: O(1) [0]

----------------------------------------

(43) ResultPropagationProof (UPPER BOUND(ID))
Applied inner abstraction using the recently inferred runtime/size bounds where possible.
----------------------------------------

(44)
Obligation:
Complexity RNTS consisting of the following rules:

   f_0(z) -{ 1 }-> 0 :|: z >= 0
   f_1(z) -{ 1 + 2*z }-> s :|: s >= 0, s <= 0, z >= 0
   f_2(z) -{ 1 + 2*z + 2*z^2 }-> s1 :|: s1 >= 0, s1 <= 0, z >= 0
   f_3(z) -{ 1 }-> g_3(z, z) :|: z >= 0
   f_4(z) -{ 1 }-> g_4(z, z) :|: z >= 0
   f_5(z) -{ 1 }-> g_5(z, z) :|: z >= 0
   g_1(z, z') -{ 2*z }-> 1 + 0 + s' :|: s' >= 0, s' <= 0, z - 1 >= 0, z' >= 0
   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
   g_3(z, z') -{ 1 }-> 1 + f_2(z') + g_3(z - 1, z') :|: z - 1 >= 0, z' >= 0
   g_4(z, z') -{ 1 }-> 1 + f_3(z') + g_4(z - 1, z') :|: z - 1 >= 0, z' >= 0
   g_5(z, z') -{ 1 }-> 1 + f_4(z') + g_5(z - 1, z') :|: z - 1 >= 0, z' >= 0

Function symbols to be analyzed: {f_2}, {g_3}, {f_3}, {g_4}, {f_4}, {g_5}, {f_5}
Previous analysis results are:
  f_0: runtime: O(1) [1], size: O(1) [0]
  g_1: runtime: O(n^1) [2*z], size: O(1) [0]
  f_1: runtime: O(n^1) [1 + 2*z], size: O(1) [0]
  g_2: runtime: O(n^2) [2*z + 2*z*z'], size: O(1) [0]

----------------------------------------

(45) IntTrsBoundProof (UPPER BOUND(ID))

Computed SIZE bound using CoFloCo for: f_2
after applying outer abstraction to obtain an ITS,
resulting in: O(1) with polynomial bound: 0

----------------------------------------

(46)
Obligation:
Complexity RNTS consisting of the following rules:

   f_0(z) -{ 1 }-> 0 :|: z >= 0
   f_1(z) -{ 1 + 2*z }-> s :|: s >= 0, s <= 0, z >= 0
   f_2(z) -{ 1 + 2*z + 2*z^2 }-> s1 :|: s1 >= 0, s1 <= 0, z >= 0
   f_3(z) -{ 1 }-> g_3(z, z) :|: z >= 0
   f_4(z) -{ 1 }-> g_4(z, z) :|: z >= 0
   f_5(z) -{ 1 }-> g_5(z, z) :|: z >= 0
   g_1(z, z') -{ 2*z }-> 1 + 0 + s' :|: s' >= 0, s' <= 0, z - 1 >= 0, z' >= 0
   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
   g_3(z, z') -{ 1 }-> 1 + f_2(z') + g_3(z - 1, z') :|: z - 1 >= 0, z' >= 0
   g_4(z, z') -{ 1 }-> 1 + f_3(z') + g_4(z - 1, z') :|: z - 1 >= 0, z' >= 0
   g_5(z, z') -{ 1 }-> 1 + f_4(z') + g_5(z - 1, z') :|: z - 1 >= 0, z' >= 0

Function symbols to be analyzed: {f_2}, {g_3}, {f_3}, {g_4}, {f_4}, {g_5}, {f_5}
Previous analysis results are:
  f_0: runtime: O(1) [1], size: O(1) [0]
  g_1: runtime: O(n^1) [2*z], size: O(1) [0]
  f_1: runtime: O(n^1) [1 + 2*z], size: O(1) [0]
  g_2: runtime: O(n^2) [2*z + 2*z*z'], size: O(1) [0]
  f_2: runtime: ?, size: O(1) [0]

----------------------------------------

(47) IntTrsBoundProof (UPPER BOUND(ID))

Computed RUNTIME bound using KoAT for: f_2
after applying outer abstraction to obtain an ITS,
resulting in: O(n^2) with polynomial bound: 1 + 2*z + 2*z^2

----------------------------------------

(48)
Obligation:
Complexity RNTS consisting of the following rules:

   f_0(z) -{ 1 }-> 0 :|: z >= 0
   f_1(z) -{ 1 + 2*z }-> s :|: s >= 0, s <= 0, z >= 0
   f_2(z) -{ 1 + 2*z + 2*z^2 }-> s1 :|: s1 >= 0, s1 <= 0, z >= 0
   f_3(z) -{ 1 }-> g_3(z, z) :|: z >= 0
   f_4(z) -{ 1 }-> g_4(z, z) :|: z >= 0
   f_5(z) -{ 1 }-> g_5(z, z) :|: z >= 0
   g_1(z, z') -{ 2*z }-> 1 + 0 + s' :|: s' >= 0, s' <= 0, z - 1 >= 0, z' >= 0
   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
   g_3(z, z') -{ 1 }-> 1 + f_2(z') + g_3(z - 1, z') :|: z - 1 >= 0, z' >= 0
   g_4(z, z') -{ 1 }-> 1 + f_3(z') + g_4(z - 1, z') :|: z - 1 >= 0, z' >= 0
   g_5(z, z') -{ 1 }-> 1 + f_4(z') + g_5(z - 1, z') :|: z - 1 >= 0, z' >= 0

Function symbols to be analyzed: {g_3}, {f_3}, {g_4}, {f_4}, {g_5}, {f_5}
Previous analysis results are:
  f_0: runtime: O(1) [1], size: O(1) [0]
  g_1: runtime: O(n^1) [2*z], size: O(1) [0]
  f_1: runtime: O(n^1) [1 + 2*z], size: O(1) [0]
  g_2: runtime: O(n^2) [2*z + 2*z*z'], size: O(1) [0]
  f_2: runtime: O(n^2) [1 + 2*z + 2*z^2], size: O(1) [0]

----------------------------------------

(49) ResultPropagationProof (UPPER BOUND(ID))
Applied inner abstraction using the recently inferred runtime/size bounds where possible.
----------------------------------------

(50)
Obligation:
Complexity RNTS consisting of the following rules:

   f_0(z) -{ 1 }-> 0 :|: z >= 0
   f_1(z) -{ 1 + 2*z }-> s :|: s >= 0, s <= 0, z >= 0
   f_2(z) -{ 1 + 2*z + 2*z^2 }-> s1 :|: s1 >= 0, s1 <= 0, z >= 0
   f_3(z) -{ 1 }-> g_3(z, z) :|: z >= 0
   f_4(z) -{ 1 }-> g_4(z, z) :|: z >= 0
   f_5(z) -{ 1 }-> g_5(z, z) :|: z >= 0
   g_1(z, z') -{ 2*z }-> 1 + 0 + s' :|: s' >= 0, s' <= 0, z - 1 >= 0, z' >= 0
   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
   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
   g_4(z, z') -{ 1 }-> 1 + f_3(z') + g_4(z - 1, z') :|: z - 1 >= 0, z' >= 0
   g_5(z, z') -{ 1 }-> 1 + f_4(z') + g_5(z - 1, z') :|: z - 1 >= 0, z' >= 0

Function symbols to be analyzed: {g_3}, {f_3}, {g_4}, {f_4}, {g_5}, {f_5}
Previous analysis results are:
  f_0: runtime: O(1) [1], size: O(1) [0]
  g_1: runtime: O(n^1) [2*z], size: O(1) [0]
  f_1: runtime: O(n^1) [1 + 2*z], size: O(1) [0]
  g_2: runtime: O(n^2) [2*z + 2*z*z'], size: O(1) [0]
  f_2: runtime: O(n^2) [1 + 2*z + 2*z^2], size: O(1) [0]

----------------------------------------

(51) IntTrsBoundProof (UPPER BOUND(ID))

Computed SIZE bound using CoFloCo for: g_3
after applying outer abstraction to obtain an ITS,
resulting in: O(1) with polynomial bound: 0

----------------------------------------

(52)
Obligation:
Complexity RNTS consisting of the following rules:

   f_0(z) -{ 1 }-> 0 :|: z >= 0
   f_1(z) -{ 1 + 2*z }-> s :|: s >= 0, s <= 0, z >= 0
   f_2(z) -{ 1 + 2*z + 2*z^2 }-> s1 :|: s1 >= 0, s1 <= 0, z >= 0
   f_3(z) -{ 1 }-> g_3(z, z) :|: z >= 0
   f_4(z) -{ 1 }-> g_4(z, z) :|: z >= 0
   f_5(z) -{ 1 }-> g_5(z, z) :|: z >= 0
   g_1(z, z') -{ 2*z }-> 1 + 0 + s' :|: s' >= 0, s' <= 0, z - 1 >= 0, z' >= 0
   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
   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
   g_4(z, z') -{ 1 }-> 1 + f_3(z') + g_4(z - 1, z') :|: z - 1 >= 0, z' >= 0
   g_5(z, z') -{ 1 }-> 1 + f_4(z') + g_5(z - 1, z') :|: z - 1 >= 0, z' >= 0

Function symbols to be analyzed: {g_3}, {f_3}, {g_4}, {f_4}, {g_5}, {f_5}
Previous analysis results are:
  f_0: runtime: O(1) [1], size: O(1) [0]
  g_1: runtime: O(n^1) [2*z], size: O(1) [0]
  f_1: runtime: O(n^1) [1 + 2*z], size: O(1) [0]
  g_2: runtime: O(n^2) [2*z + 2*z*z'], size: O(1) [0]
  f_2: runtime: O(n^2) [1 + 2*z + 2*z^2], size: O(1) [0]
  g_3: runtime: ?, size: O(1) [0]

----------------------------------------

(53) IntTrsBoundProof (UPPER BOUND(ID))

Computed RUNTIME bound using KoAT for: g_3
after applying outer abstraction to obtain an ITS,
resulting in: O(n^3) with polynomial bound: 2*z + 2*z*z' + 2*z*z'^2

----------------------------------------

(54)
Obligation:
Complexity RNTS consisting of the following rules:

   f_0(z) -{ 1 }-> 0 :|: z >= 0
   f_1(z) -{ 1 + 2*z }-> s :|: s >= 0, s <= 0, z >= 0
   f_2(z) -{ 1 + 2*z + 2*z^2 }-> s1 :|: s1 >= 0, s1 <= 0, z >= 0
   f_3(z) -{ 1 }-> g_3(z, z) :|: z >= 0
   f_4(z) -{ 1 }-> g_4(z, z) :|: z >= 0
   f_5(z) -{ 1 }-> g_5(z, z) :|: z >= 0
   g_1(z, z') -{ 2*z }-> 1 + 0 + s' :|: s' >= 0, s' <= 0, z - 1 >= 0, z' >= 0
   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
   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
   g_4(z, z') -{ 1 }-> 1 + f_3(z') + g_4(z - 1, z') :|: z - 1 >= 0, z' >= 0
   g_5(z, z') -{ 1 }-> 1 + f_4(z') + g_5(z - 1, z') :|: z - 1 >= 0, z' >= 0

Function symbols to be analyzed: {f_3}, {g_4}, {f_4}, {g_5}, {f_5}
Previous analysis results are:
  f_0: runtime: O(1) [1], size: O(1) [0]
  g_1: runtime: O(n^1) [2*z], size: O(1) [0]
  f_1: runtime: O(n^1) [1 + 2*z], size: O(1) [0]
  g_2: runtime: O(n^2) [2*z + 2*z*z'], size: O(1) [0]
  f_2: runtime: O(n^2) [1 + 2*z + 2*z^2], size: O(1) [0]
  g_3: runtime: O(n^3) [2*z + 2*z*z' + 2*z*z'^2], size: O(1) [0]

----------------------------------------

(55) ResultPropagationProof (UPPER BOUND(ID))
Applied inner abstraction using the recently inferred runtime/size bounds where possible.
----------------------------------------

(56)
Obligation:
Complexity RNTS consisting of the following rules:

   f_0(z) -{ 1 }-> 0 :|: z >= 0
   f_1(z) -{ 1 + 2*z }-> s :|: s >= 0, s <= 0, z >= 0
   f_2(z) -{ 1 + 2*z + 2*z^2 }-> s1 :|: s1 >= 0, s1 <= 0, z >= 0
   f_3(z) -{ 1 + 2*z + 2*z^2 + 2*z^3 }-> s4 :|: s4 >= 0, s4 <= 0, z >= 0
   f_4(z) -{ 1 }-> g_4(z, z) :|: z >= 0
   f_5(z) -{ 1 }-> g_5(z, z) :|: z >= 0
   g_1(z, z') -{ 2*z }-> 1 + 0 + s' :|: s' >= 0, s' <= 0, z - 1 >= 0, z' >= 0
   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
   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
   g_4(z, z') -{ 1 }-> 1 + f_3(z') + g_4(z - 1, z') :|: z - 1 >= 0, z' >= 0
   g_5(z, z') -{ 1 }-> 1 + f_4(z') + g_5(z - 1, z') :|: z - 1 >= 0, z' >= 0

Function symbols to be analyzed: {f_3}, {g_4}, {f_4}, {g_5}, {f_5}
Previous analysis results are:
  f_0: runtime: O(1) [1], size: O(1) [0]
  g_1: runtime: O(n^1) [2*z], size: O(1) [0]
  f_1: runtime: O(n^1) [1 + 2*z], size: O(1) [0]
  g_2: runtime: O(n^2) [2*z + 2*z*z'], size: O(1) [0]
  f_2: runtime: O(n^2) [1 + 2*z + 2*z^2], size: O(1) [0]
  g_3: runtime: O(n^3) [2*z + 2*z*z' + 2*z*z'^2], size: O(1) [0]

----------------------------------------

(57) IntTrsBoundProof (UPPER BOUND(ID))

Computed SIZE bound using CoFloCo for: f_3
after applying outer abstraction to obtain an ITS,
resulting in: O(1) with polynomial bound: 0

----------------------------------------

(58)
Obligation:
Complexity RNTS consisting of the following rules:

   f_0(z) -{ 1 }-> 0 :|: z >= 0
   f_1(z) -{ 1 + 2*z }-> s :|: s >= 0, s <= 0, z >= 0
   f_2(z) -{ 1 + 2*z + 2*z^2 }-> s1 :|: s1 >= 0, s1 <= 0, z >= 0
   f_3(z) -{ 1 + 2*z + 2*z^2 + 2*z^3 }-> s4 :|: s4 >= 0, s4 <= 0, z >= 0
   f_4(z) -{ 1 }-> g_4(z, z) :|: z >= 0
   f_5(z) -{ 1 }-> g_5(z, z) :|: z >= 0
   g_1(z, z') -{ 2*z }-> 1 + 0 + s' :|: s' >= 0, s' <= 0, z - 1 >= 0, z' >= 0
   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
   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
   g_4(z, z') -{ 1 }-> 1 + f_3(z') + g_4(z - 1, z') :|: z - 1 >= 0, z' >= 0
   g_5(z, z') -{ 1 }-> 1 + f_4(z') + g_5(z - 1, z') :|: z - 1 >= 0, z' >= 0

Function symbols to be analyzed: {f_3}, {g_4}, {f_4}, {g_5}, {f_5}
Previous analysis results are:
  f_0: runtime: O(1) [1], size: O(1) [0]
  g_1: runtime: O(n^1) [2*z], size: O(1) [0]
  f_1: runtime: O(n^1) [1 + 2*z], size: O(1) [0]
  g_2: runtime: O(n^2) [2*z + 2*z*z'], size: O(1) [0]
  f_2: runtime: O(n^2) [1 + 2*z + 2*z^2], size: O(1) [0]
  g_3: runtime: O(n^3) [2*z + 2*z*z' + 2*z*z'^2], size: O(1) [0]
  f_3: runtime: ?, size: O(1) [0]

----------------------------------------

(59) IntTrsBoundProof (UPPER BOUND(ID))

Computed RUNTIME bound using KoAT for: f_3
after applying outer abstraction to obtain an ITS,
resulting in: O(n^3) with polynomial bound: 1 + 2*z + 2*z^2 + 2*z^3

----------------------------------------

(60)
Obligation:
Complexity RNTS consisting of the following rules:

   f_0(z) -{ 1 }-> 0 :|: z >= 0
   f_1(z) -{ 1 + 2*z }-> s :|: s >= 0, s <= 0, z >= 0
   f_2(z) -{ 1 + 2*z + 2*z^2 }-> s1 :|: s1 >= 0, s1 <= 0, z >= 0
   f_3(z) -{ 1 + 2*z + 2*z^2 + 2*z^3 }-> s4 :|: s4 >= 0, s4 <= 0, z >= 0
   f_4(z) -{ 1 }-> g_4(z, z) :|: z >= 0
   f_5(z) -{ 1 }-> g_5(z, z) :|: z >= 0
   g_1(z, z') -{ 2*z }-> 1 + 0 + s' :|: s' >= 0, s' <= 0, z - 1 >= 0, z' >= 0
   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
   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
   g_4(z, z') -{ 1 }-> 1 + f_3(z') + g_4(z - 1, z') :|: z - 1 >= 0, z' >= 0
   g_5(z, z') -{ 1 }-> 1 + f_4(z') + g_5(z - 1, z') :|: z - 1 >= 0, z' >= 0

Function symbols to be analyzed: {g_4}, {f_4}, {g_5}, {f_5}
Previous analysis results are:
  f_0: runtime: O(1) [1], size: O(1) [0]
  g_1: runtime: O(n^1) [2*z], size: O(1) [0]
  f_1: runtime: O(n^1) [1 + 2*z], size: O(1) [0]
  g_2: runtime: O(n^2) [2*z + 2*z*z'], size: O(1) [0]
  f_2: runtime: O(n^2) [1 + 2*z + 2*z^2], size: O(1) [0]
  g_3: runtime: O(n^3) [2*z + 2*z*z' + 2*z*z'^2], size: O(1) [0]
  f_3: runtime: O(n^3) [1 + 2*z + 2*z^2 + 2*z^3], size: O(1) [0]

----------------------------------------

(61) ResultPropagationProof (UPPER BOUND(ID))
Applied inner abstraction using the recently inferred runtime/size bounds where possible.
----------------------------------------

(62)
Obligation:
Complexity RNTS consisting of the following rules:

   f_0(z) -{ 1 }-> 0 :|: z >= 0
   f_1(z) -{ 1 + 2*z }-> s :|: s >= 0, s <= 0, z >= 0
   f_2(z) -{ 1 + 2*z + 2*z^2 }-> s1 :|: s1 >= 0, s1 <= 0, z >= 0
   f_3(z) -{ 1 + 2*z + 2*z^2 + 2*z^3 }-> s4 :|: s4 >= 0, s4 <= 0, z >= 0
   f_4(z) -{ 1 }-> g_4(z, z) :|: z >= 0
   f_5(z) -{ 1 }-> g_5(z, z) :|: z >= 0
   g_1(z, z') -{ 2*z }-> 1 + 0 + s' :|: s' >= 0, s' <= 0, z - 1 >= 0, z' >= 0
   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
   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
   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
   g_5(z, z') -{ 1 }-> 1 + f_4(z') + g_5(z - 1, z') :|: z - 1 >= 0, z' >= 0

Function symbols to be analyzed: {g_4}, {f_4}, {g_5}, {f_5}
Previous analysis results are:
  f_0: runtime: O(1) [1], size: O(1) [0]
  g_1: runtime: O(n^1) [2*z], size: O(1) [0]
  f_1: runtime: O(n^1) [1 + 2*z], size: O(1) [0]
  g_2: runtime: O(n^2) [2*z + 2*z*z'], size: O(1) [0]
  f_2: runtime: O(n^2) [1 + 2*z + 2*z^2], size: O(1) [0]
  g_3: runtime: O(n^3) [2*z + 2*z*z' + 2*z*z'^2], size: O(1) [0]
  f_3: runtime: O(n^3) [1 + 2*z + 2*z^2 + 2*z^3], size: O(1) [0]

----------------------------------------

(63) IntTrsBoundProof (UPPER BOUND(ID))

Computed SIZE bound using CoFloCo for: g_4
after applying outer abstraction to obtain an ITS,
resulting in: O(1) with polynomial bound: 0

----------------------------------------

(64)
Obligation:
Complexity RNTS consisting of the following rules:

   f_0(z) -{ 1 }-> 0 :|: z >= 0
   f_1(z) -{ 1 + 2*z }-> s :|: s >= 0, s <= 0, z >= 0
   f_2(z) -{ 1 + 2*z + 2*z^2 }-> s1 :|: s1 >= 0, s1 <= 0, z >= 0
   f_3(z) -{ 1 + 2*z + 2*z^2 + 2*z^3 }-> s4 :|: s4 >= 0, s4 <= 0, z >= 0
   f_4(z) -{ 1 }-> g_4(z, z) :|: z >= 0
   f_5(z) -{ 1 }-> g_5(z, z) :|: z >= 0
   g_1(z, z') -{ 2*z }-> 1 + 0 + s' :|: s' >= 0, s' <= 0, z - 1 >= 0, z' >= 0
   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
   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
   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
   g_5(z, z') -{ 1 }-> 1 + f_4(z') + g_5(z - 1, z') :|: z - 1 >= 0, z' >= 0

Function symbols to be analyzed: {g_4}, {f_4}, {g_5}, {f_5}
Previous analysis results are:
  f_0: runtime: O(1) [1], size: O(1) [0]
  g_1: runtime: O(n^1) [2*z], size: O(1) [0]
  f_1: runtime: O(n^1) [1 + 2*z], size: O(1) [0]
  g_2: runtime: O(n^2) [2*z + 2*z*z'], size: O(1) [0]
  f_2: runtime: O(n^2) [1 + 2*z + 2*z^2], size: O(1) [0]
  g_3: runtime: O(n^3) [2*z + 2*z*z' + 2*z*z'^2], size: O(1) [0]
  f_3: runtime: O(n^3) [1 + 2*z + 2*z^2 + 2*z^3], size: O(1) [0]
  g_4: runtime: ?, size: O(1) [0]

----------------------------------------

(65) IntTrsBoundProof (UPPER BOUND(ID))

Computed RUNTIME bound using KoAT for: g_4
after applying outer abstraction to obtain an ITS,
resulting in: O(n^4) with polynomial bound: 2*z + 2*z*z' + 2*z*z'^2 + 2*z*z'^3

----------------------------------------

(66)
Obligation:
Complexity RNTS consisting of the following rules:

   f_0(z) -{ 1 }-> 0 :|: z >= 0
   f_1(z) -{ 1 + 2*z }-> s :|: s >= 0, s <= 0, z >= 0
   f_2(z) -{ 1 + 2*z + 2*z^2 }-> s1 :|: s1 >= 0, s1 <= 0, z >= 0
   f_3(z) -{ 1 + 2*z + 2*z^2 + 2*z^3 }-> s4 :|: s4 >= 0, s4 <= 0, z >= 0
   f_4(z) -{ 1 }-> g_4(z, z) :|: z >= 0
   f_5(z) -{ 1 }-> g_5(z, z) :|: z >= 0
   g_1(z, z') -{ 2*z }-> 1 + 0 + s' :|: s' >= 0, s' <= 0, z - 1 >= 0, z' >= 0
   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
   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
   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
   g_5(z, z') -{ 1 }-> 1 + f_4(z') + g_5(z - 1, z') :|: z - 1 >= 0, z' >= 0

Function symbols to be analyzed: {f_4}, {g_5}, {f_5}
Previous analysis results are:
  f_0: runtime: O(1) [1], size: O(1) [0]
  g_1: runtime: O(n^1) [2*z], size: O(1) [0]
  f_1: runtime: O(n^1) [1 + 2*z], size: O(1) [0]
  g_2: runtime: O(n^2) [2*z + 2*z*z'], size: O(1) [0]
  f_2: runtime: O(n^2) [1 + 2*z + 2*z^2], size: O(1) [0]
  g_3: runtime: O(n^3) [2*z + 2*z*z' + 2*z*z'^2], size: O(1) [0]
  f_3: runtime: O(n^3) [1 + 2*z + 2*z^2 + 2*z^3], size: O(1) [0]
  g_4: runtime: O(n^4) [2*z + 2*z*z' + 2*z*z'^2 + 2*z*z'^3], size: O(1) [0]

----------------------------------------

(67) ResultPropagationProof (UPPER BOUND(ID))
Applied inner abstraction using the recently inferred runtime/size bounds where possible.
----------------------------------------

(68)
Obligation:
Complexity RNTS consisting of the following rules:

   f_0(z) -{ 1 }-> 0 :|: z >= 0
   f_1(z) -{ 1 + 2*z }-> s :|: s >= 0, s <= 0, z >= 0
   f_2(z) -{ 1 + 2*z + 2*z^2 }-> s1 :|: s1 >= 0, s1 <= 0, z >= 0
   f_3(z) -{ 1 + 2*z + 2*z^2 + 2*z^3 }-> s4 :|: s4 >= 0, s4 <= 0, z >= 0
   f_4(z) -{ 1 + 2*z + 2*z^2 + 2*z^3 + 2*z^4 }-> s7 :|: s7 >= 0, s7 <= 0, z >= 0
   f_5(z) -{ 1 }-> g_5(z, z) :|: z >= 0
   g_1(z, z') -{ 2*z }-> 1 + 0 + s' :|: s' >= 0, s' <= 0, z - 1 >= 0, z' >= 0
   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
   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
   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
   g_5(z, z') -{ 1 }-> 1 + f_4(z') + g_5(z - 1, z') :|: z - 1 >= 0, z' >= 0

Function symbols to be analyzed: {f_4}, {g_5}, {f_5}
Previous analysis results are:
  f_0: runtime: O(1) [1], size: O(1) [0]
  g_1: runtime: O(n^1) [2*z], size: O(1) [0]
  f_1: runtime: O(n^1) [1 + 2*z], size: O(1) [0]
  g_2: runtime: O(n^2) [2*z + 2*z*z'], size: O(1) [0]
  f_2: runtime: O(n^2) [1 + 2*z + 2*z^2], size: O(1) [0]
  g_3: runtime: O(n^3) [2*z + 2*z*z' + 2*z*z'^2], size: O(1) [0]
  f_3: runtime: O(n^3) [1 + 2*z + 2*z^2 + 2*z^3], size: O(1) [0]
  g_4: runtime: O(n^4) [2*z + 2*z*z' + 2*z*z'^2 + 2*z*z'^3], size: O(1) [0]

----------------------------------------

(69) IntTrsBoundProof (UPPER BOUND(ID))

Computed SIZE bound using CoFloCo for: f_4
after applying outer abstraction to obtain an ITS,
resulting in: O(1) with polynomial bound: 0

----------------------------------------

(70)
Obligation:
Complexity RNTS consisting of the following rules:

   f_0(z) -{ 1 }-> 0 :|: z >= 0
   f_1(z) -{ 1 + 2*z }-> s :|: s >= 0, s <= 0, z >= 0
   f_2(z) -{ 1 + 2*z + 2*z^2 }-> s1 :|: s1 >= 0, s1 <= 0, z >= 0
   f_3(z) -{ 1 + 2*z + 2*z^2 + 2*z^3 }-> s4 :|: s4 >= 0, s4 <= 0, z >= 0
   f_4(z) -{ 1 + 2*z + 2*z^2 + 2*z^3 + 2*z^4 }-> s7 :|: s7 >= 0, s7 <= 0, z >= 0
   f_5(z) -{ 1 }-> g_5(z, z) :|: z >= 0
   g_1(z, z') -{ 2*z }-> 1 + 0 + s' :|: s' >= 0, s' <= 0, z - 1 >= 0, z' >= 0
   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
   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
   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
   g_5(z, z') -{ 1 }-> 1 + f_4(z') + g_5(z - 1, z') :|: z - 1 >= 0, z' >= 0

Function symbols to be analyzed: {f_4}, {g_5}, {f_5}
Previous analysis results are:
  f_0: runtime: O(1) [1], size: O(1) [0]
  g_1: runtime: O(n^1) [2*z], size: O(1) [0]
  f_1: runtime: O(n^1) [1 + 2*z], size: O(1) [0]
  g_2: runtime: O(n^2) [2*z + 2*z*z'], size: O(1) [0]
  f_2: runtime: O(n^2) [1 + 2*z + 2*z^2], size: O(1) [0]
  g_3: runtime: O(n^3) [2*z + 2*z*z' + 2*z*z'^2], size: O(1) [0]
  f_3: runtime: O(n^3) [1 + 2*z + 2*z^2 + 2*z^3], size: O(1) [0]
  g_4: runtime: O(n^4) [2*z + 2*z*z' + 2*z*z'^2 + 2*z*z'^3], size: O(1) [0]
  f_4: runtime: ?, size: O(1) [0]

----------------------------------------

(71) IntTrsBoundProof (UPPER BOUND(ID))

Computed RUNTIME bound using KoAT for: f_4
after applying outer abstraction to obtain an ITS,
resulting in: O(n^4) with polynomial bound: 1 + 2*z + 2*z^2 + 2*z^3 + 2*z^4

----------------------------------------

(72)
Obligation:
Complexity RNTS consisting of the following rules:

   f_0(z) -{ 1 }-> 0 :|: z >= 0
   f_1(z) -{ 1 + 2*z }-> s :|: s >= 0, s <= 0, z >= 0
   f_2(z) -{ 1 + 2*z + 2*z^2 }-> s1 :|: s1 >= 0, s1 <= 0, z >= 0
   f_3(z) -{ 1 + 2*z + 2*z^2 + 2*z^3 }-> s4 :|: s4 >= 0, s4 <= 0, z >= 0
   f_4(z) -{ 1 + 2*z + 2*z^2 + 2*z^3 + 2*z^4 }-> s7 :|: s7 >= 0, s7 <= 0, z >= 0
   f_5(z) -{ 1 }-> g_5(z, z) :|: z >= 0
   g_1(z, z') -{ 2*z }-> 1 + 0 + s' :|: s' >= 0, s' <= 0, z - 1 >= 0, z' >= 0
   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
   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
   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
   g_5(z, z') -{ 1 }-> 1 + f_4(z') + g_5(z - 1, z') :|: z - 1 >= 0, z' >= 0

Function symbols to be analyzed: {g_5}, {f_5}
Previous analysis results are:
  f_0: runtime: O(1) [1], size: O(1) [0]
  g_1: runtime: O(n^1) [2*z], size: O(1) [0]
  f_1: runtime: O(n^1) [1 + 2*z], size: O(1) [0]
  g_2: runtime: O(n^2) [2*z + 2*z*z'], size: O(1) [0]
  f_2: runtime: O(n^2) [1 + 2*z + 2*z^2], size: O(1) [0]
  g_3: runtime: O(n^3) [2*z + 2*z*z' + 2*z*z'^2], size: O(1) [0]
  f_3: runtime: O(n^3) [1 + 2*z + 2*z^2 + 2*z^3], size: O(1) [0]
  g_4: runtime: O(n^4) [2*z + 2*z*z' + 2*z*z'^2 + 2*z*z'^3], size: O(1) [0]
  f_4: runtime: O(n^4) [1 + 2*z + 2*z^2 + 2*z^3 + 2*z^4], size: O(1) [0]

----------------------------------------

(73) ResultPropagationProof (UPPER BOUND(ID))
Applied inner abstraction using the recently inferred runtime/size bounds where possible.
----------------------------------------

(74)
Obligation:
Complexity RNTS consisting of the following rules:

   f_0(z) -{ 1 }-> 0 :|: z >= 0
   f_1(z) -{ 1 + 2*z }-> s :|: s >= 0, s <= 0, z >= 0
   f_2(z) -{ 1 + 2*z + 2*z^2 }-> s1 :|: s1 >= 0, s1 <= 0, z >= 0
   f_3(z) -{ 1 + 2*z + 2*z^2 + 2*z^3 }-> s4 :|: s4 >= 0, s4 <= 0, z >= 0
   f_4(z) -{ 1 + 2*z + 2*z^2 + 2*z^3 + 2*z^4 }-> s7 :|: s7 >= 0, s7 <= 0, z >= 0
   f_5(z) -{ 1 }-> g_5(z, z) :|: z >= 0
   g_1(z, z') -{ 2*z }-> 1 + 0 + s' :|: s' >= 0, s' <= 0, z - 1 >= 0, z' >= 0
   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
   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
   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
   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

Function symbols to be analyzed: {g_5}, {f_5}
Previous analysis results are:
  f_0: runtime: O(1) [1], size: O(1) [0]
  g_1: runtime: O(n^1) [2*z], size: O(1) [0]
  f_1: runtime: O(n^1) [1 + 2*z], size: O(1) [0]
  g_2: runtime: O(n^2) [2*z + 2*z*z'], size: O(1) [0]
  f_2: runtime: O(n^2) [1 + 2*z + 2*z^2], size: O(1) [0]
  g_3: runtime: O(n^3) [2*z + 2*z*z' + 2*z*z'^2], size: O(1) [0]
  f_3: runtime: O(n^3) [1 + 2*z + 2*z^2 + 2*z^3], size: O(1) [0]
  g_4: runtime: O(n^4) [2*z + 2*z*z' + 2*z*z'^2 + 2*z*z'^3], size: O(1) [0]
  f_4: runtime: O(n^4) [1 + 2*z + 2*z^2 + 2*z^3 + 2*z^4], size: O(1) [0]

----------------------------------------

(75) IntTrsBoundProof (UPPER BOUND(ID))

Computed SIZE bound using CoFloCo for: g_5
after applying outer abstraction to obtain an ITS,
resulting in: O(1) with polynomial bound: 0

----------------------------------------

(76)
Obligation:
Complexity RNTS consisting of the following rules:

   f_0(z) -{ 1 }-> 0 :|: z >= 0
   f_1(z) -{ 1 + 2*z }-> s :|: s >= 0, s <= 0, z >= 0
   f_2(z) -{ 1 + 2*z + 2*z^2 }-> s1 :|: s1 >= 0, s1 <= 0, z >= 0
   f_3(z) -{ 1 + 2*z + 2*z^2 + 2*z^3 }-> s4 :|: s4 >= 0, s4 <= 0, z >= 0
   f_4(z) -{ 1 + 2*z + 2*z^2 + 2*z^3 + 2*z^4 }-> s7 :|: s7 >= 0, s7 <= 0, z >= 0
   f_5(z) -{ 1 }-> g_5(z, z) :|: z >= 0
   g_1(z, z') -{ 2*z }-> 1 + 0 + s' :|: s' >= 0, s' <= 0, z - 1 >= 0, z' >= 0
   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
   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
   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
   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

Function symbols to be analyzed: {g_5}, {f_5}
Previous analysis results are:
  f_0: runtime: O(1) [1], size: O(1) [0]
  g_1: runtime: O(n^1) [2*z], size: O(1) [0]
  f_1: runtime: O(n^1) [1 + 2*z], size: O(1) [0]
  g_2: runtime: O(n^2) [2*z + 2*z*z'], size: O(1) [0]
  f_2: runtime: O(n^2) [1 + 2*z + 2*z^2], size: O(1) [0]
  g_3: runtime: O(n^3) [2*z + 2*z*z' + 2*z*z'^2], size: O(1) [0]
  f_3: runtime: O(n^3) [1 + 2*z + 2*z^2 + 2*z^3], size: O(1) [0]
  g_4: runtime: O(n^4) [2*z + 2*z*z' + 2*z*z'^2 + 2*z*z'^3], size: O(1) [0]
  f_4: runtime: O(n^4) [1 + 2*z + 2*z^2 + 2*z^3 + 2*z^4], size: O(1) [0]
  g_5: runtime: ?, size: O(1) [0]

----------------------------------------

(77) IntTrsBoundProof (UPPER BOUND(ID))

Computed RUNTIME bound using KoAT for: g_5
after applying outer abstraction to obtain an ITS,
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

----------------------------------------

(78)
Obligation:
Complexity RNTS consisting of the following rules:

   f_0(z) -{ 1 }-> 0 :|: z >= 0
   f_1(z) -{ 1 + 2*z }-> s :|: s >= 0, s <= 0, z >= 0
   f_2(z) -{ 1 + 2*z + 2*z^2 }-> s1 :|: s1 >= 0, s1 <= 0, z >= 0
   f_3(z) -{ 1 + 2*z + 2*z^2 + 2*z^3 }-> s4 :|: s4 >= 0, s4 <= 0, z >= 0
   f_4(z) -{ 1 + 2*z + 2*z^2 + 2*z^3 + 2*z^4 }-> s7 :|: s7 >= 0, s7 <= 0, z >= 0
   f_5(z) -{ 1 }-> g_5(z, z) :|: z >= 0
   g_1(z, z') -{ 2*z }-> 1 + 0 + s' :|: s' >= 0, s' <= 0, z - 1 >= 0, z' >= 0
   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
   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
   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
   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

Function symbols to be analyzed: {f_5}
Previous analysis results are:
  f_0: runtime: O(1) [1], size: O(1) [0]
  g_1: runtime: O(n^1) [2*z], size: O(1) [0]
  f_1: runtime: O(n^1) [1 + 2*z], size: O(1) [0]
  g_2: runtime: O(n^2) [2*z + 2*z*z'], size: O(1) [0]
  f_2: runtime: O(n^2) [1 + 2*z + 2*z^2], size: O(1) [0]
  g_3: runtime: O(n^3) [2*z + 2*z*z' + 2*z*z'^2], size: O(1) [0]
  f_3: runtime: O(n^3) [1 + 2*z + 2*z^2 + 2*z^3], size: O(1) [0]
  g_4: runtime: O(n^4) [2*z + 2*z*z' + 2*z*z'^2 + 2*z*z'^3], size: O(1) [0]
  f_4: runtime: O(n^4) [1 + 2*z + 2*z^2 + 2*z^3 + 2*z^4], size: O(1) [0]
  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]

----------------------------------------

(79) ResultPropagationProof (UPPER BOUND(ID))
Applied inner abstraction using the recently inferred runtime/size bounds where possible.
----------------------------------------

(80)
Obligation:
Complexity RNTS consisting of the following rules:

   f_0(z) -{ 1 }-> 0 :|: z >= 0
   f_1(z) -{ 1 + 2*z }-> s :|: s >= 0, s <= 0, z >= 0
   f_2(z) -{ 1 + 2*z + 2*z^2 }-> s1 :|: s1 >= 0, s1 <= 0, z >= 0
   f_3(z) -{ 1 + 2*z + 2*z^2 + 2*z^3 }-> s4 :|: s4 >= 0, s4 <= 0, z >= 0
   f_4(z) -{ 1 + 2*z + 2*z^2 + 2*z^3 + 2*z^4 }-> s7 :|: s7 >= 0, s7 <= 0, z >= 0
   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
   g_1(z, z') -{ 2*z }-> 1 + 0 + s' :|: s' >= 0, s' <= 0, z - 1 >= 0, z' >= 0
   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
   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
   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
   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

Function symbols to be analyzed: {f_5}
Previous analysis results are:
  f_0: runtime: O(1) [1], size: O(1) [0]
  g_1: runtime: O(n^1) [2*z], size: O(1) [0]
  f_1: runtime: O(n^1) [1 + 2*z], size: O(1) [0]
  g_2: runtime: O(n^2) [2*z + 2*z*z'], size: O(1) [0]
  f_2: runtime: O(n^2) [1 + 2*z + 2*z^2], size: O(1) [0]
  g_3: runtime: O(n^3) [2*z + 2*z*z' + 2*z*z'^2], size: O(1) [0]
  f_3: runtime: O(n^3) [1 + 2*z + 2*z^2 + 2*z^3], size: O(1) [0]
  g_4: runtime: O(n^4) [2*z + 2*z*z' + 2*z*z'^2 + 2*z*z'^3], size: O(1) [0]
  f_4: runtime: O(n^4) [1 + 2*z + 2*z^2 + 2*z^3 + 2*z^4], size: O(1) [0]
  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]

----------------------------------------

(81) IntTrsBoundProof (UPPER BOUND(ID))

Computed SIZE bound using CoFloCo for: f_5
after applying outer abstraction to obtain an ITS,
resulting in: O(1) with polynomial bound: 0

----------------------------------------

(82)
Obligation:
Complexity RNTS consisting of the following rules:

   f_0(z) -{ 1 }-> 0 :|: z >= 0
   f_1(z) -{ 1 + 2*z }-> s :|: s >= 0, s <= 0, z >= 0
   f_2(z) -{ 1 + 2*z + 2*z^2 }-> s1 :|: s1 >= 0, s1 <= 0, z >= 0
   f_3(z) -{ 1 + 2*z + 2*z^2 + 2*z^3 }-> s4 :|: s4 >= 0, s4 <= 0, z >= 0
   f_4(z) -{ 1 + 2*z + 2*z^2 + 2*z^3 + 2*z^4 }-> s7 :|: s7 >= 0, s7 <= 0, z >= 0
   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
   g_1(z, z') -{ 2*z }-> 1 + 0 + s' :|: s' >= 0, s' <= 0, z - 1 >= 0, z' >= 0
   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
   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
   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
   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

Function symbols to be analyzed: {f_5}
Previous analysis results are:
  f_0: runtime: O(1) [1], size: O(1) [0]
  g_1: runtime: O(n^1) [2*z], size: O(1) [0]
  f_1: runtime: O(n^1) [1 + 2*z], size: O(1) [0]
  g_2: runtime: O(n^2) [2*z + 2*z*z'], size: O(1) [0]
  f_2: runtime: O(n^2) [1 + 2*z + 2*z^2], size: O(1) [0]
  g_3: runtime: O(n^3) [2*z + 2*z*z' + 2*z*z'^2], size: O(1) [0]
  f_3: runtime: O(n^3) [1 + 2*z + 2*z^2 + 2*z^3], size: O(1) [0]
  g_4: runtime: O(n^4) [2*z + 2*z*z' + 2*z*z'^2 + 2*z*z'^3], size: O(1) [0]
  f_4: runtime: O(n^4) [1 + 2*z + 2*z^2 + 2*z^3 + 2*z^4], size: O(1) [0]
  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]
  f_5: runtime: ?, size: O(1) [0]

----------------------------------------

(83) IntTrsBoundProof (UPPER BOUND(ID))

Computed RUNTIME bound using KoAT for: f_5
after applying outer abstraction to obtain an ITS,
resulting in: O(n^5) with polynomial bound: 1 + 2*z + 2*z^2 + 2*z^3 + 2*z^4 + 2*z^5

----------------------------------------

(84)
Obligation:
Complexity RNTS consisting of the following rules:

   f_0(z) -{ 1 }-> 0 :|: z >= 0
   f_1(z) -{ 1 + 2*z }-> s :|: s >= 0, s <= 0, z >= 0
   f_2(z) -{ 1 + 2*z + 2*z^2 }-> s1 :|: s1 >= 0, s1 <= 0, z >= 0
   f_3(z) -{ 1 + 2*z + 2*z^2 + 2*z^3 }-> s4 :|: s4 >= 0, s4 <= 0, z >= 0
   f_4(z) -{ 1 + 2*z + 2*z^2 + 2*z^3 + 2*z^4 }-> s7 :|: s7 >= 0, s7 <= 0, z >= 0
   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
   g_1(z, z') -{ 2*z }-> 1 + 0 + s' :|: s' >= 0, s' <= 0, z - 1 >= 0, z' >= 0
   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
   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
   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
   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

Function symbols to be analyzed: 
Previous analysis results are:
  f_0: runtime: O(1) [1], size: O(1) [0]
  g_1: runtime: O(n^1) [2*z], size: O(1) [0]
  f_1: runtime: O(n^1) [1 + 2*z], size: O(1) [0]
  g_2: runtime: O(n^2) [2*z + 2*z*z'], size: O(1) [0]
  f_2: runtime: O(n^2) [1 + 2*z + 2*z^2], size: O(1) [0]
  g_3: runtime: O(n^3) [2*z + 2*z*z' + 2*z*z'^2], size: O(1) [0]
  f_3: runtime: O(n^3) [1 + 2*z + 2*z^2 + 2*z^3], size: O(1) [0]
  g_4: runtime: O(n^4) [2*z + 2*z*z' + 2*z*z'^2 + 2*z*z'^3], size: O(1) [0]
  f_4: runtime: O(n^4) [1 + 2*z + 2*z^2 + 2*z^3 + 2*z^4], size: O(1) [0]
  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]
  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]

----------------------------------------

(85) FinalProof (FINISHED)
Computed overall runtime complexity
----------------------------------------

(86)
BOUNDS(1, n^5)

----------------------------------------

(87) RenamingProof (BOTH BOUNDS(ID, ID))
Renamed function symbols to avoid clashes with predefined symbol.
----------------------------------------

(88)
Obligation:
The Runtime Complexity (full) of the given CpxTRS could be proven to be BOUNDS(n^1, INF).


The TRS R consists of the following rules:

   f_0(x) -> a
   f_1(x) -> g_1(x, x)
   g_1(s(x), y) -> b(f_0(y), g_1(x, y))
   f_2(x) -> g_2(x, x)
   g_2(s(x), y) -> b(f_1(y), g_2(x, y))
   f_3(x) -> g_3(x, x)
   g_3(s(x), y) -> b(f_2(y), g_3(x, y))
   f_4(x) -> g_4(x, x)
   g_4(s(x), y) -> b(f_3(y), g_4(x, y))
   f_5(x) -> g_5(x, x)
   g_5(s(x), y) -> b(f_4(y), g_5(x, y))

S is empty.
Rewrite Strategy: FULL
----------------------------------------

(89) SlicingProof (LOWER BOUND(ID))
Sliced the following arguments:
f_0/0
g_1/1

----------------------------------------

(90)
Obligation:
The Runtime Complexity (full) of the given CpxTRS could be proven to be BOUNDS(n^1, INF).


The TRS R consists of the following rules:

   f_0 -> a
   f_1(x) -> g_1(x)
   g_1(s(x)) -> b(f_0, g_1(x))
   f_2(x) -> g_2(x, x)
   g_2(s(x), y) -> b(f_1(y), g_2(x, y))
   f_3(x) -> g_3(x, x)
   g_3(s(x), y) -> b(f_2(y), g_3(x, y))
   f_4(x) -> g_4(x, x)
   g_4(s(x), y) -> b(f_3(y), g_4(x, y))
   f_5(x) -> g_5(x, x)
   g_5(s(x), y) -> b(f_4(y), g_5(x, y))

S is empty.
Rewrite Strategy: FULL
----------------------------------------

(91) TypeInferenceProof (BOTH BOUNDS(ID, ID))
Infered types.
----------------------------------------

(92)
Obligation:
TRS:
Rules:
f_0 -> a
f_1(x) -> g_1(x)
g_1(s(x)) -> b(f_0, g_1(x))
f_2(x) -> g_2(x, x)
g_2(s(x), y) -> b(f_1(y), g_2(x, y))
f_3(x) -> g_3(x, x)
g_3(s(x), y) -> b(f_2(y), g_3(x, y))
f_4(x) -> g_4(x, x)
g_4(s(x), y) -> b(f_3(y), g_4(x, y))
f_5(x) -> g_5(x, x)
g_5(s(x), y) -> b(f_4(y), g_5(x, y))

Types:
f_0 :: a:b
a :: a:b
f_1 :: s -> a:b
g_1 :: s -> a:b
s :: s -> s
b :: a:b -> a:b -> a:b
f_2 :: s -> a:b
g_2 :: s -> s -> a:b
f_3 :: s -> a:b
g_3 :: s -> s -> a:b
f_4 :: s -> a:b
g_4 :: s -> s -> a:b
f_5 :: s -> a:b
g_5 :: s -> s -> a:b
hole_a:b1_6 :: a:b
hole_s2_6 :: s
gen_a:b3_6 :: Nat -> a:b
gen_s4_6 :: Nat -> s

----------------------------------------

(93) OrderProof (LOWER BOUND(ID))
Heuristically decided to analyse the following defined symbols:
g_1, g_2, g_3, g_4, g_5
----------------------------------------

(94)
Obligation:
TRS:
Rules:
f_0 -> a
f_1(x) -> g_1(x)
g_1(s(x)) -> b(f_0, g_1(x))
f_2(x) -> g_2(x, x)
g_2(s(x), y) -> b(f_1(y), g_2(x, y))
f_3(x) -> g_3(x, x)
g_3(s(x), y) -> b(f_2(y), g_3(x, y))
f_4(x) -> g_4(x, x)
g_4(s(x), y) -> b(f_3(y), g_4(x, y))
f_5(x) -> g_5(x, x)
g_5(s(x), y) -> b(f_4(y), g_5(x, y))

Types:
f_0 :: a:b
a :: a:b
f_1 :: s -> a:b
g_1 :: s -> a:b
s :: s -> s
b :: a:b -> a:b -> a:b
f_2 :: s -> a:b
g_2 :: s -> s -> a:b
f_3 :: s -> a:b
g_3 :: s -> s -> a:b
f_4 :: s -> a:b
g_4 :: s -> s -> a:b
f_5 :: s -> a:b
g_5 :: s -> s -> a:b
hole_a:b1_6 :: a:b
hole_s2_6 :: s
gen_a:b3_6 :: Nat -> a:b
gen_s4_6 :: Nat -> s


Generator Equations:
gen_a:b3_6(0) <=> a
gen_a:b3_6(+(x, 1)) <=> b(a, gen_a:b3_6(x))
gen_s4_6(0) <=> hole_s2_6
gen_s4_6(+(x, 1)) <=> s(gen_s4_6(x))


The following defined symbols remain to be analysed:
g_1, g_2, g_3, g_4, g_5
----------------------------------------

(95) RewriteLemmaProof (LOWER BOUND(ID))
Proved the following rewrite lemma:
g_1(gen_s4_6(+(1, n6_6))) -> *5_6, rt in Omega(n6_6)

Induction Base:
g_1(gen_s4_6(+(1, 0)))

Induction Step:
g_1(gen_s4_6(+(1, +(n6_6, 1)))) ->_R^Omega(1)
b(f_0, g_1(gen_s4_6(+(1, n6_6)))) ->_R^Omega(1)
b(a, g_1(gen_s4_6(+(1, n6_6)))) ->_IH
b(a, *5_6)

We have rt in Omega(n^1) and sz in O(n). Thus, we have irc_R in Omega(n).
----------------------------------------

(96)
Complex Obligation (BEST)

----------------------------------------

(97)
Obligation:
Proved the lower bound n^1 for the following obligation:

TRS:
Rules:
f_0 -> a
f_1(x) -> g_1(x)
g_1(s(x)) -> b(f_0, g_1(x))
f_2(x) -> g_2(x, x)
g_2(s(x), y) -> b(f_1(y), g_2(x, y))
f_3(x) -> g_3(x, x)
g_3(s(x), y) -> b(f_2(y), g_3(x, y))
f_4(x) -> g_4(x, x)
g_4(s(x), y) -> b(f_3(y), g_4(x, y))
f_5(x) -> g_5(x, x)
g_5(s(x), y) -> b(f_4(y), g_5(x, y))

Types:
f_0 :: a:b
a :: a:b
f_1 :: s -> a:b
g_1 :: s -> a:b
s :: s -> s
b :: a:b -> a:b -> a:b
f_2 :: s -> a:b
g_2 :: s -> s -> a:b
f_3 :: s -> a:b
g_3 :: s -> s -> a:b
f_4 :: s -> a:b
g_4 :: s -> s -> a:b
f_5 :: s -> a:b
g_5 :: s -> s -> a:b
hole_a:b1_6 :: a:b
hole_s2_6 :: s
gen_a:b3_6 :: Nat -> a:b
gen_s4_6 :: Nat -> s


Generator Equations:
gen_a:b3_6(0) <=> a
gen_a:b3_6(+(x, 1)) <=> b(a, gen_a:b3_6(x))
gen_s4_6(0) <=> hole_s2_6
gen_s4_6(+(x, 1)) <=> s(gen_s4_6(x))


The following defined symbols remain to be analysed:
g_1, g_2, g_3, g_4, g_5
----------------------------------------

(98) LowerBoundPropagationProof (FINISHED)
Propagated lower bound.
----------------------------------------

(99)
BOUNDS(n^1, INF)

----------------------------------------

(100)
Obligation:
TRS:
Rules:
f_0 -> a
f_1(x) -> g_1(x)
g_1(s(x)) -> b(f_0, g_1(x))
f_2(x) -> g_2(x, x)
g_2(s(x), y) -> b(f_1(y), g_2(x, y))
f_3(x) -> g_3(x, x)
g_3(s(x), y) -> b(f_2(y), g_3(x, y))
f_4(x) -> g_4(x, x)
g_4(s(x), y) -> b(f_3(y), g_4(x, y))
f_5(x) -> g_5(x, x)
g_5(s(x), y) -> b(f_4(y), g_5(x, y))

Types:
f_0 :: a:b
a :: a:b
f_1 :: s -> a:b
g_1 :: s -> a:b
s :: s -> s
b :: a:b -> a:b -> a:b
f_2 :: s -> a:b
g_2 :: s -> s -> a:b
f_3 :: s -> a:b
g_3 :: s -> s -> a:b
f_4 :: s -> a:b
g_4 :: s -> s -> a:b
f_5 :: s -> a:b
g_5 :: s -> s -> a:b
hole_a:b1_6 :: a:b
hole_s2_6 :: s
gen_a:b3_6 :: Nat -> a:b
gen_s4_6 :: Nat -> s


Lemmas:
g_1(gen_s4_6(+(1, n6_6))) -> *5_6, rt in Omega(n6_6)


Generator Equations:
gen_a:b3_6(0) <=> a
gen_a:b3_6(+(x, 1)) <=> b(a, gen_a:b3_6(x))
gen_s4_6(0) <=> hole_s2_6
gen_s4_6(+(x, 1)) <=> s(gen_s4_6(x))


The following defined symbols remain to be analysed:
g_2, g_3, g_4, g_5