/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), ?)
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, INF).

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


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

(0)
Obligation:
Complexity Int TRS consisting of the following rules:
eval_serpent_start(v_3, v_6, v_8, v_n, v_x_0, v_y_0, v_y_1, v_y_2) -> Com_1(eval_serpent_bb0_in(v_3, v_6, v_8, v_n, v_x_0, v_y_0, v_y_1, v_y_2)) :|: TRUE
eval_serpent_bb0_in(v_3, v_6, v_8, v_n, v_x_0, v_y_0, v_y_1, v_y_2) -> Com_1(eval_serpent_0(v_3, v_6, v_8, v_n, v_x_0, v_y_0, v_y_1, v_y_2)) :|: TRUE
eval_serpent_0(v_3, v_6, v_8, v_n, v_x_0, v_y_0, v_y_1, v_y_2) -> Com_1(eval_serpent_1(v_3, v_6, v_8, v_n, v_x_0, v_y_0, v_y_1, v_y_2)) :|: TRUE
eval_serpent_1(v_3, v_6, v_8, v_n, v_x_0, v_y_0, v_y_1, v_y_2) -> Com_1(eval_serpent_bb7_in(v_3, v_6, v_8, v_n, v_x_0, v_y_0, v_y_1, v_y_2)) :|: v_n <= 0
eval_serpent_1(v_3, v_6, v_8, v_n, v_x_0, v_y_0, v_y_1, v_y_2) -> Com_1(eval_serpent__critedge1_in(v_3, v_6, v_8, v_n, v_n, v_n, v_y_1, v_y_2)) :|: v_n > 0
eval_serpent__critedge1_in(v_3, v_6, v_8, v_n, v_x_0, v_y_0, v_y_1, v_y_2) -> Com_1(eval_serpent_bb1_in(v_3, v_6, v_8, v_n, v_x_0, v_y_0, v_y_0, v_y_2)) :|: v_x_0 >= 0
eval_serpent__critedge1_in(v_3, v_6, v_8, v_n, v_x_0, v_y_0, v_y_1, v_y_2) -> Com_1(eval_serpent_bb7_in(v_3, v_6, v_8, v_n, v_x_0, v_y_0, v_y_1, v_y_2)) :|: v_x_0 < 0
eval_serpent_bb1_in(v_3, v_6, v_8, v_n, v_x_0, v_y_0, v_y_1, v_y_2) -> Com_1(eval_serpent_bb2_in(v_3, v_6, v_8, v_n, v_x_0, v_y_0, v_y_1, v_y_2)) :|: v_y_1 >= 0
eval_serpent_bb1_in(v_3, v_6, v_8, v_n, v_x_0, v_y_0, v_y_1, v_y_2) -> Com_1(eval_serpent__critedge_in(v_3, v_6, v_8, v_n, v_x_0, v_y_0, v_y_1, v_y_2)) :|: v_y_1 < 0
eval_serpent_bb2_in(v_3, v_6, v_8, v_n, v_x_0, v_y_0, v_y_1, v_y_2) -> Com_1(eval_serpent_2(v_3, v_6, v_8, v_n, v_x_0, v_y_0, v_y_1, v_y_2)) :|: TRUE
eval_serpent_2(v_3, v_6, v_8, v_n, v_x_0, v_y_0, v_y_1, v_y_2) -> Com_1(eval_serpent_3(nondef_0, v_6, v_8, v_n, v_x_0, v_y_0, v_y_1, v_y_2)) :|: TRUE
eval_serpent_3(v_3, v_6, v_8, v_n, v_x_0, v_y_0, v_y_1, v_y_2) -> Com_1(eval_serpent_bb3_in(v_3, v_6, v_8, v_n, v_x_0, v_y_0, v_y_1, v_y_2)) :|: v_3 > 0
eval_serpent_3(v_3, v_6, v_8, v_n, v_x_0, v_y_0, v_y_1, v_y_2) -> Com_1(eval_serpent__critedge_in(v_3, v_6, v_8, v_n, v_x_0, v_y_0, v_y_1, v_y_2)) :|: v_3 <= 0
eval_serpent_bb3_in(v_3, v_6, v_8, v_n, v_x_0, v_y_0, v_y_1, v_y_2) -> Com_1(eval_serpent_bb1_in(v_3, v_6, v_8, v_n, v_x_0, v_y_0, v_y_1 - 1, v_y_2)) :|: TRUE
eval_serpent__critedge_in(v_3, v_6, v_8, v_n, v_x_0, v_y_0, v_y_1, v_y_2) -> Com_1(eval_serpent_7(v_3, v_x_0 - 1, v_8, v_n, v_x_0, v_y_0, v_y_1, v_y_2)) :|: TRUE
eval_serpent_7(v_3, v_6, v_8, v_n, v_x_0, v_y_0, v_y_1, v_y_2) -> Com_1(eval_serpent_8(v_3, v_6, v_8, v_n, v_x_0, v_y_0, v_y_1, v_y_2)) :|: TRUE
eval_serpent_8(v_3, v_6, v_8, v_n, v_x_0, v_y_0, v_y_1, v_y_2) -> Com_1(eval_serpent_9(v_3, v_6, v_8, v_n, v_x_0, v_y_0, v_y_1, v_y_2)) :|: TRUE
eval_serpent_9(v_3, v_6, v_8, v_n, v_x_0, v_y_0, v_y_1, v_y_2) -> Com_1(eval_serpent_bb4_in(v_3, v_6, v_8, v_n, v_x_0, v_y_0, v_y_1, v_y_1)) :|: TRUE
eval_serpent_bb4_in(v_3, v_6, v_8, v_n, v_x_0, v_y_0, v_y_1, v_y_2) -> Com_1(eval_serpent_bb5_in(v_3, v_6, v_8, v_n, v_x_0, v_y_0, v_y_1, v_y_2)) :|: v_y_2 <= v_n
eval_serpent_bb4_in(v_3, v_6, v_8, v_n, v_x_0, v_y_0, v_y_1, v_y_2) -> Com_1(eval_serpent__critedge1_in(v_3, v_6, v_8, v_n, v_6, v_y_2, v_y_1, v_y_2)) :|: v_y_2 > v_n
eval_serpent_bb5_in(v_3, v_6, v_8, v_n, v_x_0, v_y_0, v_y_1, v_y_2) -> Com_1(eval_serpent_10(v_3, v_6, v_8, v_n, v_x_0, v_y_0, v_y_1, v_y_2)) :|: TRUE
eval_serpent_10(v_3, v_6, v_8, v_n, v_x_0, v_y_0, v_y_1, v_y_2) -> Com_1(eval_serpent_11(v_3, v_6, nondef_1, v_n, v_x_0, v_y_0, v_y_1, v_y_2)) :|: TRUE
eval_serpent_11(v_3, v_6, v_8, v_n, v_x_0, v_y_0, v_y_1, v_y_2) -> Com_1(eval_serpent_bb6_in(v_3, v_6, v_8, v_n, v_x_0, v_y_0, v_y_1, v_y_2)) :|: v_8 > 0
eval_serpent_11(v_3, v_6, v_8, v_n, v_x_0, v_y_0, v_y_1, v_y_2) -> Com_1(eval_serpent__critedge1_in(v_3, v_6, v_8, v_n, v_6, v_y_2, v_y_1, v_y_2)) :|: v_8 <= 0
eval_serpent_bb6_in(v_3, v_6, v_8, v_n, v_x_0, v_y_0, v_y_1, v_y_2) -> Com_1(eval_serpent_bb4_in(v_3, v_6, v_8, v_n, v_x_0, v_y_0, v_y_1, v_y_2 + 1)) :|: TRUE
eval_serpent_bb7_in(v_3, v_6, v_8, v_n, v_x_0, v_y_0, v_y_1, v_y_2) -> Com_1(eval_serpent_stop(v_3, v_6, v_8, v_n, v_x_0, v_y_0, v_y_1, v_y_2)) :|: TRUE

