7.66/3.64 WORST_CASE(Omega(n^1), O(n^1)) 7.66/3.65 proof of /export/starexec/sandbox/benchmark/theBenchmark.koat 7.66/3.65 # AProVE Commit ID: 48fb2092695e11cc9f56e44b17a92a5f88ffb256 marcel 20180622 unpublished dirty 7.66/3.65 7.66/3.65 7.66/3.65 The runtime complexity of the given CpxIntTrs could be proven to be BOUNDS(n^1, n^1). 7.66/3.65 7.66/3.65 (0) CpxIntTrs 7.66/3.65 (1) Koat Proof [FINISHED, 231 ms] 7.66/3.65 (2) BOUNDS(1, n^1) 7.66/3.65 (3) Loat Proof [FINISHED, 1927 ms] 7.66/3.65 (4) BOUNDS(n^1, INF) 7.66/3.65 7.66/3.65 7.66/3.65 ---------------------------------------- 7.66/3.65 7.66/3.65 (0) 7.66/3.65 Obligation: 7.66/3.65 Complexity Int TRS consisting of the following rules: 7.66/3.65 eval_wcet1_start(v_1, v_i_0, v_j_0, v_j_3, v_n) -> Com_1(eval_wcet1_bb0_in(v_1, v_i_0, v_j_0, v_j_3, v_n)) :|: TRUE 7.66/3.65 eval_wcet1_bb0_in(v_1, v_i_0, v_j_0, v_j_3, v_n) -> Com_1(eval_wcet1_0(v_1, v_i_0, v_j_0, v_j_3, v_n)) :|: TRUE 7.66/3.65 eval_wcet1_0(v_1, v_i_0, v_j_0, v_j_3, v_n) -> Com_1(eval_wcet1_1(v_1, v_i_0, v_j_0, v_j_3, v_n)) :|: TRUE 7.66/3.65 eval_wcet1_1(v_1, v_i_0, v_j_0, v_j_3, v_n) -> Com_1(eval_wcet1_2(v_1, v_i_0, v_j_0, v_j_3, v_n)) :|: TRUE 7.66/3.65 eval_wcet1_2(v_1, v_i_0, v_j_0, v_j_3, v_n) -> Com_1(eval_wcet1_3(v_1, v_i_0, v_j_0, v_j_3, v_n)) :|: TRUE 7.66/3.65 eval_wcet1_3(v_1, v_i_0, v_j_0, v_j_3, v_n) -> Com_1(eval_wcet1_bb1_in(v_1, v_n, 0, v_j_3, v_n)) :|: v_n >= 1 7.66/3.65 eval_wcet1_3(v_1, v_i_0, v_j_0, v_j_3, v_n) -> Com_1(eval_wcet1_bb5_in(v_1, v_i_0, v_j_0, v_j_3, v_n)) :|: v_n < 1 7.66/3.65 eval_wcet1_bb1_in(v_1, v_i_0, v_j_0, v_j_3, v_n) -> Com_1(eval_wcet1_4(v_1, v_i_0, v_j_0, v_j_3, v_n)) :|: TRUE 7.66/3.65 eval_wcet1_4(v_1, v_i_0, v_j_0, v_j_3, v_n) -> Com_1(eval_wcet1_5(nondef_0, v_i_0, v_j_0, v_j_3, v_n)) :|: TRUE 7.66/3.65 eval_wcet1_5(v_1, v_i_0, v_j_0, v_j_3, v_n) -> Com_1(eval_wcet1_bb2_in(v_1, v_i_0, v_j_0, v_j_3, v_n)) :|: v_1 > 0 7.66/3.65 eval_wcet1_5(v_1, v_i_0, v_j_0, v_j_3, v_n) -> Com_1(eval_wcet1_bb3_in(v_1, v_i_0, v_j_0, v_j_3, v_n)) :|: v_1 <= 0 7.66/3.65 eval_wcet1_bb2_in(v_1, v_i_0, v_j_0, v_j_3, v_n) -> Com_1(eval_wcet1_bb4_in(v_1, v_i_0, v_j_0, 0, v_n)) :|: v_j_0 + 1 >= v_n 7.66/3.65 eval_wcet1_bb2_in(v_1, v_i_0, v_j_0, v_j_3, v_n) -> Com_1(eval_wcet1_bb4_in(v_1, v_i_0, v_j_0, v_j_0 + 1, v_n)) :|: v_j_0 + 1 < v_n 7.66/3.65 eval_wcet1_bb3_in(v_1, v_i_0, v_j_0, v_j_3, v_n) -> Com_1(eval_wcet1_bb4_in(v_1, v_i_0, v_j_0, 0, v_n)) :|: v_j_0 - 1 <= 0 7.66/3.65 eval_wcet1_bb3_in(v_1, v_i_0, v_j_0, v_j_3, v_n) -> Com_1(eval_wcet1_bb4_in(v_1, v_i_0, v_j_0, v_j_0 - 1, v_n)) :|: v_j_0 - 1 > 0 7.66/3.65 eval_wcet1_bb4_in(v_1, v_i_0, v_j_0, v_j_3, v_n) -> Com_1(eval_wcet1_bb1_in(v_1, v_i_0 - 1, v_j_3, v_j_3, v_n)) :|: v_i_0 - 1 > 0 7.66/3.65 eval_wcet1_bb4_in(v_1, v_i_0, v_j_0, v_j_3, v_n) -> Com_1(eval_wcet1_bb5_in(v_1, v_i_0, v_j_0, v_j_3, v_n)) :|: v_i_0 - 1 <= 0 7.66/3.65 eval_wcet1_bb5_in(v_1, v_i_0, v_j_0, v_j_3, v_n) -> Com_1(eval_wcet1_stop(v_1, v_i_0, v_j_0, v_j_3, v_n)) :|: TRUE 7.66/3.65 7.66/3.65 The start-symbols are:[eval_wcet1_start_5] 7.66/3.65 7.66/3.65 7.66/3.65 ---------------------------------------- 7.66/3.65 7.66/3.65 (1) Koat Proof (FINISHED) 7.66/3.65 YES(?, 9*ar_0 + 19) 7.66/3.65 7.66/3.65 7.66/3.65 7.66/3.65 Initial complexity problem: 7.66/3.65 7.66/3.65 1: T: 7.66/3.65 7.66/3.65 (Comp: ?, Cost: 1) evalwcet1start(ar_0, ar_1, ar_2, ar_3, ar_4) -> Com_1(evalwcet1bb0in(ar_0, ar_1, ar_2, ar_3, ar_4)) 7.66/3.65 7.66/3.65 (Comp: ?, Cost: 1) evalwcet1bb0in(ar_0, ar_1, ar_2, ar_3, ar_4) -> Com_1(evalwcet10(ar_0, ar_1, ar_2, ar_3, ar_4)) 7.66/3.65 7.66/3.65 (Comp: ?, Cost: 1) evalwcet10(ar_0, ar_1, ar_2, ar_3, ar_4) -> Com_1(evalwcet11(ar_0, ar_1, ar_2, ar_3, ar_4)) 7.66/3.65 7.66/3.65 (Comp: ?, Cost: 1) evalwcet11(ar_0, ar_1, ar_2, ar_3, ar_4) -> Com_1(evalwcet12(ar_0, ar_1, ar_2, ar_3, ar_4)) 7.66/3.65 7.66/3.65 (Comp: ?, Cost: 1) evalwcet12(ar_0, ar_1, ar_2, ar_3, ar_4) -> Com_1(evalwcet13(ar_0, ar_1, ar_2, ar_3, ar_4)) 7.66/3.65 7.66/3.65 (Comp: ?, Cost: 1) evalwcet13(ar_0, ar_1, ar_2, ar_3, ar_4) -> Com_1(evalwcet1bb1in(ar_0, ar_0, 0, ar_3, ar_4)) [ ar_0 >= 1 ] 7.66/3.65 7.66/3.65 (Comp: ?, Cost: 1) evalwcet13(ar_0, ar_1, ar_2, ar_3, ar_4) -> Com_1(evalwcet1bb5in(ar_0, ar_1, ar_2, ar_3, ar_4)) [ 0 >= ar_0 ] 7.66/3.65 7.66/3.65 (Comp: ?, Cost: 1) evalwcet1bb1in(ar_0, ar_1, ar_2, ar_3, ar_4) -> Com_1(evalwcet14(ar_0, ar_1, ar_2, ar_3, ar_4)) 7.66/3.65 7.66/3.65 (Comp: ?, Cost: 1) evalwcet14(ar_0, ar_1, ar_2, ar_3, ar_4) -> Com_1(evalwcet15(ar_0, ar_1, ar_2, f, ar_4)) 7.66/3.65 7.66/3.65 (Comp: ?, Cost: 1) evalwcet15(ar_0, ar_1, ar_2, ar_3, ar_4) -> Com_1(evalwcet1bb2in(ar_0, ar_1, ar_2, ar_3, ar_4)) [ ar_3 >= 1 ] 7.66/3.65 7.66/3.65 (Comp: ?, Cost: 1) evalwcet15(ar_0, ar_1, ar_2, ar_3, ar_4) -> Com_1(evalwcet1bb3in(ar_0, ar_1, ar_2, ar_3, ar_4)) [ 0 >= ar_3 ] 7.66/3.65 7.66/3.65 (Comp: ?, Cost: 1) evalwcet1bb2in(ar_0, ar_1, ar_2, ar_3, ar_4) -> Com_1(evalwcet1bb4in(ar_0, ar_1, ar_2, ar_3, 0)) [ ar_2 + 1 >= ar_0 ] 7.66/3.65 7.66/3.65 (Comp: ?, Cost: 1) evalwcet1bb2in(ar_0, ar_1, ar_2, ar_3, ar_4) -> Com_1(evalwcet1bb4in(ar_0, ar_1, ar_2, ar_3, ar_2 + 1)) [ ar_0 >= ar_2 + 2 ] 7.66/3.65 7.66/3.65 (Comp: ?, Cost: 1) evalwcet1bb3in(ar_0, ar_1, ar_2, ar_3, ar_4) -> Com_1(evalwcet1bb4in(ar_0, ar_1, ar_2, ar_3, 0)) [ 1 >= ar_2 ] 7.66/3.65 7.66/3.65 (Comp: ?, Cost: 1) evalwcet1bb3in(ar_0, ar_1, ar_2, ar_3, ar_4) -> Com_1(evalwcet1bb4in(ar_0, ar_1, ar_2, ar_3, ar_2 - 1)) [ ar_2 >= 2 ] 7.66/3.65 7.66/3.65 (Comp: ?, Cost: 1) evalwcet1bb4in(ar_0, ar_1, ar_2, ar_3, ar_4) -> Com_1(evalwcet1bb1in(ar_0, ar_1 - 1, ar_4, ar_3, ar_4)) [ ar_1 >= 2 ] 7.66/3.65 7.66/3.65 (Comp: ?, Cost: 1) evalwcet1bb4in(ar_0, ar_1, ar_2, ar_3, ar_4) -> Com_1(evalwcet1bb5in(ar_0, ar_1, ar_2, ar_3, ar_4)) [ 1 >= ar_1 ] 7.66/3.65 7.66/3.65 (Comp: ?, Cost: 1) evalwcet1bb5in(ar_0, ar_1, ar_2, ar_3, ar_4) -> Com_1(evalwcet1stop(ar_0, ar_1, ar_2, ar_3, ar_4)) 7.66/3.65 7.66/3.65 (Comp: 1, Cost: 0) koat_start(ar_0, ar_1, ar_2, ar_3, ar_4) -> Com_1(evalwcet1start(ar_0, ar_1, ar_2, ar_3, ar_4)) [ 0 <= 0 ] 7.66/3.65 7.66/3.65 start location: koat_start 7.66/3.65 7.66/3.65 leaf cost: 0 7.66/3.65 7.66/3.65 7.66/3.65 7.66/3.65 Repeatedly propagating knowledge in problem 1 produces the following problem: 7.66/3.65 7.66/3.65 2: T: 7.66/3.65 7.66/3.65 (Comp: 1, Cost: 1) evalwcet1start(ar_0, ar_1, ar_2, ar_3, ar_4) -> Com_1(evalwcet1bb0in(ar_0, ar_1, ar_2, ar_3, ar_4)) 7.66/3.65 7.66/3.65 (Comp: 1, Cost: 1) evalwcet1bb0in(ar_0, ar_1, ar_2, ar_3, ar_4) -> Com_1(evalwcet10(ar_0, ar_1, ar_2, ar_3, ar_4)) 7.66/3.65 7.66/3.65 (Comp: 1, Cost: 1) evalwcet10(ar_0, ar_1, ar_2, ar_3, ar_4) -> Com_1(evalwcet11(ar_0, ar_1, ar_2, ar_3, ar_4)) 7.66/3.65 7.66/3.65 (Comp: 1, Cost: 1) evalwcet11(ar_0, ar_1, ar_2, ar_3, ar_4) -> Com_1(evalwcet12(ar_0, ar_1, ar_2, ar_3, ar_4)) 7.66/3.65 7.66/3.65 (Comp: 1, Cost: 1) evalwcet12(ar_0, ar_1, ar_2, ar_3, ar_4) -> Com_1(evalwcet13(ar_0, ar_1, ar_2, ar_3, ar_4)) 7.66/3.65 7.66/3.65 (Comp: 1, Cost: 1) evalwcet13(ar_0, ar_1, ar_2, ar_3, ar_4) -> Com_1(evalwcet1bb1in(ar_0, ar_0, 0, ar_3, ar_4)) [ ar_0 >= 1 ] 7.66/3.65 7.66/3.65 (Comp: 1, Cost: 1) evalwcet13(ar_0, ar_1, ar_2, ar_3, ar_4) -> Com_1(evalwcet1bb5in(ar_0, ar_1, ar_2, ar_3, ar_4)) [ 0 >= ar_0 ] 7.66/3.65 7.66/3.65 (Comp: ?, Cost: 1) evalwcet1bb1in(ar_0, ar_1, ar_2, ar_3, ar_4) -> Com_1(evalwcet14(ar_0, ar_1, ar_2, ar_3, ar_4)) 7.66/3.65 7.66/3.65 (Comp: ?, Cost: 1) evalwcet14(ar_0, ar_1, ar_2, ar_3, ar_4) -> Com_1(evalwcet15(ar_0, ar_1, ar_2, f, ar_4)) 7.66/3.65 7.66/3.65 (Comp: ?, Cost: 1) evalwcet15(ar_0, ar_1, ar_2, ar_3, ar_4) -> Com_1(evalwcet1bb2in(ar_0, ar_1, ar_2, ar_3, ar_4)) [ ar_3 >= 1 ] 7.66/3.65 7.66/3.65 (Comp: ?, Cost: 1) evalwcet15(ar_0, ar_1, ar_2, ar_3, ar_4) -> Com_1(evalwcet1bb3in(ar_0, ar_1, ar_2, ar_3, ar_4)) [ 0 >= ar_3 ] 7.66/3.65 7.66/3.65 (Comp: ?, Cost: 1) evalwcet1bb2in(ar_0, ar_1, ar_2, ar_3, ar_4) -> Com_1(evalwcet1bb4in(ar_0, ar_1, ar_2, ar_3, 0)) [ ar_2 + 1 >= ar_0 ] 7.66/3.65 7.66/3.65 (Comp: ?, Cost: 1) evalwcet1bb2in(ar_0, ar_1, ar_2, ar_3, ar_4) -> Com_1(evalwcet1bb4in(ar_0, ar_1, ar_2, ar_3, ar_2 + 1)) [ ar_0 >= ar_2 + 2 ] 7.66/3.65 7.66/3.65 (Comp: ?, Cost: 1) evalwcet1bb3in(ar_0, ar_1, ar_2, ar_3, ar_4) -> Com_1(evalwcet1bb4in(ar_0, ar_1, ar_2, ar_3, 0)) [ 1 >= ar_2 ] 7.66/3.65 7.66/3.65 (Comp: ?, Cost: 1) evalwcet1bb3in(ar_0, ar_1, ar_2, ar_3, ar_4) -> Com_1(evalwcet1bb4in(ar_0, ar_1, ar_2, ar_3, ar_2 - 1)) [ ar_2 >= 2 ] 7.66/3.65 7.66/3.65 (Comp: ?, Cost: 1) evalwcet1bb4in(ar_0, ar_1, ar_2, ar_3, ar_4) -> Com_1(evalwcet1bb1in(ar_0, ar_1 - 1, ar_4, ar_3, ar_4)) [ ar_1 >= 2 ] 7.66/3.65 7.66/3.65 (Comp: ?, Cost: 1) evalwcet1bb4in(ar_0, ar_1, ar_2, ar_3, ar_4) -> Com_1(evalwcet1bb5in(ar_0, ar_1, ar_2, ar_3, ar_4)) [ 1 >= ar_1 ] 7.66/3.65 7.66/3.65 (Comp: ?, Cost: 1) evalwcet1bb5in(ar_0, ar_1, ar_2, ar_3, ar_4) -> Com_1(evalwcet1stop(ar_0, ar_1, ar_2, ar_3, ar_4)) 7.66/3.65 7.66/3.65 (Comp: 1, Cost: 0) koat_start(ar_0, ar_1, ar_2, ar_3, ar_4) -> Com_1(evalwcet1start(ar_0, ar_1, ar_2, ar_3, ar_4)) [ 0 <= 0 ] 7.66/3.65 7.66/3.65 start location: koat_start 7.66/3.65 7.66/3.65 leaf cost: 0 7.66/3.65 7.66/3.65 7.66/3.65 7.66/3.65 A polynomial rank function with 7.66/3.65 7.66/3.65 Pol(evalwcet1start) = 2 7.66/3.65 7.66/3.65 Pol(evalwcet1bb0in) = 2 7.66/3.65 7.66/3.65 Pol(evalwcet10) = 2 7.66/3.65 7.66/3.65 Pol(evalwcet11) = 2 7.66/3.65 7.66/3.65 Pol(evalwcet12) = 2 7.66/3.65 7.66/3.65 Pol(evalwcet13) = 2 7.66/3.65 7.66/3.65 Pol(evalwcet1bb1in) = 2 7.66/3.65 7.66/3.65 Pol(evalwcet1bb5in) = 1 7.66/3.65 7.66/3.65 Pol(evalwcet14) = 2 7.66/3.65 7.66/3.65 Pol(evalwcet15) = 2 7.66/3.65 7.66/3.65 Pol(evalwcet1bb2in) = 2 7.66/3.65 7.66/3.65 Pol(evalwcet1bb3in) = 2 7.66/3.65 7.66/3.65 Pol(evalwcet1bb4in) = 2 7.66/3.65 7.66/3.65 Pol(evalwcet1stop) = 0 7.66/3.65 7.66/3.65 Pol(koat_start) = 2 7.66/3.65 7.66/3.65 orients all transitions weakly and the transitions 7.66/3.65 7.66/3.65 evalwcet1bb5in(ar_0, ar_1, ar_2, ar_3, ar_4) -> Com_1(evalwcet1stop(ar_0, ar_1, ar_2, ar_3, ar_4)) 7.66/3.65 7.66/3.65 evalwcet1bb4in(ar_0, ar_1, ar_2, ar_3, ar_4) -> Com_1(evalwcet1bb5in(ar_0, ar_1, ar_2, ar_3, ar_4)) [ 1 >= ar_1 ] 7.66/3.65 7.66/3.65 strictly and produces the following problem: 7.66/3.65 7.66/3.65 3: T: 7.66/3.65 7.66/3.65 (Comp: 1, Cost: 1) evalwcet1start(ar_0, ar_1, ar_2, ar_3, ar_4) -> Com_1(evalwcet1bb0in(ar_0, ar_1, ar_2, ar_3, ar_4)) 7.66/3.65 7.66/3.65 (Comp: 1, Cost: 1) evalwcet1bb0in(ar_0, ar_1, ar_2, ar_3, ar_4) -> Com_1(evalwcet10(ar_0, ar_1, ar_2, ar_3, ar_4)) 7.66/3.65 7.66/3.65 (Comp: 1, Cost: 1) evalwcet10(ar_0, ar_1, ar_2, ar_3, ar_4) -> Com_1(evalwcet11(ar_0, ar_1, ar_2, ar_3, ar_4)) 7.66/3.65 7.66/3.65 (Comp: 1, Cost: 1) evalwcet11(ar_0, ar_1, ar_2, ar_3, ar_4) -> Com_1(evalwcet12(ar_0, ar_1, ar_2, ar_3, ar_4)) 7.66/3.65 7.66/3.65 (Comp: 1, Cost: 1) evalwcet12(ar_0, ar_1, ar_2, ar_3, ar_4) -> Com_1(evalwcet13(ar_0, ar_1, ar_2, ar_3, ar_4)) 7.66/3.65 7.66/3.65 (Comp: 1, Cost: 1) evalwcet13(ar_0, ar_1, ar_2, ar_3, ar_4) -> Com_1(evalwcet1bb1in(ar_0, ar_0, 0, ar_3, ar_4)) [ ar_0 >= 1 ] 7.66/3.65 7.66/3.65 (Comp: 1, Cost: 1) evalwcet13(ar_0, ar_1, ar_2, ar_3, ar_4) -> Com_1(evalwcet1bb5in(ar_0, ar_1, ar_2, ar_3, ar_4)) [ 0 >= ar_0 ] 7.66/3.65 7.66/3.65 (Comp: ?, Cost: 1) evalwcet1bb1in(ar_0, ar_1, ar_2, ar_3, ar_4) -> Com_1(evalwcet14(ar_0, ar_1, ar_2, ar_3, ar_4)) 7.66/3.65 7.66/3.65 (Comp: ?, Cost: 1) evalwcet14(ar_0, ar_1, ar_2, ar_3, ar_4) -> Com_1(evalwcet15(ar_0, ar_1, ar_2, f, ar_4)) 7.66/3.65 7.66/3.65 (Comp: ?, Cost: 1) evalwcet15(ar_0, ar_1, ar_2, ar_3, ar_4) -> Com_1(evalwcet1bb2in(ar_0, ar_1, ar_2, ar_3, ar_4)) [ ar_3 >= 1 ] 7.66/3.65 7.66/3.65 (Comp: ?, Cost: 1) evalwcet15(ar_0, ar_1, ar_2, ar_3, ar_4) -> Com_1(evalwcet1bb3in(ar_0, ar_1, ar_2, ar_3, ar_4)) [ 0 >= ar_3 ] 7.66/3.65 7.66/3.65 (Comp: ?, Cost: 1) evalwcet1bb2in(ar_0, ar_1, ar_2, ar_3, ar_4) -> Com_1(evalwcet1bb4in(ar_0, ar_1, ar_2, ar_3, 0)) [ ar_2 + 1 >= ar_0 ] 7.66/3.65 7.66/3.65 (Comp: ?, Cost: 1) evalwcet1bb2in(ar_0, ar_1, ar_2, ar_3, ar_4) -> Com_1(evalwcet1bb4in(ar_0, ar_1, ar_2, ar_3, ar_2 + 1)) [ ar_0 >= ar_2 + 2 ] 7.66/3.65 7.66/3.65 (Comp: ?, Cost: 1) evalwcet1bb3in(ar_0, ar_1, ar_2, ar_3, ar_4) -> Com_1(evalwcet1bb4in(ar_0, ar_1, ar_2, ar_3, 0)) [ 1 >= ar_2 ] 7.66/3.65 7.66/3.65 (Comp: ?, Cost: 1) evalwcet1bb3in(ar_0, ar_1, ar_2, ar_3, ar_4) -> Com_1(evalwcet1bb4in(ar_0, ar_1, ar_2, ar_3, ar_2 - 1)) [ ar_2 >= 2 ] 7.66/3.65 7.66/3.65 (Comp: ?, Cost: 1) evalwcet1bb4in(ar_0, ar_1, ar_2, ar_3, ar_4) -> Com_1(evalwcet1bb1in(ar_0, ar_1 - 1, ar_4, ar_3, ar_4)) [ ar_1 >= 2 ] 7.66/3.65 7.66/3.65 (Comp: 2, Cost: 1) evalwcet1bb4in(ar_0, ar_1, ar_2, ar_3, ar_4) -> Com_1(evalwcet1bb5in(ar_0, ar_1, ar_2, ar_3, ar_4)) [ 1 >= ar_1 ] 7.66/3.65 7.66/3.65 (Comp: 2, Cost: 1) evalwcet1bb5in(ar_0, ar_1, ar_2, ar_3, ar_4) -> Com_1(evalwcet1stop(ar_0, ar_1, ar_2, ar_3, ar_4)) 7.66/3.65 7.66/3.65 (Comp: 1, Cost: 0) koat_start(ar_0, ar_1, ar_2, ar_3, ar_4) -> Com_1(evalwcet1start(ar_0, ar_1, ar_2, ar_3, ar_4)) [ 0 <= 0 ] 7.66/3.65 7.66/3.65 start location: koat_start 7.66/3.65 7.66/3.65 leaf cost: 0 7.66/3.65 7.66/3.65 7.66/3.65 7.66/3.65 A polynomial rank function with 7.66/3.65 7.66/3.65 Pol(evalwcet1bb4in) = V_2 7.66/3.65 7.66/3.65 Pol(evalwcet1bb1in) = V_2 7.66/3.65 7.66/3.65 Pol(evalwcet1bb3in) = V_2 7.66/3.65 7.66/3.65 Pol(evalwcet1bb2in) = V_2 7.66/3.65 7.66/3.65 Pol(evalwcet14) = V_2 7.66/3.65 7.66/3.65 Pol(evalwcet15) = V_2 7.66/3.65 7.66/3.65 and size complexities 7.66/3.65 7.66/3.65 S("koat_start(ar_0, ar_1, ar_2, ar_3, ar_4) -> Com_1(evalwcet1start(ar_0, ar_1, ar_2, ar_3, ar_4)) [ 0 <= 0 ]", 0-0) = ar_0 7.66/3.65 7.66/3.65 S("koat_start(ar_0, ar_1, ar_2, ar_3, ar_4) -> Com_1(evalwcet1start(ar_0, ar_1, ar_2, ar_3, ar_4)) [ 0 <= 0 ]", 0-1) = ar_1 7.66/3.65 7.66/3.65 S("koat_start(ar_0, ar_1, ar_2, ar_3, ar_4) -> Com_1(evalwcet1start(ar_0, ar_1, ar_2, ar_3, ar_4)) [ 0 <= 0 ]", 0-2) = ar_2 7.66/3.65 7.66/3.65 S("koat_start(ar_0, ar_1, ar_2, ar_3, ar_4) -> Com_1(evalwcet1start(ar_0, ar_1, ar_2, ar_3, ar_4)) [ 0 <= 0 ]", 0-3) = ar_3 7.66/3.65 7.66/3.65 S("koat_start(ar_0, ar_1, ar_2, ar_3, ar_4) -> Com_1(evalwcet1start(ar_0, ar_1, ar_2, ar_3, ar_4)) [ 0 <= 0 ]", 0-4) = ar_4 7.66/3.65 7.66/3.65 S("evalwcet1bb5in(ar_0, ar_1, ar_2, ar_3, ar_4) -> Com_1(evalwcet1stop(ar_0, ar_1, ar_2, ar_3, ar_4))", 0-0) = ar_0 7.66/3.65 7.66/3.65 S("evalwcet1bb5in(ar_0, ar_1, ar_2, ar_3, ar_4) -> Com_1(evalwcet1stop(ar_0, ar_1, ar_2, ar_3, ar_4))", 0-1) = ar_0 + ar_1 7.66/3.65 7.66/3.65 S("evalwcet1bb5in(ar_0, ar_1, ar_2, ar_3, ar_4) -> Com_1(evalwcet1stop(ar_0, ar_1, ar_2, ar_3, ar_4))", 0-2) = ? 7.66/3.65 7.66/3.65 S("evalwcet1bb5in(ar_0, ar_1, ar_2, ar_3, ar_4) -> Com_1(evalwcet1stop(ar_0, ar_1, ar_2, ar_3, ar_4))", 0-3) = ? 7.66/3.65 7.66/3.65 S("evalwcet1bb5in(ar_0, ar_1, ar_2, ar_3, ar_4) -> Com_1(evalwcet1stop(ar_0, ar_1, ar_2, ar_3, ar_4))", 0-4) = ? 7.66/3.65 7.66/3.65 S("evalwcet1bb4in(ar_0, ar_1, ar_2, ar_3, ar_4) -> Com_1(evalwcet1bb5in(ar_0, ar_1, ar_2, ar_3, ar_4)) [ 1 >= ar_1 ]", 0-0) = ar_0 7.66/3.65 7.66/3.65 S("evalwcet1bb4in(ar_0, ar_1, ar_2, ar_3, ar_4) -> Com_1(evalwcet1bb5in(ar_0, ar_1, ar_2, ar_3, ar_4)) [ 1 >= ar_1 ]", 0-1) = ar_0 7.66/3.65 7.66/3.65 S("evalwcet1bb4in(ar_0, ar_1, ar_2, ar_3, ar_4) -> Com_1(evalwcet1bb5in(ar_0, ar_1, ar_2, ar_3, ar_4)) [ 1 >= ar_1 ]", 0-2) = ? 7.66/3.65 7.66/3.65 S("evalwcet1bb4in(ar_0, ar_1, ar_2, ar_3, ar_4) -> Com_1(evalwcet1bb5in(ar_0, ar_1, ar_2, ar_3, ar_4)) [ 1 >= ar_1 ]", 0-3) = ? 7.66/3.65 7.66/3.65 S("evalwcet1bb4in(ar_0, ar_1, ar_2, ar_3, ar_4) -> Com_1(evalwcet1bb5in(ar_0, ar_1, ar_2, ar_3, ar_4)) [ 1 >= ar_1 ]", 0-4) = ? 7.66/3.65 7.66/3.65 S("evalwcet1bb4in(ar_0, ar_1, ar_2, ar_3, ar_4) -> Com_1(evalwcet1bb1in(ar_0, ar_1 - 1, ar_4, ar_3, ar_4)) [ ar_1 >= 2 ]", 0-0) = ar_0 7.66/3.65 7.66/3.65 S("evalwcet1bb4in(ar_0, ar_1, ar_2, ar_3, ar_4) -> Com_1(evalwcet1bb1in(ar_0, ar_1 - 1, ar_4, ar_3, ar_4)) [ ar_1 >= 2 ]", 0-1) = ar_0 7.66/3.65 7.66/3.65 S("evalwcet1bb4in(ar_0, ar_1, ar_2, ar_3, ar_4) -> Com_1(evalwcet1bb1in(ar_0, ar_1 - 1, ar_4, ar_3, ar_4)) [ ar_1 >= 2 ]", 0-2) = ? 7.66/3.65 7.66/3.65 S("evalwcet1bb4in(ar_0, ar_1, ar_2, ar_3, ar_4) -> Com_1(evalwcet1bb1in(ar_0, ar_1 - 1, ar_4, ar_3, ar_4)) [ ar_1 >= 2 ]", 0-3) = ? 7.66/3.65 7.66/3.65 S("evalwcet1bb4in(ar_0, ar_1, ar_2, ar_3, ar_4) -> Com_1(evalwcet1bb1in(ar_0, ar_1 - 1, ar_4, ar_3, ar_4)) [ ar_1 >= 2 ]", 0-4) = ? 7.66/3.65 7.66/3.65 S("evalwcet1bb3in(ar_0, ar_1, ar_2, ar_3, ar_4) -> Com_1(evalwcet1bb4in(ar_0, ar_1, ar_2, ar_3, ar_2 - 1)) [ ar_2 >= 2 ]", 0-0) = ar_0 7.66/3.65 7.66/3.65 S("evalwcet1bb3in(ar_0, ar_1, ar_2, ar_3, ar_4) -> Com_1(evalwcet1bb4in(ar_0, ar_1, ar_2, ar_3, ar_2 - 1)) [ ar_2 >= 2 ]", 0-1) = ar_0 7.66/3.65 7.66/3.65 S("evalwcet1bb3in(ar_0, ar_1, ar_2, ar_3, ar_4) -> Com_1(evalwcet1bb4in(ar_0, ar_1, ar_2, ar_3, ar_2 - 1)) [ ar_2 >= 2 ]", 0-2) = ? 7.66/3.65 7.66/3.65 S("evalwcet1bb3in(ar_0, ar_1, ar_2, ar_3, ar_4) -> Com_1(evalwcet1bb4in(ar_0, ar_1, ar_2, ar_3, ar_2 - 1)) [ ar_2 >= 2 ]", 0-3) = ? 7.66/3.65 7.66/3.65 S("evalwcet1bb3in(ar_0, ar_1, ar_2, ar_3, ar_4) -> Com_1(evalwcet1bb4in(ar_0, ar_1, ar_2, ar_3, ar_2 - 1)) [ ar_2 >= 2 ]", 0-4) = ? 7.66/3.65 7.66/3.65 S("evalwcet1bb3in(ar_0, ar_1, ar_2, ar_3, ar_4) -> Com_1(evalwcet1bb4in(ar_0, ar_1, ar_2, ar_3, 0)) [ 1 >= ar_2 ]", 0-0) = ar_0 7.66/3.65 7.66/3.65 S("evalwcet1bb3in(ar_0, ar_1, ar_2, ar_3, ar_4) -> Com_1(evalwcet1bb4in(ar_0, ar_1, ar_2, ar_3, 0)) [ 1 >= ar_2 ]", 0-1) = ar_0 7.66/3.65 7.66/3.65 S("evalwcet1bb3in(ar_0, ar_1, ar_2, ar_3, ar_4) -> Com_1(evalwcet1bb4in(ar_0, ar_1, ar_2, ar_3, 0)) [ 1 >= ar_2 ]", 0-2) = ? 7.66/3.65 7.66/3.65 S("evalwcet1bb3in(ar_0, ar_1, ar_2, ar_3, ar_4) -> Com_1(evalwcet1bb4in(ar_0, ar_1, ar_2, ar_3, 0)) [ 1 >= ar_2 ]", 0-3) = ? 7.66/3.65 7.66/3.65 S("evalwcet1bb3in(ar_0, ar_1, ar_2, ar_3, ar_4) -> Com_1(evalwcet1bb4in(ar_0, ar_1, ar_2, ar_3, 0)) [ 1 >= ar_2 ]", 0-4) = 0 7.66/3.65 7.66/3.65 S("evalwcet1bb2in(ar_0, ar_1, ar_2, ar_3, ar_4) -> Com_1(evalwcet1bb4in(ar_0, ar_1, ar_2, ar_3, ar_2 + 1)) [ ar_0 >= ar_2 + 2 ]", 0-0) = ar_0 7.66/3.65 7.66/3.65 S("evalwcet1bb2in(ar_0, ar_1, ar_2, ar_3, ar_4) -> Com_1(evalwcet1bb4in(ar_0, ar_1, ar_2, ar_3, ar_2 + 1)) [ ar_0 >= ar_2 + 2 ]", 0-1) = ar_0 7.66/3.65 7.66/3.65 S("evalwcet1bb2in(ar_0, ar_1, ar_2, ar_3, ar_4) -> Com_1(evalwcet1bb4in(ar_0, ar_1, ar_2, ar_3, ar_2 + 1)) [ ar_0 >= ar_2 + 2 ]", 0-2) = ? 7.66/3.65 7.66/3.65 S("evalwcet1bb2in(ar_0, ar_1, ar_2, ar_3, ar_4) -> Com_1(evalwcet1bb4in(ar_0, ar_1, ar_2, ar_3, ar_2 + 1)) [ ar_0 >= ar_2 + 2 ]", 0-3) = ? 7.66/3.65 7.66/3.65 S("evalwcet1bb2in(ar_0, ar_1, ar_2, ar_3, ar_4) -> Com_1(evalwcet1bb4in(ar_0, ar_1, ar_2, ar_3, ar_2 + 1)) [ ar_0 >= ar_2 + 2 ]", 0-4) = ? 7.66/3.65 7.66/3.65 S("evalwcet1bb2in(ar_0, ar_1, ar_2, ar_3, ar_4) -> Com_1(evalwcet1bb4in(ar_0, ar_1, ar_2, ar_3, 0)) [ ar_2 + 1 >= ar_0 ]", 0-0) = ar_0 7.66/3.65 7.66/3.65 S("evalwcet1bb2in(ar_0, ar_1, ar_2, ar_3, ar_4) -> Com_1(evalwcet1bb4in(ar_0, ar_1, ar_2, ar_3, 0)) [ ar_2 + 1 >= ar_0 ]", 0-1) = ar_0 7.66/3.65 7.66/3.65 S("evalwcet1bb2in(ar_0, ar_1, ar_2, ar_3, ar_4) -> Com_1(evalwcet1bb4in(ar_0, ar_1, ar_2, ar_3, 0)) [ ar_2 + 1 >= ar_0 ]", 0-2) = ? 7.66/3.65 7.66/3.65 S("evalwcet1bb2in(ar_0, ar_1, ar_2, ar_3, ar_4) -> Com_1(evalwcet1bb4in(ar_0, ar_1, ar_2, ar_3, 0)) [ ar_2 + 1 >= ar_0 ]", 0-3) = ? 7.66/3.65 7.66/3.65 S("evalwcet1bb2in(ar_0, ar_1, ar_2, ar_3, ar_4) -> Com_1(evalwcet1bb4in(ar_0, ar_1, ar_2, ar_3, 0)) [ ar_2 + 1 >= ar_0 ]", 0-4) = 0 7.66/3.65 7.66/3.65 S("evalwcet15(ar_0, ar_1, ar_2, ar_3, ar_4) -> Com_1(evalwcet1bb3in(ar_0, ar_1, ar_2, ar_3, ar_4)) [ 0 >= ar_3 ]", 0-0) = ar_0 7.66/3.65 7.66/3.65 S("evalwcet15(ar_0, ar_1, ar_2, ar_3, ar_4) -> Com_1(evalwcet1bb3in(ar_0, ar_1, ar_2, ar_3, ar_4)) [ 0 >= ar_3 ]", 0-1) = ar_0 7.66/3.65 7.66/3.65 S("evalwcet15(ar_0, ar_1, ar_2, ar_3, ar_4) -> Com_1(evalwcet1bb3in(ar_0, ar_1, ar_2, ar_3, ar_4)) [ 0 >= ar_3 ]", 0-2) = ? 7.66/3.65 7.66/3.65 S("evalwcet15(ar_0, ar_1, ar_2, ar_3, ar_4) -> Com_1(evalwcet1bb3in(ar_0, ar_1, ar_2, ar_3, ar_4)) [ 0 >= ar_3 ]", 0-3) = ? 7.66/3.65 7.66/3.65 S("evalwcet15(ar_0, ar_1, ar_2, ar_3, ar_4) -> Com_1(evalwcet1bb3in(ar_0, ar_1, ar_2, ar_3, ar_4)) [ 0 >= ar_3 ]", 0-4) = ? 7.66/3.65 7.66/3.65 S("evalwcet15(ar_0, ar_1, ar_2, ar_3, ar_4) -> Com_1(evalwcet1bb2in(ar_0, ar_1, ar_2, ar_3, ar_4)) [ ar_3 >= 1 ]", 0-0) = ar_0 7.66/3.65 7.66/3.65 S("evalwcet15(ar_0, ar_1, ar_2, ar_3, ar_4) -> Com_1(evalwcet1bb2in(ar_0, ar_1, ar_2, ar_3, ar_4)) [ ar_3 >= 1 ]", 0-1) = ar_0 7.66/3.65 7.66/3.65 S("evalwcet15(ar_0, ar_1, ar_2, ar_3, ar_4) -> Com_1(evalwcet1bb2in(ar_0, ar_1, ar_2, ar_3, ar_4)) [ ar_3 >= 1 ]", 0-2) = ? 7.66/3.65 7.66/3.65 S("evalwcet15(ar_0, ar_1, ar_2, ar_3, ar_4) -> Com_1(evalwcet1bb2in(ar_0, ar_1, ar_2, ar_3, ar_4)) [ ar_3 >= 1 ]", 0-3) = ? 7.66/3.65 7.66/3.65 S("evalwcet15(ar_0, ar_1, ar_2, ar_3, ar_4) -> Com_1(evalwcet1bb2in(ar_0, ar_1, ar_2, ar_3, ar_4)) [ ar_3 >= 1 ]", 0-4) = ? 7.66/3.65 7.66/3.65 S("evalwcet14(ar_0, ar_1, ar_2, ar_3, ar_4) -> Com_1(evalwcet15(ar_0, ar_1, ar_2, f, ar_4))", 0-0) = ar_0 7.66/3.65 7.66/3.65 S("evalwcet14(ar_0, ar_1, ar_2, ar_3, ar_4) -> Com_1(evalwcet15(ar_0, ar_1, ar_2, f, ar_4))", 0-1) = ar_0 7.66/3.65 7.66/3.65 S("evalwcet14(ar_0, ar_1, ar_2, ar_3, ar_4) -> Com_1(evalwcet15(ar_0, ar_1, ar_2, f, ar_4))", 0-2) = ? 7.66/3.65 7.66/3.65 S("evalwcet14(ar_0, ar_1, ar_2, ar_3, ar_4) -> Com_1(evalwcet15(ar_0, ar_1, ar_2, f, ar_4))", 0-3) = ? 7.66/3.65 7.66/3.65 S("evalwcet14(ar_0, ar_1, ar_2, ar_3, ar_4) -> Com_1(evalwcet15(ar_0, ar_1, ar_2, f, ar_4))", 0-4) = ? 7.66/3.65 7.66/3.65 S("evalwcet1bb1in(ar_0, ar_1, ar_2, ar_3, ar_4) -> Com_1(evalwcet14(ar_0, ar_1, ar_2, ar_3, ar_4))", 0-0) = ar_0 7.66/3.65 7.66/3.65 S("evalwcet1bb1in(ar_0, ar_1, ar_2, ar_3, ar_4) -> Com_1(evalwcet14(ar_0, ar_1, ar_2, ar_3, ar_4))", 0-1) = ar_0 7.66/3.65 7.66/3.65 S("evalwcet1bb1in(ar_0, ar_1, ar_2, ar_3, ar_4) -> Com_1(evalwcet14(ar_0, ar_1, ar_2, ar_3, ar_4))", 0-2) = ? 7.66/3.65 7.66/3.65 S("evalwcet1bb1in(ar_0, ar_1, ar_2, ar_3, ar_4) -> Com_1(evalwcet14(ar_0, ar_1, ar_2, ar_3, ar_4))", 0-3) = ? 7.66/3.65 7.66/3.65 S("evalwcet1bb1in(ar_0, ar_1, ar_2, ar_3, ar_4) -> Com_1(evalwcet14(ar_0, ar_1, ar_2, ar_3, ar_4))", 0-4) = ? 7.66/3.65 7.66/3.65 S("evalwcet13(ar_0, ar_1, ar_2, ar_3, ar_4) -> Com_1(evalwcet1bb5in(ar_0, ar_1, ar_2, ar_3, ar_4)) [ 0 >= ar_0 ]", 0-0) = ar_0 7.66/3.65 7.66/3.65 S("evalwcet13(ar_0, ar_1, ar_2, ar_3, ar_4) -> Com_1(evalwcet1bb5in(ar_0, ar_1, ar_2, ar_3, ar_4)) [ 0 >= ar_0 ]", 0-1) = ar_1 7.66/3.65 7.66/3.65 S("evalwcet13(ar_0, ar_1, ar_2, ar_3, ar_4) -> Com_1(evalwcet1bb5in(ar_0, ar_1, ar_2, ar_3, ar_4)) [ 0 >= ar_0 ]", 0-2) = ar_2 7.66/3.65 7.66/3.65 S("evalwcet13(ar_0, ar_1, ar_2, ar_3, ar_4) -> Com_1(evalwcet1bb5in(ar_0, ar_1, ar_2, ar_3, ar_4)) [ 0 >= ar_0 ]", 0-3) = ar_3 7.66/3.65 7.66/3.65 S("evalwcet13(ar_0, ar_1, ar_2, ar_3, ar_4) -> Com_1(evalwcet1bb5in(ar_0, ar_1, ar_2, ar_3, ar_4)) [ 0 >= ar_0 ]", 0-4) = ar_4 7.66/3.65 7.66/3.65 S("evalwcet13(ar_0, ar_1, ar_2, ar_3, ar_4) -> Com_1(evalwcet1bb1in(ar_0, ar_0, 0, ar_3, ar_4)) [ ar_0 >= 1 ]", 0-0) = ar_0 7.66/3.65 7.66/3.65 S("evalwcet13(ar_0, ar_1, ar_2, ar_3, ar_4) -> Com_1(evalwcet1bb1in(ar_0, ar_0, 0, ar_3, ar_4)) [ ar_0 >= 1 ]", 0-1) = ar_0 7.66/3.65 7.66/3.65 S("evalwcet13(ar_0, ar_1, ar_2, ar_3, ar_4) -> Com_1(evalwcet1bb1in(ar_0, ar_0, 0, ar_3, ar_4)) [ ar_0 >= 1 ]", 0-2) = 0 7.66/3.65 7.66/3.65 S("evalwcet13(ar_0, ar_1, ar_2, ar_3, ar_4) -> Com_1(evalwcet1bb1in(ar_0, ar_0, 0, ar_3, ar_4)) [ ar_0 >= 1 ]", 0-3) = ar_3 7.66/3.65 7.66/3.65 S("evalwcet13(ar_0, ar_1, ar_2, ar_3, ar_4) -> Com_1(evalwcet1bb1in(ar_0, ar_0, 0, ar_3, ar_4)) [ ar_0 >= 1 ]", 0-4) = ar_4 7.66/3.65 7.66/3.65 S("evalwcet12(ar_0, ar_1, ar_2, ar_3, ar_4) -> Com_1(evalwcet13(ar_0, ar_1, ar_2, ar_3, ar_4))", 0-0) = ar_0 7.66/3.65 7.66/3.65 S("evalwcet12(ar_0, ar_1, ar_2, ar_3, ar_4) -> Com_1(evalwcet13(ar_0, ar_1, ar_2, ar_3, ar_4))", 0-1) = ar_1 7.66/3.65 7.66/3.65 S("evalwcet12(ar_0, ar_1, ar_2, ar_3, ar_4) -> Com_1(evalwcet13(ar_0, ar_1, ar_2, ar_3, ar_4))", 0-2) = ar_2 7.66/3.65 7.66/3.65 S("evalwcet12(ar_0, ar_1, ar_2, ar_3, ar_4) -> Com_1(evalwcet13(ar_0, ar_1, ar_2, ar_3, ar_4))", 0-3) = ar_3 7.66/3.65 7.66/3.65 S("evalwcet12(ar_0, ar_1, ar_2, ar_3, ar_4) -> Com_1(evalwcet13(ar_0, ar_1, ar_2, ar_3, ar_4))", 0-4) = ar_4 7.66/3.65 7.66/3.65 S("evalwcet11(ar_0, ar_1, ar_2, ar_3, ar_4) -> Com_1(evalwcet12(ar_0, ar_1, ar_2, ar_3, ar_4))", 0-0) = ar_0 7.66/3.65 7.66/3.65 S("evalwcet11(ar_0, ar_1, ar_2, ar_3, ar_4) -> Com_1(evalwcet12(ar_0, ar_1, ar_2, ar_3, ar_4))", 0-1) = ar_1 7.66/3.65 7.66/3.65 S("evalwcet11(ar_0, ar_1, ar_2, ar_3, ar_4) -> Com_1(evalwcet12(ar_0, ar_1, ar_2, ar_3, ar_4))", 0-2) = ar_2 7.66/3.65 7.66/3.65 S("evalwcet11(ar_0, ar_1, ar_2, ar_3, ar_4) -> Com_1(evalwcet12(ar_0, ar_1, ar_2, ar_3, ar_4))", 0-3) = ar_3 7.66/3.65 7.66/3.65 S("evalwcet11(ar_0, ar_1, ar_2, ar_3, ar_4) -> Com_1(evalwcet12(ar_0, ar_1, ar_2, ar_3, ar_4))", 0-4) = ar_4 7.66/3.65 7.66/3.65 S("evalwcet10(ar_0, ar_1, ar_2, ar_3, ar_4) -> Com_1(evalwcet11(ar_0, ar_1, ar_2, ar_3, ar_4))", 0-0) = ar_0 7.66/3.65 7.66/3.65 S("evalwcet10(ar_0, ar_1, ar_2, ar_3, ar_4) -> Com_1(evalwcet11(ar_0, ar_1, ar_2, ar_3, ar_4))", 0-1) = ar_1 7.66/3.65 7.66/3.65 S("evalwcet10(ar_0, ar_1, ar_2, ar_3, ar_4) -> Com_1(evalwcet11(ar_0, ar_1, ar_2, ar_3, ar_4))", 0-2) = ar_2 7.66/3.65 7.66/3.65 S("evalwcet10(ar_0, ar_1, ar_2, ar_3, ar_4) -> Com_1(evalwcet11(ar_0, ar_1, ar_2, ar_3, ar_4))", 0-3) = ar_3 7.66/3.65 7.66/3.65 S("evalwcet10(ar_0, ar_1, ar_2, ar_3, ar_4) -> Com_1(evalwcet11(ar_0, ar_1, ar_2, ar_3, ar_4))", 0-4) = ar_4 7.66/3.65 7.66/3.65 S("evalwcet1bb0in(ar_0, ar_1, ar_2, ar_3, ar_4) -> Com_1(evalwcet10(ar_0, ar_1, ar_2, ar_3, ar_4))", 0-0) = ar_0 7.66/3.65 7.66/3.65 S("evalwcet1bb0in(ar_0, ar_1, ar_2, ar_3, ar_4) -> Com_1(evalwcet10(ar_0, ar_1, ar_2, ar_3, ar_4))", 0-1) = ar_1 7.66/3.65 7.66/3.65 S("evalwcet1bb0in(ar_0, ar_1, ar_2, ar_3, ar_4) -> Com_1(evalwcet10(ar_0, ar_1, ar_2, ar_3, ar_4))", 0-2) = ar_2 7.66/3.65 7.66/3.65 S("evalwcet1bb0in(ar_0, ar_1, ar_2, ar_3, ar_4) -> Com_1(evalwcet10(ar_0, ar_1, ar_2, ar_3, ar_4))", 0-3) = ar_3 7.66/3.65 7.66/3.65 S("evalwcet1bb0in(ar_0, ar_1, ar_2, ar_3, ar_4) -> Com_1(evalwcet10(ar_0, ar_1, ar_2, ar_3, ar_4))", 0-4) = ar_4 7.66/3.65 7.66/3.65 S("evalwcet1start(ar_0, ar_1, ar_2, ar_3, ar_4) -> Com_1(evalwcet1bb0in(ar_0, ar_1, ar_2, ar_3, ar_4))", 0-0) = ar_0 7.66/3.65 7.66/3.65 S("evalwcet1start(ar_0, ar_1, ar_2, ar_3, ar_4) -> Com_1(evalwcet1bb0in(ar_0, ar_1, ar_2, ar_3, ar_4))", 0-1) = ar_1 7.66/3.65 7.66/3.65 S("evalwcet1start(ar_0, ar_1, ar_2, ar_3, ar_4) -> Com_1(evalwcet1bb0in(ar_0, ar_1, ar_2, ar_3, ar_4))", 0-2) = ar_2 7.66/3.65 7.66/3.65 S("evalwcet1start(ar_0, ar_1, ar_2, ar_3, ar_4) -> Com_1(evalwcet1bb0in(ar_0, ar_1, ar_2, ar_3, ar_4))", 0-3) = ar_3 7.66/3.65 7.66/3.65 S("evalwcet1start(ar_0, ar_1, ar_2, ar_3, ar_4) -> Com_1(evalwcet1bb0in(ar_0, ar_1, ar_2, ar_3, ar_4))", 0-4) = ar_4 7.66/3.65 7.66/3.65 orients the transitions 7.66/3.65 7.66/3.65 evalwcet1bb4in(ar_0, ar_1, ar_2, ar_3, ar_4) -> Com_1(evalwcet1bb1in(ar_0, ar_1 - 1, ar_4, ar_3, ar_4)) [ ar_1 >= 2 ] 7.66/3.65 7.66/3.65 evalwcet1bb3in(ar_0, ar_1, ar_2, ar_3, ar_4) -> Com_1(evalwcet1bb4in(ar_0, ar_1, ar_2, ar_3, 0)) [ 1 >= ar_2 ] 7.66/3.65 7.66/3.65 evalwcet1bb3in(ar_0, ar_1, ar_2, ar_3, ar_4) -> Com_1(evalwcet1bb4in(ar_0, ar_1, ar_2, ar_3, ar_2 - 1)) [ ar_2 >= 2 ] 7.66/3.65 7.66/3.65 evalwcet1bb2in(ar_0, ar_1, ar_2, ar_3, ar_4) -> Com_1(evalwcet1bb4in(ar_0, ar_1, ar_2, ar_3, ar_2 + 1)) [ ar_0 >= ar_2 + 2 ] 7.66/3.65 7.66/3.65 evalwcet1bb2in(ar_0, ar_1, ar_2, ar_3, ar_4) -> Com_1(evalwcet1bb4in(ar_0, ar_1, ar_2, ar_3, 0)) [ ar_2 + 1 >= ar_0 ] 7.66/3.65 7.66/3.65 evalwcet1bb1in(ar_0, ar_1, ar_2, ar_3, ar_4) -> Com_1(evalwcet14(ar_0, ar_1, ar_2, ar_3, ar_4)) 7.66/3.65 7.66/3.65 evalwcet15(ar_0, ar_1, ar_2, ar_3, ar_4) -> Com_1(evalwcet1bb3in(ar_0, ar_1, ar_2, ar_3, ar_4)) [ 0 >= ar_3 ] 7.66/3.65 7.66/3.65 evalwcet15(ar_0, ar_1, ar_2, ar_3, ar_4) -> Com_1(evalwcet1bb2in(ar_0, ar_1, ar_2, ar_3, ar_4)) [ ar_3 >= 1 ] 7.66/3.65 7.66/3.65 evalwcet14(ar_0, ar_1, ar_2, ar_3, ar_4) -> Com_1(evalwcet15(ar_0, ar_1, ar_2, f, ar_4)) 7.66/3.65 7.66/3.65 weakly and the transition 7.66/3.65 7.66/3.65 evalwcet1bb4in(ar_0, ar_1, ar_2, ar_3, ar_4) -> Com_1(evalwcet1bb1in(ar_0, ar_1 - 1, ar_4, ar_3, ar_4)) [ ar_1 >= 2 ] 7.66/3.65 7.66/3.65 strictly and produces the following problem: 7.66/3.65 7.66/3.65 4: T: 7.66/3.65 7.66/3.65 (Comp: 1, Cost: 1) evalwcet1start(ar_0, ar_1, ar_2, ar_3, ar_4) -> Com_1(evalwcet1bb0in(ar_0, ar_1, ar_2, ar_3, ar_4)) 7.66/3.65 7.66/3.65 (Comp: 1, Cost: 1) evalwcet1bb0in(ar_0, ar_1, ar_2, ar_3, ar_4) -> Com_1(evalwcet10(ar_0, ar_1, ar_2, ar_3, ar_4)) 7.66/3.65 7.66/3.65 (Comp: 1, Cost: 1) evalwcet10(ar_0, ar_1, ar_2, ar_3, ar_4) -> Com_1(evalwcet11(ar_0, ar_1, ar_2, ar_3, ar_4)) 7.66/3.65 7.66/3.65 (Comp: 1, Cost: 1) evalwcet11(ar_0, ar_1, ar_2, ar_3, ar_4) -> Com_1(evalwcet12(ar_0, ar_1, ar_2, ar_3, ar_4)) 7.66/3.65 7.66/3.65 (Comp: 1, Cost: 1) evalwcet12(ar_0, ar_1, ar_2, ar_3, ar_4) -> Com_1(evalwcet13(ar_0, ar_1, ar_2, ar_3, ar_4)) 7.66/3.65 7.66/3.65 (Comp: 1, Cost: 1) evalwcet13(ar_0, ar_1, ar_2, ar_3, ar_4) -> Com_1(evalwcet1bb1in(ar_0, ar_0, 0, ar_3, ar_4)) [ ar_0 >= 1 ] 7.66/3.65 7.66/3.65 (Comp: 1, Cost: 1) evalwcet13(ar_0, ar_1, ar_2, ar_3, ar_4) -> Com_1(evalwcet1bb5in(ar_0, ar_1, ar_2, ar_3, ar_4)) [ 0 >= ar_0 ] 7.66/3.65 7.66/3.65 (Comp: ?, Cost: 1) evalwcet1bb1in(ar_0, ar_1, ar_2, ar_3, ar_4) -> Com_1(evalwcet14(ar_0, ar_1, ar_2, ar_3, ar_4)) 7.66/3.65 7.66/3.65 (Comp: ?, Cost: 1) evalwcet14(ar_0, ar_1, ar_2, ar_3, ar_4) -> Com_1(evalwcet15(ar_0, ar_1, ar_2, f, ar_4)) 7.66/3.65 7.66/3.65 (Comp: ?, Cost: 1) evalwcet15(ar_0, ar_1, ar_2, ar_3, ar_4) -> Com_1(evalwcet1bb2in(ar_0, ar_1, ar_2, ar_3, ar_4)) [ ar_3 >= 1 ] 7.66/3.65 7.66/3.65 (Comp: ?, Cost: 1) evalwcet15(ar_0, ar_1, ar_2, ar_3, ar_4) -> Com_1(evalwcet1bb3in(ar_0, ar_1, ar_2, ar_3, ar_4)) [ 0 >= ar_3 ] 7.66/3.65 7.66/3.65 (Comp: ?, Cost: 1) evalwcet1bb2in(ar_0, ar_1, ar_2, ar_3, ar_4) -> Com_1(evalwcet1bb4in(ar_0, ar_1, ar_2, ar_3, 0)) [ ar_2 + 1 >= ar_0 ] 7.66/3.65 7.66/3.65 (Comp: ?, Cost: 1) evalwcet1bb2in(ar_0, ar_1, ar_2, ar_3, ar_4) -> Com_1(evalwcet1bb4in(ar_0, ar_1, ar_2, ar_3, ar_2 + 1)) [ ar_0 >= ar_2 + 2 ] 7.66/3.65 7.66/3.65 (Comp: ?, Cost: 1) evalwcet1bb3in(ar_0, ar_1, ar_2, ar_3, ar_4) -> Com_1(evalwcet1bb4in(ar_0, ar_1, ar_2, ar_3, 0)) [ 1 >= ar_2 ] 7.66/3.65 7.66/3.65 (Comp: ?, Cost: 1) evalwcet1bb3in(ar_0, ar_1, ar_2, ar_3, ar_4) -> Com_1(evalwcet1bb4in(ar_0, ar_1, ar_2, ar_3, ar_2 - 1)) [ ar_2 >= 2 ] 7.66/3.65 7.66/3.65 (Comp: ar_0, Cost: 1) evalwcet1bb4in(ar_0, ar_1, ar_2, ar_3, ar_4) -> Com_1(evalwcet1bb1in(ar_0, ar_1 - 1, ar_4, ar_3, ar_4)) [ ar_1 >= 2 ] 7.66/3.65 7.66/3.65 (Comp: 2, Cost: 1) evalwcet1bb4in(ar_0, ar_1, ar_2, ar_3, ar_4) -> Com_1(evalwcet1bb5in(ar_0, ar_1, ar_2, ar_3, ar_4)) [ 1 >= ar_1 ] 7.66/3.65 7.66/3.65 (Comp: 2, Cost: 1) evalwcet1bb5in(ar_0, ar_1, ar_2, ar_3, ar_4) -> Com_1(evalwcet1stop(ar_0, ar_1, ar_2, ar_3, ar_4)) 7.66/3.65 7.66/3.65 (Comp: 1, Cost: 0) koat_start(ar_0, ar_1, ar_2, ar_3, ar_4) -> Com_1(evalwcet1start(ar_0, ar_1, ar_2, ar_3, ar_4)) [ 0 <= 0 ] 7.66/3.65 7.66/3.65 start location: koat_start 7.66/3.65 7.66/3.65 leaf cost: 0 7.66/3.65 7.66/3.65 7.66/3.65 7.66/3.65 Repeatedly propagating knowledge in problem 4 produces the following problem: 7.66/3.65 7.66/3.65 5: T: 7.66/3.65 7.66/3.65 (Comp: 1, Cost: 1) evalwcet1start(ar_0, ar_1, ar_2, ar_3, ar_4) -> Com_1(evalwcet1bb0in(ar_0, ar_1, ar_2, ar_3, ar_4)) 7.66/3.65 7.66/3.65 (Comp: 1, Cost: 1) evalwcet1bb0in(ar_0, ar_1, ar_2, ar_3, ar_4) -> Com_1(evalwcet10(ar_0, ar_1, ar_2, ar_3, ar_4)) 7.66/3.65 7.66/3.65 (Comp: 1, Cost: 1) evalwcet10(ar_0, ar_1, ar_2, ar_3, ar_4) -> Com_1(evalwcet11(ar_0, ar_1, ar_2, ar_3, ar_4)) 7.66/3.65 7.66/3.65 (Comp: 1, Cost: 1) evalwcet11(ar_0, ar_1, ar_2, ar_3, ar_4) -> Com_1(evalwcet12(ar_0, ar_1, ar_2, ar_3, ar_4)) 7.66/3.65 7.66/3.65 (Comp: 1, Cost: 1) evalwcet12(ar_0, ar_1, ar_2, ar_3, ar_4) -> Com_1(evalwcet13(ar_0, ar_1, ar_2, ar_3, ar_4)) 7.66/3.65 7.66/3.65 (Comp: 1, Cost: 1) evalwcet13(ar_0, ar_1, ar_2, ar_3, ar_4) -> Com_1(evalwcet1bb1in(ar_0, ar_0, 0, ar_3, ar_4)) [ ar_0 >= 1 ] 7.66/3.65 7.66/3.65 (Comp: 1, Cost: 1) evalwcet13(ar_0, ar_1, ar_2, ar_3, ar_4) -> Com_1(evalwcet1bb5in(ar_0, ar_1, ar_2, ar_3, ar_4)) [ 0 >= ar_0 ] 7.66/3.65 7.66/3.65 (Comp: ar_0 + 1, Cost: 1) evalwcet1bb1in(ar_0, ar_1, ar_2, ar_3, ar_4) -> Com_1(evalwcet14(ar_0, ar_1, ar_2, ar_3, ar_4)) 7.66/3.65 7.66/3.65 (Comp: ar_0 + 1, Cost: 1) evalwcet14(ar_0, ar_1, ar_2, ar_3, ar_4) -> Com_1(evalwcet15(ar_0, ar_1, ar_2, f, ar_4)) 7.66/3.65 7.66/3.65 (Comp: ar_0 + 1, Cost: 1) evalwcet15(ar_0, ar_1, ar_2, ar_3, ar_4) -> Com_1(evalwcet1bb2in(ar_0, ar_1, ar_2, ar_3, ar_4)) [ ar_3 >= 1 ] 7.66/3.65 7.66/3.65 (Comp: ar_0 + 1, Cost: 1) evalwcet15(ar_0, ar_1, ar_2, ar_3, ar_4) -> Com_1(evalwcet1bb3in(ar_0, ar_1, ar_2, ar_3, ar_4)) [ 0 >= ar_3 ] 7.66/3.65 7.66/3.65 (Comp: ar_0 + 1, Cost: 1) evalwcet1bb2in(ar_0, ar_1, ar_2, ar_3, ar_4) -> Com_1(evalwcet1bb4in(ar_0, ar_1, ar_2, ar_3, 0)) [ ar_2 + 1 >= ar_0 ] 7.66/3.65 7.66/3.65 (Comp: ar_0 + 1, Cost: 1) evalwcet1bb2in(ar_0, ar_1, ar_2, ar_3, ar_4) -> Com_1(evalwcet1bb4in(ar_0, ar_1, ar_2, ar_3, ar_2 + 1)) [ ar_0 >= ar_2 + 2 ] 7.66/3.65 7.66/3.65 (Comp: ar_0 + 1, Cost: 1) evalwcet1bb3in(ar_0, ar_1, ar_2, ar_3, ar_4) -> Com_1(evalwcet1bb4in(ar_0, ar_1, ar_2, ar_3, 0)) [ 1 >= ar_2 ] 7.66/3.65 7.66/3.65 (Comp: ar_0 + 1, Cost: 1) evalwcet1bb3in(ar_0, ar_1, ar_2, ar_3, ar_4) -> Com_1(evalwcet1bb4in(ar_0, ar_1, ar_2, ar_3, ar_2 - 1)) [ ar_2 >= 2 ] 7.66/3.65 7.66/3.65 (Comp: ar_0, Cost: 1) evalwcet1bb4in(ar_0, ar_1, ar_2, ar_3, ar_4) -> Com_1(evalwcet1bb1in(ar_0, ar_1 - 1, ar_4, ar_3, ar_4)) [ ar_1 >= 2 ] 7.66/3.65 7.66/3.65 (Comp: 2, Cost: 1) evalwcet1bb4in(ar_0, ar_1, ar_2, ar_3, ar_4) -> Com_1(evalwcet1bb5in(ar_0, ar_1, ar_2, ar_3, ar_4)) [ 1 >= ar_1 ] 7.66/3.65 7.66/3.65 (Comp: 2, Cost: 1) evalwcet1bb5in(ar_0, ar_1, ar_2, ar_3, ar_4) -> Com_1(evalwcet1stop(ar_0, ar_1, ar_2, ar_3, ar_4)) 7.66/3.65 7.66/3.65 (Comp: 1, Cost: 0) koat_start(ar_0, ar_1, ar_2, ar_3, ar_4) -> Com_1(evalwcet1start(ar_0, ar_1, ar_2, ar_3, ar_4)) [ 0 <= 0 ] 7.66/3.65 7.66/3.65 start location: koat_start 7.66/3.65 7.66/3.65 leaf cost: 0 7.66/3.65 7.66/3.65 7.66/3.65 7.66/3.65 Complexity upper bound 9*ar_0 + 19 7.66/3.65 7.66/3.65 7.66/3.65 7.66/3.65 Time: 0.244 sec (SMT: 0.186 sec) 7.66/3.65 7.66/3.65 7.66/3.65 ---------------------------------------- 7.66/3.65 7.66/3.65 (2) 7.66/3.65 BOUNDS(1, n^1) 7.66/3.65 7.66/3.65 ---------------------------------------- 7.66/3.65 7.66/3.65 (3) Loat Proof (FINISHED) 7.66/3.65 7.66/3.65 7.66/3.65 ### Pre-processing the ITS problem ### 7.66/3.65 7.66/3.65 7.66/3.65 7.66/3.65 Initial linear ITS problem 7.66/3.65 7.66/3.65 Start location: evalwcet1start 7.66/3.65 7.66/3.65 0: evalwcet1start -> evalwcet1bb0in : [], cost: 1 7.66/3.65 7.66/3.65 1: evalwcet1bb0in -> evalwcet10 : [], cost: 1 7.66/3.65 7.66/3.65 2: evalwcet10 -> evalwcet11 : [], cost: 1 7.66/3.65 7.66/3.65 3: evalwcet11 -> evalwcet12 : [], cost: 1 7.66/3.65 7.66/3.65 4: evalwcet12 -> evalwcet13 : [], cost: 1 7.66/3.65 7.66/3.65 5: evalwcet13 -> evalwcet1bb1in : B'=A, C'=0, [ A>=1 ], cost: 1 7.66/3.65 7.66/3.65 6: evalwcet13 -> evalwcet1bb5in : [ 0>=A ], cost: 1 7.66/3.65 7.66/3.65 7: evalwcet1bb1in -> evalwcet14 : [], cost: 1 7.66/3.65 7.66/3.65 8: evalwcet14 -> evalwcet15 : D'=free, [], cost: 1 7.66/3.65 7.66/3.65 9: evalwcet15 -> evalwcet1bb2in : [ D>=1 ], cost: 1 7.66/3.65 7.66/3.65 10: evalwcet15 -> evalwcet1bb3in : [ 0>=D ], cost: 1 7.66/3.65 7.66/3.65 11: evalwcet1bb2in -> evalwcet1bb4in : E'=0, [ 1+C>=A ], cost: 1 7.66/3.65 7.66/3.65 12: evalwcet1bb2in -> evalwcet1bb4in : E'=1+C, [ A>=2+C ], cost: 1 7.66/3.65 7.66/3.65 13: evalwcet1bb3in -> evalwcet1bb4in : E'=0, [ 1>=C ], cost: 1 7.66/3.65 7.66/3.65 14: evalwcet1bb3in -> evalwcet1bb4in : E'=-1+C, [ C>=2 ], cost: 1 7.66/3.65 7.66/3.65 15: evalwcet1bb4in -> evalwcet1bb1in : B'=-1+B, C'=E, [ B>=2 ], cost: 1 7.66/3.65 7.66/3.65 16: evalwcet1bb4in -> evalwcet1bb5in : [ 1>=B ], cost: 1 7.66/3.65 7.66/3.65 17: evalwcet1bb5in -> evalwcet1stop : [], cost: 1 7.66/3.65 7.66/3.65 7.66/3.65 7.66/3.65 Removed unreachable and leaf rules: 7.66/3.65 7.66/3.65 Start location: evalwcet1start 7.66/3.65 7.66/3.65 0: evalwcet1start -> evalwcet1bb0in : [], cost: 1 7.66/3.65 7.66/3.65 1: evalwcet1bb0in -> evalwcet10 : [], cost: 1 7.66/3.65 7.66/3.65 2: evalwcet10 -> evalwcet11 : [], cost: 1 7.66/3.65 7.66/3.65 3: evalwcet11 -> evalwcet12 : [], cost: 1 7.66/3.65 7.66/3.65 4: evalwcet12 -> evalwcet13 : [], cost: 1 7.66/3.65 7.66/3.65 5: evalwcet13 -> evalwcet1bb1in : B'=A, C'=0, [ A>=1 ], cost: 1 7.66/3.65 7.66/3.65 7: evalwcet1bb1in -> evalwcet14 : [], cost: 1 7.66/3.65 7.66/3.65 8: evalwcet14 -> evalwcet15 : D'=free, [], cost: 1 7.66/3.65 7.66/3.65 9: evalwcet15 -> evalwcet1bb2in : [ D>=1 ], cost: 1 7.66/3.65 7.66/3.65 10: evalwcet15 -> evalwcet1bb3in : [ 0>=D ], cost: 1 7.66/3.65 7.66/3.65 11: evalwcet1bb2in -> evalwcet1bb4in : E'=0, [ 1+C>=A ], cost: 1 7.66/3.65 7.66/3.65 12: evalwcet1bb2in -> evalwcet1bb4in : E'=1+C, [ A>=2+C ], cost: 1 7.66/3.65 7.66/3.65 13: evalwcet1bb3in -> evalwcet1bb4in : E'=0, [ 1>=C ], cost: 1 7.66/3.65 7.66/3.65 14: evalwcet1bb3in -> evalwcet1bb4in : E'=-1+C, [ C>=2 ], cost: 1 7.66/3.65 7.66/3.65 15: evalwcet1bb4in -> evalwcet1bb1in : B'=-1+B, C'=E, [ B>=2 ], cost: 1 7.66/3.65 7.66/3.65 7.66/3.65 7.66/3.65 ### Simplification by acceleration and chaining ### 7.66/3.65 7.66/3.65 7.66/3.65 7.66/3.65 Eliminated locations (on linear paths): 7.66/3.65 7.66/3.65 Start location: evalwcet1start 7.66/3.65 7.66/3.65 22: evalwcet1start -> evalwcet1bb1in : B'=A, C'=0, [ A>=1 ], cost: 6 7.66/3.65 7.66/3.65 23: evalwcet1bb1in -> evalwcet15 : D'=free, [], cost: 2 7.66/3.65 7.66/3.65 9: evalwcet15 -> evalwcet1bb2in : [ D>=1 ], cost: 1 7.66/3.65 7.66/3.65 10: evalwcet15 -> evalwcet1bb3in : [ 0>=D ], cost: 1 7.66/3.65 7.66/3.65 11: evalwcet1bb2in -> evalwcet1bb4in : E'=0, [ 1+C>=A ], cost: 1 7.66/3.65 7.66/3.65 12: evalwcet1bb2in -> evalwcet1bb4in : E'=1+C, [ A>=2+C ], cost: 1 7.66/3.65 7.66/3.65 13: evalwcet1bb3in -> evalwcet1bb4in : E'=0, [ 1>=C ], cost: 1 7.66/3.65 7.66/3.65 14: evalwcet1bb3in -> evalwcet1bb4in : E'=-1+C, [ C>=2 ], cost: 1 7.66/3.65 7.66/3.65 15: evalwcet1bb4in -> evalwcet1bb1in : B'=-1+B, C'=E, [ B>=2 ], cost: 1 7.66/3.65 7.66/3.65 7.66/3.65 7.66/3.65 Eliminated locations (on tree-shaped paths): 7.66/3.65 7.66/3.65 Start location: evalwcet1start 7.66/3.65 7.66/3.65 22: evalwcet1start -> evalwcet1bb1in : B'=A, C'=0, [ A>=1 ], cost: 6 7.66/3.65 7.66/3.65 24: evalwcet1bb1in -> evalwcet1bb2in : D'=free, [ free>=1 ], cost: 3 7.66/3.65 7.66/3.65 25: evalwcet1bb1in -> evalwcet1bb3in : D'=free, [ 0>=free ], cost: 3 7.66/3.65 7.66/3.65 11: evalwcet1bb2in -> evalwcet1bb4in : E'=0, [ 1+C>=A ], cost: 1 7.66/3.65 7.66/3.65 12: evalwcet1bb2in -> evalwcet1bb4in : E'=1+C, [ A>=2+C ], cost: 1 7.66/3.65 7.66/3.65 13: evalwcet1bb3in -> evalwcet1bb4in : E'=0, [ 1>=C ], cost: 1 7.66/3.65 7.66/3.65 14: evalwcet1bb3in -> evalwcet1bb4in : E'=-1+C, [ C>=2 ], cost: 1 7.66/3.65 7.66/3.65 15: evalwcet1bb4in -> evalwcet1bb1in : B'=-1+B, C'=E, [ B>=2 ], cost: 1 7.66/3.65 7.66/3.65 7.66/3.65 7.66/3.65 Eliminated locations (on tree-shaped paths): 7.66/3.65 7.66/3.65 Start location: evalwcet1start 7.66/3.65 7.66/3.65 22: evalwcet1start -> evalwcet1bb1in : B'=A, C'=0, [ A>=1 ], cost: 6 7.66/3.65 7.66/3.65 26: evalwcet1bb1in -> evalwcet1bb4in : D'=free, E'=0, [ free>=1 && 1+C>=A ], cost: 4 7.66/3.65 7.66/3.65 27: evalwcet1bb1in -> evalwcet1bb4in : D'=free, E'=1+C, [ free>=1 && A>=2+C ], cost: 4 7.66/3.65 7.66/3.65 28: evalwcet1bb1in -> evalwcet1bb4in : D'=free, E'=0, [ 0>=free && 1>=C ], cost: 4 7.66/3.65 7.66/3.65 29: evalwcet1bb1in -> evalwcet1bb4in : D'=free, E'=-1+C, [ 0>=free && C>=2 ], cost: 4 7.66/3.65 7.66/3.65 15: evalwcet1bb4in -> evalwcet1bb1in : B'=-1+B, C'=E, [ B>=2 ], cost: 1 7.66/3.65 7.66/3.65 7.66/3.65 7.66/3.65 Eliminated locations (on tree-shaped paths): 7.66/3.65 7.66/3.65 Start location: evalwcet1start 7.66/3.65 7.66/3.65 22: evalwcet1start -> evalwcet1bb1in : B'=A, C'=0, [ A>=1 ], cost: 6 7.66/3.65 7.66/3.65 30: evalwcet1bb1in -> evalwcet1bb1in : B'=-1+B, C'=0, D'=free, E'=0, [ free>=1 && 1+C>=A && B>=2 ], cost: 5 7.66/3.65 7.66/3.65 31: evalwcet1bb1in -> evalwcet1bb1in : B'=-1+B, C'=1+C, D'=free, E'=1+C, [ free>=1 && A>=2+C && B>=2 ], cost: 5 7.66/3.65 7.66/3.65 32: evalwcet1bb1in -> evalwcet1bb1in : B'=-1+B, C'=0, D'=free, E'=0, [ 0>=free && 1>=C && B>=2 ], cost: 5 7.66/3.65 7.66/3.65 33: evalwcet1bb1in -> evalwcet1bb1in : B'=-1+B, C'=-1+C, D'=free, E'=-1+C, [ 0>=free && C>=2 && B>=2 ], cost: 5 7.66/3.65 7.66/3.65 7.66/3.65 7.66/3.65 Accelerating simple loops of location 6. 7.66/3.65 7.66/3.65 Accelerating the following rules: 7.66/3.65 7.66/3.65 30: evalwcet1bb1in -> evalwcet1bb1in : B'=-1+B, C'=0, D'=free, E'=0, [ free>=1 && 1+C>=A && B>=2 ], cost: 5 7.66/3.65 7.66/3.65 31: evalwcet1bb1in -> evalwcet1bb1in : B'=-1+B, C'=1+C, D'=free, E'=1+C, [ free>=1 && A>=2+C && B>=2 ], cost: 5 7.66/3.65 7.66/3.65 32: evalwcet1bb1in -> evalwcet1bb1in : B'=-1+B, C'=0, D'=free, E'=0, [ 0>=free && 1>=C && B>=2 ], cost: 5 7.66/3.65 7.66/3.65 33: evalwcet1bb1in -> evalwcet1bb1in : B'=-1+B, C'=-1+C, D'=free, E'=-1+C, [ 0>=free && C>=2 && B>=2 ], cost: 5 7.66/3.65 7.66/3.65 7.66/3.65 7.66/3.65 Accelerated rule 30 with metering function -1+B (after strengthening guard), yielding the new rule 34. 7.66/3.65 7.66/3.65 Accelerated rule 31 with backward acceleration, yielding the new rule 35. 7.66/3.65 7.66/3.65 Accelerated rule 31 with backward acceleration, yielding the new rule 36. 7.66/3.65 7.66/3.65 Accelerated rule 32 with metering function -1+B, yielding the new rule 37. 7.66/3.65 7.66/3.65 Accelerated rule 33 with metering function -1+C (after adding B>=C), yielding the new rule 38. 7.66/3.65 7.66/3.65 Accelerated rule 33 with metering function -1+B (after adding B<=C), yielding the new rule 39. 7.66/3.65 7.66/3.65 Removing the simple loops: 31 32 33. 7.66/3.65 7.66/3.65 7.66/3.65 7.66/3.65 Accelerated all simple loops using metering functions (where possible): 7.66/3.65 7.66/3.65 Start location: evalwcet1start 7.66/3.65 7.66/3.65 22: evalwcet1start -> evalwcet1bb1in : B'=A, C'=0, [ A>=1 ], cost: 6 7.66/3.65 7.66/3.65 30: evalwcet1bb1in -> evalwcet1bb1in : B'=-1+B, C'=0, D'=free, E'=0, [ free>=1 && 1+C>=A && B>=2 ], cost: 5 7.66/3.65 7.66/3.65 34: evalwcet1bb1in -> evalwcet1bb1in : B'=1, C'=0, D'=free, E'=0, [ free>=1 && 1+C>=A && B>=2 && 1>=A ], cost: -5+5*B 7.66/3.65 7.66/3.65 35: evalwcet1bb1in -> evalwcet1bb1in : B'=1+C-A+B, C'=-1+A, D'=free, E'=-1+A, [ free>=1 && A>=2+C && B>=2 && 2+C-A+B>=2 ], cost: -5-5*C+5*A 7.66/3.65 7.66/3.65 36: evalwcet1bb1in -> evalwcet1bb1in : B'=1, C'=-1+C+B, D'=free, E'=-1+C+B, [ free>=1 && A>=2+C && B>=2 && A>=C+B ], cost: -5+5*B 7.66/3.65 7.66/3.65 37: evalwcet1bb1in -> evalwcet1bb1in : B'=1, C'=0, D'=free, E'=0, [ 0>=free && 1>=C && B>=2 ], cost: -5+5*B 7.66/3.65 7.66/3.65 38: evalwcet1bb1in -> evalwcet1bb1in : B'=1-C+B, C'=1, D'=free, E'=1, [ 0>=free && C>=2 && B>=2 && B>=C ], cost: -5+5*C 7.66/3.65 7.66/3.65 39: evalwcet1bb1in -> evalwcet1bb1in : B'=1, C'=1+C-B, D'=free, E'=1+C-B, [ 0>=free && C>=2 && B>=2 && B<=C ], cost: -5+5*B 7.66/3.65 7.66/3.65 7.66/3.65 7.66/3.65 Chained accelerated rules (with incoming rules): 7.66/3.65 7.66/3.65 Start location: evalwcet1start 7.66/3.65 7.66/3.65 22: evalwcet1start -> evalwcet1bb1in : B'=A, C'=0, [ A>=1 ], cost: 6 7.66/3.65 7.66/3.65 40: evalwcet1start -> evalwcet1bb1in : B'=1, C'=-1+A, D'=free, E'=-1+A, [ free>=1 && A>=2 ], cost: 1+5*A 7.66/3.65 7.66/3.65 41: evalwcet1start -> evalwcet1bb1in : B'=1, C'=-1+A, D'=free, E'=-1+A, [ free>=1 && A>=2 ], cost: 1+5*A 7.66/3.65 7.66/3.65 42: evalwcet1start -> evalwcet1bb1in : B'=1, C'=0, D'=free, E'=0, [ 0>=free && A>=2 ], cost: 1+5*A 7.66/3.65 7.66/3.65 7.66/3.65 7.66/3.65 Removed unreachable locations (and leaf rules with constant cost): 7.66/3.65 7.66/3.65 Start location: evalwcet1start 7.66/3.65 7.66/3.65 40: evalwcet1start -> evalwcet1bb1in : B'=1, C'=-1+A, D'=free, E'=-1+A, [ free>=1 && A>=2 ], cost: 1+5*A 7.66/3.65 7.66/3.65 41: evalwcet1start -> evalwcet1bb1in : B'=1, C'=-1+A, D'=free, E'=-1+A, [ free>=1 && A>=2 ], cost: 1+5*A 7.66/3.65 7.66/3.65 42: evalwcet1start -> evalwcet1bb1in : B'=1, C'=0, D'=free, E'=0, [ 0>=free && A>=2 ], cost: 1+5*A 7.66/3.65 7.66/3.65 7.66/3.65 7.66/3.65 ### Computing asymptotic complexity ### 7.66/3.65 7.66/3.65 7.66/3.65 7.66/3.65 Fully simplified ITS problem 7.66/3.65 7.66/3.65 Start location: evalwcet1start 7.66/3.65 7.66/3.65 41: evalwcet1start -> evalwcet1bb1in : B'=1, C'=-1+A, D'=free, E'=-1+A, [ free>=1 && A>=2 ], cost: 1+5*A 7.66/3.65 7.66/3.65 42: evalwcet1start -> evalwcet1bb1in : B'=1, C'=0, D'=free, E'=0, [ 0>=free && A>=2 ], cost: 1+5*A 7.66/3.65 7.66/3.65 7.66/3.65 7.66/3.65 Computing asymptotic complexity for rule 41 7.66/3.65 7.66/3.65 Solved the limit problem by the following transformations: 7.66/3.65 7.66/3.65 Created initial limit problem: 7.66/3.65 7.66/3.65 -1+A (+/+!), 1+5*A (+), free (+/+!) [not solved] 7.66/3.65 7.66/3.65 7.66/3.65 7.66/3.65 removing all constraints (solved by SMT) 7.66/3.65 7.66/3.65 resulting limit problem: [solved] 7.66/3.65 7.66/3.65 7.66/3.65 7.66/3.65 applying transformation rule (C) using substitution {free==n,A==n} 7.66/3.65 7.66/3.65 resulting limit problem: 7.66/3.65 7.66/3.65 [solved] 7.66/3.65 7.66/3.65 7.66/3.65 7.66/3.65 Solution: 7.66/3.65 7.66/3.65 free / n 7.66/3.65 7.66/3.65 A / n 7.66/3.65 7.66/3.65 Resulting cost 1+5*n has complexity: Poly(n^1) 7.66/3.65 7.66/3.65 7.66/3.65 7.66/3.65 Found new complexity Poly(n^1). 7.66/3.65 7.66/3.65 7.66/3.65 7.66/3.65 Obtained the following overall complexity (w.r.t. the length of the input n): 7.66/3.65 7.66/3.65 Complexity: Poly(n^1) 7.66/3.65 7.66/3.65 Cpx degree: 1 7.66/3.65 7.66/3.65 Solved cost: 1+5*n 7.66/3.65 7.66/3.65 Rule cost: 1+5*A 7.66/3.65 7.66/3.65 Rule guard: [ free>=1 && A>=2 ] 7.66/3.65 7.66/3.65 7.66/3.65 7.66/3.65 WORST_CASE(Omega(n^1),?) 7.66/3.65 7.66/3.65 7.66/3.65 ---------------------------------------- 7.66/3.65 7.66/3.65 (4) 7.66/3.65 BOUNDS(n^1, INF) 7.70/3.72 EOF