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


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


WORST_CASE(NON_POLY, ?)
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(INF, INF).

(0) CpxIntTrs
(1) Loat Proof [FINISHED, 8316 ms]
(2) BOUNDS(INF, INF)


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

(0)
Obligation:
Complexity Int TRS consisting of the following rules:
f25(A, B, C, D, E, F, G, H, I, J) -> Com_1(f16(A, B, C, D, E, F, G, H, I, J)) :|: 0 >= A
f0(A, B, C, D, E, F, G, H, I, J) -> Com_1(f16(A, 1, 0, 1, N, 0, M, L, K, J)) :|: K >= 0 && L >= K && L >= 0 && M >= L && N >= 0 && M >= 0
f16(A, B, C, D, E, F, G, H, I, J) -> Com_1(f25(0, B, C, D, E, F + 1, G, H, I, J)) :|: I >= 1 && 0 >= F && 0 >= E
f16(A, B, C, D, E, F, G, H, I, J) -> Com_1(f25(N, B, C, D, E, F, G, H, I, J)) :|: I >= 1 && F >= 2 && 0 >= E && 1 >= N && N >= 0
f16(A, B, C, D, E, F, G, H, I, J) -> Com_1(f25(1, B, C + 1, D, E, F, G, H, I, J)) :|: I >= 1 && 0 >= E && 0 >= C && F >= 1 && F <= 1
f16(A, B, C, D, E, F, G, H, I, J) -> Com_1(f25(0, B, 0, D - 1, E, F, G, H, I, J)) :|: I >= 1 && 0 >= E && D >= 1 && F >= 1 && F <= 1 && C >= 1 && C <= 1
f16(A, B, C, D, E, F, G, H, I, J) -> Com_1(f25(M, B + 1, 0, B + 1, N, 0, G, H, I, J)) :|: I >= 1 && 0 >= E && M >= 0 && 1 >= M && C >= 2 && N >= 0 && F >= 1 && F <= 1
f16(A, B, C, D, E, F, G, H, I, J) -> Com_1(f25(M, B + 1, 0, B + 1, N, 0, G, H, I, J)) :|: I >= 1 && 0 >= E && 0 >= D && M >= 0 && 1 >= M && N >= 0 && F >= 1 && F <= 1 && C >= 1 && C <= 1
f16(A, B, C, D, E, F, G, H, I, J) -> Com_1(f25(N, B, C, D, E - 1, F, G, H, I, J)) :|: I >= 1 && E >= 1 && 1 >= N && N >= 0
f25(A, B, C, D, E, F, G, H, I, J) -> Com_1(f50(A, B, C, D, E, F + 1, G, H, I, 0)) :|: A >= 1 && 0 >= F && 0 >= E
f25(A, B, C, D, E, F, G, H, I, J) -> Com_1(f50(A, B, C, D, E, F, G, H, I, N)) :|: A >= 1 && F >= 2 && 0 >= E && 1 >= N && N >= 0
f25(A, B, C, D, E, F, G, H, I, J) -> Com_1(f50(A, B, C + 1, D, E, F, G, H, I, 1)) :|: A >= 1 && 0 >= E && 0 >= C && F >= 1 && F <= 1
f25(A, B, C, D, E, F, G, H, I, J) -> Com_1(f50(A, B, 0, D - 1, E, F, G, H, I, 0)) :|: A >= 1 && 0 >= E && D >= 1 && F >= 1 && F <= 1 && C >= 1 && C <= 1
f25(A, B, C, D, E, F, G, H, I, J) -> Com_1(f50(A, B + 1, 0, B + 1, N, 0, G, H, I, M)) :|: A >= 1 && 0 >= E && M >= 0 && 1 >= M && C >= 2 && N >= 0 && F >= 1 && F <= 1
f25(A, B, C, D, E, F, G, H, I, J) -> Com_1(f50(A, B + 1, 0, B + 1, N, 0, G, H, I, M)) :|: A >= 1 && 0 >= E && 0 >= D && M >= 0 && 1 >= M && N >= 0 && F >= 1 && F <= 1 && C >= 1 && C <= 1
f25(A, B, C, D, E, F, G, H, I, J) -> Com_1(f50(A, B, C, D, E - 1, F, G, H, I, N)) :|: A >= 1 && E >= 1 && 1 >= N && N >= 0
f50(A, B, C, D, E, F, G, H, I, J) -> Com_1(f16(A, B, C, D, E, F, G, H, I, J)) :|: I >= H && J >= 1
f50(A, B, C, D, E, F, G, H, I, J) -> Com_1(f16(A, B, C, D, E, F, G, H, I + 1, J)) :|: H >= I + 1 && J >= 1
f50(A, B, C, D, E, F, G, H, I, J) -> Com_1(f16(A, B, C, D, E, F, G, H, I - 1, J)) :|: 0 >= J
f16(A, B, C, D, E, F, G, H, I, J) -> Com_1(f73(A, B, C, D, E, F, G, H, I, J)) :|: 0 >= I

The start-symbols are:[f0_10]


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

(1) Loat Proof (FINISHED)


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



Initial linear ITS problem

   Start location: f0

      0: f25 -> f16 : [ 0>=A ], cost: 1

      9: f25 -> f50 : F'=1+F, J'=0, [ A>=1 && 0>=F && 0>=E ], cost: 1

     10: f25 -> f50 : J'=free_10, [ A>=1 && F>=2 && 0>=E && 1>=free_10 && free_10>=0 ], cost: 1

     11: f25 -> f50 : C'=1+C, J'=1, [ A>=1 && 0>=E && 0>=C && F==1 ], cost: 1

     12: f25 -> f50 : C'=0, D'=-1+D, J'=0, [ A>=1 && 0>=E && D>=1 && F==1 && C==1 ], cost: 1

     13: f25 -> f50 : B'=1+B, C'=0, D'=1+B, E'=free_12, F'=0, J'=free_11, [ A>=1 && 0>=E && free_11>=0 && 1>=free_11 && C>=2 && free_12>=0 && F==1 ], cost: 1

     14: f25 -> f50 : B'=1+B, C'=0, D'=1+B, E'=free_14, F'=0, J'=free_13, [ A>=1 && 0>=E && 0>=D && free_13>=0 && 1>=free_13 && free_14>=0 && F==1 && C==1 ], cost: 1

     15: f25 -> f50 : E'=-1+E, J'=free_15, [ A>=1 && E>=1 && 1>=free_15 && free_15>=0 ], cost: 1

      1: f0 -> f16 : B'=1, C'=0, D'=1, E'=free_1, F'=0, G'=free, H'=free_3, Q'=free_2, [ free_2>=0 && free_3>=free_2 && free_3>=0 && free>=free_3 && free_1>=0 && free>=0 ], cost: 1

      2: f16 -> f25 : A'=0, F'=1+F, [ Q>=1 && 0>=F && 0>=E ], cost: 1

      3: f16 -> f25 : A'=free_4, [ Q>=1 && F>=2 && 0>=E && 1>=free_4 && free_4>=0 ], cost: 1

      4: f16 -> f25 : A'=1, C'=1+C, [ Q>=1 && 0>=E && 0>=C && F==1 ], cost: 1

      5: f16 -> f25 : A'=0, C'=0, D'=-1+D, [ Q>=1 && 0>=E && D>=1 && F==1 && C==1 ], cost: 1

      6: f16 -> f25 : A'=free_6, B'=1+B, C'=0, D'=1+B, E'=free_5, F'=0, [ Q>=1 && 0>=E && free_6>=0 && 1>=free_6 && C>=2 && free_5>=0 && F==1 ], cost: 1

      7: f16 -> f25 : A'=free_8, B'=1+B, C'=0, D'=1+B, E'=free_7, F'=0, [ Q>=1 && 0>=E && 0>=D && free_8>=0 && 1>=free_8 && free_7>=0 && F==1 && C==1 ], cost: 1

      8: f16 -> f25 : A'=free_9, E'=-1+E, [ Q>=1 && E>=1 && 1>=free_9 && free_9>=0 ], cost: 1

     19: f16 -> f73 : [ 0>=Q ], cost: 1

     16: f50 -> f16 : [ Q>=H && J>=1 ], cost: 1

     17: f50 -> f16 : Q'=1+Q, [ H>=1+Q && J>=1 ], cost: 1

     18: f50 -> f16 : Q'=-1+Q, [ 0>=J ], cost: 1



Checking for constant complexity:

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

      1: f0 -> f16 : B'=1, C'=0, D'=1, E'=free_1, F'=0, G'=free, H'=free_3, Q'=free_2, [ free_2>=0 && free_3>=free_2 && free_3>=0 && free>=free_3 && free_1>=0 && free>=0 ], cost: 1