The start-symbols are:[eval_serpent_start_8]


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

(1) Loat Proof (FINISHED)


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



Initial linear ITS problem

   Start location: evalserpentstart

      0: evalserpentstart -> evalserpentbb0in : [], cost: 1

      1: evalserpentbb0in -> evalserpent0 : [], cost: 1

      2: evalserpent0 -> evalserpent1 : [], cost: 1

      3: evalserpent1 -> evalserpentbb7in : [ 0>=A ], cost: 1

      4: evalserpent1 -> evalserpentcritedge1in : B'=A, C'=A, [ A>=1 ], cost: 1

      5: evalserpentcritedge1in -> evalserpentbb1in : D'=C, [ B>=0 ], cost: 1

      6: evalserpentcritedge1in -> evalserpentbb7in : [ 0>=1+B ], cost: 1

      7: evalserpentbb1in -> evalserpentbb2in : [ D>=0 ], cost: 1

      8: evalserpentbb1in -> evalserpentcritedgein : [ 0>=1+D ], cost: 1

      9: evalserpentbb2in -> evalserpent2 : [], cost: 1

     10: evalserpent2 -> evalserpent3 : E'=free, [], cost: 1

     11: evalserpent3 -> evalserpentbb3in : [ E>=1 ], cost: 1

     12: evalserpent3 -> evalserpentcritedgein : [ 0>=E ], cost: 1

     13: evalserpentbb3in -> evalserpentbb1in : D'=-1+D, [], cost: 1

     14: evalserpentcritedgein -> evalserpent7 : F'=-1+B, [], cost: 1

     15: evalserpent7 -> evalserpent8 : [], cost: 1

     16: evalserpent8 -> evalserpent9 : [], cost: 1

     17: evalserpent9 -> evalserpentbb4in : G'=D, [], cost: 1

     18: evalserpentbb4in -> evalserpentbb5in : [ A>=G ], cost: 1

     19: evalserpentbb4in -> evalserpentcritedge1in : B'=F, C'=G, [ G>=1+A ], cost: 1

     20: evalserpentbb5in -> evalserpent10 : [], cost: 1

     21: evalserpent10 -> evalserpent11 : H'=free_1, [], cost: 1

     22: evalserpent11 -> evalserpentbb6in : [ H>=1 ], cost: 1

     23: evalserpent11 -> evalserpentcritedge1in : B'=F, C'=G, [ 0>=H ], cost: 1

     24: evalserpentbb6in -> evalserpentbb4in : G'=1+G, [], cost: 1

     25: evalserpentbb7in -> evalserpentstop : [], cost: 1



