/export/starexec/sandbox2/solver/bin/starexec_run_complexity /export/starexec/sandbox2/benchmark/theBenchmark.koat /export/starexec/sandbox2/output/output_files -------------------------------------------------------------------------------- WORST_CASE(Omega(n^2), O(n^2)) 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^2, n^2). (0) CpxIntTrs (1) Koat Proof [FINISHED, 224 ms] (2) BOUNDS(1, n^2) (3) Loat Proof [FINISHED, 1216 ms] (4) BOUNDS(n^2, INF) ---------------------------------------- (0) Obligation: Complexity Int TRS consisting of the following rules: eval_insertsort_start(v_20, v_3, v_i_0, v_j_0, v_length) -> Com_1(eval_insertsort_bb0_in(v_20, v_3, v_i_0, v_j_0, v_length)) :|: TRUE eval_insertsort_bb0_in(v_20, v_3, v_i_0, v_j_0, v_length) -> Com_1(eval_insertsort_0(v_20, v_3, v_i_0, v_j_0, v_length)) :|: TRUE eval_insertsort_0(v_20, v_3, v_i_0, v_j_0, v_length) -> Com_1(eval_insertsort_1(v_20, v_3, v_i_0, v_j_0, v_length)) :|: TRUE eval_insertsort_1(v_20, v_3, v_i_0, v_j_0, v_length) -> Com_1(eval_insertsort_2(v_20, v_3, v_i_0, v_j_0, v_length)) :|: TRUE eval_insertsort_2(v_20, v_3, v_i_0, v_j_0, v_length) -> Com_1(eval_insertsort_3(v_20, v_3, v_i_0, v_j_0, v_length)) :|: TRUE eval_insertsort_3(v_20, v_3, v_i_0, v_j_0, v_length) -> Com_1(eval_insertsort_4(v_20, v_3, v_i_0, v_j_0, v_length)) :|: TRUE eval_insertsort_4(v_20, v_3, v_i_0, v_j_0, v_length) -> Com_1(eval_insertsort_5(v_20, v_3, v_i_0, v_j_0, v_length)) :|: TRUE eval_insertsort_5(v_20, v_3, v_i_0, v_j_0, v_length) -> Com_1(eval_insertsort_6(v_20, v_3, v_i_0, v_j_0, v_length)) :|: TRUE eval_insertsort_6(v_20, v_3, v_i_0, v_j_0, v_length) -> Com_1(eval_insertsort_bb1_in(v_20, v_3, 1, v_j_0, v_length)) :|: TRUE eval_insertsort_bb1_in(v_20, v_3, v_i_0, v_j_0, v_length) -> Com_1(eval_insertsort_bb2_in(v_20, v_3, v_i_0, v_j_0, v_length)) :|: v_i_0 < v_length eval_insertsort_bb1_in(v_20, v_3, v_i_0, v_j_0, v_length) -> Com_1(eval_insertsort_bb7_in(v_20, v_3, v_i_0, v_j_0, v_length)) :|: v_i_0 >= v_length eval_insertsort_bb2_in(v_20, v_3, v_i_0, v_j_0, v_length) -> Com_1(eval_insertsort_bb3_in(v_20, nondef_0, v_i_0, v_i_0 - 1, v_length)) :|: TRUE eval_insertsort_bb3_in(v_20, v_3, v_i_0, v_j_0, v_length) -> Com_1(eval_insertsort_bb4_in(v_20, v_3, v_i_0, v_j_0, v_length)) :|: v_j_0 >= 0 eval_insertsort_bb3_in(v_20, v_3, v_i_0, v_j_0, v_length) -> Com_1(eval_insertsort_bb6_in(v_20, v_3, v_i_0, v_j_0, v_length)) :|: v_j_0 < 0 eval_insertsort_bb4_in(v_20, v_3, v_i_0, v_j_0, v_length) -> Com_1(eval_insertsort_bb5_in(v_20, v_3, v_i_0, v_j_0, v_length)) :|: nondef_1 > v_3 eval_insertsort_bb4_in(v_20, v_3, v_i_0, v_j_0, v_length) -> Com_1(eval_insertsort_bb6_in(v_20, v_3, v_i_0, v_j_0, v_length)) :|: nondef_1 <= v_3 eval_insertsort_bb5_in(v_20, v_3, v_i_0, v_j_0, v_length) -> Com_1(eval_insertsort_bb3_in(v_20, v_3, v_i_0, v_j_0 - 1, v_length)) :|: TRUE eval_insertsort_bb6_in(v_20, v_3, v_i_0, v_j_0, v_length) -> Com_1(eval_insertsort_25(v_i_0 + 1, v_3, v_i_0, v_j_0, v_length)) :|: TRUE eval_insertsort_25(v_20, v_3, v_i_0, v_j_0, v_length) -> Com_1(eval_insertsort_26(v_20, v_3, v_i_0, v_j_0, v_length)) :|: TRUE eval_insertsort_26(v_20, v_3, v_i_0, v_j_0, v_length) -> Com_1(eval_insertsort_bb1_in(v_20, v_3, v_20, v_j_0, v_length)) :|: TRUE eval_insertsort_bb7_in(v_20, v_3, v_i_0, v_j_0, v_length) -> Com_1(eval_insertsort_stop(v_20, v_3, v_i_0, v_j_0, v_length)) :|: TRUE The start-symbols are:[eval_insertsort_start_5] ---------------------------------------- (1) Koat Proof (FINISHED) YES(?, 229*Ar_1 + 12*Ar_1^2 + 13) Initial complexity problem: 1: T: (Comp: ?, Cost: 1) evalinsertsortstart(Ar_0, Ar_1, Ar_2, Ar_3, Ar_4) -> Com_1(evalinsertsortbb0in(Ar_0, Ar_1, Ar_2, Ar_3, Ar_4)) (Comp: ?, Cost: 1) evalinsertsortbb0in(Ar_0, Ar_1, Ar_2, Ar_3, Ar_4) -> Com_1(evalinsertsort0(Ar_0, Ar_1, Ar_2, Ar_3, Ar_4)) (Comp: ?, Cost: 1) evalinsertsort0(Ar_0, Ar_1, Ar_2, Ar_3, Ar_4) -> Com_1(evalinsertsort1(Ar_0, Ar_1, Ar_2, Ar_3, Ar_4)) (Comp: ?, Cost: 1) evalinsertsort1(Ar_0, Ar_1, Ar_2, Ar_3, Ar_4) -> Com_1(evalinsertsort2(Ar_0, Ar_1, Ar_2, Ar_3, Ar_4)) (Comp: ?, Cost: 1) evalinsertsort2(Ar_0, Ar_1, Ar_2, Ar_3, Ar_4) -> Com_1(evalinsertsort3(Ar_0, Ar_1, Ar_2, Ar_3, Ar_4)) (Comp: ?, Cost: 1) evalinsertsort3(Ar_0, Ar_1, Ar_2, Ar_3, Ar_4) -> Com_1(evalinsertsort4(Ar_0, Ar_1, Ar_2, Ar_3, Ar_4)) (Comp: ?, Cost: 1) evalinsertsort4(Ar_0, Ar_1, Ar_2, Ar_3, Ar_4) -> Com_1(evalinsertsort5(Ar_0, Ar_1, Ar_2, Ar_3, Ar_4)) (Comp: ?, Cost: 1) evalinsertsort5(Ar_0, Ar_1, Ar_2, Ar_3, Ar_4) -> Com_1(evalinsertsort6(Ar_0, Ar_1, Ar_2, Ar_3, Ar_4)) (Comp: ?, Cost: 1) evalinsertsort6(Ar_0, Ar_1, Ar_2, Ar_3, Ar_4) -> Com_1(evalinsertsortbb1in(1, Ar_1, Ar_2, Ar_3, Ar_4)) (Comp: ?, Cost: 1) evalinsertsortbb1in(Ar_0, Ar_1, Ar_2, Ar_3, Ar_4) -> Com_1(evalinsertsortbb2in(Ar_0, Ar_1, Ar_2, Ar_3, Ar_4)) [ Ar_1 >= Ar_0 + 1 ] (Comp: ?, Cost: 1) evalinsertsortbb1in(Ar_0, Ar_1, Ar_2, Ar_3, Ar_4) -> Com_1(evalinsertsortbb7in(Ar_0, Ar_1, Ar_2, Ar_3, Ar_4)) [ Ar_0 >= Ar_1 ] (Comp: ?, Cost: 1) evalinsertsortbb2in(Ar_0, Ar_1, Ar_2, Ar_3, Ar_4) -> Com_1(evalinsertsortbb3in(Ar_0, Ar_1, Fresh_0, Ar_0 - 1, Ar_4)) (Comp: ?, Cost: 1) evalinsertsortbb3in(Ar_0, Ar_1, Ar_2, Ar_3, Ar_4) -> Com_1(evalinsertsortbb4in(Ar_0, Ar_1, Ar_2, Ar_3, Ar_4)) [ Ar_3 >= 0 ] (Comp: ?, Cost: 1) evalinsertsortbb3in(Ar_0, Ar_1, Ar_2, Ar_3, Ar_4) -> Com_1(evalinsertsortbb6in(Ar_0, Ar_1, Ar_2, Ar_3, Ar_4)) [ 0 >= Ar_3 + 1 ] (Comp: ?, Cost: 1) evalinsertsortbb4in(Ar_0, Ar_1, Ar_2, Ar_3, Ar_4) -> Com_1(evalinsertsortbb5in(Ar_0, Ar_1, Ar_2, Ar_3, Ar_4)) [ F >= Ar_2 + 1 ] (Comp: ?, Cost: 1) evalinsertsortbb4in(Ar_0, Ar_1, Ar_2, Ar_3, Ar_4) -> Com_1(evalinsertsortbb6in(Ar_0, Ar_1, Ar_2, Ar_3, Ar_4)) [ Ar_2 >= F ] (Comp: ?, Cost: 1) evalinsertsortbb5in(Ar_0, Ar_1, Ar_2, Ar_3, Ar_4) -> Com_1(evalinsertsortbb3in(Ar_0, Ar_1, Ar_2, Ar_3 - 1, Ar_4)) (Comp: ?, Cost: 1) evalinsertsortbb6in(Ar_0, Ar_1, Ar_2, Ar_3, Ar_4) -> Com_1(evalinsertsort25(Ar_0, Ar_1, Ar_2, Ar_3, Ar_0 + 1)) (Comp: ?, Cost: 1) evalinsertsort25(Ar_0, Ar_1, Ar_2, Ar_3, Ar_4) -> Com_1(evalinsertsort26(Ar_0, Ar_1, Ar_2, Ar_3, Ar_4)) (Comp: ?, Cost: 1) evalinsertsort26(Ar_0, Ar_1, Ar_2, Ar_3, Ar_4) -> Com_1(evalinsertsortbb1in(Ar_4, Ar_1, Ar_2, Ar_3, Ar_4)) (Comp: ?, Cost: 1) evalinsertsortbb7in(Ar_0, Ar_1, Ar_2, Ar_3, Ar_4) -> Com_1(evalinsertsortstop(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(evalinsertsortstart(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) evalinsertsortstart(Ar_0, Ar_1, Ar_2, Ar_3, Ar_4) -> Com_1(evalinsertsortbb0in(Ar_0, Ar_1, Ar_2, Ar_3, Ar_4)) (Comp: 1, Cost: 1) evalinsertsortbb0in(Ar_0, Ar_1, Ar_2, Ar_3, Ar_4) -> Com_1(evalinsertsort0(Ar_0, Ar_1, Ar_2, Ar_3, Ar_4)) (Comp: 1, Cost: 1) evalinsertsort0(Ar_0, Ar_1, Ar_2, Ar_3, Ar_4) -> Com_1(evalinsertsort1(Ar_0, Ar_1, Ar_2, Ar_3, Ar_4)) (Comp: 1, Cost: 1) evalinsertsort1(Ar_0, Ar_1, Ar_2, Ar_3, Ar_4) -> Com_1(evalinsertsort2(Ar_0, Ar_1, Ar_2, Ar_3, Ar_4)) (Comp: 1, Cost: 1) evalinsertsort2(Ar_0, Ar_1, Ar_2, Ar_3, Ar_4) -> Com_1(evalinsertsort3(Ar_0, Ar_1, Ar_2, Ar_3, Ar_4)) (Comp: 1, Cost: 1) evalinsertsort3(Ar_0, Ar_1, Ar_2, Ar_3, Ar_4) -> Com_1(evalinsertsort4(Ar_0, Ar_1, Ar_2, Ar_3, Ar_4)) (Comp: 1, Cost: 1) evalinsertsort4(Ar_0, Ar_1, Ar_2, Ar_3, Ar_4) -> Com_1(evalinsertsort5(Ar_0, Ar_1, Ar_2, Ar_3, Ar_4)) (Comp: 1, Cost: 1) evalinsertsort5(Ar_0, Ar_1, Ar_2, Ar_3, Ar_4) -> Com_1(evalinsertsort6(Ar_0, Ar_1, Ar_2, Ar_3, Ar_4)) (Comp: 1, Cost: 1) evalinsertsort6(Ar_0, Ar_1, Ar_2, Ar_3, Ar_4) -> Com_1(evalinsertsortbb1in(1, Ar_1, Ar_2, Ar_3, Ar_4)) (Comp: ?, Cost: 1) evalinsertsortbb1in(Ar_0, Ar_1, Ar_2, Ar_3, Ar_4) -> Com_1(evalinsertsortbb2in(Ar_0, Ar_1, Ar_2, Ar_3, Ar_4)) [ Ar_1 >= Ar_0 + 1 ] (Comp: ?, Cost: 1) evalinsertsortbb1in(Ar_0, Ar_1, Ar_2, Ar_3, Ar_4) -> Com_1(evalinsertsortbb7in(Ar_0, Ar_1, Ar_2, Ar_3, Ar_4)) [ Ar_0 >= Ar_1 ] (Comp: ?, Cost: 1) evalinsertsortbb2in(Ar_0, Ar_1, Ar_2, Ar_3, Ar_4) -> Com_1(evalinsertsortbb3in(Ar_0, Ar_1, Fresh_0, Ar_0 - 1, Ar_4)) (Comp: ?, Cost: 1) evalinsertsortbb3in(Ar_0, Ar_1, Ar_2, Ar_3, Ar_4) -> Com_1(evalinsertsortbb4in(Ar_0, Ar_1, Ar_2, Ar_3, Ar_4)) [ Ar_3 >= 0 ] (Comp: ?, Cost: 1) evalinsertsortbb3in(Ar_0, Ar_1, Ar_2, Ar_3, Ar_4) -> Com_1(evalinsertsortbb6in(Ar_0, Ar_1, Ar_2, Ar_3, Ar_4)) [ 0 >= Ar_3 + 1 ] (Comp: ?, Cost: 1) evalinsertsortbb4in(Ar_0, Ar_1, Ar_2, Ar_3, Ar_4) -> Com_1(evalinsertsortbb5in(Ar_0, Ar_1, Ar_2, Ar_3, Ar_4)) [ F >= Ar_2 + 1 ] (Comp: ?, Cost: 1) evalinsertsortbb4in(Ar_0, Ar_1, Ar_2, Ar_3, Ar_4) -> Com_1(evalinsertsortbb6in(Ar_0, Ar_1, Ar_2, Ar_3, Ar_4)) [ Ar_2 >= F ] (Comp: ?, Cost: 1) evalinsertsortbb5in(Ar_0, Ar_1, Ar_2, Ar_3, Ar_4) -> Com_1(evalinsertsortbb3in(Ar_0, Ar_1, Ar_2, Ar_3 - 1, Ar_4)) (Comp: ?, Cost: 1) evalinsertsortbb6in(Ar_0, Ar_1, Ar_2, Ar_3, Ar_4) -> Com_1(evalinsertsort25(Ar_0, Ar_1, Ar_2, Ar_3, Ar_0 + 1)) (Comp: ?, Cost: 1) evalinsertsort25(Ar_0, Ar_1, Ar_2, Ar_3, Ar_4) -> Com_1(evalinsertsort26(Ar_0, Ar_1, Ar_2, Ar_3, Ar_4)) (Comp: ?, Cost: 1) evalinsertsort26(Ar_0, Ar_1, Ar_2, Ar_3, Ar_4) -> Com_1(evalinsertsortbb1in(Ar_4, Ar_1, Ar_2, Ar_3, Ar_4)) (Comp: ?, Cost: 1) evalinsertsortbb7in(Ar_0, Ar_1, Ar_2, Ar_3, Ar_4) -> Com_1(evalinsertsortstop(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(evalinsertsortstart(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(evalinsertsortstart) = 2 Pol(evalinsertsortbb0in) = 2 Pol(evalinsertsort0) = 2 Pol(evalinsertsort1) = 2 Pol(evalinsertsort2) = 2 Pol(evalinsertsort3) = 2 Pol(evalinsertsort4) = 2 Pol(evalinsertsort5) = 2 Pol(evalinsertsort6) = 2 Pol(evalinsertsortbb1in) = 2 Pol(evalinsertsortbb2in) = 2 Pol(evalinsertsortbb7in) = 1 Pol(evalinsertsortbb3in) = 2 Pol(evalinsertsortbb4in) = 2 Pol(evalinsertsortbb6in) = 2 Pol(evalinsertsortbb5in) = 2 Pol(evalinsertsort25) = 2 Pol(evalinsertsort26) = 2 Pol(evalinsertsortstop) = 0 Pol(koat_start) = 2 orients all transitions weakly and the transitions evalinsertsortbb7in(Ar_0, Ar_1, Ar_2, Ar_3, Ar_4) -> Com_1(evalinsertsortstop(Ar_0, Ar_1, Ar_2, Ar_3, Ar_4)) evalinsertsortbb1in(Ar_0, Ar_1, Ar_2, Ar_3, Ar_4) -> Com_1(evalinsertsortbb7in(Ar_0, Ar_1, Ar_2, Ar_3, Ar_4)) [ Ar_0 >= Ar_1 ] strictly and produces the following problem: 3: T: (Comp: 1, Cost: 1) evalinsertsortstart(Ar_0, Ar_1, Ar_2, Ar_3, Ar_4) -> Com_1(evalinsertsortbb0in(Ar_0, Ar_1, Ar_2, Ar_3, Ar_4)) (Comp: 1, Cost: 1) evalinsertsortbb0in(Ar_0, Ar_1, Ar_2, Ar_3, Ar_4) -> Com_1(evalinsertsort0(Ar_0, Ar_1, Ar_2, Ar_3, Ar_4)) (Comp: 1, Cost: 1) evalinsertsort0(Ar_0, Ar_1, Ar_2, Ar_3, Ar_4) -> Com_1(evalinsertsort1(Ar_0, Ar_1, Ar_2, Ar_3, Ar_4)) (Comp: 1, Cost: 1) evalinsertsort1(Ar_0, Ar_1, Ar_2, Ar_3, Ar_4) -> Com_1(evalinsertsort2(Ar_0, Ar_1, Ar_2, Ar_3, Ar_4)) (Comp: 1, Cost: 1) evalinsertsort2(Ar_0, Ar_1, Ar_2, Ar_3, Ar_4) -> Com_1(evalinsertsort3(Ar_0, Ar_1, Ar_2, Ar_3, Ar_4)) (Comp: 1, Cost: 1) evalinsertsort3(Ar_0, Ar_1, Ar_2, Ar_3, Ar_4) -> Com_1(evalinsertsort4(Ar_0, Ar_1, Ar_2, Ar_3, Ar_4)) (Comp: 1, Cost: 1) evalinsertsort4(Ar_0, Ar_1, Ar_2, Ar_3, Ar_4) -> Com_1(evalinsertsort5(Ar_0, Ar_1, Ar_2, Ar_3, Ar_4)) (Comp: 1, Cost: 1) evalinsertsort5(Ar_0, Ar_1, Ar_2, Ar_3, Ar_4) -> Com_1(evalinsertsort6(Ar_0, Ar_1, Ar_2, Ar_3, Ar_4)) (Comp: 1, Cost: 1) evalinsertsort6(Ar_0, Ar_1, Ar_2, Ar_3, Ar_4) -> Com_1(evalinsertsortbb1in(1, Ar_1, Ar_2, Ar_3, Ar_4)) (Comp: ?, Cost: 1) evalinsertsortbb1in(Ar_0, Ar_1, Ar_2, Ar_3, Ar_4) -> Com_1(evalinsertsortbb2in(Ar_0, Ar_1, Ar_2, Ar_3, Ar_4)) [ Ar_1 >= Ar_0 + 1 ] (Comp: 2, Cost: 1) evalinsertsortbb1in(Ar_0, Ar_1, Ar_2, Ar_3, Ar_4) -> Com_1(evalinsertsortbb7in(Ar_0, Ar_1, Ar_2, Ar_3, Ar_4)) [ Ar_0 >= Ar_1 ] (Comp: ?, Cost: 1) evalinsertsortbb2in(Ar_0, Ar_1, Ar_2, Ar_3, Ar_4) -> Com_1(evalinsertsortbb3in(Ar_0, Ar_1, Fresh_0, Ar_0 - 1, Ar_4)) (Comp: ?, Cost: 1) evalinsertsortbb3in(Ar_0, Ar_1, Ar_2, Ar_3, Ar_4) -> Com_1(evalinsertsortbb4in(Ar_0, Ar_1, Ar_2, Ar_3, Ar_4)) [ Ar_3 >= 0 ] (Comp: ?, Cost: 1) evalinsertsortbb3in(Ar_0, Ar_1, Ar_2, Ar_3, Ar_4) -> Com_1(evalinsertsortbb6in(Ar_0, Ar_1, Ar_2, Ar_3, Ar_4)) [ 0 >= Ar_3 + 1 ] (Comp: ?, Cost: 1) evalinsertsortbb4in(Ar_0, Ar_1, Ar_2, Ar_3, Ar_4) -> Com_1(evalinsertsortbb5in(Ar_0, Ar_1, Ar_2, Ar_3, Ar_4)) [ F >= Ar_2 + 1 ] (Comp: ?, Cost: 1) evalinsertsortbb4in(Ar_0, Ar_1, Ar_2, Ar_3, Ar_4) -> Com_1(evalinsertsortbb6in(Ar_0, Ar_1, Ar_2, Ar_3, Ar_4)) [ Ar_2 >= F ] (Comp: ?, Cost: 1) evalinsertsortbb5in(Ar_0, Ar_1, Ar_2, Ar_3, Ar_4) -> Com_1(evalinsertsortbb3in(Ar_0, Ar_1, Ar_2, Ar_3 - 1, Ar_4)) (Comp: ?, Cost: 1) evalinsertsortbb6in(Ar_0, Ar_1, Ar_2, Ar_3, Ar_4) -> Com_1(evalinsertsort25(Ar_0, Ar_1, Ar_2, Ar_3, Ar_0 + 1)) (Comp: ?, Cost: 1) evalinsertsort25(Ar_0, Ar_1, Ar_2, Ar_3, Ar_4) -> Com_1(evalinsertsort26(Ar_0, Ar_1, Ar_2, Ar_3, Ar_4)) (Comp: ?, Cost: 1) evalinsertsort26(Ar_0, Ar_1, Ar_2, Ar_3, Ar_4) -> Com_1(evalinsertsortbb1in(Ar_4, Ar_1, Ar_2, Ar_3, Ar_4)) (Comp: 2, Cost: 1) evalinsertsortbb7in(Ar_0, Ar_1, Ar_2, Ar_3, Ar_4) -> Com_1(evalinsertsortstop(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(evalinsertsortstart(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(evalinsertsortstart) = V_2 Pol(evalinsertsortbb0in) = V_2 Pol(evalinsertsort0) = V_2 Pol(evalinsertsort1) = V_2 Pol(evalinsertsort2) = V_2 Pol(evalinsertsort3) = V_2 Pol(evalinsertsort4) = V_2 Pol(evalinsertsort5) = V_2 Pol(evalinsertsort6) = V_2 Pol(evalinsertsortbb1in) = -V_1 + V_2 Pol(evalinsertsortbb2in) = -V_1 + V_2 - 1 Pol(evalinsertsortbb7in) = -V_1 + V_2 Pol(evalinsertsortbb3in) = -V_1 + V_2 - 1 Pol(evalinsertsortbb4in) = -V_1 + V_2 - 1 Pol(evalinsertsortbb6in) = -V_1 + V_2 - 1 Pol(evalinsertsortbb5in) = -V_1 + V_2 - 1 Pol(evalinsertsort25) = V_2 - V_5 Pol(evalinsertsort26) = V_2 - V_5 Pol(evalinsertsortstop) = -V_1 + V_2 Pol(koat_start) = V_2 orients all transitions weakly and the transition evalinsertsortbb1in(Ar_0, Ar_1, Ar_2, Ar_3, Ar_4) -> Com_1(evalinsertsortbb2in(Ar_0, Ar_1, Ar_2, Ar_3, Ar_4)) [ Ar_1 >= Ar_0 + 1 ] strictly and produces the following problem: 4: T: (Comp: 1, Cost: 1) evalinsertsortstart(Ar_0, Ar_1, Ar_2, Ar_3, Ar_4) -> Com_1(evalinsertsortbb0in(Ar_0, Ar_1, Ar_2, Ar_3, Ar_4)) (Comp: 1, Cost: 1) evalinsertsortbb0in(Ar_0, Ar_1, Ar_2, Ar_3, Ar_4) -> Com_1(evalinsertsort0(Ar_0, Ar_1, Ar_2, Ar_3, Ar_4)) (Comp: 1, Cost: 1) evalinsertsort0(Ar_0, Ar_1, Ar_2, Ar_3, Ar_4) -> Com_1(evalinsertsort1(Ar_0, Ar_1, Ar_2, Ar_3, Ar_4)) (Comp: 1, Cost: 1) evalinsertsort1(Ar_0, Ar_1, Ar_2, Ar_3, Ar_4) -> Com_1(evalinsertsort2(Ar_0, Ar_1, Ar_2, Ar_3, Ar_4)) (Comp: 1, Cost: 1) evalinsertsort2(Ar_0, Ar_1, Ar_2, Ar_3, Ar_4) -> Com_1(evalinsertsort3(Ar_0, Ar_1, Ar_2, Ar_3, Ar_4)) (Comp: 1, Cost: 1) evalinsertsort3(Ar_0, Ar_1, Ar_2, Ar_3, Ar_4) -> Com_1(evalinsertsort4(Ar_0, Ar_1, Ar_2, Ar_3, Ar_4)) (Comp: 1, Cost: 1) evalinsertsort4(Ar_0, Ar_1, Ar_2, Ar_3, Ar_4) -> Com_1(evalinsertsort5(Ar_0, Ar_1, Ar_2, Ar_3, Ar_4)) (Comp: 1, Cost: 1) evalinsertsort5(Ar_0, Ar_1, Ar_2, Ar_3, Ar_4) -> Com_1(evalinsertsort6(Ar_0, Ar_1, Ar_2, Ar_3, Ar_4)) (Comp: 1, Cost: 1) evalinsertsort6(Ar_0, Ar_1, Ar_2, Ar_3, Ar_4) -> Com_1(evalinsertsortbb1in(1, Ar_1, Ar_2, Ar_3, Ar_4)) (Comp: Ar_1, Cost: 1) evalinsertsortbb1in(Ar_0, Ar_1, Ar_2, Ar_3, Ar_4) -> Com_1(evalinsertsortbb2in(Ar_0, Ar_1, Ar_2, Ar_3, Ar_4)) [ Ar_1 >= Ar_0 + 1 ] (Comp: 2, Cost: 1) evalinsertsortbb1in(Ar_0, Ar_1, Ar_2, Ar_3, Ar_4) -> Com_1(evalinsertsortbb7in(Ar_0, Ar_1, Ar_2, Ar_3, Ar_4)) [ Ar_0 >= Ar_1 ] (Comp: ?, Cost: 1) evalinsertsortbb2in(Ar_0, Ar_1, Ar_2, Ar_3, Ar_4) -> Com_1(evalinsertsortbb3in(Ar_0, Ar_1, Fresh_0, Ar_0 - 1, Ar_4)) (Comp: ?, Cost: 1) evalinsertsortbb3in(Ar_0, Ar_1, Ar_2, Ar_3, Ar_4) -> Com_1(evalinsertsortbb4in(Ar_0, Ar_1, Ar_2, Ar_3, Ar_4)) [ Ar_3 >= 0 ] (Comp: ?, Cost: 1) evalinsertsortbb3in(Ar_0, Ar_1, Ar_2, Ar_3, Ar_4) -> Com_1(evalinsertsortbb6in(Ar_0, Ar_1, Ar_2, Ar_3, Ar_4)) [ 0 >= Ar_3 + 1 ] (Comp: ?, Cost: 1) evalinsertsortbb4in(Ar_0, Ar_1, Ar_2, Ar_3, Ar_4) -> Com_1(evalinsertsortbb5in(Ar_0, Ar_1, Ar_2, Ar_3, Ar_4)) [ F >= Ar_2 + 1 ] (Comp: ?, Cost: 1) evalinsertsortbb4in(Ar_0, Ar_1, Ar_2, Ar_3, Ar_4) -> Com_1(evalinsertsortbb6in(Ar_0, Ar_1, Ar_2, Ar_3, Ar_4)) [ Ar_2 >= F ] (Comp: ?, Cost: 1) evalinsertsortbb5in(Ar_0, Ar_1, Ar_2, Ar_3, Ar_4) -> Com_1(evalinsertsortbb3in(Ar_0, Ar_1, Ar_2, Ar_3 - 1, Ar_4)) (Comp: ?, Cost: 1) evalinsertsortbb6in(Ar_0, Ar_1, Ar_2, Ar_3, Ar_4) -> Com_1(evalinsertsort25(Ar_0, Ar_1, Ar_2, Ar_3, Ar_0 + 1)) (Comp: ?, Cost: 1) evalinsertsort25(Ar_0, Ar_1, Ar_2, Ar_3, Ar_4) -> Com_1(evalinsertsort26(Ar_0, Ar_1, Ar_2, Ar_3, Ar_4)) (Comp: ?, Cost: 1) evalinsertsort26(Ar_0, Ar_1, Ar_2, Ar_3, Ar_4) -> Com_1(evalinsertsortbb1in(Ar_4, Ar_1, Ar_2, Ar_3, Ar_4)) (Comp: 2, Cost: 1) evalinsertsortbb7in(Ar_0, Ar_1, Ar_2, Ar_3, Ar_4) -> Com_1(evalinsertsortstop(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(evalinsertsortstart(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) evalinsertsortstart(Ar_0, Ar_1, Ar_2, Ar_3, Ar_4) -> Com_1(evalinsertsortbb0in(Ar_0, Ar_1, Ar_2, Ar_3, Ar_4)) (Comp: 1, Cost: 1) evalinsertsortbb0in(Ar_0, Ar_1, Ar_2, Ar_3, Ar_4) -> Com_1(evalinsertsort0(Ar_0, Ar_1, Ar_2, Ar_3, Ar_4)) (Comp: 1, Cost: 1) evalinsertsort0(Ar_0, Ar_1, Ar_2, Ar_3, Ar_4) -> Com_1(evalinsertsort1(Ar_0, Ar_1, Ar_2, Ar_3, Ar_4)) (Comp: 1, Cost: 1) evalinsertsort1(Ar_0, Ar_1, Ar_2, Ar_3, Ar_4) -> Com_1(evalinsertsort2(Ar_0, Ar_1, Ar_2, Ar_3, Ar_4)) (Comp: 1, Cost: 1) evalinsertsort2(Ar_0, Ar_1, Ar_2, Ar_3, Ar_4) -> Com_1(evalinsertsort3(Ar_0, Ar_1, Ar_2, Ar_3, Ar_4)) (Comp: 1, Cost: 1) evalinsertsort3(Ar_0, Ar_1, Ar_2, Ar_3, Ar_4) -> Com_1(evalinsertsort4(Ar_0, Ar_1, Ar_2, Ar_3, Ar_4)) (Comp: 1, Cost: 1) evalinsertsort4(Ar_0, Ar_1, Ar_2, Ar_3, Ar_4) -> Com_1(evalinsertsort5(Ar_0, Ar_1, Ar_2, Ar_3, Ar_4)) (Comp: 1, Cost: 1) evalinsertsort5(Ar_0, Ar_1, Ar_2, Ar_3, Ar_4) -> Com_1(evalinsertsort6(Ar_0, Ar_1, Ar_2, Ar_3, Ar_4)) (Comp: 1, Cost: 1) evalinsertsort6(Ar_0, Ar_1, Ar_2, Ar_3, Ar_4) -> Com_1(evalinsertsortbb1in(1, Ar_1, Ar_2, Ar_3, Ar_4)) (Comp: Ar_1, Cost: 1) evalinsertsortbb1in(Ar_0, Ar_1, Ar_2, Ar_3, Ar_4) -> Com_1(evalinsertsortbb2in(Ar_0, Ar_1, Ar_2, Ar_3, Ar_4)) [ Ar_1 >= Ar_0 + 1 ] (Comp: 2, Cost: 1) evalinsertsortbb1in(Ar_0, Ar_1, Ar_2, Ar_3, Ar_4) -> Com_1(evalinsertsortbb7in(Ar_0, Ar_1, Ar_2, Ar_3, Ar_4)) [ Ar_0 >= Ar_1 ] (Comp: Ar_1, Cost: 1) evalinsertsortbb2in(Ar_0, Ar_1, Ar_2, Ar_3, Ar_4) -> Com_1(evalinsertsortbb3in(Ar_0, Ar_1, Fresh_0, Ar_0 - 1, Ar_4)) (Comp: ?, Cost: 1) evalinsertsortbb3in(Ar_0, Ar_1, Ar_2, Ar_3, Ar_4) -> Com_1(evalinsertsortbb4in(Ar_0, Ar_1, Ar_2, Ar_3, Ar_4)) [ Ar_3 >= 0 ] (Comp: ?, Cost: 1) evalinsertsortbb3in(Ar_0, Ar_1, Ar_2, Ar_3, Ar_4) -> Com_1(evalinsertsortbb6in(Ar_0, Ar_1, Ar_2, Ar_3, Ar_4)) [ 0 >= Ar_3 + 1 ] (Comp: ?, Cost: 1) evalinsertsortbb4in(Ar_0, Ar_1, Ar_2, Ar_3, Ar_4) -> Com_1(evalinsertsortbb5in(Ar_0, Ar_1, Ar_2, Ar_3, Ar_4)) [ F >= Ar_2 + 1 ] (Comp: ?, Cost: 1) evalinsertsortbb4in(Ar_0, Ar_1, Ar_2, Ar_3, Ar_4) -> Com_1(evalinsertsortbb6in(Ar_0, Ar_1, Ar_2, Ar_3, Ar_4)) [ Ar_2 >= F ] (Comp: ?, Cost: 1) evalinsertsortbb5in(Ar_0, Ar_1, Ar_2, Ar_3, Ar_4) -> Com_1(evalinsertsortbb3in(Ar_0, Ar_1, Ar_2, Ar_3 - 1, Ar_4)) (Comp: ?, Cost: 1) evalinsertsortbb6in(Ar_0, Ar_1, Ar_2, Ar_3, Ar_4) -> Com_1(evalinsertsort25(Ar_0, Ar_1, Ar_2, Ar_3, Ar_0 + 1)) (Comp: ?, Cost: 1) evalinsertsort25(Ar_0, Ar_1, Ar_2, Ar_3, Ar_4) -> Com_1(evalinsertsort26(Ar_0, Ar_1, Ar_2, Ar_3, Ar_4)) (Comp: ?, Cost: 1) evalinsertsort26(Ar_0, Ar_1, Ar_2, Ar_3, Ar_4) -> Com_1(evalinsertsortbb1in(Ar_4, Ar_1, Ar_2, Ar_3, Ar_4)) (Comp: 2, Cost: 1) evalinsertsortbb7in(Ar_0, Ar_1, Ar_2, Ar_3, Ar_4) -> Com_1(evalinsertsortstop(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(evalinsertsortstart(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(evalinsertsortbb6in) = 3 Pol(evalinsertsort25) = 2 Pol(evalinsertsortbb5in) = 4 Pol(evalinsertsortbb3in) = 4 Pol(evalinsertsortbb4in) = 4 Pol(evalinsertsort26) = 1 Pol(evalinsertsortbb1in) = 0 and size complexities S("koat_start(Ar_0, Ar_1, Ar_2, Ar_3, Ar_4) -> Com_1(evalinsertsortstart(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(evalinsertsortstart(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(evalinsertsortstart(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(evalinsertsortstart(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(evalinsertsortstart(Ar_0, Ar_1, Ar_2, Ar_3, Ar_4)) [ 0 <= 0 ]", 0-4) = Ar_4 S("evalinsertsortbb7in(Ar_0, Ar_1, Ar_2, Ar_3, Ar_4) -> Com_1(evalinsertsortstop(Ar_0, Ar_1, Ar_2, Ar_3, Ar_4))", 0-0) = ? S("evalinsertsortbb7in(Ar_0, Ar_1, Ar_2, Ar_3, Ar_4) -> Com_1(evalinsertsortstop(Ar_0, Ar_1, Ar_2, Ar_3, Ar_4))", 0-1) = Ar_1 S("evalinsertsortbb7in(Ar_0, Ar_1, Ar_2, Ar_3, Ar_4) -> Com_1(evalinsertsortstop(Ar_0, Ar_1, Ar_2, Ar_3, Ar_4))", 0-2) = ? S("evalinsertsortbb7in(Ar_0, Ar_1, Ar_2, Ar_3, Ar_4) -> Com_1(evalinsertsortstop(Ar_0, Ar_1, Ar_2, Ar_3, Ar_4))", 0-3) = ? S("evalinsertsortbb7in(Ar_0, Ar_1, Ar_2, Ar_3, Ar_4) -> Com_1(evalinsertsortstop(Ar_0, Ar_1, Ar_2, Ar_3, Ar_4))", 0-4) = ? S("evalinsertsort26(Ar_0, Ar_1, Ar_2, Ar_3, Ar_4) -> Com_1(evalinsertsortbb1in(Ar_4, Ar_1, Ar_2, Ar_3, Ar_4))", 0-0) = ? S("evalinsertsort26(Ar_0, Ar_1, Ar_2, Ar_3, Ar_4) -> Com_1(evalinsertsortbb1in(Ar_4, Ar_1, Ar_2, Ar_3, Ar_4))", 0-1) = Ar_1 S("evalinsertsort26(Ar_0, Ar_1, Ar_2, Ar_3, Ar_4) -> Com_1(evalinsertsortbb1in(Ar_4, Ar_1, Ar_2, Ar_3, Ar_4))", 0-2) = ? S("evalinsertsort26(Ar_0, Ar_1, Ar_2, Ar_3, Ar_4) -> Com_1(evalinsertsortbb1in(Ar_4, Ar_1, Ar_2, Ar_3, Ar_4))", 0-3) = ? S("evalinsertsort26(Ar_0, Ar_1, Ar_2, Ar_3, Ar_4) -> Com_1(evalinsertsortbb1in(Ar_4, Ar_1, Ar_2, Ar_3, Ar_4))", 0-4) = ? S("evalinsertsort25(Ar_0, Ar_1, Ar_2, Ar_3, Ar_4) -> Com_1(evalinsertsort26(Ar_0, Ar_1, Ar_2, Ar_3, Ar_4))", 0-0) = ? S("evalinsertsort25(Ar_0, Ar_1, Ar_2, Ar_3, Ar_4) -> Com_1(evalinsertsort26(Ar_0, Ar_1, Ar_2, Ar_3, Ar_4))", 0-1) = Ar_1 S("evalinsertsort25(Ar_0, Ar_1, Ar_2, Ar_3, Ar_4) -> Com_1(evalinsertsort26(Ar_0, Ar_1, Ar_2, Ar_3, Ar_4))", 0-2) = ? S("evalinsertsort25(Ar_0, Ar_1, Ar_2, Ar_3, Ar_4) -> Com_1(evalinsertsort26(Ar_0, Ar_1, Ar_2, Ar_3, Ar_4))", 0-3) = ? S("evalinsertsort25(Ar_0, Ar_1, Ar_2, Ar_3, Ar_4) -> Com_1(evalinsertsort26(Ar_0, Ar_1, Ar_2, Ar_3, Ar_4))", 0-4) = ? S("evalinsertsortbb6in(Ar_0, Ar_1, Ar_2, Ar_3, Ar_4) -> Com_1(evalinsertsort25(Ar_0, Ar_1, Ar_2, Ar_3, Ar_0 + 1))", 0-0) = ? S("evalinsertsortbb6in(Ar_0, Ar_1, Ar_2, Ar_3, Ar_4) -> Com_1(evalinsertsort25(Ar_0, Ar_1, Ar_2, Ar_3, Ar_0 + 1))", 0-1) = Ar_1 S("evalinsertsortbb6in(Ar_0, Ar_1, Ar_2, Ar_3, Ar_4) -> Com_1(evalinsertsort25(Ar_0, Ar_1, Ar_2, Ar_3, Ar_0 + 1))", 0-2) = ? S("evalinsertsortbb6in(Ar_0, Ar_1, Ar_2, Ar_3, Ar_4) -> Com_1(evalinsertsort25(Ar_0, Ar_1, Ar_2, Ar_3, Ar_0 + 1))", 0-3) = ? S("evalinsertsortbb6in(Ar_0, Ar_1, Ar_2, Ar_3, Ar_4) -> Com_1(evalinsertsort25(Ar_0, Ar_1, Ar_2, Ar_3, Ar_0 + 1))", 0-4) = ? S("evalinsertsortbb5in(Ar_0, Ar_1, Ar_2, Ar_3, Ar_4) -> Com_1(evalinsertsortbb3in(Ar_0, Ar_1, Ar_2, Ar_3 - 1, Ar_4))", 0-0) = ? S("evalinsertsortbb5in(Ar_0, Ar_1, Ar_2, Ar_3, Ar_4) -> Com_1(evalinsertsortbb3in(Ar_0, Ar_1, Ar_2, Ar_3 - 1, Ar_4))", 0-1) = Ar_1 S("evalinsertsortbb5in(Ar_0, Ar_1, Ar_2, Ar_3, Ar_4) -> Com_1(evalinsertsortbb3in(Ar_0, Ar_1, Ar_2, Ar_3 - 1, Ar_4))", 0-2) = ? S("evalinsertsortbb5in(Ar_0, Ar_1, Ar_2, Ar_3, Ar_4) -> Com_1(evalinsertsortbb3in(Ar_0, Ar_1, Ar_2, Ar_3 - 1, Ar_4))", 0-3) = ? S("evalinsertsortbb5in(Ar_0, Ar_1, Ar_2, Ar_3, Ar_4) -> Com_1(evalinsertsortbb3in(Ar_0, Ar_1, Ar_2, Ar_3 - 1, Ar_4))", 0-4) = ? S("evalinsertsortbb4in(Ar_0, Ar_1, Ar_2, Ar_3, Ar_4) -> Com_1(evalinsertsortbb6in(Ar_0, Ar_1, Ar_2, Ar_3, Ar_4)) [ Ar_2 >= F ]", 0-0) = ? S("evalinsertsortbb4in(Ar_0, Ar_1, Ar_2, Ar_3, Ar_4) -> Com_1(evalinsertsortbb6in(Ar_0, Ar_1, Ar_2, Ar_3, Ar_4)) [ Ar_2 >= F ]", 0-1) = Ar_1 S("evalinsertsortbb4in(Ar_0, Ar_1, Ar_2, Ar_3, Ar_4) -> Com_1(evalinsertsortbb6in(Ar_0, Ar_1, Ar_2, Ar_3, Ar_4)) [ Ar_2 >= F ]", 0-2) = ? S("evalinsertsortbb4in(Ar_0, Ar_1, Ar_2, Ar_3, Ar_4) -> Com_1(evalinsertsortbb6in(Ar_0, Ar_1, Ar_2, Ar_3, Ar_4)) [ Ar_2 >= F ]", 0-3) = ? S("evalinsertsortbb4in(Ar_0, Ar_1, Ar_2, Ar_3, Ar_4) -> Com_1(evalinsertsortbb6in(Ar_0, Ar_1, Ar_2, Ar_3, Ar_4)) [ Ar_2 >= F ]", 0-4) = ? S("evalinsertsortbb4in(Ar_0, Ar_1, Ar_2, Ar_3, Ar_4) -> Com_1(evalinsertsortbb5in(Ar_0, Ar_1, Ar_2, Ar_3, Ar_4)) [ F >= Ar_2 + 1 ]", 0-0) = ? S("evalinsertsortbb4in(Ar_0, Ar_1, Ar_2, Ar_3, Ar_4) -> Com_1(evalinsertsortbb5in(Ar_0, Ar_1, Ar_2, Ar_3, Ar_4)) [ F >= Ar_2 + 1 ]", 0-1) = Ar_1 S("evalinsertsortbb4in(Ar_0, Ar_1, Ar_2, Ar_3, Ar_4) -> Com_1(evalinsertsortbb5in(Ar_0, Ar_1, Ar_2, Ar_3, Ar_4)) [ F >= Ar_2 + 1 ]", 0-2) = ? S("evalinsertsortbb4in(Ar_0, Ar_1, Ar_2, Ar_3, Ar_4) -> Com_1(evalinsertsortbb5in(Ar_0, Ar_1, Ar_2, Ar_3, Ar_4)) [ F >= Ar_2 + 1 ]", 0-3) = ? S("evalinsertsortbb4in(Ar_0, Ar_1, Ar_2, Ar_3, Ar_4) -> Com_1(evalinsertsortbb5in(Ar_0, Ar_1, Ar_2, Ar_3, Ar_4)) [ F >= Ar_2 + 1 ]", 0-4) = ? S("evalinsertsortbb3in(Ar_0, Ar_1, Ar_2, Ar_3, Ar_4) -> Com_1(evalinsertsortbb6in(Ar_0, Ar_1, Ar_2, Ar_3, Ar_4)) [ 0 >= Ar_3 + 1 ]", 0-0) = ? S("evalinsertsortbb3in(Ar_0, Ar_1, Ar_2, Ar_3, Ar_4) -> Com_1(evalinsertsortbb6in(Ar_0, Ar_1, Ar_2, Ar_3, Ar_4)) [ 0 >= Ar_3 + 1 ]", 0-1) = Ar_1 S("evalinsertsortbb3in(Ar_0, Ar_1, Ar_2, Ar_3, Ar_4) -> Com_1(evalinsertsortbb6in(Ar_0, Ar_1, Ar_2, Ar_3, Ar_4)) [ 0 >= Ar_3 + 1 ]", 0-2) = ? S("evalinsertsortbb3in(Ar_0, Ar_1, Ar_2, Ar_3, Ar_4) -> Com_1(evalinsertsortbb6in(Ar_0, Ar_1, Ar_2, Ar_3, Ar_4)) [ 0 >= Ar_3 + 1 ]", 0-3) = ? S("evalinsertsortbb3in(Ar_0, Ar_1, Ar_2, Ar_3, Ar_4) -> Com_1(evalinsertsortbb6in(Ar_0, Ar_1, Ar_2, Ar_3, Ar_4)) [ 0 >= Ar_3 + 1 ]", 0-4) = ? S("evalinsertsortbb3in(Ar_0, Ar_1, Ar_2, Ar_3, Ar_4) -> Com_1(evalinsertsortbb4in(Ar_0, Ar_1, Ar_2, Ar_3, Ar_4)) [ Ar_3 >= 0 ]", 0-0) = ? S("evalinsertsortbb3in(Ar_0, Ar_1, Ar_2, Ar_3, Ar_4) -> Com_1(evalinsertsortbb4in(Ar_0, Ar_1, Ar_2, Ar_3, Ar_4)) [ Ar_3 >= 0 ]", 0-1) = Ar_1 S("evalinsertsortbb3in(Ar_0, Ar_1, Ar_2, Ar_3, Ar_4) -> Com_1(evalinsertsortbb4in(Ar_0, Ar_1, Ar_2, Ar_3, Ar_4)) [ Ar_3 >= 0 ]", 0-2) = ? S("evalinsertsortbb3in(Ar_0, Ar_1, Ar_2, Ar_3, Ar_4) -> Com_1(evalinsertsortbb4in(Ar_0, Ar_1, Ar_2, Ar_3, Ar_4)) [ Ar_3 >= 0 ]", 0-3) = ? S("evalinsertsortbb3in(Ar_0, Ar_1, Ar_2, Ar_3, Ar_4) -> Com_1(evalinsertsortbb4in(Ar_0, Ar_1, Ar_2, Ar_3, Ar_4)) [ Ar_3 >= 0 ]", 0-4) = ? S("evalinsertsortbb2in(Ar_0, Ar_1, Ar_2, Ar_3, Ar_4) -> Com_1(evalinsertsortbb3in(Ar_0, Ar_1, Fresh_0, Ar_0 - 1, Ar_4))", 0-0) = ? S("evalinsertsortbb2in(Ar_0, Ar_1, Ar_2, Ar_3, Ar_4) -> Com_1(evalinsertsortbb3in(Ar_0, Ar_1, Fresh_0, Ar_0 - 1, Ar_4))", 0-1) = Ar_1 S("evalinsertsortbb2in(Ar_0, Ar_1, Ar_2, Ar_3, Ar_4) -> Com_1(evalinsertsortbb3in(Ar_0, Ar_1, Fresh_0, Ar_0 - 1, Ar_4))", 0-2) = ? S("evalinsertsortbb2in(Ar_0, Ar_1, Ar_2, Ar_3, Ar_4) -> Com_1(evalinsertsortbb3in(Ar_0, Ar_1, Fresh_0, Ar_0 - 1, Ar_4))", 0-3) = ? S("evalinsertsortbb2in(Ar_0, Ar_1, Ar_2, Ar_3, Ar_4) -> Com_1(evalinsertsortbb3in(Ar_0, Ar_1, Fresh_0, Ar_0 - 1, Ar_4))", 0-4) = ? S("evalinsertsortbb1in(Ar_0, Ar_1, Ar_2, Ar_3, Ar_4) -> Com_1(evalinsertsortbb7in(Ar_0, Ar_1, Ar_2, Ar_3, Ar_4)) [ Ar_0 >= Ar_1 ]", 0-0) = ? S("evalinsertsortbb1in(Ar_0, Ar_1, Ar_2, Ar_3, Ar_4) -> Com_1(evalinsertsortbb7in(Ar_0, Ar_1, Ar_2, Ar_3, Ar_4)) [ Ar_0 >= Ar_1 ]", 0-1) = Ar_1 S("evalinsertsortbb1in(Ar_0, Ar_1, Ar_2, Ar_3, Ar_4) -> Com_1(evalinsertsortbb7in(Ar_0, Ar_1, Ar_2, Ar_3, Ar_4)) [ Ar_0 >= Ar_1 ]", 0-2) = ? S("evalinsertsortbb1in(Ar_0, Ar_1, Ar_2, Ar_3, Ar_4) -> Com_1(evalinsertsortbb7in(Ar_0, Ar_1, Ar_2, Ar_3, Ar_4)) [ Ar_0 >= Ar_1 ]", 0-3) = ? S("evalinsertsortbb1in(Ar_0, Ar_1, Ar_2, Ar_3, Ar_4) -> Com_1(evalinsertsortbb7in(Ar_0, Ar_1, Ar_2, Ar_3, Ar_4)) [ Ar_0 >= Ar_1 ]", 0-4) = ? S("evalinsertsortbb1in(Ar_0, Ar_1, Ar_2, Ar_3, Ar_4) -> Com_1(evalinsertsortbb2in(Ar_0, Ar_1, Ar_2, Ar_3, Ar_4)) [ Ar_1 >= Ar_0 + 1 ]", 0-0) = ? S("evalinsertsortbb1in(Ar_0, Ar_1, Ar_2, Ar_3, Ar_4) -> Com_1(evalinsertsortbb2in(Ar_0, Ar_1, Ar_2, Ar_3, Ar_4)) [ Ar_1 >= Ar_0 + 1 ]", 0-1) = Ar_1 S("evalinsertsortbb1in(Ar_0, Ar_1, Ar_2, Ar_3, Ar_4) -> Com_1(evalinsertsortbb2in(Ar_0, Ar_1, Ar_2, Ar_3, Ar_4)) [ Ar_1 >= Ar_0 + 1 ]", 0-2) = ? S("evalinsertsortbb1in(Ar_0, Ar_1, Ar_2, Ar_3, Ar_4) -> Com_1(evalinsertsortbb2in(Ar_0, Ar_1, Ar_2, Ar_3, Ar_4)) [ Ar_1 >= Ar_0 + 1 ]", 0-3) = ? S("evalinsertsortbb1in(Ar_0, Ar_1, Ar_2, Ar_3, Ar_4) -> Com_1(evalinsertsortbb2in(Ar_0, Ar_1, Ar_2, Ar_3, Ar_4)) [ Ar_1 >= Ar_0 + 1 ]", 0-4) = ? S("evalinsertsort6(Ar_0, Ar_1, Ar_2, Ar_3, Ar_4) -> Com_1(evalinsertsortbb1in(1, Ar_1, Ar_2, Ar_3, Ar_4))", 0-0) = 1 S("evalinsertsort6(Ar_0, Ar_1, Ar_2, Ar_3, Ar_4) -> Com_1(evalinsertsortbb1in(1, Ar_1, Ar_2, Ar_3, Ar_4))", 0-1) = Ar_1 S("evalinsertsort6(Ar_0, Ar_1, Ar_2, Ar_3, Ar_4) -> Com_1(evalinsertsortbb1in(1, Ar_1, Ar_2, Ar_3, Ar_4))", 0-2) = Ar_2 S("evalinsertsort6(Ar_0, Ar_1, Ar_2, Ar_3, Ar_4) -> Com_1(evalinsertsortbb1in(1, Ar_1, Ar_2, Ar_3, Ar_4))", 0-3) = Ar_3 S("evalinsertsort6(Ar_0, Ar_1, Ar_2, Ar_3, Ar_4) -> Com_1(evalinsertsortbb1in(1, Ar_1, Ar_2, Ar_3, Ar_4))", 0-4) = Ar_4 S("evalinsertsort5(Ar_0, Ar_1, Ar_2, Ar_3, Ar_4) -> Com_1(evalinsertsort6(Ar_0, Ar_1, Ar_2, Ar_3, Ar_4))", 0-0) = Ar_0 S("evalinsertsort5(Ar_0, Ar_1, Ar_2, Ar_3, Ar_4) -> Com_1(evalinsertsort6(Ar_0, Ar_1, Ar_2, Ar_3, Ar_4))", 0-1) = Ar_1 S("evalinsertsort5(Ar_0, Ar_1, Ar_2, Ar_3, Ar_4) -> Com_1(evalinsertsort6(Ar_0, Ar_1, Ar_2, Ar_3, Ar_4))", 0-2) = Ar_2 S("evalinsertsort5(Ar_0, Ar_1, Ar_2, Ar_3, Ar_4) -> Com_1(evalinsertsort6(Ar_0, Ar_1, Ar_2, Ar_3, Ar_4))", 0-3) = Ar_3 S("evalinsertsort5(Ar_0, Ar_1, Ar_2, Ar_3, Ar_4) -> Com_1(evalinsertsort6(Ar_0, Ar_1, Ar_2, Ar_3, Ar_4))", 0-4) = Ar_4 S("evalinsertsort4(Ar_0, Ar_1, Ar_2, Ar_3, Ar_4) -> Com_1(evalinsertsort5(Ar_0, Ar_1, Ar_2, Ar_3, Ar_4))", 0-0) = Ar_0 S("evalinsertsort4(Ar_0, Ar_1, Ar_2, Ar_3, Ar_4) -> Com_1(evalinsertsort5(Ar_0, Ar_1, Ar_2, Ar_3, Ar_4))", 0-1) = Ar_1 S("evalinsertsort4(Ar_0, Ar_1, Ar_2, Ar_3, Ar_4) -> Com_1(evalinsertsort5(Ar_0, Ar_1, Ar_2, Ar_3, Ar_4))", 0-2) = Ar_2 S("evalinsertsort4(Ar_0, Ar_1, Ar_2, Ar_3, Ar_4) -> Com_1(evalinsertsort5(Ar_0, Ar_1, Ar_2, Ar_3, Ar_4))", 0-3) = Ar_3 S("evalinsertsort4(Ar_0, Ar_1, Ar_2, Ar_3, Ar_4) -> Com_1(evalinsertsort5(Ar_0, Ar_1, Ar_2, Ar_3, Ar_4))", 0-4) = Ar_4 S("evalinsertsort3(Ar_0, Ar_1, Ar_2, Ar_3, Ar_4) -> Com_1(evalinsertsort4(Ar_0, Ar_1, Ar_2, Ar_3, Ar_4))", 0-0) = Ar_0 S("evalinsertsort3(Ar_0, Ar_1, Ar_2, Ar_3, Ar_4) -> Com_1(evalinsertsort4(Ar_0, Ar_1, Ar_2, Ar_3, Ar_4))", 0-1) = Ar_1 S("evalinsertsort3(Ar_0, Ar_1, Ar_2, Ar_3, Ar_4) -> Com_1(evalinsertsort4(Ar_0, Ar_1, Ar_2, Ar_3, Ar_4))", 0-2) = Ar_2 S("evalinsertsort3(Ar_0, Ar_1, Ar_2, Ar_3, Ar_4) -> Com_1(evalinsertsort4(Ar_0, Ar_1, Ar_2, Ar_3, Ar_4))", 0-3) = Ar_3 S("evalinsertsort3(Ar_0, Ar_1, Ar_2, Ar_3, Ar_4) -> Com_1(evalinsertsort4(Ar_0, Ar_1, Ar_2, Ar_3, Ar_4))", 0-4) = Ar_4 S("evalinsertsort2(Ar_0, Ar_1, Ar_2, Ar_3, Ar_4) -> Com_1(evalinsertsort3(Ar_0, Ar_1, Ar_2, Ar_3, Ar_4))", 0-0) = Ar_0 S("evalinsertsort2(Ar_0, Ar_1, Ar_2, Ar_3, Ar_4) -> Com_1(evalinsertsort3(Ar_0, Ar_1, Ar_2, Ar_3, Ar_4))", 0-1) = Ar_1 S("evalinsertsort2(Ar_0, Ar_1, Ar_2, Ar_3, Ar_4) -> Com_1(evalinsertsort3(Ar_0, Ar_1, Ar_2, Ar_3, Ar_4))", 0-2) = Ar_2 S("evalinsertsort2(Ar_0, Ar_1, Ar_2, Ar_3, Ar_4) -> Com_1(evalinsertsort3(Ar_0, Ar_1, Ar_2, Ar_3, Ar_4))", 0-3) = Ar_3 S("evalinsertsort2(Ar_0, Ar_1, Ar_2, Ar_3, Ar_4) -> Com_1(evalinsertsort3(Ar_0, Ar_1, Ar_2, Ar_3, Ar_4))", 0-4) = Ar_4 S("evalinsertsort1(Ar_0, Ar_1, Ar_2, Ar_3, Ar_4) -> Com_1(evalinsertsort2(Ar_0, Ar_1, Ar_2, Ar_3, Ar_4))", 0-0) = Ar_0 S("evalinsertsort1(Ar_0, Ar_1, Ar_2, Ar_3, Ar_4) -> Com_1(evalinsertsort2(Ar_0, Ar_1, Ar_2, Ar_3, Ar_4))", 0-1) = Ar_1 S("evalinsertsort1(Ar_0, Ar_1, Ar_2, Ar_3, Ar_4) -> Com_1(evalinsertsort2(Ar_0, Ar_1, Ar_2, Ar_3, Ar_4))", 0-2) = Ar_2 S("evalinsertsort1(Ar_0, Ar_1, Ar_2, Ar_3, Ar_4) -> Com_1(evalinsertsort2(Ar_0, Ar_1, Ar_2, Ar_3, Ar_4))", 0-3) = Ar_3 S("evalinsertsort1(Ar_0, Ar_1, Ar_2, Ar_3, Ar_4) -> Com_1(evalinsertsort2(Ar_0, Ar_1, Ar_2, Ar_3, Ar_4))", 0-4) = Ar_4 S("evalinsertsort0(Ar_0, Ar_1, Ar_2, Ar_3, Ar_4) -> Com_1(evalinsertsort1(Ar_0, Ar_1, Ar_2, Ar_3, Ar_4))", 0-0) = Ar_0 S("evalinsertsort0(Ar_0, Ar_1, Ar_2, Ar_3, Ar_4) -> Com_1(evalinsertsort1(Ar_0, Ar_1, Ar_2, Ar_3, Ar_4))", 0-1) = Ar_1 S("evalinsertsort0(Ar_0, Ar_1, Ar_2, Ar_3, Ar_4) -> Com_1(evalinsertsort1(Ar_0, Ar_1, Ar_2, Ar_3, Ar_4))", 0-2) = Ar_2 S("evalinsertsort0(Ar_0, Ar_1, Ar_2, Ar_3, Ar_4) -> Com_1(evalinsertsort1(Ar_0, Ar_1, Ar_2, Ar_3, Ar_4))", 0-3) = Ar_3 S("evalinsertsort0(Ar_0, Ar_1, Ar_2, Ar_3, Ar_4) -> Com_1(evalinsertsort1(Ar_0, Ar_1, Ar_2, Ar_3, Ar_4))", 0-4) = Ar_4 S("evalinsertsortbb0in(Ar_0, Ar_1, Ar_2, Ar_3, Ar_4) -> Com_1(evalinsertsort0(Ar_0, Ar_1, Ar_2, Ar_3, Ar_4))", 0-0) = Ar_0 S("evalinsertsortbb0in(Ar_0, Ar_1, Ar_2, Ar_3, Ar_4) -> Com_1(evalinsertsort0(Ar_0, Ar_1, Ar_2, Ar_3, Ar_4))", 0-1) = Ar_1 S("evalinsertsortbb0in(Ar_0, Ar_1, Ar_2, Ar_3, Ar_4) -> Com_1(evalinsertsort0(Ar_0, Ar_1, Ar_2, Ar_3, Ar_4))", 0-2) = Ar_2 S("evalinsertsortbb0in(Ar_0, Ar_1, Ar_2, Ar_3, Ar_4) -> Com_1(evalinsertsort0(Ar_0, Ar_1, Ar_2, Ar_3, Ar_4))", 0-3) = Ar_3 S("evalinsertsortbb0in(Ar_0, Ar_1, Ar_2, Ar_3, Ar_4) -> Com_1(evalinsertsort0(Ar_0, Ar_1, Ar_2, Ar_3, Ar_4))", 0-4) = Ar_4 S("evalinsertsortstart(Ar_0, Ar_1, Ar_2, Ar_3, Ar_4) -> Com_1(evalinsertsortbb0in(Ar_0, Ar_1, Ar_2, Ar_3, Ar_4))", 0-0) = Ar_0 S("evalinsertsortstart(Ar_0, Ar_1, Ar_2, Ar_3, Ar_4) -> Com_1(evalinsertsortbb0in(Ar_0, Ar_1, Ar_2, Ar_3, Ar_4))", 0-1) = Ar_1 S("evalinsertsortstart(Ar_0, Ar_1, Ar_2, Ar_3, Ar_4) -> Com_1(evalinsertsortbb0in(Ar_0, Ar_1, Ar_2, Ar_3, Ar_4))", 0-2) = Ar_2 S("evalinsertsortstart(Ar_0, Ar_1, Ar_2, Ar_3, Ar_4) -> Com_1(evalinsertsortbb0in(Ar_0, Ar_1, Ar_2, Ar_3, Ar_4))", 0-3) = Ar_3 S("evalinsertsortstart(Ar_0, Ar_1, Ar_2, Ar_3, Ar_4) -> Com_1(evalinsertsortbb0in(Ar_0, Ar_1, Ar_2, Ar_3, Ar_4))", 0-4) = Ar_4 orients the transitions evalinsertsortbb6in(Ar_0, Ar_1, Ar_2, Ar_3, Ar_4) -> Com_1(evalinsertsort25(Ar_0, Ar_1, Ar_2, Ar_3, Ar_0 + 1)) evalinsertsortbb5in(Ar_0, Ar_1, Ar_2, Ar_3, Ar_4) -> Com_1(evalinsertsortbb3in(Ar_0, Ar_1, Ar_2, Ar_3 - 1, Ar_4)) evalinsertsortbb4in(Ar_0, Ar_1, Ar_2, Ar_3, Ar_4) -> Com_1(evalinsertsortbb6in(Ar_0, Ar_1, Ar_2, Ar_3, Ar_4)) [ Ar_2 >= F ] evalinsertsortbb4in(Ar_0, Ar_1, Ar_2, Ar_3, Ar_4) -> Com_1(evalinsertsortbb5in(Ar_0, Ar_1, Ar_2, Ar_3, Ar_4)) [ F >= Ar_2 + 1 ] evalinsertsortbb3in(Ar_0, Ar_1, Ar_2, Ar_3, Ar_4) -> Com_1(evalinsertsortbb6in(Ar_0, Ar_1, Ar_2, Ar_3, Ar_4)) [ 0 >= Ar_3 + 1 ] evalinsertsortbb3in(Ar_0, Ar_1, Ar_2, Ar_3, Ar_4) -> Com_1(evalinsertsortbb4in(Ar_0, Ar_1, Ar_2, Ar_3, Ar_4)) [ Ar_3 >= 0 ] evalinsertsort26(Ar_0, Ar_1, Ar_2, Ar_3, Ar_4) -> Com_1(evalinsertsortbb1in(Ar_4, Ar_1, Ar_2, Ar_3, Ar_4)) evalinsertsort25(Ar_0, Ar_1, Ar_2, Ar_3, Ar_4) -> Com_1(evalinsertsort26(Ar_0, Ar_1, Ar_2, Ar_3, Ar_4)) weakly and the transitions evalinsertsortbb6in(Ar_0, Ar_1, Ar_2, Ar_3, Ar_4) -> Com_1(evalinsertsort25(Ar_0, Ar_1, Ar_2, Ar_3, Ar_0 + 1)) evalinsertsortbb4in(Ar_0, Ar_1, Ar_2, Ar_3, Ar_4) -> Com_1(evalinsertsortbb6in(Ar_0, Ar_1, Ar_2, Ar_3, Ar_4)) [ Ar_2 >= F ] evalinsertsortbb3in(Ar_0, Ar_1, Ar_2, Ar_3, Ar_4) -> Com_1(evalinsertsortbb6in(Ar_0, Ar_1, Ar_2, Ar_3, Ar_4)) [ 0 >= Ar_3 + 1 ] evalinsertsort26(Ar_0, Ar_1, Ar_2, Ar_3, Ar_4) -> Com_1(evalinsertsortbb1in(Ar_4, Ar_1, Ar_2, Ar_3, Ar_4)) evalinsertsort25(Ar_0, Ar_1, Ar_2, Ar_3, Ar_4) -> Com_1(evalinsertsort26(Ar_0, Ar_1, Ar_2, Ar_3, Ar_4)) strictly and produces the following problem: 6: T: (Comp: 1, Cost: 1) evalinsertsortstart(Ar_0, Ar_1, Ar_2, Ar_3, Ar_4) -> Com_1(evalinsertsortbb0in(Ar_0, Ar_1, Ar_2, Ar_3, Ar_4)) (Comp: 1, Cost: 1) evalinsertsortbb0in(Ar_0, Ar_1, Ar_2, Ar_3, Ar_4) -> Com_1(evalinsertsort0(Ar_0, Ar_1, Ar_2, Ar_3, Ar_4)) (Comp: 1, Cost: 1) evalinsertsort0(Ar_0, Ar_1, Ar_2, Ar_3, Ar_4) -> Com_1(evalinsertsort1(Ar_0, Ar_1, Ar_2, Ar_3, Ar_4)) (Comp: 1, Cost: 1) evalinsertsort1(Ar_0, Ar_1, Ar_2, Ar_3, Ar_4) -> Com_1(evalinsertsort2(Ar_0, Ar_1, Ar_2, Ar_3, Ar_4)) (Comp: 1, Cost: 1) evalinsertsort2(Ar_0, Ar_1, Ar_2, Ar_3, Ar_4) -> Com_1(evalinsertsort3(Ar_0, Ar_1, Ar_2, Ar_3, Ar_4)) (Comp: 1, Cost: 1) evalinsertsort3(Ar_0, Ar_1, Ar_2, Ar_3, Ar_4) -> Com_1(evalinsertsort4(Ar_0, Ar_1, Ar_2, Ar_3, Ar_4)) (Comp: 1, Cost: 1) evalinsertsort4(Ar_0, Ar_1, Ar_2, Ar_3, Ar_4) -> Com_1(evalinsertsort5(Ar_0, Ar_1, Ar_2, Ar_3, Ar_4)) (Comp: 1, Cost: 1) evalinsertsort5(Ar_0, Ar_1, Ar_2, Ar_3, Ar_4) -> Com_1(evalinsertsort6(Ar_0, Ar_1, Ar_2, Ar_3, Ar_4)) (Comp: 1, Cost: 1) evalinsertsort6(Ar_0, Ar_1, Ar_2, Ar_3, Ar_4) -> Com_1(evalinsertsortbb1in(1, Ar_1, Ar_2, Ar_3, Ar_4)) (Comp: Ar_1, Cost: 1) evalinsertsortbb1in(Ar_0, Ar_1, Ar_2, Ar_3, Ar_4) -> Com_1(evalinsertsortbb2in(Ar_0, Ar_1, Ar_2, Ar_3, Ar_4)) [ Ar_1 >= Ar_0 + 1 ] (Comp: 2, Cost: 1) evalinsertsortbb1in(Ar_0, Ar_1, Ar_2, Ar_3, Ar_4) -> Com_1(evalinsertsortbb7in(Ar_0, Ar_1, Ar_2, Ar_3, Ar_4)) [ Ar_0 >= Ar_1 ] (Comp: Ar_1, Cost: 1) evalinsertsortbb2in(Ar_0, Ar_1, Ar_2, Ar_3, Ar_4) -> Com_1(evalinsertsortbb3in(Ar_0, Ar_1, Fresh_0, Ar_0 - 1, Ar_4)) (Comp: ?, Cost: 1) evalinsertsortbb3in(Ar_0, Ar_1, Ar_2, Ar_3, Ar_4) -> Com_1(evalinsertsortbb4in(Ar_0, Ar_1, Ar_2, Ar_3, Ar_4)) [ Ar_3 >= 0 ] (Comp: 4*Ar_1, Cost: 1) evalinsertsortbb3in(Ar_0, Ar_1, Ar_2, Ar_3, Ar_4) -> Com_1(evalinsertsortbb6in(Ar_0, Ar_1, Ar_2, Ar_3, Ar_4)) [ 0 >= Ar_3 + 1 ] (Comp: ?, Cost: 1) evalinsertsortbb4in(Ar_0, Ar_1, Ar_2, Ar_3, Ar_4) -> Com_1(evalinsertsortbb5in(Ar_0, Ar_1, Ar_2, Ar_3, Ar_4)) [ F >= Ar_2 + 1 ] (Comp: 4*Ar_1, Cost: 1) evalinsertsortbb4in(Ar_0, Ar_1, Ar_2, Ar_3, Ar_4) -> Com_1(evalinsertsortbb6in(Ar_0, Ar_1, Ar_2, Ar_3, Ar_4)) [ Ar_2 >= F ] (Comp: ?, Cost: 1) evalinsertsortbb5in(Ar_0, Ar_1, Ar_2, Ar_3, Ar_4) -> Com_1(evalinsertsortbb3in(Ar_0, Ar_1, Ar_2, Ar_3 - 1, Ar_4)) (Comp: 4*Ar_1, Cost: 1) evalinsertsortbb6in(Ar_0, Ar_1, Ar_2, Ar_3, Ar_4) -> Com_1(evalinsertsort25(Ar_0, Ar_1, Ar_2, Ar_3, Ar_0 + 1)) (Comp: 4*Ar_1, Cost: 1) evalinsertsort25(Ar_0, Ar_1, Ar_2, Ar_3, Ar_4) -> Com_1(evalinsertsort26(Ar_0, Ar_1, Ar_2, Ar_3, Ar_4)) (Comp: 4*Ar_1, Cost: 1) evalinsertsort26(Ar_0, Ar_1, Ar_2, Ar_3, Ar_4) -> Com_1(evalinsertsortbb1in(Ar_4, Ar_1, Ar_2, Ar_3, Ar_4)) (Comp: 2, Cost: 1) evalinsertsortbb7in(Ar_0, Ar_1, Ar_2, Ar_3, Ar_4) -> Com_1(evalinsertsortstop(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(evalinsertsortstart(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(evalinsertsortbb5in) = V_4 Pol(evalinsertsortbb3in) = V_4 + 1 Pol(evalinsertsortbb4in) = V_4 and size complexities S("koat_start(Ar_0, Ar_1, Ar_2, Ar_3, Ar_4) -> Com_1(evalinsertsortstart(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(evalinsertsortstart(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(evalinsertsortstart(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(evalinsertsortstart(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(evalinsertsortstart(Ar_0, Ar_1, Ar_2, Ar_3, Ar_4)) [ 0 <= 0 ]", 0-4) = Ar_4 S("evalinsertsortbb7in(Ar_0, Ar_1, Ar_2, Ar_3, Ar_4) -> Com_1(evalinsertsortstop(Ar_0, Ar_1, Ar_2, Ar_3, Ar_4))", 0-0) = 4*Ar_1 + 272 S("evalinsertsortbb7in(Ar_0, Ar_1, Ar_2, Ar_3, Ar_4) -> Com_1(evalinsertsortstop(Ar_0, Ar_1, Ar_2, Ar_3, Ar_4))", 0-1) = Ar_1 S("evalinsertsortbb7in(Ar_0, Ar_1, Ar_2, Ar_3, Ar_4) -> Com_1(evalinsertsortstop(Ar_0, Ar_1, Ar_2, Ar_3, Ar_4))", 0-2) = ? S("evalinsertsortbb7in(Ar_0, Ar_1, Ar_2, Ar_3, Ar_4) -> Com_1(evalinsertsortstop(Ar_0, Ar_1, Ar_2, Ar_3, Ar_4))", 0-3) = ? S("evalinsertsortbb7in(Ar_0, Ar_1, Ar_2, Ar_3, Ar_4) -> Com_1(evalinsertsortstop(Ar_0, Ar_1, Ar_2, Ar_3, Ar_4))", 0-4) = 4*Ar_1 + 4*Ar_4 + 1024 S("evalinsertsort26(Ar_0, Ar_1, Ar_2, Ar_3, Ar_4) -> Com_1(evalinsertsortbb1in(Ar_4, Ar_1, Ar_2, Ar_3, Ar_4))", 0-0) = 4*Ar_1 + 16 S("evalinsertsort26(Ar_0, Ar_1, Ar_2, Ar_3, Ar_4) -> Com_1(evalinsertsortbb1in(Ar_4, Ar_1, Ar_2, Ar_3, Ar_4))", 0-1) = Ar_1 S("evalinsertsort26(Ar_0, Ar_1, Ar_2, Ar_3, Ar_4) -> Com_1(evalinsertsortbb1in(Ar_4, Ar_1, Ar_2, Ar_3, Ar_4))", 0-2) = ? S("evalinsertsort26(Ar_0, Ar_1, Ar_2, Ar_3, Ar_4) -> Com_1(evalinsertsortbb1in(Ar_4, Ar_1, Ar_2, Ar_3, Ar_4))", 0-3) = ? S("evalinsertsort26(Ar_0, Ar_1, Ar_2, Ar_3, Ar_4) -> Com_1(evalinsertsortbb1in(Ar_4, Ar_1, Ar_2, Ar_3, Ar_4))", 0-4) = 4*Ar_1 + 64 S("evalinsertsort25(Ar_0, Ar_1, Ar_2, Ar_3, Ar_4) -> Com_1(evalinsertsort26(Ar_0, Ar_1, Ar_2, Ar_3, Ar_4))", 0-0) = 4*Ar_1 + 256 S("evalinsertsort25(Ar_0, Ar_1, Ar_2, Ar_3, Ar_4) -> Com_1(evalinsertsort26(Ar_0, Ar_1, Ar_2, Ar_3, Ar_4))", 0-1) = Ar_1 S("evalinsertsort25(Ar_0, Ar_1, Ar_2, Ar_3, Ar_4) -> Com_1(evalinsertsort26(Ar_0, Ar_1, Ar_2, Ar_3, Ar_4))", 0-2) = ? S("evalinsertsort25(Ar_0, Ar_1, Ar_2, Ar_3, Ar_4) -> Com_1(evalinsertsort26(Ar_0, Ar_1, Ar_2, Ar_3, Ar_4))", 0-3) = ? S("evalinsertsort25(Ar_0, Ar_1, Ar_2, Ar_3, Ar_4) -> Com_1(evalinsertsort26(Ar_0, Ar_1, Ar_2, Ar_3, Ar_4))", 0-4) = 4*Ar_1 + 16 S("evalinsertsortbb6in(Ar_0, Ar_1, Ar_2, Ar_3, Ar_4) -> Com_1(evalinsertsort25(Ar_0, Ar_1, Ar_2, Ar_3, Ar_0 + 1))", 0-0) = 4*Ar_1 + 64 S("evalinsertsortbb6in(Ar_0, Ar_1, Ar_2, Ar_3, Ar_4) -> Com_1(evalinsertsort25(Ar_0, Ar_1, Ar_2, Ar_3, Ar_0 + 1))", 0-1) = Ar_1 S("evalinsertsortbb6in(Ar_0, Ar_1, Ar_2, Ar_3, Ar_4) -> Com_1(evalinsertsort25(Ar_0, Ar_1, Ar_2, Ar_3, Ar_0 + 1))", 0-2) = ? S("evalinsertsortbb6in(Ar_0, Ar_1, Ar_2, Ar_3, Ar_4) -> Com_1(evalinsertsort25(Ar_0, Ar_1, Ar_2, Ar_3, Ar_0 + 1))", 0-3) = ? S("evalinsertsortbb6in(Ar_0, Ar_1, Ar_2, Ar_3, Ar_4) -> Com_1(evalinsertsort25(Ar_0, Ar_1, Ar_2, Ar_3, Ar_0 + 1))", 0-4) = 4*Ar_1 + 16 S("evalinsertsortbb5in(Ar_0, Ar_1, Ar_2, Ar_3, Ar_4) -> Com_1(evalinsertsortbb3in(Ar_0, Ar_1, Ar_2, Ar_3 - 1, Ar_4))", 0-0) = 4*Ar_1 + 16 S("evalinsertsortbb5in(Ar_0, Ar_1, Ar_2, Ar_3, Ar_4) -> Com_1(evalinsertsortbb3in(Ar_0, Ar_1, Ar_2, Ar_3 - 1, Ar_4))", 0-1) = Ar_1 S("evalinsertsortbb5in(Ar_0, Ar_1, Ar_2, Ar_3, Ar_4) -> Com_1(evalinsertsortbb3in(Ar_0, Ar_1, Ar_2, Ar_3 - 1, Ar_4))", 0-2) = ? S("evalinsertsortbb5in(Ar_0, Ar_1, Ar_2, Ar_3, Ar_4) -> Com_1(evalinsertsortbb3in(Ar_0, Ar_1, Ar_2, Ar_3 - 1, Ar_4))", 0-3) = ? S("evalinsertsortbb5in(Ar_0, Ar_1, Ar_2, Ar_3, Ar_4) -> Com_1(evalinsertsortbb3in(Ar_0, Ar_1, Ar_2, Ar_3 - 1, Ar_4))", 0-4) = 4*Ar_1 + 4*Ar_4 + 4096 S("evalinsertsortbb4in(Ar_0, Ar_1, Ar_2, Ar_3, Ar_4) -> Com_1(evalinsertsortbb6in(Ar_0, Ar_1, Ar_2, Ar_3, Ar_4)) [ Ar_2 >= F ]", 0-0) = 4*Ar_1 + 16 S("evalinsertsortbb4in(Ar_0, Ar_1, Ar_2, Ar_3, Ar_4) -> Com_1(evalinsertsortbb6in(Ar_0, Ar_1, Ar_2, Ar_3, Ar_4)) [ Ar_2 >= F ]", 0-1) = Ar_1 S("evalinsertsortbb4in(Ar_0, Ar_1, Ar_2, Ar_3, Ar_4) -> Com_1(evalinsertsortbb6in(Ar_0, Ar_1, Ar_2, Ar_3, Ar_4)) [ Ar_2 >= F ]", 0-2) = ? S("evalinsertsortbb4in(Ar_0, Ar_1, Ar_2, Ar_3, Ar_4) -> Com_1(evalinsertsortbb6in(Ar_0, Ar_1, Ar_2, Ar_3, Ar_4)) [ Ar_2 >= F ]", 0-3) = ? S("evalinsertsortbb4in(Ar_0, Ar_1, Ar_2, Ar_3, Ar_4) -> Com_1(evalinsertsortbb6in(Ar_0, Ar_1, Ar_2, Ar_3, Ar_4)) [ Ar_2 >= F ]", 0-4) = 4*Ar_1 + 4*Ar_4 + 16384 S("evalinsertsortbb4in(Ar_0, Ar_1, Ar_2, Ar_3, Ar_4) -> Com_1(evalinsertsortbb5in(Ar_0, Ar_1, Ar_2, Ar_3, Ar_4)) [ F >= Ar_2 + 1 ]", 0-0) = 4*Ar_1 + 16 S("evalinsertsortbb4in(Ar_0, Ar_1, Ar_2, Ar_3, Ar_4) -> Com_1(evalinsertsortbb5in(Ar_0, Ar_1, Ar_2, Ar_3, Ar_4)) [ F >= Ar_2 + 1 ]", 0-1) = Ar_1 S("evalinsertsortbb4in(Ar_0, Ar_1, Ar_2, Ar_3, Ar_4) -> Com_1(evalinsertsortbb5in(Ar_0, Ar_1, Ar_2, Ar_3, Ar_4)) [ F >= Ar_2 + 1 ]", 0-2) = ? S("evalinsertsortbb4in(Ar_0, Ar_1, Ar_2, Ar_3, Ar_4) -> Com_1(evalinsertsortbb5in(Ar_0, Ar_1, Ar_2, Ar_3, Ar_4)) [ F >= Ar_2 + 1 ]", 0-3) = ? S("evalinsertsortbb4in(Ar_0, Ar_1, Ar_2, Ar_3, Ar_4) -> Com_1(evalinsertsortbb5in(Ar_0, Ar_1, Ar_2, Ar_3, Ar_4)) [ F >= Ar_2 + 1 ]", 0-4) = 4*Ar_1 + 4*Ar_4 + 4096 S("evalinsertsortbb3in(Ar_0, Ar_1, Ar_2, Ar_3, Ar_4) -> Com_1(evalinsertsortbb6in(Ar_0, Ar_1, Ar_2, Ar_3, Ar_4)) [ 0 >= Ar_3 + 1 ]", 0-0) = 4*Ar_1 + 16 S("evalinsertsortbb3in(Ar_0, Ar_1, Ar_2, Ar_3, Ar_4) -> Com_1(evalinsertsortbb6in(Ar_0, Ar_1, Ar_2, Ar_3, Ar_4)) [ 0 >= Ar_3 + 1 ]", 0-1) = Ar_1 S("evalinsertsortbb3in(Ar_0, Ar_1, Ar_2, Ar_3, Ar_4) -> Com_1(evalinsertsortbb6in(Ar_0, Ar_1, Ar_2, Ar_3, Ar_4)) [ 0 >= Ar_3 + 1 ]", 0-2) = ? S("evalinsertsortbb3in(Ar_0, Ar_1, Ar_2, Ar_3, Ar_4) -> Com_1(evalinsertsortbb6in(Ar_0, Ar_1, Ar_2, Ar_3, Ar_4)) [ 0 >= Ar_3 + 1 ]", 0-3) = ? S("evalinsertsortbb3in(Ar_0, Ar_1, Ar_2, Ar_3, Ar_4) -> Com_1(evalinsertsortbb6in(Ar_0, Ar_1, Ar_2, Ar_3, Ar_4)) [ 0 >= Ar_3 + 1 ]", 0-4) = 4*Ar_1 + 4*Ar_4 + 16384 S("evalinsertsortbb3in(Ar_0, Ar_1, Ar_2, Ar_3, Ar_4) -> Com_1(evalinsertsortbb4in(Ar_0, Ar_1, Ar_2, Ar_3, Ar_4)) [ Ar_3 >= 0 ]", 0-0) = 4*Ar_1 + 16 S("evalinsertsortbb3in(Ar_0, Ar_1, Ar_2, Ar_3, Ar_4) -> Com_1(evalinsertsortbb4in(Ar_0, Ar_1, Ar_2, Ar_3, Ar_4)) [ Ar_3 >= 0 ]", 0-1) = Ar_1 S("evalinsertsortbb3in(Ar_0, Ar_1, Ar_2, Ar_3, Ar_4) -> Com_1(evalinsertsortbb4in(Ar_0, Ar_1, Ar_2, Ar_3, Ar_4)) [ Ar_3 >= 0 ]", 0-2) = ? S("evalinsertsortbb3in(Ar_0, Ar_1, Ar_2, Ar_3, Ar_4) -> Com_1(evalinsertsortbb4in(Ar_0, Ar_1, Ar_2, Ar_3, Ar_4)) [ Ar_3 >= 0 ]", 0-3) = ? S("evalinsertsortbb3in(Ar_0, Ar_1, Ar_2, Ar_3, Ar_4) -> Com_1(evalinsertsortbb4in(Ar_0, Ar_1, Ar_2, Ar_3, Ar_4)) [ Ar_3 >= 0 ]", 0-4) = 4*Ar_1 + 4*Ar_4 + 4096 S("evalinsertsortbb2in(Ar_0, Ar_1, Ar_2, Ar_3, Ar_4) -> Com_1(evalinsertsortbb3in(Ar_0, Ar_1, Fresh_0, Ar_0 - 1, Ar_4))", 0-0) = 4*Ar_1 + 16 S("evalinsertsortbb2in(Ar_0, Ar_1, Ar_2, Ar_3, Ar_4) -> Com_1(evalinsertsortbb3in(Ar_0, Ar_1, Fresh_0, Ar_0 - 1, Ar_4))", 0-1) = Ar_1 S("evalinsertsortbb2in(Ar_0, Ar_1, Ar_2, Ar_3, Ar_4) -> Com_1(evalinsertsortbb3in(Ar_0, Ar_1, Fresh_0, Ar_0 - 1, Ar_4))", 0-2) = ? S("evalinsertsortbb2in(Ar_0, Ar_1, Ar_2, Ar_3, Ar_4) -> Com_1(evalinsertsortbb3in(Ar_0, Ar_1, Fresh_0, Ar_0 - 1, Ar_4))", 0-3) = 4*Ar_1 + 68 S("evalinsertsortbb2in(Ar_0, Ar_1, Ar_2, Ar_3, Ar_4) -> Com_1(evalinsertsortbb3in(Ar_0, Ar_1, Fresh_0, Ar_0 - 1, Ar_4))", 0-4) = 4*Ar_1 + 4*Ar_4 + 1024 S("evalinsertsortbb1in(Ar_0, Ar_1, Ar_2, Ar_3, Ar_4) -> Com_1(evalinsertsortbb7in(Ar_0, Ar_1, Ar_2, Ar_3, Ar_4)) [ Ar_0 >= Ar_1 ]", 0-0) = 4*Ar_1 + 68 S("evalinsertsortbb1in(Ar_0, Ar_1, Ar_2, Ar_3, Ar_4) -> Com_1(evalinsertsortbb7in(Ar_0, Ar_1, Ar_2, Ar_3, Ar_4)) [ Ar_0 >= Ar_1 ]", 0-1) = Ar_1 S("evalinsertsortbb1in(Ar_0, Ar_1, Ar_2, Ar_3, Ar_4) -> Com_1(evalinsertsortbb7in(Ar_0, Ar_1, Ar_2, Ar_3, Ar_4)) [ Ar_0 >= Ar_1 ]", 0-2) = ? S("evalinsertsortbb1in(Ar_0, Ar_1, Ar_2, Ar_3, Ar_4) -> Com_1(evalinsertsortbb7in(Ar_0, Ar_1, Ar_2, Ar_3, Ar_4)) [ Ar_0 >= Ar_1 ]", 0-3) = ? S("evalinsertsortbb1in(Ar_0, Ar_1, Ar_2, Ar_3, Ar_4) -> Com_1(evalinsertsortbb7in(Ar_0, Ar_1, Ar_2, Ar_3, Ar_4)) [ Ar_0 >= Ar_1 ]", 0-4) = 4*Ar_1 + 4*Ar_4 + 256 S("evalinsertsortbb1in(Ar_0, Ar_1, Ar_2, Ar_3, Ar_4) -> Com_1(evalinsertsortbb2in(Ar_0, Ar_1, Ar_2, Ar_3, Ar_4)) [ Ar_1 >= Ar_0 + 1 ]", 0-0) = 4*Ar_1 + 16 S("evalinsertsortbb1in(Ar_0, Ar_1, Ar_2, Ar_3, Ar_4) -> Com_1(evalinsertsortbb2in(Ar_0, Ar_1, Ar_2, Ar_3, Ar_4)) [ Ar_1 >= Ar_0 + 1 ]", 0-1) = Ar_1 S("evalinsertsortbb1in(Ar_0, Ar_1, Ar_2, Ar_3, Ar_4) -> Com_1(evalinsertsortbb2in(Ar_0, Ar_1, Ar_2, Ar_3, Ar_4)) [ Ar_1 >= Ar_0 + 1 ]", 0-2) = ? S("evalinsertsortbb1in(Ar_0, Ar_1, Ar_2, Ar_3, Ar_4) -> Com_1(evalinsertsortbb2in(Ar_0, Ar_1, Ar_2, Ar_3, Ar_4)) [ Ar_1 >= Ar_0 + 1 ]", 0-3) = ? S("evalinsertsortbb1in(Ar_0, Ar_1, Ar_2, Ar_3, Ar_4) -> Com_1(evalinsertsortbb2in(Ar_0, Ar_1, Ar_2, Ar_3, Ar_4)) [ Ar_1 >= Ar_0 + 1 ]", 0-4) = 4*Ar_1 + 4*Ar_4 + 256 S("evalinsertsort6(Ar_0, Ar_1, Ar_2, Ar_3, Ar_4) -> Com_1(evalinsertsortbb1in(1, Ar_1, Ar_2, Ar_3, Ar_4))", 0-0) = 1 S("evalinsertsort6(Ar_0, Ar_1, Ar_2, Ar_3, Ar_4) -> Com_1(evalinsertsortbb1in(1, Ar_1, Ar_2, Ar_3, Ar_4))", 0-1) = Ar_1 S("evalinsertsort6(Ar_0, Ar_1, Ar_2, Ar_3, Ar_4) -> Com_1(evalinsertsortbb1in(1, Ar_1, Ar_2, Ar_3, Ar_4))", 0-2) = Ar_2 S("evalinsertsort6(Ar_0, Ar_1, Ar_2, Ar_3, Ar_4) -> Com_1(evalinsertsortbb1in(1, Ar_1, Ar_2, Ar_3, Ar_4))", 0-3) = Ar_3 S("evalinsertsort6(Ar_0, Ar_1, Ar_2, Ar_3, Ar_4) -> Com_1(evalinsertsortbb1in(1, Ar_1, Ar_2, Ar_3, Ar_4))", 0-4) = Ar_4 S("evalinsertsort5(Ar_0, Ar_1, Ar_2, Ar_3, Ar_4) -> Com_1(evalinsertsort6(Ar_0, Ar_1, Ar_2, Ar_3, Ar_4))", 0-0) = Ar_0 S("evalinsertsort5(Ar_0, Ar_1, Ar_2, Ar_3, Ar_4) -> Com_1(evalinsertsort6(Ar_0, Ar_1, Ar_2, Ar_3, Ar_4))", 0-1) = Ar_1 S("evalinsertsort5(Ar_0, Ar_1, Ar_2, Ar_3, Ar_4) -> Com_1(evalinsertsort6(Ar_0, Ar_1, Ar_2, Ar_3, Ar_4))", 0-2) = Ar_2 S("evalinsertsort5(Ar_0, Ar_1, Ar_2, Ar_3, Ar_4) -> Com_1(evalinsertsort6(Ar_0, Ar_1, Ar_2, Ar_3, Ar_4))", 0-3) = Ar_3 S("evalinsertsort5(Ar_0, Ar_1, Ar_2, Ar_3, Ar_4) -> Com_1(evalinsertsort6(Ar_0, Ar_1, Ar_2, Ar_3, Ar_4))", 0-4) = Ar_4 S("evalinsertsort4(Ar_0, Ar_1, Ar_2, Ar_3, Ar_4) -> Com_1(evalinsertsort5(Ar_0, Ar_1, Ar_2, Ar_3, Ar_4))", 0-0) = Ar_0 S("evalinsertsort4(Ar_0, Ar_1, Ar_2, Ar_3, Ar_4) -> Com_1(evalinsertsort5(Ar_0, Ar_1, Ar_2, Ar_3, Ar_4))", 0-1) = Ar_1 S("evalinsertsort4(Ar_0, Ar_1, Ar_2, Ar_3, Ar_4) -> Com_1(evalinsertsort5(Ar_0, Ar_1, Ar_2, Ar_3, Ar_4))", 0-2) = Ar_2 S("evalinsertsort4(Ar_0, Ar_1, Ar_2, Ar_3, Ar_4) -> Com_1(evalinsertsort5(Ar_0, Ar_1, Ar_2, Ar_3, Ar_4))", 0-3) = Ar_3 S("evalinsertsort4(Ar_0, Ar_1, Ar_2, Ar_3, Ar_4) -> Com_1(evalinsertsort5(Ar_0, Ar_1, Ar_2, Ar_3, Ar_4))", 0-4) = Ar_4 S("evalinsertsort3(Ar_0, Ar_1, Ar_2, Ar_3, Ar_4) -> Com_1(evalinsertsort4(Ar_0, Ar_1, Ar_2, Ar_3, Ar_4))", 0-0) = Ar_0 S("evalinsertsort3(Ar_0, Ar_1, Ar_2, Ar_3, Ar_4) -> Com_1(evalinsertsort4(Ar_0, Ar_1, Ar_2, Ar_3, Ar_4))", 0-1) = Ar_1 S("evalinsertsort3(Ar_0, Ar_1, Ar_2, Ar_3, Ar_4) -> Com_1(evalinsertsort4(Ar_0, Ar_1, Ar_2, Ar_3, Ar_4))", 0-2) = Ar_2 S("evalinsertsort3(Ar_0, Ar_1, Ar_2, Ar_3, Ar_4) -> Com_1(evalinsertsort4(Ar_0, Ar_1, Ar_2, Ar_3, Ar_4))", 0-3) = Ar_3 S("evalinsertsort3(Ar_0, Ar_1, Ar_2, Ar_3, Ar_4) -> Com_1(evalinsertsort4(Ar_0, Ar_1, Ar_2, Ar_3, Ar_4))", 0-4) = Ar_4 S("evalinsertsort2(Ar_0, Ar_1, Ar_2, Ar_3, Ar_4) -> Com_1(evalinsertsort3(Ar_0, Ar_1, Ar_2, Ar_3, Ar_4))", 0-0) = Ar_0 S("evalinsertsort2(Ar_0, Ar_1, Ar_2, Ar_3, Ar_4) -> Com_1(evalinsertsort3(Ar_0, Ar_1, Ar_2, Ar_3, Ar_4))", 0-1) = Ar_1 S("evalinsertsort2(Ar_0, Ar_1, Ar_2, Ar_3, Ar_4) -> Com_1(evalinsertsort3(Ar_0, Ar_1, Ar_2, Ar_3, Ar_4))", 0-2) = Ar_2 S("evalinsertsort2(Ar_0, Ar_1, Ar_2, Ar_3, Ar_4) -> Com_1(evalinsertsort3(Ar_0, Ar_1, Ar_2, Ar_3, Ar_4))", 0-3) = Ar_3 S("evalinsertsort2(Ar_0, Ar_1, Ar_2, Ar_3, Ar_4) -> Com_1(evalinsertsort3(Ar_0, Ar_1, Ar_2, Ar_3, Ar_4))", 0-4) = Ar_4 S("evalinsertsort1(Ar_0, Ar_1, Ar_2, Ar_3, Ar_4) -> Com_1(evalinsertsort2(Ar_0, Ar_1, Ar_2, Ar_3, Ar_4))", 0-0) = Ar_0 S("evalinsertsort1(Ar_0, Ar_1, Ar_2, Ar_3, Ar_4) -> Com_1(evalinsertsort2(Ar_0, Ar_1, Ar_2, Ar_3, Ar_4))", 0-1) = Ar_1 S("evalinsertsort1(Ar_0, Ar_1, Ar_2, Ar_3, Ar_4) -> Com_1(evalinsertsort2(Ar_0, Ar_1, Ar_2, Ar_3, Ar_4))", 0-2) = Ar_2 S("evalinsertsort1(Ar_0, Ar_1, Ar_2, Ar_3, Ar_4) -> Com_1(evalinsertsort2(Ar_0, Ar_1, Ar_2, Ar_3, Ar_4))", 0-3) = Ar_3 S("evalinsertsort1(Ar_0, Ar_1, Ar_2, Ar_3, Ar_4) -> Com_1(evalinsertsort2(Ar_0, Ar_1, Ar_2, Ar_3, Ar_4))", 0-4) = Ar_4 S("evalinsertsort0(Ar_0, Ar_1, Ar_2, Ar_3, Ar_4) -> Com_1(evalinsertsort1(Ar_0, Ar_1, Ar_2, Ar_3, Ar_4))", 0-0) = Ar_0 S("evalinsertsort0(Ar_0, Ar_1, Ar_2, Ar_3, Ar_4) -> Com_1(evalinsertsort1(Ar_0, Ar_1, Ar_2, Ar_3, Ar_4))", 0-1) = Ar_1 S("evalinsertsort0(Ar_0, Ar_1, Ar_2, Ar_3, Ar_4) -> Com_1(evalinsertsort1(Ar_0, Ar_1, Ar_2, Ar_3, Ar_4))", 0-2) = Ar_2 S("evalinsertsort0(Ar_0, Ar_1, Ar_2, Ar_3, Ar_4) -> Com_1(evalinsertsort1(Ar_0, Ar_1, Ar_2, Ar_3, Ar_4))", 0-3) = Ar_3 S("evalinsertsort0(Ar_0, Ar_1, Ar_2, Ar_3, Ar_4) -> Com_1(evalinsertsort1(Ar_0, Ar_1, Ar_2, Ar_3, Ar_4))", 0-4) = Ar_4 S("evalinsertsortbb0in(Ar_0, Ar_1, Ar_2, Ar_3, Ar_4) -> Com_1(evalinsertsort0(Ar_0, Ar_1, Ar_2, Ar_3, Ar_4))", 0-0) = Ar_0 S("evalinsertsortbb0in(Ar_0, Ar_1, Ar_2, Ar_3, Ar_4) -> Com_1(evalinsertsort0(Ar_0, Ar_1, Ar_2, Ar_3, Ar_4))", 0-1) = Ar_1 S("evalinsertsortbb0in(Ar_0, Ar_1, Ar_2, Ar_3, Ar_4) -> Com_1(evalinsertsort0(Ar_0, Ar_1, Ar_2, Ar_3, Ar_4))", 0-2) = Ar_2 S("evalinsertsortbb0in(Ar_0, Ar_1, Ar_2, Ar_3, Ar_4) -> Com_1(evalinsertsort0(Ar_0, Ar_1, Ar_2, Ar_3, Ar_4))", 0-3) = Ar_3 S("evalinsertsortbb0in(Ar_0, Ar_1, Ar_2, Ar_3, Ar_4) -> Com_1(evalinsertsort0(Ar_0, Ar_1, Ar_2, Ar_3, Ar_4))", 0-4) = Ar_4 S("evalinsertsortstart(Ar_0, Ar_1, Ar_2, Ar_3, Ar_4) -> Com_1(evalinsertsortbb0in(Ar_0, Ar_1, Ar_2, Ar_3, Ar_4))", 0-0) = Ar_0 S("evalinsertsortstart(Ar_0, Ar_1, Ar_2, Ar_3, Ar_4) -> Com_1(evalinsertsortbb0in(Ar_0, Ar_1, Ar_2, Ar_3, Ar_4))", 0-1) = Ar_1 S("evalinsertsortstart(Ar_0, Ar_1, Ar_2, Ar_3, Ar_4) -> Com_1(evalinsertsortbb0in(Ar_0, Ar_1, Ar_2, Ar_3, Ar_4))", 0-2) = Ar_2 S("evalinsertsortstart(Ar_0, Ar_1, Ar_2, Ar_3, Ar_4) -> Com_1(evalinsertsortbb0in(Ar_0, Ar_1, Ar_2, Ar_3, Ar_4))", 0-3) = Ar_3 S("evalinsertsortstart(Ar_0, Ar_1, Ar_2, Ar_3, Ar_4) -> Com_1(evalinsertsortbb0in(Ar_0, Ar_1, Ar_2, Ar_3, Ar_4))", 0-4) = Ar_4 orients the transitions evalinsertsortbb5in(Ar_0, Ar_1, Ar_2, Ar_3, Ar_4) -> Com_1(evalinsertsortbb3in(Ar_0, Ar_1, Ar_2, Ar_3 - 1, Ar_4)) evalinsertsortbb4in(Ar_0, Ar_1, Ar_2, Ar_3, Ar_4) -> Com_1(evalinsertsortbb5in(Ar_0, Ar_1, Ar_2, Ar_3, Ar_4)) [ F >= Ar_2 + 1 ] evalinsertsortbb3in(Ar_0, Ar_1, Ar_2, Ar_3, Ar_4) -> Com_1(evalinsertsortbb4in(Ar_0, Ar_1, Ar_2, Ar_3, Ar_4)) [ Ar_3 >= 0 ] weakly and the transition evalinsertsortbb3in(Ar_0, Ar_1, Ar_2, Ar_3, Ar_4) -> Com_1(evalinsertsortbb4in(Ar_0, Ar_1, Ar_2, Ar_3, Ar_4)) [ Ar_3 >= 0 ] strictly and produces the following problem: 7: T: (Comp: 1, Cost: 1) evalinsertsortstart(Ar_0, Ar_1, Ar_2, Ar_3, Ar_4) -> Com_1(evalinsertsortbb0in(Ar_0, Ar_1, Ar_2, Ar_3, Ar_4)) (Comp: 1, Cost: 1) evalinsertsortbb0in(Ar_0, Ar_1, Ar_2, Ar_3, Ar_4) -> Com_1(evalinsertsort0(Ar_0, Ar_1, Ar_2, Ar_3, Ar_4)) (Comp: 1, Cost: 1) evalinsertsort0(Ar_0, Ar_1, Ar_2, Ar_3, Ar_4) -> Com_1(evalinsertsort1(Ar_0, Ar_1, Ar_2, Ar_3, Ar_4)) (Comp: 1, Cost: 1) evalinsertsort1(Ar_0, Ar_1, Ar_2, Ar_3, Ar_4) -> Com_1(evalinsertsort2(Ar_0, Ar_1, Ar_2, Ar_3, Ar_4)) (Comp: 1, Cost: 1) evalinsertsort2(Ar_0, Ar_1, Ar_2, Ar_3, Ar_4) -> Com_1(evalinsertsort3(Ar_0, Ar_1, Ar_2, Ar_3, Ar_4)) (Comp: 1, Cost: 1) evalinsertsort3(Ar_0, Ar_1, Ar_2, Ar_3, Ar_4) -> Com_1(evalinsertsort4(Ar_0, Ar_1, Ar_2, Ar_3, Ar_4)) (Comp: 1, Cost: 1) evalinsertsort4(Ar_0, Ar_1, Ar_2, Ar_3, Ar_4) -> Com_1(evalinsertsort5(Ar_0, Ar_1, Ar_2, Ar_3, Ar_4)) (Comp: 1, Cost: 1) evalinsertsort5(Ar_0, Ar_1, Ar_2, Ar_3, Ar_4) -> Com_1(evalinsertsort6(Ar_0, Ar_1, Ar_2, Ar_3, Ar_4)) (Comp: 1, Cost: 1) evalinsertsort6(Ar_0, Ar_1, Ar_2, Ar_3, Ar_4) -> Com_1(evalinsertsortbb1in(1, Ar_1, Ar_2, Ar_3, Ar_4)) (Comp: Ar_1, Cost: 1) evalinsertsortbb1in(Ar_0, Ar_1, Ar_2, Ar_3, Ar_4) -> Com_1(evalinsertsortbb2in(Ar_0, Ar_1, Ar_2, Ar_3, Ar_4)) [ Ar_1 >= Ar_0 + 1 ] (Comp: 2, Cost: 1) evalinsertsortbb1in(Ar_0, Ar_1, Ar_2, Ar_3, Ar_4) -> Com_1(evalinsertsortbb7in(Ar_0, Ar_1, Ar_2, Ar_3, Ar_4)) [ Ar_0 >= Ar_1 ] (Comp: Ar_1, Cost: 1) evalinsertsortbb2in(Ar_0, Ar_1, Ar_2, Ar_3, Ar_4) -> Com_1(evalinsertsortbb3in(Ar_0, Ar_1, Fresh_0, Ar_0 - 1, Ar_4)) (Comp: 4*Ar_1^2 + 69*Ar_1, Cost: 1) evalinsertsortbb3in(Ar_0, Ar_1, Ar_2, Ar_3, Ar_4) -> Com_1(evalinsertsortbb4in(Ar_0, Ar_1, Ar_2, Ar_3, Ar_4)) [ Ar_3 >= 0 ] (Comp: 4*Ar_1, Cost: 1) evalinsertsortbb3in(Ar_0, Ar_1, Ar_2, Ar_3, Ar_4) -> Com_1(evalinsertsortbb6in(Ar_0, Ar_1, Ar_2, Ar_3, Ar_4)) [ 0 >= Ar_3 + 1 ] (Comp: ?, Cost: 1) evalinsertsortbb4in(Ar_0, Ar_1, Ar_2, Ar_3, Ar_4) -> Com_1(evalinsertsortbb5in(Ar_0, Ar_1, Ar_2, Ar_3, Ar_4)) [ F >= Ar_2 + 1 ] (Comp: 4*Ar_1, Cost: 1) evalinsertsortbb4in(Ar_0, Ar_1, Ar_2, Ar_3, Ar_4) -> Com_1(evalinsertsortbb6in(Ar_0, Ar_1, Ar_2, Ar_3, Ar_4)) [ Ar_2 >= F ] (Comp: ?, Cost: 1) evalinsertsortbb5in(Ar_0, Ar_1, Ar_2, Ar_3, Ar_4) -> Com_1(evalinsertsortbb3in(Ar_0, Ar_1, Ar_2, Ar_3 - 1, Ar_4)) (Comp: 4*Ar_1, Cost: 1) evalinsertsortbb6in(Ar_0, Ar_1, Ar_2, Ar_3, Ar_4) -> Com_1(evalinsertsort25(Ar_0, Ar_1, Ar_2, Ar_3, Ar_0 + 1)) (Comp: 4*Ar_1, Cost: 1) evalinsertsort25(Ar_0, Ar_1, Ar_2, Ar_3, Ar_4) -> Com_1(evalinsertsort26(Ar_0, Ar_1, Ar_2, Ar_3, Ar_4)) (Comp: 4*Ar_1, Cost: 1) evalinsertsort26(Ar_0, Ar_1, Ar_2, Ar_3, Ar_4) -> Com_1(evalinsertsortbb1in(Ar_4, Ar_1, Ar_2, Ar_3, Ar_4)) (Comp: 2, Cost: 1) evalinsertsortbb7in(Ar_0, Ar_1, Ar_2, Ar_3, Ar_4) -> Com_1(evalinsertsortstop(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(evalinsertsortstart(Ar_0, Ar_1, Ar_2, Ar_3, Ar_4)) [ 0 <= 0 ] start location: koat_start leaf cost: 0 Repeatedly propagating knowledge in problem 7 produces the following problem: 8: T: (Comp: 1, Cost: 1) evalinsertsortstart(Ar_0, Ar_1, Ar_2, Ar_3, Ar_4) -> Com_1(evalinsertsortbb0in(Ar_0, Ar_1, Ar_2, Ar_3, Ar_4)) (Comp: 1, Cost: 1) evalinsertsortbb0in(Ar_0, Ar_1, Ar_2, Ar_3, Ar_4) -> Com_1(evalinsertsort0(Ar_0, Ar_1, Ar_2, Ar_3, Ar_4)) (Comp: 1, Cost: 1) evalinsertsort0(Ar_0, Ar_1, Ar_2, Ar_3, Ar_4) -> Com_1(evalinsertsort1(Ar_0, Ar_1, Ar_2, Ar_3, Ar_4)) (Comp: 1, Cost: 1) evalinsertsort1(Ar_0, Ar_1, Ar_2, Ar_3, Ar_4) -> Com_1(evalinsertsort2(Ar_0, Ar_1, Ar_2, Ar_3, Ar_4)) (Comp: 1, Cost: 1) evalinsertsort2(Ar_0, Ar_1, Ar_2, Ar_3, Ar_4) -> Com_1(evalinsertsort3(Ar_0, Ar_1, Ar_2, Ar_3, Ar_4)) (Comp: 1, Cost: 1) evalinsertsort3(Ar_0, Ar_1, Ar_2, Ar_3, Ar_4) -> Com_1(evalinsertsort4(Ar_0, Ar_1, Ar_2, Ar_3, Ar_4)) (Comp: 1, Cost: 1) evalinsertsort4(Ar_0, Ar_1, Ar_2, Ar_3, Ar_4) -> Com_1(evalinsertsort5(Ar_0, Ar_1, Ar_2, Ar_3, Ar_4)) (Comp: 1, Cost: 1) evalinsertsort5(Ar_0, Ar_1, Ar_2, Ar_3, Ar_4) -> Com_1(evalinsertsort6(Ar_0, Ar_1, Ar_2, Ar_3, Ar_4)) (Comp: 1, Cost: 1) evalinsertsort6(Ar_0, Ar_1, Ar_2, Ar_3, Ar_4) -> Com_1(evalinsertsortbb1in(1, Ar_1, Ar_2, Ar_3, Ar_4)) (Comp: Ar_1, Cost: 1) evalinsertsortbb1in(Ar_0, Ar_1, Ar_2, Ar_3, Ar_4) -> Com_1(evalinsertsortbb2in(Ar_0, Ar_1, Ar_2, Ar_3, Ar_4)) [ Ar_1 >= Ar_0 + 1 ] (Comp: 2, Cost: 1) evalinsertsortbb1in(Ar_0, Ar_1, Ar_2, Ar_3, Ar_4) -> Com_1(evalinsertsortbb7in(Ar_0, Ar_1, Ar_2, Ar_3, Ar_4)) [ Ar_0 >= Ar_1 ] (Comp: Ar_1, Cost: 1) evalinsertsortbb2in(Ar_0, Ar_1, Ar_2, Ar_3, Ar_4) -> Com_1(evalinsertsortbb3in(Ar_0, Ar_1, Fresh_0, Ar_0 - 1, Ar_4)) (Comp: 4*Ar_1^2 + 69*Ar_1, Cost: 1) evalinsertsortbb3in(Ar_0, Ar_1, Ar_2, Ar_3, Ar_4) -> Com_1(evalinsertsortbb4in(Ar_0, Ar_1, Ar_2, Ar_3, Ar_4)) [ Ar_3 >= 0 ] (Comp: 4*Ar_1, Cost: 1) evalinsertsortbb3in(Ar_0, Ar_1, Ar_2, Ar_3, Ar_4) -> Com_1(evalinsertsortbb6in(Ar_0, Ar_1, Ar_2, Ar_3, Ar_4)) [ 0 >= Ar_3 + 1 ] (Comp: 4*Ar_1^2 + 69*Ar_1, Cost: 1) evalinsertsortbb4in(Ar_0, Ar_1, Ar_2, Ar_3, Ar_4) -> Com_1(evalinsertsortbb5in(Ar_0, Ar_1, Ar_2, Ar_3, Ar_4)) [ F >= Ar_2 + 1 ] (Comp: 4*Ar_1, Cost: 1) evalinsertsortbb4in(Ar_0, Ar_1, Ar_2, Ar_3, Ar_4) -> Com_1(evalinsertsortbb6in(Ar_0, Ar_1, Ar_2, Ar_3, Ar_4)) [ Ar_2 >= F ] (Comp: 4*Ar_1^2 + 69*Ar_1, Cost: 1) evalinsertsortbb5in(Ar_0, Ar_1, Ar_2, Ar_3, Ar_4) -> Com_1(evalinsertsortbb3in(Ar_0, Ar_1, Ar_2, Ar_3 - 1, Ar_4)) (Comp: 4*Ar_1, Cost: 1) evalinsertsortbb6in(Ar_0, Ar_1, Ar_2, Ar_3, Ar_4) -> Com_1(evalinsertsort25(Ar_0, Ar_1, Ar_2, Ar_3, Ar_0 + 1)) (Comp: 4*Ar_1, Cost: 1) evalinsertsort25(Ar_0, Ar_1, Ar_2, Ar_3, Ar_4) -> Com_1(evalinsertsort26(Ar_0, Ar_1, Ar_2, Ar_3, Ar_4)) (Comp: 4*Ar_1, Cost: 1) evalinsertsort26(Ar_0, Ar_1, Ar_2, Ar_3, Ar_4) -> Com_1(evalinsertsortbb1in(Ar_4, Ar_1, Ar_2, Ar_3, Ar_4)) (Comp: 2, Cost: 1) evalinsertsortbb7in(Ar_0, Ar_1, Ar_2, Ar_3, Ar_4) -> Com_1(evalinsertsortstop(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(evalinsertsortstart(Ar_0, Ar_1, Ar_2, Ar_3, Ar_4)) [ 0 <= 0 ] start location: koat_start leaf cost: 0 Complexity upper bound 229*Ar_1 + 12*Ar_1^2 + 13 Time: 0.223 sec (SMT: 0.137 sec) ---------------------------------------- (2) BOUNDS(1, n^2) ---------------------------------------- (3) Loat Proof (FINISHED) ### Pre-processing the ITS problem ### Initial linear ITS problem Start location: evalinsertsortstart 0: evalinsertsortstart -> evalinsertsortbb0in : [], cost: 1 1: evalinsertsortbb0in -> evalinsertsort0 : [], cost: 1 2: evalinsertsort0 -> evalinsertsort1 : [], cost: 1 3: evalinsertsort1 -> evalinsertsort2 : [], cost: 1 4: evalinsertsort2 -> evalinsertsort3 : [], cost: 1 5: evalinsertsort3 -> evalinsertsort4 : [], cost: 1 6: evalinsertsort4 -> evalinsertsort5 : [], cost: 1 7: evalinsertsort5 -> evalinsertsort6 : [], cost: 1 8: evalinsertsort6 -> evalinsertsortbb1in : A'=1, [], cost: 1 9: evalinsertsortbb1in -> evalinsertsortbb2in : [ B>=1+A ], cost: 1 10: evalinsertsortbb1in -> evalinsertsortbb7in : [ A>=B ], cost: 1 11: evalinsertsortbb2in -> evalinsertsortbb3in : C'=free, D'=-1+A, [], cost: 1 12: evalinsertsortbb3in -> evalinsertsortbb4in : [ D>=0 ], cost: 1 13: evalinsertsortbb3in -> evalinsertsortbb6in : [ 0>=1+D ], cost: 1 14: evalinsertsortbb4in -> evalinsertsortbb5in : [ free_1>=1+C ], cost: 1 15: evalinsertsortbb4in -> evalinsertsortbb6in : [ C>=free_2 ], cost: 1 16: evalinsertsortbb5in -> evalinsertsortbb3in : D'=-1+D, [], cost: 1 17: evalinsertsortbb6in -> evalinsertsort25 : E'=1+A, [], cost: 1 18: evalinsertsort25 -> evalinsertsort26 : [], cost: 1 19: evalinsertsort26 -> evalinsertsortbb1in : A'=E, [], cost: 1 20: evalinsertsortbb7in -> evalinsertsortstop : [], cost: 1 Checking for constant complexity: The following rule is satisfiable with cost >= 1, yielding constant complexity: 0: evalinsertsortstart -> evalinsertsortbb0in : [], cost: 1 Removed unreachable and leaf rules: Start location: evalinsertsortstart 0: evalinsertsortstart -> evalinsertsortbb0in : [], cost: 1 1: evalinsertsortbb0in -> evalinsertsort0 : [], cost: 1 2: evalinsertsort0 -> evalinsertsort1 : [], cost: 1 3: evalinsertsort1 -> evalinsertsort2 : [], cost: 1 4: evalinsertsort2 -> evalinsertsort3 : [], cost: 1 5: evalinsertsort3 -> evalinsertsort4 : [], cost: 1 6: evalinsertsort4 -> evalinsertsort5 : [], cost: 1 7: evalinsertsort5 -> evalinsertsort6 : [], cost: 1 8: evalinsertsort6 -> evalinsertsortbb1in : A'=1, [], cost: 1 9: evalinsertsortbb1in -> evalinsertsortbb2in : [ B>=1+A ], cost: 1 11: evalinsertsortbb2in -> evalinsertsortbb3in : C'=free, D'=-1+A, [], cost: 1 12: evalinsertsortbb3in -> evalinsertsortbb4in : [ D>=0 ], cost: 1 13: evalinsertsortbb3in -> evalinsertsortbb6in : [ 0>=1+D ], cost: 1 14: evalinsertsortbb4in -> evalinsertsortbb5in : [ free_1>=1+C ], cost: 1 15: evalinsertsortbb4in -> evalinsertsortbb6in : [ C>=free_2 ], cost: 1 16: evalinsertsortbb5in -> evalinsertsortbb3in : D'=-1+D, [], cost: 1 17: evalinsertsortbb6in -> evalinsertsort25 : E'=1+A, [], cost: 1 18: evalinsertsort25 -> evalinsertsort26 : [], cost: 1 19: evalinsertsort26 -> evalinsertsortbb1in : A'=E, [], cost: 1 Simplified all rules, resulting in: Start location: evalinsertsortstart 0: evalinsertsortstart -> evalinsertsortbb0in : [], cost: 1 1: evalinsertsortbb0in -> evalinsertsort0 : [], cost: 1 2: evalinsertsort0 -> evalinsertsort1 : [], cost: 1 3: evalinsertsort1 -> evalinsertsort2 : [], cost: 1 4: evalinsertsort2 -> evalinsertsort3 : [], cost: 1 5: evalinsertsort3 -> evalinsertsort4 : [], cost: 1 6: evalinsertsort4 -> evalinsertsort5 : [], cost: 1 7: evalinsertsort5 -> evalinsertsort6 : [], cost: 1 8: evalinsertsort6 -> evalinsertsortbb1in : A'=1, [], cost: 1 9: evalinsertsortbb1in -> evalinsertsortbb2in : [ B>=1+A ], cost: 1 11: evalinsertsortbb2in -> evalinsertsortbb3in : C'=free, D'=-1+A, [], cost: 1 12: evalinsertsortbb3in -> evalinsertsortbb4in : [ D>=0 ], cost: 1 13: evalinsertsortbb3in -> evalinsertsortbb6in : [ 0>=1+D ], cost: 1 14: evalinsertsortbb4in -> evalinsertsortbb5in : [], cost: 1 15: evalinsertsortbb4in -> evalinsertsortbb6in : [], cost: 1 16: evalinsertsortbb5in -> evalinsertsortbb3in : D'=-1+D, [], cost: 1 17: evalinsertsortbb6in -> evalinsertsort25 : E'=1+A, [], cost: 1 18: evalinsertsort25 -> evalinsertsort26 : [], cost: 1 19: evalinsertsort26 -> evalinsertsortbb1in : A'=E, [], cost: 1 ### Simplification by acceleration and chaining ### Eliminated locations (on linear paths): Start location: evalinsertsortstart 28: evalinsertsortstart -> evalinsertsortbb1in : A'=1, [], cost: 9 29: evalinsertsortbb1in -> evalinsertsortbb3in : C'=free, D'=-1+A, [ B>=1+A ], cost: 2 12: evalinsertsortbb3in -> evalinsertsortbb4in : [ D>=0 ], cost: 1 13: evalinsertsortbb3in -> evalinsertsortbb6in : [ 0>=1+D ], cost: 1 15: evalinsertsortbb4in -> evalinsertsortbb6in : [], cost: 1 30: evalinsertsortbb4in -> evalinsertsortbb3in : D'=-1+D, [], cost: 2 32: evalinsertsortbb6in -> evalinsertsortbb1in : A'=1+A, E'=1+A, [], cost: 3 Eliminated locations (on tree-shaped paths): Start location: evalinsertsortstart 28: evalinsertsortstart -> evalinsertsortbb1in : A'=1, [], cost: 9 29: evalinsertsortbb1in -> evalinsertsortbb3in : C'=free, D'=-1+A, [ B>=1+A ], cost: 2 34: evalinsertsortbb3in -> evalinsertsortbb3in : D'=-1+D, [ D>=0 ], cost: 3 35: evalinsertsortbb3in -> evalinsertsortbb1in : A'=1+A, E'=1+A, [ 0>=1+D ], cost: 4 36: evalinsertsortbb3in -> evalinsertsortbb1in : A'=1+A, E'=1+A, [ D>=0 ], cost: 5 Accelerating simple loops of location 11. Accelerating the following rules: 34: evalinsertsortbb3in -> evalinsertsortbb3in : D'=-1+D, [ D>=0 ], cost: 3 Accelerated rule 34 with metering function 1+D, yielding the new rule 37. Removing the simple loops: 34. Accelerated all simple loops using metering functions (where possible): Start location: evalinsertsortstart 28: evalinsertsortstart -> evalinsertsortbb1in : A'=1, [], cost: 9 29: evalinsertsortbb1in -> evalinsertsortbb3in : C'=free, D'=-1+A, [ B>=1+A ], cost: 2 35: evalinsertsortbb3in -> evalinsertsortbb1in : A'=1+A, E'=1+A, [ 0>=1+D ], cost: 4 36: evalinsertsortbb3in -> evalinsertsortbb1in : A'=1+A, E'=1+A, [ D>=0 ], cost: 5 37: evalinsertsortbb3in -> evalinsertsortbb3in : D'=-1, [ D>=0 ], cost: 3+3*D Chained accelerated rules (with incoming rules): Start location: evalinsertsortstart 28: evalinsertsortstart -> evalinsertsortbb1in : A'=1, [], cost: 9 29: evalinsertsortbb1in -> evalinsertsortbb3in : C'=free, D'=-1+A, [ B>=1+A ], cost: 2 38: evalinsertsortbb1in -> evalinsertsortbb3in : C'=free, D'=-1, [ B>=1+A && -1+A>=0 ], cost: 2+3*A 35: evalinsertsortbb3in -> evalinsertsortbb1in : A'=1+A, E'=1+A, [ 0>=1+D ], cost: 4 36: evalinsertsortbb3in -> evalinsertsortbb1in : A'=1+A, E'=1+A, [ D>=0 ], cost: 5 Eliminated locations (on tree-shaped paths): Start location: evalinsertsortstart 28: evalinsertsortstart -> evalinsertsortbb1in : A'=1, [], cost: 9 39: evalinsertsortbb1in -> evalinsertsortbb1in : A'=1+A, C'=free, D'=-1+A, E'=1+A, [ B>=1+A && 0>=A ], cost: 6 40: evalinsertsortbb1in -> evalinsertsortbb1in : A'=1+A, C'=free, D'=-1+A, E'=1+A, [ B>=1+A && -1+A>=0 ], cost: 7 41: evalinsertsortbb1in -> evalinsertsortbb1in : A'=1+A, C'=free, D'=-1, E'=1+A, [ B>=1+A && -1+A>=0 ], cost: 6+3*A 42: evalinsertsortbb1in -> [20] : [ B>=1+A && -1+A>=0 ], cost: 2+3*A Accelerating simple loops of location 9. Accelerating the following rules: 39: evalinsertsortbb1in -> evalinsertsortbb1in : A'=1+A, C'=free, D'=-1+A, E'=1+A, [ B>=1+A && 0>=A ], cost: 6 40: evalinsertsortbb1in -> evalinsertsortbb1in : A'=1+A, C'=free, D'=-1+A, E'=1+A, [ B>=1+A && -1+A>=0 ], cost: 7 41: evalinsertsortbb1in -> evalinsertsortbb1in : A'=1+A, C'=free, D'=-1, E'=1+A, [ B>=1+A && -1+A>=0 ], cost: 6+3*A Found no metering function for rule 39. Accelerated rule 40 with metering function -A+B, yielding the new rule 43. Accelerated rule 41 with metering function -A+B, yielding the new rule 44. Removing the simple loops: 40 41. Accelerated all simple loops using metering functions (where possible): Start location: evalinsertsortstart 28: evalinsertsortstart -> evalinsertsortbb1in : A'=1, [], cost: 9 39: evalinsertsortbb1in -> evalinsertsortbb1in : A'=1+A, C'=free, D'=-1+A, E'=1+A, [ B>=1+A && 0>=A ], cost: 6 42: evalinsertsortbb1in -> [20] : [ B>=1+A && -1+A>=0 ], cost: 2+3*A 43: evalinsertsortbb1in -> evalinsertsortbb1in : A'=B, C'=free, D'=-2+B, E'=B, [ B>=1+A && -1+A>=0 ], cost: -7*A+7*B 44: evalinsertsortbb1in -> evalinsertsortbb1in : A'=B, C'=free, D'=-1, E'=B, [ B>=1+A && -1+A>=0 ], cost: 3/2*(A-B)^2-9/2*A-3*A*(A-B)+9/2*B Chained accelerated rules (with incoming rules): Start location: evalinsertsortstart 28: evalinsertsortstart -> evalinsertsortbb1in : A'=1, [], cost: 9 45: evalinsertsortstart -> evalinsertsortbb1in : A'=B, C'=free, D'=-2+B, E'=B, [ B>=2 ], cost: 2+7*B 46: evalinsertsortstart -> evalinsertsortbb1in : A'=B, C'=free, D'=-1, E'=B, [ B>=2 ], cost: 3/2+15/2*B+3/2*(-1+B)^2 42: evalinsertsortbb1in -> [20] : [ B>=1+A && -1+A>=0 ], cost: 2+3*A Eliminated locations (on tree-shaped paths): Start location: evalinsertsortstart 47: evalinsertsortstart -> [20] : A'=1, [ B>=2 ], cost: 14 48: evalinsertsortstart -> [22] : [ B>=2 ], cost: 2+7*B 49: evalinsertsortstart -> [22] : [ B>=2 ], cost: 3/2+15/2*B+3/2*(-1+B)^2 Applied pruning (of leafs and parallel rules): Start location: evalinsertsortstart 48: evalinsertsortstart -> [22] : [ B>=2 ], cost: 2+7*B 49: evalinsertsortstart -> [22] : [ B>=2 ], cost: 3/2+15/2*B+3/2*(-1+B)^2 ### Computing asymptotic complexity ### Fully simplified ITS problem Start location: evalinsertsortstart 48: evalinsertsortstart -> [22] : [ B>=2 ], cost: 2+7*B 49: evalinsertsortstart -> [22] : [ B>=2 ], cost: 3/2+15/2*B+3/2*(-1+B)^2 Computing asymptotic complexity for rule 48 Solved the limit problem by the following transformations: Created initial limit problem: -1+B (+/+!), 2+7*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 2+7*n has complexity: Poly(n^1) Found new complexity Poly(n^1). Computing asymptotic complexity for rule 49 Solved the limit problem by the following transformations: Created initial limit problem: 3+9/2*B+3/2*B^2 (+), -1+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 3+3/2*n^2+9/2*n has complexity: Poly(n^2) Found new complexity Poly(n^2). Obtained the following overall complexity (w.r.t. the length of the input n): Complexity: Poly(n^2) Cpx degree: 2 Solved cost: 3+3/2*n^2+9/2*n Rule cost: 3/2+15/2*B+3/2*(-1+B)^2 Rule guard: [ B>=2 ] WORST_CASE(Omega(n^2),?) ---------------------------------------- (4) BOUNDS(n^2, INF)