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


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

(0)
Obligation:
Complexity Int TRS consisting of the following rules:
f12(A, B, C, D, E, F, G, H, I, J, K, L, M, N, O, P, Q, R, S, T, U, V, W, X, Y, Z, A1, B1) -> Com_1(f12(A, C1, D1, E, E, G, G, A, I, J, K, L, M, N, O, P, Q, R, S, T, U, V, W, X, Y, Z, A1, B1)) :|: A >= 0 && C1 >= 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, X, Y, Z, A1, B1) -> Com_1(f1(A, B, C, D, E, F, G, H, I, 1 + J, L, C1, L, D1, J, P, Q, R, S, T, U, V, W, X, Y, Z, A1, B1)) :|: I >= J + 1 && J >= 0
f8(A, B, C, D, E, F, G, H, I, J, K, L, M, N, O, P, Q, R, S, T, U, V, W, X, Y, Z, A1, B1) -> Com_1(f1(A, C1, C, D, E, F, G, H, C1, 2, E1, F1, E1, N, O, D1, E1, G1, 2, T, U, V, W, X, Y, Z, A1, B1)) :|: C1 >= 2
f8(A, B, C, D, E, F, G, H, I, J, K, L, M, N, O, P, Q, R, S, T, U, V, W, X, Y, Z, A1, B1) -> Com_1(f9(A, C1, 0, D, 0, F, G, H, N1, L1, O1, R1, Q1, N, O, M1, P1, R, S, D1, E1, F1, G1, K1, S1, T1, U1, B1)) :|: 0 >= H1 && 0 >= I1 && 0 >= C1 && 0 >= J1
f1(A, B, C, D, E, F, G, H, I, J, K, L, M, N, O, P, Q, R, S, T, U, V, W, X, Y, Z, A1, B1) -> Com_1(f12(A, C1, D1, D, K, F, G, H, G1, F1, K1, N1, M1, N, O, P, L1, R, S, T, U, V, W, X, O1, P1, A1, E1)) :|: J >= I && J >= 0 && Q1 >= 2 && F1 >= Q1 && F1 >= 0 && C1 >= 2 && E1 >= C1
f12(A, B, C, D, E, F, G, H, I, J, K, L, M, N, O, P, Q, R, S, T, U, V, W, X, Y, Z, A1, B1) -> Com_1(f9(A, C1, 0, D, 0, F, G, H, I, J, K, L, M, N, O, P, Q, R, S, D1, E1, F1, G1, K1, Y, L1, M1, B1)) :|: N1 >= 2 && O1 >= 2 && A >= 0 && C1 >= 2 && E >= 0 && E <= 0 && C >= 0 && C <= 0
f8(A, B, C, D, E, F, G, H, I, J, K, L, M, N, O, P, Q, R, S, T, U, V, W, X, Y, Z, A1, B1) -> Com_1(f9(A, 1, K1, D, 0, F, G, H, N1, L1, O1, R1, Q1, N, O, M1, P1, R, S, C1, D1, E1, F1, G1, S1, T1, U1, B1)) :|: L >= 0 && L <= 0

The start-symbols are:[f8_28]


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

(1) Loat Proof (FINISHED)


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



Initial linear ITS problem

   Start location: f8

      0: f12 -> f12 : B'=free, C'=free_1, D'=E, F'=G, H'=A, [ A>=0 && free>=2 ], cost: 1

      5: f12 -> f9 : A1'=free_40, B'=0, B1'=D, C'=0, C1'=F, D'=G, D1'=H, E'=Q, E1'=J, F'=K, F1'=L, G'=M, G1'=N, H'=O, H1'=P, Q'=Q_1, Q1'=R, J'=S, J1'=free_46, K'=free_42, K1'=free_48, L'=free_44, L1'=free_49, M'=Y, M1'=free_45, N'=free_41, N1'=B1, [ free_47>=2 && free_43>=2 && A>=0 && free_40>=2 && E==0 && C==0 ], cost: 1

      1: f1 -> f1 : J'=1+J, K'=L, L'=free_2, M'=L, N'=free_3, O'=J, [ Q>=1+J && J>=0 ], cost: 1

      4: f1 -> f12 : B'=free_28, B1'=free_29, C'=free_35, E'=K, Q'=free_31, J'=free_38, K'=free_33, L'=free_39, M'=free_34, Q_1'=free_30, Y'=free_37, Z'=free_32, [ J>=Q && J>=0 && free_36>=2 && free_38>=free_36 && free_38>=0 && free_28>=2 && free_29>=free_28 ], cost: 1

      2: f8 -> f1 : B'=free_4, Q'=free_4, J'=2, K'=free_7, L'=free_5, M'=free_7, P'=free_8, Q_1'=free_7, R'=free_6, S'=2, [ free_4>=2 ], cost: 1

      3: f8 -> f9 : A1'=free_9, B'=0, B1'=D, C'=0, C1'=F, D'=G, D1'=H, E'=free_21, E1'=free_14, F'=free_25, F1'=free_18, G'=free_27, G1'=N, H'=O, H1'=free_20, Q'=free_13, Q1'=R, J'=S, J1'=free_24, K'=free_17, K1'=free_10, L'=free_22, L1'=free_15, M'=free_26, M1'=free_19, N'=free_12, N1'=B1, [ 0>=free_11 && 0>=free_23 && 0>=free_9 && 0>=free_16 ], cost: 1

      6: f8 -> f9 : A1'=1, B'=free_50, B1'=D, C'=0, C1'=F, D'=G, D1'=H, E'=free_60, E1'=free_54, F'=free_63, F1'=free_57, G'=free_65, G1'=N, H'=O, H1'=free_59, Q'=free_53, Q1'=R, J'=S, J1'=free_62, K'=free_56, K1'=free_51, L'=free_61, L1'=free_55, M'=free_64, M1'=free_58, N'=free_52, N1'=B1, [ L==0 ], cost: 1