Removed unreachable and leaf rules:

   Start location: f0

      0: f25 -> f16 : [ 0>=A ], cost: 1

      9: f25 -> f50 : F'=1+F, J'=0, [ A>=1 && 0>=F && 0>=E ], cost: 1

     10: f25 -> f50 : J'=free_10, [ A>=1 && F>=2 && 0>=E && 1>=free_10 && free_10>=0 ], cost: 1

     11: f25 -> f50 : C'=1+C, J'=1, [ A>=1 && 0>=E && 0>=C && F==1 ], cost: 1

     12: f25 -> f50 : C'=0, D'=-1+D, J'=0, [ A>=1 && 0>=E && D>=1 && F==1 && C==1 ], cost: 1

     13: f25 -> f50 : B'=1+B, C'=0, D'=1+B, E'=free_12, F'=0, J'=free_11, [ A>=1 && 0>=E && free_11>=0 && 1>=free_11 && C>=2 && free_12>=0 && F==1 ], cost: 1

     14: f25 -> f50 : B'=1+B, C'=0, D'=1+B, E'=free_14, F'=0, J'=free_13, [ A>=1 && 0>=E && 0>=D && free_13>=0 && 1>=free_13 && free_14>=0 && F==1 && C==1 ], cost: 1

     15: f25 -> f50 : E'=-1+E, J'=free_15, [ A>=1 && E>=1 && 1>=free_15 && free_15>=0 ], cost: 1

      1: f0 -> f16 : B'=1, C'=0, D'=1, E'=free_1, F'=0, G'=free, H'=free_3, Q'=free_2, [ free_2>=0 && free_3>=free_2 && free_3>=0 && free>=free_3 && free_1>=0 && free>=0 ], cost: 1

      2: f16 -> f25 : A'=0, F'=1+F, [ Q>=1 && 0>=F && 0>=E ], cost: 1

      3: f16 -> f25 : A'=free_4, [ Q>=1 && F>=2 && 0>=E && 1>=free_4 && free_4>=0 ], cost: 1

      4: f16 -> f25 : A'=1, C'=1+C, [ Q>=1 && 0>=E && 0>=C && F==1 ], cost: 1

      5: f16 -> f25 : A'=0, C'=0, D'=-1+D, [ Q>=1 && 0>=E && D>=1 && F==1 && C==1 ], cost: 1

      6: f16 -> f25 : A'=free_6, B'=1+B, C'=0, D'=1+B, E'=free_5, F'=0, [ Q>=1 && 0>=E && free_6>=0 && 1>=free_6 && C>=2 && free_5>=0 && F==1 ], cost: 1

      7: f16 -> f25 : A'=free_8, B'=1+B, C'=0, D'=1+B, E'=free_7, F'=0, [ Q>=1 && 0>=E && 0>=D && free_8>=0 && 1>=free_8 && free_7>=0 && F==1 && C==1 ], cost: 1

      8: f16 -> f25 : A'=free_9, E'=-1+E, [ Q>=1 && E>=1 && 1>=free_9 && free_9>=0 ], cost: 1

     16: f50 -> f16 : [ Q>=H && J>=1 ], cost: 1

     17: f50 -> f16 : Q'=1+Q, [ H>=1+Q && J>=1 ], cost: 1

     18: f50 -> f16 : Q'=-1+Q, [ 0>=J ], cost: 1



### Simplification by acceleration and chaining ###



Eliminated locations (on tree-shaped paths):

   Start location: f0

      1: f0 -> f16 : B'=1, C'=0, D'=1, E'=free_1, F'=0, G'=free, H'=free_3, Q'=free_2, [ free_2>=0 && free_3>=free_2 && free>=free_3 && free_1>=0 ], cost: 1

     20: f16 -> f16 : A'=0, F'=1+F, [ Q>=1 && 0>=F && 0>=E ], cost: 2

     21: f16 -> f16 : A'=free_4, [ Q>=1 && F>=2 && 0>=E && free_4>=0 && 0>=free_4 ], cost: 2

     22: f16 -> f50 : A'=free_4, J'=free_10, [ Q>=1 && F>=2 && 0>=E && 1>=free_4 && free_4>=1 && 1>=free_10 && free_10>=0 ], cost: 2

     23: f16 -> f50 : A'=1, C'=2+C, J'=1, [ Q>=1 && 0>=E && F==1 && 0>=1+C ], cost: 2

     24: f16 -> f50 : A'=1, C'=0, D'=-1+D, J'=0, [ Q>=1 && 0>=E && F==1 && D>=1 && 1+C==1 ], cost: 2

     25: f16 -> f50 : A'=1, B'=1+B, C'=0, D'=1+B, E'=free_14, F'=0, J'=free_13, [ Q>=1 && 0>=E && F==1 && 0>=D && free_13>=0 && 1>=free_13 && free_14>=0 && 1+C==1 ], cost: 2

     26: f16 -> f16 : A'=0, C'=0, D'=-1+D, [ Q>=1 && 0>=E && D>=1 && F==1 && C==1 ], cost: 2

     27: f16 -> f16 : A'=free_6, B'=1+B, C'=0, D'=1+B, E'=free_5, F'=0, [ Q>=1 && 0>=E && free_6>=0 && C>=2 && free_5>=0 && F==1 && 0>=free_6 ], cost: 2

     28: f16 -> f50 : A'=free_6, B'=1+B, C'=0, D'=1+B, E'=free_5, F'=1, J'=0, [ Q>=1 && 0>=E && 1>=free_6 && C>=2 && free_5>=0 && F==1 && free_6>=1 && 0>=free_5 ], cost: 2

     29: f16 -> f50 : A'=free_6, B'=1+B, C'=0, D'=1+B, E'=-1+free_5, F'=0, J'=free_15, [ Q>=1 && 0>=E && 1>=free_6 && C>=2 && F==1 && free_6>=1 && free_5>=1 && 1>=free_15 && free_15>=0 ], cost: 2

     30: f16 -> f16 : A'=free_8, B'=1+B, C'=0, D'=1+B, E'=free_7, F'=0, [ Q>=1 && 0>=E && 0>=D && free_8>=0 && free_7>=0 && F==1 && C==1 && 0>=free_8 ], cost: 2

     31: f16 -> f50 : A'=free_8, B'=1+B, C'=0, D'=1+B, E'=free_7, F'=1, J'=0, [ Q>=1 && 0>=E && 0>=D && 1>=free_8 && free_7>=0 && F==1 && C==1 && free_8>=1 && 0>=free_7 ], cost: 2

     32: f16 -> f50 : A'=free_8, B'=1+B, C'=0, D'=1+B, E'=-1+free_7, F'=0, J'=free_15, [ Q>=1 && 0>=E && 0>=D && 1>=free_8 && F==1 && C==1 && free_8>=1 && free_7>=1 && 1>=free_15 && free_15>=0 ], cost: 2

     33: f16 -> f16 : A'=free_9, E'=-1+E, [ Q>=1 && E>=1 && free_9>=0 && 0>=free_9 ], cost: 2

     34: f16 -> f50 : A'=free_9, E'=-1+E, F'=1+F, J'=0, [ Q>=1 && E>=1 && 1>=free_9 && free_9>=1 && 0>=F && 0>=-1+E ], cost: 2

     35: f16 -> f50 : A'=free_9, E'=-1+E, J'=free_10, [ Q>=1 && E>=1 && 1>=free_9 && free_9>=1 && F>=2 && 0>=-1+E && 1>=free_10 && free_10>=0 ], cost: 2

     36: f16 -> f50 : A'=free_9, C'=1+C, E'=-1+E, J'=1, [ Q>=1 && E>=1 && 1>=free_9 && free_9>=1 && 0>=-1+E && 0>=C && F==1 ], cost: 2

     37: f16 -> f50 : A'=free_9, C'=0, D'=-1+D, E'=-1+E, J'=0, [ Q>=1 && E>=1 && 1>=free_9 && free_9>=1 && 0>=-1+E && D>=1 && F==1 && C==1 ], cost: 2

     38: f16 -> f50 : A'=free_9, B'=1+B, C'=0, D'=1+B, E'=free_12, F'=0, J'=free_11, [ Q>=1 && E>=1 && 1>=free_9 && free_9>=1 && 0>=-1+E && free_11>=0 && 1>=free_11 && C>=2 && free_12>=0 && F==1 ], cost: 2

     39: f16 -> f50 : A'=free_9, B'=1+B, C'=0, D'=1+B, E'=free_14, F'=0, J'=free_13, [ Q>=1 && E>=1 && 1>=free_9 && free_9>=1 && 0>=-1+E && 0>=D && free_13>=0 && 1>=free_13 && free_14>=0 && F==1 && C==1 ], cost: 2

     40: f16 -> f50 : A'=free_9, E'=-2+E, J'=free_15, [ Q>=1 && 1>=free_9 && free_9>=1 && -1+E>=1 && 1>=free_15 && free_15>=0 ], cost: 2

     16: f50 -> f16 : [ Q>=H && J>=1 ], cost: 1

     17: f50 -> f16 : Q'=1+Q, [ H>=1+Q && J>=1 ], cost: 1

     18: f50 -> f16 : Q'=-1+Q, [ 0>=J ], cost: 1



