/export/starexec/sandbox2/solver/bin/starexec_run_complexity /export/starexec/sandbox2/benchmark/theBenchmark.koat /export/starexec/sandbox2/output/output_files


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


WORST_CASE(NON_POLY, ?)
proof of /export/starexec/sandbox2/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, 325 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_43, 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_48, K'=free_45, K1'=free_41, L'=free_46, L1'=free_42, M'=Y, M1'=free_47, N'=free_44, N1'=B1, [ free_40>=2 && free_49>=2 && A>=0 && free_43>=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_32, B1'=free_35, C'=free_38, E'=K, Q'=free_34, J'=free_29, K'=free_36, L'=free_31, M'=free_37, Q_1'=free_33, Y'=free_28, Z'=free_39, [ J>=Q && J>=0 && free_30>=2 && free_29>=free_30 && free_29>=0 && free_32>=2 && free_35>=free_32 ], cost: 1

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

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

      6: f8 -> f9 : A1'=1, B'=free_54, B1'=D, C'=0, C1'=F, D'=G, D1'=H, E'=free_63, E1'=free_57, F'=free_51, F1'=free_60, G'=free_53, G1'=N, H'=O, H1'=free_62, Q'=free_56, Q1'=R, J'=S, J1'=free_50, K'=free_64, K1'=free_58, L'=free_52, L1'=free_61, M'=free_55, M1'=free_65, N'=free_59, N1'=B1, [ L==0 ], 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_32, B1'=free_35, C'=free_38, E'=K, Q'=free_34, J'=free_29, K'=free_36, L'=free_31, M'=free_37, Q_1'=free_33, Y'=free_28, Z'=free_39, [ J>=Q && J>=0 && free_30>=2 && free_29>=free_30 && free_29>=0 && free_32>=2 && free_35>=free_32 ], cost: 1

      2: f8 -> f1 : B'=free_5, Q'=free_5, J'=2, K'=free_8, L'=free_6, M'=free_8, P'=free_4, Q_1'=free_8, R'=free_7, S'=2, [ free_5>=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_32, B1'=free_35, C'=free_38, E'=K, Q'=free_34, J'=free_29, K'=free_36, L'=free_31, M'=free_37, Q_1'=free_33, Y'=free_28, Z'=free_39, [ J>=Q && J>=0 && free_32>=2 && free_35>=free_32 && 2<=free_29 ], cost: 1

      2: f8 -> f1 : B'=free_5, Q'=free_5, J'=2, K'=free_8, L'=free_6, M'=free_8, P'=free_4, Q_1'=free_8, R'=free_7, S'=2, [ free_5>=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: INF

      4: f1 -> f12 : B'=free_32, B1'=free_35, C'=free_38, E'=K, Q'=free_34, J'=free_29, K'=free_36, L'=free_31, M'=free_37, Q_1'=free_33, Y'=free_28, Z'=free_39, [ J>=Q && J>=0 && free_32>=2 && free_35>=free_32 && 2<=free_29 ], 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_5, Q'=free_5, J'=2, K'=free_8, L'=free_6, M'=free_8, P'=free_4, Q_1'=free_8, R'=free_7, S'=2, [ free_5>=2 ], cost: 1



Chained accelerated rules (with incoming rules):

   Start location: f8

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

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

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

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



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

   Start location: f8

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

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

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



Eliminated locations (on tree-shaped paths):

   Start location: f8

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

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



### Computing asymptotic complexity ###



Fully simplified ITS problem

   Start location: f8

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

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



Computing asymptotic complexity for rule 11

   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:  [ free_5>=2 && 2>=free_5 && free_32>=2 && free_35>=free_32 && 2<=free_29 && A>=0 ]



NO


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

(2)
BOUNDS(INF, INF)