/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, 694 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, C1, D1, E1, F1, G1, H1, I1, J1, K1, L1) -> Com_1(f16(A, 1, M1, O1, P1, 1 + G, G, Q1, G, J, K, L, M, N, O, P, Q, R, S, T, U, V, W, X, Y, Z, A1, B1, C1, D1, E1, F1, G1, H1, I1, J1, K1, L1)) :|: A >= 0 && M1 >= 2 && N1 >= M1 && B >= 1 && B <= 1
f13(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, C1, D1, E1, F1, G1, H1, I1, J1, K1, L1) -> Com_1(f16(A, B, M1, O1, E, F, G, H, I, P1, Q1, L, M, N, O, P, Q, R, S, T, U, V, W, X, Y, Z, A1, B1, C1, D1, E1, F1, G1, H1, I1, J1, K1, L1)) :|: M1 >= 2 && I >= 0
f16(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, C1, D1, E1, F1, G1, H1, I1, J1, K1, L1) -> Com_1(f16(A, 1 + B, M1, O1, P1, F, -(1) + G, H, I, J, K, M, M, Q1, 1 + B, -(1) + G, Q, R, S, T, U, V, W, X, Y, Z, A1, B1, C1, D1, E1, F1, G1, H1, I1, J1, K1, L1)) :|: B >= 0 && G >= 0 && M1 >= 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, C1, D1, E1, F1, G1, H1, I1, J1, K1, L1) -> Com_1(f1(1 + A, B, C, D, E, F, G, H, I, J, K, L, M, N, O, P, Q, S, M1, S, O1, A, W, X, Y, Z, A1, B1, C1, D1, E1, F1, G1, H1, I1, J1, K1, L1)) :|: Q >= A + 1 && A >= 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, X, Y, Z, A1, B1, C1, D1, E1, F1, G1, H1, I1, J1, K1, L1) -> Com_1(f16(G, 0, M1, R, E, F, G, H, I, J, K, L, R, N, O, P, O1, P1, S1, N1, U, V, Q1, T1, U1, R1, A1, B1, C1, D1, E1, F1, G1, H1, I1, J1, K1, L1)) :|: A >= Q && A >= 0 && M1 >= 2 && R1 >= M1 && G >= M1 && B >= 0 && B <= 0
f7(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, C1, D1, E1, F1, G1, H1, I1, J1, K1, L1) -> Com_1(f8(A, B, M1, O1, E, F, G, H, I, J, K, L, 0, N, O, P, Q, R, S, T, U, V, W, X, Y, Z, A1, 0, O1, 0, O1, G1, G1, H1, I1, J1, K1, L1)) :|: M1 >= 2 && A1 >= 0 && B1 >= 0 && B1 <= 0
f7(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, C1, D1, E1, F1, G1, H1, I1, J1, K1, L1) -> Com_1(f10(A, B, M1, T1, E, F, G, H, I, J, K, L, M, N, O, P, Q, R, S, T, U, V, W, X, U1, Z, A1, N1, O1, P1, Q1, R1, S1, H1, I1, J1, K1, L1)) :|: M1 >= 2 && A1 >= 0 && B1 >= G1 && B1 <= G1
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, C1, D1, E1, F1, G1, H1, I1, J1, K1, L1) -> Com_1(f8(A, B, M1, O1, P1, F, G, H, I, J, K, L, 0, N, O, P, Q, R, S, T, U, V, W, X, Y, Z, A1, 0, O1, 0, O1, G1, G1, -(1) + H1, -(1) + H1, J1, K1, L1)) :|: M1 >= 2 && H1 >= 0 && B1 >= 0 && B1 <= 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, C1, D1, E1, F1, G1, H1, I1, J1, K1, L1) -> Com_1(f10(A, B, M1, D, E, F, G, H, I, J, K, L, M, N, O, P, Q, R, S, T, U, V, W, X, T1, Z, A1, N1, O1, P1, Q1, U1, S1, H1, I1, J1, K1, L1)) :|: M1 >= 2 && H1 >= 0 && B1 >= G1 && B1 <= G1
f13(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, C1, D1, E1, F1, G1, H1, I1, J1, K1, L1) -> Com_1(f8(A, H1 + 1, M1, D, E, F, G, H, 0, J, K, L, 0, N, O, P, Q, R, S, T, U, V, W, X, Y, Z, H1, 0, D, 0, D, D, D, H1, I1, J1, K1, L1)) :|: O1 >= 2 && M1 >= 2 && M >= 0 && M <= 0 && I >= 0 && I <= 0 && B >= 1 && B <= 1
f16(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, C1, D1, E1, F1, G1, H1, I1, J1, K1, L1) -> Com_1(f8(A, H1 + 1, M1, D, E, F, G, H, I, J, K, L, 0, N, O, P, Q, R, S, T, U, V, W, X, Y, Z, H1, 0, D, 0, D, D, D, H1, I1, J1, K1, L1)) :|: O1 >= 2 && M1 >= 2 && B >= 0 && G >= 0 && M >= 0 && M <= 0
f9(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, C1, D1, E1, F1, G1, H1, I1, J1, K1, L1) -> Com_1(f1(2, B, M1, D, E, F, G, H, I, J, K, L, M, N, O, P, M1, P1, Q1, P1, U, V, P1, X, Y, Z, A1, B1, C1, D1, E1, F1, G1, H1, I1, O1, N1, 2)) :|: M1 >= 2
f9(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, C1, D1, E1, F1, G1, H1, I1, J1, K1, L1) -> Com_1(f10(T1, B, M1, 0, E, F, G, H, I, J, K, L, 0, N, O, P, R1, Y1, B2, A2, U, V, Z1, C2, D2, Z, A1, N1, O1, P1, Q1, E2, S1, H1, I1, U1, K1, L1)) :|: 0 >= V1 && 0 >= W1 && 0 >= M1 && 0 >= X1
f9(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, C1, D1, E1, F1, G1, H1, I1, J1, K1, L1) -> Com_1(f10(T1, B, 1, S1, E, F, G, H, I, J, K, L, 0, N, O, P, R1, Y1, B2, A2, U, V, Z1, C2, D2, Z, A1, Q1, M1, O1, P1, E2, N1, H1, I1, U1, K1, L1)) :|: S >= 0 && S <= 0