Accelerating simple loops of location 2.

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

   Accelerating the following rules:

     20: f16 -> f16 : A'=0, F'=1+F, [ Q>=1 && 0>=F && 0>=E ], cost: 2

     21: f16 -> f16 : A'=0, [ Q>=1 && F>=2 && 0>=E ], cost: 2

     26: f16 -> f16 : A'=0, C'=0, D'=-1+D, [ Q>=1 && 0>=E && D>=1 && F==1 && C==1 ], cost: 2

     27: f16 -> f16 : A'=0, B'=1+B, C'=0, D'=1+B, E'=free_5, F'=0, [ Q>=1 && 0>=E && C>=2 && free_5>=0 && F==1 ], cost: 2

     30: f16 -> f16 : A'=0, B'=1+B, C'=0, D'=1+B, E'=free_7, F'=0, [ Q>=1 && 0>=E && 0>=D && free_7>=0 && F==1 && C==1 ], cost: 2

     33: f16 -> f16 : A'=0, E'=-1+E, [ Q>=1 && E>=1 ], cost: 2



   Accelerated rule 20 with metering function 1-F, yielding the new rule 41.

   Accelerated rule 21 with NONTERM, yielding the new rule 42.

   Accelerated rule 26 with metering function -1+C, yielding the new rule 43.

   Accelerated rule 27 with metering function -1+F, yielding the new rule 44.

   Accelerated rule 30 with metering function meter (where 2*meter==-2+F+C), yielding the new rule 45.

   Accelerated rule 33 with metering function E, yielding the new rule 46.

   Nested simple loops 27 (outer loop) and 46 (inner loop) with metering function -1+F, resulting in the new rules: 47.

   Nested simple loops 30 (outer loop) and 46 (inner loop) with metering function meter_1 (where 2*meter_1==-2+F+C), resulting in the new rules: 48.

   Removing the simple loops: 20 21 26 27 30 33.



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

   Start location: f0

      1: f0 -> f16 : B'=1, C'=0, D'=1, E'=free_1, F'=0, G'=free, H'=free_3, Q'=free_2, [ free_2>=0 && free_3>=free_2 && free>=free_3 && free_1>=0 ], cost: 1

     22: f16 -> f50 : A'=free_4, J'=free_10, [ Q>=1 && F>=2 && 0>=E && 1>=free_4 && free_4>=1 && 1>=free_10 && free_10>=0 ], cost: 2

     23: f16 -> f50 : A'=1, C'=2+C, J'=1, [ Q>=1 && 0>=E && F==1 && 0>=1+C ], cost: 2

     24: f16 -> f50 : A'=1, C'=0, D'=-1+D, J'=0, [ Q>=1 && 0>=E && F==1 && D>=1 && 1+C==1 ], cost: 2

     25: f16 -> f50 : A'=1, B'=1+B, C'=0, D'=1+B, E'=free_14, F'=0, J'=free_13, [ Q>=1 && 0>=E && F==1 && 0>=D && free_13>=0 && 1>=free_13 && free_14>=0 && 1+C==1 ], cost: 2

     28: f16 -> f50 : A'=free_6, B'=1+B, C'=0, D'=1+B, E'=free_5, F'=1, J'=0, [ Q>=1 && 0>=E && 1>=free_6 && C>=2 && free_5>=0 && F==1 && free_6>=1 && 0>=free_5 ], cost: 2

     29: f16 -> f50 : A'=free_6, B'=1+B, C'=0, D'=1+B, E'=-1+free_5, F'=0, J'=free_15, [ Q>=1 && 0>=E && 1>=free_6 && C>=2 && F==1 && free_6>=1 && free_5>=1 && 1>=free_15 && free_15>=0 ], cost: 2

     31: f16 -> f50 : A'=free_8, B'=1+B, C'=0, D'=1+B, E'=free_7, F'=1, J'=0, [ Q>=1 && 0>=E && 0>=D && 1>=free_8 && free_7>=0 && F==1 && C==1 && free_8>=1 && 0>=free_7 ], cost: 2

     32: f16 -> f50 : A'=free_8, B'=1+B, C'=0, D'=1+B, E'=-1+free_7, F'=0, J'=free_15, [ Q>=1 && 0>=E && 0>=D && 1>=free_8 && F==1 && C==1 && free_8>=1 && free_7>=1 && 1>=free_15 && free_15>=0 ], cost: 2

     34: f16 -> f50 : A'=free_9, E'=-1+E, F'=1+F, J'=0, [ Q>=1 && E>=1 && 1>=free_9 && free_9>=1 && 0>=F && 0>=-1+E ], cost: 2

     35: f16 -> f50 : A'=free_9, E'=-1+E, J'=free_10, [ Q>=1 && E>=1 && 1>=free_9 && free_9>=1 && F>=2 && 0>=-1+E && 1>=free_10 && free_10>=0 ], cost: 2

     36: f16 -> f50 : A'=free_9, C'=1+C, E'=-1+E, J'=1, [ Q>=1 && E>=1 && 1>=free_9 && free_9>=1 && 0>=-1+E && 0>=C && F==1 ], cost: 2

     37: f16 -> f50 : A'=free_9, C'=0, D'=-1+D, E'=-1+E, J'=0, [ Q>=1 && E>=1 && 1>=free_9 && free_9>=1 && 0>=-1+E && D>=1 && F==1 && C==1 ], cost: 2

     38: f16 -> f50 : A'=free_9, B'=1+B, C'=0, D'=1+B, E'=free_12, F'=0, J'=free_11, [ Q>=1 && E>=1 && 1>=free_9 && free_9>=1 && 0>=-1+E && free_11>=0 && 1>=free_11 && C>=2 && free_12>=0 && F==1 ], cost: 2

     39: f16 -> f50 : A'=free_9, B'=1+B, C'=0, D'=1+B, E'=free_14, F'=0, J'=free_13, [ Q>=1 && E>=1 && 1>=free_9 && free_9>=1 && 0>=-1+E && 0>=D && free_13>=0 && 1>=free_13 && free_14>=0 && F==1 && C==1 ], cost: 2

     40: f16 -> f50 : A'=free_9, E'=-2+E, J'=free_15, [ Q>=1 && 1>=free_9 && free_9>=1 && -1+E>=1 && 1>=free_15 && free_15>=0 ], cost: 2

     41: f16 -> f16 : A'=0, F'=1, [ Q>=1 && 0>=F && 0>=E ], cost: 2-2*F

     42: f16 -> [5] : [ Q>=1 && F>=2 && 0>=E ], cost: NONTERM

     43: f16 -> f16 : A'=0, C'=0, D'=1-C+D, [ Q>=1 && 0>=E && D>=1 && F==1 && C==1 && -1+C>=1 ], cost: -2+2*C

     44: f16 -> f16 : A'=0, B'=-1+F+B, C'=0, D'=-1+F+B, E'=free_5, F'=0, [ Q>=1 && 0>=E && C>=2 && free_5>=0 && F==1 && -1+F>=1 ], cost: -2+2*F

     45: f16 -> f16 : A'=0, B'=meter+B, C'=0, D'=meter+B, E'=free_7, F'=0, [ Q>=1 && 0>=E && 0>=D && free_7>=0 && F==1 && C==1 && 2*meter==-2+F+C && meter>=1 ], cost: 2*meter

     46: f16 -> f16 : A'=0, E'=0, [ Q>=1 && E>=1 ], cost: 2*E

     47: f16 -> f16 : A'=0, B'=-1+F+B, C'=0, D'=-1+F+B, E'=free_5, F'=0, [ Q>=1 && E>=1 && C>=2 && free_5>=0 && F==1 && -1+F>=1 ], cost: -2+2*F+2*free_5*(-1+F)

     48: f16 -> f16 : A'=0, B'=meter_1+B, C'=0, D'=meter_1+B, E'=free_7, F'=0, [ Q>=1 && E>=1 && 0>=D && free_7>=0 && F==1 && C==1 && 2*meter_1==-2+F+C && meter_1>=1 ], cost: 2*meter_1+2*meter_1*free_7

     16: f50 -> f16 : [ Q>=H && J>=1 ], cost: 1

     17: f50 -> f16 : Q'=1+Q, [ H>=1+Q && J>=1 ], cost: 1

     18: f50 -> f16 : Q'=-1+Q, [ 0>=J ], cost: 1



