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


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


MAYBE
proof of /export/starexec/sandbox2/benchmark/theBenchmark.koat
# AProVE Commit ID: 48fb2092695e11cc9f56e44b17a92a5f88ffb256 marcel 20180622 unpublished dirty


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

(0) CpxIntTrs
(1) Loat Proof [FINISHED, 288.6 s]
(2) BOUNDS(1, INF)


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

(0)
Obligation:
Complexity Int TRS consisting of the following rules:
f0(A, B, C, D, E, F, G) -> Com_1(f1(A, B, C, D, E, F, G)) :|: A >= 0 && 3 >= A && B >= 0 && 3 >= B && 3 >= C && D >= 0 && 3 >= E && E >= 0
f1(A, B, C, D, E, F, G) -> Com_1(f2(A, B, C, D, E, D + 1, G)) :|: 1 + B >= 2 * D
f1(A, B, C, D, E, F, G) -> Com_1(f2(A, B, C, D, E, D - 1, G)) :|: 2 * D >= 4 + B
f1(A, B, C, D, E, F, G) -> Com_1(f2(A, B, C, D, E, D, G)) :|: B + 2 >= 2 * D && B + 2 <= 2 * D
f1(A, B, C, D, E, F, G) -> Com_1(f2(A, B, C, D, E, D, G)) :|: B + 3 >= 2 * D && B + 3 <= 2 * D
f2(A, B, C, D, E, F, G) -> Com_1(f3(A, B, C, D, E, F, E + 1)) :|: D + A >= 2 * E + 1
f2(A, B, C, D, E, F, G) -> Com_1(f3(A, B, C, D, E, F, E - 1)) :|: 2 * E >= 2 + D + A
f2(A, B, C, D, E, F, G) -> Com_1(f3(A, B, C, D, E, F, E)) :|: D + A >= 2 * E && D + A <= 2 * E
f2(A, B, C, D, E, F, G) -> Com_1(f3(A, B, C, D, E, F, E)) :|: D + A + 1 >= 2 * E && D + A + 1 <= 2 * E
f3(A, B, C, D, E, F, G) -> Com_1(f1(A, B, C, F, G, F, G)) :|: D >= F + 1
f3(A, B, C, D, E, F, G) -> Com_1(f1(A, B, C, F, G, F, G)) :|: F >= D + 1
f3(A, B, C, D, E, F, G) -> Com_1(f1(A, B, C, F, G, F, G)) :|: E >= G + 1
f3(A, B, C, D, E, F, G) -> Com_1(f1(A, B, C, F, G, F, G)) :|: G >= E + 1

The start-symbols are:[f0_7]


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

(1) Loat Proof (FINISHED)


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



Initial linear ITS problem

   Start location: f0

      0: f0 -> f1 : [ A>=0 && 3>=A && B>=0 && 3>=B && 3>=C && D>=0 && 3>=E && E>=0 ], cost: 1

      1: f1 -> f2 : F'=1+D, [ 1+B>=2*D ], cost: 1

      2: f1 -> f2 : F'=-1+D, [ 2*D>=4+B ], cost: 1

      3: f1 -> f2 : F'=D, [ 2+B==2*D ], cost: 1

      4: f1 -> f2 : F'=D, [ 3+B==2*D ], cost: 1

      5: f2 -> f3 : G'=1+E, [ D+A>=1+2*E ], cost: 1

      6: f2 -> f3 : G'=-1+E, [ 2*E>=2+D+A ], cost: 1

      7: f2 -> f3 : G'=E, [ D+A==2*E ], cost: 1

      8: f2 -> f3 : G'=E, [ 1+D+A==2*E ], cost: 1

      9: f3 -> f1 : D'=F, E'=G, [ D>=1+F ], cost: 1

     10: f3 -> f1 : D'=F, E'=G, [ F>=1+D ], cost: 1

     11: f3 -> f1 : D'=F, E'=G, [ E>=1+G ], cost: 1

     12: f3 -> f1 : D'=F, E'=G, [ G>=1+E ], cost: 1



### Simplification by acceleration and chaining ###



