/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, 1996 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) -> Com_1(f1(A, 1 + B, D, Z, D, A1, B, H, I, J, K, L, M, N, O, P, Q, R, S, T, U, V, W, X, Y)) :|: A >= B + 1 && 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) -> Com_1(f8(A, B, C, D, E, F, G, H, I, 0, Z, A1, A1, 0, A1, H, Q, R, S, T, U, V, W, X, Y)) :|: B1 >= H + 1 && I >= 0 && A1 >= B1 + 1 && Z >= 2 && J >= 0 && J <= 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) -> Com_1(f8(A, B, C, D, E, F, G, H, I, 0, Z, A1, A1, 0, A1, H, Q, R, S, T, U, V, W, X, Y)) :|: B1 >= H + 1 && I >= 0 && B1 >= A1 + 1 && Z >= 2 && J >= 0 && J <= 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) -> Com_1(f8(A, B, C, D, E, F, G, H, I, 0, Z, A1, A1, 0, A1, H, Q, R, S, T, U, V, W, X, Y)) :|: H >= B1 + 1 && I >= 0 && A1 >= B1 + 1 && Z >= 2 && J >= 0 && J <= 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) -> Com_1(f8(A, B, C, D, E, F, G, H, I, 0, Z, A1, A1, 0, A1, H, Q, R, S, T, U, V, W, X, Y)) :|: H >= B1 + 1 && I >= 0 && B1 >= A1 + 1 && Z >= 2 && J >= 0 && J <= 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) -> Com_1(f10(A, B, C, D, E, F, G, G1, I, F1, Z, B1, C1, D1, E1, H1, A1, R, S, T, U, V, W, X, Y)) :|: I >= 0 && 0 >= B1 + 1 && Z >= 2 && J >= H && J <= H
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) -> Com_1(f10(A, B, C, D, E, F, G, G1, I, F1, Z, B1, C1, D1, E1, H1, A1, R, S, T, U, V, W, X, Y)) :|: I >= 0 && B1 >= 1 && Z >= 2 && J >= H && J <= H
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) -> Com_1(f8(A, B, C, D, E, F, G, H, I, 0, Z, A1, A1, 0, A1, H, Q, -(1) + R, B1, -(1) + R, U, V, W, X, Y)) :|: C1 >= H + 1 && R >= 0 && A1 >= C1 + 1 && Z >= 2 && J >= 0 && 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) -> Com_1(f8(A, B, C, D, E, F, G, H, I, 0, Z, A1, A1, 0, A1, H, Q, -(1) + R, B1, -(1) + R, U, V, W, X, Y)) :|: C1 >= H + 1 && R >= 0 && C1 >= A1 + 1 && Z >= 2 && J >= 0 && 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) -> Com_1(f8(A, B, C, D, E, F, G, H, I, 0, Z, A1, A1, 0, A1, H, Q, -(1) + R, B1, -(1) + R, U, V, W, X, Y)) :|: H >= C1 + 1 && R >= 0 && A1 >= C1 + 1 && Z >= 2 && J >= 0 && 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) -> Com_1(f8(A, B, C, D, E, F, G, H, I, 0, Z, A1, A1, 0, A1, H, Q, -(1) + R, B1, -(1) + R, U, V, W, X, Y)) :|: H >= C1 + 1 && R >= 0 && C1 >= A1 + 1 && Z >= 2 && J >= 0 && 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) -> Com_1(f10(A, B, C, D, E, F, G, F1, I, E1, Z, L, B1, C1, D1, G1, A1, R, S, T, U, V, W, X, Y)) :|: Z >= 2 && R >= 0 && J >= H && J <= H
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) -> Com_1(f10(B1, D1, C1, K1, H1, F, G, P1, I, O1, A1, 0, L1, M1, N1, Q1, F1, R, S, T, Z, E1, G1, X, Y)) :|: 0 >= I1 && 0 >= A1 && 0 >= J1
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) -> Com_1(f1(A1, 2, B1, C1, B1, F, G, H, I, J, A1, L, M, N, O, P, Q, R, S, T, Z, V, B1, D1, Y)) :|: A1 >= 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) -> Com_1(f8(A1, C1, B1, H1, G1, F, G, C, R, 0, Z, C, C, 0, C, C, E1, R, S, T, U, D1, F1, X, R + 1)) :|: K1 >= Z && L1 >= 2 && C1 >= L1 && B >= A && B >= 0 && C >= 1 && C1 >= 0 && Z >= 2 && 0 >= 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) -> Com_1(f8(A1, C1, B1, H1, G1, F, G, C, R, 0, Z, C, C, 0, C, C, E1, R, S, T, U, D1, F1, X, R + 1)) :|: K1 >= Z && L1 >= 2 && C1 >= L1 && B >= A && B >= 0 && C >= 1 && C1 >= 0 && Z >= 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) -> Com_1(f8(A1, C1, B1, H1, G1, F, G, C, R, 0, Z, C, C, 0, C, C, E1, R, S, T, U, D1, F1, X, R + 1)) :|: K1 >= Z && L1 >= 2 && C1 >= L1 && B >= A && B >= 0 && 0 >= C + 1 && C1 >= 0 && Z >= 2

The start-symbols are:[f9_25]


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

(1) Loat Proof (FINISHED)


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