Chained accelerated rules (with incoming rules):

   Start location: f0

      1: f0 -> f16 : B'=1, C'=0, D'=1, E'=free_1, F'=0, G'=free, H'=free_3, Q'=free_2, [ free_2>=0 && free_3>=free_2 && free>=free_3 && free_1>=0 ], cost: 1

     49: f0 -> f16 : A'=0, B'=1, C'=0, D'=1, E'=0, F'=1, G'=free, H'=free_3, Q'=free_2, [ free_3>=free_2 && free>=free_3 && free_2>=1 ], cost: 3

     56: f0 -> f16 : A'=0, B'=1, C'=0, D'=1, E'=0, F'=0, G'=free, H'=free_3, Q'=free_2, [ free_3>=free_2 && free>=free_3 && free_2>=1 && free_1>=1 ], cost: 1+2*free_1

     22: f16 -> f50 : A'=free_4, J'=free_10, [ Q>=1 && F>=2 && 0>=E && 1>=free_4 && free_4>=1 && 1>=free_10 && free_10>=0 ], cost: 2

     23: f16 -> f50 : A'=1, C'=2+C, J'=1, [ Q>=1 && 0>=E && F==1 && 0>=1+C ], cost: 2

     24: f16 -> f50 : A'=1, C'=0, D'=-1+D, J'=0, [ Q>=1 && 0>=E && F==1 && D>=1 && 1+C==1 ], cost: 2

     25: f16 -> f50 : A'=1, B'=1+B, C'=0, D'=1+B, E'=free_14, F'=0, J'=free_13, [ Q>=1 && 0>=E && F==1 && 0>=D && free_13>=0 && 1>=free_13 && free_14>=0 && 1+C==1 ], cost: 2

     28: f16 -> f50 : A'=free_6, B'=1+B, C'=0, D'=1+B, E'=free_5, F'=1, J'=0, [ Q>=1 && 0>=E && 1>=free_6 && C>=2 && free_5>=0 && F==1 && free_6>=1 && 0>=free_5 ], cost: 2

     29: f16 -> f50 : A'=free_6, B'=1+B, C'=0, D'=1+B, E'=-1+free_5, F'=0, J'=free_15, [ Q>=1 && 0>=E && 1>=free_6 && C>=2 && F==1 && free_6>=1 && free_5>=1 && 1>=free_15 && free_15>=0 ], cost: 2

     31: f16 -> f50 : A'=free_8, B'=1+B, C'=0, D'=1+B, E'=free_7, F'=1, J'=0, [ Q>=1 && 0>=E && 0>=D && 1>=free_8 && free_7>=0 && F==1 && C==1 && free_8>=1 && 0>=free_7 ], cost: 2

     32: f16 -> f50 : A'=free_8, B'=1+B, C'=0, D'=1+B, E'=-1+free_7, F'=0, J'=free_15, [ Q>=1 && 0>=E && 0>=D && 1>=free_8 && F==1 && C==1 && free_8>=1 && free_7>=1 && 1>=free_15 && free_15>=0 ], cost: 2

     34: f16 -> f50 : A'=free_9, E'=-1+E, F'=1+F, J'=0, [ Q>=1 && E>=1 && 1>=free_9 && free_9>=1 && 0>=F && 0>=-1+E ], cost: 2

     35: f16 -> f50 : A'=free_9, E'=-1+E, J'=free_10, [ Q>=1 && E>=1 && 1>=free_9 && free_9>=1 && F>=2 && 0>=-1+E && 1>=free_10 && free_10>=0 ], cost: 2

     36: f16 -> f50 : A'=free_9, C'=1+C, E'=-1+E, J'=1, [ Q>=1 && E>=1 && 1>=free_9 && free_9>=1 && 0>=-1+E && 0>=C && F==1 ], cost: 2

     37: f16 -> f50 : A'=free_9, C'=0, D'=-1+D, E'=-1+E, J'=0, [ Q>=1 && E>=1 && 1>=free_9 && free_9>=1 && 0>=-1+E && D>=1 && F==1 && C==1 ], cost: 2

     38: f16 -> f50 : A'=free_9, B'=1+B, C'=0, D'=1+B, E'=free_12, F'=0, J'=free_11, [ Q>=1 && E>=1 && 1>=free_9 && free_9>=1 && 0>=-1+E && free_11>=0 && 1>=free_11 && C>=2 && free_12>=0 && F==1 ], cost: 2

     39: f16 -> f50 : A'=free_9, B'=1+B, C'=0, D'=1+B, E'=free_14, F'=0, J'=free_13, [ Q>=1 && E>=1 && 1>=free_9 && free_9>=1 && 0>=-1+E && 0>=D && free_13>=0 && 1>=free_13 && free_14>=0 && F==1 && C==1 ], cost: 2

     40: f16 -> f50 : A'=free_9, E'=-2+E, J'=free_15, [ Q>=1 && 1>=free_9 && free_9>=1 && -1+E>=1 && 1>=free_15 && free_15>=0 ], cost: 2

     16: f50 -> f16 : [ Q>=H && J>=1 ], cost: 1

     17: f50 -> f16 : Q'=1+Q, [ H>=1+Q && J>=1 ], cost: 1

     18: f50 -> f16 : Q'=-1+Q, [ 0>=J ], cost: 1

     50: f50 -> f16 : A'=0, F'=1, [ Q>=H && J>=1 && Q>=1 && 0>=F && 0>=E ], cost: 3-2*F

     51: f50 -> f16 : A'=0, F'=1, Q'=1+Q, [ H>=1+Q && J>=1 && 1+Q>=1 && 0>=F && 0>=E ], cost: 3-2*F

     52: f50 -> f16 : A'=0, F'=1, Q'=-1+Q, [ 0>=J && -1+Q>=1 && 0>=F && 0>=E ], cost: 3-2*F

     53: f50 -> [5] : [ Q>=H && J>=1 && Q>=1 && F>=2 && 0>=E ], cost: NONTERM

     54: f50 -> [5] : Q'=1+Q, [ H>=1+Q && J>=1 && 1+Q>=1 && F>=2 && 0>=E ], cost: NONTERM

     55: f50 -> [5] : Q'=-1+Q, [ 0>=J && -1+Q>=1 && F>=2 && 0>=E ], cost: NONTERM

     57: f50 -> f16 : A'=0, E'=0, [ Q>=H && J>=1 && Q>=1 && E>=1 ], cost: 1+2*E

     58: f50 -> f16 : A'=0, E'=0, Q'=1+Q, [ H>=1+Q && J>=1 && 1+Q>=1 && E>=1 ], cost: 1+2*E

     59: f50 -> f16 : A'=0, E'=0, Q'=-1+Q, [ 0>=J && -1+Q>=1 && E>=1 ], cost: 1+2*E



