5.64/2.65 WORST_CASE(Omega(n^2), O(n^2)) 5.64/2.66 proof of /export/starexec/sandbox/benchmark/theBenchmark.koat 5.64/2.66 # AProVE Commit ID: 48fb2092695e11cc9f56e44b17a92a5f88ffb256 marcel 20180622 unpublished dirty 5.64/2.66 5.64/2.66 5.64/2.66 The runtime complexity of the given CpxIntTrs could be proven to be BOUNDS(n^2, n^2). 5.64/2.66 5.64/2.66 (0) CpxIntTrs 5.64/2.66 (1) Koat Proof [FINISHED, 300 ms] 5.64/2.66 (2) BOUNDS(1, n^2) 5.64/2.66 (3) Loat Proof [FINISHED, 893 ms] 5.64/2.66 (4) BOUNDS(n^2, INF) 5.64/2.66 5.64/2.66 5.64/2.66 ---------------------------------------- 5.64/2.66 5.64/2.66 (0) 5.64/2.66 Obligation: 5.64/2.66 Complexity Int TRS consisting of the following rules: 5.64/2.66 eval_cousot9_start(v__0, v_N, v_i_0, v_j) -> Com_1(eval_cousot9_bb0_in(v__0, v_N, v_i_0, v_j)) :|: TRUE 5.64/2.66 eval_cousot9_bb0_in(v__0, v_N, v_i_0, v_j) -> Com_1(eval_cousot9_0(v__0, v_N, v_i_0, v_j)) :|: TRUE 5.64/2.66 eval_cousot9_0(v__0, v_N, v_i_0, v_j) -> Com_1(eval_cousot9_1(v__0, v_N, v_i_0, v_j)) :|: TRUE 5.64/2.66 eval_cousot9_1(v__0, v_N, v_i_0, v_j) -> Com_1(eval_cousot9_2(v__0, v_N, v_i_0, v_j)) :|: TRUE 5.64/2.66 eval_cousot9_2(v__0, v_N, v_i_0, v_j) -> Com_1(eval_cousot9_3(v__0, v_N, v_i_0, v_j)) :|: TRUE 5.64/2.66 eval_cousot9_3(v__0, v_N, v_i_0, v_j) -> Com_1(eval_cousot9_4(v__0, v_N, v_i_0, v_j)) :|: TRUE 5.64/2.66 eval_cousot9_4(v__0, v_N, v_i_0, v_j) -> Com_1(eval_cousot9_5(v__0, v_N, v_i_0, v_j)) :|: TRUE 5.64/2.66 eval_cousot9_5(v__0, v_N, v_i_0, v_j) -> Com_1(eval_cousot9_6(v__0, v_N, v_i_0, v_j)) :|: TRUE 5.64/2.66 eval_cousot9_6(v__0, v_N, v_i_0, v_j) -> Com_1(eval_cousot9_bb1_in(v_j, v_N, v_N, v_j)) :|: TRUE 5.64/2.66 eval_cousot9_bb1_in(v__0, v_N, v_i_0, v_j) -> Com_1(eval_cousot9_bb2_in(v__0, v_N, v_i_0, v_j)) :|: v_i_0 > 0 5.64/2.66 eval_cousot9_bb1_in(v__0, v_N, v_i_0, v_j) -> Com_1(eval_cousot9_bb3_in(v__0, v_N, v_i_0, v_j)) :|: v_i_0 <= 0 5.64/2.66 eval_cousot9_bb2_in(v__0, v_N, v_i_0, v_j) -> Com_1(eval_cousot9_bb1_in(v__0 - 1, v_N, v_i_0, v_j)) :|: v__0 > 0 5.64/2.66 eval_cousot9_bb2_in(v__0, v_N, v_i_0, v_j) -> Com_1(eval_cousot9_bb1_in(v_N, v_N, v_i_0, v_j)) :|: v__0 > 0 && v__0 <= 0 5.64/2.66 eval_cousot9_bb2_in(v__0, v_N, v_i_0, v_j) -> Com_1(eval_cousot9_bb1_in(v__0 - 1, v_N, v_i_0 - 1, v_j)) :|: v__0 <= 0 && v__0 > 0 5.64/2.66 eval_cousot9_bb2_in(v__0, v_N, v_i_0, v_j) -> Com_1(eval_cousot9_bb1_in(v_N, v_N, v_i_0 - 1, v_j)) :|: v__0 <= 0 5.64/2.66 eval_cousot9_bb3_in(v__0, v_N, v_i_0, v_j) -> Com_1(eval_cousot9_stop(v__0, v_N, v_i_0, v_j)) :|: TRUE 5.64/2.66 5.64/2.66 The start-symbols are:[eval_cousot9_start_4] 5.64/2.66 5.64/2.66 5.64/2.66 ---------------------------------------- 5.64/2.66 5.64/2.66 (1) Koat Proof (FINISHED) 5.64/2.66 YES(?, 2*ar_3 + 2*ar_3^2 + 2*ar_1 + 14) 5.64/2.66 5.64/2.66 5.64/2.66 5.64/2.66 Initial complexity problem: 5.64/2.66 5.64/2.66 1: T: 5.64/2.66 5.64/2.66 (Comp: ?, Cost: 1) evalcousot9start(ar_0, ar_1, ar_2, ar_3) -> Com_1(evalcousot9bb0in(ar_0, ar_1, ar_2, ar_3)) 5.64/2.66 5.64/2.66 (Comp: ?, Cost: 1) evalcousot9bb0in(ar_0, ar_1, ar_2, ar_3) -> Com_1(evalcousot90(ar_0, ar_1, ar_2, ar_3)) 5.64/2.66 5.64/2.66 (Comp: ?, Cost: 1) evalcousot90(ar_0, ar_1, ar_2, ar_3) -> Com_1(evalcousot91(ar_0, ar_1, ar_2, ar_3)) 5.64/2.66 5.64/2.66 (Comp: ?, Cost: 1) evalcousot91(ar_0, ar_1, ar_2, ar_3) -> Com_1(evalcousot92(ar_0, ar_1, ar_2, ar_3)) 5.64/2.66 5.64/2.66 (Comp: ?, Cost: 1) evalcousot92(ar_0, ar_1, ar_2, ar_3) -> Com_1(evalcousot93(ar_0, ar_1, ar_2, ar_3)) 5.64/2.66 5.64/2.66 (Comp: ?, Cost: 1) evalcousot93(ar_0, ar_1, ar_2, ar_3) -> Com_1(evalcousot94(ar_0, ar_1, ar_2, ar_3)) 5.64/2.66 5.64/2.66 (Comp: ?, Cost: 1) evalcousot94(ar_0, ar_1, ar_2, ar_3) -> Com_1(evalcousot95(ar_0, ar_1, ar_2, ar_3)) 5.64/2.66 5.64/2.66 (Comp: ?, Cost: 1) evalcousot95(ar_0, ar_1, ar_2, ar_3) -> Com_1(evalcousot96(ar_0, ar_1, ar_2, ar_3)) 5.64/2.66 5.64/2.66 (Comp: ?, Cost: 1) evalcousot96(ar_0, ar_1, ar_2, ar_3) -> Com_1(evalcousot9bb1in(ar_1, ar_1, ar_3, ar_3)) 5.64/2.66 5.64/2.66 (Comp: ?, Cost: 1) evalcousot9bb1in(ar_0, ar_1, ar_2, ar_3) -> Com_1(evalcousot9bb2in(ar_0, ar_1, ar_2, ar_3)) [ ar_2 >= 1 ] 5.64/2.66 5.64/2.66 (Comp: ?, Cost: 1) evalcousot9bb1in(ar_0, ar_1, ar_2, ar_3) -> Com_1(evalcousot9bb3in(ar_0, ar_1, ar_2, ar_3)) [ 0 >= ar_2 ] 5.64/2.66 5.64/2.66 (Comp: ?, Cost: 1) evalcousot9bb2in(ar_0, ar_1, ar_2, ar_3) -> Com_1(evalcousot9bb1in(ar_0 - 1, ar_1, ar_2, ar_3)) [ ar_0 >= 1 ] 5.64/2.66 5.64/2.66 (Comp: ?, Cost: 1) evalcousot9bb2in(ar_0, ar_1, ar_2, ar_3) -> Com_1(evalcousot9bb1in(ar_3, ar_1, ar_2, ar_3)) [ ar_0 >= 1 /\ 0 >= ar_0 ] 5.64/2.66 5.64/2.66 (Comp: ?, Cost: 1) evalcousot9bb2in(ar_0, ar_1, ar_2, ar_3) -> Com_1(evalcousot9bb1in(ar_0 - 1, ar_1, ar_2 - 1, ar_3)) [ 0 >= ar_0 /\ ar_0 >= 1 ] 5.64/2.66 5.64/2.66 (Comp: ?, Cost: 1) evalcousot9bb2in(ar_0, ar_1, ar_2, ar_3) -> Com_1(evalcousot9bb1in(ar_3, ar_1, ar_2 - 1, ar_3)) [ 0 >= ar_0 ] 5.64/2.66 5.64/2.66 (Comp: ?, Cost: 1) evalcousot9bb3in(ar_0, ar_1, ar_2, ar_3) -> Com_1(evalcousot9stop(ar_0, ar_1, ar_2, ar_3)) 5.64/2.66 5.64/2.66 (Comp: 1, Cost: 0) koat_start(ar_0, ar_1, ar_2, ar_3) -> Com_1(evalcousot9start(ar_0, ar_1, ar_2, ar_3)) [ 0 <= 0 ] 5.64/2.66 5.64/2.66 start location: koat_start 5.64/2.66 5.64/2.66 leaf cost: 0 5.64/2.66 5.64/2.66 5.64/2.66 5.64/2.66 Testing for reachability in the complexity graph removes the following transitions from problem 1: 5.64/2.66 5.64/2.66 evalcousot9bb2in(ar_0, ar_1, ar_2, ar_3) -> Com_1(evalcousot9bb1in(ar_3, ar_1, ar_2, ar_3)) [ ar_0 >= 1 /\ 0 >= ar_0 ] 5.64/2.66 5.64/2.66 evalcousot9bb2in(ar_0, ar_1, ar_2, ar_3) -> Com_1(evalcousot9bb1in(ar_0 - 1, ar_1, ar_2 - 1, ar_3)) [ 0 >= ar_0 /\ ar_0 >= 1 ] 5.64/2.66 5.64/2.66 We thus obtain the following problem: 5.64/2.66 5.64/2.66 2: T: 5.64/2.66 5.64/2.66 (Comp: ?, Cost: 1) evalcousot9bb3in(ar_0, ar_1, ar_2, ar_3) -> Com_1(evalcousot9stop(ar_0, ar_1, ar_2, ar_3)) 5.64/2.66 5.64/2.66 (Comp: ?, Cost: 1) evalcousot9bb2in(ar_0, ar_1, ar_2, ar_3) -> Com_1(evalcousot9bb1in(ar_3, ar_1, ar_2 - 1, ar_3)) [ 0 >= ar_0 ] 5.64/2.66 5.64/2.66 (Comp: ?, Cost: 1) evalcousot9bb2in(ar_0, ar_1, ar_2, ar_3) -> Com_1(evalcousot9bb1in(ar_0 - 1, ar_1, ar_2, ar_3)) [ ar_0 >= 1 ] 5.64/2.66 5.64/2.66 (Comp: ?, Cost: 1) evalcousot9bb1in(ar_0, ar_1, ar_2, ar_3) -> Com_1(evalcousot9bb3in(ar_0, ar_1, ar_2, ar_3)) [ 0 >= ar_2 ] 5.64/2.66 5.64/2.66 (Comp: ?, Cost: 1) evalcousot9bb1in(ar_0, ar_1, ar_2, ar_3) -> Com_1(evalcousot9bb2in(ar_0, ar_1, ar_2, ar_3)) [ ar_2 >= 1 ] 5.64/2.66 5.64/2.66 (Comp: ?, Cost: 1) evalcousot96(ar_0, ar_1, ar_2, ar_3) -> Com_1(evalcousot9bb1in(ar_1, ar_1, ar_3, ar_3)) 5.64/2.66 5.64/2.66 (Comp: ?, Cost: 1) evalcousot95(ar_0, ar_1, ar_2, ar_3) -> Com_1(evalcousot96(ar_0, ar_1, ar_2, ar_3)) 5.64/2.66 5.64/2.66 (Comp: ?, Cost: 1) evalcousot94(ar_0, ar_1, ar_2, ar_3) -> Com_1(evalcousot95(ar_0, ar_1, ar_2, ar_3)) 5.64/2.66 5.64/2.66 (Comp: ?, Cost: 1) evalcousot93(ar_0, ar_1, ar_2, ar_3) -> Com_1(evalcousot94(ar_0, ar_1, ar_2, ar_3)) 5.64/2.66 5.64/2.66 (Comp: ?, Cost: 1) evalcousot92(ar_0, ar_1, ar_2, ar_3) -> Com_1(evalcousot93(ar_0, ar_1, ar_2, ar_3)) 5.64/2.66 5.64/2.66 (Comp: ?, Cost: 1) evalcousot91(ar_0, ar_1, ar_2, ar_3) -> Com_1(evalcousot92(ar_0, ar_1, ar_2, ar_3)) 5.64/2.66 5.64/2.66 (Comp: ?, Cost: 1) evalcousot90(ar_0, ar_1, ar_2, ar_3) -> Com_1(evalcousot91(ar_0, ar_1, ar_2, ar_3)) 5.64/2.66 5.64/2.66 (Comp: ?, Cost: 1) evalcousot9bb0in(ar_0, ar_1, ar_2, ar_3) -> Com_1(evalcousot90(ar_0, ar_1, ar_2, ar_3)) 5.64/2.66 5.64/2.66 (Comp: ?, Cost: 1) evalcousot9start(ar_0, ar_1, ar_2, ar_3) -> Com_1(evalcousot9bb0in(ar_0, ar_1, ar_2, ar_3)) 5.64/2.66 5.64/2.66 (Comp: 1, Cost: 0) koat_start(ar_0, ar_1, ar_2, ar_3) -> Com_1(evalcousot9start(ar_0, ar_1, ar_2, ar_3)) [ 0 <= 0 ] 5.64/2.66 5.64/2.66 start location: koat_start 5.64/2.66 5.64/2.66 leaf cost: 0 5.64/2.66 5.64/2.66 5.64/2.66 5.64/2.66 Repeatedly propagating knowledge in problem 2 produces the following problem: 5.64/2.66 5.64/2.66 3: T: 5.64/2.66 5.64/2.66 (Comp: ?, Cost: 1) evalcousot9bb3in(ar_0, ar_1, ar_2, ar_3) -> Com_1(evalcousot9stop(ar_0, ar_1, ar_2, ar_3)) 5.64/2.66 5.64/2.66 (Comp: ?, Cost: 1) evalcousot9bb2in(ar_0, ar_1, ar_2, ar_3) -> Com_1(evalcousot9bb1in(ar_3, ar_1, ar_2 - 1, ar_3)) [ 0 >= ar_0 ] 5.64/2.66 5.64/2.66 (Comp: ?, Cost: 1) evalcousot9bb2in(ar_0, ar_1, ar_2, ar_3) -> Com_1(evalcousot9bb1in(ar_0 - 1, ar_1, ar_2, ar_3)) [ ar_0 >= 1 ] 5.64/2.66 5.64/2.66 (Comp: ?, Cost: 1) evalcousot9bb1in(ar_0, ar_1, ar_2, ar_3) -> Com_1(evalcousot9bb3in(ar_0, ar_1, ar_2, ar_3)) [ 0 >= ar_2 ] 5.64/2.66 5.64/2.66 (Comp: ?, Cost: 1) evalcousot9bb1in(ar_0, ar_1, ar_2, ar_3) -> Com_1(evalcousot9bb2in(ar_0, ar_1, ar_2, ar_3)) [ ar_2 >= 1 ] 5.64/2.66 5.64/2.66 (Comp: 1, Cost: 1) evalcousot96(ar_0, ar_1, ar_2, ar_3) -> Com_1(evalcousot9bb1in(ar_1, ar_1, ar_3, ar_3)) 5.64/2.66 5.64/2.66 (Comp: 1, Cost: 1) evalcousot95(ar_0, ar_1, ar_2, ar_3) -> Com_1(evalcousot96(ar_0, ar_1, ar_2, ar_3)) 5.64/2.66 5.64/2.66 (Comp: 1, Cost: 1) evalcousot94(ar_0, ar_1, ar_2, ar_3) -> Com_1(evalcousot95(ar_0, ar_1, ar_2, ar_3)) 5.64/2.66 5.64/2.66 (Comp: 1, Cost: 1) evalcousot93(ar_0, ar_1, ar_2, ar_3) -> Com_1(evalcousot94(ar_0, ar_1, ar_2, ar_3)) 5.64/2.66 5.64/2.66 (Comp: 1, Cost: 1) evalcousot92(ar_0, ar_1, ar_2, ar_3) -> Com_1(evalcousot93(ar_0, ar_1, ar_2, ar_3)) 5.64/2.66 5.64/2.66 (Comp: 1, Cost: 1) evalcousot91(ar_0, ar_1, ar_2, ar_3) -> Com_1(evalcousot92(ar_0, ar_1, ar_2, ar_3)) 5.64/2.66 5.64/2.66 (Comp: 1, Cost: 1) evalcousot90(ar_0, ar_1, ar_2, ar_3) -> Com_1(evalcousot91(ar_0, ar_1, ar_2, ar_3)) 5.64/2.66 5.64/2.66 (Comp: 1, Cost: 1) evalcousot9bb0in(ar_0, ar_1, ar_2, ar_3) -> Com_1(evalcousot90(ar_0, ar_1, ar_2, ar_3)) 5.64/2.66 5.64/2.66 (Comp: 1, Cost: 1) evalcousot9start(ar_0, ar_1, ar_2, ar_3) -> Com_1(evalcousot9bb0in(ar_0, ar_1, ar_2, ar_3)) 5.64/2.66 5.64/2.66 (Comp: 1, Cost: 0) koat_start(ar_0, ar_1, ar_2, ar_3) -> Com_1(evalcousot9start(ar_0, ar_1, ar_2, ar_3)) [ 0 <= 0 ] 5.64/2.66 5.64/2.66 start location: koat_start 5.64/2.66 5.64/2.66 leaf cost: 0 5.64/2.66 5.64/2.66 5.64/2.66 5.64/2.66 A polynomial rank function with 5.64/2.66 5.64/2.66 Pol(evalcousot9bb3in) = 1 5.64/2.66 5.64/2.66 Pol(evalcousot9stop) = 0 5.64/2.66 5.64/2.66 Pol(evalcousot9bb2in) = 2 5.64/2.66 5.64/2.66 Pol(evalcousot9bb1in) = 2 5.64/2.66 5.64/2.66 Pol(evalcousot96) = 2 5.64/2.66 5.64/2.66 Pol(evalcousot95) = 2 5.64/2.66 5.64/2.66 Pol(evalcousot94) = 2 5.64/2.66 5.64/2.66 Pol(evalcousot93) = 2 5.64/2.66 5.64/2.66 Pol(evalcousot92) = 2 5.64/2.66 5.64/2.66 Pol(evalcousot91) = 2 5.64/2.66 5.64/2.66 Pol(evalcousot90) = 2 5.64/2.66 5.64/2.66 Pol(evalcousot9bb0in) = 2 5.64/2.66 5.64/2.66 Pol(evalcousot9start) = 2 5.64/2.66 5.64/2.66 Pol(koat_start) = 2 5.64/2.66 5.64/2.66 orients all transitions weakly and the transitions 5.64/2.66 5.64/2.66 evalcousot9bb3in(ar_0, ar_1, ar_2, ar_3) -> Com_1(evalcousot9stop(ar_0, ar_1, ar_2, ar_3)) 5.64/2.66 5.64/2.66 evalcousot9bb1in(ar_0, ar_1, ar_2, ar_3) -> Com_1(evalcousot9bb3in(ar_0, ar_1, ar_2, ar_3)) [ 0 >= ar_2 ] 5.64/2.66 5.64/2.66 strictly and produces the following problem: 5.64/2.66 5.64/2.66 4: T: 5.64/2.66 5.64/2.66 (Comp: 2, Cost: 1) evalcousot9bb3in(ar_0, ar_1, ar_2, ar_3) -> Com_1(evalcousot9stop(ar_0, ar_1, ar_2, ar_3)) 5.64/2.66 5.64/2.66 (Comp: ?, Cost: 1) evalcousot9bb2in(ar_0, ar_1, ar_2, ar_3) -> Com_1(evalcousot9bb1in(ar_3, ar_1, ar_2 - 1, ar_3)) [ 0 >= ar_0 ] 5.64/2.66 5.64/2.66 (Comp: ?, Cost: 1) evalcousot9bb2in(ar_0, ar_1, ar_2, ar_3) -> Com_1(evalcousot9bb1in(ar_0 - 1, ar_1, ar_2, ar_3)) [ ar_0 >= 1 ] 5.64/2.66 5.64/2.66 (Comp: 2, Cost: 1) evalcousot9bb1in(ar_0, ar_1, ar_2, ar_3) -> Com_1(evalcousot9bb3in(ar_0, ar_1, ar_2, ar_3)) [ 0 >= ar_2 ] 5.64/2.66 5.64/2.66 (Comp: ?, Cost: 1) evalcousot9bb1in(ar_0, ar_1, ar_2, ar_3) -> Com_1(evalcousot9bb2in(ar_0, ar_1, ar_2, ar_3)) [ ar_2 >= 1 ] 5.64/2.66 5.64/2.66 (Comp: 1, Cost: 1) evalcousot96(ar_0, ar_1, ar_2, ar_3) -> Com_1(evalcousot9bb1in(ar_1, ar_1, ar_3, ar_3)) 5.64/2.66 5.64/2.66 (Comp: 1, Cost: 1) evalcousot95(ar_0, ar_1, ar_2, ar_3) -> Com_1(evalcousot96(ar_0, ar_1, ar_2, ar_3)) 5.64/2.66 5.64/2.66 (Comp: 1, Cost: 1) evalcousot94(ar_0, ar_1, ar_2, ar_3) -> Com_1(evalcousot95(ar_0, ar_1, ar_2, ar_3)) 5.64/2.66 5.64/2.66 (Comp: 1, Cost: 1) evalcousot93(ar_0, ar_1, ar_2, ar_3) -> Com_1(evalcousot94(ar_0, ar_1, ar_2, ar_3)) 5.64/2.66 5.64/2.66 (Comp: 1, Cost: 1) evalcousot92(ar_0, ar_1, ar_2, ar_3) -> Com_1(evalcousot93(ar_0, ar_1, ar_2, ar_3)) 5.64/2.66 5.64/2.66 (Comp: 1, Cost: 1) evalcousot91(ar_0, ar_1, ar_2, ar_3) -> Com_1(evalcousot92(ar_0, ar_1, ar_2, ar_3)) 5.64/2.66 5.64/2.66 (Comp: 1, Cost: 1) evalcousot90(ar_0, ar_1, ar_2, ar_3) -> Com_1(evalcousot91(ar_0, ar_1, ar_2, ar_3)) 5.64/2.66 5.64/2.66 (Comp: 1, Cost: 1) evalcousot9bb0in(ar_0, ar_1, ar_2, ar_3) -> Com_1(evalcousot90(ar_0, ar_1, ar_2, ar_3)) 5.64/2.66 5.64/2.66 (Comp: 1, Cost: 1) evalcousot9start(ar_0, ar_1, ar_2, ar_3) -> Com_1(evalcousot9bb0in(ar_0, ar_1, ar_2, ar_3)) 5.64/2.66 5.64/2.66 (Comp: 1, Cost: 0) koat_start(ar_0, ar_1, ar_2, ar_3) -> Com_1(evalcousot9start(ar_0, ar_1, ar_2, ar_3)) [ 0 <= 0 ] 5.64/2.66 5.64/2.66 start location: koat_start 5.64/2.66 5.64/2.66 leaf cost: 0 5.64/2.66 5.64/2.66 5.64/2.66 5.64/2.66 Applied AI with 'oct' on problem 4 to obtain the following invariants: 5.64/2.66 5.64/2.66 For symbol evalcousot9bb1in: -X_3 + X_4 >= 0 5.64/2.66 5.64/2.66 For symbol evalcousot9bb2in: X_4 - 1 >= 0 /\ X_3 + X_4 - 2 >= 0 /\ -X_3 + X_4 >= 0 /\ X_3 - 1 >= 0 5.64/2.66 5.64/2.66 For symbol evalcousot9bb3in: -X_3 + X_4 >= 0 /\ -X_3 >= 0 5.64/2.66 5.64/2.66 5.64/2.66 5.64/2.66 5.64/2.66 5.64/2.66 This yielded the following problem: 5.64/2.66 5.64/2.66 5: T: 5.64/2.66 5.64/2.66 (Comp: 1, Cost: 0) koat_start(ar_0, ar_1, ar_2, ar_3) -> Com_1(evalcousot9start(ar_0, ar_1, ar_2, ar_3)) [ 0 <= 0 ] 5.64/2.66 5.64/2.66 (Comp: 1, Cost: 1) evalcousot9start(ar_0, ar_1, ar_2, ar_3) -> Com_1(evalcousot9bb0in(ar_0, ar_1, ar_2, ar_3)) 5.64/2.66 5.64/2.66 (Comp: 1, Cost: 1) evalcousot9bb0in(ar_0, ar_1, ar_2, ar_3) -> Com_1(evalcousot90(ar_0, ar_1, ar_2, ar_3)) 5.64/2.66 5.64/2.66 (Comp: 1, Cost: 1) evalcousot90(ar_0, ar_1, ar_2, ar_3) -> Com_1(evalcousot91(ar_0, ar_1, ar_2, ar_3)) 5.64/2.66 5.64/2.66 (Comp: 1, Cost: 1) evalcousot91(ar_0, ar_1, ar_2, ar_3) -> Com_1(evalcousot92(ar_0, ar_1, ar_2, ar_3)) 5.64/2.66 5.64/2.66 (Comp: 1, Cost: 1) evalcousot92(ar_0, ar_1, ar_2, ar_3) -> Com_1(evalcousot93(ar_0, ar_1, ar_2, ar_3)) 5.64/2.66 5.64/2.66 (Comp: 1, Cost: 1) evalcousot93(ar_0, ar_1, ar_2, ar_3) -> Com_1(evalcousot94(ar_0, ar_1, ar_2, ar_3)) 5.64/2.66 5.64/2.66 (Comp: 1, Cost: 1) evalcousot94(ar_0, ar_1, ar_2, ar_3) -> Com_1(evalcousot95(ar_0, ar_1, ar_2, ar_3)) 5.64/2.66 5.64/2.66 (Comp: 1, Cost: 1) evalcousot95(ar_0, ar_1, ar_2, ar_3) -> Com_1(evalcousot96(ar_0, ar_1, ar_2, ar_3)) 5.64/2.66 5.64/2.66 (Comp: 1, Cost: 1) evalcousot96(ar_0, ar_1, ar_2, ar_3) -> Com_1(evalcousot9bb1in(ar_1, ar_1, ar_3, ar_3)) 5.64/2.66 5.64/2.66 (Comp: ?, Cost: 1) evalcousot9bb1in(ar_0, ar_1, ar_2, ar_3) -> Com_1(evalcousot9bb2in(ar_0, ar_1, ar_2, ar_3)) [ -ar_2 + ar_3 >= 0 /\ ar_2 >= 1 ] 5.64/2.66 5.64/2.66 (Comp: 2, Cost: 1) evalcousot9bb1in(ar_0, ar_1, ar_2, ar_3) -> Com_1(evalcousot9bb3in(ar_0, ar_1, ar_2, ar_3)) [ -ar_2 + ar_3 >= 0 /\ 0 >= ar_2 ] 5.64/2.66 5.64/2.66 (Comp: ?, Cost: 1) evalcousot9bb2in(ar_0, ar_1, ar_2, ar_3) -> Com_1(evalcousot9bb1in(ar_0 - 1, ar_1, ar_2, ar_3)) [ ar_3 - 1 >= 0 /\ ar_2 + ar_3 - 2 >= 0 /\ -ar_2 + ar_3 >= 0 /\ ar_2 - 1 >= 0 /\ ar_0 >= 1 ] 5.64/2.66 5.64/2.66 (Comp: ?, Cost: 1) evalcousot9bb2in(ar_0, ar_1, ar_2, ar_3) -> Com_1(evalcousot9bb1in(ar_3, ar_1, ar_2 - 1, ar_3)) [ ar_3 - 1 >= 0 /\ ar_2 + ar_3 - 2 >= 0 /\ -ar_2 + ar_3 >= 0 /\ ar_2 - 1 >= 0 /\ 0 >= ar_0 ] 5.64/2.66 5.64/2.66 (Comp: 2, Cost: 1) evalcousot9bb3in(ar_0, ar_1, ar_2, ar_3) -> Com_1(evalcousot9stop(ar_0, ar_1, ar_2, ar_3)) [ -ar_2 + ar_3 >= 0 /\ -ar_2 >= 0 ] 5.64/2.66 5.64/2.66 start location: koat_start 5.64/2.66 5.64/2.66 leaf cost: 0 5.64/2.66 5.64/2.66 5.64/2.66 5.64/2.66 A polynomial rank function with 5.64/2.66 5.64/2.66 Pol(koat_start) = V_4 5.64/2.66 5.64/2.66 Pol(evalcousot9start) = V_4 5.64/2.66 5.64/2.66 Pol(evalcousot9bb0in) = V_4 5.64/2.66 5.64/2.66 Pol(evalcousot90) = V_4 5.64/2.66 5.64/2.66 Pol(evalcousot91) = V_4 5.64/2.66 5.64/2.66 Pol(evalcousot92) = V_4 5.64/2.66 5.64/2.66 Pol(evalcousot93) = V_4 5.64/2.66 5.64/2.66 Pol(evalcousot94) = V_4 5.64/2.66 5.64/2.66 Pol(evalcousot95) = V_4 5.64/2.66 5.64/2.66 Pol(evalcousot96) = V_4 5.64/2.66 5.64/2.66 Pol(evalcousot9bb1in) = V_3 5.64/2.66 5.64/2.66 Pol(evalcousot9bb2in) = V_3 5.64/2.66 5.64/2.66 Pol(evalcousot9bb3in) = V_3 5.64/2.66 5.64/2.66 Pol(evalcousot9stop) = V_3 5.64/2.66 5.64/2.66 orients all transitions weakly and the transition 5.64/2.66 5.64/2.66 evalcousot9bb2in(ar_0, ar_1, ar_2, ar_3) -> Com_1(evalcousot9bb1in(ar_3, ar_1, ar_2 - 1, ar_3)) [ ar_3 - 1 >= 0 /\ ar_2 + ar_3 - 2 >= 0 /\ -ar_2 + ar_3 >= 0 /\ ar_2 - 1 >= 0 /\ 0 >= ar_0 ] 5.64/2.66 5.64/2.66 strictly and produces the following problem: 5.64/2.66 5.64/2.66 6: T: 5.64/2.66 5.64/2.66 (Comp: 1, Cost: 0) koat_start(ar_0, ar_1, ar_2, ar_3) -> Com_1(evalcousot9start(ar_0, ar_1, ar_2, ar_3)) [ 0 <= 0 ] 5.64/2.66 5.64/2.66 (Comp: 1, Cost: 1) evalcousot9start(ar_0, ar_1, ar_2, ar_3) -> Com_1(evalcousot9bb0in(ar_0, ar_1, ar_2, ar_3)) 5.64/2.66 5.64/2.66 (Comp: 1, Cost: 1) evalcousot9bb0in(ar_0, ar_1, ar_2, ar_3) -> Com_1(evalcousot90(ar_0, ar_1, ar_2, ar_3)) 5.64/2.66 5.64/2.66 (Comp: 1, Cost: 1) evalcousot90(ar_0, ar_1, ar_2, ar_3) -> Com_1(evalcousot91(ar_0, ar_1, ar_2, ar_3)) 5.64/2.66 5.64/2.66 (Comp: 1, Cost: 1) evalcousot91(ar_0, ar_1, ar_2, ar_3) -> Com_1(evalcousot92(ar_0, ar_1, ar_2, ar_3)) 5.64/2.66 5.64/2.66 (Comp: 1, Cost: 1) evalcousot92(ar_0, ar_1, ar_2, ar_3) -> Com_1(evalcousot93(ar_0, ar_1, ar_2, ar_3)) 5.64/2.66 5.64/2.66 (Comp: 1, Cost: 1) evalcousot93(ar_0, ar_1, ar_2, ar_3) -> Com_1(evalcousot94(ar_0, ar_1, ar_2, ar_3)) 5.64/2.66 5.64/2.66 (Comp: 1, Cost: 1) evalcousot94(ar_0, ar_1, ar_2, ar_3) -> Com_1(evalcousot95(ar_0, ar_1, ar_2, ar_3)) 5.64/2.66 5.64/2.66 (Comp: 1, Cost: 1) evalcousot95(ar_0, ar_1, ar_2, ar_3) -> Com_1(evalcousot96(ar_0, ar_1, ar_2, ar_3)) 5.64/2.66 5.64/2.66 (Comp: 1, Cost: 1) evalcousot96(ar_0, ar_1, ar_2, ar_3) -> Com_1(evalcousot9bb1in(ar_1, ar_1, ar_3, ar_3)) 5.64/2.66 5.64/2.66 (Comp: ?, Cost: 1) evalcousot9bb1in(ar_0, ar_1, ar_2, ar_3) -> Com_1(evalcousot9bb2in(ar_0, ar_1, ar_2, ar_3)) [ -ar_2 + ar_3 >= 0 /\ ar_2 >= 1 ] 5.64/2.66 5.64/2.66 (Comp: 2, Cost: 1) evalcousot9bb1in(ar_0, ar_1, ar_2, ar_3) -> Com_1(evalcousot9bb3in(ar_0, ar_1, ar_2, ar_3)) [ -ar_2 + ar_3 >= 0 /\ 0 >= ar_2 ] 5.64/2.66 5.64/2.66 (Comp: ?, Cost: 1) evalcousot9bb2in(ar_0, ar_1, ar_2, ar_3) -> Com_1(evalcousot9bb1in(ar_0 - 1, ar_1, ar_2, ar_3)) [ ar_3 - 1 >= 0 /\ ar_2 + ar_3 - 2 >= 0 /\ -ar_2 + ar_3 >= 0 /\ ar_2 - 1 >= 0 /\ ar_0 >= 1 ] 5.64/2.66 5.64/2.66 (Comp: ar_3, Cost: 1) evalcousot9bb2in(ar_0, ar_1, ar_2, ar_3) -> Com_1(evalcousot9bb1in(ar_3, ar_1, ar_2 - 1, ar_3)) [ ar_3 - 1 >= 0 /\ ar_2 + ar_3 - 2 >= 0 /\ -ar_2 + ar_3 >= 0 /\ ar_2 - 1 >= 0 /\ 0 >= ar_0 ] 5.64/2.66 5.64/2.66 (Comp: 2, Cost: 1) evalcousot9bb3in(ar_0, ar_1, ar_2, ar_3) -> Com_1(evalcousot9stop(ar_0, ar_1, ar_2, ar_3)) [ -ar_2 + ar_3 >= 0 /\ -ar_2 >= 0 ] 5.64/2.66 5.64/2.66 start location: koat_start 5.64/2.66 5.64/2.66 leaf cost: 0 5.64/2.66 5.64/2.66 5.64/2.66 5.64/2.66 A polynomial rank function with 5.64/2.66 5.64/2.66 Pol(evalcousot9bb2in) = V_1 5.64/2.66 5.64/2.66 Pol(evalcousot9bb1in) = V_1 5.64/2.66 5.64/2.66 and size complexities 5.64/2.66 5.64/2.66 S("evalcousot9bb3in(ar_0, ar_1, ar_2, ar_3) -> Com_1(evalcousot9stop(ar_0, ar_1, ar_2, ar_3)) [ -ar_2 + ar_3 >= 0 /\\ -ar_2 >= 0 ]", 0-0) = ar_1 + ar_3 5.64/2.66 5.64/2.66 S("evalcousot9bb3in(ar_0, ar_1, ar_2, ar_3) -> Com_1(evalcousot9stop(ar_0, ar_1, ar_2, ar_3)) [ -ar_2 + ar_3 >= 0 /\\ -ar_2 >= 0 ]", 0-1) = ar_1 5.64/2.66 5.64/2.66 S("evalcousot9bb3in(ar_0, ar_1, ar_2, ar_3) -> Com_1(evalcousot9stop(ar_0, ar_1, ar_2, ar_3)) [ -ar_2 + ar_3 >= 0 /\\ -ar_2 >= 0 ]", 0-2) = ar_3 5.64/2.66 5.64/2.66 S("evalcousot9bb3in(ar_0, ar_1, ar_2, ar_3) -> Com_1(evalcousot9stop(ar_0, ar_1, ar_2, ar_3)) [ -ar_2 + ar_3 >= 0 /\\ -ar_2 >= 0 ]", 0-3) = ar_3 5.64/2.66 5.64/2.66 S("evalcousot9bb2in(ar_0, ar_1, ar_2, ar_3) -> Com_1(evalcousot9bb1in(ar_3, ar_1, ar_2 - 1, ar_3)) [ ar_3 - 1 >= 0 /\\ ar_2 + ar_3 - 2 >= 0 /\\ -ar_2 + ar_3 >= 0 /\\ ar_2 - 1 >= 0 /\\ 0 >= ar_0 ]", 0-0) = ar_3 5.64/2.66 5.64/2.66 S("evalcousot9bb2in(ar_0, ar_1, ar_2, ar_3) -> Com_1(evalcousot9bb1in(ar_3, ar_1, ar_2 - 1, ar_3)) [ ar_3 - 1 >= 0 /\\ ar_2 + ar_3 - 2 >= 0 /\\ -ar_2 + ar_3 >= 0 /\\ ar_2 - 1 >= 0 /\\ 0 >= ar_0 ]", 0-1) = ar_1 5.64/2.66 5.64/2.66 S("evalcousot9bb2in(ar_0, ar_1, ar_2, ar_3) -> Com_1(evalcousot9bb1in(ar_3, ar_1, ar_2 - 1, ar_3)) [ ar_3 - 1 >= 0 /\\ ar_2 + ar_3 - 2 >= 0 /\\ -ar_2 + ar_3 >= 0 /\\ ar_2 - 1 >= 0 /\\ 0 >= ar_0 ]", 0-2) = ar_3 5.64/2.66 5.64/2.66 S("evalcousot9bb2in(ar_0, ar_1, ar_2, ar_3) -> Com_1(evalcousot9bb1in(ar_3, ar_1, ar_2 - 1, ar_3)) [ ar_3 - 1 >= 0 /\\ ar_2 + ar_3 - 2 >= 0 /\\ -ar_2 + ar_3 >= 0 /\\ ar_2 - 1 >= 0 /\\ 0 >= ar_0 ]", 0-3) = ar_3 5.64/2.66 5.64/2.66 S("evalcousot9bb2in(ar_0, ar_1, ar_2, ar_3) -> Com_1(evalcousot9bb1in(ar_0 - 1, ar_1, ar_2, ar_3)) [ ar_3 - 1 >= 0 /\\ ar_2 + ar_3 - 2 >= 0 /\\ -ar_2 + ar_3 >= 0 /\\ ar_2 - 1 >= 0 /\\ ar_0 >= 1 ]", 0-0) = ar_1 + ar_3 5.64/2.66 5.64/2.66 S("evalcousot9bb2in(ar_0, ar_1, ar_2, ar_3) -> Com_1(evalcousot9bb1in(ar_0 - 1, ar_1, ar_2, ar_3)) [ ar_3 - 1 >= 0 /\\ ar_2 + ar_3 - 2 >= 0 /\\ -ar_2 + ar_3 >= 0 /\\ ar_2 - 1 >= 0 /\\ ar_0 >= 1 ]", 0-1) = ar_1 5.64/2.66 5.64/2.66 S("evalcousot9bb2in(ar_0, ar_1, ar_2, ar_3) -> Com_1(evalcousot9bb1in(ar_0 - 1, ar_1, ar_2, ar_3)) [ ar_3 - 1 >= 0 /\\ ar_2 + ar_3 - 2 >= 0 /\\ -ar_2 + ar_3 >= 0 /\\ ar_2 - 1 >= 0 /\\ ar_0 >= 1 ]", 0-2) = ar_3 5.64/2.66 5.64/2.66 S("evalcousot9bb2in(ar_0, ar_1, ar_2, ar_3) -> Com_1(evalcousot9bb1in(ar_0 - 1, ar_1, ar_2, ar_3)) [ ar_3 - 1 >= 0 /\\ ar_2 + ar_3 - 2 >= 0 /\\ -ar_2 + ar_3 >= 0 /\\ ar_2 - 1 >= 0 /\\ ar_0 >= 1 ]", 0-3) = ar_3 5.64/2.66 5.64/2.66 S("evalcousot9bb1in(ar_0, ar_1, ar_2, ar_3) -> Com_1(evalcousot9bb3in(ar_0, ar_1, ar_2, ar_3)) [ -ar_2 + ar_3 >= 0 /\\ 0 >= ar_2 ]", 0-0) = ar_1 + ar_3 5.64/2.66 5.64/2.66 S("evalcousot9bb1in(ar_0, ar_1, ar_2, ar_3) -> Com_1(evalcousot9bb3in(ar_0, ar_1, ar_2, ar_3)) [ -ar_2 + ar_3 >= 0 /\\ 0 >= ar_2 ]", 0-1) = ar_1 5.64/2.66 5.64/2.66 S("evalcousot9bb1in(ar_0, ar_1, ar_2, ar_3) -> Com_1(evalcousot9bb3in(ar_0, ar_1, ar_2, ar_3)) [ -ar_2 + ar_3 >= 0 /\\ 0 >= ar_2 ]", 0-2) = ar_3 5.64/2.66 5.64/2.66 S("evalcousot9bb1in(ar_0, ar_1, ar_2, ar_3) -> Com_1(evalcousot9bb3in(ar_0, ar_1, ar_2, ar_3)) [ -ar_2 + ar_3 >= 0 /\\ 0 >= ar_2 ]", 0-3) = ar_3 5.64/2.66 5.64/2.66 S("evalcousot9bb1in(ar_0, ar_1, ar_2, ar_3) -> Com_1(evalcousot9bb2in(ar_0, ar_1, ar_2, ar_3)) [ -ar_2 + ar_3 >= 0 /\\ ar_2 >= 1 ]", 0-0) = ar_1 + ar_3 5.64/2.66 5.64/2.66 S("evalcousot9bb1in(ar_0, ar_1, ar_2, ar_3) -> Com_1(evalcousot9bb2in(ar_0, ar_1, ar_2, ar_3)) [ -ar_2 + ar_3 >= 0 /\\ ar_2 >= 1 ]", 0-1) = ar_1 5.64/2.66 5.64/2.66 S("evalcousot9bb1in(ar_0, ar_1, ar_2, ar_3) -> Com_1(evalcousot9bb2in(ar_0, ar_1, ar_2, ar_3)) [ -ar_2 + ar_3 >= 0 /\\ ar_2 >= 1 ]", 0-2) = ar_3 5.64/2.66 5.64/2.66 S("evalcousot9bb1in(ar_0, ar_1, ar_2, ar_3) -> Com_1(evalcousot9bb2in(ar_0, ar_1, ar_2, ar_3)) [ -ar_2 + ar_3 >= 0 /\\ ar_2 >= 1 ]", 0-3) = ar_3 5.64/2.66 5.64/2.66 S("evalcousot96(ar_0, ar_1, ar_2, ar_3) -> Com_1(evalcousot9bb1in(ar_1, ar_1, ar_3, ar_3))", 0-0) = ar_1 5.64/2.66 5.64/2.66 S("evalcousot96(ar_0, ar_1, ar_2, ar_3) -> Com_1(evalcousot9bb1in(ar_1, ar_1, ar_3, ar_3))", 0-1) = ar_1 5.64/2.66 5.64/2.66 S("evalcousot96(ar_0, ar_1, ar_2, ar_3) -> Com_1(evalcousot9bb1in(ar_1, ar_1, ar_3, ar_3))", 0-2) = ar_3 5.64/2.66 5.64/2.66 S("evalcousot96(ar_0, ar_1, ar_2, ar_3) -> Com_1(evalcousot9bb1in(ar_1, ar_1, ar_3, ar_3))", 0-3) = ar_3 5.64/2.66 5.64/2.66 S("evalcousot95(ar_0, ar_1, ar_2, ar_3) -> Com_1(evalcousot96(ar_0, ar_1, ar_2, ar_3))", 0-0) = ar_0 5.64/2.66 5.64/2.66 S("evalcousot95(ar_0, ar_1, ar_2, ar_3) -> Com_1(evalcousot96(ar_0, ar_1, ar_2, ar_3))", 0-1) = ar_1 5.64/2.66 5.64/2.66 S("evalcousot95(ar_0, ar_1, ar_2, ar_3) -> Com_1(evalcousot96(ar_0, ar_1, ar_2, ar_3))", 0-2) = ar_2 5.64/2.66 5.64/2.66 S("evalcousot95(ar_0, ar_1, ar_2, ar_3) -> Com_1(evalcousot96(ar_0, ar_1, ar_2, ar_3))", 0-3) = ar_3 5.64/2.66 5.64/2.66 S("evalcousot94(ar_0, ar_1, ar_2, ar_3) -> Com_1(evalcousot95(ar_0, ar_1, ar_2, ar_3))", 0-0) = ar_0 5.64/2.66 5.64/2.66 S("evalcousot94(ar_0, ar_1, ar_2, ar_3) -> Com_1(evalcousot95(ar_0, ar_1, ar_2, ar_3))", 0-1) = ar_1 5.64/2.66 5.64/2.66 S("evalcousot94(ar_0, ar_1, ar_2, ar_3) -> Com_1(evalcousot95(ar_0, ar_1, ar_2, ar_3))", 0-2) = ar_2 5.64/2.66 5.64/2.66 S("evalcousot94(ar_0, ar_1, ar_2, ar_3) -> Com_1(evalcousot95(ar_0, ar_1, ar_2, ar_3))", 0-3) = ar_3 5.64/2.66 5.64/2.66 S("evalcousot93(ar_0, ar_1, ar_2, ar_3) -> Com_1(evalcousot94(ar_0, ar_1, ar_2, ar_3))", 0-0) = ar_0 5.64/2.66 5.64/2.66 S("evalcousot93(ar_0, ar_1, ar_2, ar_3) -> Com_1(evalcousot94(ar_0, ar_1, ar_2, ar_3))", 0-1) = ar_1 5.64/2.66 5.64/2.66 S("evalcousot93(ar_0, ar_1, ar_2, ar_3) -> Com_1(evalcousot94(ar_0, ar_1, ar_2, ar_3))", 0-2) = ar_2 5.64/2.66 5.64/2.66 S("evalcousot93(ar_0, ar_1, ar_2, ar_3) -> Com_1(evalcousot94(ar_0, ar_1, ar_2, ar_3))", 0-3) = ar_3 5.64/2.66 5.64/2.66 S("evalcousot92(ar_0, ar_1, ar_2, ar_3) -> Com_1(evalcousot93(ar_0, ar_1, ar_2, ar_3))", 0-0) = ar_0 5.64/2.66 5.64/2.66 S("evalcousot92(ar_0, ar_1, ar_2, ar_3) -> Com_1(evalcousot93(ar_0, ar_1, ar_2, ar_3))", 0-1) = ar_1 5.64/2.66 5.64/2.66 S("evalcousot92(ar_0, ar_1, ar_2, ar_3) -> Com_1(evalcousot93(ar_0, ar_1, ar_2, ar_3))", 0-2) = ar_2 5.64/2.66 5.64/2.66 S("evalcousot92(ar_0, ar_1, ar_2, ar_3) -> Com_1(evalcousot93(ar_0, ar_1, ar_2, ar_3))", 0-3) = ar_3 5.64/2.66 5.64/2.66 S("evalcousot91(ar_0, ar_1, ar_2, ar_3) -> Com_1(evalcousot92(ar_0, ar_1, ar_2, ar_3))", 0-0) = ar_0 5.64/2.66 5.64/2.66 S("evalcousot91(ar_0, ar_1, ar_2, ar_3) -> Com_1(evalcousot92(ar_0, ar_1, ar_2, ar_3))", 0-1) = ar_1 5.64/2.66 5.64/2.66 S("evalcousot91(ar_0, ar_1, ar_2, ar_3) -> Com_1(evalcousot92(ar_0, ar_1, ar_2, ar_3))", 0-2) = ar_2 5.64/2.66 5.64/2.66 S("evalcousot91(ar_0, ar_1, ar_2, ar_3) -> Com_1(evalcousot92(ar_0, ar_1, ar_2, ar_3))", 0-3) = ar_3 5.64/2.66 5.64/2.66 S("evalcousot90(ar_0, ar_1, ar_2, ar_3) -> Com_1(evalcousot91(ar_0, ar_1, ar_2, ar_3))", 0-0) = ar_0 5.64/2.66 5.64/2.66 S("evalcousot90(ar_0, ar_1, ar_2, ar_3) -> Com_1(evalcousot91(ar_0, ar_1, ar_2, ar_3))", 0-1) = ar_1 5.64/2.66 5.64/2.66 S("evalcousot90(ar_0, ar_1, ar_2, ar_3) -> Com_1(evalcousot91(ar_0, ar_1, ar_2, ar_3))", 0-2) = ar_2 5.64/2.66 5.64/2.66 S("evalcousot90(ar_0, ar_1, ar_2, ar_3) -> Com_1(evalcousot91(ar_0, ar_1, ar_2, ar_3))", 0-3) = ar_3 5.64/2.66 5.64/2.66 S("evalcousot9bb0in(ar_0, ar_1, ar_2, ar_3) -> Com_1(evalcousot90(ar_0, ar_1, ar_2, ar_3))", 0-0) = ar_0 5.64/2.66 5.64/2.66 S("evalcousot9bb0in(ar_0, ar_1, ar_2, ar_3) -> Com_1(evalcousot90(ar_0, ar_1, ar_2, ar_3))", 0-1) = ar_1 5.64/2.66 5.64/2.66 S("evalcousot9bb0in(ar_0, ar_1, ar_2, ar_3) -> Com_1(evalcousot90(ar_0, ar_1, ar_2, ar_3))", 0-2) = ar_2 5.64/2.66 5.64/2.66 S("evalcousot9bb0in(ar_0, ar_1, ar_2, ar_3) -> Com_1(evalcousot90(ar_0, ar_1, ar_2, ar_3))", 0-3) = ar_3 5.64/2.66 5.64/2.66 S("evalcousot9start(ar_0, ar_1, ar_2, ar_3) -> Com_1(evalcousot9bb0in(ar_0, ar_1, ar_2, ar_3))", 0-0) = ar_0 5.64/2.66 5.64/2.66 S("evalcousot9start(ar_0, ar_1, ar_2, ar_3) -> Com_1(evalcousot9bb0in(ar_0, ar_1, ar_2, ar_3))", 0-1) = ar_1 5.64/2.66 5.64/2.66 S("evalcousot9start(ar_0, ar_1, ar_2, ar_3) -> Com_1(evalcousot9bb0in(ar_0, ar_1, ar_2, ar_3))", 0-2) = ar_2 5.64/2.66 5.64/2.66 S("evalcousot9start(ar_0, ar_1, ar_2, ar_3) -> Com_1(evalcousot9bb0in(ar_0, ar_1, ar_2, ar_3))", 0-3) = ar_3 5.64/2.66 5.64/2.66 S("koat_start(ar_0, ar_1, ar_2, ar_3) -> Com_1(evalcousot9start(ar_0, ar_1, ar_2, ar_3)) [ 0 <= 0 ]", 0-0) = ar_0 5.64/2.66 5.64/2.66 S("koat_start(ar_0, ar_1, ar_2, ar_3) -> Com_1(evalcousot9start(ar_0, ar_1, ar_2, ar_3)) [ 0 <= 0 ]", 0-1) = ar_1 5.64/2.66 5.64/2.66 S("koat_start(ar_0, ar_1, ar_2, ar_3) -> Com_1(evalcousot9start(ar_0, ar_1, ar_2, ar_3)) [ 0 <= 0 ]", 0-2) = ar_2 5.64/2.66 5.64/2.66 S("koat_start(ar_0, ar_1, ar_2, ar_3) -> Com_1(evalcousot9start(ar_0, ar_1, ar_2, ar_3)) [ 0 <= 0 ]", 0-3) = ar_3 5.64/2.66 5.64/2.66 orients the transitions 5.64/2.66 5.64/2.66 evalcousot9bb2in(ar_0, ar_1, ar_2, ar_3) -> Com_1(evalcousot9bb1in(ar_0 - 1, ar_1, ar_2, ar_3)) [ ar_3 - 1 >= 0 /\ ar_2 + ar_3 - 2 >= 0 /\ -ar_2 + ar_3 >= 0 /\ ar_2 - 1 >= 0 /\ ar_0 >= 1 ] 5.64/2.66 5.64/2.66 evalcousot9bb1in(ar_0, ar_1, ar_2, ar_3) -> Com_1(evalcousot9bb2in(ar_0, ar_1, ar_2, ar_3)) [ -ar_2 + ar_3 >= 0 /\ ar_2 >= 1 ] 5.64/2.66 5.64/2.66 weakly and the transition 5.64/2.66 5.64/2.66 evalcousot9bb2in(ar_0, ar_1, ar_2, ar_3) -> Com_1(evalcousot9bb1in(ar_0 - 1, ar_1, ar_2, ar_3)) [ ar_3 - 1 >= 0 /\ ar_2 + ar_3 - 2 >= 0 /\ -ar_2 + ar_3 >= 0 /\ ar_2 - 1 >= 0 /\ ar_0 >= 1 ] 5.64/2.66 5.64/2.66 strictly and produces the following problem: 5.64/2.66 5.64/2.66 7: T: 5.64/2.66 5.64/2.66 (Comp: 1, Cost: 0) koat_start(ar_0, ar_1, ar_2, ar_3) -> Com_1(evalcousot9start(ar_0, ar_1, ar_2, ar_3)) [ 0 <= 0 ] 5.64/2.66 5.64/2.66 (Comp: 1, Cost: 1) evalcousot9start(ar_0, ar_1, ar_2, ar_3) -> Com_1(evalcousot9bb0in(ar_0, ar_1, ar_2, ar_3)) 5.64/2.66 5.64/2.66 (Comp: 1, Cost: 1) evalcousot9bb0in(ar_0, ar_1, ar_2, ar_3) -> Com_1(evalcousot90(ar_0, ar_1, ar_2, ar_3)) 5.64/2.66 5.64/2.66 (Comp: 1, Cost: 1) evalcousot90(ar_0, ar_1, ar_2, ar_3) -> Com_1(evalcousot91(ar_0, ar_1, ar_2, ar_3)) 5.64/2.66 5.64/2.66 (Comp: 1, Cost: 1) evalcousot91(ar_0, ar_1, ar_2, ar_3) -> Com_1(evalcousot92(ar_0, ar_1, ar_2, ar_3)) 5.64/2.66 5.64/2.66 (Comp: 1, Cost: 1) evalcousot92(ar_0, ar_1, ar_2, ar_3) -> Com_1(evalcousot93(ar_0, ar_1, ar_2, ar_3)) 5.64/2.66 5.64/2.66 (Comp: 1, Cost: 1) evalcousot93(ar_0, ar_1, ar_2, ar_3) -> Com_1(evalcousot94(ar_0, ar_1, ar_2, ar_3)) 5.64/2.66 5.64/2.66 (Comp: 1, Cost: 1) evalcousot94(ar_0, ar_1, ar_2, ar_3) -> Com_1(evalcousot95(ar_0, ar_1, ar_2, ar_3)) 5.64/2.66 5.64/2.66 (Comp: 1, Cost: 1) evalcousot95(ar_0, ar_1, ar_2, ar_3) -> Com_1(evalcousot96(ar_0, ar_1, ar_2, ar_3)) 5.64/2.66 5.64/2.66 (Comp: 1, Cost: 1) evalcousot96(ar_0, ar_1, ar_2, ar_3) -> Com_1(evalcousot9bb1in(ar_1, ar_1, ar_3, ar_3)) 5.64/2.66 5.64/2.66 (Comp: ?, Cost: 1) evalcousot9bb1in(ar_0, ar_1, ar_2, ar_3) -> Com_1(evalcousot9bb2in(ar_0, ar_1, ar_2, ar_3)) [ -ar_2 + ar_3 >= 0 /\ ar_2 >= 1 ] 5.64/2.66 5.64/2.66 (Comp: 2, Cost: 1) evalcousot9bb1in(ar_0, ar_1, ar_2, ar_3) -> Com_1(evalcousot9bb3in(ar_0, ar_1, ar_2, ar_3)) [ -ar_2 + ar_3 >= 0 /\ 0 >= ar_2 ] 5.64/2.66 5.64/2.66 (Comp: ar_3^2 + ar_1, Cost: 1) evalcousot9bb2in(ar_0, ar_1, ar_2, ar_3) -> Com_1(evalcousot9bb1in(ar_0 - 1, ar_1, ar_2, ar_3)) [ ar_3 - 1 >= 0 /\ ar_2 + ar_3 - 2 >= 0 /\ -ar_2 + ar_3 >= 0 /\ ar_2 - 1 >= 0 /\ ar_0 >= 1 ] 5.64/2.66 5.64/2.66 (Comp: ar_3, Cost: 1) evalcousot9bb2in(ar_0, ar_1, ar_2, ar_3) -> Com_1(evalcousot9bb1in(ar_3, ar_1, ar_2 - 1, ar_3)) [ ar_3 - 1 >= 0 /\ ar_2 + ar_3 - 2 >= 0 /\ -ar_2 + ar_3 >= 0 /\ ar_2 - 1 >= 0 /\ 0 >= ar_0 ] 5.64/2.66 5.64/2.66 (Comp: 2, Cost: 1) evalcousot9bb3in(ar_0, ar_1, ar_2, ar_3) -> Com_1(evalcousot9stop(ar_0, ar_1, ar_2, ar_3)) [ -ar_2 + ar_3 >= 0 /\ -ar_2 >= 0 ] 5.64/2.66 5.64/2.66 start location: koat_start 5.64/2.66 5.64/2.66 leaf cost: 0 5.64/2.66 5.64/2.66 5.64/2.66 5.64/2.66 Repeatedly propagating knowledge in problem 7 produces the following problem: 5.64/2.66 5.64/2.66 8: T: 5.64/2.66 5.64/2.66 (Comp: 1, Cost: 0) koat_start(ar_0, ar_1, ar_2, ar_3) -> Com_1(evalcousot9start(ar_0, ar_1, ar_2, ar_3)) [ 0 <= 0 ] 5.64/2.66 5.64/2.66 (Comp: 1, Cost: 1) evalcousot9start(ar_0, ar_1, ar_2, ar_3) -> Com_1(evalcousot9bb0in(ar_0, ar_1, ar_2, ar_3)) 5.64/2.66 5.64/2.66 (Comp: 1, Cost: 1) evalcousot9bb0in(ar_0, ar_1, ar_2, ar_3) -> Com_1(evalcousot90(ar_0, ar_1, ar_2, ar_3)) 5.64/2.66 5.64/2.66 (Comp: 1, Cost: 1) evalcousot90(ar_0, ar_1, ar_2, ar_3) -> Com_1(evalcousot91(ar_0, ar_1, ar_2, ar_3)) 5.64/2.66 5.64/2.66 (Comp: 1, Cost: 1) evalcousot91(ar_0, ar_1, ar_2, ar_3) -> Com_1(evalcousot92(ar_0, ar_1, ar_2, ar_3)) 5.64/2.66 5.64/2.66 (Comp: 1, Cost: 1) evalcousot92(ar_0, ar_1, ar_2, ar_3) -> Com_1(evalcousot93(ar_0, ar_1, ar_2, ar_3)) 5.64/2.66 5.64/2.66 (Comp: 1, Cost: 1) evalcousot93(ar_0, ar_1, ar_2, ar_3) -> Com_1(evalcousot94(ar_0, ar_1, ar_2, ar_3)) 5.64/2.66 5.64/2.66 (Comp: 1, Cost: 1) evalcousot94(ar_0, ar_1, ar_2, ar_3) -> Com_1(evalcousot95(ar_0, ar_1, ar_2, ar_3)) 5.64/2.66 5.64/2.66 (Comp: 1, Cost: 1) evalcousot95(ar_0, ar_1, ar_2, ar_3) -> Com_1(evalcousot96(ar_0, ar_1, ar_2, ar_3)) 5.64/2.66 5.64/2.66 (Comp: 1, Cost: 1) evalcousot96(ar_0, ar_1, ar_2, ar_3) -> Com_1(evalcousot9bb1in(ar_1, ar_1, ar_3, ar_3)) 5.64/2.66 5.64/2.66 (Comp: ar_3 + ar_3^2 + ar_1 + 1, Cost: 1) evalcousot9bb1in(ar_0, ar_1, ar_2, ar_3) -> Com_1(evalcousot9bb2in(ar_0, ar_1, ar_2, ar_3)) [ -ar_2 + ar_3 >= 0 /\ ar_2 >= 1 ] 5.64/2.66 5.64/2.66 (Comp: 2, Cost: 1) evalcousot9bb1in(ar_0, ar_1, ar_2, ar_3) -> Com_1(evalcousot9bb3in(ar_0, ar_1, ar_2, ar_3)) [ -ar_2 + ar_3 >= 0 /\ 0 >= ar_2 ] 5.64/2.66 5.64/2.66 (Comp: ar_3^2 + ar_1, Cost: 1) evalcousot9bb2in(ar_0, ar_1, ar_2, ar_3) -> Com_1(evalcousot9bb1in(ar_0 - 1, ar_1, ar_2, ar_3)) [ ar_3 - 1 >= 0 /\ ar_2 + ar_3 - 2 >= 0 /\ -ar_2 + ar_3 >= 0 /\ ar_2 - 1 >= 0 /\ ar_0 >= 1 ] 5.64/2.66 5.64/2.66 (Comp: ar_3, Cost: 1) evalcousot9bb2in(ar_0, ar_1, ar_2, ar_3) -> Com_1(evalcousot9bb1in(ar_3, ar_1, ar_2 - 1, ar_3)) [ ar_3 - 1 >= 0 /\ ar_2 + ar_3 - 2 >= 0 /\ -ar_2 + ar_3 >= 0 /\ ar_2 - 1 >= 0 /\ 0 >= ar_0 ] 5.64/2.66 5.64/2.66 (Comp: 2, Cost: 1) evalcousot9bb3in(ar_0, ar_1, ar_2, ar_3) -> Com_1(evalcousot9stop(ar_0, ar_1, ar_2, ar_3)) [ -ar_2 + ar_3 >= 0 /\ -ar_2 >= 0 ] 5.64/2.66 5.64/2.66 start location: koat_start 5.64/2.66 5.64/2.66 leaf cost: 0 5.64/2.66 5.64/2.66 5.64/2.66 5.64/2.66 Complexity upper bound 2*ar_3 + 2*ar_3^2 + 2*ar_1 + 14 5.64/2.66 5.64/2.66 5.64/2.66 5.64/2.66 Time: 0.322 sec (SMT: 0.253 sec) 5.64/2.66 5.64/2.66 5.64/2.66 ---------------------------------------- 5.64/2.66 5.64/2.66 (2) 5.64/2.66 BOUNDS(1, n^2) 5.64/2.66 5.64/2.66 ---------------------------------------- 5.64/2.66 5.64/2.66 (3) Loat Proof (FINISHED) 5.64/2.66 5.64/2.66 5.64/2.66 ### Pre-processing the ITS problem ### 5.64/2.66 5.64/2.66 5.64/2.66 5.64/2.66 Initial linear ITS problem 5.64/2.66 5.64/2.66 Start location: evalcousot9start 5.64/2.66 5.64/2.66 0: evalcousot9start -> evalcousot9bb0in : [], cost: 1 5.64/2.66 5.64/2.66 1: evalcousot9bb0in -> evalcousot90 : [], cost: 1 5.64/2.66 5.64/2.66 2: evalcousot90 -> evalcousot91 : [], cost: 1 5.64/2.66 5.64/2.66 3: evalcousot91 -> evalcousot92 : [], cost: 1 5.64/2.66 5.64/2.66 4: evalcousot92 -> evalcousot93 : [], cost: 1 5.64/2.66 5.64/2.66 5: evalcousot93 -> evalcousot94 : [], cost: 1 5.64/2.66 5.64/2.66 6: evalcousot94 -> evalcousot95 : [], cost: 1 5.64/2.66 5.64/2.66 7: evalcousot95 -> evalcousot96 : [], cost: 1 5.64/2.66 5.64/2.66 8: evalcousot96 -> evalcousot9bb1in : A'=B, C'=D, [], cost: 1 5.64/2.66 5.64/2.66 9: evalcousot9bb1in -> evalcousot9bb2in : [ C>=1 ], cost: 1 5.64/2.66 5.64/2.66 10: evalcousot9bb1in -> evalcousot9bb3in : [ 0>=C ], cost: 1 5.64/2.66 5.64/2.66 11: evalcousot9bb2in -> evalcousot9bb1in : A'=-1+A, [ A>=1 ], cost: 1 5.64/2.66 5.64/2.66 12: evalcousot9bb2in -> evalcousot9bb1in : A'=D, [ A>=1 && 0>=A ], cost: 1 5.64/2.66 5.64/2.66 13: evalcousot9bb2in -> evalcousot9bb1in : A'=-1+A, C'=-1+C, [ 0>=A && A>=1 ], cost: 1 5.64/2.66 5.64/2.66 14: evalcousot9bb2in -> evalcousot9bb1in : A'=D, C'=-1+C, [ 0>=A ], cost: 1 5.64/2.66 5.64/2.66 15: evalcousot9bb3in -> evalcousot9stop : [], cost: 1 5.64/2.66 5.64/2.66 5.64/2.66 5.64/2.66 Removed unreachable and leaf rules: 5.64/2.66 5.64/2.66 Start location: evalcousot9start 5.64/2.66 5.64/2.66 0: evalcousot9start -> evalcousot9bb0in : [], cost: 1 5.64/2.66 5.64/2.66 1: evalcousot9bb0in -> evalcousot90 : [], cost: 1 5.64/2.66 5.64/2.66 2: evalcousot90 -> evalcousot91 : [], cost: 1 5.64/2.66 5.64/2.66 3: evalcousot91 -> evalcousot92 : [], cost: 1 5.64/2.66 5.64/2.66 4: evalcousot92 -> evalcousot93 : [], cost: 1 5.64/2.66 5.64/2.66 5: evalcousot93 -> evalcousot94 : [], cost: 1 5.64/2.66 5.64/2.66 6: evalcousot94 -> evalcousot95 : [], cost: 1 5.64/2.66 5.64/2.66 7: evalcousot95 -> evalcousot96 : [], cost: 1 5.64/2.66 5.64/2.66 8: evalcousot96 -> evalcousot9bb1in : A'=B, C'=D, [], cost: 1 5.64/2.66 5.64/2.66 9: evalcousot9bb1in -> evalcousot9bb2in : [ C>=1 ], cost: 1 5.64/2.66 5.64/2.66 11: evalcousot9bb2in -> evalcousot9bb1in : A'=-1+A, [ A>=1 ], cost: 1 5.64/2.66 5.64/2.66 12: evalcousot9bb2in -> evalcousot9bb1in : A'=D, [ A>=1 && 0>=A ], cost: 1 5.64/2.66 5.64/2.66 13: evalcousot9bb2in -> evalcousot9bb1in : A'=-1+A, C'=-1+C, [ 0>=A && A>=1 ], cost: 1 5.64/2.66 5.64/2.66 14: evalcousot9bb2in -> evalcousot9bb1in : A'=D, C'=-1+C, [ 0>=A ], cost: 1 5.64/2.66 5.64/2.66 5.64/2.66 5.64/2.66 Removed rules with unsatisfiable guard: 5.64/2.66 5.64/2.66 Start location: evalcousot9start 5.64/2.66 5.64/2.66 0: evalcousot9start -> evalcousot9bb0in : [], cost: 1 5.64/2.66 5.64/2.66 1: evalcousot9bb0in -> evalcousot90 : [], cost: 1 5.64/2.66 5.64/2.66 2: evalcousot90 -> evalcousot91 : [], cost: 1 5.64/2.66 5.64/2.66 3: evalcousot91 -> evalcousot92 : [], cost: 1 5.64/2.66 5.64/2.66 4: evalcousot92 -> evalcousot93 : [], cost: 1 5.64/2.66 5.64/2.66 5: evalcousot93 -> evalcousot94 : [], cost: 1 5.64/2.66 5.64/2.66 6: evalcousot94 -> evalcousot95 : [], cost: 1 5.64/2.66 5.64/2.66 7: evalcousot95 -> evalcousot96 : [], cost: 1 5.64/2.66 5.64/2.66 8: evalcousot96 -> evalcousot9bb1in : A'=B, C'=D, [], cost: 1 5.64/2.66 5.64/2.66 9: evalcousot9bb1in -> evalcousot9bb2in : [ C>=1 ], cost: 1 5.64/2.66 5.64/2.66 11: evalcousot9bb2in -> evalcousot9bb1in : A'=-1+A, [ A>=1 ], cost: 1 5.64/2.66 5.64/2.66 14: evalcousot9bb2in -> evalcousot9bb1in : A'=D, C'=-1+C, [ 0>=A ], cost: 1 5.64/2.66 5.64/2.66 5.64/2.66 5.64/2.66 ### Simplification by acceleration and chaining ### 5.64/2.66 5.64/2.66 5.64/2.66 5.64/2.66 Eliminated locations (on linear paths): 5.64/2.66 5.64/2.66 Start location: evalcousot9start 5.64/2.66 5.64/2.66 23: evalcousot9start -> evalcousot9bb1in : A'=B, C'=D, [], cost: 9 5.64/2.66 5.64/2.66 9: evalcousot9bb1in -> evalcousot9bb2in : [ C>=1 ], cost: 1 5.64/2.66 5.64/2.66 11: evalcousot9bb2in -> evalcousot9bb1in : A'=-1+A, [ A>=1 ], cost: 1 5.64/2.66 5.64/2.66 14: evalcousot9bb2in -> evalcousot9bb1in : A'=D, C'=-1+C, [ 0>=A ], cost: 1 5.64/2.66 5.64/2.66 5.64/2.66 5.64/2.66 Eliminated locations (on tree-shaped paths): 5.64/2.66 5.64/2.66 Start location: evalcousot9start 5.64/2.66 5.64/2.66 23: evalcousot9start -> evalcousot9bb1in : A'=B, C'=D, [], cost: 9 5.64/2.66 5.64/2.66 24: evalcousot9bb1in -> evalcousot9bb1in : A'=-1+A, [ C>=1 && A>=1 ], cost: 2 5.64/2.66 5.64/2.66 25: evalcousot9bb1in -> evalcousot9bb1in : A'=D, C'=-1+C, [ C>=1 && 0>=A ], cost: 2 5.64/2.66 5.64/2.66 5.64/2.66 5.64/2.66 Accelerating simple loops of location 9. 5.64/2.66 5.64/2.66 Accelerating the following rules: 5.64/2.66 5.64/2.66 24: evalcousot9bb1in -> evalcousot9bb1in : A'=-1+A, [ C>=1 && A>=1 ], cost: 2 5.64/2.66 5.64/2.66 25: evalcousot9bb1in -> evalcousot9bb1in : A'=D, C'=-1+C, [ C>=1 && 0>=A ], cost: 2 5.64/2.66 5.64/2.66 5.64/2.66 5.64/2.66 Accelerated rule 24 with metering function A, yielding the new rule 26. 5.64/2.66 5.64/2.66 Accelerated rule 25 with metering function C (after strengthening guard), yielding the new rule 27. 5.64/2.66 5.64/2.66 Nested simple loops 25 (outer loop) and 26 (inner loop) with metering function -1+C, resulting in the new rules: 28, 29. 5.64/2.66 5.64/2.66 Removing the simple loops: 24 25. 5.64/2.66 5.64/2.66 5.64/2.66 5.64/2.66 Accelerated all simple loops using metering functions (where possible): 5.64/2.66 5.64/2.66 Start location: evalcousot9start 5.64/2.66 5.64/2.66 23: evalcousot9start -> evalcousot9bb1in : A'=B, C'=D, [], cost: 9 5.64/2.66 5.64/2.66 26: evalcousot9bb1in -> evalcousot9bb1in : A'=0, [ C>=1 && A>=1 ], cost: 2*A 5.64/2.66 5.64/2.66 27: evalcousot9bb1in -> evalcousot9bb1in : A'=D, C'=0, [ C>=1 && 0>=A && 0>=D ], cost: 2*C 5.64/2.66 5.64/2.66 28: evalcousot9bb1in -> evalcousot9bb1in : A'=0, C'=1, [ 0>=A && -1+C>=1 && D>=1 ], cost: -2+2*D*(-1+C)+2*C 5.64/2.66 5.64/2.66 29: evalcousot9bb1in -> evalcousot9bb1in : A'=0, C'=1, [ A>=1 && -1+C>=1 && D>=1 ], cost: -2+2*D*(-1+C)+2*C+2*A 5.64/2.66 5.64/2.66 5.64/2.66 5.64/2.66 Chained accelerated rules (with incoming rules): 5.64/2.66 5.64/2.66 Start location: evalcousot9start 5.64/2.66 5.64/2.66 23: evalcousot9start -> evalcousot9bb1in : A'=B, C'=D, [], cost: 9 5.64/2.66 5.64/2.66 30: evalcousot9start -> evalcousot9bb1in : A'=0, C'=D, [ D>=1 && B>=1 ], cost: 9+2*B 5.64/2.66 5.64/2.66 31: evalcousot9start -> evalcousot9bb1in : A'=0, C'=1, [ 0>=B && -1+D>=1 ], cost: 7+2*D+2*(-1+D)*D 5.64/2.66 5.64/2.66 32: evalcousot9start -> evalcousot9bb1in : A'=0, C'=1, [ B>=1 && -1+D>=1 ], cost: 7+2*D+2*(-1+D)*D+2*B 5.64/2.66 5.64/2.66 5.64/2.66 5.64/2.66 Removed unreachable locations (and leaf rules with constant cost): 5.64/2.66 5.64/2.66 Start location: evalcousot9start 5.64/2.66 5.64/2.66 30: evalcousot9start -> evalcousot9bb1in : A'=0, C'=D, [ D>=1 && B>=1 ], cost: 9+2*B 5.64/2.66 5.64/2.66 31: evalcousot9start -> evalcousot9bb1in : A'=0, C'=1, [ 0>=B && -1+D>=1 ], cost: 7+2*D+2*(-1+D)*D 5.64/2.66 5.64/2.66 32: evalcousot9start -> evalcousot9bb1in : A'=0, C'=1, [ B>=1 && -1+D>=1 ], cost: 7+2*D+2*(-1+D)*D+2*B 5.64/2.66 5.64/2.66 5.64/2.66 5.64/2.66 ### Computing asymptotic complexity ### 5.64/2.66 5.64/2.66 5.64/2.66 5.64/2.66 Fully simplified ITS problem 5.64/2.66 5.64/2.66 Start location: evalcousot9start 5.64/2.66 5.64/2.66 30: evalcousot9start -> evalcousot9bb1in : A'=0, C'=D, [ D>=1 && B>=1 ], cost: 9+2*B 5.64/2.66 5.64/2.66 31: evalcousot9start -> evalcousot9bb1in : A'=0, C'=1, [ 0>=B && -1+D>=1 ], cost: 7+2*D+2*(-1+D)*D 5.64/2.66 5.64/2.66 32: evalcousot9start -> evalcousot9bb1in : A'=0, C'=1, [ B>=1 && -1+D>=1 ], cost: 7+2*D+2*(-1+D)*D+2*B 5.64/2.66 5.64/2.66 5.64/2.66 5.64/2.66 Computing asymptotic complexity for rule 30 5.64/2.66 5.64/2.66 Solved the limit problem by the following transformations: 5.64/2.66 5.64/2.66 Created initial limit problem: 5.64/2.66 5.64/2.66 9+2*B (+), D (+/+!), B (+/+!) [not solved] 5.64/2.66 5.64/2.66 5.64/2.66 5.64/2.66 removing all constraints (solved by SMT) 5.64/2.66 5.64/2.66 resulting limit problem: [solved] 5.64/2.66 5.64/2.66 5.64/2.66 5.64/2.66 applying transformation rule (C) using substitution {D==n,B==n} 5.64/2.66 5.64/2.66 resulting limit problem: 5.64/2.66 5.64/2.66 [solved] 5.64/2.66 5.64/2.66 5.64/2.66 5.64/2.66 Solution: 5.64/2.66 5.64/2.66 D / n 5.64/2.66 5.64/2.66 B / n 5.64/2.66 5.64/2.66 Resulting cost 9+2*n has complexity: Poly(n^1) 5.64/2.66 5.64/2.66 5.64/2.66 5.64/2.66 Found new complexity Poly(n^1). 5.64/2.66 5.64/2.66 5.64/2.66 5.64/2.66 Computing asymptotic complexity for rule 31 5.64/2.66 5.64/2.66 Solved the limit problem by the following transformations: 5.64/2.66 5.64/2.66 Created initial limit problem: 5.64/2.66 5.64/2.66 7+2*D^2 (+), -1+D (+/+!), 1-B (+/+!) [not solved] 5.64/2.66 5.64/2.66 5.64/2.66 5.64/2.66 applying transformation rule (C) using substitution {B==0} 5.64/2.66 5.64/2.66 resulting limit problem: 5.64/2.66 5.64/2.66 1 (+/+!), 7+2*D^2 (+), -1+D (+/+!) [not solved] 5.64/2.66 5.64/2.66 5.64/2.66 5.64/2.66 applying transformation rule (B), deleting 1 (+/+!) 5.64/2.66 5.64/2.66 resulting limit problem: 5.64/2.66 5.64/2.66 7+2*D^2 (+), -1+D (+/+!) [not solved] 5.64/2.66 5.64/2.66 5.64/2.66 5.64/2.66 removing all constraints (solved by SMT) 5.64/2.66 5.64/2.66 resulting limit problem: [solved] 5.64/2.66 5.64/2.66 5.64/2.66 5.64/2.66 applying transformation rule (C) using substitution {D==n} 5.64/2.66 5.64/2.66 resulting limit problem: 5.64/2.66 5.64/2.66 [solved] 5.64/2.66 5.64/2.66 5.64/2.66 5.64/2.66 Solution: 5.64/2.66 5.64/2.66 D / n 5.64/2.66 5.64/2.66 B / 0 5.64/2.66 5.64/2.66 Resulting cost 7+2*n^2 has complexity: Poly(n^2) 5.64/2.66 5.64/2.66 5.64/2.66 5.64/2.66 Found new complexity Poly(n^2). 5.64/2.66 5.64/2.66 5.64/2.66 5.64/2.66 Obtained the following overall complexity (w.r.t. the length of the input n): 5.64/2.66 5.64/2.66 Complexity: Poly(n^2) 5.64/2.66 5.64/2.66 Cpx degree: 2 5.64/2.66 5.64/2.66 Solved cost: 7+2*n^2 5.64/2.66 5.64/2.66 Rule cost: 7+2*D+2*(-1+D)*D 5.64/2.66 5.64/2.66 Rule guard: [ 0>=B && -1+D>=1 ] 5.64/2.66 5.64/2.66 5.64/2.66 5.64/2.66 WORST_CASE(Omega(n^2),?) 5.64/2.66 5.64/2.66 5.64/2.66 ---------------------------------------- 5.64/2.66 5.64/2.66 (4) 5.64/2.66 BOUNDS(n^2, INF) 5.82/2.69 EOF