/export/starexec/sandbox2/solver/bin/starexec_run_rcdcRelativeAlsoLower /export/starexec/sandbox2/benchmark/theBenchmark.xml /export/starexec/sandbox2/output/output_files -------------------------------------------------------------------------------- WORST_CASE(Omega(n^1), O(n^3)) proof of /export/starexec/sandbox2/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(n^1, n^3). (0) DCpxTrs (1) DerivationalComplexityToRuntimeComplexityProof [BOTH BOUNDS(ID, ID), 0 ms] (2) CpxRelTRS (3) SInnermostTerminationProof [BOTH CONCRETE BOUNDS(ID, ID), 211 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) CpxTypedWeightedTrsToRntsProof [UPPER BOUND(ID), 7 ms] (12) CpxRNTS (13) CompleteCoflocoProof [FINISHED, 7388 ms] (14) BOUNDS(1, n^3) (15) RenamingProof [BOTH BOUNDS(ID, ID), 0 ms] (16) CpxRelTRS (17) TypeInferenceProof [BOTH BOUNDS(ID, ID), 0 ms] (18) typed CpxTrs (19) OrderProof [LOWER BOUND(ID), 0 ms] (20) typed CpxTrs (21) RewriteLemmaProof [LOWER BOUND(ID), 305 ms] (22) BEST (23) proven lower bound (24) LowerBoundPropagationProof [FINISHED, 0 ms] (25) BOUNDS(n^1, INF) (26) typed CpxTrs (27) RewriteLemmaProof [LOWER BOUND(ID), 13.3 s] (28) BOUNDS(1, INF) ---------------------------------------- (0) Obligation: The Derivational Complexity (innermost) of the given DCpxTrs could be proven to be BOUNDS(n^1, n^3). The TRS R consists of the following rules: minus(x, y) -> cond(min(x, y), x, y) cond(y, x, y) -> s(minus(x, s(y))) min(0, v) -> 0 min(u, 0) -> 0 min(s(u), s(v)) -> s(min(u, v)) S is empty. Rewrite Strategy: INNERMOST ---------------------------------------- (1) DerivationalComplexityToRuntimeComplexityProof (BOTH BOUNDS(ID, ID)) The following rules have been added to S to convert the given derivational complexity problem to a runtime complexity problem: encArg(s(x_1)) -> s(encArg(x_1)) encArg(0) -> 0 encArg(cons_minus(x_1, x_2)) -> minus(encArg(x_1), encArg(x_2)) encArg(cons_cond(x_1, x_2, x_3)) -> cond(encArg(x_1), encArg(x_2), encArg(x_3)) encArg(cons_min(x_1, x_2)) -> min(encArg(x_1), encArg(x_2)) encode_minus(x_1, x_2) -> minus(encArg(x_1), encArg(x_2)) encode_cond(x_1, x_2, x_3) -> cond(encArg(x_1), encArg(x_2), encArg(x_3)) encode_min(x_1, x_2) -> min(encArg(x_1), encArg(x_2)) encode_s(x_1) -> s(encArg(x_1)) encode_0 -> 0 ---------------------------------------- (2) Obligation: The Runtime Complexity (innermost) of the given CpxRelTRS could be proven to be BOUNDS(n^1, n^3). The TRS R consists of the following rules: minus(x, y) -> cond(min(x, y), x, y) cond(y, x, y) -> s(minus(x, s(y))) min(0, v) -> 0 min(u, 0) -> 0 min(s(u), s(v)) -> s(min(u, v)) The (relative) TRS S consists of the following rules: encArg(s(x_1)) -> s(encArg(x_1)) encArg(0) -> 0 encArg(cons_minus(x_1, x_2)) -> minus(encArg(x_1), encArg(x_2)) encArg(cons_cond(x_1, x_2, x_3)) -> cond(encArg(x_1), encArg(x_2), encArg(x_3)) encArg(cons_min(x_1, x_2)) -> min(encArg(x_1), encArg(x_2)) encode_minus(x_1, x_2) -> minus(encArg(x_1), encArg(x_2)) encode_cond(x_1, x_2, x_3) -> cond(encArg(x_1), encArg(x_2), encArg(x_3)) encode_min(x_1, x_2) -> min(encArg(x_1), encArg(x_2)) encode_s(x_1) -> s(encArg(x_1)) encode_0 -> 0 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(n^1, n^3). The TRS R consists of the following rules: minus(x, y) -> cond(min(x, y), x, y) cond(y, x, y) -> s(minus(x, s(y))) min(0, v) -> 0 min(u, 0) -> 0 min(s(u), s(v)) -> s(min(u, v)) The (relative) TRS S consists of the following rules: encArg(s(x_1)) -> s(encArg(x_1)) encArg(0) -> 0 encArg(cons_minus(x_1, x_2)) -> minus(encArg(x_1), encArg(x_2)) encArg(cons_cond(x_1, x_2, x_3)) -> cond(encArg(x_1), encArg(x_2), encArg(x_3)) encArg(cons_min(x_1, x_2)) -> min(encArg(x_1), encArg(x_2)) encode_minus(x_1, x_2) -> minus(encArg(x_1), encArg(x_2)) encode_cond(x_1, x_2, x_3) -> cond(encArg(x_1), encArg(x_2), encArg(x_3)) encode_min(x_1, x_2) -> min(encArg(x_1), encArg(x_2)) encode_s(x_1) -> s(encArg(x_1)) encode_0 -> 0 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^3). The TRS R consists of the following rules: minus(x, y) -> cond(min(x, y), x, y) [1] cond(y, x, y) -> s(minus(x, s(y))) [1] min(0, v) -> 0 [1] min(u, 0) -> 0 [1] min(s(u), s(v)) -> s(min(u, v)) [1] encArg(s(x_1)) -> s(encArg(x_1)) [0] encArg(0) -> 0 [0] encArg(cons_minus(x_1, x_2)) -> minus(encArg(x_1), encArg(x_2)) [0] encArg(cons_cond(x_1, x_2, x_3)) -> cond(encArg(x_1), encArg(x_2), encArg(x_3)) [0] encArg(cons_min(x_1, x_2)) -> min(encArg(x_1), encArg(x_2)) [0] encode_minus(x_1, x_2) -> minus(encArg(x_1), encArg(x_2)) [0] encode_cond(x_1, x_2, x_3) -> cond(encArg(x_1), encArg(x_2), encArg(x_3)) [0] encode_min(x_1, x_2) -> min(encArg(x_1), encArg(x_2)) [0] encode_s(x_1) -> s(encArg(x_1)) [0] encode_0 -> 0 [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: minus(x, y) -> cond(min(x, y), x, y) [1] cond(y, x, y) -> s(minus(x, s(y))) [1] min(0, v) -> 0 [1] min(u, 0) -> 0 [1] min(s(u), s(v)) -> s(min(u, v)) [1] encArg(s(x_1)) -> s(encArg(x_1)) [0] encArg(0) -> 0 [0] encArg(cons_minus(x_1, x_2)) -> minus(encArg(x_1), encArg(x_2)) [0] encArg(cons_cond(x_1, x_2, x_3)) -> cond(encArg(x_1), encArg(x_2), encArg(x_3)) [0] encArg(cons_min(x_1, x_2)) -> min(encArg(x_1), encArg(x_2)) [0] encode_minus(x_1, x_2) -> minus(encArg(x_1), encArg(x_2)) [0] encode_cond(x_1, x_2, x_3) -> cond(encArg(x_1), encArg(x_2), encArg(x_3)) [0] encode_min(x_1, x_2) -> min(encArg(x_1), encArg(x_2)) [0] encode_s(x_1) -> s(encArg(x_1)) [0] encode_0 -> 0 [0] The TRS has the following type information: minus :: s:0:cons_minus:cons_cond:cons_min -> s:0:cons_minus:cons_cond:cons_min -> s:0:cons_minus:cons_cond:cons_min cond :: s:0:cons_minus:cons_cond:cons_min -> s:0:cons_minus:cons_cond:cons_min -> s:0:cons_minus:cons_cond:cons_min -> s:0:cons_minus:cons_cond:cons_min min :: s:0:cons_minus:cons_cond:cons_min -> s:0:cons_minus:cons_cond:cons_min -> s:0:cons_minus:cons_cond:cons_min s :: s:0:cons_minus:cons_cond:cons_min -> s:0:cons_minus:cons_cond:cons_min 0 :: s:0:cons_minus:cons_cond:cons_min encArg :: s:0:cons_minus:cons_cond:cons_min -> s:0:cons_minus:cons_cond:cons_min cons_minus :: s:0:cons_minus:cons_cond:cons_min -> s:0:cons_minus:cons_cond:cons_min -> s:0:cons_minus:cons_cond:cons_min cons_cond :: s:0:cons_minus:cons_cond:cons_min -> s:0:cons_minus:cons_cond:cons_min -> s:0:cons_minus:cons_cond:cons_min -> s:0:cons_minus:cons_cond:cons_min cons_min :: s:0:cons_minus:cons_cond:cons_min -> s:0:cons_minus:cons_cond:cons_min -> s:0:cons_minus:cons_cond:cons_min encode_minus :: s:0:cons_minus:cons_cond:cons_min -> s:0:cons_minus:cons_cond:cons_min -> s:0:cons_minus:cons_cond:cons_min encode_cond :: s:0:cons_minus:cons_cond:cons_min -> s:0:cons_minus:cons_cond:cons_min -> s:0:cons_minus:cons_cond:cons_min -> s:0:cons_minus:cons_cond:cons_min encode_min :: s:0:cons_minus:cons_cond:cons_min -> s:0:cons_minus:cons_cond:cons_min -> s:0:cons_minus:cons_cond:cons_min encode_s :: s:0:cons_minus:cons_cond:cons_min -> s:0:cons_minus:cons_cond:cons_min encode_0 :: s:0:cons_minus:cons_cond:cons_min Rewrite Strategy: INNERMOST ---------------------------------------- (9) CompletionProof (UPPER BOUND(ID)) The TRS is a completely defined constructor system, as every type has a constant constructor and the following rules were added: encArg(v0) -> null_encArg [0] encode_minus(v0, v1) -> null_encode_minus [0] encode_cond(v0, v1, v2) -> null_encode_cond [0] encode_min(v0, v1) -> null_encode_min [0] encode_s(v0) -> null_encode_s [0] encode_0 -> null_encode_0 [0] cond(v0, v1, v2) -> null_cond [0] min(v0, v1) -> null_min [0] And the following fresh constants: null_encArg, null_encode_minus, null_encode_cond, null_encode_min, null_encode_s, null_encode_0, null_cond, null_min ---------------------------------------- (10) Obligation: Runtime Complexity Weighted TRS where all functions are completely defined. The underlying TRS is: Runtime Complexity Weighted TRS with Types. The TRS R consists of the following rules: minus(x, y) -> cond(min(x, y), x, y) [1] cond(y, x, y) -> s(minus(x, s(y))) [1] min(0, v) -> 0 [1] min(u, 0) -> 0 [1] min(s(u), s(v)) -> s(min(u, v)) [1] encArg(s(x_1)) -> s(encArg(x_1)) [0] encArg(0) -> 0 [0] encArg(cons_minus(x_1, x_2)) -> minus(encArg(x_1), encArg(x_2)) [0] encArg(cons_cond(x_1, x_2, x_3)) -> cond(encArg(x_1), encArg(x_2), encArg(x_3)) [0] encArg(cons_min(x_1, x_2)) -> min(encArg(x_1), encArg(x_2)) [0] encode_minus(x_1, x_2) -> minus(encArg(x_1), encArg(x_2)) [0] encode_cond(x_1, x_2, x_3) -> cond(encArg(x_1), encArg(x_2), encArg(x_3)) [0] encode_min(x_1, x_2) -> min(encArg(x_1), encArg(x_2)) [0] encode_s(x_1) -> s(encArg(x_1)) [0] encode_0 -> 0 [0] encArg(v0) -> null_encArg [0] encode_minus(v0, v1) -> null_encode_minus [0] encode_cond(v0, v1, v2) -> null_encode_cond [0] encode_min(v0, v1) -> null_encode_min [0] encode_s(v0) -> null_encode_s [0] encode_0 -> null_encode_0 [0] cond(v0, v1, v2) -> null_cond [0] min(v0, v1) -> null_min [0] The TRS has the following type information: minus :: s:0:cons_minus:cons_cond:cons_min:null_encArg:null_encode_minus:null_encode_cond:null_encode_min:null_encode_s:null_encode_0:null_cond:null_min -> s:0:cons_minus:cons_cond:cons_min:null_encArg:null_encode_minus:null_encode_cond:null_encode_min:null_encode_s:null_encode_0:null_cond:null_min -> s:0:cons_minus:cons_cond:cons_min:null_encArg:null_encode_minus:null_encode_cond:null_encode_min:null_encode_s:null_encode_0:null_cond:null_min cond :: s:0:cons_minus:cons_cond:cons_min:null_encArg:null_encode_minus:null_encode_cond:null_encode_min:null_encode_s:null_encode_0:null_cond:null_min -> s:0:cons_minus:cons_cond:cons_min:null_encArg:null_encode_minus:null_encode_cond:null_encode_min:null_encode_s:null_encode_0:null_cond:null_min -> s:0:cons_minus:cons_cond:cons_min:null_encArg:null_encode_minus:null_encode_cond:null_encode_min:null_encode_s:null_encode_0:null_cond:null_min -> s:0:cons_minus:cons_cond:cons_min:null_encArg:null_encode_minus:null_encode_cond:null_encode_min:null_encode_s:null_encode_0:null_cond:null_min min :: s:0:cons_minus:cons_cond:cons_min:null_encArg:null_encode_minus:null_encode_cond:null_encode_min:null_encode_s:null_encode_0:null_cond:null_min -> s:0:cons_minus:cons_cond:cons_min:null_encArg:null_encode_minus:null_encode_cond:null_encode_min:null_encode_s:null_encode_0:null_cond:null_min -> s:0:cons_minus:cons_cond:cons_min:null_encArg:null_encode_minus:null_encode_cond:null_encode_min:null_encode_s:null_encode_0:null_cond:null_min s :: s:0:cons_minus:cons_cond:cons_min:null_encArg:null_encode_minus:null_encode_cond:null_encode_min:null_encode_s:null_encode_0:null_cond:null_min -> s:0:cons_minus:cons_cond:cons_min:null_encArg:null_encode_minus:null_encode_cond:null_encode_min:null_encode_s:null_encode_0:null_cond:null_min 0 :: s:0:cons_minus:cons_cond:cons_min:null_encArg:null_encode_minus:null_encode_cond:null_encode_min:null_encode_s:null_encode_0:null_cond:null_min encArg :: s:0:cons_minus:cons_cond:cons_min:null_encArg:null_encode_minus:null_encode_cond:null_encode_min:null_encode_s:null_encode_0:null_cond:null_min -> s:0:cons_minus:cons_cond:cons_min:null_encArg:null_encode_minus:null_encode_cond:null_encode_min:null_encode_s:null_encode_0:null_cond:null_min cons_minus :: s:0:cons_minus:cons_cond:cons_min:null_encArg:null_encode_minus:null_encode_cond:null_encode_min:null_encode_s:null_encode_0:null_cond:null_min -> s:0:cons_minus:cons_cond:cons_min:null_encArg:null_encode_minus:null_encode_cond:null_encode_min:null_encode_s:null_encode_0:null_cond:null_min -> s:0:cons_minus:cons_cond:cons_min:null_encArg:null_encode_minus:null_encode_cond:null_encode_min:null_encode_s:null_encode_0:null_cond:null_min cons_cond :: s:0:cons_minus:cons_cond:cons_min:null_encArg:null_encode_minus:null_encode_cond:null_encode_min:null_encode_s:null_encode_0:null_cond:null_min -> s:0:cons_minus:cons_cond:cons_min:null_encArg:null_encode_minus:null_encode_cond:null_encode_min:null_encode_s:null_encode_0:null_cond:null_min -> s:0:cons_minus:cons_cond:cons_min:null_encArg:null_encode_minus:null_encode_cond:null_encode_min:null_encode_s:null_encode_0:null_cond:null_min -> s:0:cons_minus:cons_cond:cons_min:null_encArg:null_encode_minus:null_encode_cond:null_encode_min:null_encode_s:null_encode_0:null_cond:null_min cons_min :: s:0:cons_minus:cons_cond:cons_min:null_encArg:null_encode_minus:null_encode_cond:null_encode_min:null_encode_s:null_encode_0:null_cond:null_min -> s:0:cons_minus:cons_cond:cons_min:null_encArg:null_encode_minus:null_encode_cond:null_encode_min:null_encode_s:null_encode_0:null_cond:null_min -> s:0:cons_minus:cons_cond:cons_min:null_encArg:null_encode_minus:null_encode_cond:null_encode_min:null_encode_s:null_encode_0:null_cond:null_min encode_minus :: s:0:cons_minus:cons_cond:cons_min:null_encArg:null_encode_minus:null_encode_cond:null_encode_min:null_encode_s:null_encode_0:null_cond:null_min -> s:0:cons_minus:cons_cond:cons_min:null_encArg:null_encode_minus:null_encode_cond:null_encode_min:null_encode_s:null_encode_0:null_cond:null_min -> s:0:cons_minus:cons_cond:cons_min:null_encArg:null_encode_minus:null_encode_cond:null_encode_min:null_encode_s:null_encode_0:null_cond:null_min encode_cond :: s:0:cons_minus:cons_cond:cons_min:null_encArg:null_encode_minus:null_encode_cond:null_encode_min:null_encode_s:null_encode_0:null_cond:null_min -> s:0:cons_minus:cons_cond:cons_min:null_encArg:null_encode_minus:null_encode_cond:null_encode_min:null_encode_s:null_encode_0:null_cond:null_min -> s:0:cons_minus:cons_cond:cons_min:null_encArg:null_encode_minus:null_encode_cond:null_encode_min:null_encode_s:null_encode_0:null_cond:null_min -> s:0:cons_minus:cons_cond:cons_min:null_encArg:null_encode_minus:null_encode_cond:null_encode_min:null_encode_s:null_encode_0:null_cond:null_min encode_min :: s:0:cons_minus:cons_cond:cons_min:null_encArg:null_encode_minus:null_encode_cond:null_encode_min:null_encode_s:null_encode_0:null_cond:null_min -> s:0:cons_minus:cons_cond:cons_min:null_encArg:null_encode_minus:null_encode_cond:null_encode_min:null_encode_s:null_encode_0:null_cond:null_min -> s:0:cons_minus:cons_cond:cons_min:null_encArg:null_encode_minus:null_encode_cond:null_encode_min:null_encode_s:null_encode_0:null_cond:null_min encode_s :: s:0:cons_minus:cons_cond:cons_min:null_encArg:null_encode_minus:null_encode_cond:null_encode_min:null_encode_s:null_encode_0:null_cond:null_min -> s:0:cons_minus:cons_cond:cons_min:null_encArg:null_encode_minus:null_encode_cond:null_encode_min:null_encode_s:null_encode_0:null_cond:null_min encode_0 :: s:0:cons_minus:cons_cond:cons_min:null_encArg:null_encode_minus:null_encode_cond:null_encode_min:null_encode_s:null_encode_0:null_cond:null_min null_encArg :: s:0:cons_minus:cons_cond:cons_min:null_encArg:null_encode_minus:null_encode_cond:null_encode_min:null_encode_s:null_encode_0:null_cond:null_min null_encode_minus :: s:0:cons_minus:cons_cond:cons_min:null_encArg:null_encode_minus:null_encode_cond:null_encode_min:null_encode_s:null_encode_0:null_cond:null_min null_encode_cond :: s:0:cons_minus:cons_cond:cons_min:null_encArg:null_encode_minus:null_encode_cond:null_encode_min:null_encode_s:null_encode_0:null_cond:null_min null_encode_min :: s:0:cons_minus:cons_cond:cons_min:null_encArg:null_encode_minus:null_encode_cond:null_encode_min:null_encode_s:null_encode_0:null_cond:null_min null_encode_s :: s:0:cons_minus:cons_cond:cons_min:null_encArg:null_encode_minus:null_encode_cond:null_encode_min:null_encode_s:null_encode_0:null_cond:null_min null_encode_0 :: s:0:cons_minus:cons_cond:cons_min:null_encArg:null_encode_minus:null_encode_cond:null_encode_min:null_encode_s:null_encode_0:null_cond:null_min null_cond :: s:0:cons_minus:cons_cond:cons_min:null_encArg:null_encode_minus:null_encode_cond:null_encode_min:null_encode_s:null_encode_0:null_cond:null_min null_min :: s:0:cons_minus:cons_cond:cons_min:null_encArg:null_encode_minus:null_encode_cond:null_encode_min:null_encode_s:null_encode_0:null_cond:null_min Rewrite Strategy: INNERMOST ---------------------------------------- (11) CpxTypedWeightedTrsToRntsProof (UPPER BOUND(ID)) Transformed the TRS into an over-approximating RNTS by (improved) Size Abstraction. The constant constructors are abstracted as follows: 0 => 0 null_encArg => 0 null_encode_minus => 0 null_encode_cond => 0 null_encode_min => 0 null_encode_s => 0 null_encode_0 => 0 null_cond => 0 null_min => 0 ---------------------------------------- (12) Obligation: Complexity RNTS consisting of the following rules: cond(z, z', z'') -{ 0 }-> 0 :|: v0 >= 0, z'' = v2, v1 >= 0, z = v0, z' = v1, v2 >= 0 cond(z, z', z'') -{ 1 }-> 1 + minus(x, 1 + y) :|: z' = x, z'' = y, y >= 0, x >= 0, z = y encArg(z) -{ 0 }-> minus(encArg(x_1), encArg(x_2)) :|: x_1 >= 0, z = 1 + x_1 + x_2, x_2 >= 0 encArg(z) -{ 0 }-> min(encArg(x_1), encArg(x_2)) :|: x_1 >= 0, z = 1 + x_1 + x_2, x_2 >= 0 encArg(z) -{ 0 }-> cond(encArg(x_1), encArg(x_2), encArg(x_3)) :|: x_1 >= 0, z = 1 + x_1 + x_2 + x_3, x_3 >= 0, x_2 >= 0 encArg(z) -{ 0 }-> 0 :|: z = 0 encArg(z) -{ 0 }-> 0 :|: v0 >= 0, z = v0 encArg(z) -{ 0 }-> 1 + encArg(x_1) :|: z = 1 + x_1, x_1 >= 0 encode_0 -{ 0 }-> 0 :|: encode_cond(z, z', z'') -{ 0 }-> cond(encArg(x_1), encArg(x_2), encArg(x_3)) :|: x_1 >= 0, x_3 >= 0, x_2 >= 0, z = x_1, z' = x_2, z'' = x_3 encode_cond(z, z', z'') -{ 0 }-> 0 :|: v0 >= 0, z'' = v2, v1 >= 0, z = v0, z' = v1, v2 >= 0 encode_min(z, z') -{ 0 }-> min(encArg(x_1), encArg(x_2)) :|: x_1 >= 0, x_2 >= 0, z = x_1, z' = x_2 encode_min(z, z') -{ 0 }-> 0 :|: v0 >= 0, v1 >= 0, z = v0, z' = v1 encode_minus(z, z') -{ 0 }-> minus(encArg(x_1), encArg(x_2)) :|: x_1 >= 0, x_2 >= 0, z = x_1, z' = x_2 encode_minus(z, z') -{ 0 }-> 0 :|: v0 >= 0, v1 >= 0, z = v0, z' = v1 encode_s(z) -{ 0 }-> 0 :|: v0 >= 0, z = v0 encode_s(z) -{ 0 }-> 1 + encArg(x_1) :|: x_1 >= 0, z = x_1 min(z, z') -{ 1 }-> 0 :|: v >= 0, z' = v, z = 0 min(z, z') -{ 1 }-> 0 :|: z = u, z' = 0, u >= 0 min(z, z') -{ 0 }-> 0 :|: v0 >= 0, v1 >= 0, z = v0, z' = v1 min(z, z') -{ 1 }-> 1 + min(u, v) :|: v >= 0, z' = 1 + v, z = 1 + u, u >= 0 minus(z, z') -{ 1 }-> cond(min(x, y), x, y) :|: x >= 0, y >= 0, z = x, z' = y Only complete derivations are relevant for the runtime complexity. ---------------------------------------- (13) CompleteCoflocoProof (FINISHED) Transformed the RNTS (where only complete derivations are relevant) into cost relations for CoFloCo: eq(start(V1, V, V5),0,[minus(V1, V, Out)],[V1 >= 0,V >= 0]). eq(start(V1, V, V5),0,[cond(V1, V, V5, Out)],[V1 >= 0,V >= 0,V5 >= 0]). eq(start(V1, V, V5),0,[min(V1, V, Out)],[V1 >= 0,V >= 0]). eq(start(V1, V, V5),0,[encArg(V1, Out)],[V1 >= 0]). eq(start(V1, V, V5),0,[fun(V1, V, Out)],[V1 >= 0,V >= 0]). eq(start(V1, V, V5),0,[fun1(V1, V, V5, Out)],[V1 >= 0,V >= 0,V5 >= 0]). eq(start(V1, V, V5),0,[fun2(V1, V, Out)],[V1 >= 0,V >= 0]). eq(start(V1, V, V5),0,[fun3(V1, Out)],[V1 >= 0]). eq(start(V1, V, V5),0,[fun4(Out)],[]). eq(minus(V1, V, Out),1,[min(V3, V2, Ret0),cond(Ret0, V3, V2, Ret)],[Out = Ret,V3 >= 0,V2 >= 0,V1 = V3,V = V2]). eq(cond(V1, V, V5, Out),1,[minus(V4, 1 + V6, Ret1)],[Out = 1 + Ret1,V = V4,V5 = V6,V6 >= 0,V4 >= 0,V1 = V6]). eq(min(V1, V, Out),1,[],[Out = 0,V7 >= 0,V = V7,V1 = 0]). eq(min(V1, V, Out),1,[],[Out = 0,V1 = V8,V = 0,V8 >= 0]). eq(min(V1, V, Out),1,[min(V9, V10, Ret11)],[Out = 1 + Ret11,V10 >= 0,V = 1 + V10,V1 = 1 + V9,V9 >= 0]). eq(encArg(V1, Out),0,[encArg(V11, Ret12)],[Out = 1 + Ret12,V1 = 1 + V11,V11 >= 0]). eq(encArg(V1, Out),0,[],[Out = 0,V1 = 0]). eq(encArg(V1, Out),0,[encArg(V12, Ret01),encArg(V13, Ret13),minus(Ret01, Ret13, Ret2)],[Out = Ret2,V12 >= 0,V1 = 1 + V12 + V13,V13 >= 0]). eq(encArg(V1, Out),0,[encArg(V15, Ret02),encArg(V16, Ret14),encArg(V14, Ret21),cond(Ret02, Ret14, Ret21, Ret3)],[Out = Ret3,V15 >= 0,V1 = 1 + V14 + V15 + V16,V14 >= 0,V16 >= 0]). eq(encArg(V1, Out),0,[encArg(V18, Ret03),encArg(V17, Ret15),min(Ret03, Ret15, Ret4)],[Out = Ret4,V18 >= 0,V1 = 1 + V17 + V18,V17 >= 0]). eq(fun(V1, V, Out),0,[encArg(V20, Ret04),encArg(V19, Ret16),minus(Ret04, Ret16, Ret5)],[Out = Ret5,V20 >= 0,V19 >= 0,V1 = V20,V = V19]). eq(fun1(V1, V, V5, Out),0,[encArg(V22, Ret05),encArg(V23, Ret17),encArg(V21, Ret22),cond(Ret05, Ret17, Ret22, Ret6)],[Out = Ret6,V22 >= 0,V21 >= 0,V23 >= 0,V1 = V22,V = V23,V5 = V21]). eq(fun2(V1, V, Out),0,[encArg(V24, Ret06),encArg(V25, Ret18),min(Ret06, Ret18, Ret7)],[Out = Ret7,V24 >= 0,V25 >= 0,V1 = V24,V = V25]). eq(fun3(V1, Out),0,[encArg(V26, Ret19)],[Out = 1 + Ret19,V26 >= 0,V1 = V26]). eq(fun4(Out),0,[],[Out = 0]). eq(encArg(V1, Out),0,[],[Out = 0,V27 >= 0,V1 = V27]). eq(fun(V1, V, Out),0,[],[Out = 0,V29 >= 0,V28 >= 0,V1 = V29,V = V28]). eq(fun1(V1, V, V5, Out),0,[],[Out = 0,V31 >= 0,V5 = V32,V30 >= 0,V1 = V31,V = V30,V32 >= 0]). eq(fun2(V1, V, Out),0,[],[Out = 0,V33 >= 0,V34 >= 0,V1 = V33,V = V34]). eq(fun3(V1, Out),0,[],[Out = 0,V35 >= 0,V1 = V35]). eq(cond(V1, V, V5, Out),0,[],[Out = 0,V36 >= 0,V5 = V37,V38 >= 0,V1 = V36,V = V38,V37 >= 0]). eq(min(V1, V, Out),0,[],[Out = 0,V40 >= 0,V39 >= 0,V1 = V40,V = V39]). input_output_vars(minus(V1,V,Out),[V1,V],[Out]). input_output_vars(cond(V1,V,V5,Out),[V1,V,V5],[Out]). input_output_vars(min(V1,V,Out),[V1,V],[Out]). input_output_vars(encArg(V1,Out),[V1],[Out]). input_output_vars(fun(V1,V,Out),[V1,V],[Out]). input_output_vars(fun1(V1,V,V5,Out),[V1,V,V5],[Out]). input_output_vars(fun2(V1,V,Out),[V1,V],[Out]). input_output_vars(fun3(V1,Out),[V1],[Out]). input_output_vars(fun4(Out),[],[Out]). CoFloCo proof output: Preprocessing Cost Relations ===================================== #### Computed strongly connected components 0. recursive : [min/3] 1. recursive : [cond/4,minus/3] 2. recursive [non_tail,multiple] : [encArg/2] 3. non_recursive : [fun/3] 4. non_recursive : [fun1/4] 5. non_recursive : [fun2/3] 6. non_recursive : [fun3/2] 7. non_recursive : [fun4/1] 8. non_recursive : [start/3] #### Obtained direct recursion through partial evaluation 0. SCC is partially evaluated into min/3 1. SCC is partially evaluated into minus/3 2. SCC is partially evaluated into encArg/2 3. SCC is partially evaluated into fun/3 4. SCC is partially evaluated into fun1/4 5. SCC is partially evaluated into fun2/3 6. SCC is partially evaluated into fun3/2 7. SCC is completely evaluated into other SCCs 8. SCC is partially evaluated into start/3 Control-Flow Refinement of Cost Relations ===================================== ### Specialization of cost equations min/3 * CE 13 is refined into CE [31] * CE 12 is refined into CE [32] * CE 15 is refined into CE [33] * CE 14 is refined into CE [34] ### Cost equations --> "Loop" of min/3 * CEs [34] --> Loop 16 * CEs [31] --> Loop 17 * CEs [32,33] --> Loop 18 ### Ranking functions of CR min(V1,V,Out) * RF of phase [16]: [V,V1] #### Partial ranking functions of CR min(V1,V,Out) * Partial RF of phase [16]: - RF of loop [16:1]: V V1 ### Specialization of cost equations minus/3 * CE 11 is refined into CE [35,36] * CE 10 is refined into CE [37,38] ### Cost equations --> "Loop" of minus/3 * CEs [37,38] --> Loop 19 * CEs [36] --> Loop 20 * CEs [35] --> Loop 21 ### Ranking functions of CR minus(V1,V,Out) * RF of phase [20]: [V1-V+1] #### Partial ranking functions of CR minus(V1,V,Out) * Partial RF of phase [20]: - RF of loop [20:1]: V1-V+1 ### Specialization of cost equations encArg/2 * CE 19 is refined into CE [39] * CE 20 is refined into CE [40,41,42,43] * CE 21 is refined into CE [44,45] * CE 18 is refined into CE [46] * CE 17 is refined into CE [47,48] * CE 16 is refined into CE [49] ### Cost equations --> "Loop" of encArg/2 * CEs [48] --> Loop 22 * CEs [47] --> Loop 23 * CEs [49] --> Loop 24 * CEs [46] --> Loop 25 * CEs [45] --> Loop 26 * CEs [43] --> Loop 27 * CEs [41] --> Loop 28 * CEs [40] --> Loop 29 * CEs [42,44] --> Loop 30 * CEs [39] --> Loop 31 ### Ranking functions of CR encArg(V1,Out) * RF of phase [22,23,24,25,26,27,28,29,30]: [V1] #### Partial ranking functions of CR encArg(V1,Out) * Partial RF of phase [22,23,24,25,26,27,28,29,30]: - RF of loop [22:1,22:2,22:3,23:1,23:2,23:3,24:1,24:2,24:3,25:1,26:1,26:2,27:1,27:2,28:1,28:2,29:1,29:2,30:1,30:2]: V1 ### Specialization of cost equations fun/3 * CE 22 is refined into CE [50,51,52,53,54,55,56,57,58,59,60] * CE 23 is refined into CE [61] ### Cost equations --> "Loop" of fun/3 * CEs [60] --> Loop 32 * CEs [55,58] --> Loop 33 * CEs [50,52,54,57] --> Loop 34 * CEs [51,53,56,59,61] --> Loop 35 ### Ranking functions of CR fun(V1,V,Out) #### Partial ranking functions of CR fun(V1,V,Out) ### Specialization of cost equations fun1/4 * CE 24 is refined into CE [62,63,64,65,66,67,68,69] * CE 25 is refined into CE [70,71,72,73,74,75,76,77,78,79,80,81] * CE 26 is refined into CE [82] ### Cost equations --> "Loop" of fun1/4 * CEs [73,75,79,81] --> Loop 36 * CEs [70,71,72,74,76,77,78,80] --> Loop 37 * CEs [62,63,64,65,66,67,68,69,82] --> Loop 38 ### Ranking functions of CR fun1(V1,V,V5,Out) #### Partial ranking functions of CR fun1(V1,V,V5,Out) ### Specialization of cost equations fun2/3 * CE 27 is refined into CE [83,84,85,86,87] * CE 28 is refined into CE [88] ### Cost equations --> "Loop" of fun2/3 * CEs [87] --> Loop 39 * CEs [83,84,85,86,88] --> Loop 40 ### Ranking functions of CR fun2(V1,V,Out) #### Partial ranking functions of CR fun2(V1,V,Out) ### Specialization of cost equations fun3/2 * CE 29 is refined into CE [89,90] * CE 30 is refined into CE [91] ### Cost equations --> "Loop" of fun3/2 * CEs [90] --> Loop 41 * CEs [89] --> Loop 42 * CEs [91] --> Loop 43 ### Ranking functions of CR fun3(V1,Out) #### Partial ranking functions of CR fun3(V1,Out) ### Specialization of cost equations start/3 * CE 1 is refined into CE [92] * CE 2 is refined into CE [93,94] * CE 3 is refined into CE [95,96,97,98] * CE 4 is refined into CE [99,100] * CE 5 is refined into CE [101,102] * CE 6 is refined into CE [103,104,105,106] * CE 7 is refined into CE [107,108,109] * CE 8 is refined into CE [110,111] * CE 9 is refined into CE [112,113,114] ### Cost equations --> "Loop" of start/3 * CEs [92,93,94,95,96,97,98,99,100,101,102,103,104,105,106,107,108,109,110,111,112,113,114] --> Loop 44 ### Ranking functions of CR start(V1,V,V5) #### Partial ranking functions of CR start(V1,V,V5) Computing Bounds ===================================== #### Cost of chains of min(V1,V,Out): * Chain [[16],18]: 1*it(16)+1 Such that:it(16) =< Out with precondition: [Out>=1,V1>=Out,V>=Out] * Chain [[16],17]: 1*it(16)+1 Such that:it(16) =< Out with precondition: [V=Out,V>=1,V1>=V] * Chain [18]: 1 with precondition: [Out=0,V1>=0,V>=0] * Chain [17]: 1 with precondition: [V=0,Out=0,V1>=0] #### Cost of chains of minus(V1,V,Out): * Chain [[20],19]: 3*it(20)+2*s(4)+2*s(9)+2 Such that:aux(2) =< V1+1 s(3) =< V+Out it(20) =< Out s(4) =< s(3) s(10) =< it(20)*aux(2) s(9) =< s(10) with precondition: [V>=1,Out>=1,V1+1>=Out+V] * Chain [21,[20],19]: 5*it(20)+2*s(9)+5 Such that:aux(2) =< V1+1 aux(3) =< Out it(20) =< aux(3) s(10) =< it(20)*aux(2) s(9) =< s(10) with precondition: [V=0,Out>=2,V1+1>=Out] * Chain [21,19]: 2*s(4)+5 Such that:s(3) =< 1 s(4) =< s(3) with precondition: [V=0,Out=1,V1>=0] * Chain [19]: 2*s(4)+2 Such that:s(3) =< V s(4) =< s(3) with precondition: [Out=0,V1>=0,V>=0] #### Cost of chains of encArg(V1,Out): * Chain [31]: 0 with precondition: [Out=0,V1>=0] * Chain [multiple([22,23,24,25,26,27,28,29,30],[[31]])]: 3*it(22)+3*it(23)+3*it(26)+5*it(28)+7*it(29)+5*s(56)+2*s(57)+2*s(60)+2*s(62)+5*s(64)+2*s(65)+5*s(68)+2*s(69)+2*s(72)+2*s(74)+0 Such that:it([31]) =< 2*V1+1 aux(18) =< V1 aux(19) =< V1/2 aux(20) =< 2/3*V1 aux(21) =< 3/5*V1 it(23) =< aux(18) it(26) =< aux(18) it(28) =< aux(18) it(29) =< aux(18) it(26) =< aux(19) it(28) =< aux(20) it(22) =< aux(21) aux(13) =< aux(18) aux(8) =< aux(18)+1 aux(11) =< aux(18)-1 it(28) =< it([31])*(1/3)+aux(20) it(29) =< it([31])*(1/3)+aux(20) it(26) =< it([31])*(1/2)+aux(19) it(28) =< it([31])*(1/2)+aux(19) it(29) =< it([31])*(1/2)+aux(19) it(22) =< it([31])*(1/5)+aux(21) it(23) =< it([31])*(1/5)+aux(21) s(75) =< it(29)*aux(13) s(71) =< it(28)*aux(8) s(67) =< it(26)*aux(13) s(63) =< it(26)*aux(11) s(61) =< it(23)*aux(8) s(59) =< it(22)*aux(8) s(74) =< s(75) s(72) =< aux(18) s(68) =< s(71) s(70) =< s(68)*aux(8) s(69) =< s(70) s(64) =< s(67) s(66) =< s(64)*aux(18) s(65) =< s(66) s(62) =< s(63) s(60) =< s(61) s(56) =< s(59) s(58) =< s(56)*aux(8) s(57) =< s(58) with precondition: [V1>=1,Out>=0,V1>=Out] #### Cost of chains of fun(V1,V,Out): * Chain [35]: 6*s(83)+6*s(84)+10*s(85)+14*s(86)+6*s(87)+4*s(97)+8*s(98)+10*s(99)+4*s(101)+10*s(102)+4*s(104)+4*s(105)+4*s(106)+10*s(107)+4*s(109)+6*s(117)+6*s(118)+10*s(119)+14*s(120)+6*s(121)+4*s(131)+4*s(132)+10*s(133)+4*s(135)+10*s(136)+4*s(138)+4*s(139)+4*s(140)+10*s(141)+4*s(143)+2 Such that:aux(24) =< V1 aux(25) =< 2*V1+1 aux(26) =< V1/2 aux(27) =< 2/3*V1 aux(28) =< 3/5*V1 aux(29) =< V aux(30) =< 2*V+1 aux(31) =< V/2 aux(32) =< 2/3*V aux(33) =< 3/5*V s(117) =< aux(24) s(118) =< aux(24) s(119) =< aux(24) s(120) =< aux(24) s(118) =< aux(26) s(119) =< aux(27) s(121) =< aux(28) s(122) =< aux(24) s(123) =< aux(24)+1 s(124) =< aux(24)-1 s(119) =< aux(25)*(1/3)+aux(27) s(120) =< aux(25)*(1/3)+aux(27) s(118) =< aux(25)*(1/2)+aux(26) s(119) =< aux(25)*(1/2)+aux(26) s(120) =< aux(25)*(1/2)+aux(26) s(121) =< aux(25)*(1/5)+aux(28) s(117) =< aux(25)*(1/5)+aux(28) s(125) =< s(120)*s(122) s(126) =< s(119)*s(123) s(127) =< s(118)*s(122) s(128) =< s(118)*s(124) s(129) =< s(117)*s(123) s(130) =< s(121)*s(123) s(131) =< s(125) s(132) =< aux(24) s(133) =< s(126) s(134) =< s(133)*s(123) s(135) =< s(134) s(136) =< s(127) s(137) =< s(136)*aux(24) s(138) =< s(137) s(139) =< s(128) s(140) =< s(129) s(141) =< s(130) s(142) =< s(141)*s(123) s(143) =< s(142) s(98) =< aux(29) s(83) =< aux(29) s(84) =< aux(29) s(85) =< aux(29) s(86) =< aux(29) s(84) =< aux(31) s(85) =< aux(32) s(87) =< aux(33) s(88) =< aux(29) s(89) =< aux(29)+1 s(90) =< aux(29)-1 s(85) =< aux(30)*(1/3)+aux(32) s(86) =< aux(30)*(1/3)+aux(32) s(84) =< aux(30)*(1/2)+aux(31) s(85) =< aux(30)*(1/2)+aux(31) s(86) =< aux(30)*(1/2)+aux(31) s(87) =< aux(30)*(1/5)+aux(33) s(83) =< aux(30)*(1/5)+aux(33) s(91) =< s(86)*s(88) s(92) =< s(85)*s(89) s(93) =< s(84)*s(88) s(94) =< s(84)*s(90) s(95) =< s(83)*s(89) s(96) =< s(87)*s(89) s(97) =< s(91) s(99) =< s(92) s(100) =< s(99)*s(89) s(101) =< s(100) s(102) =< s(93) s(103) =< s(102)*aux(29) s(104) =< s(103) s(105) =< s(94) s(106) =< s(95) s(107) =< s(96) s(108) =< s(107)*s(89) s(109) =< s(108) with precondition: [Out=0,V1>=0,V>=0] * Chain [34]: 8*s(213)+6*s(219)+6*s(220)+10*s(221)+14*s(222)+6*s(223)+4*s(233)+4*s(234)+10*s(235)+4*s(237)+10*s(238)+4*s(240)+4*s(241)+4*s(242)+10*s(243)+4*s(245)+6*s(253)+6*s(254)+10*s(255)+14*s(256)+6*s(257)+4*s(267)+4*s(268)+10*s(269)+4*s(271)+10*s(272)+4*s(274)+4*s(275)+4*s(276)+10*s(277)+4*s(279)+5 Such that:aux(34) =< 1 aux(35) =< V1 aux(36) =< 2*V1+1 aux(37) =< V1/2 aux(38) =< 2/3*V1 aux(39) =< 3/5*V1 aux(40) =< V aux(41) =< 2*V+1 aux(42) =< V/2 aux(43) =< 2/3*V aux(44) =< 3/5*V s(213) =< aux(34) s(219) =< aux(40) s(220) =< aux(40) s(221) =< aux(40) s(222) =< aux(40) s(220) =< aux(42) s(221) =< aux(43) s(223) =< aux(44) s(224) =< aux(40) s(225) =< aux(40)+1 s(226) =< aux(40)-1 s(221) =< aux(41)*(1/3)+aux(43) s(222) =< aux(41)*(1/3)+aux(43) s(220) =< aux(41)*(1/2)+aux(42) s(221) =< aux(41)*(1/2)+aux(42) s(222) =< aux(41)*(1/2)+aux(42) s(223) =< aux(41)*(1/5)+aux(44) s(219) =< aux(41)*(1/5)+aux(44) s(227) =< s(222)*s(224) s(228) =< s(221)*s(225) s(229) =< s(220)*s(224) s(230) =< s(220)*s(226) s(231) =< s(219)*s(225) s(232) =< s(223)*s(225) s(233) =< s(227) s(234) =< aux(40) s(235) =< s(228) s(236) =< s(235)*s(225) s(237) =< s(236) s(238) =< s(229) s(239) =< s(238)*aux(40) s(240) =< s(239) s(241) =< s(230) s(242) =< s(231) s(243) =< s(232) s(244) =< s(243)*s(225) s(245) =< s(244) s(253) =< aux(35) s(254) =< aux(35) s(255) =< aux(35) s(256) =< aux(35) s(254) =< aux(37) s(255) =< aux(38) s(257) =< aux(39) s(258) =< aux(35) s(259) =< aux(35)+1 s(260) =< aux(35)-1 s(255) =< aux(36)*(1/3)+aux(38) s(256) =< aux(36)*(1/3)+aux(38) s(254) =< aux(36)*(1/2)+aux(37) s(255) =< aux(36)*(1/2)+aux(37) s(256) =< aux(36)*(1/2)+aux(37) s(257) =< aux(36)*(1/5)+aux(39) s(253) =< aux(36)*(1/5)+aux(39) s(261) =< s(256)*s(258) s(262) =< s(255)*s(259) s(263) =< s(254)*s(258) s(264) =< s(254)*s(260) s(265) =< s(253)*s(259) s(266) =< s(257)*s(259) s(267) =< s(261) s(268) =< aux(35) s(269) =< s(262) s(270) =< s(269)*s(259) s(271) =< s(270) s(272) =< s(263) s(273) =< s(272)*aux(35) s(274) =< s(273) s(275) =< s(264) s(276) =< s(265) s(277) =< s(266) s(278) =< s(277)*s(259) s(279) =< s(278) with precondition: [Out=1,V1>=0,V>=0] * Chain [33]: 6*s(353)+6*s(354)+10*s(355)+14*s(356)+6*s(357)+4*s(367)+4*s(368)+10*s(369)+4*s(371)+10*s(372)+4*s(374)+4*s(375)+4*s(376)+10*s(377)+4*s(379)+10*s(382)+4*s(384)+3*s(422)+3*s(423)+5*s(424)+7*s(425)+3*s(426)+2*s(436)+2*s(437)+5*s(438)+2*s(440)+5*s(441)+2*s(443)+2*s(444)+2*s(445)+5*s(446)+2*s(448)+5 Such that:s(418) =< V s(417) =< 2*V+1 s(419) =< V/2 s(420) =< 2/3*V s(421) =< 3/5*V aux(47) =< V1 aux(48) =< V1+1 aux(49) =< 2*V1+1 aux(50) =< V1/2 aux(51) =< 2/3*V1 aux(52) =< 3/5*V1 s(382) =< aux(48) s(383) =< s(382)*aux(48) s(384) =< s(383) s(353) =< aux(47) s(354) =< aux(47) s(355) =< aux(47) s(356) =< aux(47) s(354) =< aux(50) s(355) =< aux(51) s(357) =< aux(52) s(358) =< aux(47) s(359) =< aux(47)+1 s(360) =< aux(47)-1 s(355) =< aux(49)*(1/3)+aux(51) s(356) =< aux(49)*(1/3)+aux(51) s(354) =< aux(49)*(1/2)+aux(50) s(355) =< aux(49)*(1/2)+aux(50) s(356) =< aux(49)*(1/2)+aux(50) s(357) =< aux(49)*(1/5)+aux(52) s(353) =< aux(49)*(1/5)+aux(52) s(361) =< s(356)*s(358) s(362) =< s(355)*s(359) s(363) =< s(354)*s(358) s(364) =< s(354)*s(360) s(365) =< s(353)*s(359) s(366) =< s(357)*s(359) s(367) =< s(361) s(368) =< aux(47) s(369) =< s(362) s(370) =< s(369)*s(359) s(371) =< s(370) s(372) =< s(363) s(373) =< s(372)*aux(47) s(374) =< s(373) s(375) =< s(364) s(376) =< s(365) s(377) =< s(366) s(378) =< s(377)*s(359) s(379) =< s(378) s(422) =< s(418) s(423) =< s(418) s(424) =< s(418) s(425) =< s(418) s(423) =< s(419) s(424) =< s(420) s(426) =< s(421) s(427) =< s(418) s(428) =< s(418)+1 s(429) =< s(418)-1 s(424) =< s(417)*(1/3)+s(420) s(425) =< s(417)*(1/3)+s(420) s(423) =< s(417)*(1/2)+s(419) s(424) =< s(417)*(1/2)+s(419) s(425) =< s(417)*(1/2)+s(419) s(426) =< s(417)*(1/5)+s(421) s(422) =< s(417)*(1/5)+s(421) s(430) =< s(425)*s(427) s(431) =< s(424)*s(428) s(432) =< s(423)*s(427) s(433) =< s(423)*s(429) s(434) =< s(422)*s(428) s(435) =< s(426)*s(428) s(436) =< s(430) s(437) =< s(418) s(438) =< s(431) s(439) =< s(438)*s(428) s(440) =< s(439) s(441) =< s(432) s(442) =< s(441)*s(418) s(443) =< s(442) s(444) =< s(433) s(445) =< s(434) s(446) =< s(435) s(447) =< s(446)*s(428) s(448) =< s(447) with precondition: [V>=0,Out>=2,V1+1>=Out] * Chain [32]: 3*s(459)+3*s(460)+5*s(461)+7*s(462)+3*s(463)+2*s(473)+5*s(474)+5*s(475)+2*s(477)+5*s(478)+2*s(480)+2*s(481)+2*s(482)+5*s(483)+2*s(485)+3*s(491)+3*s(492)+5*s(493)+7*s(494)+3*s(495)+2*s(505)+2*s(506)+5*s(507)+2*s(509)+5*s(510)+2*s(512)+2*s(513)+2*s(514)+5*s(515)+2*s(517)+2*s(521)+2*s(523)+2 Such that:s(454) =< 2*V1+1 s(456) =< V1/2 s(457) =< 2/3*V1 s(458) =< 3/5*V1 s(487) =< V s(486) =< 2*V+1 s(488) =< V/2 s(489) =< 2/3*V s(490) =< 3/5*V aux(53) =< V1 aux(54) =< V1+1 s(474) =< aux(53) s(521) =< aux(54) s(522) =< s(474)*aux(54) s(523) =< s(522) s(491) =< s(487) s(492) =< s(487) s(493) =< s(487) s(494) =< s(487) s(492) =< s(488) s(493) =< s(489) s(495) =< s(490) s(496) =< s(487) s(497) =< s(487)+1 s(498) =< s(487)-1 s(493) =< s(486)*(1/3)+s(489) s(494) =< s(486)*(1/3)+s(489) s(492) =< s(486)*(1/2)+s(488) s(493) =< s(486)*(1/2)+s(488) s(494) =< s(486)*(1/2)+s(488) s(495) =< s(486)*(1/5)+s(490) s(491) =< s(486)*(1/5)+s(490) s(499) =< s(494)*s(496) s(500) =< s(493)*s(497) s(501) =< s(492)*s(496) s(502) =< s(492)*s(498) s(503) =< s(491)*s(497) s(504) =< s(495)*s(497) s(505) =< s(499) s(506) =< s(487) s(507) =< s(500) s(508) =< s(507)*s(497) s(509) =< s(508) s(510) =< s(501) s(511) =< s(510)*s(487) s(512) =< s(511) s(513) =< s(502) s(514) =< s(503) s(515) =< s(504) s(516) =< s(515)*s(497) s(517) =< s(516) s(459) =< aux(53) s(460) =< aux(53) s(461) =< aux(53) s(462) =< aux(53) s(460) =< s(456) s(461) =< s(457) s(463) =< s(458) s(464) =< aux(53) s(465) =< aux(53)+1 s(466) =< aux(53)-1 s(461) =< s(454)*(1/3)+s(457) s(462) =< s(454)*(1/3)+s(457) s(460) =< s(454)*(1/2)+s(456) s(461) =< s(454)*(1/2)+s(456) s(462) =< s(454)*(1/2)+s(456) s(463) =< s(454)*(1/5)+s(458) s(459) =< s(454)*(1/5)+s(458) s(467) =< s(462)*s(464) s(468) =< s(461)*s(465) s(469) =< s(460)*s(464) s(470) =< s(460)*s(466) s(471) =< s(459)*s(465) s(472) =< s(463)*s(465) s(473) =< s(467) s(475) =< s(468) s(476) =< s(475)*s(465) s(477) =< s(476) s(478) =< s(469) s(479) =< s(478)*aux(53) s(480) =< s(479) s(481) =< s(470) s(482) =< s(471) s(483) =< s(472) s(484) =< s(483)*s(465) s(485) =< s(484) with precondition: [V>=1,Out>=1,V1>=Out] #### Cost of chains of fun1(V1,V,V5,Out): * Chain [38]: 12*s(529)+12*s(530)+20*s(531)+28*s(532)+12*s(533)+8*s(543)+8*s(544)+20*s(545)+8*s(547)+20*s(548)+8*s(550)+8*s(551)+8*s(552)+20*s(553)+8*s(555)+12*s(561)+12*s(562)+20*s(563)+28*s(564)+12*s(565)+8*s(575)+8*s(576)+20*s(577)+8*s(579)+20*s(580)+8*s(582)+8*s(583)+8*s(584)+20*s(585)+8*s(587)+12*s(657)+12*s(658)+20*s(659)+28*s(660)+12*s(661)+8*s(671)+8*s(672)+20*s(673)+8*s(675)+20*s(676)+8*s(678)+8*s(679)+8*s(680)+20*s(681)+8*s(683)+0 Such that:aux(55) =< V1 aux(56) =< 2*V1+1 aux(57) =< V1/2 aux(58) =< 2/3*V1 aux(59) =< 3/5*V1 aux(60) =< V aux(61) =< 2*V+1 aux(62) =< V/2 aux(63) =< 2/3*V aux(64) =< 3/5*V aux(65) =< V5 aux(66) =< 2*V5+1 aux(67) =< V5/2 aux(68) =< 2/3*V5 aux(69) =< 3/5*V5 s(657) =< aux(55) s(658) =< aux(55) s(659) =< aux(55) s(660) =< aux(55) s(658) =< aux(57) s(659) =< aux(58) s(661) =< aux(59) s(662) =< aux(55) s(663) =< aux(55)+1 s(664) =< aux(55)-1 s(659) =< aux(56)*(1/3)+aux(58) s(660) =< aux(56)*(1/3)+aux(58) s(658) =< aux(56)*(1/2)+aux(57) s(659) =< aux(56)*(1/2)+aux(57) s(660) =< aux(56)*(1/2)+aux(57) s(661) =< aux(56)*(1/5)+aux(59) s(657) =< aux(56)*(1/5)+aux(59) s(665) =< s(660)*s(662) s(666) =< s(659)*s(663) s(667) =< s(658)*s(662) s(668) =< s(658)*s(664) s(669) =< s(657)*s(663) s(670) =< s(661)*s(663) s(671) =< s(665) s(672) =< aux(55) s(673) =< s(666) s(674) =< s(673)*s(663) s(675) =< s(674) s(676) =< s(667) s(677) =< s(676)*aux(55) s(678) =< s(677) s(679) =< s(668) s(680) =< s(669) s(681) =< s(670) s(682) =< s(681)*s(663) s(683) =< s(682) s(529) =< aux(65) s(530) =< aux(65) s(531) =< aux(65) s(532) =< aux(65) s(530) =< aux(67) s(531) =< aux(68) s(533) =< aux(69) s(534) =< aux(65) s(535) =< aux(65)+1 s(536) =< aux(65)-1 s(531) =< aux(66)*(1/3)+aux(68) s(532) =< aux(66)*(1/3)+aux(68) s(530) =< aux(66)*(1/2)+aux(67) s(531) =< aux(66)*(1/2)+aux(67) s(532) =< aux(66)*(1/2)+aux(67) s(533) =< aux(66)*(1/5)+aux(69) s(529) =< aux(66)*(1/5)+aux(69) s(537) =< s(532)*s(534) s(538) =< s(531)*s(535) s(539) =< s(530)*s(534) s(540) =< s(530)*s(536) s(541) =< s(529)*s(535) s(542) =< s(533)*s(535) s(543) =< s(537) s(544) =< aux(65) s(545) =< s(538) s(546) =< s(545)*s(535) s(547) =< s(546) s(548) =< s(539) s(549) =< s(548)*aux(65) s(550) =< s(549) s(551) =< s(540) s(552) =< s(541) s(553) =< s(542) s(554) =< s(553)*s(535) s(555) =< s(554) s(561) =< aux(60) s(562) =< aux(60) s(563) =< aux(60) s(564) =< aux(60) s(562) =< aux(62) s(563) =< aux(63) s(565) =< aux(64) s(566) =< aux(60) s(567) =< aux(60)+1 s(568) =< aux(60)-1 s(563) =< aux(61)*(1/3)+aux(63) s(564) =< aux(61)*(1/3)+aux(63) s(562) =< aux(61)*(1/2)+aux(62) s(563) =< aux(61)*(1/2)+aux(62) s(564) =< aux(61)*(1/2)+aux(62) s(565) =< aux(61)*(1/5)+aux(64) s(561) =< aux(61)*(1/5)+aux(64) s(569) =< s(564)*s(566) s(570) =< s(563)*s(567) s(571) =< s(562)*s(566) s(572) =< s(562)*s(568) s(573) =< s(561)*s(567) s(574) =< s(565)*s(567) s(575) =< s(569) s(576) =< aux(60) s(577) =< s(570) s(578) =< s(577)*s(567) s(579) =< s(578) s(580) =< s(571) s(581) =< s(580)*aux(60) s(582) =< s(581) s(583) =< s(572) s(584) =< s(573) s(585) =< s(574) s(586) =< s(585)*s(567) s(587) =< s(586) with precondition: [Out=0,V1>=0,V>=0,V5>=0] * Chain [37]: 12*s(909)+12*s(915)+12*s(916)+20*s(917)+28*s(918)+12*s(919)+8*s(929)+8*s(930)+20*s(931)+8*s(933)+20*s(934)+8*s(936)+8*s(937)+8*s(938)+20*s(939)+8*s(941)+12*s(949)+12*s(950)+20*s(951)+28*s(952)+12*s(953)+8*s(963)+8*s(964)+20*s(965)+8*s(967)+20*s(968)+8*s(970)+8*s(971)+8*s(972)+20*s(973)+8*s(975)+12*s(1049)+12*s(1050)+20*s(1051)+28*s(1052)+12*s(1053)+8*s(1063)+8*s(1064)+20*s(1065)+8*s(1067)+20*s(1068)+8*s(1070)+8*s(1071)+8*s(1072)+20*s(1073)+8*s(1075)+4*s(1143)+3 Such that:aux(70) =< 1 aux(71) =< V1 aux(72) =< V1+1 aux(73) =< 2*V1+1 aux(74) =< V1/2 aux(75) =< 2/3*V1 aux(76) =< 3/5*V1 aux(77) =< V aux(78) =< 2*V+1 aux(79) =< V/2 aux(80) =< 2/3*V aux(81) =< 3/5*V aux(82) =< V5 aux(83) =< 2*V5+1 aux(84) =< V5/2 aux(85) =< 2/3*V5 aux(86) =< 3/5*V5 s(909) =< aux(70) s(915) =< aux(82) s(916) =< aux(82) s(917) =< aux(82) s(918) =< aux(82) s(916) =< aux(84) s(917) =< aux(85) s(919) =< aux(86) s(920) =< aux(82) s(921) =< aux(82)+1 s(922) =< aux(82)-1 s(917) =< aux(83)*(1/3)+aux(85) s(918) =< aux(83)*(1/3)+aux(85) s(916) =< aux(83)*(1/2)+aux(84) s(917) =< aux(83)*(1/2)+aux(84) s(918) =< aux(83)*(1/2)+aux(84) s(919) =< aux(83)*(1/5)+aux(86) s(915) =< aux(83)*(1/5)+aux(86) s(923) =< s(918)*s(920) s(924) =< s(917)*s(921) s(925) =< s(916)*s(920) s(926) =< s(916)*s(922) s(927) =< s(915)*s(921) s(928) =< s(919)*s(921) s(929) =< s(923) s(930) =< aux(82) s(931) =< s(924) s(932) =< s(931)*s(921) s(933) =< s(932) s(934) =< s(925) s(935) =< s(934)*aux(82) s(936) =< s(935) s(937) =< s(926) s(938) =< s(927) s(939) =< s(928) s(940) =< s(939)*s(921) s(941) =< s(940) s(949) =< aux(77) s(950) =< aux(77) s(951) =< aux(77) s(952) =< aux(77) s(950) =< aux(79) s(951) =< aux(80) s(953) =< aux(81) s(954) =< aux(77) s(955) =< aux(77)+1 s(956) =< aux(77)-1 s(951) =< aux(78)*(1/3)+aux(80) s(952) =< aux(78)*(1/3)+aux(80) s(950) =< aux(78)*(1/2)+aux(79) s(951) =< aux(78)*(1/2)+aux(79) s(952) =< aux(78)*(1/2)+aux(79) s(953) =< aux(78)*(1/5)+aux(81) s(949) =< aux(78)*(1/5)+aux(81) s(957) =< s(952)*s(954) s(958) =< s(951)*s(955) s(959) =< s(950)*s(954) s(960) =< s(950)*s(956) s(961) =< s(949)*s(955) s(962) =< s(953)*s(955) s(963) =< s(957) s(964) =< aux(77) s(965) =< s(958) s(966) =< s(965)*s(955) s(967) =< s(966) s(968) =< s(959) s(969) =< s(968)*aux(77) s(970) =< s(969) s(971) =< s(960) s(972) =< s(961) s(973) =< s(962) s(974) =< s(973)*s(955) s(975) =< s(974) s(1049) =< aux(71) s(1050) =< aux(71) s(1051) =< aux(71) s(1052) =< aux(71) s(1050) =< aux(74) s(1051) =< aux(75) s(1053) =< aux(76) s(1054) =< aux(71) s(1055) =< aux(71)+1 s(1056) =< aux(71)-1 s(1051) =< aux(73)*(1/3)+aux(75) s(1052) =< aux(73)*(1/3)+aux(75) s(1050) =< aux(73)*(1/2)+aux(74) s(1051) =< aux(73)*(1/2)+aux(74) s(1052) =< aux(73)*(1/2)+aux(74) s(1053) =< aux(73)*(1/5)+aux(76) s(1049) =< aux(73)*(1/5)+aux(76) s(1057) =< s(1052)*s(1054) s(1058) =< s(1051)*s(1055) s(1059) =< s(1050)*s(1054) s(1060) =< s(1050)*s(1056) s(1061) =< s(1049)*s(1055) s(1062) =< s(1053)*s(1055) s(1063) =< s(1057) s(1064) =< aux(71) s(1065) =< s(1058) s(1066) =< s(1065)*s(1055) s(1067) =< s(1066) s(1068) =< s(1059) s(1069) =< s(1068)*aux(71) s(1070) =< s(1069) s(1071) =< s(1060) s(1072) =< s(1061) s(1073) =< s(1062) s(1074) =< s(1073)*s(1055) s(1075) =< s(1074) s(1143) =< aux(72) with precondition: [Out=1,V1>=0,V>=0,V5>=0] * Chain [36]: 12*s(1313)+12*s(1314)+20*s(1315)+28*s(1316)+12*s(1317)+8*s(1327)+20*s(1328)+20*s(1329)+8*s(1331)+20*s(1332)+8*s(1334)+8*s(1335)+8*s(1336)+20*s(1337)+8*s(1339)+8*s(1343)+8*s(1345)+6*s(1383)+6*s(1384)+10*s(1385)+14*s(1386)+6*s(1387)+4*s(1397)+4*s(1398)+10*s(1399)+4*s(1401)+10*s(1402)+4*s(1404)+4*s(1405)+4*s(1406)+10*s(1407)+4*s(1409)+6*s(1421)+6*s(1422)+10*s(1423)+14*s(1424)+6*s(1425)+4*s(1435)+4*s(1436)+10*s(1437)+4*s(1439)+10*s(1440)+4*s(1442)+4*s(1443)+4*s(1444)+10*s(1445)+4*s(1447)+3 Such that:aux(95) =< V1 aux(96) =< 2*V1+1 aux(97) =< V1/2 aux(98) =< 2/3*V1 aux(99) =< 3/5*V1 aux(100) =< V aux(101) =< V+1 aux(102) =< 2*V+1 aux(103) =< V/2 aux(104) =< 2/3*V aux(105) =< 3/5*V aux(106) =< V5 aux(107) =< 2*V5+1 aux(108) =< V5/2 aux(109) =< 2/3*V5 aux(110) =< 3/5*V5 s(1328) =< aux(100) s(1343) =< aux(101) s(1344) =< s(1328)*aux(101) s(1345) =< s(1344) s(1313) =< aux(100) s(1314) =< aux(100) s(1315) =< aux(100) s(1316) =< aux(100) s(1314) =< aux(103) s(1315) =< aux(104) s(1317) =< aux(105) s(1318) =< aux(100) s(1319) =< aux(100)+1 s(1320) =< aux(100)-1 s(1315) =< aux(102)*(1/3)+aux(104) s(1316) =< aux(102)*(1/3)+aux(104) s(1314) =< aux(102)*(1/2)+aux(103) s(1315) =< aux(102)*(1/2)+aux(103) s(1316) =< aux(102)*(1/2)+aux(103) s(1317) =< aux(102)*(1/5)+aux(105) s(1313) =< aux(102)*(1/5)+aux(105) s(1321) =< s(1316)*s(1318) s(1322) =< s(1315)*s(1319) s(1323) =< s(1314)*s(1318) s(1324) =< s(1314)*s(1320) s(1325) =< s(1313)*s(1319) s(1326) =< s(1317)*s(1319) s(1327) =< s(1321) s(1329) =< s(1322) s(1330) =< s(1329)*s(1319) s(1331) =< s(1330) s(1332) =< s(1323) s(1333) =< s(1332)*aux(100) s(1334) =< s(1333) s(1335) =< s(1324) s(1336) =< s(1325) s(1337) =< s(1326) s(1338) =< s(1337)*s(1319) s(1339) =< s(1338) s(1421) =< aux(95) s(1422) =< aux(95) s(1423) =< aux(95) s(1424) =< aux(95) s(1422) =< aux(97) s(1423) =< aux(98) s(1425) =< aux(99) s(1426) =< aux(95) s(1427) =< aux(95)+1 s(1428) =< aux(95)-1 s(1423) =< aux(96)*(1/3)+aux(98) s(1424) =< aux(96)*(1/3)+aux(98) s(1422) =< aux(96)*(1/2)+aux(97) s(1423) =< aux(96)*(1/2)+aux(97) s(1424) =< aux(96)*(1/2)+aux(97) s(1425) =< aux(96)*(1/5)+aux(99) s(1421) =< aux(96)*(1/5)+aux(99) s(1429) =< s(1424)*s(1426) s(1430) =< s(1423)*s(1427) s(1431) =< s(1422)*s(1426) s(1432) =< s(1422)*s(1428) s(1433) =< s(1421)*s(1427) s(1434) =< s(1425)*s(1427) s(1435) =< s(1429) s(1436) =< aux(95) s(1437) =< s(1430) s(1438) =< s(1437)*s(1427) s(1439) =< s(1438) s(1440) =< s(1431) s(1441) =< s(1440)*aux(95) s(1442) =< s(1441) s(1443) =< s(1432) s(1444) =< s(1433) s(1445) =< s(1434) s(1446) =< s(1445)*s(1427) s(1447) =< s(1446) s(1383) =< aux(106) s(1384) =< aux(106) s(1385) =< aux(106) s(1386) =< aux(106) s(1384) =< aux(108) s(1385) =< aux(109) s(1387) =< aux(110) s(1388) =< aux(106) s(1389) =< aux(106)+1 s(1390) =< aux(106)-1 s(1385) =< aux(107)*(1/3)+aux(109) s(1386) =< aux(107)*(1/3)+aux(109) s(1384) =< aux(107)*(1/2)+aux(108) s(1385) =< aux(107)*(1/2)+aux(108) s(1386) =< aux(107)*(1/2)+aux(108) s(1387) =< aux(107)*(1/5)+aux(110) s(1383) =< aux(107)*(1/5)+aux(110) s(1391) =< s(1386)*s(1388) s(1392) =< s(1385)*s(1389) s(1393) =< s(1384)*s(1388) s(1394) =< s(1384)*s(1390) s(1395) =< s(1383)*s(1389) s(1396) =< s(1387)*s(1389) s(1397) =< s(1391) s(1398) =< aux(106) s(1399) =< s(1392) s(1400) =< s(1399)*s(1389) s(1401) =< s(1400) s(1402) =< s(1393) s(1403) =< s(1402)*aux(106) s(1404) =< s(1403) s(1405) =< s(1394) s(1406) =< s(1395) s(1407) =< s(1396) s(1408) =< s(1407)*s(1389) s(1409) =< s(1408) with precondition: [V1>=0,V5>=0,Out>=2,V+1>=Out] #### Cost of chains of fun2(V1,V,Out): * Chain [40]: 6*s(1593)+6*s(1594)+10*s(1595)+14*s(1596)+6*s(1597)+4*s(1607)+4*s(1608)+10*s(1609)+4*s(1611)+10*s(1612)+4*s(1614)+4*s(1615)+4*s(1616)+10*s(1617)+4*s(1619)+6*s(1625)+6*s(1626)+10*s(1627)+14*s(1628)+6*s(1629)+4*s(1639)+4*s(1640)+10*s(1641)+4*s(1643)+10*s(1644)+4*s(1646)+4*s(1647)+4*s(1648)+10*s(1649)+4*s(1651)+1 Such that:aux(111) =< V1 aux(112) =< 2*V1+1 aux(113) =< V1/2 aux(114) =< 2/3*V1 aux(115) =< 3/5*V1 aux(116) =< V aux(117) =< 2*V+1 aux(118) =< V/2 aux(119) =< 2/3*V aux(120) =< 3/5*V s(1625) =< aux(111) s(1626) =< aux(111) s(1627) =< aux(111) s(1628) =< aux(111) s(1626) =< aux(113) s(1627) =< aux(114) s(1629) =< aux(115) s(1630) =< aux(111) s(1631) =< aux(111)+1 s(1632) =< aux(111)-1 s(1627) =< aux(112)*(1/3)+aux(114) s(1628) =< aux(112)*(1/3)+aux(114) s(1626) =< aux(112)*(1/2)+aux(113) s(1627) =< aux(112)*(1/2)+aux(113) s(1628) =< aux(112)*(1/2)+aux(113) s(1629) =< aux(112)*(1/5)+aux(115) s(1625) =< aux(112)*(1/5)+aux(115) s(1633) =< s(1628)*s(1630) s(1634) =< s(1627)*s(1631) s(1635) =< s(1626)*s(1630) s(1636) =< s(1626)*s(1632) s(1637) =< s(1625)*s(1631) s(1638) =< s(1629)*s(1631) s(1639) =< s(1633) s(1640) =< aux(111) s(1641) =< s(1634) s(1642) =< s(1641)*s(1631) s(1643) =< s(1642) s(1644) =< s(1635) s(1645) =< s(1644)*aux(111) s(1646) =< s(1645) s(1647) =< s(1636) s(1648) =< s(1637) s(1649) =< s(1638) s(1650) =< s(1649)*s(1631) s(1651) =< s(1650) s(1593) =< aux(116) s(1594) =< aux(116) s(1595) =< aux(116) s(1596) =< aux(116) s(1594) =< aux(118) s(1595) =< aux(119) s(1597) =< aux(120) s(1598) =< aux(116) s(1599) =< aux(116)+1 s(1600) =< aux(116)-1 s(1595) =< aux(117)*(1/3)+aux(119) s(1596) =< aux(117)*(1/3)+aux(119) s(1594) =< aux(117)*(1/2)+aux(118) s(1595) =< aux(117)*(1/2)+aux(118) s(1596) =< aux(117)*(1/2)+aux(118) s(1597) =< aux(117)*(1/5)+aux(120) s(1593) =< aux(117)*(1/5)+aux(120) s(1601) =< s(1596)*s(1598) s(1602) =< s(1595)*s(1599) s(1603) =< s(1594)*s(1598) s(1604) =< s(1594)*s(1600) s(1605) =< s(1593)*s(1599) s(1606) =< s(1597)*s(1599) s(1607) =< s(1601) s(1608) =< aux(116) s(1609) =< s(1602) s(1610) =< s(1609)*s(1599) s(1611) =< s(1610) s(1612) =< s(1603) s(1613) =< s(1612)*aux(116) s(1614) =< s(1613) s(1615) =< s(1604) s(1616) =< s(1605) s(1617) =< s(1606) s(1618) =< s(1617)*s(1599) s(1619) =< s(1618) with precondition: [Out=0,V1>=0,V>=0] * Chain [39]: 3*s(1721)+3*s(1722)+5*s(1723)+7*s(1724)+3*s(1725)+2*s(1735)+2*s(1736)+5*s(1737)+2*s(1739)+5*s(1740)+2*s(1742)+2*s(1743)+2*s(1744)+5*s(1745)+2*s(1747)+3*s(1753)+3*s(1754)+5*s(1755)+7*s(1756)+3*s(1757)+2*s(1767)+4*s(1768)+5*s(1769)+2*s(1771)+5*s(1772)+2*s(1774)+2*s(1775)+2*s(1776)+5*s(1777)+2*s(1779)+1 Such that:s(1717) =< V1 s(1716) =< 2*V1+1 s(1718) =< V1/2 s(1719) =< 2/3*V1 s(1720) =< 3/5*V1 s(1748) =< 2*V+1 s(1750) =< V/2 s(1751) =< 2/3*V s(1752) =< 3/5*V aux(121) =< V s(1768) =< aux(121) s(1753) =< aux(121) s(1754) =< aux(121) s(1755) =< aux(121) s(1756) =< aux(121) s(1754) =< s(1750) s(1755) =< s(1751) s(1757) =< s(1752) s(1758) =< aux(121) s(1759) =< aux(121)+1 s(1760) =< aux(121)-1 s(1755) =< s(1748)*(1/3)+s(1751) s(1756) =< s(1748)*(1/3)+s(1751) s(1754) =< s(1748)*(1/2)+s(1750) s(1755) =< s(1748)*(1/2)+s(1750) s(1756) =< s(1748)*(1/2)+s(1750) s(1757) =< s(1748)*(1/5)+s(1752) s(1753) =< s(1748)*(1/5)+s(1752) s(1761) =< s(1756)*s(1758) s(1762) =< s(1755)*s(1759) s(1763) =< s(1754)*s(1758) s(1764) =< s(1754)*s(1760) s(1765) =< s(1753)*s(1759) s(1766) =< s(1757)*s(1759) s(1767) =< s(1761) s(1769) =< s(1762) s(1770) =< s(1769)*s(1759) s(1771) =< s(1770) s(1772) =< s(1763) s(1773) =< s(1772)*aux(121) s(1774) =< s(1773) s(1775) =< s(1764) s(1776) =< s(1765) s(1777) =< s(1766) s(1778) =< s(1777)*s(1759) s(1779) =< s(1778) s(1721) =< s(1717) s(1722) =< s(1717) s(1723) =< s(1717) s(1724) =< s(1717) s(1722) =< s(1718) s(1723) =< s(1719) s(1725) =< s(1720) s(1726) =< s(1717) s(1727) =< s(1717)+1 s(1728) =< s(1717)-1 s(1723) =< s(1716)*(1/3)+s(1719) s(1724) =< s(1716)*(1/3)+s(1719) s(1722) =< s(1716)*(1/2)+s(1718) s(1723) =< s(1716)*(1/2)+s(1718) s(1724) =< s(1716)*(1/2)+s(1718) s(1725) =< s(1716)*(1/5)+s(1720) s(1721) =< s(1716)*(1/5)+s(1720) s(1729) =< s(1724)*s(1726) s(1730) =< s(1723)*s(1727) s(1731) =< s(1722)*s(1726) s(1732) =< s(1722)*s(1728) s(1733) =< s(1721)*s(1727) s(1734) =< s(1725)*s(1727) s(1735) =< s(1729) s(1736) =< s(1717) s(1737) =< s(1730) s(1738) =< s(1737)*s(1727) s(1739) =< s(1738) s(1740) =< s(1731) s(1741) =< s(1740)*s(1717) s(1742) =< s(1741) s(1743) =< s(1732) s(1744) =< s(1733) s(1745) =< s(1734) s(1746) =< s(1745)*s(1727) s(1747) =< s(1746) with precondition: [Out>=1,V1>=Out,V>=Out] #### Cost of chains of fun3(V1,Out): * Chain [43]: 0 with precondition: [Out=0,V1>=0] * Chain [42]: 0 with precondition: [Out=1,V1>=0] * Chain [41]: 3*s(1787)+3*s(1788)+5*s(1789)+7*s(1790)+3*s(1791)+2*s(1801)+2*s(1802)+5*s(1803)+2*s(1805)+5*s(1806)+2*s(1808)+2*s(1809)+2*s(1810)+5*s(1811)+2*s(1813)+0 Such that:s(1783) =< V1 s(1782) =< 2*V1+1 s(1784) =< V1/2 s(1785) =< 2/3*V1 s(1786) =< 3/5*V1 s(1787) =< s(1783) s(1788) =< s(1783) s(1789) =< s(1783) s(1790) =< s(1783) s(1788) =< s(1784) s(1789) =< s(1785) s(1791) =< s(1786) s(1792) =< s(1783) s(1793) =< s(1783)+1 s(1794) =< s(1783)-1 s(1789) =< s(1782)*(1/3)+s(1785) s(1790) =< s(1782)*(1/3)+s(1785) s(1788) =< s(1782)*(1/2)+s(1784) s(1789) =< s(1782)*(1/2)+s(1784) s(1790) =< s(1782)*(1/2)+s(1784) s(1791) =< s(1782)*(1/5)+s(1786) s(1787) =< s(1782)*(1/5)+s(1786) s(1795) =< s(1790)*s(1792) s(1796) =< s(1789)*s(1793) s(1797) =< s(1788)*s(1792) s(1798) =< s(1788)*s(1794) s(1799) =< s(1787)*s(1793) s(1800) =< s(1791)*s(1793) s(1801) =< s(1795) s(1802) =< s(1783) s(1803) =< s(1796) s(1804) =< s(1803)*s(1793) s(1805) =< s(1804) s(1806) =< s(1797) s(1807) =< s(1806)*s(1783) s(1808) =< s(1807) s(1809) =< s(1798) s(1810) =< s(1799) s(1811) =< s(1800) s(1812) =< s(1811)*s(1793) s(1813) =< s(1812) with precondition: [V1>=1,Out>=1,V1+1>=Out] #### Cost of chains of start(V1,V,V5): * Chain [44]: 25*s(1815)+3*s(1818)+10*s(1819)+2*s(1821)+22*s(1823)+6*s(1828)+64*s(1830)+3*s(1833)+2*s(1836)+66*s(1844)+66*s(1845)+110*s(1846)+154*s(1847)+66*s(1848)+44*s(1858)+47*s(1859)+110*s(1860)+44*s(1862)+110*s(1863)+44*s(1865)+44*s(1866)+44*s(1867)+110*s(1868)+44*s(1870)+63*s(1909)+63*s(1910)+105*s(1911)+147*s(1912)+63*s(1913)+42*s(1923)+105*s(1924)+42*s(1926)+105*s(1927)+42*s(1929)+42*s(1930)+42*s(1931)+105*s(1932)+42*s(1934)+2*s(2083)+30*s(2179)+30*s(2180)+50*s(2181)+70*s(2182)+30*s(2183)+20*s(2193)+20*s(2194)+50*s(2195)+20*s(2197)+50*s(2198)+20*s(2200)+20*s(2201)+20*s(2202)+50*s(2203)+20*s(2205)+8*s(2352)+5 Such that:s(1833) =< V1-V+1 s(1818) =< V-V5 aux(125) =< 1 aux(126) =< V1 aux(127) =< V1+1 aux(128) =< 2*V1+1 aux(129) =< V1/2 aux(130) =< 2/3*V1 aux(131) =< 3/5*V1 aux(132) =< V aux(133) =< V+1 aux(134) =< 2*V+1 aux(135) =< V/2 aux(136) =< 2/3*V aux(137) =< 3/5*V aux(138) =< V5 aux(139) =< 2*V5+1 aux(140) =< V5/2 aux(141) =< 2/3*V5 aux(142) =< 3/5*V5 s(1823) =< aux(125) s(1909) =< aux(132) s(1910) =< aux(132) s(1911) =< aux(132) s(1912) =< aux(132) s(1910) =< aux(135) s(1911) =< aux(136) s(1913) =< aux(137) s(1914) =< aux(132) s(1915) =< aux(132)+1 s(1916) =< aux(132)-1 s(1911) =< aux(134)*(1/3)+aux(136) s(1912) =< aux(134)*(1/3)+aux(136) s(1910) =< aux(134)*(1/2)+aux(135) s(1911) =< aux(134)*(1/2)+aux(135) s(1912) =< aux(134)*(1/2)+aux(135) s(1913) =< aux(134)*(1/5)+aux(137) s(1909) =< aux(134)*(1/5)+aux(137) s(1917) =< s(1912)*s(1914) s(1918) =< s(1911)*s(1915) s(1919) =< s(1910)*s(1914) s(1920) =< s(1910)*s(1916) s(1921) =< s(1909)*s(1915) s(1922) =< s(1913)*s(1915) s(1923) =< s(1917) s(1830) =< aux(132) s(1924) =< s(1918) s(1925) =< s(1924)*s(1915) s(1926) =< s(1925) s(1927) =< s(1919) s(1928) =< s(1927)*aux(132) s(1929) =< s(1928) s(1930) =< s(1920) s(1931) =< s(1921) s(1932) =< s(1922) s(1933) =< s(1932)*s(1915) s(1934) =< s(1933) s(1844) =< aux(126) s(1845) =< aux(126) s(1846) =< aux(126) s(1847) =< aux(126) s(1845) =< aux(129) s(1846) =< aux(130) s(1848) =< aux(131) s(1849) =< aux(126) s(1850) =< aux(126)+1 s(1851) =< aux(126)-1 s(1846) =< aux(128)*(1/3)+aux(130) s(1847) =< aux(128)*(1/3)+aux(130) s(1845) =< aux(128)*(1/2)+aux(129) s(1846) =< aux(128)*(1/2)+aux(129) s(1847) =< aux(128)*(1/2)+aux(129) s(1848) =< aux(128)*(1/5)+aux(131) s(1844) =< aux(128)*(1/5)+aux(131) s(1852) =< s(1847)*s(1849) s(1853) =< s(1846)*s(1850) s(1854) =< s(1845)*s(1849) s(1855) =< s(1845)*s(1851) s(1856) =< s(1844)*s(1850) s(1857) =< s(1848)*s(1850) s(1858) =< s(1852) s(1859) =< aux(126) s(1860) =< s(1853) s(1861) =< s(1860)*s(1850) s(1862) =< s(1861) s(1863) =< s(1854) s(1864) =< s(1863)*aux(126) s(1865) =< s(1864) s(1866) =< s(1855) s(1867) =< s(1856) s(1868) =< s(1857) s(1869) =< s(1868)*s(1850) s(1870) =< s(1869) s(2179) =< aux(138) s(2180) =< aux(138) s(2181) =< aux(138) s(2182) =< aux(138) s(2180) =< aux(140) s(2181) =< aux(141) s(2183) =< aux(142) s(2184) =< aux(138) s(2185) =< aux(138)+1 s(2186) =< aux(138)-1 s(2181) =< aux(139)*(1/3)+aux(141) s(2182) =< aux(139)*(1/3)+aux(141) s(2180) =< aux(139)*(1/2)+aux(140) s(2181) =< aux(139)*(1/2)+aux(140) s(2182) =< aux(139)*(1/2)+aux(140) s(2183) =< aux(139)*(1/5)+aux(142) s(2179) =< aux(139)*(1/5)+aux(142) s(2187) =< s(2182)*s(2184) s(2188) =< s(2181)*s(2185) s(2189) =< s(2180)*s(2184) s(2190) =< s(2180)*s(2186) s(2191) =< s(2179)*s(2185) s(2192) =< s(2183)*s(2185) s(2193) =< s(2187) s(2194) =< aux(138) s(2195) =< s(2188) s(2196) =< s(2195)*s(2185) s(2197) =< s(2196) s(2198) =< s(2189) s(2199) =< s(2198)*aux(138) s(2200) =< s(2199) s(2201) =< s(2190) s(2202) =< s(2191) s(2203) =< s(2192) s(2204) =< s(2203)*s(2185) s(2205) =< s(2204) s(1815) =< aux(127) s(1827) =< s(1815)*aux(127) s(1828) =< s(1827) s(2082) =< s(1859)*aux(127) s(2083) =< s(2082) s(1819) =< aux(133) s(2351) =< s(1830)*aux(133) s(2352) =< s(2351) s(1835) =< s(1833)*aux(127) s(1836) =< s(1835) s(1820) =< s(1818)*aux(133) s(1821) =< s(1820) with precondition: [] Closed-form bounds of start(V1,V,V5): ------------------------------------- * Chain [44] with precondition: [] - Upper bound: nat(V1)*641+27+nat(V1)*396*nat(V1)+nat(V1)*88*nat(V1)*nat(V1)+nat(V1)*44*nat(V1)*nat(3/5*V1)+nat(V1)*44*nat(nat(V1)+ -1)+nat(V1)*198*nat(3/5*V1)+nat(V1)*2*nat(V1+1)+nat(V)*631+nat(V)*378*nat(V)+nat(V)*84*nat(V)*nat(V)+nat(V)*42*nat(V)*nat(3/5*V)+nat(V)*42*nat(nat(V)+ -1)+nat(V)*189*nat(3/5*V)+nat(V)*8*nat(V+1)+nat(V5)*290+nat(V5)*180*nat(V5)+nat(V5)*40*nat(V5)*nat(V5)+nat(V5)*20*nat(V5)*nat(3/5*V5)+nat(V5)*20*nat(nat(V5)+ -1)+nat(V5)*90*nat(3/5*V5)+nat(3/5*V1)*220+nat(3/5*V)*210+nat(3/5*V5)*100+nat(V1+1)*25+nat(V1+1)*6*nat(V1+1)+nat(V1+1)*2*nat(V1-V+1)+nat(V+1)*10+nat(V+1)*2*nat(V-V5)+nat(V1-V+1)*3+nat(V-V5)*3 - Complexity: n^3 ### Maximum cost of start(V1,V,V5): nat(V1)*641+27+nat(V1)*396*nat(V1)+nat(V1)*88*nat(V1)*nat(V1)+nat(V1)*44*nat(V1)*nat(3/5*V1)+nat(V1)*44*nat(nat(V1)+ -1)+nat(V1)*198*nat(3/5*V1)+nat(V1)*2*nat(V1+1)+nat(V)*631+nat(V)*378*nat(V)+nat(V)*84*nat(V)*nat(V)+nat(V)*42*nat(V)*nat(3/5*V)+nat(V)*42*nat(nat(V)+ -1)+nat(V)*189*nat(3/5*V)+nat(V)*8*nat(V+1)+nat(V5)*290+nat(V5)*180*nat(V5)+nat(V5)*40*nat(V5)*nat(V5)+nat(V5)*20*nat(V5)*nat(3/5*V5)+nat(V5)*20*nat(nat(V5)+ -1)+nat(V5)*90*nat(3/5*V5)+nat(3/5*V1)*220+nat(3/5*V)*210+nat(3/5*V5)*100+nat(V1+1)*25+nat(V1+1)*6*nat(V1+1)+nat(V1+1)*2*nat(V1-V+1)+nat(V+1)*10+nat(V+1)*2*nat(V-V5)+nat(V1-V+1)*3+nat(V-V5)*3 Asymptotic class: n^3 * Total analysis performed in 6520 ms. ---------------------------------------- (14) BOUNDS(1, n^3) ---------------------------------------- (15) RenamingProof (BOTH BOUNDS(ID, ID)) Renamed function symbols to avoid clashes with predefined symbol. ---------------------------------------- (16) Obligation: The Runtime Complexity (innermost) of the given CpxRelTRS could be proven to be BOUNDS(n^1, INF). The TRS R consists of the following rules: minus(x, y) -> cond(min(x, y), x, y) cond(y, x, y) -> s(minus(x, s(y))) min(0', v) -> 0' min(u, 0') -> 0' min(s(u), s(v)) -> s(min(u, v)) The (relative) TRS S consists of the following rules: encArg(s(x_1)) -> s(encArg(x_1)) encArg(0') -> 0' encArg(cons_minus(x_1, x_2)) -> minus(encArg(x_1), encArg(x_2)) encArg(cons_cond(x_1, x_2, x_3)) -> cond(encArg(x_1), encArg(x_2), encArg(x_3)) encArg(cons_min(x_1, x_2)) -> min(encArg(x_1), encArg(x_2)) encode_minus(x_1, x_2) -> minus(encArg(x_1), encArg(x_2)) encode_cond(x_1, x_2, x_3) -> cond(encArg(x_1), encArg(x_2), encArg(x_3)) encode_min(x_1, x_2) -> min(encArg(x_1), encArg(x_2)) encode_s(x_1) -> s(encArg(x_1)) encode_0 -> 0' Rewrite Strategy: INNERMOST ---------------------------------------- (17) TypeInferenceProof (BOTH BOUNDS(ID, ID)) Infered types. ---------------------------------------- (18) Obligation: Innermost TRS: Rules: minus(x, y) -> cond(min(x, y), x, y) cond(y, x, y) -> s(minus(x, s(y))) min(0', v) -> 0' min(u, 0') -> 0' min(s(u), s(v)) -> s(min(u, v)) encArg(s(x_1)) -> s(encArg(x_1)) encArg(0') -> 0' encArg(cons_minus(x_1, x_2)) -> minus(encArg(x_1), encArg(x_2)) encArg(cons_cond(x_1, x_2, x_3)) -> cond(encArg(x_1), encArg(x_2), encArg(x_3)) encArg(cons_min(x_1, x_2)) -> min(encArg(x_1), encArg(x_2)) encode_minus(x_1, x_2) -> minus(encArg(x_1), encArg(x_2)) encode_cond(x_1, x_2, x_3) -> cond(encArg(x_1), encArg(x_2), encArg(x_3)) encode_min(x_1, x_2) -> min(encArg(x_1), encArg(x_2)) encode_s(x_1) -> s(encArg(x_1)) encode_0 -> 0' Types: minus :: s:0':cons_minus:cons_cond:cons_min -> s:0':cons_minus:cons_cond:cons_min -> s:0':cons_minus:cons_cond:cons_min cond :: s:0':cons_minus:cons_cond:cons_min -> s:0':cons_minus:cons_cond:cons_min -> s:0':cons_minus:cons_cond:cons_min -> s:0':cons_minus:cons_cond:cons_min min :: s:0':cons_minus:cons_cond:cons_min -> s:0':cons_minus:cons_cond:cons_min -> s:0':cons_minus:cons_cond:cons_min s :: s:0':cons_minus:cons_cond:cons_min -> s:0':cons_minus:cons_cond:cons_min 0' :: s:0':cons_minus:cons_cond:cons_min encArg :: s:0':cons_minus:cons_cond:cons_min -> s:0':cons_minus:cons_cond:cons_min cons_minus :: s:0':cons_minus:cons_cond:cons_min -> s:0':cons_minus:cons_cond:cons_min -> s:0':cons_minus:cons_cond:cons_min cons_cond :: s:0':cons_minus:cons_cond:cons_min -> s:0':cons_minus:cons_cond:cons_min -> s:0':cons_minus:cons_cond:cons_min -> s:0':cons_minus:cons_cond:cons_min cons_min :: s:0':cons_minus:cons_cond:cons_min -> s:0':cons_minus:cons_cond:cons_min -> s:0':cons_minus:cons_cond:cons_min encode_minus :: s:0':cons_minus:cons_cond:cons_min -> s:0':cons_minus:cons_cond:cons_min -> s:0':cons_minus:cons_cond:cons_min encode_cond :: s:0':cons_minus:cons_cond:cons_min -> s:0':cons_minus:cons_cond:cons_min -> s:0':cons_minus:cons_cond:cons_min -> s:0':cons_minus:cons_cond:cons_min encode_min :: s:0':cons_minus:cons_cond:cons_min -> s:0':cons_minus:cons_cond:cons_min -> s:0':cons_minus:cons_cond:cons_min encode_s :: s:0':cons_minus:cons_cond:cons_min -> s:0':cons_minus:cons_cond:cons_min encode_0 :: s:0':cons_minus:cons_cond:cons_min hole_s:0':cons_minus:cons_cond:cons_min1_4 :: s:0':cons_minus:cons_cond:cons_min gen_s:0':cons_minus:cons_cond:cons_min2_4 :: Nat -> s:0':cons_minus:cons_cond:cons_min ---------------------------------------- (19) OrderProof (LOWER BOUND(ID)) Heuristically decided to analyse the following defined symbols: minus, cond, min, encArg They will be analysed ascendingly in the following order: minus = cond min < minus minus < encArg cond < encArg min < encArg ---------------------------------------- (20) Obligation: Innermost TRS: Rules: minus(x, y) -> cond(min(x, y), x, y) cond(y, x, y) -> s(minus(x, s(y))) min(0', v) -> 0' min(u, 0') -> 0' min(s(u), s(v)) -> s(min(u, v)) encArg(s(x_1)) -> s(encArg(x_1)) encArg(0') -> 0' encArg(cons_minus(x_1, x_2)) -> minus(encArg(x_1), encArg(x_2)) encArg(cons_cond(x_1, x_2, x_3)) -> cond(encArg(x_1), encArg(x_2), encArg(x_3)) encArg(cons_min(x_1, x_2)) -> min(encArg(x_1), encArg(x_2)) encode_minus(x_1, x_2) -> minus(encArg(x_1), encArg(x_2)) encode_cond(x_1, x_2, x_3) -> cond(encArg(x_1), encArg(x_2), encArg(x_3)) encode_min(x_1, x_2) -> min(encArg(x_1), encArg(x_2)) encode_s(x_1) -> s(encArg(x_1)) encode_0 -> 0' Types: minus :: s:0':cons_minus:cons_cond:cons_min -> s:0':cons_minus:cons_cond:cons_min -> s:0':cons_minus:cons_cond:cons_min cond :: s:0':cons_minus:cons_cond:cons_min -> s:0':cons_minus:cons_cond:cons_min -> s:0':cons_minus:cons_cond:cons_min -> s:0':cons_minus:cons_cond:cons_min min :: s:0':cons_minus:cons_cond:cons_min -> s:0':cons_minus:cons_cond:cons_min -> s:0':cons_minus:cons_cond:cons_min s :: s:0':cons_minus:cons_cond:cons_min -> s:0':cons_minus:cons_cond:cons_min 0' :: s:0':cons_minus:cons_cond:cons_min encArg :: s:0':cons_minus:cons_cond:cons_min -> s:0':cons_minus:cons_cond:cons_min cons_minus :: s:0':cons_minus:cons_cond:cons_min -> s:0':cons_minus:cons_cond:cons_min -> s:0':cons_minus:cons_cond:cons_min cons_cond :: s:0':cons_minus:cons_cond:cons_min -> s:0':cons_minus:cons_cond:cons_min -> s:0':cons_minus:cons_cond:cons_min -> s:0':cons_minus:cons_cond:cons_min cons_min :: s:0':cons_minus:cons_cond:cons_min -> s:0':cons_minus:cons_cond:cons_min -> s:0':cons_minus:cons_cond:cons_min encode_minus :: s:0':cons_minus:cons_cond:cons_min -> s:0':cons_minus:cons_cond:cons_min -> s:0':cons_minus:cons_cond:cons_min encode_cond :: s:0':cons_minus:cons_cond:cons_min -> s:0':cons_minus:cons_cond:cons_min -> s:0':cons_minus:cons_cond:cons_min -> s:0':cons_minus:cons_cond:cons_min encode_min :: s:0':cons_minus:cons_cond:cons_min -> s:0':cons_minus:cons_cond:cons_min -> s:0':cons_minus:cons_cond:cons_min encode_s :: s:0':cons_minus:cons_cond:cons_min -> s:0':cons_minus:cons_cond:cons_min encode_0 :: s:0':cons_minus:cons_cond:cons_min hole_s:0':cons_minus:cons_cond:cons_min1_4 :: s:0':cons_minus:cons_cond:cons_min gen_s:0':cons_minus:cons_cond:cons_min2_4 :: Nat -> s:0':cons_minus:cons_cond:cons_min Generator Equations: gen_s:0':cons_minus:cons_cond:cons_min2_4(0) <=> 0' gen_s:0':cons_minus:cons_cond:cons_min2_4(+(x, 1)) <=> s(gen_s:0':cons_minus:cons_cond:cons_min2_4(x)) The following defined symbols remain to be analysed: min, minus, cond, encArg They will be analysed ascendingly in the following order: minus = cond min < minus minus < encArg cond < encArg min < encArg ---------------------------------------- (21) RewriteLemmaProof (LOWER BOUND(ID)) Proved the following rewrite lemma: min(gen_s:0':cons_minus:cons_cond:cons_min2_4(n4_4), gen_s:0':cons_minus:cons_cond:cons_min2_4(n4_4)) -> gen_s:0':cons_minus:cons_cond:cons_min2_4(n4_4), rt in Omega(1 + n4_4) Induction Base: min(gen_s:0':cons_minus:cons_cond:cons_min2_4(0), gen_s:0':cons_minus:cons_cond:cons_min2_4(0)) ->_R^Omega(1) 0' Induction Step: min(gen_s:0':cons_minus:cons_cond:cons_min2_4(+(n4_4, 1)), gen_s:0':cons_minus:cons_cond:cons_min2_4(+(n4_4, 1))) ->_R^Omega(1) s(min(gen_s:0':cons_minus:cons_cond:cons_min2_4(n4_4), gen_s:0':cons_minus:cons_cond:cons_min2_4(n4_4))) ->_IH s(gen_s:0':cons_minus:cons_cond:cons_min2_4(c5_4)) We have rt in Omega(n^1) and sz in O(n). Thus, we have irc_R in Omega(n). ---------------------------------------- (22) Complex Obligation (BEST) ---------------------------------------- (23) Obligation: Proved the lower bound n^1 for the following obligation: Innermost TRS: Rules: minus(x, y) -> cond(min(x, y), x, y) cond(y, x, y) -> s(minus(x, s(y))) min(0', v) -> 0' min(u, 0') -> 0' min(s(u), s(v)) -> s(min(u, v)) encArg(s(x_1)) -> s(encArg(x_1)) encArg(0') -> 0' encArg(cons_minus(x_1, x_2)) -> minus(encArg(x_1), encArg(x_2)) encArg(cons_cond(x_1, x_2, x_3)) -> cond(encArg(x_1), encArg(x_2), encArg(x_3)) encArg(cons_min(x_1, x_2)) -> min(encArg(x_1), encArg(x_2)) encode_minus(x_1, x_2) -> minus(encArg(x_1), encArg(x_2)) encode_cond(x_1, x_2, x_3) -> cond(encArg(x_1), encArg(x_2), encArg(x_3)) encode_min(x_1, x_2) -> min(encArg(x_1), encArg(x_2)) encode_s(x_1) -> s(encArg(x_1)) encode_0 -> 0' Types: minus :: s:0':cons_minus:cons_cond:cons_min -> s:0':cons_minus:cons_cond:cons_min -> s:0':cons_minus:cons_cond:cons_min cond :: s:0':cons_minus:cons_cond:cons_min -> s:0':cons_minus:cons_cond:cons_min -> s:0':cons_minus:cons_cond:cons_min -> s:0':cons_minus:cons_cond:cons_min min :: s:0':cons_minus:cons_cond:cons_min -> s:0':cons_minus:cons_cond:cons_min -> s:0':cons_minus:cons_cond:cons_min s :: s:0':cons_minus:cons_cond:cons_min -> s:0':cons_minus:cons_cond:cons_min 0' :: s:0':cons_minus:cons_cond:cons_min encArg :: s:0':cons_minus:cons_cond:cons_min -> s:0':cons_minus:cons_cond:cons_min cons_minus :: s:0':cons_minus:cons_cond:cons_min -> s:0':cons_minus:cons_cond:cons_min -> s:0':cons_minus:cons_cond:cons_min cons_cond :: s:0':cons_minus:cons_cond:cons_min -> s:0':cons_minus:cons_cond:cons_min -> s:0':cons_minus:cons_cond:cons_min -> s:0':cons_minus:cons_cond:cons_min cons_min :: s:0':cons_minus:cons_cond:cons_min -> s:0':cons_minus:cons_cond:cons_min -> s:0':cons_minus:cons_cond:cons_min encode_minus :: s:0':cons_minus:cons_cond:cons_min -> s:0':cons_minus:cons_cond:cons_min -> s:0':cons_minus:cons_cond:cons_min encode_cond :: s:0':cons_minus:cons_cond:cons_min -> s:0':cons_minus:cons_cond:cons_min -> s:0':cons_minus:cons_cond:cons_min -> s:0':cons_minus:cons_cond:cons_min encode_min :: s:0':cons_minus:cons_cond:cons_min -> s:0':cons_minus:cons_cond:cons_min -> s:0':cons_minus:cons_cond:cons_min encode_s :: s:0':cons_minus:cons_cond:cons_min -> s:0':cons_minus:cons_cond:cons_min encode_0 :: s:0':cons_minus:cons_cond:cons_min hole_s:0':cons_minus:cons_cond:cons_min1_4 :: s:0':cons_minus:cons_cond:cons_min gen_s:0':cons_minus:cons_cond:cons_min2_4 :: Nat -> s:0':cons_minus:cons_cond:cons_min Generator Equations: gen_s:0':cons_minus:cons_cond:cons_min2_4(0) <=> 0' gen_s:0':cons_minus:cons_cond:cons_min2_4(+(x, 1)) <=> s(gen_s:0':cons_minus:cons_cond:cons_min2_4(x)) The following defined symbols remain to be analysed: min, minus, cond, encArg They will be analysed ascendingly in the following order: minus = cond min < minus minus < encArg cond < encArg min < encArg ---------------------------------------- (24) LowerBoundPropagationProof (FINISHED) Propagated lower bound. ---------------------------------------- (25) BOUNDS(n^1, INF) ---------------------------------------- (26) Obligation: Innermost TRS: Rules: minus(x, y) -> cond(min(x, y), x, y) cond(y, x, y) -> s(minus(x, s(y))) min(0', v) -> 0' min(u, 0') -> 0' min(s(u), s(v)) -> s(min(u, v)) encArg(s(x_1)) -> s(encArg(x_1)) encArg(0') -> 0' encArg(cons_minus(x_1, x_2)) -> minus(encArg(x_1), encArg(x_2)) encArg(cons_cond(x_1, x_2, x_3)) -> cond(encArg(x_1), encArg(x_2), encArg(x_3)) encArg(cons_min(x_1, x_2)) -> min(encArg(x_1), encArg(x_2)) encode_minus(x_1, x_2) -> minus(encArg(x_1), encArg(x_2)) encode_cond(x_1, x_2, x_3) -> cond(encArg(x_1), encArg(x_2), encArg(x_3)) encode_min(x_1, x_2) -> min(encArg(x_1), encArg(x_2)) encode_s(x_1) -> s(encArg(x_1)) encode_0 -> 0' Types: minus :: s:0':cons_minus:cons_cond:cons_min -> s:0':cons_minus:cons_cond:cons_min -> s:0':cons_minus:cons_cond:cons_min cond :: s:0':cons_minus:cons_cond:cons_min -> s:0':cons_minus:cons_cond:cons_min -> s:0':cons_minus:cons_cond:cons_min -> s:0':cons_minus:cons_cond:cons_min min :: s:0':cons_minus:cons_cond:cons_min -> s:0':cons_minus:cons_cond:cons_min -> s:0':cons_minus:cons_cond:cons_min s :: s:0':cons_minus:cons_cond:cons_min -> s:0':cons_minus:cons_cond:cons_min 0' :: s:0':cons_minus:cons_cond:cons_min encArg :: s:0':cons_minus:cons_cond:cons_min -> s:0':cons_minus:cons_cond:cons_min cons_minus :: s:0':cons_minus:cons_cond:cons_min -> s:0':cons_minus:cons_cond:cons_min -> s:0':cons_minus:cons_cond:cons_min cons_cond :: s:0':cons_minus:cons_cond:cons_min -> s:0':cons_minus:cons_cond:cons_min -> s:0':cons_minus:cons_cond:cons_min -> s:0':cons_minus:cons_cond:cons_min cons_min :: s:0':cons_minus:cons_cond:cons_min -> s:0':cons_minus:cons_cond:cons_min -> s:0':cons_minus:cons_cond:cons_min encode_minus :: s:0':cons_minus:cons_cond:cons_min -> s:0':cons_minus:cons_cond:cons_min -> s:0':cons_minus:cons_cond:cons_min encode_cond :: s:0':cons_minus:cons_cond:cons_min -> s:0':cons_minus:cons_cond:cons_min -> s:0':cons_minus:cons_cond:cons_min -> s:0':cons_minus:cons_cond:cons_min encode_min :: s:0':cons_minus:cons_cond:cons_min -> s:0':cons_minus:cons_cond:cons_min -> s:0':cons_minus:cons_cond:cons_min encode_s :: s:0':cons_minus:cons_cond:cons_min -> s:0':cons_minus:cons_cond:cons_min encode_0 :: s:0':cons_minus:cons_cond:cons_min hole_s:0':cons_minus:cons_cond:cons_min1_4 :: s:0':cons_minus:cons_cond:cons_min gen_s:0':cons_minus:cons_cond:cons_min2_4 :: Nat -> s:0':cons_minus:cons_cond:cons_min Lemmas: min(gen_s:0':cons_minus:cons_cond:cons_min2_4(n4_4), gen_s:0':cons_minus:cons_cond:cons_min2_4(n4_4)) -> gen_s:0':cons_minus:cons_cond:cons_min2_4(n4_4), rt in Omega(1 + n4_4) Generator Equations: gen_s:0':cons_minus:cons_cond:cons_min2_4(0) <=> 0' gen_s:0':cons_minus:cons_cond:cons_min2_4(+(x, 1)) <=> s(gen_s:0':cons_minus:cons_cond:cons_min2_4(x)) The following defined symbols remain to be analysed: cond, minus, encArg They will be analysed ascendingly in the following order: minus = cond minus < encArg cond < encArg ---------------------------------------- (27) RewriteLemmaProof (LOWER BOUND(ID)) Proved the following rewrite lemma: encArg(gen_s:0':cons_minus:cons_cond:cons_min2_4(n10256_4)) -> gen_s:0':cons_minus:cons_cond:cons_min2_4(n10256_4), rt in Omega(0) Induction Base: encArg(gen_s:0':cons_minus:cons_cond:cons_min2_4(0)) ->_R^Omega(0) 0' Induction Step: encArg(gen_s:0':cons_minus:cons_cond:cons_min2_4(+(n10256_4, 1))) ->_R^Omega(0) s(encArg(gen_s:0':cons_minus:cons_cond:cons_min2_4(n10256_4))) ->_IH s(gen_s:0':cons_minus:cons_cond:cons_min2_4(c10257_4)) We have rt in Omega(1) and sz in O(n). Thus, we have irc_R in Omega(n^0). ---------------------------------------- (28) BOUNDS(1, INF)