Eliminated locations (on tree-shaped paths):

   Start location: f0

      0: f0 -> f1 : [ A>=0 && 3>=A && B>=0 && 3>=B && 3>=C && D>=0 && 3>=E && E>=0 ], cost: 1

     13: f1 -> f3 : F'=1+D, G'=1+E, [ 1+B>=2*D && D+A>=1+2*E ], cost: 2

     14: f1 -> f3 : F'=1+D, G'=-1+E, [ 1+B>=2*D && 2*E>=2+D+A ], cost: 2

     15: f1 -> f3 : F'=1+D, G'=E, [ 1+B>=2*D && D+A==2*E ], cost: 2

     16: f1 -> f3 : F'=1+D, G'=E, [ 1+B>=2*D && 1+D+A==2*E ], cost: 2

     17: f1 -> f3 : F'=-1+D, G'=1+E, [ 2*D>=4+B && D+A>=1+2*E ], cost: 2

     18: f1 -> f3 : F'=-1+D, G'=-1+E, [ 2*D>=4+B && 2*E>=2+D+A ], cost: 2

     19: f1 -> f3 : F'=-1+D, G'=E, [ 2*D>=4+B && D+A==2*E ], cost: 2

     20: f1 -> f3 : F'=-1+D, G'=E, [ 2*D>=4+B && 1+D+A==2*E ], cost: 2

     21: f1 -> f3 : F'=D, G'=1+E, [ 2+B==2*D && D+A>=1+2*E ], cost: 2

     22: f1 -> f3 : F'=D, G'=-1+E, [ 2+B==2*D && 2*E>=2+D+A ], cost: 2

     23: f1 -> f3 : F'=D, G'=E, [ 2+B==2*D && D+A==2*E ], cost: 2

     24: f1 -> f3 : F'=D, G'=E, [ 2+B==2*D && 1+D+A==2*E ], cost: 2

     25: f1 -> f3 : F'=D, G'=1+E, [ 3+B==2*D && D+A>=1+2*E ], cost: 2

     26: f1 -> f3 : F'=D, G'=-1+E, [ 3+B==2*D && 2*E>=2+D+A ], cost: 2

     27: f1 -> f3 : F'=D, G'=E, [ 3+B==2*D && D+A==2*E ], cost: 2

     28: f1 -> f3 : F'=D, G'=E, [ 3+B==2*D && 1+D+A==2*E ], cost: 2

      9: f3 -> f1 : D'=F, E'=G, [ D>=1+F ], cost: 1

     10: f3 -> f1 : D'=F, E'=G, [ F>=1+D ], cost: 1

     11: f3 -> f1 : D'=F, E'=G, [ E>=1+G ], cost: 1

     12: f3 -> f1 : D'=F, E'=G, [ G>=1+E ], cost: 1



Eliminated locations (on tree-shaped paths):

   Start location: f0

      0: f0 -> f1 : [ A>=0 && 3>=A && B>=0 && 3>=B && 3>=C && D>=0 && 3>=E && E>=0 ], cost: 1

     29: f1 -> f1 : D'=1+D, E'=1+E, F'=1+D, G'=1+E, [ 1+B>=2*D && D+A>=1+2*E ], cost: 3

     30: f1 -> f1 : D'=1+D, E'=1+E, F'=1+D, G'=1+E, [ 1+B>=2*D && D+A>=1+2*E ], cost: 3

     31: f1 -> f1 : D'=1+D, E'=-1+E, F'=1+D, G'=-1+E, [ 1+B>=2*D && 2*E>=2+D+A ], cost: 3

     32: f1 -> f1 : D'=1+D, E'=-1+E, F'=1+D, G'=-1+E, [ 1+B>=2*D && 2*E>=2+D+A ], cost: 3

     33: f1 -> f1 : D'=1+D, E'=E, F'=1+D, G'=E, [ 1+B>=2*D && D+A==2*E ], cost: 3

     34: f1 -> f1 : D'=1+D, E'=E, F'=1+D, G'=E, [ 1+B>=2*D && 1+D+A==2*E ], cost: 3

     35: f1 -> f1 : D'=-1+D, E'=1+E, F'=-1+D, G'=1+E, [ 2*D>=4+B && D+A>=1+2*E ], cost: 3

     36: f1 -> f1 : D'=-1+D, E'=1+E, F'=-1+D, G'=1+E, [ 2*D>=4+B && D+A>=1+2*E ], cost: 3

     37: f1 -> f1 : D'=-1+D, E'=-1+E, F'=-1+D, G'=-1+E, [ 2*D>=4+B && 2*E>=2+D+A ], cost: 3

     38: f1 -> f1 : D'=-1+D, E'=-1+E, F'=-1+D, G'=-1+E, [ 2*D>=4+B && 2*E>=2+D+A ], cost: 3

     39: f1 -> f1 : D'=-1+D, E'=E, F'=-1+D, G'=E, [ 2*D>=4+B && D+A==2*E ], cost: 3

     40: f1 -> f1 : D'=-1+D, E'=E, F'=-1+D, G'=E, [ 2*D>=4+B && 1+D+A==2*E ], cost: 3

     41: f1 -> f1 : D'=D, E'=1+E, F'=D, G'=1+E, [ 2+B==2*D && D+A>=1+2*E ], cost: 3

     42: f1 -> f1 : D'=D, E'=-1+E, F'=D, G'=-1+E, [ 2+B==2*D && 2*E>=2+D+A ], cost: 3

     43: f1 -> f1 : D'=D, E'=1+E, F'=D, G'=1+E, [ 3+B==2*D && D+A>=1+2*E ], cost: 3

     44: f1 -> f1 : D'=D, E'=-1+E, F'=D, G'=-1+E, [ 3+B==2*D && 2*E>=2+D+A ], cost: 3



