/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, 2475 ms]
(2) BOUNDS(n^2, INF)


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

(0)
Obligation:
Complexity Int TRS consisting of the following rules:
eval_counterex1b_start(v__0, v__01, v__1, v__2, v_2, v_5, v_7, v_n, v_x, v_y) -> Com_1(eval_counterex1b_bb0_in(v__0, v__01, v__1, v__2, v_2, v_5, v_7, v_n, v_x, v_y)) :|: TRUE
eval_counterex1b_bb0_in(v__0, v__01, v__1, v__2, v_2, v_5, v_7, v_n, v_x, v_y) -> Com_1(eval_counterex1b_0(v__0, v__01, v__1, v__2, v_2, v_5, v_7, v_n, v_x, v_y)) :|: TRUE
eval_counterex1b_0(v__0, v__01, v__1, v__2, v_2, v_5, v_7, v_n, v_x, v_y) -> Com_1(eval_counterex1b_1(v__0, v__01, v__1, v__2, v_2, v_5, v_7, v_n, v_x, v_y)) :|: TRUE
eval_counterex1b_1(v__0, v__01, v__1, v__2, v_2, v_5, v_7, v_n, v_x, v_y) -> Com_1(eval_counterex1b_2(v__0, v__01, v__1, v__2, v_2, v_5, v_7, v_n, v_x, v_y)) :|: TRUE
eval_counterex1b_2(v__0, v__01, v__1, v__2, v_2, v_5, v_7, v_n, v_x, v_y) -> Com_1(eval_counterex1b_3(v__0, v__01, v__1, v__2, v_2, v_5, v_7, v_n, v_x, v_y)) :|: TRUE
eval_counterex1b_3(v__0, v__01, v__1, v__2, v_2, v_5, v_7, v_n, v_x, v_y) -> Com_1(eval_counterex1b_4(v__0, v__01, v__1, v__2, v_2, v_5, v_7, v_n, v_x, v_y)) :|: TRUE
eval_counterex1b_4(v__0, v__01, v__1, v__2, v_2, v_5, v_7, v_n, v_x, v_y) -> Com_1(eval_counterex1b__critedge2_in(v_x, v_y, v__1, v__2, v_2, v_5, v_7, v_n, v_x, v_y)) :|: TRUE
eval_counterex1b__critedge2_in(v__0, v__01, v__1, v__2, v_2, v_5, v_7, v_n, v_x, v_y) -> Com_1(eval_counterex1b_bb1_in(v__0, v__01, v__01, v__2, v_2, v_5, v_7, v_n, v_x, v_y)) :|: v__0 >= 0
eval_counterex1b__critedge2_in(v__0, v__01, v__1, v__2, v_2, v_5, v_7, v_n, v_x, v_y) -> Com_1(eval_counterex1b_bb7_in(v__0, v__01, v__1, v__2, v_2, v_5, v_7, v_n, v_x, v_y)) :|: v__0 < 0
eval_counterex1b_bb1_in(v__0, v__01, v__1, v__2, v_2, v_5, v_7, v_n, v_x, v_y) -> Com_1(eval_counterex1b_bb2_in(v__0, v__01, v__1, v__2, v_2, v_5, v_7, v_n, v_x, v_y)) :|: v__1 >= 0
eval_counterex1b_bb1_in(v__0, v__01, v__1, v__2, v_2, v_5, v_7, v_n, v_x, v_y) -> Com_1(eval_counterex1b__critedge_in(v__0, v__01, v__1, v__2, v_2, v_5, v_7, v_n, v_x, v_y)) :|: v__1 < 0
eval_counterex1b_bb2_in(v__0, v__01, v__1, v__2, v_2, v_5, v_7, v_n, v_x, v_y) -> Com_1(eval_counterex1b_5(v__0, v__01, v__1, v__2, v_2, v_5, v_7, v_n, v_x, v_y)) :|: TRUE
eval_counterex1b_5(v__0, v__01, v__1, v__2, v_2, v_5, v_7, v_n, v_x, v_y) -> Com_1(eval_counterex1b_6(v__0, v__01, v__1, v__2, nondef_0, v_5, v_7, v_n, v_x, v_y)) :|: TRUE
eval_counterex1b_6(v__0, v__01, v__1, v__2, v_2, v_5, v_7, v_n, v_x, v_y) -> Com_1(eval_counterex1b_bb3_in(v__0, v__01, v__1, v__2, v_2, v_5, v_7, v_n, v_x, v_y)) :|: v_2 > 0
eval_counterex1b_6(v__0, v__01, v__1, v__2, v_2, v_5, v_7, v_n, v_x, v_y) -> Com_1(eval_counterex1b__critedge_in(v__0, v__01, v__1, v__2, v_2, v_5, v_7, v_n, v_x, v_y)) :|: v_2 <= 0
eval_counterex1b_bb3_in(v__0, v__01, v__1, v__2, v_2, v_5, v_7, v_n, v_x, v_y) -> Com_1(eval_counterex1b_bb1_in(v__0, v__01, v__1 - 1, v__2, v_2, v_5, v_7, v_n, v_x, v_y)) :|: TRUE
eval_counterex1b__critedge_in(v__0, v__01, v__1, v__2, v_2, v_5, v_7, v_n, v_x, v_y) -> Com_1(eval_counterex1b_10(v__0, v__01, v__1, v__2, v_2, v__0 - 1, v_7, v_n, v_x, v_y)) :|: TRUE
eval_counterex1b_10(v__0, v__01, v__1, v__2, v_2, v_5, v_7, v_n, v_x, v_y) -> Com_1(eval_counterex1b_11(v__0, v__01, v__1, v__2, v_2, v_5, v_7, v_n, v_x, v_y)) :|: TRUE
eval_counterex1b_11(v__0, v__01, v__1, v__2, v_2, v_5, v_7, v_n, v_x, v_y) -> Com_1(eval_counterex1b_12(v__0, v__01, v__1, v__2, v_2, v_5, v_7, v_n, v_x, v_y)) :|: TRUE
eval_counterex1b_12(v__0, v__01, v__1, v__2, v_2, v_5, v_7, v_n, v_x, v_y) -> Com_1(eval_counterex1b_bb4_in(v__0, v__01, v__1, v__1, v_2, v_5, v_7, v_n, v_x, v_y)) :|: TRUE
eval_counterex1b_bb4_in(v__0, v__01, v__1, v__2, v_2, v_5, v_7, v_n, v_x, v_y) -> Com_1(eval_counterex1b_bb5_in(v__0, v__01, v__1, v__2, v_2, v_5, v_7, v_n, v_x, v_y)) :|: v__2 <= v_n
eval_counterex1b_bb4_in(v__0, v__01, v__1, v__2, v_2, v_5, v_7, v_n, v_x, v_y) -> Com_1(eval_counterex1b__critedge2_in(v_5, v__2, v__1, v__2, v_2, v_5, v_7, v_n, v_x, v_y)) :|: v__2 > v_n
eval_counterex1b_bb5_in(v__0, v__01, v__1, v__2, v_2, v_5, v_7, v_n, v_x, v_y) -> Com_1(eval_counterex1b_13(v__0, v__01, v__1, v__2, v_2, v_5, v_7, v_n, v_x, v_y)) :|: TRUE
eval_counterex1b_13(v__0, v__01, v__1, v__2, v_2, v_5, v_7, v_n, v_x, v_y) -> Com_1(eval_counterex1b_14(v__0, v__01, v__1, v__2, v_2, v_5, nondef_1, v_n, v_x, v_y)) :|: TRUE
eval_counterex1b_14(v__0, v__01, v__1, v__2, v_2, v_5, v_7, v_n, v_x, v_y) -> Com_1(eval_counterex1b_bb6_in(v__0, v__01, v__1, v__2, v_2, v_5, v_7, v_n, v_x, v_y)) :|: v_7 > 0
eval_counterex1b_14(v__0, v__01, v__1, v__2, v_2, v_5, v_7, v_n, v_x, v_y) -> Com_1(eval_counterex1b__critedge2_in(v_5, v__2, v__1, v__2, v_2, v_5, v_7, v_n, v_x, v_y)) :|: v_7 <= 0
eval_counterex1b_bb6_in(v__0, v__01, v__1, v__2, v_2, v_5, v_7, v_n, v_x, v_y) -> Com_1(eval_counterex1b_bb4_in(v__0, v__01, v__1, v__2 + 1, v_2, v_5, v_7, v_n, v_x, v_y)) :|: TRUE
eval_counterex1b_bb7_in(v__0, v__01, v__1, v__2, v_2, v_5, v_7, v_n, v_x, v_y) -> Com_1(eval_counterex1b_stop(v__0, v__01, v__1, v__2, v_2, v_5, v_7, v_n, v_x, v_y)) :|: TRUE