Eliminated locations (on tree-shaped paths):

   Start location: f0

      1: f0 -> f16 : B'=1, C'=0, D'=1, E'=free_1, F'=0, G'=free, H'=free_3, Q'=free_2, [ free_2>=0 && free_3>=free_2 && free>=free_3 && free_1>=0 ], cost: 1

     49: f0 -> f16 : A'=0, B'=1, C'=0, D'=1, E'=0, F'=1, G'=free, H'=free_3, Q'=free_2, [ free_3>=free_2 && free>=free_3 && free_2>=1 ], cost: 3

     56: f0 -> f16 : A'=0, B'=1, C'=0, D'=1, E'=0, F'=0, G'=free, H'=free_3, Q'=free_2, [ free_3>=free_2 && free>=free_3 && free_2>=1 && free_1>=1 ], cost: 1+2*free_1

     60: f16 -> f16 : A'=free_4, J'=free_10, [ Q>=1 && F>=2 && 0>=E && 1>=free_4 && free_4>=1 && 1>=free_10 && Q>=H && free_10>=1 ], cost: 3

     61: f16 -> f16 : A'=free_4, Q'=1+Q, J'=free_10, [ Q>=1 && F>=2 && 0>=E && 1>=free_4 && free_4>=1 && 1>=free_10 && H>=1+Q && free_10>=1 ], cost: 3

     62: f16 -> f16 : A'=free_4, Q'=-1+Q, J'=free_10, [ Q>=1 && F>=2 && 0>=E && 1>=free_4 && free_4>=1 && free_10>=0 && 0>=free_10 ], cost: 3

     63: f16 -> [5] : A'=free_4, J'=free_10, [ Q>=1 && F>=2 && 0>=E && 1>=free_4 && free_4>=1 && 1>=free_10 && Q>=H && free_10>=1 ], cost: NONTERM

     64: f16 -> [5] : A'=free_4, Q'=1+Q, J'=free_10, [ Q>=1 && F>=2 && 0>=E && 1>=free_4 && free_4>=1 && 1>=free_10 && H>=1+Q && free_10>=1 ], cost: NONTERM

     65: f16 -> [5] : A'=free_4, Q'=-1+Q, J'=free_10, [ F>=2 && 0>=E && 1>=free_4 && free_4>=1 && free_10>=0 && 0>=free_10 && -1+Q>=1 ], cost: NONTERM

     66: f16 -> f16 : A'=1, C'=2+C, J'=1, [ Q>=1 && 0>=E && F==1 && 0>=1+C && Q>=H ], cost: 3

     67: f16 -> f16 : A'=1, C'=2+C, Q'=1+Q, J'=1, [ Q>=1 && 0>=E && F==1 && 0>=1+C && H>=1+Q ], cost: 3

     68: f16 -> f16 : A'=1, C'=0, D'=-1+D, Q'=-1+Q, J'=0, [ Q>=1 && 0>=E && F==1 && D>=1 && 1+C==1 ], cost: 3

     69: f16 -> f16 : A'=1, B'=1+B, C'=0, D'=1+B, E'=free_14, F'=0, J'=free_13, [ Q>=1 && 0>=E && F==1 && 0>=D && 1>=free_13 && free_14>=0 && 1+C==1 && Q>=H && free_13>=1 ], cost: 3

     70: f16 -> f16 : A'=1, B'=1+B, C'=0, D'=1+B, E'=free_14, F'=0, Q'=1+Q, J'=free_13, [ Q>=1 && 0>=E && F==1 && 0>=D && 1>=free_13 && free_14>=0 && 1+C==1 && H>=1+Q && free_13>=1 ], cost: 3

     71: f16 -> f16 : A'=1, B'=1+B, C'=0, D'=1+B, E'=free_14, F'=0, Q'=-1+Q, J'=free_13, [ Q>=1 && 0>=E && F==1 && 0>=D && free_13>=0 && free_14>=0 && 1+C==1 && 0>=free_13 ], cost: 3

     72: f16 -> f16 : A'=0, B'=1+B, C'=0, D'=1+B, E'=free_14, F'=1, J'=free_13, [ Q>=1 && 0>=E && F==1 && 0>=D && 1>=free_13 && free_14>=0 && 1+C==1 && Q>=H && free_13>=1 && 0>=free_14 ], cost: 5

     73: f16 -> f16 : A'=0, B'=1+B, C'=0, D'=1+B, E'=free_14, F'=1, Q'=1+Q, J'=free_13, [ Q>=1 && 0>=E && F==1 && 0>=D && 1>=free_13 && free_14>=0 && 1+C==1 && H>=1+Q && free_13>=1 && 0>=free_14 ], cost: 5

     74: f16 -> f16 : A'=0, B'=1+B, C'=0, D'=1+B, E'=free_14, F'=1, Q'=-1+Q, J'=free_13, [ 0>=E && F==1 && 0>=D && free_13>=0 && free_14>=0 && 1+C==1 && 0>=free_13 && -1+Q>=1 && 0>=free_14 ], cost: 5

     75: f16 -> f16 : A'=0, B'=1+B, C'=0, D'=1+B, E'=0, F'=0, J'=free_13, [ Q>=1 && 0>=E && F==1 && 0>=D && 1>=free_13 && 1+C==1 && Q>=H && free_13>=1 && free_14>=1 ], cost: 3+2*free_14

     76: f16 -> f16 : A'=0, B'=1+B, C'=0, D'=1+B, E'=0, F'=0, Q'=1+Q, J'=free_13, [ Q>=1 && 0>=E && F==1 && 0>=D && 1>=free_13 && 1+C==1 && H>=1+Q && free_13>=1 && free_14>=1 ], cost: 3+2*free_14

     77: f16 -> f16 : A'=0, B'=1+B, C'=0, D'=1+B, E'=0, F'=0, Q'=-1+Q, J'=free_13, [ 0>=E && F==1 && 0>=D && free_13>=0 && 1+C==1 && 0>=free_13 && -1+Q>=1 && free_14>=1 ], cost: 3+2*free_14

     78: f16 -> f16 : A'=free_6, B'=1+B, C'=0, D'=1+B, E'=free_5, F'=1, Q'=-1+Q, J'=0, [ Q>=1 && 0>=E && 1>=free_6 && C>=2 && free_5>=0 && F==1 && free_6>=1 && 0>=free_5 ], cost: 3

     79: f16 -> f16 : A'=free_6, B'=1+B, C'=0, D'=1+B, E'=-1+free_5, F'=0, J'=free_15, [ Q>=1 && 0>=E && 1>=free_6 && C>=2 && F==1 && free_6>=1 && free_5>=1 && 1>=free_15 && Q>=H && free_15>=1 ], cost: 3

     80: f16 -> f16 : A'=free_6, B'=1+B, C'=0, D'=1+B, E'=-1+free_5, F'=0, Q'=1+Q, J'=free_15, [ Q>=1 && 0>=E && 1>=free_6 && C>=2 && F==1 && free_6>=1 && free_5>=1 && 1>=free_15 && H>=1+Q && free_15>=1 ], cost: 3

     81: f16 -> f16 : A'=free_6, B'=1+B, C'=0, D'=1+B, E'=-1+free_5, F'=0, Q'=-1+Q, J'=free_15, [ Q>=1 && 0>=E && 1>=free_6 && C>=2 && F==1 && free_6>=1 && free_5>=1 && free_15>=0 && 0>=free_15 ], cost: 3

     82: f16 -> f16 : A'=0, B'=1+B, C'=0, D'=1+B, E'=-1+free_5, F'=1, J'=free_15, [ Q>=1 && 0>=E && 1>=free_6 && C>=2 && F==1 && free_6>=1 && free_5>=1 && 1>=free_15 && Q>=H && free_15>=1 && 0>=-1+free_5 ], cost: 5

     83: f16 -> f16 : A'=0, B'=1+B, C'=0, D'=1+B, E'=-1+free_5, F'=1, Q'=1+Q, J'=free_15, [ Q>=1 && 0>=E && 1>=free_6 && C>=2 && F==1 && free_6>=1 && free_5>=1 && 1>=free_15 && H>=1+Q && free_15>=1 && 0>=-1+free_5 ], cost: 5

     84: f16 -> f16 : A'=0, B'=1+B, C'=0, D'=1+B, E'=-1+free_5, F'=1, Q'=-1+Q, J'=free_15, [ 0>=E && 1>=free_6 && C>=2 && F==1 && free_6>=1 && free_5>=1 && free_15>=0 && 0>=free_15 && -1+Q>=1 && 0>=-1+free_5 ], cost: 5

     85: f16 -> f16 : A'=0, B'=1+B, C'=0, D'=1+B, E'=0, F'=0, J'=free_15, [ Q>=1 && 0>=E && 1>=free_6 && C>=2 && F==1 && free_6>=1 && 1>=free_15 && Q>=H && free_15>=1 && -1+free_5>=1 ], cost: 1+2*free_5

     86: f16 -> f16 : A'=0, B'=1+B, C'=0, D'=1+B, E'=0, F'=0, Q'=1+Q, J'=free_15, [ Q>=1 && 0>=E && 1>=free_6 && C>=2 && F==1 && free_6>=1 && 1>=free_15 && H>=1+Q && free_15>=1 && -1+free_5>=1 ], cost: 1+2*free_5

     87: f16 -> f16 : A'=0, B'=1+B, C'=0, D'=1+B, E'=0, F'=0, Q'=-1+Q, J'=free_15, [ 0>=E && 1>=free_6 && C>=2 && F==1 && free_6>=1 && free_15>=0 && 0>=free_15 && -1+Q>=1 && -1+free_5>=1 ], cost: 1+2*free_5

     88: f16 -> f16 : A'=free_8, B'=1+B, C'=0, D'=1+B, E'=free_7, F'=1, Q'=-1+Q, J'=0, [ Q>=1 && 0>=E && 0>=D && 1>=free_8 && free_7>=0 && F==1 && C==1 && free_8>=1 && 0>=free_7 ], cost: 3

     89: f16 -> f16 : A'=free_8, B'=1+B, C'=0, D'=1+B, E'=-1+free_7, F'=0, J'=free_15, [ Q>=1 && 0>=E && 0>=D && 1>=free_8 && F==1 && C==1 && free_8>=1 && free_7>=1 && 1>=free_15 && Q>=H && free_15>=1 ], cost: 3

     90: f16 -> f16 : A'=free_8, B'=1+B, C'=0, D'=1+B, E'=-1+free_7, F'=0, Q'=1+Q, J'=free_15, [ Q>=1 && 0>=E && 0>=D && 1>=free_8 && F==1 && C==1 && free_8>=1 && free_7>=1 && 1>=free_15 && H>=1+Q && free_15>=1 ], cost: 3

     91: f16 -> f16 : A'=free_8, B'=1+B, C'=0, D'=1+B, E'=-1+free_7, F'=0, Q'=-1+Q, J'=free_15, [ Q>=1 && 0>=E && 0>=D && 1>=free_8 && F==1 && C==1 && free_8>=1 && free_7>=1 && free_15>=0 && 0>=free_15 ], cost: 3

     92: f16 -> f16 : A'=0, B'=1+B, C'=0, D'=1+B, E'=-1+free_7, F'=1, J'=free_15, [ Q>=1 && 0>=E && 0>=D && 1>=free_8 && F==1 && C==1 && free_8>=1 && free_7>=1 && 1>=free_15 && Q>=H && free_15>=1 && 0>=-1+free_7 ], cost: 5

     93: f16 -> f16 : A'=0, B'=1+B, C'=0, D'=1+B, E'=-1+free_7, F'=1, Q'=1+Q, J'=free_15, [ Q>=1 && 0>=E && 0>=D && 1>=free_8 && F==1 && C==1 && free_8>=1 && free_7>=1 && 1>=free_15 && H>=1+Q && free_15>=1 && 0>=-1+free_7 ], cost: 5

     94: f16 -> f16 : A'=0, B'=1+B, C'=0, D'=1+B, E'=-1+free_7, F'=1, Q'=-1+Q, J'=free_15, [ 0>=E && 0>=D && 1>=free_8 && F==1 && C==1 && free_8>=1 && free_7>=1 && free_15>=0 && 0>=free_15 && -1+Q>=1 && 0>=-1+free_7 ], cost: 5

     95: f16 -> f16 : A'=0, B'=1+B, C'=0, D'=1+B, E'=0, F'=0, J'=free_15, [ Q>=1 && 0>=E && 0>=D && 1>=free_8 && F==1 && C==1 && free_8>=1 && 1>=free_15 && Q>=H && free_15>=1 && -1+free_7>=1 ], cost: 1+2*free_7

     96: f16 -> f16 : A'=0, B'=1+B, C'=0, D'=1+B, E'=0, F'=0, Q'=1+Q, J'=free_15, [ Q>=1 && 0>=E && 0>=D && 1>=free_8 && F==1 && C==1 && free_8>=1 && 1>=free_15 && H>=1+Q && free_15>=1 && -1+free_7>=1 ], cost: 1+2*free_7

     97: f16 -> f16 : A'=0, B'=1+B, C'=0, D'=1+B, E'=0, F'=0, Q'=-1+Q, J'=free_15, [ 0>=E && 0>=D && 1>=free_8 && F==1 && C==1 && free_8>=1 && free_15>=0 && 0>=free_15 && -1+Q>=1 && -1+free_7>=1 ], cost: 1+2*free_7

     98: f16 -> f16 : A'=free_9, E'=-1+E, F'=1+F, Q'=-1+Q, J'=0, [ Q>=1 && E>=1 && 1>=free_9 && free_9>=1 && 0>=F && 0>=-1+E ], cost: 3

     99: f16 -> f16 : A'=0, E'=-1+E, F'=1, Q'=-1+Q, J'=0, [ E>=1 && 1>=free_9 && free_9>=1 && 0>=-1+E && -1+Q>=1 && 0>=1+F ], cost: 3-2*F

    100: f16 -> f16 : A'=free_9, E'=-1+E, J'=free_10, [ Q>=1 && E>=1 && 1>=free_9 && free_9>=1 && F>=2 && 0>=-1+E && 1>=free_10 && Q>=H && free_10>=1 ], cost: 3

    101: f16 -> f16 : A'=free_9, E'=-1+E, Q'=1+Q, J'=free_10, [ Q>=1 && E>=1 && 1>=free_9 && free_9>=1 && F>=2 && 0>=-1+E && 1>=free_10 && H>=1+Q && free_10>=1 ], cost: 3

    102: f16 -> f16 : A'=free_9, E'=-1+E, Q'=-1+Q, J'=free_10, [ Q>=1 && E>=1 && 1>=free_9 && free_9>=1 && F>=2 && 0>=-1+E && free_10>=0 && 0>=free_10 ], cost: 3

    103: f16 -> [5] : A'=free_9, E'=-1+E, J'=free_10, [ Q>=1 && E>=1 && 1>=free_9 && free_9>=1 && F>=2 && 0>=-1+E && 1>=free_10 && Q>=H && free_10>=1 ], cost: NONTERM

    104: f16 -> [5] : A'=free_9, E'=-1+E, Q'=1+Q, J'=free_10, [ Q>=1 && E>=1 && 1>=free_9 && free_9>=1 && F>=2 && 0>=-1+E && 1>=free_10 && H>=1+Q && free_10>=1 ], cost: NONTERM

    105: f16 -> [5] : A'=free_9, E'=-1+E, Q'=-1+Q, J'=free_10, [ E>=1 && 1>=free_9 && free_9>=1 && F>=2 && 0>=-1+E && free_10>=0 && 0>=free_10 && -1+Q>=1 ], cost: NONTERM

    106: f16 -> f16 : A'=free_9, C'=1+C, E'=-1+E, J'=1, [ Q>=1 && E>=1 && 1>=free_9 && free_9>=1 && 0>=-1+E && 0>=C && F==1 && Q>=H ], cost: 3

    107: f16 -> f16 : A'=free_9, C'=1+C, E'=-1+E, Q'=1+Q, J'=1, [ Q>=1 && E>=1 && 1>=free_9 && free_9>=1 && 0>=-1+E && 0>=C && F==1 && H>=1+Q ], cost: 3

    108: f16 -> f16 : A'=free_9, C'=0, D'=-1+D, E'=-1+E, Q'=-1+Q, J'=0, [ Q>=1 && E>=1 && 1>=free_9 && free_9>=1 && 0>=-1+E && D>=1 && F==1 && C==1 ], cost: 3

    109: f16 -> f16 : A'=free_9, B'=1+B, C'=0, D'=1+B, E'=free_12, F'=0, J'=free_11, [ Q>=1 && E>=1 && 1>=free_9 && free_9>=1 && 0>=-1+E && 1>=free_11 && C>=2 && free_12>=0 && F==1 && Q>=H && free_11>=1 ], cost: 3

    110: f16 -> f16 : A'=free_9, B'=1+B, C'=0, D'=1+B, E'=free_12, F'=0, Q'=1+Q, J'=free_11, [ Q>=1 && E>=1 && 1>=free_9 && free_9>=1 && 0>=-1+E && 1>=free_11 && C>=2 && free_12>=0 && F==1 && H>=1+Q && free_11>=1 ], cost: 3

    111: f16 -> f16 : A'=free_9, B'=1+B, C'=0, D'=1+B, E'=free_12, F'=0, Q'=-1+Q, J'=free_11, [ Q>=1 && E>=1 && 1>=free_9 && free_9>=1 && 0>=-1+E && free_11>=0 && C>=2 && free_12>=0 && F==1 && 0>=free_11 ], cost: 3

    112: f16 -> f16 : A'=0, B'=1+B, C'=0, D'=1+B, E'=free_12, F'=1, J'=free_11, [ Q>=1 && E>=1 && 1>=free_9 && free_9>=1 && 0>=-1+E && 1>=free_11 && C>=2 && free_12>=0 && F==1 && Q>=H && free_11>=1 && 0>=free_12 ], cost: 5

    113: f16 -> f16 : A'=0, B'=1+B, C'=0, D'=1+B, E'=free_12, F'=1, Q'=1+Q, J'=free_11, [ Q>=1 && E>=1 && 1>=free_9 && free_9>=1 && 0>=-1+E && 1>=free_11 && C>=2 && free_12>=0 && F==1 && H>=1+Q && free_11>=1 && 0>=free_12 ], cost: 5

    114: f16 -> f16 : A'=0, B'=1+B, C'=0, D'=1+B, E'=free_12, F'=1, Q'=-1+Q, J'=free_11, [ E>=1 && 1>=free_9 && free_9>=1 && 0>=-1+E && free_11>=0 && C>=2 && free_12>=0 && F==1 && 0>=free_11 && -1+Q>=1 && 0>=free_12 ], cost: 5

    115: f16 -> f16 : A'=0, B'=1+B, C'=0, D'=1+B, E'=0, F'=0, J'=free_11, [ Q>=1 && E>=1 && 1>=free_9 && free_9>=1 && 0>=-1+E && 1>=free_11 && C>=2 && F==1 && Q>=H && free_11>=1 && free_12>=1 ], cost: 3+2*free_12

    116: f16 -> f16 : A'=0, B'=1+B, C'=0, D'=1+B, E'=0, F'=0, Q'=1+Q, J'=free_11, [ Q>=1 && E>=1 && 1>=free_9 && free_9>=1 && 0>=-1+E && 1>=free_11 && C>=2 && F==1 && H>=1+Q && free_11>=1 && free_12>=1 ], cost: 3+2*free_12

    117: f16 -> f16 : A'=0, B'=1+B, C'=0, D'=1+B, E'=0, F'=0, Q'=-1+Q, J'=free_11, [ E>=1 && 1>=free_9 && free_9>=1 && 0>=-1+E && free_11>=0 && C>=2 && F==1 && 0>=free_11 && -1+Q>=1 && free_12>=1 ], cost: 3+2*free_12

    118: f16 -> f16 : A'=free_9, B'=1+B, C'=0, D'=1+B, E'=free_14, F'=0, J'=free_13, [ Q>=1 && E>=1 && 1>=free_9 && free_9>=1 && 0>=-1+E && 0>=D && 1>=free_13 && free_14>=0 && F==1 && C==1 && Q>=H && free_13>=1 ], cost: 3

    119: f16 -> f16 : A'=free_9, B'=1+B, C'=0, D'=1+B, E'=free_14, F'=0, Q'=1+Q, J'=free_13, [ Q>=1 && E>=1 && 1>=free_9 && free_9>=1 && 0>=-1+E && 0>=D && 1>=free_13 && free_14>=0 && F==1 && C==1 && H>=1+Q && free_13>=1 ], cost: 3

    120: f16 -> f16 : A'=free_9, B'=1+B, C'=0, D'=1+B, E'=free_14, F'=0, Q'=-1+Q, J'=free_13, [ Q>=1 && E>=1 && 1>=free_9 && free_9>=1 && 0>=-1+E && 0>=D && free_13>=0 && free_14>=0 && F==1 && C==1 && 0>=free_13 ], cost: 3

    121: f16 -> f16 : A'=0, B'=1+B, C'=0, D'=1+B, E'=free_14, F'=1, J'=free_13, [ Q>=1 && E>=1 && 1>=free_9 && free_9>=1 && 0>=-1+E && 0>=D && 1>=free_13 && free_14>=0 && F==1 && C==1 && Q>=H && free_13>=1 && 0>=free_14 ], cost: 5

    122: f16 -> f16 : A'=0, B'=1+B, C'=0, D'=1+B, E'=free_14, F'=1, Q'=1+Q, J'=free_13, [ Q>=1 && E>=1 && 1>=free_9 && free_9>=1 && 0>=-1+E && 0>=D && 1>=free_13 && free_14>=0 && F==1 && C==1 && H>=1+Q && free_13>=1 && 0>=free_14 ], cost: 5

    123: f16 -> f16 : A'=0, B'=1+B, C'=0, D'=1+B, E'=free_14, F'=1, Q'=-1+Q, J'=free_13, [ E>=1 && 1>=free_9 && free_9>=1 && 0>=-1+E && 0>=D && free_13>=0 && free_14>=0 && F==1 && C==1 && 0>=free_13 && -1+Q>=1 && 0>=free_14 ], cost: 5

    124: f16 -> f16 : A'=0, B'=1+B, C'=0, D'=1+B, E'=0, F'=0, J'=free_13, [ Q>=1 && E>=1 && 1>=free_9 && free_9>=1 && 0>=-1+E && 0>=D && 1>=free_13 && F==1 && C==1 && Q>=H && free_13>=1 && free_14>=1 ], cost: 3+2*free_14

    125: f16 -> f16 : A'=0, B'=1+B, C'=0, D'=1+B, E'=0, F'=0, Q'=1+Q, J'=free_13, [ Q>=1 && E>=1 && 1>=free_9 && free_9>=1 && 0>=-1+E && 0>=D && 1>=free_13 && F==1 && C==1 && H>=1+Q && free_13>=1 && free_14>=1 ], cost: 3+2*free_14

    126: f16 -> f16 : A'=0, B'=1+B, C'=0, D'=1+B, E'=0, F'=0, Q'=-1+Q, J'=free_13, [ E>=1 && 1>=free_9 && free_9>=1 && 0>=-1+E && 0>=D && free_13>=0 && F==1 && C==1 && 0>=free_13 && -1+Q>=1 && free_14>=1 ], cost: 3+2*free_14

    127: f16 -> f16 : A'=free_9, E'=-2+E, J'=free_15, [ Q>=1 && 1>=free_9 && free_9>=1 && -1+E>=1 && 1>=free_15 && Q>=H && free_15>=1 ], cost: 3

    128: f16 -> f16 : A'=free_9, E'=-2+E, Q'=1+Q, J'=free_15, [ Q>=1 && 1>=free_9 && free_9>=1 && -1+E>=1 && 1>=free_15 && H>=1+Q && free_15>=1 ], cost: 3

    129: f16 -> f16 : A'=free_9, E'=-2+E, Q'=-1+Q, J'=free_15, [ Q>=1 && 1>=free_9 && free_9>=1 && -1+E>=1 && free_15>=0 && 0>=free_15 ], cost: 3

    130: f16 -> f16 : A'=0, E'=-2+E, F'=1, J'=free_15, [ Q>=1 && 1>=free_9 && free_9>=1 && -1+E>=1 && 1>=free_15 && Q>=H && free_15>=1 && 0>=F && 0>=-2+E ], cost: 5-2*F

    131: f16 -> f16 : A'=0, E'=-2+E, F'=1, Q'=1+Q, J'=free_15, [ Q>=1 && 1>=free_9 && free_9>=1 && -1+E>=1 && 1>=free_15 && H>=1+Q && free_15>=1 && 0>=F && 0>=-2+E ], cost: 5-2*F

    132: f16 -> f16 : A'=0, E'=-2+E, F'=1, Q'=-1+Q, J'=free_15, [ 1>=free_9 && free_9>=1 && -1+E>=1 && free_15>=0 && 0>=free_15 && -1+Q>=1 && 0>=F && 0>=-2+E ], cost: 5-2*F

    133: f16 -> [5] : A'=free_9, E'=-2+E, J'=free_15, [ Q>=1 && 1>=free_9 && free_9>=1 && -1+E>=1 && 1>=free_15 && Q>=H && free_15>=1 && F>=2 && 0>=-2+E ], cost: NONTERM

    134: f16 -> [5] : A'=free_9, E'=-2+E, Q'=1+Q, J'=free_15, [ Q>=1 && 1>=free_9 && free_9>=1 && -1+E>=1 && 1>=free_15 && H>=1+Q && free_15>=1 && F>=2 && 0>=-2+E ], cost: NONTERM

    135: f16 -> [5] : A'=free_9, E'=-2+E, Q'=-1+Q, J'=free_15, [ 1>=free_9 && free_9>=1 && -1+E>=1 && free_15>=0 && 0>=free_15 && -1+Q>=1 && F>=2 && 0>=-2+E ], cost: NONTERM

    136: f16 -> f16 : A'=0, E'=0, J'=free_15, [ Q>=1 && 1>=free_9 && free_9>=1 && 1>=free_15 && Q>=H && free_15>=1 && -2+E>=1 ], cost: -1+2*E

    137: f16 -> f16 : A'=0, E'=0, Q'=1+Q, J'=free_15, [ Q>=1 && 1>=free_9 && free_9>=1 && 1>=free_15 && H>=1+Q && free_15>=1 && -2+E>=1 ], cost: -1+2*E

    138: f16 -> f16 : A'=0, E'=0, Q'=-1+Q, J'=free_15, [ 1>=free_9 && free_9>=1 && free_15>=0 && 0>=free_15 && -1+Q>=1 && -2+E>=1 ], cost: -1+2*E



