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


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

(0)
Obligation:
Complexity Int TRS consisting of the following rules:
f0(A, B, C, D, E, F, G, H, I, J, K, L, M) -> Com_1(f1(A, B, C, D, E, F, G, H, I, J, K, L, M)) :|: TRUE
f1(A, B, C, D, E, F, G, H, I, J, K, L, M) -> Com_1(f2(0, O, P, 3, N, 0, O, P, 3, N, 2, L, M)) :|: 7 >= N && N >= 1
f4(A, B, C, D, E, F, G, H, I, J, K, L, M) -> Com_1(f2(0, O, P, N, Q, 0, O, P, N, Q, 2, L, M)) :|: L >= 1 && L >= P + 1 && M >= 1 && M >= O + 1 && 7 >= Q && 7 >= N && Q >= 1 && N >= 1
f1(A, B, C, D, E, F, G, H, I, J, K, L, M) -> Com_1(f1(O, P, N, 2, Q, O, P, N, 2, Q, 1, L, M)) :|: R >= 1 && 7 >= R && S >= 1 && 7 >= S && Q >= 1 && 7 >= Q && 1 >= O && O >= 0
f2(A, B, C, D, E, F, G, H, I, J, K, L, M) -> Com_1(f1(O, P, N, 2, Q, O, P, N, 2, Q, 1, L, M)) :|: R >= 1 && 7 >= R && S >= 1 && 7 >= S && Q >= 1 && 7 >= Q && 1 >= O && O >= 0
f4(A, B, C, D, E, F, G, H, I, J, K, L, M) -> Com_1(f1(O, P, N, 2, Q, O, P, N, 2, Q, 1, L, M)) :|: R >= L && S >= M && T >= 1 && 7 >= T && U >= 1 && 7 >= U && Q >= 1 && 7 >= Q && 1 >= O && O >= 0
f4(A, B, C, D, E, F, G, H, I, J, K, L, M) -> Com_1(f1(O, P, N, 2, Q, O, P, N, 2, Q, 1, L, M)) :|: R >= 1 && 7 >= R && S >= 1 && 7 >= S && Q >= 1 && 7 >= Q && 1 >= O && O >= 0
f2(A, B, C, D, E, F, G, H, I, J, K, L, M) -> Com_1(f4(O, P, N, Q, 2, O, P, N, Q, 2, 4, L, M)) :|: R >= 1 && 7 >= R && S >= 1 && 7 >= S && T >= 1 && 7 >= T && U >= 1 && 7 >= U && Q >= 1 && 7 >= Q && 1 >= O && O >= 0
f2(A, B, C, D, E, F, G, H, I, J, K, L, M) -> Com_1(f4(O, P, N, Q, 7, O, P, N, Q, 7, 4, L, M)) :|: R >= 1 && 7 >= R && S >= 1 && 7 >= S && T >= 1 && 7 >= T && U >= 1 && 7 >= U && Q >= 1 && 7 >= Q && 1 >= O && O >= 0

The start-symbols are:[f0_13]


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

(1) Loat Proof (FINISHED)


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



Initial linear ITS problem

   Start location: f0

      0: f0 -> f1 : [], cost: 1

      1: f1 -> f2 : A'=0, B'=free_2, C'=free, D'=3, E'=free_1, F'=0, G'=free_2, H'=free, Q'=3, J'=free_1, K'=2, [ 7>=free_1 && free_1>=1 ], cost: 1

      3: f1 -> f1 : A'=free_12, B'=free_8, C'=free_10, D'=2, E'=free_9, F'=free_12, G'=free_8, H'=free_10, Q'=2, J'=free_9, K'=1, [ free_11>=1 && 7>=free_11 && free_7>=1 && 7>=free_7 && free_9>=1 && 7>=free_9 && 1>=free_12 && free_12>=0 ], cost: 1

      2: f4 -> f2 : A'=0, B'=free_6, C'=free_3, D'=free_5, E'=free_4, F'=0, G'=free_6, H'=free_3, Q'=free_5, J'=free_4, K'=2, [ L>=1 && L>=1+free_3 && M>=1 && M>=1+free_6 && 7>=free_4 && 7>=free_5 && free_4>=1 && free_5>=1 ], cost: 1

      5: f4 -> f1 : A'=free_26, B'=free_20, C'=free_23, D'=2, E'=free_22, F'=free_26, G'=free_20, H'=free_23, Q'=2, J'=free_22, K'=1, [ free_25>=L && free_19>=M && free_21>=1 && 7>=free_21 && free_24>=1 && 7>=free_24 && free_22>=1 && 7>=free_22 && 1>=free_26 && free_26>=0 ], cost: 1

      6: f4 -> f1 : A'=free_32, B'=free_28, C'=free_30, D'=2, E'=free_29, F'=free_32, G'=free_28, H'=free_30, Q'=2, J'=free_29, K'=1, [ free_31>=1 && 7>=free_31 && free_27>=1 && 7>=free_27 && free_29>=1 && 7>=free_29 && 1>=free_32 && free_32>=0 ], cost: 1

      4: f2 -> f1 : A'=free_18, B'=free_14, C'=free_16, D'=2, E'=free_15, F'=free_18, G'=free_14, H'=free_16, Q'=2, J'=free_15, K'=1, [ free_17>=1 && 7>=free_17 && free_13>=1 && 7>=free_13 && free_15>=1 && 7>=free_15 && 1>=free_18 && free_18>=0 ], cost: 1

      7: f2 -> f4 : A'=free_40, B'=free_34, C'=free_37, D'=free_36, E'=2, F'=free_40, G'=free_34, H'=free_37, Q'=free_36, J'=2, K'=4, [ free_39>=1 && 7>=free_39 && free_33>=1 && 7>=free_33 && free_35>=1 && 7>=free_35 && free_38>=1 && 7>=free_38 && free_36>=1 && 7>=free_36 && 1>=free_40 && free_40>=0 ], cost: 1

      8: f2 -> f4 : A'=free_48, B'=free_42, C'=free_45, D'=free_44, E'=7, F'=free_48, G'=free_42, H'=free_45, Q'=free_44, J'=7, K'=4, [ free_47>=1 && 7>=free_47 && free_41>=1 && 7>=free_41 && free_43>=1 && 7>=free_43 && free_46>=1 && 7>=free_46 && free_44>=1 && 7>=free_44 && 1>=free_48 && free_48>=0 ], cost: 1