The start-symbols are:[eval_counterex1b_start_10]


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

(1) Loat Proof (FINISHED)


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



Initial linear ITS problem

   Start location: evalcounterex1bstart

      0: evalcounterex1bstart -> evalcounterex1bbb0in : [], cost: 1

      1: evalcounterex1bbb0in -> evalcounterex1b0 : [], cost: 1

      2: evalcounterex1b0 -> evalcounterex1b1 : [], cost: 1

      3: evalcounterex1b1 -> evalcounterex1b2 : [], cost: 1

      4: evalcounterex1b2 -> evalcounterex1b3 : [], cost: 1

      5: evalcounterex1b3 -> evalcounterex1b4 : [], cost: 1

      6: evalcounterex1b4 -> evalcounterex1bcritedge2in : A'=B, C'=D, [], cost: 1

      7: evalcounterex1bcritedge2in -> evalcounterex1bbb1in : E'=C, [ A>=0 ], cost: 1

      8: evalcounterex1bcritedge2in -> evalcounterex1bbb7in : [ 0>=1+A ], cost: 1

      9: evalcounterex1bbb1in -> evalcounterex1bbb2in : [ E>=0 ], cost: 1

     10: evalcounterex1bbb1in -> evalcounterex1bcritedgein : [ 0>=1+E ], cost: 1

     11: evalcounterex1bbb2in -> evalcounterex1b5 : [], cost: 1

     12: evalcounterex1b5 -> evalcounterex1b6 : F'=free, [], cost: 1

     13: evalcounterex1b6 -> evalcounterex1bbb3in : [ F>=1 ], cost: 1

     14: evalcounterex1b6 -> evalcounterex1bcritedgein : [ 0>=F ], cost: 1

     15: evalcounterex1bbb3in -> evalcounterex1bbb1in : E'=-1+E, [], cost: 1

     16: evalcounterex1bcritedgein -> evalcounterex1b10 : G'=-1+A, [], cost: 1

     17: evalcounterex1b10 -> evalcounterex1b11 : [], cost: 1

     18: evalcounterex1b11 -> evalcounterex1b12 : [], cost: 1

     19: evalcounterex1b12 -> evalcounterex1bbb4in : H'=E, [], cost: 1

     20: evalcounterex1bbb4in -> evalcounterex1bbb5in : [ Q>=H ], cost: 1

     21: evalcounterex1bbb4in -> evalcounterex1bcritedge2in : A'=G, C'=H, [ H>=1+Q ], cost: 1

     22: evalcounterex1bbb5in -> evalcounterex1b13 : [], cost: 1

     23: evalcounterex1b13 -> evalcounterex1b14 : J'=free_1, [], cost: 1

     24: evalcounterex1b14 -> evalcounterex1bbb6in : [ J>=1 ], cost: 1

     25: evalcounterex1b14 -> evalcounterex1bcritedge2in : A'=G, C'=H, [ 0>=J ], cost: 1

     26: evalcounterex1bbb6in -> evalcounterex1bbb4in : H'=1+H, [], cost: 1

     27: evalcounterex1bbb7in -> evalcounterex1bstop : [], cost: 1



