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


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

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

The start-symbols are:[f3_32]


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

(1) Loat Proof (FINISHED)


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



Initial linear ITS problem

   Start location: f3

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

     14: f1 -> f10 : A'=free_82, A1'=free_85, B'=free_77, B1'=free_80, C'=free_86, D'=free_89, D1'=1+T, E'=free_81, E1'=Q, F1'=free_88, J'=C, K'=T, L'=N, M'=N, O'=free_84, P'=C, Q_1'=C, R'=C, S'=free_79, Z'=free_87, [ B>=A && B>=0 && free_83>=free_84 && free_78>=2 && free_77>=free_78 && C>=1+N && free_77>=0 && free_84>=2 && N>=1+C ], cost: 1

     15: f1 -> f10 : A'=free_95, A1'=free_98, B'=free_90, B1'=free_93, C'=free_99, D'=free_102, D1'=1+T, E'=free_94, E1'=Q, F1'=free_101, J'=C, K'=T, L'=N, M'=N, O'=free_97, P'=C, Q_1'=C, R'=C, S'=free_92, Z'=free_100, [ B>=A && B>=0 && free_96>=free_97 && free_91>=2 && free_90>=free_91 && C>=1+N && free_90>=0 && free_97>=2 ], cost: 1

     16: f1 -> f10 : A'=free_108, A1'=free_111, B'=free_103, B1'=free_106, C'=free_112, D'=free_115, D1'=1+T, E'=free_107, E1'=Q, F1'=free_114, J'=C, K'=T, L'=N, M'=N, O'=free_110, P'=C, Q_1'=C, R'=C, S'=free_105, Z'=free_113, [ B>=A && B>=0 && free_109>=free_110 && free_104>=2 && free_103>=free_104 && N>=1+C && free_103>=0 && free_110>=2 ], cost: 1

      1: f9 -> f10 : L'=M, N'=M, O'=free_3, P'=free_2, Q_1'=free_2, R'=J, [ free_4>=1+J && K>=0 && free_2>=1+free_4 && free_3>=2 ], cost: 1

      2: f9 -> f10 : L'=M, N'=M, O'=free_6, P'=free_5, Q_1'=free_5, R'=J, [ free_7>=1+J && K>=0 && free_7>=1+free_5 && free_6>=2 ], cost: 1

      3: f9 -> f10 : L'=M, N'=M, O'=free_9, P'=free_8, Q_1'=free_8, R'=J, [ J>=1+free_10 && K>=0 && free_8>=1+free_10 && free_9>=2 ], cost: 1

      4: f9 -> f10 : L'=M, N'=M, O'=free_12, P'=free_11, Q_1'=free_11, R'=J, [ J>=1+free_13 && K>=0 && free_13>=1+free_11 && free_12>=2 ], cost: 1

      5: f9 -> f4 : A1'=B, B'=C, B1'=D, C'=E, C1'=F, D'=G, D1'=H, E'=Q, E1'=free_17, F'=K, F1'=free_14, G'=free_19, G1'=N, H'=free_21, H1'=free_16, Q'=free_18, Q1'=free_15, J'=free_20, J1'=T, K'=U, K1'=V, L'=W, L1'=X, M'=Y, M1'=Z, N'=A1, N1'=B1, O'=C1, O1'=D1, P'=E1, P1'=F1, [ K>=0 && free_14>=1+free_16 && free_21>=2 && M==J ], cost: 1

      6: f9 -> f4 : A1'=B, B'=C, B1'=D, C'=E, C1'=F, D'=G, D1'=H, E'=Q, E1'=free_25, F'=K, F1'=free_22, G'=free_27, G1'=N, H'=free_29, H1'=free_24, Q'=free_26, Q1'=free_23, J'=free_28, J1'=T, K'=U, K1'=V, L'=W, L1'=X, M'=Y, M1'=Z, N'=A1, N1'=B1, O'=C1, O1'=D1, P'=E1, P1'=F1, [ K>=0 && free_24>=1+free_22 && free_29>=2 && M==J ], cost: 1

      7: f10 -> f10 : L'=M, N'=M, O'=free_31, P'=free_30, Q_1'=free_30, R'=J, T'=-1+T, U'=free_32, V'=Q, W'=-1+T, [ free_33>=1+J && T>=0 && free_30>=1+free_33 && free_31>=2 ], cost: 1

      8: f10 -> f10 : L'=M, N'=M, O'=free_35, P'=free_34, Q_1'=free_34, R'=J, T'=-1+T, U'=free_36, V'=Q, W'=-1+T, [ free_37>=1+J && T>=0 && free_37>=1+free_34 && free_35>=2 ], cost: 1

      9: f10 -> f10 : L'=M, N'=M, O'=free_39, P'=free_38, Q_1'=free_38, R'=J, T'=-1+T, U'=free_40, V'=Q, W'=-1+T, [ J>=1+free_41 && T>=0 && free_38>=1+free_41 && free_39>=2 ], cost: 1

     10: f10 -> f10 : L'=M, N'=M, O'=free_43, P'=free_42, Q_1'=free_42, R'=J, T'=-1+T, U'=free_44, V'=Q, W'=-1+T, [ J>=1+free_45 && T>=0 && free_45>=1+free_42 && free_43>=2 ], cost: 1

     11: f10 -> f4 : A1'=B, B'=C, B1'=D, C'=E, C1'=F, D'=G, D1'=H, E'=Q, E1'=free_48, F'=K, F1'=L, G'=free_46, G1'=N, H'=free_50, H1'=P, Q'=free_51, Q1'=free_47, J'=free_49, J1'=T, K'=U, K1'=V, L'=W, L1'=X, M'=Y, M1'=Z, N'=A1, N1'=B1, O'=C1, O1'=D1, P'=E1, P1'=F1, [ free_50>=2 && T>=0 && M==J ], cost: 1

     12: f3 -> f4 : A'=free_61, A1'=free_54, B'=free_65, B1'=free_69, C'=free_58, C1'=F, D'=G, D1'=H, E'=Q, E1'=free_63, F'=K, F1'=X, G'=free_56, G1'=X, H'=free_67, H1'=X, Q'=free_64, Q1'=free_57, J'=free_68, J1'=T, K'=U, K1'=V, L'=W, L1'=free_62, M'=free_55, M1'=free_66, N'=free_59, N1'=free_52, O'=C1, O1'=D1, P'=E1, P1'=F1, [ 0>=free_60 && 0>=free_67 && 0>=free_53 ], cost: 1

     13: f3 -> f1 : A'=free_73, B'=2, B1'=free_70, C'=free_70, C1'=free_71, D'=free_75, E'=free_70, L'=free_76, N'=free_76, O'=free_73, X'=free_72, Y'=free_74, Z'=free_76, [ free_73>=2 ], cost: 1

     17: f3 -> f4 : A'=free_124, A1'=free_117, B'=free_128, B1'=free_132, C'=free_121, C1'=F, D'=G, D1'=H, E'=Q, E1'=free_126, F'=K, F1'=free_119, G'=free_130, G1'=D, H'=1, H1'=free_127, Q'=free_120, Q1'=free_131, J'=free_125, J1'=T, K'=U, K1'=V, L'=W, L1'=free_118, M'=free_129, M1'=free_122, N'=free_116, N1'=free_123, O'=C1, O1'=D1, P'=E1, P1'=F1, [ 0>=1 && free_119>=1+free_127 ], cost: 1

     18: f3 -> f4 : A'=free_141, A1'=free_134, B'=free_145, B1'=free_149, C'=free_138, C1'=F, D'=G, D1'=H, E'=Q, E1'=free_143, F'=K, F1'=free_136, G'=free_147, G1'=D, H'=1, H1'=free_144, Q'=free_137, Q1'=free_148, J'=free_142, J1'=T, K'=U, K1'=V, L'=W, L1'=free_135, M'=free_146, M1'=free_139, N'=free_133, N1'=free_140, O'=C1, O1'=D1, P'=E1, P1'=F1, [ 0>=1 && free_144>=1+free_136 ], cost: 1



