/export/starexec/sandbox2/solver/bin/starexec_run_complexity /export/starexec/sandbox2/benchmark/theBenchmark.koat /export/starexec/sandbox2/output/output_files -------------------------------------------------------------------------------- WORST_CASE(Omega(n^1), O(n^1)) proof of /export/starexec/sandbox2/benchmark/theBenchmark.koat # AProVE Commit ID: 794c25de1cacf0d048858bcd21c9a779e1221865 marcel 20200619 unpublished dirty The runtime complexity of the given CpxIntTrs could be proven to be BOUNDS(n^1, n^1). (0) CpxIntTrs (1) Koat Proof [FINISHED, 127 ms] (2) BOUNDS(1, n^1) (3) Loat Proof [FINISHED, 828 ms] (4) BOUNDS(n^1, INF) ---------------------------------------- (0) Obligation: Complexity Int TRS consisting of the following rules: eval_wcet2_start(v__0, v_4, v_i, v_j_0) -> Com_1(eval_wcet2_bb0_in(v__0, v_4, v_i, v_j_0)) :|: TRUE eval_wcet2_bb0_in(v__0, v_4, v_i, v_j_0) -> Com_1(eval_wcet2_0(v__0, v_4, v_i, v_j_0)) :|: TRUE eval_wcet2_0(v__0, v_4, v_i, v_j_0) -> Com_1(eval_wcet2_1(v__0, v_4, v_i, v_j_0)) :|: TRUE eval_wcet2_1(v__0, v_4, v_i, v_j_0) -> Com_1(eval_wcet2_2(v__0, v_4, v_i, v_j_0)) :|: TRUE eval_wcet2_2(v__0, v_4, v_i, v_j_0) -> Com_1(eval_wcet2_3(v__0, v_4, v_i, v_j_0)) :|: TRUE eval_wcet2_3(v__0, v_4, v_i, v_j_0) -> Com_1(eval_wcet2_bb1_in(v_i, v_4, v_i, v_j_0)) :|: TRUE eval_wcet2_bb1_in(v__0, v_4, v_i, v_j_0) -> Com_1(eval_wcet2_bb2_in(v__0, v_4, v_i, 0)) :|: v__0 < 5 eval_wcet2_bb1_in(v__0, v_4, v_i, v_j_0) -> Com_1(eval_wcet2_bb5_in(v__0, v_4, v_i, v_j_0)) :|: v__0 >= 5 eval_wcet2_bb2_in(v__0, v_4, v_i, v_j_0) -> Com_1(eval_wcet2_bb3_in(v__0, v_4, v_i, v_j_0)) :|: v__0 > 2 && v_j_0 <= 9 eval_wcet2_bb2_in(v__0, v_4, v_i, v_j_0) -> Com_1(eval_wcet2_bb4_in(v__0, v_4, v_i, v_j_0)) :|: v__0 <= 2 eval_wcet2_bb2_in(v__0, v_4, v_i, v_j_0) -> Com_1(eval_wcet2_bb4_in(v__0, v_4, v_i, v_j_0)) :|: v_j_0 > 9 eval_wcet2_bb3_in(v__0, v_4, v_i, v_j_0) -> Com_1(eval_wcet2_bb2_in(v__0, v_4, v_i, v_j_0 + 1)) :|: TRUE eval_wcet2_bb4_in(v__0, v_4, v_i, v_j_0) -> Com_1(eval_wcet2_7(v__0, v__0 + 1, v_i, v_j_0)) :|: TRUE eval_wcet2_7(v__0, v_4, v_i, v_j_0) -> Com_1(eval_wcet2_8(v__0, v_4, v_i, v_j_0)) :|: TRUE eval_wcet2_8(v__0, v_4, v_i, v_j_0) -> Com_1(eval_wcet2_bb1_in(v_4, v_4, v_i, v_j_0)) :|: TRUE eval_wcet2_bb5_in(v__0, v_4, v_i, v_j_0) -> Com_1(eval_wcet2_stop(v__0, v_4, v_i, v_j_0)) :|: TRUE The start-symbols are:[eval_wcet2_start_4] ---------------------------------------- (1) Koat Proof (FINISHED) YES(?, 100*Ar_1 + 460) Initial complexity problem: 1: T: (Comp: ?, Cost: 1) evalwcet2start(Ar_0, Ar_1, Ar_2, Ar_3) -> Com_1(evalwcet2bb0in(Ar_0, Ar_1, Ar_2, Ar_3)) (Comp: ?, Cost: 1) evalwcet2bb0in(Ar_0, Ar_1, Ar_2, Ar_3) -> Com_1(evalwcet20(Ar_0, Ar_1, Ar_2, Ar_3)) (Comp: ?, Cost: 1) evalwcet20(Ar_0, Ar_1, Ar_2, Ar_3) -> Com_1(evalwcet21(Ar_0, Ar_1, Ar_2, Ar_3)) (Comp: ?, Cost: 1) evalwcet21(Ar_0, Ar_1, Ar_2, Ar_3) -> Com_1(evalwcet22(Ar_0, Ar_1, Ar_2, Ar_3)) (Comp: ?, Cost: 1) evalwcet22(Ar_0, Ar_1, Ar_2, Ar_3) -> Com_1(evalwcet23(Ar_0, Ar_1, Ar_2, Ar_3)) (Comp: ?, Cost: 1) evalwcet23(Ar_0, Ar_1, Ar_2, Ar_3) -> Com_1(evalwcet2bb1in(Ar_1, Ar_1, Ar_2, Ar_3)) (Comp: ?, Cost: 1) evalwcet2bb1in(Ar_0, Ar_1, Ar_2, Ar_3) -> Com_1(evalwcet2bb2in(Ar_0, Ar_1, 0, Ar_3)) [ 4 >= Ar_0 ] (Comp: ?, Cost: 1) evalwcet2bb1in(Ar_0, Ar_1, Ar_2, Ar_3) -> Com_1(evalwcet2bb5in(Ar_0, Ar_1, Ar_2, Ar_3)) [ Ar_0 >= 5 ] (Comp: ?, Cost: 1) evalwcet2bb2in(Ar_0, Ar_1, Ar_2, Ar_3) -> Com_1(evalwcet2bb3in(Ar_0, Ar_1, Ar_2, Ar_3)) [ Ar_0 >= 3 /\ 9 >= Ar_2 ] (Comp: ?, Cost: 1) evalwcet2bb2in(Ar_0, Ar_1, Ar_2, Ar_3) -> Com_1(evalwcet2bb4in(Ar_0, Ar_1, Ar_2, Ar_3)) [ 2 >= Ar_0 ] (Comp: ?, Cost: 1) evalwcet2bb2in(Ar_0, Ar_1, Ar_2, Ar_3) -> Com_1(evalwcet2bb4in(Ar_0, Ar_1, Ar_2, Ar_3)) [ Ar_2 >= 10 ] (Comp: ?, Cost: 1) evalwcet2bb3in(Ar_0, Ar_1, Ar_2, Ar_3) -> Com_1(evalwcet2bb2in(Ar_0, Ar_1, Ar_2 + 1, Ar_3)) (Comp: ?, Cost: 1) evalwcet2bb4in(Ar_0, Ar_1, Ar_2, Ar_3) -> Com_1(evalwcet27(Ar_0, Ar_1, Ar_2, Ar_0 + 1)) (Comp: ?, Cost: 1) evalwcet27(Ar_0, Ar_1, Ar_2, Ar_3) -> Com_1(evalwcet28(Ar_0, Ar_1, Ar_2, Ar_3)) (Comp: ?, Cost: 1) evalwcet28(Ar_0, Ar_1, Ar_2, Ar_3) -> Com_1(evalwcet2bb1in(Ar_3, Ar_1, Ar_2, Ar_3)) (Comp: ?, Cost: 1) evalwcet2bb5in(Ar_0, Ar_1, Ar_2, Ar_3) -> Com_1(evalwcet2stop(Ar_0, Ar_1, Ar_2, Ar_3)) (Comp: 1, Cost: 0) koat_start(Ar_0, Ar_1, Ar_2, Ar_3) -> Com_1(evalwcet2start(Ar_0, Ar_1, Ar_2, Ar_3)) [ 0 <= 0 ] start location: koat_start leaf cost: 0 Repeatedly propagating knowledge in problem 1 produces the following problem: 2: T: (Comp: 1, Cost: 1) evalwcet2start(Ar_0, Ar_1, Ar_2, Ar_3) -> Com_1(evalwcet2bb0in(Ar_0, Ar_1, Ar_2, Ar_3)) (Comp: 1, Cost: 1) evalwcet2bb0in(Ar_0, Ar_1, Ar_2, Ar_3) -> Com_1(evalwcet20(Ar_0, Ar_1, Ar_2, Ar_3)) (Comp: 1, Cost: 1) evalwcet20(Ar_0, Ar_1, Ar_2, Ar_3) -> Com_1(evalwcet21(Ar_0, Ar_1, Ar_2, Ar_3)) (Comp: 1, Cost: 1) evalwcet21(Ar_0, Ar_1, Ar_2, Ar_3) -> Com_1(evalwcet22(Ar_0, Ar_1, Ar_2, Ar_3)) (Comp: 1, Cost: 1) evalwcet22(Ar_0, Ar_1, Ar_2, Ar_3) -> Com_1(evalwcet23(Ar_0, Ar_1, Ar_2, Ar_3)) (Comp: 1, Cost: 1) evalwcet23(Ar_0, Ar_1, Ar_2, Ar_3) -> Com_1(evalwcet2bb1in(Ar_1, Ar_1, Ar_2, Ar_3)) (Comp: ?, Cost: 1) evalwcet2bb1in(Ar_0, Ar_1, Ar_2, Ar_3) -> Com_1(evalwcet2bb2in(Ar_0, Ar_1, 0, Ar_3)) [ 4 >= Ar_0 ] (Comp: ?, Cost: 1) evalwcet2bb1in(Ar_0, Ar_1, Ar_2, Ar_3) -> Com_1(evalwcet2bb5in(Ar_0, Ar_1, Ar_2, Ar_3)) [ Ar_0 >= 5 ] (Comp: ?, Cost: 1) evalwcet2bb2in(Ar_0, Ar_1, Ar_2, Ar_3) -> Com_1(evalwcet2bb3in(Ar_0, Ar_1, Ar_2, Ar_3)) [ Ar_0 >= 3 /\ 9 >= Ar_2 ] (Comp: ?, Cost: 1) evalwcet2bb2in(Ar_0, Ar_1, Ar_2, Ar_3) -> Com_1(evalwcet2bb4in(Ar_0, Ar_1, Ar_2, Ar_3)) [ 2 >= Ar_0 ] (Comp: ?, Cost: 1) evalwcet2bb2in(Ar_0, Ar_1, Ar_2, Ar_3) -> Com_1(evalwcet2bb4in(Ar_0, Ar_1, Ar_2, Ar_3)) [ Ar_2 >= 10 ] (Comp: ?, Cost: 1) evalwcet2bb3in(Ar_0, Ar_1, Ar_2, Ar_3) -> Com_1(evalwcet2bb2in(Ar_0, Ar_1, Ar_2 + 1, Ar_3)) (Comp: ?, Cost: 1) evalwcet2bb4in(Ar_0, Ar_1, Ar_2, Ar_3) -> Com_1(evalwcet27(Ar_0, Ar_1, Ar_2, Ar_0 + 1)) (Comp: ?, Cost: 1) evalwcet27(Ar_0, Ar_1, Ar_2, Ar_3) -> Com_1(evalwcet28(Ar_0, Ar_1, Ar_2, Ar_3)) (Comp: ?, Cost: 1) evalwcet28(Ar_0, Ar_1, Ar_2, Ar_3) -> Com_1(evalwcet2bb1in(Ar_3, Ar_1, Ar_2, Ar_3)) (Comp: ?, Cost: 1) evalwcet2bb5in(Ar_0, Ar_1, Ar_2, Ar_3) -> Com_1(evalwcet2stop(Ar_0, Ar_1, Ar_2, Ar_3)) (Comp: 1, Cost: 0) koat_start(Ar_0, Ar_1, Ar_2, Ar_3) -> Com_1(evalwcet2start(Ar_0, Ar_1, Ar_2, Ar_3)) [ 0 <= 0 ] start location: koat_start leaf cost: 0 A polynomial rank function with Pol(evalwcet2start) = 2 Pol(evalwcet2bb0in) = 2 Pol(evalwcet20) = 2 Pol(evalwcet21) = 2 Pol(evalwcet22) = 2 Pol(evalwcet23) = 2 Pol(evalwcet2bb1in) = 2 Pol(evalwcet2bb2in) = 2 Pol(evalwcet2bb5in) = 1 Pol(evalwcet2bb3in) = 2 Pol(evalwcet2bb4in) = 2 Pol(evalwcet27) = 2 Pol(evalwcet28) = 2 Pol(evalwcet2stop) = 0 Pol(koat_start) = 2 orients all transitions weakly and the transitions evalwcet2bb5in(Ar_0, Ar_1, Ar_2, Ar_3) -> Com_1(evalwcet2stop(Ar_0, Ar_1, Ar_2, Ar_3)) evalwcet2bb1in(Ar_0, Ar_1, Ar_2, Ar_3) -> Com_1(evalwcet2bb5in(Ar_0, Ar_1, Ar_2, Ar_3)) [ Ar_0 >= 5 ] strictly and produces the following problem: 3: T: (Comp: 1, Cost: 1) evalwcet2start(Ar_0, Ar_1, Ar_2, Ar_3) -> Com_1(evalwcet2bb0in(Ar_0, Ar_1, Ar_2, Ar_3)) (Comp: 1, Cost: 1) evalwcet2bb0in(Ar_0, Ar_1, Ar_2, Ar_3) -> Com_1(evalwcet20(Ar_0, Ar_1, Ar_2, Ar_3)) (Comp: 1, Cost: 1) evalwcet20(Ar_0, Ar_1, Ar_2, Ar_3) -> Com_1(evalwcet21(Ar_0, Ar_1, Ar_2, Ar_3)) (Comp: 1, Cost: 1) evalwcet21(Ar_0, Ar_1, Ar_2, Ar_3) -> Com_1(evalwcet22(Ar_0, Ar_1, Ar_2, Ar_3)) (Comp: 1, Cost: 1) evalwcet22(Ar_0, Ar_1, Ar_2, Ar_3) -> Com_1(evalwcet23(Ar_0, Ar_1, Ar_2, Ar_3)) (Comp: 1, Cost: 1) evalwcet23(Ar_0, Ar_1, Ar_2, Ar_3) -> Com_1(evalwcet2bb1in(Ar_1, Ar_1, Ar_2, Ar_3)) (Comp: ?, Cost: 1) evalwcet2bb1in(Ar_0, Ar_1, Ar_2, Ar_3) -> Com_1(evalwcet2bb2in(Ar_0, Ar_1, 0, Ar_3)) [ 4 >= Ar_0 ] (Comp: 2, Cost: 1) evalwcet2bb1in(Ar_0, Ar_1, Ar_2, Ar_3) -> Com_1(evalwcet2bb5in(Ar_0, Ar_1, Ar_2, Ar_3)) [ Ar_0 >= 5 ] (Comp: ?, Cost: 1) evalwcet2bb2in(Ar_0, Ar_1, Ar_2, Ar_3) -> Com_1(evalwcet2bb3in(Ar_0, Ar_1, Ar_2, Ar_3)) [ Ar_0 >= 3 /\ 9 >= Ar_2 ] (Comp: ?, Cost: 1) evalwcet2bb2in(Ar_0, Ar_1, Ar_2, Ar_3) -> Com_1(evalwcet2bb4in(Ar_0, Ar_1, Ar_2, Ar_3)) [ 2 >= Ar_0 ] (Comp: ?, Cost: 1) evalwcet2bb2in(Ar_0, Ar_1, Ar_2, Ar_3) -> Com_1(evalwcet2bb4in(Ar_0, Ar_1, Ar_2, Ar_3)) [ Ar_2 >= 10 ] (Comp: ?, Cost: 1) evalwcet2bb3in(Ar_0, Ar_1, Ar_2, Ar_3) -> Com_1(evalwcet2bb2in(Ar_0, Ar_1, Ar_2 + 1, Ar_3)) (Comp: ?, Cost: 1) evalwcet2bb4in(Ar_0, Ar_1, Ar_2, Ar_3) -> Com_1(evalwcet27(Ar_0, Ar_1, Ar_2, Ar_0 + 1)) (Comp: ?, Cost: 1) evalwcet27(Ar_0, Ar_1, Ar_2, Ar_3) -> Com_1(evalwcet28(Ar_0, Ar_1, Ar_2, Ar_3)) (Comp: ?, Cost: 1) evalwcet28(Ar_0, Ar_1, Ar_2, Ar_3) -> Com_1(evalwcet2bb1in(Ar_3, Ar_1, Ar_2, Ar_3)) (Comp: 2, Cost: 1) evalwcet2bb5in(Ar_0, Ar_1, Ar_2, Ar_3) -> Com_1(evalwcet2stop(Ar_0, Ar_1, Ar_2, Ar_3)) (Comp: 1, Cost: 0) koat_start(Ar_0, Ar_1, Ar_2, Ar_3) -> Com_1(evalwcet2start(Ar_0, Ar_1, Ar_2, Ar_3)) [ 0 <= 0 ] start location: koat_start leaf cost: 0 A polynomial rank function with Pol(evalwcet2start) = -2*V_2 + 9 Pol(evalwcet2bb0in) = -2*V_2 + 9 Pol(evalwcet20) = -2*V_2 + 9 Pol(evalwcet21) = -2*V_2 + 9 Pol(evalwcet22) = -2*V_2 + 9 Pol(evalwcet23) = -2*V_2 + 9 Pol(evalwcet2bb1in) = -2*V_1 + 9 Pol(evalwcet2bb2in) = -2*V_1 + 8 Pol(evalwcet2bb5in) = -2*V_1 + 9 Pol(evalwcet2bb3in) = -2*V_1 + 8 Pol(evalwcet2bb4in) = -2*V_1 + 7 Pol(evalwcet27) = -2*V_4 + 9 Pol(evalwcet28) = -2*V_4 + 9 Pol(evalwcet2stop) = -2*V_1 + 9 Pol(koat_start) = -2*V_2 + 9 orients all transitions weakly and the transitions evalwcet2bb2in(Ar_0, Ar_1, Ar_2, Ar_3) -> Com_1(evalwcet2bb4in(Ar_0, Ar_1, Ar_2, Ar_3)) [ 2 >= Ar_0 ] evalwcet2bb1in(Ar_0, Ar_1, Ar_2, Ar_3) -> Com_1(evalwcet2bb2in(Ar_0, Ar_1, 0, Ar_3)) [ 4 >= Ar_0 ] strictly and produces the following problem: 4: T: (Comp: 1, Cost: 1) evalwcet2start(Ar_0, Ar_1, Ar_2, Ar_3) -> Com_1(evalwcet2bb0in(Ar_0, Ar_1, Ar_2, Ar_3)) (Comp: 1, Cost: 1) evalwcet2bb0in(Ar_0, Ar_1, Ar_2, Ar_3) -> Com_1(evalwcet20(Ar_0, Ar_1, Ar_2, Ar_3)) (Comp: 1, Cost: 1) evalwcet20(Ar_0, Ar_1, Ar_2, Ar_3) -> Com_1(evalwcet21(Ar_0, Ar_1, Ar_2, Ar_3)) (Comp: 1, Cost: 1) evalwcet21(Ar_0, Ar_1, Ar_2, Ar_3) -> Com_1(evalwcet22(Ar_0, Ar_1, Ar_2, Ar_3)) (Comp: 1, Cost: 1) evalwcet22(Ar_0, Ar_1, Ar_2, Ar_3) -> Com_1(evalwcet23(Ar_0, Ar_1, Ar_2, Ar_3)) (Comp: 1, Cost: 1) evalwcet23(Ar_0, Ar_1, Ar_2, Ar_3) -> Com_1(evalwcet2bb1in(Ar_1, Ar_1, Ar_2, Ar_3)) (Comp: 2*Ar_1 + 9, Cost: 1) evalwcet2bb1in(Ar_0, Ar_1, Ar_2, Ar_3) -> Com_1(evalwcet2bb2in(Ar_0, Ar_1, 0, Ar_3)) [ 4 >= Ar_0 ] (Comp: 2, Cost: 1) evalwcet2bb1in(Ar_0, Ar_1, Ar_2, Ar_3) -> Com_1(evalwcet2bb5in(Ar_0, Ar_1, Ar_2, Ar_3)) [ Ar_0 >= 5 ] (Comp: ?, Cost: 1) evalwcet2bb2in(Ar_0, Ar_1, Ar_2, Ar_3) -> Com_1(evalwcet2bb3in(Ar_0, Ar_1, Ar_2, Ar_3)) [ Ar_0 >= 3 /\ 9 >= Ar_2 ] (Comp: 2*Ar_1 + 9, Cost: 1) evalwcet2bb2in(Ar_0, Ar_1, Ar_2, Ar_3) -> Com_1(evalwcet2bb4in(Ar_0, Ar_1, Ar_2, Ar_3)) [ 2 >= Ar_0 ] (Comp: ?, Cost: 1) evalwcet2bb2in(Ar_0, Ar_1, Ar_2, Ar_3) -> Com_1(evalwcet2bb4in(Ar_0, Ar_1, Ar_2, Ar_3)) [ Ar_2 >= 10 ] (Comp: ?, Cost: 1) evalwcet2bb3in(Ar_0, Ar_1, Ar_2, Ar_3) -> Com_1(evalwcet2bb2in(Ar_0, Ar_1, Ar_2 + 1, Ar_3)) (Comp: ?, Cost: 1) evalwcet2bb4in(Ar_0, Ar_1, Ar_2, Ar_3) -> Com_1(evalwcet27(Ar_0, Ar_1, Ar_2, Ar_0 + 1)) (Comp: ?, Cost: 1) evalwcet27(Ar_0, Ar_1, Ar_2, Ar_3) -> Com_1(evalwcet28(Ar_0, Ar_1, Ar_2, Ar_3)) (Comp: ?, Cost: 1) evalwcet28(Ar_0, Ar_1, Ar_2, Ar_3) -> Com_1(evalwcet2bb1in(Ar_3, Ar_1, Ar_2, Ar_3)) (Comp: 2, Cost: 1) evalwcet2bb5in(Ar_0, Ar_1, Ar_2, Ar_3) -> Com_1(evalwcet2stop(Ar_0, Ar_1, Ar_2, Ar_3)) (Comp: 1, Cost: 0) koat_start(Ar_0, Ar_1, Ar_2, Ar_3) -> Com_1(evalwcet2start(Ar_0, Ar_1, Ar_2, Ar_3)) [ 0 <= 0 ] start location: koat_start leaf cost: 0 A polynomial rank function with Pol(evalwcet2bb4in) = 3 Pol(evalwcet27) = 2 Pol(evalwcet2bb3in) = 4 Pol(evalwcet2bb2in) = 4 Pol(evalwcet28) = 1 Pol(evalwcet2bb1in) = 0 and size complexities S("koat_start(Ar_0, Ar_1, Ar_2, Ar_3) -> Com_1(evalwcet2start(Ar_0, Ar_1, Ar_2, Ar_3)) [ 0 <= 0 ]", 0-0) = Ar_0 S("koat_start(Ar_0, Ar_1, Ar_2, Ar_3) -> Com_1(evalwcet2start(Ar_0, Ar_1, Ar_2, Ar_3)) [ 0 <= 0 ]", 0-1) = Ar_1 S("koat_start(Ar_0, Ar_1, Ar_2, Ar_3) -> Com_1(evalwcet2start(Ar_0, Ar_1, Ar_2, Ar_3)) [ 0 <= 0 ]", 0-2) = Ar_2 S("koat_start(Ar_0, Ar_1, Ar_2, Ar_3) -> Com_1(evalwcet2start(Ar_0, Ar_1, Ar_2, Ar_3)) [ 0 <= 0 ]", 0-3) = Ar_3 S("evalwcet2bb5in(Ar_0, Ar_1, Ar_2, Ar_3) -> Com_1(evalwcet2stop(Ar_0, Ar_1, Ar_2, Ar_3))", 0-0) = ? S("evalwcet2bb5in(Ar_0, Ar_1, Ar_2, Ar_3) -> Com_1(evalwcet2stop(Ar_0, Ar_1, Ar_2, Ar_3))", 0-1) = Ar_1 S("evalwcet2bb5in(Ar_0, Ar_1, Ar_2, Ar_3) -> Com_1(evalwcet2stop(Ar_0, Ar_1, Ar_2, Ar_3))", 0-2) = ? S("evalwcet2bb5in(Ar_0, Ar_1, Ar_2, Ar_3) -> Com_1(evalwcet2stop(Ar_0, Ar_1, Ar_2, Ar_3))", 0-3) = ? S("evalwcet28(Ar_0, Ar_1, Ar_2, Ar_3) -> Com_1(evalwcet2bb1in(Ar_3, Ar_1, Ar_2, Ar_3))", 0-0) = ? S("evalwcet28(Ar_0, Ar_1, Ar_2, Ar_3) -> Com_1(evalwcet2bb1in(Ar_3, Ar_1, Ar_2, Ar_3))", 0-1) = Ar_1 S("evalwcet28(Ar_0, Ar_1, Ar_2, Ar_3) -> Com_1(evalwcet2bb1in(Ar_3, Ar_1, Ar_2, Ar_3))", 0-2) = ? S("evalwcet28(Ar_0, Ar_1, Ar_2, Ar_3) -> Com_1(evalwcet2bb1in(Ar_3, Ar_1, Ar_2, Ar_3))", 0-3) = ? S("evalwcet27(Ar_0, Ar_1, Ar_2, Ar_3) -> Com_1(evalwcet28(Ar_0, Ar_1, Ar_2, Ar_3))", 0-0) = ? S("evalwcet27(Ar_0, Ar_1, Ar_2, Ar_3) -> Com_1(evalwcet28(Ar_0, Ar_1, Ar_2, Ar_3))", 0-1) = Ar_1 S("evalwcet27(Ar_0, Ar_1, Ar_2, Ar_3) -> Com_1(evalwcet28(Ar_0, Ar_1, Ar_2, Ar_3))", 0-2) = ? S("evalwcet27(Ar_0, Ar_1, Ar_2, Ar_3) -> Com_1(evalwcet28(Ar_0, Ar_1, Ar_2, Ar_3))", 0-3) = ? S("evalwcet2bb4in(Ar_0, Ar_1, Ar_2, Ar_3) -> Com_1(evalwcet27(Ar_0, Ar_1, Ar_2, Ar_0 + 1))", 0-0) = ? S("evalwcet2bb4in(Ar_0, Ar_1, Ar_2, Ar_3) -> Com_1(evalwcet27(Ar_0, Ar_1, Ar_2, Ar_0 + 1))", 0-1) = Ar_1 S("evalwcet2bb4in(Ar_0, Ar_1, Ar_2, Ar_3) -> Com_1(evalwcet27(Ar_0, Ar_1, Ar_2, Ar_0 + 1))", 0-2) = ? S("evalwcet2bb4in(Ar_0, Ar_1, Ar_2, Ar_3) -> Com_1(evalwcet27(Ar_0, Ar_1, Ar_2, Ar_0 + 1))", 0-3) = ? S("evalwcet2bb3in(Ar_0, Ar_1, Ar_2, Ar_3) -> Com_1(evalwcet2bb2in(Ar_0, Ar_1, Ar_2 + 1, Ar_3))", 0-0) = ? S("evalwcet2bb3in(Ar_0, Ar_1, Ar_2, Ar_3) -> Com_1(evalwcet2bb2in(Ar_0, Ar_1, Ar_2 + 1, Ar_3))", 0-1) = Ar_1 S("evalwcet2bb3in(Ar_0, Ar_1, Ar_2, Ar_3) -> Com_1(evalwcet2bb2in(Ar_0, Ar_1, Ar_2 + 1, Ar_3))", 0-2) = ? S("evalwcet2bb3in(Ar_0, Ar_1, Ar_2, Ar_3) -> Com_1(evalwcet2bb2in(Ar_0, Ar_1, Ar_2 + 1, Ar_3))", 0-3) = ? S("evalwcet2bb2in(Ar_0, Ar_1, Ar_2, Ar_3) -> Com_1(evalwcet2bb4in(Ar_0, Ar_1, Ar_2, Ar_3)) [ Ar_2 >= 10 ]", 0-0) = ? S("evalwcet2bb2in(Ar_0, Ar_1, Ar_2, Ar_3) -> Com_1(evalwcet2bb4in(Ar_0, Ar_1, Ar_2, Ar_3)) [ Ar_2 >= 10 ]", 0-1) = Ar_1 S("evalwcet2bb2in(Ar_0, Ar_1, Ar_2, Ar_3) -> Com_1(evalwcet2bb4in(Ar_0, Ar_1, Ar_2, Ar_3)) [ Ar_2 >= 10 ]", 0-2) = ? S("evalwcet2bb2in(Ar_0, Ar_1, Ar_2, Ar_3) -> Com_1(evalwcet2bb4in(Ar_0, Ar_1, Ar_2, Ar_3)) [ Ar_2 >= 10 ]", 0-3) = ? S("evalwcet2bb2in(Ar_0, Ar_1, Ar_2, Ar_3) -> Com_1(evalwcet2bb4in(Ar_0, Ar_1, Ar_2, Ar_3)) [ 2 >= Ar_0 ]", 0-0) = ? S("evalwcet2bb2in(Ar_0, Ar_1, Ar_2, Ar_3) -> Com_1(evalwcet2bb4in(Ar_0, Ar_1, Ar_2, Ar_3)) [ 2 >= Ar_0 ]", 0-1) = Ar_1 S("evalwcet2bb2in(Ar_0, Ar_1, Ar_2, Ar_3) -> Com_1(evalwcet2bb4in(Ar_0, Ar_1, Ar_2, Ar_3)) [ 2 >= Ar_0 ]", 0-2) = ? S("evalwcet2bb2in(Ar_0, Ar_1, Ar_2, Ar_3) -> Com_1(evalwcet2bb4in(Ar_0, Ar_1, Ar_2, Ar_3)) [ 2 >= Ar_0 ]", 0-3) = ? S("evalwcet2bb2in(Ar_0, Ar_1, Ar_2, Ar_3) -> Com_1(evalwcet2bb3in(Ar_0, Ar_1, Ar_2, Ar_3)) [ Ar_0 >= 3 /\\ 9 >= Ar_2 ]", 0-0) = ? S("evalwcet2bb2in(Ar_0, Ar_1, Ar_2, Ar_3) -> Com_1(evalwcet2bb3in(Ar_0, Ar_1, Ar_2, Ar_3)) [ Ar_0 >= 3 /\\ 9 >= Ar_2 ]", 0-1) = Ar_1 S("evalwcet2bb2in(Ar_0, Ar_1, Ar_2, Ar_3) -> Com_1(evalwcet2bb3in(Ar_0, Ar_1, Ar_2, Ar_3)) [ Ar_0 >= 3 /\\ 9 >= Ar_2 ]", 0-2) = ? S("evalwcet2bb2in(Ar_0, Ar_1, Ar_2, Ar_3) -> Com_1(evalwcet2bb3in(Ar_0, Ar_1, Ar_2, Ar_3)) [ Ar_0 >= 3 /\\ 9 >= Ar_2 ]", 0-3) = ? S("evalwcet2bb1in(Ar_0, Ar_1, Ar_2, Ar_3) -> Com_1(evalwcet2bb5in(Ar_0, Ar_1, Ar_2, Ar_3)) [ Ar_0 >= 5 ]", 0-0) = ? S("evalwcet2bb1in(Ar_0, Ar_1, Ar_2, Ar_3) -> Com_1(evalwcet2bb5in(Ar_0, Ar_1, Ar_2, Ar_3)) [ Ar_0 >= 5 ]", 0-1) = Ar_1 S("evalwcet2bb1in(Ar_0, Ar_1, Ar_2, Ar_3) -> Com_1(evalwcet2bb5in(Ar_0, Ar_1, Ar_2, Ar_3)) [ Ar_0 >= 5 ]", 0-2) = ? S("evalwcet2bb1in(Ar_0, Ar_1, Ar_2, Ar_3) -> Com_1(evalwcet2bb5in(Ar_0, Ar_1, Ar_2, Ar_3)) [ Ar_0 >= 5 ]", 0-3) = ? S("evalwcet2bb1in(Ar_0, Ar_1, Ar_2, Ar_3) -> Com_1(evalwcet2bb2in(Ar_0, Ar_1, 0, Ar_3)) [ 4 >= Ar_0 ]", 0-0) = ? S("evalwcet2bb1in(Ar_0, Ar_1, Ar_2, Ar_3) -> Com_1(evalwcet2bb2in(Ar_0, Ar_1, 0, Ar_3)) [ 4 >= Ar_0 ]", 0-1) = Ar_1 S("evalwcet2bb1in(Ar_0, Ar_1, Ar_2, Ar_3) -> Com_1(evalwcet2bb2in(Ar_0, Ar_1, 0, Ar_3)) [ 4 >= Ar_0 ]", 0-2) = 0 S("evalwcet2bb1in(Ar_0, Ar_1, Ar_2, Ar_3) -> Com_1(evalwcet2bb2in(Ar_0, Ar_1, 0, Ar_3)) [ 4 >= Ar_0 ]", 0-3) = ? S("evalwcet23(Ar_0, Ar_1, Ar_2, Ar_3) -> Com_1(evalwcet2bb1in(Ar_1, Ar_1, Ar_2, Ar_3))", 0-0) = Ar_1 S("evalwcet23(Ar_0, Ar_1, Ar_2, Ar_3) -> Com_1(evalwcet2bb1in(Ar_1, Ar_1, Ar_2, Ar_3))", 0-1) = Ar_1 S("evalwcet23(Ar_0, Ar_1, Ar_2, Ar_3) -> Com_1(evalwcet2bb1in(Ar_1, Ar_1, Ar_2, Ar_3))", 0-2) = Ar_2 S("evalwcet23(Ar_0, Ar_1, Ar_2, Ar_3) -> Com_1(evalwcet2bb1in(Ar_1, Ar_1, Ar_2, Ar_3))", 0-3) = Ar_3 S("evalwcet22(Ar_0, Ar_1, Ar_2, Ar_3) -> Com_1(evalwcet23(Ar_0, Ar_1, Ar_2, Ar_3))", 0-0) = Ar_0 S("evalwcet22(Ar_0, Ar_1, Ar_2, Ar_3) -> Com_1(evalwcet23(Ar_0, Ar_1, Ar_2, Ar_3))", 0-1) = Ar_1 S("evalwcet22(Ar_0, Ar_1, Ar_2, Ar_3) -> Com_1(evalwcet23(Ar_0, Ar_1, Ar_2, Ar_3))", 0-2) = Ar_2 S("evalwcet22(Ar_0, Ar_1, Ar_2, Ar_3) -> Com_1(evalwcet23(Ar_0, Ar_1, Ar_2, Ar_3))", 0-3) = Ar_3 S("evalwcet21(Ar_0, Ar_1, Ar_2, Ar_3) -> Com_1(evalwcet22(Ar_0, Ar_1, Ar_2, Ar_3))", 0-0) = Ar_0 S("evalwcet21(Ar_0, Ar_1, Ar_2, Ar_3) -> Com_1(evalwcet22(Ar_0, Ar_1, Ar_2, Ar_3))", 0-1) = Ar_1 S("evalwcet21(Ar_0, Ar_1, Ar_2, Ar_3) -> Com_1(evalwcet22(Ar_0, Ar_1, Ar_2, Ar_3))", 0-2) = Ar_2 S("evalwcet21(Ar_0, Ar_1, Ar_2, Ar_3) -> Com_1(evalwcet22(Ar_0, Ar_1, Ar_2, Ar_3))", 0-3) = Ar_3 S("evalwcet20(Ar_0, Ar_1, Ar_2, Ar_3) -> Com_1(evalwcet21(Ar_0, Ar_1, Ar_2, Ar_3))", 0-0) = Ar_0 S("evalwcet20(Ar_0, Ar_1, Ar_2, Ar_3) -> Com_1(evalwcet21(Ar_0, Ar_1, Ar_2, Ar_3))", 0-1) = Ar_1 S("evalwcet20(Ar_0, Ar_1, Ar_2, Ar_3) -> Com_1(evalwcet21(Ar_0, Ar_1, Ar_2, Ar_3))", 0-2) = Ar_2 S("evalwcet20(Ar_0, Ar_1, Ar_2, Ar_3) -> Com_1(evalwcet21(Ar_0, Ar_1, Ar_2, Ar_3))", 0-3) = Ar_3 S("evalwcet2bb0in(Ar_0, Ar_1, Ar_2, Ar_3) -> Com_1(evalwcet20(Ar_0, Ar_1, Ar_2, Ar_3))", 0-0) = Ar_0 S("evalwcet2bb0in(Ar_0, Ar_1, Ar_2, Ar_3) -> Com_1(evalwcet20(Ar_0, Ar_1, Ar_2, Ar_3))", 0-1) = Ar_1 S("evalwcet2bb0in(Ar_0, Ar_1, Ar_2, Ar_3) -> Com_1(evalwcet20(Ar_0, Ar_1, Ar_2, Ar_3))", 0-2) = Ar_2 S("evalwcet2bb0in(Ar_0, Ar_1, Ar_2, Ar_3) -> Com_1(evalwcet20(Ar_0, Ar_1, Ar_2, Ar_3))", 0-3) = Ar_3 S("evalwcet2start(Ar_0, Ar_1, Ar_2, Ar_3) -> Com_1(evalwcet2bb0in(Ar_0, Ar_1, Ar_2, Ar_3))", 0-0) = Ar_0 S("evalwcet2start(Ar_0, Ar_1, Ar_2, Ar_3) -> Com_1(evalwcet2bb0in(Ar_0, Ar_1, Ar_2, Ar_3))", 0-1) = Ar_1 S("evalwcet2start(Ar_0, Ar_1, Ar_2, Ar_3) -> Com_1(evalwcet2bb0in(Ar_0, Ar_1, Ar_2, Ar_3))", 0-2) = Ar_2 S("evalwcet2start(Ar_0, Ar_1, Ar_2, Ar_3) -> Com_1(evalwcet2bb0in(Ar_0, Ar_1, Ar_2, Ar_3))", 0-3) = Ar_3 orients the transitions evalwcet2bb4in(Ar_0, Ar_1, Ar_2, Ar_3) -> Com_1(evalwcet27(Ar_0, Ar_1, Ar_2, Ar_0 + 1)) evalwcet2bb3in(Ar_0, Ar_1, Ar_2, Ar_3) -> Com_1(evalwcet2bb2in(Ar_0, Ar_1, Ar_2 + 1, Ar_3)) evalwcet2bb2in(Ar_0, Ar_1, Ar_2, Ar_3) -> Com_1(evalwcet2bb4in(Ar_0, Ar_1, Ar_2, Ar_3)) [ Ar_2 >= 10 ] evalwcet2bb2in(Ar_0, Ar_1, Ar_2, Ar_3) -> Com_1(evalwcet2bb3in(Ar_0, Ar_1, Ar_2, Ar_3)) [ Ar_0 >= 3 /\ 9 >= Ar_2 ] evalwcet28(Ar_0, Ar_1, Ar_2, Ar_3) -> Com_1(evalwcet2bb1in(Ar_3, Ar_1, Ar_2, Ar_3)) evalwcet27(Ar_0, Ar_1, Ar_2, Ar_3) -> Com_1(evalwcet28(Ar_0, Ar_1, Ar_2, Ar_3)) weakly and the transitions evalwcet2bb4in(Ar_0, Ar_1, Ar_2, Ar_3) -> Com_1(evalwcet27(Ar_0, Ar_1, Ar_2, Ar_0 + 1)) evalwcet2bb2in(Ar_0, Ar_1, Ar_2, Ar_3) -> Com_1(evalwcet2bb4in(Ar_0, Ar_1, Ar_2, Ar_3)) [ Ar_2 >= 10 ] evalwcet28(Ar_0, Ar_1, Ar_2, Ar_3) -> Com_1(evalwcet2bb1in(Ar_3, Ar_1, Ar_2, Ar_3)) evalwcet27(Ar_0, Ar_1, Ar_2, Ar_3) -> Com_1(evalwcet28(Ar_0, Ar_1, Ar_2, Ar_3)) strictly and produces the following problem: 5: T: (Comp: 1, Cost: 1) evalwcet2start(Ar_0, Ar_1, Ar_2, Ar_3) -> Com_1(evalwcet2bb0in(Ar_0, Ar_1, Ar_2, Ar_3)) (Comp: 1, Cost: 1) evalwcet2bb0in(Ar_0, Ar_1, Ar_2, Ar_3) -> Com_1(evalwcet20(Ar_0, Ar_1, Ar_2, Ar_3)) (Comp: 1, Cost: 1) evalwcet20(Ar_0, Ar_1, Ar_2, Ar_3) -> Com_1(evalwcet21(Ar_0, Ar_1, Ar_2, Ar_3)) (Comp: 1, Cost: 1) evalwcet21(Ar_0, Ar_1, Ar_2, Ar_3) -> Com_1(evalwcet22(Ar_0, Ar_1, Ar_2, Ar_3)) (Comp: 1, Cost: 1) evalwcet22(Ar_0, Ar_1, Ar_2, Ar_3) -> Com_1(evalwcet23(Ar_0, Ar_1, Ar_2, Ar_3)) (Comp: 1, Cost: 1) evalwcet23(Ar_0, Ar_1, Ar_2, Ar_3) -> Com_1(evalwcet2bb1in(Ar_1, Ar_1, Ar_2, Ar_3)) (Comp: 2*Ar_1 + 9, Cost: 1) evalwcet2bb1in(Ar_0, Ar_1, Ar_2, Ar_3) -> Com_1(evalwcet2bb2in(Ar_0, Ar_1, 0, Ar_3)) [ 4 >= Ar_0 ] (Comp: 2, Cost: 1) evalwcet2bb1in(Ar_0, Ar_1, Ar_2, Ar_3) -> Com_1(evalwcet2bb5in(Ar_0, Ar_1, Ar_2, Ar_3)) [ Ar_0 >= 5 ] (Comp: ?, Cost: 1) evalwcet2bb2in(Ar_0, Ar_1, Ar_2, Ar_3) -> Com_1(evalwcet2bb3in(Ar_0, Ar_1, Ar_2, Ar_3)) [ Ar_0 >= 3 /\ 9 >= Ar_2 ] (Comp: 2*Ar_1 + 9, Cost: 1) evalwcet2bb2in(Ar_0, Ar_1, Ar_2, Ar_3) -> Com_1(evalwcet2bb4in(Ar_0, Ar_1, Ar_2, Ar_3)) [ 2 >= Ar_0 ] (Comp: 14*Ar_1 + 63, Cost: 1) evalwcet2bb2in(Ar_0, Ar_1, Ar_2, Ar_3) -> Com_1(evalwcet2bb4in(Ar_0, Ar_1, Ar_2, Ar_3)) [ Ar_2 >= 10 ] (Comp: ?, Cost: 1) evalwcet2bb3in(Ar_0, Ar_1, Ar_2, Ar_3) -> Com_1(evalwcet2bb2in(Ar_0, Ar_1, Ar_2 + 1, Ar_3)) (Comp: 14*Ar_1 + 63, Cost: 1) evalwcet2bb4in(Ar_0, Ar_1, Ar_2, Ar_3) -> Com_1(evalwcet27(Ar_0, Ar_1, Ar_2, Ar_0 + 1)) (Comp: 14*Ar_1 + 63, Cost: 1) evalwcet27(Ar_0, Ar_1, Ar_2, Ar_3) -> Com_1(evalwcet28(Ar_0, Ar_1, Ar_2, Ar_3)) (Comp: 14*Ar_1 + 63, Cost: 1) evalwcet28(Ar_0, Ar_1, Ar_2, Ar_3) -> Com_1(evalwcet2bb1in(Ar_3, Ar_1, Ar_2, Ar_3)) (Comp: 2, Cost: 1) evalwcet2bb5in(Ar_0, Ar_1, Ar_2, Ar_3) -> Com_1(evalwcet2stop(Ar_0, Ar_1, Ar_2, Ar_3)) (Comp: 1, Cost: 0) koat_start(Ar_0, Ar_1, Ar_2, Ar_3) -> Com_1(evalwcet2start(Ar_0, Ar_1, Ar_2, Ar_3)) [ 0 <= 0 ] start location: koat_start leaf cost: 0 A polynomial rank function with Pol(evalwcet2bb3in) = -V_3 + 9 Pol(evalwcet2bb2in) = -V_3 + 10 and size complexities S("koat_start(Ar_0, Ar_1, Ar_2, Ar_3) -> Com_1(evalwcet2start(Ar_0, Ar_1, Ar_2, Ar_3)) [ 0 <= 0 ]", 0-0) = Ar_0 S("koat_start(Ar_0, Ar_1, Ar_2, Ar_3) -> Com_1(evalwcet2start(Ar_0, Ar_1, Ar_2, Ar_3)) [ 0 <= 0 ]", 0-1) = Ar_1 S("koat_start(Ar_0, Ar_1, Ar_2, Ar_3) -> Com_1(evalwcet2start(Ar_0, Ar_1, Ar_2, Ar_3)) [ 0 <= 0 ]", 0-2) = Ar_2 S("koat_start(Ar_0, Ar_1, Ar_2, Ar_3) -> Com_1(evalwcet2start(Ar_0, Ar_1, Ar_2, Ar_3)) [ 0 <= 0 ]", 0-3) = Ar_3 S("evalwcet2bb5in(Ar_0, Ar_1, Ar_2, Ar_3) -> Com_1(evalwcet2stop(Ar_0, Ar_1, Ar_2, Ar_3))", 0-0) = 15*Ar_1 + 3189375 S("evalwcet2bb5in(Ar_0, Ar_1, Ar_2, Ar_3) -> Com_1(evalwcet2stop(Ar_0, Ar_1, Ar_2, Ar_3))", 0-1) = Ar_1 S("evalwcet2bb5in(Ar_0, Ar_1, Ar_2, Ar_3) -> Com_1(evalwcet2stop(Ar_0, Ar_1, Ar_2, Ar_3))", 0-2) = ? S("evalwcet2bb5in(Ar_0, Ar_1, Ar_2, Ar_3) -> Com_1(evalwcet2stop(Ar_0, Ar_1, Ar_2, Ar_3))", 0-3) = 15*Ar_1 + 15*Ar_3 + 47840625 S("evalwcet28(Ar_0, Ar_1, Ar_2, Ar_3) -> Com_1(evalwcet2bb1in(Ar_3, Ar_1, Ar_2, Ar_3))", 0-0) = 15*Ar_1 + 14175 S("evalwcet28(Ar_0, Ar_1, Ar_2, Ar_3) -> Com_1(evalwcet2bb1in(Ar_3, Ar_1, Ar_2, Ar_3))", 0-1) = Ar_1 S("evalwcet28(Ar_0, Ar_1, Ar_2, Ar_3) -> Com_1(evalwcet2bb1in(Ar_3, Ar_1, Ar_2, Ar_3))", 0-2) = ? S("evalwcet28(Ar_0, Ar_1, Ar_2, Ar_3) -> Com_1(evalwcet2bb1in(Ar_3, Ar_1, Ar_2, Ar_3))", 0-3) = 15*Ar_1 + 212625 S("evalwcet27(Ar_0, Ar_1, Ar_2, Ar_3) -> Com_1(evalwcet28(Ar_0, Ar_1, Ar_2, Ar_3))", 0-0) = 15*Ar_1 + 3189375 S("evalwcet27(Ar_0, Ar_1, Ar_2, Ar_3) -> Com_1(evalwcet28(Ar_0, Ar_1, Ar_2, Ar_3))", 0-1) = Ar_1 S("evalwcet27(Ar_0, Ar_1, Ar_2, Ar_3) -> Com_1(evalwcet28(Ar_0, Ar_1, Ar_2, Ar_3))", 0-2) = ? S("evalwcet27(Ar_0, Ar_1, Ar_2, Ar_3) -> Com_1(evalwcet28(Ar_0, Ar_1, Ar_2, Ar_3))", 0-3) = 15*Ar_1 + 14175 S("evalwcet2bb4in(Ar_0, Ar_1, Ar_2, Ar_3) -> Com_1(evalwcet27(Ar_0, Ar_1, Ar_2, Ar_0 + 1))", 0-0) = 15*Ar_1 + 212625 S("evalwcet2bb4in(Ar_0, Ar_1, Ar_2, Ar_3) -> Com_1(evalwcet27(Ar_0, Ar_1, Ar_2, Ar_0 + 1))", 0-1) = Ar_1 S("evalwcet2bb4in(Ar_0, Ar_1, Ar_2, Ar_3) -> Com_1(evalwcet27(Ar_0, Ar_1, Ar_2, Ar_0 + 1))", 0-2) = ? S("evalwcet2bb4in(Ar_0, Ar_1, Ar_2, Ar_3) -> Com_1(evalwcet27(Ar_0, Ar_1, Ar_2, Ar_0 + 1))", 0-3) = 15*Ar_1 + 14175 S("evalwcet2bb3in(Ar_0, Ar_1, Ar_2, Ar_3) -> Com_1(evalwcet2bb2in(Ar_0, Ar_1, Ar_2 + 1, Ar_3))", 0-0) = 15*Ar_1 + 14175 S("evalwcet2bb3in(Ar_0, Ar_1, Ar_2, Ar_3) -> Com_1(evalwcet2bb2in(Ar_0, Ar_1, Ar_2 + 1, Ar_3))", 0-1) = Ar_1 S("evalwcet2bb3in(Ar_0, Ar_1, Ar_2, Ar_3) -> Com_1(evalwcet2bb2in(Ar_0, Ar_1, Ar_2 + 1, Ar_3))", 0-2) = ? S("evalwcet2bb3in(Ar_0, Ar_1, Ar_2, Ar_3) -> Com_1(evalwcet2bb2in(Ar_0, Ar_1, Ar_2 + 1, Ar_3))", 0-3) = 15*Ar_1 + 15*Ar_3 + 47840625 S("evalwcet2bb2in(Ar_0, Ar_1, Ar_2, Ar_3) -> Com_1(evalwcet2bb4in(Ar_0, Ar_1, Ar_2, Ar_3)) [ Ar_2 >= 10 ]", 0-0) = 15*Ar_1 + 14175 S("evalwcet2bb2in(Ar_0, Ar_1, Ar_2, Ar_3) -> Com_1(evalwcet2bb4in(Ar_0, Ar_1, Ar_2, Ar_3)) [ Ar_2 >= 10 ]", 0-1) = Ar_1 S("evalwcet2bb2in(Ar_0, Ar_1, Ar_2, Ar_3) -> Com_1(evalwcet2bb4in(Ar_0, Ar_1, Ar_2, Ar_3)) [ Ar_2 >= 10 ]", 0-2) = ? S("evalwcet2bb2in(Ar_0, Ar_1, Ar_2, Ar_3) -> Com_1(evalwcet2bb4in(Ar_0, Ar_1, Ar_2, Ar_3)) [ Ar_2 >= 10 ]", 0-3) = 15*Ar_1 + 15*Ar_3 + 717609375 S("evalwcet2bb2in(Ar_0, Ar_1, Ar_2, Ar_3) -> Com_1(evalwcet2bb4in(Ar_0, Ar_1, Ar_2, Ar_3)) [ 2 >= Ar_0 ]", 0-0) = 15*Ar_1 + 14175 S("evalwcet2bb2in(Ar_0, Ar_1, Ar_2, Ar_3) -> Com_1(evalwcet2bb4in(Ar_0, Ar_1, Ar_2, Ar_3)) [ 2 >= Ar_0 ]", 0-1) = Ar_1 S("evalwcet2bb2in(Ar_0, Ar_1, Ar_2, Ar_3) -> Com_1(evalwcet2bb4in(Ar_0, Ar_1, Ar_2, Ar_3)) [ 2 >= Ar_0 ]", 0-2) = ? S("evalwcet2bb2in(Ar_0, Ar_1, Ar_2, Ar_3) -> Com_1(evalwcet2bb4in(Ar_0, Ar_1, Ar_2, Ar_3)) [ 2 >= Ar_0 ]", 0-3) = 15*Ar_1 + 15*Ar_3 + 717609375 S("evalwcet2bb2in(Ar_0, Ar_1, Ar_2, Ar_3) -> Com_1(evalwcet2bb3in(Ar_0, Ar_1, Ar_2, Ar_3)) [ Ar_0 >= 3 /\\ 9 >= Ar_2 ]", 0-0) = 15*Ar_1 + 14175 S("evalwcet2bb2in(Ar_0, Ar_1, Ar_2, Ar_3) -> Com_1(evalwcet2bb3in(Ar_0, Ar_1, Ar_2, Ar_3)) [ Ar_0 >= 3 /\\ 9 >= Ar_2 ]", 0-1) = Ar_1 S("evalwcet2bb2in(Ar_0, Ar_1, Ar_2, Ar_3) -> Com_1(evalwcet2bb3in(Ar_0, Ar_1, Ar_2, Ar_3)) [ Ar_0 >= 3 /\\ 9 >= Ar_2 ]", 0-2) = ? S("evalwcet2bb2in(Ar_0, Ar_1, Ar_2, Ar_3) -> Com_1(evalwcet2bb3in(Ar_0, Ar_1, Ar_2, Ar_3)) [ Ar_0 >= 3 /\\ 9 >= Ar_2 ]", 0-3) = 15*Ar_1 + 15*Ar_3 + 47840625 S("evalwcet2bb1in(Ar_0, Ar_1, Ar_2, Ar_3) -> Com_1(evalwcet2bb5in(Ar_0, Ar_1, Ar_2, Ar_3)) [ Ar_0 >= 5 ]", 0-0) = 15*Ar_1 + 212625 S("evalwcet2bb1in(Ar_0, Ar_1, Ar_2, Ar_3) -> Com_1(evalwcet2bb5in(Ar_0, Ar_1, Ar_2, Ar_3)) [ Ar_0 >= 5 ]", 0-1) = Ar_1 S("evalwcet2bb1in(Ar_0, Ar_1, Ar_2, Ar_3) -> Com_1(evalwcet2bb5in(Ar_0, Ar_1, Ar_2, Ar_3)) [ Ar_0 >= 5 ]", 0-2) = ? S("evalwcet2bb1in(Ar_0, Ar_1, Ar_2, Ar_3) -> Com_1(evalwcet2bb5in(Ar_0, Ar_1, Ar_2, Ar_3)) [ Ar_0 >= 5 ]", 0-3) = 15*Ar_1 + 15*Ar_3 + 3189375 S("evalwcet2bb1in(Ar_0, Ar_1, Ar_2, Ar_3) -> Com_1(evalwcet2bb2in(Ar_0, Ar_1, 0, Ar_3)) [ 4 >= Ar_0 ]", 0-0) = 15*Ar_1 + 14175 S("evalwcet2bb1in(Ar_0, Ar_1, Ar_2, Ar_3) -> Com_1(evalwcet2bb2in(Ar_0, Ar_1, 0, Ar_3)) [ 4 >= Ar_0 ]", 0-1) = Ar_1 S("evalwcet2bb1in(Ar_0, Ar_1, Ar_2, Ar_3) -> Com_1(evalwcet2bb2in(Ar_0, Ar_1, 0, Ar_3)) [ 4 >= Ar_0 ]", 0-2) = 0 S("evalwcet2bb1in(Ar_0, Ar_1, Ar_2, Ar_3) -> Com_1(evalwcet2bb2in(Ar_0, Ar_1, 0, Ar_3)) [ 4 >= Ar_0 ]", 0-3) = 15*Ar_1 + 15*Ar_3 + 3189375 S("evalwcet23(Ar_0, Ar_1, Ar_2, Ar_3) -> Com_1(evalwcet2bb1in(Ar_1, Ar_1, Ar_2, Ar_3))", 0-0) = Ar_1 S("evalwcet23(Ar_0, Ar_1, Ar_2, Ar_3) -> Com_1(evalwcet2bb1in(Ar_1, Ar_1, Ar_2, Ar_3))", 0-1) = Ar_1 S("evalwcet23(Ar_0, Ar_1, Ar_2, Ar_3) -> Com_1(evalwcet2bb1in(Ar_1, Ar_1, Ar_2, Ar_3))", 0-2) = Ar_2 S("evalwcet23(Ar_0, Ar_1, Ar_2, Ar_3) -> Com_1(evalwcet2bb1in(Ar_1, Ar_1, Ar_2, Ar_3))", 0-3) = Ar_3 S("evalwcet22(Ar_0, Ar_1, Ar_2, Ar_3) -> Com_1(evalwcet23(Ar_0, Ar_1, Ar_2, Ar_3))", 0-0) = Ar_0 S("evalwcet22(Ar_0, Ar_1, Ar_2, Ar_3) -> Com_1(evalwcet23(Ar_0, Ar_1, Ar_2, Ar_3))", 0-1) = Ar_1 S("evalwcet22(Ar_0, Ar_1, Ar_2, Ar_3) -> Com_1(evalwcet23(Ar_0, Ar_1, Ar_2, Ar_3))", 0-2) = Ar_2 S("evalwcet22(Ar_0, Ar_1, Ar_2, Ar_3) -> Com_1(evalwcet23(Ar_0, Ar_1, Ar_2, Ar_3))", 0-3) = Ar_3 S("evalwcet21(Ar_0, Ar_1, Ar_2, Ar_3) -> Com_1(evalwcet22(Ar_0, Ar_1, Ar_2, Ar_3))", 0-0) = Ar_0 S("evalwcet21(Ar_0, Ar_1, Ar_2, Ar_3) -> Com_1(evalwcet22(Ar_0, Ar_1, Ar_2, Ar_3))", 0-1) = Ar_1 S("evalwcet21(Ar_0, Ar_1, Ar_2, Ar_3) -> Com_1(evalwcet22(Ar_0, Ar_1, Ar_2, Ar_3))", 0-2) = Ar_2 S("evalwcet21(Ar_0, Ar_1, Ar_2, Ar_3) -> Com_1(evalwcet22(Ar_0, Ar_1, Ar_2, Ar_3))", 0-3) = Ar_3 S("evalwcet20(Ar_0, Ar_1, Ar_2, Ar_3) -> Com_1(evalwcet21(Ar_0, Ar_1, Ar_2, Ar_3))", 0-0) = Ar_0 S("evalwcet20(Ar_0, Ar_1, Ar_2, Ar_3) -> Com_1(evalwcet21(Ar_0, Ar_1, Ar_2, Ar_3))", 0-1) = Ar_1 S("evalwcet20(Ar_0, Ar_1, Ar_2, Ar_3) -> Com_1(evalwcet21(Ar_0, Ar_1, Ar_2, Ar_3))", 0-2) = Ar_2 S("evalwcet20(Ar_0, Ar_1, Ar_2, Ar_3) -> Com_1(evalwcet21(Ar_0, Ar_1, Ar_2, Ar_3))", 0-3) = Ar_3 S("evalwcet2bb0in(Ar_0, Ar_1, Ar_2, Ar_3) -> Com_1(evalwcet20(Ar_0, Ar_1, Ar_2, Ar_3))", 0-0) = Ar_0 S("evalwcet2bb0in(Ar_0, Ar_1, Ar_2, Ar_3) -> Com_1(evalwcet20(Ar_0, Ar_1, Ar_2, Ar_3))", 0-1) = Ar_1 S("evalwcet2bb0in(Ar_0, Ar_1, Ar_2, Ar_3) -> Com_1(evalwcet20(Ar_0, Ar_1, Ar_2, Ar_3))", 0-2) = Ar_2 S("evalwcet2bb0in(Ar_0, Ar_1, Ar_2, Ar_3) -> Com_1(evalwcet20(Ar_0, Ar_1, Ar_2, Ar_3))", 0-3) = Ar_3 S("evalwcet2start(Ar_0, Ar_1, Ar_2, Ar_3) -> Com_1(evalwcet2bb0in(Ar_0, Ar_1, Ar_2, Ar_3))", 0-0) = Ar_0 S("evalwcet2start(Ar_0, Ar_1, Ar_2, Ar_3) -> Com_1(evalwcet2bb0in(Ar_0, Ar_1, Ar_2, Ar_3))", 0-1) = Ar_1 S("evalwcet2start(Ar_0, Ar_1, Ar_2, Ar_3) -> Com_1(evalwcet2bb0in(Ar_0, Ar_1, Ar_2, Ar_3))", 0-2) = Ar_2 S("evalwcet2start(Ar_0, Ar_1, Ar_2, Ar_3) -> Com_1(evalwcet2bb0in(Ar_0, Ar_1, Ar_2, Ar_3))", 0-3) = Ar_3 orients the transitions evalwcet2bb3in(Ar_0, Ar_1, Ar_2, Ar_3) -> Com_1(evalwcet2bb2in(Ar_0, Ar_1, Ar_2 + 1, Ar_3)) evalwcet2bb2in(Ar_0, Ar_1, Ar_2, Ar_3) -> Com_1(evalwcet2bb3in(Ar_0, Ar_1, Ar_2, Ar_3)) [ Ar_0 >= 3 /\ 9 >= Ar_2 ] weakly and the transition evalwcet2bb2in(Ar_0, Ar_1, Ar_2, Ar_3) -> Com_1(evalwcet2bb3in(Ar_0, Ar_1, Ar_2, Ar_3)) [ Ar_0 >= 3 /\ 9 >= Ar_2 ] strictly and produces the following problem: 6: T: (Comp: 1, Cost: 1) evalwcet2start(Ar_0, Ar_1, Ar_2, Ar_3) -> Com_1(evalwcet2bb0in(Ar_0, Ar_1, Ar_2, Ar_3)) (Comp: 1, Cost: 1) evalwcet2bb0in(Ar_0, Ar_1, Ar_2, Ar_3) -> Com_1(evalwcet20(Ar_0, Ar_1, Ar_2, Ar_3)) (Comp: 1, Cost: 1) evalwcet20(Ar_0, Ar_1, Ar_2, Ar_3) -> Com_1(evalwcet21(Ar_0, Ar_1, Ar_2, Ar_3)) (Comp: 1, Cost: 1) evalwcet21(Ar_0, Ar_1, Ar_2, Ar_3) -> Com_1(evalwcet22(Ar_0, Ar_1, Ar_2, Ar_3)) (Comp: 1, Cost: 1) evalwcet22(Ar_0, Ar_1, Ar_2, Ar_3) -> Com_1(evalwcet23(Ar_0, Ar_1, Ar_2, Ar_3)) (Comp: 1, Cost: 1) evalwcet23(Ar_0, Ar_1, Ar_2, Ar_3) -> Com_1(evalwcet2bb1in(Ar_1, Ar_1, Ar_2, Ar_3)) (Comp: 2*Ar_1 + 9, Cost: 1) evalwcet2bb1in(Ar_0, Ar_1, Ar_2, Ar_3) -> Com_1(evalwcet2bb2in(Ar_0, Ar_1, 0, Ar_3)) [ 4 >= Ar_0 ] (Comp: 2, Cost: 1) evalwcet2bb1in(Ar_0, Ar_1, Ar_2, Ar_3) -> Com_1(evalwcet2bb5in(Ar_0, Ar_1, Ar_2, Ar_3)) [ Ar_0 >= 5 ] (Comp: 20*Ar_1 + 90, Cost: 1) evalwcet2bb2in(Ar_0, Ar_1, Ar_2, Ar_3) -> Com_1(evalwcet2bb3in(Ar_0, Ar_1, Ar_2, Ar_3)) [ Ar_0 >= 3 /\ 9 >= Ar_2 ] (Comp: 2*Ar_1 + 9, Cost: 1) evalwcet2bb2in(Ar_0, Ar_1, Ar_2, Ar_3) -> Com_1(evalwcet2bb4in(Ar_0, Ar_1, Ar_2, Ar_3)) [ 2 >= Ar_0 ] (Comp: 14*Ar_1 + 63, Cost: 1) evalwcet2bb2in(Ar_0, Ar_1, Ar_2, Ar_3) -> Com_1(evalwcet2bb4in(Ar_0, Ar_1, Ar_2, Ar_3)) [ Ar_2 >= 10 ] (Comp: ?, Cost: 1) evalwcet2bb3in(Ar_0, Ar_1, Ar_2, Ar_3) -> Com_1(evalwcet2bb2in(Ar_0, Ar_1, Ar_2 + 1, Ar_3)) (Comp: 14*Ar_1 + 63, Cost: 1) evalwcet2bb4in(Ar_0, Ar_1, Ar_2, Ar_3) -> Com_1(evalwcet27(Ar_0, Ar_1, Ar_2, Ar_0 + 1)) (Comp: 14*Ar_1 + 63, Cost: 1) evalwcet27(Ar_0, Ar_1, Ar_2, Ar_3) -> Com_1(evalwcet28(Ar_0, Ar_1, Ar_2, Ar_3)) (Comp: 14*Ar_1 + 63, Cost: 1) evalwcet28(Ar_0, Ar_1, Ar_2, Ar_3) -> Com_1(evalwcet2bb1in(Ar_3, Ar_1, Ar_2, Ar_3)) (Comp: 2, Cost: 1) evalwcet2bb5in(Ar_0, Ar_1, Ar_2, Ar_3) -> Com_1(evalwcet2stop(Ar_0, Ar_1, Ar_2, Ar_3)) (Comp: 1, Cost: 0) koat_start(Ar_0, Ar_1, Ar_2, Ar_3) -> Com_1(evalwcet2start(Ar_0, Ar_1, Ar_2, Ar_3)) [ 0 <= 0 ] start location: koat_start leaf cost: 0 Repeatedly propagating knowledge in problem 6 produces the following problem: 7: T: (Comp: 1, Cost: 1) evalwcet2start(Ar_0, Ar_1, Ar_2, Ar_3) -> Com_1(evalwcet2bb0in(Ar_0, Ar_1, Ar_2, Ar_3)) (Comp: 1, Cost: 1) evalwcet2bb0in(Ar_0, Ar_1, Ar_2, Ar_3) -> Com_1(evalwcet20(Ar_0, Ar_1, Ar_2, Ar_3)) (Comp: 1, Cost: 1) evalwcet20(Ar_0, Ar_1, Ar_2, Ar_3) -> Com_1(evalwcet21(Ar_0, Ar_1, Ar_2, Ar_3)) (Comp: 1, Cost: 1) evalwcet21(Ar_0, Ar_1, Ar_2, Ar_3) -> Com_1(evalwcet22(Ar_0, Ar_1, Ar_2, Ar_3)) (Comp: 1, Cost: 1) evalwcet22(Ar_0, Ar_1, Ar_2, Ar_3) -> Com_1(evalwcet23(Ar_0, Ar_1, Ar_2, Ar_3)) (Comp: 1, Cost: 1) evalwcet23(Ar_0, Ar_1, Ar_2, Ar_3) -> Com_1(evalwcet2bb1in(Ar_1, Ar_1, Ar_2, Ar_3)) (Comp: 2*Ar_1 + 9, Cost: 1) evalwcet2bb1in(Ar_0, Ar_1, Ar_2, Ar_3) -> Com_1(evalwcet2bb2in(Ar_0, Ar_1, 0, Ar_3)) [ 4 >= Ar_0 ] (Comp: 2, Cost: 1) evalwcet2bb1in(Ar_0, Ar_1, Ar_2, Ar_3) -> Com_1(evalwcet2bb5in(Ar_0, Ar_1, Ar_2, Ar_3)) [ Ar_0 >= 5 ] (Comp: 20*Ar_1 + 90, Cost: 1) evalwcet2bb2in(Ar_0, Ar_1, Ar_2, Ar_3) -> Com_1(evalwcet2bb3in(Ar_0, Ar_1, Ar_2, Ar_3)) [ Ar_0 >= 3 /\ 9 >= Ar_2 ] (Comp: 2*Ar_1 + 9, Cost: 1) evalwcet2bb2in(Ar_0, Ar_1, Ar_2, Ar_3) -> Com_1(evalwcet2bb4in(Ar_0, Ar_1, Ar_2, Ar_3)) [ 2 >= Ar_0 ] (Comp: 14*Ar_1 + 63, Cost: 1) evalwcet2bb2in(Ar_0, Ar_1, Ar_2, Ar_3) -> Com_1(evalwcet2bb4in(Ar_0, Ar_1, Ar_2, Ar_3)) [ Ar_2 >= 10 ] (Comp: 20*Ar_1 + 90, Cost: 1) evalwcet2bb3in(Ar_0, Ar_1, Ar_2, Ar_3) -> Com_1(evalwcet2bb2in(Ar_0, Ar_1, Ar_2 + 1, Ar_3)) (Comp: 14*Ar_1 + 63, Cost: 1) evalwcet2bb4in(Ar_0, Ar_1, Ar_2, Ar_3) -> Com_1(evalwcet27(Ar_0, Ar_1, Ar_2, Ar_0 + 1)) (Comp: 14*Ar_1 + 63, Cost: 1) evalwcet27(Ar_0, Ar_1, Ar_2, Ar_3) -> Com_1(evalwcet28(Ar_0, Ar_1, Ar_2, Ar_3)) (Comp: 14*Ar_1 + 63, Cost: 1) evalwcet28(Ar_0, Ar_1, Ar_2, Ar_3) -> Com_1(evalwcet2bb1in(Ar_3, Ar_1, Ar_2, Ar_3)) (Comp: 2, Cost: 1) evalwcet2bb5in(Ar_0, Ar_1, Ar_2, Ar_3) -> Com_1(evalwcet2stop(Ar_0, Ar_1, Ar_2, Ar_3)) (Comp: 1, Cost: 0) koat_start(Ar_0, Ar_1, Ar_2, Ar_3) -> Com_1(evalwcet2start(Ar_0, Ar_1, Ar_2, Ar_3)) [ 0 <= 0 ] start location: koat_start leaf cost: 0 Complexity upper bound 100*Ar_1 + 460 Time: 0.137 sec (SMT: 0.101 sec) ---------------------------------------- (2) BOUNDS(1, n^1) ---------------------------------------- (3) Loat Proof (FINISHED) ### Pre-processing the ITS problem ### Initial linear ITS problem Start location: evalwcet2start 0: evalwcet2start -> evalwcet2bb0in : [], cost: 1 1: evalwcet2bb0in -> evalwcet20 : [], cost: 1 2: evalwcet20 -> evalwcet21 : [], cost: 1 3: evalwcet21 -> evalwcet22 : [], cost: 1 4: evalwcet22 -> evalwcet23 : [], cost: 1 5: evalwcet23 -> evalwcet2bb1in : A'=B, [], cost: 1 6: evalwcet2bb1in -> evalwcet2bb2in : C'=0, [ 4>=A ], cost: 1 7: evalwcet2bb1in -> evalwcet2bb5in : [ A>=5 ], cost: 1 8: evalwcet2bb2in -> evalwcet2bb3in : [ A>=3 && 9>=C ], cost: 1 9: evalwcet2bb2in -> evalwcet2bb4in : [ 2>=A ], cost: 1 10: evalwcet2bb2in -> evalwcet2bb4in : [ C>=10 ], cost: 1 11: evalwcet2bb3in -> evalwcet2bb2in : C'=1+C, [], cost: 1 12: evalwcet2bb4in -> evalwcet27 : D'=1+A, [], cost: 1 13: evalwcet27 -> evalwcet28 : [], cost: 1 14: evalwcet28 -> evalwcet2bb1in : A'=D, [], cost: 1 15: evalwcet2bb5in -> evalwcet2stop : [], cost: 1 Checking for constant complexity: The following rule is satisfiable with cost >= 1, yielding constant complexity: 0: evalwcet2start -> evalwcet2bb0in : [], cost: 1 Removed unreachable and leaf rules: Start location: evalwcet2start 0: evalwcet2start -> evalwcet2bb0in : [], cost: 1 1: evalwcet2bb0in -> evalwcet20 : [], cost: 1 2: evalwcet20 -> evalwcet21 : [], cost: 1 3: evalwcet21 -> evalwcet22 : [], cost: 1 4: evalwcet22 -> evalwcet23 : [], cost: 1 5: evalwcet23 -> evalwcet2bb1in : A'=B, [], cost: 1 6: evalwcet2bb1in -> evalwcet2bb2in : C'=0, [ 4>=A ], cost: 1 8: evalwcet2bb2in -> evalwcet2bb3in : [ A>=3 && 9>=C ], cost: 1 9: evalwcet2bb2in -> evalwcet2bb4in : [ 2>=A ], cost: 1 10: evalwcet2bb2in -> evalwcet2bb4in : [ C>=10 ], cost: 1 11: evalwcet2bb3in -> evalwcet2bb2in : C'=1+C, [], cost: 1 12: evalwcet2bb4in -> evalwcet27 : D'=1+A, [], cost: 1 13: evalwcet27 -> evalwcet28 : [], cost: 1 14: evalwcet28 -> evalwcet2bb1in : A'=D, [], cost: 1 ### Simplification by acceleration and chaining ### Eliminated locations (on linear paths): Start location: evalwcet2start 20: evalwcet2start -> evalwcet2bb1in : A'=B, [], cost: 6 6: evalwcet2bb1in -> evalwcet2bb2in : C'=0, [ 4>=A ], cost: 1 9: evalwcet2bb2in -> evalwcet2bb4in : [ 2>=A ], cost: 1 10: evalwcet2bb2in -> evalwcet2bb4in : [ C>=10 ], cost: 1 21: evalwcet2bb2in -> evalwcet2bb2in : C'=1+C, [ A>=3 && 9>=C ], cost: 2 23: evalwcet2bb4in -> evalwcet2bb1in : A'=1+A, D'=1+A, [], cost: 3 Accelerating simple loops of location 7. Accelerating the following rules: 21: evalwcet2bb2in -> evalwcet2bb2in : C'=1+C, [ A>=3 && 9>=C ], cost: 2 Accelerated rule 21 with metering function 10-C, yielding the new rule 24. Removing the simple loops: 21. Accelerated all simple loops using metering functions (where possible): Start location: evalwcet2start 20: evalwcet2start -> evalwcet2bb1in : A'=B, [], cost: 6 6: evalwcet2bb1in -> evalwcet2bb2in : C'=0, [ 4>=A ], cost: 1 9: evalwcet2bb2in -> evalwcet2bb4in : [ 2>=A ], cost: 1 10: evalwcet2bb2in -> evalwcet2bb4in : [ C>=10 ], cost: 1 24: evalwcet2bb2in -> evalwcet2bb2in : C'=10, [ A>=3 && 9>=C ], cost: 20-2*C 23: evalwcet2bb4in -> evalwcet2bb1in : A'=1+A, D'=1+A, [], cost: 3 Chained accelerated rules (with incoming rules): Start location: evalwcet2start 20: evalwcet2start -> evalwcet2bb1in : A'=B, [], cost: 6 6: evalwcet2bb1in -> evalwcet2bb2in : C'=0, [ 4>=A ], cost: 1 25: evalwcet2bb1in -> evalwcet2bb2in : C'=10, [ 4>=A && A>=3 ], cost: 21 9: evalwcet2bb2in -> evalwcet2bb4in : [ 2>=A ], cost: 1 10: evalwcet2bb2in -> evalwcet2bb4in : [ C>=10 ], cost: 1 23: evalwcet2bb4in -> evalwcet2bb1in : A'=1+A, D'=1+A, [], cost: 3 Eliminated locations (on tree-shaped paths): Start location: evalwcet2start 20: evalwcet2start -> evalwcet2bb1in : A'=B, [], cost: 6 26: evalwcet2bb1in -> evalwcet2bb4in : C'=0, [ 2>=A ], cost: 2 27: evalwcet2bb1in -> evalwcet2bb4in : C'=10, [ 4>=A && A>=3 ], cost: 22 23: evalwcet2bb4in -> evalwcet2bb1in : A'=1+A, D'=1+A, [], cost: 3 Eliminated locations (on tree-shaped paths): Start location: evalwcet2start 20: evalwcet2start -> evalwcet2bb1in : A'=B, [], cost: 6 28: evalwcet2bb1in -> evalwcet2bb1in : A'=1+A, C'=0, D'=1+A, [ 2>=A ], cost: 5 29: evalwcet2bb1in -> evalwcet2bb1in : A'=1+A, C'=10, D'=1+A, [ 4>=A && A>=3 ], cost: 25 Accelerating simple loops of location 6. Accelerating the following rules: 28: evalwcet2bb1in -> evalwcet2bb1in : A'=1+A, C'=0, D'=1+A, [ 2>=A ], cost: 5 29: evalwcet2bb1in -> evalwcet2bb1in : A'=1+A, C'=10, D'=1+A, [ 4>=A && A>=3 ], cost: 25 Accelerated rule 28 with metering function 3-A, yielding the new rule 30. Accelerated rule 29 with metering function 5-A, yielding the new rule 31. Removing the simple loops: 28 29. Accelerated all simple loops using metering functions (where possible): Start location: evalwcet2start 20: evalwcet2start -> evalwcet2bb1in : A'=B, [], cost: 6 30: evalwcet2bb1in -> evalwcet2bb1in : A'=3, C'=0, D'=3, [ 2>=A ], cost: 15-5*A 31: evalwcet2bb1in -> evalwcet2bb1in : A'=5, C'=10, D'=5, [ 4>=A && A>=3 ], cost: 125-25*A Chained accelerated rules (with incoming rules): Start location: evalwcet2start 20: evalwcet2start -> evalwcet2bb1in : A'=B, [], cost: 6 32: evalwcet2start -> evalwcet2bb1in : A'=3, C'=0, D'=3, [ 2>=B ], cost: 21-5*B 33: evalwcet2start -> evalwcet2bb1in : A'=5, C'=10, D'=5, [ 4>=B && B>=3 ], cost: 131-25*B Removed unreachable locations (and leaf rules with constant cost): Start location: evalwcet2start 32: evalwcet2start -> evalwcet2bb1in : A'=3, C'=0, D'=3, [ 2>=B ], cost: 21-5*B 33: evalwcet2start -> evalwcet2bb1in : A'=5, C'=10, D'=5, [ 4>=B && B>=3 ], cost: 131-25*B ### Computing asymptotic complexity ### Fully simplified ITS problem Start location: evalwcet2start 32: evalwcet2start -> evalwcet2bb1in : A'=3, C'=0, D'=3, [ 2>=B ], cost: 21-5*B 33: evalwcet2start -> evalwcet2bb1in : A'=5, C'=10, D'=5, [ 4>=B && B>=3 ], cost: 131-25*B Computing asymptotic complexity for rule 32 Solved the limit problem by the following transformations: Created initial limit problem: 3-B (+/+!), 21-5*B (+) [not solved] removing all constraints (solved by SMT) resulting limit problem: [solved] applying transformation rule (C) using substitution {B==-n} resulting limit problem: [solved] Solution: B / -n Resulting cost 21+5*n has complexity: Poly(n^1) Found new complexity Poly(n^1). Obtained the following overall complexity (w.r.t. the length of the input n): Complexity: Poly(n^1) Cpx degree: 1 Solved cost: 21+5*n Rule cost: 21-5*B Rule guard: [ 2>=B ] WORST_CASE(Omega(n^1),?) ---------------------------------------- (4) BOUNDS(n^1, INF)