Checking for constant complexity:

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

      0: evalcounterex1bstart -> evalcounterex1bbb0in : [], cost: 1



Removed unreachable and leaf rules:

   Start location: evalcounterex1bstart

      0: evalcounterex1bstart -> evalcounterex1bbb0in : [], cost: 1

      1: evalcounterex1bbb0in -> evalcounterex1b0 : [], cost: 1

      2: evalcounterex1b0 -> evalcounterex1b1 : [], cost: 1

      3: evalcounterex1b1 -> evalcounterex1b2 : [], cost: 1

      4: evalcounterex1b2 -> evalcounterex1b3 : [], cost: 1

      5: evalcounterex1b3 -> evalcounterex1b4 : [], cost: 1

      6: evalcounterex1b4 -> evalcounterex1bcritedge2in : A'=B, C'=D, [], cost: 1

      7: evalcounterex1bcritedge2in -> evalcounterex1bbb1in : E'=C, [ A>=0 ], cost: 1

      9: evalcounterex1bbb1in -> evalcounterex1bbb2in : [ E>=0 ], cost: 1

     10: evalcounterex1bbb1in -> evalcounterex1bcritedgein : [ 0>=1+E ], cost: 1

     11: evalcounterex1bbb2in -> evalcounterex1b5 : [], cost: 1

     12: evalcounterex1b5 -> evalcounterex1b6 : F'=free, [], cost: 1

     13: evalcounterex1b6 -> evalcounterex1bbb3in : [ F>=1 ], cost: 1

     14: evalcounterex1b6 -> evalcounterex1bcritedgein : [ 0>=F ], cost: 1

     15: evalcounterex1bbb3in -> evalcounterex1bbb1in : E'=-1+E, [], cost: 1

     16: evalcounterex1bcritedgein -> evalcounterex1b10 : G'=-1+A, [], cost: 1

     17: evalcounterex1b10 -> evalcounterex1b11 : [], cost: 1

     18: evalcounterex1b11 -> evalcounterex1b12 : [], cost: 1

     19: evalcounterex1b12 -> evalcounterex1bbb4in : H'=E, [], cost: 1

     20: evalcounterex1bbb4in -> evalcounterex1bbb5in : [ Q>=H ], cost: 1

     21: evalcounterex1bbb4in -> evalcounterex1bcritedge2in : A'=G, C'=H, [ H>=1+Q ], cost: 1

     22: evalcounterex1bbb5in -> evalcounterex1b13 : [], cost: 1

     23: evalcounterex1b13 -> evalcounterex1b14 : J'=free_1, [], cost: 1

     24: evalcounterex1b14 -> evalcounterex1bbb6in : [ J>=1 ], cost: 1

     25: evalcounterex1b14 -> evalcounterex1bcritedge2in : A'=G, C'=H, [ 0>=J ], cost: 1

     26: evalcounterex1bbb6in -> evalcounterex1bbb4in : H'=1+H, [], cost: 1



### Simplification by acceleration and chaining ###



Eliminated locations (on linear paths):

   Start location: evalcounterex1bstart

     33: evalcounterex1bstart -> evalcounterex1bcritedge2in : A'=B, C'=D, [], cost: 7

      7: evalcounterex1bcritedge2in -> evalcounterex1bbb1in : E'=C, [ A>=0 ], cost: 1

     10: evalcounterex1bbb1in -> evalcounterex1bcritedgein : [ 0>=1+E ], cost: 1

     35: evalcounterex1bbb1in -> evalcounterex1b6 : F'=free, [ E>=0 ], cost: 3

     14: evalcounterex1b6 -> evalcounterex1bcritedgein : [ 0>=F ], cost: 1

     36: evalcounterex1b6 -> evalcounterex1bbb1in : E'=-1+E, [ F>=1 ], cost: 2

     39: evalcounterex1bcritedgein -> evalcounterex1bbb4in : G'=-1+A, H'=E, [], cost: 4

     21: evalcounterex1bbb4in -> evalcounterex1bcritedge2in : A'=G, C'=H, [ H>=1+Q ], cost: 1

     41: evalcounterex1bbb4in -> evalcounterex1b14 : J'=free_1, [ Q>=H ], cost: 3

     25: evalcounterex1b14 -> evalcounterex1bcritedge2in : A'=G, C'=H, [ 0>=J ], cost: 1

     42: evalcounterex1b14 -> evalcounterex1bbb4in : H'=1+H, [ J>=1 ], cost: 2