Applied pruning (of leafs and parallel rules):

   Start location: f0

      1: f0 -> f16 : B'=1, C'=0, D'=1, E'=free_1, F'=0, G'=free, H'=free_3, Q'=free_2, [ free_2>=0 && free_3>=free_2 && free>=free_3 && free_1>=0 ], cost: 1

     49: f0 -> f16 : A'=0, B'=1, C'=0, D'=1, E'=0, F'=1, G'=free, H'=free_3, Q'=free_2, [ free_3>=free_2 && free>=free_3 && free_2>=1 ], cost: 3

     56: f0 -> f16 : A'=0, B'=1, C'=0, D'=1, E'=0, F'=0, G'=free, H'=free_3, Q'=free_2, [ free_3>=free_2 && free>=free_3 && free_2>=1 && free_1>=1 ], cost: 1+2*free_1

     63: f16 -> [5] : A'=free_4, J'=free_10, [ Q>=1 && F>=2 && 0>=E && 1>=free_4 && free_4>=1 && 1>=free_10 && Q>=H && free_10>=1 ], cost: NONTERM

     64: f16 -> [5] : A'=free_4, Q'=1+Q, J'=free_10, [ Q>=1 && F>=2 && 0>=E && 1>=free_4 && free_4>=1 && 1>=free_10 && H>=1+Q && free_10>=1 ], cost: NONTERM

     75: f16 -> f16 : A'=0, B'=1+B, C'=0, D'=1+B, E'=0, F'=0, J'=free_13, [ Q>=1 && 0>=E && F==1 && 0>=D && 1>=free_13 && 1+C==1 && Q>=H && free_13>=1 && free_14>=1 ], cost: 3+2*free_14

     76: f16 -> f16 : A'=0, B'=1+B, C'=0, D'=1+B, E'=0, F'=0, Q'=1+Q, J'=free_13, [ Q>=1 && 0>=E && F==1 && 0>=D && 1>=free_13 && 1+C==1 && H>=1+Q && free_13>=1 && free_14>=1 ], cost: 3+2*free_14

     77: f16 -> f16 : A'=0, B'=1+B, C'=0, D'=1+B, E'=0, F'=0, Q'=-1+Q, J'=free_13, [ 0>=E && F==1 && 0>=D && free_13>=0 && 1+C==1 && 0>=free_13 && -1+Q>=1 && free_14>=1 ], cost: 3+2*free_14

    103: f16 -> [5] : A'=free_9, E'=-1+E, J'=free_10, [ Q>=1 && E>=1 && 1>=free_9 && free_9>=1 && F>=2 && 0>=-1+E && 1>=free_10 && Q>=H && free_10>=1 ], cost: NONTERM

    104: f16 -> [5] : A'=free_9, E'=-1+E, Q'=1+Q, J'=free_10, [ Q>=1 && E>=1 && 1>=free_9 && free_9>=1 && F>=2 && 0>=-1+E && 1>=free_10 && H>=1+Q && free_10>=1 ], cost: NONTERM

    124: f16 -> f16 : A'=0, B'=1+B, C'=0, D'=1+B, E'=0, F'=0, J'=free_13, [ Q>=1 && E>=1 && 1>=free_9 && free_9>=1 && 0>=-1+E && 0>=D && 1>=free_13 && F==1 && C==1 && Q>=H && free_13>=1 && free_14>=1 ], cost: 3+2*free_14

    126: f16 -> f16 : A'=0, B'=1+B, C'=0, D'=1+B, E'=0, F'=0, Q'=-1+Q, J'=free_13, [ E>=1 && 1>=free_9 && free_9>=1 && 0>=-1+E && 0>=D && free_13>=0 && F==1 && C==1 && 0>=free_13 && -1+Q>=1 && free_14>=1 ], cost: 3+2*free_14

    133: f16 -> [5] : A'=free_9, E'=-2+E, J'=free_15, [ Q>=1 && 1>=free_9 && free_9>=1 && -1+E>=1 && 1>=free_15 && Q>=H && free_15>=1 && F>=2 && 0>=-2+E ], cost: NONTERM



