/export/starexec/sandbox/solver/bin/starexec_run_complexity /export/starexec/sandbox/benchmark/theBenchmark.koat /export/starexec/sandbox/output/output_files


--------------------------------------------------------------------------------


WORST_CASE(Omega(n^1), ?)
proof of /export/starexec/sandbox/benchmark/theBenchmark.koat
# AProVE Commit ID: 48fb2092695e11cc9f56e44b17a92a5f88ffb256 marcel 20180622 unpublished dirty


The runtime complexity of the given CpxIntTrs could be proven to be BOUNDS(n^1, INF).

(0) CpxIntTrs
(1) Loat Proof [FINISHED, 2434 ms]
(2) BOUNDS(n^1, INF)


----------------------------------------

(0)
Obligation:
Complexity Int TRS consisting of the following rules:
eval_rank1_start(v_2, v_5, v_8, v_m, v_x_0, v_x_1, v_y_0, v_y_1, v_y_2) -> Com_1(eval_rank1_bb0_in(v_2, v_5, v_8, v_m, v_x_0, v_x_1, v_y_0, v_y_1, v_y_2)) :|: TRUE
eval_rank1_bb0_in(v_2, v_5, v_8, v_m, v_x_0, v_x_1, v_y_0, v_y_1, v_y_2) -> Com_1(eval_rank1_0(v_2, v_5, v_8, v_m, v_x_0, v_x_1, v_y_0, v_y_1, v_y_2)) :|: TRUE
eval_rank1_0(v_2, v_5, v_8, v_m, v_x_0, v_x_1, v_y_0, v_y_1, v_y_2) -> Com_1(eval_rank1_1(v_2, v_5, v_8, v_m, v_x_0, v_x_1, v_y_0, v_y_1, v_y_2)) :|: TRUE
eval_rank1_1(v_2, v_5, v_8, v_m, v_x_0, v_x_1, v_y_0, v_y_1, v_y_2) -> Com_1(eval_rank1_2(v_2, v_5, v_8, v_m, v_x_0, v_x_1, v_y_0, v_y_1, v_y_2)) :|: TRUE
eval_rank1_2(v_2, v_5, v_8, v_m, v_x_0, v_x_1, v_y_0, v_y_1, v_y_2) -> Com_1(eval_rank1_3(v_2, v_5, v_8, v_m, v_x_0, v_x_1, v_y_0, v_y_1, v_y_2)) :|: TRUE
eval_rank1_3(v_2, v_5, v_8, v_m, v_x_0, v_x_1, v_y_0, v_y_1, v_y_2) -> Com_1(eval_rank1_4(v_2, v_5, v_8, v_m, v_x_0, v_x_1, v_y_0, v_y_1, v_y_2)) :|: TRUE
eval_rank1_4(v_2, v_5, v_8, v_m, v_x_0, v_x_1, v_y_0, v_y_1, v_y_2) -> Com_1(eval_rank1_5(v_2, v_5, v_8, v_m, v_x_0, v_x_1, v_y_0, v_y_1, v_y_2)) :|: TRUE
eval_rank1_5(v_2, v_5, v_8, v_m, v_x_0, v_x_1, v_y_0, v_y_1, v_y_2) -> Com_1(eval_rank1_bb1_in(v_2, v_5, v_8, v_m, v_m, v_x_1, 0, v_y_1, v_y_2)) :|: TRUE
eval_rank1_bb1_in(v_2, v_5, v_8, v_m, v_x_0, v_x_1, v_y_0, v_y_1, v_y_2) -> Com_1(eval_rank1_bb2_in(v_2, v_5, v_8, v_m, v_x_0, v_x_1, v_y_0, v_y_1, v_y_2)) :|: v_x_0 >= 0 && v_y_0 >= 0
eval_rank1_bb1_in(v_2, v_5, v_8, v_m, v_x_0, v_x_1, v_y_0, v_y_1, v_y_2) -> Com_1(eval_rank1_bb7_in(v_2, v_5, v_8, v_m, v_x_0, v_x_1, v_y_0, v_y_1, v_y_2)) :|: v_x_0 < 0
eval_rank1_bb1_in(v_2, v_5, v_8, v_m, v_x_0, v_x_1, v_y_0, v_y_1, v_y_2) -> Com_1(eval_rank1_bb7_in(v_2, v_5, v_8, v_m, v_x_0, v_x_1, v_y_0, v_y_1, v_y_2)) :|: v_y_0 < 0
eval_rank1_bb2_in(v_2, v_5, v_8, v_m, v_x_0, v_x_1, v_y_0, v_y_1, v_y_2) -> Com_1(eval_rank1_6(v_2, v_5, v_8, v_m, v_x_0, v_x_1, v_y_0, v_y_1, v_y_2)) :|: TRUE
eval_rank1_6(v_2, v_5, v_8, v_m, v_x_0, v_x_1, v_y_0, v_y_1, v_y_2) -> Com_1(eval_rank1_7(nondef_0, v_5, v_8, v_m, v_x_0, v_x_1, v_y_0, v_y_1, v_y_2)) :|: TRUE
eval_rank1_7(v_2, v_5, v_8, v_m, v_x_0, v_x_1, v_y_0, v_y_1, v_y_2) -> Com_1(eval_rank1_bb3_in(v_2, v_5, v_8, v_m, v_x_0, v_x_1, v_y_0, v_y_0, v_y_2)) :|: v_2 > 0
eval_rank1_7(v_2, v_5, v_8, v_m, v_x_0, v_x_1, v_y_0, v_y_1, v_y_2) -> Com_1(eval_rank1_bb6_in(v_2, v_5, v_8, v_m, v_x_0, v_x_0, v_y_0, v_y_1, v_y_0)) :|: v_2 <= 0
eval_rank1_bb3_in(v_2, v_5, v_8, v_m, v_x_0, v_x_1, v_y_0, v_y_1, v_y_2) -> Com_1(eval_rank1_bb4_in(v_2, v_5, v_8, v_m, v_x_0, v_x_1, v_y_0, v_y_1, v_y_2)) :|: v_y_1 <= v_m
eval_rank1_bb3_in(v_2, v_5, v_8, v_m, v_x_0, v_x_1, v_y_0, v_y_1, v_y_2) -> Com_1(eval_rank1__critedge_in(v_2, v_5, v_8, v_m, v_x_0, v_x_1, v_y_0, v_y_1, v_y_2)) :|: v_y_1 > v_m
eval_rank1_bb4_in(v_2, v_5, v_8, v_m, v_x_0, v_x_1, v_y_0, v_y_1, v_y_2) -> Com_1(eval_rank1_8(v_2, v_5, v_8, v_m, v_x_0, v_x_1, v_y_0, v_y_1, v_y_2)) :|: TRUE
eval_rank1_8(v_2, v_5, v_8, v_m, v_x_0, v_x_1, v_y_0, v_y_1, v_y_2) -> Com_1(eval_rank1_9(v_2, nondef_1, v_8, v_m, v_x_0, v_x_1, v_y_0, v_y_1, v_y_2)) :|: TRUE
eval_rank1_9(v_2, v_5, v_8, v_m, v_x_0, v_x_1, v_y_0, v_y_1, v_y_2) -> Com_1(eval_rank1_bb5_in(v_2, v_5, v_8, v_m, v_x_0, v_x_1, v_y_0, v_y_1, v_y_2)) :|: v_5 > 0
eval_rank1_9(v_2, v_5, v_8, v_m, v_x_0, v_x_1, v_y_0, v_y_1, v_y_2) -> Com_1(eval_rank1__critedge_in(v_2, v_5, v_8, v_m, v_x_0, v_x_1, v_y_0, v_y_1, v_y_2)) :|: v_5 <= 0
eval_rank1_bb5_in(v_2, v_5, v_8, v_m, v_x_0, v_x_1, v_y_0, v_y_1, v_y_2) -> Com_1(eval_rank1_bb3_in(v_2, v_5, v_8, v_m, v_x_0, v_x_1, v_y_0, v_y_1 + 1, v_y_2)) :|: TRUE
eval_rank1__critedge_in(v_2, v_5, v_8, v_m, v_x_0, v_x_1, v_y_0, v_y_1, v_y_2) -> Com_1(eval_rank1_13(v_2, v_5, v_x_0 - 1, v_m, v_x_0, v_x_1, v_y_0, v_y_1, v_y_2)) :|: TRUE
eval_rank1_13(v_2, v_5, v_8, v_m, v_x_0, v_x_1, v_y_0, v_y_1, v_y_2) -> Com_1(eval_rank1_14(v_2, v_5, v_8, v_m, v_x_0, v_x_1, v_y_0, v_y_1, v_y_2)) :|: TRUE
eval_rank1_14(v_2, v_5, v_8, v_m, v_x_0, v_x_1, v_y_0, v_y_1, v_y_2) -> Com_1(eval_rank1_bb6_in(v_2, v_5, v_8, v_m, v_x_0, v_8, v_y_0, v_y_1, v_y_1)) :|: TRUE
eval_rank1_bb6_in(v_2, v_5, v_8, v_m, v_x_0, v_x_1, v_y_0, v_y_1, v_y_2) -> Com_1(eval_rank1_bb1_in(v_2, v_5, v_8, v_m, v_x_1, v_x_1, v_y_2 - 1, v_y_1, v_y_2)) :|: TRUE
eval_rank1_bb7_in(v_2, v_5, v_8, v_m, v_x_0, v_x_1, v_y_0, v_y_1, v_y_2) -> Com_1(eval_rank1_stop(v_2, v_5, v_8, v_m, v_x_0, v_x_1, v_y_0, v_y_1, v_y_2)) :|: TRUE