Checking for constant complexity:

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

      0: evalserpentstart -> evalserpentbb0in : [], cost: 1



Removed unreachable and leaf rules:

   Start location: evalserpentstart

      0: evalserpentstart -> evalserpentbb0in : [], cost: 1

      1: evalserpentbb0in -> evalserpent0 : [], cost: 1

      2: evalserpent0 -> evalserpent1 : [], cost: 1

      4: evalserpent1 -> evalserpentcritedge1in : B'=A, C'=A, [ A>=1 ], cost: 1

      5: evalserpentcritedge1in -> evalserpentbb1in : D'=C, [ B>=0 ], cost: 1

      7: evalserpentbb1in -> evalserpentbb2in : [ D>=0 ], cost: 1

      8: evalserpentbb1in -> evalserpentcritedgein : [ 0>=1+D ], cost: 1

      9: evalserpentbb2in -> evalserpent2 : [], cost: 1

     10: evalserpent2 -> evalserpent3 : E'=free, [], cost: 1

     11: evalserpent3 -> evalserpentbb3in : [ E>=1 ], cost: 1

     12: evalserpent3 -> evalserpentcritedgein : [ 0>=E ], cost: 1

     13: evalserpentbb3in -> evalserpentbb1in : D'=-1+D, [], cost: 1

     14: evalserpentcritedgein -> evalserpent7 : F'=-1+B, [], cost: 1

     15: evalserpent7 -> evalserpent8 : [], cost: 1

     16: evalserpent8 -> evalserpent9 : [], cost: 1

     17: evalserpent9 -> evalserpentbb4in : G'=D, [], cost: 1

     18: evalserpentbb4in -> evalserpentbb5in : [ A>=G ], cost: 1

     19: evalserpentbb4in -> evalserpentcritedge1in : B'=F, C'=G, [ G>=1+A ], cost: 1

     20: evalserpentbb5in -> evalserpent10 : [], cost: 1

     21: evalserpent10 -> evalserpent11 : H'=free_1, [], cost: 1

     22: evalserpent11 -> evalserpentbb6in : [ H>=1 ], cost: 1

     23: evalserpent11 -> evalserpentcritedge1in : B'=F, C'=G, [ 0>=H ], cost: 1

     24: evalserpentbb6in -> evalserpentbb4in : G'=1+G, [], cost: 1



