/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: 48fb2092695e11cc9f56e44b17a92a5f88ffb256 marcel 20180622 unpublished dirty


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

(0) CpxIntTrs
(1) Loat Proof [FINISHED, 3551 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, N, O, P, Q, R) -> Com_1(f13(1, B, C, D, E, F, G, H, I, J, K, L, M, N, O, P, Q, R)) :|: A >= 1 && A <= 1
f0(A, B, C, D, E, F, G, H, I, J, K, L, M, N, O, P, Q, R) -> Com_1(f17(A, 1, C, D, E, F, G, H, I, J, K, L, M, N, O, P, Q, R)) :|: 0 >= A
f0(A, B, C, D, E, F, G, H, I, J, K, L, M, N, O, P, Q, R) -> Com_1(f17(A, 1, C, D, E, F, G, H, I, J, K, L, M, N, O, P, Q, R)) :|: A >= 2
f17(A, B, C, D, E, F, G, H, I, J, K, L, M, N, O, P, Q, R) -> Com_1(f23(A, B, B + 1, S, T, 1, G, H, I, J, K, L, M, N, O, P, Q, R)) :|: A >= B
f23(A, B, C, D, E, F, G, H, I, J, K, L, M, N, O, P, Q, R) -> Com_1(f23(A, B, C, S, T, F + 1, G, H, I, J, K, L, M, N, O, P, Q, R)) :|: B >= F
f33(A, B, C, D, E, F, G, H, I, J, K, L, M, N, O, P, Q, R) -> Com_1(f33(A, B, C, D, E, F + 1, G, H, I, J, K, L, M, N, O, P, Q, R)) :|: B >= F
f46(A, B, C, D, E, F, G, H, I, J, K, L, M, N, O, P, Q, R) -> Com_1(f46(A, B, C, D, E, F + 1, S, T, U, J, K, L, M, N, O, P, Q, R)) :|: B >= F
f60(A, B, C, D, E, F, G, H, I, J, K, L, M, N, O, P, Q, R) -> Com_1(f60(A, B, C, D, E, F + 1, G, H, I, J, K - 1, S, T, U, V, K, Q, R)) :|: J >= F
f60(A, B, C, D, E, F, G, H, I, J, K, L, M, N, O, P, Q, R) -> Com_1(f17(A, B + 1, C, D, E, F, G, H, I, J, K, L, M, N, O, P, Q, R)) :|: F >= 1 + J
f46(A, B, C, D, E, F, G, H, I, J, K, L, M, N, O, P, Q, R) -> Com_1(f60(A, B, C, D, E, 1, G, H, I, S, B, L, M, N, O, P, T, U)) :|: F >= 1 + B
f33(A, B, C, D, E, F, G, H, I, J, K, L, M, N, O, P, Q, R) -> Com_1(f13(A, B, A, D, E, F, G, H, I, J, K, L, M, N, O, P, Q, R)) :|: F >= 1 + B && A >= C && A <= C
f33(A, B, C, D, E, F, G, H, I, J, K, L, M, N, O, P, Q, R) -> Com_1(f46(A, B, C, D, E, 1, S, T, U, J, K, L, M, N, O, P, Q, R)) :|: A >= C + 1 && F >= 1 + B
f33(A, B, C, D, E, F, G, H, I, J, K, L, M, N, O, P, Q, R) -> Com_1(f46(A, B, C, D, E, 1, S, T, U, J, K, L, M, N, O, P, Q, R)) :|: C >= 1 + A && F >= 1 + B
f23(A, B, C, D, E, F, G, H, I, J, K, L, M, N, O, P, Q, R) -> Com_1(f33(A, B, C, D, E, 1, G, H, I, J, K, L, M, N, O, P, Q, R)) :|: 0 >= E + 1 && F >= 1 + B
f23(A, B, C, D, E, F, G, H, I, J, K, L, M, N, O, P, Q, R) -> Com_1(f33(A, B, C, D, E, 1, G, H, I, J, K, L, M, N, O, P, Q, R)) :|: E >= 1 && F >= 1 + B
f23(A, B, C, D, E, F, G, H, I, J, K, L, M, N, O, P, Q, R) -> Com_1(f33(A, B, C, D, 0, 1, G, H, I, J, K, L, M, N, O, P, Q, R)) :|: F >= 1 + B && E >= 0 && E <= 0
f17(A, B, C, D, E, F, G, H, I, J, K, L, M, N, O, P, Q, R) -> Com_1(f13(A, B, C, D, E, F, G, H, I, J, K, L, M, N, O, P, Q, R)) :|: B >= 1 + A

The start-symbols are:[f0_18]


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

(1) Loat Proof (FINISHED)


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



Initial linear ITS problem

   Start location: f0

      0: f0 -> f13 : A'=1, [ A==1 ], cost: 1

      1: f0 -> f17 : B'=1, [ 0>=A ], cost: 1

      2: f0 -> f17 : B'=1, [ A>=2 ], cost: 1

      3: f17 -> f23 : C'=1+B, D'=free, E'=free_1, F'=1, [ A>=B ], cost: 1

     16: f17 -> f13 : [ B>=1+A ], cost: 1

      4: f23 -> f23 : D'=free_2, E'=free_3, F'=1+F, [ B>=F ], cost: 1

     13: f23 -> f33 : F'=1, [ 0>=1+E && F>=1+B ], cost: 1

     14: f23 -> f33 : F'=1, [ E>=1 && F>=1+B ], cost: 1

     15: f23 -> f33 : E'=0, F'=1, [ F>=1+B && E==0 ], cost: 1

      5: f33 -> f33 : F'=1+F, [ B>=F ], cost: 1

     10: f33 -> f13 : C'=A, [ F>=1+B && A==C ], cost: 1

     11: f33 -> f46 : F'=1, G'=free_14, H'=free_15, Q'=free_16, [ A>=1+C && F>=1+B ], cost: 1

     12: f33 -> f46 : F'=1, G'=free_17, H'=free_18, Q'=free_19, [ C>=1+A && F>=1+B ], cost: 1

      6: f46 -> f46 : F'=1+F, G'=free_4, H'=free_5, Q'=free_6, [ B>=F ], cost: 1

      9: f46 -> f60 : F'=1, J'=free_11, K'=B, Q_1'=free_12, R'=free_13, [ F>=1+B ], cost: 1

      7: f60 -> f60 : F'=1+F, K'=-1+K, L'=free_8, M'=free_9, N'=free_10, O'=free_7, P'=K, [ J>=F ], cost: 1

      8: f60 -> f17 : B'=1+B, [ F>=1+J ], cost: 1