Eliminated locations (on tree-shaped paths):

   Start location: evalcounterex1bstart

     33: evalcounterex1bstart -> evalcounterex1bcritedge2in : A'=B, C'=D, [], cost: 7

      7: evalcounterex1bcritedge2in -> evalcounterex1bbb1in : E'=C, [ A>=0 ], cost: 1

     44: evalcounterex1bbb1in -> evalcounterex1bbb1in : E'=-1+E, F'=free, [ E>=0 && free>=1 ], cost: 5

     45: evalcounterex1bbb1in -> evalcounterex1bbb4in : G'=-1+A, H'=E, [ 0>=1+E ], cost: 5

     46: evalcounterex1bbb1in -> evalcounterex1bbb4in : F'=free, G'=-1+A, H'=E, [ E>=0 && 0>=free ], cost: 8

     21: evalcounterex1bbb4in -> evalcounterex1bcritedge2in : A'=G, C'=H, [ H>=1+Q ], cost: 1

     47: evalcounterex1bbb4in -> evalcounterex1bcritedge2in : A'=G, C'=H, J'=free_1, [ Q>=H && 0>=free_1 ], cost: 4

     48: evalcounterex1bbb4in -> evalcounterex1bbb4in : H'=1+H, J'=free_1, [ Q>=H && free_1>=1 ], cost: 5



Accelerating simple loops of location 8.

   Accelerating the following rules:

     44: evalcounterex1bbb1in -> evalcounterex1bbb1in : E'=-1+E, F'=free, [ E>=0 && free>=1 ], cost: 5



   Accelerated rule 44 with metering function 1+E, yielding the new rule 49.

   Removing the simple loops: 44.



Accelerating simple loops of location 17.

   Accelerating the following rules:

     48: evalcounterex1bbb4in -> evalcounterex1bbb4in : H'=1+H, J'=free_1, [ Q>=H && free_1>=1 ], cost: 5



   Accelerated rule 48 with metering function 1-H+Q, yielding the new rule 50.

   Removing the simple loops: 48.



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

   Start location: evalcounterex1bstart

     33: evalcounterex1bstart -> evalcounterex1bcritedge2in : A'=B, C'=D, [], cost: 7

      7: evalcounterex1bcritedge2in -> evalcounterex1bbb1in : E'=C, [ A>=0 ], cost: 1

     45: evalcounterex1bbb1in -> evalcounterex1bbb4in : G'=-1+A, H'=E, [ 0>=1+E ], cost: 5

     46: evalcounterex1bbb1in -> evalcounterex1bbb4in : F'=free, G'=-1+A, H'=E, [ E>=0 && 0>=free ], cost: 8

     49: evalcounterex1bbb1in -> evalcounterex1bbb1in : E'=-1, F'=free, [ E>=0 && free>=1 ], cost: 5+5*E

     21: evalcounterex1bbb4in -> evalcounterex1bcritedge2in : A'=G, C'=H, [ H>=1+Q ], cost: 1

     47: evalcounterex1bbb4in -> evalcounterex1bcritedge2in : A'=G, C'=H, J'=free_1, [ Q>=H && 0>=free_1 ], cost: 4

     50: evalcounterex1bbb4in -> evalcounterex1bbb4in : H'=1+Q, J'=free_1, [ Q>=H && free_1>=1 ], cost: 5-5*H+5*Q



Chained accelerated rules (with incoming rules):

   Start location: evalcounterex1bstart

     33: evalcounterex1bstart -> evalcounterex1bcritedge2in : A'=B, C'=D, [], cost: 7

      7: evalcounterex1bcritedge2in -> evalcounterex1bbb1in : E'=C, [ A>=0 ], cost: 1

     51: evalcounterex1bcritedge2in -> evalcounterex1bbb1in : E'=-1, F'=free, [ A>=0 && C>=0 && free>=1 ], cost: 6+5*C

     45: evalcounterex1bbb1in -> evalcounterex1bbb4in : G'=-1+A, H'=E, [ 0>=1+E ], cost: 5

     46: evalcounterex1bbb1in -> evalcounterex1bbb4in : F'=free, G'=-1+A, H'=E, [ E>=0 && 0>=free ], cost: 8

     52: evalcounterex1bbb1in -> evalcounterex1bbb4in : G'=-1+A, H'=1+Q, J'=free_1, [ 0>=1+E && Q>=E && free_1>=1 ], cost: 10-5*E+5*Q

     53: evalcounterex1bbb1in -> evalcounterex1bbb4in : F'=free, G'=-1+A, H'=1+Q, J'=free_1, [ E>=0 && 0>=free && Q>=E && free_1>=1 ], cost: 13-5*E+5*Q

     21: evalcounterex1bbb4in -> evalcounterex1bcritedge2in : A'=G, C'=H, [ H>=1+Q ], cost: 1

     47: evalcounterex1bbb4in -> evalcounterex1bcritedge2in : A'=G, C'=H, J'=free_1, [ Q>=H && 0>=free_1 ], cost: 4