Checking for constant complexity:

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

     12: f3 -> f4 : A'=free_61, A1'=free_54, B'=free_65, B1'=free_69, C'=free_58, C1'=F, D'=G, D1'=H, E'=Q, E1'=free_63, F'=K, F1'=X, G'=free_56, G1'=X, H'=free_67, H1'=X, Q'=free_64, Q1'=free_57, J'=free_68, J1'=T, K'=U, K1'=V, L'=W, L1'=free_62, M'=free_55, M1'=free_66, N'=free_59, N1'=free_52, O'=C1, O1'=D1, P'=E1, P1'=F1, [ 0>=free_60 && 0>=free_67 && 0>=free_53 ], cost: 1



Removed unreachable and leaf rules:

   Start location: f3

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

     14: f1 -> f10 : A'=free_82, A1'=free_85, B'=free_77, B1'=free_80, C'=free_86, D'=free_89, D1'=1+T, E'=free_81, E1'=Q, F1'=free_88, J'=C, K'=T, L'=N, M'=N, O'=free_84, P'=C, Q_1'=C, R'=C, S'=free_79, Z'=free_87, [ B>=A && B>=0 && free_83>=free_84 && free_78>=2 && free_77>=free_78 && C>=1+N && free_77>=0 && free_84>=2 && N>=1+C ], cost: 1

     15: f1 -> f10 : A'=free_95, A1'=free_98, B'=free_90, B1'=free_93, C'=free_99, D'=free_102, D1'=1+T, E'=free_94, E1'=Q, F1'=free_101, J'=C, K'=T, L'=N, M'=N, O'=free_97, P'=C, Q_1'=C, R'=C, S'=free_92, Z'=free_100, [ B>=A && B>=0 && free_96>=free_97 && free_91>=2 && free_90>=free_91 && C>=1+N && free_90>=0 && free_97>=2 ], cost: 1

     16: f1 -> f10 : A'=free_108, A1'=free_111, B'=free_103, B1'=free_106, C'=free_112, D'=free_115, D1'=1+T, E'=free_107, E1'=Q, F1'=free_114, J'=C, K'=T, L'=N, M'=N, O'=free_110, P'=C, Q_1'=C, R'=C, S'=free_105, Z'=free_113, [ B>=A && B>=0 && free_109>=free_110 && free_104>=2 && free_103>=free_104 && N>=1+C && free_103>=0 && free_110>=2 ], cost: 1

      7: f10 -> f10 : L'=M, N'=M, O'=free_31, P'=free_30, Q_1'=free_30, R'=J, T'=-1+T, U'=free_32, V'=Q, W'=-1+T, [ free_33>=1+J && T>=0 && free_30>=1+free_33 && free_31>=2 ], cost: 1

      8: f10 -> f10 : L'=M, N'=M, O'=free_35, P'=free_34, Q_1'=free_34, R'=J, T'=-1+T, U'=free_36, V'=Q, W'=-1+T, [ free_37>=1+J && T>=0 && free_37>=1+free_34 && free_35>=2 ], cost: 1

      9: f10 -> f10 : L'=M, N'=M, O'=free_39, P'=free_38, Q_1'=free_38, R'=J, T'=-1+T, U'=free_40, V'=Q, W'=-1+T, [ J>=1+free_41 && T>=0 && free_38>=1+free_41 && free_39>=2 ], cost: 1

     10: f10 -> f10 : L'=M, N'=M, O'=free_43, P'=free_42, Q_1'=free_42, R'=J, T'=-1+T, U'=free_44, V'=Q, W'=-1+T, [ J>=1+free_45 && T>=0 && free_45>=1+free_42 && free_43>=2 ], cost: 1

     13: f3 -> f1 : A'=free_73, B'=2, B1'=free_70, C'=free_70, C1'=free_71, D'=free_75, E'=free_70, L'=free_76, N'=free_76, O'=free_73, X'=free_72, Y'=free_74, Z'=free_76, [ free_73>=2 ], cost: 1



Removed rules with unsatisfiable guard:

   Start location: f3

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

     15: f1 -> f10 : A'=free_95, A1'=free_98, B'=free_90, B1'=free_93, C'=free_99, D'=free_102, D1'=1+T, E'=free_94, E1'=Q, F1'=free_101, J'=C, K'=T, L'=N, M'=N, O'=free_97, P'=C, Q_1'=C, R'=C, S'=free_92, Z'=free_100, [ B>=A && B>=0 && free_96>=free_97 && free_91>=2 && free_90>=free_91 && C>=1+N && free_90>=0 && free_97>=2 ], cost: 1

     16: f1 -> f10 : A'=free_108, A1'=free_111, B'=free_103, B1'=free_106, C'=free_112, D'=free_115, D1'=1+T, E'=free_107, E1'=Q, F1'=free_114, J'=C, K'=T, L'=N, M'=N, O'=free_110, P'=C, Q_1'=C, R'=C, S'=free_105, Z'=free_113, [ B>=A && B>=0 && free_109>=free_110 && free_104>=2 && free_103>=free_104 && N>=1+C && free_103>=0 && free_110>=2 ], cost: 1

      7: f10 -> f10 : L'=M, N'=M, O'=free_31, P'=free_30, Q_1'=free_30, R'=J, T'=-1+T, U'=free_32, V'=Q, W'=-1+T, [ free_33>=1+J && T>=0 && free_30>=1+free_33 && free_31>=2 ], cost: 1

      8: f10 -> f10 : L'=M, N'=M, O'=free_35, P'=free_34, Q_1'=free_34, R'=J, T'=-1+T, U'=free_36, V'=Q, W'=-1+T, [ free_37>=1+J && T>=0 && free_37>=1+free_34 && free_35>=2 ], cost: 1

      9: f10 -> f10 : L'=M, N'=M, O'=free_39, P'=free_38, Q_1'=free_38, R'=J, T'=-1+T, U'=free_40, V'=Q, W'=-1+T, [ J>=1+free_41 && T>=0 && free_38>=1+free_41 && free_39>=2 ], cost: 1

     10: f10 -> f10 : L'=M, N'=M, O'=free_43, P'=free_42, Q_1'=free_42, R'=J, T'=-1+T, U'=free_44, V'=Q, W'=-1+T, [ J>=1+free_45 && T>=0 && free_45>=1+free_42 && free_43>=2 ], cost: 1

     13: f3 -> f1 : A'=free_73, B'=2, B1'=free_70, C'=free_70, C1'=free_71, D'=free_75, E'=free_70, L'=free_76, N'=free_76, O'=free_73, X'=free_72, Y'=free_74, Z'=free_76, [ free_73>=2 ], cost: 1