Removed unreachable and leaf rules:

   Start location: f0

      1: f0 -> f17 : B'=1, [ 0>=A ], cost: 1

      2: f0 -> f17 : B'=1, [ A>=2 ], cost: 1

      3: f17 -> f23 : C'=1+B, D'=free, E'=free_1, F'=1, [ A>=B ], cost: 1

      4: f23 -> f23 : D'=free_2, E'=free_3, F'=1+F, [ B>=F ], cost: 1

     13: f23 -> f33 : F'=1, [ 0>=1+E && F>=1+B ], cost: 1

     14: f23 -> f33 : F'=1, [ E>=1 && F>=1+B ], cost: 1

     15: f23 -> f33 : E'=0, F'=1, [ F>=1+B && E==0 ], cost: 1

      5: f33 -> f33 : F'=1+F, [ B>=F ], cost: 1

     11: f33 -> f46 : F'=1, G'=free_14, H'=free_15, Q'=free_16, [ A>=1+C && F>=1+B ], cost: 1

     12: f33 -> f46 : F'=1, G'=free_17, H'=free_18, Q'=free_19, [ C>=1+A && F>=1+B ], cost: 1

      6: f46 -> f46 : F'=1+F, G'=free_4, H'=free_5, Q'=free_6, [ B>=F ], cost: 1

      9: f46 -> f60 : F'=1, J'=free_11, K'=B, Q_1'=free_12, R'=free_13, [ F>=1+B ], cost: 1

      7: f60 -> f60 : F'=1+F, K'=-1+K, L'=free_8, M'=free_9, N'=free_10, O'=free_7, P'=K, [ J>=F ], cost: 1

      8: f60 -> f17 : B'=1+B, [ F>=1+J ], cost: 1



### Simplification by acceleration and chaining ###



Accelerating simple loops of location 2.

   Accelerating the following rules:

      4: f23 -> f23 : D'=free_2, E'=free_3, F'=1+F, [ B>=F ], cost: 1



   Accelerated rule 4 with metering function 1-F+B, yielding the new rule 17.

   Removing the simple loops: 4.



Accelerating simple loops of location 3.

   Accelerating the following rules:

      5: f33 -> f33 : F'=1+F, [ B>=F ], cost: 1



   Accelerated rule 5 with metering function 1-F+B, yielding the new rule 18.

   Removing the simple loops: 5.



Accelerating simple loops of location 4.

   Accelerating the following rules:

      6: f46 -> f46 : F'=1+F, G'=free_4, H'=free_5, Q'=free_6, [ B>=F ], cost: 1



   Accelerated rule 6 with metering function 1-F+B, yielding the new rule 19.

   Removing the simple loops: 6.



Accelerating simple loops of location 5.

   Accelerating the following rules:

      7: f60 -> f60 : F'=1+F, K'=-1+K, L'=free_8, M'=free_9, N'=free_10, O'=free_7, P'=K, [ J>=F ], cost: 1



   Accelerated rule 7 with metering function 1-F+J, yielding the new rule 20.

   Removing the simple loops: 7.



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

   Start location: f0

      1: f0 -> f17 : B'=1, [ 0>=A ], cost: 1

      2: f0 -> f17 : B'=1, [ A>=2 ], cost: 1

      3: f17 -> f23 : C'=1+B, D'=free, E'=free_1, F'=1, [ A>=B ], cost: 1

     13: f23 -> f33 : F'=1, [ 0>=1+E && F>=1+B ], cost: 1

     14: f23 -> f33 : F'=1, [ E>=1 && F>=1+B ], cost: 1

     15: f23 -> f33 : E'=0, F'=1, [ F>=1+B && E==0 ], cost: 1

     17: f23 -> f23 : D'=free_2, E'=free_3, F'=1+B, [ B>=F ], cost: 1-F+B

     11: f33 -> f46 : F'=1, G'=free_14, H'=free_15, Q'=free_16, [ A>=1+C && F>=1+B ], cost: 1

     12: f33 -> f46 : F'=1, G'=free_17, H'=free_18, Q'=free_19, [ C>=1+A && F>=1+B ], cost: 1

     18: f33 -> f33 : F'=1+B, [ B>=F ], cost: 1-F+B

      9: f46 -> f60 : F'=1, J'=free_11, K'=B, Q_1'=free_12, R'=free_13, [ F>=1+B ], cost: 1

     19: f46 -> f46 : F'=1+B, G'=free_4, H'=free_5, Q'=free_6, [ B>=F ], cost: 1-F+B

      8: f60 -> f17 : B'=1+B, [ F>=1+J ], cost: 1

     20: f60 -> f60 : F'=1+J, K'=-1+F-J+K, L'=free_8, M'=free_9, N'=free_10, O'=free_7, P'=F-J+K, [ J>=F ], cost: 1-F+J