The start-symbols are:[eval_rank1_start_9]


----------------------------------------

(1) Loat Proof (FINISHED)


### Pre-processing the ITS problem ###



Initial linear ITS problem

   Start location: evalrank1start

      0: evalrank1start -> evalrank1bb0in : [], cost: 1

      1: evalrank1bb0in -> evalrank10 : [], cost: 1

      2: evalrank10 -> evalrank11 : [], cost: 1

      3: evalrank11 -> evalrank12 : [], cost: 1

      4: evalrank12 -> evalrank13 : [], cost: 1

      5: evalrank13 -> evalrank14 : [], cost: 1

      6: evalrank14 -> evalrank15 : [], cost: 1

      7: evalrank15 -> evalrank1bb1in : A'=B, C'=0, [], cost: 1

      8: evalrank1bb1in -> evalrank1bb2in : [ A>=0 && C>=0 ], cost: 1

      9: evalrank1bb1in -> evalrank1bb7in : [ 0>=1+A ], cost: 1

     10: evalrank1bb1in -> evalrank1bb7in : [ 0>=1+C ], cost: 1

     11: evalrank1bb2in -> evalrank16 : [], cost: 1

     12: evalrank16 -> evalrank17 : D'=free, [], cost: 1

     13: evalrank17 -> evalrank1bb3in : E'=C, [ D>=1 ], cost: 1

     14: evalrank17 -> evalrank1bb6in : F'=A, G'=C, [ 0>=D ], cost: 1

     15: evalrank1bb3in -> evalrank1bb4in : [ B>=E ], cost: 1

     16: evalrank1bb3in -> evalrank1critedgein : [ E>=1+B ], cost: 1

     17: evalrank1bb4in -> evalrank18 : [], cost: 1

     18: evalrank18 -> evalrank19 : H'=free_1, [], cost: 1

     19: evalrank19 -> evalrank1bb5in : [ H>=1 ], cost: 1

     20: evalrank19 -> evalrank1critedgein : [ 0>=H ], cost: 1

     21: evalrank1bb5in -> evalrank1bb3in : E'=1+E, [], cost: 1

     22: evalrank1critedgein -> evalrank113 : Q'=-1+A, [], cost: 1

     23: evalrank113 -> evalrank114 : [], cost: 1

     24: evalrank114 -> evalrank1bb6in : F'=Q, G'=E, [], cost: 1

     25: evalrank1bb6in -> evalrank1bb1in : A'=F, C'=-1+G, [], cost: 1

     26: evalrank1bb7in -> evalrank1stop : [], cost: 1