### Simplification by acceleration and chaining ###



Eliminated locations (on linear paths):

   Start location: evalserpentstart

     28: evalserpentstart -> evalserpentcritedge1in : B'=A, C'=A, [ A>=1 ], cost: 4

      5: evalserpentcritedge1in -> evalserpentbb1in : D'=C, [ B>=0 ], cost: 1

      8: evalserpentbb1in -> evalserpentcritedgein : [ 0>=1+D ], cost: 1

     30: evalserpentbb1in -> evalserpent3 : E'=free, [ D>=0 ], cost: 3

     12: evalserpent3 -> evalserpentcritedgein : [ 0>=E ], cost: 1

     31: evalserpent3 -> evalserpentbb1in : D'=-1+D, [ E>=1 ], cost: 2

     34: evalserpentcritedgein -> evalserpentbb4in : F'=-1+B, G'=D, [], cost: 4

     19: evalserpentbb4in -> evalserpentcritedge1in : B'=F, C'=G, [ G>=1+A ], cost: 1

     36: evalserpentbb4in -> evalserpent11 : H'=free_1, [ A>=G ], cost: 3

     23: evalserpent11 -> evalserpentcritedge1in : B'=F, C'=G, [ 0>=H ], cost: 1

     37: evalserpent11 -> evalserpentbb4in : G'=1+G, [ H>=1 ], cost: 2



Eliminated locations (on tree-shaped paths):

   Start location: evalserpentstart

     28: evalserpentstart -> evalserpentcritedge1in : B'=A, C'=A, [ A>=1 ], cost: 4

      5: evalserpentcritedge1in -> evalserpentbb1in : D'=C, [ B>=0 ], cost: 1

     39: evalserpentbb1in -> evalserpentbb1in : D'=-1+D, E'=free, [ D>=0 && free>=1 ], cost: 5

     40: evalserpentbb1in -> evalserpentbb4in : F'=-1+B, G'=D, [ 0>=1+D ], cost: 5

     41: evalserpentbb1in -> evalserpentbb4in : E'=free, F'=-1+B, G'=D, [ D>=0 && 0>=free ], cost: 8

     19: evalserpentbb4in -> evalserpentcritedge1in : B'=F, C'=G, [ G>=1+A ], cost: 1

     42: evalserpentbb4in -> evalserpentcritedge1in : B'=F, C'=G, H'=free_1, [ A>=G && 0>=free_1 ], cost: 4

     43: evalserpentbb4in -> evalserpentbb4in : G'=1+G, H'=free_1, [ A>=G && free_1>=1 ], cost: 5



Accelerating simple loops of location 5.

   Accelerating the following rules:

     39: evalserpentbb1in -> evalserpentbb1in : D'=-1+D, E'=free, [ D>=0 && free>=1 ], cost: 5



   Accelerated rule 39 with metering function 1+D, yielding the new rule 44.

   Removing the simple loops: 39.



Accelerating simple loops of location 14.

   Accelerating the following rules:

     43: evalserpentbb4in -> evalserpentbb4in : G'=1+G, H'=free_1, [ A>=G && free_1>=1 ], cost: 5



   Accelerated rule 43 with metering function 1-G+A, yielding the new rule 45.

   Removing the simple loops: 43.



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

   Start location: evalserpentstart

     28: evalserpentstart -> evalserpentcritedge1in : B'=A, C'=A, [ A>=1 ], cost: 4

      5: evalserpentcritedge1in -> evalserpentbb1in : D'=C, [ B>=0 ], cost: 1

     40: evalserpentbb1in -> evalserpentbb4in : F'=-1+B, G'=D, [ 0>=1+D ], cost: 5

     41: evalserpentbb1in -> evalserpentbb4in : E'=free, F'=-1+B, G'=D, [ D>=0 && 0>=free ], cost: 8

     44: evalserpentbb1in -> evalserpentbb1in : D'=-1, E'=free, [ D>=0 && free>=1 ], cost: 5+5*D

     19: evalserpentbb4in -> evalserpentcritedge1in : B'=F, C'=G, [ G>=1+A ], cost: 1

     42: evalserpentbb4in -> evalserpentcritedge1in : B'=F, C'=G, H'=free_1, [ A>=G && 0>=free_1 ], cost: 4

     45: evalserpentbb4in -> evalserpentbb4in : G'=1+A, H'=free_1, [ A>=G && free_1>=1 ], cost: 5-5*G+5*A



