/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, 19.4 s]
(2) BOUNDS(INF, INF)


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

(0)
Obligation:
Complexity Int TRS consisting of the following rules:
f38(A, B, C, D, E, F, G) -> Com_1(f11(A, A, C, D, E, F, G)) :|: A >= B && A <= B
f0(A, B, C, D, E, F, G) -> Com_1(f11(0, 0, H, 0, 1, I, I)) :|: H >= 0 && I >= 1
f11(A, B, C, D, E, F, G) -> Com_1(f34(0, H, C, D + 1, E, F, G)) :|: H >= 0 && 1 >= H && G >= 1 && 0 >= C && 0 >= D
f11(A, B, C, D, E, F, G) -> Com_1(f34(1, H, C, D + 1, E, F, G)) :|: H >= 0 && 1 >= H && G >= 1 && 0 >= C && D >= 1 && D <= 1
f11(A, B, C, D, E, F, G) -> Com_1(f34(0, H, C, D + 1, E, F, G)) :|: H >= 0 && 1 >= H && G >= 1 && 0 >= C && D >= 2 && D <= 2
f11(A, B, C, D, E, F, G) -> Com_1(f34(I, J, H, 0, E + 1, F, G)) :|: J >= 0 && 1 >= J && I >= 0 && 1 >= I && H >= 0 && G >= 1 && 0 >= C && D >= 3
f11(A, B, C, D, E, F, G) -> Com_1(f34(H, I, C - 1, D, E, F, G)) :|: I >= 0 && 1 >= I && H >= 0 && 1 >= H && C >= 1 && G >= 1
f34(A, B, C, D, E, F, G) -> Com_1(f38(A, B, C, D + 1, E, F, G)) :|: 0 >= B && 0 >= C && 0 >= D
f34(A, B, C, D, E, F, G) -> Com_1(f38(A, B, C, D + 1, E, F, G)) :|: B >= 1 && 0 >= C && D >= 1 && D <= 1
f34(A, B, C, D, E, F, G) -> Com_1(f38(A, B, C, D + 1, E, F, G)) :|: 0 >= B && 0 >= C && D >= 2 && D <= 2
f34(A, B, C, D, E, F, G) -> Com_1(f38(A, B, H, 0, E + 1, F, G)) :|: H >= 0 && 0 >= C && D >= 3
f34(A, B, C, D, E, F, G) -> Com_1(f38(A, B, C - 1, D, E, F, G)) :|: C >= 1
f38(A, B, C, D, E, F, G) -> Com_1(f11(A, B, C, D, E, F, G - 1)) :|: B >= A + 1
f38(A, B, C, D, E, F, G) -> Com_1(f11(A, B, C, D, E, F, G - 1)) :|: A >= 1 + B
f11(A, B, C, D, E, F, G) -> Com_1(f53(A, B, C, D, E, F, G)) :|: 0 >= G

The start-symbols are:[f0_7]


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

(1) Loat Proof (FINISHED)


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



Initial linear ITS problem

   Start location: f0

      0: f38 -> f11 : B'=A, [ A==B ], cost: 1

     12: f38 -> f11 : G'=-1+G, [ B>=1+A ], cost: 1

     13: f38 -> f11 : G'=-1+G, [ A>=1+B ], cost: 1

      1: f0 -> f11 : A'=0, B'=0, C'=free, D'=0, E'=1, F'=free_1, G'=free_1, [ free>=0 && free_1>=1 ], cost: 1

      2: f11 -> f34 : A'=0, B'=free_2, D'=1+D, [ free_2>=0 && 1>=free_2 && G>=1 && 0>=C && 0>=D ], cost: 1

      3: f11 -> f34 : A'=1, B'=free_3, D'=1+D, [ free_3>=0 && 1>=free_3 && G>=1 && 0>=C && D==1 ], cost: 1

      4: f11 -> f34 : A'=0, B'=free_4, D'=1+D, [ free_4>=0 && 1>=free_4 && G>=1 && 0>=C && D==2 ], cost: 1

      5: f11 -> f34 : A'=free_6, B'=free_7, C'=free_5, D'=0, E'=1+E, [ free_7>=0 && 1>=free_7 && free_6>=0 && 1>=free_6 && free_5>=0 && G>=1 && 0>=C && D>=3 ], cost: 1

      6: f11 -> f34 : A'=free_8, B'=free_9, C'=-1+C, [ free_9>=0 && 1>=free_9 && free_8>=0 && 1>=free_8 && C>=1 && G>=1 ], cost: 1

     14: f11 -> f53 : [ 0>=G ], cost: 1

      7: f34 -> f38 : D'=1+D, [ 0>=B && 0>=C && 0>=D ], cost: 1

      8: f34 -> f38 : D'=1+D, [ B>=1 && 0>=C && D==1 ], cost: 1

      9: f34 -> f38 : D'=1+D, [ 0>=B && 0>=C && D==2 ], cost: 1

     10: f34 -> f38 : C'=free_10, D'=0, E'=1+E, [ free_10>=0 && 0>=C && D>=3 ], cost: 1

     11: f34 -> f38 : C'=-1+C, [ C>=1 ], cost: 1



Checking for constant complexity:

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

      1: f0 -> f11 : A'=0, B'=0, C'=free, D'=0, E'=1, F'=free_1, G'=free_1, [ free>=0 && free_1>=1 ], cost: 1