Removed unreachable and leaf rules:

   Start location: evalrank1start

      0: evalrank1start -> evalrank1bb0in : [], cost: 1

      1: evalrank1bb0in -> evalrank10 : [], cost: 1

      2: evalrank10 -> evalrank11 : [], cost: 1

      3: evalrank11 -> evalrank12 : [], cost: 1

      4: evalrank12 -> evalrank13 : [], cost: 1

      5: evalrank13 -> evalrank14 : [], cost: 1

      6: evalrank14 -> evalrank15 : [], cost: 1

      7: evalrank15 -> evalrank1bb1in : A'=B, C'=0, [], cost: 1

      8: evalrank1bb1in -> evalrank1bb2in : [ A>=0 && C>=0 ], cost: 1

     11: evalrank1bb2in -> evalrank16 : [], cost: 1

     12: evalrank16 -> evalrank17 : D'=free, [], cost: 1

     13: evalrank17 -> evalrank1bb3in : E'=C, [ D>=1 ], cost: 1

     14: evalrank17 -> evalrank1bb6in : F'=A, G'=C, [ 0>=D ], cost: 1

     15: evalrank1bb3in -> evalrank1bb4in : [ B>=E ], cost: 1

     16: evalrank1bb3in -> evalrank1critedgein : [ E>=1+B ], cost: 1

     17: evalrank1bb4in -> evalrank18 : [], cost: 1

     18: evalrank18 -> evalrank19 : H'=free_1, [], cost: 1

     19: evalrank19 -> evalrank1bb5in : [ H>=1 ], cost: 1

     20: evalrank19 -> evalrank1critedgein : [ 0>=H ], cost: 1

     21: evalrank1bb5in -> evalrank1bb3in : E'=1+E, [], cost: 1

     22: evalrank1critedgein -> evalrank113 : Q'=-1+A, [], cost: 1

     23: evalrank113 -> evalrank114 : [], cost: 1

     24: evalrank114 -> evalrank1bb6in : F'=Q, G'=E, [], cost: 1

     25: evalrank1bb6in -> evalrank1bb1in : A'=F, C'=-1+G, [], cost: 1