Chained accelerated rules (with incoming rules):

   Start location: f0

      1: f0 -> f17 : B'=1, [ 0>=A ], cost: 1

      2: f0 -> f17 : B'=1, [ A>=2 ], cost: 1

      3: f17 -> f23 : C'=1+B, D'=free, E'=free_1, F'=1, [ A>=B ], cost: 1

     21: f17 -> f23 : C'=1+B, D'=free_2, E'=free_3, F'=1+B, [ A>=B && B>=1 ], cost: 1+B

     13: f23 -> f33 : F'=1, [ 0>=1+E && F>=1+B ], cost: 1

     14: f23 -> f33 : F'=1, [ E>=1 && F>=1+B ], cost: 1

     15: f23 -> f33 : E'=0, F'=1, [ F>=1+B && E==0 ], cost: 1

     22: f23 -> f33 : F'=1+B, [ 0>=1+E && F>=1+B && B>=1 ], cost: 1+B

     23: f23 -> f33 : F'=1+B, [ E>=1 && F>=1+B && B>=1 ], cost: 1+B

     24: f23 -> f33 : E'=0, F'=1+B, [ F>=1+B && E==0 && B>=1 ], cost: 1+B

     11: f33 -> f46 : F'=1, G'=free_14, H'=free_15, Q'=free_16, [ A>=1+C && F>=1+B ], cost: 1

     12: f33 -> f46 : F'=1, G'=free_17, H'=free_18, Q'=free_19, [ C>=1+A && F>=1+B ], cost: 1

     25: f33 -> f46 : F'=1+B, G'=free_4, H'=free_5, Q'=free_6, [ A>=1+C && F>=1+B && B>=1 ], cost: 1+B

     26: f33 -> f46 : F'=1+B, G'=free_4, H'=free_5, Q'=free_6, [ C>=1+A && F>=1+B && B>=1 ], cost: 1+B

      9: f46 -> f60 : F'=1, J'=free_11, K'=B, Q_1'=free_12, R'=free_13, [ F>=1+B ], cost: 1

     27: f46 -> f60 : F'=1+free_11, J'=free_11, K'=-free_11+B, L'=free_8, M'=free_9, N'=free_10, O'=free_7, P'=1-free_11+B, Q_1'=free_12, R'=free_13, [ F>=1+B && free_11>=1 ], cost: 1+free_11

      8: f60 -> f17 : B'=1+B, [ F>=1+J ], cost: 1



Eliminated locations (on tree-shaped paths):

   Start location: f0

      1: f0 -> f17 : B'=1, [ 0>=A ], cost: 1

      2: f0 -> f17 : B'=1, [ A>=2 ], cost: 1

     28: f17 -> f33 : C'=1+B, D'=free, E'=free_1, F'=1, [ A>=B && 0>=1+free_1 && 1>=1+B ], cost: 2

     29: f17 -> f33 : C'=1+B, D'=free, E'=free_1, F'=1, [ A>=B && free_1>=1 && 1>=1+B ], cost: 2

     30: f17 -> f33 : C'=1+B, D'=free, E'=0, F'=1, [ A>=B && 1>=1+B && free_1==0 ], cost: 2

     31: f17 -> f33 : C'=1+B, D'=free_2, E'=free_3, F'=1, [ A>=B && B>=1 && 0>=1+free_3 ], cost: 2+B

     32: f17 -> f33 : C'=1+B, D'=free_2, E'=free_3, F'=1, [ A>=B && B>=1 && free_3>=1 ], cost: 2+B

     33: f17 -> f33 : C'=1+B, D'=free_2, E'=0, F'=1, [ A>=B && B>=1 && free_3==0 ], cost: 2+B

     34: f17 -> f33 : C'=1+B, D'=free_2, E'=free_3, F'=1+B, [ A>=B && B>=1 && 0>=1+free_3 ], cost: 2+2*B

     35: f17 -> f33 : C'=1+B, D'=free_2, E'=free_3, F'=1+B, [ A>=B && B>=1 && free_3>=1 ], cost: 2+2*B

     36: f17 -> f33 : C'=1+B, D'=free_2, E'=0, F'=1+B, [ A>=B && B>=1 && free_3==0 ], cost: 2+2*B

     37: f33 -> f60 : F'=1, G'=free_14, H'=free_15, Q'=free_16, J'=free_11, K'=B, Q_1'=free_12, R'=free_13, [ A>=1+C && F>=1+B && 1>=1+B ], cost: 2

     38: f33 -> f60 : F'=1+free_11, G'=free_14, H'=free_15, Q'=free_16, J'=free_11, K'=-free_11+B, L'=free_8, M'=free_9, N'=free_10, O'=free_7, P'=1-free_11+B, Q_1'=free_12, R'=free_13, [ A>=1+C && F>=1+B && 1>=1+B && free_11>=1 ], cost: 2+free_11

     39: f33 -> f60 : F'=1, G'=free_17, H'=free_18, Q'=free_19, J'=free_11, K'=B, Q_1'=free_12, R'=free_13, [ C>=1+A && F>=1+B && 1>=1+B ], cost: 2

     40: f33 -> f60 : F'=1+free_11, G'=free_17, H'=free_18, Q'=free_19, J'=free_11, K'=-free_11+B, L'=free_8, M'=free_9, N'=free_10, O'=free_7, P'=1-free_11+B, Q_1'=free_12, R'=free_13, [ C>=1+A && F>=1+B && 1>=1+B && free_11>=1 ], cost: 2+free_11

     41: f33 -> f60 : F'=1, G'=free_4, H'=free_5, Q'=free_6, J'=free_11, K'=B, Q_1'=free_12, R'=free_13, [ A>=1+C && F>=1+B && B>=1 ], cost: 2+B

     42: f33 -> f60 : F'=1+free_11, G'=free_4, H'=free_5, Q'=free_6, J'=free_11, K'=-free_11+B, L'=free_8, M'=free_9, N'=free_10, O'=free_7, P'=1-free_11+B, Q_1'=free_12, R'=free_13, [ A>=1+C && F>=1+B && B>=1 && free_11>=1 ], cost: 2+free_11+B

     43: f33 -> f60 : F'=1, G'=free_4, H'=free_5, Q'=free_6, J'=free_11, K'=B, Q_1'=free_12, R'=free_13, [ C>=1+A && F>=1+B && B>=1 ], cost: 2+B

     44: f33 -> f60 : F'=1+free_11, G'=free_4, H'=free_5, Q'=free_6, J'=free_11, K'=-free_11+B, L'=free_8, M'=free_9, N'=free_10, O'=free_7, P'=1-free_11+B, Q_1'=free_12, R'=free_13, [ C>=1+A && F>=1+B && B>=1 && free_11>=1 ], cost: 2+free_11+B

      8: f60 -> f17 : B'=1+B, [ F>=1+J ], cost: 1