Initial linear ITS problem

   Start location: f9

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

     14: f1 -> f8 : A'=free_83, B'=free_87, C'=free_82, D'=free_79, E'=free_86, H'=C, Q'=R, J'=0, K'=free_81, L'=C, M'=C, N'=0, O'=C, P'=C, Q_1'=free_88, V'=free_84, W'=free_80, Y'=1+R, [ free_89>=free_81 && free_85>=2 && free_87>=free_85 && B>=A && B>=0 && C>=1 && free_87>=0 && free_81>=2 && 0>=1+C ], cost: 1

     15: f1 -> f8 : A'=free_94, B'=free_98, C'=free_93, D'=free_90, E'=free_97, H'=C, Q'=R, J'=0, K'=free_92, L'=C, M'=C, N'=0, O'=C, P'=C, Q_1'=free_99, V'=free_95, W'=free_91, Y'=1+R, [ free_100>=free_92 && free_96>=2 && free_98>=free_96 && B>=A && B>=0 && C>=1 && free_98>=0 && free_92>=2 ], cost: 1

     16: f1 -> f8 : A'=free_105, B'=free_109, C'=free_104, D'=free_101, E'=free_108, H'=C, Q'=R, J'=0, K'=free_103, L'=C, M'=C, N'=0, O'=C, P'=C, Q_1'=free_110, V'=free_106, W'=free_102, Y'=1+R, [ free_111>=free_103 && free_107>=2 && free_109>=free_107 && B>=A && B>=0 && 0>=1+C && free_109>=0 && free_103>=2 ], cost: 1

      1: f7 -> f8 : J'=0, K'=free_3, L'=free_4, M'=free_4, N'=0, O'=free_4, P'=H, [ free_2>=1+H && Q>=0 && free_4>=1+free_2 && free_3>=2 && J==0 ], cost: 1

      2: f7 -> f8 : J'=0, K'=free_6, L'=free_7, M'=free_7, N'=0, O'=free_7, P'=H, [ free_5>=1+H && Q>=0 && free_5>=1+free_7 && free_6>=2 && J==0 ], cost: 1

      3: f7 -> f8 : J'=0, K'=free_9, L'=free_10, M'=free_10, N'=0, O'=free_10, P'=H, [ H>=1+free_8 && Q>=0 && free_10>=1+free_8 && free_9>=2 && J==0 ], cost: 1

      4: f7 -> f8 : J'=0, K'=free_12, L'=free_13, M'=free_13, N'=0, O'=free_13, P'=H, [ H>=1+free_11 && Q>=0 && free_11>=1+free_13 && free_12>=2 && J==0 ], cost: 1

      5: f7 -> f10 : A1'=B, B'=C, B1'=D, C'=E, C1'=F, D'=G, D1'=free_18, E'=Q, E1'=free_21, F'=free_17, F1'=free_14, G'=free_20, G1'=free_16, H'=free_22, H1'=free_19, Q'=free_15, Q1'=R, J'=S, J1'=T, K'=U, K1'=V, L'=W, L1'=X, M'=Y, [ Q>=0 && 0>=1+free_14 && free_17>=2 && J==H ], cost: 1

      6: f7 -> f10 : A1'=B, B'=C, B1'=D, C'=E, C1'=F, D'=G, D1'=free_27, E'=Q, E1'=free_30, F'=free_26, F1'=free_23, G'=free_29, G1'=free_25, H'=free_31, H1'=free_28, Q'=free_24, Q1'=R, J'=S, J1'=T, K'=U, K1'=V, L'=W, L1'=X, M'=Y, [ Q>=0 && free_23>=1 && free_26>=2 && J==H ], cost: 1

      7: f8 -> f8 : J'=0, K'=free_34, L'=free_35, M'=free_35, N'=0, O'=free_35, P'=H, R'=-1+R, S'=free_33, T'=-1+R, [ free_32>=1+H && R>=0 && free_35>=1+free_32 && free_34>=2 && J==0 ], cost: 1

      8: f8 -> f8 : J'=0, K'=free_38, L'=free_39, M'=free_39, N'=0, O'=free_39, P'=H, R'=-1+R, S'=free_37, T'=-1+R, [ free_36>=1+H && R>=0 && free_36>=1+free_39 && free_38>=2 && J==0 ], cost: 1

      9: f8 -> f8 : J'=0, K'=free_42, L'=free_43, M'=free_43, N'=0, O'=free_43, P'=H, R'=-1+R, S'=free_41, T'=-1+R, [ H>=1+free_40 && R>=0 && free_43>=1+free_40 && free_42>=2 && J==0 ], cost: 1

     10: f8 -> f8 : J'=0, K'=free_46, L'=free_47, M'=free_47, N'=0, O'=free_47, P'=H, R'=-1+R, S'=free_45, T'=-1+R, [ H>=1+free_44 && R>=0 && free_44>=1+free_47 && free_46>=2 && J==0 ], cost: 1

     11: f8 -> f10 : A1'=B, B'=C, B1'=D, C'=E, C1'=F, D'=G, D1'=free_51, E'=Q, E1'=free_54, F'=free_50, F1'=L, G'=free_48, G1'=free_53, H'=free_49, H1'=free_55, Q'=free_52, Q1'=R, J'=S, J1'=T, K'=U, K1'=V, L'=W, L1'=X, M'=Y, [ free_50>=2 && R>=0 && J==H ], cost: 1

     12: f9 -> f10 : A'=free_64, A1'=free_70, B'=free_62, B1'=free_56, C'=free_67, C1'=F, D'=G, D1'=free_60, E'=Q, E1'=free_72, F'=free_65, F1'=0, G'=free_58, G1'=free_73, H'=free_66, H1'=free_59, Q'=free_71, Q1'=R, J'=S, J1'=T, K'=free_63, K1'=free_57, L'=free_68, L1'=X, M'=Y, [ 0>=free_69 && 0>=free_65 && 0>=free_61 ], cost: 1

     13: f9 -> f1 : A'=free_76, B'=2, C'=free_78, D'=free_75, E'=free_78, K'=free_76, U'=free_74, W'=free_78, X'=free_77, [ free_76>=2 ], cost: 1



Checking for constant complexity:

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

     12: f9 -> f10 : A'=free_64, A1'=free_70, B'=free_62, B1'=free_56, C'=free_67, C1'=F, D'=G, D1'=free_60, E'=Q, E1'=free_72, F'=free_65, F1'=0, G'=free_58, G1'=free_73, H'=free_66, H1'=free_59, Q'=free_71, Q1'=R, J'=S, J1'=T, K'=free_63, K1'=free_57, L'=free_68, L1'=X, M'=Y, [ 0>=free_69 && 0>=free_65 && 0>=free_61 ], cost: 1



