/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: 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, 197 ms] (2) BOUNDS(1, n^1) (3) Loat Proof [FINISHED, 1620 ms] (4) BOUNDS(n^1, INF) ---------------------------------------- (0) Obligation: Complexity Int TRS consisting of the following rules: 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 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 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 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 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 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 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 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 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 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 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 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 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 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 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 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 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 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 The start-symbols are:[eval_wcet1_start_5] ---------------------------------------- (1) Koat Proof (FINISHED) YES(?, 9*Ar_0 + 19) Initial complexity problem: 1: T: (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)) (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)) (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)) (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)) (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)) (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 ] (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 ] (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)) (Comp: ?, Cost: 1) evalwcet14(Ar_0, Ar_1, Ar_2, Ar_3, Ar_4) -> Com_1(evalwcet15(Ar_0, Ar_1, Ar_2, Fresh_0, Ar_4)) (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 ] (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 ] (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 ] (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 ] (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 ] (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 ] (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 ] (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 ] (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)) (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 ] start location: koat_start leaf cost: 0 Repeatedly propagating knowledge in problem 1 produces the following problem: 2: T: (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)) (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)) (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)) (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)) (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)) (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 ] (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 ] (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)) (Comp: ?, Cost: 1) evalwcet14(Ar_0, Ar_1, Ar_2, Ar_3, Ar_4) -> Com_1(evalwcet15(Ar_0, Ar_1, Ar_2, Fresh_0, Ar_4)) (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 ] (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 ] (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 ] (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 ] (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 ] (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 ] (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 ] (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 ] (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)) (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 ] start location: koat_start leaf cost: 0 A polynomial rank function with Pol(evalwcet1start) = 2 Pol(evalwcet1bb0in) = 2 Pol(evalwcet10) = 2 Pol(evalwcet11) = 2 Pol(evalwcet12) = 2 Pol(evalwcet13) = 2 Pol(evalwcet1bb1in) = 2 Pol(evalwcet1bb5in) = 1 Pol(evalwcet14) = 2 Pol(evalwcet15) = 2 Pol(evalwcet1bb2in) = 2 Pol(evalwcet1bb3in) = 2 Pol(evalwcet1bb4in) = 2 Pol(evalwcet1stop) = 0 Pol(koat_start) = 2 orients all transitions weakly and the transitions evalwcet1bb5in(Ar_0, Ar_1, Ar_2, Ar_3, Ar_4) -> Com_1(evalwcet1stop(Ar_0, Ar_1, Ar_2, Ar_3, Ar_4)) 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 ] strictly and produces the following problem: 3: T: (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)) (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)) (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)) (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)) (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)) (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 ] (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 ] (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)) (Comp: ?, Cost: 1) evalwcet14(Ar_0, Ar_1, Ar_2, Ar_3, Ar_4) -> Com_1(evalwcet15(Ar_0, Ar_1, Ar_2, Fresh_0, Ar_4)) (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 ] (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 ] (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 ] (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 ] (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 ] (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 ] (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 ] (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 ] (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)) (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 ] start location: koat_start leaf cost: 0 A polynomial rank function with Pol(evalwcet1bb4in) = V_2 Pol(evalwcet1bb1in) = V_2 Pol(evalwcet1bb3in) = V_2 Pol(evalwcet1bb2in) = V_2 Pol(evalwcet14) = V_2 Pol(evalwcet15) = V_2 and size complexities 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 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 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 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 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 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 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 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) = ? 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) = ? 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) = ? 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 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 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) = ? 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) = ? 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) = ? 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 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 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) = ? 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) = ? 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) = ? 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 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 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) = ? 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) = ? 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) = ? 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 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 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) = ? 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) = ? 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 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 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 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) = ? 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) = ? 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) = ? 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 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 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) = ? 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) = ? 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 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 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 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) = ? 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) = ? 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) = ? 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 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 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) = ? 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) = ? 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) = ? S("evalwcet14(Ar_0, Ar_1, Ar_2, Ar_3, Ar_4) -> Com_1(evalwcet15(Ar_0, Ar_1, Ar_2, Fresh_0, Ar_4))", 0-0) = Ar_0 S("evalwcet14(Ar_0, Ar_1, Ar_2, Ar_3, Ar_4) -> Com_1(evalwcet15(Ar_0, Ar_1, Ar_2, Fresh_0, Ar_4))", 0-1) = Ar_0 S("evalwcet14(Ar_0, Ar_1, Ar_2, Ar_3, Ar_4) -> Com_1(evalwcet15(Ar_0, Ar_1, Ar_2, Fresh_0, Ar_4))", 0-2) = ? S("evalwcet14(Ar_0, Ar_1, Ar_2, Ar_3, Ar_4) -> Com_1(evalwcet15(Ar_0, Ar_1, Ar_2, Fresh_0, Ar_4))", 0-3) = ? S("evalwcet14(Ar_0, Ar_1, Ar_2, Ar_3, Ar_4) -> Com_1(evalwcet15(Ar_0, Ar_1, Ar_2, Fresh_0, Ar_4))", 0-4) = ? 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 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 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) = ? 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) = ? 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) = ? 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 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 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 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 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 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 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 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 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 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 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 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 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 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 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 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 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 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 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 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 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 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 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 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 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 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 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 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 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 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 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 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 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 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 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 orients the transitions 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 ] 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 ] 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 ] 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 ] 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 ] evalwcet1bb1in(Ar_0, Ar_1, Ar_2, Ar_3, Ar_4) -> Com_1(evalwcet14(Ar_0, Ar_1, Ar_2, Ar_3, Ar_4)) 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 ] 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 ] evalwcet14(Ar_0, Ar_1, Ar_2, Ar_3, Ar_4) -> Com_1(evalwcet15(Ar_0, Ar_1, Ar_2, Fresh_0, Ar_4)) weakly and the transition 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 ] strictly and produces the following problem: 4: T: (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)) (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)) (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)) (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)) (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)) (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 ] (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 ] (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)) (Comp: ?, Cost: 1) evalwcet14(Ar_0, Ar_1, Ar_2, Ar_3, Ar_4) -> Com_1(evalwcet15(Ar_0, Ar_1, Ar_2, Fresh_0, Ar_4)) (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 ] (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 ] (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 ] (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 ] (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 ] (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 ] (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 ] (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 ] (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)) (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 ] start location: koat_start leaf cost: 0 Repeatedly propagating knowledge in problem 4 produces the following problem: 5: T: (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)) (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)) (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)) (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)) (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)) (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 ] (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 ] (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)) (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, Fresh_0, Ar_4)) (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 ] (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 ] (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 ] (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 ] (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 ] (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 ] (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 ] (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 ] (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)) (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 ] start location: koat_start leaf cost: 0 Complexity upper bound 9*Ar_0 + 19 Time: 0.188 sec (SMT: 0.125 sec) ---------------------------------------- (2) BOUNDS(1, n^1) ---------------------------------------- (3) Loat Proof (FINISHED) ### Pre-processing the ITS problem ### Initial linear ITS problem Start location: evalwcet1start 0: evalwcet1start -> evalwcet1bb0in : [], cost: 1 1: evalwcet1bb0in -> evalwcet10 : [], cost: 1 2: evalwcet10 -> evalwcet11 : [], cost: 1 3: evalwcet11 -> evalwcet12 : [], cost: 1 4: evalwcet12 -> evalwcet13 : [], cost: 1 5: evalwcet13 -> evalwcet1bb1in : B'=A, C'=0, [ A>=1 ], cost: 1 6: evalwcet13 -> evalwcet1bb5in : [ 0>=A ], cost: 1 7: evalwcet1bb1in -> evalwcet14 : [], cost: 1 8: evalwcet14 -> evalwcet15 : D'=free, [], cost: 1 9: evalwcet15 -> evalwcet1bb2in : [ D>=1 ], cost: 1 10: evalwcet15 -> evalwcet1bb3in : [ 0>=D ], cost: 1 11: evalwcet1bb2in -> evalwcet1bb4in : E'=0, [ 1+C>=A ], cost: 1 12: evalwcet1bb2in -> evalwcet1bb4in : E'=1+C, [ A>=2+C ], cost: 1 13: evalwcet1bb3in -> evalwcet1bb4in : E'=0, [ 1>=C ], cost: 1 14: evalwcet1bb3in -> evalwcet1bb4in : E'=-1+C, [ C>=2 ], cost: 1 15: evalwcet1bb4in -> evalwcet1bb1in : B'=-1+B, C'=E, [ B>=2 ], cost: 1 16: evalwcet1bb4in -> evalwcet1bb5in : [ 1>=B ], cost: 1 17: evalwcet1bb5in -> evalwcet1stop : [], cost: 1 Checking for constant complexity: The following rule is satisfiable with cost >= 1, yielding constant complexity: 0: evalwcet1start -> evalwcet1bb0in : [], cost: 1 Removed unreachable and leaf rules: Start location: evalwcet1start 0: evalwcet1start -> evalwcet1bb0in : [], cost: 1 1: evalwcet1bb0in -> evalwcet10 : [], cost: 1 2: evalwcet10 -> evalwcet11 : [], cost: 1 3: evalwcet11 -> evalwcet12 : [], cost: 1 4: evalwcet12 -> evalwcet13 : [], cost: 1 5: evalwcet13 -> evalwcet1bb1in : B'=A, C'=0, [ A>=1 ], cost: 1 7: evalwcet1bb1in -> evalwcet14 : [], cost: 1 8: evalwcet14 -> evalwcet15 : D'=free, [], cost: 1 9: evalwcet15 -> evalwcet1bb2in : [ D>=1 ], cost: 1 10: evalwcet15 -> evalwcet1bb3in : [ 0>=D ], cost: 1 11: evalwcet1bb2in -> evalwcet1bb4in : E'=0, [ 1+C>=A ], cost: 1 12: evalwcet1bb2in -> evalwcet1bb4in : E'=1+C, [ A>=2+C ], cost: 1 13: evalwcet1bb3in -> evalwcet1bb4in : E'=0, [ 1>=C ], cost: 1 14: evalwcet1bb3in -> evalwcet1bb4in : E'=-1+C, [ C>=2 ], cost: 1 15: evalwcet1bb4in -> evalwcet1bb1in : B'=-1+B, C'=E, [ B>=2 ], cost: 1 ### Simplification by acceleration and chaining ### Eliminated locations (on linear paths): Start location: evalwcet1start 22: evalwcet1start -> evalwcet1bb1in : B'=A, C'=0, [ A>=1 ], cost: 6 23: evalwcet1bb1in -> evalwcet15 : D'=free, [], cost: 2 9: evalwcet15 -> evalwcet1bb2in : [ D>=1 ], cost: 1 10: evalwcet15 -> evalwcet1bb3in : [ 0>=D ], cost: 1 11: evalwcet1bb2in -> evalwcet1bb4in : E'=0, [ 1+C>=A ], cost: 1 12: evalwcet1bb2in -> evalwcet1bb4in : E'=1+C, [ A>=2+C ], cost: 1 13: evalwcet1bb3in -> evalwcet1bb4in : E'=0, [ 1>=C ], cost: 1 14: evalwcet1bb3in -> evalwcet1bb4in : E'=-1+C, [ C>=2 ], cost: 1 15: evalwcet1bb4in -> evalwcet1bb1in : B'=-1+B, C'=E, [ B>=2 ], cost: 1 Eliminated locations (on tree-shaped paths): Start location: evalwcet1start 22: evalwcet1start -> evalwcet1bb1in : B'=A, C'=0, [ A>=1 ], cost: 6 24: evalwcet1bb1in -> evalwcet1bb2in : D'=free, [ free>=1 ], cost: 3 25: evalwcet1bb1in -> evalwcet1bb3in : D'=free, [ 0>=free ], cost: 3 11: evalwcet1bb2in -> evalwcet1bb4in : E'=0, [ 1+C>=A ], cost: 1 12: evalwcet1bb2in -> evalwcet1bb4in : E'=1+C, [ A>=2+C ], cost: 1 13: evalwcet1bb3in -> evalwcet1bb4in : E'=0, [ 1>=C ], cost: 1 14: evalwcet1bb3in -> evalwcet1bb4in : E'=-1+C, [ C>=2 ], cost: 1 15: evalwcet1bb4in -> evalwcet1bb1in : B'=-1+B, C'=E, [ B>=2 ], cost: 1 Eliminated locations (on tree-shaped paths): Start location: evalwcet1start 22: evalwcet1start -> evalwcet1bb1in : B'=A, C'=0, [ A>=1 ], cost: 6 26: evalwcet1bb1in -> evalwcet1bb4in : D'=free, E'=0, [ free>=1 && 1+C>=A ], cost: 4 27: evalwcet1bb1in -> evalwcet1bb4in : D'=free, E'=1+C, [ free>=1 && A>=2+C ], cost: 4 28: evalwcet1bb1in -> evalwcet1bb4in : D'=free, E'=0, [ 0>=free && 1>=C ], cost: 4 29: evalwcet1bb1in -> evalwcet1bb4in : D'=free, E'=-1+C, [ 0>=free && C>=2 ], cost: 4 15: evalwcet1bb4in -> evalwcet1bb1in : B'=-1+B, C'=E, [ B>=2 ], cost: 1 Eliminated locations (on tree-shaped paths): Start location: evalwcet1start 22: evalwcet1start -> evalwcet1bb1in : B'=A, C'=0, [ A>=1 ], cost: 6 30: evalwcet1bb1in -> evalwcet1bb1in : B'=-1+B, C'=0, D'=free, E'=0, [ free>=1 && 1+C>=A && B>=2 ], cost: 5 31: evalwcet1bb1in -> evalwcet1bb1in : B'=-1+B, C'=1+C, D'=free, E'=1+C, [ free>=1 && A>=2+C && B>=2 ], cost: 5 32: evalwcet1bb1in -> evalwcet1bb1in : B'=-1+B, C'=0, D'=free, E'=0, [ 0>=free && 1>=C && B>=2 ], cost: 5 33: evalwcet1bb1in -> evalwcet1bb1in : B'=-1+B, C'=-1+C, D'=free, E'=-1+C, [ 0>=free && C>=2 && B>=2 ], cost: 5 Accelerating simple loops of location 6. Accelerating the following rules: 30: evalwcet1bb1in -> evalwcet1bb1in : B'=-1+B, C'=0, D'=free, E'=0, [ free>=1 && 1+C>=A && B>=2 ], cost: 5 31: evalwcet1bb1in -> evalwcet1bb1in : B'=-1+B, C'=1+C, D'=free, E'=1+C, [ free>=1 && A>=2+C && B>=2 ], cost: 5 32: evalwcet1bb1in -> evalwcet1bb1in : B'=-1+B, C'=0, D'=free, E'=0, [ 0>=free && 1>=C && B>=2 ], cost: 5 33: evalwcet1bb1in -> evalwcet1bb1in : B'=-1+B, C'=-1+C, D'=free, E'=-1+C, [ 0>=free && C>=2 && B>=2 ], cost: 5 Accelerated rule 30 with metering function -1+B (after strengthening guard), yielding the new rule 34. Found no metering function for rule 31. Accelerated rule 32 with metering function -1+B, yielding the new rule 35. Accelerated rule 33 with metering function -1+C (after adding B>=C), yielding the new rule 36. Accelerated rule 33 with metering function -1+B (after adding B<=C), yielding the new rule 37. Removing the simple loops: 32 33. Accelerated all simple loops using metering functions (where possible): Start location: evalwcet1start 22: evalwcet1start -> evalwcet1bb1in : B'=A, C'=0, [ A>=1 ], cost: 6 30: evalwcet1bb1in -> evalwcet1bb1in : B'=-1+B, C'=0, D'=free, E'=0, [ free>=1 && 1+C>=A && B>=2 ], cost: 5 31: evalwcet1bb1in -> evalwcet1bb1in : B'=-1+B, C'=1+C, D'=free, E'=1+C, [ free>=1 && A>=2+C && B>=2 ], cost: 5 34: evalwcet1bb1in -> evalwcet1bb1in : B'=1, C'=0, D'=free, E'=0, [ free>=1 && 1+C>=A && B>=2 && 1>=A ], cost: -5+5*B 35: evalwcet1bb1in -> evalwcet1bb1in : B'=1, C'=0, D'=free, E'=0, [ 0>=free && 1>=C && B>=2 ], cost: -5+5*B 36: evalwcet1bb1in -> evalwcet1bb1in : B'=1-C+B, C'=1, D'=free, E'=1, [ 0>=free && C>=2 && B>=2 && B>=C ], cost: -5+5*C 37: 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 Chained accelerated rules (with incoming rules): Start location: evalwcet1start 22: evalwcet1start -> evalwcet1bb1in : B'=A, C'=0, [ A>=1 ], cost: 6 38: evalwcet1start -> evalwcet1bb1in : B'=-1+A, C'=1, D'=free, E'=1, [ free>=1 && A>=2 ], cost: 11 39: evalwcet1start -> evalwcet1bb1in : B'=1, C'=0, D'=free, E'=0, [ 0>=free && A>=2 ], cost: 1+5*A Removed unreachable locations (and leaf rules with constant cost): Start location: evalwcet1start 39: evalwcet1start -> evalwcet1bb1in : B'=1, C'=0, D'=free, E'=0, [ 0>=free && A>=2 ], cost: 1+5*A ### Computing asymptotic complexity ### Fully simplified ITS problem Start location: evalwcet1start 39: evalwcet1start -> evalwcet1bb1in : B'=1, C'=0, D'=free, E'=0, [ 0>=free && A>=2 ], cost: 1+5*A Computing asymptotic complexity for rule 39 Solved the limit problem by the following transformations: Created initial limit problem: -1+A (+/+!), 1+5*A (+), 1-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: [ 0>=free && A>=2 ] WORST_CASE(Omega(n^1),?) ---------------------------------------- (4) BOUNDS(n^1, INF)