Checking for constant complexity:

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

      0: f0 -> f1 : [], cost: 1



Simplified all rules, resulting in:

   Start location: f0

      0: f0 -> f1 : [], cost: 1

      1: f1 -> f2 : A'=0, B'=free_2, C'=free, D'=3, E'=free_1, F'=0, G'=free_2, H'=free, Q'=3, J'=free_1, K'=2, [ 7>=free_1 && free_1>=1 ], cost: 1

      3: f1 -> f1 : A'=free_12, B'=free_8, C'=free_10, D'=2, E'=free_9, F'=free_12, G'=free_8, H'=free_10, Q'=2, J'=free_9, K'=1, [ free_9>=1 && 7>=free_9 && 1>=free_12 && free_12>=0 ], cost: 1

      2: f4 -> f2 : A'=0, B'=free_6, C'=free_3, D'=free_5, E'=free_4, F'=0, G'=free_6, H'=free_3, Q'=free_5, J'=free_4, K'=2, [ L>=1 && L>=1+free_3 && M>=1 && M>=1+free_6 && 7>=free_4 && 7>=free_5 && free_4>=1 && free_5>=1 ], cost: 1

      5: f4 -> f1 : A'=free_26, B'=free_20, C'=free_23, D'=2, E'=free_22, F'=free_26, G'=free_20, H'=free_23, Q'=2, J'=free_22, K'=1, [ free_22>=1 && 7>=free_22 && 1>=free_26 && free_26>=0 ], cost: 1

      6: f4 -> f1 : A'=free_32, B'=free_28, C'=free_30, D'=2, E'=free_29, F'=free_32, G'=free_28, H'=free_30, Q'=2, J'=free_29, K'=1, [ free_29>=1 && 7>=free_29 && 1>=free_32 && free_32>=0 ], cost: 1

      4: f2 -> f1 : A'=free_18, B'=free_14, C'=free_16, D'=2, E'=free_15, F'=free_18, G'=free_14, H'=free_16, Q'=2, J'=free_15, K'=1, [ free_15>=1 && 7>=free_15 && 1>=free_18 && free_18>=0 ], cost: 1

      7: f2 -> f4 : A'=free_40, B'=free_34, C'=free_37, D'=free_36, E'=2, F'=free_40, G'=free_34, H'=free_37, Q'=free_36, J'=2, K'=4, [ free_36>=1 && 7>=free_36 && 1>=free_40 && free_40>=0 ], cost: 1

      8: f2 -> f4 : A'=free_48, B'=free_42, C'=free_45, D'=free_44, E'=7, F'=free_48, G'=free_42, H'=free_45, Q'=free_44, J'=7, K'=4, [ free_44>=1 && 7>=free_44 && 1>=free_48 && free_48>=0 ], cost: 1



### Simplification by acceleration and chaining ###



Accelerating simple loops of location 1.

   Accelerating the following rules:

      3: f1 -> f1 : A'=free_12, B'=free_8, C'=free_10, D'=2, E'=free_9, F'=free_12, G'=free_8, H'=free_10, Q'=2, J'=free_9, K'=1, [ free_9>=1 && 7>=free_9 && 1>=free_12 && free_12>=0 ], cost: 1



   Accelerated rule 3 with NONTERM, yielding the new rule 9.

   Removing the simple loops: 3.



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

   Start location: f0

      0: f0 -> f1 : [], cost: 1

      1: f1 -> f2 : A'=0, B'=free_2, C'=free, D'=3, E'=free_1, F'=0, G'=free_2, H'=free, Q'=3, J'=free_1, K'=2, [ 7>=free_1 && free_1>=1 ], cost: 1

      9: f1 -> [4] : [ free_9>=1 && 7>=free_9 && 1>=free_12 && free_12>=0 ], cost: NONTERM

      2: f4 -> f2 : A'=0, B'=free_6, C'=free_3, D'=free_5, E'=free_4, F'=0, G'=free_6, H'=free_3, Q'=free_5, J'=free_4, K'=2, [ L>=1 && L>=1+free_3 && M>=1 && M>=1+free_6 && 7>=free_4 && 7>=free_5 && free_4>=1 && free_5>=1 ], cost: 1

      5: f4 -> f1 : A'=free_26, B'=free_20, C'=free_23, D'=2, E'=free_22, F'=free_26, G'=free_20, H'=free_23, Q'=2, J'=free_22, K'=1, [ free_22>=1 && 7>=free_22 && 1>=free_26 && free_26>=0 ], cost: 1

      6: f4 -> f1 : A'=free_32, B'=free_28, C'=free_30, D'=2, E'=free_29, F'=free_32, G'=free_28, H'=free_30, Q'=2, J'=free_29, K'=1, [ free_29>=1 && 7>=free_29 && 1>=free_32 && free_32>=0 ], cost: 1

      4: f2 -> f1 : A'=free_18, B'=free_14, C'=free_16, D'=2, E'=free_15, F'=free_18, G'=free_14, H'=free_16, Q'=2, J'=free_15, K'=1, [ free_15>=1 && 7>=free_15 && 1>=free_18 && free_18>=0 ], cost: 1

      7: f2 -> f4 : A'=free_40, B'=free_34, C'=free_37, D'=free_36, E'=2, F'=free_40, G'=free_34, H'=free_37, Q'=free_36, J'=2, K'=4, [ free_36>=1 && 7>=free_36 && 1>=free_40 && free_40>=0 ], cost: 1

      8: f2 -> f4 : A'=free_48, B'=free_42, C'=free_45, D'=free_44, E'=7, F'=free_48, G'=free_42, H'=free_45, Q'=free_44, J'=7, K'=4, [ free_44>=1 && 7>=free_44 && 1>=free_48 && free_48>=0 ], cost: 1