Removed unreachable and leaf rules:

   Start location: f9

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

     14: f1 -> f8 : A'=free_83, B'=free_87, C'=free_82, D'=free_79, E'=free_86, H'=C, Q'=R, J'=0, K'=free_81, L'=C, M'=C, N'=0, O'=C, P'=C, Q_1'=free_88, V'=free_84, W'=free_80, Y'=1+R, [ free_89>=free_81 && free_85>=2 && free_87>=free_85 && B>=A && B>=0 && C>=1 && free_87>=0 && free_81>=2 && 0>=1+C ], cost: 1

     15: f1 -> f8 : A'=free_94, B'=free_98, C'=free_93, D'=free_90, E'=free_97, H'=C, Q'=R, J'=0, K'=free_92, L'=C, M'=C, N'=0, O'=C, P'=C, Q_1'=free_99, V'=free_95, W'=free_91, Y'=1+R, [ free_100>=free_92 && free_96>=2 && free_98>=free_96 && B>=A && B>=0 && C>=1 && free_98>=0 && free_92>=2 ], cost: 1

     16: f1 -> f8 : A'=free_105, B'=free_109, C'=free_104, D'=free_101, E'=free_108, H'=C, Q'=R, J'=0, K'=free_103, L'=C, M'=C, N'=0, O'=C, P'=C, Q_1'=free_110, V'=free_106, W'=free_102, Y'=1+R, [ free_111>=free_103 && free_107>=2 && free_109>=free_107 && B>=A && B>=0 && 0>=1+C && free_109>=0 && free_103>=2 ], cost: 1

      7: f8 -> f8 : J'=0, K'=free_34, L'=free_35, M'=free_35, N'=0, O'=free_35, P'=H, R'=-1+R, S'=free_33, T'=-1+R, [ free_32>=1+H && R>=0 && free_35>=1+free_32 && free_34>=2 && J==0 ], cost: 1

      8: f8 -> f8 : J'=0, K'=free_38, L'=free_39, M'=free_39, N'=0, O'=free_39, P'=H, R'=-1+R, S'=free_37, T'=-1+R, [ free_36>=1+H && R>=0 && free_36>=1+free_39 && free_38>=2 && J==0 ], cost: 1

      9: f8 -> f8 : J'=0, K'=free_42, L'=free_43, M'=free_43, N'=0, O'=free_43, P'=H, R'=-1+R, S'=free_41, T'=-1+R, [ H>=1+free_40 && R>=0 && free_43>=1+free_40 && free_42>=2 && J==0 ], cost: 1

     10: f8 -> f8 : J'=0, K'=free_46, L'=free_47, M'=free_47, N'=0, O'=free_47, P'=H, R'=-1+R, S'=free_45, T'=-1+R, [ H>=1+free_44 && R>=0 && free_44>=1+free_47 && free_46>=2 && J==0 ], cost: 1

     13: f9 -> f1 : A'=free_76, B'=2, C'=free_78, D'=free_75, E'=free_78, K'=free_76, U'=free_74, W'=free_78, X'=free_77, [ free_76>=2 ], cost: 1



Removed rules with unsatisfiable guard:

   Start location: f9

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

     15: f1 -> f8 : A'=free_94, B'=free_98, C'=free_93, D'=free_90, E'=free_97, H'=C, Q'=R, J'=0, K'=free_92, L'=C, M'=C, N'=0, O'=C, P'=C, Q_1'=free_99, V'=free_95, W'=free_91, Y'=1+R, [ free_100>=free_92 && free_96>=2 && free_98>=free_96 && B>=A && B>=0 && C>=1 && free_98>=0 && free_92>=2 ], cost: 1

     16: f1 -> f8 : A'=free_105, B'=free_109, C'=free_104, D'=free_101, E'=free_108, H'=C, Q'=R, J'=0, K'=free_103, L'=C, M'=C, N'=0, O'=C, P'=C, Q_1'=free_110, V'=free_106, W'=free_102, Y'=1+R, [ free_111>=free_103 && free_107>=2 && free_109>=free_107 && B>=A && B>=0 && 0>=1+C && free_109>=0 && free_103>=2 ], cost: 1

      7: f8 -> f8 : J'=0, K'=free_34, L'=free_35, M'=free_35, N'=0, O'=free_35, P'=H, R'=-1+R, S'=free_33, T'=-1+R, [ free_32>=1+H && R>=0 && free_35>=1+free_32 && free_34>=2 && J==0 ], cost: 1

      8: f8 -> f8 : J'=0, K'=free_38, L'=free_39, M'=free_39, N'=0, O'=free_39, P'=H, R'=-1+R, S'=free_37, T'=-1+R, [ free_36>=1+H && R>=0 && free_36>=1+free_39 && free_38>=2 && J==0 ], cost: 1

      9: f8 -> f8 : J'=0, K'=free_42, L'=free_43, M'=free_43, N'=0, O'=free_43, P'=H, R'=-1+R, S'=free_41, T'=-1+R, [ H>=1+free_40 && R>=0 && free_43>=1+free_40 && free_42>=2 && J==0 ], cost: 1

     10: f8 -> f8 : J'=0, K'=free_46, L'=free_47, M'=free_47, N'=0, O'=free_47, P'=H, R'=-1+R, S'=free_45, T'=-1+R, [ H>=1+free_44 && R>=0 && free_44>=1+free_47 && free_46>=2 && J==0 ], cost: 1

     13: f9 -> f1 : A'=free_76, B'=2, C'=free_78, D'=free_75, E'=free_78, K'=free_76, U'=free_74, W'=free_78, X'=free_77, [ free_76>=2 ], cost: 1



Removed unreachable and leaf rules:

   Start location: f9

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

     15: f1 -> f8 : A'=free_94, B'=free_98, C'=free_93, D'=free_90, E'=free_97, H'=C, Q'=R, J'=0, K'=free_92, L'=C, M'=C, N'=0, O'=C, P'=C, Q_1'=free_99, V'=free_95, W'=free_91, Y'=1+R, [ free_100>=free_92 && free_96>=2 && free_98>=free_96 && B>=A && B>=0 && C>=1 && free_98>=0 && free_92>=2 ], cost: 1

     16: f1 -> f8 : A'=free_105, B'=free_109, C'=free_104, D'=free_101, E'=free_108, H'=C, Q'=R, J'=0, K'=free_103, L'=C, M'=C, N'=0, O'=C, P'=C, Q_1'=free_110, V'=free_106, W'=free_102, Y'=1+R, [ free_111>=free_103 && free_107>=2 && free_109>=free_107 && B>=A && B>=0 && 0>=1+C && free_109>=0 && free_103>=2 ], cost: 1

      7: f8 -> f8 : J'=0, K'=free_34, L'=free_35, M'=free_35, N'=0, O'=free_35, P'=H, R'=-1+R, S'=free_33, T'=-1+R, [ free_32>=1+H && R>=0 && free_35>=1+free_32 && free_34>=2 && J==0 ], cost: 1

      8: f8 -> f8 : J'=0, K'=free_38, L'=free_39, M'=free_39, N'=0, O'=free_39, P'=H, R'=-1+R, S'=free_37, T'=-1+R, [ free_36>=1+H && R>=0 && free_36>=1+free_39 && free_38>=2 && J==0 ], cost: 1

      9: f8 -> f8 : J'=0, K'=free_42, L'=free_43, M'=free_43, N'=0, O'=free_43, P'=H, R'=-1+R, S'=free_41, T'=-1+R, [ H>=1+free_40 && R>=0 && free_43>=1+free_40 && free_42>=2 && J==0 ], cost: 1

     10: f8 -> f8 : J'=0, K'=free_46, L'=free_47, M'=free_47, N'=0, O'=free_47, P'=H, R'=-1+R, S'=free_45, T'=-1+R, [ H>=1+free_44 && R>=0 && free_44>=1+free_47 && free_46>=2 && J==0 ], cost: 1

     13: f9 -> f1 : A'=free_76, B'=2, C'=free_78, D'=free_75, E'=free_78, K'=free_76, U'=free_74, W'=free_78, X'=free_77, [ free_76>=2 ], cost: 1



