/export/starexec/sandbox/solver/bin/starexec_run_rcdcRelativeAlsoLower /export/starexec/sandbox/benchmark/theBenchmark.xml /export/starexec/sandbox/output/output_files -------------------------------------------------------------------------------- WORST_CASE(?, O(n^1)) proof of /export/starexec/sandbox/benchmark/theBenchmark.xml # AProVE Commit ID: 794c25de1cacf0d048858bcd21c9a779e1221865 marcel 20200619 unpublished dirty The Derivational Complexity (innermost) of the given DCpxTrs could be proven to be BOUNDS(1, n^1). (0) DCpxTrs (1) DerivationalComplexityToRuntimeComplexityProof [BOTH BOUNDS(ID, ID), 0 ms] (2) CpxRelTRS (3) SInnermostTerminationProof [BOTH CONCRETE BOUNDS(ID, ID), 152 ms] (4) CpxRelTRS (5) RelTrsToWeightedTrsProof [BOTH BOUNDS(ID, ID), 0 ms] (6) CpxWeightedTrs (7) TypeInferenceProof [BOTH BOUNDS(ID, ID), 0 ms] (8) CpxTypedWeightedTrs (9) CompletionProof [UPPER BOUND(ID), 0 ms] (10) CpxTypedWeightedCompleteTrs (11) NarrowingProof [BOTH BOUNDS(ID, ID), 0 ms] (12) CpxTypedWeightedCompleteTrs (13) CpxTypedWeightedTrsToRntsProof [UPPER BOUND(ID), 10 ms] (14) CpxRNTS (15) InliningProof [UPPER BOUND(ID), 71 ms] (16) CpxRNTS (17) SimplificationProof [BOTH BOUNDS(ID, ID), 5 ms] (18) CpxRNTS (19) CpxRntsAnalysisOrderProof [BOTH BOUNDS(ID, ID), 0 ms] (20) CpxRNTS (21) ResultPropagationProof [UPPER BOUND(ID), 0 ms] (22) CpxRNTS (23) IntTrsBoundProof [UPPER BOUND(ID), 114 ms] (24) CpxRNTS (25) IntTrsBoundProof [UPPER BOUND(ID), 4 ms] (26) CpxRNTS (27) ResultPropagationProof [UPPER BOUND(ID), 0 ms] (28) CpxRNTS (29) IntTrsBoundProof [UPPER BOUND(ID), 168 ms] (30) CpxRNTS (31) IntTrsBoundProof [UPPER BOUND(ID), 63 ms] (32) CpxRNTS (33) ResultPropagationProof [UPPER BOUND(ID), 0 ms] (34) CpxRNTS (35) IntTrsBoundProof [UPPER BOUND(ID), 720 ms] (36) CpxRNTS (37) IntTrsBoundProof [UPPER BOUND(ID), 1261 ms] (38) CpxRNTS (39) ResultPropagationProof [UPPER BOUND(ID), 0 ms] (40) CpxRNTS (41) IntTrsBoundProof [UPPER BOUND(ID), 944 ms] (42) CpxRNTS (43) IntTrsBoundProof [UPPER BOUND(ID), 593 ms] (44) CpxRNTS (45) ResultPropagationProof [UPPER BOUND(ID), 0 ms] (46) CpxRNTS (47) IntTrsBoundProof [UPPER BOUND(ID), 300 ms] (48) CpxRNTS (49) IntTrsBoundProof [UPPER BOUND(ID), 115 ms] (50) CpxRNTS (51) ResultPropagationProof [UPPER BOUND(ID), 0 ms] (52) CpxRNTS (53) IntTrsBoundProof [UPPER BOUND(ID), 136 ms] (54) CpxRNTS (55) IntTrsBoundProof [UPPER BOUND(ID), 52 ms] (56) CpxRNTS (57) FinalProof [FINISHED, 0 ms] (58) BOUNDS(1, n^1) ---------------------------------------- (0) Obligation: The Derivational Complexity (innermost) of the given DCpxTrs could be proven to be BOUNDS(1, n^1). The TRS R consists of the following rules: f(x, x) -> f(g(x), x) g(x) -> s(x) S is empty. Rewrite Strategy: INNERMOST ---------------------------------------- (1) DerivationalComplexityToRuntimeComplexityProof (BOTH BOUNDS(ID, ID)) The following rules have been added to S to convert the given derivational complexity problem to a runtime complexity problem: encArg(s(x_1)) -> s(encArg(x_1)) encArg(cons_f(x_1, x_2)) -> f(encArg(x_1), encArg(x_2)) encArg(cons_g(x_1)) -> g(encArg(x_1)) encode_f(x_1, x_2) -> f(encArg(x_1), encArg(x_2)) encode_g(x_1) -> g(encArg(x_1)) encode_s(x_1) -> s(encArg(x_1)) ---------------------------------------- (2) Obligation: The Runtime Complexity (innermost) of the given CpxRelTRS could be proven to be BOUNDS(1, n^1). The TRS R consists of the following rules: f(x, x) -> f(g(x), x) g(x) -> s(x) The (relative) TRS S consists of the following rules: encArg(s(x_1)) -> s(encArg(x_1)) encArg(cons_f(x_1, x_2)) -> f(encArg(x_1), encArg(x_2)) encArg(cons_g(x_1)) -> g(encArg(x_1)) encode_f(x_1, x_2) -> f(encArg(x_1), encArg(x_2)) encode_g(x_1) -> g(encArg(x_1)) encode_s(x_1) -> s(encArg(x_1)) Rewrite Strategy: INNERMOST ---------------------------------------- (3) SInnermostTerminationProof (BOTH CONCRETE BOUNDS(ID, ID)) proved innermost termination of relative rules ---------------------------------------- (4) Obligation: The Runtime Complexity (innermost) of the given CpxRelTRS could be proven to be BOUNDS(1, n^1). The TRS R consists of the following rules: f(x, x) -> f(g(x), x) g(x) -> s(x) The (relative) TRS S consists of the following rules: encArg(s(x_1)) -> s(encArg(x_1)) encArg(cons_f(x_1, x_2)) -> f(encArg(x_1), encArg(x_2)) encArg(cons_g(x_1)) -> g(encArg(x_1)) encode_f(x_1, x_2) -> f(encArg(x_1), encArg(x_2)) encode_g(x_1) -> g(encArg(x_1)) encode_s(x_1) -> s(encArg(x_1)) Rewrite Strategy: INNERMOST ---------------------------------------- (5) RelTrsToWeightedTrsProof (BOTH BOUNDS(ID, ID)) Transformed relative TRS to weighted TRS ---------------------------------------- (6) Obligation: The Runtime Complexity (innermost) of the given CpxWeightedTrs could be proven to be BOUNDS(1, n^1). The TRS R consists of the following rules: f(x, x) -> f(g(x), x) [1] g(x) -> s(x) [1] encArg(s(x_1)) -> s(encArg(x_1)) [0] encArg(cons_f(x_1, x_2)) -> f(encArg(x_1), encArg(x_2)) [0] encArg(cons_g(x_1)) -> g(encArg(x_1)) [0] encode_f(x_1, x_2) -> f(encArg(x_1), encArg(x_2)) [0] encode_g(x_1) -> g(encArg(x_1)) [0] encode_s(x_1) -> s(encArg(x_1)) [0] Rewrite Strategy: INNERMOST ---------------------------------------- (7) TypeInferenceProof (BOTH BOUNDS(ID, ID)) Infered types. ---------------------------------------- (8) Obligation: Runtime Complexity Weighted TRS with Types. The TRS R consists of the following rules: f(x, x) -> f(g(x), x) [1] g(x) -> s(x) [1] encArg(s(x_1)) -> s(encArg(x_1)) [0] encArg(cons_f(x_1, x_2)) -> f(encArg(x_1), encArg(x_2)) [0] encArg(cons_g(x_1)) -> g(encArg(x_1)) [0] encode_f(x_1, x_2) -> f(encArg(x_1), encArg(x_2)) [0] encode_g(x_1) -> g(encArg(x_1)) [0] encode_s(x_1) -> s(encArg(x_1)) [0] The TRS has the following type information: f :: s:cons_f:cons_g -> s:cons_f:cons_g -> s:cons_f:cons_g g :: s:cons_f:cons_g -> s:cons_f:cons_g s :: s:cons_f:cons_g -> s:cons_f:cons_g encArg :: s:cons_f:cons_g -> s:cons_f:cons_g cons_f :: s:cons_f:cons_g -> s:cons_f:cons_g -> s:cons_f:cons_g cons_g :: s:cons_f:cons_g -> s:cons_f:cons_g encode_f :: s:cons_f:cons_g -> s:cons_f:cons_g -> s:cons_f:cons_g encode_g :: s:cons_f:cons_g -> s:cons_f:cons_g encode_s :: s:cons_f:cons_g -> s:cons_f:cons_g Rewrite Strategy: INNERMOST ---------------------------------------- (9) 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: none (c) The following functions are completely defined: g_1 f_2 encArg_1 encode_f_2 encode_g_1 encode_s_1 Due to the following rules being added: encArg(v0) -> const [0] encode_f(v0, v1) -> const [0] encode_g(v0) -> const [0] encode_s(v0) -> const [0] f(v0, v1) -> const [0] And the following fresh constants: const ---------------------------------------- (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(x, x) -> f(g(x), x) [1] g(x) -> s(x) [1] encArg(s(x_1)) -> s(encArg(x_1)) [0] encArg(cons_f(x_1, x_2)) -> f(encArg(x_1), encArg(x_2)) [0] encArg(cons_g(x_1)) -> g(encArg(x_1)) [0] encode_f(x_1, x_2) -> f(encArg(x_1), encArg(x_2)) [0] encode_g(x_1) -> g(encArg(x_1)) [0] encode_s(x_1) -> s(encArg(x_1)) [0] encArg(v0) -> const [0] encode_f(v0, v1) -> const [0] encode_g(v0) -> const [0] encode_s(v0) -> const [0] f(v0, v1) -> const [0] The TRS has the following type information: f :: s:cons_f:cons_g:const -> s:cons_f:cons_g:const -> s:cons_f:cons_g:const g :: s:cons_f:cons_g:const -> s:cons_f:cons_g:const s :: s:cons_f:cons_g:const -> s:cons_f:cons_g:const encArg :: s:cons_f:cons_g:const -> s:cons_f:cons_g:const cons_f :: s:cons_f:cons_g:const -> s:cons_f:cons_g:const -> s:cons_f:cons_g:const cons_g :: s:cons_f:cons_g:const -> s:cons_f:cons_g:const encode_f :: s:cons_f:cons_g:const -> s:cons_f:cons_g:const -> s:cons_f:cons_g:const encode_g :: s:cons_f:cons_g:const -> s:cons_f:cons_g:const encode_s :: s:cons_f:cons_g:const -> s:cons_f:cons_g:const const :: s:cons_f:cons_g:const Rewrite Strategy: INNERMOST ---------------------------------------- (11) NarrowingProof (BOTH BOUNDS(ID, ID)) Narrowed the inner basic terms of all right-hand sides by a single narrowing step. ---------------------------------------- (12) 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(x, x) -> f(s(x), x) [2] g(x) -> s(x) [1] encArg(s(x_1)) -> s(encArg(x_1)) [0] encArg(cons_f(s(x_1'), s(x_12))) -> f(s(encArg(x_1')), s(encArg(x_12))) [0] encArg(cons_f(s(x_1'), cons_f(x_13, x_2''))) -> f(s(encArg(x_1')), f(encArg(x_13), encArg(x_2''))) [0] encArg(cons_f(s(x_1'), cons_g(x_14))) -> f(s(encArg(x_1')), g(encArg(x_14))) [0] encArg(cons_f(s(x_1'), x_2)) -> f(s(encArg(x_1')), const) [0] encArg(cons_f(cons_f(x_1'', x_2'), s(x_15))) -> f(f(encArg(x_1''), encArg(x_2')), s(encArg(x_15))) [0] encArg(cons_f(cons_f(x_1'', x_2'), cons_f(x_16, x_21))) -> f(f(encArg(x_1''), encArg(x_2')), f(encArg(x_16), encArg(x_21))) [0] encArg(cons_f(cons_f(x_1'', x_2'), cons_g(x_17))) -> f(f(encArg(x_1''), encArg(x_2')), g(encArg(x_17))) [0] encArg(cons_f(cons_f(x_1'', x_2'), x_2)) -> f(f(encArg(x_1''), encArg(x_2')), const) [0] encArg(cons_f(cons_g(x_11), s(x_18))) -> f(g(encArg(x_11)), s(encArg(x_18))) [0] encArg(cons_f(cons_g(x_11), cons_f(x_19, x_22))) -> f(g(encArg(x_11)), f(encArg(x_19), encArg(x_22))) [0] encArg(cons_f(cons_g(x_11), cons_g(x_110))) -> f(g(encArg(x_11)), g(encArg(x_110))) [0] encArg(cons_f(cons_g(x_11), x_2)) -> f(g(encArg(x_11)), const) [0] encArg(cons_f(x_1, s(x_111))) -> f(const, s(encArg(x_111))) [0] encArg(cons_f(x_1, cons_f(x_112, x_23))) -> f(const, f(encArg(x_112), encArg(x_23))) [0] encArg(cons_f(x_1, cons_g(x_113))) -> f(const, g(encArg(x_113))) [0] encArg(cons_f(x_1, x_2)) -> f(const, const) [0] encArg(cons_g(s(x_114))) -> g(s(encArg(x_114))) [0] encArg(cons_g(cons_f(x_115, x_24))) -> g(f(encArg(x_115), encArg(x_24))) [0] encArg(cons_g(cons_g(x_116))) -> g(g(encArg(x_116))) [0] encArg(cons_g(x_1)) -> g(const) [0] encode_f(s(x_117), s(x_120)) -> f(s(encArg(x_117)), s(encArg(x_120))) [0] encode_f(s(x_117), cons_f(x_121, x_26)) -> f(s(encArg(x_117)), f(encArg(x_121), encArg(x_26))) [0] encode_f(s(x_117), cons_g(x_122)) -> f(s(encArg(x_117)), g(encArg(x_122))) [0] encode_f(s(x_117), x_2) -> f(s(encArg(x_117)), const) [0] encode_f(cons_f(x_118, x_25), s(x_123)) -> f(f(encArg(x_118), encArg(x_25)), s(encArg(x_123))) [0] encode_f(cons_f(x_118, x_25), cons_f(x_124, x_27)) -> f(f(encArg(x_118), encArg(x_25)), f(encArg(x_124), encArg(x_27))) [0] encode_f(cons_f(x_118, x_25), cons_g(x_125)) -> f(f(encArg(x_118), encArg(x_25)), g(encArg(x_125))) [0] encode_f(cons_f(x_118, x_25), x_2) -> f(f(encArg(x_118), encArg(x_25)), const) [0] encode_f(cons_g(x_119), s(x_126)) -> f(g(encArg(x_119)), s(encArg(x_126))) [0] encode_f(cons_g(x_119), cons_f(x_127, x_28)) -> f(g(encArg(x_119)), f(encArg(x_127), encArg(x_28))) [0] encode_f(cons_g(x_119), cons_g(x_128)) -> f(g(encArg(x_119)), g(encArg(x_128))) [0] encode_f(cons_g(x_119), x_2) -> f(g(encArg(x_119)), const) [0] encode_f(x_1, s(x_129)) -> f(const, s(encArg(x_129))) [0] encode_f(x_1, cons_f(x_130, x_29)) -> f(const, f(encArg(x_130), encArg(x_29))) [0] encode_f(x_1, cons_g(x_131)) -> f(const, g(encArg(x_131))) [0] encode_f(x_1, x_2) -> f(const, const) [0] encode_g(s(x_132)) -> g(s(encArg(x_132))) [0] encode_g(cons_f(x_133, x_210)) -> g(f(encArg(x_133), encArg(x_210))) [0] encode_g(cons_g(x_134)) -> g(g(encArg(x_134))) [0] encode_g(x_1) -> g(const) [0] encode_s(x_1) -> s(encArg(x_1)) [0] encArg(v0) -> const [0] encode_f(v0, v1) -> const [0] encode_g(v0) -> const [0] encode_s(v0) -> const [0] f(v0, v1) -> const [0] The TRS has the following type information: f :: s:cons_f:cons_g:const -> s:cons_f:cons_g:const -> s:cons_f:cons_g:const g :: s:cons_f:cons_g:const -> s:cons_f:cons_g:const s :: s:cons_f:cons_g:const -> s:cons_f:cons_g:const encArg :: s:cons_f:cons_g:const -> s:cons_f:cons_g:const cons_f :: s:cons_f:cons_g:const -> s:cons_f:cons_g:const -> s:cons_f:cons_g:const cons_g :: s:cons_f:cons_g:const -> s:cons_f:cons_g:const encode_f :: s:cons_f:cons_g:const -> s:cons_f:cons_g:const -> s:cons_f:cons_g:const encode_g :: s:cons_f:cons_g:const -> s:cons_f:cons_g:const encode_s :: s:cons_f:cons_g:const -> s:cons_f:cons_g:const const :: s:cons_f:cons_g:const Rewrite Strategy: INNERMOST ---------------------------------------- (13) CpxTypedWeightedTrsToRntsProof (UPPER BOUND(ID)) Transformed the TRS into an over-approximating RNTS by (improved) Size Abstraction. The constant constructors are abstracted as follows: const => 0 ---------------------------------------- (14) Obligation: Complexity RNTS consisting of the following rules: encArg(z) -{ 0 }-> g(g(encArg(x_116))) :|: z = 1 + (1 + x_116), x_116 >= 0 encArg(z) -{ 0 }-> g(f(encArg(x_115), encArg(x_24))) :|: z = 1 + (1 + x_115 + x_24), x_115 >= 0, x_24 >= 0 encArg(z) -{ 0 }-> g(0) :|: z = 1 + x_1, x_1 >= 0 encArg(z) -{ 0 }-> g(1 + encArg(x_114)) :|: z = 1 + (1 + x_114), x_114 >= 0 encArg(z) -{ 0 }-> f(g(encArg(x_11)), g(encArg(x_110))) :|: x_11 >= 0, z = 1 + (1 + x_11) + (1 + x_110), x_110 >= 0 encArg(z) -{ 0 }-> f(g(encArg(x_11)), f(encArg(x_19), encArg(x_22))) :|: x_11 >= 0, z = 1 + (1 + x_11) + (1 + x_19 + x_22), x_22 >= 0, x_19 >= 0 encArg(z) -{ 0 }-> f(g(encArg(x_11)), 0) :|: x_11 >= 0, z = 1 + (1 + x_11) + x_2, x_2 >= 0 encArg(z) -{ 0 }-> f(g(encArg(x_11)), 1 + encArg(x_18)) :|: x_11 >= 0, z = 1 + (1 + x_11) + (1 + x_18), x_18 >= 0 encArg(z) -{ 0 }-> f(f(encArg(x_1''), encArg(x_2')), g(encArg(x_17))) :|: x_1'' >= 0, z = 1 + (1 + x_1'' + x_2') + (1 + x_17), x_2' >= 0, x_17 >= 0 encArg(z) -{ 0 }-> f(f(encArg(x_1''), encArg(x_2')), f(encArg(x_16), encArg(x_21))) :|: x_1'' >= 0, x_16 >= 0, x_2' >= 0, z = 1 + (1 + x_1'' + x_2') + (1 + x_16 + x_21), x_21 >= 0 encArg(z) -{ 0 }-> f(f(encArg(x_1''), encArg(x_2')), 0) :|: x_1'' >= 0, x_2' >= 0, z = 1 + (1 + x_1'' + x_2') + x_2, x_2 >= 0 encArg(z) -{ 0 }-> f(f(encArg(x_1''), encArg(x_2')), 1 + encArg(x_15)) :|: x_15 >= 0, z = 1 + (1 + x_1'' + x_2') + (1 + x_15), x_1'' >= 0, x_2' >= 0 encArg(z) -{ 0 }-> f(0, g(encArg(x_113))) :|: x_1 >= 0, x_113 >= 0, z = 1 + x_1 + (1 + x_113) encArg(z) -{ 0 }-> f(0, f(encArg(x_112), encArg(x_23))) :|: x_1 >= 0, z = 1 + x_1 + (1 + x_112 + x_23), x_23 >= 0, x_112 >= 0 encArg(z) -{ 0 }-> f(0, 0) :|: x_1 >= 0, z = 1 + x_1 + x_2, x_2 >= 0 encArg(z) -{ 0 }-> f(0, 1 + encArg(x_111)) :|: x_1 >= 0, z = 1 + x_1 + (1 + x_111), x_111 >= 0 encArg(z) -{ 0 }-> f(1 + encArg(x_1'), g(encArg(x_14))) :|: z = 1 + (1 + x_1') + (1 + x_14), x_14 >= 0, x_1' >= 0 encArg(z) -{ 0 }-> f(1 + encArg(x_1'), f(encArg(x_13), encArg(x_2''))) :|: x_13 >= 0, x_1' >= 0, x_2'' >= 0, z = 1 + (1 + x_1') + (1 + x_13 + x_2'') encArg(z) -{ 0 }-> f(1 + encArg(x_1'), 0) :|: x_1' >= 0, x_2 >= 0, z = 1 + (1 + x_1') + x_2 encArg(z) -{ 0 }-> f(1 + encArg(x_1'), 1 + encArg(x_12)) :|: z = 1 + (1 + x_1') + (1 + x_12), x_1' >= 0, x_12 >= 0 encArg(z) -{ 0 }-> 0 :|: v0 >= 0, z = v0 encArg(z) -{ 0 }-> 1 + encArg(x_1) :|: z = 1 + x_1, x_1 >= 0 encode_f(z, z') -{ 0 }-> f(g(encArg(x_119)), g(encArg(x_128))) :|: x_128 >= 0, z' = 1 + x_128, z = 1 + x_119, x_119 >= 0 encode_f(z, z') -{ 0 }-> f(g(encArg(x_119)), f(encArg(x_127), encArg(x_28))) :|: x_127 >= 0, z' = 1 + x_127 + x_28, z = 1 + x_119, x_28 >= 0, x_119 >= 0 encode_f(z, z') -{ 0 }-> f(g(encArg(x_119)), 0) :|: z = 1 + x_119, x_2 >= 0, z' = x_2, x_119 >= 0 encode_f(z, z') -{ 0 }-> f(g(encArg(x_119)), 1 + encArg(x_126)) :|: z' = 1 + x_126, x_126 >= 0, z = 1 + x_119, x_119 >= 0 encode_f(z, z') -{ 0 }-> f(f(encArg(x_118), encArg(x_25)), g(encArg(x_125))) :|: z' = 1 + x_125, x_25 >= 0, z = 1 + x_118 + x_25, x_125 >= 0, x_118 >= 0 encode_f(z, z') -{ 0 }-> f(f(encArg(x_118), encArg(x_25)), f(encArg(x_124), encArg(x_27))) :|: x_124 >= 0, x_25 >= 0, z = 1 + x_118 + x_25, x_27 >= 0, x_118 >= 0, z' = 1 + x_124 + x_27 encode_f(z, z') -{ 0 }-> f(f(encArg(x_118), encArg(x_25)), 0) :|: x_25 >= 0, z = 1 + x_118 + x_25, x_2 >= 0, z' = x_2, x_118 >= 0 encode_f(z, z') -{ 0 }-> f(f(encArg(x_118), encArg(x_25)), 1 + encArg(x_123)) :|: z' = 1 + x_123, x_123 >= 0, x_25 >= 0, z = 1 + x_118 + x_25, x_118 >= 0 encode_f(z, z') -{ 0 }-> f(0, g(encArg(x_131))) :|: x_1 >= 0, z' = 1 + x_131, z = x_1, x_131 >= 0 encode_f(z, z') -{ 0 }-> f(0, f(encArg(x_130), encArg(x_29))) :|: x_1 >= 0, x_130 >= 0, z' = 1 + x_130 + x_29, z = x_1, x_29 >= 0 encode_f(z, z') -{ 0 }-> f(0, 0) :|: x_1 >= 0, x_2 >= 0, z = x_1, z' = x_2 encode_f(z, z') -{ 0 }-> f(0, 1 + encArg(x_129)) :|: x_1 >= 0, z' = 1 + x_129, z = x_1, x_129 >= 0 encode_f(z, z') -{ 0 }-> f(1 + encArg(x_117), g(encArg(x_122))) :|: z' = 1 + x_122, x_117 >= 0, x_122 >= 0, z = 1 + x_117 encode_f(z, z') -{ 0 }-> f(1 + encArg(x_117), f(encArg(x_121), encArg(x_26))) :|: x_117 >= 0, x_26 >= 0, z' = 1 + x_121 + x_26, z = 1 + x_117, x_121 >= 0 encode_f(z, z') -{ 0 }-> f(1 + encArg(x_117), 0) :|: x_117 >= 0, x_2 >= 0, z' = x_2, z = 1 + x_117 encode_f(z, z') -{ 0 }-> f(1 + encArg(x_117), 1 + encArg(x_120)) :|: x_120 >= 0, x_117 >= 0, z' = 1 + x_120, z = 1 + x_117 encode_f(z, z') -{ 0 }-> 0 :|: v0 >= 0, v1 >= 0, z = v0, z' = v1 encode_g(z) -{ 0 }-> g(g(encArg(x_134))) :|: x_134 >= 0, z = 1 + x_134 encode_g(z) -{ 0 }-> g(f(encArg(x_133), encArg(x_210))) :|: z = 1 + x_133 + x_210, x_133 >= 0, x_210 >= 0 encode_g(z) -{ 0 }-> g(0) :|: x_1 >= 0, z = x_1 encode_g(z) -{ 0 }-> g(1 + encArg(x_132)) :|: z = 1 + x_132, x_132 >= 0 encode_g(z) -{ 0 }-> 0 :|: v0 >= 0, z = v0 encode_s(z) -{ 0 }-> 0 :|: v0 >= 0, z = v0 encode_s(z) -{ 0 }-> 1 + encArg(x_1) :|: x_1 >= 0, z = x_1 f(z, z') -{ 2 }-> f(1 + x, x) :|: z' = x, x >= 0, z = x f(z, z') -{ 0 }-> 0 :|: v0 >= 0, v1 >= 0, z = v0, z' = v1 g(z) -{ 1 }-> 1 + x :|: x >= 0, z = x ---------------------------------------- (15) InliningProof (UPPER BOUND(ID)) Inlined the following terminating rules on right-hand sides where appropriate: g(z) -{ 1 }-> 1 + x :|: x >= 0, z = x ---------------------------------------- (16) Obligation: Complexity RNTS consisting of the following rules: encArg(z) -{ 0 }-> g(g(encArg(x_116))) :|: z = 1 + (1 + x_116), x_116 >= 0 encArg(z) -{ 0 }-> g(f(encArg(x_115), encArg(x_24))) :|: z = 1 + (1 + x_115 + x_24), x_115 >= 0, x_24 >= 0 encArg(z) -{ 0 }-> g(1 + encArg(x_114)) :|: z = 1 + (1 + x_114), x_114 >= 0 encArg(z) -{ 0 }-> f(g(encArg(x_11)), g(encArg(x_110))) :|: x_11 >= 0, z = 1 + (1 + x_11) + (1 + x_110), x_110 >= 0 encArg(z) -{ 0 }-> f(g(encArg(x_11)), f(encArg(x_19), encArg(x_22))) :|: x_11 >= 0, z = 1 + (1 + x_11) + (1 + x_19 + x_22), x_22 >= 0, x_19 >= 0 encArg(z) -{ 0 }-> f(g(encArg(x_11)), 0) :|: x_11 >= 0, z = 1 + (1 + x_11) + x_2, x_2 >= 0 encArg(z) -{ 0 }-> f(g(encArg(x_11)), 1 + encArg(x_18)) :|: x_11 >= 0, z = 1 + (1 + x_11) + (1 + x_18), x_18 >= 0 encArg(z) -{ 0 }-> f(f(encArg(x_1''), encArg(x_2')), g(encArg(x_17))) :|: x_1'' >= 0, z = 1 + (1 + x_1'' + x_2') + (1 + x_17), x_2' >= 0, x_17 >= 0 encArg(z) -{ 0 }-> f(f(encArg(x_1''), encArg(x_2')), f(encArg(x_16), encArg(x_21))) :|: x_1'' >= 0, x_16 >= 0, x_2' >= 0, z = 1 + (1 + x_1'' + x_2') + (1 + x_16 + x_21), x_21 >= 0 encArg(z) -{ 0 }-> f(f(encArg(x_1''), encArg(x_2')), 0) :|: x_1'' >= 0, x_2' >= 0, z = 1 + (1 + x_1'' + x_2') + x_2, x_2 >= 0 encArg(z) -{ 0 }-> f(f(encArg(x_1''), encArg(x_2')), 1 + encArg(x_15)) :|: x_15 >= 0, z = 1 + (1 + x_1'' + x_2') + (1 + x_15), x_1'' >= 0, x_2' >= 0 encArg(z) -{ 0 }-> f(0, g(encArg(x_113))) :|: x_1 >= 0, x_113 >= 0, z = 1 + x_1 + (1 + x_113) encArg(z) -{ 0 }-> f(0, f(encArg(x_112), encArg(x_23))) :|: x_1 >= 0, z = 1 + x_1 + (1 + x_112 + x_23), x_23 >= 0, x_112 >= 0 encArg(z) -{ 0 }-> f(0, 0) :|: x_1 >= 0, z = 1 + x_1 + x_2, x_2 >= 0 encArg(z) -{ 0 }-> f(0, 1 + encArg(x_111)) :|: x_1 >= 0, z = 1 + x_1 + (1 + x_111), x_111 >= 0 encArg(z) -{ 0 }-> f(1 + encArg(x_1'), g(encArg(x_14))) :|: z = 1 + (1 + x_1') + (1 + x_14), x_14 >= 0, x_1' >= 0 encArg(z) -{ 0 }-> f(1 + encArg(x_1'), f(encArg(x_13), encArg(x_2''))) :|: x_13 >= 0, x_1' >= 0, x_2'' >= 0, z = 1 + (1 + x_1') + (1 + x_13 + x_2'') encArg(z) -{ 0 }-> f(1 + encArg(x_1'), 0) :|: x_1' >= 0, x_2 >= 0, z = 1 + (1 + x_1') + x_2 encArg(z) -{ 0 }-> f(1 + encArg(x_1'), 1 + encArg(x_12)) :|: z = 1 + (1 + x_1') + (1 + x_12), x_1' >= 0, x_12 >= 0 encArg(z) -{ 0 }-> 0 :|: v0 >= 0, z = v0 encArg(z) -{ 1 }-> 1 + x :|: z = 1 + x_1, x_1 >= 0, x >= 0, 0 = x encArg(z) -{ 0 }-> 1 + encArg(x_1) :|: z = 1 + x_1, x_1 >= 0 encode_f(z, z') -{ 0 }-> f(g(encArg(x_119)), g(encArg(x_128))) :|: x_128 >= 0, z' = 1 + x_128, z = 1 + x_119, x_119 >= 0 encode_f(z, z') -{ 0 }-> f(g(encArg(x_119)), f(encArg(x_127), encArg(x_28))) :|: x_127 >= 0, z' = 1 + x_127 + x_28, z = 1 + x_119, x_28 >= 0, x_119 >= 0 encode_f(z, z') -{ 0 }-> f(g(encArg(x_119)), 0) :|: z = 1 + x_119, x_2 >= 0, z' = x_2, x_119 >= 0 encode_f(z, z') -{ 0 }-> f(g(encArg(x_119)), 1 + encArg(x_126)) :|: z' = 1 + x_126, x_126 >= 0, z = 1 + x_119, x_119 >= 0 encode_f(z, z') -{ 0 }-> f(f(encArg(x_118), encArg(x_25)), g(encArg(x_125))) :|: z' = 1 + x_125, x_25 >= 0, z = 1 + x_118 + x_25, x_125 >= 0, x_118 >= 0 encode_f(z, z') -{ 0 }-> f(f(encArg(x_118), encArg(x_25)), f(encArg(x_124), encArg(x_27))) :|: x_124 >= 0, x_25 >= 0, z = 1 + x_118 + x_25, x_27 >= 0, x_118 >= 0, z' = 1 + x_124 + x_27 encode_f(z, z') -{ 0 }-> f(f(encArg(x_118), encArg(x_25)), 0) :|: x_25 >= 0, z = 1 + x_118 + x_25, x_2 >= 0, z' = x_2, x_118 >= 0 encode_f(z, z') -{ 0 }-> f(f(encArg(x_118), encArg(x_25)), 1 + encArg(x_123)) :|: z' = 1 + x_123, x_123 >= 0, x_25 >= 0, z = 1 + x_118 + x_25, x_118 >= 0 encode_f(z, z') -{ 0 }-> f(0, g(encArg(x_131))) :|: x_1 >= 0, z' = 1 + x_131, z = x_1, x_131 >= 0 encode_f(z, z') -{ 0 }-> f(0, f(encArg(x_130), encArg(x_29))) :|: x_1 >= 0, x_130 >= 0, z' = 1 + x_130 + x_29, z = x_1, x_29 >= 0 encode_f(z, z') -{ 0 }-> f(0, 0) :|: x_1 >= 0, x_2 >= 0, z = x_1, z' = x_2 encode_f(z, z') -{ 0 }-> f(0, 1 + encArg(x_129)) :|: x_1 >= 0, z' = 1 + x_129, z = x_1, x_129 >= 0 encode_f(z, z') -{ 0 }-> f(1 + encArg(x_117), g(encArg(x_122))) :|: z' = 1 + x_122, x_117 >= 0, x_122 >= 0, z = 1 + x_117 encode_f(z, z') -{ 0 }-> f(1 + encArg(x_117), f(encArg(x_121), encArg(x_26))) :|: x_117 >= 0, x_26 >= 0, z' = 1 + x_121 + x_26, z = 1 + x_117, x_121 >= 0 encode_f(z, z') -{ 0 }-> f(1 + encArg(x_117), 0) :|: x_117 >= 0, x_2 >= 0, z' = x_2, z = 1 + x_117 encode_f(z, z') -{ 0 }-> f(1 + encArg(x_117), 1 + encArg(x_120)) :|: x_120 >= 0, x_117 >= 0, z' = 1 + x_120, z = 1 + x_117 encode_f(z, z') -{ 0 }-> 0 :|: v0 >= 0, v1 >= 0, z = v0, z' = v1 encode_g(z) -{ 0 }-> g(g(encArg(x_134))) :|: x_134 >= 0, z = 1 + x_134 encode_g(z) -{ 0 }-> g(f(encArg(x_133), encArg(x_210))) :|: z = 1 + x_133 + x_210, x_133 >= 0, x_210 >= 0 encode_g(z) -{ 0 }-> g(1 + encArg(x_132)) :|: z = 1 + x_132, x_132 >= 0 encode_g(z) -{ 0 }-> 0 :|: v0 >= 0, z = v0 encode_g(z) -{ 1 }-> 1 + x :|: x_1 >= 0, z = x_1, x >= 0, 0 = x encode_s(z) -{ 0 }-> 0 :|: v0 >= 0, z = v0 encode_s(z) -{ 0 }-> 1 + encArg(x_1) :|: x_1 >= 0, z = x_1 f(z, z') -{ 2 }-> f(1 + x, x) :|: z' = x, x >= 0, z = x f(z, z') -{ 0 }-> 0 :|: v0 >= 0, v1 >= 0, z = v0, z' = v1 g(z) -{ 1 }-> 1 + x :|: x >= 0, z = x ---------------------------------------- (17) SimplificationProof (BOTH BOUNDS(ID, ID)) Simplified the RNTS by moving equalities from the constraints into the right-hand sides. ---------------------------------------- (18) Obligation: Complexity RNTS consisting of the following rules: encArg(z) -{ 0 }-> g(g(encArg(z - 2))) :|: z - 2 >= 0 encArg(z) -{ 0 }-> g(f(encArg(x_115), encArg(x_24))) :|: z = 1 + (1 + x_115 + x_24), x_115 >= 0, x_24 >= 0 encArg(z) -{ 0 }-> g(1 + encArg(z - 2)) :|: z - 2 >= 0 encArg(z) -{ 0 }-> f(g(encArg(x_11)), g(encArg(x_110))) :|: x_11 >= 0, z = 1 + (1 + x_11) + (1 + x_110), x_110 >= 0 encArg(z) -{ 0 }-> f(g(encArg(x_11)), f(encArg(x_19), encArg(x_22))) :|: x_11 >= 0, z = 1 + (1 + x_11) + (1 + x_19 + x_22), x_22 >= 0, x_19 >= 0 encArg(z) -{ 0 }-> f(g(encArg(x_11)), 0) :|: x_11 >= 0, z = 1 + (1 + x_11) + x_2, x_2 >= 0 encArg(z) -{ 0 }-> f(g(encArg(x_11)), 1 + encArg(x_18)) :|: x_11 >= 0, z = 1 + (1 + x_11) + (1 + x_18), x_18 >= 0 encArg(z) -{ 0 }-> f(f(encArg(x_1''), encArg(x_2')), g(encArg(x_17))) :|: x_1'' >= 0, z = 1 + (1 + x_1'' + x_2') + (1 + x_17), x_2' >= 0, x_17 >= 0 encArg(z) -{ 0 }-> f(f(encArg(x_1''), encArg(x_2')), f(encArg(x_16), encArg(x_21))) :|: x_1'' >= 0, x_16 >= 0, x_2' >= 0, z = 1 + (1 + x_1'' + x_2') + (1 + x_16 + x_21), x_21 >= 0 encArg(z) -{ 0 }-> f(f(encArg(x_1''), encArg(x_2')), 0) :|: x_1'' >= 0, x_2' >= 0, z = 1 + (1 + x_1'' + x_2') + x_2, x_2 >= 0 encArg(z) -{ 0 }-> f(f(encArg(x_1''), encArg(x_2')), 1 + encArg(x_15)) :|: x_15 >= 0, z = 1 + (1 + x_1'' + x_2') + (1 + x_15), x_1'' >= 0, x_2' >= 0 encArg(z) -{ 0 }-> f(0, g(encArg(x_113))) :|: x_1 >= 0, x_113 >= 0, z = 1 + x_1 + (1 + x_113) encArg(z) -{ 0 }-> f(0, f(encArg(x_112), encArg(x_23))) :|: x_1 >= 0, z = 1 + x_1 + (1 + x_112 + x_23), x_23 >= 0, x_112 >= 0 encArg(z) -{ 0 }-> f(0, 0) :|: x_1 >= 0, z = 1 + x_1 + x_2, x_2 >= 0 encArg(z) -{ 0 }-> f(0, 1 + encArg(x_111)) :|: x_1 >= 0, z = 1 + x_1 + (1 + x_111), x_111 >= 0 encArg(z) -{ 0 }-> f(1 + encArg(x_1'), g(encArg(x_14))) :|: z = 1 + (1 + x_1') + (1 + x_14), x_14 >= 0, x_1' >= 0 encArg(z) -{ 0 }-> f(1 + encArg(x_1'), f(encArg(x_13), encArg(x_2''))) :|: x_13 >= 0, x_1' >= 0, x_2'' >= 0, z = 1 + (1 + x_1') + (1 + x_13 + x_2'') encArg(z) -{ 0 }-> f(1 + encArg(x_1'), 0) :|: x_1' >= 0, x_2 >= 0, z = 1 + (1 + x_1') + x_2 encArg(z) -{ 0 }-> f(1 + encArg(x_1'), 1 + encArg(x_12)) :|: z = 1 + (1 + x_1') + (1 + x_12), x_1' >= 0, x_12 >= 0 encArg(z) -{ 0 }-> 0 :|: z >= 0 encArg(z) -{ 1 }-> 1 + x :|: z - 1 >= 0, x >= 0, 0 = x encArg(z) -{ 0 }-> 1 + encArg(z - 1) :|: z - 1 >= 0 encode_f(z, z') -{ 0 }-> f(g(encArg(z - 1)), g(encArg(z' - 1))) :|: z' - 1 >= 0, z - 1 >= 0 encode_f(z, z') -{ 0 }-> f(g(encArg(z - 1)), f(encArg(x_127), encArg(x_28))) :|: x_127 >= 0, z' = 1 + x_127 + x_28, x_28 >= 0, z - 1 >= 0 encode_f(z, z') -{ 0 }-> f(g(encArg(z - 1)), 0) :|: z' >= 0, z - 1 >= 0 encode_f(z, z') -{ 0 }-> f(g(encArg(z - 1)), 1 + encArg(z' - 1)) :|: z' - 1 >= 0, z - 1 >= 0 encode_f(z, z') -{ 0 }-> f(f(encArg(x_118), encArg(x_25)), g(encArg(z' - 1))) :|: x_25 >= 0, z = 1 + x_118 + x_25, z' - 1 >= 0, x_118 >= 0 encode_f(z, z') -{ 0 }-> f(f(encArg(x_118), encArg(x_25)), f(encArg(x_124), encArg(x_27))) :|: x_124 >= 0, x_25 >= 0, z = 1 + x_118 + x_25, x_27 >= 0, x_118 >= 0, z' = 1 + x_124 + x_27 encode_f(z, z') -{ 0 }-> f(f(encArg(x_118), encArg(x_25)), 0) :|: x_25 >= 0, z = 1 + x_118 + x_25, z' >= 0, x_118 >= 0 encode_f(z, z') -{ 0 }-> f(f(encArg(x_118), encArg(x_25)), 1 + encArg(z' - 1)) :|: z' - 1 >= 0, x_25 >= 0, z = 1 + x_118 + x_25, x_118 >= 0 encode_f(z, z') -{ 0 }-> f(0, g(encArg(z' - 1))) :|: z >= 0, z' - 1 >= 0 encode_f(z, z') -{ 0 }-> f(0, f(encArg(x_130), encArg(x_29))) :|: z >= 0, x_130 >= 0, z' = 1 + x_130 + x_29, x_29 >= 0 encode_f(z, z') -{ 0 }-> f(0, 0) :|: z >= 0, z' >= 0 encode_f(z, z') -{ 0 }-> f(0, 1 + encArg(z' - 1)) :|: z >= 0, z' - 1 >= 0 encode_f(z, z') -{ 0 }-> f(1 + encArg(z - 1), g(encArg(z' - 1))) :|: z - 1 >= 0, z' - 1 >= 0 encode_f(z, z') -{ 0 }-> f(1 + encArg(z - 1), f(encArg(x_121), encArg(x_26))) :|: z - 1 >= 0, x_26 >= 0, z' = 1 + x_121 + x_26, x_121 >= 0 encode_f(z, z') -{ 0 }-> f(1 + encArg(z - 1), 0) :|: z - 1 >= 0, z' >= 0 encode_f(z, z') -{ 0 }-> f(1 + encArg(z - 1), 1 + encArg(z' - 1)) :|: z' - 1 >= 0, z - 1 >= 0 encode_f(z, z') -{ 0 }-> 0 :|: z >= 0, z' >= 0 encode_g(z) -{ 0 }-> g(g(encArg(z - 1))) :|: z - 1 >= 0 encode_g(z) -{ 0 }-> g(f(encArg(x_133), encArg(x_210))) :|: z = 1 + x_133 + x_210, x_133 >= 0, x_210 >= 0 encode_g(z) -{ 0 }-> g(1 + encArg(z - 1)) :|: z - 1 >= 0 encode_g(z) -{ 0 }-> 0 :|: z >= 0 encode_g(z) -{ 1 }-> 1 + x :|: z >= 0, x >= 0, 0 = x encode_s(z) -{ 0 }-> 0 :|: z >= 0 encode_s(z) -{ 0 }-> 1 + encArg(z) :|: z >= 0 f(z, z') -{ 2 }-> f(1 + z', z') :|: z' >= 0, z = z' f(z, z') -{ 0 }-> 0 :|: z >= 0, z' >= 0 g(z) -{ 1 }-> 1 + z :|: z >= 0 ---------------------------------------- (19) CpxRntsAnalysisOrderProof (BOTH BOUNDS(ID, ID)) Found the following analysis order by SCC decomposition: { g } { f } { encArg } { encode_f } { encode_g } { encode_s } ---------------------------------------- (20) Obligation: Complexity RNTS consisting of the following rules: encArg(z) -{ 0 }-> g(g(encArg(z - 2))) :|: z - 2 >= 0 encArg(z) -{ 0 }-> g(f(encArg(x_115), encArg(x_24))) :|: z = 1 + (1 + x_115 + x_24), x_115 >= 0, x_24 >= 0 encArg(z) -{ 0 }-> g(1 + encArg(z - 2)) :|: z - 2 >= 0 encArg(z) -{ 0 }-> f(g(encArg(x_11)), g(encArg(x_110))) :|: x_11 >= 0, z = 1 + (1 + x_11) + (1 + x_110), x_110 >= 0 encArg(z) -{ 0 }-> f(g(encArg(x_11)), f(encArg(x_19), encArg(x_22))) :|: x_11 >= 0, z = 1 + (1 + x_11) + (1 + x_19 + x_22), x_22 >= 0, x_19 >= 0 encArg(z) -{ 0 }-> f(g(encArg(x_11)), 0) :|: x_11 >= 0, z = 1 + (1 + x_11) + x_2, x_2 >= 0 encArg(z) -{ 0 }-> f(g(encArg(x_11)), 1 + encArg(x_18)) :|: x_11 >= 0, z = 1 + (1 + x_11) + (1 + x_18), x_18 >= 0 encArg(z) -{ 0 }-> f(f(encArg(x_1''), encArg(x_2')), g(encArg(x_17))) :|: x_1'' >= 0, z = 1 + (1 + x_1'' + x_2') + (1 + x_17), x_2' >= 0, x_17 >= 0 encArg(z) -{ 0 }-> f(f(encArg(x_1''), encArg(x_2')), f(encArg(x_16), encArg(x_21))) :|: x_1'' >= 0, x_16 >= 0, x_2' >= 0, z = 1 + (1 + x_1'' + x_2') + (1 + x_16 + x_21), x_21 >= 0 encArg(z) -{ 0 }-> f(f(encArg(x_1''), encArg(x_2')), 0) :|: x_1'' >= 0, x_2' >= 0, z = 1 + (1 + x_1'' + x_2') + x_2, x_2 >= 0 encArg(z) -{ 0 }-> f(f(encArg(x_1''), encArg(x_2')), 1 + encArg(x_15)) :|: x_15 >= 0, z = 1 + (1 + x_1'' + x_2') + (1 + x_15), x_1'' >= 0, x_2' >= 0 encArg(z) -{ 0 }-> f(0, g(encArg(x_113))) :|: x_1 >= 0, x_113 >= 0, z = 1 + x_1 + (1 + x_113) encArg(z) -{ 0 }-> f(0, f(encArg(x_112), encArg(x_23))) :|: x_1 >= 0, z = 1 + x_1 + (1 + x_112 + x_23), x_23 >= 0, x_112 >= 0 encArg(z) -{ 0 }-> f(0, 0) :|: x_1 >= 0, z = 1 + x_1 + x_2, x_2 >= 0 encArg(z) -{ 0 }-> f(0, 1 + encArg(x_111)) :|: x_1 >= 0, z = 1 + x_1 + (1 + x_111), x_111 >= 0 encArg(z) -{ 0 }-> f(1 + encArg(x_1'), g(encArg(x_14))) :|: z = 1 + (1 + x_1') + (1 + x_14), x_14 >= 0, x_1' >= 0 encArg(z) -{ 0 }-> f(1 + encArg(x_1'), f(encArg(x_13), encArg(x_2''))) :|: x_13 >= 0, x_1' >= 0, x_2'' >= 0, z = 1 + (1 + x_1') + (1 + x_13 + x_2'') encArg(z) -{ 0 }-> f(1 + encArg(x_1'), 0) :|: x_1' >= 0, x_2 >= 0, z = 1 + (1 + x_1') + x_2 encArg(z) -{ 0 }-> f(1 + encArg(x_1'), 1 + encArg(x_12)) :|: z = 1 + (1 + x_1') + (1 + x_12), x_1' >= 0, x_12 >= 0 encArg(z) -{ 0 }-> 0 :|: z >= 0 encArg(z) -{ 1 }-> 1 + x :|: z - 1 >= 0, x >= 0, 0 = x encArg(z) -{ 0 }-> 1 + encArg(z - 1) :|: z - 1 >= 0 encode_f(z, z') -{ 0 }-> f(g(encArg(z - 1)), g(encArg(z' - 1))) :|: z' - 1 >= 0, z - 1 >= 0 encode_f(z, z') -{ 0 }-> f(g(encArg(z - 1)), f(encArg(x_127), encArg(x_28))) :|: x_127 >= 0, z' = 1 + x_127 + x_28, x_28 >= 0, z - 1 >= 0 encode_f(z, z') -{ 0 }-> f(g(encArg(z - 1)), 0) :|: z' >= 0, z - 1 >= 0 encode_f(z, z') -{ 0 }-> f(g(encArg(z - 1)), 1 + encArg(z' - 1)) :|: z' - 1 >= 0, z - 1 >= 0 encode_f(z, z') -{ 0 }-> f(f(encArg(x_118), encArg(x_25)), g(encArg(z' - 1))) :|: x_25 >= 0, z = 1 + x_118 + x_25, z' - 1 >= 0, x_118 >= 0 encode_f(z, z') -{ 0 }-> f(f(encArg(x_118), encArg(x_25)), f(encArg(x_124), encArg(x_27))) :|: x_124 >= 0, x_25 >= 0, z = 1 + x_118 + x_25, x_27 >= 0, x_118 >= 0, z' = 1 + x_124 + x_27 encode_f(z, z') -{ 0 }-> f(f(encArg(x_118), encArg(x_25)), 0) :|: x_25 >= 0, z = 1 + x_118 + x_25, z' >= 0, x_118 >= 0 encode_f(z, z') -{ 0 }-> f(f(encArg(x_118), encArg(x_25)), 1 + encArg(z' - 1)) :|: z' - 1 >= 0, x_25 >= 0, z = 1 + x_118 + x_25, x_118 >= 0 encode_f(z, z') -{ 0 }-> f(0, g(encArg(z' - 1))) :|: z >= 0, z' - 1 >= 0 encode_f(z, z') -{ 0 }-> f(0, f(encArg(x_130), encArg(x_29))) :|: z >= 0, x_130 >= 0, z' = 1 + x_130 + x_29, x_29 >= 0 encode_f(z, z') -{ 0 }-> f(0, 0) :|: z >= 0, z' >= 0 encode_f(z, z') -{ 0 }-> f(0, 1 + encArg(z' - 1)) :|: z >= 0, z' - 1 >= 0 encode_f(z, z') -{ 0 }-> f(1 + encArg(z - 1), g(encArg(z' - 1))) :|: z - 1 >= 0, z' - 1 >= 0 encode_f(z, z') -{ 0 }-> f(1 + encArg(z - 1), f(encArg(x_121), encArg(x_26))) :|: z - 1 >= 0, x_26 >= 0, z' = 1 + x_121 + x_26, x_121 >= 0 encode_f(z, z') -{ 0 }-> f(1 + encArg(z - 1), 0) :|: z - 1 >= 0, z' >= 0 encode_f(z, z') -{ 0 }-> f(1 + encArg(z - 1), 1 + encArg(z' - 1)) :|: z' - 1 >= 0, z - 1 >= 0 encode_f(z, z') -{ 0 }-> 0 :|: z >= 0, z' >= 0 encode_g(z) -{ 0 }-> g(g(encArg(z - 1))) :|: z - 1 >= 0 encode_g(z) -{ 0 }-> g(f(encArg(x_133), encArg(x_210))) :|: z = 1 + x_133 + x_210, x_133 >= 0, x_210 >= 0 encode_g(z) -{ 0 }-> g(1 + encArg(z - 1)) :|: z - 1 >= 0 encode_g(z) -{ 0 }-> 0 :|: z >= 0 encode_g(z) -{ 1 }-> 1 + x :|: z >= 0, x >= 0, 0 = x encode_s(z) -{ 0 }-> 0 :|: z >= 0 encode_s(z) -{ 0 }-> 1 + encArg(z) :|: z >= 0 f(z, z') -{ 2 }-> f(1 + z', z') :|: z' >= 0, z = z' f(z, z') -{ 0 }-> 0 :|: z >= 0, z' >= 0 g(z) -{ 1 }-> 1 + z :|: z >= 0 Function symbols to be analyzed: {g}, {f}, {encArg}, {encode_f}, {encode_g}, {encode_s} ---------------------------------------- (21) ResultPropagationProof (UPPER BOUND(ID)) Applied inner abstraction using the recently inferred runtime/size bounds where possible. ---------------------------------------- (22) Obligation: Complexity RNTS consisting of the following rules: encArg(z) -{ 0 }-> g(g(encArg(z - 2))) :|: z - 2 >= 0 encArg(z) -{ 0 }-> g(f(encArg(x_115), encArg(x_24))) :|: z = 1 + (1 + x_115 + x_24), x_115 >= 0, x_24 >= 0 encArg(z) -{ 0 }-> g(1 + encArg(z - 2)) :|: z - 2 >= 0 encArg(z) -{ 0 }-> f(g(encArg(x_11)), g(encArg(x_110))) :|: x_11 >= 0, z = 1 + (1 + x_11) + (1 + x_110), x_110 >= 0 encArg(z) -{ 0 }-> f(g(encArg(x_11)), f(encArg(x_19), encArg(x_22))) :|: x_11 >= 0, z = 1 + (1 + x_11) + (1 + x_19 + x_22), x_22 >= 0, x_19 >= 0 encArg(z) -{ 0 }-> f(g(encArg(x_11)), 0) :|: x_11 >= 0, z = 1 + (1 + x_11) + x_2, x_2 >= 0 encArg(z) -{ 0 }-> f(g(encArg(x_11)), 1 + encArg(x_18)) :|: x_11 >= 0, z = 1 + (1 + x_11) + (1 + x_18), x_18 >= 0 encArg(z) -{ 0 }-> f(f(encArg(x_1''), encArg(x_2')), g(encArg(x_17))) :|: x_1'' >= 0, z = 1 + (1 + x_1'' + x_2') + (1 + x_17), x_2' >= 0, x_17 >= 0 encArg(z) -{ 0 }-> f(f(encArg(x_1''), encArg(x_2')), f(encArg(x_16), encArg(x_21))) :|: x_1'' >= 0, x_16 >= 0, x_2' >= 0, z = 1 + (1 + x_1'' + x_2') + (1 + x_16 + x_21), x_21 >= 0 encArg(z) -{ 0 }-> f(f(encArg(x_1''), encArg(x_2')), 0) :|: x_1'' >= 0, x_2' >= 0, z = 1 + (1 + x_1'' + x_2') + x_2, x_2 >= 0 encArg(z) -{ 0 }-> f(f(encArg(x_1''), encArg(x_2')), 1 + encArg(x_15)) :|: x_15 >= 0, z = 1 + (1 + x_1'' + x_2') + (1 + x_15), x_1'' >= 0, x_2' >= 0 encArg(z) -{ 0 }-> f(0, g(encArg(x_113))) :|: x_1 >= 0, x_113 >= 0, z = 1 + x_1 + (1 + x_113) encArg(z) -{ 0 }-> f(0, f(encArg(x_112), encArg(x_23))) :|: x_1 >= 0, z = 1 + x_1 + (1 + x_112 + x_23), x_23 >= 0, x_112 >= 0 encArg(z) -{ 0 }-> f(0, 0) :|: x_1 >= 0, z = 1 + x_1 + x_2, x_2 >= 0 encArg(z) -{ 0 }-> f(0, 1 + encArg(x_111)) :|: x_1 >= 0, z = 1 + x_1 + (1 + x_111), x_111 >= 0 encArg(z) -{ 0 }-> f(1 + encArg(x_1'), g(encArg(x_14))) :|: z = 1 + (1 + x_1') + (1 + x_14), x_14 >= 0, x_1' >= 0 encArg(z) -{ 0 }-> f(1 + encArg(x_1'), f(encArg(x_13), encArg(x_2''))) :|: x_13 >= 0, x_1' >= 0, x_2'' >= 0, z = 1 + (1 + x_1') + (1 + x_13 + x_2'') encArg(z) -{ 0 }-> f(1 + encArg(x_1'), 0) :|: x_1' >= 0, x_2 >= 0, z = 1 + (1 + x_1') + x_2 encArg(z) -{ 0 }-> f(1 + encArg(x_1'), 1 + encArg(x_12)) :|: z = 1 + (1 + x_1') + (1 + x_12), x_1' >= 0, x_12 >= 0 encArg(z) -{ 0 }-> 0 :|: z >= 0 encArg(z) -{ 1 }-> 1 + x :|: z - 1 >= 0, x >= 0, 0 = x encArg(z) -{ 0 }-> 1 + encArg(z - 1) :|: z - 1 >= 0 encode_f(z, z') -{ 0 }-> f(g(encArg(z - 1)), g(encArg(z' - 1))) :|: z' - 1 >= 0, z - 1 >= 0 encode_f(z, z') -{ 0 }-> f(g(encArg(z - 1)), f(encArg(x_127), encArg(x_28))) :|: x_127 >= 0, z' = 1 + x_127 + x_28, x_28 >= 0, z - 1 >= 0 encode_f(z, z') -{ 0 }-> f(g(encArg(z - 1)), 0) :|: z' >= 0, z - 1 >= 0 encode_f(z, z') -{ 0 }-> f(g(encArg(z - 1)), 1 + encArg(z' - 1)) :|: z' - 1 >= 0, z - 1 >= 0 encode_f(z, z') -{ 0 }-> f(f(encArg(x_118), encArg(x_25)), g(encArg(z' - 1))) :|: x_25 >= 0, z = 1 + x_118 + x_25, z' - 1 >= 0, x_118 >= 0 encode_f(z, z') -{ 0 }-> f(f(encArg(x_118), encArg(x_25)), f(encArg(x_124), encArg(x_27))) :|: x_124 >= 0, x_25 >= 0, z = 1 + x_118 + x_25, x_27 >= 0, x_118 >= 0, z' = 1 + x_124 + x_27 encode_f(z, z') -{ 0 }-> f(f(encArg(x_118), encArg(x_25)), 0) :|: x_25 >= 0, z = 1 + x_118 + x_25, z' >= 0, x_118 >= 0 encode_f(z, z') -{ 0 }-> f(f(encArg(x_118), encArg(x_25)), 1 + encArg(z' - 1)) :|: z' - 1 >= 0, x_25 >= 0, z = 1 + x_118 + x_25, x_118 >= 0 encode_f(z, z') -{ 0 }-> f(0, g(encArg(z' - 1))) :|: z >= 0, z' - 1 >= 0 encode_f(z, z') -{ 0 }-> f(0, f(encArg(x_130), encArg(x_29))) :|: z >= 0, x_130 >= 0, z' = 1 + x_130 + x_29, x_29 >= 0 encode_f(z, z') -{ 0 }-> f(0, 0) :|: z >= 0, z' >= 0 encode_f(z, z') -{ 0 }-> f(0, 1 + encArg(z' - 1)) :|: z >= 0, z' - 1 >= 0 encode_f(z, z') -{ 0 }-> f(1 + encArg(z - 1), g(encArg(z' - 1))) :|: z - 1 >= 0, z' - 1 >= 0 encode_f(z, z') -{ 0 }-> f(1 + encArg(z - 1), f(encArg(x_121), encArg(x_26))) :|: z - 1 >= 0, x_26 >= 0, z' = 1 + x_121 + x_26, x_121 >= 0 encode_f(z, z') -{ 0 }-> f(1 + encArg(z - 1), 0) :|: z - 1 >= 0, z' >= 0 encode_f(z, z') -{ 0 }-> f(1 + encArg(z - 1), 1 + encArg(z' - 1)) :|: z' - 1 >= 0, z - 1 >= 0 encode_f(z, z') -{ 0 }-> 0 :|: z >= 0, z' >= 0 encode_g(z) -{ 0 }-> g(g(encArg(z - 1))) :|: z - 1 >= 0 encode_g(z) -{ 0 }-> g(f(encArg(x_133), encArg(x_210))) :|: z = 1 + x_133 + x_210, x_133 >= 0, x_210 >= 0 encode_g(z) -{ 0 }-> g(1 + encArg(z - 1)) :|: z - 1 >= 0 encode_g(z) -{ 0 }-> 0 :|: z >= 0 encode_g(z) -{ 1 }-> 1 + x :|: z >= 0, x >= 0, 0 = x encode_s(z) -{ 0 }-> 0 :|: z >= 0 encode_s(z) -{ 0 }-> 1 + encArg(z) :|: z >= 0 f(z, z') -{ 2 }-> f(1 + z', z') :|: z' >= 0, z = z' f(z, z') -{ 0 }-> 0 :|: z >= 0, z' >= 0 g(z) -{ 1 }-> 1 + z :|: z >= 0 Function symbols to be analyzed: {g}, {f}, {encArg}, {encode_f}, {encode_g}, {encode_s} ---------------------------------------- (23) IntTrsBoundProof (UPPER BOUND(ID)) Computed SIZE bound using CoFloCo for: g after applying outer abstraction to obtain an ITS, resulting in: O(n^1) with polynomial bound: 1 + z ---------------------------------------- (24) Obligation: Complexity RNTS consisting of the following rules: encArg(z) -{ 0 }-> g(g(encArg(z - 2))) :|: z - 2 >= 0 encArg(z) -{ 0 }-> g(f(encArg(x_115), encArg(x_24))) :|: z = 1 + (1 + x_115 + x_24), x_115 >= 0, x_24 >= 0 encArg(z) -{ 0 }-> g(1 + encArg(z - 2)) :|: z - 2 >= 0 encArg(z) -{ 0 }-> f(g(encArg(x_11)), g(encArg(x_110))) :|: x_11 >= 0, z = 1 + (1 + x_11) + (1 + x_110), x_110 >= 0 encArg(z) -{ 0 }-> f(g(encArg(x_11)), f(encArg(x_19), encArg(x_22))) :|: x_11 >= 0, z = 1 + (1 + x_11) + (1 + x_19 + x_22), x_22 >= 0, x_19 >= 0 encArg(z) -{ 0 }-> f(g(encArg(x_11)), 0) :|: x_11 >= 0, z = 1 + (1 + x_11) + x_2, x_2 >= 0 encArg(z) -{ 0 }-> f(g(encArg(x_11)), 1 + encArg(x_18)) :|: x_11 >= 0, z = 1 + (1 + x_11) + (1 + x_18), x_18 >= 0 encArg(z) -{ 0 }-> f(f(encArg(x_1''), encArg(x_2')), g(encArg(x_17))) :|: x_1'' >= 0, z = 1 + (1 + x_1'' + x_2') + (1 + x_17), x_2' >= 0, x_17 >= 0 encArg(z) -{ 0 }-> f(f(encArg(x_1''), encArg(x_2')), f(encArg(x_16), encArg(x_21))) :|: x_1'' >= 0, x_16 >= 0, x_2' >= 0, z = 1 + (1 + x_1'' + x_2') + (1 + x_16 + x_21), x_21 >= 0 encArg(z) -{ 0 }-> f(f(encArg(x_1''), encArg(x_2')), 0) :|: x_1'' >= 0, x_2' >= 0, z = 1 + (1 + x_1'' + x_2') + x_2, x_2 >= 0 encArg(z) -{ 0 }-> f(f(encArg(x_1''), encArg(x_2')), 1 + encArg(x_15)) :|: x_15 >= 0, z = 1 + (1 + x_1'' + x_2') + (1 + x_15), x_1'' >= 0, x_2' >= 0 encArg(z) -{ 0 }-> f(0, g(encArg(x_113))) :|: x_1 >= 0, x_113 >= 0, z = 1 + x_1 + (1 + x_113) encArg(z) -{ 0 }-> f(0, f(encArg(x_112), encArg(x_23))) :|: x_1 >= 0, z = 1 + x_1 + (1 + x_112 + x_23), x_23 >= 0, x_112 >= 0 encArg(z) -{ 0 }-> f(0, 0) :|: x_1 >= 0, z = 1 + x_1 + x_2, x_2 >= 0 encArg(z) -{ 0 }-> f(0, 1 + encArg(x_111)) :|: x_1 >= 0, z = 1 + x_1 + (1 + x_111), x_111 >= 0 encArg(z) -{ 0 }-> f(1 + encArg(x_1'), g(encArg(x_14))) :|: z = 1 + (1 + x_1') + (1 + x_14), x_14 >= 0, x_1' >= 0 encArg(z) -{ 0 }-> f(1 + encArg(x_1'), f(encArg(x_13), encArg(x_2''))) :|: x_13 >= 0, x_1' >= 0, x_2'' >= 0, z = 1 + (1 + x_1') + (1 + x_13 + x_2'') encArg(z) -{ 0 }-> f(1 + encArg(x_1'), 0) :|: x_1' >= 0, x_2 >= 0, z = 1 + (1 + x_1') + x_2 encArg(z) -{ 0 }-> f(1 + encArg(x_1'), 1 + encArg(x_12)) :|: z = 1 + (1 + x_1') + (1 + x_12), x_1' >= 0, x_12 >= 0 encArg(z) -{ 0 }-> 0 :|: z >= 0 encArg(z) -{ 1 }-> 1 + x :|: z - 1 >= 0, x >= 0, 0 = x encArg(z) -{ 0 }-> 1 + encArg(z - 1) :|: z - 1 >= 0 encode_f(z, z') -{ 0 }-> f(g(encArg(z - 1)), g(encArg(z' - 1))) :|: z' - 1 >= 0, z - 1 >= 0 encode_f(z, z') -{ 0 }-> f(g(encArg(z - 1)), f(encArg(x_127), encArg(x_28))) :|: x_127 >= 0, z' = 1 + x_127 + x_28, x_28 >= 0, z - 1 >= 0 encode_f(z, z') -{ 0 }-> f(g(encArg(z - 1)), 0) :|: z' >= 0, z - 1 >= 0 encode_f(z, z') -{ 0 }-> f(g(encArg(z - 1)), 1 + encArg(z' - 1)) :|: z' - 1 >= 0, z - 1 >= 0 encode_f(z, z') -{ 0 }-> f(f(encArg(x_118), encArg(x_25)), g(encArg(z' - 1))) :|: x_25 >= 0, z = 1 + x_118 + x_25, z' - 1 >= 0, x_118 >= 0 encode_f(z, z') -{ 0 }-> f(f(encArg(x_118), encArg(x_25)), f(encArg(x_124), encArg(x_27))) :|: x_124 >= 0, x_25 >= 0, z = 1 + x_118 + x_25, x_27 >= 0, x_118 >= 0, z' = 1 + x_124 + x_27 encode_f(z, z') -{ 0 }-> f(f(encArg(x_118), encArg(x_25)), 0) :|: x_25 >= 0, z = 1 + x_118 + x_25, z' >= 0, x_118 >= 0 encode_f(z, z') -{ 0 }-> f(f(encArg(x_118), encArg(x_25)), 1 + encArg(z' - 1)) :|: z' - 1 >= 0, x_25 >= 0, z = 1 + x_118 + x_25, x_118 >= 0 encode_f(z, z') -{ 0 }-> f(0, g(encArg(z' - 1))) :|: z >= 0, z' - 1 >= 0 encode_f(z, z') -{ 0 }-> f(0, f(encArg(x_130), encArg(x_29))) :|: z >= 0, x_130 >= 0, z' = 1 + x_130 + x_29, x_29 >= 0 encode_f(z, z') -{ 0 }-> f(0, 0) :|: z >= 0, z' >= 0 encode_f(z, z') -{ 0 }-> f(0, 1 + encArg(z' - 1)) :|: z >= 0, z' - 1 >= 0 encode_f(z, z') -{ 0 }-> f(1 + encArg(z - 1), g(encArg(z' - 1))) :|: z - 1 >= 0, z' - 1 >= 0 encode_f(z, z') -{ 0 }-> f(1 + encArg(z - 1), f(encArg(x_121), encArg(x_26))) :|: z - 1 >= 0, x_26 >= 0, z' = 1 + x_121 + x_26, x_121 >= 0 encode_f(z, z') -{ 0 }-> f(1 + encArg(z - 1), 0) :|: z - 1 >= 0, z' >= 0 encode_f(z, z') -{ 0 }-> f(1 + encArg(z - 1), 1 + encArg(z' - 1)) :|: z' - 1 >= 0, z - 1 >= 0 encode_f(z, z') -{ 0 }-> 0 :|: z >= 0, z' >= 0 encode_g(z) -{ 0 }-> g(g(encArg(z - 1))) :|: z - 1 >= 0 encode_g(z) -{ 0 }-> g(f(encArg(x_133), encArg(x_210))) :|: z = 1 + x_133 + x_210, x_133 >= 0, x_210 >= 0 encode_g(z) -{ 0 }-> g(1 + encArg(z - 1)) :|: z - 1 >= 0 encode_g(z) -{ 0 }-> 0 :|: z >= 0 encode_g(z) -{ 1 }-> 1 + x :|: z >= 0, x >= 0, 0 = x encode_s(z) -{ 0 }-> 0 :|: z >= 0 encode_s(z) -{ 0 }-> 1 + encArg(z) :|: z >= 0 f(z, z') -{ 2 }-> f(1 + z', z') :|: z' >= 0, z = z' f(z, z') -{ 0 }-> 0 :|: z >= 0, z' >= 0 g(z) -{ 1 }-> 1 + z :|: z >= 0 Function symbols to be analyzed: {g}, {f}, {encArg}, {encode_f}, {encode_g}, {encode_s} Previous analysis results are: g: runtime: ?, size: O(n^1) [1 + z] ---------------------------------------- (25) IntTrsBoundProof (UPPER BOUND(ID)) Computed RUNTIME bound using CoFloCo for: g after applying outer abstraction to obtain an ITS, resulting in: O(1) with polynomial bound: 1 ---------------------------------------- (26) Obligation: Complexity RNTS consisting of the following rules: encArg(z) -{ 0 }-> g(g(encArg(z - 2))) :|: z - 2 >= 0 encArg(z) -{ 0 }-> g(f(encArg(x_115), encArg(x_24))) :|: z = 1 + (1 + x_115 + x_24), x_115 >= 0, x_24 >= 0 encArg(z) -{ 0 }-> g(1 + encArg(z - 2)) :|: z - 2 >= 0 encArg(z) -{ 0 }-> f(g(encArg(x_11)), g(encArg(x_110))) :|: x_11 >= 0, z = 1 + (1 + x_11) + (1 + x_110), x_110 >= 0 encArg(z) -{ 0 }-> f(g(encArg(x_11)), f(encArg(x_19), encArg(x_22))) :|: x_11 >= 0, z = 1 + (1 + x_11) + (1 + x_19 + x_22), x_22 >= 0, x_19 >= 0 encArg(z) -{ 0 }-> f(g(encArg(x_11)), 0) :|: x_11 >= 0, z = 1 + (1 + x_11) + x_2, x_2 >= 0 encArg(z) -{ 0 }-> f(g(encArg(x_11)), 1 + encArg(x_18)) :|: x_11 >= 0, z = 1 + (1 + x_11) + (1 + x_18), x_18 >= 0 encArg(z) -{ 0 }-> f(f(encArg(x_1''), encArg(x_2')), g(encArg(x_17))) :|: x_1'' >= 0, z = 1 + (1 + x_1'' + x_2') + (1 + x_17), x_2' >= 0, x_17 >= 0 encArg(z) -{ 0 }-> f(f(encArg(x_1''), encArg(x_2')), f(encArg(x_16), encArg(x_21))) :|: x_1'' >= 0, x_16 >= 0, x_2' >= 0, z = 1 + (1 + x_1'' + x_2') + (1 + x_16 + x_21), x_21 >= 0 encArg(z) -{ 0 }-> f(f(encArg(x_1''), encArg(x_2')), 0) :|: x_1'' >= 0, x_2' >= 0, z = 1 + (1 + x_1'' + x_2') + x_2, x_2 >= 0 encArg(z) -{ 0 }-> f(f(encArg(x_1''), encArg(x_2')), 1 + encArg(x_15)) :|: x_15 >= 0, z = 1 + (1 + x_1'' + x_2') + (1 + x_15), x_1'' >= 0, x_2' >= 0 encArg(z) -{ 0 }-> f(0, g(encArg(x_113))) :|: x_1 >= 0, x_113 >= 0, z = 1 + x_1 + (1 + x_113) encArg(z) -{ 0 }-> f(0, f(encArg(x_112), encArg(x_23))) :|: x_1 >= 0, z = 1 + x_1 + (1 + x_112 + x_23), x_23 >= 0, x_112 >= 0 encArg(z) -{ 0 }-> f(0, 0) :|: x_1 >= 0, z = 1 + x_1 + x_2, x_2 >= 0 encArg(z) -{ 0 }-> f(0, 1 + encArg(x_111)) :|: x_1 >= 0, z = 1 + x_1 + (1 + x_111), x_111 >= 0 encArg(z) -{ 0 }-> f(1 + encArg(x_1'), g(encArg(x_14))) :|: z = 1 + (1 + x_1') + (1 + x_14), x_14 >= 0, x_1' >= 0 encArg(z) -{ 0 }-> f(1 + encArg(x_1'), f(encArg(x_13), encArg(x_2''))) :|: x_13 >= 0, x_1' >= 0, x_2'' >= 0, z = 1 + (1 + x_1') + (1 + x_13 + x_2'') encArg(z) -{ 0 }-> f(1 + encArg(x_1'), 0) :|: x_1' >= 0, x_2 >= 0, z = 1 + (1 + x_1') + x_2 encArg(z) -{ 0 }-> f(1 + encArg(x_1'), 1 + encArg(x_12)) :|: z = 1 + (1 + x_1') + (1 + x_12), x_1' >= 0, x_12 >= 0 encArg(z) -{ 0 }-> 0 :|: z >= 0 encArg(z) -{ 1 }-> 1 + x :|: z - 1 >= 0, x >= 0, 0 = x encArg(z) -{ 0 }-> 1 + encArg(z - 1) :|: z - 1 >= 0 encode_f(z, z') -{ 0 }-> f(g(encArg(z - 1)), g(encArg(z' - 1))) :|: z' - 1 >= 0, z - 1 >= 0 encode_f(z, z') -{ 0 }-> f(g(encArg(z - 1)), f(encArg(x_127), encArg(x_28))) :|: x_127 >= 0, z' = 1 + x_127 + x_28, x_28 >= 0, z - 1 >= 0 encode_f(z, z') -{ 0 }-> f(g(encArg(z - 1)), 0) :|: z' >= 0, z - 1 >= 0 encode_f(z, z') -{ 0 }-> f(g(encArg(z - 1)), 1 + encArg(z' - 1)) :|: z' - 1 >= 0, z - 1 >= 0 encode_f(z, z') -{ 0 }-> f(f(encArg(x_118), encArg(x_25)), g(encArg(z' - 1))) :|: x_25 >= 0, z = 1 + x_118 + x_25, z' - 1 >= 0, x_118 >= 0 encode_f(z, z') -{ 0 }-> f(f(encArg(x_118), encArg(x_25)), f(encArg(x_124), encArg(x_27))) :|: x_124 >= 0, x_25 >= 0, z = 1 + x_118 + x_25, x_27 >= 0, x_118 >= 0, z' = 1 + x_124 + x_27 encode_f(z, z') -{ 0 }-> f(f(encArg(x_118), encArg(x_25)), 0) :|: x_25 >= 0, z = 1 + x_118 + x_25, z' >= 0, x_118 >= 0 encode_f(z, z') -{ 0 }-> f(f(encArg(x_118), encArg(x_25)), 1 + encArg(z' - 1)) :|: z' - 1 >= 0, x_25 >= 0, z = 1 + x_118 + x_25, x_118 >= 0 encode_f(z, z') -{ 0 }-> f(0, g(encArg(z' - 1))) :|: z >= 0, z' - 1 >= 0 encode_f(z, z') -{ 0 }-> f(0, f(encArg(x_130), encArg(x_29))) :|: z >= 0, x_130 >= 0, z' = 1 + x_130 + x_29, x_29 >= 0 encode_f(z, z') -{ 0 }-> f(0, 0) :|: z >= 0, z' >= 0 encode_f(z, z') -{ 0 }-> f(0, 1 + encArg(z' - 1)) :|: z >= 0, z' - 1 >= 0 encode_f(z, z') -{ 0 }-> f(1 + encArg(z - 1), g(encArg(z' - 1))) :|: z - 1 >= 0, z' - 1 >= 0 encode_f(z, z') -{ 0 }-> f(1 + encArg(z - 1), f(encArg(x_121), encArg(x_26))) :|: z - 1 >= 0, x_26 >= 0, z' = 1 + x_121 + x_26, x_121 >= 0 encode_f(z, z') -{ 0 }-> f(1 + encArg(z - 1), 0) :|: z - 1 >= 0, z' >= 0 encode_f(z, z') -{ 0 }-> f(1 + encArg(z - 1), 1 + encArg(z' - 1)) :|: z' - 1 >= 0, z - 1 >= 0 encode_f(z, z') -{ 0 }-> 0 :|: z >= 0, z' >= 0 encode_g(z) -{ 0 }-> g(g(encArg(z - 1))) :|: z - 1 >= 0 encode_g(z) -{ 0 }-> g(f(encArg(x_133), encArg(x_210))) :|: z = 1 + x_133 + x_210, x_133 >= 0, x_210 >= 0 encode_g(z) -{ 0 }-> g(1 + encArg(z - 1)) :|: z - 1 >= 0 encode_g(z) -{ 0 }-> 0 :|: z >= 0 encode_g(z) -{ 1 }-> 1 + x :|: z >= 0, x >= 0, 0 = x encode_s(z) -{ 0 }-> 0 :|: z >= 0 encode_s(z) -{ 0 }-> 1 + encArg(z) :|: z >= 0 f(z, z') -{ 2 }-> f(1 + z', z') :|: z' >= 0, z = z' f(z, z') -{ 0 }-> 0 :|: z >= 0, z' >= 0 g(z) -{ 1 }-> 1 + z :|: z >= 0 Function symbols to be analyzed: {f}, {encArg}, {encode_f}, {encode_g}, {encode_s} Previous analysis results are: g: runtime: O(1) [1], size: O(n^1) [1 + z] ---------------------------------------- (27) ResultPropagationProof (UPPER BOUND(ID)) Applied inner abstraction using the recently inferred runtime/size bounds where possible. ---------------------------------------- (28) Obligation: Complexity RNTS consisting of the following rules: encArg(z) -{ 0 }-> g(g(encArg(z - 2))) :|: z - 2 >= 0 encArg(z) -{ 0 }-> g(f(encArg(x_115), encArg(x_24))) :|: z = 1 + (1 + x_115 + x_24), x_115 >= 0, x_24 >= 0 encArg(z) -{ 0 }-> g(1 + encArg(z - 2)) :|: z - 2 >= 0 encArg(z) -{ 0 }-> f(g(encArg(x_11)), g(encArg(x_110))) :|: x_11 >= 0, z = 1 + (1 + x_11) + (1 + x_110), x_110 >= 0 encArg(z) -{ 0 }-> f(g(encArg(x_11)), f(encArg(x_19), encArg(x_22))) :|: x_11 >= 0, z = 1 + (1 + x_11) + (1 + x_19 + x_22), x_22 >= 0, x_19 >= 0 encArg(z) -{ 0 }-> f(g(encArg(x_11)), 0) :|: x_11 >= 0, z = 1 + (1 + x_11) + x_2, x_2 >= 0 encArg(z) -{ 0 }-> f(g(encArg(x_11)), 1 + encArg(x_18)) :|: x_11 >= 0, z = 1 + (1 + x_11) + (1 + x_18), x_18 >= 0 encArg(z) -{ 0 }-> f(f(encArg(x_1''), encArg(x_2')), g(encArg(x_17))) :|: x_1'' >= 0, z = 1 + (1 + x_1'' + x_2') + (1 + x_17), x_2' >= 0, x_17 >= 0 encArg(z) -{ 0 }-> f(f(encArg(x_1''), encArg(x_2')), f(encArg(x_16), encArg(x_21))) :|: x_1'' >= 0, x_16 >= 0, x_2' >= 0, z = 1 + (1 + x_1'' + x_2') + (1 + x_16 + x_21), x_21 >= 0 encArg(z) -{ 0 }-> f(f(encArg(x_1''), encArg(x_2')), 0) :|: x_1'' >= 0, x_2' >= 0, z = 1 + (1 + x_1'' + x_2') + x_2, x_2 >= 0 encArg(z) -{ 0 }-> f(f(encArg(x_1''), encArg(x_2')), 1 + encArg(x_15)) :|: x_15 >= 0, z = 1 + (1 + x_1'' + x_2') + (1 + x_15), x_1'' >= 0, x_2' >= 0 encArg(z) -{ 0 }-> f(0, g(encArg(x_113))) :|: x_1 >= 0, x_113 >= 0, z = 1 + x_1 + (1 + x_113) encArg(z) -{ 0 }-> f(0, f(encArg(x_112), encArg(x_23))) :|: x_1 >= 0, z = 1 + x_1 + (1 + x_112 + x_23), x_23 >= 0, x_112 >= 0 encArg(z) -{ 0 }-> f(0, 0) :|: x_1 >= 0, z = 1 + x_1 + x_2, x_2 >= 0 encArg(z) -{ 0 }-> f(0, 1 + encArg(x_111)) :|: x_1 >= 0, z = 1 + x_1 + (1 + x_111), x_111 >= 0 encArg(z) -{ 0 }-> f(1 + encArg(x_1'), g(encArg(x_14))) :|: z = 1 + (1 + x_1') + (1 + x_14), x_14 >= 0, x_1' >= 0 encArg(z) -{ 0 }-> f(1 + encArg(x_1'), f(encArg(x_13), encArg(x_2''))) :|: x_13 >= 0, x_1' >= 0, x_2'' >= 0, z = 1 + (1 + x_1') + (1 + x_13 + x_2'') encArg(z) -{ 0 }-> f(1 + encArg(x_1'), 0) :|: x_1' >= 0, x_2 >= 0, z = 1 + (1 + x_1') + x_2 encArg(z) -{ 0 }-> f(1 + encArg(x_1'), 1 + encArg(x_12)) :|: z = 1 + (1 + x_1') + (1 + x_12), x_1' >= 0, x_12 >= 0 encArg(z) -{ 0 }-> 0 :|: z >= 0 encArg(z) -{ 1 }-> 1 + x :|: z - 1 >= 0, x >= 0, 0 = x encArg(z) -{ 0 }-> 1 + encArg(z - 1) :|: z - 1 >= 0 encode_f(z, z') -{ 0 }-> f(g(encArg(z - 1)), g(encArg(z' - 1))) :|: z' - 1 >= 0, z - 1 >= 0 encode_f(z, z') -{ 0 }-> f(g(encArg(z - 1)), f(encArg(x_127), encArg(x_28))) :|: x_127 >= 0, z' = 1 + x_127 + x_28, x_28 >= 0, z - 1 >= 0 encode_f(z, z') -{ 0 }-> f(g(encArg(z - 1)), 0) :|: z' >= 0, z - 1 >= 0 encode_f(z, z') -{ 0 }-> f(g(encArg(z - 1)), 1 + encArg(z' - 1)) :|: z' - 1 >= 0, z - 1 >= 0 encode_f(z, z') -{ 0 }-> f(f(encArg(x_118), encArg(x_25)), g(encArg(z' - 1))) :|: x_25 >= 0, z = 1 + x_118 + x_25, z' - 1 >= 0, x_118 >= 0 encode_f(z, z') -{ 0 }-> f(f(encArg(x_118), encArg(x_25)), f(encArg(x_124), encArg(x_27))) :|: x_124 >= 0, x_25 >= 0, z = 1 + x_118 + x_25, x_27 >= 0, x_118 >= 0, z' = 1 + x_124 + x_27 encode_f(z, z') -{ 0 }-> f(f(encArg(x_118), encArg(x_25)), 0) :|: x_25 >= 0, z = 1 + x_118 + x_25, z' >= 0, x_118 >= 0 encode_f(z, z') -{ 0 }-> f(f(encArg(x_118), encArg(x_25)), 1 + encArg(z' - 1)) :|: z' - 1 >= 0, x_25 >= 0, z = 1 + x_118 + x_25, x_118 >= 0 encode_f(z, z') -{ 0 }-> f(0, g(encArg(z' - 1))) :|: z >= 0, z' - 1 >= 0 encode_f(z, z') -{ 0 }-> f(0, f(encArg(x_130), encArg(x_29))) :|: z >= 0, x_130 >= 0, z' = 1 + x_130 + x_29, x_29 >= 0 encode_f(z, z') -{ 0 }-> f(0, 0) :|: z >= 0, z' >= 0 encode_f(z, z') -{ 0 }-> f(0, 1 + encArg(z' - 1)) :|: z >= 0, z' - 1 >= 0 encode_f(z, z') -{ 0 }-> f(1 + encArg(z - 1), g(encArg(z' - 1))) :|: z - 1 >= 0, z' - 1 >= 0 encode_f(z, z') -{ 0 }-> f(1 + encArg(z - 1), f(encArg(x_121), encArg(x_26))) :|: z - 1 >= 0, x_26 >= 0, z' = 1 + x_121 + x_26, x_121 >= 0 encode_f(z, z') -{ 0 }-> f(1 + encArg(z - 1), 0) :|: z - 1 >= 0, z' >= 0 encode_f(z, z') -{ 0 }-> f(1 + encArg(z - 1), 1 + encArg(z' - 1)) :|: z' - 1 >= 0, z - 1 >= 0 encode_f(z, z') -{ 0 }-> 0 :|: z >= 0, z' >= 0 encode_g(z) -{ 0 }-> g(g(encArg(z - 1))) :|: z - 1 >= 0 encode_g(z) -{ 0 }-> g(f(encArg(x_133), encArg(x_210))) :|: z = 1 + x_133 + x_210, x_133 >= 0, x_210 >= 0 encode_g(z) -{ 0 }-> g(1 + encArg(z - 1)) :|: z - 1 >= 0 encode_g(z) -{ 0 }-> 0 :|: z >= 0 encode_g(z) -{ 1 }-> 1 + x :|: z >= 0, x >= 0, 0 = x encode_s(z) -{ 0 }-> 0 :|: z >= 0 encode_s(z) -{ 0 }-> 1 + encArg(z) :|: z >= 0 f(z, z') -{ 2 }-> f(1 + z', z') :|: z' >= 0, z = z' f(z, z') -{ 0 }-> 0 :|: z >= 0, z' >= 0 g(z) -{ 1 }-> 1 + z :|: z >= 0 Function symbols to be analyzed: {f}, {encArg}, {encode_f}, {encode_g}, {encode_s} Previous analysis results are: g: runtime: O(1) [1], size: O(n^1) [1 + z] ---------------------------------------- (29) IntTrsBoundProof (UPPER BOUND(ID)) Computed SIZE bound using CoFloCo for: f after applying outer abstraction to obtain an ITS, resulting in: O(1) with polynomial bound: 0 ---------------------------------------- (30) Obligation: Complexity RNTS consisting of the following rules: encArg(z) -{ 0 }-> g(g(encArg(z - 2))) :|: z - 2 >= 0 encArg(z) -{ 0 }-> g(f(encArg(x_115), encArg(x_24))) :|: z = 1 + (1 + x_115 + x_24), x_115 >= 0, x_24 >= 0 encArg(z) -{ 0 }-> g(1 + encArg(z - 2)) :|: z - 2 >= 0 encArg(z) -{ 0 }-> f(g(encArg(x_11)), g(encArg(x_110))) :|: x_11 >= 0, z = 1 + (1 + x_11) + (1 + x_110), x_110 >= 0 encArg(z) -{ 0 }-> f(g(encArg(x_11)), f(encArg(x_19), encArg(x_22))) :|: x_11 >= 0, z = 1 + (1 + x_11) + (1 + x_19 + x_22), x_22 >= 0, x_19 >= 0 encArg(z) -{ 0 }-> f(g(encArg(x_11)), 0) :|: x_11 >= 0, z = 1 + (1 + x_11) + x_2, x_2 >= 0 encArg(z) -{ 0 }-> f(g(encArg(x_11)), 1 + encArg(x_18)) :|: x_11 >= 0, z = 1 + (1 + x_11) + (1 + x_18), x_18 >= 0 encArg(z) -{ 0 }-> f(f(encArg(x_1''), encArg(x_2')), g(encArg(x_17))) :|: x_1'' >= 0, z = 1 + (1 + x_1'' + x_2') + (1 + x_17), x_2' >= 0, x_17 >= 0 encArg(z) -{ 0 }-> f(f(encArg(x_1''), encArg(x_2')), f(encArg(x_16), encArg(x_21))) :|: x_1'' >= 0, x_16 >= 0, x_2' >= 0, z = 1 + (1 + x_1'' + x_2') + (1 + x_16 + x_21), x_21 >= 0 encArg(z) -{ 0 }-> f(f(encArg(x_1''), encArg(x_2')), 0) :|: x_1'' >= 0, x_2' >= 0, z = 1 + (1 + x_1'' + x_2') + x_2, x_2 >= 0 encArg(z) -{ 0 }-> f(f(encArg(x_1''), encArg(x_2')), 1 + encArg(x_15)) :|: x_15 >= 0, z = 1 + (1 + x_1'' + x_2') + (1 + x_15), x_1'' >= 0, x_2' >= 0 encArg(z) -{ 0 }-> f(0, g(encArg(x_113))) :|: x_1 >= 0, x_113 >= 0, z = 1 + x_1 + (1 + x_113) encArg(z) -{ 0 }-> f(0, f(encArg(x_112), encArg(x_23))) :|: x_1 >= 0, z = 1 + x_1 + (1 + x_112 + x_23), x_23 >= 0, x_112 >= 0 encArg(z) -{ 0 }-> f(0, 0) :|: x_1 >= 0, z = 1 + x_1 + x_2, x_2 >= 0 encArg(z) -{ 0 }-> f(0, 1 + encArg(x_111)) :|: x_1 >= 0, z = 1 + x_1 + (1 + x_111), x_111 >= 0 encArg(z) -{ 0 }-> f(1 + encArg(x_1'), g(encArg(x_14))) :|: z = 1 + (1 + x_1') + (1 + x_14), x_14 >= 0, x_1' >= 0 encArg(z) -{ 0 }-> f(1 + encArg(x_1'), f(encArg(x_13), encArg(x_2''))) :|: x_13 >= 0, x_1' >= 0, x_2'' >= 0, z = 1 + (1 + x_1') + (1 + x_13 + x_2'') encArg(z) -{ 0 }-> f(1 + encArg(x_1'), 0) :|: x_1' >= 0, x_2 >= 0, z = 1 + (1 + x_1') + x_2 encArg(z) -{ 0 }-> f(1 + encArg(x_1'), 1 + encArg(x_12)) :|: z = 1 + (1 + x_1') + (1 + x_12), x_1' >= 0, x_12 >= 0 encArg(z) -{ 0 }-> 0 :|: z >= 0 encArg(z) -{ 1 }-> 1 + x :|: z - 1 >= 0, x >= 0, 0 = x encArg(z) -{ 0 }-> 1 + encArg(z - 1) :|: z - 1 >= 0 encode_f(z, z') -{ 0 }-> f(g(encArg(z - 1)), g(encArg(z' - 1))) :|: z' - 1 >= 0, z - 1 >= 0 encode_f(z, z') -{ 0 }-> f(g(encArg(z - 1)), f(encArg(x_127), encArg(x_28))) :|: x_127 >= 0, z' = 1 + x_127 + x_28, x_28 >= 0, z - 1 >= 0 encode_f(z, z') -{ 0 }-> f(g(encArg(z - 1)), 0) :|: z' >= 0, z - 1 >= 0 encode_f(z, z') -{ 0 }-> f(g(encArg(z - 1)), 1 + encArg(z' - 1)) :|: z' - 1 >= 0, z - 1 >= 0 encode_f(z, z') -{ 0 }-> f(f(encArg(x_118), encArg(x_25)), g(encArg(z' - 1))) :|: x_25 >= 0, z = 1 + x_118 + x_25, z' - 1 >= 0, x_118 >= 0 encode_f(z, z') -{ 0 }-> f(f(encArg(x_118), encArg(x_25)), f(encArg(x_124), encArg(x_27))) :|: x_124 >= 0, x_25 >= 0, z = 1 + x_118 + x_25, x_27 >= 0, x_118 >= 0, z' = 1 + x_124 + x_27 encode_f(z, z') -{ 0 }-> f(f(encArg(x_118), encArg(x_25)), 0) :|: x_25 >= 0, z = 1 + x_118 + x_25, z' >= 0, x_118 >= 0 encode_f(z, z') -{ 0 }-> f(f(encArg(x_118), encArg(x_25)), 1 + encArg(z' - 1)) :|: z' - 1 >= 0, x_25 >= 0, z = 1 + x_118 + x_25, x_118 >= 0 encode_f(z, z') -{ 0 }-> f(0, g(encArg(z' - 1))) :|: z >= 0, z' - 1 >= 0 encode_f(z, z') -{ 0 }-> f(0, f(encArg(x_130), encArg(x_29))) :|: z >= 0, x_130 >= 0, z' = 1 + x_130 + x_29, x_29 >= 0 encode_f(z, z') -{ 0 }-> f(0, 0) :|: z >= 0, z' >= 0 encode_f(z, z') -{ 0 }-> f(0, 1 + encArg(z' - 1)) :|: z >= 0, z' - 1 >= 0 encode_f(z, z') -{ 0 }-> f(1 + encArg(z - 1), g(encArg(z' - 1))) :|: z - 1 >= 0, z' - 1 >= 0 encode_f(z, z') -{ 0 }-> f(1 + encArg(z - 1), f(encArg(x_121), encArg(x_26))) :|: z - 1 >= 0, x_26 >= 0, z' = 1 + x_121 + x_26, x_121 >= 0 encode_f(z, z') -{ 0 }-> f(1 + encArg(z - 1), 0) :|: z - 1 >= 0, z' >= 0 encode_f(z, z') -{ 0 }-> f(1 + encArg(z - 1), 1 + encArg(z' - 1)) :|: z' - 1 >= 0, z - 1 >= 0 encode_f(z, z') -{ 0 }-> 0 :|: z >= 0, z' >= 0 encode_g(z) -{ 0 }-> g(g(encArg(z - 1))) :|: z - 1 >= 0 encode_g(z) -{ 0 }-> g(f(encArg(x_133), encArg(x_210))) :|: z = 1 + x_133 + x_210, x_133 >= 0, x_210 >= 0 encode_g(z) -{ 0 }-> g(1 + encArg(z - 1)) :|: z - 1 >= 0 encode_g(z) -{ 0 }-> 0 :|: z >= 0 encode_g(z) -{ 1 }-> 1 + x :|: z >= 0, x >= 0, 0 = x encode_s(z) -{ 0 }-> 0 :|: z >= 0 encode_s(z) -{ 0 }-> 1 + encArg(z) :|: z >= 0 f(z, z') -{ 2 }-> f(1 + z', z') :|: z' >= 0, z = z' f(z, z') -{ 0 }-> 0 :|: z >= 0, z' >= 0 g(z) -{ 1 }-> 1 + z :|: z >= 0 Function symbols to be analyzed: {f}, {encArg}, {encode_f}, {encode_g}, {encode_s} Previous analysis results are: g: runtime: O(1) [1], size: O(n^1) [1 + z] f: runtime: ?, size: O(1) [0] ---------------------------------------- (31) IntTrsBoundProof (UPPER BOUND(ID)) Computed RUNTIME bound using CoFloCo for: f after applying outer abstraction to obtain an ITS, resulting in: O(1) with polynomial bound: 2 ---------------------------------------- (32) Obligation: Complexity RNTS consisting of the following rules: encArg(z) -{ 0 }-> g(g(encArg(z - 2))) :|: z - 2 >= 0 encArg(z) -{ 0 }-> g(f(encArg(x_115), encArg(x_24))) :|: z = 1 + (1 + x_115 + x_24), x_115 >= 0, x_24 >= 0 encArg(z) -{ 0 }-> g(1 + encArg(z - 2)) :|: z - 2 >= 0 encArg(z) -{ 0 }-> f(g(encArg(x_11)), g(encArg(x_110))) :|: x_11 >= 0, z = 1 + (1 + x_11) + (1 + x_110), x_110 >= 0 encArg(z) -{ 0 }-> f(g(encArg(x_11)), f(encArg(x_19), encArg(x_22))) :|: x_11 >= 0, z = 1 + (1 + x_11) + (1 + x_19 + x_22), x_22 >= 0, x_19 >= 0 encArg(z) -{ 0 }-> f(g(encArg(x_11)), 0) :|: x_11 >= 0, z = 1 + (1 + x_11) + x_2, x_2 >= 0 encArg(z) -{ 0 }-> f(g(encArg(x_11)), 1 + encArg(x_18)) :|: x_11 >= 0, z = 1 + (1 + x_11) + (1 + x_18), x_18 >= 0 encArg(z) -{ 0 }-> f(f(encArg(x_1''), encArg(x_2')), g(encArg(x_17))) :|: x_1'' >= 0, z = 1 + (1 + x_1'' + x_2') + (1 + x_17), x_2' >= 0, x_17 >= 0 encArg(z) -{ 0 }-> f(f(encArg(x_1''), encArg(x_2')), f(encArg(x_16), encArg(x_21))) :|: x_1'' >= 0, x_16 >= 0, x_2' >= 0, z = 1 + (1 + x_1'' + x_2') + (1 + x_16 + x_21), x_21 >= 0 encArg(z) -{ 0 }-> f(f(encArg(x_1''), encArg(x_2')), 0) :|: x_1'' >= 0, x_2' >= 0, z = 1 + (1 + x_1'' + x_2') + x_2, x_2 >= 0 encArg(z) -{ 0 }-> f(f(encArg(x_1''), encArg(x_2')), 1 + encArg(x_15)) :|: x_15 >= 0, z = 1 + (1 + x_1'' + x_2') + (1 + x_15), x_1'' >= 0, x_2' >= 0 encArg(z) -{ 0 }-> f(0, g(encArg(x_113))) :|: x_1 >= 0, x_113 >= 0, z = 1 + x_1 + (1 + x_113) encArg(z) -{ 0 }-> f(0, f(encArg(x_112), encArg(x_23))) :|: x_1 >= 0, z = 1 + x_1 + (1 + x_112 + x_23), x_23 >= 0, x_112 >= 0 encArg(z) -{ 0 }-> f(0, 0) :|: x_1 >= 0, z = 1 + x_1 + x_2, x_2 >= 0 encArg(z) -{ 0 }-> f(0, 1 + encArg(x_111)) :|: x_1 >= 0, z = 1 + x_1 + (1 + x_111), x_111 >= 0 encArg(z) -{ 0 }-> f(1 + encArg(x_1'), g(encArg(x_14))) :|: z = 1 + (1 + x_1') + (1 + x_14), x_14 >= 0, x_1' >= 0 encArg(z) -{ 0 }-> f(1 + encArg(x_1'), f(encArg(x_13), encArg(x_2''))) :|: x_13 >= 0, x_1' >= 0, x_2'' >= 0, z = 1 + (1 + x_1') + (1 + x_13 + x_2'') encArg(z) -{ 0 }-> f(1 + encArg(x_1'), 0) :|: x_1' >= 0, x_2 >= 0, z = 1 + (1 + x_1') + x_2 encArg(z) -{ 0 }-> f(1 + encArg(x_1'), 1 + encArg(x_12)) :|: z = 1 + (1 + x_1') + (1 + x_12), x_1' >= 0, x_12 >= 0 encArg(z) -{ 0 }-> 0 :|: z >= 0 encArg(z) -{ 1 }-> 1 + x :|: z - 1 >= 0, x >= 0, 0 = x encArg(z) -{ 0 }-> 1 + encArg(z - 1) :|: z - 1 >= 0 encode_f(z, z') -{ 0 }-> f(g(encArg(z - 1)), g(encArg(z' - 1))) :|: z' - 1 >= 0, z - 1 >= 0 encode_f(z, z') -{ 0 }-> f(g(encArg(z - 1)), f(encArg(x_127), encArg(x_28))) :|: x_127 >= 0, z' = 1 + x_127 + x_28, x_28 >= 0, z - 1 >= 0 encode_f(z, z') -{ 0 }-> f(g(encArg(z - 1)), 0) :|: z' >= 0, z - 1 >= 0 encode_f(z, z') -{ 0 }-> f(g(encArg(z - 1)), 1 + encArg(z' - 1)) :|: z' - 1 >= 0, z - 1 >= 0 encode_f(z, z') -{ 0 }-> f(f(encArg(x_118), encArg(x_25)), g(encArg(z' - 1))) :|: x_25 >= 0, z = 1 + x_118 + x_25, z' - 1 >= 0, x_118 >= 0 encode_f(z, z') -{ 0 }-> f(f(encArg(x_118), encArg(x_25)), f(encArg(x_124), encArg(x_27))) :|: x_124 >= 0, x_25 >= 0, z = 1 + x_118 + x_25, x_27 >= 0, x_118 >= 0, z' = 1 + x_124 + x_27 encode_f(z, z') -{ 0 }-> f(f(encArg(x_118), encArg(x_25)), 0) :|: x_25 >= 0, z = 1 + x_118 + x_25, z' >= 0, x_118 >= 0 encode_f(z, z') -{ 0 }-> f(f(encArg(x_118), encArg(x_25)), 1 + encArg(z' - 1)) :|: z' - 1 >= 0, x_25 >= 0, z = 1 + x_118 + x_25, x_118 >= 0 encode_f(z, z') -{ 0 }-> f(0, g(encArg(z' - 1))) :|: z >= 0, z' - 1 >= 0 encode_f(z, z') -{ 0 }-> f(0, f(encArg(x_130), encArg(x_29))) :|: z >= 0, x_130 >= 0, z' = 1 + x_130 + x_29, x_29 >= 0 encode_f(z, z') -{ 0 }-> f(0, 0) :|: z >= 0, z' >= 0 encode_f(z, z') -{ 0 }-> f(0, 1 + encArg(z' - 1)) :|: z >= 0, z' - 1 >= 0 encode_f(z, z') -{ 0 }-> f(1 + encArg(z - 1), g(encArg(z' - 1))) :|: z - 1 >= 0, z' - 1 >= 0 encode_f(z, z') -{ 0 }-> f(1 + encArg(z - 1), f(encArg(x_121), encArg(x_26))) :|: z - 1 >= 0, x_26 >= 0, z' = 1 + x_121 + x_26, x_121 >= 0 encode_f(z, z') -{ 0 }-> f(1 + encArg(z - 1), 0) :|: z - 1 >= 0, z' >= 0 encode_f(z, z') -{ 0 }-> f(1 + encArg(z - 1), 1 + encArg(z' - 1)) :|: z' - 1 >= 0, z - 1 >= 0 encode_f(z, z') -{ 0 }-> 0 :|: z >= 0, z' >= 0 encode_g(z) -{ 0 }-> g(g(encArg(z - 1))) :|: z - 1 >= 0 encode_g(z) -{ 0 }-> g(f(encArg(x_133), encArg(x_210))) :|: z = 1 + x_133 + x_210, x_133 >= 0, x_210 >= 0 encode_g(z) -{ 0 }-> g(1 + encArg(z - 1)) :|: z - 1 >= 0 encode_g(z) -{ 0 }-> 0 :|: z >= 0 encode_g(z) -{ 1 }-> 1 + x :|: z >= 0, x >= 0, 0 = x encode_s(z) -{ 0 }-> 0 :|: z >= 0 encode_s(z) -{ 0 }-> 1 + encArg(z) :|: z >= 0 f(z, z') -{ 2 }-> f(1 + z', z') :|: z' >= 0, z = z' f(z, z') -{ 0 }-> 0 :|: z >= 0, z' >= 0 g(z) -{ 1 }-> 1 + z :|: z >= 0 Function symbols to be analyzed: {encArg}, {encode_f}, {encode_g}, {encode_s} Previous analysis results are: g: runtime: O(1) [1], size: O(n^1) [1 + z] f: runtime: O(1) [2], size: O(1) [0] ---------------------------------------- (33) ResultPropagationProof (UPPER BOUND(ID)) Applied inner abstraction using the recently inferred runtime/size bounds where possible. ---------------------------------------- (34) Obligation: Complexity RNTS consisting of the following rules: encArg(z) -{ 2 }-> s' :|: s' >= 0, s' <= 0, x_1 >= 0, z = 1 + x_1 + x_2, x_2 >= 0 encArg(z) -{ 0 }-> g(g(encArg(z - 2))) :|: z - 2 >= 0 encArg(z) -{ 0 }-> g(f(encArg(x_115), encArg(x_24))) :|: z = 1 + (1 + x_115 + x_24), x_115 >= 0, x_24 >= 0 encArg(z) -{ 0 }-> g(1 + encArg(z - 2)) :|: z - 2 >= 0 encArg(z) -{ 0 }-> f(g(encArg(x_11)), g(encArg(x_110))) :|: x_11 >= 0, z = 1 + (1 + x_11) + (1 + x_110), x_110 >= 0 encArg(z) -{ 0 }-> f(g(encArg(x_11)), f(encArg(x_19), encArg(x_22))) :|: x_11 >= 0, z = 1 + (1 + x_11) + (1 + x_19 + x_22), x_22 >= 0, x_19 >= 0 encArg(z) -{ 0 }-> f(g(encArg(x_11)), 0) :|: x_11 >= 0, z = 1 + (1 + x_11) + x_2, x_2 >= 0 encArg(z) -{ 0 }-> f(g(encArg(x_11)), 1 + encArg(x_18)) :|: x_11 >= 0, z = 1 + (1 + x_11) + (1 + x_18), x_18 >= 0 encArg(z) -{ 0 }-> f(f(encArg(x_1''), encArg(x_2')), g(encArg(x_17))) :|: x_1'' >= 0, z = 1 + (1 + x_1'' + x_2') + (1 + x_17), x_2' >= 0, x_17 >= 0 encArg(z) -{ 0 }-> f(f(encArg(x_1''), encArg(x_2')), f(encArg(x_16), encArg(x_21))) :|: x_1'' >= 0, x_16 >= 0, x_2' >= 0, z = 1 + (1 + x_1'' + x_2') + (1 + x_16 + x_21), x_21 >= 0 encArg(z) -{ 0 }-> f(f(encArg(x_1''), encArg(x_2')), 0) :|: x_1'' >= 0, x_2' >= 0, z = 1 + (1 + x_1'' + x_2') + x_2, x_2 >= 0 encArg(z) -{ 0 }-> f(f(encArg(x_1''), encArg(x_2')), 1 + encArg(x_15)) :|: x_15 >= 0, z = 1 + (1 + x_1'' + x_2') + (1 + x_15), x_1'' >= 0, x_2' >= 0 encArg(z) -{ 0 }-> f(0, g(encArg(x_113))) :|: x_1 >= 0, x_113 >= 0, z = 1 + x_1 + (1 + x_113) encArg(z) -{ 0 }-> f(0, f(encArg(x_112), encArg(x_23))) :|: x_1 >= 0, z = 1 + x_1 + (1 + x_112 + x_23), x_23 >= 0, x_112 >= 0 encArg(z) -{ 0 }-> f(0, 1 + encArg(x_111)) :|: x_1 >= 0, z = 1 + x_1 + (1 + x_111), x_111 >= 0 encArg(z) -{ 0 }-> f(1 + encArg(x_1'), g(encArg(x_14))) :|: z = 1 + (1 + x_1') + (1 + x_14), x_14 >= 0, x_1' >= 0 encArg(z) -{ 0 }-> f(1 + encArg(x_1'), f(encArg(x_13), encArg(x_2''))) :|: x_13 >= 0, x_1' >= 0, x_2'' >= 0, z = 1 + (1 + x_1') + (1 + x_13 + x_2'') encArg(z) -{ 0 }-> f(1 + encArg(x_1'), 0) :|: x_1' >= 0, x_2 >= 0, z = 1 + (1 + x_1') + x_2 encArg(z) -{ 0 }-> f(1 + encArg(x_1'), 1 + encArg(x_12)) :|: z = 1 + (1 + x_1') + (1 + x_12), x_1' >= 0, x_12 >= 0 encArg(z) -{ 0 }-> 0 :|: z >= 0 encArg(z) -{ 1 }-> 1 + x :|: z - 1 >= 0, x >= 0, 0 = x encArg(z) -{ 0 }-> 1 + encArg(z - 1) :|: z - 1 >= 0 encode_f(z, z') -{ 2 }-> s'' :|: s'' >= 0, s'' <= 0, z >= 0, z' >= 0 encode_f(z, z') -{ 0 }-> f(g(encArg(z - 1)), g(encArg(z' - 1))) :|: z' - 1 >= 0, z - 1 >= 0 encode_f(z, z') -{ 0 }-> f(g(encArg(z - 1)), f(encArg(x_127), encArg(x_28))) :|: x_127 >= 0, z' = 1 + x_127 + x_28, x_28 >= 0, z - 1 >= 0 encode_f(z, z') -{ 0 }-> f(g(encArg(z - 1)), 0) :|: z' >= 0, z - 1 >= 0 encode_f(z, z') -{ 0 }-> f(g(encArg(z - 1)), 1 + encArg(z' - 1)) :|: z' - 1 >= 0, z - 1 >= 0 encode_f(z, z') -{ 0 }-> f(f(encArg(x_118), encArg(x_25)), g(encArg(z' - 1))) :|: x_25 >= 0, z = 1 + x_118 + x_25, z' - 1 >= 0, x_118 >= 0 encode_f(z, z') -{ 0 }-> f(f(encArg(x_118), encArg(x_25)), f(encArg(x_124), encArg(x_27))) :|: x_124 >= 0, x_25 >= 0, z = 1 + x_118 + x_25, x_27 >= 0, x_118 >= 0, z' = 1 + x_124 + x_27 encode_f(z, z') -{ 0 }-> f(f(encArg(x_118), encArg(x_25)), 0) :|: x_25 >= 0, z = 1 + x_118 + x_25, z' >= 0, x_118 >= 0 encode_f(z, z') -{ 0 }-> f(f(encArg(x_118), encArg(x_25)), 1 + encArg(z' - 1)) :|: z' - 1 >= 0, x_25 >= 0, z = 1 + x_118 + x_25, x_118 >= 0 encode_f(z, z') -{ 0 }-> f(0, g(encArg(z' - 1))) :|: z >= 0, z' - 1 >= 0 encode_f(z, z') -{ 0 }-> f(0, f(encArg(x_130), encArg(x_29))) :|: z >= 0, x_130 >= 0, z' = 1 + x_130 + x_29, x_29 >= 0 encode_f(z, z') -{ 0 }-> f(0, 1 + encArg(z' - 1)) :|: z >= 0, z' - 1 >= 0 encode_f(z, z') -{ 0 }-> f(1 + encArg(z - 1), g(encArg(z' - 1))) :|: z - 1 >= 0, z' - 1 >= 0 encode_f(z, z') -{ 0 }-> f(1 + encArg(z - 1), f(encArg(x_121), encArg(x_26))) :|: z - 1 >= 0, x_26 >= 0, z' = 1 + x_121 + x_26, x_121 >= 0 encode_f(z, z') -{ 0 }-> f(1 + encArg(z - 1), 0) :|: z - 1 >= 0, z' >= 0 encode_f(z, z') -{ 0 }-> f(1 + encArg(z - 1), 1 + encArg(z' - 1)) :|: z' - 1 >= 0, z - 1 >= 0 encode_f(z, z') -{ 0 }-> 0 :|: z >= 0, z' >= 0 encode_g(z) -{ 0 }-> g(g(encArg(z - 1))) :|: z - 1 >= 0 encode_g(z) -{ 0 }-> g(f(encArg(x_133), encArg(x_210))) :|: z = 1 + x_133 + x_210, x_133 >= 0, x_210 >= 0 encode_g(z) -{ 0 }-> g(1 + encArg(z - 1)) :|: z - 1 >= 0 encode_g(z) -{ 0 }-> 0 :|: z >= 0 encode_g(z) -{ 1 }-> 1 + x :|: z >= 0, x >= 0, 0 = x encode_s(z) -{ 0 }-> 0 :|: z >= 0 encode_s(z) -{ 0 }-> 1 + encArg(z) :|: z >= 0 f(z, z') -{ 4 }-> s :|: s >= 0, s <= 0, z' >= 0, z = z' f(z, z') -{ 0 }-> 0 :|: z >= 0, z' >= 0 g(z) -{ 1 }-> 1 + z :|: z >= 0 Function symbols to be analyzed: {encArg}, {encode_f}, {encode_g}, {encode_s} Previous analysis results are: g: runtime: O(1) [1], size: O(n^1) [1 + z] f: runtime: O(1) [2], size: O(1) [0] ---------------------------------------- (35) IntTrsBoundProof (UPPER BOUND(ID)) Computed SIZE bound using KoAT for: encArg after applying outer abstraction to obtain an ITS, resulting in: O(n^1) with polynomial bound: z ---------------------------------------- (36) Obligation: Complexity RNTS consisting of the following rules: encArg(z) -{ 2 }-> s' :|: s' >= 0, s' <= 0, x_1 >= 0, z = 1 + x_1 + x_2, x_2 >= 0 encArg(z) -{ 0 }-> g(g(encArg(z - 2))) :|: z - 2 >= 0 encArg(z) -{ 0 }-> g(f(encArg(x_115), encArg(x_24))) :|: z = 1 + (1 + x_115 + x_24), x_115 >= 0, x_24 >= 0 encArg(z) -{ 0 }-> g(1 + encArg(z - 2)) :|: z - 2 >= 0 encArg(z) -{ 0 }-> f(g(encArg(x_11)), g(encArg(x_110))) :|: x_11 >= 0, z = 1 + (1 + x_11) + (1 + x_110), x_110 >= 0 encArg(z) -{ 0 }-> f(g(encArg(x_11)), f(encArg(x_19), encArg(x_22))) :|: x_11 >= 0, z = 1 + (1 + x_11) + (1 + x_19 + x_22), x_22 >= 0, x_19 >= 0 encArg(z) -{ 0 }-> f(g(encArg(x_11)), 0) :|: x_11 >= 0, z = 1 + (1 + x_11) + x_2, x_2 >= 0 encArg(z) -{ 0 }-> f(g(encArg(x_11)), 1 + encArg(x_18)) :|: x_11 >= 0, z = 1 + (1 + x_11) + (1 + x_18), x_18 >= 0 encArg(z) -{ 0 }-> f(f(encArg(x_1''), encArg(x_2')), g(encArg(x_17))) :|: x_1'' >= 0, z = 1 + (1 + x_1'' + x_2') + (1 + x_17), x_2' >= 0, x_17 >= 0 encArg(z) -{ 0 }-> f(f(encArg(x_1''), encArg(x_2')), f(encArg(x_16), encArg(x_21))) :|: x_1'' >= 0, x_16 >= 0, x_2' >= 0, z = 1 + (1 + x_1'' + x_2') + (1 + x_16 + x_21), x_21 >= 0 encArg(z) -{ 0 }-> f(f(encArg(x_1''), encArg(x_2')), 0) :|: x_1'' >= 0, x_2' >= 0, z = 1 + (1 + x_1'' + x_2') + x_2, x_2 >= 0 encArg(z) -{ 0 }-> f(f(encArg(x_1''), encArg(x_2')), 1 + encArg(x_15)) :|: x_15 >= 0, z = 1 + (1 + x_1'' + x_2') + (1 + x_15), x_1'' >= 0, x_2' >= 0 encArg(z) -{ 0 }-> f(0, g(encArg(x_113))) :|: x_1 >= 0, x_113 >= 0, z = 1 + x_1 + (1 + x_113) encArg(z) -{ 0 }-> f(0, f(encArg(x_112), encArg(x_23))) :|: x_1 >= 0, z = 1 + x_1 + (1 + x_112 + x_23), x_23 >= 0, x_112 >= 0 encArg(z) -{ 0 }-> f(0, 1 + encArg(x_111)) :|: x_1 >= 0, z = 1 + x_1 + (1 + x_111), x_111 >= 0 encArg(z) -{ 0 }-> f(1 + encArg(x_1'), g(encArg(x_14))) :|: z = 1 + (1 + x_1') + (1 + x_14), x_14 >= 0, x_1' >= 0 encArg(z) -{ 0 }-> f(1 + encArg(x_1'), f(encArg(x_13), encArg(x_2''))) :|: x_13 >= 0, x_1' >= 0, x_2'' >= 0, z = 1 + (1 + x_1') + (1 + x_13 + x_2'') encArg(z) -{ 0 }-> f(1 + encArg(x_1'), 0) :|: x_1' >= 0, x_2 >= 0, z = 1 + (1 + x_1') + x_2 encArg(z) -{ 0 }-> f(1 + encArg(x_1'), 1 + encArg(x_12)) :|: z = 1 + (1 + x_1') + (1 + x_12), x_1' >= 0, x_12 >= 0 encArg(z) -{ 0 }-> 0 :|: z >= 0 encArg(z) -{ 1 }-> 1 + x :|: z - 1 >= 0, x >= 0, 0 = x encArg(z) -{ 0 }-> 1 + encArg(z - 1) :|: z - 1 >= 0 encode_f(z, z') -{ 2 }-> s'' :|: s'' >= 0, s'' <= 0, z >= 0, z' >= 0 encode_f(z, z') -{ 0 }-> f(g(encArg(z - 1)), g(encArg(z' - 1))) :|: z' - 1 >= 0, z - 1 >= 0 encode_f(z, z') -{ 0 }-> f(g(encArg(z - 1)), f(encArg(x_127), encArg(x_28))) :|: x_127 >= 0, z' = 1 + x_127 + x_28, x_28 >= 0, z - 1 >= 0 encode_f(z, z') -{ 0 }-> f(g(encArg(z - 1)), 0) :|: z' >= 0, z - 1 >= 0 encode_f(z, z') -{ 0 }-> f(g(encArg(z - 1)), 1 + encArg(z' - 1)) :|: z' - 1 >= 0, z - 1 >= 0 encode_f(z, z') -{ 0 }-> f(f(encArg(x_118), encArg(x_25)), g(encArg(z' - 1))) :|: x_25 >= 0, z = 1 + x_118 + x_25, z' - 1 >= 0, x_118 >= 0 encode_f(z, z') -{ 0 }-> f(f(encArg(x_118), encArg(x_25)), f(encArg(x_124), encArg(x_27))) :|: x_124 >= 0, x_25 >= 0, z = 1 + x_118 + x_25, x_27 >= 0, x_118 >= 0, z' = 1 + x_124 + x_27 encode_f(z, z') -{ 0 }-> f(f(encArg(x_118), encArg(x_25)), 0) :|: x_25 >= 0, z = 1 + x_118 + x_25, z' >= 0, x_118 >= 0 encode_f(z, z') -{ 0 }-> f(f(encArg(x_118), encArg(x_25)), 1 + encArg(z' - 1)) :|: z' - 1 >= 0, x_25 >= 0, z = 1 + x_118 + x_25, x_118 >= 0 encode_f(z, z') -{ 0 }-> f(0, g(encArg(z' - 1))) :|: z >= 0, z' - 1 >= 0 encode_f(z, z') -{ 0 }-> f(0, f(encArg(x_130), encArg(x_29))) :|: z >= 0, x_130 >= 0, z' = 1 + x_130 + x_29, x_29 >= 0 encode_f(z, z') -{ 0 }-> f(0, 1 + encArg(z' - 1)) :|: z >= 0, z' - 1 >= 0 encode_f(z, z') -{ 0 }-> f(1 + encArg(z - 1), g(encArg(z' - 1))) :|: z - 1 >= 0, z' - 1 >= 0 encode_f(z, z') -{ 0 }-> f(1 + encArg(z - 1), f(encArg(x_121), encArg(x_26))) :|: z - 1 >= 0, x_26 >= 0, z' = 1 + x_121 + x_26, x_121 >= 0 encode_f(z, z') -{ 0 }-> f(1 + encArg(z - 1), 0) :|: z - 1 >= 0, z' >= 0 encode_f(z, z') -{ 0 }-> f(1 + encArg(z - 1), 1 + encArg(z' - 1)) :|: z' - 1 >= 0, z - 1 >= 0 encode_f(z, z') -{ 0 }-> 0 :|: z >= 0, z' >= 0 encode_g(z) -{ 0 }-> g(g(encArg(z - 1))) :|: z - 1 >= 0 encode_g(z) -{ 0 }-> g(f(encArg(x_133), encArg(x_210))) :|: z = 1 + x_133 + x_210, x_133 >= 0, x_210 >= 0 encode_g(z) -{ 0 }-> g(1 + encArg(z - 1)) :|: z - 1 >= 0 encode_g(z) -{ 0 }-> 0 :|: z >= 0 encode_g(z) -{ 1 }-> 1 + x :|: z >= 0, x >= 0, 0 = x encode_s(z) -{ 0 }-> 0 :|: z >= 0 encode_s(z) -{ 0 }-> 1 + encArg(z) :|: z >= 0 f(z, z') -{ 4 }-> s :|: s >= 0, s <= 0, z' >= 0, z = z' f(z, z') -{ 0 }-> 0 :|: z >= 0, z' >= 0 g(z) -{ 1 }-> 1 + z :|: z >= 0 Function symbols to be analyzed: {encArg}, {encode_f}, {encode_g}, {encode_s} Previous analysis results are: g: runtime: O(1) [1], size: O(n^1) [1 + z] f: runtime: O(1) [2], size: O(1) [0] encArg: runtime: ?, size: O(n^1) [z] ---------------------------------------- (37) IntTrsBoundProof (UPPER BOUND(ID)) Computed RUNTIME bound using CoFloCo for: encArg after applying outer abstraction to obtain an ITS, resulting in: O(n^1) with polynomial bound: 2 + 13*z ---------------------------------------- (38) Obligation: Complexity RNTS consisting of the following rules: encArg(z) -{ 2 }-> s' :|: s' >= 0, s' <= 0, x_1 >= 0, z = 1 + x_1 + x_2, x_2 >= 0 encArg(z) -{ 0 }-> g(g(encArg(z - 2))) :|: z - 2 >= 0 encArg(z) -{ 0 }-> g(f(encArg(x_115), encArg(x_24))) :|: z = 1 + (1 + x_115 + x_24), x_115 >= 0, x_24 >= 0 encArg(z) -{ 0 }-> g(1 + encArg(z - 2)) :|: z - 2 >= 0 encArg(z) -{ 0 }-> f(g(encArg(x_11)), g(encArg(x_110))) :|: x_11 >= 0, z = 1 + (1 + x_11) + (1 + x_110), x_110 >= 0 encArg(z) -{ 0 }-> f(g(encArg(x_11)), f(encArg(x_19), encArg(x_22))) :|: x_11 >= 0, z = 1 + (1 + x_11) + (1 + x_19 + x_22), x_22 >= 0, x_19 >= 0 encArg(z) -{ 0 }-> f(g(encArg(x_11)), 0) :|: x_11 >= 0, z = 1 + (1 + x_11) + x_2, x_2 >= 0 encArg(z) -{ 0 }-> f(g(encArg(x_11)), 1 + encArg(x_18)) :|: x_11 >= 0, z = 1 + (1 + x_11) + (1 + x_18), x_18 >= 0 encArg(z) -{ 0 }-> f(f(encArg(x_1''), encArg(x_2')), g(encArg(x_17))) :|: x_1'' >= 0, z = 1 + (1 + x_1'' + x_2') + (1 + x_17), x_2' >= 0, x_17 >= 0 encArg(z) -{ 0 }-> f(f(encArg(x_1''), encArg(x_2')), f(encArg(x_16), encArg(x_21))) :|: x_1'' >= 0, x_16 >= 0, x_2' >= 0, z = 1 + (1 + x_1'' + x_2') + (1 + x_16 + x_21), x_21 >= 0 encArg(z) -{ 0 }-> f(f(encArg(x_1''), encArg(x_2')), 0) :|: x_1'' >= 0, x_2' >= 0, z = 1 + (1 + x_1'' + x_2') + x_2, x_2 >= 0 encArg(z) -{ 0 }-> f(f(encArg(x_1''), encArg(x_2')), 1 + encArg(x_15)) :|: x_15 >= 0, z = 1 + (1 + x_1'' + x_2') + (1 + x_15), x_1'' >= 0, x_2' >= 0 encArg(z) -{ 0 }-> f(0, g(encArg(x_113))) :|: x_1 >= 0, x_113 >= 0, z = 1 + x_1 + (1 + x_113) encArg(z) -{ 0 }-> f(0, f(encArg(x_112), encArg(x_23))) :|: x_1 >= 0, z = 1 + x_1 + (1 + x_112 + x_23), x_23 >= 0, x_112 >= 0 encArg(z) -{ 0 }-> f(0, 1 + encArg(x_111)) :|: x_1 >= 0, z = 1 + x_1 + (1 + x_111), x_111 >= 0 encArg(z) -{ 0 }-> f(1 + encArg(x_1'), g(encArg(x_14))) :|: z = 1 + (1 + x_1') + (1 + x_14), x_14 >= 0, x_1' >= 0 encArg(z) -{ 0 }-> f(1 + encArg(x_1'), f(encArg(x_13), encArg(x_2''))) :|: x_13 >= 0, x_1' >= 0, x_2'' >= 0, z = 1 + (1 + x_1') + (1 + x_13 + x_2'') encArg(z) -{ 0 }-> f(1 + encArg(x_1'), 0) :|: x_1' >= 0, x_2 >= 0, z = 1 + (1 + x_1') + x_2 encArg(z) -{ 0 }-> f(1 + encArg(x_1'), 1 + encArg(x_12)) :|: z = 1 + (1 + x_1') + (1 + x_12), x_1' >= 0, x_12 >= 0 encArg(z) -{ 0 }-> 0 :|: z >= 0 encArg(z) -{ 1 }-> 1 + x :|: z - 1 >= 0, x >= 0, 0 = x encArg(z) -{ 0 }-> 1 + encArg(z - 1) :|: z - 1 >= 0 encode_f(z, z') -{ 2 }-> s'' :|: s'' >= 0, s'' <= 0, z >= 0, z' >= 0 encode_f(z, z') -{ 0 }-> f(g(encArg(z - 1)), g(encArg(z' - 1))) :|: z' - 1 >= 0, z - 1 >= 0 encode_f(z, z') -{ 0 }-> f(g(encArg(z - 1)), f(encArg(x_127), encArg(x_28))) :|: x_127 >= 0, z' = 1 + x_127 + x_28, x_28 >= 0, z - 1 >= 0 encode_f(z, z') -{ 0 }-> f(g(encArg(z - 1)), 0) :|: z' >= 0, z - 1 >= 0 encode_f(z, z') -{ 0 }-> f(g(encArg(z - 1)), 1 + encArg(z' - 1)) :|: z' - 1 >= 0, z - 1 >= 0 encode_f(z, z') -{ 0 }-> f(f(encArg(x_118), encArg(x_25)), g(encArg(z' - 1))) :|: x_25 >= 0, z = 1 + x_118 + x_25, z' - 1 >= 0, x_118 >= 0 encode_f(z, z') -{ 0 }-> f(f(encArg(x_118), encArg(x_25)), f(encArg(x_124), encArg(x_27))) :|: x_124 >= 0, x_25 >= 0, z = 1 + x_118 + x_25, x_27 >= 0, x_118 >= 0, z' = 1 + x_124 + x_27 encode_f(z, z') -{ 0 }-> f(f(encArg(x_118), encArg(x_25)), 0) :|: x_25 >= 0, z = 1 + x_118 + x_25, z' >= 0, x_118 >= 0 encode_f(z, z') -{ 0 }-> f(f(encArg(x_118), encArg(x_25)), 1 + encArg(z' - 1)) :|: z' - 1 >= 0, x_25 >= 0, z = 1 + x_118 + x_25, x_118 >= 0 encode_f(z, z') -{ 0 }-> f(0, g(encArg(z' - 1))) :|: z >= 0, z' - 1 >= 0 encode_f(z, z') -{ 0 }-> f(0, f(encArg(x_130), encArg(x_29))) :|: z >= 0, x_130 >= 0, z' = 1 + x_130 + x_29, x_29 >= 0 encode_f(z, z') -{ 0 }-> f(0, 1 + encArg(z' - 1)) :|: z >= 0, z' - 1 >= 0 encode_f(z, z') -{ 0 }-> f(1 + encArg(z - 1), g(encArg(z' - 1))) :|: z - 1 >= 0, z' - 1 >= 0 encode_f(z, z') -{ 0 }-> f(1 + encArg(z - 1), f(encArg(x_121), encArg(x_26))) :|: z - 1 >= 0, x_26 >= 0, z' = 1 + x_121 + x_26, x_121 >= 0 encode_f(z, z') -{ 0 }-> f(1 + encArg(z - 1), 0) :|: z - 1 >= 0, z' >= 0 encode_f(z, z') -{ 0 }-> f(1 + encArg(z - 1), 1 + encArg(z' - 1)) :|: z' - 1 >= 0, z - 1 >= 0 encode_f(z, z') -{ 0 }-> 0 :|: z >= 0, z' >= 0 encode_g(z) -{ 0 }-> g(g(encArg(z - 1))) :|: z - 1 >= 0 encode_g(z) -{ 0 }-> g(f(encArg(x_133), encArg(x_210))) :|: z = 1 + x_133 + x_210, x_133 >= 0, x_210 >= 0 encode_g(z) -{ 0 }-> g(1 + encArg(z - 1)) :|: z - 1 >= 0 encode_g(z) -{ 0 }-> 0 :|: z >= 0 encode_g(z) -{ 1 }-> 1 + x :|: z >= 0, x >= 0, 0 = x encode_s(z) -{ 0 }-> 0 :|: z >= 0 encode_s(z) -{ 0 }-> 1 + encArg(z) :|: z >= 0 f(z, z') -{ 4 }-> s :|: s >= 0, s <= 0, z' >= 0, z = z' f(z, z') -{ 0 }-> 0 :|: z >= 0, z' >= 0 g(z) -{ 1 }-> 1 + z :|: z >= 0 Function symbols to be analyzed: {encode_f}, {encode_g}, {encode_s} Previous analysis results are: g: runtime: O(1) [1], size: O(n^1) [1 + z] f: runtime: O(1) [2], size: O(1) [0] encArg: runtime: O(n^1) [2 + 13*z], size: O(n^1) [z] ---------------------------------------- (39) ResultPropagationProof (UPPER BOUND(ID)) Applied inner abstraction using the recently inferred runtime/size bounds where possible. ---------------------------------------- (40) Obligation: Complexity RNTS consisting of the following rules: encArg(z) -{ 2 }-> s' :|: s' >= 0, s' <= 0, x_1 >= 0, z = 1 + x_1 + x_2, x_2 >= 0 encArg(z) -{ 7 + 13*x_115 + 13*x_24 }-> s103 :|: s100 >= 0, s100 <= x_115, s101 >= 0, s101 <= x_24, s102 >= 0, s102 <= 0, s103 >= 0, s103 <= s102 + 1, z = 1 + (1 + x_115 + x_24), x_115 >= 0, x_24 >= 0 encArg(z) -{ -22 + 13*z }-> s106 :|: s104 >= 0, s104 <= z - 2, s105 >= 0, s105 <= s104 + 1, s106 >= 0, s106 <= s105 + 1, z - 2 >= 0 encArg(z) -{ 4 + 13*x_1' }-> s11 :|: s10 >= 0, s10 <= x_1', s11 >= 0, s11 <= 0, x_1' >= 0, x_2 >= 0, z = 1 + (1 + x_1') + x_2 encArg(z) -{ 10 + 13*x_1'' + 13*x_15 + 13*x_2' }-> s16 :|: s12 >= 0, s12 <= x_1'', s13 >= 0, s13 <= x_2', s14 >= 0, s14 <= 0, s15 >= 0, s15 <= x_15, s16 >= 0, s16 <= 0, x_15 >= 0, z = 1 + (1 + x_1'' + x_2') + (1 + x_15), x_1'' >= 0, x_2' >= 0 encArg(z) -{ 14 + 13*x_1'' + 13*x_16 + 13*x_2' + 13*x_21 }-> s23 :|: s17 >= 0, s17 <= x_1'', s18 >= 0, s18 <= x_2', s19 >= 0, s19 <= 0, s20 >= 0, s20 <= x_16, s21 >= 0, s21 <= x_21, s22 >= 0, s22 <= 0, s23 >= 0, s23 <= 0, x_1'' >= 0, x_16 >= 0, x_2' >= 0, z = 1 + (1 + x_1'' + x_2') + (1 + x_16 + x_21), x_21 >= 0 encArg(z) -{ 8 + 13*x_1'' + 13*x_2' }-> s27 :|: s24 >= 0, s24 <= x_1'', s25 >= 0, s25 <= x_2', s26 >= 0, s26 <= 0, s27 >= 0, s27 <= 0, x_1'' >= 0, x_2' >= 0, z = 1 + (1 + x_1'' + x_2') + x_2, x_2 >= 0 encArg(z) -{ 4 + 13*x_111 }-> s29 :|: s28 >= 0, s28 <= x_111, s29 >= 0, s29 <= 0, x_1 >= 0, z = 1 + x_1 + (1 + x_111), x_111 >= 0 encArg(z) -{ 8 + 13*x_112 + 13*x_23 }-> s33 :|: s30 >= 0, s30 <= x_112, s31 >= 0, s31 <= x_23, s32 >= 0, s32 <= 0, s33 >= 0, s33 <= 0, x_1 >= 0, z = 1 + x_1 + (1 + x_112 + x_23), x_23 >= 0, x_112 >= 0 encArg(z) -{ 6 + 13*x_1' + 13*x_12 }-> s4 :|: s2 >= 0, s2 <= x_1', s3 >= 0, s3 <= x_12, s4 >= 0, s4 <= 0, z = 1 + (1 + x_1') + (1 + x_12), x_1' >= 0, x_12 >= 0 encArg(z) -{ 7 + 13*x_1' + 13*x_14 }-> s70 :|: s67 >= 0, s67 <= x_1', s68 >= 0, s68 <= x_14, s69 >= 0, s69 <= s68 + 1, s70 >= 0, s70 <= 0, z = 1 + (1 + x_1') + (1 + x_14), x_14 >= 0, x_1' >= 0 encArg(z) -{ 11 + 13*x_1'' + 13*x_17 + 13*x_2' }-> s76 :|: s71 >= 0, s71 <= x_1'', s72 >= 0, s72 <= x_2', s73 >= 0, s73 <= 0, s74 >= 0, s74 <= x_17, s75 >= 0, s75 <= s74 + 1, s76 >= 0, s76 <= 0, x_1'' >= 0, z = 1 + (1 + x_1'' + x_2') + (1 + x_17), x_2' >= 0, x_17 >= 0 encArg(z) -{ 7 + 13*x_11 + 13*x_18 }-> s80 :|: s77 >= 0, s77 <= x_11, s78 >= 0, s78 <= s77 + 1, s79 >= 0, s79 <= x_18, s80 >= 0, s80 <= 0, x_11 >= 0, z = 1 + (1 + x_11) + (1 + x_18), x_18 >= 0 encArg(z) -{ 11 + 13*x_11 + 13*x_19 + 13*x_22 }-> s86 :|: s81 >= 0, s81 <= x_11, s82 >= 0, s82 <= s81 + 1, s83 >= 0, s83 <= x_19, s84 >= 0, s84 <= x_22, s85 >= 0, s85 <= 0, s86 >= 0, s86 <= 0, x_11 >= 0, z = 1 + (1 + x_11) + (1 + x_19 + x_22), x_22 >= 0, x_19 >= 0 encArg(z) -{ 10 + 13*x_1' + 13*x_13 + 13*x_2'' }-> s9 :|: s5 >= 0, s5 <= x_1', s6 >= 0, s6 <= x_13, s7 >= 0, s7 <= x_2'', s8 >= 0, s8 <= 0, s9 >= 0, s9 <= 0, x_13 >= 0, x_1' >= 0, x_2'' >= 0, z = 1 + (1 + x_1') + (1 + x_13 + x_2'') encArg(z) -{ 8 + 13*x_11 + 13*x_110 }-> s91 :|: s87 >= 0, s87 <= x_11, s88 >= 0, s88 <= s87 + 1, s89 >= 0, s89 <= x_110, s90 >= 0, s90 <= s89 + 1, s91 >= 0, s91 <= 0, x_11 >= 0, z = 1 + (1 + x_11) + (1 + x_110), x_110 >= 0 encArg(z) -{ 5 + 13*x_11 }-> s94 :|: s92 >= 0, s92 <= x_11, s93 >= 0, s93 <= s92 + 1, s94 >= 0, s94 <= 0, x_11 >= 0, z = 1 + (1 + x_11) + x_2, x_2 >= 0 encArg(z) -{ 5 + 13*x_113 }-> s97 :|: s95 >= 0, s95 <= x_113, s96 >= 0, s96 <= s95 + 1, s97 >= 0, s97 <= 0, x_1 >= 0, x_113 >= 0, z = 1 + x_1 + (1 + x_113) encArg(z) -{ -23 + 13*z }-> s99 :|: s98 >= 0, s98 <= z - 2, s99 >= 0, s99 <= 1 + s98 + 1, z - 2 >= 0 encArg(z) -{ 0 }-> 0 :|: z >= 0 encArg(z) -{ -11 + 13*z }-> 1 + s1 :|: s1 >= 0, s1 <= z - 1, z - 1 >= 0 encArg(z) -{ 1 }-> 1 + x :|: z - 1 >= 0, x >= 0, 0 = x encode_f(z, z') -{ 2 }-> s'' :|: s'' >= 0, s'' <= 0, z >= 0, z' >= 0 encode_f(z, z') -{ -19 + 13*z + 13*z' }-> s110 :|: s107 >= 0, s107 <= z - 1, s108 >= 0, s108 <= z' - 1, s109 >= 0, s109 <= s108 + 1, s110 >= 0, s110 <= 0, z - 1 >= 0, z' - 1 >= 0 encode_f(z, z') -{ -2 + 13*x_118 + 13*x_25 + 13*z' }-> s116 :|: s111 >= 0, s111 <= x_118, s112 >= 0, s112 <= x_25, s113 >= 0, s113 <= 0, s114 >= 0, s114 <= z' - 1, s115 >= 0, s115 <= s114 + 1, s116 >= 0, s116 <= 0, x_25 >= 0, z = 1 + x_118 + x_25, z' - 1 >= 0, x_118 >= 0 encode_f(z, z') -{ -19 + 13*z + 13*z' }-> s120 :|: s117 >= 0, s117 <= z - 1, s118 >= 0, s118 <= s117 + 1, s119 >= 0, s119 <= z' - 1, s120 >= 0, s120 <= 0, z' - 1 >= 0, z - 1 >= 0 encode_f(z, z') -{ -2 + 13*x_127 + 13*x_28 + 13*z }-> s126 :|: s121 >= 0, s121 <= z - 1, s122 >= 0, s122 <= s121 + 1, s123 >= 0, s123 <= x_127, s124 >= 0, s124 <= x_28, s125 >= 0, s125 <= 0, s126 >= 0, s126 <= 0, x_127 >= 0, z' = 1 + x_127 + x_28, x_28 >= 0, z - 1 >= 0 encode_f(z, z') -{ -18 + 13*z + 13*z' }-> s131 :|: s127 >= 0, s127 <= z - 1, s128 >= 0, s128 <= s127 + 1, s129 >= 0, s129 <= z' - 1, s130 >= 0, s130 <= s129 + 1, s131 >= 0, s131 <= 0, z' - 1 >= 0, z - 1 >= 0 encode_f(z, z') -{ -8 + 13*z }-> s134 :|: s132 >= 0, s132 <= z - 1, s133 >= 0, s133 <= s132 + 1, s134 >= 0, s134 <= 0, z' >= 0, z - 1 >= 0 encode_f(z, z') -{ -8 + 13*z' }-> s137 :|: s135 >= 0, s135 <= z' - 1, s136 >= 0, s136 <= s135 + 1, s137 >= 0, s137 <= 0, z >= 0, z' - 1 >= 0 encode_f(z, z') -{ -20 + 13*z + 13*z' }-> s36 :|: s34 >= 0, s34 <= z - 1, s35 >= 0, s35 <= z' - 1, s36 >= 0, s36 <= 0, z' - 1 >= 0, z - 1 >= 0 encode_f(z, z') -{ -3 + 13*x_121 + 13*x_26 + 13*z }-> s41 :|: s37 >= 0, s37 <= z - 1, s38 >= 0, s38 <= x_121, s39 >= 0, s39 <= x_26, s40 >= 0, s40 <= 0, s41 >= 0, s41 <= 0, z - 1 >= 0, x_26 >= 0, z' = 1 + x_121 + x_26, x_121 >= 0 encode_f(z, z') -{ -9 + 13*z }-> s43 :|: s42 >= 0, s42 <= z - 1, s43 >= 0, s43 <= 0, z - 1 >= 0, z' >= 0 encode_f(z, z') -{ -3 + 13*x_118 + 13*x_25 + 13*z' }-> s48 :|: s44 >= 0, s44 <= x_118, s45 >= 0, s45 <= x_25, s46 >= 0, s46 <= 0, s47 >= 0, s47 <= z' - 1, s48 >= 0, s48 <= 0, z' - 1 >= 0, x_25 >= 0, z = 1 + x_118 + x_25, x_118 >= 0 encode_f(z, z') -{ 14 + 13*x_118 + 13*x_124 + 13*x_25 + 13*x_27 }-> s55 :|: s49 >= 0, s49 <= x_118, s50 >= 0, s50 <= x_25, s51 >= 0, s51 <= 0, s52 >= 0, s52 <= x_124, s53 >= 0, s53 <= x_27, s54 >= 0, s54 <= 0, s55 >= 0, s55 <= 0, x_124 >= 0, x_25 >= 0, z = 1 + x_118 + x_25, x_27 >= 0, x_118 >= 0, z' = 1 + x_124 + x_27 encode_f(z, z') -{ 8 + 13*x_118 + 13*x_25 }-> s59 :|: s56 >= 0, s56 <= x_118, s57 >= 0, s57 <= x_25, s58 >= 0, s58 <= 0, s59 >= 0, s59 <= 0, x_25 >= 0, z = 1 + x_118 + x_25, z' >= 0, x_118 >= 0 encode_f(z, z') -{ -9 + 13*z' }-> s61 :|: s60 >= 0, s60 <= z' - 1, s61 >= 0, s61 <= 0, z >= 0, z' - 1 >= 0 encode_f(z, z') -{ 8 + 13*x_130 + 13*x_29 }-> s65 :|: s62 >= 0, s62 <= x_130, s63 >= 0, s63 <= x_29, s64 >= 0, s64 <= 0, s65 >= 0, s65 <= 0, z >= 0, x_130 >= 0, z' = 1 + x_130 + x_29, x_29 >= 0 encode_f(z, z') -{ 0 }-> 0 :|: z >= 0, z' >= 0 encode_g(z) -{ -10 + 13*z }-> s139 :|: s138 >= 0, s138 <= z - 1, s139 >= 0, s139 <= 1 + s138 + 1, z - 1 >= 0 encode_g(z) -{ 7 + 13*x_133 + 13*x_210 }-> s143 :|: s140 >= 0, s140 <= x_133, s141 >= 0, s141 <= x_210, s142 >= 0, s142 <= 0, s143 >= 0, s143 <= s142 + 1, z = 1 + x_133 + x_210, x_133 >= 0, x_210 >= 0 encode_g(z) -{ -9 + 13*z }-> s146 :|: s144 >= 0, s144 <= z - 1, s145 >= 0, s145 <= s144 + 1, s146 >= 0, s146 <= s145 + 1, z - 1 >= 0 encode_g(z) -{ 0 }-> 0 :|: z >= 0 encode_g(z) -{ 1 }-> 1 + x :|: z >= 0, x >= 0, 0 = x encode_s(z) -{ 0 }-> 0 :|: z >= 0 encode_s(z) -{ 2 + 13*z }-> 1 + s66 :|: s66 >= 0, s66 <= z, z >= 0 f(z, z') -{ 4 }-> s :|: s >= 0, s <= 0, z' >= 0, z = z' f(z, z') -{ 0 }-> 0 :|: z >= 0, z' >= 0 g(z) -{ 1 }-> 1 + z :|: z >= 0 Function symbols to be analyzed: {encode_f}, {encode_g}, {encode_s} Previous analysis results are: g: runtime: O(1) [1], size: O(n^1) [1 + z] f: runtime: O(1) [2], size: O(1) [0] encArg: runtime: O(n^1) [2 + 13*z], size: O(n^1) [z] ---------------------------------------- (41) IntTrsBoundProof (UPPER BOUND(ID)) Computed SIZE bound using CoFloCo for: encode_f after applying outer abstraction to obtain an ITS, resulting in: O(1) with polynomial bound: 0 ---------------------------------------- (42) Obligation: Complexity RNTS consisting of the following rules: encArg(z) -{ 2 }-> s' :|: s' >= 0, s' <= 0, x_1 >= 0, z = 1 + x_1 + x_2, x_2 >= 0 encArg(z) -{ 7 + 13*x_115 + 13*x_24 }-> s103 :|: s100 >= 0, s100 <= x_115, s101 >= 0, s101 <= x_24, s102 >= 0, s102 <= 0, s103 >= 0, s103 <= s102 + 1, z = 1 + (1 + x_115 + x_24), x_115 >= 0, x_24 >= 0 encArg(z) -{ -22 + 13*z }-> s106 :|: s104 >= 0, s104 <= z - 2, s105 >= 0, s105 <= s104 + 1, s106 >= 0, s106 <= s105 + 1, z - 2 >= 0 encArg(z) -{ 4 + 13*x_1' }-> s11 :|: s10 >= 0, s10 <= x_1', s11 >= 0, s11 <= 0, x_1' >= 0, x_2 >= 0, z = 1 + (1 + x_1') + x_2 encArg(z) -{ 10 + 13*x_1'' + 13*x_15 + 13*x_2' }-> s16 :|: s12 >= 0, s12 <= x_1'', s13 >= 0, s13 <= x_2', s14 >= 0, s14 <= 0, s15 >= 0, s15 <= x_15, s16 >= 0, s16 <= 0, x_15 >= 0, z = 1 + (1 + x_1'' + x_2') + (1 + x_15), x_1'' >= 0, x_2' >= 0 encArg(z) -{ 14 + 13*x_1'' + 13*x_16 + 13*x_2' + 13*x_21 }-> s23 :|: s17 >= 0, s17 <= x_1'', s18 >= 0, s18 <= x_2', s19 >= 0, s19 <= 0, s20 >= 0, s20 <= x_16, s21 >= 0, s21 <= x_21, s22 >= 0, s22 <= 0, s23 >= 0, s23 <= 0, x_1'' >= 0, x_16 >= 0, x_2' >= 0, z = 1 + (1 + x_1'' + x_2') + (1 + x_16 + x_21), x_21 >= 0 encArg(z) -{ 8 + 13*x_1'' + 13*x_2' }-> s27 :|: s24 >= 0, s24 <= x_1'', s25 >= 0, s25 <= x_2', s26 >= 0, s26 <= 0, s27 >= 0, s27 <= 0, x_1'' >= 0, x_2' >= 0, z = 1 + (1 + x_1'' + x_2') + x_2, x_2 >= 0 encArg(z) -{ 4 + 13*x_111 }-> s29 :|: s28 >= 0, s28 <= x_111, s29 >= 0, s29 <= 0, x_1 >= 0, z = 1 + x_1 + (1 + x_111), x_111 >= 0 encArg(z) -{ 8 + 13*x_112 + 13*x_23 }-> s33 :|: s30 >= 0, s30 <= x_112, s31 >= 0, s31 <= x_23, s32 >= 0, s32 <= 0, s33 >= 0, s33 <= 0, x_1 >= 0, z = 1 + x_1 + (1 + x_112 + x_23), x_23 >= 0, x_112 >= 0 encArg(z) -{ 6 + 13*x_1' + 13*x_12 }-> s4 :|: s2 >= 0, s2 <= x_1', s3 >= 0, s3 <= x_12, s4 >= 0, s4 <= 0, z = 1 + (1 + x_1') + (1 + x_12), x_1' >= 0, x_12 >= 0 encArg(z) -{ 7 + 13*x_1' + 13*x_14 }-> s70 :|: s67 >= 0, s67 <= x_1', s68 >= 0, s68 <= x_14, s69 >= 0, s69 <= s68 + 1, s70 >= 0, s70 <= 0, z = 1 + (1 + x_1') + (1 + x_14), x_14 >= 0, x_1' >= 0 encArg(z) -{ 11 + 13*x_1'' + 13*x_17 + 13*x_2' }-> s76 :|: s71 >= 0, s71 <= x_1'', s72 >= 0, s72 <= x_2', s73 >= 0, s73 <= 0, s74 >= 0, s74 <= x_17, s75 >= 0, s75 <= s74 + 1, s76 >= 0, s76 <= 0, x_1'' >= 0, z = 1 + (1 + x_1'' + x_2') + (1 + x_17), x_2' >= 0, x_17 >= 0 encArg(z) -{ 7 + 13*x_11 + 13*x_18 }-> s80 :|: s77 >= 0, s77 <= x_11, s78 >= 0, s78 <= s77 + 1, s79 >= 0, s79 <= x_18, s80 >= 0, s80 <= 0, x_11 >= 0, z = 1 + (1 + x_11) + (1 + x_18), x_18 >= 0 encArg(z) -{ 11 + 13*x_11 + 13*x_19 + 13*x_22 }-> s86 :|: s81 >= 0, s81 <= x_11, s82 >= 0, s82 <= s81 + 1, s83 >= 0, s83 <= x_19, s84 >= 0, s84 <= x_22, s85 >= 0, s85 <= 0, s86 >= 0, s86 <= 0, x_11 >= 0, z = 1 + (1 + x_11) + (1 + x_19 + x_22), x_22 >= 0, x_19 >= 0 encArg(z) -{ 10 + 13*x_1' + 13*x_13 + 13*x_2'' }-> s9 :|: s5 >= 0, s5 <= x_1', s6 >= 0, s6 <= x_13, s7 >= 0, s7 <= x_2'', s8 >= 0, s8 <= 0, s9 >= 0, s9 <= 0, x_13 >= 0, x_1' >= 0, x_2'' >= 0, z = 1 + (1 + x_1') + (1 + x_13 + x_2'') encArg(z) -{ 8 + 13*x_11 + 13*x_110 }-> s91 :|: s87 >= 0, s87 <= x_11, s88 >= 0, s88 <= s87 + 1, s89 >= 0, s89 <= x_110, s90 >= 0, s90 <= s89 + 1, s91 >= 0, s91 <= 0, x_11 >= 0, z = 1 + (1 + x_11) + (1 + x_110), x_110 >= 0 encArg(z) -{ 5 + 13*x_11 }-> s94 :|: s92 >= 0, s92 <= x_11, s93 >= 0, s93 <= s92 + 1, s94 >= 0, s94 <= 0, x_11 >= 0, z = 1 + (1 + x_11) + x_2, x_2 >= 0 encArg(z) -{ 5 + 13*x_113 }-> s97 :|: s95 >= 0, s95 <= x_113, s96 >= 0, s96 <= s95 + 1, s97 >= 0, s97 <= 0, x_1 >= 0, x_113 >= 0, z = 1 + x_1 + (1 + x_113) encArg(z) -{ -23 + 13*z }-> s99 :|: s98 >= 0, s98 <= z - 2, s99 >= 0, s99 <= 1 + s98 + 1, z - 2 >= 0 encArg(z) -{ 0 }-> 0 :|: z >= 0 encArg(z) -{ -11 + 13*z }-> 1 + s1 :|: s1 >= 0, s1 <= z - 1, z - 1 >= 0 encArg(z) -{ 1 }-> 1 + x :|: z - 1 >= 0, x >= 0, 0 = x encode_f(z, z') -{ 2 }-> s'' :|: s'' >= 0, s'' <= 0, z >= 0, z' >= 0 encode_f(z, z') -{ -19 + 13*z + 13*z' }-> s110 :|: s107 >= 0, s107 <= z - 1, s108 >= 0, s108 <= z' - 1, s109 >= 0, s109 <= s108 + 1, s110 >= 0, s110 <= 0, z - 1 >= 0, z' - 1 >= 0 encode_f(z, z') -{ -2 + 13*x_118 + 13*x_25 + 13*z' }-> s116 :|: s111 >= 0, s111 <= x_118, s112 >= 0, s112 <= x_25, s113 >= 0, s113 <= 0, s114 >= 0, s114 <= z' - 1, s115 >= 0, s115 <= s114 + 1, s116 >= 0, s116 <= 0, x_25 >= 0, z = 1 + x_118 + x_25, z' - 1 >= 0, x_118 >= 0 encode_f(z, z') -{ -19 + 13*z + 13*z' }-> s120 :|: s117 >= 0, s117 <= z - 1, s118 >= 0, s118 <= s117 + 1, s119 >= 0, s119 <= z' - 1, s120 >= 0, s120 <= 0, z' - 1 >= 0, z - 1 >= 0 encode_f(z, z') -{ -2 + 13*x_127 + 13*x_28 + 13*z }-> s126 :|: s121 >= 0, s121 <= z - 1, s122 >= 0, s122 <= s121 + 1, s123 >= 0, s123 <= x_127, s124 >= 0, s124 <= x_28, s125 >= 0, s125 <= 0, s126 >= 0, s126 <= 0, x_127 >= 0, z' = 1 + x_127 + x_28, x_28 >= 0, z - 1 >= 0 encode_f(z, z') -{ -18 + 13*z + 13*z' }-> s131 :|: s127 >= 0, s127 <= z - 1, s128 >= 0, s128 <= s127 + 1, s129 >= 0, s129 <= z' - 1, s130 >= 0, s130 <= s129 + 1, s131 >= 0, s131 <= 0, z' - 1 >= 0, z - 1 >= 0 encode_f(z, z') -{ -8 + 13*z }-> s134 :|: s132 >= 0, s132 <= z - 1, s133 >= 0, s133 <= s132 + 1, s134 >= 0, s134 <= 0, z' >= 0, z - 1 >= 0 encode_f(z, z') -{ -8 + 13*z' }-> s137 :|: s135 >= 0, s135 <= z' - 1, s136 >= 0, s136 <= s135 + 1, s137 >= 0, s137 <= 0, z >= 0, z' - 1 >= 0 encode_f(z, z') -{ -20 + 13*z + 13*z' }-> s36 :|: s34 >= 0, s34 <= z - 1, s35 >= 0, s35 <= z' - 1, s36 >= 0, s36 <= 0, z' - 1 >= 0, z - 1 >= 0 encode_f(z, z') -{ -3 + 13*x_121 + 13*x_26 + 13*z }-> s41 :|: s37 >= 0, s37 <= z - 1, s38 >= 0, s38 <= x_121, s39 >= 0, s39 <= x_26, s40 >= 0, s40 <= 0, s41 >= 0, s41 <= 0, z - 1 >= 0, x_26 >= 0, z' = 1 + x_121 + x_26, x_121 >= 0 encode_f(z, z') -{ -9 + 13*z }-> s43 :|: s42 >= 0, s42 <= z - 1, s43 >= 0, s43 <= 0, z - 1 >= 0, z' >= 0 encode_f(z, z') -{ -3 + 13*x_118 + 13*x_25 + 13*z' }-> s48 :|: s44 >= 0, s44 <= x_118, s45 >= 0, s45 <= x_25, s46 >= 0, s46 <= 0, s47 >= 0, s47 <= z' - 1, s48 >= 0, s48 <= 0, z' - 1 >= 0, x_25 >= 0, z = 1 + x_118 + x_25, x_118 >= 0 encode_f(z, z') -{ 14 + 13*x_118 + 13*x_124 + 13*x_25 + 13*x_27 }-> s55 :|: s49 >= 0, s49 <= x_118, s50 >= 0, s50 <= x_25, s51 >= 0, s51 <= 0, s52 >= 0, s52 <= x_124, s53 >= 0, s53 <= x_27, s54 >= 0, s54 <= 0, s55 >= 0, s55 <= 0, x_124 >= 0, x_25 >= 0, z = 1 + x_118 + x_25, x_27 >= 0, x_118 >= 0, z' = 1 + x_124 + x_27 encode_f(z, z') -{ 8 + 13*x_118 + 13*x_25 }-> s59 :|: s56 >= 0, s56 <= x_118, s57 >= 0, s57 <= x_25, s58 >= 0, s58 <= 0, s59 >= 0, s59 <= 0, x_25 >= 0, z = 1 + x_118 + x_25, z' >= 0, x_118 >= 0 encode_f(z, z') -{ -9 + 13*z' }-> s61 :|: s60 >= 0, s60 <= z' - 1, s61 >= 0, s61 <= 0, z >= 0, z' - 1 >= 0 encode_f(z, z') -{ 8 + 13*x_130 + 13*x_29 }-> s65 :|: s62 >= 0, s62 <= x_130, s63 >= 0, s63 <= x_29, s64 >= 0, s64 <= 0, s65 >= 0, s65 <= 0, z >= 0, x_130 >= 0, z' = 1 + x_130 + x_29, x_29 >= 0 encode_f(z, z') -{ 0 }-> 0 :|: z >= 0, z' >= 0 encode_g(z) -{ -10 + 13*z }-> s139 :|: s138 >= 0, s138 <= z - 1, s139 >= 0, s139 <= 1 + s138 + 1, z - 1 >= 0 encode_g(z) -{ 7 + 13*x_133 + 13*x_210 }-> s143 :|: s140 >= 0, s140 <= x_133, s141 >= 0, s141 <= x_210, s142 >= 0, s142 <= 0, s143 >= 0, s143 <= s142 + 1, z = 1 + x_133 + x_210, x_133 >= 0, x_210 >= 0 encode_g(z) -{ -9 + 13*z }-> s146 :|: s144 >= 0, s144 <= z - 1, s145 >= 0, s145 <= s144 + 1, s146 >= 0, s146 <= s145 + 1, z - 1 >= 0 encode_g(z) -{ 0 }-> 0 :|: z >= 0 encode_g(z) -{ 1 }-> 1 + x :|: z >= 0, x >= 0, 0 = x encode_s(z) -{ 0 }-> 0 :|: z >= 0 encode_s(z) -{ 2 + 13*z }-> 1 + s66 :|: s66 >= 0, s66 <= z, z >= 0 f(z, z') -{ 4 }-> s :|: s >= 0, s <= 0, z' >= 0, z = z' f(z, z') -{ 0 }-> 0 :|: z >= 0, z' >= 0 g(z) -{ 1 }-> 1 + z :|: z >= 0 Function symbols to be analyzed: {encode_f}, {encode_g}, {encode_s} Previous analysis results are: g: runtime: O(1) [1], size: O(n^1) [1 + z] f: runtime: O(1) [2], size: O(1) [0] encArg: runtime: O(n^1) [2 + 13*z], size: O(n^1) [z] encode_f: runtime: ?, size: O(1) [0] ---------------------------------------- (43) IntTrsBoundProof (UPPER BOUND(ID)) Computed RUNTIME bound using CoFloCo for: encode_f after applying outer abstraction to obtain an ITS, resulting in: O(n^1) with polynomial bound: 20 + 13*z + 13*z' ---------------------------------------- (44) Obligation: Complexity RNTS consisting of the following rules: encArg(z) -{ 2 }-> s' :|: s' >= 0, s' <= 0, x_1 >= 0, z = 1 + x_1 + x_2, x_2 >= 0 encArg(z) -{ 7 + 13*x_115 + 13*x_24 }-> s103 :|: s100 >= 0, s100 <= x_115, s101 >= 0, s101 <= x_24, s102 >= 0, s102 <= 0, s103 >= 0, s103 <= s102 + 1, z = 1 + (1 + x_115 + x_24), x_115 >= 0, x_24 >= 0 encArg(z) -{ -22 + 13*z }-> s106 :|: s104 >= 0, s104 <= z - 2, s105 >= 0, s105 <= s104 + 1, s106 >= 0, s106 <= s105 + 1, z - 2 >= 0 encArg(z) -{ 4 + 13*x_1' }-> s11 :|: s10 >= 0, s10 <= x_1', s11 >= 0, s11 <= 0, x_1' >= 0, x_2 >= 0, z = 1 + (1 + x_1') + x_2 encArg(z) -{ 10 + 13*x_1'' + 13*x_15 + 13*x_2' }-> s16 :|: s12 >= 0, s12 <= x_1'', s13 >= 0, s13 <= x_2', s14 >= 0, s14 <= 0, s15 >= 0, s15 <= x_15, s16 >= 0, s16 <= 0, x_15 >= 0, z = 1 + (1 + x_1'' + x_2') + (1 + x_15), x_1'' >= 0, x_2' >= 0 encArg(z) -{ 14 + 13*x_1'' + 13*x_16 + 13*x_2' + 13*x_21 }-> s23 :|: s17 >= 0, s17 <= x_1'', s18 >= 0, s18 <= x_2', s19 >= 0, s19 <= 0, s20 >= 0, s20 <= x_16, s21 >= 0, s21 <= x_21, s22 >= 0, s22 <= 0, s23 >= 0, s23 <= 0, x_1'' >= 0, x_16 >= 0, x_2' >= 0, z = 1 + (1 + x_1'' + x_2') + (1 + x_16 + x_21), x_21 >= 0 encArg(z) -{ 8 + 13*x_1'' + 13*x_2' }-> s27 :|: s24 >= 0, s24 <= x_1'', s25 >= 0, s25 <= x_2', s26 >= 0, s26 <= 0, s27 >= 0, s27 <= 0, x_1'' >= 0, x_2' >= 0, z = 1 + (1 + x_1'' + x_2') + x_2, x_2 >= 0 encArg(z) -{ 4 + 13*x_111 }-> s29 :|: s28 >= 0, s28 <= x_111, s29 >= 0, s29 <= 0, x_1 >= 0, z = 1 + x_1 + (1 + x_111), x_111 >= 0 encArg(z) -{ 8 + 13*x_112 + 13*x_23 }-> s33 :|: s30 >= 0, s30 <= x_112, s31 >= 0, s31 <= x_23, s32 >= 0, s32 <= 0, s33 >= 0, s33 <= 0, x_1 >= 0, z = 1 + x_1 + (1 + x_112 + x_23), x_23 >= 0, x_112 >= 0 encArg(z) -{ 6 + 13*x_1' + 13*x_12 }-> s4 :|: s2 >= 0, s2 <= x_1', s3 >= 0, s3 <= x_12, s4 >= 0, s4 <= 0, z = 1 + (1 + x_1') + (1 + x_12), x_1' >= 0, x_12 >= 0 encArg(z) -{ 7 + 13*x_1' + 13*x_14 }-> s70 :|: s67 >= 0, s67 <= x_1', s68 >= 0, s68 <= x_14, s69 >= 0, s69 <= s68 + 1, s70 >= 0, s70 <= 0, z = 1 + (1 + x_1') + (1 + x_14), x_14 >= 0, x_1' >= 0 encArg(z) -{ 11 + 13*x_1'' + 13*x_17 + 13*x_2' }-> s76 :|: s71 >= 0, s71 <= x_1'', s72 >= 0, s72 <= x_2', s73 >= 0, s73 <= 0, s74 >= 0, s74 <= x_17, s75 >= 0, s75 <= s74 + 1, s76 >= 0, s76 <= 0, x_1'' >= 0, z = 1 + (1 + x_1'' + x_2') + (1 + x_17), x_2' >= 0, x_17 >= 0 encArg(z) -{ 7 + 13*x_11 + 13*x_18 }-> s80 :|: s77 >= 0, s77 <= x_11, s78 >= 0, s78 <= s77 + 1, s79 >= 0, s79 <= x_18, s80 >= 0, s80 <= 0, x_11 >= 0, z = 1 + (1 + x_11) + (1 + x_18), x_18 >= 0 encArg(z) -{ 11 + 13*x_11 + 13*x_19 + 13*x_22 }-> s86 :|: s81 >= 0, s81 <= x_11, s82 >= 0, s82 <= s81 + 1, s83 >= 0, s83 <= x_19, s84 >= 0, s84 <= x_22, s85 >= 0, s85 <= 0, s86 >= 0, s86 <= 0, x_11 >= 0, z = 1 + (1 + x_11) + (1 + x_19 + x_22), x_22 >= 0, x_19 >= 0 encArg(z) -{ 10 + 13*x_1' + 13*x_13 + 13*x_2'' }-> s9 :|: s5 >= 0, s5 <= x_1', s6 >= 0, s6 <= x_13, s7 >= 0, s7 <= x_2'', s8 >= 0, s8 <= 0, s9 >= 0, s9 <= 0, x_13 >= 0, x_1' >= 0, x_2'' >= 0, z = 1 + (1 + x_1') + (1 + x_13 + x_2'') encArg(z) -{ 8 + 13*x_11 + 13*x_110 }-> s91 :|: s87 >= 0, s87 <= x_11, s88 >= 0, s88 <= s87 + 1, s89 >= 0, s89 <= x_110, s90 >= 0, s90 <= s89 + 1, s91 >= 0, s91 <= 0, x_11 >= 0, z = 1 + (1 + x_11) + (1 + x_110), x_110 >= 0 encArg(z) -{ 5 + 13*x_11 }-> s94 :|: s92 >= 0, s92 <= x_11, s93 >= 0, s93 <= s92 + 1, s94 >= 0, s94 <= 0, x_11 >= 0, z = 1 + (1 + x_11) + x_2, x_2 >= 0 encArg(z) -{ 5 + 13*x_113 }-> s97 :|: s95 >= 0, s95 <= x_113, s96 >= 0, s96 <= s95 + 1, s97 >= 0, s97 <= 0, x_1 >= 0, x_113 >= 0, z = 1 + x_1 + (1 + x_113) encArg(z) -{ -23 + 13*z }-> s99 :|: s98 >= 0, s98 <= z - 2, s99 >= 0, s99 <= 1 + s98 + 1, z - 2 >= 0 encArg(z) -{ 0 }-> 0 :|: z >= 0 encArg(z) -{ -11 + 13*z }-> 1 + s1 :|: s1 >= 0, s1 <= z - 1, z - 1 >= 0 encArg(z) -{ 1 }-> 1 + x :|: z - 1 >= 0, x >= 0, 0 = x encode_f(z, z') -{ 2 }-> s'' :|: s'' >= 0, s'' <= 0, z >= 0, z' >= 0 encode_f(z, z') -{ -19 + 13*z + 13*z' }-> s110 :|: s107 >= 0, s107 <= z - 1, s108 >= 0, s108 <= z' - 1, s109 >= 0, s109 <= s108 + 1, s110 >= 0, s110 <= 0, z - 1 >= 0, z' - 1 >= 0 encode_f(z, z') -{ -2 + 13*x_118 + 13*x_25 + 13*z' }-> s116 :|: s111 >= 0, s111 <= x_118, s112 >= 0, s112 <= x_25, s113 >= 0, s113 <= 0, s114 >= 0, s114 <= z' - 1, s115 >= 0, s115 <= s114 + 1, s116 >= 0, s116 <= 0, x_25 >= 0, z = 1 + x_118 + x_25, z' - 1 >= 0, x_118 >= 0 encode_f(z, z') -{ -19 + 13*z + 13*z' }-> s120 :|: s117 >= 0, s117 <= z - 1, s118 >= 0, s118 <= s117 + 1, s119 >= 0, s119 <= z' - 1, s120 >= 0, s120 <= 0, z' - 1 >= 0, z - 1 >= 0 encode_f(z, z') -{ -2 + 13*x_127 + 13*x_28 + 13*z }-> s126 :|: s121 >= 0, s121 <= z - 1, s122 >= 0, s122 <= s121 + 1, s123 >= 0, s123 <= x_127, s124 >= 0, s124 <= x_28, s125 >= 0, s125 <= 0, s126 >= 0, s126 <= 0, x_127 >= 0, z' = 1 + x_127 + x_28, x_28 >= 0, z - 1 >= 0 encode_f(z, z') -{ -18 + 13*z + 13*z' }-> s131 :|: s127 >= 0, s127 <= z - 1, s128 >= 0, s128 <= s127 + 1, s129 >= 0, s129 <= z' - 1, s130 >= 0, s130 <= s129 + 1, s131 >= 0, s131 <= 0, z' - 1 >= 0, z - 1 >= 0 encode_f(z, z') -{ -8 + 13*z }-> s134 :|: s132 >= 0, s132 <= z - 1, s133 >= 0, s133 <= s132 + 1, s134 >= 0, s134 <= 0, z' >= 0, z - 1 >= 0 encode_f(z, z') -{ -8 + 13*z' }-> s137 :|: s135 >= 0, s135 <= z' - 1, s136 >= 0, s136 <= s135 + 1, s137 >= 0, s137 <= 0, z >= 0, z' - 1 >= 0 encode_f(z, z') -{ -20 + 13*z + 13*z' }-> s36 :|: s34 >= 0, s34 <= z - 1, s35 >= 0, s35 <= z' - 1, s36 >= 0, s36 <= 0, z' - 1 >= 0, z - 1 >= 0 encode_f(z, z') -{ -3 + 13*x_121 + 13*x_26 + 13*z }-> s41 :|: s37 >= 0, s37 <= z - 1, s38 >= 0, s38 <= x_121, s39 >= 0, s39 <= x_26, s40 >= 0, s40 <= 0, s41 >= 0, s41 <= 0, z - 1 >= 0, x_26 >= 0, z' = 1 + x_121 + x_26, x_121 >= 0 encode_f(z, z') -{ -9 + 13*z }-> s43 :|: s42 >= 0, s42 <= z - 1, s43 >= 0, s43 <= 0, z - 1 >= 0, z' >= 0 encode_f(z, z') -{ -3 + 13*x_118 + 13*x_25 + 13*z' }-> s48 :|: s44 >= 0, s44 <= x_118, s45 >= 0, s45 <= x_25, s46 >= 0, s46 <= 0, s47 >= 0, s47 <= z' - 1, s48 >= 0, s48 <= 0, z' - 1 >= 0, x_25 >= 0, z = 1 + x_118 + x_25, x_118 >= 0 encode_f(z, z') -{ 14 + 13*x_118 + 13*x_124 + 13*x_25 + 13*x_27 }-> s55 :|: s49 >= 0, s49 <= x_118, s50 >= 0, s50 <= x_25, s51 >= 0, s51 <= 0, s52 >= 0, s52 <= x_124, s53 >= 0, s53 <= x_27, s54 >= 0, s54 <= 0, s55 >= 0, s55 <= 0, x_124 >= 0, x_25 >= 0, z = 1 + x_118 + x_25, x_27 >= 0, x_118 >= 0, z' = 1 + x_124 + x_27 encode_f(z, z') -{ 8 + 13*x_118 + 13*x_25 }-> s59 :|: s56 >= 0, s56 <= x_118, s57 >= 0, s57 <= x_25, s58 >= 0, s58 <= 0, s59 >= 0, s59 <= 0, x_25 >= 0, z = 1 + x_118 + x_25, z' >= 0, x_118 >= 0 encode_f(z, z') -{ -9 + 13*z' }-> s61 :|: s60 >= 0, s60 <= z' - 1, s61 >= 0, s61 <= 0, z >= 0, z' - 1 >= 0 encode_f(z, z') -{ 8 + 13*x_130 + 13*x_29 }-> s65 :|: s62 >= 0, s62 <= x_130, s63 >= 0, s63 <= x_29, s64 >= 0, s64 <= 0, s65 >= 0, s65 <= 0, z >= 0, x_130 >= 0, z' = 1 + x_130 + x_29, x_29 >= 0 encode_f(z, z') -{ 0 }-> 0 :|: z >= 0, z' >= 0 encode_g(z) -{ -10 + 13*z }-> s139 :|: s138 >= 0, s138 <= z - 1, s139 >= 0, s139 <= 1 + s138 + 1, z - 1 >= 0 encode_g(z) -{ 7 + 13*x_133 + 13*x_210 }-> s143 :|: s140 >= 0, s140 <= x_133, s141 >= 0, s141 <= x_210, s142 >= 0, s142 <= 0, s143 >= 0, s143 <= s142 + 1, z = 1 + x_133 + x_210, x_133 >= 0, x_210 >= 0 encode_g(z) -{ -9 + 13*z }-> s146 :|: s144 >= 0, s144 <= z - 1, s145 >= 0, s145 <= s144 + 1, s146 >= 0, s146 <= s145 + 1, z - 1 >= 0 encode_g(z) -{ 0 }-> 0 :|: z >= 0 encode_g(z) -{ 1 }-> 1 + x :|: z >= 0, x >= 0, 0 = x encode_s(z) -{ 0 }-> 0 :|: z >= 0 encode_s(z) -{ 2 + 13*z }-> 1 + s66 :|: s66 >= 0, s66 <= z, z >= 0 f(z, z') -{ 4 }-> s :|: s >= 0, s <= 0, z' >= 0, z = z' f(z, z') -{ 0 }-> 0 :|: z >= 0, z' >= 0 g(z) -{ 1 }-> 1 + z :|: z >= 0 Function symbols to be analyzed: {encode_g}, {encode_s} Previous analysis results are: g: runtime: O(1) [1], size: O(n^1) [1 + z] f: runtime: O(1) [2], size: O(1) [0] encArg: runtime: O(n^1) [2 + 13*z], size: O(n^1) [z] encode_f: runtime: O(n^1) [20 + 13*z + 13*z'], size: O(1) [0] ---------------------------------------- (45) ResultPropagationProof (UPPER BOUND(ID)) Applied inner abstraction using the recently inferred runtime/size bounds where possible. ---------------------------------------- (46) Obligation: Complexity RNTS consisting of the following rules: encArg(z) -{ 2 }-> s' :|: s' >= 0, s' <= 0, x_1 >= 0, z = 1 + x_1 + x_2, x_2 >= 0 encArg(z) -{ 7 + 13*x_115 + 13*x_24 }-> s103 :|: s100 >= 0, s100 <= x_115, s101 >= 0, s101 <= x_24, s102 >= 0, s102 <= 0, s103 >= 0, s103 <= s102 + 1, z = 1 + (1 + x_115 + x_24), x_115 >= 0, x_24 >= 0 encArg(z) -{ -22 + 13*z }-> s106 :|: s104 >= 0, s104 <= z - 2, s105 >= 0, s105 <= s104 + 1, s106 >= 0, s106 <= s105 + 1, z - 2 >= 0 encArg(z) -{ 4 + 13*x_1' }-> s11 :|: s10 >= 0, s10 <= x_1', s11 >= 0, s11 <= 0, x_1' >= 0, x_2 >= 0, z = 1 + (1 + x_1') + x_2 encArg(z) -{ 10 + 13*x_1'' + 13*x_15 + 13*x_2' }-> s16 :|: s12 >= 0, s12 <= x_1'', s13 >= 0, s13 <= x_2', s14 >= 0, s14 <= 0, s15 >= 0, s15 <= x_15, s16 >= 0, s16 <= 0, x_15 >= 0, z = 1 + (1 + x_1'' + x_2') + (1 + x_15), x_1'' >= 0, x_2' >= 0 encArg(z) -{ 14 + 13*x_1'' + 13*x_16 + 13*x_2' + 13*x_21 }-> s23 :|: s17 >= 0, s17 <= x_1'', s18 >= 0, s18 <= x_2', s19 >= 0, s19 <= 0, s20 >= 0, s20 <= x_16, s21 >= 0, s21 <= x_21, s22 >= 0, s22 <= 0, s23 >= 0, s23 <= 0, x_1'' >= 0, x_16 >= 0, x_2' >= 0, z = 1 + (1 + x_1'' + x_2') + (1 + x_16 + x_21), x_21 >= 0 encArg(z) -{ 8 + 13*x_1'' + 13*x_2' }-> s27 :|: s24 >= 0, s24 <= x_1'', s25 >= 0, s25 <= x_2', s26 >= 0, s26 <= 0, s27 >= 0, s27 <= 0, x_1'' >= 0, x_2' >= 0, z = 1 + (1 + x_1'' + x_2') + x_2, x_2 >= 0 encArg(z) -{ 4 + 13*x_111 }-> s29 :|: s28 >= 0, s28 <= x_111, s29 >= 0, s29 <= 0, x_1 >= 0, z = 1 + x_1 + (1 + x_111), x_111 >= 0 encArg(z) -{ 8 + 13*x_112 + 13*x_23 }-> s33 :|: s30 >= 0, s30 <= x_112, s31 >= 0, s31 <= x_23, s32 >= 0, s32 <= 0, s33 >= 0, s33 <= 0, x_1 >= 0, z = 1 + x_1 + (1 + x_112 + x_23), x_23 >= 0, x_112 >= 0 encArg(z) -{ 6 + 13*x_1' + 13*x_12 }-> s4 :|: s2 >= 0, s2 <= x_1', s3 >= 0, s3 <= x_12, s4 >= 0, s4 <= 0, z = 1 + (1 + x_1') + (1 + x_12), x_1' >= 0, x_12 >= 0 encArg(z) -{ 7 + 13*x_1' + 13*x_14 }-> s70 :|: s67 >= 0, s67 <= x_1', s68 >= 0, s68 <= x_14, s69 >= 0, s69 <= s68 + 1, s70 >= 0, s70 <= 0, z = 1 + (1 + x_1') + (1 + x_14), x_14 >= 0, x_1' >= 0 encArg(z) -{ 11 + 13*x_1'' + 13*x_17 + 13*x_2' }-> s76 :|: s71 >= 0, s71 <= x_1'', s72 >= 0, s72 <= x_2', s73 >= 0, s73 <= 0, s74 >= 0, s74 <= x_17, s75 >= 0, s75 <= s74 + 1, s76 >= 0, s76 <= 0, x_1'' >= 0, z = 1 + (1 + x_1'' + x_2') + (1 + x_17), x_2' >= 0, x_17 >= 0 encArg(z) -{ 7 + 13*x_11 + 13*x_18 }-> s80 :|: s77 >= 0, s77 <= x_11, s78 >= 0, s78 <= s77 + 1, s79 >= 0, s79 <= x_18, s80 >= 0, s80 <= 0, x_11 >= 0, z = 1 + (1 + x_11) + (1 + x_18), x_18 >= 0 encArg(z) -{ 11 + 13*x_11 + 13*x_19 + 13*x_22 }-> s86 :|: s81 >= 0, s81 <= x_11, s82 >= 0, s82 <= s81 + 1, s83 >= 0, s83 <= x_19, s84 >= 0, s84 <= x_22, s85 >= 0, s85 <= 0, s86 >= 0, s86 <= 0, x_11 >= 0, z = 1 + (1 + x_11) + (1 + x_19 + x_22), x_22 >= 0, x_19 >= 0 encArg(z) -{ 10 + 13*x_1' + 13*x_13 + 13*x_2'' }-> s9 :|: s5 >= 0, s5 <= x_1', s6 >= 0, s6 <= x_13, s7 >= 0, s7 <= x_2'', s8 >= 0, s8 <= 0, s9 >= 0, s9 <= 0, x_13 >= 0, x_1' >= 0, x_2'' >= 0, z = 1 + (1 + x_1') + (1 + x_13 + x_2'') encArg(z) -{ 8 + 13*x_11 + 13*x_110 }-> s91 :|: s87 >= 0, s87 <= x_11, s88 >= 0, s88 <= s87 + 1, s89 >= 0, s89 <= x_110, s90 >= 0, s90 <= s89 + 1, s91 >= 0, s91 <= 0, x_11 >= 0, z = 1 + (1 + x_11) + (1 + x_110), x_110 >= 0 encArg(z) -{ 5 + 13*x_11 }-> s94 :|: s92 >= 0, s92 <= x_11, s93 >= 0, s93 <= s92 + 1, s94 >= 0, s94 <= 0, x_11 >= 0, z = 1 + (1 + x_11) + x_2, x_2 >= 0 encArg(z) -{ 5 + 13*x_113 }-> s97 :|: s95 >= 0, s95 <= x_113, s96 >= 0, s96 <= s95 + 1, s97 >= 0, s97 <= 0, x_1 >= 0, x_113 >= 0, z = 1 + x_1 + (1 + x_113) encArg(z) -{ -23 + 13*z }-> s99 :|: s98 >= 0, s98 <= z - 2, s99 >= 0, s99 <= 1 + s98 + 1, z - 2 >= 0 encArg(z) -{ 0 }-> 0 :|: z >= 0 encArg(z) -{ -11 + 13*z }-> 1 + s1 :|: s1 >= 0, s1 <= z - 1, z - 1 >= 0 encArg(z) -{ 1 }-> 1 + x :|: z - 1 >= 0, x >= 0, 0 = x encode_f(z, z') -{ 2 }-> s'' :|: s'' >= 0, s'' <= 0, z >= 0, z' >= 0 encode_f(z, z') -{ -19 + 13*z + 13*z' }-> s110 :|: s107 >= 0, s107 <= z - 1, s108 >= 0, s108 <= z' - 1, s109 >= 0, s109 <= s108 + 1, s110 >= 0, s110 <= 0, z - 1 >= 0, z' - 1 >= 0 encode_f(z, z') -{ -2 + 13*x_118 + 13*x_25 + 13*z' }-> s116 :|: s111 >= 0, s111 <= x_118, s112 >= 0, s112 <= x_25, s113 >= 0, s113 <= 0, s114 >= 0, s114 <= z' - 1, s115 >= 0, s115 <= s114 + 1, s116 >= 0, s116 <= 0, x_25 >= 0, z = 1 + x_118 + x_25, z' - 1 >= 0, x_118 >= 0 encode_f(z, z') -{ -19 + 13*z + 13*z' }-> s120 :|: s117 >= 0, s117 <= z - 1, s118 >= 0, s118 <= s117 + 1, s119 >= 0, s119 <= z' - 1, s120 >= 0, s120 <= 0, z' - 1 >= 0, z - 1 >= 0 encode_f(z, z') -{ -2 + 13*x_127 + 13*x_28 + 13*z }-> s126 :|: s121 >= 0, s121 <= z - 1, s122 >= 0, s122 <= s121 + 1, s123 >= 0, s123 <= x_127, s124 >= 0, s124 <= x_28, s125 >= 0, s125 <= 0, s126 >= 0, s126 <= 0, x_127 >= 0, z' = 1 + x_127 + x_28, x_28 >= 0, z - 1 >= 0 encode_f(z, z') -{ -18 + 13*z + 13*z' }-> s131 :|: s127 >= 0, s127 <= z - 1, s128 >= 0, s128 <= s127 + 1, s129 >= 0, s129 <= z' - 1, s130 >= 0, s130 <= s129 + 1, s131 >= 0, s131 <= 0, z' - 1 >= 0, z - 1 >= 0 encode_f(z, z') -{ -8 + 13*z }-> s134 :|: s132 >= 0, s132 <= z - 1, s133 >= 0, s133 <= s132 + 1, s134 >= 0, s134 <= 0, z' >= 0, z - 1 >= 0 encode_f(z, z') -{ -8 + 13*z' }-> s137 :|: s135 >= 0, s135 <= z' - 1, s136 >= 0, s136 <= s135 + 1, s137 >= 0, s137 <= 0, z >= 0, z' - 1 >= 0 encode_f(z, z') -{ -20 + 13*z + 13*z' }-> s36 :|: s34 >= 0, s34 <= z - 1, s35 >= 0, s35 <= z' - 1, s36 >= 0, s36 <= 0, z' - 1 >= 0, z - 1 >= 0 encode_f(z, z') -{ -3 + 13*x_121 + 13*x_26 + 13*z }-> s41 :|: s37 >= 0, s37 <= z - 1, s38 >= 0, s38 <= x_121, s39 >= 0, s39 <= x_26, s40 >= 0, s40 <= 0, s41 >= 0, s41 <= 0, z - 1 >= 0, x_26 >= 0, z' = 1 + x_121 + x_26, x_121 >= 0 encode_f(z, z') -{ -9 + 13*z }-> s43 :|: s42 >= 0, s42 <= z - 1, s43 >= 0, s43 <= 0, z - 1 >= 0, z' >= 0 encode_f(z, z') -{ -3 + 13*x_118 + 13*x_25 + 13*z' }-> s48 :|: s44 >= 0, s44 <= x_118, s45 >= 0, s45 <= x_25, s46 >= 0, s46 <= 0, s47 >= 0, s47 <= z' - 1, s48 >= 0, s48 <= 0, z' - 1 >= 0, x_25 >= 0, z = 1 + x_118 + x_25, x_118 >= 0 encode_f(z, z') -{ 14 + 13*x_118 + 13*x_124 + 13*x_25 + 13*x_27 }-> s55 :|: s49 >= 0, s49 <= x_118, s50 >= 0, s50 <= x_25, s51 >= 0, s51 <= 0, s52 >= 0, s52 <= x_124, s53 >= 0, s53 <= x_27, s54 >= 0, s54 <= 0, s55 >= 0, s55 <= 0, x_124 >= 0, x_25 >= 0, z = 1 + x_118 + x_25, x_27 >= 0, x_118 >= 0, z' = 1 + x_124 + x_27 encode_f(z, z') -{ 8 + 13*x_118 + 13*x_25 }-> s59 :|: s56 >= 0, s56 <= x_118, s57 >= 0, s57 <= x_25, s58 >= 0, s58 <= 0, s59 >= 0, s59 <= 0, x_25 >= 0, z = 1 + x_118 + x_25, z' >= 0, x_118 >= 0 encode_f(z, z') -{ -9 + 13*z' }-> s61 :|: s60 >= 0, s60 <= z' - 1, s61 >= 0, s61 <= 0, z >= 0, z' - 1 >= 0 encode_f(z, z') -{ 8 + 13*x_130 + 13*x_29 }-> s65 :|: s62 >= 0, s62 <= x_130, s63 >= 0, s63 <= x_29, s64 >= 0, s64 <= 0, s65 >= 0, s65 <= 0, z >= 0, x_130 >= 0, z' = 1 + x_130 + x_29, x_29 >= 0 encode_f(z, z') -{ 0 }-> 0 :|: z >= 0, z' >= 0 encode_g(z) -{ -10 + 13*z }-> s139 :|: s138 >= 0, s138 <= z - 1, s139 >= 0, s139 <= 1 + s138 + 1, z - 1 >= 0 encode_g(z) -{ 7 + 13*x_133 + 13*x_210 }-> s143 :|: s140 >= 0, s140 <= x_133, s141 >= 0, s141 <= x_210, s142 >= 0, s142 <= 0, s143 >= 0, s143 <= s142 + 1, z = 1 + x_133 + x_210, x_133 >= 0, x_210 >= 0 encode_g(z) -{ -9 + 13*z }-> s146 :|: s144 >= 0, s144 <= z - 1, s145 >= 0, s145 <= s144 + 1, s146 >= 0, s146 <= s145 + 1, z - 1 >= 0 encode_g(z) -{ 0 }-> 0 :|: z >= 0 encode_g(z) -{ 1 }-> 1 + x :|: z >= 0, x >= 0, 0 = x encode_s(z) -{ 0 }-> 0 :|: z >= 0 encode_s(z) -{ 2 + 13*z }-> 1 + s66 :|: s66 >= 0, s66 <= z, z >= 0 f(z, z') -{ 4 }-> s :|: s >= 0, s <= 0, z' >= 0, z = z' f(z, z') -{ 0 }-> 0 :|: z >= 0, z' >= 0 g(z) -{ 1 }-> 1 + z :|: z >= 0 Function symbols to be analyzed: {encode_g}, {encode_s} Previous analysis results are: g: runtime: O(1) [1], size: O(n^1) [1 + z] f: runtime: O(1) [2], size: O(1) [0] encArg: runtime: O(n^1) [2 + 13*z], size: O(n^1) [z] encode_f: runtime: O(n^1) [20 + 13*z + 13*z'], size: O(1) [0] ---------------------------------------- (47) IntTrsBoundProof (UPPER BOUND(ID)) Computed SIZE bound using CoFloCo for: encode_g after applying outer abstraction to obtain an ITS, resulting in: O(n^1) with polynomial bound: 1 + z ---------------------------------------- (48) Obligation: Complexity RNTS consisting of the following rules: encArg(z) -{ 2 }-> s' :|: s' >= 0, s' <= 0, x_1 >= 0, z = 1 + x_1 + x_2, x_2 >= 0 encArg(z) -{ 7 + 13*x_115 + 13*x_24 }-> s103 :|: s100 >= 0, s100 <= x_115, s101 >= 0, s101 <= x_24, s102 >= 0, s102 <= 0, s103 >= 0, s103 <= s102 + 1, z = 1 + (1 + x_115 + x_24), x_115 >= 0, x_24 >= 0 encArg(z) -{ -22 + 13*z }-> s106 :|: s104 >= 0, s104 <= z - 2, s105 >= 0, s105 <= s104 + 1, s106 >= 0, s106 <= s105 + 1, z - 2 >= 0 encArg(z) -{ 4 + 13*x_1' }-> s11 :|: s10 >= 0, s10 <= x_1', s11 >= 0, s11 <= 0, x_1' >= 0, x_2 >= 0, z = 1 + (1 + x_1') + x_2 encArg(z) -{ 10 + 13*x_1'' + 13*x_15 + 13*x_2' }-> s16 :|: s12 >= 0, s12 <= x_1'', s13 >= 0, s13 <= x_2', s14 >= 0, s14 <= 0, s15 >= 0, s15 <= x_15, s16 >= 0, s16 <= 0, x_15 >= 0, z = 1 + (1 + x_1'' + x_2') + (1 + x_15), x_1'' >= 0, x_2' >= 0 encArg(z) -{ 14 + 13*x_1'' + 13*x_16 + 13*x_2' + 13*x_21 }-> s23 :|: s17 >= 0, s17 <= x_1'', s18 >= 0, s18 <= x_2', s19 >= 0, s19 <= 0, s20 >= 0, s20 <= x_16, s21 >= 0, s21 <= x_21, s22 >= 0, s22 <= 0, s23 >= 0, s23 <= 0, x_1'' >= 0, x_16 >= 0, x_2' >= 0, z = 1 + (1 + x_1'' + x_2') + (1 + x_16 + x_21), x_21 >= 0 encArg(z) -{ 8 + 13*x_1'' + 13*x_2' }-> s27 :|: s24 >= 0, s24 <= x_1'', s25 >= 0, s25 <= x_2', s26 >= 0, s26 <= 0, s27 >= 0, s27 <= 0, x_1'' >= 0, x_2' >= 0, z = 1 + (1 + x_1'' + x_2') + x_2, x_2 >= 0 encArg(z) -{ 4 + 13*x_111 }-> s29 :|: s28 >= 0, s28 <= x_111, s29 >= 0, s29 <= 0, x_1 >= 0, z = 1 + x_1 + (1 + x_111), x_111 >= 0 encArg(z) -{ 8 + 13*x_112 + 13*x_23 }-> s33 :|: s30 >= 0, s30 <= x_112, s31 >= 0, s31 <= x_23, s32 >= 0, s32 <= 0, s33 >= 0, s33 <= 0, x_1 >= 0, z = 1 + x_1 + (1 + x_112 + x_23), x_23 >= 0, x_112 >= 0 encArg(z) -{ 6 + 13*x_1' + 13*x_12 }-> s4 :|: s2 >= 0, s2 <= x_1', s3 >= 0, s3 <= x_12, s4 >= 0, s4 <= 0, z = 1 + (1 + x_1') + (1 + x_12), x_1' >= 0, x_12 >= 0 encArg(z) -{ 7 + 13*x_1' + 13*x_14 }-> s70 :|: s67 >= 0, s67 <= x_1', s68 >= 0, s68 <= x_14, s69 >= 0, s69 <= s68 + 1, s70 >= 0, s70 <= 0, z = 1 + (1 + x_1') + (1 + x_14), x_14 >= 0, x_1' >= 0 encArg(z) -{ 11 + 13*x_1'' + 13*x_17 + 13*x_2' }-> s76 :|: s71 >= 0, s71 <= x_1'', s72 >= 0, s72 <= x_2', s73 >= 0, s73 <= 0, s74 >= 0, s74 <= x_17, s75 >= 0, s75 <= s74 + 1, s76 >= 0, s76 <= 0, x_1'' >= 0, z = 1 + (1 + x_1'' + x_2') + (1 + x_17), x_2' >= 0, x_17 >= 0 encArg(z) -{ 7 + 13*x_11 + 13*x_18 }-> s80 :|: s77 >= 0, s77 <= x_11, s78 >= 0, s78 <= s77 + 1, s79 >= 0, s79 <= x_18, s80 >= 0, s80 <= 0, x_11 >= 0, z = 1 + (1 + x_11) + (1 + x_18), x_18 >= 0 encArg(z) -{ 11 + 13*x_11 + 13*x_19 + 13*x_22 }-> s86 :|: s81 >= 0, s81 <= x_11, s82 >= 0, s82 <= s81 + 1, s83 >= 0, s83 <= x_19, s84 >= 0, s84 <= x_22, s85 >= 0, s85 <= 0, s86 >= 0, s86 <= 0, x_11 >= 0, z = 1 + (1 + x_11) + (1 + x_19 + x_22), x_22 >= 0, x_19 >= 0 encArg(z) -{ 10 + 13*x_1' + 13*x_13 + 13*x_2'' }-> s9 :|: s5 >= 0, s5 <= x_1', s6 >= 0, s6 <= x_13, s7 >= 0, s7 <= x_2'', s8 >= 0, s8 <= 0, s9 >= 0, s9 <= 0, x_13 >= 0, x_1' >= 0, x_2'' >= 0, z = 1 + (1 + x_1') + (1 + x_13 + x_2'') encArg(z) -{ 8 + 13*x_11 + 13*x_110 }-> s91 :|: s87 >= 0, s87 <= x_11, s88 >= 0, s88 <= s87 + 1, s89 >= 0, s89 <= x_110, s90 >= 0, s90 <= s89 + 1, s91 >= 0, s91 <= 0, x_11 >= 0, z = 1 + (1 + x_11) + (1 + x_110), x_110 >= 0 encArg(z) -{ 5 + 13*x_11 }-> s94 :|: s92 >= 0, s92 <= x_11, s93 >= 0, s93 <= s92 + 1, s94 >= 0, s94 <= 0, x_11 >= 0, z = 1 + (1 + x_11) + x_2, x_2 >= 0 encArg(z) -{ 5 + 13*x_113 }-> s97 :|: s95 >= 0, s95 <= x_113, s96 >= 0, s96 <= s95 + 1, s97 >= 0, s97 <= 0, x_1 >= 0, x_113 >= 0, z = 1 + x_1 + (1 + x_113) encArg(z) -{ -23 + 13*z }-> s99 :|: s98 >= 0, s98 <= z - 2, s99 >= 0, s99 <= 1 + s98 + 1, z - 2 >= 0 encArg(z) -{ 0 }-> 0 :|: z >= 0 encArg(z) -{ -11 + 13*z }-> 1 + s1 :|: s1 >= 0, s1 <= z - 1, z - 1 >= 0 encArg(z) -{ 1 }-> 1 + x :|: z - 1 >= 0, x >= 0, 0 = x encode_f(z, z') -{ 2 }-> s'' :|: s'' >= 0, s'' <= 0, z >= 0, z' >= 0 encode_f(z, z') -{ -19 + 13*z + 13*z' }-> s110 :|: s107 >= 0, s107 <= z - 1, s108 >= 0, s108 <= z' - 1, s109 >= 0, s109 <= s108 + 1, s110 >= 0, s110 <= 0, z - 1 >= 0, z' - 1 >= 0 encode_f(z, z') -{ -2 + 13*x_118 + 13*x_25 + 13*z' }-> s116 :|: s111 >= 0, s111 <= x_118, s112 >= 0, s112 <= x_25, s113 >= 0, s113 <= 0, s114 >= 0, s114 <= z' - 1, s115 >= 0, s115 <= s114 + 1, s116 >= 0, s116 <= 0, x_25 >= 0, z = 1 + x_118 + x_25, z' - 1 >= 0, x_118 >= 0 encode_f(z, z') -{ -19 + 13*z + 13*z' }-> s120 :|: s117 >= 0, s117 <= z - 1, s118 >= 0, s118 <= s117 + 1, s119 >= 0, s119 <= z' - 1, s120 >= 0, s120 <= 0, z' - 1 >= 0, z - 1 >= 0 encode_f(z, z') -{ -2 + 13*x_127 + 13*x_28 + 13*z }-> s126 :|: s121 >= 0, s121 <= z - 1, s122 >= 0, s122 <= s121 + 1, s123 >= 0, s123 <= x_127, s124 >= 0, s124 <= x_28, s125 >= 0, s125 <= 0, s126 >= 0, s126 <= 0, x_127 >= 0, z' = 1 + x_127 + x_28, x_28 >= 0, z - 1 >= 0 encode_f(z, z') -{ -18 + 13*z + 13*z' }-> s131 :|: s127 >= 0, s127 <= z - 1, s128 >= 0, s128 <= s127 + 1, s129 >= 0, s129 <= z' - 1, s130 >= 0, s130 <= s129 + 1, s131 >= 0, s131 <= 0, z' - 1 >= 0, z - 1 >= 0 encode_f(z, z') -{ -8 + 13*z }-> s134 :|: s132 >= 0, s132 <= z - 1, s133 >= 0, s133 <= s132 + 1, s134 >= 0, s134 <= 0, z' >= 0, z - 1 >= 0 encode_f(z, z') -{ -8 + 13*z' }-> s137 :|: s135 >= 0, s135 <= z' - 1, s136 >= 0, s136 <= s135 + 1, s137 >= 0, s137 <= 0, z >= 0, z' - 1 >= 0 encode_f(z, z') -{ -20 + 13*z + 13*z' }-> s36 :|: s34 >= 0, s34 <= z - 1, s35 >= 0, s35 <= z' - 1, s36 >= 0, s36 <= 0, z' - 1 >= 0, z - 1 >= 0 encode_f(z, z') -{ -3 + 13*x_121 + 13*x_26 + 13*z }-> s41 :|: s37 >= 0, s37 <= z - 1, s38 >= 0, s38 <= x_121, s39 >= 0, s39 <= x_26, s40 >= 0, s40 <= 0, s41 >= 0, s41 <= 0, z - 1 >= 0, x_26 >= 0, z' = 1 + x_121 + x_26, x_121 >= 0 encode_f(z, z') -{ -9 + 13*z }-> s43 :|: s42 >= 0, s42 <= z - 1, s43 >= 0, s43 <= 0, z - 1 >= 0, z' >= 0 encode_f(z, z') -{ -3 + 13*x_118 + 13*x_25 + 13*z' }-> s48 :|: s44 >= 0, s44 <= x_118, s45 >= 0, s45 <= x_25, s46 >= 0, s46 <= 0, s47 >= 0, s47 <= z' - 1, s48 >= 0, s48 <= 0, z' - 1 >= 0, x_25 >= 0, z = 1 + x_118 + x_25, x_118 >= 0 encode_f(z, z') -{ 14 + 13*x_118 + 13*x_124 + 13*x_25 + 13*x_27 }-> s55 :|: s49 >= 0, s49 <= x_118, s50 >= 0, s50 <= x_25, s51 >= 0, s51 <= 0, s52 >= 0, s52 <= x_124, s53 >= 0, s53 <= x_27, s54 >= 0, s54 <= 0, s55 >= 0, s55 <= 0, x_124 >= 0, x_25 >= 0, z = 1 + x_118 + x_25, x_27 >= 0, x_118 >= 0, z' = 1 + x_124 + x_27 encode_f(z, z') -{ 8 + 13*x_118 + 13*x_25 }-> s59 :|: s56 >= 0, s56 <= x_118, s57 >= 0, s57 <= x_25, s58 >= 0, s58 <= 0, s59 >= 0, s59 <= 0, x_25 >= 0, z = 1 + x_118 + x_25, z' >= 0, x_118 >= 0 encode_f(z, z') -{ -9 + 13*z' }-> s61 :|: s60 >= 0, s60 <= z' - 1, s61 >= 0, s61 <= 0, z >= 0, z' - 1 >= 0 encode_f(z, z') -{ 8 + 13*x_130 + 13*x_29 }-> s65 :|: s62 >= 0, s62 <= x_130, s63 >= 0, s63 <= x_29, s64 >= 0, s64 <= 0, s65 >= 0, s65 <= 0, z >= 0, x_130 >= 0, z' = 1 + x_130 + x_29, x_29 >= 0 encode_f(z, z') -{ 0 }-> 0 :|: z >= 0, z' >= 0 encode_g(z) -{ -10 + 13*z }-> s139 :|: s138 >= 0, s138 <= z - 1, s139 >= 0, s139 <= 1 + s138 + 1, z - 1 >= 0 encode_g(z) -{ 7 + 13*x_133 + 13*x_210 }-> s143 :|: s140 >= 0, s140 <= x_133, s141 >= 0, s141 <= x_210, s142 >= 0, s142 <= 0, s143 >= 0, s143 <= s142 + 1, z = 1 + x_133 + x_210, x_133 >= 0, x_210 >= 0 encode_g(z) -{ -9 + 13*z }-> s146 :|: s144 >= 0, s144 <= z - 1, s145 >= 0, s145 <= s144 + 1, s146 >= 0, s146 <= s145 + 1, z - 1 >= 0 encode_g(z) -{ 0 }-> 0 :|: z >= 0 encode_g(z) -{ 1 }-> 1 + x :|: z >= 0, x >= 0, 0 = x encode_s(z) -{ 0 }-> 0 :|: z >= 0 encode_s(z) -{ 2 + 13*z }-> 1 + s66 :|: s66 >= 0, s66 <= z, z >= 0 f(z, z') -{ 4 }-> s :|: s >= 0, s <= 0, z' >= 0, z = z' f(z, z') -{ 0 }-> 0 :|: z >= 0, z' >= 0 g(z) -{ 1 }-> 1 + z :|: z >= 0 Function symbols to be analyzed: {encode_g}, {encode_s} Previous analysis results are: g: runtime: O(1) [1], size: O(n^1) [1 + z] f: runtime: O(1) [2], size: O(1) [0] encArg: runtime: O(n^1) [2 + 13*z], size: O(n^1) [z] encode_f: runtime: O(n^1) [20 + 13*z + 13*z'], size: O(1) [0] encode_g: runtime: ?, size: O(n^1) [1 + z] ---------------------------------------- (49) IntTrsBoundProof (UPPER BOUND(ID)) Computed RUNTIME bound using CoFloCo for: encode_g after applying outer abstraction to obtain an ITS, resulting in: O(n^1) with polynomial bound: 10 + 13*z ---------------------------------------- (50) Obligation: Complexity RNTS consisting of the following rules: encArg(z) -{ 2 }-> s' :|: s' >= 0, s' <= 0, x_1 >= 0, z = 1 + x_1 + x_2, x_2 >= 0 encArg(z) -{ 7 + 13*x_115 + 13*x_24 }-> s103 :|: s100 >= 0, s100 <= x_115, s101 >= 0, s101 <= x_24, s102 >= 0, s102 <= 0, s103 >= 0, s103 <= s102 + 1, z = 1 + (1 + x_115 + x_24), x_115 >= 0, x_24 >= 0 encArg(z) -{ -22 + 13*z }-> s106 :|: s104 >= 0, s104 <= z - 2, s105 >= 0, s105 <= s104 + 1, s106 >= 0, s106 <= s105 + 1, z - 2 >= 0 encArg(z) -{ 4 + 13*x_1' }-> s11 :|: s10 >= 0, s10 <= x_1', s11 >= 0, s11 <= 0, x_1' >= 0, x_2 >= 0, z = 1 + (1 + x_1') + x_2 encArg(z) -{ 10 + 13*x_1'' + 13*x_15 + 13*x_2' }-> s16 :|: s12 >= 0, s12 <= x_1'', s13 >= 0, s13 <= x_2', s14 >= 0, s14 <= 0, s15 >= 0, s15 <= x_15, s16 >= 0, s16 <= 0, x_15 >= 0, z = 1 + (1 + x_1'' + x_2') + (1 + x_15), x_1'' >= 0, x_2' >= 0 encArg(z) -{ 14 + 13*x_1'' + 13*x_16 + 13*x_2' + 13*x_21 }-> s23 :|: s17 >= 0, s17 <= x_1'', s18 >= 0, s18 <= x_2', s19 >= 0, s19 <= 0, s20 >= 0, s20 <= x_16, s21 >= 0, s21 <= x_21, s22 >= 0, s22 <= 0, s23 >= 0, s23 <= 0, x_1'' >= 0, x_16 >= 0, x_2' >= 0, z = 1 + (1 + x_1'' + x_2') + (1 + x_16 + x_21), x_21 >= 0 encArg(z) -{ 8 + 13*x_1'' + 13*x_2' }-> s27 :|: s24 >= 0, s24 <= x_1'', s25 >= 0, s25 <= x_2', s26 >= 0, s26 <= 0, s27 >= 0, s27 <= 0, x_1'' >= 0, x_2' >= 0, z = 1 + (1 + x_1'' + x_2') + x_2, x_2 >= 0 encArg(z) -{ 4 + 13*x_111 }-> s29 :|: s28 >= 0, s28 <= x_111, s29 >= 0, s29 <= 0, x_1 >= 0, z = 1 + x_1 + (1 + x_111), x_111 >= 0 encArg(z) -{ 8 + 13*x_112 + 13*x_23 }-> s33 :|: s30 >= 0, s30 <= x_112, s31 >= 0, s31 <= x_23, s32 >= 0, s32 <= 0, s33 >= 0, s33 <= 0, x_1 >= 0, z = 1 + x_1 + (1 + x_112 + x_23), x_23 >= 0, x_112 >= 0 encArg(z) -{ 6 + 13*x_1' + 13*x_12 }-> s4 :|: s2 >= 0, s2 <= x_1', s3 >= 0, s3 <= x_12, s4 >= 0, s4 <= 0, z = 1 + (1 + x_1') + (1 + x_12), x_1' >= 0, x_12 >= 0 encArg(z) -{ 7 + 13*x_1' + 13*x_14 }-> s70 :|: s67 >= 0, s67 <= x_1', s68 >= 0, s68 <= x_14, s69 >= 0, s69 <= s68 + 1, s70 >= 0, s70 <= 0, z = 1 + (1 + x_1') + (1 + x_14), x_14 >= 0, x_1' >= 0 encArg(z) -{ 11 + 13*x_1'' + 13*x_17 + 13*x_2' }-> s76 :|: s71 >= 0, s71 <= x_1'', s72 >= 0, s72 <= x_2', s73 >= 0, s73 <= 0, s74 >= 0, s74 <= x_17, s75 >= 0, s75 <= s74 + 1, s76 >= 0, s76 <= 0, x_1'' >= 0, z = 1 + (1 + x_1'' + x_2') + (1 + x_17), x_2' >= 0, x_17 >= 0 encArg(z) -{ 7 + 13*x_11 + 13*x_18 }-> s80 :|: s77 >= 0, s77 <= x_11, s78 >= 0, s78 <= s77 + 1, s79 >= 0, s79 <= x_18, s80 >= 0, s80 <= 0, x_11 >= 0, z = 1 + (1 + x_11) + (1 + x_18), x_18 >= 0 encArg(z) -{ 11 + 13*x_11 + 13*x_19 + 13*x_22 }-> s86 :|: s81 >= 0, s81 <= x_11, s82 >= 0, s82 <= s81 + 1, s83 >= 0, s83 <= x_19, s84 >= 0, s84 <= x_22, s85 >= 0, s85 <= 0, s86 >= 0, s86 <= 0, x_11 >= 0, z = 1 + (1 + x_11) + (1 + x_19 + x_22), x_22 >= 0, x_19 >= 0 encArg(z) -{ 10 + 13*x_1' + 13*x_13 + 13*x_2'' }-> s9 :|: s5 >= 0, s5 <= x_1', s6 >= 0, s6 <= x_13, s7 >= 0, s7 <= x_2'', s8 >= 0, s8 <= 0, s9 >= 0, s9 <= 0, x_13 >= 0, x_1' >= 0, x_2'' >= 0, z = 1 + (1 + x_1') + (1 + x_13 + x_2'') encArg(z) -{ 8 + 13*x_11 + 13*x_110 }-> s91 :|: s87 >= 0, s87 <= x_11, s88 >= 0, s88 <= s87 + 1, s89 >= 0, s89 <= x_110, s90 >= 0, s90 <= s89 + 1, s91 >= 0, s91 <= 0, x_11 >= 0, z = 1 + (1 + x_11) + (1 + x_110), x_110 >= 0 encArg(z) -{ 5 + 13*x_11 }-> s94 :|: s92 >= 0, s92 <= x_11, s93 >= 0, s93 <= s92 + 1, s94 >= 0, s94 <= 0, x_11 >= 0, z = 1 + (1 + x_11) + x_2, x_2 >= 0 encArg(z) -{ 5 + 13*x_113 }-> s97 :|: s95 >= 0, s95 <= x_113, s96 >= 0, s96 <= s95 + 1, s97 >= 0, s97 <= 0, x_1 >= 0, x_113 >= 0, z = 1 + x_1 + (1 + x_113) encArg(z) -{ -23 + 13*z }-> s99 :|: s98 >= 0, s98 <= z - 2, s99 >= 0, s99 <= 1 + s98 + 1, z - 2 >= 0 encArg(z) -{ 0 }-> 0 :|: z >= 0 encArg(z) -{ -11 + 13*z }-> 1 + s1 :|: s1 >= 0, s1 <= z - 1, z - 1 >= 0 encArg(z) -{ 1 }-> 1 + x :|: z - 1 >= 0, x >= 0, 0 = x encode_f(z, z') -{ 2 }-> s'' :|: s'' >= 0, s'' <= 0, z >= 0, z' >= 0 encode_f(z, z') -{ -19 + 13*z + 13*z' }-> s110 :|: s107 >= 0, s107 <= z - 1, s108 >= 0, s108 <= z' - 1, s109 >= 0, s109 <= s108 + 1, s110 >= 0, s110 <= 0, z - 1 >= 0, z' - 1 >= 0 encode_f(z, z') -{ -2 + 13*x_118 + 13*x_25 + 13*z' }-> s116 :|: s111 >= 0, s111 <= x_118, s112 >= 0, s112 <= x_25, s113 >= 0, s113 <= 0, s114 >= 0, s114 <= z' - 1, s115 >= 0, s115 <= s114 + 1, s116 >= 0, s116 <= 0, x_25 >= 0, z = 1 + x_118 + x_25, z' - 1 >= 0, x_118 >= 0 encode_f(z, z') -{ -19 + 13*z + 13*z' }-> s120 :|: s117 >= 0, s117 <= z - 1, s118 >= 0, s118 <= s117 + 1, s119 >= 0, s119 <= z' - 1, s120 >= 0, s120 <= 0, z' - 1 >= 0, z - 1 >= 0 encode_f(z, z') -{ -2 + 13*x_127 + 13*x_28 + 13*z }-> s126 :|: s121 >= 0, s121 <= z - 1, s122 >= 0, s122 <= s121 + 1, s123 >= 0, s123 <= x_127, s124 >= 0, s124 <= x_28, s125 >= 0, s125 <= 0, s126 >= 0, s126 <= 0, x_127 >= 0, z' = 1 + x_127 + x_28, x_28 >= 0, z - 1 >= 0 encode_f(z, z') -{ -18 + 13*z + 13*z' }-> s131 :|: s127 >= 0, s127 <= z - 1, s128 >= 0, s128 <= s127 + 1, s129 >= 0, s129 <= z' - 1, s130 >= 0, s130 <= s129 + 1, s131 >= 0, s131 <= 0, z' - 1 >= 0, z - 1 >= 0 encode_f(z, z') -{ -8 + 13*z }-> s134 :|: s132 >= 0, s132 <= z - 1, s133 >= 0, s133 <= s132 + 1, s134 >= 0, s134 <= 0, z' >= 0, z - 1 >= 0 encode_f(z, z') -{ -8 + 13*z' }-> s137 :|: s135 >= 0, s135 <= z' - 1, s136 >= 0, s136 <= s135 + 1, s137 >= 0, s137 <= 0, z >= 0, z' - 1 >= 0 encode_f(z, z') -{ -20 + 13*z + 13*z' }-> s36 :|: s34 >= 0, s34 <= z - 1, s35 >= 0, s35 <= z' - 1, s36 >= 0, s36 <= 0, z' - 1 >= 0, z - 1 >= 0 encode_f(z, z') -{ -3 + 13*x_121 + 13*x_26 + 13*z }-> s41 :|: s37 >= 0, s37 <= z - 1, s38 >= 0, s38 <= x_121, s39 >= 0, s39 <= x_26, s40 >= 0, s40 <= 0, s41 >= 0, s41 <= 0, z - 1 >= 0, x_26 >= 0, z' = 1 + x_121 + x_26, x_121 >= 0 encode_f(z, z') -{ -9 + 13*z }-> s43 :|: s42 >= 0, s42 <= z - 1, s43 >= 0, s43 <= 0, z - 1 >= 0, z' >= 0 encode_f(z, z') -{ -3 + 13*x_118 + 13*x_25 + 13*z' }-> s48 :|: s44 >= 0, s44 <= x_118, s45 >= 0, s45 <= x_25, s46 >= 0, s46 <= 0, s47 >= 0, s47 <= z' - 1, s48 >= 0, s48 <= 0, z' - 1 >= 0, x_25 >= 0, z = 1 + x_118 + x_25, x_118 >= 0 encode_f(z, z') -{ 14 + 13*x_118 + 13*x_124 + 13*x_25 + 13*x_27 }-> s55 :|: s49 >= 0, s49 <= x_118, s50 >= 0, s50 <= x_25, s51 >= 0, s51 <= 0, s52 >= 0, s52 <= x_124, s53 >= 0, s53 <= x_27, s54 >= 0, s54 <= 0, s55 >= 0, s55 <= 0, x_124 >= 0, x_25 >= 0, z = 1 + x_118 + x_25, x_27 >= 0, x_118 >= 0, z' = 1 + x_124 + x_27 encode_f(z, z') -{ 8 + 13*x_118 + 13*x_25 }-> s59 :|: s56 >= 0, s56 <= x_118, s57 >= 0, s57 <= x_25, s58 >= 0, s58 <= 0, s59 >= 0, s59 <= 0, x_25 >= 0, z = 1 + x_118 + x_25, z' >= 0, x_118 >= 0 encode_f(z, z') -{ -9 + 13*z' }-> s61 :|: s60 >= 0, s60 <= z' - 1, s61 >= 0, s61 <= 0, z >= 0, z' - 1 >= 0 encode_f(z, z') -{ 8 + 13*x_130 + 13*x_29 }-> s65 :|: s62 >= 0, s62 <= x_130, s63 >= 0, s63 <= x_29, s64 >= 0, s64 <= 0, s65 >= 0, s65 <= 0, z >= 0, x_130 >= 0, z' = 1 + x_130 + x_29, x_29 >= 0 encode_f(z, z') -{ 0 }-> 0 :|: z >= 0, z' >= 0 encode_g(z) -{ -10 + 13*z }-> s139 :|: s138 >= 0, s138 <= z - 1, s139 >= 0, s139 <= 1 + s138 + 1, z - 1 >= 0 encode_g(z) -{ 7 + 13*x_133 + 13*x_210 }-> s143 :|: s140 >= 0, s140 <= x_133, s141 >= 0, s141 <= x_210, s142 >= 0, s142 <= 0, s143 >= 0, s143 <= s142 + 1, z = 1 + x_133 + x_210, x_133 >= 0, x_210 >= 0 encode_g(z) -{ -9 + 13*z }-> s146 :|: s144 >= 0, s144 <= z - 1, s145 >= 0, s145 <= s144 + 1, s146 >= 0, s146 <= s145 + 1, z - 1 >= 0 encode_g(z) -{ 0 }-> 0 :|: z >= 0 encode_g(z) -{ 1 }-> 1 + x :|: z >= 0, x >= 0, 0 = x encode_s(z) -{ 0 }-> 0 :|: z >= 0 encode_s(z) -{ 2 + 13*z }-> 1 + s66 :|: s66 >= 0, s66 <= z, z >= 0 f(z, z') -{ 4 }-> s :|: s >= 0, s <= 0, z' >= 0, z = z' f(z, z') -{ 0 }-> 0 :|: z >= 0, z' >= 0 g(z) -{ 1 }-> 1 + z :|: z >= 0 Function symbols to be analyzed: {encode_s} Previous analysis results are: g: runtime: O(1) [1], size: O(n^1) [1 + z] f: runtime: O(1) [2], size: O(1) [0] encArg: runtime: O(n^1) [2 + 13*z], size: O(n^1) [z] encode_f: runtime: O(n^1) [20 + 13*z + 13*z'], size: O(1) [0] encode_g: runtime: O(n^1) [10 + 13*z], size: O(n^1) [1 + z] ---------------------------------------- (51) ResultPropagationProof (UPPER BOUND(ID)) Applied inner abstraction using the recently inferred runtime/size bounds where possible. ---------------------------------------- (52) Obligation: Complexity RNTS consisting of the following rules: encArg(z) -{ 2 }-> s' :|: s' >= 0, s' <= 0, x_1 >= 0, z = 1 + x_1 + x_2, x_2 >= 0 encArg(z) -{ 7 + 13*x_115 + 13*x_24 }-> s103 :|: s100 >= 0, s100 <= x_115, s101 >= 0, s101 <= x_24, s102 >= 0, s102 <= 0, s103 >= 0, s103 <= s102 + 1, z = 1 + (1 + x_115 + x_24), x_115 >= 0, x_24 >= 0 encArg(z) -{ -22 + 13*z }-> s106 :|: s104 >= 0, s104 <= z - 2, s105 >= 0, s105 <= s104 + 1, s106 >= 0, s106 <= s105 + 1, z - 2 >= 0 encArg(z) -{ 4 + 13*x_1' }-> s11 :|: s10 >= 0, s10 <= x_1', s11 >= 0, s11 <= 0, x_1' >= 0, x_2 >= 0, z = 1 + (1 + x_1') + x_2 encArg(z) -{ 10 + 13*x_1'' + 13*x_15 + 13*x_2' }-> s16 :|: s12 >= 0, s12 <= x_1'', s13 >= 0, s13 <= x_2', s14 >= 0, s14 <= 0, s15 >= 0, s15 <= x_15, s16 >= 0, s16 <= 0, x_15 >= 0, z = 1 + (1 + x_1'' + x_2') + (1 + x_15), x_1'' >= 0, x_2' >= 0 encArg(z) -{ 14 + 13*x_1'' + 13*x_16 + 13*x_2' + 13*x_21 }-> s23 :|: s17 >= 0, s17 <= x_1'', s18 >= 0, s18 <= x_2', s19 >= 0, s19 <= 0, s20 >= 0, s20 <= x_16, s21 >= 0, s21 <= x_21, s22 >= 0, s22 <= 0, s23 >= 0, s23 <= 0, x_1'' >= 0, x_16 >= 0, x_2' >= 0, z = 1 + (1 + x_1'' + x_2') + (1 + x_16 + x_21), x_21 >= 0 encArg(z) -{ 8 + 13*x_1'' + 13*x_2' }-> s27 :|: s24 >= 0, s24 <= x_1'', s25 >= 0, s25 <= x_2', s26 >= 0, s26 <= 0, s27 >= 0, s27 <= 0, x_1'' >= 0, x_2' >= 0, z = 1 + (1 + x_1'' + x_2') + x_2, x_2 >= 0 encArg(z) -{ 4 + 13*x_111 }-> s29 :|: s28 >= 0, s28 <= x_111, s29 >= 0, s29 <= 0, x_1 >= 0, z = 1 + x_1 + (1 + x_111), x_111 >= 0 encArg(z) -{ 8 + 13*x_112 + 13*x_23 }-> s33 :|: s30 >= 0, s30 <= x_112, s31 >= 0, s31 <= x_23, s32 >= 0, s32 <= 0, s33 >= 0, s33 <= 0, x_1 >= 0, z = 1 + x_1 + (1 + x_112 + x_23), x_23 >= 0, x_112 >= 0 encArg(z) -{ 6 + 13*x_1' + 13*x_12 }-> s4 :|: s2 >= 0, s2 <= x_1', s3 >= 0, s3 <= x_12, s4 >= 0, s4 <= 0, z = 1 + (1 + x_1') + (1 + x_12), x_1' >= 0, x_12 >= 0 encArg(z) -{ 7 + 13*x_1' + 13*x_14 }-> s70 :|: s67 >= 0, s67 <= x_1', s68 >= 0, s68 <= x_14, s69 >= 0, s69 <= s68 + 1, s70 >= 0, s70 <= 0, z = 1 + (1 + x_1') + (1 + x_14), x_14 >= 0, x_1' >= 0 encArg(z) -{ 11 + 13*x_1'' + 13*x_17 + 13*x_2' }-> s76 :|: s71 >= 0, s71 <= x_1'', s72 >= 0, s72 <= x_2', s73 >= 0, s73 <= 0, s74 >= 0, s74 <= x_17, s75 >= 0, s75 <= s74 + 1, s76 >= 0, s76 <= 0, x_1'' >= 0, z = 1 + (1 + x_1'' + x_2') + (1 + x_17), x_2' >= 0, x_17 >= 0 encArg(z) -{ 7 + 13*x_11 + 13*x_18 }-> s80 :|: s77 >= 0, s77 <= x_11, s78 >= 0, s78 <= s77 + 1, s79 >= 0, s79 <= x_18, s80 >= 0, s80 <= 0, x_11 >= 0, z = 1 + (1 + x_11) + (1 + x_18), x_18 >= 0 encArg(z) -{ 11 + 13*x_11 + 13*x_19 + 13*x_22 }-> s86 :|: s81 >= 0, s81 <= x_11, s82 >= 0, s82 <= s81 + 1, s83 >= 0, s83 <= x_19, s84 >= 0, s84 <= x_22, s85 >= 0, s85 <= 0, s86 >= 0, s86 <= 0, x_11 >= 0, z = 1 + (1 + x_11) + (1 + x_19 + x_22), x_22 >= 0, x_19 >= 0 encArg(z) -{ 10 + 13*x_1' + 13*x_13 + 13*x_2'' }-> s9 :|: s5 >= 0, s5 <= x_1', s6 >= 0, s6 <= x_13, s7 >= 0, s7 <= x_2'', s8 >= 0, s8 <= 0, s9 >= 0, s9 <= 0, x_13 >= 0, x_1' >= 0, x_2'' >= 0, z = 1 + (1 + x_1') + (1 + x_13 + x_2'') encArg(z) -{ 8 + 13*x_11 + 13*x_110 }-> s91 :|: s87 >= 0, s87 <= x_11, s88 >= 0, s88 <= s87 + 1, s89 >= 0, s89 <= x_110, s90 >= 0, s90 <= s89 + 1, s91 >= 0, s91 <= 0, x_11 >= 0, z = 1 + (1 + x_11) + (1 + x_110), x_110 >= 0 encArg(z) -{ 5 + 13*x_11 }-> s94 :|: s92 >= 0, s92 <= x_11, s93 >= 0, s93 <= s92 + 1, s94 >= 0, s94 <= 0, x_11 >= 0, z = 1 + (1 + x_11) + x_2, x_2 >= 0 encArg(z) -{ 5 + 13*x_113 }-> s97 :|: s95 >= 0, s95 <= x_113, s96 >= 0, s96 <= s95 + 1, s97 >= 0, s97 <= 0, x_1 >= 0, x_113 >= 0, z = 1 + x_1 + (1 + x_113) encArg(z) -{ -23 + 13*z }-> s99 :|: s98 >= 0, s98 <= z - 2, s99 >= 0, s99 <= 1 + s98 + 1, z - 2 >= 0 encArg(z) -{ 0 }-> 0 :|: z >= 0 encArg(z) -{ -11 + 13*z }-> 1 + s1 :|: s1 >= 0, s1 <= z - 1, z - 1 >= 0 encArg(z) -{ 1 }-> 1 + x :|: z - 1 >= 0, x >= 0, 0 = x encode_f(z, z') -{ 2 }-> s'' :|: s'' >= 0, s'' <= 0, z >= 0, z' >= 0 encode_f(z, z') -{ -19 + 13*z + 13*z' }-> s110 :|: s107 >= 0, s107 <= z - 1, s108 >= 0, s108 <= z' - 1, s109 >= 0, s109 <= s108 + 1, s110 >= 0, s110 <= 0, z - 1 >= 0, z' - 1 >= 0 encode_f(z, z') -{ -2 + 13*x_118 + 13*x_25 + 13*z' }-> s116 :|: s111 >= 0, s111 <= x_118, s112 >= 0, s112 <= x_25, s113 >= 0, s113 <= 0, s114 >= 0, s114 <= z' - 1, s115 >= 0, s115 <= s114 + 1, s116 >= 0, s116 <= 0, x_25 >= 0, z = 1 + x_118 + x_25, z' - 1 >= 0, x_118 >= 0 encode_f(z, z') -{ -19 + 13*z + 13*z' }-> s120 :|: s117 >= 0, s117 <= z - 1, s118 >= 0, s118 <= s117 + 1, s119 >= 0, s119 <= z' - 1, s120 >= 0, s120 <= 0, z' - 1 >= 0, z - 1 >= 0 encode_f(z, z') -{ -2 + 13*x_127 + 13*x_28 + 13*z }-> s126 :|: s121 >= 0, s121 <= z - 1, s122 >= 0, s122 <= s121 + 1, s123 >= 0, s123 <= x_127, s124 >= 0, s124 <= x_28, s125 >= 0, s125 <= 0, s126 >= 0, s126 <= 0, x_127 >= 0, z' = 1 + x_127 + x_28, x_28 >= 0, z - 1 >= 0 encode_f(z, z') -{ -18 + 13*z + 13*z' }-> s131 :|: s127 >= 0, s127 <= z - 1, s128 >= 0, s128 <= s127 + 1, s129 >= 0, s129 <= z' - 1, s130 >= 0, s130 <= s129 + 1, s131 >= 0, s131 <= 0, z' - 1 >= 0, z - 1 >= 0 encode_f(z, z') -{ -8 + 13*z }-> s134 :|: s132 >= 0, s132 <= z - 1, s133 >= 0, s133 <= s132 + 1, s134 >= 0, s134 <= 0, z' >= 0, z - 1 >= 0 encode_f(z, z') -{ -8 + 13*z' }-> s137 :|: s135 >= 0, s135 <= z' - 1, s136 >= 0, s136 <= s135 + 1, s137 >= 0, s137 <= 0, z >= 0, z' - 1 >= 0 encode_f(z, z') -{ -20 + 13*z + 13*z' }-> s36 :|: s34 >= 0, s34 <= z - 1, s35 >= 0, s35 <= z' - 1, s36 >= 0, s36 <= 0, z' - 1 >= 0, z - 1 >= 0 encode_f(z, z') -{ -3 + 13*x_121 + 13*x_26 + 13*z }-> s41 :|: s37 >= 0, s37 <= z - 1, s38 >= 0, s38 <= x_121, s39 >= 0, s39 <= x_26, s40 >= 0, s40 <= 0, s41 >= 0, s41 <= 0, z - 1 >= 0, x_26 >= 0, z' = 1 + x_121 + x_26, x_121 >= 0 encode_f(z, z') -{ -9 + 13*z }-> s43 :|: s42 >= 0, s42 <= z - 1, s43 >= 0, s43 <= 0, z - 1 >= 0, z' >= 0 encode_f(z, z') -{ -3 + 13*x_118 + 13*x_25 + 13*z' }-> s48 :|: s44 >= 0, s44 <= x_118, s45 >= 0, s45 <= x_25, s46 >= 0, s46 <= 0, s47 >= 0, s47 <= z' - 1, s48 >= 0, s48 <= 0, z' - 1 >= 0, x_25 >= 0, z = 1 + x_118 + x_25, x_118 >= 0 encode_f(z, z') -{ 14 + 13*x_118 + 13*x_124 + 13*x_25 + 13*x_27 }-> s55 :|: s49 >= 0, s49 <= x_118, s50 >= 0, s50 <= x_25, s51 >= 0, s51 <= 0, s52 >= 0, s52 <= x_124, s53 >= 0, s53 <= x_27, s54 >= 0, s54 <= 0, s55 >= 0, s55 <= 0, x_124 >= 0, x_25 >= 0, z = 1 + x_118 + x_25, x_27 >= 0, x_118 >= 0, z' = 1 + x_124 + x_27 encode_f(z, z') -{ 8 + 13*x_118 + 13*x_25 }-> s59 :|: s56 >= 0, s56 <= x_118, s57 >= 0, s57 <= x_25, s58 >= 0, s58 <= 0, s59 >= 0, s59 <= 0, x_25 >= 0, z = 1 + x_118 + x_25, z' >= 0, x_118 >= 0 encode_f(z, z') -{ -9 + 13*z' }-> s61 :|: s60 >= 0, s60 <= z' - 1, s61 >= 0, s61 <= 0, z >= 0, z' - 1 >= 0 encode_f(z, z') -{ 8 + 13*x_130 + 13*x_29 }-> s65 :|: s62 >= 0, s62 <= x_130, s63 >= 0, s63 <= x_29, s64 >= 0, s64 <= 0, s65 >= 0, s65 <= 0, z >= 0, x_130 >= 0, z' = 1 + x_130 + x_29, x_29 >= 0 encode_f(z, z') -{ 0 }-> 0 :|: z >= 0, z' >= 0 encode_g(z) -{ -10 + 13*z }-> s139 :|: s138 >= 0, s138 <= z - 1, s139 >= 0, s139 <= 1 + s138 + 1, z - 1 >= 0 encode_g(z) -{ 7 + 13*x_133 + 13*x_210 }-> s143 :|: s140 >= 0, s140 <= x_133, s141 >= 0, s141 <= x_210, s142 >= 0, s142 <= 0, s143 >= 0, s143 <= s142 + 1, z = 1 + x_133 + x_210, x_133 >= 0, x_210 >= 0 encode_g(z) -{ -9 + 13*z }-> s146 :|: s144 >= 0, s144 <= z - 1, s145 >= 0, s145 <= s144 + 1, s146 >= 0, s146 <= s145 + 1, z - 1 >= 0 encode_g(z) -{ 0 }-> 0 :|: z >= 0 encode_g(z) -{ 1 }-> 1 + x :|: z >= 0, x >= 0, 0 = x encode_s(z) -{ 0 }-> 0 :|: z >= 0 encode_s(z) -{ 2 + 13*z }-> 1 + s66 :|: s66 >= 0, s66 <= z, z >= 0 f(z, z') -{ 4 }-> s :|: s >= 0, s <= 0, z' >= 0, z = z' f(z, z') -{ 0 }-> 0 :|: z >= 0, z' >= 0 g(z) -{ 1 }-> 1 + z :|: z >= 0 Function symbols to be analyzed: {encode_s} Previous analysis results are: g: runtime: O(1) [1], size: O(n^1) [1 + z] f: runtime: O(1) [2], size: O(1) [0] encArg: runtime: O(n^1) [2 + 13*z], size: O(n^1) [z] encode_f: runtime: O(n^1) [20 + 13*z + 13*z'], size: O(1) [0] encode_g: runtime: O(n^1) [10 + 13*z], size: O(n^1) [1 + z] ---------------------------------------- (53) IntTrsBoundProof (UPPER BOUND(ID)) Computed SIZE bound using CoFloCo for: encode_s after applying outer abstraction to obtain an ITS, resulting in: O(n^1) with polynomial bound: 1 + z ---------------------------------------- (54) Obligation: Complexity RNTS consisting of the following rules: encArg(z) -{ 2 }-> s' :|: s' >= 0, s' <= 0, x_1 >= 0, z = 1 + x_1 + x_2, x_2 >= 0 encArg(z) -{ 7 + 13*x_115 + 13*x_24 }-> s103 :|: s100 >= 0, s100 <= x_115, s101 >= 0, s101 <= x_24, s102 >= 0, s102 <= 0, s103 >= 0, s103 <= s102 + 1, z = 1 + (1 + x_115 + x_24), x_115 >= 0, x_24 >= 0 encArg(z) -{ -22 + 13*z }-> s106 :|: s104 >= 0, s104 <= z - 2, s105 >= 0, s105 <= s104 + 1, s106 >= 0, s106 <= s105 + 1, z - 2 >= 0 encArg(z) -{ 4 + 13*x_1' }-> s11 :|: s10 >= 0, s10 <= x_1', s11 >= 0, s11 <= 0, x_1' >= 0, x_2 >= 0, z = 1 + (1 + x_1') + x_2 encArg(z) -{ 10 + 13*x_1'' + 13*x_15 + 13*x_2' }-> s16 :|: s12 >= 0, s12 <= x_1'', s13 >= 0, s13 <= x_2', s14 >= 0, s14 <= 0, s15 >= 0, s15 <= x_15, s16 >= 0, s16 <= 0, x_15 >= 0, z = 1 + (1 + x_1'' + x_2') + (1 + x_15), x_1'' >= 0, x_2' >= 0 encArg(z) -{ 14 + 13*x_1'' + 13*x_16 + 13*x_2' + 13*x_21 }-> s23 :|: s17 >= 0, s17 <= x_1'', s18 >= 0, s18 <= x_2', s19 >= 0, s19 <= 0, s20 >= 0, s20 <= x_16, s21 >= 0, s21 <= x_21, s22 >= 0, s22 <= 0, s23 >= 0, s23 <= 0, x_1'' >= 0, x_16 >= 0, x_2' >= 0, z = 1 + (1 + x_1'' + x_2') + (1 + x_16 + x_21), x_21 >= 0 encArg(z) -{ 8 + 13*x_1'' + 13*x_2' }-> s27 :|: s24 >= 0, s24 <= x_1'', s25 >= 0, s25 <= x_2', s26 >= 0, s26 <= 0, s27 >= 0, s27 <= 0, x_1'' >= 0, x_2' >= 0, z = 1 + (1 + x_1'' + x_2') + x_2, x_2 >= 0 encArg(z) -{ 4 + 13*x_111 }-> s29 :|: s28 >= 0, s28 <= x_111, s29 >= 0, s29 <= 0, x_1 >= 0, z = 1 + x_1 + (1 + x_111), x_111 >= 0 encArg(z) -{ 8 + 13*x_112 + 13*x_23 }-> s33 :|: s30 >= 0, s30 <= x_112, s31 >= 0, s31 <= x_23, s32 >= 0, s32 <= 0, s33 >= 0, s33 <= 0, x_1 >= 0, z = 1 + x_1 + (1 + x_112 + x_23), x_23 >= 0, x_112 >= 0 encArg(z) -{ 6 + 13*x_1' + 13*x_12 }-> s4 :|: s2 >= 0, s2 <= x_1', s3 >= 0, s3 <= x_12, s4 >= 0, s4 <= 0, z = 1 + (1 + x_1') + (1 + x_12), x_1' >= 0, x_12 >= 0 encArg(z) -{ 7 + 13*x_1' + 13*x_14 }-> s70 :|: s67 >= 0, s67 <= x_1', s68 >= 0, s68 <= x_14, s69 >= 0, s69 <= s68 + 1, s70 >= 0, s70 <= 0, z = 1 + (1 + x_1') + (1 + x_14), x_14 >= 0, x_1' >= 0 encArg(z) -{ 11 + 13*x_1'' + 13*x_17 + 13*x_2' }-> s76 :|: s71 >= 0, s71 <= x_1'', s72 >= 0, s72 <= x_2', s73 >= 0, s73 <= 0, s74 >= 0, s74 <= x_17, s75 >= 0, s75 <= s74 + 1, s76 >= 0, s76 <= 0, x_1'' >= 0, z = 1 + (1 + x_1'' + x_2') + (1 + x_17), x_2' >= 0, x_17 >= 0 encArg(z) -{ 7 + 13*x_11 + 13*x_18 }-> s80 :|: s77 >= 0, s77 <= x_11, s78 >= 0, s78 <= s77 + 1, s79 >= 0, s79 <= x_18, s80 >= 0, s80 <= 0, x_11 >= 0, z = 1 + (1 + x_11) + (1 + x_18), x_18 >= 0 encArg(z) -{ 11 + 13*x_11 + 13*x_19 + 13*x_22 }-> s86 :|: s81 >= 0, s81 <= x_11, s82 >= 0, s82 <= s81 + 1, s83 >= 0, s83 <= x_19, s84 >= 0, s84 <= x_22, s85 >= 0, s85 <= 0, s86 >= 0, s86 <= 0, x_11 >= 0, z = 1 + (1 + x_11) + (1 + x_19 + x_22), x_22 >= 0, x_19 >= 0 encArg(z) -{ 10 + 13*x_1' + 13*x_13 + 13*x_2'' }-> s9 :|: s5 >= 0, s5 <= x_1', s6 >= 0, s6 <= x_13, s7 >= 0, s7 <= x_2'', s8 >= 0, s8 <= 0, s9 >= 0, s9 <= 0, x_13 >= 0, x_1' >= 0, x_2'' >= 0, z = 1 + (1 + x_1') + (1 + x_13 + x_2'') encArg(z) -{ 8 + 13*x_11 + 13*x_110 }-> s91 :|: s87 >= 0, s87 <= x_11, s88 >= 0, s88 <= s87 + 1, s89 >= 0, s89 <= x_110, s90 >= 0, s90 <= s89 + 1, s91 >= 0, s91 <= 0, x_11 >= 0, z = 1 + (1 + x_11) + (1 + x_110), x_110 >= 0 encArg(z) -{ 5 + 13*x_11 }-> s94 :|: s92 >= 0, s92 <= x_11, s93 >= 0, s93 <= s92 + 1, s94 >= 0, s94 <= 0, x_11 >= 0, z = 1 + (1 + x_11) + x_2, x_2 >= 0 encArg(z) -{ 5 + 13*x_113 }-> s97 :|: s95 >= 0, s95 <= x_113, s96 >= 0, s96 <= s95 + 1, s97 >= 0, s97 <= 0, x_1 >= 0, x_113 >= 0, z = 1 + x_1 + (1 + x_113) encArg(z) -{ -23 + 13*z }-> s99 :|: s98 >= 0, s98 <= z - 2, s99 >= 0, s99 <= 1 + s98 + 1, z - 2 >= 0 encArg(z) -{ 0 }-> 0 :|: z >= 0 encArg(z) -{ -11 + 13*z }-> 1 + s1 :|: s1 >= 0, s1 <= z - 1, z - 1 >= 0 encArg(z) -{ 1 }-> 1 + x :|: z - 1 >= 0, x >= 0, 0 = x encode_f(z, z') -{ 2 }-> s'' :|: s'' >= 0, s'' <= 0, z >= 0, z' >= 0 encode_f(z, z') -{ -19 + 13*z + 13*z' }-> s110 :|: s107 >= 0, s107 <= z - 1, s108 >= 0, s108 <= z' - 1, s109 >= 0, s109 <= s108 + 1, s110 >= 0, s110 <= 0, z - 1 >= 0, z' - 1 >= 0 encode_f(z, z') -{ -2 + 13*x_118 + 13*x_25 + 13*z' }-> s116 :|: s111 >= 0, s111 <= x_118, s112 >= 0, s112 <= x_25, s113 >= 0, s113 <= 0, s114 >= 0, s114 <= z' - 1, s115 >= 0, s115 <= s114 + 1, s116 >= 0, s116 <= 0, x_25 >= 0, z = 1 + x_118 + x_25, z' - 1 >= 0, x_118 >= 0 encode_f(z, z') -{ -19 + 13*z + 13*z' }-> s120 :|: s117 >= 0, s117 <= z - 1, s118 >= 0, s118 <= s117 + 1, s119 >= 0, s119 <= z' - 1, s120 >= 0, s120 <= 0, z' - 1 >= 0, z - 1 >= 0 encode_f(z, z') -{ -2 + 13*x_127 + 13*x_28 + 13*z }-> s126 :|: s121 >= 0, s121 <= z - 1, s122 >= 0, s122 <= s121 + 1, s123 >= 0, s123 <= x_127, s124 >= 0, s124 <= x_28, s125 >= 0, s125 <= 0, s126 >= 0, s126 <= 0, x_127 >= 0, z' = 1 + x_127 + x_28, x_28 >= 0, z - 1 >= 0 encode_f(z, z') -{ -18 + 13*z + 13*z' }-> s131 :|: s127 >= 0, s127 <= z - 1, s128 >= 0, s128 <= s127 + 1, s129 >= 0, s129 <= z' - 1, s130 >= 0, s130 <= s129 + 1, s131 >= 0, s131 <= 0, z' - 1 >= 0, z - 1 >= 0 encode_f(z, z') -{ -8 + 13*z }-> s134 :|: s132 >= 0, s132 <= z - 1, s133 >= 0, s133 <= s132 + 1, s134 >= 0, s134 <= 0, z' >= 0, z - 1 >= 0 encode_f(z, z') -{ -8 + 13*z' }-> s137 :|: s135 >= 0, s135 <= z' - 1, s136 >= 0, s136 <= s135 + 1, s137 >= 0, s137 <= 0, z >= 0, z' - 1 >= 0 encode_f(z, z') -{ -20 + 13*z + 13*z' }-> s36 :|: s34 >= 0, s34 <= z - 1, s35 >= 0, s35 <= z' - 1, s36 >= 0, s36 <= 0, z' - 1 >= 0, z - 1 >= 0 encode_f(z, z') -{ -3 + 13*x_121 + 13*x_26 + 13*z }-> s41 :|: s37 >= 0, s37 <= z - 1, s38 >= 0, s38 <= x_121, s39 >= 0, s39 <= x_26, s40 >= 0, s40 <= 0, s41 >= 0, s41 <= 0, z - 1 >= 0, x_26 >= 0, z' = 1 + x_121 + x_26, x_121 >= 0 encode_f(z, z') -{ -9 + 13*z }-> s43 :|: s42 >= 0, s42 <= z - 1, s43 >= 0, s43 <= 0, z - 1 >= 0, z' >= 0 encode_f(z, z') -{ -3 + 13*x_118 + 13*x_25 + 13*z' }-> s48 :|: s44 >= 0, s44 <= x_118, s45 >= 0, s45 <= x_25, s46 >= 0, s46 <= 0, s47 >= 0, s47 <= z' - 1, s48 >= 0, s48 <= 0, z' - 1 >= 0, x_25 >= 0, z = 1 + x_118 + x_25, x_118 >= 0 encode_f(z, z') -{ 14 + 13*x_118 + 13*x_124 + 13*x_25 + 13*x_27 }-> s55 :|: s49 >= 0, s49 <= x_118, s50 >= 0, s50 <= x_25, s51 >= 0, s51 <= 0, s52 >= 0, s52 <= x_124, s53 >= 0, s53 <= x_27, s54 >= 0, s54 <= 0, s55 >= 0, s55 <= 0, x_124 >= 0, x_25 >= 0, z = 1 + x_118 + x_25, x_27 >= 0, x_118 >= 0, z' = 1 + x_124 + x_27 encode_f(z, z') -{ 8 + 13*x_118 + 13*x_25 }-> s59 :|: s56 >= 0, s56 <= x_118, s57 >= 0, s57 <= x_25, s58 >= 0, s58 <= 0, s59 >= 0, s59 <= 0, x_25 >= 0, z = 1 + x_118 + x_25, z' >= 0, x_118 >= 0 encode_f(z, z') -{ -9 + 13*z' }-> s61 :|: s60 >= 0, s60 <= z' - 1, s61 >= 0, s61 <= 0, z >= 0, z' - 1 >= 0 encode_f(z, z') -{ 8 + 13*x_130 + 13*x_29 }-> s65 :|: s62 >= 0, s62 <= x_130, s63 >= 0, s63 <= x_29, s64 >= 0, s64 <= 0, s65 >= 0, s65 <= 0, z >= 0, x_130 >= 0, z' = 1 + x_130 + x_29, x_29 >= 0 encode_f(z, z') -{ 0 }-> 0 :|: z >= 0, z' >= 0 encode_g(z) -{ -10 + 13*z }-> s139 :|: s138 >= 0, s138 <= z - 1, s139 >= 0, s139 <= 1 + s138 + 1, z - 1 >= 0 encode_g(z) -{ 7 + 13*x_133 + 13*x_210 }-> s143 :|: s140 >= 0, s140 <= x_133, s141 >= 0, s141 <= x_210, s142 >= 0, s142 <= 0, s143 >= 0, s143 <= s142 + 1, z = 1 + x_133 + x_210, x_133 >= 0, x_210 >= 0 encode_g(z) -{ -9 + 13*z }-> s146 :|: s144 >= 0, s144 <= z - 1, s145 >= 0, s145 <= s144 + 1, s146 >= 0, s146 <= s145 + 1, z - 1 >= 0 encode_g(z) -{ 0 }-> 0 :|: z >= 0 encode_g(z) -{ 1 }-> 1 + x :|: z >= 0, x >= 0, 0 = x encode_s(z) -{ 0 }-> 0 :|: z >= 0 encode_s(z) -{ 2 + 13*z }-> 1 + s66 :|: s66 >= 0, s66 <= z, z >= 0 f(z, z') -{ 4 }-> s :|: s >= 0, s <= 0, z' >= 0, z = z' f(z, z') -{ 0 }-> 0 :|: z >= 0, z' >= 0 g(z) -{ 1 }-> 1 + z :|: z >= 0 Function symbols to be analyzed: {encode_s} Previous analysis results are: g: runtime: O(1) [1], size: O(n^1) [1 + z] f: runtime: O(1) [2], size: O(1) [0] encArg: runtime: O(n^1) [2 + 13*z], size: O(n^1) [z] encode_f: runtime: O(n^1) [20 + 13*z + 13*z'], size: O(1) [0] encode_g: runtime: O(n^1) [10 + 13*z], size: O(n^1) [1 + z] encode_s: runtime: ?, size: O(n^1) [1 + z] ---------------------------------------- (55) IntTrsBoundProof (UPPER BOUND(ID)) Computed RUNTIME bound using CoFloCo for: encode_s after applying outer abstraction to obtain an ITS, resulting in: O(n^1) with polynomial bound: 2 + 13*z ---------------------------------------- (56) Obligation: Complexity RNTS consisting of the following rules: encArg(z) -{ 2 }-> s' :|: s' >= 0, s' <= 0, x_1 >= 0, z = 1 + x_1 + x_2, x_2 >= 0 encArg(z) -{ 7 + 13*x_115 + 13*x_24 }-> s103 :|: s100 >= 0, s100 <= x_115, s101 >= 0, s101 <= x_24, s102 >= 0, s102 <= 0, s103 >= 0, s103 <= s102 + 1, z = 1 + (1 + x_115 + x_24), x_115 >= 0, x_24 >= 0 encArg(z) -{ -22 + 13*z }-> s106 :|: s104 >= 0, s104 <= z - 2, s105 >= 0, s105 <= s104 + 1, s106 >= 0, s106 <= s105 + 1, z - 2 >= 0 encArg(z) -{ 4 + 13*x_1' }-> s11 :|: s10 >= 0, s10 <= x_1', s11 >= 0, s11 <= 0, x_1' >= 0, x_2 >= 0, z = 1 + (1 + x_1') + x_2 encArg(z) -{ 10 + 13*x_1'' + 13*x_15 + 13*x_2' }-> s16 :|: s12 >= 0, s12 <= x_1'', s13 >= 0, s13 <= x_2', s14 >= 0, s14 <= 0, s15 >= 0, s15 <= x_15, s16 >= 0, s16 <= 0, x_15 >= 0, z = 1 + (1 + x_1'' + x_2') + (1 + x_15), x_1'' >= 0, x_2' >= 0 encArg(z) -{ 14 + 13*x_1'' + 13*x_16 + 13*x_2' + 13*x_21 }-> s23 :|: s17 >= 0, s17 <= x_1'', s18 >= 0, s18 <= x_2', s19 >= 0, s19 <= 0, s20 >= 0, s20 <= x_16, s21 >= 0, s21 <= x_21, s22 >= 0, s22 <= 0, s23 >= 0, s23 <= 0, x_1'' >= 0, x_16 >= 0, x_2' >= 0, z = 1 + (1 + x_1'' + x_2') + (1 + x_16 + x_21), x_21 >= 0 encArg(z) -{ 8 + 13*x_1'' + 13*x_2' }-> s27 :|: s24 >= 0, s24 <= x_1'', s25 >= 0, s25 <= x_2', s26 >= 0, s26 <= 0, s27 >= 0, s27 <= 0, x_1'' >= 0, x_2' >= 0, z = 1 + (1 + x_1'' + x_2') + x_2, x_2 >= 0 encArg(z) -{ 4 + 13*x_111 }-> s29 :|: s28 >= 0, s28 <= x_111, s29 >= 0, s29 <= 0, x_1 >= 0, z = 1 + x_1 + (1 + x_111), x_111 >= 0 encArg(z) -{ 8 + 13*x_112 + 13*x_23 }-> s33 :|: s30 >= 0, s30 <= x_112, s31 >= 0, s31 <= x_23, s32 >= 0, s32 <= 0, s33 >= 0, s33 <= 0, x_1 >= 0, z = 1 + x_1 + (1 + x_112 + x_23), x_23 >= 0, x_112 >= 0 encArg(z) -{ 6 + 13*x_1' + 13*x_12 }-> s4 :|: s2 >= 0, s2 <= x_1', s3 >= 0, s3 <= x_12, s4 >= 0, s4 <= 0, z = 1 + (1 + x_1') + (1 + x_12), x_1' >= 0, x_12 >= 0 encArg(z) -{ 7 + 13*x_1' + 13*x_14 }-> s70 :|: s67 >= 0, s67 <= x_1', s68 >= 0, s68 <= x_14, s69 >= 0, s69 <= s68 + 1, s70 >= 0, s70 <= 0, z = 1 + (1 + x_1') + (1 + x_14), x_14 >= 0, x_1' >= 0 encArg(z) -{ 11 + 13*x_1'' + 13*x_17 + 13*x_2' }-> s76 :|: s71 >= 0, s71 <= x_1'', s72 >= 0, s72 <= x_2', s73 >= 0, s73 <= 0, s74 >= 0, s74 <= x_17, s75 >= 0, s75 <= s74 + 1, s76 >= 0, s76 <= 0, x_1'' >= 0, z = 1 + (1 + x_1'' + x_2') + (1 + x_17), x_2' >= 0, x_17 >= 0 encArg(z) -{ 7 + 13*x_11 + 13*x_18 }-> s80 :|: s77 >= 0, s77 <= x_11, s78 >= 0, s78 <= s77 + 1, s79 >= 0, s79 <= x_18, s80 >= 0, s80 <= 0, x_11 >= 0, z = 1 + (1 + x_11) + (1 + x_18), x_18 >= 0 encArg(z) -{ 11 + 13*x_11 + 13*x_19 + 13*x_22 }-> s86 :|: s81 >= 0, s81 <= x_11, s82 >= 0, s82 <= s81 + 1, s83 >= 0, s83 <= x_19, s84 >= 0, s84 <= x_22, s85 >= 0, s85 <= 0, s86 >= 0, s86 <= 0, x_11 >= 0, z = 1 + (1 + x_11) + (1 + x_19 + x_22), x_22 >= 0, x_19 >= 0 encArg(z) -{ 10 + 13*x_1' + 13*x_13 + 13*x_2'' }-> s9 :|: s5 >= 0, s5 <= x_1', s6 >= 0, s6 <= x_13, s7 >= 0, s7 <= x_2'', s8 >= 0, s8 <= 0, s9 >= 0, s9 <= 0, x_13 >= 0, x_1' >= 0, x_2'' >= 0, z = 1 + (1 + x_1') + (1 + x_13 + x_2'') encArg(z) -{ 8 + 13*x_11 + 13*x_110 }-> s91 :|: s87 >= 0, s87 <= x_11, s88 >= 0, s88 <= s87 + 1, s89 >= 0, s89 <= x_110, s90 >= 0, s90 <= s89 + 1, s91 >= 0, s91 <= 0, x_11 >= 0, z = 1 + (1 + x_11) + (1 + x_110), x_110 >= 0 encArg(z) -{ 5 + 13*x_11 }-> s94 :|: s92 >= 0, s92 <= x_11, s93 >= 0, s93 <= s92 + 1, s94 >= 0, s94 <= 0, x_11 >= 0, z = 1 + (1 + x_11) + x_2, x_2 >= 0 encArg(z) -{ 5 + 13*x_113 }-> s97 :|: s95 >= 0, s95 <= x_113, s96 >= 0, s96 <= s95 + 1, s97 >= 0, s97 <= 0, x_1 >= 0, x_113 >= 0, z = 1 + x_1 + (1 + x_113) encArg(z) -{ -23 + 13*z }-> s99 :|: s98 >= 0, s98 <= z - 2, s99 >= 0, s99 <= 1 + s98 + 1, z - 2 >= 0 encArg(z) -{ 0 }-> 0 :|: z >= 0 encArg(z) -{ -11 + 13*z }-> 1 + s1 :|: s1 >= 0, s1 <= z - 1, z - 1 >= 0 encArg(z) -{ 1 }-> 1 + x :|: z - 1 >= 0, x >= 0, 0 = x encode_f(z, z') -{ 2 }-> s'' :|: s'' >= 0, s'' <= 0, z >= 0, z' >= 0 encode_f(z, z') -{ -19 + 13*z + 13*z' }-> s110 :|: s107 >= 0, s107 <= z - 1, s108 >= 0, s108 <= z' - 1, s109 >= 0, s109 <= s108 + 1, s110 >= 0, s110 <= 0, z - 1 >= 0, z' - 1 >= 0 encode_f(z, z') -{ -2 + 13*x_118 + 13*x_25 + 13*z' }-> s116 :|: s111 >= 0, s111 <= x_118, s112 >= 0, s112 <= x_25, s113 >= 0, s113 <= 0, s114 >= 0, s114 <= z' - 1, s115 >= 0, s115 <= s114 + 1, s116 >= 0, s116 <= 0, x_25 >= 0, z = 1 + x_118 + x_25, z' - 1 >= 0, x_118 >= 0 encode_f(z, z') -{ -19 + 13*z + 13*z' }-> s120 :|: s117 >= 0, s117 <= z - 1, s118 >= 0, s118 <= s117 + 1, s119 >= 0, s119 <= z' - 1, s120 >= 0, s120 <= 0, z' - 1 >= 0, z - 1 >= 0 encode_f(z, z') -{ -2 + 13*x_127 + 13*x_28 + 13*z }-> s126 :|: s121 >= 0, s121 <= z - 1, s122 >= 0, s122 <= s121 + 1, s123 >= 0, s123 <= x_127, s124 >= 0, s124 <= x_28, s125 >= 0, s125 <= 0, s126 >= 0, s126 <= 0, x_127 >= 0, z' = 1 + x_127 + x_28, x_28 >= 0, z - 1 >= 0 encode_f(z, z') -{ -18 + 13*z + 13*z' }-> s131 :|: s127 >= 0, s127 <= z - 1, s128 >= 0, s128 <= s127 + 1, s129 >= 0, s129 <= z' - 1, s130 >= 0, s130 <= s129 + 1, s131 >= 0, s131 <= 0, z' - 1 >= 0, z - 1 >= 0 encode_f(z, z') -{ -8 + 13*z }-> s134 :|: s132 >= 0, s132 <= z - 1, s133 >= 0, s133 <= s132 + 1, s134 >= 0, s134 <= 0, z' >= 0, z - 1 >= 0 encode_f(z, z') -{ -8 + 13*z' }-> s137 :|: s135 >= 0, s135 <= z' - 1, s136 >= 0, s136 <= s135 + 1, s137 >= 0, s137 <= 0, z >= 0, z' - 1 >= 0 encode_f(z, z') -{ -20 + 13*z + 13*z' }-> s36 :|: s34 >= 0, s34 <= z - 1, s35 >= 0, s35 <= z' - 1, s36 >= 0, s36 <= 0, z' - 1 >= 0, z - 1 >= 0 encode_f(z, z') -{ -3 + 13*x_121 + 13*x_26 + 13*z }-> s41 :|: s37 >= 0, s37 <= z - 1, s38 >= 0, s38 <= x_121, s39 >= 0, s39 <= x_26, s40 >= 0, s40 <= 0, s41 >= 0, s41 <= 0, z - 1 >= 0, x_26 >= 0, z' = 1 + x_121 + x_26, x_121 >= 0 encode_f(z, z') -{ -9 + 13*z }-> s43 :|: s42 >= 0, s42 <= z - 1, s43 >= 0, s43 <= 0, z - 1 >= 0, z' >= 0 encode_f(z, z') -{ -3 + 13*x_118 + 13*x_25 + 13*z' }-> s48 :|: s44 >= 0, s44 <= x_118, s45 >= 0, s45 <= x_25, s46 >= 0, s46 <= 0, s47 >= 0, s47 <= z' - 1, s48 >= 0, s48 <= 0, z' - 1 >= 0, x_25 >= 0, z = 1 + x_118 + x_25, x_118 >= 0 encode_f(z, z') -{ 14 + 13*x_118 + 13*x_124 + 13*x_25 + 13*x_27 }-> s55 :|: s49 >= 0, s49 <= x_118, s50 >= 0, s50 <= x_25, s51 >= 0, s51 <= 0, s52 >= 0, s52 <= x_124, s53 >= 0, s53 <= x_27, s54 >= 0, s54 <= 0, s55 >= 0, s55 <= 0, x_124 >= 0, x_25 >= 0, z = 1 + x_118 + x_25, x_27 >= 0, x_118 >= 0, z' = 1 + x_124 + x_27 encode_f(z, z') -{ 8 + 13*x_118 + 13*x_25 }-> s59 :|: s56 >= 0, s56 <= x_118, s57 >= 0, s57 <= x_25, s58 >= 0, s58 <= 0, s59 >= 0, s59 <= 0, x_25 >= 0, z = 1 + x_118 + x_25, z' >= 0, x_118 >= 0 encode_f(z, z') -{ -9 + 13*z' }-> s61 :|: s60 >= 0, s60 <= z' - 1, s61 >= 0, s61 <= 0, z >= 0, z' - 1 >= 0 encode_f(z, z') -{ 8 + 13*x_130 + 13*x_29 }-> s65 :|: s62 >= 0, s62 <= x_130, s63 >= 0, s63 <= x_29, s64 >= 0, s64 <= 0, s65 >= 0, s65 <= 0, z >= 0, x_130 >= 0, z' = 1 + x_130 + x_29, x_29 >= 0 encode_f(z, z') -{ 0 }-> 0 :|: z >= 0, z' >= 0 encode_g(z) -{ -10 + 13*z }-> s139 :|: s138 >= 0, s138 <= z - 1, s139 >= 0, s139 <= 1 + s138 + 1, z - 1 >= 0 encode_g(z) -{ 7 + 13*x_133 + 13*x_210 }-> s143 :|: s140 >= 0, s140 <= x_133, s141 >= 0, s141 <= x_210, s142 >= 0, s142 <= 0, s143 >= 0, s143 <= s142 + 1, z = 1 + x_133 + x_210, x_133 >= 0, x_210 >= 0 encode_g(z) -{ -9 + 13*z }-> s146 :|: s144 >= 0, s144 <= z - 1, s145 >= 0, s145 <= s144 + 1, s146 >= 0, s146 <= s145 + 1, z - 1 >= 0 encode_g(z) -{ 0 }-> 0 :|: z >= 0 encode_g(z) -{ 1 }-> 1 + x :|: z >= 0, x >= 0, 0 = x encode_s(z) -{ 0 }-> 0 :|: z >= 0 encode_s(z) -{ 2 + 13*z }-> 1 + s66 :|: s66 >= 0, s66 <= z, z >= 0 f(z, z') -{ 4 }-> s :|: s >= 0, s <= 0, z' >= 0, z = z' f(z, z') -{ 0 }-> 0 :|: z >= 0, z' >= 0 g(z) -{ 1 }-> 1 + z :|: z >= 0 Function symbols to be analyzed: Previous analysis results are: g: runtime: O(1) [1], size: O(n^1) [1 + z] f: runtime: O(1) [2], size: O(1) [0] encArg: runtime: O(n^1) [2 + 13*z], size: O(n^1) [z] encode_f: runtime: O(n^1) [20 + 13*z + 13*z'], size: O(1) [0] encode_g: runtime: O(n^1) [10 + 13*z], size: O(n^1) [1 + z] encode_s: runtime: O(n^1) [2 + 13*z], size: O(n^1) [1 + z] ---------------------------------------- (57) FinalProof (FINISHED) Computed overall runtime complexity ---------------------------------------- (58) BOUNDS(1, n^1)