Chained accelerated rules (with incoming rules):

   Start location: f0

      0: f0 -> f1 : [], cost: 1

     10: f0 -> [4] : [], cost: NONTERM

      1: f1 -> f2 : A'=0, B'=free_2, C'=free, D'=3, E'=free_1, F'=0, G'=free_2, H'=free, Q'=3, J'=free_1, K'=2, [ 7>=free_1 && free_1>=1 ], cost: 1

      2: f4 -> f2 : A'=0, B'=free_6, C'=free_3, D'=free_5, E'=free_4, F'=0, G'=free_6, H'=free_3, Q'=free_5, J'=free_4, K'=2, [ L>=1 && L>=1+free_3 && M>=1 && M>=1+free_6 && 7>=free_4 && 7>=free_5 && free_4>=1 && free_5>=1 ], cost: 1

      5: f4 -> f1 : A'=free_26, B'=free_20, C'=free_23, D'=2, E'=free_22, F'=free_26, G'=free_20, H'=free_23, Q'=2, J'=free_22, K'=1, [ free_22>=1 && 7>=free_22 && 1>=free_26 && free_26>=0 ], cost: 1

      6: f4 -> f1 : A'=free_32, B'=free_28, C'=free_30, D'=2, E'=free_29, F'=free_32, G'=free_28, H'=free_30, Q'=2, J'=free_29, K'=1, [ free_29>=1 && 7>=free_29 && 1>=free_32 && free_32>=0 ], cost: 1

     12: f4 -> [4] : A'=free_26, B'=free_20, C'=free_23, D'=2, E'=free_22, F'=free_26, G'=free_20, H'=free_23, Q'=2, J'=free_22, K'=1, [ free_22>=1 && 7>=free_22 && 1>=free_26 && free_26>=0 ], cost: NONTERM

     13: f4 -> [4] : A'=free_32, B'=free_28, C'=free_30, D'=2, E'=free_29, F'=free_32, G'=free_28, H'=free_30, Q'=2, J'=free_29, K'=1, [ free_29>=1 && 7>=free_29 && 1>=free_32 && free_32>=0 ], cost: NONTERM

      4: f2 -> f1 : A'=free_18, B'=free_14, C'=free_16, D'=2, E'=free_15, F'=free_18, G'=free_14, H'=free_16, Q'=2, J'=free_15, K'=1, [ free_15>=1 && 7>=free_15 && 1>=free_18 && free_18>=0 ], cost: 1

      7: f2 -> f4 : A'=free_40, B'=free_34, C'=free_37, D'=free_36, E'=2, F'=free_40, G'=free_34, H'=free_37, Q'=free_36, J'=2, K'=4, [ free_36>=1 && 7>=free_36 && 1>=free_40 && free_40>=0 ], cost: 1

      8: f2 -> f4 : A'=free_48, B'=free_42, C'=free_45, D'=free_44, E'=7, F'=free_48, G'=free_42, H'=free_45, Q'=free_44, J'=7, K'=4, [ free_44>=1 && 7>=free_44 && 1>=free_48 && free_48>=0 ], cost: 1

     11: f2 -> [4] : A'=free_18, B'=free_14, C'=free_16, D'=2, E'=free_15, F'=free_18, G'=free_14, H'=free_16, Q'=2, J'=free_15, K'=1, [ free_15>=1 && 7>=free_15 && 1>=free_18 && free_18>=0 ], cost: NONTERM



Eliminated locations (on tree-shaped paths):

   Start location: f0

      0: f0 -> f1 : [], cost: 1

     10: f0 -> [4] : [], cost: NONTERM

      1: f1 -> f2 : A'=0, B'=free_2, C'=free, D'=3, E'=free_1, F'=0, G'=free_2, H'=free, Q'=3, J'=free_1, K'=2, [ 7>=free_1 && free_1>=1 ], cost: 1

      4: f2 -> f1 : A'=free_18, B'=free_14, C'=free_16, D'=2, E'=free_15, F'=free_18, G'=free_14, H'=free_16, Q'=2, J'=free_15, K'=1, [ free_15>=1 && 7>=free_15 && 1>=free_18 && free_18>=0 ], cost: 1

     11: f2 -> [4] : A'=free_18, B'=free_14, C'=free_16, D'=2, E'=free_15, F'=free_18, G'=free_14, H'=free_16, Q'=2, J'=free_15, K'=1, [ free_15>=1 && 7>=free_15 && 1>=free_18 && free_18>=0 ], cost: NONTERM

     14: f2 -> f2 : A'=0, B'=free_6, C'=free_3, D'=free_5, E'=free_4, F'=0, G'=free_6, H'=free_3, Q'=free_5, J'=free_4, K'=2, [ free_36>=1 && 7>=free_36 && 1>=free_40 && free_40>=0 && L>=1 && L>=1+free_3 && M>=1 && M>=1+free_6 && 7>=free_4 && 7>=free_5 && free_4>=1 && free_5>=1 ], cost: 2

     15: f2 -> f1 : A'=free_26, B'=free_20, C'=free_23, D'=2, E'=free_22, F'=free_26, G'=free_20, H'=free_23, Q'=2, J'=free_22, K'=1, [ free_36>=1 && 7>=free_36 && 1>=free_40 && free_40>=0 && free_22>=1 && 7>=free_22 && 1>=free_26 && free_26>=0 ], cost: 2

     16: f2 -> f1 : A'=free_32, B'=free_28, C'=free_30, D'=2, E'=free_29, F'=free_32, G'=free_28, H'=free_30, Q'=2, J'=free_29, K'=1, [ free_36>=1 && 7>=free_36 && 1>=free_40 && free_40>=0 && free_29>=1 && 7>=free_29 && 1>=free_32 && free_32>=0 ], cost: 2

     17: f2 -> [4] : A'=free_26, B'=free_20, C'=free_23, D'=2, E'=free_22, F'=free_26, G'=free_20, H'=free_23, Q'=2, J'=free_22, K'=1, [ free_36>=1 && 7>=free_36 && 1>=free_40 && free_40>=0 && free_22>=1 && 7>=free_22 && 1>=free_26 && free_26>=0 ], cost: NONTERM

     18: f2 -> [4] : A'=free_32, B'=free_28, C'=free_30, D'=2, E'=free_29, F'=free_32, G'=free_28, H'=free_30, Q'=2, J'=free_29, K'=1, [ free_36>=1 && 7>=free_36 && 1>=free_40 && free_40>=0 && free_29>=1 && 7>=free_29 && 1>=free_32 && free_32>=0 ], cost: NONTERM

     19: f2 -> f2 : A'=0, B'=free_6, C'=free_3, D'=free_5, E'=free_4, F'=0, G'=free_6, H'=free_3, Q'=free_5, J'=free_4, K'=2, [ free_44>=1 && 7>=free_44 && 1>=free_48 && free_48>=0 && L>=1 && L>=1+free_3 && M>=1 && M>=1+free_6 && 7>=free_4 && 7>=free_5 && free_4>=1 && free_5>=1 ], cost: 2

     20: f2 -> f1 : A'=free_26, B'=free_20, C'=free_23, D'=2, E'=free_22, F'=free_26, G'=free_20, H'=free_23, Q'=2, J'=free_22, K'=1, [ free_44>=1 && 7>=free_44 && 1>=free_48 && free_48>=0 && free_22>=1 && 7>=free_22 && 1>=free_26 && free_26>=0 ], cost: 2

     21: f2 -> f1 : A'=free_32, B'=free_28, C'=free_30, D'=2, E'=free_29, F'=free_32, G'=free_28, H'=free_30, Q'=2, J'=free_29, K'=1, [ free_44>=1 && 7>=free_44 && 1>=free_48 && free_48>=0 && free_29>=1 && 7>=free_29 && 1>=free_32 && free_32>=0 ], cost: 2

     22: f2 -> [4] : A'=free_26, B'=free_20, C'=free_23, D'=2, E'=free_22, F'=free_26, G'=free_20, H'=free_23, Q'=2, J'=free_22, K'=1, [ free_44>=1 && 7>=free_44 && 1>=free_48 && free_48>=0 && free_22>=1 && 7>=free_22 && 1>=free_26 && free_26>=0 ], cost: NONTERM

     23: f2 -> [4] : A'=free_32, B'=free_28, C'=free_30, D'=2, E'=free_29, F'=free_32, G'=free_28, H'=free_30, Q'=2, J'=free_29, K'=1, [ free_44>=1 && 7>=free_44 && 1>=free_48 && free_48>=0 && free_29>=1 && 7>=free_29 && 1>=free_32 && free_32>=0 ], cost: NONTERM



