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


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

(0)
Obligation:
Complexity Int TRS consisting of the following rules:
f63(A, B, C, D, E, F, G, H, I, J, K) -> Com_1(f11(A, B, C, D, E, F, G, H, I, J, K)) :|: A >= 1 + B
f0(A, B, C, D, E, F, G, H, I, J, K) -> Com_1(f11(A, 10, 20, 1, 20, 0, 0, H, I, J, K)) :|: TRUE
f11(A, B, C, D, E, F, G, H, I, J, K) -> Com_1(f11(A, B, C, D, E, F, 1, H, I, J, K)) :|: D >= E && G >= 0 && G <= 0
f11(A, B, C, D, E, F, G, H, I, J, K) -> Com_1(f11(A, B, C, D, E, F, 1, H, I, J, K)) :|: D + 1 >= E && E >= 2 + D && G >= 0 && G <= 0
f11(A, B, C, D, E, F, G, H, I, J, K) -> Com_1(f11(A, B, C, D, D + 1, F, 1, H, I, J, K)) :|: E >= D + 1 && E <= D + 1 && G >= 0 && G <= 0
f11(A, B, C, D, E, F, G, H, I, J, K) -> Com_1(f11(A, B, C, D, D + 1, F, 1, N, I, J, K)) :|: L >= M + 1 && E >= D + 1 && E <= D + 1 && G >= 0 && G <= 0
f11(A, B, C, D, E, F, G, H, I, J, K) -> Com_1(f40(E, B, C, D, E, F, 0, N, L, D + 1, M)) :|: E >= 2 + D && G >= 0 && G <= 0
f40(A, B, C, D, E, F, G, H, I, J, K) -> Com_1(f59(A, B, C, D, E, F, G, H, I, J, K)) :|: 0 >= F + 1
f40(A, B, C, D, E, F, G, H, I, J, K) -> Com_1(f59(A, B, C, D, E, F, G, H, I, J, K)) :|: F >= 1
f40(A, B, C, D, E, F, G, H, I, J, K) -> Com_1(f43(A, B, C, D, E, 0, G, H, I, J + 1, K)) :|: F >= 0 && F <= 0
f43(A, B, C, D, E, F, G, H, I, J, K) -> Com_1(f43(A, B, C, D, E, F, G, H, I, J + 1, K)) :|: K >= N + 1
f48(A, B, C, D, E, F, G, H, I, J, K) -> Com_1(f48(A - 1, B, C, D, E, F, G, H, I, J, K)) :|: TRUE
f54(A, B, C, D, E, F, G, H, I, J, K) -> Com_1(f40(A, B, C, D, E, F, G, H, I, J, K)) :|: 0 >= F + 1
f54(A, B, C, D, E, F, G, H, I, J, K) -> Com_1(f40(A, B, C, D, E, F, G, H, I, J, K)) :|: F >= 1
f54(A, B, C, D, E, F, G, H, I, J, K) -> Com_1(f40(A, B, C, D, E, 0, G, N, I, J, K)) :|: F >= 0 && F <= 0
f59(A, B, C, D, E, F, G, H, I, J, K) -> Com_1(f63(A, B, C, D, E, F, G, H, I, J, K)) :|: B >= A + 1
f59(A, B, C, D, E, F, G, H, I, J, K) -> Com_1(f63(A, B, C, D, A - 1, F, G, H, I, J, K)) :|: A >= B
f63(A, B, C, D, E, F, G, H, I, J, K) -> Com_1(f11(A, B, C, J, E, F, G, H, I, J, K)) :|: B >= A
f48(A, B, C, D, E, F, G, H, I, J, K) -> Com_1(f54(A, B, C, D, E, F, G, H, I, J, K)) :|: A >= J
f48(A, B, C, D, E, F, G, H, I, J, K) -> Com_1(f54(A, B, C, D, E, 1, G, H, I, J, K)) :|: J >= A + 1
f43(A, B, C, D, E, F, G, H, I, J, K) -> Com_1(f48(A - 1, B, C, D, E, F, G, H, I, J, K)) :|: TRUE
f11(A, B, C, D, E, F, G, H, I, J, K) -> Com_1(f69(A, B, C, D, E, F, G, H, I, J, K)) :|: 0 >= G + 1
f11(A, B, C, D, E, F, G, H, I, J, K) -> Com_1(f69(A, B, C, D, E, F, G, H, I, J, K)) :|: G >= 1

The start-symbols are:[f0_11]


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

(1) Loat Proof (FINISHED)


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



