/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), 164 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, 12.0 s] (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), 489 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), 90 ms] (28) typed CpxTrs (29) RewriteLemmaProof [LOWER BOUND(ID), 140 ms] (30) 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), trunc(x), s(y)) trunc(0) -> 0 trunc(s(0)) -> 0 trunc(s(s(x))) -> s(s(trunc(x))) 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_trunc(x_1)) -> trunc(encArg(x_1)) 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_trunc(x_1) -> trunc(encArg(x_1)) 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), trunc(x), s(y)) trunc(0) -> 0 trunc(s(0)) -> 0 trunc(s(s(x))) -> s(s(trunc(x))) 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_trunc(x_1)) -> trunc(encArg(x_1)) 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_trunc(x_1) -> trunc(encArg(x_1)) 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), trunc(x), s(y)) trunc(0) -> 0 trunc(s(0)) -> 0 trunc(s(s(x))) -> s(s(trunc(x))) 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_trunc(x_1)) -> trunc(encArg(x_1)) 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_trunc(x_1) -> trunc(encArg(x_1)) 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), trunc(x), s(y)) [1] trunc(0) -> 0 [1] trunc(s(0)) -> 0 [1] trunc(s(s(x))) -> s(s(trunc(x))) [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_trunc(x_1)) -> trunc(encArg(x_1)) [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_trunc(x_1) -> trunc(encArg(x_1)) [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), trunc(x), s(y)) [1] trunc(0) -> 0 [1] trunc(s(0)) -> 0 [1] trunc(s(s(x))) -> s(s(trunc(x))) [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_trunc(x_1)) -> trunc(encArg(x_1)) [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_trunc(x_1) -> trunc(encArg(x_1)) [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_trunc:cons_gt -> true:s:0:false:cons_f:cons_trunc:cons_gt -> true:s:0:false:cons_f:cons_trunc:cons_gt -> true:s:0:false:cons_f:cons_trunc:cons_gt true :: true:s:0:false:cons_f:cons_trunc:cons_gt gt :: true:s:0:false:cons_f:cons_trunc:cons_gt -> true:s:0:false:cons_f:cons_trunc:cons_gt -> true:s:0:false:cons_f:cons_trunc:cons_gt trunc :: true:s:0:false:cons_f:cons_trunc:cons_gt -> true:s:0:false:cons_f:cons_trunc:cons_gt s :: true:s:0:false:cons_f:cons_trunc:cons_gt -> true:s:0:false:cons_f:cons_trunc:cons_gt 0 :: true:s:0:false:cons_f:cons_trunc:cons_gt false :: true:s:0:false:cons_f:cons_trunc:cons_gt encArg :: true:s:0:false:cons_f:cons_trunc:cons_gt -> true:s:0:false:cons_f:cons_trunc:cons_gt cons_f :: true:s:0:false:cons_f:cons_trunc:cons_gt -> true:s:0:false:cons_f:cons_trunc:cons_gt -> true:s:0:false:cons_f:cons_trunc:cons_gt -> true:s:0:false:cons_f:cons_trunc:cons_gt cons_trunc :: true:s:0:false:cons_f:cons_trunc:cons_gt -> true:s:0:false:cons_f:cons_trunc:cons_gt cons_gt :: true:s:0:false:cons_f:cons_trunc:cons_gt -> true:s:0:false:cons_f:cons_trunc:cons_gt -> true:s:0:false:cons_f:cons_trunc:cons_gt encode_f :: true:s:0:false:cons_f:cons_trunc:cons_gt -> true:s:0:false:cons_f:cons_trunc:cons_gt -> true:s:0:false:cons_f:cons_trunc:cons_gt -> true:s:0:false:cons_f:cons_trunc:cons_gt encode_true :: true:s:0:false:cons_f:cons_trunc:cons_gt encode_gt :: true:s:0:false:cons_f:cons_trunc:cons_gt -> true:s:0:false:cons_f:cons_trunc:cons_gt -> true:s:0:false:cons_f:cons_trunc:cons_gt encode_trunc :: true:s:0:false:cons_f:cons_trunc:cons_gt -> true:s:0:false:cons_f:cons_trunc:cons_gt encode_s :: true:s:0:false:cons_f:cons_trunc:cons_gt -> true:s:0:false:cons_f:cons_trunc:cons_gt encode_0 :: true:s:0:false:cons_f:cons_trunc:cons_gt encode_false :: true:s:0:false:cons_f:cons_trunc: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_trunc(v0) -> null_encode_trunc [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] trunc(v0) -> null_trunc [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_trunc, null_encode_s, null_encode_0, null_encode_false, null_f, null_trunc, 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), trunc(x), s(y)) [1] trunc(0) -> 0 [1] trunc(s(0)) -> 0 [1] trunc(s(s(x))) -> s(s(trunc(x))) [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_trunc(x_1)) -> trunc(encArg(x_1)) [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_trunc(x_1) -> trunc(encArg(x_1)) [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_trunc(v0) -> null_encode_trunc [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] trunc(v0) -> null_trunc [0] gt(v0, v1) -> null_gt [0] The TRS has the following type information: f :: true:s:0:false:cons_f:cons_trunc:cons_gt:null_encArg:null_encode_f:null_encode_true:null_encode_gt:null_encode_trunc:null_encode_s:null_encode_0:null_encode_false:null_f:null_trunc:null_gt -> true:s:0:false:cons_f:cons_trunc:cons_gt:null_encArg:null_encode_f:null_encode_true:null_encode_gt:null_encode_trunc:null_encode_s:null_encode_0:null_encode_false:null_f:null_trunc:null_gt -> true:s:0:false:cons_f:cons_trunc:cons_gt:null_encArg:null_encode_f:null_encode_true:null_encode_gt:null_encode_trunc:null_encode_s:null_encode_0:null_encode_false:null_f:null_trunc:null_gt -> true:s:0:false:cons_f:cons_trunc:cons_gt:null_encArg:null_encode_f:null_encode_true:null_encode_gt:null_encode_trunc:null_encode_s:null_encode_0:null_encode_false:null_f:null_trunc:null_gt true :: true:s:0:false:cons_f:cons_trunc:cons_gt:null_encArg:null_encode_f:null_encode_true:null_encode_gt:null_encode_trunc:null_encode_s:null_encode_0:null_encode_false:null_f:null_trunc:null_gt gt :: true:s:0:false:cons_f:cons_trunc:cons_gt:null_encArg:null_encode_f:null_encode_true:null_encode_gt:null_encode_trunc:null_encode_s:null_encode_0:null_encode_false:null_f:null_trunc:null_gt -> true:s:0:false:cons_f:cons_trunc:cons_gt:null_encArg:null_encode_f:null_encode_true:null_encode_gt:null_encode_trunc:null_encode_s:null_encode_0:null_encode_false:null_f:null_trunc:null_gt -> true:s:0:false:cons_f:cons_trunc:cons_gt:null_encArg:null_encode_f:null_encode_true:null_encode_gt:null_encode_trunc:null_encode_s:null_encode_0:null_encode_false:null_f:null_trunc:null_gt trunc :: true:s:0:false:cons_f:cons_trunc:cons_gt:null_encArg:null_encode_f:null_encode_true:null_encode_gt:null_encode_trunc:null_encode_s:null_encode_0:null_encode_false:null_f:null_trunc:null_gt -> true:s:0:false:cons_f:cons_trunc:cons_gt:null_encArg:null_encode_f:null_encode_true:null_encode_gt:null_encode_trunc:null_encode_s:null_encode_0:null_encode_false:null_f:null_trunc:null_gt s :: true:s:0:false:cons_f:cons_trunc:cons_gt:null_encArg:null_encode_f:null_encode_true:null_encode_gt:null_encode_trunc:null_encode_s:null_encode_0:null_encode_false:null_f:null_trunc:null_gt -> true:s:0:false:cons_f:cons_trunc:cons_gt:null_encArg:null_encode_f:null_encode_true:null_encode_gt:null_encode_trunc:null_encode_s:null_encode_0:null_encode_false:null_f:null_trunc:null_gt 0 :: true:s:0:false:cons_f:cons_trunc:cons_gt:null_encArg:null_encode_f:null_encode_true:null_encode_gt:null_encode_trunc:null_encode_s:null_encode_0:null_encode_false:null_f:null_trunc:null_gt false :: true:s:0:false:cons_f:cons_trunc:cons_gt:null_encArg:null_encode_f:null_encode_true:null_encode_gt:null_encode_trunc:null_encode_s:null_encode_0:null_encode_false:null_f:null_trunc:null_gt encArg :: true:s:0:false:cons_f:cons_trunc:cons_gt:null_encArg:null_encode_f:null_encode_true:null_encode_gt:null_encode_trunc:null_encode_s:null_encode_0:null_encode_false:null_f:null_trunc:null_gt -> true:s:0:false:cons_f:cons_trunc:cons_gt:null_encArg:null_encode_f:null_encode_true:null_encode_gt:null_encode_trunc:null_encode_s:null_encode_0:null_encode_false:null_f:null_trunc:null_gt cons_f :: true:s:0:false:cons_f:cons_trunc:cons_gt:null_encArg:null_encode_f:null_encode_true:null_encode_gt:null_encode_trunc:null_encode_s:null_encode_0:null_encode_false:null_f:null_trunc:null_gt -> true:s:0:false:cons_f:cons_trunc:cons_gt:null_encArg:null_encode_f:null_encode_true:null_encode_gt:null_encode_trunc:null_encode_s:null_encode_0:null_encode_false:null_f:null_trunc:null_gt -> true:s:0:false:cons_f:cons_trunc:cons_gt:null_encArg:null_encode_f:null_encode_true:null_encode_gt:null_encode_trunc:null_encode_s:null_encode_0:null_encode_false:null_f:null_trunc:null_gt -> true:s:0:false:cons_f:cons_trunc:cons_gt:null_encArg:null_encode_f:null_encode_true:null_encode_gt:null_encode_trunc:null_encode_s:null_encode_0:null_encode_false:null_f:null_trunc:null_gt cons_trunc :: true:s:0:false:cons_f:cons_trunc:cons_gt:null_encArg:null_encode_f:null_encode_true:null_encode_gt:null_encode_trunc:null_encode_s:null_encode_0:null_encode_false:null_f:null_trunc:null_gt -> true:s:0:false:cons_f:cons_trunc:cons_gt:null_encArg:null_encode_f:null_encode_true:null_encode_gt:null_encode_trunc:null_encode_s:null_encode_0:null_encode_false:null_f:null_trunc:null_gt cons_gt :: true:s:0:false:cons_f:cons_trunc:cons_gt:null_encArg:null_encode_f:null_encode_true:null_encode_gt:null_encode_trunc:null_encode_s:null_encode_0:null_encode_false:null_f:null_trunc:null_gt -> true:s:0:false:cons_f:cons_trunc:cons_gt:null_encArg:null_encode_f:null_encode_true:null_encode_gt:null_encode_trunc:null_encode_s:null_encode_0:null_encode_false:null_f:null_trunc:null_gt -> true:s:0:false:cons_f:cons_trunc:cons_gt:null_encArg:null_encode_f:null_encode_true:null_encode_gt:null_encode_trunc:null_encode_s:null_encode_0:null_encode_false:null_f:null_trunc:null_gt encode_f :: true:s:0:false:cons_f:cons_trunc:cons_gt:null_encArg:null_encode_f:null_encode_true:null_encode_gt:null_encode_trunc:null_encode_s:null_encode_0:null_encode_false:null_f:null_trunc:null_gt -> true:s:0:false:cons_f:cons_trunc:cons_gt:null_encArg:null_encode_f:null_encode_true:null_encode_gt:null_encode_trunc:null_encode_s:null_encode_0:null_encode_false:null_f:null_trunc:null_gt -> true:s:0:false:cons_f:cons_trunc:cons_gt:null_encArg:null_encode_f:null_encode_true:null_encode_gt:null_encode_trunc:null_encode_s:null_encode_0:null_encode_false:null_f:null_trunc:null_gt -> true:s:0:false:cons_f:cons_trunc:cons_gt:null_encArg:null_encode_f:null_encode_true:null_encode_gt:null_encode_trunc:null_encode_s:null_encode_0:null_encode_false:null_f:null_trunc:null_gt encode_true :: true:s:0:false:cons_f:cons_trunc:cons_gt:null_encArg:null_encode_f:null_encode_true:null_encode_gt:null_encode_trunc:null_encode_s:null_encode_0:null_encode_false:null_f:null_trunc:null_gt encode_gt :: true:s:0:false:cons_f:cons_trunc:cons_gt:null_encArg:null_encode_f:null_encode_true:null_encode_gt:null_encode_trunc:null_encode_s:null_encode_0:null_encode_false:null_f:null_trunc:null_gt -> true:s:0:false:cons_f:cons_trunc:cons_gt:null_encArg:null_encode_f:null_encode_true:null_encode_gt:null_encode_trunc:null_encode_s:null_encode_0:null_encode_false:null_f:null_trunc:null_gt -> true:s:0:false:cons_f:cons_trunc:cons_gt:null_encArg:null_encode_f:null_encode_true:null_encode_gt:null_encode_trunc:null_encode_s:null_encode_0:null_encode_false:null_f:null_trunc:null_gt encode_trunc :: true:s:0:false:cons_f:cons_trunc:cons_gt:null_encArg:null_encode_f:null_encode_true:null_encode_gt:null_encode_trunc:null_encode_s:null_encode_0:null_encode_false:null_f:null_trunc:null_gt -> true:s:0:false:cons_f:cons_trunc:cons_gt:null_encArg:null_encode_f:null_encode_true:null_encode_gt:null_encode_trunc:null_encode_s:null_encode_0:null_encode_false:null_f:null_trunc:null_gt encode_s :: true:s:0:false:cons_f:cons_trunc:cons_gt:null_encArg:null_encode_f:null_encode_true:null_encode_gt:null_encode_trunc:null_encode_s:null_encode_0:null_encode_false:null_f:null_trunc:null_gt -> true:s:0:false:cons_f:cons_trunc:cons_gt:null_encArg:null_encode_f:null_encode_true:null_encode_gt:null_encode_trunc:null_encode_s:null_encode_0:null_encode_false:null_f:null_trunc:null_gt encode_0 :: true:s:0:false:cons_f:cons_trunc:cons_gt:null_encArg:null_encode_f:null_encode_true:null_encode_gt:null_encode_trunc:null_encode_s:null_encode_0:null_encode_false:null_f:null_trunc:null_gt encode_false :: true:s:0:false:cons_f:cons_trunc:cons_gt:null_encArg:null_encode_f:null_encode_true:null_encode_gt:null_encode_trunc:null_encode_s:null_encode_0:null_encode_false:null_f:null_trunc:null_gt null_encArg :: true:s:0:false:cons_f:cons_trunc:cons_gt:null_encArg:null_encode_f:null_encode_true:null_encode_gt:null_encode_trunc:null_encode_s:null_encode_0:null_encode_false:null_f:null_trunc:null_gt null_encode_f :: true:s:0:false:cons_f:cons_trunc:cons_gt:null_encArg:null_encode_f:null_encode_true:null_encode_gt:null_encode_trunc:null_encode_s:null_encode_0:null_encode_false:null_f:null_trunc:null_gt null_encode_true :: true:s:0:false:cons_f:cons_trunc:cons_gt:null_encArg:null_encode_f:null_encode_true:null_encode_gt:null_encode_trunc:null_encode_s:null_encode_0:null_encode_false:null_f:null_trunc:null_gt null_encode_gt :: true:s:0:false:cons_f:cons_trunc:cons_gt:null_encArg:null_encode_f:null_encode_true:null_encode_gt:null_encode_trunc:null_encode_s:null_encode_0:null_encode_false:null_f:null_trunc:null_gt null_encode_trunc :: true:s:0:false:cons_f:cons_trunc:cons_gt:null_encArg:null_encode_f:null_encode_true:null_encode_gt:null_encode_trunc:null_encode_s:null_encode_0:null_encode_false:null_f:null_trunc:null_gt null_encode_s :: true:s:0:false:cons_f:cons_trunc:cons_gt:null_encArg:null_encode_f:null_encode_true:null_encode_gt:null_encode_trunc:null_encode_s:null_encode_0:null_encode_false:null_f:null_trunc:null_gt null_encode_0 :: true:s:0:false:cons_f:cons_trunc:cons_gt:null_encArg:null_encode_f:null_encode_true:null_encode_gt:null_encode_trunc:null_encode_s:null_encode_0:null_encode_false:null_f:null_trunc:null_gt null_encode_false :: true:s:0:false:cons_f:cons_trunc:cons_gt:null_encArg:null_encode_f:null_encode_true:null_encode_gt:null_encode_trunc:null_encode_s:null_encode_0:null_encode_false:null_f:null_trunc:null_gt null_f :: true:s:0:false:cons_f:cons_trunc:cons_gt:null_encArg:null_encode_f:null_encode_true:null_encode_gt:null_encode_trunc:null_encode_s:null_encode_0:null_encode_false:null_f:null_trunc:null_gt null_trunc :: true:s:0:false:cons_f:cons_trunc:cons_gt:null_encArg:null_encode_f:null_encode_true:null_encode_gt:null_encode_trunc:null_encode_s:null_encode_0:null_encode_false:null_f:null_trunc:null_gt null_gt :: true:s:0:false:cons_f:cons_trunc:cons_gt:null_encArg:null_encode_f:null_encode_true:null_encode_gt:null_encode_trunc:null_encode_s:null_encode_0:null_encode_false:null_f:null_trunc: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_trunc => 0 null_encode_s => 0 null_encode_0 => 0 null_encode_false => 0 null_f => 0 null_trunc => 0 null_gt => 0 ---------------------------------------- (12) Obligation: Complexity RNTS consisting of the following rules: encArg(z) -{ 0 }-> trunc(encArg(x_1)) :|: z = 1 + x_1, x_1 >= 0 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 :|: encode_trunc(z) -{ 0 }-> trunc(encArg(x_1)) :|: x_1 >= 0, z = x_1 encode_trunc(z) -{ 0 }-> 0 :|: v0 >= 0, z = v0 f(z, z', z'') -{ 1 }-> f(gt(x, y), trunc(x), 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 trunc(z) -{ 1 }-> 0 :|: z = 0 trunc(z) -{ 1 }-> 0 :|: z = 1 + 0 trunc(z) -{ 0 }-> 0 :|: v0 >= 0, z = v0 trunc(z) -{ 1 }-> 1 + (1 + trunc(x)) :|: x >= 0, z = 1 + (1 + x) 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,[trunc(V1, Out)],[V1 >= 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(V1, Out)],[V1 >= 0]). eq(start(V1, V, V2),0,[fun5(Out)],[]). eq(start(V1, V, V2),0,[fun6(Out)],[]). eq(f(V1, V, V2, Out),1,[gt(V4, V3, Ret0),trunc(V4, Ret1),f(Ret0, Ret1, 1 + V3, Ret)],[Out = Ret,V1 = 2,V = V4,V2 = V3,V4 >= 0,V3 >= 0]). eq(trunc(V1, Out),1,[],[Out = 0,V1 = 0]). eq(trunc(V1, Out),1,[],[Out = 0,V1 = 1]). eq(trunc(V1, Out),1,[trunc(V5, Ret11)],[Out = 2 + Ret11,V5 >= 0,V1 = 2 + V5]). eq(gt(V1, V, Out),1,[],[Out = 1,V6 >= 0,V = V6,V1 = 0]). eq(gt(V1, V, Out),1,[],[Out = 2,V1 = 1 + V7,V = 0,V7 >= 0]). eq(gt(V1, V, Out),1,[gt(V8, V9, Ret2)],[Out = Ret2,V9 >= 0,V = 1 + V9,V1 = 1 + V8,V8 >= 0]). eq(encArg(V1, Out),0,[],[Out = 2,V1 = 2]). eq(encArg(V1, Out),0,[encArg(V10, Ret12)],[Out = 1 + Ret12,V1 = 1 + V10,V10 >= 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(V12, Ret01),encArg(V13, Ret13),encArg(V11, Ret21),f(Ret01, Ret13, Ret21, Ret3)],[Out = Ret3,V12 >= 0,V1 = 1 + V11 + V12 + V13,V11 >= 0,V13 >= 0]). eq(encArg(V1, Out),0,[encArg(V14, Ret02),trunc(Ret02, Ret4)],[Out = Ret4,V1 = 1 + V14,V14 >= 0]). eq(encArg(V1, Out),0,[encArg(V16, Ret03),encArg(V15, Ret14),gt(Ret03, Ret14, Ret5)],[Out = Ret5,V16 >= 0,V1 = 1 + V15 + V16,V15 >= 0]). eq(fun(V1, V, V2, Out),0,[encArg(V19, Ret04),encArg(V17, Ret15),encArg(V18, Ret22),f(Ret04, Ret15, Ret22, Ret6)],[Out = Ret6,V19 >= 0,V18 >= 0,V17 >= 0,V1 = V19,V = V17,V2 = V18]). eq(fun1(Out),0,[],[Out = 2]). eq(fun2(V1, V, Out),0,[encArg(V21, Ret05),encArg(V20, Ret16),gt(Ret05, Ret16, Ret7)],[Out = Ret7,V21 >= 0,V20 >= 0,V1 = V21,V = V20]). eq(fun3(V1, Out),0,[encArg(V22, Ret06),trunc(Ret06, Ret8)],[Out = Ret8,V22 >= 0,V1 = V22]). eq(fun4(V1, Out),0,[encArg(V23, Ret17)],[Out = 1 + Ret17,V23 >= 0,V1 = V23]). eq(fun5(Out),0,[],[Out = 0]). eq(fun6(Out),0,[],[Out = 1]). eq(encArg(V1, Out),0,[],[Out = 0,V24 >= 0,V1 = V24]). eq(fun(V1, V, V2, Out),0,[],[Out = 0,V26 >= 0,V2 = V27,V25 >= 0,V1 = V26,V = V25,V27 >= 0]). eq(fun1(Out),0,[],[Out = 0]). eq(fun2(V1, V, Out),0,[],[Out = 0,V29 >= 0,V28 >= 0,V1 = V29,V = V28]). eq(fun3(V1, Out),0,[],[Out = 0,V30 >= 0,V1 = V30]). eq(fun4(V1, Out),0,[],[Out = 0,V31 >= 0,V1 = V31]). eq(fun6(Out),0,[],[Out = 0]). eq(f(V1, V, V2, Out),0,[],[Out = 0,V32 >= 0,V2 = V33,V34 >= 0,V1 = V32,V = V34,V33 >= 0]). eq(trunc(V1, Out),0,[],[Out = 0,V35 >= 0,V1 = V35]). eq(gt(V1, V, Out),0,[],[Out = 0,V36 >= 0,V37 >= 0,V1 = V36,V = V37]). input_output_vars(f(V1,V,V2,Out),[V1,V,V2],[Out]). input_output_vars(trunc(V1,Out),[V1],[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(V1,Out),[V1],[Out]). input_output_vars(fun5(Out),[],[Out]). input_output_vars(fun6(Out),[],[Out]). CoFloCo proof output: Preprocessing Cost Relations ===================================== #### Computed strongly connected components 0. recursive : [gt/3] 1. recursive : [trunc/2] 2. recursive : [f/4] 3. recursive [non_tail,multiple] : [encArg/2] 4. non_recursive : [fun/4] 5. non_recursive : [fun1/1] 6. non_recursive : [fun2/3] 7. non_recursive : [fun3/2] 8. non_recursive : [fun4/2] 9. non_recursive : [fun5/1] 10. non_recursive : [fun6/1] 11. non_recursive : [start/3] #### Obtained direct recursion through partial evaluation 0. SCC is partially evaluated into gt/3 1. SCC is partially evaluated into trunc/2 2. SCC is partially evaluated into f/4 3. SCC is partially evaluated into encArg/2 4. SCC is partially evaluated into fun/4 5. SCC is partially evaluated into fun1/1 6. SCC is partially evaluated into fun2/3 7. SCC is partially evaluated into fun3/2 8. SCC is partially evaluated into fun4/2 9. SCC is completely evaluated into other SCCs 10. SCC is partially evaluated into fun6/1 11. SCC is partially evaluated into start/3 Control-Flow Refinement of Cost Relations ===================================== ### Specialization of cost equations gt/3 * CE 21 is refined into CE [41] * CE 19 is refined into CE [42] * CE 18 is refined into CE [43] * CE 20 is refined into CE [44] ### Cost equations --> "Loop" of gt/3 * CEs [44] --> Loop 25 * CEs [41] --> Loop 26 * CEs [42] --> Loop 27 * CEs [43] --> Loop 28 ### Ranking functions of CR gt(V1,V,Out) * RF of phase [25]: [V,V1] #### Partial ranking functions of CR gt(V1,V,Out) * Partial RF of phase [25]: - RF of loop [25:1]: V V1 ### Specialization of cost equations trunc/2 * CE 15 is refined into CE [45] * CE 14 is refined into CE [46] * CE 17 is refined into CE [47] * CE 16 is refined into CE [48] ### Cost equations --> "Loop" of trunc/2 * CEs [48] --> Loop 29 * CEs [45] --> Loop 30 * CEs [46,47] --> Loop 31 ### Ranking functions of CR trunc(V1,Out) * RF of phase [29]: [V1-1] #### Partial ranking functions of CR trunc(V1,Out) * Partial RF of phase [29]: - RF of loop [29:1]: V1-1 ### Specialization of cost equations f/4 * CE 13 is refined into CE [49] * CE 12 is refined into CE [50,51,52,53,54,55,56,57,58] ### Cost equations --> "Loop" of f/4 * CEs [58] --> Loop 32 * CEs [57] --> Loop 33 * CEs [56] --> Loop 34 * CEs [55] --> Loop 35 * CEs [54] --> Loop 36 * CEs [53] --> Loop 37 * CEs [52] --> Loop 38 * CEs [51] --> Loop 39 * CEs [50] --> Loop 40 * CEs [49] --> Loop 41 ### Ranking functions of CR f(V1,V,V2,Out) * RF of phase [32]: [V-V2] #### Partial ranking functions of CR f(V1,V,V2,Out) * Partial RF of phase [32]: - RF of loop [32:1]: V-V2 ### Specialization of cost equations encArg/2 * CE 24 is refined into CE [59] * CE 22 is refined into CE [60] * CE 25 is refined into CE [61] * CE 28 is refined into CE [62,63,64,65,66] * CE 23 is refined into CE [67] * CE 27 is refined into CE [68,69] * CE 26 is refined into CE [70,71] ### Cost equations --> "Loop" of encArg/2 * CEs [70,71] --> Loop 42 * CEs [69] --> Loop 43 * CEs [67] --> Loop 44 * CEs [68] --> Loop 45 * CEs [66] --> Loop 46 * CEs [63] --> Loop 47 * CEs [65] --> Loop 48 * CEs [62] --> Loop 49 * CEs [64] --> Loop 50 * CEs [59] --> Loop 51 * CEs [60] --> Loop 52 * CEs [61] --> Loop 53 ### Ranking functions of CR encArg(V1,Out) * RF of phase [42,43,44,45,46,47,48,49,50]: [V1] #### Partial ranking functions of CR encArg(V1,Out) * Partial RF of phase [42,43,44,45,46,47,48,49,50]: - RF of loop [42:1,42:2,42:3,43:1,44:1,45:1,46:1,46:2,47:1,47:2,48:1,48:2,49:1,49:2,50:1,50:2]: V1 ### Specialization of cost equations fun/4 * CE 29 is refined into CE [72,73,74,75,76,77,78,79,80,81,82,83,84,85,86,87,88,89,90,91,92,93,94,95,96,97,98,99,100,101,102,103,104,105,106] * CE 30 is refined into CE [107] ### Cost equations --> "Loop" of fun/4 * CEs [77,78,79,80,81,101,102,103] --> Loop 54 * CEs [74,83,87,96,99,105] --> Loop 55 * CEs [72,73,75,76,82,84,85,86,88,89,90,91,92,93,94,95,97,98,100,104,106,107] --> Loop 56 ### 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 31 is refined into CE [108] * CE 32 is refined into CE [109] ### Cost equations --> "Loop" of fun1/1 * CEs [108] --> Loop 57 * CEs [109] --> Loop 58 ### Ranking functions of CR fun1(Out) #### Partial ranking functions of CR fun1(Out) ### Specialization of cost equations fun2/3 * CE 33 is refined into CE [110,111,112,113,114,115,116,117,118,119,120,121,122,123,124,125,126,127,128,129,130,131,132,133,134,135] * CE 34 is refined into CE [136] ### Cost equations --> "Loop" of fun2/3 * CEs [118] --> Loop 59 * CEs [115,117,132] --> Loop 60 * CEs [116,133] --> Loop 61 * CEs [111,114,120,122,125,128] --> Loop 62 * CEs [110,113,119,124,127,130,134] --> Loop 63 * CEs [112,121,123,126,129,131,135,136] --> Loop 64 ### Ranking functions of CR fun2(V1,V,Out) #### Partial ranking functions of CR fun2(V1,V,Out) ### Specialization of cost equations fun3/2 * CE 35 is refined into CE [137,138,139,140,141] * CE 36 is refined into CE [142] ### Cost equations --> "Loop" of fun3/2 * CEs [138,140] --> Loop 65 * CEs [137,139,141,142] --> Loop 66 ### Ranking functions of CR fun3(V1,Out) #### Partial ranking functions of CR fun3(V1,Out) ### Specialization of cost equations fun4/2 * CE 37 is refined into CE [143,144,145] * CE 38 is refined into CE [146] ### Cost equations --> "Loop" of fun4/2 * CEs [145] --> Loop 67 * CEs [146] --> Loop 68 * CEs [143,144] --> Loop 69 ### Ranking functions of CR fun4(V1,Out) #### Partial ranking functions of CR fun4(V1,Out) ### Specialization of cost equations fun6/1 * CE 39 is refined into CE [147] * CE 40 is refined into CE [148] ### Cost equations --> "Loop" of fun6/1 * CEs [147] --> Loop 70 * CEs [148] --> Loop 71 ### Ranking functions of CR fun6(Out) #### Partial ranking functions of CR fun6(Out) ### Specialization of cost equations start/3 * CE 1 is refined into CE [149,150] * CE 2 is refined into CE [151,152] * CE 3 is refined into CE [153,154,155,156,157] * CE 4 is refined into CE [158,159,160] * CE 5 is refined into CE [161,162] * CE 6 is refined into CE [163,164] * CE 7 is refined into CE [165,166,167] * CE 8 is refined into CE [168,169] * CE 9 is refined into CE [170,171,172] * CE 10 is refined into CE [173] * CE 11 is refined into CE [174,175] ### Cost equations --> "Loop" of start/3 * CEs [149,150,151,152,153,154,155,156,157,158,159,160,161,162,163,164,165,166,167,168,169,170,171,172,173,174,175] --> Loop 72 ### 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 [[25],28]: 1*it(25)+1 Such that:it(25) =< V1 with precondition: [Out=1,V1>=1,V>=V1] * Chain [[25],27]: 1*it(25)+1 Such that:it(25) =< V with precondition: [Out=2,V>=1,V1>=V+1] * Chain [[25],26]: 1*it(25)+0 Such that:it(25) =< V with precondition: [Out=0,V1>=1,V>=1] * Chain [28]: 1 with precondition: [V1=0,Out=1,V>=0] * Chain [27]: 1 with precondition: [V=0,Out=2,V1>=1] * Chain [26]: 0 with precondition: [Out=0,V1>=0,V>=0] #### Cost of chains of trunc(V1,Out): * Chain [[29],31]: 1*it(29)+1 Such that:it(29) =< Out with precondition: [Out>=2,V1>=Out] * Chain [[29],30]: 1*it(29)+1 Such that:it(29) =< Out with precondition: [V1=Out+1,V1>=3] * Chain [31]: 1 with precondition: [Out=0,V1>=0] * Chain [30]: 1 with precondition: [V1=1,Out=0] #### Cost of chains of f(V1,V,V2,Out): * Chain [[32],41]: 3*it(32)+1*s(10)+2*s(11)+0 Such that:aux(4) =< V it(32) =< V-V2 s(10) =< it(32)*aux(4) s(12) =< it(32)*aux(4) s(11) =< s(12) with precondition: [V1=2,Out=0,V2>=1,V>=V2+1] * Chain [[32],37,41]: 3*it(32)+1*s(10)+2*s(11)+1*s(13)+2 Such that:aux(4) =< V s(13) =< V+1 it(32) =< V-V2 s(10) =< it(32)*aux(4) s(12) =< it(32)*aux(4) s(11) =< s(12) with precondition: [V1=2,Out=0,V2>=1,V>=V2+1] * Chain [[32],36,41]: 3*it(32)+1*s(10)+2*s(11)+1*s(14)+2*s(16)+2 Such that:s(14) =< V+1 it(32) =< V-V2 aux(5) =< V s(16) =< aux(5) s(10) =< it(32)*aux(5) s(12) =< it(32)*aux(5) s(11) =< s(12) with precondition: [V1=2,Out=0,V2>=1,V>=V2+1] * Chain [[32],35,41]: 3*it(32)+1*s(10)+2*s(11)+1*s(17)+3 Such that:it(32) =< V-V2 aux(6) =< V s(17) =< aux(6) s(10) =< it(32)*aux(6) s(12) =< it(32)*aux(6) s(11) =< s(12) with precondition: [V1=2,Out=0,V2>=1,V>=V2+1] * Chain [[32],34,41]: 3*it(32)+1*s(10)+2*s(11)+3*s(18)+3 Such that:it(32) =< V-V2 aux(8) =< V s(18) =< aux(8) s(10) =< it(32)*aux(8) s(12) =< it(32)*aux(8) s(11) =< s(12) with precondition: [V1=2,Out=0,V2>=1,V>=V2+1] * Chain [[32],33,41]: 3*it(32)+1*s(10)+2*s(11)+1*s(21)+3 Such that:it(32) =< V-V2 aux(9) =< V s(21) =< aux(9) s(10) =< it(32)*aux(9) s(12) =< it(32)*aux(9) s(11) =< s(12) with precondition: [V1=2,Out=0,V2>=1,V>=V2+2] * Chain [[32],33,40,41]: 3*it(32)+1*s(10)+2*s(11)+1*s(21)+6 Such that:it(32) =< V-V2 aux(10) =< V s(21) =< aux(10) s(10) =< it(32)*aux(10) s(12) =< it(32)*aux(10) s(11) =< s(12) with precondition: [V1=2,Out=0,V2>=1,V>=V2+2] * Chain [[32],33,37,41]: 3*it(32)+1*s(10)+2*s(11)+1*s(13)+1*s(21)+5 Such that:s(13) =< V+1 it(32) =< V-V2 aux(11) =< V s(21) =< aux(11) s(10) =< it(32)*aux(11) s(12) =< it(32)*aux(11) s(11) =< s(12) with precondition: [V1=2,Out=0,V2>=1,V>=V2+2] * Chain [41]: 0 with precondition: [Out=0,V1>=0,V>=0,V2>=0] * Chain [40,41]: 3 with precondition: [V1=2,V=0,Out=0,V2>=0] * Chain [39,41]: 3 with precondition: [V1=2,V2=0,Out=0,V>=1] * Chain [39,40,41]: 6 with precondition: [V1=2,V2=0,Out=0,V>=1] * Chain [39,37,41]: 1*s(13)+5 Such that:s(13) =< 2 with precondition: [V1=2,V2=0,Out=0,V>=1] * Chain [38,[32],41]: 5*it(32)+1*s(10)+2*s(11)+3 Such that:aux(12) =< V it(32) =< aux(12) s(10) =< it(32)*aux(12) s(12) =< it(32)*aux(12) s(11) =< s(12) with precondition: [V1=2,V2=0,Out=0,V>=2] * Chain [38,[32],37,41]: 5*it(32)+1*s(10)+2*s(11)+1*s(13)+5 Such that:s(13) =< V+1 aux(13) =< V it(32) =< aux(13) s(10) =< it(32)*aux(13) s(12) =< it(32)*aux(13) s(11) =< s(12) with precondition: [V1=2,V2=0,Out=0,V>=2] * Chain [38,[32],36,41]: 7*it(32)+1*s(10)+2*s(11)+1*s(14)+5 Such that:s(14) =< V+1 aux(14) =< V it(32) =< aux(14) s(10) =< it(32)*aux(14) s(12) =< it(32)*aux(14) s(11) =< s(12) with precondition: [V1=2,V2=0,Out=0,V>=2] * Chain [38,[32],35,41]: 6*it(32)+1*s(10)+2*s(11)+6 Such that:aux(15) =< V it(32) =< aux(15) s(10) =< it(32)*aux(15) s(12) =< it(32)*aux(15) s(11) =< s(12) with precondition: [V1=2,V2=0,Out=0,V>=2] * Chain [38,[32],34,41]: 8*it(32)+1*s(10)+2*s(11)+6 Such that:aux(16) =< V it(32) =< aux(16) s(10) =< it(32)*aux(16) s(12) =< it(32)*aux(16) s(11) =< s(12) with precondition: [V1=2,V2=0,Out=0,V>=2] * Chain [38,[32],33,41]: 6*it(32)+1*s(10)+2*s(11)+6 Such that:aux(17) =< V it(32) =< aux(17) s(10) =< it(32)*aux(17) s(12) =< it(32)*aux(17) s(11) =< s(12) with precondition: [V1=2,V2=0,Out=0,V>=3] * Chain [38,[32],33,40,41]: 6*it(32)+1*s(10)+2*s(11)+9 Such that:aux(18) =< V it(32) =< aux(18) s(10) =< it(32)*aux(18) s(12) =< it(32)*aux(18) s(11) =< s(12) with precondition: [V1=2,V2=0,Out=0,V>=3] * Chain [38,[32],33,37,41]: 6*it(32)+1*s(10)+2*s(11)+1*s(13)+8 Such that:s(13) =< V+1 aux(19) =< V it(32) =< aux(19) s(10) =< it(32)*aux(19) s(12) =< it(32)*aux(19) s(11) =< s(12) with precondition: [V1=2,V2=0,Out=0,V>=3] * Chain [38,41]: 2*s(23)+3 Such that:s(22) =< V s(23) =< s(22) with precondition: [V1=2,V2=0,Out=0,V>=2] * Chain [38,37,41]: 1*s(13)+2*s(23)+5 Such that:s(13) =< 2 s(22) =< V s(23) =< s(22) with precondition: [V1=2,V2=0,Out=0,V>=2] * Chain [38,36,41]: 1*s(14)+4*s(16)+5 Such that:s(14) =< 2 aux(20) =< V s(16) =< aux(20) with precondition: [V1=2,V2=0,Out=0,V>=2] * Chain [38,33,41]: 1*s(21)+2*s(23)+6 Such that:s(21) =< 2 s(22) =< V s(23) =< s(22) with precondition: [V1=2,V2=0,Out=0,V>=2] * Chain [38,33,40,41]: 1*s(21)+2*s(23)+9 Such that:s(21) =< 2 s(22) =< V s(23) =< s(22) with precondition: [V1=2,V2=0,Out=0,V>=2] * Chain [38,33,37,41]: 1*s(13)+1*s(21)+2*s(23)+8 Such that:s(21) =< 2 s(13) =< 3 s(22) =< V s(23) =< s(22) with precondition: [V1=2,V2=0,Out=0,V>=2] * Chain [37,41]: 1*s(13)+2 Such that:s(13) =< V2+1 with precondition: [V1=2,Out=0,V>=0,V2>=0] * Chain [36,41]: 1*s(14)+2*s(16)+2 Such that:s(15) =< V s(14) =< V2+1 s(16) =< s(15) with precondition: [V1=2,Out=0,V>=2,V2>=0] * Chain [35,41]: 1*s(17)+3 Such that:s(17) =< V with precondition: [V1=2,Out=0,V>=1,V2>=V] * Chain [34,41]: 3*s(18)+3 Such that:aux(7) =< V s(18) =< aux(7) with precondition: [V1=2,Out=0,V>=2,V2>=V] * Chain [33,41]: 1*s(21)+3 Such that:s(21) =< V2+1 with precondition: [V1=2,Out=0,V2>=1,V>=V2+1] * Chain [33,40,41]: 1*s(21)+6 Such that:s(21) =< V2+1 with precondition: [V1=2,Out=0,V2>=1,V>=V2+1] * Chain [33,37,41]: 1*s(13)+1*s(21)+5 Such that:s(21) =< V2+1 s(13) =< V2+2 with precondition: [V1=2,Out=0,V2>=1,V>=V2+1] #### Cost of chains of encArg(V1,Out): * Chain [53]: 0 with precondition: [V1=1,Out=1] * Chain [52]: 0 with precondition: [V1=2,Out=2] * Chain [51]: 0 with precondition: [Out=0,V1>=0] * Chain [multiple([42,43,44,45,46,47,48,49,50],[[53],[52],[51]])]: 11*it(42)+1*it(46)+1*it(47)+1*it(48)+1*it(49)+1*s(191)+104*s(192)+11*s(193)+16*s(195)+32*s(196)+1*s(197)+6*s(198)+1*s(206)+1*s(207)+1*s(208)+0 Such that:it([53]) =< 2/3*V1+1/3 aux(44) =< V1 aux(45) =< 2*V1+1 aux(46) =< V1/2 aux(47) =< 2/3*V1 aux(48) =< 2/5*V1 it(42) =< aux(44) it(46) =< aux(44) it(47) =< aux(44) it(48) =< aux(44) it(49) =< aux(44) it(50) =< aux(44) it([53]) =< aux(44) it([51]) =< aux(45) it([53]) =< aux(45) it(48) =< aux(46) it(47) =< aux(47) it(48) =< aux(47) it(46) =< aux(48) aux(33) =< aux(44) aux(42) =< aux(44)-1 aux(39) =< aux(44)-2 aux(36) =< aux(44)+2 aux(34) =< aux(44)+1 it(48) =< it([51])*(1/2)+aux(46) it(49) =< it([51])*(1/2)+aux(46) it(50) =< it([51])*(1/2)+aux(46) it(47) =< it([51])*(1/3)+aux(47) it(48) =< it([51])*(1/3)+aux(47) it(49) =< it([51])*(1/3)+aux(47) it(50) =< it([51])*(1/3)+aux(47) it(46) =< it([51])*(3/5)+it([53])*(1/5)+aux(48) it(47) =< it([51])*(3/5)+it([53])*(1/5)+aux(48) it(48) =< it([51])*(3/5)+it([53])*(1/5)+aux(48) it(49) =< it([51])*(3/5)+it([53])*(1/5)+aux(48) it(50) =< it([51])*(3/5)+it([53])*(1/5)+aux(48) s(197) =< aux(44)*3 s(203) =< aux(44)*2 s(208) =< it(50)*aux(33) s(207) =< it(48)*aux(42) s(206) =< it(46)*aux(39) s(201) =< it(42)*aux(33) s(191) =< it(42)*aux(36) s(199) =< it(42)*aux(34) s(192) =< s(201) s(198) =< s(203) s(193) =< s(199) s(195) =< s(192)*aux(44) s(200) =< s(192)*aux(44) s(196) =< s(200) with precondition: [V1>=1,Out>=0,V1>=Out] #### Cost of chains of fun(V1,V,V2,Out): * Chain [56]: 66*s(247)+6*s(248)+6*s(249)+6*s(250)+6*s(251)+6*s(258)+6*s(260)+6*s(261)+6*s(262)+6*s(264)+624*s(266)+36*s(267)+66*s(268)+96*s(269)+192*s(271)+596*s(278)+10*s(279)+10*s(280)+10*s(281)+10*s(282)+10*s(289)+10*s(291)+10*s(292)+10*s(293)+10*s(295)+1040*s(297)+60*s(298)+110*s(299)+160*s(300)+320*s(302)+110*s(309)+10*s(310)+10*s(311)+10*s(312)+10*s(313)+10*s(320)+10*s(322)+10*s(323)+10*s(324)+10*s(326)+1040*s(328)+60*s(329)+110*s(330)+160*s(331)+320*s(333)+7*s(334)+30*s(340)+35*s(342)+80*s(343)+160*s(345)+26*s(439)+262*s(443)+53*s(519)+32*s(982)+64*s(984)+1*s(1026)+9 Such that:s(1026) =< 4 aux(75) =< 1 aux(76) =< 2 aux(77) =< 3 aux(78) =< V1 aux(79) =< 2*V1+1 aux(80) =< V1/2 aux(81) =< 2/3*V1 aux(82) =< 2/3*V1+1/3 aux(83) =< 2/5*V1 aux(84) =< V aux(85) =< V+1 aux(86) =< 2*V+1 aux(87) =< V/2 aux(88) =< 2/3*V aux(89) =< 2/3*V+1/3 aux(90) =< 2/5*V aux(91) =< V2 aux(92) =< V2+1 aux(93) =< V2+2 aux(94) =< 2*V2+1 aux(95) =< V2/2 aux(96) =< 2/3*V2 aux(97) =< 2/3*V2+1/3 aux(98) =< 2/5*V2 s(443) =< aux(76) s(439) =< aux(77) s(245) =< aux(82) s(276) =< aux(89) s(334) =< aux(93) s(307) =< aux(97) s(278) =< aux(84) s(340) =< aux(85) s(519) =< aux(75) s(343) =< s(278)*aux(84) s(344) =< s(278)*aux(84) s(345) =< s(344) s(279) =< aux(84) s(280) =< aux(84) s(281) =< aux(84) s(282) =< aux(84) s(283) =< aux(84) s(276) =< aux(84) s(276) =< aux(86) s(281) =< aux(87) s(280) =< aux(88) s(281) =< aux(88) s(279) =< aux(90) s(284) =< aux(84) s(285) =< aux(84)-1 s(286) =< aux(84)-2 s(287) =< aux(84)+2 s(288) =< aux(84)+1 s(281) =< aux(86)*(1/2)+aux(87) s(282) =< aux(86)*(1/2)+aux(87) s(283) =< aux(86)*(1/2)+aux(87) s(280) =< aux(86)*(1/3)+aux(88) s(281) =< aux(86)*(1/3)+aux(88) s(282) =< aux(86)*(1/3)+aux(88) s(283) =< aux(86)*(1/3)+aux(88) s(279) =< aux(86)*(3/5)+s(276)*(1/5)+aux(90) s(280) =< aux(86)*(3/5)+s(276)*(1/5)+aux(90) s(281) =< aux(86)*(3/5)+s(276)*(1/5)+aux(90) s(282) =< aux(86)*(3/5)+s(276)*(1/5)+aux(90) s(283) =< aux(86)*(3/5)+s(276)*(1/5)+aux(90) s(289) =< aux(84)*3 s(290) =< aux(84)*2 s(291) =< s(283)*s(284) s(292) =< s(281)*s(285) s(293) =< s(279)*s(286) s(294) =< s(278)*s(284) s(295) =< s(278)*s(287) s(296) =< s(278)*s(288) s(297) =< s(294) s(298) =< s(290) s(299) =< s(296) s(300) =< s(297)*aux(84) s(301) =< s(297)*aux(84) s(302) =< s(301) s(247) =< aux(78) s(248) =< aux(78) s(249) =< aux(78) s(250) =< aux(78) s(251) =< aux(78) s(252) =< aux(78) s(245) =< aux(78) s(245) =< aux(79) s(250) =< aux(80) s(249) =< aux(81) s(250) =< aux(81) s(248) =< aux(83) s(253) =< aux(78) s(254) =< aux(78)-1 s(255) =< aux(78)-2 s(256) =< aux(78)+2 s(257) =< aux(78)+1 s(250) =< aux(79)*(1/2)+aux(80) s(251) =< aux(79)*(1/2)+aux(80) s(252) =< aux(79)*(1/2)+aux(80) s(249) =< aux(79)*(1/3)+aux(81) s(250) =< aux(79)*(1/3)+aux(81) s(251) =< aux(79)*(1/3)+aux(81) s(252) =< aux(79)*(1/3)+aux(81) s(248) =< aux(79)*(3/5)+s(245)*(1/5)+aux(83) s(249) =< aux(79)*(3/5)+s(245)*(1/5)+aux(83) s(250) =< aux(79)*(3/5)+s(245)*(1/5)+aux(83) s(251) =< aux(79)*(3/5)+s(245)*(1/5)+aux(83) s(252) =< aux(79)*(3/5)+s(245)*(1/5)+aux(83) s(258) =< aux(78)*3 s(259) =< aux(78)*2 s(260) =< s(252)*s(253) s(261) =< s(250)*s(254) s(262) =< s(248)*s(255) s(263) =< s(247)*s(253) s(264) =< s(247)*s(256) s(265) =< s(247)*s(257) s(266) =< s(263) s(267) =< s(259) s(268) =< s(265) s(269) =< s(266)*aux(78) s(270) =< s(266)*aux(78) s(271) =< s(270) s(342) =< aux(92) s(309) =< aux(91) s(310) =< aux(91) s(311) =< aux(91) s(312) =< aux(91) s(313) =< aux(91) s(314) =< aux(91) s(307) =< aux(91) s(307) =< aux(94) s(312) =< aux(95) s(311) =< aux(96) s(312) =< aux(96) s(310) =< aux(98) s(315) =< aux(91) s(316) =< aux(91)-1 s(317) =< aux(91)-2 s(318) =< aux(91)+2 s(319) =< aux(91)+1 s(312) =< aux(94)*(1/2)+aux(95) s(313) =< aux(94)*(1/2)+aux(95) s(314) =< aux(94)*(1/2)+aux(95) s(311) =< aux(94)*(1/3)+aux(96) s(312) =< aux(94)*(1/3)+aux(96) s(313) =< aux(94)*(1/3)+aux(96) s(314) =< aux(94)*(1/3)+aux(96) s(310) =< aux(94)*(3/5)+s(307)*(1/5)+aux(98) s(311) =< aux(94)*(3/5)+s(307)*(1/5)+aux(98) s(312) =< aux(94)*(3/5)+s(307)*(1/5)+aux(98) s(313) =< aux(94)*(3/5)+s(307)*(1/5)+aux(98) s(314) =< aux(94)*(3/5)+s(307)*(1/5)+aux(98) s(320) =< aux(91)*3 s(321) =< aux(91)*2 s(322) =< s(314)*s(315) s(323) =< s(312)*s(316) s(324) =< s(310)*s(317) s(325) =< s(309)*s(315) s(326) =< s(309)*s(318) s(327) =< s(309)*s(319) s(328) =< s(325) s(329) =< s(321) s(330) =< s(327) s(331) =< s(328)*aux(91) s(332) =< s(328)*aux(91) s(333) =< s(332) s(982) =< s(443)*aux(76) s(983) =< s(443)*aux(76) s(984) =< s(983) with precondition: [Out=0,V1>=0,V>=0,V2>=0] * Chain [55]: 22*s(1293)+2*s(1294)+2*s(1295)+2*s(1296)+2*s(1297)+2*s(1304)+2*s(1306)+2*s(1307)+2*s(1308)+2*s(1310)+208*s(1312)+12*s(1313)+22*s(1314)+32*s(1315)+64*s(1317)+150*s(1324)+3*s(1325)+3*s(1326)+3*s(1327)+3*s(1328)+3*s(1335)+3*s(1337)+3*s(1338)+3*s(1339)+3*s(1341)+312*s(1343)+18*s(1344)+33*s(1345)+48*s(1346)+96*s(1348)+6*s(1349)+9*s(1355)+30*s(1357)+24*s(1358)+48*s(1360)+9*s(1398)+6 Such that:aux(105) =< 1 aux(106) =< 3 aux(107) =< 4 aux(108) =< V1 aux(109) =< 2*V1+1 aux(110) =< V1/2 aux(111) =< 2/3*V1 aux(112) =< 2/3*V1+1/3 aux(113) =< 2/5*V1 aux(114) =< V aux(115) =< V+1 aux(116) =< 2*V+1 aux(117) =< V/2 aux(118) =< 2/3*V aux(119) =< 2/3*V+1/3 aux(120) =< 2/5*V s(1349) =< aux(107) s(1291) =< aux(112) s(1322) =< aux(119) s(1398) =< aux(105) s(1357) =< aux(106) s(1293) =< aux(108) s(1294) =< aux(108) s(1295) =< aux(108) s(1296) =< aux(108) s(1297) =< aux(108) s(1298) =< aux(108) s(1291) =< aux(108) s(1291) =< aux(109) s(1296) =< aux(110) s(1295) =< aux(111) s(1296) =< aux(111) s(1294) =< aux(113) s(1299) =< aux(108) s(1300) =< aux(108)-1 s(1301) =< aux(108)-2 s(1302) =< aux(108)+2 s(1303) =< aux(108)+1 s(1296) =< aux(109)*(1/2)+aux(110) s(1297) =< aux(109)*(1/2)+aux(110) s(1298) =< aux(109)*(1/2)+aux(110) s(1295) =< aux(109)*(1/3)+aux(111) s(1296) =< aux(109)*(1/3)+aux(111) s(1297) =< aux(109)*(1/3)+aux(111) s(1298) =< aux(109)*(1/3)+aux(111) s(1294) =< aux(109)*(3/5)+s(1291)*(1/5)+aux(113) s(1295) =< aux(109)*(3/5)+s(1291)*(1/5)+aux(113) s(1296) =< aux(109)*(3/5)+s(1291)*(1/5)+aux(113) s(1297) =< aux(109)*(3/5)+s(1291)*(1/5)+aux(113) s(1298) =< aux(109)*(3/5)+s(1291)*(1/5)+aux(113) s(1304) =< aux(108)*3 s(1305) =< aux(108)*2 s(1306) =< s(1298)*s(1299) s(1307) =< s(1296)*s(1300) s(1308) =< s(1294)*s(1301) s(1309) =< s(1293)*s(1299) s(1310) =< s(1293)*s(1302) s(1311) =< s(1293)*s(1303) s(1312) =< s(1309) s(1313) =< s(1305) s(1314) =< s(1311) s(1315) =< s(1312)*aux(108) s(1316) =< s(1312)*aux(108) s(1317) =< s(1316) s(1324) =< aux(114) s(1355) =< aux(115) s(1358) =< s(1324)*aux(114) s(1359) =< s(1324)*aux(114) s(1360) =< s(1359) s(1325) =< aux(114) s(1326) =< aux(114) s(1327) =< aux(114) s(1328) =< aux(114) s(1329) =< aux(114) s(1322) =< aux(114) s(1322) =< aux(116) s(1327) =< aux(117) s(1326) =< aux(118) s(1327) =< aux(118) s(1325) =< aux(120) s(1330) =< aux(114) s(1331) =< aux(114)-1 s(1332) =< aux(114)-2 s(1333) =< aux(114)+2 s(1334) =< aux(114)+1 s(1327) =< aux(116)*(1/2)+aux(117) s(1328) =< aux(116)*(1/2)+aux(117) s(1329) =< aux(116)*(1/2)+aux(117) s(1326) =< aux(116)*(1/3)+aux(118) s(1327) =< aux(116)*(1/3)+aux(118) s(1328) =< aux(116)*(1/3)+aux(118) s(1329) =< aux(116)*(1/3)+aux(118) s(1325) =< aux(116)*(3/5)+s(1322)*(1/5)+aux(120) s(1326) =< aux(116)*(3/5)+s(1322)*(1/5)+aux(120) s(1327) =< aux(116)*(3/5)+s(1322)*(1/5)+aux(120) s(1328) =< aux(116)*(3/5)+s(1322)*(1/5)+aux(120) s(1329) =< aux(116)*(3/5)+s(1322)*(1/5)+aux(120) s(1335) =< aux(114)*3 s(1336) =< aux(114)*2 s(1337) =< s(1329)*s(1330) s(1338) =< s(1327)*s(1331) s(1339) =< s(1325)*s(1332) s(1340) =< s(1324)*s(1330) s(1341) =< s(1324)*s(1333) s(1342) =< s(1324)*s(1334) s(1343) =< s(1340) s(1344) =< s(1336) s(1345) =< s(1342) s(1346) =< s(1343)*aux(114) s(1347) =< s(1343)*aux(114) s(1348) =< s(1347) with precondition: [V2=2,Out=0,V1>=0,V>=0] * Chain [54]: 55*s(1520)+5*s(1521)+5*s(1522)+5*s(1523)+5*s(1524)+5*s(1531)+5*s(1533)+5*s(1534)+5*s(1535)+5*s(1537)+520*s(1539)+30*s(1540)+55*s(1541)+80*s(1542)+160*s(1544)+33*s(1551)+3*s(1552)+3*s(1553)+3*s(1554)+3*s(1555)+3*s(1562)+3*s(1564)+3*s(1565)+3*s(1566)+3*s(1568)+312*s(1570)+18*s(1571)+33*s(1572)+48*s(1573)+96*s(1575)+2*s(1576)+326*s(1581)+36*s(1582)+10*s(1584)+48*s(1585)+96*s(1587)+2*s(1691)+10*s(1742)+9 Such that:aux(131) =< 1 aux(132) =< 2 aux(133) =< 3 aux(134) =< 4 aux(135) =< V1 aux(136) =< 2*V1+1 aux(137) =< V1/2 aux(138) =< 2/3*V1 aux(139) =< 2/3*V1+1/3 aux(140) =< 2/5*V1 aux(141) =< V2 aux(142) =< V2+1 aux(143) =< V2+2 aux(144) =< 2*V2+1 aux(145) =< V2/2 aux(146) =< 2/3*V2 aux(147) =< 2/3*V2+1/3 aux(148) =< 2/5*V2 s(1691) =< aux(134) s(1518) =< aux(139) s(1576) =< aux(143) s(1549) =< aux(147) s(1581) =< aux(132) s(1582) =< aux(133) s(1742) =< aux(131) s(1585) =< s(1581)*aux(132) s(1586) =< s(1581)*aux(132) s(1587) =< s(1586) s(1520) =< aux(135) s(1521) =< aux(135) s(1522) =< aux(135) s(1523) =< aux(135) s(1524) =< aux(135) s(1525) =< aux(135) s(1518) =< aux(135) s(1518) =< aux(136) s(1523) =< aux(137) s(1522) =< aux(138) s(1523) =< aux(138) s(1521) =< aux(140) s(1526) =< aux(135) s(1527) =< aux(135)-1 s(1528) =< aux(135)-2 s(1529) =< aux(135)+2 s(1530) =< aux(135)+1 s(1523) =< aux(136)*(1/2)+aux(137) s(1524) =< aux(136)*(1/2)+aux(137) s(1525) =< aux(136)*(1/2)+aux(137) s(1522) =< aux(136)*(1/3)+aux(138) s(1523) =< aux(136)*(1/3)+aux(138) s(1524) =< aux(136)*(1/3)+aux(138) s(1525) =< aux(136)*(1/3)+aux(138) s(1521) =< aux(136)*(3/5)+s(1518)*(1/5)+aux(140) s(1522) =< aux(136)*(3/5)+s(1518)*(1/5)+aux(140) s(1523) =< aux(136)*(3/5)+s(1518)*(1/5)+aux(140) s(1524) =< aux(136)*(3/5)+s(1518)*(1/5)+aux(140) s(1525) =< aux(136)*(3/5)+s(1518)*(1/5)+aux(140) s(1531) =< aux(135)*3 s(1532) =< aux(135)*2 s(1533) =< s(1525)*s(1526) s(1534) =< s(1523)*s(1527) s(1535) =< s(1521)*s(1528) s(1536) =< s(1520)*s(1526) s(1537) =< s(1520)*s(1529) s(1538) =< s(1520)*s(1530) s(1539) =< s(1536) s(1540) =< s(1532) s(1541) =< s(1538) s(1542) =< s(1539)*aux(135) s(1543) =< s(1539)*aux(135) s(1544) =< s(1543) s(1584) =< aux(142) s(1551) =< aux(141) s(1552) =< aux(141) s(1553) =< aux(141) s(1554) =< aux(141) s(1555) =< aux(141) s(1556) =< aux(141) s(1549) =< aux(141) s(1549) =< aux(144) s(1554) =< aux(145) s(1553) =< aux(146) s(1554) =< aux(146) s(1552) =< aux(148) s(1557) =< aux(141) s(1558) =< aux(141)-1 s(1559) =< aux(141)-2 s(1560) =< aux(141)+2 s(1561) =< aux(141)+1 s(1554) =< aux(144)*(1/2)+aux(145) s(1555) =< aux(144)*(1/2)+aux(145) s(1556) =< aux(144)*(1/2)+aux(145) s(1553) =< aux(144)*(1/3)+aux(146) s(1554) =< aux(144)*(1/3)+aux(146) s(1555) =< aux(144)*(1/3)+aux(146) s(1556) =< aux(144)*(1/3)+aux(146) s(1552) =< aux(144)*(3/5)+s(1549)*(1/5)+aux(148) s(1553) =< aux(144)*(3/5)+s(1549)*(1/5)+aux(148) s(1554) =< aux(144)*(3/5)+s(1549)*(1/5)+aux(148) s(1555) =< aux(144)*(3/5)+s(1549)*(1/5)+aux(148) s(1556) =< aux(144)*(3/5)+s(1549)*(1/5)+aux(148) s(1562) =< aux(141)*3 s(1563) =< aux(141)*2 s(1564) =< s(1556)*s(1557) s(1565) =< s(1554)*s(1558) s(1566) =< s(1552)*s(1559) s(1567) =< s(1551)*s(1557) s(1568) =< s(1551)*s(1560) s(1569) =< s(1551)*s(1561) s(1570) =< s(1567) s(1571) =< s(1563) s(1572) =< s(1569) s(1573) =< s(1570)*aux(141) s(1574) =< s(1570)*aux(141) s(1575) =< s(1574) with precondition: [V=2,Out=0,V1>=0,V2>=0] #### Cost of chains of fun1(Out): * Chain [58]: 0 with precondition: [Out=0] * Chain [57]: 0 with precondition: [Out=2] #### Cost of chains of fun2(V1,V,Out): * Chain [64]: 22*s(2054)+2*s(2055)+2*s(2056)+2*s(2057)+2*s(2058)+2*s(2065)+2*s(2067)+2*s(2068)+2*s(2069)+2*s(2071)+208*s(2073)+12*s(2074)+22*s(2075)+32*s(2076)+64*s(2078)+36*s(2085)+3*s(2086)+3*s(2087)+3*s(2088)+3*s(2089)+3*s(2096)+3*s(2098)+3*s(2099)+3*s(2100)+3*s(2102)+312*s(2104)+18*s(2105)+33*s(2106)+48*s(2107)+96*s(2109)+1*s(2175)+0 Such that:s(2175) =< 2 aux(170) =< V1 aux(171) =< 2*V1+1 aux(172) =< V1/2 aux(173) =< 2/3*V1 aux(174) =< 2/3*V1+1/3 aux(175) =< 2/5*V1 aux(176) =< V aux(177) =< 2*V+1 aux(178) =< V/2 aux(179) =< 2/3*V aux(180) =< 2/3*V+1/3 aux(181) =< 2/5*V s(2052) =< aux(174) s(2083) =< aux(180) s(2085) =< aux(176) s(2086) =< aux(176) s(2087) =< aux(176) s(2088) =< aux(176) s(2089) =< aux(176) s(2090) =< aux(176) s(2083) =< aux(176) s(2083) =< aux(177) s(2088) =< aux(178) s(2087) =< aux(179) s(2088) =< aux(179) s(2086) =< aux(181) s(2091) =< aux(176) s(2092) =< aux(176)-1 s(2093) =< aux(176)-2 s(2094) =< aux(176)+2 s(2095) =< aux(176)+1 s(2088) =< aux(177)*(1/2)+aux(178) s(2089) =< aux(177)*(1/2)+aux(178) s(2090) =< aux(177)*(1/2)+aux(178) s(2087) =< aux(177)*(1/3)+aux(179) s(2088) =< aux(177)*(1/3)+aux(179) s(2089) =< aux(177)*(1/3)+aux(179) s(2090) =< aux(177)*(1/3)+aux(179) s(2086) =< aux(177)*(3/5)+s(2083)*(1/5)+aux(181) s(2087) =< aux(177)*(3/5)+s(2083)*(1/5)+aux(181) s(2088) =< aux(177)*(3/5)+s(2083)*(1/5)+aux(181) s(2089) =< aux(177)*(3/5)+s(2083)*(1/5)+aux(181) s(2090) =< aux(177)*(3/5)+s(2083)*(1/5)+aux(181) s(2096) =< aux(176)*3 s(2097) =< aux(176)*2 s(2098) =< s(2090)*s(2091) s(2099) =< s(2088)*s(2092) s(2100) =< s(2086)*s(2093) s(2101) =< s(2085)*s(2091) s(2102) =< s(2085)*s(2094) s(2103) =< s(2085)*s(2095) s(2104) =< s(2101) s(2105) =< s(2097) s(2106) =< s(2103) s(2107) =< s(2104)*aux(176) s(2108) =< s(2104)*aux(176) s(2109) =< s(2108) s(2054) =< aux(170) s(2055) =< aux(170) s(2056) =< aux(170) s(2057) =< aux(170) s(2058) =< aux(170) s(2059) =< aux(170) s(2052) =< aux(170) s(2052) =< aux(171) s(2057) =< aux(172) s(2056) =< aux(173) s(2057) =< aux(173) s(2055) =< aux(175) s(2060) =< aux(170) s(2061) =< aux(170)-1 s(2062) =< aux(170)-2 s(2063) =< aux(170)+2 s(2064) =< aux(170)+1 s(2057) =< aux(171)*(1/2)+aux(172) s(2058) =< aux(171)*(1/2)+aux(172) s(2059) =< aux(171)*(1/2)+aux(172) s(2056) =< aux(171)*(1/3)+aux(173) s(2057) =< aux(171)*(1/3)+aux(173) s(2058) =< aux(171)*(1/3)+aux(173) s(2059) =< aux(171)*(1/3)+aux(173) s(2055) =< aux(171)*(3/5)+s(2052)*(1/5)+aux(175) s(2056) =< aux(171)*(3/5)+s(2052)*(1/5)+aux(175) s(2057) =< aux(171)*(3/5)+s(2052)*(1/5)+aux(175) s(2058) =< aux(171)*(3/5)+s(2052)*(1/5)+aux(175) s(2059) =< aux(171)*(3/5)+s(2052)*(1/5)+aux(175) s(2065) =< aux(170)*3 s(2066) =< aux(170)*2 s(2067) =< s(2059)*s(2060) s(2068) =< s(2057)*s(2061) s(2069) =< s(2055)*s(2062) s(2070) =< s(2054)*s(2060) s(2071) =< s(2054)*s(2063) s(2072) =< s(2054)*s(2064) s(2073) =< s(2070) s(2074) =< s(2066) s(2075) =< s(2072) s(2076) =< s(2073)*aux(170) s(2077) =< s(2073)*aux(170) s(2078) =< s(2077) with precondition: [Out=0,V1>=0,V>=0] * Chain [63]: 33*s(2216)+3*s(2217)+3*s(2218)+3*s(2219)+3*s(2220)+3*s(2227)+3*s(2229)+3*s(2230)+3*s(2231)+3*s(2233)+312*s(2235)+18*s(2236)+33*s(2237)+48*s(2238)+96*s(2240)+45*s(2247)+4*s(2248)+4*s(2249)+4*s(2250)+4*s(2251)+4*s(2258)+4*s(2260)+4*s(2261)+4*s(2262)+4*s(2264)+416*s(2266)+24*s(2267)+44*s(2268)+64*s(2269)+128*s(2271)+2*s(2397)+1 Such that:aux(183) =< 2 aux(184) =< V1 aux(185) =< 2*V1+1 aux(186) =< V1/2 aux(187) =< 2/3*V1 aux(188) =< 2/3*V1+1/3 aux(189) =< 2/5*V1 aux(190) =< V aux(191) =< 2*V+1 aux(192) =< V/2 aux(193) =< 2/3*V aux(194) =< 2/3*V+1/3 aux(195) =< 2/5*V s(2397) =< aux(183) s(2214) =< aux(188) s(2245) =< aux(194) s(2247) =< aux(190) s(2248) =< aux(190) s(2249) =< aux(190) s(2250) =< aux(190) s(2251) =< aux(190) s(2252) =< aux(190) s(2245) =< aux(190) s(2245) =< aux(191) s(2250) =< aux(192) s(2249) =< aux(193) s(2250) =< aux(193) s(2248) =< aux(195) s(2253) =< aux(190) s(2254) =< aux(190)-1 s(2255) =< aux(190)-2 s(2256) =< aux(190)+2 s(2257) =< aux(190)+1 s(2250) =< aux(191)*(1/2)+aux(192) s(2251) =< aux(191)*(1/2)+aux(192) s(2252) =< aux(191)*(1/2)+aux(192) s(2249) =< aux(191)*(1/3)+aux(193) s(2250) =< aux(191)*(1/3)+aux(193) s(2251) =< aux(191)*(1/3)+aux(193) s(2252) =< aux(191)*(1/3)+aux(193) s(2248) =< aux(191)*(3/5)+s(2245)*(1/5)+aux(195) s(2249) =< aux(191)*(3/5)+s(2245)*(1/5)+aux(195) s(2250) =< aux(191)*(3/5)+s(2245)*(1/5)+aux(195) s(2251) =< aux(191)*(3/5)+s(2245)*(1/5)+aux(195) s(2252) =< aux(191)*(3/5)+s(2245)*(1/5)+aux(195) s(2258) =< aux(190)*3 s(2259) =< aux(190)*2 s(2260) =< s(2252)*s(2253) s(2261) =< s(2250)*s(2254) s(2262) =< s(2248)*s(2255) s(2263) =< s(2247)*s(2253) s(2264) =< s(2247)*s(2256) s(2265) =< s(2247)*s(2257) s(2266) =< s(2263) s(2267) =< s(2259) s(2268) =< s(2265) s(2269) =< s(2266)*aux(190) s(2270) =< s(2266)*aux(190) s(2271) =< s(2270) s(2216) =< aux(184) s(2217) =< aux(184) s(2218) =< aux(184) s(2219) =< aux(184) s(2220) =< aux(184) s(2221) =< aux(184) s(2214) =< aux(184) s(2214) =< aux(185) s(2219) =< aux(186) s(2218) =< aux(187) s(2219) =< aux(187) s(2217) =< aux(189) s(2222) =< aux(184) s(2223) =< aux(184)-1 s(2224) =< aux(184)-2 s(2225) =< aux(184)+2 s(2226) =< aux(184)+1 s(2219) =< aux(185)*(1/2)+aux(186) s(2220) =< aux(185)*(1/2)+aux(186) s(2221) =< aux(185)*(1/2)+aux(186) s(2218) =< aux(185)*(1/3)+aux(187) s(2219) =< aux(185)*(1/3)+aux(187) s(2220) =< aux(185)*(1/3)+aux(187) s(2221) =< aux(185)*(1/3)+aux(187) s(2217) =< aux(185)*(3/5)+s(2214)*(1/5)+aux(189) s(2218) =< aux(185)*(3/5)+s(2214)*(1/5)+aux(189) s(2219) =< aux(185)*(3/5)+s(2214)*(1/5)+aux(189) s(2220) =< aux(185)*(3/5)+s(2214)*(1/5)+aux(189) s(2221) =< aux(185)*(3/5)+s(2214)*(1/5)+aux(189) s(2227) =< aux(184)*3 s(2228) =< aux(184)*2 s(2229) =< s(2221)*s(2222) s(2230) =< s(2219)*s(2223) s(2231) =< s(2217)*s(2224) s(2232) =< s(2216)*s(2222) s(2233) =< s(2216)*s(2225) s(2234) =< s(2216)*s(2226) s(2235) =< s(2232) s(2236) =< s(2228) s(2237) =< s(2234) s(2238) =< s(2235)*aux(184) s(2239) =< s(2235)*aux(184) s(2240) =< s(2239) with precondition: [Out=1,V1>=0,V>=0] * Chain [62]: 33*s(2436)+3*s(2437)+3*s(2438)+3*s(2439)+3*s(2440)+3*s(2447)+3*s(2449)+3*s(2450)+3*s(2451)+3*s(2453)+312*s(2455)+18*s(2456)+33*s(2457)+48*s(2458)+96*s(2460)+45*s(2467)+4*s(2468)+4*s(2469)+4*s(2470)+4*s(2471)+4*s(2478)+4*s(2480)+4*s(2481)+4*s(2482)+4*s(2484)+416*s(2486)+24*s(2487)+44*s(2488)+64*s(2489)+128*s(2491)+1*s(2648)+1 Such that:s(2648) =< 1 aux(197) =< V1 aux(198) =< 2*V1+1 aux(199) =< V1/2 aux(200) =< 2/3*V1 aux(201) =< 2/3*V1+1/3 aux(202) =< 2/5*V1 aux(203) =< V aux(204) =< 2*V+1 aux(205) =< V/2 aux(206) =< 2/3*V aux(207) =< 2/3*V+1/3 aux(208) =< 2/5*V s(2434) =< aux(201) s(2465) =< aux(207) s(2467) =< aux(203) s(2468) =< aux(203) s(2469) =< aux(203) s(2470) =< aux(203) s(2471) =< aux(203) s(2472) =< aux(203) s(2465) =< aux(203) s(2465) =< aux(204) s(2470) =< aux(205) s(2469) =< aux(206) s(2470) =< aux(206) s(2468) =< aux(208) s(2473) =< aux(203) s(2474) =< aux(203)-1 s(2475) =< aux(203)-2 s(2476) =< aux(203)+2 s(2477) =< aux(203)+1 s(2470) =< aux(204)*(1/2)+aux(205) s(2471) =< aux(204)*(1/2)+aux(205) s(2472) =< aux(204)*(1/2)+aux(205) s(2469) =< aux(204)*(1/3)+aux(206) s(2470) =< aux(204)*(1/3)+aux(206) s(2471) =< aux(204)*(1/3)+aux(206) s(2472) =< aux(204)*(1/3)+aux(206) s(2468) =< aux(204)*(3/5)+s(2465)*(1/5)+aux(208) s(2469) =< aux(204)*(3/5)+s(2465)*(1/5)+aux(208) s(2470) =< aux(204)*(3/5)+s(2465)*(1/5)+aux(208) s(2471) =< aux(204)*(3/5)+s(2465)*(1/5)+aux(208) s(2472) =< aux(204)*(3/5)+s(2465)*(1/5)+aux(208) s(2478) =< aux(203)*3 s(2479) =< aux(203)*2 s(2480) =< s(2472)*s(2473) s(2481) =< s(2470)*s(2474) s(2482) =< s(2468)*s(2475) s(2483) =< s(2467)*s(2473) s(2484) =< s(2467)*s(2476) s(2485) =< s(2467)*s(2477) s(2486) =< s(2483) s(2487) =< s(2479) s(2488) =< s(2485) s(2489) =< s(2486)*aux(203) s(2490) =< s(2486)*aux(203) s(2491) =< s(2490) s(2436) =< aux(197) s(2437) =< aux(197) s(2438) =< aux(197) s(2439) =< aux(197) s(2440) =< aux(197) s(2441) =< aux(197) s(2434) =< aux(197) s(2434) =< aux(198) s(2439) =< aux(199) s(2438) =< aux(200) s(2439) =< aux(200) s(2437) =< aux(202) s(2442) =< aux(197) s(2443) =< aux(197)-1 s(2444) =< aux(197)-2 s(2445) =< aux(197)+2 s(2446) =< aux(197)+1 s(2439) =< aux(198)*(1/2)+aux(199) s(2440) =< aux(198)*(1/2)+aux(199) s(2441) =< aux(198)*(1/2)+aux(199) s(2438) =< aux(198)*(1/3)+aux(200) s(2439) =< aux(198)*(1/3)+aux(200) s(2440) =< aux(198)*(1/3)+aux(200) s(2441) =< aux(198)*(1/3)+aux(200) s(2437) =< aux(198)*(3/5)+s(2434)*(1/5)+aux(202) s(2438) =< aux(198)*(3/5)+s(2434)*(1/5)+aux(202) s(2439) =< aux(198)*(3/5)+s(2434)*(1/5)+aux(202) s(2440) =< aux(198)*(3/5)+s(2434)*(1/5)+aux(202) s(2441) =< aux(198)*(3/5)+s(2434)*(1/5)+aux(202) s(2447) =< aux(197)*3 s(2448) =< aux(197)*2 s(2449) =< s(2441)*s(2442) s(2450) =< s(2439)*s(2443) s(2451) =< s(2437)*s(2444) s(2452) =< s(2436)*s(2442) s(2453) =< s(2436)*s(2445) s(2454) =< s(2436)*s(2446) s(2455) =< s(2452) s(2456) =< s(2448) s(2457) =< s(2454) s(2458) =< s(2455)*aux(197) s(2459) =< s(2455)*aux(197) s(2460) =< s(2459) with precondition: [Out=2,V1>=1,V>=0] * Chain [61]: 11*s(2655)+1*s(2656)+1*s(2657)+1*s(2658)+1*s(2659)+1*s(2666)+1*s(2668)+1*s(2669)+1*s(2670)+1*s(2672)+104*s(2674)+6*s(2675)+11*s(2676)+16*s(2677)+32*s(2679)+2*s(2680)+0 Such that:s(2649) =< V1 s(2650) =< 2*V1+1 s(2651) =< V1/2 s(2652) =< 2/3*V1 s(2653) =< 2/3*V1+1/3 s(2654) =< 2/5*V1 aux(209) =< 2 s(2680) =< aux(209) s(2655) =< s(2649) s(2656) =< s(2649) s(2657) =< s(2649) s(2658) =< s(2649) s(2659) =< s(2649) s(2660) =< s(2649) s(2653) =< s(2649) s(2653) =< s(2650) s(2658) =< s(2651) s(2657) =< s(2652) s(2658) =< s(2652) s(2656) =< s(2654) s(2661) =< s(2649) s(2662) =< s(2649)-1 s(2663) =< s(2649)-2 s(2664) =< s(2649)+2 s(2665) =< s(2649)+1 s(2658) =< s(2650)*(1/2)+s(2651) s(2659) =< s(2650)*(1/2)+s(2651) s(2660) =< s(2650)*(1/2)+s(2651) s(2657) =< s(2650)*(1/3)+s(2652) s(2658) =< s(2650)*(1/3)+s(2652) s(2659) =< s(2650)*(1/3)+s(2652) s(2660) =< s(2650)*(1/3)+s(2652) s(2656) =< s(2650)*(3/5)+s(2653)*(1/5)+s(2654) s(2657) =< s(2650)*(3/5)+s(2653)*(1/5)+s(2654) s(2658) =< s(2650)*(3/5)+s(2653)*(1/5)+s(2654) s(2659) =< s(2650)*(3/5)+s(2653)*(1/5)+s(2654) s(2660) =< s(2650)*(3/5)+s(2653)*(1/5)+s(2654) s(2666) =< s(2649)*3 s(2667) =< s(2649)*2 s(2668) =< s(2660)*s(2661) s(2669) =< s(2658)*s(2662) s(2670) =< s(2656)*s(2663) s(2671) =< s(2655)*s(2661) s(2672) =< s(2655)*s(2664) s(2673) =< s(2655)*s(2665) s(2674) =< s(2671) s(2675) =< s(2667) s(2676) =< s(2673) s(2677) =< s(2674)*s(2649) s(2678) =< s(2674)*s(2649) s(2679) =< s(2678) with precondition: [V=2,Out=0,V1>=0] * Chain [60]: 23*s(2688)+2*s(2689)+2*s(2690)+2*s(2691)+2*s(2692)+2*s(2699)+2*s(2701)+2*s(2702)+2*s(2703)+2*s(2705)+208*s(2707)+12*s(2708)+22*s(2709)+32*s(2710)+64*s(2712)+1 Such that:aux(211) =< V1 aux(212) =< 2*V1+1 aux(213) =< V1/2 aux(214) =< 2/3*V1 aux(215) =< 2/3*V1+1/3 aux(216) =< 2/5*V1 s(2686) =< aux(215) s(2688) =< aux(211) s(2689) =< aux(211) s(2690) =< aux(211) s(2691) =< aux(211) s(2692) =< aux(211) s(2693) =< aux(211) s(2686) =< aux(211) s(2686) =< aux(212) s(2691) =< aux(213) s(2690) =< aux(214) s(2691) =< aux(214) s(2689) =< aux(216) s(2694) =< aux(211) s(2695) =< aux(211)-1 s(2696) =< aux(211)-2 s(2697) =< aux(211)+2 s(2698) =< aux(211)+1 s(2691) =< aux(212)*(1/2)+aux(213) s(2692) =< aux(212)*(1/2)+aux(213) s(2693) =< aux(212)*(1/2)+aux(213) s(2690) =< aux(212)*(1/3)+aux(214) s(2691) =< aux(212)*(1/3)+aux(214) s(2692) =< aux(212)*(1/3)+aux(214) s(2693) =< aux(212)*(1/3)+aux(214) s(2689) =< aux(212)*(3/5)+s(2686)*(1/5)+aux(216) s(2690) =< aux(212)*(3/5)+s(2686)*(1/5)+aux(216) s(2691) =< aux(212)*(3/5)+s(2686)*(1/5)+aux(216) s(2692) =< aux(212)*(3/5)+s(2686)*(1/5)+aux(216) s(2693) =< aux(212)*(3/5)+s(2686)*(1/5)+aux(216) s(2699) =< aux(211)*3 s(2700) =< aux(211)*2 s(2701) =< s(2693)*s(2694) s(2702) =< s(2691)*s(2695) s(2703) =< s(2689)*s(2696) s(2704) =< s(2688)*s(2694) s(2705) =< s(2688)*s(2697) s(2706) =< s(2688)*s(2698) s(2707) =< s(2704) s(2708) =< s(2700) s(2709) =< s(2706) s(2710) =< s(2707)*aux(211) s(2711) =< s(2707)*aux(211) s(2712) =< s(2711) with precondition: [V=2,Out=1,V1>=0] * Chain [59]: 11*s(2751)+1*s(2752)+1*s(2753)+1*s(2754)+1*s(2755)+1*s(2762)+1*s(2764)+1*s(2765)+1*s(2766)+1*s(2768)+104*s(2770)+6*s(2771)+11*s(2772)+16*s(2773)+32*s(2775)+1*s(2776)+1 Such that:s(2776) =< 2 s(2745) =< V1 s(2746) =< 2*V1+1 s(2747) =< V1/2 s(2748) =< 2/3*V1 s(2749) =< 2/3*V1+1/3 s(2750) =< 2/5*V1 s(2751) =< s(2745) s(2752) =< s(2745) s(2753) =< s(2745) s(2754) =< s(2745) s(2755) =< s(2745) s(2756) =< s(2745) s(2749) =< s(2745) s(2749) =< s(2746) s(2754) =< s(2747) s(2753) =< s(2748) s(2754) =< s(2748) s(2752) =< s(2750) s(2757) =< s(2745) s(2758) =< s(2745)-1 s(2759) =< s(2745)-2 s(2760) =< s(2745)+2 s(2761) =< s(2745)+1 s(2754) =< s(2746)*(1/2)+s(2747) s(2755) =< s(2746)*(1/2)+s(2747) s(2756) =< s(2746)*(1/2)+s(2747) s(2753) =< s(2746)*(1/3)+s(2748) s(2754) =< s(2746)*(1/3)+s(2748) s(2755) =< s(2746)*(1/3)+s(2748) s(2756) =< s(2746)*(1/3)+s(2748) s(2752) =< s(2746)*(3/5)+s(2749)*(1/5)+s(2750) s(2753) =< s(2746)*(3/5)+s(2749)*(1/5)+s(2750) s(2754) =< s(2746)*(3/5)+s(2749)*(1/5)+s(2750) s(2755) =< s(2746)*(3/5)+s(2749)*(1/5)+s(2750) s(2756) =< s(2746)*(3/5)+s(2749)*(1/5)+s(2750) s(2762) =< s(2745)*3 s(2763) =< s(2745)*2 s(2764) =< s(2756)*s(2757) s(2765) =< s(2754)*s(2758) s(2766) =< s(2752)*s(2759) s(2767) =< s(2751)*s(2757) s(2768) =< s(2751)*s(2760) s(2769) =< s(2751)*s(2761) s(2770) =< s(2767) s(2771) =< s(2763) s(2772) =< s(2769) s(2773) =< s(2770)*s(2745) s(2774) =< s(2770)*s(2745) s(2775) =< s(2774) with precondition: [V=2,Out=2,V1>=3] #### Cost of chains of fun3(V1,Out): * Chain [66]: 11*s(3076)+1*s(3077)+1*s(3078)+1*s(3079)+1*s(3080)+1*s(3087)+1*s(3089)+1*s(3090)+1*s(3091)+1*s(3093)+104*s(3095)+6*s(3096)+11*s(3097)+16*s(3098)+32*s(3100)+1 Such that:s(3070) =< V1 s(3071) =< 2*V1+1 s(3072) =< V1/2 s(3073) =< 2/3*V1 s(3074) =< 2/3*V1+1/3 s(3075) =< 2/5*V1 s(3076) =< s(3070) s(3077) =< s(3070) s(3078) =< s(3070) s(3079) =< s(3070) s(3080) =< s(3070) s(3081) =< s(3070) s(3074) =< s(3070) s(3074) =< s(3071) s(3079) =< s(3072) s(3078) =< s(3073) s(3079) =< s(3073) s(3077) =< s(3075) s(3082) =< s(3070) s(3083) =< s(3070)-1 s(3084) =< s(3070)-2 s(3085) =< s(3070)+2 s(3086) =< s(3070)+1 s(3079) =< s(3071)*(1/2)+s(3072) s(3080) =< s(3071)*(1/2)+s(3072) s(3081) =< s(3071)*(1/2)+s(3072) s(3078) =< s(3071)*(1/3)+s(3073) s(3079) =< s(3071)*(1/3)+s(3073) s(3080) =< s(3071)*(1/3)+s(3073) s(3081) =< s(3071)*(1/3)+s(3073) s(3077) =< s(3071)*(3/5)+s(3074)*(1/5)+s(3075) s(3078) =< s(3071)*(3/5)+s(3074)*(1/5)+s(3075) s(3079) =< s(3071)*(3/5)+s(3074)*(1/5)+s(3075) s(3080) =< s(3071)*(3/5)+s(3074)*(1/5)+s(3075) s(3081) =< s(3071)*(3/5)+s(3074)*(1/5)+s(3075) s(3087) =< s(3070)*3 s(3088) =< s(3070)*2 s(3089) =< s(3081)*s(3082) s(3090) =< s(3079)*s(3083) s(3091) =< s(3077)*s(3084) s(3092) =< s(3076)*s(3082) s(3093) =< s(3076)*s(3085) s(3094) =< s(3076)*s(3086) s(3095) =< s(3092) s(3096) =< s(3088) s(3097) =< s(3094) s(3098) =< s(3095)*s(3070) s(3099) =< s(3095)*s(3070) s(3100) =< s(3099) with precondition: [Out=0,V1>=0] * Chain [65]: 13*s(3107)+1*s(3108)+1*s(3109)+1*s(3110)+1*s(3111)+1*s(3118)+1*s(3120)+1*s(3121)+1*s(3122)+1*s(3124)+104*s(3126)+6*s(3127)+11*s(3128)+16*s(3129)+32*s(3131)+2*s(3135)+1 Such that:s(3134) =< 2 aux(236) =< V1 s(3102) =< 2*V1+1 s(3103) =< V1/2 s(3104) =< 2/3*V1 s(3105) =< 2/3*V1+1/3 s(3106) =< 2/5*V1 s(3135) =< s(3134) s(3107) =< aux(236) s(3108) =< aux(236) s(3109) =< aux(236) s(3110) =< aux(236) s(3111) =< aux(236) s(3112) =< aux(236) s(3105) =< aux(236) s(3105) =< s(3102) s(3110) =< s(3103) s(3109) =< s(3104) s(3110) =< s(3104) s(3108) =< s(3106) s(3113) =< aux(236) s(3114) =< aux(236)-1 s(3115) =< aux(236)-2 s(3116) =< aux(236)+2 s(3117) =< aux(236)+1 s(3110) =< s(3102)*(1/2)+s(3103) s(3111) =< s(3102)*(1/2)+s(3103) s(3112) =< s(3102)*(1/2)+s(3103) s(3109) =< s(3102)*(1/3)+s(3104) s(3110) =< s(3102)*(1/3)+s(3104) s(3111) =< s(3102)*(1/3)+s(3104) s(3112) =< s(3102)*(1/3)+s(3104) s(3108) =< s(3102)*(3/5)+s(3105)*(1/5)+s(3106) s(3109) =< s(3102)*(3/5)+s(3105)*(1/5)+s(3106) s(3110) =< s(3102)*(3/5)+s(3105)*(1/5)+s(3106) s(3111) =< s(3102)*(3/5)+s(3105)*(1/5)+s(3106) s(3112) =< s(3102)*(3/5)+s(3105)*(1/5)+s(3106) s(3118) =< aux(236)*3 s(3119) =< aux(236)*2 s(3120) =< s(3112)*s(3113) s(3121) =< s(3110)*s(3114) s(3122) =< s(3108)*s(3115) s(3123) =< s(3107)*s(3113) s(3124) =< s(3107)*s(3116) s(3125) =< s(3107)*s(3117) s(3126) =< s(3123) s(3127) =< s(3119) s(3128) =< s(3125) s(3129) =< s(3126)*aux(236) s(3130) =< s(3126)*aux(236) s(3131) =< s(3130) with precondition: [Out>=2,V1>=Out] #### Cost of chains of fun4(V1,Out): * Chain [69]: 11*s(3142)+1*s(3143)+1*s(3144)+1*s(3145)+1*s(3146)+1*s(3153)+1*s(3155)+1*s(3156)+1*s(3157)+1*s(3159)+104*s(3161)+6*s(3162)+11*s(3163)+16*s(3164)+32*s(3166)+0 Such that:s(3136) =< V1 s(3137) =< 2*V1+1 s(3138) =< V1/2 s(3139) =< 2/3*V1 s(3140) =< 2/3*V1+1/3 s(3141) =< 2/5*V1 s(3142) =< s(3136) s(3143) =< s(3136) s(3144) =< s(3136) s(3145) =< s(3136) s(3146) =< s(3136) s(3147) =< s(3136) s(3140) =< s(3136) s(3140) =< s(3137) s(3145) =< s(3138) s(3144) =< s(3139) s(3145) =< s(3139) s(3143) =< s(3141) s(3148) =< s(3136) s(3149) =< s(3136)-1 s(3150) =< s(3136)-2 s(3151) =< s(3136)+2 s(3152) =< s(3136)+1 s(3145) =< s(3137)*(1/2)+s(3138) s(3146) =< s(3137)*(1/2)+s(3138) s(3147) =< s(3137)*(1/2)+s(3138) s(3144) =< s(3137)*(1/3)+s(3139) s(3145) =< s(3137)*(1/3)+s(3139) s(3146) =< s(3137)*(1/3)+s(3139) s(3147) =< s(3137)*(1/3)+s(3139) s(3143) =< s(3137)*(3/5)+s(3140)*(1/5)+s(3141) s(3144) =< s(3137)*(3/5)+s(3140)*(1/5)+s(3141) s(3145) =< s(3137)*(3/5)+s(3140)*(1/5)+s(3141) s(3146) =< s(3137)*(3/5)+s(3140)*(1/5)+s(3141) s(3147) =< s(3137)*(3/5)+s(3140)*(1/5)+s(3141) s(3153) =< s(3136)*3 s(3154) =< s(3136)*2 s(3155) =< s(3147)*s(3148) s(3156) =< s(3145)*s(3149) s(3157) =< s(3143)*s(3150) s(3158) =< s(3142)*s(3148) s(3159) =< s(3142)*s(3151) s(3160) =< s(3142)*s(3152) s(3161) =< s(3158) s(3162) =< s(3154) s(3163) =< s(3160) s(3164) =< s(3161)*s(3136) s(3165) =< s(3161)*s(3136) s(3166) =< s(3165) with precondition: [V1>=1,Out>=1,V1+1>=Out] * Chain [68]: 0 with precondition: [Out=0,V1>=0] * Chain [67]: 0 with precondition: [Out=1,V1>=0] #### Cost of chains of fun6(Out): * Chain [71]: 0 with precondition: [Out=0] * Chain [70]: 0 with precondition: [Out=1] #### Cost of chains of start(V1,V,V2): * Chain [72]: 10*s(3167)+952*s(3172)+45*s(3173)+24*s(3174)+50*s(3175)+8*s(3176)+16*s(3178)+93*s(3179)+602*s(3183)+112*s(3186)+224*s(3188)+325*s(3190)+29*s(3201)+29*s(3202)+29*s(3203)+29*s(3204)+29*s(3211)+29*s(3213)+29*s(3214)+29*s(3215)+29*s(3217)+3016*s(3219)+174*s(3220)+319*s(3221)+464*s(3222)+928*s(3224)+9*s(3250)+73*s(3256)+80*s(3257)+160*s(3259)+143*s(3286)+13*s(3287)+13*s(3288)+13*s(3289)+13*s(3290)+13*s(3297)+13*s(3299)+13*s(3300)+13*s(3301)+13*s(3303)+1352*s(3305)+78*s(3306)+143*s(3307)+208*s(3308)+416*s(3310)+24*s(3317)+24*s(3318)+24*s(3319)+24*s(3320)+24*s(3327)+24*s(3329)+24*s(3330)+24*s(3331)+24*s(3333)+2496*s(3335)+144*s(3336)+264*s(3337)+384*s(3338)+768*s(3340)+9 Such that:s(3170) =< V-V2 s(3242) =< V2 s(3245) =< 2*V2+1 s(3246) =< V2/2 s(3247) =< 2/3*V2 s(3248) =< 2/3*V2+1/3 s(3249) =< 2/5*V2 aux(237) =< 1 aux(238) =< 2 aux(239) =< 3 aux(240) =< 4 aux(241) =< V1 aux(242) =< 2*V1+1 aux(243) =< V1/2 aux(244) =< 2/3*V1 aux(245) =< 2/3*V1+1/3 aux(246) =< 2/5*V1 aux(247) =< V aux(248) =< V+1 aux(249) =< 2*V+1 aux(250) =< V/2 aux(251) =< 2/3*V aux(252) =< 2/3*V+1/3 aux(253) =< 2/5*V aux(254) =< V2+1 aux(255) =< V2+2 s(3256) =< aux(237) s(3183) =< aux(238) s(3179) =< aux(239) s(3190) =< aux(241) s(3198) =< aux(245) s(3172) =< aux(247) s(3167) =< aux(255) s(3250) =< aux(240) s(3253) =< s(3248) s(3257) =< s(3183)*aux(238) s(3258) =< s(3183)*aux(238) s(3259) =< s(3258) s(3201) =< aux(241) s(3202) =< aux(241) s(3203) =< aux(241) s(3204) =< aux(241) s(3205) =< aux(241) s(3198) =< aux(241) s(3198) =< aux(242) s(3203) =< aux(243) s(3202) =< aux(244) s(3203) =< aux(244) s(3201) =< aux(246) s(3206) =< aux(241) s(3207) =< aux(241)-1 s(3208) =< aux(241)-2 s(3209) =< aux(241)+2 s(3210) =< aux(241)+1 s(3203) =< aux(242)*(1/2)+aux(243) s(3204) =< aux(242)*(1/2)+aux(243) s(3205) =< aux(242)*(1/2)+aux(243) s(3202) =< aux(242)*(1/3)+aux(244) s(3203) =< aux(242)*(1/3)+aux(244) s(3204) =< aux(242)*(1/3)+aux(244) s(3205) =< aux(242)*(1/3)+aux(244) s(3201) =< aux(242)*(3/5)+s(3198)*(1/5)+aux(246) s(3202) =< aux(242)*(3/5)+s(3198)*(1/5)+aux(246) s(3203) =< aux(242)*(3/5)+s(3198)*(1/5)+aux(246) s(3204) =< aux(242)*(3/5)+s(3198)*(1/5)+aux(246) s(3205) =< aux(242)*(3/5)+s(3198)*(1/5)+aux(246) s(3211) =< aux(241)*3 s(3212) =< aux(241)*2 s(3213) =< s(3205)*s(3206) s(3214) =< s(3203)*s(3207) s(3215) =< s(3201)*s(3208) s(3216) =< s(3190)*s(3206) s(3217) =< s(3190)*s(3209) s(3218) =< s(3190)*s(3210) s(3219) =< s(3216) s(3220) =< s(3212) s(3221) =< s(3218) s(3222) =< s(3219)*aux(241) s(3223) =< s(3219)*aux(241) s(3224) =< s(3223) s(3175) =< aux(254) s(3286) =< s(3242) s(3287) =< s(3242) s(3288) =< s(3242) s(3289) =< s(3242) s(3290) =< s(3242) s(3291) =< s(3242) s(3253) =< s(3242) s(3253) =< s(3245) s(3289) =< s(3246) s(3288) =< s(3247) s(3289) =< s(3247) s(3287) =< s(3249) s(3292) =< s(3242) s(3293) =< s(3242)-1 s(3294) =< s(3242)-2 s(3295) =< s(3242)+2 s(3296) =< s(3242)+1 s(3289) =< s(3245)*(1/2)+s(3246) s(3290) =< s(3245)*(1/2)+s(3246) s(3291) =< s(3245)*(1/2)+s(3246) s(3288) =< s(3245)*(1/3)+s(3247) s(3289) =< s(3245)*(1/3)+s(3247) s(3290) =< s(3245)*(1/3)+s(3247) s(3291) =< s(3245)*(1/3)+s(3247) s(3287) =< s(3245)*(3/5)+s(3253)*(1/5)+s(3249) s(3288) =< s(3245)*(3/5)+s(3253)*(1/5)+s(3249) s(3289) =< s(3245)*(3/5)+s(3253)*(1/5)+s(3249) s(3290) =< s(3245)*(3/5)+s(3253)*(1/5)+s(3249) s(3291) =< s(3245)*(3/5)+s(3253)*(1/5)+s(3249) s(3297) =< s(3242)*3 s(3298) =< s(3242)*2 s(3299) =< s(3291)*s(3292) s(3300) =< s(3289)*s(3293) s(3301) =< s(3287)*s(3294) s(3302) =< s(3286)*s(3292) s(3303) =< s(3286)*s(3295) s(3304) =< s(3286)*s(3296) s(3305) =< s(3302) s(3306) =< s(3298) s(3307) =< s(3304) s(3308) =< s(3305)*s(3242) s(3309) =< s(3305)*s(3242) s(3310) =< s(3309) s(3311) =< aux(252) s(3173) =< aux(248) s(3186) =< s(3172)*aux(247) s(3187) =< s(3172)*aux(247) s(3188) =< s(3187) s(3317) =< aux(247) s(3318) =< aux(247) s(3319) =< aux(247) s(3320) =< aux(247) s(3321) =< aux(247) s(3311) =< aux(247) s(3311) =< aux(249) s(3319) =< aux(250) s(3318) =< aux(251) s(3319) =< aux(251) s(3317) =< aux(253) s(3322) =< aux(247) s(3323) =< aux(247)-1 s(3324) =< aux(247)-2 s(3325) =< aux(247)+2 s(3326) =< aux(247)+1 s(3319) =< aux(249)*(1/2)+aux(250) s(3320) =< aux(249)*(1/2)+aux(250) s(3321) =< aux(249)*(1/2)+aux(250) s(3318) =< aux(249)*(1/3)+aux(251) s(3319) =< aux(249)*(1/3)+aux(251) s(3320) =< aux(249)*(1/3)+aux(251) s(3321) =< aux(249)*(1/3)+aux(251) s(3317) =< aux(249)*(3/5)+s(3311)*(1/5)+aux(253) s(3318) =< aux(249)*(3/5)+s(3311)*(1/5)+aux(253) s(3319) =< aux(249)*(3/5)+s(3311)*(1/5)+aux(253) s(3320) =< aux(249)*(3/5)+s(3311)*(1/5)+aux(253) s(3321) =< aux(249)*(3/5)+s(3311)*(1/5)+aux(253) s(3327) =< aux(247)*3 s(3328) =< aux(247)*2 s(3329) =< s(3321)*s(3322) s(3330) =< s(3319)*s(3323) s(3331) =< s(3317)*s(3324) s(3332) =< s(3172)*s(3322) s(3333) =< s(3172)*s(3325) s(3334) =< s(3172)*s(3326) s(3335) =< s(3332) s(3336) =< s(3328) s(3337) =< s(3334) s(3338) =< s(3335)*aux(247) s(3339) =< s(3335)*aux(247) s(3340) =< s(3339) s(3174) =< s(3170) s(3176) =< s(3174)*aux(247) s(3177) =< s(3174)*aux(247) s(3178) =< s(3177) with precondition: [] Closed-form bounds of start(V1,V,V2): ------------------------------------- * Chain [72] with precondition: [] - Upper bound: nat(V1)*1253+2561+nat(V1)*3393*nat(V1)+nat(V1)*1392*nat(V1)*nat(V1)+nat(V1)*29*nat(nat(V1)+ -2)+nat(V1)*29*nat(nat(V1)+ -1)+nat(V)*1720+nat(V)*3144*nat(V)+nat(V)*1152*nat(V)*nat(V)+nat(V)*24*nat(nat(V)+ -2)+nat(V)*24*nat(nat(V)+ -1)+nat(V)*24*nat(V-V2)+nat(V2)*559+nat(V2)*1521*nat(V2)+nat(V2)*624*nat(V2)*nat(V2)+nat(V2)*13*nat(nat(V2)+ -2)+nat(V2)*13*nat(nat(V2)+ -1)+nat(V+1)*45+nat(V2+1)*50+nat(V2+2)*10+nat(V-V2)*24 - Complexity: n^3 ### Maximum cost of start(V1,V,V2): nat(V1)*1253+2561+nat(V1)*3393*nat(V1)+nat(V1)*1392*nat(V1)*nat(V1)+nat(V1)*29*nat(nat(V1)+ -2)+nat(V1)*29*nat(nat(V1)+ -1)+nat(V)*1720+nat(V)*3144*nat(V)+nat(V)*1152*nat(V)*nat(V)+nat(V)*24*nat(nat(V)+ -2)+nat(V)*24*nat(nat(V)+ -1)+nat(V)*24*nat(V-V2)+nat(V2)*559+nat(V2)*1521*nat(V2)+nat(V2)*624*nat(V2)*nat(V2)+nat(V2)*13*nat(nat(V2)+ -2)+nat(V2)*13*nat(nat(V2)+ -1)+nat(V+1)*45+nat(V2+1)*50+nat(V2+2)*10+nat(V-V2)*24 Asymptotic class: n^3 * Total analysis performed in 10677 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), trunc(x), s(y)) trunc(0') -> 0' trunc(s(0')) -> 0' trunc(s(s(x))) -> s(s(trunc(x))) 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_trunc(x_1)) -> trunc(encArg(x_1)) 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_trunc(x_1) -> trunc(encArg(x_1)) 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), trunc(x), s(y)) trunc(0') -> 0' trunc(s(0')) -> 0' trunc(s(s(x))) -> s(s(trunc(x))) 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_trunc(x_1)) -> trunc(encArg(x_1)) 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_trunc(x_1) -> trunc(encArg(x_1)) encode_s(x_1) -> s(encArg(x_1)) encode_0 -> 0' encode_false -> false Types: f :: true:s:0':false:cons_f:cons_trunc:cons_gt -> true:s:0':false:cons_f:cons_trunc:cons_gt -> true:s:0':false:cons_f:cons_trunc:cons_gt -> true:s:0':false:cons_f:cons_trunc:cons_gt true :: true:s:0':false:cons_f:cons_trunc:cons_gt gt :: true:s:0':false:cons_f:cons_trunc:cons_gt -> true:s:0':false:cons_f:cons_trunc:cons_gt -> true:s:0':false:cons_f:cons_trunc:cons_gt trunc :: true:s:0':false:cons_f:cons_trunc:cons_gt -> true:s:0':false:cons_f:cons_trunc:cons_gt s :: true:s:0':false:cons_f:cons_trunc:cons_gt -> true:s:0':false:cons_f:cons_trunc:cons_gt 0' :: true:s:0':false:cons_f:cons_trunc:cons_gt false :: true:s:0':false:cons_f:cons_trunc:cons_gt encArg :: true:s:0':false:cons_f:cons_trunc:cons_gt -> true:s:0':false:cons_f:cons_trunc:cons_gt cons_f :: true:s:0':false:cons_f:cons_trunc:cons_gt -> true:s:0':false:cons_f:cons_trunc:cons_gt -> true:s:0':false:cons_f:cons_trunc:cons_gt -> true:s:0':false:cons_f:cons_trunc:cons_gt cons_trunc :: true:s:0':false:cons_f:cons_trunc:cons_gt -> true:s:0':false:cons_f:cons_trunc:cons_gt cons_gt :: true:s:0':false:cons_f:cons_trunc:cons_gt -> true:s:0':false:cons_f:cons_trunc:cons_gt -> true:s:0':false:cons_f:cons_trunc:cons_gt encode_f :: true:s:0':false:cons_f:cons_trunc:cons_gt -> true:s:0':false:cons_f:cons_trunc:cons_gt -> true:s:0':false:cons_f:cons_trunc:cons_gt -> true:s:0':false:cons_f:cons_trunc:cons_gt encode_true :: true:s:0':false:cons_f:cons_trunc:cons_gt encode_gt :: true:s:0':false:cons_f:cons_trunc:cons_gt -> true:s:0':false:cons_f:cons_trunc:cons_gt -> true:s:0':false:cons_f:cons_trunc:cons_gt encode_trunc :: true:s:0':false:cons_f:cons_trunc:cons_gt -> true:s:0':false:cons_f:cons_trunc:cons_gt encode_s :: true:s:0':false:cons_f:cons_trunc:cons_gt -> true:s:0':false:cons_f:cons_trunc:cons_gt encode_0 :: true:s:0':false:cons_f:cons_trunc:cons_gt encode_false :: true:s:0':false:cons_f:cons_trunc:cons_gt hole_true:s:0':false:cons_f:cons_trunc:cons_gt1_4 :: true:s:0':false:cons_f:cons_trunc:cons_gt gen_true:s:0':false:cons_f:cons_trunc:cons_gt2_4 :: Nat -> true:s:0':false:cons_f:cons_trunc:cons_gt ---------------------------------------- (19) OrderProof (LOWER BOUND(ID)) Heuristically decided to analyse the following defined symbols: f, gt, trunc, encArg They will be analysed ascendingly in the following order: gt < f trunc < f f < encArg gt < encArg trunc < encArg ---------------------------------------- (20) Obligation: Innermost TRS: Rules: f(true, x, y) -> f(gt(x, y), trunc(x), s(y)) trunc(0') -> 0' trunc(s(0')) -> 0' trunc(s(s(x))) -> s(s(trunc(x))) 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_trunc(x_1)) -> trunc(encArg(x_1)) 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_trunc(x_1) -> trunc(encArg(x_1)) encode_s(x_1) -> s(encArg(x_1)) encode_0 -> 0' encode_false -> false Types: f :: true:s:0':false:cons_f:cons_trunc:cons_gt -> true:s:0':false:cons_f:cons_trunc:cons_gt -> true:s:0':false:cons_f:cons_trunc:cons_gt -> true:s:0':false:cons_f:cons_trunc:cons_gt true :: true:s:0':false:cons_f:cons_trunc:cons_gt gt :: true:s:0':false:cons_f:cons_trunc:cons_gt -> true:s:0':false:cons_f:cons_trunc:cons_gt -> true:s:0':false:cons_f:cons_trunc:cons_gt trunc :: true:s:0':false:cons_f:cons_trunc:cons_gt -> true:s:0':false:cons_f:cons_trunc:cons_gt s :: true:s:0':false:cons_f:cons_trunc:cons_gt -> true:s:0':false:cons_f:cons_trunc:cons_gt 0' :: true:s:0':false:cons_f:cons_trunc:cons_gt false :: true:s:0':false:cons_f:cons_trunc:cons_gt encArg :: true:s:0':false:cons_f:cons_trunc:cons_gt -> true:s:0':false:cons_f:cons_trunc:cons_gt cons_f :: true:s:0':false:cons_f:cons_trunc:cons_gt -> true:s:0':false:cons_f:cons_trunc:cons_gt -> true:s:0':false:cons_f:cons_trunc:cons_gt -> true:s:0':false:cons_f:cons_trunc:cons_gt cons_trunc :: true:s:0':false:cons_f:cons_trunc:cons_gt -> true:s:0':false:cons_f:cons_trunc:cons_gt cons_gt :: true:s:0':false:cons_f:cons_trunc:cons_gt -> true:s:0':false:cons_f:cons_trunc:cons_gt -> true:s:0':false:cons_f:cons_trunc:cons_gt encode_f :: true:s:0':false:cons_f:cons_trunc:cons_gt -> true:s:0':false:cons_f:cons_trunc:cons_gt -> true:s:0':false:cons_f:cons_trunc:cons_gt -> true:s:0':false:cons_f:cons_trunc:cons_gt encode_true :: true:s:0':false:cons_f:cons_trunc:cons_gt encode_gt :: true:s:0':false:cons_f:cons_trunc:cons_gt -> true:s:0':false:cons_f:cons_trunc:cons_gt -> true:s:0':false:cons_f:cons_trunc:cons_gt encode_trunc :: true:s:0':false:cons_f:cons_trunc:cons_gt -> true:s:0':false:cons_f:cons_trunc:cons_gt encode_s :: true:s:0':false:cons_f:cons_trunc:cons_gt -> true:s:0':false:cons_f:cons_trunc:cons_gt encode_0 :: true:s:0':false:cons_f:cons_trunc:cons_gt encode_false :: true:s:0':false:cons_f:cons_trunc:cons_gt hole_true:s:0':false:cons_f:cons_trunc:cons_gt1_4 :: true:s:0':false:cons_f:cons_trunc:cons_gt gen_true:s:0':false:cons_f:cons_trunc:cons_gt2_4 :: Nat -> true:s:0':false:cons_f:cons_trunc:cons_gt Generator Equations: gen_true:s:0':false:cons_f:cons_trunc:cons_gt2_4(0) <=> true gen_true:s:0':false:cons_f:cons_trunc:cons_gt2_4(+(x, 1)) <=> s(gen_true:s:0':false:cons_f:cons_trunc:cons_gt2_4(x)) The following defined symbols remain to be analysed: gt, f, trunc, encArg They will be analysed ascendingly in the following order: gt < f trunc < f f < encArg gt < encArg trunc < encArg ---------------------------------------- (21) RewriteLemmaProof (LOWER BOUND(ID)) Proved the following rewrite lemma: gt(gen_true:s:0':false:cons_f:cons_trunc:cons_gt2_4(+(1, n4_4)), gen_true:s:0':false:cons_f:cons_trunc:cons_gt2_4(+(1, n4_4))) -> *3_4, rt in Omega(n4_4) Induction Base: gt(gen_true:s:0':false:cons_f:cons_trunc:cons_gt2_4(+(1, 0)), gen_true:s:0':false:cons_f:cons_trunc:cons_gt2_4(+(1, 0))) Induction Step: gt(gen_true:s:0':false:cons_f:cons_trunc:cons_gt2_4(+(1, +(n4_4, 1))), gen_true:s:0':false:cons_f:cons_trunc:cons_gt2_4(+(1, +(n4_4, 1)))) ->_R^Omega(1) gt(gen_true:s:0':false:cons_f:cons_trunc:cons_gt2_4(+(1, n4_4)), gen_true:s:0':false:cons_f:cons_trunc: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), trunc(x), s(y)) trunc(0') -> 0' trunc(s(0')) -> 0' trunc(s(s(x))) -> s(s(trunc(x))) 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_trunc(x_1)) -> trunc(encArg(x_1)) 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_trunc(x_1) -> trunc(encArg(x_1)) encode_s(x_1) -> s(encArg(x_1)) encode_0 -> 0' encode_false -> false Types: f :: true:s:0':false:cons_f:cons_trunc:cons_gt -> true:s:0':false:cons_f:cons_trunc:cons_gt -> true:s:0':false:cons_f:cons_trunc:cons_gt -> true:s:0':false:cons_f:cons_trunc:cons_gt true :: true:s:0':false:cons_f:cons_trunc:cons_gt gt :: true:s:0':false:cons_f:cons_trunc:cons_gt -> true:s:0':false:cons_f:cons_trunc:cons_gt -> true:s:0':false:cons_f:cons_trunc:cons_gt trunc :: true:s:0':false:cons_f:cons_trunc:cons_gt -> true:s:0':false:cons_f:cons_trunc:cons_gt s :: true:s:0':false:cons_f:cons_trunc:cons_gt -> true:s:0':false:cons_f:cons_trunc:cons_gt 0' :: true:s:0':false:cons_f:cons_trunc:cons_gt false :: true:s:0':false:cons_f:cons_trunc:cons_gt encArg :: true:s:0':false:cons_f:cons_trunc:cons_gt -> true:s:0':false:cons_f:cons_trunc:cons_gt cons_f :: true:s:0':false:cons_f:cons_trunc:cons_gt -> true:s:0':false:cons_f:cons_trunc:cons_gt -> true:s:0':false:cons_f:cons_trunc:cons_gt -> true:s:0':false:cons_f:cons_trunc:cons_gt cons_trunc :: true:s:0':false:cons_f:cons_trunc:cons_gt -> true:s:0':false:cons_f:cons_trunc:cons_gt cons_gt :: true:s:0':false:cons_f:cons_trunc:cons_gt -> true:s:0':false:cons_f:cons_trunc:cons_gt -> true:s:0':false:cons_f:cons_trunc:cons_gt encode_f :: true:s:0':false:cons_f:cons_trunc:cons_gt -> true:s:0':false:cons_f:cons_trunc:cons_gt -> true:s:0':false:cons_f:cons_trunc:cons_gt -> true:s:0':false:cons_f:cons_trunc:cons_gt encode_true :: true:s:0':false:cons_f:cons_trunc:cons_gt encode_gt :: true:s:0':false:cons_f:cons_trunc:cons_gt -> true:s:0':false:cons_f:cons_trunc:cons_gt -> true:s:0':false:cons_f:cons_trunc:cons_gt encode_trunc :: true:s:0':false:cons_f:cons_trunc:cons_gt -> true:s:0':false:cons_f:cons_trunc:cons_gt encode_s :: true:s:0':false:cons_f:cons_trunc:cons_gt -> true:s:0':false:cons_f:cons_trunc:cons_gt encode_0 :: true:s:0':false:cons_f:cons_trunc:cons_gt encode_false :: true:s:0':false:cons_f:cons_trunc:cons_gt hole_true:s:0':false:cons_f:cons_trunc:cons_gt1_4 :: true:s:0':false:cons_f:cons_trunc:cons_gt gen_true:s:0':false:cons_f:cons_trunc:cons_gt2_4 :: Nat -> true:s:0':false:cons_f:cons_trunc:cons_gt Generator Equations: gen_true:s:0':false:cons_f:cons_trunc:cons_gt2_4(0) <=> true gen_true:s:0':false:cons_f:cons_trunc:cons_gt2_4(+(x, 1)) <=> s(gen_true:s:0':false:cons_f:cons_trunc:cons_gt2_4(x)) The following defined symbols remain to be analysed: gt, f, trunc, encArg They will be analysed ascendingly in the following order: gt < f trunc < f f < encArg gt < encArg trunc < 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), trunc(x), s(y)) trunc(0') -> 0' trunc(s(0')) -> 0' trunc(s(s(x))) -> s(s(trunc(x))) 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_trunc(x_1)) -> trunc(encArg(x_1)) 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_trunc(x_1) -> trunc(encArg(x_1)) encode_s(x_1) -> s(encArg(x_1)) encode_0 -> 0' encode_false -> false Types: f :: true:s:0':false:cons_f:cons_trunc:cons_gt -> true:s:0':false:cons_f:cons_trunc:cons_gt -> true:s:0':false:cons_f:cons_trunc:cons_gt -> true:s:0':false:cons_f:cons_trunc:cons_gt true :: true:s:0':false:cons_f:cons_trunc:cons_gt gt :: true:s:0':false:cons_f:cons_trunc:cons_gt -> true:s:0':false:cons_f:cons_trunc:cons_gt -> true:s:0':false:cons_f:cons_trunc:cons_gt trunc :: true:s:0':false:cons_f:cons_trunc:cons_gt -> true:s:0':false:cons_f:cons_trunc:cons_gt s :: true:s:0':false:cons_f:cons_trunc:cons_gt -> true:s:0':false:cons_f:cons_trunc:cons_gt 0' :: true:s:0':false:cons_f:cons_trunc:cons_gt false :: true:s:0':false:cons_f:cons_trunc:cons_gt encArg :: true:s:0':false:cons_f:cons_trunc:cons_gt -> true:s:0':false:cons_f:cons_trunc:cons_gt cons_f :: true:s:0':false:cons_f:cons_trunc:cons_gt -> true:s:0':false:cons_f:cons_trunc:cons_gt -> true:s:0':false:cons_f:cons_trunc:cons_gt -> true:s:0':false:cons_f:cons_trunc:cons_gt cons_trunc :: true:s:0':false:cons_f:cons_trunc:cons_gt -> true:s:0':false:cons_f:cons_trunc:cons_gt cons_gt :: true:s:0':false:cons_f:cons_trunc:cons_gt -> true:s:0':false:cons_f:cons_trunc:cons_gt -> true:s:0':false:cons_f:cons_trunc:cons_gt encode_f :: true:s:0':false:cons_f:cons_trunc:cons_gt -> true:s:0':false:cons_f:cons_trunc:cons_gt -> true:s:0':false:cons_f:cons_trunc:cons_gt -> true:s:0':false:cons_f:cons_trunc:cons_gt encode_true :: true:s:0':false:cons_f:cons_trunc:cons_gt encode_gt :: true:s:0':false:cons_f:cons_trunc:cons_gt -> true:s:0':false:cons_f:cons_trunc:cons_gt -> true:s:0':false:cons_f:cons_trunc:cons_gt encode_trunc :: true:s:0':false:cons_f:cons_trunc:cons_gt -> true:s:0':false:cons_f:cons_trunc:cons_gt encode_s :: true:s:0':false:cons_f:cons_trunc:cons_gt -> true:s:0':false:cons_f:cons_trunc:cons_gt encode_0 :: true:s:0':false:cons_f:cons_trunc:cons_gt encode_false :: true:s:0':false:cons_f:cons_trunc:cons_gt hole_true:s:0':false:cons_f:cons_trunc:cons_gt1_4 :: true:s:0':false:cons_f:cons_trunc:cons_gt gen_true:s:0':false:cons_f:cons_trunc:cons_gt2_4 :: Nat -> true:s:0':false:cons_f:cons_trunc:cons_gt Lemmas: gt(gen_true:s:0':false:cons_f:cons_trunc:cons_gt2_4(+(1, n4_4)), gen_true:s:0':false:cons_f:cons_trunc:cons_gt2_4(+(1, n4_4))) -> *3_4, rt in Omega(n4_4) Generator Equations: gen_true:s:0':false:cons_f:cons_trunc:cons_gt2_4(0) <=> true gen_true:s:0':false:cons_f:cons_trunc:cons_gt2_4(+(x, 1)) <=> s(gen_true:s:0':false:cons_f:cons_trunc:cons_gt2_4(x)) The following defined symbols remain to be analysed: trunc, f, encArg They will be analysed ascendingly in the following order: trunc < f f < encArg trunc < encArg ---------------------------------------- (27) RewriteLemmaProof (LOWER BOUND(ID)) Proved the following rewrite lemma: trunc(gen_true:s:0':false:cons_f:cons_trunc:cons_gt2_4(+(2, *(2, n1182_4)))) -> *3_4, rt in Omega(n1182_4) Induction Base: trunc(gen_true:s:0':false:cons_f:cons_trunc:cons_gt2_4(+(2, *(2, 0)))) Induction Step: trunc(gen_true:s:0':false:cons_f:cons_trunc:cons_gt2_4(+(2, *(2, +(n1182_4, 1))))) ->_R^Omega(1) s(s(trunc(gen_true:s:0':false:cons_f:cons_trunc:cons_gt2_4(+(2, *(2, n1182_4)))))) ->_IH s(s(*3_4)) We have rt in Omega(n^1) and sz in O(n). Thus, we have irc_R in Omega(n). ---------------------------------------- (28) Obligation: Innermost TRS: Rules: f(true, x, y) -> f(gt(x, y), trunc(x), s(y)) trunc(0') -> 0' trunc(s(0')) -> 0' trunc(s(s(x))) -> s(s(trunc(x))) 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_trunc(x_1)) -> trunc(encArg(x_1)) 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_trunc(x_1) -> trunc(encArg(x_1)) encode_s(x_1) -> s(encArg(x_1)) encode_0 -> 0' encode_false -> false Types: f :: true:s:0':false:cons_f:cons_trunc:cons_gt -> true:s:0':false:cons_f:cons_trunc:cons_gt -> true:s:0':false:cons_f:cons_trunc:cons_gt -> true:s:0':false:cons_f:cons_trunc:cons_gt true :: true:s:0':false:cons_f:cons_trunc:cons_gt gt :: true:s:0':false:cons_f:cons_trunc:cons_gt -> true:s:0':false:cons_f:cons_trunc:cons_gt -> true:s:0':false:cons_f:cons_trunc:cons_gt trunc :: true:s:0':false:cons_f:cons_trunc:cons_gt -> true:s:0':false:cons_f:cons_trunc:cons_gt s :: true:s:0':false:cons_f:cons_trunc:cons_gt -> true:s:0':false:cons_f:cons_trunc:cons_gt 0' :: true:s:0':false:cons_f:cons_trunc:cons_gt false :: true:s:0':false:cons_f:cons_trunc:cons_gt encArg :: true:s:0':false:cons_f:cons_trunc:cons_gt -> true:s:0':false:cons_f:cons_trunc:cons_gt cons_f :: true:s:0':false:cons_f:cons_trunc:cons_gt -> true:s:0':false:cons_f:cons_trunc:cons_gt -> true:s:0':false:cons_f:cons_trunc:cons_gt -> true:s:0':false:cons_f:cons_trunc:cons_gt cons_trunc :: true:s:0':false:cons_f:cons_trunc:cons_gt -> true:s:0':false:cons_f:cons_trunc:cons_gt cons_gt :: true:s:0':false:cons_f:cons_trunc:cons_gt -> true:s:0':false:cons_f:cons_trunc:cons_gt -> true:s:0':false:cons_f:cons_trunc:cons_gt encode_f :: true:s:0':false:cons_f:cons_trunc:cons_gt -> true:s:0':false:cons_f:cons_trunc:cons_gt -> true:s:0':false:cons_f:cons_trunc:cons_gt -> true:s:0':false:cons_f:cons_trunc:cons_gt encode_true :: true:s:0':false:cons_f:cons_trunc:cons_gt encode_gt :: true:s:0':false:cons_f:cons_trunc:cons_gt -> true:s:0':false:cons_f:cons_trunc:cons_gt -> true:s:0':false:cons_f:cons_trunc:cons_gt encode_trunc :: true:s:0':false:cons_f:cons_trunc:cons_gt -> true:s:0':false:cons_f:cons_trunc:cons_gt encode_s :: true:s:0':false:cons_f:cons_trunc:cons_gt -> true:s:0':false:cons_f:cons_trunc:cons_gt encode_0 :: true:s:0':false:cons_f:cons_trunc:cons_gt encode_false :: true:s:0':false:cons_f:cons_trunc:cons_gt hole_true:s:0':false:cons_f:cons_trunc:cons_gt1_4 :: true:s:0':false:cons_f:cons_trunc:cons_gt gen_true:s:0':false:cons_f:cons_trunc:cons_gt2_4 :: Nat -> true:s:0':false:cons_f:cons_trunc:cons_gt Lemmas: gt(gen_true:s:0':false:cons_f:cons_trunc:cons_gt2_4(+(1, n4_4)), gen_true:s:0':false:cons_f:cons_trunc:cons_gt2_4(+(1, n4_4))) -> *3_4, rt in Omega(n4_4) trunc(gen_true:s:0':false:cons_f:cons_trunc:cons_gt2_4(+(2, *(2, n1182_4)))) -> *3_4, rt in Omega(n1182_4) Generator Equations: gen_true:s:0':false:cons_f:cons_trunc:cons_gt2_4(0) <=> true gen_true:s:0':false:cons_f:cons_trunc:cons_gt2_4(+(x, 1)) <=> s(gen_true:s:0':false:cons_f:cons_trunc: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 ---------------------------------------- (29) RewriteLemmaProof (LOWER BOUND(ID)) Proved the following rewrite lemma: encArg(gen_true:s:0':false:cons_f:cons_trunc:cons_gt2_4(n3246_4)) -> gen_true:s:0':false:cons_f:cons_trunc:cons_gt2_4(n3246_4), rt in Omega(0) Induction Base: encArg(gen_true:s:0':false:cons_f:cons_trunc:cons_gt2_4(0)) ->_R^Omega(0) true Induction Step: encArg(gen_true:s:0':false:cons_f:cons_trunc:cons_gt2_4(+(n3246_4, 1))) ->_R^Omega(0) s(encArg(gen_true:s:0':false:cons_f:cons_trunc:cons_gt2_4(n3246_4))) ->_IH s(gen_true:s:0':false:cons_f:cons_trunc:cons_gt2_4(c3247_4)) We have rt in Omega(1) and sz in O(n). Thus, we have irc_R in Omega(n^0). ---------------------------------------- (30) BOUNDS(1, INF)