### Simplification by acceleration and chaining ###



Eliminated locations (on linear paths):

   Start location: evalrank1start

     33: evalrank1start -> evalrank1bb1in : A'=B, C'=0, [], cost: 8

     35: evalrank1bb1in -> evalrank17 : D'=free, [ A>=0 && C>=0 ], cost: 3

     13: evalrank17 -> evalrank1bb3in : E'=C, [ D>=1 ], cost: 1

     14: evalrank17 -> evalrank1bb6in : F'=A, G'=C, [ 0>=D ], cost: 1

     16: evalrank1bb3in -> evalrank1critedgein : [ E>=1+B ], cost: 1

     37: evalrank1bb3in -> evalrank19 : H'=free_1, [ B>=E ], cost: 3

     20: evalrank19 -> evalrank1critedgein : [ 0>=H ], cost: 1

     38: evalrank19 -> evalrank1bb3in : E'=1+E, [ H>=1 ], cost: 2

     40: evalrank1critedgein -> evalrank1bb6in : F'=-1+A, G'=E, Q'=-1+A, [], cost: 3

     25: evalrank1bb6in -> evalrank1bb1in : A'=F, C'=-1+G, [], cost: 1



Eliminated locations (on tree-shaped paths):

   Start location: evalrank1start

     33: evalrank1start -> evalrank1bb1in : A'=B, C'=0, [], cost: 8

     41: evalrank1bb1in -> evalrank1bb3in : D'=free, E'=C, [ A>=0 && C>=0 && free>=1 ], cost: 4

     42: evalrank1bb1in -> evalrank1bb6in : D'=free, F'=A, G'=C, [ A>=0 && C>=0 && 0>=free ], cost: 4

     44: evalrank1bb3in -> evalrank1bb3in : E'=1+E, H'=free_1, [ B>=E && free_1>=1 ], cost: 5

     45: evalrank1bb3in -> evalrank1bb6in : F'=-1+A, G'=E, Q'=-1+A, [ E>=1+B ], cost: 4

     46: evalrank1bb3in -> evalrank1bb6in : F'=-1+A, G'=E, H'=free_1, Q'=-1+A, [ B>=E && 0>=free_1 ], cost: 7

     25: evalrank1bb6in -> evalrank1bb1in : A'=F, C'=-1+G, [], cost: 1