Initial linear ITS problem

   Start location: f0

      0: f63 -> f11 : [ A>=1+B ], cost: 1

     17: f63 -> f11 : D'=J, [ B>=A ], cost: 1

      1: f0 -> f11 : B'=10, C'=20, D'=1, E'=20, F'=0, G'=0, [], cost: 1

      2: f11 -> f11 : G'=1, [ D>=E && G==0 ], cost: 1

      3: f11 -> f11 : G'=1, [ 1+D>=E && E>=2+D && G==0 ], cost: 1

      4: f11 -> f11 : E'=1+D, G'=1, [ E==1+D && G==0 ], cost: 1

      5: f11 -> f11 : E'=1+D, G'=1, H'=free_1, [ free_2>=1+free && E==1+D && G==0 ], cost: 1

      6: f11 -> f40 : A'=E, G'=0, H'=free_4, Q'=free_5, J'=1+D, K'=free_3, [ E>=2+D && G==0 ], cost: 1

     21: f11 -> f69 : [ 0>=1+G ], cost: 1

     22: f11 -> f69 : [ G>=1 ], cost: 1

      7: f40 -> f59 : [ 0>=1+F ], cost: 1

      8: f40 -> f59 : [ F>=1 ], cost: 1

      9: f40 -> f43 : F'=0, J'=1+J, [ F==0 ], cost: 1

     10: f43 -> f43 : J'=1+J, [ K>=1+free_6 ], cost: 1

     20: f43 -> f48 : A'=-1+A, [], cost: 1

     11: f48 -> f48 : A'=-1+A, [], cost: 1

     18: f48 -> f54 : [ A>=J ], cost: 1

     19: f48 -> f54 : F'=1, [ J>=1+A ], cost: 1

     12: f54 -> f40 : [ 0>=1+F ], cost: 1

     13: f54 -> f40 : [ F>=1 ], cost: 1

     14: f54 -> f40 : F'=0, H'=free_7, [ F==0 ], cost: 1

     15: f59 -> f63 : [ B>=1+A ], cost: 1

     16: f59 -> f63 : E'=-1+A, [ A>=B ], cost: 1



Checking for constant complexity:

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

      1: f0 -> f11 : B'=10, C'=20, D'=1, E'=20, F'=0, G'=0, [], cost: 1



Removed unreachable and leaf rules:

   Start location: f0

      0: f63 -> f11 : [ A>=1+B ], cost: 1

     17: f63 -> f11 : D'=J, [ B>=A ], cost: 1

      1: f0 -> f11 : B'=10, C'=20, D'=1, E'=20, F'=0, G'=0, [], cost: 1

      2: f11 -> f11 : G'=1, [ D>=E && G==0 ], cost: 1

      3: f11 -> f11 : G'=1, [ 1+D>=E && E>=2+D && G==0 ], cost: 1

      4: f11 -> f11 : E'=1+D, G'=1, [ E==1+D && G==0 ], cost: 1

      5: f11 -> f11 : E'=1+D, G'=1, H'=free_1, [ free_2>=1+free && E==1+D && G==0 ], cost: 1

      6: f11 -> f40 : A'=E, G'=0, H'=free_4, Q'=free_5, J'=1+D, K'=free_3, [ E>=2+D && G==0 ], cost: 1

      7: f40 -> f59 : [ 0>=1+F ], cost: 1

      8: f40 -> f59 : [ F>=1 ], cost: 1

      9: f40 -> f43 : F'=0, J'=1+J, [ F==0 ], cost: 1

     10: f43 -> f43 : J'=1+J, [ K>=1+free_6 ], cost: 1

     20: f43 -> f48 : A'=-1+A, [], cost: 1

     11: f48 -> f48 : A'=-1+A, [], cost: 1

     18: f48 -> f54 : [ A>=J ], cost: 1

     19: f48 -> f54 : F'=1, [ J>=1+A ], cost: 1

     12: f54 -> f40 : [ 0>=1+F ], cost: 1

     13: f54 -> f40 : [ F>=1 ], cost: 1

     14: f54 -> f40 : F'=0, H'=free_7, [ F==0 ], cost: 1

     15: f59 -> f63 : [ B>=1+A ], cost: 1

     16: f59 -> f63 : E'=-1+A, [ A>=B ], cost: 1



Removed rules with unsatisfiable guard:

   Start location: f0

      0: f63 -> f11 : [ A>=1+B ], cost: 1

     17: f63 -> f11 : D'=J, [ B>=A ], cost: 1

      1: f0 -> f11 : B'=10, C'=20, D'=1, E'=20, F'=0, G'=0, [], cost: 1

      2: f11 -> f11 : G'=1, [ D>=E && G==0 ], cost: 1

      4: f11 -> f11 : E'=1+D, G'=1, [ E==1+D && G==0 ], cost: 1

      5: f11 -> f11 : E'=1+D, G'=1, H'=free_1, [ free_2>=1+free && E==1+D && G==0 ], cost: 1

      6: f11 -> f40 : A'=E, G'=0, H'=free_4, Q'=free_5, J'=1+D, K'=free_3, [ E>=2+D && G==0 ], cost: 1

      7: f40 -> f59 : [ 0>=1+F ], cost: 1

      8: f40 -> f59 : [ F>=1 ], cost: 1

      9: f40 -> f43 : F'=0, J'=1+J, [ F==0 ], cost: 1

     10: f43 -> f43 : J'=1+J, [ K>=1+free_6 ], cost: 1

     20: f43 -> f48 : A'=-1+A, [], cost: 1

     11: f48 -> f48 : A'=-1+A, [], cost: 1

     18: f48 -> f54 : [ A>=J ], cost: 1

     19: f48 -> f54 : F'=1, [ J>=1+A ], cost: 1

     12: f54 -> f40 : [ 0>=1+F ], cost: 1

     13: f54 -> f40 : [ F>=1 ], cost: 1

     14: f54 -> f40 : F'=0, H'=free_7, [ F==0 ], cost: 1

     15: f59 -> f63 : [ B>=1+A ], cost: 1

     16: f59 -> f63 : E'=-1+A, [ A>=B ], cost: 1