Applied pruning (of leafs and parallel rules):

   Start location: f0

      1: f0 -> f17 : B'=1, [ 0>=A ], cost: 1

      2: f0 -> f17 : B'=1, [ A>=2 ], cost: 1

     31: f17 -> f33 : C'=1+B, D'=free_2, E'=free_3, F'=1, [ A>=B && B>=1 && 0>=1+free_3 ], cost: 2+B

     32: f17 -> f33 : C'=1+B, D'=free_2, E'=free_3, F'=1, [ A>=B && B>=1 && free_3>=1 ], cost: 2+B

     33: f17 -> f33 : C'=1+B, D'=free_2, E'=0, F'=1, [ A>=B && B>=1 && free_3==0 ], cost: 2+B

     34: f17 -> f33 : C'=1+B, D'=free_2, E'=free_3, F'=1+B, [ A>=B && B>=1 && 0>=1+free_3 ], cost: 2+2*B

     35: f17 -> f33 : C'=1+B, D'=free_2, E'=free_3, F'=1+B, [ A>=B && B>=1 && free_3>=1 ], cost: 2+2*B

     38: f33 -> f60 : F'=1+free_11, G'=free_14, H'=free_15, Q'=free_16, J'=free_11, K'=-free_11+B, L'=free_8, M'=free_9, N'=free_10, O'=free_7, P'=1-free_11+B, Q_1'=free_12, R'=free_13, [ A>=1+C && F>=1+B && 1>=1+B && free_11>=1 ], cost: 2+free_11

     40: f33 -> f60 : F'=1+free_11, G'=free_17, H'=free_18, Q'=free_19, J'=free_11, K'=-free_11+B, L'=free_8, M'=free_9, N'=free_10, O'=free_7, P'=1-free_11+B, Q_1'=free_12, R'=free_13, [ C>=1+A && F>=1+B && 1>=1+B && free_11>=1 ], cost: 2+free_11

     42: f33 -> f60 : F'=1+free_11, G'=free_4, H'=free_5, Q'=free_6, J'=free_11, K'=-free_11+B, L'=free_8, M'=free_9, N'=free_10, O'=free_7, P'=1-free_11+B, Q_1'=free_12, R'=free_13, [ A>=1+C && F>=1+B && B>=1 && free_11>=1 ], cost: 2+free_11+B

     43: f33 -> f60 : F'=1, G'=free_4, H'=free_5, Q'=free_6, J'=free_11, K'=B, Q_1'=free_12, R'=free_13, [ C>=1+A && F>=1+B && B>=1 ], cost: 2+B

     44: f33 -> f60 : F'=1+free_11, G'=free_4, H'=free_5, Q'=free_6, J'=free_11, K'=-free_11+B, L'=free_8, M'=free_9, N'=free_10, O'=free_7, P'=1-free_11+B, Q_1'=free_12, R'=free_13, [ C>=1+A && F>=1+B && B>=1 && free_11>=1 ], cost: 2+free_11+B

      8: f60 -> f17 : B'=1+B, [ F>=1+J ], cost: 1



Eliminated locations (on tree-shaped paths):

   Start location: f0

      1: f0 -> f17 : B'=1, [ 0>=A ], cost: 1

      2: f0 -> f17 : B'=1, [ A>=2 ], cost: 1

     45: f17 -> f60 : C'=1+B, D'=free_2, E'=free_3, F'=1+free_11, G'=free_4, H'=free_5, Q'=free_6, J'=free_11, K'=-free_11+B, L'=free_8, M'=free_9, N'=free_10, O'=free_7, P'=1-free_11+B, Q_1'=free_12, R'=free_13, [ B>=1 && 0>=1+free_3 && A>=2+B && free_11>=1 ], cost: 4+free_11+3*B

     46: f17 -> f60 : C'=1+B, D'=free_2, E'=free_3, F'=1, G'=free_4, H'=free_5, Q'=free_6, J'=free_11, K'=B, Q_1'=free_12, R'=free_13, [ A>=B && B>=1 && 0>=1+free_3 && 1+B>=1+A ], cost: 4+3*B

     47: f17 -> f60 : C'=1+B, D'=free_2, E'=free_3, F'=1+free_11, G'=free_4, H'=free_5, Q'=free_6, J'=free_11, K'=-free_11+B, L'=free_8, M'=free_9, N'=free_10, O'=free_7, P'=1-free_11+B, Q_1'=free_12, R'=free_13, [ A>=B && B>=1 && 0>=1+free_3 && 1+B>=1+A && free_11>=1 ], cost: 4+free_11+3*B

     48: f17 -> f60 : C'=1+B, D'=free_2, E'=free_3, F'=1+free_11, G'=free_4, H'=free_5, Q'=free_6, J'=free_11, K'=-free_11+B, L'=free_8, M'=free_9, N'=free_10, O'=free_7, P'=1-free_11+B, Q_1'=free_12, R'=free_13, [ B>=1 && free_3>=1 && A>=2+B && free_11>=1 ], cost: 4+free_11+3*B

     49: f17 -> f60 : C'=1+B, D'=free_2, E'=free_3, F'=1, G'=free_4, H'=free_5, Q'=free_6, J'=free_11, K'=B, Q_1'=free_12, R'=free_13, [ A>=B && B>=1 && free_3>=1 && 1+B>=1+A ], cost: 4+3*B

     50: f17 -> f60 : C'=1+B, D'=free_2, E'=free_3, F'=1+free_11, G'=free_4, H'=free_5, Q'=free_6, J'=free_11, K'=-free_11+B, L'=free_8, M'=free_9, N'=free_10, O'=free_7, P'=1-free_11+B, Q_1'=free_12, R'=free_13, [ A>=B && B>=1 && free_3>=1 && 1+B>=1+A && free_11>=1 ], cost: 4+free_11+3*B

     51: f17 -> [11] : [ A>=B && B>=1 && 0>=1+free_3 ], cost: 2+B

     52: f17 -> [11] : [ A>=B && B>=1 && free_3>=1 ], cost: 2+B

     53: f17 -> [11] : [ A>=B && B>=1 && free_3==0 ], cost: 2+B

     54: f17 -> [11] : [ A>=B && B>=1 && 0>=1+free_3 ], cost: 2+2*B

     55: f17 -> [11] : [ A>=B && B>=1 && free_3>=1 ], cost: 2+2*B

      8: f60 -> f17 : B'=1+B, [ F>=1+J ], cost: 1