Accelerating simple loops of location 1.

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

   Accelerating the following rules:

     30: f1 -> f1 : D'=1+D, E'=1+E, F'=1+D, G'=1+E, [ 1+B>=2*D && D+A>=1+2*E ], cost: 3

     32: f1 -> f1 : D'=1+D, E'=-1+E, F'=1+D, G'=-1+E, [ 1+B>=2*D && 2*E>=2+D+A ], cost: 3

     33: f1 -> f1 : D'=1+D, F'=1+D, G'=E, [ 1+B>=2*D && D+A==2*E ], cost: 3

     34: f1 -> f1 : D'=1+D, F'=1+D, G'=E, [ 1+B>=2*D && 1+D+A==2*E ], cost: 3

     36: f1 -> f1 : D'=-1+D, E'=1+E, F'=-1+D, G'=1+E, [ 2*D>=4+B && D+A>=1+2*E ], cost: 3

     38: f1 -> f1 : D'=-1+D, E'=-1+E, F'=-1+D, G'=-1+E, [ 2*D>=4+B && 2*E>=2+D+A ], cost: 3

     39: f1 -> f1 : D'=-1+D, F'=-1+D, G'=E, [ 2*D>=4+B && D+A==2*E ], cost: 3

     40: f1 -> f1 : D'=-1+D, F'=-1+D, G'=E, [ 2*D>=4+B && 1+D+A==2*E ], cost: 3

     41: f1 -> f1 : E'=1+E, F'=D, G'=1+E, [ 2+B==2*D && D+A>=1+2*E ], cost: 3

     42: f1 -> f1 : E'=-1+E, F'=D, G'=-1+E, [ 2+B==2*D && 2*E>=2+D+A ], cost: 3

     43: f1 -> f1 : E'=1+E, F'=D, G'=1+E, [ 3+B==2*D && D+A>=1+2*E ], cost: 3

     44: f1 -> f1 : E'=-1+E, F'=D, G'=-1+E, [ 3+B==2*D && 2*E>=2+D+A ], cost: 3



   Accelerated rule 30 with backward acceleration, yielding the new rule 45.

   Accelerated rule 32 with backward acceleration, yielding the new rule 46.

   Accelerated rule 33 with metering function -D-A+2*E, yielding the new rule 47.

   Accelerated rule 34 with metering function -1-D-A+2*E, yielding the new rule 48.

   Accelerated rule 36 with backward acceleration, yielding the new rule 49.

   Accelerated rule 38 with backward acceleration, yielding the new rule 50.

   Accelerated rule 39 with metering function D+A-2*E, yielding the new rule 51.

   Accelerated rule 40 with metering function 1+D+A-2*E, yielding the new rule 52.

   Accelerated rule 41 with metering function meter (where 2*meter==D+A-2*E), yielding the new rule 53.

   Accelerated rule 42 with metering function meter_1 (where 2*meter_1==-1-D-A+2*E), yielding the new rule 54.

   Accelerated rule 43 with metering function meter_2 (where 2*meter_2==D+A-2*E), yielding the new rule 55.

   Accelerated rule 44 with metering function meter_3 (where 2*meter_3==-1-D-A+2*E), yielding the new rule 56.

   Nested simple loops 32 (outer loop) and 45 (inner loop) with metering function meter_4 (where 2*meter_4==-1-D-A-k+2*E), resulting in the new rules: 57.

   Nested simple loops 33 (outer loop) and 45 (inner loop) with metering function meter_6 (where 4*meter_6==1-2*D-k+B), resulting in the new rules: 58, 59.

      During metering: Instantiating temporary variables by {k==-1+D+A-2*E}

      During metering: Instantiating temporary variables by {k==-1+D+A-2*E}

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

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

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

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

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

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

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

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

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

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

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

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

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

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

   Nested simple loops 36 (outer loop) and 50 (inner loop) with metering function meter_23 (where 2*meter_23==D+A-k_3-2*E), resulting in the new rules: 60.

   Nested simple loops 40 (outer loop) and 50 (inner loop) with metering function meter_25 (where 4*meter_25==-4+2*D-k_3-B), resulting in the new rules: 61, 62.

      During metering: Instantiating temporary variables by {k_3==-2-D-A+2*E}

      During metering: Instantiating temporary variables by {k_3==-2-D-A+2*E}

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

   Nested simple loops 36 (outer loop) and 53 (inner loop) with metering function meter_29 (where 2*meter_29==-4+2*D-B), resulting in the new rules: 64.

   Nested simple loops 32 (outer loop) and 54 (inner loop) with metering function meter_30 (where 2*meter_30==-2*D+B), resulting in the new rules: 65.

   Nested simple loops 38 (outer loop) and 54 (inner loop) with metering function meter_31 (where 2*meter_31==-4+2*D-B), resulting in the new rules: 66.

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

   Nested simple loops 36 (outer loop) and 55 (inner loop) with metering function meter_33 (where 2*meter_33==-5+2*D-B), resulting in the new rules: 68.

   Nested simple loops 32 (outer loop) and 56 (inner loop) with metering function meter_34 (where 2*meter_34==1-2*D+B), resulting in the new rules: 69.

   Nested simple loops 38 (outer loop) and 56 (inner loop) with metering function meter_35 (where 2*meter_35==-5+2*D-B), resulting in the new rules: 70.

   Removing the simple loops: 30 32 33 34 36 38 39 40 41 42 43 44.



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

   Start location: f0

      0: f0 -> f1 : [ A>=0 && 3>=A && B>=0 && 3>=B && 3>=C && D>=0 && 3>=E && E>=0 ], cost: 1

     45: f1 -> f1 : D'=D+k, E'=k+E, F'=D+k, G'=k+E, [ 1+B>=2*D && D+A>=1+2*E && k>0 && 1+B>=-2+2*D+2*k && -1+D+A+k>=-1+2*k+2*E ], cost: 3*k

     46: f1 -> f1 : D'=k_1+D, E'=-k_1+E, F'=k_1+D, G'=-k_1+E, [ 1+B>=2*D && 2*E>=2+D+A && k_1>0 && 1+B>=-2+2*k_1+2*D && 2-2*k_1+2*E>=1+k_1+D+A ], cost: 3*k_1

     47: f1 -> f1 : D'=-A+2*E, F'=-A+2*E, G'=E, [ 1+B>=2*D && D+A==2*E && -D-A+2*E>=1 ], cost: -3*D-3*A+6*E

     48: f1 -> f1 : D'=-1-A+2*E, F'=-1-A+2*E, G'=E, [ 1+B>=2*D && 1+D+A==2*E && -1-D-A+2*E>=1 ], cost: -3-3*D-3*A+6*E

     49: f1 -> f1 : D'=-k_2+D, E'=k_2+E, F'=-k_2+D, G'=k_2+E, [ 2*D>=4+B && D+A>=1+2*E && k_2>0 && 2-2*k_2+2*D>=4+B && 1-k_2+D+A>=-1+2*k_2+2*E ], cost: 3*k_2

     50: f1 -> f1 : D'=D-k_3, E'=-k_3+E, F'=D-k_3, G'=-k_3+E, [ 2*D>=4+B && 2*E>=2+D+A && k_3>0 && 2+2*D-2*k_3>=4+B && 2-2*k_3+2*E>=3+D+A-k_3 ], cost: 3*k_3

     51: f1 -> f1 : D'=-A+2*E, F'=-A+2*E, G'=E, [ 2*D>=4+B && D+A==2*E && D+A-2*E>=1 ], cost: 3*D+3*A-6*E

     52: f1 -> f1 : D'=-1-A+2*E, F'=-1-A+2*E, G'=E, [ 2*D>=4+B && 1+D+A==2*E && 1+D+A-2*E>=1 ], cost: 3+3*D+3*A-6*E

     53: f1 -> f1 : E'=meter+E, F'=D, G'=meter+E, [ 2+B==2*D && D+A>=1+2*E && 2*meter==D+A-2*E && meter>=1 ], cost: 3*meter

     54: f1 -> f1 : E'=-meter_1+E, F'=D, G'=-meter_1+E, [ 2+B==2*D && 2*E>=2+D+A && 2*meter_1==-1-D-A+2*E && meter_1>=1 ], cost: 3*meter_1

     55: f1 -> f1 : E'=E+meter_2, F'=D, G'=E+meter_2, [ 3+B==2*D && D+A>=1+2*E && 2*meter_2==D+A-2*E && meter_2>=1 ], cost: 3*meter_2

     56: f1 -> f1 : E'=-meter_3+E, F'=D, G'=-meter_3+E, [ 3+B==2*D && 2*E>=2+D+A && 2*meter_3==-1-D-A+2*E && meter_3>=1 ], cost: 3*meter_3

     57: f1 -> f1 : D'=meter_4*k+meter_4+D, E'=meter_4*k-meter_4+E, F'=meter_4*k+meter_4+D, G'=meter_4*k-meter_4+E, [ 2+D+A-2*E==0 && 1+B>=2+2*D && k>0 && 1+B>=2*D+2*k && D+A+k>=-3+2*k+2*E && 2*meter_4==-1-D-A-k+2*E && meter_4>=1 ], cost: 3*meter_4*k+3*meter_4

     58: f1 -> f1 : D'=meter_6+D+meter_6*k, E'=meter_6*k+E, F'=meter_6+D+meter_6*k, G'=meter_6*k+E, [ D+A==2*E && 1+B>=2+2*D && k>0 && 1+B>=2*D+2*k && D+A+k>=-1+2*k+2*E && 4*meter_6==1-2*D-k+B && meter_6>=1 ], cost: 3*meter_6+3*meter_6*k

     59: f1 -> f1 : D'=meter_6+D+k+meter_6*k, E'=k+meter_6*k+E, F'=meter_6+D+k+meter_6*k, G'=k+meter_6*k+E, [ 1+B>=2*D && D+A>=1+2*E && k>0 && D+A+k==2*k+2*E && 1+B>=2+2*D+2*k && 1+B>=2*D+4*k && D+A+2*k>=-1+4*k+2*E && 4*meter_6==1-2*D-3*k+B && meter_6>=1 ], cost: 3*meter_6+3*k+3*meter_6*k

     60: f1 -> f1 : D'=-k_3*meter_23+D-meter_23, E'=-k_3*meter_23+meter_23+E, F'=-k_3*meter_23+D-meter_23, G'=-k_3*meter_23+meter_23+E, [ 1-D-A+2*E==0 && -2+2*D>=4+B && k_3>0 && 2*D-2*k_3>=4+B && 4-2*k_3+2*E>=2+D+A-k_3 && 2*meter_23==D+A-k_3-2*E && meter_23>=1 ], cost: 3*k_3*meter_23+3*meter_23

     61: f1 -> f1 : D'=D-meter_25-meter_25*k_3, E'=-meter_25*k_3+E, F'=D-meter_25-meter_25*k_3, G'=-meter_25*k_3+E, [ 1+D+A==2*E && -2+2*D>=4+B && k_3>0 && 2*D-2*k_3>=4+B && 2-2*k_3+2*E>=2+D+A-k_3 && 4*meter_25==-4+2*D-k_3-B && meter_25>=1 ], cost: 3*meter_25+3*meter_25*k_3

     62: f1 -> f1 : D'=D-meter_25-meter_25*k_3-k_3, E'=-meter_25*k_3-k_3+E, F'=D-meter_25-meter_25*k_3-k_3, G'=-meter_25*k_3-k_3+E, [ 2*D>=4+B && 2*E>=2+D+A && k_3>0 && 1+D+A-k_3==-2*k_3+2*E && -2+2*D-2*k_3>=4+B && 2*D-4*k_3>=4+B && 2-4*k_3+2*E>=2+D+A-2*k_3 && 4*meter_25==-4+2*D-3*k_3-B && meter_25>=1 ], cost: 3*meter_25+3*meter_25*k_3+3*k_3

     63: f1 -> f1 : D'=D+meter_28, E'=meter*meter_28+meter_28+E, F'=D+meter_28, G'=meter*meter_28+meter_28+E, [ 2+B==2+2*D && 1+D+A>=3+2*E && 2*meter==-1+D+A-2*E && meter>=1 && 2*meter_28==-2*D+B && meter_28>=1 ], cost: 3*meter*meter_28+3*meter_28

     64: f1 -> f1 : D'=-meter_29+D, E'=meter_29+meter_29*meter+E, F'=-meter_29+D, G'=meter_29+meter_29*meter+E, [ 2+B==-2+2*D && -1+D+A>=3+2*E && 2*meter==-3+D+A-2*E && meter>=1 && 2*meter_29==-4+2*D-B && meter_29>=1 ], cost: 3*meter_29+3*meter_29*meter

     65: f1 -> f1 : D'=meter_30+D, E'=-meter_30-meter_30*meter_1+E, F'=meter_30+D, G'=-meter_30-meter_30*meter_1+E, [ 2+B==2+2*D && -2+2*E>=3+D+A && 2*meter_1==-4-D-A+2*E && meter_1>=1 && 2*meter_30==-2*D+B && meter_30>=1 ], cost: 3*meter_30+3*meter_30*meter_1

     66: f1 -> f1 : D'=D-meter_31, E'=-meter_1*meter_31-meter_31+E, F'=D-meter_31, G'=-meter_1*meter_31-meter_31+E, [ 2+B==-2+2*D && -2+2*E>=1+D+A && 2*meter_1==-2-D-A+2*E && meter_1>=1 && 2*meter_31==-4+2*D-B && meter_31>=1 ], cost: 3*meter_1*meter_31+3*meter_31

     67: f1 -> f1 : D'=meter_32+D, E'=meter_32+meter_32*meter_2+E, F'=meter_32+D, G'=meter_32+meter_32*meter_2+E, [ 3+B==2+2*D && 1+D+A>=3+2*E && 2*meter_2==-1+D+A-2*E && meter_2>=1 && 2*meter_32==1-2*D+B && meter_32>=1 ], cost: 3*meter_32+3*meter_32*meter_2

     68: f1 -> f1 : D'=-meter_33+D, E'=meter_33+meter_33*meter_2+E, F'=-meter_33+D, G'=meter_33+meter_33*meter_2+E, [ 3+B==-2+2*D && -1+D+A>=3+2*E && 2*meter_2==-3+D+A-2*E && meter_2>=1 && 2*meter_33==-5+2*D-B && meter_33>=1 ], cost: 3*meter_33+3*meter_33*meter_2

     69: f1 -> f1 : D'=meter_34+D, E'=-meter_34-meter_34*meter_3+E, F'=meter_34+D, G'=-meter_34-meter_34*meter_3+E, [ 3+B==2+2*D && -2+2*E>=3+D+A && 2*meter_3==-4-D-A+2*E && meter_3>=1 && 2*meter_34==1-2*D+B && meter_34>=1 ], cost: 3*meter_34+3*meter_34*meter_3

     70: f1 -> f1 : D'=D-meter_35, E'=-meter_3*meter_35-meter_35+E, F'=D-meter_35, G'=-meter_3*meter_35-meter_35+E, [ 3+B==-2+2*D && -2+2*E>=1+D+A && 2*meter_3==-2-D-A+2*E && meter_3>=1 && 2*meter_35==-5+2*D-B && meter_35>=1 ], cost: 3*meter_3*meter_35+3*meter_35



