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


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

(0)
Obligation:
Complexity Int TRS consisting of the following rules:
f2(A, B, C, D, E, F, G, H, I, J, K, L, M, N, O, P, Q, R, S, T, U, V, W) -> Com_1(f1(X, X, X, X, X, X, X, X, X, J, K, L, M, N, O, P, Q, R, S, T, U, V, W)) :|: TRUE
f1(A, B, C, D, E, F, G, H, I, J, K, L, M, N, O, P, Q, R, S, T, U, V, W) -> Com_1(f1(A, B, C, D, E, F, G, H, I, J, X, Z, A1, B1, C1, D1, Q, R, S, T, U, V, W)) :|: 0 >= Y && 0 >= J + 1
f1(A, B, C, D, E, F, G, H, I, J, K, L, M, N, O, P, Q, R, S, T, U, V, W) -> Com_1(f1(A, B, C, D, E, F, G, H, I, J, X, Z, A1, B1, O, P, C1, D1, Y, T, U, V, W)) :|: 0 >= J + 1 && E1 >= 1 && F1 >= 2
f1(A, B, C, D, E, F, G, H, I, J, K, L, M, N, O, P, Q, R, S, T, U, V, W) -> Com_1(f1(A, B, C, D, E, F, G, H, I, J, X, L, M, Z, A1, B1, Q, R, S, C1, D1, Y, W)) :|: 0 >= 2 + E1 && J >= 1
f1(A, B, C, D, E, F, G, H, I, J, K, L, M, N, O, P, Q, R, S, T, U, V, W) -> Com_1(f1(A, B, C, D, E, F, G, H, I, J, X, L, M, Z, O, P, A1, B1, C1, D1, Y, E1, W)) :|: J >= 1 && F1 >= 0 && G1 + 1 >= 0
f1(A, B, C, D, E, F, G, H, I, J, K, L, M, N, O, P, Q, R, S, T, U, V, W) -> Com_1(f300(A, B, C, D, E, F, G, H, I, J, X, Z, A1, B1, O, P, C1, R, S, T, U, V, D1)) :|: 1 >= Y && 0 >= J + 1 && E1 >= 1
f1(A, B, C, D, E, F, G, H, I, J, K, L, M, N, O, P, Q, R, S, T, U, V, W) -> Com_1(f300(A, B, C, D, E, F, G, H, I, J, X, L, M, Z, O, P, A1, R, S, B1, C1, D1, Y)) :|: 0 >= E1 + 1 && J >= 1 && F1 + 1 >= 0
f1(A, B, C, D, E, F, G, H, I, J, K, L, M, N, O, P, Q, R, S, T, U, V, W) -> Com_1(f300(A, B, C, D, E, F, G, H, I, J, X, L, M, N, O, P, Q, R, S, Z, U, V, A1)) :|: J >= 0 && J <= 0

The start-symbols are:[f2_23]


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

(1) Loat Proof (FINISHED)


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



Initial linear ITS problem

   Start location: f2

      0: f2 -> f1 : A'=free, B'=free, C'=free, D'=free, E'=free, F'=free, G'=free, H'=free, Q'=free, [], cost: 1

      1: f1 -> f1 : K'=free_1, L'=free_5, M'=free_7, N'=free_4, O'=free_2, P'=free_6, [ 0>=free_3 && 0>=1+J ], cost: 1

      2: f1 -> f1 : K'=free_9, L'=free_14, M'=free_16, N'=free_13, Q_1'=free_10, R'=free_15, S'=free_12, [ 0>=1+J && free_11>=1 && free_8>=2 ], cost: 1

      3: f1 -> f1 : K'=free_17, N'=free_22, O'=free_24, P'=free_21, T'=free_18, U'=free_23, V'=free_20, [ 0>=2+free_19 && J>=1 ], cost: 1

      4: f1 -> f1 : K'=free_26, N'=free_32, Q_1'=free_34, R'=free_30, S'=free_27, T'=free_33, U'=free_29, V'=free_28, [ J>=1 && free_25>=0 && 1+free_31>=0 ], cost: 1

      5: f1 -> f300 : A1'=B, B'=C, B1'=D, C'=E, C1'=F, D'=G, D1'=H, E'=Q, E1'=J, F'=free_35, F1'=free_40, G'=free_42, G1'=free_39, H'=O, Q'=P, J'=free_36, K'=R, L'=S, M'=T, N'=U, O'=V, P'=free_41, [ 1>=free_38 && 0>=1+J && free_37>=1 ], cost: 1

      6: f1 -> f300 : A1'=B, B'=C, B1'=D, C'=E, C1'=F, D'=G, D1'=H, E'=Q, E1'=J, F'=free_44, F1'=L, G'=M, G1'=free_49, H'=O, Q'=P, J'=free_51, K'=R, L'=S, M'=free_48, N'=free_45, O'=free_50, P'=free_47, [ 0>=1+free_46 && J>=1 && 1+free_43>=0 ], cost: 1

      7: f1 -> f300 : A1'=B, B'=C, B1'=D, C'=E, C1'=F, D'=G, D1'=H, E'=Q, E1'=J, F'=free_52, F1'=L, G'=M, G1'=N, H'=O, Q'=P, J'=Q_1, K'=R, L'=S, M'=free_53, N'=U, O'=V, P'=free_54, [ J==0 ], cost: 1



