/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), 142 ms] (4) CpxRelTRS (5) RelTrsToWeightedTrsProof [BOTH BOUNDS(ID, ID), 0 ms] (6) CpxWeightedTrs (7) TypeInferenceProof [BOTH BOUNDS(ID, ID), 0 ms] (8) CpxTypedWeightedTrs (9) CompletionProof [UPPER BOUND(ID), 0 ms] (10) CpxTypedWeightedCompleteTrs (11) NarrowingProof [BOTH BOUNDS(ID, ID), 0 ms] (12) CpxTypedWeightedCompleteTrs (13) CpxTypedWeightedTrsToRntsProof [UPPER BOUND(ID), 0 ms] (14) CpxRNTS (15) InliningProof [UPPER BOUND(ID), 242 ms] (16) CpxRNTS (17) SimplificationProof [BOTH BOUNDS(ID, ID), 0 ms] (18) CpxRNTS (19) CpxRntsAnalysisOrderProof [BOTH BOUNDS(ID, ID), 0 ms] (20) CpxRNTS (21) ResultPropagationProof [UPPER BOUND(ID), 0 ms] (22) CpxRNTS (23) IntTrsBoundProof [UPPER BOUND(ID), 185 ms] (24) CpxRNTS (25) IntTrsBoundProof [UPPER BOUND(ID), 55 ms] (26) CpxRNTS (27) ResultPropagationProof [UPPER BOUND(ID), 0 ms] (28) CpxRNTS (29) IntTrsBoundProof [UPPER BOUND(ID), 168 ms] (30) CpxRNTS (31) IntTrsBoundProof [UPPER BOUND(ID), 63 ms] (32) CpxRNTS (33) ResultPropagationProof [UPPER BOUND(ID), 0 ms] (34) CpxRNTS (35) IntTrsBoundProof [UPPER BOUND(ID), 993 ms] (36) CpxRNTS (37) IntTrsBoundProof [UPPER BOUND(ID), 1442 ms] (38) CpxRNTS (39) ResultPropagationProof [UPPER BOUND(ID), 0 ms] (40) CpxRNTS (41) IntTrsBoundProof [UPPER BOUND(ID), 542 ms] (42) CpxRNTS (43) IntTrsBoundProof [UPPER BOUND(ID), 587 ms] (44) CpxRNTS (45) ResultPropagationProof [UPPER BOUND(ID), 0 ms] (46) CpxRNTS (47) IntTrsBoundProof [UPPER BOUND(ID), 552 ms] (48) CpxRNTS (49) IntTrsBoundProof [UPPER BOUND(ID), 543 ms] (50) CpxRNTS (51) FinalProof [FINISHED, 0 ms] (52) BOUNDS(1, n^1) ---------------------------------------- (0) Obligation: The Derivational Complexity (innermost) of the given DCpxTrs could be proven to be BOUNDS(1, n^1). The TRS R consists of the following rules: f(x, y) -> h(x, y) f(x, y) -> h(y, x) h(x, x) -> x S is empty. Rewrite Strategy: INNERMOST ---------------------------------------- (1) DerivationalComplexityToRuntimeComplexityProof (BOTH BOUNDS(ID, ID)) The following rules have been added to S to convert the given derivational complexity problem to a runtime complexity problem: encArg(cons_f(x_1, x_2)) -> f(encArg(x_1), encArg(x_2)) encArg(cons_h(x_1, x_2)) -> h(encArg(x_1), encArg(x_2)) encode_f(x_1, x_2) -> f(encArg(x_1), encArg(x_2)) encode_h(x_1, x_2) -> h(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(x, y) -> h(x, y) f(x, y) -> h(y, x) h(x, x) -> x The (relative) TRS S consists of the following rules: encArg(cons_f(x_1, x_2)) -> f(encArg(x_1), encArg(x_2)) encArg(cons_h(x_1, x_2)) -> h(encArg(x_1), encArg(x_2)) encode_f(x_1, x_2) -> f(encArg(x_1), encArg(x_2)) encode_h(x_1, x_2) -> h(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(x, y) -> h(x, y) f(x, y) -> h(y, x) h(x, x) -> x The (relative) TRS S consists of the following rules: encArg(cons_f(x_1, x_2)) -> f(encArg(x_1), encArg(x_2)) encArg(cons_h(x_1, x_2)) -> h(encArg(x_1), encArg(x_2)) encode_f(x_1, x_2) -> f(encArg(x_1), encArg(x_2)) encode_h(x_1, x_2) -> h(encArg(x_1), encArg(x_2)) Rewrite Strategy: INNERMOST ---------------------------------------- (5) RelTrsToWeightedTrsProof (BOTH BOUNDS(ID, ID)) Transformed relative TRS to weighted TRS ---------------------------------------- (6) Obligation: The Runtime Complexity (innermost) of the given CpxWeightedTrs could be proven to be BOUNDS(1, n^1). The TRS R consists of the following rules: f(x, y) -> h(x, y) [1] f(x, y) -> h(y, x) [1] h(x, x) -> x [1] encArg(cons_f(x_1, x_2)) -> f(encArg(x_1), encArg(x_2)) [0] encArg(cons_h(x_1, x_2)) -> h(encArg(x_1), encArg(x_2)) [0] encode_f(x_1, x_2) -> f(encArg(x_1), encArg(x_2)) [0] encode_h(x_1, x_2) -> h(encArg(x_1), encArg(x_2)) [0] Rewrite Strategy: INNERMOST ---------------------------------------- (7) TypeInferenceProof (BOTH BOUNDS(ID, ID)) Infered types. ---------------------------------------- (8) Obligation: Runtime Complexity Weighted TRS with Types. The TRS R consists of the following rules: f(x, y) -> h(x, y) [1] f(x, y) -> h(y, x) [1] h(x, x) -> x [1] encArg(cons_f(x_1, x_2)) -> f(encArg(x_1), encArg(x_2)) [0] encArg(cons_h(x_1, x_2)) -> h(encArg(x_1), encArg(x_2)) [0] encode_f(x_1, x_2) -> f(encArg(x_1), encArg(x_2)) [0] encode_h(x_1, x_2) -> h(encArg(x_1), encArg(x_2)) [0] The TRS has the following type information: f :: f:h:encArg:encode_f:encode_h -> f:h:encArg:encode_f:encode_h -> f:h:encArg:encode_f:encode_h h :: f:h:encArg:encode_f:encode_h -> f:h:encArg:encode_f:encode_h -> f:h:encArg:encode_f:encode_h encArg :: cons_f:cons_h -> f:h:encArg:encode_f:encode_h cons_f :: cons_f:cons_h -> cons_f:cons_h -> cons_f:cons_h cons_h :: cons_f:cons_h -> cons_f:cons_h -> cons_f:cons_h encode_f :: cons_f:cons_h -> cons_f:cons_h -> f:h:encArg:encode_f:encode_h encode_h :: cons_f:cons_h -> cons_f:cons_h -> f:h:encArg:encode_f:encode_h Rewrite Strategy: INNERMOST ---------------------------------------- (9) CompletionProof (UPPER BOUND(ID)) The transformation into a RNTS is sound, since: (a) The obligation is a constructor system where every type has a constant constructor, (b) The following defined symbols do not have to be completely defined, as they can never occur inside other defined symbols: none (c) The following functions are completely defined: h_2 f_2 encArg_1 encode_f_2 encode_h_2 Due to the following rules being added: encArg(v0) -> const [0] encode_f(v0, v1) -> const [0] encode_h(v0, v1) -> const [0] h(v0, v1) -> const [0] And the following fresh constants: const, const1 ---------------------------------------- (10) Obligation: Runtime Complexity Weighted TRS where critical functions are completely defined. The underlying TRS is: Runtime Complexity Weighted TRS with Types. The TRS R consists of the following rules: f(x, y) -> h(x, y) [1] f(x, y) -> h(y, x) [1] h(x, x) -> x [1] encArg(cons_f(x_1, x_2)) -> f(encArg(x_1), encArg(x_2)) [0] encArg(cons_h(x_1, x_2)) -> h(encArg(x_1), encArg(x_2)) [0] encode_f(x_1, x_2) -> f(encArg(x_1), encArg(x_2)) [0] encode_h(x_1, x_2) -> h(encArg(x_1), encArg(x_2)) [0] encArg(v0) -> const [0] encode_f(v0, v1) -> const [0] encode_h(v0, v1) -> const [0] h(v0, v1) -> const [0] The TRS has the following type information: f :: const -> const -> const h :: const -> const -> const encArg :: cons_f:cons_h -> const cons_f :: cons_f:cons_h -> cons_f:cons_h -> cons_f:cons_h cons_h :: cons_f:cons_h -> cons_f:cons_h -> cons_f:cons_h encode_f :: cons_f:cons_h -> cons_f:cons_h -> const encode_h :: cons_f:cons_h -> cons_f:cons_h -> const const :: const const1 :: cons_f:cons_h Rewrite Strategy: INNERMOST ---------------------------------------- (11) NarrowingProof (BOTH BOUNDS(ID, ID)) Narrowed the inner basic terms of all right-hand sides by a single narrowing step. ---------------------------------------- (12) Obligation: Runtime Complexity Weighted TRS where critical functions are completely defined. The underlying TRS is: Runtime Complexity Weighted TRS with Types. The TRS R consists of the following rules: f(x, y) -> h(x, y) [1] f(x, y) -> h(y, x) [1] h(x, x) -> x [1] encArg(cons_f(cons_f(x_1', x_2'), cons_f(x_11, x_21))) -> f(f(encArg(x_1'), encArg(x_2')), f(encArg(x_11), encArg(x_21))) [0] encArg(cons_f(cons_f(x_1', x_2'), cons_h(x_12, x_22))) -> f(f(encArg(x_1'), encArg(x_2')), h(encArg(x_12), encArg(x_22))) [0] encArg(cons_f(cons_f(x_1', x_2'), x_2)) -> f(f(encArg(x_1'), encArg(x_2')), const) [0] encArg(cons_f(cons_h(x_1'', x_2''), cons_f(x_13, x_23))) -> f(h(encArg(x_1''), encArg(x_2'')), f(encArg(x_13), encArg(x_23))) [0] encArg(cons_f(cons_h(x_1'', x_2''), cons_h(x_14, x_24))) -> f(h(encArg(x_1''), encArg(x_2'')), h(encArg(x_14), encArg(x_24))) [0] encArg(cons_f(cons_h(x_1'', x_2''), x_2)) -> f(h(encArg(x_1''), encArg(x_2'')), const) [0] encArg(cons_f(x_1, cons_f(x_15, x_25))) -> f(const, f(encArg(x_15), encArg(x_25))) [0] encArg(cons_f(x_1, cons_h(x_16, x_26))) -> f(const, h(encArg(x_16), encArg(x_26))) [0] encArg(cons_f(x_1, x_2)) -> f(const, const) [0] encArg(cons_h(cons_f(x_17, x_27), cons_f(x_19, x_29))) -> h(f(encArg(x_17), encArg(x_27)), f(encArg(x_19), encArg(x_29))) [0] encArg(cons_h(cons_f(x_17, x_27), cons_h(x_110, x_210))) -> h(f(encArg(x_17), encArg(x_27)), h(encArg(x_110), encArg(x_210))) [0] encArg(cons_h(cons_f(x_17, x_27), x_2)) -> h(f(encArg(x_17), encArg(x_27)), const) [0] encArg(cons_h(cons_h(x_18, x_28), cons_f(x_111, x_211))) -> h(h(encArg(x_18), encArg(x_28)), f(encArg(x_111), encArg(x_211))) [0] encArg(cons_h(cons_h(x_18, x_28), cons_h(x_112, x_212))) -> h(h(encArg(x_18), encArg(x_28)), h(encArg(x_112), encArg(x_212))) [0] encArg(cons_h(cons_h(x_18, x_28), x_2)) -> h(h(encArg(x_18), encArg(x_28)), const) [0] encArg(cons_h(x_1, cons_f(x_113, x_213))) -> h(const, f(encArg(x_113), encArg(x_213))) [0] encArg(cons_h(x_1, cons_h(x_114, x_214))) -> h(const, h(encArg(x_114), encArg(x_214))) [0] encArg(cons_h(x_1, x_2)) -> h(const, const) [0] encode_f(cons_f(x_115, x_215), cons_f(x_117, x_217)) -> f(f(encArg(x_115), encArg(x_215)), f(encArg(x_117), encArg(x_217))) [0] encode_f(cons_f(x_115, x_215), cons_h(x_118, x_218)) -> f(f(encArg(x_115), encArg(x_215)), h(encArg(x_118), encArg(x_218))) [0] encode_f(cons_f(x_115, x_215), x_2) -> f(f(encArg(x_115), encArg(x_215)), const) [0] encode_f(cons_h(x_116, x_216), cons_f(x_119, x_219)) -> f(h(encArg(x_116), encArg(x_216)), f(encArg(x_119), encArg(x_219))) [0] encode_f(cons_h(x_116, x_216), cons_h(x_120, x_220)) -> f(h(encArg(x_116), encArg(x_216)), h(encArg(x_120), encArg(x_220))) [0] encode_f(cons_h(x_116, x_216), x_2) -> f(h(encArg(x_116), encArg(x_216)), const) [0] encode_f(x_1, cons_f(x_121, x_221)) -> f(const, f(encArg(x_121), encArg(x_221))) [0] encode_f(x_1, cons_h(x_122, x_222)) -> f(const, h(encArg(x_122), encArg(x_222))) [0] encode_f(x_1, x_2) -> f(const, const) [0] encode_h(cons_f(x_123, x_223), cons_f(x_125, x_225)) -> h(f(encArg(x_123), encArg(x_223)), f(encArg(x_125), encArg(x_225))) [0] encode_h(cons_f(x_123, x_223), cons_h(x_126, x_226)) -> h(f(encArg(x_123), encArg(x_223)), h(encArg(x_126), encArg(x_226))) [0] encode_h(cons_f(x_123, x_223), x_2) -> h(f(encArg(x_123), encArg(x_223)), const) [0] encode_h(cons_h(x_124, x_224), cons_f(x_127, x_227)) -> h(h(encArg(x_124), encArg(x_224)), f(encArg(x_127), encArg(x_227))) [0] encode_h(cons_h(x_124, x_224), cons_h(x_128, x_228)) -> h(h(encArg(x_124), encArg(x_224)), h(encArg(x_128), encArg(x_228))) [0] encode_h(cons_h(x_124, x_224), x_2) -> h(h(encArg(x_124), encArg(x_224)), const) [0] encode_h(x_1, cons_f(x_129, x_229)) -> h(const, f(encArg(x_129), encArg(x_229))) [0] encode_h(x_1, cons_h(x_130, x_230)) -> h(const, h(encArg(x_130), encArg(x_230))) [0] encode_h(x_1, x_2) -> h(const, const) [0] encArg(v0) -> const [0] encode_f(v0, v1) -> const [0] encode_h(v0, v1) -> const [0] h(v0, v1) -> const [0] The TRS has the following type information: f :: const -> const -> const h :: const -> const -> const encArg :: cons_f:cons_h -> const cons_f :: cons_f:cons_h -> cons_f:cons_h -> cons_f:cons_h cons_h :: cons_f:cons_h -> cons_f:cons_h -> cons_f:cons_h encode_f :: cons_f:cons_h -> cons_f:cons_h -> const encode_h :: cons_f:cons_h -> cons_f:cons_h -> const const :: const const1 :: cons_f:cons_h Rewrite Strategy: INNERMOST ---------------------------------------- (13) CpxTypedWeightedTrsToRntsProof (UPPER BOUND(ID)) Transformed the TRS into an over-approximating RNTS by (improved) Size Abstraction. The constant constructors are abstracted as follows: const => 0 const1 => 0 ---------------------------------------- (14) Obligation: Complexity RNTS consisting of the following rules: encArg(z) -{ 0 }-> h(h(encArg(x_18), encArg(x_28)), h(encArg(x_112), encArg(x_212))) :|: x_212 >= 0, z = 1 + (1 + x_18 + x_28) + (1 + x_112 + x_212), x_18 >= 0, x_28 >= 0, x_112 >= 0 encArg(z) -{ 0 }-> h(h(encArg(x_18), encArg(x_28)), f(encArg(x_111), encArg(x_211))) :|: z = 1 + (1 + x_18 + x_28) + (1 + x_111 + x_211), x_18 >= 0, x_28 >= 0, x_211 >= 0, x_111 >= 0 encArg(z) -{ 0 }-> h(h(encArg(x_18), encArg(x_28)), 0) :|: z = 1 + (1 + x_18 + x_28) + x_2, x_2 >= 0, x_18 >= 0, x_28 >= 0 encArg(z) -{ 0 }-> h(f(encArg(x_17), encArg(x_27)), h(encArg(x_110), encArg(x_210))) :|: z = 1 + (1 + x_17 + x_27) + (1 + x_110 + x_210), x_17 >= 0, x_27 >= 0, x_110 >= 0, x_210 >= 0 encArg(z) -{ 0 }-> h(f(encArg(x_17), encArg(x_27)), f(encArg(x_19), encArg(x_29))) :|: z = 1 + (1 + x_17 + x_27) + (1 + x_19 + x_29), x_17 >= 0, x_27 >= 0, x_19 >= 0, x_29 >= 0 encArg(z) -{ 0 }-> h(f(encArg(x_17), encArg(x_27)), 0) :|: x_17 >= 0, x_27 >= 0, x_2 >= 0, z = 1 + (1 + x_17 + x_27) + x_2 encArg(z) -{ 0 }-> h(0, h(encArg(x_114), encArg(x_214))) :|: z = 1 + x_1 + (1 + x_114 + x_214), x_1 >= 0, x_114 >= 0, x_214 >= 0 encArg(z) -{ 0 }-> h(0, f(encArg(x_113), encArg(x_213))) :|: x_1 >= 0, x_113 >= 0, x_213 >= 0, z = 1 + x_1 + (1 + x_113 + x_213) encArg(z) -{ 0 }-> h(0, 0) :|: x_1 >= 0, z = 1 + x_1 + x_2, x_2 >= 0 encArg(z) -{ 0 }-> f(h(encArg(x_1''), encArg(x_2'')), h(encArg(x_14), encArg(x_24))) :|: x_1'' >= 0, x_14 >= 0, x_2'' >= 0, x_24 >= 0, z = 1 + (1 + x_1'' + x_2'') + (1 + x_14 + x_24) encArg(z) -{ 0 }-> f(h(encArg(x_1''), encArg(x_2'')), f(encArg(x_13), encArg(x_23))) :|: x_1'' >= 0, x_13 >= 0, x_2'' >= 0, x_23 >= 0, z = 1 + (1 + x_1'' + x_2'') + (1 + x_13 + x_23) encArg(z) -{ 0 }-> f(h(encArg(x_1''), encArg(x_2'')), 0) :|: x_1'' >= 0, z = 1 + (1 + x_1'' + x_2'') + x_2, x_2'' >= 0, x_2 >= 0 encArg(z) -{ 0 }-> f(f(encArg(x_1'), encArg(x_2')), h(encArg(x_12), encArg(x_22))) :|: x_2' >= 0, z = 1 + (1 + x_1' + x_2') + (1 + x_12 + x_22), x_1' >= 0, x_12 >= 0, x_22 >= 0 encArg(z) -{ 0 }-> f(f(encArg(x_1'), encArg(x_2')), f(encArg(x_11), encArg(x_21))) :|: x_11 >= 0, x_2' >= 0, x_1' >= 0, x_21 >= 0, z = 1 + (1 + x_1' + x_2') + (1 + x_11 + x_21) encArg(z) -{ 0 }-> f(f(encArg(x_1'), encArg(x_2')), 0) :|: z = 1 + (1 + x_1' + x_2') + x_2, x_2' >= 0, x_1' >= 0, x_2 >= 0 encArg(z) -{ 0 }-> f(0, h(encArg(x_16), encArg(x_26))) :|: x_1 >= 0, x_16 >= 0, x_26 >= 0, z = 1 + x_1 + (1 + x_16 + x_26) encArg(z) -{ 0 }-> f(0, f(encArg(x_15), encArg(x_25))) :|: x_15 >= 0, x_1 >= 0, x_25 >= 0, z = 1 + x_1 + (1 + x_15 + x_25) encArg(z) -{ 0 }-> f(0, 0) :|: x_1 >= 0, z = 1 + x_1 + x_2, x_2 >= 0 encArg(z) -{ 0 }-> 0 :|: v0 >= 0, z = v0 encode_f(z, z') -{ 0 }-> f(h(encArg(x_116), encArg(x_216)), h(encArg(x_120), encArg(x_220))) :|: x_216 >= 0, x_120 >= 0, x_116 >= 0, z = 1 + x_116 + x_216, z' = 1 + x_120 + x_220, x_220 >= 0 encode_f(z, z') -{ 0 }-> f(h(encArg(x_116), encArg(x_216)), f(encArg(x_119), encArg(x_219))) :|: x_216 >= 0, z' = 1 + x_119 + x_219, x_116 >= 0, z = 1 + x_116 + x_216, x_219 >= 0, x_119 >= 0 encode_f(z, z') -{ 0 }-> f(h(encArg(x_116), encArg(x_216)), 0) :|: x_216 >= 0, x_116 >= 0, z = 1 + x_116 + x_216, x_2 >= 0, z' = x_2 encode_f(z, z') -{ 0 }-> f(f(encArg(x_115), encArg(x_215)), h(encArg(x_118), encArg(x_218))) :|: x_215 >= 0, x_115 >= 0, z = 1 + x_115 + x_215, x_218 >= 0, z' = 1 + x_118 + x_218, x_118 >= 0 encode_f(z, z') -{ 0 }-> f(f(encArg(x_115), encArg(x_215)), f(encArg(x_117), encArg(x_217))) :|: x_117 >= 0, x_215 >= 0, x_115 >= 0, z = 1 + x_115 + x_215, z' = 1 + x_117 + x_217, x_217 >= 0 encode_f(z, z') -{ 0 }-> f(f(encArg(x_115), encArg(x_215)), 0) :|: x_215 >= 0, x_115 >= 0, z = 1 + x_115 + x_215, x_2 >= 0, z' = x_2 encode_f(z, z') -{ 0 }-> f(0, h(encArg(x_122), encArg(x_222))) :|: x_1 >= 0, x_222 >= 0, x_122 >= 0, z = x_1, z' = 1 + x_122 + x_222 encode_f(z, z') -{ 0 }-> f(0, f(encArg(x_121), encArg(x_221))) :|: x_1 >= 0, z' = 1 + x_121 + x_221, x_221 >= 0, z = x_1, x_121 >= 0 encode_f(z, z') -{ 0 }-> f(0, 0) :|: x_1 >= 0, x_2 >= 0, z = x_1, z' = x_2 encode_f(z, z') -{ 0 }-> 0 :|: v0 >= 0, v1 >= 0, z = v0, z' = v1 encode_h(z, z') -{ 0 }-> h(h(encArg(x_124), encArg(x_224)), h(encArg(x_128), encArg(x_228))) :|: z = 1 + x_124 + x_224, x_124 >= 0, x_128 >= 0, z' = 1 + x_128 + x_228, x_224 >= 0, x_228 >= 0 encode_h(z, z') -{ 0 }-> h(h(encArg(x_124), encArg(x_224)), f(encArg(x_127), encArg(x_227))) :|: z = 1 + x_124 + x_224, x_124 >= 0, x_127 >= 0, x_224 >= 0, z' = 1 + x_127 + x_227, x_227 >= 0 encode_h(z, z') -{ 0 }-> h(h(encArg(x_124), encArg(x_224)), 0) :|: z = 1 + x_124 + x_224, x_124 >= 0, x_224 >= 0, x_2 >= 0, z' = x_2 encode_h(z, z') -{ 0 }-> h(f(encArg(x_123), encArg(x_223)), h(encArg(x_126), encArg(x_226))) :|: z = 1 + x_123 + x_223, x_226 >= 0, x_123 >= 0, x_223 >= 0, x_126 >= 0, z' = 1 + x_126 + x_226 encode_h(z, z') -{ 0 }-> h(f(encArg(x_123), encArg(x_223)), f(encArg(x_125), encArg(x_225))) :|: z = 1 + x_123 + x_223, x_123 >= 0, z' = 1 + x_125 + x_225, x_223 >= 0, x_125 >= 0, x_225 >= 0 encode_h(z, z') -{ 0 }-> h(f(encArg(x_123), encArg(x_223)), 0) :|: z = 1 + x_123 + x_223, x_123 >= 0, x_223 >= 0, x_2 >= 0, z' = x_2 encode_h(z, z') -{ 0 }-> h(0, h(encArg(x_130), encArg(x_230))) :|: x_1 >= 0, x_130 >= 0, z' = 1 + x_130 + x_230, z = x_1, x_230 >= 0 encode_h(z, z') -{ 0 }-> h(0, f(encArg(x_129), encArg(x_229))) :|: x_1 >= 0, z' = 1 + x_129 + x_229, x_229 >= 0, z = x_1, x_129 >= 0 encode_h(z, z') -{ 0 }-> h(0, 0) :|: x_1 >= 0, x_2 >= 0, z = x_1, z' = x_2 encode_h(z, z') -{ 0 }-> 0 :|: v0 >= 0, v1 >= 0, z = v0, z' = v1 f(z, z') -{ 1 }-> h(x, y) :|: x >= 0, y >= 0, z = x, z' = y f(z, z') -{ 1 }-> h(y, x) :|: x >= 0, y >= 0, z = x, z' = y h(z, z') -{ 1 }-> x :|: z' = x, x >= 0, z = x h(z, z') -{ 0 }-> 0 :|: v0 >= 0, v1 >= 0, z = v0, z' = v1 ---------------------------------------- (15) InliningProof (UPPER BOUND(ID)) Inlined the following terminating rules on right-hand sides where appropriate: h(z, z') -{ 1 }-> x :|: z' = x, x >= 0, z = x h(z, z') -{ 0 }-> 0 :|: v0 >= 0, v1 >= 0, z = v0, z' = v1 f(z, z') -{ 1 }-> h(x, y) :|: x >= 0, y >= 0, z = x, z' = y f(z, z') -{ 1 }-> h(y, x) :|: x >= 0, y >= 0, z = x, z' = y ---------------------------------------- (16) Obligation: Complexity RNTS consisting of the following rules: encArg(z) -{ 1 }-> x :|: x_1 >= 0, z = 1 + x_1 + x_2, x_2 >= 0, 0 = x, x >= 0 encArg(z) -{ 1 }-> h(x, y) :|: x_1 >= 0, z = 1 + x_1 + x_2, x_2 >= 0, x >= 0, y >= 0, 0 = x, 0 = y encArg(z) -{ 1 }-> h(y, x) :|: x_1 >= 0, z = 1 + x_1 + x_2, x_2 >= 0, x >= 0, y >= 0, 0 = x, 0 = y encArg(z) -{ 0 }-> h(h(encArg(x_18), encArg(x_28)), h(encArg(x_112), encArg(x_212))) :|: x_212 >= 0, z = 1 + (1 + x_18 + x_28) + (1 + x_112 + x_212), x_18 >= 0, x_28 >= 0, x_112 >= 0 encArg(z) -{ 0 }-> h(h(encArg(x_18), encArg(x_28)), f(encArg(x_111), encArg(x_211))) :|: z = 1 + (1 + x_18 + x_28) + (1 + x_111 + x_211), x_18 >= 0, x_28 >= 0, x_211 >= 0, x_111 >= 0 encArg(z) -{ 0 }-> h(h(encArg(x_18), encArg(x_28)), 0) :|: z = 1 + (1 + x_18 + x_28) + x_2, x_2 >= 0, x_18 >= 0, x_28 >= 0 encArg(z) -{ 0 }-> h(f(encArg(x_17), encArg(x_27)), h(encArg(x_110), encArg(x_210))) :|: z = 1 + (1 + x_17 + x_27) + (1 + x_110 + x_210), x_17 >= 0, x_27 >= 0, x_110 >= 0, x_210 >= 0 encArg(z) -{ 0 }-> h(f(encArg(x_17), encArg(x_27)), f(encArg(x_19), encArg(x_29))) :|: z = 1 + (1 + x_17 + x_27) + (1 + x_19 + x_29), x_17 >= 0, x_27 >= 0, x_19 >= 0, x_29 >= 0 encArg(z) -{ 0 }-> h(f(encArg(x_17), encArg(x_27)), 0) :|: x_17 >= 0, x_27 >= 0, x_2 >= 0, z = 1 + (1 + x_17 + x_27) + x_2 encArg(z) -{ 0 }-> h(0, h(encArg(x_114), encArg(x_214))) :|: z = 1 + x_1 + (1 + x_114 + x_214), x_1 >= 0, x_114 >= 0, x_214 >= 0 encArg(z) -{ 0 }-> h(0, f(encArg(x_113), encArg(x_213))) :|: x_1 >= 0, x_113 >= 0, x_213 >= 0, z = 1 + x_1 + (1 + x_113 + x_213) encArg(z) -{ 0 }-> f(h(encArg(x_1''), encArg(x_2'')), h(encArg(x_14), encArg(x_24))) :|: x_1'' >= 0, x_14 >= 0, x_2'' >= 0, x_24 >= 0, z = 1 + (1 + x_1'' + x_2'') + (1 + x_14 + x_24) encArg(z) -{ 0 }-> f(h(encArg(x_1''), encArg(x_2'')), f(encArg(x_13), encArg(x_23))) :|: x_1'' >= 0, x_13 >= 0, x_2'' >= 0, x_23 >= 0, z = 1 + (1 + x_1'' + x_2'') + (1 + x_13 + x_23) encArg(z) -{ 0 }-> f(h(encArg(x_1''), encArg(x_2'')), 0) :|: x_1'' >= 0, z = 1 + (1 + x_1'' + x_2'') + x_2, x_2'' >= 0, x_2 >= 0 encArg(z) -{ 0 }-> f(f(encArg(x_1'), encArg(x_2')), h(encArg(x_12), encArg(x_22))) :|: x_2' >= 0, z = 1 + (1 + x_1' + x_2') + (1 + x_12 + x_22), x_1' >= 0, x_12 >= 0, x_22 >= 0 encArg(z) -{ 0 }-> f(f(encArg(x_1'), encArg(x_2')), f(encArg(x_11), encArg(x_21))) :|: x_11 >= 0, x_2' >= 0, x_1' >= 0, x_21 >= 0, z = 1 + (1 + x_1' + x_2') + (1 + x_11 + x_21) encArg(z) -{ 0 }-> f(f(encArg(x_1'), encArg(x_2')), 0) :|: z = 1 + (1 + x_1' + x_2') + x_2, x_2' >= 0, x_1' >= 0, x_2 >= 0 encArg(z) -{ 0 }-> f(0, h(encArg(x_16), encArg(x_26))) :|: x_1 >= 0, x_16 >= 0, x_26 >= 0, z = 1 + x_1 + (1 + x_16 + x_26) encArg(z) -{ 0 }-> f(0, f(encArg(x_15), encArg(x_25))) :|: x_15 >= 0, x_1 >= 0, x_25 >= 0, z = 1 + x_1 + (1 + x_15 + x_25) encArg(z) -{ 0 }-> 0 :|: v0 >= 0, z = v0 encArg(z) -{ 0 }-> 0 :|: x_1 >= 0, z = 1 + x_1 + x_2, x_2 >= 0, v0 >= 0, v1 >= 0, 0 = v0, 0 = v1 encode_f(z, z') -{ 1 }-> h(x, y) :|: x_1 >= 0, x_2 >= 0, z = x_1, z' = x_2, x >= 0, y >= 0, 0 = x, 0 = y encode_f(z, z') -{ 1 }-> h(y, x) :|: x_1 >= 0, x_2 >= 0, z = x_1, z' = x_2, x >= 0, y >= 0, 0 = x, 0 = y encode_f(z, z') -{ 0 }-> f(h(encArg(x_116), encArg(x_216)), h(encArg(x_120), encArg(x_220))) :|: x_216 >= 0, x_120 >= 0, x_116 >= 0, z = 1 + x_116 + x_216, z' = 1 + x_120 + x_220, x_220 >= 0 encode_f(z, z') -{ 0 }-> f(h(encArg(x_116), encArg(x_216)), f(encArg(x_119), encArg(x_219))) :|: x_216 >= 0, z' = 1 + x_119 + x_219, x_116 >= 0, z = 1 + x_116 + x_216, x_219 >= 0, x_119 >= 0 encode_f(z, z') -{ 0 }-> f(h(encArg(x_116), encArg(x_216)), 0) :|: x_216 >= 0, x_116 >= 0, z = 1 + x_116 + x_216, x_2 >= 0, z' = x_2 encode_f(z, z') -{ 0 }-> f(f(encArg(x_115), encArg(x_215)), h(encArg(x_118), encArg(x_218))) :|: x_215 >= 0, x_115 >= 0, z = 1 + x_115 + x_215, x_218 >= 0, z' = 1 + x_118 + x_218, x_118 >= 0 encode_f(z, z') -{ 0 }-> f(f(encArg(x_115), encArg(x_215)), f(encArg(x_117), encArg(x_217))) :|: x_117 >= 0, x_215 >= 0, x_115 >= 0, z = 1 + x_115 + x_215, z' = 1 + x_117 + x_217, x_217 >= 0 encode_f(z, z') -{ 0 }-> f(f(encArg(x_115), encArg(x_215)), 0) :|: x_215 >= 0, x_115 >= 0, z = 1 + x_115 + x_215, x_2 >= 0, z' = x_2 encode_f(z, z') -{ 0 }-> f(0, h(encArg(x_122), encArg(x_222))) :|: x_1 >= 0, x_222 >= 0, x_122 >= 0, z = x_1, z' = 1 + x_122 + x_222 encode_f(z, z') -{ 0 }-> f(0, f(encArg(x_121), encArg(x_221))) :|: x_1 >= 0, z' = 1 + x_121 + x_221, x_221 >= 0, z = x_1, x_121 >= 0 encode_f(z, z') -{ 0 }-> 0 :|: v0 >= 0, v1 >= 0, z = v0, z' = v1 encode_h(z, z') -{ 1 }-> x :|: x_1 >= 0, x_2 >= 0, z = x_1, z' = x_2, 0 = x, x >= 0 encode_h(z, z') -{ 0 }-> h(h(encArg(x_124), encArg(x_224)), h(encArg(x_128), encArg(x_228))) :|: z = 1 + x_124 + x_224, x_124 >= 0, x_128 >= 0, z' = 1 + x_128 + x_228, x_224 >= 0, x_228 >= 0 encode_h(z, z') -{ 0 }-> h(h(encArg(x_124), encArg(x_224)), f(encArg(x_127), encArg(x_227))) :|: z = 1 + x_124 + x_224, x_124 >= 0, x_127 >= 0, x_224 >= 0, z' = 1 + x_127 + x_227, x_227 >= 0 encode_h(z, z') -{ 0 }-> h(h(encArg(x_124), encArg(x_224)), 0) :|: z = 1 + x_124 + x_224, x_124 >= 0, x_224 >= 0, x_2 >= 0, z' = x_2 encode_h(z, z') -{ 0 }-> h(f(encArg(x_123), encArg(x_223)), h(encArg(x_126), encArg(x_226))) :|: z = 1 + x_123 + x_223, x_226 >= 0, x_123 >= 0, x_223 >= 0, x_126 >= 0, z' = 1 + x_126 + x_226 encode_h(z, z') -{ 0 }-> h(f(encArg(x_123), encArg(x_223)), f(encArg(x_125), encArg(x_225))) :|: z = 1 + x_123 + x_223, x_123 >= 0, z' = 1 + x_125 + x_225, x_223 >= 0, x_125 >= 0, x_225 >= 0 encode_h(z, z') -{ 0 }-> h(f(encArg(x_123), encArg(x_223)), 0) :|: z = 1 + x_123 + x_223, x_123 >= 0, x_223 >= 0, x_2 >= 0, z' = x_2 encode_h(z, z') -{ 0 }-> h(0, h(encArg(x_130), encArg(x_230))) :|: x_1 >= 0, x_130 >= 0, z' = 1 + x_130 + x_230, z = x_1, x_230 >= 0 encode_h(z, z') -{ 0 }-> h(0, f(encArg(x_129), encArg(x_229))) :|: x_1 >= 0, z' = 1 + x_129 + x_229, x_229 >= 0, z = x_1, x_129 >= 0 encode_h(z, z') -{ 0 }-> 0 :|: v0 >= 0, v1 >= 0, z = v0, z' = v1 encode_h(z, z') -{ 0 }-> 0 :|: x_1 >= 0, x_2 >= 0, z = x_1, z' = x_2, v0 >= 0, v1 >= 0, 0 = v0, 0 = v1 f(z, z') -{ 2 }-> x' :|: x >= 0, y >= 0, z = x, z' = y, y = x', x' >= 0, x = x' f(z, z') -{ 1 }-> 0 :|: x >= 0, y >= 0, z = x, z' = y, v0 >= 0, v1 >= 0, x = v0, y = v1 f(z, z') -{ 1 }-> 0 :|: x >= 0, y >= 0, z = x, z' = y, v0 >= 0, v1 >= 0, y = v0, x = v1 h(z, z') -{ 1 }-> x :|: z' = x, x >= 0, z = x h(z, z') -{ 0 }-> 0 :|: v0 >= 0, v1 >= 0, z = v0, z' = v1 ---------------------------------------- (17) SimplificationProof (BOTH BOUNDS(ID, ID)) Simplified the RNTS by moving equalities from the constraints into the right-hand sides. ---------------------------------------- (18) Obligation: Complexity RNTS consisting of the following rules: encArg(z) -{ 1 }-> x :|: x_1 >= 0, z = 1 + x_1 + x_2, x_2 >= 0, 0 = x, x >= 0 encArg(z) -{ 1 }-> h(x, y) :|: x_1 >= 0, z = 1 + x_1 + x_2, x_2 >= 0, x >= 0, y >= 0, 0 = x, 0 = y encArg(z) -{ 1 }-> h(y, x) :|: x_1 >= 0, z = 1 + x_1 + x_2, x_2 >= 0, x >= 0, y >= 0, 0 = x, 0 = y encArg(z) -{ 0 }-> h(h(encArg(x_18), encArg(x_28)), h(encArg(x_112), encArg(x_212))) :|: x_212 >= 0, z = 1 + (1 + x_18 + x_28) + (1 + x_112 + x_212), x_18 >= 0, x_28 >= 0, x_112 >= 0 encArg(z) -{ 0 }-> h(h(encArg(x_18), encArg(x_28)), f(encArg(x_111), encArg(x_211))) :|: z = 1 + (1 + x_18 + x_28) + (1 + x_111 + x_211), x_18 >= 0, x_28 >= 0, x_211 >= 0, x_111 >= 0 encArg(z) -{ 0 }-> h(h(encArg(x_18), encArg(x_28)), 0) :|: z = 1 + (1 + x_18 + x_28) + x_2, x_2 >= 0, x_18 >= 0, x_28 >= 0 encArg(z) -{ 0 }-> h(f(encArg(x_17), encArg(x_27)), h(encArg(x_110), encArg(x_210))) :|: z = 1 + (1 + x_17 + x_27) + (1 + x_110 + x_210), x_17 >= 0, x_27 >= 0, x_110 >= 0, x_210 >= 0 encArg(z) -{ 0 }-> h(f(encArg(x_17), encArg(x_27)), f(encArg(x_19), encArg(x_29))) :|: z = 1 + (1 + x_17 + x_27) + (1 + x_19 + x_29), x_17 >= 0, x_27 >= 0, x_19 >= 0, x_29 >= 0 encArg(z) -{ 0 }-> h(f(encArg(x_17), encArg(x_27)), 0) :|: x_17 >= 0, x_27 >= 0, x_2 >= 0, z = 1 + (1 + x_17 + x_27) + x_2 encArg(z) -{ 0 }-> h(0, h(encArg(x_114), encArg(x_214))) :|: z = 1 + x_1 + (1 + x_114 + x_214), x_1 >= 0, x_114 >= 0, x_214 >= 0 encArg(z) -{ 0 }-> h(0, f(encArg(x_113), encArg(x_213))) :|: x_1 >= 0, x_113 >= 0, x_213 >= 0, z = 1 + x_1 + (1 + x_113 + x_213) encArg(z) -{ 0 }-> f(h(encArg(x_1''), encArg(x_2'')), h(encArg(x_14), encArg(x_24))) :|: x_1'' >= 0, x_14 >= 0, x_2'' >= 0, x_24 >= 0, z = 1 + (1 + x_1'' + x_2'') + (1 + x_14 + x_24) encArg(z) -{ 0 }-> f(h(encArg(x_1''), encArg(x_2'')), f(encArg(x_13), encArg(x_23))) :|: x_1'' >= 0, x_13 >= 0, x_2'' >= 0, x_23 >= 0, z = 1 + (1 + x_1'' + x_2'') + (1 + x_13 + x_23) encArg(z) -{ 0 }-> f(h(encArg(x_1''), encArg(x_2'')), 0) :|: x_1'' >= 0, z = 1 + (1 + x_1'' + x_2'') + x_2, x_2'' >= 0, x_2 >= 0 encArg(z) -{ 0 }-> f(f(encArg(x_1'), encArg(x_2')), h(encArg(x_12), encArg(x_22))) :|: x_2' >= 0, z = 1 + (1 + x_1' + x_2') + (1 + x_12 + x_22), x_1' >= 0, x_12 >= 0, x_22 >= 0 encArg(z) -{ 0 }-> f(f(encArg(x_1'), encArg(x_2')), f(encArg(x_11), encArg(x_21))) :|: x_11 >= 0, x_2' >= 0, x_1' >= 0, x_21 >= 0, z = 1 + (1 + x_1' + x_2') + (1 + x_11 + x_21) encArg(z) -{ 0 }-> f(f(encArg(x_1'), encArg(x_2')), 0) :|: z = 1 + (1 + x_1' + x_2') + x_2, x_2' >= 0, x_1' >= 0, x_2 >= 0 encArg(z) -{ 0 }-> f(0, h(encArg(x_16), encArg(x_26))) :|: x_1 >= 0, x_16 >= 0, x_26 >= 0, z = 1 + x_1 + (1 + x_16 + x_26) encArg(z) -{ 0 }-> f(0, f(encArg(x_15), encArg(x_25))) :|: x_15 >= 0, x_1 >= 0, x_25 >= 0, z = 1 + x_1 + (1 + x_15 + x_25) encArg(z) -{ 0 }-> 0 :|: z >= 0 encArg(z) -{ 0 }-> 0 :|: x_1 >= 0, z = 1 + x_1 + x_2, x_2 >= 0, v0 >= 0, v1 >= 0, 0 = v0, 0 = v1 encode_f(z, z') -{ 1 }-> h(x, y) :|: z >= 0, z' >= 0, x >= 0, y >= 0, 0 = x, 0 = y encode_f(z, z') -{ 1 }-> h(y, x) :|: z >= 0, z' >= 0, x >= 0, y >= 0, 0 = x, 0 = y encode_f(z, z') -{ 0 }-> f(h(encArg(x_116), encArg(x_216)), h(encArg(x_120), encArg(x_220))) :|: x_216 >= 0, x_120 >= 0, x_116 >= 0, z = 1 + x_116 + x_216, z' = 1 + x_120 + x_220, x_220 >= 0 encode_f(z, z') -{ 0 }-> f(h(encArg(x_116), encArg(x_216)), f(encArg(x_119), encArg(x_219))) :|: x_216 >= 0, z' = 1 + x_119 + x_219, x_116 >= 0, z = 1 + x_116 + x_216, x_219 >= 0, x_119 >= 0 encode_f(z, z') -{ 0 }-> f(h(encArg(x_116), encArg(x_216)), 0) :|: x_216 >= 0, x_116 >= 0, z = 1 + x_116 + x_216, z' >= 0 encode_f(z, z') -{ 0 }-> f(f(encArg(x_115), encArg(x_215)), h(encArg(x_118), encArg(x_218))) :|: x_215 >= 0, x_115 >= 0, z = 1 + x_115 + x_215, x_218 >= 0, z' = 1 + x_118 + x_218, x_118 >= 0 encode_f(z, z') -{ 0 }-> f(f(encArg(x_115), encArg(x_215)), f(encArg(x_117), encArg(x_217))) :|: x_117 >= 0, x_215 >= 0, x_115 >= 0, z = 1 + x_115 + x_215, z' = 1 + x_117 + x_217, x_217 >= 0 encode_f(z, z') -{ 0 }-> f(f(encArg(x_115), encArg(x_215)), 0) :|: x_215 >= 0, x_115 >= 0, z = 1 + x_115 + x_215, z' >= 0 encode_f(z, z') -{ 0 }-> f(0, h(encArg(x_122), encArg(x_222))) :|: z >= 0, x_222 >= 0, x_122 >= 0, z' = 1 + x_122 + x_222 encode_f(z, z') -{ 0 }-> f(0, f(encArg(x_121), encArg(x_221))) :|: z >= 0, z' = 1 + x_121 + x_221, x_221 >= 0, x_121 >= 0 encode_f(z, z') -{ 0 }-> 0 :|: z >= 0, z' >= 0 encode_h(z, z') -{ 1 }-> x :|: z >= 0, z' >= 0, 0 = x, x >= 0 encode_h(z, z') -{ 0 }-> h(h(encArg(x_124), encArg(x_224)), h(encArg(x_128), encArg(x_228))) :|: z = 1 + x_124 + x_224, x_124 >= 0, x_128 >= 0, z' = 1 + x_128 + x_228, x_224 >= 0, x_228 >= 0 encode_h(z, z') -{ 0 }-> h(h(encArg(x_124), encArg(x_224)), f(encArg(x_127), encArg(x_227))) :|: z = 1 + x_124 + x_224, x_124 >= 0, x_127 >= 0, x_224 >= 0, z' = 1 + x_127 + x_227, x_227 >= 0 encode_h(z, z') -{ 0 }-> h(h(encArg(x_124), encArg(x_224)), 0) :|: z = 1 + x_124 + x_224, x_124 >= 0, x_224 >= 0, z' >= 0 encode_h(z, z') -{ 0 }-> h(f(encArg(x_123), encArg(x_223)), h(encArg(x_126), encArg(x_226))) :|: z = 1 + x_123 + x_223, x_226 >= 0, x_123 >= 0, x_223 >= 0, x_126 >= 0, z' = 1 + x_126 + x_226 encode_h(z, z') -{ 0 }-> h(f(encArg(x_123), encArg(x_223)), f(encArg(x_125), encArg(x_225))) :|: z = 1 + x_123 + x_223, x_123 >= 0, z' = 1 + x_125 + x_225, x_223 >= 0, x_125 >= 0, x_225 >= 0 encode_h(z, z') -{ 0 }-> h(f(encArg(x_123), encArg(x_223)), 0) :|: z = 1 + x_123 + x_223, x_123 >= 0, x_223 >= 0, z' >= 0 encode_h(z, z') -{ 0 }-> h(0, h(encArg(x_130), encArg(x_230))) :|: z >= 0, x_130 >= 0, z' = 1 + x_130 + x_230, x_230 >= 0 encode_h(z, z') -{ 0 }-> h(0, f(encArg(x_129), encArg(x_229))) :|: z >= 0, z' = 1 + x_129 + x_229, x_229 >= 0, x_129 >= 0 encode_h(z, z') -{ 0 }-> 0 :|: z >= 0, z' >= 0 encode_h(z, z') -{ 0 }-> 0 :|: z >= 0, z' >= 0, v0 >= 0, v1 >= 0, 0 = v0, 0 = v1 f(z, z') -{ 2 }-> z' :|: z >= 0, z' >= 0, z = z' f(z, z') -{ 1 }-> 0 :|: z >= 0, z' >= 0 h(z, z') -{ 1 }-> z' :|: z' >= 0, z = z' h(z, z') -{ 0 }-> 0 :|: z >= 0, z' >= 0 ---------------------------------------- (19) CpxRntsAnalysisOrderProof (BOTH BOUNDS(ID, ID)) Found the following analysis order by SCC decomposition: { h } { f } { encArg } { encode_f } { encode_h } ---------------------------------------- (20) Obligation: Complexity RNTS consisting of the following rules: encArg(z) -{ 1 }-> x :|: x_1 >= 0, z = 1 + x_1 + x_2, x_2 >= 0, 0 = x, x >= 0 encArg(z) -{ 1 }-> h(x, y) :|: x_1 >= 0, z = 1 + x_1 + x_2, x_2 >= 0, x >= 0, y >= 0, 0 = x, 0 = y encArg(z) -{ 1 }-> h(y, x) :|: x_1 >= 0, z = 1 + x_1 + x_2, x_2 >= 0, x >= 0, y >= 0, 0 = x, 0 = y encArg(z) -{ 0 }-> h(h(encArg(x_18), encArg(x_28)), h(encArg(x_112), encArg(x_212))) :|: x_212 >= 0, z = 1 + (1 + x_18 + x_28) + (1 + x_112 + x_212), x_18 >= 0, x_28 >= 0, x_112 >= 0 encArg(z) -{ 0 }-> h(h(encArg(x_18), encArg(x_28)), f(encArg(x_111), encArg(x_211))) :|: z = 1 + (1 + x_18 + x_28) + (1 + x_111 + x_211), x_18 >= 0, x_28 >= 0, x_211 >= 0, x_111 >= 0 encArg(z) -{ 0 }-> h(h(encArg(x_18), encArg(x_28)), 0) :|: z = 1 + (1 + x_18 + x_28) + x_2, x_2 >= 0, x_18 >= 0, x_28 >= 0 encArg(z) -{ 0 }-> h(f(encArg(x_17), encArg(x_27)), h(encArg(x_110), encArg(x_210))) :|: z = 1 + (1 + x_17 + x_27) + (1 + x_110 + x_210), x_17 >= 0, x_27 >= 0, x_110 >= 0, x_210 >= 0 encArg(z) -{ 0 }-> h(f(encArg(x_17), encArg(x_27)), f(encArg(x_19), encArg(x_29))) :|: z = 1 + (1 + x_17 + x_27) + (1 + x_19 + x_29), x_17 >= 0, x_27 >= 0, x_19 >= 0, x_29 >= 0 encArg(z) -{ 0 }-> h(f(encArg(x_17), encArg(x_27)), 0) :|: x_17 >= 0, x_27 >= 0, x_2 >= 0, z = 1 + (1 + x_17 + x_27) + x_2 encArg(z) -{ 0 }-> h(0, h(encArg(x_114), encArg(x_214))) :|: z = 1 + x_1 + (1 + x_114 + x_214), x_1 >= 0, x_114 >= 0, x_214 >= 0 encArg(z) -{ 0 }-> h(0, f(encArg(x_113), encArg(x_213))) :|: x_1 >= 0, x_113 >= 0, x_213 >= 0, z = 1 + x_1 + (1 + x_113 + x_213) encArg(z) -{ 0 }-> f(h(encArg(x_1''), encArg(x_2'')), h(encArg(x_14), encArg(x_24))) :|: x_1'' >= 0, x_14 >= 0, x_2'' >= 0, x_24 >= 0, z = 1 + (1 + x_1'' + x_2'') + (1 + x_14 + x_24) encArg(z) -{ 0 }-> f(h(encArg(x_1''), encArg(x_2'')), f(encArg(x_13), encArg(x_23))) :|: x_1'' >= 0, x_13 >= 0, x_2'' >= 0, x_23 >= 0, z = 1 + (1 + x_1'' + x_2'') + (1 + x_13 + x_23) encArg(z) -{ 0 }-> f(h(encArg(x_1''), encArg(x_2'')), 0) :|: x_1'' >= 0, z = 1 + (1 + x_1'' + x_2'') + x_2, x_2'' >= 0, x_2 >= 0 encArg(z) -{ 0 }-> f(f(encArg(x_1'), encArg(x_2')), h(encArg(x_12), encArg(x_22))) :|: x_2' >= 0, z = 1 + (1 + x_1' + x_2') + (1 + x_12 + x_22), x_1' >= 0, x_12 >= 0, x_22 >= 0 encArg(z) -{ 0 }-> f(f(encArg(x_1'), encArg(x_2')), f(encArg(x_11), encArg(x_21))) :|: x_11 >= 0, x_2' >= 0, x_1' >= 0, x_21 >= 0, z = 1 + (1 + x_1' + x_2') + (1 + x_11 + x_21) encArg(z) -{ 0 }-> f(f(encArg(x_1'), encArg(x_2')), 0) :|: z = 1 + (1 + x_1' + x_2') + x_2, x_2' >= 0, x_1' >= 0, x_2 >= 0 encArg(z) -{ 0 }-> f(0, h(encArg(x_16), encArg(x_26))) :|: x_1 >= 0, x_16 >= 0, x_26 >= 0, z = 1 + x_1 + (1 + x_16 + x_26) encArg(z) -{ 0 }-> f(0, f(encArg(x_15), encArg(x_25))) :|: x_15 >= 0, x_1 >= 0, x_25 >= 0, z = 1 + x_1 + (1 + x_15 + x_25) encArg(z) -{ 0 }-> 0 :|: z >= 0 encArg(z) -{ 0 }-> 0 :|: x_1 >= 0, z = 1 + x_1 + x_2, x_2 >= 0, v0 >= 0, v1 >= 0, 0 = v0, 0 = v1 encode_f(z, z') -{ 1 }-> h(x, y) :|: z >= 0, z' >= 0, x >= 0, y >= 0, 0 = x, 0 = y encode_f(z, z') -{ 1 }-> h(y, x) :|: z >= 0, z' >= 0, x >= 0, y >= 0, 0 = x, 0 = y encode_f(z, z') -{ 0 }-> f(h(encArg(x_116), encArg(x_216)), h(encArg(x_120), encArg(x_220))) :|: x_216 >= 0, x_120 >= 0, x_116 >= 0, z = 1 + x_116 + x_216, z' = 1 + x_120 + x_220, x_220 >= 0 encode_f(z, z') -{ 0 }-> f(h(encArg(x_116), encArg(x_216)), f(encArg(x_119), encArg(x_219))) :|: x_216 >= 0, z' = 1 + x_119 + x_219, x_116 >= 0, z = 1 + x_116 + x_216, x_219 >= 0, x_119 >= 0 encode_f(z, z') -{ 0 }-> f(h(encArg(x_116), encArg(x_216)), 0) :|: x_216 >= 0, x_116 >= 0, z = 1 + x_116 + x_216, z' >= 0 encode_f(z, z') -{ 0 }-> f(f(encArg(x_115), encArg(x_215)), h(encArg(x_118), encArg(x_218))) :|: x_215 >= 0, x_115 >= 0, z = 1 + x_115 + x_215, x_218 >= 0, z' = 1 + x_118 + x_218, x_118 >= 0 encode_f(z, z') -{ 0 }-> f(f(encArg(x_115), encArg(x_215)), f(encArg(x_117), encArg(x_217))) :|: x_117 >= 0, x_215 >= 0, x_115 >= 0, z = 1 + x_115 + x_215, z' = 1 + x_117 + x_217, x_217 >= 0 encode_f(z, z') -{ 0 }-> f(f(encArg(x_115), encArg(x_215)), 0) :|: x_215 >= 0, x_115 >= 0, z = 1 + x_115 + x_215, z' >= 0 encode_f(z, z') -{ 0 }-> f(0, h(encArg(x_122), encArg(x_222))) :|: z >= 0, x_222 >= 0, x_122 >= 0, z' = 1 + x_122 + x_222 encode_f(z, z') -{ 0 }-> f(0, f(encArg(x_121), encArg(x_221))) :|: z >= 0, z' = 1 + x_121 + x_221, x_221 >= 0, x_121 >= 0 encode_f(z, z') -{ 0 }-> 0 :|: z >= 0, z' >= 0 encode_h(z, z') -{ 1 }-> x :|: z >= 0, z' >= 0, 0 = x, x >= 0 encode_h(z, z') -{ 0 }-> h(h(encArg(x_124), encArg(x_224)), h(encArg(x_128), encArg(x_228))) :|: z = 1 + x_124 + x_224, x_124 >= 0, x_128 >= 0, z' = 1 + x_128 + x_228, x_224 >= 0, x_228 >= 0 encode_h(z, z') -{ 0 }-> h(h(encArg(x_124), encArg(x_224)), f(encArg(x_127), encArg(x_227))) :|: z = 1 + x_124 + x_224, x_124 >= 0, x_127 >= 0, x_224 >= 0, z' = 1 + x_127 + x_227, x_227 >= 0 encode_h(z, z') -{ 0 }-> h(h(encArg(x_124), encArg(x_224)), 0) :|: z = 1 + x_124 + x_224, x_124 >= 0, x_224 >= 0, z' >= 0 encode_h(z, z') -{ 0 }-> h(f(encArg(x_123), encArg(x_223)), h(encArg(x_126), encArg(x_226))) :|: z = 1 + x_123 + x_223, x_226 >= 0, x_123 >= 0, x_223 >= 0, x_126 >= 0, z' = 1 + x_126 + x_226 encode_h(z, z') -{ 0 }-> h(f(encArg(x_123), encArg(x_223)), f(encArg(x_125), encArg(x_225))) :|: z = 1 + x_123 + x_223, x_123 >= 0, z' = 1 + x_125 + x_225, x_223 >= 0, x_125 >= 0, x_225 >= 0 encode_h(z, z') -{ 0 }-> h(f(encArg(x_123), encArg(x_223)), 0) :|: z = 1 + x_123 + x_223, x_123 >= 0, x_223 >= 0, z' >= 0 encode_h(z, z') -{ 0 }-> h(0, h(encArg(x_130), encArg(x_230))) :|: z >= 0, x_130 >= 0, z' = 1 + x_130 + x_230, x_230 >= 0 encode_h(z, z') -{ 0 }-> h(0, f(encArg(x_129), encArg(x_229))) :|: z >= 0, z' = 1 + x_129 + x_229, x_229 >= 0, x_129 >= 0 encode_h(z, z') -{ 0 }-> 0 :|: z >= 0, z' >= 0 encode_h(z, z') -{ 0 }-> 0 :|: z >= 0, z' >= 0, v0 >= 0, v1 >= 0, 0 = v0, 0 = v1 f(z, z') -{ 2 }-> z' :|: z >= 0, z' >= 0, z = z' f(z, z') -{ 1 }-> 0 :|: z >= 0, z' >= 0 h(z, z') -{ 1 }-> z' :|: z' >= 0, z = z' h(z, z') -{ 0 }-> 0 :|: z >= 0, z' >= 0 Function symbols to be analyzed: {h}, {f}, {encArg}, {encode_f}, {encode_h} ---------------------------------------- (21) ResultPropagationProof (UPPER BOUND(ID)) Applied inner abstraction using the recently inferred runtime/size bounds where possible. ---------------------------------------- (22) Obligation: Complexity RNTS consisting of the following rules: encArg(z) -{ 1 }-> x :|: x_1 >= 0, z = 1 + x_1 + x_2, x_2 >= 0, 0 = x, x >= 0 encArg(z) -{ 1 }-> h(x, y) :|: x_1 >= 0, z = 1 + x_1 + x_2, x_2 >= 0, x >= 0, y >= 0, 0 = x, 0 = y encArg(z) -{ 1 }-> h(y, x) :|: x_1 >= 0, z = 1 + x_1 + x_2, x_2 >= 0, x >= 0, y >= 0, 0 = x, 0 = y encArg(z) -{ 0 }-> h(h(encArg(x_18), encArg(x_28)), h(encArg(x_112), encArg(x_212))) :|: x_212 >= 0, z = 1 + (1 + x_18 + x_28) + (1 + x_112 + x_212), x_18 >= 0, x_28 >= 0, x_112 >= 0 encArg(z) -{ 0 }-> h(h(encArg(x_18), encArg(x_28)), f(encArg(x_111), encArg(x_211))) :|: z = 1 + (1 + x_18 + x_28) + (1 + x_111 + x_211), x_18 >= 0, x_28 >= 0, x_211 >= 0, x_111 >= 0 encArg(z) -{ 0 }-> h(h(encArg(x_18), encArg(x_28)), 0) :|: z = 1 + (1 + x_18 + x_28) + x_2, x_2 >= 0, x_18 >= 0, x_28 >= 0 encArg(z) -{ 0 }-> h(f(encArg(x_17), encArg(x_27)), h(encArg(x_110), encArg(x_210))) :|: z = 1 + (1 + x_17 + x_27) + (1 + x_110 + x_210), x_17 >= 0, x_27 >= 0, x_110 >= 0, x_210 >= 0 encArg(z) -{ 0 }-> h(f(encArg(x_17), encArg(x_27)), f(encArg(x_19), encArg(x_29))) :|: z = 1 + (1 + x_17 + x_27) + (1 + x_19 + x_29), x_17 >= 0, x_27 >= 0, x_19 >= 0, x_29 >= 0 encArg(z) -{ 0 }-> h(f(encArg(x_17), encArg(x_27)), 0) :|: x_17 >= 0, x_27 >= 0, x_2 >= 0, z = 1 + (1 + x_17 + x_27) + x_2 encArg(z) -{ 0 }-> h(0, h(encArg(x_114), encArg(x_214))) :|: z = 1 + x_1 + (1 + x_114 + x_214), x_1 >= 0, x_114 >= 0, x_214 >= 0 encArg(z) -{ 0 }-> h(0, f(encArg(x_113), encArg(x_213))) :|: x_1 >= 0, x_113 >= 0, x_213 >= 0, z = 1 + x_1 + (1 + x_113 + x_213) encArg(z) -{ 0 }-> f(h(encArg(x_1''), encArg(x_2'')), h(encArg(x_14), encArg(x_24))) :|: x_1'' >= 0, x_14 >= 0, x_2'' >= 0, x_24 >= 0, z = 1 + (1 + x_1'' + x_2'') + (1 + x_14 + x_24) encArg(z) -{ 0 }-> f(h(encArg(x_1''), encArg(x_2'')), f(encArg(x_13), encArg(x_23))) :|: x_1'' >= 0, x_13 >= 0, x_2'' >= 0, x_23 >= 0, z = 1 + (1 + x_1'' + x_2'') + (1 + x_13 + x_23) encArg(z) -{ 0 }-> f(h(encArg(x_1''), encArg(x_2'')), 0) :|: x_1'' >= 0, z = 1 + (1 + x_1'' + x_2'') + x_2, x_2'' >= 0, x_2 >= 0 encArg(z) -{ 0 }-> f(f(encArg(x_1'), encArg(x_2')), h(encArg(x_12), encArg(x_22))) :|: x_2' >= 0, z = 1 + (1 + x_1' + x_2') + (1 + x_12 + x_22), x_1' >= 0, x_12 >= 0, x_22 >= 0 encArg(z) -{ 0 }-> f(f(encArg(x_1'), encArg(x_2')), f(encArg(x_11), encArg(x_21))) :|: x_11 >= 0, x_2' >= 0, x_1' >= 0, x_21 >= 0, z = 1 + (1 + x_1' + x_2') + (1 + x_11 + x_21) encArg(z) -{ 0 }-> f(f(encArg(x_1'), encArg(x_2')), 0) :|: z = 1 + (1 + x_1' + x_2') + x_2, x_2' >= 0, x_1' >= 0, x_2 >= 0 encArg(z) -{ 0 }-> f(0, h(encArg(x_16), encArg(x_26))) :|: x_1 >= 0, x_16 >= 0, x_26 >= 0, z = 1 + x_1 + (1 + x_16 + x_26) encArg(z) -{ 0 }-> f(0, f(encArg(x_15), encArg(x_25))) :|: x_15 >= 0, x_1 >= 0, x_25 >= 0, z = 1 + x_1 + (1 + x_15 + x_25) encArg(z) -{ 0 }-> 0 :|: z >= 0 encArg(z) -{ 0 }-> 0 :|: x_1 >= 0, z = 1 + x_1 + x_2, x_2 >= 0, v0 >= 0, v1 >= 0, 0 = v0, 0 = v1 encode_f(z, z') -{ 1 }-> h(x, y) :|: z >= 0, z' >= 0, x >= 0, y >= 0, 0 = x, 0 = y encode_f(z, z') -{ 1 }-> h(y, x) :|: z >= 0, z' >= 0, x >= 0, y >= 0, 0 = x, 0 = y encode_f(z, z') -{ 0 }-> f(h(encArg(x_116), encArg(x_216)), h(encArg(x_120), encArg(x_220))) :|: x_216 >= 0, x_120 >= 0, x_116 >= 0, z = 1 + x_116 + x_216, z' = 1 + x_120 + x_220, x_220 >= 0 encode_f(z, z') -{ 0 }-> f(h(encArg(x_116), encArg(x_216)), f(encArg(x_119), encArg(x_219))) :|: x_216 >= 0, z' = 1 + x_119 + x_219, x_116 >= 0, z = 1 + x_116 + x_216, x_219 >= 0, x_119 >= 0 encode_f(z, z') -{ 0 }-> f(h(encArg(x_116), encArg(x_216)), 0) :|: x_216 >= 0, x_116 >= 0, z = 1 + x_116 + x_216, z' >= 0 encode_f(z, z') -{ 0 }-> f(f(encArg(x_115), encArg(x_215)), h(encArg(x_118), encArg(x_218))) :|: x_215 >= 0, x_115 >= 0, z = 1 + x_115 + x_215, x_218 >= 0, z' = 1 + x_118 + x_218, x_118 >= 0 encode_f(z, z') -{ 0 }-> f(f(encArg(x_115), encArg(x_215)), f(encArg(x_117), encArg(x_217))) :|: x_117 >= 0, x_215 >= 0, x_115 >= 0, z = 1 + x_115 + x_215, z' = 1 + x_117 + x_217, x_217 >= 0 encode_f(z, z') -{ 0 }-> f(f(encArg(x_115), encArg(x_215)), 0) :|: x_215 >= 0, x_115 >= 0, z = 1 + x_115 + x_215, z' >= 0 encode_f(z, z') -{ 0 }-> f(0, h(encArg(x_122), encArg(x_222))) :|: z >= 0, x_222 >= 0, x_122 >= 0, z' = 1 + x_122 + x_222 encode_f(z, z') -{ 0 }-> f(0, f(encArg(x_121), encArg(x_221))) :|: z >= 0, z' = 1 + x_121 + x_221, x_221 >= 0, x_121 >= 0 encode_f(z, z') -{ 0 }-> 0 :|: z >= 0, z' >= 0 encode_h(z, z') -{ 1 }-> x :|: z >= 0, z' >= 0, 0 = x, x >= 0 encode_h(z, z') -{ 0 }-> h(h(encArg(x_124), encArg(x_224)), h(encArg(x_128), encArg(x_228))) :|: z = 1 + x_124 + x_224, x_124 >= 0, x_128 >= 0, z' = 1 + x_128 + x_228, x_224 >= 0, x_228 >= 0 encode_h(z, z') -{ 0 }-> h(h(encArg(x_124), encArg(x_224)), f(encArg(x_127), encArg(x_227))) :|: z = 1 + x_124 + x_224, x_124 >= 0, x_127 >= 0, x_224 >= 0, z' = 1 + x_127 + x_227, x_227 >= 0 encode_h(z, z') -{ 0 }-> h(h(encArg(x_124), encArg(x_224)), 0) :|: z = 1 + x_124 + x_224, x_124 >= 0, x_224 >= 0, z' >= 0 encode_h(z, z') -{ 0 }-> h(f(encArg(x_123), encArg(x_223)), h(encArg(x_126), encArg(x_226))) :|: z = 1 + x_123 + x_223, x_226 >= 0, x_123 >= 0, x_223 >= 0, x_126 >= 0, z' = 1 + x_126 + x_226 encode_h(z, z') -{ 0 }-> h(f(encArg(x_123), encArg(x_223)), f(encArg(x_125), encArg(x_225))) :|: z = 1 + x_123 + x_223, x_123 >= 0, z' = 1 + x_125 + x_225, x_223 >= 0, x_125 >= 0, x_225 >= 0 encode_h(z, z') -{ 0 }-> h(f(encArg(x_123), encArg(x_223)), 0) :|: z = 1 + x_123 + x_223, x_123 >= 0, x_223 >= 0, z' >= 0 encode_h(z, z') -{ 0 }-> h(0, h(encArg(x_130), encArg(x_230))) :|: z >= 0, x_130 >= 0, z' = 1 + x_130 + x_230, x_230 >= 0 encode_h(z, z') -{ 0 }-> h(0, f(encArg(x_129), encArg(x_229))) :|: z >= 0, z' = 1 + x_129 + x_229, x_229 >= 0, x_129 >= 0 encode_h(z, z') -{ 0 }-> 0 :|: z >= 0, z' >= 0 encode_h(z, z') -{ 0 }-> 0 :|: z >= 0, z' >= 0, v0 >= 0, v1 >= 0, 0 = v0, 0 = v1 f(z, z') -{ 2 }-> z' :|: z >= 0, z' >= 0, z = z' f(z, z') -{ 1 }-> 0 :|: z >= 0, z' >= 0 h(z, z') -{ 1 }-> z' :|: z' >= 0, z = z' h(z, z') -{ 0 }-> 0 :|: z >= 0, z' >= 0 Function symbols to be analyzed: {h}, {f}, {encArg}, {encode_f}, {encode_h} ---------------------------------------- (23) IntTrsBoundProof (UPPER BOUND(ID)) Computed SIZE bound using CoFloCo for: h after applying outer abstraction to obtain an ITS, resulting in: O(n^1) with polynomial bound: z' ---------------------------------------- (24) Obligation: Complexity RNTS consisting of the following rules: encArg(z) -{ 1 }-> x :|: x_1 >= 0, z = 1 + x_1 + x_2, x_2 >= 0, 0 = x, x >= 0 encArg(z) -{ 1 }-> h(x, y) :|: x_1 >= 0, z = 1 + x_1 + x_2, x_2 >= 0, x >= 0, y >= 0, 0 = x, 0 = y encArg(z) -{ 1 }-> h(y, x) :|: x_1 >= 0, z = 1 + x_1 + x_2, x_2 >= 0, x >= 0, y >= 0, 0 = x, 0 = y encArg(z) -{ 0 }-> h(h(encArg(x_18), encArg(x_28)), h(encArg(x_112), encArg(x_212))) :|: x_212 >= 0, z = 1 + (1 + x_18 + x_28) + (1 + x_112 + x_212), x_18 >= 0, x_28 >= 0, x_112 >= 0 encArg(z) -{ 0 }-> h(h(encArg(x_18), encArg(x_28)), f(encArg(x_111), encArg(x_211))) :|: z = 1 + (1 + x_18 + x_28) + (1 + x_111 + x_211), x_18 >= 0, x_28 >= 0, x_211 >= 0, x_111 >= 0 encArg(z) -{ 0 }-> h(h(encArg(x_18), encArg(x_28)), 0) :|: z = 1 + (1 + x_18 + x_28) + x_2, x_2 >= 0, x_18 >= 0, x_28 >= 0 encArg(z) -{ 0 }-> h(f(encArg(x_17), encArg(x_27)), h(encArg(x_110), encArg(x_210))) :|: z = 1 + (1 + x_17 + x_27) + (1 + x_110 + x_210), x_17 >= 0, x_27 >= 0, x_110 >= 0, x_210 >= 0 encArg(z) -{ 0 }-> h(f(encArg(x_17), encArg(x_27)), f(encArg(x_19), encArg(x_29))) :|: z = 1 + (1 + x_17 + x_27) + (1 + x_19 + x_29), x_17 >= 0, x_27 >= 0, x_19 >= 0, x_29 >= 0 encArg(z) -{ 0 }-> h(f(encArg(x_17), encArg(x_27)), 0) :|: x_17 >= 0, x_27 >= 0, x_2 >= 0, z = 1 + (1 + x_17 + x_27) + x_2 encArg(z) -{ 0 }-> h(0, h(encArg(x_114), encArg(x_214))) :|: z = 1 + x_1 + (1 + x_114 + x_214), x_1 >= 0, x_114 >= 0, x_214 >= 0 encArg(z) -{ 0 }-> h(0, f(encArg(x_113), encArg(x_213))) :|: x_1 >= 0, x_113 >= 0, x_213 >= 0, z = 1 + x_1 + (1 + x_113 + x_213) encArg(z) -{ 0 }-> f(h(encArg(x_1''), encArg(x_2'')), h(encArg(x_14), encArg(x_24))) :|: x_1'' >= 0, x_14 >= 0, x_2'' >= 0, x_24 >= 0, z = 1 + (1 + x_1'' + x_2'') + (1 + x_14 + x_24) encArg(z) -{ 0 }-> f(h(encArg(x_1''), encArg(x_2'')), f(encArg(x_13), encArg(x_23))) :|: x_1'' >= 0, x_13 >= 0, x_2'' >= 0, x_23 >= 0, z = 1 + (1 + x_1'' + x_2'') + (1 + x_13 + x_23) encArg(z) -{ 0 }-> f(h(encArg(x_1''), encArg(x_2'')), 0) :|: x_1'' >= 0, z = 1 + (1 + x_1'' + x_2'') + x_2, x_2'' >= 0, x_2 >= 0 encArg(z) -{ 0 }-> f(f(encArg(x_1'), encArg(x_2')), h(encArg(x_12), encArg(x_22))) :|: x_2' >= 0, z = 1 + (1 + x_1' + x_2') + (1 + x_12 + x_22), x_1' >= 0, x_12 >= 0, x_22 >= 0 encArg(z) -{ 0 }-> f(f(encArg(x_1'), encArg(x_2')), f(encArg(x_11), encArg(x_21))) :|: x_11 >= 0, x_2' >= 0, x_1' >= 0, x_21 >= 0, z = 1 + (1 + x_1' + x_2') + (1 + x_11 + x_21) encArg(z) -{ 0 }-> f(f(encArg(x_1'), encArg(x_2')), 0) :|: z = 1 + (1 + x_1' + x_2') + x_2, x_2' >= 0, x_1' >= 0, x_2 >= 0 encArg(z) -{ 0 }-> f(0, h(encArg(x_16), encArg(x_26))) :|: x_1 >= 0, x_16 >= 0, x_26 >= 0, z = 1 + x_1 + (1 + x_16 + x_26) encArg(z) -{ 0 }-> f(0, f(encArg(x_15), encArg(x_25))) :|: x_15 >= 0, x_1 >= 0, x_25 >= 0, z = 1 + x_1 + (1 + x_15 + x_25) encArg(z) -{ 0 }-> 0 :|: z >= 0 encArg(z) -{ 0 }-> 0 :|: x_1 >= 0, z = 1 + x_1 + x_2, x_2 >= 0, v0 >= 0, v1 >= 0, 0 = v0, 0 = v1 encode_f(z, z') -{ 1 }-> h(x, y) :|: z >= 0, z' >= 0, x >= 0, y >= 0, 0 = x, 0 = y encode_f(z, z') -{ 1 }-> h(y, x) :|: z >= 0, z' >= 0, x >= 0, y >= 0, 0 = x, 0 = y encode_f(z, z') -{ 0 }-> f(h(encArg(x_116), encArg(x_216)), h(encArg(x_120), encArg(x_220))) :|: x_216 >= 0, x_120 >= 0, x_116 >= 0, z = 1 + x_116 + x_216, z' = 1 + x_120 + x_220, x_220 >= 0 encode_f(z, z') -{ 0 }-> f(h(encArg(x_116), encArg(x_216)), f(encArg(x_119), encArg(x_219))) :|: x_216 >= 0, z' = 1 + x_119 + x_219, x_116 >= 0, z = 1 + x_116 + x_216, x_219 >= 0, x_119 >= 0 encode_f(z, z') -{ 0 }-> f(h(encArg(x_116), encArg(x_216)), 0) :|: x_216 >= 0, x_116 >= 0, z = 1 + x_116 + x_216, z' >= 0 encode_f(z, z') -{ 0 }-> f(f(encArg(x_115), encArg(x_215)), h(encArg(x_118), encArg(x_218))) :|: x_215 >= 0, x_115 >= 0, z = 1 + x_115 + x_215, x_218 >= 0, z' = 1 + x_118 + x_218, x_118 >= 0 encode_f(z, z') -{ 0 }-> f(f(encArg(x_115), encArg(x_215)), f(encArg(x_117), encArg(x_217))) :|: x_117 >= 0, x_215 >= 0, x_115 >= 0, z = 1 + x_115 + x_215, z' = 1 + x_117 + x_217, x_217 >= 0 encode_f(z, z') -{ 0 }-> f(f(encArg(x_115), encArg(x_215)), 0) :|: x_215 >= 0, x_115 >= 0, z = 1 + x_115 + x_215, z' >= 0 encode_f(z, z') -{ 0 }-> f(0, h(encArg(x_122), encArg(x_222))) :|: z >= 0, x_222 >= 0, x_122 >= 0, z' = 1 + x_122 + x_222 encode_f(z, z') -{ 0 }-> f(0, f(encArg(x_121), encArg(x_221))) :|: z >= 0, z' = 1 + x_121 + x_221, x_221 >= 0, x_121 >= 0 encode_f(z, z') -{ 0 }-> 0 :|: z >= 0, z' >= 0 encode_h(z, z') -{ 1 }-> x :|: z >= 0, z' >= 0, 0 = x, x >= 0 encode_h(z, z') -{ 0 }-> h(h(encArg(x_124), encArg(x_224)), h(encArg(x_128), encArg(x_228))) :|: z = 1 + x_124 + x_224, x_124 >= 0, x_128 >= 0, z' = 1 + x_128 + x_228, x_224 >= 0, x_228 >= 0 encode_h(z, z') -{ 0 }-> h(h(encArg(x_124), encArg(x_224)), f(encArg(x_127), encArg(x_227))) :|: z = 1 + x_124 + x_224, x_124 >= 0, x_127 >= 0, x_224 >= 0, z' = 1 + x_127 + x_227, x_227 >= 0 encode_h(z, z') -{ 0 }-> h(h(encArg(x_124), encArg(x_224)), 0) :|: z = 1 + x_124 + x_224, x_124 >= 0, x_224 >= 0, z' >= 0 encode_h(z, z') -{ 0 }-> h(f(encArg(x_123), encArg(x_223)), h(encArg(x_126), encArg(x_226))) :|: z = 1 + x_123 + x_223, x_226 >= 0, x_123 >= 0, x_223 >= 0, x_126 >= 0, z' = 1 + x_126 + x_226 encode_h(z, z') -{ 0 }-> h(f(encArg(x_123), encArg(x_223)), f(encArg(x_125), encArg(x_225))) :|: z = 1 + x_123 + x_223, x_123 >= 0, z' = 1 + x_125 + x_225, x_223 >= 0, x_125 >= 0, x_225 >= 0 encode_h(z, z') -{ 0 }-> h(f(encArg(x_123), encArg(x_223)), 0) :|: z = 1 + x_123 + x_223, x_123 >= 0, x_223 >= 0, z' >= 0 encode_h(z, z') -{ 0 }-> h(0, h(encArg(x_130), encArg(x_230))) :|: z >= 0, x_130 >= 0, z' = 1 + x_130 + x_230, x_230 >= 0 encode_h(z, z') -{ 0 }-> h(0, f(encArg(x_129), encArg(x_229))) :|: z >= 0, z' = 1 + x_129 + x_229, x_229 >= 0, x_129 >= 0 encode_h(z, z') -{ 0 }-> 0 :|: z >= 0, z' >= 0 encode_h(z, z') -{ 0 }-> 0 :|: z >= 0, z' >= 0, v0 >= 0, v1 >= 0, 0 = v0, 0 = v1 f(z, z') -{ 2 }-> z' :|: z >= 0, z' >= 0, z = z' f(z, z') -{ 1 }-> 0 :|: z >= 0, z' >= 0 h(z, z') -{ 1 }-> z' :|: z' >= 0, z = z' h(z, z') -{ 0 }-> 0 :|: z >= 0, z' >= 0 Function symbols to be analyzed: {h}, {f}, {encArg}, {encode_f}, {encode_h} Previous analysis results are: h: runtime: ?, size: O(n^1) [z'] ---------------------------------------- (25) IntTrsBoundProof (UPPER BOUND(ID)) Computed RUNTIME bound using CoFloCo for: h after applying outer abstraction to obtain an ITS, resulting in: O(1) with polynomial bound: 1 ---------------------------------------- (26) Obligation: Complexity RNTS consisting of the following rules: encArg(z) -{ 1 }-> x :|: x_1 >= 0, z = 1 + x_1 + x_2, x_2 >= 0, 0 = x, x >= 0 encArg(z) -{ 1 }-> h(x, y) :|: x_1 >= 0, z = 1 + x_1 + x_2, x_2 >= 0, x >= 0, y >= 0, 0 = x, 0 = y encArg(z) -{ 1 }-> h(y, x) :|: x_1 >= 0, z = 1 + x_1 + x_2, x_2 >= 0, x >= 0, y >= 0, 0 = x, 0 = y encArg(z) -{ 0 }-> h(h(encArg(x_18), encArg(x_28)), h(encArg(x_112), encArg(x_212))) :|: x_212 >= 0, z = 1 + (1 + x_18 + x_28) + (1 + x_112 + x_212), x_18 >= 0, x_28 >= 0, x_112 >= 0 encArg(z) -{ 0 }-> h(h(encArg(x_18), encArg(x_28)), f(encArg(x_111), encArg(x_211))) :|: z = 1 + (1 + x_18 + x_28) + (1 + x_111 + x_211), x_18 >= 0, x_28 >= 0, x_211 >= 0, x_111 >= 0 encArg(z) -{ 0 }-> h(h(encArg(x_18), encArg(x_28)), 0) :|: z = 1 + (1 + x_18 + x_28) + x_2, x_2 >= 0, x_18 >= 0, x_28 >= 0 encArg(z) -{ 0 }-> h(f(encArg(x_17), encArg(x_27)), h(encArg(x_110), encArg(x_210))) :|: z = 1 + (1 + x_17 + x_27) + (1 + x_110 + x_210), x_17 >= 0, x_27 >= 0, x_110 >= 0, x_210 >= 0 encArg(z) -{ 0 }-> h(f(encArg(x_17), encArg(x_27)), f(encArg(x_19), encArg(x_29))) :|: z = 1 + (1 + x_17 + x_27) + (1 + x_19 + x_29), x_17 >= 0, x_27 >= 0, x_19 >= 0, x_29 >= 0 encArg(z) -{ 0 }-> h(f(encArg(x_17), encArg(x_27)), 0) :|: x_17 >= 0, x_27 >= 0, x_2 >= 0, z = 1 + (1 + x_17 + x_27) + x_2 encArg(z) -{ 0 }-> h(0, h(encArg(x_114), encArg(x_214))) :|: z = 1 + x_1 + (1 + x_114 + x_214), x_1 >= 0, x_114 >= 0, x_214 >= 0 encArg(z) -{ 0 }-> h(0, f(encArg(x_113), encArg(x_213))) :|: x_1 >= 0, x_113 >= 0, x_213 >= 0, z = 1 + x_1 + (1 + x_113 + x_213) encArg(z) -{ 0 }-> f(h(encArg(x_1''), encArg(x_2'')), h(encArg(x_14), encArg(x_24))) :|: x_1'' >= 0, x_14 >= 0, x_2'' >= 0, x_24 >= 0, z = 1 + (1 + x_1'' + x_2'') + (1 + x_14 + x_24) encArg(z) -{ 0 }-> f(h(encArg(x_1''), encArg(x_2'')), f(encArg(x_13), encArg(x_23))) :|: x_1'' >= 0, x_13 >= 0, x_2'' >= 0, x_23 >= 0, z = 1 + (1 + x_1'' + x_2'') + (1 + x_13 + x_23) encArg(z) -{ 0 }-> f(h(encArg(x_1''), encArg(x_2'')), 0) :|: x_1'' >= 0, z = 1 + (1 + x_1'' + x_2'') + x_2, x_2'' >= 0, x_2 >= 0 encArg(z) -{ 0 }-> f(f(encArg(x_1'), encArg(x_2')), h(encArg(x_12), encArg(x_22))) :|: x_2' >= 0, z = 1 + (1 + x_1' + x_2') + (1 + x_12 + x_22), x_1' >= 0, x_12 >= 0, x_22 >= 0 encArg(z) -{ 0 }-> f(f(encArg(x_1'), encArg(x_2')), f(encArg(x_11), encArg(x_21))) :|: x_11 >= 0, x_2' >= 0, x_1' >= 0, x_21 >= 0, z = 1 + (1 + x_1' + x_2') + (1 + x_11 + x_21) encArg(z) -{ 0 }-> f(f(encArg(x_1'), encArg(x_2')), 0) :|: z = 1 + (1 + x_1' + x_2') + x_2, x_2' >= 0, x_1' >= 0, x_2 >= 0 encArg(z) -{ 0 }-> f(0, h(encArg(x_16), encArg(x_26))) :|: x_1 >= 0, x_16 >= 0, x_26 >= 0, z = 1 + x_1 + (1 + x_16 + x_26) encArg(z) -{ 0 }-> f(0, f(encArg(x_15), encArg(x_25))) :|: x_15 >= 0, x_1 >= 0, x_25 >= 0, z = 1 + x_1 + (1 + x_15 + x_25) encArg(z) -{ 0 }-> 0 :|: z >= 0 encArg(z) -{ 0 }-> 0 :|: x_1 >= 0, z = 1 + x_1 + x_2, x_2 >= 0, v0 >= 0, v1 >= 0, 0 = v0, 0 = v1 encode_f(z, z') -{ 1 }-> h(x, y) :|: z >= 0, z' >= 0, x >= 0, y >= 0, 0 = x, 0 = y encode_f(z, z') -{ 1 }-> h(y, x) :|: z >= 0, z' >= 0, x >= 0, y >= 0, 0 = x, 0 = y encode_f(z, z') -{ 0 }-> f(h(encArg(x_116), encArg(x_216)), h(encArg(x_120), encArg(x_220))) :|: x_216 >= 0, x_120 >= 0, x_116 >= 0, z = 1 + x_116 + x_216, z' = 1 + x_120 + x_220, x_220 >= 0 encode_f(z, z') -{ 0 }-> f(h(encArg(x_116), encArg(x_216)), f(encArg(x_119), encArg(x_219))) :|: x_216 >= 0, z' = 1 + x_119 + x_219, x_116 >= 0, z = 1 + x_116 + x_216, x_219 >= 0, x_119 >= 0 encode_f(z, z') -{ 0 }-> f(h(encArg(x_116), encArg(x_216)), 0) :|: x_216 >= 0, x_116 >= 0, z = 1 + x_116 + x_216, z' >= 0 encode_f(z, z') -{ 0 }-> f(f(encArg(x_115), encArg(x_215)), h(encArg(x_118), encArg(x_218))) :|: x_215 >= 0, x_115 >= 0, z = 1 + x_115 + x_215, x_218 >= 0, z' = 1 + x_118 + x_218, x_118 >= 0 encode_f(z, z') -{ 0 }-> f(f(encArg(x_115), encArg(x_215)), f(encArg(x_117), encArg(x_217))) :|: x_117 >= 0, x_215 >= 0, x_115 >= 0, z = 1 + x_115 + x_215, z' = 1 + x_117 + x_217, x_217 >= 0 encode_f(z, z') -{ 0 }-> f(f(encArg(x_115), encArg(x_215)), 0) :|: x_215 >= 0, x_115 >= 0, z = 1 + x_115 + x_215, z' >= 0 encode_f(z, z') -{ 0 }-> f(0, h(encArg(x_122), encArg(x_222))) :|: z >= 0, x_222 >= 0, x_122 >= 0, z' = 1 + x_122 + x_222 encode_f(z, z') -{ 0 }-> f(0, f(encArg(x_121), encArg(x_221))) :|: z >= 0, z' = 1 + x_121 + x_221, x_221 >= 0, x_121 >= 0 encode_f(z, z') -{ 0 }-> 0 :|: z >= 0, z' >= 0 encode_h(z, z') -{ 1 }-> x :|: z >= 0, z' >= 0, 0 = x, x >= 0 encode_h(z, z') -{ 0 }-> h(h(encArg(x_124), encArg(x_224)), h(encArg(x_128), encArg(x_228))) :|: z = 1 + x_124 + x_224, x_124 >= 0, x_128 >= 0, z' = 1 + x_128 + x_228, x_224 >= 0, x_228 >= 0 encode_h(z, z') -{ 0 }-> h(h(encArg(x_124), encArg(x_224)), f(encArg(x_127), encArg(x_227))) :|: z = 1 + x_124 + x_224, x_124 >= 0, x_127 >= 0, x_224 >= 0, z' = 1 + x_127 + x_227, x_227 >= 0 encode_h(z, z') -{ 0 }-> h(h(encArg(x_124), encArg(x_224)), 0) :|: z = 1 + x_124 + x_224, x_124 >= 0, x_224 >= 0, z' >= 0 encode_h(z, z') -{ 0 }-> h(f(encArg(x_123), encArg(x_223)), h(encArg(x_126), encArg(x_226))) :|: z = 1 + x_123 + x_223, x_226 >= 0, x_123 >= 0, x_223 >= 0, x_126 >= 0, z' = 1 + x_126 + x_226 encode_h(z, z') -{ 0 }-> h(f(encArg(x_123), encArg(x_223)), f(encArg(x_125), encArg(x_225))) :|: z = 1 + x_123 + x_223, x_123 >= 0, z' = 1 + x_125 + x_225, x_223 >= 0, x_125 >= 0, x_225 >= 0 encode_h(z, z') -{ 0 }-> h(f(encArg(x_123), encArg(x_223)), 0) :|: z = 1 + x_123 + x_223, x_123 >= 0, x_223 >= 0, z' >= 0 encode_h(z, z') -{ 0 }-> h(0, h(encArg(x_130), encArg(x_230))) :|: z >= 0, x_130 >= 0, z' = 1 + x_130 + x_230, x_230 >= 0 encode_h(z, z') -{ 0 }-> h(0, f(encArg(x_129), encArg(x_229))) :|: z >= 0, z' = 1 + x_129 + x_229, x_229 >= 0, x_129 >= 0 encode_h(z, z') -{ 0 }-> 0 :|: z >= 0, z' >= 0 encode_h(z, z') -{ 0 }-> 0 :|: z >= 0, z' >= 0, v0 >= 0, v1 >= 0, 0 = v0, 0 = v1 f(z, z') -{ 2 }-> z' :|: z >= 0, z' >= 0, z = z' f(z, z') -{ 1 }-> 0 :|: z >= 0, z' >= 0 h(z, z') -{ 1 }-> z' :|: z' >= 0, z = z' h(z, z') -{ 0 }-> 0 :|: z >= 0, z' >= 0 Function symbols to be analyzed: {f}, {encArg}, {encode_f}, {encode_h} Previous analysis results are: h: runtime: O(1) [1], size: O(n^1) [z'] ---------------------------------------- (27) ResultPropagationProof (UPPER BOUND(ID)) Applied inner abstraction using the recently inferred runtime/size bounds where possible. ---------------------------------------- (28) Obligation: Complexity RNTS consisting of the following rules: encArg(z) -{ 2 }-> s :|: s >= 0, s <= y, x_1 >= 0, z = 1 + x_1 + x_2, x_2 >= 0, x >= 0, y >= 0, 0 = x, 0 = y encArg(z) -{ 2 }-> s' :|: s' >= 0, s' <= x, x_1 >= 0, z = 1 + x_1 + x_2, x_2 >= 0, x >= 0, y >= 0, 0 = x, 0 = y encArg(z) -{ 1 }-> x :|: x_1 >= 0, z = 1 + x_1 + x_2, x_2 >= 0, 0 = x, x >= 0 encArg(z) -{ 0 }-> h(h(encArg(x_18), encArg(x_28)), h(encArg(x_112), encArg(x_212))) :|: x_212 >= 0, z = 1 + (1 + x_18 + x_28) + (1 + x_112 + x_212), x_18 >= 0, x_28 >= 0, x_112 >= 0 encArg(z) -{ 0 }-> h(h(encArg(x_18), encArg(x_28)), f(encArg(x_111), encArg(x_211))) :|: z = 1 + (1 + x_18 + x_28) + (1 + x_111 + x_211), x_18 >= 0, x_28 >= 0, x_211 >= 0, x_111 >= 0 encArg(z) -{ 0 }-> h(h(encArg(x_18), encArg(x_28)), 0) :|: z = 1 + (1 + x_18 + x_28) + x_2, x_2 >= 0, x_18 >= 0, x_28 >= 0 encArg(z) -{ 0 }-> h(f(encArg(x_17), encArg(x_27)), h(encArg(x_110), encArg(x_210))) :|: z = 1 + (1 + x_17 + x_27) + (1 + x_110 + x_210), x_17 >= 0, x_27 >= 0, x_110 >= 0, x_210 >= 0 encArg(z) -{ 0 }-> h(f(encArg(x_17), encArg(x_27)), f(encArg(x_19), encArg(x_29))) :|: z = 1 + (1 + x_17 + x_27) + (1 + x_19 + x_29), x_17 >= 0, x_27 >= 0, x_19 >= 0, x_29 >= 0 encArg(z) -{ 0 }-> h(f(encArg(x_17), encArg(x_27)), 0) :|: x_17 >= 0, x_27 >= 0, x_2 >= 0, z = 1 + (1 + x_17 + x_27) + x_2 encArg(z) -{ 0 }-> h(0, h(encArg(x_114), encArg(x_214))) :|: z = 1 + x_1 + (1 + x_114 + x_214), x_1 >= 0, x_114 >= 0, x_214 >= 0 encArg(z) -{ 0 }-> h(0, f(encArg(x_113), encArg(x_213))) :|: x_1 >= 0, x_113 >= 0, x_213 >= 0, z = 1 + x_1 + (1 + x_113 + x_213) encArg(z) -{ 0 }-> f(h(encArg(x_1''), encArg(x_2'')), h(encArg(x_14), encArg(x_24))) :|: x_1'' >= 0, x_14 >= 0, x_2'' >= 0, x_24 >= 0, z = 1 + (1 + x_1'' + x_2'') + (1 + x_14 + x_24) encArg(z) -{ 0 }-> f(h(encArg(x_1''), encArg(x_2'')), f(encArg(x_13), encArg(x_23))) :|: x_1'' >= 0, x_13 >= 0, x_2'' >= 0, x_23 >= 0, z = 1 + (1 + x_1'' + x_2'') + (1 + x_13 + x_23) encArg(z) -{ 0 }-> f(h(encArg(x_1''), encArg(x_2'')), 0) :|: x_1'' >= 0, z = 1 + (1 + x_1'' + x_2'') + x_2, x_2'' >= 0, x_2 >= 0 encArg(z) -{ 0 }-> f(f(encArg(x_1'), encArg(x_2')), h(encArg(x_12), encArg(x_22))) :|: x_2' >= 0, z = 1 + (1 + x_1' + x_2') + (1 + x_12 + x_22), x_1' >= 0, x_12 >= 0, x_22 >= 0 encArg(z) -{ 0 }-> f(f(encArg(x_1'), encArg(x_2')), f(encArg(x_11), encArg(x_21))) :|: x_11 >= 0, x_2' >= 0, x_1' >= 0, x_21 >= 0, z = 1 + (1 + x_1' + x_2') + (1 + x_11 + x_21) encArg(z) -{ 0 }-> f(f(encArg(x_1'), encArg(x_2')), 0) :|: z = 1 + (1 + x_1' + x_2') + x_2, x_2' >= 0, x_1' >= 0, x_2 >= 0 encArg(z) -{ 0 }-> f(0, h(encArg(x_16), encArg(x_26))) :|: x_1 >= 0, x_16 >= 0, x_26 >= 0, z = 1 + x_1 + (1 + x_16 + x_26) encArg(z) -{ 0 }-> f(0, f(encArg(x_15), encArg(x_25))) :|: x_15 >= 0, x_1 >= 0, x_25 >= 0, z = 1 + x_1 + (1 + x_15 + x_25) encArg(z) -{ 0 }-> 0 :|: z >= 0 encArg(z) -{ 0 }-> 0 :|: x_1 >= 0, z = 1 + x_1 + x_2, x_2 >= 0, v0 >= 0, v1 >= 0, 0 = v0, 0 = v1 encode_f(z, z') -{ 2 }-> s'' :|: s'' >= 0, s'' <= y, z >= 0, z' >= 0, x >= 0, y >= 0, 0 = x, 0 = y encode_f(z, z') -{ 2 }-> s1 :|: s1 >= 0, s1 <= x, z >= 0, z' >= 0, x >= 0, y >= 0, 0 = x, 0 = y encode_f(z, z') -{ 0 }-> f(h(encArg(x_116), encArg(x_216)), h(encArg(x_120), encArg(x_220))) :|: x_216 >= 0, x_120 >= 0, x_116 >= 0, z = 1 + x_116 + x_216, z' = 1 + x_120 + x_220, x_220 >= 0 encode_f(z, z') -{ 0 }-> f(h(encArg(x_116), encArg(x_216)), f(encArg(x_119), encArg(x_219))) :|: x_216 >= 0, z' = 1 + x_119 + x_219, x_116 >= 0, z = 1 + x_116 + x_216, x_219 >= 0, x_119 >= 0 encode_f(z, z') -{ 0 }-> f(h(encArg(x_116), encArg(x_216)), 0) :|: x_216 >= 0, x_116 >= 0, z = 1 + x_116 + x_216, z' >= 0 encode_f(z, z') -{ 0 }-> f(f(encArg(x_115), encArg(x_215)), h(encArg(x_118), encArg(x_218))) :|: x_215 >= 0, x_115 >= 0, z = 1 + x_115 + x_215, x_218 >= 0, z' = 1 + x_118 + x_218, x_118 >= 0 encode_f(z, z') -{ 0 }-> f(f(encArg(x_115), encArg(x_215)), f(encArg(x_117), encArg(x_217))) :|: x_117 >= 0, x_215 >= 0, x_115 >= 0, z = 1 + x_115 + x_215, z' = 1 + x_117 + x_217, x_217 >= 0 encode_f(z, z') -{ 0 }-> f(f(encArg(x_115), encArg(x_215)), 0) :|: x_215 >= 0, x_115 >= 0, z = 1 + x_115 + x_215, z' >= 0 encode_f(z, z') -{ 0 }-> f(0, h(encArg(x_122), encArg(x_222))) :|: z >= 0, x_222 >= 0, x_122 >= 0, z' = 1 + x_122 + x_222 encode_f(z, z') -{ 0 }-> f(0, f(encArg(x_121), encArg(x_221))) :|: z >= 0, z' = 1 + x_121 + x_221, x_221 >= 0, x_121 >= 0 encode_f(z, z') -{ 0 }-> 0 :|: z >= 0, z' >= 0 encode_h(z, z') -{ 1 }-> x :|: z >= 0, z' >= 0, 0 = x, x >= 0 encode_h(z, z') -{ 0 }-> h(h(encArg(x_124), encArg(x_224)), h(encArg(x_128), encArg(x_228))) :|: z = 1 + x_124 + x_224, x_124 >= 0, x_128 >= 0, z' = 1 + x_128 + x_228, x_224 >= 0, x_228 >= 0 encode_h(z, z') -{ 0 }-> h(h(encArg(x_124), encArg(x_224)), f(encArg(x_127), encArg(x_227))) :|: z = 1 + x_124 + x_224, x_124 >= 0, x_127 >= 0, x_224 >= 0, z' = 1 + x_127 + x_227, x_227 >= 0 encode_h(z, z') -{ 0 }-> h(h(encArg(x_124), encArg(x_224)), 0) :|: z = 1 + x_124 + x_224, x_124 >= 0, x_224 >= 0, z' >= 0 encode_h(z, z') -{ 0 }-> h(f(encArg(x_123), encArg(x_223)), h(encArg(x_126), encArg(x_226))) :|: z = 1 + x_123 + x_223, x_226 >= 0, x_123 >= 0, x_223 >= 0, x_126 >= 0, z' = 1 + x_126 + x_226 encode_h(z, z') -{ 0 }-> h(f(encArg(x_123), encArg(x_223)), f(encArg(x_125), encArg(x_225))) :|: z = 1 + x_123 + x_223, x_123 >= 0, z' = 1 + x_125 + x_225, x_223 >= 0, x_125 >= 0, x_225 >= 0 encode_h(z, z') -{ 0 }-> h(f(encArg(x_123), encArg(x_223)), 0) :|: z = 1 + x_123 + x_223, x_123 >= 0, x_223 >= 0, z' >= 0 encode_h(z, z') -{ 0 }-> h(0, h(encArg(x_130), encArg(x_230))) :|: z >= 0, x_130 >= 0, z' = 1 + x_130 + x_230, x_230 >= 0 encode_h(z, z') -{ 0 }-> h(0, f(encArg(x_129), encArg(x_229))) :|: z >= 0, z' = 1 + x_129 + x_229, x_229 >= 0, x_129 >= 0 encode_h(z, z') -{ 0 }-> 0 :|: z >= 0, z' >= 0 encode_h(z, z') -{ 0 }-> 0 :|: z >= 0, z' >= 0, v0 >= 0, v1 >= 0, 0 = v0, 0 = v1 f(z, z') -{ 2 }-> z' :|: z >= 0, z' >= 0, z = z' f(z, z') -{ 1 }-> 0 :|: z >= 0, z' >= 0 h(z, z') -{ 1 }-> z' :|: z' >= 0, z = z' h(z, z') -{ 0 }-> 0 :|: z >= 0, z' >= 0 Function symbols to be analyzed: {f}, {encArg}, {encode_f}, {encode_h} Previous analysis results are: h: runtime: O(1) [1], size: O(n^1) [z'] ---------------------------------------- (29) IntTrsBoundProof (UPPER BOUND(ID)) Computed SIZE bound using CoFloCo for: f after applying outer abstraction to obtain an ITS, resulting in: O(n^1) with polynomial bound: z' ---------------------------------------- (30) Obligation: Complexity RNTS consisting of the following rules: encArg(z) -{ 2 }-> s :|: s >= 0, s <= y, x_1 >= 0, z = 1 + x_1 + x_2, x_2 >= 0, x >= 0, y >= 0, 0 = x, 0 = y encArg(z) -{ 2 }-> s' :|: s' >= 0, s' <= x, x_1 >= 0, z = 1 + x_1 + x_2, x_2 >= 0, x >= 0, y >= 0, 0 = x, 0 = y encArg(z) -{ 1 }-> x :|: x_1 >= 0, z = 1 + x_1 + x_2, x_2 >= 0, 0 = x, x >= 0 encArg(z) -{ 0 }-> h(h(encArg(x_18), encArg(x_28)), h(encArg(x_112), encArg(x_212))) :|: x_212 >= 0, z = 1 + (1 + x_18 + x_28) + (1 + x_112 + x_212), x_18 >= 0, x_28 >= 0, x_112 >= 0 encArg(z) -{ 0 }-> h(h(encArg(x_18), encArg(x_28)), f(encArg(x_111), encArg(x_211))) :|: z = 1 + (1 + x_18 + x_28) + (1 + x_111 + x_211), x_18 >= 0, x_28 >= 0, x_211 >= 0, x_111 >= 0 encArg(z) -{ 0 }-> h(h(encArg(x_18), encArg(x_28)), 0) :|: z = 1 + (1 + x_18 + x_28) + x_2, x_2 >= 0, x_18 >= 0, x_28 >= 0 encArg(z) -{ 0 }-> h(f(encArg(x_17), encArg(x_27)), h(encArg(x_110), encArg(x_210))) :|: z = 1 + (1 + x_17 + x_27) + (1 + x_110 + x_210), x_17 >= 0, x_27 >= 0, x_110 >= 0, x_210 >= 0 encArg(z) -{ 0 }-> h(f(encArg(x_17), encArg(x_27)), f(encArg(x_19), encArg(x_29))) :|: z = 1 + (1 + x_17 + x_27) + (1 + x_19 + x_29), x_17 >= 0, x_27 >= 0, x_19 >= 0, x_29 >= 0 encArg(z) -{ 0 }-> h(f(encArg(x_17), encArg(x_27)), 0) :|: x_17 >= 0, x_27 >= 0, x_2 >= 0, z = 1 + (1 + x_17 + x_27) + x_2 encArg(z) -{ 0 }-> h(0, h(encArg(x_114), encArg(x_214))) :|: z = 1 + x_1 + (1 + x_114 + x_214), x_1 >= 0, x_114 >= 0, x_214 >= 0 encArg(z) -{ 0 }-> h(0, f(encArg(x_113), encArg(x_213))) :|: x_1 >= 0, x_113 >= 0, x_213 >= 0, z = 1 + x_1 + (1 + x_113 + x_213) encArg(z) -{ 0 }-> f(h(encArg(x_1''), encArg(x_2'')), h(encArg(x_14), encArg(x_24))) :|: x_1'' >= 0, x_14 >= 0, x_2'' >= 0, x_24 >= 0, z = 1 + (1 + x_1'' + x_2'') + (1 + x_14 + x_24) encArg(z) -{ 0 }-> f(h(encArg(x_1''), encArg(x_2'')), f(encArg(x_13), encArg(x_23))) :|: x_1'' >= 0, x_13 >= 0, x_2'' >= 0, x_23 >= 0, z = 1 + (1 + x_1'' + x_2'') + (1 + x_13 + x_23) encArg(z) -{ 0 }-> f(h(encArg(x_1''), encArg(x_2'')), 0) :|: x_1'' >= 0, z = 1 + (1 + x_1'' + x_2'') + x_2, x_2'' >= 0, x_2 >= 0 encArg(z) -{ 0 }-> f(f(encArg(x_1'), encArg(x_2')), h(encArg(x_12), encArg(x_22))) :|: x_2' >= 0, z = 1 + (1 + x_1' + x_2') + (1 + x_12 + x_22), x_1' >= 0, x_12 >= 0, x_22 >= 0 encArg(z) -{ 0 }-> f(f(encArg(x_1'), encArg(x_2')), f(encArg(x_11), encArg(x_21))) :|: x_11 >= 0, x_2' >= 0, x_1' >= 0, x_21 >= 0, z = 1 + (1 + x_1' + x_2') + (1 + x_11 + x_21) encArg(z) -{ 0 }-> f(f(encArg(x_1'), encArg(x_2')), 0) :|: z = 1 + (1 + x_1' + x_2') + x_2, x_2' >= 0, x_1' >= 0, x_2 >= 0 encArg(z) -{ 0 }-> f(0, h(encArg(x_16), encArg(x_26))) :|: x_1 >= 0, x_16 >= 0, x_26 >= 0, z = 1 + x_1 + (1 + x_16 + x_26) encArg(z) -{ 0 }-> f(0, f(encArg(x_15), encArg(x_25))) :|: x_15 >= 0, x_1 >= 0, x_25 >= 0, z = 1 + x_1 + (1 + x_15 + x_25) encArg(z) -{ 0 }-> 0 :|: z >= 0 encArg(z) -{ 0 }-> 0 :|: x_1 >= 0, z = 1 + x_1 + x_2, x_2 >= 0, v0 >= 0, v1 >= 0, 0 = v0, 0 = v1 encode_f(z, z') -{ 2 }-> s'' :|: s'' >= 0, s'' <= y, z >= 0, z' >= 0, x >= 0, y >= 0, 0 = x, 0 = y encode_f(z, z') -{ 2 }-> s1 :|: s1 >= 0, s1 <= x, z >= 0, z' >= 0, x >= 0, y >= 0, 0 = x, 0 = y encode_f(z, z') -{ 0 }-> f(h(encArg(x_116), encArg(x_216)), h(encArg(x_120), encArg(x_220))) :|: x_216 >= 0, x_120 >= 0, x_116 >= 0, z = 1 + x_116 + x_216, z' = 1 + x_120 + x_220, x_220 >= 0 encode_f(z, z') -{ 0 }-> f(h(encArg(x_116), encArg(x_216)), f(encArg(x_119), encArg(x_219))) :|: x_216 >= 0, z' = 1 + x_119 + x_219, x_116 >= 0, z = 1 + x_116 + x_216, x_219 >= 0, x_119 >= 0 encode_f(z, z') -{ 0 }-> f(h(encArg(x_116), encArg(x_216)), 0) :|: x_216 >= 0, x_116 >= 0, z = 1 + x_116 + x_216, z' >= 0 encode_f(z, z') -{ 0 }-> f(f(encArg(x_115), encArg(x_215)), h(encArg(x_118), encArg(x_218))) :|: x_215 >= 0, x_115 >= 0, z = 1 + x_115 + x_215, x_218 >= 0, z' = 1 + x_118 + x_218, x_118 >= 0 encode_f(z, z') -{ 0 }-> f(f(encArg(x_115), encArg(x_215)), f(encArg(x_117), encArg(x_217))) :|: x_117 >= 0, x_215 >= 0, x_115 >= 0, z = 1 + x_115 + x_215, z' = 1 + x_117 + x_217, x_217 >= 0 encode_f(z, z') -{ 0 }-> f(f(encArg(x_115), encArg(x_215)), 0) :|: x_215 >= 0, x_115 >= 0, z = 1 + x_115 + x_215, z' >= 0 encode_f(z, z') -{ 0 }-> f(0, h(encArg(x_122), encArg(x_222))) :|: z >= 0, x_222 >= 0, x_122 >= 0, z' = 1 + x_122 + x_222 encode_f(z, z') -{ 0 }-> f(0, f(encArg(x_121), encArg(x_221))) :|: z >= 0, z' = 1 + x_121 + x_221, x_221 >= 0, x_121 >= 0 encode_f(z, z') -{ 0 }-> 0 :|: z >= 0, z' >= 0 encode_h(z, z') -{ 1 }-> x :|: z >= 0, z' >= 0, 0 = x, x >= 0 encode_h(z, z') -{ 0 }-> h(h(encArg(x_124), encArg(x_224)), h(encArg(x_128), encArg(x_228))) :|: z = 1 + x_124 + x_224, x_124 >= 0, x_128 >= 0, z' = 1 + x_128 + x_228, x_224 >= 0, x_228 >= 0 encode_h(z, z') -{ 0 }-> h(h(encArg(x_124), encArg(x_224)), f(encArg(x_127), encArg(x_227))) :|: z = 1 + x_124 + x_224, x_124 >= 0, x_127 >= 0, x_224 >= 0, z' = 1 + x_127 + x_227, x_227 >= 0 encode_h(z, z') -{ 0 }-> h(h(encArg(x_124), encArg(x_224)), 0) :|: z = 1 + x_124 + x_224, x_124 >= 0, x_224 >= 0, z' >= 0 encode_h(z, z') -{ 0 }-> h(f(encArg(x_123), encArg(x_223)), h(encArg(x_126), encArg(x_226))) :|: z = 1 + x_123 + x_223, x_226 >= 0, x_123 >= 0, x_223 >= 0, x_126 >= 0, z' = 1 + x_126 + x_226 encode_h(z, z') -{ 0 }-> h(f(encArg(x_123), encArg(x_223)), f(encArg(x_125), encArg(x_225))) :|: z = 1 + x_123 + x_223, x_123 >= 0, z' = 1 + x_125 + x_225, x_223 >= 0, x_125 >= 0, x_225 >= 0 encode_h(z, z') -{ 0 }-> h(f(encArg(x_123), encArg(x_223)), 0) :|: z = 1 + x_123 + x_223, x_123 >= 0, x_223 >= 0, z' >= 0 encode_h(z, z') -{ 0 }-> h(0, h(encArg(x_130), encArg(x_230))) :|: z >= 0, x_130 >= 0, z' = 1 + x_130 + x_230, x_230 >= 0 encode_h(z, z') -{ 0 }-> h(0, f(encArg(x_129), encArg(x_229))) :|: z >= 0, z' = 1 + x_129 + x_229, x_229 >= 0, x_129 >= 0 encode_h(z, z') -{ 0 }-> 0 :|: z >= 0, z' >= 0 encode_h(z, z') -{ 0 }-> 0 :|: z >= 0, z' >= 0, v0 >= 0, v1 >= 0, 0 = v0, 0 = v1 f(z, z') -{ 2 }-> z' :|: z >= 0, z' >= 0, z = z' f(z, z') -{ 1 }-> 0 :|: z >= 0, z' >= 0 h(z, z') -{ 1 }-> z' :|: z' >= 0, z = z' h(z, z') -{ 0 }-> 0 :|: z >= 0, z' >= 0 Function symbols to be analyzed: {f}, {encArg}, {encode_f}, {encode_h} Previous analysis results are: h: runtime: O(1) [1], size: O(n^1) [z'] f: runtime: ?, size: O(n^1) [z'] ---------------------------------------- (31) IntTrsBoundProof (UPPER BOUND(ID)) Computed RUNTIME bound using CoFloCo for: f after applying outer abstraction to obtain an ITS, resulting in: O(1) with polynomial bound: 2 ---------------------------------------- (32) Obligation: Complexity RNTS consisting of the following rules: encArg(z) -{ 2 }-> s :|: s >= 0, s <= y, x_1 >= 0, z = 1 + x_1 + x_2, x_2 >= 0, x >= 0, y >= 0, 0 = x, 0 = y encArg(z) -{ 2 }-> s' :|: s' >= 0, s' <= x, x_1 >= 0, z = 1 + x_1 + x_2, x_2 >= 0, x >= 0, y >= 0, 0 = x, 0 = y encArg(z) -{ 1 }-> x :|: x_1 >= 0, z = 1 + x_1 + x_2, x_2 >= 0, 0 = x, x >= 0 encArg(z) -{ 0 }-> h(h(encArg(x_18), encArg(x_28)), h(encArg(x_112), encArg(x_212))) :|: x_212 >= 0, z = 1 + (1 + x_18 + x_28) + (1 + x_112 + x_212), x_18 >= 0, x_28 >= 0, x_112 >= 0 encArg(z) -{ 0 }-> h(h(encArg(x_18), encArg(x_28)), f(encArg(x_111), encArg(x_211))) :|: z = 1 + (1 + x_18 + x_28) + (1 + x_111 + x_211), x_18 >= 0, x_28 >= 0, x_211 >= 0, x_111 >= 0 encArg(z) -{ 0 }-> h(h(encArg(x_18), encArg(x_28)), 0) :|: z = 1 + (1 + x_18 + x_28) + x_2, x_2 >= 0, x_18 >= 0, x_28 >= 0 encArg(z) -{ 0 }-> h(f(encArg(x_17), encArg(x_27)), h(encArg(x_110), encArg(x_210))) :|: z = 1 + (1 + x_17 + x_27) + (1 + x_110 + x_210), x_17 >= 0, x_27 >= 0, x_110 >= 0, x_210 >= 0 encArg(z) -{ 0 }-> h(f(encArg(x_17), encArg(x_27)), f(encArg(x_19), encArg(x_29))) :|: z = 1 + (1 + x_17 + x_27) + (1 + x_19 + x_29), x_17 >= 0, x_27 >= 0, x_19 >= 0, x_29 >= 0 encArg(z) -{ 0 }-> h(f(encArg(x_17), encArg(x_27)), 0) :|: x_17 >= 0, x_27 >= 0, x_2 >= 0, z = 1 + (1 + x_17 + x_27) + x_2 encArg(z) -{ 0 }-> h(0, h(encArg(x_114), encArg(x_214))) :|: z = 1 + x_1 + (1 + x_114 + x_214), x_1 >= 0, x_114 >= 0, x_214 >= 0 encArg(z) -{ 0 }-> h(0, f(encArg(x_113), encArg(x_213))) :|: x_1 >= 0, x_113 >= 0, x_213 >= 0, z = 1 + x_1 + (1 + x_113 + x_213) encArg(z) -{ 0 }-> f(h(encArg(x_1''), encArg(x_2'')), h(encArg(x_14), encArg(x_24))) :|: x_1'' >= 0, x_14 >= 0, x_2'' >= 0, x_24 >= 0, z = 1 + (1 + x_1'' + x_2'') + (1 + x_14 + x_24) encArg(z) -{ 0 }-> f(h(encArg(x_1''), encArg(x_2'')), f(encArg(x_13), encArg(x_23))) :|: x_1'' >= 0, x_13 >= 0, x_2'' >= 0, x_23 >= 0, z = 1 + (1 + x_1'' + x_2'') + (1 + x_13 + x_23) encArg(z) -{ 0 }-> f(h(encArg(x_1''), encArg(x_2'')), 0) :|: x_1'' >= 0, z = 1 + (1 + x_1'' + x_2'') + x_2, x_2'' >= 0, x_2 >= 0 encArg(z) -{ 0 }-> f(f(encArg(x_1'), encArg(x_2')), h(encArg(x_12), encArg(x_22))) :|: x_2' >= 0, z = 1 + (1 + x_1' + x_2') + (1 + x_12 + x_22), x_1' >= 0, x_12 >= 0, x_22 >= 0 encArg(z) -{ 0 }-> f(f(encArg(x_1'), encArg(x_2')), f(encArg(x_11), encArg(x_21))) :|: x_11 >= 0, x_2' >= 0, x_1' >= 0, x_21 >= 0, z = 1 + (1 + x_1' + x_2') + (1 + x_11 + x_21) encArg(z) -{ 0 }-> f(f(encArg(x_1'), encArg(x_2')), 0) :|: z = 1 + (1 + x_1' + x_2') + x_2, x_2' >= 0, x_1' >= 0, x_2 >= 0 encArg(z) -{ 0 }-> f(0, h(encArg(x_16), encArg(x_26))) :|: x_1 >= 0, x_16 >= 0, x_26 >= 0, z = 1 + x_1 + (1 + x_16 + x_26) encArg(z) -{ 0 }-> f(0, f(encArg(x_15), encArg(x_25))) :|: x_15 >= 0, x_1 >= 0, x_25 >= 0, z = 1 + x_1 + (1 + x_15 + x_25) encArg(z) -{ 0 }-> 0 :|: z >= 0 encArg(z) -{ 0 }-> 0 :|: x_1 >= 0, z = 1 + x_1 + x_2, x_2 >= 0, v0 >= 0, v1 >= 0, 0 = v0, 0 = v1 encode_f(z, z') -{ 2 }-> s'' :|: s'' >= 0, s'' <= y, z >= 0, z' >= 0, x >= 0, y >= 0, 0 = x, 0 = y encode_f(z, z') -{ 2 }-> s1 :|: s1 >= 0, s1 <= x, z >= 0, z' >= 0, x >= 0, y >= 0, 0 = x, 0 = y encode_f(z, z') -{ 0 }-> f(h(encArg(x_116), encArg(x_216)), h(encArg(x_120), encArg(x_220))) :|: x_216 >= 0, x_120 >= 0, x_116 >= 0, z = 1 + x_116 + x_216, z' = 1 + x_120 + x_220, x_220 >= 0 encode_f(z, z') -{ 0 }-> f(h(encArg(x_116), encArg(x_216)), f(encArg(x_119), encArg(x_219))) :|: x_216 >= 0, z' = 1 + x_119 + x_219, x_116 >= 0, z = 1 + x_116 + x_216, x_219 >= 0, x_119 >= 0 encode_f(z, z') -{ 0 }-> f(h(encArg(x_116), encArg(x_216)), 0) :|: x_216 >= 0, x_116 >= 0, z = 1 + x_116 + x_216, z' >= 0 encode_f(z, z') -{ 0 }-> f(f(encArg(x_115), encArg(x_215)), h(encArg(x_118), encArg(x_218))) :|: x_215 >= 0, x_115 >= 0, z = 1 + x_115 + x_215, x_218 >= 0, z' = 1 + x_118 + x_218, x_118 >= 0 encode_f(z, z') -{ 0 }-> f(f(encArg(x_115), encArg(x_215)), f(encArg(x_117), encArg(x_217))) :|: x_117 >= 0, x_215 >= 0, x_115 >= 0, z = 1 + x_115 + x_215, z' = 1 + x_117 + x_217, x_217 >= 0 encode_f(z, z') -{ 0 }-> f(f(encArg(x_115), encArg(x_215)), 0) :|: x_215 >= 0, x_115 >= 0, z = 1 + x_115 + x_215, z' >= 0 encode_f(z, z') -{ 0 }-> f(0, h(encArg(x_122), encArg(x_222))) :|: z >= 0, x_222 >= 0, x_122 >= 0, z' = 1 + x_122 + x_222 encode_f(z, z') -{ 0 }-> f(0, f(encArg(x_121), encArg(x_221))) :|: z >= 0, z' = 1 + x_121 + x_221, x_221 >= 0, x_121 >= 0 encode_f(z, z') -{ 0 }-> 0 :|: z >= 0, z' >= 0 encode_h(z, z') -{ 1 }-> x :|: z >= 0, z' >= 0, 0 = x, x >= 0 encode_h(z, z') -{ 0 }-> h(h(encArg(x_124), encArg(x_224)), h(encArg(x_128), encArg(x_228))) :|: z = 1 + x_124 + x_224, x_124 >= 0, x_128 >= 0, z' = 1 + x_128 + x_228, x_224 >= 0, x_228 >= 0 encode_h(z, z') -{ 0 }-> h(h(encArg(x_124), encArg(x_224)), f(encArg(x_127), encArg(x_227))) :|: z = 1 + x_124 + x_224, x_124 >= 0, x_127 >= 0, x_224 >= 0, z' = 1 + x_127 + x_227, x_227 >= 0 encode_h(z, z') -{ 0 }-> h(h(encArg(x_124), encArg(x_224)), 0) :|: z = 1 + x_124 + x_224, x_124 >= 0, x_224 >= 0, z' >= 0 encode_h(z, z') -{ 0 }-> h(f(encArg(x_123), encArg(x_223)), h(encArg(x_126), encArg(x_226))) :|: z = 1 + x_123 + x_223, x_226 >= 0, x_123 >= 0, x_223 >= 0, x_126 >= 0, z' = 1 + x_126 + x_226 encode_h(z, z') -{ 0 }-> h(f(encArg(x_123), encArg(x_223)), f(encArg(x_125), encArg(x_225))) :|: z = 1 + x_123 + x_223, x_123 >= 0, z' = 1 + x_125 + x_225, x_223 >= 0, x_125 >= 0, x_225 >= 0 encode_h(z, z') -{ 0 }-> h(f(encArg(x_123), encArg(x_223)), 0) :|: z = 1 + x_123 + x_223, x_123 >= 0, x_223 >= 0, z' >= 0 encode_h(z, z') -{ 0 }-> h(0, h(encArg(x_130), encArg(x_230))) :|: z >= 0, x_130 >= 0, z' = 1 + x_130 + x_230, x_230 >= 0 encode_h(z, z') -{ 0 }-> h(0, f(encArg(x_129), encArg(x_229))) :|: z >= 0, z' = 1 + x_129 + x_229, x_229 >= 0, x_129 >= 0 encode_h(z, z') -{ 0 }-> 0 :|: z >= 0, z' >= 0 encode_h(z, z') -{ 0 }-> 0 :|: z >= 0, z' >= 0, v0 >= 0, v1 >= 0, 0 = v0, 0 = v1 f(z, z') -{ 2 }-> z' :|: z >= 0, z' >= 0, z = z' f(z, z') -{ 1 }-> 0 :|: z >= 0, z' >= 0 h(z, z') -{ 1 }-> z' :|: z' >= 0, z = z' h(z, z') -{ 0 }-> 0 :|: z >= 0, z' >= 0 Function symbols to be analyzed: {encArg}, {encode_f}, {encode_h} Previous analysis results are: h: runtime: O(1) [1], size: O(n^1) [z'] f: runtime: O(1) [2], size: O(n^1) [z'] ---------------------------------------- (33) ResultPropagationProof (UPPER BOUND(ID)) Applied inner abstraction using the recently inferred runtime/size bounds where possible. ---------------------------------------- (34) Obligation: Complexity RNTS consisting of the following rules: encArg(z) -{ 2 }-> s :|: s >= 0, s <= y, x_1 >= 0, z = 1 + x_1 + x_2, x_2 >= 0, x >= 0, y >= 0, 0 = x, 0 = y encArg(z) -{ 2 }-> s' :|: s' >= 0, s' <= x, x_1 >= 0, z = 1 + x_1 + x_2, x_2 >= 0, x >= 0, y >= 0, 0 = x, 0 = y encArg(z) -{ 1 }-> x :|: x_1 >= 0, z = 1 + x_1 + x_2, x_2 >= 0, 0 = x, x >= 0 encArg(z) -{ 0 }-> h(h(encArg(x_18), encArg(x_28)), h(encArg(x_112), encArg(x_212))) :|: x_212 >= 0, z = 1 + (1 + x_18 + x_28) + (1 + x_112 + x_212), x_18 >= 0, x_28 >= 0, x_112 >= 0 encArg(z) -{ 0 }-> h(h(encArg(x_18), encArg(x_28)), f(encArg(x_111), encArg(x_211))) :|: z = 1 + (1 + x_18 + x_28) + (1 + x_111 + x_211), x_18 >= 0, x_28 >= 0, x_211 >= 0, x_111 >= 0 encArg(z) -{ 0 }-> h(h(encArg(x_18), encArg(x_28)), 0) :|: z = 1 + (1 + x_18 + x_28) + x_2, x_2 >= 0, x_18 >= 0, x_28 >= 0 encArg(z) -{ 0 }-> h(f(encArg(x_17), encArg(x_27)), h(encArg(x_110), encArg(x_210))) :|: z = 1 + (1 + x_17 + x_27) + (1 + x_110 + x_210), x_17 >= 0, x_27 >= 0, x_110 >= 0, x_210 >= 0 encArg(z) -{ 0 }-> h(f(encArg(x_17), encArg(x_27)), f(encArg(x_19), encArg(x_29))) :|: z = 1 + (1 + x_17 + x_27) + (1 + x_19 + x_29), x_17 >= 0, x_27 >= 0, x_19 >= 0, x_29 >= 0 encArg(z) -{ 0 }-> h(f(encArg(x_17), encArg(x_27)), 0) :|: x_17 >= 0, x_27 >= 0, x_2 >= 0, z = 1 + (1 + x_17 + x_27) + x_2 encArg(z) -{ 0 }-> h(0, h(encArg(x_114), encArg(x_214))) :|: z = 1 + x_1 + (1 + x_114 + x_214), x_1 >= 0, x_114 >= 0, x_214 >= 0 encArg(z) -{ 0 }-> h(0, f(encArg(x_113), encArg(x_213))) :|: x_1 >= 0, x_113 >= 0, x_213 >= 0, z = 1 + x_1 + (1 + x_113 + x_213) encArg(z) -{ 0 }-> f(h(encArg(x_1''), encArg(x_2'')), h(encArg(x_14), encArg(x_24))) :|: x_1'' >= 0, x_14 >= 0, x_2'' >= 0, x_24 >= 0, z = 1 + (1 + x_1'' + x_2'') + (1 + x_14 + x_24) encArg(z) -{ 0 }-> f(h(encArg(x_1''), encArg(x_2'')), f(encArg(x_13), encArg(x_23))) :|: x_1'' >= 0, x_13 >= 0, x_2'' >= 0, x_23 >= 0, z = 1 + (1 + x_1'' + x_2'') + (1 + x_13 + x_23) encArg(z) -{ 0 }-> f(h(encArg(x_1''), encArg(x_2'')), 0) :|: x_1'' >= 0, z = 1 + (1 + x_1'' + x_2'') + x_2, x_2'' >= 0, x_2 >= 0 encArg(z) -{ 0 }-> f(f(encArg(x_1'), encArg(x_2')), h(encArg(x_12), encArg(x_22))) :|: x_2' >= 0, z = 1 + (1 + x_1' + x_2') + (1 + x_12 + x_22), x_1' >= 0, x_12 >= 0, x_22 >= 0 encArg(z) -{ 0 }-> f(f(encArg(x_1'), encArg(x_2')), f(encArg(x_11), encArg(x_21))) :|: x_11 >= 0, x_2' >= 0, x_1' >= 0, x_21 >= 0, z = 1 + (1 + x_1' + x_2') + (1 + x_11 + x_21) encArg(z) -{ 0 }-> f(f(encArg(x_1'), encArg(x_2')), 0) :|: z = 1 + (1 + x_1' + x_2') + x_2, x_2' >= 0, x_1' >= 0, x_2 >= 0 encArg(z) -{ 0 }-> f(0, h(encArg(x_16), encArg(x_26))) :|: x_1 >= 0, x_16 >= 0, x_26 >= 0, z = 1 + x_1 + (1 + x_16 + x_26) encArg(z) -{ 0 }-> f(0, f(encArg(x_15), encArg(x_25))) :|: x_15 >= 0, x_1 >= 0, x_25 >= 0, z = 1 + x_1 + (1 + x_15 + x_25) encArg(z) -{ 0 }-> 0 :|: z >= 0 encArg(z) -{ 0 }-> 0 :|: x_1 >= 0, z = 1 + x_1 + x_2, x_2 >= 0, v0 >= 0, v1 >= 0, 0 = v0, 0 = v1 encode_f(z, z') -{ 2 }-> s'' :|: s'' >= 0, s'' <= y, z >= 0, z' >= 0, x >= 0, y >= 0, 0 = x, 0 = y encode_f(z, z') -{ 2 }-> s1 :|: s1 >= 0, s1 <= x, z >= 0, z' >= 0, x >= 0, y >= 0, 0 = x, 0 = y encode_f(z, z') -{ 0 }-> f(h(encArg(x_116), encArg(x_216)), h(encArg(x_120), encArg(x_220))) :|: x_216 >= 0, x_120 >= 0, x_116 >= 0, z = 1 + x_116 + x_216, z' = 1 + x_120 + x_220, x_220 >= 0 encode_f(z, z') -{ 0 }-> f(h(encArg(x_116), encArg(x_216)), f(encArg(x_119), encArg(x_219))) :|: x_216 >= 0, z' = 1 + x_119 + x_219, x_116 >= 0, z = 1 + x_116 + x_216, x_219 >= 0, x_119 >= 0 encode_f(z, z') -{ 0 }-> f(h(encArg(x_116), encArg(x_216)), 0) :|: x_216 >= 0, x_116 >= 0, z = 1 + x_116 + x_216, z' >= 0 encode_f(z, z') -{ 0 }-> f(f(encArg(x_115), encArg(x_215)), h(encArg(x_118), encArg(x_218))) :|: x_215 >= 0, x_115 >= 0, z = 1 + x_115 + x_215, x_218 >= 0, z' = 1 + x_118 + x_218, x_118 >= 0 encode_f(z, z') -{ 0 }-> f(f(encArg(x_115), encArg(x_215)), f(encArg(x_117), encArg(x_217))) :|: x_117 >= 0, x_215 >= 0, x_115 >= 0, z = 1 + x_115 + x_215, z' = 1 + x_117 + x_217, x_217 >= 0 encode_f(z, z') -{ 0 }-> f(f(encArg(x_115), encArg(x_215)), 0) :|: x_215 >= 0, x_115 >= 0, z = 1 + x_115 + x_215, z' >= 0 encode_f(z, z') -{ 0 }-> f(0, h(encArg(x_122), encArg(x_222))) :|: z >= 0, x_222 >= 0, x_122 >= 0, z' = 1 + x_122 + x_222 encode_f(z, z') -{ 0 }-> f(0, f(encArg(x_121), encArg(x_221))) :|: z >= 0, z' = 1 + x_121 + x_221, x_221 >= 0, x_121 >= 0 encode_f(z, z') -{ 0 }-> 0 :|: z >= 0, z' >= 0 encode_h(z, z') -{ 1 }-> x :|: z >= 0, z' >= 0, 0 = x, x >= 0 encode_h(z, z') -{ 0 }-> h(h(encArg(x_124), encArg(x_224)), h(encArg(x_128), encArg(x_228))) :|: z = 1 + x_124 + x_224, x_124 >= 0, x_128 >= 0, z' = 1 + x_128 + x_228, x_224 >= 0, x_228 >= 0 encode_h(z, z') -{ 0 }-> h(h(encArg(x_124), encArg(x_224)), f(encArg(x_127), encArg(x_227))) :|: z = 1 + x_124 + x_224, x_124 >= 0, x_127 >= 0, x_224 >= 0, z' = 1 + x_127 + x_227, x_227 >= 0 encode_h(z, z') -{ 0 }-> h(h(encArg(x_124), encArg(x_224)), 0) :|: z = 1 + x_124 + x_224, x_124 >= 0, x_224 >= 0, z' >= 0 encode_h(z, z') -{ 0 }-> h(f(encArg(x_123), encArg(x_223)), h(encArg(x_126), encArg(x_226))) :|: z = 1 + x_123 + x_223, x_226 >= 0, x_123 >= 0, x_223 >= 0, x_126 >= 0, z' = 1 + x_126 + x_226 encode_h(z, z') -{ 0 }-> h(f(encArg(x_123), encArg(x_223)), f(encArg(x_125), encArg(x_225))) :|: z = 1 + x_123 + x_223, x_123 >= 0, z' = 1 + x_125 + x_225, x_223 >= 0, x_125 >= 0, x_225 >= 0 encode_h(z, z') -{ 0 }-> h(f(encArg(x_123), encArg(x_223)), 0) :|: z = 1 + x_123 + x_223, x_123 >= 0, x_223 >= 0, z' >= 0 encode_h(z, z') -{ 0 }-> h(0, h(encArg(x_130), encArg(x_230))) :|: z >= 0, x_130 >= 0, z' = 1 + x_130 + x_230, x_230 >= 0 encode_h(z, z') -{ 0 }-> h(0, f(encArg(x_129), encArg(x_229))) :|: z >= 0, z' = 1 + x_129 + x_229, x_229 >= 0, x_129 >= 0 encode_h(z, z') -{ 0 }-> 0 :|: z >= 0, z' >= 0 encode_h(z, z') -{ 0 }-> 0 :|: z >= 0, z' >= 0, v0 >= 0, v1 >= 0, 0 = v0, 0 = v1 f(z, z') -{ 2 }-> z' :|: z >= 0, z' >= 0, z = z' f(z, z') -{ 1 }-> 0 :|: z >= 0, z' >= 0 h(z, z') -{ 1 }-> z' :|: z' >= 0, z = z' h(z, z') -{ 0 }-> 0 :|: z >= 0, z' >= 0 Function symbols to be analyzed: {encArg}, {encode_f}, {encode_h} Previous analysis results are: h: runtime: O(1) [1], size: O(n^1) [z'] f: runtime: O(1) [2], size: O(n^1) [z'] ---------------------------------------- (35) IntTrsBoundProof (UPPER BOUND(ID)) Computed SIZE bound using CoFloCo for: encArg after applying outer abstraction to obtain an ITS, resulting in: O(1) with polynomial bound: 0 ---------------------------------------- (36) Obligation: Complexity RNTS consisting of the following rules: encArg(z) -{ 2 }-> s :|: s >= 0, s <= y, x_1 >= 0, z = 1 + x_1 + x_2, x_2 >= 0, x >= 0, y >= 0, 0 = x, 0 = y encArg(z) -{ 2 }-> s' :|: s' >= 0, s' <= x, x_1 >= 0, z = 1 + x_1 + x_2, x_2 >= 0, x >= 0, y >= 0, 0 = x, 0 = y encArg(z) -{ 1 }-> x :|: x_1 >= 0, z = 1 + x_1 + x_2, x_2 >= 0, 0 = x, x >= 0 encArg(z) -{ 0 }-> h(h(encArg(x_18), encArg(x_28)), h(encArg(x_112), encArg(x_212))) :|: x_212 >= 0, z = 1 + (1 + x_18 + x_28) + (1 + x_112 + x_212), x_18 >= 0, x_28 >= 0, x_112 >= 0 encArg(z) -{ 0 }-> h(h(encArg(x_18), encArg(x_28)), f(encArg(x_111), encArg(x_211))) :|: z = 1 + (1 + x_18 + x_28) + (1 + x_111 + x_211), x_18 >= 0, x_28 >= 0, x_211 >= 0, x_111 >= 0 encArg(z) -{ 0 }-> h(h(encArg(x_18), encArg(x_28)), 0) :|: z = 1 + (1 + x_18 + x_28) + x_2, x_2 >= 0, x_18 >= 0, x_28 >= 0 encArg(z) -{ 0 }-> h(f(encArg(x_17), encArg(x_27)), h(encArg(x_110), encArg(x_210))) :|: z = 1 + (1 + x_17 + x_27) + (1 + x_110 + x_210), x_17 >= 0, x_27 >= 0, x_110 >= 0, x_210 >= 0 encArg(z) -{ 0 }-> h(f(encArg(x_17), encArg(x_27)), f(encArg(x_19), encArg(x_29))) :|: z = 1 + (1 + x_17 + x_27) + (1 + x_19 + x_29), x_17 >= 0, x_27 >= 0, x_19 >= 0, x_29 >= 0 encArg(z) -{ 0 }-> h(f(encArg(x_17), encArg(x_27)), 0) :|: x_17 >= 0, x_27 >= 0, x_2 >= 0, z = 1 + (1 + x_17 + x_27) + x_2 encArg(z) -{ 0 }-> h(0, h(encArg(x_114), encArg(x_214))) :|: z = 1 + x_1 + (1 + x_114 + x_214), x_1 >= 0, x_114 >= 0, x_214 >= 0 encArg(z) -{ 0 }-> h(0, f(encArg(x_113), encArg(x_213))) :|: x_1 >= 0, x_113 >= 0, x_213 >= 0, z = 1 + x_1 + (1 + x_113 + x_213) encArg(z) -{ 0 }-> f(h(encArg(x_1''), encArg(x_2'')), h(encArg(x_14), encArg(x_24))) :|: x_1'' >= 0, x_14 >= 0, x_2'' >= 0, x_24 >= 0, z = 1 + (1 + x_1'' + x_2'') + (1 + x_14 + x_24) encArg(z) -{ 0 }-> f(h(encArg(x_1''), encArg(x_2'')), f(encArg(x_13), encArg(x_23))) :|: x_1'' >= 0, x_13 >= 0, x_2'' >= 0, x_23 >= 0, z = 1 + (1 + x_1'' + x_2'') + (1 + x_13 + x_23) encArg(z) -{ 0 }-> f(h(encArg(x_1''), encArg(x_2'')), 0) :|: x_1'' >= 0, z = 1 + (1 + x_1'' + x_2'') + x_2, x_2'' >= 0, x_2 >= 0 encArg(z) -{ 0 }-> f(f(encArg(x_1'), encArg(x_2')), h(encArg(x_12), encArg(x_22))) :|: x_2' >= 0, z = 1 + (1 + x_1' + x_2') + (1 + x_12 + x_22), x_1' >= 0, x_12 >= 0, x_22 >= 0 encArg(z) -{ 0 }-> f(f(encArg(x_1'), encArg(x_2')), f(encArg(x_11), encArg(x_21))) :|: x_11 >= 0, x_2' >= 0, x_1' >= 0, x_21 >= 0, z = 1 + (1 + x_1' + x_2') + (1 + x_11 + x_21) encArg(z) -{ 0 }-> f(f(encArg(x_1'), encArg(x_2')), 0) :|: z = 1 + (1 + x_1' + x_2') + x_2, x_2' >= 0, x_1' >= 0, x_2 >= 0 encArg(z) -{ 0 }-> f(0, h(encArg(x_16), encArg(x_26))) :|: x_1 >= 0, x_16 >= 0, x_26 >= 0, z = 1 + x_1 + (1 + x_16 + x_26) encArg(z) -{ 0 }-> f(0, f(encArg(x_15), encArg(x_25))) :|: x_15 >= 0, x_1 >= 0, x_25 >= 0, z = 1 + x_1 + (1 + x_15 + x_25) encArg(z) -{ 0 }-> 0 :|: z >= 0 encArg(z) -{ 0 }-> 0 :|: x_1 >= 0, z = 1 + x_1 + x_2, x_2 >= 0, v0 >= 0, v1 >= 0, 0 = v0, 0 = v1 encode_f(z, z') -{ 2 }-> s'' :|: s'' >= 0, s'' <= y, z >= 0, z' >= 0, x >= 0, y >= 0, 0 = x, 0 = y encode_f(z, z') -{ 2 }-> s1 :|: s1 >= 0, s1 <= x, z >= 0, z' >= 0, x >= 0, y >= 0, 0 = x, 0 = y encode_f(z, z') -{ 0 }-> f(h(encArg(x_116), encArg(x_216)), h(encArg(x_120), encArg(x_220))) :|: x_216 >= 0, x_120 >= 0, x_116 >= 0, z = 1 + x_116 + x_216, z' = 1 + x_120 + x_220, x_220 >= 0 encode_f(z, z') -{ 0 }-> f(h(encArg(x_116), encArg(x_216)), f(encArg(x_119), encArg(x_219))) :|: x_216 >= 0, z' = 1 + x_119 + x_219, x_116 >= 0, z = 1 + x_116 + x_216, x_219 >= 0, x_119 >= 0 encode_f(z, z') -{ 0 }-> f(h(encArg(x_116), encArg(x_216)), 0) :|: x_216 >= 0, x_116 >= 0, z = 1 + x_116 + x_216, z' >= 0 encode_f(z, z') -{ 0 }-> f(f(encArg(x_115), encArg(x_215)), h(encArg(x_118), encArg(x_218))) :|: x_215 >= 0, x_115 >= 0, z = 1 + x_115 + x_215, x_218 >= 0, z' = 1 + x_118 + x_218, x_118 >= 0 encode_f(z, z') -{ 0 }-> f(f(encArg(x_115), encArg(x_215)), f(encArg(x_117), encArg(x_217))) :|: x_117 >= 0, x_215 >= 0, x_115 >= 0, z = 1 + x_115 + x_215, z' = 1 + x_117 + x_217, x_217 >= 0 encode_f(z, z') -{ 0 }-> f(f(encArg(x_115), encArg(x_215)), 0) :|: x_215 >= 0, x_115 >= 0, z = 1 + x_115 + x_215, z' >= 0 encode_f(z, z') -{ 0 }-> f(0, h(encArg(x_122), encArg(x_222))) :|: z >= 0, x_222 >= 0, x_122 >= 0, z' = 1 + x_122 + x_222 encode_f(z, z') -{ 0 }-> f(0, f(encArg(x_121), encArg(x_221))) :|: z >= 0, z' = 1 + x_121 + x_221, x_221 >= 0, x_121 >= 0 encode_f(z, z') -{ 0 }-> 0 :|: z >= 0, z' >= 0 encode_h(z, z') -{ 1 }-> x :|: z >= 0, z' >= 0, 0 = x, x >= 0 encode_h(z, z') -{ 0 }-> h(h(encArg(x_124), encArg(x_224)), h(encArg(x_128), encArg(x_228))) :|: z = 1 + x_124 + x_224, x_124 >= 0, x_128 >= 0, z' = 1 + x_128 + x_228, x_224 >= 0, x_228 >= 0 encode_h(z, z') -{ 0 }-> h(h(encArg(x_124), encArg(x_224)), f(encArg(x_127), encArg(x_227))) :|: z = 1 + x_124 + x_224, x_124 >= 0, x_127 >= 0, x_224 >= 0, z' = 1 + x_127 + x_227, x_227 >= 0 encode_h(z, z') -{ 0 }-> h(h(encArg(x_124), encArg(x_224)), 0) :|: z = 1 + x_124 + x_224, x_124 >= 0, x_224 >= 0, z' >= 0 encode_h(z, z') -{ 0 }-> h(f(encArg(x_123), encArg(x_223)), h(encArg(x_126), encArg(x_226))) :|: z = 1 + x_123 + x_223, x_226 >= 0, x_123 >= 0, x_223 >= 0, x_126 >= 0, z' = 1 + x_126 + x_226 encode_h(z, z') -{ 0 }-> h(f(encArg(x_123), encArg(x_223)), f(encArg(x_125), encArg(x_225))) :|: z = 1 + x_123 + x_223, x_123 >= 0, z' = 1 + x_125 + x_225, x_223 >= 0, x_125 >= 0, x_225 >= 0 encode_h(z, z') -{ 0 }-> h(f(encArg(x_123), encArg(x_223)), 0) :|: z = 1 + x_123 + x_223, x_123 >= 0, x_223 >= 0, z' >= 0 encode_h(z, z') -{ 0 }-> h(0, h(encArg(x_130), encArg(x_230))) :|: z >= 0, x_130 >= 0, z' = 1 + x_130 + x_230, x_230 >= 0 encode_h(z, z') -{ 0 }-> h(0, f(encArg(x_129), encArg(x_229))) :|: z >= 0, z' = 1 + x_129 + x_229, x_229 >= 0, x_129 >= 0 encode_h(z, z') -{ 0 }-> 0 :|: z >= 0, z' >= 0 encode_h(z, z') -{ 0 }-> 0 :|: z >= 0, z' >= 0, v0 >= 0, v1 >= 0, 0 = v0, 0 = v1 f(z, z') -{ 2 }-> z' :|: z >= 0, z' >= 0, z = z' f(z, z') -{ 1 }-> 0 :|: z >= 0, z' >= 0 h(z, z') -{ 1 }-> z' :|: z' >= 0, z = z' h(z, z') -{ 0 }-> 0 :|: z >= 0, z' >= 0 Function symbols to be analyzed: {encArg}, {encode_f}, {encode_h} Previous analysis results are: h: runtime: O(1) [1], size: O(n^1) [z'] f: runtime: O(1) [2], size: O(n^1) [z'] encArg: runtime: ?, size: O(1) [0] ---------------------------------------- (37) IntTrsBoundProof (UPPER BOUND(ID)) Computed RUNTIME bound using CoFloCo for: encArg after applying outer abstraction to obtain an ITS, resulting in: O(n^1) with polynomial bound: 4 + 14*z ---------------------------------------- (38) Obligation: Complexity RNTS consisting of the following rules: encArg(z) -{ 2 }-> s :|: s >= 0, s <= y, x_1 >= 0, z = 1 + x_1 + x_2, x_2 >= 0, x >= 0, y >= 0, 0 = x, 0 = y encArg(z) -{ 2 }-> s' :|: s' >= 0, s' <= x, x_1 >= 0, z = 1 + x_1 + x_2, x_2 >= 0, x >= 0, y >= 0, 0 = x, 0 = y encArg(z) -{ 1 }-> x :|: x_1 >= 0, z = 1 + x_1 + x_2, x_2 >= 0, 0 = x, x >= 0 encArg(z) -{ 0 }-> h(h(encArg(x_18), encArg(x_28)), h(encArg(x_112), encArg(x_212))) :|: x_212 >= 0, z = 1 + (1 + x_18 + x_28) + (1 + x_112 + x_212), x_18 >= 0, x_28 >= 0, x_112 >= 0 encArg(z) -{ 0 }-> h(h(encArg(x_18), encArg(x_28)), f(encArg(x_111), encArg(x_211))) :|: z = 1 + (1 + x_18 + x_28) + (1 + x_111 + x_211), x_18 >= 0, x_28 >= 0, x_211 >= 0, x_111 >= 0 encArg(z) -{ 0 }-> h(h(encArg(x_18), encArg(x_28)), 0) :|: z = 1 + (1 + x_18 + x_28) + x_2, x_2 >= 0, x_18 >= 0, x_28 >= 0 encArg(z) -{ 0 }-> h(f(encArg(x_17), encArg(x_27)), h(encArg(x_110), encArg(x_210))) :|: z = 1 + (1 + x_17 + x_27) + (1 + x_110 + x_210), x_17 >= 0, x_27 >= 0, x_110 >= 0, x_210 >= 0 encArg(z) -{ 0 }-> h(f(encArg(x_17), encArg(x_27)), f(encArg(x_19), encArg(x_29))) :|: z = 1 + (1 + x_17 + x_27) + (1 + x_19 + x_29), x_17 >= 0, x_27 >= 0, x_19 >= 0, x_29 >= 0 encArg(z) -{ 0 }-> h(f(encArg(x_17), encArg(x_27)), 0) :|: x_17 >= 0, x_27 >= 0, x_2 >= 0, z = 1 + (1 + x_17 + x_27) + x_2 encArg(z) -{ 0 }-> h(0, h(encArg(x_114), encArg(x_214))) :|: z = 1 + x_1 + (1 + x_114 + x_214), x_1 >= 0, x_114 >= 0, x_214 >= 0 encArg(z) -{ 0 }-> h(0, f(encArg(x_113), encArg(x_213))) :|: x_1 >= 0, x_113 >= 0, x_213 >= 0, z = 1 + x_1 + (1 + x_113 + x_213) encArg(z) -{ 0 }-> f(h(encArg(x_1''), encArg(x_2'')), h(encArg(x_14), encArg(x_24))) :|: x_1'' >= 0, x_14 >= 0, x_2'' >= 0, x_24 >= 0, z = 1 + (1 + x_1'' + x_2'') + (1 + x_14 + x_24) encArg(z) -{ 0 }-> f(h(encArg(x_1''), encArg(x_2'')), f(encArg(x_13), encArg(x_23))) :|: x_1'' >= 0, x_13 >= 0, x_2'' >= 0, x_23 >= 0, z = 1 + (1 + x_1'' + x_2'') + (1 + x_13 + x_23) encArg(z) -{ 0 }-> f(h(encArg(x_1''), encArg(x_2'')), 0) :|: x_1'' >= 0, z = 1 + (1 + x_1'' + x_2'') + x_2, x_2'' >= 0, x_2 >= 0 encArg(z) -{ 0 }-> f(f(encArg(x_1'), encArg(x_2')), h(encArg(x_12), encArg(x_22))) :|: x_2' >= 0, z = 1 + (1 + x_1' + x_2') + (1 + x_12 + x_22), x_1' >= 0, x_12 >= 0, x_22 >= 0 encArg(z) -{ 0 }-> f(f(encArg(x_1'), encArg(x_2')), f(encArg(x_11), encArg(x_21))) :|: x_11 >= 0, x_2' >= 0, x_1' >= 0, x_21 >= 0, z = 1 + (1 + x_1' + x_2') + (1 + x_11 + x_21) encArg(z) -{ 0 }-> f(f(encArg(x_1'), encArg(x_2')), 0) :|: z = 1 + (1 + x_1' + x_2') + x_2, x_2' >= 0, x_1' >= 0, x_2 >= 0 encArg(z) -{ 0 }-> f(0, h(encArg(x_16), encArg(x_26))) :|: x_1 >= 0, x_16 >= 0, x_26 >= 0, z = 1 + x_1 + (1 + x_16 + x_26) encArg(z) -{ 0 }-> f(0, f(encArg(x_15), encArg(x_25))) :|: x_15 >= 0, x_1 >= 0, x_25 >= 0, z = 1 + x_1 + (1 + x_15 + x_25) encArg(z) -{ 0 }-> 0 :|: z >= 0 encArg(z) -{ 0 }-> 0 :|: x_1 >= 0, z = 1 + x_1 + x_2, x_2 >= 0, v0 >= 0, v1 >= 0, 0 = v0, 0 = v1 encode_f(z, z') -{ 2 }-> s'' :|: s'' >= 0, s'' <= y, z >= 0, z' >= 0, x >= 0, y >= 0, 0 = x, 0 = y encode_f(z, z') -{ 2 }-> s1 :|: s1 >= 0, s1 <= x, z >= 0, z' >= 0, x >= 0, y >= 0, 0 = x, 0 = y encode_f(z, z') -{ 0 }-> f(h(encArg(x_116), encArg(x_216)), h(encArg(x_120), encArg(x_220))) :|: x_216 >= 0, x_120 >= 0, x_116 >= 0, z = 1 + x_116 + x_216, z' = 1 + x_120 + x_220, x_220 >= 0 encode_f(z, z') -{ 0 }-> f(h(encArg(x_116), encArg(x_216)), f(encArg(x_119), encArg(x_219))) :|: x_216 >= 0, z' = 1 + x_119 + x_219, x_116 >= 0, z = 1 + x_116 + x_216, x_219 >= 0, x_119 >= 0 encode_f(z, z') -{ 0 }-> f(h(encArg(x_116), encArg(x_216)), 0) :|: x_216 >= 0, x_116 >= 0, z = 1 + x_116 + x_216, z' >= 0 encode_f(z, z') -{ 0 }-> f(f(encArg(x_115), encArg(x_215)), h(encArg(x_118), encArg(x_218))) :|: x_215 >= 0, x_115 >= 0, z = 1 + x_115 + x_215, x_218 >= 0, z' = 1 + x_118 + x_218, x_118 >= 0 encode_f(z, z') -{ 0 }-> f(f(encArg(x_115), encArg(x_215)), f(encArg(x_117), encArg(x_217))) :|: x_117 >= 0, x_215 >= 0, x_115 >= 0, z = 1 + x_115 + x_215, z' = 1 + x_117 + x_217, x_217 >= 0 encode_f(z, z') -{ 0 }-> f(f(encArg(x_115), encArg(x_215)), 0) :|: x_215 >= 0, x_115 >= 0, z = 1 + x_115 + x_215, z' >= 0 encode_f(z, z') -{ 0 }-> f(0, h(encArg(x_122), encArg(x_222))) :|: z >= 0, x_222 >= 0, x_122 >= 0, z' = 1 + x_122 + x_222 encode_f(z, z') -{ 0 }-> f(0, f(encArg(x_121), encArg(x_221))) :|: z >= 0, z' = 1 + x_121 + x_221, x_221 >= 0, x_121 >= 0 encode_f(z, z') -{ 0 }-> 0 :|: z >= 0, z' >= 0 encode_h(z, z') -{ 1 }-> x :|: z >= 0, z' >= 0, 0 = x, x >= 0 encode_h(z, z') -{ 0 }-> h(h(encArg(x_124), encArg(x_224)), h(encArg(x_128), encArg(x_228))) :|: z = 1 + x_124 + x_224, x_124 >= 0, x_128 >= 0, z' = 1 + x_128 + x_228, x_224 >= 0, x_228 >= 0 encode_h(z, z') -{ 0 }-> h(h(encArg(x_124), encArg(x_224)), f(encArg(x_127), encArg(x_227))) :|: z = 1 + x_124 + x_224, x_124 >= 0, x_127 >= 0, x_224 >= 0, z' = 1 + x_127 + x_227, x_227 >= 0 encode_h(z, z') -{ 0 }-> h(h(encArg(x_124), encArg(x_224)), 0) :|: z = 1 + x_124 + x_224, x_124 >= 0, x_224 >= 0, z' >= 0 encode_h(z, z') -{ 0 }-> h(f(encArg(x_123), encArg(x_223)), h(encArg(x_126), encArg(x_226))) :|: z = 1 + x_123 + x_223, x_226 >= 0, x_123 >= 0, x_223 >= 0, x_126 >= 0, z' = 1 + x_126 + x_226 encode_h(z, z') -{ 0 }-> h(f(encArg(x_123), encArg(x_223)), f(encArg(x_125), encArg(x_225))) :|: z = 1 + x_123 + x_223, x_123 >= 0, z' = 1 + x_125 + x_225, x_223 >= 0, x_125 >= 0, x_225 >= 0 encode_h(z, z') -{ 0 }-> h(f(encArg(x_123), encArg(x_223)), 0) :|: z = 1 + x_123 + x_223, x_123 >= 0, x_223 >= 0, z' >= 0 encode_h(z, z') -{ 0 }-> h(0, h(encArg(x_130), encArg(x_230))) :|: z >= 0, x_130 >= 0, z' = 1 + x_130 + x_230, x_230 >= 0 encode_h(z, z') -{ 0 }-> h(0, f(encArg(x_129), encArg(x_229))) :|: z >= 0, z' = 1 + x_129 + x_229, x_229 >= 0, x_129 >= 0 encode_h(z, z') -{ 0 }-> 0 :|: z >= 0, z' >= 0 encode_h(z, z') -{ 0 }-> 0 :|: z >= 0, z' >= 0, v0 >= 0, v1 >= 0, 0 = v0, 0 = v1 f(z, z') -{ 2 }-> z' :|: z >= 0, z' >= 0, z = z' f(z, z') -{ 1 }-> 0 :|: z >= 0, z' >= 0 h(z, z') -{ 1 }-> z' :|: z' >= 0, z = z' h(z, z') -{ 0 }-> 0 :|: z >= 0, z' >= 0 Function symbols to be analyzed: {encode_f}, {encode_h} Previous analysis results are: h: runtime: O(1) [1], size: O(n^1) [z'] f: runtime: O(1) [2], size: O(n^1) [z'] encArg: runtime: O(n^1) [4 + 14*z], size: O(1) [0] ---------------------------------------- (39) ResultPropagationProof (UPPER BOUND(ID)) Applied inner abstraction using the recently inferred runtime/size bounds where possible. ---------------------------------------- (40) Obligation: Complexity RNTS consisting of the following rules: encArg(z) -{ 2 }-> s :|: s >= 0, s <= y, x_1 >= 0, z = 1 + x_1 + x_2, x_2 >= 0, x >= 0, y >= 0, 0 = x, 0 = y encArg(z) -{ 2 }-> s' :|: s' >= 0, s' <= x, x_1 >= 0, z = 1 + x_1 + x_2, x_2 >= 0, x >= 0, y >= 0, 0 = x, 0 = y encArg(z) -{ 20 + 14*x_110 + 14*x_17 + 14*x_210 + 14*x_27 }-> s104 :|: s98 >= 0, s98 <= 0, s99 >= 0, s99 <= 0, s100 >= 0, s100 <= s99, s101 >= 0, s101 <= 0, s102 >= 0, s102 <= 0, s103 >= 0, s103 <= s102, s104 >= 0, s104 <= s103, z = 1 + (1 + x_17 + x_27) + (1 + x_110 + x_210), x_17 >= 0, x_27 >= 0, x_110 >= 0, x_210 >= 0 encArg(z) -{ 11 + 14*x_17 + 14*x_27 }-> s108 :|: s105 >= 0, s105 <= 0, s106 >= 0, s106 <= 0, s107 >= 0, s107 <= s106, s108 >= 0, s108 <= 0, x_17 >= 0, x_27 >= 0, x_2 >= 0, z = 1 + (1 + x_17 + x_27) + x_2 encArg(z) -{ 20 + 14*x_111 + 14*x_18 + 14*x_211 + 14*x_28 }-> s115 :|: s109 >= 0, s109 <= 0, s110 >= 0, s110 <= 0, s111 >= 0, s111 <= s110, s112 >= 0, s112 <= 0, s113 >= 0, s113 <= 0, s114 >= 0, s114 <= s113, s115 >= 0, s115 <= s114, z = 1 + (1 + x_18 + x_28) + (1 + x_111 + x_211), x_18 >= 0, x_28 >= 0, x_211 >= 0, x_111 >= 0 encArg(z) -{ 11 + 14*x_113 + 14*x_213 }-> s119 :|: s116 >= 0, s116 <= 0, s117 >= 0, s117 <= 0, s118 >= 0, s118 <= s117, s119 >= 0, s119 <= s118, x_1 >= 0, x_113 >= 0, x_213 >= 0, z = 1 + x_1 + (1 + x_113 + x_213) encArg(z) -{ 10 + 14*x_18 + 14*x_28 }-> s12 :|: s9 >= 0, s9 <= 0, s10 >= 0, s10 <= 0, s11 >= 0, s11 <= s10, s12 >= 0, s12 <= 0, z = 1 + (1 + x_18 + x_28) + x_2, x_2 >= 0, x_18 >= 0, x_28 >= 0 encArg(z) -{ 10 + 14*x_114 + 14*x_214 }-> s16 :|: s13 >= 0, s13 <= 0, s14 >= 0, s14 <= 0, s15 >= 0, s15 <= s14, s16 >= 0, s16 <= s15, z = 1 + x_1 + (1 + x_114 + x_214), x_1 >= 0, x_114 >= 0, x_214 >= 0 encArg(z) -{ 22 + 14*x_1' + 14*x_11 + 14*x_2' + 14*x_21 }-> s38 :|: s32 >= 0, s32 <= 0, s33 >= 0, s33 <= 0, s34 >= 0, s34 <= s33, s35 >= 0, s35 <= 0, s36 >= 0, s36 <= 0, s37 >= 0, s37 <= s36, s38 >= 0, s38 <= s37, x_11 >= 0, x_2' >= 0, x_1' >= 0, x_21 >= 0, z = 1 + (1 + x_1' + x_2') + (1 + x_11 + x_21) encArg(z) -{ 12 + 14*x_1' + 14*x_2' }-> s42 :|: s39 >= 0, s39 <= 0, s40 >= 0, s40 <= 0, s41 >= 0, s41 <= s40, s42 >= 0, s42 <= 0, z = 1 + (1 + x_1' + x_2') + x_2, x_2' >= 0, x_1' >= 0, x_2 >= 0 encArg(z) -{ 12 + 14*x_15 + 14*x_25 }-> s46 :|: s43 >= 0, s43 <= 0, s44 >= 0, s44 <= 0, s45 >= 0, s45 <= s44, s46 >= 0, s46 <= s45, x_15 >= 0, x_1 >= 0, x_25 >= 0, z = 1 + x_1 + (1 + x_15 + x_25) encArg(z) -{ 21 + 14*x_1' + 14*x_12 + 14*x_2' + 14*x_22 }-> s68 :|: s62 >= 0, s62 <= 0, s63 >= 0, s63 <= 0, s64 >= 0, s64 <= s63, s65 >= 0, s65 <= 0, s66 >= 0, s66 <= 0, s67 >= 0, s67 <= s66, s68 >= 0, s68 <= s67, x_2' >= 0, z = 1 + (1 + x_1' + x_2') + (1 + x_12 + x_22), x_1' >= 0, x_12 >= 0, x_22 >= 0 encArg(z) -{ 21 + 14*x_1'' + 14*x_13 + 14*x_2'' + 14*x_23 }-> s75 :|: s69 >= 0, s69 <= 0, s70 >= 0, s70 <= 0, s71 >= 0, s71 <= s70, s72 >= 0, s72 <= 0, s73 >= 0, s73 <= 0, s74 >= 0, s74 <= s73, s75 >= 0, s75 <= s74, x_1'' >= 0, x_13 >= 0, x_2'' >= 0, x_23 >= 0, z = 1 + (1 + x_1'' + x_2'') + (1 + x_13 + x_23) encArg(z) -{ 19 + 14*x_112 + 14*x_18 + 14*x_212 + 14*x_28 }-> s8 :|: s2 >= 0, s2 <= 0, s3 >= 0, s3 <= 0, s4 >= 0, s4 <= s3, s5 >= 0, s5 <= 0, s6 >= 0, s6 <= 0, s7 >= 0, s7 <= s6, s8 >= 0, s8 <= s7, x_212 >= 0, z = 1 + (1 + x_18 + x_28) + (1 + x_112 + x_212), x_18 >= 0, x_28 >= 0, x_112 >= 0 encArg(z) -{ 20 + 14*x_1'' + 14*x_14 + 14*x_2'' + 14*x_24 }-> s82 :|: s76 >= 0, s76 <= 0, s77 >= 0, s77 <= 0, s78 >= 0, s78 <= s77, s79 >= 0, s79 <= 0, s80 >= 0, s80 <= 0, s81 >= 0, s81 <= s80, s82 >= 0, s82 <= s81, x_1'' >= 0, x_14 >= 0, x_2'' >= 0, x_24 >= 0, z = 1 + (1 + x_1'' + x_2'') + (1 + x_14 + x_24) encArg(z) -{ 11 + 14*x_1'' + 14*x_2'' }-> s86 :|: s83 >= 0, s83 <= 0, s84 >= 0, s84 <= 0, s85 >= 0, s85 <= s84, s86 >= 0, s86 <= 0, x_1'' >= 0, z = 1 + (1 + x_1'' + x_2'') + x_2, x_2'' >= 0, x_2 >= 0 encArg(z) -{ 11 + 14*x_16 + 14*x_26 }-> s90 :|: s87 >= 0, s87 <= 0, s88 >= 0, s88 <= 0, s89 >= 0, s89 <= s88, s90 >= 0, s90 <= s89, x_1 >= 0, x_16 >= 0, x_26 >= 0, z = 1 + x_1 + (1 + x_16 + x_26) encArg(z) -{ 21 + 14*x_17 + 14*x_19 + 14*x_27 + 14*x_29 }-> s97 :|: s91 >= 0, s91 <= 0, s92 >= 0, s92 <= 0, s93 >= 0, s93 <= s92, s94 >= 0, s94 <= 0, s95 >= 0, s95 <= 0, s96 >= 0, s96 <= s95, s97 >= 0, s97 <= s96, z = 1 + (1 + x_17 + x_27) + (1 + x_19 + x_29), x_17 >= 0, x_27 >= 0, x_19 >= 0, x_29 >= 0 encArg(z) -{ 1 }-> x :|: x_1 >= 0, z = 1 + x_1 + x_2, x_2 >= 0, 0 = x, x >= 0 encArg(z) -{ 0 }-> 0 :|: z >= 0 encArg(z) -{ 0 }-> 0 :|: x_1 >= 0, z = 1 + x_1 + x_2, x_2 >= 0, v0 >= 0, v1 >= 0, 0 = v0, 0 = v1 encode_f(z, z') -{ 2 }-> s'' :|: s'' >= 0, s'' <= y, z >= 0, z' >= 0, x >= 0, y >= 0, 0 = x, 0 = y encode_f(z, z') -{ 2 }-> s1 :|: s1 >= 0, s1 <= x, z >= 0, z' >= 0, x >= 0, y >= 0, 0 = x, 0 = y encode_f(z, z') -{ 21 + 14*x_115 + 14*x_118 + 14*x_215 + 14*x_218 }-> s126 :|: s120 >= 0, s120 <= 0, s121 >= 0, s121 <= 0, s122 >= 0, s122 <= s121, s123 >= 0, s123 <= 0, s124 >= 0, s124 <= 0, s125 >= 0, s125 <= s124, s126 >= 0, s126 <= s125, x_215 >= 0, x_115 >= 0, z = 1 + x_115 + x_215, x_218 >= 0, z' = 1 + x_118 + x_218, x_118 >= 0 encode_f(z, z') -{ 21 + 14*x_116 + 14*x_119 + 14*x_216 + 14*x_219 }-> s133 :|: s127 >= 0, s127 <= 0, s128 >= 0, s128 <= 0, s129 >= 0, s129 <= s128, s130 >= 0, s130 <= 0, s131 >= 0, s131 <= 0, s132 >= 0, s132 <= s131, s133 >= 0, s133 <= s132, x_216 >= 0, z' = 1 + x_119 + x_219, x_116 >= 0, z = 1 + x_116 + x_216, x_219 >= 0, x_119 >= 0 encode_f(z, z') -{ 20 + 14*x_116 + 14*x_120 + 14*x_216 + 14*x_220 }-> s140 :|: s134 >= 0, s134 <= 0, s135 >= 0, s135 <= 0, s136 >= 0, s136 <= s135, s137 >= 0, s137 <= 0, s138 >= 0, s138 <= 0, s139 >= 0, s139 <= s138, s140 >= 0, s140 <= s139, x_216 >= 0, x_120 >= 0, x_116 >= 0, z = 1 + x_116 + x_216, z' = 1 + x_120 + x_220, x_220 >= 0 encode_f(z, z') -{ 11 + 14*x_116 + 14*x_216 }-> s144 :|: s141 >= 0, s141 <= 0, s142 >= 0, s142 <= 0, s143 >= 0, s143 <= s142, s144 >= 0, s144 <= 0, x_216 >= 0, x_116 >= 0, z = 1 + x_116 + x_216, z' >= 0 encode_f(z, z') -{ 11 + 14*x_122 + 14*x_222 }-> s148 :|: s145 >= 0, s145 <= 0, s146 >= 0, s146 <= 0, s147 >= 0, s147 <= s146, s148 >= 0, s148 <= s147, z >= 0, x_222 >= 0, x_122 >= 0, z' = 1 + x_122 + x_222 encode_f(z, z') -{ 22 + 14*x_115 + 14*x_117 + 14*x_215 + 14*x_217 }-> s53 :|: s47 >= 0, s47 <= 0, s48 >= 0, s48 <= 0, s49 >= 0, s49 <= s48, s50 >= 0, s50 <= 0, s51 >= 0, s51 <= 0, s52 >= 0, s52 <= s51, s53 >= 0, s53 <= s52, x_117 >= 0, x_215 >= 0, x_115 >= 0, z = 1 + x_115 + x_215, z' = 1 + x_117 + x_217, x_217 >= 0 encode_f(z, z') -{ 12 + 14*x_115 + 14*x_215 }-> s57 :|: s54 >= 0, s54 <= 0, s55 >= 0, s55 <= 0, s56 >= 0, s56 <= s55, s57 >= 0, s57 <= 0, x_215 >= 0, x_115 >= 0, z = 1 + x_115 + x_215, z' >= 0 encode_f(z, z') -{ 12 + 14*x_121 + 14*x_221 }-> s61 :|: s58 >= 0, s58 <= 0, s59 >= 0, s59 <= 0, s60 >= 0, s60 <= s59, s61 >= 0, s61 <= s60, z >= 0, z' = 1 + x_121 + x_221, x_221 >= 0, x_121 >= 0 encode_f(z, z') -{ 0 }-> 0 :|: z >= 0, z' >= 0 encode_h(z, z') -{ 21 + 14*x_123 + 14*x_125 + 14*x_223 + 14*x_225 }-> s155 :|: s149 >= 0, s149 <= 0, s150 >= 0, s150 <= 0, s151 >= 0, s151 <= s150, s152 >= 0, s152 <= 0, s153 >= 0, s153 <= 0, s154 >= 0, s154 <= s153, s155 >= 0, s155 <= s154, z = 1 + x_123 + x_223, x_123 >= 0, z' = 1 + x_125 + x_225, x_223 >= 0, x_125 >= 0, x_225 >= 0 encode_h(z, z') -{ 20 + 14*x_123 + 14*x_126 + 14*x_223 + 14*x_226 }-> s162 :|: s156 >= 0, s156 <= 0, s157 >= 0, s157 <= 0, s158 >= 0, s158 <= s157, s159 >= 0, s159 <= 0, s160 >= 0, s160 <= 0, s161 >= 0, s161 <= s160, s162 >= 0, s162 <= s161, z = 1 + x_123 + x_223, x_226 >= 0, x_123 >= 0, x_223 >= 0, x_126 >= 0, z' = 1 + x_126 + x_226 encode_h(z, z') -{ 11 + 14*x_123 + 14*x_223 }-> s166 :|: s163 >= 0, s163 <= 0, s164 >= 0, s164 <= 0, s165 >= 0, s165 <= s164, s166 >= 0, s166 <= 0, z = 1 + x_123 + x_223, x_123 >= 0, x_223 >= 0, z' >= 0 encode_h(z, z') -{ 20 + 14*x_124 + 14*x_127 + 14*x_224 + 14*x_227 }-> s173 :|: s167 >= 0, s167 <= 0, s168 >= 0, s168 <= 0, s169 >= 0, s169 <= s168, s170 >= 0, s170 <= 0, s171 >= 0, s171 <= 0, s172 >= 0, s172 <= s171, s173 >= 0, s173 <= s172, z = 1 + x_124 + x_224, x_124 >= 0, x_127 >= 0, x_224 >= 0, z' = 1 + x_127 + x_227, x_227 >= 0 encode_h(z, z') -{ 11 + 14*x_129 + 14*x_229 }-> s177 :|: s174 >= 0, s174 <= 0, s175 >= 0, s175 <= 0, s176 >= 0, s176 <= s175, s177 >= 0, s177 <= s176, z >= 0, z' = 1 + x_129 + x_229, x_229 >= 0, x_129 >= 0 encode_h(z, z') -{ 19 + 14*x_124 + 14*x_128 + 14*x_224 + 14*x_228 }-> s23 :|: s17 >= 0, s17 <= 0, s18 >= 0, s18 <= 0, s19 >= 0, s19 <= s18, s20 >= 0, s20 <= 0, s21 >= 0, s21 <= 0, s22 >= 0, s22 <= s21, s23 >= 0, s23 <= s22, z = 1 + x_124 + x_224, x_124 >= 0, x_128 >= 0, z' = 1 + x_128 + x_228, x_224 >= 0, x_228 >= 0 encode_h(z, z') -{ 10 + 14*x_124 + 14*x_224 }-> s27 :|: s24 >= 0, s24 <= 0, s25 >= 0, s25 <= 0, s26 >= 0, s26 <= s25, s27 >= 0, s27 <= 0, z = 1 + x_124 + x_224, x_124 >= 0, x_224 >= 0, z' >= 0 encode_h(z, z') -{ 10 + 14*x_130 + 14*x_230 }-> s31 :|: s28 >= 0, s28 <= 0, s29 >= 0, s29 <= 0, s30 >= 0, s30 <= s29, s31 >= 0, s31 <= s30, z >= 0, x_130 >= 0, z' = 1 + x_130 + x_230, x_230 >= 0 encode_h(z, z') -{ 1 }-> x :|: z >= 0, z' >= 0, 0 = x, x >= 0 encode_h(z, z') -{ 0 }-> 0 :|: z >= 0, z' >= 0 encode_h(z, z') -{ 0 }-> 0 :|: z >= 0, z' >= 0, v0 >= 0, v1 >= 0, 0 = v0, 0 = v1 f(z, z') -{ 2 }-> z' :|: z >= 0, z' >= 0, z = z' f(z, z') -{ 1 }-> 0 :|: z >= 0, z' >= 0 h(z, z') -{ 1 }-> z' :|: z' >= 0, z = z' h(z, z') -{ 0 }-> 0 :|: z >= 0, z' >= 0 Function symbols to be analyzed: {encode_f}, {encode_h} Previous analysis results are: h: runtime: O(1) [1], size: O(n^1) [z'] f: runtime: O(1) [2], size: O(n^1) [z'] encArg: runtime: O(n^1) [4 + 14*z], size: O(1) [0] ---------------------------------------- (41) IntTrsBoundProof (UPPER BOUND(ID)) Computed SIZE bound using CoFloCo for: encode_f after applying outer abstraction to obtain an ITS, resulting in: O(1) with polynomial bound: 0 ---------------------------------------- (42) Obligation: Complexity RNTS consisting of the following rules: encArg(z) -{ 2 }-> s :|: s >= 0, s <= y, x_1 >= 0, z = 1 + x_1 + x_2, x_2 >= 0, x >= 0, y >= 0, 0 = x, 0 = y encArg(z) -{ 2 }-> s' :|: s' >= 0, s' <= x, x_1 >= 0, z = 1 + x_1 + x_2, x_2 >= 0, x >= 0, y >= 0, 0 = x, 0 = y encArg(z) -{ 20 + 14*x_110 + 14*x_17 + 14*x_210 + 14*x_27 }-> s104 :|: s98 >= 0, s98 <= 0, s99 >= 0, s99 <= 0, s100 >= 0, s100 <= s99, s101 >= 0, s101 <= 0, s102 >= 0, s102 <= 0, s103 >= 0, s103 <= s102, s104 >= 0, s104 <= s103, z = 1 + (1 + x_17 + x_27) + (1 + x_110 + x_210), x_17 >= 0, x_27 >= 0, x_110 >= 0, x_210 >= 0 encArg(z) -{ 11 + 14*x_17 + 14*x_27 }-> s108 :|: s105 >= 0, s105 <= 0, s106 >= 0, s106 <= 0, s107 >= 0, s107 <= s106, s108 >= 0, s108 <= 0, x_17 >= 0, x_27 >= 0, x_2 >= 0, z = 1 + (1 + x_17 + x_27) + x_2 encArg(z) -{ 20 + 14*x_111 + 14*x_18 + 14*x_211 + 14*x_28 }-> s115 :|: s109 >= 0, s109 <= 0, s110 >= 0, s110 <= 0, s111 >= 0, s111 <= s110, s112 >= 0, s112 <= 0, s113 >= 0, s113 <= 0, s114 >= 0, s114 <= s113, s115 >= 0, s115 <= s114, z = 1 + (1 + x_18 + x_28) + (1 + x_111 + x_211), x_18 >= 0, x_28 >= 0, x_211 >= 0, x_111 >= 0 encArg(z) -{ 11 + 14*x_113 + 14*x_213 }-> s119 :|: s116 >= 0, s116 <= 0, s117 >= 0, s117 <= 0, s118 >= 0, s118 <= s117, s119 >= 0, s119 <= s118, x_1 >= 0, x_113 >= 0, x_213 >= 0, z = 1 + x_1 + (1 + x_113 + x_213) encArg(z) -{ 10 + 14*x_18 + 14*x_28 }-> s12 :|: s9 >= 0, s9 <= 0, s10 >= 0, s10 <= 0, s11 >= 0, s11 <= s10, s12 >= 0, s12 <= 0, z = 1 + (1 + x_18 + x_28) + x_2, x_2 >= 0, x_18 >= 0, x_28 >= 0 encArg(z) -{ 10 + 14*x_114 + 14*x_214 }-> s16 :|: s13 >= 0, s13 <= 0, s14 >= 0, s14 <= 0, s15 >= 0, s15 <= s14, s16 >= 0, s16 <= s15, z = 1 + x_1 + (1 + x_114 + x_214), x_1 >= 0, x_114 >= 0, x_214 >= 0 encArg(z) -{ 22 + 14*x_1' + 14*x_11 + 14*x_2' + 14*x_21 }-> s38 :|: s32 >= 0, s32 <= 0, s33 >= 0, s33 <= 0, s34 >= 0, s34 <= s33, s35 >= 0, s35 <= 0, s36 >= 0, s36 <= 0, s37 >= 0, s37 <= s36, s38 >= 0, s38 <= s37, x_11 >= 0, x_2' >= 0, x_1' >= 0, x_21 >= 0, z = 1 + (1 + x_1' + x_2') + (1 + x_11 + x_21) encArg(z) -{ 12 + 14*x_1' + 14*x_2' }-> s42 :|: s39 >= 0, s39 <= 0, s40 >= 0, s40 <= 0, s41 >= 0, s41 <= s40, s42 >= 0, s42 <= 0, z = 1 + (1 + x_1' + x_2') + x_2, x_2' >= 0, x_1' >= 0, x_2 >= 0 encArg(z) -{ 12 + 14*x_15 + 14*x_25 }-> s46 :|: s43 >= 0, s43 <= 0, s44 >= 0, s44 <= 0, s45 >= 0, s45 <= s44, s46 >= 0, s46 <= s45, x_15 >= 0, x_1 >= 0, x_25 >= 0, z = 1 + x_1 + (1 + x_15 + x_25) encArg(z) -{ 21 + 14*x_1' + 14*x_12 + 14*x_2' + 14*x_22 }-> s68 :|: s62 >= 0, s62 <= 0, s63 >= 0, s63 <= 0, s64 >= 0, s64 <= s63, s65 >= 0, s65 <= 0, s66 >= 0, s66 <= 0, s67 >= 0, s67 <= s66, s68 >= 0, s68 <= s67, x_2' >= 0, z = 1 + (1 + x_1' + x_2') + (1 + x_12 + x_22), x_1' >= 0, x_12 >= 0, x_22 >= 0 encArg(z) -{ 21 + 14*x_1'' + 14*x_13 + 14*x_2'' + 14*x_23 }-> s75 :|: s69 >= 0, s69 <= 0, s70 >= 0, s70 <= 0, s71 >= 0, s71 <= s70, s72 >= 0, s72 <= 0, s73 >= 0, s73 <= 0, s74 >= 0, s74 <= s73, s75 >= 0, s75 <= s74, x_1'' >= 0, x_13 >= 0, x_2'' >= 0, x_23 >= 0, z = 1 + (1 + x_1'' + x_2'') + (1 + x_13 + x_23) encArg(z) -{ 19 + 14*x_112 + 14*x_18 + 14*x_212 + 14*x_28 }-> s8 :|: s2 >= 0, s2 <= 0, s3 >= 0, s3 <= 0, s4 >= 0, s4 <= s3, s5 >= 0, s5 <= 0, s6 >= 0, s6 <= 0, s7 >= 0, s7 <= s6, s8 >= 0, s8 <= s7, x_212 >= 0, z = 1 + (1 + x_18 + x_28) + (1 + x_112 + x_212), x_18 >= 0, x_28 >= 0, x_112 >= 0 encArg(z) -{ 20 + 14*x_1'' + 14*x_14 + 14*x_2'' + 14*x_24 }-> s82 :|: s76 >= 0, s76 <= 0, s77 >= 0, s77 <= 0, s78 >= 0, s78 <= s77, s79 >= 0, s79 <= 0, s80 >= 0, s80 <= 0, s81 >= 0, s81 <= s80, s82 >= 0, s82 <= s81, x_1'' >= 0, x_14 >= 0, x_2'' >= 0, x_24 >= 0, z = 1 + (1 + x_1'' + x_2'') + (1 + x_14 + x_24) encArg(z) -{ 11 + 14*x_1'' + 14*x_2'' }-> s86 :|: s83 >= 0, s83 <= 0, s84 >= 0, s84 <= 0, s85 >= 0, s85 <= s84, s86 >= 0, s86 <= 0, x_1'' >= 0, z = 1 + (1 + x_1'' + x_2'') + x_2, x_2'' >= 0, x_2 >= 0 encArg(z) -{ 11 + 14*x_16 + 14*x_26 }-> s90 :|: s87 >= 0, s87 <= 0, s88 >= 0, s88 <= 0, s89 >= 0, s89 <= s88, s90 >= 0, s90 <= s89, x_1 >= 0, x_16 >= 0, x_26 >= 0, z = 1 + x_1 + (1 + x_16 + x_26) encArg(z) -{ 21 + 14*x_17 + 14*x_19 + 14*x_27 + 14*x_29 }-> s97 :|: s91 >= 0, s91 <= 0, s92 >= 0, s92 <= 0, s93 >= 0, s93 <= s92, s94 >= 0, s94 <= 0, s95 >= 0, s95 <= 0, s96 >= 0, s96 <= s95, s97 >= 0, s97 <= s96, z = 1 + (1 + x_17 + x_27) + (1 + x_19 + x_29), x_17 >= 0, x_27 >= 0, x_19 >= 0, x_29 >= 0 encArg(z) -{ 1 }-> x :|: x_1 >= 0, z = 1 + x_1 + x_2, x_2 >= 0, 0 = x, x >= 0 encArg(z) -{ 0 }-> 0 :|: z >= 0 encArg(z) -{ 0 }-> 0 :|: x_1 >= 0, z = 1 + x_1 + x_2, x_2 >= 0, v0 >= 0, v1 >= 0, 0 = v0, 0 = v1 encode_f(z, z') -{ 2 }-> s'' :|: s'' >= 0, s'' <= y, z >= 0, z' >= 0, x >= 0, y >= 0, 0 = x, 0 = y encode_f(z, z') -{ 2 }-> s1 :|: s1 >= 0, s1 <= x, z >= 0, z' >= 0, x >= 0, y >= 0, 0 = x, 0 = y encode_f(z, z') -{ 21 + 14*x_115 + 14*x_118 + 14*x_215 + 14*x_218 }-> s126 :|: s120 >= 0, s120 <= 0, s121 >= 0, s121 <= 0, s122 >= 0, s122 <= s121, s123 >= 0, s123 <= 0, s124 >= 0, s124 <= 0, s125 >= 0, s125 <= s124, s126 >= 0, s126 <= s125, x_215 >= 0, x_115 >= 0, z = 1 + x_115 + x_215, x_218 >= 0, z' = 1 + x_118 + x_218, x_118 >= 0 encode_f(z, z') -{ 21 + 14*x_116 + 14*x_119 + 14*x_216 + 14*x_219 }-> s133 :|: s127 >= 0, s127 <= 0, s128 >= 0, s128 <= 0, s129 >= 0, s129 <= s128, s130 >= 0, s130 <= 0, s131 >= 0, s131 <= 0, s132 >= 0, s132 <= s131, s133 >= 0, s133 <= s132, x_216 >= 0, z' = 1 + x_119 + x_219, x_116 >= 0, z = 1 + x_116 + x_216, x_219 >= 0, x_119 >= 0 encode_f(z, z') -{ 20 + 14*x_116 + 14*x_120 + 14*x_216 + 14*x_220 }-> s140 :|: s134 >= 0, s134 <= 0, s135 >= 0, s135 <= 0, s136 >= 0, s136 <= s135, s137 >= 0, s137 <= 0, s138 >= 0, s138 <= 0, s139 >= 0, s139 <= s138, s140 >= 0, s140 <= s139, x_216 >= 0, x_120 >= 0, x_116 >= 0, z = 1 + x_116 + x_216, z' = 1 + x_120 + x_220, x_220 >= 0 encode_f(z, z') -{ 11 + 14*x_116 + 14*x_216 }-> s144 :|: s141 >= 0, s141 <= 0, s142 >= 0, s142 <= 0, s143 >= 0, s143 <= s142, s144 >= 0, s144 <= 0, x_216 >= 0, x_116 >= 0, z = 1 + x_116 + x_216, z' >= 0 encode_f(z, z') -{ 11 + 14*x_122 + 14*x_222 }-> s148 :|: s145 >= 0, s145 <= 0, s146 >= 0, s146 <= 0, s147 >= 0, s147 <= s146, s148 >= 0, s148 <= s147, z >= 0, x_222 >= 0, x_122 >= 0, z' = 1 + x_122 + x_222 encode_f(z, z') -{ 22 + 14*x_115 + 14*x_117 + 14*x_215 + 14*x_217 }-> s53 :|: s47 >= 0, s47 <= 0, s48 >= 0, s48 <= 0, s49 >= 0, s49 <= s48, s50 >= 0, s50 <= 0, s51 >= 0, s51 <= 0, s52 >= 0, s52 <= s51, s53 >= 0, s53 <= s52, x_117 >= 0, x_215 >= 0, x_115 >= 0, z = 1 + x_115 + x_215, z' = 1 + x_117 + x_217, x_217 >= 0 encode_f(z, z') -{ 12 + 14*x_115 + 14*x_215 }-> s57 :|: s54 >= 0, s54 <= 0, s55 >= 0, s55 <= 0, s56 >= 0, s56 <= s55, s57 >= 0, s57 <= 0, x_215 >= 0, x_115 >= 0, z = 1 + x_115 + x_215, z' >= 0 encode_f(z, z') -{ 12 + 14*x_121 + 14*x_221 }-> s61 :|: s58 >= 0, s58 <= 0, s59 >= 0, s59 <= 0, s60 >= 0, s60 <= s59, s61 >= 0, s61 <= s60, z >= 0, z' = 1 + x_121 + x_221, x_221 >= 0, x_121 >= 0 encode_f(z, z') -{ 0 }-> 0 :|: z >= 0, z' >= 0 encode_h(z, z') -{ 21 + 14*x_123 + 14*x_125 + 14*x_223 + 14*x_225 }-> s155 :|: s149 >= 0, s149 <= 0, s150 >= 0, s150 <= 0, s151 >= 0, s151 <= s150, s152 >= 0, s152 <= 0, s153 >= 0, s153 <= 0, s154 >= 0, s154 <= s153, s155 >= 0, s155 <= s154, z = 1 + x_123 + x_223, x_123 >= 0, z' = 1 + x_125 + x_225, x_223 >= 0, x_125 >= 0, x_225 >= 0 encode_h(z, z') -{ 20 + 14*x_123 + 14*x_126 + 14*x_223 + 14*x_226 }-> s162 :|: s156 >= 0, s156 <= 0, s157 >= 0, s157 <= 0, s158 >= 0, s158 <= s157, s159 >= 0, s159 <= 0, s160 >= 0, s160 <= 0, s161 >= 0, s161 <= s160, s162 >= 0, s162 <= s161, z = 1 + x_123 + x_223, x_226 >= 0, x_123 >= 0, x_223 >= 0, x_126 >= 0, z' = 1 + x_126 + x_226 encode_h(z, z') -{ 11 + 14*x_123 + 14*x_223 }-> s166 :|: s163 >= 0, s163 <= 0, s164 >= 0, s164 <= 0, s165 >= 0, s165 <= s164, s166 >= 0, s166 <= 0, z = 1 + x_123 + x_223, x_123 >= 0, x_223 >= 0, z' >= 0 encode_h(z, z') -{ 20 + 14*x_124 + 14*x_127 + 14*x_224 + 14*x_227 }-> s173 :|: s167 >= 0, s167 <= 0, s168 >= 0, s168 <= 0, s169 >= 0, s169 <= s168, s170 >= 0, s170 <= 0, s171 >= 0, s171 <= 0, s172 >= 0, s172 <= s171, s173 >= 0, s173 <= s172, z = 1 + x_124 + x_224, x_124 >= 0, x_127 >= 0, x_224 >= 0, z' = 1 + x_127 + x_227, x_227 >= 0 encode_h(z, z') -{ 11 + 14*x_129 + 14*x_229 }-> s177 :|: s174 >= 0, s174 <= 0, s175 >= 0, s175 <= 0, s176 >= 0, s176 <= s175, s177 >= 0, s177 <= s176, z >= 0, z' = 1 + x_129 + x_229, x_229 >= 0, x_129 >= 0 encode_h(z, z') -{ 19 + 14*x_124 + 14*x_128 + 14*x_224 + 14*x_228 }-> s23 :|: s17 >= 0, s17 <= 0, s18 >= 0, s18 <= 0, s19 >= 0, s19 <= s18, s20 >= 0, s20 <= 0, s21 >= 0, s21 <= 0, s22 >= 0, s22 <= s21, s23 >= 0, s23 <= s22, z = 1 + x_124 + x_224, x_124 >= 0, x_128 >= 0, z' = 1 + x_128 + x_228, x_224 >= 0, x_228 >= 0 encode_h(z, z') -{ 10 + 14*x_124 + 14*x_224 }-> s27 :|: s24 >= 0, s24 <= 0, s25 >= 0, s25 <= 0, s26 >= 0, s26 <= s25, s27 >= 0, s27 <= 0, z = 1 + x_124 + x_224, x_124 >= 0, x_224 >= 0, z' >= 0 encode_h(z, z') -{ 10 + 14*x_130 + 14*x_230 }-> s31 :|: s28 >= 0, s28 <= 0, s29 >= 0, s29 <= 0, s30 >= 0, s30 <= s29, s31 >= 0, s31 <= s30, z >= 0, x_130 >= 0, z' = 1 + x_130 + x_230, x_230 >= 0 encode_h(z, z') -{ 1 }-> x :|: z >= 0, z' >= 0, 0 = x, x >= 0 encode_h(z, z') -{ 0 }-> 0 :|: z >= 0, z' >= 0 encode_h(z, z') -{ 0 }-> 0 :|: z >= 0, z' >= 0, v0 >= 0, v1 >= 0, 0 = v0, 0 = v1 f(z, z') -{ 2 }-> z' :|: z >= 0, z' >= 0, z = z' f(z, z') -{ 1 }-> 0 :|: z >= 0, z' >= 0 h(z, z') -{ 1 }-> z' :|: z' >= 0, z = z' h(z, z') -{ 0 }-> 0 :|: z >= 0, z' >= 0 Function symbols to be analyzed: {encode_f}, {encode_h} Previous analysis results are: h: runtime: O(1) [1], size: O(n^1) [z'] f: runtime: O(1) [2], size: O(n^1) [z'] encArg: runtime: O(n^1) [4 + 14*z], size: O(1) [0] encode_f: runtime: ?, size: O(1) [0] ---------------------------------------- (43) IntTrsBoundProof (UPPER BOUND(ID)) Computed RUNTIME bound using CoFloCo for: encode_f after applying outer abstraction to obtain an ITS, resulting in: O(n^1) with polynomial bound: 8 + 14*z + 14*z' ---------------------------------------- (44) Obligation: Complexity RNTS consisting of the following rules: encArg(z) -{ 2 }-> s :|: s >= 0, s <= y, x_1 >= 0, z = 1 + x_1 + x_2, x_2 >= 0, x >= 0, y >= 0, 0 = x, 0 = y encArg(z) -{ 2 }-> s' :|: s' >= 0, s' <= x, x_1 >= 0, z = 1 + x_1 + x_2, x_2 >= 0, x >= 0, y >= 0, 0 = x, 0 = y encArg(z) -{ 20 + 14*x_110 + 14*x_17 + 14*x_210 + 14*x_27 }-> s104 :|: s98 >= 0, s98 <= 0, s99 >= 0, s99 <= 0, s100 >= 0, s100 <= s99, s101 >= 0, s101 <= 0, s102 >= 0, s102 <= 0, s103 >= 0, s103 <= s102, s104 >= 0, s104 <= s103, z = 1 + (1 + x_17 + x_27) + (1 + x_110 + x_210), x_17 >= 0, x_27 >= 0, x_110 >= 0, x_210 >= 0 encArg(z) -{ 11 + 14*x_17 + 14*x_27 }-> s108 :|: s105 >= 0, s105 <= 0, s106 >= 0, s106 <= 0, s107 >= 0, s107 <= s106, s108 >= 0, s108 <= 0, x_17 >= 0, x_27 >= 0, x_2 >= 0, z = 1 + (1 + x_17 + x_27) + x_2 encArg(z) -{ 20 + 14*x_111 + 14*x_18 + 14*x_211 + 14*x_28 }-> s115 :|: s109 >= 0, s109 <= 0, s110 >= 0, s110 <= 0, s111 >= 0, s111 <= s110, s112 >= 0, s112 <= 0, s113 >= 0, s113 <= 0, s114 >= 0, s114 <= s113, s115 >= 0, s115 <= s114, z = 1 + (1 + x_18 + x_28) + (1 + x_111 + x_211), x_18 >= 0, x_28 >= 0, x_211 >= 0, x_111 >= 0 encArg(z) -{ 11 + 14*x_113 + 14*x_213 }-> s119 :|: s116 >= 0, s116 <= 0, s117 >= 0, s117 <= 0, s118 >= 0, s118 <= s117, s119 >= 0, s119 <= s118, x_1 >= 0, x_113 >= 0, x_213 >= 0, z = 1 + x_1 + (1 + x_113 + x_213) encArg(z) -{ 10 + 14*x_18 + 14*x_28 }-> s12 :|: s9 >= 0, s9 <= 0, s10 >= 0, s10 <= 0, s11 >= 0, s11 <= s10, s12 >= 0, s12 <= 0, z = 1 + (1 + x_18 + x_28) + x_2, x_2 >= 0, x_18 >= 0, x_28 >= 0 encArg(z) -{ 10 + 14*x_114 + 14*x_214 }-> s16 :|: s13 >= 0, s13 <= 0, s14 >= 0, s14 <= 0, s15 >= 0, s15 <= s14, s16 >= 0, s16 <= s15, z = 1 + x_1 + (1 + x_114 + x_214), x_1 >= 0, x_114 >= 0, x_214 >= 0 encArg(z) -{ 22 + 14*x_1' + 14*x_11 + 14*x_2' + 14*x_21 }-> s38 :|: s32 >= 0, s32 <= 0, s33 >= 0, s33 <= 0, s34 >= 0, s34 <= s33, s35 >= 0, s35 <= 0, s36 >= 0, s36 <= 0, s37 >= 0, s37 <= s36, s38 >= 0, s38 <= s37, x_11 >= 0, x_2' >= 0, x_1' >= 0, x_21 >= 0, z = 1 + (1 + x_1' + x_2') + (1 + x_11 + x_21) encArg(z) -{ 12 + 14*x_1' + 14*x_2' }-> s42 :|: s39 >= 0, s39 <= 0, s40 >= 0, s40 <= 0, s41 >= 0, s41 <= s40, s42 >= 0, s42 <= 0, z = 1 + (1 + x_1' + x_2') + x_2, x_2' >= 0, x_1' >= 0, x_2 >= 0 encArg(z) -{ 12 + 14*x_15 + 14*x_25 }-> s46 :|: s43 >= 0, s43 <= 0, s44 >= 0, s44 <= 0, s45 >= 0, s45 <= s44, s46 >= 0, s46 <= s45, x_15 >= 0, x_1 >= 0, x_25 >= 0, z = 1 + x_1 + (1 + x_15 + x_25) encArg(z) -{ 21 + 14*x_1' + 14*x_12 + 14*x_2' + 14*x_22 }-> s68 :|: s62 >= 0, s62 <= 0, s63 >= 0, s63 <= 0, s64 >= 0, s64 <= s63, s65 >= 0, s65 <= 0, s66 >= 0, s66 <= 0, s67 >= 0, s67 <= s66, s68 >= 0, s68 <= s67, x_2' >= 0, z = 1 + (1 + x_1' + x_2') + (1 + x_12 + x_22), x_1' >= 0, x_12 >= 0, x_22 >= 0 encArg(z) -{ 21 + 14*x_1'' + 14*x_13 + 14*x_2'' + 14*x_23 }-> s75 :|: s69 >= 0, s69 <= 0, s70 >= 0, s70 <= 0, s71 >= 0, s71 <= s70, s72 >= 0, s72 <= 0, s73 >= 0, s73 <= 0, s74 >= 0, s74 <= s73, s75 >= 0, s75 <= s74, x_1'' >= 0, x_13 >= 0, x_2'' >= 0, x_23 >= 0, z = 1 + (1 + x_1'' + x_2'') + (1 + x_13 + x_23) encArg(z) -{ 19 + 14*x_112 + 14*x_18 + 14*x_212 + 14*x_28 }-> s8 :|: s2 >= 0, s2 <= 0, s3 >= 0, s3 <= 0, s4 >= 0, s4 <= s3, s5 >= 0, s5 <= 0, s6 >= 0, s6 <= 0, s7 >= 0, s7 <= s6, s8 >= 0, s8 <= s7, x_212 >= 0, z = 1 + (1 + x_18 + x_28) + (1 + x_112 + x_212), x_18 >= 0, x_28 >= 0, x_112 >= 0 encArg(z) -{ 20 + 14*x_1'' + 14*x_14 + 14*x_2'' + 14*x_24 }-> s82 :|: s76 >= 0, s76 <= 0, s77 >= 0, s77 <= 0, s78 >= 0, s78 <= s77, s79 >= 0, s79 <= 0, s80 >= 0, s80 <= 0, s81 >= 0, s81 <= s80, s82 >= 0, s82 <= s81, x_1'' >= 0, x_14 >= 0, x_2'' >= 0, x_24 >= 0, z = 1 + (1 + x_1'' + x_2'') + (1 + x_14 + x_24) encArg(z) -{ 11 + 14*x_1'' + 14*x_2'' }-> s86 :|: s83 >= 0, s83 <= 0, s84 >= 0, s84 <= 0, s85 >= 0, s85 <= s84, s86 >= 0, s86 <= 0, x_1'' >= 0, z = 1 + (1 + x_1'' + x_2'') + x_2, x_2'' >= 0, x_2 >= 0 encArg(z) -{ 11 + 14*x_16 + 14*x_26 }-> s90 :|: s87 >= 0, s87 <= 0, s88 >= 0, s88 <= 0, s89 >= 0, s89 <= s88, s90 >= 0, s90 <= s89, x_1 >= 0, x_16 >= 0, x_26 >= 0, z = 1 + x_1 + (1 + x_16 + x_26) encArg(z) -{ 21 + 14*x_17 + 14*x_19 + 14*x_27 + 14*x_29 }-> s97 :|: s91 >= 0, s91 <= 0, s92 >= 0, s92 <= 0, s93 >= 0, s93 <= s92, s94 >= 0, s94 <= 0, s95 >= 0, s95 <= 0, s96 >= 0, s96 <= s95, s97 >= 0, s97 <= s96, z = 1 + (1 + x_17 + x_27) + (1 + x_19 + x_29), x_17 >= 0, x_27 >= 0, x_19 >= 0, x_29 >= 0 encArg(z) -{ 1 }-> x :|: x_1 >= 0, z = 1 + x_1 + x_2, x_2 >= 0, 0 = x, x >= 0 encArg(z) -{ 0 }-> 0 :|: z >= 0 encArg(z) -{ 0 }-> 0 :|: x_1 >= 0, z = 1 + x_1 + x_2, x_2 >= 0, v0 >= 0, v1 >= 0, 0 = v0, 0 = v1 encode_f(z, z') -{ 2 }-> s'' :|: s'' >= 0, s'' <= y, z >= 0, z' >= 0, x >= 0, y >= 0, 0 = x, 0 = y encode_f(z, z') -{ 2 }-> s1 :|: s1 >= 0, s1 <= x, z >= 0, z' >= 0, x >= 0, y >= 0, 0 = x, 0 = y encode_f(z, z') -{ 21 + 14*x_115 + 14*x_118 + 14*x_215 + 14*x_218 }-> s126 :|: s120 >= 0, s120 <= 0, s121 >= 0, s121 <= 0, s122 >= 0, s122 <= s121, s123 >= 0, s123 <= 0, s124 >= 0, s124 <= 0, s125 >= 0, s125 <= s124, s126 >= 0, s126 <= s125, x_215 >= 0, x_115 >= 0, z = 1 + x_115 + x_215, x_218 >= 0, z' = 1 + x_118 + x_218, x_118 >= 0 encode_f(z, z') -{ 21 + 14*x_116 + 14*x_119 + 14*x_216 + 14*x_219 }-> s133 :|: s127 >= 0, s127 <= 0, s128 >= 0, s128 <= 0, s129 >= 0, s129 <= s128, s130 >= 0, s130 <= 0, s131 >= 0, s131 <= 0, s132 >= 0, s132 <= s131, s133 >= 0, s133 <= s132, x_216 >= 0, z' = 1 + x_119 + x_219, x_116 >= 0, z = 1 + x_116 + x_216, x_219 >= 0, x_119 >= 0 encode_f(z, z') -{ 20 + 14*x_116 + 14*x_120 + 14*x_216 + 14*x_220 }-> s140 :|: s134 >= 0, s134 <= 0, s135 >= 0, s135 <= 0, s136 >= 0, s136 <= s135, s137 >= 0, s137 <= 0, s138 >= 0, s138 <= 0, s139 >= 0, s139 <= s138, s140 >= 0, s140 <= s139, x_216 >= 0, x_120 >= 0, x_116 >= 0, z = 1 + x_116 + x_216, z' = 1 + x_120 + x_220, x_220 >= 0 encode_f(z, z') -{ 11 + 14*x_116 + 14*x_216 }-> s144 :|: s141 >= 0, s141 <= 0, s142 >= 0, s142 <= 0, s143 >= 0, s143 <= s142, s144 >= 0, s144 <= 0, x_216 >= 0, x_116 >= 0, z = 1 + x_116 + x_216, z' >= 0 encode_f(z, z') -{ 11 + 14*x_122 + 14*x_222 }-> s148 :|: s145 >= 0, s145 <= 0, s146 >= 0, s146 <= 0, s147 >= 0, s147 <= s146, s148 >= 0, s148 <= s147, z >= 0, x_222 >= 0, x_122 >= 0, z' = 1 + x_122 + x_222 encode_f(z, z') -{ 22 + 14*x_115 + 14*x_117 + 14*x_215 + 14*x_217 }-> s53 :|: s47 >= 0, s47 <= 0, s48 >= 0, s48 <= 0, s49 >= 0, s49 <= s48, s50 >= 0, s50 <= 0, s51 >= 0, s51 <= 0, s52 >= 0, s52 <= s51, s53 >= 0, s53 <= s52, x_117 >= 0, x_215 >= 0, x_115 >= 0, z = 1 + x_115 + x_215, z' = 1 + x_117 + x_217, x_217 >= 0 encode_f(z, z') -{ 12 + 14*x_115 + 14*x_215 }-> s57 :|: s54 >= 0, s54 <= 0, s55 >= 0, s55 <= 0, s56 >= 0, s56 <= s55, s57 >= 0, s57 <= 0, x_215 >= 0, x_115 >= 0, z = 1 + x_115 + x_215, z' >= 0 encode_f(z, z') -{ 12 + 14*x_121 + 14*x_221 }-> s61 :|: s58 >= 0, s58 <= 0, s59 >= 0, s59 <= 0, s60 >= 0, s60 <= s59, s61 >= 0, s61 <= s60, z >= 0, z' = 1 + x_121 + x_221, x_221 >= 0, x_121 >= 0 encode_f(z, z') -{ 0 }-> 0 :|: z >= 0, z' >= 0 encode_h(z, z') -{ 21 + 14*x_123 + 14*x_125 + 14*x_223 + 14*x_225 }-> s155 :|: s149 >= 0, s149 <= 0, s150 >= 0, s150 <= 0, s151 >= 0, s151 <= s150, s152 >= 0, s152 <= 0, s153 >= 0, s153 <= 0, s154 >= 0, s154 <= s153, s155 >= 0, s155 <= s154, z = 1 + x_123 + x_223, x_123 >= 0, z' = 1 + x_125 + x_225, x_223 >= 0, x_125 >= 0, x_225 >= 0 encode_h(z, z') -{ 20 + 14*x_123 + 14*x_126 + 14*x_223 + 14*x_226 }-> s162 :|: s156 >= 0, s156 <= 0, s157 >= 0, s157 <= 0, s158 >= 0, s158 <= s157, s159 >= 0, s159 <= 0, s160 >= 0, s160 <= 0, s161 >= 0, s161 <= s160, s162 >= 0, s162 <= s161, z = 1 + x_123 + x_223, x_226 >= 0, x_123 >= 0, x_223 >= 0, x_126 >= 0, z' = 1 + x_126 + x_226 encode_h(z, z') -{ 11 + 14*x_123 + 14*x_223 }-> s166 :|: s163 >= 0, s163 <= 0, s164 >= 0, s164 <= 0, s165 >= 0, s165 <= s164, s166 >= 0, s166 <= 0, z = 1 + x_123 + x_223, x_123 >= 0, x_223 >= 0, z' >= 0 encode_h(z, z') -{ 20 + 14*x_124 + 14*x_127 + 14*x_224 + 14*x_227 }-> s173 :|: s167 >= 0, s167 <= 0, s168 >= 0, s168 <= 0, s169 >= 0, s169 <= s168, s170 >= 0, s170 <= 0, s171 >= 0, s171 <= 0, s172 >= 0, s172 <= s171, s173 >= 0, s173 <= s172, z = 1 + x_124 + x_224, x_124 >= 0, x_127 >= 0, x_224 >= 0, z' = 1 + x_127 + x_227, x_227 >= 0 encode_h(z, z') -{ 11 + 14*x_129 + 14*x_229 }-> s177 :|: s174 >= 0, s174 <= 0, s175 >= 0, s175 <= 0, s176 >= 0, s176 <= s175, s177 >= 0, s177 <= s176, z >= 0, z' = 1 + x_129 + x_229, x_229 >= 0, x_129 >= 0 encode_h(z, z') -{ 19 + 14*x_124 + 14*x_128 + 14*x_224 + 14*x_228 }-> s23 :|: s17 >= 0, s17 <= 0, s18 >= 0, s18 <= 0, s19 >= 0, s19 <= s18, s20 >= 0, s20 <= 0, s21 >= 0, s21 <= 0, s22 >= 0, s22 <= s21, s23 >= 0, s23 <= s22, z = 1 + x_124 + x_224, x_124 >= 0, x_128 >= 0, z' = 1 + x_128 + x_228, x_224 >= 0, x_228 >= 0 encode_h(z, z') -{ 10 + 14*x_124 + 14*x_224 }-> s27 :|: s24 >= 0, s24 <= 0, s25 >= 0, s25 <= 0, s26 >= 0, s26 <= s25, s27 >= 0, s27 <= 0, z = 1 + x_124 + x_224, x_124 >= 0, x_224 >= 0, z' >= 0 encode_h(z, z') -{ 10 + 14*x_130 + 14*x_230 }-> s31 :|: s28 >= 0, s28 <= 0, s29 >= 0, s29 <= 0, s30 >= 0, s30 <= s29, s31 >= 0, s31 <= s30, z >= 0, x_130 >= 0, z' = 1 + x_130 + x_230, x_230 >= 0 encode_h(z, z') -{ 1 }-> x :|: z >= 0, z' >= 0, 0 = x, x >= 0 encode_h(z, z') -{ 0 }-> 0 :|: z >= 0, z' >= 0 encode_h(z, z') -{ 0 }-> 0 :|: z >= 0, z' >= 0, v0 >= 0, v1 >= 0, 0 = v0, 0 = v1 f(z, z') -{ 2 }-> z' :|: z >= 0, z' >= 0, z = z' f(z, z') -{ 1 }-> 0 :|: z >= 0, z' >= 0 h(z, z') -{ 1 }-> z' :|: z' >= 0, z = z' h(z, z') -{ 0 }-> 0 :|: z >= 0, z' >= 0 Function symbols to be analyzed: {encode_h} Previous analysis results are: h: runtime: O(1) [1], size: O(n^1) [z'] f: runtime: O(1) [2], size: O(n^1) [z'] encArg: runtime: O(n^1) [4 + 14*z], size: O(1) [0] encode_f: runtime: O(n^1) [8 + 14*z + 14*z'], size: O(1) [0] ---------------------------------------- (45) ResultPropagationProof (UPPER BOUND(ID)) Applied inner abstraction using the recently inferred runtime/size bounds where possible. ---------------------------------------- (46) Obligation: Complexity RNTS consisting of the following rules: encArg(z) -{ 2 }-> s :|: s >= 0, s <= y, x_1 >= 0, z = 1 + x_1 + x_2, x_2 >= 0, x >= 0, y >= 0, 0 = x, 0 = y encArg(z) -{ 2 }-> s' :|: s' >= 0, s' <= x, x_1 >= 0, z = 1 + x_1 + x_2, x_2 >= 0, x >= 0, y >= 0, 0 = x, 0 = y encArg(z) -{ 20 + 14*x_110 + 14*x_17 + 14*x_210 + 14*x_27 }-> s104 :|: s98 >= 0, s98 <= 0, s99 >= 0, s99 <= 0, s100 >= 0, s100 <= s99, s101 >= 0, s101 <= 0, s102 >= 0, s102 <= 0, s103 >= 0, s103 <= s102, s104 >= 0, s104 <= s103, z = 1 + (1 + x_17 + x_27) + (1 + x_110 + x_210), x_17 >= 0, x_27 >= 0, x_110 >= 0, x_210 >= 0 encArg(z) -{ 11 + 14*x_17 + 14*x_27 }-> s108 :|: s105 >= 0, s105 <= 0, s106 >= 0, s106 <= 0, s107 >= 0, s107 <= s106, s108 >= 0, s108 <= 0, x_17 >= 0, x_27 >= 0, x_2 >= 0, z = 1 + (1 + x_17 + x_27) + x_2 encArg(z) -{ 20 + 14*x_111 + 14*x_18 + 14*x_211 + 14*x_28 }-> s115 :|: s109 >= 0, s109 <= 0, s110 >= 0, s110 <= 0, s111 >= 0, s111 <= s110, s112 >= 0, s112 <= 0, s113 >= 0, s113 <= 0, s114 >= 0, s114 <= s113, s115 >= 0, s115 <= s114, z = 1 + (1 + x_18 + x_28) + (1 + x_111 + x_211), x_18 >= 0, x_28 >= 0, x_211 >= 0, x_111 >= 0 encArg(z) -{ 11 + 14*x_113 + 14*x_213 }-> s119 :|: s116 >= 0, s116 <= 0, s117 >= 0, s117 <= 0, s118 >= 0, s118 <= s117, s119 >= 0, s119 <= s118, x_1 >= 0, x_113 >= 0, x_213 >= 0, z = 1 + x_1 + (1 + x_113 + x_213) encArg(z) -{ 10 + 14*x_18 + 14*x_28 }-> s12 :|: s9 >= 0, s9 <= 0, s10 >= 0, s10 <= 0, s11 >= 0, s11 <= s10, s12 >= 0, s12 <= 0, z = 1 + (1 + x_18 + x_28) + x_2, x_2 >= 0, x_18 >= 0, x_28 >= 0 encArg(z) -{ 10 + 14*x_114 + 14*x_214 }-> s16 :|: s13 >= 0, s13 <= 0, s14 >= 0, s14 <= 0, s15 >= 0, s15 <= s14, s16 >= 0, s16 <= s15, z = 1 + x_1 + (1 + x_114 + x_214), x_1 >= 0, x_114 >= 0, x_214 >= 0 encArg(z) -{ 22 + 14*x_1' + 14*x_11 + 14*x_2' + 14*x_21 }-> s38 :|: s32 >= 0, s32 <= 0, s33 >= 0, s33 <= 0, s34 >= 0, s34 <= s33, s35 >= 0, s35 <= 0, s36 >= 0, s36 <= 0, s37 >= 0, s37 <= s36, s38 >= 0, s38 <= s37, x_11 >= 0, x_2' >= 0, x_1' >= 0, x_21 >= 0, z = 1 + (1 + x_1' + x_2') + (1 + x_11 + x_21) encArg(z) -{ 12 + 14*x_1' + 14*x_2' }-> s42 :|: s39 >= 0, s39 <= 0, s40 >= 0, s40 <= 0, s41 >= 0, s41 <= s40, s42 >= 0, s42 <= 0, z = 1 + (1 + x_1' + x_2') + x_2, x_2' >= 0, x_1' >= 0, x_2 >= 0 encArg(z) -{ 12 + 14*x_15 + 14*x_25 }-> s46 :|: s43 >= 0, s43 <= 0, s44 >= 0, s44 <= 0, s45 >= 0, s45 <= s44, s46 >= 0, s46 <= s45, x_15 >= 0, x_1 >= 0, x_25 >= 0, z = 1 + x_1 + (1 + x_15 + x_25) encArg(z) -{ 21 + 14*x_1' + 14*x_12 + 14*x_2' + 14*x_22 }-> s68 :|: s62 >= 0, s62 <= 0, s63 >= 0, s63 <= 0, s64 >= 0, s64 <= s63, s65 >= 0, s65 <= 0, s66 >= 0, s66 <= 0, s67 >= 0, s67 <= s66, s68 >= 0, s68 <= s67, x_2' >= 0, z = 1 + (1 + x_1' + x_2') + (1 + x_12 + x_22), x_1' >= 0, x_12 >= 0, x_22 >= 0 encArg(z) -{ 21 + 14*x_1'' + 14*x_13 + 14*x_2'' + 14*x_23 }-> s75 :|: s69 >= 0, s69 <= 0, s70 >= 0, s70 <= 0, s71 >= 0, s71 <= s70, s72 >= 0, s72 <= 0, s73 >= 0, s73 <= 0, s74 >= 0, s74 <= s73, s75 >= 0, s75 <= s74, x_1'' >= 0, x_13 >= 0, x_2'' >= 0, x_23 >= 0, z = 1 + (1 + x_1'' + x_2'') + (1 + x_13 + x_23) encArg(z) -{ 19 + 14*x_112 + 14*x_18 + 14*x_212 + 14*x_28 }-> s8 :|: s2 >= 0, s2 <= 0, s3 >= 0, s3 <= 0, s4 >= 0, s4 <= s3, s5 >= 0, s5 <= 0, s6 >= 0, s6 <= 0, s7 >= 0, s7 <= s6, s8 >= 0, s8 <= s7, x_212 >= 0, z = 1 + (1 + x_18 + x_28) + (1 + x_112 + x_212), x_18 >= 0, x_28 >= 0, x_112 >= 0 encArg(z) -{ 20 + 14*x_1'' + 14*x_14 + 14*x_2'' + 14*x_24 }-> s82 :|: s76 >= 0, s76 <= 0, s77 >= 0, s77 <= 0, s78 >= 0, s78 <= s77, s79 >= 0, s79 <= 0, s80 >= 0, s80 <= 0, s81 >= 0, s81 <= s80, s82 >= 0, s82 <= s81, x_1'' >= 0, x_14 >= 0, x_2'' >= 0, x_24 >= 0, z = 1 + (1 + x_1'' + x_2'') + (1 + x_14 + x_24) encArg(z) -{ 11 + 14*x_1'' + 14*x_2'' }-> s86 :|: s83 >= 0, s83 <= 0, s84 >= 0, s84 <= 0, s85 >= 0, s85 <= s84, s86 >= 0, s86 <= 0, x_1'' >= 0, z = 1 + (1 + x_1'' + x_2'') + x_2, x_2'' >= 0, x_2 >= 0 encArg(z) -{ 11 + 14*x_16 + 14*x_26 }-> s90 :|: s87 >= 0, s87 <= 0, s88 >= 0, s88 <= 0, s89 >= 0, s89 <= s88, s90 >= 0, s90 <= s89, x_1 >= 0, x_16 >= 0, x_26 >= 0, z = 1 + x_1 + (1 + x_16 + x_26) encArg(z) -{ 21 + 14*x_17 + 14*x_19 + 14*x_27 + 14*x_29 }-> s97 :|: s91 >= 0, s91 <= 0, s92 >= 0, s92 <= 0, s93 >= 0, s93 <= s92, s94 >= 0, s94 <= 0, s95 >= 0, s95 <= 0, s96 >= 0, s96 <= s95, s97 >= 0, s97 <= s96, z = 1 + (1 + x_17 + x_27) + (1 + x_19 + x_29), x_17 >= 0, x_27 >= 0, x_19 >= 0, x_29 >= 0 encArg(z) -{ 1 }-> x :|: x_1 >= 0, z = 1 + x_1 + x_2, x_2 >= 0, 0 = x, x >= 0 encArg(z) -{ 0 }-> 0 :|: z >= 0 encArg(z) -{ 0 }-> 0 :|: x_1 >= 0, z = 1 + x_1 + x_2, x_2 >= 0, v0 >= 0, v1 >= 0, 0 = v0, 0 = v1 encode_f(z, z') -{ 2 }-> s'' :|: s'' >= 0, s'' <= y, z >= 0, z' >= 0, x >= 0, y >= 0, 0 = x, 0 = y encode_f(z, z') -{ 2 }-> s1 :|: s1 >= 0, s1 <= x, z >= 0, z' >= 0, x >= 0, y >= 0, 0 = x, 0 = y encode_f(z, z') -{ 21 + 14*x_115 + 14*x_118 + 14*x_215 + 14*x_218 }-> s126 :|: s120 >= 0, s120 <= 0, s121 >= 0, s121 <= 0, s122 >= 0, s122 <= s121, s123 >= 0, s123 <= 0, s124 >= 0, s124 <= 0, s125 >= 0, s125 <= s124, s126 >= 0, s126 <= s125, x_215 >= 0, x_115 >= 0, z = 1 + x_115 + x_215, x_218 >= 0, z' = 1 + x_118 + x_218, x_118 >= 0 encode_f(z, z') -{ 21 + 14*x_116 + 14*x_119 + 14*x_216 + 14*x_219 }-> s133 :|: s127 >= 0, s127 <= 0, s128 >= 0, s128 <= 0, s129 >= 0, s129 <= s128, s130 >= 0, s130 <= 0, s131 >= 0, s131 <= 0, s132 >= 0, s132 <= s131, s133 >= 0, s133 <= s132, x_216 >= 0, z' = 1 + x_119 + x_219, x_116 >= 0, z = 1 + x_116 + x_216, x_219 >= 0, x_119 >= 0 encode_f(z, z') -{ 20 + 14*x_116 + 14*x_120 + 14*x_216 + 14*x_220 }-> s140 :|: s134 >= 0, s134 <= 0, s135 >= 0, s135 <= 0, s136 >= 0, s136 <= s135, s137 >= 0, s137 <= 0, s138 >= 0, s138 <= 0, s139 >= 0, s139 <= s138, s140 >= 0, s140 <= s139, x_216 >= 0, x_120 >= 0, x_116 >= 0, z = 1 + x_116 + x_216, z' = 1 + x_120 + x_220, x_220 >= 0 encode_f(z, z') -{ 11 + 14*x_116 + 14*x_216 }-> s144 :|: s141 >= 0, s141 <= 0, s142 >= 0, s142 <= 0, s143 >= 0, s143 <= s142, s144 >= 0, s144 <= 0, x_216 >= 0, x_116 >= 0, z = 1 + x_116 + x_216, z' >= 0 encode_f(z, z') -{ 11 + 14*x_122 + 14*x_222 }-> s148 :|: s145 >= 0, s145 <= 0, s146 >= 0, s146 <= 0, s147 >= 0, s147 <= s146, s148 >= 0, s148 <= s147, z >= 0, x_222 >= 0, x_122 >= 0, z' = 1 + x_122 + x_222 encode_f(z, z') -{ 22 + 14*x_115 + 14*x_117 + 14*x_215 + 14*x_217 }-> s53 :|: s47 >= 0, s47 <= 0, s48 >= 0, s48 <= 0, s49 >= 0, s49 <= s48, s50 >= 0, s50 <= 0, s51 >= 0, s51 <= 0, s52 >= 0, s52 <= s51, s53 >= 0, s53 <= s52, x_117 >= 0, x_215 >= 0, x_115 >= 0, z = 1 + x_115 + x_215, z' = 1 + x_117 + x_217, x_217 >= 0 encode_f(z, z') -{ 12 + 14*x_115 + 14*x_215 }-> s57 :|: s54 >= 0, s54 <= 0, s55 >= 0, s55 <= 0, s56 >= 0, s56 <= s55, s57 >= 0, s57 <= 0, x_215 >= 0, x_115 >= 0, z = 1 + x_115 + x_215, z' >= 0 encode_f(z, z') -{ 12 + 14*x_121 + 14*x_221 }-> s61 :|: s58 >= 0, s58 <= 0, s59 >= 0, s59 <= 0, s60 >= 0, s60 <= s59, s61 >= 0, s61 <= s60, z >= 0, z' = 1 + x_121 + x_221, x_221 >= 0, x_121 >= 0 encode_f(z, z') -{ 0 }-> 0 :|: z >= 0, z' >= 0 encode_h(z, z') -{ 21 + 14*x_123 + 14*x_125 + 14*x_223 + 14*x_225 }-> s155 :|: s149 >= 0, s149 <= 0, s150 >= 0, s150 <= 0, s151 >= 0, s151 <= s150, s152 >= 0, s152 <= 0, s153 >= 0, s153 <= 0, s154 >= 0, s154 <= s153, s155 >= 0, s155 <= s154, z = 1 + x_123 + x_223, x_123 >= 0, z' = 1 + x_125 + x_225, x_223 >= 0, x_125 >= 0, x_225 >= 0 encode_h(z, z') -{ 20 + 14*x_123 + 14*x_126 + 14*x_223 + 14*x_226 }-> s162 :|: s156 >= 0, s156 <= 0, s157 >= 0, s157 <= 0, s158 >= 0, s158 <= s157, s159 >= 0, s159 <= 0, s160 >= 0, s160 <= 0, s161 >= 0, s161 <= s160, s162 >= 0, s162 <= s161, z = 1 + x_123 + x_223, x_226 >= 0, x_123 >= 0, x_223 >= 0, x_126 >= 0, z' = 1 + x_126 + x_226 encode_h(z, z') -{ 11 + 14*x_123 + 14*x_223 }-> s166 :|: s163 >= 0, s163 <= 0, s164 >= 0, s164 <= 0, s165 >= 0, s165 <= s164, s166 >= 0, s166 <= 0, z = 1 + x_123 + x_223, x_123 >= 0, x_223 >= 0, z' >= 0 encode_h(z, z') -{ 20 + 14*x_124 + 14*x_127 + 14*x_224 + 14*x_227 }-> s173 :|: s167 >= 0, s167 <= 0, s168 >= 0, s168 <= 0, s169 >= 0, s169 <= s168, s170 >= 0, s170 <= 0, s171 >= 0, s171 <= 0, s172 >= 0, s172 <= s171, s173 >= 0, s173 <= s172, z = 1 + x_124 + x_224, x_124 >= 0, x_127 >= 0, x_224 >= 0, z' = 1 + x_127 + x_227, x_227 >= 0 encode_h(z, z') -{ 11 + 14*x_129 + 14*x_229 }-> s177 :|: s174 >= 0, s174 <= 0, s175 >= 0, s175 <= 0, s176 >= 0, s176 <= s175, s177 >= 0, s177 <= s176, z >= 0, z' = 1 + x_129 + x_229, x_229 >= 0, x_129 >= 0 encode_h(z, z') -{ 19 + 14*x_124 + 14*x_128 + 14*x_224 + 14*x_228 }-> s23 :|: s17 >= 0, s17 <= 0, s18 >= 0, s18 <= 0, s19 >= 0, s19 <= s18, s20 >= 0, s20 <= 0, s21 >= 0, s21 <= 0, s22 >= 0, s22 <= s21, s23 >= 0, s23 <= s22, z = 1 + x_124 + x_224, x_124 >= 0, x_128 >= 0, z' = 1 + x_128 + x_228, x_224 >= 0, x_228 >= 0 encode_h(z, z') -{ 10 + 14*x_124 + 14*x_224 }-> s27 :|: s24 >= 0, s24 <= 0, s25 >= 0, s25 <= 0, s26 >= 0, s26 <= s25, s27 >= 0, s27 <= 0, z = 1 + x_124 + x_224, x_124 >= 0, x_224 >= 0, z' >= 0 encode_h(z, z') -{ 10 + 14*x_130 + 14*x_230 }-> s31 :|: s28 >= 0, s28 <= 0, s29 >= 0, s29 <= 0, s30 >= 0, s30 <= s29, s31 >= 0, s31 <= s30, z >= 0, x_130 >= 0, z' = 1 + x_130 + x_230, x_230 >= 0 encode_h(z, z') -{ 1 }-> x :|: z >= 0, z' >= 0, 0 = x, x >= 0 encode_h(z, z') -{ 0 }-> 0 :|: z >= 0, z' >= 0 encode_h(z, z') -{ 0 }-> 0 :|: z >= 0, z' >= 0, v0 >= 0, v1 >= 0, 0 = v0, 0 = v1 f(z, z') -{ 2 }-> z' :|: z >= 0, z' >= 0, z = z' f(z, z') -{ 1 }-> 0 :|: z >= 0, z' >= 0 h(z, z') -{ 1 }-> z' :|: z' >= 0, z = z' h(z, z') -{ 0 }-> 0 :|: z >= 0, z' >= 0 Function symbols to be analyzed: {encode_h} Previous analysis results are: h: runtime: O(1) [1], size: O(n^1) [z'] f: runtime: O(1) [2], size: O(n^1) [z'] encArg: runtime: O(n^1) [4 + 14*z], size: O(1) [0] encode_f: runtime: O(n^1) [8 + 14*z + 14*z'], size: O(1) [0] ---------------------------------------- (47) IntTrsBoundProof (UPPER BOUND(ID)) Computed SIZE bound using CoFloCo for: encode_h after applying outer abstraction to obtain an ITS, resulting in: O(1) with polynomial bound: 0 ---------------------------------------- (48) Obligation: Complexity RNTS consisting of the following rules: encArg(z) -{ 2 }-> s :|: s >= 0, s <= y, x_1 >= 0, z = 1 + x_1 + x_2, x_2 >= 0, x >= 0, y >= 0, 0 = x, 0 = y encArg(z) -{ 2 }-> s' :|: s' >= 0, s' <= x, x_1 >= 0, z = 1 + x_1 + x_2, x_2 >= 0, x >= 0, y >= 0, 0 = x, 0 = y encArg(z) -{ 20 + 14*x_110 + 14*x_17 + 14*x_210 + 14*x_27 }-> s104 :|: s98 >= 0, s98 <= 0, s99 >= 0, s99 <= 0, s100 >= 0, s100 <= s99, s101 >= 0, s101 <= 0, s102 >= 0, s102 <= 0, s103 >= 0, s103 <= s102, s104 >= 0, s104 <= s103, z = 1 + (1 + x_17 + x_27) + (1 + x_110 + x_210), x_17 >= 0, x_27 >= 0, x_110 >= 0, x_210 >= 0 encArg(z) -{ 11 + 14*x_17 + 14*x_27 }-> s108 :|: s105 >= 0, s105 <= 0, s106 >= 0, s106 <= 0, s107 >= 0, s107 <= s106, s108 >= 0, s108 <= 0, x_17 >= 0, x_27 >= 0, x_2 >= 0, z = 1 + (1 + x_17 + x_27) + x_2 encArg(z) -{ 20 + 14*x_111 + 14*x_18 + 14*x_211 + 14*x_28 }-> s115 :|: s109 >= 0, s109 <= 0, s110 >= 0, s110 <= 0, s111 >= 0, s111 <= s110, s112 >= 0, s112 <= 0, s113 >= 0, s113 <= 0, s114 >= 0, s114 <= s113, s115 >= 0, s115 <= s114, z = 1 + (1 + x_18 + x_28) + (1 + x_111 + x_211), x_18 >= 0, x_28 >= 0, x_211 >= 0, x_111 >= 0 encArg(z) -{ 11 + 14*x_113 + 14*x_213 }-> s119 :|: s116 >= 0, s116 <= 0, s117 >= 0, s117 <= 0, s118 >= 0, s118 <= s117, s119 >= 0, s119 <= s118, x_1 >= 0, x_113 >= 0, x_213 >= 0, z = 1 + x_1 + (1 + x_113 + x_213) encArg(z) -{ 10 + 14*x_18 + 14*x_28 }-> s12 :|: s9 >= 0, s9 <= 0, s10 >= 0, s10 <= 0, s11 >= 0, s11 <= s10, s12 >= 0, s12 <= 0, z = 1 + (1 + x_18 + x_28) + x_2, x_2 >= 0, x_18 >= 0, x_28 >= 0 encArg(z) -{ 10 + 14*x_114 + 14*x_214 }-> s16 :|: s13 >= 0, s13 <= 0, s14 >= 0, s14 <= 0, s15 >= 0, s15 <= s14, s16 >= 0, s16 <= s15, z = 1 + x_1 + (1 + x_114 + x_214), x_1 >= 0, x_114 >= 0, x_214 >= 0 encArg(z) -{ 22 + 14*x_1' + 14*x_11 + 14*x_2' + 14*x_21 }-> s38 :|: s32 >= 0, s32 <= 0, s33 >= 0, s33 <= 0, s34 >= 0, s34 <= s33, s35 >= 0, s35 <= 0, s36 >= 0, s36 <= 0, s37 >= 0, s37 <= s36, s38 >= 0, s38 <= s37, x_11 >= 0, x_2' >= 0, x_1' >= 0, x_21 >= 0, z = 1 + (1 + x_1' + x_2') + (1 + x_11 + x_21) encArg(z) -{ 12 + 14*x_1' + 14*x_2' }-> s42 :|: s39 >= 0, s39 <= 0, s40 >= 0, s40 <= 0, s41 >= 0, s41 <= s40, s42 >= 0, s42 <= 0, z = 1 + (1 + x_1' + x_2') + x_2, x_2' >= 0, x_1' >= 0, x_2 >= 0 encArg(z) -{ 12 + 14*x_15 + 14*x_25 }-> s46 :|: s43 >= 0, s43 <= 0, s44 >= 0, s44 <= 0, s45 >= 0, s45 <= s44, s46 >= 0, s46 <= s45, x_15 >= 0, x_1 >= 0, x_25 >= 0, z = 1 + x_1 + (1 + x_15 + x_25) encArg(z) -{ 21 + 14*x_1' + 14*x_12 + 14*x_2' + 14*x_22 }-> s68 :|: s62 >= 0, s62 <= 0, s63 >= 0, s63 <= 0, s64 >= 0, s64 <= s63, s65 >= 0, s65 <= 0, s66 >= 0, s66 <= 0, s67 >= 0, s67 <= s66, s68 >= 0, s68 <= s67, x_2' >= 0, z = 1 + (1 + x_1' + x_2') + (1 + x_12 + x_22), x_1' >= 0, x_12 >= 0, x_22 >= 0 encArg(z) -{ 21 + 14*x_1'' + 14*x_13 + 14*x_2'' + 14*x_23 }-> s75 :|: s69 >= 0, s69 <= 0, s70 >= 0, s70 <= 0, s71 >= 0, s71 <= s70, s72 >= 0, s72 <= 0, s73 >= 0, s73 <= 0, s74 >= 0, s74 <= s73, s75 >= 0, s75 <= s74, x_1'' >= 0, x_13 >= 0, x_2'' >= 0, x_23 >= 0, z = 1 + (1 + x_1'' + x_2'') + (1 + x_13 + x_23) encArg(z) -{ 19 + 14*x_112 + 14*x_18 + 14*x_212 + 14*x_28 }-> s8 :|: s2 >= 0, s2 <= 0, s3 >= 0, s3 <= 0, s4 >= 0, s4 <= s3, s5 >= 0, s5 <= 0, s6 >= 0, s6 <= 0, s7 >= 0, s7 <= s6, s8 >= 0, s8 <= s7, x_212 >= 0, z = 1 + (1 + x_18 + x_28) + (1 + x_112 + x_212), x_18 >= 0, x_28 >= 0, x_112 >= 0 encArg(z) -{ 20 + 14*x_1'' + 14*x_14 + 14*x_2'' + 14*x_24 }-> s82 :|: s76 >= 0, s76 <= 0, s77 >= 0, s77 <= 0, s78 >= 0, s78 <= s77, s79 >= 0, s79 <= 0, s80 >= 0, s80 <= 0, s81 >= 0, s81 <= s80, s82 >= 0, s82 <= s81, x_1'' >= 0, x_14 >= 0, x_2'' >= 0, x_24 >= 0, z = 1 + (1 + x_1'' + x_2'') + (1 + x_14 + x_24) encArg(z) -{ 11 + 14*x_1'' + 14*x_2'' }-> s86 :|: s83 >= 0, s83 <= 0, s84 >= 0, s84 <= 0, s85 >= 0, s85 <= s84, s86 >= 0, s86 <= 0, x_1'' >= 0, z = 1 + (1 + x_1'' + x_2'') + x_2, x_2'' >= 0, x_2 >= 0 encArg(z) -{ 11 + 14*x_16 + 14*x_26 }-> s90 :|: s87 >= 0, s87 <= 0, s88 >= 0, s88 <= 0, s89 >= 0, s89 <= s88, s90 >= 0, s90 <= s89, x_1 >= 0, x_16 >= 0, x_26 >= 0, z = 1 + x_1 + (1 + x_16 + x_26) encArg(z) -{ 21 + 14*x_17 + 14*x_19 + 14*x_27 + 14*x_29 }-> s97 :|: s91 >= 0, s91 <= 0, s92 >= 0, s92 <= 0, s93 >= 0, s93 <= s92, s94 >= 0, s94 <= 0, s95 >= 0, s95 <= 0, s96 >= 0, s96 <= s95, s97 >= 0, s97 <= s96, z = 1 + (1 + x_17 + x_27) + (1 + x_19 + x_29), x_17 >= 0, x_27 >= 0, x_19 >= 0, x_29 >= 0 encArg(z) -{ 1 }-> x :|: x_1 >= 0, z = 1 + x_1 + x_2, x_2 >= 0, 0 = x, x >= 0 encArg(z) -{ 0 }-> 0 :|: z >= 0 encArg(z) -{ 0 }-> 0 :|: x_1 >= 0, z = 1 + x_1 + x_2, x_2 >= 0, v0 >= 0, v1 >= 0, 0 = v0, 0 = v1 encode_f(z, z') -{ 2 }-> s'' :|: s'' >= 0, s'' <= y, z >= 0, z' >= 0, x >= 0, y >= 0, 0 = x, 0 = y encode_f(z, z') -{ 2 }-> s1 :|: s1 >= 0, s1 <= x, z >= 0, z' >= 0, x >= 0, y >= 0, 0 = x, 0 = y encode_f(z, z') -{ 21 + 14*x_115 + 14*x_118 + 14*x_215 + 14*x_218 }-> s126 :|: s120 >= 0, s120 <= 0, s121 >= 0, s121 <= 0, s122 >= 0, s122 <= s121, s123 >= 0, s123 <= 0, s124 >= 0, s124 <= 0, s125 >= 0, s125 <= s124, s126 >= 0, s126 <= s125, x_215 >= 0, x_115 >= 0, z = 1 + x_115 + x_215, x_218 >= 0, z' = 1 + x_118 + x_218, x_118 >= 0 encode_f(z, z') -{ 21 + 14*x_116 + 14*x_119 + 14*x_216 + 14*x_219 }-> s133 :|: s127 >= 0, s127 <= 0, s128 >= 0, s128 <= 0, s129 >= 0, s129 <= s128, s130 >= 0, s130 <= 0, s131 >= 0, s131 <= 0, s132 >= 0, s132 <= s131, s133 >= 0, s133 <= s132, x_216 >= 0, z' = 1 + x_119 + x_219, x_116 >= 0, z = 1 + x_116 + x_216, x_219 >= 0, x_119 >= 0 encode_f(z, z') -{ 20 + 14*x_116 + 14*x_120 + 14*x_216 + 14*x_220 }-> s140 :|: s134 >= 0, s134 <= 0, s135 >= 0, s135 <= 0, s136 >= 0, s136 <= s135, s137 >= 0, s137 <= 0, s138 >= 0, s138 <= 0, s139 >= 0, s139 <= s138, s140 >= 0, s140 <= s139, x_216 >= 0, x_120 >= 0, x_116 >= 0, z = 1 + x_116 + x_216, z' = 1 + x_120 + x_220, x_220 >= 0 encode_f(z, z') -{ 11 + 14*x_116 + 14*x_216 }-> s144 :|: s141 >= 0, s141 <= 0, s142 >= 0, s142 <= 0, s143 >= 0, s143 <= s142, s144 >= 0, s144 <= 0, x_216 >= 0, x_116 >= 0, z = 1 + x_116 + x_216, z' >= 0 encode_f(z, z') -{ 11 + 14*x_122 + 14*x_222 }-> s148 :|: s145 >= 0, s145 <= 0, s146 >= 0, s146 <= 0, s147 >= 0, s147 <= s146, s148 >= 0, s148 <= s147, z >= 0, x_222 >= 0, x_122 >= 0, z' = 1 + x_122 + x_222 encode_f(z, z') -{ 22 + 14*x_115 + 14*x_117 + 14*x_215 + 14*x_217 }-> s53 :|: s47 >= 0, s47 <= 0, s48 >= 0, s48 <= 0, s49 >= 0, s49 <= s48, s50 >= 0, s50 <= 0, s51 >= 0, s51 <= 0, s52 >= 0, s52 <= s51, s53 >= 0, s53 <= s52, x_117 >= 0, x_215 >= 0, x_115 >= 0, z = 1 + x_115 + x_215, z' = 1 + x_117 + x_217, x_217 >= 0 encode_f(z, z') -{ 12 + 14*x_115 + 14*x_215 }-> s57 :|: s54 >= 0, s54 <= 0, s55 >= 0, s55 <= 0, s56 >= 0, s56 <= s55, s57 >= 0, s57 <= 0, x_215 >= 0, x_115 >= 0, z = 1 + x_115 + x_215, z' >= 0 encode_f(z, z') -{ 12 + 14*x_121 + 14*x_221 }-> s61 :|: s58 >= 0, s58 <= 0, s59 >= 0, s59 <= 0, s60 >= 0, s60 <= s59, s61 >= 0, s61 <= s60, z >= 0, z' = 1 + x_121 + x_221, x_221 >= 0, x_121 >= 0 encode_f(z, z') -{ 0 }-> 0 :|: z >= 0, z' >= 0 encode_h(z, z') -{ 21 + 14*x_123 + 14*x_125 + 14*x_223 + 14*x_225 }-> s155 :|: s149 >= 0, s149 <= 0, s150 >= 0, s150 <= 0, s151 >= 0, s151 <= s150, s152 >= 0, s152 <= 0, s153 >= 0, s153 <= 0, s154 >= 0, s154 <= s153, s155 >= 0, s155 <= s154, z = 1 + x_123 + x_223, x_123 >= 0, z' = 1 + x_125 + x_225, x_223 >= 0, x_125 >= 0, x_225 >= 0 encode_h(z, z') -{ 20 + 14*x_123 + 14*x_126 + 14*x_223 + 14*x_226 }-> s162 :|: s156 >= 0, s156 <= 0, s157 >= 0, s157 <= 0, s158 >= 0, s158 <= s157, s159 >= 0, s159 <= 0, s160 >= 0, s160 <= 0, s161 >= 0, s161 <= s160, s162 >= 0, s162 <= s161, z = 1 + x_123 + x_223, x_226 >= 0, x_123 >= 0, x_223 >= 0, x_126 >= 0, z' = 1 + x_126 + x_226 encode_h(z, z') -{ 11 + 14*x_123 + 14*x_223 }-> s166 :|: s163 >= 0, s163 <= 0, s164 >= 0, s164 <= 0, s165 >= 0, s165 <= s164, s166 >= 0, s166 <= 0, z = 1 + x_123 + x_223, x_123 >= 0, x_223 >= 0, z' >= 0 encode_h(z, z') -{ 20 + 14*x_124 + 14*x_127 + 14*x_224 + 14*x_227 }-> s173 :|: s167 >= 0, s167 <= 0, s168 >= 0, s168 <= 0, s169 >= 0, s169 <= s168, s170 >= 0, s170 <= 0, s171 >= 0, s171 <= 0, s172 >= 0, s172 <= s171, s173 >= 0, s173 <= s172, z = 1 + x_124 + x_224, x_124 >= 0, x_127 >= 0, x_224 >= 0, z' = 1 + x_127 + x_227, x_227 >= 0 encode_h(z, z') -{ 11 + 14*x_129 + 14*x_229 }-> s177 :|: s174 >= 0, s174 <= 0, s175 >= 0, s175 <= 0, s176 >= 0, s176 <= s175, s177 >= 0, s177 <= s176, z >= 0, z' = 1 + x_129 + x_229, x_229 >= 0, x_129 >= 0 encode_h(z, z') -{ 19 + 14*x_124 + 14*x_128 + 14*x_224 + 14*x_228 }-> s23 :|: s17 >= 0, s17 <= 0, s18 >= 0, s18 <= 0, s19 >= 0, s19 <= s18, s20 >= 0, s20 <= 0, s21 >= 0, s21 <= 0, s22 >= 0, s22 <= s21, s23 >= 0, s23 <= s22, z = 1 + x_124 + x_224, x_124 >= 0, x_128 >= 0, z' = 1 + x_128 + x_228, x_224 >= 0, x_228 >= 0 encode_h(z, z') -{ 10 + 14*x_124 + 14*x_224 }-> s27 :|: s24 >= 0, s24 <= 0, s25 >= 0, s25 <= 0, s26 >= 0, s26 <= s25, s27 >= 0, s27 <= 0, z = 1 + x_124 + x_224, x_124 >= 0, x_224 >= 0, z' >= 0 encode_h(z, z') -{ 10 + 14*x_130 + 14*x_230 }-> s31 :|: s28 >= 0, s28 <= 0, s29 >= 0, s29 <= 0, s30 >= 0, s30 <= s29, s31 >= 0, s31 <= s30, z >= 0, x_130 >= 0, z' = 1 + x_130 + x_230, x_230 >= 0 encode_h(z, z') -{ 1 }-> x :|: z >= 0, z' >= 0, 0 = x, x >= 0 encode_h(z, z') -{ 0 }-> 0 :|: z >= 0, z' >= 0 encode_h(z, z') -{ 0 }-> 0 :|: z >= 0, z' >= 0, v0 >= 0, v1 >= 0, 0 = v0, 0 = v1 f(z, z') -{ 2 }-> z' :|: z >= 0, z' >= 0, z = z' f(z, z') -{ 1 }-> 0 :|: z >= 0, z' >= 0 h(z, z') -{ 1 }-> z' :|: z' >= 0, z = z' h(z, z') -{ 0 }-> 0 :|: z >= 0, z' >= 0 Function symbols to be analyzed: {encode_h} Previous analysis results are: h: runtime: O(1) [1], size: O(n^1) [z'] f: runtime: O(1) [2], size: O(n^1) [z'] encArg: runtime: O(n^1) [4 + 14*z], size: O(1) [0] encode_f: runtime: O(n^1) [8 + 14*z + 14*z'], size: O(1) [0] encode_h: runtime: ?, size: O(1) [0] ---------------------------------------- (49) IntTrsBoundProof (UPPER BOUND(ID)) Computed RUNTIME bound using CoFloCo for: encode_h after applying outer abstraction to obtain an ITS, resulting in: O(n^1) with polynomial bound: 9 + 14*z + 14*z' ---------------------------------------- (50) Obligation: Complexity RNTS consisting of the following rules: encArg(z) -{ 2 }-> s :|: s >= 0, s <= y, x_1 >= 0, z = 1 + x_1 + x_2, x_2 >= 0, x >= 0, y >= 0, 0 = x, 0 = y encArg(z) -{ 2 }-> s' :|: s' >= 0, s' <= x, x_1 >= 0, z = 1 + x_1 + x_2, x_2 >= 0, x >= 0, y >= 0, 0 = x, 0 = y encArg(z) -{ 20 + 14*x_110 + 14*x_17 + 14*x_210 + 14*x_27 }-> s104 :|: s98 >= 0, s98 <= 0, s99 >= 0, s99 <= 0, s100 >= 0, s100 <= s99, s101 >= 0, s101 <= 0, s102 >= 0, s102 <= 0, s103 >= 0, s103 <= s102, s104 >= 0, s104 <= s103, z = 1 + (1 + x_17 + x_27) + (1 + x_110 + x_210), x_17 >= 0, x_27 >= 0, x_110 >= 0, x_210 >= 0 encArg(z) -{ 11 + 14*x_17 + 14*x_27 }-> s108 :|: s105 >= 0, s105 <= 0, s106 >= 0, s106 <= 0, s107 >= 0, s107 <= s106, s108 >= 0, s108 <= 0, x_17 >= 0, x_27 >= 0, x_2 >= 0, z = 1 + (1 + x_17 + x_27) + x_2 encArg(z) -{ 20 + 14*x_111 + 14*x_18 + 14*x_211 + 14*x_28 }-> s115 :|: s109 >= 0, s109 <= 0, s110 >= 0, s110 <= 0, s111 >= 0, s111 <= s110, s112 >= 0, s112 <= 0, s113 >= 0, s113 <= 0, s114 >= 0, s114 <= s113, s115 >= 0, s115 <= s114, z = 1 + (1 + x_18 + x_28) + (1 + x_111 + x_211), x_18 >= 0, x_28 >= 0, x_211 >= 0, x_111 >= 0 encArg(z) -{ 11 + 14*x_113 + 14*x_213 }-> s119 :|: s116 >= 0, s116 <= 0, s117 >= 0, s117 <= 0, s118 >= 0, s118 <= s117, s119 >= 0, s119 <= s118, x_1 >= 0, x_113 >= 0, x_213 >= 0, z = 1 + x_1 + (1 + x_113 + x_213) encArg(z) -{ 10 + 14*x_18 + 14*x_28 }-> s12 :|: s9 >= 0, s9 <= 0, s10 >= 0, s10 <= 0, s11 >= 0, s11 <= s10, s12 >= 0, s12 <= 0, z = 1 + (1 + x_18 + x_28) + x_2, x_2 >= 0, x_18 >= 0, x_28 >= 0 encArg(z) -{ 10 + 14*x_114 + 14*x_214 }-> s16 :|: s13 >= 0, s13 <= 0, s14 >= 0, s14 <= 0, s15 >= 0, s15 <= s14, s16 >= 0, s16 <= s15, z = 1 + x_1 + (1 + x_114 + x_214), x_1 >= 0, x_114 >= 0, x_214 >= 0 encArg(z) -{ 22 + 14*x_1' + 14*x_11 + 14*x_2' + 14*x_21 }-> s38 :|: s32 >= 0, s32 <= 0, s33 >= 0, s33 <= 0, s34 >= 0, s34 <= s33, s35 >= 0, s35 <= 0, s36 >= 0, s36 <= 0, s37 >= 0, s37 <= s36, s38 >= 0, s38 <= s37, x_11 >= 0, x_2' >= 0, x_1' >= 0, x_21 >= 0, z = 1 + (1 + x_1' + x_2') + (1 + x_11 + x_21) encArg(z) -{ 12 + 14*x_1' + 14*x_2' }-> s42 :|: s39 >= 0, s39 <= 0, s40 >= 0, s40 <= 0, s41 >= 0, s41 <= s40, s42 >= 0, s42 <= 0, z = 1 + (1 + x_1' + x_2') + x_2, x_2' >= 0, x_1' >= 0, x_2 >= 0 encArg(z) -{ 12 + 14*x_15 + 14*x_25 }-> s46 :|: s43 >= 0, s43 <= 0, s44 >= 0, s44 <= 0, s45 >= 0, s45 <= s44, s46 >= 0, s46 <= s45, x_15 >= 0, x_1 >= 0, x_25 >= 0, z = 1 + x_1 + (1 + x_15 + x_25) encArg(z) -{ 21 + 14*x_1' + 14*x_12 + 14*x_2' + 14*x_22 }-> s68 :|: s62 >= 0, s62 <= 0, s63 >= 0, s63 <= 0, s64 >= 0, s64 <= s63, s65 >= 0, s65 <= 0, s66 >= 0, s66 <= 0, s67 >= 0, s67 <= s66, s68 >= 0, s68 <= s67, x_2' >= 0, z = 1 + (1 + x_1' + x_2') + (1 + x_12 + x_22), x_1' >= 0, x_12 >= 0, x_22 >= 0 encArg(z) -{ 21 + 14*x_1'' + 14*x_13 + 14*x_2'' + 14*x_23 }-> s75 :|: s69 >= 0, s69 <= 0, s70 >= 0, s70 <= 0, s71 >= 0, s71 <= s70, s72 >= 0, s72 <= 0, s73 >= 0, s73 <= 0, s74 >= 0, s74 <= s73, s75 >= 0, s75 <= s74, x_1'' >= 0, x_13 >= 0, x_2'' >= 0, x_23 >= 0, z = 1 + (1 + x_1'' + x_2'') + (1 + x_13 + x_23) encArg(z) -{ 19 + 14*x_112 + 14*x_18 + 14*x_212 + 14*x_28 }-> s8 :|: s2 >= 0, s2 <= 0, s3 >= 0, s3 <= 0, s4 >= 0, s4 <= s3, s5 >= 0, s5 <= 0, s6 >= 0, s6 <= 0, s7 >= 0, s7 <= s6, s8 >= 0, s8 <= s7, x_212 >= 0, z = 1 + (1 + x_18 + x_28) + (1 + x_112 + x_212), x_18 >= 0, x_28 >= 0, x_112 >= 0 encArg(z) -{ 20 + 14*x_1'' + 14*x_14 + 14*x_2'' + 14*x_24 }-> s82 :|: s76 >= 0, s76 <= 0, s77 >= 0, s77 <= 0, s78 >= 0, s78 <= s77, s79 >= 0, s79 <= 0, s80 >= 0, s80 <= 0, s81 >= 0, s81 <= s80, s82 >= 0, s82 <= s81, x_1'' >= 0, x_14 >= 0, x_2'' >= 0, x_24 >= 0, z = 1 + (1 + x_1'' + x_2'') + (1 + x_14 + x_24) encArg(z) -{ 11 + 14*x_1'' + 14*x_2'' }-> s86 :|: s83 >= 0, s83 <= 0, s84 >= 0, s84 <= 0, s85 >= 0, s85 <= s84, s86 >= 0, s86 <= 0, x_1'' >= 0, z = 1 + (1 + x_1'' + x_2'') + x_2, x_2'' >= 0, x_2 >= 0 encArg(z) -{ 11 + 14*x_16 + 14*x_26 }-> s90 :|: s87 >= 0, s87 <= 0, s88 >= 0, s88 <= 0, s89 >= 0, s89 <= s88, s90 >= 0, s90 <= s89, x_1 >= 0, x_16 >= 0, x_26 >= 0, z = 1 + x_1 + (1 + x_16 + x_26) encArg(z) -{ 21 + 14*x_17 + 14*x_19 + 14*x_27 + 14*x_29 }-> s97 :|: s91 >= 0, s91 <= 0, s92 >= 0, s92 <= 0, s93 >= 0, s93 <= s92, s94 >= 0, s94 <= 0, s95 >= 0, s95 <= 0, s96 >= 0, s96 <= s95, s97 >= 0, s97 <= s96, z = 1 + (1 + x_17 + x_27) + (1 + x_19 + x_29), x_17 >= 0, x_27 >= 0, x_19 >= 0, x_29 >= 0 encArg(z) -{ 1 }-> x :|: x_1 >= 0, z = 1 + x_1 + x_2, x_2 >= 0, 0 = x, x >= 0 encArg(z) -{ 0 }-> 0 :|: z >= 0 encArg(z) -{ 0 }-> 0 :|: x_1 >= 0, z = 1 + x_1 + x_2, x_2 >= 0, v0 >= 0, v1 >= 0, 0 = v0, 0 = v1 encode_f(z, z') -{ 2 }-> s'' :|: s'' >= 0, s'' <= y, z >= 0, z' >= 0, x >= 0, y >= 0, 0 = x, 0 = y encode_f(z, z') -{ 2 }-> s1 :|: s1 >= 0, s1 <= x, z >= 0, z' >= 0, x >= 0, y >= 0, 0 = x, 0 = y encode_f(z, z') -{ 21 + 14*x_115 + 14*x_118 + 14*x_215 + 14*x_218 }-> s126 :|: s120 >= 0, s120 <= 0, s121 >= 0, s121 <= 0, s122 >= 0, s122 <= s121, s123 >= 0, s123 <= 0, s124 >= 0, s124 <= 0, s125 >= 0, s125 <= s124, s126 >= 0, s126 <= s125, x_215 >= 0, x_115 >= 0, z = 1 + x_115 + x_215, x_218 >= 0, z' = 1 + x_118 + x_218, x_118 >= 0 encode_f(z, z') -{ 21 + 14*x_116 + 14*x_119 + 14*x_216 + 14*x_219 }-> s133 :|: s127 >= 0, s127 <= 0, s128 >= 0, s128 <= 0, s129 >= 0, s129 <= s128, s130 >= 0, s130 <= 0, s131 >= 0, s131 <= 0, s132 >= 0, s132 <= s131, s133 >= 0, s133 <= s132, x_216 >= 0, z' = 1 + x_119 + x_219, x_116 >= 0, z = 1 + x_116 + x_216, x_219 >= 0, x_119 >= 0 encode_f(z, z') -{ 20 + 14*x_116 + 14*x_120 + 14*x_216 + 14*x_220 }-> s140 :|: s134 >= 0, s134 <= 0, s135 >= 0, s135 <= 0, s136 >= 0, s136 <= s135, s137 >= 0, s137 <= 0, s138 >= 0, s138 <= 0, s139 >= 0, s139 <= s138, s140 >= 0, s140 <= s139, x_216 >= 0, x_120 >= 0, x_116 >= 0, z = 1 + x_116 + x_216, z' = 1 + x_120 + x_220, x_220 >= 0 encode_f(z, z') -{ 11 + 14*x_116 + 14*x_216 }-> s144 :|: s141 >= 0, s141 <= 0, s142 >= 0, s142 <= 0, s143 >= 0, s143 <= s142, s144 >= 0, s144 <= 0, x_216 >= 0, x_116 >= 0, z = 1 + x_116 + x_216, z' >= 0 encode_f(z, z') -{ 11 + 14*x_122 + 14*x_222 }-> s148 :|: s145 >= 0, s145 <= 0, s146 >= 0, s146 <= 0, s147 >= 0, s147 <= s146, s148 >= 0, s148 <= s147, z >= 0, x_222 >= 0, x_122 >= 0, z' = 1 + x_122 + x_222 encode_f(z, z') -{ 22 + 14*x_115 + 14*x_117 + 14*x_215 + 14*x_217 }-> s53 :|: s47 >= 0, s47 <= 0, s48 >= 0, s48 <= 0, s49 >= 0, s49 <= s48, s50 >= 0, s50 <= 0, s51 >= 0, s51 <= 0, s52 >= 0, s52 <= s51, s53 >= 0, s53 <= s52, x_117 >= 0, x_215 >= 0, x_115 >= 0, z = 1 + x_115 + x_215, z' = 1 + x_117 + x_217, x_217 >= 0 encode_f(z, z') -{ 12 + 14*x_115 + 14*x_215 }-> s57 :|: s54 >= 0, s54 <= 0, s55 >= 0, s55 <= 0, s56 >= 0, s56 <= s55, s57 >= 0, s57 <= 0, x_215 >= 0, x_115 >= 0, z = 1 + x_115 + x_215, z' >= 0 encode_f(z, z') -{ 12 + 14*x_121 + 14*x_221 }-> s61 :|: s58 >= 0, s58 <= 0, s59 >= 0, s59 <= 0, s60 >= 0, s60 <= s59, s61 >= 0, s61 <= s60, z >= 0, z' = 1 + x_121 + x_221, x_221 >= 0, x_121 >= 0 encode_f(z, z') -{ 0 }-> 0 :|: z >= 0, z' >= 0 encode_h(z, z') -{ 21 + 14*x_123 + 14*x_125 + 14*x_223 + 14*x_225 }-> s155 :|: s149 >= 0, s149 <= 0, s150 >= 0, s150 <= 0, s151 >= 0, s151 <= s150, s152 >= 0, s152 <= 0, s153 >= 0, s153 <= 0, s154 >= 0, s154 <= s153, s155 >= 0, s155 <= s154, z = 1 + x_123 + x_223, x_123 >= 0, z' = 1 + x_125 + x_225, x_223 >= 0, x_125 >= 0, x_225 >= 0 encode_h(z, z') -{ 20 + 14*x_123 + 14*x_126 + 14*x_223 + 14*x_226 }-> s162 :|: s156 >= 0, s156 <= 0, s157 >= 0, s157 <= 0, s158 >= 0, s158 <= s157, s159 >= 0, s159 <= 0, s160 >= 0, s160 <= 0, s161 >= 0, s161 <= s160, s162 >= 0, s162 <= s161, z = 1 + x_123 + x_223, x_226 >= 0, x_123 >= 0, x_223 >= 0, x_126 >= 0, z' = 1 + x_126 + x_226 encode_h(z, z') -{ 11 + 14*x_123 + 14*x_223 }-> s166 :|: s163 >= 0, s163 <= 0, s164 >= 0, s164 <= 0, s165 >= 0, s165 <= s164, s166 >= 0, s166 <= 0, z = 1 + x_123 + x_223, x_123 >= 0, x_223 >= 0, z' >= 0 encode_h(z, z') -{ 20 + 14*x_124 + 14*x_127 + 14*x_224 + 14*x_227 }-> s173 :|: s167 >= 0, s167 <= 0, s168 >= 0, s168 <= 0, s169 >= 0, s169 <= s168, s170 >= 0, s170 <= 0, s171 >= 0, s171 <= 0, s172 >= 0, s172 <= s171, s173 >= 0, s173 <= s172, z = 1 + x_124 + x_224, x_124 >= 0, x_127 >= 0, x_224 >= 0, z' = 1 + x_127 + x_227, x_227 >= 0 encode_h(z, z') -{ 11 + 14*x_129 + 14*x_229 }-> s177 :|: s174 >= 0, s174 <= 0, s175 >= 0, s175 <= 0, s176 >= 0, s176 <= s175, s177 >= 0, s177 <= s176, z >= 0, z' = 1 + x_129 + x_229, x_229 >= 0, x_129 >= 0 encode_h(z, z') -{ 19 + 14*x_124 + 14*x_128 + 14*x_224 + 14*x_228 }-> s23 :|: s17 >= 0, s17 <= 0, s18 >= 0, s18 <= 0, s19 >= 0, s19 <= s18, s20 >= 0, s20 <= 0, s21 >= 0, s21 <= 0, s22 >= 0, s22 <= s21, s23 >= 0, s23 <= s22, z = 1 + x_124 + x_224, x_124 >= 0, x_128 >= 0, z' = 1 + x_128 + x_228, x_224 >= 0, x_228 >= 0 encode_h(z, z') -{ 10 + 14*x_124 + 14*x_224 }-> s27 :|: s24 >= 0, s24 <= 0, s25 >= 0, s25 <= 0, s26 >= 0, s26 <= s25, s27 >= 0, s27 <= 0, z = 1 + x_124 + x_224, x_124 >= 0, x_224 >= 0, z' >= 0 encode_h(z, z') -{ 10 + 14*x_130 + 14*x_230 }-> s31 :|: s28 >= 0, s28 <= 0, s29 >= 0, s29 <= 0, s30 >= 0, s30 <= s29, s31 >= 0, s31 <= s30, z >= 0, x_130 >= 0, z' = 1 + x_130 + x_230, x_230 >= 0 encode_h(z, z') -{ 1 }-> x :|: z >= 0, z' >= 0, 0 = x, x >= 0 encode_h(z, z') -{ 0 }-> 0 :|: z >= 0, z' >= 0 encode_h(z, z') -{ 0 }-> 0 :|: z >= 0, z' >= 0, v0 >= 0, v1 >= 0, 0 = v0, 0 = v1 f(z, z') -{ 2 }-> z' :|: z >= 0, z' >= 0, z = z' f(z, z') -{ 1 }-> 0 :|: z >= 0, z' >= 0 h(z, z') -{ 1 }-> z' :|: z' >= 0, z = z' h(z, z') -{ 0 }-> 0 :|: z >= 0, z' >= 0 Function symbols to be analyzed: Previous analysis results are: h: runtime: O(1) [1], size: O(n^1) [z'] f: runtime: O(1) [2], size: O(n^1) [z'] encArg: runtime: O(n^1) [4 + 14*z], size: O(1) [0] encode_f: runtime: O(n^1) [8 + 14*z + 14*z'], size: O(1) [0] encode_h: runtime: O(n^1) [9 + 14*z + 14*z'], size: O(1) [0] ---------------------------------------- (51) FinalProof (FINISHED) Computed overall runtime complexity ---------------------------------------- (52) BOUNDS(1, n^1)