Checking for constant complexity:

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

      2: f8 -> f1 : B'=free_4, Q'=free_4, J'=2, K'=free_7, L'=free_5, M'=free_7, P'=free_8, Q_1'=free_7, R'=free_6, S'=2, [ free_4>=2 ], cost: 1



Removed unreachable and leaf rules:

   Start location: f8

      0: f12 -> f12 : B'=free, C'=free_1, D'=E, F'=G, H'=A, [ A>=0 && free>=2 ], cost: 1

      1: f1 -> f1 : J'=1+J, K'=L, L'=free_2, M'=L, N'=free_3, O'=J, [ Q>=1+J && J>=0 ], cost: 1

      4: f1 -> f12 : B'=free_28, B1'=free_29, C'=free_35, E'=K, Q'=free_31, J'=free_38, K'=free_33, L'=free_39, M'=free_34, Q_1'=free_30, Y'=free_37, Z'=free_32, [ J>=Q && J>=0 && free_36>=2 && free_38>=free_36 && free_38>=0 && free_28>=2 && free_29>=free_28 ], cost: 1

      2: f8 -> f1 : B'=free_4, Q'=free_4, J'=2, K'=free_7, L'=free_5, M'=free_7, P'=free_8, Q_1'=free_7, R'=free_6, S'=2, [ free_4>=2 ], cost: 1



Simplified all rules, resulting in:

   Start location: f8

      0: f12 -> f12 : B'=free, C'=free_1, D'=E, F'=G, H'=A, [ A>=0 && free>=2 ], cost: 1

      1: f1 -> f1 : J'=1+J, K'=L, L'=free_2, M'=L, N'=free_3, O'=J, [ Q>=1+J && J>=0 ], cost: 1

      4: f1 -> f12 : B'=free_28, B1'=free_29, C'=free_35, E'=K, Q'=free_31, J'=free_38, K'=free_33, L'=free_39, M'=free_34, Q_1'=free_30, Y'=free_37, Z'=free_32, [ J>=Q && J>=0 && free_28>=2 && free_29>=free_28 && 2<=free_38 ], cost: 1

      2: f8 -> f1 : B'=free_4, Q'=free_4, J'=2, K'=free_7, L'=free_5, M'=free_7, P'=free_8, Q_1'=free_7, R'=free_6, S'=2, [ free_4>=2 ], cost: 1



### Simplification by acceleration and chaining ###



Accelerating simple loops of location 0.

   Accelerating the following rules:

      0: f12 -> f12 : B'=free, C'=free_1, D'=E, F'=G, H'=A, [ A>=0 && free>=2 ], cost: 1



   Accelerated rule 0 with NONTERM, yielding the new rule 7.

   Removing the simple loops: 0.



Accelerating simple loops of location 1.

   Accelerating the following rules:

      1: f1 -> f1 : J'=1+J, K'=L, L'=free_2, M'=L, N'=free_3, O'=J, [ Q>=1+J && J>=0 ], cost: 1



   Accelerated rule 1 with metering function -J+Q, yielding the new rule 8.

   Removing the simple loops: 1.



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

   Start location: f8

      7: f12 -> [4] : [ A>=0 && free>=2 ], cost: NONTERM

      4: f1 -> f12 : B'=free_28, B1'=free_29, C'=free_35, E'=K, Q'=free_31, J'=free_38, K'=free_33, L'=free_39, M'=free_34, Q_1'=free_30, Y'=free_37, Z'=free_32, [ J>=Q && J>=0 && free_28>=2 && free_29>=free_28 && 2<=free_38 ], cost: 1

      8: f1 -> f1 : J'=Q, K'=free_2, L'=free_2, M'=free_2, N'=free_3, O'=-1+Q, [ Q>=1+J && J>=0 ], cost: -J+Q

      2: f8 -> f1 : B'=free_4, Q'=free_4, J'=2, K'=free_7, L'=free_5, M'=free_7, P'=free_8, Q_1'=free_7, R'=free_6, S'=2, [ free_4>=2 ], cost: 1