Applied pruning (of leafs and parallel rules):

   Start location: f0

      1: f0 -> f17 : B'=1, [ 0>=A ], cost: 1

      2: f0 -> f17 : B'=1, [ A>=2 ], cost: 1

     45: f17 -> f60 : C'=1+B, D'=free_2, E'=free_3, F'=1+free_11, G'=free_4, H'=free_5, Q'=free_6, J'=free_11, K'=-free_11+B, L'=free_8, M'=free_9, N'=free_10, O'=free_7, P'=1-free_11+B, Q_1'=free_12, R'=free_13, [ B>=1 && 0>=1+free_3 && A>=2+B && free_11>=1 ], cost: 4+free_11+3*B

     47: f17 -> f60 : C'=1+B, D'=free_2, E'=free_3, F'=1+free_11, G'=free_4, H'=free_5, Q'=free_6, J'=free_11, K'=-free_11+B, L'=free_8, M'=free_9, N'=free_10, O'=free_7, P'=1-free_11+B, Q_1'=free_12, R'=free_13, [ A>=B && B>=1 && 0>=1+free_3 && 1+B>=1+A && free_11>=1 ], cost: 4+free_11+3*B

     48: f17 -> f60 : C'=1+B, D'=free_2, E'=free_3, F'=1+free_11, G'=free_4, H'=free_5, Q'=free_6, J'=free_11, K'=-free_11+B, L'=free_8, M'=free_9, N'=free_10, O'=free_7, P'=1-free_11+B, Q_1'=free_12, R'=free_13, [ B>=1 && free_3>=1 && A>=2+B && free_11>=1 ], cost: 4+free_11+3*B

     49: f17 -> f60 : C'=1+B, D'=free_2, E'=free_3, F'=1, G'=free_4, H'=free_5, Q'=free_6, J'=free_11, K'=B, Q_1'=free_12, R'=free_13, [ A>=B && B>=1 && free_3>=1 && 1+B>=1+A ], cost: 4+3*B

     50: f17 -> f60 : C'=1+B, D'=free_2, E'=free_3, F'=1+free_11, G'=free_4, H'=free_5, Q'=free_6, J'=free_11, K'=-free_11+B, L'=free_8, M'=free_9, N'=free_10, O'=free_7, P'=1-free_11+B, Q_1'=free_12, R'=free_13, [ A>=B && B>=1 && free_3>=1 && 1+B>=1+A && free_11>=1 ], cost: 4+free_11+3*B

     51: f17 -> [11] : [ A>=B && B>=1 && 0>=1+free_3 ], cost: 2+B

     52: f17 -> [11] : [ A>=B && B>=1 && free_3>=1 ], cost: 2+B

     53: f17 -> [11] : [ A>=B && B>=1 && free_3==0 ], cost: 2+B

     54: f17 -> [11] : [ A>=B && B>=1 && 0>=1+free_3 ], cost: 2+2*B

     55: f17 -> [11] : [ A>=B && B>=1 && free_3>=1 ], cost: 2+2*B

      8: f60 -> f17 : B'=1+B, [ F>=1+J ], cost: 1



Eliminated locations (on tree-shaped paths):

   Start location: f0

      1: f0 -> f17 : B'=1, [ 0>=A ], cost: 1

      2: f0 -> f17 : B'=1, [ A>=2 ], cost: 1

     51: f17 -> [11] : [ A>=B && B>=1 && 0>=1+free_3 ], cost: 2+B

     52: f17 -> [11] : [ A>=B && B>=1 && free_3>=1 ], cost: 2+B

     53: f17 -> [11] : [ A>=B && B>=1 && free_3==0 ], cost: 2+B

     54: f17 -> [11] : [ A>=B && B>=1 && 0>=1+free_3 ], cost: 2+2*B

     55: f17 -> [11] : [ A>=B && B>=1 && free_3>=1 ], cost: 2+2*B

     56: f17 -> f17 : B'=1+B, C'=1+B, D'=free_2, E'=free_3, F'=1+free_11, G'=free_4, H'=free_5, Q'=free_6, J'=free_11, K'=-free_11+B, L'=free_8, M'=free_9, N'=free_10, O'=free_7, P'=1-free_11+B, Q_1'=free_12, R'=free_13, [ B>=1 && 0>=1+free_3 && A>=2+B && free_11>=1 ], cost: 5+free_11+3*B

     57: f17 -> f17 : B'=1+B, C'=1+B, D'=free_2, E'=free_3, F'=1+free_11, G'=free_4, H'=free_5, Q'=free_6, J'=free_11, K'=-free_11+B, L'=free_8, M'=free_9, N'=free_10, O'=free_7, P'=1-free_11+B, Q_1'=free_12, R'=free_13, [ A>=B && B>=1 && 0>=1+free_3 && 1+B>=1+A && free_11>=1 ], cost: 5+free_11+3*B

     58: f17 -> f17 : B'=1+B, C'=1+B, D'=free_2, E'=free_3, F'=1+free_11, G'=free_4, H'=free_5, Q'=free_6, J'=free_11, K'=-free_11+B, L'=free_8, M'=free_9, N'=free_10, O'=free_7, P'=1-free_11+B, Q_1'=free_12, R'=free_13, [ B>=1 && free_3>=1 && A>=2+B && free_11>=1 ], cost: 5+free_11+3*B

     59: f17 -> f17 : B'=1+B, C'=1+B, D'=free_2, E'=free_3, F'=1, G'=free_4, H'=free_5, Q'=free_6, J'=free_11, K'=B, Q_1'=free_12, R'=free_13, [ A>=B && B>=1 && free_3>=1 && 1+B>=1+A && 1>=1+free_11 ], cost: 5+3*B

     60: f17 -> f17 : B'=1+B, C'=1+B, D'=free_2, E'=free_3, F'=1+free_11, G'=free_4, H'=free_5, Q'=free_6, J'=free_11, K'=-free_11+B, L'=free_8, M'=free_9, N'=free_10, O'=free_7, P'=1-free_11+B, Q_1'=free_12, R'=free_13, [ A>=B && B>=1 && free_3>=1 && 1+B>=1+A && free_11>=1 ], cost: 5+free_11+3*B