Removed unreachable and leaf rules:

   Start location: f3

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

     15: f1 -> f10 : A'=free_95, A1'=free_98, B'=free_90, B1'=free_93, C'=free_99, D'=free_102, D1'=1+T, E'=free_94, E1'=Q, F1'=free_101, J'=C, K'=T, L'=N, M'=N, O'=free_97, P'=C, Q_1'=C, R'=C, S'=free_92, Z'=free_100, [ B>=A && B>=0 && free_96>=free_97 && free_91>=2 && free_90>=free_91 && C>=1+N && free_90>=0 && free_97>=2 ], cost: 1

     16: f1 -> f10 : A'=free_108, A1'=free_111, B'=free_103, B1'=free_106, C'=free_112, D'=free_115, D1'=1+T, E'=free_107, E1'=Q, F1'=free_114, J'=C, K'=T, L'=N, M'=N, O'=free_110, P'=C, Q_1'=C, R'=C, S'=free_105, Z'=free_113, [ B>=A && B>=0 && free_109>=free_110 && free_104>=2 && free_103>=free_104 && N>=1+C && free_103>=0 && free_110>=2 ], cost: 1

      7: f10 -> f10 : L'=M, N'=M, O'=free_31, P'=free_30, Q_1'=free_30, R'=J, T'=-1+T, U'=free_32, V'=Q, W'=-1+T, [ free_33>=1+J && T>=0 && free_30>=1+free_33 && free_31>=2 ], cost: 1

      8: f10 -> f10 : L'=M, N'=M, O'=free_35, P'=free_34, Q_1'=free_34, R'=J, T'=-1+T, U'=free_36, V'=Q, W'=-1+T, [ free_37>=1+J && T>=0 && free_37>=1+free_34 && free_35>=2 ], cost: 1

      9: f10 -> f10 : L'=M, N'=M, O'=free_39, P'=free_38, Q_1'=free_38, R'=J, T'=-1+T, U'=free_40, V'=Q, W'=-1+T, [ J>=1+free_41 && T>=0 && free_38>=1+free_41 && free_39>=2 ], cost: 1

     10: f10 -> f10 : L'=M, N'=M, O'=free_43, P'=free_42, Q_1'=free_42, R'=J, T'=-1+T, U'=free_44, V'=Q, W'=-1+T, [ J>=1+free_45 && T>=0 && free_45>=1+free_42 && free_43>=2 ], cost: 1

     13: f3 -> f1 : A'=free_73, B'=2, B1'=free_70, C'=free_70, C1'=free_71, D'=free_75, E'=free_70, L'=free_76, N'=free_76, O'=free_73, X'=free_72, Y'=free_74, Z'=free_76, [ free_73>=2 ], cost: 1



Simplified all rules, resulting in:

   Start location: f3

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

     15: f1 -> f10 : A'=free_95, A1'=free_98, B'=free_90, B1'=free_93, C'=free_99, D'=free_102, D1'=1+T, E'=free_94, E1'=Q, F1'=free_101, J'=C, K'=T, L'=N, M'=N, O'=free_97, P'=C, Q_1'=C, R'=C, S'=free_92, Z'=free_100, [ B>=A && B>=0 && C>=1+N && free_97>=2 && 2<=free_90 ], cost: 1

     16: f1 -> f10 : A'=free_108, A1'=free_111, B'=free_103, B1'=free_106, C'=free_112, D'=free_115, D1'=1+T, E'=free_107, E1'=Q, F1'=free_114, J'=C, K'=T, L'=N, M'=N, O'=free_110, P'=C, Q_1'=C, R'=C, S'=free_105, Z'=free_113, [ B>=A && B>=0 && N>=1+C && free_110>=2 && 2<=free_103 ], cost: 1

      7: f10 -> f10 : L'=M, N'=M, O'=free_31, P'=free_30, Q_1'=free_30, R'=J, T'=-1+T, U'=free_32, V'=Q, W'=-1+T, [ T>=0 && free_31>=2 && 1+J<=-1+free_30 ], cost: 1

      8: f10 -> f10 : L'=M, N'=M, O'=free_35, P'=free_34, Q_1'=free_34, R'=J, T'=-1+T, U'=free_36, V'=Q, W'=-1+T, [ T>=0 && free_35>=2 ], cost: 1

      9: f10 -> f10 : L'=M, N'=M, O'=free_39, P'=free_38, Q_1'=free_38, R'=J, T'=-1+T, U'=free_40, V'=Q, W'=-1+T, [ T>=0 && free_39>=2 ], cost: 1

     10: f10 -> f10 : L'=M, N'=M, O'=free_43, P'=free_42, Q_1'=free_42, R'=J, T'=-1+T, U'=free_44, V'=Q, W'=-1+T, [ T>=0 && free_43>=2 && 1+free_42<=-1+J ], cost: 1

     13: f3 -> f1 : A'=free_73, B'=2, B1'=free_70, C'=free_70, C1'=free_71, D'=free_75, E'=free_70, L'=free_76, N'=free_76, O'=free_73, X'=free_72, Y'=free_74, Z'=free_76, [ free_73>=2 ], cost: 1



### Simplification by acceleration and chaining ###



Accelerating simple loops of location 0.

   Accelerating the following rules:

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



   Accelerated rule 0 with metering function -B+A, yielding the new rule 19.

   Removing the simple loops: 0.