Chained accelerated rules (with incoming rules):

   Start location: f0

      0: f0 -> f1 : [ A>=0 && 3>=A && B>=0 && 3>=B && 3>=C && D>=0 && 3>=E && E>=0 ], cost: 1

     71: f0 -> f1 : D'=D+k, E'=k+E, F'=D+k, G'=k+E, [ A>=0 && 3>=A && B>=0 && 3>=B && 3>=C && D>=0 && 3>=E && E>=0 && 1+B>=2*D && D+A>=1+2*E && k>0 && 1+B>=-2+2*D+2*k && -1+D+A+k>=-1+2*k+2*E ], cost: 1+3*k

     72: f0 -> f1 : D'=k_1+D, E'=-k_1+E, F'=k_1+D, G'=-k_1+E, [ A>=0 && 3>=A && B>=0 && 3>=B && 3>=C && D>=0 && 3>=E && E>=0 && 1+B>=2*D && 2*E>=2+D+A && k_1>0 && 1+B>=-2+2*k_1+2*D && 2-2*k_1+2*E>=1+k_1+D+A ], cost: 1+3*k_1

     73: f0 -> f1 : D'=-k_2+D, E'=k_2+E, F'=-k_2+D, G'=k_2+E, [ A>=0 && 3>=A && B>=0 && 3>=B && 3>=C && D>=0 && 3>=E && E>=0 && 2*D>=4+B && D+A>=1+2*E && k_2>0 && 2-2*k_2+2*D>=4+B && 1-k_2+D+A>=-1+2*k_2+2*E ], cost: 1+3*k_2

     74: f0 -> f1 : D'=D-k_3, E'=-k_3+E, F'=D-k_3, G'=-k_3+E, [ A>=0 && 3>=A && B>=0 && 3>=B && 3>=C && D>=0 && 3>=E && E>=0 && 2*D>=4+B && 2*E>=2+D+A && k_3>0 && 2+2*D-2*k_3>=4+B && 2-2*k_3+2*E>=3+D+A-k_3 ], cost: 1+3*k_3

     75: f0 -> f1 : E'=meter+E, F'=D, G'=meter+E, [ A>=0 && 3>=A && B>=0 && 3>=B && 3>=C && D>=0 && 3>=E && E>=0 && 2+B==2*D && D+A>=1+2*E && 2*meter==D+A-2*E && meter>=1 ], cost: 1+3*meter

     76: f0 -> f1 : E'=-meter_1+E, F'=D, G'=-meter_1+E, [ A>=0 && 3>=A && B>=0 && 3>=B && 3>=C && D>=0 && 3>=E && E>=0 && 2+B==2*D && 2*E>=2+D+A && 2*meter_1==-1-D-A+2*E && meter_1>=1 ], cost: 1+3*meter_1

     77: f0 -> f1 : E'=E+meter_2, F'=D, G'=E+meter_2, [ A>=0 && 3>=A && B>=0 && 3>=B && 3>=C && D>=0 && 3>=E && E>=0 && 3+B==2*D && D+A>=1+2*E && 2*meter_2==D+A-2*E && meter_2>=1 ], cost: 1+3*meter_2

     78: f0 -> f1 : E'=-meter_3+E, F'=D, G'=-meter_3+E, [ A>=0 && 3>=A && B>=0 && 3>=B && 3>=C && D>=0 && 3>=E && E>=0 && 3+B==2*D && 2*E>=2+D+A && 2*meter_3==-1-D-A+2*E && meter_3>=1 ], cost: 1+3*meter_3

     79: f0 -> f1 : D'=D-meter_25-meter_25*(-4+2*D-4*meter_25-B), E'=-meter_25*(-4+2*D-4*meter_25-B)+E, F'=D-meter_25-meter_25*(-4+2*D-4*meter_25-B), G'=-meter_25*(-4+2*D-4*meter_25-B)+E, [ A>=0 && 3>=A && B>=0 && 3>=B && 3>=C && D>=0 && 3>=E && E>=0 && 1+D+A==2*E && -2+2*D>=4+B && -4+2*D-4*meter_25-B>0 && 8-2*D+8*meter_25+2*B>=4+B && 10-4*D+8*meter_25+2*E+2*B>=6-D+4*meter_25+A+B && meter_25>=1 ], cost: 1+3*meter_25+3*meter_25*(-4+2*D-4*meter_25-B)



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

   Start location: f0

     71: f0 -> f1 : D'=D+k, E'=k+E, F'=D+k, G'=k+E, [ A>=0 && 3>=A && B>=0 && 3>=B && 3>=C && D>=0 && 3>=E && E>=0 && 1+B>=2*D && D+A>=1+2*E && k>0 && 1+B>=-2+2*D+2*k && -1+D+A+k>=-1+2*k+2*E ], cost: 1+3*k

     72: f0 -> f1 : D'=k_1+D, E'=-k_1+E, F'=k_1+D, G'=-k_1+E, [ A>=0 && 3>=A && B>=0 && 3>=B && 3>=C && D>=0 && 3>=E && E>=0 && 1+B>=2*D && 2*E>=2+D+A && k_1>0 && 1+B>=-2+2*k_1+2*D && 2-2*k_1+2*E>=1+k_1+D+A ], cost: 1+3*k_1

     73: f0 -> f1 : D'=-k_2+D, E'=k_2+E, F'=-k_2+D, G'=k_2+E, [ A>=0 && 3>=A && B>=0 && 3>=B && 3>=C && D>=0 && 3>=E && E>=0 && 2*D>=4+B && D+A>=1+2*E && k_2>0 && 2-2*k_2+2*D>=4+B && 1-k_2+D+A>=-1+2*k_2+2*E ], cost: 1+3*k_2

     74: f0 -> f1 : D'=D-k_3, E'=-k_3+E, F'=D-k_3, G'=-k_3+E, [ A>=0 && 3>=A && B>=0 && 3>=B && 3>=C && D>=0 && 3>=E && E>=0 && 2*D>=4+B && 2*E>=2+D+A && k_3>0 && 2+2*D-2*k_3>=4+B && 2-2*k_3+2*E>=3+D+A-k_3 ], cost: 1+3*k_3

     75: f0 -> f1 : E'=meter+E, F'=D, G'=meter+E, [ A>=0 && 3>=A && B>=0 && 3>=B && 3>=C && D>=0 && 3>=E && E>=0 && 2+B==2*D && D+A>=1+2*E && 2*meter==D+A-2*E && meter>=1 ], cost: 1+3*meter

     76: f0 -> f1 : E'=-meter_1+E, F'=D, G'=-meter_1+E, [ A>=0 && 3>=A && B>=0 && 3>=B && 3>=C && D>=0 && 3>=E && E>=0 && 2+B==2*D && 2*E>=2+D+A && 2*meter_1==-1-D-A+2*E && meter_1>=1 ], cost: 1+3*meter_1

     77: f0 -> f1 : E'=E+meter_2, F'=D, G'=E+meter_2, [ A>=0 && 3>=A && B>=0 && 3>=B && 3>=C && D>=0 && 3>=E && E>=0 && 3+B==2*D && D+A>=1+2*E && 2*meter_2==D+A-2*E && meter_2>=1 ], cost: 1+3*meter_2

     78: f0 -> f1 : E'=-meter_3+E, F'=D, G'=-meter_3+E, [ A>=0 && 3>=A && B>=0 && 3>=B && 3>=C && D>=0 && 3>=E && E>=0 && 3+B==2*D && 2*E>=2+D+A && 2*meter_3==-1-D-A+2*E && meter_3>=1 ], cost: 1+3*meter_3

     79: f0 -> f1 : D'=D-meter_25-meter_25*(-4+2*D-4*meter_25-B), E'=-meter_25*(-4+2*D-4*meter_25-B)+E, F'=D-meter_25-meter_25*(-4+2*D-4*meter_25-B), G'=-meter_25*(-4+2*D-4*meter_25-B)+E, [ A>=0 && 3>=A && B>=0 && 3>=B && 3>=C && D>=0 && 3>=E && E>=0 && 1+D+A==2*E && -2+2*D>=4+B && -4+2*D-4*meter_25-B>0 && 8-2*D+8*meter_25+2*B>=4+B && 10-4*D+8*meter_25+2*E+2*B>=6-D+4*meter_25+A+B && meter_25>=1 ], cost: 1+3*meter_25+3*meter_25*(-4+2*D-4*meter_25-B)