Accelerating simple loops of location 2.

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

   Accelerating the following rules:

     75: f16 -> f16 : A'=0, B'=1+B, C'=0, D'=1+B, E'=0, F'=0, J'=1, [ Q>=1 && 0>=E && F==1 && 0>=D && 1+C==1 && Q>=H && free_14>=1 ], cost: 3+2*free_14

     76: f16 -> f16 : A'=0, B'=1+B, C'=0, D'=1+B, E'=0, F'=0, Q'=1+Q, J'=1, [ Q>=1 && 0>=E && F==1 && 0>=D && 1+C==1 && H>=1+Q && free_14>=1 ], cost: 3+2*free_14

     77: f16 -> f16 : A'=0, B'=1+B, C'=0, D'=1+B, E'=0, F'=0, Q'=-1+Q, J'=0, [ 0>=E && F==1 && 0>=D && 1+C==1 && -1+Q>=1 && free_14>=1 ], cost: 3+2*free_14

    124: f16 -> f16 : A'=0, B'=1+B, C'=0, D'=1+B, E'=0, F'=0, J'=1, [ Q>=1 && 1-E==0 && 0>=D && F==1 && C==1 && Q>=H && free_14>=1 ], cost: 3+2*free_14

    126: f16 -> f16 : A'=0, B'=1+B, C'=0, D'=1+B, E'=0, F'=0, Q'=-1+Q, J'=0, [ 1-E==0 && 0>=D && F==1 && C==1 && -1+Q>=1 && free_14>=1 ], cost: 3+2*free_14



   Accelerated rule 75 with metering function -1+F, yielding the new rule 139.

   Accelerated rule 76 with metering function -1+F, yielding the new rule 140.

   Accelerated rule 77 with metering function -1+F, yielding the new rule 141.

   Accelerated rule 124 with metering function meter_2 (where 3*meter_2==-3+F+C+E), yielding the new rule 142.

   Accelerated rule 126 with metering function meter_3 (where 3*meter_3==-3+F+C+E), yielding the new rule 143.

   Removing the simple loops: 75 76 77 124 126.



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

   Start location: f0

      1: f0 -> f16 : B'=1, C'=0, D'=1, E'=free_1, F'=0, G'=free, H'=free_3, Q'=free_2, [ free_2>=0 && free_3>=free_2 && free>=free_3 && free_1>=0 ], cost: 1

     49: f0 -> f16 : A'=0, B'=1, C'=0, D'=1, E'=0, F'=1, G'=free, H'=free_3, Q'=free_2, [ free_3>=free_2 && free>=free_3 && free_2>=1 ], cost: 3

     56: f0 -> f16 : A'=0, B'=1, C'=0, D'=1, E'=0, F'=0, G'=free, H'=free_3, Q'=free_2, [ free_3>=free_2 && free>=free_3 && free_2>=1 && free_1>=1 ], cost: 1+2*free_1

     63: f16 -> [5] : A'=free_4, J'=free_10, [ Q>=1 && F>=2 && 0>=E && 1>=free_4 && free_4>=1 && 1>=free_10 && Q>=H && free_10>=1 ], cost: NONTERM

     64: f16 -> [5] : A'=free_4, Q'=1+Q, J'=free_10, [ Q>=1 && F>=2 && 0>=E && 1>=free_4 && free_4>=1 && 1>=free_10 && H>=1+Q && free_10>=1 ], cost: NONTERM

    103: f16 -> [5] : A'=free_9, E'=-1+E, J'=free_10, [ Q>=1 && E>=1 && 1>=free_9 && free_9>=1 && F>=2 && 0>=-1+E && 1>=free_10 && Q>=H && free_10>=1 ], cost: NONTERM

    104: f16 -> [5] : A'=free_9, E'=-1+E, Q'=1+Q, J'=free_10, [ Q>=1 && E>=1 && 1>=free_9 && free_9>=1 && F>=2 && 0>=-1+E && 1>=free_10 && H>=1+Q && free_10>=1 ], cost: NONTERM

    133: f16 -> [5] : A'=free_9, E'=-2+E, J'=free_15, [ Q>=1 && 1>=free_9 && free_9>=1 && -1+E>=1 && 1>=free_15 && Q>=H && free_15>=1 && F>=2 && 0>=-2+E ], cost: NONTERM

    139: f16 -> f16 : A'=0, B'=-1+F+B, C'=0, D'=-1+F+B, E'=0, F'=0, J'=1, [ Q>=1 && 0>=E && F==1 && 0>=D && 1+C==1 && Q>=H && free_14>=1 && -1+F>=1 ], cost: -3+3*F+2*free_14*(-1+F)

    140: f16 -> f16 : A'=0, B'=-1+F+B, C'=0, D'=-1+F+B, E'=0, F'=0, Q'=-1+F+Q, J'=1, [ Q>=1 && 0>=E && F==1 && 0>=D && 1+C==1 && H>=1+Q && free_14>=1 && -1+F>=1 ], cost: -3+3*F+2*free_14*(-1+F)

    141: f16 -> f16 : A'=0, B'=-1+F+B, C'=0, D'=-1+F+B, E'=0, F'=0, Q'=1-F+Q, J'=0, [ 0>=E && F==1 && 0>=D && 1+C==1 && -1+Q>=1 && free_14>=1 && -1+F>=1 ], cost: -3+3*F+2*free_14*(-1+F)

    142: f16 -> f16 : A'=0, B'=meter_2+B, C'=0, D'=meter_2+B, E'=0, F'=0, J'=1, [ Q>=1 && 1-E==0 && 0>=D && F==1 && C==1 && Q>=H && free_14>=1 && 3*meter_2==-3+F+C+E && meter_2>=1 ], cost: 3*meter_2+2*meter_2*free_14

    143: f16 -> f16 : A'=0, B'=meter_3+B, C'=0, D'=meter_3+B, E'=0, F'=0, Q'=-meter_3+Q, J'=0, [ 1-E==0 && 0>=D && F==1 && C==1 && -1+Q>=1 && free_14>=1 && 3*meter_3==-3+F+C+E && meter_3>=1 ], cost: 2*free_14*meter_3+3*meter_3