Chained accelerated rules (with incoming rules):

   Start location: evalserpentstart

     28: evalserpentstart -> evalserpentcritedge1in : B'=A, C'=A, [ A>=1 ], cost: 4

      5: evalserpentcritedge1in -> evalserpentbb1in : D'=C, [ B>=0 ], cost: 1

     46: evalserpentcritedge1in -> evalserpentbb1in : D'=-1, E'=free, [ B>=0 && C>=0 && free>=1 ], cost: 6+5*C

     40: evalserpentbb1in -> evalserpentbb4in : F'=-1+B, G'=D, [ 0>=1+D ], cost: 5

     41: evalserpentbb1in -> evalserpentbb4in : E'=free, F'=-1+B, G'=D, [ D>=0 && 0>=free ], cost: 8

     47: evalserpentbb1in -> evalserpentbb4in : F'=-1+B, G'=1+A, H'=free_1, [ 0>=1+D && A>=D && free_1>=1 ], cost: 10-5*D+5*A

     48: evalserpentbb1in -> evalserpentbb4in : E'=free, F'=-1+B, G'=1+A, H'=free_1, [ D>=0 && 0>=free && A>=D && free_1>=1 ], cost: 13-5*D+5*A

     19: evalserpentbb4in -> evalserpentcritedge1in : B'=F, C'=G, [ G>=1+A ], cost: 1

     42: evalserpentbb4in -> evalserpentcritedge1in : B'=F, C'=G, H'=free_1, [ A>=G && 0>=free_1 ], cost: 4



Eliminated locations (on tree-shaped paths):

   Start location: evalserpentstart

     28: evalserpentstart -> evalserpentcritedge1in : B'=A, C'=A, [ A>=1 ], cost: 4

     49: evalserpentcritedge1in -> evalserpentbb4in : D'=C, F'=-1+B, G'=C, [ B>=0 && 0>=1+C ], cost: 6

     50: evalserpentcritedge1in -> evalserpentbb4in : D'=C, E'=free, F'=-1+B, G'=C, [ B>=0 && C>=0 && 0>=free ], cost: 9

     51: evalserpentcritedge1in -> evalserpentbb4in : D'=C, F'=-1+B, G'=1+A, H'=free_1, [ B>=0 && 0>=1+C && A>=C && free_1>=1 ], cost: 11-5*C+5*A

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

     53: evalserpentcritedge1in -> evalserpentbb4in : D'=-1, E'=free, F'=-1+B, G'=-1, [ B>=0 && C>=0 && free>=1 ], cost: 11+5*C

     54: evalserpentcritedge1in -> evalserpentbb4in : D'=-1, E'=free, F'=-1+B, G'=1+A, H'=free_1, [ B>=0 && C>=0 && free>=1 && A>=-1 && free_1>=1 ], cost: 21+5*C+5*A

     55: evalserpentcritedge1in -> [23] : [ B>=0 && C>=0 && free>=1 ], cost: 6+5*C

     19: evalserpentbb4in -> evalserpentcritedge1in : B'=F, C'=G, [ G>=1+A ], cost: 1

     42: evalserpentbb4in -> evalserpentcritedge1in : B'=F, C'=G, H'=free_1, [ A>=G && 0>=free_1 ], cost: 4



Applied pruning (of leafs and parallel rules):

   Start location: evalserpentstart

     28: evalserpentstart -> evalserpentcritedge1in : B'=A, C'=A, [ A>=1 ], cost: 4

     49: evalserpentcritedge1in -> evalserpentbb4in : D'=C, F'=-1+B, G'=C, [ B>=0 && 0>=1+C ], cost: 6

     51: evalserpentcritedge1in -> evalserpentbb4in : D'=C, F'=-1+B, G'=1+A, H'=free_1, [ B>=0 && 0>=1+C && A>=C && free_1>=1 ], cost: 11-5*C+5*A

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

     53: evalserpentcritedge1in -> evalserpentbb4in : D'=-1, E'=free, F'=-1+B, G'=-1, [ B>=0 && C>=0 && free>=1 ], cost: 11+5*C

     54: evalserpentcritedge1in -> evalserpentbb4in : D'=-1, E'=free, F'=-1+B, G'=1+A, H'=free_1, [ B>=0 && C>=0 && free>=1 && A>=-1 && free_1>=1 ], cost: 21+5*C+5*A

     55: evalserpentcritedge1in -> [23] : [ B>=0 && C>=0 && free>=1 ], cost: 6+5*C

     19: evalserpentbb4in -> evalserpentcritedge1in : B'=F, C'=G, [ G>=1+A ], cost: 1

     42: evalserpentbb4in -> evalserpentcritedge1in : B'=F, C'=G, H'=free_1, [ A>=G && 0>=free_1 ], cost: 4