Accelerating simple loops of location 3.

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

   Accelerating the following rules:

     19: f2 -> f2 : A'=0, B'=free_6, C'=free_3, D'=free_5, E'=free_4, F'=0, G'=free_6, H'=free_3, Q'=free_5, J'=free_4, K'=2, [ L>=1 && L>=1+free_3 && M>=1 && M>=1+free_6 && 7>=free_4 && 7>=free_5 && free_4>=1 && free_5>=1 ], cost: 2



   Accelerated rule 19 with NONTERM, yielding the new rule 24.

   Removing the simple loops: 19.



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

   Start location: f0

      0: f0 -> f1 : [], cost: 1

     10: f0 -> [4] : [], cost: NONTERM

      1: f1 -> f2 : A'=0, B'=free_2, C'=free, D'=3, E'=free_1, F'=0, G'=free_2, H'=free, Q'=3, J'=free_1, K'=2, [ 7>=free_1 && free_1>=1 ], cost: 1

      4: f2 -> f1 : A'=free_18, B'=free_14, C'=free_16, D'=2, E'=free_15, F'=free_18, G'=free_14, H'=free_16, Q'=2, J'=free_15, K'=1, [ free_15>=1 && 7>=free_15 && 1>=free_18 && free_18>=0 ], cost: 1

     11: f2 -> [4] : A'=free_18, B'=free_14, C'=free_16, D'=2, E'=free_15, F'=free_18, G'=free_14, H'=free_16, Q'=2, J'=free_15, K'=1, [ free_15>=1 && 7>=free_15 && 1>=free_18 && free_18>=0 ], cost: NONTERM

     15: f2 -> f1 : A'=free_26, B'=free_20, C'=free_23, D'=2, E'=free_22, F'=free_26, G'=free_20, H'=free_23, Q'=2, J'=free_22, K'=1, [ free_36>=1 && 7>=free_36 && 1>=free_40 && free_40>=0 && free_22>=1 && 7>=free_22 && 1>=free_26 && free_26>=0 ], cost: 2

     16: f2 -> f1 : A'=free_32, B'=free_28, C'=free_30, D'=2, E'=free_29, F'=free_32, G'=free_28, H'=free_30, Q'=2, J'=free_29, K'=1, [ free_36>=1 && 7>=free_36 && 1>=free_40 && free_40>=0 && free_29>=1 && 7>=free_29 && 1>=free_32 && free_32>=0 ], cost: 2

     17: f2 -> [4] : A'=free_26, B'=free_20, C'=free_23, D'=2, E'=free_22, F'=free_26, G'=free_20, H'=free_23, Q'=2, J'=free_22, K'=1, [ free_36>=1 && 7>=free_36 && 1>=free_40 && free_40>=0 && free_22>=1 && 7>=free_22 && 1>=free_26 && free_26>=0 ], cost: NONTERM

     18: f2 -> [4] : A'=free_32, B'=free_28, C'=free_30, D'=2, E'=free_29, F'=free_32, G'=free_28, H'=free_30, Q'=2, J'=free_29, K'=1, [ free_36>=1 && 7>=free_36 && 1>=free_40 && free_40>=0 && free_29>=1 && 7>=free_29 && 1>=free_32 && free_32>=0 ], cost: NONTERM

     20: f2 -> f1 : A'=free_26, B'=free_20, C'=free_23, D'=2, E'=free_22, F'=free_26, G'=free_20, H'=free_23, Q'=2, J'=free_22, K'=1, [ free_44>=1 && 7>=free_44 && 1>=free_48 && free_48>=0 && free_22>=1 && 7>=free_22 && 1>=free_26 && free_26>=0 ], cost: 2

     21: f2 -> f1 : A'=free_32, B'=free_28, C'=free_30, D'=2, E'=free_29, F'=free_32, G'=free_28, H'=free_30, Q'=2, J'=free_29, K'=1, [ free_44>=1 && 7>=free_44 && 1>=free_48 && free_48>=0 && free_29>=1 && 7>=free_29 && 1>=free_32 && free_32>=0 ], cost: 2

     22: f2 -> [4] : A'=free_26, B'=free_20, C'=free_23, D'=2, E'=free_22, F'=free_26, G'=free_20, H'=free_23, Q'=2, J'=free_22, K'=1, [ free_44>=1 && 7>=free_44 && 1>=free_48 && free_48>=0 && free_22>=1 && 7>=free_22 && 1>=free_26 && free_26>=0 ], cost: NONTERM

     23: f2 -> [4] : A'=free_32, B'=free_28, C'=free_30, D'=2, E'=free_29, F'=free_32, G'=free_28, H'=free_30, Q'=2, J'=free_29, K'=1, [ free_44>=1 && 7>=free_44 && 1>=free_48 && free_48>=0 && free_29>=1 && 7>=free_29 && 1>=free_32 && free_32>=0 ], cost: NONTERM

     24: f2 -> [5] : [ L>=1 && L>=1+free_3 && M>=1 && M>=1+free_6 && 7>=free_4 && 7>=free_5 && free_4>=1 && free_5>=1 ], cost: NONTERM