Chained accelerated rules (with incoming rules):

   Start location: f8

      4: f1 -> f12 : B'=free_28, B1'=free_29, C'=free_35, E'=K, Q'=free_31, J'=free_38, K'=free_33, L'=free_39, M'=free_34, Q_1'=free_30, Y'=free_37, Z'=free_32, [ J>=Q && J>=0 && free_28>=2 && free_29>=free_28 && 2<=free_38 ], cost: 1

      9: f1 -> [4] : B'=free_28, B1'=free_29, C'=free_35, E'=K, Q'=free_31, J'=free_38, K'=free_33, L'=free_39, M'=free_34, Q_1'=free_30, Y'=free_37, Z'=free_32, [ J>=Q && J>=0 && free_28>=2 && free_29>=free_28 && 2<=free_38 && A>=0 ], cost: NONTERM

      2: f8 -> f1 : B'=free_4, Q'=free_4, J'=2, K'=free_7, L'=free_5, M'=free_7, P'=free_8, Q_1'=free_7, R'=free_6, S'=2, [ free_4>=2 ], cost: 1

     10: f8 -> f1 : B'=free_4, Q'=free_4, J'=free_4, K'=free_2, L'=free_2, M'=free_2, N'=free_3, O'=-1+free_4, P'=free_8, Q_1'=free_7, R'=free_6, S'=2, [ free_4>=3 ], cost: -1+free_4



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

   Start location: f8

      9: f1 -> [4] : B'=free_28, B1'=free_29, C'=free_35, E'=K, Q'=free_31, J'=free_38, K'=free_33, L'=free_39, M'=free_34, Q_1'=free_30, Y'=free_37, Z'=free_32, [ J>=Q && J>=0 && free_28>=2 && free_29>=free_28 && 2<=free_38 && A>=0 ], cost: NONTERM

      2: f8 -> f1 : B'=free_4, Q'=free_4, J'=2, K'=free_7, L'=free_5, M'=free_7, P'=free_8, Q_1'=free_7, R'=free_6, S'=2, [ free_4>=2 ], cost: 1

     10: f8 -> f1 : B'=free_4, Q'=free_4, J'=free_4, K'=free_2, L'=free_2, M'=free_2, N'=free_3, O'=-1+free_4, P'=free_8, Q_1'=free_7, R'=free_6, S'=2, [ free_4>=3 ], cost: -1+free_4



Eliminated locations (on tree-shaped paths):

   Start location: f8

     11: f8 -> [4] : B'=free_28, B1'=free_29, C'=free_35, E'=free_7, Q'=free_31, J'=free_38, K'=free_33, L'=free_39, M'=free_34, P'=free_8, Q_1'=free_30, R'=free_6, S'=2, Y'=free_37, Z'=free_32, [ free_4>=2 && 2>=free_4 && free_28>=2 && free_29>=free_28 && 2<=free_38 && A>=0 ], cost: NONTERM

     12: f8 -> [4] : B'=free_28, B1'=free_29, C'=free_35, E'=free_2, Q'=free_31, J'=free_38, K'=free_33, L'=free_39, M'=free_34, N'=free_3, O'=-1+free_4, P'=free_8, Q_1'=free_30, R'=free_6, S'=2, Y'=free_37, Z'=free_32, [ free_4>=3 && free_28>=2 && free_29>=free_28 && 2<=free_38 && A>=0 ], cost: NONTERM



### Computing asymptotic complexity ###



Fully simplified ITS problem

   Start location: f8

     11: f8 -> [4] : B'=free_28, B1'=free_29, C'=free_35, E'=free_7, Q'=free_31, J'=free_38, K'=free_33, L'=free_39, M'=free_34, P'=free_8, Q_1'=free_30, R'=free_6, S'=2, Y'=free_37, Z'=free_32, [ free_4>=2 && 2>=free_4 && free_28>=2 && free_29>=free_28 && 2<=free_38 && A>=0 ], cost: NONTERM

     12: f8 -> [4] : B'=free_28, B1'=free_29, C'=free_35, E'=free_2, Q'=free_31, J'=free_38, K'=free_33, L'=free_39, M'=free_34, N'=free_3, O'=-1+free_4, P'=free_8, Q_1'=free_30, R'=free_6, S'=2, Y'=free_37, Z'=free_32, [ free_4>=3 && free_28>=2 && free_29>=free_28 && 2<=free_38 && A>=0 ], cost: NONTERM



Computing asymptotic complexity for rule 11

   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:  [ free_4>=2 && 2>=free_4 && free_28>=2 && free_29>=free_28 && 2<=free_38 && A>=0 ]



NO


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

(2)
BOUNDS(INF, INF)