/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), 156 ms] (4) CpxRelTRS (5) NonCtorToCtorProof [UPPER BOUND(ID), 0 ms] (6) CpxRelTRS (7) RelTrsToWeightedTrsProof [BOTH BOUNDS(ID, ID), 0 ms] (8) CpxWeightedTrs (9) TypeInferenceProof [BOTH BOUNDS(ID, ID), 0 ms] (10) CpxTypedWeightedTrs (11) CompletionProof [UPPER BOUND(ID), 0 ms] (12) CpxTypedWeightedCompleteTrs (13) NarrowingProof [BOTH BOUNDS(ID, ID), 0 ms] (14) CpxTypedWeightedCompleteTrs (15) CpxTypedWeightedTrsToRntsProof [UPPER BOUND(ID), 0 ms] (16) CpxRNTS (17) InliningProof [UPPER BOUND(ID), 165 ms] (18) CpxRNTS (19) SimplificationProof [BOTH BOUNDS(ID, ID), 0 ms] (20) CpxRNTS (21) CpxRntsAnalysisOrderProof [BOTH BOUNDS(ID, ID), 0 ms] (22) CpxRNTS (23) ResultPropagationProof [UPPER BOUND(ID), 0 ms] (24) CpxRNTS (25) IntTrsBoundProof [UPPER BOUND(ID), 238 ms] (26) CpxRNTS (27) IntTrsBoundProof [UPPER BOUND(ID), 55 ms] (28) CpxRNTS (29) ResultPropagationProof [UPPER BOUND(ID), 0 ms] (30) CpxRNTS (31) IntTrsBoundProof [UPPER BOUND(ID), 211 ms] (32) CpxRNTS (33) IntTrsBoundProof [UPPER BOUND(ID), 73 ms] (34) CpxRNTS (35) ResultPropagationProof [UPPER BOUND(ID), 0 ms] (36) CpxRNTS (37) IntTrsBoundProof [UPPER BOUND(ID), 1316 ms] (38) CpxRNTS (39) IntTrsBoundProof [UPPER BOUND(ID), 1366 ms] (40) CpxRNTS (41) ResultPropagationProof [UPPER BOUND(ID), 0 ms] (42) CpxRNTS (43) IntTrsBoundProof [UPPER BOUND(ID), 181 ms] (44) CpxRNTS (45) IntTrsBoundProof [UPPER BOUND(ID), 75 ms] (46) CpxRNTS (47) ResultPropagationProof [UPPER BOUND(ID), 0 ms] (48) CpxRNTS (49) IntTrsBoundProof [UPPER BOUND(ID), 1038 ms] (50) CpxRNTS (51) IntTrsBoundProof [UPPER BOUND(ID), 739 ms] (52) CpxRNTS (53) FinalProof [FINISHED, 0 ms] (54) 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(g(x, y), x, z) -> f(z, z, z) g(x, y) -> x g(x, y) -> y 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(cons_f(x_1, x_2, x_3)) -> f(encArg(x_1), encArg(x_2), encArg(x_3)) encArg(cons_g(x_1, x_2)) -> g(encArg(x_1), encArg(x_2)) encode_f(x_1, x_2, x_3) -> f(encArg(x_1), encArg(x_2), encArg(x_3)) encode_g(x_1, x_2) -> g(encArg(x_1), encArg(x_2)) ---------------------------------------- (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(g(x, y), x, z) -> f(z, z, z) g(x, y) -> x g(x, y) -> y The (relative) TRS S consists of the following rules: encArg(cons_f(x_1, x_2, x_3)) -> f(encArg(x_1), encArg(x_2), encArg(x_3)) encArg(cons_g(x_1, x_2)) -> g(encArg(x_1), encArg(x_2)) encode_f(x_1, x_2, x_3) -> f(encArg(x_1), encArg(x_2), encArg(x_3)) encode_g(x_1, x_2) -> g(encArg(x_1), encArg(x_2)) 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(g(x, y), x, z) -> f(z, z, z) g(x, y) -> x g(x, y) -> y The (relative) TRS S consists of the following rules: encArg(cons_f(x_1, x_2, x_3)) -> f(encArg(x_1), encArg(x_2), encArg(x_3)) encArg(cons_g(x_1, x_2)) -> g(encArg(x_1), encArg(x_2)) encode_f(x_1, x_2, x_3) -> f(encArg(x_1), encArg(x_2), encArg(x_3)) encode_g(x_1, x_2) -> g(encArg(x_1), encArg(x_2)) Rewrite Strategy: INNERMOST ---------------------------------------- (5) NonCtorToCtorProof (UPPER BOUND(ID)) transformed non-ctor to ctor-system ---------------------------------------- (6) 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: g(x, y) -> x g(x, y) -> y f(c_g(x, y), x, z) -> f(z, z, z) The (relative) TRS S consists of the following rules: encArg(cons_f(x_1, x_2, x_3)) -> f(encArg(x_1), encArg(x_2), encArg(x_3)) encArg(cons_g(x_1, x_2)) -> g(encArg(x_1), encArg(x_2)) encode_f(x_1, x_2, x_3) -> f(encArg(x_1), encArg(x_2), encArg(x_3)) encode_g(x_1, x_2) -> g(encArg(x_1), encArg(x_2)) g(x0, x1) -> c_g(x0, x1) Rewrite Strategy: INNERMOST ---------------------------------------- (7) RelTrsToWeightedTrsProof (BOTH BOUNDS(ID, ID)) Transformed relative TRS to weighted TRS ---------------------------------------- (8) 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: g(x, y) -> x [1] g(x, y) -> y [1] f(c_g(x, y), x, z) -> f(z, z, z) [1] encArg(cons_f(x_1, x_2, x_3)) -> f(encArg(x_1), encArg(x_2), encArg(x_3)) [0] encArg(cons_g(x_1, x_2)) -> g(encArg(x_1), encArg(x_2)) [0] encode_f(x_1, x_2, x_3) -> f(encArg(x_1), encArg(x_2), encArg(x_3)) [0] encode_g(x_1, x_2) -> g(encArg(x_1), encArg(x_2)) [0] g(x0, x1) -> c_g(x0, x1) [0] Rewrite Strategy: INNERMOST ---------------------------------------- (9) TypeInferenceProof (BOTH BOUNDS(ID, ID)) Infered types. ---------------------------------------- (10) Obligation: Runtime Complexity Weighted TRS with Types. The TRS R consists of the following rules: g(x, y) -> x [1] g(x, y) -> y [1] f(c_g(x, y), x, z) -> f(z, z, z) [1] encArg(cons_f(x_1, x_2, x_3)) -> f(encArg(x_1), encArg(x_2), encArg(x_3)) [0] encArg(cons_g(x_1, x_2)) -> g(encArg(x_1), encArg(x_2)) [0] encode_f(x_1, x_2, x_3) -> f(encArg(x_1), encArg(x_2), encArg(x_3)) [0] encode_g(x_1, x_2) -> g(encArg(x_1), encArg(x_2)) [0] g(x0, x1) -> c_g(x0, x1) [0] The TRS has the following type information: g :: c_g -> c_g -> c_g f :: c_g -> c_g -> c_g -> c_g c_g :: c_g -> c_g -> c_g encArg :: cons_f:cons_g -> c_g cons_f :: cons_f:cons_g -> cons_f:cons_g -> cons_f:cons_g -> cons_f:cons_g cons_g :: cons_f:cons_g -> cons_f:cons_g -> cons_f:cons_g encode_f :: cons_f:cons_g -> cons_f:cons_g -> cons_f:cons_g -> c_g encode_g :: cons_f:cons_g -> cons_f:cons_g -> c_g Rewrite Strategy: INNERMOST ---------------------------------------- (11) 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: f_3 encArg_1 encode_f_3 encode_g_2 g_2 Due to the following rules being added: encArg(v0) -> const [0] encode_f(v0, v1, v2) -> const [0] encode_g(v0, v1) -> const [0] g(v0, v1) -> const [0] f(v0, v1, v2) -> const [0] And the following fresh constants: const, const1 ---------------------------------------- (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: g(x, y) -> x [1] g(x, y) -> y [1] f(c_g(x, y), x, z) -> f(z, z, z) [1] encArg(cons_f(x_1, x_2, x_3)) -> f(encArg(x_1), encArg(x_2), encArg(x_3)) [0] encArg(cons_g(x_1, x_2)) -> g(encArg(x_1), encArg(x_2)) [0] encode_f(x_1, x_2, x_3) -> f(encArg(x_1), encArg(x_2), encArg(x_3)) [0] encode_g(x_1, x_2) -> g(encArg(x_1), encArg(x_2)) [0] g(x0, x1) -> c_g(x0, x1) [0] encArg(v0) -> const [0] encode_f(v0, v1, v2) -> const [0] encode_g(v0, v1) -> const [0] g(v0, v1) -> const [0] f(v0, v1, v2) -> const [0] The TRS has the following type information: g :: c_g:const -> c_g:const -> c_g:const f :: c_g:const -> c_g:const -> c_g:const -> c_g:const c_g :: c_g:const -> c_g:const -> c_g:const encArg :: cons_f:cons_g -> c_g:const cons_f :: cons_f:cons_g -> cons_f:cons_g -> cons_f:cons_g -> cons_f:cons_g cons_g :: cons_f:cons_g -> cons_f:cons_g -> cons_f:cons_g encode_f :: cons_f:cons_g -> cons_f:cons_g -> cons_f:cons_g -> c_g:const encode_g :: cons_f:cons_g -> cons_f:cons_g -> c_g:const const :: c_g:const const1 :: cons_f:cons_g Rewrite Strategy: INNERMOST ---------------------------------------- (13) NarrowingProof (BOTH BOUNDS(ID, ID)) Narrowed the inner basic terms of all right-hand sides by a single narrowing step. ---------------------------------------- (14) 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: g(x, y) -> x [1] g(x, y) -> y [1] f(c_g(x, y), x, z) -> f(z, z, z) [1] encArg(cons_f(x_1, x_2, x_3)) -> f(encArg(x_1), encArg(x_2), encArg(x_3)) [0] encArg(cons_g(cons_f(x_125, x_225, x_312), cons_f(x_127, x_227, x_313))) -> g(f(encArg(x_125), encArg(x_225), encArg(x_312)), f(encArg(x_127), encArg(x_227), encArg(x_313))) [0] encArg(cons_g(cons_f(x_125, x_225, x_312), cons_g(x_128, x_228))) -> g(f(encArg(x_125), encArg(x_225), encArg(x_312)), g(encArg(x_128), encArg(x_228))) [0] encArg(cons_g(cons_f(x_125, x_225, x_312), x_2)) -> g(f(encArg(x_125), encArg(x_225), encArg(x_312)), const) [0] encArg(cons_g(cons_g(x_126, x_226), cons_f(x_129, x_229, x_314))) -> g(g(encArg(x_126), encArg(x_226)), f(encArg(x_129), encArg(x_229), encArg(x_314))) [0] encArg(cons_g(cons_g(x_126, x_226), cons_g(x_130, x_230))) -> g(g(encArg(x_126), encArg(x_226)), g(encArg(x_130), encArg(x_230))) [0] encArg(cons_g(cons_g(x_126, x_226), x_2)) -> g(g(encArg(x_126), encArg(x_226)), const) [0] encArg(cons_g(x_1, cons_f(x_131, x_231, x_315))) -> g(const, f(encArg(x_131), encArg(x_231), encArg(x_315))) [0] encArg(cons_g(x_1, cons_g(x_132, x_232))) -> g(const, g(encArg(x_132), encArg(x_232))) [0] encArg(cons_g(x_1, x_2)) -> g(const, const) [0] encode_f(x_1, x_2, x_3) -> f(encArg(x_1), encArg(x_2), encArg(x_3)) [0] encode_g(cons_f(x_159, x_259, x_329), cons_f(x_161, x_261, x_330)) -> g(f(encArg(x_159), encArg(x_259), encArg(x_329)), f(encArg(x_161), encArg(x_261), encArg(x_330))) [0] encode_g(cons_f(x_159, x_259, x_329), cons_g(x_162, x_262)) -> g(f(encArg(x_159), encArg(x_259), encArg(x_329)), g(encArg(x_162), encArg(x_262))) [0] encode_g(cons_f(x_159, x_259, x_329), x_2) -> g(f(encArg(x_159), encArg(x_259), encArg(x_329)), const) [0] encode_g(cons_g(x_160, x_260), cons_f(x_163, x_263, x_331)) -> g(g(encArg(x_160), encArg(x_260)), f(encArg(x_163), encArg(x_263), encArg(x_331))) [0] encode_g(cons_g(x_160, x_260), cons_g(x_164, x_264)) -> g(g(encArg(x_160), encArg(x_260)), g(encArg(x_164), encArg(x_264))) [0] encode_g(cons_g(x_160, x_260), x_2) -> g(g(encArg(x_160), encArg(x_260)), const) [0] encode_g(x_1, cons_f(x_165, x_265, x_332)) -> g(const, f(encArg(x_165), encArg(x_265), encArg(x_332))) [0] encode_g(x_1, cons_g(x_166, x_266)) -> g(const, g(encArg(x_166), encArg(x_266))) [0] encode_g(x_1, x_2) -> g(const, const) [0] g(x0, x1) -> c_g(x0, x1) [0] encArg(v0) -> const [0] encode_f(v0, v1, v2) -> const [0] encode_g(v0, v1) -> const [0] g(v0, v1) -> const [0] f(v0, v1, v2) -> const [0] The TRS has the following type information: g :: c_g:const -> c_g:const -> c_g:const f :: c_g:const -> c_g:const -> c_g:const -> c_g:const c_g :: c_g:const -> c_g:const -> c_g:const encArg :: cons_f:cons_g -> c_g:const cons_f :: cons_f:cons_g -> cons_f:cons_g -> cons_f:cons_g -> cons_f:cons_g cons_g :: cons_f:cons_g -> cons_f:cons_g -> cons_f:cons_g encode_f :: cons_f:cons_g -> cons_f:cons_g -> cons_f:cons_g -> c_g:const encode_g :: cons_f:cons_g -> cons_f:cons_g -> c_g:const const :: c_g:const const1 :: cons_f:cons_g Rewrite Strategy: INNERMOST ---------------------------------------- (15) 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 const1 => 0 ---------------------------------------- (16) Obligation: Complexity RNTS consisting of the following rules: encArg(z') -{ 0 }-> g(g(encArg(x_126), encArg(x_226)), g(encArg(x_130), encArg(x_230))) :|: z' = 1 + (1 + x_126 + x_226) + (1 + x_130 + x_230), x_130 >= 0, x_226 >= 0, x_126 >= 0, x_230 >= 0 encArg(z') -{ 0 }-> g(g(encArg(x_126), encArg(x_226)), f(encArg(x_129), encArg(x_229), encArg(x_314))) :|: x_226 >= 0, x_314 >= 0, x_126 >= 0, x_229 >= 0, x_129 >= 0, z' = 1 + (1 + x_126 + x_226) + (1 + x_129 + x_229 + x_314) encArg(z') -{ 0 }-> g(g(encArg(x_126), encArg(x_226)), 0) :|: x_226 >= 0, z' = 1 + (1 + x_126 + x_226) + x_2, x_126 >= 0, x_2 >= 0 encArg(z') -{ 0 }-> g(f(encArg(x_125), encArg(x_225), encArg(x_312)), g(encArg(x_128), encArg(x_228))) :|: x_128 >= 0, x_312 >= 0, z' = 1 + (1 + x_125 + x_225 + x_312) + (1 + x_128 + x_228), x_125 >= 0, x_225 >= 0, x_228 >= 0 encArg(z') -{ 0 }-> g(f(encArg(x_125), encArg(x_225), encArg(x_312)), f(encArg(x_127), encArg(x_227), encArg(x_313))) :|: x_127 >= 0, x_312 >= 0, z' = 1 + (1 + x_125 + x_225 + x_312) + (1 + x_127 + x_227 + x_313), x_125 >= 0, x_313 >= 0, x_225 >= 0, x_227 >= 0 encArg(z') -{ 0 }-> g(f(encArg(x_125), encArg(x_225), encArg(x_312)), 0) :|: x_312 >= 0, x_125 >= 0, x_225 >= 0, x_2 >= 0, z' = 1 + (1 + x_125 + x_225 + x_312) + x_2 encArg(z') -{ 0 }-> g(0, g(encArg(x_132), encArg(x_232))) :|: x_1 >= 0, z' = 1 + x_1 + (1 + x_132 + x_232), x_232 >= 0, x_132 >= 0 encArg(z') -{ 0 }-> g(0, f(encArg(x_131), encArg(x_231), encArg(x_315))) :|: x_315 >= 0, x_1 >= 0, z' = 1 + x_1 + (1 + x_131 + x_231 + x_315), x_231 >= 0, x_131 >= 0 encArg(z') -{ 0 }-> g(0, 0) :|: x_1 >= 0, x_2 >= 0, z' = 1 + x_1 + x_2 encArg(z') -{ 0 }-> f(encArg(x_1), encArg(x_2), encArg(x_3)) :|: x_1 >= 0, z' = 1 + x_1 + x_2 + x_3, x_3 >= 0, x_2 >= 0 encArg(z') -{ 0 }-> 0 :|: v0 >= 0, z' = v0 encode_f(z', z'', z1) -{ 0 }-> f(encArg(x_1), encArg(x_2), encArg(x_3)) :|: x_1 >= 0, z1 = x_3, z' = x_1, x_3 >= 0, x_2 >= 0, z'' = x_2 encode_f(z', z'', z1) -{ 0 }-> 0 :|: v0 >= 0, z1 = v2, v1 >= 0, z'' = v1, v2 >= 0, z' = v0 encode_g(z', z'') -{ 0 }-> g(g(encArg(x_160), encArg(x_260)), g(encArg(x_164), encArg(x_264))) :|: x_264 >= 0, z' = 1 + x_160 + x_260, x_160 >= 0, x_164 >= 0, z'' = 1 + x_164 + x_264, x_260 >= 0 encode_g(z', z'') -{ 0 }-> g(g(encArg(x_160), encArg(x_260)), f(encArg(x_163), encArg(x_263), encArg(x_331))) :|: x_331 >= 0, x_263 >= 0, z' = 1 + x_160 + x_260, x_160 >= 0, x_163 >= 0, z'' = 1 + x_163 + x_263 + x_331, x_260 >= 0 encode_g(z', z'') -{ 0 }-> g(g(encArg(x_160), encArg(x_260)), 0) :|: z' = 1 + x_160 + x_260, x_160 >= 0, x_2 >= 0, z'' = x_2, x_260 >= 0 encode_g(z', z'') -{ 0 }-> g(f(encArg(x_159), encArg(x_259), encArg(x_329)), g(encArg(x_162), encArg(x_262))) :|: x_159 >= 0, x_162 >= 0, x_329 >= 0, z' = 1 + x_159 + x_259 + x_329, z'' = 1 + x_162 + x_262, x_262 >= 0, x_259 >= 0 encode_g(z', z'') -{ 0 }-> g(f(encArg(x_159), encArg(x_259), encArg(x_329)), f(encArg(x_161), encArg(x_261), encArg(x_330))) :|: x_159 >= 0, x_329 >= 0, x_261 >= 0, z'' = 1 + x_161 + x_261 + x_330, z' = 1 + x_159 + x_259 + x_329, x_330 >= 0, x_259 >= 0, x_161 >= 0 encode_g(z', z'') -{ 0 }-> g(f(encArg(x_159), encArg(x_259), encArg(x_329)), 0) :|: x_159 >= 0, x_329 >= 0, z' = 1 + x_159 + x_259 + x_329, x_2 >= 0, x_259 >= 0, z'' = x_2 encode_g(z', z'') -{ 0 }-> g(0, g(encArg(x_166), encArg(x_266))) :|: x_1 >= 0, x_166 >= 0, z' = x_1, z'' = 1 + x_166 + x_266, x_266 >= 0 encode_g(z', z'') -{ 0 }-> g(0, f(encArg(x_165), encArg(x_265), encArg(x_332))) :|: x_332 >= 0, x_1 >= 0, x_265 >= 0, x_165 >= 0, z' = x_1, z'' = 1 + x_165 + x_265 + x_332 encode_g(z', z'') -{ 0 }-> g(0, 0) :|: x_1 >= 0, z' = x_1, x_2 >= 0, z'' = x_2 encode_g(z', z'') -{ 0 }-> 0 :|: v0 >= 0, v1 >= 0, z'' = v1, z' = v0 f(z', z'', z1) -{ 1 }-> f(z, z, z) :|: z1 = z, z >= 0, z' = 1 + x + y, x >= 0, y >= 0, z'' = x f(z', z'', z1) -{ 0 }-> 0 :|: v0 >= 0, z1 = v2, v1 >= 0, z'' = v1, v2 >= 0, z' = v0 g(z', z'') -{ 1 }-> x :|: z' = x, z'' = y, x >= 0, y >= 0 g(z', z'') -{ 1 }-> y :|: z' = x, z'' = y, x >= 0, y >= 0 g(z', z'') -{ 0 }-> 0 :|: v0 >= 0, v1 >= 0, z'' = v1, z' = v0 g(z', z'') -{ 0 }-> 1 + x0 + x1 :|: z'' = x1, x0 >= 0, x1 >= 0, z' = x0 ---------------------------------------- (17) InliningProof (UPPER BOUND(ID)) Inlined the following terminating rules on right-hand sides where appropriate: g(z', z'') -{ 0 }-> 1 + x0 + x1 :|: z'' = x1, x0 >= 0, x1 >= 0, z' = x0 g(z', z'') -{ 0 }-> 0 :|: v0 >= 0, v1 >= 0, z'' = v1, z' = v0 g(z', z'') -{ 1 }-> y :|: z' = x, z'' = y, x >= 0, y >= 0 g(z', z'') -{ 1 }-> x :|: z' = x, z'' = y, x >= 0, y >= 0 ---------------------------------------- (18) Obligation: Complexity RNTS consisting of the following rules: encArg(z') -{ 1 }-> x :|: x_1 >= 0, x_2 >= 0, z' = 1 + x_1 + x_2, 0 = x, 0 = y, x >= 0, y >= 0 encArg(z') -{ 1 }-> y :|: x_1 >= 0, x_2 >= 0, z' = 1 + x_1 + x_2, 0 = x, 0 = y, x >= 0, y >= 0 encArg(z') -{ 0 }-> g(g(encArg(x_126), encArg(x_226)), g(encArg(x_130), encArg(x_230))) :|: z' = 1 + (1 + x_126 + x_226) + (1 + x_130 + x_230), x_130 >= 0, x_226 >= 0, x_126 >= 0, x_230 >= 0 encArg(z') -{ 0 }-> g(g(encArg(x_126), encArg(x_226)), f(encArg(x_129), encArg(x_229), encArg(x_314))) :|: x_226 >= 0, x_314 >= 0, x_126 >= 0, x_229 >= 0, x_129 >= 0, z' = 1 + (1 + x_126 + x_226) + (1 + x_129 + x_229 + x_314) encArg(z') -{ 0 }-> g(g(encArg(x_126), encArg(x_226)), 0) :|: x_226 >= 0, z' = 1 + (1 + x_126 + x_226) + x_2, x_126 >= 0, x_2 >= 0 encArg(z') -{ 0 }-> g(f(encArg(x_125), encArg(x_225), encArg(x_312)), g(encArg(x_128), encArg(x_228))) :|: x_128 >= 0, x_312 >= 0, z' = 1 + (1 + x_125 + x_225 + x_312) + (1 + x_128 + x_228), x_125 >= 0, x_225 >= 0, x_228 >= 0 encArg(z') -{ 0 }-> g(f(encArg(x_125), encArg(x_225), encArg(x_312)), f(encArg(x_127), encArg(x_227), encArg(x_313))) :|: x_127 >= 0, x_312 >= 0, z' = 1 + (1 + x_125 + x_225 + x_312) + (1 + x_127 + x_227 + x_313), x_125 >= 0, x_313 >= 0, x_225 >= 0, x_227 >= 0 encArg(z') -{ 0 }-> g(f(encArg(x_125), encArg(x_225), encArg(x_312)), 0) :|: x_312 >= 0, x_125 >= 0, x_225 >= 0, x_2 >= 0, z' = 1 + (1 + x_125 + x_225 + x_312) + x_2 encArg(z') -{ 0 }-> g(0, g(encArg(x_132), encArg(x_232))) :|: x_1 >= 0, z' = 1 + x_1 + (1 + x_132 + x_232), x_232 >= 0, x_132 >= 0 encArg(z') -{ 0 }-> g(0, f(encArg(x_131), encArg(x_231), encArg(x_315))) :|: x_315 >= 0, x_1 >= 0, z' = 1 + x_1 + (1 + x_131 + x_231 + x_315), x_231 >= 0, x_131 >= 0 encArg(z') -{ 0 }-> f(encArg(x_1), encArg(x_2), encArg(x_3)) :|: x_1 >= 0, z' = 1 + x_1 + x_2 + x_3, x_3 >= 0, x_2 >= 0 encArg(z') -{ 0 }-> 0 :|: v0 >= 0, z' = v0 encArg(z') -{ 0 }-> 0 :|: x_1 >= 0, x_2 >= 0, z' = 1 + x_1 + x_2, v0 >= 0, v1 >= 0, 0 = v1, 0 = v0 encArg(z') -{ 0 }-> 1 + x0 + x1 :|: x_1 >= 0, x_2 >= 0, z' = 1 + x_1 + x_2, 0 = x1, x0 >= 0, x1 >= 0, 0 = x0 encode_f(z', z'', z1) -{ 0 }-> f(encArg(x_1), encArg(x_2), encArg(x_3)) :|: x_1 >= 0, z1 = x_3, z' = x_1, x_3 >= 0, x_2 >= 0, z'' = x_2 encode_f(z', z'', z1) -{ 0 }-> 0 :|: v0 >= 0, z1 = v2, v1 >= 0, z'' = v1, v2 >= 0, z' = v0 encode_g(z', z'') -{ 1 }-> x :|: x_1 >= 0, z' = x_1, x_2 >= 0, z'' = x_2, 0 = x, 0 = y, x >= 0, y >= 0 encode_g(z', z'') -{ 1 }-> y :|: x_1 >= 0, z' = x_1, x_2 >= 0, z'' = x_2, 0 = x, 0 = y, x >= 0, y >= 0 encode_g(z', z'') -{ 0 }-> g(g(encArg(x_160), encArg(x_260)), g(encArg(x_164), encArg(x_264))) :|: x_264 >= 0, z' = 1 + x_160 + x_260, x_160 >= 0, x_164 >= 0, z'' = 1 + x_164 + x_264, x_260 >= 0 encode_g(z', z'') -{ 0 }-> g(g(encArg(x_160), encArg(x_260)), f(encArg(x_163), encArg(x_263), encArg(x_331))) :|: x_331 >= 0, x_263 >= 0, z' = 1 + x_160 + x_260, x_160 >= 0, x_163 >= 0, z'' = 1 + x_163 + x_263 + x_331, x_260 >= 0 encode_g(z', z'') -{ 0 }-> g(g(encArg(x_160), encArg(x_260)), 0) :|: z' = 1 + x_160 + x_260, x_160 >= 0, x_2 >= 0, z'' = x_2, x_260 >= 0 encode_g(z', z'') -{ 0 }-> g(f(encArg(x_159), encArg(x_259), encArg(x_329)), g(encArg(x_162), encArg(x_262))) :|: x_159 >= 0, x_162 >= 0, x_329 >= 0, z' = 1 + x_159 + x_259 + x_329, z'' = 1 + x_162 + x_262, x_262 >= 0, x_259 >= 0 encode_g(z', z'') -{ 0 }-> g(f(encArg(x_159), encArg(x_259), encArg(x_329)), f(encArg(x_161), encArg(x_261), encArg(x_330))) :|: x_159 >= 0, x_329 >= 0, x_261 >= 0, z'' = 1 + x_161 + x_261 + x_330, z' = 1 + x_159 + x_259 + x_329, x_330 >= 0, x_259 >= 0, x_161 >= 0 encode_g(z', z'') -{ 0 }-> g(f(encArg(x_159), encArg(x_259), encArg(x_329)), 0) :|: x_159 >= 0, x_329 >= 0, z' = 1 + x_159 + x_259 + x_329, x_2 >= 0, x_259 >= 0, z'' = x_2 encode_g(z', z'') -{ 0 }-> g(0, g(encArg(x_166), encArg(x_266))) :|: x_1 >= 0, x_166 >= 0, z' = x_1, z'' = 1 + x_166 + x_266, x_266 >= 0 encode_g(z', z'') -{ 0 }-> g(0, f(encArg(x_165), encArg(x_265), encArg(x_332))) :|: x_332 >= 0, x_1 >= 0, x_265 >= 0, x_165 >= 0, z' = x_1, z'' = 1 + x_165 + x_265 + x_332 encode_g(z', z'') -{ 0 }-> 0 :|: v0 >= 0, v1 >= 0, z'' = v1, z' = v0 encode_g(z', z'') -{ 0 }-> 0 :|: x_1 >= 0, z' = x_1, x_2 >= 0, z'' = x_2, v0 >= 0, v1 >= 0, 0 = v1, 0 = v0 encode_g(z', z'') -{ 0 }-> 1 + x0 + x1 :|: x_1 >= 0, z' = x_1, x_2 >= 0, z'' = x_2, 0 = x1, x0 >= 0, x1 >= 0, 0 = x0 f(z', z'', z1) -{ 1 }-> f(z, z, z) :|: z1 = z, z >= 0, z' = 1 + x + y, x >= 0, y >= 0, z'' = x f(z', z'', z1) -{ 0 }-> 0 :|: v0 >= 0, z1 = v2, v1 >= 0, z'' = v1, v2 >= 0, z' = v0 g(z', z'') -{ 1 }-> x :|: z' = x, z'' = y, x >= 0, y >= 0 g(z', z'') -{ 1 }-> y :|: z' = x, z'' = y, x >= 0, y >= 0 g(z', z'') -{ 0 }-> 0 :|: v0 >= 0, v1 >= 0, z'' = v1, z' = v0 g(z', z'') -{ 0 }-> 1 + x0 + x1 :|: z'' = x1, x0 >= 0, x1 >= 0, z' = x0 ---------------------------------------- (19) SimplificationProof (BOTH BOUNDS(ID, ID)) Simplified the RNTS by moving equalities from the constraints into the right-hand sides. ---------------------------------------- (20) Obligation: Complexity RNTS consisting of the following rules: encArg(z') -{ 1 }-> x :|: x_1 >= 0, x_2 >= 0, z' = 1 + x_1 + x_2, 0 = x, 0 = y, x >= 0, y >= 0 encArg(z') -{ 1 }-> y :|: x_1 >= 0, x_2 >= 0, z' = 1 + x_1 + x_2, 0 = x, 0 = y, x >= 0, y >= 0 encArg(z') -{ 0 }-> g(g(encArg(x_126), encArg(x_226)), g(encArg(x_130), encArg(x_230))) :|: z' = 1 + (1 + x_126 + x_226) + (1 + x_130 + x_230), x_130 >= 0, x_226 >= 0, x_126 >= 0, x_230 >= 0 encArg(z') -{ 0 }-> g(g(encArg(x_126), encArg(x_226)), f(encArg(x_129), encArg(x_229), encArg(x_314))) :|: x_226 >= 0, x_314 >= 0, x_126 >= 0, x_229 >= 0, x_129 >= 0, z' = 1 + (1 + x_126 + x_226) + (1 + x_129 + x_229 + x_314) encArg(z') -{ 0 }-> g(g(encArg(x_126), encArg(x_226)), 0) :|: x_226 >= 0, z' = 1 + (1 + x_126 + x_226) + x_2, x_126 >= 0, x_2 >= 0 encArg(z') -{ 0 }-> g(f(encArg(x_125), encArg(x_225), encArg(x_312)), g(encArg(x_128), encArg(x_228))) :|: x_128 >= 0, x_312 >= 0, z' = 1 + (1 + x_125 + x_225 + x_312) + (1 + x_128 + x_228), x_125 >= 0, x_225 >= 0, x_228 >= 0 encArg(z') -{ 0 }-> g(f(encArg(x_125), encArg(x_225), encArg(x_312)), f(encArg(x_127), encArg(x_227), encArg(x_313))) :|: x_127 >= 0, x_312 >= 0, z' = 1 + (1 + x_125 + x_225 + x_312) + (1 + x_127 + x_227 + x_313), x_125 >= 0, x_313 >= 0, x_225 >= 0, x_227 >= 0 encArg(z') -{ 0 }-> g(f(encArg(x_125), encArg(x_225), encArg(x_312)), 0) :|: x_312 >= 0, x_125 >= 0, x_225 >= 0, x_2 >= 0, z' = 1 + (1 + x_125 + x_225 + x_312) + x_2 encArg(z') -{ 0 }-> g(0, g(encArg(x_132), encArg(x_232))) :|: x_1 >= 0, z' = 1 + x_1 + (1 + x_132 + x_232), x_232 >= 0, x_132 >= 0 encArg(z') -{ 0 }-> g(0, f(encArg(x_131), encArg(x_231), encArg(x_315))) :|: x_315 >= 0, x_1 >= 0, z' = 1 + x_1 + (1 + x_131 + x_231 + x_315), x_231 >= 0, x_131 >= 0 encArg(z') -{ 0 }-> f(encArg(x_1), encArg(x_2), encArg(x_3)) :|: x_1 >= 0, z' = 1 + x_1 + x_2 + x_3, x_3 >= 0, x_2 >= 0 encArg(z') -{ 0 }-> 0 :|: z' >= 0 encArg(z') -{ 0 }-> 0 :|: x_1 >= 0, x_2 >= 0, z' = 1 + x_1 + x_2, v0 >= 0, v1 >= 0, 0 = v1, 0 = v0 encArg(z') -{ 0 }-> 1 + x0 + x1 :|: x_1 >= 0, x_2 >= 0, z' = 1 + x_1 + x_2, 0 = x1, x0 >= 0, x1 >= 0, 0 = x0 encode_f(z', z'', z1) -{ 0 }-> f(encArg(z'), encArg(z''), encArg(z1)) :|: z' >= 0, z1 >= 0, z'' >= 0 encode_f(z', z'', z1) -{ 0 }-> 0 :|: z' >= 0, z'' >= 0, z1 >= 0 encode_g(z', z'') -{ 1 }-> x :|: z' >= 0, z'' >= 0, 0 = x, 0 = y, x >= 0, y >= 0 encode_g(z', z'') -{ 1 }-> y :|: z' >= 0, z'' >= 0, 0 = x, 0 = y, x >= 0, y >= 0 encode_g(z', z'') -{ 0 }-> g(g(encArg(x_160), encArg(x_260)), g(encArg(x_164), encArg(x_264))) :|: x_264 >= 0, z' = 1 + x_160 + x_260, x_160 >= 0, x_164 >= 0, z'' = 1 + x_164 + x_264, x_260 >= 0 encode_g(z', z'') -{ 0 }-> g(g(encArg(x_160), encArg(x_260)), f(encArg(x_163), encArg(x_263), encArg(x_331))) :|: x_331 >= 0, x_263 >= 0, z' = 1 + x_160 + x_260, x_160 >= 0, x_163 >= 0, z'' = 1 + x_163 + x_263 + x_331, x_260 >= 0 encode_g(z', z'') -{ 0 }-> g(g(encArg(x_160), encArg(x_260)), 0) :|: z' = 1 + x_160 + x_260, x_160 >= 0, z'' >= 0, x_260 >= 0 encode_g(z', z'') -{ 0 }-> g(f(encArg(x_159), encArg(x_259), encArg(x_329)), g(encArg(x_162), encArg(x_262))) :|: x_159 >= 0, x_162 >= 0, x_329 >= 0, z' = 1 + x_159 + x_259 + x_329, z'' = 1 + x_162 + x_262, x_262 >= 0, x_259 >= 0 encode_g(z', z'') -{ 0 }-> g(f(encArg(x_159), encArg(x_259), encArg(x_329)), f(encArg(x_161), encArg(x_261), encArg(x_330))) :|: x_159 >= 0, x_329 >= 0, x_261 >= 0, z'' = 1 + x_161 + x_261 + x_330, z' = 1 + x_159 + x_259 + x_329, x_330 >= 0, x_259 >= 0, x_161 >= 0 encode_g(z', z'') -{ 0 }-> g(f(encArg(x_159), encArg(x_259), encArg(x_329)), 0) :|: x_159 >= 0, x_329 >= 0, z' = 1 + x_159 + x_259 + x_329, z'' >= 0, x_259 >= 0 encode_g(z', z'') -{ 0 }-> g(0, g(encArg(x_166), encArg(x_266))) :|: z' >= 0, x_166 >= 0, z'' = 1 + x_166 + x_266, x_266 >= 0 encode_g(z', z'') -{ 0 }-> g(0, f(encArg(x_165), encArg(x_265), encArg(x_332))) :|: x_332 >= 0, z' >= 0, x_265 >= 0, x_165 >= 0, z'' = 1 + x_165 + x_265 + x_332 encode_g(z', z'') -{ 0 }-> 0 :|: z' >= 0, z'' >= 0 encode_g(z', z'') -{ 0 }-> 0 :|: z' >= 0, z'' >= 0, v0 >= 0, v1 >= 0, 0 = v1, 0 = v0 encode_g(z', z'') -{ 0 }-> 1 + x0 + x1 :|: z' >= 0, z'' >= 0, 0 = x1, x0 >= 0, x1 >= 0, 0 = x0 f(z', z'', z1) -{ 1 }-> f(z1, z1, z1) :|: z1 >= 0, z' = 1 + z'' + y, z'' >= 0, y >= 0 f(z', z'', z1) -{ 0 }-> 0 :|: z' >= 0, z'' >= 0, z1 >= 0 g(z', z'') -{ 1 }-> z' :|: z' >= 0, z'' >= 0 g(z', z'') -{ 1 }-> z'' :|: z' >= 0, z'' >= 0 g(z', z'') -{ 0 }-> 0 :|: z' >= 0, z'' >= 0 g(z', z'') -{ 0 }-> 1 + z' + z'' :|: z' >= 0, z'' >= 0 ---------------------------------------- (21) CpxRntsAnalysisOrderProof (BOTH BOUNDS(ID, ID)) Found the following analysis order by SCC decomposition: { g } { f } { encArg } { encode_f } { encode_g } ---------------------------------------- (22) Obligation: Complexity RNTS consisting of the following rules: encArg(z') -{ 1 }-> x :|: x_1 >= 0, x_2 >= 0, z' = 1 + x_1 + x_2, 0 = x, 0 = y, x >= 0, y >= 0 encArg(z') -{ 1 }-> y :|: x_1 >= 0, x_2 >= 0, z' = 1 + x_1 + x_2, 0 = x, 0 = y, x >= 0, y >= 0 encArg(z') -{ 0 }-> g(g(encArg(x_126), encArg(x_226)), g(encArg(x_130), encArg(x_230))) :|: z' = 1 + (1 + x_126 + x_226) + (1 + x_130 + x_230), x_130 >= 0, x_226 >= 0, x_126 >= 0, x_230 >= 0 encArg(z') -{ 0 }-> g(g(encArg(x_126), encArg(x_226)), f(encArg(x_129), encArg(x_229), encArg(x_314))) :|: x_226 >= 0, x_314 >= 0, x_126 >= 0, x_229 >= 0, x_129 >= 0, z' = 1 + (1 + x_126 + x_226) + (1 + x_129 + x_229 + x_314) encArg(z') -{ 0 }-> g(g(encArg(x_126), encArg(x_226)), 0) :|: x_226 >= 0, z' = 1 + (1 + x_126 + x_226) + x_2, x_126 >= 0, x_2 >= 0 encArg(z') -{ 0 }-> g(f(encArg(x_125), encArg(x_225), encArg(x_312)), g(encArg(x_128), encArg(x_228))) :|: x_128 >= 0, x_312 >= 0, z' = 1 + (1 + x_125 + x_225 + x_312) + (1 + x_128 + x_228), x_125 >= 0, x_225 >= 0, x_228 >= 0 encArg(z') -{ 0 }-> g(f(encArg(x_125), encArg(x_225), encArg(x_312)), f(encArg(x_127), encArg(x_227), encArg(x_313))) :|: x_127 >= 0, x_312 >= 0, z' = 1 + (1 + x_125 + x_225 + x_312) + (1 + x_127 + x_227 + x_313), x_125 >= 0, x_313 >= 0, x_225 >= 0, x_227 >= 0 encArg(z') -{ 0 }-> g(f(encArg(x_125), encArg(x_225), encArg(x_312)), 0) :|: x_312 >= 0, x_125 >= 0, x_225 >= 0, x_2 >= 0, z' = 1 + (1 + x_125 + x_225 + x_312) + x_2 encArg(z') -{ 0 }-> g(0, g(encArg(x_132), encArg(x_232))) :|: x_1 >= 0, z' = 1 + x_1 + (1 + x_132 + x_232), x_232 >= 0, x_132 >= 0 encArg(z') -{ 0 }-> g(0, f(encArg(x_131), encArg(x_231), encArg(x_315))) :|: x_315 >= 0, x_1 >= 0, z' = 1 + x_1 + (1 + x_131 + x_231 + x_315), x_231 >= 0, x_131 >= 0 encArg(z') -{ 0 }-> f(encArg(x_1), encArg(x_2), encArg(x_3)) :|: x_1 >= 0, z' = 1 + x_1 + x_2 + x_3, x_3 >= 0, x_2 >= 0 encArg(z') -{ 0 }-> 0 :|: z' >= 0 encArg(z') -{ 0 }-> 0 :|: x_1 >= 0, x_2 >= 0, z' = 1 + x_1 + x_2, v0 >= 0, v1 >= 0, 0 = v1, 0 = v0 encArg(z') -{ 0 }-> 1 + x0 + x1 :|: x_1 >= 0, x_2 >= 0, z' = 1 + x_1 + x_2, 0 = x1, x0 >= 0, x1 >= 0, 0 = x0 encode_f(z', z'', z1) -{ 0 }-> f(encArg(z'), encArg(z''), encArg(z1)) :|: z' >= 0, z1 >= 0, z'' >= 0 encode_f(z', z'', z1) -{ 0 }-> 0 :|: z' >= 0, z'' >= 0, z1 >= 0 encode_g(z', z'') -{ 1 }-> x :|: z' >= 0, z'' >= 0, 0 = x, 0 = y, x >= 0, y >= 0 encode_g(z', z'') -{ 1 }-> y :|: z' >= 0, z'' >= 0, 0 = x, 0 = y, x >= 0, y >= 0 encode_g(z', z'') -{ 0 }-> g(g(encArg(x_160), encArg(x_260)), g(encArg(x_164), encArg(x_264))) :|: x_264 >= 0, z' = 1 + x_160 + x_260, x_160 >= 0, x_164 >= 0, z'' = 1 + x_164 + x_264, x_260 >= 0 encode_g(z', z'') -{ 0 }-> g(g(encArg(x_160), encArg(x_260)), f(encArg(x_163), encArg(x_263), encArg(x_331))) :|: x_331 >= 0, x_263 >= 0, z' = 1 + x_160 + x_260, x_160 >= 0, x_163 >= 0, z'' = 1 + x_163 + x_263 + x_331, x_260 >= 0 encode_g(z', z'') -{ 0 }-> g(g(encArg(x_160), encArg(x_260)), 0) :|: z' = 1 + x_160 + x_260, x_160 >= 0, z'' >= 0, x_260 >= 0 encode_g(z', z'') -{ 0 }-> g(f(encArg(x_159), encArg(x_259), encArg(x_329)), g(encArg(x_162), encArg(x_262))) :|: x_159 >= 0, x_162 >= 0, x_329 >= 0, z' = 1 + x_159 + x_259 + x_329, z'' = 1 + x_162 + x_262, x_262 >= 0, x_259 >= 0 encode_g(z', z'') -{ 0 }-> g(f(encArg(x_159), encArg(x_259), encArg(x_329)), f(encArg(x_161), encArg(x_261), encArg(x_330))) :|: x_159 >= 0, x_329 >= 0, x_261 >= 0, z'' = 1 + x_161 + x_261 + x_330, z' = 1 + x_159 + x_259 + x_329, x_330 >= 0, x_259 >= 0, x_161 >= 0 encode_g(z', z'') -{ 0 }-> g(f(encArg(x_159), encArg(x_259), encArg(x_329)), 0) :|: x_159 >= 0, x_329 >= 0, z' = 1 + x_159 + x_259 + x_329, z'' >= 0, x_259 >= 0 encode_g(z', z'') -{ 0 }-> g(0, g(encArg(x_166), encArg(x_266))) :|: z' >= 0, x_166 >= 0, z'' = 1 + x_166 + x_266, x_266 >= 0 encode_g(z', z'') -{ 0 }-> g(0, f(encArg(x_165), encArg(x_265), encArg(x_332))) :|: x_332 >= 0, z' >= 0, x_265 >= 0, x_165 >= 0, z'' = 1 + x_165 + x_265 + x_332 encode_g(z', z'') -{ 0 }-> 0 :|: z' >= 0, z'' >= 0 encode_g(z', z'') -{ 0 }-> 0 :|: z' >= 0, z'' >= 0, v0 >= 0, v1 >= 0, 0 = v1, 0 = v0 encode_g(z', z'') -{ 0 }-> 1 + x0 + x1 :|: z' >= 0, z'' >= 0, 0 = x1, x0 >= 0, x1 >= 0, 0 = x0 f(z', z'', z1) -{ 1 }-> f(z1, z1, z1) :|: z1 >= 0, z' = 1 + z'' + y, z'' >= 0, y >= 0 f(z', z'', z1) -{ 0 }-> 0 :|: z' >= 0, z'' >= 0, z1 >= 0 g(z', z'') -{ 1 }-> z' :|: z' >= 0, z'' >= 0 g(z', z'') -{ 1 }-> z'' :|: z' >= 0, z'' >= 0 g(z', z'') -{ 0 }-> 0 :|: z' >= 0, z'' >= 0 g(z', z'') -{ 0 }-> 1 + z' + z'' :|: z' >= 0, z'' >= 0 Function symbols to be analyzed: {g}, {f}, {encArg}, {encode_f}, {encode_g} ---------------------------------------- (23) ResultPropagationProof (UPPER BOUND(ID)) Applied inner abstraction using the recently inferred runtime/size bounds where possible. ---------------------------------------- (24) Obligation: Complexity RNTS consisting of the following rules: encArg(z') -{ 1 }-> x :|: x_1 >= 0, x_2 >= 0, z' = 1 + x_1 + x_2, 0 = x, 0 = y, x >= 0, y >= 0 encArg(z') -{ 1 }-> y :|: x_1 >= 0, x_2 >= 0, z' = 1 + x_1 + x_2, 0 = x, 0 = y, x >= 0, y >= 0 encArg(z') -{ 0 }-> g(g(encArg(x_126), encArg(x_226)), g(encArg(x_130), encArg(x_230))) :|: z' = 1 + (1 + x_126 + x_226) + (1 + x_130 + x_230), x_130 >= 0, x_226 >= 0, x_126 >= 0, x_230 >= 0 encArg(z') -{ 0 }-> g(g(encArg(x_126), encArg(x_226)), f(encArg(x_129), encArg(x_229), encArg(x_314))) :|: x_226 >= 0, x_314 >= 0, x_126 >= 0, x_229 >= 0, x_129 >= 0, z' = 1 + (1 + x_126 + x_226) + (1 + x_129 + x_229 + x_314) encArg(z') -{ 0 }-> g(g(encArg(x_126), encArg(x_226)), 0) :|: x_226 >= 0, z' = 1 + (1 + x_126 + x_226) + x_2, x_126 >= 0, x_2 >= 0 encArg(z') -{ 0 }-> g(f(encArg(x_125), encArg(x_225), encArg(x_312)), g(encArg(x_128), encArg(x_228))) :|: x_128 >= 0, x_312 >= 0, z' = 1 + (1 + x_125 + x_225 + x_312) + (1 + x_128 + x_228), x_125 >= 0, x_225 >= 0, x_228 >= 0 encArg(z') -{ 0 }-> g(f(encArg(x_125), encArg(x_225), encArg(x_312)), f(encArg(x_127), encArg(x_227), encArg(x_313))) :|: x_127 >= 0, x_312 >= 0, z' = 1 + (1 + x_125 + x_225 + x_312) + (1 + x_127 + x_227 + x_313), x_125 >= 0, x_313 >= 0, x_225 >= 0, x_227 >= 0 encArg(z') -{ 0 }-> g(f(encArg(x_125), encArg(x_225), encArg(x_312)), 0) :|: x_312 >= 0, x_125 >= 0, x_225 >= 0, x_2 >= 0, z' = 1 + (1 + x_125 + x_225 + x_312) + x_2 encArg(z') -{ 0 }-> g(0, g(encArg(x_132), encArg(x_232))) :|: x_1 >= 0, z' = 1 + x_1 + (1 + x_132 + x_232), x_232 >= 0, x_132 >= 0 encArg(z') -{ 0 }-> g(0, f(encArg(x_131), encArg(x_231), encArg(x_315))) :|: x_315 >= 0, x_1 >= 0, z' = 1 + x_1 + (1 + x_131 + x_231 + x_315), x_231 >= 0, x_131 >= 0 encArg(z') -{ 0 }-> f(encArg(x_1), encArg(x_2), encArg(x_3)) :|: x_1 >= 0, z' = 1 + x_1 + x_2 + x_3, x_3 >= 0, x_2 >= 0 encArg(z') -{ 0 }-> 0 :|: z' >= 0 encArg(z') -{ 0 }-> 0 :|: x_1 >= 0, x_2 >= 0, z' = 1 + x_1 + x_2, v0 >= 0, v1 >= 0, 0 = v1, 0 = v0 encArg(z') -{ 0 }-> 1 + x0 + x1 :|: x_1 >= 0, x_2 >= 0, z' = 1 + x_1 + x_2, 0 = x1, x0 >= 0, x1 >= 0, 0 = x0 encode_f(z', z'', z1) -{ 0 }-> f(encArg(z'), encArg(z''), encArg(z1)) :|: z' >= 0, z1 >= 0, z'' >= 0 encode_f(z', z'', z1) -{ 0 }-> 0 :|: z' >= 0, z'' >= 0, z1 >= 0 encode_g(z', z'') -{ 1 }-> x :|: z' >= 0, z'' >= 0, 0 = x, 0 = y, x >= 0, y >= 0 encode_g(z', z'') -{ 1 }-> y :|: z' >= 0, z'' >= 0, 0 = x, 0 = y, x >= 0, y >= 0 encode_g(z', z'') -{ 0 }-> g(g(encArg(x_160), encArg(x_260)), g(encArg(x_164), encArg(x_264))) :|: x_264 >= 0, z' = 1 + x_160 + x_260, x_160 >= 0, x_164 >= 0, z'' = 1 + x_164 + x_264, x_260 >= 0 encode_g(z', z'') -{ 0 }-> g(g(encArg(x_160), encArg(x_260)), f(encArg(x_163), encArg(x_263), encArg(x_331))) :|: x_331 >= 0, x_263 >= 0, z' = 1 + x_160 + x_260, x_160 >= 0, x_163 >= 0, z'' = 1 + x_163 + x_263 + x_331, x_260 >= 0 encode_g(z', z'') -{ 0 }-> g(g(encArg(x_160), encArg(x_260)), 0) :|: z' = 1 + x_160 + x_260, x_160 >= 0, z'' >= 0, x_260 >= 0 encode_g(z', z'') -{ 0 }-> g(f(encArg(x_159), encArg(x_259), encArg(x_329)), g(encArg(x_162), encArg(x_262))) :|: x_159 >= 0, x_162 >= 0, x_329 >= 0, z' = 1 + x_159 + x_259 + x_329, z'' = 1 + x_162 + x_262, x_262 >= 0, x_259 >= 0 encode_g(z', z'') -{ 0 }-> g(f(encArg(x_159), encArg(x_259), encArg(x_329)), f(encArg(x_161), encArg(x_261), encArg(x_330))) :|: x_159 >= 0, x_329 >= 0, x_261 >= 0, z'' = 1 + x_161 + x_261 + x_330, z' = 1 + x_159 + x_259 + x_329, x_330 >= 0, x_259 >= 0, x_161 >= 0 encode_g(z', z'') -{ 0 }-> g(f(encArg(x_159), encArg(x_259), encArg(x_329)), 0) :|: x_159 >= 0, x_329 >= 0, z' = 1 + x_159 + x_259 + x_329, z'' >= 0, x_259 >= 0 encode_g(z', z'') -{ 0 }-> g(0, g(encArg(x_166), encArg(x_266))) :|: z' >= 0, x_166 >= 0, z'' = 1 + x_166 + x_266, x_266 >= 0 encode_g(z', z'') -{ 0 }-> g(0, f(encArg(x_165), encArg(x_265), encArg(x_332))) :|: x_332 >= 0, z' >= 0, x_265 >= 0, x_165 >= 0, z'' = 1 + x_165 + x_265 + x_332 encode_g(z', z'') -{ 0 }-> 0 :|: z' >= 0, z'' >= 0 encode_g(z', z'') -{ 0 }-> 0 :|: z' >= 0, z'' >= 0, v0 >= 0, v1 >= 0, 0 = v1, 0 = v0 encode_g(z', z'') -{ 0 }-> 1 + x0 + x1 :|: z' >= 0, z'' >= 0, 0 = x1, x0 >= 0, x1 >= 0, 0 = x0 f(z', z'', z1) -{ 1 }-> f(z1, z1, z1) :|: z1 >= 0, z' = 1 + z'' + y, z'' >= 0, y >= 0 f(z', z'', z1) -{ 0 }-> 0 :|: z' >= 0, z'' >= 0, z1 >= 0 g(z', z'') -{ 1 }-> z' :|: z' >= 0, z'' >= 0 g(z', z'') -{ 1 }-> z'' :|: z' >= 0, z'' >= 0 g(z', z'') -{ 0 }-> 0 :|: z' >= 0, z'' >= 0 g(z', z'') -{ 0 }-> 1 + z' + z'' :|: z' >= 0, z'' >= 0 Function symbols to be analyzed: {g}, {f}, {encArg}, {encode_f}, {encode_g} ---------------------------------------- (25) 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' + z'' ---------------------------------------- (26) Obligation: Complexity RNTS consisting of the following rules: encArg(z') -{ 1 }-> x :|: x_1 >= 0, x_2 >= 0, z' = 1 + x_1 + x_2, 0 = x, 0 = y, x >= 0, y >= 0 encArg(z') -{ 1 }-> y :|: x_1 >= 0, x_2 >= 0, z' = 1 + x_1 + x_2, 0 = x, 0 = y, x >= 0, y >= 0 encArg(z') -{ 0 }-> g(g(encArg(x_126), encArg(x_226)), g(encArg(x_130), encArg(x_230))) :|: z' = 1 + (1 + x_126 + x_226) + (1 + x_130 + x_230), x_130 >= 0, x_226 >= 0, x_126 >= 0, x_230 >= 0 encArg(z') -{ 0 }-> g(g(encArg(x_126), encArg(x_226)), f(encArg(x_129), encArg(x_229), encArg(x_314))) :|: x_226 >= 0, x_314 >= 0, x_126 >= 0, x_229 >= 0, x_129 >= 0, z' = 1 + (1 + x_126 + x_226) + (1 + x_129 + x_229 + x_314) encArg(z') -{ 0 }-> g(g(encArg(x_126), encArg(x_226)), 0) :|: x_226 >= 0, z' = 1 + (1 + x_126 + x_226) + x_2, x_126 >= 0, x_2 >= 0 encArg(z') -{ 0 }-> g(f(encArg(x_125), encArg(x_225), encArg(x_312)), g(encArg(x_128), encArg(x_228))) :|: x_128 >= 0, x_312 >= 0, z' = 1 + (1 + x_125 + x_225 + x_312) + (1 + x_128 + x_228), x_125 >= 0, x_225 >= 0, x_228 >= 0 encArg(z') -{ 0 }-> g(f(encArg(x_125), encArg(x_225), encArg(x_312)), f(encArg(x_127), encArg(x_227), encArg(x_313))) :|: x_127 >= 0, x_312 >= 0, z' = 1 + (1 + x_125 + x_225 + x_312) + (1 + x_127 + x_227 + x_313), x_125 >= 0, x_313 >= 0, x_225 >= 0, x_227 >= 0 encArg(z') -{ 0 }-> g(f(encArg(x_125), encArg(x_225), encArg(x_312)), 0) :|: x_312 >= 0, x_125 >= 0, x_225 >= 0, x_2 >= 0, z' = 1 + (1 + x_125 + x_225 + x_312) + x_2 encArg(z') -{ 0 }-> g(0, g(encArg(x_132), encArg(x_232))) :|: x_1 >= 0, z' = 1 + x_1 + (1 + x_132 + x_232), x_232 >= 0, x_132 >= 0 encArg(z') -{ 0 }-> g(0, f(encArg(x_131), encArg(x_231), encArg(x_315))) :|: x_315 >= 0, x_1 >= 0, z' = 1 + x_1 + (1 + x_131 + x_231 + x_315), x_231 >= 0, x_131 >= 0 encArg(z') -{ 0 }-> f(encArg(x_1), encArg(x_2), encArg(x_3)) :|: x_1 >= 0, z' = 1 + x_1 + x_2 + x_3, x_3 >= 0, x_2 >= 0 encArg(z') -{ 0 }-> 0 :|: z' >= 0 encArg(z') -{ 0 }-> 0 :|: x_1 >= 0, x_2 >= 0, z' = 1 + x_1 + x_2, v0 >= 0, v1 >= 0, 0 = v1, 0 = v0 encArg(z') -{ 0 }-> 1 + x0 + x1 :|: x_1 >= 0, x_2 >= 0, z' = 1 + x_1 + x_2, 0 = x1, x0 >= 0, x1 >= 0, 0 = x0 encode_f(z', z'', z1) -{ 0 }-> f(encArg(z'), encArg(z''), encArg(z1)) :|: z' >= 0, z1 >= 0, z'' >= 0 encode_f(z', z'', z1) -{ 0 }-> 0 :|: z' >= 0, z'' >= 0, z1 >= 0 encode_g(z', z'') -{ 1 }-> x :|: z' >= 0, z'' >= 0, 0 = x, 0 = y, x >= 0, y >= 0 encode_g(z', z'') -{ 1 }-> y :|: z' >= 0, z'' >= 0, 0 = x, 0 = y, x >= 0, y >= 0 encode_g(z', z'') -{ 0 }-> g(g(encArg(x_160), encArg(x_260)), g(encArg(x_164), encArg(x_264))) :|: x_264 >= 0, z' = 1 + x_160 + x_260, x_160 >= 0, x_164 >= 0, z'' = 1 + x_164 + x_264, x_260 >= 0 encode_g(z', z'') -{ 0 }-> g(g(encArg(x_160), encArg(x_260)), f(encArg(x_163), encArg(x_263), encArg(x_331))) :|: x_331 >= 0, x_263 >= 0, z' = 1 + x_160 + x_260, x_160 >= 0, x_163 >= 0, z'' = 1 + x_163 + x_263 + x_331, x_260 >= 0 encode_g(z', z'') -{ 0 }-> g(g(encArg(x_160), encArg(x_260)), 0) :|: z' = 1 + x_160 + x_260, x_160 >= 0, z'' >= 0, x_260 >= 0 encode_g(z', z'') -{ 0 }-> g(f(encArg(x_159), encArg(x_259), encArg(x_329)), g(encArg(x_162), encArg(x_262))) :|: x_159 >= 0, x_162 >= 0, x_329 >= 0, z' = 1 + x_159 + x_259 + x_329, z'' = 1 + x_162 + x_262, x_262 >= 0, x_259 >= 0 encode_g(z', z'') -{ 0 }-> g(f(encArg(x_159), encArg(x_259), encArg(x_329)), f(encArg(x_161), encArg(x_261), encArg(x_330))) :|: x_159 >= 0, x_329 >= 0, x_261 >= 0, z'' = 1 + x_161 + x_261 + x_330, z' = 1 + x_159 + x_259 + x_329, x_330 >= 0, x_259 >= 0, x_161 >= 0 encode_g(z', z'') -{ 0 }-> g(f(encArg(x_159), encArg(x_259), encArg(x_329)), 0) :|: x_159 >= 0, x_329 >= 0, z' = 1 + x_159 + x_259 + x_329, z'' >= 0, x_259 >= 0 encode_g(z', z'') -{ 0 }-> g(0, g(encArg(x_166), encArg(x_266))) :|: z' >= 0, x_166 >= 0, z'' = 1 + x_166 + x_266, x_266 >= 0 encode_g(z', z'') -{ 0 }-> g(0, f(encArg(x_165), encArg(x_265), encArg(x_332))) :|: x_332 >= 0, z' >= 0, x_265 >= 0, x_165 >= 0, z'' = 1 + x_165 + x_265 + x_332 encode_g(z', z'') -{ 0 }-> 0 :|: z' >= 0, z'' >= 0 encode_g(z', z'') -{ 0 }-> 0 :|: z' >= 0, z'' >= 0, v0 >= 0, v1 >= 0, 0 = v1, 0 = v0 encode_g(z', z'') -{ 0 }-> 1 + x0 + x1 :|: z' >= 0, z'' >= 0, 0 = x1, x0 >= 0, x1 >= 0, 0 = x0 f(z', z'', z1) -{ 1 }-> f(z1, z1, z1) :|: z1 >= 0, z' = 1 + z'' + y, z'' >= 0, y >= 0 f(z', z'', z1) -{ 0 }-> 0 :|: z' >= 0, z'' >= 0, z1 >= 0 g(z', z'') -{ 1 }-> z' :|: z' >= 0, z'' >= 0 g(z', z'') -{ 1 }-> z'' :|: z' >= 0, z'' >= 0 g(z', z'') -{ 0 }-> 0 :|: z' >= 0, z'' >= 0 g(z', z'') -{ 0 }-> 1 + z' + z'' :|: z' >= 0, z'' >= 0 Function symbols to be analyzed: {g}, {f}, {encArg}, {encode_f}, {encode_g} Previous analysis results are: g: runtime: ?, size: O(n^1) [1 + z' + z''] ---------------------------------------- (27) 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 ---------------------------------------- (28) Obligation: Complexity RNTS consisting of the following rules: encArg(z') -{ 1 }-> x :|: x_1 >= 0, x_2 >= 0, z' = 1 + x_1 + x_2, 0 = x, 0 = y, x >= 0, y >= 0 encArg(z') -{ 1 }-> y :|: x_1 >= 0, x_2 >= 0, z' = 1 + x_1 + x_2, 0 = x, 0 = y, x >= 0, y >= 0 encArg(z') -{ 0 }-> g(g(encArg(x_126), encArg(x_226)), g(encArg(x_130), encArg(x_230))) :|: z' = 1 + (1 + x_126 + x_226) + (1 + x_130 + x_230), x_130 >= 0, x_226 >= 0, x_126 >= 0, x_230 >= 0 encArg(z') -{ 0 }-> g(g(encArg(x_126), encArg(x_226)), f(encArg(x_129), encArg(x_229), encArg(x_314))) :|: x_226 >= 0, x_314 >= 0, x_126 >= 0, x_229 >= 0, x_129 >= 0, z' = 1 + (1 + x_126 + x_226) + (1 + x_129 + x_229 + x_314) encArg(z') -{ 0 }-> g(g(encArg(x_126), encArg(x_226)), 0) :|: x_226 >= 0, z' = 1 + (1 + x_126 + x_226) + x_2, x_126 >= 0, x_2 >= 0 encArg(z') -{ 0 }-> g(f(encArg(x_125), encArg(x_225), encArg(x_312)), g(encArg(x_128), encArg(x_228))) :|: x_128 >= 0, x_312 >= 0, z' = 1 + (1 + x_125 + x_225 + x_312) + (1 + x_128 + x_228), x_125 >= 0, x_225 >= 0, x_228 >= 0 encArg(z') -{ 0 }-> g(f(encArg(x_125), encArg(x_225), encArg(x_312)), f(encArg(x_127), encArg(x_227), encArg(x_313))) :|: x_127 >= 0, x_312 >= 0, z' = 1 + (1 + x_125 + x_225 + x_312) + (1 + x_127 + x_227 + x_313), x_125 >= 0, x_313 >= 0, x_225 >= 0, x_227 >= 0 encArg(z') -{ 0 }-> g(f(encArg(x_125), encArg(x_225), encArg(x_312)), 0) :|: x_312 >= 0, x_125 >= 0, x_225 >= 0, x_2 >= 0, z' = 1 + (1 + x_125 + x_225 + x_312) + x_2 encArg(z') -{ 0 }-> g(0, g(encArg(x_132), encArg(x_232))) :|: x_1 >= 0, z' = 1 + x_1 + (1 + x_132 + x_232), x_232 >= 0, x_132 >= 0 encArg(z') -{ 0 }-> g(0, f(encArg(x_131), encArg(x_231), encArg(x_315))) :|: x_315 >= 0, x_1 >= 0, z' = 1 + x_1 + (1 + x_131 + x_231 + x_315), x_231 >= 0, x_131 >= 0 encArg(z') -{ 0 }-> f(encArg(x_1), encArg(x_2), encArg(x_3)) :|: x_1 >= 0, z' = 1 + x_1 + x_2 + x_3, x_3 >= 0, x_2 >= 0 encArg(z') -{ 0 }-> 0 :|: z' >= 0 encArg(z') -{ 0 }-> 0 :|: x_1 >= 0, x_2 >= 0, z' = 1 + x_1 + x_2, v0 >= 0, v1 >= 0, 0 = v1, 0 = v0 encArg(z') -{ 0 }-> 1 + x0 + x1 :|: x_1 >= 0, x_2 >= 0, z' = 1 + x_1 + x_2, 0 = x1, x0 >= 0, x1 >= 0, 0 = x0 encode_f(z', z'', z1) -{ 0 }-> f(encArg(z'), encArg(z''), encArg(z1)) :|: z' >= 0, z1 >= 0, z'' >= 0 encode_f(z', z'', z1) -{ 0 }-> 0 :|: z' >= 0, z'' >= 0, z1 >= 0 encode_g(z', z'') -{ 1 }-> x :|: z' >= 0, z'' >= 0, 0 = x, 0 = y, x >= 0, y >= 0 encode_g(z', z'') -{ 1 }-> y :|: z' >= 0, z'' >= 0, 0 = x, 0 = y, x >= 0, y >= 0 encode_g(z', z'') -{ 0 }-> g(g(encArg(x_160), encArg(x_260)), g(encArg(x_164), encArg(x_264))) :|: x_264 >= 0, z' = 1 + x_160 + x_260, x_160 >= 0, x_164 >= 0, z'' = 1 + x_164 + x_264, x_260 >= 0 encode_g(z', z'') -{ 0 }-> g(g(encArg(x_160), encArg(x_260)), f(encArg(x_163), encArg(x_263), encArg(x_331))) :|: x_331 >= 0, x_263 >= 0, z' = 1 + x_160 + x_260, x_160 >= 0, x_163 >= 0, z'' = 1 + x_163 + x_263 + x_331, x_260 >= 0 encode_g(z', z'') -{ 0 }-> g(g(encArg(x_160), encArg(x_260)), 0) :|: z' = 1 + x_160 + x_260, x_160 >= 0, z'' >= 0, x_260 >= 0 encode_g(z', z'') -{ 0 }-> g(f(encArg(x_159), encArg(x_259), encArg(x_329)), g(encArg(x_162), encArg(x_262))) :|: x_159 >= 0, x_162 >= 0, x_329 >= 0, z' = 1 + x_159 + x_259 + x_329, z'' = 1 + x_162 + x_262, x_262 >= 0, x_259 >= 0 encode_g(z', z'') -{ 0 }-> g(f(encArg(x_159), encArg(x_259), encArg(x_329)), f(encArg(x_161), encArg(x_261), encArg(x_330))) :|: x_159 >= 0, x_329 >= 0, x_261 >= 0, z'' = 1 + x_161 + x_261 + x_330, z' = 1 + x_159 + x_259 + x_329, x_330 >= 0, x_259 >= 0, x_161 >= 0 encode_g(z', z'') -{ 0 }-> g(f(encArg(x_159), encArg(x_259), encArg(x_329)), 0) :|: x_159 >= 0, x_329 >= 0, z' = 1 + x_159 + x_259 + x_329, z'' >= 0, x_259 >= 0 encode_g(z', z'') -{ 0 }-> g(0, g(encArg(x_166), encArg(x_266))) :|: z' >= 0, x_166 >= 0, z'' = 1 + x_166 + x_266, x_266 >= 0 encode_g(z', z'') -{ 0 }-> g(0, f(encArg(x_165), encArg(x_265), encArg(x_332))) :|: x_332 >= 0, z' >= 0, x_265 >= 0, x_165 >= 0, z'' = 1 + x_165 + x_265 + x_332 encode_g(z', z'') -{ 0 }-> 0 :|: z' >= 0, z'' >= 0 encode_g(z', z'') -{ 0 }-> 0 :|: z' >= 0, z'' >= 0, v0 >= 0, v1 >= 0, 0 = v1, 0 = v0 encode_g(z', z'') -{ 0 }-> 1 + x0 + x1 :|: z' >= 0, z'' >= 0, 0 = x1, x0 >= 0, x1 >= 0, 0 = x0 f(z', z'', z1) -{ 1 }-> f(z1, z1, z1) :|: z1 >= 0, z' = 1 + z'' + y, z'' >= 0, y >= 0 f(z', z'', z1) -{ 0 }-> 0 :|: z' >= 0, z'' >= 0, z1 >= 0 g(z', z'') -{ 1 }-> z' :|: z' >= 0, z'' >= 0 g(z', z'') -{ 1 }-> z'' :|: z' >= 0, z'' >= 0 g(z', z'') -{ 0 }-> 0 :|: z' >= 0, z'' >= 0 g(z', z'') -{ 0 }-> 1 + z' + z'' :|: z' >= 0, z'' >= 0 Function symbols to be analyzed: {f}, {encArg}, {encode_f}, {encode_g} Previous analysis results are: g: runtime: O(1) [1], size: O(n^1) [1 + z' + z''] ---------------------------------------- (29) ResultPropagationProof (UPPER BOUND(ID)) Applied inner abstraction using the recently inferred runtime/size bounds where possible. ---------------------------------------- (30) Obligation: Complexity RNTS consisting of the following rules: encArg(z') -{ 1 }-> x :|: x_1 >= 0, x_2 >= 0, z' = 1 + x_1 + x_2, 0 = x, 0 = y, x >= 0, y >= 0 encArg(z') -{ 1 }-> y :|: x_1 >= 0, x_2 >= 0, z' = 1 + x_1 + x_2, 0 = x, 0 = y, x >= 0, y >= 0 encArg(z') -{ 0 }-> g(g(encArg(x_126), encArg(x_226)), g(encArg(x_130), encArg(x_230))) :|: z' = 1 + (1 + x_126 + x_226) + (1 + x_130 + x_230), x_130 >= 0, x_226 >= 0, x_126 >= 0, x_230 >= 0 encArg(z') -{ 0 }-> g(g(encArg(x_126), encArg(x_226)), f(encArg(x_129), encArg(x_229), encArg(x_314))) :|: x_226 >= 0, x_314 >= 0, x_126 >= 0, x_229 >= 0, x_129 >= 0, z' = 1 + (1 + x_126 + x_226) + (1 + x_129 + x_229 + x_314) encArg(z') -{ 0 }-> g(g(encArg(x_126), encArg(x_226)), 0) :|: x_226 >= 0, z' = 1 + (1 + x_126 + x_226) + x_2, x_126 >= 0, x_2 >= 0 encArg(z') -{ 0 }-> g(f(encArg(x_125), encArg(x_225), encArg(x_312)), g(encArg(x_128), encArg(x_228))) :|: x_128 >= 0, x_312 >= 0, z' = 1 + (1 + x_125 + x_225 + x_312) + (1 + x_128 + x_228), x_125 >= 0, x_225 >= 0, x_228 >= 0 encArg(z') -{ 0 }-> g(f(encArg(x_125), encArg(x_225), encArg(x_312)), f(encArg(x_127), encArg(x_227), encArg(x_313))) :|: x_127 >= 0, x_312 >= 0, z' = 1 + (1 + x_125 + x_225 + x_312) + (1 + x_127 + x_227 + x_313), x_125 >= 0, x_313 >= 0, x_225 >= 0, x_227 >= 0 encArg(z') -{ 0 }-> g(f(encArg(x_125), encArg(x_225), encArg(x_312)), 0) :|: x_312 >= 0, x_125 >= 0, x_225 >= 0, x_2 >= 0, z' = 1 + (1 + x_125 + x_225 + x_312) + x_2 encArg(z') -{ 0 }-> g(0, g(encArg(x_132), encArg(x_232))) :|: x_1 >= 0, z' = 1 + x_1 + (1 + x_132 + x_232), x_232 >= 0, x_132 >= 0 encArg(z') -{ 0 }-> g(0, f(encArg(x_131), encArg(x_231), encArg(x_315))) :|: x_315 >= 0, x_1 >= 0, z' = 1 + x_1 + (1 + x_131 + x_231 + x_315), x_231 >= 0, x_131 >= 0 encArg(z') -{ 0 }-> f(encArg(x_1), encArg(x_2), encArg(x_3)) :|: x_1 >= 0, z' = 1 + x_1 + x_2 + x_3, x_3 >= 0, x_2 >= 0 encArg(z') -{ 0 }-> 0 :|: z' >= 0 encArg(z') -{ 0 }-> 0 :|: x_1 >= 0, x_2 >= 0, z' = 1 + x_1 + x_2, v0 >= 0, v1 >= 0, 0 = v1, 0 = v0 encArg(z') -{ 0 }-> 1 + x0 + x1 :|: x_1 >= 0, x_2 >= 0, z' = 1 + x_1 + x_2, 0 = x1, x0 >= 0, x1 >= 0, 0 = x0 encode_f(z', z'', z1) -{ 0 }-> f(encArg(z'), encArg(z''), encArg(z1)) :|: z' >= 0, z1 >= 0, z'' >= 0 encode_f(z', z'', z1) -{ 0 }-> 0 :|: z' >= 0, z'' >= 0, z1 >= 0 encode_g(z', z'') -{ 1 }-> x :|: z' >= 0, z'' >= 0, 0 = x, 0 = y, x >= 0, y >= 0 encode_g(z', z'') -{ 1 }-> y :|: z' >= 0, z'' >= 0, 0 = x, 0 = y, x >= 0, y >= 0 encode_g(z', z'') -{ 0 }-> g(g(encArg(x_160), encArg(x_260)), g(encArg(x_164), encArg(x_264))) :|: x_264 >= 0, z' = 1 + x_160 + x_260, x_160 >= 0, x_164 >= 0, z'' = 1 + x_164 + x_264, x_260 >= 0 encode_g(z', z'') -{ 0 }-> g(g(encArg(x_160), encArg(x_260)), f(encArg(x_163), encArg(x_263), encArg(x_331))) :|: x_331 >= 0, x_263 >= 0, z' = 1 + x_160 + x_260, x_160 >= 0, x_163 >= 0, z'' = 1 + x_163 + x_263 + x_331, x_260 >= 0 encode_g(z', z'') -{ 0 }-> g(g(encArg(x_160), encArg(x_260)), 0) :|: z' = 1 + x_160 + x_260, x_160 >= 0, z'' >= 0, x_260 >= 0 encode_g(z', z'') -{ 0 }-> g(f(encArg(x_159), encArg(x_259), encArg(x_329)), g(encArg(x_162), encArg(x_262))) :|: x_159 >= 0, x_162 >= 0, x_329 >= 0, z' = 1 + x_159 + x_259 + x_329, z'' = 1 + x_162 + x_262, x_262 >= 0, x_259 >= 0 encode_g(z', z'') -{ 0 }-> g(f(encArg(x_159), encArg(x_259), encArg(x_329)), f(encArg(x_161), encArg(x_261), encArg(x_330))) :|: x_159 >= 0, x_329 >= 0, x_261 >= 0, z'' = 1 + x_161 + x_261 + x_330, z' = 1 + x_159 + x_259 + x_329, x_330 >= 0, x_259 >= 0, x_161 >= 0 encode_g(z', z'') -{ 0 }-> g(f(encArg(x_159), encArg(x_259), encArg(x_329)), 0) :|: x_159 >= 0, x_329 >= 0, z' = 1 + x_159 + x_259 + x_329, z'' >= 0, x_259 >= 0 encode_g(z', z'') -{ 0 }-> g(0, g(encArg(x_166), encArg(x_266))) :|: z' >= 0, x_166 >= 0, z'' = 1 + x_166 + x_266, x_266 >= 0 encode_g(z', z'') -{ 0 }-> g(0, f(encArg(x_165), encArg(x_265), encArg(x_332))) :|: x_332 >= 0, z' >= 0, x_265 >= 0, x_165 >= 0, z'' = 1 + x_165 + x_265 + x_332 encode_g(z', z'') -{ 0 }-> 0 :|: z' >= 0, z'' >= 0 encode_g(z', z'') -{ 0 }-> 0 :|: z' >= 0, z'' >= 0, v0 >= 0, v1 >= 0, 0 = v1, 0 = v0 encode_g(z', z'') -{ 0 }-> 1 + x0 + x1 :|: z' >= 0, z'' >= 0, 0 = x1, x0 >= 0, x1 >= 0, 0 = x0 f(z', z'', z1) -{ 1 }-> f(z1, z1, z1) :|: z1 >= 0, z' = 1 + z'' + y, z'' >= 0, y >= 0 f(z', z'', z1) -{ 0 }-> 0 :|: z' >= 0, z'' >= 0, z1 >= 0 g(z', z'') -{ 1 }-> z' :|: z' >= 0, z'' >= 0 g(z', z'') -{ 1 }-> z'' :|: z' >= 0, z'' >= 0 g(z', z'') -{ 0 }-> 0 :|: z' >= 0, z'' >= 0 g(z', z'') -{ 0 }-> 1 + z' + z'' :|: z' >= 0, z'' >= 0 Function symbols to be analyzed: {f}, {encArg}, {encode_f}, {encode_g} Previous analysis results are: g: runtime: O(1) [1], size: O(n^1) [1 + z' + z''] ---------------------------------------- (31) 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 ---------------------------------------- (32) Obligation: Complexity RNTS consisting of the following rules: encArg(z') -{ 1 }-> x :|: x_1 >= 0, x_2 >= 0, z' = 1 + x_1 + x_2, 0 = x, 0 = y, x >= 0, y >= 0 encArg(z') -{ 1 }-> y :|: x_1 >= 0, x_2 >= 0, z' = 1 + x_1 + x_2, 0 = x, 0 = y, x >= 0, y >= 0 encArg(z') -{ 0 }-> g(g(encArg(x_126), encArg(x_226)), g(encArg(x_130), encArg(x_230))) :|: z' = 1 + (1 + x_126 + x_226) + (1 + x_130 + x_230), x_130 >= 0, x_226 >= 0, x_126 >= 0, x_230 >= 0 encArg(z') -{ 0 }-> g(g(encArg(x_126), encArg(x_226)), f(encArg(x_129), encArg(x_229), encArg(x_314))) :|: x_226 >= 0, x_314 >= 0, x_126 >= 0, x_229 >= 0, x_129 >= 0, z' = 1 + (1 + x_126 + x_226) + (1 + x_129 + x_229 + x_314) encArg(z') -{ 0 }-> g(g(encArg(x_126), encArg(x_226)), 0) :|: x_226 >= 0, z' = 1 + (1 + x_126 + x_226) + x_2, x_126 >= 0, x_2 >= 0 encArg(z') -{ 0 }-> g(f(encArg(x_125), encArg(x_225), encArg(x_312)), g(encArg(x_128), encArg(x_228))) :|: x_128 >= 0, x_312 >= 0, z' = 1 + (1 + x_125 + x_225 + x_312) + (1 + x_128 + x_228), x_125 >= 0, x_225 >= 0, x_228 >= 0 encArg(z') -{ 0 }-> g(f(encArg(x_125), encArg(x_225), encArg(x_312)), f(encArg(x_127), encArg(x_227), encArg(x_313))) :|: x_127 >= 0, x_312 >= 0, z' = 1 + (1 + x_125 + x_225 + x_312) + (1 + x_127 + x_227 + x_313), x_125 >= 0, x_313 >= 0, x_225 >= 0, x_227 >= 0 encArg(z') -{ 0 }-> g(f(encArg(x_125), encArg(x_225), encArg(x_312)), 0) :|: x_312 >= 0, x_125 >= 0, x_225 >= 0, x_2 >= 0, z' = 1 + (1 + x_125 + x_225 + x_312) + x_2 encArg(z') -{ 0 }-> g(0, g(encArg(x_132), encArg(x_232))) :|: x_1 >= 0, z' = 1 + x_1 + (1 + x_132 + x_232), x_232 >= 0, x_132 >= 0 encArg(z') -{ 0 }-> g(0, f(encArg(x_131), encArg(x_231), encArg(x_315))) :|: x_315 >= 0, x_1 >= 0, z' = 1 + x_1 + (1 + x_131 + x_231 + x_315), x_231 >= 0, x_131 >= 0 encArg(z') -{ 0 }-> f(encArg(x_1), encArg(x_2), encArg(x_3)) :|: x_1 >= 0, z' = 1 + x_1 + x_2 + x_3, x_3 >= 0, x_2 >= 0 encArg(z') -{ 0 }-> 0 :|: z' >= 0 encArg(z') -{ 0 }-> 0 :|: x_1 >= 0, x_2 >= 0, z' = 1 + x_1 + x_2, v0 >= 0, v1 >= 0, 0 = v1, 0 = v0 encArg(z') -{ 0 }-> 1 + x0 + x1 :|: x_1 >= 0, x_2 >= 0, z' = 1 + x_1 + x_2, 0 = x1, x0 >= 0, x1 >= 0, 0 = x0 encode_f(z', z'', z1) -{ 0 }-> f(encArg(z'), encArg(z''), encArg(z1)) :|: z' >= 0, z1 >= 0, z'' >= 0 encode_f(z', z'', z1) -{ 0 }-> 0 :|: z' >= 0, z'' >= 0, z1 >= 0 encode_g(z', z'') -{ 1 }-> x :|: z' >= 0, z'' >= 0, 0 = x, 0 = y, x >= 0, y >= 0 encode_g(z', z'') -{ 1 }-> y :|: z' >= 0, z'' >= 0, 0 = x, 0 = y, x >= 0, y >= 0 encode_g(z', z'') -{ 0 }-> g(g(encArg(x_160), encArg(x_260)), g(encArg(x_164), encArg(x_264))) :|: x_264 >= 0, z' = 1 + x_160 + x_260, x_160 >= 0, x_164 >= 0, z'' = 1 + x_164 + x_264, x_260 >= 0 encode_g(z', z'') -{ 0 }-> g(g(encArg(x_160), encArg(x_260)), f(encArg(x_163), encArg(x_263), encArg(x_331))) :|: x_331 >= 0, x_263 >= 0, z' = 1 + x_160 + x_260, x_160 >= 0, x_163 >= 0, z'' = 1 + x_163 + x_263 + x_331, x_260 >= 0 encode_g(z', z'') -{ 0 }-> g(g(encArg(x_160), encArg(x_260)), 0) :|: z' = 1 + x_160 + x_260, x_160 >= 0, z'' >= 0, x_260 >= 0 encode_g(z', z'') -{ 0 }-> g(f(encArg(x_159), encArg(x_259), encArg(x_329)), g(encArg(x_162), encArg(x_262))) :|: x_159 >= 0, x_162 >= 0, x_329 >= 0, z' = 1 + x_159 + x_259 + x_329, z'' = 1 + x_162 + x_262, x_262 >= 0, x_259 >= 0 encode_g(z', z'') -{ 0 }-> g(f(encArg(x_159), encArg(x_259), encArg(x_329)), f(encArg(x_161), encArg(x_261), encArg(x_330))) :|: x_159 >= 0, x_329 >= 0, x_261 >= 0, z'' = 1 + x_161 + x_261 + x_330, z' = 1 + x_159 + x_259 + x_329, x_330 >= 0, x_259 >= 0, x_161 >= 0 encode_g(z', z'') -{ 0 }-> g(f(encArg(x_159), encArg(x_259), encArg(x_329)), 0) :|: x_159 >= 0, x_329 >= 0, z' = 1 + x_159 + x_259 + x_329, z'' >= 0, x_259 >= 0 encode_g(z', z'') -{ 0 }-> g(0, g(encArg(x_166), encArg(x_266))) :|: z' >= 0, x_166 >= 0, z'' = 1 + x_166 + x_266, x_266 >= 0 encode_g(z', z'') -{ 0 }-> g(0, f(encArg(x_165), encArg(x_265), encArg(x_332))) :|: x_332 >= 0, z' >= 0, x_265 >= 0, x_165 >= 0, z'' = 1 + x_165 + x_265 + x_332 encode_g(z', z'') -{ 0 }-> 0 :|: z' >= 0, z'' >= 0 encode_g(z', z'') -{ 0 }-> 0 :|: z' >= 0, z'' >= 0, v0 >= 0, v1 >= 0, 0 = v1, 0 = v0 encode_g(z', z'') -{ 0 }-> 1 + x0 + x1 :|: z' >= 0, z'' >= 0, 0 = x1, x0 >= 0, x1 >= 0, 0 = x0 f(z', z'', z1) -{ 1 }-> f(z1, z1, z1) :|: z1 >= 0, z' = 1 + z'' + y, z'' >= 0, y >= 0 f(z', z'', z1) -{ 0 }-> 0 :|: z' >= 0, z'' >= 0, z1 >= 0 g(z', z'') -{ 1 }-> z' :|: z' >= 0, z'' >= 0 g(z', z'') -{ 1 }-> z'' :|: z' >= 0, z'' >= 0 g(z', z'') -{ 0 }-> 0 :|: z' >= 0, z'' >= 0 g(z', z'') -{ 0 }-> 1 + z' + z'' :|: z' >= 0, z'' >= 0 Function symbols to be analyzed: {f}, {encArg}, {encode_f}, {encode_g} Previous analysis results are: g: runtime: O(1) [1], size: O(n^1) [1 + z' + z''] f: runtime: ?, size: O(1) [0] ---------------------------------------- (33) 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: 1 ---------------------------------------- (34) Obligation: Complexity RNTS consisting of the following rules: encArg(z') -{ 1 }-> x :|: x_1 >= 0, x_2 >= 0, z' = 1 + x_1 + x_2, 0 = x, 0 = y, x >= 0, y >= 0 encArg(z') -{ 1 }-> y :|: x_1 >= 0, x_2 >= 0, z' = 1 + x_1 + x_2, 0 = x, 0 = y, x >= 0, y >= 0 encArg(z') -{ 0 }-> g(g(encArg(x_126), encArg(x_226)), g(encArg(x_130), encArg(x_230))) :|: z' = 1 + (1 + x_126 + x_226) + (1 + x_130 + x_230), x_130 >= 0, x_226 >= 0, x_126 >= 0, x_230 >= 0 encArg(z') -{ 0 }-> g(g(encArg(x_126), encArg(x_226)), f(encArg(x_129), encArg(x_229), encArg(x_314))) :|: x_226 >= 0, x_314 >= 0, x_126 >= 0, x_229 >= 0, x_129 >= 0, z' = 1 + (1 + x_126 + x_226) + (1 + x_129 + x_229 + x_314) encArg(z') -{ 0 }-> g(g(encArg(x_126), encArg(x_226)), 0) :|: x_226 >= 0, z' = 1 + (1 + x_126 + x_226) + x_2, x_126 >= 0, x_2 >= 0 encArg(z') -{ 0 }-> g(f(encArg(x_125), encArg(x_225), encArg(x_312)), g(encArg(x_128), encArg(x_228))) :|: x_128 >= 0, x_312 >= 0, z' = 1 + (1 + x_125 + x_225 + x_312) + (1 + x_128 + x_228), x_125 >= 0, x_225 >= 0, x_228 >= 0 encArg(z') -{ 0 }-> g(f(encArg(x_125), encArg(x_225), encArg(x_312)), f(encArg(x_127), encArg(x_227), encArg(x_313))) :|: x_127 >= 0, x_312 >= 0, z' = 1 + (1 + x_125 + x_225 + x_312) + (1 + x_127 + x_227 + x_313), x_125 >= 0, x_313 >= 0, x_225 >= 0, x_227 >= 0 encArg(z') -{ 0 }-> g(f(encArg(x_125), encArg(x_225), encArg(x_312)), 0) :|: x_312 >= 0, x_125 >= 0, x_225 >= 0, x_2 >= 0, z' = 1 + (1 + x_125 + x_225 + x_312) + x_2 encArg(z') -{ 0 }-> g(0, g(encArg(x_132), encArg(x_232))) :|: x_1 >= 0, z' = 1 + x_1 + (1 + x_132 + x_232), x_232 >= 0, x_132 >= 0 encArg(z') -{ 0 }-> g(0, f(encArg(x_131), encArg(x_231), encArg(x_315))) :|: x_315 >= 0, x_1 >= 0, z' = 1 + x_1 + (1 + x_131 + x_231 + x_315), x_231 >= 0, x_131 >= 0 encArg(z') -{ 0 }-> f(encArg(x_1), encArg(x_2), encArg(x_3)) :|: x_1 >= 0, z' = 1 + x_1 + x_2 + x_3, x_3 >= 0, x_2 >= 0 encArg(z') -{ 0 }-> 0 :|: z' >= 0 encArg(z') -{ 0 }-> 0 :|: x_1 >= 0, x_2 >= 0, z' = 1 + x_1 + x_2, v0 >= 0, v1 >= 0, 0 = v1, 0 = v0 encArg(z') -{ 0 }-> 1 + x0 + x1 :|: x_1 >= 0, x_2 >= 0, z' = 1 + x_1 + x_2, 0 = x1, x0 >= 0, x1 >= 0, 0 = x0 encode_f(z', z'', z1) -{ 0 }-> f(encArg(z'), encArg(z''), encArg(z1)) :|: z' >= 0, z1 >= 0, z'' >= 0 encode_f(z', z'', z1) -{ 0 }-> 0 :|: z' >= 0, z'' >= 0, z1 >= 0 encode_g(z', z'') -{ 1 }-> x :|: z' >= 0, z'' >= 0, 0 = x, 0 = y, x >= 0, y >= 0 encode_g(z', z'') -{ 1 }-> y :|: z' >= 0, z'' >= 0, 0 = x, 0 = y, x >= 0, y >= 0 encode_g(z', z'') -{ 0 }-> g(g(encArg(x_160), encArg(x_260)), g(encArg(x_164), encArg(x_264))) :|: x_264 >= 0, z' = 1 + x_160 + x_260, x_160 >= 0, x_164 >= 0, z'' = 1 + x_164 + x_264, x_260 >= 0 encode_g(z', z'') -{ 0 }-> g(g(encArg(x_160), encArg(x_260)), f(encArg(x_163), encArg(x_263), encArg(x_331))) :|: x_331 >= 0, x_263 >= 0, z' = 1 + x_160 + x_260, x_160 >= 0, x_163 >= 0, z'' = 1 + x_163 + x_263 + x_331, x_260 >= 0 encode_g(z', z'') -{ 0 }-> g(g(encArg(x_160), encArg(x_260)), 0) :|: z' = 1 + x_160 + x_260, x_160 >= 0, z'' >= 0, x_260 >= 0 encode_g(z', z'') -{ 0 }-> g(f(encArg(x_159), encArg(x_259), encArg(x_329)), g(encArg(x_162), encArg(x_262))) :|: x_159 >= 0, x_162 >= 0, x_329 >= 0, z' = 1 + x_159 + x_259 + x_329, z'' = 1 + x_162 + x_262, x_262 >= 0, x_259 >= 0 encode_g(z', z'') -{ 0 }-> g(f(encArg(x_159), encArg(x_259), encArg(x_329)), f(encArg(x_161), encArg(x_261), encArg(x_330))) :|: x_159 >= 0, x_329 >= 0, x_261 >= 0, z'' = 1 + x_161 + x_261 + x_330, z' = 1 + x_159 + x_259 + x_329, x_330 >= 0, x_259 >= 0, x_161 >= 0 encode_g(z', z'') -{ 0 }-> g(f(encArg(x_159), encArg(x_259), encArg(x_329)), 0) :|: x_159 >= 0, x_329 >= 0, z' = 1 + x_159 + x_259 + x_329, z'' >= 0, x_259 >= 0 encode_g(z', z'') -{ 0 }-> g(0, g(encArg(x_166), encArg(x_266))) :|: z' >= 0, x_166 >= 0, z'' = 1 + x_166 + x_266, x_266 >= 0 encode_g(z', z'') -{ 0 }-> g(0, f(encArg(x_165), encArg(x_265), encArg(x_332))) :|: x_332 >= 0, z' >= 0, x_265 >= 0, x_165 >= 0, z'' = 1 + x_165 + x_265 + x_332 encode_g(z', z'') -{ 0 }-> 0 :|: z' >= 0, z'' >= 0 encode_g(z', z'') -{ 0 }-> 0 :|: z' >= 0, z'' >= 0, v0 >= 0, v1 >= 0, 0 = v1, 0 = v0 encode_g(z', z'') -{ 0 }-> 1 + x0 + x1 :|: z' >= 0, z'' >= 0, 0 = x1, x0 >= 0, x1 >= 0, 0 = x0 f(z', z'', z1) -{ 1 }-> f(z1, z1, z1) :|: z1 >= 0, z' = 1 + z'' + y, z'' >= 0, y >= 0 f(z', z'', z1) -{ 0 }-> 0 :|: z' >= 0, z'' >= 0, z1 >= 0 g(z', z'') -{ 1 }-> z' :|: z' >= 0, z'' >= 0 g(z', z'') -{ 1 }-> z'' :|: z' >= 0, z'' >= 0 g(z', z'') -{ 0 }-> 0 :|: z' >= 0, z'' >= 0 g(z', z'') -{ 0 }-> 1 + z' + z'' :|: z' >= 0, z'' >= 0 Function symbols to be analyzed: {encArg}, {encode_f}, {encode_g} Previous analysis results are: g: runtime: O(1) [1], size: O(n^1) [1 + z' + z''] f: runtime: O(1) [1], size: O(1) [0] ---------------------------------------- (35) ResultPropagationProof (UPPER BOUND(ID)) Applied inner abstraction using the recently inferred runtime/size bounds where possible. ---------------------------------------- (36) Obligation: Complexity RNTS consisting of the following rules: encArg(z') -{ 1 }-> x :|: x_1 >= 0, x_2 >= 0, z' = 1 + x_1 + x_2, 0 = x, 0 = y, x >= 0, y >= 0 encArg(z') -{ 1 }-> y :|: x_1 >= 0, x_2 >= 0, z' = 1 + x_1 + x_2, 0 = x, 0 = y, x >= 0, y >= 0 encArg(z') -{ 0 }-> g(g(encArg(x_126), encArg(x_226)), g(encArg(x_130), encArg(x_230))) :|: z' = 1 + (1 + x_126 + x_226) + (1 + x_130 + x_230), x_130 >= 0, x_226 >= 0, x_126 >= 0, x_230 >= 0 encArg(z') -{ 0 }-> g(g(encArg(x_126), encArg(x_226)), f(encArg(x_129), encArg(x_229), encArg(x_314))) :|: x_226 >= 0, x_314 >= 0, x_126 >= 0, x_229 >= 0, x_129 >= 0, z' = 1 + (1 + x_126 + x_226) + (1 + x_129 + x_229 + x_314) encArg(z') -{ 0 }-> g(g(encArg(x_126), encArg(x_226)), 0) :|: x_226 >= 0, z' = 1 + (1 + x_126 + x_226) + x_2, x_126 >= 0, x_2 >= 0 encArg(z') -{ 0 }-> g(f(encArg(x_125), encArg(x_225), encArg(x_312)), g(encArg(x_128), encArg(x_228))) :|: x_128 >= 0, x_312 >= 0, z' = 1 + (1 + x_125 + x_225 + x_312) + (1 + x_128 + x_228), x_125 >= 0, x_225 >= 0, x_228 >= 0 encArg(z') -{ 0 }-> g(f(encArg(x_125), encArg(x_225), encArg(x_312)), f(encArg(x_127), encArg(x_227), encArg(x_313))) :|: x_127 >= 0, x_312 >= 0, z' = 1 + (1 + x_125 + x_225 + x_312) + (1 + x_127 + x_227 + x_313), x_125 >= 0, x_313 >= 0, x_225 >= 0, x_227 >= 0 encArg(z') -{ 0 }-> g(f(encArg(x_125), encArg(x_225), encArg(x_312)), 0) :|: x_312 >= 0, x_125 >= 0, x_225 >= 0, x_2 >= 0, z' = 1 + (1 + x_125 + x_225 + x_312) + x_2 encArg(z') -{ 0 }-> g(0, g(encArg(x_132), encArg(x_232))) :|: x_1 >= 0, z' = 1 + x_1 + (1 + x_132 + x_232), x_232 >= 0, x_132 >= 0 encArg(z') -{ 0 }-> g(0, f(encArg(x_131), encArg(x_231), encArg(x_315))) :|: x_315 >= 0, x_1 >= 0, z' = 1 + x_1 + (1 + x_131 + x_231 + x_315), x_231 >= 0, x_131 >= 0 encArg(z') -{ 0 }-> f(encArg(x_1), encArg(x_2), encArg(x_3)) :|: x_1 >= 0, z' = 1 + x_1 + x_2 + x_3, x_3 >= 0, x_2 >= 0 encArg(z') -{ 0 }-> 0 :|: z' >= 0 encArg(z') -{ 0 }-> 0 :|: x_1 >= 0, x_2 >= 0, z' = 1 + x_1 + x_2, v0 >= 0, v1 >= 0, 0 = v1, 0 = v0 encArg(z') -{ 0 }-> 1 + x0 + x1 :|: x_1 >= 0, x_2 >= 0, z' = 1 + x_1 + x_2, 0 = x1, x0 >= 0, x1 >= 0, 0 = x0 encode_f(z', z'', z1) -{ 0 }-> f(encArg(z'), encArg(z''), encArg(z1)) :|: z' >= 0, z1 >= 0, z'' >= 0 encode_f(z', z'', z1) -{ 0 }-> 0 :|: z' >= 0, z'' >= 0, z1 >= 0 encode_g(z', z'') -{ 1 }-> x :|: z' >= 0, z'' >= 0, 0 = x, 0 = y, x >= 0, y >= 0 encode_g(z', z'') -{ 1 }-> y :|: z' >= 0, z'' >= 0, 0 = x, 0 = y, x >= 0, y >= 0 encode_g(z', z'') -{ 0 }-> g(g(encArg(x_160), encArg(x_260)), g(encArg(x_164), encArg(x_264))) :|: x_264 >= 0, z' = 1 + x_160 + x_260, x_160 >= 0, x_164 >= 0, z'' = 1 + x_164 + x_264, x_260 >= 0 encode_g(z', z'') -{ 0 }-> g(g(encArg(x_160), encArg(x_260)), f(encArg(x_163), encArg(x_263), encArg(x_331))) :|: x_331 >= 0, x_263 >= 0, z' = 1 + x_160 + x_260, x_160 >= 0, x_163 >= 0, z'' = 1 + x_163 + x_263 + x_331, x_260 >= 0 encode_g(z', z'') -{ 0 }-> g(g(encArg(x_160), encArg(x_260)), 0) :|: z' = 1 + x_160 + x_260, x_160 >= 0, z'' >= 0, x_260 >= 0 encode_g(z', z'') -{ 0 }-> g(f(encArg(x_159), encArg(x_259), encArg(x_329)), g(encArg(x_162), encArg(x_262))) :|: x_159 >= 0, x_162 >= 0, x_329 >= 0, z' = 1 + x_159 + x_259 + x_329, z'' = 1 + x_162 + x_262, x_262 >= 0, x_259 >= 0 encode_g(z', z'') -{ 0 }-> g(f(encArg(x_159), encArg(x_259), encArg(x_329)), f(encArg(x_161), encArg(x_261), encArg(x_330))) :|: x_159 >= 0, x_329 >= 0, x_261 >= 0, z'' = 1 + x_161 + x_261 + x_330, z' = 1 + x_159 + x_259 + x_329, x_330 >= 0, x_259 >= 0, x_161 >= 0 encode_g(z', z'') -{ 0 }-> g(f(encArg(x_159), encArg(x_259), encArg(x_329)), 0) :|: x_159 >= 0, x_329 >= 0, z' = 1 + x_159 + x_259 + x_329, z'' >= 0, x_259 >= 0 encode_g(z', z'') -{ 0 }-> g(0, g(encArg(x_166), encArg(x_266))) :|: z' >= 0, x_166 >= 0, z'' = 1 + x_166 + x_266, x_266 >= 0 encode_g(z', z'') -{ 0 }-> g(0, f(encArg(x_165), encArg(x_265), encArg(x_332))) :|: x_332 >= 0, z' >= 0, x_265 >= 0, x_165 >= 0, z'' = 1 + x_165 + x_265 + x_332 encode_g(z', z'') -{ 0 }-> 0 :|: z' >= 0, z'' >= 0 encode_g(z', z'') -{ 0 }-> 0 :|: z' >= 0, z'' >= 0, v0 >= 0, v1 >= 0, 0 = v1, 0 = v0 encode_g(z', z'') -{ 0 }-> 1 + x0 + x1 :|: z' >= 0, z'' >= 0, 0 = x1, x0 >= 0, x1 >= 0, 0 = x0 f(z', z'', z1) -{ 2 }-> s :|: s >= 0, s <= 0, z1 >= 0, z' = 1 + z'' + y, z'' >= 0, y >= 0 f(z', z'', z1) -{ 0 }-> 0 :|: z' >= 0, z'' >= 0, z1 >= 0 g(z', z'') -{ 1 }-> z' :|: z' >= 0, z'' >= 0 g(z', z'') -{ 1 }-> z'' :|: z' >= 0, z'' >= 0 g(z', z'') -{ 0 }-> 0 :|: z' >= 0, z'' >= 0 g(z', z'') -{ 0 }-> 1 + z' + z'' :|: z' >= 0, z'' >= 0 Function symbols to be analyzed: {encArg}, {encode_f}, {encode_g} Previous analysis results are: g: runtime: O(1) [1], size: O(n^1) [1 + z' + z''] f: runtime: O(1) [1], size: O(1) [0] ---------------------------------------- (37) IntTrsBoundProof (UPPER BOUND(ID)) Computed SIZE bound using CoFloCo for: encArg after applying outer abstraction to obtain an ITS, resulting in: O(n^1) with polynomial bound: 1 + z' ---------------------------------------- (38) Obligation: Complexity RNTS consisting of the following rules: encArg(z') -{ 1 }-> x :|: x_1 >= 0, x_2 >= 0, z' = 1 + x_1 + x_2, 0 = x, 0 = y, x >= 0, y >= 0 encArg(z') -{ 1 }-> y :|: x_1 >= 0, x_2 >= 0, z' = 1 + x_1 + x_2, 0 = x, 0 = y, x >= 0, y >= 0 encArg(z') -{ 0 }-> g(g(encArg(x_126), encArg(x_226)), g(encArg(x_130), encArg(x_230))) :|: z' = 1 + (1 + x_126 + x_226) + (1 + x_130 + x_230), x_130 >= 0, x_226 >= 0, x_126 >= 0, x_230 >= 0 encArg(z') -{ 0 }-> g(g(encArg(x_126), encArg(x_226)), f(encArg(x_129), encArg(x_229), encArg(x_314))) :|: x_226 >= 0, x_314 >= 0, x_126 >= 0, x_229 >= 0, x_129 >= 0, z' = 1 + (1 + x_126 + x_226) + (1 + x_129 + x_229 + x_314) encArg(z') -{ 0 }-> g(g(encArg(x_126), encArg(x_226)), 0) :|: x_226 >= 0, z' = 1 + (1 + x_126 + x_226) + x_2, x_126 >= 0, x_2 >= 0 encArg(z') -{ 0 }-> g(f(encArg(x_125), encArg(x_225), encArg(x_312)), g(encArg(x_128), encArg(x_228))) :|: x_128 >= 0, x_312 >= 0, z' = 1 + (1 + x_125 + x_225 + x_312) + (1 + x_128 + x_228), x_125 >= 0, x_225 >= 0, x_228 >= 0 encArg(z') -{ 0 }-> g(f(encArg(x_125), encArg(x_225), encArg(x_312)), f(encArg(x_127), encArg(x_227), encArg(x_313))) :|: x_127 >= 0, x_312 >= 0, z' = 1 + (1 + x_125 + x_225 + x_312) + (1 + x_127 + x_227 + x_313), x_125 >= 0, x_313 >= 0, x_225 >= 0, x_227 >= 0 encArg(z') -{ 0 }-> g(f(encArg(x_125), encArg(x_225), encArg(x_312)), 0) :|: x_312 >= 0, x_125 >= 0, x_225 >= 0, x_2 >= 0, z' = 1 + (1 + x_125 + x_225 + x_312) + x_2 encArg(z') -{ 0 }-> g(0, g(encArg(x_132), encArg(x_232))) :|: x_1 >= 0, z' = 1 + x_1 + (1 + x_132 + x_232), x_232 >= 0, x_132 >= 0 encArg(z') -{ 0 }-> g(0, f(encArg(x_131), encArg(x_231), encArg(x_315))) :|: x_315 >= 0, x_1 >= 0, z' = 1 + x_1 + (1 + x_131 + x_231 + x_315), x_231 >= 0, x_131 >= 0 encArg(z') -{ 0 }-> f(encArg(x_1), encArg(x_2), encArg(x_3)) :|: x_1 >= 0, z' = 1 + x_1 + x_2 + x_3, x_3 >= 0, x_2 >= 0 encArg(z') -{ 0 }-> 0 :|: z' >= 0 encArg(z') -{ 0 }-> 0 :|: x_1 >= 0, x_2 >= 0, z' = 1 + x_1 + x_2, v0 >= 0, v1 >= 0, 0 = v1, 0 = v0 encArg(z') -{ 0 }-> 1 + x0 + x1 :|: x_1 >= 0, x_2 >= 0, z' = 1 + x_1 + x_2, 0 = x1, x0 >= 0, x1 >= 0, 0 = x0 encode_f(z', z'', z1) -{ 0 }-> f(encArg(z'), encArg(z''), encArg(z1)) :|: z' >= 0, z1 >= 0, z'' >= 0 encode_f(z', z'', z1) -{ 0 }-> 0 :|: z' >= 0, z'' >= 0, z1 >= 0 encode_g(z', z'') -{ 1 }-> x :|: z' >= 0, z'' >= 0, 0 = x, 0 = y, x >= 0, y >= 0 encode_g(z', z'') -{ 1 }-> y :|: z' >= 0, z'' >= 0, 0 = x, 0 = y, x >= 0, y >= 0 encode_g(z', z'') -{ 0 }-> g(g(encArg(x_160), encArg(x_260)), g(encArg(x_164), encArg(x_264))) :|: x_264 >= 0, z' = 1 + x_160 + x_260, x_160 >= 0, x_164 >= 0, z'' = 1 + x_164 + x_264, x_260 >= 0 encode_g(z', z'') -{ 0 }-> g(g(encArg(x_160), encArg(x_260)), f(encArg(x_163), encArg(x_263), encArg(x_331))) :|: x_331 >= 0, x_263 >= 0, z' = 1 + x_160 + x_260, x_160 >= 0, x_163 >= 0, z'' = 1 + x_163 + x_263 + x_331, x_260 >= 0 encode_g(z', z'') -{ 0 }-> g(g(encArg(x_160), encArg(x_260)), 0) :|: z' = 1 + x_160 + x_260, x_160 >= 0, z'' >= 0, x_260 >= 0 encode_g(z', z'') -{ 0 }-> g(f(encArg(x_159), encArg(x_259), encArg(x_329)), g(encArg(x_162), encArg(x_262))) :|: x_159 >= 0, x_162 >= 0, x_329 >= 0, z' = 1 + x_159 + x_259 + x_329, z'' = 1 + x_162 + x_262, x_262 >= 0, x_259 >= 0 encode_g(z', z'') -{ 0 }-> g(f(encArg(x_159), encArg(x_259), encArg(x_329)), f(encArg(x_161), encArg(x_261), encArg(x_330))) :|: x_159 >= 0, x_329 >= 0, x_261 >= 0, z'' = 1 + x_161 + x_261 + x_330, z' = 1 + x_159 + x_259 + x_329, x_330 >= 0, x_259 >= 0, x_161 >= 0 encode_g(z', z'') -{ 0 }-> g(f(encArg(x_159), encArg(x_259), encArg(x_329)), 0) :|: x_159 >= 0, x_329 >= 0, z' = 1 + x_159 + x_259 + x_329, z'' >= 0, x_259 >= 0 encode_g(z', z'') -{ 0 }-> g(0, g(encArg(x_166), encArg(x_266))) :|: z' >= 0, x_166 >= 0, z'' = 1 + x_166 + x_266, x_266 >= 0 encode_g(z', z'') -{ 0 }-> g(0, f(encArg(x_165), encArg(x_265), encArg(x_332))) :|: x_332 >= 0, z' >= 0, x_265 >= 0, x_165 >= 0, z'' = 1 + x_165 + x_265 + x_332 encode_g(z', z'') -{ 0 }-> 0 :|: z' >= 0, z'' >= 0 encode_g(z', z'') -{ 0 }-> 0 :|: z' >= 0, z'' >= 0, v0 >= 0, v1 >= 0, 0 = v1, 0 = v0 encode_g(z', z'') -{ 0 }-> 1 + x0 + x1 :|: z' >= 0, z'' >= 0, 0 = x1, x0 >= 0, x1 >= 0, 0 = x0 f(z', z'', z1) -{ 2 }-> s :|: s >= 0, s <= 0, z1 >= 0, z' = 1 + z'' + y, z'' >= 0, y >= 0 f(z', z'', z1) -{ 0 }-> 0 :|: z' >= 0, z'' >= 0, z1 >= 0 g(z', z'') -{ 1 }-> z' :|: z' >= 0, z'' >= 0 g(z', z'') -{ 1 }-> z'' :|: z' >= 0, z'' >= 0 g(z', z'') -{ 0 }-> 0 :|: z' >= 0, z'' >= 0 g(z', z'') -{ 0 }-> 1 + z' + z'' :|: z' >= 0, z'' >= 0 Function symbols to be analyzed: {encArg}, {encode_f}, {encode_g} Previous analysis results are: g: runtime: O(1) [1], size: O(n^1) [1 + z' + z''] f: runtime: O(1) [1], size: O(1) [0] encArg: runtime: ?, size: O(n^1) [1 + z'] ---------------------------------------- (39) 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: 1 + 4*z' ---------------------------------------- (40) Obligation: Complexity RNTS consisting of the following rules: encArg(z') -{ 1 }-> x :|: x_1 >= 0, x_2 >= 0, z' = 1 + x_1 + x_2, 0 = x, 0 = y, x >= 0, y >= 0 encArg(z') -{ 1 }-> y :|: x_1 >= 0, x_2 >= 0, z' = 1 + x_1 + x_2, 0 = x, 0 = y, x >= 0, y >= 0 encArg(z') -{ 0 }-> g(g(encArg(x_126), encArg(x_226)), g(encArg(x_130), encArg(x_230))) :|: z' = 1 + (1 + x_126 + x_226) + (1 + x_130 + x_230), x_130 >= 0, x_226 >= 0, x_126 >= 0, x_230 >= 0 encArg(z') -{ 0 }-> g(g(encArg(x_126), encArg(x_226)), f(encArg(x_129), encArg(x_229), encArg(x_314))) :|: x_226 >= 0, x_314 >= 0, x_126 >= 0, x_229 >= 0, x_129 >= 0, z' = 1 + (1 + x_126 + x_226) + (1 + x_129 + x_229 + x_314) encArg(z') -{ 0 }-> g(g(encArg(x_126), encArg(x_226)), 0) :|: x_226 >= 0, z' = 1 + (1 + x_126 + x_226) + x_2, x_126 >= 0, x_2 >= 0 encArg(z') -{ 0 }-> g(f(encArg(x_125), encArg(x_225), encArg(x_312)), g(encArg(x_128), encArg(x_228))) :|: x_128 >= 0, x_312 >= 0, z' = 1 + (1 + x_125 + x_225 + x_312) + (1 + x_128 + x_228), x_125 >= 0, x_225 >= 0, x_228 >= 0 encArg(z') -{ 0 }-> g(f(encArg(x_125), encArg(x_225), encArg(x_312)), f(encArg(x_127), encArg(x_227), encArg(x_313))) :|: x_127 >= 0, x_312 >= 0, z' = 1 + (1 + x_125 + x_225 + x_312) + (1 + x_127 + x_227 + x_313), x_125 >= 0, x_313 >= 0, x_225 >= 0, x_227 >= 0 encArg(z') -{ 0 }-> g(f(encArg(x_125), encArg(x_225), encArg(x_312)), 0) :|: x_312 >= 0, x_125 >= 0, x_225 >= 0, x_2 >= 0, z' = 1 + (1 + x_125 + x_225 + x_312) + x_2 encArg(z') -{ 0 }-> g(0, g(encArg(x_132), encArg(x_232))) :|: x_1 >= 0, z' = 1 + x_1 + (1 + x_132 + x_232), x_232 >= 0, x_132 >= 0 encArg(z') -{ 0 }-> g(0, f(encArg(x_131), encArg(x_231), encArg(x_315))) :|: x_315 >= 0, x_1 >= 0, z' = 1 + x_1 + (1 + x_131 + x_231 + x_315), x_231 >= 0, x_131 >= 0 encArg(z') -{ 0 }-> f(encArg(x_1), encArg(x_2), encArg(x_3)) :|: x_1 >= 0, z' = 1 + x_1 + x_2 + x_3, x_3 >= 0, x_2 >= 0 encArg(z') -{ 0 }-> 0 :|: z' >= 0 encArg(z') -{ 0 }-> 0 :|: x_1 >= 0, x_2 >= 0, z' = 1 + x_1 + x_2, v0 >= 0, v1 >= 0, 0 = v1, 0 = v0 encArg(z') -{ 0 }-> 1 + x0 + x1 :|: x_1 >= 0, x_2 >= 0, z' = 1 + x_1 + x_2, 0 = x1, x0 >= 0, x1 >= 0, 0 = x0 encode_f(z', z'', z1) -{ 0 }-> f(encArg(z'), encArg(z''), encArg(z1)) :|: z' >= 0, z1 >= 0, z'' >= 0 encode_f(z', z'', z1) -{ 0 }-> 0 :|: z' >= 0, z'' >= 0, z1 >= 0 encode_g(z', z'') -{ 1 }-> x :|: z' >= 0, z'' >= 0, 0 = x, 0 = y, x >= 0, y >= 0 encode_g(z', z'') -{ 1 }-> y :|: z' >= 0, z'' >= 0, 0 = x, 0 = y, x >= 0, y >= 0 encode_g(z', z'') -{ 0 }-> g(g(encArg(x_160), encArg(x_260)), g(encArg(x_164), encArg(x_264))) :|: x_264 >= 0, z' = 1 + x_160 + x_260, x_160 >= 0, x_164 >= 0, z'' = 1 + x_164 + x_264, x_260 >= 0 encode_g(z', z'') -{ 0 }-> g(g(encArg(x_160), encArg(x_260)), f(encArg(x_163), encArg(x_263), encArg(x_331))) :|: x_331 >= 0, x_263 >= 0, z' = 1 + x_160 + x_260, x_160 >= 0, x_163 >= 0, z'' = 1 + x_163 + x_263 + x_331, x_260 >= 0 encode_g(z', z'') -{ 0 }-> g(g(encArg(x_160), encArg(x_260)), 0) :|: z' = 1 + x_160 + x_260, x_160 >= 0, z'' >= 0, x_260 >= 0 encode_g(z', z'') -{ 0 }-> g(f(encArg(x_159), encArg(x_259), encArg(x_329)), g(encArg(x_162), encArg(x_262))) :|: x_159 >= 0, x_162 >= 0, x_329 >= 0, z' = 1 + x_159 + x_259 + x_329, z'' = 1 + x_162 + x_262, x_262 >= 0, x_259 >= 0 encode_g(z', z'') -{ 0 }-> g(f(encArg(x_159), encArg(x_259), encArg(x_329)), f(encArg(x_161), encArg(x_261), encArg(x_330))) :|: x_159 >= 0, x_329 >= 0, x_261 >= 0, z'' = 1 + x_161 + x_261 + x_330, z' = 1 + x_159 + x_259 + x_329, x_330 >= 0, x_259 >= 0, x_161 >= 0 encode_g(z', z'') -{ 0 }-> g(f(encArg(x_159), encArg(x_259), encArg(x_329)), 0) :|: x_159 >= 0, x_329 >= 0, z' = 1 + x_159 + x_259 + x_329, z'' >= 0, x_259 >= 0 encode_g(z', z'') -{ 0 }-> g(0, g(encArg(x_166), encArg(x_266))) :|: z' >= 0, x_166 >= 0, z'' = 1 + x_166 + x_266, x_266 >= 0 encode_g(z', z'') -{ 0 }-> g(0, f(encArg(x_165), encArg(x_265), encArg(x_332))) :|: x_332 >= 0, z' >= 0, x_265 >= 0, x_165 >= 0, z'' = 1 + x_165 + x_265 + x_332 encode_g(z', z'') -{ 0 }-> 0 :|: z' >= 0, z'' >= 0 encode_g(z', z'') -{ 0 }-> 0 :|: z' >= 0, z'' >= 0, v0 >= 0, v1 >= 0, 0 = v1, 0 = v0 encode_g(z', z'') -{ 0 }-> 1 + x0 + x1 :|: z' >= 0, z'' >= 0, 0 = x1, x0 >= 0, x1 >= 0, 0 = x0 f(z', z'', z1) -{ 2 }-> s :|: s >= 0, s <= 0, z1 >= 0, z' = 1 + z'' + y, z'' >= 0, y >= 0 f(z', z'', z1) -{ 0 }-> 0 :|: z' >= 0, z'' >= 0, z1 >= 0 g(z', z'') -{ 1 }-> z' :|: z' >= 0, z'' >= 0 g(z', z'') -{ 1 }-> z'' :|: z' >= 0, z'' >= 0 g(z', z'') -{ 0 }-> 0 :|: z' >= 0, z'' >= 0 g(z', z'') -{ 0 }-> 1 + z' + z'' :|: z' >= 0, z'' >= 0 Function symbols to be analyzed: {encode_f}, {encode_g} Previous analysis results are: g: runtime: O(1) [1], size: O(n^1) [1 + z' + z''] f: runtime: O(1) [1], size: O(1) [0] encArg: runtime: O(n^1) [1 + 4*z'], size: O(n^1) [1 + z'] ---------------------------------------- (41) ResultPropagationProof (UPPER BOUND(ID)) Applied inner abstraction using the recently inferred runtime/size bounds where possible. ---------------------------------------- (42) Obligation: Complexity RNTS consisting of the following rules: encArg(z') -{ 4 + 4*x_1 + 4*x_2 + 4*x_3 }-> s2 :|: s' >= 0, s' <= x_1 + 1, s'' >= 0, s'' <= x_2 + 1, s1 >= 0, s1 <= x_3 + 1, s2 >= 0, s2 <= 0, x_1 >= 0, z' = 1 + x_1 + x_2 + x_3, x_3 >= 0, x_2 >= 0 encArg(z') -{ 9 + 4*x_125 + 4*x_127 + 4*x_225 + 4*x_227 + 4*x_312 + 4*x_313 }-> s29 :|: s21 >= 0, s21 <= x_125 + 1, s22 >= 0, s22 <= x_225 + 1, s23 >= 0, s23 <= x_312 + 1, s24 >= 0, s24 <= 0, s25 >= 0, s25 <= x_127 + 1, s26 >= 0, s26 <= x_227 + 1, s27 >= 0, s27 <= x_313 + 1, s28 >= 0, s28 <= 0, s29 >= 0, s29 <= s24 + s28 + 1, x_127 >= 0, x_312 >= 0, z' = 1 + (1 + x_125 + x_225 + x_312) + (1 + x_127 + x_227 + x_313), x_125 >= 0, x_313 >= 0, x_225 >= 0, x_227 >= 0 encArg(z') -{ 8 + 4*x_125 + 4*x_128 + 4*x_225 + 4*x_228 + 4*x_312 }-> s37 :|: s30 >= 0, s30 <= x_125 + 1, s31 >= 0, s31 <= x_225 + 1, s32 >= 0, s32 <= x_312 + 1, s33 >= 0, s33 <= 0, s34 >= 0, s34 <= x_128 + 1, s35 >= 0, s35 <= x_228 + 1, s36 >= 0, s36 <= s34 + s35 + 1, s37 >= 0, s37 <= s33 + s36 + 1, x_128 >= 0, x_312 >= 0, z' = 1 + (1 + x_125 + x_225 + x_312) + (1 + x_128 + x_228), x_125 >= 0, x_225 >= 0, x_228 >= 0 encArg(z') -{ 5 + 4*x_125 + 4*x_225 + 4*x_312 }-> s42 :|: s38 >= 0, s38 <= x_125 + 1, s39 >= 0, s39 <= x_225 + 1, s40 >= 0, s40 <= x_312 + 1, s41 >= 0, s41 <= 0, s42 >= 0, s42 <= s41 + 0 + 1, x_312 >= 0, x_125 >= 0, x_225 >= 0, x_2 >= 0, z' = 1 + (1 + x_125 + x_225 + x_312) + x_2 encArg(z') -{ 8 + 4*x_126 + 4*x_129 + 4*x_226 + 4*x_229 + 4*x_314 }-> s50 :|: s43 >= 0, s43 <= x_126 + 1, s44 >= 0, s44 <= x_226 + 1, s45 >= 0, s45 <= s43 + s44 + 1, s46 >= 0, s46 <= x_129 + 1, s47 >= 0, s47 <= x_229 + 1, s48 >= 0, s48 <= x_314 + 1, s49 >= 0, s49 <= 0, s50 >= 0, s50 <= s45 + s49 + 1, x_226 >= 0, x_314 >= 0, x_126 >= 0, x_229 >= 0, x_129 >= 0, z' = 1 + (1 + x_126 + x_226) + (1 + x_129 + x_229 + x_314) encArg(z') -{ 4 + 4*x_126 + 4*x_226 }-> s54 :|: s51 >= 0, s51 <= x_126 + 1, s52 >= 0, s52 <= x_226 + 1, s53 >= 0, s53 <= s51 + s52 + 1, s54 >= 0, s54 <= s53 + 0 + 1, x_226 >= 0, z' = 1 + (1 + x_126 + x_226) + x_2, x_126 >= 0, x_2 >= 0 encArg(z') -{ 5 + 4*x_131 + 4*x_231 + 4*x_315 }-> s59 :|: s55 >= 0, s55 <= x_131 + 1, s56 >= 0, s56 <= x_231 + 1, s57 >= 0, s57 <= x_315 + 1, s58 >= 0, s58 <= 0, s59 >= 0, s59 <= 0 + s58 + 1, x_315 >= 0, x_1 >= 0, z' = 1 + x_1 + (1 + x_131 + x_231 + x_315), x_231 >= 0, x_131 >= 0 encArg(z') -{ 4 + 4*x_132 + 4*x_232 }-> s63 :|: s60 >= 0, s60 <= x_132 + 1, s61 >= 0, s61 <= x_232 + 1, s62 >= 0, s62 <= s60 + s61 + 1, s63 >= 0, s63 <= 0 + s62 + 1, x_1 >= 0, z' = 1 + x_1 + (1 + x_132 + x_232), x_232 >= 0, x_132 >= 0 encArg(z') -{ 7 + 4*x_126 + 4*x_130 + 4*x_226 + 4*x_230 }-> s9 :|: s3 >= 0, s3 <= x_126 + 1, s4 >= 0, s4 <= x_226 + 1, s5 >= 0, s5 <= s3 + s4 + 1, s6 >= 0, s6 <= x_130 + 1, s7 >= 0, s7 <= x_230 + 1, s8 >= 0, s8 <= s6 + s7 + 1, s9 >= 0, s9 <= s5 + s8 + 1, z' = 1 + (1 + x_126 + x_226) + (1 + x_130 + x_230), x_130 >= 0, x_226 >= 0, x_126 >= 0, x_230 >= 0 encArg(z') -{ 1 }-> x :|: x_1 >= 0, x_2 >= 0, z' = 1 + x_1 + x_2, 0 = x, 0 = y, x >= 0, y >= 0 encArg(z') -{ 1 }-> y :|: x_1 >= 0, x_2 >= 0, z' = 1 + x_1 + x_2, 0 = x, 0 = y, x >= 0, y >= 0 encArg(z') -{ 0 }-> 0 :|: z' >= 0 encArg(z') -{ 0 }-> 0 :|: x_1 >= 0, x_2 >= 0, z' = 1 + x_1 + x_2, v0 >= 0, v1 >= 0, 0 = v1, 0 = v0 encArg(z') -{ 0 }-> 1 + x0 + x1 :|: x_1 >= 0, x_2 >= 0, z' = 1 + x_1 + x_2, 0 = x1, x0 >= 0, x1 >= 0, 0 = x0 encode_f(z', z'', z1) -{ 4 + 4*z' + 4*z'' + 4*z1 }-> s13 :|: s10 >= 0, s10 <= z' + 1, s11 >= 0, s11 <= z'' + 1, s12 >= 0, s12 <= z1 + 1, s13 >= 0, s13 <= 0, z' >= 0, z1 >= 0, z'' >= 0 encode_f(z', z'', z1) -{ 0 }-> 0 :|: z' >= 0, z'' >= 0, z1 >= 0 encode_g(z', z'') -{ 5 + 4*x_165 + 4*x_265 + 4*x_332 }-> s102 :|: s98 >= 0, s98 <= x_165 + 1, s99 >= 0, s99 <= x_265 + 1, s100 >= 0, s100 <= x_332 + 1, s101 >= 0, s101 <= 0, s102 >= 0, s102 <= 0 + s101 + 1, x_332 >= 0, z' >= 0, x_265 >= 0, x_165 >= 0, z'' = 1 + x_165 + x_265 + x_332 encode_g(z', z'') -{ 4 + 4*x_166 + 4*x_266 }-> s106 :|: s103 >= 0, s103 <= x_166 + 1, s104 >= 0, s104 <= x_266 + 1, s105 >= 0, s105 <= s103 + s104 + 1, s106 >= 0, s106 <= 0 + s105 + 1, z' >= 0, x_166 >= 0, z'' = 1 + x_166 + x_266, x_266 >= 0 encode_g(z', z'') -{ 7 + 4*x_160 + 4*x_164 + 4*x_260 + 4*x_264 }-> s20 :|: s14 >= 0, s14 <= x_160 + 1, s15 >= 0, s15 <= x_260 + 1, s16 >= 0, s16 <= s14 + s15 + 1, s17 >= 0, s17 <= x_164 + 1, s18 >= 0, s18 <= x_264 + 1, s19 >= 0, s19 <= s17 + s18 + 1, s20 >= 0, s20 <= s16 + s19 + 1, x_264 >= 0, z' = 1 + x_160 + x_260, x_160 >= 0, x_164 >= 0, z'' = 1 + x_164 + x_264, x_260 >= 0 encode_g(z', z'') -{ 9 + 4*x_159 + 4*x_161 + 4*x_259 + 4*x_261 + 4*x_329 + 4*x_330 }-> s72 :|: s64 >= 0, s64 <= x_159 + 1, s65 >= 0, s65 <= x_259 + 1, s66 >= 0, s66 <= x_329 + 1, s67 >= 0, s67 <= 0, s68 >= 0, s68 <= x_161 + 1, s69 >= 0, s69 <= x_261 + 1, s70 >= 0, s70 <= x_330 + 1, s71 >= 0, s71 <= 0, s72 >= 0, s72 <= s67 + s71 + 1, x_159 >= 0, x_329 >= 0, x_261 >= 0, z'' = 1 + x_161 + x_261 + x_330, z' = 1 + x_159 + x_259 + x_329, x_330 >= 0, x_259 >= 0, x_161 >= 0 encode_g(z', z'') -{ 8 + 4*x_159 + 4*x_162 + 4*x_259 + 4*x_262 + 4*x_329 }-> s80 :|: s73 >= 0, s73 <= x_159 + 1, s74 >= 0, s74 <= x_259 + 1, s75 >= 0, s75 <= x_329 + 1, s76 >= 0, s76 <= 0, s77 >= 0, s77 <= x_162 + 1, s78 >= 0, s78 <= x_262 + 1, s79 >= 0, s79 <= s77 + s78 + 1, s80 >= 0, s80 <= s76 + s79 + 1, x_159 >= 0, x_162 >= 0, x_329 >= 0, z' = 1 + x_159 + x_259 + x_329, z'' = 1 + x_162 + x_262, x_262 >= 0, x_259 >= 0 encode_g(z', z'') -{ 5 + 4*x_159 + 4*x_259 + 4*x_329 }-> s85 :|: s81 >= 0, s81 <= x_159 + 1, s82 >= 0, s82 <= x_259 + 1, s83 >= 0, s83 <= x_329 + 1, s84 >= 0, s84 <= 0, s85 >= 0, s85 <= s84 + 0 + 1, x_159 >= 0, x_329 >= 0, z' = 1 + x_159 + x_259 + x_329, z'' >= 0, x_259 >= 0 encode_g(z', z'') -{ 8 + 4*x_160 + 4*x_163 + 4*x_260 + 4*x_263 + 4*x_331 }-> s93 :|: s86 >= 0, s86 <= x_160 + 1, s87 >= 0, s87 <= x_260 + 1, s88 >= 0, s88 <= s86 + s87 + 1, s89 >= 0, s89 <= x_163 + 1, s90 >= 0, s90 <= x_263 + 1, s91 >= 0, s91 <= x_331 + 1, s92 >= 0, s92 <= 0, s93 >= 0, s93 <= s88 + s92 + 1, x_331 >= 0, x_263 >= 0, z' = 1 + x_160 + x_260, x_160 >= 0, x_163 >= 0, z'' = 1 + x_163 + x_263 + x_331, x_260 >= 0 encode_g(z', z'') -{ 4 + 4*x_160 + 4*x_260 }-> s97 :|: s94 >= 0, s94 <= x_160 + 1, s95 >= 0, s95 <= x_260 + 1, s96 >= 0, s96 <= s94 + s95 + 1, s97 >= 0, s97 <= s96 + 0 + 1, z' = 1 + x_160 + x_260, x_160 >= 0, z'' >= 0, x_260 >= 0 encode_g(z', z'') -{ 1 }-> x :|: z' >= 0, z'' >= 0, 0 = x, 0 = y, x >= 0, y >= 0 encode_g(z', z'') -{ 1 }-> y :|: z' >= 0, z'' >= 0, 0 = x, 0 = y, x >= 0, y >= 0 encode_g(z', z'') -{ 0 }-> 0 :|: z' >= 0, z'' >= 0 encode_g(z', z'') -{ 0 }-> 0 :|: z' >= 0, z'' >= 0, v0 >= 0, v1 >= 0, 0 = v1, 0 = v0 encode_g(z', z'') -{ 0 }-> 1 + x0 + x1 :|: z' >= 0, z'' >= 0, 0 = x1, x0 >= 0, x1 >= 0, 0 = x0 f(z', z'', z1) -{ 2 }-> s :|: s >= 0, s <= 0, z1 >= 0, z' = 1 + z'' + y, z'' >= 0, y >= 0 f(z', z'', z1) -{ 0 }-> 0 :|: z' >= 0, z'' >= 0, z1 >= 0 g(z', z'') -{ 1 }-> z' :|: z' >= 0, z'' >= 0 g(z', z'') -{ 1 }-> z'' :|: z' >= 0, z'' >= 0 g(z', z'') -{ 0 }-> 0 :|: z' >= 0, z'' >= 0 g(z', z'') -{ 0 }-> 1 + z' + z'' :|: z' >= 0, z'' >= 0 Function symbols to be analyzed: {encode_f}, {encode_g} Previous analysis results are: g: runtime: O(1) [1], size: O(n^1) [1 + z' + z''] f: runtime: O(1) [1], size: O(1) [0] encArg: runtime: O(n^1) [1 + 4*z'], size: O(n^1) [1 + z'] ---------------------------------------- (43) 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 ---------------------------------------- (44) Obligation: Complexity RNTS consisting of the following rules: encArg(z') -{ 4 + 4*x_1 + 4*x_2 + 4*x_3 }-> s2 :|: s' >= 0, s' <= x_1 + 1, s'' >= 0, s'' <= x_2 + 1, s1 >= 0, s1 <= x_3 + 1, s2 >= 0, s2 <= 0, x_1 >= 0, z' = 1 + x_1 + x_2 + x_3, x_3 >= 0, x_2 >= 0 encArg(z') -{ 9 + 4*x_125 + 4*x_127 + 4*x_225 + 4*x_227 + 4*x_312 + 4*x_313 }-> s29 :|: s21 >= 0, s21 <= x_125 + 1, s22 >= 0, s22 <= x_225 + 1, s23 >= 0, s23 <= x_312 + 1, s24 >= 0, s24 <= 0, s25 >= 0, s25 <= x_127 + 1, s26 >= 0, s26 <= x_227 + 1, s27 >= 0, s27 <= x_313 + 1, s28 >= 0, s28 <= 0, s29 >= 0, s29 <= s24 + s28 + 1, x_127 >= 0, x_312 >= 0, z' = 1 + (1 + x_125 + x_225 + x_312) + (1 + x_127 + x_227 + x_313), x_125 >= 0, x_313 >= 0, x_225 >= 0, x_227 >= 0 encArg(z') -{ 8 + 4*x_125 + 4*x_128 + 4*x_225 + 4*x_228 + 4*x_312 }-> s37 :|: s30 >= 0, s30 <= x_125 + 1, s31 >= 0, s31 <= x_225 + 1, s32 >= 0, s32 <= x_312 + 1, s33 >= 0, s33 <= 0, s34 >= 0, s34 <= x_128 + 1, s35 >= 0, s35 <= x_228 + 1, s36 >= 0, s36 <= s34 + s35 + 1, s37 >= 0, s37 <= s33 + s36 + 1, x_128 >= 0, x_312 >= 0, z' = 1 + (1 + x_125 + x_225 + x_312) + (1 + x_128 + x_228), x_125 >= 0, x_225 >= 0, x_228 >= 0 encArg(z') -{ 5 + 4*x_125 + 4*x_225 + 4*x_312 }-> s42 :|: s38 >= 0, s38 <= x_125 + 1, s39 >= 0, s39 <= x_225 + 1, s40 >= 0, s40 <= x_312 + 1, s41 >= 0, s41 <= 0, s42 >= 0, s42 <= s41 + 0 + 1, x_312 >= 0, x_125 >= 0, x_225 >= 0, x_2 >= 0, z' = 1 + (1 + x_125 + x_225 + x_312) + x_2 encArg(z') -{ 8 + 4*x_126 + 4*x_129 + 4*x_226 + 4*x_229 + 4*x_314 }-> s50 :|: s43 >= 0, s43 <= x_126 + 1, s44 >= 0, s44 <= x_226 + 1, s45 >= 0, s45 <= s43 + s44 + 1, s46 >= 0, s46 <= x_129 + 1, s47 >= 0, s47 <= x_229 + 1, s48 >= 0, s48 <= x_314 + 1, s49 >= 0, s49 <= 0, s50 >= 0, s50 <= s45 + s49 + 1, x_226 >= 0, x_314 >= 0, x_126 >= 0, x_229 >= 0, x_129 >= 0, z' = 1 + (1 + x_126 + x_226) + (1 + x_129 + x_229 + x_314) encArg(z') -{ 4 + 4*x_126 + 4*x_226 }-> s54 :|: s51 >= 0, s51 <= x_126 + 1, s52 >= 0, s52 <= x_226 + 1, s53 >= 0, s53 <= s51 + s52 + 1, s54 >= 0, s54 <= s53 + 0 + 1, x_226 >= 0, z' = 1 + (1 + x_126 + x_226) + x_2, x_126 >= 0, x_2 >= 0 encArg(z') -{ 5 + 4*x_131 + 4*x_231 + 4*x_315 }-> s59 :|: s55 >= 0, s55 <= x_131 + 1, s56 >= 0, s56 <= x_231 + 1, s57 >= 0, s57 <= x_315 + 1, s58 >= 0, s58 <= 0, s59 >= 0, s59 <= 0 + s58 + 1, x_315 >= 0, x_1 >= 0, z' = 1 + x_1 + (1 + x_131 + x_231 + x_315), x_231 >= 0, x_131 >= 0 encArg(z') -{ 4 + 4*x_132 + 4*x_232 }-> s63 :|: s60 >= 0, s60 <= x_132 + 1, s61 >= 0, s61 <= x_232 + 1, s62 >= 0, s62 <= s60 + s61 + 1, s63 >= 0, s63 <= 0 + s62 + 1, x_1 >= 0, z' = 1 + x_1 + (1 + x_132 + x_232), x_232 >= 0, x_132 >= 0 encArg(z') -{ 7 + 4*x_126 + 4*x_130 + 4*x_226 + 4*x_230 }-> s9 :|: s3 >= 0, s3 <= x_126 + 1, s4 >= 0, s4 <= x_226 + 1, s5 >= 0, s5 <= s3 + s4 + 1, s6 >= 0, s6 <= x_130 + 1, s7 >= 0, s7 <= x_230 + 1, s8 >= 0, s8 <= s6 + s7 + 1, s9 >= 0, s9 <= s5 + s8 + 1, z' = 1 + (1 + x_126 + x_226) + (1 + x_130 + x_230), x_130 >= 0, x_226 >= 0, x_126 >= 0, x_230 >= 0 encArg(z') -{ 1 }-> x :|: x_1 >= 0, x_2 >= 0, z' = 1 + x_1 + x_2, 0 = x, 0 = y, x >= 0, y >= 0 encArg(z') -{ 1 }-> y :|: x_1 >= 0, x_2 >= 0, z' = 1 + x_1 + x_2, 0 = x, 0 = y, x >= 0, y >= 0 encArg(z') -{ 0 }-> 0 :|: z' >= 0 encArg(z') -{ 0 }-> 0 :|: x_1 >= 0, x_2 >= 0, z' = 1 + x_1 + x_2, v0 >= 0, v1 >= 0, 0 = v1, 0 = v0 encArg(z') -{ 0 }-> 1 + x0 + x1 :|: x_1 >= 0, x_2 >= 0, z' = 1 + x_1 + x_2, 0 = x1, x0 >= 0, x1 >= 0, 0 = x0 encode_f(z', z'', z1) -{ 4 + 4*z' + 4*z'' + 4*z1 }-> s13 :|: s10 >= 0, s10 <= z' + 1, s11 >= 0, s11 <= z'' + 1, s12 >= 0, s12 <= z1 + 1, s13 >= 0, s13 <= 0, z' >= 0, z1 >= 0, z'' >= 0 encode_f(z', z'', z1) -{ 0 }-> 0 :|: z' >= 0, z'' >= 0, z1 >= 0 encode_g(z', z'') -{ 5 + 4*x_165 + 4*x_265 + 4*x_332 }-> s102 :|: s98 >= 0, s98 <= x_165 + 1, s99 >= 0, s99 <= x_265 + 1, s100 >= 0, s100 <= x_332 + 1, s101 >= 0, s101 <= 0, s102 >= 0, s102 <= 0 + s101 + 1, x_332 >= 0, z' >= 0, x_265 >= 0, x_165 >= 0, z'' = 1 + x_165 + x_265 + x_332 encode_g(z', z'') -{ 4 + 4*x_166 + 4*x_266 }-> s106 :|: s103 >= 0, s103 <= x_166 + 1, s104 >= 0, s104 <= x_266 + 1, s105 >= 0, s105 <= s103 + s104 + 1, s106 >= 0, s106 <= 0 + s105 + 1, z' >= 0, x_166 >= 0, z'' = 1 + x_166 + x_266, x_266 >= 0 encode_g(z', z'') -{ 7 + 4*x_160 + 4*x_164 + 4*x_260 + 4*x_264 }-> s20 :|: s14 >= 0, s14 <= x_160 + 1, s15 >= 0, s15 <= x_260 + 1, s16 >= 0, s16 <= s14 + s15 + 1, s17 >= 0, s17 <= x_164 + 1, s18 >= 0, s18 <= x_264 + 1, s19 >= 0, s19 <= s17 + s18 + 1, s20 >= 0, s20 <= s16 + s19 + 1, x_264 >= 0, z' = 1 + x_160 + x_260, x_160 >= 0, x_164 >= 0, z'' = 1 + x_164 + x_264, x_260 >= 0 encode_g(z', z'') -{ 9 + 4*x_159 + 4*x_161 + 4*x_259 + 4*x_261 + 4*x_329 + 4*x_330 }-> s72 :|: s64 >= 0, s64 <= x_159 + 1, s65 >= 0, s65 <= x_259 + 1, s66 >= 0, s66 <= x_329 + 1, s67 >= 0, s67 <= 0, s68 >= 0, s68 <= x_161 + 1, s69 >= 0, s69 <= x_261 + 1, s70 >= 0, s70 <= x_330 + 1, s71 >= 0, s71 <= 0, s72 >= 0, s72 <= s67 + s71 + 1, x_159 >= 0, x_329 >= 0, x_261 >= 0, z'' = 1 + x_161 + x_261 + x_330, z' = 1 + x_159 + x_259 + x_329, x_330 >= 0, x_259 >= 0, x_161 >= 0 encode_g(z', z'') -{ 8 + 4*x_159 + 4*x_162 + 4*x_259 + 4*x_262 + 4*x_329 }-> s80 :|: s73 >= 0, s73 <= x_159 + 1, s74 >= 0, s74 <= x_259 + 1, s75 >= 0, s75 <= x_329 + 1, s76 >= 0, s76 <= 0, s77 >= 0, s77 <= x_162 + 1, s78 >= 0, s78 <= x_262 + 1, s79 >= 0, s79 <= s77 + s78 + 1, s80 >= 0, s80 <= s76 + s79 + 1, x_159 >= 0, x_162 >= 0, x_329 >= 0, z' = 1 + x_159 + x_259 + x_329, z'' = 1 + x_162 + x_262, x_262 >= 0, x_259 >= 0 encode_g(z', z'') -{ 5 + 4*x_159 + 4*x_259 + 4*x_329 }-> s85 :|: s81 >= 0, s81 <= x_159 + 1, s82 >= 0, s82 <= x_259 + 1, s83 >= 0, s83 <= x_329 + 1, s84 >= 0, s84 <= 0, s85 >= 0, s85 <= s84 + 0 + 1, x_159 >= 0, x_329 >= 0, z' = 1 + x_159 + x_259 + x_329, z'' >= 0, x_259 >= 0 encode_g(z', z'') -{ 8 + 4*x_160 + 4*x_163 + 4*x_260 + 4*x_263 + 4*x_331 }-> s93 :|: s86 >= 0, s86 <= x_160 + 1, s87 >= 0, s87 <= x_260 + 1, s88 >= 0, s88 <= s86 + s87 + 1, s89 >= 0, s89 <= x_163 + 1, s90 >= 0, s90 <= x_263 + 1, s91 >= 0, s91 <= x_331 + 1, s92 >= 0, s92 <= 0, s93 >= 0, s93 <= s88 + s92 + 1, x_331 >= 0, x_263 >= 0, z' = 1 + x_160 + x_260, x_160 >= 0, x_163 >= 0, z'' = 1 + x_163 + x_263 + x_331, x_260 >= 0 encode_g(z', z'') -{ 4 + 4*x_160 + 4*x_260 }-> s97 :|: s94 >= 0, s94 <= x_160 + 1, s95 >= 0, s95 <= x_260 + 1, s96 >= 0, s96 <= s94 + s95 + 1, s97 >= 0, s97 <= s96 + 0 + 1, z' = 1 + x_160 + x_260, x_160 >= 0, z'' >= 0, x_260 >= 0 encode_g(z', z'') -{ 1 }-> x :|: z' >= 0, z'' >= 0, 0 = x, 0 = y, x >= 0, y >= 0 encode_g(z', z'') -{ 1 }-> y :|: z' >= 0, z'' >= 0, 0 = x, 0 = y, x >= 0, y >= 0 encode_g(z', z'') -{ 0 }-> 0 :|: z' >= 0, z'' >= 0 encode_g(z', z'') -{ 0 }-> 0 :|: z' >= 0, z'' >= 0, v0 >= 0, v1 >= 0, 0 = v1, 0 = v0 encode_g(z', z'') -{ 0 }-> 1 + x0 + x1 :|: z' >= 0, z'' >= 0, 0 = x1, x0 >= 0, x1 >= 0, 0 = x0 f(z', z'', z1) -{ 2 }-> s :|: s >= 0, s <= 0, z1 >= 0, z' = 1 + z'' + y, z'' >= 0, y >= 0 f(z', z'', z1) -{ 0 }-> 0 :|: z' >= 0, z'' >= 0, z1 >= 0 g(z', z'') -{ 1 }-> z' :|: z' >= 0, z'' >= 0 g(z', z'') -{ 1 }-> z'' :|: z' >= 0, z'' >= 0 g(z', z'') -{ 0 }-> 0 :|: z' >= 0, z'' >= 0 g(z', z'') -{ 0 }-> 1 + z' + z'' :|: z' >= 0, z'' >= 0 Function symbols to be analyzed: {encode_f}, {encode_g} Previous analysis results are: g: runtime: O(1) [1], size: O(n^1) [1 + z' + z''] f: runtime: O(1) [1], size: O(1) [0] encArg: runtime: O(n^1) [1 + 4*z'], size: O(n^1) [1 + z'] encode_f: runtime: ?, size: O(1) [0] ---------------------------------------- (45) 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: 4 + 4*z' + 4*z'' + 4*z1 ---------------------------------------- (46) Obligation: Complexity RNTS consisting of the following rules: encArg(z') -{ 4 + 4*x_1 + 4*x_2 + 4*x_3 }-> s2 :|: s' >= 0, s' <= x_1 + 1, s'' >= 0, s'' <= x_2 + 1, s1 >= 0, s1 <= x_3 + 1, s2 >= 0, s2 <= 0, x_1 >= 0, z' = 1 + x_1 + x_2 + x_3, x_3 >= 0, x_2 >= 0 encArg(z') -{ 9 + 4*x_125 + 4*x_127 + 4*x_225 + 4*x_227 + 4*x_312 + 4*x_313 }-> s29 :|: s21 >= 0, s21 <= x_125 + 1, s22 >= 0, s22 <= x_225 + 1, s23 >= 0, s23 <= x_312 + 1, s24 >= 0, s24 <= 0, s25 >= 0, s25 <= x_127 + 1, s26 >= 0, s26 <= x_227 + 1, s27 >= 0, s27 <= x_313 + 1, s28 >= 0, s28 <= 0, s29 >= 0, s29 <= s24 + s28 + 1, x_127 >= 0, x_312 >= 0, z' = 1 + (1 + x_125 + x_225 + x_312) + (1 + x_127 + x_227 + x_313), x_125 >= 0, x_313 >= 0, x_225 >= 0, x_227 >= 0 encArg(z') -{ 8 + 4*x_125 + 4*x_128 + 4*x_225 + 4*x_228 + 4*x_312 }-> s37 :|: s30 >= 0, s30 <= x_125 + 1, s31 >= 0, s31 <= x_225 + 1, s32 >= 0, s32 <= x_312 + 1, s33 >= 0, s33 <= 0, s34 >= 0, s34 <= x_128 + 1, s35 >= 0, s35 <= x_228 + 1, s36 >= 0, s36 <= s34 + s35 + 1, s37 >= 0, s37 <= s33 + s36 + 1, x_128 >= 0, x_312 >= 0, z' = 1 + (1 + x_125 + x_225 + x_312) + (1 + x_128 + x_228), x_125 >= 0, x_225 >= 0, x_228 >= 0 encArg(z') -{ 5 + 4*x_125 + 4*x_225 + 4*x_312 }-> s42 :|: s38 >= 0, s38 <= x_125 + 1, s39 >= 0, s39 <= x_225 + 1, s40 >= 0, s40 <= x_312 + 1, s41 >= 0, s41 <= 0, s42 >= 0, s42 <= s41 + 0 + 1, x_312 >= 0, x_125 >= 0, x_225 >= 0, x_2 >= 0, z' = 1 + (1 + x_125 + x_225 + x_312) + x_2 encArg(z') -{ 8 + 4*x_126 + 4*x_129 + 4*x_226 + 4*x_229 + 4*x_314 }-> s50 :|: s43 >= 0, s43 <= x_126 + 1, s44 >= 0, s44 <= x_226 + 1, s45 >= 0, s45 <= s43 + s44 + 1, s46 >= 0, s46 <= x_129 + 1, s47 >= 0, s47 <= x_229 + 1, s48 >= 0, s48 <= x_314 + 1, s49 >= 0, s49 <= 0, s50 >= 0, s50 <= s45 + s49 + 1, x_226 >= 0, x_314 >= 0, x_126 >= 0, x_229 >= 0, x_129 >= 0, z' = 1 + (1 + x_126 + x_226) + (1 + x_129 + x_229 + x_314) encArg(z') -{ 4 + 4*x_126 + 4*x_226 }-> s54 :|: s51 >= 0, s51 <= x_126 + 1, s52 >= 0, s52 <= x_226 + 1, s53 >= 0, s53 <= s51 + s52 + 1, s54 >= 0, s54 <= s53 + 0 + 1, x_226 >= 0, z' = 1 + (1 + x_126 + x_226) + x_2, x_126 >= 0, x_2 >= 0 encArg(z') -{ 5 + 4*x_131 + 4*x_231 + 4*x_315 }-> s59 :|: s55 >= 0, s55 <= x_131 + 1, s56 >= 0, s56 <= x_231 + 1, s57 >= 0, s57 <= x_315 + 1, s58 >= 0, s58 <= 0, s59 >= 0, s59 <= 0 + s58 + 1, x_315 >= 0, x_1 >= 0, z' = 1 + x_1 + (1 + x_131 + x_231 + x_315), x_231 >= 0, x_131 >= 0 encArg(z') -{ 4 + 4*x_132 + 4*x_232 }-> s63 :|: s60 >= 0, s60 <= x_132 + 1, s61 >= 0, s61 <= x_232 + 1, s62 >= 0, s62 <= s60 + s61 + 1, s63 >= 0, s63 <= 0 + s62 + 1, x_1 >= 0, z' = 1 + x_1 + (1 + x_132 + x_232), x_232 >= 0, x_132 >= 0 encArg(z') -{ 7 + 4*x_126 + 4*x_130 + 4*x_226 + 4*x_230 }-> s9 :|: s3 >= 0, s3 <= x_126 + 1, s4 >= 0, s4 <= x_226 + 1, s5 >= 0, s5 <= s3 + s4 + 1, s6 >= 0, s6 <= x_130 + 1, s7 >= 0, s7 <= x_230 + 1, s8 >= 0, s8 <= s6 + s7 + 1, s9 >= 0, s9 <= s5 + s8 + 1, z' = 1 + (1 + x_126 + x_226) + (1 + x_130 + x_230), x_130 >= 0, x_226 >= 0, x_126 >= 0, x_230 >= 0 encArg(z') -{ 1 }-> x :|: x_1 >= 0, x_2 >= 0, z' = 1 + x_1 + x_2, 0 = x, 0 = y, x >= 0, y >= 0 encArg(z') -{ 1 }-> y :|: x_1 >= 0, x_2 >= 0, z' = 1 + x_1 + x_2, 0 = x, 0 = y, x >= 0, y >= 0 encArg(z') -{ 0 }-> 0 :|: z' >= 0 encArg(z') -{ 0 }-> 0 :|: x_1 >= 0, x_2 >= 0, z' = 1 + x_1 + x_2, v0 >= 0, v1 >= 0, 0 = v1, 0 = v0 encArg(z') -{ 0 }-> 1 + x0 + x1 :|: x_1 >= 0, x_2 >= 0, z' = 1 + x_1 + x_2, 0 = x1, x0 >= 0, x1 >= 0, 0 = x0 encode_f(z', z'', z1) -{ 4 + 4*z' + 4*z'' + 4*z1 }-> s13 :|: s10 >= 0, s10 <= z' + 1, s11 >= 0, s11 <= z'' + 1, s12 >= 0, s12 <= z1 + 1, s13 >= 0, s13 <= 0, z' >= 0, z1 >= 0, z'' >= 0 encode_f(z', z'', z1) -{ 0 }-> 0 :|: z' >= 0, z'' >= 0, z1 >= 0 encode_g(z', z'') -{ 5 + 4*x_165 + 4*x_265 + 4*x_332 }-> s102 :|: s98 >= 0, s98 <= x_165 + 1, s99 >= 0, s99 <= x_265 + 1, s100 >= 0, s100 <= x_332 + 1, s101 >= 0, s101 <= 0, s102 >= 0, s102 <= 0 + s101 + 1, x_332 >= 0, z' >= 0, x_265 >= 0, x_165 >= 0, z'' = 1 + x_165 + x_265 + x_332 encode_g(z', z'') -{ 4 + 4*x_166 + 4*x_266 }-> s106 :|: s103 >= 0, s103 <= x_166 + 1, s104 >= 0, s104 <= x_266 + 1, s105 >= 0, s105 <= s103 + s104 + 1, s106 >= 0, s106 <= 0 + s105 + 1, z' >= 0, x_166 >= 0, z'' = 1 + x_166 + x_266, x_266 >= 0 encode_g(z', z'') -{ 7 + 4*x_160 + 4*x_164 + 4*x_260 + 4*x_264 }-> s20 :|: s14 >= 0, s14 <= x_160 + 1, s15 >= 0, s15 <= x_260 + 1, s16 >= 0, s16 <= s14 + s15 + 1, s17 >= 0, s17 <= x_164 + 1, s18 >= 0, s18 <= x_264 + 1, s19 >= 0, s19 <= s17 + s18 + 1, s20 >= 0, s20 <= s16 + s19 + 1, x_264 >= 0, z' = 1 + x_160 + x_260, x_160 >= 0, x_164 >= 0, z'' = 1 + x_164 + x_264, x_260 >= 0 encode_g(z', z'') -{ 9 + 4*x_159 + 4*x_161 + 4*x_259 + 4*x_261 + 4*x_329 + 4*x_330 }-> s72 :|: s64 >= 0, s64 <= x_159 + 1, s65 >= 0, s65 <= x_259 + 1, s66 >= 0, s66 <= x_329 + 1, s67 >= 0, s67 <= 0, s68 >= 0, s68 <= x_161 + 1, s69 >= 0, s69 <= x_261 + 1, s70 >= 0, s70 <= x_330 + 1, s71 >= 0, s71 <= 0, s72 >= 0, s72 <= s67 + s71 + 1, x_159 >= 0, x_329 >= 0, x_261 >= 0, z'' = 1 + x_161 + x_261 + x_330, z' = 1 + x_159 + x_259 + x_329, x_330 >= 0, x_259 >= 0, x_161 >= 0 encode_g(z', z'') -{ 8 + 4*x_159 + 4*x_162 + 4*x_259 + 4*x_262 + 4*x_329 }-> s80 :|: s73 >= 0, s73 <= x_159 + 1, s74 >= 0, s74 <= x_259 + 1, s75 >= 0, s75 <= x_329 + 1, s76 >= 0, s76 <= 0, s77 >= 0, s77 <= x_162 + 1, s78 >= 0, s78 <= x_262 + 1, s79 >= 0, s79 <= s77 + s78 + 1, s80 >= 0, s80 <= s76 + s79 + 1, x_159 >= 0, x_162 >= 0, x_329 >= 0, z' = 1 + x_159 + x_259 + x_329, z'' = 1 + x_162 + x_262, x_262 >= 0, x_259 >= 0 encode_g(z', z'') -{ 5 + 4*x_159 + 4*x_259 + 4*x_329 }-> s85 :|: s81 >= 0, s81 <= x_159 + 1, s82 >= 0, s82 <= x_259 + 1, s83 >= 0, s83 <= x_329 + 1, s84 >= 0, s84 <= 0, s85 >= 0, s85 <= s84 + 0 + 1, x_159 >= 0, x_329 >= 0, z' = 1 + x_159 + x_259 + x_329, z'' >= 0, x_259 >= 0 encode_g(z', z'') -{ 8 + 4*x_160 + 4*x_163 + 4*x_260 + 4*x_263 + 4*x_331 }-> s93 :|: s86 >= 0, s86 <= x_160 + 1, s87 >= 0, s87 <= x_260 + 1, s88 >= 0, s88 <= s86 + s87 + 1, s89 >= 0, s89 <= x_163 + 1, s90 >= 0, s90 <= x_263 + 1, s91 >= 0, s91 <= x_331 + 1, s92 >= 0, s92 <= 0, s93 >= 0, s93 <= s88 + s92 + 1, x_331 >= 0, x_263 >= 0, z' = 1 + x_160 + x_260, x_160 >= 0, x_163 >= 0, z'' = 1 + x_163 + x_263 + x_331, x_260 >= 0 encode_g(z', z'') -{ 4 + 4*x_160 + 4*x_260 }-> s97 :|: s94 >= 0, s94 <= x_160 + 1, s95 >= 0, s95 <= x_260 + 1, s96 >= 0, s96 <= s94 + s95 + 1, s97 >= 0, s97 <= s96 + 0 + 1, z' = 1 + x_160 + x_260, x_160 >= 0, z'' >= 0, x_260 >= 0 encode_g(z', z'') -{ 1 }-> x :|: z' >= 0, z'' >= 0, 0 = x, 0 = y, x >= 0, y >= 0 encode_g(z', z'') -{ 1 }-> y :|: z' >= 0, z'' >= 0, 0 = x, 0 = y, x >= 0, y >= 0 encode_g(z', z'') -{ 0 }-> 0 :|: z' >= 0, z'' >= 0 encode_g(z', z'') -{ 0 }-> 0 :|: z' >= 0, z'' >= 0, v0 >= 0, v1 >= 0, 0 = v1, 0 = v0 encode_g(z', z'') -{ 0 }-> 1 + x0 + x1 :|: z' >= 0, z'' >= 0, 0 = x1, x0 >= 0, x1 >= 0, 0 = x0 f(z', z'', z1) -{ 2 }-> s :|: s >= 0, s <= 0, z1 >= 0, z' = 1 + z'' + y, z'' >= 0, y >= 0 f(z', z'', z1) -{ 0 }-> 0 :|: z' >= 0, z'' >= 0, z1 >= 0 g(z', z'') -{ 1 }-> z' :|: z' >= 0, z'' >= 0 g(z', z'') -{ 1 }-> z'' :|: z' >= 0, z'' >= 0 g(z', z'') -{ 0 }-> 0 :|: z' >= 0, z'' >= 0 g(z', z'') -{ 0 }-> 1 + z' + z'' :|: z' >= 0, z'' >= 0 Function symbols to be analyzed: {encode_g} Previous analysis results are: g: runtime: O(1) [1], size: O(n^1) [1 + z' + z''] f: runtime: O(1) [1], size: O(1) [0] encArg: runtime: O(n^1) [1 + 4*z'], size: O(n^1) [1 + z'] encode_f: runtime: O(n^1) [4 + 4*z' + 4*z'' + 4*z1], size: O(1) [0] ---------------------------------------- (47) ResultPropagationProof (UPPER BOUND(ID)) Applied inner abstraction using the recently inferred runtime/size bounds where possible. ---------------------------------------- (48) Obligation: Complexity RNTS consisting of the following rules: encArg(z') -{ 4 + 4*x_1 + 4*x_2 + 4*x_3 }-> s2 :|: s' >= 0, s' <= x_1 + 1, s'' >= 0, s'' <= x_2 + 1, s1 >= 0, s1 <= x_3 + 1, s2 >= 0, s2 <= 0, x_1 >= 0, z' = 1 + x_1 + x_2 + x_3, x_3 >= 0, x_2 >= 0 encArg(z') -{ 9 + 4*x_125 + 4*x_127 + 4*x_225 + 4*x_227 + 4*x_312 + 4*x_313 }-> s29 :|: s21 >= 0, s21 <= x_125 + 1, s22 >= 0, s22 <= x_225 + 1, s23 >= 0, s23 <= x_312 + 1, s24 >= 0, s24 <= 0, s25 >= 0, s25 <= x_127 + 1, s26 >= 0, s26 <= x_227 + 1, s27 >= 0, s27 <= x_313 + 1, s28 >= 0, s28 <= 0, s29 >= 0, s29 <= s24 + s28 + 1, x_127 >= 0, x_312 >= 0, z' = 1 + (1 + x_125 + x_225 + x_312) + (1 + x_127 + x_227 + x_313), x_125 >= 0, x_313 >= 0, x_225 >= 0, x_227 >= 0 encArg(z') -{ 8 + 4*x_125 + 4*x_128 + 4*x_225 + 4*x_228 + 4*x_312 }-> s37 :|: s30 >= 0, s30 <= x_125 + 1, s31 >= 0, s31 <= x_225 + 1, s32 >= 0, s32 <= x_312 + 1, s33 >= 0, s33 <= 0, s34 >= 0, s34 <= x_128 + 1, s35 >= 0, s35 <= x_228 + 1, s36 >= 0, s36 <= s34 + s35 + 1, s37 >= 0, s37 <= s33 + s36 + 1, x_128 >= 0, x_312 >= 0, z' = 1 + (1 + x_125 + x_225 + x_312) + (1 + x_128 + x_228), x_125 >= 0, x_225 >= 0, x_228 >= 0 encArg(z') -{ 5 + 4*x_125 + 4*x_225 + 4*x_312 }-> s42 :|: s38 >= 0, s38 <= x_125 + 1, s39 >= 0, s39 <= x_225 + 1, s40 >= 0, s40 <= x_312 + 1, s41 >= 0, s41 <= 0, s42 >= 0, s42 <= s41 + 0 + 1, x_312 >= 0, x_125 >= 0, x_225 >= 0, x_2 >= 0, z' = 1 + (1 + x_125 + x_225 + x_312) + x_2 encArg(z') -{ 8 + 4*x_126 + 4*x_129 + 4*x_226 + 4*x_229 + 4*x_314 }-> s50 :|: s43 >= 0, s43 <= x_126 + 1, s44 >= 0, s44 <= x_226 + 1, s45 >= 0, s45 <= s43 + s44 + 1, s46 >= 0, s46 <= x_129 + 1, s47 >= 0, s47 <= x_229 + 1, s48 >= 0, s48 <= x_314 + 1, s49 >= 0, s49 <= 0, s50 >= 0, s50 <= s45 + s49 + 1, x_226 >= 0, x_314 >= 0, x_126 >= 0, x_229 >= 0, x_129 >= 0, z' = 1 + (1 + x_126 + x_226) + (1 + x_129 + x_229 + x_314) encArg(z') -{ 4 + 4*x_126 + 4*x_226 }-> s54 :|: s51 >= 0, s51 <= x_126 + 1, s52 >= 0, s52 <= x_226 + 1, s53 >= 0, s53 <= s51 + s52 + 1, s54 >= 0, s54 <= s53 + 0 + 1, x_226 >= 0, z' = 1 + (1 + x_126 + x_226) + x_2, x_126 >= 0, x_2 >= 0 encArg(z') -{ 5 + 4*x_131 + 4*x_231 + 4*x_315 }-> s59 :|: s55 >= 0, s55 <= x_131 + 1, s56 >= 0, s56 <= x_231 + 1, s57 >= 0, s57 <= x_315 + 1, s58 >= 0, s58 <= 0, s59 >= 0, s59 <= 0 + s58 + 1, x_315 >= 0, x_1 >= 0, z' = 1 + x_1 + (1 + x_131 + x_231 + x_315), x_231 >= 0, x_131 >= 0 encArg(z') -{ 4 + 4*x_132 + 4*x_232 }-> s63 :|: s60 >= 0, s60 <= x_132 + 1, s61 >= 0, s61 <= x_232 + 1, s62 >= 0, s62 <= s60 + s61 + 1, s63 >= 0, s63 <= 0 + s62 + 1, x_1 >= 0, z' = 1 + x_1 + (1 + x_132 + x_232), x_232 >= 0, x_132 >= 0 encArg(z') -{ 7 + 4*x_126 + 4*x_130 + 4*x_226 + 4*x_230 }-> s9 :|: s3 >= 0, s3 <= x_126 + 1, s4 >= 0, s4 <= x_226 + 1, s5 >= 0, s5 <= s3 + s4 + 1, s6 >= 0, s6 <= x_130 + 1, s7 >= 0, s7 <= x_230 + 1, s8 >= 0, s8 <= s6 + s7 + 1, s9 >= 0, s9 <= s5 + s8 + 1, z' = 1 + (1 + x_126 + x_226) + (1 + x_130 + x_230), x_130 >= 0, x_226 >= 0, x_126 >= 0, x_230 >= 0 encArg(z') -{ 1 }-> x :|: x_1 >= 0, x_2 >= 0, z' = 1 + x_1 + x_2, 0 = x, 0 = y, x >= 0, y >= 0 encArg(z') -{ 1 }-> y :|: x_1 >= 0, x_2 >= 0, z' = 1 + x_1 + x_2, 0 = x, 0 = y, x >= 0, y >= 0 encArg(z') -{ 0 }-> 0 :|: z' >= 0 encArg(z') -{ 0 }-> 0 :|: x_1 >= 0, x_2 >= 0, z' = 1 + x_1 + x_2, v0 >= 0, v1 >= 0, 0 = v1, 0 = v0 encArg(z') -{ 0 }-> 1 + x0 + x1 :|: x_1 >= 0, x_2 >= 0, z' = 1 + x_1 + x_2, 0 = x1, x0 >= 0, x1 >= 0, 0 = x0 encode_f(z', z'', z1) -{ 4 + 4*z' + 4*z'' + 4*z1 }-> s13 :|: s10 >= 0, s10 <= z' + 1, s11 >= 0, s11 <= z'' + 1, s12 >= 0, s12 <= z1 + 1, s13 >= 0, s13 <= 0, z' >= 0, z1 >= 0, z'' >= 0 encode_f(z', z'', z1) -{ 0 }-> 0 :|: z' >= 0, z'' >= 0, z1 >= 0 encode_g(z', z'') -{ 5 + 4*x_165 + 4*x_265 + 4*x_332 }-> s102 :|: s98 >= 0, s98 <= x_165 + 1, s99 >= 0, s99 <= x_265 + 1, s100 >= 0, s100 <= x_332 + 1, s101 >= 0, s101 <= 0, s102 >= 0, s102 <= 0 + s101 + 1, x_332 >= 0, z' >= 0, x_265 >= 0, x_165 >= 0, z'' = 1 + x_165 + x_265 + x_332 encode_g(z', z'') -{ 4 + 4*x_166 + 4*x_266 }-> s106 :|: s103 >= 0, s103 <= x_166 + 1, s104 >= 0, s104 <= x_266 + 1, s105 >= 0, s105 <= s103 + s104 + 1, s106 >= 0, s106 <= 0 + s105 + 1, z' >= 0, x_166 >= 0, z'' = 1 + x_166 + x_266, x_266 >= 0 encode_g(z', z'') -{ 7 + 4*x_160 + 4*x_164 + 4*x_260 + 4*x_264 }-> s20 :|: s14 >= 0, s14 <= x_160 + 1, s15 >= 0, s15 <= x_260 + 1, s16 >= 0, s16 <= s14 + s15 + 1, s17 >= 0, s17 <= x_164 + 1, s18 >= 0, s18 <= x_264 + 1, s19 >= 0, s19 <= s17 + s18 + 1, s20 >= 0, s20 <= s16 + s19 + 1, x_264 >= 0, z' = 1 + x_160 + x_260, x_160 >= 0, x_164 >= 0, z'' = 1 + x_164 + x_264, x_260 >= 0 encode_g(z', z'') -{ 9 + 4*x_159 + 4*x_161 + 4*x_259 + 4*x_261 + 4*x_329 + 4*x_330 }-> s72 :|: s64 >= 0, s64 <= x_159 + 1, s65 >= 0, s65 <= x_259 + 1, s66 >= 0, s66 <= x_329 + 1, s67 >= 0, s67 <= 0, s68 >= 0, s68 <= x_161 + 1, s69 >= 0, s69 <= x_261 + 1, s70 >= 0, s70 <= x_330 + 1, s71 >= 0, s71 <= 0, s72 >= 0, s72 <= s67 + s71 + 1, x_159 >= 0, x_329 >= 0, x_261 >= 0, z'' = 1 + x_161 + x_261 + x_330, z' = 1 + x_159 + x_259 + x_329, x_330 >= 0, x_259 >= 0, x_161 >= 0 encode_g(z', z'') -{ 8 + 4*x_159 + 4*x_162 + 4*x_259 + 4*x_262 + 4*x_329 }-> s80 :|: s73 >= 0, s73 <= x_159 + 1, s74 >= 0, s74 <= x_259 + 1, s75 >= 0, s75 <= x_329 + 1, s76 >= 0, s76 <= 0, s77 >= 0, s77 <= x_162 + 1, s78 >= 0, s78 <= x_262 + 1, s79 >= 0, s79 <= s77 + s78 + 1, s80 >= 0, s80 <= s76 + s79 + 1, x_159 >= 0, x_162 >= 0, x_329 >= 0, z' = 1 + x_159 + x_259 + x_329, z'' = 1 + x_162 + x_262, x_262 >= 0, x_259 >= 0 encode_g(z', z'') -{ 5 + 4*x_159 + 4*x_259 + 4*x_329 }-> s85 :|: s81 >= 0, s81 <= x_159 + 1, s82 >= 0, s82 <= x_259 + 1, s83 >= 0, s83 <= x_329 + 1, s84 >= 0, s84 <= 0, s85 >= 0, s85 <= s84 + 0 + 1, x_159 >= 0, x_329 >= 0, z' = 1 + x_159 + x_259 + x_329, z'' >= 0, x_259 >= 0 encode_g(z', z'') -{ 8 + 4*x_160 + 4*x_163 + 4*x_260 + 4*x_263 + 4*x_331 }-> s93 :|: s86 >= 0, s86 <= x_160 + 1, s87 >= 0, s87 <= x_260 + 1, s88 >= 0, s88 <= s86 + s87 + 1, s89 >= 0, s89 <= x_163 + 1, s90 >= 0, s90 <= x_263 + 1, s91 >= 0, s91 <= x_331 + 1, s92 >= 0, s92 <= 0, s93 >= 0, s93 <= s88 + s92 + 1, x_331 >= 0, x_263 >= 0, z' = 1 + x_160 + x_260, x_160 >= 0, x_163 >= 0, z'' = 1 + x_163 + x_263 + x_331, x_260 >= 0 encode_g(z', z'') -{ 4 + 4*x_160 + 4*x_260 }-> s97 :|: s94 >= 0, s94 <= x_160 + 1, s95 >= 0, s95 <= x_260 + 1, s96 >= 0, s96 <= s94 + s95 + 1, s97 >= 0, s97 <= s96 + 0 + 1, z' = 1 + x_160 + x_260, x_160 >= 0, z'' >= 0, x_260 >= 0 encode_g(z', z'') -{ 1 }-> x :|: z' >= 0, z'' >= 0, 0 = x, 0 = y, x >= 0, y >= 0 encode_g(z', z'') -{ 1 }-> y :|: z' >= 0, z'' >= 0, 0 = x, 0 = y, x >= 0, y >= 0 encode_g(z', z'') -{ 0 }-> 0 :|: z' >= 0, z'' >= 0 encode_g(z', z'') -{ 0 }-> 0 :|: z' >= 0, z'' >= 0, v0 >= 0, v1 >= 0, 0 = v1, 0 = v0 encode_g(z', z'') -{ 0 }-> 1 + x0 + x1 :|: z' >= 0, z'' >= 0, 0 = x1, x0 >= 0, x1 >= 0, 0 = x0 f(z', z'', z1) -{ 2 }-> s :|: s >= 0, s <= 0, z1 >= 0, z' = 1 + z'' + y, z'' >= 0, y >= 0 f(z', z'', z1) -{ 0 }-> 0 :|: z' >= 0, z'' >= 0, z1 >= 0 g(z', z'') -{ 1 }-> z' :|: z' >= 0, z'' >= 0 g(z', z'') -{ 1 }-> z'' :|: z' >= 0, z'' >= 0 g(z', z'') -{ 0 }-> 0 :|: z' >= 0, z'' >= 0 g(z', z'') -{ 0 }-> 1 + z' + z'' :|: z' >= 0, z'' >= 0 Function symbols to be analyzed: {encode_g} Previous analysis results are: g: runtime: O(1) [1], size: O(n^1) [1 + z' + z''] f: runtime: O(1) [1], size: O(1) [0] encArg: runtime: O(n^1) [1 + 4*z'], size: O(n^1) [1 + z'] encode_f: runtime: O(n^1) [4 + 4*z' + 4*z'' + 4*z1], size: O(1) [0] ---------------------------------------- (49) 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: 5 + z' + z'' ---------------------------------------- (50) Obligation: Complexity RNTS consisting of the following rules: encArg(z') -{ 4 + 4*x_1 + 4*x_2 + 4*x_3 }-> s2 :|: s' >= 0, s' <= x_1 + 1, s'' >= 0, s'' <= x_2 + 1, s1 >= 0, s1 <= x_3 + 1, s2 >= 0, s2 <= 0, x_1 >= 0, z' = 1 + x_1 + x_2 + x_3, x_3 >= 0, x_2 >= 0 encArg(z') -{ 9 + 4*x_125 + 4*x_127 + 4*x_225 + 4*x_227 + 4*x_312 + 4*x_313 }-> s29 :|: s21 >= 0, s21 <= x_125 + 1, s22 >= 0, s22 <= x_225 + 1, s23 >= 0, s23 <= x_312 + 1, s24 >= 0, s24 <= 0, s25 >= 0, s25 <= x_127 + 1, s26 >= 0, s26 <= x_227 + 1, s27 >= 0, s27 <= x_313 + 1, s28 >= 0, s28 <= 0, s29 >= 0, s29 <= s24 + s28 + 1, x_127 >= 0, x_312 >= 0, z' = 1 + (1 + x_125 + x_225 + x_312) + (1 + x_127 + x_227 + x_313), x_125 >= 0, x_313 >= 0, x_225 >= 0, x_227 >= 0 encArg(z') -{ 8 + 4*x_125 + 4*x_128 + 4*x_225 + 4*x_228 + 4*x_312 }-> s37 :|: s30 >= 0, s30 <= x_125 + 1, s31 >= 0, s31 <= x_225 + 1, s32 >= 0, s32 <= x_312 + 1, s33 >= 0, s33 <= 0, s34 >= 0, s34 <= x_128 + 1, s35 >= 0, s35 <= x_228 + 1, s36 >= 0, s36 <= s34 + s35 + 1, s37 >= 0, s37 <= s33 + s36 + 1, x_128 >= 0, x_312 >= 0, z' = 1 + (1 + x_125 + x_225 + x_312) + (1 + x_128 + x_228), x_125 >= 0, x_225 >= 0, x_228 >= 0 encArg(z') -{ 5 + 4*x_125 + 4*x_225 + 4*x_312 }-> s42 :|: s38 >= 0, s38 <= x_125 + 1, s39 >= 0, s39 <= x_225 + 1, s40 >= 0, s40 <= x_312 + 1, s41 >= 0, s41 <= 0, s42 >= 0, s42 <= s41 + 0 + 1, x_312 >= 0, x_125 >= 0, x_225 >= 0, x_2 >= 0, z' = 1 + (1 + x_125 + x_225 + x_312) + x_2 encArg(z') -{ 8 + 4*x_126 + 4*x_129 + 4*x_226 + 4*x_229 + 4*x_314 }-> s50 :|: s43 >= 0, s43 <= x_126 + 1, s44 >= 0, s44 <= x_226 + 1, s45 >= 0, s45 <= s43 + s44 + 1, s46 >= 0, s46 <= x_129 + 1, s47 >= 0, s47 <= x_229 + 1, s48 >= 0, s48 <= x_314 + 1, s49 >= 0, s49 <= 0, s50 >= 0, s50 <= s45 + s49 + 1, x_226 >= 0, x_314 >= 0, x_126 >= 0, x_229 >= 0, x_129 >= 0, z' = 1 + (1 + x_126 + x_226) + (1 + x_129 + x_229 + x_314) encArg(z') -{ 4 + 4*x_126 + 4*x_226 }-> s54 :|: s51 >= 0, s51 <= x_126 + 1, s52 >= 0, s52 <= x_226 + 1, s53 >= 0, s53 <= s51 + s52 + 1, s54 >= 0, s54 <= s53 + 0 + 1, x_226 >= 0, z' = 1 + (1 + x_126 + x_226) + x_2, x_126 >= 0, x_2 >= 0 encArg(z') -{ 5 + 4*x_131 + 4*x_231 + 4*x_315 }-> s59 :|: s55 >= 0, s55 <= x_131 + 1, s56 >= 0, s56 <= x_231 + 1, s57 >= 0, s57 <= x_315 + 1, s58 >= 0, s58 <= 0, s59 >= 0, s59 <= 0 + s58 + 1, x_315 >= 0, x_1 >= 0, z' = 1 + x_1 + (1 + x_131 + x_231 + x_315), x_231 >= 0, x_131 >= 0 encArg(z') -{ 4 + 4*x_132 + 4*x_232 }-> s63 :|: s60 >= 0, s60 <= x_132 + 1, s61 >= 0, s61 <= x_232 + 1, s62 >= 0, s62 <= s60 + s61 + 1, s63 >= 0, s63 <= 0 + s62 + 1, x_1 >= 0, z' = 1 + x_1 + (1 + x_132 + x_232), x_232 >= 0, x_132 >= 0 encArg(z') -{ 7 + 4*x_126 + 4*x_130 + 4*x_226 + 4*x_230 }-> s9 :|: s3 >= 0, s3 <= x_126 + 1, s4 >= 0, s4 <= x_226 + 1, s5 >= 0, s5 <= s3 + s4 + 1, s6 >= 0, s6 <= x_130 + 1, s7 >= 0, s7 <= x_230 + 1, s8 >= 0, s8 <= s6 + s7 + 1, s9 >= 0, s9 <= s5 + s8 + 1, z' = 1 + (1 + x_126 + x_226) + (1 + x_130 + x_230), x_130 >= 0, x_226 >= 0, x_126 >= 0, x_230 >= 0 encArg(z') -{ 1 }-> x :|: x_1 >= 0, x_2 >= 0, z' = 1 + x_1 + x_2, 0 = x, 0 = y, x >= 0, y >= 0 encArg(z') -{ 1 }-> y :|: x_1 >= 0, x_2 >= 0, z' = 1 + x_1 + x_2, 0 = x, 0 = y, x >= 0, y >= 0 encArg(z') -{ 0 }-> 0 :|: z' >= 0 encArg(z') -{ 0 }-> 0 :|: x_1 >= 0, x_2 >= 0, z' = 1 + x_1 + x_2, v0 >= 0, v1 >= 0, 0 = v1, 0 = v0 encArg(z') -{ 0 }-> 1 + x0 + x1 :|: x_1 >= 0, x_2 >= 0, z' = 1 + x_1 + x_2, 0 = x1, x0 >= 0, x1 >= 0, 0 = x0 encode_f(z', z'', z1) -{ 4 + 4*z' + 4*z'' + 4*z1 }-> s13 :|: s10 >= 0, s10 <= z' + 1, s11 >= 0, s11 <= z'' + 1, s12 >= 0, s12 <= z1 + 1, s13 >= 0, s13 <= 0, z' >= 0, z1 >= 0, z'' >= 0 encode_f(z', z'', z1) -{ 0 }-> 0 :|: z' >= 0, z'' >= 0, z1 >= 0 encode_g(z', z'') -{ 5 + 4*x_165 + 4*x_265 + 4*x_332 }-> s102 :|: s98 >= 0, s98 <= x_165 + 1, s99 >= 0, s99 <= x_265 + 1, s100 >= 0, s100 <= x_332 + 1, s101 >= 0, s101 <= 0, s102 >= 0, s102 <= 0 + s101 + 1, x_332 >= 0, z' >= 0, x_265 >= 0, x_165 >= 0, z'' = 1 + x_165 + x_265 + x_332 encode_g(z', z'') -{ 4 + 4*x_166 + 4*x_266 }-> s106 :|: s103 >= 0, s103 <= x_166 + 1, s104 >= 0, s104 <= x_266 + 1, s105 >= 0, s105 <= s103 + s104 + 1, s106 >= 0, s106 <= 0 + s105 + 1, z' >= 0, x_166 >= 0, z'' = 1 + x_166 + x_266, x_266 >= 0 encode_g(z', z'') -{ 7 + 4*x_160 + 4*x_164 + 4*x_260 + 4*x_264 }-> s20 :|: s14 >= 0, s14 <= x_160 + 1, s15 >= 0, s15 <= x_260 + 1, s16 >= 0, s16 <= s14 + s15 + 1, s17 >= 0, s17 <= x_164 + 1, s18 >= 0, s18 <= x_264 + 1, s19 >= 0, s19 <= s17 + s18 + 1, s20 >= 0, s20 <= s16 + s19 + 1, x_264 >= 0, z' = 1 + x_160 + x_260, x_160 >= 0, x_164 >= 0, z'' = 1 + x_164 + x_264, x_260 >= 0 encode_g(z', z'') -{ 9 + 4*x_159 + 4*x_161 + 4*x_259 + 4*x_261 + 4*x_329 + 4*x_330 }-> s72 :|: s64 >= 0, s64 <= x_159 + 1, s65 >= 0, s65 <= x_259 + 1, s66 >= 0, s66 <= x_329 + 1, s67 >= 0, s67 <= 0, s68 >= 0, s68 <= x_161 + 1, s69 >= 0, s69 <= x_261 + 1, s70 >= 0, s70 <= x_330 + 1, s71 >= 0, s71 <= 0, s72 >= 0, s72 <= s67 + s71 + 1, x_159 >= 0, x_329 >= 0, x_261 >= 0, z'' = 1 + x_161 + x_261 + x_330, z' = 1 + x_159 + x_259 + x_329, x_330 >= 0, x_259 >= 0, x_161 >= 0 encode_g(z', z'') -{ 8 + 4*x_159 + 4*x_162 + 4*x_259 + 4*x_262 + 4*x_329 }-> s80 :|: s73 >= 0, s73 <= x_159 + 1, s74 >= 0, s74 <= x_259 + 1, s75 >= 0, s75 <= x_329 + 1, s76 >= 0, s76 <= 0, s77 >= 0, s77 <= x_162 + 1, s78 >= 0, s78 <= x_262 + 1, s79 >= 0, s79 <= s77 + s78 + 1, s80 >= 0, s80 <= s76 + s79 + 1, x_159 >= 0, x_162 >= 0, x_329 >= 0, z' = 1 + x_159 + x_259 + x_329, z'' = 1 + x_162 + x_262, x_262 >= 0, x_259 >= 0 encode_g(z', z'') -{ 5 + 4*x_159 + 4*x_259 + 4*x_329 }-> s85 :|: s81 >= 0, s81 <= x_159 + 1, s82 >= 0, s82 <= x_259 + 1, s83 >= 0, s83 <= x_329 + 1, s84 >= 0, s84 <= 0, s85 >= 0, s85 <= s84 + 0 + 1, x_159 >= 0, x_329 >= 0, z' = 1 + x_159 + x_259 + x_329, z'' >= 0, x_259 >= 0 encode_g(z', z'') -{ 8 + 4*x_160 + 4*x_163 + 4*x_260 + 4*x_263 + 4*x_331 }-> s93 :|: s86 >= 0, s86 <= x_160 + 1, s87 >= 0, s87 <= x_260 + 1, s88 >= 0, s88 <= s86 + s87 + 1, s89 >= 0, s89 <= x_163 + 1, s90 >= 0, s90 <= x_263 + 1, s91 >= 0, s91 <= x_331 + 1, s92 >= 0, s92 <= 0, s93 >= 0, s93 <= s88 + s92 + 1, x_331 >= 0, x_263 >= 0, z' = 1 + x_160 + x_260, x_160 >= 0, x_163 >= 0, z'' = 1 + x_163 + x_263 + x_331, x_260 >= 0 encode_g(z', z'') -{ 4 + 4*x_160 + 4*x_260 }-> s97 :|: s94 >= 0, s94 <= x_160 + 1, s95 >= 0, s95 <= x_260 + 1, s96 >= 0, s96 <= s94 + s95 + 1, s97 >= 0, s97 <= s96 + 0 + 1, z' = 1 + x_160 + x_260, x_160 >= 0, z'' >= 0, x_260 >= 0 encode_g(z', z'') -{ 1 }-> x :|: z' >= 0, z'' >= 0, 0 = x, 0 = y, x >= 0, y >= 0 encode_g(z', z'') -{ 1 }-> y :|: z' >= 0, z'' >= 0, 0 = x, 0 = y, x >= 0, y >= 0 encode_g(z', z'') -{ 0 }-> 0 :|: z' >= 0, z'' >= 0 encode_g(z', z'') -{ 0 }-> 0 :|: z' >= 0, z'' >= 0, v0 >= 0, v1 >= 0, 0 = v1, 0 = v0 encode_g(z', z'') -{ 0 }-> 1 + x0 + x1 :|: z' >= 0, z'' >= 0, 0 = x1, x0 >= 0, x1 >= 0, 0 = x0 f(z', z'', z1) -{ 2 }-> s :|: s >= 0, s <= 0, z1 >= 0, z' = 1 + z'' + y, z'' >= 0, y >= 0 f(z', z'', z1) -{ 0 }-> 0 :|: z' >= 0, z'' >= 0, z1 >= 0 g(z', z'') -{ 1 }-> z' :|: z' >= 0, z'' >= 0 g(z', z'') -{ 1 }-> z'' :|: z' >= 0, z'' >= 0 g(z', z'') -{ 0 }-> 0 :|: z' >= 0, z'' >= 0 g(z', z'') -{ 0 }-> 1 + z' + z'' :|: z' >= 0, z'' >= 0 Function symbols to be analyzed: {encode_g} Previous analysis results are: g: runtime: O(1) [1], size: O(n^1) [1 + z' + z''] f: runtime: O(1) [1], size: O(1) [0] encArg: runtime: O(n^1) [1 + 4*z'], size: O(n^1) [1 + z'] encode_f: runtime: O(n^1) [4 + 4*z' + 4*z'' + 4*z1], size: O(1) [0] encode_g: runtime: ?, size: O(n^1) [5 + z' + z''] ---------------------------------------- (51) 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: 1 + 4*z' + 4*z'' ---------------------------------------- (52) Obligation: Complexity RNTS consisting of the following rules: encArg(z') -{ 4 + 4*x_1 + 4*x_2 + 4*x_3 }-> s2 :|: s' >= 0, s' <= x_1 + 1, s'' >= 0, s'' <= x_2 + 1, s1 >= 0, s1 <= x_3 + 1, s2 >= 0, s2 <= 0, x_1 >= 0, z' = 1 + x_1 + x_2 + x_3, x_3 >= 0, x_2 >= 0 encArg(z') -{ 9 + 4*x_125 + 4*x_127 + 4*x_225 + 4*x_227 + 4*x_312 + 4*x_313 }-> s29 :|: s21 >= 0, s21 <= x_125 + 1, s22 >= 0, s22 <= x_225 + 1, s23 >= 0, s23 <= x_312 + 1, s24 >= 0, s24 <= 0, s25 >= 0, s25 <= x_127 + 1, s26 >= 0, s26 <= x_227 + 1, s27 >= 0, s27 <= x_313 + 1, s28 >= 0, s28 <= 0, s29 >= 0, s29 <= s24 + s28 + 1, x_127 >= 0, x_312 >= 0, z' = 1 + (1 + x_125 + x_225 + x_312) + (1 + x_127 + x_227 + x_313), x_125 >= 0, x_313 >= 0, x_225 >= 0, x_227 >= 0 encArg(z') -{ 8 + 4*x_125 + 4*x_128 + 4*x_225 + 4*x_228 + 4*x_312 }-> s37 :|: s30 >= 0, s30 <= x_125 + 1, s31 >= 0, s31 <= x_225 + 1, s32 >= 0, s32 <= x_312 + 1, s33 >= 0, s33 <= 0, s34 >= 0, s34 <= x_128 + 1, s35 >= 0, s35 <= x_228 + 1, s36 >= 0, s36 <= s34 + s35 + 1, s37 >= 0, s37 <= s33 + s36 + 1, x_128 >= 0, x_312 >= 0, z' = 1 + (1 + x_125 + x_225 + x_312) + (1 + x_128 + x_228), x_125 >= 0, x_225 >= 0, x_228 >= 0 encArg(z') -{ 5 + 4*x_125 + 4*x_225 + 4*x_312 }-> s42 :|: s38 >= 0, s38 <= x_125 + 1, s39 >= 0, s39 <= x_225 + 1, s40 >= 0, s40 <= x_312 + 1, s41 >= 0, s41 <= 0, s42 >= 0, s42 <= s41 + 0 + 1, x_312 >= 0, x_125 >= 0, x_225 >= 0, x_2 >= 0, z' = 1 + (1 + x_125 + x_225 + x_312) + x_2 encArg(z') -{ 8 + 4*x_126 + 4*x_129 + 4*x_226 + 4*x_229 + 4*x_314 }-> s50 :|: s43 >= 0, s43 <= x_126 + 1, s44 >= 0, s44 <= x_226 + 1, s45 >= 0, s45 <= s43 + s44 + 1, s46 >= 0, s46 <= x_129 + 1, s47 >= 0, s47 <= x_229 + 1, s48 >= 0, s48 <= x_314 + 1, s49 >= 0, s49 <= 0, s50 >= 0, s50 <= s45 + s49 + 1, x_226 >= 0, x_314 >= 0, x_126 >= 0, x_229 >= 0, x_129 >= 0, z' = 1 + (1 + x_126 + x_226) + (1 + x_129 + x_229 + x_314) encArg(z') -{ 4 + 4*x_126 + 4*x_226 }-> s54 :|: s51 >= 0, s51 <= x_126 + 1, s52 >= 0, s52 <= x_226 + 1, s53 >= 0, s53 <= s51 + s52 + 1, s54 >= 0, s54 <= s53 + 0 + 1, x_226 >= 0, z' = 1 + (1 + x_126 + x_226) + x_2, x_126 >= 0, x_2 >= 0 encArg(z') -{ 5 + 4*x_131 + 4*x_231 + 4*x_315 }-> s59 :|: s55 >= 0, s55 <= x_131 + 1, s56 >= 0, s56 <= x_231 + 1, s57 >= 0, s57 <= x_315 + 1, s58 >= 0, s58 <= 0, s59 >= 0, s59 <= 0 + s58 + 1, x_315 >= 0, x_1 >= 0, z' = 1 + x_1 + (1 + x_131 + x_231 + x_315), x_231 >= 0, x_131 >= 0 encArg(z') -{ 4 + 4*x_132 + 4*x_232 }-> s63 :|: s60 >= 0, s60 <= x_132 + 1, s61 >= 0, s61 <= x_232 + 1, s62 >= 0, s62 <= s60 + s61 + 1, s63 >= 0, s63 <= 0 + s62 + 1, x_1 >= 0, z' = 1 + x_1 + (1 + x_132 + x_232), x_232 >= 0, x_132 >= 0 encArg(z') -{ 7 + 4*x_126 + 4*x_130 + 4*x_226 + 4*x_230 }-> s9 :|: s3 >= 0, s3 <= x_126 + 1, s4 >= 0, s4 <= x_226 + 1, s5 >= 0, s5 <= s3 + s4 + 1, s6 >= 0, s6 <= x_130 + 1, s7 >= 0, s7 <= x_230 + 1, s8 >= 0, s8 <= s6 + s7 + 1, s9 >= 0, s9 <= s5 + s8 + 1, z' = 1 + (1 + x_126 + x_226) + (1 + x_130 + x_230), x_130 >= 0, x_226 >= 0, x_126 >= 0, x_230 >= 0 encArg(z') -{ 1 }-> x :|: x_1 >= 0, x_2 >= 0, z' = 1 + x_1 + x_2, 0 = x, 0 = y, x >= 0, y >= 0 encArg(z') -{ 1 }-> y :|: x_1 >= 0, x_2 >= 0, z' = 1 + x_1 + x_2, 0 = x, 0 = y, x >= 0, y >= 0 encArg(z') -{ 0 }-> 0 :|: z' >= 0 encArg(z') -{ 0 }-> 0 :|: x_1 >= 0, x_2 >= 0, z' = 1 + x_1 + x_2, v0 >= 0, v1 >= 0, 0 = v1, 0 = v0 encArg(z') -{ 0 }-> 1 + x0 + x1 :|: x_1 >= 0, x_2 >= 0, z' = 1 + x_1 + x_2, 0 = x1, x0 >= 0, x1 >= 0, 0 = x0 encode_f(z', z'', z1) -{ 4 + 4*z' + 4*z'' + 4*z1 }-> s13 :|: s10 >= 0, s10 <= z' + 1, s11 >= 0, s11 <= z'' + 1, s12 >= 0, s12 <= z1 + 1, s13 >= 0, s13 <= 0, z' >= 0, z1 >= 0, z'' >= 0 encode_f(z', z'', z1) -{ 0 }-> 0 :|: z' >= 0, z'' >= 0, z1 >= 0 encode_g(z', z'') -{ 5 + 4*x_165 + 4*x_265 + 4*x_332 }-> s102 :|: s98 >= 0, s98 <= x_165 + 1, s99 >= 0, s99 <= x_265 + 1, s100 >= 0, s100 <= x_332 + 1, s101 >= 0, s101 <= 0, s102 >= 0, s102 <= 0 + s101 + 1, x_332 >= 0, z' >= 0, x_265 >= 0, x_165 >= 0, z'' = 1 + x_165 + x_265 + x_332 encode_g(z', z'') -{ 4 + 4*x_166 + 4*x_266 }-> s106 :|: s103 >= 0, s103 <= x_166 + 1, s104 >= 0, s104 <= x_266 + 1, s105 >= 0, s105 <= s103 + s104 + 1, s106 >= 0, s106 <= 0 + s105 + 1, z' >= 0, x_166 >= 0, z'' = 1 + x_166 + x_266, x_266 >= 0 encode_g(z', z'') -{ 7 + 4*x_160 + 4*x_164 + 4*x_260 + 4*x_264 }-> s20 :|: s14 >= 0, s14 <= x_160 + 1, s15 >= 0, s15 <= x_260 + 1, s16 >= 0, s16 <= s14 + s15 + 1, s17 >= 0, s17 <= x_164 + 1, s18 >= 0, s18 <= x_264 + 1, s19 >= 0, s19 <= s17 + s18 + 1, s20 >= 0, s20 <= s16 + s19 + 1, x_264 >= 0, z' = 1 + x_160 + x_260, x_160 >= 0, x_164 >= 0, z'' = 1 + x_164 + x_264, x_260 >= 0 encode_g(z', z'') -{ 9 + 4*x_159 + 4*x_161 + 4*x_259 + 4*x_261 + 4*x_329 + 4*x_330 }-> s72 :|: s64 >= 0, s64 <= x_159 + 1, s65 >= 0, s65 <= x_259 + 1, s66 >= 0, s66 <= x_329 + 1, s67 >= 0, s67 <= 0, s68 >= 0, s68 <= x_161 + 1, s69 >= 0, s69 <= x_261 + 1, s70 >= 0, s70 <= x_330 + 1, s71 >= 0, s71 <= 0, s72 >= 0, s72 <= s67 + s71 + 1, x_159 >= 0, x_329 >= 0, x_261 >= 0, z'' = 1 + x_161 + x_261 + x_330, z' = 1 + x_159 + x_259 + x_329, x_330 >= 0, x_259 >= 0, x_161 >= 0 encode_g(z', z'') -{ 8 + 4*x_159 + 4*x_162 + 4*x_259 + 4*x_262 + 4*x_329 }-> s80 :|: s73 >= 0, s73 <= x_159 + 1, s74 >= 0, s74 <= x_259 + 1, s75 >= 0, s75 <= x_329 + 1, s76 >= 0, s76 <= 0, s77 >= 0, s77 <= x_162 + 1, s78 >= 0, s78 <= x_262 + 1, s79 >= 0, s79 <= s77 + s78 + 1, s80 >= 0, s80 <= s76 + s79 + 1, x_159 >= 0, x_162 >= 0, x_329 >= 0, z' = 1 + x_159 + x_259 + x_329, z'' = 1 + x_162 + x_262, x_262 >= 0, x_259 >= 0 encode_g(z', z'') -{ 5 + 4*x_159 + 4*x_259 + 4*x_329 }-> s85 :|: s81 >= 0, s81 <= x_159 + 1, s82 >= 0, s82 <= x_259 + 1, s83 >= 0, s83 <= x_329 + 1, s84 >= 0, s84 <= 0, s85 >= 0, s85 <= s84 + 0 + 1, x_159 >= 0, x_329 >= 0, z' = 1 + x_159 + x_259 + x_329, z'' >= 0, x_259 >= 0 encode_g(z', z'') -{ 8 + 4*x_160 + 4*x_163 + 4*x_260 + 4*x_263 + 4*x_331 }-> s93 :|: s86 >= 0, s86 <= x_160 + 1, s87 >= 0, s87 <= x_260 + 1, s88 >= 0, s88 <= s86 + s87 + 1, s89 >= 0, s89 <= x_163 + 1, s90 >= 0, s90 <= x_263 + 1, s91 >= 0, s91 <= x_331 + 1, s92 >= 0, s92 <= 0, s93 >= 0, s93 <= s88 + s92 + 1, x_331 >= 0, x_263 >= 0, z' = 1 + x_160 + x_260, x_160 >= 0, x_163 >= 0, z'' = 1 + x_163 + x_263 + x_331, x_260 >= 0 encode_g(z', z'') -{ 4 + 4*x_160 + 4*x_260 }-> s97 :|: s94 >= 0, s94 <= x_160 + 1, s95 >= 0, s95 <= x_260 + 1, s96 >= 0, s96 <= s94 + s95 + 1, s97 >= 0, s97 <= s96 + 0 + 1, z' = 1 + x_160 + x_260, x_160 >= 0, z'' >= 0, x_260 >= 0 encode_g(z', z'') -{ 1 }-> x :|: z' >= 0, z'' >= 0, 0 = x, 0 = y, x >= 0, y >= 0 encode_g(z', z'') -{ 1 }-> y :|: z' >= 0, z'' >= 0, 0 = x, 0 = y, x >= 0, y >= 0 encode_g(z', z'') -{ 0 }-> 0 :|: z' >= 0, z'' >= 0 encode_g(z', z'') -{ 0 }-> 0 :|: z' >= 0, z'' >= 0, v0 >= 0, v1 >= 0, 0 = v1, 0 = v0 encode_g(z', z'') -{ 0 }-> 1 + x0 + x1 :|: z' >= 0, z'' >= 0, 0 = x1, x0 >= 0, x1 >= 0, 0 = x0 f(z', z'', z1) -{ 2 }-> s :|: s >= 0, s <= 0, z1 >= 0, z' = 1 + z'' + y, z'' >= 0, y >= 0 f(z', z'', z1) -{ 0 }-> 0 :|: z' >= 0, z'' >= 0, z1 >= 0 g(z', z'') -{ 1 }-> z' :|: z' >= 0, z'' >= 0 g(z', z'') -{ 1 }-> z'' :|: z' >= 0, z'' >= 0 g(z', z'') -{ 0 }-> 0 :|: z' >= 0, z'' >= 0 g(z', z'') -{ 0 }-> 1 + z' + z'' :|: z' >= 0, z'' >= 0 Function symbols to be analyzed: Previous analysis results are: g: runtime: O(1) [1], size: O(n^1) [1 + z' + z''] f: runtime: O(1) [1], size: O(1) [0] encArg: runtime: O(n^1) [1 + 4*z'], size: O(n^1) [1 + z'] encode_f: runtime: O(n^1) [4 + 4*z' + 4*z'' + 4*z1], size: O(1) [0] encode_g: runtime: O(n^1) [1 + 4*z' + 4*z''], size: O(n^1) [5 + z' + z''] ---------------------------------------- (53) FinalProof (FINISHED) Computed overall runtime complexity ---------------------------------------- (54) BOUNDS(1, n^1)