Removed unreachable and leaf rules:

   Start location: f0

      0: f38 -> f11 : B'=A, [ A==B ], cost: 1

     12: f38 -> f11 : G'=-1+G, [ B>=1+A ], cost: 1

     13: f38 -> f11 : G'=-1+G, [ A>=1+B ], cost: 1

      1: f0 -> f11 : A'=0, B'=0, C'=free, D'=0, E'=1, F'=free_1, G'=free_1, [ free>=0 && free_1>=1 ], cost: 1

      2: f11 -> f34 : A'=0, B'=free_2, D'=1+D, [ free_2>=0 && 1>=free_2 && G>=1 && 0>=C && 0>=D ], cost: 1

      3: f11 -> f34 : A'=1, B'=free_3, D'=1+D, [ free_3>=0 && 1>=free_3 && G>=1 && 0>=C && D==1 ], cost: 1

      4: f11 -> f34 : A'=0, B'=free_4, D'=1+D, [ free_4>=0 && 1>=free_4 && G>=1 && 0>=C && D==2 ], cost: 1

      5: f11 -> f34 : A'=free_6, B'=free_7, C'=free_5, D'=0, E'=1+E, [ free_7>=0 && 1>=free_7 && free_6>=0 && 1>=free_6 && free_5>=0 && G>=1 && 0>=C && D>=3 ], cost: 1

      6: f11 -> f34 : A'=free_8, B'=free_9, C'=-1+C, [ free_9>=0 && 1>=free_9 && free_8>=0 && 1>=free_8 && C>=1 && G>=1 ], cost: 1

      7: f34 -> f38 : D'=1+D, [ 0>=B && 0>=C && 0>=D ], cost: 1

      8: f34 -> f38 : D'=1+D, [ B>=1 && 0>=C && D==1 ], cost: 1

      9: f34 -> f38 : D'=1+D, [ 0>=B && 0>=C && D==2 ], cost: 1

     10: f34 -> f38 : C'=free_10, D'=0, E'=1+E, [ free_10>=0 && 0>=C && D>=3 ], cost: 1

     11: f34 -> f38 : C'=-1+C, [ C>=1 ], cost: 1



### Simplification by acceleration and chaining ###



Eliminated locations (on tree-shaped paths):

   Start location: f0

      0: f38 -> f11 : B'=A, [ A==B ], cost: 1

     12: f38 -> f11 : G'=-1+G, [ B>=1+A ], cost: 1

     13: f38 -> f11 : G'=-1+G, [ A>=1+B ], cost: 1

      1: f0 -> f11 : A'=0, B'=0, C'=free, D'=0, E'=1, F'=free_1, G'=free_1, [ free>=0 && free_1>=1 ], cost: 1

     15: f11 -> f38 : A'=0, B'=free_2, D'=2+D, [ free_2>=0 && G>=1 && 0>=C && 0>=free_2 && 0>=1+D ], cost: 2

     16: f11 -> f38 : A'=0, B'=free_2, D'=2+D, [ 1>=free_2 && G>=1 && 0>=C && free_2>=1 && 1+D==1 ], cost: 2

     17: f11 -> f38 : A'=1, B'=free_3, D'=2+D, [ free_3>=0 && G>=1 && 0>=C && D==1 && 0>=free_3 ], cost: 2

     18: f11 -> f38 : A'=0, B'=free_4, C'=free_10, D'=0, E'=1+E, [ free_4>=0 && 1>=free_4 && G>=1 && 0>=C && D==2 && free_10>=0 ], cost: 2

     19: f11 -> f38 : A'=free_6, B'=free_7, C'=free_5, D'=1, E'=1+E, [ free_7>=0 && free_6>=0 && 1>=free_6 && free_5>=0 && G>=1 && 0>=C && D>=3 && 0>=free_7 && 0>=free_5 ], cost: 2

     20: f11 -> f38 : A'=free_6, B'=free_7, C'=-1+free_5, D'=0, E'=1+E, [ free_7>=0 && 1>=free_7 && free_6>=0 && 1>=free_6 && G>=1 && 0>=C && D>=3 && free_5>=1 ], cost: 2

     21: f11 -> f38 : A'=free_8, B'=free_9, C'=-1+C, D'=1+D, [ free_9>=0 && free_8>=0 && 1>=free_8 && C>=1 && G>=1 && 0>=free_9 && 0>=-1+C && 0>=D ], cost: 2

     22: f11 -> f38 : A'=free_8, B'=free_9, C'=-1+C, D'=1+D, [ 1>=free_9 && free_8>=0 && 1>=free_8 && C>=1 && G>=1 && free_9>=1 && 0>=-1+C && D==1 ], cost: 2

     23: f11 -> f38 : A'=free_8, B'=free_9, C'=-1+C, D'=1+D, [ free_9>=0 && free_8>=0 && 1>=free_8 && C>=1 && G>=1 && 0>=free_9 && 0>=-1+C && D==2 ], cost: 2

     24: f11 -> f38 : A'=free_8, B'=free_9, C'=free_10, D'=0, E'=1+E, [ free_9>=0 && 1>=free_9 && free_8>=0 && 1>=free_8 && C>=1 && G>=1 && free_10>=0 && 0>=-1+C && D>=3 ], cost: 2

     25: f11 -> f38 : A'=free_8, B'=free_9, C'=-2+C, [ free_9>=0 && 1>=free_9 && free_8>=0 && 1>=free_8 && G>=1 && -1+C>=1 ], cost: 2