The start-symbols are:[f9_38]


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

(1) Loat Proof (FINISHED)


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



Initial linear ITS problem

   Start location: f9

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

      1: f13 -> f16 : C'=free_8, D'=free_5, J'=free_7, K'=free_6, [ free_8>=2 && Q>=0 ], cost: 1

      9: f13 -> f8 : A1'=H1, B'=1+H1, B1'=0, C'=free_47, C1'=D, D1'=0, E1'=D, F1'=D, G1'=D, Q'=0, M'=0, [ free_46>=2 && free_47>=2 && M==0 && Q==0 && B==1 ], cost: 1

      2: f16 -> f16 : B'=1+B, C'=free_12, D'=free_9, E'=free_11, G'=-1+G, L'=M, N'=free_10, O'=1+B, P'=-1+G, [ B>=0 && G>=0 && free_12>=2 ], cost: 1

     10: f16 -> f8 : A1'=H1, B'=1+H1, B1'=0, C'=free_49, C1'=D, D1'=0, E1'=D, F1'=D, G1'=D, M'=0, [ free_48>=2 && free_49>=2 && B>=0 && G>=0 && M==0 ], cost: 1

      3: f1 -> f1 : A'=1+A, R'=S, S'=free_14, T'=S, U'=free_13, V'=A, [ Q_1>=1+A && A>=0 ], cost: 1

      4: f1 -> f16 : A'=G, B'=0, C'=free_22, D'=R, M'=R, Q_1'=free_15, R'=free_20, S'=free_17, T'=free_18, W'=free_19, X'=free_16, Y'=free_21, Z'=free_23, [ A>=Q_1 && A>=0 && free_22>=2 && free_23>=free_22 && G>=free_22 && B==0 ], cost: 1

      5: f7 -> f8 : B1'=0, C'=free_25, C1'=free_24, D'=free_24, D1'=0, E1'=free_24, F1'=G1, M'=0, [ free_25>=2 && A1>=0 && B1==0 ], cost: 1

      6: f7 -> f10 : A1'=B, A2'=free_33, B'=free_26, B1'=E, B2'=F, C'=G, C1'=H, C2'=Q, D'=J, D1'=K, D2'=L, E'=M, E1'=N, E2'=O, F'=P, F1'=Q_1, G'=R, G1'=S, H'=T, H1'=U, Q'=V, Q1'=W, J'=X, J1'=free_31, K'=Z, K1'=A1, L'=free_28, L1'=free_29, M'=free_30, M1'=free_27, N'=free_32, N1'=free_34, O'=H1, O1'=Q1, P'=J1, P1'=K1, Q_1'=L1, [ free_33>=2 && A1>=0 && B1==G1 ], cost: 1

      7: f8 -> f8 : B1'=0, C'=free_37, C1'=free_35, D'=free_35, D1'=0, E'=free_36, E1'=free_35, F1'=G1, H1'=-1+H1, Q1'=-1+H1, M'=0, [ free_37>=2 && H1>=0 && B1==0 ], cost: 1

      8: f8 -> f10 : A1'=B, A2'=free_45, B'=D, B1'=E, B2'=F, C'=G, C1'=H, C2'=Q, D'=J, D1'=K, D2'=L, E'=M, E1'=N, E2'=O, F'=P, F1'=Q_1, G'=R, G1'=S, H'=T, H1'=U, Q'=V, Q1'=W, J'=X, J1'=free_38, K'=Z, K1'=A1, L'=free_43, L1'=free_40, M'=free_41, M1'=free_42, N'=free_39, N1'=free_44, O'=H1, O1'=Q1, P'=J1, P1'=K1, Q_1'=L1, [ free_45>=2 && H1>=0 && B1==G1 ], cost: 1

     11: f9 -> f1 : A'=2, C'=free_54, J1'=free_51, K1'=free_52, L1'=2, Q_1'=free_54, R'=free_50, S'=free_53, T'=free_50, W'=free_50, [ free_54>=2 ], cost: 1

     12: f9 -> f10 : A'=free_67, A1'=B, A2'=free_55, B'=0, B1'=E, B2'=F, C'=G, C1'=H, C2'=Q, D'=J, D1'=K, D2'=L, E'=0, E1'=N, E2'=O, F'=P, F1'=free_65, G'=free_60, G1'=free_62, H'=free_63, H1'=U, Q'=V, Q1'=free_57, J'=free_66, J1'=free_70, K'=Z, K1'=A1, L'=free_59, L1'=free_68, M'=free_58, M1'=free_56, N'=free_73, N1'=free_71, O'=H1, O1'=Q1, P'=free_69, P1'=K1, Q_1'=L1, [ 0>=free_61 && 0>=free_72 && 0>=free_55 && 0>=free_64 ], cost: 1

     13: f9 -> f10 : A'=free_84, A1'=B, A2'=1, B'=free_74, B1'=E, B2'=F, C'=G, C1'=H, C2'=Q, D'=J, D1'=K, D2'=L, E'=0, E1'=N, E2'=O, F'=P, F1'=free_82, G'=free_79, G1'=free_80, H'=free_81, H1'=U, Q'=V, Q1'=free_76, J'=free_83, J1'=free_87, K'=Z, K1'=A1, L'=free_78, L1'=free_85, M'=free_77, M1'=free_75, N'=free_89, N1'=free_88, O'=H1, O1'=Q1, P'=free_86, P1'=K1, Q_1'=L1, [ S==0 ], cost: 1



