1109.65/291.54 WORST_CASE(Omega(n^1), O(n^2)) 1109.65/291.56 proof of /export/starexec/sandbox/benchmark/theBenchmark.xml 1109.65/291.56 # AProVE Commit ID: 48fb2092695e11cc9f56e44b17a92a5f88ffb256 marcel 20180622 unpublished dirty 1109.65/291.56 1109.65/291.56 1109.65/291.56 The Runtime Complexity (innermost) of the given CpxTRS could be proven to be BOUNDS(n^1, n^2). 1109.65/291.56 1109.65/291.56 (0) CpxTRS 1109.65/291.56 (1) RelTrsToWeightedTrsProof [BOTH BOUNDS(ID, ID), 0 ms] 1109.65/291.56 (2) CpxWeightedTrs 1109.65/291.56 (3) TypeInferenceProof [BOTH BOUNDS(ID, ID), 0 ms] 1109.65/291.56 (4) CpxTypedWeightedTrs 1109.65/291.56 (5) CompletionProof [UPPER BOUND(ID), 0 ms] 1109.65/291.56 (6) CpxTypedWeightedCompleteTrs 1109.65/291.56 (7) CpxTypedWeightedTrsToRntsProof [UPPER BOUND(ID), 0 ms] 1109.65/291.56 (8) CpxRNTS 1109.65/291.56 (9) CompleteCoflocoProof [FINISHED, 1734 ms] 1109.65/291.56 (10) BOUNDS(1, n^2) 1109.65/291.56 (11) RenamingProof [BOTH BOUNDS(ID, ID), 0 ms] 1109.65/291.56 (12) CpxTRS 1109.65/291.56 (13) TypeInferenceProof [BOTH BOUNDS(ID, ID), 0 ms] 1109.65/291.56 (14) typed CpxTrs 1109.65/291.56 (15) OrderProof [LOWER BOUND(ID), 0 ms] 1109.65/291.56 (16) typed CpxTrs 1109.65/291.56 (17) RewriteLemmaProof [LOWER BOUND(ID), 287 ms] 1109.65/291.56 (18) BEST 1109.65/291.56 (19) proven lower bound 1109.65/291.56 (20) LowerBoundPropagationProof [FINISHED, 0 ms] 1109.65/291.56 (21) BOUNDS(n^1, INF) 1109.65/291.56 (22) typed CpxTrs 1109.65/291.56 (23) RewriteLemmaProof [LOWER BOUND(ID), 90 ms] 1109.65/291.56 (24) typed CpxTrs 1109.65/291.56 1109.65/291.56 1109.65/291.56 ---------------------------------------- 1109.65/291.56 1109.65/291.56 (0) 1109.65/291.56 Obligation: 1109.65/291.56 The Runtime Complexity (innermost) of the given CpxTRS could be proven to be BOUNDS(n^1, n^2). 1109.65/291.56 1109.65/291.56 1109.65/291.56 The TRS R consists of the following rules: 1109.65/291.56 1109.65/291.56 cond1(true, x, y, z) -> cond2(gr(y, z), x, y, z) 1109.65/291.56 cond2(true, x, y, z) -> cond2(gr(y, z), p(x), p(y), z) 1109.65/291.56 cond2(false, x, y, z) -> cond1(and(eq(x, y), gr(x, z)), x, y, z) 1109.65/291.56 gr(0, x) -> false 1109.65/291.56 gr(s(x), 0) -> true 1109.65/291.56 gr(s(x), s(y)) -> gr(x, y) 1109.65/291.56 p(0) -> 0 1109.65/291.56 p(s(x)) -> x 1109.65/291.56 eq(0, 0) -> true 1109.65/291.56 eq(s(x), 0) -> false 1109.65/291.56 eq(0, s(x)) -> false 1109.65/291.56 eq(s(x), s(y)) -> eq(x, y) 1109.65/291.56 and(true, true) -> true 1109.65/291.56 and(false, x) -> false 1109.65/291.56 and(x, false) -> false 1109.65/291.56 1109.65/291.56 S is empty. 1109.65/291.56 Rewrite Strategy: INNERMOST 1109.65/291.56 ---------------------------------------- 1109.65/291.56 1109.65/291.56 (1) RelTrsToWeightedTrsProof (BOTH BOUNDS(ID, ID)) 1109.65/291.56 Transformed relative TRS to weighted TRS 1109.65/291.56 ---------------------------------------- 1109.65/291.56 1109.65/291.56 (2) 1109.65/291.56 Obligation: 1109.65/291.56 The Runtime Complexity (innermost) of the given CpxWeightedTrs could be proven to be BOUNDS(1, n^2). 1109.65/291.56 1109.65/291.56 1109.65/291.56 The TRS R consists of the following rules: 1109.65/291.56 1109.65/291.56 cond1(true, x, y, z) -> cond2(gr(y, z), x, y, z) [1] 1109.65/291.56 cond2(true, x, y, z) -> cond2(gr(y, z), p(x), p(y), z) [1] 1109.65/291.56 cond2(false, x, y, z) -> cond1(and(eq(x, y), gr(x, z)), x, y, z) [1] 1109.65/291.56 gr(0, x) -> false [1] 1109.65/291.56 gr(s(x), 0) -> true [1] 1109.65/291.56 gr(s(x), s(y)) -> gr(x, y) [1] 1109.65/291.56 p(0) -> 0 [1] 1109.65/291.56 p(s(x)) -> x [1] 1109.65/291.56 eq(0, 0) -> true [1] 1109.65/291.56 eq(s(x), 0) -> false [1] 1109.65/291.56 eq(0, s(x)) -> false [1] 1109.65/291.56 eq(s(x), s(y)) -> eq(x, y) [1] 1109.65/291.56 and(true, true) -> true [1] 1109.65/291.56 and(false, x) -> false [1] 1109.65/291.56 and(x, false) -> false [1] 1109.65/291.56 1109.65/291.56 Rewrite Strategy: INNERMOST 1109.65/291.56 ---------------------------------------- 1109.65/291.56 1109.65/291.56 (3) TypeInferenceProof (BOTH BOUNDS(ID, ID)) 1109.65/291.56 Infered types. 1109.65/291.56 ---------------------------------------- 1109.65/291.56 1109.65/291.56 (4) 1109.65/291.56 Obligation: 1109.65/291.56 Runtime Complexity Weighted TRS with Types. 1109.65/291.56 The TRS R consists of the following rules: 1109.65/291.56 1109.65/291.56 cond1(true, x, y, z) -> cond2(gr(y, z), x, y, z) [1] 1109.65/291.56 cond2(true, x, y, z) -> cond2(gr(y, z), p(x), p(y), z) [1] 1109.65/291.56 cond2(false, x, y, z) -> cond1(and(eq(x, y), gr(x, z)), x, y, z) [1] 1109.65/291.56 gr(0, x) -> false [1] 1109.65/291.56 gr(s(x), 0) -> true [1] 1109.65/291.56 gr(s(x), s(y)) -> gr(x, y) [1] 1109.65/291.56 p(0) -> 0 [1] 1109.65/291.56 p(s(x)) -> x [1] 1109.65/291.56 eq(0, 0) -> true [1] 1109.65/291.56 eq(s(x), 0) -> false [1] 1109.65/291.56 eq(0, s(x)) -> false [1] 1109.65/291.56 eq(s(x), s(y)) -> eq(x, y) [1] 1109.65/291.56 and(true, true) -> true [1] 1109.65/291.56 and(false, x) -> false [1] 1109.65/291.56 and(x, false) -> false [1] 1109.65/291.56 1109.65/291.56 The TRS has the following type information: 1109.65/291.56 cond1 :: true:false -> 0:s -> 0:s -> 0:s -> cond1:cond2 1109.65/291.56 true :: true:false 1109.65/291.56 cond2 :: true:false -> 0:s -> 0:s -> 0:s -> cond1:cond2 1109.65/291.56 gr :: 0:s -> 0:s -> true:false 1109.65/291.56 p :: 0:s -> 0:s 1109.65/291.56 false :: true:false 1109.65/291.56 and :: true:false -> true:false -> true:false 1109.65/291.56 eq :: 0:s -> 0:s -> true:false 1109.65/291.56 0 :: 0:s 1109.65/291.56 s :: 0:s -> 0:s 1109.65/291.56 1109.65/291.56 Rewrite Strategy: INNERMOST 1109.65/291.56 ---------------------------------------- 1109.65/291.56 1109.65/291.56 (5) CompletionProof (UPPER BOUND(ID)) 1109.65/291.56 The TRS is a completely defined constructor system, as every type has a constant constructor and the following rules were added: 1109.65/291.56 1109.65/291.56 cond1(v0, v1, v2, v3) -> null_cond1 [0] 1109.65/291.56 1109.65/291.56 And the following fresh constants: null_cond1 1109.65/291.56 1109.65/291.56 ---------------------------------------- 1109.65/291.56 1109.65/291.56 (6) 1109.65/291.56 Obligation: 1109.65/291.56 Runtime Complexity Weighted TRS where all functions are completely defined. The underlying TRS is: 1109.65/291.56 1109.65/291.56 Runtime Complexity Weighted TRS with Types. 1109.65/291.56 The TRS R consists of the following rules: 1109.65/291.56 1109.65/291.56 cond1(true, x, y, z) -> cond2(gr(y, z), x, y, z) [1] 1109.65/291.56 cond2(true, x, y, z) -> cond2(gr(y, z), p(x), p(y), z) [1] 1109.65/291.56 cond2(false, x, y, z) -> cond1(and(eq(x, y), gr(x, z)), x, y, z) [1] 1109.65/291.56 gr(0, x) -> false [1] 1109.65/291.56 gr(s(x), 0) -> true [1] 1109.65/291.56 gr(s(x), s(y)) -> gr(x, y) [1] 1109.65/291.56 p(0) -> 0 [1] 1109.65/291.56 p(s(x)) -> x [1] 1109.65/291.56 eq(0, 0) -> true [1] 1109.65/291.56 eq(s(x), 0) -> false [1] 1109.65/291.56 eq(0, s(x)) -> false [1] 1109.65/291.56 eq(s(x), s(y)) -> eq(x, y) [1] 1109.65/291.56 and(true, true) -> true [1] 1109.65/291.56 and(false, x) -> false [1] 1109.65/291.56 and(x, false) -> false [1] 1109.65/291.56 cond1(v0, v1, v2, v3) -> null_cond1 [0] 1109.65/291.56 1109.65/291.56 The TRS has the following type information: 1109.65/291.56 cond1 :: true:false -> 0:s -> 0:s -> 0:s -> null_cond1 1109.65/291.56 true :: true:false 1109.65/291.56 cond2 :: true:false -> 0:s -> 0:s -> 0:s -> null_cond1 1109.65/291.56 gr :: 0:s -> 0:s -> true:false 1109.65/291.56 p :: 0:s -> 0:s 1109.65/291.56 false :: true:false 1109.65/291.56 and :: true:false -> true:false -> true:false 1109.65/291.56 eq :: 0:s -> 0:s -> true:false 1109.65/291.56 0 :: 0:s 1109.65/291.56 s :: 0:s -> 0:s 1109.65/291.56 null_cond1 :: null_cond1 1109.65/291.56 1109.65/291.56 Rewrite Strategy: INNERMOST 1109.65/291.56 ---------------------------------------- 1109.65/291.56 1109.65/291.56 (7) CpxTypedWeightedTrsToRntsProof (UPPER BOUND(ID)) 1109.65/291.56 Transformed the TRS into an over-approximating RNTS by (improved) Size Abstraction. 1109.65/291.56 The constant constructors are abstracted as follows: 1109.65/291.56 1109.65/291.56 true => 1 1109.65/291.56 false => 0 1109.65/291.56 0 => 0 1109.65/291.56 null_cond1 => 0 1109.65/291.56 1109.65/291.56 ---------------------------------------- 1109.65/291.56 1109.65/291.56 (8) 1109.65/291.56 Obligation: 1109.65/291.56 Complexity RNTS consisting of the following rules: 1109.65/291.56 1109.65/291.56 and(z', z'') -{ 1 }-> 1 :|: z' = 1, z'' = 1 1109.65/291.56 and(z', z'') -{ 1 }-> 0 :|: x >= 0, z'' = x, z' = 0 1109.65/291.56 and(z', z'') -{ 1 }-> 0 :|: z'' = 0, z' = x, x >= 0 1109.65/291.56 cond1(z', z'', z1, z2) -{ 1 }-> cond2(gr(y, z), x, y, z) :|: z1 = y, z >= 0, z2 = z, x >= 0, y >= 0, z'' = x, z' = 1 1109.65/291.56 cond1(z', z'', z1, z2) -{ 0 }-> 0 :|: z2 = v3, v0 >= 0, z1 = v2, v1 >= 0, z'' = v1, v2 >= 0, v3 >= 0, z' = v0 1109.65/291.56 cond2(z', z'', z1, z2) -{ 1 }-> cond2(gr(y, z), p(x), p(y), z) :|: z1 = y, z >= 0, z2 = z, x >= 0, y >= 0, z'' = x, z' = 1 1109.65/291.56 cond2(z', z'', z1, z2) -{ 1 }-> cond1(and(eq(x, y), gr(x, z)), x, y, z) :|: z1 = y, z >= 0, z2 = z, x >= 0, y >= 0, z'' = x, z' = 0 1109.65/291.56 eq(z', z'') -{ 1 }-> eq(x, y) :|: z' = 1 + x, x >= 0, y >= 0, z'' = 1 + y 1109.65/291.56 eq(z', z'') -{ 1 }-> 1 :|: z'' = 0, z' = 0 1109.65/291.56 eq(z', z'') -{ 1 }-> 0 :|: z'' = 0, z' = 1 + x, x >= 0 1109.65/291.56 eq(z', z'') -{ 1 }-> 0 :|: x >= 0, z'' = 1 + x, z' = 0 1109.65/291.56 gr(z', z'') -{ 1 }-> gr(x, y) :|: z' = 1 + x, x >= 0, y >= 0, z'' = 1 + y 1109.65/291.56 gr(z', z'') -{ 1 }-> 1 :|: z'' = 0, z' = 1 + x, x >= 0 1109.65/291.56 gr(z', z'') -{ 1 }-> 0 :|: x >= 0, z'' = x, z' = 0 1109.65/291.56 p(z') -{ 1 }-> x :|: z' = 1 + x, x >= 0 1109.65/291.56 p(z') -{ 1 }-> 0 :|: z' = 0 1109.65/291.56 1109.65/291.56 Only complete derivations are relevant for the runtime complexity. 1109.65/291.56 1109.65/291.56 ---------------------------------------- 1109.65/291.56 1109.65/291.56 (9) CompleteCoflocoProof (FINISHED) 1109.65/291.56 Transformed the RNTS (where only complete derivations are relevant) into cost relations for CoFloCo: 1109.65/291.56 1109.65/291.56 eq(start(V, V1, V6, V2),0,[cond1(V, V1, V6, V2, Out)],[V >= 0,V1 >= 0,V6 >= 0,V2 >= 0]). 1109.65/291.56 eq(start(V, V1, V6, V2),0,[cond2(V, V1, V6, V2, Out)],[V >= 0,V1 >= 0,V6 >= 0,V2 >= 0]). 1109.65/291.56 eq(start(V, V1, V6, V2),0,[gr(V, V1, Out)],[V >= 0,V1 >= 0]). 1109.65/291.56 eq(start(V, V1, V6, V2),0,[p(V, Out)],[V >= 0]). 1109.65/291.56 eq(start(V, V1, V6, V2),0,[eq(V, V1, Out)],[V >= 0,V1 >= 0]). 1109.65/291.56 eq(start(V, V1, V6, V2),0,[and(V, V1, Out)],[V >= 0,V1 >= 0]). 1109.65/291.56 eq(cond1(V, V1, V6, V2, Out),1,[gr(V3, V4, Ret0),cond2(Ret0, V5, V3, V4, Ret)],[Out = Ret,V6 = V3,V4 >= 0,V2 = V4,V5 >= 0,V3 >= 0,V1 = V5,V = 1]). 1109.65/291.56 eq(cond2(V, V1, V6, V2, Out),1,[gr(V9, V7, Ret01),p(V8, Ret1),p(V9, Ret2),cond2(Ret01, Ret1, Ret2, V7, Ret3)],[Out = Ret3,V6 = V9,V7 >= 0,V2 = V7,V8 >= 0,V9 >= 0,V1 = V8,V = 1]). 1109.65/291.56 eq(cond2(V, V1, V6, V2, Out),1,[eq(V11, V10, Ret00),gr(V11, V12, Ret011),and(Ret00, Ret011, Ret02),cond1(Ret02, V11, V10, V12, Ret4)],[Out = Ret4,V6 = V10,V12 >= 0,V2 = V12,V11 >= 0,V10 >= 0,V1 = V11,V = 0]). 1109.65/291.56 eq(gr(V, V1, Out),1,[],[Out = 0,V13 >= 0,V1 = V13,V = 0]). 1109.65/291.56 eq(gr(V, V1, Out),1,[],[Out = 1,V1 = 0,V = 1 + V14,V14 >= 0]). 1109.65/291.56 eq(gr(V, V1, Out),1,[gr(V16, V15, Ret5)],[Out = Ret5,V = 1 + V16,V16 >= 0,V15 >= 0,V1 = 1 + V15]). 1109.65/291.56 eq(p(V, Out),1,[],[Out = 0,V = 0]). 1109.65/291.56 eq(p(V, Out),1,[],[Out = V17,V = 1 + V17,V17 >= 0]). 1109.65/291.56 eq(eq(V, V1, Out),1,[],[Out = 1,V1 = 0,V = 0]). 1109.65/291.56 eq(eq(V, V1, Out),1,[],[Out = 0,V1 = 0,V = 1 + V18,V18 >= 0]). 1109.65/291.56 eq(eq(V, V1, Out),1,[],[Out = 0,V19 >= 0,V1 = 1 + V19,V = 0]). 1109.65/291.56 eq(eq(V, V1, Out),1,[eq(V21, V20, Ret6)],[Out = Ret6,V = 1 + V21,V21 >= 0,V20 >= 0,V1 = 1 + V20]). 1109.65/291.56 eq(and(V, V1, Out),1,[],[Out = 1,V = 1,V1 = 1]). 1109.65/291.56 eq(and(V, V1, Out),1,[],[Out = 0,V22 >= 0,V1 = V22,V = 0]). 1109.65/291.56 eq(and(V, V1, Out),1,[],[Out = 0,V1 = 0,V = V23,V23 >= 0]). 1109.65/291.56 eq(cond1(V, V1, V6, V2, Out),0,[],[Out = 0,V2 = V26,V25 >= 0,V6 = V27,V24 >= 0,V1 = V24,V27 >= 0,V26 >= 0,V = V25]). 1109.65/291.56 input_output_vars(cond1(V,V1,V6,V2,Out),[V,V1,V6,V2],[Out]). 1109.65/291.56 input_output_vars(cond2(V,V1,V6,V2,Out),[V,V1,V6,V2],[Out]). 1109.65/291.56 input_output_vars(gr(V,V1,Out),[V,V1],[Out]). 1109.65/291.56 input_output_vars(p(V,Out),[V],[Out]). 1109.65/291.56 input_output_vars(eq(V,V1,Out),[V,V1],[Out]). 1109.65/291.56 input_output_vars(and(V,V1,Out),[V,V1],[Out]). 1109.65/291.56 1109.65/291.56 1109.65/291.56 CoFloCo proof output: 1109.65/291.56 Preprocessing Cost Relations 1109.65/291.56 ===================================== 1109.65/291.56 1109.65/291.56 #### Computed strongly connected components 1109.65/291.56 0. non_recursive : [and/3] 1109.65/291.56 1. recursive : [eq/3] 1109.65/291.56 2. recursive : [gr/3] 1109.65/291.56 3. non_recursive : [p/2] 1109.65/291.56 4. recursive : [cond1/5,cond2/5] 1109.65/291.56 5. non_recursive : [start/4] 1109.65/291.56 1109.65/291.56 #### Obtained direct recursion through partial evaluation 1109.65/291.56 0. SCC is partially evaluated into and/3 1109.65/291.56 1. SCC is partially evaluated into eq/3 1109.65/291.56 2. SCC is partially evaluated into gr/3 1109.65/291.56 3. SCC is partially evaluated into p/2 1109.65/291.56 4. SCC is partially evaluated into cond2/5 1109.65/291.56 5. SCC is partially evaluated into start/4 1109.65/291.56 1109.65/291.56 Control-Flow Refinement of Cost Relations 1109.65/291.56 ===================================== 1109.65/291.56 1109.65/291.56 ### Specialization of cost equations and/3 1109.65/291.56 * CE 22 is refined into CE [23] 1109.65/291.56 * CE 20 is refined into CE [24] 1109.65/291.56 * CE 21 is refined into CE [25] 1109.65/291.56 1109.65/291.56 1109.65/291.56 ### Cost equations --> "Loop" of and/3 1109.65/291.56 * CEs [23] --> Loop 17 1109.65/291.56 * CEs [24] --> Loop 18 1109.65/291.56 * CEs [25] --> Loop 19 1109.65/291.56 1109.65/291.56 ### Ranking functions of CR and(V,V1,Out) 1109.65/291.56 1109.65/291.56 #### Partial ranking functions of CR and(V,V1,Out) 1109.65/291.56 1109.65/291.56 1109.65/291.56 ### Specialization of cost equations eq/3 1109.65/291.56 * CE 19 is refined into CE [26] 1109.65/291.56 * CE 17 is refined into CE [27] 1109.65/291.56 * CE 18 is refined into CE [28] 1109.65/291.56 * CE 16 is refined into CE [29] 1109.65/291.56 1109.65/291.56 1109.65/291.56 ### Cost equations --> "Loop" of eq/3 1109.65/291.56 * CEs [27] --> Loop 20 1109.65/291.56 * CEs [28] --> Loop 21 1109.65/291.56 * CEs [29] --> Loop 22 1109.65/291.56 * CEs [26] --> Loop 23 1109.65/291.56 1109.65/291.56 ### Ranking functions of CR eq(V,V1,Out) 1109.65/291.56 * RF of phase [23]: [V,V1] 1109.65/291.56 1109.65/291.56 #### Partial ranking functions of CR eq(V,V1,Out) 1109.65/291.56 * Partial RF of phase [23]: 1109.65/291.56 - RF of loop [23:1]: 1109.65/291.56 V 1109.65/291.56 V1 1109.65/291.56 1109.65/291.56 1109.65/291.56 ### Specialization of cost equations gr/3 1109.65/291.56 * CE 10 is refined into CE [30] 1109.65/291.56 * CE 9 is refined into CE [31] 1109.65/291.56 * CE 8 is refined into CE [32] 1109.65/291.56 1109.65/291.56 1109.65/291.56 ### Cost equations --> "Loop" of gr/3 1109.65/291.56 * CEs [31] --> Loop 24 1109.65/291.56 * CEs [32] --> Loop 25 1109.65/291.56 * CEs [30] --> Loop 26 1109.65/291.56 1109.65/291.56 ### Ranking functions of CR gr(V,V1,Out) 1109.65/291.56 * RF of phase [26]: [V,V1] 1109.65/291.56 1109.65/291.56 #### Partial ranking functions of CR gr(V,V1,Out) 1109.65/291.56 * Partial RF of phase [26]: 1109.65/291.56 - RF of loop [26:1]: 1109.65/291.56 V 1109.65/291.56 V1 1109.65/291.56 1109.65/291.56 1109.65/291.56 ### Specialization of cost equations p/2 1109.65/291.56 * CE 15 is refined into CE [33] 1109.65/291.56 * CE 14 is refined into CE [34] 1109.65/291.56 1109.65/291.56 1109.65/291.56 ### Cost equations --> "Loop" of p/2 1109.65/291.56 * CEs [33] --> Loop 27 1109.65/291.56 * CEs [34] --> Loop 28 1109.65/291.56 1109.65/291.56 ### Ranking functions of CR p(V,Out) 1109.65/291.56 1109.65/291.56 #### Partial ranking functions of CR p(V,Out) 1109.65/291.56 1109.65/291.56 1109.65/291.56 ### Specialization of cost equations cond2/5 1109.65/291.56 * CE 13 is refined into CE [35,36,37,38,39,40,41,42] 1109.65/291.56 * CE 12 is refined into CE [43,44] 1109.65/291.56 * CE 11 is refined into CE [45,46,47,48,49,50,51,52,53,54,55,56,57,58,59,60,61,62] 1109.65/291.56 1109.65/291.56 1109.65/291.56 ### Cost equations --> "Loop" of cond2/5 1109.65/291.56 * CEs [55] --> Loop 29 1109.65/291.56 * CEs [57,58] --> Loop 30 1109.65/291.56 * CEs [59] --> Loop 31 1109.65/291.56 * CEs [53,54] --> Loop 32 1109.65/291.56 * CEs [62] --> Loop 33 1109.65/291.56 * CEs [61] --> Loop 34 1109.65/291.56 * CEs [56] --> Loop 35 1109.65/291.56 * CEs [52] --> Loop 36 1109.65/291.56 * CEs [60] --> Loop 37 1109.65/291.56 * CEs [51] --> Loop 38 1109.65/291.56 * CEs [49,50] --> Loop 39 1109.65/291.56 * CEs [48] --> Loop 40 1109.65/291.56 * CEs [46,47] --> Loop 41 1109.65/291.56 * CEs [45] --> Loop 42 1109.65/291.56 * CEs [42] --> Loop 43 1109.65/291.56 * CEs [40] --> Loop 44 1109.65/291.56 * CEs [38] --> Loop 45 1109.65/291.56 * CEs [36] --> Loop 46 1109.65/291.56 * CEs [41] --> Loop 47 1109.65/291.56 * CEs [39] --> Loop 48 1109.65/291.56 * CEs [37] --> Loop 49 1109.65/291.56 * CEs [35] --> Loop 50 1109.65/291.56 * CEs [44] --> Loop 51 1109.65/291.56 * CEs [43] --> Loop 52 1109.65/291.56 1109.65/291.56 ### Ranking functions of CR cond2(V,V1,V6,V2,Out) 1109.65/291.56 * RF of phase [43]: [V1,V6-1,V6-V2] 1109.65/291.56 * RF of phase [45]: [V1,V6] 1109.65/291.56 * RF of phase [47]: [V6-1,V6-V2] 1109.65/291.56 * RF of phase [49]: [V6] 1109.65/291.56 1109.65/291.56 #### Partial ranking functions of CR cond2(V,V1,V6,V2,Out) 1109.65/291.56 * Partial RF of phase [43]: 1109.65/291.56 - RF of loop [43:1]: 1109.65/291.56 V1 1109.65/291.56 V6-1 1109.65/291.56 V6-V2 1109.65/291.56 * Partial RF of phase [45]: 1109.65/291.56 - RF of loop [45:1]: 1109.65/291.56 V1 1109.65/291.56 V6 1109.65/291.56 * Partial RF of phase [47]: 1109.65/291.56 - RF of loop [47:1]: 1109.65/291.56 V6-1 1109.65/291.56 V6-V2 1109.65/291.56 * Partial RF of phase [49]: 1109.65/291.56 - RF of loop [49:1]: 1109.65/291.56 V6 1109.65/291.56 1109.65/291.56 1109.65/291.56 ### Specialization of cost equations start/4 1109.65/291.56 * CE 1 is refined into CE [63] 1109.65/291.56 * CE 2 is refined into CE [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] 1109.65/291.56 * CE 3 is refined into CE [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,122,123,124,125,126,127,128,129,130,131,132,133,134,135,136,137,138,139] 1109.65/291.56 * CE 4 is refined into CE [140,141,142,143] 1109.65/291.56 * CE 5 is refined into CE [144,145] 1109.65/291.56 * CE 6 is refined into CE [146,147,148,149,150,151] 1109.65/291.56 * CE 7 is refined into CE [152,153,154] 1109.65/291.56 1109.65/291.56 1109.65/291.56 ### Cost equations --> "Loop" of start/4 1109.65/291.56 * CEs [91,139] --> Loop 53 1109.65/291.56 * CEs [90,138] --> Loop 54 1109.65/291.56 * CEs [136] --> Loop 55 1109.65/291.56 * CEs [77] --> Loop 56 1109.65/291.56 * CEs [75,135] --> Loop 57 1109.65/291.56 * CEs [89,134] --> Loop 58 1109.65/291.56 * CEs [88,133] --> Loop 59 1109.65/291.56 * CEs [87,132] --> Loop 60 1109.65/291.56 * CEs [86,131] --> Loop 61 1109.65/291.56 * CEs [85,130] --> Loop 62 1109.65/291.56 * CEs [74,129] --> Loop 63 1109.65/291.56 * CEs [84,128] --> Loop 64 1109.65/291.56 * CEs [83,127] --> Loop 65 1109.65/291.56 * CEs [82,126] --> Loop 66 1109.65/291.56 * CEs [81,125] --> Loop 67 1109.65/291.56 * CEs [80,124] --> Loop 68 1109.65/291.56 * CEs [72,123] --> Loop 69 1109.65/291.56 * CEs [71,122] --> Loop 70 1109.65/291.56 * CEs [70,121] --> Loop 71 1109.65/291.56 * CEs [69,120] --> Loop 72 1109.65/291.56 * CEs [76,119,137] --> Loop 73 1109.65/291.56 * CEs [118] --> Loop 74 1109.65/291.56 * CEs [67,117] --> Loop 75 1109.65/291.56 * CEs [116] --> Loop 76 1109.65/291.56 * CEs [66] --> Loop 77 1109.65/291.56 * CEs [65,115] --> Loop 78 1109.65/291.56 * CEs [112,113,114,151,153] --> Loop 79 1109.65/291.56 * CEs [79,111] --> Loop 80 1109.65/291.56 * CEs [78,109] --> Loop 81 1109.65/291.56 * CEs [68,108,142,143,145,149,150] --> Loop 82 1109.65/291.56 * CEs [63,73,107,110] --> Loop 83 1109.65/291.56 * CEs [64,106,141,148,154] --> Loop 84 1109.65/291.56 * CEs [92,93,94,95,96,97,98,99,100,101,102,103,104,105,140,144,146,147,152] --> Loop 85 1109.65/291.56 1109.65/291.56 ### Ranking functions of CR start(V,V1,V6,V2) 1109.65/291.56 1109.65/291.56 #### Partial ranking functions of CR start(V,V1,V6,V2) 1109.65/291.56 1109.65/291.56 1109.65/291.56 Computing Bounds 1109.65/291.56 ===================================== 1109.65/291.56 1109.65/291.56 #### Cost of chains of and(V,V1,Out): 1109.65/291.56 * Chain [19]: 1 1109.65/291.56 with precondition: [V=0,Out=0,V1>=0] 1109.65/291.56 1109.65/291.56 * Chain [18]: 1 1109.65/291.56 with precondition: [V=1,V1=1,Out=1] 1109.65/291.56 1109.65/291.56 * Chain [17]: 1 1109.65/291.56 with precondition: [V1=0,Out=0,V>=0] 1109.65/291.56 1109.65/291.56 1109.65/291.56 #### Cost of chains of eq(V,V1,Out): 1109.65/291.56 * Chain [[23],22]: 1*it(23)+1 1109.65/291.56 Such that:it(23) =< V 1109.65/291.56 1109.65/291.56 with precondition: [Out=1,V=V1,V>=1] 1109.65/291.56 1109.65/291.56 * Chain [[23],21]: 1*it(23)+1 1109.65/291.56 Such that:it(23) =< V 1109.65/291.56 1109.65/291.56 with precondition: [Out=0,V>=1,V1>=V+1] 1109.65/291.56 1109.65/291.56 * Chain [[23],20]: 1*it(23)+1 1109.65/291.56 Such that:it(23) =< V1 1109.65/291.56 1109.65/291.56 with precondition: [Out=0,V1>=1,V>=V1+1] 1109.65/291.56 1109.65/291.56 * Chain [22]: 1 1109.65/291.56 with precondition: [V=0,V1=0,Out=1] 1109.65/291.56 1109.65/291.56 * Chain [21]: 1 1109.65/291.56 with precondition: [V=0,Out=0,V1>=1] 1109.65/291.56 1109.65/291.56 * Chain [20]: 1 1109.65/291.56 with precondition: [V1=0,Out=0,V>=1] 1109.65/291.56 1109.65/291.56 1109.65/291.56 #### Cost of chains of gr(V,V1,Out): 1109.65/291.56 * Chain [[26],25]: 1*it(26)+1 1109.65/291.56 Such that:it(26) =< V 1109.65/291.56 1109.65/291.56 with precondition: [Out=0,V>=1,V1>=V] 1109.65/291.56 1109.65/291.56 * Chain [[26],24]: 1*it(26)+1 1109.65/291.56 Such that:it(26) =< V1 1109.65/291.56 1109.65/291.56 with precondition: [Out=1,V1>=1,V>=V1+1] 1109.65/291.56 1109.65/291.56 * Chain [25]: 1 1109.65/291.56 with precondition: [V=0,Out=0,V1>=0] 1109.65/291.56 1109.65/291.56 * Chain [24]: 1 1109.65/291.56 with precondition: [V1=0,Out=1,V>=1] 1109.65/291.56 1109.65/291.56 1109.65/291.56 #### Cost of chains of p(V,Out): 1109.65/291.56 * Chain [28]: 1 1109.65/291.56 with precondition: [V=0,Out=0] 1109.65/291.56 1109.65/291.56 * Chain [27]: 1 1109.65/291.56 with precondition: [V=Out+1,V>=1] 1109.65/291.56 1109.65/291.56 1109.65/291.56 #### Cost of chains of cond2(V,V1,V6,V2,Out): 1109.65/291.56 * Chain [[49],50,42]: 4*it(49)+8 1109.65/291.56 Such that:it(49) =< V6 1109.65/291.56 1109.65/291.56 with precondition: [V=1,V1=0,V2=0,Out=0,V6>=1] 1109.65/291.56 1109.65/291.56 * Chain [[47],48,42]: 4*it(47)+1*s(1)+1*s(4)+8 1109.65/291.56 Such that:it(47) =< V6 1109.65/291.56 aux(2) =< 1 1109.65/291.56 s(1) =< aux(2) 1109.65/291.56 s(4) =< it(47)*aux(2) 1109.65/291.56 1109.65/291.56 with precondition: [V=1,V1=0,V2=1,Out=0,V6>=2] 1109.65/291.56 1109.65/291.56 * Chain [[47],48,41]: 4*it(47)+1*s(1)+1*s(4)+8 1109.65/291.56 Such that:it(47) =< V6-V2 1109.65/291.56 aux(3) =< V2 1109.65/291.56 s(1) =< aux(3) 1109.65/291.56 s(4) =< it(47)*aux(3) 1109.65/291.56 1109.65/291.56 with precondition: [V=1,V1=0,Out=0,V2>=2,V6>=V2+1] 1109.65/291.56 1109.65/291.56 * Chain [[45],[49],50,42]: 4*it(45)+4*it(49)+8 1109.65/291.56 Such that:it(49) =< -V1+V6 1109.65/291.56 it(45) =< V1 1109.65/291.56 1109.65/291.56 with precondition: [V=1,V2=0,Out=0,V1>=1,V6>=V1+1] 1109.65/291.56 1109.65/291.56 * Chain [[45],50,42]: 4*it(45)+8 1109.65/291.56 Such that:it(45) =< V1 1109.65/291.56 1109.65/291.56 with precondition: [V=1,V2=0,Out=0,V1=V6,V1>=1] 1109.65/291.56 1109.65/291.56 * Chain [[45],46,42]: 4*it(45)+8 1109.65/291.56 Such that:it(45) =< V1 1109.65/291.56 1109.65/291.56 with precondition: [V=1,V2=0,Out=0,V1=V6+1,V1>=2] 1109.65/291.56 1109.65/291.56 * Chain [[45],46,40]: 4*it(45)+8 1109.65/291.56 Such that:it(45) =< V6 1109.65/291.56 1109.65/291.56 with precondition: [V=1,V2=0,Out=0,V6>=1,V1>=V6+2] 1109.65/291.56 1109.65/291.56 * Chain [[43],[47],48,42]: 4*it(43)+4*it(47)+1*s(1)+1*s(4)+1*s(7)+8 1109.65/291.56 Such that:it(47) =< -V1+V6 1109.65/291.56 it(43) =< V1 1109.65/291.56 aux(5) =< 1 1109.65/291.56 s(1) =< aux(5) 1109.65/291.56 s(4) =< it(47)*aux(5) 1109.65/291.56 s(7) =< it(43)*aux(5) 1109.65/291.56 1109.65/291.56 with precondition: [V=1,V2=1,Out=0,V1>=1,V6>=V1+2] 1109.65/291.56 1109.65/291.56 * Chain [[43],[47],48,41]: 4*it(43)+4*it(47)+1*s(1)+1*s(4)+1*s(7)+8 1109.65/291.56 Such that:it(47) =< -V1+V6-V2 1109.65/291.56 it(43) =< V1 1109.65/291.56 aux(6) =< V2 1109.65/291.56 s(1) =< aux(6) 1109.65/291.56 s(4) =< it(47)*aux(6) 1109.65/291.56 s(7) =< it(43)*aux(6) 1109.65/291.56 1109.65/291.56 with precondition: [V=1,Out=0,V1>=1,V2>=2,V6>=V1+V2+1] 1109.65/291.56 1109.65/291.56 * Chain [[43],48,42]: 4*it(43)+1*s(1)+1*s(7)+8 1109.65/291.56 Such that:it(43) =< V6 1109.65/291.56 aux(7) =< 1 1109.65/291.56 s(1) =< aux(7) 1109.65/291.56 s(7) =< it(43)*aux(7) 1109.65/291.56 1109.65/291.56 with precondition: [V=1,V2=1,Out=0,V1+1=V6,V1>=1] 1109.65/291.56 1109.65/291.56 * Chain [[43],48,41]: 4*it(43)+1*s(1)+1*s(7)+8 1109.65/291.56 Such that:it(43) =< V6-V2 1109.65/291.56 aux(8) =< V2 1109.65/291.56 s(1) =< aux(8) 1109.65/291.56 s(7) =< it(43)*aux(8) 1109.65/291.56 1109.65/291.56 with precondition: [V=1,Out=0,V1+V2=V6,V1>=1,V6>=V1+2] 1109.65/291.56 1109.65/291.56 * Chain [[43],44,42]: 4*it(43)+1*s(7)+1*s(8)+8 1109.65/291.56 Such that:it(43) =< V6 1109.65/291.56 aux(9) =< 1 1109.65/291.56 s(8) =< aux(9) 1109.65/291.56 s(7) =< it(43)*aux(9) 1109.65/291.56 1109.65/291.56 with precondition: [V=1,V2=1,Out=0,V1=V6,V1>=2] 1109.65/291.56 1109.65/291.56 * Chain [[43],44,41]: 4*it(43)+1*s(7)+1*s(8)+8 1109.65/291.56 Such that:it(43) =< V6-V2 1109.65/291.56 aux(10) =< V2 1109.65/291.56 s(8) =< aux(10) 1109.65/291.56 s(7) =< it(43)*aux(10) 1109.65/291.56 1109.65/291.56 with precondition: [V=1,Out=0,V1+V2=V6+1,V1>=2,V6>=V1+1] 1109.65/291.56 1109.65/291.56 * Chain [[43],44,39]: 4*it(43)+1*s(7)+1*s(8)+2*s(9)+8 1109.65/291.56 Such that:aux(11) =< 2 1109.65/291.56 it(43) =< V6 1109.65/291.56 aux(12) =< 1 1109.65/291.56 s(8) =< aux(12) 1109.65/291.56 s(9) =< aux(11) 1109.65/291.56 s(7) =< it(43)*aux(12) 1109.65/291.56 1109.65/291.56 with precondition: [V=1,V2=1,Out=0,V1=V6+1,V1>=3] 1109.65/291.56 1109.65/291.56 * Chain [[43],44,38]: 4*it(43)+1*s(7)+2*s(8)+8 1109.65/291.56 Such that:it(43) =< V6 1109.65/291.56 aux(13) =< 1 1109.65/291.56 s(8) =< aux(13) 1109.65/291.56 s(7) =< it(43)*aux(13) 1109.65/291.56 1109.65/291.56 with precondition: [V=1,V2=1,Out=0,V6>=2,V1>=V6+2] 1109.65/291.56 1109.65/291.56 * Chain [[43],44,34]: 4*it(43)+1*s(7)+3*s(8)+8 1109.65/291.56 Such that:it(43) =< V6-V2 1109.65/291.56 aux(16) =< V2 1109.65/291.56 s(8) =< aux(16) 1109.65/291.56 s(7) =< it(43)*aux(16) 1109.65/291.56 1109.65/291.56 with precondition: [V=1,Out=0,V1=V6,V2>=2,V1>=V2+1] 1109.65/291.56 1109.65/291.56 * Chain [[43],44,32]: 4*it(43)+1*s(7)+1*s(8)+4*s(14)+8 1109.65/291.56 Such that:aux(19) =< V1-V6+V2 1109.65/291.56 it(43) =< V6-V2 1109.65/291.56 aux(20) =< V2 1109.65/291.56 s(8) =< aux(20) 1109.65/291.56 s(14) =< aux(19) 1109.65/291.56 s(7) =< it(43)*aux(20) 1109.65/291.56 1109.65/291.56 with precondition: [V=1,Out=0,V6>=V1+1,V6>=V2+1,V1+V2>=V6+2] 1109.65/291.56 1109.65/291.56 * Chain [[43],44,31]: 4*it(43)+1*s(7)+3*s(8)+8 1109.65/291.56 Such that:it(43) =< V6-V2 1109.65/291.56 aux(22) =< V2 1109.65/291.56 s(8) =< aux(22) 1109.65/291.56 s(7) =< it(43)*aux(22) 1109.65/291.56 1109.65/291.56 with precondition: [V=1,Out=0,V2>=2,V1>=V6+2,V6>=V2+1] 1109.65/291.56 1109.65/291.56 * Chain [[43],44,30]: 4*it(43)+1*s(7)+3*s(8)+2*s(21)+8 1109.65/291.56 Such that:it(43) =< V6-V2 1109.65/291.56 aux(23) =< V2+1 1109.65/291.56 aux(26) =< V2 1109.65/291.56 s(8) =< aux(26) 1109.65/291.56 s(21) =< aux(23) 1109.65/291.56 s(7) =< it(43)*aux(26) 1109.65/291.56 1109.65/291.56 with precondition: [V=1,Out=0,V1=V6+1,V2>=2,V1>=V2+2] 1109.65/291.56 1109.65/291.56 * Chain [52,[45],50,42]: 5*it(45)+14 1109.65/291.56 Such that:aux(27) =< V1 1109.65/291.56 it(45) =< aux(27) 1109.65/291.56 1109.65/291.56 with precondition: [V=0,V2=0,Out=0,V1=V6,V1>=1] 1109.65/291.56 1109.65/291.56 * Chain [51,[43],44,42]: 5*it(43)+1*s(7)+3*s(8)+14 1109.65/291.56 Such that:aux(29) =< 1 1109.65/291.56 aux(30) =< V6 1109.65/291.56 it(43) =< aux(30) 1109.65/291.56 s(8) =< aux(29) 1109.65/291.56 s(7) =< it(43)*aux(29) 1109.65/291.56 1109.65/291.56 with precondition: [V=0,V2=1,Out=0,V1=V6,V1>=2] 1109.65/291.56 1109.65/291.56 * Chain [51,[43],44,34]: 4*it(43)+1*s(7)+5*s(8)+1*s(25)+14 1109.65/291.56 Such that:s(25) =< V6 1109.65/291.56 it(43) =< V6-V2 1109.65/291.56 aux(31) =< V2 1109.65/291.56 s(8) =< aux(31) 1109.65/291.56 s(7) =< it(43)*aux(31) 1109.65/291.56 1109.65/291.56 with precondition: [V=0,Out=0,V1=V6,V2>=2,V1>=V2+1] 1109.65/291.56 1109.65/291.56 * Chain [50,42]: 8 1109.65/291.56 with precondition: [V=1,V1=0,V6=0,Out=0,V2>=0] 1109.65/291.56 1109.65/291.56 * Chain [48,42]: 1*s(1)+8 1109.65/291.56 Such that:s(1) =< 1 1109.65/291.56 1109.65/291.56 with precondition: [V=1,V1=0,V6=1,Out=0,V2>=1] 1109.65/291.56 1109.65/291.56 * Chain [48,41]: 1*s(1)+8 1109.65/291.56 Such that:s(1) =< V6 1109.65/291.56 1109.65/291.56 with precondition: [V=1,V1=0,Out=0,V6>=2,V2>=V6] 1109.65/291.56 1109.65/291.56 * Chain [46,42]: 8 1109.65/291.56 with precondition: [V=1,V1=1,V6=0,Out=0,V2>=0] 1109.65/291.56 1109.65/291.56 * Chain [46,40]: 8 1109.65/291.56 with precondition: [V=1,V6=0,V2=0,Out=0,V1>=2] 1109.65/291.56 1109.65/291.56 * Chain [46,39]: 2*s(9)+8 1109.65/291.56 Such that:aux(11) =< V1 1109.65/291.56 s(9) =< aux(11) 1109.65/291.56 1109.65/291.56 with precondition: [V=1,V6=0,Out=0,V1>=2,V2+1>=V1] 1109.65/291.56 1109.65/291.56 * Chain [46,38]: 1*s(11)+8 1109.65/291.56 Such that:s(11) =< V2 1109.65/291.56 1109.65/291.56 with precondition: [V=1,V6=0,Out=0,V2>=1,V1>=V2+2] 1109.65/291.56 1109.65/291.56 * Chain [44,42]: 1*s(8)+8 1109.65/291.56 Such that:s(8) =< 1 1109.65/291.56 1109.65/291.56 with precondition: [V=1,V1=1,V6=1,Out=0,V2>=1] 1109.65/291.56 1109.65/291.56 * Chain [44,41]: 1*s(8)+8 1109.65/291.56 Such that:s(8) =< V6 1109.65/291.56 1109.65/291.56 with precondition: [V=1,V1=1,Out=0,V6>=2,V2>=V6] 1109.65/291.56 1109.65/291.56 * Chain [44,39]: 1*s(8)+2*s(9)+8 1109.65/291.56 Such that:s(8) =< 1 1109.65/291.56 aux(11) =< V1 1109.65/291.56 s(9) =< aux(11) 1109.65/291.56 1109.65/291.56 with precondition: [V=1,V6=1,Out=0,V1>=2,V2+1>=V1] 1109.65/291.56 1109.65/291.56 * Chain [44,38]: 1*s(8)+1*s(11)+8 1109.65/291.56 Such that:s(8) =< 1 1109.65/291.56 s(11) =< V2 1109.65/291.56 1109.65/291.56 with precondition: [V=1,V6=1,Out=0,V2>=1,V1>=V2+2] 1109.65/291.56 1109.65/291.56 * Chain [44,34]: 3*s(8)+8 1109.65/291.56 Such that:aux(15) =< V6 1109.65/291.56 s(8) =< aux(15) 1109.65/291.56 1109.65/291.56 with precondition: [V=1,Out=0,V1=V6,V1>=2,V2>=V1] 1109.65/291.56 1109.65/291.56 * Chain [44,32]: 1*s(8)+4*s(14)+8 1109.65/291.56 Such that:aux(19) =< V1 1109.65/291.56 s(8) =< V6 1109.65/291.56 s(14) =< aux(19) 1109.65/291.56 1109.65/291.56 with precondition: [V=1,Out=0,V1>=2,V6>=V1+1,V2>=V6] 1109.65/291.56 1109.65/291.56 * Chain [44,31]: 2*s(8)+1*s(19)+8 1109.65/291.56 Such that:s(19) =< V2 1109.65/291.56 aux(21) =< V6 1109.65/291.56 s(8) =< aux(21) 1109.65/291.56 1109.65/291.56 with precondition: [V=1,Out=0,V6>=2,V2>=V6,V1>=V2+2] 1109.65/291.56 1109.65/291.56 * Chain [44,30]: 3*s(8)+2*s(21)+8 1109.65/291.56 Such that:aux(23) =< V1 1109.65/291.56 aux(25) =< V6 1109.65/291.56 s(8) =< aux(25) 1109.65/291.56 s(21) =< aux(23) 1109.65/291.56 1109.65/291.56 with precondition: [V=1,Out=0,V6>=2,V2+1>=V1,V1>=V6+1] 1109.65/291.56 1109.65/291.56 * Chain [42]: 4 1109.65/291.56 with precondition: [V=0,V1=0,V6=0,Out=0,V2>=0] 1109.65/291.56 1109.65/291.56 * Chain [41]: 4 1109.65/291.56 with precondition: [V=0,V1=0,Out=0,V6>=1,V2>=0] 1109.65/291.56 1109.65/291.56 * Chain [40]: 4 1109.65/291.56 with precondition: [V=0,V6=0,V2=0,Out=0,V1>=1] 1109.65/291.56 1109.65/291.56 * Chain [39]: 2*s(9)+4 1109.65/291.56 Such that:aux(11) =< V1 1109.65/291.56 s(9) =< aux(11) 1109.65/291.56 1109.65/291.56 with precondition: [V=0,V6=0,Out=0,V1>=1,V2>=V1] 1109.65/291.56 1109.65/291.56 * Chain [38]: 1*s(11)+4 1109.65/291.56 Such that:s(11) =< V2 1109.65/291.56 1109.65/291.56 with precondition: [V=0,V6=0,Out=0,V2>=1,V1>=V2+1] 1109.65/291.56 1109.65/291.56 * Chain [37]: 1*s(28)+4 1109.65/291.56 Such that:s(28) =< V1 1109.65/291.56 1109.65/291.56 with precondition: [V=0,V2=0,Out=0,V1=V6,V1>=1] 1109.65/291.56 1109.65/291.56 * Chain [36]: 1*s(29)+4 1109.65/291.56 Such that:s(29) =< V1 1109.65/291.56 1109.65/291.56 with precondition: [V=0,V2=0,Out=0,V1>=1,V6>=V1+1] 1109.65/291.56 1109.65/291.56 * Chain [35]: 1*s(30)+4 1109.65/291.56 Such that:s(30) =< V6 1109.65/291.56 1109.65/291.56 with precondition: [V=0,V2=0,Out=0,V6>=1,V1>=V6+1] 1109.65/291.56 1109.65/291.56 * Chain [34]: 2*s(12)+4 1109.65/291.56 Such that:aux(14) =< V1 1109.65/291.56 s(12) =< aux(14) 1109.65/291.56 1109.65/291.56 with precondition: [V=0,Out=0,V1=V6,V1>=1,V2>=V1] 1109.65/291.56 1109.65/291.56 * Chain [33]: 1*s(31)+1*s(32)+4 1109.65/291.56 Such that:s(31) =< V6 1109.65/291.56 s(32) =< V2 1109.65/291.56 1109.65/291.56 with precondition: [V=0,Out=0,V1=V6,V2>=1,V1>=V2+1] 1109.65/291.56 1109.65/291.56 * Chain [32]: 4*s(14)+4 1109.65/291.56 Such that:aux(19) =< V1 1109.65/291.56 s(14) =< aux(19) 1109.65/291.56 1109.65/291.56 with precondition: [V=0,Out=0,V1>=1,V6>=V1+1,V2>=V1] 1109.65/291.56 1109.65/291.56 * Chain [31]: 1*s(18)+1*s(19)+4 1109.65/291.56 Such that:s(18) =< V6 1109.65/291.56 s(19) =< V2 1109.65/291.56 1109.65/291.56 with precondition: [V=0,Out=0,V6>=1,V2>=1,V1>=V6+1,V1>=V2+1] 1109.65/291.56 1109.65/291.56 * Chain [30]: 2*s(20)+2*s(21)+4 1109.65/291.56 Such that:aux(23) =< V1 1109.65/291.56 aux(24) =< V6 1109.65/291.56 s(21) =< aux(23) 1109.65/291.56 s(20) =< aux(24) 1109.65/291.56 1109.65/291.56 with precondition: [V=0,Out=0,V6>=1,V2>=V1,V1>=V6+1] 1109.65/291.56 1109.65/291.56 * Chain [29]: 1*s(33)+1*s(34)+4 1109.65/291.56 Such that:s(33) =< V1 1109.65/291.56 s(34) =< V2 1109.65/291.56 1109.65/291.56 with precondition: [V=0,Out=0,V2>=1,V6>=V1+1,V1>=V2+1] 1109.65/291.56 1109.65/291.56 1109.65/291.56 #### Cost of chains of start(V,V1,V6,V2): 1109.65/291.56 * Chain [85]: 16*s(51)+9*s(52)+13*s(56)+4*s(58)+3*s(63)+1*s(64)+1*s(65)+14 1109.65/291.56 Such that:s(57) =< 1 1109.65/291.56 s(58) =< V6-V2 1109.65/291.56 aux(35) =< V1 1109.65/291.56 aux(36) =< V6 1109.65/291.56 aux(37) =< V2 1109.65/291.56 s(51) =< aux(35) 1109.65/291.56 s(56) =< aux(36) 1109.65/291.56 s(52) =< aux(37) 1109.65/291.56 s(63) =< s(57) 1109.65/291.56 s(64) =< s(56)*s(57) 1109.65/291.56 s(65) =< s(58)*aux(37) 1109.65/291.56 1109.65/291.56 with precondition: [V=0] 1109.65/291.56 1109.65/291.56 * Chain [84]: 8 1109.65/291.56 with precondition: [V1=0,V>=0] 1109.65/291.56 1109.65/291.56 * Chain [83]: 2*s(78)+1*s(79)+8 1109.65/291.56 Such that:s(79) =< 1 1109.65/291.56 aux(38) =< V6 1109.65/291.56 s(78) =< aux(38) 1109.65/291.56 1109.65/291.56 with precondition: [V>=0,V1>=0,V6>=0,V2>=0] 1109.65/291.56 1109.65/291.56 * Chain [82]: 8*s(81)+2*s(83)+2*s(84)+10 1109.65/291.56 Such that:aux(39) =< V 1109.65/291.56 aux(40) =< V1 1109.65/291.56 aux(41) =< V6 1109.65/291.56 s(83) =< aux(39) 1109.65/291.56 s(84) =< aux(40) 1109.65/291.56 s(81) =< aux(41) 1109.65/291.56 1109.65/291.56 with precondition: [V>=1] 1109.65/291.56 1109.65/291.56 * Chain [81]: 3*s(87)+8*s(88)+2*s(91)+10 1109.65/291.56 Such that:aux(43) =< 1 1109.65/291.56 aux(44) =< V6 1109.65/291.56 s(88) =< aux(44) 1109.65/291.56 s(87) =< aux(43) 1109.65/291.56 s(91) =< s(88)*aux(43) 1109.65/291.56 1109.65/291.56 with precondition: [V=1,V1=0,V2=1,V6>=2] 1109.65/291.56 1109.65/291.56 * Chain [80]: 3*s(96)+8*s(97)+2*s(100)+10 1109.65/291.56 Such that:aux(46) =< V6-V2 1109.65/291.56 aux(47) =< V2 1109.65/291.56 s(97) =< aux(46) 1109.65/291.56 s(96) =< aux(47) 1109.65/291.56 s(100) =< s(97)*aux(47) 1109.65/291.56 1109.65/291.56 with precondition: [V=1,V1=0,V2>=2,V6>=V2+1] 1109.65/291.56 1109.65/291.56 * Chain [79]: 1*s(105)+1*s(106)+1*s(107)+8 1109.65/291.56 Such that:s(105) =< 1 1109.65/291.56 s(107) =< V1 1109.65/291.56 s(106) =< V6 1109.65/291.56 1109.65/291.56 with precondition: [V=V1,V>=1] 1109.65/291.56 1109.65/291.56 * Chain [78]: 8 1109.65/291.56 with precondition: [V=1,V6=0,V2=0,V1>=1] 1109.65/291.56 1109.65/291.56 * Chain [77]: 2*s(109)+6 1109.65/291.56 Such that:s(108) =< V1 1109.65/291.56 s(109) =< s(108) 1109.65/291.56 1109.65/291.56 with precondition: [V=1,V6=0,V1>=1,V2>=V1] 1109.65/291.56 1109.65/291.56 * Chain [76]: 2*s(111)+8 1109.65/291.56 Such that:s(110) =< V1 1109.65/291.56 s(111) =< s(110) 1109.65/291.56 1109.65/291.56 with precondition: [V=1,V6=0,V1>=2,V2+1>=V1] 1109.65/291.56 1109.65/291.56 * Chain [75]: 2*s(112)+8 1109.65/291.56 Such that:aux(48) =< V2 1109.65/291.56 s(112) =< aux(48) 1109.65/291.56 1109.65/291.56 with precondition: [V=1,V6=0,V2>=1,V1>=V2+1] 1109.65/291.56 1109.65/291.56 * Chain [74]: 1*s(114)+2*s(116)+8 1109.65/291.56 Such that:s(114) =< 1 1109.65/291.56 s(115) =< V1 1109.65/291.56 s(116) =< s(115) 1109.65/291.56 1109.65/291.56 with precondition: [V=1,V6=1,V1>=2,V2+1>=V1] 1109.65/291.56 1109.65/291.56 * Chain [73]: 4*s(117)+3*s(119)+1*s(120)+8 1109.65/291.56 Such that:s(120) =< 1 1109.65/291.56 aux(50) =< V6 1109.65/291.56 aux(51) =< V2 1109.65/291.56 s(119) =< aux(51) 1109.65/291.56 s(117) =< aux(50) 1109.65/291.56 1109.65/291.56 with precondition: [V=1,V6>=1,V2>=V6,V1>=V2+1] 1109.65/291.56 1109.65/291.56 * Chain [72]: 8*s(125)+10 1109.65/291.56 Such that:aux(52) =< V1 1109.65/291.56 s(125) =< aux(52) 1109.65/291.56 1109.65/291.56 with precondition: [V=1,V2=0,V1=V6,V1>=1] 1109.65/291.56 1109.65/291.56 * Chain [71]: 8*s(127)+10 1109.65/291.56 Such that:aux(53) =< V1 1109.65/291.56 s(127) =< aux(53) 1109.65/291.56 1109.65/291.56 with precondition: [V=1,V2=0,V1=V6+1,V1>=2] 1109.65/291.56 1109.65/291.56 * Chain [70]: 8*s(129)+8*s(130)+10 1109.65/291.56 Such that:aux(54) =< -V1+V6 1109.65/291.56 aux(55) =< V1 1109.65/291.56 s(129) =< aux(54) 1109.65/291.56 s(130) =< aux(55) 1109.65/291.56 1109.65/291.56 with precondition: [V=1,V2=0,V1>=1,V6>=V1+1] 1109.65/291.56 1109.65/291.56 * Chain [69]: 8*s(133)+10 1109.65/291.56 Such that:aux(56) =< V6 1109.65/291.56 s(133) =< aux(56) 1109.65/291.56 1109.65/291.56 with precondition: [V=1,V2=0,V6>=1,V1>=V6+2] 1109.65/291.56 1109.65/291.56 * Chain [68]: 3*s(135)+8*s(136)+2*s(139)+10 1109.65/291.56 Such that:aux(58) =< 1 1109.65/291.56 aux(59) =< V6 1109.65/291.56 s(136) =< aux(59) 1109.65/291.56 s(135) =< aux(58) 1109.65/291.56 s(139) =< s(136)*aux(58) 1109.65/291.56 1109.65/291.56 with precondition: [V=1,V2=1,V1+1=V6,V1>=1] 1109.65/291.56 1109.65/291.56 * Chain [67]: 3*s(144)+8*s(145)+2*s(148)+10 1109.65/291.56 Such that:aux(61) =< 1 1109.65/291.56 aux(62) =< V6 1109.65/291.56 s(145) =< aux(62) 1109.65/291.56 s(144) =< aux(61) 1109.65/291.56 s(148) =< s(145)*aux(61) 1109.65/291.56 1109.65/291.56 with precondition: [V=1,V2=1,V1=V6,V1>=2] 1109.65/291.56 1109.65/291.56 * Chain [66]: 3*s(153)+4*s(155)+4*s(158)+1*s(159)+4*s(161)+1*s(165)+10 1109.65/291.56 Such that:s(155) =< V1 1109.65/291.56 s(161) =< V6 1109.65/291.56 aux(64) =< 1 1109.65/291.56 aux(65) =< 2 1109.65/291.56 s(153) =< aux(64) 1109.65/291.56 s(158) =< aux(65) 1109.65/291.56 s(165) =< s(161)*aux(64) 1109.65/291.56 s(159) =< s(155)*aux(64) 1109.65/291.56 1109.65/291.56 with precondition: [V=1,V2=1,V1=V6+1,V1>=3] 1109.65/291.56 1109.65/291.56 * Chain [65]: 3*s(166)+8*s(167)+8*s(168)+2*s(171)+2*s(172)+10 1109.65/291.56 Such that:aux(67) =< 1 1109.65/291.56 aux(68) =< -V1+V6 1109.65/291.56 aux(69) =< V1 1109.65/291.56 s(167) =< aux(68) 1109.65/291.56 s(168) =< aux(69) 1109.65/291.56 s(166) =< aux(67) 1109.65/291.56 s(171) =< s(167)*aux(67) 1109.65/291.56 s(172) =< s(168)*aux(67) 1109.65/291.56 1109.65/291.56 with precondition: [V=1,V2=1,V1>=1,V6>=V1+2] 1109.65/291.56 1109.65/291.56 * Chain [64]: 5*s(179)+8*s(180)+2*s(183)+10 1109.65/291.56 Such that:aux(71) =< 1 1109.65/291.56 aux(72) =< V6 1109.65/291.56 s(180) =< aux(72) 1109.65/291.56 s(179) =< aux(71) 1109.65/291.56 s(183) =< s(180)*aux(71) 1109.65/291.56 1109.65/291.56 with precondition: [V=1,V2=1,V6>=2,V1>=V6+2] 1109.65/291.56 1109.65/291.56 * Chain [63]: 3*s(188)+3*s(192)+8 1109.65/291.56 Such that:aux(73) =< V1 1109.65/291.56 s(191) =< V6 1109.65/291.56 s(188) =< aux(73) 1109.65/291.56 s(192) =< s(191) 1109.65/291.56 1109.65/291.56 with precondition: [V=1,V1=V6,V1>=1,V2>=V1] 1109.65/291.56 1109.65/291.56 * Chain [62]: 7*s(193)+4*s(194)+1*s(197)+4*s(198)+1*s(201)+10 1109.65/291.56 Such that:s(198) =< V1-V2 1109.65/291.56 s(194) =< V6-V2 1109.65/291.56 aux(75) =< V2 1109.65/291.56 s(193) =< aux(75) 1109.65/291.56 s(201) =< s(198)*aux(75) 1109.65/291.56 s(197) =< s(194)*aux(75) 1109.65/291.56 1109.65/291.56 with precondition: [V=1,V1=V6,V2>=2,V1>=V2+1] 1109.65/291.56 1109.65/291.56 * Chain [61]: 7*s(202)+8*s(203)+4*s(207)+2*s(208)+10 1109.65/291.56 Such that:aux(77) =< V6-V2 1109.65/291.56 aux(78) =< V2 1109.65/291.56 aux(79) =< V2+1 1109.65/291.56 s(203) =< aux(77) 1109.65/291.56 s(202) =< aux(78) 1109.65/291.56 s(207) =< aux(79) 1109.65/291.56 s(208) =< s(203)*aux(78) 1109.65/291.56 1109.65/291.56 with precondition: [V=1,V1=V6+1,V2>=2,V1>=V2+2] 1109.65/291.56 1109.65/291.56 * Chain [60]: 3*s(215)+4*s(216)+1*s(219)+4*s(220)+1*s(223)+10 1109.65/291.56 Such that:s(220) =< V1 1109.65/291.56 s(216) =< V6-V2 1109.65/291.56 aux(81) =< V2 1109.65/291.56 s(215) =< aux(81) 1109.65/291.56 s(223) =< s(220)*aux(81) 1109.65/291.56 s(219) =< s(216)*aux(81) 1109.65/291.56 1109.65/291.56 with precondition: [V=1,V6=V1+V2,V1>=1,V6>=V1+2] 1109.65/291.56 1109.65/291.56 * Chain [59]: 3*s(224)+4*s(225)+1*s(228)+4*s(229)+1*s(232)+10 1109.65/291.56 Such that:s(229) =< V1 1109.65/291.56 s(225) =< V6-V2 1109.65/291.56 aux(83) =< V2 1109.65/291.56 s(224) =< aux(83) 1109.65/291.56 s(232) =< s(229)*aux(83) 1109.65/291.56 s(228) =< s(225)*aux(83) 1109.65/291.56 1109.65/291.56 with precondition: [V=1,V6+1=V1+V2,V1>=2,V6>=V1+1] 1109.65/291.56 1109.65/291.56 * Chain [58]: 3*s(233)+8*s(234)+8*s(235)+2*s(238)+2*s(239)+10 1109.65/291.56 Such that:aux(85) =< -V1+V6-V2 1109.65/291.56 aux(86) =< V1 1109.65/291.56 aux(87) =< V2 1109.65/291.56 s(234) =< aux(85) 1109.65/291.56 s(235) =< aux(86) 1109.65/291.56 s(233) =< aux(87) 1109.65/291.56 s(238) =< s(234)*aux(87) 1109.65/291.56 s(239) =< s(235)*aux(87) 1109.65/291.56 1109.65/291.56 with precondition: [V=1,V1>=1,V2>=2,V6>=V1+V2+1] 1109.65/291.56 1109.65/291.56 * Chain [57]: 2*s(246)+8*s(248)+8 1109.65/291.56 Such that:aux(88) =< V1 1109.65/291.56 aux(89) =< V6 1109.65/291.56 s(246) =< aux(89) 1109.65/291.56 s(248) =< aux(88) 1109.65/291.56 1109.65/291.56 with precondition: [V=1,V1>=1,V6>=V1+1,V2>=V6] 1109.65/291.56 1109.65/291.56 * Chain [56]: 3*s(252)+2*s(255)+6 1109.65/291.56 Such that:s(253) =< V1 1109.65/291.56 aux(90) =< V6 1109.65/291.56 s(252) =< aux(90) 1109.65/291.56 s(255) =< s(253) 1109.65/291.56 1109.65/291.56 with precondition: [V=1,V6>=1,V2>=V1,V1>=V6+1] 1109.65/291.56 1109.65/291.56 * Chain [55]: 3*s(259)+2*s(260)+8 1109.65/291.56 Such that:s(257) =< V1 1109.65/291.56 s(258) =< V6 1109.65/291.56 s(259) =< s(258) 1109.65/291.56 s(260) =< s(257) 1109.65/291.56 1109.65/291.56 with precondition: [V=1,V6>=2,V2+1>=V1,V1>=V6+1] 1109.65/291.56 1109.65/291.56 * Chain [54]: 7*s(261)+8*s(262)+2*s(265)+10 1109.65/291.56 Such that:aux(92) =< V6-V2 1109.65/291.56 aux(93) =< V2 1109.65/291.56 s(262) =< aux(92) 1109.65/291.56 s(261) =< aux(93) 1109.65/291.56 s(265) =< s(262)*aux(93) 1109.65/291.56 1109.65/291.56 with precondition: [V=1,V2>=2,V1>=V6+2,V6>=V2+1] 1109.65/291.56 1109.65/291.56 * Chain [53]: 3*s(270)+8*s(272)+8*s(275)+2*s(276)+10 1109.65/291.56 Such that:aux(95) =< V1-V6+V2 1109.65/291.56 aux(96) =< V6-V2 1109.65/291.56 aux(97) =< V2 1109.65/291.56 s(272) =< aux(96) 1109.65/291.56 s(270) =< aux(97) 1109.65/291.56 s(275) =< aux(95) 1109.65/291.56 s(276) =< s(272)*aux(97) 1109.65/291.56 1109.65/291.56 with precondition: [V=1,V6>=V1+1,V6>=V2+1,V1+V2>=V6+2] 1109.65/291.56 1109.65/291.56 1109.65/291.56 Closed-form bounds of start(V,V1,V6,V2): 1109.65/291.56 ------------------------------------- 1109.65/291.56 * Chain [85] with precondition: [V=0] 1109.65/291.56 - Upper bound: nat(V1)*16+17+nat(V6)*14+nat(V2)*9+nat(V6-V2)*nat(V2)+nat(V6-V2)*4 1109.65/291.56 - Complexity: n^2 1109.65/291.56 * Chain [84] with precondition: [V1=0,V>=0] 1109.65/291.56 - Upper bound: 8 1109.65/291.56 - Complexity: constant 1109.65/291.56 * Chain [83] with precondition: [V>=0,V1>=0,V6>=0,V2>=0] 1109.65/291.56 - Upper bound: 2*V6+9 1109.65/291.56 - Complexity: n 1109.65/291.56 * Chain [82] with precondition: [V>=1] 1109.65/291.56 - Upper bound: 2*V+10+nat(V1)*2+nat(V6)*8 1109.65/291.56 - Complexity: n 1109.65/291.56 * Chain [81] with precondition: [V=1,V1=0,V2=1,V6>=2] 1109.65/291.56 - Upper bound: 10*V6+13 1109.65/291.56 - Complexity: n 1109.65/291.56 * Chain [80] with precondition: [V=1,V1=0,V2>=2,V6>=V2+1] 1109.65/291.56 - Upper bound: 8*V6-8*V2+(3*V2+10+(V6-V2)*(2*V2)) 1109.65/291.56 - Complexity: n^2 1109.65/291.56 * Chain [79] with precondition: [V=V1,V>=1] 1109.65/291.56 - Upper bound: V1+9+nat(V6) 1109.65/291.56 - Complexity: n 1109.65/291.56 * Chain [78] with precondition: [V=1,V6=0,V2=0,V1>=1] 1109.65/291.56 - Upper bound: 8 1109.65/291.56 - Complexity: constant 1109.65/291.56 * Chain [77] with precondition: [V=1,V6=0,V1>=1,V2>=V1] 1109.65/291.56 - Upper bound: 2*V1+6 1109.65/291.56 - Complexity: n 1109.65/291.56 * Chain [76] with precondition: [V=1,V6=0,V1>=2,V2+1>=V1] 1109.65/291.56 - Upper bound: 2*V1+8 1109.65/291.56 - Complexity: n 1109.65/291.56 * Chain [75] with precondition: [V=1,V6=0,V2>=1,V1>=V2+1] 1109.65/291.56 - Upper bound: 2*V2+8 1109.65/291.56 - Complexity: n 1109.65/291.56 * Chain [74] with precondition: [V=1,V6=1,V1>=2,V2+1>=V1] 1109.65/291.56 - Upper bound: 2*V1+9 1109.65/291.56 - Complexity: n 1109.65/291.56 * Chain [73] with precondition: [V=1,V6>=1,V2>=V6,V1>=V2+1] 1109.65/291.56 - Upper bound: 4*V6+3*V2+9 1109.65/291.56 - Complexity: n 1109.65/291.56 * Chain [72] with precondition: [V=1,V2=0,V1=V6,V1>=1] 1109.65/291.56 - Upper bound: 8*V1+10 1109.65/291.56 - Complexity: n 1109.65/291.56 * Chain [71] with precondition: [V=1,V2=0,V1=V6+1,V1>=2] 1109.65/291.56 - Upper bound: 8*V1+10 1109.65/291.56 - Complexity: n 1109.65/291.56 * Chain [70] with precondition: [V=1,V2=0,V1>=1,V6>=V1+1] 1109.65/291.56 - Upper bound: 8*V6+10 1109.65/291.56 - Complexity: n 1109.65/291.56 * Chain [69] with precondition: [V=1,V2=0,V6>=1,V1>=V6+2] 1109.65/291.56 - Upper bound: 8*V6+10 1109.65/291.56 - Complexity: n 1109.65/291.56 * Chain [68] with precondition: [V=1,V2=1,V1+1=V6,V1>=1] 1109.65/291.56 - Upper bound: 10*V6+13 1109.65/291.56 - Complexity: n 1109.65/291.56 * Chain [67] with precondition: [V=1,V2=1,V1=V6,V1>=2] 1109.65/291.56 - Upper bound: 10*V6+13 1109.65/291.56 - Complexity: n 1109.65/291.56 * Chain [66] with precondition: [V=1,V2=1,V1=V6+1,V1>=3] 1109.65/291.56 - Upper bound: 5*V1+5*V6+21 1109.65/291.56 - Complexity: n 1109.65/291.56 * Chain [65] with precondition: [V=1,V2=1,V1>=1,V6>=V1+2] 1109.65/291.56 - Upper bound: 10*V6+13 1109.65/291.56 - Complexity: n 1109.65/291.56 * Chain [64] with precondition: [V=1,V2=1,V6>=2,V1>=V6+2] 1109.65/291.56 - Upper bound: 10*V6+15 1109.65/291.56 - Complexity: n 1109.65/291.56 * Chain [63] with precondition: [V=1,V1=V6,V1>=1,V2>=V1] 1109.65/291.56 - Upper bound: 3*V1+3*V6+8 1109.65/291.56 - Complexity: n 1109.65/291.56 * Chain [62] with precondition: [V=1,V1=V6,V2>=2,V1>=V2+1] 1109.65/291.56 - Upper bound: 4*V6-4*V2+(4*V1-4*V2+(7*V2+10+(V1-V2)*V2+(V6-V2)*V2)) 1109.65/291.56 - Complexity: n^2 1109.65/291.56 * Chain [61] with precondition: [V=1,V1=V6+1,V2>=2,V1>=V2+2] 1109.65/291.56 - Upper bound: 8*V6-8*V2+(7*V2+10+(V6-V2)*(2*V2)+(4*V2+4)) 1109.65/291.56 - Complexity: n^2 1109.65/291.56 * Chain [60] with precondition: [V=1,V6=V1+V2,V1>=1,V6>=V1+2] 1109.65/291.56 - Upper bound: 4*V6-4*V2+(4*V1+10+V2*V1+3*V2+(V6-V2)*V2) 1109.65/291.56 - Complexity: n^2 1109.65/291.56 * Chain [59] with precondition: [V=1,V6+1=V1+V2,V1>=2,V6>=V1+1] 1109.65/291.56 - Upper bound: 4*V6-4*V2+(4*V1+10+V2*V1+3*V2+(V6-V2)*V2) 1109.65/291.56 - Complexity: n^2 1109.65/291.56 * Chain [58] with precondition: [V=1,V1>=1,V2>=2,V6>=V1+V2+1] 1109.65/291.56 - Upper bound: -8*V1+8*V6-8*V2+(8*V1+10+2*V1*V2+3*V2+(-V1+V6-V2)*(2*V2)) 1109.65/291.56 - Complexity: n^2 1109.65/291.56 * Chain [57] with precondition: [V=1,V1>=1,V6>=V1+1,V2>=V6] 1109.65/291.56 - Upper bound: 8*V1+2*V6+8 1109.65/291.56 - Complexity: n 1109.65/291.56 * Chain [56] with precondition: [V=1,V6>=1,V2>=V1,V1>=V6+1] 1109.65/291.56 - Upper bound: 2*V1+3*V6+6 1109.65/291.56 - Complexity: n 1109.65/291.56 * Chain [55] with precondition: [V=1,V6>=2,V2+1>=V1,V1>=V6+1] 1109.65/291.56 - Upper bound: 2*V1+3*V6+8 1109.65/291.56 - Complexity: n 1109.65/291.56 * Chain [54] with precondition: [V=1,V2>=2,V1>=V6+2,V6>=V2+1] 1109.65/291.56 - Upper bound: 8*V6-8*V2+(7*V2+10+(V6-V2)*(2*V2)) 1109.65/291.56 - Complexity: n^2 1109.65/291.56 * Chain [53] with precondition: [V=1,V6>=V1+1,V6>=V2+1,V1+V2>=V6+2] 1109.65/291.56 - Upper bound: 8*V6-8*V2+(8*V1-8*V6+8*V2+(3*V2+10+(V6-V2)*(2*V2))) 1109.65/291.56 - Complexity: n^2 1109.65/291.56 1109.65/291.56 ### Maximum cost of start(V,V1,V6,V2): max([max([nat(V2)+1+max([nat(V6)*4,nat(V6-V2)*nat(V2)+1+nat(V6-V2)*4+max([nat(V1-V2)*nat(V2)+nat(V2)*4+nat(V1-V2)*4,nat(V6-V2)*nat(V2)+nat(V6-V2)*4+max([nat(V1-V6+V2)*8,nat(V2+1)*4+nat(V2)*4])])])+nat(V2)*2,nat(V6)*6+1+(nat(V6)*2+5)+(nat(V6)*2+1)])+2,nat(V1)+max([nat(V1)+max([max([3,nat(V6)*3+max([2,2*V+4+nat(V6)*5])]),nat(V1)+2+max([nat(V6)*3,nat(V1)+max([nat(V1)+max([nat(V1)*3+max([max([2,nat(V6)*2,nat(-V1+V6)*8+2,nat(V1)*2*nat(V2)+2+nat(V2)*3+nat(V2)*2*nat(-V1+V6-V2)+nat(-V1+V6-V2)*8]),nat(V1)*2+5+max([nat(-V1+V6)*10,nat(V1)*6+4+nat(V6)*14+nat(V2)*9+nat(V6-V2)*nat(V2)+nat(V6-V2)*4])]),nat(V6)*5+13]),nat(V2)*nat(V1)+2+nat(V2)*3+nat(V6-V2)*nat(V2)+nat(V6-V2)*4])])]),nat(V6)+3])])+6 1109.65/291.56 Asymptotic class: n^2 1109.65/291.56 * Total analysis performed in 1595 ms. 1109.65/291.56 1109.65/291.56 1109.65/291.56 ---------------------------------------- 1109.65/291.56 1109.65/291.56 (10) 1109.65/291.56 BOUNDS(1, n^2) 1109.65/291.56 1109.65/291.56 ---------------------------------------- 1109.65/291.56 1109.65/291.56 (11) RenamingProof (BOTH BOUNDS(ID, ID)) 1109.65/291.56 Renamed function symbols to avoid clashes with predefined symbol. 1109.65/291.56 ---------------------------------------- 1109.65/291.56 1109.65/291.56 (12) 1109.65/291.56 Obligation: 1109.65/291.56 The Runtime Complexity (innermost) of the given CpxTRS could be proven to be BOUNDS(n^1, INF). 1109.65/291.56 1109.65/291.56 1109.65/291.56 The TRS R consists of the following rules: 1109.65/291.56 1109.65/291.56 cond1(true, x, y, z) -> cond2(gr(y, z), x, y, z) 1109.65/291.56 cond2(true, x, y, z) -> cond2(gr(y, z), p(x), p(y), z) 1109.65/291.56 cond2(false, x, y, z) -> cond1(and(eq(x, y), gr(x, z)), x, y, z) 1109.65/291.56 gr(0', x) -> false 1109.65/291.56 gr(s(x), 0') -> true 1109.65/291.56 gr(s(x), s(y)) -> gr(x, y) 1109.65/291.56 p(0') -> 0' 1109.65/291.56 p(s(x)) -> x 1109.65/291.56 eq(0', 0') -> true 1109.65/291.56 eq(s(x), 0') -> false 1109.65/291.56 eq(0', s(x)) -> false 1109.65/291.56 eq(s(x), s(y)) -> eq(x, y) 1109.65/291.56 and(true, true) -> true 1109.65/291.56 and(false, x) -> false 1109.65/291.56 and(x, false) -> false 1109.65/291.56 1109.65/291.56 S is empty. 1109.65/291.56 Rewrite Strategy: INNERMOST 1109.65/291.56 ---------------------------------------- 1109.65/291.56 1109.65/291.56 (13) TypeInferenceProof (BOTH BOUNDS(ID, ID)) 1109.65/291.56 Infered types. 1109.65/291.56 ---------------------------------------- 1109.65/291.56 1109.65/291.56 (14) 1109.65/291.56 Obligation: 1109.65/291.56 Innermost TRS: 1109.65/291.56 Rules: 1109.65/291.56 cond1(true, x, y, z) -> cond2(gr(y, z), x, y, z) 1109.65/291.56 cond2(true, x, y, z) -> cond2(gr(y, z), p(x), p(y), z) 1109.65/291.56 cond2(false, x, y, z) -> cond1(and(eq(x, y), gr(x, z)), x, y, z) 1109.65/291.56 gr(0', x) -> false 1109.65/291.56 gr(s(x), 0') -> true 1109.65/291.56 gr(s(x), s(y)) -> gr(x, y) 1109.65/291.56 p(0') -> 0' 1109.65/291.56 p(s(x)) -> x 1109.65/291.56 eq(0', 0') -> true 1109.65/291.56 eq(s(x), 0') -> false 1109.65/291.56 eq(0', s(x)) -> false 1109.65/291.56 eq(s(x), s(y)) -> eq(x, y) 1109.65/291.56 and(true, true) -> true 1109.65/291.56 and(false, x) -> false 1109.65/291.56 and(x, false) -> false 1109.65/291.56 1109.65/291.56 Types: 1109.65/291.56 cond1 :: true:false -> 0':s -> 0':s -> 0':s -> cond1:cond2 1109.65/291.56 true :: true:false 1109.65/291.56 cond2 :: true:false -> 0':s -> 0':s -> 0':s -> cond1:cond2 1109.65/291.56 gr :: 0':s -> 0':s -> true:false 1109.65/291.56 p :: 0':s -> 0':s 1109.65/291.56 false :: true:false 1109.65/291.56 and :: true:false -> true:false -> true:false 1109.65/291.56 eq :: 0':s -> 0':s -> true:false 1109.65/291.56 0' :: 0':s 1109.65/291.56 s :: 0':s -> 0':s 1109.65/291.56 hole_cond1:cond21_0 :: cond1:cond2 1109.65/291.56 hole_true:false2_0 :: true:false 1109.65/291.56 hole_0':s3_0 :: 0':s 1109.65/291.57 gen_0':s4_0 :: Nat -> 0':s 1109.65/291.57 1109.65/291.57 ---------------------------------------- 1109.65/291.57 1109.65/291.57 (15) OrderProof (LOWER BOUND(ID)) 1109.65/291.57 Heuristically decided to analyse the following defined symbols: 1109.65/291.57 cond1, cond2, gr, eq 1109.65/291.57 1109.65/291.57 They will be analysed ascendingly in the following order: 1109.65/291.57 cond1 = cond2 1109.65/291.57 gr < cond1 1109.65/291.57 gr < cond2 1109.65/291.57 eq < cond2 1109.65/291.57 1109.65/291.57 ---------------------------------------- 1109.65/291.57 1109.65/291.57 (16) 1109.65/291.57 Obligation: 1109.65/291.57 Innermost TRS: 1109.65/291.57 Rules: 1109.65/291.57 cond1(true, x, y, z) -> cond2(gr(y, z), x, y, z) 1109.65/291.57 cond2(true, x, y, z) -> cond2(gr(y, z), p(x), p(y), z) 1109.65/291.57 cond2(false, x, y, z) -> cond1(and(eq(x, y), gr(x, z)), x, y, z) 1109.65/291.57 gr(0', x) -> false 1109.65/291.57 gr(s(x), 0') -> true 1109.65/291.57 gr(s(x), s(y)) -> gr(x, y) 1109.65/291.57 p(0') -> 0' 1109.65/291.57 p(s(x)) -> x 1109.65/291.57 eq(0', 0') -> true 1109.65/291.57 eq(s(x), 0') -> false 1109.65/291.57 eq(0', s(x)) -> false 1109.65/291.57 eq(s(x), s(y)) -> eq(x, y) 1109.65/291.57 and(true, true) -> true 1109.65/291.57 and(false, x) -> false 1109.65/291.57 and(x, false) -> false 1109.65/291.57 1109.65/291.57 Types: 1109.65/291.57 cond1 :: true:false -> 0':s -> 0':s -> 0':s -> cond1:cond2 1109.65/291.57 true :: true:false 1109.65/291.57 cond2 :: true:false -> 0':s -> 0':s -> 0':s -> cond1:cond2 1109.65/291.57 gr :: 0':s -> 0':s -> true:false 1109.65/291.57 p :: 0':s -> 0':s 1109.65/291.57 false :: true:false 1109.65/291.57 and :: true:false -> true:false -> true:false 1109.65/291.57 eq :: 0':s -> 0':s -> true:false 1109.65/291.57 0' :: 0':s 1109.65/291.57 s :: 0':s -> 0':s 1109.65/291.57 hole_cond1:cond21_0 :: cond1:cond2 1109.65/291.57 hole_true:false2_0 :: true:false 1109.65/291.57 hole_0':s3_0 :: 0':s 1109.65/291.57 gen_0':s4_0 :: Nat -> 0':s 1109.65/291.57 1109.65/291.57 1109.65/291.57 Generator Equations: 1109.65/291.57 gen_0':s4_0(0) <=> 0' 1109.65/291.57 gen_0':s4_0(+(x, 1)) <=> s(gen_0':s4_0(x)) 1109.65/291.57 1109.65/291.57 1109.65/291.57 The following defined symbols remain to be analysed: 1109.65/291.57 gr, cond1, cond2, eq 1109.65/291.57 1109.65/291.57 They will be analysed ascendingly in the following order: 1109.65/291.57 cond1 = cond2 1109.65/291.57 gr < cond1 1109.65/291.57 gr < cond2 1109.65/291.57 eq < cond2 1109.65/291.57 1109.65/291.57 ---------------------------------------- 1109.65/291.57 1109.65/291.57 (17) RewriteLemmaProof (LOWER BOUND(ID)) 1109.65/291.57 Proved the following rewrite lemma: 1109.65/291.57 gr(gen_0':s4_0(n6_0), gen_0':s4_0(n6_0)) -> false, rt in Omega(1 + n6_0) 1109.65/291.57 1109.65/291.57 Induction Base: 1109.65/291.57 gr(gen_0':s4_0(0), gen_0':s4_0(0)) ->_R^Omega(1) 1109.65/291.57 false 1109.65/291.57 1109.65/291.57 Induction Step: 1109.65/291.57 gr(gen_0':s4_0(+(n6_0, 1)), gen_0':s4_0(+(n6_0, 1))) ->_R^Omega(1) 1109.65/291.57 gr(gen_0':s4_0(n6_0), gen_0':s4_0(n6_0)) ->_IH 1109.65/291.57 false 1109.65/291.57 1109.65/291.57 We have rt in Omega(n^1) and sz in O(n). Thus, we have irc_R in Omega(n). 1109.65/291.57 ---------------------------------------- 1109.65/291.57 1109.65/291.57 (18) 1109.65/291.57 Complex Obligation (BEST) 1109.65/291.57 1109.65/291.57 ---------------------------------------- 1109.65/291.57 1109.65/291.57 (19) 1109.65/291.57 Obligation: 1109.65/291.57 Proved the lower bound n^1 for the following obligation: 1109.65/291.57 1109.65/291.57 Innermost TRS: 1109.65/291.57 Rules: 1109.65/291.57 cond1(true, x, y, z) -> cond2(gr(y, z), x, y, z) 1109.65/291.57 cond2(true, x, y, z) -> cond2(gr(y, z), p(x), p(y), z) 1109.65/291.57 cond2(false, x, y, z) -> cond1(and(eq(x, y), gr(x, z)), x, y, z) 1109.65/291.57 gr(0', x) -> false 1109.65/291.57 gr(s(x), 0') -> true 1109.65/291.57 gr(s(x), s(y)) -> gr(x, y) 1109.65/291.57 p(0') -> 0' 1109.65/291.57 p(s(x)) -> x 1109.65/291.57 eq(0', 0') -> true 1109.65/291.57 eq(s(x), 0') -> false 1109.65/291.57 eq(0', s(x)) -> false 1109.65/291.57 eq(s(x), s(y)) -> eq(x, y) 1109.65/291.57 and(true, true) -> true 1109.65/291.57 and(false, x) -> false 1109.65/291.57 and(x, false) -> false 1109.65/291.57 1109.65/291.57 Types: 1109.65/291.57 cond1 :: true:false -> 0':s -> 0':s -> 0':s -> cond1:cond2 1109.65/291.57 true :: true:false 1109.65/291.57 cond2 :: true:false -> 0':s -> 0':s -> 0':s -> cond1:cond2 1109.65/291.57 gr :: 0':s -> 0':s -> true:false 1109.65/291.57 p :: 0':s -> 0':s 1109.65/291.57 false :: true:false 1109.65/291.57 and :: true:false -> true:false -> true:false 1109.65/291.57 eq :: 0':s -> 0':s -> true:false 1109.65/291.57 0' :: 0':s 1109.65/291.57 s :: 0':s -> 0':s 1109.65/291.57 hole_cond1:cond21_0 :: cond1:cond2 1109.65/291.57 hole_true:false2_0 :: true:false 1109.65/291.57 hole_0':s3_0 :: 0':s 1109.65/291.57 gen_0':s4_0 :: Nat -> 0':s 1109.65/291.57 1109.65/291.57 1109.65/291.57 Generator Equations: 1109.65/291.57 gen_0':s4_0(0) <=> 0' 1109.65/291.57 gen_0':s4_0(+(x, 1)) <=> s(gen_0':s4_0(x)) 1109.65/291.57 1109.65/291.57 1109.65/291.57 The following defined symbols remain to be analysed: 1109.65/291.57 gr, cond1, cond2, eq 1109.65/291.57 1109.65/291.57 They will be analysed ascendingly in the following order: 1109.65/291.57 cond1 = cond2 1109.65/291.57 gr < cond1 1109.65/291.57 gr < cond2 1109.65/291.57 eq < cond2 1109.65/291.57 1109.65/291.57 ---------------------------------------- 1109.65/291.57 1109.65/291.57 (20) LowerBoundPropagationProof (FINISHED) 1109.65/291.57 Propagated lower bound. 1109.65/291.57 ---------------------------------------- 1109.65/291.57 1109.65/291.57 (21) 1109.65/291.57 BOUNDS(n^1, INF) 1109.65/291.57 1109.65/291.57 ---------------------------------------- 1109.65/291.57 1109.65/291.57 (22) 1109.65/291.57 Obligation: 1109.65/291.57 Innermost TRS: 1109.65/291.57 Rules: 1109.65/291.57 cond1(true, x, y, z) -> cond2(gr(y, z), x, y, z) 1109.65/291.57 cond2(true, x, y, z) -> cond2(gr(y, z), p(x), p(y), z) 1109.65/291.57 cond2(false, x, y, z) -> cond1(and(eq(x, y), gr(x, z)), x, y, z) 1109.65/291.57 gr(0', x) -> false 1109.65/291.57 gr(s(x), 0') -> true 1109.65/291.57 gr(s(x), s(y)) -> gr(x, y) 1109.65/291.57 p(0') -> 0' 1109.65/291.57 p(s(x)) -> x 1109.65/291.57 eq(0', 0') -> true 1109.65/291.57 eq(s(x), 0') -> false 1109.65/291.57 eq(0', s(x)) -> false 1109.65/291.57 eq(s(x), s(y)) -> eq(x, y) 1109.65/291.57 and(true, true) -> true 1109.65/291.57 and(false, x) -> false 1109.65/291.57 and(x, false) -> false 1109.65/291.57 1109.65/291.57 Types: 1109.65/291.57 cond1 :: true:false -> 0':s -> 0':s -> 0':s -> cond1:cond2 1109.65/291.57 true :: true:false 1109.65/291.57 cond2 :: true:false -> 0':s -> 0':s -> 0':s -> cond1:cond2 1109.65/291.57 gr :: 0':s -> 0':s -> true:false 1109.65/291.57 p :: 0':s -> 0':s 1109.65/291.57 false :: true:false 1109.65/291.57 and :: true:false -> true:false -> true:false 1109.65/291.57 eq :: 0':s -> 0':s -> true:false 1109.65/291.57 0' :: 0':s 1109.65/291.57 s :: 0':s -> 0':s 1109.65/291.57 hole_cond1:cond21_0 :: cond1:cond2 1109.65/291.57 hole_true:false2_0 :: true:false 1109.65/291.57 hole_0':s3_0 :: 0':s 1109.65/291.57 gen_0':s4_0 :: Nat -> 0':s 1109.65/291.57 1109.65/291.57 1109.65/291.57 Lemmas: 1109.65/291.57 gr(gen_0':s4_0(n6_0), gen_0':s4_0(n6_0)) -> false, rt in Omega(1 + n6_0) 1109.65/291.57 1109.65/291.57 1109.65/291.57 Generator Equations: 1109.65/291.57 gen_0':s4_0(0) <=> 0' 1109.65/291.57 gen_0':s4_0(+(x, 1)) <=> s(gen_0':s4_0(x)) 1109.65/291.57 1109.65/291.57 1109.65/291.57 The following defined symbols remain to be analysed: 1109.65/291.57 eq, cond1, cond2 1109.65/291.57 1109.65/291.57 They will be analysed ascendingly in the following order: 1109.65/291.57 cond1 = cond2 1109.65/291.57 eq < cond2 1109.65/291.57 1109.65/291.57 ---------------------------------------- 1109.65/291.57 1109.65/291.57 (23) RewriteLemmaProof (LOWER BOUND(ID)) 1109.65/291.57 Proved the following rewrite lemma: 1109.65/291.57 eq(gen_0':s4_0(n295_0), gen_0':s4_0(n295_0)) -> true, rt in Omega(1 + n295_0) 1109.65/291.57 1109.65/291.57 Induction Base: 1109.65/291.57 eq(gen_0':s4_0(0), gen_0':s4_0(0)) ->_R^Omega(1) 1109.65/291.57 true 1109.65/291.57 1109.65/291.57 Induction Step: 1109.65/291.57 eq(gen_0':s4_0(+(n295_0, 1)), gen_0':s4_0(+(n295_0, 1))) ->_R^Omega(1) 1109.65/291.57 eq(gen_0':s4_0(n295_0), gen_0':s4_0(n295_0)) ->_IH 1109.65/291.57 true 1109.65/291.57 1109.65/291.57 We have rt in Omega(n^1) and sz in O(n). Thus, we have irc_R in Omega(n). 1109.65/291.57 ---------------------------------------- 1109.65/291.57 1109.65/291.57 (24) 1109.65/291.57 Obligation: 1109.65/291.57 Innermost TRS: 1109.65/291.57 Rules: 1109.65/291.57 cond1(true, x, y, z) -> cond2(gr(y, z), x, y, z) 1109.65/291.57 cond2(true, x, y, z) -> cond2(gr(y, z), p(x), p(y), z) 1109.65/291.57 cond2(false, x, y, z) -> cond1(and(eq(x, y), gr(x, z)), x, y, z) 1109.65/291.57 gr(0', x) -> false 1109.65/291.57 gr(s(x), 0') -> true 1109.65/291.57 gr(s(x), s(y)) -> gr(x, y) 1109.65/291.57 p(0') -> 0' 1109.65/291.57 p(s(x)) -> x 1109.65/291.57 eq(0', 0') -> true 1109.65/291.57 eq(s(x), 0') -> false 1109.65/291.57 eq(0', s(x)) -> false 1109.65/291.57 eq(s(x), s(y)) -> eq(x, y) 1109.65/291.57 and(true, true) -> true 1109.65/291.57 and(false, x) -> false 1109.65/291.57 and(x, false) -> false 1109.65/291.57 1109.65/291.57 Types: 1109.65/291.57 cond1 :: true:false -> 0':s -> 0':s -> 0':s -> cond1:cond2 1109.65/291.57 true :: true:false 1109.65/291.57 cond2 :: true:false -> 0':s -> 0':s -> 0':s -> cond1:cond2 1109.65/291.57 gr :: 0':s -> 0':s -> true:false 1109.65/291.57 p :: 0':s -> 0':s 1109.65/291.57 false :: true:false 1109.65/291.57 and :: true:false -> true:false -> true:false 1109.65/291.57 eq :: 0':s -> 0':s -> true:false 1109.65/291.57 0' :: 0':s 1109.65/291.57 s :: 0':s -> 0':s 1109.65/291.57 hole_cond1:cond21_0 :: cond1:cond2 1109.65/291.57 hole_true:false2_0 :: true:false 1109.65/291.57 hole_0':s3_0 :: 0':s 1109.65/291.57 gen_0':s4_0 :: Nat -> 0':s 1109.65/291.57 1109.65/291.57 1109.65/291.57 Lemmas: 1109.65/291.57 gr(gen_0':s4_0(n6_0), gen_0':s4_0(n6_0)) -> false, rt in Omega(1 + n6_0) 1109.65/291.57 eq(gen_0':s4_0(n295_0), gen_0':s4_0(n295_0)) -> true, rt in Omega(1 + n295_0) 1109.65/291.57 1109.65/291.57 1109.65/291.57 Generator Equations: 1109.65/291.57 gen_0':s4_0(0) <=> 0' 1109.65/291.57 gen_0':s4_0(+(x, 1)) <=> s(gen_0':s4_0(x)) 1109.65/291.57 1109.65/291.57 1109.65/291.57 The following defined symbols remain to be analysed: 1109.65/291.57 cond2, cond1 1109.65/291.57 1109.65/291.57 They will be analysed ascendingly in the following order: 1109.65/291.57 cond1 = cond2 1110.11/291.63 EOF