/export/starexec/sandbox/solver/bin/starexec_run_complexity /export/starexec/sandbox/benchmark/theBenchmark.koat /export/starexec/sandbox/output/output_files -------------------------------------------------------------------------------- WORST_CASE(Omega(n^1), O(n^1)) proof of /export/starexec/sandbox/benchmark/theBenchmark.koat # AProVE Commit ID: 48fb2092695e11cc9f56e44b17a92a5f88ffb256 marcel 20180622 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, 216 ms] (2) BOUNDS(1, n^1) (3) Loat Proof [FINISHED, 2123 ms] (4) BOUNDS(n^1, INF) ---------------------------------------- (0) Obligation: Complexity Int TRS consisting of the following rules: eval_wcet0_start(v_1, v_i_0, v_j_0, v_j_3, v_n) -> Com_1(eval_wcet0_bb0_in(v_1, v_i_0, v_j_0, v_j_3, v_n)) :|: TRUE eval_wcet0_bb0_in(v_1, v_i_0, v_j_0, v_j_3, v_n) -> Com_1(eval_wcet0_0(v_1, v_i_0, v_j_0, v_j_3, v_n)) :|: TRUE eval_wcet0_0(v_1, v_i_0, v_j_0, v_j_3, v_n) -> Com_1(eval_wcet0_1(v_1, v_i_0, v_j_0, v_j_3, v_n)) :|: TRUE eval_wcet0_1(v_1, v_i_0, v_j_0, v_j_3, v_n) -> Com_1(eval_wcet0_2(v_1, v_i_0, v_j_0, v_j_3, v_n)) :|: TRUE eval_wcet0_2(v_1, v_i_0, v_j_0, v_j_3, v_n) -> Com_1(eval_wcet0_3(v_1, v_i_0, v_j_0, v_j_3, v_n)) :|: TRUE eval_wcet0_3(v_1, v_i_0, v_j_0, v_j_3, v_n) -> Com_1(eval_wcet0_bb1_in(v_1, v_n, 0, v_j_3, v_n)) :|: v_n >= 1 eval_wcet0_3(v_1, v_i_0, v_j_0, v_j_3, v_n) -> Com_1(eval_wcet0_bb5_in(v_1, v_i_0, v_j_0, v_j_3, v_n)) :|: v_n < 1 eval_wcet0_bb1_in(v_1, v_i_0, v_j_0, v_j_3, v_n) -> Com_1(eval_wcet0_4(v_1, v_i_0, v_j_0, v_j_3, v_n)) :|: TRUE eval_wcet0_4(v_1, v_i_0, v_j_0, v_j_3, v_n) -> Com_1(eval_wcet0_5(nondef_0, v_i_0, v_j_0, v_j_3, v_n)) :|: TRUE eval_wcet0_5(v_1, v_i_0, v_j_0, v_j_3, v_n) -> Com_1(eval_wcet0_bb2_in(v_1, v_i_0, v_j_0, v_j_3, v_n)) :|: v_1 > 0 eval_wcet0_5(v_1, v_i_0, v_j_0, v_j_3, v_n) -> Com_1(eval_wcet0_bb3_in(v_1, v_i_0, v_j_0, v_j_3, v_n)) :|: v_1 <= 0 eval_wcet0_bb2_in(v_1, v_i_0, v_j_0, v_j_3, v_n) -> Com_1(eval_wcet0_bb4_in(v_1, v_i_0, v_j_0, 0, v_n)) :|: v_j_0 + 1 >= v_n eval_wcet0_bb2_in(v_1, v_i_0, v_j_0, v_j_3, v_n) -> Com_1(eval_wcet0_bb4_in(v_1, v_i_0, v_j_0, v_j_0 + 1, v_n)) :|: v_j_0 + 1 < v_n eval_wcet0_bb3_in(v_1, v_i_0, v_j_0, v_j_3, v_n) -> Com_1(eval_wcet0_bb4_in(v_1, v_i_0, v_j_0, 0, v_n)) :|: v_j_0 - 1 <= -(v_n) eval_wcet0_bb3_in(v_1, v_i_0, v_j_0, v_j_3, v_n) -> Com_1(eval_wcet0_bb4_in(v_1, v_i_0, v_j_0, v_j_0 - 1, v_n)) :|: v_j_0 - 1 > -(v_n) eval_wcet0_bb4_in(v_1, v_i_0, v_j_0, v_j_3, v_n) -> Com_1(eval_wcet0_bb1_in(v_1, v_i_0 - 1, v_j_3, v_j_3, v_n)) :|: v_i_0 - 1 > 0 eval_wcet0_bb4_in(v_1, v_i_0, v_j_0, v_j_3, v_n) -> Com_1(eval_wcet0_bb5_in(v_1, v_i_0, v_j_0, v_j_3, v_n)) :|: v_i_0 - 1 <= 0 eval_wcet0_bb5_in(v_1, v_i_0, v_j_0, v_j_3, v_n) -> Com_1(eval_wcet0_stop(v_1, v_i_0, v_j_0, v_j_3, v_n)) :|: TRUE The start-symbols are:[eval_wcet0_start_5] ---------------------------------------- (1) Koat Proof (FINISHED) YES(?, 9*ar_0 + 19) Initial complexity problem: 1: T: (Comp: ?, Cost: 1) evalwcet0start(ar_0, ar_1, ar_2, ar_3, ar_4) -> Com_1(evalwcet0bb0in(ar_0, ar_1, ar_2, ar_3, ar_4)) (Comp: ?, Cost: 1) evalwcet0bb0in(ar_0, ar_1, ar_2, ar_3, ar_4) -> Com_1(evalwcet00(ar_0, ar_1, ar_2, ar_3, ar_4)) (Comp: ?, Cost: 1) evalwcet00(ar_0, ar_1, ar_2, ar_3, ar_4) -> Com_1(evalwcet01(ar_0, ar_1, ar_2, ar_3, ar_4)) (Comp: ?, Cost: 1) evalwcet01(ar_0, ar_1, ar_2, ar_3, ar_4) -> Com_1(evalwcet02(ar_0, ar_1, ar_2, ar_3, ar_4)) (Comp: ?, Cost: 1) evalwcet02(ar_0, ar_1, ar_2, ar_3, ar_4) -> Com_1(evalwcet03(ar_0, ar_1, ar_2, ar_3, ar_4)) (Comp: ?, Cost: 1) evalwcet03(ar_0, ar_1, ar_2, ar_3, ar_4) -> Com_1(evalwcet0bb1in(ar_0, ar_0, 0, ar_3, ar_4)) [ ar_0 >= 1 ] (Comp: ?, Cost: 1) evalwcet03(ar_0, ar_1, ar_2, ar_3, ar_4) -> Com_1(evalwcet0bb5in(ar_0, ar_1, ar_2, ar_3, ar_4)) [ 0 >= ar_0 ] (Comp: ?, Cost: 1) evalwcet0bb1in(ar_0, ar_1, ar_2, ar_3, ar_4) -> Com_1(evalwcet04(ar_0, ar_1, ar_2, ar_3, ar_4)) (Comp: ?, Cost: 1) evalwcet04(ar_0, ar_1, ar_2, ar_3, ar_4) -> Com_1(evalwcet05(ar_0, ar_1, ar_2, f, ar_4)) (Comp: ?, Cost: 1) evalwcet05(ar_0, ar_1, ar_2, ar_3, ar_4) -> Com_1(evalwcet0bb2in(ar_0, ar_1, ar_2, ar_3, ar_4)) [ ar_3 >= 1 ] (Comp: ?, Cost: 1) evalwcet05(ar_0, ar_1, ar_2, ar_3, ar_4) -> Com_1(evalwcet0bb3in(ar_0, ar_1, ar_2, ar_3, ar_4)) [ 0 >= ar_3 ] (Comp: ?, Cost: 1) evalwcet0bb2in(ar_0, ar_1, ar_2, ar_3, ar_4) -> Com_1(evalwcet0bb4in(ar_0, ar_1, ar_2, ar_3, 0)) [ ar_2 + 1 >= ar_0 ] (Comp: ?, Cost: 1) evalwcet0bb2in(ar_0, ar_1, ar_2, ar_3, ar_4) -> Com_1(evalwcet0bb4in(ar_0, ar_1, ar_2, ar_3, ar_2 + 1)) [ ar_0 >= ar_2 + 2 ] (Comp: ?, Cost: 1) evalwcet0bb3in(ar_0, ar_1, ar_2, ar_3, ar_4) -> Com_1(evalwcet0bb4in(ar_0, ar_1, ar_2, ar_3, 0)) [ 1 >= ar_0 + ar_2 ] (Comp: ?, Cost: 1) evalwcet0bb3in(ar_0, ar_1, ar_2, ar_3, ar_4) -> Com_1(evalwcet0bb4in(ar_0, ar_1, ar_2, ar_3, ar_2 - 1)) [ ar_2 + ar_0 >= 2 ] (Comp: ?, Cost: 1) evalwcet0bb4in(ar_0, ar_1, ar_2, ar_3, ar_4) -> Com_1(evalwcet0bb1in(ar_0, ar_1 - 1, ar_4, ar_3, ar_4)) [ ar_1 >= 2 ] (Comp: ?, Cost: 1) evalwcet0bb4in(ar_0, ar_1, ar_2, ar_3, ar_4) -> Com_1(evalwcet0bb5in(ar_0, ar_1, ar_2, ar_3, ar_4)) [ 1 >= ar_1 ] (Comp: ?, Cost: 1) evalwcet0bb5in(ar_0, ar_1, ar_2, ar_3, ar_4) -> Com_1(evalwcet0stop(ar_0, ar_1, ar_2, ar_3, ar_4)) (Comp: 1, Cost: 0) koat_start(ar_0, ar_1, ar_2, ar_3, ar_4) -> Com_1(evalwcet0start(ar_0, ar_1, ar_2, ar_3, ar_4)) [ 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) evalwcet0start(ar_0, ar_1, ar_2, ar_3, ar_4) -> Com_1(evalwcet0bb0in(ar_0, ar_1, ar_2, ar_3, ar_4)) (Comp: 1, Cost: 1) evalwcet0bb0in(ar_0, ar_1, ar_2, ar_3, ar_4) -> Com_1(evalwcet00(ar_0, ar_1, ar_2, ar_3, ar_4)) (Comp: 1, Cost: 1) evalwcet00(ar_0, ar_1, ar_2, ar_3, ar_4) -> Com_1(evalwcet01(ar_0, ar_1, ar_2, ar_3, ar_4)) (Comp: 1, Cost: 1) evalwcet01(ar_0, ar_1, ar_2, ar_3, ar_4) -> Com_1(evalwcet02(ar_0, ar_1, ar_2, ar_3, ar_4)) (Comp: 1, Cost: 1) evalwcet02(ar_0, ar_1, ar_2, ar_3, ar_4) -> Com_1(evalwcet03(ar_0, ar_1, ar_2, ar_3, ar_4)) (Comp: 1, Cost: 1) evalwcet03(ar_0, ar_1, ar_2, ar_3, ar_4) -> Com_1(evalwcet0bb1in(ar_0, ar_0, 0, ar_3, ar_4)) [ ar_0 >= 1 ] (Comp: 1, Cost: 1) evalwcet03(ar_0, ar_1, ar_2, ar_3, ar_4) -> Com_1(evalwcet0bb5in(ar_0, ar_1, ar_2, ar_3, ar_4)) [ 0 >= ar_0 ] (Comp: ?, Cost: 1) evalwcet0bb1in(ar_0, ar_1, ar_2, ar_3, ar_4) -> Com_1(evalwcet04(ar_0, ar_1, ar_2, ar_3, ar_4)) (Comp: ?, Cost: 1) evalwcet04(ar_0, ar_1, ar_2, ar_3, ar_4) -> Com_1(evalwcet05(ar_0, ar_1, ar_2, f, ar_4)) (Comp: ?, Cost: 1) evalwcet05(ar_0, ar_1, ar_2, ar_3, ar_4) -> Com_1(evalwcet0bb2in(ar_0, ar_1, ar_2, ar_3, ar_4)) [ ar_3 >= 1 ] (Comp: ?, Cost: 1) evalwcet05(ar_0, ar_1, ar_2, ar_3, ar_4) -> Com_1(evalwcet0bb3in(ar_0, ar_1, ar_2, ar_3, ar_4)) [ 0 >= ar_3 ] (Comp: ?, Cost: 1) evalwcet0bb2in(ar_0, ar_1, ar_2, ar_3, ar_4) -> Com_1(evalwcet0bb4in(ar_0, ar_1, ar_2, ar_3, 0)) [ ar_2 + 1 >= ar_0 ] (Comp: ?, Cost: 1) evalwcet0bb2in(ar_0, ar_1, ar_2, ar_3, ar_4) -> Com_1(evalwcet0bb4in(ar_0, ar_1, ar_2, ar_3, ar_2 + 1)) [ ar_0 >= ar_2 + 2 ] (Comp: ?, Cost: 1) evalwcet0bb3in(ar_0, ar_1, ar_2, ar_3, ar_4) -> Com_1(evalwcet0bb4in(ar_0, ar_1, ar_2, ar_3, 0)) [ 1 >= ar_0 + ar_2 ] (Comp: ?, Cost: 1) evalwcet0bb3in(ar_0, ar_1, ar_2, ar_3, ar_4) -> Com_1(evalwcet0bb4in(ar_0, ar_1, ar_2, ar_3, ar_2 - 1)) [ ar_2 + ar_0 >= 2 ] (Comp: ?, Cost: 1) evalwcet0bb4in(ar_0, ar_1, ar_2, ar_3, ar_4) -> Com_1(evalwcet0bb1in(ar_0, ar_1 - 1, ar_4, ar_3, ar_4)) [ ar_1 >= 2 ] (Comp: ?, Cost: 1) evalwcet0bb4in(ar_0, ar_1, ar_2, ar_3, ar_4) -> Com_1(evalwcet0bb5in(ar_0, ar_1, ar_2, ar_3, ar_4)) [ 1 >= ar_1 ] (Comp: ?, Cost: 1) evalwcet0bb5in(ar_0, ar_1, ar_2, ar_3, ar_4) -> Com_1(evalwcet0stop(ar_0, ar_1, ar_2, ar_3, ar_4)) (Comp: 1, Cost: 0) koat_start(ar_0, ar_1, ar_2, ar_3, ar_4) -> Com_1(evalwcet0start(ar_0, ar_1, ar_2, ar_3, ar_4)) [ 0 <= 0 ] start location: koat_start leaf cost: 0 A polynomial rank function with Pol(evalwcet0start) = 2 Pol(evalwcet0bb0in) = 2 Pol(evalwcet00) = 2 Pol(evalwcet01) = 2 Pol(evalwcet02) = 2 Pol(evalwcet03) = 2 Pol(evalwcet0bb1in) = 2 Pol(evalwcet0bb5in) = 1 Pol(evalwcet04) = 2 Pol(evalwcet05) = 2 Pol(evalwcet0bb2in) = 2 Pol(evalwcet0bb3in) = 2 Pol(evalwcet0bb4in) = 2 Pol(evalwcet0stop) = 0 Pol(koat_start) = 2 orients all transitions weakly and the transitions evalwcet0bb5in(ar_0, ar_1, ar_2, ar_3, ar_4) -> Com_1(evalwcet0stop(ar_0, ar_1, ar_2, ar_3, ar_4)) evalwcet0bb4in(ar_0, ar_1, ar_2, ar_3, ar_4) -> Com_1(evalwcet0bb5in(ar_0, ar_1, ar_2, ar_3, ar_4)) [ 1 >= ar_1 ] strictly and produces the following problem: 3: T: (Comp: 1, Cost: 1) evalwcet0start(ar_0, ar_1, ar_2, ar_3, ar_4) -> Com_1(evalwcet0bb0in(ar_0, ar_1, ar_2, ar_3, ar_4)) (Comp: 1, Cost: 1) evalwcet0bb0in(ar_0, ar_1, ar_2, ar_3, ar_4) -> Com_1(evalwcet00(ar_0, ar_1, ar_2, ar_3, ar_4)) (Comp: 1, Cost: 1) evalwcet00(ar_0, ar_1, ar_2, ar_3, ar_4) -> Com_1(evalwcet01(ar_0, ar_1, ar_2, ar_3, ar_4)) (Comp: 1, Cost: 1) evalwcet01(ar_0, ar_1, ar_2, ar_3, ar_4) -> Com_1(evalwcet02(ar_0, ar_1, ar_2, ar_3, ar_4)) (Comp: 1, Cost: 1) evalwcet02(ar_0, ar_1, ar_2, ar_3, ar_4) -> Com_1(evalwcet03(ar_0, ar_1, ar_2, ar_3, ar_4)) (Comp: 1, Cost: 1) evalwcet03(ar_0, ar_1, ar_2, ar_3, ar_4) -> Com_1(evalwcet0bb1in(ar_0, ar_0, 0, ar_3, ar_4)) [ ar_0 >= 1 ] (Comp: 1, Cost: 1) evalwcet03(ar_0, ar_1, ar_2, ar_3, ar_4) -> Com_1(evalwcet0bb5in(ar_0, ar_1, ar_2, ar_3, ar_4)) [ 0 >= ar_0 ] (Comp: ?, Cost: 1) evalwcet0bb1in(ar_0, ar_1, ar_2, ar_3, ar_4) -> Com_1(evalwcet04(ar_0, ar_1, ar_2, ar_3, ar_4)) (Comp: ?, Cost: 1) evalwcet04(ar_0, ar_1, ar_2, ar_3, ar_4) -> Com_1(evalwcet05(ar_0, ar_1, ar_2, f, ar_4)) (Comp: ?, Cost: 1) evalwcet05(ar_0, ar_1, ar_2, ar_3, ar_4) -> Com_1(evalwcet0bb2in(ar_0, ar_1, ar_2, ar_3, ar_4)) [ ar_3 >= 1 ] (Comp: ?, Cost: 1) evalwcet05(ar_0, ar_1, ar_2, ar_3, ar_4) -> Com_1(evalwcet0bb3in(ar_0, ar_1, ar_2, ar_3, ar_4)) [ 0 >= ar_3 ] (Comp: ?, Cost: 1) evalwcet0bb2in(ar_0, ar_1, ar_2, ar_3, ar_4) -> Com_1(evalwcet0bb4in(ar_0, ar_1, ar_2, ar_3, 0)) [ ar_2 + 1 >= ar_0 ] (Comp: ?, Cost: 1) evalwcet0bb2in(ar_0, ar_1, ar_2, ar_3, ar_4) -> Com_1(evalwcet0bb4in(ar_0, ar_1, ar_2, ar_3, ar_2 + 1)) [ ar_0 >= ar_2 + 2 ] (Comp: ?, Cost: 1) evalwcet0bb3in(ar_0, ar_1, ar_2, ar_3, ar_4) -> Com_1(evalwcet0bb4in(ar_0, ar_1, ar_2, ar_3, 0)) [ 1 >= ar_0 + ar_2 ] (Comp: ?, Cost: 1) evalwcet0bb3in(ar_0, ar_1, ar_2, ar_3, ar_4) -> Com_1(evalwcet0bb4in(ar_0, ar_1, ar_2, ar_3, ar_2 - 1)) [ ar_2 + ar_0 >= 2 ] (Comp: ?, Cost: 1) evalwcet0bb4in(ar_0, ar_1, ar_2, ar_3, ar_4) -> Com_1(evalwcet0bb1in(ar_0, ar_1 - 1, ar_4, ar_3, ar_4)) [ ar_1 >= 2 ] (Comp: 2, Cost: 1) evalwcet0bb4in(ar_0, ar_1, ar_2, ar_3, ar_4) -> Com_1(evalwcet0bb5in(ar_0, ar_1, ar_2, ar_3, ar_4)) [ 1 >= ar_1 ] (Comp: 2, Cost: 1) evalwcet0bb5in(ar_0, ar_1, ar_2, ar_3, ar_4) -> Com_1(evalwcet0stop(ar_0, ar_1, ar_2, ar_3, ar_4)) (Comp: 1, Cost: 0) koat_start(ar_0, ar_1, ar_2, ar_3, ar_4) -> Com_1(evalwcet0start(ar_0, ar_1, ar_2, ar_3, ar_4)) [ 0 <= 0 ] start location: koat_start leaf cost: 0 A polynomial rank function with Pol(evalwcet0bb4in) = V_2 Pol(evalwcet0bb1in) = V_2 Pol(evalwcet0bb3in) = V_2 Pol(evalwcet0bb2in) = V_2 Pol(evalwcet04) = V_2 Pol(evalwcet05) = V_2 and size complexities S("koat_start(ar_0, ar_1, ar_2, ar_3, ar_4) -> Com_1(evalwcet0start(ar_0, ar_1, ar_2, ar_3, ar_4)) [ 0 <= 0 ]", 0-0) = ar_0 S("koat_start(ar_0, ar_1, ar_2, ar_3, ar_4) -> Com_1(evalwcet0start(ar_0, ar_1, ar_2, ar_3, ar_4)) [ 0 <= 0 ]", 0-1) = ar_1 S("koat_start(ar_0, ar_1, ar_2, ar_3, ar_4) -> Com_1(evalwcet0start(ar_0, ar_1, ar_2, ar_3, ar_4)) [ 0 <= 0 ]", 0-2) = ar_2 S("koat_start(ar_0, ar_1, ar_2, ar_3, ar_4) -> Com_1(evalwcet0start(ar_0, ar_1, ar_2, ar_3, ar_4)) [ 0 <= 0 ]", 0-3) = ar_3 S("koat_start(ar_0, ar_1, ar_2, ar_3, ar_4) -> Com_1(evalwcet0start(ar_0, ar_1, ar_2, ar_3, ar_4)) [ 0 <= 0 ]", 0-4) = ar_4 S("evalwcet0bb5in(ar_0, ar_1, ar_2, ar_3, ar_4) -> Com_1(evalwcet0stop(ar_0, ar_1, ar_2, ar_3, ar_4))", 0-0) = ar_0 S("evalwcet0bb5in(ar_0, ar_1, ar_2, ar_3, ar_4) -> Com_1(evalwcet0stop(ar_0, ar_1, ar_2, ar_3, ar_4))", 0-1) = ar_0 + ar_1 S("evalwcet0bb5in(ar_0, ar_1, ar_2, ar_3, ar_4) -> Com_1(evalwcet0stop(ar_0, ar_1, ar_2, ar_3, ar_4))", 0-2) = ? S("evalwcet0bb5in(ar_0, ar_1, ar_2, ar_3, ar_4) -> Com_1(evalwcet0stop(ar_0, ar_1, ar_2, ar_3, ar_4))", 0-3) = ? S("evalwcet0bb5in(ar_0, ar_1, ar_2, ar_3, ar_4) -> Com_1(evalwcet0stop(ar_0, ar_1, ar_2, ar_3, ar_4))", 0-4) = ? S("evalwcet0bb4in(ar_0, ar_1, ar_2, ar_3, ar_4) -> Com_1(evalwcet0bb5in(ar_0, ar_1, ar_2, ar_3, ar_4)) [ 1 >= ar_1 ]", 0-0) = ar_0 S("evalwcet0bb4in(ar_0, ar_1, ar_2, ar_3, ar_4) -> Com_1(evalwcet0bb5in(ar_0, ar_1, ar_2, ar_3, ar_4)) [ 1 >= ar_1 ]", 0-1) = ar_0 S("evalwcet0bb4in(ar_0, ar_1, ar_2, ar_3, ar_4) -> Com_1(evalwcet0bb5in(ar_0, ar_1, ar_2, ar_3, ar_4)) [ 1 >= ar_1 ]", 0-2) = ? S("evalwcet0bb4in(ar_0, ar_1, ar_2, ar_3, ar_4) -> Com_1(evalwcet0bb5in(ar_0, ar_1, ar_2, ar_3, ar_4)) [ 1 >= ar_1 ]", 0-3) = ? S("evalwcet0bb4in(ar_0, ar_1, ar_2, ar_3, ar_4) -> Com_1(evalwcet0bb5in(ar_0, ar_1, ar_2, ar_3, ar_4)) [ 1 >= ar_1 ]", 0-4) = ? S("evalwcet0bb4in(ar_0, ar_1, ar_2, ar_3, ar_4) -> Com_1(evalwcet0bb1in(ar_0, ar_1 - 1, ar_4, ar_3, ar_4)) [ ar_1 >= 2 ]", 0-0) = ar_0 S("evalwcet0bb4in(ar_0, ar_1, ar_2, ar_3, ar_4) -> Com_1(evalwcet0bb1in(ar_0, ar_1 - 1, ar_4, ar_3, ar_4)) [ ar_1 >= 2 ]", 0-1) = ar_0 S("evalwcet0bb4in(ar_0, ar_1, ar_2, ar_3, ar_4) -> Com_1(evalwcet0bb1in(ar_0, ar_1 - 1, ar_4, ar_3, ar_4)) [ ar_1 >= 2 ]", 0-2) = ? S("evalwcet0bb4in(ar_0, ar_1, ar_2, ar_3, ar_4) -> Com_1(evalwcet0bb1in(ar_0, ar_1 - 1, ar_4, ar_3, ar_4)) [ ar_1 >= 2 ]", 0-3) = ? S("evalwcet0bb4in(ar_0, ar_1, ar_2, ar_3, ar_4) -> Com_1(evalwcet0bb1in(ar_0, ar_1 - 1, ar_4, ar_3, ar_4)) [ ar_1 >= 2 ]", 0-4) = ? S("evalwcet0bb3in(ar_0, ar_1, ar_2, ar_3, ar_4) -> Com_1(evalwcet0bb4in(ar_0, ar_1, ar_2, ar_3, ar_2 - 1)) [ ar_2 + ar_0 >= 2 ]", 0-0) = ar_0 S("evalwcet0bb3in(ar_0, ar_1, ar_2, ar_3, ar_4) -> Com_1(evalwcet0bb4in(ar_0, ar_1, ar_2, ar_3, ar_2 - 1)) [ ar_2 + ar_0 >= 2 ]", 0-1) = ar_0 S("evalwcet0bb3in(ar_0, ar_1, ar_2, ar_3, ar_4) -> Com_1(evalwcet0bb4in(ar_0, ar_1, ar_2, ar_3, ar_2 - 1)) [ ar_2 + ar_0 >= 2 ]", 0-2) = ? S("evalwcet0bb3in(ar_0, ar_1, ar_2, ar_3, ar_4) -> Com_1(evalwcet0bb4in(ar_0, ar_1, ar_2, ar_3, ar_2 - 1)) [ ar_2 + ar_0 >= 2 ]", 0-3) = ? S("evalwcet0bb3in(ar_0, ar_1, ar_2, ar_3, ar_4) -> Com_1(evalwcet0bb4in(ar_0, ar_1, ar_2, ar_3, ar_2 - 1)) [ ar_2 + ar_0 >= 2 ]", 0-4) = ? S("evalwcet0bb3in(ar_0, ar_1, ar_2, ar_3, ar_4) -> Com_1(evalwcet0bb4in(ar_0, ar_1, ar_2, ar_3, 0)) [ 1 >= ar_0 + ar_2 ]", 0-0) = ar_0 S("evalwcet0bb3in(ar_0, ar_1, ar_2, ar_3, ar_4) -> Com_1(evalwcet0bb4in(ar_0, ar_1, ar_2, ar_3, 0)) [ 1 >= ar_0 + ar_2 ]", 0-1) = ar_0 S("evalwcet0bb3in(ar_0, ar_1, ar_2, ar_3, ar_4) -> Com_1(evalwcet0bb4in(ar_0, ar_1, ar_2, ar_3, 0)) [ 1 >= ar_0 + ar_2 ]", 0-2) = ? S("evalwcet0bb3in(ar_0, ar_1, ar_2, ar_3, ar_4) -> Com_1(evalwcet0bb4in(ar_0, ar_1, ar_2, ar_3, 0)) [ 1 >= ar_0 + ar_2 ]", 0-3) = ? S("evalwcet0bb3in(ar_0, ar_1, ar_2, ar_3, ar_4) -> Com_1(evalwcet0bb4in(ar_0, ar_1, ar_2, ar_3, 0)) [ 1 >= ar_0 + ar_2 ]", 0-4) = 0 S("evalwcet0bb2in(ar_0, ar_1, ar_2, ar_3, ar_4) -> Com_1(evalwcet0bb4in(ar_0, ar_1, ar_2, ar_3, ar_2 + 1)) [ ar_0 >= ar_2 + 2 ]", 0-0) = ar_0 S("evalwcet0bb2in(ar_0, ar_1, ar_2, ar_3, ar_4) -> Com_1(evalwcet0bb4in(ar_0, ar_1, ar_2, ar_3, ar_2 + 1)) [ ar_0 >= ar_2 + 2 ]", 0-1) = ar_0 S("evalwcet0bb2in(ar_0, ar_1, ar_2, ar_3, ar_4) -> Com_1(evalwcet0bb4in(ar_0, ar_1, ar_2, ar_3, ar_2 + 1)) [ ar_0 >= ar_2 + 2 ]", 0-2) = ? S("evalwcet0bb2in(ar_0, ar_1, ar_2, ar_3, ar_4) -> Com_1(evalwcet0bb4in(ar_0, ar_1, ar_2, ar_3, ar_2 + 1)) [ ar_0 >= ar_2 + 2 ]", 0-3) = ? S("evalwcet0bb2in(ar_0, ar_1, ar_2, ar_3, ar_4) -> Com_1(evalwcet0bb4in(ar_0, ar_1, ar_2, ar_3, ar_2 + 1)) [ ar_0 >= ar_2 + 2 ]", 0-4) = ? S("evalwcet0bb2in(ar_0, ar_1, ar_2, ar_3, ar_4) -> Com_1(evalwcet0bb4in(ar_0, ar_1, ar_2, ar_3, 0)) [ ar_2 + 1 >= ar_0 ]", 0-0) = ar_0 S("evalwcet0bb2in(ar_0, ar_1, ar_2, ar_3, ar_4) -> Com_1(evalwcet0bb4in(ar_0, ar_1, ar_2, ar_3, 0)) [ ar_2 + 1 >= ar_0 ]", 0-1) = ar_0 S("evalwcet0bb2in(ar_0, ar_1, ar_2, ar_3, ar_4) -> Com_1(evalwcet0bb4in(ar_0, ar_1, ar_2, ar_3, 0)) [ ar_2 + 1 >= ar_0 ]", 0-2) = ? S("evalwcet0bb2in(ar_0, ar_1, ar_2, ar_3, ar_4) -> Com_1(evalwcet0bb4in(ar_0, ar_1, ar_2, ar_3, 0)) [ ar_2 + 1 >= ar_0 ]", 0-3) = ? S("evalwcet0bb2in(ar_0, ar_1, ar_2, ar_3, ar_4) -> Com_1(evalwcet0bb4in(ar_0, ar_1, ar_2, ar_3, 0)) [ ar_2 + 1 >= ar_0 ]", 0-4) = 0 S("evalwcet05(ar_0, ar_1, ar_2, ar_3, ar_4) -> Com_1(evalwcet0bb3in(ar_0, ar_1, ar_2, ar_3, ar_4)) [ 0 >= ar_3 ]", 0-0) = ar_0 S("evalwcet05(ar_0, ar_1, ar_2, ar_3, ar_4) -> Com_1(evalwcet0bb3in(ar_0, ar_1, ar_2, ar_3, ar_4)) [ 0 >= ar_3 ]", 0-1) = ar_0 S("evalwcet05(ar_0, ar_1, ar_2, ar_3, ar_4) -> Com_1(evalwcet0bb3in(ar_0, ar_1, ar_2, ar_3, ar_4)) [ 0 >= ar_3 ]", 0-2) = ? S("evalwcet05(ar_0, ar_1, ar_2, ar_3, ar_4) -> Com_1(evalwcet0bb3in(ar_0, ar_1, ar_2, ar_3, ar_4)) [ 0 >= ar_3 ]", 0-3) = ? S("evalwcet05(ar_0, ar_1, ar_2, ar_3, ar_4) -> Com_1(evalwcet0bb3in(ar_0, ar_1, ar_2, ar_3, ar_4)) [ 0 >= ar_3 ]", 0-4) = ? S("evalwcet05(ar_0, ar_1, ar_2, ar_3, ar_4) -> Com_1(evalwcet0bb2in(ar_0, ar_1, ar_2, ar_3, ar_4)) [ ar_3 >= 1 ]", 0-0) = ar_0 S("evalwcet05(ar_0, ar_1, ar_2, ar_3, ar_4) -> Com_1(evalwcet0bb2in(ar_0, ar_1, ar_2, ar_3, ar_4)) [ ar_3 >= 1 ]", 0-1) = ar_0 S("evalwcet05(ar_0, ar_1, ar_2, ar_3, ar_4) -> Com_1(evalwcet0bb2in(ar_0, ar_1, ar_2, ar_3, ar_4)) [ ar_3 >= 1 ]", 0-2) = ? S("evalwcet05(ar_0, ar_1, ar_2, ar_3, ar_4) -> Com_1(evalwcet0bb2in(ar_0, ar_1, ar_2, ar_3, ar_4)) [ ar_3 >= 1 ]", 0-3) = ? S("evalwcet05(ar_0, ar_1, ar_2, ar_3, ar_4) -> Com_1(evalwcet0bb2in(ar_0, ar_1, ar_2, ar_3, ar_4)) [ ar_3 >= 1 ]", 0-4) = ? S("evalwcet04(ar_0, ar_1, ar_2, ar_3, ar_4) -> Com_1(evalwcet05(ar_0, ar_1, ar_2, f, ar_4))", 0-0) = ar_0 S("evalwcet04(ar_0, ar_1, ar_2, ar_3, ar_4) -> Com_1(evalwcet05(ar_0, ar_1, ar_2, f, ar_4))", 0-1) = ar_0 S("evalwcet04(ar_0, ar_1, ar_2, ar_3, ar_4) -> Com_1(evalwcet05(ar_0, ar_1, ar_2, f, ar_4))", 0-2) = ? S("evalwcet04(ar_0, ar_1, ar_2, ar_3, ar_4) -> Com_1(evalwcet05(ar_0, ar_1, ar_2, f, ar_4))", 0-3) = ? S("evalwcet04(ar_0, ar_1, ar_2, ar_3, ar_4) -> Com_1(evalwcet05(ar_0, ar_1, ar_2, f, ar_4))", 0-4) = ? S("evalwcet0bb1in(ar_0, ar_1, ar_2, ar_3, ar_4) -> Com_1(evalwcet04(ar_0, ar_1, ar_2, ar_3, ar_4))", 0-0) = ar_0 S("evalwcet0bb1in(ar_0, ar_1, ar_2, ar_3, ar_4) -> Com_1(evalwcet04(ar_0, ar_1, ar_2, ar_3, ar_4))", 0-1) = ar_0 S("evalwcet0bb1in(ar_0, ar_1, ar_2, ar_3, ar_4) -> Com_1(evalwcet04(ar_0, ar_1, ar_2, ar_3, ar_4))", 0-2) = ? S("evalwcet0bb1in(ar_0, ar_1, ar_2, ar_3, ar_4) -> Com_1(evalwcet04(ar_0, ar_1, ar_2, ar_3, ar_4))", 0-3) = ? S("evalwcet0bb1in(ar_0, ar_1, ar_2, ar_3, ar_4) -> Com_1(evalwcet04(ar_0, ar_1, ar_2, ar_3, ar_4))", 0-4) = ? S("evalwcet03(ar_0, ar_1, ar_2, ar_3, ar_4) -> Com_1(evalwcet0bb5in(ar_0, ar_1, ar_2, ar_3, ar_4)) [ 0 >= ar_0 ]", 0-0) = ar_0 S("evalwcet03(ar_0, ar_1, ar_2, ar_3, ar_4) -> Com_1(evalwcet0bb5in(ar_0, ar_1, ar_2, ar_3, ar_4)) [ 0 >= ar_0 ]", 0-1) = ar_1 S("evalwcet03(ar_0, ar_1, ar_2, ar_3, ar_4) -> Com_1(evalwcet0bb5in(ar_0, ar_1, ar_2, ar_3, ar_4)) [ 0 >= ar_0 ]", 0-2) = ar_2 S("evalwcet03(ar_0, ar_1, ar_2, ar_3, ar_4) -> Com_1(evalwcet0bb5in(ar_0, ar_1, ar_2, ar_3, ar_4)) [ 0 >= ar_0 ]", 0-3) = ar_3 S("evalwcet03(ar_0, ar_1, ar_2, ar_3, ar_4) -> Com_1(evalwcet0bb5in(ar_0, ar_1, ar_2, ar_3, ar_4)) [ 0 >= ar_0 ]", 0-4) = ar_4 S("evalwcet03(ar_0, ar_1, ar_2, ar_3, ar_4) -> Com_1(evalwcet0bb1in(ar_0, ar_0, 0, ar_3, ar_4)) [ ar_0 >= 1 ]", 0-0) = ar_0 S("evalwcet03(ar_0, ar_1, ar_2, ar_3, ar_4) -> Com_1(evalwcet0bb1in(ar_0, ar_0, 0, ar_3, ar_4)) [ ar_0 >= 1 ]", 0-1) = ar_0 S("evalwcet03(ar_0, ar_1, ar_2, ar_3, ar_4) -> Com_1(evalwcet0bb1in(ar_0, ar_0, 0, ar_3, ar_4)) [ ar_0 >= 1 ]", 0-2) = 0 S("evalwcet03(ar_0, ar_1, ar_2, ar_3, ar_4) -> Com_1(evalwcet0bb1in(ar_0, ar_0, 0, ar_3, ar_4)) [ ar_0 >= 1 ]", 0-3) = ar_3 S("evalwcet03(ar_0, ar_1, ar_2, ar_3, ar_4) -> Com_1(evalwcet0bb1in(ar_0, ar_0, 0, ar_3, ar_4)) [ ar_0 >= 1 ]", 0-4) = ar_4 S("evalwcet02(ar_0, ar_1, ar_2, ar_3, ar_4) -> Com_1(evalwcet03(ar_0, ar_1, ar_2, ar_3, ar_4))", 0-0) = ar_0 S("evalwcet02(ar_0, ar_1, ar_2, ar_3, ar_4) -> Com_1(evalwcet03(ar_0, ar_1, ar_2, ar_3, ar_4))", 0-1) = ar_1 S("evalwcet02(ar_0, ar_1, ar_2, ar_3, ar_4) -> Com_1(evalwcet03(ar_0, ar_1, ar_2, ar_3, ar_4))", 0-2) = ar_2 S("evalwcet02(ar_0, ar_1, ar_2, ar_3, ar_4) -> Com_1(evalwcet03(ar_0, ar_1, ar_2, ar_3, ar_4))", 0-3) = ar_3 S("evalwcet02(ar_0, ar_1, ar_2, ar_3, ar_4) -> Com_1(evalwcet03(ar_0, ar_1, ar_2, ar_3, ar_4))", 0-4) = ar_4 S("evalwcet01(ar_0, ar_1, ar_2, ar_3, ar_4) -> Com_1(evalwcet02(ar_0, ar_1, ar_2, ar_3, ar_4))", 0-0) = ar_0 S("evalwcet01(ar_0, ar_1, ar_2, ar_3, ar_4) -> Com_1(evalwcet02(ar_0, ar_1, ar_2, ar_3, ar_4))", 0-1) = ar_1 S("evalwcet01(ar_0, ar_1, ar_2, ar_3, ar_4) -> Com_1(evalwcet02(ar_0, ar_1, ar_2, ar_3, ar_4))", 0-2) = ar_2 S("evalwcet01(ar_0, ar_1, ar_2, ar_3, ar_4) -> Com_1(evalwcet02(ar_0, ar_1, ar_2, ar_3, ar_4))", 0-3) = ar_3 S("evalwcet01(ar_0, ar_1, ar_2, ar_3, ar_4) -> Com_1(evalwcet02(ar_0, ar_1, ar_2, ar_3, ar_4))", 0-4) = ar_4 S("evalwcet00(ar_0, ar_1, ar_2, ar_3, ar_4) -> Com_1(evalwcet01(ar_0, ar_1, ar_2, ar_3, ar_4))", 0-0) = ar_0 S("evalwcet00(ar_0, ar_1, ar_2, ar_3, ar_4) -> Com_1(evalwcet01(ar_0, ar_1, ar_2, ar_3, ar_4))", 0-1) = ar_1 S("evalwcet00(ar_0, ar_1, ar_2, ar_3, ar_4) -> Com_1(evalwcet01(ar_0, ar_1, ar_2, ar_3, ar_4))", 0-2) = ar_2 S("evalwcet00(ar_0, ar_1, ar_2, ar_3, ar_4) -> Com_1(evalwcet01(ar_0, ar_1, ar_2, ar_3, ar_4))", 0-3) = ar_3 S("evalwcet00(ar_0, ar_1, ar_2, ar_3, ar_4) -> Com_1(evalwcet01(ar_0, ar_1, ar_2, ar_3, ar_4))", 0-4) = ar_4 S("evalwcet0bb0in(ar_0, ar_1, ar_2, ar_3, ar_4) -> Com_1(evalwcet00(ar_0, ar_1, ar_2, ar_3, ar_4))", 0-0) = ar_0 S("evalwcet0bb0in(ar_0, ar_1, ar_2, ar_3, ar_4) -> Com_1(evalwcet00(ar_0, ar_1, ar_2, ar_3, ar_4))", 0-1) = ar_1 S("evalwcet0bb0in(ar_0, ar_1, ar_2, ar_3, ar_4) -> Com_1(evalwcet00(ar_0, ar_1, ar_2, ar_3, ar_4))", 0-2) = ar_2 S("evalwcet0bb0in(ar_0, ar_1, ar_2, ar_3, ar_4) -> Com_1(evalwcet00(ar_0, ar_1, ar_2, ar_3, ar_4))", 0-3) = ar_3 S("evalwcet0bb0in(ar_0, ar_1, ar_2, ar_3, ar_4) -> Com_1(evalwcet00(ar_0, ar_1, ar_2, ar_3, ar_4))", 0-4) = ar_4 S("evalwcet0start(ar_0, ar_1, ar_2, ar_3, ar_4) -> Com_1(evalwcet0bb0in(ar_0, ar_1, ar_2, ar_3, ar_4))", 0-0) = ar_0 S("evalwcet0start(ar_0, ar_1, ar_2, ar_3, ar_4) -> Com_1(evalwcet0bb0in(ar_0, ar_1, ar_2, ar_3, ar_4))", 0-1) = ar_1 S("evalwcet0start(ar_0, ar_1, ar_2, ar_3, ar_4) -> Com_1(evalwcet0bb0in(ar_0, ar_1, ar_2, ar_3, ar_4))", 0-2) = ar_2 S("evalwcet0start(ar_0, ar_1, ar_2, ar_3, ar_4) -> Com_1(evalwcet0bb0in(ar_0, ar_1, ar_2, ar_3, ar_4))", 0-3) = ar_3 S("evalwcet0start(ar_0, ar_1, ar_2, ar_3, ar_4) -> Com_1(evalwcet0bb0in(ar_0, ar_1, ar_2, ar_3, ar_4))", 0-4) = ar_4 orients the transitions evalwcet0bb4in(ar_0, ar_1, ar_2, ar_3, ar_4) -> Com_1(evalwcet0bb1in(ar_0, ar_1 - 1, ar_4, ar_3, ar_4)) [ ar_1 >= 2 ] evalwcet0bb3in(ar_0, ar_1, ar_2, ar_3, ar_4) -> Com_1(evalwcet0bb4in(ar_0, ar_1, ar_2, ar_3, 0)) [ 1 >= ar_0 + ar_2 ] evalwcet0bb3in(ar_0, ar_1, ar_2, ar_3, ar_4) -> Com_1(evalwcet0bb4in(ar_0, ar_1, ar_2, ar_3, ar_2 - 1)) [ ar_2 + ar_0 >= 2 ] evalwcet0bb2in(ar_0, ar_1, ar_2, ar_3, ar_4) -> Com_1(evalwcet0bb4in(ar_0, ar_1, ar_2, ar_3, ar_2 + 1)) [ ar_0 >= ar_2 + 2 ] evalwcet0bb2in(ar_0, ar_1, ar_2, ar_3, ar_4) -> Com_1(evalwcet0bb4in(ar_0, ar_1, ar_2, ar_3, 0)) [ ar_2 + 1 >= ar_0 ] evalwcet0bb1in(ar_0, ar_1, ar_2, ar_3, ar_4) -> Com_1(evalwcet04(ar_0, ar_1, ar_2, ar_3, ar_4)) evalwcet05(ar_0, ar_1, ar_2, ar_3, ar_4) -> Com_1(evalwcet0bb3in(ar_0, ar_1, ar_2, ar_3, ar_4)) [ 0 >= ar_3 ] evalwcet05(ar_0, ar_1, ar_2, ar_3, ar_4) -> Com_1(evalwcet0bb2in(ar_0, ar_1, ar_2, ar_3, ar_4)) [ ar_3 >= 1 ] evalwcet04(ar_0, ar_1, ar_2, ar_3, ar_4) -> Com_1(evalwcet05(ar_0, ar_1, ar_2, f, ar_4)) weakly and the transition evalwcet0bb4in(ar_0, ar_1, ar_2, ar_3, ar_4) -> Com_1(evalwcet0bb1in(ar_0, ar_1 - 1, ar_4, ar_3, ar_4)) [ ar_1 >= 2 ] strictly and produces the following problem: 4: T: (Comp: 1, Cost: 1) evalwcet0start(ar_0, ar_1, ar_2, ar_3, ar_4) -> Com_1(evalwcet0bb0in(ar_0, ar_1, ar_2, ar_3, ar_4)) (Comp: 1, Cost: 1) evalwcet0bb0in(ar_0, ar_1, ar_2, ar_3, ar_4) -> Com_1(evalwcet00(ar_0, ar_1, ar_2, ar_3, ar_4)) (Comp: 1, Cost: 1) evalwcet00(ar_0, ar_1, ar_2, ar_3, ar_4) -> Com_1(evalwcet01(ar_0, ar_1, ar_2, ar_3, ar_4)) (Comp: 1, Cost: 1) evalwcet01(ar_0, ar_1, ar_2, ar_3, ar_4) -> Com_1(evalwcet02(ar_0, ar_1, ar_2, ar_3, ar_4)) (Comp: 1, Cost: 1) evalwcet02(ar_0, ar_1, ar_2, ar_3, ar_4) -> Com_1(evalwcet03(ar_0, ar_1, ar_2, ar_3, ar_4)) (Comp: 1, Cost: 1) evalwcet03(ar_0, ar_1, ar_2, ar_3, ar_4) -> Com_1(evalwcet0bb1in(ar_0, ar_0, 0, ar_3, ar_4)) [ ar_0 >= 1 ] (Comp: 1, Cost: 1) evalwcet03(ar_0, ar_1, ar_2, ar_3, ar_4) -> Com_1(evalwcet0bb5in(ar_0, ar_1, ar_2, ar_3, ar_4)) [ 0 >= ar_0 ] (Comp: ?, Cost: 1) evalwcet0bb1in(ar_0, ar_1, ar_2, ar_3, ar_4) -> Com_1(evalwcet04(ar_0, ar_1, ar_2, ar_3, ar_4)) (Comp: ?, Cost: 1) evalwcet04(ar_0, ar_1, ar_2, ar_3, ar_4) -> Com_1(evalwcet05(ar_0, ar_1, ar_2, f, ar_4)) (Comp: ?, Cost: 1) evalwcet05(ar_0, ar_1, ar_2, ar_3, ar_4) -> Com_1(evalwcet0bb2in(ar_0, ar_1, ar_2, ar_3, ar_4)) [ ar_3 >= 1 ] (Comp: ?, Cost: 1) evalwcet05(ar_0, ar_1, ar_2, ar_3, ar_4) -> Com_1(evalwcet0bb3in(ar_0, ar_1, ar_2, ar_3, ar_4)) [ 0 >= ar_3 ] (Comp: ?, Cost: 1) evalwcet0bb2in(ar_0, ar_1, ar_2, ar_3, ar_4) -> Com_1(evalwcet0bb4in(ar_0, ar_1, ar_2, ar_3, 0)) [ ar_2 + 1 >= ar_0 ] (Comp: ?, Cost: 1) evalwcet0bb2in(ar_0, ar_1, ar_2, ar_3, ar_4) -> Com_1(evalwcet0bb4in(ar_0, ar_1, ar_2, ar_3, ar_2 + 1)) [ ar_0 >= ar_2 + 2 ] (Comp: ?, Cost: 1) evalwcet0bb3in(ar_0, ar_1, ar_2, ar_3, ar_4) -> Com_1(evalwcet0bb4in(ar_0, ar_1, ar_2, ar_3, 0)) [ 1 >= ar_0 + ar_2 ] (Comp: ?, Cost: 1) evalwcet0bb3in(ar_0, ar_1, ar_2, ar_3, ar_4) -> Com_1(evalwcet0bb4in(ar_0, ar_1, ar_2, ar_3, ar_2 - 1)) [ ar_2 + ar_0 >= 2 ] (Comp: ar_0, Cost: 1) evalwcet0bb4in(ar_0, ar_1, ar_2, ar_3, ar_4) -> Com_1(evalwcet0bb1in(ar_0, ar_1 - 1, ar_4, ar_3, ar_4)) [ ar_1 >= 2 ] (Comp: 2, Cost: 1) evalwcet0bb4in(ar_0, ar_1, ar_2, ar_3, ar_4) -> Com_1(evalwcet0bb5in(ar_0, ar_1, ar_2, ar_3, ar_4)) [ 1 >= ar_1 ] (Comp: 2, Cost: 1) evalwcet0bb5in(ar_0, ar_1, ar_2, ar_3, ar_4) -> Com_1(evalwcet0stop(ar_0, ar_1, ar_2, ar_3, ar_4)) (Comp: 1, Cost: 0) koat_start(ar_0, ar_1, ar_2, ar_3, ar_4) -> Com_1(evalwcet0start(ar_0, ar_1, ar_2, ar_3, ar_4)) [ 0 <= 0 ] start location: koat_start leaf cost: 0 Repeatedly propagating knowledge in problem 4 produces the following problem: 5: T: (Comp: 1, Cost: 1) evalwcet0start(ar_0, ar_1, ar_2, ar_3, ar_4) -> Com_1(evalwcet0bb0in(ar_0, ar_1, ar_2, ar_3, ar_4)) (Comp: 1, Cost: 1) evalwcet0bb0in(ar_0, ar_1, ar_2, ar_3, ar_4) -> Com_1(evalwcet00(ar_0, ar_1, ar_2, ar_3, ar_4)) (Comp: 1, Cost: 1) evalwcet00(ar_0, ar_1, ar_2, ar_3, ar_4) -> Com_1(evalwcet01(ar_0, ar_1, ar_2, ar_3, ar_4)) (Comp: 1, Cost: 1) evalwcet01(ar_0, ar_1, ar_2, ar_3, ar_4) -> Com_1(evalwcet02(ar_0, ar_1, ar_2, ar_3, ar_4)) (Comp: 1, Cost: 1) evalwcet02(ar_0, ar_1, ar_2, ar_3, ar_4) -> Com_1(evalwcet03(ar_0, ar_1, ar_2, ar_3, ar_4)) (Comp: 1, Cost: 1) evalwcet03(ar_0, ar_1, ar_2, ar_3, ar_4) -> Com_1(evalwcet0bb1in(ar_0, ar_0, 0, ar_3, ar_4)) [ ar_0 >= 1 ] (Comp: 1, Cost: 1) evalwcet03(ar_0, ar_1, ar_2, ar_3, ar_4) -> Com_1(evalwcet0bb5in(ar_0, ar_1, ar_2, ar_3, ar_4)) [ 0 >= ar_0 ] (Comp: ar_0 + 1, Cost: 1) evalwcet0bb1in(ar_0, ar_1, ar_2, ar_3, ar_4) -> Com_1(evalwcet04(ar_0, ar_1, ar_2, ar_3, ar_4)) (Comp: ar_0 + 1, Cost: 1) evalwcet04(ar_0, ar_1, ar_2, ar_3, ar_4) -> Com_1(evalwcet05(ar_0, ar_1, ar_2, f, ar_4)) (Comp: ar_0 + 1, Cost: 1) evalwcet05(ar_0, ar_1, ar_2, ar_3, ar_4) -> Com_1(evalwcet0bb2in(ar_0, ar_1, ar_2, ar_3, ar_4)) [ ar_3 >= 1 ] (Comp: ar_0 + 1, Cost: 1) evalwcet05(ar_0, ar_1, ar_2, ar_3, ar_4) -> Com_1(evalwcet0bb3in(ar_0, ar_1, ar_2, ar_3, ar_4)) [ 0 >= ar_3 ] (Comp: ar_0 + 1, Cost: 1) evalwcet0bb2in(ar_0, ar_1, ar_2, ar_3, ar_4) -> Com_1(evalwcet0bb4in(ar_0, ar_1, ar_2, ar_3, 0)) [ ar_2 + 1 >= ar_0 ] (Comp: ar_0 + 1, Cost: 1) evalwcet0bb2in(ar_0, ar_1, ar_2, ar_3, ar_4) -> Com_1(evalwcet0bb4in(ar_0, ar_1, ar_2, ar_3, ar_2 + 1)) [ ar_0 >= ar_2 + 2 ] (Comp: ar_0 + 1, Cost: 1) evalwcet0bb3in(ar_0, ar_1, ar_2, ar_3, ar_4) -> Com_1(evalwcet0bb4in(ar_0, ar_1, ar_2, ar_3, 0)) [ 1 >= ar_0 + ar_2 ] (Comp: ar_0 + 1, Cost: 1) evalwcet0bb3in(ar_0, ar_1, ar_2, ar_3, ar_4) -> Com_1(evalwcet0bb4in(ar_0, ar_1, ar_2, ar_3, ar_2 - 1)) [ ar_2 + ar_0 >= 2 ] (Comp: ar_0, Cost: 1) evalwcet0bb4in(ar_0, ar_1, ar_2, ar_3, ar_4) -> Com_1(evalwcet0bb1in(ar_0, ar_1 - 1, ar_4, ar_3, ar_4)) [ ar_1 >= 2 ] (Comp: 2, Cost: 1) evalwcet0bb4in(ar_0, ar_1, ar_2, ar_3, ar_4) -> Com_1(evalwcet0bb5in(ar_0, ar_1, ar_2, ar_3, ar_4)) [ 1 >= ar_1 ] (Comp: 2, Cost: 1) evalwcet0bb5in(ar_0, ar_1, ar_2, ar_3, ar_4) -> Com_1(evalwcet0stop(ar_0, ar_1, ar_2, ar_3, ar_4)) (Comp: 1, Cost: 0) koat_start(ar_0, ar_1, ar_2, ar_3, ar_4) -> Com_1(evalwcet0start(ar_0, ar_1, ar_2, ar_3, ar_4)) [ 0 <= 0 ] start location: koat_start leaf cost: 0 Complexity upper bound 9*ar_0 + 19 Time: 0.215 sec (SMT: 0.159 sec) ---------------------------------------- (2) BOUNDS(1, n^1) ---------------------------------------- (3) Loat Proof (FINISHED) ### Pre-processing the ITS problem ### Initial linear ITS problem Start location: evalwcet0start 0: evalwcet0start -> evalwcet0bb0in : [], cost: 1 1: evalwcet0bb0in -> evalwcet00 : [], cost: 1 2: evalwcet00 -> evalwcet01 : [], cost: 1 3: evalwcet01 -> evalwcet02 : [], cost: 1 4: evalwcet02 -> evalwcet03 : [], cost: 1 5: evalwcet03 -> evalwcet0bb1in : B'=A, C'=0, [ A>=1 ], cost: 1 6: evalwcet03 -> evalwcet0bb5in : [ 0>=A ], cost: 1 7: evalwcet0bb1in -> evalwcet04 : [], cost: 1 8: evalwcet04 -> evalwcet05 : D'=free, [], cost: 1 9: evalwcet05 -> evalwcet0bb2in : [ D>=1 ], cost: 1 10: evalwcet05 -> evalwcet0bb3in : [ 0>=D ], cost: 1 11: evalwcet0bb2in -> evalwcet0bb4in : E'=0, [ 1+C>=A ], cost: 1 12: evalwcet0bb2in -> evalwcet0bb4in : E'=1+C, [ A>=2+C ], cost: 1 13: evalwcet0bb3in -> evalwcet0bb4in : E'=0, [ 1>=C+A ], cost: 1 14: evalwcet0bb3in -> evalwcet0bb4in : E'=-1+C, [ C+A>=2 ], cost: 1 15: evalwcet0bb4in -> evalwcet0bb1in : B'=-1+B, C'=E, [ B>=2 ], cost: 1 16: evalwcet0bb4in -> evalwcet0bb5in : [ 1>=B ], cost: 1 17: evalwcet0bb5in -> evalwcet0stop : [], cost: 1 Removed unreachable and leaf rules: Start location: evalwcet0start 0: evalwcet0start -> evalwcet0bb0in : [], cost: 1 1: evalwcet0bb0in -> evalwcet00 : [], cost: 1 2: evalwcet00 -> evalwcet01 : [], cost: 1 3: evalwcet01 -> evalwcet02 : [], cost: 1 4: evalwcet02 -> evalwcet03 : [], cost: 1 5: evalwcet03 -> evalwcet0bb1in : B'=A, C'=0, [ A>=1 ], cost: 1 7: evalwcet0bb1in -> evalwcet04 : [], cost: 1 8: evalwcet04 -> evalwcet05 : D'=free, [], cost: 1 9: evalwcet05 -> evalwcet0bb2in : [ D>=1 ], cost: 1 10: evalwcet05 -> evalwcet0bb3in : [ 0>=D ], cost: 1 11: evalwcet0bb2in -> evalwcet0bb4in : E'=0, [ 1+C>=A ], cost: 1 12: evalwcet0bb2in -> evalwcet0bb4in : E'=1+C, [ A>=2+C ], cost: 1 13: evalwcet0bb3in -> evalwcet0bb4in : E'=0, [ 1>=C+A ], cost: 1 14: evalwcet0bb3in -> evalwcet0bb4in : E'=-1+C, [ C+A>=2 ], cost: 1 15: evalwcet0bb4in -> evalwcet0bb1in : B'=-1+B, C'=E, [ B>=2 ], cost: 1 ### Simplification by acceleration and chaining ### Eliminated locations (on linear paths): Start location: evalwcet0start 22: evalwcet0start -> evalwcet0bb1in : B'=A, C'=0, [ A>=1 ], cost: 6 23: evalwcet0bb1in -> evalwcet05 : D'=free, [], cost: 2 9: evalwcet05 -> evalwcet0bb2in : [ D>=1 ], cost: 1 10: evalwcet05 -> evalwcet0bb3in : [ 0>=D ], cost: 1 11: evalwcet0bb2in -> evalwcet0bb4in : E'=0, [ 1+C>=A ], cost: 1 12: evalwcet0bb2in -> evalwcet0bb4in : E'=1+C, [ A>=2+C ], cost: 1 13: evalwcet0bb3in -> evalwcet0bb4in : E'=0, [ 1>=C+A ], cost: 1 14: evalwcet0bb3in -> evalwcet0bb4in : E'=-1+C, [ C+A>=2 ], cost: 1 15: evalwcet0bb4in -> evalwcet0bb1in : B'=-1+B, C'=E, [ B>=2 ], cost: 1 Eliminated locations (on tree-shaped paths): Start location: evalwcet0start 22: evalwcet0start -> evalwcet0bb1in : B'=A, C'=0, [ A>=1 ], cost: 6 24: evalwcet0bb1in -> evalwcet0bb2in : D'=free, [ free>=1 ], cost: 3 25: evalwcet0bb1in -> evalwcet0bb3in : D'=free, [ 0>=free ], cost: 3 11: evalwcet0bb2in -> evalwcet0bb4in : E'=0, [ 1+C>=A ], cost: 1 12: evalwcet0bb2in -> evalwcet0bb4in : E'=1+C, [ A>=2+C ], cost: 1 13: evalwcet0bb3in -> evalwcet0bb4in : E'=0, [ 1>=C+A ], cost: 1 14: evalwcet0bb3in -> evalwcet0bb4in : E'=-1+C, [ C+A>=2 ], cost: 1 15: evalwcet0bb4in -> evalwcet0bb1in : B'=-1+B, C'=E, [ B>=2 ], cost: 1 Eliminated locations (on tree-shaped paths): Start location: evalwcet0start 22: evalwcet0start -> evalwcet0bb1in : B'=A, C'=0, [ A>=1 ], cost: 6 26: evalwcet0bb1in -> evalwcet0bb4in : D'=free, E'=0, [ free>=1 && 1+C>=A ], cost: 4 27: evalwcet0bb1in -> evalwcet0bb4in : D'=free, E'=1+C, [ free>=1 && A>=2+C ], cost: 4 28: evalwcet0bb1in -> evalwcet0bb4in : D'=free, E'=0, [ 0>=free && 1>=C+A ], cost: 4 29: evalwcet0bb1in -> evalwcet0bb4in : D'=free, E'=-1+C, [ 0>=free && C+A>=2 ], cost: 4 15: evalwcet0bb4in -> evalwcet0bb1in : B'=-1+B, C'=E, [ B>=2 ], cost: 1 Eliminated locations (on tree-shaped paths): Start location: evalwcet0start 22: evalwcet0start -> evalwcet0bb1in : B'=A, C'=0, [ A>=1 ], cost: 6 30: evalwcet0bb1in -> evalwcet0bb1in : B'=-1+B, C'=0, D'=free, E'=0, [ free>=1 && 1+C>=A && B>=2 ], cost: 5 31: evalwcet0bb1in -> evalwcet0bb1in : B'=-1+B, C'=1+C, D'=free, E'=1+C, [ free>=1 && A>=2+C && B>=2 ], cost: 5 32: evalwcet0bb1in -> evalwcet0bb1in : B'=-1+B, C'=0, D'=free, E'=0, [ 0>=free && 1>=C+A && B>=2 ], cost: 5 33: evalwcet0bb1in -> evalwcet0bb1in : B'=-1+B, C'=-1+C, D'=free, E'=-1+C, [ 0>=free && C+A>=2 && B>=2 ], cost: 5 Accelerating simple loops of location 6. Accelerating the following rules: 30: evalwcet0bb1in -> evalwcet0bb1in : B'=-1+B, C'=0, D'=free, E'=0, [ free>=1 && 1+C>=A && B>=2 ], cost: 5 31: evalwcet0bb1in -> evalwcet0bb1in : B'=-1+B, C'=1+C, D'=free, E'=1+C, [ free>=1 && A>=2+C && B>=2 ], cost: 5 32: evalwcet0bb1in -> evalwcet0bb1in : B'=-1+B, C'=0, D'=free, E'=0, [ 0>=free && 1>=C+A && B>=2 ], cost: 5 33: evalwcet0bb1in -> evalwcet0bb1in : B'=-1+B, C'=-1+C, D'=free, E'=-1+C, [ 0>=free && C+A>=2 && B>=2 ], cost: 5 Accelerated rule 30 with metering function -1+B (after strengthening guard), yielding the new rule 34. Accelerated rule 31 with backward acceleration, yielding the new rule 35. Accelerated rule 31 with backward acceleration, yielding the new rule 36. Accelerated rule 32 with metering function -1+B (after strengthening guard), yielding the new rule 37. Accelerated rule 33 with backward acceleration, yielding the new rule 38. Accelerated rule 33 with backward acceleration, yielding the new rule 39. Removing the simple loops: 31 33. Accelerated all simple loops using metering functions (where possible): Start location: evalwcet0start 22: evalwcet0start -> evalwcet0bb1in : B'=A, C'=0, [ A>=1 ], cost: 6 30: evalwcet0bb1in -> evalwcet0bb1in : B'=-1+B, C'=0, D'=free, E'=0, [ free>=1 && 1+C>=A && B>=2 ], cost: 5 32: evalwcet0bb1in -> evalwcet0bb1in : B'=-1+B, C'=0, D'=free, E'=0, [ 0>=free && 1>=C+A && B>=2 ], cost: 5 34: evalwcet0bb1in -> evalwcet0bb1in : B'=1, C'=0, D'=free, E'=0, [ free>=1 && 1+C>=A && B>=2 && 1>=A ], cost: -5+5*B 35: evalwcet0bb1in -> evalwcet0bb1in : 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 36: evalwcet0bb1in -> evalwcet0bb1in : 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 37: evalwcet0bb1in -> evalwcet0bb1in : B'=1, C'=0, D'=free, E'=0, [ 0>=free && 1>=C+A && B>=2 && 1>=A ], cost: -5+5*B 38: evalwcet0bb1in -> evalwcet0bb1in : B'=1-C-A+B, C'=1-A, D'=free, E'=1-A, [ 0>=free && C+A>=2 && B>=2 && 2-C-A+B>=2 ], cost: -5+5*C+5*A 39: evalwcet0bb1in -> evalwcet0bb1in : B'=1, C'=1+C-B, D'=free, E'=1+C-B, [ 0>=free && C+A>=2 && B>=2 && 2+C+A-B>=2 ], cost: -5+5*B Chained accelerated rules (with incoming rules): Start location: evalwcet0start 22: evalwcet0start -> evalwcet0bb1in : B'=A, C'=0, [ A>=1 ], cost: 6 40: evalwcet0start -> evalwcet0bb1in : B'=1, C'=-1+A, D'=free, E'=-1+A, [ free>=1 && A>=2 ], cost: 1+5*A 41: evalwcet0start -> evalwcet0bb1in : B'=1, C'=-1+A, D'=free, E'=-1+A, [ free>=1 && A>=2 ], cost: 1+5*A 42: evalwcet0start -> evalwcet0bb1in : B'=1, C'=1-A, D'=free, E'=1-A, [ 0>=free && A>=2 ], cost: 1+5*A 43: evalwcet0start -> evalwcet0bb1in : B'=1, C'=1-A, D'=free, E'=1-A, [ 0>=free && A>=2 ], cost: 1+5*A Removed unreachable locations (and leaf rules with constant cost): Start location: evalwcet0start 40: evalwcet0start -> evalwcet0bb1in : B'=1, C'=-1+A, D'=free, E'=-1+A, [ free>=1 && A>=2 ], cost: 1+5*A 41: evalwcet0start -> evalwcet0bb1in : B'=1, C'=-1+A, D'=free, E'=-1+A, [ free>=1 && A>=2 ], cost: 1+5*A 42: evalwcet0start -> evalwcet0bb1in : B'=1, C'=1-A, D'=free, E'=1-A, [ 0>=free && A>=2 ], cost: 1+5*A 43: evalwcet0start -> evalwcet0bb1in : B'=1, C'=1-A, D'=free, E'=1-A, [ 0>=free && A>=2 ], cost: 1+5*A ### Computing asymptotic complexity ### Fully simplified ITS problem Start location: evalwcet0start 41: evalwcet0start -> evalwcet0bb1in : B'=1, C'=-1+A, D'=free, E'=-1+A, [ free>=1 && A>=2 ], cost: 1+5*A 43: evalwcet0start -> evalwcet0bb1in : B'=1, C'=1-A, D'=free, E'=1-A, [ 0>=free && A>=2 ], cost: 1+5*A Computing asymptotic complexity for rule 41 Solved the limit problem by the following transformations: Created initial limit problem: -1+A (+/+!), 1+5*A (+), free (+/+!) [not solved] removing all constraints (solved by SMT) resulting limit problem: [solved] applying transformation rule (C) using substitution {free==n,A==n} resulting limit problem: [solved] Solution: free / n A / n Resulting cost 1+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: 1+5*n Rule cost: 1+5*A Rule guard: [ free>=1 && A>=2 ] WORST_CASE(Omega(n^1),?) ---------------------------------------- (4) BOUNDS(n^1, INF)