Eliminated locations (on tree-shaped paths):

   Start location: f0

      1: f0 -> f11 : A'=0, B'=0, C'=free, D'=0, E'=1, F'=free_1, G'=free_1, [ free>=0 && free_1>=1 ], cost: 1

     26: f11 -> f11 : A'=0, B'=0, D'=2+D, [ G>=1 && 0>=C && 0>=1+D && 0==free_2 ], cost: 3

     27: f11 -> f11 : A'=0, B'=free_2, D'=2+D, G'=-1+G, [ 1>=free_2 && G>=1 && 0>=C && free_2>=1 && 1+D==1 ], cost: 3

     28: f11 -> f11 : A'=1, B'=free_3, D'=2+D, G'=-1+G, [ free_3>=0 && G>=1 && 0>=C && D==1 && 0>=free_3 ], cost: 3

     29: f11 -> f11 : A'=0, B'=0, C'=free_10, D'=0, E'=1+E, [ G>=1 && 0>=C && D==2 && free_10>=0 && 0==free_4 ], cost: 3

     30: f11 -> f11 : A'=0, B'=free_4, C'=free_10, D'=0, E'=1+E, G'=-1+G, [ 1>=free_4 && G>=1 && 0>=C && D==2 && free_10>=0 && free_4>=1 ], cost: 3

     31: f11 -> f11 : A'=free_6, B'=free_6, C'=free_5, D'=1, E'=1+E, [ free_7>=0 && free_6>=0 && 1>=free_6 && free_5>=0 && G>=1 && 0>=C && D>=3 && 0>=free_7 && 0>=free_5 && free_6==free_7 ], cost: 3

     32: f11 -> f11 : A'=free_6, B'=free_7, C'=free_5, D'=1, E'=1+E, G'=-1+G, [ free_7>=0 && free_6>=0 && 1>=free_6 && free_5>=0 && G>=1 && 0>=C && D>=3 && 0>=free_7 && 0>=free_5 && free_6>=1+free_7 ], cost: 3

     33: f11 -> f11 : A'=free_6, B'=free_6, C'=-1+free_5, D'=0, E'=1+E, [ free_7>=0 && 1>=free_7 && free_6>=0 && 1>=free_6 && G>=1 && 0>=C && D>=3 && free_5>=1 && free_6==free_7 ], cost: 3

     34: f11 -> f11 : A'=free_6, B'=free_7, C'=-1+free_5, D'=0, E'=1+E, G'=-1+G, [ free_7>=0 && 1>=free_7 && free_6>=0 && 1>=free_6 && G>=1 && 0>=C && D>=3 && free_5>=1 && free_7>=1+free_6 ], cost: 3

     35: f11 -> f11 : A'=free_6, B'=free_7, C'=-1+free_5, D'=0, E'=1+E, G'=-1+G, [ free_7>=0 && 1>=free_7 && free_6>=0 && 1>=free_6 && G>=1 && 0>=C && D>=3 && free_5>=1 && free_6>=1+free_7 ], cost: 3

     36: f11 -> f11 : A'=free_8, B'=free_8, C'=-1+C, D'=1+D, [ free_9>=0 && free_8>=0 && 1>=free_8 && C>=1 && G>=1 && 0>=free_9 && 0>=-1+C && 0>=D && free_8==free_9 ], cost: 3

     37: f11 -> f11 : A'=free_8, B'=free_9, C'=-1+C, D'=1+D, G'=-1+G, [ free_9>=0 && free_8>=0 && 1>=free_8 && C>=1 && G>=1 && 0>=free_9 && 0>=-1+C && 0>=D && free_8>=1+free_9 ], cost: 3

     38: f11 -> f11 : A'=free_8, B'=free_8, C'=-1+C, D'=1+D, [ 1>=free_9 && free_8>=0 && 1>=free_8 && C>=1 && G>=1 && free_9>=1 && 0>=-1+C && D==1 && free_8==free_9 ], cost: 3

     39: f11 -> f11 : A'=free_8, B'=free_9, C'=-1+C, D'=1+D, G'=-1+G, [ 1>=free_9 && free_8>=0 && 1>=free_8 && C>=1 && G>=1 && free_9>=1 && 0>=-1+C && D==1 && free_9>=1+free_8 ], cost: 3

     40: f11 -> f11 : A'=free_8, B'=free_8, C'=-1+C, D'=1+D, [ free_9>=0 && free_8>=0 && 1>=free_8 && C>=1 && G>=1 && 0>=free_9 && 0>=-1+C && D==2 && free_8==free_9 ], cost: 3

     41: f11 -> f11 : A'=free_8, B'=free_9, C'=-1+C, D'=1+D, G'=-1+G, [ free_9>=0 && free_8>=0 && 1>=free_8 && C>=1 && G>=1 && 0>=free_9 && 0>=-1+C && D==2 && free_8>=1+free_9 ], cost: 3

     42: f11 -> f11 : A'=free_8, B'=free_8, C'=free_10, D'=0, E'=1+E, [ free_9>=0 && 1>=free_9 && free_8>=0 && 1>=free_8 && C>=1 && G>=1 && free_10>=0 && 0>=-1+C && D>=3 && free_8==free_9 ], cost: 3

     43: f11 -> f11 : A'=free_8, B'=free_9, C'=free_10, D'=0, E'=1+E, G'=-1+G, [ free_9>=0 && 1>=free_9 && free_8>=0 && 1>=free_8 && C>=1 && G>=1 && free_10>=0 && 0>=-1+C && D>=3 && free_9>=1+free_8 ], cost: 3

     44: f11 -> f11 : A'=free_8, B'=free_9, C'=free_10, D'=0, E'=1+E, G'=-1+G, [ free_9>=0 && 1>=free_9 && free_8>=0 && 1>=free_8 && C>=1 && G>=1 && free_10>=0 && 0>=-1+C && D>=3 && free_8>=1+free_9 ], cost: 3

     45: f11 -> f11 : A'=free_8, B'=free_8, C'=-2+C, [ free_9>=0 && 1>=free_9 && free_8>=0 && 1>=free_8 && G>=1 && -1+C>=1 && free_8==free_9 ], cost: 3

     46: f11 -> f11 : A'=free_8, B'=free_9, C'=-2+C, G'=-1+G, [ free_9>=0 && 1>=free_9 && free_8>=0 && 1>=free_8 && G>=1 && -1+C>=1 && free_9>=1+free_8 ], cost: 3

     47: f11 -> f11 : A'=free_8, B'=free_9, C'=-2+C, G'=-1+G, [ free_9>=0 && 1>=free_9 && free_8>=0 && 1>=free_8 && G>=1 && -1+C>=1 && free_8>=1+free_9 ], cost: 3