Chained accelerated rules (with incoming rules):

   Start location: f0

      0: f0 -> f1 : [], cost: 1

     10: f0 -> [4] : [], cost: NONTERM

      1: f1 -> f2 : A'=0, B'=free_2, C'=free, D'=3, E'=free_1, F'=0, G'=free_2, H'=free, Q'=3, J'=free_1, K'=2, [ 7>=free_1 && free_1>=1 ], cost: 1

     25: f1 -> [5] : A'=0, B'=free_2, C'=free, D'=3, E'=free_1, F'=0, G'=free_2, H'=free, Q'=3, J'=free_1, K'=2, [ 7>=free_1 && free_1>=1 && L>=1 && M>=1 ], cost: NONTERM

      4: f2 -> f1 : A'=free_18, B'=free_14, C'=free_16, D'=2, E'=free_15, F'=free_18, G'=free_14, H'=free_16, Q'=2, J'=free_15, K'=1, [ free_15>=1 && 7>=free_15 && 1>=free_18 && free_18>=0 ], cost: 1

     11: f2 -> [4] : A'=free_18, B'=free_14, C'=free_16, D'=2, E'=free_15, F'=free_18, G'=free_14, H'=free_16, Q'=2, J'=free_15, K'=1, [ free_15>=1 && 7>=free_15 && 1>=free_18 && free_18>=0 ], cost: NONTERM

     15: f2 -> f1 : A'=free_26, B'=free_20, C'=free_23, D'=2, E'=free_22, F'=free_26, G'=free_20, H'=free_23, Q'=2, J'=free_22, K'=1, [ free_36>=1 && 7>=free_36 && 1>=free_40 && free_40>=0 && free_22>=1 && 7>=free_22 && 1>=free_26 && free_26>=0 ], cost: 2

     16: f2 -> f1 : A'=free_32, B'=free_28, C'=free_30, D'=2, E'=free_29, F'=free_32, G'=free_28, H'=free_30, Q'=2, J'=free_29, K'=1, [ free_36>=1 && 7>=free_36 && 1>=free_40 && free_40>=0 && free_29>=1 && 7>=free_29 && 1>=free_32 && free_32>=0 ], cost: 2

     17: f2 -> [4] : A'=free_26, B'=free_20, C'=free_23, D'=2, E'=free_22, F'=free_26, G'=free_20, H'=free_23, Q'=2, J'=free_22, K'=1, [ free_36>=1 && 7>=free_36 && 1>=free_40 && free_40>=0 && free_22>=1 && 7>=free_22 && 1>=free_26 && free_26>=0 ], cost: NONTERM

     18: f2 -> [4] : A'=free_32, B'=free_28, C'=free_30, D'=2, E'=free_29, F'=free_32, G'=free_28, H'=free_30, Q'=2, J'=free_29, K'=1, [ free_36>=1 && 7>=free_36 && 1>=free_40 && free_40>=0 && free_29>=1 && 7>=free_29 && 1>=free_32 && free_32>=0 ], cost: NONTERM

     20: f2 -> f1 : A'=free_26, B'=free_20, C'=free_23, D'=2, E'=free_22, F'=free_26, G'=free_20, H'=free_23, Q'=2, J'=free_22, K'=1, [ free_44>=1 && 7>=free_44 && 1>=free_48 && free_48>=0 && free_22>=1 && 7>=free_22 && 1>=free_26 && free_26>=0 ], cost: 2

     21: f2 -> f1 : A'=free_32, B'=free_28, C'=free_30, D'=2, E'=free_29, F'=free_32, G'=free_28, H'=free_30, Q'=2, J'=free_29, K'=1, [ free_44>=1 && 7>=free_44 && 1>=free_48 && free_48>=0 && free_29>=1 && 7>=free_29 && 1>=free_32 && free_32>=0 ], cost: 2

     22: f2 -> [4] : A'=free_26, B'=free_20, C'=free_23, D'=2, E'=free_22, F'=free_26, G'=free_20, H'=free_23, Q'=2, J'=free_22, K'=1, [ free_44>=1 && 7>=free_44 && 1>=free_48 && free_48>=0 && free_22>=1 && 7>=free_22 && 1>=free_26 && free_26>=0 ], cost: NONTERM

     23: f2 -> [4] : A'=free_32, B'=free_28, C'=free_30, D'=2, E'=free_29, F'=free_32, G'=free_28, H'=free_30, Q'=2, J'=free_29, K'=1, [ free_44>=1 && 7>=free_44 && 1>=free_48 && free_48>=0 && free_29>=1 && 7>=free_29 && 1>=free_32 && free_32>=0 ], cost: NONTERM