Simplified all rules, resulting in:

   Start location: f9

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

     15: f1 -> f8 : A'=free_94, B'=free_98, C'=free_93, D'=free_90, E'=free_97, H'=C, Q'=R, J'=0, K'=free_92, L'=C, M'=C, N'=0, O'=C, P'=C, Q_1'=free_99, V'=free_95, W'=free_91, Y'=1+R, [ B>=A && B>=0 && C>=1 && free_92>=2 && 2<=free_98 ], cost: 1

     16: f1 -> f8 : A'=free_105, B'=free_109, C'=free_104, D'=free_101, E'=free_108, H'=C, Q'=R, J'=0, K'=free_103, L'=C, M'=C, N'=0, O'=C, P'=C, Q_1'=free_110, V'=free_106, W'=free_102, Y'=1+R, [ B>=A && B>=0 && 0>=1+C && free_103>=2 && 2<=free_109 ], cost: 1

      7: f8 -> f8 : J'=0, K'=free_34, L'=free_35, M'=free_35, N'=0, O'=free_35, P'=H, R'=-1+R, S'=free_33, T'=-1+R, [ R>=0 && free_34>=2 && J==0 && 1+H<=-1+free_35 ], cost: 1

      8: f8 -> f8 : J'=0, K'=free_38, L'=free_39, M'=free_39, N'=0, O'=free_39, P'=H, R'=-1+R, S'=free_37, T'=-1+R, [ R>=0 && free_38>=2 && J==0 ], cost: 1

      9: f8 -> f8 : J'=0, K'=free_42, L'=free_43, M'=free_43, N'=0, O'=free_43, P'=H, R'=-1+R, S'=free_41, T'=-1+R, [ R>=0 && free_42>=2 && J==0 ], cost: 1

     10: f8 -> f8 : J'=0, K'=free_46, L'=free_47, M'=free_47, N'=0, O'=free_47, P'=H, R'=-1+R, S'=free_45, T'=-1+R, [ R>=0 && free_46>=2 && J==0 && 1+free_47<=-1+H ], cost: 1

     13: f9 -> f1 : A'=free_76, B'=2, C'=free_78, D'=free_75, E'=free_78, K'=free_76, U'=free_74, W'=free_78, X'=free_77, [ free_76>=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, E'=D, F'=free_1, G'=B, [ A>=1+B && B>=0 ], cost: 1



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

   Removing the simple loops: 0.



Accelerating simple loops of location 2.

   Accelerating the following rules:

      7: f8 -> f8 : J'=0, K'=free_34, L'=free_35, M'=free_35, N'=0, O'=free_35, P'=H, R'=-1+R, S'=free_33, T'=-1+R, [ R>=0 && free_34>=2 && J==0 && 1+H<=-1+free_35 ], cost: 1

      8: f8 -> f8 : J'=0, K'=free_38, L'=free_39, M'=free_39, N'=0, O'=free_39, P'=H, R'=-1+R, S'=free_37, T'=-1+R, [ R>=0 && free_38>=2 && J==0 ], cost: 1

      9: f8 -> f8 : J'=0, K'=free_42, L'=free_43, M'=free_43, N'=0, O'=free_43, P'=H, R'=-1+R, S'=free_41, T'=-1+R, [ R>=0 && free_42>=2 && J==0 ], cost: 1

     10: f8 -> f8 : J'=0, K'=free_46, L'=free_47, M'=free_47, N'=0, O'=free_47, P'=H, R'=-1+R, S'=free_45, T'=-1+R, [ R>=0 && free_46>=2 && J==0 && 1+free_47<=-1+H ], cost: 1



   Accelerated rule 7 with metering function 1+R, yielding the new rule 18.

   Accelerated rule 8 with metering function 1+R, yielding the new rule 19.

   Accelerated rule 9 with metering function 1+R, yielding the new rule 20.

   Accelerated rule 10 with metering function 1+R, yielding the new rule 21.

   Removing the simple loops: 7 8 9 10.



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

   Start location: f9

     15: f1 -> f8 : A'=free_94, B'=free_98, C'=free_93, D'=free_90, E'=free_97, H'=C, Q'=R, J'=0, K'=free_92, L'=C, M'=C, N'=0, O'=C, P'=C, Q_1'=free_99, V'=free_95, W'=free_91, Y'=1+R, [ B>=A && B>=0 && C>=1 && free_92>=2 && 2<=free_98 ], cost: 1

     16: f1 -> f8 : A'=free_105, B'=free_109, C'=free_104, D'=free_101, E'=free_108, H'=C, Q'=R, J'=0, K'=free_103, L'=C, M'=C, N'=0, O'=C, P'=C, Q_1'=free_110, V'=free_106, W'=free_102, Y'=1+R, [ B>=A && B>=0 && 0>=1+C && free_103>=2 && 2<=free_109 ], cost: 1

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

     18: f8 -> f8 : J'=0, K'=free_34, L'=free_35, M'=free_35, N'=0, O'=free_35, P'=H, R'=-1, S'=free_33, T'=-1, [ R>=0 && free_34>=2 && J==0 && 1+H<=-1+free_35 ], cost: 1+R

     19: f8 -> f8 : J'=0, K'=free_38, L'=free_39, M'=free_39, N'=0, O'=free_39, P'=H, R'=-1, S'=free_37, T'=-1, [ R>=0 && free_38>=2 && J==0 ], cost: 1+R

     20: f8 -> f8 : J'=0, K'=free_42, L'=free_43, M'=free_43, N'=0, O'=free_43, P'=H, R'=-1, S'=free_41, T'=-1, [ R>=0 && free_42>=2 && J==0 ], cost: 1+R

     21: f8 -> f8 : J'=0, K'=free_46, L'=free_47, M'=free_47, N'=0, O'=free_47, P'=H, R'=-1, S'=free_45, T'=-1, [ R>=0 && free_46>=2 && J==0 && 1+free_47<=-1+H ], cost: 1+R

     13: f9 -> f1 : A'=free_76, B'=2, C'=free_78, D'=free_75, E'=free_78, K'=free_76, U'=free_74, W'=free_78, X'=free_77, [ free_76>=2 ], cost: 1