Accelerating simple loops of location 2.

   Accelerating the following rules:

      7: f10 -> f10 : L'=M, N'=M, O'=free_31, P'=free_30, Q_1'=free_30, R'=J, T'=-1+T, U'=free_32, V'=Q, W'=-1+T, [ T>=0 && free_31>=2 && 1+J<=-1+free_30 ], cost: 1

      8: f10 -> f10 : L'=M, N'=M, O'=free_35, P'=free_34, Q_1'=free_34, R'=J, T'=-1+T, U'=free_36, V'=Q, W'=-1+T, [ T>=0 && free_35>=2 ], cost: 1

      9: f10 -> f10 : L'=M, N'=M, O'=free_39, P'=free_38, Q_1'=free_38, R'=J, T'=-1+T, U'=free_40, V'=Q, W'=-1+T, [ T>=0 && free_39>=2 ], cost: 1

     10: f10 -> f10 : L'=M, N'=M, O'=free_43, P'=free_42, Q_1'=free_42, R'=J, T'=-1+T, U'=free_44, V'=Q, W'=-1+T, [ T>=0 && free_43>=2 && 1+free_42<=-1+J ], cost: 1



   Accelerated rule 7 with metering function 1+T, yielding the new rule 20.

   Accelerated rule 8 with metering function 1+T, yielding the new rule 21.

   Accelerated rule 9 with metering function 1+T, yielding the new rule 22.

   Accelerated rule 10 with metering function 1+T, yielding the new rule 23.

   Removing the simple loops: 7 8 9 10.



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

   Start location: f3

     15: f1 -> f10 : A'=free_95, A1'=free_98, B'=free_90, B1'=free_93, C'=free_99, D'=free_102, D1'=1+T, E'=free_94, E1'=Q, F1'=free_101, J'=C, K'=T, L'=N, M'=N, O'=free_97, P'=C, Q_1'=C, R'=C, S'=free_92, Z'=free_100, [ B>=A && B>=0 && C>=1+N && free_97>=2 && 2<=free_90 ], cost: 1

     16: f1 -> f10 : A'=free_108, A1'=free_111, B'=free_103, B1'=free_106, C'=free_112, D'=free_115, D1'=1+T, E'=free_107, E1'=Q, F1'=free_114, J'=C, K'=T, L'=N, M'=N, O'=free_110, P'=C, Q_1'=C, R'=C, S'=free_105, Z'=free_113, [ B>=A && B>=0 && N>=1+C && free_110>=2 && 2<=free_103 ], cost: 1

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

     20: f10 -> f10 : L'=M, N'=M, O'=free_31, P'=free_30, Q_1'=free_30, R'=J, T'=-1, U'=free_32, V'=Q, W'=-1, [ T>=0 && free_31>=2 && 1+J<=-1+free_30 ], cost: 1+T

     21: f10 -> f10 : L'=M, N'=M, O'=free_35, P'=free_34, Q_1'=free_34, R'=J, T'=-1, U'=free_36, V'=Q, W'=-1, [ T>=0 && free_35>=2 ], cost: 1+T

     22: f10 -> f10 : L'=M, N'=M, O'=free_39, P'=free_38, Q_1'=free_38, R'=J, T'=-1, U'=free_40, V'=Q, W'=-1, [ T>=0 && free_39>=2 ], cost: 1+T

     23: f10 -> f10 : L'=M, N'=M, O'=free_43, P'=free_42, Q_1'=free_42, R'=J, T'=-1, U'=free_44, V'=Q, W'=-1, [ T>=0 && free_43>=2 && 1+free_42<=-1+J ], cost: 1+T

     13: f3 -> f1 : A'=free_73, B'=2, B1'=free_70, C'=free_70, C1'=free_71, D'=free_75, E'=free_70, L'=free_76, N'=free_76, O'=free_73, X'=free_72, Y'=free_74, Z'=free_76, [ free_73>=2 ], cost: 1