Simplified all rules, resulting in:

   Start location: f0

      0: f63 -> f11 : [ A>=1+B ], cost: 1

     17: f63 -> f11 : D'=J, [ B>=A ], cost: 1

      1: f0 -> f11 : B'=10, C'=20, D'=1, E'=20, F'=0, G'=0, [], cost: 1

      2: f11 -> f11 : G'=1, [ D>=E && G==0 ], cost: 1

      4: f11 -> f11 : E'=1+D, G'=1, [ E==1+D && G==0 ], cost: 1

      5: f11 -> f11 : E'=1+D, G'=1, H'=free_1, [ E==1+D && G==0 ], cost: 1

      6: f11 -> f40 : A'=E, G'=0, H'=free_4, Q'=free_5, J'=1+D, K'=free_3, [ E>=2+D && G==0 ], cost: 1

      7: f40 -> f59 : [ 0>=1+F ], cost: 1

      8: f40 -> f59 : [ F>=1 ], cost: 1

      9: f40 -> f43 : F'=0, J'=1+J, [ F==0 ], cost: 1

     10: f43 -> f43 : J'=1+J, [], cost: 1

     20: f43 -> f48 : A'=-1+A, [], cost: 1

     11: f48 -> f48 : A'=-1+A, [], cost: 1

     18: f48 -> f54 : [ A>=J ], cost: 1

     19: f48 -> f54 : F'=1, [ J>=1+A ], cost: 1

     12: f54 -> f40 : [ 0>=1+F ], cost: 1

     13: f54 -> f40 : [ F>=1 ], cost: 1

     14: f54 -> f40 : F'=0, H'=free_7, [ F==0 ], cost: 1

     15: f59 -> f63 : [ B>=1+A ], cost: 1

     16: f59 -> f63 : E'=-1+A, [ A>=B ], cost: 1



### Simplification by acceleration and chaining ###



Accelerating simple loops of location 2.

   Accelerating the following rules:

      2: f11 -> f11 : G'=1, [ D>=E && G==0 ], cost: 1

      4: f11 -> f11 : E'=1+D, G'=1, [ E==1+D && G==0 ], cost: 1

      5: f11 -> f11 : E'=1+D, G'=1, H'=free_1, [ E==1+D && G==0 ], cost: 1



   Accelerated rule 2 with metering function 1-G, yielding the new rule 23.

   Accelerated rule 4 with metering function 1-G, yielding the new rule 24.

   Accelerated rule 5 with metering function 1-G, yielding the new rule 25.

   Removing the simple loops: 2 4 5.



Accelerating simple loops of location 4.

   Accelerating the following rules:

     10: f43 -> f43 : J'=1+J, [], cost: 1



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

   Removing the simple loops: 10.



Accelerating simple loops of location 5.

   Accelerating the following rules:

     11: f48 -> f48 : A'=-1+A, [], cost: 1



   Accelerated rule 11 with NONTERM, yielding the new rule 27.

   Removing the simple loops: 11.



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

   Start location: f0

      0: f63 -> f11 : [ A>=1+B ], cost: 1

     17: f63 -> f11 : D'=J, [ B>=A ], cost: 1

      1: f0 -> f11 : B'=10, C'=20, D'=1, E'=20, F'=0, G'=0, [], cost: 1

      6: f11 -> f40 : A'=E, G'=0, H'=free_4, Q'=free_5, J'=1+D, K'=free_3, [ E>=2+D && G==0 ], cost: 1

     23: f11 -> f11 : G'=1, [ D>=E && G==0 ], cost: 1-G

     24: f11 -> f11 : E'=1+D, G'=1, [ E==1+D && G==0 ], cost: 1-G

     25: f11 -> f11 : E'=1+D, G'=1, H'=free_1, [ E==1+D && G==0 ], cost: 1-G

      7: f40 -> f59 : [ 0>=1+F ], cost: 1

      8: f40 -> f59 : [ F>=1 ], cost: 1

      9: f40 -> f43 : F'=0, J'=1+J, [ F==0 ], cost: 1

     20: f43 -> f48 : A'=-1+A, [], cost: 1

     26: f43 -> [10] : [], cost: NONTERM

     18: f48 -> f54 : [ A>=J ], cost: 1

     19: f48 -> f54 : F'=1, [ J>=1+A ], cost: 1

     27: f48 -> [11] : [], cost: NONTERM

     12: f54 -> f40 : [ 0>=1+F ], cost: 1

     13: f54 -> f40 : [ F>=1 ], cost: 1

     14: f54 -> f40 : F'=0, H'=free_7, [ F==0 ], cost: 1

     15: f59 -> f63 : [ B>=1+A ], cost: 1

     16: f59 -> f63 : E'=-1+A, [ A>=B ], cost: 1