Eliminated locations (on tree-shaped paths):

   Start location: evalserpentstart

     28: evalserpentstart -> evalserpentcritedge1in : B'=A, C'=A, [ A>=1 ], cost: 4

     55: evalserpentcritedge1in -> [23] : [ B>=0 && C>=0 && free>=1 ], cost: 6+5*C

     56: evalserpentcritedge1in -> evalserpentcritedge1in : B'=-1+B, C'=C, D'=C, F'=-1+B, G'=C, [ B>=0 && 0>=1+C && C>=1+A ], cost: 7

     57: evalserpentcritedge1in -> evalserpentcritedge1in : B'=-1+B, C'=C, D'=C, F'=-1+B, G'=C, H'=free_1, [ B>=0 && 0>=1+C && A>=C && 0>=free_1 ], cost: 10

     58: evalserpentcritedge1in -> evalserpentcritedge1in : B'=-1+B, C'=1+A, D'=C, F'=-1+B, G'=1+A, H'=free_1, [ B>=0 && 0>=1+C && A>=C && free_1>=1 ], cost: 12-5*C+5*A

     59: evalserpentcritedge1in -> evalserpentcritedge1in : B'=-1+B, C'=1+A, D'=C, E'=free, F'=-1+B, G'=1+A, H'=free_1, [ B>=0 && C>=0 && 0>=free && A>=C && free_1>=1 ], cost: 15-5*C+5*A

     60: evalserpentcritedge1in -> evalserpentcritedge1in : B'=-1+B, C'=-1, D'=-1, E'=free, F'=-1+B, G'=-1, [ B>=0 && C>=0 && free>=1 && -1>=1+A ], cost: 12+5*C

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

     62: evalserpentcritedge1in -> evalserpentcritedge1in : B'=-1+B, C'=1+A, D'=-1, E'=free, F'=-1+B, G'=1+A, H'=free_1, [ B>=0 && C>=0 && free>=1 && A>=-1 && free_1>=1 ], cost: 22+5*C+5*A

     63: evalserpentcritedge1in -> [24] : [ B>=0 && 0>=1+C && A>=C && free_1>=1 ], cost: 11-5*C+5*A

     64: evalserpentcritedge1in -> [24] : [ B>=0 && C>=0 && 0>=free && A>=C && free_1>=1 ], cost: 14-5*C+5*A

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



Applied pruning (of leafs and parallel rules):

   Start location: evalserpentstart

     28: evalserpentstart -> evalserpentcritedge1in : B'=A, C'=A, [ A>=1 ], cost: 4

     55: evalserpentcritedge1in -> [23] : [ B>=0 && C>=0 && free>=1 ], cost: 6+5*C

     58: evalserpentcritedge1in -> evalserpentcritedge1in : B'=-1+B, C'=1+A, D'=C, F'=-1+B, G'=1+A, H'=free_1, [ B>=0 && 0>=1+C && A>=C && free_1>=1 ], cost: 12-5*C+5*A

     59: evalserpentcritedge1in -> evalserpentcritedge1in : B'=-1+B, C'=1+A, D'=C, E'=free, F'=-1+B, G'=1+A, H'=free_1, [ B>=0 && C>=0 && 0>=free && A>=C && free_1>=1 ], cost: 15-5*C+5*A

     60: evalserpentcritedge1in -> evalserpentcritedge1in : B'=-1+B, C'=-1, D'=-1, E'=free, F'=-1+B, G'=-1, [ B>=0 && C>=0 && free>=1 && -1>=1+A ], cost: 12+5*C

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

     62: evalserpentcritedge1in -> evalserpentcritedge1in : B'=-1+B, C'=1+A, D'=-1, E'=free, F'=-1+B, G'=1+A, H'=free_1, [ B>=0 && C>=0 && free>=1 && A>=-1 && free_1>=1 ], cost: 22+5*C+5*A

     63: evalserpentcritedge1in -> [24] : [ B>=0 && 0>=1+C && A>=C && free_1>=1 ], cost: 11-5*C+5*A

     64: evalserpentcritedge1in -> [24] : [ B>=0 && C>=0 && 0>=free && A>=C && free_1>=1 ], cost: 14-5*C+5*A

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



