/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: 794c25de1cacf0d048858bcd21c9a779e1221865 marcel 20200619 unpublished dirty


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

(0) CpxIntTrs
(1) Loat Proof [FINISHED, 2236 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



Checking for constant complexity:

   The following rule is satisfiable with cost >= 1, yielding constant complexity:

      0: evalrank1start -> evalrank1bb0in : [], 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.

   Found no metering function for rule 54.

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

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

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

   Removing the simple loops: 53 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

     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

     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+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

     59: 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

     60: 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

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

     62: 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

     63: 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

     64: 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

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

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

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



### Computing asymptotic complexity ###



Fully simplified ITS problem

   Start location: evalrank1start

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

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

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



Computing asymptotic complexity for rule 65

   Solved the limit problem by the following transformations:

      Created initial limit problem:

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



      removing all constraints (solved by SMT)

      resulting limit problem: [solved]



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

      resulting limit problem:

      [solved]



   Solution:

      free / n

      B / n

      free_1 / 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)