Chained accelerated rules (with incoming rules):

   Start location: f0

      0: f63 -> f11 : [ A>=1+B ], cost: 1

     17: f63 -> f11 : D'=J, [ B>=A ], cost: 1

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

     29: f63 -> f11 : D'=J, G'=1, [ B>=A && J>=E && G==0 ], cost: 2-G

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

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

     32: f63 -> f11 : E'=1+D, G'=1, H'=free_1, [ A>=1+B && E==1+D && G==0 ], cost: 2-G

     33: f63 -> f11 : D'=J, E'=1+J, G'=1, H'=free_1, [ B>=A && E==1+J && G==0 ], cost: 2-G

      1: f0 -> f11 : B'=10, C'=20, D'=1, E'=20, F'=0, G'=0, [], cost: 1

      6: f11 -> f40 : A'=E, G'=0, H'=free_4, Q'=free_5, J'=1+D, K'=free_3, [ E>=2+D && G==0 ], cost: 1

      7: f40 -> f59 : [ 0>=1+F ], cost: 1

      8: f40 -> f59 : [ F>=1 ], cost: 1

      9: f40 -> f43 : F'=0, J'=1+J, [ F==0 ], cost: 1

     34: f40 -> [10] : F'=0, J'=1+J, [ F==0 ], cost: NONTERM

     20: f43 -> f48 : A'=-1+A, [], cost: 1

     35: f43 -> [11] : A'=-1+A, [], cost: NONTERM

     18: f48 -> f54 : [ A>=J ], cost: 1

     19: f48 -> f54 : F'=1, [ J>=1+A ], cost: 1

     12: f54 -> f40 : [ 0>=1+F ], cost: 1

     13: f54 -> f40 : [ F>=1 ], cost: 1

     14: f54 -> f40 : F'=0, H'=free_7, [ F==0 ], cost: 1

     15: f59 -> f63 : [ B>=1+A ], cost: 1

     16: f59 -> f63 : E'=-1+A, [ A>=B ], cost: 1



Eliminated locations (on tree-shaped paths):

   Start location: f0

      0: f63 -> f11 : [ A>=1+B ], cost: 1

     17: f63 -> f11 : D'=J, [ B>=A ], cost: 1

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

     29: f63 -> f11 : D'=J, G'=1, [ B>=A && J>=E && G==0 ], cost: 2-G

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

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

     32: f63 -> f11 : E'=1+D, G'=1, H'=free_1, [ A>=1+B && E==1+D && G==0 ], cost: 2-G

     33: f63 -> f11 : D'=J, E'=1+J, G'=1, H'=free_1, [ B>=A && E==1+J && G==0 ], cost: 2-G

      1: f0 -> f11 : B'=10, C'=20, D'=1, E'=20, F'=0, G'=0, [], cost: 1

      6: f11 -> f40 : A'=E, G'=0, H'=free_4, Q'=free_5, J'=1+D, K'=free_3, [ E>=2+D && G==0 ], cost: 1

     34: f40 -> [10] : F'=0, J'=1+J, [ F==0 ], cost: NONTERM

     36: f40 -> f48 : A'=-1+A, F'=0, J'=1+J, [ F==0 ], cost: 2

     37: f40 -> [11] : A'=-1+A, F'=0, J'=1+J, [ F==0 ], cost: NONTERM

     38: f40 -> f63 : [ 0>=1+F && B>=1+A ], cost: 2

     39: f40 -> f63 : E'=-1+A, [ 0>=1+F && A>=B ], cost: 2

     40: f40 -> f63 : [ F>=1 && B>=1+A ], cost: 2

     41: f40 -> f63 : E'=-1+A, [ F>=1 && A>=B ], cost: 2

     42: f48 -> f40 : [ A>=J && 0>=1+F ], cost: 2

     43: f48 -> f40 : [ A>=J && F>=1 ], cost: 2

     44: f48 -> f40 : F'=0, H'=free_7, [ A>=J && F==0 ], cost: 2

     45: f48 -> f40 : F'=1, [ J>=1+A ], cost: 2