Eliminated locations (on tree-shaped paths):

   Start location: evalcounterex1bstart

     33: evalcounterex1bstart -> evalcounterex1bcritedge2in : A'=B, C'=D, [], cost: 7

     54: evalcounterex1bcritedge2in -> evalcounterex1bbb4in : E'=C, G'=-1+A, H'=C, [ A>=0 && 0>=1+C ], cost: 6

     55: evalcounterex1bcritedge2in -> evalcounterex1bbb4in : E'=C, F'=free, G'=-1+A, H'=C, [ A>=0 && C>=0 && 0>=free ], cost: 9

     56: evalcounterex1bcritedge2in -> evalcounterex1bbb4in : E'=C, G'=-1+A, H'=1+Q, J'=free_1, [ A>=0 && 0>=1+C && Q>=C && free_1>=1 ], cost: 11-5*C+5*Q

     57: evalcounterex1bcritedge2in -> evalcounterex1bbb4in : E'=C, F'=free, G'=-1+A, H'=1+Q, J'=free_1, [ A>=0 && C>=0 && 0>=free && Q>=C && free_1>=1 ], cost: 14-5*C+5*Q

     58: evalcounterex1bcritedge2in -> evalcounterex1bbb4in : E'=-1, F'=free, G'=-1+A, H'=-1, [ A>=0 && C>=0 && free>=1 ], cost: 11+5*C

     59: evalcounterex1bcritedge2in -> evalcounterex1bbb4in : E'=-1, F'=free, G'=-1+A, H'=1+Q, J'=free_1, [ A>=0 && C>=0 && free>=1 && Q>=-1 && free_1>=1 ], cost: 21+5*C+5*Q

     60: evalcounterex1bcritedge2in -> [26] : [ A>=0 && C>=0 && free>=1 ], cost: 6+5*C

     21: evalcounterex1bbb4in -> evalcounterex1bcritedge2in : A'=G, C'=H, [ H>=1+Q ], cost: 1

     47: evalcounterex1bbb4in -> evalcounterex1bcritedge2in : A'=G, C'=H, J'=free_1, [ Q>=H && 0>=free_1 ], cost: 4



Applied pruning (of leafs and parallel rules):

   Start location: evalcounterex1bstart

     33: evalcounterex1bstart -> evalcounterex1bcritedge2in : A'=B, C'=D, [], cost: 7

     54: evalcounterex1bcritedge2in -> evalcounterex1bbb4in : E'=C, G'=-1+A, H'=C, [ A>=0 && 0>=1+C ], cost: 6

     56: evalcounterex1bcritedge2in -> evalcounterex1bbb4in : E'=C, G'=-1+A, H'=1+Q, J'=free_1, [ A>=0 && 0>=1+C && Q>=C && free_1>=1 ], cost: 11-5*C+5*Q

     57: evalcounterex1bcritedge2in -> evalcounterex1bbb4in : E'=C, F'=free, G'=-1+A, H'=1+Q, J'=free_1, [ A>=0 && C>=0 && 0>=free && Q>=C && free_1>=1 ], cost: 14-5*C+5*Q

     58: evalcounterex1bcritedge2in -> evalcounterex1bbb4in : E'=-1, F'=free, G'=-1+A, H'=-1, [ A>=0 && C>=0 && free>=1 ], cost: 11+5*C

     59: evalcounterex1bcritedge2in -> evalcounterex1bbb4in : E'=-1, F'=free, G'=-1+A, H'=1+Q, J'=free_1, [ A>=0 && C>=0 && free>=1 && Q>=-1 && free_1>=1 ], cost: 21+5*C+5*Q

     60: evalcounterex1bcritedge2in -> [26] : [ A>=0 && C>=0 && free>=1 ], cost: 6+5*C

     21: evalcounterex1bbb4in -> evalcounterex1bcritedge2in : A'=G, C'=H, [ H>=1+Q ], cost: 1

     47: evalcounterex1bbb4in -> evalcounterex1bcritedge2in : A'=G, C'=H, J'=free_1, [ Q>=H && 0>=free_1 ], cost: 4



Eliminated locations (on tree-shaped paths):

   Start location: evalcounterex1bstart

     33: evalcounterex1bstart -> evalcounterex1bcritedge2in : A'=B, C'=D, [], cost: 7

     60: evalcounterex1bcritedge2in -> [26] : [ A>=0 && C>=0 && free>=1 ], cost: 6+5*C

     61: evalcounterex1bcritedge2in -> evalcounterex1bcritedge2in : A'=-1+A, C'=C, E'=C, G'=-1+A, H'=C, [ A>=0 && 0>=1+C && C>=1+Q ], cost: 7

     62: evalcounterex1bcritedge2in -> evalcounterex1bcritedge2in : A'=-1+A, C'=C, E'=C, G'=-1+A, H'=C, J'=free_1, [ A>=0 && 0>=1+C && Q>=C && 0>=free_1 ], cost: 10

     63: evalcounterex1bcritedge2in -> evalcounterex1bcritedge2in : A'=-1+A, C'=1+Q, E'=C, G'=-1+A, H'=1+Q, J'=free_1, [ A>=0 && 0>=1+C && Q>=C && free_1>=1 ], cost: 12-5*C+5*Q

     64: evalcounterex1bcritedge2in -> evalcounterex1bcritedge2in : A'=-1+A, C'=1+Q, E'=C, F'=free, G'=-1+A, H'=1+Q, J'=free_1, [ A>=0 && C>=0 && 0>=free && Q>=C && free_1>=1 ], cost: 15-5*C+5*Q

     65: evalcounterex1bcritedge2in -> evalcounterex1bcritedge2in : A'=-1+A, C'=-1, E'=-1, F'=free, G'=-1+A, H'=-1, [ A>=0 && C>=0 && free>=1 && -1>=1+Q ], cost: 12+5*C

     66: evalcounterex1bcritedge2in -> evalcounterex1bcritedge2in : A'=-1+A, C'=-1, E'=-1, F'=free, G'=-1+A, H'=-1, J'=free_1, [ A>=0 && C>=0 && free>=1 && Q>=-1 && 0>=free_1 ], cost: 15+5*C

     67: evalcounterex1bcritedge2in -> evalcounterex1bcritedge2in : A'=-1+A, C'=1+Q, E'=-1, F'=free, G'=-1+A, H'=1+Q, J'=free_1, [ A>=0 && C>=0 && free>=1 && Q>=-1 && free_1>=1 ], cost: 22+5*C+5*Q

     68: evalcounterex1bcritedge2in -> [27] : [ A>=0 && 0>=1+C && Q>=C && free_1>=1 ], cost: 11-5*C+5*Q

     69: evalcounterex1bcritedge2in -> [27] : [ A>=0 && C>=0 && 0>=free && Q>=C && free_1>=1 ], cost: 14-5*C+5*Q

     70: evalcounterex1bcritedge2in -> [27] : [ A>=0 && C>=0 && free>=1 && Q>=-1 && free_1>=1 ], cost: 21+5*C+5*Q