Accelerating simple loops of location 1.

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

   Accelerating the following rules:

     56: f17 -> f17 : B'=1+B, C'=1+B, D'=free_2, E'=free_3, F'=1+free_11, G'=free_4, H'=free_5, Q'=free_6, J'=free_11, K'=-free_11+B, L'=free_8, M'=free_9, N'=free_10, O'=free_7, P'=1-free_11+B, Q_1'=free_12, R'=free_13, [ B>=1 && 0>=1+free_3 && A>=2+B && free_11>=1 ], cost: 5+free_11+3*B

     57: f17 -> f17 : B'=1+B, C'=1+B, D'=free_2, E'=free_3, F'=1+free_11, G'=free_4, H'=free_5, Q'=free_6, J'=free_11, K'=-free_11+B, L'=free_8, M'=free_9, N'=free_10, O'=free_7, P'=1-free_11+B, Q_1'=free_12, R'=free_13, [ -A+B==0 && B>=1 && 0>=1+free_3 && free_11>=1 ], cost: 5+free_11+3*B

     58: f17 -> f17 : B'=1+B, C'=1+B, D'=free_2, E'=free_3, F'=1+free_11, G'=free_4, H'=free_5, Q'=free_6, J'=free_11, K'=-free_11+B, L'=free_8, M'=free_9, N'=free_10, O'=free_7, P'=1-free_11+B, Q_1'=free_12, R'=free_13, [ B>=1 && free_3>=1 && A>=2+B && free_11>=1 ], cost: 5+free_11+3*B

     59: f17 -> f17 : B'=1+B, C'=1+B, D'=free_2, E'=free_3, F'=1, G'=free_4, H'=free_5, Q'=free_6, J'=free_11, K'=B, Q_1'=free_12, R'=free_13, [ -A+B==0 && B>=1 && free_3>=1 && 1>=1+free_11 ], cost: 5+3*B

     60: f17 -> f17 : B'=1+B, C'=1+B, D'=free_2, E'=free_3, F'=1+free_11, G'=free_4, H'=free_5, Q'=free_6, J'=free_11, K'=-free_11+B, L'=free_8, M'=free_9, N'=free_10, O'=free_7, P'=1-free_11+B, Q_1'=free_12, R'=free_13, [ -A+B==0 && B>=1 && free_3>=1 && free_11>=1 ], cost: 5+free_11+3*B



   Accelerated rule 56 with metering function -1+A-B, yielding the new rule 61.

   Accelerated rule 57 with metering function 1+A-B, yielding the new rule 62.

   Accelerated rule 58 with metering function -1+A-B, yielding the new rule 63.

   Accelerated rule 59 with metering function 1+A-B, yielding the new rule 64.

   Accelerated rule 60 with metering function 1+A-B, yielding the new rule 65.

   Removing the simple loops: 56 57 58 59 60.



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

   Start location: f0

      1: f0 -> f17 : B'=1, [ 0>=A ], cost: 1

      2: f0 -> f17 : B'=1, [ A>=2 ], cost: 1

     51: f17 -> [11] : [ A>=B && B>=1 && 0>=1+free_3 ], cost: 2+B

     52: f17 -> [11] : [ A>=B && B>=1 && free_3>=1 ], cost: 2+B

     53: f17 -> [11] : [ A>=B && B>=1 && free_3==0 ], cost: 2+B

     54: f17 -> [11] : [ A>=B && B>=1 && 0>=1+free_3 ], cost: 2+2*B

     55: f17 -> [11] : [ A>=B && B>=1 && free_3>=1 ], cost: 2+2*B

     61: f17 -> f17 : B'=-1+A, C'=-1+A, D'=free_2, E'=free_3, F'=1+free_11, G'=free_4, H'=free_5, Q'=free_6, J'=free_11, K'=-2-free_11+A, L'=free_8, M'=free_9, N'=free_10, O'=free_7, P'=-1-free_11+A, Q_1'=free_12, R'=free_13, [ B>=1 && 0>=1+free_3 && A>=2+B && free_11>=1 ], cost: -7/2+free_11*(-1+A-B)+7/2*A+3*(-1+A-B)*B+3/2*(-1+A-B)^2-7/2*B

     62: f17 -> f17 : B'=1+A, C'=1+A, D'=free_2, E'=free_3, F'=1+free_11, G'=free_4, H'=free_5, Q'=free_6, J'=free_11, K'=-free_11+A, L'=free_8, M'=free_9, N'=free_10, O'=free_7, P'=1-free_11+A, Q_1'=free_12, R'=free_13, [ -A+B==0 && B>=1 && 0>=1+free_3 && free_11>=1 ], cost: 7/2+free_11*(1+A-B)+3/2*(1+A-B)^2+7/2*A+3*(1+A-B)*B-7/2*B

     63: f17 -> f17 : B'=-1+A, C'=-1+A, D'=free_2, E'=free_3, F'=1+free_11, G'=free_4, H'=free_5, Q'=free_6, J'=free_11, K'=-2-free_11+A, L'=free_8, M'=free_9, N'=free_10, O'=free_7, P'=-1-free_11+A, Q_1'=free_12, R'=free_13, [ B>=1 && free_3>=1 && A>=2+B && free_11>=1 ], cost: -7/2+free_11*(-1+A-B)+7/2*A+3*(-1+A-B)*B+3/2*(-1+A-B)^2-7/2*B

     64: f17 -> f17 : B'=1+A, C'=1+A, D'=free_2, E'=free_3, F'=1, G'=free_4, H'=free_5, Q'=free_6, J'=free_11, K'=A, Q_1'=free_12, R'=free_13, [ -A+B==0 && B>=1 && free_3>=1 && 1>=1+free_11 ], cost: 7/2+3/2*(1+A-B)^2+7/2*A+3*(1+A-B)*B-7/2*B

     65: f17 -> f17 : B'=1+A, C'=1+A, D'=free_2, E'=free_3, F'=1+free_11, G'=free_4, H'=free_5, Q'=free_6, J'=free_11, K'=-free_11+A, L'=free_8, M'=free_9, N'=free_10, O'=free_7, P'=1-free_11+A, Q_1'=free_12, R'=free_13, [ -A+B==0 && B>=1 && free_3>=1 && free_11>=1 ], cost: 7/2+free_11*(1+A-B)+3/2*(1+A-B)^2+7/2*A+3*(1+A-B)*B-7/2*B



