/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), 178 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, 1705 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: pred(s(x)) -> x minus(x, 0) -> x minus(x, s(y)) -> pred(minus(x, y)) quot(0, s(y)) -> 0 quot(s(x), s(y)) -> s(quot(minus(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(s(x_1)) -> s(encArg(x_1)) encArg(0) -> 0 encArg(cons_pred(x_1)) -> pred(encArg(x_1)) encArg(cons_minus(x_1, x_2)) -> minus(encArg(x_1), encArg(x_2)) encArg(cons_quot(x_1, x_2)) -> quot(encArg(x_1), encArg(x_2)) encode_pred(x_1) -> pred(encArg(x_1)) encode_s(x_1) -> s(encArg(x_1)) encode_minus(x_1, x_2) -> minus(encArg(x_1), encArg(x_2)) encode_0 -> 0 encode_quot(x_1, x_2) -> quot(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: pred(s(x)) -> x minus(x, 0) -> x minus(x, s(y)) -> pred(minus(x, y)) quot(0, s(y)) -> 0 quot(s(x), s(y)) -> s(quot(minus(x, y), s(y))) The (relative) TRS S consists of the following rules: encArg(s(x_1)) -> s(encArg(x_1)) encArg(0) -> 0 encArg(cons_pred(x_1)) -> pred(encArg(x_1)) encArg(cons_minus(x_1, x_2)) -> minus(encArg(x_1), encArg(x_2)) encArg(cons_quot(x_1, x_2)) -> quot(encArg(x_1), encArg(x_2)) encode_pred(x_1) -> pred(encArg(x_1)) encode_s(x_1) -> s(encArg(x_1)) encode_minus(x_1, x_2) -> minus(encArg(x_1), encArg(x_2)) encode_0 -> 0 encode_quot(x_1, x_2) -> quot(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: pred(s(x)) -> x minus(x, 0) -> x minus(x, s(y)) -> pred(minus(x, y)) quot(0, s(y)) -> 0 quot(s(x), s(y)) -> s(quot(minus(x, y), s(y))) The (relative) TRS S consists of the following rules: encArg(s(x_1)) -> s(encArg(x_1)) encArg(0) -> 0 encArg(cons_pred(x_1)) -> pred(encArg(x_1)) encArg(cons_minus(x_1, x_2)) -> minus(encArg(x_1), encArg(x_2)) encArg(cons_quot(x_1, x_2)) -> quot(encArg(x_1), encArg(x_2)) encode_pred(x_1) -> pred(encArg(x_1)) encode_s(x_1) -> s(encArg(x_1)) encode_minus(x_1, x_2) -> minus(encArg(x_1), encArg(x_2)) encode_0 -> 0 encode_quot(x_1, x_2) -> quot(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: pred(s(x)) -> x [1] minus(x, 0) -> x [1] minus(x, s(y)) -> pred(minus(x, y)) [1] quot(0, s(y)) -> 0 [1] quot(s(x), s(y)) -> s(quot(minus(x, y), s(y))) [1] encArg(s(x_1)) -> s(encArg(x_1)) [0] encArg(0) -> 0 [0] encArg(cons_pred(x_1)) -> pred(encArg(x_1)) [0] encArg(cons_minus(x_1, x_2)) -> minus(encArg(x_1), encArg(x_2)) [0] encArg(cons_quot(x_1, x_2)) -> quot(encArg(x_1), encArg(x_2)) [0] encode_pred(x_1) -> pred(encArg(x_1)) [0] encode_s(x_1) -> s(encArg(x_1)) [0] encode_minus(x_1, x_2) -> minus(encArg(x_1), encArg(x_2)) [0] encode_0 -> 0 [0] encode_quot(x_1, x_2) -> quot(encArg(x_1), encArg(x_2)) [0] Rewrite Strategy: INNERMOST ---------------------------------------- (7) TypeInferenceProof (BOTH BOUNDS(ID, ID)) Infered types. ---------------------------------------- (8) Obligation: Runtime Complexity Weighted TRS with Types. The TRS R consists of the following rules: pred(s(x)) -> x [1] minus(x, 0) -> x [1] minus(x, s(y)) -> pred(minus(x, y)) [1] quot(0, s(y)) -> 0 [1] quot(s(x), s(y)) -> s(quot(minus(x, y), s(y))) [1] encArg(s(x_1)) -> s(encArg(x_1)) [0] encArg(0) -> 0 [0] encArg(cons_pred(x_1)) -> pred(encArg(x_1)) [0] encArg(cons_minus(x_1, x_2)) -> minus(encArg(x_1), encArg(x_2)) [0] encArg(cons_quot(x_1, x_2)) -> quot(encArg(x_1), encArg(x_2)) [0] encode_pred(x_1) -> pred(encArg(x_1)) [0] encode_s(x_1) -> s(encArg(x_1)) [0] encode_minus(x_1, x_2) -> minus(encArg(x_1), encArg(x_2)) [0] encode_0 -> 0 [0] encode_quot(x_1, x_2) -> quot(encArg(x_1), encArg(x_2)) [0] The TRS has the following type information: pred :: s:0:cons_pred:cons_minus:cons_quot -> s:0:cons_pred:cons_minus:cons_quot s :: s:0:cons_pred:cons_minus:cons_quot -> s:0:cons_pred:cons_minus:cons_quot minus :: s:0:cons_pred:cons_minus:cons_quot -> s:0:cons_pred:cons_minus:cons_quot -> s:0:cons_pred:cons_minus:cons_quot 0 :: s:0:cons_pred:cons_minus:cons_quot quot :: s:0:cons_pred:cons_minus:cons_quot -> s:0:cons_pred:cons_minus:cons_quot -> s:0:cons_pred:cons_minus:cons_quot encArg :: s:0:cons_pred:cons_minus:cons_quot -> s:0:cons_pred:cons_minus:cons_quot cons_pred :: s:0:cons_pred:cons_minus:cons_quot -> s:0:cons_pred:cons_minus:cons_quot cons_minus :: s:0:cons_pred:cons_minus:cons_quot -> s:0:cons_pred:cons_minus:cons_quot -> s:0:cons_pred:cons_minus:cons_quot cons_quot :: s:0:cons_pred:cons_minus:cons_quot -> s:0:cons_pred:cons_minus:cons_quot -> s:0:cons_pred:cons_minus:cons_quot encode_pred :: s:0:cons_pred:cons_minus:cons_quot -> s:0:cons_pred:cons_minus:cons_quot encode_s :: s:0:cons_pred:cons_minus:cons_quot -> s:0:cons_pred:cons_minus:cons_quot encode_minus :: s:0:cons_pred:cons_minus:cons_quot -> s:0:cons_pred:cons_minus:cons_quot -> s:0:cons_pred:cons_minus:cons_quot encode_0 :: s:0:cons_pred:cons_minus:cons_quot encode_quot :: s:0:cons_pred:cons_minus:cons_quot -> s:0:cons_pred:cons_minus:cons_quot -> s:0:cons_pred:cons_minus:cons_quot 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_pred(v0) -> null_encode_pred [0] encode_s(v0) -> null_encode_s [0] encode_minus(v0, v1) -> null_encode_minus [0] encode_0 -> null_encode_0 [0] encode_quot(v0, v1) -> null_encode_quot [0] pred(v0) -> null_pred [0] minus(v0, v1) -> null_minus [0] quot(v0, v1) -> null_quot [0] And the following fresh constants: null_encArg, null_encode_pred, null_encode_s, null_encode_minus, null_encode_0, null_encode_quot, null_pred, null_minus, null_quot ---------------------------------------- (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: pred(s(x)) -> x [1] minus(x, 0) -> x [1] minus(x, s(y)) -> pred(minus(x, y)) [1] quot(0, s(y)) -> 0 [1] quot(s(x), s(y)) -> s(quot(minus(x, y), s(y))) [1] encArg(s(x_1)) -> s(encArg(x_1)) [0] encArg(0) -> 0 [0] encArg(cons_pred(x_1)) -> pred(encArg(x_1)) [0] encArg(cons_minus(x_1, x_2)) -> minus(encArg(x_1), encArg(x_2)) [0] encArg(cons_quot(x_1, x_2)) -> quot(encArg(x_1), encArg(x_2)) [0] encode_pred(x_1) -> pred(encArg(x_1)) [0] encode_s(x_1) -> s(encArg(x_1)) [0] encode_minus(x_1, x_2) -> minus(encArg(x_1), encArg(x_2)) [0] encode_0 -> 0 [0] encode_quot(x_1, x_2) -> quot(encArg(x_1), encArg(x_2)) [0] encArg(v0) -> null_encArg [0] encode_pred(v0) -> null_encode_pred [0] encode_s(v0) -> null_encode_s [0] encode_minus(v0, v1) -> null_encode_minus [0] encode_0 -> null_encode_0 [0] encode_quot(v0, v1) -> null_encode_quot [0] pred(v0) -> null_pred [0] minus(v0, v1) -> null_minus [0] quot(v0, v1) -> null_quot [0] The TRS has the following type information: pred :: s:0:cons_pred:cons_minus:cons_quot:null_encArg:null_encode_pred:null_encode_s:null_encode_minus:null_encode_0:null_encode_quot:null_pred:null_minus:null_quot -> s:0:cons_pred:cons_minus:cons_quot:null_encArg:null_encode_pred:null_encode_s:null_encode_minus:null_encode_0:null_encode_quot:null_pred:null_minus:null_quot s :: s:0:cons_pred:cons_minus:cons_quot:null_encArg:null_encode_pred:null_encode_s:null_encode_minus:null_encode_0:null_encode_quot:null_pred:null_minus:null_quot -> s:0:cons_pred:cons_minus:cons_quot:null_encArg:null_encode_pred:null_encode_s:null_encode_minus:null_encode_0:null_encode_quot:null_pred:null_minus:null_quot minus :: s:0:cons_pred:cons_minus:cons_quot:null_encArg:null_encode_pred:null_encode_s:null_encode_minus:null_encode_0:null_encode_quot:null_pred:null_minus:null_quot -> s:0:cons_pred:cons_minus:cons_quot:null_encArg:null_encode_pred:null_encode_s:null_encode_minus:null_encode_0:null_encode_quot:null_pred:null_minus:null_quot -> s:0:cons_pred:cons_minus:cons_quot:null_encArg:null_encode_pred:null_encode_s:null_encode_minus:null_encode_0:null_encode_quot:null_pred:null_minus:null_quot 0 :: s:0:cons_pred:cons_minus:cons_quot:null_encArg:null_encode_pred:null_encode_s:null_encode_minus:null_encode_0:null_encode_quot:null_pred:null_minus:null_quot quot :: s:0:cons_pred:cons_minus:cons_quot:null_encArg:null_encode_pred:null_encode_s:null_encode_minus:null_encode_0:null_encode_quot:null_pred:null_minus:null_quot -> s:0:cons_pred:cons_minus:cons_quot:null_encArg:null_encode_pred:null_encode_s:null_encode_minus:null_encode_0:null_encode_quot:null_pred:null_minus:null_quot -> s:0:cons_pred:cons_minus:cons_quot:null_encArg:null_encode_pred:null_encode_s:null_encode_minus:null_encode_0:null_encode_quot:null_pred:null_minus:null_quot encArg :: s:0:cons_pred:cons_minus:cons_quot:null_encArg:null_encode_pred:null_encode_s:null_encode_minus:null_encode_0:null_encode_quot:null_pred:null_minus:null_quot -> s:0:cons_pred:cons_minus:cons_quot:null_encArg:null_encode_pred:null_encode_s:null_encode_minus:null_encode_0:null_encode_quot:null_pred:null_minus:null_quot cons_pred :: s:0:cons_pred:cons_minus:cons_quot:null_encArg:null_encode_pred:null_encode_s:null_encode_minus:null_encode_0:null_encode_quot:null_pred:null_minus:null_quot -> s:0:cons_pred:cons_minus:cons_quot:null_encArg:null_encode_pred:null_encode_s:null_encode_minus:null_encode_0:null_encode_quot:null_pred:null_minus:null_quot cons_minus :: s:0:cons_pred:cons_minus:cons_quot:null_encArg:null_encode_pred:null_encode_s:null_encode_minus:null_encode_0:null_encode_quot:null_pred:null_minus:null_quot -> s:0:cons_pred:cons_minus:cons_quot:null_encArg:null_encode_pred:null_encode_s:null_encode_minus:null_encode_0:null_encode_quot:null_pred:null_minus:null_quot -> s:0:cons_pred:cons_minus:cons_quot:null_encArg:null_encode_pred:null_encode_s:null_encode_minus:null_encode_0:null_encode_quot:null_pred:null_minus:null_quot cons_quot :: s:0:cons_pred:cons_minus:cons_quot:null_encArg:null_encode_pred:null_encode_s:null_encode_minus:null_encode_0:null_encode_quot:null_pred:null_minus:null_quot -> s:0:cons_pred:cons_minus:cons_quot:null_encArg:null_encode_pred:null_encode_s:null_encode_minus:null_encode_0:null_encode_quot:null_pred:null_minus:null_quot -> s:0:cons_pred:cons_minus:cons_quot:null_encArg:null_encode_pred:null_encode_s:null_encode_minus:null_encode_0:null_encode_quot:null_pred:null_minus:null_quot encode_pred :: s:0:cons_pred:cons_minus:cons_quot:null_encArg:null_encode_pred:null_encode_s:null_encode_minus:null_encode_0:null_encode_quot:null_pred:null_minus:null_quot -> s:0:cons_pred:cons_minus:cons_quot:null_encArg:null_encode_pred:null_encode_s:null_encode_minus:null_encode_0:null_encode_quot:null_pred:null_minus:null_quot encode_s :: s:0:cons_pred:cons_minus:cons_quot:null_encArg:null_encode_pred:null_encode_s:null_encode_minus:null_encode_0:null_encode_quot:null_pred:null_minus:null_quot -> s:0:cons_pred:cons_minus:cons_quot:null_encArg:null_encode_pred:null_encode_s:null_encode_minus:null_encode_0:null_encode_quot:null_pred:null_minus:null_quot encode_minus :: s:0:cons_pred:cons_minus:cons_quot:null_encArg:null_encode_pred:null_encode_s:null_encode_minus:null_encode_0:null_encode_quot:null_pred:null_minus:null_quot -> s:0:cons_pred:cons_minus:cons_quot:null_encArg:null_encode_pred:null_encode_s:null_encode_minus:null_encode_0:null_encode_quot:null_pred:null_minus:null_quot -> s:0:cons_pred:cons_minus:cons_quot:null_encArg:null_encode_pred:null_encode_s:null_encode_minus:null_encode_0:null_encode_quot:null_pred:null_minus:null_quot encode_0 :: s:0:cons_pred:cons_minus:cons_quot:null_encArg:null_encode_pred:null_encode_s:null_encode_minus:null_encode_0:null_encode_quot:null_pred:null_minus:null_quot encode_quot :: s:0:cons_pred:cons_minus:cons_quot:null_encArg:null_encode_pred:null_encode_s:null_encode_minus:null_encode_0:null_encode_quot:null_pred:null_minus:null_quot -> s:0:cons_pred:cons_minus:cons_quot:null_encArg:null_encode_pred:null_encode_s:null_encode_minus:null_encode_0:null_encode_quot:null_pred:null_minus:null_quot -> s:0:cons_pred:cons_minus:cons_quot:null_encArg:null_encode_pred:null_encode_s:null_encode_minus:null_encode_0:null_encode_quot:null_pred:null_minus:null_quot null_encArg :: s:0:cons_pred:cons_minus:cons_quot:null_encArg:null_encode_pred:null_encode_s:null_encode_minus:null_encode_0:null_encode_quot:null_pred:null_minus:null_quot null_encode_pred :: s:0:cons_pred:cons_minus:cons_quot:null_encArg:null_encode_pred:null_encode_s:null_encode_minus:null_encode_0:null_encode_quot:null_pred:null_minus:null_quot null_encode_s :: s:0:cons_pred:cons_minus:cons_quot:null_encArg:null_encode_pred:null_encode_s:null_encode_minus:null_encode_0:null_encode_quot:null_pred:null_minus:null_quot null_encode_minus :: s:0:cons_pred:cons_minus:cons_quot:null_encArg:null_encode_pred:null_encode_s:null_encode_minus:null_encode_0:null_encode_quot:null_pred:null_minus:null_quot null_encode_0 :: s:0:cons_pred:cons_minus:cons_quot:null_encArg:null_encode_pred:null_encode_s:null_encode_minus:null_encode_0:null_encode_quot:null_pred:null_minus:null_quot null_encode_quot :: s:0:cons_pred:cons_minus:cons_quot:null_encArg:null_encode_pred:null_encode_s:null_encode_minus:null_encode_0:null_encode_quot:null_pred:null_minus:null_quot null_pred :: s:0:cons_pred:cons_minus:cons_quot:null_encArg:null_encode_pred:null_encode_s:null_encode_minus:null_encode_0:null_encode_quot:null_pred:null_minus:null_quot null_minus :: s:0:cons_pred:cons_minus:cons_quot:null_encArg:null_encode_pred:null_encode_s:null_encode_minus:null_encode_0:null_encode_quot:null_pred:null_minus:null_quot null_quot :: s:0:cons_pred:cons_minus:cons_quot:null_encArg:null_encode_pred:null_encode_s:null_encode_minus:null_encode_0:null_encode_quot:null_pred:null_minus:null_quot 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_pred => 0 null_encode_s => 0 null_encode_minus => 0 null_encode_0 => 0 null_encode_quot => 0 null_pred => 0 null_minus => 0 null_quot => 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 }-> pred(encArg(x_1)) :|: z = 1 + x_1, x_1 >= 0 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 }-> 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_minus(z, z') -{ 0 }-> minus(encArg(x_1), encArg(x_2)) :|: x_1 >= 0, x_2 >= 0, z = x_1, z' = x_2 encode_minus(z, z') -{ 0 }-> 0 :|: v0 >= 0, v1 >= 0, z = v0, z' = v1 encode_pred(z) -{ 0 }-> pred(encArg(x_1)) :|: x_1 >= 0, z = x_1 encode_pred(z) -{ 0 }-> 0 :|: v0 >= 0, z = v0 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 minus(z, z') -{ 1 }-> x :|: x >= 0, z = x, z' = 0 minus(z, z') -{ 1 }-> pred(minus(x, y)) :|: z' = 1 + y, x >= 0, y >= 0, z = x minus(z, z') -{ 0 }-> 0 :|: v0 >= 0, v1 >= 0, z = v0, z' = v1 pred(z) -{ 1 }-> x :|: x >= 0, z = 1 + x pred(z) -{ 0 }-> 0 :|: v0 >= 0, z = v0 quot(z, z') -{ 1 }-> 0 :|: z' = 1 + y, y >= 0, z = 0 quot(z, z') -{ 0 }-> 0 :|: v0 >= 0, v1 >= 0, z = v0, z' = v1 quot(z, z') -{ 1 }-> 1 + quot(minus(x, y), 1 + y) :|: z' = 1 + y, x >= 0, y >= 0, z = 1 + x Only complete derivations are relevant for the runtime complexity. ---------------------------------------- (13) CompleteCoflocoProof (FINISHED) Transformed the RNTS (where only complete derivations are relevant) into cost relations for CoFloCo: eq(start(V, V2),0,[pred(V, Out)],[V >= 0]). eq(start(V, V2),0,[minus(V, V2, Out)],[V >= 0,V2 >= 0]). eq(start(V, V2),0,[quot(V, V2, Out)],[V >= 0,V2 >= 0]). eq(start(V, V2),0,[encArg(V, Out)],[V >= 0]). eq(start(V, V2),0,[fun(V, Out)],[V >= 0]). eq(start(V, V2),0,[fun1(V, Out)],[V >= 0]). eq(start(V, V2),0,[fun2(V, V2, Out)],[V >= 0,V2 >= 0]). eq(start(V, V2),0,[fun3(Out)],[]). eq(start(V, V2),0,[fun4(V, V2, Out)],[V >= 0,V2 >= 0]). eq(pred(V, Out),1,[],[Out = V1,V1 >= 0,V = 1 + V1]). eq(minus(V, V2, Out),1,[],[Out = V3,V3 >= 0,V = V3,V2 = 0]). eq(minus(V, V2, Out),1,[minus(V4, V5, Ret0),pred(Ret0, Ret)],[Out = Ret,V2 = 1 + V5,V4 >= 0,V5 >= 0,V = V4]). eq(quot(V, V2, Out),1,[],[Out = 0,V2 = 1 + V6,V6 >= 0,V = 0]). eq(quot(V, V2, Out),1,[minus(V7, V8, Ret10),quot(Ret10, 1 + V8, Ret1)],[Out = 1 + Ret1,V2 = 1 + V8,V7 >= 0,V8 >= 0,V = 1 + V7]). eq(encArg(V, Out),0,[encArg(V9, Ret11)],[Out = 1 + Ret11,V = 1 + V9,V9 >= 0]). eq(encArg(V, Out),0,[],[Out = 0,V = 0]). eq(encArg(V, Out),0,[encArg(V10, Ret01),pred(Ret01, Ret2)],[Out = Ret2,V = 1 + V10,V10 >= 0]). eq(encArg(V, Out),0,[encArg(V11, Ret02),encArg(V12, Ret12),minus(Ret02, Ret12, Ret3)],[Out = Ret3,V11 >= 0,V = 1 + V11 + V12,V12 >= 0]). eq(encArg(V, Out),0,[encArg(V14, Ret03),encArg(V13, Ret13),quot(Ret03, Ret13, Ret4)],[Out = Ret4,V14 >= 0,V = 1 + V13 + V14,V13 >= 0]). eq(fun(V, Out),0,[encArg(V15, Ret04),pred(Ret04, Ret5)],[Out = Ret5,V15 >= 0,V = V15]). eq(fun1(V, Out),0,[encArg(V16, Ret14)],[Out = 1 + Ret14,V16 >= 0,V = V16]). eq(fun2(V, V2, Out),0,[encArg(V18, Ret05),encArg(V17, Ret15),minus(Ret05, Ret15, Ret6)],[Out = Ret6,V18 >= 0,V17 >= 0,V = V18,V2 = V17]). eq(fun3(Out),0,[],[Out = 0]). eq(fun4(V, V2, Out),0,[encArg(V20, Ret06),encArg(V19, Ret16),quot(Ret06, Ret16, Ret7)],[Out = Ret7,V20 >= 0,V19 >= 0,V = V20,V2 = V19]). eq(encArg(V, Out),0,[],[Out = 0,V21 >= 0,V = V21]). eq(fun(V, Out),0,[],[Out = 0,V22 >= 0,V = V22]). eq(fun1(V, Out),0,[],[Out = 0,V23 >= 0,V = V23]). eq(fun2(V, V2, Out),0,[],[Out = 0,V24 >= 0,V25 >= 0,V = V24,V2 = V25]). eq(fun4(V, V2, Out),0,[],[Out = 0,V26 >= 0,V27 >= 0,V = V26,V2 = V27]). eq(pred(V, Out),0,[],[Out = 0,V28 >= 0,V = V28]). eq(minus(V, V2, Out),0,[],[Out = 0,V29 >= 0,V30 >= 0,V = V29,V2 = V30]). eq(quot(V, V2, Out),0,[],[Out = 0,V31 >= 0,V32 >= 0,V = V31,V2 = V32]). input_output_vars(pred(V,Out),[V],[Out]). input_output_vars(minus(V,V2,Out),[V,V2],[Out]). input_output_vars(quot(V,V2,Out),[V,V2],[Out]). input_output_vars(encArg(V,Out),[V],[Out]). input_output_vars(fun(V,Out),[V],[Out]). input_output_vars(fun1(V,Out),[V],[Out]). input_output_vars(fun2(V,V2,Out),[V,V2],[Out]). input_output_vars(fun3(Out),[],[Out]). input_output_vars(fun4(V,V2,Out),[V,V2],[Out]). CoFloCo proof output: Preprocessing Cost Relations ===================================== #### Computed strongly connected components 0. non_recursive : [pred/2] 1. recursive [non_tail] : [minus/3] 2. recursive : [quot/3] 3. recursive [non_tail,multiple] : [encArg/2] 4. non_recursive : [fun/2] 5. non_recursive : [fun1/2] 6. non_recursive : [fun2/3] 7. non_recursive : [fun3/1] 8. non_recursive : [fun4/3] 9. non_recursive : [start/2] #### Obtained direct recursion through partial evaluation 0. SCC is partially evaluated into pred/2 1. SCC is partially evaluated into minus/3 2. SCC is partially evaluated into quot/3 3. SCC is partially evaluated into encArg/2 4. SCC is partially evaluated into fun/2 5. SCC is partially evaluated into fun1/2 6. SCC is partially evaluated into fun2/3 7. SCC is completely evaluated into other SCCs 8. SCC is partially evaluated into fun4/3 9. SCC is partially evaluated into start/2 Control-Flow Refinement of Cost Relations ===================================== ### Specialization of cost equations pred/2 * CE 10 is refined into CE [31] * CE 11 is refined into CE [32] ### Cost equations --> "Loop" of pred/2 * CEs [31] --> Loop 16 * CEs [32] --> Loop 17 ### Ranking functions of CR pred(V,Out) #### Partial ranking functions of CR pred(V,Out) ### Specialization of cost equations minus/3 * CE 14 is refined into CE [33] * CE 12 is refined into CE [34] * CE 13 is refined into CE [35,36] ### Cost equations --> "Loop" of minus/3 * CEs [36] --> Loop 18 * CEs [35] --> Loop 19 * CEs [33] --> Loop 20 * CEs [34] --> Loop 21 ### Ranking functions of CR minus(V,V2,Out) * RF of phase [18]: [V2] * RF of phase [19]: [V2] #### Partial ranking functions of CR minus(V,V2,Out) * Partial RF of phase [18]: - RF of loop [18:1]: V2 * Partial RF of phase [19]: - RF of loop [19:1]: V2 ### Specialization of cost equations quot/3 * CE 15 is refined into CE [37] * CE 17 is refined into CE [38] * CE 16 is refined into CE [39,40,41] ### Cost equations --> "Loop" of quot/3 * CEs [41] --> Loop 22 * CEs [40] --> Loop 23 * CEs [39] --> Loop 24 * CEs [37,38] --> Loop 25 ### Ranking functions of CR quot(V,V2,Out) * RF of phase [22]: [V-1,V-V2+1] * RF of phase [24]: [V] #### Partial ranking functions of CR quot(V,V2,Out) * Partial RF of phase [22]: - RF of loop [22:1]: V-1 V-V2+1 * Partial RF of phase [24]: - RF of loop [24:1]: V ### Specialization of cost equations encArg/2 * CE 19 is refined into CE [42] * CE 21 is refined into CE [43,44,45] * CE 22 is refined into CE [46,47,48,49,50] * CE 18 is refined into CE [51] * CE 20 is refined into CE [52,53] ### Cost equations --> "Loop" of encArg/2 * CEs [51] --> Loop 26 * CEs [53] --> Loop 27 * CEs [52] --> Loop 28 * CEs [50] --> Loop 29 * CEs [49] --> Loop 30 * CEs [45] --> Loop 31 * CEs [46] --> Loop 32 * CEs [43] --> Loop 33 * CEs [48] --> Loop 34 * CEs [44,47] --> Loop 35 * CEs [42] --> Loop 36 ### Ranking functions of CR encArg(V,Out) * RF of phase [26,27,28,29,30,31,32,33,34,35]: [V] #### Partial ranking functions of CR encArg(V,Out) * Partial RF of phase [26,27,28,29,30,31,32,33,34,35]: - RF of loop [26:1,27:1,28:1,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,35:2]: V ### Specialization of cost equations fun/2 * CE 23 is refined into CE [54,55,56] * CE 24 is refined into CE [57] ### Cost equations --> "Loop" of fun/2 * CEs [56] --> Loop 37 * CEs [54,55,57] --> Loop 38 ### Ranking functions of CR fun(V,Out) #### Partial ranking functions of CR fun(V,Out) ### Specialization of cost equations fun1/2 * CE 25 is refined into CE [58,59] * CE 26 is refined into CE [60] ### Cost equations --> "Loop" of fun1/2 * CEs [59] --> Loop 39 * CEs [58] --> Loop 40 * CEs [60] --> Loop 41 ### Ranking functions of CR fun1(V,Out) #### Partial ranking functions of CR fun1(V,Out) ### Specialization of cost equations fun2/3 * CE 27 is refined into CE [61,62,63,64,65,66,67,68,69] * CE 28 is refined into CE [70] ### Cost equations --> "Loop" of fun2/3 * CEs [65,67,69] --> Loop 42 * CEs [61,62,63,64,66,68,70] --> Loop 43 ### Ranking functions of CR fun2(V,V2,Out) #### Partial ranking functions of CR fun2(V,V2,Out) ### Specialization of cost equations fun4/3 * CE 29 is refined into CE [71,72,73,74,75,76,77,78] * CE 30 is refined into CE [79] ### Cost equations --> "Loop" of fun4/3 * CEs [74,76,77,78] --> Loop 44 * CEs [71,72,73,75,79] --> Loop 45 ### Ranking functions of CR fun4(V,V2,Out) #### Partial ranking functions of CR fun4(V,V2,Out) ### Specialization of cost equations start/2 * CE 1 is refined into CE [80,81] * CE 2 is refined into CE [82,83,84] * CE 3 is refined into CE [85,86,87,88,89] * CE 4 is refined into CE [90,91] * CE 5 is refined into CE [92,93] * CE 6 is refined into CE [94,95,96] * CE 7 is refined into CE [97,98] * CE 8 is refined into CE [99] * CE 9 is refined into CE [100,101] ### Cost equations --> "Loop" of start/2 * CEs [80,81,82,83,84,85,86,87,88,89,90,91,92,93,94,95,96,97,98,99,100,101] --> Loop 46 ### Ranking functions of CR start(V,V2) #### Partial ranking functions of CR start(V,V2) Computing Bounds ===================================== #### Cost of chains of pred(V,Out): * Chain [17]: 0 with precondition: [Out=0,V>=0] * Chain [16]: 1 with precondition: [V=Out+1,V>=1] #### Cost of chains of minus(V,V2,Out): * Chain [[19],[18],21]: 3*it(18)+1 Such that:aux(1) =< V2 it(18) =< aux(1) with precondition: [Out=0,V>=1,V2>=2] * Chain [[19],21]: 1*it(19)+1 Such that:it(19) =< V2 with precondition: [Out=0,V>=0,V2>=1] * Chain [[19],20]: 1*it(19)+0 Such that:it(19) =< V2 with precondition: [Out=0,V>=0,V2>=1] * Chain [[18],21]: 2*it(18)+1 Such that:it(18) =< V2 with precondition: [V=Out+V2,V2>=1,V>=V2] * Chain [21]: 1 with precondition: [V2=0,V=Out,V>=0] * Chain [20]: 0 with precondition: [Out=0,V>=0,V2>=0] #### Cost of chains of quot(V,V2,Out): * Chain [[24],25]: 2*it(24)+1 Such that:it(24) =< Out with precondition: [V2=1,Out>=1,V>=Out] * Chain [[24],23,25]: 2*it(24)+5*s(6)+3 Such that:s(5) =< 1 it(24) =< Out s(6) =< s(5) with precondition: [V2=1,Out>=2,V>=Out] * Chain [[22],25]: 2*it(22)+2*s(9)+1 Such that:it(22) =< V-V2+1 aux(5) =< V it(22) =< aux(5) s(9) =< aux(5) with precondition: [V2>=2,Out>=1,V+2>=2*Out+V2] * Chain [[22],23,25]: 2*it(22)+5*s(6)+2*s(9)+3 Such that:it(22) =< V-V2+1 s(5) =< V2 aux(6) =< V s(6) =< s(5) it(22) =< aux(6) s(9) =< aux(6) with precondition: [V2>=2,Out>=2,V+3>=2*Out+V2] * Chain [25]: 1 with precondition: [Out=0,V>=0,V2>=0] * Chain [23,25]: 5*s(6)+3 Such that:s(5) =< V2 s(6) =< s(5) with precondition: [Out=1,V>=1,V2>=1] #### Cost of chains of encArg(V,Out): * Chain [36]: 0 with precondition: [Out=0,V>=0] * Chain [multiple([26,27,28,29,30,31,32,33,34,35],[[36]])]: 3*it(27)+3*it(29)+1*it(30)+7*it(31)+9*s(44)+4*s(46)+2*s(48)+4*s(49)+5*s(50)+5*s(53)+5*s(55)+0 Such that:aux(25) =< V aux(26) =< V/2 aux(27) =< V/3 aux(28) =< 2/7*V it(27) =< aux(25) it(29) =< aux(25) it(30) =< aux(25) it(31) =< aux(25) it(31) =< aux(26) it(30) =< aux(27) it(29) =< aux(28) aux(18) =< aux(25)+1 aux(13) =< aux(25) s(56) =< it(27)*aux(18) s(54) =< it(31)*aux(13) s(52) =< it(31)*aux(18) s(48) =< it(31)*aux(13) s(47) =< it(30)*aux(13) s(45) =< it(29)*aux(25) s(55) =< s(56) s(53) =< s(54) s(49) =< s(52) s(50) =< aux(26) s(46) =< s(47) s(44) =< s(45) with precondition: [V>=1,Out>=0,V>=Out] #### Cost of chains of fun(V,Out): * Chain [38]: 3*s(61)+3*s(62)+1*s(63)+7*s(64)+2*s(70)+5*s(73)+5*s(74)+4*s(75)+5*s(76)+4*s(77)+9*s(78)+0 Such that:s(57) =< V s(58) =< V/2 s(59) =< V/3 s(60) =< 2/7*V s(61) =< s(57) s(62) =< s(57) s(63) =< s(57) s(64) =< s(57) s(64) =< s(58) s(63) =< s(59) s(62) =< s(60) s(65) =< s(57)+1 s(66) =< s(57) s(67) =< s(61)*s(65) s(68) =< s(64)*s(66) s(69) =< s(64)*s(65) s(70) =< s(64)*s(66) s(71) =< s(63)*s(66) s(72) =< s(62)*s(57) s(73) =< s(67) s(74) =< s(68) s(75) =< s(69) s(76) =< s(58) s(77) =< s(71) s(78) =< s(72) with precondition: [Out=0,V>=0] * Chain [37]: 3*s(83)+3*s(84)+1*s(85)+7*s(86)+2*s(92)+5*s(95)+5*s(96)+4*s(97)+5*s(98)+4*s(99)+9*s(100)+1 Such that:s(79) =< V s(80) =< V/2 s(81) =< V/3 s(82) =< 2/7*V s(83) =< s(79) s(84) =< s(79) s(85) =< s(79) s(86) =< s(79) s(86) =< s(80) s(85) =< s(81) s(84) =< s(82) s(87) =< s(79)+1 s(88) =< s(79) s(89) =< s(83)*s(87) s(90) =< s(86)*s(88) s(91) =< s(86)*s(87) s(92) =< s(86)*s(88) s(93) =< s(85)*s(88) s(94) =< s(84)*s(79) s(95) =< s(89) s(96) =< s(90) s(97) =< s(91) s(98) =< s(80) s(99) =< s(93) s(100) =< s(94) with precondition: [Out>=0,V>=Out+1] #### Cost of chains of fun1(V,Out): * Chain [41]: 0 with precondition: [Out=0,V>=0] * Chain [40]: 0 with precondition: [Out=1,V>=0] * Chain [39]: 3*s(105)+3*s(106)+1*s(107)+7*s(108)+2*s(114)+5*s(117)+5*s(118)+4*s(119)+5*s(120)+4*s(121)+9*s(122)+0 Such that:s(101) =< V s(102) =< V/2 s(103) =< V/3 s(104) =< 2/7*V s(105) =< s(101) s(106) =< s(101) s(107) =< s(101) s(108) =< s(101) s(108) =< s(102) s(107) =< s(103) s(106) =< s(104) s(109) =< s(101)+1 s(110) =< s(101) s(111) =< s(105)*s(109) s(112) =< s(108)*s(110) s(113) =< s(108)*s(109) s(114) =< s(108)*s(110) s(115) =< s(107)*s(110) s(116) =< s(106)*s(101) s(117) =< s(111) s(118) =< s(112) s(119) =< s(113) s(120) =< s(102) s(121) =< s(115) s(122) =< s(116) with precondition: [V>=1,Out>=1,V+1>=Out] #### Cost of chains of fun2(V,V2,Out): * Chain [43]: 19*s(129)+9*s(130)+3*s(131)+21*s(132)+6*s(138)+15*s(141)+15*s(142)+12*s(143)+15*s(144)+12*s(145)+27*s(146)+6*s(175)+6*s(176)+2*s(177)+14*s(178)+4*s(184)+10*s(187)+10*s(188)+8*s(189)+10*s(190)+8*s(191)+18*s(192)+1 Such that:aux(31) =< V aux(32) =< V/2 aux(33) =< V/3 aux(34) =< 2/7*V aux(35) =< V2 aux(36) =< V2/2 aux(37) =< V2/3 aux(38) =< 2/7*V2 s(175) =< aux(31) s(176) =< aux(31) s(177) =< aux(31) s(178) =< aux(31) s(178) =< aux(32) s(177) =< aux(33) s(176) =< aux(34) s(179) =< aux(31)+1 s(180) =< aux(31) s(181) =< s(175)*s(179) s(182) =< s(178)*s(180) s(183) =< s(178)*s(179) s(184) =< s(178)*s(180) s(185) =< s(177)*s(180) s(186) =< s(176)*aux(31) s(187) =< s(181) s(188) =< s(182) s(189) =< s(183) s(190) =< aux(32) s(191) =< s(185) s(192) =< s(186) s(129) =< aux(35) s(130) =< aux(35) s(131) =< aux(35) s(132) =< aux(35) s(132) =< aux(36) s(131) =< aux(37) s(130) =< aux(38) s(133) =< aux(35)+1 s(134) =< aux(35) s(135) =< s(129)*s(133) s(136) =< s(132)*s(134) s(137) =< s(132)*s(133) s(138) =< s(132)*s(134) s(139) =< s(131)*s(134) s(140) =< s(130)*aux(35) s(141) =< s(135) s(142) =< s(136) s(143) =< s(137) s(144) =< aux(36) s(145) =< s(139) s(146) =< s(140) with precondition: [Out=0,V>=0,V2>=0] * Chain [42]: 9*s(245)+9*s(246)+3*s(247)+21*s(248)+6*s(254)+15*s(257)+15*s(258)+12*s(259)+15*s(260)+12*s(261)+27*s(262)+8*s(289)+6*s(290)+2*s(291)+14*s(292)+4*s(298)+10*s(301)+10*s(302)+8*s(303)+10*s(304)+8*s(305)+18*s(306)+1 Such that:aux(40) =< V aux(41) =< V/2 aux(42) =< V/3 aux(43) =< 2/7*V aux(44) =< V2 aux(45) =< V2/2 aux(46) =< V2/3 aux(47) =< 2/7*V2 s(245) =< aux(40) s(246) =< aux(40) s(247) =< aux(40) s(248) =< aux(40) s(248) =< aux(41) s(247) =< aux(42) s(246) =< aux(43) s(249) =< aux(40)+1 s(250) =< aux(40) s(251) =< s(245)*s(249) s(252) =< s(248)*s(250) s(253) =< s(248)*s(249) s(254) =< s(248)*s(250) s(255) =< s(247)*s(250) s(256) =< s(246)*aux(40) s(257) =< s(251) s(258) =< s(252) s(259) =< s(253) s(260) =< aux(41) s(261) =< s(255) s(262) =< s(256) s(289) =< aux(44) s(290) =< aux(44) s(291) =< aux(44) s(292) =< aux(44) s(292) =< aux(45) s(291) =< aux(46) s(290) =< aux(47) s(293) =< aux(44)+1 s(294) =< aux(44) s(295) =< s(289)*s(293) s(296) =< s(292)*s(294) s(297) =< s(292)*s(293) s(298) =< s(292)*s(294) s(299) =< s(291)*s(294) s(300) =< s(290)*aux(44) s(301) =< s(295) s(302) =< s(296) s(303) =< s(297) s(304) =< aux(45) s(305) =< s(299) s(306) =< s(300) with precondition: [V>=1,V2>=0,Out>=0,V>=Out] #### Cost of chains of fun4(V,V2,Out): * Chain [45]: 6*s(356)+6*s(357)+2*s(358)+14*s(359)+4*s(365)+10*s(368)+10*s(369)+8*s(370)+10*s(371)+8*s(372)+18*s(373)+6*s(378)+6*s(379)+2*s(380)+14*s(381)+4*s(387)+10*s(390)+10*s(391)+8*s(392)+10*s(393)+8*s(394)+18*s(395)+1 Such that:aux(48) =< V aux(49) =< V/2 aux(50) =< V/3 aux(51) =< 2/7*V aux(52) =< V2 aux(53) =< V2/2 aux(54) =< V2/3 aux(55) =< 2/7*V2 s(378) =< aux(48) s(379) =< aux(48) s(380) =< aux(48) s(381) =< aux(48) s(381) =< aux(49) s(380) =< aux(50) s(379) =< aux(51) s(382) =< aux(48)+1 s(383) =< aux(48) s(384) =< s(378)*s(382) s(385) =< s(381)*s(383) s(386) =< s(381)*s(382) s(387) =< s(381)*s(383) s(388) =< s(380)*s(383) s(389) =< s(379)*aux(48) s(390) =< s(384) s(391) =< s(385) s(392) =< s(386) s(393) =< aux(49) s(394) =< s(388) s(395) =< s(389) s(356) =< aux(52) s(357) =< aux(52) s(358) =< aux(52) s(359) =< aux(52) s(359) =< aux(53) s(358) =< aux(54) s(357) =< aux(55) s(360) =< aux(52)+1 s(361) =< aux(52) s(362) =< s(356)*s(360) s(363) =< s(359)*s(361) s(364) =< s(359)*s(360) s(365) =< s(359)*s(361) s(366) =< s(358)*s(361) s(367) =< s(357)*aux(52) s(368) =< s(362) s(369) =< s(363) s(370) =< s(364) s(371) =< aux(53) s(372) =< s(366) s(373) =< s(367) with precondition: [Out=0,V>=0,V2>=0] * Chain [44]: 22*s(444)+12*s(445)+4*s(446)+28*s(447)+8*s(453)+20*s(456)+20*s(457)+16*s(458)+20*s(459)+16*s(460)+36*s(461)+17*s(466)+12*s(467)+4*s(468)+28*s(469)+8*s(475)+20*s(478)+20*s(479)+16*s(480)+20*s(481)+16*s(482)+36*s(483)+5*s(487)+2*s(625)+5*s(628)+3 Such that:s(484) =< 1 aux(60) =< V+1 aux(61) =< V aux(62) =< V/2 aux(63) =< V/3 aux(64) =< 2/7*V aux(65) =< V2 aux(66) =< V2/2 aux(67) =< V2/3 aux(68) =< 2/7*V2 s(444) =< aux(61) s(487) =< s(484) s(466) =< aux(65) s(467) =< aux(65) s(468) =< aux(65) s(469) =< aux(65) s(469) =< aux(66) s(468) =< aux(67) s(467) =< aux(68) s(470) =< aux(65)+1 s(471) =< aux(65) s(472) =< s(466)*s(470) s(473) =< s(469)*s(471) s(474) =< s(469)*s(470) s(475) =< s(469)*s(471) s(476) =< s(468)*s(471) s(477) =< s(467)*aux(65) s(478) =< s(472) s(479) =< s(473) s(480) =< s(474) s(481) =< aux(66) s(482) =< s(476) s(483) =< s(477) s(445) =< aux(61) s(446) =< aux(61) s(447) =< aux(61) s(447) =< aux(62) s(446) =< aux(63) s(445) =< aux(64) s(448) =< aux(61)+1 s(449) =< aux(61) s(450) =< s(444)*s(448) s(451) =< s(447)*s(449) s(452) =< s(447)*s(448) s(453) =< s(447)*s(449) s(454) =< s(446)*s(449) s(455) =< s(445)*aux(61) s(456) =< s(450) s(457) =< s(451) s(458) =< s(452) s(459) =< aux(62) s(460) =< s(454) s(461) =< s(455) s(625) =< aux(60) s(628) =< aux(60) s(625) =< aux(61) with precondition: [V2>=1,Out>=1,V>=Out] #### Cost of chains of start(V,V2): * Chain [46]: 67*s(631)+63*s(635)+10*s(636)+4*s(639)+45*s(652)+15*s(653)+105*s(654)+30*s(660)+75*s(663)+75*s(664)+60*s(665)+75*s(666)+60*s(667)+135*s(668)+33*s(762)+11*s(763)+77*s(764)+22*s(770)+55*s(773)+55*s(774)+44*s(775)+55*s(776)+44*s(777)+99*s(778)+2*s(914)+5*s(915)+3 Such that:s(868) =< V+1 aux(69) =< 1 aux(70) =< V aux(71) =< V-V2+1 aux(72) =< V/2 aux(73) =< V/3 aux(74) =< 2/7*V aux(75) =< V2 aux(76) =< V2/2 aux(77) =< V2/3 aux(78) =< 2/7*V2 s(639) =< aux(71) s(631) =< aux(75) s(635) =< aux(70) s(636) =< aux(69) s(762) =< aux(75) s(763) =< aux(75) s(764) =< aux(75) s(764) =< aux(76) s(763) =< aux(77) s(762) =< aux(78) s(765) =< aux(75)+1 s(766) =< aux(75) s(767) =< s(631)*s(765) s(768) =< s(764)*s(766) s(769) =< s(764)*s(765) s(770) =< s(764)*s(766) s(771) =< s(763)*s(766) s(772) =< s(762)*aux(75) s(773) =< s(767) s(774) =< s(768) s(775) =< s(769) s(776) =< aux(76) s(777) =< s(771) s(778) =< s(772) s(652) =< aux(70) s(653) =< aux(70) s(654) =< aux(70) s(654) =< aux(72) s(653) =< aux(73) s(652) =< aux(74) s(655) =< aux(70)+1 s(656) =< aux(70) s(657) =< s(635)*s(655) s(658) =< s(654)*s(656) s(659) =< s(654)*s(655) s(660) =< s(654)*s(656) s(661) =< s(653)*s(656) s(662) =< s(652)*aux(70) s(663) =< s(657) s(664) =< s(658) s(665) =< s(659) s(666) =< aux(72) s(667) =< s(661) s(668) =< s(662) s(914) =< s(868) s(915) =< s(868) s(914) =< aux(70) s(639) =< aux(70) with precondition: [] Closed-form bounds of start(V,V2): ------------------------------------- * Chain [46] with precondition: [] - Upper bound: nat(V)*363+13+nat(V)*435*nat(V)+nat(V2)*287+nat(V2)*319*nat(V2)+nat(V+1)*7+nat(V-V2+1)*4+nat(V/2)*75+nat(V2/2)*55 - Complexity: n^2 ### Maximum cost of start(V,V2): nat(V)*363+13+nat(V)*435*nat(V)+nat(V2)*287+nat(V2)*319*nat(V2)+nat(V+1)*7+nat(V-V2+1)*4+nat(V/2)*75+nat(V2/2)*55 Asymptotic class: n^2 * Total analysis performed in 1495 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: pred(s(x)) -> x minus(x, 0) -> x minus(x, s(y)) -> pred(minus(x, y)) quot(0, s(y)) -> 0 quot(s(x), s(y)) -> s(quot(minus(x, y), s(y))) The (relative) TRS S consists of the following rules: encArg(s(x_1)) -> s(encArg(x_1)) encArg(0) -> 0 encArg(cons_pred(x_1)) -> pred(encArg(x_1)) encArg(cons_minus(x_1, x_2)) -> minus(encArg(x_1), encArg(x_2)) encArg(cons_quot(x_1, x_2)) -> quot(encArg(x_1), encArg(x_2)) encode_pred(x_1) -> pred(encArg(x_1)) encode_s(x_1) -> s(encArg(x_1)) encode_minus(x_1, x_2) -> minus(encArg(x_1), encArg(x_2)) encode_0 -> 0 encode_quot(x_1, x_2) -> quot(encArg(x_1), encArg(x_2)) 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 minus(x, s(y)) ->^+ pred(minus(x, y)) gives rise to a decreasing loop by considering the right hand sides subterm at position [0]. The pumping substitution is [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: pred(s(x)) -> x minus(x, 0) -> x minus(x, s(y)) -> pred(minus(x, y)) quot(0, s(y)) -> 0 quot(s(x), s(y)) -> s(quot(minus(x, y), s(y))) The (relative) TRS S consists of the following rules: encArg(s(x_1)) -> s(encArg(x_1)) encArg(0) -> 0 encArg(cons_pred(x_1)) -> pred(encArg(x_1)) encArg(cons_minus(x_1, x_2)) -> minus(encArg(x_1), encArg(x_2)) encArg(cons_quot(x_1, x_2)) -> quot(encArg(x_1), encArg(x_2)) encode_pred(x_1) -> pred(encArg(x_1)) encode_s(x_1) -> s(encArg(x_1)) encode_minus(x_1, x_2) -> minus(encArg(x_1), encArg(x_2)) encode_0 -> 0 encode_quot(x_1, x_2) -> quot(encArg(x_1), encArg(x_2)) 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: pred(s(x)) -> x minus(x, 0) -> x minus(x, s(y)) -> pred(minus(x, y)) quot(0, s(y)) -> 0 quot(s(x), s(y)) -> s(quot(minus(x, y), s(y))) The (relative) TRS S consists of the following rules: encArg(s(x_1)) -> s(encArg(x_1)) encArg(0) -> 0 encArg(cons_pred(x_1)) -> pred(encArg(x_1)) encArg(cons_minus(x_1, x_2)) -> minus(encArg(x_1), encArg(x_2)) encArg(cons_quot(x_1, x_2)) -> quot(encArg(x_1), encArg(x_2)) encode_pred(x_1) -> pred(encArg(x_1)) encode_s(x_1) -> s(encArg(x_1)) encode_minus(x_1, x_2) -> minus(encArg(x_1), encArg(x_2)) encode_0 -> 0 encode_quot(x_1, x_2) -> quot(encArg(x_1), encArg(x_2)) Rewrite Strategy: INNERMOST