Checking for constant complexity:

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

     11: f9 -> f1 : A'=2, C'=free_54, J1'=free_51, K1'=free_52, L1'=2, Q_1'=free_54, R'=free_50, S'=free_53, T'=free_50, W'=free_50, [ free_54>=2 ], cost: 1



Removed unreachable and leaf rules:

   Start location: f9

      2: f16 -> f16 : B'=1+B, C'=free_12, D'=free_9, E'=free_11, G'=-1+G, L'=M, N'=free_10, O'=1+B, P'=-1+G, [ B>=0 && G>=0 && free_12>=2 ], cost: 1

     10: f16 -> f8 : A1'=H1, B'=1+H1, B1'=0, C'=free_49, C1'=D, D1'=0, E1'=D, F1'=D, G1'=D, M'=0, [ free_48>=2 && free_49>=2 && B>=0 && G>=0 && M==0 ], cost: 1

      3: f1 -> f1 : A'=1+A, R'=S, S'=free_14, T'=S, U'=free_13, V'=A, [ Q_1>=1+A && A>=0 ], cost: 1

      4: f1 -> f16 : A'=G, B'=0, C'=free_22, D'=R, M'=R, Q_1'=free_15, R'=free_20, S'=free_17, T'=free_18, W'=free_19, X'=free_16, Y'=free_21, Z'=free_23, [ A>=Q_1 && A>=0 && free_22>=2 && free_23>=free_22 && G>=free_22 && B==0 ], cost: 1

      7: f8 -> f8 : B1'=0, C'=free_37, C1'=free_35, D'=free_35, D1'=0, E'=free_36, E1'=free_35, F1'=G1, H1'=-1+H1, Q1'=-1+H1, M'=0, [ free_37>=2 && H1>=0 && B1==0 ], cost: 1

     11: f9 -> f1 : A'=2, C'=free_54, J1'=free_51, K1'=free_52, L1'=2, Q_1'=free_54, R'=free_50, S'=free_53, T'=free_50, W'=free_50, [ free_54>=2 ], cost: 1