Applied pruning (of leafs and parallel rules):

   Start location: f0

      0: f63 -> f11 : [ A>=1+B ], cost: 1

     17: f63 -> f11 : D'=J, [ B>=A ], cost: 1

     29: f63 -> f11 : D'=J, G'=1, [ B>=A && J>=E && G==0 ], cost: 2-G

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

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

      1: f0 -> f11 : B'=10, C'=20, D'=1, E'=20, F'=0, G'=0, [], cost: 1

      6: f11 -> f40 : A'=E, G'=0, H'=free_4, Q'=free_5, J'=1+D, K'=free_3, [ E>=2+D && G==0 ], cost: 1

     34: f40 -> [10] : F'=0, J'=1+J, [ F==0 ], cost: NONTERM

     36: f40 -> f48 : A'=-1+A, F'=0, J'=1+J, [ F==0 ], cost: 2

     37: f40 -> [11] : A'=-1+A, F'=0, J'=1+J, [ F==0 ], cost: NONTERM

     38: f40 -> f63 : [ 0>=1+F && B>=1+A ], cost: 2

     39: f40 -> f63 : E'=-1+A, [ 0>=1+F && A>=B ], cost: 2

     40: f40 -> f63 : [ F>=1 && B>=1+A ], cost: 2

     41: f40 -> f63 : E'=-1+A, [ F>=1 && A>=B ], cost: 2

     42: f48 -> f40 : [ A>=J && 0>=1+F ], cost: 2

     43: f48 -> f40 : [ A>=J && F>=1 ], cost: 2

     44: f48 -> f40 : F'=0, H'=free_7, [ A>=J && F==0 ], cost: 2

     45: f48 -> f40 : F'=1, [ J>=1+A ], cost: 2



Eliminated locations (on tree-shaped paths):

   Start location: f0

      1: f0 -> f11 : B'=10, C'=20, D'=1, E'=20, F'=0, G'=0, [], cost: 1

      6: f11 -> f40 : A'=E, G'=0, H'=free_4, Q'=free_5, J'=1+D, K'=free_3, [ E>=2+D && G==0 ], cost: 1

     34: f40 -> [10] : F'=0, J'=1+J, [ F==0 ], cost: NONTERM

     37: f40 -> [11] : A'=-1+A, F'=0, J'=1+J, [ F==0 ], cost: NONTERM

     46: f40 -> f11 : D'=J, [ 0>=1+F && B>=1+A ], cost: 3

     47: f40 -> f11 : D'=J, G'=1, [ 0>=1+F && B>=1+A && J>=E && G==0 ], cost: 4-G

     48: f40 -> f11 : D'=J, E'=1+J, G'=1, [ 0>=1+F && B>=1+A && E==1+J && G==0 ], cost: 4-G

     49: f40 -> f11 : E'=-1+A, [ 0>=1+F && A>=1+B ], cost: 3

     50: f40 -> f11 : D'=J, E'=-1+A, [ 0>=1+F && A>=B && B>=A ], cost: 3

     51: f40 -> f11 : D'=J, E'=-1+A, G'=1, [ 0>=1+F && A>=B && B>=A && J>=-1+A && G==0 ], cost: 4-G

     52: f40 -> f11 : E'=1+D, G'=1, [ 0>=1+F && A>=1+B && -1+A==1+D && G==0 ], cost: 4-G

     53: f40 -> f11 : D'=J, E'=1+J, G'=1, [ 0>=1+F && A>=B && B>=A && -1+A==1+J && G==0 ], cost: 4-G

     54: f40 -> f11 : D'=J, [ F>=1 && B>=1+A ], cost: 3

     55: f40 -> f11 : D'=J, G'=1, [ F>=1 && B>=1+A && J>=E && G==0 ], cost: 4-G

     56: f40 -> f11 : D'=J, E'=1+J, G'=1, [ F>=1 && B>=1+A && E==1+J && G==0 ], cost: 4-G

     57: f40 -> f11 : E'=-1+A, [ F>=1 && A>=1+B ], cost: 3

     58: f40 -> f11 : D'=J, E'=-1+A, [ F>=1 && A>=B && B>=A ], cost: 3

     59: f40 -> f11 : D'=J, E'=-1+A, G'=1, [ F>=1 && A>=B && B>=A && J>=-1+A && G==0 ], cost: 4-G

     60: f40 -> f11 : E'=1+D, G'=1, [ F>=1 && A>=1+B && -1+A==1+D && G==0 ], cost: 4-G

     61: f40 -> f11 : D'=J, E'=1+J, G'=1, [ F>=1 && A>=B && B>=A && -1+A==1+J && G==0 ], cost: 4-G

     62: f40 -> f40 : A'=-1+A, F'=0, H'=free_7, J'=1+J, [ F==0 && -1+A>=1+J ], cost: 4

     63: f40 -> f40 : A'=-1+A, F'=1, J'=1+J, [ F==0 && 1+J>=A ], cost: 4