Accelerating simple loops of location 4.

   Accelerating the following rules:

     58: evalserpentcritedge1in -> evalserpentcritedge1in : B'=-1+B, C'=1+A, D'=C, F'=-1+B, G'=1+A, H'=free_1, [ B>=0 && 0>=1+C && A>=C && free_1>=1 ], cost: 12-5*C+5*A

     59: evalserpentcritedge1in -> evalserpentcritedge1in : B'=-1+B, C'=1+A, D'=C, E'=free, F'=-1+B, G'=1+A, H'=free_1, [ B>=0 && C>=0 && 0>=free && A>=C && free_1>=1 ], cost: 15-5*C+5*A

     60: evalserpentcritedge1in -> evalserpentcritedge1in : B'=-1+B, C'=-1, D'=-1, E'=free, F'=-1+B, G'=-1, [ B>=0 && C>=0 && free>=1 && -1>=1+A ], cost: 12+5*C

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

     62: evalserpentcritedge1in -> evalserpentcritedge1in : B'=-1+B, C'=1+A, D'=-1, E'=free, F'=-1+B, G'=1+A, H'=free_1, [ B>=0 && C>=0 && free>=1 && A>=-1 && free_1>=1 ], cost: 22+5*C+5*A



   Found no metering function for rule 58.

   Found no metering function for rule 59.

   Found no metering function for rule 60.

   Found no metering function for rule 61.

   Accelerated rule 62 with metering function 1+B, yielding the new rule 66.

   Removing the simple loops: 62.



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

   Start location: evalserpentstart

     28: evalserpentstart -> evalserpentcritedge1in : B'=A, C'=A, [ A>=1 ], cost: 4

     55: evalserpentcritedge1in -> [23] : [ B>=0 && C>=0 && free>=1 ], cost: 6+5*C

     58: evalserpentcritedge1in -> evalserpentcritedge1in : B'=-1+B, C'=1+A, D'=C, F'=-1+B, G'=1+A, H'=free_1, [ B>=0 && 0>=1+C && A>=C && free_1>=1 ], cost: 12-5*C+5*A

     59: evalserpentcritedge1in -> evalserpentcritedge1in : B'=-1+B, C'=1+A, D'=C, E'=free, F'=-1+B, G'=1+A, H'=free_1, [ B>=0 && C>=0 && 0>=free && A>=C && free_1>=1 ], cost: 15-5*C+5*A

     60: evalserpentcritedge1in -> evalserpentcritedge1in : B'=-1+B, C'=-1, D'=-1, E'=free, F'=-1+B, G'=-1, [ B>=0 && C>=0 && free>=1 && -1>=1+A ], cost: 12+5*C

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

     63: evalserpentcritedge1in -> [24] : [ B>=0 && 0>=1+C && A>=C && free_1>=1 ], cost: 11-5*C+5*A

     64: evalserpentcritedge1in -> [24] : [ B>=0 && C>=0 && 0>=free && A>=C && free_1>=1 ], cost: 14-5*C+5*A

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

     66: evalserpentcritedge1in -> evalserpentcritedge1in : B'=-1, C'=1+A, D'=-1, E'=free, F'=-1, G'=1+A, H'=free_1, [ B>=0 && C>=0 && free>=1 && A>=-1 && free_1>=1 ], cost: 27+10*A*(1+B)+27*B