Removed unreachable and leaf rules:

   Start location: f9

      2: f16 -> f16 : B'=1+B, C'=free_12, D'=free_9, E'=free_11, G'=-1+G, L'=M, N'=free_10, O'=1+B, P'=-1+G, [ B>=0 && G>=0 && free_12>=2 ], cost: 1

     10: f16 -> f8 : A1'=H1, B'=1+H1, B1'=0, C'=free_49, C1'=D, D1'=0, E1'=D, F1'=D, G1'=D, M'=0, [ free_48>=2 && free_49>=2 && B>=0 && G>=0 && M==0 ], cost: 1

      3: f1 -> f1 : A'=1+A, R'=S, S'=free_14, T'=S, U'=free_13, V'=A, [ Q_1>=1+A && A>=0 ], cost: 1

      4: f1 -> f16 : A'=G, B'=0, C'=free_22, D'=R, M'=R, Q_1'=free_15, R'=free_20, S'=free_17, T'=free_18, W'=free_19, X'=free_16, Y'=free_21, Z'=free_23, [ A>=Q_1 && A>=0 && free_22>=2 && free_23>=free_22 && G>=free_22 && B==0 ], cost: 1

      7: f8 -> f8 : B1'=0, C'=free_37, C1'=free_35, D'=free_35, D1'=0, E'=free_36, E1'=free_35, F1'=G1, H1'=-1+H1, Q1'=-1+H1, M'=0, [ free_37>=2 && H1>=0 && B1==0 ], cost: 1

     11: f9 -> f1 : A'=2, C'=free_54, J1'=free_51, K1'=free_52, L1'=2, Q_1'=free_54, R'=free_50, S'=free_53, T'=free_50, W'=free_50, [ free_54>=2 ], cost: 1



Simplified all rules, resulting in:

   Start location: f9

      2: f16 -> f16 : B'=1+B, C'=free_12, D'=free_9, E'=free_11, G'=-1+G, L'=M, N'=free_10, O'=1+B, P'=-1+G, [ B>=0 && G>=0 && free_12>=2 ], cost: 1

     10: f16 -> f8 : A1'=H1, B'=1+H1, B1'=0, C'=free_49, C1'=D, D1'=0, E1'=D, F1'=D, G1'=D, M'=0, [ free_49>=2 && B>=0 && G>=0 && M==0 ], cost: 1

      3: f1 -> f1 : A'=1+A, R'=S, S'=free_14, T'=S, U'=free_13, V'=A, [ Q_1>=1+A && A>=0 ], cost: 1

      4: f1 -> f16 : A'=G, B'=0, C'=free_22, D'=R, M'=R, Q_1'=free_15, R'=free_20, S'=free_17, T'=free_18, W'=free_19, X'=free_16, Y'=free_21, Z'=free_23, [ A>=Q_1 && A>=0 && free_22>=2 && free_23>=free_22 && G>=free_22 && B==0 ], cost: 1

      7: f8 -> f8 : B1'=0, C'=free_37, C1'=free_35, D'=free_35, D1'=0, E'=free_36, E1'=free_35, F1'=G1, H1'=-1+H1, Q1'=-1+H1, M'=0, [ free_37>=2 && H1>=0 && B1==0 ], cost: 1

     11: f9 -> f1 : A'=2, C'=free_54, J1'=free_51, K1'=free_52, L1'=2, Q_1'=free_54, R'=free_50, S'=free_53, T'=free_50, W'=free_50, [ free_54>=2 ], cost: 1