Accelerating simple loops of location 2.

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

   Accelerating the following rules:

     26: f11 -> f11 : A'=0, B'=0, D'=2+D, [ G>=1 && 0>=C && 0>=1+D ], cost: 3

     27: f11 -> f11 : A'=0, B'=1, D'=2+D, G'=-1+G, [ G>=1 && 0>=C && 1+D==1 ], cost: 3

     28: f11 -> f11 : A'=1, B'=0, D'=2+D, G'=-1+G, [ G>=1 && 0>=C && D==1 ], cost: 3

     29: f11 -> f11 : A'=0, B'=0, C'=free_10, D'=0, E'=1+E, [ G>=1 && 0>=C && D==2 && free_10>=0 ], cost: 3

     30: f11 -> f11 : A'=0, B'=1, C'=free_10, D'=0, E'=1+E, G'=-1+G, [ G>=1 && 0>=C && D==2 && free_10>=0 ], cost: 3

     31: f11 -> f11 : A'=0, B'=0, C'=0, D'=1, E'=1+E, [ G>=1 && 0>=C && D>=3 ], cost: 3

     32: f11 -> f11 : A'=free_6, B'=0, C'=0, D'=1, E'=1+E, G'=-1+G, [ 1>=free_6 && G>=1 && 0>=C && D>=3 && free_6>=1 ], cost: 3

     33: f11 -> f11 : A'=free_7, B'=free_7, C'=-1+free_5, D'=0, E'=1+E, [ free_7>=0 && 1>=free_7 && G>=1 && 0>=C && D>=3 && free_5>=1 ], cost: 3

     34: f11 -> f11 : A'=free_6, B'=free_7, C'=-1+free_5, D'=0, E'=1+E, G'=-1+G, [ free_7>=0 && 1>=free_7 && free_6>=0 && 1>=free_6 && G>=1 && 0>=C && D>=3 && free_5>=1 && free_7>=1+free_6 ], cost: 3

     35: f11 -> f11 : A'=free_6, B'=free_7, C'=-1+free_5, D'=0, E'=1+E, G'=-1+G, [ free_7>=0 && 1>=free_7 && free_6>=0 && 1>=free_6 && G>=1 && 0>=C && D>=3 && free_5>=1 && free_6>=1+free_7 ], cost: 3

     36: f11 -> f11 : A'=0, B'=0, C'=-1+C, D'=1+D, [ 1-C==0 && G>=1 && 0>=D ], cost: 3

     37: f11 -> f11 : A'=free_8, B'=0, C'=-1+C, D'=1+D, G'=-1+G, [ 1>=free_8 && 1-C==0 && G>=1 && 0>=D && free_8>=1 ], cost: 3

     38: f11 -> f11 : A'=1, B'=1, C'=-1+C, D'=1+D, [ 1-C==0 && G>=1 && D==1 ], cost: 3

     39: f11 -> f11 : A'=free_8, B'=1, C'=-1+C, D'=1+D, G'=-1+G, [ free_8>=0 && 1-C==0 && G>=1 && D==1 && 1>=1+free_8 ], cost: 3

     40: f11 -> f11 : A'=0, B'=0, C'=-1+C, D'=1+D, [ 1-C==0 && G>=1 && D==2 ], cost: 3

     41: f11 -> f11 : A'=free_8, B'=0, C'=-1+C, D'=1+D, G'=-1+G, [ 1>=free_8 && 1-C==0 && G>=1 && D==2 && free_8>=1 ], cost: 3

     42: f11 -> f11 : A'=free_9, B'=free_9, C'=free_10, D'=0, E'=1+E, [ free_9>=0 && 1>=free_9 && 1-C==0 && G>=1 && free_10>=0 && D>=3 ], cost: 3

     43: f11 -> f11 : A'=free_8, B'=free_9, C'=free_10, D'=0, E'=1+E, G'=-1+G, [ free_9>=0 && 1>=free_9 && free_8>=0 && 1>=free_8 && 1-C==0 && G>=1 && free_10>=0 && D>=3 && free_9>=1+free_8 ], cost: 3

     44: f11 -> f11 : A'=free_8, B'=free_9, C'=free_10, D'=0, E'=1+E, G'=-1+G, [ free_9>=0 && 1>=free_9 && free_8>=0 && 1>=free_8 && 1-C==0 && G>=1 && free_10>=0 && D>=3 && free_8>=1+free_9 ], cost: 3

     45: f11 -> f11 : A'=free_9, B'=free_9, C'=-2+C, [ free_9>=0 && 1>=free_9 && G>=1 && -1+C>=1 ], cost: 3

     46: f11 -> f11 : A'=free_8, B'=free_9, C'=-2+C, G'=-1+G, [ free_9>=0 && 1>=free_9 && free_8>=0 && 1>=free_8 && G>=1 && -1+C>=1 && free_9>=1+free_8 ], cost: 3

     47: f11 -> f11 : A'=free_8, B'=free_9, C'=-2+C, G'=-1+G, [ free_9>=0 && 1>=free_9 && free_8>=0 && 1>=free_8 && G>=1 && -1+C>=1 && free_8>=1+free_9 ], cost: 3



   Accelerated rule 26 with metering function meter (where 2*meter==-D), yielding the new rule 48.

   Accelerated rule 27 with metering function meter_1 (where 2*meter_1==-D), yielding the new rule 49.

   Accelerated rule 28 with metering function meter_2 (where 2*meter_2==1-D), yielding the new rule 50.

   Accelerated rule 29 with metering function meter_3 (where 2*meter_3==-2+D), yielding the new rule 51.

   Accelerated rule 30 with metering function meter_4 (where 2*meter_4==-2+D), yielding the new rule 52.

   Found no metering function for rule 31.

   Found no metering function for rule 32.

   Found no metering function for rule 33.

   Found no metering function for rule 34.

   Found no metering function for rule 35.

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

   Accelerated rule 37 with metering function -1+C, yielding the new rule 54.

   Accelerated rule 38 with metering function meter_5 (where 2*meter_5==C-D), yielding the new rule 55.

   Accelerated rule 39 with metering function meter_6 (where 2*meter_6==C-D), yielding the new rule 56.

   Accelerated rule 40 with metering function meter_7 (where 2*meter_7==1+C-D), yielding the new rule 57.

   Accelerated rule 41 with metering function meter_8 (where 2*meter_8==1+C-D), yielding the new rule 58.

      During metering: Instantiating temporary variables by {free_10==0}

   Accelerated rule 42 with metering function -1+C, yielding the new rule 59.

      During metering: Instantiating temporary variables by {free_10==0}

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

      During metering: Instantiating temporary variables by {free_10==0}

   Accelerated rule 44 with metering function -1+C, yielding the new rule 61.

   Accelerated rule 45 with metering function meter_9 (where 2*meter_9==-1+C), yielding the new rule 62.

   Accelerated rule 46 with metering function meter_10 (where 2*meter_10==-1+C) (after adding C<=G), yielding the new rule 63.

   Accelerated rule 47 with metering function meter_11 (where 2*meter_11==-1+C) (after adding C<=G), yielding the new rule 64.

      During metering: Instantiating temporary variables by {meter==1}

   Nested simple loops 36 (outer loop) and 48 (inner loop) with metering function -1+C, resulting in the new rules: 65.

   Nested simple loops 37 (outer loop) and 48 (inner loop) with metering function -1+C, resulting in the new rules: 66.

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

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

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

   Nested simple loops 29 (outer loop) and 62 (inner loop) with metering function meter_16 (where 2*meter_16==-2+D), resulting in the new rules: 70.

   Nested simple loops 30 (outer loop) and 62 (inner loop) with metering function meter_17 (where 2*meter_17==-2+D), resulting in the new rules: 71.

      During metering: Instantiating temporary variables by {meter_9==1}

      During metering: Instantiating temporary variables by {meter_9==1}

   Nested simple loops 38 (outer loop) and 62 (inner loop) with metering function 1-D, resulting in the new rules: 72.

   Nested simple loops 39 (outer loop) and 62 (inner loop) with metering function 1-D, resulting in the new rules: 73.

   Nested simple loops 40 (outer loop) and 62 (inner loop) with metering function 2-D, resulting in the new rules: 74.

   Nested simple loops 41 (outer loop) and 62 (inner loop) with metering function 2-D, resulting in the new rules: 75.

      During metering: Instantiating temporary variables by {meter_9==1,free_10==0}

      During metering: Instantiating temporary variables by {meter_9==1,free_10==0}

      During metering: Instantiating temporary variables by {meter_9==1,free_10==0}

      During metering: Instantiating temporary variables by {meter_9==1}

      During metering: Instantiating temporary variables by {meter_9==1}

   Nested simple loops 29 (outer loop) and 63 (inner loop) with metering function meter_25 (where 2*meter_25==-2+D), resulting in the new rules: 76.

   Nested simple loops 30 (outer loop) and 63 (inner loop) with metering function meter_26 (where 2*meter_26==-2+D), resulting in the new rules: 77.

      During metering: Instantiating temporary variables by {meter_10==1}

   Nested simple loops 38 (outer loop) and 63 (inner loop) with metering function 1-D, resulting in the new rules: 78.

   Nested simple loops 39 (outer loop) and 63 (inner loop) with metering function 1-D, resulting in the new rules: 79.

   Nested simple loops 40 (outer loop) and 63 (inner loop) with metering function 2-D, resulting in the new rules: 80.

      During metering: Instantiating temporary variables by {meter_10==1,free_10==0}

      During metering: Instantiating temporary variables by {meter_10==1,free_10==0}

      During metering: Instantiating temporary variables by {meter_10==1}

   Nested simple loops 29 (outer loop) and 64 (inner loop) with metering function meter_31 (where 2*meter_31==-2+D), resulting in the new rules: 81.

   Nested simple loops 30 (outer loop) and 64 (inner loop) with metering function meter_32 (where 2*meter_32==-2+D), resulting in the new rules: 82.

      During metering: Instantiating temporary variables by {meter_11==1}

      During metering: Instantiating temporary variables by {meter_11==1}

   Nested simple loops 38 (outer loop) and 64 (inner loop) with metering function 1-D, resulting in the new rules: 83.

   Nested simple loops 40 (outer loop) and 64 (inner loop) with metering function 2-D, resulting in the new rules: 84.

   Nested simple loops 41 (outer loop) and 64 (inner loop) with metering function 2-D, resulting in the new rules: 85.

      During metering: Instantiating temporary variables by {meter_11==1,free_10==0}

      During metering: Instantiating temporary variables by {meter_11==1,free_10==0}

      During metering: Instantiating temporary variables by {meter_11==1}

   Removing the simple loops: 26 27 28 29 30 36 37 38 39 40 41 42 43 44 45 46 47.



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

   Start location: f0

      1: f0 -> f11 : A'=0, B'=0, C'=free, D'=0, E'=1, F'=free_1, G'=free_1, [ free>=0 && free_1>=1 ], cost: 1

     31: f11 -> f11 : A'=0, B'=0, C'=0, D'=1, E'=1+E, [ G>=1 && 0>=C && D>=3 ], cost: 3

     32: f11 -> f11 : A'=free_6, B'=0, C'=0, D'=1, E'=1+E, G'=-1+G, [ 1>=free_6 && G>=1 && 0>=C && D>=3 && free_6>=1 ], cost: 3

     33: f11 -> f11 : A'=free_7, B'=free_7, C'=-1+free_5, D'=0, E'=1+E, [ free_7>=0 && 1>=free_7 && G>=1 && 0>=C && D>=3 && free_5>=1 ], cost: 3

     34: f11 -> f11 : A'=free_6, B'=free_7, C'=-1+free_5, D'=0, E'=1+E, G'=-1+G, [ free_7>=0 && 1>=free_7 && free_6>=0 && 1>=free_6 && G>=1 && 0>=C && D>=3 && free_5>=1 && free_7>=1+free_6 ], cost: 3

     35: f11 -> f11 : A'=free_6, B'=free_7, C'=-1+free_5, D'=0, E'=1+E, G'=-1+G, [ free_7>=0 && 1>=free_7 && free_6>=0 && 1>=free_6 && G>=1 && 0>=C && D>=3 && free_5>=1 && free_6>=1+free_7 ], cost: 3

     48: f11 -> f11 : A'=0, B'=0, D'=2*meter+D, [ G>=1 && 0>=C && 0>=1+D && 2*meter==-D && meter>=1 ], cost: 3*meter

     49: f11 -> f11 : A'=0, B'=1, D'=D+2*meter_1, G'=G-meter_1, [ G>=1 && 0>=C && 1+D==1 && 2*meter_1==-D && meter_1>=1 ], cost: 3*meter_1

     50: f11 -> f11 : A'=1, B'=0, D'=D+2*meter_2, G'=G-meter_2, [ G>=1 && 0>=C && D==1 && 2*meter_2==1-D && meter_2>=1 ], cost: 3*meter_2

     51: f11 -> f11 : A'=0, B'=0, C'=free_10, D'=0, E'=E+meter_3, [ G>=1 && 0>=C && D==2 && free_10>=0 && 2*meter_3==-2+D && meter_3>=1 ], cost: 3*meter_3

     52: f11 -> f11 : A'=0, B'=1, C'=free_10, D'=0, E'=E+meter_4, G'=G-meter_4, [ G>=1 && 0>=C && D==2 && free_10>=0 && 2*meter_4==-2+D && meter_4>=1 ], cost: 3*meter_4

     53: f11 -> f11 : A'=0, B'=0, C'=1, D'=-1+C+D, [ 1-C==0 && G>=1 && 0>=D && -1+C>=1 ], cost: -3+3*C

     54: f11 -> f11 : A'=free_8, B'=0, C'=1, D'=-1+C+D, G'=1-C+G, [ 1>=free_8 && 1-C==0 && G>=1 && 0>=D && free_8>=1 && -1+C>=1 ], cost: -3+3*C

     55: f11 -> f11 : A'=1, B'=1, C'=C-meter_5, D'=D+meter_5, [ 1-C==0 && G>=1 && D==1 && 2*meter_5==C-D && meter_5>=1 ], cost: 3*meter_5

     56: f11 -> f11 : A'=free_8, B'=1, C'=C-meter_6, D'=D+meter_6, G'=G-meter_6, [ free_8>=0 && 1-C==0 && G>=1 && D==1 && 1>=1+free_8 && 2*meter_6==C-D && meter_6>=1 ], cost: 3*meter_6

     57: f11 -> f11 : A'=0, B'=0, C'=C-meter_7, D'=meter_7+D, [ 1-C==0 && G>=1 && D==2 && 2*meter_7==1+C-D && meter_7>=1 ], cost: 3*meter_7

     58: f11 -> f11 : A'=free_8, B'=0, C'=-meter_8+C, D'=meter_8+D, G'=-meter_8+G, [ 1>=free_8 && 1-C==0 && G>=1 && D==2 && free_8>=1 && 2*meter_8==1+C-D && meter_8>=1 ], cost: 3*meter_8

     59: f11 -> f11 : A'=free_9, B'=free_9, C'=0, D'=0, E'=-1+C+E, [ free_9>=0 && 1>=free_9 && 1-C==0 && G>=1 && D>=3 && -1+C>=1 ], cost: -3+3*C

     60: f11 -> f11 : A'=free_8, B'=free_9, C'=0, D'=0, E'=-1+C+E, G'=1-C+G, [ free_9>=0 && 1>=free_9 && free_8>=0 && 1>=free_8 && 1-C==0 && G>=1 && D>=3 && free_9>=1+free_8 && -1+C>=1 ], cost: -3+3*C

     61: f11 -> f11 : A'=free_8, B'=free_9, C'=0, D'=0, E'=-1+C+E, G'=1-C+G, [ free_9>=0 && 1>=free_9 && free_8>=0 && 1>=free_8 && 1-C==0 && G>=1 && D>=3 && free_8>=1+free_9 && -1+C>=1 ], cost: -3+3*C

     62: f11 -> f11 : A'=free_9, B'=free_9, C'=C-2*meter_9, [ free_9>=0 && 1>=free_9 && G>=1 && -1+C>=1 && 2*meter_9==-1+C && meter_9>=1 ], cost: 3*meter_9

     63: f11 -> f11 : A'=free_8, B'=free_9, C'=C-2*meter_10, G'=-meter_10+G, [ free_9>=0 && 1>=free_9 && free_8>=0 && 1>=free_8 && G>=1 && -1+C>=1 && free_9>=1+free_8 && C<=G && 2*meter_10==-1+C && meter_10>=1 ], cost: 3*meter_10

     64: f11 -> f11 : A'=free_8, B'=free_9, C'=C-2*meter_11, G'=-meter_11+G, [ free_9>=0 && 1>=free_9 && free_8>=0 && 1>=free_8 && G>=1 && -1+C>=1 && free_8>=1+free_9 && C<=G && 2*meter_11==-1+C && meter_11>=1 ], cost: 3*meter_11

     65: f11 -> f11 : A'=0, B'=0, C'=1, D'=-1+C+D+2*meter*(-1+C), [ 1-C==0 && G>=1 && 0>=2+D && 2*meter==-1-D && meter>=1 && -1+C>=1 ], cost: -3+3*C+3*meter*(-1+C)

     66: f11 -> f11 : A'=0, B'=0, C'=1, D'=-1+C+D+2*meter*(-1+C), G'=1-C+G, [ 1-C==0 && -1+G>=1 && 0>=2+D && 2*meter==-1-D && meter>=1 && -1+C>=1 ], cost: -3+3*C+3*meter*(-1+C)

     67: f11 -> f11 : A'=0, B'=0, C'=C-2*meter_13, D'=2*meter*meter_13+D, [ G>=1 && 2-C==0 && 0>=1+D && 2*meter==-D && meter>=1 && 2*meter_13==-2+C && meter_13>=1 ], cost: 3*meter*meter_13+3*meter_13

     68: f11 -> f11 : A'=0, B'=0, C'=C-2*meter_14, D'=D+2*meter*meter_14, G'=G-meter_14, [ 2-C==0 && -1+G>=1 && 0>=1+D && 2*meter==-D && meter>=1 && 2*meter_14==-2+C && meter_14>=1 ], cost: 3*meter_14+3*meter*meter_14

     69: f11 -> f11 : A'=0, B'=0, C'=C-2*meter_15, D'=D+2*meter*meter_15, G'=G-meter_15, [ 2-C==0 && -1+G>=1 && 0>=1+D && 2*meter==-D && meter>=1 && 2*meter_15==-2+C && meter_15>=1 ], cost: 3*meter_15+3*meter*meter_15

     70: f11 -> f11 : A'=free_9, B'=free_9, C'=1, D'=0, E'=E+meter_16, [ G>=1 && 0>=C && D==2 && free_9>=0 && 1>=free_9 && 2*meter_9>=1 && meter_9>=1 && 2*meter_16==-2+D && meter_16>=1 ], cost: 3*meter_9*meter_16+3*meter_16

     71: f11 -> f11 : A'=free_9, B'=free_9, C'=1, D'=0, E'=meter_17+E, G'=-meter_17+G, [ 0>=C && D==2 && free_9>=0 && 1>=free_9 && -1+G>=1 && 2*meter_9>=1 && meter_9>=1 && 2*meter_17==-2+D && meter_17>=1 ], cost: 3*meter_17+3*meter_17*meter_9

     72: f11 -> f11 : A'=1, B'=1, C'=-1+C+D+2*(-1+D)*meter_9, D'=1, [ G>=1 && -1+C>=1 && 2*meter_9==-1+C && meter_9>=1 && D==1 && 1-D>=1 ], cost: 3-3*D-3*(-1+D)*meter_9

     73: f11 -> f11 : A'=0, B'=1, C'=-1+C+D+2*(-1+D)*meter_9, D'=1, G'=-1+G+D, [ G>=1 && -1+C>=1 && 2*meter_9==-1+C && meter_9>=1 && D==1 && 1-D>=1 ], cost: 3-3*D-3*(-1+D)*meter_9

     74: f11 -> f11 : A'=0, B'=0, C'=-2+2*meter_9*(-2+D)+C+D, D'=2, [ G>=1 && -1+C>=1 && 2*meter_9==-1+C && meter_9>=1 && D==2 && 2-D>=1 ], cost: 6-3*meter_9*(-2+D)-3*D

     75: f11 -> f11 : A'=1, B'=0, C'=-2+2*meter_9*(-2+D)+C+D, D'=2, G'=-2+G+D, [ G>=1 && -1+C>=1 && 2*meter_9==-1+C && meter_9>=1 && D==2 && 2-D>=1 ], cost: 6-3*meter_9*(-2+D)-3*D

     76: f11 -> f11 : A'=free_8, B'=free_9, C'=1, D'=0, E'=meter_25+E, G'=G-meter_10*meter_25, [ G>=1 && 0>=C && D==2 && free_9>=0 && 1>=free_9 && free_8>=0 && 1>=free_8 && 2*meter_10>=1 && free_9>=1+free_8 && 1+2*meter_10<=G && meter_10>=1 && 2*meter_25==-2+D && meter_25>=1 ], cost: 3*meter_25+3*meter_10*meter_25

     77: f11 -> f11 : A'=free_8, B'=free_9, C'=1, D'=0, E'=meter_26+E, G'=-meter_10*meter_26+G-meter_26, [ 0>=C && D==2 && free_9>=0 && 1>=free_9 && free_8>=0 && 1>=free_8 && -1+G>=1 && 2*meter_10>=1 && free_9>=1+free_8 && 1+2*meter_10<=-1+G && meter_10>=1 && 2*meter_26==-2+D && meter_26>=1 ], cost: 3*meter_10*meter_26+3*meter_26

     78: f11 -> f11 : A'=1, B'=1, C'=-1+C+2*(-1+D)*meter_10+D, D'=1, G'=(-1+D)*meter_10+G, [ G>=1 && -1+C>=1 && C<=G && 2*meter_10==-1+C && meter_10>=1 && -meter_10+G>=1 && D==1 && 1-D>=1 ], cost: 3-3*(-1+D)*meter_10-3*D

     79: f11 -> f11 : A'=0, B'=1, C'=-1+C+2*(-1+D)*meter_10+D, D'=1, G'=-1+(-1+D)*meter_10+G+D, [ G>=1 && -1+C>=1 && C<=G && 2*meter_10==-1+C && meter_10>=1 && -meter_10+G>=1 && D==1 && 1-D>=1 ], cost: 3-3*(-1+D)*meter_10-3*D

     80: f11 -> f11 : A'=0, B'=0, C'=-2+C+D+2*meter_10*(-2+D), D'=2, G'=G+meter_10*(-2+D), [ G>=1 && -1+C>=1 && C<=G && 2*meter_10==-1+C && meter_10>=1 && -meter_10+G>=1 && D==2 && 2-D>=1 ], cost: 6-3*D-3*meter_10*(-2+D)

     81: f11 -> f11 : A'=free_8, B'=free_9, C'=1, D'=0, E'=meter_31+E, G'=-meter_11*meter_31+G, [ G>=1 && 0>=C && D==2 && free_9>=0 && 1>=free_9 && free_8>=0 && 1>=free_8 && 2*meter_11>=1 && free_8>=1+free_9 && 1+2*meter_11<=G && meter_11>=1 && 2*meter_31==-2+D && meter_31>=1 ], cost: 3*meter_11*meter_31+3*meter_31

     82: f11 -> f11 : A'=free_8, B'=free_9, C'=1, D'=0, E'=E+meter_32, G'=G-meter_11*meter_32-meter_32, [ 0>=C && D==2 && free_9>=0 && 1>=free_9 && free_8>=0 && 1>=free_8 && -1+G>=1 && 2*meter_11>=1 && free_8>=1+free_9 && 1+2*meter_11<=-1+G && meter_11>=1 && 2*meter_32==-2+D && meter_32>=1 ], cost: 3*meter_11*meter_32+3*meter_32

     83: f11 -> f11 : A'=1, B'=1, C'=-1+C+D+2*(-1+D)*meter_11, D'=1, G'=G+(-1+D)*meter_11, [ G>=1 && -1+C>=1 && C<=G && 2*meter_11==-1+C && meter_11>=1 && -meter_11+G>=1 && D==1 && 1-D>=1 ], cost: 3-3*D-3*(-1+D)*meter_11

     84: f11 -> f11 : A'=0, B'=0, C'=-2+C+D+2*meter_11*(-2+D), D'=2, G'=G+meter_11*(-2+D), [ G>=1 && -1+C>=1 && C<=G && 2*meter_11==-1+C && meter_11>=1 && -meter_11+G>=1 && D==2 && 2-D>=1 ], cost: 6-3*D-3*meter_11*(-2+D)

     85: f11 -> f11 : A'=1, B'=0, C'=-2+C+D+2*meter_11*(-2+D), D'=2, G'=-2+G+D+meter_11*(-2+D), [ G>=1 && -1+C>=1 && C<=G && 2*meter_11==-1+C && meter_11>=1 && -meter_11+G>=1 && D==2 && 2-D>=1 ], cost: 6-3*D-3*meter_11*(-2+D)



