/export/starexec/sandbox2/solver/bin/starexec_run_complexity /export/starexec/sandbox2/benchmark/theBenchmark.koat /export/starexec/sandbox2/output/output_files -------------------------------------------------------------------------------- WORST_CASE(Omega(n^1), O(n^1)) proof of /export/starexec/sandbox2/benchmark/theBenchmark.koat # AProVE Commit ID: 48fb2092695e11cc9f56e44b17a92a5f88ffb256 marcel 20180622 unpublished dirty The runtime complexity of the given CpxIntTrs could be proven to be BOUNDS(n^1, nat(2 + 6 * Arg_2 + -6 * Arg_4) + nat(3 + 3 * Arg_2 + -3 * Arg_4) + max(5, 6 + Arg_2 + -1 * Arg_4) + max(5 + 2 * Arg_2 + -2 * Arg_4, 4)). (0) CpxIntTrs (1) Koat2 Proof [FINISHED, 3561 ms] (2) BOUNDS(1, nat(2 + 6 * Arg_2 + -6 * Arg_4) + nat(3 + 3 * Arg_2 + -3 * Arg_4) + max(5, 6 + Arg_2 + -1 * Arg_4) + max(5 + 2 * Arg_2 + -2 * Arg_4, 4)) (3) Loat Proof [FINISHED, 7578 ms] (4) BOUNDS(n^1, INF) ---------------------------------------- (0) Obligation: Complexity Int TRS consisting of the following rules: eval_aaron2_start(v__01, v__02, v_3, v_tx, v_x, v_y) -> Com_1(eval_aaron2_bb0_in(v__01, v__02, v_3, v_tx, v_x, v_y)) :|: TRUE eval_aaron2_bb0_in(v__01, v__02, v_3, v_tx, v_x, v_y) -> Com_1(eval_aaron2_0(v__01, v__02, v_3, v_tx, v_x, v_y)) :|: TRUE eval_aaron2_0(v__01, v__02, v_3, v_tx, v_x, v_y) -> Com_1(eval_aaron2_1(v__01, v__02, v_3, v_tx, v_x, v_y)) :|: TRUE eval_aaron2_1(v__01, v__02, v_3, v_tx, v_x, v_y) -> Com_1(eval_aaron2_2(v__01, v__02, v_3, v_tx, v_x, v_y)) :|: TRUE eval_aaron2_2(v__01, v__02, v_3, v_tx, v_x, v_y) -> Com_1(eval_aaron2_3(v__01, v__02, v_3, v_tx, v_x, v_y)) :|: TRUE eval_aaron2_3(v__01, v__02, v_3, v_tx, v_x, v_y) -> Com_1(eval_aaron2_bb1_in(v_x, v_y, v_3, v_tx, v_x, v_y)) :|: v_tx >= 0 eval_aaron2_3(v__01, v__02, v_3, v_tx, v_x, v_y) -> Com_1(eval_aaron2_bb5_in(v__01, v__02, v_3, v_tx, v_x, v_y)) :|: v_tx < 0 eval_aaron2_bb1_in(v__01, v__02, v_3, v_tx, v_x, v_y) -> Com_1(eval_aaron2_bb5_in(v__01, v__02, v_3, v_tx, v_x, v_y)) :|: v__01 < v__02 eval_aaron2_bb1_in(v__01, v__02, v_3, v_tx, v_x, v_y) -> Com_1(eval_aaron2_bb5_in(v__01, v__02, v_3, v_tx, v_x, v_y)) :|: v_tx < 0 eval_aaron2_bb1_in(v__01, v__02, v_3, v_tx, v_x, v_y) -> Com_1(eval_aaron2_bb2_in(v__01, v__02, v_3, v_tx, v_x, v_y)) :|: v__01 >= v__02 && v_tx >= 0 eval_aaron2_bb2_in(v__01, v__02, v_3, v_tx, v_x, v_y) -> Com_1(eval_aaron2_4(v__01, v__02, v_3, v_tx, v_x, v_y)) :|: TRUE eval_aaron2_4(v__01, v__02, v_3, v_tx, v_x, v_y) -> Com_1(eval_aaron2_5(v__01, v__02, nondef_0, v_tx, v_x, v_y)) :|: TRUE eval_aaron2_5(v__01, v__02, v_3, v_tx, v_x, v_y) -> Com_1(eval_aaron2_bb3_in(v__01, v__02, v_3, v_tx, v_x, v_y)) :|: v_3 > 0 eval_aaron2_5(v__01, v__02, v_3, v_tx, v_x, v_y) -> Com_1(eval_aaron2_bb4_in(v__01, v__02, v_3, v_tx, v_x, v_y)) :|: v_3 <= 0 eval_aaron2_bb3_in(v__01, v__02, v_3, v_tx, v_x, v_y) -> Com_1(eval_aaron2_bb1_in(v__01 - v_tx - 1, v__02, v_3, v_tx, v_x, v_y)) :|: TRUE eval_aaron2_bb4_in(v__01, v__02, v_3, v_tx, v_x, v_y) -> Com_1(eval_aaron2_bb1_in(v__01, v__02 + v_tx + 1, v_3, v_tx, v_x, v_y)) :|: TRUE eval_aaron2_bb5_in(v__01, v__02, v_3, v_tx, v_x, v_y) -> Com_1(eval_aaron2_stop(v__01, v__02, v_3, v_tx, v_x, v_y)) :|: TRUE The start-symbols are:[eval_aaron2_start_6] ---------------------------------------- (1) Koat2 Proof (FINISHED) YES( ?, 4+max([0, 1+2*Arg_2+-2*Arg_4])+max([0, 1+3*Arg_2+-3*Arg_4])+max([0, 1+3*Arg_2+-3*Arg_4])+max([0, 1+Arg_2-Arg_4])+max([0, 1+Arg_2-Arg_4])+max([5, 6+Arg_2-Arg_4])+max([0, 1+Arg_2-Arg_4]) {O(n)}) Initial Complexity Problem: Start: evalaaron2start Program_Vars: Arg_0, Arg_1, Arg_2, Arg_3, Arg_4, Arg_5 Temp_Vars: G Locations: evalaaron20, evalaaron21, evalaaron22, evalaaron23, evalaaron24, evalaaron25, evalaaron2bb0in, evalaaron2bb1in, evalaaron2bb2in, evalaaron2bb3in, evalaaron2bb4in, evalaaron2bb5in, evalaaron2start, evalaaron2stop Transitions: evalaaron20(Arg_0,Arg_1,Arg_2,Arg_3,Arg_4,Arg_5) -> evalaaron21(Arg_0,Arg_1,Arg_2,Arg_3,Arg_4,Arg_5):|: evalaaron21(Arg_0,Arg_1,Arg_2,Arg_3,Arg_4,Arg_5) -> evalaaron22(Arg_0,Arg_1,Arg_2,Arg_3,Arg_4,Arg_5):|: evalaaron22(Arg_0,Arg_1,Arg_2,Arg_3,Arg_4,Arg_5) -> evalaaron23(Arg_0,Arg_1,Arg_2,Arg_3,Arg_4,Arg_5):|: evalaaron23(Arg_0,Arg_1,Arg_2,Arg_3,Arg_4,Arg_5) -> evalaaron2bb1in(Arg_0,Arg_2,Arg_2,Arg_4,Arg_4,Arg_5):|:0 <= Arg_0 evalaaron23(Arg_0,Arg_1,Arg_2,Arg_3,Arg_4,Arg_5) -> evalaaron2bb5in(Arg_0,Arg_1,Arg_2,Arg_3,Arg_4,Arg_5):|:Arg_0+1 <= 0 evalaaron24(Arg_0,Arg_1,Arg_2,Arg_3,Arg_4,Arg_5) -> evalaaron25(Arg_0,Arg_1,Arg_2,Arg_3,Arg_4,G):|:Arg_4 <= Arg_3 && Arg_4 <= Arg_2 && Arg_4 <= Arg_1 && Arg_3 <= Arg_2 && Arg_3 <= Arg_1 && Arg_1 <= Arg_2 && 0 <= Arg_0 evalaaron25(Arg_0,Arg_1,Arg_2,Arg_3,Arg_4,Arg_5) -> evalaaron2bb3in(Arg_0,Arg_1,Arg_2,Arg_3,Arg_4,Arg_5):|:Arg_4 <= Arg_3 && Arg_4 <= Arg_2 && Arg_4 <= Arg_1 && Arg_3 <= Arg_2 && Arg_3 <= Arg_1 && Arg_1 <= Arg_2 && 0 <= Arg_0 && 1 <= Arg_5 evalaaron25(Arg_0,Arg_1,Arg_2,Arg_3,Arg_4,Arg_5) -> evalaaron2bb4in(Arg_0,Arg_1,Arg_2,Arg_3,Arg_4,Arg_5):|:Arg_4 <= Arg_3 && Arg_4 <= Arg_2 && Arg_4 <= Arg_1 && Arg_3 <= Arg_2 && Arg_3 <= Arg_1 && Arg_1 <= Arg_2 && 0 <= Arg_0 && Arg_5 <= 0 evalaaron2bb0in(Arg_0,Arg_1,Arg_2,Arg_3,Arg_4,Arg_5) -> evalaaron20(Arg_0,Arg_1,Arg_2,Arg_3,Arg_4,Arg_5):|: evalaaron2bb1in(Arg_0,Arg_1,Arg_2,Arg_3,Arg_4,Arg_5) -> evalaaron2bb2in(Arg_0,Arg_1,Arg_2,Arg_3,Arg_4,Arg_5):|:Arg_4 <= Arg_3 && Arg_1 <= Arg_2 && 0 <= Arg_0 && Arg_3 <= Arg_1 && 0 <= Arg_0 evalaaron2bb1in(Arg_0,Arg_1,Arg_2,Arg_3,Arg_4,Arg_5) -> evalaaron2bb5in(Arg_0,Arg_1,Arg_2,Arg_3,Arg_4,Arg_5):|:Arg_4 <= Arg_3 && Arg_1 <= Arg_2 && 0 <= Arg_0 && Arg_1+1 <= Arg_3 evalaaron2bb2in(Arg_0,Arg_1,Arg_2,Arg_3,Arg_4,Arg_5) -> evalaaron24(Arg_0,Arg_1,Arg_2,Arg_3,Arg_4,Arg_5):|:Arg_4 <= Arg_3 && Arg_4 <= Arg_2 && Arg_4 <= Arg_1 && Arg_3 <= Arg_2 && Arg_3 <= Arg_1 && Arg_1 <= Arg_2 && 0 <= Arg_0 evalaaron2bb3in(Arg_0,Arg_1,Arg_2,Arg_3,Arg_4,Arg_5) -> evalaaron2bb1in(Arg_0,Arg_1-Arg_0-1,Arg_2,Arg_3,Arg_4,Arg_5):|:1 <= Arg_5 && 1 <= Arg_0+Arg_5 && Arg_4 <= Arg_3 && Arg_4 <= Arg_2 && Arg_4 <= Arg_1 && Arg_3 <= Arg_2 && Arg_3 <= Arg_1 && Arg_1 <= Arg_2 && 0 <= Arg_0 evalaaron2bb4in(Arg_0,Arg_1,Arg_2,Arg_3,Arg_4,Arg_5) -> evalaaron2bb1in(Arg_0,Arg_1,Arg_2,Arg_3+Arg_0+1,Arg_4,Arg_5):|:Arg_5 <= 0 && Arg_5 <= Arg_0 && Arg_4 <= Arg_3 && Arg_4 <= Arg_2 && Arg_4 <= Arg_1 && Arg_3 <= Arg_2 && Arg_3 <= Arg_1 && Arg_1 <= Arg_2 && 0 <= Arg_0 evalaaron2bb5in(Arg_0,Arg_1,Arg_2,Arg_3,Arg_4,Arg_5) -> evalaaron2stop(Arg_0,Arg_1,Arg_2,Arg_3,Arg_4,Arg_5):|: evalaaron2start(Arg_0,Arg_1,Arg_2,Arg_3,Arg_4,Arg_5) -> evalaaron2bb0in(Arg_0,Arg_1,Arg_2,Arg_3,Arg_4,Arg_5):|: Timebounds: Overall timebound: 4+max([0, 1+2*Arg_2+-2*Arg_4])+max([0, 1+3*Arg_2+-3*Arg_4])+max([0, 1+3*Arg_2+-3*Arg_4])+max([0, 1+Arg_2-Arg_4])+max([0, 1+Arg_2-Arg_4])+max([5, 6+Arg_2-Arg_4])+max([0, 1+Arg_2-Arg_4]) {O(n)} 2: evalaaron20->evalaaron21: 1 {O(1)} 3: evalaaron21->evalaaron22: 1 {O(1)} 4: evalaaron22->evalaaron23: 1 {O(1)} 5: evalaaron23->evalaaron2bb1in: 1 {O(1)} 6: evalaaron23->evalaaron2bb5in: 1 {O(1)} 11: evalaaron24->evalaaron25: max([0, 1+Arg_2-Arg_4]) {O(n)} 12: evalaaron25->evalaaron2bb3in: max([0, 1+Arg_2-Arg_4]) {O(n)} 13: evalaaron25->evalaaron2bb4in: max([0, 1+3*Arg_2+-3*Arg_4]) {O(n)} 1: evalaaron2bb0in->evalaaron20: 1 {O(1)} 7: evalaaron2bb1in->evalaaron2bb5in: 1 {O(1)} 9: evalaaron2bb1in->evalaaron2bb2in: max([0, 1+Arg_2-Arg_4]) {O(n)} 10: evalaaron2bb2in->evalaaron24: max([0, 1+Arg_2-Arg_4]) {O(n)} 14: evalaaron2bb3in->evalaaron2bb1in: max([0, 1+3*Arg_2+-3*Arg_4]) {O(n)} 15: evalaaron2bb4in->evalaaron2bb1in: max([0, 1+2*Arg_2+-2*Arg_4]) {O(n)} 16: evalaaron2bb5in->evalaaron2stop: 1 {O(1)} 0: evalaaron2start->evalaaron2bb0in: 1 {O(1)} Costbounds: Overall costbound: 4+max([0, 1+2*Arg_2+-2*Arg_4])+max([0, 1+3*Arg_2+-3*Arg_4])+max([0, 1+3*Arg_2+-3*Arg_4])+max([0, 1+Arg_2-Arg_4])+max([0, 1+Arg_2-Arg_4])+max([5, 6+Arg_2-Arg_4])+max([0, 1+Arg_2-Arg_4]) {O(n)} 2: evalaaron20->evalaaron21: 1 {O(1)} 3: evalaaron21->evalaaron22: 1 {O(1)} 4: evalaaron22->evalaaron23: 1 {O(1)} 5: evalaaron23->evalaaron2bb1in: 1 {O(1)} 6: evalaaron23->evalaaron2bb5in: 1 {O(1)} 11: evalaaron24->evalaaron25: max([0, 1+Arg_2-Arg_4]) {O(n)} 12: evalaaron25->evalaaron2bb3in: max([0, 1+Arg_2-Arg_4]) {O(n)} 13: evalaaron25->evalaaron2bb4in: max([0, 1+3*Arg_2+-3*Arg_4]) {O(n)} 1: evalaaron2bb0in->evalaaron20: 1 {O(1)} 7: evalaaron2bb1in->evalaaron2bb5in: 1 {O(1)} 9: evalaaron2bb1in->evalaaron2bb2in: max([0, 1+Arg_2-Arg_4]) {O(n)} 10: evalaaron2bb2in->evalaaron24: max([0, 1+Arg_2-Arg_4]) {O(n)} 14: evalaaron2bb3in->evalaaron2bb1in: max([0, 1+3*Arg_2+-3*Arg_4]) {O(n)} 15: evalaaron2bb4in->evalaaron2bb1in: max([0, 1+2*Arg_2+-2*Arg_4]) {O(n)} 16: evalaaron2bb5in->evalaaron2stop: 1 {O(1)} 0: evalaaron2start->evalaaron2bb0in: 1 {O(1)} Sizebounds: `Lower: 2: evalaaron20->evalaaron21, Arg_0: Arg_0 {O(n)} 2: evalaaron20->evalaaron21, Arg_1: Arg_1 {O(n)} 2: evalaaron20->evalaaron21, Arg_2: Arg_2 {O(n)} 2: evalaaron20->evalaaron21, Arg_3: Arg_3 {O(n)} 2: evalaaron20->evalaaron21, Arg_4: Arg_4 {O(n)} 2: evalaaron20->evalaaron21, Arg_5: Arg_5 {O(n)} 3: evalaaron21->evalaaron22, Arg_0: Arg_0 {O(n)} 3: evalaaron21->evalaaron22, Arg_1: Arg_1 {O(n)} 3: evalaaron21->evalaaron22, Arg_2: Arg_2 {O(n)} 3: evalaaron21->evalaaron22, Arg_3: Arg_3 {O(n)} 3: evalaaron21->evalaaron22, Arg_4: Arg_4 {O(n)} 3: evalaaron21->evalaaron22, Arg_5: Arg_5 {O(n)} 4: evalaaron22->evalaaron23, Arg_0: Arg_0 {O(n)} 4: evalaaron22->evalaaron23, Arg_1: Arg_1 {O(n)} 4: evalaaron22->evalaaron23, Arg_2: Arg_2 {O(n)} 4: evalaaron22->evalaaron23, Arg_3: Arg_3 {O(n)} 4: evalaaron22->evalaaron23, Arg_4: Arg_4 {O(n)} 4: evalaaron22->evalaaron23, Arg_5: Arg_5 {O(n)} 5: evalaaron23->evalaaron2bb1in, Arg_0: 0 {O(1)} 5: evalaaron23->evalaaron2bb1in, Arg_1: Arg_2 {O(n)} 5: evalaaron23->evalaaron2bb1in, Arg_2: Arg_2 {O(n)} 5: evalaaron23->evalaaron2bb1in, Arg_3: Arg_4 {O(n)} 5: evalaaron23->evalaaron2bb1in, Arg_4: Arg_4 {O(n)} 5: evalaaron23->evalaaron2bb1in, Arg_5: Arg_5 {O(n)} 6: evalaaron23->evalaaron2bb5in, Arg_0: Arg_0 {O(n)} 6: evalaaron23->evalaaron2bb5in, Arg_1: Arg_1 {O(n)} 6: evalaaron23->evalaaron2bb5in, Arg_2: Arg_2 {O(n)} 6: evalaaron23->evalaaron2bb5in, Arg_3: Arg_3 {O(n)} 6: evalaaron23->evalaaron2bb5in, Arg_4: Arg_4 {O(n)} 6: evalaaron23->evalaaron2bb5in, Arg_5: Arg_5 {O(n)} 11: evalaaron24->evalaaron25, Arg_0: 0 {O(1)} 11: evalaaron24->evalaaron25, Arg_1: min([0, Arg_2])-max([0, (1+3*Arg_2+-3*Arg_4)*max([1, 1+Arg_0])]) {O(n^2)} 11: evalaaron24->evalaaron25, Arg_2: Arg_2 {O(n)} 11: evalaaron24->evalaaron25, Arg_3: Arg_4 {O(n)} 11: evalaaron24->evalaaron25, Arg_4: Arg_4 {O(n)} 12: evalaaron25->evalaaron2bb3in, Arg_0: 0 {O(1)} 12: evalaaron25->evalaaron2bb3in, Arg_1: min([0, Arg_2])-max([0, (1+3*Arg_2+-3*Arg_4)*max([1, 1+Arg_0])]) {O(n^2)} 12: evalaaron25->evalaaron2bb3in, Arg_2: Arg_2 {O(n)} 12: evalaaron25->evalaaron2bb3in, Arg_3: Arg_4 {O(n)} 12: evalaaron25->evalaaron2bb3in, Arg_4: Arg_4 {O(n)} 12: evalaaron25->evalaaron2bb3in, Arg_5: 1 {O(1)} 13: evalaaron25->evalaaron2bb4in, Arg_0: 0 {O(1)} 13: evalaaron25->evalaaron2bb4in, Arg_1: min([0, Arg_2])-max([0, (1+3*Arg_2+-3*Arg_4)*max([1, 1+Arg_0])]) {O(n^2)} 13: evalaaron25->evalaaron2bb4in, Arg_2: Arg_2 {O(n)} 13: evalaaron25->evalaaron2bb4in, Arg_3: Arg_4 {O(n)} 13: evalaaron25->evalaaron2bb4in, Arg_4: Arg_4 {O(n)} 1: evalaaron2bb0in->evalaaron20, Arg_0: Arg_0 {O(n)} 1: evalaaron2bb0in->evalaaron20, Arg_1: Arg_1 {O(n)} 1: evalaaron2bb0in->evalaaron20, Arg_2: Arg_2 {O(n)} 1: evalaaron2bb0in->evalaaron20, Arg_3: Arg_3 {O(n)} 1: evalaaron2bb0in->evalaaron20, Arg_4: Arg_4 {O(n)} 1: evalaaron2bb0in->evalaaron20, Arg_5: Arg_5 {O(n)} 7: evalaaron2bb1in->evalaaron2bb5in, Arg_0: 0 {O(1)} 7: evalaaron2bb1in->evalaaron2bb5in, Arg_1: min([Arg_2, -(max([0, -(Arg_2)])+max([0, (1+3*Arg_2+-3*Arg_4)*max([1, 1+Arg_0])]))]) {O(n^2)} 7: evalaaron2bb1in->evalaaron2bb5in, Arg_2: Arg_2 {O(n)} 7: evalaaron2bb1in->evalaaron2bb5in, Arg_3: Arg_4 {O(n)} 7: evalaaron2bb1in->evalaaron2bb5in, Arg_4: Arg_4 {O(n)} 9: evalaaron2bb1in->evalaaron2bb2in, Arg_0: 0 {O(1)} 9: evalaaron2bb1in->evalaaron2bb2in, Arg_1: min([0, Arg_2])-max([0, (1+3*Arg_2+-3*Arg_4)*max([1, 1+Arg_0])]) {O(n^2)} 9: evalaaron2bb1in->evalaaron2bb2in, Arg_2: Arg_2 {O(n)} 9: evalaaron2bb1in->evalaaron2bb2in, Arg_3: Arg_4 {O(n)} 9: evalaaron2bb1in->evalaaron2bb2in, Arg_4: Arg_4 {O(n)} 10: evalaaron2bb2in->evalaaron24, Arg_0: 0 {O(1)} 10: evalaaron2bb2in->evalaaron24, Arg_1: min([0, Arg_2])-max([0, (1+3*Arg_2+-3*Arg_4)*max([1, 1+Arg_0])]) {O(n^2)} 10: evalaaron2bb2in->evalaaron24, Arg_2: Arg_2 {O(n)} 10: evalaaron2bb2in->evalaaron24, Arg_3: Arg_4 {O(n)} 10: evalaaron2bb2in->evalaaron24, Arg_4: Arg_4 {O(n)} 14: evalaaron2bb3in->evalaaron2bb1in, Arg_0: 0 {O(1)} 14: evalaaron2bb3in->evalaaron2bb1in, Arg_1: min([0, Arg_2])-max([0, (1+3*Arg_2+-3*Arg_4)*max([1, 1+Arg_0])]) {O(n^2)} 14: evalaaron2bb3in->evalaaron2bb1in, Arg_2: Arg_2 {O(n)} 14: evalaaron2bb3in->evalaaron2bb1in, Arg_3: Arg_4 {O(n)} 14: evalaaron2bb3in->evalaaron2bb1in, Arg_4: Arg_4 {O(n)} 14: evalaaron2bb3in->evalaaron2bb1in, Arg_5: 1 {O(1)} 15: evalaaron2bb4in->evalaaron2bb1in, Arg_0: 0 {O(1)} 15: evalaaron2bb4in->evalaaron2bb1in, Arg_1: min([0, Arg_2])-max([0, (1+3*Arg_2+-3*Arg_4)*max([1, 1+Arg_0])]) {O(n^2)} 15: evalaaron2bb4in->evalaaron2bb1in, Arg_2: Arg_2 {O(n)} 15: evalaaron2bb4in->evalaaron2bb1in, Arg_3: Arg_4 {O(n)} 15: evalaaron2bb4in->evalaaron2bb1in, Arg_4: Arg_4 {O(n)} 16: evalaaron2bb5in->evalaaron2stop, Arg_0: min([0, Arg_0]) {O(n)} 16: evalaaron2bb5in->evalaaron2stop, Arg_1: min([Arg_2, min([Arg_1, -(max([0, -(Arg_2)])+max([0, (1+3*Arg_2+-3*Arg_4)*max([1, 1+Arg_0])]))])]) {O(n^2)} 16: evalaaron2bb5in->evalaaron2stop, Arg_2: Arg_2 {O(n)} 16: evalaaron2bb5in->evalaaron2stop, Arg_3: min([Arg_4, Arg_3]) {O(n)} 16: evalaaron2bb5in->evalaaron2stop, Arg_4: Arg_4 {O(n)} 0: evalaaron2start->evalaaron2bb0in, Arg_0: Arg_0 {O(n)} 0: evalaaron2start->evalaaron2bb0in, Arg_1: Arg_1 {O(n)} 0: evalaaron2start->evalaaron2bb0in, Arg_2: Arg_2 {O(n)} 0: evalaaron2start->evalaaron2bb0in, Arg_3: Arg_3 {O(n)} 0: evalaaron2start->evalaaron2bb0in, Arg_4: Arg_4 {O(n)} 0: evalaaron2start->evalaaron2bb0in, Arg_5: Arg_5 {O(n)} `Upper: 2: evalaaron20->evalaaron21, Arg_0: Arg_0 {O(n)} 2: evalaaron20->evalaaron21, Arg_1: Arg_1 {O(n)} 2: evalaaron20->evalaaron21, Arg_2: Arg_2 {O(n)} 2: evalaaron20->evalaaron21, Arg_3: Arg_3 {O(n)} 2: evalaaron20->evalaaron21, Arg_4: Arg_4 {O(n)} 2: evalaaron20->evalaaron21, Arg_5: Arg_5 {O(n)} 3: evalaaron21->evalaaron22, Arg_0: Arg_0 {O(n)} 3: evalaaron21->evalaaron22, Arg_1: Arg_1 {O(n)} 3: evalaaron21->evalaaron22, Arg_2: Arg_2 {O(n)} 3: evalaaron21->evalaaron22, Arg_3: Arg_3 {O(n)} 3: evalaaron21->evalaaron22, Arg_4: Arg_4 {O(n)} 3: evalaaron21->evalaaron22, Arg_5: Arg_5 {O(n)} 4: evalaaron22->evalaaron23, Arg_0: Arg_0 {O(n)} 4: evalaaron22->evalaaron23, Arg_1: Arg_1 {O(n)} 4: evalaaron22->evalaaron23, Arg_2: Arg_2 {O(n)} 4: evalaaron22->evalaaron23, Arg_3: Arg_3 {O(n)} 4: evalaaron22->evalaaron23, Arg_4: Arg_4 {O(n)} 4: evalaaron22->evalaaron23, Arg_5: Arg_5 {O(n)} 5: evalaaron23->evalaaron2bb1in, Arg_0: Arg_0 {O(n)} 5: evalaaron23->evalaaron2bb1in, Arg_1: Arg_2 {O(n)} 5: evalaaron23->evalaaron2bb1in, Arg_2: Arg_2 {O(n)} 5: evalaaron23->evalaaron2bb1in, Arg_3: Arg_4 {O(n)} 5: evalaaron23->evalaaron2bb1in, Arg_4: Arg_4 {O(n)} 5: evalaaron23->evalaaron2bb1in, Arg_5: Arg_5 {O(n)} 6: evalaaron23->evalaaron2bb5in, Arg_0: -1 {O(1)} 6: evalaaron23->evalaaron2bb5in, Arg_1: Arg_1 {O(n)} 6: evalaaron23->evalaaron2bb5in, Arg_2: Arg_2 {O(n)} 6: evalaaron23->evalaaron2bb5in, Arg_3: Arg_3 {O(n)} 6: evalaaron23->evalaaron2bb5in, Arg_4: Arg_4 {O(n)} 6: evalaaron23->evalaaron2bb5in, Arg_5: Arg_5 {O(n)} 11: evalaaron24->evalaaron25, Arg_0: Arg_0 {O(n)} 11: evalaaron24->evalaaron25, Arg_1: Arg_2 {O(n)} 11: evalaaron24->evalaaron25, Arg_2: Arg_2 {O(n)} 11: evalaaron24->evalaaron25, Arg_3: max([Arg_0, Arg_4])+max([0, (1+2*Arg_2+-2*Arg_4)*max([1, 1+Arg_0])]) {O(n^2)} 11: evalaaron24->evalaaron25, Arg_4: Arg_4 {O(n)} 12: evalaaron25->evalaaron2bb3in, Arg_0: Arg_0 {O(n)} 12: evalaaron25->evalaaron2bb3in, Arg_1: Arg_2 {O(n)} 12: evalaaron25->evalaaron2bb3in, Arg_2: Arg_2 {O(n)} 12: evalaaron25->evalaaron2bb3in, Arg_3: max([Arg_0, Arg_4])+max([0, (1+2*Arg_2+-2*Arg_4)*max([1, 1+Arg_0])]) {O(n^2)} 12: evalaaron25->evalaaron2bb3in, Arg_4: Arg_4 {O(n)} 13: evalaaron25->evalaaron2bb4in, Arg_0: Arg_0 {O(n)} 13: evalaaron25->evalaaron2bb4in, Arg_1: Arg_2 {O(n)} 13: evalaaron25->evalaaron2bb4in, Arg_2: Arg_2 {O(n)} 13: evalaaron25->evalaaron2bb4in, Arg_3: max([Arg_0, Arg_4])+max([0, (1+2*Arg_2+-2*Arg_4)*max([1, 1+Arg_0])]) {O(n^2)} 13: evalaaron25->evalaaron2bb4in, Arg_4: Arg_4 {O(n)} 13: evalaaron25->evalaaron2bb4in, Arg_5: 0 {O(1)} 1: evalaaron2bb0in->evalaaron20, Arg_0: Arg_0 {O(n)} 1: evalaaron2bb0in->evalaaron20, Arg_1: Arg_1 {O(n)} 1: evalaaron2bb0in->evalaaron20, Arg_2: Arg_2 {O(n)} 1: evalaaron2bb0in->evalaaron20, Arg_3: Arg_3 {O(n)} 1: evalaaron2bb0in->evalaaron20, Arg_4: Arg_4 {O(n)} 1: evalaaron2bb0in->evalaaron20, Arg_5: Arg_5 {O(n)} 7: evalaaron2bb1in->evalaaron2bb5in, Arg_0: Arg_0 {O(n)} 7: evalaaron2bb1in->evalaaron2bb5in, Arg_1: Arg_2 {O(n)} 7: evalaaron2bb1in->evalaaron2bb5in, Arg_2: Arg_2 {O(n)} 7: evalaaron2bb1in->evalaaron2bb5in, Arg_3: max([Arg_4, max([Arg_0, Arg_4])+max([0, (1+2*Arg_2+-2*Arg_4)*max([1, 1+Arg_0])])]) {O(n^2)} 7: evalaaron2bb1in->evalaaron2bb5in, Arg_4: Arg_4 {O(n)} 9: evalaaron2bb1in->evalaaron2bb2in, Arg_0: Arg_0 {O(n)} 9: evalaaron2bb1in->evalaaron2bb2in, Arg_1: Arg_2 {O(n)} 9: evalaaron2bb1in->evalaaron2bb2in, Arg_2: Arg_2 {O(n)} 9: evalaaron2bb1in->evalaaron2bb2in, Arg_3: max([Arg_0, Arg_4])+max([0, (1+2*Arg_2+-2*Arg_4)*max([1, 1+Arg_0])]) {O(n^2)} 9: evalaaron2bb1in->evalaaron2bb2in, Arg_4: Arg_4 {O(n)} 10: evalaaron2bb2in->evalaaron24, Arg_0: Arg_0 {O(n)} 10: evalaaron2bb2in->evalaaron24, Arg_1: Arg_2 {O(n)} 10: evalaaron2bb2in->evalaaron24, Arg_2: Arg_2 {O(n)} 10: evalaaron2bb2in->evalaaron24, Arg_3: max([Arg_0, Arg_4])+max([0, (1+2*Arg_2+-2*Arg_4)*max([1, 1+Arg_0])]) {O(n^2)} 10: evalaaron2bb2in->evalaaron24, Arg_4: Arg_4 {O(n)} 14: evalaaron2bb3in->evalaaron2bb1in, Arg_0: Arg_0 {O(n)} 14: evalaaron2bb3in->evalaaron2bb1in, Arg_1: Arg_2 {O(n)} 14: evalaaron2bb3in->evalaaron2bb1in, Arg_2: Arg_2 {O(n)} 14: evalaaron2bb3in->evalaaron2bb1in, Arg_3: max([Arg_0, Arg_4])+max([0, (1+2*Arg_2+-2*Arg_4)*max([1, 1+Arg_0])]) {O(n^2)} 14: evalaaron2bb3in->evalaaron2bb1in, Arg_4: Arg_4 {O(n)} 15: evalaaron2bb4in->evalaaron2bb1in, Arg_0: Arg_0 {O(n)} 15: evalaaron2bb4in->evalaaron2bb1in, Arg_1: Arg_2 {O(n)} 15: evalaaron2bb4in->evalaaron2bb1in, Arg_2: Arg_2 {O(n)} 15: evalaaron2bb4in->evalaaron2bb1in, Arg_3: max([Arg_0, Arg_4])+max([0, (1+2*Arg_2+-2*Arg_4)*max([1, 1+Arg_0])]) {O(n^2)} 15: evalaaron2bb4in->evalaaron2bb1in, Arg_4: Arg_4 {O(n)} 15: evalaaron2bb4in->evalaaron2bb1in, Arg_5: 0 {O(1)} 16: evalaaron2bb5in->evalaaron2stop, Arg_0: max([-1, Arg_0]) {O(n)} 16: evalaaron2bb5in->evalaaron2stop, Arg_1: max([Arg_2, Arg_1]) {O(n)} 16: evalaaron2bb5in->evalaaron2stop, Arg_2: Arg_2 {O(n)} 16: evalaaron2bb5in->evalaaron2stop, Arg_3: max([Arg_4, max([Arg_3, max([Arg_0, Arg_4])+max([0, (1+2*Arg_2+-2*Arg_4)*max([1, 1+Arg_0])])])]) {O(n^2)} 16: evalaaron2bb5in->evalaaron2stop, Arg_4: Arg_4 {O(n)} 0: evalaaron2start->evalaaron2bb0in, Arg_0: Arg_0 {O(n)} 0: evalaaron2start->evalaaron2bb0in, Arg_1: Arg_1 {O(n)} 0: evalaaron2start->evalaaron2bb0in, Arg_2: Arg_2 {O(n)} 0: evalaaron2start->evalaaron2bb0in, Arg_3: Arg_3 {O(n)} 0: evalaaron2start->evalaaron2bb0in, Arg_4: Arg_4 {O(n)} 0: evalaaron2start->evalaaron2bb0in, Arg_5: Arg_5 {O(n)} ---------------------------------------- (2) BOUNDS(1, nat(2 + 6 * Arg_2 + -6 * Arg_4) + nat(3 + 3 * Arg_2 + -3 * Arg_4) + max(5, 6 + Arg_2 + -1 * Arg_4) + max(5 + 2 * Arg_2 + -2 * Arg_4, 4)) ---------------------------------------- (3) Loat Proof (FINISHED) ### Pre-processing the ITS problem ### Initial linear ITS problem Start location: evalaaron2start 0: evalaaron2start -> evalaaron2bb0in : [], cost: 1 1: evalaaron2bb0in -> evalaaron20 : [], cost: 1 2: evalaaron20 -> evalaaron21 : [], cost: 1 3: evalaaron21 -> evalaaron22 : [], cost: 1 4: evalaaron22 -> evalaaron23 : [], cost: 1 5: evalaaron23 -> evalaaron2bb1in : B'=C, D'=E, [ A>=0 ], cost: 1 6: evalaaron23 -> evalaaron2bb5in : [ 0>=1+A ], cost: 1 7: evalaaron2bb1in -> evalaaron2bb5in : [ D>=1+B ], cost: 1 8: evalaaron2bb1in -> evalaaron2bb5in : [ 0>=1+A ], cost: 1 9: evalaaron2bb1in -> evalaaron2bb2in : [ B>=D && A>=0 ], cost: 1 10: evalaaron2bb2in -> evalaaron24 : [], cost: 1 11: evalaaron24 -> evalaaron25 : F'=free, [], cost: 1 12: evalaaron25 -> evalaaron2bb3in : [ F>=1 ], cost: 1 13: evalaaron25 -> evalaaron2bb4in : [ 0>=F ], cost: 1 14: evalaaron2bb3in -> evalaaron2bb1in : B'=-1-A+B, [], cost: 1 15: evalaaron2bb4in -> evalaaron2bb1in : D'=1+D+A, [], cost: 1 16: evalaaron2bb5in -> evalaaron2stop : [], cost: 1 Removed unreachable and leaf rules: Start location: evalaaron2start 0: evalaaron2start -> evalaaron2bb0in : [], cost: 1 1: evalaaron2bb0in -> evalaaron20 : [], cost: 1 2: evalaaron20 -> evalaaron21 : [], cost: 1 3: evalaaron21 -> evalaaron22 : [], cost: 1 4: evalaaron22 -> evalaaron23 : [], cost: 1 5: evalaaron23 -> evalaaron2bb1in : B'=C, D'=E, [ A>=0 ], cost: 1 9: evalaaron2bb1in -> evalaaron2bb2in : [ B>=D && A>=0 ], cost: 1 10: evalaaron2bb2in -> evalaaron24 : [], cost: 1 11: evalaaron24 -> evalaaron25 : F'=free, [], cost: 1 12: evalaaron25 -> evalaaron2bb3in : [ F>=1 ], cost: 1 13: evalaaron25 -> evalaaron2bb4in : [ 0>=F ], cost: 1 14: evalaaron2bb3in -> evalaaron2bb1in : B'=-1-A+B, [], cost: 1 15: evalaaron2bb4in -> evalaaron2bb1in : D'=1+D+A, [], cost: 1 ### Simplification by acceleration and chaining ### Eliminated locations (on linear paths): Start location: evalaaron2start 21: evalaaron2start -> evalaaron2bb1in : B'=C, D'=E, [ A>=0 ], cost: 6 23: evalaaron2bb1in -> evalaaron25 : F'=free, [ B>=D && A>=0 ], cost: 3 24: evalaaron25 -> evalaaron2bb1in : B'=-1-A+B, [ F>=1 ], cost: 2 25: evalaaron25 -> evalaaron2bb1in : D'=1+D+A, [ 0>=F ], cost: 2 Eliminated locations (on tree-shaped paths): Start location: evalaaron2start 21: evalaaron2start -> evalaaron2bb1in : B'=C, D'=E, [ A>=0 ], cost: 6 26: evalaaron2bb1in -> evalaaron2bb1in : B'=-1-A+B, F'=free, [ B>=D && A>=0 && free>=1 ], cost: 5 27: evalaaron2bb1in -> evalaaron2bb1in : D'=1+D+A, F'=free, [ B>=D && A>=0 && 0>=free ], cost: 5 Accelerating simple loops of location 6. Accelerating the following rules: 26: evalaaron2bb1in -> evalaaron2bb1in : B'=-1-A+B, F'=free, [ B>=D && A>=0 && free>=1 ], cost: 5 27: evalaaron2bb1in -> evalaaron2bb1in : D'=1+D+A, F'=free, [ B>=D && A>=0 && 0>=free ], cost: 5 Accelerated rule 26 with backward acceleration, yielding the new rule 28. Accelerated rule 27 with backward acceleration, yielding the new rule 29. Removing the simple loops: 26 27. Accelerated all simple loops using metering functions (where possible): Start location: evalaaron2start 21: evalaaron2start -> evalaaron2bb1in : B'=C, D'=E, [ A>=0 ], cost: 6 28: evalaaron2bb1in -> evalaaron2bb1in : B'=-A*k-k+B, F'=free, [ B>=D && A>=0 && free>=1 && k>0 && 1-k-A*(-1+k)+B>=D ], cost: 5*k 29: evalaaron2bb1in -> evalaaron2bb1in : D'=k_1*A+k_1+D, F'=free, [ B>=D && A>=0 && 0>=free && k_1>0 && B>=-1+k_1+D+(-1+k_1)*A ], cost: 5*k_1 Chained accelerated rules (with incoming rules): Start location: evalaaron2start 21: evalaaron2start -> evalaaron2bb1in : B'=C, D'=E, [ A>=0 ], cost: 6 30: evalaaron2start -> evalaaron2bb1in : B'=C-A*k-k, D'=E, F'=free, [ A>=0 && C>=E && free>=1 && k>0 && 1+C-k-A*(-1+k)>=E ], cost: 6+5*k 31: evalaaron2start -> evalaaron2bb1in : B'=C, D'=k_1*A+k_1+E, F'=free, [ A>=0 && C>=E && 0>=free && k_1>0 && C>=-1+k_1+(-1+k_1)*A+E ], cost: 6+5*k_1 Removed unreachable locations (and leaf rules with constant cost): Start location: evalaaron2start 30: evalaaron2start -> evalaaron2bb1in : B'=C-A*k-k, D'=E, F'=free, [ A>=0 && C>=E && free>=1 && k>0 && 1+C-k-A*(-1+k)>=E ], cost: 6+5*k 31: evalaaron2start -> evalaaron2bb1in : B'=C, D'=k_1*A+k_1+E, F'=free, [ A>=0 && C>=E && 0>=free && k_1>0 && C>=-1+k_1+(-1+k_1)*A+E ], cost: 6+5*k_1 ### Computing asymptotic complexity ### Fully simplified ITS problem Start location: evalaaron2start 30: evalaaron2start -> evalaaron2bb1in : B'=C-A*k-k, D'=E, F'=free, [ A>=0 && C>=E && free>=1 && k>0 && 1+C-k-A*(-1+k)>=E ], cost: 6+5*k 31: evalaaron2start -> evalaaron2bb1in : B'=C, D'=k_1*A+k_1+E, F'=free, [ A>=0 && C>=E && 0>=free && k_1>0 && C>=-1+k_1+(-1+k_1)*A+E ], cost: 6+5*k_1 Computing asymptotic complexity for rule 30 Solved the limit problem by the following transformations: Created initial limit problem: 6+5*k (+), 1+C-E (+/+!), 2+C-k-E-A*(-1+k) (+/+!), k (+/+!), free (+/+!), 1+A (+/+!) [not solved] removing all constraints (solved by SMT) resulting limit problem: [solved] applying transformation rule (C) using substitution {C==n,A==0,k==1+n,free==n,E==0} resulting limit problem: [solved] Solved the limit problem by the following transformations: Created initial limit problem: 6+5*k (+), 1+C-E (+/+!), 2+C-k-E-A*(-1+k) (+/+!), k (+/+!), free (+/+!), 1+A (+/+!) [not solved] applying transformation rule (C) using substitution {A==0} resulting limit problem: 1 (+/+!), 6+5*k (+), 1+C-E (+/+!), 2+C-k-E (+/+!), k (+/+!), free (+/+!) [not solved] applying transformation rule (C) using substitution {free==1} resulting limit problem: 1 (+/+!), 6+5*k (+), 1+C-E (+/+!), 2+C-k-E (+/+!), k (+/+!) [not solved] applying transformation rule (C) using substitution {E==1+C-k-A*(-1+k)} resulting limit problem: 1 (+/+!), 6+5*k (+), 1+A*(-1+k) (+/+!), k+A*(-1+k) (+/+!), k (+/+!) [not solved] applying transformation rule (B), deleting 1 (+/+!) resulting limit problem: 6+5*k (+), 1+A*(-1+k) (+/+!), k+A*(-1+k) (+/+!), k (+/+!) [not solved] removing all constraints (solved by SMT) resulting limit problem: [solved] applying transformation rule (C) using substitution {A==1,k==n} resulting limit problem: [solved] Solved the limit problem by the following transformations: Created initial limit problem: 6+5*k (+), 1+C-E (+/+!), 2+C-k-E-A*(-1+k) (+/+!), k (+/+!), free (+/+!), 1+A (+/+!) [not solved] applying transformation rule (C) using substitution {free==1} resulting limit problem: 1 (+/+!), 6+5*k (+), 1+C-E (+/+!), 2+C-k-E-A*(-1+k) (+/+!), k (+/+!), 1+A (+/+!) [not solved] applying transformation rule (C) using substitution {E==1+C-k-A*(-1+k)} resulting limit problem: 1 (+/+!), 6+5*k (+), k+A*(-1+k) (+/+!), k (+/+!), 1+A (+/+!) [not solved] applying transformation rule (B), deleting 1 (+/+!) resulting limit problem: 6+5*k (+), k+A*(-1+k) (+/+!), k (+/+!), 1+A (+/+!) [not solved] removing all constraints (solved by SMT) resulting limit problem: [solved] applying transformation rule (C) using substitution {A==0,k==n} resulting limit problem: [solved] Solved the limit problem by the following transformations: Created initial limit problem: 6+5*k (+), 1+C-E (+/+!), 2+C-k-E-A*(-1+k) (+/+!), k (+/+!), free (+/+!), 1+A (+/+!) [not solved] applying transformation rule (C) using substitution {A==0} resulting limit problem: 1 (+/+!), 6+5*k (+), 1+C-E (+/+!), 2+C-k-E (+/+!), k (+/+!), free (+/+!) [not solved] applying transformation rule (C) using substitution {E==1+C-k-A*(-1+k)} resulting limit problem: 1 (+/+!), 6+5*k (+), 1+A*(-1+k) (+/+!), k+A*(-1+k) (+/+!), k (+/+!), free (+/+!) [not solved] applying transformation rule (B), deleting 1 (+/+!) resulting limit problem: 6+5*k (+), 1+A*(-1+k) (+/+!), k+A*(-1+k) (+/+!), k (+/+!), free (+/+!) [not solved] removing all constraints (solved by SMT) resulting limit problem: [solved] applying transformation rule (C) using substitution {A==0,k==1+n,free==n} resulting limit problem: [solved] Solved the limit problem by the following transformations: Created initial limit problem: 6+5*k (+), 1+C-E (+/+!), 2+C-k-E-A*(-1+k) (+/+!), k (+/+!), free (+/+!), 1+A (+/+!) [not solved] applying transformation rule (C) using substitution {E==1+C-k-A*(-1+k)} resulting limit problem: 1 (+/+!), 6+5*k (+), k+A*(-1+k) (+/+!), k (+/+!), free (+/+!), 1+A (+/+!) [not solved] applying transformation rule (B), deleting 1 (+/+!) resulting limit problem: 6+5*k (+), k+A*(-1+k) (+/+!), k (+/+!), free (+/+!), 1+A (+/+!) [not solved] removing all constraints (solved by SMT) resulting limit problem: [solved] applying transformation rule (C) using substitution {A==0,k==n,free==n} resulting limit problem: [solved] Solved the limit problem by the following transformations: Created initial limit problem: 6+5*k (+), 1+C-E (+/+!), 2+C-k-E-A*(-1+k) (+/+!), k (+/+!), free (+/+!), 1+A (+/+!) [not solved] applying transformation rule (C) using substitution {A==0} resulting limit problem: 1 (+/+!), 6+5*k (+), 1+C-E (+/+!), 2+C-k-E (+/+!), k (+/+!), free (+/+!) [not solved] applying transformation rule (C) using substitution {free==1} resulting limit problem: 1 (+/+!), 6+5*k (+), 1+C-E (+/+!), 2+C-k-E (+/+!), k (+/+!) [not solved] applying transformation rule (B), deleting 1 (+/+!) resulting limit problem: 6+5*k (+), 1+C-E (+/+!), 2+C-k-E (+/+!), k (+/+!) [not solved] removing all constraints (solved by SMT) resulting limit problem: [solved] applying transformation rule (C) using substitution {C==0,k==n,E==-n} resulting limit problem: [solved] Solved the limit problem by the following transformations: Created initial limit problem: 6+5*k (+), 1+C-E (+/+!), 2+C-k-E-A*(-1+k) (+/+!), k (+/+!), free (+/+!), 1+A (+/+!) [not solved] applying transformation rule (C) using substitution {free==1} resulting limit problem: 1 (+/+!), 6+5*k (+), 1+C-E (+/+!), 2+C-k-E-A*(-1+k) (+/+!), k (+/+!), 1+A (+/+!) [not solved] applying transformation rule (B), deleting 1 (+/+!) resulting limit problem: 6+5*k (+), 1+C-E (+/+!), 2+C-k-E-A*(-1+k) (+/+!), k (+/+!), 1+A (+/+!) [not solved] removing all constraints (solved by SMT) resulting limit problem: [solved] applying transformation rule (C) using substitution {C==n,A==0,k==1+n,E==0} resulting limit problem: [solved] Solved the limit problem by the following transformations: Created initial limit problem: 6+5*k (+), 1+C-E (+/+!), 2+C-k-E-A*(-1+k) (+/+!), k (+/+!), free (+/+!), 1+A (+/+!) [not solved] applying transformation rule (C) using substitution {A==0} resulting limit problem: 1 (+/+!), 6+5*k (+), 1+C-E (+/+!), 2+C-k-E (+/+!), k (+/+!), free (+/+!) [not solved] applying transformation rule (B), deleting 1 (+/+!) resulting limit problem: 6+5*k (+), 1+C-E (+/+!), 2+C-k-E (+/+!), k (+/+!), free (+/+!) [not solved] removing all constraints (solved by SMT) resulting limit problem: [solved] applying transformation rule (C) using substitution {C==0,k==n,free==n,E==-n} resulting limit problem: [solved] Solution: C / n A / 0 k / 1+n free / n E / 0 Resulting cost 11+5*n has complexity: Poly(n^1) Found new complexity Poly(n^1). Computing asymptotic complexity for rule 31 Solved the limit problem by the following transformations: Created initial limit problem: 1+C-E (+/+!), 6+5*k_1 (+), k_1 (+/+!), 2+C-k_1-(-1+k_1)*A-E (+/+!), 1-free (+/+!), 1+A (+/+!) [not solved] removing all constraints (solved by SMT) resulting limit problem: [solved] applying transformation rule (C) using substitution {C==n,k_1==n,A==0,free==-n,E==1} resulting limit problem: [solved] Solved the limit problem by the following transformations: Created initial limit problem: 1+C-E (+/+!), 6+5*k_1 (+), k_1 (+/+!), 2+C-k_1-(-1+k_1)*A-E (+/+!), 1-free (+/+!), 1+A (+/+!) [not solved] applying transformation rule (C) using substitution {A==0} resulting limit problem: 1 (+/+!), 1+C-E (+/+!), 6+5*k_1 (+), k_1 (+/+!), 2+C-k_1-E (+/+!), 1-free (+/+!) [not solved] applying transformation rule (C) using substitution {free==0} resulting limit problem: 1 (+/+!), 1+C-E (+/+!), 6+5*k_1 (+), k_1 (+/+!), 2+C-k_1-E (+/+!) [not solved] applying transformation rule (C) using substitution {C==-1+k_1+(-1+k_1)*A+E} resulting limit problem: 1 (+/+!), 6+5*k_1 (+), k_1 (+/+!), k_1+(-1+k_1)*A (+/+!), 1+(-1+k_1)*A (+/+!) [not solved] applying transformation rule (B), deleting 1 (+/+!) resulting limit problem: 6+5*k_1 (+), k_1 (+/+!), k_1+(-1+k_1)*A (+/+!), 1+(-1+k_1)*A (+/+!) [not solved] removing all constraints (solved by SMT) resulting limit problem: [solved] applying transformation rule (C) using substitution {k_1==n,A==1} resulting limit problem: [solved] Solved the limit problem by the following transformations: Created initial limit problem: 1+C-E (+/+!), 6+5*k_1 (+), k_1 (+/+!), 2+C-k_1-(-1+k_1)*A-E (+/+!), 1-free (+/+!), 1+A (+/+!) [not solved] applying transformation rule (C) using substitution {free==0} resulting limit problem: 1 (+/+!), 1+C-E (+/+!), 6+5*k_1 (+), k_1 (+/+!), 2+C-k_1-(-1+k_1)*A-E (+/+!), 1+A (+/+!) [not solved] applying transformation rule (C) using substitution {C==-1+k_1+(-1+k_1)*A+E} resulting limit problem: 1 (+/+!), 6+5*k_1 (+), k_1 (+/+!), k_1+(-1+k_1)*A (+/+!), 1+A (+/+!) [not solved] applying transformation rule (B), deleting 1 (+/+!) resulting limit problem: 6+5*k_1 (+), k_1 (+/+!), k_1+(-1+k_1)*A (+/+!), 1+A (+/+!) [not solved] removing all constraints (solved by SMT) resulting limit problem: [solved] applying transformation rule (C) using substitution {k_1==n,A==0} resulting limit problem: [solved] Solved the limit problem by the following transformations: Created initial limit problem: 1+C-E (+/+!), 6+5*k_1 (+), k_1 (+/+!), 2+C-k_1-(-1+k_1)*A-E (+/+!), 1-free (+/+!), 1+A (+/+!) [not solved] applying transformation rule (C) using substitution {A==0} resulting limit problem: 1 (+/+!), 1+C-E (+/+!), 6+5*k_1 (+), k_1 (+/+!), 2+C-k_1-E (+/+!), 1-free (+/+!) [not solved] applying transformation rule (C) using substitution {C==-1+k_1+(-1+k_1)*A+E} resulting limit problem: 1 (+/+!), 6+5*k_1 (+), k_1 (+/+!), 1-free (+/+!), k_1+(-1+k_1)*A (+/+!), 1+(-1+k_1)*A (+/+!) [not solved] applying transformation rule (B), deleting 1 (+/+!) resulting limit problem: 6+5*k_1 (+), k_1 (+/+!), 1-free (+/+!), k_1+(-1+k_1)*A (+/+!), 1+(-1+k_1)*A (+/+!) [not solved] removing all constraints (solved by SMT) resulting limit problem: [solved] applying transformation rule (C) using substitution {k_1==n,A==1,free==-n} resulting limit problem: [solved] Solved the limit problem by the following transformations: Created initial limit problem: 1+C-E (+/+!), 6+5*k_1 (+), k_1 (+/+!), 2+C-k_1-(-1+k_1)*A-E (+/+!), 1-free (+/+!), 1+A (+/+!) [not solved] applying transformation rule (C) using substitution {C==-1+k_1+(-1+k_1)*A+E} resulting limit problem: 1 (+/+!), 6+5*k_1 (+), k_1 (+/+!), 1-free (+/+!), k_1+(-1+k_1)*A (+/+!), 1+A (+/+!) [not solved] applying transformation rule (B), deleting 1 (+/+!) resulting limit problem: 6+5*k_1 (+), k_1 (+/+!), 1-free (+/+!), k_1+(-1+k_1)*A (+/+!), 1+A (+/+!) [not solved] removing all constraints (solved by SMT) resulting limit problem: [solved] applying transformation rule (C) using substitution {k_1==n,A==0,free==-n} resulting limit problem: [solved] Solved the limit problem by the following transformations: Created initial limit problem: 1+C-E (+/+!), 6+5*k_1 (+), k_1 (+/+!), 2+C-k_1-(-1+k_1)*A-E (+/+!), 1-free (+/+!), 1+A (+/+!) [not solved] applying transformation rule (C) using substitution {A==0} resulting limit problem: 1 (+/+!), 1+C-E (+/+!), 6+5*k_1 (+), k_1 (+/+!), 2+C-k_1-E (+/+!), 1-free (+/+!) [not solved] applying transformation rule (C) using substitution {free==0} resulting limit problem: 1 (+/+!), 1+C-E (+/+!), 6+5*k_1 (+), k_1 (+/+!), 2+C-k_1-E (+/+!) [not solved] applying transformation rule (B), deleting 1 (+/+!) resulting limit problem: 1+C-E (+/+!), 6+5*k_1 (+), k_1 (+/+!), 2+C-k_1-E (+/+!) [not solved] removing all constraints (solved by SMT) resulting limit problem: [solved] applying transformation rule (C) using substitution {C==0,k_1==n,E==-n} resulting limit problem: [solved] Solved the limit problem by the following transformations: Created initial limit problem: 1+C-E (+/+!), 6+5*k_1 (+), k_1 (+/+!), 2+C-k_1-(-1+k_1)*A-E (+/+!), 1-free (+/+!), 1+A (+/+!) [not solved] applying transformation rule (C) using substitution {free==0} resulting limit problem: 1 (+/+!), 1+C-E (+/+!), 6+5*k_1 (+), k_1 (+/+!), 2+C-k_1-(-1+k_1)*A-E (+/+!), 1+A (+/+!) [not solved] applying transformation rule (B), deleting 1 (+/+!) resulting limit problem: 1+C-E (+/+!), 6+5*k_1 (+), k_1 (+/+!), 2+C-k_1-(-1+k_1)*A-E (+/+!), 1+A (+/+!) [not solved] removing all constraints (solved by SMT) resulting limit problem: [solved] applying transformation rule (C) using substitution {C==n,k_1==-1+n,A==0,E==2} resulting limit problem: [solved] Solved the limit problem by the following transformations: Created initial limit problem: 1+C-E (+/+!), 6+5*k_1 (+), k_1 (+/+!), 2+C-k_1-(-1+k_1)*A-E (+/+!), 1-free (+/+!), 1+A (+/+!) [not solved] applying transformation rule (C) using substitution {A==0} resulting limit problem: 1 (+/+!), 1+C-E (+/+!), 6+5*k_1 (+), k_1 (+/+!), 2+C-k_1-E (+/+!), 1-free (+/+!) [not solved] applying transformation rule (B), deleting 1 (+/+!) resulting limit problem: 1+C-E (+/+!), 6+5*k_1 (+), k_1 (+/+!), 2+C-k_1-E (+/+!), 1-free (+/+!) [not solved] removing all constraints (solved by SMT) resulting limit problem: [solved] applying transformation rule (C) using substitution {C==0,k_1==n,free==-n,E==-n} resulting limit problem: [solved] Solution: C / n k_1 / n A / 0 free / -n E / 1 Resulting cost 6+5*n has 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: 11+5*n Rule cost: 6+5*k Rule guard: [ A>=0 && C>=E && free>=1 && k>0 && 1+C-k-A*(-1+k)>=E ] WORST_CASE(Omega(n^1),?) ---------------------------------------- (4) BOUNDS(n^1, INF)