Applied pruning (of leafs and parallel rules):

   Start location: evalcounterex1bstart

     33: evalcounterex1bstart -> evalcounterex1bcritedge2in : A'=B, C'=D, [], cost: 7

     60: evalcounterex1bcritedge2in -> [26] : [ A>=0 && C>=0 && free>=1 ], cost: 6+5*C

     63: evalcounterex1bcritedge2in -> evalcounterex1bcritedge2in : A'=-1+A, C'=1+Q, E'=C, G'=-1+A, H'=1+Q, J'=free_1, [ A>=0 && 0>=1+C && Q>=C && free_1>=1 ], cost: 12-5*C+5*Q

     64: evalcounterex1bcritedge2in -> evalcounterex1bcritedge2in : A'=-1+A, C'=1+Q, E'=C, F'=free, G'=-1+A, H'=1+Q, J'=free_1, [ A>=0 && C>=0 && 0>=free && Q>=C && free_1>=1 ], cost: 15-5*C+5*Q

     65: evalcounterex1bcritedge2in -> evalcounterex1bcritedge2in : A'=-1+A, C'=-1, E'=-1, F'=free, G'=-1+A, H'=-1, [ A>=0 && C>=0 && free>=1 && -1>=1+Q ], cost: 12+5*C

     66: evalcounterex1bcritedge2in -> evalcounterex1bcritedge2in : A'=-1+A, C'=-1, E'=-1, F'=free, G'=-1+A, H'=-1, J'=free_1, [ A>=0 && C>=0 && free>=1 && Q>=-1 && 0>=free_1 ], cost: 15+5*C

     67: evalcounterex1bcritedge2in -> evalcounterex1bcritedge2in : A'=-1+A, C'=1+Q, E'=-1, F'=free, G'=-1+A, H'=1+Q, J'=free_1, [ A>=0 && C>=0 && free>=1 && Q>=-1 && free_1>=1 ], cost: 22+5*C+5*Q

     68: evalcounterex1bcritedge2in -> [27] : [ A>=0 && 0>=1+C && Q>=C && free_1>=1 ], cost: 11-5*C+5*Q

     69: evalcounterex1bcritedge2in -> [27] : [ A>=0 && C>=0 && 0>=free && Q>=C && free_1>=1 ], cost: 14-5*C+5*Q

     70: evalcounterex1bcritedge2in -> [27] : [ A>=0 && C>=0 && free>=1 && Q>=-1 && free_1>=1 ], cost: 21+5*C+5*Q