Accelerating simple loops of location 12.

   Accelerating the following rules:

     44: evalrank1bb3in -> evalrank1bb3in : E'=1+E, H'=free_1, [ B>=E && free_1>=1 ], cost: 5



   Accelerated rule 44 with metering function 1-E+B, yielding the new rule 47.

   Removing the simple loops: 44.



Accelerated all simple loops using metering functions (where possible):

   Start location: evalrank1start

     33: evalrank1start -> evalrank1bb1in : A'=B, C'=0, [], cost: 8

     41: evalrank1bb1in -> evalrank1bb3in : D'=free, E'=C, [ A>=0 && C>=0 && free>=1 ], cost: 4

     42: evalrank1bb1in -> evalrank1bb6in : D'=free, F'=A, G'=C, [ A>=0 && C>=0 && 0>=free ], cost: 4

     45: evalrank1bb3in -> evalrank1bb6in : F'=-1+A, G'=E, Q'=-1+A, [ E>=1+B ], cost: 4

     46: evalrank1bb3in -> evalrank1bb6in : F'=-1+A, G'=E, H'=free_1, Q'=-1+A, [ B>=E && 0>=free_1 ], cost: 7

     47: evalrank1bb3in -> evalrank1bb3in : E'=1+B, H'=free_1, [ B>=E && free_1>=1 ], cost: 5-5*E+5*B

     25: evalrank1bb6in -> evalrank1bb1in : A'=F, C'=-1+G, [], cost: 1



Chained accelerated rules (with incoming rules):

   Start location: evalrank1start

     33: evalrank1start -> evalrank1bb1in : A'=B, C'=0, [], cost: 8

     41: evalrank1bb1in -> evalrank1bb3in : D'=free, E'=C, [ A>=0 && C>=0 && free>=1 ], cost: 4

     42: evalrank1bb1in -> evalrank1bb6in : D'=free, F'=A, G'=C, [ A>=0 && C>=0 && 0>=free ], cost: 4

     48: evalrank1bb1in -> evalrank1bb3in : D'=free, E'=1+B, H'=free_1, [ A>=0 && C>=0 && free>=1 && B>=C && free_1>=1 ], cost: 9-5*C+5*B

     45: evalrank1bb3in -> evalrank1bb6in : F'=-1+A, G'=E, Q'=-1+A, [ E>=1+B ], cost: 4

     46: evalrank1bb3in -> evalrank1bb6in : F'=-1+A, G'=E, H'=free_1, Q'=-1+A, [ B>=E && 0>=free_1 ], cost: 7

     25: evalrank1bb6in -> evalrank1bb1in : A'=F, C'=-1+G, [], cost: 1



Eliminated locations (on tree-shaped paths):

   Start location: evalrank1start

     33: evalrank1start -> evalrank1bb1in : A'=B, C'=0, [], cost: 8

     52: evalrank1bb1in -> [24] : [ A>=0 && C>=0 && free>=1 && B>=C && free_1>=1 ], cost: 9-5*C+5*B

     53: evalrank1bb1in -> evalrank1bb1in : A'=A, C'=-1+C, D'=free, F'=A, G'=C, [ A>=0 && C>=0 && 0>=free ], cost: 5

     54: evalrank1bb1in -> evalrank1bb1in : A'=-1+A, C'=-1+C, D'=free, E'=C, F'=-1+A, G'=C, Q'=-1+A, [ A>=0 && C>=0 && free>=1 && C>=1+B ], cost: 9

     55: evalrank1bb1in -> evalrank1bb1in : A'=-1+A, C'=-1+C, D'=free, E'=C, F'=-1+A, G'=C, H'=free_1, Q'=-1+A, [ A>=0 && C>=0 && free>=1 && B>=C && 0>=free_1 ], cost: 12

     56: evalrank1bb1in -> evalrank1bb1in : A'=-1+A, C'=B, D'=free, E'=1+B, F'=-1+A, G'=1+B, H'=free_1, Q'=-1+A, [ A>=0 && C>=0 && free>=1 && B>=C && free_1>=1 ], cost: 14-5*C+5*B