Chained accelerated rules (with incoming rules):

   Start location: f0

      1: f0 -> f17 : B'=1, [ 0>=A ], cost: 1

      2: f0 -> f17 : B'=1, [ A>=2 ], cost: 1

     66: f0 -> f17 : B'=-1+A, C'=-1+A, D'=free_2, E'=free_3, F'=1+free_11, G'=free_4, H'=free_5, Q'=free_6, J'=free_11, K'=-2-free_11+A, L'=free_8, M'=free_9, N'=free_10, O'=free_7, P'=-1-free_11+A, Q_1'=free_12, R'=free_13, [ 0>=1+free_3 && A>=3 && free_11>=1 ], cost: -12+3/2*(-2+A)^2+free_11*(-2+A)+13/2*A

     67: f0 -> f17 : B'=-1+A, C'=-1+A, D'=free_2, E'=free_3, F'=1+free_11, G'=free_4, H'=free_5, Q'=free_6, J'=free_11, K'=-2-free_11+A, L'=free_8, M'=free_9, N'=free_10, O'=free_7, P'=-1-free_11+A, Q_1'=free_12, R'=free_13, [ free_3>=1 && A>=3 && free_11>=1 ], cost: -12+3/2*(-2+A)^2+free_11*(-2+A)+13/2*A

     51: f17 -> [11] : [ A>=B && B>=1 && 0>=1+free_3 ], cost: 2+B

     52: f17 -> [11] : [ A>=B && B>=1 && free_3>=1 ], cost: 2+B

     53: f17 -> [11] : [ A>=B && B>=1 && free_3==0 ], cost: 2+B

     54: f17 -> [11] : [ A>=B && B>=1 && 0>=1+free_3 ], cost: 2+2*B

     55: f17 -> [11] : [ A>=B && B>=1 && free_3>=1 ], cost: 2+2*B



Eliminated locations (on tree-shaped paths):

   Start location: f0

     68: f0 -> [11] : B'=1, [ A>=2 && 0>=1+free_3 ], cost: 4

     69: f0 -> [11] : B'=1, [ A>=2 && free_3>=1 ], cost: 4

     70: f0 -> [11] : B'=1, [ A>=2 && free_3==0 ], cost: 4

     71: f0 -> [11] : B'=1, [ A>=2 && 0>=1+free_3 ], cost: 5

     72: f0 -> [11] : B'=1, [ A>=2 && free_3>=1 ], cost: 5

     73: f0 -> [11] : B'=-1+A, C'=-1+A, D'=free_2, E'=free_3, F'=1+free_11, G'=free_4, H'=free_5, Q'=free_6, J'=free_11, K'=-2-free_11+A, L'=free_8, M'=free_9, N'=free_10, O'=free_7, P'=-1-free_11+A, Q_1'=free_12, R'=free_13, [ 0>=1+free_3 && A>=3 && free_11>=1 ], cost: -11+3/2*(-2+A)^2+free_11*(-2+A)+15/2*A

     74: f0 -> [11] : B'=-1+A, C'=-1+A, D'=free_2, E'=free_3, F'=1+free_11, G'=free_4, H'=free_5, Q'=free_6, J'=free_11, K'=-2-free_11+A, L'=free_8, M'=free_9, N'=free_10, O'=free_7, P'=-1-free_11+A, Q_1'=free_12, R'=free_13, [ 0>=1+free_3 && A>=3 && free_11>=1 ], cost: -12+3/2*(-2+A)^2+free_11*(-2+A)+17/2*A

     75: f0 -> [11] : B'=-1+A, C'=-1+A, D'=free_2, E'=free_3, F'=1+free_11, G'=free_4, H'=free_5, Q'=free_6, J'=free_11, K'=-2-free_11+A, L'=free_8, M'=free_9, N'=free_10, O'=free_7, P'=-1-free_11+A, Q_1'=free_12, R'=free_13, [ free_3>=1 && A>=3 && free_11>=1 ], cost: -11+3/2*(-2+A)^2+free_11*(-2+A)+15/2*A

     76: f0 -> [11] : B'=-1+A, C'=-1+A, D'=free_2, E'=free_3, F'=1+free_11, G'=free_4, H'=free_5, Q'=free_6, J'=free_11, K'=-2-free_11+A, L'=free_8, M'=free_9, N'=free_10, O'=free_7, P'=-1-free_11+A, Q_1'=free_12, R'=free_13, [ free_3>=1 && A>=3 && free_11>=1 ], cost: -12+3/2*(-2+A)^2+free_11*(-2+A)+17/2*A

     77: f0 -> [13] : [ 0>=1+free_3 && A>=3 && free_11>=1 ], cost: -12+3/2*(-2+A)^2+free_11*(-2+A)+13/2*A

     78: f0 -> [13] : [ free_3>=1 && A>=3 && free_11>=1 ], cost: -12+3/2*(-2+A)^2+free_11*(-2+A)+13/2*A



