/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^2)) 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^2). (0) DCpxTrs (1) DerivationalComplexityToRuntimeComplexityProof [BOTH BOUNDS(ID, ID), 0 ms] (2) CpxRelTRS (3) SInnermostTerminationProof [BOTH CONCRETE BOUNDS(ID, ID), 189 ms] (4) CpxRelTRS (5) RelTrsToWeightedTrsProof [BOTH BOUNDS(ID, ID), 0 ms] (6) CpxWeightedTrs (7) CpxWeightedTrsRenamingProof [BOTH BOUNDS(ID, ID), 0 ms] (8) CpxWeightedTrs (9) TypeInferenceProof [BOTH BOUNDS(ID, ID), 0 ms] (10) CpxTypedWeightedTrs (11) CompletionProof [UPPER BOUND(ID), 0 ms] (12) CpxTypedWeightedCompleteTrs (13) CpxTypedWeightedTrsToRntsProof [UPPER BOUND(ID), 0 ms] (14) CpxRNTS (15) CompleteCoflocoProof [FINISHED, 13.2 s] (16) BOUNDS(1, n^2) (17) RenamingProof [BOTH BOUNDS(ID, ID), 0 ms] (18) CpxRelTRS (19) TypeInferenceProof [BOTH BOUNDS(ID, ID), 0 ms] (20) typed CpxTrs (21) OrderProof [LOWER BOUND(ID), 0 ms] (22) typed CpxTrs (23) RewriteLemmaProof [LOWER BOUND(ID), 308 ms] (24) BEST (25) proven lower bound (26) LowerBoundPropagationProof [FINISHED, 0 ms] (27) BOUNDS(n^1, INF) (28) typed CpxTrs (29) RewriteLemmaProof [LOWER BOUND(ID), 71 ms] (30) typed CpxTrs (31) RewriteLemmaProof [LOWER BOUND(ID), 124 ms] (32) BOUNDS(1, INF) ---------------------------------------- (0) Obligation: The Derivational Complexity (innermost) of the given DCpxTrs could be proven to be BOUNDS(n^1, n^2). The TRS R consists of the following rules: -(x, 0) -> x -(0, s(y)) -> 0 -(s(x), s(y)) -> -(x, y) lt(x, 0) -> false lt(0, s(y)) -> true lt(s(x), s(y)) -> lt(x, y) if(true, x, y) -> x if(false, x, y) -> y div(x, 0) -> 0 div(0, y) -> 0 div(s(x), s(y)) -> if(lt(x, y), 0, s(div(-(x, y), s(y)))) 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(false) -> false encArg(true) -> true encArg(cons_-(x_1, x_2)) -> -(encArg(x_1), encArg(x_2)) encArg(cons_lt(x_1, x_2)) -> lt(encArg(x_1), encArg(x_2)) encArg(cons_if(x_1, x_2, x_3)) -> if(encArg(x_1), encArg(x_2), encArg(x_3)) encArg(cons_div(x_1, x_2)) -> div(encArg(x_1), encArg(x_2)) encode_-(x_1, x_2) -> -(encArg(x_1), encArg(x_2)) encode_0 -> 0 encode_s(x_1) -> s(encArg(x_1)) encode_lt(x_1, x_2) -> lt(encArg(x_1), encArg(x_2)) encode_false -> false encode_true -> true encode_if(x_1, x_2, x_3) -> if(encArg(x_1), encArg(x_2), encArg(x_3)) encode_div(x_1, x_2) -> div(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^2). The TRS R consists of the following rules: -(x, 0) -> x -(0, s(y)) -> 0 -(s(x), s(y)) -> -(x, y) lt(x, 0) -> false lt(0, s(y)) -> true lt(s(x), s(y)) -> lt(x, y) if(true, x, y) -> x if(false, x, y) -> y div(x, 0) -> 0 div(0, y) -> 0 div(s(x), s(y)) -> if(lt(x, y), 0, s(div(-(x, y), s(y)))) The (relative) TRS S consists of the following rules: encArg(0) -> 0 encArg(s(x_1)) -> s(encArg(x_1)) encArg(false) -> false encArg(true) -> true encArg(cons_-(x_1, x_2)) -> -(encArg(x_1), encArg(x_2)) encArg(cons_lt(x_1, x_2)) -> lt(encArg(x_1), encArg(x_2)) encArg(cons_if(x_1, x_2, x_3)) -> if(encArg(x_1), encArg(x_2), encArg(x_3)) encArg(cons_div(x_1, x_2)) -> div(encArg(x_1), encArg(x_2)) encode_-(x_1, x_2) -> -(encArg(x_1), encArg(x_2)) encode_0 -> 0 encode_s(x_1) -> s(encArg(x_1)) encode_lt(x_1, x_2) -> lt(encArg(x_1), encArg(x_2)) encode_false -> false encode_true -> true encode_if(x_1, x_2, x_3) -> if(encArg(x_1), encArg(x_2), encArg(x_3)) encode_div(x_1, x_2) -> div(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^2). The TRS R consists of the following rules: -(x, 0) -> x -(0, s(y)) -> 0 -(s(x), s(y)) -> -(x, y) lt(x, 0) -> false lt(0, s(y)) -> true lt(s(x), s(y)) -> lt(x, y) if(true, x, y) -> x if(false, x, y) -> y div(x, 0) -> 0 div(0, y) -> 0 div(s(x), s(y)) -> if(lt(x, y), 0, s(div(-(x, y), s(y)))) The (relative) TRS S consists of the following rules: encArg(0) -> 0 encArg(s(x_1)) -> s(encArg(x_1)) encArg(false) -> false encArg(true) -> true encArg(cons_-(x_1, x_2)) -> -(encArg(x_1), encArg(x_2)) encArg(cons_lt(x_1, x_2)) -> lt(encArg(x_1), encArg(x_2)) encArg(cons_if(x_1, x_2, x_3)) -> if(encArg(x_1), encArg(x_2), encArg(x_3)) encArg(cons_div(x_1, x_2)) -> div(encArg(x_1), encArg(x_2)) encode_-(x_1, x_2) -> -(encArg(x_1), encArg(x_2)) encode_0 -> 0 encode_s(x_1) -> s(encArg(x_1)) encode_lt(x_1, x_2) -> lt(encArg(x_1), encArg(x_2)) encode_false -> false encode_true -> true encode_if(x_1, x_2, x_3) -> if(encArg(x_1), encArg(x_2), encArg(x_3)) encode_div(x_1, x_2) -> div(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^2). The TRS R consists of the following rules: -(x, 0) -> x [1] -(0, s(y)) -> 0 [1] -(s(x), s(y)) -> -(x, y) [1] lt(x, 0) -> false [1] lt(0, s(y)) -> true [1] lt(s(x), s(y)) -> lt(x, y) [1] if(true, x, y) -> x [1] if(false, x, y) -> y [1] div(x, 0) -> 0 [1] div(0, y) -> 0 [1] div(s(x), s(y)) -> if(lt(x, y), 0, s(div(-(x, y), s(y)))) [1] encArg(0) -> 0 [0] encArg(s(x_1)) -> s(encArg(x_1)) [0] encArg(false) -> false [0] encArg(true) -> true [0] encArg(cons_-(x_1, x_2)) -> -(encArg(x_1), encArg(x_2)) [0] encArg(cons_lt(x_1, x_2)) -> lt(encArg(x_1), encArg(x_2)) [0] encArg(cons_if(x_1, x_2, x_3)) -> if(encArg(x_1), encArg(x_2), encArg(x_3)) [0] encArg(cons_div(x_1, x_2)) -> div(encArg(x_1), encArg(x_2)) [0] encode_-(x_1, x_2) -> -(encArg(x_1), encArg(x_2)) [0] encode_0 -> 0 [0] encode_s(x_1) -> s(encArg(x_1)) [0] encode_lt(x_1, x_2) -> lt(encArg(x_1), encArg(x_2)) [0] encode_false -> false [0] encode_true -> true [0] encode_if(x_1, x_2, x_3) -> if(encArg(x_1), encArg(x_2), encArg(x_3)) [0] encode_div(x_1, x_2) -> div(encArg(x_1), encArg(x_2)) [0] Rewrite Strategy: INNERMOST ---------------------------------------- (7) CpxWeightedTrsRenamingProof (BOTH BOUNDS(ID, ID)) Renamed defined symbols to avoid conflicts with arithmetic symbols: - => minus ---------------------------------------- (8) Obligation: The Runtime Complexity (innermost) of the given CpxWeightedTrs could be proven to be BOUNDS(1, n^2). The TRS R consists of the following rules: minus(x, 0) -> x [1] minus(0, s(y)) -> 0 [1] minus(s(x), s(y)) -> minus(x, y) [1] lt(x, 0) -> false [1] lt(0, s(y)) -> true [1] lt(s(x), s(y)) -> lt(x, y) [1] if(true, x, y) -> x [1] if(false, x, y) -> y [1] div(x, 0) -> 0 [1] div(0, y) -> 0 [1] div(s(x), s(y)) -> if(lt(x, y), 0, s(div(minus(x, y), s(y)))) [1] encArg(0) -> 0 [0] encArg(s(x_1)) -> s(encArg(x_1)) [0] encArg(false) -> false [0] encArg(true) -> true [0] encArg(cons_-(x_1, x_2)) -> minus(encArg(x_1), encArg(x_2)) [0] encArg(cons_lt(x_1, x_2)) -> lt(encArg(x_1), encArg(x_2)) [0] encArg(cons_if(x_1, x_2, x_3)) -> if(encArg(x_1), encArg(x_2), encArg(x_3)) [0] encArg(cons_div(x_1, x_2)) -> div(encArg(x_1), encArg(x_2)) [0] encode_-(x_1, x_2) -> minus(encArg(x_1), encArg(x_2)) [0] encode_0 -> 0 [0] encode_s(x_1) -> s(encArg(x_1)) [0] encode_lt(x_1, x_2) -> lt(encArg(x_1), encArg(x_2)) [0] encode_false -> false [0] encode_true -> true [0] encode_if(x_1, x_2, x_3) -> if(encArg(x_1), encArg(x_2), encArg(x_3)) [0] encode_div(x_1, x_2) -> div(encArg(x_1), encArg(x_2)) [0] Rewrite Strategy: INNERMOST ---------------------------------------- (9) TypeInferenceProof (BOTH BOUNDS(ID, ID)) Infered types. ---------------------------------------- (10) Obligation: Runtime Complexity Weighted TRS with Types. The TRS R consists of the following rules: minus(x, 0) -> x [1] minus(0, s(y)) -> 0 [1] minus(s(x), s(y)) -> minus(x, y) [1] lt(x, 0) -> false [1] lt(0, s(y)) -> true [1] lt(s(x), s(y)) -> lt(x, y) [1] if(true, x, y) -> x [1] if(false, x, y) -> y [1] div(x, 0) -> 0 [1] div(0, y) -> 0 [1] div(s(x), s(y)) -> if(lt(x, y), 0, s(div(minus(x, y), s(y)))) [1] encArg(0) -> 0 [0] encArg(s(x_1)) -> s(encArg(x_1)) [0] encArg(false) -> false [0] encArg(true) -> true [0] encArg(cons_-(x_1, x_2)) -> minus(encArg(x_1), encArg(x_2)) [0] encArg(cons_lt(x_1, x_2)) -> lt(encArg(x_1), encArg(x_2)) [0] encArg(cons_if(x_1, x_2, x_3)) -> if(encArg(x_1), encArg(x_2), encArg(x_3)) [0] encArg(cons_div(x_1, x_2)) -> div(encArg(x_1), encArg(x_2)) [0] encode_-(x_1, x_2) -> minus(encArg(x_1), encArg(x_2)) [0] encode_0 -> 0 [0] encode_s(x_1) -> s(encArg(x_1)) [0] encode_lt(x_1, x_2) -> lt(encArg(x_1), encArg(x_2)) [0] encode_false -> false [0] encode_true -> true [0] encode_if(x_1, x_2, x_3) -> if(encArg(x_1), encArg(x_2), encArg(x_3)) [0] encode_div(x_1, x_2) -> div(encArg(x_1), encArg(x_2)) [0] The TRS has the following type information: minus :: 0:s:false:true:cons_-:cons_lt:cons_if:cons_div -> 0:s:false:true:cons_-:cons_lt:cons_if:cons_div -> 0:s:false:true:cons_-:cons_lt:cons_if:cons_div 0 :: 0:s:false:true:cons_-:cons_lt:cons_if:cons_div s :: 0:s:false:true:cons_-:cons_lt:cons_if:cons_div -> 0:s:false:true:cons_-:cons_lt:cons_if:cons_div lt :: 0:s:false:true:cons_-:cons_lt:cons_if:cons_div -> 0:s:false:true:cons_-:cons_lt:cons_if:cons_div -> 0:s:false:true:cons_-:cons_lt:cons_if:cons_div false :: 0:s:false:true:cons_-:cons_lt:cons_if:cons_div true :: 0:s:false:true:cons_-:cons_lt:cons_if:cons_div if :: 0:s:false:true:cons_-:cons_lt:cons_if:cons_div -> 0:s:false:true:cons_-:cons_lt:cons_if:cons_div -> 0:s:false:true:cons_-:cons_lt:cons_if:cons_div -> 0:s:false:true:cons_-:cons_lt:cons_if:cons_div div :: 0:s:false:true:cons_-:cons_lt:cons_if:cons_div -> 0:s:false:true:cons_-:cons_lt:cons_if:cons_div -> 0:s:false:true:cons_-:cons_lt:cons_if:cons_div encArg :: 0:s:false:true:cons_-:cons_lt:cons_if:cons_div -> 0:s:false:true:cons_-:cons_lt:cons_if:cons_div cons_- :: 0:s:false:true:cons_-:cons_lt:cons_if:cons_div -> 0:s:false:true:cons_-:cons_lt:cons_if:cons_div -> 0:s:false:true:cons_-:cons_lt:cons_if:cons_div cons_lt :: 0:s:false:true:cons_-:cons_lt:cons_if:cons_div -> 0:s:false:true:cons_-:cons_lt:cons_if:cons_div -> 0:s:false:true:cons_-:cons_lt:cons_if:cons_div cons_if :: 0:s:false:true:cons_-:cons_lt:cons_if:cons_div -> 0:s:false:true:cons_-:cons_lt:cons_if:cons_div -> 0:s:false:true:cons_-:cons_lt:cons_if:cons_div -> 0:s:false:true:cons_-:cons_lt:cons_if:cons_div cons_div :: 0:s:false:true:cons_-:cons_lt:cons_if:cons_div -> 0:s:false:true:cons_-:cons_lt:cons_if:cons_div -> 0:s:false:true:cons_-:cons_lt:cons_if:cons_div encode_- :: 0:s:false:true:cons_-:cons_lt:cons_if:cons_div -> 0:s:false:true:cons_-:cons_lt:cons_if:cons_div -> 0:s:false:true:cons_-:cons_lt:cons_if:cons_div encode_0 :: 0:s:false:true:cons_-:cons_lt:cons_if:cons_div encode_s :: 0:s:false:true:cons_-:cons_lt:cons_if:cons_div -> 0:s:false:true:cons_-:cons_lt:cons_if:cons_div encode_lt :: 0:s:false:true:cons_-:cons_lt:cons_if:cons_div -> 0:s:false:true:cons_-:cons_lt:cons_if:cons_div -> 0:s:false:true:cons_-:cons_lt:cons_if:cons_div encode_false :: 0:s:false:true:cons_-:cons_lt:cons_if:cons_div encode_true :: 0:s:false:true:cons_-:cons_lt:cons_if:cons_div encode_if :: 0:s:false:true:cons_-:cons_lt:cons_if:cons_div -> 0:s:false:true:cons_-:cons_lt:cons_if:cons_div -> 0:s:false:true:cons_-:cons_lt:cons_if:cons_div -> 0:s:false:true:cons_-:cons_lt:cons_if:cons_div encode_div :: 0:s:false:true:cons_-:cons_lt:cons_if:cons_div -> 0:s:false:true:cons_-:cons_lt:cons_if:cons_div -> 0:s:false:true:cons_-:cons_lt:cons_if:cons_div Rewrite Strategy: INNERMOST ---------------------------------------- (11) 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_-(v0, v1) -> null_encode_- [0] encode_0 -> null_encode_0 [0] encode_s(v0) -> null_encode_s [0] encode_lt(v0, v1) -> null_encode_lt [0] encode_false -> null_encode_false [0] encode_true -> null_encode_true [0] encode_if(v0, v1, v2) -> null_encode_if [0] encode_div(v0, v1) -> null_encode_div [0] minus(v0, v1) -> null_minus [0] lt(v0, v1) -> null_lt [0] if(v0, v1, v2) -> null_if [0] div(v0, v1) -> null_div [0] And the following fresh constants: null_encArg, null_encode_-, null_encode_0, null_encode_s, null_encode_lt, null_encode_false, null_encode_true, null_encode_if, null_encode_div, null_minus, null_lt, null_if, null_div ---------------------------------------- (12) Obligation: Runtime Complexity Weighted TRS where all functions are completely defined. The underlying TRS is: Runtime Complexity Weighted TRS with Types. The TRS R consists of the following rules: minus(x, 0) -> x [1] minus(0, s(y)) -> 0 [1] minus(s(x), s(y)) -> minus(x, y) [1] lt(x, 0) -> false [1] lt(0, s(y)) -> true [1] lt(s(x), s(y)) -> lt(x, y) [1] if(true, x, y) -> x [1] if(false, x, y) -> y [1] div(x, 0) -> 0 [1] div(0, y) -> 0 [1] div(s(x), s(y)) -> if(lt(x, y), 0, s(div(minus(x, y), s(y)))) [1] encArg(0) -> 0 [0] encArg(s(x_1)) -> s(encArg(x_1)) [0] encArg(false) -> false [0] encArg(true) -> true [0] encArg(cons_-(x_1, x_2)) -> minus(encArg(x_1), encArg(x_2)) [0] encArg(cons_lt(x_1, x_2)) -> lt(encArg(x_1), encArg(x_2)) [0] encArg(cons_if(x_1, x_2, x_3)) -> if(encArg(x_1), encArg(x_2), encArg(x_3)) [0] encArg(cons_div(x_1, x_2)) -> div(encArg(x_1), encArg(x_2)) [0] encode_-(x_1, x_2) -> minus(encArg(x_1), encArg(x_2)) [0] encode_0 -> 0 [0] encode_s(x_1) -> s(encArg(x_1)) [0] encode_lt(x_1, x_2) -> lt(encArg(x_1), encArg(x_2)) [0] encode_false -> false [0] encode_true -> true [0] encode_if(x_1, x_2, x_3) -> if(encArg(x_1), encArg(x_2), encArg(x_3)) [0] encode_div(x_1, x_2) -> div(encArg(x_1), encArg(x_2)) [0] encArg(v0) -> null_encArg [0] encode_-(v0, v1) -> null_encode_- [0] encode_0 -> null_encode_0 [0] encode_s(v0) -> null_encode_s [0] encode_lt(v0, v1) -> null_encode_lt [0] encode_false -> null_encode_false [0] encode_true -> null_encode_true [0] encode_if(v0, v1, v2) -> null_encode_if [0] encode_div(v0, v1) -> null_encode_div [0] minus(v0, v1) -> null_minus [0] lt(v0, v1) -> null_lt [0] if(v0, v1, v2) -> null_if [0] div(v0, v1) -> null_div [0] The TRS has the following type information: minus :: 0:s:false:true:cons_-:cons_lt:cons_if:cons_div:null_encArg:null_encode_-:null_encode_0:null_encode_s:null_encode_lt:null_encode_false:null_encode_true:null_encode_if:null_encode_div:null_minus:null_lt:null_if:null_div -> 0:s:false:true:cons_-:cons_lt:cons_if:cons_div:null_encArg:null_encode_-:null_encode_0:null_encode_s:null_encode_lt:null_encode_false:null_encode_true:null_encode_if:null_encode_div:null_minus:null_lt:null_if:null_div -> 0:s:false:true:cons_-:cons_lt:cons_if:cons_div:null_encArg:null_encode_-:null_encode_0:null_encode_s:null_encode_lt:null_encode_false:null_encode_true:null_encode_if:null_encode_div:null_minus:null_lt:null_if:null_div 0 :: 0:s:false:true:cons_-:cons_lt:cons_if:cons_div:null_encArg:null_encode_-:null_encode_0:null_encode_s:null_encode_lt:null_encode_false:null_encode_true:null_encode_if:null_encode_div:null_minus:null_lt:null_if:null_div s :: 0:s:false:true:cons_-:cons_lt:cons_if:cons_div:null_encArg:null_encode_-:null_encode_0:null_encode_s:null_encode_lt:null_encode_false:null_encode_true:null_encode_if:null_encode_div:null_minus:null_lt:null_if:null_div -> 0:s:false:true:cons_-:cons_lt:cons_if:cons_div:null_encArg:null_encode_-:null_encode_0:null_encode_s:null_encode_lt:null_encode_false:null_encode_true:null_encode_if:null_encode_div:null_minus:null_lt:null_if:null_div lt :: 0:s:false:true:cons_-:cons_lt:cons_if:cons_div:null_encArg:null_encode_-:null_encode_0:null_encode_s:null_encode_lt:null_encode_false:null_encode_true:null_encode_if:null_encode_div:null_minus:null_lt:null_if:null_div -> 0:s:false:true:cons_-:cons_lt:cons_if:cons_div:null_encArg:null_encode_-:null_encode_0:null_encode_s:null_encode_lt:null_encode_false:null_encode_true:null_encode_if:null_encode_div:null_minus:null_lt:null_if:null_div -> 0:s:false:true:cons_-:cons_lt:cons_if:cons_div:null_encArg:null_encode_-:null_encode_0:null_encode_s:null_encode_lt:null_encode_false:null_encode_true:null_encode_if:null_encode_div:null_minus:null_lt:null_if:null_div false :: 0:s:false:true:cons_-:cons_lt:cons_if:cons_div:null_encArg:null_encode_-:null_encode_0:null_encode_s:null_encode_lt:null_encode_false:null_encode_true:null_encode_if:null_encode_div:null_minus:null_lt:null_if:null_div true :: 0:s:false:true:cons_-:cons_lt:cons_if:cons_div:null_encArg:null_encode_-:null_encode_0:null_encode_s:null_encode_lt:null_encode_false:null_encode_true:null_encode_if:null_encode_div:null_minus:null_lt:null_if:null_div if :: 0:s:false:true:cons_-:cons_lt:cons_if:cons_div:null_encArg:null_encode_-:null_encode_0:null_encode_s:null_encode_lt:null_encode_false:null_encode_true:null_encode_if:null_encode_div:null_minus:null_lt:null_if:null_div -> 0:s:false:true:cons_-:cons_lt:cons_if:cons_div:null_encArg:null_encode_-:null_encode_0:null_encode_s:null_encode_lt:null_encode_false:null_encode_true:null_encode_if:null_encode_div:null_minus:null_lt:null_if:null_div -> 0:s:false:true:cons_-:cons_lt:cons_if:cons_div:null_encArg:null_encode_-:null_encode_0:null_encode_s:null_encode_lt:null_encode_false:null_encode_true:null_encode_if:null_encode_div:null_minus:null_lt:null_if:null_div -> 0:s:false:true:cons_-:cons_lt:cons_if:cons_div:null_encArg:null_encode_-:null_encode_0:null_encode_s:null_encode_lt:null_encode_false:null_encode_true:null_encode_if:null_encode_div:null_minus:null_lt:null_if:null_div div :: 0:s:false:true:cons_-:cons_lt:cons_if:cons_div:null_encArg:null_encode_-:null_encode_0:null_encode_s:null_encode_lt:null_encode_false:null_encode_true:null_encode_if:null_encode_div:null_minus:null_lt:null_if:null_div -> 0:s:false:true:cons_-:cons_lt:cons_if:cons_div:null_encArg:null_encode_-:null_encode_0:null_encode_s:null_encode_lt:null_encode_false:null_encode_true:null_encode_if:null_encode_div:null_minus:null_lt:null_if:null_div -> 0:s:false:true:cons_-:cons_lt:cons_if:cons_div:null_encArg:null_encode_-:null_encode_0:null_encode_s:null_encode_lt:null_encode_false:null_encode_true:null_encode_if:null_encode_div:null_minus:null_lt:null_if:null_div encArg :: 0:s:false:true:cons_-:cons_lt:cons_if:cons_div:null_encArg:null_encode_-:null_encode_0:null_encode_s:null_encode_lt:null_encode_false:null_encode_true:null_encode_if:null_encode_div:null_minus:null_lt:null_if:null_div -> 0:s:false:true:cons_-:cons_lt:cons_if:cons_div:null_encArg:null_encode_-:null_encode_0:null_encode_s:null_encode_lt:null_encode_false:null_encode_true:null_encode_if:null_encode_div:null_minus:null_lt:null_if:null_div cons_- :: 0:s:false:true:cons_-:cons_lt:cons_if:cons_div:null_encArg:null_encode_-:null_encode_0:null_encode_s:null_encode_lt:null_encode_false:null_encode_true:null_encode_if:null_encode_div:null_minus:null_lt:null_if:null_div -> 0:s:false:true:cons_-:cons_lt:cons_if:cons_div:null_encArg:null_encode_-:null_encode_0:null_encode_s:null_encode_lt:null_encode_false:null_encode_true:null_encode_if:null_encode_div:null_minus:null_lt:null_if:null_div -> 0:s:false:true:cons_-:cons_lt:cons_if:cons_div:null_encArg:null_encode_-:null_encode_0:null_encode_s:null_encode_lt:null_encode_false:null_encode_true:null_encode_if:null_encode_div:null_minus:null_lt:null_if:null_div cons_lt :: 0:s:false:true:cons_-:cons_lt:cons_if:cons_div:null_encArg:null_encode_-:null_encode_0:null_encode_s:null_encode_lt:null_encode_false:null_encode_true:null_encode_if:null_encode_div:null_minus:null_lt:null_if:null_div -> 0:s:false:true:cons_-:cons_lt:cons_if:cons_div:null_encArg:null_encode_-:null_encode_0:null_encode_s:null_encode_lt:null_encode_false:null_encode_true:null_encode_if:null_encode_div:null_minus:null_lt:null_if:null_div -> 0:s:false:true:cons_-:cons_lt:cons_if:cons_div:null_encArg:null_encode_-:null_encode_0:null_encode_s:null_encode_lt:null_encode_false:null_encode_true:null_encode_if:null_encode_div:null_minus:null_lt:null_if:null_div cons_if :: 0:s:false:true:cons_-:cons_lt:cons_if:cons_div:null_encArg:null_encode_-:null_encode_0:null_encode_s:null_encode_lt:null_encode_false:null_encode_true:null_encode_if:null_encode_div:null_minus:null_lt:null_if:null_div -> 0:s:false:true:cons_-:cons_lt:cons_if:cons_div:null_encArg:null_encode_-:null_encode_0:null_encode_s:null_encode_lt:null_encode_false:null_encode_true:null_encode_if:null_encode_div:null_minus:null_lt:null_if:null_div -> 0:s:false:true:cons_-:cons_lt:cons_if:cons_div:null_encArg:null_encode_-:null_encode_0:null_encode_s:null_encode_lt:null_encode_false:null_encode_true:null_encode_if:null_encode_div:null_minus:null_lt:null_if:null_div -> 0:s:false:true:cons_-:cons_lt:cons_if:cons_div:null_encArg:null_encode_-:null_encode_0:null_encode_s:null_encode_lt:null_encode_false:null_encode_true:null_encode_if:null_encode_div:null_minus:null_lt:null_if:null_div cons_div :: 0:s:false:true:cons_-:cons_lt:cons_if:cons_div:null_encArg:null_encode_-:null_encode_0:null_encode_s:null_encode_lt:null_encode_false:null_encode_true:null_encode_if:null_encode_div:null_minus:null_lt:null_if:null_div -> 0:s:false:true:cons_-:cons_lt:cons_if:cons_div:null_encArg:null_encode_-:null_encode_0:null_encode_s:null_encode_lt:null_encode_false:null_encode_true:null_encode_if:null_encode_div:null_minus:null_lt:null_if:null_div -> 0:s:false:true:cons_-:cons_lt:cons_if:cons_div:null_encArg:null_encode_-:null_encode_0:null_encode_s:null_encode_lt:null_encode_false:null_encode_true:null_encode_if:null_encode_div:null_minus:null_lt:null_if:null_div encode_- :: 0:s:false:true:cons_-:cons_lt:cons_if:cons_div:null_encArg:null_encode_-:null_encode_0:null_encode_s:null_encode_lt:null_encode_false:null_encode_true:null_encode_if:null_encode_div:null_minus:null_lt:null_if:null_div -> 0:s:false:true:cons_-:cons_lt:cons_if:cons_div:null_encArg:null_encode_-:null_encode_0:null_encode_s:null_encode_lt:null_encode_false:null_encode_true:null_encode_if:null_encode_div:null_minus:null_lt:null_if:null_div -> 0:s:false:true:cons_-:cons_lt:cons_if:cons_div:null_encArg:null_encode_-:null_encode_0:null_encode_s:null_encode_lt:null_encode_false:null_encode_true:null_encode_if:null_encode_div:null_minus:null_lt:null_if:null_div encode_0 :: 0:s:false:true:cons_-:cons_lt:cons_if:cons_div:null_encArg:null_encode_-:null_encode_0:null_encode_s:null_encode_lt:null_encode_false:null_encode_true:null_encode_if:null_encode_div:null_minus:null_lt:null_if:null_div encode_s :: 0:s:false:true:cons_-:cons_lt:cons_if:cons_div:null_encArg:null_encode_-:null_encode_0:null_encode_s:null_encode_lt:null_encode_false:null_encode_true:null_encode_if:null_encode_div:null_minus:null_lt:null_if:null_div -> 0:s:false:true:cons_-:cons_lt:cons_if:cons_div:null_encArg:null_encode_-:null_encode_0:null_encode_s:null_encode_lt:null_encode_false:null_encode_true:null_encode_if:null_encode_div:null_minus:null_lt:null_if:null_div encode_lt :: 0:s:false:true:cons_-:cons_lt:cons_if:cons_div:null_encArg:null_encode_-:null_encode_0:null_encode_s:null_encode_lt:null_encode_false:null_encode_true:null_encode_if:null_encode_div:null_minus:null_lt:null_if:null_div -> 0:s:false:true:cons_-:cons_lt:cons_if:cons_div:null_encArg:null_encode_-:null_encode_0:null_encode_s:null_encode_lt:null_encode_false:null_encode_true:null_encode_if:null_encode_div:null_minus:null_lt:null_if:null_div -> 0:s:false:true:cons_-:cons_lt:cons_if:cons_div:null_encArg:null_encode_-:null_encode_0:null_encode_s:null_encode_lt:null_encode_false:null_encode_true:null_encode_if:null_encode_div:null_minus:null_lt:null_if:null_div encode_false :: 0:s:false:true:cons_-:cons_lt:cons_if:cons_div:null_encArg:null_encode_-:null_encode_0:null_encode_s:null_encode_lt:null_encode_false:null_encode_true:null_encode_if:null_encode_div:null_minus:null_lt:null_if:null_div encode_true :: 0:s:false:true:cons_-:cons_lt:cons_if:cons_div:null_encArg:null_encode_-:null_encode_0:null_encode_s:null_encode_lt:null_encode_false:null_encode_true:null_encode_if:null_encode_div:null_minus:null_lt:null_if:null_div encode_if :: 0:s:false:true:cons_-:cons_lt:cons_if:cons_div:null_encArg:null_encode_-:null_encode_0:null_encode_s:null_encode_lt:null_encode_false:null_encode_true:null_encode_if:null_encode_div:null_minus:null_lt:null_if:null_div -> 0:s:false:true:cons_-:cons_lt:cons_if:cons_div:null_encArg:null_encode_-:null_encode_0:null_encode_s:null_encode_lt:null_encode_false:null_encode_true:null_encode_if:null_encode_div:null_minus:null_lt:null_if:null_div -> 0:s:false:true:cons_-:cons_lt:cons_if:cons_div:null_encArg:null_encode_-:null_encode_0:null_encode_s:null_encode_lt:null_encode_false:null_encode_true:null_encode_if:null_encode_div:null_minus:null_lt:null_if:null_div -> 0:s:false:true:cons_-:cons_lt:cons_if:cons_div:null_encArg:null_encode_-:null_encode_0:null_encode_s:null_encode_lt:null_encode_false:null_encode_true:null_encode_if:null_encode_div:null_minus:null_lt:null_if:null_div encode_div :: 0:s:false:true:cons_-:cons_lt:cons_if:cons_div:null_encArg:null_encode_-:null_encode_0:null_encode_s:null_encode_lt:null_encode_false:null_encode_true:null_encode_if:null_encode_div:null_minus:null_lt:null_if:null_div -> 0:s:false:true:cons_-:cons_lt:cons_if:cons_div:null_encArg:null_encode_-:null_encode_0:null_encode_s:null_encode_lt:null_encode_false:null_encode_true:null_encode_if:null_encode_div:null_minus:null_lt:null_if:null_div -> 0:s:false:true:cons_-:cons_lt:cons_if:cons_div:null_encArg:null_encode_-:null_encode_0:null_encode_s:null_encode_lt:null_encode_false:null_encode_true:null_encode_if:null_encode_div:null_minus:null_lt:null_if:null_div null_encArg :: 0:s:false:true:cons_-:cons_lt:cons_if:cons_div:null_encArg:null_encode_-:null_encode_0:null_encode_s:null_encode_lt:null_encode_false:null_encode_true:null_encode_if:null_encode_div:null_minus:null_lt:null_if:null_div null_encode_- :: 0:s:false:true:cons_-:cons_lt:cons_if:cons_div:null_encArg:null_encode_-:null_encode_0:null_encode_s:null_encode_lt:null_encode_false:null_encode_true:null_encode_if:null_encode_div:null_minus:null_lt:null_if:null_div null_encode_0 :: 0:s:false:true:cons_-:cons_lt:cons_if:cons_div:null_encArg:null_encode_-:null_encode_0:null_encode_s:null_encode_lt:null_encode_false:null_encode_true:null_encode_if:null_encode_div:null_minus:null_lt:null_if:null_div null_encode_s :: 0:s:false:true:cons_-:cons_lt:cons_if:cons_div:null_encArg:null_encode_-:null_encode_0:null_encode_s:null_encode_lt:null_encode_false:null_encode_true:null_encode_if:null_encode_div:null_minus:null_lt:null_if:null_div null_encode_lt :: 0:s:false:true:cons_-:cons_lt:cons_if:cons_div:null_encArg:null_encode_-:null_encode_0:null_encode_s:null_encode_lt:null_encode_false:null_encode_true:null_encode_if:null_encode_div:null_minus:null_lt:null_if:null_div null_encode_false :: 0:s:false:true:cons_-:cons_lt:cons_if:cons_div:null_encArg:null_encode_-:null_encode_0:null_encode_s:null_encode_lt:null_encode_false:null_encode_true:null_encode_if:null_encode_div:null_minus:null_lt:null_if:null_div null_encode_true :: 0:s:false:true:cons_-:cons_lt:cons_if:cons_div:null_encArg:null_encode_-:null_encode_0:null_encode_s:null_encode_lt:null_encode_false:null_encode_true:null_encode_if:null_encode_div:null_minus:null_lt:null_if:null_div null_encode_if :: 0:s:false:true:cons_-:cons_lt:cons_if:cons_div:null_encArg:null_encode_-:null_encode_0:null_encode_s:null_encode_lt:null_encode_false:null_encode_true:null_encode_if:null_encode_div:null_minus:null_lt:null_if:null_div null_encode_div :: 0:s:false:true:cons_-:cons_lt:cons_if:cons_div:null_encArg:null_encode_-:null_encode_0:null_encode_s:null_encode_lt:null_encode_false:null_encode_true:null_encode_if:null_encode_div:null_minus:null_lt:null_if:null_div null_minus :: 0:s:false:true:cons_-:cons_lt:cons_if:cons_div:null_encArg:null_encode_-:null_encode_0:null_encode_s:null_encode_lt:null_encode_false:null_encode_true:null_encode_if:null_encode_div:null_minus:null_lt:null_if:null_div null_lt :: 0:s:false:true:cons_-:cons_lt:cons_if:cons_div:null_encArg:null_encode_-:null_encode_0:null_encode_s:null_encode_lt:null_encode_false:null_encode_true:null_encode_if:null_encode_div:null_minus:null_lt:null_if:null_div null_if :: 0:s:false:true:cons_-:cons_lt:cons_if:cons_div:null_encArg:null_encode_-:null_encode_0:null_encode_s:null_encode_lt:null_encode_false:null_encode_true:null_encode_if:null_encode_div:null_minus:null_lt:null_if:null_div null_div :: 0:s:false:true:cons_-:cons_lt:cons_if:cons_div:null_encArg:null_encode_-:null_encode_0:null_encode_s:null_encode_lt:null_encode_false:null_encode_true:null_encode_if:null_encode_div:null_minus:null_lt:null_if:null_div Rewrite Strategy: INNERMOST ---------------------------------------- (13) 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 false => 1 true => 2 null_encArg => 0 null_encode_- => 0 null_encode_0 => 0 null_encode_s => 0 null_encode_lt => 0 null_encode_false => 0 null_encode_true => 0 null_encode_if => 0 null_encode_div => 0 null_minus => 0 null_lt => 0 null_if => 0 null_div => 0 ---------------------------------------- (14) Obligation: Complexity RNTS consisting of the following rules: div(z, z') -{ 1 }-> if(lt(x, y), 0, 1 + div(minus(x, y), 1 + y)) :|: z' = 1 + y, x >= 0, y >= 0, z = 1 + x div(z, z') -{ 1 }-> 0 :|: x >= 0, z = x, z' = 0 div(z, z') -{ 1 }-> 0 :|: y >= 0, z = 0, z' = y div(z, z') -{ 0 }-> 0 :|: v0 >= 0, v1 >= 0, z = v0, z' = v1 encArg(z) -{ 0 }-> minus(encArg(x_1), encArg(x_2)) :|: x_1 >= 0, z = 1 + x_1 + x_2, x_2 >= 0 encArg(z) -{ 0 }-> lt(encArg(x_1), encArg(x_2)) :|: x_1 >= 0, z = 1 + x_1 + x_2, x_2 >= 0 encArg(z) -{ 0 }-> if(encArg(x_1), encArg(x_2), encArg(x_3)) :|: x_1 >= 0, z = 1 + x_1 + x_2 + x_3, x_3 >= 0, x_2 >= 0 encArg(z) -{ 0 }-> div(encArg(x_1), encArg(x_2)) :|: x_1 >= 0, z = 1 + x_1 + x_2, x_2 >= 0 encArg(z) -{ 0 }-> 2 :|: z = 2 encArg(z) -{ 0 }-> 1 :|: z = 1 encArg(z) -{ 0 }-> 0 :|: z = 0 encArg(z) -{ 0 }-> 0 :|: v0 >= 0, z = v0 encArg(z) -{ 0 }-> 1 + encArg(x_1) :|: z = 1 + x_1, x_1 >= 0 encode_-(z, z') -{ 0 }-> minus(encArg(x_1), encArg(x_2)) :|: x_1 >= 0, x_2 >= 0, z = x_1, z' = x_2 encode_-(z, z') -{ 0 }-> 0 :|: v0 >= 0, v1 >= 0, z = v0, z' = v1 encode_0 -{ 0 }-> 0 :|: encode_div(z, z') -{ 0 }-> div(encArg(x_1), encArg(x_2)) :|: x_1 >= 0, x_2 >= 0, z = x_1, z' = x_2 encode_div(z, z') -{ 0 }-> 0 :|: v0 >= 0, v1 >= 0, z = v0, z' = v1 encode_false -{ 0 }-> 1 :|: encode_false -{ 0 }-> 0 :|: encode_if(z, z', z'') -{ 0 }-> if(encArg(x_1), encArg(x_2), encArg(x_3)) :|: x_1 >= 0, x_3 >= 0, x_2 >= 0, z = x_1, z' = x_2, z'' = x_3 encode_if(z, z', z'') -{ 0 }-> 0 :|: v0 >= 0, z'' = v2, v1 >= 0, z = v0, z' = v1, v2 >= 0 encode_lt(z, z') -{ 0 }-> lt(encArg(x_1), encArg(x_2)) :|: x_1 >= 0, x_2 >= 0, z = x_1, z' = x_2 encode_lt(z, z') -{ 0 }-> 0 :|: v0 >= 0, v1 >= 0, z = v0, z' = v1 encode_s(z) -{ 0 }-> 0 :|: v0 >= 0, z = v0 encode_s(z) -{ 0 }-> 1 + encArg(x_1) :|: x_1 >= 0, z = x_1 encode_true -{ 0 }-> 2 :|: encode_true -{ 0 }-> 0 :|: if(z, z', z'') -{ 1 }-> x :|: z = 2, z' = x, z'' = y, x >= 0, y >= 0 if(z, z', z'') -{ 1 }-> y :|: z' = x, z'' = y, z = 1, x >= 0, y >= 0 if(z, z', z'') -{ 0 }-> 0 :|: v0 >= 0, z'' = v2, v1 >= 0, z = v0, z' = v1, v2 >= 0 lt(z, z') -{ 1 }-> lt(x, y) :|: z' = 1 + y, x >= 0, y >= 0, z = 1 + x lt(z, z') -{ 1 }-> 2 :|: z' = 1 + y, y >= 0, z = 0 lt(z, z') -{ 1 }-> 1 :|: x >= 0, z = x, z' = 0 lt(z, z') -{ 0 }-> 0 :|: v0 >= 0, v1 >= 0, z = v0, z' = v1 minus(z, z') -{ 1 }-> x :|: x >= 0, z = x, z' = 0 minus(z, z') -{ 1 }-> minus(x, y) :|: z' = 1 + y, x >= 0, y >= 0, z = 1 + x minus(z, z') -{ 1 }-> 0 :|: z' = 1 + y, y >= 0, z = 0 minus(z, z') -{ 0 }-> 0 :|: v0 >= 0, v1 >= 0, z = v0, z' = v1 Only complete derivations are relevant for the runtime complexity. ---------------------------------------- (15) CompleteCoflocoProof (FINISHED) Transformed the RNTS (where only complete derivations are relevant) into cost relations for CoFloCo: eq(start(V1, V, V12),0,[minus(V1, V, Out)],[V1 >= 0,V >= 0]). eq(start(V1, V, V12),0,[lt(V1, V, Out)],[V1 >= 0,V >= 0]). eq(start(V1, V, V12),0,[if(V1, V, V12, Out)],[V1 >= 0,V >= 0,V12 >= 0]). eq(start(V1, V, V12),0,[div(V1, V, Out)],[V1 >= 0,V >= 0]). eq(start(V1, V, V12),0,[encArg(V1, Out)],[V1 >= 0]). eq(start(V1, V, V12),0,[fun(V1, V, Out)],[V1 >= 0,V >= 0]). eq(start(V1, V, V12),0,[fun1(Out)],[]). eq(start(V1, V, V12),0,[fun2(V1, Out)],[V1 >= 0]). eq(start(V1, V, V12),0,[fun3(V1, V, Out)],[V1 >= 0,V >= 0]). eq(start(V1, V, V12),0,[fun4(Out)],[]). eq(start(V1, V, V12),0,[fun5(Out)],[]). eq(start(V1, V, V12),0,[fun6(V1, V, V12, Out)],[V1 >= 0,V >= 0,V12 >= 0]). eq(start(V1, V, V12),0,[fun7(V1, V, Out)],[V1 >= 0,V >= 0]). eq(minus(V1, V, Out),1,[],[Out = V2,V2 >= 0,V1 = V2,V = 0]). eq(minus(V1, V, Out),1,[],[Out = 0,V = 1 + V3,V3 >= 0,V1 = 0]). eq(minus(V1, V, Out),1,[minus(V4, V5, Ret)],[Out = Ret,V = 1 + V5,V4 >= 0,V5 >= 0,V1 = 1 + V4]). eq(lt(V1, V, Out),1,[],[Out = 1,V6 >= 0,V1 = V6,V = 0]). eq(lt(V1, V, Out),1,[],[Out = 2,V = 1 + V7,V7 >= 0,V1 = 0]). eq(lt(V1, V, Out),1,[lt(V8, V9, Ret1)],[Out = Ret1,V = 1 + V9,V8 >= 0,V9 >= 0,V1 = 1 + V8]). eq(if(V1, V, V12, Out),1,[],[Out = V11,V1 = 2,V = V11,V12 = V10,V11 >= 0,V10 >= 0]). eq(if(V1, V, V12, Out),1,[],[Out = V13,V = V14,V12 = V13,V1 = 1,V14 >= 0,V13 >= 0]). eq(div(V1, V, Out),1,[],[Out = 0,V15 >= 0,V1 = V15,V = 0]). eq(div(V1, V, Out),1,[],[Out = 0,V16 >= 0,V1 = 0,V = V16]). eq(div(V1, V, Out),1,[lt(V17, V18, Ret0),minus(V17, V18, Ret210),div(Ret210, 1 + V18, Ret21),if(Ret0, 0, 1 + Ret21, Ret2)],[Out = Ret2,V = 1 + V18,V17 >= 0,V18 >= 0,V1 = 1 + V17]). eq(encArg(V1, Out),0,[],[Out = 0,V1 = 0]). eq(encArg(V1, Out),0,[encArg(V19, Ret11)],[Out = 1 + Ret11,V1 = 1 + V19,V19 >= 0]). eq(encArg(V1, Out),0,[],[Out = 1,V1 = 1]). eq(encArg(V1, Out),0,[],[Out = 2,V1 = 2]). eq(encArg(V1, Out),0,[encArg(V20, Ret01),encArg(V21, Ret12),minus(Ret01, Ret12, Ret3)],[Out = Ret3,V20 >= 0,V1 = 1 + V20 + V21,V21 >= 0]). eq(encArg(V1, Out),0,[encArg(V22, Ret02),encArg(V23, Ret13),lt(Ret02, Ret13, Ret4)],[Out = Ret4,V22 >= 0,V1 = 1 + V22 + V23,V23 >= 0]). eq(encArg(V1, Out),0,[encArg(V26, Ret03),encArg(V25, Ret14),encArg(V24, Ret22),if(Ret03, Ret14, Ret22, Ret5)],[Out = Ret5,V26 >= 0,V1 = 1 + V24 + V25 + V26,V24 >= 0,V25 >= 0]). eq(encArg(V1, Out),0,[encArg(V28, Ret04),encArg(V27, Ret15),div(Ret04, Ret15, Ret6)],[Out = Ret6,V28 >= 0,V1 = 1 + V27 + V28,V27 >= 0]). eq(fun(V1, V, Out),0,[encArg(V29, Ret05),encArg(V30, Ret16),minus(Ret05, Ret16, Ret7)],[Out = Ret7,V29 >= 0,V30 >= 0,V1 = V29,V = V30]). eq(fun1(Out),0,[],[Out = 0]). eq(fun2(V1, Out),0,[encArg(V31, Ret17)],[Out = 1 + Ret17,V31 >= 0,V1 = V31]). eq(fun3(V1, V, Out),0,[encArg(V33, Ret06),encArg(V32, Ret18),lt(Ret06, Ret18, Ret8)],[Out = Ret8,V33 >= 0,V32 >= 0,V1 = V33,V = V32]). eq(fun4(Out),0,[],[Out = 1]). eq(fun5(Out),0,[],[Out = 2]). eq(fun6(V1, V, V12, Out),0,[encArg(V36, Ret07),encArg(V35, Ret19),encArg(V34, Ret23),if(Ret07, Ret19, Ret23, Ret9)],[Out = Ret9,V36 >= 0,V34 >= 0,V35 >= 0,V1 = V36,V = V35,V12 = V34]). eq(fun7(V1, V, Out),0,[encArg(V37, Ret08),encArg(V38, Ret110),div(Ret08, Ret110, Ret10)],[Out = Ret10,V37 >= 0,V38 >= 0,V1 = V37,V = V38]). eq(encArg(V1, Out),0,[],[Out = 0,V39 >= 0,V1 = V39]). eq(fun(V1, V, Out),0,[],[Out = 0,V41 >= 0,V40 >= 0,V1 = V41,V = V40]). eq(fun2(V1, Out),0,[],[Out = 0,V42 >= 0,V1 = V42]). eq(fun3(V1, V, Out),0,[],[Out = 0,V43 >= 0,V44 >= 0,V1 = V43,V = V44]). eq(fun4(Out),0,[],[Out = 0]). eq(fun5(Out),0,[],[Out = 0]). eq(fun6(V1, V, V12, Out),0,[],[Out = 0,V45 >= 0,V12 = V47,V46 >= 0,V1 = V45,V = V46,V47 >= 0]). eq(fun7(V1, V, Out),0,[],[Out = 0,V48 >= 0,V49 >= 0,V1 = V48,V = V49]). eq(minus(V1, V, Out),0,[],[Out = 0,V51 >= 0,V50 >= 0,V1 = V51,V = V50]). eq(lt(V1, V, Out),0,[],[Out = 0,V52 >= 0,V53 >= 0,V1 = V52,V = V53]). eq(if(V1, V, V12, Out),0,[],[Out = 0,V54 >= 0,V12 = V56,V55 >= 0,V1 = V54,V = V55,V56 >= 0]). eq(div(V1, V, Out),0,[],[Out = 0,V57 >= 0,V58 >= 0,V1 = V57,V = V58]). input_output_vars(minus(V1,V,Out),[V1,V],[Out]). input_output_vars(lt(V1,V,Out),[V1,V],[Out]). input_output_vars(if(V1,V,V12,Out),[V1,V,V12],[Out]). input_output_vars(div(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,V,Out),[V1,V],[Out]). input_output_vars(fun4(Out),[],[Out]). input_output_vars(fun5(Out),[],[Out]). input_output_vars(fun6(V1,V,V12,Out),[V1,V,V12],[Out]). input_output_vars(fun7(V1,V,Out),[V1,V],[Out]). CoFloCo proof output: Preprocessing Cost Relations ===================================== #### Computed strongly connected components 0. non_recursive : [if/4] 1. recursive : [lt/3] 2. recursive : [minus/3] 3. recursive [non_tail] : [(div)/3] 4. recursive [non_tail,multiple] : [encArg/2] 5. non_recursive : [fun/3] 6. non_recursive : [fun1/1] 7. non_recursive : [fun2/2] 8. non_recursive : [fun3/3] 9. non_recursive : [fun4/1] 10. non_recursive : [fun5/1] 11. non_recursive : [fun6/4] 12. non_recursive : [fun7/3] 13. non_recursive : [start/3] #### Obtained direct recursion through partial evaluation 0. SCC is partially evaluated into if/4 1. SCC is partially evaluated into lt/3 2. SCC is partially evaluated into minus/3 3. SCC is partially evaluated into (div)/3 4. SCC is partially evaluated into encArg/2 5. SCC is partially evaluated into fun/3 6. SCC is completely evaluated into other SCCs 7. SCC is partially evaluated into fun2/2 8. SCC is partially evaluated into fun3/3 9. SCC is partially evaluated into fun4/1 10. SCC is partially evaluated into fun5/1 11. SCC is partially evaluated into fun6/4 12. SCC is partially evaluated into fun7/3 13. SCC is partially evaluated into start/3 Control-Flow Refinement of Cost Relations ===================================== ### Specialization of cost equations if/4 * CE 24 is refined into CE [51] * CE 22 is refined into CE [52] * CE 23 is refined into CE [53] ### Cost equations --> "Loop" of if/4 * CEs [51] --> Loop 30 * CEs [52] --> Loop 31 * CEs [53] --> Loop 32 ### Ranking functions of CR if(V1,V,V12,Out) #### Partial ranking functions of CR if(V1,V,V12,Out) ### Specialization of cost equations lt/3 * CE 21 is refined into CE [54] * CE 18 is refined into CE [55] * CE 19 is refined into CE [56] * CE 20 is refined into CE [57] ### Cost equations --> "Loop" of lt/3 * CEs [57] --> Loop 33 * CEs [54] --> Loop 34 * CEs [55] --> Loop 35 * CEs [56] --> Loop 36 ### Ranking functions of CR lt(V1,V,Out) * RF of phase [33]: [V,V1] #### Partial ranking functions of CR lt(V1,V,Out) * Partial RF of phase [33]: - RF of loop [33:1]: V V1 ### Specialization of cost equations minus/3 * CE 14 is refined into CE [58] * CE 15 is refined into CE [59] * CE 17 is refined into CE [60] * CE 16 is refined into CE [61] ### Cost equations --> "Loop" of minus/3 * CEs [61] --> Loop 37 * CEs [58] --> Loop 38 * CEs [59,60] --> Loop 39 ### Ranking functions of CR minus(V1,V,Out) * RF of phase [37]: [V,V1] #### Partial ranking functions of CR minus(V1,V,Out) * Partial RF of phase [37]: - RF of loop [37:1]: V V1 ### Specialization of cost equations (div)/3 * CE 25 is refined into CE [62] * CE 26 is refined into CE [63] * CE 28 is refined into CE [64] * CE 27 is refined into CE [65,66,67,68,69,70,71,72,73,74,75,76,77,78,79] ### Cost equations --> "Loop" of (div)/3 * CEs [76] --> Loop 40 * CEs [74] --> Loop 41 * CEs [73,77] --> Loop 42 * CEs [75] --> Loop 43 * CEs [67] --> Loop 44 * CEs [69] --> Loop 45 * CEs [68,71] --> Loop 46 * CEs [70] --> Loop 47 * CEs [65,66,72,78,79] --> Loop 48 * CEs [62] --> Loop 49 * CEs [63,64] --> Loop 50 ### Ranking functions of CR div(V1,V,Out) * RF of phase [40,42]: [V1-1,V1-V+1] * RF of phase [44,46]: [V1] #### Partial ranking functions of CR div(V1,V,Out) * Partial RF of phase [40,42]: - RF of loop [40:1,42:1]: V1-1 V1-V+1 * Partial RF of phase [44,46]: - RF of loop [44:1,46:1]: V1 ### Specialization of cost equations encArg/2 * CE 29 is refined into CE [80] * CE 32 is refined into CE [81] * CE 31 is refined into CE [82] * CE 33 is refined into CE [83,84,85] * CE 34 is refined into CE [86,87,88,89,90] * CE 36 is refined into CE [91,92,93,94,95] * CE 35 is refined into CE [96,97,98] * CE 30 is refined into CE [99] ### Cost equations --> "Loop" of encArg/2 * CEs [99] --> Loop 51 * CEs [97] --> Loop 52 * CEs [96] --> Loop 53 * CEs [98] --> Loop 54 * CEs [94,95] --> Loop 55 * CEs [85] --> Loop 56 * CEs [92] --> Loop 57 * CEs [83] --> Loop 58 * CEs [90] --> Loop 59 * CEs [86] --> Loop 60 * CEs [89,93] --> Loop 61 * CEs [87] --> Loop 62 * CEs [84,88,91] --> Loop 63 * CEs [80] --> Loop 64 * CEs [81] --> Loop 65 * CEs [82] --> Loop 66 ### Ranking functions of CR encArg(V1,Out) * RF of phase [51,52,53,54,55,56,57,58,59,60,61,62,63]: [V1] #### Partial ranking functions of CR encArg(V1,Out) * Partial RF of phase [51,52,53,54,55,56,57,58,59,60,61,62,63]: - RF of loop [51:1,52:1,52:2,52:3,53:1,53:2,53:3,54:1,54:2,54:3,55:1,55:2,56:1,56:2,57:1,57:2,58:1,58:2,59:1,59:2,60:1,60:2,61:1,61:2,62:1,62:2,63:1,63:2]: V1 ### Specialization of cost equations fun/3 * CE 37 is refined into CE [100,101,102,103,104,105,106,107,108,109,110,111,112,113,114,115,116,117,118] * CE 38 is refined into CE [119] ### Cost equations --> "Loop" of fun/3 * CEs [104] --> Loop 67 * CEs [103,116] --> Loop 68 * CEs [109] --> Loop 69 * CEs [100,102,105,107,112] --> Loop 70 * CEs [101,106,108,110,111,113,114,115,117,118,119] --> Loop 71 ### 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 [120,121,122] * CE 40 is refined into CE [123] ### Cost equations --> "Loop" of fun2/2 * CEs [122] --> Loop 72 * CEs [123] --> Loop 73 * CEs [120,121] --> Loop 74 ### Ranking functions of CR fun2(V1,Out) #### Partial ranking functions of CR fun2(V1,Out) ### Specialization of cost equations fun3/3 * CE 41 is refined into CE [124,125,126,127,128,129,130,131,132,133,134,135,136,137,138,139,140,141,142,143,144,145,146,147,148,149] * CE 42 is refined into CE [150] ### Cost equations --> "Loop" of fun3/3 * CEs [129,132,146] --> Loop 75 * CEs [131] --> Loop 76 * CEs [130,147] --> Loop 77 * CEs [124,128,138,143] --> Loop 78 * CEs [125,127,133,135,137,140,141,144,148] --> Loop 79 * CEs [126,134,136,139,142,145,149,150] --> Loop 80 ### Ranking functions of CR fun3(V1,V,Out) #### Partial ranking functions of CR fun3(V1,V,Out) ### Specialization of cost equations fun4/1 * CE 43 is refined into CE [151] * CE 44 is refined into CE [152] ### Cost equations --> "Loop" of fun4/1 * CEs [151] --> Loop 81 * CEs [152] --> Loop 82 ### Ranking functions of CR fun4(Out) #### Partial ranking functions of CR fun4(Out) ### Specialization of cost equations fun5/1 * CE 45 is refined into CE [153] * CE 46 is refined into CE [154] ### Cost equations --> "Loop" of fun5/1 * CEs [153] --> Loop 83 * CEs [154] --> Loop 84 ### Ranking functions of CR fun5(Out) #### Partial ranking functions of CR fun5(Out) ### Specialization of cost equations fun6/4 * CE 47 is refined into CE [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,180,181,182,183,184,185,186,187,188,189,190,191,192,193,194,195,196,197,198,199,200,201,202,203,204,205,206,207,208] * CE 48 is refined into CE [209] ### Cost equations --> "Loop" of fun6/4 * CEs [158,176] --> Loop 85 * CEs [165,171] --> Loop 86 * CEs [155,164,167,168,173] --> Loop 87 * CEs [166,169,170,172,203,204,205] --> Loop 88 * CEs [159,184] --> Loop 89 * CEs [160,177,178,185,196,197,201,207] --> Loop 90 * CEs [156,162,182,186,188,190,192] --> Loop 91 * CEs [157,161,163,174,175,179,180,181,183,187,189,191,193,194,195,198,199,200,202,206,208,209] --> Loop 92 ### Ranking functions of CR fun6(V1,V,V12,Out) #### Partial ranking functions of CR fun6(V1,V,V12,Out) ### Specialization of cost equations fun7/3 * CE 49 is refined into CE [210,211,212,213,214,215,216,217,218,219,220,221,222,223,224,225,226,227,228] * CE 50 is refined into CE [229] ### Cost equations --> "Loop" of fun7/3 * CEs [216,217] --> Loop 93 * CEs [215,227] --> Loop 94 * CEs [212,221] --> Loop 95 * CEs [210,218,219,225,226,228,229] --> Loop 96 * CEs [211,213,214,220,222,223,224] --> Loop 97 ### Ranking functions of CR fun7(V1,V,Out) #### Partial ranking functions of CR fun7(V1,V,Out) ### Specialization of cost equations start/3 * CE 1 is refined into CE [230,231,232] * CE 2 is refined into CE [233,234,235,236,237] * CE 3 is refined into CE [238,239,240] * CE 4 is refined into CE [241,242,243,244,245] * CE 5 is refined into CE [246,247,248] * CE 6 is refined into CE [249,250,251] * CE 7 is refined into CE [252] * CE 8 is refined into CE [253,254,255] * CE 9 is refined into CE [256,257,258] * CE 10 is refined into CE [259,260] * CE 11 is refined into CE [261,262] * CE 12 is refined into CE [263,264,265,266,267] * CE 13 is refined into CE [268,269,270] ### Cost equations --> "Loop" of start/3 * CEs [230,231,232,233,234,235,236,237,238,239,240,241,242,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] --> Loop 98 ### Ranking functions of CR start(V1,V,V12) #### Partial ranking functions of CR start(V1,V,V12) Computing Bounds ===================================== #### Cost of chains of if(V1,V,V12,Out): * Chain [32]: 1 with precondition: [V1=1,V12=Out,V>=0,V12>=0] * Chain [31]: 1 with precondition: [V1=2,V=Out,V>=0,V12>=0] * Chain [30]: 0 with precondition: [Out=0,V1>=0,V>=0,V12>=0] #### Cost of chains of lt(V1,V,Out): * Chain [[33],36]: 1*it(33)+1 Such that:it(33) =< V1 with precondition: [Out=2,V1>=1,V>=V1+1] * Chain [[33],35]: 1*it(33)+1 Such that:it(33) =< V with precondition: [Out=1,V>=1,V1>=V] * Chain [[33],34]: 1*it(33)+0 Such that:it(33) =< V with precondition: [Out=0,V1>=1,V>=1] * Chain [36]: 1 with precondition: [V1=0,Out=2,V>=1] * Chain [35]: 1 with precondition: [V=0,Out=1,V1>=0] * Chain [34]: 0 with precondition: [Out=0,V1>=0,V>=0] #### Cost of chains of minus(V1,V,Out): * Chain [[37],39]: 1*it(37)+1 Such that:it(37) =< V with precondition: [Out=0,V1>=1,V>=1] * Chain [[37],38]: 1*it(37)+1 Such that:it(37) =< V with precondition: [V1=Out+V,V>=1,V1>=V] * Chain [39]: 1 with precondition: [Out=0,V1>=0,V>=0] * Chain [38]: 1 with precondition: [V=0,V1=Out,V1>=0] #### Cost of chains of div(V1,V,Out): * Chain [[44,46],50]: 7*it(44)+1 Such that:aux(3) =< V1 it(44) =< aux(3) with precondition: [V=1,V1>=1,Out>=0,V1>=Out] * Chain [[44,46],48,50]: 9*it(44)+6*s(4)+5 Such that:aux(7) =< 1 aux(8) =< V1 it(44) =< aux(8) s(4) =< aux(7) with precondition: [V=1,V1>=2,Out>=0,V1>=Out+1] * Chain [[44,46],47,50]: 7*it(44)+4 Such that:aux(9) =< V1 it(44) =< aux(9) with precondition: [V=1,V1>=2,Out>=0,V1>=Out+1] * Chain [[44,46],45,50]: 7*it(44)+5 Such that:aux(10) =< V1 it(44) =< aux(10) with precondition: [V=1,V1>=2,Out>=0,V1>=Out] * Chain [[40,42],50]: 7*it(40)+6*s(24)+1 Such that:aux(16) =< V1-V+1 aux(19) =< V1 it(40) =< aux(19) it(40) =< aux(16) s(24) =< aux(19) with precondition: [V>=2,Out>=0,V1>=V,V1+2>=2*Out+V] * Chain [[40,42],48,50]: 7*it(40)+6*s(4)+8*s(8)+5 Such that:aux(16) =< V1-V+1 aux(7) =< V aux(20) =< V1 s(8) =< aux(20) s(4) =< aux(7) it(40) =< aux(20) it(40) =< aux(16) with precondition: [V>=2,Out>=0,V1>=V+1,V1+1>=2*Out+V] * Chain [[40,42],43,50]: 7*it(40)+6*s(24)+2*s(28)+4 Such that:aux(15) =< V1 aux(16) =< V1-V+1 aux(21) =< V aux(22) =< V1-V s(28) =< aux(21) it(40) =< aux(15) s(25) =< aux(15) it(40) =< aux(16) it(40) =< aux(22) s(25) =< aux(22) s(24) =< s(25) with precondition: [V>=2,Out>=0,V1>=2*V,V1+2>=2*Out+2*V] * Chain [[40,42],41,50]: 7*it(40)+6*s(24)+2*s(30)+5 Such that:aux(15) =< V1 aux(16) =< V1-V+1 aux(23) =< V aux(24) =< V1-V s(30) =< aux(23) it(40) =< aux(15) s(25) =< aux(15) it(40) =< aux(16) it(40) =< aux(24) s(25) =< aux(24) s(24) =< s(25) with precondition: [V>=2,Out>=0,V1>=2*V,V1+4>=2*Out+2*V] * Chain [50]: 1 with precondition: [Out=0,V1>=0,V>=0] * Chain [49]: 1 with precondition: [V=0,Out=0,V1>=0] * Chain [48,50]: 6*s(4)+2*s(8)+5 Such that:aux(5) =< V1 aux(7) =< V s(8) =< aux(5) s(4) =< aux(7) with precondition: [Out=0,V1>=1,V>=1] * Chain [47,50]: 4 with precondition: [V=1,Out=0,V1>=1] * Chain [45,50]: 5 with precondition: [V=1,Out=1,V1>=1] * Chain [43,50]: 2*s(28)+4 Such that:aux(21) =< V s(28) =< aux(21) with precondition: [Out=0,V>=2,V1>=V] * Chain [41,50]: 2*s(30)+5 Such that:aux(23) =< V s(30) =< aux(23) with precondition: [Out=1,V>=2,V1>=V] #### Cost of chains of encArg(V1,Out): * Chain [66]: 0 with precondition: [V1=1,Out=1] * Chain [65]: 0 with precondition: [V1=2,Out=2] * Chain [64]: 0 with precondition: [Out=0,V1>=0] * Chain [multiple([51,52,53,54,55,56,57,58,59,60,61,62,63],[[66],[65],[64]])]: 1*it(52)+1*it(53)+6*it(55)+10*it(57)+7*it(58)+1*it(59)+1*it(60)+66*s(118)+1*s(120)+30*s(121)+6*s(122)+1*s(125)+1*s(126)+4*s(127)+8*s(129)+0 Such that:aux(62) =< V1 aux(63) =< V1/2 aux(64) =< 2/3*V1 aux(65) =< 2/5*V1 aux(66) =< 3/5*V1 aux(67) =< 3/7*V1 it(52) =< aux(62) it(53) =< aux(62) it(55) =< aux(62) it(57) =< aux(62) it(58) =< aux(62) it(59) =< aux(62) it(60) =< aux(62) it(55) =< aux(63) it(57) =< aux(63) it(59) =< aux(63) it(57) =< aux(64) it(59) =< aux(64) it(60) =< aux(64) it(59) =< aux(65) it(53) =< aux(66) it(52) =< aux(67) aux(46) =< aux(62)+1 aux(52) =< aux(62)+2 aux(43) =< aux(62) s(131) =< it(58)*aux(46) s(130) =< it(58)*aux(52) s(126) =< it(57)*aux(43) s(125) =< it(59)*aux(43) s(124) =< it(57)*aux(46) s(120) =< it(55)*aux(43) s(119) =< it(55)*aux(62) s(127) =< s(131) s(129) =< s(130) s(121) =< s(124) s(122) =< aux(64) s(118) =< s(119) with precondition: [V1>=1,Out>=0,V1>=Out] #### Cost of chains of fun(V1,V,Out): * Chain [71]: 2*s(167)+2*s(168)+12*s(169)+20*s(170)+14*s(171)+2*s(172)+2*s(173)+2*s(179)+2*s(180)+2*s(182)+8*s(184)+16*s(185)+60*s(186)+12*s(187)+132*s(188)+4*s(195)+4*s(196)+24*s(197)+40*s(198)+31*s(199)+4*s(200)+4*s(201)+4*s(207)+4*s(208)+4*s(210)+16*s(212)+32*s(213)+120*s(214)+24*s(215)+264*s(216)+2*s(276)+1 Such that:aux(71) =< 2 aux(72) =< V1 aux(73) =< V1/2 aux(74) =< 2/3*V1 aux(75) =< 2/5*V1 aux(76) =< 3/5*V1 aux(77) =< 3/7*V1 aux(78) =< V aux(79) =< V/2 aux(80) =< 2/3*V aux(81) =< 2/5*V aux(82) =< 3/5*V aux(83) =< 3/7*V s(276) =< aux(71) s(199) =< aux(78) s(195) =< aux(78) s(196) =< aux(78) s(197) =< aux(78) s(198) =< aux(78) s(200) =< aux(78) s(201) =< aux(78) s(197) =< aux(79) s(198) =< aux(79) s(200) =< aux(79) s(198) =< aux(80) s(200) =< aux(80) s(201) =< aux(80) s(200) =< aux(81) s(196) =< aux(82) s(195) =< aux(83) s(202) =< aux(78)+1 s(203) =< aux(78)+2 s(204) =< aux(78) s(205) =< s(199)*s(202) s(206) =< s(199)*s(203) s(207) =< s(198)*s(204) s(208) =< s(200)*s(204) s(209) =< s(198)*s(202) s(210) =< s(197)*s(204) s(211) =< s(197)*aux(78) s(212) =< s(205) s(213) =< s(206) s(214) =< s(209) s(215) =< aux(80) s(216) =< s(211) s(167) =< aux(72) s(168) =< aux(72) s(169) =< aux(72) s(170) =< aux(72) s(171) =< aux(72) s(172) =< aux(72) s(173) =< aux(72) s(169) =< aux(73) s(170) =< aux(73) s(172) =< aux(73) s(170) =< aux(74) s(172) =< aux(74) s(173) =< aux(74) s(172) =< aux(75) s(168) =< aux(76) s(167) =< aux(77) s(174) =< aux(72)+1 s(175) =< aux(72)+2 s(176) =< aux(72) s(177) =< s(171)*s(174) s(178) =< s(171)*s(175) s(179) =< s(170)*s(176) s(180) =< s(172)*s(176) s(181) =< s(170)*s(174) s(182) =< s(169)*s(176) s(183) =< s(169)*aux(72) s(184) =< s(177) s(185) =< s(178) s(186) =< s(181) s(187) =< aux(74) s(188) =< s(183) with precondition: [Out=0,V1>=0,V>=0] * Chain [70]: 3*s(343)+3*s(344)+18*s(345)+30*s(346)+21*s(347)+3*s(348)+3*s(349)+3*s(355)+3*s(356)+3*s(358)+12*s(360)+24*s(361)+90*s(362)+18*s(363)+198*s(364)+3*s(371)+3*s(372)+18*s(373)+30*s(374)+22*s(375)+3*s(376)+3*s(377)+3*s(383)+3*s(384)+3*s(386)+12*s(388)+24*s(389)+90*s(390)+18*s(391)+198*s(392)+1 Such that:aux(85) =< V1 aux(86) =< V1/2 aux(87) =< 2/3*V1 aux(88) =< 2/5*V1 aux(89) =< 3/5*V1 aux(90) =< 3/7*V1 aux(91) =< V aux(92) =< V/2 aux(93) =< 2/3*V aux(94) =< 2/5*V aux(95) =< 3/5*V aux(96) =< 3/7*V s(371) =< aux(91) s(372) =< aux(91) s(373) =< aux(91) s(374) =< aux(91) s(375) =< aux(91) s(376) =< aux(91) s(377) =< aux(91) s(373) =< aux(92) s(374) =< aux(92) s(376) =< aux(92) s(374) =< aux(93) s(376) =< aux(93) s(377) =< aux(93) s(376) =< aux(94) s(372) =< aux(95) s(371) =< aux(96) s(378) =< aux(91)+1 s(379) =< aux(91)+2 s(380) =< aux(91) s(381) =< s(375)*s(378) s(382) =< s(375)*s(379) s(383) =< s(374)*s(380) s(384) =< s(376)*s(380) s(385) =< s(374)*s(378) s(386) =< s(373)*s(380) s(387) =< s(373)*aux(91) s(388) =< s(381) s(389) =< s(382) s(390) =< s(385) s(391) =< aux(93) s(392) =< s(387) s(343) =< aux(85) s(344) =< aux(85) s(345) =< aux(85) s(346) =< aux(85) s(347) =< aux(85) s(348) =< aux(85) s(349) =< aux(85) s(345) =< aux(86) s(346) =< aux(86) s(348) =< aux(86) s(346) =< aux(87) s(348) =< aux(87) s(349) =< aux(87) s(348) =< aux(88) s(344) =< aux(89) s(343) =< aux(90) s(350) =< aux(85)+1 s(351) =< aux(85)+2 s(352) =< aux(85) s(353) =< s(347)*s(350) s(354) =< s(347)*s(351) s(355) =< s(346)*s(352) s(356) =< s(348)*s(352) s(357) =< s(346)*s(350) s(358) =< s(345)*s(352) s(359) =< s(345)*aux(85) s(360) =< s(353) s(361) =< s(354) s(362) =< s(357) s(363) =< aux(87) s(364) =< s(359) with precondition: [V1>=1,V>=0,Out>=0,V1>=Out] * Chain [69]: 1*s(512)+1*s(513)+6*s(514)+10*s(515)+8*s(516)+1*s(517)+1*s(518)+1*s(524)+1*s(525)+1*s(527)+4*s(529)+8*s(530)+30*s(531)+6*s(532)+66*s(533)+1 Such that:s(507) =< V/2 s(508) =< 2/3*V s(509) =< 2/5*V s(510) =< 3/5*V s(511) =< 3/7*V aux(97) =< V s(516) =< aux(97) s(512) =< aux(97) s(513) =< aux(97) s(514) =< aux(97) s(515) =< aux(97) s(517) =< aux(97) s(518) =< aux(97) s(514) =< s(507) s(515) =< s(507) s(517) =< s(507) s(515) =< s(508) s(517) =< s(508) s(518) =< s(508) s(517) =< s(509) s(513) =< s(510) s(512) =< s(511) s(519) =< aux(97)+1 s(520) =< aux(97)+2 s(521) =< aux(97) s(522) =< s(516)*s(519) s(523) =< s(516)*s(520) s(524) =< s(515)*s(521) s(525) =< s(517)*s(521) s(526) =< s(515)*s(519) s(527) =< s(514)*s(521) s(528) =< s(514)*aux(97) s(529) =< s(522) s(530) =< s(523) s(531) =< s(526) s(532) =< s(508) s(533) =< s(528) with precondition: [V1=2,1>=Out,Out>=0,Out+V>=2] * Chain [68]: 1*s(541)+1*s(542)+6*s(543)+10*s(544)+7*s(545)+1*s(546)+1*s(547)+1*s(553)+1*s(554)+1*s(556)+4*s(558)+8*s(559)+30*s(560)+6*s(561)+66*s(562)+2*s(563)+1 Such that:s(535) =< V1 s(536) =< V1/2 s(537) =< 2/3*V1 s(538) =< 2/5*V1 s(539) =< 3/5*V1 s(540) =< 3/7*V1 aux(98) =< 2 s(563) =< aux(98) s(541) =< s(535) s(542) =< s(535) s(543) =< s(535) s(544) =< s(535) s(545) =< s(535) s(546) =< s(535) s(547) =< s(535) s(543) =< s(536) s(544) =< s(536) s(546) =< s(536) s(544) =< s(537) s(546) =< s(537) s(547) =< s(537) s(546) =< s(538) s(542) =< s(539) s(541) =< s(540) s(548) =< s(535)+1 s(549) =< s(535)+2 s(550) =< s(535) s(551) =< s(545)*s(548) s(552) =< s(545)*s(549) s(553) =< s(544)*s(550) s(554) =< s(546)*s(550) s(555) =< s(544)*s(548) s(556) =< s(543)*s(550) s(557) =< s(543)*s(535) s(558) =< s(551) s(559) =< s(552) s(560) =< s(555) s(561) =< s(537) s(562) =< s(557) with precondition: [V=2,Out=0,V1>=0] * Chain [67]: 1*s(571)+1*s(572)+6*s(573)+10*s(574)+7*s(575)+1*s(576)+1*s(577)+1*s(583)+1*s(584)+1*s(586)+4*s(588)+8*s(589)+30*s(590)+6*s(591)+66*s(592)+1*s(593)+1 Such that:s(593) =< 2 s(565) =< V1 s(566) =< V1/2 s(567) =< 2/3*V1 s(568) =< 2/5*V1 s(569) =< 3/5*V1 s(570) =< 3/7*V1 s(571) =< s(565) s(572) =< s(565) s(573) =< s(565) s(574) =< s(565) s(575) =< s(565) s(576) =< s(565) s(577) =< s(565) s(573) =< s(566) s(574) =< s(566) s(576) =< s(566) s(574) =< s(567) s(576) =< s(567) s(577) =< s(567) s(576) =< s(568) s(572) =< s(569) s(571) =< s(570) s(578) =< s(565)+1 s(579) =< s(565)+2 s(580) =< s(565) s(581) =< s(575)*s(578) s(582) =< s(575)*s(579) s(583) =< s(574)*s(580) s(584) =< s(576)*s(580) s(585) =< s(574)*s(578) s(586) =< s(573)*s(580) s(587) =< s(573)*s(565) s(588) =< s(581) s(589) =< s(582) s(590) =< s(585) s(591) =< s(567) s(592) =< s(587) with precondition: [V=2,Out>=0,V1>=Out+2] #### Cost of chains of fun2(V1,Out): * Chain [74]: 1*s(772)+1*s(773)+6*s(774)+10*s(775)+7*s(776)+1*s(777)+1*s(778)+1*s(784)+1*s(785)+1*s(787)+4*s(789)+8*s(790)+30*s(791)+6*s(792)+66*s(793)+0 Such that:s(766) =< V1 s(767) =< V1/2 s(768) =< 2/3*V1 s(769) =< 2/5*V1 s(770) =< 3/5*V1 s(771) =< 3/7*V1 s(772) =< s(766) s(773) =< s(766) s(774) =< s(766) s(775) =< s(766) s(776) =< s(766) s(777) =< s(766) s(778) =< s(766) s(774) =< s(767) s(775) =< s(767) s(777) =< s(767) s(775) =< s(768) s(777) =< s(768) s(778) =< s(768) s(777) =< s(769) s(773) =< s(770) s(772) =< s(771) s(779) =< s(766)+1 s(780) =< s(766)+2 s(781) =< s(766) s(782) =< s(776)*s(779) s(783) =< s(776)*s(780) s(784) =< s(775)*s(781) s(785) =< s(777)*s(781) s(786) =< s(775)*s(779) s(787) =< s(774)*s(781) s(788) =< s(774)*s(766) s(789) =< s(782) s(790) =< s(783) s(791) =< s(786) s(792) =< s(768) s(793) =< s(788) with precondition: [V1>=1,Out>=1,V1+1>=Out] * Chain [73]: 0 with precondition: [Out=0,V1>=0] * Chain [72]: 0 with precondition: [Out=1,V1>=0] #### Cost of chains of fun3(V1,V,Out): * Chain [80]: 2*s(800)+2*s(801)+12*s(802)+20*s(803)+14*s(804)+2*s(805)+2*s(806)+2*s(812)+2*s(813)+2*s(815)+8*s(817)+16*s(818)+60*s(819)+12*s(820)+132*s(821)+3*s(828)+3*s(829)+18*s(830)+30*s(831)+24*s(832)+3*s(833)+3*s(834)+3*s(840)+3*s(841)+3*s(843)+12*s(845)+24*s(846)+90*s(847)+18*s(848)+198*s(849)+1*s(909)+0 Such that:s(909) =< 2 aux(115) =< V1 aux(116) =< V1/2 aux(117) =< 2/3*V1 aux(118) =< 2/5*V1 aux(119) =< 3/5*V1 aux(120) =< 3/7*V1 aux(121) =< V aux(122) =< V/2 aux(123) =< 2/3*V aux(124) =< 2/5*V aux(125) =< 3/5*V aux(126) =< 3/7*V s(832) =< aux(121) s(828) =< aux(121) s(829) =< aux(121) s(830) =< aux(121) s(831) =< aux(121) s(833) =< aux(121) s(834) =< aux(121) s(830) =< aux(122) s(831) =< aux(122) s(833) =< aux(122) s(831) =< aux(123) s(833) =< aux(123) s(834) =< aux(123) s(833) =< aux(124) s(829) =< aux(125) s(828) =< aux(126) s(835) =< aux(121)+1 s(836) =< aux(121)+2 s(837) =< aux(121) s(838) =< s(832)*s(835) s(839) =< s(832)*s(836) s(840) =< s(831)*s(837) s(841) =< s(833)*s(837) s(842) =< s(831)*s(835) s(843) =< s(830)*s(837) s(844) =< s(830)*aux(121) s(845) =< s(838) s(846) =< s(839) s(847) =< s(842) s(848) =< aux(123) s(849) =< s(844) s(800) =< aux(115) s(801) =< aux(115) s(802) =< aux(115) s(803) =< aux(115) s(804) =< aux(115) s(805) =< aux(115) s(806) =< aux(115) s(802) =< aux(116) s(803) =< aux(116) s(805) =< aux(116) s(803) =< aux(117) s(805) =< aux(117) s(806) =< aux(117) s(805) =< aux(118) s(801) =< aux(119) s(800) =< aux(120) s(807) =< aux(115)+1 s(808) =< aux(115)+2 s(809) =< aux(115) s(810) =< s(804)*s(807) s(811) =< s(804)*s(808) s(812) =< s(803)*s(809) s(813) =< s(805)*s(809) s(814) =< s(803)*s(807) s(815) =< s(802)*s(809) s(816) =< s(802)*aux(115) s(817) =< s(810) s(818) =< s(811) s(819) =< s(814) s(820) =< aux(117) s(821) =< s(816) with precondition: [Out=0,V1>=0,V>=0] * Chain [79]: 3*s(947)+3*s(948)+18*s(949)+30*s(950)+21*s(951)+3*s(952)+3*s(953)+3*s(959)+3*s(960)+3*s(962)+12*s(964)+24*s(965)+90*s(966)+18*s(967)+198*s(968)+5*s(975)+5*s(976)+30*s(977)+50*s(978)+37*s(979)+5*s(980)+5*s(981)+5*s(987)+5*s(988)+5*s(990)+20*s(992)+40*s(993)+150*s(994)+30*s(995)+330*s(996)+1*s(1139)+1 Such that:s(1139) =< 2 aux(129) =< V1 aux(130) =< V1/2 aux(131) =< 2/3*V1 aux(132) =< 2/5*V1 aux(133) =< 3/5*V1 aux(134) =< 3/7*V1 aux(135) =< V aux(136) =< V/2 aux(137) =< 2/3*V aux(138) =< 2/5*V aux(139) =< 3/5*V aux(140) =< 3/7*V s(975) =< aux(135) s(976) =< aux(135) s(977) =< aux(135) s(978) =< aux(135) s(979) =< aux(135) s(980) =< aux(135) s(981) =< aux(135) s(977) =< aux(136) s(978) =< aux(136) s(980) =< aux(136) s(978) =< aux(137) s(980) =< aux(137) s(981) =< aux(137) s(980) =< aux(138) s(976) =< aux(139) s(975) =< aux(140) s(982) =< aux(135)+1 s(983) =< aux(135)+2 s(984) =< aux(135) s(985) =< s(979)*s(982) s(986) =< s(979)*s(983) s(987) =< s(978)*s(984) s(988) =< s(980)*s(984) s(989) =< s(978)*s(982) s(990) =< s(977)*s(984) s(991) =< s(977)*aux(135) s(992) =< s(985) s(993) =< s(986) s(994) =< s(989) s(995) =< aux(137) s(996) =< s(991) s(947) =< aux(129) s(948) =< aux(129) s(949) =< aux(129) s(950) =< aux(129) s(951) =< aux(129) s(952) =< aux(129) s(953) =< aux(129) s(949) =< aux(130) s(950) =< aux(130) s(952) =< aux(130) s(950) =< aux(131) s(952) =< aux(131) s(953) =< aux(131) s(952) =< aux(132) s(948) =< aux(133) s(947) =< aux(134) s(954) =< aux(129)+1 s(955) =< aux(129)+2 s(956) =< aux(129) s(957) =< s(951)*s(954) s(958) =< s(951)*s(955) s(959) =< s(950)*s(956) s(960) =< s(952)*s(956) s(961) =< s(950)*s(954) s(962) =< s(949)*s(956) s(963) =< s(949)*aux(129) s(964) =< s(957) s(965) =< s(958) s(966) =< s(961) s(967) =< aux(131) s(968) =< s(963) with precondition: [Out=1,V1>=0,V>=0] * Chain [78]: 2*s(1174)+2*s(1175)+12*s(1176)+20*s(1177)+14*s(1178)+2*s(1179)+2*s(1180)+2*s(1186)+2*s(1187)+2*s(1189)+8*s(1191)+16*s(1192)+60*s(1193)+12*s(1194)+132*s(1195)+4*s(1202)+4*s(1203)+24*s(1204)+40*s(1205)+29*s(1206)+4*s(1207)+4*s(1208)+4*s(1214)+4*s(1215)+4*s(1217)+16*s(1219)+32*s(1220)+120*s(1221)+24*s(1222)+264*s(1223)+1*s(1309)+1 Such that:s(1309) =< 2 aux(142) =< V1 aux(143) =< V1/2 aux(144) =< 2/3*V1 aux(145) =< 2/5*V1 aux(146) =< 3/5*V1 aux(147) =< 3/7*V1 aux(148) =< V aux(149) =< V/2 aux(150) =< 2/3*V aux(151) =< 2/5*V aux(152) =< 3/5*V aux(153) =< 3/7*V s(1202) =< aux(148) s(1203) =< aux(148) s(1204) =< aux(148) s(1205) =< aux(148) s(1206) =< aux(148) s(1207) =< aux(148) s(1208) =< aux(148) s(1204) =< aux(149) s(1205) =< aux(149) s(1207) =< aux(149) s(1205) =< aux(150) s(1207) =< aux(150) s(1208) =< aux(150) s(1207) =< aux(151) s(1203) =< aux(152) s(1202) =< aux(153) s(1209) =< aux(148)+1 s(1210) =< aux(148)+2 s(1211) =< aux(148) s(1212) =< s(1206)*s(1209) s(1213) =< s(1206)*s(1210) s(1214) =< s(1205)*s(1211) s(1215) =< s(1207)*s(1211) s(1216) =< s(1205)*s(1209) s(1217) =< s(1204)*s(1211) s(1218) =< s(1204)*aux(148) s(1219) =< s(1212) s(1220) =< s(1213) s(1221) =< s(1216) s(1222) =< aux(150) s(1223) =< s(1218) s(1174) =< aux(142) s(1175) =< aux(142) s(1176) =< aux(142) s(1177) =< aux(142) s(1178) =< aux(142) s(1179) =< aux(142) s(1180) =< aux(142) s(1176) =< aux(143) s(1177) =< aux(143) s(1179) =< aux(143) s(1177) =< aux(144) s(1179) =< aux(144) s(1180) =< aux(144) s(1179) =< aux(145) s(1175) =< aux(146) s(1174) =< aux(147) s(1181) =< aux(142)+1 s(1182) =< aux(142)+2 s(1183) =< aux(142) s(1184) =< s(1178)*s(1181) s(1185) =< s(1178)*s(1182) s(1186) =< s(1177)*s(1183) s(1187) =< s(1179)*s(1183) s(1188) =< s(1177)*s(1181) s(1189) =< s(1176)*s(1183) s(1190) =< s(1176)*aux(142) s(1191) =< s(1184) s(1192) =< s(1185) s(1193) =< s(1188) s(1194) =< aux(144) s(1195) =< s(1190) with precondition: [Out=2,V1>=0,V>=1] * Chain [77]: 1*s(1344)+1*s(1345)+6*s(1346)+10*s(1347)+7*s(1348)+1*s(1349)+1*s(1350)+1*s(1356)+1*s(1357)+1*s(1359)+4*s(1361)+8*s(1362)+30*s(1363)+6*s(1364)+66*s(1365)+2*s(1366)+0 Such that:s(1338) =< V1 s(1339) =< V1/2 s(1340) =< 2/3*V1 s(1341) =< 2/5*V1 s(1342) =< 3/5*V1 s(1343) =< 3/7*V1 aux(154) =< 2 s(1366) =< aux(154) s(1344) =< s(1338) s(1345) =< s(1338) s(1346) =< s(1338) s(1347) =< s(1338) s(1348) =< s(1338) s(1349) =< s(1338) s(1350) =< s(1338) s(1346) =< s(1339) s(1347) =< s(1339) s(1349) =< s(1339) s(1347) =< s(1340) s(1349) =< s(1340) s(1350) =< s(1340) s(1349) =< s(1341) s(1345) =< s(1342) s(1344) =< s(1343) s(1351) =< s(1338)+1 s(1352) =< s(1338)+2 s(1353) =< s(1338) s(1354) =< s(1348)*s(1351) s(1355) =< s(1348)*s(1352) s(1356) =< s(1347)*s(1353) s(1357) =< s(1349)*s(1353) s(1358) =< s(1347)*s(1351) s(1359) =< s(1346)*s(1353) s(1360) =< s(1346)*s(1338) s(1361) =< s(1354) s(1362) =< s(1355) s(1363) =< s(1358) s(1364) =< s(1340) s(1365) =< s(1360) with precondition: [V=2,Out=0,V1>=0] * Chain [76]: 1*s(1374)+1*s(1375)+6*s(1376)+10*s(1377)+7*s(1378)+1*s(1379)+1*s(1380)+1*s(1386)+1*s(1387)+1*s(1389)+4*s(1391)+8*s(1392)+30*s(1393)+6*s(1394)+66*s(1395)+1*s(1396)+1 Such that:s(1396) =< 2 s(1368) =< V1 s(1369) =< V1/2 s(1370) =< 2/3*V1 s(1371) =< 2/5*V1 s(1372) =< 3/5*V1 s(1373) =< 3/7*V1 s(1374) =< s(1368) s(1375) =< s(1368) s(1376) =< s(1368) s(1377) =< s(1368) s(1378) =< s(1368) s(1379) =< s(1368) s(1380) =< s(1368) s(1376) =< s(1369) s(1377) =< s(1369) s(1379) =< s(1369) s(1377) =< s(1370) s(1379) =< s(1370) s(1380) =< s(1370) s(1379) =< s(1371) s(1375) =< s(1372) s(1374) =< s(1373) s(1381) =< s(1368)+1 s(1382) =< s(1368)+2 s(1383) =< s(1368) s(1384) =< s(1378)*s(1381) s(1385) =< s(1378)*s(1382) s(1386) =< s(1377)*s(1383) s(1387) =< s(1379)*s(1383) s(1388) =< s(1377)*s(1381) s(1389) =< s(1376)*s(1383) s(1390) =< s(1376)*s(1368) s(1391) =< s(1384) s(1392) =< s(1385) s(1393) =< s(1388) s(1394) =< s(1370) s(1395) =< s(1390) with precondition: [V=2,Out=1,V1>=2] * Chain [75]: 2*s(1403)+2*s(1404)+12*s(1405)+20*s(1406)+14*s(1407)+2*s(1408)+2*s(1409)+2*s(1415)+2*s(1416)+2*s(1418)+8*s(1420)+16*s(1421)+60*s(1422)+12*s(1423)+132*s(1424)+1*s(1453)+1 Such that:s(1453) =< 1 aux(155) =< V1 aux(156) =< V1/2 aux(157) =< 2/3*V1 aux(158) =< 2/5*V1 aux(159) =< 3/5*V1 aux(160) =< 3/7*V1 s(1403) =< aux(155) s(1404) =< aux(155) s(1405) =< aux(155) s(1406) =< aux(155) s(1407) =< aux(155) s(1408) =< aux(155) s(1409) =< aux(155) s(1405) =< aux(156) s(1406) =< aux(156) s(1408) =< aux(156) s(1406) =< aux(157) s(1408) =< aux(157) s(1409) =< aux(157) s(1408) =< aux(158) s(1404) =< aux(159) s(1403) =< aux(160) s(1410) =< aux(155)+1 s(1411) =< aux(155)+2 s(1412) =< aux(155) s(1413) =< s(1407)*s(1410) s(1414) =< s(1407)*s(1411) s(1415) =< s(1406)*s(1412) s(1416) =< s(1408)*s(1412) s(1417) =< s(1406)*s(1410) s(1418) =< s(1405)*s(1412) s(1419) =< s(1405)*aux(155) s(1420) =< s(1413) s(1421) =< s(1414) s(1422) =< s(1417) s(1423) =< aux(157) s(1424) =< s(1419) with precondition: [V=2,Out=2,V1>=0] #### Cost of chains of fun4(Out): * Chain [82]: 0 with precondition: [Out=0] * Chain [81]: 0 with precondition: [Out=1] #### Cost of chains of fun5(Out): * Chain [84]: 0 with precondition: [Out=0] * Chain [83]: 0 with precondition: [Out=2] #### Cost of chains of fun6(V1,V,V12,Out): * Chain [92]: 8*s(1719)+8*s(1720)+48*s(1721)+80*s(1722)+56*s(1723)+8*s(1724)+8*s(1725)+8*s(1731)+8*s(1732)+8*s(1734)+32*s(1736)+64*s(1737)+240*s(1738)+48*s(1739)+528*s(1740)+7*s(1747)+7*s(1748)+42*s(1749)+70*s(1750)+49*s(1751)+7*s(1752)+7*s(1753)+7*s(1759)+7*s(1760)+7*s(1762)+28*s(1764)+56*s(1765)+210*s(1766)+42*s(1767)+462*s(1768)+9*s(1775)+9*s(1776)+54*s(1777)+90*s(1778)+63*s(1779)+9*s(1780)+9*s(1781)+9*s(1787)+9*s(1788)+9*s(1790)+36*s(1792)+72*s(1793)+270*s(1794)+54*s(1795)+594*s(1796)+1 Such that:aux(181) =< V1 aux(182) =< V1/2 aux(183) =< 2/3*V1 aux(184) =< 2/5*V1 aux(185) =< 3/5*V1 aux(186) =< 3/7*V1 aux(187) =< V aux(188) =< V/2 aux(189) =< 2/3*V aux(190) =< 2/5*V aux(191) =< 3/5*V aux(192) =< 3/7*V aux(193) =< V12 aux(194) =< V12/2 aux(195) =< 2/3*V12 aux(196) =< 2/5*V12 aux(197) =< 3/5*V12 aux(198) =< 3/7*V12 s(1775) =< aux(193) s(1776) =< aux(193) s(1777) =< aux(193) s(1778) =< aux(193) s(1779) =< aux(193) s(1780) =< aux(193) s(1781) =< aux(193) s(1777) =< aux(194) s(1778) =< aux(194) s(1780) =< aux(194) s(1778) =< aux(195) s(1780) =< aux(195) s(1781) =< aux(195) s(1780) =< aux(196) s(1776) =< aux(197) s(1775) =< aux(198) s(1782) =< aux(193)+1 s(1783) =< aux(193)+2 s(1784) =< aux(193) s(1785) =< s(1779)*s(1782) s(1786) =< s(1779)*s(1783) s(1787) =< s(1778)*s(1784) s(1788) =< s(1780)*s(1784) s(1789) =< s(1778)*s(1782) s(1790) =< s(1777)*s(1784) s(1791) =< s(1777)*aux(193) s(1792) =< s(1785) s(1793) =< s(1786) s(1794) =< s(1789) s(1795) =< aux(195) s(1796) =< s(1791) s(1747) =< aux(187) s(1748) =< aux(187) s(1749) =< aux(187) s(1750) =< aux(187) s(1751) =< aux(187) s(1752) =< aux(187) s(1753) =< aux(187) s(1749) =< aux(188) s(1750) =< aux(188) s(1752) =< aux(188) s(1750) =< aux(189) s(1752) =< aux(189) s(1753) =< aux(189) s(1752) =< aux(190) s(1748) =< aux(191) s(1747) =< aux(192) s(1754) =< aux(187)+1 s(1755) =< aux(187)+2 s(1756) =< aux(187) s(1757) =< s(1751)*s(1754) s(1758) =< s(1751)*s(1755) s(1759) =< s(1750)*s(1756) s(1760) =< s(1752)*s(1756) s(1761) =< s(1750)*s(1754) s(1762) =< s(1749)*s(1756) s(1763) =< s(1749)*aux(187) s(1764) =< s(1757) s(1765) =< s(1758) s(1766) =< s(1761) s(1767) =< aux(189) s(1768) =< s(1763) s(1719) =< aux(181) s(1720) =< aux(181) s(1721) =< aux(181) s(1722) =< aux(181) s(1723) =< aux(181) s(1724) =< aux(181) s(1725) =< aux(181) s(1721) =< aux(182) s(1722) =< aux(182) s(1724) =< aux(182) s(1722) =< aux(183) s(1724) =< aux(183) s(1725) =< aux(183) s(1724) =< aux(184) s(1720) =< aux(185) s(1719) =< aux(186) s(1726) =< aux(181)+1 s(1727) =< aux(181)+2 s(1728) =< aux(181) s(1729) =< s(1723)*s(1726) s(1730) =< s(1723)*s(1727) s(1731) =< s(1722)*s(1728) s(1732) =< s(1724)*s(1728) s(1733) =< s(1722)*s(1726) s(1734) =< s(1721)*s(1728) s(1735) =< s(1721)*aux(181) s(1736) =< s(1729) s(1737) =< s(1730) s(1738) =< s(1733) s(1739) =< aux(183) s(1740) =< s(1735) with precondition: [Out=0,V1>=0,V>=0,V12>=0] * Chain [91]: 2*s(2391)+2*s(2392)+12*s(2393)+20*s(2394)+14*s(2395)+2*s(2396)+2*s(2397)+2*s(2403)+2*s(2404)+2*s(2406)+8*s(2408)+16*s(2409)+60*s(2410)+12*s(2411)+132*s(2412)+4*s(2419)+4*s(2420)+24*s(2421)+40*s(2422)+28*s(2423)+4*s(2424)+4*s(2425)+4*s(2431)+4*s(2432)+4*s(2434)+16*s(2436)+32*s(2437)+120*s(2438)+24*s(2439)+264*s(2440)+3*s(2447)+3*s(2448)+18*s(2449)+30*s(2450)+21*s(2451)+3*s(2452)+3*s(2453)+3*s(2459)+3*s(2460)+3*s(2462)+12*s(2464)+24*s(2465)+90*s(2466)+18*s(2467)+198*s(2468)+1 Such that:aux(199) =< V1 aux(200) =< V1/2 aux(201) =< 2/3*V1 aux(202) =< 2/5*V1 aux(203) =< 3/5*V1 aux(204) =< 3/7*V1 aux(205) =< V aux(206) =< V/2 aux(207) =< 2/3*V aux(208) =< 2/5*V aux(209) =< 3/5*V aux(210) =< 3/7*V aux(211) =< V12 aux(212) =< V12/2 aux(213) =< 2/3*V12 aux(214) =< 2/5*V12 aux(215) =< 3/5*V12 aux(216) =< 3/7*V12 s(2447) =< aux(211) s(2448) =< aux(211) s(2449) =< aux(211) s(2450) =< aux(211) s(2451) =< aux(211) s(2452) =< aux(211) s(2453) =< aux(211) s(2449) =< aux(212) s(2450) =< aux(212) s(2452) =< aux(212) s(2450) =< aux(213) s(2452) =< aux(213) s(2453) =< aux(213) s(2452) =< aux(214) s(2448) =< aux(215) s(2447) =< aux(216) s(2454) =< aux(211)+1 s(2455) =< aux(211)+2 s(2456) =< aux(211) s(2457) =< s(2451)*s(2454) s(2458) =< s(2451)*s(2455) s(2459) =< s(2450)*s(2456) s(2460) =< s(2452)*s(2456) s(2461) =< s(2450)*s(2454) s(2462) =< s(2449)*s(2456) s(2463) =< s(2449)*aux(211) s(2464) =< s(2457) s(2465) =< s(2458) s(2466) =< s(2461) s(2467) =< aux(213) s(2468) =< s(2463) s(2419) =< aux(205) s(2420) =< aux(205) s(2421) =< aux(205) s(2422) =< aux(205) s(2423) =< aux(205) s(2424) =< aux(205) s(2425) =< aux(205) s(2421) =< aux(206) s(2422) =< aux(206) s(2424) =< aux(206) s(2422) =< aux(207) s(2424) =< aux(207) s(2425) =< aux(207) s(2424) =< aux(208) s(2420) =< aux(209) s(2419) =< aux(210) s(2426) =< aux(205)+1 s(2427) =< aux(205)+2 s(2428) =< aux(205) s(2429) =< s(2423)*s(2426) s(2430) =< s(2423)*s(2427) s(2431) =< s(2422)*s(2428) s(2432) =< s(2424)*s(2428) s(2433) =< s(2422)*s(2426) s(2434) =< s(2421)*s(2428) s(2435) =< s(2421)*aux(205) s(2436) =< s(2429) s(2437) =< s(2430) s(2438) =< s(2433) s(2439) =< aux(207) s(2440) =< s(2435) s(2391) =< aux(199) s(2392) =< aux(199) s(2393) =< aux(199) s(2394) =< aux(199) s(2395) =< aux(199) s(2396) =< aux(199) s(2397) =< aux(199) s(2393) =< aux(200) s(2394) =< aux(200) s(2396) =< aux(200) s(2394) =< aux(201) s(2396) =< aux(201) s(2397) =< aux(201) s(2396) =< aux(202) s(2392) =< aux(203) s(2391) =< aux(204) s(2398) =< aux(199)+1 s(2399) =< aux(199)+2 s(2400) =< aux(199) s(2401) =< s(2395)*s(2398) s(2402) =< s(2395)*s(2399) s(2403) =< s(2394)*s(2400) s(2404) =< s(2396)*s(2400) s(2405) =< s(2394)*s(2398) s(2406) =< s(2393)*s(2400) s(2407) =< s(2393)*aux(199) s(2408) =< s(2401) s(2409) =< s(2402) s(2410) =< s(2405) s(2411) =< aux(201) s(2412) =< s(2407) with precondition: [V1>=2,V>=1,V12>=0,Out>=0,V>=Out] * Chain [90]: 3*s(2643)+3*s(2644)+18*s(2645)+30*s(2646)+21*s(2647)+3*s(2648)+3*s(2649)+3*s(2655)+3*s(2656)+3*s(2658)+12*s(2660)+24*s(2661)+90*s(2662)+18*s(2663)+198*s(2664)+3*s(2671)+3*s(2672)+18*s(2673)+30*s(2674)+21*s(2675)+3*s(2676)+3*s(2677)+3*s(2683)+3*s(2684)+3*s(2686)+12*s(2688)+24*s(2689)+90*s(2690)+18*s(2691)+198*s(2692)+1 Such that:aux(217) =< V1 aux(218) =< V1/2 aux(219) =< 2/3*V1 aux(220) =< 2/5*V1 aux(221) =< 3/5*V1 aux(222) =< 3/7*V1 aux(223) =< V aux(224) =< V/2 aux(225) =< 2/3*V aux(226) =< 2/5*V aux(227) =< 3/5*V aux(228) =< 3/7*V s(2671) =< aux(223) s(2672) =< aux(223) s(2673) =< aux(223) s(2674) =< aux(223) s(2675) =< aux(223) s(2676) =< aux(223) s(2677) =< aux(223) s(2673) =< aux(224) s(2674) =< aux(224) s(2676) =< aux(224) s(2674) =< aux(225) s(2676) =< aux(225) s(2677) =< aux(225) s(2676) =< aux(226) s(2672) =< aux(227) s(2671) =< aux(228) s(2678) =< aux(223)+1 s(2679) =< aux(223)+2 s(2680) =< aux(223) s(2681) =< s(2675)*s(2678) s(2682) =< s(2675)*s(2679) s(2683) =< s(2674)*s(2680) s(2684) =< s(2676)*s(2680) s(2685) =< s(2674)*s(2678) s(2686) =< s(2673)*s(2680) s(2687) =< s(2673)*aux(223) s(2688) =< s(2681) s(2689) =< s(2682) s(2690) =< s(2685) s(2691) =< aux(225) s(2692) =< s(2687) s(2643) =< aux(217) s(2644) =< aux(217) s(2645) =< aux(217) s(2646) =< aux(217) s(2647) =< aux(217) s(2648) =< aux(217) s(2649) =< aux(217) s(2645) =< aux(218) s(2646) =< aux(218) s(2648) =< aux(218) s(2646) =< aux(219) s(2648) =< aux(219) s(2649) =< aux(219) s(2648) =< aux(220) s(2644) =< aux(221) s(2643) =< aux(222) s(2650) =< aux(217)+1 s(2651) =< aux(217)+2 s(2652) =< aux(217) s(2653) =< s(2647)*s(2650) s(2654) =< s(2647)*s(2651) s(2655) =< s(2646)*s(2652) s(2656) =< s(2648)*s(2652) s(2657) =< s(2646)*s(2650) s(2658) =< s(2645)*s(2652) s(2659) =< s(2645)*aux(217) s(2660) =< s(2653) s(2661) =< s(2654) s(2662) =< s(2657) s(2663) =< aux(219) s(2664) =< s(2659) with precondition: [V12=2,Out=0,V1>=0,V>=0] * Chain [89]: 1*s(2811)+1*s(2812)+6*s(2813)+10*s(2814)+7*s(2815)+1*s(2816)+1*s(2817)+1*s(2823)+1*s(2824)+1*s(2826)+4*s(2828)+8*s(2829)+30*s(2830)+6*s(2831)+66*s(2832)+2*s(2839)+2*s(2840)+12*s(2841)+20*s(2842)+14*s(2843)+2*s(2844)+2*s(2845)+2*s(2851)+2*s(2852)+2*s(2854)+8*s(2856)+16*s(2857)+60*s(2858)+12*s(2859)+132*s(2860)+1 Such that:s(2805) =< V1 s(2806) =< V1/2 s(2807) =< 2/3*V1 s(2808) =< 2/5*V1 s(2809) =< 3/5*V1 s(2810) =< 3/7*V1 aux(229) =< V aux(230) =< V/2 aux(231) =< 2/3*V aux(232) =< 2/5*V aux(233) =< 3/5*V aux(234) =< 3/7*V s(2839) =< aux(229) s(2840) =< aux(229) s(2841) =< aux(229) s(2842) =< aux(229) s(2843) =< aux(229) s(2844) =< aux(229) s(2845) =< aux(229) s(2841) =< aux(230) s(2842) =< aux(230) s(2844) =< aux(230) s(2842) =< aux(231) s(2844) =< aux(231) s(2845) =< aux(231) s(2844) =< aux(232) s(2840) =< aux(233) s(2839) =< aux(234) s(2846) =< aux(229)+1 s(2847) =< aux(229)+2 s(2848) =< aux(229) s(2849) =< s(2843)*s(2846) s(2850) =< s(2843)*s(2847) s(2851) =< s(2842)*s(2848) s(2852) =< s(2844)*s(2848) s(2853) =< s(2842)*s(2846) s(2854) =< s(2841)*s(2848) s(2855) =< s(2841)*aux(229) s(2856) =< s(2849) s(2857) =< s(2850) s(2858) =< s(2853) s(2859) =< aux(231) s(2860) =< s(2855) s(2811) =< s(2805) s(2812) =< s(2805) s(2813) =< s(2805) s(2814) =< s(2805) s(2815) =< s(2805) s(2816) =< s(2805) s(2817) =< s(2805) s(2813) =< s(2806) s(2814) =< s(2806) s(2816) =< s(2806) s(2814) =< s(2807) s(2816) =< s(2807) s(2817) =< s(2807) s(2816) =< s(2808) s(2812) =< s(2809) s(2811) =< s(2810) s(2818) =< s(2805)+1 s(2819) =< s(2805)+2 s(2820) =< s(2805) s(2821) =< s(2815)*s(2818) s(2822) =< s(2815)*s(2819) s(2823) =< s(2814)*s(2820) s(2824) =< s(2816)*s(2820) s(2825) =< s(2814)*s(2818) s(2826) =< s(2813)*s(2820) s(2827) =< s(2813)*s(2805) s(2828) =< s(2821) s(2829) =< s(2822) s(2830) =< s(2825) s(2831) =< s(2807) s(2832) =< s(2827) with precondition: [V12=2,V1>=2,V>=1,Out>=0,V>=Out] * Chain [88]: 4*s(2895)+4*s(2896)+24*s(2897)+40*s(2898)+28*s(2899)+4*s(2900)+4*s(2901)+4*s(2907)+4*s(2908)+4*s(2910)+16*s(2912)+32*s(2913)+120*s(2914)+24*s(2915)+264*s(2916)+2*s(2923)+2*s(2924)+12*s(2925)+20*s(2926)+14*s(2927)+2*s(2928)+2*s(2929)+2*s(2935)+2*s(2936)+2*s(2938)+8*s(2940)+16*s(2941)+60*s(2942)+12*s(2943)+132*s(2944)+1 Such that:aux(235) =< V1 aux(236) =< V1/2 aux(237) =< 2/3*V1 aux(238) =< 2/5*V1 aux(239) =< 3/5*V1 aux(240) =< 3/7*V1 aux(241) =< V12 aux(242) =< V12/2 aux(243) =< 2/3*V12 aux(244) =< 2/5*V12 aux(245) =< 3/5*V12 aux(246) =< 3/7*V12 s(2923) =< aux(241) s(2924) =< aux(241) s(2925) =< aux(241) s(2926) =< aux(241) s(2927) =< aux(241) s(2928) =< aux(241) s(2929) =< aux(241) s(2925) =< aux(242) s(2926) =< aux(242) s(2928) =< aux(242) s(2926) =< aux(243) s(2928) =< aux(243) s(2929) =< aux(243) s(2928) =< aux(244) s(2924) =< aux(245) s(2923) =< aux(246) s(2930) =< aux(241)+1 s(2931) =< aux(241)+2 s(2932) =< aux(241) s(2933) =< s(2927)*s(2930) s(2934) =< s(2927)*s(2931) s(2935) =< s(2926)*s(2932) s(2936) =< s(2928)*s(2932) s(2937) =< s(2926)*s(2930) s(2938) =< s(2925)*s(2932) s(2939) =< s(2925)*aux(241) s(2940) =< s(2933) s(2941) =< s(2934) s(2942) =< s(2937) s(2943) =< aux(243) s(2944) =< s(2939) s(2895) =< aux(235) s(2896) =< aux(235) s(2897) =< aux(235) s(2898) =< aux(235) s(2899) =< aux(235) s(2900) =< aux(235) s(2901) =< aux(235) s(2897) =< aux(236) s(2898) =< aux(236) s(2900) =< aux(236) s(2898) =< aux(237) s(2900) =< aux(237) s(2901) =< aux(237) s(2900) =< aux(238) s(2896) =< aux(239) s(2895) =< aux(240) s(2902) =< aux(235)+1 s(2903) =< aux(235)+2 s(2904) =< aux(235) s(2905) =< s(2899)*s(2902) s(2906) =< s(2899)*s(2903) s(2907) =< s(2898)*s(2904) s(2908) =< s(2900)*s(2904) s(2909) =< s(2898)*s(2902) s(2910) =< s(2897)*s(2904) s(2911) =< s(2897)*aux(235) s(2912) =< s(2905) s(2913) =< s(2906) s(2914) =< s(2909) s(2915) =< aux(237) s(2916) =< s(2911) with precondition: [V=2,Out=0,V1>=0,V12>=0] * Chain [87]: 5*s(3063)+5*s(3064)+30*s(3065)+50*s(3066)+35*s(3067)+5*s(3068)+5*s(3069)+5*s(3075)+5*s(3076)+5*s(3078)+20*s(3080)+40*s(3081)+150*s(3082)+30*s(3083)+330*s(3084)+1*s(3091)+1*s(3092)+6*s(3093)+10*s(3094)+7*s(3095)+1*s(3096)+1*s(3097)+1*s(3103)+1*s(3104)+1*s(3106)+4*s(3108)+8*s(3109)+30*s(3110)+6*s(3111)+66*s(3112)+3*s(3119)+3*s(3120)+18*s(3121)+30*s(3122)+21*s(3123)+3*s(3124)+3*s(3125)+3*s(3131)+3*s(3132)+3*s(3134)+12*s(3136)+24*s(3137)+90*s(3138)+18*s(3139)+198*s(3140)+1 Such that:s(3085) =< V s(3086) =< V/2 s(3087) =< 2/3*V s(3088) =< 2/5*V s(3089) =< 3/5*V s(3090) =< 3/7*V aux(247) =< V1 aux(248) =< V1/2 aux(249) =< 2/3*V1 aux(250) =< 2/5*V1 aux(251) =< 3/5*V1 aux(252) =< 3/7*V1 aux(253) =< V12 aux(254) =< V12/2 aux(255) =< 2/3*V12 aux(256) =< 2/5*V12 aux(257) =< 3/5*V12 aux(258) =< 3/7*V12 s(3119) =< aux(253) s(3120) =< aux(253) s(3121) =< aux(253) s(3122) =< aux(253) s(3123) =< aux(253) s(3124) =< aux(253) s(3125) =< aux(253) s(3121) =< aux(254) s(3122) =< aux(254) s(3124) =< aux(254) s(3122) =< aux(255) s(3124) =< aux(255) s(3125) =< aux(255) s(3124) =< aux(256) s(3120) =< aux(257) s(3119) =< aux(258) s(3126) =< aux(253)+1 s(3127) =< aux(253)+2 s(3128) =< aux(253) s(3129) =< s(3123)*s(3126) s(3130) =< s(3123)*s(3127) s(3131) =< s(3122)*s(3128) s(3132) =< s(3124)*s(3128) s(3133) =< s(3122)*s(3126) s(3134) =< s(3121)*s(3128) s(3135) =< s(3121)*aux(253) s(3136) =< s(3129) s(3137) =< s(3130) s(3138) =< s(3133) s(3139) =< aux(255) s(3140) =< s(3135) s(3091) =< s(3085) s(3092) =< s(3085) s(3093) =< s(3085) s(3094) =< s(3085) s(3095) =< s(3085) s(3096) =< s(3085) s(3097) =< s(3085) s(3093) =< s(3086) s(3094) =< s(3086) s(3096) =< s(3086) s(3094) =< s(3087) s(3096) =< s(3087) s(3097) =< s(3087) s(3096) =< s(3088) s(3092) =< s(3089) s(3091) =< s(3090) s(3098) =< s(3085)+1 s(3099) =< s(3085)+2 s(3100) =< s(3085) s(3101) =< s(3095)*s(3098) s(3102) =< s(3095)*s(3099) s(3103) =< s(3094)*s(3100) s(3104) =< s(3096)*s(3100) s(3105) =< s(3094)*s(3098) s(3106) =< s(3093)*s(3100) s(3107) =< s(3093)*s(3085) s(3108) =< s(3101) s(3109) =< s(3102) s(3110) =< s(3105) s(3111) =< s(3087) s(3112) =< s(3107) s(3063) =< aux(247) s(3064) =< aux(247) s(3065) =< aux(247) s(3066) =< aux(247) s(3067) =< aux(247) s(3068) =< aux(247) s(3069) =< aux(247) s(3065) =< aux(248) s(3066) =< aux(248) s(3068) =< aux(248) s(3066) =< aux(249) s(3068) =< aux(249) s(3069) =< aux(249) s(3068) =< aux(250) s(3064) =< aux(251) s(3063) =< aux(252) s(3070) =< aux(247)+1 s(3071) =< aux(247)+2 s(3072) =< aux(247) s(3073) =< s(3067)*s(3070) s(3074) =< s(3067)*s(3071) s(3075) =< s(3066)*s(3072) s(3076) =< s(3068)*s(3072) s(3077) =< s(3066)*s(3070) s(3078) =< s(3065)*s(3072) s(3079) =< s(3065)*aux(247) s(3080) =< s(3073) s(3081) =< s(3074) s(3082) =< s(3077) s(3083) =< aux(249) s(3084) =< s(3079) with precondition: [V1>=1,V>=0,V12>=1,Out>=0,V12>=Out] * Chain [86]: 2*s(3315)+2*s(3316)+12*s(3317)+20*s(3318)+14*s(3319)+2*s(3320)+2*s(3321)+2*s(3327)+2*s(3328)+2*s(3330)+8*s(3332)+16*s(3333)+60*s(3334)+12*s(3335)+132*s(3336)+1*s(3343)+1*s(3344)+6*s(3345)+10*s(3346)+7*s(3347)+1*s(3348)+1*s(3349)+1*s(3355)+1*s(3356)+1*s(3358)+4*s(3360)+8*s(3361)+30*s(3362)+6*s(3363)+66*s(3364)+1 Such that:s(3337) =< V12 s(3338) =< V12/2 s(3339) =< 2/3*V12 s(3340) =< 2/5*V12 s(3341) =< 3/5*V12 s(3342) =< 3/7*V12 aux(259) =< V1 aux(260) =< V1/2 aux(261) =< 2/3*V1 aux(262) =< 2/5*V1 aux(263) =< 3/5*V1 aux(264) =< 3/7*V1 s(3343) =< s(3337) s(3344) =< s(3337) s(3345) =< s(3337) s(3346) =< s(3337) s(3347) =< s(3337) s(3348) =< s(3337) s(3349) =< s(3337) s(3345) =< s(3338) s(3346) =< s(3338) s(3348) =< s(3338) s(3346) =< s(3339) s(3348) =< s(3339) s(3349) =< s(3339) s(3348) =< s(3340) s(3344) =< s(3341) s(3343) =< s(3342) s(3350) =< s(3337)+1 s(3351) =< s(3337)+2 s(3352) =< s(3337) s(3353) =< s(3347)*s(3350) s(3354) =< s(3347)*s(3351) s(3355) =< s(3346)*s(3352) s(3356) =< s(3348)*s(3352) s(3357) =< s(3346)*s(3350) s(3358) =< s(3345)*s(3352) s(3359) =< s(3345)*s(3337) s(3360) =< s(3353) s(3361) =< s(3354) s(3362) =< s(3357) s(3363) =< s(3339) s(3364) =< s(3359) s(3315) =< aux(259) s(3316) =< aux(259) s(3317) =< aux(259) s(3318) =< aux(259) s(3319) =< aux(259) s(3320) =< aux(259) s(3321) =< aux(259) s(3317) =< aux(260) s(3318) =< aux(260) s(3320) =< aux(260) s(3318) =< aux(261) s(3320) =< aux(261) s(3321) =< aux(261) s(3320) =< aux(262) s(3316) =< aux(263) s(3315) =< aux(264) s(3322) =< aux(259)+1 s(3323) =< aux(259)+2 s(3324) =< aux(259) s(3325) =< s(3319)*s(3322) s(3326) =< s(3319)*s(3323) s(3327) =< s(3318)*s(3324) s(3328) =< s(3320)*s(3324) s(3329) =< s(3318)*s(3322) s(3330) =< s(3317)*s(3324) s(3331) =< s(3317)*aux(259) s(3332) =< s(3325) s(3333) =< s(3326) s(3334) =< s(3329) s(3335) =< aux(261) s(3336) =< s(3331) with precondition: [V=2,Out=2,V1>=2,V12>=0] * Chain [85]: 2*s(3399)+2*s(3400)+12*s(3401)+20*s(3402)+14*s(3403)+2*s(3404)+2*s(3405)+2*s(3411)+2*s(3412)+2*s(3414)+8*s(3416)+16*s(3417)+60*s(3418)+12*s(3419)+132*s(3420)+1*s(3427)+1*s(3428)+6*s(3429)+10*s(3430)+7*s(3431)+1*s(3432)+1*s(3433)+1*s(3439)+1*s(3440)+1*s(3442)+4*s(3444)+8*s(3445)+30*s(3446)+6*s(3447)+66*s(3448)+1 Such that:s(3421) =< V s(3422) =< V/2 s(3423) =< 2/3*V s(3424) =< 2/5*V s(3425) =< 3/5*V s(3426) =< 3/7*V aux(265) =< V1 aux(266) =< V1/2 aux(267) =< 2/3*V1 aux(268) =< 2/5*V1 aux(269) =< 3/5*V1 aux(270) =< 3/7*V1 s(3427) =< s(3421) s(3428) =< s(3421) s(3429) =< s(3421) s(3430) =< s(3421) s(3431) =< s(3421) s(3432) =< s(3421) s(3433) =< s(3421) s(3429) =< s(3422) s(3430) =< s(3422) s(3432) =< s(3422) s(3430) =< s(3423) s(3432) =< s(3423) s(3433) =< s(3423) s(3432) =< s(3424) s(3428) =< s(3425) s(3427) =< s(3426) s(3434) =< s(3421)+1 s(3435) =< s(3421)+2 s(3436) =< s(3421) s(3437) =< s(3431)*s(3434) s(3438) =< s(3431)*s(3435) s(3439) =< s(3430)*s(3436) s(3440) =< s(3432)*s(3436) s(3441) =< s(3430)*s(3434) s(3442) =< s(3429)*s(3436) s(3443) =< s(3429)*s(3421) s(3444) =< s(3437) s(3445) =< s(3438) s(3446) =< s(3441) s(3447) =< s(3423) s(3448) =< s(3443) s(3399) =< aux(265) s(3400) =< aux(265) s(3401) =< aux(265) s(3402) =< aux(265) s(3403) =< aux(265) s(3404) =< aux(265) s(3405) =< aux(265) s(3401) =< aux(266) s(3402) =< aux(266) s(3404) =< aux(266) s(3402) =< aux(267) s(3404) =< aux(267) s(3405) =< aux(267) s(3404) =< aux(268) s(3400) =< aux(269) s(3399) =< aux(270) s(3406) =< aux(265)+1 s(3407) =< aux(265)+2 s(3408) =< aux(265) s(3409) =< s(3403)*s(3406) s(3410) =< s(3403)*s(3407) s(3411) =< s(3402)*s(3408) s(3412) =< s(3404)*s(3408) s(3413) =< s(3402)*s(3406) s(3414) =< s(3401)*s(3408) s(3415) =< s(3401)*aux(265) s(3416) =< s(3409) s(3417) =< s(3410) s(3418) =< s(3413) s(3419) =< aux(267) s(3420) =< s(3415) with precondition: [V12=2,Out=2,V1>=1,V>=0] #### Cost of chains of fun7(V1,V,Out): * Chain [97]: 3*s(3903)+3*s(3904)+18*s(3905)+30*s(3906)+81*s(3907)+3*s(3908)+3*s(3909)+3*s(3915)+3*s(3916)+3*s(3918)+12*s(3920)+24*s(3921)+90*s(3922)+18*s(3923)+198*s(3924)+5*s(3931)+5*s(3932)+30*s(3933)+50*s(3934)+35*s(3935)+5*s(3936)+5*s(3937)+5*s(3943)+5*s(3944)+5*s(3946)+20*s(3948)+40*s(3949)+150*s(3950)+30*s(3951)+330*s(3952)+12*s(3956)+8*s(4017)+28*s(4018)+84*s(4113)+28*s(4148)+5 Such that:aux(314) =< 1 aux(315) =< 2 aux(316) =< V1 aux(317) =< V1+1 aux(318) =< V1/2 aux(319) =< 2/3*V1 aux(320) =< 2/5*V1 aux(321) =< 3/5*V1 aux(322) =< 3/7*V1 aux(323) =< V aux(324) =< V/2 aux(325) =< 2/3*V aux(326) =< 2/5*V aux(327) =< 3/5*V aux(328) =< 3/7*V s(3907) =< aux(316) s(3956) =< aux(314) s(3931) =< aux(323) s(3932) =< aux(323) s(3933) =< aux(323) s(3934) =< aux(323) s(3935) =< aux(323) s(3936) =< aux(323) s(3937) =< aux(323) s(3933) =< aux(324) s(3934) =< aux(324) s(3936) =< aux(324) s(3934) =< aux(325) s(3936) =< aux(325) s(3937) =< aux(325) s(3936) =< aux(326) s(3932) =< aux(327) s(3931) =< aux(328) s(3938) =< aux(323)+1 s(3939) =< aux(323)+2 s(3940) =< aux(323) s(3941) =< s(3935)*s(3938) s(3942) =< s(3935)*s(3939) s(3943) =< s(3934)*s(3940) s(3944) =< s(3936)*s(3940) s(3945) =< s(3934)*s(3938) s(3946) =< s(3933)*s(3940) s(3947) =< s(3933)*aux(323) s(3948) =< s(3941) s(3949) =< s(3942) s(3950) =< s(3945) s(3951) =< aux(325) s(3952) =< s(3947) s(3903) =< aux(316) s(3904) =< aux(316) s(3905) =< aux(316) s(3906) =< aux(316) s(3908) =< aux(316) s(3909) =< aux(316) s(3905) =< aux(318) s(3906) =< aux(318) s(3908) =< aux(318) s(3906) =< aux(319) s(3908) =< aux(319) s(3909) =< aux(319) s(3908) =< aux(320) s(3904) =< aux(321) s(3903) =< aux(322) s(3910) =< aux(316)+1 s(3911) =< aux(316)+2 s(3912) =< aux(316) s(3913) =< s(3907)*s(3910) s(3914) =< s(3907)*s(3911) s(3915) =< s(3906)*s(3912) s(3916) =< s(3908)*s(3912) s(3917) =< s(3906)*s(3910) s(3918) =< s(3905)*s(3912) s(3919) =< s(3905)*aux(316) s(3920) =< s(3913) s(3921) =< s(3914) s(3922) =< s(3917) s(3923) =< aux(319) s(3924) =< s(3919) s(4113) =< aux(315) s(4148) =< aux(315) s(4148) =< aux(314) s(4018) =< aux(316) s(4018) =< aux(317) s(4017) =< aux(317) with precondition: [V1>=1,V>=1,Out>=0,V1>=Out] * Chain [96]: 2*s(4165)+2*s(4166)+12*s(4167)+20*s(4168)+18*s(4169)+2*s(4170)+2*s(4171)+2*s(4177)+2*s(4178)+2*s(4180)+8*s(4182)+16*s(4183)+60*s(4184)+12*s(4185)+132*s(4186)+3*s(4193)+3*s(4194)+18*s(4195)+30*s(4196)+45*s(4197)+3*s(4198)+3*s(4199)+3*s(4205)+3*s(4206)+3*s(4208)+12*s(4210)+24*s(4211)+90*s(4212)+18*s(4213)+198*s(4214)+4*s(4281)+5 Such that:aux(335) =< 2 aux(336) =< V1 aux(337) =< V1/2 aux(338) =< 2/3*V1 aux(339) =< 2/5*V1 aux(340) =< 3/5*V1 aux(341) =< 3/7*V1 aux(342) =< V aux(343) =< V/2 aux(344) =< 2/3*V aux(345) =< 2/5*V aux(346) =< 3/5*V aux(347) =< 3/7*V s(4281) =< aux(335) s(4197) =< aux(342) s(4193) =< aux(342) s(4194) =< aux(342) s(4195) =< aux(342) s(4196) =< aux(342) s(4198) =< aux(342) s(4199) =< aux(342) s(4195) =< aux(343) s(4196) =< aux(343) s(4198) =< aux(343) s(4196) =< aux(344) s(4198) =< aux(344) s(4199) =< aux(344) s(4198) =< aux(345) s(4194) =< aux(346) s(4193) =< aux(347) s(4200) =< aux(342)+1 s(4201) =< aux(342)+2 s(4202) =< aux(342) s(4203) =< s(4197)*s(4200) s(4204) =< s(4197)*s(4201) s(4205) =< s(4196)*s(4202) s(4206) =< s(4198)*s(4202) s(4207) =< s(4196)*s(4200) s(4208) =< s(4195)*s(4202) s(4209) =< s(4195)*aux(342) s(4210) =< s(4203) s(4211) =< s(4204) s(4212) =< s(4207) s(4213) =< aux(344) s(4214) =< s(4209) s(4169) =< aux(336) s(4165) =< aux(336) s(4166) =< aux(336) s(4167) =< aux(336) s(4168) =< aux(336) s(4170) =< aux(336) s(4171) =< aux(336) s(4167) =< aux(337) s(4168) =< aux(337) s(4170) =< aux(337) s(4168) =< aux(338) s(4170) =< aux(338) s(4171) =< aux(338) s(4170) =< aux(339) s(4166) =< aux(340) s(4165) =< aux(341) s(4172) =< aux(336)+1 s(4173) =< aux(336)+2 s(4174) =< aux(336) s(4175) =< s(4169)*s(4172) s(4176) =< s(4169)*s(4173) s(4177) =< s(4168)*s(4174) s(4178) =< s(4170)*s(4174) s(4179) =< s(4168)*s(4172) s(4180) =< s(4167)*s(4174) s(4181) =< s(4167)*aux(336) s(4182) =< s(4175) s(4183) =< s(4176) s(4184) =< s(4179) s(4185) =< aux(338) s(4186) =< s(4181) with precondition: [Out=0,V1>=0,V>=0] * Chain [95]: 1*s(4329)+1*s(4330)+6*s(4331)+10*s(4332)+7*s(4333)+1*s(4334)+1*s(4335)+1*s(4341)+1*s(4342)+1*s(4344)+4*s(4346)+8*s(4347)+30*s(4348)+6*s(4349)+66*s(4350)+2*s(4357)+2*s(4358)+12*s(4359)+20*s(4360)+14*s(4361)+2*s(4362)+2*s(4363)+2*s(4369)+2*s(4370)+2*s(4372)+8*s(4374)+16*s(4375)+60*s(4376)+12*s(4377)+132*s(4378)+5 Such that:s(4323) =< V1 s(4324) =< V1/2 s(4325) =< 2/3*V1 s(4326) =< 2/5*V1 s(4327) =< 3/5*V1 s(4328) =< 3/7*V1 aux(348) =< V aux(349) =< V/2 aux(350) =< 2/3*V aux(351) =< 2/5*V aux(352) =< 3/5*V aux(353) =< 3/7*V s(4357) =< aux(348) s(4358) =< aux(348) s(4359) =< aux(348) s(4360) =< aux(348) s(4361) =< aux(348) s(4362) =< aux(348) s(4363) =< aux(348) s(4359) =< aux(349) s(4360) =< aux(349) s(4362) =< aux(349) s(4360) =< aux(350) s(4362) =< aux(350) s(4363) =< aux(350) s(4362) =< aux(351) s(4358) =< aux(352) s(4357) =< aux(353) s(4364) =< aux(348)+1 s(4365) =< aux(348)+2 s(4366) =< aux(348) s(4367) =< s(4361)*s(4364) s(4368) =< s(4361)*s(4365) s(4369) =< s(4360)*s(4366) s(4370) =< s(4362)*s(4366) s(4371) =< s(4360)*s(4364) s(4372) =< s(4359)*s(4366) s(4373) =< s(4359)*aux(348) s(4374) =< s(4367) s(4375) =< s(4368) s(4376) =< s(4371) s(4377) =< aux(350) s(4378) =< s(4373) s(4329) =< s(4323) s(4330) =< s(4323) s(4331) =< s(4323) s(4332) =< s(4323) s(4333) =< s(4323) s(4334) =< s(4323) s(4335) =< s(4323) s(4331) =< s(4324) s(4332) =< s(4324) s(4334) =< s(4324) s(4332) =< s(4325) s(4334) =< s(4325) s(4335) =< s(4325) s(4334) =< s(4326) s(4330) =< s(4327) s(4329) =< s(4328) s(4336) =< s(4323)+1 s(4337) =< s(4323)+2 s(4338) =< s(4323) s(4339) =< s(4333)*s(4336) s(4340) =< s(4333)*s(4337) s(4341) =< s(4332)*s(4338) s(4342) =< s(4334)*s(4338) s(4343) =< s(4332)*s(4336) s(4344) =< s(4331)*s(4338) s(4345) =< s(4331)*s(4323) s(4346) =< s(4339) s(4347) =< s(4340) s(4348) =< s(4343) s(4349) =< s(4325) s(4350) =< s(4345) with precondition: [Out=1,V1>=1,V>=1] * Chain [94]: 1*s(4413)+1*s(4414)+6*s(4415)+10*s(4416)+9*s(4417)+1*s(4418)+1*s(4419)+1*s(4425)+1*s(4426)+1*s(4428)+4*s(4430)+8*s(4431)+30*s(4432)+6*s(4433)+66*s(4434)+16*s(4438)+5 Such that:aux(354) =< V1 s(4408) =< V1/2 s(4409) =< 2/3*V1 s(4410) =< 2/5*V1 s(4411) =< 3/5*V1 s(4412) =< 3/7*V1 aux(355) =< 2 s(4417) =< aux(354) s(4438) =< aux(355) s(4413) =< aux(354) s(4414) =< aux(354) s(4415) =< aux(354) s(4416) =< aux(354) s(4418) =< aux(354) s(4419) =< aux(354) s(4415) =< s(4408) s(4416) =< s(4408) s(4418) =< s(4408) s(4416) =< s(4409) s(4418) =< s(4409) s(4419) =< s(4409) s(4418) =< s(4410) s(4414) =< s(4411) s(4413) =< s(4412) s(4420) =< aux(354)+1 s(4421) =< aux(354)+2 s(4422) =< aux(354) s(4423) =< s(4417)*s(4420) s(4424) =< s(4417)*s(4421) s(4425) =< s(4416)*s(4422) s(4426) =< s(4418)*s(4422) s(4427) =< s(4416)*s(4420) s(4428) =< s(4415)*s(4422) s(4429) =< s(4415)*aux(354) s(4430) =< s(4423) s(4431) =< s(4424) s(4432) =< s(4427) s(4433) =< s(4409) s(4434) =< s(4429) with precondition: [V=2,Out=0,V1>=0] * Chain [93]: 2*s(4449)+2*s(4450)+12*s(4451)+20*s(4452)+68*s(4453)+2*s(4454)+2*s(4455)+2*s(4461)+2*s(4462)+2*s(4464)+8*s(4466)+16*s(4467)+60*s(4468)+12*s(4469)+132*s(4470)+12*s(4475)+5 Such that:aux(358) =< 2 aux(359) =< V1 aux(360) =< V1/2 aux(361) =< 2/3*V1 aux(362) =< 2/5*V1 aux(363) =< 3/5*V1 aux(364) =< 3/7*V1 s(4453) =< aux(359) s(4475) =< aux(358) s(4449) =< aux(359) s(4450) =< aux(359) s(4451) =< aux(359) s(4452) =< aux(359) s(4454) =< aux(359) s(4455) =< aux(359) s(4451) =< aux(360) s(4452) =< aux(360) s(4454) =< aux(360) s(4452) =< aux(361) s(4454) =< aux(361) s(4455) =< aux(361) s(4454) =< aux(362) s(4450) =< aux(363) s(4449) =< aux(364) s(4456) =< aux(359)+1 s(4457) =< aux(359)+2 s(4458) =< aux(359) s(4459) =< s(4453)*s(4456) s(4460) =< s(4453)*s(4457) s(4461) =< s(4452)*s(4458) s(4462) =< s(4454)*s(4458) s(4463) =< s(4452)*s(4456) s(4464) =< s(4451)*s(4458) s(4465) =< s(4451)*aux(359) s(4466) =< s(4459) s(4467) =< s(4460) s(4468) =< s(4463) s(4469) =< aux(361) s(4470) =< s(4465) with precondition: [V=2,V1>=2,Out>=0,V1>=2*Out] #### Cost of chains of start(V1,V,V12): * Chain [98]: 395*s(4695)+559*s(4699)+19*s(4707)+14*s(4713)+14*s(4719)+12*s(4721)+56*s(4728)+56*s(4729)+336*s(4730)+560*s(4731)+56*s(4733)+56*s(4734)+56*s(4740)+56*s(4741)+56*s(4743)+224*s(4745)+448*s(4746)+1680*s(4747)+336*s(4748)+3696*s(4749)+48*s(4762)+48*s(4763)+288*s(4764)+480*s(4765)+48*s(4767)+48*s(4768)+48*s(4774)+48*s(4775)+48*s(4777)+192*s(4779)+384*s(4780)+1440*s(4781)+288*s(4782)+3168*s(4783)+127*s(4819)+18*s(5113)+18*s(5114)+108*s(5115)+180*s(5116)+126*s(5117)+18*s(5118)+18*s(5119)+18*s(5125)+18*s(5126)+18*s(5128)+72*s(5130)+144*s(5131)+540*s(5132)+108*s(5133)+1188*s(5134)+28*s(5578)+28*s(5579)+8*s(5580)+5 Such that:s(5518) =< V1+1 s(4715) =< V1-V aux(379) =< 1 aux(380) =< 2 aux(381) =< V1 aux(382) =< V1-V+1 aux(383) =< V1/2 aux(384) =< 2/3*V1 aux(385) =< 2/5*V1 aux(386) =< 3/5*V1 aux(387) =< 3/7*V1 aux(388) =< V aux(389) =< V/2 aux(390) =< 2/3*V aux(391) =< 2/5*V aux(392) =< 3/5*V aux(393) =< 3/7*V aux(394) =< V12 aux(395) =< V12/2 aux(396) =< 2/3*V12 aux(397) =< 2/5*V12 aux(398) =< 3/5*V12 aux(399) =< 3/7*V12 s(4707) =< aux(379) s(4819) =< aux(380) s(4699) =< aux(381) s(4695) =< aux(388) s(4728) =< aux(381) s(4729) =< aux(381) s(4730) =< aux(381) s(4731) =< aux(381) s(4733) =< aux(381) s(4734) =< aux(381) s(4730) =< aux(383) s(4731) =< aux(383) s(4733) =< aux(383) s(4731) =< aux(384) s(4733) =< aux(384) s(4734) =< aux(384) s(4733) =< aux(385) s(4729) =< aux(386) s(4728) =< aux(387) s(4735) =< aux(381)+1 s(4736) =< aux(381)+2 s(4737) =< aux(381) s(4738) =< s(4699)*s(4735) s(4739) =< s(4699)*s(4736) s(4740) =< s(4731)*s(4737) s(4741) =< s(4733)*s(4737) s(4742) =< s(4731)*s(4735) s(4743) =< s(4730)*s(4737) s(4744) =< s(4730)*aux(381) s(4745) =< s(4738) s(4746) =< s(4739) s(4747) =< s(4742) s(4748) =< aux(384) s(4749) =< s(4744) s(4762) =< aux(388) s(4763) =< aux(388) s(4764) =< aux(388) s(4765) =< aux(388) s(4767) =< aux(388) s(4768) =< aux(388) s(4764) =< aux(389) s(4765) =< aux(389) s(4767) =< aux(389) s(4765) =< aux(390) s(4767) =< aux(390) s(4768) =< aux(390) s(4767) =< aux(391) s(4763) =< aux(392) s(4762) =< aux(393) s(4769) =< aux(388)+1 s(4770) =< aux(388)+2 s(4771) =< aux(388) s(4772) =< s(4695)*s(4769) s(4773) =< s(4695)*s(4770) s(4774) =< s(4765)*s(4771) s(4775) =< s(4767)*s(4771) s(4776) =< s(4765)*s(4769) s(4777) =< s(4764)*s(4771) s(4778) =< s(4764)*aux(388) s(4779) =< s(4772) s(4780) =< s(4773) s(4781) =< s(4776) s(4782) =< aux(390) s(4783) =< s(4778) s(5578) =< aux(380) s(5578) =< aux(379) s(5579) =< aux(381) s(5579) =< s(5518) s(5580) =< s(5518) s(4713) =< aux(381) s(4713) =< aux(382) s(4719) =< aux(381) s(4720) =< aux(381) s(4719) =< aux(382) s(4719) =< s(4715) s(4720) =< s(4715) s(4721) =< s(4720) s(5113) =< aux(394) s(5114) =< aux(394) s(5115) =< aux(394) s(5116) =< aux(394) s(5117) =< aux(394) s(5118) =< aux(394) s(5119) =< aux(394) s(5115) =< aux(395) s(5116) =< aux(395) s(5118) =< aux(395) s(5116) =< aux(396) s(5118) =< aux(396) s(5119) =< aux(396) s(5118) =< aux(397) s(5114) =< aux(398) s(5113) =< aux(399) s(5120) =< aux(394)+1 s(5121) =< aux(394)+2 s(5122) =< aux(394) s(5123) =< s(5117)*s(5120) s(5124) =< s(5117)*s(5121) s(5125) =< s(5116)*s(5122) s(5126) =< s(5118)*s(5122) s(5127) =< s(5116)*s(5120) s(5128) =< s(5115)*s(5122) s(5129) =< s(5115)*aux(394) s(5130) =< s(5123) s(5131) =< s(5124) s(5132) =< s(5127) s(5133) =< aux(396) s(5134) =< s(5129) with precondition: [] Closed-form bounds of start(V1,V,V12): ------------------------------------- * Chain [98] with precondition: [] - Upper bound: nat(V1)*4547+334+nat(V1)*6216*nat(V1)+nat(V)*3755+nat(V)*5328*nat(V)+nat(V12)*1386+nat(V12)*1998*nat(V12)+nat(2/3*V1)*336+nat(2/3*V)*288+nat(2/3*V12)*108+nat(V1+1)*8 - Complexity: n^2 ### Maximum cost of start(V1,V,V12): nat(V1)*4547+334+nat(V1)*6216*nat(V1)+nat(V)*3755+nat(V)*5328*nat(V)+nat(V12)*1386+nat(V12)*1998*nat(V12)+nat(2/3*V1)*336+nat(2/3*V)*288+nat(2/3*V12)*108+nat(V1+1)*8 Asymptotic class: n^2 * Total analysis performed in 11961 ms. ---------------------------------------- (16) BOUNDS(1, n^2) ---------------------------------------- (17) RenamingProof (BOTH BOUNDS(ID, ID)) Renamed function symbols to avoid clashes with predefined symbol. ---------------------------------------- (18) 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: -(x, 0') -> x -(0', s(y)) -> 0' -(s(x), s(y)) -> -(x, y) lt(x, 0') -> false lt(0', s(y)) -> true lt(s(x), s(y)) -> lt(x, y) if(true, x, y) -> x if(false, x, y) -> y div(x, 0') -> 0' div(0', y) -> 0' div(s(x), s(y)) -> if(lt(x, y), 0', s(div(-(x, y), s(y)))) The (relative) TRS S consists of the following rules: encArg(0') -> 0' encArg(s(x_1)) -> s(encArg(x_1)) encArg(false) -> false encArg(true) -> true encArg(cons_-(x_1, x_2)) -> -(encArg(x_1), encArg(x_2)) encArg(cons_lt(x_1, x_2)) -> lt(encArg(x_1), encArg(x_2)) encArg(cons_if(x_1, x_2, x_3)) -> if(encArg(x_1), encArg(x_2), encArg(x_3)) encArg(cons_div(x_1, x_2)) -> div(encArg(x_1), encArg(x_2)) encode_-(x_1, x_2) -> -(encArg(x_1), encArg(x_2)) encode_0 -> 0' encode_s(x_1) -> s(encArg(x_1)) encode_lt(x_1, x_2) -> lt(encArg(x_1), encArg(x_2)) encode_false -> false encode_true -> true encode_if(x_1, x_2, x_3) -> if(encArg(x_1), encArg(x_2), encArg(x_3)) encode_div(x_1, x_2) -> div(encArg(x_1), encArg(x_2)) Rewrite Strategy: INNERMOST ---------------------------------------- (19) TypeInferenceProof (BOTH BOUNDS(ID, ID)) Infered types. ---------------------------------------- (20) Obligation: Innermost TRS: Rules: -(x, 0') -> x -(0', s(y)) -> 0' -(s(x), s(y)) -> -(x, y) lt(x, 0') -> false lt(0', s(y)) -> true lt(s(x), s(y)) -> lt(x, y) if(true, x, y) -> x if(false, x, y) -> y div(x, 0') -> 0' div(0', y) -> 0' div(s(x), s(y)) -> if(lt(x, y), 0', s(div(-(x, y), s(y)))) encArg(0') -> 0' encArg(s(x_1)) -> s(encArg(x_1)) encArg(false) -> false encArg(true) -> true encArg(cons_-(x_1, x_2)) -> -(encArg(x_1), encArg(x_2)) encArg(cons_lt(x_1, x_2)) -> lt(encArg(x_1), encArg(x_2)) encArg(cons_if(x_1, x_2, x_3)) -> if(encArg(x_1), encArg(x_2), encArg(x_3)) encArg(cons_div(x_1, x_2)) -> div(encArg(x_1), encArg(x_2)) encode_-(x_1, x_2) -> -(encArg(x_1), encArg(x_2)) encode_0 -> 0' encode_s(x_1) -> s(encArg(x_1)) encode_lt(x_1, x_2) -> lt(encArg(x_1), encArg(x_2)) encode_false -> false encode_true -> true encode_if(x_1, x_2, x_3) -> if(encArg(x_1), encArg(x_2), encArg(x_3)) encode_div(x_1, x_2) -> div(encArg(x_1), encArg(x_2)) Types: - :: 0':s:false:true:cons_-:cons_lt:cons_if:cons_div -> 0':s:false:true:cons_-:cons_lt:cons_if:cons_div -> 0':s:false:true:cons_-:cons_lt:cons_if:cons_div 0' :: 0':s:false:true:cons_-:cons_lt:cons_if:cons_div s :: 0':s:false:true:cons_-:cons_lt:cons_if:cons_div -> 0':s:false:true:cons_-:cons_lt:cons_if:cons_div lt :: 0':s:false:true:cons_-:cons_lt:cons_if:cons_div -> 0':s:false:true:cons_-:cons_lt:cons_if:cons_div -> 0':s:false:true:cons_-:cons_lt:cons_if:cons_div false :: 0':s:false:true:cons_-:cons_lt:cons_if:cons_div true :: 0':s:false:true:cons_-:cons_lt:cons_if:cons_div if :: 0':s:false:true:cons_-:cons_lt:cons_if:cons_div -> 0':s:false:true:cons_-:cons_lt:cons_if:cons_div -> 0':s:false:true:cons_-:cons_lt:cons_if:cons_div -> 0':s:false:true:cons_-:cons_lt:cons_if:cons_div div :: 0':s:false:true:cons_-:cons_lt:cons_if:cons_div -> 0':s:false:true:cons_-:cons_lt:cons_if:cons_div -> 0':s:false:true:cons_-:cons_lt:cons_if:cons_div encArg :: 0':s:false:true:cons_-:cons_lt:cons_if:cons_div -> 0':s:false:true:cons_-:cons_lt:cons_if:cons_div cons_- :: 0':s:false:true:cons_-:cons_lt:cons_if:cons_div -> 0':s:false:true:cons_-:cons_lt:cons_if:cons_div -> 0':s:false:true:cons_-:cons_lt:cons_if:cons_div cons_lt :: 0':s:false:true:cons_-:cons_lt:cons_if:cons_div -> 0':s:false:true:cons_-:cons_lt:cons_if:cons_div -> 0':s:false:true:cons_-:cons_lt:cons_if:cons_div cons_if :: 0':s:false:true:cons_-:cons_lt:cons_if:cons_div -> 0':s:false:true:cons_-:cons_lt:cons_if:cons_div -> 0':s:false:true:cons_-:cons_lt:cons_if:cons_div -> 0':s:false:true:cons_-:cons_lt:cons_if:cons_div cons_div :: 0':s:false:true:cons_-:cons_lt:cons_if:cons_div -> 0':s:false:true:cons_-:cons_lt:cons_if:cons_div -> 0':s:false:true:cons_-:cons_lt:cons_if:cons_div encode_- :: 0':s:false:true:cons_-:cons_lt:cons_if:cons_div -> 0':s:false:true:cons_-:cons_lt:cons_if:cons_div -> 0':s:false:true:cons_-:cons_lt:cons_if:cons_div encode_0 :: 0':s:false:true:cons_-:cons_lt:cons_if:cons_div encode_s :: 0':s:false:true:cons_-:cons_lt:cons_if:cons_div -> 0':s:false:true:cons_-:cons_lt:cons_if:cons_div encode_lt :: 0':s:false:true:cons_-:cons_lt:cons_if:cons_div -> 0':s:false:true:cons_-:cons_lt:cons_if:cons_div -> 0':s:false:true:cons_-:cons_lt:cons_if:cons_div encode_false :: 0':s:false:true:cons_-:cons_lt:cons_if:cons_div encode_true :: 0':s:false:true:cons_-:cons_lt:cons_if:cons_div encode_if :: 0':s:false:true:cons_-:cons_lt:cons_if:cons_div -> 0':s:false:true:cons_-:cons_lt:cons_if:cons_div -> 0':s:false:true:cons_-:cons_lt:cons_if:cons_div -> 0':s:false:true:cons_-:cons_lt:cons_if:cons_div encode_div :: 0':s:false:true:cons_-:cons_lt:cons_if:cons_div -> 0':s:false:true:cons_-:cons_lt:cons_if:cons_div -> 0':s:false:true:cons_-:cons_lt:cons_if:cons_div hole_0':s:false:true:cons_-:cons_lt:cons_if:cons_div1_4 :: 0':s:false:true:cons_-:cons_lt:cons_if:cons_div gen_0':s:false:true:cons_-:cons_lt:cons_if:cons_div2_4 :: Nat -> 0':s:false:true:cons_-:cons_lt:cons_if:cons_div ---------------------------------------- (21) OrderProof (LOWER BOUND(ID)) Heuristically decided to analyse the following defined symbols: -, lt, div, encArg They will be analysed ascendingly in the following order: - < div - < encArg lt < div lt < encArg div < encArg ---------------------------------------- (22) Obligation: Innermost TRS: Rules: -(x, 0') -> x -(0', s(y)) -> 0' -(s(x), s(y)) -> -(x, y) lt(x, 0') -> false lt(0', s(y)) -> true lt(s(x), s(y)) -> lt(x, y) if(true, x, y) -> x if(false, x, y) -> y div(x, 0') -> 0' div(0', y) -> 0' div(s(x), s(y)) -> if(lt(x, y), 0', s(div(-(x, y), s(y)))) encArg(0') -> 0' encArg(s(x_1)) -> s(encArg(x_1)) encArg(false) -> false encArg(true) -> true encArg(cons_-(x_1, x_2)) -> -(encArg(x_1), encArg(x_2)) encArg(cons_lt(x_1, x_2)) -> lt(encArg(x_1), encArg(x_2)) encArg(cons_if(x_1, x_2, x_3)) -> if(encArg(x_1), encArg(x_2), encArg(x_3)) encArg(cons_div(x_1, x_2)) -> div(encArg(x_1), encArg(x_2)) encode_-(x_1, x_2) -> -(encArg(x_1), encArg(x_2)) encode_0 -> 0' encode_s(x_1) -> s(encArg(x_1)) encode_lt(x_1, x_2) -> lt(encArg(x_1), encArg(x_2)) encode_false -> false encode_true -> true encode_if(x_1, x_2, x_3) -> if(encArg(x_1), encArg(x_2), encArg(x_3)) encode_div(x_1, x_2) -> div(encArg(x_1), encArg(x_2)) Types: - :: 0':s:false:true:cons_-:cons_lt:cons_if:cons_div -> 0':s:false:true:cons_-:cons_lt:cons_if:cons_div -> 0':s:false:true:cons_-:cons_lt:cons_if:cons_div 0' :: 0':s:false:true:cons_-:cons_lt:cons_if:cons_div s :: 0':s:false:true:cons_-:cons_lt:cons_if:cons_div -> 0':s:false:true:cons_-:cons_lt:cons_if:cons_div lt :: 0':s:false:true:cons_-:cons_lt:cons_if:cons_div -> 0':s:false:true:cons_-:cons_lt:cons_if:cons_div -> 0':s:false:true:cons_-:cons_lt:cons_if:cons_div false :: 0':s:false:true:cons_-:cons_lt:cons_if:cons_div true :: 0':s:false:true:cons_-:cons_lt:cons_if:cons_div if :: 0':s:false:true:cons_-:cons_lt:cons_if:cons_div -> 0':s:false:true:cons_-:cons_lt:cons_if:cons_div -> 0':s:false:true:cons_-:cons_lt:cons_if:cons_div -> 0':s:false:true:cons_-:cons_lt:cons_if:cons_div div :: 0':s:false:true:cons_-:cons_lt:cons_if:cons_div -> 0':s:false:true:cons_-:cons_lt:cons_if:cons_div -> 0':s:false:true:cons_-:cons_lt:cons_if:cons_div encArg :: 0':s:false:true:cons_-:cons_lt:cons_if:cons_div -> 0':s:false:true:cons_-:cons_lt:cons_if:cons_div cons_- :: 0':s:false:true:cons_-:cons_lt:cons_if:cons_div -> 0':s:false:true:cons_-:cons_lt:cons_if:cons_div -> 0':s:false:true:cons_-:cons_lt:cons_if:cons_div cons_lt :: 0':s:false:true:cons_-:cons_lt:cons_if:cons_div -> 0':s:false:true:cons_-:cons_lt:cons_if:cons_div -> 0':s:false:true:cons_-:cons_lt:cons_if:cons_div cons_if :: 0':s:false:true:cons_-:cons_lt:cons_if:cons_div -> 0':s:false:true:cons_-:cons_lt:cons_if:cons_div -> 0':s:false:true:cons_-:cons_lt:cons_if:cons_div -> 0':s:false:true:cons_-:cons_lt:cons_if:cons_div cons_div :: 0':s:false:true:cons_-:cons_lt:cons_if:cons_div -> 0':s:false:true:cons_-:cons_lt:cons_if:cons_div -> 0':s:false:true:cons_-:cons_lt:cons_if:cons_div encode_- :: 0':s:false:true:cons_-:cons_lt:cons_if:cons_div -> 0':s:false:true:cons_-:cons_lt:cons_if:cons_div -> 0':s:false:true:cons_-:cons_lt:cons_if:cons_div encode_0 :: 0':s:false:true:cons_-:cons_lt:cons_if:cons_div encode_s :: 0':s:false:true:cons_-:cons_lt:cons_if:cons_div -> 0':s:false:true:cons_-:cons_lt:cons_if:cons_div encode_lt :: 0':s:false:true:cons_-:cons_lt:cons_if:cons_div -> 0':s:false:true:cons_-:cons_lt:cons_if:cons_div -> 0':s:false:true:cons_-:cons_lt:cons_if:cons_div encode_false :: 0':s:false:true:cons_-:cons_lt:cons_if:cons_div encode_true :: 0':s:false:true:cons_-:cons_lt:cons_if:cons_div encode_if :: 0':s:false:true:cons_-:cons_lt:cons_if:cons_div -> 0':s:false:true:cons_-:cons_lt:cons_if:cons_div -> 0':s:false:true:cons_-:cons_lt:cons_if:cons_div -> 0':s:false:true:cons_-:cons_lt:cons_if:cons_div encode_div :: 0':s:false:true:cons_-:cons_lt:cons_if:cons_div -> 0':s:false:true:cons_-:cons_lt:cons_if:cons_div -> 0':s:false:true:cons_-:cons_lt:cons_if:cons_div hole_0':s:false:true:cons_-:cons_lt:cons_if:cons_div1_4 :: 0':s:false:true:cons_-:cons_lt:cons_if:cons_div gen_0':s:false:true:cons_-:cons_lt:cons_if:cons_div2_4 :: Nat -> 0':s:false:true:cons_-:cons_lt:cons_if:cons_div Generator Equations: gen_0':s:false:true:cons_-:cons_lt:cons_if:cons_div2_4(0) <=> 0' gen_0':s:false:true:cons_-:cons_lt:cons_if:cons_div2_4(+(x, 1)) <=> s(gen_0':s:false:true:cons_-:cons_lt:cons_if:cons_div2_4(x)) The following defined symbols remain to be analysed: -, lt, div, encArg They will be analysed ascendingly in the following order: - < div - < encArg lt < div lt < encArg div < encArg ---------------------------------------- (23) RewriteLemmaProof (LOWER BOUND(ID)) Proved the following rewrite lemma: -(gen_0':s:false:true:cons_-:cons_lt:cons_if:cons_div2_4(n4_4), gen_0':s:false:true:cons_-:cons_lt:cons_if:cons_div2_4(n4_4)) -> gen_0':s:false:true:cons_-:cons_lt:cons_if:cons_div2_4(0), rt in Omega(1 + n4_4) Induction Base: -(gen_0':s:false:true:cons_-:cons_lt:cons_if:cons_div2_4(0), gen_0':s:false:true:cons_-:cons_lt:cons_if:cons_div2_4(0)) ->_R^Omega(1) gen_0':s:false:true:cons_-:cons_lt:cons_if:cons_div2_4(0) Induction Step: -(gen_0':s:false:true:cons_-:cons_lt:cons_if:cons_div2_4(+(n4_4, 1)), gen_0':s:false:true:cons_-:cons_lt:cons_if:cons_div2_4(+(n4_4, 1))) ->_R^Omega(1) -(gen_0':s:false:true:cons_-:cons_lt:cons_if:cons_div2_4(n4_4), gen_0':s:false:true:cons_-:cons_lt:cons_if:cons_div2_4(n4_4)) ->_IH gen_0':s:false:true:cons_-:cons_lt:cons_if:cons_div2_4(0) We have rt in Omega(n^1) and sz in O(n). Thus, we have irc_R in Omega(n). ---------------------------------------- (24) Complex Obligation (BEST) ---------------------------------------- (25) Obligation: Proved the lower bound n^1 for the following obligation: Innermost TRS: Rules: -(x, 0') -> x -(0', s(y)) -> 0' -(s(x), s(y)) -> -(x, y) lt(x, 0') -> false lt(0', s(y)) -> true lt(s(x), s(y)) -> lt(x, y) if(true, x, y) -> x if(false, x, y) -> y div(x, 0') -> 0' div(0', y) -> 0' div(s(x), s(y)) -> if(lt(x, y), 0', s(div(-(x, y), s(y)))) encArg(0') -> 0' encArg(s(x_1)) -> s(encArg(x_1)) encArg(false) -> false encArg(true) -> true encArg(cons_-(x_1, x_2)) -> -(encArg(x_1), encArg(x_2)) encArg(cons_lt(x_1, x_2)) -> lt(encArg(x_1), encArg(x_2)) encArg(cons_if(x_1, x_2, x_3)) -> if(encArg(x_1), encArg(x_2), encArg(x_3)) encArg(cons_div(x_1, x_2)) -> div(encArg(x_1), encArg(x_2)) encode_-(x_1, x_2) -> -(encArg(x_1), encArg(x_2)) encode_0 -> 0' encode_s(x_1) -> s(encArg(x_1)) encode_lt(x_1, x_2) -> lt(encArg(x_1), encArg(x_2)) encode_false -> false encode_true -> true encode_if(x_1, x_2, x_3) -> if(encArg(x_1), encArg(x_2), encArg(x_3)) encode_div(x_1, x_2) -> div(encArg(x_1), encArg(x_2)) Types: - :: 0':s:false:true:cons_-:cons_lt:cons_if:cons_div -> 0':s:false:true:cons_-:cons_lt:cons_if:cons_div -> 0':s:false:true:cons_-:cons_lt:cons_if:cons_div 0' :: 0':s:false:true:cons_-:cons_lt:cons_if:cons_div s :: 0':s:false:true:cons_-:cons_lt:cons_if:cons_div -> 0':s:false:true:cons_-:cons_lt:cons_if:cons_div lt :: 0':s:false:true:cons_-:cons_lt:cons_if:cons_div -> 0':s:false:true:cons_-:cons_lt:cons_if:cons_div -> 0':s:false:true:cons_-:cons_lt:cons_if:cons_div false :: 0':s:false:true:cons_-:cons_lt:cons_if:cons_div true :: 0':s:false:true:cons_-:cons_lt:cons_if:cons_div if :: 0':s:false:true:cons_-:cons_lt:cons_if:cons_div -> 0':s:false:true:cons_-:cons_lt:cons_if:cons_div -> 0':s:false:true:cons_-:cons_lt:cons_if:cons_div -> 0':s:false:true:cons_-:cons_lt:cons_if:cons_div div :: 0':s:false:true:cons_-:cons_lt:cons_if:cons_div -> 0':s:false:true:cons_-:cons_lt:cons_if:cons_div -> 0':s:false:true:cons_-:cons_lt:cons_if:cons_div encArg :: 0':s:false:true:cons_-:cons_lt:cons_if:cons_div -> 0':s:false:true:cons_-:cons_lt:cons_if:cons_div cons_- :: 0':s:false:true:cons_-:cons_lt:cons_if:cons_div -> 0':s:false:true:cons_-:cons_lt:cons_if:cons_div -> 0':s:false:true:cons_-:cons_lt:cons_if:cons_div cons_lt :: 0':s:false:true:cons_-:cons_lt:cons_if:cons_div -> 0':s:false:true:cons_-:cons_lt:cons_if:cons_div -> 0':s:false:true:cons_-:cons_lt:cons_if:cons_div cons_if :: 0':s:false:true:cons_-:cons_lt:cons_if:cons_div -> 0':s:false:true:cons_-:cons_lt:cons_if:cons_div -> 0':s:false:true:cons_-:cons_lt:cons_if:cons_div -> 0':s:false:true:cons_-:cons_lt:cons_if:cons_div cons_div :: 0':s:false:true:cons_-:cons_lt:cons_if:cons_div -> 0':s:false:true:cons_-:cons_lt:cons_if:cons_div -> 0':s:false:true:cons_-:cons_lt:cons_if:cons_div encode_- :: 0':s:false:true:cons_-:cons_lt:cons_if:cons_div -> 0':s:false:true:cons_-:cons_lt:cons_if:cons_div -> 0':s:false:true:cons_-:cons_lt:cons_if:cons_div encode_0 :: 0':s:false:true:cons_-:cons_lt:cons_if:cons_div encode_s :: 0':s:false:true:cons_-:cons_lt:cons_if:cons_div -> 0':s:false:true:cons_-:cons_lt:cons_if:cons_div encode_lt :: 0':s:false:true:cons_-:cons_lt:cons_if:cons_div -> 0':s:false:true:cons_-:cons_lt:cons_if:cons_div -> 0':s:false:true:cons_-:cons_lt:cons_if:cons_div encode_false :: 0':s:false:true:cons_-:cons_lt:cons_if:cons_div encode_true :: 0':s:false:true:cons_-:cons_lt:cons_if:cons_div encode_if :: 0':s:false:true:cons_-:cons_lt:cons_if:cons_div -> 0':s:false:true:cons_-:cons_lt:cons_if:cons_div -> 0':s:false:true:cons_-:cons_lt:cons_if:cons_div -> 0':s:false:true:cons_-:cons_lt:cons_if:cons_div encode_div :: 0':s:false:true:cons_-:cons_lt:cons_if:cons_div -> 0':s:false:true:cons_-:cons_lt:cons_if:cons_div -> 0':s:false:true:cons_-:cons_lt:cons_if:cons_div hole_0':s:false:true:cons_-:cons_lt:cons_if:cons_div1_4 :: 0':s:false:true:cons_-:cons_lt:cons_if:cons_div gen_0':s:false:true:cons_-:cons_lt:cons_if:cons_div2_4 :: Nat -> 0':s:false:true:cons_-:cons_lt:cons_if:cons_div Generator Equations: gen_0':s:false:true:cons_-:cons_lt:cons_if:cons_div2_4(0) <=> 0' gen_0':s:false:true:cons_-:cons_lt:cons_if:cons_div2_4(+(x, 1)) <=> s(gen_0':s:false:true:cons_-:cons_lt:cons_if:cons_div2_4(x)) The following defined symbols remain to be analysed: -, lt, div, encArg They will be analysed ascendingly in the following order: - < div - < encArg lt < div lt < encArg div < encArg ---------------------------------------- (26) LowerBoundPropagationProof (FINISHED) Propagated lower bound. ---------------------------------------- (27) BOUNDS(n^1, INF) ---------------------------------------- (28) Obligation: Innermost TRS: Rules: -(x, 0') -> x -(0', s(y)) -> 0' -(s(x), s(y)) -> -(x, y) lt(x, 0') -> false lt(0', s(y)) -> true lt(s(x), s(y)) -> lt(x, y) if(true, x, y) -> x if(false, x, y) -> y div(x, 0') -> 0' div(0', y) -> 0' div(s(x), s(y)) -> if(lt(x, y), 0', s(div(-(x, y), s(y)))) encArg(0') -> 0' encArg(s(x_1)) -> s(encArg(x_1)) encArg(false) -> false encArg(true) -> true encArg(cons_-(x_1, x_2)) -> -(encArg(x_1), encArg(x_2)) encArg(cons_lt(x_1, x_2)) -> lt(encArg(x_1), encArg(x_2)) encArg(cons_if(x_1, x_2, x_3)) -> if(encArg(x_1), encArg(x_2), encArg(x_3)) encArg(cons_div(x_1, x_2)) -> div(encArg(x_1), encArg(x_2)) encode_-(x_1, x_2) -> -(encArg(x_1), encArg(x_2)) encode_0 -> 0' encode_s(x_1) -> s(encArg(x_1)) encode_lt(x_1, x_2) -> lt(encArg(x_1), encArg(x_2)) encode_false -> false encode_true -> true encode_if(x_1, x_2, x_3) -> if(encArg(x_1), encArg(x_2), encArg(x_3)) encode_div(x_1, x_2) -> div(encArg(x_1), encArg(x_2)) Types: - :: 0':s:false:true:cons_-:cons_lt:cons_if:cons_div -> 0':s:false:true:cons_-:cons_lt:cons_if:cons_div -> 0':s:false:true:cons_-:cons_lt:cons_if:cons_div 0' :: 0':s:false:true:cons_-:cons_lt:cons_if:cons_div s :: 0':s:false:true:cons_-:cons_lt:cons_if:cons_div -> 0':s:false:true:cons_-:cons_lt:cons_if:cons_div lt :: 0':s:false:true:cons_-:cons_lt:cons_if:cons_div -> 0':s:false:true:cons_-:cons_lt:cons_if:cons_div -> 0':s:false:true:cons_-:cons_lt:cons_if:cons_div false :: 0':s:false:true:cons_-:cons_lt:cons_if:cons_div true :: 0':s:false:true:cons_-:cons_lt:cons_if:cons_div if :: 0':s:false:true:cons_-:cons_lt:cons_if:cons_div -> 0':s:false:true:cons_-:cons_lt:cons_if:cons_div -> 0':s:false:true:cons_-:cons_lt:cons_if:cons_div -> 0':s:false:true:cons_-:cons_lt:cons_if:cons_div div :: 0':s:false:true:cons_-:cons_lt:cons_if:cons_div -> 0':s:false:true:cons_-:cons_lt:cons_if:cons_div -> 0':s:false:true:cons_-:cons_lt:cons_if:cons_div encArg :: 0':s:false:true:cons_-:cons_lt:cons_if:cons_div -> 0':s:false:true:cons_-:cons_lt:cons_if:cons_div cons_- :: 0':s:false:true:cons_-:cons_lt:cons_if:cons_div -> 0':s:false:true:cons_-:cons_lt:cons_if:cons_div -> 0':s:false:true:cons_-:cons_lt:cons_if:cons_div cons_lt :: 0':s:false:true:cons_-:cons_lt:cons_if:cons_div -> 0':s:false:true:cons_-:cons_lt:cons_if:cons_div -> 0':s:false:true:cons_-:cons_lt:cons_if:cons_div cons_if :: 0':s:false:true:cons_-:cons_lt:cons_if:cons_div -> 0':s:false:true:cons_-:cons_lt:cons_if:cons_div -> 0':s:false:true:cons_-:cons_lt:cons_if:cons_div -> 0':s:false:true:cons_-:cons_lt:cons_if:cons_div cons_div :: 0':s:false:true:cons_-:cons_lt:cons_if:cons_div -> 0':s:false:true:cons_-:cons_lt:cons_if:cons_div -> 0':s:false:true:cons_-:cons_lt:cons_if:cons_div encode_- :: 0':s:false:true:cons_-:cons_lt:cons_if:cons_div -> 0':s:false:true:cons_-:cons_lt:cons_if:cons_div -> 0':s:false:true:cons_-:cons_lt:cons_if:cons_div encode_0 :: 0':s:false:true:cons_-:cons_lt:cons_if:cons_div encode_s :: 0':s:false:true:cons_-:cons_lt:cons_if:cons_div -> 0':s:false:true:cons_-:cons_lt:cons_if:cons_div encode_lt :: 0':s:false:true:cons_-:cons_lt:cons_if:cons_div -> 0':s:false:true:cons_-:cons_lt:cons_if:cons_div -> 0':s:false:true:cons_-:cons_lt:cons_if:cons_div encode_false :: 0':s:false:true:cons_-:cons_lt:cons_if:cons_div encode_true :: 0':s:false:true:cons_-:cons_lt:cons_if:cons_div encode_if :: 0':s:false:true:cons_-:cons_lt:cons_if:cons_div -> 0':s:false:true:cons_-:cons_lt:cons_if:cons_div -> 0':s:false:true:cons_-:cons_lt:cons_if:cons_div -> 0':s:false:true:cons_-:cons_lt:cons_if:cons_div encode_div :: 0':s:false:true:cons_-:cons_lt:cons_if:cons_div -> 0':s:false:true:cons_-:cons_lt:cons_if:cons_div -> 0':s:false:true:cons_-:cons_lt:cons_if:cons_div hole_0':s:false:true:cons_-:cons_lt:cons_if:cons_div1_4 :: 0':s:false:true:cons_-:cons_lt:cons_if:cons_div gen_0':s:false:true:cons_-:cons_lt:cons_if:cons_div2_4 :: Nat -> 0':s:false:true:cons_-:cons_lt:cons_if:cons_div Lemmas: -(gen_0':s:false:true:cons_-:cons_lt:cons_if:cons_div2_4(n4_4), gen_0':s:false:true:cons_-:cons_lt:cons_if:cons_div2_4(n4_4)) -> gen_0':s:false:true:cons_-:cons_lt:cons_if:cons_div2_4(0), rt in Omega(1 + n4_4) Generator Equations: gen_0':s:false:true:cons_-:cons_lt:cons_if:cons_div2_4(0) <=> 0' gen_0':s:false:true:cons_-:cons_lt:cons_if:cons_div2_4(+(x, 1)) <=> s(gen_0':s:false:true:cons_-:cons_lt:cons_if:cons_div2_4(x)) The following defined symbols remain to be analysed: lt, div, encArg They will be analysed ascendingly in the following order: lt < div lt < encArg div < encArg ---------------------------------------- (29) RewriteLemmaProof (LOWER BOUND(ID)) Proved the following rewrite lemma: lt(gen_0':s:false:true:cons_-:cons_lt:cons_if:cons_div2_4(n711_4), gen_0':s:false:true:cons_-:cons_lt:cons_if:cons_div2_4(n711_4)) -> false, rt in Omega(1 + n711_4) Induction Base: lt(gen_0':s:false:true:cons_-:cons_lt:cons_if:cons_div2_4(0), gen_0':s:false:true:cons_-:cons_lt:cons_if:cons_div2_4(0)) ->_R^Omega(1) false Induction Step: lt(gen_0':s:false:true:cons_-:cons_lt:cons_if:cons_div2_4(+(n711_4, 1)), gen_0':s:false:true:cons_-:cons_lt:cons_if:cons_div2_4(+(n711_4, 1))) ->_R^Omega(1) lt(gen_0':s:false:true:cons_-:cons_lt:cons_if:cons_div2_4(n711_4), gen_0':s:false:true:cons_-:cons_lt:cons_if:cons_div2_4(n711_4)) ->_IH false We have rt in Omega(n^1) and sz in O(n). Thus, we have irc_R in Omega(n). ---------------------------------------- (30) Obligation: Innermost TRS: Rules: -(x, 0') -> x -(0', s(y)) -> 0' -(s(x), s(y)) -> -(x, y) lt(x, 0') -> false lt(0', s(y)) -> true lt(s(x), s(y)) -> lt(x, y) if(true, x, y) -> x if(false, x, y) -> y div(x, 0') -> 0' div(0', y) -> 0' div(s(x), s(y)) -> if(lt(x, y), 0', s(div(-(x, y), s(y)))) encArg(0') -> 0' encArg(s(x_1)) -> s(encArg(x_1)) encArg(false) -> false encArg(true) -> true encArg(cons_-(x_1, x_2)) -> -(encArg(x_1), encArg(x_2)) encArg(cons_lt(x_1, x_2)) -> lt(encArg(x_1), encArg(x_2)) encArg(cons_if(x_1, x_2, x_3)) -> if(encArg(x_1), encArg(x_2), encArg(x_3)) encArg(cons_div(x_1, x_2)) -> div(encArg(x_1), encArg(x_2)) encode_-(x_1, x_2) -> -(encArg(x_1), encArg(x_2)) encode_0 -> 0' encode_s(x_1) -> s(encArg(x_1)) encode_lt(x_1, x_2) -> lt(encArg(x_1), encArg(x_2)) encode_false -> false encode_true -> true encode_if(x_1, x_2, x_3) -> if(encArg(x_1), encArg(x_2), encArg(x_3)) encode_div(x_1, x_2) -> div(encArg(x_1), encArg(x_2)) Types: - :: 0':s:false:true:cons_-:cons_lt:cons_if:cons_div -> 0':s:false:true:cons_-:cons_lt:cons_if:cons_div -> 0':s:false:true:cons_-:cons_lt:cons_if:cons_div 0' :: 0':s:false:true:cons_-:cons_lt:cons_if:cons_div s :: 0':s:false:true:cons_-:cons_lt:cons_if:cons_div -> 0':s:false:true:cons_-:cons_lt:cons_if:cons_div lt :: 0':s:false:true:cons_-:cons_lt:cons_if:cons_div -> 0':s:false:true:cons_-:cons_lt:cons_if:cons_div -> 0':s:false:true:cons_-:cons_lt:cons_if:cons_div false :: 0':s:false:true:cons_-:cons_lt:cons_if:cons_div true :: 0':s:false:true:cons_-:cons_lt:cons_if:cons_div if :: 0':s:false:true:cons_-:cons_lt:cons_if:cons_div -> 0':s:false:true:cons_-:cons_lt:cons_if:cons_div -> 0':s:false:true:cons_-:cons_lt:cons_if:cons_div -> 0':s:false:true:cons_-:cons_lt:cons_if:cons_div div :: 0':s:false:true:cons_-:cons_lt:cons_if:cons_div -> 0':s:false:true:cons_-:cons_lt:cons_if:cons_div -> 0':s:false:true:cons_-:cons_lt:cons_if:cons_div encArg :: 0':s:false:true:cons_-:cons_lt:cons_if:cons_div -> 0':s:false:true:cons_-:cons_lt:cons_if:cons_div cons_- :: 0':s:false:true:cons_-:cons_lt:cons_if:cons_div -> 0':s:false:true:cons_-:cons_lt:cons_if:cons_div -> 0':s:false:true:cons_-:cons_lt:cons_if:cons_div cons_lt :: 0':s:false:true:cons_-:cons_lt:cons_if:cons_div -> 0':s:false:true:cons_-:cons_lt:cons_if:cons_div -> 0':s:false:true:cons_-:cons_lt:cons_if:cons_div cons_if :: 0':s:false:true:cons_-:cons_lt:cons_if:cons_div -> 0':s:false:true:cons_-:cons_lt:cons_if:cons_div -> 0':s:false:true:cons_-:cons_lt:cons_if:cons_div -> 0':s:false:true:cons_-:cons_lt:cons_if:cons_div cons_div :: 0':s:false:true:cons_-:cons_lt:cons_if:cons_div -> 0':s:false:true:cons_-:cons_lt:cons_if:cons_div -> 0':s:false:true:cons_-:cons_lt:cons_if:cons_div encode_- :: 0':s:false:true:cons_-:cons_lt:cons_if:cons_div -> 0':s:false:true:cons_-:cons_lt:cons_if:cons_div -> 0':s:false:true:cons_-:cons_lt:cons_if:cons_div encode_0 :: 0':s:false:true:cons_-:cons_lt:cons_if:cons_div encode_s :: 0':s:false:true:cons_-:cons_lt:cons_if:cons_div -> 0':s:false:true:cons_-:cons_lt:cons_if:cons_div encode_lt :: 0':s:false:true:cons_-:cons_lt:cons_if:cons_div -> 0':s:false:true:cons_-:cons_lt:cons_if:cons_div -> 0':s:false:true:cons_-:cons_lt:cons_if:cons_div encode_false :: 0':s:false:true:cons_-:cons_lt:cons_if:cons_div encode_true :: 0':s:false:true:cons_-:cons_lt:cons_if:cons_div encode_if :: 0':s:false:true:cons_-:cons_lt:cons_if:cons_div -> 0':s:false:true:cons_-:cons_lt:cons_if:cons_div -> 0':s:false:true:cons_-:cons_lt:cons_if:cons_div -> 0':s:false:true:cons_-:cons_lt:cons_if:cons_div encode_div :: 0':s:false:true:cons_-:cons_lt:cons_if:cons_div -> 0':s:false:true:cons_-:cons_lt:cons_if:cons_div -> 0':s:false:true:cons_-:cons_lt:cons_if:cons_div hole_0':s:false:true:cons_-:cons_lt:cons_if:cons_div1_4 :: 0':s:false:true:cons_-:cons_lt:cons_if:cons_div gen_0':s:false:true:cons_-:cons_lt:cons_if:cons_div2_4 :: Nat -> 0':s:false:true:cons_-:cons_lt:cons_if:cons_div Lemmas: -(gen_0':s:false:true:cons_-:cons_lt:cons_if:cons_div2_4(n4_4), gen_0':s:false:true:cons_-:cons_lt:cons_if:cons_div2_4(n4_4)) -> gen_0':s:false:true:cons_-:cons_lt:cons_if:cons_div2_4(0), rt in Omega(1 + n4_4) lt(gen_0':s:false:true:cons_-:cons_lt:cons_if:cons_div2_4(n711_4), gen_0':s:false:true:cons_-:cons_lt:cons_if:cons_div2_4(n711_4)) -> false, rt in Omega(1 + n711_4) Generator Equations: gen_0':s:false:true:cons_-:cons_lt:cons_if:cons_div2_4(0) <=> 0' gen_0':s:false:true:cons_-:cons_lt:cons_if:cons_div2_4(+(x, 1)) <=> s(gen_0':s:false:true:cons_-:cons_lt:cons_if:cons_div2_4(x)) The following defined symbols remain to be analysed: div, encArg They will be analysed ascendingly in the following order: div < encArg ---------------------------------------- (31) RewriteLemmaProof (LOWER BOUND(ID)) Proved the following rewrite lemma: encArg(gen_0':s:false:true:cons_-:cons_lt:cons_if:cons_div2_4(n1379_4)) -> gen_0':s:false:true:cons_-:cons_lt:cons_if:cons_div2_4(n1379_4), rt in Omega(0) Induction Base: encArg(gen_0':s:false:true:cons_-:cons_lt:cons_if:cons_div2_4(0)) ->_R^Omega(0) 0' Induction Step: encArg(gen_0':s:false:true:cons_-:cons_lt:cons_if:cons_div2_4(+(n1379_4, 1))) ->_R^Omega(0) s(encArg(gen_0':s:false:true:cons_-:cons_lt:cons_if:cons_div2_4(n1379_4))) ->_IH s(gen_0':s:false:true:cons_-:cons_lt:cons_if:cons_div2_4(c1380_4)) We have rt in Omega(1) and sz in O(n). Thus, we have irc_R in Omega(n^0). ---------------------------------------- (32) BOUNDS(1, INF)