Eliminated locations (on tree-shaped paths):

   Start location: f0

      0: f0 -> f1 : [], cost: 1

     10: f0 -> [4] : [], cost: NONTERM

     25: f1 -> [5] : A'=0, B'=free_2, C'=free, D'=3, E'=free_1, F'=0, G'=free_2, H'=free, Q'=3, J'=free_1, K'=2, [ 7>=free_1 && free_1>=1 && L>=1 && M>=1 ], cost: NONTERM

     26: f1 -> f1 : A'=free_18, B'=free_14, C'=free_16, D'=2, E'=free_15, F'=free_18, G'=free_14, H'=free_16, Q'=2, J'=free_15, K'=1, [ 7>=free_1 && free_1>=1 && free_15>=1 && 7>=free_15 && 1>=free_18 && free_18>=0 ], cost: 2

     27: f1 -> [4] : A'=free_18, B'=free_14, C'=free_16, D'=2, E'=free_15, F'=free_18, G'=free_14, H'=free_16, Q'=2, J'=free_15, K'=1, [ 7>=free_1 && free_1>=1 && free_15>=1 && 7>=free_15 && 1>=free_18 && free_18>=0 ], cost: NONTERM

     28: f1 -> f1 : A'=free_26, B'=free_20, C'=free_23, D'=2, E'=free_22, F'=free_26, G'=free_20, H'=free_23, Q'=2, J'=free_22, K'=1, [ 7>=free_1 && free_1>=1 && free_36>=1 && 7>=free_36 && 1>=free_40 && free_40>=0 && free_22>=1 && 7>=free_22 && 1>=free_26 && free_26>=0 ], cost: 3

     29: f1 -> f1 : A'=free_32, B'=free_28, C'=free_30, D'=2, E'=free_29, F'=free_32, G'=free_28, H'=free_30, Q'=2, J'=free_29, K'=1, [ 7>=free_1 && free_1>=1 && free_36>=1 && 7>=free_36 && 1>=free_40 && free_40>=0 && free_29>=1 && 7>=free_29 && 1>=free_32 && free_32>=0 ], cost: 3

     30: f1 -> [4] : A'=free_26, B'=free_20, C'=free_23, D'=2, E'=free_22, F'=free_26, G'=free_20, H'=free_23, Q'=2, J'=free_22, K'=1, [ 7>=free_1 && free_1>=1 && free_36>=1 && 7>=free_36 && 1>=free_40 && free_40>=0 && free_22>=1 && 7>=free_22 && 1>=free_26 && free_26>=0 ], cost: NONTERM

     31: f1 -> [4] : A'=free_32, B'=free_28, C'=free_30, D'=2, E'=free_29, F'=free_32, G'=free_28, H'=free_30, Q'=2, J'=free_29, K'=1, [ 7>=free_1 && free_1>=1 && free_36>=1 && 7>=free_36 && 1>=free_40 && free_40>=0 && free_29>=1 && 7>=free_29 && 1>=free_32 && free_32>=0 ], cost: NONTERM

     32: f1 -> f1 : A'=free_26, B'=free_20, C'=free_23, D'=2, E'=free_22, F'=free_26, G'=free_20, H'=free_23, Q'=2, J'=free_22, K'=1, [ 7>=free_1 && free_1>=1 && free_44>=1 && 7>=free_44 && 1>=free_48 && free_48>=0 && free_22>=1 && 7>=free_22 && 1>=free_26 && free_26>=0 ], cost: 3

     33: f1 -> f1 : A'=free_32, B'=free_28, C'=free_30, D'=2, E'=free_29, F'=free_32, G'=free_28, H'=free_30, Q'=2, J'=free_29, K'=1, [ 7>=free_1 && free_1>=1 && free_44>=1 && 7>=free_44 && 1>=free_48 && free_48>=0 && free_29>=1 && 7>=free_29 && 1>=free_32 && free_32>=0 ], cost: 3

     34: f1 -> [4] : A'=free_26, B'=free_20, C'=free_23, D'=2, E'=free_22, F'=free_26, G'=free_20, H'=free_23, Q'=2, J'=free_22, K'=1, [ 7>=free_1 && free_1>=1 && free_44>=1 && 7>=free_44 && 1>=free_48 && free_48>=0 && free_22>=1 && 7>=free_22 && 1>=free_26 && free_26>=0 ], cost: NONTERM

     35: f1 -> [4] : A'=free_32, B'=free_28, C'=free_30, D'=2, E'=free_29, F'=free_32, G'=free_28, H'=free_30, Q'=2, J'=free_29, K'=1, [ 7>=free_1 && free_1>=1 && free_44>=1 && 7>=free_44 && 1>=free_48 && free_48>=0 && free_29>=1 && 7>=free_29 && 1>=free_32 && free_32>=0 ], cost: NONTERM



Accelerating simple loops of location 1.

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

   Accelerating the following rules:

     26: f1 -> f1 : A'=free_18, B'=free_14, C'=free_16, D'=2, E'=free_15, F'=free_18, G'=free_14, H'=free_16, Q'=2, J'=free_15, K'=1, [ free_15>=1 && 7>=free_15 && 1>=free_18 && free_18>=0 ], cost: 2

     32: f1 -> f1 : A'=free_26, B'=free_20, C'=free_23, D'=2, E'=free_22, F'=free_26, G'=free_20, H'=free_23, Q'=2, J'=free_22, K'=1, [ free_22>=1 && 7>=free_22 && 1>=free_26 && free_26>=0 ], cost: 3

     33: f1 -> f1 : A'=free_32, B'=free_28, C'=free_30, D'=2, E'=free_29, F'=free_32, G'=free_28, H'=free_30, Q'=2, J'=free_29, K'=1, [ free_29>=1 && 7>=free_29 && 1>=free_32 && free_32>=0 ], cost: 3



   Accelerated rule 26 with NONTERM, yielding the new rule 36.

   Accelerated rule 32 with NONTERM, yielding the new rule 37.

   Accelerated rule 33 with NONTERM, yielding the new rule 38.

   Removing the simple loops: 26 32 33.



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

   Start location: f0

      0: f0 -> f1 : [], cost: 1

     10: f0 -> [4] : [], cost: NONTERM

     25: f1 -> [5] : A'=0, B'=free_2, C'=free, D'=3, E'=free_1, F'=0, G'=free_2, H'=free, Q'=3, J'=free_1, K'=2, [ 7>=free_1 && free_1>=1 && L>=1 && M>=1 ], cost: NONTERM

     27: f1 -> [4] : A'=free_18, B'=free_14, C'=free_16, D'=2, E'=free_15, F'=free_18, G'=free_14, H'=free_16, Q'=2, J'=free_15, K'=1, [ 7>=free_1 && free_1>=1 && free_15>=1 && 7>=free_15 && 1>=free_18 && free_18>=0 ], cost: NONTERM

     30: f1 -> [4] : A'=free_26, B'=free_20, C'=free_23, D'=2, E'=free_22, F'=free_26, G'=free_20, H'=free_23, Q'=2, J'=free_22, K'=1, [ 7>=free_1 && free_1>=1 && free_36>=1 && 7>=free_36 && 1>=free_40 && free_40>=0 && free_22>=1 && 7>=free_22 && 1>=free_26 && free_26>=0 ], cost: NONTERM

     31: f1 -> [4] : A'=free_32, B'=free_28, C'=free_30, D'=2, E'=free_29, F'=free_32, G'=free_28, H'=free_30, Q'=2, J'=free_29, K'=1, [ 7>=free_1 && free_1>=1 && free_36>=1 && 7>=free_36 && 1>=free_40 && free_40>=0 && free_29>=1 && 7>=free_29 && 1>=free_32 && free_32>=0 ], cost: NONTERM

     34: f1 -> [4] : A'=free_26, B'=free_20, C'=free_23, D'=2, E'=free_22, F'=free_26, G'=free_20, H'=free_23, Q'=2, J'=free_22, K'=1, [ 7>=free_1 && free_1>=1 && free_44>=1 && 7>=free_44 && 1>=free_48 && free_48>=0 && free_22>=1 && 7>=free_22 && 1>=free_26 && free_26>=0 ], cost: NONTERM

     35: f1 -> [4] : A'=free_32, B'=free_28, C'=free_30, D'=2, E'=free_29, F'=free_32, G'=free_28, H'=free_30, Q'=2, J'=free_29, K'=1, [ 7>=free_1 && free_1>=1 && free_44>=1 && 7>=free_44 && 1>=free_48 && free_48>=0 && free_29>=1 && 7>=free_29 && 1>=free_32 && free_32>=0 ], cost: NONTERM

     36: f1 -> [6] : [ free_15>=1 && 7>=free_15 && 1>=free_18 && free_18>=0 ], cost: NONTERM

     37: f1 -> [6] : [ free_22>=1 && 7>=free_22 && 1>=free_26 && free_26>=0 ], cost: NONTERM

     38: f1 -> [6] : [ free_29>=1 && 7>=free_29 && 1>=free_32 && free_32>=0 ], cost: NONTERM