Applied pruning (of leafs and parallel rules):

   Start location: f0

     73: f0 -> [11] : B'=-1+A, C'=-1+A, D'=free_2, E'=free_3, F'=1+free_11, G'=free_4, H'=free_5, Q'=free_6, J'=free_11, K'=-2-free_11+A, L'=free_8, M'=free_9, N'=free_10, O'=free_7, P'=-1-free_11+A, Q_1'=free_12, R'=free_13, [ 0>=1+free_3 && A>=3 && free_11>=1 ], cost: -11+3/2*(-2+A)^2+free_11*(-2+A)+15/2*A

     74: f0 -> [11] : B'=-1+A, C'=-1+A, D'=free_2, E'=free_3, F'=1+free_11, G'=free_4, H'=free_5, Q'=free_6, J'=free_11, K'=-2-free_11+A, L'=free_8, M'=free_9, N'=free_10, O'=free_7, P'=-1-free_11+A, Q_1'=free_12, R'=free_13, [ 0>=1+free_3 && A>=3 && free_11>=1 ], cost: -12+3/2*(-2+A)^2+free_11*(-2+A)+17/2*A

     75: f0 -> [11] : B'=-1+A, C'=-1+A, D'=free_2, E'=free_3, F'=1+free_11, G'=free_4, H'=free_5, Q'=free_6, J'=free_11, K'=-2-free_11+A, L'=free_8, M'=free_9, N'=free_10, O'=free_7, P'=-1-free_11+A, Q_1'=free_12, R'=free_13, [ free_3>=1 && A>=3 && free_11>=1 ], cost: -11+3/2*(-2+A)^2+free_11*(-2+A)+15/2*A

     76: f0 -> [11] : B'=-1+A, C'=-1+A, D'=free_2, E'=free_3, F'=1+free_11, G'=free_4, H'=free_5, Q'=free_6, J'=free_11, K'=-2-free_11+A, L'=free_8, M'=free_9, N'=free_10, O'=free_7, P'=-1-free_11+A, Q_1'=free_12, R'=free_13, [ free_3>=1 && A>=3 && free_11>=1 ], cost: -12+3/2*(-2+A)^2+free_11*(-2+A)+17/2*A

     77: f0 -> [13] : [ 0>=1+free_3 && A>=3 && free_11>=1 ], cost: -12+3/2*(-2+A)^2+free_11*(-2+A)+13/2*A

     78: f0 -> [13] : [ free_3>=1 && A>=3 && free_11>=1 ], cost: -12+3/2*(-2+A)^2+free_11*(-2+A)+13/2*A



### Computing asymptotic complexity ###



Fully simplified ITS problem

   Start location: f0

     73: f0 -> [11] : B'=-1+A, C'=-1+A, D'=free_2, E'=free_3, F'=1+free_11, G'=free_4, H'=free_5, Q'=free_6, J'=free_11, K'=-2-free_11+A, L'=free_8, M'=free_9, N'=free_10, O'=free_7, P'=-1-free_11+A, Q_1'=free_12, R'=free_13, [ 0>=1+free_3 && A>=3 && free_11>=1 ], cost: -11+3/2*(-2+A)^2+free_11*(-2+A)+15/2*A

     74: f0 -> [11] : B'=-1+A, C'=-1+A, D'=free_2, E'=free_3, F'=1+free_11, G'=free_4, H'=free_5, Q'=free_6, J'=free_11, K'=-2-free_11+A, L'=free_8, M'=free_9, N'=free_10, O'=free_7, P'=-1-free_11+A, Q_1'=free_12, R'=free_13, [ 0>=1+free_3 && A>=3 && free_11>=1 ], cost: -12+3/2*(-2+A)^2+free_11*(-2+A)+17/2*A

     75: f0 -> [11] : B'=-1+A, C'=-1+A, D'=free_2, E'=free_3, F'=1+free_11, G'=free_4, H'=free_5, Q'=free_6, J'=free_11, K'=-2-free_11+A, L'=free_8, M'=free_9, N'=free_10, O'=free_7, P'=-1-free_11+A, Q_1'=free_12, R'=free_13, [ free_3>=1 && A>=3 && free_11>=1 ], cost: -11+3/2*(-2+A)^2+free_11*(-2+A)+15/2*A

     76: f0 -> [11] : B'=-1+A, C'=-1+A, D'=free_2, E'=free_3, F'=1+free_11, G'=free_4, H'=free_5, Q'=free_6, J'=free_11, K'=-2-free_11+A, L'=free_8, M'=free_9, N'=free_10, O'=free_7, P'=-1-free_11+A, Q_1'=free_12, R'=free_13, [ free_3>=1 && A>=3 && free_11>=1 ], cost: -12+3/2*(-2+A)^2+free_11*(-2+A)+17/2*A

     77: f0 -> [13] : [ 0>=1+free_3 && A>=3 && free_11>=1 ], cost: -12+3/2*(-2+A)^2+free_11*(-2+A)+13/2*A

     78: f0 -> [13] : [ free_3>=1 && A>=3 && free_11>=1 ], cost: -12+3/2*(-2+A)^2+free_11*(-2+A)+13/2*A



Computing asymptotic complexity for rule 73

   Solved the limit problem by the following transformations:

      Created initial limit problem:

      -5-2*free_11+free_11*A+3/2*A+3/2*A^2 (+), free_11 (+/+!), -free_3 (+/+!), -2+A (+/+!) [not solved]



      removing all constraints (solved by SMT)

      resulting limit problem: [solved]



      applying transformation rule (C) using substitution {free_11==1+n,free_3==-1,A==3}

      resulting limit problem:

      [solved]



   Solution:

      free_11 / 1+n

      free_3 / -1

      A / 3

   Resulting cost 14+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: 14+n

   Rule cost:   -11+3/2*(-2+A)^2+free_11*(-2+A)+15/2*A

   Rule guard:  [ 0>=1+free_3 && A>=3 && free_11>=1 ]



WORST_CASE(INF,?)


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

(2)
BOUNDS(INF, INF)