Applied pruning (of leafs and parallel rules):

   Start location: f0

      1: f0 -> f11 : B'=10, C'=20, D'=1, E'=20, F'=0, G'=0, [], cost: 1

      6: f11 -> f40 : A'=E, G'=0, H'=free_4, Q'=free_5, J'=1+D, K'=free_3, [ E>=2+D && G==0 ], cost: 1

     34: f40 -> [10] : F'=0, J'=1+J, [ F==0 ], cost: NONTERM

     37: f40 -> [11] : A'=-1+A, F'=0, J'=1+J, [ F==0 ], cost: NONTERM

     46: f40 -> f11 : D'=J, [ 0>=1+F && B>=1+A ], cost: 3

     47: f40 -> f11 : D'=J, G'=1, [ 0>=1+F && B>=1+A && J>=E && G==0 ], cost: 4-G

     49: f40 -> f11 : E'=-1+A, [ 0>=1+F && A>=1+B ], cost: 3

     53: f40 -> f11 : D'=J, E'=1+J, G'=1, [ 0>=1+F && A>=B && B>=A && -1+A==1+J && G==0 ], cost: 4-G

     55: f40 -> f11 : D'=J, G'=1, [ F>=1 && B>=1+A && J>=E && G==0 ], cost: 4-G

     62: f40 -> f40 : A'=-1+A, F'=0, H'=free_7, J'=1+J, [ F==0 && -1+A>=1+J ], cost: 4

     63: f40 -> f40 : A'=-1+A, F'=1, J'=1+J, [ F==0 && 1+J>=A ], cost: 4



Accelerating simple loops of location 3.

   Accelerating the following rules:

     62: f40 -> f40 : A'=-1+A, F'=0, H'=free_7, J'=1+J, [ F==0 && -1+A>=1+J ], cost: 4

     63: f40 -> f40 : A'=-1+A, F'=1, J'=1+J, [ F==0 && 1+J>=A ], cost: 4



   Accelerated rule 62 with metering function meter (where 2*meter==-1-J+A), yielding the new rule 64.

   Accelerated rule 63 with metering function 1-F, yielding the new rule 65.

   Nested simple loops 63 (outer loop) and 64 (inner loop) with metering function -F, resulting in the new rules: 66.

   Removing the simple loops: 62 63.



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

   Start location: f0

      1: f0 -> f11 : B'=10, C'=20, D'=1, E'=20, F'=0, G'=0, [], cost: 1

      6: f11 -> f40 : A'=E, G'=0, H'=free_4, Q'=free_5, J'=1+D, K'=free_3, [ E>=2+D && G==0 ], cost: 1

     34: f40 -> [10] : F'=0, J'=1+J, [ F==0 ], cost: NONTERM

     37: f40 -> [11] : A'=-1+A, F'=0, J'=1+J, [ F==0 ], cost: NONTERM

     46: f40 -> f11 : D'=J, [ 0>=1+F && B>=1+A ], cost: 3

     47: f40 -> f11 : D'=J, G'=1, [ 0>=1+F && B>=1+A && J>=E && G==0 ], cost: 4-G

     49: f40 -> f11 : E'=-1+A, [ 0>=1+F && A>=1+B ], cost: 3

     53: f40 -> f11 : D'=J, E'=1+J, G'=1, [ 0>=1+F && A>=B && B>=A && -1+A==1+J && G==0 ], cost: 4-G

     55: f40 -> f11 : D'=J, G'=1, [ F>=1 && B>=1+A && J>=E && G==0 ], cost: 4-G

     64: f40 -> f40 : A'=A-meter, F'=0, H'=free_7, J'=J+meter, [ F==0 && -1+A>=1+J && 2*meter==-1-J+A && meter>=1 ], cost: 4*meter

     65: f40 -> f40 : A'=-1+F+A, F'=1, J'=1-F+J, [ F==0 && 1+J>=A ], cost: 4-4*F

     66: f40 -> f40 : A'=F+A+F*meter, F'=1, H'=free_7, J'=-F+J-F*meter, [ F==0 && -1+A>=1+J && 2*meter==-1-J+A && meter>=1 && -F>=1 ], cost: -4*F-4*F*meter



Chained accelerated rules (with incoming rules):

   Start location: f0

      1: f0 -> f11 : B'=10, C'=20, D'=1, E'=20, F'=0, G'=0, [], cost: 1

      6: f11 -> f40 : A'=E, G'=0, H'=free_4, Q'=free_5, J'=1+D, K'=free_3, [ E>=2+D && G==0 ], cost: 1

     67: f11 -> f40 : A'=E-meter, F'=0, G'=0, H'=free_7, Q'=free_5, J'=1+D+meter, K'=free_3, [ G==0 && F==0 && -1+E>=2+D && 2*meter==-2-D+E && meter>=1 ], cost: 1+4*meter

     68: f11 -> f40 : A'=-1+F+E, F'=1, G'=0, H'=free_4, Q'=free_5, J'=2-F+D, K'=free_3, [ 2+D-E==0 && G==0 && F==0 ], cost: 5-4*F

     34: f40 -> [10] : F'=0, J'=1+J, [ F==0 ], cost: NONTERM

     37: f40 -> [11] : A'=-1+A, F'=0, J'=1+J, [ F==0 ], cost: NONTERM

     46: f40 -> f11 : D'=J, [ 0>=1+F && B>=1+A ], cost: 3

     47: f40 -> f11 : D'=J, G'=1, [ 0>=1+F && B>=1+A && J>=E && G==0 ], cost: 4-G

     49: f40 -> f11 : E'=-1+A, [ 0>=1+F && A>=1+B ], cost: 3

     53: f40 -> f11 : D'=J, E'=1+J, G'=1, [ 0>=1+F && A>=B && B>=A && -1+A==1+J && G==0 ], cost: 4-G

     55: f40 -> f11 : D'=J, G'=1, [ F>=1 && B>=1+A && J>=E && G==0 ], cost: 4-G