Accelerating simple loops of location 7.

   Accelerating the following rules:

     63: evalcounterex1bcritedge2in -> evalcounterex1bcritedge2in : A'=-1+A, C'=1+Q, E'=C, G'=-1+A, H'=1+Q, J'=free_1, [ A>=0 && 0>=1+C && Q>=C && free_1>=1 ], cost: 12-5*C+5*Q

     64: evalcounterex1bcritedge2in -> evalcounterex1bcritedge2in : A'=-1+A, C'=1+Q, E'=C, F'=free, G'=-1+A, H'=1+Q, J'=free_1, [ A>=0 && C>=0 && 0>=free && Q>=C && free_1>=1 ], cost: 15-5*C+5*Q

     65: evalcounterex1bcritedge2in -> evalcounterex1bcritedge2in : A'=-1+A, C'=-1, E'=-1, F'=free, G'=-1+A, H'=-1, [ A>=0 && C>=0 && free>=1 && -1>=1+Q ], cost: 12+5*C

     66: evalcounterex1bcritedge2in -> evalcounterex1bcritedge2in : A'=-1+A, C'=-1, E'=-1, F'=free, G'=-1+A, H'=-1, J'=free_1, [ A>=0 && C>=0 && free>=1 && Q>=-1 && 0>=free_1 ], cost: 15+5*C

     67: evalcounterex1bcritedge2in -> evalcounterex1bcritedge2in : A'=-1+A, C'=1+Q, E'=-1, F'=free, G'=-1+A, H'=1+Q, J'=free_1, [ A>=0 && C>=0 && free>=1 && Q>=-1 && free_1>=1 ], cost: 22+5*C+5*Q



   Found no metering function for rule 63.

   Found no metering function for rule 64.

   Found no metering function for rule 65.

   Found no metering function for rule 66.

   Accelerated rule 67 with metering function 1+A, yielding the new rule 71.

   Removing the simple loops: 67.



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

   Start location: evalcounterex1bstart

     33: evalcounterex1bstart -> evalcounterex1bcritedge2in : A'=B, C'=D, [], cost: 7

     60: evalcounterex1bcritedge2in -> [26] : [ A>=0 && C>=0 && free>=1 ], cost: 6+5*C

     63: evalcounterex1bcritedge2in -> evalcounterex1bcritedge2in : A'=-1+A, C'=1+Q, E'=C, G'=-1+A, H'=1+Q, J'=free_1, [ A>=0 && 0>=1+C && Q>=C && free_1>=1 ], cost: 12-5*C+5*Q

     64: evalcounterex1bcritedge2in -> evalcounterex1bcritedge2in : A'=-1+A, C'=1+Q, E'=C, F'=free, G'=-1+A, H'=1+Q, J'=free_1, [ A>=0 && C>=0 && 0>=free && Q>=C && free_1>=1 ], cost: 15-5*C+5*Q

     65: evalcounterex1bcritedge2in -> evalcounterex1bcritedge2in : A'=-1+A, C'=-1, E'=-1, F'=free, G'=-1+A, H'=-1, [ A>=0 && C>=0 && free>=1 && -1>=1+Q ], cost: 12+5*C

     66: evalcounterex1bcritedge2in -> evalcounterex1bcritedge2in : A'=-1+A, C'=-1, E'=-1, F'=free, G'=-1+A, H'=-1, J'=free_1, [ A>=0 && C>=0 && free>=1 && Q>=-1 && 0>=free_1 ], cost: 15+5*C

     68: evalcounterex1bcritedge2in -> [27] : [ A>=0 && 0>=1+C && Q>=C && free_1>=1 ], cost: 11-5*C+5*Q

     69: evalcounterex1bcritedge2in -> [27] : [ A>=0 && C>=0 && 0>=free && Q>=C && free_1>=1 ], cost: 14-5*C+5*Q

     70: evalcounterex1bcritedge2in -> [27] : [ A>=0 && C>=0 && free>=1 && Q>=-1 && free_1>=1 ], cost: 21+5*C+5*Q

     71: evalcounterex1bcritedge2in -> evalcounterex1bcritedge2in : A'=-1, C'=1+Q, E'=-1, F'=free, G'=-1, H'=1+Q, J'=free_1, [ A>=0 && C>=0 && free>=1 && Q>=-1 && free_1>=1 ], cost: 27+10*(1+A)*Q+27*A



Chained accelerated rules (with incoming rules):

   Start location: evalcounterex1bstart

     33: evalcounterex1bstart -> evalcounterex1bcritedge2in : A'=B, C'=D, [], cost: 7

     72: evalcounterex1bstart -> evalcounterex1bcritedge2in : A'=-1+B, C'=1+Q, E'=D, G'=-1+B, H'=1+Q, J'=free_1, [ B>=0 && 0>=1+D && Q>=D && free_1>=1 ], cost: 19-5*D+5*Q

     73: evalcounterex1bstart -> evalcounterex1bcritedge2in : A'=-1+B, C'=1+Q, E'=D, F'=free, G'=-1+B, H'=1+Q, J'=free_1, [ B>=0 && D>=0 && 0>=free && Q>=D && free_1>=1 ], cost: 22-5*D+5*Q

     74: evalcounterex1bstart -> evalcounterex1bcritedge2in : A'=-1+B, C'=-1, E'=-1, F'=free, G'=-1+B, H'=-1, [ B>=0 && D>=0 && free>=1 && -1>=1+Q ], cost: 19+5*D

     75: evalcounterex1bstart -> evalcounterex1bcritedge2in : A'=-1+B, C'=-1, E'=-1, F'=free, G'=-1+B, H'=-1, J'=free_1, [ B>=0 && D>=0 && free>=1 && Q>=-1 && 0>=free_1 ], cost: 22+5*D

     76: evalcounterex1bstart -> evalcounterex1bcritedge2in : A'=-1, C'=1+Q, E'=-1, F'=free, G'=-1, H'=1+Q, J'=free_1, [ B>=0 && D>=0 && free>=1 && Q>=-1 && free_1>=1 ], cost: 34+27*B+10*(1+B)*Q

     60: evalcounterex1bcritedge2in -> [26] : [ A>=0 && C>=0 && free>=1 ], cost: 6+5*C

     68: evalcounterex1bcritedge2in -> [27] : [ A>=0 && 0>=1+C && Q>=C && free_1>=1 ], cost: 11-5*C+5*Q

     69: evalcounterex1bcritedge2in -> [27] : [ A>=0 && C>=0 && 0>=free && Q>=C && free_1>=1 ], cost: 14-5*C+5*Q

     70: evalcounterex1bcritedge2in -> [27] : [ A>=0 && C>=0 && free>=1 && Q>=-1 && free_1>=1 ], cost: 21+5*C+5*Q