Accelerating simple loops of location 8.

   Simplified some of the simple loops (and removed duplicate rules).

   Accelerating the following rules:

     53: evalrank1bb1in -> evalrank1bb1in : C'=-1+C, D'=free, F'=A, G'=C, [ A>=0 && C>=0 && 0>=free ], cost: 5

     54: evalrank1bb1in -> evalrank1bb1in : A'=-1+A, C'=-1+C, D'=free, E'=C, F'=-1+A, G'=C, Q'=-1+A, [ A>=0 && C>=0 && free>=1 && C>=1+B ], cost: 9

     55: evalrank1bb1in -> evalrank1bb1in : A'=-1+A, C'=-1+C, D'=free, E'=C, F'=-1+A, G'=C, H'=free_1, Q'=-1+A, [ A>=0 && C>=0 && free>=1 && B>=C && 0>=free_1 ], cost: 12

     56: evalrank1bb1in -> evalrank1bb1in : A'=-1+A, C'=B, D'=free, E'=1+B, F'=-1+A, G'=1+B, H'=free_1, Q'=-1+A, [ A>=0 && C>=0 && free>=1 && B>=C && free_1>=1 ], cost: 14-5*C+5*B



   Accelerated rule 53 with metering function 1+C, yielding the new rule 57.

   Accelerated rule 54 with backward acceleration, yielding the new rule 58.

   Accelerated rule 54 with backward acceleration, yielding the new rule 59.

   Accelerated rule 54 with backward acceleration, yielding the new rule 60.

   Accelerated rule 55 with metering function 1+C (after adding A>=C), yielding the new rule 61.

   Accelerated rule 55 with metering function 1+A (after adding A<=C), yielding the new rule 62.

   Accelerated rule 56 with metering function 1+A, yielding the new rule 63.

   Removing the simple loops: 53 54 55 56.



Accelerated all simple loops using metering functions (where possible):

   Start location: evalrank1start

     33: evalrank1start -> evalrank1bb1in : A'=B, C'=0, [], cost: 8

     52: evalrank1bb1in -> [24] : [ A>=0 && C>=0 && free>=1 && B>=C && free_1>=1 ], cost: 9-5*C+5*B

     57: evalrank1bb1in -> evalrank1bb1in : C'=-1, D'=free, F'=A, G'=0, [ A>=0 && C>=0 && 0>=free ], cost: 5+5*C

     58: evalrank1bb1in -> evalrank1bb1in : A'=-1, C'=-1+C-A, D'=free, E'=C-A, F'=-1, G'=C-A, Q'=-1, [ A>=0 && C>=0 && free>=1 && C>=1+B && C-A>=0 && C-A>=1+B ], cost: 9+9*A

     59: evalrank1bb1in -> evalrank1bb1in : A'=-1-C+A, C'=-1, D'=free, E'=0, F'=-1-C+A, G'=0, Q'=-1-C+A, [ A>=0 && C>=0 && free>=1 && C>=1+B && -C+A>=0 && 0>=1+B ], cost: 9+9*C

     60: evalrank1bb1in -> evalrank1bb1in : A'=-C+A+B, C'=B, D'=free, E'=1+B, F'=-C+A+B, G'=1+B, Q'=-C+A+B, [ A>=0 && C>=0 && free>=1 && C>=1+B && 1-C+A+B>=0 && 1+B>=0 ], cost: 9*C-9*B

     61: evalrank1bb1in -> evalrank1bb1in : A'=-1-C+A, C'=-1, D'=free, E'=0, F'=-1-C+A, G'=0, H'=free_1, Q'=-1-C+A, [ A>=0 && C>=0 && free>=1 && B>=C && 0>=free_1 && A>=C ], cost: 12+12*C

     62: evalrank1bb1in -> evalrank1bb1in : A'=-1, C'=-1+C-A, D'=free, E'=C-A, F'=-1, G'=C-A, H'=free_1, Q'=-1, [ A>=0 && C>=0 && free>=1 && B>=C && 0>=free_1 && A<=C ], cost: 12+12*A

     63: evalrank1bb1in -> evalrank1bb1in : A'=-1, C'=B, D'=free, E'=1+B, F'=-1, G'=1+B, H'=free_1, Q'=-1, [ A>=0 && C>=0 && free>=1 && B>=C && free_1>=1 ], cost: 14+14*A