Chained accelerated rules (with incoming rules):

   Start location: f3

     15: f1 -> f10 : A'=free_95, A1'=free_98, B'=free_90, B1'=free_93, C'=free_99, D'=free_102, D1'=1+T, E'=free_94, E1'=Q, F1'=free_101, J'=C, K'=T, L'=N, M'=N, O'=free_97, P'=C, Q_1'=C, R'=C, S'=free_92, Z'=free_100, [ B>=A && B>=0 && C>=1+N && free_97>=2 && 2<=free_90 ], cost: 1

     16: f1 -> f10 : A'=free_108, A1'=free_111, B'=free_103, B1'=free_106, C'=free_112, D'=free_115, D1'=1+T, E'=free_107, E1'=Q, F1'=free_114, J'=C, K'=T, L'=N, M'=N, O'=free_110, P'=C, Q_1'=C, R'=C, S'=free_105, Z'=free_113, [ B>=A && B>=0 && N>=1+C && free_110>=2 && 2<=free_103 ], cost: 1

     25: f1 -> f10 : A'=free_95, A1'=free_98, B'=free_90, B1'=free_93, C'=free_99, D'=free_102, D1'=1+T, E'=free_94, E1'=Q, F1'=free_101, J'=C, K'=T, L'=N, M'=N, O'=free_31, P'=free_30, Q_1'=free_30, R'=C, S'=free_92, T'=-1, U'=free_32, V'=Q, W'=-1, Z'=free_100, [ B>=A && B>=0 && C>=1+N && 2<=free_90 && T>=0 && free_31>=2 && 1+C<=-1+free_30 ], cost: 2+T

     26: f1 -> f10 : A'=free_108, A1'=free_111, B'=free_103, B1'=free_106, C'=free_112, D'=free_115, D1'=1+T, E'=free_107, E1'=Q, F1'=free_114, J'=C, K'=T, L'=N, M'=N, O'=free_31, P'=free_30, Q_1'=free_30, R'=C, S'=free_105, T'=-1, U'=free_32, V'=Q, W'=-1, Z'=free_113, [ B>=A && B>=0 && N>=1+C && 2<=free_103 && T>=0 && free_31>=2 && 1+C<=-1+free_30 ], cost: 2+T

     27: f1 -> f10 : A'=free_95, A1'=free_98, B'=free_90, B1'=free_93, C'=free_99, D'=free_102, D1'=1+T, E'=free_94, E1'=Q, F1'=free_101, J'=C, K'=T, L'=N, M'=N, O'=free_35, P'=free_34, Q_1'=free_34, R'=C, S'=free_92, T'=-1, U'=free_36, V'=Q, W'=-1, Z'=free_100, [ B>=A && B>=0 && C>=1+N && 2<=free_90 && T>=0 && free_35>=2 ], cost: 2+T

     28: f1 -> f10 : A'=free_108, A1'=free_111, B'=free_103, B1'=free_106, C'=free_112, D'=free_115, D1'=1+T, E'=free_107, E1'=Q, F1'=free_114, J'=C, K'=T, L'=N, M'=N, O'=free_35, P'=free_34, Q_1'=free_34, R'=C, S'=free_105, T'=-1, U'=free_36, V'=Q, W'=-1, Z'=free_113, [ B>=A && B>=0 && N>=1+C && 2<=free_103 && T>=0 && free_35>=2 ], cost: 2+T

     29: f1 -> f10 : A'=free_95, A1'=free_98, B'=free_90, B1'=free_93, C'=free_99, D'=free_102, D1'=1+T, E'=free_94, E1'=Q, F1'=free_101, J'=C, K'=T, L'=N, M'=N, O'=free_39, P'=free_38, Q_1'=free_38, R'=C, S'=free_92, T'=-1, U'=free_40, V'=Q, W'=-1, Z'=free_100, [ B>=A && B>=0 && C>=1+N && 2<=free_90 && T>=0 && free_39>=2 ], cost: 2+T

     30: f1 -> f10 : A'=free_108, A1'=free_111, B'=free_103, B1'=free_106, C'=free_112, D'=free_115, D1'=1+T, E'=free_107, E1'=Q, F1'=free_114, J'=C, K'=T, L'=N, M'=N, O'=free_39, P'=free_38, Q_1'=free_38, R'=C, S'=free_105, T'=-1, U'=free_40, V'=Q, W'=-1, Z'=free_113, [ B>=A && B>=0 && N>=1+C && 2<=free_103 && T>=0 && free_39>=2 ], cost: 2+T

     31: f1 -> f10 : A'=free_95, A1'=free_98, B'=free_90, B1'=free_93, C'=free_99, D'=free_102, D1'=1+T, E'=free_94, E1'=Q, F1'=free_101, J'=C, K'=T, L'=N, M'=N, O'=free_43, P'=free_42, Q_1'=free_42, R'=C, S'=free_92, T'=-1, U'=free_44, V'=Q, W'=-1, Z'=free_100, [ B>=A && B>=0 && C>=1+N && 2<=free_90 && T>=0 && free_43>=2 && 1+free_42<=-1+C ], cost: 2+T

     32: f1 -> f10 : A'=free_108, A1'=free_111, B'=free_103, B1'=free_106, C'=free_112, D'=free_115, D1'=1+T, E'=free_107, E1'=Q, F1'=free_114, J'=C, K'=T, L'=N, M'=N, O'=free_43, P'=free_42, Q_1'=free_42, R'=C, S'=free_105, T'=-1, U'=free_44, V'=Q, W'=-1, Z'=free_113, [ B>=A && B>=0 && N>=1+C && 2<=free_103 && T>=0 && free_43>=2 && 1+free_42<=-1+C ], cost: 2+T

     13: f3 -> f1 : A'=free_73, B'=2, B1'=free_70, C'=free_70, C1'=free_71, D'=free_75, E'=free_70, L'=free_76, N'=free_76, O'=free_73, X'=free_72, Y'=free_74, Z'=free_76, [ free_73>=2 ], cost: 1

     24: f3 -> f1 : A'=free_73, B'=free_73, B1'=free_70, C'=free_1, C1'=free_71, D'=free_1, E'=free_1, F'=free, G'=-1+free_73, H'=Q, L'=free_76, N'=free_76, O'=free_73, X'=free_72, Y'=free_74, Z'=free_76, [ free_73>=3 ], cost: -1+free_73



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

   Start location: f3

     25: f1 -> f10 : A'=free_95, A1'=free_98, B'=free_90, B1'=free_93, C'=free_99, D'=free_102, D1'=1+T, E'=free_94, E1'=Q, F1'=free_101, J'=C, K'=T, L'=N, M'=N, O'=free_31, P'=free_30, Q_1'=free_30, R'=C, S'=free_92, T'=-1, U'=free_32, V'=Q, W'=-1, Z'=free_100, [ B>=A && B>=0 && C>=1+N && 2<=free_90 && T>=0 && free_31>=2 && 1+C<=-1+free_30 ], cost: 2+T

     26: f1 -> f10 : A'=free_108, A1'=free_111, B'=free_103, B1'=free_106, C'=free_112, D'=free_115, D1'=1+T, E'=free_107, E1'=Q, F1'=free_114, J'=C, K'=T, L'=N, M'=N, O'=free_31, P'=free_30, Q_1'=free_30, R'=C, S'=free_105, T'=-1, U'=free_32, V'=Q, W'=-1, Z'=free_113, [ B>=A && B>=0 && N>=1+C && 2<=free_103 && T>=0 && free_31>=2 && 1+C<=-1+free_30 ], cost: 2+T

     27: f1 -> f10 : A'=free_95, A1'=free_98, B'=free_90, B1'=free_93, C'=free_99, D'=free_102, D1'=1+T, E'=free_94, E1'=Q, F1'=free_101, J'=C, K'=T, L'=N, M'=N, O'=free_35, P'=free_34, Q_1'=free_34, R'=C, S'=free_92, T'=-1, U'=free_36, V'=Q, W'=-1, Z'=free_100, [ B>=A && B>=0 && C>=1+N && 2<=free_90 && T>=0 && free_35>=2 ], cost: 2+T

     28: f1 -> f10 : A'=free_108, A1'=free_111, B'=free_103, B1'=free_106, C'=free_112, D'=free_115, D1'=1+T, E'=free_107, E1'=Q, F1'=free_114, J'=C, K'=T, L'=N, M'=N, O'=free_35, P'=free_34, Q_1'=free_34, R'=C, S'=free_105, T'=-1, U'=free_36, V'=Q, W'=-1, Z'=free_113, [ B>=A && B>=0 && N>=1+C && 2<=free_103 && T>=0 && free_35>=2 ], cost: 2+T

     29: f1 -> f10 : A'=free_95, A1'=free_98, B'=free_90, B1'=free_93, C'=free_99, D'=free_102, D1'=1+T, E'=free_94, E1'=Q, F1'=free_101, J'=C, K'=T, L'=N, M'=N, O'=free_39, P'=free_38, Q_1'=free_38, R'=C, S'=free_92, T'=-1, U'=free_40, V'=Q, W'=-1, Z'=free_100, [ B>=A && B>=0 && C>=1+N && 2<=free_90 && T>=0 && free_39>=2 ], cost: 2+T

     30: f1 -> f10 : A'=free_108, A1'=free_111, B'=free_103, B1'=free_106, C'=free_112, D'=free_115, D1'=1+T, E'=free_107, E1'=Q, F1'=free_114, J'=C, K'=T, L'=N, M'=N, O'=free_39, P'=free_38, Q_1'=free_38, R'=C, S'=free_105, T'=-1, U'=free_40, V'=Q, W'=-1, Z'=free_113, [ B>=A && B>=0 && N>=1+C && 2<=free_103 && T>=0 && free_39>=2 ], cost: 2+T

     31: f1 -> f10 : A'=free_95, A1'=free_98, B'=free_90, B1'=free_93, C'=free_99, D'=free_102, D1'=1+T, E'=free_94, E1'=Q, F1'=free_101, J'=C, K'=T, L'=N, M'=N, O'=free_43, P'=free_42, Q_1'=free_42, R'=C, S'=free_92, T'=-1, U'=free_44, V'=Q, W'=-1, Z'=free_100, [ B>=A && B>=0 && C>=1+N && 2<=free_90 && T>=0 && free_43>=2 && 1+free_42<=-1+C ], cost: 2+T

     32: f1 -> f10 : A'=free_108, A1'=free_111, B'=free_103, B1'=free_106, C'=free_112, D'=free_115, D1'=1+T, E'=free_107, E1'=Q, F1'=free_114, J'=C, K'=T, L'=N, M'=N, O'=free_43, P'=free_42, Q_1'=free_42, R'=C, S'=free_105, T'=-1, U'=free_44, V'=Q, W'=-1, Z'=free_113, [ B>=A && B>=0 && N>=1+C && 2<=free_103 && T>=0 && free_43>=2 && 1+free_42<=-1+C ], cost: 2+T

     13: f3 -> f1 : A'=free_73, B'=2, B1'=free_70, C'=free_70, C1'=free_71, D'=free_75, E'=free_70, L'=free_76, N'=free_76, O'=free_73, X'=free_72, Y'=free_74, Z'=free_76, [ free_73>=2 ], cost: 1

     24: f3 -> f1 : A'=free_73, B'=free_73, B1'=free_70, C'=free_1, C1'=free_71, D'=free_1, E'=free_1, F'=free, G'=-1+free_73, H'=Q, L'=free_76, N'=free_76, O'=free_73, X'=free_72, Y'=free_74, Z'=free_76, [ free_73>=3 ], cost: -1+free_73