### Simplification by acceleration and chaining ###



Accelerating simple loops of location 2.

   Accelerating the following rules:

      2: f16 -> f16 : B'=1+B, C'=free_12, D'=free_9, E'=free_11, G'=-1+G, L'=M, N'=free_10, O'=1+B, P'=-1+G, [ B>=0 && G>=0 && free_12>=2 ], cost: 1



   Accelerated rule 2 with metering function 1+G, yielding the new rule 14.

   Removing the simple loops: 2.



Accelerating simple loops of location 3.

   Accelerating the following rules:

      3: f1 -> f1 : A'=1+A, R'=S, S'=free_14, T'=S, U'=free_13, V'=A, [ Q_1>=1+A && A>=0 ], cost: 1



   Accelerated rule 3 with metering function -A+Q_1, yielding the new rule 15.

   Removing the simple loops: 3.



Accelerating simple loops of location 5.

   Accelerating the following rules:

      7: f8 -> f8 : B1'=0, C'=free_37, C1'=free_35, D'=free_35, D1'=0, E'=free_36, E1'=free_35, F1'=G1, H1'=-1+H1, Q1'=-1+H1, M'=0, [ free_37>=2 && H1>=0 && B1==0 ], cost: 1



   Accelerated rule 7 with metering function 1+H1, yielding the new rule 16.

   Removing the simple loops: 7.



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

   Start location: f9

     10: f16 -> f8 : A1'=H1, B'=1+H1, B1'=0, C'=free_49, C1'=D, D1'=0, E1'=D, F1'=D, G1'=D, M'=0, [ free_49>=2 && B>=0 && G>=0 && M==0 ], cost: 1

     14: f16 -> f16 : B'=1+B+G, C'=free_12, D'=free_9, E'=free_11, G'=-1, L'=M, N'=free_10, O'=1+B+G, P'=-1, [ B>=0 && G>=0 && free_12>=2 ], cost: 1+G

      4: f1 -> f16 : A'=G, B'=0, C'=free_22, D'=R, M'=R, Q_1'=free_15, R'=free_20, S'=free_17, T'=free_18, W'=free_19, X'=free_16, Y'=free_21, Z'=free_23, [ A>=Q_1 && A>=0 && free_22>=2 && free_23>=free_22 && G>=free_22 && B==0 ], cost: 1

     15: f1 -> f1 : A'=Q_1, R'=free_14, S'=free_14, T'=free_14, U'=free_13, V'=-1+Q_1, [ Q_1>=1+A && A>=0 ], cost: -A+Q_1

     16: f8 -> f8 : B1'=0, C'=free_37, C1'=free_35, D'=free_35, D1'=0, E'=free_36, E1'=free_35, F1'=G1, H1'=-1, Q1'=-1, M'=0, [ free_37>=2 && H1>=0 && B1==0 ], cost: 1+H1

     11: f9 -> f1 : A'=2, C'=free_54, J1'=free_51, K1'=free_52, L1'=2, Q_1'=free_54, R'=free_50, S'=free_53, T'=free_50, W'=free_50, [ free_54>=2 ], cost: 1