Chained accelerated rules (with incoming rules):

   Start location: f0

      1: f0 -> f11 : A'=0, B'=0, C'=free, D'=0, E'=1, F'=free_1, G'=free_1, [ free>=0 && free_1>=1 ], cost: 1

     86: f0 -> f11 : A'=free_9, B'=free_9, C'=1, D'=0, E'=1, F'=free_1, G'=free_1, [ free_1>=1 && free_9>=0 && 1>=free_9 && 2*meter_9>=1 && meter_9>=1 ], cost: 1+3*meter_9

     87: f0 -> f11 : A'=free_8, B'=free_9, C'=1, D'=0, E'=1, F'=free_1, G'=-meter_10+free_1, [ free_1>=1 && free_9>=0 && 1>=free_9 && free_8>=0 && 1>=free_8 && 2*meter_10>=1 && free_9>=1+free_8 && 1+2*meter_10<=free_1 && meter_10>=1 ], cost: 1+3*meter_10

     88: f0 -> f11 : A'=free_8, B'=free_9, C'=1, D'=0, E'=1, F'=free_1, G'=-meter_11+free_1, [ free_1>=1 && free_9>=0 && 1>=free_9 && free_8>=0 && 1>=free_8 && 2*meter_11>=1 && free_8>=1+free_9 && 1+2*meter_11<=free_1 && meter_11>=1 ], cost: 1+3*meter_11