Chained accelerated rules (with incoming rules):

   Start location: f0

      0: f0 -> f1 : [], cost: 1

     10: f0 -> [4] : [], cost: NONTERM

     39: f0 -> [6] : [], cost: NONTERM

     40: f0 -> [6] : [], cost: NONTERM

     41: f0 -> [6] : [], cost: NONTERM

     25: f1 -> [5] : A'=0, B'=free_2, C'=free, D'=3, E'=free_1, F'=0, G'=free_2, H'=free, Q'=3, J'=free_1, K'=2, [ 7>=free_1 && free_1>=1 && L>=1 && M>=1 ], cost: NONTERM

     27: f1 -> [4] : A'=free_18, B'=free_14, C'=free_16, D'=2, E'=free_15, F'=free_18, G'=free_14, H'=free_16, Q'=2, J'=free_15, K'=1, [ 7>=free_1 && free_1>=1 && free_15>=1 && 7>=free_15 && 1>=free_18 && free_18>=0 ], cost: NONTERM

     30: f1 -> [4] : A'=free_26, B'=free_20, C'=free_23, D'=2, E'=free_22, F'=free_26, G'=free_20, H'=free_23, Q'=2, J'=free_22, K'=1, [ 7>=free_1 && free_1>=1 && free_36>=1 && 7>=free_36 && 1>=free_40 && free_40>=0 && free_22>=1 && 7>=free_22 && 1>=free_26 && free_26>=0 ], cost: NONTERM

     31: f1 -> [4] : A'=free_32, B'=free_28, C'=free_30, D'=2, E'=free_29, F'=free_32, G'=free_28, H'=free_30, Q'=2, J'=free_29, K'=1, [ 7>=free_1 && free_1>=1 && free_36>=1 && 7>=free_36 && 1>=free_40 && free_40>=0 && free_29>=1 && 7>=free_29 && 1>=free_32 && free_32>=0 ], cost: NONTERM

     34: f1 -> [4] : A'=free_26, B'=free_20, C'=free_23, D'=2, E'=free_22, F'=free_26, G'=free_20, H'=free_23, Q'=2, J'=free_22, K'=1, [ 7>=free_1 && free_1>=1 && free_44>=1 && 7>=free_44 && 1>=free_48 && free_48>=0 && free_22>=1 && 7>=free_22 && 1>=free_26 && free_26>=0 ], cost: NONTERM

     35: f1 -> [4] : A'=free_32, B'=free_28, C'=free_30, D'=2, E'=free_29, F'=free_32, G'=free_28, H'=free_30, Q'=2, J'=free_29, K'=1, [ 7>=free_1 && free_1>=1 && free_44>=1 && 7>=free_44 && 1>=free_48 && free_48>=0 && free_29>=1 && 7>=free_29 && 1>=free_32 && free_32>=0 ], cost: NONTERM



