/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), 262 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, 3865 ms] (14) BOUNDS(1, n^3) (15) RenamingProof [BOTH BOUNDS(ID, ID), 0 ms] (16) CpxRelTRS (17) TypeInferenceProof [BOTH BOUNDS(ID, ID), 0 ms] (18) typed CpxTrs (19) OrderProof [LOWER BOUND(ID), 2 ms] (20) typed CpxTrs (21) RewriteLemmaProof [LOWER BOUND(ID), 507 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), 367 ms] (28) BOUNDS(1, INF) ---------------------------------------- (0) Obligation: The Derivational Complexity (innermost) of the given DCpxTrs could be proven to be BOUNDS(n^1, n^3). The TRS R consists of the following rules: cond(true, x) -> cond(and(even(x), gr(x, 0)), p(x)) and(x, false) -> false and(false, x) -> false and(true, true) -> true even(0) -> true even(s(0)) -> false even(s(s(x))) -> even(x) gr(0, x) -> false gr(s(x), 0) -> true gr(s(x), s(y)) -> gr(x, y) p(0) -> 0 p(s(x)) -> x S is empty. Rewrite Strategy: INNERMOST ---------------------------------------- (1) DerivationalComplexityToRuntimeComplexityProof (BOTH BOUNDS(ID, ID)) The following rules have been added to S to convert the given derivational complexity problem to a runtime complexity problem: encArg(true) -> true encArg(0) -> 0 encArg(false) -> false encArg(s(x_1)) -> s(encArg(x_1)) encArg(y) -> y encArg(cons_cond(x_1, x_2)) -> cond(encArg(x_1), encArg(x_2)) encArg(cons_and(x_1, x_2)) -> and(encArg(x_1), encArg(x_2)) encArg(cons_even(x_1)) -> even(encArg(x_1)) encArg(cons_gr(x_1, x_2)) -> gr(encArg(x_1), encArg(x_2)) encArg(cons_p(x_1)) -> p(encArg(x_1)) encode_cond(x_1, x_2) -> cond(encArg(x_1), encArg(x_2)) encode_true -> true encode_and(x_1, x_2) -> and(encArg(x_1), encArg(x_2)) encode_even(x_1) -> even(encArg(x_1)) encode_gr(x_1, x_2) -> gr(encArg(x_1), encArg(x_2)) encode_0 -> 0 encode_p(x_1) -> p(encArg(x_1)) encode_false -> false encode_s(x_1) -> s(encArg(x_1)) encode_y -> y ---------------------------------------- (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: cond(true, x) -> cond(and(even(x), gr(x, 0)), p(x)) and(x, false) -> false and(false, x) -> false and(true, true) -> true even(0) -> true even(s(0)) -> false even(s(s(x))) -> even(x) gr(0, x) -> false gr(s(x), 0) -> true gr(s(x), s(y)) -> gr(x, y) p(0) -> 0 p(s(x)) -> x The (relative) TRS S consists of the following rules: encArg(true) -> true encArg(0) -> 0 encArg(false) -> false encArg(s(x_1)) -> s(encArg(x_1)) encArg(y) -> y encArg(cons_cond(x_1, x_2)) -> cond(encArg(x_1), encArg(x_2)) encArg(cons_and(x_1, x_2)) -> and(encArg(x_1), encArg(x_2)) encArg(cons_even(x_1)) -> even(encArg(x_1)) encArg(cons_gr(x_1, x_2)) -> gr(encArg(x_1), encArg(x_2)) encArg(cons_p(x_1)) -> p(encArg(x_1)) encode_cond(x_1, x_2) -> cond(encArg(x_1), encArg(x_2)) encode_true -> true encode_and(x_1, x_2) -> and(encArg(x_1), encArg(x_2)) encode_even(x_1) -> even(encArg(x_1)) encode_gr(x_1, x_2) -> gr(encArg(x_1), encArg(x_2)) encode_0 -> 0 encode_p(x_1) -> p(encArg(x_1)) encode_false -> false encode_s(x_1) -> s(encArg(x_1)) encode_y -> y 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: cond(true, x) -> cond(and(even(x), gr(x, 0)), p(x)) and(x, false) -> false and(false, x) -> false and(true, true) -> true even(0) -> true even(s(0)) -> false even(s(s(x))) -> even(x) gr(0, x) -> false gr(s(x), 0) -> true gr(s(x), s(y)) -> gr(x, y) p(0) -> 0 p(s(x)) -> x The (relative) TRS S consists of the following rules: encArg(true) -> true encArg(0) -> 0 encArg(false) -> false encArg(s(x_1)) -> s(encArg(x_1)) encArg(y) -> y encArg(cons_cond(x_1, x_2)) -> cond(encArg(x_1), encArg(x_2)) encArg(cons_and(x_1, x_2)) -> and(encArg(x_1), encArg(x_2)) encArg(cons_even(x_1)) -> even(encArg(x_1)) encArg(cons_gr(x_1, x_2)) -> gr(encArg(x_1), encArg(x_2)) encArg(cons_p(x_1)) -> p(encArg(x_1)) encode_cond(x_1, x_2) -> cond(encArg(x_1), encArg(x_2)) encode_true -> true encode_and(x_1, x_2) -> and(encArg(x_1), encArg(x_2)) encode_even(x_1) -> even(encArg(x_1)) encode_gr(x_1, x_2) -> gr(encArg(x_1), encArg(x_2)) encode_0 -> 0 encode_p(x_1) -> p(encArg(x_1)) encode_false -> false encode_s(x_1) -> s(encArg(x_1)) encode_y -> y 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: cond(true, x) -> cond(and(even(x), gr(x, 0)), p(x)) [1] and(x, false) -> false [1] and(false, x) -> false [1] and(true, true) -> true [1] even(0) -> true [1] even(s(0)) -> false [1] even(s(s(x))) -> even(x) [1] gr(0, x) -> false [1] gr(s(x), 0) -> true [1] gr(s(x), s(y)) -> gr(x, y) [1] p(0) -> 0 [1] p(s(x)) -> x [1] encArg(true) -> true [0] encArg(0) -> 0 [0] encArg(false) -> false [0] encArg(s(x_1)) -> s(encArg(x_1)) [0] encArg(y) -> y [0] encArg(cons_cond(x_1, x_2)) -> cond(encArg(x_1), encArg(x_2)) [0] encArg(cons_and(x_1, x_2)) -> and(encArg(x_1), encArg(x_2)) [0] encArg(cons_even(x_1)) -> even(encArg(x_1)) [0] encArg(cons_gr(x_1, x_2)) -> gr(encArg(x_1), encArg(x_2)) [0] encArg(cons_p(x_1)) -> p(encArg(x_1)) [0] encode_cond(x_1, x_2) -> cond(encArg(x_1), encArg(x_2)) [0] encode_true -> true [0] encode_and(x_1, x_2) -> and(encArg(x_1), encArg(x_2)) [0] encode_even(x_1) -> even(encArg(x_1)) [0] encode_gr(x_1, x_2) -> gr(encArg(x_1), encArg(x_2)) [0] encode_0 -> 0 [0] encode_p(x_1) -> p(encArg(x_1)) [0] encode_false -> false [0] encode_s(x_1) -> s(encArg(x_1)) [0] encode_y -> y [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: cond(true, x) -> cond(and(even(x), gr(x, 0)), p(x)) [1] and(x, false) -> false [1] and(false, x) -> false [1] and(true, true) -> true [1] even(0) -> true [1] even(s(0)) -> false [1] even(s(s(x))) -> even(x) [1] gr(0, x) -> false [1] gr(s(x), 0) -> true [1] gr(s(x), s(y)) -> gr(x, y) [1] p(0) -> 0 [1] p(s(x)) -> x [1] encArg(true) -> true [0] encArg(0) -> 0 [0] encArg(false) -> false [0] encArg(s(x_1)) -> s(encArg(x_1)) [0] encArg(y) -> y [0] encArg(cons_cond(x_1, x_2)) -> cond(encArg(x_1), encArg(x_2)) [0] encArg(cons_and(x_1, x_2)) -> and(encArg(x_1), encArg(x_2)) [0] encArg(cons_even(x_1)) -> even(encArg(x_1)) [0] encArg(cons_gr(x_1, x_2)) -> gr(encArg(x_1), encArg(x_2)) [0] encArg(cons_p(x_1)) -> p(encArg(x_1)) [0] encode_cond(x_1, x_2) -> cond(encArg(x_1), encArg(x_2)) [0] encode_true -> true [0] encode_and(x_1, x_2) -> and(encArg(x_1), encArg(x_2)) [0] encode_even(x_1) -> even(encArg(x_1)) [0] encode_gr(x_1, x_2) -> gr(encArg(x_1), encArg(x_2)) [0] encode_0 -> 0 [0] encode_p(x_1) -> p(encArg(x_1)) [0] encode_false -> false [0] encode_s(x_1) -> s(encArg(x_1)) [0] encode_y -> y [0] The TRS has the following type information: cond :: true:0:false:s:y:cons_cond:cons_and:cons_even:cons_gr:cons_p -> true:0:false:s:y:cons_cond:cons_and:cons_even:cons_gr:cons_p -> true:0:false:s:y:cons_cond:cons_and:cons_even:cons_gr:cons_p true :: true:0:false:s:y:cons_cond:cons_and:cons_even:cons_gr:cons_p and :: true:0:false:s:y:cons_cond:cons_and:cons_even:cons_gr:cons_p -> true:0:false:s:y:cons_cond:cons_and:cons_even:cons_gr:cons_p -> true:0:false:s:y:cons_cond:cons_and:cons_even:cons_gr:cons_p even :: true:0:false:s:y:cons_cond:cons_and:cons_even:cons_gr:cons_p -> true:0:false:s:y:cons_cond:cons_and:cons_even:cons_gr:cons_p gr :: true:0:false:s:y:cons_cond:cons_and:cons_even:cons_gr:cons_p -> true:0:false:s:y:cons_cond:cons_and:cons_even:cons_gr:cons_p -> true:0:false:s:y:cons_cond:cons_and:cons_even:cons_gr:cons_p 0 :: true:0:false:s:y:cons_cond:cons_and:cons_even:cons_gr:cons_p p :: true:0:false:s:y:cons_cond:cons_and:cons_even:cons_gr:cons_p -> true:0:false:s:y:cons_cond:cons_and:cons_even:cons_gr:cons_p false :: true:0:false:s:y:cons_cond:cons_and:cons_even:cons_gr:cons_p s :: true:0:false:s:y:cons_cond:cons_and:cons_even:cons_gr:cons_p -> true:0:false:s:y:cons_cond:cons_and:cons_even:cons_gr:cons_p y :: true:0:false:s:y:cons_cond:cons_and:cons_even:cons_gr:cons_p encArg :: true:0:false:s:y:cons_cond:cons_and:cons_even:cons_gr:cons_p -> true:0:false:s:y:cons_cond:cons_and:cons_even:cons_gr:cons_p cons_cond :: true:0:false:s:y:cons_cond:cons_and:cons_even:cons_gr:cons_p -> true:0:false:s:y:cons_cond:cons_and:cons_even:cons_gr:cons_p -> true:0:false:s:y:cons_cond:cons_and:cons_even:cons_gr:cons_p cons_and :: true:0:false:s:y:cons_cond:cons_and:cons_even:cons_gr:cons_p -> true:0:false:s:y:cons_cond:cons_and:cons_even:cons_gr:cons_p -> true:0:false:s:y:cons_cond:cons_and:cons_even:cons_gr:cons_p cons_even :: true:0:false:s:y:cons_cond:cons_and:cons_even:cons_gr:cons_p -> true:0:false:s:y:cons_cond:cons_and:cons_even:cons_gr:cons_p cons_gr :: true:0:false:s:y:cons_cond:cons_and:cons_even:cons_gr:cons_p -> true:0:false:s:y:cons_cond:cons_and:cons_even:cons_gr:cons_p -> true:0:false:s:y:cons_cond:cons_and:cons_even:cons_gr:cons_p cons_p :: true:0:false:s:y:cons_cond:cons_and:cons_even:cons_gr:cons_p -> true:0:false:s:y:cons_cond:cons_and:cons_even:cons_gr:cons_p encode_cond :: true:0:false:s:y:cons_cond:cons_and:cons_even:cons_gr:cons_p -> true:0:false:s:y:cons_cond:cons_and:cons_even:cons_gr:cons_p -> true:0:false:s:y:cons_cond:cons_and:cons_even:cons_gr:cons_p encode_true :: true:0:false:s:y:cons_cond:cons_and:cons_even:cons_gr:cons_p encode_and :: true:0:false:s:y:cons_cond:cons_and:cons_even:cons_gr:cons_p -> true:0:false:s:y:cons_cond:cons_and:cons_even:cons_gr:cons_p -> true:0:false:s:y:cons_cond:cons_and:cons_even:cons_gr:cons_p encode_even :: true:0:false:s:y:cons_cond:cons_and:cons_even:cons_gr:cons_p -> true:0:false:s:y:cons_cond:cons_and:cons_even:cons_gr:cons_p encode_gr :: true:0:false:s:y:cons_cond:cons_and:cons_even:cons_gr:cons_p -> true:0:false:s:y:cons_cond:cons_and:cons_even:cons_gr:cons_p -> true:0:false:s:y:cons_cond:cons_and:cons_even:cons_gr:cons_p encode_0 :: true:0:false:s:y:cons_cond:cons_and:cons_even:cons_gr:cons_p encode_p :: true:0:false:s:y:cons_cond:cons_and:cons_even:cons_gr:cons_p -> true:0:false:s:y:cons_cond:cons_and:cons_even:cons_gr:cons_p encode_false :: true:0:false:s:y:cons_cond:cons_and:cons_even:cons_gr:cons_p encode_s :: true:0:false:s:y:cons_cond:cons_and:cons_even:cons_gr:cons_p -> true:0:false:s:y:cons_cond:cons_and:cons_even:cons_gr:cons_p encode_y :: true:0:false:s:y:cons_cond:cons_and:cons_even:cons_gr:cons_p 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_cond(v0, v1) -> null_encode_cond [0] encode_true -> null_encode_true [0] encode_and(v0, v1) -> null_encode_and [0] encode_even(v0) -> null_encode_even [0] encode_gr(v0, v1) -> null_encode_gr [0] encode_0 -> null_encode_0 [0] encode_p(v0) -> null_encode_p [0] encode_false -> null_encode_false [0] encode_s(v0) -> null_encode_s [0] encode_y -> null_encode_y [0] cond(v0, v1) -> null_cond [0] and(v0, v1) -> null_and [0] even(v0) -> null_even [0] gr(v0, v1) -> null_gr [0] p(v0) -> null_p [0] And the following fresh constants: null_encArg, null_encode_cond, null_encode_true, null_encode_and, null_encode_even, null_encode_gr, null_encode_0, null_encode_p, null_encode_false, null_encode_s, null_encode_y, null_cond, null_and, null_even, null_gr, null_p ---------------------------------------- (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: cond(true, x) -> cond(and(even(x), gr(x, 0)), p(x)) [1] and(x, false) -> false [1] and(false, x) -> false [1] and(true, true) -> true [1] even(0) -> true [1] even(s(0)) -> false [1] even(s(s(x))) -> even(x) [1] gr(0, x) -> false [1] gr(s(x), 0) -> true [1] gr(s(x), s(y)) -> gr(x, y) [1] p(0) -> 0 [1] p(s(x)) -> x [1] encArg(true) -> true [0] encArg(0) -> 0 [0] encArg(false) -> false [0] encArg(s(x_1)) -> s(encArg(x_1)) [0] encArg(y) -> y [0] encArg(cons_cond(x_1, x_2)) -> cond(encArg(x_1), encArg(x_2)) [0] encArg(cons_and(x_1, x_2)) -> and(encArg(x_1), encArg(x_2)) [0] encArg(cons_even(x_1)) -> even(encArg(x_1)) [0] encArg(cons_gr(x_1, x_2)) -> gr(encArg(x_1), encArg(x_2)) [0] encArg(cons_p(x_1)) -> p(encArg(x_1)) [0] encode_cond(x_1, x_2) -> cond(encArg(x_1), encArg(x_2)) [0] encode_true -> true [0] encode_and(x_1, x_2) -> and(encArg(x_1), encArg(x_2)) [0] encode_even(x_1) -> even(encArg(x_1)) [0] encode_gr(x_1, x_2) -> gr(encArg(x_1), encArg(x_2)) [0] encode_0 -> 0 [0] encode_p(x_1) -> p(encArg(x_1)) [0] encode_false -> false [0] encode_s(x_1) -> s(encArg(x_1)) [0] encode_y -> y [0] encArg(v0) -> null_encArg [0] encode_cond(v0, v1) -> null_encode_cond [0] encode_true -> null_encode_true [0] encode_and(v0, v1) -> null_encode_and [0] encode_even(v0) -> null_encode_even [0] encode_gr(v0, v1) -> null_encode_gr [0] encode_0 -> null_encode_0 [0] encode_p(v0) -> null_encode_p [0] encode_false -> null_encode_false [0] encode_s(v0) -> null_encode_s [0] encode_y -> null_encode_y [0] cond(v0, v1) -> null_cond [0] and(v0, v1) -> null_and [0] even(v0) -> null_even [0] gr(v0, v1) -> null_gr [0] p(v0) -> null_p [0] The TRS has the following type information: cond :: true:0:false:s:y:cons_cond:cons_and:cons_even:cons_gr:cons_p:null_encArg:null_encode_cond:null_encode_true:null_encode_and:null_encode_even:null_encode_gr:null_encode_0:null_encode_p:null_encode_false:null_encode_s:null_encode_y:null_cond:null_and:null_even:null_gr:null_p -> true:0:false:s:y:cons_cond:cons_and:cons_even:cons_gr:cons_p:null_encArg:null_encode_cond:null_encode_true:null_encode_and:null_encode_even:null_encode_gr:null_encode_0:null_encode_p:null_encode_false:null_encode_s:null_encode_y:null_cond:null_and:null_even:null_gr:null_p -> true:0:false:s:y:cons_cond:cons_and:cons_even:cons_gr:cons_p:null_encArg:null_encode_cond:null_encode_true:null_encode_and:null_encode_even:null_encode_gr:null_encode_0:null_encode_p:null_encode_false:null_encode_s:null_encode_y:null_cond:null_and:null_even:null_gr:null_p true :: true:0:false:s:y:cons_cond:cons_and:cons_even:cons_gr:cons_p:null_encArg:null_encode_cond:null_encode_true:null_encode_and:null_encode_even:null_encode_gr:null_encode_0:null_encode_p:null_encode_false:null_encode_s:null_encode_y:null_cond:null_and:null_even:null_gr:null_p and :: true:0:false:s:y:cons_cond:cons_and:cons_even:cons_gr:cons_p:null_encArg:null_encode_cond:null_encode_true:null_encode_and:null_encode_even:null_encode_gr:null_encode_0:null_encode_p:null_encode_false:null_encode_s:null_encode_y:null_cond:null_and:null_even:null_gr:null_p -> true:0:false:s:y:cons_cond:cons_and:cons_even:cons_gr:cons_p:null_encArg:null_encode_cond:null_encode_true:null_encode_and:null_encode_even:null_encode_gr:null_encode_0:null_encode_p:null_encode_false:null_encode_s:null_encode_y:null_cond:null_and:null_even:null_gr:null_p -> true:0:false:s:y:cons_cond:cons_and:cons_even:cons_gr:cons_p:null_encArg:null_encode_cond:null_encode_true:null_encode_and:null_encode_even:null_encode_gr:null_encode_0:null_encode_p:null_encode_false:null_encode_s:null_encode_y:null_cond:null_and:null_even:null_gr:null_p even :: true:0:false:s:y:cons_cond:cons_and:cons_even:cons_gr:cons_p:null_encArg:null_encode_cond:null_encode_true:null_encode_and:null_encode_even:null_encode_gr:null_encode_0:null_encode_p:null_encode_false:null_encode_s:null_encode_y:null_cond:null_and:null_even:null_gr:null_p -> true:0:false:s:y:cons_cond:cons_and:cons_even:cons_gr:cons_p:null_encArg:null_encode_cond:null_encode_true:null_encode_and:null_encode_even:null_encode_gr:null_encode_0:null_encode_p:null_encode_false:null_encode_s:null_encode_y:null_cond:null_and:null_even:null_gr:null_p gr :: true:0:false:s:y:cons_cond:cons_and:cons_even:cons_gr:cons_p:null_encArg:null_encode_cond:null_encode_true:null_encode_and:null_encode_even:null_encode_gr:null_encode_0:null_encode_p:null_encode_false:null_encode_s:null_encode_y:null_cond:null_and:null_even:null_gr:null_p -> true:0:false:s:y:cons_cond:cons_and:cons_even:cons_gr:cons_p:null_encArg:null_encode_cond:null_encode_true:null_encode_and:null_encode_even:null_encode_gr:null_encode_0:null_encode_p:null_encode_false:null_encode_s:null_encode_y:null_cond:null_and:null_even:null_gr:null_p -> true:0:false:s:y:cons_cond:cons_and:cons_even:cons_gr:cons_p:null_encArg:null_encode_cond:null_encode_true:null_encode_and:null_encode_even:null_encode_gr:null_encode_0:null_encode_p:null_encode_false:null_encode_s:null_encode_y:null_cond:null_and:null_even:null_gr:null_p 0 :: true:0:false:s:y:cons_cond:cons_and:cons_even:cons_gr:cons_p:null_encArg:null_encode_cond:null_encode_true:null_encode_and:null_encode_even:null_encode_gr:null_encode_0:null_encode_p:null_encode_false:null_encode_s:null_encode_y:null_cond:null_and:null_even:null_gr:null_p p :: true:0:false:s:y:cons_cond:cons_and:cons_even:cons_gr:cons_p:null_encArg:null_encode_cond:null_encode_true:null_encode_and:null_encode_even:null_encode_gr:null_encode_0:null_encode_p:null_encode_false:null_encode_s:null_encode_y:null_cond:null_and:null_even:null_gr:null_p -> true:0:false:s:y:cons_cond:cons_and:cons_even:cons_gr:cons_p:null_encArg:null_encode_cond:null_encode_true:null_encode_and:null_encode_even:null_encode_gr:null_encode_0:null_encode_p:null_encode_false:null_encode_s:null_encode_y:null_cond:null_and:null_even:null_gr:null_p false :: true:0:false:s:y:cons_cond:cons_and:cons_even:cons_gr:cons_p:null_encArg:null_encode_cond:null_encode_true:null_encode_and:null_encode_even:null_encode_gr:null_encode_0:null_encode_p:null_encode_false:null_encode_s:null_encode_y:null_cond:null_and:null_even:null_gr:null_p s :: true:0:false:s:y:cons_cond:cons_and:cons_even:cons_gr:cons_p:null_encArg:null_encode_cond:null_encode_true:null_encode_and:null_encode_even:null_encode_gr:null_encode_0:null_encode_p:null_encode_false:null_encode_s:null_encode_y:null_cond:null_and:null_even:null_gr:null_p -> true:0:false:s:y:cons_cond:cons_and:cons_even:cons_gr:cons_p:null_encArg:null_encode_cond:null_encode_true:null_encode_and:null_encode_even:null_encode_gr:null_encode_0:null_encode_p:null_encode_false:null_encode_s:null_encode_y:null_cond:null_and:null_even:null_gr:null_p y :: true:0:false:s:y:cons_cond:cons_and:cons_even:cons_gr:cons_p:null_encArg:null_encode_cond:null_encode_true:null_encode_and:null_encode_even:null_encode_gr:null_encode_0:null_encode_p:null_encode_false:null_encode_s:null_encode_y:null_cond:null_and:null_even:null_gr:null_p encArg :: true:0:false:s:y:cons_cond:cons_and:cons_even:cons_gr:cons_p:null_encArg:null_encode_cond:null_encode_true:null_encode_and:null_encode_even:null_encode_gr:null_encode_0:null_encode_p:null_encode_false:null_encode_s:null_encode_y:null_cond:null_and:null_even:null_gr:null_p -> true:0:false:s:y:cons_cond:cons_and:cons_even:cons_gr:cons_p:null_encArg:null_encode_cond:null_encode_true:null_encode_and:null_encode_even:null_encode_gr:null_encode_0:null_encode_p:null_encode_false:null_encode_s:null_encode_y:null_cond:null_and:null_even:null_gr:null_p cons_cond :: true:0:false:s:y:cons_cond:cons_and:cons_even:cons_gr:cons_p:null_encArg:null_encode_cond:null_encode_true:null_encode_and:null_encode_even:null_encode_gr:null_encode_0:null_encode_p:null_encode_false:null_encode_s:null_encode_y:null_cond:null_and:null_even:null_gr:null_p -> true:0:false:s:y:cons_cond:cons_and:cons_even:cons_gr:cons_p:null_encArg:null_encode_cond:null_encode_true:null_encode_and:null_encode_even:null_encode_gr:null_encode_0:null_encode_p:null_encode_false:null_encode_s:null_encode_y:null_cond:null_and:null_even:null_gr:null_p -> true:0:false:s:y:cons_cond:cons_and:cons_even:cons_gr:cons_p:null_encArg:null_encode_cond:null_encode_true:null_encode_and:null_encode_even:null_encode_gr:null_encode_0:null_encode_p:null_encode_false:null_encode_s:null_encode_y:null_cond:null_and:null_even:null_gr:null_p cons_and :: true:0:false:s:y:cons_cond:cons_and:cons_even:cons_gr:cons_p:null_encArg:null_encode_cond:null_encode_true:null_encode_and:null_encode_even:null_encode_gr:null_encode_0:null_encode_p:null_encode_false:null_encode_s:null_encode_y:null_cond:null_and:null_even:null_gr:null_p -> true:0:false:s:y:cons_cond:cons_and:cons_even:cons_gr:cons_p:null_encArg:null_encode_cond:null_encode_true:null_encode_and:null_encode_even:null_encode_gr:null_encode_0:null_encode_p:null_encode_false:null_encode_s:null_encode_y:null_cond:null_and:null_even:null_gr:null_p -> true:0:false:s:y:cons_cond:cons_and:cons_even:cons_gr:cons_p:null_encArg:null_encode_cond:null_encode_true:null_encode_and:null_encode_even:null_encode_gr:null_encode_0:null_encode_p:null_encode_false:null_encode_s:null_encode_y:null_cond:null_and:null_even:null_gr:null_p cons_even :: true:0:false:s:y:cons_cond:cons_and:cons_even:cons_gr:cons_p:null_encArg:null_encode_cond:null_encode_true:null_encode_and:null_encode_even:null_encode_gr:null_encode_0:null_encode_p:null_encode_false:null_encode_s:null_encode_y:null_cond:null_and:null_even:null_gr:null_p -> true:0:false:s:y:cons_cond:cons_and:cons_even:cons_gr:cons_p:null_encArg:null_encode_cond:null_encode_true:null_encode_and:null_encode_even:null_encode_gr:null_encode_0:null_encode_p:null_encode_false:null_encode_s:null_encode_y:null_cond:null_and:null_even:null_gr:null_p cons_gr :: true:0:false:s:y:cons_cond:cons_and:cons_even:cons_gr:cons_p:null_encArg:null_encode_cond:null_encode_true:null_encode_and:null_encode_even:null_encode_gr:null_encode_0:null_encode_p:null_encode_false:null_encode_s:null_encode_y:null_cond:null_and:null_even:null_gr:null_p -> true:0:false:s:y:cons_cond:cons_and:cons_even:cons_gr:cons_p:null_encArg:null_encode_cond:null_encode_true:null_encode_and:null_encode_even:null_encode_gr:null_encode_0:null_encode_p:null_encode_false:null_encode_s:null_encode_y:null_cond:null_and:null_even:null_gr:null_p -> true:0:false:s:y:cons_cond:cons_and:cons_even:cons_gr:cons_p:null_encArg:null_encode_cond:null_encode_true:null_encode_and:null_encode_even:null_encode_gr:null_encode_0:null_encode_p:null_encode_false:null_encode_s:null_encode_y:null_cond:null_and:null_even:null_gr:null_p cons_p :: true:0:false:s:y:cons_cond:cons_and:cons_even:cons_gr:cons_p:null_encArg:null_encode_cond:null_encode_true:null_encode_and:null_encode_even:null_encode_gr:null_encode_0:null_encode_p:null_encode_false:null_encode_s:null_encode_y:null_cond:null_and:null_even:null_gr:null_p -> true:0:false:s:y:cons_cond:cons_and:cons_even:cons_gr:cons_p:null_encArg:null_encode_cond:null_encode_true:null_encode_and:null_encode_even:null_encode_gr:null_encode_0:null_encode_p:null_encode_false:null_encode_s:null_encode_y:null_cond:null_and:null_even:null_gr:null_p encode_cond :: true:0:false:s:y:cons_cond:cons_and:cons_even:cons_gr:cons_p:null_encArg:null_encode_cond:null_encode_true:null_encode_and:null_encode_even:null_encode_gr:null_encode_0:null_encode_p:null_encode_false:null_encode_s:null_encode_y:null_cond:null_and:null_even:null_gr:null_p -> true:0:false:s:y:cons_cond:cons_and:cons_even:cons_gr:cons_p:null_encArg:null_encode_cond:null_encode_true:null_encode_and:null_encode_even:null_encode_gr:null_encode_0:null_encode_p:null_encode_false:null_encode_s:null_encode_y:null_cond:null_and:null_even:null_gr:null_p -> true:0:false:s:y:cons_cond:cons_and:cons_even:cons_gr:cons_p:null_encArg:null_encode_cond:null_encode_true:null_encode_and:null_encode_even:null_encode_gr:null_encode_0:null_encode_p:null_encode_false:null_encode_s:null_encode_y:null_cond:null_and:null_even:null_gr:null_p encode_true :: true:0:false:s:y:cons_cond:cons_and:cons_even:cons_gr:cons_p:null_encArg:null_encode_cond:null_encode_true:null_encode_and:null_encode_even:null_encode_gr:null_encode_0:null_encode_p:null_encode_false:null_encode_s:null_encode_y:null_cond:null_and:null_even:null_gr:null_p encode_and :: true:0:false:s:y:cons_cond:cons_and:cons_even:cons_gr:cons_p:null_encArg:null_encode_cond:null_encode_true:null_encode_and:null_encode_even:null_encode_gr:null_encode_0:null_encode_p:null_encode_false:null_encode_s:null_encode_y:null_cond:null_and:null_even:null_gr:null_p -> true:0:false:s:y:cons_cond:cons_and:cons_even:cons_gr:cons_p:null_encArg:null_encode_cond:null_encode_true:null_encode_and:null_encode_even:null_encode_gr:null_encode_0:null_encode_p:null_encode_false:null_encode_s:null_encode_y:null_cond:null_and:null_even:null_gr:null_p -> true:0:false:s:y:cons_cond:cons_and:cons_even:cons_gr:cons_p:null_encArg:null_encode_cond:null_encode_true:null_encode_and:null_encode_even:null_encode_gr:null_encode_0:null_encode_p:null_encode_false:null_encode_s:null_encode_y:null_cond:null_and:null_even:null_gr:null_p encode_even :: true:0:false:s:y:cons_cond:cons_and:cons_even:cons_gr:cons_p:null_encArg:null_encode_cond:null_encode_true:null_encode_and:null_encode_even:null_encode_gr:null_encode_0:null_encode_p:null_encode_false:null_encode_s:null_encode_y:null_cond:null_and:null_even:null_gr:null_p -> true:0:false:s:y:cons_cond:cons_and:cons_even:cons_gr:cons_p:null_encArg:null_encode_cond:null_encode_true:null_encode_and:null_encode_even:null_encode_gr:null_encode_0:null_encode_p:null_encode_false:null_encode_s:null_encode_y:null_cond:null_and:null_even:null_gr:null_p encode_gr :: true:0:false:s:y:cons_cond:cons_and:cons_even:cons_gr:cons_p:null_encArg:null_encode_cond:null_encode_true:null_encode_and:null_encode_even:null_encode_gr:null_encode_0:null_encode_p:null_encode_false:null_encode_s:null_encode_y:null_cond:null_and:null_even:null_gr:null_p -> true:0:false:s:y:cons_cond:cons_and:cons_even:cons_gr:cons_p:null_encArg:null_encode_cond:null_encode_true:null_encode_and:null_encode_even:null_encode_gr:null_encode_0:null_encode_p:null_encode_false:null_encode_s:null_encode_y:null_cond:null_and:null_even:null_gr:null_p -> true:0:false:s:y:cons_cond:cons_and:cons_even:cons_gr:cons_p:null_encArg:null_encode_cond:null_encode_true:null_encode_and:null_encode_even:null_encode_gr:null_encode_0:null_encode_p:null_encode_false:null_encode_s:null_encode_y:null_cond:null_and:null_even:null_gr:null_p encode_0 :: true:0:false:s:y:cons_cond:cons_and:cons_even:cons_gr:cons_p:null_encArg:null_encode_cond:null_encode_true:null_encode_and:null_encode_even:null_encode_gr:null_encode_0:null_encode_p:null_encode_false:null_encode_s:null_encode_y:null_cond:null_and:null_even:null_gr:null_p encode_p :: true:0:false:s:y:cons_cond:cons_and:cons_even:cons_gr:cons_p:null_encArg:null_encode_cond:null_encode_true:null_encode_and:null_encode_even:null_encode_gr:null_encode_0:null_encode_p:null_encode_false:null_encode_s:null_encode_y:null_cond:null_and:null_even:null_gr:null_p -> true:0:false:s:y:cons_cond:cons_and:cons_even:cons_gr:cons_p:null_encArg:null_encode_cond:null_encode_true:null_encode_and:null_encode_even:null_encode_gr:null_encode_0:null_encode_p:null_encode_false:null_encode_s:null_encode_y:null_cond:null_and:null_even:null_gr:null_p encode_false :: true:0:false:s:y:cons_cond:cons_and:cons_even:cons_gr:cons_p:null_encArg:null_encode_cond:null_encode_true:null_encode_and:null_encode_even:null_encode_gr:null_encode_0:null_encode_p:null_encode_false:null_encode_s:null_encode_y:null_cond:null_and:null_even:null_gr:null_p encode_s :: true:0:false:s:y:cons_cond:cons_and:cons_even:cons_gr:cons_p:null_encArg:null_encode_cond:null_encode_true:null_encode_and:null_encode_even:null_encode_gr:null_encode_0:null_encode_p:null_encode_false:null_encode_s:null_encode_y:null_cond:null_and:null_even:null_gr:null_p -> true:0:false:s:y:cons_cond:cons_and:cons_even:cons_gr:cons_p:null_encArg:null_encode_cond:null_encode_true:null_encode_and:null_encode_even:null_encode_gr:null_encode_0:null_encode_p:null_encode_false:null_encode_s:null_encode_y:null_cond:null_and:null_even:null_gr:null_p encode_y :: true:0:false:s:y:cons_cond:cons_and:cons_even:cons_gr:cons_p:null_encArg:null_encode_cond:null_encode_true:null_encode_and:null_encode_even:null_encode_gr:null_encode_0:null_encode_p:null_encode_false:null_encode_s:null_encode_y:null_cond:null_and:null_even:null_gr:null_p null_encArg :: true:0:false:s:y:cons_cond:cons_and:cons_even:cons_gr:cons_p:null_encArg:null_encode_cond:null_encode_true:null_encode_and:null_encode_even:null_encode_gr:null_encode_0:null_encode_p:null_encode_false:null_encode_s:null_encode_y:null_cond:null_and:null_even:null_gr:null_p null_encode_cond :: true:0:false:s:y:cons_cond:cons_and:cons_even:cons_gr:cons_p:null_encArg:null_encode_cond:null_encode_true:null_encode_and:null_encode_even:null_encode_gr:null_encode_0:null_encode_p:null_encode_false:null_encode_s:null_encode_y:null_cond:null_and:null_even:null_gr:null_p null_encode_true :: true:0:false:s:y:cons_cond:cons_and:cons_even:cons_gr:cons_p:null_encArg:null_encode_cond:null_encode_true:null_encode_and:null_encode_even:null_encode_gr:null_encode_0:null_encode_p:null_encode_false:null_encode_s:null_encode_y:null_cond:null_and:null_even:null_gr:null_p null_encode_and :: true:0:false:s:y:cons_cond:cons_and:cons_even:cons_gr:cons_p:null_encArg:null_encode_cond:null_encode_true:null_encode_and:null_encode_even:null_encode_gr:null_encode_0:null_encode_p:null_encode_false:null_encode_s:null_encode_y:null_cond:null_and:null_even:null_gr:null_p null_encode_even :: true:0:false:s:y:cons_cond:cons_and:cons_even:cons_gr:cons_p:null_encArg:null_encode_cond:null_encode_true:null_encode_and:null_encode_even:null_encode_gr:null_encode_0:null_encode_p:null_encode_false:null_encode_s:null_encode_y:null_cond:null_and:null_even:null_gr:null_p null_encode_gr :: true:0:false:s:y:cons_cond:cons_and:cons_even:cons_gr:cons_p:null_encArg:null_encode_cond:null_encode_true:null_encode_and:null_encode_even:null_encode_gr:null_encode_0:null_encode_p:null_encode_false:null_encode_s:null_encode_y:null_cond:null_and:null_even:null_gr:null_p null_encode_0 :: true:0:false:s:y:cons_cond:cons_and:cons_even:cons_gr:cons_p:null_encArg:null_encode_cond:null_encode_true:null_encode_and:null_encode_even:null_encode_gr:null_encode_0:null_encode_p:null_encode_false:null_encode_s:null_encode_y:null_cond:null_and:null_even:null_gr:null_p null_encode_p :: true:0:false:s:y:cons_cond:cons_and:cons_even:cons_gr:cons_p:null_encArg:null_encode_cond:null_encode_true:null_encode_and:null_encode_even:null_encode_gr:null_encode_0:null_encode_p:null_encode_false:null_encode_s:null_encode_y:null_cond:null_and:null_even:null_gr:null_p null_encode_false :: true:0:false:s:y:cons_cond:cons_and:cons_even:cons_gr:cons_p:null_encArg:null_encode_cond:null_encode_true:null_encode_and:null_encode_even:null_encode_gr:null_encode_0:null_encode_p:null_encode_false:null_encode_s:null_encode_y:null_cond:null_and:null_even:null_gr:null_p null_encode_s :: true:0:false:s:y:cons_cond:cons_and:cons_even:cons_gr:cons_p:null_encArg:null_encode_cond:null_encode_true:null_encode_and:null_encode_even:null_encode_gr:null_encode_0:null_encode_p:null_encode_false:null_encode_s:null_encode_y:null_cond:null_and:null_even:null_gr:null_p null_encode_y :: true:0:false:s:y:cons_cond:cons_and:cons_even:cons_gr:cons_p:null_encArg:null_encode_cond:null_encode_true:null_encode_and:null_encode_even:null_encode_gr:null_encode_0:null_encode_p:null_encode_false:null_encode_s:null_encode_y:null_cond:null_and:null_even:null_gr:null_p null_cond :: true:0:false:s:y:cons_cond:cons_and:cons_even:cons_gr:cons_p:null_encArg:null_encode_cond:null_encode_true:null_encode_and:null_encode_even:null_encode_gr:null_encode_0:null_encode_p:null_encode_false:null_encode_s:null_encode_y:null_cond:null_and:null_even:null_gr:null_p null_and :: true:0:false:s:y:cons_cond:cons_and:cons_even:cons_gr:cons_p:null_encArg:null_encode_cond:null_encode_true:null_encode_and:null_encode_even:null_encode_gr:null_encode_0:null_encode_p:null_encode_false:null_encode_s:null_encode_y:null_cond:null_and:null_even:null_gr:null_p null_even :: true:0:false:s:y:cons_cond:cons_and:cons_even:cons_gr:cons_p:null_encArg:null_encode_cond:null_encode_true:null_encode_and:null_encode_even:null_encode_gr:null_encode_0:null_encode_p:null_encode_false:null_encode_s:null_encode_y:null_cond:null_and:null_even:null_gr:null_p null_gr :: true:0:false:s:y:cons_cond:cons_and:cons_even:cons_gr:cons_p:null_encArg:null_encode_cond:null_encode_true:null_encode_and:null_encode_even:null_encode_gr:null_encode_0:null_encode_p:null_encode_false:null_encode_s:null_encode_y:null_cond:null_and:null_even:null_gr:null_p null_p :: true:0:false:s:y:cons_cond:cons_and:cons_even:cons_gr:cons_p:null_encArg:null_encode_cond:null_encode_true:null_encode_and:null_encode_even:null_encode_gr:null_encode_0:null_encode_p:null_encode_false:null_encode_s:null_encode_y:null_cond:null_and:null_even:null_gr:null_p 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 y => 3 null_encArg => 0 null_encode_cond => 0 null_encode_true => 0 null_encode_and => 0 null_encode_even => 0 null_encode_gr => 0 null_encode_0 => 0 null_encode_p => 0 null_encode_false => 0 null_encode_s => 0 null_encode_y => 0 null_cond => 0 null_and => 0 null_even => 0 null_gr => 0 null_p => 0 ---------------------------------------- (12) Obligation: Complexity RNTS consisting of the following rules: and(z, z') -{ 1 }-> 2 :|: z = 2, z' = 2 and(z, z') -{ 1 }-> 1 :|: x >= 0, z' = 1, z = x and(z, z') -{ 1 }-> 1 :|: z' = x, z = 1, x >= 0 and(z, z') -{ 0 }-> 0 :|: v0 >= 0, v1 >= 0, z = v0, z' = v1 cond(z, z') -{ 1 }-> cond(and(even(x), gr(x, 0)), p(x)) :|: z = 2, z' = x, x >= 0 cond(z, z') -{ 0 }-> 0 :|: v0 >= 0, v1 >= 0, z = v0, z' = v1 encArg(z) -{ 0 }-> p(encArg(x_1)) :|: z = 1 + x_1, x_1 >= 0 encArg(z) -{ 0 }-> gr(encArg(x_1), encArg(x_2)) :|: x_1 >= 0, z = 1 + x_1 + x_2, x_2 >= 0 encArg(z) -{ 0 }-> even(encArg(x_1)) :|: z = 1 + x_1, x_1 >= 0 encArg(z) -{ 0 }-> cond(encArg(x_1), encArg(x_2)) :|: x_1 >= 0, z = 1 + x_1 + x_2, x_2 >= 0 encArg(z) -{ 0 }-> and(encArg(x_1), encArg(x_2)) :|: x_1 >= 0, z = 1 + x_1 + x_2, x_2 >= 0 encArg(z) -{ 0 }-> 3 :|: z = 3 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_and(z, z') -{ 0 }-> and(encArg(x_1), encArg(x_2)) :|: x_1 >= 0, x_2 >= 0, z = x_1, z' = x_2 encode_and(z, z') -{ 0 }-> 0 :|: v0 >= 0, v1 >= 0, z = v0, z' = v1 encode_cond(z, z') -{ 0 }-> cond(encArg(x_1), encArg(x_2)) :|: x_1 >= 0, x_2 >= 0, z = x_1, z' = x_2 encode_cond(z, z') -{ 0 }-> 0 :|: v0 >= 0, v1 >= 0, z = v0, z' = v1 encode_even(z) -{ 0 }-> even(encArg(x_1)) :|: x_1 >= 0, z = x_1 encode_even(z) -{ 0 }-> 0 :|: v0 >= 0, z = v0 encode_false -{ 0 }-> 1 :|: encode_false -{ 0 }-> 0 :|: encode_gr(z, z') -{ 0 }-> gr(encArg(x_1), encArg(x_2)) :|: x_1 >= 0, x_2 >= 0, z = x_1, z' = x_2 encode_gr(z, z') -{ 0 }-> 0 :|: v0 >= 0, v1 >= 0, z = v0, z' = v1 encode_p(z) -{ 0 }-> p(encArg(x_1)) :|: x_1 >= 0, z = x_1 encode_p(z) -{ 0 }-> 0 :|: v0 >= 0, z = v0 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_y -{ 0 }-> 3 :|: encode_y -{ 0 }-> 0 :|: even(z) -{ 1 }-> even(x) :|: x >= 0, z = 1 + (1 + x) even(z) -{ 1 }-> 2 :|: z = 0 even(z) -{ 1 }-> 1 :|: z = 1 + 0 even(z) -{ 0 }-> 0 :|: v0 >= 0, z = v0 gr(z, z') -{ 1 }-> gr(x, 3) :|: z' = 1 + 3, x >= 0, z = 1 + x gr(z, z') -{ 1 }-> 2 :|: x >= 0, z = 1 + x, z' = 0 gr(z, z') -{ 1 }-> 1 :|: z' = x, x >= 0, z = 0 gr(z, z') -{ 0 }-> 0 :|: v0 >= 0, v1 >= 0, z = v0, z' = v1 p(z) -{ 1 }-> x :|: x >= 0, z = 1 + x p(z) -{ 1 }-> 0 :|: z = 0 p(z) -{ 0 }-> 0 :|: v0 >= 0, z = v0 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),0,[cond(V1, V, Out)],[V1 >= 0,V >= 0]). eq(start(V1, V),0,[and(V1, V, Out)],[V1 >= 0,V >= 0]). eq(start(V1, V),0,[even(V1, Out)],[V1 >= 0]). eq(start(V1, V),0,[gr(V1, V, Out)],[V1 >= 0,V >= 0]). eq(start(V1, V),0,[p(V1, Out)],[V1 >= 0]). eq(start(V1, V),0,[encArg(V1, Out)],[V1 >= 0]). eq(start(V1, V),0,[fun(V1, V, Out)],[V1 >= 0,V >= 0]). eq(start(V1, V),0,[fun1(Out)],[]). eq(start(V1, V),0,[fun2(V1, V, Out)],[V1 >= 0,V >= 0]). eq(start(V1, V),0,[fun3(V1, Out)],[V1 >= 0]). eq(start(V1, V),0,[fun4(V1, V, Out)],[V1 >= 0,V >= 0]). eq(start(V1, V),0,[fun5(Out)],[]). eq(start(V1, V),0,[fun6(V1, Out)],[V1 >= 0]). eq(start(V1, V),0,[fun7(Out)],[]). eq(start(V1, V),0,[fun8(V1, Out)],[V1 >= 0]). eq(start(V1, V),0,[fun9(Out)],[]). eq(cond(V1, V, Out),1,[even(V2, Ret00),gr(V2, 0, Ret01),and(Ret00, Ret01, Ret0),p(V2, Ret1),cond(Ret0, Ret1, Ret)],[Out = Ret,V1 = 2,V = V2,V2 >= 0]). eq(and(V1, V, Out),1,[],[Out = 1,V3 >= 0,V = 1,V1 = V3]). eq(and(V1, V, Out),1,[],[Out = 1,V = V4,V1 = 1,V4 >= 0]). eq(and(V1, V, Out),1,[],[Out = 2,V1 = 2,V = 2]). eq(even(V1, Out),1,[],[Out = 2,V1 = 0]). eq(even(V1, Out),1,[],[Out = 1,V1 = 1]). eq(even(V1, Out),1,[even(V5, Ret2)],[Out = Ret2,V5 >= 0,V1 = 2 + V5]). eq(gr(V1, V, Out),1,[],[Out = 1,V = V6,V6 >= 0,V1 = 0]). eq(gr(V1, V, Out),1,[],[Out = 2,V7 >= 0,V1 = 1 + V7,V = 0]). eq(gr(V1, V, Out),1,[gr(V8, 3, Ret3)],[Out = Ret3,V = 4,V8 >= 0,V1 = 1 + V8]). eq(p(V1, Out),1,[],[Out = 0,V1 = 0]). eq(p(V1, Out),1,[],[Out = V9,V9 >= 0,V1 = 1 + V9]). eq(encArg(V1, Out),0,[],[Out = 2,V1 = 2]). eq(encArg(V1, Out),0,[],[Out = 0,V1 = 0]). eq(encArg(V1, Out),0,[],[Out = 1,V1 = 1]). eq(encArg(V1, Out),0,[encArg(V10, Ret11)],[Out = 1 + Ret11,V1 = 1 + V10,V10 >= 0]). eq(encArg(V1, Out),0,[],[Out = 3,V1 = 3]). eq(encArg(V1, Out),0,[encArg(V11, Ret02),encArg(V12, Ret12),cond(Ret02, Ret12, Ret4)],[Out = Ret4,V11 >= 0,V1 = 1 + V11 + V12,V12 >= 0]). eq(encArg(V1, Out),0,[encArg(V13, Ret03),encArg(V14, Ret13),and(Ret03, Ret13, Ret5)],[Out = Ret5,V13 >= 0,V1 = 1 + V13 + V14,V14 >= 0]). eq(encArg(V1, Out),0,[encArg(V15, Ret04),even(Ret04, Ret6)],[Out = Ret6,V1 = 1 + V15,V15 >= 0]). eq(encArg(V1, Out),0,[encArg(V17, Ret05),encArg(V16, Ret14),gr(Ret05, Ret14, Ret7)],[Out = Ret7,V17 >= 0,V1 = 1 + V16 + V17,V16 >= 0]). eq(encArg(V1, Out),0,[encArg(V18, Ret06),p(Ret06, Ret8)],[Out = Ret8,V1 = 1 + V18,V18 >= 0]). eq(fun(V1, V, Out),0,[encArg(V20, Ret07),encArg(V19, Ret15),cond(Ret07, Ret15, Ret9)],[Out = Ret9,V20 >= 0,V19 >= 0,V1 = V20,V = V19]). eq(fun1(Out),0,[],[Out = 2]). eq(fun2(V1, V, Out),0,[encArg(V22, Ret08),encArg(V21, Ret16),and(Ret08, Ret16, Ret10)],[Out = Ret10,V22 >= 0,V21 >= 0,V1 = V22,V = V21]). eq(fun3(V1, Out),0,[encArg(V23, Ret09),even(Ret09, Ret17)],[Out = Ret17,V23 >= 0,V1 = V23]). eq(fun4(V1, V, Out),0,[encArg(V24, Ret010),encArg(V25, Ret18),gr(Ret010, Ret18, Ret19)],[Out = Ret19,V24 >= 0,V25 >= 0,V1 = V24,V = V25]). eq(fun5(Out),0,[],[Out = 0]). eq(fun6(V1, Out),0,[encArg(V26, Ret011),p(Ret011, Ret20)],[Out = Ret20,V26 >= 0,V1 = V26]). eq(fun7(Out),0,[],[Out = 1]). eq(fun8(V1, Out),0,[encArg(V27, Ret110)],[Out = 1 + Ret110,V27 >= 0,V1 = V27]). eq(fun9(Out),0,[],[Out = 3]). eq(encArg(V1, Out),0,[],[Out = 0,V28 >= 0,V1 = V28]). eq(fun(V1, V, Out),0,[],[Out = 0,V30 >= 0,V29 >= 0,V1 = V30,V = V29]). eq(fun1(Out),0,[],[Out = 0]). eq(fun2(V1, V, Out),0,[],[Out = 0,V32 >= 0,V31 >= 0,V1 = V32,V = V31]). eq(fun3(V1, Out),0,[],[Out = 0,V33 >= 0,V1 = V33]). eq(fun4(V1, V, Out),0,[],[Out = 0,V34 >= 0,V35 >= 0,V1 = V34,V = V35]). eq(fun6(V1, Out),0,[],[Out = 0,V36 >= 0,V1 = V36]). eq(fun7(Out),0,[],[Out = 0]). eq(fun8(V1, Out),0,[],[Out = 0,V37 >= 0,V1 = V37]). eq(fun9(Out),0,[],[Out = 0]). eq(cond(V1, V, Out),0,[],[Out = 0,V38 >= 0,V39 >= 0,V1 = V38,V = V39]). eq(and(V1, V, Out),0,[],[Out = 0,V40 >= 0,V41 >= 0,V1 = V40,V = V41]). eq(even(V1, Out),0,[],[Out = 0,V42 >= 0,V1 = V42]). eq(gr(V1, V, Out),0,[],[Out = 0,V44 >= 0,V43 >= 0,V1 = V44,V = V43]). eq(p(V1, Out),0,[],[Out = 0,V45 >= 0,V1 = V45]). input_output_vars(cond(V1,V,Out),[V1,V],[Out]). input_output_vars(and(V1,V,Out),[V1,V],[Out]). input_output_vars(even(V1,Out),[V1],[Out]). input_output_vars(gr(V1,V,Out),[V1,V],[Out]). input_output_vars(p(V1,Out),[V1],[Out]). input_output_vars(encArg(V1,Out),[V1],[Out]). input_output_vars(fun(V1,V,Out),[V1,V],[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,V,Out),[V1,V],[Out]). input_output_vars(fun5(Out),[],[Out]). input_output_vars(fun6(V1,Out),[V1],[Out]). input_output_vars(fun7(Out),[],[Out]). input_output_vars(fun8(V1,Out),[V1],[Out]). input_output_vars(fun9(Out),[],[Out]). CoFloCo proof output: Preprocessing Cost Relations ===================================== #### Computed strongly connected components 0. non_recursive : [and/3] 1. recursive : [even/2] 2. recursive : [gr/3] 3. non_recursive : [p/2] 4. recursive : [cond/3] 5. recursive [non_tail,multiple] : [encArg/2] 6. non_recursive : [fun/3] 7. non_recursive : [fun1/1] 8. non_recursive : [fun2/3] 9. non_recursive : [fun3/2] 10. non_recursive : [fun4/3] 11. non_recursive : [fun5/1] 12. non_recursive : [fun6/2] 13. non_recursive : [fun7/1] 14. non_recursive : [fun8/2] 15. non_recursive : [fun9/1] 16. non_recursive : [start/2] #### Obtained direct recursion through partial evaluation 0. SCC is partially evaluated into and/3 1. SCC is partially evaluated into even/2 2. SCC is partially evaluated into gr/3 3. SCC is partially evaluated into p/2 4. SCC is partially evaluated into cond/3 5. SCC is partially evaluated into encArg/2 6. SCC is partially evaluated into fun/3 7. SCC is partially evaluated into fun1/1 8. SCC is partially evaluated into fun2/3 9. SCC is partially evaluated into fun3/2 10. SCC is partially evaluated into fun4/3 11. SCC is completely evaluated into other SCCs 12. SCC is partially evaluated into fun6/2 13. SCC is partially evaluated into fun7/1 14. SCC is partially evaluated into fun8/2 15. SCC is partially evaluated into fun9/1 16. SCC is partially evaluated into start/2 Control-Flow Refinement of Cost Relations ===================================== ### Specialization of cost equations and/3 * CE 22 is refined into CE [62] * CE 19 is refined into CE [63] * CE 21 is refined into CE [64] * CE 20 is refined into CE [65] ### Cost equations --> "Loop" of and/3 * CEs [62] --> Loop 36 * CEs [63] --> Loop 37 * CEs [64] --> Loop 38 * CEs [65] --> Loop 39 ### Ranking functions of CR and(V1,V,Out) #### Partial ranking functions of CR and(V1,V,Out) ### Specialization of cost equations even/2 * CE 26 is refined into CE [66] * CE 24 is refined into CE [67] * CE 23 is refined into CE [68] * CE 25 is refined into CE [69] ### Cost equations --> "Loop" of even/2 * CEs [69] --> Loop 40 * CEs [66] --> Loop 41 * CEs [67] --> Loop 42 * CEs [68] --> Loop 43 ### Ranking functions of CR even(V1,Out) * RF of phase [40]: [V1-1] #### Partial ranking functions of CR even(V1,Out) * Partial RF of phase [40]: - RF of loop [40:1]: V1-1 ### Specialization of cost equations gr/3 * CE 30 is refined into CE [70] * CE 28 is refined into CE [71] * CE 27 is refined into CE [72] * CE 29 is refined into CE [73] ### Cost equations --> "Loop" of gr/3 * CEs [73] --> Loop 44 * CEs [70] --> Loop 45 * CEs [71] --> Loop 46 * CEs [72] --> Loop 47 ### Ranking functions of CR gr(V1,V,Out) #### Partial ranking functions of CR gr(V1,V,Out) ### Specialization of cost equations p/2 * CE 32 is refined into CE [74] * CE 31 is refined into CE [75] * CE 33 is refined into CE [76] ### Cost equations --> "Loop" of p/2 * CEs [74] --> Loop 48 * CEs [75,76] --> Loop 49 ### Ranking functions of CR p(V1,Out) #### Partial ranking functions of CR p(V1,Out) ### Specialization of cost equations cond/3 * CE 18 is refined into CE [77] * CE 17 is refined into CE [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,107,108] ### Cost equations --> "Loop" of cond/3 * CEs [104] --> Loop 50 * CEs [103] --> Loop 51 * CEs [96,100] --> Loop 52 * CEs [95,99] --> Loop 53 * CEs [81,82,85,86] --> Loop 54 * CEs [83,84,87,88,92,94,98,102,106,108] --> Loop 55 * CEs [78,89] --> Loop 56 * CEs [79,80,90,91,93,97,101,105,107] --> Loop 57 * CEs [77] --> Loop 58 ### Ranking functions of CR cond(V1,V,Out) * RF of phase [50]: [V-1] #### Partial ranking functions of CR cond(V1,V,Out) * Partial RF of phase [50]: - RF of loop [50:1]: V-1 ### Specialization of cost equations encArg/2 * CE 35 is refined into CE [109] * CE 38 is refined into CE [110] * CE 34 is refined into CE [111] * CE 36 is refined into CE [112] * CE 37 is refined into CE [113] * CE 41 is refined into CE [114,115,116,117,118] * CE 43 is refined into CE [119,120] * CE 39 is refined into CE [121,122] * CE 40 is refined into CE [123,124,125,126] * CE 42 is refined into CE [127,128,129,130] ### Cost equations --> "Loop" of encArg/2 * CEs [129] --> Loop 59 * CEs [124] --> Loop 60 * CEs [125] --> Loop 61 * CEs [123,128] --> Loop 62 * CEs [127] --> Loop 63 * CEs [121,122,126,130] --> Loop 64 * CEs [113] --> Loop 65 * CEs [120] --> Loop 66 * CEs [118] --> Loop 67 * CEs [114] --> Loop 68 * CEs [117] --> Loop 69 * CEs [115] --> Loop 70 * CEs [116,119] --> Loop 71 * CEs [109] --> Loop 72 * CEs [110] --> Loop 73 * CEs [111] --> Loop 74 * CEs [112] --> Loop 75 ### Ranking functions of CR encArg(V1,Out) * RF of phase [59,60,61,62,63,64,65,66,67,68,69,70,71]: [V1] #### Partial ranking functions of CR encArg(V1,Out) * Partial RF of phase [59,60,61,62,63,64,65,66,67,68,69,70,71]: - RF of loop [59:1,59:2,60:1,60:2,61:1,61:2,62:1,62:2,63:1,63:2,64:1,64:2,65:1,66:1,67:1,68:1,69:1,70:1,71:1]: V1 ### Specialization of cost equations fun/3 * CE 44 is refined into CE [131,132,133,134,135,136,137,138,139,140,141,142,143,144,145,146,147,148] * CE 45 is refined into CE [149] ### Cost equations --> "Loop" of fun/3 * CEs [133,146] --> Loop 76 * CEs [143] --> Loop 77 * CEs [141,142,144] --> Loop 78 * CEs [134,139,147] --> Loop 79 * CEs [131,132,135,136,137,138,140,145,148,149] --> Loop 80 ### Ranking functions of CR fun(V1,V,Out) #### Partial ranking functions of CR fun(V1,V,Out) ### Specialization of cost equations fun1/1 * CE 46 is refined into CE [150] * CE 47 is refined into CE [151] ### Cost equations --> "Loop" of fun1/1 * CEs [150] --> Loop 81 * CEs [151] --> Loop 82 ### Ranking functions of CR fun1(Out) #### Partial ranking functions of CR fun1(Out) ### Specialization of cost equations fun2/3 * CE 48 is refined into CE [152,153,154,155,156,157,158,159,160,161,162,163,164,165,166,167,168,169,170,171,172,173,174,175,176,177,178,179] * CE 49 is refined into CE [180] ### Cost equations --> "Loop" of fun2/3 * CEs [159] --> Loop 83 * CEs [157] --> Loop 84 * CEs [156] --> Loop 85 * CEs [158,177] --> Loop 86 * CEs [161,170] --> Loop 87 * CEs [173] --> Loop 88 * CEs [171,172,174] --> Loop 89 * CEs [152,154,164,175] --> Loop 90 * CEs [160,168,178] --> Loop 91 * CEs [153,163,166] --> Loop 92 * CEs [155,162,165,167,169,176,179,180] --> Loop 93 ### Ranking functions of CR fun2(V1,V,Out) #### Partial ranking functions of CR fun2(V1,V,Out) ### Specialization of cost equations fun3/2 * CE 50 is refined into CE [181,182,183,184,185,186,187,188,189,190,191,192] * CE 51 is refined into CE [193] ### Cost equations --> "Loop" of fun3/2 * CEs [190] --> Loop 94 * CEs [182,184,189] --> Loop 95 * CEs [188] --> Loop 96 * CEs [181,185,187,191] --> Loop 97 * CEs [183,186,192,193] --> Loop 98 ### Ranking functions of CR fun3(V1,Out) #### Partial ranking functions of CR fun3(V1,Out) ### Specialization of cost equations fun4/3 * CE 52 is refined into CE [194,195,196,197,198,199,200,201,202,203,204,205,206,207,208,209,210,211,212,213,214,215,216,217,218,219,220,221,222,223,224] * CE 53 is refined into CE [225] ### Cost equations --> "Loop" of fun4/3 * CEs [200,221] --> Loop 99 * CEs [194,195,198,202,217,219,223] --> Loop 100 * CEs [199,220] --> Loop 101 * CEs [211,215] --> Loop 102 * CEs [214] --> Loop 103 * CEs [212,213,216] --> Loop 104 * CEs [196,203,205,209] --> Loop 105 * CEs [201,208,222] --> Loop 106 * CEs [197,204,206,207,210,218,224,225] --> Loop 107 ### Ranking functions of CR fun4(V1,V,Out) #### Partial ranking functions of CR fun4(V1,V,Out) ### Specialization of cost equations fun6/2 * CE 54 is refined into CE [226,227,228,229,230,231,232] * CE 55 is refined into CE [233] ### Cost equations --> "Loop" of fun6/2 * CEs [231] --> Loop 108 * CEs [230] --> Loop 109 * CEs [227,229] --> Loop 110 * CEs [226,228,232,233] --> Loop 111 ### Ranking functions of CR fun6(V1,Out) #### Partial ranking functions of CR fun6(V1,Out) ### Specialization of cost equations fun7/1 * CE 56 is refined into CE [234] * CE 57 is refined into CE [235] ### Cost equations --> "Loop" of fun7/1 * CEs [234] --> Loop 112 * CEs [235] --> Loop 113 ### Ranking functions of CR fun7(Out) #### Partial ranking functions of CR fun7(Out) ### Specialization of cost equations fun8/2 * CE 58 is refined into CE [236,237,238,239] * CE 59 is refined into CE [240] ### Cost equations --> "Loop" of fun8/2 * CEs [239] --> Loop 114 * CEs [240] --> Loop 115 * CEs [238] --> Loop 116 * CEs [236,237] --> Loop 117 ### Ranking functions of CR fun8(V1,Out) #### Partial ranking functions of CR fun8(V1,Out) ### Specialization of cost equations fun9/1 * CE 60 is refined into CE [241] * CE 61 is refined into CE [242] ### Cost equations --> "Loop" of fun9/1 * CEs [241] --> Loop 118 * CEs [242] --> Loop 119 ### Ranking functions of CR fun9(Out) #### Partial ranking functions of CR fun9(Out) ### Specialization of cost equations start/2 * CE 1 is refined into CE [243,244] * CE 2 is refined into CE [245,246,247,248] * CE 3 is refined into CE [249,250,251,252,253] * CE 4 is refined into CE [254,255,256,257] * CE 5 is refined into CE [258,259] * CE 6 is refined into CE [260,261,262,263] * CE 7 is refined into CE [264,265,266] * CE 8 is refined into CE [267,268] * CE 9 is refined into CE [269,270,271,272,273,274] * CE 10 is refined into CE [275,276,277] * CE 11 is refined into CE [278,279,280,281,282] * CE 12 is refined into CE [283] * CE 13 is refined into CE [284,285] * CE 14 is refined into CE [286,287] * CE 15 is refined into CE [288,289,290] * CE 16 is refined into CE [291,292] ### Cost equations --> "Loop" of start/2 * CEs [243,244,245,246,247,248,249,250,251,252,253,254,255,256,257,258,259,260,261,262,263,264,265,266,267,268,269,270,271,272,273,274,275,276,277,278,279,280,281,282,283,284,285,286,287,288,289,290,291,292] --> Loop 120 ### Ranking functions of CR start(V1,V) #### Partial ranking functions of CR start(V1,V) Computing Bounds ===================================== #### Cost of chains of and(V1,V,Out): * Chain [39]: 1 with precondition: [V1=1,Out=1,V>=0] * Chain [38]: 1 with precondition: [V1=2,V=2,Out=2] * Chain [37]: 1 with precondition: [V=1,Out=1,V1>=0] * Chain [36]: 0 with precondition: [Out=0,V1>=0,V>=0] #### Cost of chains of even(V1,Out): * Chain [[40],43]: 1*it(40)+1 Such that:it(40) =< V1 with precondition: [Out=2,V1>=2] * Chain [[40],42]: 1*it(40)+1 Such that:it(40) =< V1 with precondition: [Out=1,V1>=3] * Chain [[40],41]: 1*it(40)+0 Such that:it(40) =< V1 with precondition: [Out=0,V1>=2] * Chain [43]: 1 with precondition: [V1=0,Out=2] * Chain [42]: 1 with precondition: [V1=1,Out=1] * Chain [41]: 0 with precondition: [Out=0,V1>=0] #### Cost of chains of gr(V1,V,Out): * Chain [47]: 1 with precondition: [V1=0,Out=1,V>=0] * Chain [46]: 1 with precondition: [V=0,Out=2,V1>=1] * Chain [45]: 0 with precondition: [Out=0,V1>=0,V>=0] * Chain [44,47]: 2 with precondition: [V1=1,V=4,Out=1] * Chain [44,45]: 1 with precondition: [V=4,Out=0,V1>=1] #### Cost of chains of p(V1,Out): * Chain [49]: 1 with precondition: [Out=0,V1>=0] * Chain [48]: 1 with precondition: [V1=Out+1,V1>=1] #### Cost of chains of cond(V1,V,Out): * Chain [[50],58]: 5*it(50)+1*s(4)+0 Such that:aux(3) =< V it(50) =< aux(3) s(4) =< it(50)*aux(3) with precondition: [V1=2,Out=0,V>=2] * Chain [[50],57,58]: 11*it(50)+1*s(4)+4 Such that:aux(5) =< V it(50) =< aux(5) s(4) =< it(50)*aux(5) with precondition: [V1=2,Out=0,V>=2] * Chain [[50],55,58]: 11*it(50)+1*s(4)+4 Such that:aux(7) =< V it(50) =< aux(7) s(4) =< it(50)*aux(7) with precondition: [V1=2,Out=0,V>=2] * Chain [[50],54,58]: 5*it(50)+1*s(4)+5 Such that:aux(8) =< V it(50) =< aux(8) s(4) =< it(50)*aux(8) with precondition: [V1=2,Out=0,V>=2] * Chain [[50],53,58]: 7*it(50)+1*s(4)+5 Such that:aux(10) =< V it(50) =< aux(10) s(4) =< it(50)*aux(10) with precondition: [V1=2,Out=0,V>=4] * Chain [[50],52,58]: 7*it(50)+1*s(4)+5 Such that:aux(12) =< V it(50) =< aux(12) s(4) =< it(50)*aux(12) with precondition: [V1=2,Out=0,V>=4] * Chain [[50],51,58]: 6*it(50)+1*s(4)+5 Such that:aux(13) =< V it(50) =< aux(13) s(4) =< it(50)*aux(13) with precondition: [V1=2,Out=0,V>=3] * Chain [[50],51,57,58]: 6*it(50)+1*s(4)+9 Such that:aux(14) =< V it(50) =< aux(14) s(4) =< it(50)*aux(14) with precondition: [V1=2,Out=0,V>=3] * Chain [[50],51,56,58]: 6*it(50)+1*s(4)+10 Such that:aux(15) =< V it(50) =< aux(15) s(4) =< it(50)*aux(15) with precondition: [V1=2,Out=0,V>=3] * Chain [58]: 0 with precondition: [Out=0,V1>=0,V>=0] * Chain [57,58]: 6*s(6)+4 Such that:aux(4) =< V s(6) =< aux(4) with precondition: [V1=2,Out=0,V>=0] * Chain [56,58]: 5 with precondition: [V1=2,V=0,Out=0] * Chain [55,58]: 6*s(12)+4 Such that:aux(6) =< V s(12) =< aux(6) with precondition: [V1=2,Out=0,V>=1] * Chain [54,58]: 5 with precondition: [V1=2,V=1,Out=0] * Chain [53,58]: 2*s(18)+5 Such that:aux(9) =< V s(18) =< aux(9) with precondition: [V1=2,Out=0,V>=3] * Chain [52,58]: 2*s(20)+5 Such that:aux(11) =< V s(20) =< aux(11) with precondition: [V1=2,Out=0,V>=3] * Chain [51,58]: 1*s(22)+5 Such that:s(22) =< V with precondition: [V1=2,Out=0,V>=2] * Chain [51,57,58]: 1*s(22)+9 Such that:s(22) =< V with precondition: [V1=2,Out=0,V>=2] * Chain [51,56,58]: 1*s(22)+10 Such that:s(22) =< V with precondition: [V1=2,Out=0,V>=2] #### Cost of chains of encArg(V1,Out): * Chain [75]: 0 with precondition: [V1=1,Out=1] * Chain [74]: 0 with precondition: [V1=2,Out=2] * Chain [73]: 0 with precondition: [V1=3,Out=3] * Chain [72]: 0 with precondition: [Out=0,V1>=0] * Chain [multiple([59,60,61,62,63,64,65,66,67,68,69,70,71],[[75],[74],[73],[72]])]: 1*it(59)+1*it(60)+3*it(61)+11*it(63)+6*it(66)+83*s(74)+9*s(75)+2*s(77)+1*s(79)+0 Such that:s(65) =< 2*V1 aux(25) =< V1 aux(26) =< V1+1 aux(27) =< V1/2 aux(28) =< 4/5*V1 it(63) =< aux(25) it(66) =< aux(25) it([72]) =< aux(26) it(60) =< aux(27) it(59) =< aux(28) it(60) =< aux(28) it(61) =< aux(28) aux(24) =< s(65)+2 aux(21) =< s(65) it(59) =< it([72])*(1/5)+aux(28) it(60) =< it([72])*(1/5)+aux(28) it(61) =< it([72])*(1/5)+aux(28) it(63) =< it([72])*(1/5)+aux(28) it(60) =< it([72])*(1/2)+aux(27) it(61) =< it([72])*(1/2)+aux(27) it(63) =< it([72])*(1/2)+aux(27) s(79) =< it(66)*aux(24) s(77) =< it(66)*aux(21) s(76) =< it(63)*aux(21) s(74) =< s(76) s(75) =< s(74)*s(65) with precondition: [V1>=1,Out>=0,2*V1>=Out] #### Cost of chains of fun(V1,V,Out): * Chain [80]: 33*s(103)+18*s(104)+3*s(105)+3*s(106)+9*s(107)+3*s(110)+6*s(111)+249*s(113)+27*s(114)+55*s(120)+30*s(121)+5*s(122)+5*s(123)+15*s(124)+5*s(127)+10*s(128)+415*s(130)+45*s(131)+249*s(133)+27*s(134)+83*s(227)+9*s(228)+10 Such that:s(226) =< 2 aux(32) =< V1 aux(33) =< V1+1 aux(34) =< 2*V1 aux(35) =< V1/2 aux(36) =< 4/5*V1 aux(37) =< V aux(38) =< V+1 aux(39) =< 2*V aux(40) =< V/2 aux(41) =< 4/5*V s(227) =< s(226) s(228) =< s(227)*s(226) s(133) =< aux(39) s(134) =< s(133)*aux(39) s(120) =< aux(37) s(121) =< aux(37) s(122) =< aux(40) s(123) =< aux(41) s(122) =< aux(41) s(124) =< aux(41) s(125) =< aux(39)+2 s(126) =< aux(39) s(123) =< aux(38)*(1/5)+aux(41) s(122) =< aux(38)*(1/5)+aux(41) s(124) =< aux(38)*(1/5)+aux(41) s(120) =< aux(38)*(1/5)+aux(41) s(122) =< aux(38)*(1/2)+aux(40) s(124) =< aux(38)*(1/2)+aux(40) s(120) =< aux(38)*(1/2)+aux(40) s(127) =< s(121)*s(125) s(128) =< s(121)*s(126) s(129) =< s(120)*s(126) s(130) =< s(129) s(131) =< s(130)*aux(39) s(103) =< aux(32) s(104) =< aux(32) s(105) =< aux(35) s(106) =< aux(36) s(105) =< aux(36) s(107) =< aux(36) s(108) =< aux(34)+2 s(109) =< aux(34) s(106) =< aux(33)*(1/5)+aux(36) s(105) =< aux(33)*(1/5)+aux(36) s(107) =< aux(33)*(1/5)+aux(36) s(103) =< aux(33)*(1/5)+aux(36) s(105) =< aux(33)*(1/2)+aux(35) s(107) =< aux(33)*(1/2)+aux(35) s(103) =< aux(33)*(1/2)+aux(35) s(110) =< s(104)*s(108) s(111) =< s(104)*s(109) s(112) =< s(103)*s(109) s(113) =< s(112) s(114) =< s(113)*aux(34) with precondition: [Out=0,V1>=0,V>=0] * Chain [79]: 11*s(260)+6*s(261)+1*s(262)+1*s(263)+3*s(264)+1*s(267)+2*s(268)+83*s(270)+9*s(271)+249*s(273)+27*s(274)+10 Such that:s(255) =< V1 s(256) =< V1+1 s(257) =< 2*V1 s(258) =< V1/2 s(259) =< 4/5*V1 aux(42) =< 3 s(273) =< aux(42) s(274) =< s(273)*aux(42) s(260) =< s(255) s(261) =< s(255) s(262) =< s(258) s(263) =< s(259) s(262) =< s(259) s(264) =< s(259) s(265) =< s(257)+2 s(266) =< s(257) s(263) =< s(256)*(1/5)+s(259) s(262) =< s(256)*(1/5)+s(259) s(264) =< s(256)*(1/5)+s(259) s(260) =< s(256)*(1/5)+s(259) s(262) =< s(256)*(1/2)+s(258) s(264) =< s(256)*(1/2)+s(258) s(260) =< s(256)*(1/2)+s(258) s(267) =< s(261)*s(265) s(268) =< s(261)*s(266) s(269) =< s(260)*s(266) s(270) =< s(269) s(271) =< s(270)*s(257) with precondition: [V=3,Out=0,V1>=0] * Chain [78]: 11*s(286)+6*s(287)+1*s(288)+1*s(289)+3*s(290)+1*s(293)+2*s(294)+83*s(296)+9*s(297)+83*s(299)+9*s(300)+83*s(302)+9*s(303)+10 Such that:s(301) =< 2 s(281) =< V s(282) =< V+1 aux(43) =< 2*V s(284) =< V/2 s(285) =< 4/5*V s(302) =< s(301) s(303) =< s(302)*s(301) s(299) =< aux(43) s(300) =< s(299)*aux(43) s(286) =< s(281) s(287) =< s(281) s(288) =< s(284) s(289) =< s(285) s(288) =< s(285) s(290) =< s(285) s(291) =< aux(43)+2 s(292) =< aux(43) s(289) =< s(282)*(1/5)+s(285) s(288) =< s(282)*(1/5)+s(285) s(290) =< s(282)*(1/5)+s(285) s(286) =< s(282)*(1/5)+s(285) s(288) =< s(282)*(1/2)+s(284) s(290) =< s(282)*(1/2)+s(284) s(286) =< s(282)*(1/2)+s(284) s(293) =< s(287)*s(291) s(294) =< s(287)*s(292) s(295) =< s(286)*s(292) s(296) =< s(295) s(297) =< s(296)*aux(43) with precondition: [V1=3,Out=0,V>=0] * Chain [77]: 83*s(308)+9*s(309)+10 Such that:s(307) =< 3 s(308) =< s(307) s(309) =< s(308)*s(307) with precondition: [V1=3,V=3,Out=0] * Chain [76]: 11*s(315)+6*s(316)+1*s(317)+1*s(318)+3*s(319)+1*s(322)+2*s(323)+83*s(325)+9*s(326)+166*s(328)+18*s(329)+10 Such that:s(310) =< V1 s(311) =< V1+1 s(312) =< 2*V1 s(313) =< V1/2 s(314) =< 4/5*V1 aux(44) =< 2 s(328) =< aux(44) s(329) =< s(328)*aux(44) s(315) =< s(310) s(316) =< s(310) s(317) =< s(313) s(318) =< s(314) s(317) =< s(314) s(319) =< s(314) s(320) =< s(312)+2 s(321) =< s(312) s(318) =< s(311)*(1/5)+s(314) s(317) =< s(311)*(1/5)+s(314) s(319) =< s(311)*(1/5)+s(314) s(315) =< s(311)*(1/5)+s(314) s(317) =< s(311)*(1/2)+s(313) s(319) =< s(311)*(1/2)+s(313) s(315) =< s(311)*(1/2)+s(313) s(322) =< s(316)*s(320) s(323) =< s(316)*s(321) s(324) =< s(315)*s(321) s(325) =< s(324) s(326) =< s(325)*s(312) with precondition: [V=2,Out=0,V1>=0] #### Cost of chains of fun1(Out): * Chain [82]: 0 with precondition: [Out=0] * Chain [81]: 0 with precondition: [Out=2] #### Cost of chains of fun2(V1,V,Out): * Chain [93]: 22*s(402)+12*s(403)+2*s(404)+2*s(405)+6*s(406)+2*s(409)+4*s(410)+166*s(412)+18*s(413)+33*s(419)+18*s(420)+3*s(421)+3*s(422)+9*s(423)+3*s(426)+6*s(427)+249*s(429)+27*s(430)+0 Such that:aux(51) =< V1 aux(52) =< V1+1 aux(53) =< 2*V1 aux(54) =< V1/2 aux(55) =< 4/5*V1 aux(56) =< V aux(57) =< V+1 aux(58) =< 2*V aux(59) =< V/2 aux(60) =< 4/5*V s(419) =< aux(56) s(420) =< aux(56) s(421) =< aux(59) s(422) =< aux(60) s(421) =< aux(60) s(423) =< aux(60) s(424) =< aux(58)+2 s(425) =< aux(58) s(422) =< aux(57)*(1/5)+aux(60) s(421) =< aux(57)*(1/5)+aux(60) s(423) =< aux(57)*(1/5)+aux(60) s(419) =< aux(57)*(1/5)+aux(60) s(421) =< aux(57)*(1/2)+aux(59) s(423) =< aux(57)*(1/2)+aux(59) s(419) =< aux(57)*(1/2)+aux(59) s(426) =< s(420)*s(424) s(427) =< s(420)*s(425) s(428) =< s(419)*s(425) s(429) =< s(428) s(430) =< s(429)*aux(58) s(402) =< aux(51) s(403) =< aux(51) s(404) =< aux(54) s(405) =< aux(55) s(404) =< aux(55) s(406) =< aux(55) s(407) =< aux(53)+2 s(408) =< aux(53) s(405) =< aux(52)*(1/5)+aux(55) s(404) =< aux(52)*(1/5)+aux(55) s(406) =< aux(52)*(1/5)+aux(55) s(402) =< aux(52)*(1/5)+aux(55) s(404) =< aux(52)*(1/2)+aux(54) s(406) =< aux(52)*(1/2)+aux(54) s(402) =< aux(52)*(1/2)+aux(54) s(409) =< s(403)*s(407) s(410) =< s(403)*s(408) s(411) =< s(402)*s(408) s(412) =< s(411) s(413) =< s(412)*aux(53) with precondition: [Out=0,V1>=0,V>=0] * Chain [92]: 11*s(487)+6*s(488)+1*s(489)+1*s(490)+3*s(491)+1*s(494)+2*s(495)+83*s(497)+9*s(498)+22*s(504)+12*s(505)+2*s(506)+2*s(507)+6*s(508)+2*s(511)+4*s(512)+166*s(514)+18*s(515)+1 Such that:s(482) =< V1 s(483) =< V1+1 s(484) =< 2*V1 s(485) =< V1/2 s(486) =< 4/5*V1 aux(61) =< V aux(62) =< V+1 aux(63) =< 2*V aux(64) =< V/2 aux(65) =< 4/5*V s(504) =< aux(61) s(505) =< aux(61) s(506) =< aux(64) s(507) =< aux(65) s(506) =< aux(65) s(508) =< aux(65) s(509) =< aux(63)+2 s(510) =< aux(63) s(507) =< aux(62)*(1/5)+aux(65) s(506) =< aux(62)*(1/5)+aux(65) s(508) =< aux(62)*(1/5)+aux(65) s(504) =< aux(62)*(1/5)+aux(65) s(506) =< aux(62)*(1/2)+aux(64) s(508) =< aux(62)*(1/2)+aux(64) s(504) =< aux(62)*(1/2)+aux(64) s(511) =< s(505)*s(509) s(512) =< s(505)*s(510) s(513) =< s(504)*s(510) s(514) =< s(513) s(515) =< s(514)*aux(63) s(487) =< s(482) s(488) =< s(482) s(489) =< s(485) s(490) =< s(486) s(489) =< s(486) s(491) =< s(486) s(492) =< s(484)+2 s(493) =< s(484) s(490) =< s(483)*(1/5)+s(486) s(489) =< s(483)*(1/5)+s(486) s(491) =< s(483)*(1/5)+s(486) s(487) =< s(483)*(1/5)+s(486) s(489) =< s(483)*(1/2)+s(485) s(491) =< s(483)*(1/2)+s(485) s(487) =< s(483)*(1/2)+s(485) s(494) =< s(488)*s(492) s(495) =< s(488)*s(493) s(496) =< s(487)*s(493) s(497) =< s(496) s(498) =< s(497)*s(484) with precondition: [Out=2,V1>=1,V>=1] * Chain [91]: 11*s(538)+6*s(539)+1*s(540)+1*s(541)+3*s(542)+1*s(545)+2*s(546)+83*s(548)+9*s(549)+0 Such that:s(533) =< V1 s(534) =< V1+1 s(535) =< 2*V1 s(536) =< V1/2 s(537) =< 4/5*V1 s(538) =< s(533) s(539) =< s(533) s(540) =< s(536) s(541) =< s(537) s(540) =< s(537) s(542) =< s(537) s(543) =< s(535)+2 s(544) =< s(535) s(541) =< s(534)*(1/5)+s(537) s(540) =< s(534)*(1/5)+s(537) s(542) =< s(534)*(1/5)+s(537) s(538) =< s(534)*(1/5)+s(537) s(540) =< s(534)*(1/2)+s(536) s(542) =< s(534)*(1/2)+s(536) s(538) =< s(534)*(1/2)+s(536) s(545) =< s(539)*s(543) s(546) =< s(539)*s(544) s(547) =< s(538)*s(544) s(548) =< s(547) s(549) =< s(548)*s(535) with precondition: [V=3,Out=0,V1>=0] * Chain [90]: 22*s(555)+12*s(556)+2*s(557)+2*s(558)+6*s(559)+2*s(562)+4*s(563)+166*s(565)+18*s(566)+44*s(572)+24*s(573)+4*s(574)+4*s(575)+12*s(576)+4*s(579)+8*s(580)+332*s(582)+36*s(583)+1 Such that:aux(66) =< V1 aux(67) =< V1+1 aux(68) =< 2*V1 aux(69) =< V1/2 aux(70) =< 4/5*V1 aux(71) =< V aux(72) =< V+1 aux(73) =< 2*V aux(74) =< V/2 aux(75) =< 4/5*V s(572) =< aux(71) s(573) =< aux(71) s(574) =< aux(74) s(575) =< aux(75) s(574) =< aux(75) s(576) =< aux(75) s(577) =< aux(73)+2 s(578) =< aux(73) s(575) =< aux(72)*(1/5)+aux(75) s(574) =< aux(72)*(1/5)+aux(75) s(576) =< aux(72)*(1/5)+aux(75) s(572) =< aux(72)*(1/5)+aux(75) s(574) =< aux(72)*(1/2)+aux(74) s(576) =< aux(72)*(1/2)+aux(74) s(572) =< aux(72)*(1/2)+aux(74) s(579) =< s(573)*s(577) s(580) =< s(573)*s(578) s(581) =< s(572)*s(578) s(582) =< s(581) s(583) =< s(582)*aux(73) s(555) =< aux(66) s(556) =< aux(66) s(557) =< aux(69) s(558) =< aux(70) s(557) =< aux(70) s(559) =< aux(70) s(560) =< aux(68)+2 s(561) =< aux(68) s(558) =< aux(67)*(1/5)+aux(70) s(557) =< aux(67)*(1/5)+aux(70) s(559) =< aux(67)*(1/5)+aux(70) s(555) =< aux(67)*(1/5)+aux(70) s(557) =< aux(67)*(1/2)+aux(69) s(559) =< aux(67)*(1/2)+aux(69) s(555) =< aux(67)*(1/2)+aux(69) s(562) =< s(556)*s(560) s(563) =< s(556)*s(561) s(564) =< s(555)*s(561) s(565) =< s(564) s(566) =< s(565)*aux(68) with precondition: [Out=1,V1>=0,V>=1] * Chain [89]: 11*s(657)+6*s(658)+1*s(659)+1*s(660)+3*s(661)+1*s(664)+2*s(665)+83*s(667)+9*s(668)+0 Such that:s(652) =< V s(653) =< V+1 s(654) =< 2*V s(655) =< V/2 s(656) =< 4/5*V s(657) =< s(652) s(658) =< s(652) s(659) =< s(655) s(660) =< s(656) s(659) =< s(656) s(661) =< s(656) s(662) =< s(654)+2 s(663) =< s(654) s(660) =< s(653)*(1/5)+s(656) s(659) =< s(653)*(1/5)+s(656) s(661) =< s(653)*(1/5)+s(656) s(657) =< s(653)*(1/5)+s(656) s(659) =< s(653)*(1/2)+s(655) s(661) =< s(653)*(1/2)+s(655) s(657) =< s(653)*(1/2)+s(655) s(664) =< s(658)*s(662) s(665) =< s(658)*s(663) s(666) =< s(657)*s(663) s(667) =< s(666) s(668) =< s(667)*s(654) with precondition: [V1=3,Out=0,V>=0] * Chain [88]: 0 with precondition: [V1=3,V=3,Out=0] * Chain [87]: 11*s(674)+6*s(675)+1*s(676)+1*s(677)+3*s(678)+1*s(681)+2*s(682)+83*s(684)+9*s(685)+11*s(691)+6*s(692)+1*s(693)+1*s(694)+3*s(695)+1*s(698)+2*s(699)+83*s(701)+9*s(702)+1 Such that:s(669) =< V1 s(670) =< V1+1 s(671) =< 2*V1 s(672) =< V1/2 s(673) =< 4/5*V1 s(686) =< V s(687) =< V+1 s(688) =< 2*V s(689) =< V/2 s(690) =< 4/5*V s(674) =< s(669) s(675) =< s(669) s(676) =< s(672) s(677) =< s(673) s(676) =< s(673) s(678) =< s(673) s(679) =< s(671)+2 s(680) =< s(671) s(677) =< s(670)*(1/5)+s(673) s(676) =< s(670)*(1/5)+s(673) s(678) =< s(670)*(1/5)+s(673) s(674) =< s(670)*(1/5)+s(673) s(676) =< s(670)*(1/2)+s(672) s(678) =< s(670)*(1/2)+s(672) s(674) =< s(670)*(1/2)+s(672) s(681) =< s(675)*s(679) s(682) =< s(675)*s(680) s(683) =< s(674)*s(680) s(684) =< s(683) s(685) =< s(684)*s(671) s(691) =< s(686) s(692) =< s(686) s(693) =< s(689) s(694) =< s(690) s(693) =< s(690) s(695) =< s(690) s(696) =< s(688)+2 s(697) =< s(688) s(694) =< s(687)*(1/5)+s(690) s(693) =< s(687)*(1/5)+s(690) s(695) =< s(687)*(1/5)+s(690) s(691) =< s(687)*(1/5)+s(690) s(693) =< s(687)*(1/2)+s(689) s(695) =< s(687)*(1/2)+s(689) s(691) =< s(687)*(1/2)+s(689) s(698) =< s(692)*s(696) s(699) =< s(692)*s(697) s(700) =< s(691)*s(697) s(701) =< s(700) s(702) =< s(701)*s(688) with precondition: [Out=1,V1>=1,V>=0] * Chain [86]: 11*s(708)+6*s(709)+1*s(710)+1*s(711)+3*s(712)+1*s(715)+2*s(716)+83*s(718)+9*s(719)+0 Such that:s(703) =< V1 s(704) =< V1+1 s(705) =< 2*V1 s(706) =< V1/2 s(707) =< 4/5*V1 s(708) =< s(703) s(709) =< s(703) s(710) =< s(706) s(711) =< s(707) s(710) =< s(707) s(712) =< s(707) s(713) =< s(705)+2 s(714) =< s(705) s(711) =< s(704)*(1/5)+s(707) s(710) =< s(704)*(1/5)+s(707) s(712) =< s(704)*(1/5)+s(707) s(708) =< s(704)*(1/5)+s(707) s(710) =< s(704)*(1/2)+s(706) s(712) =< s(704)*(1/2)+s(706) s(708) =< s(704)*(1/2)+s(706) s(715) =< s(709)*s(713) s(716) =< s(709)*s(714) s(717) =< s(708)*s(714) s(718) =< s(717) s(719) =< s(718)*s(705) with precondition: [V=2,Out=0,V1>=0] * Chain [85]: 11*s(725)+6*s(726)+1*s(727)+1*s(728)+3*s(729)+1*s(732)+2*s(733)+83*s(735)+9*s(736)+1 Such that:s(720) =< V1 s(721) =< V1+1 s(722) =< 2*V1 s(723) =< V1/2 s(724) =< 4/5*V1 s(725) =< s(720) s(726) =< s(720) s(727) =< s(723) s(728) =< s(724) s(727) =< s(724) s(729) =< s(724) s(730) =< s(722)+2 s(731) =< s(722) s(728) =< s(721)*(1/5)+s(724) s(727) =< s(721)*(1/5)+s(724) s(729) =< s(721)*(1/5)+s(724) s(725) =< s(721)*(1/5)+s(724) s(727) =< s(721)*(1/2)+s(723) s(729) =< s(721)*(1/2)+s(723) s(725) =< s(721)*(1/2)+s(723) s(732) =< s(726)*s(730) s(733) =< s(726)*s(731) s(734) =< s(725)*s(731) s(735) =< s(734) s(736) =< s(735)*s(722) with precondition: [V=2,Out=1,V1>=1] * Chain [84]: 11*s(742)+6*s(743)+1*s(744)+1*s(745)+3*s(746)+1*s(749)+2*s(750)+83*s(752)+9*s(753)+1 Such that:s(737) =< V1 s(738) =< V1+1 s(739) =< 2*V1 s(740) =< V1/2 s(741) =< 4/5*V1 s(742) =< s(737) s(743) =< s(737) s(744) =< s(740) s(745) =< s(741) s(744) =< s(741) s(746) =< s(741) s(747) =< s(739)+2 s(748) =< s(739) s(745) =< s(738)*(1/5)+s(741) s(744) =< s(738)*(1/5)+s(741) s(746) =< s(738)*(1/5)+s(741) s(742) =< s(738)*(1/5)+s(741) s(744) =< s(738)*(1/2)+s(740) s(746) =< s(738)*(1/2)+s(740) s(742) =< s(738)*(1/2)+s(740) s(749) =< s(743)*s(747) s(750) =< s(743)*s(748) s(751) =< s(742)*s(748) s(752) =< s(751) s(753) =< s(752)*s(739) with precondition: [V=2,Out=2,V1>=1] * Chain [83]: 11*s(759)+6*s(760)+1*s(761)+1*s(762)+3*s(763)+1*s(766)+2*s(767)+83*s(769)+9*s(770)+1 Such that:s(754) =< V1 s(755) =< V1+1 s(756) =< 2*V1 s(757) =< V1/2 s(758) =< 4/5*V1 s(759) =< s(754) s(760) =< s(754) s(761) =< s(757) s(762) =< s(758) s(761) =< s(758) s(763) =< s(758) s(764) =< s(756)+2 s(765) =< s(756) s(762) =< s(755)*(1/5)+s(758) s(761) =< s(755)*(1/5)+s(758) s(763) =< s(755)*(1/5)+s(758) s(759) =< s(755)*(1/5)+s(758) s(761) =< s(755)*(1/2)+s(757) s(763) =< s(755)*(1/2)+s(757) s(759) =< s(755)*(1/2)+s(757) s(766) =< s(760)*s(764) s(767) =< s(760)*s(765) s(768) =< s(759)*s(765) s(769) =< s(768) s(770) =< s(769)*s(756) with precondition: [V=3,Out=1,V1>=1] #### Cost of chains of fun3(V1,Out): * Chain [98]: 11*s(980)+6*s(981)+1*s(982)+1*s(983)+3*s(984)+1*s(987)+2*s(988)+83*s(990)+9*s(991)+1*s(992)+1*s(993)+0 Such that:s(993) =< 2 s(975) =< V1 s(976) =< V1+1 aux(96) =< 2*V1 s(978) =< V1/2 s(979) =< 4/5*V1 s(992) =< aux(96) s(980) =< s(975) s(981) =< s(975) s(982) =< s(978) s(983) =< s(979) s(982) =< s(979) s(984) =< s(979) s(985) =< aux(96)+2 s(986) =< aux(96) s(983) =< s(976)*(1/5)+s(979) s(982) =< s(976)*(1/5)+s(979) s(984) =< s(976)*(1/5)+s(979) s(980) =< s(976)*(1/5)+s(979) s(982) =< s(976)*(1/2)+s(978) s(984) =< s(976)*(1/2)+s(978) s(980) =< s(976)*(1/2)+s(978) s(987) =< s(981)*s(985) s(988) =< s(981)*s(986) s(989) =< s(980)*s(986) s(990) =< s(989) s(991) =< s(990)*aux(96) with precondition: [Out=0,V1>=0] * Chain [97]: 22*s(1000)+12*s(1001)+2*s(1002)+2*s(1003)+6*s(1004)+2*s(1007)+4*s(1008)+166*s(1010)+18*s(1011)+1*s(1029)+1*s(1030)+1 Such that:s(1030) =< 2 aux(98) =< V1 aux(99) =< V1+1 aux(100) =< 2*V1 aux(101) =< V1/2 aux(102) =< 4/5*V1 s(1000) =< aux(98) s(1001) =< aux(98) s(1002) =< aux(101) s(1003) =< aux(102) s(1002) =< aux(102) s(1004) =< aux(102) s(1005) =< aux(100)+2 s(1006) =< aux(100) s(1003) =< aux(99)*(1/5)+aux(102) s(1002) =< aux(99)*(1/5)+aux(102) s(1004) =< aux(99)*(1/5)+aux(102) s(1000) =< aux(99)*(1/5)+aux(102) s(1002) =< aux(99)*(1/2)+aux(101) s(1004) =< aux(99)*(1/2)+aux(101) s(1000) =< aux(99)*(1/2)+aux(101) s(1007) =< s(1001)*s(1005) s(1008) =< s(1001)*s(1006) s(1009) =< s(1000)*s(1006) s(1010) =< s(1009) s(1011) =< s(1010)*aux(100) s(1029) =< aux(100) with precondition: [Out=2,V1>=0] * Chain [96]: 1*s(1031)+0 Such that:s(1031) =< 3 with precondition: [V1=3,Out=0] * Chain [95]: 22*s(1037)+12*s(1038)+2*s(1039)+2*s(1040)+6*s(1041)+2*s(1044)+4*s(1045)+166*s(1047)+18*s(1048)+1*s(1066)+1*s(1067)+1 Such that:s(1067) =< 3 aux(104) =< V1 aux(105) =< V1+1 aux(106) =< 2*V1 aux(107) =< V1/2 aux(108) =< 4/5*V1 s(1037) =< aux(104) s(1038) =< aux(104) s(1039) =< aux(107) s(1040) =< aux(108) s(1039) =< aux(108) s(1041) =< aux(108) s(1042) =< aux(106)+2 s(1043) =< aux(106) s(1040) =< aux(105)*(1/5)+aux(108) s(1039) =< aux(105)*(1/5)+aux(108) s(1041) =< aux(105)*(1/5)+aux(108) s(1037) =< aux(105)*(1/5)+aux(108) s(1039) =< aux(105)*(1/2)+aux(107) s(1041) =< aux(105)*(1/2)+aux(107) s(1037) =< aux(105)*(1/2)+aux(107) s(1044) =< s(1038)*s(1042) s(1045) =< s(1038)*s(1043) s(1046) =< s(1037)*s(1043) s(1047) =< s(1046) s(1048) =< s(1047)*aux(106) s(1066) =< aux(106) with precondition: [Out=1,V1>=1] * Chain [94]: 1*s(1068)+1 Such that:s(1068) =< 3 with precondition: [V1=3,Out=2] #### Cost of chains of fun4(V1,V,Out): * Chain [107]: 22*s(1114)+12*s(1115)+2*s(1116)+2*s(1117)+6*s(1118)+2*s(1121)+4*s(1122)+166*s(1124)+18*s(1125)+33*s(1131)+18*s(1132)+3*s(1133)+3*s(1134)+9*s(1135)+3*s(1138)+6*s(1139)+249*s(1141)+27*s(1142)+1 Such that:aux(109) =< V1 aux(110) =< V1+1 aux(111) =< 2*V1 aux(112) =< V1/2 aux(113) =< 4/5*V1 aux(114) =< V aux(115) =< V+1 aux(116) =< 2*V aux(117) =< V/2 aux(118) =< 4/5*V s(1131) =< aux(114) s(1132) =< aux(114) s(1133) =< aux(117) s(1134) =< aux(118) s(1133) =< aux(118) s(1135) =< aux(118) s(1136) =< aux(116)+2 s(1137) =< aux(116) s(1134) =< aux(115)*(1/5)+aux(118) s(1133) =< aux(115)*(1/5)+aux(118) s(1135) =< aux(115)*(1/5)+aux(118) s(1131) =< aux(115)*(1/5)+aux(118) s(1133) =< aux(115)*(1/2)+aux(117) s(1135) =< aux(115)*(1/2)+aux(117) s(1131) =< aux(115)*(1/2)+aux(117) s(1138) =< s(1132)*s(1136) s(1139) =< s(1132)*s(1137) s(1140) =< s(1131)*s(1137) s(1141) =< s(1140) s(1142) =< s(1141)*aux(116) s(1114) =< aux(109) s(1115) =< aux(109) s(1116) =< aux(112) s(1117) =< aux(113) s(1116) =< aux(113) s(1118) =< aux(113) s(1119) =< aux(111)+2 s(1120) =< aux(111) s(1117) =< aux(110)*(1/5)+aux(113) s(1116) =< aux(110)*(1/5)+aux(113) s(1118) =< aux(110)*(1/5)+aux(113) s(1114) =< aux(110)*(1/5)+aux(113) s(1116) =< aux(110)*(1/2)+aux(112) s(1118) =< aux(110)*(1/2)+aux(112) s(1114) =< aux(110)*(1/2)+aux(112) s(1121) =< s(1115)*s(1119) s(1122) =< s(1115)*s(1120) s(1123) =< s(1114)*s(1120) s(1124) =< s(1123) s(1125) =< s(1124)*aux(111) with precondition: [Out=0,V1>=0,V>=0] * Chain [106]: 11*s(1199)+6*s(1200)+1*s(1201)+1*s(1202)+3*s(1203)+1*s(1206)+2*s(1207)+83*s(1209)+9*s(1210)+1 Such that:s(1194) =< V1 s(1195) =< V1+1 s(1196) =< 2*V1 s(1197) =< V1/2 s(1198) =< 4/5*V1 s(1199) =< s(1194) s(1200) =< s(1194) s(1201) =< s(1197) s(1202) =< s(1198) s(1201) =< s(1198) s(1203) =< s(1198) s(1204) =< s(1196)+2 s(1205) =< s(1196) s(1202) =< s(1195)*(1/5)+s(1198) s(1201) =< s(1195)*(1/5)+s(1198) s(1203) =< s(1195)*(1/5)+s(1198) s(1199) =< s(1195)*(1/5)+s(1198) s(1201) =< s(1195)*(1/2)+s(1197) s(1203) =< s(1195)*(1/2)+s(1197) s(1199) =< s(1195)*(1/2)+s(1197) s(1206) =< s(1200)*s(1204) s(1207) =< s(1200)*s(1205) s(1208) =< s(1199)*s(1205) s(1209) =< s(1208) s(1210) =< s(1209)*s(1196) with precondition: [V=3,Out=0,V1>=0] * Chain [105]: 22*s(1216)+12*s(1217)+2*s(1218)+2*s(1219)+6*s(1220)+2*s(1223)+4*s(1224)+166*s(1226)+18*s(1227)+22*s(1233)+12*s(1234)+2*s(1235)+2*s(1236)+6*s(1237)+2*s(1240)+4*s(1241)+166*s(1243)+18*s(1244)+1 Such that:aux(119) =< V1 aux(120) =< V1+1 aux(121) =< 2*V1 aux(122) =< V1/2 aux(123) =< 4/5*V1 aux(124) =< V aux(125) =< V+1 aux(126) =< 2*V aux(127) =< V/2 aux(128) =< 4/5*V s(1233) =< aux(124) s(1234) =< aux(124) s(1235) =< aux(127) s(1236) =< aux(128) s(1235) =< aux(128) s(1237) =< aux(128) s(1238) =< aux(126)+2 s(1239) =< aux(126) s(1236) =< aux(125)*(1/5)+aux(128) s(1235) =< aux(125)*(1/5)+aux(128) s(1237) =< aux(125)*(1/5)+aux(128) s(1233) =< aux(125)*(1/5)+aux(128) s(1235) =< aux(125)*(1/2)+aux(127) s(1237) =< aux(125)*(1/2)+aux(127) s(1233) =< aux(125)*(1/2)+aux(127) s(1240) =< s(1234)*s(1238) s(1241) =< s(1234)*s(1239) s(1242) =< s(1233)*s(1239) s(1243) =< s(1242) s(1244) =< s(1243)*aux(126) s(1216) =< aux(119) s(1217) =< aux(119) s(1218) =< aux(122) s(1219) =< aux(123) s(1218) =< aux(123) s(1220) =< aux(123) s(1221) =< aux(121)+2 s(1222) =< aux(121) s(1219) =< aux(120)*(1/5)+aux(123) s(1218) =< aux(120)*(1/5)+aux(123) s(1220) =< aux(120)*(1/5)+aux(123) s(1216) =< aux(120)*(1/5)+aux(123) s(1218) =< aux(120)*(1/2)+aux(122) s(1220) =< aux(120)*(1/2)+aux(122) s(1216) =< aux(120)*(1/2)+aux(122) s(1223) =< s(1217)*s(1221) s(1224) =< s(1217)*s(1222) s(1225) =< s(1216)*s(1222) s(1226) =< s(1225) s(1227) =< s(1226)*aux(121) with precondition: [Out=2,V1>=1,V>=0] * Chain [104]: 11*s(1284)+6*s(1285)+1*s(1286)+1*s(1287)+3*s(1288)+1*s(1291)+2*s(1292)+83*s(1294)+9*s(1295)+1 Such that:s(1279) =< V s(1280) =< V+1 s(1281) =< 2*V s(1282) =< V/2 s(1283) =< 4/5*V s(1284) =< s(1279) s(1285) =< s(1279) s(1286) =< s(1282) s(1287) =< s(1283) s(1286) =< s(1283) s(1288) =< s(1283) s(1289) =< s(1281)+2 s(1290) =< s(1281) s(1287) =< s(1280)*(1/5)+s(1283) s(1286) =< s(1280)*(1/5)+s(1283) s(1288) =< s(1280)*(1/5)+s(1283) s(1284) =< s(1280)*(1/5)+s(1283) s(1286) =< s(1280)*(1/2)+s(1282) s(1288) =< s(1280)*(1/2)+s(1282) s(1284) =< s(1280)*(1/2)+s(1282) s(1291) =< s(1285)*s(1289) s(1292) =< s(1285)*s(1290) s(1293) =< s(1284)*s(1290) s(1294) =< s(1293) s(1295) =< s(1294)*s(1281) with precondition: [V1=3,Out=0,V>=0] * Chain [103]: 1 with precondition: [V1=3,V=3,Out=0] * Chain [102]: 11*s(1301)+6*s(1302)+1*s(1303)+1*s(1304)+3*s(1305)+1*s(1308)+2*s(1309)+83*s(1311)+9*s(1312)+1 Such that:s(1296) =< V s(1297) =< V+1 s(1298) =< 2*V s(1299) =< V/2 s(1300) =< 4/5*V s(1301) =< s(1296) s(1302) =< s(1296) s(1303) =< s(1299) s(1304) =< s(1300) s(1303) =< s(1300) s(1305) =< s(1300) s(1306) =< s(1298)+2 s(1307) =< s(1298) s(1304) =< s(1297)*(1/5)+s(1300) s(1303) =< s(1297)*(1/5)+s(1300) s(1305) =< s(1297)*(1/5)+s(1300) s(1301) =< s(1297)*(1/5)+s(1300) s(1303) =< s(1297)*(1/2)+s(1299) s(1305) =< s(1297)*(1/2)+s(1299) s(1301) =< s(1297)*(1/2)+s(1299) s(1308) =< s(1302)*s(1306) s(1309) =< s(1302)*s(1307) s(1310) =< s(1301)*s(1307) s(1311) =< s(1310) s(1312) =< s(1311)*s(1298) with precondition: [V1=3,Out=2,V>=0] * Chain [101]: 11*s(1318)+6*s(1319)+1*s(1320)+1*s(1321)+3*s(1322)+1*s(1325)+2*s(1326)+83*s(1328)+9*s(1329)+1 Such that:s(1313) =< V1 s(1314) =< V1+1 s(1315) =< 2*V1 s(1316) =< V1/2 s(1317) =< 4/5*V1 s(1318) =< s(1313) s(1319) =< s(1313) s(1320) =< s(1316) s(1321) =< s(1317) s(1320) =< s(1317) s(1322) =< s(1317) s(1323) =< s(1315)+2 s(1324) =< s(1315) s(1321) =< s(1314)*(1/5)+s(1317) s(1320) =< s(1314)*(1/5)+s(1317) s(1322) =< s(1314)*(1/5)+s(1317) s(1318) =< s(1314)*(1/5)+s(1317) s(1320) =< s(1314)*(1/2)+s(1316) s(1322) =< s(1314)*(1/2)+s(1316) s(1318) =< s(1314)*(1/2)+s(1316) s(1325) =< s(1319)*s(1323) s(1326) =< s(1319)*s(1324) s(1327) =< s(1318)*s(1324) s(1328) =< s(1327) s(1329) =< s(1328)*s(1315) with precondition: [V=2,Out=0,V1>=0] * Chain [100]: 44*s(1335)+24*s(1336)+4*s(1337)+4*s(1338)+12*s(1339)+4*s(1342)+8*s(1343)+332*s(1345)+36*s(1346)+33*s(1352)+18*s(1353)+3*s(1354)+3*s(1355)+9*s(1356)+3*s(1359)+6*s(1360)+249*s(1362)+27*s(1363)+2 Such that:aux(129) =< V1 aux(130) =< V1+1 aux(131) =< 2*V1 aux(132) =< V1/2 aux(133) =< 4/5*V1 aux(134) =< V aux(135) =< V+1 aux(136) =< 2*V aux(137) =< V/2 aux(138) =< 4/5*V s(1352) =< aux(134) s(1353) =< aux(134) s(1354) =< aux(137) s(1355) =< aux(138) s(1354) =< aux(138) s(1356) =< aux(138) s(1357) =< aux(136)+2 s(1358) =< aux(136) s(1355) =< aux(135)*(1/5)+aux(138) s(1354) =< aux(135)*(1/5)+aux(138) s(1356) =< aux(135)*(1/5)+aux(138) s(1352) =< aux(135)*(1/5)+aux(138) s(1354) =< aux(135)*(1/2)+aux(137) s(1356) =< aux(135)*(1/2)+aux(137) s(1352) =< aux(135)*(1/2)+aux(137) s(1359) =< s(1353)*s(1357) s(1360) =< s(1353)*s(1358) s(1361) =< s(1352)*s(1358) s(1362) =< s(1361) s(1363) =< s(1362)*aux(136) s(1335) =< aux(129) s(1336) =< aux(129) s(1337) =< aux(132) s(1338) =< aux(133) s(1337) =< aux(133) s(1339) =< aux(133) s(1340) =< aux(131)+2 s(1341) =< aux(131) s(1338) =< aux(130)*(1/5)+aux(133) s(1337) =< aux(130)*(1/5)+aux(133) s(1339) =< aux(130)*(1/5)+aux(133) s(1335) =< aux(130)*(1/5)+aux(133) s(1337) =< aux(130)*(1/2)+aux(132) s(1339) =< aux(130)*(1/2)+aux(132) s(1335) =< aux(130)*(1/2)+aux(132) s(1342) =< s(1336)*s(1340) s(1343) =< s(1336)*s(1341) s(1344) =< s(1335)*s(1341) s(1345) =< s(1344) s(1346) =< s(1345)*aux(131) with precondition: [Out=1,V1>=0,V>=0] * Chain [99]: 11*s(1454)+6*s(1455)+1*s(1456)+1*s(1457)+3*s(1458)+1*s(1461)+2*s(1462)+83*s(1464)+9*s(1465)+1 Such that:s(1449) =< V1 s(1450) =< V1+1 s(1451) =< 2*V1 s(1452) =< V1/2 s(1453) =< 4/5*V1 s(1454) =< s(1449) s(1455) =< s(1449) s(1456) =< s(1452) s(1457) =< s(1453) s(1456) =< s(1453) s(1458) =< s(1453) s(1459) =< s(1451)+2 s(1460) =< s(1451) s(1457) =< s(1450)*(1/5)+s(1453) s(1456) =< s(1450)*(1/5)+s(1453) s(1458) =< s(1450)*(1/5)+s(1453) s(1454) =< s(1450)*(1/5)+s(1453) s(1456) =< s(1450)*(1/2)+s(1452) s(1458) =< s(1450)*(1/2)+s(1452) s(1454) =< s(1450)*(1/2)+s(1452) s(1461) =< s(1455)*s(1459) s(1462) =< s(1455)*s(1460) s(1463) =< s(1454)*s(1460) s(1464) =< s(1463) s(1465) =< s(1464)*s(1451) with precondition: [V=3,Out=1,V1>=0] #### Cost of chains of fun6(V1,Out): * Chain [111]: 11*s(1624)+6*s(1625)+1*s(1626)+1*s(1627)+3*s(1628)+1*s(1631)+2*s(1632)+83*s(1634)+9*s(1635)+1 Such that:s(1619) =< V1 s(1620) =< V1+1 s(1621) =< 2*V1 s(1622) =< V1/2 s(1623) =< 4/5*V1 s(1624) =< s(1619) s(1625) =< s(1619) s(1626) =< s(1622) s(1627) =< s(1623) s(1626) =< s(1623) s(1628) =< s(1623) s(1629) =< s(1621)+2 s(1630) =< s(1621) s(1627) =< s(1620)*(1/5)+s(1623) s(1626) =< s(1620)*(1/5)+s(1623) s(1628) =< s(1620)*(1/5)+s(1623) s(1624) =< s(1620)*(1/5)+s(1623) s(1626) =< s(1620)*(1/2)+s(1622) s(1628) =< s(1620)*(1/2)+s(1622) s(1624) =< s(1620)*(1/2)+s(1622) s(1631) =< s(1625)*s(1629) s(1632) =< s(1625)*s(1630) s(1633) =< s(1624)*s(1630) s(1634) =< s(1633) s(1635) =< s(1634)*s(1621) with precondition: [Out=0,V1>=0] * Chain [110]: 11*s(1641)+6*s(1642)+1*s(1643)+1*s(1644)+3*s(1645)+1*s(1648)+2*s(1649)+83*s(1651)+9*s(1652)+1 Such that:s(1636) =< V1 s(1637) =< V1+1 s(1638) =< 2*V1 s(1639) =< V1/2 s(1640) =< 4/5*V1 s(1641) =< s(1636) s(1642) =< s(1636) s(1643) =< s(1639) s(1644) =< s(1640) s(1643) =< s(1640) s(1645) =< s(1640) s(1646) =< s(1638)+2 s(1647) =< s(1638) s(1644) =< s(1637)*(1/5)+s(1640) s(1643) =< s(1637)*(1/5)+s(1640) s(1645) =< s(1637)*(1/5)+s(1640) s(1641) =< s(1637)*(1/5)+s(1640) s(1643) =< s(1637)*(1/2)+s(1639) s(1645) =< s(1637)*(1/2)+s(1639) s(1641) =< s(1637)*(1/2)+s(1639) s(1648) =< s(1642)*s(1646) s(1649) =< s(1642)*s(1647) s(1650) =< s(1641)*s(1647) s(1651) =< s(1650) s(1652) =< s(1651)*s(1638) with precondition: [V1>=1,Out>=0,2*V1>=Out+1] * Chain [109]: 1 with precondition: [V1=3,Out=0] * Chain [108]: 1 with precondition: [V1=3,Out=2] #### Cost of chains of fun7(Out): * Chain [113]: 0 with precondition: [Out=0] * Chain [112]: 0 with precondition: [Out=1] #### Cost of chains of fun8(V1,Out): * Chain [117]: 11*s(1692)+6*s(1693)+1*s(1694)+1*s(1695)+3*s(1696)+1*s(1699)+2*s(1700)+83*s(1702)+9*s(1703)+0 Such that:s(1687) =< V1 s(1688) =< V1+1 s(1689) =< 2*V1 s(1690) =< V1/2 s(1691) =< 4/5*V1 s(1692) =< s(1687) s(1693) =< s(1687) s(1694) =< s(1690) s(1695) =< s(1691) s(1694) =< s(1691) s(1696) =< s(1691) s(1697) =< s(1689)+2 s(1698) =< s(1689) s(1695) =< s(1688)*(1/5)+s(1691) s(1694) =< s(1688)*(1/5)+s(1691) s(1696) =< s(1688)*(1/5)+s(1691) s(1692) =< s(1688)*(1/5)+s(1691) s(1694) =< s(1688)*(1/2)+s(1690) s(1696) =< s(1688)*(1/2)+s(1690) s(1692) =< s(1688)*(1/2)+s(1690) s(1699) =< s(1693)*s(1697) s(1700) =< s(1693)*s(1698) s(1701) =< s(1692)*s(1698) s(1702) =< s(1701) s(1703) =< s(1702)*s(1689) with precondition: [V1>=1,Out>=1,2*V1+1>=Out] * Chain [116]: 0 with precondition: [V1=3,Out=4] * Chain [115]: 0 with precondition: [Out=0,V1>=0] * Chain [114]: 0 with precondition: [Out=1,V1>=0] #### Cost of chains of fun9(Out): * Chain [119]: 0 with precondition: [Out=0] * Chain [118]: 0 with precondition: [Out=3] #### Cost of chains of start(V1,V): * Chain [120]: 245*s(1722)+9*s(1723)+219*s(1724)+396*s(1732)+36*s(1734)+36*s(1735)+108*s(1736)+36*s(1739)+72*s(1740)+2988*s(1742)+324*s(1743)+334*s(1756)+36*s(1757)+332*s(1758)+36*s(1759)+297*s(1760)+27*s(1762)+27*s(1763)+81*s(1764)+27*s(1767)+54*s(1768)+2241*s(1770)+243*s(1771)+335*s(1784)+36*s(1785)+3*s(2003)+10 Such that:aux(154) =< 2 aux(155) =< 3 aux(156) =< V1 aux(157) =< V1+1 aux(158) =< 2*V1 aux(159) =< V1/2 aux(160) =< 4/5*V1 aux(161) =< V aux(162) =< V+1 aux(163) =< 2*V aux(164) =< V/2 aux(165) =< 4/5*V s(1756) =< aux(154) s(1784) =< aux(155) s(1724) =< aux(156) s(1757) =< s(1756)*aux(154) s(1758) =< aux(163) s(1759) =< s(1758)*aux(163) s(1760) =< aux(161) s(1722) =< aux(161) s(1762) =< aux(164) s(1763) =< aux(165) s(1762) =< aux(165) s(1764) =< aux(165) s(1765) =< aux(163)+2 s(1766) =< aux(163) s(1763) =< aux(162)*(1/5)+aux(165) s(1762) =< aux(162)*(1/5)+aux(165) s(1764) =< aux(162)*(1/5)+aux(165) s(1760) =< aux(162)*(1/5)+aux(165) s(1762) =< aux(162)*(1/2)+aux(164) s(1764) =< aux(162)*(1/2)+aux(164) s(1760) =< aux(162)*(1/2)+aux(164) s(1767) =< s(1722)*s(1765) s(1768) =< s(1722)*s(1766) s(1769) =< s(1760)*s(1766) s(1770) =< s(1769) s(1771) =< s(1770)*aux(163) s(1732) =< aux(156) s(1734) =< aux(159) s(1735) =< aux(160) s(1734) =< aux(160) s(1736) =< aux(160) s(1737) =< aux(158)+2 s(1738) =< aux(158) s(1735) =< aux(157)*(1/5)+aux(160) s(1734) =< aux(157)*(1/5)+aux(160) s(1736) =< aux(157)*(1/5)+aux(160) s(1732) =< aux(157)*(1/5)+aux(160) s(1734) =< aux(157)*(1/2)+aux(159) s(1736) =< aux(157)*(1/2)+aux(159) s(1732) =< aux(157)*(1/2)+aux(159) s(1739) =< s(1724)*s(1737) s(1740) =< s(1724)*s(1738) s(1741) =< s(1732)*s(1738) s(1742) =< s(1741) s(1743) =< s(1742)*aux(158) s(1785) =< s(1784)*aux(155) s(2003) =< aux(158) s(1723) =< s(1722)*aux(161) with precondition: [] Closed-form bounds of start(V1,V): ------------------------------------- * Chain [120] with precondition: [] - Upper bound: nat(V1)*687+2151+nat(V1)*3096*nat(2*V1)+nat(V1)*324*nat(2*V1)*nat(2*V1)+nat(V)*596+nat(V)*9*nat(V)+nat(V)*2322*nat(2*V)+nat(V)*243*nat(2*V)*nat(2*V)+nat(2*V1)*3+nat(2*V)*332+nat(2*V)*36*nat(2*V)+nat(4/5*V1)*144+nat(4/5*V)*108+nat(V1/2)*36+nat(V/2)*27 - Complexity: n^3 ### Maximum cost of start(V1,V): nat(V1)*687+2151+nat(V1)*3096*nat(2*V1)+nat(V1)*324*nat(2*V1)*nat(2*V1)+nat(V)*596+nat(V)*9*nat(V)+nat(V)*2322*nat(2*V)+nat(V)*243*nat(2*V)*nat(2*V)+nat(2*V1)*3+nat(2*V)*332+nat(2*V)*36*nat(2*V)+nat(4/5*V1)*144+nat(4/5*V)*108+nat(V1/2)*36+nat(V/2)*27 Asymptotic class: n^3 * Total analysis performed in 3404 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: cond(true, x) -> cond(and(even(x), gr(x, 0')), p(x)) and(x, false) -> false and(false, x) -> false and(true, true) -> true even(0') -> true even(s(0')) -> false even(s(s(x))) -> even(x) gr(0', x) -> false gr(s(x), 0') -> true gr(s(x), s(y)) -> gr(x, y) p(0') -> 0' p(s(x)) -> x The (relative) TRS S consists of the following rules: encArg(true) -> true encArg(0') -> 0' encArg(false) -> false encArg(s(x_1)) -> s(encArg(x_1)) encArg(y) -> y encArg(cons_cond(x_1, x_2)) -> cond(encArg(x_1), encArg(x_2)) encArg(cons_and(x_1, x_2)) -> and(encArg(x_1), encArg(x_2)) encArg(cons_even(x_1)) -> even(encArg(x_1)) encArg(cons_gr(x_1, x_2)) -> gr(encArg(x_1), encArg(x_2)) encArg(cons_p(x_1)) -> p(encArg(x_1)) encode_cond(x_1, x_2) -> cond(encArg(x_1), encArg(x_2)) encode_true -> true encode_and(x_1, x_2) -> and(encArg(x_1), encArg(x_2)) encode_even(x_1) -> even(encArg(x_1)) encode_gr(x_1, x_2) -> gr(encArg(x_1), encArg(x_2)) encode_0 -> 0' encode_p(x_1) -> p(encArg(x_1)) encode_false -> false encode_s(x_1) -> s(encArg(x_1)) encode_y -> y Rewrite Strategy: INNERMOST ---------------------------------------- (17) TypeInferenceProof (BOTH BOUNDS(ID, ID)) Infered types. ---------------------------------------- (18) Obligation: Innermost TRS: Rules: cond(true, x) -> cond(and(even(x), gr(x, 0')), p(x)) and(x, false) -> false and(false, x) -> false and(true, true) -> true even(0') -> true even(s(0')) -> false even(s(s(x))) -> even(x) gr(0', x) -> false gr(s(x), 0') -> true gr(s(x), s(y)) -> gr(x, y) p(0') -> 0' p(s(x)) -> x encArg(true) -> true encArg(0') -> 0' encArg(false) -> false encArg(s(x_1)) -> s(encArg(x_1)) encArg(y) -> y encArg(cons_cond(x_1, x_2)) -> cond(encArg(x_1), encArg(x_2)) encArg(cons_and(x_1, x_2)) -> and(encArg(x_1), encArg(x_2)) encArg(cons_even(x_1)) -> even(encArg(x_1)) encArg(cons_gr(x_1, x_2)) -> gr(encArg(x_1), encArg(x_2)) encArg(cons_p(x_1)) -> p(encArg(x_1)) encode_cond(x_1, x_2) -> cond(encArg(x_1), encArg(x_2)) encode_true -> true encode_and(x_1, x_2) -> and(encArg(x_1), encArg(x_2)) encode_even(x_1) -> even(encArg(x_1)) encode_gr(x_1, x_2) -> gr(encArg(x_1), encArg(x_2)) encode_0 -> 0' encode_p(x_1) -> p(encArg(x_1)) encode_false -> false encode_s(x_1) -> s(encArg(x_1)) encode_y -> y Types: cond :: true:0':false:s:y:cons_cond:cons_and:cons_even:cons_gr:cons_p -> true:0':false:s:y:cons_cond:cons_and:cons_even:cons_gr:cons_p -> true:0':false:s:y:cons_cond:cons_and:cons_even:cons_gr:cons_p true :: true:0':false:s:y:cons_cond:cons_and:cons_even:cons_gr:cons_p and :: true:0':false:s:y:cons_cond:cons_and:cons_even:cons_gr:cons_p -> true:0':false:s:y:cons_cond:cons_and:cons_even:cons_gr:cons_p -> true:0':false:s:y:cons_cond:cons_and:cons_even:cons_gr:cons_p even :: true:0':false:s:y:cons_cond:cons_and:cons_even:cons_gr:cons_p -> true:0':false:s:y:cons_cond:cons_and:cons_even:cons_gr:cons_p gr :: true:0':false:s:y:cons_cond:cons_and:cons_even:cons_gr:cons_p -> true:0':false:s:y:cons_cond:cons_and:cons_even:cons_gr:cons_p -> true:0':false:s:y:cons_cond:cons_and:cons_even:cons_gr:cons_p 0' :: true:0':false:s:y:cons_cond:cons_and:cons_even:cons_gr:cons_p p :: true:0':false:s:y:cons_cond:cons_and:cons_even:cons_gr:cons_p -> true:0':false:s:y:cons_cond:cons_and:cons_even:cons_gr:cons_p false :: true:0':false:s:y:cons_cond:cons_and:cons_even:cons_gr:cons_p s :: true:0':false:s:y:cons_cond:cons_and:cons_even:cons_gr:cons_p -> true:0':false:s:y:cons_cond:cons_and:cons_even:cons_gr:cons_p y :: true:0':false:s:y:cons_cond:cons_and:cons_even:cons_gr:cons_p encArg :: true:0':false:s:y:cons_cond:cons_and:cons_even:cons_gr:cons_p -> true:0':false:s:y:cons_cond:cons_and:cons_even:cons_gr:cons_p cons_cond :: true:0':false:s:y:cons_cond:cons_and:cons_even:cons_gr:cons_p -> true:0':false:s:y:cons_cond:cons_and:cons_even:cons_gr:cons_p -> true:0':false:s:y:cons_cond:cons_and:cons_even:cons_gr:cons_p cons_and :: true:0':false:s:y:cons_cond:cons_and:cons_even:cons_gr:cons_p -> true:0':false:s:y:cons_cond:cons_and:cons_even:cons_gr:cons_p -> true:0':false:s:y:cons_cond:cons_and:cons_even:cons_gr:cons_p cons_even :: true:0':false:s:y:cons_cond:cons_and:cons_even:cons_gr:cons_p -> true:0':false:s:y:cons_cond:cons_and:cons_even:cons_gr:cons_p cons_gr :: true:0':false:s:y:cons_cond:cons_and:cons_even:cons_gr:cons_p -> true:0':false:s:y:cons_cond:cons_and:cons_even:cons_gr:cons_p -> true:0':false:s:y:cons_cond:cons_and:cons_even:cons_gr:cons_p cons_p :: true:0':false:s:y:cons_cond:cons_and:cons_even:cons_gr:cons_p -> true:0':false:s:y:cons_cond:cons_and:cons_even:cons_gr:cons_p encode_cond :: true:0':false:s:y:cons_cond:cons_and:cons_even:cons_gr:cons_p -> true:0':false:s:y:cons_cond:cons_and:cons_even:cons_gr:cons_p -> true:0':false:s:y:cons_cond:cons_and:cons_even:cons_gr:cons_p encode_true :: true:0':false:s:y:cons_cond:cons_and:cons_even:cons_gr:cons_p encode_and :: true:0':false:s:y:cons_cond:cons_and:cons_even:cons_gr:cons_p -> true:0':false:s:y:cons_cond:cons_and:cons_even:cons_gr:cons_p -> true:0':false:s:y:cons_cond:cons_and:cons_even:cons_gr:cons_p encode_even :: true:0':false:s:y:cons_cond:cons_and:cons_even:cons_gr:cons_p -> true:0':false:s:y:cons_cond:cons_and:cons_even:cons_gr:cons_p encode_gr :: true:0':false:s:y:cons_cond:cons_and:cons_even:cons_gr:cons_p -> true:0':false:s:y:cons_cond:cons_and:cons_even:cons_gr:cons_p -> true:0':false:s:y:cons_cond:cons_and:cons_even:cons_gr:cons_p encode_0 :: true:0':false:s:y:cons_cond:cons_and:cons_even:cons_gr:cons_p encode_p :: true:0':false:s:y:cons_cond:cons_and:cons_even:cons_gr:cons_p -> true:0':false:s:y:cons_cond:cons_and:cons_even:cons_gr:cons_p encode_false :: true:0':false:s:y:cons_cond:cons_and:cons_even:cons_gr:cons_p encode_s :: true:0':false:s:y:cons_cond:cons_and:cons_even:cons_gr:cons_p -> true:0':false:s:y:cons_cond:cons_and:cons_even:cons_gr:cons_p encode_y :: true:0':false:s:y:cons_cond:cons_and:cons_even:cons_gr:cons_p hole_true:0':false:s:y:cons_cond:cons_and:cons_even:cons_gr:cons_p1_3 :: true:0':false:s:y:cons_cond:cons_and:cons_even:cons_gr:cons_p gen_true:0':false:s:y:cons_cond:cons_and:cons_even:cons_gr:cons_p2_3 :: Nat -> true:0':false:s:y:cons_cond:cons_and:cons_even:cons_gr:cons_p ---------------------------------------- (19) OrderProof (LOWER BOUND(ID)) Heuristically decided to analyse the following defined symbols: cond, even, gr, encArg They will be analysed ascendingly in the following order: even < cond gr < cond cond < encArg even < encArg gr < encArg ---------------------------------------- (20) Obligation: Innermost TRS: Rules: cond(true, x) -> cond(and(even(x), gr(x, 0')), p(x)) and(x, false) -> false and(false, x) -> false and(true, true) -> true even(0') -> true even(s(0')) -> false even(s(s(x))) -> even(x) gr(0', x) -> false gr(s(x), 0') -> true gr(s(x), s(y)) -> gr(x, y) p(0') -> 0' p(s(x)) -> x encArg(true) -> true encArg(0') -> 0' encArg(false) -> false encArg(s(x_1)) -> s(encArg(x_1)) encArg(y) -> y encArg(cons_cond(x_1, x_2)) -> cond(encArg(x_1), encArg(x_2)) encArg(cons_and(x_1, x_2)) -> and(encArg(x_1), encArg(x_2)) encArg(cons_even(x_1)) -> even(encArg(x_1)) encArg(cons_gr(x_1, x_2)) -> gr(encArg(x_1), encArg(x_2)) encArg(cons_p(x_1)) -> p(encArg(x_1)) encode_cond(x_1, x_2) -> cond(encArg(x_1), encArg(x_2)) encode_true -> true encode_and(x_1, x_2) -> and(encArg(x_1), encArg(x_2)) encode_even(x_1) -> even(encArg(x_1)) encode_gr(x_1, x_2) -> gr(encArg(x_1), encArg(x_2)) encode_0 -> 0' encode_p(x_1) -> p(encArg(x_1)) encode_false -> false encode_s(x_1) -> s(encArg(x_1)) encode_y -> y Types: cond :: true:0':false:s:y:cons_cond:cons_and:cons_even:cons_gr:cons_p -> true:0':false:s:y:cons_cond:cons_and:cons_even:cons_gr:cons_p -> true:0':false:s:y:cons_cond:cons_and:cons_even:cons_gr:cons_p true :: true:0':false:s:y:cons_cond:cons_and:cons_even:cons_gr:cons_p and :: true:0':false:s:y:cons_cond:cons_and:cons_even:cons_gr:cons_p -> true:0':false:s:y:cons_cond:cons_and:cons_even:cons_gr:cons_p -> true:0':false:s:y:cons_cond:cons_and:cons_even:cons_gr:cons_p even :: true:0':false:s:y:cons_cond:cons_and:cons_even:cons_gr:cons_p -> true:0':false:s:y:cons_cond:cons_and:cons_even:cons_gr:cons_p gr :: true:0':false:s:y:cons_cond:cons_and:cons_even:cons_gr:cons_p -> true:0':false:s:y:cons_cond:cons_and:cons_even:cons_gr:cons_p -> true:0':false:s:y:cons_cond:cons_and:cons_even:cons_gr:cons_p 0' :: true:0':false:s:y:cons_cond:cons_and:cons_even:cons_gr:cons_p p :: true:0':false:s:y:cons_cond:cons_and:cons_even:cons_gr:cons_p -> true:0':false:s:y:cons_cond:cons_and:cons_even:cons_gr:cons_p false :: true:0':false:s:y:cons_cond:cons_and:cons_even:cons_gr:cons_p s :: true:0':false:s:y:cons_cond:cons_and:cons_even:cons_gr:cons_p -> true:0':false:s:y:cons_cond:cons_and:cons_even:cons_gr:cons_p y :: true:0':false:s:y:cons_cond:cons_and:cons_even:cons_gr:cons_p encArg :: true:0':false:s:y:cons_cond:cons_and:cons_even:cons_gr:cons_p -> true:0':false:s:y:cons_cond:cons_and:cons_even:cons_gr:cons_p cons_cond :: true:0':false:s:y:cons_cond:cons_and:cons_even:cons_gr:cons_p -> true:0':false:s:y:cons_cond:cons_and:cons_even:cons_gr:cons_p -> true:0':false:s:y:cons_cond:cons_and:cons_even:cons_gr:cons_p cons_and :: true:0':false:s:y:cons_cond:cons_and:cons_even:cons_gr:cons_p -> true:0':false:s:y:cons_cond:cons_and:cons_even:cons_gr:cons_p -> true:0':false:s:y:cons_cond:cons_and:cons_even:cons_gr:cons_p cons_even :: true:0':false:s:y:cons_cond:cons_and:cons_even:cons_gr:cons_p -> true:0':false:s:y:cons_cond:cons_and:cons_even:cons_gr:cons_p cons_gr :: true:0':false:s:y:cons_cond:cons_and:cons_even:cons_gr:cons_p -> true:0':false:s:y:cons_cond:cons_and:cons_even:cons_gr:cons_p -> true:0':false:s:y:cons_cond:cons_and:cons_even:cons_gr:cons_p cons_p :: true:0':false:s:y:cons_cond:cons_and:cons_even:cons_gr:cons_p -> true:0':false:s:y:cons_cond:cons_and:cons_even:cons_gr:cons_p encode_cond :: true:0':false:s:y:cons_cond:cons_and:cons_even:cons_gr:cons_p -> true:0':false:s:y:cons_cond:cons_and:cons_even:cons_gr:cons_p -> true:0':false:s:y:cons_cond:cons_and:cons_even:cons_gr:cons_p encode_true :: true:0':false:s:y:cons_cond:cons_and:cons_even:cons_gr:cons_p encode_and :: true:0':false:s:y:cons_cond:cons_and:cons_even:cons_gr:cons_p -> true:0':false:s:y:cons_cond:cons_and:cons_even:cons_gr:cons_p -> true:0':false:s:y:cons_cond:cons_and:cons_even:cons_gr:cons_p encode_even :: true:0':false:s:y:cons_cond:cons_and:cons_even:cons_gr:cons_p -> true:0':false:s:y:cons_cond:cons_and:cons_even:cons_gr:cons_p encode_gr :: true:0':false:s:y:cons_cond:cons_and:cons_even:cons_gr:cons_p -> true:0':false:s:y:cons_cond:cons_and:cons_even:cons_gr:cons_p -> true:0':false:s:y:cons_cond:cons_and:cons_even:cons_gr:cons_p encode_0 :: true:0':false:s:y:cons_cond:cons_and:cons_even:cons_gr:cons_p encode_p :: true:0':false:s:y:cons_cond:cons_and:cons_even:cons_gr:cons_p -> true:0':false:s:y:cons_cond:cons_and:cons_even:cons_gr:cons_p encode_false :: true:0':false:s:y:cons_cond:cons_and:cons_even:cons_gr:cons_p encode_s :: true:0':false:s:y:cons_cond:cons_and:cons_even:cons_gr:cons_p -> true:0':false:s:y:cons_cond:cons_and:cons_even:cons_gr:cons_p encode_y :: true:0':false:s:y:cons_cond:cons_and:cons_even:cons_gr:cons_p hole_true:0':false:s:y:cons_cond:cons_and:cons_even:cons_gr:cons_p1_3 :: true:0':false:s:y:cons_cond:cons_and:cons_even:cons_gr:cons_p gen_true:0':false:s:y:cons_cond:cons_and:cons_even:cons_gr:cons_p2_3 :: Nat -> true:0':false:s:y:cons_cond:cons_and:cons_even:cons_gr:cons_p Generator Equations: gen_true:0':false:s:y:cons_cond:cons_and:cons_even:cons_gr:cons_p2_3(0) <=> true gen_true:0':false:s:y:cons_cond:cons_and:cons_even:cons_gr:cons_p2_3(+(x, 1)) <=> s(gen_true:0':false:s:y:cons_cond:cons_and:cons_even:cons_gr:cons_p2_3(x)) The following defined symbols remain to be analysed: even, cond, gr, encArg They will be analysed ascendingly in the following order: even < cond gr < cond cond < encArg even < encArg gr < encArg ---------------------------------------- (21) RewriteLemmaProof (LOWER BOUND(ID)) Proved the following rewrite lemma: even(gen_true:0':false:s:y:cons_cond:cons_and:cons_even:cons_gr:cons_p2_3(+(2, *(2, n4_3)))) -> *3_3, rt in Omega(n4_3) Induction Base: even(gen_true:0':false:s:y:cons_cond:cons_and:cons_even:cons_gr:cons_p2_3(+(2, *(2, 0)))) Induction Step: even(gen_true:0':false:s:y:cons_cond:cons_and:cons_even:cons_gr:cons_p2_3(+(2, *(2, +(n4_3, 1))))) ->_R^Omega(1) even(gen_true:0':false:s:y:cons_cond:cons_and:cons_even:cons_gr:cons_p2_3(+(2, *(2, n4_3)))) ->_IH *3_3 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: cond(true, x) -> cond(and(even(x), gr(x, 0')), p(x)) and(x, false) -> false and(false, x) -> false and(true, true) -> true even(0') -> true even(s(0')) -> false even(s(s(x))) -> even(x) gr(0', x) -> false gr(s(x), 0') -> true gr(s(x), s(y)) -> gr(x, y) p(0') -> 0' p(s(x)) -> x encArg(true) -> true encArg(0') -> 0' encArg(false) -> false encArg(s(x_1)) -> s(encArg(x_1)) encArg(y) -> y encArg(cons_cond(x_1, x_2)) -> cond(encArg(x_1), encArg(x_2)) encArg(cons_and(x_1, x_2)) -> and(encArg(x_1), encArg(x_2)) encArg(cons_even(x_1)) -> even(encArg(x_1)) encArg(cons_gr(x_1, x_2)) -> gr(encArg(x_1), encArg(x_2)) encArg(cons_p(x_1)) -> p(encArg(x_1)) encode_cond(x_1, x_2) -> cond(encArg(x_1), encArg(x_2)) encode_true -> true encode_and(x_1, x_2) -> and(encArg(x_1), encArg(x_2)) encode_even(x_1) -> even(encArg(x_1)) encode_gr(x_1, x_2) -> gr(encArg(x_1), encArg(x_2)) encode_0 -> 0' encode_p(x_1) -> p(encArg(x_1)) encode_false -> false encode_s(x_1) -> s(encArg(x_1)) encode_y -> y Types: cond :: true:0':false:s:y:cons_cond:cons_and:cons_even:cons_gr:cons_p -> true:0':false:s:y:cons_cond:cons_and:cons_even:cons_gr:cons_p -> true:0':false:s:y:cons_cond:cons_and:cons_even:cons_gr:cons_p true :: true:0':false:s:y:cons_cond:cons_and:cons_even:cons_gr:cons_p and :: true:0':false:s:y:cons_cond:cons_and:cons_even:cons_gr:cons_p -> true:0':false:s:y:cons_cond:cons_and:cons_even:cons_gr:cons_p -> true:0':false:s:y:cons_cond:cons_and:cons_even:cons_gr:cons_p even :: true:0':false:s:y:cons_cond:cons_and:cons_even:cons_gr:cons_p -> true:0':false:s:y:cons_cond:cons_and:cons_even:cons_gr:cons_p gr :: true:0':false:s:y:cons_cond:cons_and:cons_even:cons_gr:cons_p -> true:0':false:s:y:cons_cond:cons_and:cons_even:cons_gr:cons_p -> true:0':false:s:y:cons_cond:cons_and:cons_even:cons_gr:cons_p 0' :: true:0':false:s:y:cons_cond:cons_and:cons_even:cons_gr:cons_p p :: true:0':false:s:y:cons_cond:cons_and:cons_even:cons_gr:cons_p -> true:0':false:s:y:cons_cond:cons_and:cons_even:cons_gr:cons_p false :: true:0':false:s:y:cons_cond:cons_and:cons_even:cons_gr:cons_p s :: true:0':false:s:y:cons_cond:cons_and:cons_even:cons_gr:cons_p -> true:0':false:s:y:cons_cond:cons_and:cons_even:cons_gr:cons_p y :: true:0':false:s:y:cons_cond:cons_and:cons_even:cons_gr:cons_p encArg :: true:0':false:s:y:cons_cond:cons_and:cons_even:cons_gr:cons_p -> true:0':false:s:y:cons_cond:cons_and:cons_even:cons_gr:cons_p cons_cond :: true:0':false:s:y:cons_cond:cons_and:cons_even:cons_gr:cons_p -> true:0':false:s:y:cons_cond:cons_and:cons_even:cons_gr:cons_p -> true:0':false:s:y:cons_cond:cons_and:cons_even:cons_gr:cons_p cons_and :: true:0':false:s:y:cons_cond:cons_and:cons_even:cons_gr:cons_p -> true:0':false:s:y:cons_cond:cons_and:cons_even:cons_gr:cons_p -> true:0':false:s:y:cons_cond:cons_and:cons_even:cons_gr:cons_p cons_even :: true:0':false:s:y:cons_cond:cons_and:cons_even:cons_gr:cons_p -> true:0':false:s:y:cons_cond:cons_and:cons_even:cons_gr:cons_p cons_gr :: true:0':false:s:y:cons_cond:cons_and:cons_even:cons_gr:cons_p -> true:0':false:s:y:cons_cond:cons_and:cons_even:cons_gr:cons_p -> true:0':false:s:y:cons_cond:cons_and:cons_even:cons_gr:cons_p cons_p :: true:0':false:s:y:cons_cond:cons_and:cons_even:cons_gr:cons_p -> true:0':false:s:y:cons_cond:cons_and:cons_even:cons_gr:cons_p encode_cond :: true:0':false:s:y:cons_cond:cons_and:cons_even:cons_gr:cons_p -> true:0':false:s:y:cons_cond:cons_and:cons_even:cons_gr:cons_p -> true:0':false:s:y:cons_cond:cons_and:cons_even:cons_gr:cons_p encode_true :: true:0':false:s:y:cons_cond:cons_and:cons_even:cons_gr:cons_p encode_and :: true:0':false:s:y:cons_cond:cons_and:cons_even:cons_gr:cons_p -> true:0':false:s:y:cons_cond:cons_and:cons_even:cons_gr:cons_p -> true:0':false:s:y:cons_cond:cons_and:cons_even:cons_gr:cons_p encode_even :: true:0':false:s:y:cons_cond:cons_and:cons_even:cons_gr:cons_p -> true:0':false:s:y:cons_cond:cons_and:cons_even:cons_gr:cons_p encode_gr :: true:0':false:s:y:cons_cond:cons_and:cons_even:cons_gr:cons_p -> true:0':false:s:y:cons_cond:cons_and:cons_even:cons_gr:cons_p -> true:0':false:s:y:cons_cond:cons_and:cons_even:cons_gr:cons_p encode_0 :: true:0':false:s:y:cons_cond:cons_and:cons_even:cons_gr:cons_p encode_p :: true:0':false:s:y:cons_cond:cons_and:cons_even:cons_gr:cons_p -> true:0':false:s:y:cons_cond:cons_and:cons_even:cons_gr:cons_p encode_false :: true:0':false:s:y:cons_cond:cons_and:cons_even:cons_gr:cons_p encode_s :: true:0':false:s:y:cons_cond:cons_and:cons_even:cons_gr:cons_p -> true:0':false:s:y:cons_cond:cons_and:cons_even:cons_gr:cons_p encode_y :: true:0':false:s:y:cons_cond:cons_and:cons_even:cons_gr:cons_p hole_true:0':false:s:y:cons_cond:cons_and:cons_even:cons_gr:cons_p1_3 :: true:0':false:s:y:cons_cond:cons_and:cons_even:cons_gr:cons_p gen_true:0':false:s:y:cons_cond:cons_and:cons_even:cons_gr:cons_p2_3 :: Nat -> true:0':false:s:y:cons_cond:cons_and:cons_even:cons_gr:cons_p Generator Equations: gen_true:0':false:s:y:cons_cond:cons_and:cons_even:cons_gr:cons_p2_3(0) <=> true gen_true:0':false:s:y:cons_cond:cons_and:cons_even:cons_gr:cons_p2_3(+(x, 1)) <=> s(gen_true:0':false:s:y:cons_cond:cons_and:cons_even:cons_gr:cons_p2_3(x)) The following defined symbols remain to be analysed: even, cond, gr, encArg They will be analysed ascendingly in the following order: even < cond gr < cond cond < encArg even < encArg gr < encArg ---------------------------------------- (24) LowerBoundPropagationProof (FINISHED) Propagated lower bound. ---------------------------------------- (25) BOUNDS(n^1, INF) ---------------------------------------- (26) Obligation: Innermost TRS: Rules: cond(true, x) -> cond(and(even(x), gr(x, 0')), p(x)) and(x, false) -> false and(false, x) -> false and(true, true) -> true even(0') -> true even(s(0')) -> false even(s(s(x))) -> even(x) gr(0', x) -> false gr(s(x), 0') -> true gr(s(x), s(y)) -> gr(x, y) p(0') -> 0' p(s(x)) -> x encArg(true) -> true encArg(0') -> 0' encArg(false) -> false encArg(s(x_1)) -> s(encArg(x_1)) encArg(y) -> y encArg(cons_cond(x_1, x_2)) -> cond(encArg(x_1), encArg(x_2)) encArg(cons_and(x_1, x_2)) -> and(encArg(x_1), encArg(x_2)) encArg(cons_even(x_1)) -> even(encArg(x_1)) encArg(cons_gr(x_1, x_2)) -> gr(encArg(x_1), encArg(x_2)) encArg(cons_p(x_1)) -> p(encArg(x_1)) encode_cond(x_1, x_2) -> cond(encArg(x_1), encArg(x_2)) encode_true -> true encode_and(x_1, x_2) -> and(encArg(x_1), encArg(x_2)) encode_even(x_1) -> even(encArg(x_1)) encode_gr(x_1, x_2) -> gr(encArg(x_1), encArg(x_2)) encode_0 -> 0' encode_p(x_1) -> p(encArg(x_1)) encode_false -> false encode_s(x_1) -> s(encArg(x_1)) encode_y -> y Types: cond :: true:0':false:s:y:cons_cond:cons_and:cons_even:cons_gr:cons_p -> true:0':false:s:y:cons_cond:cons_and:cons_even:cons_gr:cons_p -> true:0':false:s:y:cons_cond:cons_and:cons_even:cons_gr:cons_p true :: true:0':false:s:y:cons_cond:cons_and:cons_even:cons_gr:cons_p and :: true:0':false:s:y:cons_cond:cons_and:cons_even:cons_gr:cons_p -> true:0':false:s:y:cons_cond:cons_and:cons_even:cons_gr:cons_p -> true:0':false:s:y:cons_cond:cons_and:cons_even:cons_gr:cons_p even :: true:0':false:s:y:cons_cond:cons_and:cons_even:cons_gr:cons_p -> true:0':false:s:y:cons_cond:cons_and:cons_even:cons_gr:cons_p gr :: true:0':false:s:y:cons_cond:cons_and:cons_even:cons_gr:cons_p -> true:0':false:s:y:cons_cond:cons_and:cons_even:cons_gr:cons_p -> true:0':false:s:y:cons_cond:cons_and:cons_even:cons_gr:cons_p 0' :: true:0':false:s:y:cons_cond:cons_and:cons_even:cons_gr:cons_p p :: true:0':false:s:y:cons_cond:cons_and:cons_even:cons_gr:cons_p -> true:0':false:s:y:cons_cond:cons_and:cons_even:cons_gr:cons_p false :: true:0':false:s:y:cons_cond:cons_and:cons_even:cons_gr:cons_p s :: true:0':false:s:y:cons_cond:cons_and:cons_even:cons_gr:cons_p -> true:0':false:s:y:cons_cond:cons_and:cons_even:cons_gr:cons_p y :: true:0':false:s:y:cons_cond:cons_and:cons_even:cons_gr:cons_p encArg :: true:0':false:s:y:cons_cond:cons_and:cons_even:cons_gr:cons_p -> true:0':false:s:y:cons_cond:cons_and:cons_even:cons_gr:cons_p cons_cond :: true:0':false:s:y:cons_cond:cons_and:cons_even:cons_gr:cons_p -> true:0':false:s:y:cons_cond:cons_and:cons_even:cons_gr:cons_p -> true:0':false:s:y:cons_cond:cons_and:cons_even:cons_gr:cons_p cons_and :: true:0':false:s:y:cons_cond:cons_and:cons_even:cons_gr:cons_p -> true:0':false:s:y:cons_cond:cons_and:cons_even:cons_gr:cons_p -> true:0':false:s:y:cons_cond:cons_and:cons_even:cons_gr:cons_p cons_even :: true:0':false:s:y:cons_cond:cons_and:cons_even:cons_gr:cons_p -> true:0':false:s:y:cons_cond:cons_and:cons_even:cons_gr:cons_p cons_gr :: true:0':false:s:y:cons_cond:cons_and:cons_even:cons_gr:cons_p -> true:0':false:s:y:cons_cond:cons_and:cons_even:cons_gr:cons_p -> true:0':false:s:y:cons_cond:cons_and:cons_even:cons_gr:cons_p cons_p :: true:0':false:s:y:cons_cond:cons_and:cons_even:cons_gr:cons_p -> true:0':false:s:y:cons_cond:cons_and:cons_even:cons_gr:cons_p encode_cond :: true:0':false:s:y:cons_cond:cons_and:cons_even:cons_gr:cons_p -> true:0':false:s:y:cons_cond:cons_and:cons_even:cons_gr:cons_p -> true:0':false:s:y:cons_cond:cons_and:cons_even:cons_gr:cons_p encode_true :: true:0':false:s:y:cons_cond:cons_and:cons_even:cons_gr:cons_p encode_and :: true:0':false:s:y:cons_cond:cons_and:cons_even:cons_gr:cons_p -> true:0':false:s:y:cons_cond:cons_and:cons_even:cons_gr:cons_p -> true:0':false:s:y:cons_cond:cons_and:cons_even:cons_gr:cons_p encode_even :: true:0':false:s:y:cons_cond:cons_and:cons_even:cons_gr:cons_p -> true:0':false:s:y:cons_cond:cons_and:cons_even:cons_gr:cons_p encode_gr :: true:0':false:s:y:cons_cond:cons_and:cons_even:cons_gr:cons_p -> true:0':false:s:y:cons_cond:cons_and:cons_even:cons_gr:cons_p -> true:0':false:s:y:cons_cond:cons_and:cons_even:cons_gr:cons_p encode_0 :: true:0':false:s:y:cons_cond:cons_and:cons_even:cons_gr:cons_p encode_p :: true:0':false:s:y:cons_cond:cons_and:cons_even:cons_gr:cons_p -> true:0':false:s:y:cons_cond:cons_and:cons_even:cons_gr:cons_p encode_false :: true:0':false:s:y:cons_cond:cons_and:cons_even:cons_gr:cons_p encode_s :: true:0':false:s:y:cons_cond:cons_and:cons_even:cons_gr:cons_p -> true:0':false:s:y:cons_cond:cons_and:cons_even:cons_gr:cons_p encode_y :: true:0':false:s:y:cons_cond:cons_and:cons_even:cons_gr:cons_p hole_true:0':false:s:y:cons_cond:cons_and:cons_even:cons_gr:cons_p1_3 :: true:0':false:s:y:cons_cond:cons_and:cons_even:cons_gr:cons_p gen_true:0':false:s:y:cons_cond:cons_and:cons_even:cons_gr:cons_p2_3 :: Nat -> true:0':false:s:y:cons_cond:cons_and:cons_even:cons_gr:cons_p Lemmas: even(gen_true:0':false:s:y:cons_cond:cons_and:cons_even:cons_gr:cons_p2_3(+(2, *(2, n4_3)))) -> *3_3, rt in Omega(n4_3) Generator Equations: gen_true:0':false:s:y:cons_cond:cons_and:cons_even:cons_gr:cons_p2_3(0) <=> true gen_true:0':false:s:y:cons_cond:cons_and:cons_even:cons_gr:cons_p2_3(+(x, 1)) <=> s(gen_true:0':false:s:y:cons_cond:cons_and:cons_even:cons_gr:cons_p2_3(x)) The following defined symbols remain to be analysed: gr, cond, encArg They will be analysed ascendingly in the following order: gr < cond cond < encArg gr < encArg ---------------------------------------- (27) RewriteLemmaProof (LOWER BOUND(ID)) Proved the following rewrite lemma: encArg(gen_true:0':false:s:y:cons_cond:cons_and:cons_even:cons_gr:cons_p2_3(n1352_3)) -> gen_true:0':false:s:y:cons_cond:cons_and:cons_even:cons_gr:cons_p2_3(n1352_3), rt in Omega(0) Induction Base: encArg(gen_true:0':false:s:y:cons_cond:cons_and:cons_even:cons_gr:cons_p2_3(0)) ->_R^Omega(0) true Induction Step: encArg(gen_true:0':false:s:y:cons_cond:cons_and:cons_even:cons_gr:cons_p2_3(+(n1352_3, 1))) ->_R^Omega(0) s(encArg(gen_true:0':false:s:y:cons_cond:cons_and:cons_even:cons_gr:cons_p2_3(n1352_3))) ->_IH s(gen_true:0':false:s:y:cons_cond:cons_and:cons_even:cons_gr:cons_p2_3(c1353_3)) We have rt in Omega(1) and sz in O(n). Thus, we have irc_R in Omega(n^0). ---------------------------------------- (28) BOUNDS(1, INF)