Removed unreachable locations (and leaf rules with constant cost):

   Start location: f0

     86: f0 -> f11 : A'=free_9, B'=free_9, C'=1, D'=0, E'=1, F'=free_1, G'=free_1, [ free_1>=1 && free_9>=0 && 1>=free_9 && 2*meter_9>=1 && meter_9>=1 ], cost: 1+3*meter_9

     87: f0 -> f11 : A'=free_8, B'=free_9, C'=1, D'=0, E'=1, F'=free_1, G'=-meter_10+free_1, [ free_1>=1 && free_9>=0 && 1>=free_9 && free_8>=0 && 1>=free_8 && 2*meter_10>=1 && free_9>=1+free_8 && 1+2*meter_10<=free_1 && meter_10>=1 ], cost: 1+3*meter_10

     88: f0 -> f11 : A'=free_8, B'=free_9, C'=1, D'=0, E'=1, F'=free_1, G'=-meter_11+free_1, [ free_1>=1 && free_9>=0 && 1>=free_9 && free_8>=0 && 1>=free_8 && 2*meter_11>=1 && free_8>=1+free_9 && 1+2*meter_11<=free_1 && meter_11>=1 ], cost: 1+3*meter_11



### Computing asymptotic complexity ###



Fully simplified ITS problem

   Start location: f0

     86: f0 -> f11 : A'=free_9, B'=free_9, C'=1, D'=0, E'=1, F'=free_1, G'=free_1, [ free_1>=1 && free_9>=0 && 1>=free_9 && 2*meter_9>=1 && meter_9>=1 ], cost: 1+3*meter_9

     87: f0 -> f11 : A'=free_8, B'=free_9, C'=1, D'=0, E'=1, F'=free_1, G'=-meter_10+free_1, [ free_1>=1 && free_9>=0 && 1>=free_9 && free_8>=0 && 1>=free_8 && 2*meter_10>=1 && free_9>=1+free_8 && 1+2*meter_10<=free_1 && meter_10>=1 ], cost: 1+3*meter_10

     88: f0 -> f11 : A'=free_8, B'=free_9, C'=1, D'=0, E'=1, F'=free_1, G'=-meter_11+free_1, [ free_1>=1 && free_9>=0 && 1>=free_9 && free_8>=0 && 1>=free_8 && 2*meter_11>=1 && free_8>=1+free_9 && 1+2*meter_11<=free_1 && meter_11>=1 ], cost: 1+3*meter_11



Computing asymptotic complexity for rule 86

   Solved the limit problem by the following transformations:

      Created initial limit problem:

      2-free_9 (+/+!), 2*meter_9 (+/+!), 1+3*meter_9 (+), 1+free_9 (+/+!), free_1 (+/+!) [not solved]



      removing all constraints (solved by SMT)

      resulting limit problem: [solved]



      applying transformation rule (C) using substitution {free_9==0,meter_9==n,free_1==n}

      resulting limit problem:

      [solved]



   Solution:

      free_9 / 0

      meter_9 / n

      free_1 / n

   Resulting cost 1+3*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+3*n

   Rule cost:   1+3*meter_9

   Rule guard:  [ free_1>=1 && free_9>=0 && 1>=free_9 && 2*meter_9>=1 ]



WORST_CASE(INF,?)


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

(2)
BOUNDS(INF, INF)