Eliminated locations (on tree-shaped paths):

   Start location: f0

      1: f0 -> f11 : B'=10, C'=20, D'=1, E'=20, F'=0, G'=0, [], cost: 1

     69: f11 -> [10] : A'=E, F'=0, G'=0, H'=free_4, Q'=free_5, J'=2+D, K'=free_3, [ E>=2+D && G==0 && F==0 ], cost: NONTERM

     70: f11 -> [11] : A'=-1+E, F'=0, G'=0, H'=free_4, Q'=free_5, J'=2+D, K'=free_3, [ E>=2+D && G==0 && F==0 ], cost: NONTERM

     71: f11 -> f11 : A'=E, D'=1+D, G'=0, H'=free_4, Q'=free_5, J'=1+D, K'=free_3, [ E>=2+D && G==0 && 0>=1+F && B>=1+E ], cost: 4

     72: f11 -> f11 : A'=E, E'=-1+E, G'=0, H'=free_4, Q'=free_5, J'=1+D, K'=free_3, [ E>=2+D && G==0 && 0>=1+F && E>=1+B ], cost: 4

     73: f11 -> f11 : A'=E, D'=1+D, E'=2+D, G'=1, H'=free_4, Q'=free_5, J'=1+D, K'=free_3, [ G==0 && 0>=1+F && E>=B && B>=E && -1+E==2+D ], cost: 5

     74: f11 -> [10] : A'=E-meter, F'=0, G'=0, H'=free_7, Q'=free_5, J'=2+D+meter, K'=free_3, [ G==0 && F==0 && -1+E>=2+D && 2*meter==-2-D+E && meter>=1 ], cost: NONTERM

     75: f11 -> [11] : A'=-1+E-meter, F'=0, G'=0, H'=free_7, Q'=free_5, J'=2+D+meter, K'=free_3, [ G==0 && F==0 && -1+E>=2+D && 2*meter==-2-D+E && meter>=1 ], cost: NONTERM

     76: f11 -> f11 : A'=-1+F+E, D'=2-F+D, F'=1, G'=1, H'=free_4, Q'=free_5, J'=2-F+D, K'=free_3, [ 2+D-E==0 && G==0 && F==0 && B>=F+E && 2-F+D>=E ], cost: 9-4*F

     77: f11 -> [13] : [ G==0 && F==0 && -1+E>=2+D && 2*meter==-2-D+E && meter>=1 ], cost: 1+4*meter

     78: f11 -> [13] : [ 2+D-E==0 && G==0 && F==0 ], cost: 5-4*F



