/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), 197 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), 3 ms] (10) CpxTypedWeightedCompleteTrs (11) CpxTypedWeightedTrsToRntsProof [UPPER BOUND(ID), 0 ms] (12) CpxRNTS (13) CompleteCoflocoProof [FINISHED, 6374 ms] (14) BOUNDS(1, n^3) (15) RenamingProof [BOTH BOUNDS(ID, ID), 0 ms] (16) CpxRelTRS (17) TypeInferenceProof [BOTH BOUNDS(ID, ID), 0 ms] (18) typed CpxTrs (19) OrderProof [LOWER BOUND(ID), 0 ms] (20) typed CpxTrs (21) RewriteLemmaProof [LOWER BOUND(ID), 295 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), 68 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: sub(0, 0) -> 0 sub(s(x), 0) -> s(x) sub(0, s(x)) -> 0 sub(s(x), s(y)) -> sub(x, y) zero(nil) -> zero2(0, nil) zero(cons(x, xs)) -> zero2(sub(x, x), cons(x, xs)) zero2(0, nil) -> nil zero2(0, cons(x, xs)) -> cons(sub(x, x), zero(xs)) zero2(s(y), nil) -> zero(nil) zero2(s(y), cons(x, xs)) -> zero(cons(x, xs)) 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(0) -> 0 encArg(s(x_1)) -> s(encArg(x_1)) encArg(nil) -> nil encArg(cons(x_1, x_2)) -> cons(encArg(x_1), encArg(x_2)) encArg(cons_sub(x_1, x_2)) -> sub(encArg(x_1), encArg(x_2)) encArg(cons_zero(x_1)) -> zero(encArg(x_1)) encArg(cons_zero2(x_1, x_2)) -> zero2(encArg(x_1), encArg(x_2)) encode_sub(x_1, x_2) -> sub(encArg(x_1), encArg(x_2)) encode_0 -> 0 encode_s(x_1) -> s(encArg(x_1)) encode_zero(x_1) -> zero(encArg(x_1)) encode_nil -> nil encode_zero2(x_1, x_2) -> zero2(encArg(x_1), encArg(x_2)) encode_cons(x_1, x_2) -> cons(encArg(x_1), encArg(x_2)) ---------------------------------------- (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: sub(0, 0) -> 0 sub(s(x), 0) -> s(x) sub(0, s(x)) -> 0 sub(s(x), s(y)) -> sub(x, y) zero(nil) -> zero2(0, nil) zero(cons(x, xs)) -> zero2(sub(x, x), cons(x, xs)) zero2(0, nil) -> nil zero2(0, cons(x, xs)) -> cons(sub(x, x), zero(xs)) zero2(s(y), nil) -> zero(nil) zero2(s(y), cons(x, xs)) -> zero(cons(x, xs)) The (relative) TRS S consists of the following rules: encArg(0) -> 0 encArg(s(x_1)) -> s(encArg(x_1)) encArg(nil) -> nil encArg(cons(x_1, x_2)) -> cons(encArg(x_1), encArg(x_2)) encArg(cons_sub(x_1, x_2)) -> sub(encArg(x_1), encArg(x_2)) encArg(cons_zero(x_1)) -> zero(encArg(x_1)) encArg(cons_zero2(x_1, x_2)) -> zero2(encArg(x_1), encArg(x_2)) encode_sub(x_1, x_2) -> sub(encArg(x_1), encArg(x_2)) encode_0 -> 0 encode_s(x_1) -> s(encArg(x_1)) encode_zero(x_1) -> zero(encArg(x_1)) encode_nil -> nil encode_zero2(x_1, x_2) -> zero2(encArg(x_1), encArg(x_2)) encode_cons(x_1, x_2) -> cons(encArg(x_1), encArg(x_2)) Rewrite Strategy: INNERMOST ---------------------------------------- (3) SInnermostTerminationProof (BOTH CONCRETE BOUNDS(ID, ID)) proved innermost termination of relative rules ---------------------------------------- (4) Obligation: The Runtime Complexity (innermost) of the given CpxRelTRS could be proven to be BOUNDS(n^1, n^3). The TRS R consists of the following rules: sub(0, 0) -> 0 sub(s(x), 0) -> s(x) sub(0, s(x)) -> 0 sub(s(x), s(y)) -> sub(x, y) zero(nil) -> zero2(0, nil) zero(cons(x, xs)) -> zero2(sub(x, x), cons(x, xs)) zero2(0, nil) -> nil zero2(0, cons(x, xs)) -> cons(sub(x, x), zero(xs)) zero2(s(y), nil) -> zero(nil) zero2(s(y), cons(x, xs)) -> zero(cons(x, xs)) The (relative) TRS S consists of the following rules: encArg(0) -> 0 encArg(s(x_1)) -> s(encArg(x_1)) encArg(nil) -> nil encArg(cons(x_1, x_2)) -> cons(encArg(x_1), encArg(x_2)) encArg(cons_sub(x_1, x_2)) -> sub(encArg(x_1), encArg(x_2)) encArg(cons_zero(x_1)) -> zero(encArg(x_1)) encArg(cons_zero2(x_1, x_2)) -> zero2(encArg(x_1), encArg(x_2)) encode_sub(x_1, x_2) -> sub(encArg(x_1), encArg(x_2)) encode_0 -> 0 encode_s(x_1) -> s(encArg(x_1)) encode_zero(x_1) -> zero(encArg(x_1)) encode_nil -> nil encode_zero2(x_1, x_2) -> zero2(encArg(x_1), encArg(x_2)) encode_cons(x_1, x_2) -> cons(encArg(x_1), encArg(x_2)) Rewrite Strategy: INNERMOST ---------------------------------------- (5) RelTrsToWeightedTrsProof (BOTH BOUNDS(ID, ID)) Transformed relative TRS to weighted TRS ---------------------------------------- (6) Obligation: The Runtime Complexity (innermost) of the given CpxWeightedTrs could be proven to be BOUNDS(1, n^3). The TRS R consists of the following rules: sub(0, 0) -> 0 [1] sub(s(x), 0) -> s(x) [1] sub(0, s(x)) -> 0 [1] sub(s(x), s(y)) -> sub(x, y) [1] zero(nil) -> zero2(0, nil) [1] zero(cons(x, xs)) -> zero2(sub(x, x), cons(x, xs)) [1] zero2(0, nil) -> nil [1] zero2(0, cons(x, xs)) -> cons(sub(x, x), zero(xs)) [1] zero2(s(y), nil) -> zero(nil) [1] zero2(s(y), cons(x, xs)) -> zero(cons(x, xs)) [1] encArg(0) -> 0 [0] encArg(s(x_1)) -> s(encArg(x_1)) [0] encArg(nil) -> nil [0] encArg(cons(x_1, x_2)) -> cons(encArg(x_1), encArg(x_2)) [0] encArg(cons_sub(x_1, x_2)) -> sub(encArg(x_1), encArg(x_2)) [0] encArg(cons_zero(x_1)) -> zero(encArg(x_1)) [0] encArg(cons_zero2(x_1, x_2)) -> zero2(encArg(x_1), encArg(x_2)) [0] encode_sub(x_1, x_2) -> sub(encArg(x_1), encArg(x_2)) [0] encode_0 -> 0 [0] encode_s(x_1) -> s(encArg(x_1)) [0] encode_zero(x_1) -> zero(encArg(x_1)) [0] encode_nil -> nil [0] encode_zero2(x_1, x_2) -> zero2(encArg(x_1), encArg(x_2)) [0] encode_cons(x_1, x_2) -> cons(encArg(x_1), encArg(x_2)) [0] Rewrite Strategy: INNERMOST ---------------------------------------- (7) TypeInferenceProof (BOTH BOUNDS(ID, ID)) Infered types. ---------------------------------------- (8) Obligation: Runtime Complexity Weighted TRS with Types. The TRS R consists of the following rules: sub(0, 0) -> 0 [1] sub(s(x), 0) -> s(x) [1] sub(0, s(x)) -> 0 [1] sub(s(x), s(y)) -> sub(x, y) [1] zero(nil) -> zero2(0, nil) [1] zero(cons(x, xs)) -> zero2(sub(x, x), cons(x, xs)) [1] zero2(0, nil) -> nil [1] zero2(0, cons(x, xs)) -> cons(sub(x, x), zero(xs)) [1] zero2(s(y), nil) -> zero(nil) [1] zero2(s(y), cons(x, xs)) -> zero(cons(x, xs)) [1] encArg(0) -> 0 [0] encArg(s(x_1)) -> s(encArg(x_1)) [0] encArg(nil) -> nil [0] encArg(cons(x_1, x_2)) -> cons(encArg(x_1), encArg(x_2)) [0] encArg(cons_sub(x_1, x_2)) -> sub(encArg(x_1), encArg(x_2)) [0] encArg(cons_zero(x_1)) -> zero(encArg(x_1)) [0] encArg(cons_zero2(x_1, x_2)) -> zero2(encArg(x_1), encArg(x_2)) [0] encode_sub(x_1, x_2) -> sub(encArg(x_1), encArg(x_2)) [0] encode_0 -> 0 [0] encode_s(x_1) -> s(encArg(x_1)) [0] encode_zero(x_1) -> zero(encArg(x_1)) [0] encode_nil -> nil [0] encode_zero2(x_1, x_2) -> zero2(encArg(x_1), encArg(x_2)) [0] encode_cons(x_1, x_2) -> cons(encArg(x_1), encArg(x_2)) [0] The TRS has the following type information: sub :: 0:s:nil:cons:cons_sub:cons_zero:cons_zero2 -> 0:s:nil:cons:cons_sub:cons_zero:cons_zero2 -> 0:s:nil:cons:cons_sub:cons_zero:cons_zero2 0 :: 0:s:nil:cons:cons_sub:cons_zero:cons_zero2 s :: 0:s:nil:cons:cons_sub:cons_zero:cons_zero2 -> 0:s:nil:cons:cons_sub:cons_zero:cons_zero2 zero :: 0:s:nil:cons:cons_sub:cons_zero:cons_zero2 -> 0:s:nil:cons:cons_sub:cons_zero:cons_zero2 nil :: 0:s:nil:cons:cons_sub:cons_zero:cons_zero2 zero2 :: 0:s:nil:cons:cons_sub:cons_zero:cons_zero2 -> 0:s:nil:cons:cons_sub:cons_zero:cons_zero2 -> 0:s:nil:cons:cons_sub:cons_zero:cons_zero2 cons :: 0:s:nil:cons:cons_sub:cons_zero:cons_zero2 -> 0:s:nil:cons:cons_sub:cons_zero:cons_zero2 -> 0:s:nil:cons:cons_sub:cons_zero:cons_zero2 encArg :: 0:s:nil:cons:cons_sub:cons_zero:cons_zero2 -> 0:s:nil:cons:cons_sub:cons_zero:cons_zero2 cons_sub :: 0:s:nil:cons:cons_sub:cons_zero:cons_zero2 -> 0:s:nil:cons:cons_sub:cons_zero:cons_zero2 -> 0:s:nil:cons:cons_sub:cons_zero:cons_zero2 cons_zero :: 0:s:nil:cons:cons_sub:cons_zero:cons_zero2 -> 0:s:nil:cons:cons_sub:cons_zero:cons_zero2 cons_zero2 :: 0:s:nil:cons:cons_sub:cons_zero:cons_zero2 -> 0:s:nil:cons:cons_sub:cons_zero:cons_zero2 -> 0:s:nil:cons:cons_sub:cons_zero:cons_zero2 encode_sub :: 0:s:nil:cons:cons_sub:cons_zero:cons_zero2 -> 0:s:nil:cons:cons_sub:cons_zero:cons_zero2 -> 0:s:nil:cons:cons_sub:cons_zero:cons_zero2 encode_0 :: 0:s:nil:cons:cons_sub:cons_zero:cons_zero2 encode_s :: 0:s:nil:cons:cons_sub:cons_zero:cons_zero2 -> 0:s:nil:cons:cons_sub:cons_zero:cons_zero2 encode_zero :: 0:s:nil:cons:cons_sub:cons_zero:cons_zero2 -> 0:s:nil:cons:cons_sub:cons_zero:cons_zero2 encode_nil :: 0:s:nil:cons:cons_sub:cons_zero:cons_zero2 encode_zero2 :: 0:s:nil:cons:cons_sub:cons_zero:cons_zero2 -> 0:s:nil:cons:cons_sub:cons_zero:cons_zero2 -> 0:s:nil:cons:cons_sub:cons_zero:cons_zero2 encode_cons :: 0:s:nil:cons:cons_sub:cons_zero:cons_zero2 -> 0:s:nil:cons:cons_sub:cons_zero:cons_zero2 -> 0:s:nil:cons:cons_sub:cons_zero:cons_zero2 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_sub(v0, v1) -> null_encode_sub [0] encode_0 -> null_encode_0 [0] encode_s(v0) -> null_encode_s [0] encode_zero(v0) -> null_encode_zero [0] encode_nil -> null_encode_nil [0] encode_zero2(v0, v1) -> null_encode_zero2 [0] encode_cons(v0, v1) -> null_encode_cons [0] sub(v0, v1) -> null_sub [0] zero(v0) -> null_zero [0] zero2(v0, v1) -> null_zero2 [0] And the following fresh constants: null_encArg, null_encode_sub, null_encode_0, null_encode_s, null_encode_zero, null_encode_nil, null_encode_zero2, null_encode_cons, null_sub, null_zero, null_zero2 ---------------------------------------- (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: sub(0, 0) -> 0 [1] sub(s(x), 0) -> s(x) [1] sub(0, s(x)) -> 0 [1] sub(s(x), s(y)) -> sub(x, y) [1] zero(nil) -> zero2(0, nil) [1] zero(cons(x, xs)) -> zero2(sub(x, x), cons(x, xs)) [1] zero2(0, nil) -> nil [1] zero2(0, cons(x, xs)) -> cons(sub(x, x), zero(xs)) [1] zero2(s(y), nil) -> zero(nil) [1] zero2(s(y), cons(x, xs)) -> zero(cons(x, xs)) [1] encArg(0) -> 0 [0] encArg(s(x_1)) -> s(encArg(x_1)) [0] encArg(nil) -> nil [0] encArg(cons(x_1, x_2)) -> cons(encArg(x_1), encArg(x_2)) [0] encArg(cons_sub(x_1, x_2)) -> sub(encArg(x_1), encArg(x_2)) [0] encArg(cons_zero(x_1)) -> zero(encArg(x_1)) [0] encArg(cons_zero2(x_1, x_2)) -> zero2(encArg(x_1), encArg(x_2)) [0] encode_sub(x_1, x_2) -> sub(encArg(x_1), encArg(x_2)) [0] encode_0 -> 0 [0] encode_s(x_1) -> s(encArg(x_1)) [0] encode_zero(x_1) -> zero(encArg(x_1)) [0] encode_nil -> nil [0] encode_zero2(x_1, x_2) -> zero2(encArg(x_1), encArg(x_2)) [0] encode_cons(x_1, x_2) -> cons(encArg(x_1), encArg(x_2)) [0] encArg(v0) -> null_encArg [0] encode_sub(v0, v1) -> null_encode_sub [0] encode_0 -> null_encode_0 [0] encode_s(v0) -> null_encode_s [0] encode_zero(v0) -> null_encode_zero [0] encode_nil -> null_encode_nil [0] encode_zero2(v0, v1) -> null_encode_zero2 [0] encode_cons(v0, v1) -> null_encode_cons [0] sub(v0, v1) -> null_sub [0] zero(v0) -> null_zero [0] zero2(v0, v1) -> null_zero2 [0] The TRS has the following type information: sub :: 0:s:nil:cons:cons_sub:cons_zero:cons_zero2:null_encArg:null_encode_sub:null_encode_0:null_encode_s:null_encode_zero:null_encode_nil:null_encode_zero2:null_encode_cons:null_sub:null_zero:null_zero2 -> 0:s:nil:cons:cons_sub:cons_zero:cons_zero2:null_encArg:null_encode_sub:null_encode_0:null_encode_s:null_encode_zero:null_encode_nil:null_encode_zero2:null_encode_cons:null_sub:null_zero:null_zero2 -> 0:s:nil:cons:cons_sub:cons_zero:cons_zero2:null_encArg:null_encode_sub:null_encode_0:null_encode_s:null_encode_zero:null_encode_nil:null_encode_zero2:null_encode_cons:null_sub:null_zero:null_zero2 0 :: 0:s:nil:cons:cons_sub:cons_zero:cons_zero2:null_encArg:null_encode_sub:null_encode_0:null_encode_s:null_encode_zero:null_encode_nil:null_encode_zero2:null_encode_cons:null_sub:null_zero:null_zero2 s :: 0:s:nil:cons:cons_sub:cons_zero:cons_zero2:null_encArg:null_encode_sub:null_encode_0:null_encode_s:null_encode_zero:null_encode_nil:null_encode_zero2:null_encode_cons:null_sub:null_zero:null_zero2 -> 0:s:nil:cons:cons_sub:cons_zero:cons_zero2:null_encArg:null_encode_sub:null_encode_0:null_encode_s:null_encode_zero:null_encode_nil:null_encode_zero2:null_encode_cons:null_sub:null_zero:null_zero2 zero :: 0:s:nil:cons:cons_sub:cons_zero:cons_zero2:null_encArg:null_encode_sub:null_encode_0:null_encode_s:null_encode_zero:null_encode_nil:null_encode_zero2:null_encode_cons:null_sub:null_zero:null_zero2 -> 0:s:nil:cons:cons_sub:cons_zero:cons_zero2:null_encArg:null_encode_sub:null_encode_0:null_encode_s:null_encode_zero:null_encode_nil:null_encode_zero2:null_encode_cons:null_sub:null_zero:null_zero2 nil :: 0:s:nil:cons:cons_sub:cons_zero:cons_zero2:null_encArg:null_encode_sub:null_encode_0:null_encode_s:null_encode_zero:null_encode_nil:null_encode_zero2:null_encode_cons:null_sub:null_zero:null_zero2 zero2 :: 0:s:nil:cons:cons_sub:cons_zero:cons_zero2:null_encArg:null_encode_sub:null_encode_0:null_encode_s:null_encode_zero:null_encode_nil:null_encode_zero2:null_encode_cons:null_sub:null_zero:null_zero2 -> 0:s:nil:cons:cons_sub:cons_zero:cons_zero2:null_encArg:null_encode_sub:null_encode_0:null_encode_s:null_encode_zero:null_encode_nil:null_encode_zero2:null_encode_cons:null_sub:null_zero:null_zero2 -> 0:s:nil:cons:cons_sub:cons_zero:cons_zero2:null_encArg:null_encode_sub:null_encode_0:null_encode_s:null_encode_zero:null_encode_nil:null_encode_zero2:null_encode_cons:null_sub:null_zero:null_zero2 cons :: 0:s:nil:cons:cons_sub:cons_zero:cons_zero2:null_encArg:null_encode_sub:null_encode_0:null_encode_s:null_encode_zero:null_encode_nil:null_encode_zero2:null_encode_cons:null_sub:null_zero:null_zero2 -> 0:s:nil:cons:cons_sub:cons_zero:cons_zero2:null_encArg:null_encode_sub:null_encode_0:null_encode_s:null_encode_zero:null_encode_nil:null_encode_zero2:null_encode_cons:null_sub:null_zero:null_zero2 -> 0:s:nil:cons:cons_sub:cons_zero:cons_zero2:null_encArg:null_encode_sub:null_encode_0:null_encode_s:null_encode_zero:null_encode_nil:null_encode_zero2:null_encode_cons:null_sub:null_zero:null_zero2 encArg :: 0:s:nil:cons:cons_sub:cons_zero:cons_zero2:null_encArg:null_encode_sub:null_encode_0:null_encode_s:null_encode_zero:null_encode_nil:null_encode_zero2:null_encode_cons:null_sub:null_zero:null_zero2 -> 0:s:nil:cons:cons_sub:cons_zero:cons_zero2:null_encArg:null_encode_sub:null_encode_0:null_encode_s:null_encode_zero:null_encode_nil:null_encode_zero2:null_encode_cons:null_sub:null_zero:null_zero2 cons_sub :: 0:s:nil:cons:cons_sub:cons_zero:cons_zero2:null_encArg:null_encode_sub:null_encode_0:null_encode_s:null_encode_zero:null_encode_nil:null_encode_zero2:null_encode_cons:null_sub:null_zero:null_zero2 -> 0:s:nil:cons:cons_sub:cons_zero:cons_zero2:null_encArg:null_encode_sub:null_encode_0:null_encode_s:null_encode_zero:null_encode_nil:null_encode_zero2:null_encode_cons:null_sub:null_zero:null_zero2 -> 0:s:nil:cons:cons_sub:cons_zero:cons_zero2:null_encArg:null_encode_sub:null_encode_0:null_encode_s:null_encode_zero:null_encode_nil:null_encode_zero2:null_encode_cons:null_sub:null_zero:null_zero2 cons_zero :: 0:s:nil:cons:cons_sub:cons_zero:cons_zero2:null_encArg:null_encode_sub:null_encode_0:null_encode_s:null_encode_zero:null_encode_nil:null_encode_zero2:null_encode_cons:null_sub:null_zero:null_zero2 -> 0:s:nil:cons:cons_sub:cons_zero:cons_zero2:null_encArg:null_encode_sub:null_encode_0:null_encode_s:null_encode_zero:null_encode_nil:null_encode_zero2:null_encode_cons:null_sub:null_zero:null_zero2 cons_zero2 :: 0:s:nil:cons:cons_sub:cons_zero:cons_zero2:null_encArg:null_encode_sub:null_encode_0:null_encode_s:null_encode_zero:null_encode_nil:null_encode_zero2:null_encode_cons:null_sub:null_zero:null_zero2 -> 0:s:nil:cons:cons_sub:cons_zero:cons_zero2:null_encArg:null_encode_sub:null_encode_0:null_encode_s:null_encode_zero:null_encode_nil:null_encode_zero2:null_encode_cons:null_sub:null_zero:null_zero2 -> 0:s:nil:cons:cons_sub:cons_zero:cons_zero2:null_encArg:null_encode_sub:null_encode_0:null_encode_s:null_encode_zero:null_encode_nil:null_encode_zero2:null_encode_cons:null_sub:null_zero:null_zero2 encode_sub :: 0:s:nil:cons:cons_sub:cons_zero:cons_zero2:null_encArg:null_encode_sub:null_encode_0:null_encode_s:null_encode_zero:null_encode_nil:null_encode_zero2:null_encode_cons:null_sub:null_zero:null_zero2 -> 0:s:nil:cons:cons_sub:cons_zero:cons_zero2:null_encArg:null_encode_sub:null_encode_0:null_encode_s:null_encode_zero:null_encode_nil:null_encode_zero2:null_encode_cons:null_sub:null_zero:null_zero2 -> 0:s:nil:cons:cons_sub:cons_zero:cons_zero2:null_encArg:null_encode_sub:null_encode_0:null_encode_s:null_encode_zero:null_encode_nil:null_encode_zero2:null_encode_cons:null_sub:null_zero:null_zero2 encode_0 :: 0:s:nil:cons:cons_sub:cons_zero:cons_zero2:null_encArg:null_encode_sub:null_encode_0:null_encode_s:null_encode_zero:null_encode_nil:null_encode_zero2:null_encode_cons:null_sub:null_zero:null_zero2 encode_s :: 0:s:nil:cons:cons_sub:cons_zero:cons_zero2:null_encArg:null_encode_sub:null_encode_0:null_encode_s:null_encode_zero:null_encode_nil:null_encode_zero2:null_encode_cons:null_sub:null_zero:null_zero2 -> 0:s:nil:cons:cons_sub:cons_zero:cons_zero2:null_encArg:null_encode_sub:null_encode_0:null_encode_s:null_encode_zero:null_encode_nil:null_encode_zero2:null_encode_cons:null_sub:null_zero:null_zero2 encode_zero :: 0:s:nil:cons:cons_sub:cons_zero:cons_zero2:null_encArg:null_encode_sub:null_encode_0:null_encode_s:null_encode_zero:null_encode_nil:null_encode_zero2:null_encode_cons:null_sub:null_zero:null_zero2 -> 0:s:nil:cons:cons_sub:cons_zero:cons_zero2:null_encArg:null_encode_sub:null_encode_0:null_encode_s:null_encode_zero:null_encode_nil:null_encode_zero2:null_encode_cons:null_sub:null_zero:null_zero2 encode_nil :: 0:s:nil:cons:cons_sub:cons_zero:cons_zero2:null_encArg:null_encode_sub:null_encode_0:null_encode_s:null_encode_zero:null_encode_nil:null_encode_zero2:null_encode_cons:null_sub:null_zero:null_zero2 encode_zero2 :: 0:s:nil:cons:cons_sub:cons_zero:cons_zero2:null_encArg:null_encode_sub:null_encode_0:null_encode_s:null_encode_zero:null_encode_nil:null_encode_zero2:null_encode_cons:null_sub:null_zero:null_zero2 -> 0:s:nil:cons:cons_sub:cons_zero:cons_zero2:null_encArg:null_encode_sub:null_encode_0:null_encode_s:null_encode_zero:null_encode_nil:null_encode_zero2:null_encode_cons:null_sub:null_zero:null_zero2 -> 0:s:nil:cons:cons_sub:cons_zero:cons_zero2:null_encArg:null_encode_sub:null_encode_0:null_encode_s:null_encode_zero:null_encode_nil:null_encode_zero2:null_encode_cons:null_sub:null_zero:null_zero2 encode_cons :: 0:s:nil:cons:cons_sub:cons_zero:cons_zero2:null_encArg:null_encode_sub:null_encode_0:null_encode_s:null_encode_zero:null_encode_nil:null_encode_zero2:null_encode_cons:null_sub:null_zero:null_zero2 -> 0:s:nil:cons:cons_sub:cons_zero:cons_zero2:null_encArg:null_encode_sub:null_encode_0:null_encode_s:null_encode_zero:null_encode_nil:null_encode_zero2:null_encode_cons:null_sub:null_zero:null_zero2 -> 0:s:nil:cons:cons_sub:cons_zero:cons_zero2:null_encArg:null_encode_sub:null_encode_0:null_encode_s:null_encode_zero:null_encode_nil:null_encode_zero2:null_encode_cons:null_sub:null_zero:null_zero2 null_encArg :: 0:s:nil:cons:cons_sub:cons_zero:cons_zero2:null_encArg:null_encode_sub:null_encode_0:null_encode_s:null_encode_zero:null_encode_nil:null_encode_zero2:null_encode_cons:null_sub:null_zero:null_zero2 null_encode_sub :: 0:s:nil:cons:cons_sub:cons_zero:cons_zero2:null_encArg:null_encode_sub:null_encode_0:null_encode_s:null_encode_zero:null_encode_nil:null_encode_zero2:null_encode_cons:null_sub:null_zero:null_zero2 null_encode_0 :: 0:s:nil:cons:cons_sub:cons_zero:cons_zero2:null_encArg:null_encode_sub:null_encode_0:null_encode_s:null_encode_zero:null_encode_nil:null_encode_zero2:null_encode_cons:null_sub:null_zero:null_zero2 null_encode_s :: 0:s:nil:cons:cons_sub:cons_zero:cons_zero2:null_encArg:null_encode_sub:null_encode_0:null_encode_s:null_encode_zero:null_encode_nil:null_encode_zero2:null_encode_cons:null_sub:null_zero:null_zero2 null_encode_zero :: 0:s:nil:cons:cons_sub:cons_zero:cons_zero2:null_encArg:null_encode_sub:null_encode_0:null_encode_s:null_encode_zero:null_encode_nil:null_encode_zero2:null_encode_cons:null_sub:null_zero:null_zero2 null_encode_nil :: 0:s:nil:cons:cons_sub:cons_zero:cons_zero2:null_encArg:null_encode_sub:null_encode_0:null_encode_s:null_encode_zero:null_encode_nil:null_encode_zero2:null_encode_cons:null_sub:null_zero:null_zero2 null_encode_zero2 :: 0:s:nil:cons:cons_sub:cons_zero:cons_zero2:null_encArg:null_encode_sub:null_encode_0:null_encode_s:null_encode_zero:null_encode_nil:null_encode_zero2:null_encode_cons:null_sub:null_zero:null_zero2 null_encode_cons :: 0:s:nil:cons:cons_sub:cons_zero:cons_zero2:null_encArg:null_encode_sub:null_encode_0:null_encode_s:null_encode_zero:null_encode_nil:null_encode_zero2:null_encode_cons:null_sub:null_zero:null_zero2 null_sub :: 0:s:nil:cons:cons_sub:cons_zero:cons_zero2:null_encArg:null_encode_sub:null_encode_0:null_encode_s:null_encode_zero:null_encode_nil:null_encode_zero2:null_encode_cons:null_sub:null_zero:null_zero2 null_zero :: 0:s:nil:cons:cons_sub:cons_zero:cons_zero2:null_encArg:null_encode_sub:null_encode_0:null_encode_s:null_encode_zero:null_encode_nil:null_encode_zero2:null_encode_cons:null_sub:null_zero:null_zero2 null_zero2 :: 0:s:nil:cons:cons_sub:cons_zero:cons_zero2:null_encArg:null_encode_sub:null_encode_0:null_encode_s:null_encode_zero:null_encode_nil:null_encode_zero2:null_encode_cons:null_sub:null_zero:null_zero2 Rewrite Strategy: INNERMOST ---------------------------------------- (11) CpxTypedWeightedTrsToRntsProof (UPPER BOUND(ID)) Transformed the TRS into an over-approximating RNTS by (improved) Size Abstraction. The constant constructors are abstracted as follows: 0 => 0 nil => 1 null_encArg => 0 null_encode_sub => 0 null_encode_0 => 0 null_encode_s => 0 null_encode_zero => 0 null_encode_nil => 0 null_encode_zero2 => 0 null_encode_cons => 0 null_sub => 0 null_zero => 0 null_zero2 => 0 ---------------------------------------- (12) Obligation: Complexity RNTS consisting of the following rules: encArg(z) -{ 0 }-> zero2(encArg(x_1), encArg(x_2)) :|: x_1 >= 0, z = 1 + x_1 + x_2, x_2 >= 0 encArg(z) -{ 0 }-> zero(encArg(x_1)) :|: z = 1 + x_1, x_1 >= 0 encArg(z) -{ 0 }-> sub(encArg(x_1), encArg(x_2)) :|: x_1 >= 0, z = 1 + x_1 + x_2, x_2 >= 0 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 encArg(z) -{ 0 }-> 1 + encArg(x_1) + encArg(x_2) :|: x_1 >= 0, z = 1 + x_1 + x_2, x_2 >= 0 encode_0 -{ 0 }-> 0 :|: encode_cons(z, z') -{ 0 }-> 0 :|: v0 >= 0, v1 >= 0, z = v0, z' = v1 encode_cons(z, z') -{ 0 }-> 1 + encArg(x_1) + encArg(x_2) :|: x_1 >= 0, x_2 >= 0, z = x_1, z' = x_2 encode_nil -{ 0 }-> 1 :|: encode_nil -{ 0 }-> 0 :|: encode_s(z) -{ 0 }-> 0 :|: v0 >= 0, z = v0 encode_s(z) -{ 0 }-> 1 + encArg(x_1) :|: x_1 >= 0, z = x_1 encode_sub(z, z') -{ 0 }-> sub(encArg(x_1), encArg(x_2)) :|: x_1 >= 0, x_2 >= 0, z = x_1, z' = x_2 encode_sub(z, z') -{ 0 }-> 0 :|: v0 >= 0, v1 >= 0, z = v0, z' = v1 encode_zero(z) -{ 0 }-> zero(encArg(x_1)) :|: x_1 >= 0, z = x_1 encode_zero(z) -{ 0 }-> 0 :|: v0 >= 0, z = v0 encode_zero2(z, z') -{ 0 }-> zero2(encArg(x_1), encArg(x_2)) :|: x_1 >= 0, x_2 >= 0, z = x_1, z' = x_2 encode_zero2(z, z') -{ 0 }-> 0 :|: v0 >= 0, v1 >= 0, z = v0, z' = v1 sub(z, z') -{ 1 }-> sub(x, y) :|: z' = 1 + y, x >= 0, y >= 0, z = 1 + x sub(z, z') -{ 1 }-> 0 :|: z = 0, z' = 0 sub(z, z') -{ 1 }-> 0 :|: z' = 1 + x, x >= 0, z = 0 sub(z, z') -{ 0 }-> 0 :|: v0 >= 0, v1 >= 0, z = v0, z' = v1 sub(z, z') -{ 1 }-> 1 + x :|: x >= 0, z = 1 + x, z' = 0 zero(z) -{ 1 }-> zero2(sub(x, x), 1 + x + xs) :|: z = 1 + x + xs, xs >= 0, x >= 0 zero(z) -{ 1 }-> zero2(0, 1) :|: z = 1 zero(z) -{ 0 }-> 0 :|: v0 >= 0, z = v0 zero2(z, z') -{ 1 }-> zero(1) :|: y >= 0, z' = 1, z = 1 + y zero2(z, z') -{ 1 }-> zero(1 + x + xs) :|: xs >= 0, z' = 1 + x + xs, y >= 0, x >= 0, z = 1 + y zero2(z, z') -{ 1 }-> 1 :|: z' = 1, z = 0 zero2(z, z') -{ 0 }-> 0 :|: v0 >= 0, v1 >= 0, z = v0, z' = v1 zero2(z, z') -{ 1 }-> 1 + sub(x, x) + zero(xs) :|: xs >= 0, z' = 1 + x + xs, x >= 0, z = 0 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,[sub(V1, V, Out)],[V1 >= 0,V >= 0]). eq(start(V1, V),0,[zero(V1, Out)],[V1 >= 0]). eq(start(V1, V),0,[zero2(V1, V, Out)],[V1 >= 0,V >= 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, Out)],[V1 >= 0]). eq(start(V1, V),0,[fun3(V1, Out)],[V1 >= 0]). eq(start(V1, V),0,[fun4(Out)],[]). eq(start(V1, V),0,[fun5(V1, V, Out)],[V1 >= 0,V >= 0]). eq(start(V1, V),0,[fun6(V1, V, Out)],[V1 >= 0,V >= 0]). eq(sub(V1, V, Out),1,[],[Out = 0,V1 = 0,V = 0]). eq(sub(V1, V, Out),1,[],[Out = 1 + V2,V2 >= 0,V1 = 1 + V2,V = 0]). eq(sub(V1, V, Out),1,[],[Out = 0,V = 1 + V3,V3 >= 0,V1 = 0]). eq(sub(V1, V, Out),1,[sub(V4, V5, Ret)],[Out = Ret,V = 1 + V5,V4 >= 0,V5 >= 0,V1 = 1 + V4]). eq(zero(V1, Out),1,[zero2(0, 1, Ret1)],[Out = Ret1,V1 = 1]). eq(zero(V1, Out),1,[sub(V6, V6, Ret0),zero2(Ret0, 1 + V6 + V7, Ret2)],[Out = Ret2,V1 = 1 + V6 + V7,V7 >= 0,V6 >= 0]). eq(zero2(V1, V, Out),1,[],[Out = 1,V = 1,V1 = 0]). eq(zero2(V1, V, Out),1,[sub(V8, V8, Ret01),zero(V9, Ret11)],[Out = 1 + Ret01 + Ret11,V9 >= 0,V = 1 + V8 + V9,V8 >= 0,V1 = 0]). eq(zero2(V1, V, Out),1,[zero(1, Ret3)],[Out = Ret3,V10 >= 0,V = 1,V1 = 1 + V10]). eq(zero2(V1, V, Out),1,[zero(1 + V12 + V13, Ret4)],[Out = Ret4,V13 >= 0,V = 1 + V12 + V13,V11 >= 0,V12 >= 0,V1 = 1 + V11]). eq(encArg(V1, Out),0,[],[Out = 0,V1 = 0]). eq(encArg(V1, Out),0,[encArg(V14, Ret12)],[Out = 1 + Ret12,V1 = 1 + V14,V14 >= 0]). eq(encArg(V1, Out),0,[],[Out = 1,V1 = 1]). eq(encArg(V1, Out),0,[encArg(V15, Ret011),encArg(V16, Ret13)],[Out = 1 + Ret011 + Ret13,V15 >= 0,V1 = 1 + V15 + V16,V16 >= 0]). eq(encArg(V1, Out),0,[encArg(V17, Ret02),encArg(V18, Ret14),sub(Ret02, Ret14, Ret5)],[Out = Ret5,V17 >= 0,V1 = 1 + V17 + V18,V18 >= 0]). eq(encArg(V1, Out),0,[encArg(V19, Ret03),zero(Ret03, Ret6)],[Out = Ret6,V1 = 1 + V19,V19 >= 0]). eq(encArg(V1, Out),0,[encArg(V21, Ret04),encArg(V20, Ret15),zero2(Ret04, Ret15, Ret7)],[Out = Ret7,V21 >= 0,V1 = 1 + V20 + V21,V20 >= 0]). eq(fun(V1, V, Out),0,[encArg(V23, Ret05),encArg(V22, Ret16),sub(Ret05, Ret16, Ret8)],[Out = Ret8,V23 >= 0,V22 >= 0,V1 = V23,V = V22]). eq(fun1(Out),0,[],[Out = 0]). eq(fun2(V1, Out),0,[encArg(V24, Ret17)],[Out = 1 + Ret17,V24 >= 0,V1 = V24]). eq(fun3(V1, Out),0,[encArg(V25, Ret06),zero(Ret06, Ret9)],[Out = Ret9,V25 >= 0,V1 = V25]). eq(fun4(Out),0,[],[Out = 1]). eq(fun5(V1, V, Out),0,[encArg(V27, Ret07),encArg(V26, Ret18),zero2(Ret07, Ret18, Ret10)],[Out = Ret10,V27 >= 0,V26 >= 0,V1 = V27,V = V26]). eq(fun6(V1, V, Out),0,[encArg(V28, Ret012),encArg(V29, Ret19)],[Out = 1 + Ret012 + Ret19,V28 >= 0,V29 >= 0,V1 = V28,V = V29]). eq(encArg(V1, Out),0,[],[Out = 0,V30 >= 0,V1 = V30]). eq(fun(V1, V, Out),0,[],[Out = 0,V32 >= 0,V31 >= 0,V1 = V32,V = V31]). eq(fun2(V1, Out),0,[],[Out = 0,V33 >= 0,V1 = V33]). eq(fun3(V1, Out),0,[],[Out = 0,V34 >= 0,V1 = V34]). eq(fun4(Out),0,[],[Out = 0]). eq(fun5(V1, V, Out),0,[],[Out = 0,V35 >= 0,V36 >= 0,V1 = V35,V = V36]). eq(fun6(V1, V, Out),0,[],[Out = 0,V37 >= 0,V38 >= 0,V1 = V37,V = V38]). eq(sub(V1, V, Out),0,[],[Out = 0,V39 >= 0,V40 >= 0,V1 = V39,V = V40]). eq(zero(V1, Out),0,[],[Out = 0,V41 >= 0,V1 = V41]). eq(zero2(V1, V, Out),0,[],[Out = 0,V42 >= 0,V43 >= 0,V1 = V42,V = V43]). input_output_vars(sub(V1,V,Out),[V1,V],[Out]). input_output_vars(zero(V1,Out),[V1],[Out]). input_output_vars(zero2(V1,V,Out),[V1,V],[Out]). input_output_vars(encArg(V1,Out),[V1],[Out]). input_output_vars(fun(V1,V,Out),[V1,V],[Out]). input_output_vars(fun1(Out),[],[Out]). input_output_vars(fun2(V1,Out),[V1],[Out]). input_output_vars(fun3(V1,Out),[V1],[Out]). input_output_vars(fun4(Out),[],[Out]). input_output_vars(fun5(V1,V,Out),[V1,V],[Out]). input_output_vars(fun6(V1,V,Out),[V1,V],[Out]). CoFloCo proof output: Preprocessing Cost Relations ===================================== #### Computed strongly connected components 0. recursive : [sub/3] 1. recursive : [zero/2,zero2/3] 2. recursive [non_tail,multiple] : [encArg/2] 3. non_recursive : [fun/3] 4. non_recursive : [fun1/1] 5. non_recursive : [fun2/2] 6. non_recursive : [fun3/2] 7. non_recursive : [fun4/1] 8. non_recursive : [fun5/3] 9. non_recursive : [fun6/3] 10. non_recursive : [start/2] #### Obtained direct recursion through partial evaluation 0. SCC is partially evaluated into sub/3 1. SCC is partially evaluated into zero/2 2. SCC is partially evaluated into encArg/2 3. SCC is partially evaluated into fun/3 4. SCC is completely evaluated into other SCCs 5. SCC is partially evaluated into fun2/2 6. SCC is partially evaluated into fun3/2 7. SCC is partially evaluated into fun4/1 8. SCC is partially evaluated into fun5/3 9. SCC is partially evaluated into fun6/3 10. SCC is partially evaluated into start/2 Control-Flow Refinement of Cost Relations ===================================== ### Specialization of cost equations sub/3 * CE 23 is refined into CE [52] * CE 24 is refined into CE [53] * CE 22 is refined into CE [54] * CE 26 is refined into CE [55] * CE 25 is refined into CE [56] ### Cost equations --> "Loop" of sub/3 * CEs [56] --> Loop 25 * CEs [52] --> Loop 26 * CEs [53] --> Loop 27 * CEs [54,55] --> Loop 28 ### Ranking functions of CR sub(V1,V,Out) * RF of phase [25]: [V,V1] #### Partial ranking functions of CR sub(V1,V,Out) * Partial RF of phase [25]: - RF of loop [25:1]: V V1 ### Specialization of cost equations zero/2 * CE 19 is refined into CE [57] * CE 20 is refined into CE [58] * CE 14 is refined into CE [59] * CE 15 is refined into CE [60] * CE 21 is refined into CE [61] * CE 16 is discarded (unfeasible) * CE 17 is refined into CE [62] * CE 18 is refined into CE [63] ### Cost equations --> "Loop" of zero/2 * CEs [62,63] --> Loop 29 * CEs [57,58] --> Loop 30 * CEs [59,60,61] --> Loop 31 ### Ranking functions of CR zero(V1,Out) * RF of phase [29]: [V1] #### Partial ranking functions of CR zero(V1,Out) * Partial RF of phase [29]: - RF of loop [29:1]: V1 ### Specialization of cost equations encArg/2 * CE 31 is refined into CE [64] * CE 33 is refined into CE [65] * CE 32 is refined into CE [66] * CE 36 is refined into CE [67,68] * CE 28 is refined into CE [69,70] * CE 34 is refined into CE [71] * CE 29 is refined into CE [72,73] * CE 30 is refined into CE [74] * CE 27 is refined into CE [75] * CE 35 is refined into CE [76,77,78] ### Cost equations --> "Loop" of encArg/2 * CEs [69] --> Loop 32 * CEs [78] --> Loop 33 * CEs [71] --> Loop 34 * CEs [77] --> Loop 35 * CEs [72] --> Loop 36 * CEs [73,74] --> Loop 37 * CEs [70,75,76] --> Loop 38 * CEs [67] --> Loop 39 * CEs [66] --> Loop 40 * CEs [68] --> Loop 41 * CEs [64] --> Loop 42 * CEs [65] --> Loop 43 ### Ranking functions of CR encArg(V1,Out) * RF of phase [32,33,34,35,36,37,38,39,40,41]: [V1] #### Partial ranking functions of CR encArg(V1,Out) * Partial RF of phase [32,33,34,35,36,37,38,39,40,41]: - RF of loop [32:1,32:2,33:1,33:2,34:1,34:2,35:1,35:2,36:1,36:2,37:1,37:2,38:1,38:2,39:1,40:1,41:1]: V1 ### Specialization of cost equations fun/3 * CE 37 is refined into CE [79,80,81,82,83,84,85] * CE 38 is refined into CE [86] ### Cost equations --> "Loop" of fun/3 * CEs [80,81,83] --> Loop 44 * CEs [79,82,84,85,86] --> Loop 45 ### Ranking functions of CR fun(V1,V,Out) #### Partial ranking functions of CR fun(V1,V,Out) ### Specialization of cost equations fun2/2 * CE 39 is refined into CE [87,88] * CE 40 is refined into CE [89] ### Cost equations --> "Loop" of fun2/2 * CEs [87] --> Loop 46 * CEs [88] --> Loop 47 * CEs [89] --> Loop 48 ### Ranking functions of CR fun2(V1,Out) #### Partial ranking functions of CR fun2(V1,Out) ### Specialization of cost equations fun3/2 * CE 41 is refined into CE [90,91,92] * CE 42 is refined into CE [93] ### Cost equations --> "Loop" of fun3/2 * CEs [90] --> Loop 49 * CEs [91,92,93] --> Loop 50 ### Ranking functions of CR fun3(V1,Out) #### Partial ranking functions of CR fun3(V1,Out) ### Specialization of cost equations fun4/1 * CE 43 is refined into CE [94] * CE 44 is refined into CE [95] ### Cost equations --> "Loop" of fun4/1 * CEs [94] --> Loop 51 * CEs [95] --> Loop 52 ### Ranking functions of CR fun4(Out) #### Partial ranking functions of CR fun4(Out) ### Specialization of cost equations fun5/3 * CE 48 is refined into CE [96,97] * CE 45 is refined into CE [98,99,100,101] * CE 46 is refined into CE [102,103] * CE 47 is refined into CE [104,105,106,107] * CE 49 is refined into CE [108] ### Cost equations --> "Loop" of fun5/3 * CEs [102] --> Loop 53 * CEs [104,106] --> Loop 54 * CEs [96,97,105,107] --> Loop 55 * CEs [98,99,100,101,103,108] --> Loop 56 ### Ranking functions of CR fun5(V1,V,Out) #### Partial ranking functions of CR fun5(V1,V,Out) ### Specialization of cost equations fun6/3 * CE 50 is refined into CE [109,110,111,112] * CE 51 is refined into CE [113] ### Cost equations --> "Loop" of fun6/3 * CEs [109] --> Loop 57 * CEs [110] --> Loop 58 * CEs [111] --> Loop 59 * CEs [112] --> Loop 60 * CEs [113] --> Loop 61 ### Ranking functions of CR fun6(V1,V,Out) #### Partial ranking functions of CR fun6(V1,V,Out) ### Specialization of cost equations start/2 * CE 1 is refined into CE [114] * CE 2 is refined into CE [115,116] * CE 3 is refined into CE [117,118] * CE 4 is refined into CE [119] * CE 5 is refined into CE [120,121,122] * CE 6 is refined into CE [123,124] * CE 7 is refined into CE [125,126] * CE 8 is refined into CE [127,128] * CE 9 is refined into CE [129,130,131] * CE 10 is refined into CE [132,133] * CE 11 is refined into CE [134,135] * CE 12 is refined into CE [136,137,138,139] * CE 13 is refined into CE [140,141,142,143,144] ### Cost equations --> "Loop" of start/2 * CEs [114,115,116,117,118,119,120,121,122,123,124,125,126,127,128,129,130,131,132,133,134,135,136,137,138,139,140,141,142,143,144] --> Loop 62 ### Ranking functions of CR start(V1,V) #### Partial ranking functions of CR start(V1,V) Computing Bounds ===================================== #### Cost of chains of sub(V1,V,Out): * Chain [[25],28]: 1*it(25)+1 Such that:it(25) =< V with precondition: [Out=0,V1>=1,V>=1] * Chain [[25],27]: 1*it(25)+1 Such that:it(25) =< V1 with precondition: [Out=0,V1>=1,V>=V1+1] * Chain [[25],26]: 1*it(25)+1 Such that:it(25) =< V with precondition: [V1=Out+V,V>=1,V1>=V+1] * Chain [28]: 1 with precondition: [Out=0,V1>=0,V>=0] * Chain [27]: 1 with precondition: [V1=0,Out=0,V>=1] * Chain [26]: 1 with precondition: [V=0,V1=Out,V1>=1] #### Cost of chains of zero(V1,Out): * Chain [[29],31]: 8*it(29)+2*s(15)+2 Such that:aux(8) =< V1 it(29) =< aux(8) s(18) =< it(29)*aux(8) s(15) =< s(18) with precondition: [Out>=1,V1>=Out] * Chain [[29],30]: 6*it(29)+2*s(15)+3 Such that:aux(10) =< V1 it(29) =< aux(10) s(18) =< it(29)*aux(10) s(15) =< s(18) with precondition: [Out>=2,V1>=Out] * Chain [31]: 2*s(3)+2 Such that:aux(1) =< V1 s(3) =< aux(1) with precondition: [Out=0,V1>=0] * Chain [30]: 3 with precondition: [V1=1,Out=1] #### Cost of chains of encArg(V1,Out): * Chain [43]: 0 with precondition: [V1=1,Out=1] * Chain [42]: 0 with precondition: [Out=0,V1>=0] * Chain [multiple([32,33,34,35,36,37,38,39,40,41],[[43],[42]])]: 4*it(32)+1*it(33)+5*it(35)+5*it(36)+3*it(38)+5*it(39)+14*s(75)+4*s(76)+1*s(79)+16*s(80)+4*s(81)+4*s(84)+2*s(86)+1*s(87)+1*s(88)+14*s(90)+4*s(91)+2*s(94)+0 Such that:it([43]) =< V1/2+1/2 aux(28) =< V1 aux(29) =< V1+1 aux(30) =< V1/2 aux(31) =< 2/3*V1 aux(32) =< 2/5*V1 it(35) =< aux(28) it(36) =< aux(28) it(38) =< aux(28) it(39) =< aux(28) it([43]) =< aux(28) it([42]) =< aux(29) it([43]) =< aux(29) it(32) =< aux(30) it(33) =< aux(30) it(36) =< aux(30) it(35) =< aux(31) it(36) =< aux(31) it(33) =< aux(32) aux(23) =< aux(28)+2 aux(20) =< aux(28)+1 aux(17) =< aux(28)-1 aux(15) =< aux(28) it(35) =< it([42])*(1/3)+aux(31) it(36) =< it([42])*(1/3)+aux(31) it(38) =< it([42])*(1/3)+aux(31) it(32) =< it([42])*(1/2)+aux(30) it(33) =< it([42])*(1/2)+aux(30) it(35) =< it([42])*(1/2)+aux(30) it(36) =< it([42])*(1/2)+aux(30) it(38) =< it([42])*(1/2)+aux(30) it(33) =< it([42])*(3/5)+it([43])*(1/5)+aux(32) it(35) =< it([42])*(3/5)+it([43])*(1/5)+aux(32) it(36) =< it([42])*(3/5)+it([43])*(1/5)+aux(32) it(38) =< it([42])*(3/5)+it([43])*(1/5)+aux(32) s(95) =< it(39)*aux(23) s(93) =< it(39)*aux(20) s(89) =< it(38)*aux(20) s(87) =< it(38)*aux(20) s(88) =< it(38)*aux(23) s(85) =< it(35)*aux(20) s(83) =< it(36)*aux(20) s(79) =< it(33)*aux(17) s(78) =< it(32)*aux(15) s(94) =< s(95) s(90) =< s(93) s(92) =< s(90)*aux(20) s(91) =< s(92) s(86) =< s(89) s(84) =< s(85) s(80) =< s(83) s(82) =< s(80)*aux(20) s(81) =< s(82) s(75) =< s(78) s(77) =< s(75)*aux(28) s(76) =< s(77) with precondition: [V1>=1,Out>=0,V1>=Out] #### Cost of chains of fun(V1,V,Out): * Chain [45]: 10*s(140)+10*s(141)+6*s(142)+12*s(143)+8*s(144)+2*s(145)+2*s(153)+2*s(154)+2*s(157)+4*s(159)+28*s(160)+8*s(162)+4*s(163)+8*s(164)+32*s(165)+8*s(167)+28*s(168)+8*s(170)+10*s(177)+10*s(178)+6*s(179)+12*s(180)+8*s(181)+2*s(182)+2*s(190)+2*s(191)+2*s(194)+4*s(196)+28*s(197)+8*s(199)+4*s(200)+8*s(201)+32*s(202)+8*s(204)+28*s(205)+8*s(207)+1 Such that:aux(38) =< V1 aux(39) =< V1+1 aux(40) =< V1/2 aux(41) =< V1/2+1/2 aux(42) =< 2/3*V1 aux(43) =< 2/5*V1 aux(44) =< V aux(45) =< V+1 aux(46) =< V/2 aux(47) =< V/2+1/2 aux(48) =< 2/3*V aux(49) =< 2/5*V s(137) =< aux(41) s(174) =< aux(47) s(143) =< aux(38) s(180) =< aux(44) s(177) =< aux(44) s(178) =< aux(44) s(179) =< aux(44) s(174) =< aux(44) s(174) =< aux(45) s(181) =< aux(46) s(182) =< aux(46) s(178) =< aux(46) s(177) =< aux(48) s(178) =< aux(48) s(182) =< aux(49) s(183) =< aux(44)+2 s(184) =< aux(44)+1 s(185) =< aux(44)-1 s(186) =< aux(44) s(177) =< aux(45)*(1/3)+aux(48) s(178) =< aux(45)*(1/3)+aux(48) s(179) =< aux(45)*(1/3)+aux(48) s(181) =< aux(45)*(1/2)+aux(46) s(182) =< aux(45)*(1/2)+aux(46) s(177) =< aux(45)*(1/2)+aux(46) s(178) =< aux(45)*(1/2)+aux(46) s(179) =< aux(45)*(1/2)+aux(46) s(182) =< aux(45)*(3/5)+s(174)*(1/5)+aux(49) s(177) =< aux(45)*(3/5)+s(174)*(1/5)+aux(49) s(178) =< aux(45)*(3/5)+s(174)*(1/5)+aux(49) s(179) =< aux(45)*(3/5)+s(174)*(1/5)+aux(49) s(187) =< s(180)*s(183) s(188) =< s(180)*s(184) s(189) =< s(179)*s(184) s(190) =< s(179)*s(184) s(191) =< s(179)*s(183) s(192) =< s(177)*s(184) s(193) =< s(178)*s(184) s(194) =< s(182)*s(185) s(195) =< s(181)*s(186) s(196) =< s(187) s(197) =< s(188) s(198) =< s(197)*s(184) s(199) =< s(198) s(200) =< s(189) s(201) =< s(192) s(202) =< s(193) s(203) =< s(202)*s(184) s(204) =< s(203) s(205) =< s(195) s(206) =< s(205)*aux(44) s(207) =< s(206) s(140) =< aux(38) s(141) =< aux(38) s(142) =< aux(38) s(137) =< aux(38) s(137) =< aux(39) s(144) =< aux(40) s(145) =< aux(40) s(141) =< aux(40) s(140) =< aux(42) s(141) =< aux(42) s(145) =< aux(43) s(146) =< aux(38)+2 s(147) =< aux(38)+1 s(148) =< aux(38)-1 s(149) =< aux(38) s(140) =< aux(39)*(1/3)+aux(42) s(141) =< aux(39)*(1/3)+aux(42) s(142) =< aux(39)*(1/3)+aux(42) s(144) =< aux(39)*(1/2)+aux(40) s(145) =< aux(39)*(1/2)+aux(40) s(140) =< aux(39)*(1/2)+aux(40) s(141) =< aux(39)*(1/2)+aux(40) s(142) =< aux(39)*(1/2)+aux(40) s(145) =< aux(39)*(3/5)+s(137)*(1/5)+aux(43) s(140) =< aux(39)*(3/5)+s(137)*(1/5)+aux(43) s(141) =< aux(39)*(3/5)+s(137)*(1/5)+aux(43) s(142) =< aux(39)*(3/5)+s(137)*(1/5)+aux(43) s(150) =< s(143)*s(146) s(151) =< s(143)*s(147) s(152) =< s(142)*s(147) s(153) =< s(142)*s(147) s(154) =< s(142)*s(146) s(155) =< s(140)*s(147) s(156) =< s(141)*s(147) s(157) =< s(145)*s(148) s(158) =< s(144)*s(149) s(159) =< s(150) s(160) =< s(151) s(161) =< s(160)*s(147) s(162) =< s(161) s(163) =< s(152) s(164) =< s(155) s(165) =< s(156) s(166) =< s(165)*s(147) s(167) =< s(166) s(168) =< s(158) s(169) =< s(168)*aux(38) s(170) =< s(169) with precondition: [Out=0,V1>=0,V>=0] * Chain [44]: 15*s(296)+15*s(297)+9*s(298)+15*s(299)+12*s(300)+3*s(301)+3*s(309)+3*s(310)+3*s(313)+6*s(315)+42*s(316)+12*s(318)+6*s(319)+12*s(320)+48*s(321)+12*s(323)+42*s(324)+12*s(326)+10*s(333)+10*s(334)+6*s(335)+11*s(336)+8*s(337)+2*s(338)+2*s(346)+2*s(347)+2*s(350)+4*s(352)+28*s(353)+8*s(355)+4*s(356)+8*s(357)+32*s(358)+8*s(360)+28*s(361)+8*s(363)+1 Such that:aux(51) =< V1 aux(52) =< V1+1 aux(53) =< V1/2 aux(54) =< V1/2+1/2 aux(55) =< 2/3*V1 aux(56) =< 2/5*V1 aux(57) =< V aux(58) =< V+1 aux(59) =< V/2 aux(60) =< V/2+1/2 aux(61) =< 2/3*V aux(62) =< 2/5*V s(293) =< aux(54) s(330) =< aux(60) s(333) =< aux(57) s(334) =< aux(57) s(335) =< aux(57) s(336) =< aux(57) s(330) =< aux(57) s(330) =< aux(58) s(337) =< aux(59) s(338) =< aux(59) s(334) =< aux(59) s(333) =< aux(61) s(334) =< aux(61) s(338) =< aux(62) s(339) =< aux(57)+2 s(340) =< aux(57)+1 s(341) =< aux(57)-1 s(342) =< aux(57) s(333) =< aux(58)*(1/3)+aux(61) s(334) =< aux(58)*(1/3)+aux(61) s(335) =< aux(58)*(1/3)+aux(61) s(337) =< aux(58)*(1/2)+aux(59) s(338) =< aux(58)*(1/2)+aux(59) s(333) =< aux(58)*(1/2)+aux(59) s(334) =< aux(58)*(1/2)+aux(59) s(335) =< aux(58)*(1/2)+aux(59) s(338) =< aux(58)*(3/5)+s(330)*(1/5)+aux(62) s(333) =< aux(58)*(3/5)+s(330)*(1/5)+aux(62) s(334) =< aux(58)*(3/5)+s(330)*(1/5)+aux(62) s(335) =< aux(58)*(3/5)+s(330)*(1/5)+aux(62) s(343) =< s(336)*s(339) s(344) =< s(336)*s(340) s(345) =< s(335)*s(340) s(346) =< s(335)*s(340) s(347) =< s(335)*s(339) s(348) =< s(333)*s(340) s(349) =< s(334)*s(340) s(350) =< s(338)*s(341) s(351) =< s(337)*s(342) s(352) =< s(343) s(353) =< s(344) s(354) =< s(353)*s(340) s(355) =< s(354) s(356) =< s(345) s(357) =< s(348) s(358) =< s(349) s(359) =< s(358)*s(340) s(360) =< s(359) s(361) =< s(351) s(362) =< s(361)*aux(57) s(363) =< s(362) s(296) =< aux(51) s(297) =< aux(51) s(298) =< aux(51) s(299) =< aux(51) s(293) =< aux(51) s(293) =< aux(52) s(300) =< aux(53) s(301) =< aux(53) s(297) =< aux(53) s(296) =< aux(55) s(297) =< aux(55) s(301) =< aux(56) s(302) =< aux(51)+2 s(303) =< aux(51)+1 s(304) =< aux(51)-1 s(305) =< aux(51) s(296) =< aux(52)*(1/3)+aux(55) s(297) =< aux(52)*(1/3)+aux(55) s(298) =< aux(52)*(1/3)+aux(55) s(300) =< aux(52)*(1/2)+aux(53) s(301) =< aux(52)*(1/2)+aux(53) s(296) =< aux(52)*(1/2)+aux(53) s(297) =< aux(52)*(1/2)+aux(53) s(298) =< aux(52)*(1/2)+aux(53) s(301) =< aux(52)*(3/5)+s(293)*(1/5)+aux(56) s(296) =< aux(52)*(3/5)+s(293)*(1/5)+aux(56) s(297) =< aux(52)*(3/5)+s(293)*(1/5)+aux(56) s(298) =< aux(52)*(3/5)+s(293)*(1/5)+aux(56) s(306) =< s(299)*s(302) s(307) =< s(299)*s(303) s(308) =< s(298)*s(303) s(309) =< s(298)*s(303) s(310) =< s(298)*s(302) s(311) =< s(296)*s(303) s(312) =< s(297)*s(303) s(313) =< s(301)*s(304) s(314) =< s(300)*s(305) s(315) =< s(306) s(316) =< s(307) s(317) =< s(316)*s(303) s(318) =< s(317) s(319) =< s(308) s(320) =< s(311) s(321) =< s(312) s(322) =< s(321)*s(303) s(323) =< s(322) s(324) =< s(314) s(325) =< s(324)*aux(51) s(326) =< s(325) with precondition: [V>=0,Out>=1,V1>=Out] #### Cost of chains of fun2(V1,Out): * Chain [48]: 0 with precondition: [Out=0,V1>=0] * Chain [47]: 0 with precondition: [Out=1,V1>=0] * Chain [46]: 5*s(482)+5*s(483)+3*s(484)+5*s(485)+4*s(486)+1*s(487)+1*s(495)+1*s(496)+1*s(499)+2*s(501)+14*s(502)+4*s(504)+2*s(505)+4*s(506)+16*s(507)+4*s(509)+14*s(510)+4*s(512)+0 Such that:s(476) =< V1 s(477) =< V1+1 s(478) =< V1/2 s(479) =< V1/2+1/2 s(480) =< 2/3*V1 s(481) =< 2/5*V1 s(482) =< s(476) s(483) =< s(476) s(484) =< s(476) s(485) =< s(476) s(479) =< s(476) s(479) =< s(477) s(486) =< s(478) s(487) =< s(478) s(483) =< s(478) s(482) =< s(480) s(483) =< s(480) s(487) =< s(481) s(488) =< s(476)+2 s(489) =< s(476)+1 s(490) =< s(476)-1 s(491) =< s(476) s(482) =< s(477)*(1/3)+s(480) s(483) =< s(477)*(1/3)+s(480) s(484) =< s(477)*(1/3)+s(480) s(486) =< s(477)*(1/2)+s(478) s(487) =< s(477)*(1/2)+s(478) s(482) =< s(477)*(1/2)+s(478) s(483) =< s(477)*(1/2)+s(478) s(484) =< s(477)*(1/2)+s(478) s(487) =< s(477)*(3/5)+s(479)*(1/5)+s(481) s(482) =< s(477)*(3/5)+s(479)*(1/5)+s(481) s(483) =< s(477)*(3/5)+s(479)*(1/5)+s(481) s(484) =< s(477)*(3/5)+s(479)*(1/5)+s(481) s(492) =< s(485)*s(488) s(493) =< s(485)*s(489) s(494) =< s(484)*s(489) s(495) =< s(484)*s(489) s(496) =< s(484)*s(488) s(497) =< s(482)*s(489) s(498) =< s(483)*s(489) s(499) =< s(487)*s(490) s(500) =< s(486)*s(491) s(501) =< s(492) s(502) =< s(493) s(503) =< s(502)*s(489) s(504) =< s(503) s(505) =< s(494) s(506) =< s(497) s(507) =< s(498) s(508) =< s(507)*s(489) s(509) =< s(508) s(510) =< s(500) s(511) =< s(510)*s(476) s(512) =< s(511) with precondition: [V1>=1,Out>=1,V1+1>=Out] #### Cost of chains of fun3(V1,Out): * Chain [50]: 5*s(519)+5*s(520)+3*s(521)+7*s(522)+4*s(523)+1*s(524)+1*s(532)+1*s(533)+1*s(536)+2*s(538)+14*s(539)+4*s(541)+2*s(542)+4*s(543)+16*s(544)+4*s(546)+14*s(547)+4*s(549)+2 Such that:aux(63) =< V1 s(514) =< V1+1 s(515) =< V1/2 s(516) =< V1/2+1/2 s(517) =< 2/3*V1 s(518) =< 2/5*V1 s(522) =< aux(63) s(519) =< aux(63) s(520) =< aux(63) s(521) =< aux(63) s(516) =< aux(63) s(516) =< s(514) s(523) =< s(515) s(524) =< s(515) s(520) =< s(515) s(519) =< s(517) s(520) =< s(517) s(524) =< s(518) s(525) =< aux(63)+2 s(526) =< aux(63)+1 s(527) =< aux(63)-1 s(528) =< aux(63) s(519) =< s(514)*(1/3)+s(517) s(520) =< s(514)*(1/3)+s(517) s(521) =< s(514)*(1/3)+s(517) s(523) =< s(514)*(1/2)+s(515) s(524) =< s(514)*(1/2)+s(515) s(519) =< s(514)*(1/2)+s(515) s(520) =< s(514)*(1/2)+s(515) s(521) =< s(514)*(1/2)+s(515) s(524) =< s(514)*(3/5)+s(516)*(1/5)+s(518) s(519) =< s(514)*(3/5)+s(516)*(1/5)+s(518) s(520) =< s(514)*(3/5)+s(516)*(1/5)+s(518) s(521) =< s(514)*(3/5)+s(516)*(1/5)+s(518) s(529) =< s(522)*s(525) s(530) =< s(522)*s(526) s(531) =< s(521)*s(526) s(532) =< s(521)*s(526) s(533) =< s(521)*s(525) s(534) =< s(519)*s(526) s(535) =< s(520)*s(526) s(536) =< s(524)*s(527) s(537) =< s(523)*s(528) s(538) =< s(529) s(539) =< s(530) s(540) =< s(539)*s(526) s(541) =< s(540) s(542) =< s(531) s(543) =< s(534) s(544) =< s(535) s(545) =< s(544)*s(526) s(546) =< s(545) s(547) =< s(537) s(548) =< s(547)*aux(63) s(549) =< s(548) with precondition: [Out=0,V1>=0] * Chain [49]: 5*s(560)+5*s(561)+3*s(562)+19*s(563)+4*s(564)+1*s(565)+1*s(573)+1*s(574)+1*s(577)+2*s(579)+14*s(580)+4*s(582)+2*s(583)+4*s(584)+16*s(585)+4*s(587)+14*s(588)+4*s(590)+4*s(594)+3 Such that:s(555) =< V1+1 s(556) =< V1/2 s(557) =< V1/2+1/2 s(558) =< 2/3*V1 s(559) =< 2/5*V1 aux(64) =< V1 s(563) =< aux(64) s(593) =< s(563)*aux(64) s(594) =< s(593) s(560) =< aux(64) s(561) =< aux(64) s(562) =< aux(64) s(557) =< aux(64) s(557) =< s(555) s(564) =< s(556) s(565) =< s(556) s(561) =< s(556) s(560) =< s(558) s(561) =< s(558) s(565) =< s(559) s(566) =< aux(64)+2 s(567) =< aux(64)+1 s(568) =< aux(64)-1 s(569) =< aux(64) s(560) =< s(555)*(1/3)+s(558) s(561) =< s(555)*(1/3)+s(558) s(562) =< s(555)*(1/3)+s(558) s(564) =< s(555)*(1/2)+s(556) s(565) =< s(555)*(1/2)+s(556) s(560) =< s(555)*(1/2)+s(556) s(561) =< s(555)*(1/2)+s(556) s(562) =< s(555)*(1/2)+s(556) s(565) =< s(555)*(3/5)+s(557)*(1/5)+s(559) s(560) =< s(555)*(3/5)+s(557)*(1/5)+s(559) s(561) =< s(555)*(3/5)+s(557)*(1/5)+s(559) s(562) =< s(555)*(3/5)+s(557)*(1/5)+s(559) s(570) =< s(563)*s(566) s(571) =< s(563)*s(567) s(572) =< s(562)*s(567) s(573) =< s(562)*s(567) s(574) =< s(562)*s(566) s(575) =< s(560)*s(567) s(576) =< s(561)*s(567) s(577) =< s(565)*s(568) s(578) =< s(564)*s(569) s(579) =< s(570) s(580) =< s(571) s(581) =< s(580)*s(567) s(582) =< s(581) s(583) =< s(572) s(584) =< s(575) s(585) =< s(576) s(586) =< s(585)*s(567) s(587) =< s(586) s(588) =< s(578) s(589) =< s(588)*aux(64) s(590) =< s(589) with precondition: [Out>=1,V1>=Out] #### Cost of chains of fun4(Out): * Chain [52]: 0 with precondition: [Out=0] * Chain [51]: 0 with precondition: [Out=1] #### Cost of chains of fun5(V1,V,Out): * Chain [56]: 15*s(601)+15*s(602)+9*s(603)+15*s(604)+12*s(605)+3*s(606)+3*s(614)+3*s(615)+3*s(618)+6*s(620)+42*s(621)+12*s(623)+6*s(624)+12*s(625)+48*s(626)+12*s(628)+42*s(629)+12*s(631)+15*s(638)+15*s(639)+9*s(640)+17*s(641)+12*s(642)+3*s(643)+3*s(651)+3*s(652)+3*s(655)+6*s(657)+42*s(658)+12*s(660)+6*s(661)+12*s(662)+48*s(663)+12*s(665)+42*s(666)+12*s(668)+3 Such that:aux(66) =< V1 aux(67) =< V1+1 aux(68) =< V1/2 aux(69) =< V1/2+1/2 aux(70) =< 2/3*V1 aux(71) =< 2/5*V1 aux(72) =< V aux(73) =< V+1 aux(74) =< V/2 aux(75) =< V/2+1/2 aux(76) =< 2/3*V aux(77) =< 2/5*V s(598) =< aux(69) s(635) =< aux(75) s(638) =< aux(72) s(639) =< aux(72) s(640) =< aux(72) s(641) =< aux(72) s(635) =< aux(72) s(635) =< aux(73) s(642) =< aux(74) s(643) =< aux(74) s(639) =< aux(74) s(638) =< aux(76) s(639) =< aux(76) s(643) =< aux(77) s(644) =< aux(72)+2 s(645) =< aux(72)+1 s(646) =< aux(72)-1 s(647) =< aux(72) s(638) =< aux(73)*(1/3)+aux(76) s(639) =< aux(73)*(1/3)+aux(76) s(640) =< aux(73)*(1/3)+aux(76) s(642) =< aux(73)*(1/2)+aux(74) s(643) =< aux(73)*(1/2)+aux(74) s(638) =< aux(73)*(1/2)+aux(74) s(639) =< aux(73)*(1/2)+aux(74) s(640) =< aux(73)*(1/2)+aux(74) s(643) =< aux(73)*(3/5)+s(635)*(1/5)+aux(77) s(638) =< aux(73)*(3/5)+s(635)*(1/5)+aux(77) s(639) =< aux(73)*(3/5)+s(635)*(1/5)+aux(77) s(640) =< aux(73)*(3/5)+s(635)*(1/5)+aux(77) s(648) =< s(641)*s(644) s(649) =< s(641)*s(645) s(650) =< s(640)*s(645) s(651) =< s(640)*s(645) s(652) =< s(640)*s(644) s(653) =< s(638)*s(645) s(654) =< s(639)*s(645) s(655) =< s(643)*s(646) s(656) =< s(642)*s(647) s(657) =< s(648) s(658) =< s(649) s(659) =< s(658)*s(645) s(660) =< s(659) s(661) =< s(650) s(662) =< s(653) s(663) =< s(654) s(664) =< s(663)*s(645) s(665) =< s(664) s(666) =< s(656) s(667) =< s(666)*aux(72) s(668) =< s(667) s(601) =< aux(66) s(602) =< aux(66) s(603) =< aux(66) s(604) =< aux(66) s(598) =< aux(66) s(598) =< aux(67) s(605) =< aux(68) s(606) =< aux(68) s(602) =< aux(68) s(601) =< aux(70) s(602) =< aux(70) s(606) =< aux(71) s(607) =< aux(66)+2 s(608) =< aux(66)+1 s(609) =< aux(66)-1 s(610) =< aux(66) s(601) =< aux(67)*(1/3)+aux(70) s(602) =< aux(67)*(1/3)+aux(70) s(603) =< aux(67)*(1/3)+aux(70) s(605) =< aux(67)*(1/2)+aux(68) s(606) =< aux(67)*(1/2)+aux(68) s(601) =< aux(67)*(1/2)+aux(68) s(602) =< aux(67)*(1/2)+aux(68) s(603) =< aux(67)*(1/2)+aux(68) s(606) =< aux(67)*(3/5)+s(598)*(1/5)+aux(71) s(601) =< aux(67)*(3/5)+s(598)*(1/5)+aux(71) s(602) =< aux(67)*(3/5)+s(598)*(1/5)+aux(71) s(603) =< aux(67)*(3/5)+s(598)*(1/5)+aux(71) s(611) =< s(604)*s(607) s(612) =< s(604)*s(608) s(613) =< s(603)*s(608) s(614) =< s(603)*s(608) s(615) =< s(603)*s(607) s(616) =< s(601)*s(608) s(617) =< s(602)*s(608) s(618) =< s(606)*s(609) s(619) =< s(605)*s(610) s(620) =< s(611) s(621) =< s(612) s(622) =< s(621)*s(608) s(623) =< s(622) s(624) =< s(613) s(625) =< s(616) s(626) =< s(617) s(627) =< s(626)*s(608) s(628) =< s(627) s(629) =< s(619) s(630) =< s(629)*aux(66) s(631) =< s(630) with precondition: [Out=0,V1>=0,V>=0] * Chain [55]: 10*s(825)+10*s(826)+6*s(827)+10*s(828)+8*s(829)+2*s(830)+2*s(838)+2*s(839)+2*s(842)+4*s(844)+28*s(845)+8*s(847)+4*s(848)+8*s(849)+32*s(850)+8*s(852)+28*s(853)+8*s(855)+20*s(862)+20*s(863)+12*s(864)+28*s(865)+16*s(866)+4*s(867)+4*s(875)+4*s(876)+4*s(879)+8*s(881)+56*s(882)+16*s(884)+8*s(885)+16*s(886)+64*s(887)+16*s(889)+56*s(890)+16*s(892)+4 Such that:aux(80) =< V1 aux(81) =< V1+1 aux(82) =< V1/2 aux(83) =< V1/2+1/2 aux(84) =< 2/3*V1 aux(85) =< 2/5*V1 aux(86) =< V aux(87) =< V+1 aux(88) =< V/2 aux(89) =< V/2+1/2 aux(90) =< 2/3*V aux(91) =< 2/5*V s(822) =< aux(83) s(859) =< aux(89) s(862) =< aux(86) s(863) =< aux(86) s(864) =< aux(86) s(865) =< aux(86) s(859) =< aux(86) s(859) =< aux(87) s(866) =< aux(88) s(867) =< aux(88) s(863) =< aux(88) s(862) =< aux(90) s(863) =< aux(90) s(867) =< aux(91) s(868) =< aux(86)+2 s(869) =< aux(86)+1 s(870) =< aux(86)-1 s(871) =< aux(86) s(862) =< aux(87)*(1/3)+aux(90) s(863) =< aux(87)*(1/3)+aux(90) s(864) =< aux(87)*(1/3)+aux(90) s(866) =< aux(87)*(1/2)+aux(88) s(867) =< aux(87)*(1/2)+aux(88) s(862) =< aux(87)*(1/2)+aux(88) s(863) =< aux(87)*(1/2)+aux(88) s(864) =< aux(87)*(1/2)+aux(88) s(867) =< aux(87)*(3/5)+s(859)*(1/5)+aux(91) s(862) =< aux(87)*(3/5)+s(859)*(1/5)+aux(91) s(863) =< aux(87)*(3/5)+s(859)*(1/5)+aux(91) s(864) =< aux(87)*(3/5)+s(859)*(1/5)+aux(91) s(872) =< s(865)*s(868) s(873) =< s(865)*s(869) s(874) =< s(864)*s(869) s(875) =< s(864)*s(869) s(876) =< s(864)*s(868) s(877) =< s(862)*s(869) s(878) =< s(863)*s(869) s(879) =< s(867)*s(870) s(880) =< s(866)*s(871) s(881) =< s(872) s(882) =< s(873) s(883) =< s(882)*s(869) s(884) =< s(883) s(885) =< s(874) s(886) =< s(877) s(887) =< s(878) s(888) =< s(887)*s(869) s(889) =< s(888) s(890) =< s(880) s(891) =< s(890)*aux(86) s(892) =< s(891) s(825) =< aux(80) s(826) =< aux(80) s(827) =< aux(80) s(828) =< aux(80) s(822) =< aux(80) s(822) =< aux(81) s(829) =< aux(82) s(830) =< aux(82) s(826) =< aux(82) s(825) =< aux(84) s(826) =< aux(84) s(830) =< aux(85) s(831) =< aux(80)+2 s(832) =< aux(80)+1 s(833) =< aux(80)-1 s(834) =< aux(80) s(825) =< aux(81)*(1/3)+aux(84) s(826) =< aux(81)*(1/3)+aux(84) s(827) =< aux(81)*(1/3)+aux(84) s(829) =< aux(81)*(1/2)+aux(82) s(830) =< aux(81)*(1/2)+aux(82) s(825) =< aux(81)*(1/2)+aux(82) s(826) =< aux(81)*(1/2)+aux(82) s(827) =< aux(81)*(1/2)+aux(82) s(830) =< aux(81)*(3/5)+s(822)*(1/5)+aux(85) s(825) =< aux(81)*(3/5)+s(822)*(1/5)+aux(85) s(826) =< aux(81)*(3/5)+s(822)*(1/5)+aux(85) s(827) =< aux(81)*(3/5)+s(822)*(1/5)+aux(85) s(835) =< s(828)*s(831) s(836) =< s(828)*s(832) s(837) =< s(827)*s(832) s(838) =< s(827)*s(832) s(839) =< s(827)*s(831) s(840) =< s(825)*s(832) s(841) =< s(826)*s(832) s(842) =< s(830)*s(833) s(843) =< s(829)*s(834) s(844) =< s(835) s(845) =< s(836) s(846) =< s(845)*s(832) s(847) =< s(846) s(848) =< s(837) s(849) =< s(840) s(850) =< s(841) s(851) =< s(850)*s(832) s(852) =< s(851) s(853) =< s(843) s(854) =< s(853)*aux(80) s(855) =< s(854) with precondition: [Out=1,V1>=0,V>=1] * Chain [54]: 5*s(1055)+5*s(1056)+3*s(1057)+5*s(1058)+4*s(1059)+1*s(1060)+1*s(1068)+1*s(1069)+1*s(1072)+2*s(1074)+14*s(1075)+4*s(1077)+2*s(1078)+4*s(1079)+16*s(1080)+4*s(1082)+14*s(1083)+4*s(1085)+10*s(1092)+10*s(1093)+6*s(1094)+42*s(1095)+8*s(1096)+2*s(1097)+2*s(1105)+2*s(1106)+2*s(1109)+4*s(1111)+28*s(1112)+8*s(1114)+4*s(1115)+8*s(1116)+32*s(1117)+8*s(1119)+28*s(1120)+8*s(1122)+8*s(1128)+5 Such that:s(1049) =< V1 s(1050) =< V1+1 s(1051) =< V1/2 s(1052) =< V1/2+1/2 s(1053) =< 2/3*V1 s(1054) =< 2/5*V1 aux(94) =< V aux(95) =< V+1 aux(96) =< V/2 aux(97) =< V/2+1/2 aux(98) =< 2/3*V aux(99) =< 2/5*V s(1089) =< aux(97) s(1095) =< aux(94) s(1127) =< s(1095)*aux(94) s(1128) =< s(1127) s(1092) =< aux(94) s(1093) =< aux(94) s(1094) =< aux(94) s(1089) =< aux(94) s(1089) =< aux(95) s(1096) =< aux(96) s(1097) =< aux(96) s(1093) =< aux(96) s(1092) =< aux(98) s(1093) =< aux(98) s(1097) =< aux(99) s(1098) =< aux(94)+2 s(1099) =< aux(94)+1 s(1100) =< aux(94)-1 s(1101) =< aux(94) s(1092) =< aux(95)*(1/3)+aux(98) s(1093) =< aux(95)*(1/3)+aux(98) s(1094) =< aux(95)*(1/3)+aux(98) s(1096) =< aux(95)*(1/2)+aux(96) s(1097) =< aux(95)*(1/2)+aux(96) s(1092) =< aux(95)*(1/2)+aux(96) s(1093) =< aux(95)*(1/2)+aux(96) s(1094) =< aux(95)*(1/2)+aux(96) s(1097) =< aux(95)*(3/5)+s(1089)*(1/5)+aux(99) s(1092) =< aux(95)*(3/5)+s(1089)*(1/5)+aux(99) s(1093) =< aux(95)*(3/5)+s(1089)*(1/5)+aux(99) s(1094) =< aux(95)*(3/5)+s(1089)*(1/5)+aux(99) s(1102) =< s(1095)*s(1098) s(1103) =< s(1095)*s(1099) s(1104) =< s(1094)*s(1099) s(1105) =< s(1094)*s(1099) s(1106) =< s(1094)*s(1098) s(1107) =< s(1092)*s(1099) s(1108) =< s(1093)*s(1099) s(1109) =< s(1097)*s(1100) s(1110) =< s(1096)*s(1101) s(1111) =< s(1102) s(1112) =< s(1103) s(1113) =< s(1112)*s(1099) s(1114) =< s(1113) s(1115) =< s(1104) s(1116) =< s(1107) s(1117) =< s(1108) s(1118) =< s(1117)*s(1099) s(1119) =< s(1118) s(1120) =< s(1110) s(1121) =< s(1120)*aux(94) s(1122) =< s(1121) s(1055) =< s(1049) s(1056) =< s(1049) s(1057) =< s(1049) s(1058) =< s(1049) s(1052) =< s(1049) s(1052) =< s(1050) s(1059) =< s(1051) s(1060) =< s(1051) s(1056) =< s(1051) s(1055) =< s(1053) s(1056) =< s(1053) s(1060) =< s(1054) s(1061) =< s(1049)+2 s(1062) =< s(1049)+1 s(1063) =< s(1049)-1 s(1064) =< s(1049) s(1055) =< s(1050)*(1/3)+s(1053) s(1056) =< s(1050)*(1/3)+s(1053) s(1057) =< s(1050)*(1/3)+s(1053) s(1059) =< s(1050)*(1/2)+s(1051) s(1060) =< s(1050)*(1/2)+s(1051) s(1055) =< s(1050)*(1/2)+s(1051) s(1056) =< s(1050)*(1/2)+s(1051) s(1057) =< s(1050)*(1/2)+s(1051) s(1060) =< s(1050)*(3/5)+s(1052)*(1/5)+s(1054) s(1055) =< s(1050)*(3/5)+s(1052)*(1/5)+s(1054) s(1056) =< s(1050)*(3/5)+s(1052)*(1/5)+s(1054) s(1057) =< s(1050)*(3/5)+s(1052)*(1/5)+s(1054) s(1065) =< s(1058)*s(1061) s(1066) =< s(1058)*s(1062) s(1067) =< s(1057)*s(1062) s(1068) =< s(1057)*s(1062) s(1069) =< s(1057)*s(1061) s(1070) =< s(1055)*s(1062) s(1071) =< s(1056)*s(1062) s(1072) =< s(1060)*s(1063) s(1073) =< s(1059)*s(1064) s(1074) =< s(1065) s(1075) =< s(1066) s(1076) =< s(1075)*s(1062) s(1077) =< s(1076) s(1078) =< s(1067) s(1079) =< s(1070) s(1080) =< s(1071) s(1081) =< s(1080)*s(1062) s(1082) =< s(1081) s(1083) =< s(1073) s(1084) =< s(1083)*s(1049) s(1085) =< s(1084) with precondition: [V1>=0,Out>=2,V>=Out] * Chain [53]: 5*s(1178)+5*s(1179)+3*s(1180)+5*s(1181)+4*s(1182)+1*s(1183)+1*s(1191)+1*s(1192)+1*s(1195)+2*s(1197)+14*s(1198)+4*s(1200)+2*s(1201)+4*s(1202)+16*s(1203)+4*s(1205)+14*s(1206)+4*s(1208)+5*s(1215)+5*s(1216)+3*s(1217)+19*s(1218)+4*s(1219)+1*s(1220)+1*s(1228)+1*s(1229)+1*s(1232)+2*s(1234)+14*s(1235)+4*s(1237)+2*s(1238)+4*s(1239)+16*s(1240)+4*s(1242)+14*s(1243)+4*s(1245)+4*s(1249)+4 Such that:s(1172) =< V1 s(1173) =< V1+1 s(1174) =< V1/2 s(1175) =< V1/2+1/2 s(1176) =< 2/3*V1 s(1177) =< 2/5*V1 s(1210) =< V+1 s(1211) =< V/2 s(1212) =< V/2+1/2 s(1213) =< 2/3*V s(1214) =< 2/5*V aux(100) =< V s(1218) =< aux(100) s(1248) =< s(1218)*aux(100) s(1249) =< s(1248) s(1215) =< aux(100) s(1216) =< aux(100) s(1217) =< aux(100) s(1212) =< aux(100) s(1212) =< s(1210) s(1219) =< s(1211) s(1220) =< s(1211) s(1216) =< s(1211) s(1215) =< s(1213) s(1216) =< s(1213) s(1220) =< s(1214) s(1221) =< aux(100)+2 s(1222) =< aux(100)+1 s(1223) =< aux(100)-1 s(1224) =< aux(100) s(1215) =< s(1210)*(1/3)+s(1213) s(1216) =< s(1210)*(1/3)+s(1213) s(1217) =< s(1210)*(1/3)+s(1213) s(1219) =< s(1210)*(1/2)+s(1211) s(1220) =< s(1210)*(1/2)+s(1211) s(1215) =< s(1210)*(1/2)+s(1211) s(1216) =< s(1210)*(1/2)+s(1211) s(1217) =< s(1210)*(1/2)+s(1211) s(1220) =< s(1210)*(3/5)+s(1212)*(1/5)+s(1214) s(1215) =< s(1210)*(3/5)+s(1212)*(1/5)+s(1214) s(1216) =< s(1210)*(3/5)+s(1212)*(1/5)+s(1214) s(1217) =< s(1210)*(3/5)+s(1212)*(1/5)+s(1214) s(1225) =< s(1218)*s(1221) s(1226) =< s(1218)*s(1222) s(1227) =< s(1217)*s(1222) s(1228) =< s(1217)*s(1222) s(1229) =< s(1217)*s(1221) s(1230) =< s(1215)*s(1222) s(1231) =< s(1216)*s(1222) s(1232) =< s(1220)*s(1223) s(1233) =< s(1219)*s(1224) s(1234) =< s(1225) s(1235) =< s(1226) s(1236) =< s(1235)*s(1222) s(1237) =< s(1236) s(1238) =< s(1227) s(1239) =< s(1230) s(1240) =< s(1231) s(1241) =< s(1240)*s(1222) s(1242) =< s(1241) s(1243) =< s(1233) s(1244) =< s(1243)*aux(100) s(1245) =< s(1244) s(1178) =< s(1172) s(1179) =< s(1172) s(1180) =< s(1172) s(1181) =< s(1172) s(1175) =< s(1172) s(1175) =< s(1173) s(1182) =< s(1174) s(1183) =< s(1174) s(1179) =< s(1174) s(1178) =< s(1176) s(1179) =< s(1176) s(1183) =< s(1177) s(1184) =< s(1172)+2 s(1185) =< s(1172)+1 s(1186) =< s(1172)-1 s(1187) =< s(1172) s(1178) =< s(1173)*(1/3)+s(1176) s(1179) =< s(1173)*(1/3)+s(1176) s(1180) =< s(1173)*(1/3)+s(1176) s(1182) =< s(1173)*(1/2)+s(1174) s(1183) =< s(1173)*(1/2)+s(1174) s(1178) =< s(1173)*(1/2)+s(1174) s(1179) =< s(1173)*(1/2)+s(1174) s(1180) =< s(1173)*(1/2)+s(1174) s(1183) =< s(1173)*(3/5)+s(1175)*(1/5)+s(1177) s(1178) =< s(1173)*(3/5)+s(1175)*(1/5)+s(1177) s(1179) =< s(1173)*(3/5)+s(1175)*(1/5)+s(1177) s(1180) =< s(1173)*(3/5)+s(1175)*(1/5)+s(1177) s(1188) =< s(1181)*s(1184) s(1189) =< s(1181)*s(1185) s(1190) =< s(1180)*s(1185) s(1191) =< s(1180)*s(1185) s(1192) =< s(1180)*s(1184) s(1193) =< s(1178)*s(1185) s(1194) =< s(1179)*s(1185) s(1195) =< s(1183)*s(1186) s(1196) =< s(1182)*s(1187) s(1197) =< s(1188) s(1198) =< s(1189) s(1199) =< s(1198)*s(1185) s(1200) =< s(1199) s(1201) =< s(1190) s(1202) =< s(1193) s(1203) =< s(1194) s(1204) =< s(1203)*s(1185) s(1205) =< s(1204) s(1206) =< s(1196) s(1207) =< s(1206)*s(1172) s(1208) =< s(1207) with precondition: [V1>=1,Out>=1,V>=Out] #### Cost of chains of fun6(V1,V,Out): * Chain [61]: 0 with precondition: [Out=0,V1>=0,V>=0] * Chain [60]: 0 with precondition: [Out=1,V1>=0,V>=0] * Chain [59]: 5*s(1256)+5*s(1257)+3*s(1258)+5*s(1259)+4*s(1260)+1*s(1261)+1*s(1269)+1*s(1270)+1*s(1273)+2*s(1275)+14*s(1276)+4*s(1278)+2*s(1279)+4*s(1280)+16*s(1281)+4*s(1283)+14*s(1284)+4*s(1286)+0 Such that:s(1250) =< V s(1251) =< V+1 s(1252) =< V/2 s(1253) =< V/2+1/2 s(1254) =< 2/3*V s(1255) =< 2/5*V s(1256) =< s(1250) s(1257) =< s(1250) s(1258) =< s(1250) s(1259) =< s(1250) s(1253) =< s(1250) s(1253) =< s(1251) s(1260) =< s(1252) s(1261) =< s(1252) s(1257) =< s(1252) s(1256) =< s(1254) s(1257) =< s(1254) s(1261) =< s(1255) s(1262) =< s(1250)+2 s(1263) =< s(1250)+1 s(1264) =< s(1250)-1 s(1265) =< s(1250) s(1256) =< s(1251)*(1/3)+s(1254) s(1257) =< s(1251)*(1/3)+s(1254) s(1258) =< s(1251)*(1/3)+s(1254) s(1260) =< s(1251)*(1/2)+s(1252) s(1261) =< s(1251)*(1/2)+s(1252) s(1256) =< s(1251)*(1/2)+s(1252) s(1257) =< s(1251)*(1/2)+s(1252) s(1258) =< s(1251)*(1/2)+s(1252) s(1261) =< s(1251)*(3/5)+s(1253)*(1/5)+s(1255) s(1256) =< s(1251)*(3/5)+s(1253)*(1/5)+s(1255) s(1257) =< s(1251)*(3/5)+s(1253)*(1/5)+s(1255) s(1258) =< s(1251)*(3/5)+s(1253)*(1/5)+s(1255) s(1266) =< s(1259)*s(1262) s(1267) =< s(1259)*s(1263) s(1268) =< s(1258)*s(1263) s(1269) =< s(1258)*s(1263) s(1270) =< s(1258)*s(1262) s(1271) =< s(1256)*s(1263) s(1272) =< s(1257)*s(1263) s(1273) =< s(1261)*s(1264) s(1274) =< s(1260)*s(1265) s(1275) =< s(1266) s(1276) =< s(1267) s(1277) =< s(1276)*s(1263) s(1278) =< s(1277) s(1279) =< s(1268) s(1280) =< s(1271) s(1281) =< s(1272) s(1282) =< s(1281)*s(1263) s(1283) =< s(1282) s(1284) =< s(1274) s(1285) =< s(1284)*s(1250) s(1286) =< s(1285) with precondition: [V1>=0,V>=1,Out>=1,V+1>=Out] * Chain [58]: 5*s(1293)+5*s(1294)+3*s(1295)+5*s(1296)+4*s(1297)+1*s(1298)+1*s(1306)+1*s(1307)+1*s(1310)+2*s(1312)+14*s(1313)+4*s(1315)+2*s(1316)+4*s(1317)+16*s(1318)+4*s(1320)+14*s(1321)+4*s(1323)+0 Such that:s(1287) =< V1 s(1288) =< V1+1 s(1289) =< V1/2 s(1290) =< V1/2+1/2 s(1291) =< 2/3*V1 s(1292) =< 2/5*V1 s(1293) =< s(1287) s(1294) =< s(1287) s(1295) =< s(1287) s(1296) =< s(1287) s(1290) =< s(1287) s(1290) =< s(1288) s(1297) =< s(1289) s(1298) =< s(1289) s(1294) =< s(1289) s(1293) =< s(1291) s(1294) =< s(1291) s(1298) =< s(1292) s(1299) =< s(1287)+2 s(1300) =< s(1287)+1 s(1301) =< s(1287)-1 s(1302) =< s(1287) s(1293) =< s(1288)*(1/3)+s(1291) s(1294) =< s(1288)*(1/3)+s(1291) s(1295) =< s(1288)*(1/3)+s(1291) s(1297) =< s(1288)*(1/2)+s(1289) s(1298) =< s(1288)*(1/2)+s(1289) s(1293) =< s(1288)*(1/2)+s(1289) s(1294) =< s(1288)*(1/2)+s(1289) s(1295) =< s(1288)*(1/2)+s(1289) s(1298) =< s(1288)*(3/5)+s(1290)*(1/5)+s(1292) s(1293) =< s(1288)*(3/5)+s(1290)*(1/5)+s(1292) s(1294) =< s(1288)*(3/5)+s(1290)*(1/5)+s(1292) s(1295) =< s(1288)*(3/5)+s(1290)*(1/5)+s(1292) s(1303) =< s(1296)*s(1299) s(1304) =< s(1296)*s(1300) s(1305) =< s(1295)*s(1300) s(1306) =< s(1295)*s(1300) s(1307) =< s(1295)*s(1299) s(1308) =< s(1293)*s(1300) s(1309) =< s(1294)*s(1300) s(1310) =< s(1298)*s(1301) s(1311) =< s(1297)*s(1302) s(1312) =< s(1303) s(1313) =< s(1304) s(1314) =< s(1313)*s(1300) s(1315) =< s(1314) s(1316) =< s(1305) s(1317) =< s(1308) s(1318) =< s(1309) s(1319) =< s(1318)*s(1300) s(1320) =< s(1319) s(1321) =< s(1311) s(1322) =< s(1321)*s(1287) s(1323) =< s(1322) with precondition: [V1>=1,V>=0,Out>=1,V1+1>=Out] * Chain [57]: 5*s(1330)+5*s(1331)+3*s(1332)+5*s(1333)+4*s(1334)+1*s(1335)+1*s(1343)+1*s(1344)+1*s(1347)+2*s(1349)+14*s(1350)+4*s(1352)+2*s(1353)+4*s(1354)+16*s(1355)+4*s(1357)+14*s(1358)+4*s(1360)+5*s(1367)+5*s(1368)+3*s(1369)+5*s(1370)+4*s(1371)+1*s(1372)+1*s(1380)+1*s(1381)+1*s(1384)+2*s(1386)+14*s(1387)+4*s(1389)+2*s(1390)+4*s(1391)+16*s(1392)+4*s(1394)+14*s(1395)+4*s(1397)+0 Such that:s(1324) =< V1 s(1325) =< V1+1 s(1326) =< V1/2 s(1327) =< V1/2+1/2 s(1328) =< 2/3*V1 s(1329) =< 2/5*V1 s(1361) =< V s(1362) =< V+1 s(1363) =< V/2 s(1364) =< V/2+1/2 s(1365) =< 2/3*V s(1366) =< 2/5*V s(1367) =< s(1361) s(1368) =< s(1361) s(1369) =< s(1361) s(1370) =< s(1361) s(1364) =< s(1361) s(1364) =< s(1362) s(1371) =< s(1363) s(1372) =< s(1363) s(1368) =< s(1363) s(1367) =< s(1365) s(1368) =< s(1365) s(1372) =< s(1366) s(1373) =< s(1361)+2 s(1374) =< s(1361)+1 s(1375) =< s(1361)-1 s(1376) =< s(1361) s(1367) =< s(1362)*(1/3)+s(1365) s(1368) =< s(1362)*(1/3)+s(1365) s(1369) =< s(1362)*(1/3)+s(1365) s(1371) =< s(1362)*(1/2)+s(1363) s(1372) =< s(1362)*(1/2)+s(1363) s(1367) =< s(1362)*(1/2)+s(1363) s(1368) =< s(1362)*(1/2)+s(1363) s(1369) =< s(1362)*(1/2)+s(1363) s(1372) =< s(1362)*(3/5)+s(1364)*(1/5)+s(1366) s(1367) =< s(1362)*(3/5)+s(1364)*(1/5)+s(1366) s(1368) =< s(1362)*(3/5)+s(1364)*(1/5)+s(1366) s(1369) =< s(1362)*(3/5)+s(1364)*(1/5)+s(1366) s(1377) =< s(1370)*s(1373) s(1378) =< s(1370)*s(1374) s(1379) =< s(1369)*s(1374) s(1380) =< s(1369)*s(1374) s(1381) =< s(1369)*s(1373) s(1382) =< s(1367)*s(1374) s(1383) =< s(1368)*s(1374) s(1384) =< s(1372)*s(1375) s(1385) =< s(1371)*s(1376) s(1386) =< s(1377) s(1387) =< s(1378) s(1388) =< s(1387)*s(1374) s(1389) =< s(1388) s(1390) =< s(1379) s(1391) =< s(1382) s(1392) =< s(1383) s(1393) =< s(1392)*s(1374) s(1394) =< s(1393) s(1395) =< s(1385) s(1396) =< s(1395)*s(1361) s(1397) =< s(1396) s(1330) =< s(1324) s(1331) =< s(1324) s(1332) =< s(1324) s(1333) =< s(1324) s(1327) =< s(1324) s(1327) =< s(1325) s(1334) =< s(1326) s(1335) =< s(1326) s(1331) =< s(1326) s(1330) =< s(1328) s(1331) =< s(1328) s(1335) =< s(1329) s(1336) =< s(1324)+2 s(1337) =< s(1324)+1 s(1338) =< s(1324)-1 s(1339) =< s(1324) s(1330) =< s(1325)*(1/3)+s(1328) s(1331) =< s(1325)*(1/3)+s(1328) s(1332) =< s(1325)*(1/3)+s(1328) s(1334) =< s(1325)*(1/2)+s(1326) s(1335) =< s(1325)*(1/2)+s(1326) s(1330) =< s(1325)*(1/2)+s(1326) s(1331) =< s(1325)*(1/2)+s(1326) s(1332) =< s(1325)*(1/2)+s(1326) s(1335) =< s(1325)*(3/5)+s(1327)*(1/5)+s(1329) s(1330) =< s(1325)*(3/5)+s(1327)*(1/5)+s(1329) s(1331) =< s(1325)*(3/5)+s(1327)*(1/5)+s(1329) s(1332) =< s(1325)*(3/5)+s(1327)*(1/5)+s(1329) s(1340) =< s(1333)*s(1336) s(1341) =< s(1333)*s(1337) s(1342) =< s(1332)*s(1337) s(1343) =< s(1332)*s(1337) s(1344) =< s(1332)*s(1336) s(1345) =< s(1330)*s(1337) s(1346) =< s(1331)*s(1337) s(1347) =< s(1335)*s(1338) s(1348) =< s(1334)*s(1339) s(1349) =< s(1340) s(1350) =< s(1341) s(1351) =< s(1350)*s(1337) s(1352) =< s(1351) s(1353) =< s(1342) s(1354) =< s(1345) s(1355) =< s(1346) s(1356) =< s(1355)*s(1337) s(1357) =< s(1356) s(1358) =< s(1348) s(1359) =< s(1358)*s(1324) s(1360) =< s(1359) with precondition: [V1>=1,V>=1,Out>=1,V+V1+1>=Out] #### Cost of chains of start(V1,V): * Chain [62]: 177*s(1399)+20*s(1401)+125*s(1414)+8*s(1420)+90*s(1429)+90*s(1430)+54*s(1431)+72*s(1433)+18*s(1434)+18*s(1442)+18*s(1443)+18*s(1446)+36*s(1448)+252*s(1449)+72*s(1451)+36*s(1452)+72*s(1453)+288*s(1454)+72*s(1456)+252*s(1457)+72*s(1459)+80*s(1476)+80*s(1477)+48*s(1478)+64*s(1479)+16*s(1480)+16*s(1488)+16*s(1489)+16*s(1492)+32*s(1494)+224*s(1495)+64*s(1497)+32*s(1498)+64*s(1499)+256*s(1500)+64*s(1502)+224*s(1503)+64*s(1505)+5 Such that:aux(103) =< V1 aux(104) =< V1+1 aux(105) =< V1/2 aux(106) =< V1/2+1/2 aux(107) =< 2/3*V1 aux(108) =< 2/5*V1 aux(109) =< V aux(110) =< V+1 aux(111) =< V/2 aux(112) =< V/2+1/2 aux(113) =< 2/3*V aux(114) =< 2/5*V s(1414) =< aux(103) s(1426) =< aux(106) s(1399) =< aux(109) s(1473) =< aux(112) s(1419) =< s(1414)*aux(103) s(1420) =< s(1419) s(1429) =< aux(103) s(1430) =< aux(103) s(1431) =< aux(103) s(1426) =< aux(103) s(1426) =< aux(104) s(1433) =< aux(105) s(1434) =< aux(105) s(1430) =< aux(105) s(1429) =< aux(107) s(1430) =< aux(107) s(1434) =< aux(108) s(1435) =< aux(103)+2 s(1436) =< aux(103)+1 s(1437) =< aux(103)-1 s(1438) =< aux(103) s(1429) =< aux(104)*(1/3)+aux(107) s(1430) =< aux(104)*(1/3)+aux(107) s(1431) =< aux(104)*(1/3)+aux(107) s(1433) =< aux(104)*(1/2)+aux(105) s(1434) =< aux(104)*(1/2)+aux(105) s(1429) =< aux(104)*(1/2)+aux(105) s(1430) =< aux(104)*(1/2)+aux(105) s(1431) =< aux(104)*(1/2)+aux(105) s(1434) =< aux(104)*(3/5)+s(1426)*(1/5)+aux(108) s(1429) =< aux(104)*(3/5)+s(1426)*(1/5)+aux(108) s(1430) =< aux(104)*(3/5)+s(1426)*(1/5)+aux(108) s(1431) =< aux(104)*(3/5)+s(1426)*(1/5)+aux(108) s(1439) =< s(1414)*s(1435) s(1440) =< s(1414)*s(1436) s(1441) =< s(1431)*s(1436) s(1442) =< s(1431)*s(1436) s(1443) =< s(1431)*s(1435) s(1444) =< s(1429)*s(1436) s(1445) =< s(1430)*s(1436) s(1446) =< s(1434)*s(1437) s(1447) =< s(1433)*s(1438) s(1448) =< s(1439) s(1449) =< s(1440) s(1450) =< s(1449)*s(1436) s(1451) =< s(1450) s(1452) =< s(1441) s(1453) =< s(1444) s(1454) =< s(1445) s(1455) =< s(1454)*s(1436) s(1456) =< s(1455) s(1457) =< s(1447) s(1458) =< s(1457)*aux(103) s(1459) =< s(1458) s(1476) =< aux(109) s(1477) =< aux(109) s(1478) =< aux(109) s(1473) =< aux(109) s(1473) =< aux(110) s(1479) =< aux(111) s(1480) =< aux(111) s(1477) =< aux(111) s(1476) =< aux(113) s(1477) =< aux(113) s(1480) =< aux(114) s(1481) =< aux(109)+2 s(1482) =< aux(109)+1 s(1483) =< aux(109)-1 s(1484) =< aux(109) s(1476) =< aux(110)*(1/3)+aux(113) s(1477) =< aux(110)*(1/3)+aux(113) s(1478) =< aux(110)*(1/3)+aux(113) s(1479) =< aux(110)*(1/2)+aux(111) s(1480) =< aux(110)*(1/2)+aux(111) s(1476) =< aux(110)*(1/2)+aux(111) s(1477) =< aux(110)*(1/2)+aux(111) s(1478) =< aux(110)*(1/2)+aux(111) s(1480) =< aux(110)*(3/5)+s(1473)*(1/5)+aux(114) s(1476) =< aux(110)*(3/5)+s(1473)*(1/5)+aux(114) s(1477) =< aux(110)*(3/5)+s(1473)*(1/5)+aux(114) s(1478) =< aux(110)*(3/5)+s(1473)*(1/5)+aux(114) s(1485) =< s(1399)*s(1481) s(1486) =< s(1399)*s(1482) s(1487) =< s(1478)*s(1482) s(1488) =< s(1478)*s(1482) s(1489) =< s(1478)*s(1481) s(1490) =< s(1476)*s(1482) s(1491) =< s(1477)*s(1482) s(1492) =< s(1480)*s(1483) s(1493) =< s(1479)*s(1484) s(1494) =< s(1485) s(1495) =< s(1486) s(1496) =< s(1495)*s(1482) s(1497) =< s(1496) s(1498) =< s(1487) s(1499) =< s(1490) s(1500) =< s(1491) s(1501) =< s(1500)*s(1482) s(1502) =< s(1501) s(1503) =< s(1493) s(1504) =< s(1503)*aux(109) s(1505) =< s(1504) s(1400) =< s(1399)*aux(109) s(1401) =< s(1400) with precondition: [] Closed-form bounds of start(V1,V): ------------------------------------- * Chain [62] with precondition: [] - Upper bound: nat(V1)*1277+5+nat(V1)*1016*nat(V1)+nat(V1)*144*nat(V1)*nat(V1)+nat(V1)*72*nat(V1)*nat(V1/2)+nat(V1)*252*nat(V1/2)+nat(V)*1201+nat(V)*916*nat(V)+nat(V)*128*nat(V)*nat(V)+nat(V)*64*nat(V)*nat(V/2)+nat(V)*224*nat(V/2)+nat(nat(V1)+ -1)*18*nat(V1/2)+nat(nat(V)+ -1)*16*nat(V/2)+nat(V1/2)*90+nat(V/2)*80 - Complexity: n^3 ### Maximum cost of start(V1,V): nat(V1)*1277+5+nat(V1)*1016*nat(V1)+nat(V1)*144*nat(V1)*nat(V1)+nat(V1)*72*nat(V1)*nat(V1/2)+nat(V1)*252*nat(V1/2)+nat(V)*1201+nat(V)*916*nat(V)+nat(V)*128*nat(V)*nat(V)+nat(V)*64*nat(V)*nat(V/2)+nat(V)*224*nat(V/2)+nat(nat(V1)+ -1)*18*nat(V1/2)+nat(nat(V)+ -1)*16*nat(V/2)+nat(V1/2)*90+nat(V/2)*80 Asymptotic class: n^3 * Total analysis performed in 5421 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: sub(0', 0') -> 0' sub(s(x), 0') -> s(x) sub(0', s(x)) -> 0' sub(s(x), s(y)) -> sub(x, y) zero(nil) -> zero2(0', nil) zero(cons(x, xs)) -> zero2(sub(x, x), cons(x, xs)) zero2(0', nil) -> nil zero2(0', cons(x, xs)) -> cons(sub(x, x), zero(xs)) zero2(s(y), nil) -> zero(nil) zero2(s(y), cons(x, xs)) -> zero(cons(x, xs)) The (relative) TRS S consists of the following rules: encArg(0') -> 0' encArg(s(x_1)) -> s(encArg(x_1)) encArg(nil) -> nil encArg(cons(x_1, x_2)) -> cons(encArg(x_1), encArg(x_2)) encArg(cons_sub(x_1, x_2)) -> sub(encArg(x_1), encArg(x_2)) encArg(cons_zero(x_1)) -> zero(encArg(x_1)) encArg(cons_zero2(x_1, x_2)) -> zero2(encArg(x_1), encArg(x_2)) encode_sub(x_1, x_2) -> sub(encArg(x_1), encArg(x_2)) encode_0 -> 0' encode_s(x_1) -> s(encArg(x_1)) encode_zero(x_1) -> zero(encArg(x_1)) encode_nil -> nil encode_zero2(x_1, x_2) -> zero2(encArg(x_1), encArg(x_2)) encode_cons(x_1, x_2) -> cons(encArg(x_1), encArg(x_2)) Rewrite Strategy: INNERMOST ---------------------------------------- (17) TypeInferenceProof (BOTH BOUNDS(ID, ID)) Infered types. ---------------------------------------- (18) Obligation: Innermost TRS: Rules: sub(0', 0') -> 0' sub(s(x), 0') -> s(x) sub(0', s(x)) -> 0' sub(s(x), s(y)) -> sub(x, y) zero(nil) -> zero2(0', nil) zero(cons(x, xs)) -> zero2(sub(x, x), cons(x, xs)) zero2(0', nil) -> nil zero2(0', cons(x, xs)) -> cons(sub(x, x), zero(xs)) zero2(s(y), nil) -> zero(nil) zero2(s(y), cons(x, xs)) -> zero(cons(x, xs)) encArg(0') -> 0' encArg(s(x_1)) -> s(encArg(x_1)) encArg(nil) -> nil encArg(cons(x_1, x_2)) -> cons(encArg(x_1), encArg(x_2)) encArg(cons_sub(x_1, x_2)) -> sub(encArg(x_1), encArg(x_2)) encArg(cons_zero(x_1)) -> zero(encArg(x_1)) encArg(cons_zero2(x_1, x_2)) -> zero2(encArg(x_1), encArg(x_2)) encode_sub(x_1, x_2) -> sub(encArg(x_1), encArg(x_2)) encode_0 -> 0' encode_s(x_1) -> s(encArg(x_1)) encode_zero(x_1) -> zero(encArg(x_1)) encode_nil -> nil encode_zero2(x_1, x_2) -> zero2(encArg(x_1), encArg(x_2)) encode_cons(x_1, x_2) -> cons(encArg(x_1), encArg(x_2)) Types: sub :: 0':s:nil:cons:cons_sub:cons_zero:cons_zero2 -> 0':s:nil:cons:cons_sub:cons_zero:cons_zero2 -> 0':s:nil:cons:cons_sub:cons_zero:cons_zero2 0' :: 0':s:nil:cons:cons_sub:cons_zero:cons_zero2 s :: 0':s:nil:cons:cons_sub:cons_zero:cons_zero2 -> 0':s:nil:cons:cons_sub:cons_zero:cons_zero2 zero :: 0':s:nil:cons:cons_sub:cons_zero:cons_zero2 -> 0':s:nil:cons:cons_sub:cons_zero:cons_zero2 nil :: 0':s:nil:cons:cons_sub:cons_zero:cons_zero2 zero2 :: 0':s:nil:cons:cons_sub:cons_zero:cons_zero2 -> 0':s:nil:cons:cons_sub:cons_zero:cons_zero2 -> 0':s:nil:cons:cons_sub:cons_zero:cons_zero2 cons :: 0':s:nil:cons:cons_sub:cons_zero:cons_zero2 -> 0':s:nil:cons:cons_sub:cons_zero:cons_zero2 -> 0':s:nil:cons:cons_sub:cons_zero:cons_zero2 encArg :: 0':s:nil:cons:cons_sub:cons_zero:cons_zero2 -> 0':s:nil:cons:cons_sub:cons_zero:cons_zero2 cons_sub :: 0':s:nil:cons:cons_sub:cons_zero:cons_zero2 -> 0':s:nil:cons:cons_sub:cons_zero:cons_zero2 -> 0':s:nil:cons:cons_sub:cons_zero:cons_zero2 cons_zero :: 0':s:nil:cons:cons_sub:cons_zero:cons_zero2 -> 0':s:nil:cons:cons_sub:cons_zero:cons_zero2 cons_zero2 :: 0':s:nil:cons:cons_sub:cons_zero:cons_zero2 -> 0':s:nil:cons:cons_sub:cons_zero:cons_zero2 -> 0':s:nil:cons:cons_sub:cons_zero:cons_zero2 encode_sub :: 0':s:nil:cons:cons_sub:cons_zero:cons_zero2 -> 0':s:nil:cons:cons_sub:cons_zero:cons_zero2 -> 0':s:nil:cons:cons_sub:cons_zero:cons_zero2 encode_0 :: 0':s:nil:cons:cons_sub:cons_zero:cons_zero2 encode_s :: 0':s:nil:cons:cons_sub:cons_zero:cons_zero2 -> 0':s:nil:cons:cons_sub:cons_zero:cons_zero2 encode_zero :: 0':s:nil:cons:cons_sub:cons_zero:cons_zero2 -> 0':s:nil:cons:cons_sub:cons_zero:cons_zero2 encode_nil :: 0':s:nil:cons:cons_sub:cons_zero:cons_zero2 encode_zero2 :: 0':s:nil:cons:cons_sub:cons_zero:cons_zero2 -> 0':s:nil:cons:cons_sub:cons_zero:cons_zero2 -> 0':s:nil:cons:cons_sub:cons_zero:cons_zero2 encode_cons :: 0':s:nil:cons:cons_sub:cons_zero:cons_zero2 -> 0':s:nil:cons:cons_sub:cons_zero:cons_zero2 -> 0':s:nil:cons:cons_sub:cons_zero:cons_zero2 hole_0':s:nil:cons:cons_sub:cons_zero:cons_zero21_3 :: 0':s:nil:cons:cons_sub:cons_zero:cons_zero2 gen_0':s:nil:cons:cons_sub:cons_zero:cons_zero22_3 :: Nat -> 0':s:nil:cons:cons_sub:cons_zero:cons_zero2 ---------------------------------------- (19) OrderProof (LOWER BOUND(ID)) Heuristically decided to analyse the following defined symbols: sub, zero, zero2, encArg They will be analysed ascendingly in the following order: sub < zero sub < zero2 sub < encArg zero = zero2 zero < encArg zero2 < encArg ---------------------------------------- (20) Obligation: Innermost TRS: Rules: sub(0', 0') -> 0' sub(s(x), 0') -> s(x) sub(0', s(x)) -> 0' sub(s(x), s(y)) -> sub(x, y) zero(nil) -> zero2(0', nil) zero(cons(x, xs)) -> zero2(sub(x, x), cons(x, xs)) zero2(0', nil) -> nil zero2(0', cons(x, xs)) -> cons(sub(x, x), zero(xs)) zero2(s(y), nil) -> zero(nil) zero2(s(y), cons(x, xs)) -> zero(cons(x, xs)) encArg(0') -> 0' encArg(s(x_1)) -> s(encArg(x_1)) encArg(nil) -> nil encArg(cons(x_1, x_2)) -> cons(encArg(x_1), encArg(x_2)) encArg(cons_sub(x_1, x_2)) -> sub(encArg(x_1), encArg(x_2)) encArg(cons_zero(x_1)) -> zero(encArg(x_1)) encArg(cons_zero2(x_1, x_2)) -> zero2(encArg(x_1), encArg(x_2)) encode_sub(x_1, x_2) -> sub(encArg(x_1), encArg(x_2)) encode_0 -> 0' encode_s(x_1) -> s(encArg(x_1)) encode_zero(x_1) -> zero(encArg(x_1)) encode_nil -> nil encode_zero2(x_1, x_2) -> zero2(encArg(x_1), encArg(x_2)) encode_cons(x_1, x_2) -> cons(encArg(x_1), encArg(x_2)) Types: sub :: 0':s:nil:cons:cons_sub:cons_zero:cons_zero2 -> 0':s:nil:cons:cons_sub:cons_zero:cons_zero2 -> 0':s:nil:cons:cons_sub:cons_zero:cons_zero2 0' :: 0':s:nil:cons:cons_sub:cons_zero:cons_zero2 s :: 0':s:nil:cons:cons_sub:cons_zero:cons_zero2 -> 0':s:nil:cons:cons_sub:cons_zero:cons_zero2 zero :: 0':s:nil:cons:cons_sub:cons_zero:cons_zero2 -> 0':s:nil:cons:cons_sub:cons_zero:cons_zero2 nil :: 0':s:nil:cons:cons_sub:cons_zero:cons_zero2 zero2 :: 0':s:nil:cons:cons_sub:cons_zero:cons_zero2 -> 0':s:nil:cons:cons_sub:cons_zero:cons_zero2 -> 0':s:nil:cons:cons_sub:cons_zero:cons_zero2 cons :: 0':s:nil:cons:cons_sub:cons_zero:cons_zero2 -> 0':s:nil:cons:cons_sub:cons_zero:cons_zero2 -> 0':s:nil:cons:cons_sub:cons_zero:cons_zero2 encArg :: 0':s:nil:cons:cons_sub:cons_zero:cons_zero2 -> 0':s:nil:cons:cons_sub:cons_zero:cons_zero2 cons_sub :: 0':s:nil:cons:cons_sub:cons_zero:cons_zero2 -> 0':s:nil:cons:cons_sub:cons_zero:cons_zero2 -> 0':s:nil:cons:cons_sub:cons_zero:cons_zero2 cons_zero :: 0':s:nil:cons:cons_sub:cons_zero:cons_zero2 -> 0':s:nil:cons:cons_sub:cons_zero:cons_zero2 cons_zero2 :: 0':s:nil:cons:cons_sub:cons_zero:cons_zero2 -> 0':s:nil:cons:cons_sub:cons_zero:cons_zero2 -> 0':s:nil:cons:cons_sub:cons_zero:cons_zero2 encode_sub :: 0':s:nil:cons:cons_sub:cons_zero:cons_zero2 -> 0':s:nil:cons:cons_sub:cons_zero:cons_zero2 -> 0':s:nil:cons:cons_sub:cons_zero:cons_zero2 encode_0 :: 0':s:nil:cons:cons_sub:cons_zero:cons_zero2 encode_s :: 0':s:nil:cons:cons_sub:cons_zero:cons_zero2 -> 0':s:nil:cons:cons_sub:cons_zero:cons_zero2 encode_zero :: 0':s:nil:cons:cons_sub:cons_zero:cons_zero2 -> 0':s:nil:cons:cons_sub:cons_zero:cons_zero2 encode_nil :: 0':s:nil:cons:cons_sub:cons_zero:cons_zero2 encode_zero2 :: 0':s:nil:cons:cons_sub:cons_zero:cons_zero2 -> 0':s:nil:cons:cons_sub:cons_zero:cons_zero2 -> 0':s:nil:cons:cons_sub:cons_zero:cons_zero2 encode_cons :: 0':s:nil:cons:cons_sub:cons_zero:cons_zero2 -> 0':s:nil:cons:cons_sub:cons_zero:cons_zero2 -> 0':s:nil:cons:cons_sub:cons_zero:cons_zero2 hole_0':s:nil:cons:cons_sub:cons_zero:cons_zero21_3 :: 0':s:nil:cons:cons_sub:cons_zero:cons_zero2 gen_0':s:nil:cons:cons_sub:cons_zero:cons_zero22_3 :: Nat -> 0':s:nil:cons:cons_sub:cons_zero:cons_zero2 Generator Equations: gen_0':s:nil:cons:cons_sub:cons_zero:cons_zero22_3(0) <=> 0' gen_0':s:nil:cons:cons_sub:cons_zero:cons_zero22_3(+(x, 1)) <=> s(gen_0':s:nil:cons:cons_sub:cons_zero:cons_zero22_3(x)) The following defined symbols remain to be analysed: sub, zero, zero2, encArg They will be analysed ascendingly in the following order: sub < zero sub < zero2 sub < encArg zero = zero2 zero < encArg zero2 < encArg ---------------------------------------- (21) RewriteLemmaProof (LOWER BOUND(ID)) Proved the following rewrite lemma: sub(gen_0':s:nil:cons:cons_sub:cons_zero:cons_zero22_3(n4_3), gen_0':s:nil:cons:cons_sub:cons_zero:cons_zero22_3(n4_3)) -> gen_0':s:nil:cons:cons_sub:cons_zero:cons_zero22_3(0), rt in Omega(1 + n4_3) Induction Base: sub(gen_0':s:nil:cons:cons_sub:cons_zero:cons_zero22_3(0), gen_0':s:nil:cons:cons_sub:cons_zero:cons_zero22_3(0)) ->_R^Omega(1) 0' Induction Step: sub(gen_0':s:nil:cons:cons_sub:cons_zero:cons_zero22_3(+(n4_3, 1)), gen_0':s:nil:cons:cons_sub:cons_zero:cons_zero22_3(+(n4_3, 1))) ->_R^Omega(1) sub(gen_0':s:nil:cons:cons_sub:cons_zero:cons_zero22_3(n4_3), gen_0':s:nil:cons:cons_sub:cons_zero:cons_zero22_3(n4_3)) ->_IH gen_0':s:nil:cons:cons_sub:cons_zero:cons_zero22_3(0) 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: sub(0', 0') -> 0' sub(s(x), 0') -> s(x) sub(0', s(x)) -> 0' sub(s(x), s(y)) -> sub(x, y) zero(nil) -> zero2(0', nil) zero(cons(x, xs)) -> zero2(sub(x, x), cons(x, xs)) zero2(0', nil) -> nil zero2(0', cons(x, xs)) -> cons(sub(x, x), zero(xs)) zero2(s(y), nil) -> zero(nil) zero2(s(y), cons(x, xs)) -> zero(cons(x, xs)) encArg(0') -> 0' encArg(s(x_1)) -> s(encArg(x_1)) encArg(nil) -> nil encArg(cons(x_1, x_2)) -> cons(encArg(x_1), encArg(x_2)) encArg(cons_sub(x_1, x_2)) -> sub(encArg(x_1), encArg(x_2)) encArg(cons_zero(x_1)) -> zero(encArg(x_1)) encArg(cons_zero2(x_1, x_2)) -> zero2(encArg(x_1), encArg(x_2)) encode_sub(x_1, x_2) -> sub(encArg(x_1), encArg(x_2)) encode_0 -> 0' encode_s(x_1) -> s(encArg(x_1)) encode_zero(x_1) -> zero(encArg(x_1)) encode_nil -> nil encode_zero2(x_1, x_2) -> zero2(encArg(x_1), encArg(x_2)) encode_cons(x_1, x_2) -> cons(encArg(x_1), encArg(x_2)) Types: sub :: 0':s:nil:cons:cons_sub:cons_zero:cons_zero2 -> 0':s:nil:cons:cons_sub:cons_zero:cons_zero2 -> 0':s:nil:cons:cons_sub:cons_zero:cons_zero2 0' :: 0':s:nil:cons:cons_sub:cons_zero:cons_zero2 s :: 0':s:nil:cons:cons_sub:cons_zero:cons_zero2 -> 0':s:nil:cons:cons_sub:cons_zero:cons_zero2 zero :: 0':s:nil:cons:cons_sub:cons_zero:cons_zero2 -> 0':s:nil:cons:cons_sub:cons_zero:cons_zero2 nil :: 0':s:nil:cons:cons_sub:cons_zero:cons_zero2 zero2 :: 0':s:nil:cons:cons_sub:cons_zero:cons_zero2 -> 0':s:nil:cons:cons_sub:cons_zero:cons_zero2 -> 0':s:nil:cons:cons_sub:cons_zero:cons_zero2 cons :: 0':s:nil:cons:cons_sub:cons_zero:cons_zero2 -> 0':s:nil:cons:cons_sub:cons_zero:cons_zero2 -> 0':s:nil:cons:cons_sub:cons_zero:cons_zero2 encArg :: 0':s:nil:cons:cons_sub:cons_zero:cons_zero2 -> 0':s:nil:cons:cons_sub:cons_zero:cons_zero2 cons_sub :: 0':s:nil:cons:cons_sub:cons_zero:cons_zero2 -> 0':s:nil:cons:cons_sub:cons_zero:cons_zero2 -> 0':s:nil:cons:cons_sub:cons_zero:cons_zero2 cons_zero :: 0':s:nil:cons:cons_sub:cons_zero:cons_zero2 -> 0':s:nil:cons:cons_sub:cons_zero:cons_zero2 cons_zero2 :: 0':s:nil:cons:cons_sub:cons_zero:cons_zero2 -> 0':s:nil:cons:cons_sub:cons_zero:cons_zero2 -> 0':s:nil:cons:cons_sub:cons_zero:cons_zero2 encode_sub :: 0':s:nil:cons:cons_sub:cons_zero:cons_zero2 -> 0':s:nil:cons:cons_sub:cons_zero:cons_zero2 -> 0':s:nil:cons:cons_sub:cons_zero:cons_zero2 encode_0 :: 0':s:nil:cons:cons_sub:cons_zero:cons_zero2 encode_s :: 0':s:nil:cons:cons_sub:cons_zero:cons_zero2 -> 0':s:nil:cons:cons_sub:cons_zero:cons_zero2 encode_zero :: 0':s:nil:cons:cons_sub:cons_zero:cons_zero2 -> 0':s:nil:cons:cons_sub:cons_zero:cons_zero2 encode_nil :: 0':s:nil:cons:cons_sub:cons_zero:cons_zero2 encode_zero2 :: 0':s:nil:cons:cons_sub:cons_zero:cons_zero2 -> 0':s:nil:cons:cons_sub:cons_zero:cons_zero2 -> 0':s:nil:cons:cons_sub:cons_zero:cons_zero2 encode_cons :: 0':s:nil:cons:cons_sub:cons_zero:cons_zero2 -> 0':s:nil:cons:cons_sub:cons_zero:cons_zero2 -> 0':s:nil:cons:cons_sub:cons_zero:cons_zero2 hole_0':s:nil:cons:cons_sub:cons_zero:cons_zero21_3 :: 0':s:nil:cons:cons_sub:cons_zero:cons_zero2 gen_0':s:nil:cons:cons_sub:cons_zero:cons_zero22_3 :: Nat -> 0':s:nil:cons:cons_sub:cons_zero:cons_zero2 Generator Equations: gen_0':s:nil:cons:cons_sub:cons_zero:cons_zero22_3(0) <=> 0' gen_0':s:nil:cons:cons_sub:cons_zero:cons_zero22_3(+(x, 1)) <=> s(gen_0':s:nil:cons:cons_sub:cons_zero:cons_zero22_3(x)) The following defined symbols remain to be analysed: sub, zero, zero2, encArg They will be analysed ascendingly in the following order: sub < zero sub < zero2 sub < encArg zero = zero2 zero < encArg zero2 < encArg ---------------------------------------- (24) LowerBoundPropagationProof (FINISHED) Propagated lower bound. ---------------------------------------- (25) BOUNDS(n^1, INF) ---------------------------------------- (26) Obligation: Innermost TRS: Rules: sub(0', 0') -> 0' sub(s(x), 0') -> s(x) sub(0', s(x)) -> 0' sub(s(x), s(y)) -> sub(x, y) zero(nil) -> zero2(0', nil) zero(cons(x, xs)) -> zero2(sub(x, x), cons(x, xs)) zero2(0', nil) -> nil zero2(0', cons(x, xs)) -> cons(sub(x, x), zero(xs)) zero2(s(y), nil) -> zero(nil) zero2(s(y), cons(x, xs)) -> zero(cons(x, xs)) encArg(0') -> 0' encArg(s(x_1)) -> s(encArg(x_1)) encArg(nil) -> nil encArg(cons(x_1, x_2)) -> cons(encArg(x_1), encArg(x_2)) encArg(cons_sub(x_1, x_2)) -> sub(encArg(x_1), encArg(x_2)) encArg(cons_zero(x_1)) -> zero(encArg(x_1)) encArg(cons_zero2(x_1, x_2)) -> zero2(encArg(x_1), encArg(x_2)) encode_sub(x_1, x_2) -> sub(encArg(x_1), encArg(x_2)) encode_0 -> 0' encode_s(x_1) -> s(encArg(x_1)) encode_zero(x_1) -> zero(encArg(x_1)) encode_nil -> nil encode_zero2(x_1, x_2) -> zero2(encArg(x_1), encArg(x_2)) encode_cons(x_1, x_2) -> cons(encArg(x_1), encArg(x_2)) Types: sub :: 0':s:nil:cons:cons_sub:cons_zero:cons_zero2 -> 0':s:nil:cons:cons_sub:cons_zero:cons_zero2 -> 0':s:nil:cons:cons_sub:cons_zero:cons_zero2 0' :: 0':s:nil:cons:cons_sub:cons_zero:cons_zero2 s :: 0':s:nil:cons:cons_sub:cons_zero:cons_zero2 -> 0':s:nil:cons:cons_sub:cons_zero:cons_zero2 zero :: 0':s:nil:cons:cons_sub:cons_zero:cons_zero2 -> 0':s:nil:cons:cons_sub:cons_zero:cons_zero2 nil :: 0':s:nil:cons:cons_sub:cons_zero:cons_zero2 zero2 :: 0':s:nil:cons:cons_sub:cons_zero:cons_zero2 -> 0':s:nil:cons:cons_sub:cons_zero:cons_zero2 -> 0':s:nil:cons:cons_sub:cons_zero:cons_zero2 cons :: 0':s:nil:cons:cons_sub:cons_zero:cons_zero2 -> 0':s:nil:cons:cons_sub:cons_zero:cons_zero2 -> 0':s:nil:cons:cons_sub:cons_zero:cons_zero2 encArg :: 0':s:nil:cons:cons_sub:cons_zero:cons_zero2 -> 0':s:nil:cons:cons_sub:cons_zero:cons_zero2 cons_sub :: 0':s:nil:cons:cons_sub:cons_zero:cons_zero2 -> 0':s:nil:cons:cons_sub:cons_zero:cons_zero2 -> 0':s:nil:cons:cons_sub:cons_zero:cons_zero2 cons_zero :: 0':s:nil:cons:cons_sub:cons_zero:cons_zero2 -> 0':s:nil:cons:cons_sub:cons_zero:cons_zero2 cons_zero2 :: 0':s:nil:cons:cons_sub:cons_zero:cons_zero2 -> 0':s:nil:cons:cons_sub:cons_zero:cons_zero2 -> 0':s:nil:cons:cons_sub:cons_zero:cons_zero2 encode_sub :: 0':s:nil:cons:cons_sub:cons_zero:cons_zero2 -> 0':s:nil:cons:cons_sub:cons_zero:cons_zero2 -> 0':s:nil:cons:cons_sub:cons_zero:cons_zero2 encode_0 :: 0':s:nil:cons:cons_sub:cons_zero:cons_zero2 encode_s :: 0':s:nil:cons:cons_sub:cons_zero:cons_zero2 -> 0':s:nil:cons:cons_sub:cons_zero:cons_zero2 encode_zero :: 0':s:nil:cons:cons_sub:cons_zero:cons_zero2 -> 0':s:nil:cons:cons_sub:cons_zero:cons_zero2 encode_nil :: 0':s:nil:cons:cons_sub:cons_zero:cons_zero2 encode_zero2 :: 0':s:nil:cons:cons_sub:cons_zero:cons_zero2 -> 0':s:nil:cons:cons_sub:cons_zero:cons_zero2 -> 0':s:nil:cons:cons_sub:cons_zero:cons_zero2 encode_cons :: 0':s:nil:cons:cons_sub:cons_zero:cons_zero2 -> 0':s:nil:cons:cons_sub:cons_zero:cons_zero2 -> 0':s:nil:cons:cons_sub:cons_zero:cons_zero2 hole_0':s:nil:cons:cons_sub:cons_zero:cons_zero21_3 :: 0':s:nil:cons:cons_sub:cons_zero:cons_zero2 gen_0':s:nil:cons:cons_sub:cons_zero:cons_zero22_3 :: Nat -> 0':s:nil:cons:cons_sub:cons_zero:cons_zero2 Lemmas: sub(gen_0':s:nil:cons:cons_sub:cons_zero:cons_zero22_3(n4_3), gen_0':s:nil:cons:cons_sub:cons_zero:cons_zero22_3(n4_3)) -> gen_0':s:nil:cons:cons_sub:cons_zero:cons_zero22_3(0), rt in Omega(1 + n4_3) Generator Equations: gen_0':s:nil:cons:cons_sub:cons_zero:cons_zero22_3(0) <=> 0' gen_0':s:nil:cons:cons_sub:cons_zero:cons_zero22_3(+(x, 1)) <=> s(gen_0':s:nil:cons:cons_sub:cons_zero:cons_zero22_3(x)) The following defined symbols remain to be analysed: zero2, zero, encArg They will be analysed ascendingly in the following order: zero = zero2 zero < encArg zero2 < encArg ---------------------------------------- (27) RewriteLemmaProof (LOWER BOUND(ID)) Proved the following rewrite lemma: encArg(gen_0':s:nil:cons:cons_sub:cons_zero:cons_zero22_3(n942_3)) -> gen_0':s:nil:cons:cons_sub:cons_zero:cons_zero22_3(n942_3), rt in Omega(0) Induction Base: encArg(gen_0':s:nil:cons:cons_sub:cons_zero:cons_zero22_3(0)) ->_R^Omega(0) 0' Induction Step: encArg(gen_0':s:nil:cons:cons_sub:cons_zero:cons_zero22_3(+(n942_3, 1))) ->_R^Omega(0) s(encArg(gen_0':s:nil:cons:cons_sub:cons_zero:cons_zero22_3(n942_3))) ->_IH s(gen_0':s:nil:cons:cons_sub:cons_zero:cons_zero22_3(c943_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)