Chained accelerated rules (with incoming rules):

   Start location: f0

      1: f0 -> f16 : B'=1, C'=0, D'=1, E'=free_1, F'=0, G'=free, H'=free_3, Q'=free_2, [ free_2>=0 && free_3>=free_2 && free>=free_3 && free_1>=0 ], cost: 1

     49: f0 -> f16 : A'=0, B'=1, C'=0, D'=1, E'=0, F'=1, G'=free, H'=free_3, Q'=free_2, [ free_3>=free_2 && free>=free_3 && free_2>=1 ], cost: 3

     56: f0 -> f16 : A'=0, B'=1, C'=0, D'=1, E'=0, F'=0, G'=free, H'=free_3, Q'=free_2, [ free_3>=free_2 && free>=free_3 && free_2>=1 && free_1>=1 ], cost: 1+2*free_1

     63: f16 -> [5] : A'=free_4, J'=free_10, [ Q>=1 && F>=2 && 0>=E && 1>=free_4 && free_4>=1 && 1>=free_10 && Q>=H && free_10>=1 ], cost: NONTERM

     64: f16 -> [5] : A'=free_4, Q'=1+Q, J'=free_10, [ Q>=1 && F>=2 && 0>=E && 1>=free_4 && free_4>=1 && 1>=free_10 && H>=1+Q && free_10>=1 ], cost: NONTERM

    103: f16 -> [5] : A'=free_9, E'=-1+E, J'=free_10, [ Q>=1 && E>=1 && 1>=free_9 && free_9>=1 && F>=2 && 0>=-1+E && 1>=free_10 && Q>=H && free_10>=1 ], cost: NONTERM

    104: f16 -> [5] : A'=free_9, E'=-1+E, Q'=1+Q, J'=free_10, [ Q>=1 && E>=1 && 1>=free_9 && free_9>=1 && F>=2 && 0>=-1+E && 1>=free_10 && H>=1+Q && free_10>=1 ], cost: NONTERM

    133: f16 -> [5] : A'=free_9, E'=-2+E, J'=free_15, [ Q>=1 && 1>=free_9 && free_9>=1 && -1+E>=1 && 1>=free_15 && Q>=H && free_15>=1 && F>=2 && 0>=-2+E ], cost: NONTERM



Eliminated locations (on tree-shaped paths):

   Start location: f0

    144: f0 -> [7] : [ free_3>=free_2 && free>=free_3 && free_2>=1 && free_1>=1 ], cost: 1+2*free_1



Applied pruning (of leafs and parallel rules):

   Start location: f0

    144: f0 -> [7] : [ free_3>=free_2 && free>=free_3 && free_2>=1 && free_1>=1 ], cost: 1+2*free_1



### Computing asymptotic complexity ###



Fully simplified ITS problem

   Start location: f0

    144: f0 -> [7] : [ free_3>=free_2 && free>=free_3 && free_2>=1 && free_1>=1 ], cost: 1+2*free_1



Computing asymptotic complexity for rule 144

   Solved the limit problem by the following transformations:

      Created initial limit problem:

      1-free_2+free_3 (+/+!), free_1 (+/+!), 1+2*free_1 (+), free_2 (+/+!), 1-free_3+free (+/+!) [not solved]



      removing all constraints (solved by SMT)

      resulting limit problem: [solved]



      applying transformation rule (C) using substitution {free_1==n,free_2==1,free_3==1,free==1}

      resulting limit problem:

      [solved]



   Solution:

      free_1 / n

      free_2 / 1

      free_3 / 1

      free / 1

   Resulting cost 1+2*n has complexity: Unbounded



Found new complexity Unbounded.



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

   Complexity:  Unbounded

   Cpx degree:  Unbounded

   Solved cost: 1+2*n

   Rule cost:   1+2*free_1

   Rule guard:  [ free_3>=free_2 && free>=free_3 && free_2>=1 && free_1>=1 ]



WORST_CASE(INF,?)


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

(2)
BOUNDS(INF, INF)