Chained accelerated rules (with incoming rules):

   Start location: f9

     15: f1 -> f8 : A'=free_94, B'=free_98, C'=free_93, D'=free_90, E'=free_97, H'=C, Q'=R, J'=0, K'=free_92, L'=C, M'=C, N'=0, O'=C, P'=C, Q_1'=free_99, V'=free_95, W'=free_91, Y'=1+R, [ B>=A && B>=0 && C>=1 && free_92>=2 && 2<=free_98 ], cost: 1

     16: f1 -> f8 : A'=free_105, B'=free_109, C'=free_104, D'=free_101, E'=free_108, H'=C, Q'=R, J'=0, K'=free_103, L'=C, M'=C, N'=0, O'=C, P'=C, Q_1'=free_110, V'=free_106, W'=free_102, Y'=1+R, [ B>=A && B>=0 && 0>=1+C && free_103>=2 && 2<=free_109 ], cost: 1

     23: f1 -> f8 : A'=free_94, B'=free_98, C'=free_93, D'=free_90, E'=free_97, H'=C, Q'=R, J'=0, K'=free_34, L'=free_35, M'=free_35, N'=0, O'=free_35, P'=C, Q_1'=free_99, R'=-1, S'=free_33, T'=-1, V'=free_95, W'=free_91, Y'=1+R, [ B>=A && B>=0 && C>=1 && 2<=free_98 && R>=0 && free_34>=2 && 1+C<=-1+free_35 ], cost: 2+R

     24: f1 -> f8 : A'=free_105, B'=free_109, C'=free_104, D'=free_101, E'=free_108, H'=C, Q'=R, J'=0, K'=free_34, L'=free_35, M'=free_35, N'=0, O'=free_35, P'=C, Q_1'=free_110, R'=-1, S'=free_33, T'=-1, V'=free_106, W'=free_102, Y'=1+R, [ B>=A && B>=0 && 0>=1+C && 2<=free_109 && R>=0 && free_34>=2 && 1+C<=-1+free_35 ], cost: 2+R

     25: f1 -> f8 : A'=free_94, B'=free_98, C'=free_93, D'=free_90, E'=free_97, H'=C, Q'=R, J'=0, K'=free_38, L'=free_39, M'=free_39, N'=0, O'=free_39, P'=C, Q_1'=free_99, R'=-1, S'=free_37, T'=-1, V'=free_95, W'=free_91, Y'=1+R, [ B>=A && B>=0 && C>=1 && 2<=free_98 && R>=0 && free_38>=2 ], cost: 2+R

     26: f1 -> f8 : A'=free_105, B'=free_109, C'=free_104, D'=free_101, E'=free_108, H'=C, Q'=R, J'=0, K'=free_38, L'=free_39, M'=free_39, N'=0, O'=free_39, P'=C, Q_1'=free_110, R'=-1, S'=free_37, T'=-1, V'=free_106, W'=free_102, Y'=1+R, [ B>=A && B>=0 && 0>=1+C && 2<=free_109 && R>=0 && free_38>=2 ], cost: 2+R

     27: f1 -> f8 : A'=free_94, B'=free_98, C'=free_93, D'=free_90, E'=free_97, H'=C, Q'=R, J'=0, K'=free_42, L'=free_43, M'=free_43, N'=0, O'=free_43, P'=C, Q_1'=free_99, R'=-1, S'=free_41, T'=-1, V'=free_95, W'=free_91, Y'=1+R, [ B>=A && B>=0 && C>=1 && 2<=free_98 && R>=0 && free_42>=2 ], cost: 2+R

     28: f1 -> f8 : A'=free_105, B'=free_109, C'=free_104, D'=free_101, E'=free_108, H'=C, Q'=R, J'=0, K'=free_42, L'=free_43, M'=free_43, N'=0, O'=free_43, P'=C, Q_1'=free_110, R'=-1, S'=free_41, T'=-1, V'=free_106, W'=free_102, Y'=1+R, [ B>=A && B>=0 && 0>=1+C && 2<=free_109 && R>=0 && free_42>=2 ], cost: 2+R

     29: f1 -> f8 : A'=free_94, B'=free_98, C'=free_93, D'=free_90, E'=free_97, H'=C, Q'=R, J'=0, K'=free_46, L'=free_47, M'=free_47, N'=0, O'=free_47, P'=C, Q_1'=free_99, R'=-1, S'=free_45, T'=-1, V'=free_95, W'=free_91, Y'=1+R, [ B>=A && B>=0 && C>=1 && 2<=free_98 && R>=0 && free_46>=2 && 1+free_47<=-1+C ], cost: 2+R

     30: f1 -> f8 : A'=free_105, B'=free_109, C'=free_104, D'=free_101, E'=free_108, H'=C, Q'=R, J'=0, K'=free_46, L'=free_47, M'=free_47, N'=0, O'=free_47, P'=C, Q_1'=free_110, R'=-1, S'=free_45, T'=-1, V'=free_106, W'=free_102, Y'=1+R, [ B>=A && B>=0 && 0>=1+C && 2<=free_109 && R>=0 && free_46>=2 && 1+free_47<=-1+C ], cost: 2+R

     13: f9 -> f1 : A'=free_76, B'=2, C'=free_78, D'=free_75, E'=free_78, K'=free_76, U'=free_74, W'=free_78, X'=free_77, [ free_76>=2 ], cost: 1

     22: f9 -> f1 : A'=free_76, B'=free_76, C'=free, D'=free, E'=free, F'=free_1, G'=-1+free_76, K'=free_76, U'=free_74, W'=free_78, X'=free_77, [ free_76>=3 ], cost: -1+free_76



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

   Start location: f9

     23: f1 -> f8 : A'=free_94, B'=free_98, C'=free_93, D'=free_90, E'=free_97, H'=C, Q'=R, J'=0, K'=free_34, L'=free_35, M'=free_35, N'=0, O'=free_35, P'=C, Q_1'=free_99, R'=-1, S'=free_33, T'=-1, V'=free_95, W'=free_91, Y'=1+R, [ B>=A && B>=0 && C>=1 && 2<=free_98 && R>=0 && free_34>=2 && 1+C<=-1+free_35 ], cost: 2+R

     24: f1 -> f8 : A'=free_105, B'=free_109, C'=free_104, D'=free_101, E'=free_108, H'=C, Q'=R, J'=0, K'=free_34, L'=free_35, M'=free_35, N'=0, O'=free_35, P'=C, Q_1'=free_110, R'=-1, S'=free_33, T'=-1, V'=free_106, W'=free_102, Y'=1+R, [ B>=A && B>=0 && 0>=1+C && 2<=free_109 && R>=0 && free_34>=2 && 1+C<=-1+free_35 ], cost: 2+R

     25: f1 -> f8 : A'=free_94, B'=free_98, C'=free_93, D'=free_90, E'=free_97, H'=C, Q'=R, J'=0, K'=free_38, L'=free_39, M'=free_39, N'=0, O'=free_39, P'=C, Q_1'=free_99, R'=-1, S'=free_37, T'=-1, V'=free_95, W'=free_91, Y'=1+R, [ B>=A && B>=0 && C>=1 && 2<=free_98 && R>=0 && free_38>=2 ], cost: 2+R

     26: f1 -> f8 : A'=free_105, B'=free_109, C'=free_104, D'=free_101, E'=free_108, H'=C, Q'=R, J'=0, K'=free_38, L'=free_39, M'=free_39, N'=0, O'=free_39, P'=C, Q_1'=free_110, R'=-1, S'=free_37, T'=-1, V'=free_106, W'=free_102, Y'=1+R, [ B>=A && B>=0 && 0>=1+C && 2<=free_109 && R>=0 && free_38>=2 ], cost: 2+R

     27: f1 -> f8 : A'=free_94, B'=free_98, C'=free_93, D'=free_90, E'=free_97, H'=C, Q'=R, J'=0, K'=free_42, L'=free_43, M'=free_43, N'=0, O'=free_43, P'=C, Q_1'=free_99, R'=-1, S'=free_41, T'=-1, V'=free_95, W'=free_91, Y'=1+R, [ B>=A && B>=0 && C>=1 && 2<=free_98 && R>=0 && free_42>=2 ], cost: 2+R

     28: f1 -> f8 : A'=free_105, B'=free_109, C'=free_104, D'=free_101, E'=free_108, H'=C, Q'=R, J'=0, K'=free_42, L'=free_43, M'=free_43, N'=0, O'=free_43, P'=C, Q_1'=free_110, R'=-1, S'=free_41, T'=-1, V'=free_106, W'=free_102, Y'=1+R, [ B>=A && B>=0 && 0>=1+C && 2<=free_109 && R>=0 && free_42>=2 ], cost: 2+R

     29: f1 -> f8 : A'=free_94, B'=free_98, C'=free_93, D'=free_90, E'=free_97, H'=C, Q'=R, J'=0, K'=free_46, L'=free_47, M'=free_47, N'=0, O'=free_47, P'=C, Q_1'=free_99, R'=-1, S'=free_45, T'=-1, V'=free_95, W'=free_91, Y'=1+R, [ B>=A && B>=0 && C>=1 && 2<=free_98 && R>=0 && free_46>=2 && 1+free_47<=-1+C ], cost: 2+R

     30: f1 -> f8 : A'=free_105, B'=free_109, C'=free_104, D'=free_101, E'=free_108, H'=C, Q'=R, J'=0, K'=free_46, L'=free_47, M'=free_47, N'=0, O'=free_47, P'=C, Q_1'=free_110, R'=-1, S'=free_45, T'=-1, V'=free_106, W'=free_102, Y'=1+R, [ B>=A && B>=0 && 0>=1+C && 2<=free_109 && R>=0 && free_46>=2 && 1+free_47<=-1+C ], cost: 2+R

     13: f9 -> f1 : A'=free_76, B'=2, C'=free_78, D'=free_75, E'=free_78, K'=free_76, U'=free_74, W'=free_78, X'=free_77, [ free_76>=2 ], cost: 1

     22: f9 -> f1 : A'=free_76, B'=free_76, C'=free, D'=free, E'=free, F'=free_1, G'=-1+free_76, K'=free_76, U'=free_74, W'=free_78, X'=free_77, [ free_76>=3 ], cost: -1+free_76