Eliminated locations (on tree-shaped paths):

   Start location: f3

     33: f3 -> f10 : A'=free_95, A1'=free_98, B'=free_90, B1'=free_93, C'=free_99, C1'=free_71, D'=free_102, D1'=1+T, E'=free_94, E1'=Q, F1'=free_101, J'=free_70, K'=T, L'=free_76, M'=free_76, N'=free_76, O'=free_31, P'=free_30, Q_1'=free_30, R'=free_70, S'=free_92, T'=-1, U'=free_32, V'=Q, W'=-1, X'=free_72, Y'=free_74, Z'=free_100, [ free_73>=2 && 2>=free_73 && free_70>=1+free_76 && 2<=free_90 && T>=0 && free_31>=2 && 1+free_70<=-1+free_30 ], cost: 3+T

     34: f3 -> f10 : A'=free_108, A1'=free_111, B'=free_103, B1'=free_106, C'=free_112, C1'=free_71, D'=free_115, D1'=1+T, E'=free_107, E1'=Q, F1'=free_114, J'=free_70, K'=T, L'=free_76, M'=free_76, N'=free_76, O'=free_31, P'=free_30, Q_1'=free_30, R'=free_70, S'=free_105, T'=-1, U'=free_32, V'=Q, W'=-1, X'=free_72, Y'=free_74, Z'=free_113, [ free_73>=2 && 2>=free_73 && free_76>=1+free_70 && 2<=free_103 && T>=0 && free_31>=2 && 1+free_70<=-1+free_30 ], cost: 3+T

     35: f3 -> f10 : A'=free_95, A1'=free_98, B'=free_90, B1'=free_93, C'=free_99, C1'=free_71, D'=free_102, D1'=1+T, E'=free_94, E1'=Q, F1'=free_101, J'=free_70, K'=T, L'=free_76, M'=free_76, N'=free_76, O'=free_35, P'=free_34, Q_1'=free_34, R'=free_70, S'=free_92, T'=-1, U'=free_36, V'=Q, W'=-1, X'=free_72, Y'=free_74, Z'=free_100, [ free_73>=2 && 2>=free_73 && free_70>=1+free_76 && 2<=free_90 && T>=0 && free_35>=2 ], cost: 3+T

     36: f3 -> f10 : A'=free_108, A1'=free_111, B'=free_103, B1'=free_106, C'=free_112, C1'=free_71, D'=free_115, D1'=1+T, E'=free_107, E1'=Q, F1'=free_114, J'=free_70, K'=T, L'=free_76, M'=free_76, N'=free_76, O'=free_35, P'=free_34, Q_1'=free_34, R'=free_70, S'=free_105, T'=-1, U'=free_36, V'=Q, W'=-1, X'=free_72, Y'=free_74, Z'=free_113, [ free_73>=2 && 2>=free_73 && free_76>=1+free_70 && 2<=free_103 && T>=0 && free_35>=2 ], cost: 3+T

     37: f3 -> f10 : A'=free_95, A1'=free_98, B'=free_90, B1'=free_93, C'=free_99, C1'=free_71, D'=free_102, D1'=1+T, E'=free_94, E1'=Q, F1'=free_101, J'=free_70, K'=T, L'=free_76, M'=free_76, N'=free_76, O'=free_39, P'=free_38, Q_1'=free_38, R'=free_70, S'=free_92, T'=-1, U'=free_40, V'=Q, W'=-1, X'=free_72, Y'=free_74, Z'=free_100, [ free_73>=2 && 2>=free_73 && free_70>=1+free_76 && 2<=free_90 && T>=0 && free_39>=2 ], cost: 3+T

     38: f3 -> f10 : A'=free_108, A1'=free_111, B'=free_103, B1'=free_106, C'=free_112, C1'=free_71, D'=free_115, D1'=1+T, E'=free_107, E1'=Q, F1'=free_114, J'=free_70, K'=T, L'=free_76, M'=free_76, N'=free_76, O'=free_39, P'=free_38, Q_1'=free_38, R'=free_70, S'=free_105, T'=-1, U'=free_40, V'=Q, W'=-1, X'=free_72, Y'=free_74, Z'=free_113, [ free_73>=2 && 2>=free_73 && free_76>=1+free_70 && 2<=free_103 && T>=0 && free_39>=2 ], cost: 3+T

     39: f3 -> f10 : A'=free_95, A1'=free_98, B'=free_90, B1'=free_93, C'=free_99, C1'=free_71, D'=free_102, D1'=1+T, E'=free_94, E1'=Q, F1'=free_101, J'=free_70, K'=T, L'=free_76, M'=free_76, N'=free_76, O'=free_43, P'=free_42, Q_1'=free_42, R'=free_70, S'=free_92, T'=-1, U'=free_44, V'=Q, W'=-1, X'=free_72, Y'=free_74, Z'=free_100, [ free_73>=2 && 2>=free_73 && free_70>=1+free_76 && 2<=free_90 && T>=0 && free_43>=2 && 1+free_42<=-1+free_70 ], cost: 3+T

     40: f3 -> f10 : A'=free_108, A1'=free_111, B'=free_103, B1'=free_106, C'=free_112, C1'=free_71, D'=free_115, D1'=1+T, E'=free_107, E1'=Q, F1'=free_114, J'=free_70, K'=T, L'=free_76, M'=free_76, N'=free_76, O'=free_43, P'=free_42, Q_1'=free_42, R'=free_70, S'=free_105, T'=-1, U'=free_44, V'=Q, W'=-1, X'=free_72, Y'=free_74, Z'=free_113, [ free_73>=2 && 2>=free_73 && free_76>=1+free_70 && 2<=free_103 && T>=0 && free_43>=2 && 1+free_42<=-1+free_70 ], cost: 3+T

     41: f3 -> f10 : A'=free_95, A1'=free_98, B'=free_90, B1'=free_93, C'=free_99, C1'=free_71, D'=free_102, D1'=1+T, E'=free_94, E1'=Q, F'=free, F1'=free_101, G'=-1+free_73, H'=Q, J'=free_1, K'=T, L'=free_76, M'=free_76, N'=free_76, O'=free_31, P'=free_30, Q_1'=free_30, R'=free_1, S'=free_92, T'=-1, U'=free_32, V'=Q, W'=-1, X'=free_72, Y'=free_74, Z'=free_100, [ free_73>=3 && free_1>=1+free_76 && 2<=free_90 && T>=0 && free_31>=2 && 1+free_1<=-1+free_30 ], cost: 1+T+free_73

     42: f3 -> f10 : A'=free_108, A1'=free_111, B'=free_103, B1'=free_106, C'=free_112, C1'=free_71, D'=free_115, D1'=1+T, E'=free_107, E1'=Q, F'=free, F1'=free_114, G'=-1+free_73, H'=Q, J'=free_1, K'=T, L'=free_76, M'=free_76, N'=free_76, O'=free_31, P'=free_30, Q_1'=free_30, R'=free_1, S'=free_105, T'=-1, U'=free_32, V'=Q, W'=-1, X'=free_72, Y'=free_74, Z'=free_113, [ free_73>=3 && free_76>=1+free_1 && 2<=free_103 && T>=0 && free_31>=2 && 1+free_1<=-1+free_30 ], cost: 1+T+free_73

     43: f3 -> f10 : A'=free_95, A1'=free_98, B'=free_90, B1'=free_93, C'=free_99, C1'=free_71, D'=free_102, D1'=1+T, E'=free_94, E1'=Q, F'=free, F1'=free_101, G'=-1+free_73, H'=Q, J'=free_1, K'=T, L'=free_76, M'=free_76, N'=free_76, O'=free_35, P'=free_34, Q_1'=free_34, R'=free_1, S'=free_92, T'=-1, U'=free_36, V'=Q, W'=-1, X'=free_72, Y'=free_74, Z'=free_100, [ free_73>=3 && free_1>=1+free_76 && 2<=free_90 && T>=0 && free_35>=2 ], cost: 1+T+free_73

     44: f3 -> f10 : A'=free_108, A1'=free_111, B'=free_103, B1'=free_106, C'=free_112, C1'=free_71, D'=free_115, D1'=1+T, E'=free_107, E1'=Q, F'=free, F1'=free_114, G'=-1+free_73, H'=Q, J'=free_1, K'=T, L'=free_76, M'=free_76, N'=free_76, O'=free_35, P'=free_34, Q_1'=free_34, R'=free_1, S'=free_105, T'=-1, U'=free_36, V'=Q, W'=-1, X'=free_72, Y'=free_74, Z'=free_113, [ free_73>=3 && free_76>=1+free_1 && 2<=free_103 && T>=0 && free_35>=2 ], cost: 1+T+free_73

     45: f3 -> f10 : A'=free_95, A1'=free_98, B'=free_90, B1'=free_93, C'=free_99, C1'=free_71, D'=free_102, D1'=1+T, E'=free_94, E1'=Q, F'=free, F1'=free_101, G'=-1+free_73, H'=Q, J'=free_1, K'=T, L'=free_76, M'=free_76, N'=free_76, O'=free_39, P'=free_38, Q_1'=free_38, R'=free_1, S'=free_92, T'=-1, U'=free_40, V'=Q, W'=-1, X'=free_72, Y'=free_74, Z'=free_100, [ free_73>=3 && free_1>=1+free_76 && 2<=free_90 && T>=0 && free_39>=2 ], cost: 1+T+free_73

     46: f3 -> f10 : A'=free_108, A1'=free_111, B'=free_103, B1'=free_106, C'=free_112, C1'=free_71, D'=free_115, D1'=1+T, E'=free_107, E1'=Q, F'=free, F1'=free_114, G'=-1+free_73, H'=Q, J'=free_1, K'=T, L'=free_76, M'=free_76, N'=free_76, O'=free_39, P'=free_38, Q_1'=free_38, R'=free_1, S'=free_105, T'=-1, U'=free_40, V'=Q, W'=-1, X'=free_72, Y'=free_74, Z'=free_113, [ free_73>=3 && free_76>=1+free_1 && 2<=free_103 && T>=0 && free_39>=2 ], cost: 1+T+free_73

     47: f3 -> f10 : A'=free_95, A1'=free_98, B'=free_90, B1'=free_93, C'=free_99, C1'=free_71, D'=free_102, D1'=1+T, E'=free_94, E1'=Q, F'=free, F1'=free_101, G'=-1+free_73, H'=Q, J'=free_1, K'=T, L'=free_76, M'=free_76, N'=free_76, O'=free_43, P'=free_42, Q_1'=free_42, R'=free_1, S'=free_92, T'=-1, U'=free_44, V'=Q, W'=-1, X'=free_72, Y'=free_74, Z'=free_100, [ free_73>=3 && free_1>=1+free_76 && 2<=free_90 && T>=0 && free_43>=2 && 1+free_42<=-1+free_1 ], cost: 1+T+free_73

     48: f3 -> f10 : A'=free_108, A1'=free_111, B'=free_103, B1'=free_106, C'=free_112, C1'=free_71, D'=free_115, D1'=1+T, E'=free_107, E1'=Q, F'=free, F1'=free_114, G'=-1+free_73, H'=Q, J'=free_1, K'=T, L'=free_76, M'=free_76, N'=free_76, O'=free_43, P'=free_42, Q_1'=free_42, R'=free_1, S'=free_105, T'=-1, U'=free_44, V'=Q, W'=-1, X'=free_72, Y'=free_74, Z'=free_113, [ free_73>=3 && free_76>=1+free_1 && 2<=free_103 && T>=0 && free_43>=2 && 1+free_42<=-1+free_1 ], cost: 1+T+free_73