Eliminated locations (on tree-shaped paths):

   Start location: evalcounterex1bstart

     77: evalcounterex1bstart -> [26] : A'=B, C'=D, [ B>=0 && D>=0 && free>=1 ], cost: 13+5*D

     78: evalcounterex1bstart -> [27] : A'=B, C'=D, [ B>=0 && 0>=1+D && Q>=D && free_1>=1 ], cost: 18-5*D+5*Q

     79: evalcounterex1bstart -> [27] : A'=B, C'=D, [ B>=0 && D>=0 && 0>=free && Q>=D && free_1>=1 ], cost: 21-5*D+5*Q

     80: evalcounterex1bstart -> [27] : A'=B, C'=D, [ B>=0 && D>=0 && free>=1 && Q>=-1 && free_1>=1 ], cost: 28+5*D+5*Q

     81: evalcounterex1bstart -> [26] : A'=-1+B, C'=1+Q, E'=D, G'=-1+B, H'=1+Q, J'=free_1, [ 0>=1+D && Q>=D && free_1>=1 && -1+B>=0 && 1+Q>=0 && free>=1 ], cost: 30-5*D+10*Q

     82: evalcounterex1bstart -> [27] : A'=-1+B, C'=1+Q, E'=D, G'=-1+B, H'=1+Q, J'=free_1, [ 0>=1+D && Q>=D && free_1>=1 && -1+B>=0 && 1+Q>=0 && free>=1 ], cost: 45-5*D+15*Q

     83: evalcounterex1bstart -> [29] : [ B>=0 && 0>=1+D && Q>=D && free_1>=1 ], cost: 19-5*D+5*Q

     84: evalcounterex1bstart -> [29] : [ B>=0 && D>=0 && 0>=free && Q>=D && free_1>=1 ], cost: 22-5*D+5*Q

     85: evalcounterex1bstart -> [29] : [ B>=0 && D>=0 && free>=1 && -1>=1+Q ], cost: 19+5*D

     86: evalcounterex1bstart -> [29] : [ B>=0 && D>=0 && free>=1 && Q>=-1 && 0>=free_1 ], cost: 22+5*D

     87: evalcounterex1bstart -> [29] : [ B>=0 && D>=0 && free>=1 && Q>=-1 && free_1>=1 ], cost: 34+27*B+10*(1+B)*Q



### Computing asymptotic complexity ###



Fully simplified ITS problem

   Start location: evalcounterex1bstart

     77: evalcounterex1bstart -> [26] : A'=B, C'=D, [ B>=0 && D>=0 && free>=1 ], cost: 13+5*D

     80: evalcounterex1bstart -> [27] : A'=B, C'=D, [ B>=0 && D>=0 && free>=1 && Q>=-1 && free_1>=1 ], cost: 28+5*D+5*Q

     81: evalcounterex1bstart -> [26] : A'=-1+B, C'=1+Q, E'=D, G'=-1+B, H'=1+Q, J'=free_1, [ 0>=1+D && Q>=D && free_1>=1 && -1+B>=0 && 1+Q>=0 && free>=1 ], cost: 30-5*D+10*Q

     82: evalcounterex1bstart -> [27] : A'=-1+B, C'=1+Q, E'=D, G'=-1+B, H'=1+Q, J'=free_1, [ 0>=1+D && Q>=D && free_1>=1 && -1+B>=0 && 1+Q>=0 && free>=1 ], cost: 45-5*D+15*Q

     83: evalcounterex1bstart -> [29] : [ B>=0 && 0>=1+D && Q>=D && free_1>=1 ], cost: 19-5*D+5*Q

     84: evalcounterex1bstart -> [29] : [ B>=0 && D>=0 && 0>=free && Q>=D && free_1>=1 ], cost: 22-5*D+5*Q

     85: evalcounterex1bstart -> [29] : [ B>=0 && D>=0 && free>=1 && -1>=1+Q ], cost: 19+5*D

     86: evalcounterex1bstart -> [29] : [ B>=0 && D>=0 && free>=1 && Q>=-1 && 0>=free_1 ], cost: 22+5*D

     87: evalcounterex1bstart -> [29] : [ B>=0 && D>=0 && free>=1 && Q>=-1 && free_1>=1 ], cost: 34+27*B+10*(1+B)*Q



Computing asymptotic complexity for rule 77

   Solved the limit problem by the following transformations:

      Created initial limit problem:

      13+5*D (+), 1+B (+/+!), 1+D (+/+!), free (+/+!) [not solved]



      removing all constraints (solved by SMT)

      resulting limit problem: [solved]



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

      resulting limit problem:

      [solved]



   Solution:

      D / n

      B / n

      free / n

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



Found new complexity Poly(n^1).



Computing asymptotic complexity for rule 87

   Solved the limit problem by the following transformations:

      Created initial limit problem:

      free_1 (+/+!), 34+10*B*Q+27*B+10*Q (+), 2+Q (+/+!), 1+B (+/+!), 1+D (+/+!), free (+/+!) [not solved]



      removing all constraints (solved by SMT)

      resulting limit problem: [solved]



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

      resulting limit problem:

      [solved]



   Solution:

      free_1 / n

      D / n

      B / n

      free / 1

      Q / n

   Resulting cost 34+10*n^2+37*n has complexity: Poly(n^2)



Found new complexity Poly(n^2).



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

   Complexity:  Poly(n^2)

   Cpx degree:  2

   Solved cost: 34+10*n^2+37*n

   Rule cost:   34+27*B+10*(1+B)*Q

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



WORST_CASE(Omega(n^2),?)


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

(2)
BOUNDS(n^2, INF)