Eliminated locations (on tree-shaped paths):

   Start location: f0

     10: f0 -> [4] : [], cost: NONTERM

     39: f0 -> [6] : [], cost: NONTERM

     40: f0 -> [6] : [], cost: NONTERM

     41: f0 -> [6] : [], cost: NONTERM

     42: f0 -> [5] : A'=0, B'=free_2, C'=free, D'=3, E'=free_1, F'=0, G'=free_2, H'=free, Q'=3, J'=free_1, K'=2, [ 7>=free_1 && free_1>=1 && L>=1 && M>=1 ], cost: NONTERM

     43: f0 -> [4] : A'=free_18, B'=free_14, C'=free_16, D'=2, E'=free_15, F'=free_18, G'=free_14, H'=free_16, Q'=2, J'=free_15, K'=1, [ 7>=free_1 && free_1>=1 && free_15>=1 && 7>=free_15 && 1>=free_18 && free_18>=0 ], cost: NONTERM

     44: f0 -> [4] : A'=free_26, B'=free_20, C'=free_23, D'=2, E'=free_22, F'=free_26, G'=free_20, H'=free_23, Q'=2, J'=free_22, K'=1, [ 7>=free_1 && free_1>=1 && free_36>=1 && 7>=free_36 && 1>=free_40 && free_40>=0 && free_22>=1 && 7>=free_22 && 1>=free_26 && free_26>=0 ], cost: NONTERM

     45: f0 -> [4] : A'=free_32, B'=free_28, C'=free_30, D'=2, E'=free_29, F'=free_32, G'=free_28, H'=free_30, Q'=2, J'=free_29, K'=1, [ 7>=free_1 && free_1>=1 && free_36>=1 && 7>=free_36 && 1>=free_40 && free_40>=0 && free_29>=1 && 7>=free_29 && 1>=free_32 && free_32>=0 ], cost: NONTERM

     46: f0 -> [4] : A'=free_26, B'=free_20, C'=free_23, D'=2, E'=free_22, F'=free_26, G'=free_20, H'=free_23, Q'=2, J'=free_22, K'=1, [ 7>=free_1 && free_1>=1 && free_44>=1 && 7>=free_44 && 1>=free_48 && free_48>=0 && free_22>=1 && 7>=free_22 && 1>=free_26 && free_26>=0 ], cost: NONTERM

     47: f0 -> [4] : A'=free_32, B'=free_28, C'=free_30, D'=2, E'=free_29, F'=free_32, G'=free_28, H'=free_30, Q'=2, J'=free_29, K'=1, [ 7>=free_1 && free_1>=1 && free_44>=1 && 7>=free_44 && 1>=free_48 && free_48>=0 && free_29>=1 && 7>=free_29 && 1>=free_32 && free_32>=0 ], cost: NONTERM



Applied pruning (of leafs and parallel rules):

   Start location: f0

     10: f0 -> [4] : [], cost: NONTERM

     41: f0 -> [6] : [], cost: NONTERM

     42: f0 -> [5] : A'=0, B'=free_2, C'=free, D'=3, E'=free_1, F'=0, G'=free_2, H'=free, Q'=3, J'=free_1, K'=2, [ 7>=free_1 && free_1>=1 && L>=1 && M>=1 ], cost: NONTERM

     43: f0 -> [4] : A'=free_18, B'=free_14, C'=free_16, D'=2, E'=free_15, F'=free_18, G'=free_14, H'=free_16, Q'=2, J'=free_15, K'=1, [ 7>=free_1 && free_1>=1 && free_15>=1 && 7>=free_15 && 1>=free_18 && free_18>=0 ], cost: NONTERM

     44: f0 -> [4] : A'=free_26, B'=free_20, C'=free_23, D'=2, E'=free_22, F'=free_26, G'=free_20, H'=free_23, Q'=2, J'=free_22, K'=1, [ 7>=free_1 && free_1>=1 && free_36>=1 && 7>=free_36 && 1>=free_40 && free_40>=0 && free_22>=1 && 7>=free_22 && 1>=free_26 && free_26>=0 ], cost: NONTERM

     45: f0 -> [4] : A'=free_32, B'=free_28, C'=free_30, D'=2, E'=free_29, F'=free_32, G'=free_28, H'=free_30, Q'=2, J'=free_29, K'=1, [ 7>=free_1 && free_1>=1 && free_36>=1 && 7>=free_36 && 1>=free_40 && free_40>=0 && free_29>=1 && 7>=free_29 && 1>=free_32 && free_32>=0 ], cost: NONTERM

     47: f0 -> [4] : A'=free_32, B'=free_28, C'=free_30, D'=2, E'=free_29, F'=free_32, G'=free_28, H'=free_30, Q'=2, J'=free_29, K'=1, [ 7>=free_1 && free_1>=1 && free_44>=1 && 7>=free_44 && 1>=free_48 && free_48>=0 && free_29>=1 && 7>=free_29 && 1>=free_32 && free_32>=0 ], cost: NONTERM



### Computing asymptotic complexity ###



Fully simplified ITS problem

   Start location: f0

     41: f0 -> [6] : [], cost: NONTERM

     42: f0 -> [5] : A'=0, B'=free_2, C'=free, D'=3, E'=free_1, F'=0, G'=free_2, H'=free, Q'=3, J'=free_1, K'=2, [ 7>=free_1 && free_1>=1 && L>=1 && M>=1 ], cost: NONTERM

     43: f0 -> [4] : A'=free_18, B'=free_14, C'=free_16, D'=2, E'=free_15, F'=free_18, G'=free_14, H'=free_16, Q'=2, J'=free_15, K'=1, [ 7>=free_1 && free_1>=1 && free_15>=1 && 7>=free_15 && 1>=free_18 && free_18>=0 ], cost: NONTERM

     44: f0 -> [4] : A'=free_26, B'=free_20, C'=free_23, D'=2, E'=free_22, F'=free_26, G'=free_20, H'=free_23, Q'=2, J'=free_22, K'=1, [ 7>=free_1 && free_1>=1 && free_36>=1 && 7>=free_36 && 1>=free_40 && free_40>=0 && free_22>=1 && 7>=free_22 && 1>=free_26 && free_26>=0 ], cost: NONTERM

     45: f0 -> [4] : A'=free_32, B'=free_28, C'=free_30, D'=2, E'=free_29, F'=free_32, G'=free_28, H'=free_30, Q'=2, J'=free_29, K'=1, [ 7>=free_1 && free_1>=1 && free_36>=1 && 7>=free_36 && 1>=free_40 && free_40>=0 && free_29>=1 && 7>=free_29 && 1>=free_32 && free_32>=0 ], cost: NONTERM

     47: f0 -> [4] : A'=free_32, B'=free_28, C'=free_30, D'=2, E'=free_29, F'=free_32, G'=free_28, H'=free_30, Q'=2, J'=free_29, K'=1, [ 7>=free_1 && free_1>=1 && free_44>=1 && 7>=free_44 && 1>=free_48 && free_48>=0 && free_29>=1 && 7>=free_29 && 1>=free_32 && free_32>=0 ], cost: NONTERM



Computing asymptotic complexity for rule 41

   Guard is satisfiable, yielding nontermination

   Resulting cost NONTERM has complexity: Nonterm



Found new complexity Nonterm.



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

   Complexity:  Nonterm

   Cpx degree:  Nonterm

   Solved cost: NONTERM

   Rule cost:   NONTERM

   Rule guard:  []



NO


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

(2)
BOUNDS(INF, INF)