Applied pruning (of leafs and parallel rules):

   Start location: f3

     42: f3 -> f10 : A'=free_108, A1'=free_111, B'=free_103, B1'=free_106, C'=free_112, C1'=free_71, D'=free_115, D1'=1+T, E'=free_107, E1'=Q, F'=free, F1'=free_114, G'=-1+free_73, H'=Q, J'=free_1, K'=T, L'=free_76, M'=free_76, N'=free_76, O'=free_31, P'=free_30, Q_1'=free_30, R'=free_1, S'=free_105, T'=-1, U'=free_32, V'=Q, W'=-1, X'=free_72, Y'=free_74, Z'=free_113, [ free_73>=3 && free_76>=1+free_1 && 2<=free_103 && T>=0 && free_31>=2 && 1+free_1<=-1+free_30 ], cost: 1+T+free_73

     43: f3 -> f10 : A'=free_95, A1'=free_98, B'=free_90, B1'=free_93, C'=free_99, C1'=free_71, D'=free_102, D1'=1+T, E'=free_94, E1'=Q, F'=free, F1'=free_101, G'=-1+free_73, H'=Q, J'=free_1, K'=T, L'=free_76, M'=free_76, N'=free_76, O'=free_35, P'=free_34, Q_1'=free_34, R'=free_1, S'=free_92, T'=-1, U'=free_36, V'=Q, W'=-1, X'=free_72, Y'=free_74, Z'=free_100, [ free_73>=3 && free_1>=1+free_76 && 2<=free_90 && T>=0 && free_35>=2 ], cost: 1+T+free_73

     46: f3 -> f10 : A'=free_108, A1'=free_111, B'=free_103, B1'=free_106, C'=free_112, C1'=free_71, D'=free_115, D1'=1+T, E'=free_107, E1'=Q, F'=free, F1'=free_114, G'=-1+free_73, H'=Q, J'=free_1, K'=T, L'=free_76, M'=free_76, N'=free_76, O'=free_39, P'=free_38, Q_1'=free_38, R'=free_1, S'=free_105, T'=-1, U'=free_40, V'=Q, W'=-1, X'=free_72, Y'=free_74, Z'=free_113, [ free_73>=3 && free_76>=1+free_1 && 2<=free_103 && T>=0 && free_39>=2 ], cost: 1+T+free_73

     47: f3 -> f10 : A'=free_95, A1'=free_98, B'=free_90, B1'=free_93, C'=free_99, C1'=free_71, D'=free_102, D1'=1+T, E'=free_94, E1'=Q, F'=free, F1'=free_101, G'=-1+free_73, H'=Q, J'=free_1, K'=T, L'=free_76, M'=free_76, N'=free_76, O'=free_43, P'=free_42, Q_1'=free_42, R'=free_1, S'=free_92, T'=-1, U'=free_44, V'=Q, W'=-1, X'=free_72, Y'=free_74, Z'=free_100, [ free_73>=3 && free_1>=1+free_76 && 2<=free_90 && T>=0 && free_43>=2 && 1+free_42<=-1+free_1 ], cost: 1+T+free_73

     48: f3 -> f10 : A'=free_108, A1'=free_111, B'=free_103, B1'=free_106, C'=free_112, C1'=free_71, D'=free_115, D1'=1+T, E'=free_107, E1'=Q, F'=free, F1'=free_114, G'=-1+free_73, H'=Q, J'=free_1, K'=T, L'=free_76, M'=free_76, N'=free_76, O'=free_43, P'=free_42, Q_1'=free_42, R'=free_1, S'=free_105, T'=-1, U'=free_44, V'=Q, W'=-1, X'=free_72, Y'=free_74, Z'=free_113, [ free_73>=3 && free_76>=1+free_1 && 2<=free_103 && T>=0 && free_43>=2 && 1+free_42<=-1+free_1 ], cost: 1+T+free_73