Accelerating simple loops of location 2.

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

   Accelerating the following rules:

     71: f11 -> f11 : A'=E, D'=1+D, G'=0, H'=free_4, Q'=free_5, J'=1+D, K'=free_3, [ E>=2+D && G==0 && 0>=1+F && B>=1+E ], cost: 4

     72: f11 -> f11 : A'=E, E'=-1+E, G'=0, H'=free_4, Q'=free_5, J'=1+D, K'=free_3, [ E>=2+D && G==0 && 0>=1+F && E>=1+B ], cost: 4

     73: f11 -> f11 : A'=E, D'=1+D, E'=2+D, G'=1, H'=free_4, Q'=free_5, J'=1+D, K'=free_3, [ G==0 && 0>=1+F && -E+B==0 && -1+E==2+D ], cost: 5

     76: f11 -> f11 : A'=-1+F+E, D'=2-F+D, F'=1, G'=1, H'=free_4, Q'=free_5, J'=2-F+D, K'=free_3, [ 2+D-E==0 && G==0 && F==0 && B>=F+E && 2-F+D>=E ], cost: 9-4*F



   Accelerated rule 71 with metering function -1-D+E, yielding the new rule 79.

   Found no metering function for rule 72.

   Accelerated rule 73 with metering function meter_2 (where 4*meter_2==-3-G-D+2*E-B), yielding the new rule 80.

   Accelerated rule 76 with metering function meter_3 (where 4*meter_3==-2-F-G-D+E), yielding the new rule 81.

   Removing the simple loops: 71 73 76.



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

   Start location: f0

      1: f0 -> f11 : B'=10, C'=20, D'=1, E'=20, F'=0, G'=0, [], cost: 1

     69: f11 -> [10] : A'=E, F'=0, G'=0, H'=free_4, Q'=free_5, J'=2+D, K'=free_3, [ E>=2+D && G==0 && F==0 ], cost: NONTERM

     70: f11 -> [11] : A'=-1+E, F'=0, G'=0, H'=free_4, Q'=free_5, J'=2+D, K'=free_3, [ E>=2+D && G==0 && F==0 ], cost: NONTERM

     72: f11 -> f11 : A'=E, E'=-1+E, G'=0, H'=free_4, Q'=free_5, J'=1+D, K'=free_3, [ E>=2+D && G==0 && 0>=1+F && E>=1+B ], cost: 4

     74: f11 -> [10] : A'=E-meter, F'=0, G'=0, H'=free_7, Q'=free_5, J'=2+D+meter, K'=free_3, [ G==0 && F==0 && -1+E>=2+D && 2*meter==-2-D+E && meter>=1 ], cost: NONTERM

     75: f11 -> [11] : A'=-1+E-meter, F'=0, G'=0, H'=free_7, Q'=free_5, J'=2+D+meter, K'=free_3, [ G==0 && F==0 && -1+E>=2+D && 2*meter==-2-D+E && meter>=1 ], cost: NONTERM

     77: f11 -> [13] : [ G==0 && F==0 && -1+E>=2+D && 2*meter==-2-D+E && meter>=1 ], cost: 1+4*meter

     78: f11 -> [13] : [ 2+D-E==0 && G==0 && F==0 ], cost: 5-4*F

     79: f11 -> f11 : A'=E, D'=-1+E, G'=0, H'=free_4, Q'=free_5, J'=-1+E, K'=free_3, [ E>=2+D && G==0 && 0>=1+F && B>=1+E ], cost: -4-4*D+4*E

     80: f11 -> f11 : A'=meter_2+D, D'=meter_2+D, E'=1+meter_2+D, G'=1, H'=free_4, Q'=free_5, J'=meter_2+D, K'=free_3, [ G==0 && 0>=1+F && -E+B==0 && -1+E==2+D && 4*meter_2==-3-G-D+2*E-B && meter_2>=1 ], cost: 5*meter_2

     81: f11 -> f11 : A'=E, D'=1-F+D+meter_3, F'=1, G'=1, H'=free_4, Q'=free_5, J'=1-F+D+meter_3, K'=free_3, [ 2+D-E==0 && G==0 && F==0 && B>=F+E && 2-F+D>=E && 4*meter_3==-2-F-G-D+E && meter_3>=1 ], cost: 5*meter_3



Chained accelerated rules (with incoming rules):

   Start location: f0

      1: f0 -> f11 : B'=10, C'=20, D'=1, E'=20, F'=0, G'=0, [], cost: 1

     69: f11 -> [10] : A'=E, F'=0, G'=0, H'=free_4, Q'=free_5, J'=2+D, K'=free_3, [ E>=2+D && G==0 && F==0 ], cost: NONTERM

     70: f11 -> [11] : A'=-1+E, F'=0, G'=0, H'=free_4, Q'=free_5, J'=2+D, K'=free_3, [ E>=2+D && G==0 && F==0 ], cost: NONTERM

     74: f11 -> [10] : A'=E-meter, F'=0, G'=0, H'=free_7, Q'=free_5, J'=2+D+meter, K'=free_3, [ G==0 && F==0 && -1+E>=2+D && 2*meter==-2-D+E && meter>=1 ], cost: NONTERM

     75: f11 -> [11] : A'=-1+E-meter, F'=0, G'=0, H'=free_7, Q'=free_5, J'=2+D+meter, K'=free_3, [ G==0 && F==0 && -1+E>=2+D && 2*meter==-2-D+E && meter>=1 ], cost: NONTERM

     77: f11 -> [13] : [ G==0 && F==0 && -1+E>=2+D && 2*meter==-2-D+E && meter>=1 ], cost: 1+4*meter

     78: f11 -> [13] : [ 2+D-E==0 && G==0 && F==0 ], cost: 5-4*F



Eliminated locations (on tree-shaped paths):

   Start location: f0

     82: f0 -> [10] : A'=20, B'=10, C'=20, D'=1, E'=20, F'=0, G'=0, H'=free_4, Q'=free_5, J'=3, K'=free_3, [], cost: NONTERM

     83: f0 -> [11] : A'=19, B'=10, C'=20, D'=1, E'=20, F'=0, G'=0, H'=free_4, Q'=free_5, J'=3, K'=free_3, [], cost: NONTERM



Applied pruning (of leafs and parallel rules):

   Start location: f0

     82: f0 -> [10] : A'=20, B'=10, C'=20, D'=1, E'=20, F'=0, G'=0, H'=free_4, Q'=free_5, J'=3, K'=free_3, [], cost: NONTERM

     83: f0 -> [11] : A'=19, B'=10, C'=20, D'=1, E'=20, F'=0, G'=0, H'=free_4, Q'=free_5, J'=3, K'=free_3, [], cost: NONTERM



### Computing asymptotic complexity ###



Fully simplified ITS problem

   Start location: f0

     83: f0 -> [11] : A'=19, B'=10, C'=20, D'=1, E'=20, F'=0, G'=0, H'=free_4, Q'=free_5, J'=3, K'=free_3, [], cost: NONTERM



Computing asymptotic complexity for rule 83

   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)