Chained accelerated rules (with incoming rules):

   Start location: evalserpentstart

     28: evalserpentstart -> evalserpentcritedge1in : B'=A, C'=A, [ A>=1 ], cost: 4

     67: evalserpentstart -> evalserpentcritedge1in : B'=-1+A, C'=1+A, D'=A, E'=free, F'=-1+A, G'=1+A, H'=free_1, [ A>=1 && 0>=free && free_1>=1 ], cost: 19

     68: evalserpentstart -> evalserpentcritedge1in : B'=-1+A, C'=-1, D'=-1, E'=free, F'=-1+A, G'=-1, H'=free_1, [ A>=1 && free>=1 && 0>=free_1 ], cost: 19+5*A

     69: evalserpentstart -> evalserpentcritedge1in : B'=-1, C'=1+A, D'=-1, E'=free, F'=-1, G'=1+A, H'=free_1, [ A>=1 && free>=1 && free_1>=1 ], cost: 31+10*A*(1+A)+27*A

     55: evalserpentcritedge1in -> [23] : [ B>=0 && C>=0 && free>=1 ], cost: 6+5*C

     63: evalserpentcritedge1in -> [24] : [ B>=0 && 0>=1+C && A>=C && free_1>=1 ], cost: 11-5*C+5*A

     64: evalserpentcritedge1in -> [24] : [ B>=0 && C>=0 && 0>=free && A>=C && free_1>=1 ], cost: 14-5*C+5*A

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



Eliminated locations (on tree-shaped paths):

   Start location: evalserpentstart

     70: evalserpentstart -> [23] : B'=A, C'=A, [ A>=1 && free>=1 ], cost: 10+5*A

     71: evalserpentstart -> [24] : B'=A, C'=A, [ A>=1 && 0>=free && free_1>=1 ], cost: 18

     72: evalserpentstart -> [24] : B'=A, C'=A, [ A>=1 && free>=1 && free_1>=1 ], cost: 25+10*A

     73: evalserpentstart -> [26] : [ A>=1 && free>=1 && 0>=free_1 ], cost: 19+5*A

     74: evalserpentstart -> [26] : [ A>=1 && free>=1 && free_1>=1 ], cost: 31+10*A*(1+A)+27*A



Applied pruning (of leafs and parallel rules):

   Start location: evalserpentstart

     70: evalserpentstart -> [23] : B'=A, C'=A, [ A>=1 && free>=1 ], cost: 10+5*A

     72: evalserpentstart -> [24] : B'=A, C'=A, [ A>=1 && free>=1 && free_1>=1 ], cost: 25+10*A

     73: evalserpentstart -> [26] : [ A>=1 && free>=1 && 0>=free_1 ], cost: 19+5*A

     74: evalserpentstart -> [26] : [ A>=1 && free>=1 && free_1>=1 ], cost: 31+10*A*(1+A)+27*A



### Computing asymptotic complexity ###



Fully simplified ITS problem

   Start location: evalserpentstart

     70: evalserpentstart -> [23] : B'=A, C'=A, [ A>=1 && free>=1 ], cost: 10+5*A

     72: evalserpentstart -> [24] : B'=A, C'=A, [ A>=1 && free>=1 && free_1>=1 ], cost: 25+10*A

     73: evalserpentstart -> [26] : [ A>=1 && free>=1 && 0>=free_1 ], cost: 19+5*A

     74: evalserpentstart -> [26] : [ A>=1 && free>=1 && free_1>=1 ], cost: 31+10*A*(1+A)+27*A



Computing asymptotic complexity for rule 70

   Solved the limit problem by the following transformations:

      Created initial limit problem:

      free (+/+!), A (+/+!), 10+5*A (+) [not solved]



      removing all constraints (solved by SMT)

      resulting limit problem: [solved]



      applying transformation rule (C) using substitution {free==1,A==n}

      resulting limit problem:

      [solved]



   Solution:

      free / 1

      A / n

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



Found new complexity Poly(n^1).



Computing asymptotic complexity for rule 74

   Solved the limit problem by the following transformations:

      Created initial limit problem:

      free (+/+!), A (+/+!), free_1 (+/+!), 31+37*A+10*A^2 (+) [not solved]



      removing all constraints (solved by SMT)

      resulting limit problem: [solved]



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

      resulting limit problem:

      [solved]



   Solution:

      free / n

      A / n

      free_1 / n

   Resulting cost 31+37*n+10*n^2 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: 31+37*n+10*n^2

   Rule cost:   31+10*A*(1+A)+27*A

   Rule guard:  [ A>=1 && free>=1 && free_1>=1 ]



WORST_CASE(Omega(n^2),?)


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

(2)
BOUNDS(n^2, INF)