### Computing asymptotic complexity ###



Fully simplified ITS problem

   Start location: f3

     42: f3 -> f10 : A'=free_108, A1'=free_111, B'=free_103, B1'=free_106, C'=free_112, C1'=free_71, D'=free_115, D1'=1+T, E'=free_107, E1'=Q, F'=free, F1'=free_114, G'=-1+free_73, H'=Q, J'=free_1, K'=T, L'=free_76, M'=free_76, N'=free_76, O'=free_31, P'=free_30, Q_1'=free_30, R'=free_1, S'=free_105, T'=-1, U'=free_32, V'=Q, W'=-1, X'=free_72, Y'=free_74, Z'=free_113, [ free_73>=3 && free_76>=1+free_1 && 2<=free_103 && T>=0 && free_31>=2 && 1+free_1<=-1+free_30 ], cost: 1+T+free_73

     43: f3 -> f10 : A'=free_95, A1'=free_98, B'=free_90, B1'=free_93, C'=free_99, C1'=free_71, D'=free_102, D1'=1+T, E'=free_94, E1'=Q, F'=free, F1'=free_101, G'=-1+free_73, H'=Q, J'=free_1, K'=T, L'=free_76, M'=free_76, N'=free_76, O'=free_35, P'=free_34, Q_1'=free_34, R'=free_1, S'=free_92, T'=-1, U'=free_36, V'=Q, W'=-1, X'=free_72, Y'=free_74, Z'=free_100, [ free_73>=3 && free_1>=1+free_76 && 2<=free_90 && T>=0 && free_35>=2 ], cost: 1+T+free_73

     46: f3 -> f10 : A'=free_108, A1'=free_111, B'=free_103, B1'=free_106, C'=free_112, C1'=free_71, D'=free_115, D1'=1+T, E'=free_107, E1'=Q, F'=free, F1'=free_114, G'=-1+free_73, H'=Q, J'=free_1, K'=T, L'=free_76, M'=free_76, N'=free_76, O'=free_39, P'=free_38, Q_1'=free_38, R'=free_1, S'=free_105, T'=-1, U'=free_40, V'=Q, W'=-1, X'=free_72, Y'=free_74, Z'=free_113, [ free_73>=3 && free_76>=1+free_1 && 2<=free_103 && T>=0 && free_39>=2 ], cost: 1+T+free_73

     47: f3 -> f10 : A'=free_95, A1'=free_98, B'=free_90, B1'=free_93, C'=free_99, C1'=free_71, D'=free_102, D1'=1+T, E'=free_94, E1'=Q, F'=free, F1'=free_101, G'=-1+free_73, H'=Q, J'=free_1, K'=T, L'=free_76, M'=free_76, N'=free_76, O'=free_43, P'=free_42, Q_1'=free_42, R'=free_1, S'=free_92, T'=-1, U'=free_44, V'=Q, W'=-1, X'=free_72, Y'=free_74, Z'=free_100, [ free_73>=3 && free_1>=1+free_76 && 2<=free_90 && T>=0 && free_43>=2 && 1+free_42<=-1+free_1 ], cost: 1+T+free_73

     48: f3 -> f10 : A'=free_108, A1'=free_111, B'=free_103, B1'=free_106, C'=free_112, C1'=free_71, D'=free_115, D1'=1+T, E'=free_107, E1'=Q, F'=free, F1'=free_114, G'=-1+free_73, H'=Q, J'=free_1, K'=T, L'=free_76, M'=free_76, N'=free_76, O'=free_43, P'=free_42, Q_1'=free_42, R'=free_1, S'=free_105, T'=-1, U'=free_44, V'=Q, W'=-1, X'=free_72, Y'=free_74, Z'=free_113, [ free_73>=3 && free_76>=1+free_1 && 2<=free_103 && T>=0 && free_43>=2 && 1+free_42<=-1+free_1 ], cost: 1+T+free_73



Computing asymptotic complexity for rule 42

   Solved the limit problem by the following transformations:

      Created initial limit problem:

      -2+free_73 (+/+!), -1+free_103 (+/+!), -1+free_30-free_1 (+/+!), -free_1+free_76 (+/+!), 1+T (+/+!), -1+free_31 (+/+!), 1+T+free_73 (+) [not solved]



      removing all constraints (solved by SMT)

      resulting limit problem: [solved]



      applying transformation rule (C) using substitution {free_30==2,T==0,free_1==0,free_76==1,free_73==n,free_31==n,free_103==n}

      resulting limit problem:

      [solved]



   Solution:

      free_30 / 2

      T / 0

      free_1 / 0

      free_76 / 1

      free_73 / n

      free_31 / n

      free_103 / n

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

   Rule cost:   1+T+free_73

   Rule guard:  [ free_73>=3 && free_76>=1+free_1 && 2<=free_103 && T>=0 && free_31>=2 && 1+free_1<=-1+free_30 ]



WORST_CASE(INF,?)


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

(2)
BOUNDS(INF, INF)