Eliminated locations (on tree-shaped paths):

   Start location: f9

     31: f9 -> f8 : A'=free_94, B'=free_98, C'=free_93, D'=free_90, E'=free_97, H'=free_78, Q'=R, J'=0, K'=free_34, L'=free_35, M'=free_35, N'=0, O'=free_35, P'=free_78, Q_1'=free_99, R'=-1, S'=free_33, T'=-1, U'=free_74, V'=free_95, W'=free_91, X'=free_77, Y'=1+R, [ free_76>=2 && 2>=free_76 && free_78>=1 && 2<=free_98 && R>=0 && free_34>=2 && 1+free_78<=-1+free_35 ], cost: 3+R

     32: f9 -> f8 : A'=free_105, B'=free_109, C'=free_104, D'=free_101, E'=free_108, H'=free_78, Q'=R, J'=0, K'=free_34, L'=free_35, M'=free_35, N'=0, O'=free_35, P'=free_78, Q_1'=free_110, R'=-1, S'=free_33, T'=-1, U'=free_74, V'=free_106, W'=free_102, X'=free_77, Y'=1+R, [ free_76>=2 && 2>=free_76 && 0>=1+free_78 && 2<=free_109 && R>=0 && free_34>=2 && 1+free_78<=-1+free_35 ], cost: 3+R

     33: f9 -> f8 : A'=free_94, B'=free_98, C'=free_93, D'=free_90, E'=free_97, H'=free_78, Q'=R, J'=0, K'=free_38, L'=free_39, M'=free_39, N'=0, O'=free_39, P'=free_78, Q_1'=free_99, R'=-1, S'=free_37, T'=-1, U'=free_74, V'=free_95, W'=free_91, X'=free_77, Y'=1+R, [ free_76>=2 && 2>=free_76 && free_78>=1 && 2<=free_98 && R>=0 && free_38>=2 ], cost: 3+R

     34: f9 -> f8 : A'=free_105, B'=free_109, C'=free_104, D'=free_101, E'=free_108, H'=free_78, Q'=R, J'=0, K'=free_38, L'=free_39, M'=free_39, N'=0, O'=free_39, P'=free_78, Q_1'=free_110, R'=-1, S'=free_37, T'=-1, U'=free_74, V'=free_106, W'=free_102, X'=free_77, Y'=1+R, [ free_76>=2 && 2>=free_76 && 0>=1+free_78 && 2<=free_109 && R>=0 && free_38>=2 ], cost: 3+R

     35: f9 -> f8 : A'=free_94, B'=free_98, C'=free_93, D'=free_90, E'=free_97, H'=free_78, Q'=R, J'=0, K'=free_42, L'=free_43, M'=free_43, N'=0, O'=free_43, P'=free_78, Q_1'=free_99, R'=-1, S'=free_41, T'=-1, U'=free_74, V'=free_95, W'=free_91, X'=free_77, Y'=1+R, [ free_76>=2 && 2>=free_76 && free_78>=1 && 2<=free_98 && R>=0 && free_42>=2 ], cost: 3+R

     36: f9 -> f8 : A'=free_105, B'=free_109, C'=free_104, D'=free_101, E'=free_108, H'=free_78, Q'=R, J'=0, K'=free_42, L'=free_43, M'=free_43, N'=0, O'=free_43, P'=free_78, Q_1'=free_110, R'=-1, S'=free_41, T'=-1, U'=free_74, V'=free_106, W'=free_102, X'=free_77, Y'=1+R, [ free_76>=2 && 2>=free_76 && 0>=1+free_78 && 2<=free_109 && R>=0 && free_42>=2 ], cost: 3+R

     37: f9 -> f8 : A'=free_94, B'=free_98, C'=free_93, D'=free_90, E'=free_97, H'=free_78, Q'=R, J'=0, K'=free_46, L'=free_47, M'=free_47, N'=0, O'=free_47, P'=free_78, Q_1'=free_99, R'=-1, S'=free_45, T'=-1, U'=free_74, V'=free_95, W'=free_91, X'=free_77, Y'=1+R, [ free_76>=2 && 2>=free_76 && free_78>=1 && 2<=free_98 && R>=0 && free_46>=2 && 1+free_47<=-1+free_78 ], cost: 3+R

     38: f9 -> f8 : A'=free_105, B'=free_109, C'=free_104, D'=free_101, E'=free_108, H'=free_78, Q'=R, J'=0, K'=free_46, L'=free_47, M'=free_47, N'=0, O'=free_47, P'=free_78, Q_1'=free_110, R'=-1, S'=free_45, T'=-1, U'=free_74, V'=free_106, W'=free_102, X'=free_77, Y'=1+R, [ free_76>=2 && 2>=free_76 && 0>=1+free_78 && 2<=free_109 && R>=0 && free_46>=2 && 1+free_47<=-1+free_78 ], cost: 3+R

     39: f9 -> f8 : A'=free_94, B'=free_98, C'=free_93, D'=free_90, E'=free_97, F'=free_1, G'=-1+free_76, H'=free, Q'=R, J'=0, K'=free_34, L'=free_35, M'=free_35, N'=0, O'=free_35, P'=free, Q_1'=free_99, R'=-1, S'=free_33, T'=-1, U'=free_74, V'=free_95, W'=free_91, X'=free_77, Y'=1+R, [ free_76>=3 && free>=1 && 2<=free_98 && R>=0 && free_34>=2 && 1+free<=-1+free_35 ], cost: 1+R+free_76

     40: f9 -> f8 : A'=free_105, B'=free_109, C'=free_104, D'=free_101, E'=free_108, F'=free_1, G'=-1+free_76, H'=free, Q'=R, J'=0, K'=free_34, L'=free_35, M'=free_35, N'=0, O'=free_35, P'=free, Q_1'=free_110, R'=-1, S'=free_33, T'=-1, U'=free_74, V'=free_106, W'=free_102, X'=free_77, Y'=1+R, [ free_76>=3 && 0>=1+free && 2<=free_109 && R>=0 && free_34>=2 && 1+free<=-1+free_35 ], cost: 1+R+free_76

     41: f9 -> f8 : A'=free_94, B'=free_98, C'=free_93, D'=free_90, E'=free_97, F'=free_1, G'=-1+free_76, H'=free, Q'=R, J'=0, K'=free_38, L'=free_39, M'=free_39, N'=0, O'=free_39, P'=free, Q_1'=free_99, R'=-1, S'=free_37, T'=-1, U'=free_74, V'=free_95, W'=free_91, X'=free_77, Y'=1+R, [ free_76>=3 && free>=1 && 2<=free_98 && R>=0 && free_38>=2 ], cost: 1+R+free_76

     42: f9 -> f8 : A'=free_105, B'=free_109, C'=free_104, D'=free_101, E'=free_108, F'=free_1, G'=-1+free_76, H'=free, Q'=R, J'=0, K'=free_38, L'=free_39, M'=free_39, N'=0, O'=free_39, P'=free, Q_1'=free_110, R'=-1, S'=free_37, T'=-1, U'=free_74, V'=free_106, W'=free_102, X'=free_77, Y'=1+R, [ free_76>=3 && 0>=1+free && 2<=free_109 && R>=0 && free_38>=2 ], cost: 1+R+free_76

     43: f9 -> f8 : A'=free_94, B'=free_98, C'=free_93, D'=free_90, E'=free_97, F'=free_1, G'=-1+free_76, H'=free, Q'=R, J'=0, K'=free_42, L'=free_43, M'=free_43, N'=0, O'=free_43, P'=free, Q_1'=free_99, R'=-1, S'=free_41, T'=-1, U'=free_74, V'=free_95, W'=free_91, X'=free_77, Y'=1+R, [ free_76>=3 && free>=1 && 2<=free_98 && R>=0 && free_42>=2 ], cost: 1+R+free_76

     44: f9 -> f8 : A'=free_105, B'=free_109, C'=free_104, D'=free_101, E'=free_108, F'=free_1, G'=-1+free_76, H'=free, Q'=R, J'=0, K'=free_42, L'=free_43, M'=free_43, N'=0, O'=free_43, P'=free, Q_1'=free_110, R'=-1, S'=free_41, T'=-1, U'=free_74, V'=free_106, W'=free_102, X'=free_77, Y'=1+R, [ free_76>=3 && 0>=1+free && 2<=free_109 && R>=0 && free_42>=2 ], cost: 1+R+free_76

     45: f9 -> f8 : A'=free_94, B'=free_98, C'=free_93, D'=free_90, E'=free_97, F'=free_1, G'=-1+free_76, H'=free, Q'=R, J'=0, K'=free_46, L'=free_47, M'=free_47, N'=0, O'=free_47, P'=free, Q_1'=free_99, R'=-1, S'=free_45, T'=-1, U'=free_74, V'=free_95, W'=free_91, X'=free_77, Y'=1+R, [ free_76>=3 && free>=1 && 2<=free_98 && R>=0 && free_46>=2 && 1+free_47<=-1+free ], cost: 1+R+free_76

     46: f9 -> f8 : A'=free_105, B'=free_109, C'=free_104, D'=free_101, E'=free_108, F'=free_1, G'=-1+free_76, H'=free, Q'=R, J'=0, K'=free_46, L'=free_47, M'=free_47, N'=0, O'=free_47, P'=free, Q_1'=free_110, R'=-1, S'=free_45, T'=-1, U'=free_74, V'=free_106, W'=free_102, X'=free_77, Y'=1+R, [ free_76>=3 && 0>=1+free && 2<=free_109 && R>=0 && free_46>=2 && 1+free_47<=-1+free ], cost: 1+R+free_76



