/export/starexec/sandbox/solver/bin/starexec_run_rcdcRelativeAlsoLower /export/starexec/sandbox/benchmark/theBenchmark.xml /export/starexec/sandbox/output/output_files -------------------------------------------------------------------------------- WORST_CASE(Omega(n^1), O(n^3)) 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(n^1, n^3). (0) DCpxTrs (1) DerivationalComplexityToRuntimeComplexityProof [BOTH BOUNDS(ID, ID), 0 ms] (2) CpxRelTRS (3) SInnermostTerminationProof [BOTH CONCRETE BOUNDS(ID, ID), 190 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), 0 ms] (12) CpxRNTS (13) CompleteCoflocoProof [FINISHED, 7489 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), 548 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), 48 ms] (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: f(true, x, y) -> f(gt(x, y), s(x), s(s(y))) gt(0, v) -> false gt(s(u), 0) -> true gt(s(u), s(v)) -> gt(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(true) -> true encArg(s(x_1)) -> s(encArg(x_1)) encArg(0) -> 0 encArg(false) -> false encArg(cons_f(x_1, x_2, x_3)) -> f(encArg(x_1), encArg(x_2), encArg(x_3)) encArg(cons_gt(x_1, x_2)) -> gt(encArg(x_1), encArg(x_2)) encode_f(x_1, x_2, x_3) -> f(encArg(x_1), encArg(x_2), encArg(x_3)) encode_true -> true encode_gt(x_1, x_2) -> gt(encArg(x_1), encArg(x_2)) encode_s(x_1) -> s(encArg(x_1)) encode_0 -> 0 encode_false -> false ---------------------------------------- (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: f(true, x, y) -> f(gt(x, y), s(x), s(s(y))) gt(0, v) -> false gt(s(u), 0) -> true gt(s(u), s(v)) -> gt(u, v) The (relative) TRS S consists of the following rules: encArg(true) -> true encArg(s(x_1)) -> s(encArg(x_1)) encArg(0) -> 0 encArg(false) -> false encArg(cons_f(x_1, x_2, x_3)) -> f(encArg(x_1), encArg(x_2), encArg(x_3)) encArg(cons_gt(x_1, x_2)) -> gt(encArg(x_1), encArg(x_2)) encode_f(x_1, x_2, x_3) -> f(encArg(x_1), encArg(x_2), encArg(x_3)) encode_true -> true encode_gt(x_1, x_2) -> gt(encArg(x_1), encArg(x_2)) encode_s(x_1) -> s(encArg(x_1)) encode_0 -> 0 encode_false -> false 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: f(true, x, y) -> f(gt(x, y), s(x), s(s(y))) gt(0, v) -> false gt(s(u), 0) -> true gt(s(u), s(v)) -> gt(u, v) The (relative) TRS S consists of the following rules: encArg(true) -> true encArg(s(x_1)) -> s(encArg(x_1)) encArg(0) -> 0 encArg(false) -> false encArg(cons_f(x_1, x_2, x_3)) -> f(encArg(x_1), encArg(x_2), encArg(x_3)) encArg(cons_gt(x_1, x_2)) -> gt(encArg(x_1), encArg(x_2)) encode_f(x_1, x_2, x_3) -> f(encArg(x_1), encArg(x_2), encArg(x_3)) encode_true -> true encode_gt(x_1, x_2) -> gt(encArg(x_1), encArg(x_2)) encode_s(x_1) -> s(encArg(x_1)) encode_0 -> 0 encode_false -> false 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: f(true, x, y) -> f(gt(x, y), s(x), s(s(y))) [1] gt(0, v) -> false [1] gt(s(u), 0) -> true [1] gt(s(u), s(v)) -> gt(u, v) [1] encArg(true) -> true [0] encArg(s(x_1)) -> s(encArg(x_1)) [0] encArg(0) -> 0 [0] encArg(false) -> false [0] encArg(cons_f(x_1, x_2, x_3)) -> f(encArg(x_1), encArg(x_2), encArg(x_3)) [0] encArg(cons_gt(x_1, x_2)) -> gt(encArg(x_1), encArg(x_2)) [0] encode_f(x_1, x_2, x_3) -> f(encArg(x_1), encArg(x_2), encArg(x_3)) [0] encode_true -> true [0] encode_gt(x_1, x_2) -> gt(encArg(x_1), encArg(x_2)) [0] encode_s(x_1) -> s(encArg(x_1)) [0] encode_0 -> 0 [0] encode_false -> false [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(true, x, y) -> f(gt(x, y), s(x), s(s(y))) [1] gt(0, v) -> false [1] gt(s(u), 0) -> true [1] gt(s(u), s(v)) -> gt(u, v) [1] encArg(true) -> true [0] encArg(s(x_1)) -> s(encArg(x_1)) [0] encArg(0) -> 0 [0] encArg(false) -> false [0] encArg(cons_f(x_1, x_2, x_3)) -> f(encArg(x_1), encArg(x_2), encArg(x_3)) [0] encArg(cons_gt(x_1, x_2)) -> gt(encArg(x_1), encArg(x_2)) [0] encode_f(x_1, x_2, x_3) -> f(encArg(x_1), encArg(x_2), encArg(x_3)) [0] encode_true -> true [0] encode_gt(x_1, x_2) -> gt(encArg(x_1), encArg(x_2)) [0] encode_s(x_1) -> s(encArg(x_1)) [0] encode_0 -> 0 [0] encode_false -> false [0] The TRS has the following type information: f :: true:s:0:false:cons_f:cons_gt -> true:s:0:false:cons_f:cons_gt -> true:s:0:false:cons_f:cons_gt -> true:s:0:false:cons_f:cons_gt true :: true:s:0:false:cons_f:cons_gt gt :: true:s:0:false:cons_f:cons_gt -> true:s:0:false:cons_f:cons_gt -> true:s:0:false:cons_f:cons_gt s :: true:s:0:false:cons_f:cons_gt -> true:s:0:false:cons_f:cons_gt 0 :: true:s:0:false:cons_f:cons_gt false :: true:s:0:false:cons_f:cons_gt encArg :: true:s:0:false:cons_f:cons_gt -> true:s:0:false:cons_f:cons_gt cons_f :: true:s:0:false:cons_f:cons_gt -> true:s:0:false:cons_f:cons_gt -> true:s:0:false:cons_f:cons_gt -> true:s:0:false:cons_f:cons_gt cons_gt :: true:s:0:false:cons_f:cons_gt -> true:s:0:false:cons_f:cons_gt -> true:s:0:false:cons_f:cons_gt encode_f :: true:s:0:false:cons_f:cons_gt -> true:s:0:false:cons_f:cons_gt -> true:s:0:false:cons_f:cons_gt -> true:s:0:false:cons_f:cons_gt encode_true :: true:s:0:false:cons_f:cons_gt encode_gt :: true:s:0:false:cons_f:cons_gt -> true:s:0:false:cons_f:cons_gt -> true:s:0:false:cons_f:cons_gt encode_s :: true:s:0:false:cons_f:cons_gt -> true:s:0:false:cons_f:cons_gt encode_0 :: true:s:0:false:cons_f:cons_gt encode_false :: true:s:0:false:cons_f:cons_gt 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_f(v0, v1, v2) -> null_encode_f [0] encode_true -> null_encode_true [0] encode_gt(v0, v1) -> null_encode_gt [0] encode_s(v0) -> null_encode_s [0] encode_0 -> null_encode_0 [0] encode_false -> null_encode_false [0] f(v0, v1, v2) -> null_f [0] gt(v0, v1) -> null_gt [0] And the following fresh constants: null_encArg, null_encode_f, null_encode_true, null_encode_gt, null_encode_s, null_encode_0, null_encode_false, null_f, null_gt ---------------------------------------- (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: f(true, x, y) -> f(gt(x, y), s(x), s(s(y))) [1] gt(0, v) -> false [1] gt(s(u), 0) -> true [1] gt(s(u), s(v)) -> gt(u, v) [1] encArg(true) -> true [0] encArg(s(x_1)) -> s(encArg(x_1)) [0] encArg(0) -> 0 [0] encArg(false) -> false [0] encArg(cons_f(x_1, x_2, x_3)) -> f(encArg(x_1), encArg(x_2), encArg(x_3)) [0] encArg(cons_gt(x_1, x_2)) -> gt(encArg(x_1), encArg(x_2)) [0] encode_f(x_1, x_2, x_3) -> f(encArg(x_1), encArg(x_2), encArg(x_3)) [0] encode_true -> true [0] encode_gt(x_1, x_2) -> gt(encArg(x_1), encArg(x_2)) [0] encode_s(x_1) -> s(encArg(x_1)) [0] encode_0 -> 0 [0] encode_false -> false [0] encArg(v0) -> null_encArg [0] encode_f(v0, v1, v2) -> null_encode_f [0] encode_true -> null_encode_true [0] encode_gt(v0, v1) -> null_encode_gt [0] encode_s(v0) -> null_encode_s [0] encode_0 -> null_encode_0 [0] encode_false -> null_encode_false [0] f(v0, v1, v2) -> null_f [0] gt(v0, v1) -> null_gt [0] The TRS has the following type information: f :: true:s:0:false:cons_f:cons_gt:null_encArg:null_encode_f:null_encode_true:null_encode_gt:null_encode_s:null_encode_0:null_encode_false:null_f:null_gt -> true:s:0:false:cons_f:cons_gt:null_encArg:null_encode_f:null_encode_true:null_encode_gt:null_encode_s:null_encode_0:null_encode_false:null_f:null_gt -> true:s:0:false:cons_f:cons_gt:null_encArg:null_encode_f:null_encode_true:null_encode_gt:null_encode_s:null_encode_0:null_encode_false:null_f:null_gt -> true:s:0:false:cons_f:cons_gt:null_encArg:null_encode_f:null_encode_true:null_encode_gt:null_encode_s:null_encode_0:null_encode_false:null_f:null_gt true :: true:s:0:false:cons_f:cons_gt:null_encArg:null_encode_f:null_encode_true:null_encode_gt:null_encode_s:null_encode_0:null_encode_false:null_f:null_gt gt :: true:s:0:false:cons_f:cons_gt:null_encArg:null_encode_f:null_encode_true:null_encode_gt:null_encode_s:null_encode_0:null_encode_false:null_f:null_gt -> true:s:0:false:cons_f:cons_gt:null_encArg:null_encode_f:null_encode_true:null_encode_gt:null_encode_s:null_encode_0:null_encode_false:null_f:null_gt -> true:s:0:false:cons_f:cons_gt:null_encArg:null_encode_f:null_encode_true:null_encode_gt:null_encode_s:null_encode_0:null_encode_false:null_f:null_gt s :: true:s:0:false:cons_f:cons_gt:null_encArg:null_encode_f:null_encode_true:null_encode_gt:null_encode_s:null_encode_0:null_encode_false:null_f:null_gt -> true:s:0:false:cons_f:cons_gt:null_encArg:null_encode_f:null_encode_true:null_encode_gt:null_encode_s:null_encode_0:null_encode_false:null_f:null_gt 0 :: true:s:0:false:cons_f:cons_gt:null_encArg:null_encode_f:null_encode_true:null_encode_gt:null_encode_s:null_encode_0:null_encode_false:null_f:null_gt false :: true:s:0:false:cons_f:cons_gt:null_encArg:null_encode_f:null_encode_true:null_encode_gt:null_encode_s:null_encode_0:null_encode_false:null_f:null_gt encArg :: true:s:0:false:cons_f:cons_gt:null_encArg:null_encode_f:null_encode_true:null_encode_gt:null_encode_s:null_encode_0:null_encode_false:null_f:null_gt -> true:s:0:false:cons_f:cons_gt:null_encArg:null_encode_f:null_encode_true:null_encode_gt:null_encode_s:null_encode_0:null_encode_false:null_f:null_gt cons_f :: true:s:0:false:cons_f:cons_gt:null_encArg:null_encode_f:null_encode_true:null_encode_gt:null_encode_s:null_encode_0:null_encode_false:null_f:null_gt -> true:s:0:false:cons_f:cons_gt:null_encArg:null_encode_f:null_encode_true:null_encode_gt:null_encode_s:null_encode_0:null_encode_false:null_f:null_gt -> true:s:0:false:cons_f:cons_gt:null_encArg:null_encode_f:null_encode_true:null_encode_gt:null_encode_s:null_encode_0:null_encode_false:null_f:null_gt -> true:s:0:false:cons_f:cons_gt:null_encArg:null_encode_f:null_encode_true:null_encode_gt:null_encode_s:null_encode_0:null_encode_false:null_f:null_gt cons_gt :: true:s:0:false:cons_f:cons_gt:null_encArg:null_encode_f:null_encode_true:null_encode_gt:null_encode_s:null_encode_0:null_encode_false:null_f:null_gt -> true:s:0:false:cons_f:cons_gt:null_encArg:null_encode_f:null_encode_true:null_encode_gt:null_encode_s:null_encode_0:null_encode_false:null_f:null_gt -> true:s:0:false:cons_f:cons_gt:null_encArg:null_encode_f:null_encode_true:null_encode_gt:null_encode_s:null_encode_0:null_encode_false:null_f:null_gt encode_f :: true:s:0:false:cons_f:cons_gt:null_encArg:null_encode_f:null_encode_true:null_encode_gt:null_encode_s:null_encode_0:null_encode_false:null_f:null_gt -> true:s:0:false:cons_f:cons_gt:null_encArg:null_encode_f:null_encode_true:null_encode_gt:null_encode_s:null_encode_0:null_encode_false:null_f:null_gt -> true:s:0:false:cons_f:cons_gt:null_encArg:null_encode_f:null_encode_true:null_encode_gt:null_encode_s:null_encode_0:null_encode_false:null_f:null_gt -> true:s:0:false:cons_f:cons_gt:null_encArg:null_encode_f:null_encode_true:null_encode_gt:null_encode_s:null_encode_0:null_encode_false:null_f:null_gt encode_true :: true:s:0:false:cons_f:cons_gt:null_encArg:null_encode_f:null_encode_true:null_encode_gt:null_encode_s:null_encode_0:null_encode_false:null_f:null_gt encode_gt :: true:s:0:false:cons_f:cons_gt:null_encArg:null_encode_f:null_encode_true:null_encode_gt:null_encode_s:null_encode_0:null_encode_false:null_f:null_gt -> true:s:0:false:cons_f:cons_gt:null_encArg:null_encode_f:null_encode_true:null_encode_gt:null_encode_s:null_encode_0:null_encode_false:null_f:null_gt -> true:s:0:false:cons_f:cons_gt:null_encArg:null_encode_f:null_encode_true:null_encode_gt:null_encode_s:null_encode_0:null_encode_false:null_f:null_gt encode_s :: true:s:0:false:cons_f:cons_gt:null_encArg:null_encode_f:null_encode_true:null_encode_gt:null_encode_s:null_encode_0:null_encode_false:null_f:null_gt -> true:s:0:false:cons_f:cons_gt:null_encArg:null_encode_f:null_encode_true:null_encode_gt:null_encode_s:null_encode_0:null_encode_false:null_f:null_gt encode_0 :: true:s:0:false:cons_f:cons_gt:null_encArg:null_encode_f:null_encode_true:null_encode_gt:null_encode_s:null_encode_0:null_encode_false:null_f:null_gt encode_false :: true:s:0:false:cons_f:cons_gt:null_encArg:null_encode_f:null_encode_true:null_encode_gt:null_encode_s:null_encode_0:null_encode_false:null_f:null_gt null_encArg :: true:s:0:false:cons_f:cons_gt:null_encArg:null_encode_f:null_encode_true:null_encode_gt:null_encode_s:null_encode_0:null_encode_false:null_f:null_gt null_encode_f :: true:s:0:false:cons_f:cons_gt:null_encArg:null_encode_f:null_encode_true:null_encode_gt:null_encode_s:null_encode_0:null_encode_false:null_f:null_gt null_encode_true :: true:s:0:false:cons_f:cons_gt:null_encArg:null_encode_f:null_encode_true:null_encode_gt:null_encode_s:null_encode_0:null_encode_false:null_f:null_gt null_encode_gt :: true:s:0:false:cons_f:cons_gt:null_encArg:null_encode_f:null_encode_true:null_encode_gt:null_encode_s:null_encode_0:null_encode_false:null_f:null_gt null_encode_s :: true:s:0:false:cons_f:cons_gt:null_encArg:null_encode_f:null_encode_true:null_encode_gt:null_encode_s:null_encode_0:null_encode_false:null_f:null_gt null_encode_0 :: true:s:0:false:cons_f:cons_gt:null_encArg:null_encode_f:null_encode_true:null_encode_gt:null_encode_s:null_encode_0:null_encode_false:null_f:null_gt null_encode_false :: true:s:0:false:cons_f:cons_gt:null_encArg:null_encode_f:null_encode_true:null_encode_gt:null_encode_s:null_encode_0:null_encode_false:null_f:null_gt null_f :: true:s:0:false:cons_f:cons_gt:null_encArg:null_encode_f:null_encode_true:null_encode_gt:null_encode_s:null_encode_0:null_encode_false:null_f:null_gt null_gt :: true:s:0:false:cons_f:cons_gt:null_encArg:null_encode_f:null_encode_true:null_encode_gt:null_encode_s:null_encode_0:null_encode_false:null_f:null_gt 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: true => 2 0 => 0 false => 1 null_encArg => 0 null_encode_f => 0 null_encode_true => 0 null_encode_gt => 0 null_encode_s => 0 null_encode_0 => 0 null_encode_false => 0 null_f => 0 null_gt => 0 ---------------------------------------- (12) Obligation: Complexity RNTS consisting of the following rules: encArg(z) -{ 0 }-> gt(encArg(x_1), encArg(x_2)) :|: x_1 >= 0, z = 1 + x_1 + x_2, x_2 >= 0 encArg(z) -{ 0 }-> f(encArg(x_1), encArg(x_2), encArg(x_3)) :|: x_1 >= 0, z = 1 + x_1 + x_2 + x_3, x_3 >= 0, x_2 >= 0 encArg(z) -{ 0 }-> 2 :|: z = 2 encArg(z) -{ 0 }-> 1 :|: z = 1 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_f(z, z', z'') -{ 0 }-> f(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_f(z, z', z'') -{ 0 }-> 0 :|: v0 >= 0, z'' = v2, v1 >= 0, z = v0, z' = v1, v2 >= 0 encode_false -{ 0 }-> 1 :|: encode_false -{ 0 }-> 0 :|: encode_gt(z, z') -{ 0 }-> gt(encArg(x_1), encArg(x_2)) :|: x_1 >= 0, x_2 >= 0, z = x_1, z' = x_2 encode_gt(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 encode_true -{ 0 }-> 2 :|: encode_true -{ 0 }-> 0 :|: f(z, z', z'') -{ 1 }-> f(gt(x, y), 1 + x, 1 + (1 + y)) :|: z = 2, z' = x, z'' = y, x >= 0, y >= 0 f(z, z', z'') -{ 0 }-> 0 :|: v0 >= 0, z'' = v2, v1 >= 0, z = v0, z' = v1, v2 >= 0 gt(z, z') -{ 1 }-> gt(u, v) :|: v >= 0, z' = 1 + v, z = 1 + u, u >= 0 gt(z, z') -{ 1 }-> 2 :|: z = 1 + u, z' = 0, u >= 0 gt(z, z') -{ 1 }-> 1 :|: v >= 0, z' = v, z = 0 gt(z, z') -{ 0 }-> 0 :|: v0 >= 0, v1 >= 0, z = v0, z' = v1 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, V2),0,[f(V1, V, V2, Out)],[V1 >= 0,V >= 0,V2 >= 0]). eq(start(V1, V, V2),0,[gt(V1, V, Out)],[V1 >= 0,V >= 0]). eq(start(V1, V, V2),0,[encArg(V1, Out)],[V1 >= 0]). eq(start(V1, V, V2),0,[fun(V1, V, V2, Out)],[V1 >= 0,V >= 0,V2 >= 0]). eq(start(V1, V, V2),0,[fun1(Out)],[]). eq(start(V1, V, V2),0,[fun2(V1, V, Out)],[V1 >= 0,V >= 0]). eq(start(V1, V, V2),0,[fun3(V1, Out)],[V1 >= 0]). eq(start(V1, V, V2),0,[fun4(Out)],[]). eq(start(V1, V, V2),0,[fun5(Out)],[]). eq(f(V1, V, V2, Out),1,[gt(V4, V3, Ret0),f(Ret0, 1 + V4, 1 + (1 + V3), Ret)],[Out = Ret,V1 = 2,V = V4,V2 = V3,V4 >= 0,V3 >= 0]). eq(gt(V1, V, Out),1,[],[Out = 1,V5 >= 0,V = V5,V1 = 0]). eq(gt(V1, V, Out),1,[],[Out = 2,V1 = 1 + V6,V = 0,V6 >= 0]). eq(gt(V1, V, Out),1,[gt(V7, V8, Ret1)],[Out = Ret1,V8 >= 0,V = 1 + V8,V1 = 1 + V7,V7 >= 0]). eq(encArg(V1, Out),0,[],[Out = 2,V1 = 2]). eq(encArg(V1, Out),0,[encArg(V9, Ret11)],[Out = 1 + Ret11,V1 = 1 + V9,V9 >= 0]). eq(encArg(V1, Out),0,[],[Out = 0,V1 = 0]). eq(encArg(V1, Out),0,[],[Out = 1,V1 = 1]). eq(encArg(V1, Out),0,[encArg(V11, Ret01),encArg(V12, Ret12),encArg(V10, Ret2),f(Ret01, Ret12, Ret2, Ret3)],[Out = Ret3,V11 >= 0,V1 = 1 + V10 + V11 + V12,V10 >= 0,V12 >= 0]). eq(encArg(V1, Out),0,[encArg(V13, Ret02),encArg(V14, Ret13),gt(Ret02, Ret13, Ret4)],[Out = Ret4,V13 >= 0,V1 = 1 + V13 + V14,V14 >= 0]). eq(fun(V1, V, V2, Out),0,[encArg(V17, Ret03),encArg(V15, Ret14),encArg(V16, Ret21),f(Ret03, Ret14, Ret21, Ret5)],[Out = Ret5,V17 >= 0,V16 >= 0,V15 >= 0,V1 = V17,V = V15,V2 = V16]). eq(fun1(Out),0,[],[Out = 2]). eq(fun2(V1, V, Out),0,[encArg(V19, Ret04),encArg(V18, Ret15),gt(Ret04, Ret15, Ret6)],[Out = Ret6,V19 >= 0,V18 >= 0,V1 = V19,V = V18]). eq(fun3(V1, Out),0,[encArg(V20, Ret16)],[Out = 1 + Ret16,V20 >= 0,V1 = V20]). eq(fun4(Out),0,[],[Out = 0]). eq(fun5(Out),0,[],[Out = 1]). eq(encArg(V1, Out),0,[],[Out = 0,V21 >= 0,V1 = V21]). eq(fun(V1, V, V2, Out),0,[],[Out = 0,V23 >= 0,V2 = V24,V22 >= 0,V1 = V23,V = V22,V24 >= 0]). eq(fun1(Out),0,[],[Out = 0]). eq(fun2(V1, V, Out),0,[],[Out = 0,V26 >= 0,V25 >= 0,V1 = V26,V = V25]). eq(fun3(V1, Out),0,[],[Out = 0,V27 >= 0,V1 = V27]). eq(fun5(Out),0,[],[Out = 0]). eq(f(V1, V, V2, Out),0,[],[Out = 0,V28 >= 0,V2 = V29,V30 >= 0,V1 = V28,V = V30,V29 >= 0]). eq(gt(V1, V, Out),0,[],[Out = 0,V31 >= 0,V32 >= 0,V1 = V31,V = V32]). input_output_vars(f(V1,V,V2,Out),[V1,V,V2],[Out]). input_output_vars(gt(V1,V,Out),[V1,V],[Out]). input_output_vars(encArg(V1,Out),[V1],[Out]). input_output_vars(fun(V1,V,V2,Out),[V1,V,V2],[Out]). input_output_vars(fun1(Out),[],[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]). input_output_vars(fun5(Out),[],[Out]). CoFloCo proof output: Preprocessing Cost Relations ===================================== #### Computed strongly connected components 0. recursive : [gt/3] 1. recursive : [f/4] 2. recursive [non_tail,multiple] : [encArg/2] 3. non_recursive : [fun/4] 4. non_recursive : [fun1/1] 5. non_recursive : [fun2/3] 6. non_recursive : [fun3/2] 7. non_recursive : [fun4/1] 8. non_recursive : [fun5/1] 9. non_recursive : [start/3] #### Obtained direct recursion through partial evaluation 0. SCC is partially evaluated into gt/3 1. SCC is partially evaluated into f/4 2. SCC is partially evaluated into encArg/2 3. SCC is partially evaluated into fun/4 4. SCC is partially evaluated into fun1/1 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 fun5/1 9. SCC is partially evaluated into start/3 Control-Flow Refinement of Cost Relations ===================================== ### Specialization of cost equations gt/3 * CE 15 is refined into CE [32] * CE 13 is refined into CE [33] * CE 12 is refined into CE [34] * CE 14 is refined into CE [35] ### Cost equations --> "Loop" of gt/3 * CEs [35] --> Loop 21 * CEs [32] --> Loop 22 * CEs [33] --> Loop 23 * CEs [34] --> Loop 24 ### Ranking functions of CR gt(V1,V,Out) * RF of phase [21]: [V,V1] #### Partial ranking functions of CR gt(V1,V,Out) * Partial RF of phase [21]: - RF of loop [21:1]: V V1 ### Specialization of cost equations f/4 * CE 11 is refined into CE [36] * CE 10 is refined into CE [37,38,39,40,41] ### Cost equations --> "Loop" of f/4 * CEs [41] --> Loop 25 * CEs [40] --> Loop 26 * CEs [39] --> Loop 27 * CEs [38] --> Loop 28 * CEs [37] --> Loop 29 * CEs [36] --> Loop 30 ### Ranking functions of CR f(V1,V,V2,Out) * RF of phase [25]: [V-V2] #### Partial ranking functions of CR f(V1,V,V2,Out) * Partial RF of phase [25]: - RF of loop [25:1]: V-V2 ### Specialization of cost equations encArg/2 * CE 18 is refined into CE [42] * CE 16 is refined into CE [43] * CE 19 is refined into CE [44] * CE 21 is refined into CE [45,46,47,48,49] * CE 20 is refined into CE [50,51] * CE 17 is refined into CE [52] ### Cost equations --> "Loop" of encArg/2 * CEs [52] --> Loop 31 * CEs [50,51] --> Loop 32 * CEs [49] --> Loop 33 * CEs [46] --> Loop 34 * CEs [48] --> Loop 35 * CEs [45] --> Loop 36 * CEs [47] --> Loop 37 * CEs [42] --> Loop 38 * CEs [43] --> Loop 39 * CEs [44] --> Loop 40 ### Ranking functions of CR encArg(V1,Out) * RF of phase [31,32,33,34,35,36,37]: [V1] #### Partial ranking functions of CR encArg(V1,Out) * Partial RF of phase [31,32,33,34,35,36,37]: - RF of loop [31:1,32:1,32:2,32:3,33:1,33:2,34:1,34:2,35:1,35:2,36:1,36:2,37:1,37:2]: V1 ### Specialization of cost equations fun/4 * CE 22 is refined into CE [53,54,55,56,57,58,59,60,61,62,63,64,65,66,67,68,69,70,71,72,73,74,75,76,77,78,79,80,81,82,83,84,85,86,87] * CE 23 is refined into CE [88] ### Cost equations --> "Loop" of fun/4 * CEs [58,59,60,61,62,82,83,84] --> Loop 41 * CEs [55,64,68,77,80,86] --> Loop 42 * CEs [53,54,56,57,63,65,66,67,69,70,71,72,73,74,75,76,78,79,81,85,87,88] --> Loop 43 ### Ranking functions of CR fun(V1,V,V2,Out) #### Partial ranking functions of CR fun(V1,V,V2,Out) ### Specialization of cost equations fun1/1 * CE 24 is refined into CE [89] * CE 25 is refined into CE [90] ### Cost equations --> "Loop" of fun1/1 * CEs [89] --> Loop 44 * CEs [90] --> Loop 45 ### Ranking functions of CR fun1(Out) #### Partial ranking functions of CR fun1(Out) ### Specialization of cost equations fun2/3 * CE 26 is refined into CE [91,92,93,94,95,96,97,98,99,100,101,102,103,104,105,106,107,108,109,110,111,112,113,114,115,116] * CE 27 is refined into CE [117] ### Cost equations --> "Loop" of fun2/3 * CEs [99] --> Loop 46 * CEs [96,98,113] --> Loop 47 * CEs [97,114] --> Loop 48 * CEs [92,95,101,103,106,109] --> Loop 49 * CEs [91,94,100,105,108,111,115] --> Loop 50 * CEs [93,102,104,107,110,112,116,117] --> Loop 51 ### Ranking functions of CR fun2(V1,V,Out) #### Partial ranking functions of CR fun2(V1,V,Out) ### Specialization of cost equations fun3/2 * CE 28 is refined into CE [118,119,120] * CE 29 is refined into CE [121] ### Cost equations --> "Loop" of fun3/2 * CEs [120] --> Loop 52 * CEs [121] --> Loop 53 * CEs [118,119] --> Loop 54 ### Ranking functions of CR fun3(V1,Out) #### Partial ranking functions of CR fun3(V1,Out) ### Specialization of cost equations fun5/1 * CE 30 is refined into CE [122] * CE 31 is refined into CE [123] ### Cost equations --> "Loop" of fun5/1 * CEs [122] --> Loop 55 * CEs [123] --> Loop 56 ### Ranking functions of CR fun5(Out) #### Partial ranking functions of CR fun5(Out) ### Specialization of cost equations start/3 * CE 1 is refined into CE [124,125] * CE 2 is refined into CE [126,127,128,129,130] * CE 3 is refined into CE [131,132,133] * CE 4 is refined into CE [134,135] * CE 5 is refined into CE [136,137] * CE 6 is refined into CE [138,139,140] * CE 7 is refined into CE [141,142,143] * CE 8 is refined into CE [144] * CE 9 is refined into CE [145,146] ### Cost equations --> "Loop" of start/3 * CEs [124,125,126,127,128,129,130,131,132,133,134,135,136,137,138,139,140,141,142,143,144,145,146] --> Loop 57 ### Ranking functions of CR start(V1,V,V2) #### Partial ranking functions of CR start(V1,V,V2) Computing Bounds ===================================== #### Cost of chains of gt(V1,V,Out): * Chain [[21],24]: 1*it(21)+1 Such that:it(21) =< V1 with precondition: [Out=1,V1>=1,V>=V1] * Chain [[21],23]: 1*it(21)+1 Such that:it(21) =< V with precondition: [Out=2,V>=1,V1>=V+1] * Chain [[21],22]: 1*it(21)+0 Such that:it(21) =< V with precondition: [Out=0,V1>=1,V>=1] * Chain [24]: 1 with precondition: [V1=0,Out=1,V>=0] * Chain [23]: 1 with precondition: [V=0,Out=2,V1>=1] * Chain [22]: 0 with precondition: [Out=0,V1>=0,V>=0] #### Cost of chains of f(V1,V,V2,Out): * Chain [[25],30]: 2*it(25)+1*s(4)+0 Such that:it(25) =< V-V2 aux(1) =< 2*V-V2 s(4) =< it(25)*aux(1) with precondition: [V1=2,Out=0,V2>=1,V>=V2+1] * Chain [[25],27,30]: 2*it(25)+1*s(4)+1*s(5)+1 Such that:it(25) =< V-V2 aux(1) =< 2*V-V2 s(5) =< 2*V-V2+2 s(4) =< it(25)*aux(1) with precondition: [V1=2,Out=0,V2>=1,V>=V2+1] * Chain [[25],26,30]: 2*it(25)+1*s(4)+1*s(6)+2 Such that:it(25) =< V-V2 aux(1) =< 2*V-V2 s(6) =< 2*V-V2+1 s(4) =< it(25)*aux(1) with precondition: [V1=2,Out=0,V2>=1,V>=V2+1] * Chain [30]: 0 with precondition: [Out=0,V1>=0,V>=0,V2>=0] * Chain [29,30]: 2 with precondition: [V1=2,V=0,Out=0,V2>=0] * Chain [28,[25],30]: 2*it(25)+1*s(4)+2 Such that:it(25) =< V aux(1) =< 2*V s(4) =< it(25)*aux(1) with precondition: [V1=2,V2=0,Out=0,V>=2] * Chain [28,[25],27,30]: 2*it(25)+1*s(4)+1*s(5)+3 Such that:it(25) =< V aux(1) =< 2*V s(5) =< 2*V+2 s(4) =< it(25)*aux(1) with precondition: [V1=2,V2=0,Out=0,V>=2] * Chain [28,[25],26,30]: 2*it(25)+1*s(4)+1*s(6)+4 Such that:it(25) =< V aux(1) =< 2*V s(6) =< 2*V+1 s(4) =< it(25)*aux(1) with precondition: [V1=2,V2=0,Out=0,V>=2] * Chain [28,30]: 2 with precondition: [V1=2,V2=0,Out=0,V>=1] * Chain [28,27,30]: 1*s(5)+3 Such that:s(5) =< 4 with precondition: [V1=2,V2=0,Out=0,V>=1] * Chain [28,26,30]: 1*s(6)+4 Such that:s(6) =< 3 with precondition: [V1=2,V=1,V2=0,Out=0] * Chain [27,30]: 1*s(5)+1 Such that:s(5) =< V2+2 with precondition: [V1=2,Out=0,V>=0,V2>=0] * Chain [26,30]: 1*s(6)+2 Such that:s(6) =< V+1 with precondition: [V1=2,Out=0,V>=1,V2>=V] #### Cost of chains of encArg(V1,Out): * Chain [40]: 0 with precondition: [V1=1,Out=1] * Chain [39]: 0 with precondition: [V1=2,Out=2] * Chain [38]: 0 with precondition: [Out=0,V1>=0] * Chain [multiple([31,32,33,34,35,36,37],[[40],[39],[38]])]: 5*it(32)+1*it(33)+1*it(34)+1*it(35)+1*s(67)+2*s(68)+2*s(69)+1*s(70)+12*s(71)+6*s(72)+1*s(73)+1*s(74)+1*s(78)+1*s(79)+1*s(80)+0 Such that:s(54) =< 2*V1 aux(30) =< V1 aux(31) =< V1/2 aux(32) =< 2/3*V1 aux(33) =< 2/5*V1 it(31) =< aux(30) it(32) =< aux(30) it(33) =< aux(30) it(34) =< aux(30) it(35) =< aux(30) it(35) =< aux(31) it(34) =< aux(32) it(35) =< aux(32) it(33) =< aux(33) aux(12) =< s(54)*(1/2) aux(21) =< s(54)*(1/2)-1 aux(18) =< s(54)*(1/2)-2 aux(16) =< s(54)*(1/2)+2 aux(14) =< s(54)+1 aux(13) =< s(54)*(1/2)+1 s(74) =< aux(30)*4 s(73) =< aux(30)*3 s(70) =< it(32)*aux(16) aux(15) =< it(32)*aux(13) s(77) =< it(32)*aux(14) s(67) =< it(32)*aux(13) s(75) =< it(32)*aux(12) s(76) =< aux(15)*2 s(80) =< it(31)*aux(12) s(79) =< it(35)*aux(21) s(78) =< it(33)*aux(18) s(68) =< s(77) s(69) =< s(76) s(71) =< s(75) s(72) =< s(71)*s(54) with precondition: [V1>=1,Out>=0,V1>=Out] #### Cost of chains of fun(V1,V,V2,Out): * Chain [43]: 30*s(117)+6*s(118)+6*s(119)+6*s(120)+6*s(127)+6*s(128)+6*s(129)+6*s(132)+6*s(135)+6*s(136)+6*s(137)+12*s(138)+12*s(139)+72*s(140)+36*s(141)+110*s(147)+10*s(148)+10*s(149)+10*s(150)+10*s(157)+10*s(158)+10*s(159)+10*s(162)+10*s(165)+10*s(166)+10*s(167)+20*s(168)+20*s(169)+120*s(170)+60*s(171)+50*s(177)+10*s(178)+10*s(179)+10*s(180)+10*s(187)+10*s(188)+10*s(189)+10*s(192)+10*s(195)+10*s(196)+10*s(197)+20*s(198)+20*s(199)+120*s(200)+60*s(201)+6*s(202)+10*s(203)+10*s(204)+7*s(205)+30*s(209)+10*s(300)+8*s(301)+37*s(371)+12*s(504)+4*s(793)+4*s(794)+12*s(799)+4 Such that:aux(74) =< 1 aux(75) =< 2 aux(76) =< 3 aux(77) =< 4 aux(78) =< 5 aux(79) =< 6 aux(80) =< V1 aux(81) =< 2*V1 aux(82) =< V1/2 aux(83) =< 2/3*V1 aux(84) =< 2/5*V1 aux(85) =< V aux(86) =< V+1 aux(87) =< 2*V aux(88) =< 2*V+1 aux(89) =< 2*V+2 aux(90) =< V/2 aux(91) =< 2/3*V aux(92) =< 2/5*V aux(93) =< V2 aux(94) =< V2+2 aux(95) =< 2*V2 aux(96) =< V2/2 aux(97) =< 2/3*V2 aux(98) =< 2/5*V2 s(371) =< aux(75) s(300) =< aux(76) s(301) =< aux(77) s(793) =< aux(78) s(794) =< aux(79) s(202) =< aux(86) s(203) =< aux(88) s(204) =< aux(89) s(205) =< aux(94) s(504) =< aux(74) s(147) =< aux(85) s(209) =< s(147)*aux(87) s(148) =< aux(85) s(149) =< aux(85) s(150) =< aux(85) s(150) =< aux(90) s(149) =< aux(91) s(150) =< aux(91) s(148) =< aux(92) s(151) =< aux(87)*(1/2) s(152) =< aux(87)*(1/2)-1 s(153) =< aux(87)*(1/2)-2 s(154) =< aux(87)*(1/2)+2 s(155) =< aux(87)+1 s(156) =< aux(87)*(1/2)+1 s(157) =< aux(85)*4 s(158) =< aux(85)*3 s(159) =< s(147)*s(154) s(160) =< s(147)*s(156) s(161) =< s(147)*s(155) s(162) =< s(147)*s(156) s(163) =< s(147)*s(151) s(164) =< s(160)*2 s(165) =< aux(85)*s(151) s(166) =< s(150)*s(152) s(167) =< s(148)*s(153) s(168) =< s(161) s(169) =< s(164) s(170) =< s(163) s(171) =< s(170)*aux(87) s(117) =< aux(80) s(118) =< aux(80) s(119) =< aux(80) s(120) =< aux(80) s(120) =< aux(82) s(119) =< aux(83) s(120) =< aux(83) s(118) =< aux(84) s(121) =< aux(81)*(1/2) s(122) =< aux(81)*(1/2)-1 s(123) =< aux(81)*(1/2)-2 s(124) =< aux(81)*(1/2)+2 s(125) =< aux(81)+1 s(126) =< aux(81)*(1/2)+1 s(127) =< aux(80)*4 s(128) =< aux(80)*3 s(129) =< s(117)*s(124) s(130) =< s(117)*s(126) s(131) =< s(117)*s(125) s(132) =< s(117)*s(126) s(133) =< s(117)*s(121) s(134) =< s(130)*2 s(135) =< aux(80)*s(121) s(136) =< s(120)*s(122) s(137) =< s(118)*s(123) s(138) =< s(131) s(139) =< s(134) s(140) =< s(133) s(141) =< s(140)*aux(81) s(177) =< aux(93) s(178) =< aux(93) s(179) =< aux(93) s(180) =< aux(93) s(180) =< aux(96) s(179) =< aux(97) s(180) =< aux(97) s(178) =< aux(98) s(181) =< aux(95)*(1/2) s(182) =< aux(95)*(1/2)-1 s(183) =< aux(95)*(1/2)-2 s(184) =< aux(95)*(1/2)+2 s(185) =< aux(95)+1 s(186) =< aux(95)*(1/2)+1 s(187) =< aux(93)*4 s(188) =< aux(93)*3 s(189) =< s(177)*s(184) s(190) =< s(177)*s(186) s(191) =< s(177)*s(185) s(192) =< s(177)*s(186) s(193) =< s(177)*s(181) s(194) =< s(190)*2 s(195) =< aux(93)*s(181) s(196) =< s(180)*s(182) s(197) =< s(178)*s(183) s(198) =< s(191) s(199) =< s(194) s(200) =< s(193) s(201) =< s(200)*aux(95) s(799) =< s(371)*aux(77) with precondition: [Out=0,V1>=0,V>=0,V2>=0] * Chain [42]: 10*s(1065)+2*s(1066)+2*s(1067)+2*s(1068)+2*s(1075)+2*s(1076)+2*s(1077)+2*s(1080)+2*s(1083)+2*s(1084)+2*s(1085)+4*s(1086)+4*s(1087)+24*s(1088)+12*s(1089)+33*s(1095)+3*s(1096)+3*s(1097)+3*s(1098)+3*s(1105)+3*s(1106)+3*s(1107)+3*s(1110)+3*s(1113)+3*s(1114)+3*s(1115)+6*s(1116)+6*s(1117)+36*s(1118)+18*s(1119)+3*s(1120)+6*s(1121)+6*s(1123)+9*s(1127)+3*s(1158)+2 Such that:aux(108) =< 1 aux(109) =< 4 aux(110) =< V1 aux(111) =< 2*V1 aux(112) =< V1/2 aux(113) =< 2/3*V1 aux(114) =< 2/5*V1 aux(115) =< V aux(116) =< V+1 aux(117) =< 2*V aux(118) =< V/2 aux(119) =< 2/3*V aux(120) =< 2/5*V s(1158) =< aux(108) s(1123) =< aux(109) s(1120) =< aux(116) s(1065) =< aux(110) s(1066) =< aux(110) s(1067) =< aux(110) s(1068) =< aux(110) s(1068) =< aux(112) s(1067) =< aux(113) s(1068) =< aux(113) s(1066) =< aux(114) s(1069) =< aux(111)*(1/2) s(1070) =< aux(111)*(1/2)-1 s(1071) =< aux(111)*(1/2)-2 s(1072) =< aux(111)*(1/2)+2 s(1073) =< aux(111)+1 s(1074) =< aux(111)*(1/2)+1 s(1075) =< aux(110)*4 s(1076) =< aux(110)*3 s(1077) =< s(1065)*s(1072) s(1078) =< s(1065)*s(1074) s(1079) =< s(1065)*s(1073) s(1080) =< s(1065)*s(1074) s(1081) =< s(1065)*s(1069) s(1082) =< s(1078)*2 s(1083) =< aux(110)*s(1069) s(1084) =< s(1068)*s(1070) s(1085) =< s(1066)*s(1071) s(1086) =< s(1079) s(1087) =< s(1082) s(1088) =< s(1081) s(1089) =< s(1088)*aux(111) s(1121) =< aux(117) s(1095) =< aux(115) s(1127) =< s(1095)*aux(117) s(1096) =< aux(115) s(1097) =< aux(115) s(1098) =< aux(115) s(1098) =< aux(118) s(1097) =< aux(119) s(1098) =< aux(119) s(1096) =< aux(120) s(1099) =< aux(117)*(1/2) s(1100) =< aux(117)*(1/2)-1 s(1101) =< aux(117)*(1/2)-2 s(1102) =< aux(117)*(1/2)+2 s(1103) =< aux(117)+1 s(1104) =< aux(117)*(1/2)+1 s(1105) =< aux(115)*4 s(1106) =< aux(115)*3 s(1107) =< s(1095)*s(1102) s(1108) =< s(1095)*s(1104) s(1109) =< s(1095)*s(1103) s(1110) =< s(1095)*s(1104) s(1111) =< s(1095)*s(1099) s(1112) =< s(1108)*2 s(1113) =< aux(115)*s(1099) s(1114) =< s(1098)*s(1100) s(1115) =< s(1096)*s(1101) s(1116) =< s(1109) s(1117) =< s(1112) s(1118) =< s(1111) s(1119) =< s(1118)*aux(117) with precondition: [V2=2,Out=0,V1>=0,V>=0] * Chain [41]: 25*s(1263)+5*s(1264)+5*s(1265)+5*s(1266)+5*s(1273)+5*s(1274)+5*s(1275)+5*s(1278)+5*s(1281)+5*s(1282)+5*s(1283)+10*s(1284)+10*s(1285)+60*s(1286)+30*s(1287)+15*s(1293)+3*s(1294)+3*s(1295)+3*s(1296)+3*s(1303)+3*s(1304)+3*s(1305)+3*s(1308)+3*s(1311)+3*s(1312)+3*s(1313)+6*s(1314)+6*s(1315)+36*s(1316)+18*s(1317)+10*s(1318)+6*s(1319)+6*s(1320)+2*s(1321)+38*s(1324)+18*s(1325)+6*s(1387)+4 Such that:aux(129) =< 2 aux(130) =< 3 aux(131) =< 4 aux(132) =< 5 aux(133) =< 6 aux(134) =< V1 aux(135) =< 2*V1 aux(136) =< V1/2 aux(137) =< 2/3*V1 aux(138) =< 2/5*V1 aux(139) =< V2 aux(140) =< V2+2 aux(141) =< 2*V2 aux(142) =< V2/2 aux(143) =< 2/3*V2 aux(144) =< 2/5*V2 s(1318) =< aux(130) s(1319) =< aux(132) s(1320) =< aux(133) s(1321) =< aux(140) s(1324) =< aux(129) s(1325) =< s(1324)*aux(131) s(1293) =< aux(139) s(1294) =< aux(139) s(1295) =< aux(139) s(1296) =< aux(139) s(1296) =< aux(142) s(1295) =< aux(143) s(1296) =< aux(143) s(1294) =< aux(144) s(1297) =< aux(141)*(1/2) s(1298) =< aux(141)*(1/2)-1 s(1299) =< aux(141)*(1/2)-2 s(1300) =< aux(141)*(1/2)+2 s(1301) =< aux(141)+1 s(1302) =< aux(141)*(1/2)+1 s(1303) =< aux(139)*4 s(1304) =< aux(139)*3 s(1305) =< s(1293)*s(1300) s(1306) =< s(1293)*s(1302) s(1307) =< s(1293)*s(1301) s(1308) =< s(1293)*s(1302) s(1309) =< s(1293)*s(1297) s(1310) =< s(1306)*2 s(1311) =< aux(139)*s(1297) s(1312) =< s(1296)*s(1298) s(1313) =< s(1294)*s(1299) s(1314) =< s(1307) s(1315) =< s(1310) s(1316) =< s(1309) s(1317) =< s(1316)*aux(141) s(1263) =< aux(134) s(1264) =< aux(134) s(1265) =< aux(134) s(1266) =< aux(134) s(1266) =< aux(136) s(1265) =< aux(137) s(1266) =< aux(137) s(1264) =< aux(138) s(1267) =< aux(135)*(1/2) s(1268) =< aux(135)*(1/2)-1 s(1269) =< aux(135)*(1/2)-2 s(1270) =< aux(135)*(1/2)+2 s(1271) =< aux(135)+1 s(1272) =< aux(135)*(1/2)+1 s(1273) =< aux(134)*4 s(1274) =< aux(134)*3 s(1275) =< s(1263)*s(1270) s(1276) =< s(1263)*s(1272) s(1277) =< s(1263)*s(1271) s(1278) =< s(1263)*s(1272) s(1279) =< s(1263)*s(1267) s(1280) =< s(1276)*2 s(1281) =< aux(134)*s(1267) s(1282) =< s(1266)*s(1268) s(1283) =< s(1264)*s(1269) s(1284) =< s(1277) s(1285) =< s(1280) s(1286) =< s(1279) s(1287) =< s(1286)*aux(135) s(1387) =< aux(131) with precondition: [V=2,Out=0,V1>=0,V2>=0] #### Cost of chains of fun1(Out): * Chain [45]: 0 with precondition: [Out=0] * Chain [44]: 0 with precondition: [Out=2] #### Cost of chains of fun2(V1,V,Out): * Chain [51]: 10*s(1752)+2*s(1753)+2*s(1754)+2*s(1755)+2*s(1762)+2*s(1763)+2*s(1764)+2*s(1767)+2*s(1770)+2*s(1771)+2*s(1772)+4*s(1773)+4*s(1774)+24*s(1775)+12*s(1776)+18*s(1782)+3*s(1783)+3*s(1784)+3*s(1785)+3*s(1792)+3*s(1793)+3*s(1794)+3*s(1797)+3*s(1800)+3*s(1801)+3*s(1802)+6*s(1803)+6*s(1804)+36*s(1805)+18*s(1806)+1*s(1870)+0 Such that:s(1870) =< 2 aux(164) =< V1 aux(165) =< 2*V1 aux(166) =< V1/2 aux(167) =< 2/3*V1 aux(168) =< 2/5*V1 aux(169) =< V aux(170) =< 2*V aux(171) =< V/2 aux(172) =< 2/3*V aux(173) =< 2/5*V s(1782) =< aux(169) s(1783) =< aux(169) s(1784) =< aux(169) s(1785) =< aux(169) s(1785) =< aux(171) s(1784) =< aux(172) s(1785) =< aux(172) s(1783) =< aux(173) s(1786) =< aux(170)*(1/2) s(1787) =< aux(170)*(1/2)-1 s(1788) =< aux(170)*(1/2)-2 s(1789) =< aux(170)*(1/2)+2 s(1790) =< aux(170)+1 s(1791) =< aux(170)*(1/2)+1 s(1792) =< aux(169)*4 s(1793) =< aux(169)*3 s(1794) =< s(1782)*s(1789) s(1795) =< s(1782)*s(1791) s(1796) =< s(1782)*s(1790) s(1797) =< s(1782)*s(1791) s(1798) =< s(1782)*s(1786) s(1799) =< s(1795)*2 s(1800) =< aux(169)*s(1786) s(1801) =< s(1785)*s(1787) s(1802) =< s(1783)*s(1788) s(1803) =< s(1796) s(1804) =< s(1799) s(1805) =< s(1798) s(1806) =< s(1805)*aux(170) s(1752) =< aux(164) s(1753) =< aux(164) s(1754) =< aux(164) s(1755) =< aux(164) s(1755) =< aux(166) s(1754) =< aux(167) s(1755) =< aux(167) s(1753) =< aux(168) s(1756) =< aux(165)*(1/2) s(1757) =< aux(165)*(1/2)-1 s(1758) =< aux(165)*(1/2)-2 s(1759) =< aux(165)*(1/2)+2 s(1760) =< aux(165)+1 s(1761) =< aux(165)*(1/2)+1 s(1762) =< aux(164)*4 s(1763) =< aux(164)*3 s(1764) =< s(1752)*s(1759) s(1765) =< s(1752)*s(1761) s(1766) =< s(1752)*s(1760) s(1767) =< s(1752)*s(1761) s(1768) =< s(1752)*s(1756) s(1769) =< s(1765)*2 s(1770) =< aux(164)*s(1756) s(1771) =< s(1755)*s(1757) s(1772) =< s(1753)*s(1758) s(1773) =< s(1766) s(1774) =< s(1769) s(1775) =< s(1768) s(1776) =< s(1775)*aux(165) with precondition: [Out=0,V1>=0,V>=0] * Chain [50]: 15*s(1909)+3*s(1910)+3*s(1911)+3*s(1912)+3*s(1919)+3*s(1920)+3*s(1921)+3*s(1924)+3*s(1927)+3*s(1928)+3*s(1929)+6*s(1930)+6*s(1931)+36*s(1932)+18*s(1933)+21*s(1939)+4*s(1940)+4*s(1941)+4*s(1942)+4*s(1949)+4*s(1950)+4*s(1951)+4*s(1954)+4*s(1957)+4*s(1958)+4*s(1959)+8*s(1960)+8*s(1961)+48*s(1962)+24*s(1963)+2*s(2085)+1 Such that:aux(175) =< 2 aux(176) =< V1 aux(177) =< 2*V1 aux(178) =< V1/2 aux(179) =< 2/3*V1 aux(180) =< 2/5*V1 aux(181) =< V aux(182) =< 2*V aux(183) =< V/2 aux(184) =< 2/3*V aux(185) =< 2/5*V s(2085) =< aux(175) s(1939) =< aux(181) s(1940) =< aux(181) s(1941) =< aux(181) s(1942) =< aux(181) s(1942) =< aux(183) s(1941) =< aux(184) s(1942) =< aux(184) s(1940) =< aux(185) s(1943) =< aux(182)*(1/2) s(1944) =< aux(182)*(1/2)-1 s(1945) =< aux(182)*(1/2)-2 s(1946) =< aux(182)*(1/2)+2 s(1947) =< aux(182)+1 s(1948) =< aux(182)*(1/2)+1 s(1949) =< aux(181)*4 s(1950) =< aux(181)*3 s(1951) =< s(1939)*s(1946) s(1952) =< s(1939)*s(1948) s(1953) =< s(1939)*s(1947) s(1954) =< s(1939)*s(1948) s(1955) =< s(1939)*s(1943) s(1956) =< s(1952)*2 s(1957) =< aux(181)*s(1943) s(1958) =< s(1942)*s(1944) s(1959) =< s(1940)*s(1945) s(1960) =< s(1953) s(1961) =< s(1956) s(1962) =< s(1955) s(1963) =< s(1962)*aux(182) s(1909) =< aux(176) s(1910) =< aux(176) s(1911) =< aux(176) s(1912) =< aux(176) s(1912) =< aux(178) s(1911) =< aux(179) s(1912) =< aux(179) s(1910) =< aux(180) s(1913) =< aux(177)*(1/2) s(1914) =< aux(177)*(1/2)-1 s(1915) =< aux(177)*(1/2)-2 s(1916) =< aux(177)*(1/2)+2 s(1917) =< aux(177)+1 s(1918) =< aux(177)*(1/2)+1 s(1919) =< aux(176)*4 s(1920) =< aux(176)*3 s(1921) =< s(1909)*s(1916) s(1922) =< s(1909)*s(1918) s(1923) =< s(1909)*s(1917) s(1924) =< s(1909)*s(1918) s(1925) =< s(1909)*s(1913) s(1926) =< s(1922)*2 s(1927) =< aux(176)*s(1913) s(1928) =< s(1912)*s(1914) s(1929) =< s(1910)*s(1915) s(1930) =< s(1923) s(1931) =< s(1926) s(1932) =< s(1925) s(1933) =< s(1932)*aux(177) with precondition: [Out=1,V1>=0,V>=0] * Chain [49]: 15*s(2122)+3*s(2123)+3*s(2124)+3*s(2125)+3*s(2132)+3*s(2133)+3*s(2134)+3*s(2137)+3*s(2140)+3*s(2141)+3*s(2142)+6*s(2143)+6*s(2144)+36*s(2145)+18*s(2146)+21*s(2152)+4*s(2153)+4*s(2154)+4*s(2155)+4*s(2162)+4*s(2163)+4*s(2164)+4*s(2167)+4*s(2170)+4*s(2171)+4*s(2172)+8*s(2173)+8*s(2174)+48*s(2175)+24*s(2176)+1*s(2328)+1 Such that:s(2328) =< 1 aux(187) =< V1 aux(188) =< 2*V1 aux(189) =< V1/2 aux(190) =< 2/3*V1 aux(191) =< 2/5*V1 aux(192) =< V aux(193) =< 2*V aux(194) =< V/2 aux(195) =< 2/3*V aux(196) =< 2/5*V s(2152) =< aux(192) s(2153) =< aux(192) s(2154) =< aux(192) s(2155) =< aux(192) s(2155) =< aux(194) s(2154) =< aux(195) s(2155) =< aux(195) s(2153) =< aux(196) s(2156) =< aux(193)*(1/2) s(2157) =< aux(193)*(1/2)-1 s(2158) =< aux(193)*(1/2)-2 s(2159) =< aux(193)*(1/2)+2 s(2160) =< aux(193)+1 s(2161) =< aux(193)*(1/2)+1 s(2162) =< aux(192)*4 s(2163) =< aux(192)*3 s(2164) =< s(2152)*s(2159) s(2165) =< s(2152)*s(2161) s(2166) =< s(2152)*s(2160) s(2167) =< s(2152)*s(2161) s(2168) =< s(2152)*s(2156) s(2169) =< s(2165)*2 s(2170) =< aux(192)*s(2156) s(2171) =< s(2155)*s(2157) s(2172) =< s(2153)*s(2158) s(2173) =< s(2166) s(2174) =< s(2169) s(2175) =< s(2168) s(2176) =< s(2175)*aux(193) s(2122) =< aux(187) s(2123) =< aux(187) s(2124) =< aux(187) s(2125) =< aux(187) s(2125) =< aux(189) s(2124) =< aux(190) s(2125) =< aux(190) s(2123) =< aux(191) s(2126) =< aux(188)*(1/2) s(2127) =< aux(188)*(1/2)-1 s(2128) =< aux(188)*(1/2)-2 s(2129) =< aux(188)*(1/2)+2 s(2130) =< aux(188)+1 s(2131) =< aux(188)*(1/2)+1 s(2132) =< aux(187)*4 s(2133) =< aux(187)*3 s(2134) =< s(2122)*s(2129) s(2135) =< s(2122)*s(2131) s(2136) =< s(2122)*s(2130) s(2137) =< s(2122)*s(2131) s(2138) =< s(2122)*s(2126) s(2139) =< s(2135)*2 s(2140) =< aux(187)*s(2126) s(2141) =< s(2125)*s(2127) s(2142) =< s(2123)*s(2128) s(2143) =< s(2136) s(2144) =< s(2139) s(2145) =< s(2138) s(2146) =< s(2145)*aux(188) with precondition: [Out=2,V1>=1,V>=0] * Chain [48]: 5*s(2334)+1*s(2335)+1*s(2336)+1*s(2337)+1*s(2344)+1*s(2345)+1*s(2346)+1*s(2349)+1*s(2352)+1*s(2353)+1*s(2354)+2*s(2355)+2*s(2356)+12*s(2357)+6*s(2358)+2*s(2359)+0 Such that:s(2329) =< V1 s(2330) =< 2*V1 s(2331) =< V1/2 s(2332) =< 2/3*V1 s(2333) =< 2/5*V1 aux(197) =< 2 s(2359) =< aux(197) s(2334) =< s(2329) s(2335) =< s(2329) s(2336) =< s(2329) s(2337) =< s(2329) s(2337) =< s(2331) s(2336) =< s(2332) s(2337) =< s(2332) s(2335) =< s(2333) s(2338) =< s(2330)*(1/2) s(2339) =< s(2330)*(1/2)-1 s(2340) =< s(2330)*(1/2)-2 s(2341) =< s(2330)*(1/2)+2 s(2342) =< s(2330)+1 s(2343) =< s(2330)*(1/2)+1 s(2344) =< s(2329)*4 s(2345) =< s(2329)*3 s(2346) =< s(2334)*s(2341) s(2347) =< s(2334)*s(2343) s(2348) =< s(2334)*s(2342) s(2349) =< s(2334)*s(2343) s(2350) =< s(2334)*s(2338) s(2351) =< s(2347)*2 s(2352) =< s(2329)*s(2338) s(2353) =< s(2337)*s(2339) s(2354) =< s(2335)*s(2340) s(2355) =< s(2348) s(2356) =< s(2351) s(2357) =< s(2350) s(2358) =< s(2357)*s(2330) with precondition: [V=2,Out=0,V1>=0] * Chain [47]: 11*s(2366)+2*s(2367)+2*s(2368)+2*s(2369)+2*s(2376)+2*s(2377)+2*s(2378)+2*s(2381)+2*s(2384)+2*s(2385)+2*s(2386)+4*s(2387)+4*s(2388)+24*s(2389)+12*s(2390)+1 Such that:aux(199) =< V1 aux(200) =< 2*V1 aux(201) =< V1/2 aux(202) =< 2/3*V1 aux(203) =< 2/5*V1 s(2366) =< aux(199) s(2367) =< aux(199) s(2368) =< aux(199) s(2369) =< aux(199) s(2369) =< aux(201) s(2368) =< aux(202) s(2369) =< aux(202) s(2367) =< aux(203) s(2370) =< aux(200)*(1/2) s(2371) =< aux(200)*(1/2)-1 s(2372) =< aux(200)*(1/2)-2 s(2373) =< aux(200)*(1/2)+2 s(2374) =< aux(200)+1 s(2375) =< aux(200)*(1/2)+1 s(2376) =< aux(199)*4 s(2377) =< aux(199)*3 s(2378) =< s(2366)*s(2373) s(2379) =< s(2366)*s(2375) s(2380) =< s(2366)*s(2374) s(2381) =< s(2366)*s(2375) s(2382) =< s(2366)*s(2370) s(2383) =< s(2379)*2 s(2384) =< aux(199)*s(2370) s(2385) =< s(2369)*s(2371) s(2386) =< s(2367)*s(2372) s(2387) =< s(2380) s(2388) =< s(2383) s(2389) =< s(2382) s(2390) =< s(2389)*aux(200) with precondition: [V=2,Out=1,V1>=0] * Chain [46]: 5*s(2427)+1*s(2428)+1*s(2429)+1*s(2430)+1*s(2437)+1*s(2438)+1*s(2439)+1*s(2442)+1*s(2445)+1*s(2446)+1*s(2447)+2*s(2448)+2*s(2449)+12*s(2450)+6*s(2451)+1*s(2452)+1 Such that:s(2452) =< 2 s(2422) =< V1 s(2423) =< 2*V1 s(2424) =< V1/2 s(2425) =< 2/3*V1 s(2426) =< 2/5*V1 s(2427) =< s(2422) s(2428) =< s(2422) s(2429) =< s(2422) s(2430) =< s(2422) s(2430) =< s(2424) s(2429) =< s(2425) s(2430) =< s(2425) s(2428) =< s(2426) s(2431) =< s(2423)*(1/2) s(2432) =< s(2423)*(1/2)-1 s(2433) =< s(2423)*(1/2)-2 s(2434) =< s(2423)*(1/2)+2 s(2435) =< s(2423)+1 s(2436) =< s(2423)*(1/2)+1 s(2437) =< s(2422)*4 s(2438) =< s(2422)*3 s(2439) =< s(2427)*s(2434) s(2440) =< s(2427)*s(2436) s(2441) =< s(2427)*s(2435) s(2442) =< s(2427)*s(2436) s(2443) =< s(2427)*s(2431) s(2444) =< s(2440)*2 s(2445) =< s(2422)*s(2431) s(2446) =< s(2430)*s(2432) s(2447) =< s(2428)*s(2433) s(2448) =< s(2441) s(2449) =< s(2444) s(2450) =< s(2443) s(2451) =< s(2450)*s(2423) with precondition: [V=2,Out=2,V1>=3] #### Cost of chains of fun3(V1,Out): * Chain [54]: 5*s(2735)+1*s(2736)+1*s(2737)+1*s(2738)+1*s(2745)+1*s(2746)+1*s(2747)+1*s(2750)+1*s(2753)+1*s(2754)+1*s(2755)+2*s(2756)+2*s(2757)+12*s(2758)+6*s(2759)+0 Such that:s(2730) =< V1 s(2731) =< 2*V1 s(2732) =< V1/2 s(2733) =< 2/3*V1 s(2734) =< 2/5*V1 s(2735) =< s(2730) s(2736) =< s(2730) s(2737) =< s(2730) s(2738) =< s(2730) s(2738) =< s(2732) s(2737) =< s(2733) s(2738) =< s(2733) s(2736) =< s(2734) s(2739) =< s(2731)*(1/2) s(2740) =< s(2731)*(1/2)-1 s(2741) =< s(2731)*(1/2)-2 s(2742) =< s(2731)*(1/2)+2 s(2743) =< s(2731)+1 s(2744) =< s(2731)*(1/2)+1 s(2745) =< s(2730)*4 s(2746) =< s(2730)*3 s(2747) =< s(2735)*s(2742) s(2748) =< s(2735)*s(2744) s(2749) =< s(2735)*s(2743) s(2750) =< s(2735)*s(2744) s(2751) =< s(2735)*s(2739) s(2752) =< s(2748)*2 s(2753) =< s(2730)*s(2739) s(2754) =< s(2738)*s(2740) s(2755) =< s(2736)*s(2741) s(2756) =< s(2749) s(2757) =< s(2752) s(2758) =< s(2751) s(2759) =< s(2758)*s(2731) with precondition: [V1>=1,Out>=1,V1+1>=Out] * Chain [53]: 0 with precondition: [Out=0,V1>=0] * Chain [52]: 0 with precondition: [Out=1,V1>=0] #### Cost of chains of fun5(Out): * Chain [56]: 0 with precondition: [Out=0] * Chain [55]: 0 with precondition: [Out=1] #### Cost of chains of start(V1,V,V2): * Chain [57]: 10*s(2760)+1*s(2761)+1*s(2762)+10*s(2763)+6*s(2766)+3*s(2767)+21*s(2768)+21*s(2769)+11*s(2770)+11*s(2771)+211*s(2774)+42*s(2775)+137*s(2777)+27*s(2785)+27*s(2786)+27*s(2787)+27*s(2794)+27*s(2795)+27*s(2796)+27*s(2799)+27*s(2802)+27*s(2803)+27*s(2804)+54*s(2805)+54*s(2806)+324*s(2807)+162*s(2808)+81*s(2834)+10*s(2837)+10*s(2838)+16*s(2843)+24*s(2846)+24*s(2847)+24*s(2848)+24*s(2855)+24*s(2856)+24*s(2857)+24*s(2860)+24*s(2863)+24*s(2864)+24*s(2865)+48*s(2866)+48*s(2867)+288*s(2868)+144*s(2869)+65*s(2895)+13*s(2896)+13*s(2897)+13*s(2898)+13*s(2905)+13*s(2906)+13*s(2907)+13*s(2910)+13*s(2913)+13*s(2914)+13*s(2915)+26*s(2916)+26*s(2917)+156*s(2918)+78*s(2919)+30*s(2920)+6*s(2962)+4 Such that:s(2821) =< 5 s(2822) =< 6 s(2764) =< V-V2 s(2765) =< 2*V-V2 s(2761) =< 2*V-V2+1 s(2762) =< 2*V-V2+2 s(2828) =< V2 s(2830) =< 2*V2 s(2831) =< V2/2 s(2832) =< 2/3*V2 s(2833) =< 2/5*V2 aux(220) =< 1 aux(221) =< 2 aux(222) =< 3 aux(223) =< 4 aux(224) =< V1 aux(225) =< 2*V1 aux(226) =< V1/2 aux(227) =< 2/3*V1 aux(228) =< 2/5*V1 aux(229) =< V aux(230) =< V+1 aux(231) =< 2*V aux(232) =< 2*V+1 aux(233) =< 2*V+2 aux(234) =< V/2 aux(235) =< 2/3*V aux(236) =< 2/5*V aux(237) =< V2+2 s(2843) =< aux(220) s(2834) =< aux(221) s(2768) =< aux(222) s(2769) =< aux(223) s(2777) =< aux(224) s(2774) =< aux(229) s(2760) =< aux(230) s(2770) =< aux(232) s(2771) =< aux(233) s(2763) =< aux(237) s(2837) =< s(2821) s(2838) =< s(2822) s(2775) =< s(2774)*aux(231) s(2846) =< aux(229) s(2847) =< aux(229) s(2848) =< aux(229) s(2848) =< aux(234) s(2847) =< aux(235) s(2848) =< aux(235) s(2846) =< aux(236) s(2849) =< aux(231)*(1/2) s(2850) =< aux(231)*(1/2)-1 s(2851) =< aux(231)*(1/2)-2 s(2852) =< aux(231)*(1/2)+2 s(2853) =< aux(231)+1 s(2854) =< aux(231)*(1/2)+1 s(2855) =< aux(229)*4 s(2856) =< aux(229)*3 s(2857) =< s(2774)*s(2852) s(2858) =< s(2774)*s(2854) s(2859) =< s(2774)*s(2853) s(2860) =< s(2774)*s(2854) s(2861) =< s(2774)*s(2849) s(2862) =< s(2858)*2 s(2863) =< aux(229)*s(2849) s(2864) =< s(2848)*s(2850) s(2865) =< s(2846)*s(2851) s(2866) =< s(2859) s(2867) =< s(2862) s(2868) =< s(2861) s(2869) =< s(2868)*aux(231) s(2785) =< aux(224) s(2786) =< aux(224) s(2787) =< aux(224) s(2787) =< aux(226) s(2786) =< aux(227) s(2787) =< aux(227) s(2785) =< aux(228) s(2788) =< aux(225)*(1/2) s(2789) =< aux(225)*(1/2)-1 s(2790) =< aux(225)*(1/2)-2 s(2791) =< aux(225)*(1/2)+2 s(2792) =< aux(225)+1 s(2793) =< aux(225)*(1/2)+1 s(2794) =< aux(224)*4 s(2795) =< aux(224)*3 s(2796) =< s(2777)*s(2791) s(2797) =< s(2777)*s(2793) s(2798) =< s(2777)*s(2792) s(2799) =< s(2777)*s(2793) s(2800) =< s(2777)*s(2788) s(2801) =< s(2797)*2 s(2802) =< aux(224)*s(2788) s(2803) =< s(2787)*s(2789) s(2804) =< s(2785)*s(2790) s(2805) =< s(2798) s(2806) =< s(2801) s(2807) =< s(2800) s(2808) =< s(2807)*aux(225) s(2895) =< s(2828) s(2896) =< s(2828) s(2897) =< s(2828) s(2898) =< s(2828) s(2898) =< s(2831) s(2897) =< s(2832) s(2898) =< s(2832) s(2896) =< s(2833) s(2899) =< s(2830)*(1/2) s(2900) =< s(2830)*(1/2)-1 s(2901) =< s(2830)*(1/2)-2 s(2902) =< s(2830)*(1/2)+2 s(2903) =< s(2830)+1 s(2904) =< s(2830)*(1/2)+1 s(2905) =< s(2828)*4 s(2906) =< s(2828)*3 s(2907) =< s(2895)*s(2902) s(2908) =< s(2895)*s(2904) s(2909) =< s(2895)*s(2903) s(2910) =< s(2895)*s(2904) s(2911) =< s(2895)*s(2899) s(2912) =< s(2908)*2 s(2913) =< s(2828)*s(2899) s(2914) =< s(2898)*s(2900) s(2915) =< s(2896)*s(2901) s(2916) =< s(2909) s(2917) =< s(2912) s(2918) =< s(2911) s(2919) =< s(2918)*s(2830) s(2920) =< s(2834)*aux(223) s(2962) =< aux(231) s(2766) =< s(2764) s(2767) =< s(2766)*s(2765) with precondition: [] Closed-form bounds of start(V1,V,V2): ------------------------------------- * Chain [57] with precondition: [] - Upper bound: nat(V1)*650+679+nat(V1)*27*nat(1/2*nat(2*V1)+ -2)+nat(V1)*27*nat(1/2*nat(2*V1)+ -1)+621/2*nat(V1)*nat(2*V1)+nat(V1)*81*nat(2*V1)*nat(2*V1)+nat(V)*667+nat(V)*24*nat(1/2*nat(2*V)+ -2)+nat(V)*24*nat(1/2*nat(2*V)+ -1)+nat(V)*318*nat(2*V)+nat(V)*72*nat(2*V)*nat(2*V)+nat(V2)*312+nat(V2)*13*nat(1/2*nat(2*V2)+ -2)+nat(V2)*13*nat(1/2*nat(2*V2)+ -1)+299/2*nat(V2)*nat(2*V2)+nat(V2)*39*nat(2*V2)*nat(2*V2)+nat(2*V)*6+nat(V+1)*10+nat(V2+2)*10+nat(2*V+1)*11+nat(2*V+2)*11+nat(2*V-V2+1)+nat(2*V-V2+2)+nat(V-V2)*6+nat(V-V2)*3*nat(2*V-V2) - Complexity: n^3 ### Maximum cost of start(V1,V,V2): nat(V1)*650+679+nat(V1)*27*nat(1/2*nat(2*V1)+ -2)+nat(V1)*27*nat(1/2*nat(2*V1)+ -1)+621/2*nat(V1)*nat(2*V1)+nat(V1)*81*nat(2*V1)*nat(2*V1)+nat(V)*667+nat(V)*24*nat(1/2*nat(2*V)+ -2)+nat(V)*24*nat(1/2*nat(2*V)+ -1)+nat(V)*318*nat(2*V)+nat(V)*72*nat(2*V)*nat(2*V)+nat(V2)*312+nat(V2)*13*nat(1/2*nat(2*V2)+ -2)+nat(V2)*13*nat(1/2*nat(2*V2)+ -1)+299/2*nat(V2)*nat(2*V2)+nat(V2)*39*nat(2*V2)*nat(2*V2)+nat(2*V)*6+nat(V+1)*10+nat(V2+2)*10+nat(2*V+1)*11+nat(2*V+2)*11+nat(2*V-V2+1)+nat(2*V-V2+2)+nat(V-V2)*6+nat(V-V2)*3*nat(2*V-V2) Asymptotic class: n^3 * Total analysis performed in 6704 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: f(true, x, y) -> f(gt(x, y), s(x), s(s(y))) gt(0', v) -> false gt(s(u), 0') -> true gt(s(u), s(v)) -> gt(u, v) The (relative) TRS S consists of the following rules: encArg(true) -> true encArg(s(x_1)) -> s(encArg(x_1)) encArg(0') -> 0' encArg(false) -> false encArg(cons_f(x_1, x_2, x_3)) -> f(encArg(x_1), encArg(x_2), encArg(x_3)) encArg(cons_gt(x_1, x_2)) -> gt(encArg(x_1), encArg(x_2)) encode_f(x_1, x_2, x_3) -> f(encArg(x_1), encArg(x_2), encArg(x_3)) encode_true -> true encode_gt(x_1, x_2) -> gt(encArg(x_1), encArg(x_2)) encode_s(x_1) -> s(encArg(x_1)) encode_0 -> 0' encode_false -> false Rewrite Strategy: INNERMOST ---------------------------------------- (17) TypeInferenceProof (BOTH BOUNDS(ID, ID)) Infered types. ---------------------------------------- (18) Obligation: Innermost TRS: Rules: f(true, x, y) -> f(gt(x, y), s(x), s(s(y))) gt(0', v) -> false gt(s(u), 0') -> true gt(s(u), s(v)) -> gt(u, v) encArg(true) -> true encArg(s(x_1)) -> s(encArg(x_1)) encArg(0') -> 0' encArg(false) -> false encArg(cons_f(x_1, x_2, x_3)) -> f(encArg(x_1), encArg(x_2), encArg(x_3)) encArg(cons_gt(x_1, x_2)) -> gt(encArg(x_1), encArg(x_2)) encode_f(x_1, x_2, x_3) -> f(encArg(x_1), encArg(x_2), encArg(x_3)) encode_true -> true encode_gt(x_1, x_2) -> gt(encArg(x_1), encArg(x_2)) encode_s(x_1) -> s(encArg(x_1)) encode_0 -> 0' encode_false -> false Types: f :: true:s:0':false:cons_f:cons_gt -> true:s:0':false:cons_f:cons_gt -> true:s:0':false:cons_f:cons_gt -> true:s:0':false:cons_f:cons_gt true :: true:s:0':false:cons_f:cons_gt gt :: true:s:0':false:cons_f:cons_gt -> true:s:0':false:cons_f:cons_gt -> true:s:0':false:cons_f:cons_gt s :: true:s:0':false:cons_f:cons_gt -> true:s:0':false:cons_f:cons_gt 0' :: true:s:0':false:cons_f:cons_gt false :: true:s:0':false:cons_f:cons_gt encArg :: true:s:0':false:cons_f:cons_gt -> true:s:0':false:cons_f:cons_gt cons_f :: true:s:0':false:cons_f:cons_gt -> true:s:0':false:cons_f:cons_gt -> true:s:0':false:cons_f:cons_gt -> true:s:0':false:cons_f:cons_gt cons_gt :: true:s:0':false:cons_f:cons_gt -> true:s:0':false:cons_f:cons_gt -> true:s:0':false:cons_f:cons_gt encode_f :: true:s:0':false:cons_f:cons_gt -> true:s:0':false:cons_f:cons_gt -> true:s:0':false:cons_f:cons_gt -> true:s:0':false:cons_f:cons_gt encode_true :: true:s:0':false:cons_f:cons_gt encode_gt :: true:s:0':false:cons_f:cons_gt -> true:s:0':false:cons_f:cons_gt -> true:s:0':false:cons_f:cons_gt encode_s :: true:s:0':false:cons_f:cons_gt -> true:s:0':false:cons_f:cons_gt encode_0 :: true:s:0':false:cons_f:cons_gt encode_false :: true:s:0':false:cons_f:cons_gt hole_true:s:0':false:cons_f:cons_gt1_4 :: true:s:0':false:cons_f:cons_gt gen_true:s:0':false:cons_f:cons_gt2_4 :: Nat -> true:s:0':false:cons_f:cons_gt ---------------------------------------- (19) OrderProof (LOWER BOUND(ID)) Heuristically decided to analyse the following defined symbols: f, gt, encArg They will be analysed ascendingly in the following order: gt < f f < encArg gt < encArg ---------------------------------------- (20) Obligation: Innermost TRS: Rules: f(true, x, y) -> f(gt(x, y), s(x), s(s(y))) gt(0', v) -> false gt(s(u), 0') -> true gt(s(u), s(v)) -> gt(u, v) encArg(true) -> true encArg(s(x_1)) -> s(encArg(x_1)) encArg(0') -> 0' encArg(false) -> false encArg(cons_f(x_1, x_2, x_3)) -> f(encArg(x_1), encArg(x_2), encArg(x_3)) encArg(cons_gt(x_1, x_2)) -> gt(encArg(x_1), encArg(x_2)) encode_f(x_1, x_2, x_3) -> f(encArg(x_1), encArg(x_2), encArg(x_3)) encode_true -> true encode_gt(x_1, x_2) -> gt(encArg(x_1), encArg(x_2)) encode_s(x_1) -> s(encArg(x_1)) encode_0 -> 0' encode_false -> false Types: f :: true:s:0':false:cons_f:cons_gt -> true:s:0':false:cons_f:cons_gt -> true:s:0':false:cons_f:cons_gt -> true:s:0':false:cons_f:cons_gt true :: true:s:0':false:cons_f:cons_gt gt :: true:s:0':false:cons_f:cons_gt -> true:s:0':false:cons_f:cons_gt -> true:s:0':false:cons_f:cons_gt s :: true:s:0':false:cons_f:cons_gt -> true:s:0':false:cons_f:cons_gt 0' :: true:s:0':false:cons_f:cons_gt false :: true:s:0':false:cons_f:cons_gt encArg :: true:s:0':false:cons_f:cons_gt -> true:s:0':false:cons_f:cons_gt cons_f :: true:s:0':false:cons_f:cons_gt -> true:s:0':false:cons_f:cons_gt -> true:s:0':false:cons_f:cons_gt -> true:s:0':false:cons_f:cons_gt cons_gt :: true:s:0':false:cons_f:cons_gt -> true:s:0':false:cons_f:cons_gt -> true:s:0':false:cons_f:cons_gt encode_f :: true:s:0':false:cons_f:cons_gt -> true:s:0':false:cons_f:cons_gt -> true:s:0':false:cons_f:cons_gt -> true:s:0':false:cons_f:cons_gt encode_true :: true:s:0':false:cons_f:cons_gt encode_gt :: true:s:0':false:cons_f:cons_gt -> true:s:0':false:cons_f:cons_gt -> true:s:0':false:cons_f:cons_gt encode_s :: true:s:0':false:cons_f:cons_gt -> true:s:0':false:cons_f:cons_gt encode_0 :: true:s:0':false:cons_f:cons_gt encode_false :: true:s:0':false:cons_f:cons_gt hole_true:s:0':false:cons_f:cons_gt1_4 :: true:s:0':false:cons_f:cons_gt gen_true:s:0':false:cons_f:cons_gt2_4 :: Nat -> true:s:0':false:cons_f:cons_gt Generator Equations: gen_true:s:0':false:cons_f:cons_gt2_4(0) <=> true gen_true:s:0':false:cons_f:cons_gt2_4(+(x, 1)) <=> s(gen_true:s:0':false:cons_f:cons_gt2_4(x)) The following defined symbols remain to be analysed: gt, f, encArg They will be analysed ascendingly in the following order: gt < f f < encArg gt < encArg ---------------------------------------- (21) RewriteLemmaProof (LOWER BOUND(ID)) Proved the following rewrite lemma: gt(gen_true:s:0':false:cons_f:cons_gt2_4(+(1, n4_4)), gen_true:s:0':false:cons_f:cons_gt2_4(+(1, n4_4))) -> *3_4, rt in Omega(n4_4) Induction Base: gt(gen_true:s:0':false:cons_f:cons_gt2_4(+(1, 0)), gen_true:s:0':false:cons_f:cons_gt2_4(+(1, 0))) Induction Step: gt(gen_true:s:0':false:cons_f:cons_gt2_4(+(1, +(n4_4, 1))), gen_true:s:0':false:cons_f:cons_gt2_4(+(1, +(n4_4, 1)))) ->_R^Omega(1) gt(gen_true:s:0':false:cons_f:cons_gt2_4(+(1, n4_4)), gen_true:s:0':false:cons_f:cons_gt2_4(+(1, n4_4))) ->_IH *3_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: f(true, x, y) -> f(gt(x, y), s(x), s(s(y))) gt(0', v) -> false gt(s(u), 0') -> true gt(s(u), s(v)) -> gt(u, v) encArg(true) -> true encArg(s(x_1)) -> s(encArg(x_1)) encArg(0') -> 0' encArg(false) -> false encArg(cons_f(x_1, x_2, x_3)) -> f(encArg(x_1), encArg(x_2), encArg(x_3)) encArg(cons_gt(x_1, x_2)) -> gt(encArg(x_1), encArg(x_2)) encode_f(x_1, x_2, x_3) -> f(encArg(x_1), encArg(x_2), encArg(x_3)) encode_true -> true encode_gt(x_1, x_2) -> gt(encArg(x_1), encArg(x_2)) encode_s(x_1) -> s(encArg(x_1)) encode_0 -> 0' encode_false -> false Types: f :: true:s:0':false:cons_f:cons_gt -> true:s:0':false:cons_f:cons_gt -> true:s:0':false:cons_f:cons_gt -> true:s:0':false:cons_f:cons_gt true :: true:s:0':false:cons_f:cons_gt gt :: true:s:0':false:cons_f:cons_gt -> true:s:0':false:cons_f:cons_gt -> true:s:0':false:cons_f:cons_gt s :: true:s:0':false:cons_f:cons_gt -> true:s:0':false:cons_f:cons_gt 0' :: true:s:0':false:cons_f:cons_gt false :: true:s:0':false:cons_f:cons_gt encArg :: true:s:0':false:cons_f:cons_gt -> true:s:0':false:cons_f:cons_gt cons_f :: true:s:0':false:cons_f:cons_gt -> true:s:0':false:cons_f:cons_gt -> true:s:0':false:cons_f:cons_gt -> true:s:0':false:cons_f:cons_gt cons_gt :: true:s:0':false:cons_f:cons_gt -> true:s:0':false:cons_f:cons_gt -> true:s:0':false:cons_f:cons_gt encode_f :: true:s:0':false:cons_f:cons_gt -> true:s:0':false:cons_f:cons_gt -> true:s:0':false:cons_f:cons_gt -> true:s:0':false:cons_f:cons_gt encode_true :: true:s:0':false:cons_f:cons_gt encode_gt :: true:s:0':false:cons_f:cons_gt -> true:s:0':false:cons_f:cons_gt -> true:s:0':false:cons_f:cons_gt encode_s :: true:s:0':false:cons_f:cons_gt -> true:s:0':false:cons_f:cons_gt encode_0 :: true:s:0':false:cons_f:cons_gt encode_false :: true:s:0':false:cons_f:cons_gt hole_true:s:0':false:cons_f:cons_gt1_4 :: true:s:0':false:cons_f:cons_gt gen_true:s:0':false:cons_f:cons_gt2_4 :: Nat -> true:s:0':false:cons_f:cons_gt Generator Equations: gen_true:s:0':false:cons_f:cons_gt2_4(0) <=> true gen_true:s:0':false:cons_f:cons_gt2_4(+(x, 1)) <=> s(gen_true:s:0':false:cons_f:cons_gt2_4(x)) The following defined symbols remain to be analysed: gt, f, encArg They will be analysed ascendingly in the following order: gt < f f < encArg gt < encArg ---------------------------------------- (24) LowerBoundPropagationProof (FINISHED) Propagated lower bound. ---------------------------------------- (25) BOUNDS(n^1, INF) ---------------------------------------- (26) Obligation: Innermost TRS: Rules: f(true, x, y) -> f(gt(x, y), s(x), s(s(y))) gt(0', v) -> false gt(s(u), 0') -> true gt(s(u), s(v)) -> gt(u, v) encArg(true) -> true encArg(s(x_1)) -> s(encArg(x_1)) encArg(0') -> 0' encArg(false) -> false encArg(cons_f(x_1, x_2, x_3)) -> f(encArg(x_1), encArg(x_2), encArg(x_3)) encArg(cons_gt(x_1, x_2)) -> gt(encArg(x_1), encArg(x_2)) encode_f(x_1, x_2, x_3) -> f(encArg(x_1), encArg(x_2), encArg(x_3)) encode_true -> true encode_gt(x_1, x_2) -> gt(encArg(x_1), encArg(x_2)) encode_s(x_1) -> s(encArg(x_1)) encode_0 -> 0' encode_false -> false Types: f :: true:s:0':false:cons_f:cons_gt -> true:s:0':false:cons_f:cons_gt -> true:s:0':false:cons_f:cons_gt -> true:s:0':false:cons_f:cons_gt true :: true:s:0':false:cons_f:cons_gt gt :: true:s:0':false:cons_f:cons_gt -> true:s:0':false:cons_f:cons_gt -> true:s:0':false:cons_f:cons_gt s :: true:s:0':false:cons_f:cons_gt -> true:s:0':false:cons_f:cons_gt 0' :: true:s:0':false:cons_f:cons_gt false :: true:s:0':false:cons_f:cons_gt encArg :: true:s:0':false:cons_f:cons_gt -> true:s:0':false:cons_f:cons_gt cons_f :: true:s:0':false:cons_f:cons_gt -> true:s:0':false:cons_f:cons_gt -> true:s:0':false:cons_f:cons_gt -> true:s:0':false:cons_f:cons_gt cons_gt :: true:s:0':false:cons_f:cons_gt -> true:s:0':false:cons_f:cons_gt -> true:s:0':false:cons_f:cons_gt encode_f :: true:s:0':false:cons_f:cons_gt -> true:s:0':false:cons_f:cons_gt -> true:s:0':false:cons_f:cons_gt -> true:s:0':false:cons_f:cons_gt encode_true :: true:s:0':false:cons_f:cons_gt encode_gt :: true:s:0':false:cons_f:cons_gt -> true:s:0':false:cons_f:cons_gt -> true:s:0':false:cons_f:cons_gt encode_s :: true:s:0':false:cons_f:cons_gt -> true:s:0':false:cons_f:cons_gt encode_0 :: true:s:0':false:cons_f:cons_gt encode_false :: true:s:0':false:cons_f:cons_gt hole_true:s:0':false:cons_f:cons_gt1_4 :: true:s:0':false:cons_f:cons_gt gen_true:s:0':false:cons_f:cons_gt2_4 :: Nat -> true:s:0':false:cons_f:cons_gt Lemmas: gt(gen_true:s:0':false:cons_f:cons_gt2_4(+(1, n4_4)), gen_true:s:0':false:cons_f:cons_gt2_4(+(1, n4_4))) -> *3_4, rt in Omega(n4_4) Generator Equations: gen_true:s:0':false:cons_f:cons_gt2_4(0) <=> true gen_true:s:0':false:cons_f:cons_gt2_4(+(x, 1)) <=> s(gen_true:s:0':false:cons_f:cons_gt2_4(x)) The following defined symbols remain to be analysed: f, encArg They will be analysed ascendingly in the following order: f < encArg ---------------------------------------- (27) RewriteLemmaProof (LOWER BOUND(ID)) Proved the following rewrite lemma: encArg(gen_true:s:0':false:cons_f:cons_gt2_4(n2246_4)) -> gen_true:s:0':false:cons_f:cons_gt2_4(n2246_4), rt in Omega(0) Induction Base: encArg(gen_true:s:0':false:cons_f:cons_gt2_4(0)) ->_R^Omega(0) true Induction Step: encArg(gen_true:s:0':false:cons_f:cons_gt2_4(+(n2246_4, 1))) ->_R^Omega(0) s(encArg(gen_true:s:0':false:cons_f:cons_gt2_4(n2246_4))) ->_IH s(gen_true:s:0':false:cons_f:cons_gt2_4(c2247_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)