/export/starexec/sandbox/solver/bin/starexec_run_rcdcRelativeAlsoLower /export/starexec/sandbox/benchmark/theBenchmark.xml /export/starexec/sandbox/output/output_files -------------------------------------------------------------------------------- WORST_CASE(?, O(n^1)) proof of /export/starexec/sandbox/benchmark/theBenchmark.xml # AProVE Commit ID: 794c25de1cacf0d048858bcd21c9a779e1221865 marcel 20200619 unpublished dirty The Derivational Complexity (innermost) of the given DCpxTrs could be proven to be BOUNDS(1, n^1). (0) DCpxTrs (1) DerivationalComplexityToRuntimeComplexityProof [BOTH BOUNDS(ID, ID), 0 ms] (2) CpxRelTRS (3) SInnermostTerminationProof [BOTH CONCRETE BOUNDS(ID, ID), 162 ms] (4) CpxRelTRS (5) NonCtorToCtorProof [UPPER BOUND(ID), 0 ms] (6) CpxRelTRS (7) RelTrsToWeightedTrsProof [BOTH BOUNDS(ID, ID), 0 ms] (8) CpxWeightedTrs (9) TypeInferenceProof [BOTH BOUNDS(ID, ID), 0 ms] (10) CpxTypedWeightedTrs (11) CompletionProof [UPPER BOUND(ID), 0 ms] (12) CpxTypedWeightedCompleteTrs (13) CpxTypedWeightedTrsToRntsProof [UPPER BOUND(ID), 1 ms] (14) CpxRNTS (15) CompleteCoflocoProof [FINISHED, 1026 ms] (16) BOUNDS(1, n^1) ---------------------------------------- (0) Obligation: The Derivational Complexity (innermost) of the given DCpxTrs could be proven to be BOUNDS(1, n^1). The TRS R consists of the following rules: a(f, 0) -> a(s, 0) a(d, 0) -> 0 a(d, a(s, x)) -> a(s, a(s, a(d, a(p, a(s, x))))) a(f, a(s, x)) -> a(d, a(f, a(p, a(s, x)))) a(p, a(s, x)) -> x S is empty. Rewrite Strategy: INNERMOST ---------------------------------------- (1) DerivationalComplexityToRuntimeComplexityProof (BOTH BOUNDS(ID, ID)) The following rules have been added to S to convert the given derivational complexity problem to a runtime complexity problem: encArg(f) -> f encArg(0) -> 0 encArg(s) -> s encArg(d) -> d encArg(p) -> p encArg(cons_a(x_1, x_2)) -> a(encArg(x_1), encArg(x_2)) encode_a(x_1, x_2) -> a(encArg(x_1), encArg(x_2)) encode_f -> f encode_0 -> 0 encode_s -> s encode_d -> d encode_p -> p ---------------------------------------- (2) Obligation: The Runtime Complexity (innermost) of the given CpxRelTRS could be proven to be BOUNDS(1, n^1). The TRS R consists of the following rules: a(f, 0) -> a(s, 0) a(d, 0) -> 0 a(d, a(s, x)) -> a(s, a(s, a(d, a(p, a(s, x))))) a(f, a(s, x)) -> a(d, a(f, a(p, a(s, x)))) a(p, a(s, x)) -> x The (relative) TRS S consists of the following rules: encArg(f) -> f encArg(0) -> 0 encArg(s) -> s encArg(d) -> d encArg(p) -> p encArg(cons_a(x_1, x_2)) -> a(encArg(x_1), encArg(x_2)) encode_a(x_1, x_2) -> a(encArg(x_1), encArg(x_2)) encode_f -> f encode_0 -> 0 encode_s -> s encode_d -> d encode_p -> p 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(1, n^1). The TRS R consists of the following rules: a(f, 0) -> a(s, 0) a(d, 0) -> 0 a(d, a(s, x)) -> a(s, a(s, a(d, a(p, a(s, x))))) a(f, a(s, x)) -> a(d, a(f, a(p, a(s, x)))) a(p, a(s, x)) -> x The (relative) TRS S consists of the following rules: encArg(f) -> f encArg(0) -> 0 encArg(s) -> s encArg(d) -> d encArg(p) -> p encArg(cons_a(x_1, x_2)) -> a(encArg(x_1), encArg(x_2)) encode_a(x_1, x_2) -> a(encArg(x_1), encArg(x_2)) encode_f -> f encode_0 -> 0 encode_s -> s encode_d -> d encode_p -> p Rewrite Strategy: INNERMOST ---------------------------------------- (5) NonCtorToCtorProof (UPPER BOUND(ID)) transformed non-ctor to ctor-system ---------------------------------------- (6) Obligation: The Runtime Complexity (innermost) of the given CpxRelTRS could be proven to be BOUNDS(1, n^1). The TRS R consists of the following rules: a(f, 0) -> a(s, 0) a(d, 0) -> 0 a(d, c_a(s, x)) -> a(s, a(s, a(d, a(p, a(s, x))))) a(p, c_a(s, x)) -> x a(f, c_a(s, x)) -> a(d, a(f, a(p, a(s, x)))) The (relative) TRS S consists of the following rules: encArg(f) -> f encArg(0) -> 0 encArg(s) -> s encArg(d) -> d encArg(p) -> p encArg(cons_a(x_1, x_2)) -> a(encArg(x_1), encArg(x_2)) encode_a(x_1, x_2) -> a(encArg(x_1), encArg(x_2)) encode_f -> f encode_0 -> 0 encode_s -> s encode_d -> d encode_p -> p a(x0, x1) -> c_a(x0, x1) Rewrite Strategy: INNERMOST ---------------------------------------- (7) RelTrsToWeightedTrsProof (BOTH BOUNDS(ID, ID)) Transformed relative TRS to weighted TRS ---------------------------------------- (8) Obligation: The Runtime Complexity (innermost) of the given CpxWeightedTrs could be proven to be BOUNDS(1, n^1). The TRS R consists of the following rules: a(f, 0) -> a(s, 0) [1] a(d, 0) -> 0 [1] a(d, c_a(s, x)) -> a(s, a(s, a(d, a(p, a(s, x))))) [1] a(p, c_a(s, x)) -> x [1] a(f, c_a(s, x)) -> a(d, a(f, a(p, a(s, x)))) [1] encArg(f) -> f [0] encArg(0) -> 0 [0] encArg(s) -> s [0] encArg(d) -> d [0] encArg(p) -> p [0] encArg(cons_a(x_1, x_2)) -> a(encArg(x_1), encArg(x_2)) [0] encode_a(x_1, x_2) -> a(encArg(x_1), encArg(x_2)) [0] encode_f -> f [0] encode_0 -> 0 [0] encode_s -> s [0] encode_d -> d [0] encode_p -> p [0] a(x0, x1) -> c_a(x0, x1) [0] Rewrite Strategy: INNERMOST ---------------------------------------- (9) TypeInferenceProof (BOTH BOUNDS(ID, ID)) Infered types. ---------------------------------------- (10) Obligation: Runtime Complexity Weighted TRS with Types. The TRS R consists of the following rules: a(f, 0) -> a(s, 0) [1] a(d, 0) -> 0 [1] a(d, c_a(s, x)) -> a(s, a(s, a(d, a(p, a(s, x))))) [1] a(p, c_a(s, x)) -> x [1] a(f, c_a(s, x)) -> a(d, a(f, a(p, a(s, x)))) [1] encArg(f) -> f [0] encArg(0) -> 0 [0] encArg(s) -> s [0] encArg(d) -> d [0] encArg(p) -> p [0] encArg(cons_a(x_1, x_2)) -> a(encArg(x_1), encArg(x_2)) [0] encode_a(x_1, x_2) -> a(encArg(x_1), encArg(x_2)) [0] encode_f -> f [0] encode_0 -> 0 [0] encode_s -> s [0] encode_d -> d [0] encode_p -> p [0] a(x0, x1) -> c_a(x0, x1) [0] The TRS has the following type information: a :: f:0:s:d:c_a:p:cons_a -> f:0:s:d:c_a:p:cons_a -> f:0:s:d:c_a:p:cons_a f :: f:0:s:d:c_a:p:cons_a 0 :: f:0:s:d:c_a:p:cons_a s :: f:0:s:d:c_a:p:cons_a d :: f:0:s:d:c_a:p:cons_a c_a :: f:0:s:d:c_a:p:cons_a -> f:0:s:d:c_a:p:cons_a -> f:0:s:d:c_a:p:cons_a p :: f:0:s:d:c_a:p:cons_a encArg :: f:0:s:d:c_a:p:cons_a -> f:0:s:d:c_a:p:cons_a cons_a :: f:0:s:d:c_a:p:cons_a -> f:0:s:d:c_a:p:cons_a -> f:0:s:d:c_a:p:cons_a encode_a :: f:0:s:d:c_a:p:cons_a -> f:0:s:d:c_a:p:cons_a -> f:0:s:d:c_a:p:cons_a encode_f :: f:0:s:d:c_a:p:cons_a encode_0 :: f:0:s:d:c_a:p:cons_a encode_s :: f:0:s:d:c_a:p:cons_a encode_d :: f:0:s:d:c_a:p:cons_a encode_p :: f:0:s:d:c_a:p:cons_a Rewrite Strategy: INNERMOST ---------------------------------------- (11) CompletionProof (UPPER BOUND(ID)) The TRS is a completely defined constructor system, as every type has a constant constructor and the following rules were added: encArg(v0) -> null_encArg [0] encode_a(v0, v1) -> null_encode_a [0] encode_f -> null_encode_f [0] encode_0 -> null_encode_0 [0] encode_s -> null_encode_s [0] encode_d -> null_encode_d [0] encode_p -> null_encode_p [0] a(v0, v1) -> null_a [0] And the following fresh constants: null_encArg, null_encode_a, null_encode_f, null_encode_0, null_encode_s, null_encode_d, null_encode_p, null_a ---------------------------------------- (12) Obligation: Runtime Complexity Weighted TRS where all functions are completely defined. The underlying TRS is: Runtime Complexity Weighted TRS with Types. The TRS R consists of the following rules: a(f, 0) -> a(s, 0) [1] a(d, 0) -> 0 [1] a(d, c_a(s, x)) -> a(s, a(s, a(d, a(p, a(s, x))))) [1] a(p, c_a(s, x)) -> x [1] a(f, c_a(s, x)) -> a(d, a(f, a(p, a(s, x)))) [1] encArg(f) -> f [0] encArg(0) -> 0 [0] encArg(s) -> s [0] encArg(d) -> d [0] encArg(p) -> p [0] encArg(cons_a(x_1, x_2)) -> a(encArg(x_1), encArg(x_2)) [0] encode_a(x_1, x_2) -> a(encArg(x_1), encArg(x_2)) [0] encode_f -> f [0] encode_0 -> 0 [0] encode_s -> s [0] encode_d -> d [0] encode_p -> p [0] a(x0, x1) -> c_a(x0, x1) [0] encArg(v0) -> null_encArg [0] encode_a(v0, v1) -> null_encode_a [0] encode_f -> null_encode_f [0] encode_0 -> null_encode_0 [0] encode_s -> null_encode_s [0] encode_d -> null_encode_d [0] encode_p -> null_encode_p [0] a(v0, v1) -> null_a [0] The TRS has the following type information: a :: f:0:s:d:c_a:p:cons_a:null_encArg:null_encode_a:null_encode_f:null_encode_0:null_encode_s:null_encode_d:null_encode_p:null_a -> f:0:s:d:c_a:p:cons_a:null_encArg:null_encode_a:null_encode_f:null_encode_0:null_encode_s:null_encode_d:null_encode_p:null_a -> f:0:s:d:c_a:p:cons_a:null_encArg:null_encode_a:null_encode_f:null_encode_0:null_encode_s:null_encode_d:null_encode_p:null_a f :: f:0:s:d:c_a:p:cons_a:null_encArg:null_encode_a:null_encode_f:null_encode_0:null_encode_s:null_encode_d:null_encode_p:null_a 0 :: f:0:s:d:c_a:p:cons_a:null_encArg:null_encode_a:null_encode_f:null_encode_0:null_encode_s:null_encode_d:null_encode_p:null_a s :: f:0:s:d:c_a:p:cons_a:null_encArg:null_encode_a:null_encode_f:null_encode_0:null_encode_s:null_encode_d:null_encode_p:null_a d :: f:0:s:d:c_a:p:cons_a:null_encArg:null_encode_a:null_encode_f:null_encode_0:null_encode_s:null_encode_d:null_encode_p:null_a c_a :: f:0:s:d:c_a:p:cons_a:null_encArg:null_encode_a:null_encode_f:null_encode_0:null_encode_s:null_encode_d:null_encode_p:null_a -> f:0:s:d:c_a:p:cons_a:null_encArg:null_encode_a:null_encode_f:null_encode_0:null_encode_s:null_encode_d:null_encode_p:null_a -> f:0:s:d:c_a:p:cons_a:null_encArg:null_encode_a:null_encode_f:null_encode_0:null_encode_s:null_encode_d:null_encode_p:null_a p :: f:0:s:d:c_a:p:cons_a:null_encArg:null_encode_a:null_encode_f:null_encode_0:null_encode_s:null_encode_d:null_encode_p:null_a encArg :: f:0:s:d:c_a:p:cons_a:null_encArg:null_encode_a:null_encode_f:null_encode_0:null_encode_s:null_encode_d:null_encode_p:null_a -> f:0:s:d:c_a:p:cons_a:null_encArg:null_encode_a:null_encode_f:null_encode_0:null_encode_s:null_encode_d:null_encode_p:null_a cons_a :: f:0:s:d:c_a:p:cons_a:null_encArg:null_encode_a:null_encode_f:null_encode_0:null_encode_s:null_encode_d:null_encode_p:null_a -> f:0:s:d:c_a:p:cons_a:null_encArg:null_encode_a:null_encode_f:null_encode_0:null_encode_s:null_encode_d:null_encode_p:null_a -> f:0:s:d:c_a:p:cons_a:null_encArg:null_encode_a:null_encode_f:null_encode_0:null_encode_s:null_encode_d:null_encode_p:null_a encode_a :: f:0:s:d:c_a:p:cons_a:null_encArg:null_encode_a:null_encode_f:null_encode_0:null_encode_s:null_encode_d:null_encode_p:null_a -> f:0:s:d:c_a:p:cons_a:null_encArg:null_encode_a:null_encode_f:null_encode_0:null_encode_s:null_encode_d:null_encode_p:null_a -> f:0:s:d:c_a:p:cons_a:null_encArg:null_encode_a:null_encode_f:null_encode_0:null_encode_s:null_encode_d:null_encode_p:null_a encode_f :: f:0:s:d:c_a:p:cons_a:null_encArg:null_encode_a:null_encode_f:null_encode_0:null_encode_s:null_encode_d:null_encode_p:null_a encode_0 :: f:0:s:d:c_a:p:cons_a:null_encArg:null_encode_a:null_encode_f:null_encode_0:null_encode_s:null_encode_d:null_encode_p:null_a encode_s :: f:0:s:d:c_a:p:cons_a:null_encArg:null_encode_a:null_encode_f:null_encode_0:null_encode_s:null_encode_d:null_encode_p:null_a encode_d :: f:0:s:d:c_a:p:cons_a:null_encArg:null_encode_a:null_encode_f:null_encode_0:null_encode_s:null_encode_d:null_encode_p:null_a encode_p :: f:0:s:d:c_a:p:cons_a:null_encArg:null_encode_a:null_encode_f:null_encode_0:null_encode_s:null_encode_d:null_encode_p:null_a null_encArg :: f:0:s:d:c_a:p:cons_a:null_encArg:null_encode_a:null_encode_f:null_encode_0:null_encode_s:null_encode_d:null_encode_p:null_a null_encode_a :: f:0:s:d:c_a:p:cons_a:null_encArg:null_encode_a:null_encode_f:null_encode_0:null_encode_s:null_encode_d:null_encode_p:null_a null_encode_f :: f:0:s:d:c_a:p:cons_a:null_encArg:null_encode_a:null_encode_f:null_encode_0:null_encode_s:null_encode_d:null_encode_p:null_a null_encode_0 :: f:0:s:d:c_a:p:cons_a:null_encArg:null_encode_a:null_encode_f:null_encode_0:null_encode_s:null_encode_d:null_encode_p:null_a null_encode_s :: f:0:s:d:c_a:p:cons_a:null_encArg:null_encode_a:null_encode_f:null_encode_0:null_encode_s:null_encode_d:null_encode_p:null_a null_encode_d :: f:0:s:d:c_a:p:cons_a:null_encArg:null_encode_a:null_encode_f:null_encode_0:null_encode_s:null_encode_d:null_encode_p:null_a null_encode_p :: f:0:s:d:c_a:p:cons_a:null_encArg:null_encode_a:null_encode_f:null_encode_0:null_encode_s:null_encode_d:null_encode_p:null_a null_a :: f:0:s:d:c_a:p:cons_a:null_encArg:null_encode_a:null_encode_f:null_encode_0:null_encode_s:null_encode_d:null_encode_p:null_a Rewrite Strategy: INNERMOST ---------------------------------------- (13) CpxTypedWeightedTrsToRntsProof (UPPER BOUND(ID)) Transformed the TRS into an over-approximating RNTS by (improved) Size Abstraction. The constant constructors are abstracted as follows: f => 2 0 => 0 s => 4 d => 1 p => 3 null_encArg => 0 null_encode_a => 0 null_encode_f => 0 null_encode_0 => 0 null_encode_s => 0 null_encode_d => 0 null_encode_p => 0 null_a => 0 ---------------------------------------- (14) Obligation: Complexity RNTS consisting of the following rules: a(z, z') -{ 1 }-> x :|: z = 3, x >= 0, z' = 1 + 4 + x a(z, z') -{ 1 }-> a(4, a(4, a(1, a(3, a(4, x))))) :|: z = 1, x >= 0, z' = 1 + 4 + x a(z, z') -{ 1 }-> a(4, 0) :|: z = 2, z' = 0 a(z, z') -{ 1 }-> a(1, a(2, a(3, a(4, x)))) :|: z = 2, x >= 0, z' = 1 + 4 + x a(z, z') -{ 1 }-> 0 :|: z = 1, z' = 0 a(z, z') -{ 0 }-> 0 :|: v0 >= 0, v1 >= 0, z = v0, z' = v1 a(z, z') -{ 0 }-> 1 + x0 + x1 :|: z = x0, x0 >= 0, x1 >= 0, z' = x1 encArg(z) -{ 0 }-> a(encArg(x_1), encArg(x_2)) :|: x_1 >= 0, z = 1 + x_1 + x_2, x_2 >= 0 encArg(z) -{ 0 }-> 4 :|: z = 4 encArg(z) -{ 0 }-> 3 :|: z = 3 encArg(z) -{ 0 }-> 2 :|: z = 2 encArg(z) -{ 0 }-> 1 :|: z = 1 encArg(z) -{ 0 }-> 0 :|: z = 0 encArg(z) -{ 0 }-> 0 :|: v0 >= 0, z = v0 encode_0 -{ 0 }-> 0 :|: encode_a(z, z') -{ 0 }-> a(encArg(x_1), encArg(x_2)) :|: x_1 >= 0, x_2 >= 0, z = x_1, z' = x_2 encode_a(z, z') -{ 0 }-> 0 :|: v0 >= 0, v1 >= 0, z = v0, z' = v1 encode_d -{ 0 }-> 1 :|: encode_d -{ 0 }-> 0 :|: encode_f -{ 0 }-> 2 :|: encode_f -{ 0 }-> 0 :|: encode_p -{ 0 }-> 3 :|: encode_p -{ 0 }-> 0 :|: encode_s -{ 0 }-> 4 :|: encode_s -{ 0 }-> 0 :|: Only complete derivations are relevant for the runtime complexity. ---------------------------------------- (15) CompleteCoflocoProof (FINISHED) Transformed the RNTS (where only complete derivations are relevant) into cost relations for CoFloCo: eq(start(V1, V),0,[a(V1, V, Out)],[V1 >= 0,V >= 0]). eq(start(V1, V),0,[encArg(V1, Out)],[V1 >= 0]). eq(start(V1, V),0,[fun(V1, V, Out)],[V1 >= 0,V >= 0]). eq(start(V1, V),0,[fun1(Out)],[]). eq(start(V1, V),0,[fun2(Out)],[]). eq(start(V1, V),0,[fun3(Out)],[]). eq(start(V1, V),0,[fun4(Out)],[]). eq(start(V1, V),0,[fun5(Out)],[]). eq(a(V1, V, Out),1,[a(4, 0, Ret)],[Out = Ret,V1 = 2,V = 0]). eq(a(V1, V, Out),1,[],[Out = 0,V1 = 1,V = 0]). eq(a(V1, V, Out),1,[a(4, V2, Ret1111),a(3, Ret1111, Ret111),a(1, Ret111, Ret11),a(4, Ret11, Ret1),a(4, Ret1, Ret2)],[Out = Ret2,V1 = 1,V2 >= 0,V = 5 + V2]). eq(a(V1, V, Out),1,[],[Out = V3,V1 = 3,V3 >= 0,V = 5 + V3]). eq(a(V1, V, Out),1,[a(4, V4, Ret1112),a(3, Ret1112, Ret112),a(2, Ret112, Ret12),a(1, Ret12, Ret3)],[Out = Ret3,V1 = 2,V4 >= 0,V = 5 + V4]). eq(encArg(V1, Out),0,[],[Out = 2,V1 = 2]). eq(encArg(V1, Out),0,[],[Out = 0,V1 = 0]). eq(encArg(V1, Out),0,[],[Out = 4,V1 = 4]). eq(encArg(V1, Out),0,[],[Out = 1,V1 = 1]). eq(encArg(V1, Out),0,[],[Out = 3,V1 = 3]). eq(encArg(V1, Out),0,[encArg(V6, Ret0),encArg(V5, Ret13),a(Ret0, Ret13, Ret4)],[Out = Ret4,V6 >= 0,V1 = 1 + V5 + V6,V5 >= 0]). eq(fun(V1, V, Out),0,[encArg(V7, Ret01),encArg(V8, Ret14),a(Ret01, Ret14, Ret5)],[Out = Ret5,V7 >= 0,V8 >= 0,V1 = V7,V = V8]). eq(fun1(Out),0,[],[Out = 2]). eq(fun2(Out),0,[],[Out = 0]). eq(fun3(Out),0,[],[Out = 4]). eq(fun4(Out),0,[],[Out = 1]). eq(fun5(Out),0,[],[Out = 3]). eq(a(V1, V, Out),0,[],[Out = 1 + V10 + V9,V1 = V10,V10 >= 0,V9 >= 0,V = V9]). eq(encArg(V1, Out),0,[],[Out = 0,V11 >= 0,V1 = V11]). eq(fun(V1, V, Out),0,[],[Out = 0,V13 >= 0,V12 >= 0,V1 = V13,V = V12]). eq(fun1(Out),0,[],[Out = 0]). eq(fun3(Out),0,[],[Out = 0]). eq(fun4(Out),0,[],[Out = 0]). eq(fun5(Out),0,[],[Out = 0]). eq(a(V1, V, Out),0,[],[Out = 0,V15 >= 0,V14 >= 0,V1 = V15,V = V14]). input_output_vars(a(V1,V,Out),[V1,V],[Out]). input_output_vars(encArg(V1,Out),[V1],[Out]). input_output_vars(fun(V1,V,Out),[V1,V],[Out]). input_output_vars(fun1(Out),[],[Out]). input_output_vars(fun2(Out),[],[Out]). input_output_vars(fun3(Out),[],[Out]). input_output_vars(fun4(Out),[],[Out]). input_output_vars(fun5(Out),[],[Out]). CoFloCo proof output: Preprocessing Cost Relations ===================================== #### Computed strongly connected components 0. recursive [multiple] : [a/3] 1. recursive [non_tail,multiple] : [encArg/2] 2. non_recursive : [fun/3] 3. non_recursive : [fun1/1] 4. non_recursive : [fun2/1] 5. non_recursive : [fun3/1] 6. non_recursive : [fun4/1] 7. non_recursive : [fun5/1] 8. non_recursive : [start/2] #### Obtained direct recursion through partial evaluation 0. SCC is partially evaluated into a/3 1. SCC is partially evaluated into encArg/2 2. SCC is partially evaluated into fun/3 3. SCC is partially evaluated into fun1/1 4. SCC is completely evaluated into other SCCs 5. SCC is partially evaluated into fun3/1 6. SCC is partially evaluated into fun4/1 7. SCC is partially evaluated into fun5/1 8. SCC is partially evaluated into start/2 Control-Flow Refinement of Cost Relations ===================================== ### Specialization of cost equations a/3 * CE 14 is refined into CE [32] * CE 12 is refined into CE [33] * CE 10 is refined into CE [34] * CE 15 is refined into CE [35] * CE 13 is refined into CE [36] * CE 11 is refined into CE [37] * CE 9 is refined into CE [38] ### Cost equations --> "Loop" of a/3 * CEs [38] --> Loop 23 * CEs [37] --> Loop 24 * CEs [36] --> Loop 25 * CEs [32] --> Loop 26 * CEs [33] --> Loop 27 * CEs [34,35] --> Loop 28 ### Ranking functions of CR a(V1,V,Out) #### Partial ranking functions of CR a(V1,V,Out) * Partial RF of phase [24]: - RF of loop [24:1]: V/5-4/5 depends on loops [24:2,24:3,24:4,24:5] - RF of loop [24:1,24:4,24:5]: -V1/3+2/3 - RF of loop [24:2]: -V1/2+1 * Partial RF of phase [25]: - RF of loop [25:1]: V/5-4/5 depends on loops [25:2,25:3,25:4] -V1/2+3/2 depends on loops [25:4] - RF of loop [25:2]: -V1+3 depends on loops [25:4] - RF of loop [25:4]: V1-1 depends on loops [25:1,25:2] ### Specialization of cost equations encArg/2 * CE 17 is refined into CE [39] * CE 18 is refined into CE [40] * CE 20 is refined into CE [41] * CE 16 is refined into CE [42] * CE 19 is refined into CE [43] * CE 21 is refined into CE [44,45,46,47,48,49] ### Cost equations --> "Loop" of encArg/2 * CEs [49] --> Loop 29 * CEs [48] --> Loop 30 * CEs [47] --> Loop 31 * CEs [46] --> Loop 32 * CEs [45] --> Loop 33 * CEs [44] --> Loop 34 * CEs [39] --> Loop 35 * CEs [40] --> Loop 36 * CEs [41] --> Loop 37 * CEs [42] --> Loop 38 * CEs [43] --> Loop 39 ### Ranking functions of CR encArg(V1,Out) * RF of phase [29,30,31,32,33,34]: [V1] #### Partial ranking functions of CR encArg(V1,Out) * Partial RF of phase [29,30,31,32,33,34]: - RF of loop [29:1,29:2,30:1,30:2,31:1,31:2,32:1,32:2,33:1,33:2,34:1,34:2]: V1 ### Specialization of cost equations fun/3 * CE 22 is refined into CE [50,51,52,53,54,55,56,57,58,59,60,61,62,63,64,65,66,67,68,69,70,71,72,73,74,75,76,77,78,79,80,81,82,83,84,85,86,87,88,89,90,91,92,93,94,95,96,97,98,99,100,101,102,103,104,105,106,107,108] * CE 23 is refined into CE [109] ### Cost equations --> "Loop" of fun/3 * CEs [108] --> Loop 40 * CEs [106] --> Loop 41 * CEs [104] --> Loop 42 * CEs [57] --> Loop 43 * CEs [102] --> Loop 44 * CEs [56,101] --> Loop 45 * CEs [98] --> Loop 46 * CEs [96] --> Loop 47 * CEs [95] --> Loop 48 * CEs [94] --> Loop 49 * CEs [93] --> Loop 50 * CEs [90,92] --> Loop 51 * CEs [89,91,97] --> Loop 52 * CEs [88] --> Loop 53 * CEs [86] --> Loop 54 * CEs [85] --> Loop 55 * CEs [59,84] --> Loop 56 * CEs [83] --> Loop 57 * CEs [79,80,82] --> Loop 58 * CEs [78,81,87] --> Loop 59 * CEs [77] --> Loop 60 * CEs [52,61,74] --> Loop 61 * CEs [60,73,105] --> Loop 62 * CEs [67,72,100] --> Loop 63 * CEs [58,71,103] --> Loop 64 * CEs [51,53,63,64,66,70,76] --> Loop 65 * CEs [50,62,65,69,75,99,107,109] --> Loop 66 * CEs [54,55,68] --> Loop 67 ### Ranking functions of CR fun(V1,V,Out) #### Partial ranking functions of CR fun(V1,V,Out) ### Specialization of cost equations fun1/1 * CE 24 is refined into CE [110] * CE 25 is refined into CE [111] ### Cost equations --> "Loop" of fun1/1 * CEs [110] --> Loop 68 * CEs [111] --> Loop 69 ### Ranking functions of CR fun1(Out) #### Partial ranking functions of CR fun1(Out) ### Specialization of cost equations fun3/1 * CE 26 is refined into CE [112] * CE 27 is refined into CE [113] ### Cost equations --> "Loop" of fun3/1 * CEs [112] --> Loop 70 * CEs [113] --> Loop 71 ### Ranking functions of CR fun3(Out) #### Partial ranking functions of CR fun3(Out) ### Specialization of cost equations fun4/1 * CE 28 is refined into CE [114] * CE 29 is refined into CE [115] ### Cost equations --> "Loop" of fun4/1 * CEs [114] --> Loop 72 * CEs [115] --> Loop 73 ### Ranking functions of CR fun4(Out) #### Partial ranking functions of CR fun4(Out) ### Specialization of cost equations fun5/1 * CE 30 is refined into CE [116] * CE 31 is refined into CE [117] ### Cost equations --> "Loop" of fun5/1 * CEs [116] --> Loop 74 * CEs [117] --> Loop 75 ### Ranking functions of CR fun5(Out) #### Partial ranking functions of CR fun5(Out) ### Specialization of cost equations start/2 * CE 1 is refined into CE [118,119,120,121,122,123] * CE 2 is refined into CE [124,125,126,127,128] * CE 3 is refined into CE [129,130,131,132,133,134,135,136,137,138,139,140,141,142,143,144,145,146,147] * CE 4 is refined into CE [148,149] * CE 5 is refined into CE [150] * CE 6 is refined into CE [151,152] * CE 7 is refined into CE [153,154] * CE 8 is refined into CE [155,156] ### Cost equations --> "Loop" of start/2 * CEs [118,119,120,121,124,125,126,127,128,129,130,131,132,133,134,135,136,137,138,139,140,141,142,143,144,145,146,148,149,150,151,152,153,154,155,156] --> Loop 76 * CEs [123] --> Loop 77 * CEs [122,147] --> Loop 78 ### Ranking functions of CR start(V1,V) #### Partial ranking functions of CR start(V1,V) Computing Bounds ===================================== #### Cost of chains of a(V1,V,Out): * Chain [multiple([25],[[],[multiple([24],[[],[28],[27],[26]])],[28],[27],[26],[23,28],[23,26]])]...: 4*it(25)+2*it([27])+1*s(1)+2*s(2)+0 Such that:aux(2) =< 1 s(1) =< -3/5*V1+8/5 aux(3) =< -2*V1+5 it(25) =< aux(3) it([27]) =< it(25)*3+aux(2) s(3) =< it(25)*3+aux(2) s(2) =< s(1)*4+s(3) with precondition: [V1=2,V>=5] * Chain [multiple([24],[[],[28],[27],[26]])]...: 1*it(24)+2*it([27])+0 Such that:aux(1) =< 1 it(24) =< -5/11*V1+16/11 it([27]) =< it(24)*4+aux(1) with precondition: [V1=1,V>=5] * Chain [28]: 1 with precondition: [Out=0,V1>=0,V>=0] * Chain [27]: 1 with precondition: [V1=3,V=Out+5,V>=5] * Chain [26]: 0 with precondition: [V+V1+1=Out,V1>=0,V>=0] * Chain [23,28]: 2 with precondition: [V1=2,V=0,Out=0] * Chain [23,26]: 1 with precondition: [V1=2,V=0,Out=5] #### Cost of chains of encArg(V1,Out): * Chain [39]: 0 with precondition: [V1=1,Out=1] * Chain [38]: 0 with precondition: [V1=2,Out=2] * Chain [37]: 0 with precondition: [V1=3,Out=3] * Chain [36]: 0 with precondition: [V1=4,Out=4] * Chain [35]: 0 with precondition: [Out=0,V1>=0] * Chain [multiple([29,30,31,32,33,34],[[39],[38],[37],[36],[35]])]: 9*it(32)+1*s(23)+2*s(25)+2*s(26)+2*s(30)+0 Such that:aux(9) =< V1 it(32) =< aux(9) s(23) =< aux(9)*(2/5) s(30) =< it(32)*4+aux(9) s(25) =< it(32)*3+aux(9) s(27) =< it(32)*3+aux(9) s(26) =< s(23)*4+s(27) with precondition: [V1>=1] #### Cost of chains of fun(V1,V,Out): * Chain [67]...: 18*s(40)+2*s(41)+4*s(42)+4*s(43)+4*s(45)+27*s(47)+3*s(48)+6*s(49)+6*s(50)+6*s(52)+9*s(54)+2*s(55)+2*s(71)+4*s(74)+4*s(76)+0 Such that:aux(14) =< 1 aux(15) =< 2/5 aux(16) =< V1 aux(17) =< V s(71) =< aux(15) s(54) =< aux(14) s(74) =< s(54)*3+aux(14) s(75) =< s(54)*3+aux(14) s(76) =< s(71)*4+s(75) s(47) =< aux(17) s(48) =< aux(17)*(2/5) s(49) =< s(47)*4+aux(17) s(50) =< s(47)*3+aux(17) s(51) =< s(47)*3+aux(17) s(52) =< s(48)*4+s(51) s(40) =< aux(16) s(41) =< aux(16)*(2/5) s(42) =< s(40)*4+aux(16) s(43) =< s(40)*3+aux(16) s(44) =< s(40)*3+aux(16) s(45) =< s(41)*4+s(44) s(55) =< s(54)*4+aux(14) with precondition: [V1>=1,V>=1] * Chain [66]: 18*s(92)+2*s(93)+4*s(94)+4*s(95)+4*s(97)+27*s(99)+3*s(100)+6*s(101)+6*s(102)+6*s(104)+2 Such that:aux(18) =< V1 aux(19) =< V s(99) =< aux(19) s(100) =< aux(19)*(2/5) s(101) =< s(99)*4+aux(19) s(102) =< s(99)*3+aux(19) s(103) =< s(99)*3+aux(19) s(104) =< s(100)*4+s(103) s(92) =< aux(18) s(93) =< aux(18)*(2/5) s(94) =< s(92)*4+aux(18) s(95) =< s(92)*3+aux(18) s(96) =< s(92)*3+aux(18) s(97) =< s(93)*4+s(96) with precondition: [Out=0,V1>=0,V>=0] * Chain [65]: 36*s(127)+4*s(128)+8*s(129)+8*s(130)+8*s(132)+27*s(134)+3*s(135)+6*s(136)+6*s(137)+6*s(139)+1 Such that:aux(20) =< V1 aux(21) =< V s(134) =< aux(21) s(135) =< aux(21)*(2/5) s(136) =< s(134)*4+aux(21) s(137) =< s(134)*3+aux(21) s(138) =< s(134)*3+aux(21) s(139) =< s(135)*4+s(138) s(127) =< aux(20) s(128) =< aux(20)*(2/5) s(129) =< s(127)*4+aux(20) s(130) =< s(127)*3+aux(20) s(131) =< s(127)*3+aux(20) s(132) =< s(128)*4+s(131) with precondition: [V1>=1,V>=0,Out>=1] * Chain [64]: 9*s(176)+1*s(177)+2*s(178)+2*s(179)+2*s(181)+2 Such that:s(175) =< V1 s(176) =< s(175) s(177) =< s(175)*(2/5) s(178) =< s(176)*4+s(175) s(179) =< s(176)*3+s(175) s(180) =< s(176)*3+s(175) s(181) =< s(177)*4+s(180) with precondition: [V=3,Out=0,V1>=0] * Chain [63]: 18*s(183)+2*s(184)+4*s(185)+4*s(186)+4*s(188)+0 Such that:aux(22) =< V s(183) =< aux(22) s(184) =< aux(22)*(2/5) s(185) =< s(183)*4+aux(22) s(186) =< s(183)*3+aux(22) s(187) =< s(183)*3+aux(22) s(188) =< s(184)*4+s(187) with precondition: [V1>=0,V>=1,Out>=1] * Chain [62]: 9*s(197)+1*s(198)+2*s(199)+2*s(200)+2*s(202)+2 Such that:s(196) =< V1 s(197) =< s(196) s(198) =< s(196)*(2/5) s(199) =< s(197)*4+s(196) s(200) =< s(197)*3+s(196) s(201) =< s(197)*3+s(196) s(202) =< s(198)*4+s(201) with precondition: [V=4,Out=0,V1>=0] * Chain [61]: 18*s(204)+2*s(205)+4*s(206)+4*s(207)+4*s(209)+9*s(211)+1*s(212)+2*s(213)+2*s(214)+2*s(216)+1 Such that:s(210) =< V aux(23) =< V1 s(211) =< s(210) s(212) =< s(210)*(2/5) s(213) =< s(211)*4+s(210) s(214) =< s(211)*3+s(210) s(215) =< s(211)*3+s(210) s(216) =< s(212)*4+s(215) s(204) =< aux(23) s(205) =< aux(23)*(2/5) s(206) =< s(204)*4+aux(23) s(207) =< s(204)*3+aux(23) s(208) =< s(204)*3+aux(23) s(209) =< s(205)*4+s(208) with precondition: [V1>=1,V>=1,Out>=0] * Chain [60]: 0 with precondition: [V1=2,Out=3,V>=0] * Chain [59]: 9*s(225)+1*s(226)+2*s(227)+2*s(228)+2*s(230)+2 Such that:s(224) =< V s(225) =< s(224) s(226) =< s(224)*(2/5) s(227) =< s(225)*4+s(224) s(228) =< s(225)*3+s(224) s(229) =< s(225)*3+s(224) s(230) =< s(226)*4+s(229) with precondition: [V1=3,Out=0,V>=0] * Chain [58]: 18*s(232)+2*s(233)+4*s(234)+4*s(235)+4*s(237)+1 Such that:aux(24) =< V s(232) =< aux(24) s(233) =< aux(24)*(2/5) s(234) =< s(232)*4+aux(24) s(235) =< s(232)*3+aux(24) s(236) =< s(232)*3+aux(24) s(237) =< s(233)*4+s(236) with precondition: [V1=3,V>=1,Out>=0] * Chain [57]: 2 with precondition: [V1=3,V=3,Out=0] * Chain [56]: 9*s(246)+1*s(247)+2*s(248)+2*s(249)+2*s(251)+0 Such that:s(245) =< V1 s(246) =< s(245) s(247) =< s(245)*(2/5) s(248) =< s(246)*4+s(245) s(249) =< s(246)*3+s(245) s(250) =< s(246)*3+s(245) s(251) =< s(247)*4+s(250) with precondition: [V=3,V1>=1,Out>=4] * Chain [55]: 2 with precondition: [V1=3,V=4,Out=0] * Chain [54]: 0 with precondition: [V1=3,V=4,Out=8] * Chain [53]: 0 with precondition: [V1=3,Out=4,V>=0] * Chain [52]: 9*s(253)+1*s(254)+2*s(255)+2*s(256)+2*s(258)+2 Such that:s(252) =< V s(253) =< s(252) s(254) =< s(252)*(2/5) s(255) =< s(253)*4+s(252) s(256) =< s(253)*3+s(252) s(257) =< s(253)*3+s(252) s(258) =< s(254)*4+s(257) with precondition: [V1=4,Out=0,V>=0] * Chain [51]: 9*s(260)+1*s(261)+2*s(262)+2*s(263)+2*s(265)+0 Such that:s(259) =< V s(260) =< s(259) s(261) =< s(259)*(2/5) s(262) =< s(260)*4+s(259) s(263) =< s(260)*3+s(259) s(264) =< s(260)*3+s(259) s(265) =< s(261)*4+s(264) with precondition: [V1=4,V>=1,Out>=5] * Chain [50]: 2 with precondition: [V1=4,V=3,Out=0] * Chain [49]: 0 with precondition: [V1=4,V=3,Out=8] * Chain [48]: 2 with precondition: [V1=4,V=4,Out=0] * Chain [47]: 0 with precondition: [V1=4,V=4,Out=9] * Chain [46]: 0 with precondition: [V1=4,Out=5,V>=0] * Chain [45]: 9*s(267)+1*s(268)+2*s(269)+2*s(270)+2*s(272)+2 Such that:s(266) =< V1 s(267) =< s(266) s(268) =< s(266)*(2/5) s(269) =< s(267)*4+s(266) s(270) =< s(267)*3+s(266) s(271) =< s(267)*3+s(266) s(272) =< s(268)*4+s(271) with precondition: [V=2,Out=0,V1>=0] * Chain [44]: 0 with precondition: [V=2,Out=3,V1>=0] * Chain [43]: 9*s(274)+1*s(275)+2*s(276)+2*s(277)+2*s(279)+0 Such that:s(273) =< V1 s(274) =< s(273) s(275) =< s(273)*(2/5) s(276) =< s(274)*4+s(273) s(277) =< s(274)*3+s(273) s(278) =< s(274)*3+s(273) s(279) =< s(275)*4+s(278) with precondition: [V=2,V1>=1,Out>=3] * Chain [42]: 0 with precondition: [V=3,Out=4,V1>=0] * Chain [41]: 0 with precondition: [V=4,Out=5,V1>=0] * Chain [40]: 0 with precondition: [Out=1,V1>=0,V>=0] #### Cost of chains of fun1(Out): * Chain [69]: 0 with precondition: [Out=0] * Chain [68]: 0 with precondition: [Out=2] #### Cost of chains of fun3(Out): * Chain [71]: 0 with precondition: [Out=0] * Chain [70]: 0 with precondition: [Out=4] #### Cost of chains of fun4(Out): * Chain [73]: 0 with precondition: [Out=0] * Chain [72]: 0 with precondition: [Out=1] #### Cost of chains of fun5(Out): * Chain [75]: 0 with precondition: [Out=0] * Chain [74]: 0 with precondition: [Out=3] #### Cost of chains of start(V1,V): * Chain [78]...: 10*s(365)+4*s(366)+2*s(371)+4*s(373)+4*s(375)+27*s(376)+3*s(377)+6*s(378)+6*s(379)+6*s(381)+18*s(382)+2*s(383)+4*s(384)+4*s(385)+4*s(387)+0 Such that:s(368) =< 2/5 s(369) =< V1 s(370) =< V aux(28) =< 1 s(365) =< aux(28) s(366) =< s(365)*4+aux(28) s(371) =< s(368) s(373) =< s(365)*3+aux(28) s(374) =< s(365)*3+aux(28) s(375) =< s(371)*4+s(374) s(376) =< s(370) s(377) =< s(370)*(2/5) s(378) =< s(376)*4+s(370) s(379) =< s(376)*3+s(370) s(380) =< s(376)*3+s(370) s(381) =< s(377)*4+s(380) s(382) =< s(369) s(383) =< s(369)*(2/5) s(384) =< s(382)*4+s(369) s(385) =< s(382)*3+s(369) s(386) =< s(382)*3+s(369) s(387) =< s(383)*4+s(386) with precondition: [V1>=1,V>=1] * Chain [77]...: 1*s(390)+4*s(392)+2*s(393)+2*s(395)+0 Such that:s(390) =< 2/5 aux(29) =< 1 s(392) =< aux(29) s(393) =< s(392)*3+aux(29) s(394) =< s(392)*3+aux(29) s(395) =< s(390)*4+s(394) with precondition: [V1=2,V>=5] * Chain [76]: 126*s(397)+14*s(398)+28*s(399)+28*s(400)+28*s(402)+126*s(405)+14*s(406)+28*s(407)+28*s(408)+28*s(410)+2 Such that:aux(30) =< V1 aux(31) =< V s(397) =< aux(30) s(398) =< aux(30)*(2/5) s(399) =< s(397)*4+aux(30) s(400) =< s(397)*3+aux(30) s(401) =< s(397)*3+aux(30) s(402) =< s(398)*4+s(401) s(405) =< aux(31) s(406) =< aux(31)*(2/5) s(407) =< s(405)*4+aux(31) s(408) =< s(405)*3+aux(31) s(409) =< s(405)*3+aux(31) s(410) =< s(406)*4+s(409) with precondition: [] Closed-form bounds of start(V1,V): ------------------------------------- * Chain [78]... with precondition: [V1>=1,V>=1] - Upper bound: 386/5*V1+579/5*V+346/5 - Complexity: n * Chain [77]... with precondition: [V1=2,V>=5] - Upper bound: 118/5 - Complexity: constant * Chain [76] with precondition: [] - Upper bound: 2702/5*nat(V1)+2+2702/5*nat(V) - Complexity: n ### Maximum cost of start(V1,V): max([108/5,579/5*nat(V)+386/5*nat(V1)+max([336/5,2316/5*nat(V1)+2123/5*nat(V)])])+2 Asymptotic class: n * Total analysis performed in 898 ms. ---------------------------------------- (16) BOUNDS(1, n^1)