6.97/3.06 WORST_CASE(NON_POLY, ?) 6.97/3.07 proof of /export/starexec/sandbox/benchmark/theBenchmark.koat 6.97/3.07 # AProVE Commit ID: 48fb2092695e11cc9f56e44b17a92a5f88ffb256 marcel 20180622 unpublished dirty 6.97/3.07 6.97/3.07 6.97/3.07 The runtime complexity of the given CpxIntTrs could be proven to be BOUNDS(INF, INF). 6.97/3.07 6.97/3.07 (0) CpxIntTrs 6.97/3.07 (1) Loat Proof [FINISHED, 1305 ms] 6.97/3.07 (2) BOUNDS(INF, INF) 6.97/3.07 6.97/3.07 6.97/3.07 ---------------------------------------- 6.97/3.07 6.97/3.07 (0) 6.97/3.07 Obligation: 6.97/3.07 Complexity Int TRS consisting of the following rules: 6.97/3.07 f33(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(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)) :|: TRUE 6.97/3.07 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(f25(G1, B, B, 0, 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)) :|: A >= 1 && B >= 1 && G1 >= 1 6.97/3.07 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(f25(G1, B, B, 0, 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)) :|: A >= 1 && 0 >= B + 1 && G1 >= 1 6.97/3.07 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(f16(J, B, C, D, G1, H1, H1, H1, H1, 1 + J, H1, L, M, N, O, P, Q, R, S, T, U, V, W, X, Y, Z, A1, B1, C1, D1, E1, F1)) :|: TRUE 6.97/3.07 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(f16(1 + H1, B, C, D, E, G1, G1, G1, G1, 1 + J, G1, L, M, N, O, P, Q, R, S, T, U, V, W, X, Y, Z, A1, B1, C1, D1, E1, F1)) :|: H1 >= 0 && A >= 0 6.97/3.07 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(f22(G1, L, 0, 0, E, F, G, H, L, J, K, L, L, L, O, P, Q, R, S, T, U, V, W, X, Y, Z, A1, B1, C1, D1, E1, F1)) :|: H1 >= 1 && A >= 1 && B >= 0 && B <= 0 6.97/3.07 f23(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(f17(A, B, C, D, E, F, G, H, I, K1, 0, L, 0, N, G1, H1, J1, G1, L1, T, U, V, W, X, Y, Z, A1, B1, C1, D1, E1, F1)) :|: G1 >= 1 && 0 >= I1 6.97/3.07 f23(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(f17(A, B, C, D, E, F, G, H, I, K1, 0, L, 0, N, G1, H1, J1, G1, L1, T, U, V, W, X, Y, Z, A1, B1, C1, D1, E1, F1)) :|: 0 >= G1 + 1 && 0 >= I1 6.97/3.07 f23(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(f21(A, B, C, D, E, F, G, H, G1, K1, 0, L, 0, N, 0, H1, J1, 0, L1, 0, U, V, W, X, Y, Z, A1, B1, C1, D1, E1, F1)) :|: 0 >= I1 6.97/3.07 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) -> Com_1(f16(1 + H1, B, C, D, E, G1, G1, G1, G1, 1 + L1, G1, L, M, N, O, J1, K1, R, S, T, I1, N1, O1, P1, Q1, Z, A1, B1, C1, D1, E1, F1)) :|: A >= 0 && M1 >= 0 && Q >= 1 + J && H1 >= 0 6.97/3.07 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) -> Com_1(f18(G1, B, C, D, E, F, G, H, I, K1, K, L, 0, N, 0, H1, J1, 0, S, T, U, V, W, X, Y, L1, A1, B1, C1, D1, E1, F1)) :|: A >= 0 && I1 >= 0 && J >= Q && G1 >= 0 6.97/3.07 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) -> Com_1(f3(G1, N1, C, D, E, F, G, H, I, I1, J1, Q1, 0, N, H1, K1, L1, M1, S, T, U, V, W, X, Y, V1, O1, P1, T1, U1, E1, F1)) :|: A >= 0 && R1 >= 0 && S1 >= 0 && J >= Q && O1 >= 1 6.97/3.07 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) -> Com_1(f3(G1, N1, C, D, E, F, G, H, I, I1, J1, Q1, 0, N, H1, K1, L1, M1, S, T, U, V, W, X, Y, V1, O1, P1, T1, U1, E1, F1)) :|: A >= 0 && R1 >= 0 && S1 >= 0 && J >= Q && 0 >= O1 + 1 6.97/3.07 f23(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(f16(H1, B, C, D, E, G1, G1, G1, G1, 1 + H1, G1, L, M, N, O, J1, K1, R, S, T, L1, I1, N1, X, Y, Z, A1, B1, C1, D1, O1, P1)) :|: Q1 >= 1 6.97/3.07 6.97/3.07 The start-symbols are:[f33_32] 6.97/3.07 6.97/3.07 6.97/3.07 ---------------------------------------- 6.97/3.07 6.97/3.07 (1) Loat Proof (FINISHED) 6.97/3.07 6.97/3.07 6.97/3.07 ### Pre-processing the ITS problem ### 6.97/3.07 6.97/3.07 6.97/3.07 6.97/3.07 Initial linear ITS problem 6.97/3.07 6.97/3.07 Start location: f33 6.97/3.07 6.97/3.07 0: f33 -> f3 : [], cost: 1 6.97/3.07 6.97/3.07 1: f3 -> f25 : A'=free, A1'=B, B1'=0, C'=E, C1'=F, D'=G, D1'=H, E'=Q, E1'=J, F'=K, F1'=L, G'=M, G1'=N, H'=O, H1'=P, Q'=Q_1, Q1'=R, J'=S, J1'=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, [ A>=1 && B>=1 && free>=1 ], cost: 1 6.97/3.07 6.97/3.07 2: f3 -> f25 : A'=free_1, A1'=B, B1'=0, C'=E, C1'=F, D'=G, D1'=H, E'=Q, E1'=J, F'=K, F1'=L, G'=M, G1'=N, H'=O, H1'=P, Q'=Q_1, Q1'=R, J'=S, J1'=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, [ A>=1 && 0>=1+B && free_1>=1 ], cost: 1 6.97/3.07 6.97/3.07 3: f3 -> f16 : A'=E, E'=1+E, F'=free_3, G'=free_2, H'=free_2, Q'=free_2, J'=free_2, K'=free_2, [], cost: 1 6.97/3.07 6.97/3.07 4: f3 -> f16 : A'=1+free_5, E'=1+E, G'=free_4, H'=free_4, Q'=free_4, J'=free_4, K'=free_4, [ free_5>=0 && A>=0 ], cost: 1 6.97/3.07 6.97/3.07 5: f3 -> f22 : A'=free_7, A1'=L, B'=0, B1'=0, C'=E, C1'=F, D'=G, D1'=H, E'=Q, E1'=L, F'=K, F1'=L, G'=L, G1'=L, H'=O, H1'=P, Q'=Q_1, Q1'=R, J'=S, 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_6>=1 && A>=1 && B==0 ], cost: 1 6.97/3.07 6.97/3.07 6: f23 -> f17 : A1'=B, B'=C, B1'=D, C'=free_11, C1'=F, D'=G, D1'=H, E'=Q, E1'=J, F'=0, F1'=L, G'=0, G1'=N, H'=free_9, H1'=free_10, Q'=free_8, Q1'=free_9, J'=free_12, 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_9>=1 && 0>=free_13 ], cost: 1 6.97/3.07 6.97/3.07 7: f23 -> f17 : A1'=B, B'=C, B1'=D, C'=free_17, C1'=F, D'=G, D1'=H, E'=Q, E1'=J, F'=0, F1'=L, G'=0, G1'=N, H'=free_15, H1'=free_16, Q'=free_14, Q1'=free_15, J'=free_18, 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, [ 0>=1+free_15 && 0>=free_19 ], cost: 1 6.97/3.07 6.97/3.07 8: f23 -> f21 : A1'=B, B'=C, B1'=D, C'=free_21, C1'=F, D'=G, D1'=H, E'=Q, E1'=free_23, F'=0, F1'=L, G'=0, G1'=N, H'=0, H1'=free_22, Q'=free_20, Q1'=0, J'=free_24, J1'=0, K'=U, K1'=V, L'=W, L1'=X, M'=Y, M1'=Z, N'=A1, N1'=B1, O'=C1, O1'=D1, P'=E1, P1'=F1, [ 0>=free_25 ], cost: 1 6.97/3.07 6.97/3.07 13: f23 -> f16 : A'=free_81, E'=1+free_81, E1'=free_83, F1'=free_79, G'=free_78, H'=free_78, Q'=free_78, J'=free_78, K'=free_78, P'=free_80, Q_1'=free_77, U'=free_82, V'=free_84, W'=free_75, [ free_76>=1 ], cost: 1 6.97/3.07 6.97/3.07 9: f16 -> f16 : A'=1+free_33, E'=1+free_32, G'=free_29, H'=free_29, Q'=free_29, J'=free_29, K'=free_29, P'=free_28, Q_1'=free_34, U'=free_36, V'=free_26, W'=free_35, X'=free_31, Y'=free_27, [ A>=0 && free_30>=0 && Q_1>=1+E && free_33>=0 ], cost: 1 6.97/3.07 6.97/3.07 10: f16 -> f18 : A'=free_40, A1'=B, B'=C, B1'=D, C'=free_38, C1'=F, D'=G, D1'=H, E'=Q, E1'=J, F'=K, F1'=L, G'=0, G1'=N, H'=0, H1'=free_39, Q'=free_37, Q1'=0, J'=S, J1'=T, K'=U, K1'=V, L'=W, L1'=X, M'=Y, M1'=free_41, N'=A1, N1'=B1, O'=C1, O1'=D1, P'=E1, P1'=F1, [ A>=0 && free_42>=0 && E>=Q_1 && free_40>=0 ], cost: 1 6.97/3.07 6.97/3.07 11: f16 -> f3 : A'=free_53, A1'=free_49, B'=free_47, B1'=free_58, C1'=free_52, D1'=free_46, E'=free_51, K'=free_45, L'=free_55, M'=0, O'=free_57, P'=free_43, Q_1'=free_56, R'=free_50, Z'=free_44, [ A>=0 && free_54>=0 && free_48>=0 && E>=Q_1 && free_49>=1 ], cost: 1 6.97/3.07 6.97/3.07 12: f16 -> f3 : A'=free_69, A1'=free_65, B'=free_63, B1'=free_74, C1'=free_68, D1'=free_62, E'=free_67, K'=free_61, L'=free_71, M'=0, O'=free_73, P'=free_59, Q_1'=free_72, R'=free_66, Z'=free_60, [ A>=0 && free_70>=0 && free_64>=0 && E>=Q_1 && 0>=1+free_65 ], cost: 1 6.97/3.07 6.97/3.07 6.97/3.07 6.97/3.07 Removed unreachable and leaf rules: 6.97/3.07 6.97/3.07 Start location: f33 6.97/3.07 6.97/3.07 0: f33 -> f3 : [], cost: 1 6.97/3.07 6.97/3.07 3: f3 -> f16 : A'=E, E'=1+E, F'=free_3, G'=free_2, H'=free_2, Q'=free_2, J'=free_2, K'=free_2, [], cost: 1 6.97/3.07 6.97/3.07 4: f3 -> f16 : A'=1+free_5, E'=1+E, G'=free_4, H'=free_4, Q'=free_4, J'=free_4, K'=free_4, [ free_5>=0 && A>=0 ], cost: 1 6.97/3.07 6.97/3.07 9: f16 -> f16 : A'=1+free_33, E'=1+free_32, G'=free_29, H'=free_29, Q'=free_29, J'=free_29, K'=free_29, P'=free_28, Q_1'=free_34, U'=free_36, V'=free_26, W'=free_35, X'=free_31, Y'=free_27, [ A>=0 && free_30>=0 && Q_1>=1+E && free_33>=0 ], cost: 1 6.97/3.07 6.97/3.07 11: f16 -> f3 : A'=free_53, A1'=free_49, B'=free_47, B1'=free_58, C1'=free_52, D1'=free_46, E'=free_51, K'=free_45, L'=free_55, M'=0, O'=free_57, P'=free_43, Q_1'=free_56, R'=free_50, Z'=free_44, [ A>=0 && free_54>=0 && free_48>=0 && E>=Q_1 && free_49>=1 ], cost: 1 6.97/3.07 6.97/3.07 12: f16 -> f3 : A'=free_69, A1'=free_65, B'=free_63, B1'=free_74, C1'=free_68, D1'=free_62, E'=free_67, K'=free_61, L'=free_71, M'=0, O'=free_73, P'=free_59, Q_1'=free_72, R'=free_66, Z'=free_60, [ A>=0 && free_70>=0 && free_64>=0 && E>=Q_1 && 0>=1+free_65 ], cost: 1 6.97/3.07 6.97/3.07 6.97/3.07 6.97/3.07 Simplified all rules, resulting in: 6.97/3.07 6.97/3.07 Start location: f33 6.97/3.07 6.97/3.07 0: f33 -> f3 : [], cost: 1 6.97/3.07 6.97/3.07 3: f3 -> f16 : A'=E, E'=1+E, F'=free_3, G'=free_2, H'=free_2, Q'=free_2, J'=free_2, K'=free_2, [], cost: 1 6.97/3.07 6.97/3.07 4: f3 -> f16 : A'=1+free_5, E'=1+E, G'=free_4, H'=free_4, Q'=free_4, J'=free_4, K'=free_4, [ free_5>=0 && A>=0 ], cost: 1 6.97/3.07 6.97/3.07 9: f16 -> f16 : A'=1+free_33, E'=1+free_32, G'=free_29, H'=free_29, Q'=free_29, J'=free_29, K'=free_29, P'=free_28, Q_1'=free_34, U'=free_36, V'=free_26, W'=free_35, X'=free_31, Y'=free_27, [ A>=0 && Q_1>=1+E && free_33>=0 ], cost: 1 6.97/3.07 6.97/3.07 11: f16 -> f3 : A'=free_53, A1'=free_49, B'=free_47, B1'=free_58, C1'=free_52, D1'=free_46, E'=free_51, K'=free_45, L'=free_55, M'=0, O'=free_57, P'=free_43, Q_1'=free_56, R'=free_50, Z'=free_44, [ A>=0 && E>=Q_1 && free_49>=1 ], cost: 1 6.97/3.07 6.97/3.07 12: f16 -> f3 : A'=free_69, A1'=free_65, B'=free_63, B1'=free_74, C1'=free_68, D1'=free_62, E'=free_67, K'=free_61, L'=free_71, M'=0, O'=free_73, P'=free_59, Q_1'=free_72, R'=free_66, Z'=free_60, [ A>=0 && E>=Q_1 && 0>=1+free_65 ], cost: 1 6.97/3.07 6.97/3.07 6.97/3.07 6.97/3.07 ### Simplification by acceleration and chaining ### 6.97/3.07 6.97/3.07 6.97/3.07 6.97/3.07 Accelerating simple loops of location 3. 6.97/3.07 6.97/3.07 Accelerating the following rules: 6.97/3.07 6.97/3.07 9: f16 -> f16 : A'=1+free_33, E'=1+free_32, G'=free_29, H'=free_29, Q'=free_29, J'=free_29, K'=free_29, P'=free_28, Q_1'=free_34, U'=free_36, V'=free_26, W'=free_35, X'=free_31, Y'=free_27, [ A>=0 && Q_1>=1+E && free_33>=0 ], cost: 1 6.97/3.07 6.97/3.07 6.97/3.07 6.97/3.07 Accelerated rule 9 with NONTERM (after strengthening guard), yielding the new rule 14. 6.97/3.07 6.97/3.07 Removing the simple loops:. 6.97/3.07 6.97/3.07 6.97/3.07 6.97/3.07 Accelerated all simple loops using metering functions (where possible): 6.97/3.07 6.97/3.07 Start location: f33 6.97/3.07 6.97/3.07 0: f33 -> f3 : [], cost: 1 6.97/3.07 6.97/3.07 3: f3 -> f16 : A'=E, E'=1+E, F'=free_3, G'=free_2, H'=free_2, Q'=free_2, J'=free_2, K'=free_2, [], cost: 1 6.97/3.07 6.97/3.07 4: f3 -> f16 : A'=1+free_5, E'=1+E, G'=free_4, H'=free_4, Q'=free_4, J'=free_4, K'=free_4, [ free_5>=0 && A>=0 ], cost: 1 6.97/3.07 6.97/3.07 9: f16 -> f16 : A'=1+free_33, E'=1+free_32, G'=free_29, H'=free_29, Q'=free_29, J'=free_29, K'=free_29, P'=free_28, Q_1'=free_34, U'=free_36, V'=free_26, W'=free_35, X'=free_31, Y'=free_27, [ A>=0 && Q_1>=1+E && free_33>=0 ], cost: 1 6.97/3.07 6.97/3.07 11: f16 -> f3 : A'=free_53, A1'=free_49, B'=free_47, B1'=free_58, C1'=free_52, D1'=free_46, E'=free_51, K'=free_45, L'=free_55, M'=0, O'=free_57, P'=free_43, Q_1'=free_56, R'=free_50, Z'=free_44, [ A>=0 && E>=Q_1 && free_49>=1 ], cost: 1 6.97/3.07 6.97/3.07 12: f16 -> f3 : A'=free_69, A1'=free_65, B'=free_63, B1'=free_74, C1'=free_68, D1'=free_62, E'=free_67, K'=free_61, L'=free_71, M'=0, O'=free_73, P'=free_59, Q_1'=free_72, R'=free_66, Z'=free_60, [ A>=0 && E>=Q_1 && 0>=1+free_65 ], cost: 1 6.97/3.07 6.97/3.07 14: f16 -> [9] : [ A>=0 && Q_1>=1+E && free_33>=0 && free_34>=2+free_32 ], cost: INF 6.97/3.07 6.97/3.07 6.97/3.07 6.97/3.07 Chained accelerated rules (with incoming rules): 6.97/3.07 6.97/3.07 Start location: f33 6.97/3.07 6.97/3.07 0: f33 -> f3 : [], cost: 1 6.97/3.07 6.97/3.07 3: f3 -> f16 : A'=E, E'=1+E, F'=free_3, G'=free_2, H'=free_2, Q'=free_2, J'=free_2, K'=free_2, [], cost: 1 6.97/3.07 6.97/3.07 4: f3 -> f16 : A'=1+free_5, E'=1+E, G'=free_4, H'=free_4, Q'=free_4, J'=free_4, K'=free_4, [ free_5>=0 && A>=0 ], cost: 1 6.97/3.07 6.97/3.07 15: f3 -> f16 : A'=1+free_33, E'=1+free_32, F'=free_3, G'=free_29, H'=free_29, Q'=free_29, J'=free_29, K'=free_29, P'=free_28, Q_1'=free_34, U'=free_36, V'=free_26, W'=free_35, X'=free_31, Y'=free_27, [ E>=0 && Q_1>=2+E && free_33>=0 ], cost: 2 6.97/3.07 6.97/3.07 16: f3 -> f16 : A'=1+free_33, E'=1+free_32, G'=free_29, H'=free_29, Q'=free_29, J'=free_29, K'=free_29, P'=free_28, Q_1'=free_34, U'=free_36, V'=free_26, W'=free_35, X'=free_31, Y'=free_27, [ A>=0 && Q_1>=2+E && free_33>=0 ], cost: 2 6.97/3.07 6.97/3.07 17: f3 -> [9] : A'=E, E'=1+E, F'=free_3, G'=free_2, H'=free_2, Q'=free_2, J'=free_2, K'=free_2, [ E>=0 && Q_1>=2+E ], cost: INF 6.97/3.07 6.97/3.07 18: f3 -> [9] : A'=1+free_5, E'=1+E, G'=free_4, H'=free_4, Q'=free_4, J'=free_4, K'=free_4, [ free_5>=0 && A>=0 && Q_1>=2+E ], cost: INF 6.97/3.07 6.97/3.07 11: f16 -> f3 : A'=free_53, A1'=free_49, B'=free_47, B1'=free_58, C1'=free_52, D1'=free_46, E'=free_51, K'=free_45, L'=free_55, M'=0, O'=free_57, P'=free_43, Q_1'=free_56, R'=free_50, Z'=free_44, [ A>=0 && E>=Q_1 && free_49>=1 ], cost: 1 6.97/3.07 6.97/3.07 12: f16 -> f3 : A'=free_69, A1'=free_65, B'=free_63, B1'=free_74, C1'=free_68, D1'=free_62, E'=free_67, K'=free_61, L'=free_71, M'=0, O'=free_73, P'=free_59, Q_1'=free_72, R'=free_66, Z'=free_60, [ A>=0 && E>=Q_1 && 0>=1+free_65 ], cost: 1 6.97/3.07 6.97/3.07 6.97/3.07 6.97/3.07 Eliminated locations (on tree-shaped paths): 6.97/3.07 6.97/3.07 Start location: f33 6.97/3.07 6.97/3.07 0: f33 -> f3 : [], cost: 1 6.97/3.07 6.97/3.07 17: f3 -> [9] : A'=E, E'=1+E, F'=free_3, G'=free_2, H'=free_2, Q'=free_2, J'=free_2, K'=free_2, [ E>=0 && Q_1>=2+E ], cost: INF 6.97/3.07 6.97/3.07 18: f3 -> [9] : A'=1+free_5, E'=1+E, G'=free_4, H'=free_4, Q'=free_4, J'=free_4, K'=free_4, [ free_5>=0 && A>=0 && Q_1>=2+E ], cost: INF 6.97/3.07 6.97/3.07 19: f3 -> f3 : A'=free_53, A1'=free_49, B'=free_47, B1'=free_58, C1'=free_52, D1'=free_46, E'=free_51, F'=free_3, G'=free_2, H'=free_2, Q'=free_2, J'=free_2, K'=free_45, L'=free_55, M'=0, O'=free_57, P'=free_43, Q_1'=free_56, R'=free_50, Z'=free_44, [ E>=0 && 1+E>=Q_1 && free_49>=1 ], cost: 2 6.97/3.07 6.97/3.07 20: f3 -> f3 : A'=free_69, A1'=free_65, B'=free_63, B1'=free_74, C1'=free_68, D1'=free_62, E'=free_67, F'=free_3, G'=free_2, H'=free_2, Q'=free_2, J'=free_2, K'=free_61, L'=free_71, M'=0, O'=free_73, P'=free_59, Q_1'=free_72, R'=free_66, Z'=free_60, [ E>=0 && 1+E>=Q_1 && 0>=1+free_65 ], cost: 2 6.97/3.07 6.97/3.07 21: f3 -> f3 : A'=free_53, A1'=free_49, B'=free_47, B1'=free_58, C1'=free_52, D1'=free_46, E'=free_51, G'=free_4, H'=free_4, Q'=free_4, J'=free_4, K'=free_45, L'=free_55, M'=0, O'=free_57, P'=free_43, Q_1'=free_56, R'=free_50, Z'=free_44, [ free_5>=0 && A>=0 && 1+E>=Q_1 && free_49>=1 ], cost: 2 6.97/3.07 6.97/3.07 22: f3 -> f3 : A'=free_69, A1'=free_65, B'=free_63, B1'=free_74, C1'=free_68, D1'=free_62, E'=free_67, G'=free_4, H'=free_4, Q'=free_4, J'=free_4, K'=free_61, L'=free_71, M'=0, O'=free_73, P'=free_59, Q_1'=free_72, R'=free_66, Z'=free_60, [ free_5>=0 && A>=0 && 1+E>=Q_1 && 0>=1+free_65 ], cost: 2 6.97/3.07 6.97/3.07 23: f3 -> f3 : A'=free_53, A1'=free_49, B'=free_47, B1'=free_58, C1'=free_52, D1'=free_46, E'=free_51, F'=free_3, G'=free_29, H'=free_29, Q'=free_29, J'=free_29, K'=free_45, L'=free_55, M'=0, O'=free_57, P'=free_43, Q_1'=free_56, R'=free_50, U'=free_36, V'=free_26, W'=free_35, X'=free_31, Y'=free_27, Z'=free_44, [ E>=0 && Q_1>=2+E && free_33>=0 && 1+free_32>=free_34 && free_49>=1 ], cost: 3 6.97/3.07 6.97/3.07 24: f3 -> f3 : A'=free_69, A1'=free_65, B'=free_63, B1'=free_74, C1'=free_68, D1'=free_62, E'=free_67, F'=free_3, G'=free_29, H'=free_29, Q'=free_29, J'=free_29, K'=free_61, L'=free_71, M'=0, O'=free_73, P'=free_59, Q_1'=free_72, R'=free_66, U'=free_36, V'=free_26, W'=free_35, X'=free_31, Y'=free_27, Z'=free_60, [ E>=0 && Q_1>=2+E && free_33>=0 && 1+free_32>=free_34 && 0>=1+free_65 ], cost: 3 6.97/3.07 6.97/3.07 25: f3 -> f3 : A'=free_53, A1'=free_49, B'=free_47, B1'=free_58, C1'=free_52, D1'=free_46, E'=free_51, G'=free_29, H'=free_29, Q'=free_29, J'=free_29, K'=free_45, L'=free_55, M'=0, O'=free_57, P'=free_43, Q_1'=free_56, R'=free_50, U'=free_36, V'=free_26, W'=free_35, X'=free_31, Y'=free_27, Z'=free_44, [ A>=0 && Q_1>=2+E && free_33>=0 && 1+free_32>=free_34 && free_49>=1 ], cost: 3 6.97/3.07 6.97/3.07 26: f3 -> f3 : A'=free_69, A1'=free_65, B'=free_63, B1'=free_74, C1'=free_68, D1'=free_62, E'=free_67, G'=free_29, H'=free_29, Q'=free_29, J'=free_29, K'=free_61, L'=free_71, M'=0, O'=free_73, P'=free_59, Q_1'=free_72, R'=free_66, U'=free_36, V'=free_26, W'=free_35, X'=free_31, Y'=free_27, Z'=free_60, [ A>=0 && Q_1>=2+E && free_33>=0 && 1+free_32>=free_34 && 0>=1+free_65 ], cost: 3 6.97/3.07 6.97/3.07 6.97/3.07 6.97/3.07 Applied pruning (of leafs and parallel rules): 6.97/3.07 6.97/3.07 Start location: f33 6.97/3.07 6.97/3.07 0: f33 -> f3 : [], cost: 1 6.97/3.07 6.97/3.07 17: f3 -> [9] : A'=E, E'=1+E, F'=free_3, G'=free_2, H'=free_2, Q'=free_2, J'=free_2, K'=free_2, [ E>=0 && Q_1>=2+E ], cost: INF 6.97/3.07 6.97/3.07 18: f3 -> [9] : A'=1+free_5, E'=1+E, G'=free_4, H'=free_4, Q'=free_4, J'=free_4, K'=free_4, [ free_5>=0 && A>=0 && Q_1>=2+E ], cost: INF 6.97/3.07 6.97/3.07 19: f3 -> f3 : A'=free_53, A1'=free_49, B'=free_47, B1'=free_58, C1'=free_52, D1'=free_46, E'=free_51, F'=free_3, G'=free_2, H'=free_2, Q'=free_2, J'=free_2, K'=free_45, L'=free_55, M'=0, O'=free_57, P'=free_43, Q_1'=free_56, R'=free_50, Z'=free_44, [ E>=0 && 1+E>=Q_1 && free_49>=1 ], cost: 2 6.97/3.07 6.97/3.07 20: f3 -> f3 : A'=free_69, A1'=free_65, B'=free_63, B1'=free_74, C1'=free_68, D1'=free_62, E'=free_67, F'=free_3, G'=free_2, H'=free_2, Q'=free_2, J'=free_2, K'=free_61, L'=free_71, M'=0, O'=free_73, P'=free_59, Q_1'=free_72, R'=free_66, Z'=free_60, [ E>=0 && 1+E>=Q_1 && 0>=1+free_65 ], cost: 2 6.97/3.07 6.97/3.07 22: f3 -> f3 : A'=free_69, A1'=free_65, B'=free_63, B1'=free_74, C1'=free_68, D1'=free_62, E'=free_67, G'=free_4, H'=free_4, Q'=free_4, J'=free_4, K'=free_61, L'=free_71, M'=0, O'=free_73, P'=free_59, Q_1'=free_72, R'=free_66, Z'=free_60, [ free_5>=0 && A>=0 && 1+E>=Q_1 && 0>=1+free_65 ], cost: 2 6.97/3.07 6.97/3.07 23: f3 -> f3 : A'=free_53, A1'=free_49, B'=free_47, B1'=free_58, C1'=free_52, D1'=free_46, E'=free_51, F'=free_3, G'=free_29, H'=free_29, Q'=free_29, J'=free_29, K'=free_45, L'=free_55, M'=0, O'=free_57, P'=free_43, Q_1'=free_56, R'=free_50, U'=free_36, V'=free_26, W'=free_35, X'=free_31, Y'=free_27, Z'=free_44, [ E>=0 && Q_1>=2+E && free_33>=0 && 1+free_32>=free_34 && free_49>=1 ], cost: 3 6.97/3.07 6.97/3.07 24: f3 -> f3 : A'=free_69, A1'=free_65, B'=free_63, B1'=free_74, C1'=free_68, D1'=free_62, E'=free_67, F'=free_3, G'=free_29, H'=free_29, Q'=free_29, J'=free_29, K'=free_61, L'=free_71, M'=0, O'=free_73, P'=free_59, Q_1'=free_72, R'=free_66, U'=free_36, V'=free_26, W'=free_35, X'=free_31, Y'=free_27, Z'=free_60, [ E>=0 && Q_1>=2+E && free_33>=0 && 1+free_32>=free_34 && 0>=1+free_65 ], cost: 3 6.97/3.07 6.97/3.07 6.97/3.07 6.97/3.07 Accelerating simple loops of location 1. 6.97/3.07 6.97/3.07 Simplified some of the simple loops (and removed duplicate rules). 6.97/3.07 6.97/3.07 Accelerating the following rules: 6.97/3.07 6.97/3.07 19: f3 -> f3 : A'=free_53, A1'=free_49, B'=free_47, B1'=free_58, C1'=free_52, D1'=free_46, E'=free_51, F'=free_3, G'=free_2, H'=free_2, Q'=free_2, J'=free_2, K'=free_45, L'=free_55, M'=0, O'=free_57, P'=free_43, Q_1'=free_56, R'=free_50, Z'=free_44, [ E>=0 && 1+E>=Q_1 && free_49>=1 ], cost: 2 6.97/3.07 6.97/3.07 20: f3 -> f3 : A'=free_69, A1'=free_65, B'=free_63, B1'=free_74, C1'=free_68, D1'=free_62, E'=free_67, F'=free_3, G'=free_2, H'=free_2, Q'=free_2, J'=free_2, K'=free_61, L'=free_71, M'=0, O'=free_73, P'=free_59, Q_1'=free_72, R'=free_66, Z'=free_60, [ E>=0 && 1+E>=Q_1 && 0>=1+free_65 ], cost: 2 6.97/3.07 6.97/3.07 22: f3 -> f3 : A'=free_69, A1'=free_65, B'=free_63, B1'=free_74, C1'=free_68, D1'=free_62, E'=free_67, G'=free_4, H'=free_4, Q'=free_4, J'=free_4, K'=free_61, L'=free_71, M'=0, O'=free_73, P'=free_59, Q_1'=free_72, R'=free_66, Z'=free_60, [ A>=0 && 1+E>=Q_1 && 0>=1+free_65 ], cost: 2 6.97/3.07 6.97/3.07 23: f3 -> f3 : A'=free_53, A1'=free_49, B'=free_47, B1'=free_58, C1'=free_52, D1'=free_46, E'=free_51, F'=free_3, G'=free_29, H'=free_29, Q'=free_29, J'=free_29, K'=free_45, L'=free_55, M'=0, O'=free_57, P'=free_43, Q_1'=free_56, R'=free_50, U'=free_36, V'=free_26, W'=free_35, X'=free_31, Y'=free_27, Z'=free_44, [ E>=0 && Q_1>=2+E && free_49>=1 ], cost: 3 6.97/3.07 6.97/3.07 24: f3 -> f3 : A'=free_69, A1'=free_65, B'=free_63, B1'=free_74, C1'=free_68, D1'=free_62, E'=free_67, F'=free_3, G'=free_29, H'=free_29, Q'=free_29, J'=free_29, K'=free_61, L'=free_71, M'=0, O'=free_73, P'=free_59, Q_1'=free_72, R'=free_66, U'=free_36, V'=free_26, W'=free_35, X'=free_31, Y'=free_27, Z'=free_60, [ E>=0 && Q_1>=2+E && 0>=1+free_65 ], cost: 3 6.97/3.07 6.97/3.07 6.97/3.07 6.97/3.07 Accelerated rule 19 with NONTERM (after strengthening guard), yielding the new rule 27. 6.97/3.07 6.97/3.07 Accelerated rule 20 with NONTERM (after strengthening guard), yielding the new rule 28. 6.97/3.07 6.97/3.07 Accelerated rule 22 with NONTERM (after strengthening guard), yielding the new rule 29. 6.97/3.07 6.97/3.07 Accelerated rule 23 with NONTERM (after strengthening guard), yielding the new rule 30. 6.97/3.07 6.97/3.07 Accelerated rule 24 with NONTERM (after strengthening guard), yielding the new rule 31. 6.97/3.07 6.97/3.07 Removing the simple loops:. 6.97/3.07 6.97/3.07 6.97/3.07 6.97/3.07 Accelerated all simple loops using metering functions (where possible): 6.97/3.07 6.97/3.07 Start location: f33 6.97/3.07 6.97/3.07 0: f33 -> f3 : [], cost: 1 6.97/3.07 6.97/3.07 17: f3 -> [9] : A'=E, E'=1+E, F'=free_3, G'=free_2, H'=free_2, Q'=free_2, J'=free_2, K'=free_2, [ E>=0 && Q_1>=2+E ], cost: INF 6.97/3.07 6.97/3.07 18: f3 -> [9] : A'=1+free_5, E'=1+E, G'=free_4, H'=free_4, Q'=free_4, J'=free_4, K'=free_4, [ free_5>=0 && A>=0 && Q_1>=2+E ], cost: INF 6.97/3.07 6.97/3.07 19: f3 -> f3 : A'=free_53, A1'=free_49, B'=free_47, B1'=free_58, C1'=free_52, D1'=free_46, E'=free_51, F'=free_3, G'=free_2, H'=free_2, Q'=free_2, J'=free_2, K'=free_45, L'=free_55, M'=0, O'=free_57, P'=free_43, Q_1'=free_56, R'=free_50, Z'=free_44, [ E>=0 && 1+E>=Q_1 && free_49>=1 ], cost: 2 6.97/3.07 6.97/3.07 20: f3 -> f3 : A'=free_69, A1'=free_65, B'=free_63, B1'=free_74, C1'=free_68, D1'=free_62, E'=free_67, F'=free_3, G'=free_2, H'=free_2, Q'=free_2, J'=free_2, K'=free_61, L'=free_71, M'=0, O'=free_73, P'=free_59, Q_1'=free_72, R'=free_66, Z'=free_60, [ E>=0 && 1+E>=Q_1 && 0>=1+free_65 ], cost: 2 6.97/3.07 6.97/3.07 22: f3 -> f3 : A'=free_69, A1'=free_65, B'=free_63, B1'=free_74, C1'=free_68, D1'=free_62, E'=free_67, G'=free_4, H'=free_4, Q'=free_4, J'=free_4, K'=free_61, L'=free_71, M'=0, O'=free_73, P'=free_59, Q_1'=free_72, R'=free_66, Z'=free_60, [ A>=0 && 1+E>=Q_1 && 0>=1+free_65 ], cost: 2 6.97/3.07 6.97/3.07 23: f3 -> f3 : A'=free_53, A1'=free_49, B'=free_47, B1'=free_58, C1'=free_52, D1'=free_46, E'=free_51, F'=free_3, G'=free_29, H'=free_29, Q'=free_29, J'=free_29, K'=free_45, L'=free_55, M'=0, O'=free_57, P'=free_43, Q_1'=free_56, R'=free_50, U'=free_36, V'=free_26, W'=free_35, X'=free_31, Y'=free_27, Z'=free_44, [ E>=0 && Q_1>=2+E && free_49>=1 ], cost: 3 6.97/3.07 6.97/3.07 24: f3 -> f3 : A'=free_69, A1'=free_65, B'=free_63, B1'=free_74, C1'=free_68, D1'=free_62, E'=free_67, F'=free_3, G'=free_29, H'=free_29, Q'=free_29, J'=free_29, K'=free_61, L'=free_71, M'=0, O'=free_73, P'=free_59, Q_1'=free_72, R'=free_66, U'=free_36, V'=free_26, W'=free_35, X'=free_31, Y'=free_27, Z'=free_60, [ E>=0 && Q_1>=2+E && 0>=1+free_65 ], cost: 3 6.97/3.07 6.97/3.07 27: f3 -> [10] : [ E>=0 && 1+E>=Q_1 && free_49>=1 && free_51>=0 && 1+free_51>=free_56 ], cost: INF 6.97/3.07 6.97/3.07 28: f3 -> [10] : [ E>=0 && 1+E>=Q_1 && 0>=1+free_65 && free_67>=0 && 1+free_67>=free_72 ], cost: INF 6.97/3.07 6.97/3.07 29: f3 -> [10] : [ A>=0 && 1+E>=Q_1 && 0>=1+free_65 && free_69>=0 && 1+free_67>=free_72 ], cost: INF 6.97/3.07 6.97/3.07 30: f3 -> [10] : [ E>=0 && Q_1>=2+E && free_49>=1 && free_51>=0 && free_56>=2+free_51 ], cost: INF 6.97/3.07 6.97/3.07 31: f3 -> [10] : [ E>=0 && Q_1>=2+E && 0>=1+free_65 && free_67>=0 && free_72>=2+free_67 ], cost: INF 6.97/3.07 6.97/3.07 6.97/3.07 6.97/3.07 Chained accelerated rules (with incoming rules): 6.97/3.07 6.97/3.07 Start location: f33 6.97/3.07 6.97/3.07 0: f33 -> f3 : [], cost: 1 6.97/3.07 6.97/3.07 32: f33 -> f3 : A'=free_53, A1'=free_49, B'=free_47, B1'=free_58, C1'=free_52, D1'=free_46, E'=free_51, F'=free_3, G'=free_2, H'=free_2, Q'=free_2, J'=free_2, K'=free_45, L'=free_55, M'=0, O'=free_57, P'=free_43, Q_1'=free_56, R'=free_50, Z'=free_44, [ E>=0 && 1+E>=Q_1 && free_49>=1 ], cost: 3 6.97/3.07 6.97/3.07 33: f33 -> f3 : A'=free_69, A1'=free_65, B'=free_63, B1'=free_74, C1'=free_68, D1'=free_62, E'=free_67, F'=free_3, G'=free_2, H'=free_2, Q'=free_2, J'=free_2, K'=free_61, L'=free_71, M'=0, O'=free_73, P'=free_59, Q_1'=free_72, R'=free_66, Z'=free_60, [ E>=0 && 1+E>=Q_1 && 0>=1+free_65 ], cost: 3 6.97/3.07 6.97/3.07 34: f33 -> f3 : A'=free_69, A1'=free_65, B'=free_63, B1'=free_74, C1'=free_68, D1'=free_62, E'=free_67, G'=free_4, H'=free_4, Q'=free_4, J'=free_4, K'=free_61, L'=free_71, M'=0, O'=free_73, P'=free_59, Q_1'=free_72, R'=free_66, Z'=free_60, [ A>=0 && 1+E>=Q_1 && 0>=1+free_65 ], cost: 3 6.97/3.07 6.97/3.07 35: f33 -> f3 : A'=free_53, A1'=free_49, B'=free_47, B1'=free_58, C1'=free_52, D1'=free_46, E'=free_51, F'=free_3, G'=free_29, H'=free_29, Q'=free_29, J'=free_29, K'=free_45, L'=free_55, M'=0, O'=free_57, P'=free_43, Q_1'=free_56, R'=free_50, U'=free_36, V'=free_26, W'=free_35, X'=free_31, Y'=free_27, Z'=free_44, [ E>=0 && Q_1>=2+E && free_49>=1 ], cost: 4 6.97/3.07 6.97/3.07 36: f33 -> f3 : A'=free_69, A1'=free_65, B'=free_63, B1'=free_74, C1'=free_68, D1'=free_62, E'=free_67, F'=free_3, G'=free_29, H'=free_29, Q'=free_29, J'=free_29, K'=free_61, L'=free_71, M'=0, O'=free_73, P'=free_59, Q_1'=free_72, R'=free_66, U'=free_36, V'=free_26, W'=free_35, X'=free_31, Y'=free_27, Z'=free_60, [ E>=0 && Q_1>=2+E && 0>=1+free_65 ], cost: 4 6.97/3.07 6.97/3.07 37: f33 -> [10] : [ E>=0 && 1+E>=Q_1 ], cost: INF 6.97/3.07 6.97/3.07 38: f33 -> [10] : [ E>=0 && 1+E>=Q_1 ], cost: INF 6.97/3.07 6.97/3.07 39: f33 -> [10] : [ A>=0 && 1+E>=Q_1 ], cost: INF 6.97/3.07 6.97/3.07 40: f33 -> [10] : [ E>=0 && Q_1>=2+E ], cost: INF 6.97/3.07 6.97/3.07 41: f33 -> [10] : [ E>=0 && Q_1>=2+E ], cost: INF 6.97/3.07 6.97/3.07 17: f3 -> [9] : A'=E, E'=1+E, F'=free_3, G'=free_2, H'=free_2, Q'=free_2, J'=free_2, K'=free_2, [ E>=0 && Q_1>=2+E ], cost: INF 6.97/3.07 6.97/3.07 18: f3 -> [9] : A'=1+free_5, E'=1+E, G'=free_4, H'=free_4, Q'=free_4, J'=free_4, K'=free_4, [ free_5>=0 && A>=0 && Q_1>=2+E ], cost: INF 6.97/3.07 6.97/3.07 6.97/3.07 6.97/3.07 Eliminated locations (on tree-shaped paths): 6.97/3.07 6.97/3.07 Start location: f33 6.97/3.07 6.97/3.07 37: f33 -> [10] : [ E>=0 && 1+E>=Q_1 ], cost: INF 6.97/3.07 6.97/3.07 38: f33 -> [10] : [ E>=0 && 1+E>=Q_1 ], cost: INF 6.97/3.07 6.97/3.07 39: f33 -> [10] : [ A>=0 && 1+E>=Q_1 ], cost: INF 6.97/3.07 6.97/3.07 40: f33 -> [10] : [ E>=0 && Q_1>=2+E ], cost: INF 6.97/3.07 6.97/3.07 41: f33 -> [10] : [ E>=0 && Q_1>=2+E ], cost: INF 6.97/3.07 6.97/3.07 42: f33 -> [9] : A'=E, E'=1+E, F'=free_3, G'=free_2, H'=free_2, Q'=free_2, J'=free_2, K'=free_2, [ E>=0 && Q_1>=2+E ], cost: INF 6.97/3.07 6.97/3.07 43: f33 -> [9] : A'=1+free_5, E'=1+E, G'=free_4, H'=free_4, Q'=free_4, J'=free_4, K'=free_4, [ free_5>=0 && A>=0 && Q_1>=2+E ], cost: INF 6.97/3.07 6.97/3.07 44: f33 -> [9] : A'=free_51, A1'=free_49, B'=free_47, B1'=free_58, C1'=free_52, D1'=free_46, E'=1+free_51, F'=free_3, G'=free_2, H'=free_2, Q'=free_2, J'=free_2, K'=free_2, L'=free_55, M'=0, O'=free_57, P'=free_43, Q_1'=free_56, R'=free_50, Z'=free_44, [ E>=0 && 1+E>=Q_1 && free_49>=1 && free_51>=0 && free_56>=2+free_51 ], cost: INF 6.97/3.07 6.97/3.07 45: f33 -> [9] : A'=1+free_5, A1'=free_49, B'=free_47, B1'=free_58, C1'=free_52, D1'=free_46, E'=1+free_51, F'=free_3, G'=free_4, H'=free_4, Q'=free_4, J'=free_4, K'=free_4, L'=free_55, M'=0, O'=free_57, P'=free_43, Q_1'=free_56, R'=free_50, Z'=free_44, [ E>=0 && 1+E>=Q_1 && free_49>=1 && free_5>=0 && free_53>=0 && free_56>=2+free_51 ], cost: INF 6.97/3.07 6.97/3.07 46: f33 -> [9] : A'=free_67, A1'=free_65, B'=free_63, B1'=free_74, C1'=free_68, D1'=free_62, E'=1+free_67, F'=free_3, G'=free_2, H'=free_2, Q'=free_2, J'=free_2, K'=free_2, L'=free_71, M'=0, O'=free_73, P'=free_59, Q_1'=free_72, R'=free_66, Z'=free_60, [ E>=0 && 1+E>=Q_1 && 0>=1+free_65 && free_67>=0 && free_72>=2+free_67 ], cost: INF 6.97/3.07 6.97/3.07 47: f33 -> [9] : A'=1+free_5, A1'=free_65, B'=free_63, B1'=free_74, C1'=free_68, D1'=free_62, E'=1+free_67, F'=free_3, G'=free_4, H'=free_4, Q'=free_4, J'=free_4, K'=free_4, L'=free_71, M'=0, O'=free_73, P'=free_59, Q_1'=free_72, R'=free_66, Z'=free_60, [ E>=0 && 1+E>=Q_1 && 0>=1+free_65 && free_5>=0 && free_69>=0 && free_72>=2+free_67 ], cost: INF 6.97/3.07 6.97/3.07 48: f33 -> [9] : A'=free_67, A1'=free_65, B'=free_63, B1'=free_74, C1'=free_68, D1'=free_62, E'=1+free_67, F'=free_3, G'=free_2, H'=free_2, Q'=free_2, J'=free_2, K'=free_2, L'=free_71, M'=0, O'=free_73, P'=free_59, Q_1'=free_72, R'=free_66, Z'=free_60, [ A>=0 && 1+E>=Q_1 && 0>=1+free_65 && free_67>=0 && free_72>=2+free_67 ], cost: INF 6.97/3.07 6.97/3.07 49: f33 -> [9] : A'=1+free_5, A1'=free_65, B'=free_63, B1'=free_74, C1'=free_68, D1'=free_62, E'=1+free_67, G'=free_4, H'=free_4, Q'=free_4, J'=free_4, K'=free_4, L'=free_71, M'=0, O'=free_73, P'=free_59, Q_1'=free_72, R'=free_66, Z'=free_60, [ A>=0 && 1+E>=Q_1 && 0>=1+free_65 && free_5>=0 && free_69>=0 && free_72>=2+free_67 ], cost: INF 6.97/3.07 6.97/3.07 50: f33 -> [9] : A'=free_51, A1'=free_49, B'=free_47, B1'=free_58, C1'=free_52, D1'=free_46, E'=1+free_51, F'=free_3, G'=free_2, H'=free_2, Q'=free_2, J'=free_2, K'=free_2, L'=free_55, M'=0, O'=free_57, P'=free_43, Q_1'=free_56, R'=free_50, U'=free_36, V'=free_26, W'=free_35, X'=free_31, Y'=free_27, Z'=free_44, [ E>=0 && Q_1>=2+E && free_49>=1 && free_51>=0 && free_56>=2+free_51 ], cost: INF 6.97/3.07 6.97/3.07 51: f33 -> [9] : A'=1+free_5, A1'=free_49, B'=free_47, B1'=free_58, C1'=free_52, D1'=free_46, E'=1+free_51, F'=free_3, G'=free_4, H'=free_4, Q'=free_4, J'=free_4, K'=free_4, L'=free_55, M'=0, O'=free_57, P'=free_43, Q_1'=free_56, R'=free_50, U'=free_36, V'=free_26, W'=free_35, X'=free_31, Y'=free_27, Z'=free_44, [ E>=0 && Q_1>=2+E && free_49>=1 && free_5>=0 && free_53>=0 && free_56>=2+free_51 ], cost: INF 6.97/3.07 6.97/3.07 52: f33 -> [9] : A'=free_67, A1'=free_65, B'=free_63, B1'=free_74, C1'=free_68, D1'=free_62, E'=1+free_67, F'=free_3, G'=free_2, H'=free_2, Q'=free_2, J'=free_2, K'=free_2, L'=free_71, M'=0, O'=free_73, P'=free_59, Q_1'=free_72, R'=free_66, U'=free_36, V'=free_26, W'=free_35, X'=free_31, Y'=free_27, Z'=free_60, [ E>=0 && Q_1>=2+E && 0>=1+free_65 && free_67>=0 && free_72>=2+free_67 ], cost: INF 6.97/3.07 6.97/3.07 53: f33 -> [9] : A'=1+free_5, A1'=free_65, B'=free_63, B1'=free_74, C1'=free_68, D1'=free_62, E'=1+free_67, F'=free_3, G'=free_4, H'=free_4, Q'=free_4, J'=free_4, K'=free_4, L'=free_71, M'=0, O'=free_73, P'=free_59, Q_1'=free_72, R'=free_66, U'=free_36, V'=free_26, W'=free_35, X'=free_31, Y'=free_27, Z'=free_60, [ E>=0 && Q_1>=2+E && 0>=1+free_65 && free_5>=0 && free_69>=0 && free_72>=2+free_67 ], cost: INF 6.97/3.07 6.97/3.07 6.97/3.07 6.97/3.07 Applied pruning (of leafs and parallel rules): 6.97/3.07 6.97/3.07 Start location: f33 6.97/3.07 6.97/3.07 38: f33 -> [10] : [ E>=0 && 1+E>=Q_1 ], cost: INF 6.97/3.07 6.97/3.07 39: f33 -> [10] : [ A>=0 && 1+E>=Q_1 ], cost: INF 6.97/3.07 6.97/3.07 41: f33 -> [10] : [ E>=0 && Q_1>=2+E ], cost: INF 6.97/3.07 6.97/3.07 42: f33 -> [9] : A'=E, E'=1+E, F'=free_3, G'=free_2, H'=free_2, Q'=free_2, J'=free_2, K'=free_2, [ E>=0 && Q_1>=2+E ], cost: INF 6.97/3.07 6.97/3.07 43: f33 -> [9] : A'=1+free_5, E'=1+E, G'=free_4, H'=free_4, Q'=free_4, J'=free_4, K'=free_4, [ free_5>=0 && A>=0 && Q_1>=2+E ], cost: INF 6.97/3.07 6.97/3.07 45: f33 -> [9] : A'=1+free_5, A1'=free_49, B'=free_47, B1'=free_58, C1'=free_52, D1'=free_46, E'=1+free_51, F'=free_3, G'=free_4, H'=free_4, Q'=free_4, J'=free_4, K'=free_4, L'=free_55, M'=0, O'=free_57, P'=free_43, Q_1'=free_56, R'=free_50, Z'=free_44, [ E>=0 && 1+E>=Q_1 && free_49>=1 && free_5>=0 && free_53>=0 && free_56>=2+free_51 ], cost: INF 6.97/3.07 6.97/3.07 47: f33 -> [9] : A'=1+free_5, A1'=free_65, B'=free_63, B1'=free_74, C1'=free_68, D1'=free_62, E'=1+free_67, F'=free_3, G'=free_4, H'=free_4, Q'=free_4, J'=free_4, K'=free_4, L'=free_71, M'=0, O'=free_73, P'=free_59, Q_1'=free_72, R'=free_66, Z'=free_60, [ E>=0 && 1+E>=Q_1 && 0>=1+free_65 && free_5>=0 && free_69>=0 && free_72>=2+free_67 ], cost: INF 6.97/3.07 6.97/3.07 48: f33 -> [9] : A'=free_67, A1'=free_65, B'=free_63, B1'=free_74, C1'=free_68, D1'=free_62, E'=1+free_67, F'=free_3, G'=free_2, H'=free_2, Q'=free_2, J'=free_2, K'=free_2, L'=free_71, M'=0, O'=free_73, P'=free_59, Q_1'=free_72, R'=free_66, Z'=free_60, [ A>=0 && 1+E>=Q_1 && 0>=1+free_65 && free_67>=0 && free_72>=2+free_67 ], cost: INF 6.97/3.07 6.97/3.07 6.97/3.07 6.97/3.07 ### Computing asymptotic complexity ### 6.97/3.07 6.97/3.07 6.97/3.07 6.97/3.07 Fully simplified ITS problem 6.97/3.07 6.97/3.07 Start location: f33 6.97/3.07 6.97/3.07 38: f33 -> [10] : [ E>=0 && 1+E>=Q_1 ], cost: INF 6.97/3.07 6.97/3.07 39: f33 -> [10] : [ A>=0 && 1+E>=Q_1 ], cost: INF 6.97/3.07 6.97/3.07 42: f33 -> [9] : A'=E, E'=1+E, F'=free_3, G'=free_2, H'=free_2, Q'=free_2, J'=free_2, K'=free_2, [ E>=0 && Q_1>=2+E ], cost: INF 6.97/3.07 6.97/3.07 43: f33 -> [9] : A'=1+free_5, E'=1+E, G'=free_4, H'=free_4, Q'=free_4, J'=free_4, K'=free_4, [ free_5>=0 && A>=0 && Q_1>=2+E ], cost: INF 6.97/3.07 6.97/3.07 45: f33 -> [9] : A'=1+free_5, A1'=free_49, B'=free_47, B1'=free_58, C1'=free_52, D1'=free_46, E'=1+free_51, F'=free_3, G'=free_4, H'=free_4, Q'=free_4, J'=free_4, K'=free_4, L'=free_55, M'=0, O'=free_57, P'=free_43, Q_1'=free_56, R'=free_50, Z'=free_44, [ E>=0 && 1+E>=Q_1 && free_49>=1 && free_5>=0 && free_53>=0 && free_56>=2+free_51 ], cost: INF 6.97/3.07 6.97/3.07 47: f33 -> [9] : A'=1+free_5, A1'=free_65, B'=free_63, B1'=free_74, C1'=free_68, D1'=free_62, E'=1+free_67, F'=free_3, G'=free_4, H'=free_4, Q'=free_4, J'=free_4, K'=free_4, L'=free_71, M'=0, O'=free_73, P'=free_59, Q_1'=free_72, R'=free_66, Z'=free_60, [ E>=0 && 1+E>=Q_1 && 0>=1+free_65 && free_5>=0 && free_69>=0 && free_72>=2+free_67 ], cost: INF 6.97/3.07 6.97/3.07 48: f33 -> [9] : A'=free_67, A1'=free_65, B'=free_63, B1'=free_74, C1'=free_68, D1'=free_62, E'=1+free_67, F'=free_3, G'=free_2, H'=free_2, Q'=free_2, J'=free_2, K'=free_2, L'=free_71, M'=0, O'=free_73, P'=free_59, Q_1'=free_72, R'=free_66, Z'=free_60, [ A>=0 && 1+E>=Q_1 && 0>=1+free_65 && free_67>=0 && free_72>=2+free_67 ], cost: INF 6.97/3.07 6.97/3.07 6.97/3.07 6.97/3.07 Computing asymptotic complexity for rule 38 6.97/3.07 6.97/3.07 Resulting cost INF has complexity: Nonterm 6.97/3.07 6.97/3.07 6.97/3.07 6.97/3.07 Found new complexity Nonterm. 6.97/3.07 6.97/3.07 6.97/3.07 6.97/3.07 Obtained the following overall complexity (w.r.t. the length of the input n): 6.97/3.07 6.97/3.07 Complexity: Nonterm 6.97/3.07 6.97/3.07 Cpx degree: Nonterm 6.97/3.07 6.97/3.07 Solved cost: INF 6.97/3.07 6.97/3.07 Rule cost: INF 6.97/3.07 6.97/3.07 Rule guard: [ E>=0 && 1+E>=Q_1 ] 6.97/3.07 6.97/3.07 6.97/3.07 6.97/3.07 NO 6.97/3.07 6.97/3.07 6.97/3.07 ---------------------------------------- 6.97/3.07 6.97/3.07 (2) 6.97/3.07 BOUNDS(INF, INF) 7.19/3.09 EOF