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