Applied pruning (of leafs and parallel rules):

   Start location: f9

     39: f9 -> f8 : A'=free_94, B'=free_98, C'=free_93, D'=free_90, E'=free_97, F'=free_1, G'=-1+free_76, H'=free, Q'=R, J'=0, K'=free_34, L'=free_35, M'=free_35, N'=0, O'=free_35, P'=free, Q_1'=free_99, R'=-1, S'=free_33, T'=-1, U'=free_74, V'=free_95, W'=free_91, X'=free_77, Y'=1+R, [ free_76>=3 && free>=1 && 2<=free_98 && R>=0 && free_34>=2 && 1+free<=-1+free_35 ], cost: 1+R+free_76

     40: f9 -> f8 : A'=free_105, B'=free_109, C'=free_104, D'=free_101, E'=free_108, F'=free_1, G'=-1+free_76, H'=free, Q'=R, J'=0, K'=free_34, L'=free_35, M'=free_35, N'=0, O'=free_35, P'=free, Q_1'=free_110, R'=-1, S'=free_33, T'=-1, U'=free_74, V'=free_106, W'=free_102, X'=free_77, Y'=1+R, [ free_76>=3 && 0>=1+free && 2<=free_109 && R>=0 && free_34>=2 && 1+free<=-1+free_35 ], cost: 1+R+free_76

     44: f9 -> f8 : A'=free_105, B'=free_109, C'=free_104, D'=free_101, E'=free_108, F'=free_1, G'=-1+free_76, H'=free, Q'=R, J'=0, K'=free_42, L'=free_43, M'=free_43, N'=0, O'=free_43, P'=free, Q_1'=free_110, R'=-1, S'=free_41, T'=-1, U'=free_74, V'=free_106, W'=free_102, X'=free_77, Y'=1+R, [ free_76>=3 && 0>=1+free && 2<=free_109 && R>=0 && free_42>=2 ], cost: 1+R+free_76

     45: f9 -> f8 : A'=free_94, B'=free_98, C'=free_93, D'=free_90, E'=free_97, F'=free_1, G'=-1+free_76, H'=free, Q'=R, J'=0, K'=free_46, L'=free_47, M'=free_47, N'=0, O'=free_47, P'=free, Q_1'=free_99, R'=-1, S'=free_45, T'=-1, U'=free_74, V'=free_95, W'=free_91, X'=free_77, Y'=1+R, [ free_76>=3 && free>=1 && 2<=free_98 && R>=0 && free_46>=2 && 1+free_47<=-1+free ], cost: 1+R+free_76

     46: f9 -> f8 : A'=free_105, B'=free_109, C'=free_104, D'=free_101, E'=free_108, F'=free_1, G'=-1+free_76, H'=free, Q'=R, J'=0, K'=free_46, L'=free_47, M'=free_47, N'=0, O'=free_47, P'=free, Q_1'=free_110, R'=-1, S'=free_45, T'=-1, U'=free_74, V'=free_106, W'=free_102, X'=free_77, Y'=1+R, [ free_76>=3 && 0>=1+free && 2<=free_109 && R>=0 && free_46>=2 && 1+free_47<=-1+free ], cost: 1+R+free_76