Chained accelerated rules (with incoming rules):

   Start location: f9

     10: f16 -> f8 : A1'=H1, B'=1+H1, B1'=0, C'=free_49, C1'=D, D1'=0, E1'=D, F1'=D, G1'=D, M'=0, [ free_49>=2 && B>=0 && G>=0 && M==0 ], cost: 1

     19: f16 -> f8 : A1'=H1, B'=1+H1, B1'=0, C'=free_37, C1'=free_35, D'=free_35, D1'=0, E'=free_36, E1'=free_35, F1'=D, G1'=D, H1'=-1, Q1'=-1, M'=0, [ B>=0 && G>=0 && M==0 && free_37>=2 && H1>=0 ], cost: 2+H1

      4: f1 -> f16 : A'=G, B'=0, C'=free_22, D'=R, M'=R, Q_1'=free_15, R'=free_20, S'=free_17, T'=free_18, W'=free_19, X'=free_16, Y'=free_21, Z'=free_23, [ A>=Q_1 && A>=0 && free_22>=2 && free_23>=free_22 && G>=free_22 && B==0 ], cost: 1

     17: f1 -> f16 : A'=G, B'=1+G, C'=free_12, D'=free_9, E'=free_11, G'=-1, L'=R, M'=R, N'=free_10, O'=1+G, P'=-1, Q_1'=free_15, R'=free_20, S'=free_17, T'=free_18, W'=free_19, X'=free_16, Y'=free_21, Z'=free_23, [ A>=Q_1 && A>=0 && B==0 && free_12>=2 && 2<=free_23 && 2<=G ], cost: 2+G

     11: f9 -> f1 : A'=2, C'=free_54, J1'=free_51, K1'=free_52, L1'=2, Q_1'=free_54, R'=free_50, S'=free_53, T'=free_50, W'=free_50, [ free_54>=2 ], cost: 1

     18: f9 -> f1 : A'=free_54, C'=free_54, J1'=free_51, K1'=free_52, L1'=2, Q_1'=free_54, R'=free_14, S'=free_14, T'=free_14, U'=free_13, V'=-1+free_54, W'=free_50, [ free_54>=3 ], cost: -1+free_54



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

   Start location: f9

     19: f16 -> f8 : A1'=H1, B'=1+H1, B1'=0, C'=free_37, C1'=free_35, D'=free_35, D1'=0, E'=free_36, E1'=free_35, F1'=D, G1'=D, H1'=-1, Q1'=-1, M'=0, [ B>=0 && G>=0 && M==0 && free_37>=2 && H1>=0 ], cost: 2+H1

      4: f1 -> f16 : A'=G, B'=0, C'=free_22, D'=R, M'=R, Q_1'=free_15, R'=free_20, S'=free_17, T'=free_18, W'=free_19, X'=free_16, Y'=free_21, Z'=free_23, [ A>=Q_1 && A>=0 && free_22>=2 && free_23>=free_22 && G>=free_22 && B==0 ], cost: 1

     17: f1 -> f16 : A'=G, B'=1+G, C'=free_12, D'=free_9, E'=free_11, G'=-1, L'=R, M'=R, N'=free_10, O'=1+G, P'=-1, Q_1'=free_15, R'=free_20, S'=free_17, T'=free_18, W'=free_19, X'=free_16, Y'=free_21, Z'=free_23, [ A>=Q_1 && A>=0 && B==0 && free_12>=2 && 2<=free_23 && 2<=G ], cost: 2+G

     11: f9 -> f1 : A'=2, C'=free_54, J1'=free_51, K1'=free_52, L1'=2, Q_1'=free_54, R'=free_50, S'=free_53, T'=free_50, W'=free_50, [ free_54>=2 ], cost: 1

     18: f9 -> f1 : A'=free_54, C'=free_54, J1'=free_51, K1'=free_52, L1'=2, Q_1'=free_54, R'=free_14, S'=free_14, T'=free_14, U'=free_13, V'=-1+free_54, W'=free_50, [ free_54>=3 ], cost: -1+free_54



