/export/starexec/sandbox2/solver/bin/starexec_run_rcdcRelativeAlsoLower /export/starexec/sandbox2/benchmark/theBenchmark.xml /export/starexec/sandbox2/output/output_files -------------------------------------------------------------------------------- WORST_CASE(Omega(n^1), O(n^2)) proof of /export/starexec/sandbox2/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), 186 ms] (4) CpxRelTRS (5) RelTrsToWeightedTrsProof [BOTH BOUNDS(ID, ID), 0 ms] (6) CpxWeightedTrs (7) TypeInferenceProof [BOTH BOUNDS(ID, ID), 0 ms] (8) CpxTypedWeightedTrs (9) CompletionProof [UPPER BOUND(ID), 0 ms] (10) CpxTypedWeightedCompleteTrs (11) CpxTypedWeightedTrsToRntsProof [UPPER BOUND(ID), 0 ms] (12) CpxRNTS (13) CompleteCoflocoProof [FINISHED, 5818 ms] (14) BOUNDS(1, n^2) (15) RelTrsToDecreasingLoopProblemProof [LOWER BOUND(ID), 0 ms] (16) TRS for Loop Detection (17) DecreasingLoopProof [LOWER BOUND(ID), 0 ms] (18) BEST (19) proven lower bound (20) LowerBoundPropagationProof [FINISHED, 0 ms] (21) BOUNDS(n^1, INF) (22) TRS for Loop Detection ---------------------------------------- (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: min(X, 0) -> X min(s(X), s(Y)) -> min(X, Y) quot(0, s(Y)) -> 0 quot(s(X), s(Y)) -> s(quot(min(X, Y), s(Y))) log(s(0)) -> 0 log(s(s(X))) -> s(log(s(quot(X, s(s(0)))))) 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(cons_min(x_1, x_2)) -> min(encArg(x_1), encArg(x_2)) encArg(cons_quot(x_1, x_2)) -> quot(encArg(x_1), encArg(x_2)) encArg(cons_log(x_1)) -> log(encArg(x_1)) encode_min(x_1, x_2) -> min(encArg(x_1), encArg(x_2)) encode_0 -> 0 encode_s(x_1) -> s(encArg(x_1)) encode_quot(x_1, x_2) -> quot(encArg(x_1), encArg(x_2)) encode_log(x_1) -> log(encArg(x_1)) ---------------------------------------- (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: min(X, 0) -> X min(s(X), s(Y)) -> min(X, Y) quot(0, s(Y)) -> 0 quot(s(X), s(Y)) -> s(quot(min(X, Y), s(Y))) log(s(0)) -> 0 log(s(s(X))) -> s(log(s(quot(X, s(s(0)))))) The (relative) TRS S consists of the following rules: encArg(0) -> 0 encArg(s(x_1)) -> s(encArg(x_1)) encArg(cons_min(x_1, x_2)) -> min(encArg(x_1), encArg(x_2)) encArg(cons_quot(x_1, x_2)) -> quot(encArg(x_1), encArg(x_2)) encArg(cons_log(x_1)) -> log(encArg(x_1)) encode_min(x_1, x_2) -> min(encArg(x_1), encArg(x_2)) encode_0 -> 0 encode_s(x_1) -> s(encArg(x_1)) encode_quot(x_1, x_2) -> quot(encArg(x_1), encArg(x_2)) encode_log(x_1) -> log(encArg(x_1)) 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: min(X, 0) -> X min(s(X), s(Y)) -> min(X, Y) quot(0, s(Y)) -> 0 quot(s(X), s(Y)) -> s(quot(min(X, Y), s(Y))) log(s(0)) -> 0 log(s(s(X))) -> s(log(s(quot(X, s(s(0)))))) The (relative) TRS S consists of the following rules: encArg(0) -> 0 encArg(s(x_1)) -> s(encArg(x_1)) encArg(cons_min(x_1, x_2)) -> min(encArg(x_1), encArg(x_2)) encArg(cons_quot(x_1, x_2)) -> quot(encArg(x_1), encArg(x_2)) encArg(cons_log(x_1)) -> log(encArg(x_1)) encode_min(x_1, x_2) -> min(encArg(x_1), encArg(x_2)) encode_0 -> 0 encode_s(x_1) -> s(encArg(x_1)) encode_quot(x_1, x_2) -> quot(encArg(x_1), encArg(x_2)) encode_log(x_1) -> log(encArg(x_1)) 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: min(X, 0) -> X [1] min(s(X), s(Y)) -> min(X, Y) [1] quot(0, s(Y)) -> 0 [1] quot(s(X), s(Y)) -> s(quot(min(X, Y), s(Y))) [1] log(s(0)) -> 0 [1] log(s(s(X))) -> s(log(s(quot(X, s(s(0)))))) [1] encArg(0) -> 0 [0] encArg(s(x_1)) -> s(encArg(x_1)) [0] encArg(cons_min(x_1, x_2)) -> min(encArg(x_1), encArg(x_2)) [0] encArg(cons_quot(x_1, x_2)) -> quot(encArg(x_1), encArg(x_2)) [0] encArg(cons_log(x_1)) -> log(encArg(x_1)) [0] encode_min(x_1, x_2) -> min(encArg(x_1), encArg(x_2)) [0] encode_0 -> 0 [0] encode_s(x_1) -> s(encArg(x_1)) [0] encode_quot(x_1, x_2) -> quot(encArg(x_1), encArg(x_2)) [0] encode_log(x_1) -> log(encArg(x_1)) [0] Rewrite Strategy: INNERMOST ---------------------------------------- (7) TypeInferenceProof (BOTH BOUNDS(ID, ID)) Infered types. ---------------------------------------- (8) Obligation: Runtime Complexity Weighted TRS with Types. The TRS R consists of the following rules: min(X, 0) -> X [1] min(s(X), s(Y)) -> min(X, Y) [1] quot(0, s(Y)) -> 0 [1] quot(s(X), s(Y)) -> s(quot(min(X, Y), s(Y))) [1] log(s(0)) -> 0 [1] log(s(s(X))) -> s(log(s(quot(X, s(s(0)))))) [1] encArg(0) -> 0 [0] encArg(s(x_1)) -> s(encArg(x_1)) [0] encArg(cons_min(x_1, x_2)) -> min(encArg(x_1), encArg(x_2)) [0] encArg(cons_quot(x_1, x_2)) -> quot(encArg(x_1), encArg(x_2)) [0] encArg(cons_log(x_1)) -> log(encArg(x_1)) [0] encode_min(x_1, x_2) -> min(encArg(x_1), encArg(x_2)) [0] encode_0 -> 0 [0] encode_s(x_1) -> s(encArg(x_1)) [0] encode_quot(x_1, x_2) -> quot(encArg(x_1), encArg(x_2)) [0] encode_log(x_1) -> log(encArg(x_1)) [0] The TRS has the following type information: min :: 0:s:cons_min:cons_quot:cons_log -> 0:s:cons_min:cons_quot:cons_log -> 0:s:cons_min:cons_quot:cons_log 0 :: 0:s:cons_min:cons_quot:cons_log s :: 0:s:cons_min:cons_quot:cons_log -> 0:s:cons_min:cons_quot:cons_log quot :: 0:s:cons_min:cons_quot:cons_log -> 0:s:cons_min:cons_quot:cons_log -> 0:s:cons_min:cons_quot:cons_log log :: 0:s:cons_min:cons_quot:cons_log -> 0:s:cons_min:cons_quot:cons_log encArg :: 0:s:cons_min:cons_quot:cons_log -> 0:s:cons_min:cons_quot:cons_log cons_min :: 0:s:cons_min:cons_quot:cons_log -> 0:s:cons_min:cons_quot:cons_log -> 0:s:cons_min:cons_quot:cons_log cons_quot :: 0:s:cons_min:cons_quot:cons_log -> 0:s:cons_min:cons_quot:cons_log -> 0:s:cons_min:cons_quot:cons_log cons_log :: 0:s:cons_min:cons_quot:cons_log -> 0:s:cons_min:cons_quot:cons_log encode_min :: 0:s:cons_min:cons_quot:cons_log -> 0:s:cons_min:cons_quot:cons_log -> 0:s:cons_min:cons_quot:cons_log encode_0 :: 0:s:cons_min:cons_quot:cons_log encode_s :: 0:s:cons_min:cons_quot:cons_log -> 0:s:cons_min:cons_quot:cons_log encode_quot :: 0:s:cons_min:cons_quot:cons_log -> 0:s:cons_min:cons_quot:cons_log -> 0:s:cons_min:cons_quot:cons_log encode_log :: 0:s:cons_min:cons_quot:cons_log -> 0:s:cons_min:cons_quot:cons_log Rewrite Strategy: INNERMOST ---------------------------------------- (9) CompletionProof (UPPER BOUND(ID)) The TRS is a completely defined constructor system, as every type has a constant constructor and the following rules were added: encArg(v0) -> null_encArg [0] encode_min(v0, v1) -> null_encode_min [0] encode_0 -> null_encode_0 [0] encode_s(v0) -> null_encode_s [0] encode_quot(v0, v1) -> null_encode_quot [0] encode_log(v0) -> null_encode_log [0] min(v0, v1) -> null_min [0] quot(v0, v1) -> null_quot [0] log(v0) -> null_log [0] And the following fresh constants: null_encArg, null_encode_min, null_encode_0, null_encode_s, null_encode_quot, null_encode_log, null_min, null_quot, null_log ---------------------------------------- (10) Obligation: Runtime Complexity Weighted TRS where all functions are completely defined. The underlying TRS is: Runtime Complexity Weighted TRS with Types. The TRS R consists of the following rules: min(X, 0) -> X [1] min(s(X), s(Y)) -> min(X, Y) [1] quot(0, s(Y)) -> 0 [1] quot(s(X), s(Y)) -> s(quot(min(X, Y), s(Y))) [1] log(s(0)) -> 0 [1] log(s(s(X))) -> s(log(s(quot(X, s(s(0)))))) [1] encArg(0) -> 0 [0] encArg(s(x_1)) -> s(encArg(x_1)) [0] encArg(cons_min(x_1, x_2)) -> min(encArg(x_1), encArg(x_2)) [0] encArg(cons_quot(x_1, x_2)) -> quot(encArg(x_1), encArg(x_2)) [0] encArg(cons_log(x_1)) -> log(encArg(x_1)) [0] encode_min(x_1, x_2) -> min(encArg(x_1), encArg(x_2)) [0] encode_0 -> 0 [0] encode_s(x_1) -> s(encArg(x_1)) [0] encode_quot(x_1, x_2) -> quot(encArg(x_1), encArg(x_2)) [0] encode_log(x_1) -> log(encArg(x_1)) [0] encArg(v0) -> null_encArg [0] encode_min(v0, v1) -> null_encode_min [0] encode_0 -> null_encode_0 [0] encode_s(v0) -> null_encode_s [0] encode_quot(v0, v1) -> null_encode_quot [0] encode_log(v0) -> null_encode_log [0] min(v0, v1) -> null_min [0] quot(v0, v1) -> null_quot [0] log(v0) -> null_log [0] The TRS has the following type information: min :: 0:s:cons_min:cons_quot:cons_log:null_encArg:null_encode_min:null_encode_0:null_encode_s:null_encode_quot:null_encode_log:null_min:null_quot:null_log -> 0:s:cons_min:cons_quot:cons_log:null_encArg:null_encode_min:null_encode_0:null_encode_s:null_encode_quot:null_encode_log:null_min:null_quot:null_log -> 0:s:cons_min:cons_quot:cons_log:null_encArg:null_encode_min:null_encode_0:null_encode_s:null_encode_quot:null_encode_log:null_min:null_quot:null_log 0 :: 0:s:cons_min:cons_quot:cons_log:null_encArg:null_encode_min:null_encode_0:null_encode_s:null_encode_quot:null_encode_log:null_min:null_quot:null_log s :: 0:s:cons_min:cons_quot:cons_log:null_encArg:null_encode_min:null_encode_0:null_encode_s:null_encode_quot:null_encode_log:null_min:null_quot:null_log -> 0:s:cons_min:cons_quot:cons_log:null_encArg:null_encode_min:null_encode_0:null_encode_s:null_encode_quot:null_encode_log:null_min:null_quot:null_log quot :: 0:s:cons_min:cons_quot:cons_log:null_encArg:null_encode_min:null_encode_0:null_encode_s:null_encode_quot:null_encode_log:null_min:null_quot:null_log -> 0:s:cons_min:cons_quot:cons_log:null_encArg:null_encode_min:null_encode_0:null_encode_s:null_encode_quot:null_encode_log:null_min:null_quot:null_log -> 0:s:cons_min:cons_quot:cons_log:null_encArg:null_encode_min:null_encode_0:null_encode_s:null_encode_quot:null_encode_log:null_min:null_quot:null_log log :: 0:s:cons_min:cons_quot:cons_log:null_encArg:null_encode_min:null_encode_0:null_encode_s:null_encode_quot:null_encode_log:null_min:null_quot:null_log -> 0:s:cons_min:cons_quot:cons_log:null_encArg:null_encode_min:null_encode_0:null_encode_s:null_encode_quot:null_encode_log:null_min:null_quot:null_log encArg :: 0:s:cons_min:cons_quot:cons_log:null_encArg:null_encode_min:null_encode_0:null_encode_s:null_encode_quot:null_encode_log:null_min:null_quot:null_log -> 0:s:cons_min:cons_quot:cons_log:null_encArg:null_encode_min:null_encode_0:null_encode_s:null_encode_quot:null_encode_log:null_min:null_quot:null_log cons_min :: 0:s:cons_min:cons_quot:cons_log:null_encArg:null_encode_min:null_encode_0:null_encode_s:null_encode_quot:null_encode_log:null_min:null_quot:null_log -> 0:s:cons_min:cons_quot:cons_log:null_encArg:null_encode_min:null_encode_0:null_encode_s:null_encode_quot:null_encode_log:null_min:null_quot:null_log -> 0:s:cons_min:cons_quot:cons_log:null_encArg:null_encode_min:null_encode_0:null_encode_s:null_encode_quot:null_encode_log:null_min:null_quot:null_log cons_quot :: 0:s:cons_min:cons_quot:cons_log:null_encArg:null_encode_min:null_encode_0:null_encode_s:null_encode_quot:null_encode_log:null_min:null_quot:null_log -> 0:s:cons_min:cons_quot:cons_log:null_encArg:null_encode_min:null_encode_0:null_encode_s:null_encode_quot:null_encode_log:null_min:null_quot:null_log -> 0:s:cons_min:cons_quot:cons_log:null_encArg:null_encode_min:null_encode_0:null_encode_s:null_encode_quot:null_encode_log:null_min:null_quot:null_log cons_log :: 0:s:cons_min:cons_quot:cons_log:null_encArg:null_encode_min:null_encode_0:null_encode_s:null_encode_quot:null_encode_log:null_min:null_quot:null_log -> 0:s:cons_min:cons_quot:cons_log:null_encArg:null_encode_min:null_encode_0:null_encode_s:null_encode_quot:null_encode_log:null_min:null_quot:null_log encode_min :: 0:s:cons_min:cons_quot:cons_log:null_encArg:null_encode_min:null_encode_0:null_encode_s:null_encode_quot:null_encode_log:null_min:null_quot:null_log -> 0:s:cons_min:cons_quot:cons_log:null_encArg:null_encode_min:null_encode_0:null_encode_s:null_encode_quot:null_encode_log:null_min:null_quot:null_log -> 0:s:cons_min:cons_quot:cons_log:null_encArg:null_encode_min:null_encode_0:null_encode_s:null_encode_quot:null_encode_log:null_min:null_quot:null_log encode_0 :: 0:s:cons_min:cons_quot:cons_log:null_encArg:null_encode_min:null_encode_0:null_encode_s:null_encode_quot:null_encode_log:null_min:null_quot:null_log encode_s :: 0:s:cons_min:cons_quot:cons_log:null_encArg:null_encode_min:null_encode_0:null_encode_s:null_encode_quot:null_encode_log:null_min:null_quot:null_log -> 0:s:cons_min:cons_quot:cons_log:null_encArg:null_encode_min:null_encode_0:null_encode_s:null_encode_quot:null_encode_log:null_min:null_quot:null_log encode_quot :: 0:s:cons_min:cons_quot:cons_log:null_encArg:null_encode_min:null_encode_0:null_encode_s:null_encode_quot:null_encode_log:null_min:null_quot:null_log -> 0:s:cons_min:cons_quot:cons_log:null_encArg:null_encode_min:null_encode_0:null_encode_s:null_encode_quot:null_encode_log:null_min:null_quot:null_log -> 0:s:cons_min:cons_quot:cons_log:null_encArg:null_encode_min:null_encode_0:null_encode_s:null_encode_quot:null_encode_log:null_min:null_quot:null_log encode_log :: 0:s:cons_min:cons_quot:cons_log:null_encArg:null_encode_min:null_encode_0:null_encode_s:null_encode_quot:null_encode_log:null_min:null_quot:null_log -> 0:s:cons_min:cons_quot:cons_log:null_encArg:null_encode_min:null_encode_0:null_encode_s:null_encode_quot:null_encode_log:null_min:null_quot:null_log null_encArg :: 0:s:cons_min:cons_quot:cons_log:null_encArg:null_encode_min:null_encode_0:null_encode_s:null_encode_quot:null_encode_log:null_min:null_quot:null_log null_encode_min :: 0:s:cons_min:cons_quot:cons_log:null_encArg:null_encode_min:null_encode_0:null_encode_s:null_encode_quot:null_encode_log:null_min:null_quot:null_log null_encode_0 :: 0:s:cons_min:cons_quot:cons_log:null_encArg:null_encode_min:null_encode_0:null_encode_s:null_encode_quot:null_encode_log:null_min:null_quot:null_log null_encode_s :: 0:s:cons_min:cons_quot:cons_log:null_encArg:null_encode_min:null_encode_0:null_encode_s:null_encode_quot:null_encode_log:null_min:null_quot:null_log null_encode_quot :: 0:s:cons_min:cons_quot:cons_log:null_encArg:null_encode_min:null_encode_0:null_encode_s:null_encode_quot:null_encode_log:null_min:null_quot:null_log null_encode_log :: 0:s:cons_min:cons_quot:cons_log:null_encArg:null_encode_min:null_encode_0:null_encode_s:null_encode_quot:null_encode_log:null_min:null_quot:null_log null_min :: 0:s:cons_min:cons_quot:cons_log:null_encArg:null_encode_min:null_encode_0:null_encode_s:null_encode_quot:null_encode_log:null_min:null_quot:null_log null_quot :: 0:s:cons_min:cons_quot:cons_log:null_encArg:null_encode_min:null_encode_0:null_encode_s:null_encode_quot:null_encode_log:null_min:null_quot:null_log null_log :: 0:s:cons_min:cons_quot:cons_log:null_encArg:null_encode_min:null_encode_0:null_encode_s:null_encode_quot:null_encode_log:null_min:null_quot:null_log Rewrite Strategy: INNERMOST ---------------------------------------- (11) CpxTypedWeightedTrsToRntsProof (UPPER BOUND(ID)) Transformed the TRS into an over-approximating RNTS by (improved) Size Abstraction. The constant constructors are abstracted as follows: 0 => 0 null_encArg => 0 null_encode_min => 0 null_encode_0 => 0 null_encode_s => 0 null_encode_quot => 0 null_encode_log => 0 null_min => 0 null_quot => 0 null_log => 0 ---------------------------------------- (12) Obligation: Complexity RNTS consisting of the following rules: encArg(z) -{ 0 }-> quot(encArg(x_1), encArg(x_2)) :|: x_1 >= 0, z = 1 + x_1 + x_2, x_2 >= 0 encArg(z) -{ 0 }-> min(encArg(x_1), encArg(x_2)) :|: x_1 >= 0, z = 1 + x_1 + x_2, x_2 >= 0 encArg(z) -{ 0 }-> log(encArg(x_1)) :|: z = 1 + x_1, x_1 >= 0 encArg(z) -{ 0 }-> 0 :|: z = 0 encArg(z) -{ 0 }-> 0 :|: v0 >= 0, z = v0 encArg(z) -{ 0 }-> 1 + encArg(x_1) :|: z = 1 + x_1, x_1 >= 0 encode_0 -{ 0 }-> 0 :|: encode_log(z) -{ 0 }-> log(encArg(x_1)) :|: x_1 >= 0, z = x_1 encode_log(z) -{ 0 }-> 0 :|: v0 >= 0, z = v0 encode_min(z, z') -{ 0 }-> min(encArg(x_1), encArg(x_2)) :|: x_1 >= 0, x_2 >= 0, z = x_1, z' = x_2 encode_min(z, z') -{ 0 }-> 0 :|: v0 >= 0, v1 >= 0, z = v0, z' = v1 encode_quot(z, z') -{ 0 }-> quot(encArg(x_1), encArg(x_2)) :|: x_1 >= 0, x_2 >= 0, z = x_1, z' = x_2 encode_quot(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 log(z) -{ 1 }-> 0 :|: z = 1 + 0 log(z) -{ 0 }-> 0 :|: v0 >= 0, z = v0 log(z) -{ 1 }-> 1 + log(1 + quot(X, 1 + (1 + 0))) :|: z = 1 + (1 + X), X >= 0 min(z, z') -{ 1 }-> X :|: X >= 0, z = X, z' = 0 min(z, z') -{ 1 }-> min(X, Y) :|: z = 1 + X, Y >= 0, z' = 1 + Y, X >= 0 min(z, z') -{ 0 }-> 0 :|: v0 >= 0, v1 >= 0, z = v0, z' = v1 quot(z, z') -{ 1 }-> 0 :|: Y >= 0, z' = 1 + Y, z = 0 quot(z, z') -{ 0 }-> 0 :|: v0 >= 0, v1 >= 0, z = v0, z' = v1 quot(z, z') -{ 1 }-> 1 + quot(min(X, Y), 1 + Y) :|: z = 1 + X, Y >= 0, z' = 1 + Y, X >= 0 Only complete derivations are relevant for the runtime complexity. ---------------------------------------- (13) CompleteCoflocoProof (FINISHED) Transformed the RNTS (where only complete derivations are relevant) into cost relations for CoFloCo: eq(start(V1, V),0,[min(V1, V, Out)],[V1 >= 0,V >= 0]). eq(start(V1, V),0,[quot(V1, V, Out)],[V1 >= 0,V >= 0]). eq(start(V1, V),0,[log(V1, Out)],[V1 >= 0]). eq(start(V1, V),0,[encArg(V1, Out)],[V1 >= 0]). eq(start(V1, V),0,[fun(V1, V, Out)],[V1 >= 0,V >= 0]). eq(start(V1, V),0,[fun1(Out)],[]). eq(start(V1, V),0,[fun2(V1, Out)],[V1 >= 0]). eq(start(V1, V),0,[fun3(V1, V, Out)],[V1 >= 0,V >= 0]). eq(start(V1, V),0,[fun4(V1, Out)],[V1 >= 0]). eq(min(V1, V, Out),1,[],[Out = X1,X1 >= 0,V1 = X1,V = 0]). eq(min(V1, V, Out),1,[min(X2, Y1, Ret)],[Out = Ret,V1 = 1 + X2,Y1 >= 0,V = 1 + Y1,X2 >= 0]). eq(quot(V1, V, Out),1,[],[Out = 0,Y2 >= 0,V = 1 + Y2,V1 = 0]). eq(quot(V1, V, Out),1,[min(X3, Y3, Ret10),quot(Ret10, 1 + Y3, Ret1)],[Out = 1 + Ret1,V1 = 1 + X3,Y3 >= 0,V = 1 + Y3,X3 >= 0]). eq(log(V1, Out),1,[],[Out = 0,V1 = 1]). eq(log(V1, Out),1,[quot(X4, 1 + (1 + 0), Ret101),log(1 + Ret101, Ret11)],[Out = 1 + Ret11,V1 = 2 + X4,X4 >= 0]). eq(encArg(V1, Out),0,[],[Out = 0,V1 = 0]). eq(encArg(V1, Out),0,[encArg(V2, Ret12)],[Out = 1 + Ret12,V1 = 1 + V2,V2 >= 0]). eq(encArg(V1, Out),0,[encArg(V3, Ret0),encArg(V4, Ret13),min(Ret0, Ret13, Ret2)],[Out = Ret2,V3 >= 0,V1 = 1 + V3 + V4,V4 >= 0]). eq(encArg(V1, Out),0,[encArg(V5, Ret01),encArg(V6, Ret14),quot(Ret01, Ret14, Ret3)],[Out = Ret3,V5 >= 0,V1 = 1 + V5 + V6,V6 >= 0]). eq(encArg(V1, Out),0,[encArg(V7, Ret02),log(Ret02, Ret4)],[Out = Ret4,V1 = 1 + V7,V7 >= 0]). eq(fun(V1, V, Out),0,[encArg(V9, Ret03),encArg(V8, Ret15),min(Ret03, Ret15, Ret5)],[Out = Ret5,V9 >= 0,V8 >= 0,V1 = V9,V = V8]). eq(fun1(Out),0,[],[Out = 0]). eq(fun2(V1, Out),0,[encArg(V10, Ret16)],[Out = 1 + Ret16,V10 >= 0,V1 = V10]). eq(fun3(V1, V, Out),0,[encArg(V12, Ret04),encArg(V11, Ret17),quot(Ret04, Ret17, Ret6)],[Out = Ret6,V12 >= 0,V11 >= 0,V1 = V12,V = V11]). eq(fun4(V1, Out),0,[encArg(V13, Ret05),log(Ret05, Ret7)],[Out = Ret7,V13 >= 0,V1 = V13]). eq(encArg(V1, Out),0,[],[Out = 0,V14 >= 0,V1 = V14]). eq(fun(V1, V, Out),0,[],[Out = 0,V16 >= 0,V15 >= 0,V1 = V16,V = V15]). eq(fun2(V1, Out),0,[],[Out = 0,V17 >= 0,V1 = V17]). eq(fun3(V1, V, Out),0,[],[Out = 0,V18 >= 0,V19 >= 0,V1 = V18,V = V19]). eq(fun4(V1, Out),0,[],[Out = 0,V20 >= 0,V1 = V20]). eq(min(V1, V, Out),0,[],[Out = 0,V21 >= 0,V22 >= 0,V1 = V21,V = V22]). eq(quot(V1, V, Out),0,[],[Out = 0,V23 >= 0,V24 >= 0,V1 = V23,V = V24]). eq(log(V1, Out),0,[],[Out = 0,V25 >= 0,V1 = V25]). input_output_vars(min(V1,V,Out),[V1,V],[Out]). input_output_vars(quot(V1,V,Out),[V1,V],[Out]). input_output_vars(log(V1,Out),[V1],[Out]). input_output_vars(encArg(V1,Out),[V1],[Out]). input_output_vars(fun(V1,V,Out),[V1,V],[Out]). input_output_vars(fun1(Out),[],[Out]). input_output_vars(fun2(V1,Out),[V1],[Out]). input_output_vars(fun3(V1,V,Out),[V1,V],[Out]). input_output_vars(fun4(V1,Out),[V1],[Out]). CoFloCo proof output: Preprocessing Cost Relations ===================================== #### Computed strongly connected components 0. recursive : [min/3] 1. recursive : [quot/3] 2. recursive : [log/2] 3. recursive [non_tail,multiple] : [encArg/2] 4. non_recursive : [fun/3] 5. non_recursive : [fun1/1] 6. non_recursive : [fun2/2] 7. non_recursive : [fun3/3] 8. non_recursive : [fun4/2] 9. non_recursive : [start/2] #### Obtained direct recursion through partial evaluation 0. SCC is partially evaluated into min/3 1. SCC is partially evaluated into quot/3 2. SCC is partially evaluated into log/2 3. SCC is partially evaluated into encArg/2 4. SCC is partially evaluated into fun/3 5. SCC is completely evaluated into other SCCs 6. SCC is partially evaluated into fun2/2 7. SCC is partially evaluated into fun3/3 8. SCC is partially evaluated into fun4/2 9. SCC is partially evaluated into start/2 Control-Flow Refinement of Cost Relations ===================================== ### Specialization of cost equations min/3 * CE 12 is refined into CE [32] * CE 10 is refined into CE [33] * CE 11 is refined into CE [34] ### Cost equations --> "Loop" of min/3 * CEs [34] --> Loop 16 * CEs [32] --> Loop 17 * CEs [33] --> Loop 18 ### Ranking functions of CR min(V1,V,Out) * RF of phase [16]: [V,V1] #### Partial ranking functions of CR min(V1,V,Out) * Partial RF of phase [16]: - RF of loop [16:1]: V V1 ### Specialization of cost equations quot/3 * CE 13 is refined into CE [35] * CE 15 is refined into CE [36] * CE 14 is refined into CE [37,38,39] ### Cost equations --> "Loop" of quot/3 * CEs [39] --> Loop 19 * CEs [38] --> Loop 20 * CEs [37] --> Loop 21 * CEs [35,36] --> Loop 22 ### Ranking functions of CR quot(V1,V,Out) * RF of phase [19]: [V1-1,V1-V+1] * RF of phase [21]: [V1] #### Partial ranking functions of CR quot(V1,V,Out) * Partial RF of phase [19]: - RF of loop [19:1]: V1-1 V1-V+1 * Partial RF of phase [21]: - RF of loop [21:1]: V1 ### Specialization of cost equations log/2 * CE 16 is refined into CE [40] * CE 18 is refined into CE [41] * CE 17 is refined into CE [42,43,44,45] ### Cost equations --> "Loop" of log/2 * CEs [45] --> Loop 23 * CEs [44] --> Loop 24 * CEs [43] --> Loop 25 * CEs [42] --> Loop 26 * CEs [40,41] --> Loop 27 ### Ranking functions of CR log(V1,Out) * RF of phase [23,24]: [V1-3,V1/2-3/2] #### Partial ranking functions of CR log(V1,Out) * Partial RF of phase [23,24]: - RF of loop [23:1]: V1/2-2 - RF of loop [24:1]: V1-3 ### Specialization of cost equations encArg/2 * CE 19 is refined into CE [46] * CE 20 is refined into CE [47] * CE 23 is refined into CE [48,49,50,51,52,53] * CE 21 is refined into CE [54,55,56] * CE 22 is refined into CE [57,58,59,60,61] ### Cost equations --> "Loop" of encArg/2 * CEs [61] --> Loop 28 * CEs [60] --> Loop 29 * CEs [56] --> Loop 30 * CEs [57] --> Loop 31 * CEs [54] --> Loop 32 * CEs [59] --> Loop 33 * CEs [55,58] --> Loop 34 * CEs [53] --> Loop 35 * CEs [52] --> Loop 36 * CEs [51] --> Loop 37 * CEs [47] --> Loop 38 * CEs [50] --> Loop 39 * CEs [49] --> Loop 40 * CEs [48] --> Loop 41 * CEs [46] --> Loop 42 ### Ranking functions of CR encArg(V1,Out) * RF of phase [28,29,30,31,32,33,34,35,36,37,38,39,40,41]: [V1] #### Partial ranking functions of CR encArg(V1,Out) * Partial RF of phase [28,29,30,31,32,33,34,35,36,37,38,39,40,41]: - RF of loop [28:1,28:2,29:1,29:2,30:1,30:2,31:1,31:2,32:1,32:2,33:1,33:2,34:1,34:2,35:1,36:1,37:1,38:1,39:1,40:1,41:1]: V1 ### Specialization of cost equations fun/3 * CE 24 is refined into CE [62,63,64,65,66,67,68,69,70] * CE 25 is refined into CE [71] ### Cost equations --> "Loop" of fun/3 * CEs [66,68,70] --> Loop 43 * CEs [62,63,64,65,67,69,71] --> Loop 44 ### Ranking functions of CR fun(V1,V,Out) #### Partial ranking functions of CR fun(V1,V,Out) ### Specialization of cost equations fun2/2 * CE 26 is refined into CE [72,73] * CE 27 is refined into CE [74] ### Cost equations --> "Loop" of fun2/2 * CEs [73] --> Loop 45 * CEs [72] --> Loop 46 * CEs [74] --> Loop 47 ### Ranking functions of CR fun2(V1,Out) #### Partial ranking functions of CR fun2(V1,Out) ### Specialization of cost equations fun3/3 * CE 28 is refined into CE [75,76,77,78,79,80,81,82] * CE 29 is refined into CE [83] ### Cost equations --> "Loop" of fun3/3 * CEs [78,80,81,82] --> Loop 48 * CEs [75,76,77,79,83] --> Loop 49 ### Ranking functions of CR fun3(V1,V,Out) #### Partial ranking functions of CR fun3(V1,V,Out) ### Specialization of cost equations fun4/2 * CE 30 is refined into CE [84,85,86,87,88,89,90] * CE 31 is refined into CE [91] ### Cost equations --> "Loop" of fun4/2 * CEs [90] --> Loop 50 * CEs [89] --> Loop 51 * CEs [88] --> Loop 52 * CEs [87] --> Loop 53 * CEs [86] --> Loop 54 * CEs [84,85,91] --> Loop 55 ### Ranking functions of CR fun4(V1,Out) #### Partial ranking functions of CR fun4(V1,Out) ### Specialization of cost equations start/2 * CE 1 is refined into CE [92,93,94] * CE 2 is refined into CE [95,96,97,98,99] * CE 3 is refined into CE [100,101,102,103,104,105] * CE 4 is refined into CE [106,107] * CE 5 is refined into CE [108,109] * CE 6 is refined into CE [110] * CE 7 is refined into CE [111,112,113] * CE 8 is refined into CE [114,115] * CE 9 is refined into CE [116,117,118,119,120,121] ### Cost equations --> "Loop" of start/2 * CEs [92,93,94,95,96,97,98,99,100,101,102,103,104,105,106,107,108,109,110,111,112,113,114,115,116,117,118,119,120,121] --> Loop 56 ### Ranking functions of CR start(V1,V) #### Partial ranking functions of CR start(V1,V) Computing Bounds ===================================== #### Cost of chains of min(V1,V,Out): * Chain [[16],18]: 1*it(16)+1 Such that:it(16) =< V with precondition: [V1=Out+V,V>=1,V1>=V] * Chain [[16],17]: 1*it(16)+0 Such that:it(16) =< V with precondition: [Out=0,V1>=1,V>=1] * Chain [18]: 1 with precondition: [V=0,V1=Out,V1>=0] * Chain [17]: 0 with precondition: [Out=0,V1>=0,V>=0] #### Cost of chains of quot(V1,V,Out): * Chain [[21],22]: 2*it(21)+1 Such that:it(21) =< Out with precondition: [V=1,Out>=1,V1>=Out] * Chain [[21],20,22]: 2*it(21)+1*s(2)+2 Such that:s(2) =< 1 it(21) =< Out with precondition: [V=1,Out>=2,V1>=Out] * Chain [[19],22]: 2*it(19)+1*s(5)+1 Such that:it(19) =< V1-V+1 aux(3) =< V1 it(19) =< aux(3) s(5) =< aux(3) with precondition: [V>=2,Out>=1,V1+2>=2*Out+V] * Chain [[19],20,22]: 2*it(19)+1*s(2)+1*s(5)+2 Such that:it(19) =< V1-V+1 s(2) =< V aux(4) =< V1 it(19) =< aux(4) s(5) =< aux(4) with precondition: [V>=2,Out>=2,V1+3>=2*Out+V] * Chain [22]: 1 with precondition: [Out=0,V1>=0,V>=0] * Chain [20,22]: 1*s(2)+2 Such that:s(2) =< V with precondition: [Out=1,V1>=1,V>=1] #### Cost of chains of log(V1,Out): * Chain [[23,24],27]: 3*it(23)+2*it(24)+3*s(21)+1*s(22)+3*s(24)+1 Such that:s(25) =< 2*V1 aux(14) =< 5/2*V1 aux(13) =< 5/2*V1+27/2 aux(15) =< V1 aux(16) =< V1/2 aux(8) =< aux(15) it(23) =< aux(15) it(24) =< aux(15) aux(8) =< aux(16) it(23) =< aux(16) it(24) =< aux(16) it(24) =< aux(13) s(23) =< aux(13) it(24) =< aux(14) s(23) =< aux(14) s(22) =< aux(8)*2 s(24) =< s(25) s(21) =< s(23) with precondition: [Out>=1,V1>=3*Out+1] * Chain [[23,24],26,27]: 3*it(23)+2*it(24)+3*s(21)+1*s(22)+3*s(24)+3 Such that:s(25) =< 2*V1 aux(14) =< 5/2*V1 aux(13) =< 5/2*V1+27/2 aux(17) =< V1 aux(18) =< V1/2 aux(8) =< aux(17) it(23) =< aux(17) it(24) =< aux(17) aux(8) =< aux(18) it(23) =< aux(18) it(24) =< aux(18) it(24) =< aux(13) s(23) =< aux(13) it(24) =< aux(14) s(23) =< aux(14) s(22) =< aux(8)*2 s(24) =< s(25) s(21) =< s(23) with precondition: [Out>=2,V1+2>=3*Out] * Chain [[23,24],25,27]: 3*it(23)+2*it(24)+3*s(21)+1*s(22)+3*s(24)+1*s(26)+4 Such that:s(26) =< 2 s(25) =< 2*V1 aux(14) =< 5/2*V1 aux(13) =< 5/2*V1+27/2 aux(19) =< V1 aux(20) =< V1/2 aux(8) =< aux(19) it(23) =< aux(19) it(24) =< aux(19) aux(8) =< aux(20) it(23) =< aux(20) it(24) =< aux(20) it(24) =< aux(13) s(23) =< aux(13) it(24) =< aux(14) s(23) =< aux(14) s(22) =< aux(8)*2 s(24) =< s(25) s(21) =< s(23) with precondition: [Out>=2,V1+3>=4*Out] * Chain [[23,24],25,26,27]: 3*it(23)+2*it(24)+3*s(21)+1*s(22)+3*s(24)+1*s(26)+6 Such that:s(26) =< 2 s(25) =< 2*V1 aux(14) =< 5/2*V1 aux(13) =< 5/2*V1+27/2 aux(21) =< V1 aux(22) =< V1/2 aux(8) =< aux(21) it(23) =< aux(21) it(24) =< aux(21) aux(8) =< aux(22) it(23) =< aux(22) it(24) =< aux(22) it(24) =< aux(13) s(23) =< aux(13) it(24) =< aux(14) s(23) =< aux(14) s(22) =< aux(8)*2 s(24) =< s(25) s(21) =< s(23) with precondition: [Out>=3,V1+7>=4*Out] * Chain [27]: 1 with precondition: [Out=0,V1>=0] * Chain [26,27]: 3 with precondition: [Out=1,V1>=2] * Chain [25,27]: 1*s(26)+4 Such that:s(26) =< 2 with precondition: [Out=1,V1>=3] * Chain [25,26,27]: 1*s(26)+6 Such that:s(26) =< 2 with precondition: [Out=2,V1>=3] #### Cost of chains of encArg(V1,Out): * Chain [42]: 0 with precondition: [Out=0,V1>=0] * Chain [multiple([28,29,30,31,32,33,34,35,36,37,38,39,40,41],[[42]])]: 2*it(28)+1*it(29)+3*it(30)+2*it(32)+2*it(33)+24*it(35)+4*s(154)+3*s(156)+1*s(158)+1*s(159)+4*s(160)+1*s(162)+1*s(163)+3*s(164)+12*s(165)+8*s(166)+4*s(167)+12*s(168)+12*s(169)+0 Such that:it([42]) =< V1+1 aux(60) =< V1 aux(61) =< V1/2 aux(62) =< V1/3 aux(63) =< 2/7*V1 it(32) =< aux(60) it(33) =< aux(60) it(35) =< aux(60) aux(37) =< aux(61) it(30) =< aux(61) it(33) =< aux(61) it(29) =< aux(62) it(28) =< aux(63) aux(47) =< aux(60)*(5/2)+16 aux(38) =< aux(60)+1 aux(33) =< aux(60) s(164) =< aux(60)*2 it(30) =< it([42])*(1/2)+aux(61) it(32) =< it([42])*(1/2)+aux(61) it(33) =< it([42])*(1/2)+aux(61) aux(37) =< it([42])*(1/2)+aux(61) it(29) =< it([42])*(2/3)+aux(62) it(30) =< it([42])*(2/3)+aux(62) it(32) =< it([42])*(2/3)+aux(62) it(33) =< it([42])*(2/3)+aux(62) it(28) =< it([42])*(5/7)+aux(63) it(29) =< it([42])*(5/7)+aux(63) it(30) =< it([42])*(5/7)+aux(63) it(32) =< it([42])*(5/7)+aux(63) it(33) =< it([42])*(5/7)+aux(63) s(174) =< it(35)*aux(47) aux(44) =< it(35)*aux(38) s(163) =< it(32)*aux(38) s(162) =< it(33)*aux(33) s(161) =< it(30)*aux(38) s(159) =< aux(37) s(158) =< it(30)*aux(33) s(157) =< it(29)*aux(33) s(155) =< it(28)*aux(60) s(173) =< aux(44)*(5/2) s(175) =< aux(44)*(1/2) s(171) =< aux(44)*2 s(172) =< aux(44) s(165) =< aux(44) s(166) =< aux(44) s(172) =< s(175) s(165) =< s(175) s(166) =< s(175) s(166) =< s(174) s(170) =< s(174) s(166) =< s(173) s(170) =< s(173) s(167) =< s(172)*2 s(168) =< s(171) s(169) =< s(170) s(160) =< s(161) s(156) =< s(157) s(154) =< s(155) with precondition: [V1>=1,Out>=0,V1>=Out] #### Cost of chains of fun(V1,V,Out): * Chain [44]: 6*s(209)+6*s(210)+74*s(211)+9*s(213)+3*s(214)+6*s(215)+9*s(219)+3*s(222)+3*s(223)+3*s(225)+3*s(226)+36*s(233)+24*s(234)+12*s(236)+36*s(237)+36*s(238)+12*s(239)+9*s(240)+12*s(241)+4*s(286)+4*s(287)+48*s(288)+6*s(290)+2*s(291)+4*s(292)+6*s(296)+2*s(299)+2*s(300)+2*s(302)+2*s(303)+24*s(310)+16*s(311)+8*s(313)+24*s(314)+24*s(315)+8*s(316)+6*s(317)+8*s(318)+1 Such that:aux(66) =< V1 aux(67) =< V1+1 aux(68) =< V1/2 aux(69) =< V1/3 aux(70) =< 2/7*V1 aux(71) =< V aux(72) =< V+1 aux(73) =< V/2 aux(74) =< V/3 aux(75) =< 2/7*V s(286) =< aux(66) s(287) =< aux(66) s(288) =< aux(66) s(289) =< aux(68) s(290) =< aux(68) s(287) =< aux(68) s(291) =< aux(69) s(292) =< aux(70) s(293) =< aux(66)*(5/2)+16 s(294) =< aux(66)+1 s(295) =< aux(66) s(296) =< aux(66)*2 s(290) =< aux(67)*(1/2)+aux(68) s(286) =< aux(67)*(1/2)+aux(68) s(287) =< aux(67)*(1/2)+aux(68) s(289) =< aux(67)*(1/2)+aux(68) s(291) =< aux(67)*(2/3)+aux(69) s(290) =< aux(67)*(2/3)+aux(69) s(286) =< aux(67)*(2/3)+aux(69) s(287) =< aux(67)*(2/3)+aux(69) s(292) =< aux(67)*(5/7)+aux(70) s(291) =< aux(67)*(5/7)+aux(70) s(290) =< aux(67)*(5/7)+aux(70) s(286) =< aux(67)*(5/7)+aux(70) s(287) =< aux(67)*(5/7)+aux(70) s(297) =< s(288)*s(293) s(298) =< s(288)*s(294) s(299) =< s(286)*s(294) s(300) =< s(287)*s(295) s(301) =< s(290)*s(294) s(302) =< s(289) s(303) =< s(290)*s(295) s(304) =< s(291)*s(295) s(305) =< s(292)*aux(66) s(306) =< s(298)*(5/2) s(307) =< s(298)*(1/2) s(308) =< s(298)*2 s(309) =< s(298) s(310) =< s(298) s(311) =< s(298) s(309) =< s(307) s(310) =< s(307) s(311) =< s(307) s(311) =< s(297) s(312) =< s(297) s(311) =< s(306) s(312) =< s(306) s(313) =< s(309)*2 s(314) =< s(308) s(315) =< s(312) s(316) =< s(301) s(317) =< s(304) s(318) =< s(305) s(211) =< aux(71) s(209) =< aux(71) s(210) =< aux(71) s(212) =< aux(73) s(213) =< aux(73) s(210) =< aux(73) s(214) =< aux(74) s(215) =< aux(75) s(216) =< aux(71)*(5/2)+16 s(217) =< aux(71)+1 s(218) =< aux(71) s(219) =< aux(71)*2 s(213) =< aux(72)*(1/2)+aux(73) s(209) =< aux(72)*(1/2)+aux(73) s(210) =< aux(72)*(1/2)+aux(73) s(212) =< aux(72)*(1/2)+aux(73) s(214) =< aux(72)*(2/3)+aux(74) s(213) =< aux(72)*(2/3)+aux(74) s(209) =< aux(72)*(2/3)+aux(74) s(210) =< aux(72)*(2/3)+aux(74) s(215) =< aux(72)*(5/7)+aux(75) s(214) =< aux(72)*(5/7)+aux(75) s(213) =< aux(72)*(5/7)+aux(75) s(209) =< aux(72)*(5/7)+aux(75) s(210) =< aux(72)*(5/7)+aux(75) s(220) =< s(211)*s(216) s(221) =< s(211)*s(217) s(222) =< s(209)*s(217) s(223) =< s(210)*s(218) s(224) =< s(213)*s(217) s(225) =< s(212) s(226) =< s(213)*s(218) s(227) =< s(214)*s(218) s(228) =< s(215)*aux(71) s(229) =< s(221)*(5/2) s(230) =< s(221)*(1/2) s(231) =< s(221)*2 s(232) =< s(221) s(233) =< s(221) s(234) =< s(221) s(232) =< s(230) s(233) =< s(230) s(234) =< s(230) s(234) =< s(220) s(235) =< s(220) s(234) =< s(229) s(235) =< s(229) s(236) =< s(232)*2 s(237) =< s(231) s(238) =< s(235) s(239) =< s(224) s(240) =< s(227) s(241) =< s(228) with precondition: [Out=0,V1>=0,V>=0] * Chain [43]: 6*s(402)+6*s(403)+72*s(404)+9*s(406)+3*s(407)+6*s(408)+9*s(412)+3*s(415)+3*s(416)+3*s(418)+3*s(419)+36*s(426)+24*s(427)+12*s(429)+36*s(430)+36*s(431)+12*s(432)+9*s(433)+12*s(434)+4*s(478)+4*s(479)+49*s(480)+6*s(482)+2*s(483)+4*s(484)+6*s(488)+2*s(491)+2*s(492)+2*s(494)+2*s(495)+24*s(502)+16*s(503)+8*s(505)+24*s(506)+24*s(507)+8*s(508)+6*s(509)+8*s(510)+1 Such that:aux(77) =< V1 aux(78) =< V1+1 aux(79) =< V1/2 aux(80) =< V1/3 aux(81) =< 2/7*V1 aux(82) =< V aux(83) =< V+1 aux(84) =< V/2 aux(85) =< V/3 aux(86) =< 2/7*V s(402) =< aux(77) s(403) =< aux(77) s(404) =< aux(77) s(405) =< aux(79) s(406) =< aux(79) s(403) =< aux(79) s(407) =< aux(80) s(408) =< aux(81) s(409) =< aux(77)*(5/2)+16 s(410) =< aux(77)+1 s(411) =< aux(77) s(412) =< aux(77)*2 s(406) =< aux(78)*(1/2)+aux(79) s(402) =< aux(78)*(1/2)+aux(79) s(403) =< aux(78)*(1/2)+aux(79) s(405) =< aux(78)*(1/2)+aux(79) s(407) =< aux(78)*(2/3)+aux(80) s(406) =< aux(78)*(2/3)+aux(80) s(402) =< aux(78)*(2/3)+aux(80) s(403) =< aux(78)*(2/3)+aux(80) s(408) =< aux(78)*(5/7)+aux(81) s(407) =< aux(78)*(5/7)+aux(81) s(406) =< aux(78)*(5/7)+aux(81) s(402) =< aux(78)*(5/7)+aux(81) s(403) =< aux(78)*(5/7)+aux(81) s(413) =< s(404)*s(409) s(414) =< s(404)*s(410) s(415) =< s(402)*s(410) s(416) =< s(403)*s(411) s(417) =< s(406)*s(410) s(418) =< s(405) s(419) =< s(406)*s(411) s(420) =< s(407)*s(411) s(421) =< s(408)*aux(77) s(422) =< s(414)*(5/2) s(423) =< s(414)*(1/2) s(424) =< s(414)*2 s(425) =< s(414) s(426) =< s(414) s(427) =< s(414) s(425) =< s(423) s(426) =< s(423) s(427) =< s(423) s(427) =< s(413) s(428) =< s(413) s(427) =< s(422) s(428) =< s(422) s(429) =< s(425)*2 s(430) =< s(424) s(431) =< s(428) s(432) =< s(417) s(433) =< s(420) s(434) =< s(421) s(478) =< aux(82) s(479) =< aux(82) s(480) =< aux(82) s(481) =< aux(84) s(482) =< aux(84) s(479) =< aux(84) s(483) =< aux(85) s(484) =< aux(86) s(485) =< aux(82)*(5/2)+16 s(486) =< aux(82)+1 s(487) =< aux(82) s(488) =< aux(82)*2 s(482) =< aux(83)*(1/2)+aux(84) s(478) =< aux(83)*(1/2)+aux(84) s(479) =< aux(83)*(1/2)+aux(84) s(481) =< aux(83)*(1/2)+aux(84) s(483) =< aux(83)*(2/3)+aux(85) s(482) =< aux(83)*(2/3)+aux(85) s(478) =< aux(83)*(2/3)+aux(85) s(479) =< aux(83)*(2/3)+aux(85) s(484) =< aux(83)*(5/7)+aux(86) s(483) =< aux(83)*(5/7)+aux(86) s(482) =< aux(83)*(5/7)+aux(86) s(478) =< aux(83)*(5/7)+aux(86) s(479) =< aux(83)*(5/7)+aux(86) s(489) =< s(480)*s(485) s(490) =< s(480)*s(486) s(491) =< s(478)*s(486) s(492) =< s(479)*s(487) s(493) =< s(482)*s(486) s(494) =< s(481) s(495) =< s(482)*s(487) s(496) =< s(483)*s(487) s(497) =< s(484)*aux(82) s(498) =< s(490)*(5/2) s(499) =< s(490)*(1/2) s(500) =< s(490)*2 s(501) =< s(490) s(502) =< s(490) s(503) =< s(490) s(501) =< s(499) s(502) =< s(499) s(503) =< s(499) s(503) =< s(489) s(504) =< s(489) s(503) =< s(498) s(504) =< s(498) s(505) =< s(501)*2 s(506) =< s(500) s(507) =< s(504) s(508) =< s(493) s(509) =< s(496) s(510) =< s(497) with precondition: [V1>=1,V>=0,Out>=0,V1>=Out] #### Cost of chains of fun2(V1,Out): * Chain [47]: 0 with precondition: [Out=0,V1>=0] * Chain [46]: 0 with precondition: [Out=1,V1>=0] * Chain [45]: 2*s(593)+2*s(594)+24*s(595)+3*s(597)+1*s(598)+2*s(599)+3*s(603)+1*s(606)+1*s(607)+1*s(609)+1*s(610)+12*s(617)+8*s(618)+4*s(620)+12*s(621)+12*s(622)+4*s(623)+3*s(624)+4*s(625)+0 Such that:s(589) =< V1 s(588) =< V1+1 s(590) =< V1/2 s(591) =< V1/3 s(592) =< 2/7*V1 s(593) =< s(589) s(594) =< s(589) s(595) =< s(589) s(596) =< s(590) s(597) =< s(590) s(594) =< s(590) s(598) =< s(591) s(599) =< s(592) s(600) =< s(589)*(5/2)+16 s(601) =< s(589)+1 s(602) =< s(589) s(603) =< s(589)*2 s(597) =< s(588)*(1/2)+s(590) s(593) =< s(588)*(1/2)+s(590) s(594) =< s(588)*(1/2)+s(590) s(596) =< s(588)*(1/2)+s(590) s(598) =< s(588)*(2/3)+s(591) s(597) =< s(588)*(2/3)+s(591) s(593) =< s(588)*(2/3)+s(591) s(594) =< s(588)*(2/3)+s(591) s(599) =< s(588)*(5/7)+s(592) s(598) =< s(588)*(5/7)+s(592) s(597) =< s(588)*(5/7)+s(592) s(593) =< s(588)*(5/7)+s(592) s(594) =< s(588)*(5/7)+s(592) s(604) =< s(595)*s(600) s(605) =< s(595)*s(601) s(606) =< s(593)*s(601) s(607) =< s(594)*s(602) s(608) =< s(597)*s(601) s(609) =< s(596) s(610) =< s(597)*s(602) s(611) =< s(598)*s(602) s(612) =< s(599)*s(589) s(613) =< s(605)*(5/2) s(614) =< s(605)*(1/2) s(615) =< s(605)*2 s(616) =< s(605) s(617) =< s(605) s(618) =< s(605) s(616) =< s(614) s(617) =< s(614) s(618) =< s(614) s(618) =< s(604) s(619) =< s(604) s(618) =< s(613) s(619) =< s(613) s(620) =< s(616)*2 s(621) =< s(615) s(622) =< s(619) s(623) =< s(608) s(624) =< s(611) s(625) =< s(612) with precondition: [V1>=1,Out>=1,V1+1>=Out] #### Cost of chains of fun3(V1,V,Out): * Chain [49]: 4*s(631)+4*s(632)+48*s(633)+6*s(635)+2*s(636)+4*s(637)+6*s(641)+2*s(644)+2*s(645)+2*s(647)+2*s(648)+24*s(655)+16*s(656)+8*s(658)+24*s(659)+24*s(660)+8*s(661)+6*s(662)+8*s(663)+4*s(669)+4*s(670)+48*s(671)+6*s(673)+2*s(674)+4*s(675)+6*s(679)+2*s(682)+2*s(683)+2*s(685)+2*s(686)+24*s(693)+16*s(694)+8*s(696)+24*s(697)+24*s(698)+8*s(699)+6*s(700)+8*s(701)+1 Such that:aux(87) =< V1 aux(88) =< V1+1 aux(89) =< V1/2 aux(90) =< V1/3 aux(91) =< 2/7*V1 aux(92) =< V aux(93) =< V+1 aux(94) =< V/2 aux(95) =< V/3 aux(96) =< 2/7*V s(669) =< aux(87) s(670) =< aux(87) s(671) =< aux(87) s(672) =< aux(89) s(673) =< aux(89) s(670) =< aux(89) s(674) =< aux(90) s(675) =< aux(91) s(676) =< aux(87)*(5/2)+16 s(677) =< aux(87)+1 s(678) =< aux(87) s(679) =< aux(87)*2 s(673) =< aux(88)*(1/2)+aux(89) s(669) =< aux(88)*(1/2)+aux(89) s(670) =< aux(88)*(1/2)+aux(89) s(672) =< aux(88)*(1/2)+aux(89) s(674) =< aux(88)*(2/3)+aux(90) s(673) =< aux(88)*(2/3)+aux(90) s(669) =< aux(88)*(2/3)+aux(90) s(670) =< aux(88)*(2/3)+aux(90) s(675) =< aux(88)*(5/7)+aux(91) s(674) =< aux(88)*(5/7)+aux(91) s(673) =< aux(88)*(5/7)+aux(91) s(669) =< aux(88)*(5/7)+aux(91) s(670) =< aux(88)*(5/7)+aux(91) s(680) =< s(671)*s(676) s(681) =< s(671)*s(677) s(682) =< s(669)*s(677) s(683) =< s(670)*s(678) s(684) =< s(673)*s(677) s(685) =< s(672) s(686) =< s(673)*s(678) s(687) =< s(674)*s(678) s(688) =< s(675)*aux(87) s(689) =< s(681)*(5/2) s(690) =< s(681)*(1/2) s(691) =< s(681)*2 s(692) =< s(681) s(693) =< s(681) s(694) =< s(681) s(692) =< s(690) s(693) =< s(690) s(694) =< s(690) s(694) =< s(680) s(695) =< s(680) s(694) =< s(689) s(695) =< s(689) s(696) =< s(692)*2 s(697) =< s(691) s(698) =< s(695) s(699) =< s(684) s(700) =< s(687) s(701) =< s(688) s(631) =< aux(92) s(632) =< aux(92) s(633) =< aux(92) s(634) =< aux(94) s(635) =< aux(94) s(632) =< aux(94) s(636) =< aux(95) s(637) =< aux(96) s(638) =< aux(92)*(5/2)+16 s(639) =< aux(92)+1 s(640) =< aux(92) s(641) =< aux(92)*2 s(635) =< aux(93)*(1/2)+aux(94) s(631) =< aux(93)*(1/2)+aux(94) s(632) =< aux(93)*(1/2)+aux(94) s(634) =< aux(93)*(1/2)+aux(94) s(636) =< aux(93)*(2/3)+aux(95) s(635) =< aux(93)*(2/3)+aux(95) s(631) =< aux(93)*(2/3)+aux(95) s(632) =< aux(93)*(2/3)+aux(95) s(637) =< aux(93)*(5/7)+aux(96) s(636) =< aux(93)*(5/7)+aux(96) s(635) =< aux(93)*(5/7)+aux(96) s(631) =< aux(93)*(5/7)+aux(96) s(632) =< aux(93)*(5/7)+aux(96) s(642) =< s(633)*s(638) s(643) =< s(633)*s(639) s(644) =< s(631)*s(639) s(645) =< s(632)*s(640) s(646) =< s(635)*s(639) s(647) =< s(634) s(648) =< s(635)*s(640) s(649) =< s(636)*s(640) s(650) =< s(637)*aux(92) s(651) =< s(643)*(5/2) s(652) =< s(643)*(1/2) s(653) =< s(643)*2 s(654) =< s(643) s(655) =< s(643) s(656) =< s(643) s(654) =< s(652) s(655) =< s(652) s(656) =< s(652) s(656) =< s(642) s(657) =< s(642) s(656) =< s(651) s(657) =< s(651) s(658) =< s(654)*2 s(659) =< s(653) s(660) =< s(657) s(661) =< s(646) s(662) =< s(649) s(663) =< s(650) with precondition: [Out=0,V1>=0,V>=0] * Chain [48]: 8*s(783)+8*s(784)+104*s(785)+12*s(787)+4*s(788)+8*s(789)+12*s(793)+4*s(796)+4*s(797)+4*s(799)+4*s(800)+48*s(807)+32*s(808)+16*s(810)+48*s(811)+48*s(812)+16*s(813)+12*s(814)+16*s(815)+8*s(821)+8*s(822)+97*s(823)+12*s(825)+4*s(826)+8*s(827)+12*s(831)+4*s(834)+4*s(835)+4*s(837)+4*s(838)+48*s(845)+32*s(846)+16*s(848)+48*s(849)+48*s(850)+16*s(851)+12*s(852)+16*s(853)+1*s(854)+2*s(1089)+1*s(1090)+2 Such that:s(854) =< 1 aux(102) =< V1 aux(103) =< V1+1 aux(104) =< V1/2 aux(105) =< V1/3 aux(106) =< 2/7*V1 aux(107) =< V aux(108) =< V+1 aux(109) =< V/2 aux(110) =< V/3 aux(111) =< 2/7*V s(785) =< aux(102) s(821) =< aux(107) s(822) =< aux(107) s(823) =< aux(107) s(824) =< aux(109) s(825) =< aux(109) s(822) =< aux(109) s(826) =< aux(110) s(827) =< aux(111) s(828) =< aux(107)*(5/2)+16 s(829) =< aux(107)+1 s(830) =< aux(107) s(831) =< aux(107)*2 s(825) =< aux(108)*(1/2)+aux(109) s(821) =< aux(108)*(1/2)+aux(109) s(822) =< aux(108)*(1/2)+aux(109) s(824) =< aux(108)*(1/2)+aux(109) s(826) =< aux(108)*(2/3)+aux(110) s(825) =< aux(108)*(2/3)+aux(110) s(821) =< aux(108)*(2/3)+aux(110) s(822) =< aux(108)*(2/3)+aux(110) s(827) =< aux(108)*(5/7)+aux(111) s(826) =< aux(108)*(5/7)+aux(111) s(825) =< aux(108)*(5/7)+aux(111) s(821) =< aux(108)*(5/7)+aux(111) s(822) =< aux(108)*(5/7)+aux(111) s(832) =< s(823)*s(828) s(833) =< s(823)*s(829) s(834) =< s(821)*s(829) s(835) =< s(822)*s(830) s(836) =< s(825)*s(829) s(837) =< s(824) s(838) =< s(825)*s(830) s(839) =< s(826)*s(830) s(840) =< s(827)*aux(107) s(841) =< s(833)*(5/2) s(842) =< s(833)*(1/2) s(843) =< s(833)*2 s(844) =< s(833) s(845) =< s(833) s(846) =< s(833) s(844) =< s(842) s(845) =< s(842) s(846) =< s(842) s(846) =< s(832) s(847) =< s(832) s(846) =< s(841) s(847) =< s(841) s(848) =< s(844)*2 s(849) =< s(843) s(850) =< s(847) s(851) =< s(836) s(852) =< s(839) s(853) =< s(840) s(783) =< aux(102) s(784) =< aux(102) s(786) =< aux(104) s(787) =< aux(104) s(784) =< aux(104) s(788) =< aux(105) s(789) =< aux(106) s(790) =< aux(102)*(5/2)+16 s(791) =< aux(102)+1 s(792) =< aux(102) s(793) =< aux(102)*2 s(787) =< aux(103)*(1/2)+aux(104) s(783) =< aux(103)*(1/2)+aux(104) s(784) =< aux(103)*(1/2)+aux(104) s(786) =< aux(103)*(1/2)+aux(104) s(788) =< aux(103)*(2/3)+aux(105) s(787) =< aux(103)*(2/3)+aux(105) s(783) =< aux(103)*(2/3)+aux(105) s(784) =< aux(103)*(2/3)+aux(105) s(789) =< aux(103)*(5/7)+aux(106) s(788) =< aux(103)*(5/7)+aux(106) s(787) =< aux(103)*(5/7)+aux(106) s(783) =< aux(103)*(5/7)+aux(106) s(784) =< aux(103)*(5/7)+aux(106) s(794) =< s(785)*s(790) s(795) =< s(785)*s(791) s(796) =< s(783)*s(791) s(797) =< s(784)*s(792) s(798) =< s(787)*s(791) s(799) =< s(786) s(800) =< s(787)*s(792) s(801) =< s(788)*s(792) s(802) =< s(789)*aux(102) s(803) =< s(795)*(5/2) s(804) =< s(795)*(1/2) s(805) =< s(795)*2 s(806) =< s(795) s(807) =< s(795) s(808) =< s(795) s(806) =< s(804) s(807) =< s(804) s(808) =< s(804) s(808) =< s(794) s(809) =< s(794) s(808) =< s(803) s(809) =< s(803) s(810) =< s(806)*2 s(811) =< s(805) s(812) =< s(809) s(813) =< s(798) s(814) =< s(801) s(815) =< s(802) s(1089) =< aux(103) s(1090) =< aux(103) s(1089) =< aux(102) with precondition: [V>=1,Out>=1,V1>=Out] #### Cost of chains of fun4(V1,Out): * Chain [55]: 2*s(1098)+2*s(1099)+24*s(1100)+3*s(1102)+1*s(1103)+2*s(1104)+3*s(1108)+1*s(1111)+1*s(1112)+1*s(1114)+1*s(1115)+12*s(1122)+8*s(1123)+4*s(1125)+12*s(1126)+12*s(1127)+4*s(1128)+3*s(1129)+4*s(1130)+1 Such that:s(1094) =< V1 s(1093) =< V1+1 s(1095) =< V1/2 s(1096) =< V1/3 s(1097) =< 2/7*V1 s(1098) =< s(1094) s(1099) =< s(1094) s(1100) =< s(1094) s(1101) =< s(1095) s(1102) =< s(1095) s(1099) =< s(1095) s(1103) =< s(1096) s(1104) =< s(1097) s(1105) =< s(1094)*(5/2)+16 s(1106) =< s(1094)+1 s(1107) =< s(1094) s(1108) =< s(1094)*2 s(1102) =< s(1093)*(1/2)+s(1095) s(1098) =< s(1093)*(1/2)+s(1095) s(1099) =< s(1093)*(1/2)+s(1095) s(1101) =< s(1093)*(1/2)+s(1095) s(1103) =< s(1093)*(2/3)+s(1096) s(1102) =< s(1093)*(2/3)+s(1096) s(1098) =< s(1093)*(2/3)+s(1096) s(1099) =< s(1093)*(2/3)+s(1096) s(1104) =< s(1093)*(5/7)+s(1097) s(1103) =< s(1093)*(5/7)+s(1097) s(1102) =< s(1093)*(5/7)+s(1097) s(1098) =< s(1093)*(5/7)+s(1097) s(1099) =< s(1093)*(5/7)+s(1097) s(1109) =< s(1100)*s(1105) s(1110) =< s(1100)*s(1106) s(1111) =< s(1098)*s(1106) s(1112) =< s(1099)*s(1107) s(1113) =< s(1102)*s(1106) s(1114) =< s(1101) s(1115) =< s(1102)*s(1107) s(1116) =< s(1103)*s(1107) s(1117) =< s(1104)*s(1094) s(1118) =< s(1110)*(5/2) s(1119) =< s(1110)*(1/2) s(1120) =< s(1110)*2 s(1121) =< s(1110) s(1122) =< s(1110) s(1123) =< s(1110) s(1121) =< s(1119) s(1122) =< s(1119) s(1123) =< s(1119) s(1123) =< s(1109) s(1124) =< s(1109) s(1123) =< s(1118) s(1124) =< s(1118) s(1125) =< s(1121)*2 s(1126) =< s(1120) s(1127) =< s(1124) s(1128) =< s(1113) s(1129) =< s(1116) s(1130) =< s(1117) with precondition: [Out=0,V1>=0] * Chain [54]: 2*s(1136)+2*s(1137)+24*s(1138)+3*s(1140)+1*s(1141)+2*s(1142)+3*s(1146)+1*s(1149)+1*s(1150)+1*s(1152)+1*s(1153)+12*s(1160)+8*s(1161)+4*s(1163)+12*s(1164)+12*s(1165)+4*s(1166)+3*s(1167)+4*s(1168)+6 Such that:s(1132) =< V1 s(1131) =< V1+1 s(1133) =< V1/2 s(1134) =< V1/3 s(1135) =< 2/7*V1 s(1136) =< s(1132) s(1137) =< s(1132) s(1138) =< s(1132) s(1139) =< s(1133) s(1140) =< s(1133) s(1137) =< s(1133) s(1141) =< s(1134) s(1142) =< s(1135) s(1143) =< s(1132)*(5/2)+16 s(1144) =< s(1132)+1 s(1145) =< s(1132) s(1146) =< s(1132)*2 s(1140) =< s(1131)*(1/2)+s(1133) s(1136) =< s(1131)*(1/2)+s(1133) s(1137) =< s(1131)*(1/2)+s(1133) s(1139) =< s(1131)*(1/2)+s(1133) s(1141) =< s(1131)*(2/3)+s(1134) s(1140) =< s(1131)*(2/3)+s(1134) s(1136) =< s(1131)*(2/3)+s(1134) s(1137) =< s(1131)*(2/3)+s(1134) s(1142) =< s(1131)*(5/7)+s(1135) s(1141) =< s(1131)*(5/7)+s(1135) s(1140) =< s(1131)*(5/7)+s(1135) s(1136) =< s(1131)*(5/7)+s(1135) s(1137) =< s(1131)*(5/7)+s(1135) s(1147) =< s(1138)*s(1143) s(1148) =< s(1138)*s(1144) s(1149) =< s(1136)*s(1144) s(1150) =< s(1137)*s(1145) s(1151) =< s(1140)*s(1144) s(1152) =< s(1139) s(1153) =< s(1140)*s(1145) s(1154) =< s(1141)*s(1145) s(1155) =< s(1142)*s(1132) s(1156) =< s(1148)*(5/2) s(1157) =< s(1148)*(1/2) s(1158) =< s(1148)*2 s(1159) =< s(1148) s(1160) =< s(1148) s(1161) =< s(1148) s(1159) =< s(1157) s(1160) =< s(1157) s(1161) =< s(1157) s(1161) =< s(1147) s(1162) =< s(1147) s(1161) =< s(1156) s(1162) =< s(1156) s(1163) =< s(1159)*2 s(1164) =< s(1158) s(1165) =< s(1162) s(1166) =< s(1151) s(1167) =< s(1154) s(1168) =< s(1155) with precondition: [Out=1,V1>=2] * Chain [53]: 2*s(1174)+2*s(1175)+24*s(1176)+3*s(1178)+1*s(1179)+2*s(1180)+3*s(1184)+1*s(1187)+1*s(1188)+1*s(1190)+1*s(1191)+12*s(1198)+8*s(1199)+4*s(1201)+12*s(1202)+12*s(1203)+4*s(1204)+3*s(1205)+4*s(1206)+1*s(1207)+6 Such that:s(1207) =< 2 s(1170) =< V1 s(1169) =< V1+1 s(1171) =< V1/2 s(1172) =< V1/3 s(1173) =< 2/7*V1 s(1174) =< s(1170) s(1175) =< s(1170) s(1176) =< s(1170) s(1177) =< s(1171) s(1178) =< s(1171) s(1175) =< s(1171) s(1179) =< s(1172) s(1180) =< s(1173) s(1181) =< s(1170)*(5/2)+16 s(1182) =< s(1170)+1 s(1183) =< s(1170) s(1184) =< s(1170)*2 s(1178) =< s(1169)*(1/2)+s(1171) s(1174) =< s(1169)*(1/2)+s(1171) s(1175) =< s(1169)*(1/2)+s(1171) s(1177) =< s(1169)*(1/2)+s(1171) s(1179) =< s(1169)*(2/3)+s(1172) s(1178) =< s(1169)*(2/3)+s(1172) s(1174) =< s(1169)*(2/3)+s(1172) s(1175) =< s(1169)*(2/3)+s(1172) s(1180) =< s(1169)*(5/7)+s(1173) s(1179) =< s(1169)*(5/7)+s(1173) s(1178) =< s(1169)*(5/7)+s(1173) s(1174) =< s(1169)*(5/7)+s(1173) s(1175) =< s(1169)*(5/7)+s(1173) s(1185) =< s(1176)*s(1181) s(1186) =< s(1176)*s(1182) s(1187) =< s(1174)*s(1182) s(1188) =< s(1175)*s(1183) s(1189) =< s(1178)*s(1182) s(1190) =< s(1177) s(1191) =< s(1178)*s(1183) s(1192) =< s(1179)*s(1183) s(1193) =< s(1180)*s(1170) s(1194) =< s(1186)*(5/2) s(1195) =< s(1186)*(1/2) s(1196) =< s(1186)*2 s(1197) =< s(1186) s(1198) =< s(1186) s(1199) =< s(1186) s(1197) =< s(1195) s(1198) =< s(1195) s(1199) =< s(1195) s(1199) =< s(1185) s(1200) =< s(1185) s(1199) =< s(1194) s(1200) =< s(1194) s(1201) =< s(1197)*2 s(1202) =< s(1196) s(1203) =< s(1200) s(1204) =< s(1189) s(1205) =< s(1192) s(1206) =< s(1193) with precondition: [Out=2,V1>=3] * Chain [52]: 2*s(1213)+2*s(1214)+24*s(1215)+3*s(1217)+1*s(1218)+2*s(1219)+3*s(1223)+1*s(1226)+1*s(1227)+1*s(1229)+1*s(1230)+12*s(1237)+8*s(1238)+4*s(1240)+12*s(1241)+12*s(1242)+4*s(1243)+3*s(1244)+4*s(1245)+3*s(1252)+2*s(1253)+1*s(1255)+3*s(1256)+3*s(1257)+1 Such that:s(1208) =< V1+1 s(1246) =< 2*V1 s(1211) =< V1/3 s(1212) =< 2/7*V1 s(1247) =< 5/2*V1 s(1248) =< 5/2*V1+27/2 aux(112) =< V1 aux(113) =< V1/2 s(1251) =< aux(112) s(1252) =< aux(112) s(1253) =< aux(112) s(1251) =< aux(113) s(1252) =< aux(113) s(1253) =< aux(113) s(1253) =< s(1248) s(1254) =< s(1248) s(1253) =< s(1247) s(1254) =< s(1247) s(1255) =< s(1251)*2 s(1256) =< s(1246) s(1257) =< s(1254) s(1213) =< aux(112) s(1214) =< aux(112) s(1215) =< aux(112) s(1216) =< aux(113) s(1217) =< aux(113) s(1214) =< aux(113) s(1218) =< s(1211) s(1219) =< s(1212) s(1220) =< aux(112)*(5/2)+16 s(1221) =< aux(112)+1 s(1222) =< aux(112) s(1223) =< aux(112)*2 s(1217) =< s(1208)*(1/2)+aux(113) s(1213) =< s(1208)*(1/2)+aux(113) s(1214) =< s(1208)*(1/2)+aux(113) s(1216) =< s(1208)*(1/2)+aux(113) s(1218) =< s(1208)*(2/3)+s(1211) s(1217) =< s(1208)*(2/3)+s(1211) s(1213) =< s(1208)*(2/3)+s(1211) s(1214) =< s(1208)*(2/3)+s(1211) s(1219) =< s(1208)*(5/7)+s(1212) s(1218) =< s(1208)*(5/7)+s(1212) s(1217) =< s(1208)*(5/7)+s(1212) s(1213) =< s(1208)*(5/7)+s(1212) s(1214) =< s(1208)*(5/7)+s(1212) s(1224) =< s(1215)*s(1220) s(1225) =< s(1215)*s(1221) s(1226) =< s(1213)*s(1221) s(1227) =< s(1214)*s(1222) s(1228) =< s(1217)*s(1221) s(1229) =< s(1216) s(1230) =< s(1217)*s(1222) s(1231) =< s(1218)*s(1222) s(1232) =< s(1219)*aux(112) s(1233) =< s(1225)*(5/2) s(1234) =< s(1225)*(1/2) s(1235) =< s(1225)*2 s(1236) =< s(1225) s(1237) =< s(1225) s(1238) =< s(1225) s(1236) =< s(1234) s(1237) =< s(1234) s(1238) =< s(1234) s(1238) =< s(1224) s(1239) =< s(1224) s(1238) =< s(1233) s(1239) =< s(1233) s(1240) =< s(1236)*2 s(1241) =< s(1235) s(1242) =< s(1239) s(1243) =< s(1228) s(1244) =< s(1231) s(1245) =< s(1232) with precondition: [Out>=1,V1>=3*Out+1] * Chain [51]: 2*s(1263)+2*s(1264)+24*s(1265)+3*s(1267)+1*s(1268)+2*s(1269)+3*s(1273)+1*s(1276)+1*s(1277)+1*s(1279)+1*s(1280)+12*s(1287)+8*s(1288)+4*s(1290)+12*s(1291)+12*s(1292)+4*s(1293)+3*s(1294)+4*s(1295)+1*s(1296)+6*s(1303)+4*s(1304)+2*s(1306)+6*s(1307)+6*s(1308)+4 Such that:s(1296) =< 2 s(1258) =< V1+1 s(1298) =< 2*V1 s(1261) =< V1/3 s(1262) =< 2/7*V1 s(1300) =< 5/2*V1 s(1301) =< 5/2*V1+27/2 aux(114) =< V1 aux(115) =< V1/2 s(1302) =< aux(114) s(1303) =< aux(114) s(1304) =< aux(114) s(1302) =< aux(115) s(1303) =< aux(115) s(1304) =< aux(115) s(1304) =< s(1301) s(1305) =< s(1301) s(1304) =< s(1300) s(1305) =< s(1300) s(1306) =< s(1302)*2 s(1307) =< s(1298) s(1308) =< s(1305) s(1263) =< aux(114) s(1264) =< aux(114) s(1265) =< aux(114) s(1266) =< aux(115) s(1267) =< aux(115) s(1264) =< aux(115) s(1268) =< s(1261) s(1269) =< s(1262) s(1270) =< aux(114)*(5/2)+16 s(1271) =< aux(114)+1 s(1272) =< aux(114) s(1273) =< aux(114)*2 s(1267) =< s(1258)*(1/2)+aux(115) s(1263) =< s(1258)*(1/2)+aux(115) s(1264) =< s(1258)*(1/2)+aux(115) s(1266) =< s(1258)*(1/2)+aux(115) s(1268) =< s(1258)*(2/3)+s(1261) s(1267) =< s(1258)*(2/3)+s(1261) s(1263) =< s(1258)*(2/3)+s(1261) s(1264) =< s(1258)*(2/3)+s(1261) s(1269) =< s(1258)*(5/7)+s(1262) s(1268) =< s(1258)*(5/7)+s(1262) s(1267) =< s(1258)*(5/7)+s(1262) s(1263) =< s(1258)*(5/7)+s(1262) s(1264) =< s(1258)*(5/7)+s(1262) s(1274) =< s(1265)*s(1270) s(1275) =< s(1265)*s(1271) s(1276) =< s(1263)*s(1271) s(1277) =< s(1264)*s(1272) s(1278) =< s(1267)*s(1271) s(1279) =< s(1266) s(1280) =< s(1267)*s(1272) s(1281) =< s(1268)*s(1272) s(1282) =< s(1269)*aux(114) s(1283) =< s(1275)*(5/2) s(1284) =< s(1275)*(1/2) s(1285) =< s(1275)*2 s(1286) =< s(1275) s(1287) =< s(1275) s(1288) =< s(1275) s(1286) =< s(1284) s(1287) =< s(1284) s(1288) =< s(1284) s(1288) =< s(1274) s(1289) =< s(1274) s(1288) =< s(1283) s(1289) =< s(1283) s(1290) =< s(1286)*2 s(1291) =< s(1285) s(1292) =< s(1289) s(1293) =< s(1278) s(1294) =< s(1281) s(1295) =< s(1282) with precondition: [Out>=2,V1+2>=3*Out] * Chain [50]: 2*s(1314)+2*s(1315)+24*s(1316)+3*s(1318)+1*s(1319)+2*s(1320)+3*s(1324)+1*s(1327)+1*s(1328)+1*s(1330)+1*s(1331)+12*s(1338)+8*s(1339)+4*s(1341)+12*s(1342)+12*s(1343)+4*s(1344)+3*s(1345)+4*s(1346)+1*s(1347)+3*s(1354)+2*s(1355)+1*s(1357)+3*s(1358)+3*s(1359)+6 Such that:s(1347) =< 2 s(1309) =< V1+1 s(1348) =< 2*V1 s(1312) =< V1/3 s(1313) =< 2/7*V1 s(1349) =< 5/2*V1 s(1350) =< 5/2*V1+27/2 aux(116) =< V1 aux(117) =< V1/2 s(1353) =< aux(116) s(1354) =< aux(116) s(1355) =< aux(116) s(1353) =< aux(117) s(1354) =< aux(117) s(1355) =< aux(117) s(1355) =< s(1350) s(1356) =< s(1350) s(1355) =< s(1349) s(1356) =< s(1349) s(1357) =< s(1353)*2 s(1358) =< s(1348) s(1359) =< s(1356) s(1314) =< aux(116) s(1315) =< aux(116) s(1316) =< aux(116) s(1317) =< aux(117) s(1318) =< aux(117) s(1315) =< aux(117) s(1319) =< s(1312) s(1320) =< s(1313) s(1321) =< aux(116)*(5/2)+16 s(1322) =< aux(116)+1 s(1323) =< aux(116) s(1324) =< aux(116)*2 s(1318) =< s(1309)*(1/2)+aux(117) s(1314) =< s(1309)*(1/2)+aux(117) s(1315) =< s(1309)*(1/2)+aux(117) s(1317) =< s(1309)*(1/2)+aux(117) s(1319) =< s(1309)*(2/3)+s(1312) s(1318) =< s(1309)*(2/3)+s(1312) s(1314) =< s(1309)*(2/3)+s(1312) s(1315) =< s(1309)*(2/3)+s(1312) s(1320) =< s(1309)*(5/7)+s(1313) s(1319) =< s(1309)*(5/7)+s(1313) s(1318) =< s(1309)*(5/7)+s(1313) s(1314) =< s(1309)*(5/7)+s(1313) s(1315) =< s(1309)*(5/7)+s(1313) s(1325) =< s(1316)*s(1321) s(1326) =< s(1316)*s(1322) s(1327) =< s(1314)*s(1322) s(1328) =< s(1315)*s(1323) s(1329) =< s(1318)*s(1322) s(1330) =< s(1317) s(1331) =< s(1318)*s(1323) s(1332) =< s(1319)*s(1323) s(1333) =< s(1320)*aux(116) s(1334) =< s(1326)*(5/2) s(1335) =< s(1326)*(1/2) s(1336) =< s(1326)*2 s(1337) =< s(1326) s(1338) =< s(1326) s(1339) =< s(1326) s(1337) =< s(1335) s(1338) =< s(1335) s(1339) =< s(1335) s(1339) =< s(1325) s(1340) =< s(1325) s(1339) =< s(1334) s(1340) =< s(1334) s(1341) =< s(1337)*2 s(1342) =< s(1336) s(1343) =< s(1340) s(1344) =< s(1329) s(1345) =< s(1332) s(1346) =< s(1333) with precondition: [Out>=3,V1+7>=4*Out] #### Cost of chains of start(V1,V): * Chain [56]: 272*s(1360)+2*s(1362)+470*s(1364)+4*s(1366)+6*s(1373)+24*s(1380)+16*s(1381)+8*s(1383)+24*s(1384)+24*s(1385)+38*s(1417)+38*s(1418)+57*s(1421)+19*s(1422)+38*s(1423)+57*s(1427)+19*s(1430)+19*s(1431)+19*s(1433)+19*s(1434)+228*s(1441)+152*s(1442)+76*s(1444)+228*s(1445)+228*s(1446)+76*s(1447)+57*s(1448)+76*s(1449)+22*s(1494)+22*s(1495)+33*s(1497)+11*s(1498)+22*s(1499)+33*s(1503)+11*s(1506)+11*s(1507)+11*s(1509)+11*s(1510)+132*s(1517)+88*s(1518)+44*s(1520)+132*s(1521)+132*s(1522)+44*s(1523)+33*s(1524)+44*s(1525)+2*s(1793)+1*s(1794)+6 Such that:aux(118) =< 1 aux(119) =< 2 aux(120) =< V1 aux(121) =< V1+1 aux(122) =< V1-V+1 aux(123) =< 2*V1 aux(124) =< V1/2 aux(125) =< V1/3 aux(126) =< 2/7*V1 aux(127) =< 5/2*V1 aux(128) =< 5/2*V1+27/2 aux(129) =< V aux(130) =< V+1 aux(131) =< V/2 aux(132) =< V/3 aux(133) =< 2/7*V s(1362) =< aux(118) s(1373) =< aux(119) s(1366) =< aux(122) s(1360) =< aux(129) s(1364) =< aux(120) s(1494) =< aux(129) s(1495) =< aux(129) s(1496) =< aux(131) s(1497) =< aux(131) s(1495) =< aux(131) s(1498) =< aux(132) s(1499) =< aux(133) s(1500) =< aux(129)*(5/2)+16 s(1501) =< aux(129)+1 s(1502) =< aux(129) s(1503) =< aux(129)*2 s(1497) =< aux(130)*(1/2)+aux(131) s(1494) =< aux(130)*(1/2)+aux(131) s(1495) =< aux(130)*(1/2)+aux(131) s(1496) =< aux(130)*(1/2)+aux(131) s(1498) =< aux(130)*(2/3)+aux(132) s(1497) =< aux(130)*(2/3)+aux(132) s(1494) =< aux(130)*(2/3)+aux(132) s(1495) =< aux(130)*(2/3)+aux(132) s(1499) =< aux(130)*(5/7)+aux(133) s(1498) =< aux(130)*(5/7)+aux(133) s(1497) =< aux(130)*(5/7)+aux(133) s(1494) =< aux(130)*(5/7)+aux(133) s(1495) =< aux(130)*(5/7)+aux(133) s(1504) =< s(1360)*s(1500) s(1505) =< s(1360)*s(1501) s(1506) =< s(1494)*s(1501) s(1507) =< s(1495)*s(1502) s(1508) =< s(1497)*s(1501) s(1509) =< s(1496) s(1510) =< s(1497)*s(1502) s(1511) =< s(1498)*s(1502) s(1512) =< s(1499)*aux(129) s(1513) =< s(1505)*(5/2) s(1514) =< s(1505)*(1/2) s(1515) =< s(1505)*2 s(1516) =< s(1505) s(1517) =< s(1505) s(1518) =< s(1505) s(1516) =< s(1514) s(1517) =< s(1514) s(1518) =< s(1514) s(1518) =< s(1504) s(1519) =< s(1504) s(1518) =< s(1513) s(1519) =< s(1513) s(1520) =< s(1516)*2 s(1521) =< s(1515) s(1522) =< s(1519) s(1523) =< s(1508) s(1524) =< s(1511) s(1525) =< s(1512) s(1417) =< aux(120) s(1418) =< aux(120) s(1420) =< aux(124) s(1421) =< aux(124) s(1418) =< aux(124) s(1422) =< aux(125) s(1423) =< aux(126) s(1424) =< aux(120)*(5/2)+16 s(1425) =< aux(120)+1 s(1426) =< aux(120) s(1427) =< aux(120)*2 s(1421) =< aux(121)*(1/2)+aux(124) s(1417) =< aux(121)*(1/2)+aux(124) s(1418) =< aux(121)*(1/2)+aux(124) s(1420) =< aux(121)*(1/2)+aux(124) s(1422) =< aux(121)*(2/3)+aux(125) s(1421) =< aux(121)*(2/3)+aux(125) s(1417) =< aux(121)*(2/3)+aux(125) s(1418) =< aux(121)*(2/3)+aux(125) s(1423) =< aux(121)*(5/7)+aux(126) s(1422) =< aux(121)*(5/7)+aux(126) s(1421) =< aux(121)*(5/7)+aux(126) s(1417) =< aux(121)*(5/7)+aux(126) s(1418) =< aux(121)*(5/7)+aux(126) s(1428) =< s(1364)*s(1424) s(1429) =< s(1364)*s(1425) s(1430) =< s(1417)*s(1425) s(1431) =< s(1418)*s(1426) s(1432) =< s(1421)*s(1425) s(1433) =< s(1420) s(1434) =< s(1421)*s(1426) s(1435) =< s(1422)*s(1426) s(1436) =< s(1423)*aux(120) s(1437) =< s(1429)*(5/2) s(1438) =< s(1429)*(1/2) s(1439) =< s(1429)*2 s(1440) =< s(1429) s(1441) =< s(1429) s(1442) =< s(1429) s(1440) =< s(1438) s(1441) =< s(1438) s(1442) =< s(1438) s(1442) =< s(1428) s(1443) =< s(1428) s(1442) =< s(1437) s(1443) =< s(1437) s(1444) =< s(1440)*2 s(1445) =< s(1439) s(1446) =< s(1443) s(1447) =< s(1432) s(1448) =< s(1435) s(1449) =< s(1436) s(1793) =< aux(121) s(1794) =< aux(121) s(1793) =< aux(120) s(1379) =< aux(120) s(1380) =< aux(120) s(1381) =< aux(120) s(1379) =< aux(124) s(1380) =< aux(124) s(1381) =< aux(124) s(1381) =< aux(128) s(1382) =< aux(128) s(1381) =< aux(127) s(1382) =< aux(127) s(1383) =< s(1379)*2 s(1384) =< aux(123) s(1385) =< s(1382) s(1366) =< aux(120) with precondition: [] Closed-form bounds of start(V1,V): ------------------------------------- * Chain [56] with precondition: [] - Upper bound: nat(V1)*5371+20+nat(V1)*1596*nat(V1)+nat(V1)*76*nat(2/7*V1)+nat(V1)*95*nat(V1/2)+nat(V1)*57*nat(V1/3)+nat(V)*3077+nat(V)*924*nat(V)+nat(V)*44*nat(2/7*V)+nat(V)*55*nat(V/2)+nat(V)*33*nat(V/3)+nat(2*V1)*24+nat(2/7*V1)*38+nat(2/7*V)*22+nat(V1+1)*3+nat(5/2*V1+27/2)*24+nat(V1-V+1)*4+nat(V1/2)*152+nat(V1/3)*19+nat(V/2)*88+nat(V/3)*11 - Complexity: n^2 ### Maximum cost of start(V1,V): nat(V1)*5371+20+nat(V1)*1596*nat(V1)+nat(V1)*76*nat(2/7*V1)+nat(V1)*95*nat(V1/2)+nat(V1)*57*nat(V1/3)+nat(V)*3077+nat(V)*924*nat(V)+nat(V)*44*nat(2/7*V)+nat(V)*55*nat(V/2)+nat(V)*33*nat(V/3)+nat(2*V1)*24+nat(2/7*V1)*38+nat(2/7*V)*22+nat(V1+1)*3+nat(5/2*V1+27/2)*24+nat(V1-V+1)*4+nat(V1/2)*152+nat(V1/3)*19+nat(V/2)*88+nat(V/3)*11 Asymptotic class: n^2 * Total analysis performed in 5150 ms. ---------------------------------------- (14) BOUNDS(1, n^2) ---------------------------------------- (15) RelTrsToDecreasingLoopProblemProof (LOWER BOUND(ID)) Transformed a relative TRS into a decreasing-loop problem. ---------------------------------------- (16) Obligation: Analyzing the following TRS for decreasing loops: 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: min(X, 0) -> X min(s(X), s(Y)) -> min(X, Y) quot(0, s(Y)) -> 0 quot(s(X), s(Y)) -> s(quot(min(X, Y), s(Y))) log(s(0)) -> 0 log(s(s(X))) -> s(log(s(quot(X, s(s(0)))))) The (relative) TRS S consists of the following rules: encArg(0) -> 0 encArg(s(x_1)) -> s(encArg(x_1)) encArg(cons_min(x_1, x_2)) -> min(encArg(x_1), encArg(x_2)) encArg(cons_quot(x_1, x_2)) -> quot(encArg(x_1), encArg(x_2)) encArg(cons_log(x_1)) -> log(encArg(x_1)) encode_min(x_1, x_2) -> min(encArg(x_1), encArg(x_2)) encode_0 -> 0 encode_s(x_1) -> s(encArg(x_1)) encode_quot(x_1, x_2) -> quot(encArg(x_1), encArg(x_2)) encode_log(x_1) -> log(encArg(x_1)) Rewrite Strategy: INNERMOST ---------------------------------------- (17) DecreasingLoopProof (LOWER BOUND(ID)) The following loop(s) give(s) rise to the lower bound Omega(n^1): The rewrite sequence min(s(X), s(Y)) ->^+ min(X, Y) gives rise to a decreasing loop by considering the right hand sides subterm at position []. The pumping substitution is [X / s(X), Y / s(Y)]. The result substitution is [ ]. ---------------------------------------- (18) Complex Obligation (BEST) ---------------------------------------- (19) Obligation: Proved the lower bound n^1 for the following 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: min(X, 0) -> X min(s(X), s(Y)) -> min(X, Y) quot(0, s(Y)) -> 0 quot(s(X), s(Y)) -> s(quot(min(X, Y), s(Y))) log(s(0)) -> 0 log(s(s(X))) -> s(log(s(quot(X, s(s(0)))))) The (relative) TRS S consists of the following rules: encArg(0) -> 0 encArg(s(x_1)) -> s(encArg(x_1)) encArg(cons_min(x_1, x_2)) -> min(encArg(x_1), encArg(x_2)) encArg(cons_quot(x_1, x_2)) -> quot(encArg(x_1), encArg(x_2)) encArg(cons_log(x_1)) -> log(encArg(x_1)) encode_min(x_1, x_2) -> min(encArg(x_1), encArg(x_2)) encode_0 -> 0 encode_s(x_1) -> s(encArg(x_1)) encode_quot(x_1, x_2) -> quot(encArg(x_1), encArg(x_2)) encode_log(x_1) -> log(encArg(x_1)) Rewrite Strategy: INNERMOST ---------------------------------------- (20) LowerBoundPropagationProof (FINISHED) Propagated lower bound. ---------------------------------------- (21) BOUNDS(n^1, INF) ---------------------------------------- (22) Obligation: Analyzing the following TRS for decreasing loops: 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: min(X, 0) -> X min(s(X), s(Y)) -> min(X, Y) quot(0, s(Y)) -> 0 quot(s(X), s(Y)) -> s(quot(min(X, Y), s(Y))) log(s(0)) -> 0 log(s(s(X))) -> s(log(s(quot(X, s(s(0)))))) The (relative) TRS S consists of the following rules: encArg(0) -> 0 encArg(s(x_1)) -> s(encArg(x_1)) encArg(cons_min(x_1, x_2)) -> min(encArg(x_1), encArg(x_2)) encArg(cons_quot(x_1, x_2)) -> quot(encArg(x_1), encArg(x_2)) encArg(cons_log(x_1)) -> log(encArg(x_1)) encode_min(x_1, x_2) -> min(encArg(x_1), encArg(x_2)) encode_0 -> 0 encode_s(x_1) -> s(encArg(x_1)) encode_quot(x_1, x_2) -> quot(encArg(x_1), encArg(x_2)) encode_log(x_1) -> log(encArg(x_1)) Rewrite Strategy: INNERMOST