### Computing asymptotic complexity ###



Fully simplified ITS problem

   Start location: f0

     71: f0 -> f1 : D'=D+k, E'=k+E, F'=D+k, G'=k+E, [ A>=0 && 3>=A && B>=0 && 3>=B && 3>=C && D>=0 && 3>=E && E>=0 && 1+B>=2*D && D+A>=1+2*E && k>0 && 1+B>=-2+2*D+2*k && -1+D+A+k>=-1+2*k+2*E ], cost: 1+3*k

     72: f0 -> f1 : D'=k_1+D, E'=-k_1+E, F'=k_1+D, G'=-k_1+E, [ A>=0 && 3>=A && B>=0 && 3>=B && 3>=C && D>=0 && 3>=E && E>=0 && 1+B>=2*D && 2*E>=2+D+A && k_1>0 && 1+B>=-2+2*k_1+2*D && 2-2*k_1+2*E>=1+k_1+D+A ], cost: 1+3*k_1

     73: f0 -> f1 : D'=-k_2+D, E'=k_2+E, F'=-k_2+D, G'=k_2+E, [ A>=0 && 3>=A && B>=0 && 3>=B && 3>=C && D>=0 && 3>=E && E>=0 && 2*D>=4+B && D+A>=1+2*E && k_2>0 && 2-2*k_2+2*D>=4+B && 1-k_2+D+A>=-1+2*k_2+2*E ], cost: 1+3*k_2

     74: f0 -> f1 : D'=D-k_3, E'=-k_3+E, F'=D-k_3, G'=-k_3+E, [ A>=0 && 3>=A && B>=0 && 3>=B && 3>=C && D>=0 && 3>=E && E>=0 && 2*D>=4+B && 2*E>=2+D+A && k_3>0 && 2+2*D-2*k_3>=4+B && 2-2*k_3+2*E>=3+D+A-k_3 ], cost: 1+3*k_3

     75: f0 -> f1 : E'=meter+E, F'=D, G'=meter+E, [ A>=0 && 3>=A && B>=0 && 3>=B && 3>=C && D>=0 && 3>=E && E>=0 && 2+B==2*D && D+A>=1+2*E && 2*meter==D+A-2*E && meter>=1 ], cost: 1+3*meter

     76: f0 -> f1 : E'=-meter_1+E, F'=D, G'=-meter_1+E, [ A>=0 && 3>=A && B>=0 && 3>=B && 3>=C && D>=0 && 3>=E && E>=0 && 2+B==2*D && 2*E>=2+D+A && 2*meter_1==-1-D-A+2*E && meter_1>=1 ], cost: 1+3*meter_1

     77: f0 -> f1 : E'=E+meter_2, F'=D, G'=E+meter_2, [ A>=0 && 3>=A && B>=0 && 3>=B && 3>=C && D>=0 && 3>=E && E>=0 && 3+B==2*D && D+A>=1+2*E && 2*meter_2==D+A-2*E && meter_2>=1 ], cost: 1+3*meter_2

     78: f0 -> f1 : E'=-meter_3+E, F'=D, G'=-meter_3+E, [ A>=0 && 3>=A && B>=0 && 3>=B && 3>=C && D>=0 && 3>=E && E>=0 && 3+B==2*D && 2*E>=2+D+A && 2*meter_3==-1-D-A+2*E && meter_3>=1 ], cost: 1+3*meter_3

     79: f0 -> f1 : D'=D-meter_25-meter_25*(-4+2*D-4*meter_25-B), E'=-meter_25*(-4+2*D-4*meter_25-B)+E, F'=D-meter_25-meter_25*(-4+2*D-4*meter_25-B), G'=-meter_25*(-4+2*D-4*meter_25-B)+E, [ A>=0 && 3>=A && B>=0 && 3>=B && 3>=C && D>=0 && 3>=E && E>=0 && 1+D+A==2*E && -2+2*D>=4+B && -4+2*D-4*meter_25-B>0 && 8-2*D+8*meter_25+2*B>=4+B && 10-4*D+8*meter_25+2*E+2*B>=6-D+4*meter_25+A+B && meter_25>=1 ], cost: 1+3*meter_25+3*meter_25*(-4+2*D-4*meter_25-B)



Computing asymptotic complexity for rule 71

   Simplified the guard:

     71: f0 -> f1 : D'=D+k, E'=k+E, F'=D+k, G'=k+E, [ A>=0 && 3>=A && B>=0 && 3>=B && 3>=C && D>=0 && 3>=E && E>=0 && k>0 && 1+B>=-2+2*D+2*k && -1+D+A+k>=-1+2*k+2*E ], cost: 1+3*k

   Could not solve the limit problem.

   Resulting cost 0 has complexity: Unknown



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

   Complexity:  Unknown

   Cpx degree:  ?

   Solved cost: 0

   Rule cost:   0

   Rule guard:  []



WORST_CASE(Omega(0),?)


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

(2)
BOUNDS(1, INF)