### Computing asymptotic complexity ###



Fully simplified ITS problem

   Start location: f9

     39: f9 -> f8 : A'=free_94, B'=free_98, C'=free_93, D'=free_90, E'=free_97, F'=free_1, G'=-1+free_76, H'=free, Q'=R, J'=0, K'=free_34, L'=free_35, M'=free_35, N'=0, O'=free_35, P'=free, Q_1'=free_99, R'=-1, S'=free_33, T'=-1, U'=free_74, V'=free_95, W'=free_91, X'=free_77, Y'=1+R, [ free_76>=3 && free>=1 && 2<=free_98 && R>=0 && free_34>=2 && 1+free<=-1+free_35 ], cost: 1+R+free_76

     40: f9 -> f8 : A'=free_105, B'=free_109, C'=free_104, D'=free_101, E'=free_108, F'=free_1, G'=-1+free_76, H'=free, Q'=R, J'=0, K'=free_34, L'=free_35, M'=free_35, N'=0, O'=free_35, P'=free, Q_1'=free_110, R'=-1, S'=free_33, T'=-1, U'=free_74, V'=free_106, W'=free_102, X'=free_77, Y'=1+R, [ free_76>=3 && 0>=1+free && 2<=free_109 && R>=0 && free_34>=2 && 1+free<=-1+free_35 ], cost: 1+R+free_76

     44: f9 -> f8 : A'=free_105, B'=free_109, C'=free_104, D'=free_101, E'=free_108, F'=free_1, G'=-1+free_76, H'=free, Q'=R, J'=0, K'=free_42, L'=free_43, M'=free_43, N'=0, O'=free_43, P'=free, Q_1'=free_110, R'=-1, S'=free_41, T'=-1, U'=free_74, V'=free_106, W'=free_102, X'=free_77, Y'=1+R, [ free_76>=3 && 0>=1+free && 2<=free_109 && R>=0 && free_42>=2 ], cost: 1+R+free_76

     45: f9 -> f8 : A'=free_94, B'=free_98, C'=free_93, D'=free_90, E'=free_97, F'=free_1, G'=-1+free_76, H'=free, Q'=R, J'=0, K'=free_46, L'=free_47, M'=free_47, N'=0, O'=free_47, P'=free, Q_1'=free_99, R'=-1, S'=free_45, T'=-1, U'=free_74, V'=free_95, W'=free_91, X'=free_77, Y'=1+R, [ free_76>=3 && free>=1 && 2<=free_98 && R>=0 && free_46>=2 && 1+free_47<=-1+free ], cost: 1+R+free_76

     46: f9 -> f8 : A'=free_105, B'=free_109, C'=free_104, D'=free_101, E'=free_108, F'=free_1, G'=-1+free_76, H'=free, Q'=R, J'=0, K'=free_46, L'=free_47, M'=free_47, N'=0, O'=free_47, P'=free, Q_1'=free_110, R'=-1, S'=free_45, T'=-1, U'=free_74, V'=free_106, W'=free_102, X'=free_77, Y'=1+R, [ free_76>=3 && 0>=1+free && 2<=free_109 && R>=0 && free_46>=2 && 1+free_47<=-1+free ], cost: 1+R+free_76



Computing asymptotic complexity for rule 39

   Solved the limit problem by the following transformations:

      Created initial limit problem:

      1+R (+/+!), -1+free_34 (+/+!), -2+free_76 (+/+!), 1+R+free_76 (+), free (+/+!), -1+free_35-free (+/+!), -1+free_98 (+/+!) [not solved]



      removing all constraints (solved by SMT)

      resulting limit problem: [solved]



      applying transformation rule (C) using substitution {R==0,free_98==n,free_76==n,free_34==n,free_35==2+n,free==n}

      resulting limit problem:

      [solved]



   Solution:

      R / 0

      free_98 / n

      free_76 / n

      free_34 / n

      free_35 / 2+n

      free / 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+R+free_76

   Rule guard:  [ free_76>=3 && free>=1 && 2<=free_98 && R>=0 && free_34>=2 && 1+free<=-1+free_35 ]



WORST_CASE(INF,?)


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

(2)
BOUNDS(INF, INF)