Eliminated locations (on tree-shaped paths):

   Start location: f9

     19: f16 -> f8 : A1'=H1, B'=1+H1, B1'=0, C'=free_37, C1'=free_35, D'=free_35, D1'=0, E'=free_36, E1'=free_35, F1'=D, G1'=D, H1'=-1, Q1'=-1, M'=0, [ B>=0 && G>=0 && M==0 && free_37>=2 && H1>=0 ], cost: 2+H1

     20: f9 -> f16 : A'=G, B'=0, C'=free_22, D'=free_50, J1'=free_51, K1'=free_52, L1'=2, M'=free_50, Q_1'=free_15, R'=free_20, S'=free_17, T'=free_18, W'=free_19, X'=free_16, Y'=free_21, Z'=free_23, [ free_54>=2 && 2>=free_54 && free_22>=2 && free_23>=free_22 && G>=free_22 && B==0 ], cost: 2

     21: f9 -> f16 : A'=G, B'=1+G, C'=free_12, D'=free_9, E'=free_11, G'=-1, J1'=free_51, K1'=free_52, L'=free_50, L1'=2, M'=free_50, N'=free_10, O'=1+G, P'=-1, Q_1'=free_15, R'=free_20, S'=free_17, T'=free_18, W'=free_19, X'=free_16, Y'=free_21, Z'=free_23, [ free_54>=2 && 2>=free_54 && B==0 && free_12>=2 && 2<=free_23 && 2<=G ], cost: 3+G

     22: f9 -> f16 : A'=G, B'=0, C'=free_22, D'=free_14, J1'=free_51, K1'=free_52, L1'=2, M'=free_14, Q_1'=free_15, R'=free_20, S'=free_17, T'=free_18, U'=free_13, V'=-1+free_54, W'=free_19, X'=free_16, Y'=free_21, Z'=free_23, [ free_54>=3 && free_22>=2 && free_23>=free_22 && G>=free_22 && B==0 ], cost: free_54

     23: f9 -> f16 : A'=G, B'=1+G, C'=free_12, D'=free_9, E'=free_11, G'=-1, J1'=free_51, K1'=free_52, L'=free_14, L1'=2, M'=free_14, N'=free_10, O'=1+G, P'=-1, Q_1'=free_15, R'=free_20, S'=free_17, T'=free_18, U'=free_13, V'=-1+free_54, W'=free_19, X'=free_16, Y'=free_21, Z'=free_23, [ free_54>=3 && B==0 && free_12>=2 && 2<=free_23 && 2<=G ], cost: 1+G+free_54



Eliminated locations (on tree-shaped paths):

   Start location: f9

     24: f9 -> f8 : A'=G, A1'=H1, B'=1+H1, B1'=0, C'=free_37, C1'=free_35, D'=free_35, D1'=0, E'=free_36, E1'=free_35, F1'=free_50, G1'=free_50, H1'=-1, Q1'=-1, J1'=free_51, K1'=free_52, L1'=2, M'=0, Q_1'=free_15, R'=free_20, S'=free_17, T'=free_18, W'=free_19, X'=free_16, Y'=free_21, Z'=free_23, [ free_54>=2 && 2>=free_54 && free_22>=2 && free_23>=free_22 && G>=free_22 && B==0 && G>=0 && free_50==0 && free_37>=2 && H1>=0 ], cost: 4+H1

     25: f9 -> f8 : A'=G, A1'=H1, B'=1+H1, B1'=0, C'=free_37, C1'=free_35, D'=free_35, D1'=0, E'=free_36, E1'=free_35, F1'=free_14, G1'=free_14, H1'=-1, Q1'=-1, J1'=free_51, K1'=free_52, L1'=2, M'=0, Q_1'=free_15, R'=free_20, S'=free_17, T'=free_18, U'=free_13, V'=-1+free_54, W'=free_19, X'=free_16, Y'=free_21, Z'=free_23, [ free_54>=3 && free_22>=2 && free_23>=free_22 && G>=free_22 && B==0 && G>=0 && free_14==0 && free_37>=2 && H1>=0 ], cost: 2+H1+free_54

     26: f9 -> [11] : [ free_54>=2 && 2>=free_54 && B==0 && free_12>=2 && 2<=free_23 && 2<=G ], cost: 3+G

     27: f9 -> [11] : [ free_54>=3 && B==0 && free_12>=2 && 2<=free_23 && 2<=G ], cost: 1+G+free_54



### Computing asymptotic complexity ###