Chained accelerated rules (with incoming rules):

   Start location: evalrank1start

     33: evalrank1start -> evalrank1bb1in : A'=B, C'=0, [], cost: 8

     64: evalrank1start -> evalrank1bb1in : A'=B, C'=-1, D'=free, F'=B, G'=0, [ B>=0 && 0>=free ], cost: 13

     65: evalrank1start -> evalrank1bb1in : A'=-1+B, C'=-1, D'=free, E'=0, F'=-1+B, G'=0, H'=free_1, Q'=-1+B, [ B>=0 && free>=1 && 0>=free_1 ], cost: 20

     66: evalrank1start -> evalrank1bb1in : A'=-1, C'=-1-B, D'=free, E'=-B, F'=-1, G'=-B, H'=free_1, Q'=-1, [ -B==0 && free>=1 && 0>=free_1 ], cost: 20+12*B

     67: evalrank1start -> evalrank1bb1in : A'=-1, C'=B, D'=free, E'=1+B, F'=-1, G'=1+B, H'=free_1, Q'=-1, [ B>=0 && free>=1 && free_1>=1 ], cost: 22+14*B

     52: evalrank1bb1in -> [24] : [ A>=0 && C>=0 && free>=1 && B>=C && free_1>=1 ], cost: 9-5*C+5*B



Eliminated locations (on tree-shaped paths):

   Start location: evalrank1start

     68: evalrank1start -> [24] : A'=B, C'=0, [ B>=0 && free>=1 && free_1>=1 ], cost: 17+5*B

     69: evalrank1start -> [26] : [ -B==0 && free>=1 && 0>=free_1 ], cost: 20+12*B

     70: evalrank1start -> [26] : [ B>=0 && free>=1 && free_1>=1 ], cost: 22+14*B



### Computing asymptotic complexity ###



Fully simplified ITS problem

   Start location: evalrank1start

     68: evalrank1start -> [24] : A'=B, C'=0, [ B>=0 && free>=1 && free_1>=1 ], cost: 17+5*B

     69: evalrank1start -> [26] : [ -B==0 && free>=1 && 0>=free_1 ], cost: 20+12*B

     70: evalrank1start -> [26] : [ B>=0 && free>=1 && free_1>=1 ], cost: 22+14*B



Computing asymptotic complexity for rule 68

   Solved the limit problem by the following transformations:

      Created initial limit problem:

      free_1 (+/+!), 1+B (+/+!), 17+5*B (+), free (+/+!) [not solved]



      removing all constraints (solved by SMT)

      resulting limit problem: [solved]



      applying transformation rule (C) using substitution {free_1==n,free==n,B==n}

      resulting limit problem:

      [solved]



   Solution:

      free_1 / n

      free / n

      B / n

   Resulting cost 17+5*n has complexity: Poly(n^1)



Found new complexity Poly(n^1).



Obtained the following overall complexity (w.r.t. the length of the input n):

   Complexity:  Poly(n^1)

   Cpx degree:  1

   Solved cost: 17+5*n

   Rule cost:   17+5*B

   Rule guard:  [ B>=0 && free>=1 && free_1>=1 ]



WORST_CASE(Omega(n^1),?)


----------------------------------------

(2)
BOUNDS(n^1, INF)