Removed unreachable and leaf rules:

   Start location: f2

      0: f2 -> f1 : A'=free, B'=free, C'=free, D'=free, E'=free, F'=free, G'=free, H'=free, Q'=free, [], cost: 1

      1: f1 -> f1 : K'=free_1, L'=free_5, M'=free_7, N'=free_4, O'=free_2, P'=free_6, [ 0>=free_3 && 0>=1+J ], cost: 1

      2: f1 -> f1 : K'=free_9, L'=free_14, M'=free_16, N'=free_13, Q_1'=free_10, R'=free_15, S'=free_12, [ 0>=1+J && free_11>=1 && free_8>=2 ], cost: 1

      3: f1 -> f1 : K'=free_17, N'=free_22, O'=free_24, P'=free_21, T'=free_18, U'=free_23, V'=free_20, [ 0>=2+free_19 && J>=1 ], cost: 1

      4: f1 -> f1 : K'=free_26, N'=free_32, Q_1'=free_34, R'=free_30, S'=free_27, T'=free_33, U'=free_29, V'=free_28, [ J>=1 && free_25>=0 && 1+free_31>=0 ], cost: 1



Simplified all rules, resulting in:

   Start location: f2

      0: f2 -> f1 : A'=free, B'=free, C'=free, D'=free, E'=free, F'=free, G'=free, H'=free, Q'=free, [], cost: 1

      1: f1 -> f1 : K'=free_1, L'=free_5, M'=free_7, N'=free_4, O'=free_2, P'=free_6, [ 0>=1+J ], cost: 1

      2: f1 -> f1 : K'=free_9, L'=free_14, M'=free_16, N'=free_13, Q_1'=free_10, R'=free_15, S'=free_12, [ 0>=1+J ], cost: 1

      3: f1 -> f1 : K'=free_17, N'=free_22, O'=free_24, P'=free_21, T'=free_18, U'=free_23, V'=free_20, [ J>=1 ], cost: 1

      4: f1 -> f1 : K'=free_26, N'=free_32, Q_1'=free_34, R'=free_30, S'=free_27, T'=free_33, U'=free_29, V'=free_28, [ J>=1 ], cost: 1



### Simplification by acceleration and chaining ###



Accelerating simple loops of location 1.

   Accelerating the following rules:

      1: f1 -> f1 : K'=free_1, L'=free_5, M'=free_7, N'=free_4, O'=free_2, P'=free_6, [ 0>=1+J ], cost: 1

      2: f1 -> f1 : K'=free_9, L'=free_14, M'=free_16, N'=free_13, Q_1'=free_10, R'=free_15, S'=free_12, [ 0>=1+J ], cost: 1

      3: f1 -> f1 : K'=free_17, N'=free_22, O'=free_24, P'=free_21, T'=free_18, U'=free_23, V'=free_20, [ J>=1 ], cost: 1

      4: f1 -> f1 : K'=free_26, N'=free_32, Q_1'=free_34, R'=free_30, S'=free_27, T'=free_33, U'=free_29, V'=free_28, [ J>=1 ], cost: 1



   Accelerated rule 1 with NONTERM, yielding the new rule 8.

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

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

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

   Removing the simple loops: 1 2 3 4.

   Also removing duplicate rules:.



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

   Start location: f2

      0: f2 -> f1 : A'=free, B'=free, C'=free, D'=free, E'=free, F'=free, G'=free, H'=free, Q'=free, [], cost: 1

      9: f1 -> [3] : [ 0>=1+J ], cost: INF

     11: f1 -> [3] : [ J>=1 ], cost: INF



Chained accelerated rules (with incoming rules):

   Start location: f2

      0: f2 -> f1 : A'=free, B'=free, C'=free, D'=free, E'=free, F'=free, G'=free, H'=free, Q'=free, [], cost: 1

     12: f2 -> [3] : A'=free, B'=free, C'=free, D'=free, E'=free, F'=free, G'=free, H'=free, Q'=free, [ 0>=1+J ], cost: INF

     13: f2 -> [3] : A'=free, B'=free, C'=free, D'=free, E'=free, F'=free, G'=free, H'=free, Q'=free, [ J>=1 ], cost: INF



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

   Start location: f2

     12: f2 -> [3] : A'=free, B'=free, C'=free, D'=free, E'=free, F'=free, G'=free, H'=free, Q'=free, [ 0>=1+J ], cost: INF

     13: f2 -> [3] : A'=free, B'=free, C'=free, D'=free, E'=free, F'=free, G'=free, H'=free, Q'=free, [ J>=1 ], cost: INF



### Computing asymptotic complexity ###



Fully simplified ITS problem

   Start location: f2

     12: f2 -> [3] : A'=free, B'=free, C'=free, D'=free, E'=free, F'=free, G'=free, H'=free, Q'=free, [ 0>=1+J ], cost: INF

     13: f2 -> [3] : A'=free, B'=free, C'=free, D'=free, E'=free, F'=free, G'=free, H'=free, Q'=free, [ J>=1 ], cost: INF



Computing asymptotic complexity for rule 12

   Resulting cost INF 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: INF

   Rule cost:   INF

   Rule guard:  [ 0>=1+J ]



NO


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

(2)
BOUNDS(INF, INF)