Fully simplified ITS problem

   Start location: f9

     24: f9 -> f8 : A'=G, A1'=H1, B'=1+H1, B1'=0, C'=free_37, C1'=free_35, D'=free_35, D1'=0, E'=free_36, E1'=free_35, F1'=free_50, G1'=free_50, H1'=-1, Q1'=-1, J1'=free_51, K1'=free_52, L1'=2, M'=0, Q_1'=free_15, R'=free_20, S'=free_17, T'=free_18, W'=free_19, X'=free_16, Y'=free_21, Z'=free_23, [ free_54>=2 && 2>=free_54 && free_22>=2 && free_23>=free_22 && G>=free_22 && B==0 && G>=0 && free_50==0 && free_37>=2 && H1>=0 ], cost: 4+H1

     25: f9 -> f8 : A'=G, A1'=H1, B'=1+H1, B1'=0, C'=free_37, C1'=free_35, D'=free_35, D1'=0, E'=free_36, E1'=free_35, F1'=free_14, G1'=free_14, H1'=-1, Q1'=-1, J1'=free_51, K1'=free_52, L1'=2, M'=0, Q_1'=free_15, R'=free_20, S'=free_17, T'=free_18, U'=free_13, V'=-1+free_54, W'=free_19, X'=free_16, Y'=free_21, Z'=free_23, [ free_54>=3 && free_22>=2 && free_23>=free_22 && G>=free_22 && B==0 && G>=0 && free_14==0 && free_37>=2 && H1>=0 ], cost: 2+H1+free_54

     26: f9 -> [11] : [ free_54>=2 && 2>=free_54 && B==0 && free_12>=2 && 2<=free_23 && 2<=G ], cost: 3+G

     27: f9 -> [11] : [ free_54>=3 && B==0 && free_12>=2 && 2<=free_23 && 2<=G ], cost: 1+G+free_54



Computing asymptotic complexity for rule 24

   Solved the limit problem by the following transformations:

      Created initial limit problem:

      3-free_54 (+/+!), 1-B (+/+!), 1+free_50 (+/+!), -1+free_22 (+/+!), -1+free_54 (+/+!), 1+H1 (+/+!), 1+B (+/+!), 1+G-free_22 (+/+!), 1-free_50 (+/+!), -1+free_37 (+/+!), 4+H1 (+), 1+free_23-free_22 (+/+!) [not solved]



      removing all constraints (solved by SMT)

      resulting limit problem: [solved]



      applying transformation rule (C) using substitution {free_23==n,B==0,free_37==n,free_50==0,H1==n,G==n,free_54==2,free_22==n}

      resulting limit problem:

      [solved]



   Solution:

      free_23 / n

      B / 0

      free_37 / n

      free_50 / 0

      H1 / n

      G / n

      free_54 / 2

      free_22 / n

   Resulting cost 4+n has complexity: Poly(n^1)



Found new complexity Poly(n^1).



Computing asymptotic complexity for rule 25

   Solved the limit problem by the following transformations:

      Created initial limit problem:

      1-B (+/+!), 1-free_14 (+/+!), -1+free_22 (+/+!), 1+H1 (+/+!), 2+H1+free_54 (+), -2+free_54 (+/+!), 1+B (+/+!), 1+G-free_22 (+/+!), 1+free_14 (+/+!), -1+free_37 (+/+!), 1+free_23-free_22 (+/+!) [not solved]



      removing all constraints (solved by SMT)

      resulting limit problem: [solved]



      applying transformation rule (C) using substitution {free_23==2,B==0,free_14==0,free_37==n,H1==0,G==2,free_54==n,free_22==2}

      resulting limit problem:

      [solved]



   Solution:

      free_23 / 2

      B / 0

      free_14 / 0

      free_37 / n

      H1 / 0

      G / 2

      free_54 / n

      free_22 / 2

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

   Rule cost:   2+H1+free_54

   Rule guard:  [ free_54>=3 && free_22>=2 && free_23>=free_22 && G>=free_22 && B==0 && free_14==0 && free_37>=2 && H1>=0 ]



WORST_CASE(INF,?)


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

(2)
BOUNDS(INF, INF)