5.66/2.43 WORST_CASE(NON_POLY, ?) 5.66/2.44 proof of /export/starexec/sandbox/benchmark/theBenchmark.koat 5.66/2.44 # AProVE Commit ID: 48fb2092695e11cc9f56e44b17a92a5f88ffb256 marcel 20180622 unpublished dirty 5.66/2.44 5.66/2.44 5.66/2.44 The runtime complexity of the given CpxIntTrs could be proven to be BOUNDS(INF, INF). 5.66/2.44 5.66/2.44 (0) CpxIntTrs 5.66/2.44 (1) Loat Proof [FINISHED, 672 ms] 5.66/2.44 (2) BOUNDS(INF, INF) 5.66/2.44 5.66/2.44 5.66/2.44 ---------------------------------------- 5.66/2.44 5.66/2.44 (0) 5.66/2.44 Obligation: 5.66/2.44 Complexity Int TRS consisting of the following rules: 5.66/2.44 f11(A, B, C, D, E, F, G, H, I, J, K, L, M, N, O, P, Q, R, S, T, U, V, W, X, Y, Z, A1, B1, C1, D1, E1, F1, G1, H1) -> Com_1(f11(A, 1 + B, D, I1, D, J1, B, I, I, J, K, L, M, N, O, P, Q, R, S, T, U, V, W, X, Y, Z, A1, B1, C1, D1, E1, F1, G1, H1)) :|: A >= B + 1 && B >= 0 5.66/2.44 f2(A, B, C, D, E, F, G, H, I, J, K, L, M, N, O, P, Q, R, S, T, U, V, W, X, Y, Z, A1, B1, C1, D1, E1, F1, G1, H1) -> Com_1(f2(A, B, C, D, E, F, G, H, I, J, I1, J1, J, J1, J, Q, Q, I, S, T, U, V, W, X, Y, Z, A1, B1, C1, D1, E1, F1, G1, H1)) :|: 0 >= J + 1 && I1 >= 2 5.66/2.44 f2(A, B, C, D, E, F, G, H, I, J, K, L, M, N, O, P, Q, R, S, T, U, V, W, X, Y, Z, A1, B1, C1, D1, E1, F1, G1, H1) -> Com_1(f2(A, B, C, D, E, F, G, H, I, J, I1, J1, J, J1, J, Q, Q, I, S, T, U, V, W, X, Y, Z, A1, B1, C1, D1, E1, F1, G1, H1)) :|: J >= 1 && I1 >= 2 5.66/2.44 f5(A, B, C, D, E, F, G, H, I, J, K, L, M, N, O, P, Q, R, S, T, U, V, W, X, Y, Z, A1, B1, C1, D1, E1, F1, G1, H1) -> Com_1(f5(A, B, C, D, E, F, G, H, I, J, 1, I1, J, I1, J, P, Q, R, I, U, U, V, W, X, Y, Z, A1, B1, C1, D1, E1, F1, G1, H1)) :|: 0 >= J + 1 5.66/2.44 f5(A, B, C, D, E, F, G, H, I, J, K, L, M, N, O, P, Q, R, S, T, U, V, W, X, Y, Z, A1, B1, C1, D1, E1, F1, G1, H1) -> Com_1(f5(A, B, C, D, E, F, G, H, I, J, 1, I1, J, I1, J, P, Q, R, I, U, U, V, W, X, Y, Z, A1, B1, C1, D1, E1, F1, G1, H1)) :|: J >= 1 5.66/2.44 f0(A, B, C, D, E, F, G, H, I, J, K, L, M, N, O, P, Q, R, S, T, U, V, W, X, Y, Z, A1, B1, C1, D1, E1, F1, G1, H1) -> Com_1(f11(J1, 2, K1, L1, K1, F, G, H, I, J, J1, L, M, N, O, P, Q, R, S, T, U, I1, K1, M1, Y, Z, A1, B1, C1, D1, E1, F1, G1, H1)) :|: J1 >= 2 5.66/2.44 f0(A, B, C, D, E, F, G, H, I, J, K, L, M, N, O, P, Q, R, S, T, U, V, W, X, Y, Z, A1, B1, C1, D1, E1, F1, G1, H1) -> Com_1(f1(K1, M1, L1, U1, T1, F, G, H, I, P1, J1, V1, W1, N, X1, P, Q, R, S, T, U, I1, S1, X, D2, Q1, R1, Y1, Z1, A2, B2, C2, E2, H1)) :|: 0 >= N1 && 0 >= J1 && 0 >= O1 && Y >= 0 && Y <= 0 5.66/2.44 f0(A, B, C, D, E, F, G, H, I, J, K, L, M, N, O, P, Q, R, S, T, U, V, W, X, Y, Z, A1, B1, C1, D1, E1, F1, G1, H1) -> Com_1(f5(J1, L1, K1, S1, R1, F, G, H, I, J, 1, T1, J, T1, J, P, Q, R, S, T, U, I1, Q1, X, Y, M1, P1, B1, C1, D1, E1, F1, G1, H1)) :|: 0 >= J + 1 5.66/2.44 f0(A, B, C, D, E, F, G, H, I, J, K, L, M, N, O, P, Q, R, S, T, U, V, W, X, Y, Z, A1, B1, C1, D1, E1, F1, G1, H1) -> Com_1(f5(J1, L1, K1, S1, R1, F, G, H, I, J, 1, T1, J, T1, J, P, Q, R, S, T, U, I1, Q1, X, Y, M1, P1, B1, C1, D1, E1, F1, G1, H1)) :|: J >= 1 5.66/2.44 f11(A, B, C, D, E, F, G, H, I, J, K, L, M, N, O, P, Q, R, S, T, U, V, W, X, Y, Z, A1, B1, C1, D1, E1, F1, G1, H1) -> Com_1(f2(J1, L1, K1, S1, R1, F, G, H, I, J, I1, T1, J, T1, J, P, Q, R, S, T, U, V, Q1, X, Y, M1, P1, B1, C1, D1, E1, F1, G1, H1)) :|: U1 >= 2 && H1 >= U1 && V1 >= 2 && H1 >= V1 && B >= A && B >= 0 && I1 >= 2 && 0 >= J + 1 && H1 >= 0 5.66/2.44 f11(A, B, C, D, E, F, G, H, I, J, K, L, M, N, O, P, Q, R, S, T, U, V, W, X, Y, Z, A1, B1, C1, D1, E1, F1, G1, H1) -> Com_1(f2(J1, L1, K1, S1, R1, F, G, H, I, J, I1, T1, J, T1, J, P, Q, R, S, T, U, V, Q1, X, Y, M1, P1, B1, C1, D1, E1, F1, G1, H1)) :|: U1 >= 2 && H1 >= U1 && V1 >= 2 && H1 >= V1 && B >= A && B >= 0 && I1 >= 2 && J >= 1 && H1 >= 0 5.66/2.44 5.66/2.44 The start-symbols are:[f0_34] 5.66/2.44 5.66/2.44 5.66/2.44 ---------------------------------------- 5.66/2.44 5.66/2.44 (1) Loat Proof (FINISHED) 5.66/2.44 5.66/2.44 5.66/2.44 ### Pre-processing the ITS problem ### 5.66/2.44 5.66/2.44 5.66/2.44 5.66/2.44 Initial linear ITS problem 5.66/2.44 5.66/2.44 Start location: f0 5.66/2.44 5.66/2.44 0: f11 -> f11 : B'=1+B, C'=D, D'=free_1, E'=D, F'=free, G'=B, H'=Q, [ A>=1+B && B>=0 ], cost: 1 5.66/2.44 5.66/2.44 9: f11 -> f2 : A'=free_62, A1'=free_63, B'=free_56, C'=free_65, D'=free_60, E'=free_58, K'=free_64, L'=free_61, M'=J, N'=free_61, O'=J, W'=free_59, Z'=free_67, [ free_57>=2 && H1>=free_57 && free_66>=2 && H1>=free_66 && B>=A && B>=0 && free_64>=2 && 0>=1+J && H1>=0 ], cost: 1 5.66/2.44 5.66/2.44 10: f11 -> f2 : A'=free_74, A1'=free_75, B'=free_68, C'=free_77, D'=free_72, E'=free_70, K'=free_76, L'=free_73, M'=J, N'=free_73, O'=J, W'=free_71, Z'=free_79, [ free_69>=2 && H1>=free_69 && free_78>=2 && H1>=free_78 && B>=A && B>=0 && free_76>=2 && J>=1 && H1>=0 ], cost: 1 5.66/2.44 5.66/2.44 1: f2 -> f2 : K'=free_3, L'=free_2, M'=J, N'=free_2, O'=J, P'=Q_1, R'=Q, [ 0>=1+J && free_3>=2 ], cost: 1 5.66/2.44 5.66/2.44 2: f2 -> f2 : K'=free_5, L'=free_4, M'=J, N'=free_4, O'=J, P'=Q_1, R'=Q, [ J>=1 && free_5>=2 ], cost: 1 5.66/2.44 5.66/2.44 3: f5 -> f5 : K'=1, L'=free_6, M'=J, N'=free_6, O'=J, S'=Q, T'=U, [ 0>=1+J ], cost: 1 5.66/2.44 5.66/2.44 4: f5 -> f5 : K'=1, L'=free_7, M'=J, N'=free_7, O'=J, S'=Q, T'=U, [ J>=1 ], cost: 1 5.66/2.44 5.66/2.44 5: f0 -> f11 : A'=free_11, B'=2, C'=free_8, D'=free_12, E'=free_8, K'=free_11, V'=free_10, W'=free_8, X'=free_9, [ free_11>=2 ], cost: 1 5.66/2.44 5.66/2.44 6: f0 -> f1 : A'=free_26, A1'=free_15, A2'=free_30, B'=free_23, B1'=free_18, B2'=F, C'=G, C1'=H, C2'=Q, D'=free_29, D1'=free_25, D2'=free_21, E'=free_33, E1'=N, E2'=free_27, F'=P, F1'=Q_1, G'=R, G1'=S, H'=T, H1'=U, Q'=free_16, Q1'=free_31, J'=X, J1'=free_24, K'=free_34, K1'=free_28, L'=free_19, L1'=free_22, M'=free_20, M1'=free_17, N'=free_14, N1'=free_35, O'=H1, [ 0>=free_32 && 0>=free_25 && 0>=free_13 && Y==0 ], cost: 1 5.66/2.44 5.66/2.44 7: f0 -> f5 : A'=free_41, A1'=free_42, B'=free_36, C'=free_44, D'=free_39, E'=free_37, K'=1, L'=free_43, M'=J, N'=free_43, O'=J, V'=free_40, W'=free_38, Z'=free_45, [ 0>=1+J ], cost: 1 5.66/2.44 5.66/2.44 8: f0 -> f5 : A'=free_51, A1'=free_52, B'=free_46, C'=free_54, D'=free_49, E'=free_47, K'=1, L'=free_53, M'=J, N'=free_53, O'=J, V'=free_50, W'=free_48, Z'=free_55, [ J>=1 ], cost: 1 5.66/2.44 5.66/2.44 5.66/2.44 5.66/2.44 Removed unreachable and leaf rules: 5.66/2.44 5.66/2.44 Start location: f0 5.66/2.44 5.66/2.44 0: f11 -> f11 : B'=1+B, C'=D, D'=free_1, E'=D, F'=free, G'=B, H'=Q, [ A>=1+B && B>=0 ], cost: 1 5.66/2.44 5.66/2.44 9: f11 -> f2 : A'=free_62, A1'=free_63, B'=free_56, C'=free_65, D'=free_60, E'=free_58, K'=free_64, L'=free_61, M'=J, N'=free_61, O'=J, W'=free_59, Z'=free_67, [ free_57>=2 && H1>=free_57 && free_66>=2 && H1>=free_66 && B>=A && B>=0 && free_64>=2 && 0>=1+J && H1>=0 ], cost: 1 5.66/2.44 5.66/2.44 10: f11 -> f2 : A'=free_74, A1'=free_75, B'=free_68, C'=free_77, D'=free_72, E'=free_70, K'=free_76, L'=free_73, M'=J, N'=free_73, O'=J, W'=free_71, Z'=free_79, [ free_69>=2 && H1>=free_69 && free_78>=2 && H1>=free_78 && B>=A && B>=0 && free_76>=2 && J>=1 && H1>=0 ], cost: 1 5.66/2.44 5.66/2.44 1: f2 -> f2 : K'=free_3, L'=free_2, M'=J, N'=free_2, O'=J, P'=Q_1, R'=Q, [ 0>=1+J && free_3>=2 ], cost: 1 5.66/2.44 5.66/2.44 2: f2 -> f2 : K'=free_5, L'=free_4, M'=J, N'=free_4, O'=J, P'=Q_1, R'=Q, [ J>=1 && free_5>=2 ], cost: 1 5.66/2.44 5.66/2.44 3: f5 -> f5 : K'=1, L'=free_6, M'=J, N'=free_6, O'=J, S'=Q, T'=U, [ 0>=1+J ], cost: 1 5.66/2.44 5.66/2.44 4: f5 -> f5 : K'=1, L'=free_7, M'=J, N'=free_7, O'=J, S'=Q, T'=U, [ J>=1 ], cost: 1 5.66/2.44 5.66/2.44 5: f0 -> f11 : A'=free_11, B'=2, C'=free_8, D'=free_12, E'=free_8, K'=free_11, V'=free_10, W'=free_8, X'=free_9, [ free_11>=2 ], cost: 1 5.66/2.44 5.66/2.44 7: f0 -> f5 : A'=free_41, A1'=free_42, B'=free_36, C'=free_44, D'=free_39, E'=free_37, K'=1, L'=free_43, M'=J, N'=free_43, O'=J, V'=free_40, W'=free_38, Z'=free_45, [ 0>=1+J ], cost: 1 5.66/2.44 5.66/2.44 8: f0 -> f5 : A'=free_51, A1'=free_52, B'=free_46, C'=free_54, D'=free_49, E'=free_47, K'=1, L'=free_53, M'=J, N'=free_53, O'=J, V'=free_50, W'=free_48, Z'=free_55, [ J>=1 ], cost: 1 5.66/2.44 5.66/2.44 5.66/2.44 5.66/2.44 Simplified all rules, resulting in: 5.66/2.44 5.66/2.44 Start location: f0 5.66/2.44 5.66/2.44 0: f11 -> f11 : B'=1+B, C'=D, D'=free_1, E'=D, F'=free, G'=B, H'=Q, [ A>=1+B && B>=0 ], cost: 1 5.66/2.44 5.66/2.44 9: f11 -> f2 : A'=free_62, A1'=free_63, B'=free_56, C'=free_65, D'=free_60, E'=free_58, K'=free_64, L'=free_61, M'=J, N'=free_61, O'=J, W'=free_59, Z'=free_67, [ B>=A && B>=0 && free_64>=2 && 0>=1+J && 2<=H1 ], cost: 1 5.66/2.44 5.66/2.44 10: f11 -> f2 : A'=free_74, A1'=free_75, B'=free_68, C'=free_77, D'=free_72, E'=free_70, K'=free_76, L'=free_73, M'=J, N'=free_73, O'=J, W'=free_71, Z'=free_79, [ B>=A && B>=0 && free_76>=2 && J>=1 && 2<=H1 ], cost: 1 5.66/2.44 5.66/2.44 1: f2 -> f2 : K'=free_3, L'=free_2, M'=J, N'=free_2, O'=J, P'=Q_1, R'=Q, [ 0>=1+J && free_3>=2 ], cost: 1 5.66/2.44 5.66/2.44 2: f2 -> f2 : K'=free_5, L'=free_4, M'=J, N'=free_4, O'=J, P'=Q_1, R'=Q, [ J>=1 && free_5>=2 ], cost: 1 5.66/2.44 5.66/2.44 3: f5 -> f5 : K'=1, L'=free_6, M'=J, N'=free_6, O'=J, S'=Q, T'=U, [ 0>=1+J ], cost: 1 5.66/2.44 5.66/2.44 4: f5 -> f5 : K'=1, L'=free_7, M'=J, N'=free_7, O'=J, S'=Q, T'=U, [ J>=1 ], cost: 1 5.66/2.44 5.66/2.44 5: f0 -> f11 : A'=free_11, B'=2, C'=free_8, D'=free_12, E'=free_8, K'=free_11, V'=free_10, W'=free_8, X'=free_9, [ free_11>=2 ], cost: 1 5.66/2.44 5.66/2.44 7: f0 -> f5 : A'=free_41, A1'=free_42, B'=free_36, C'=free_44, D'=free_39, E'=free_37, K'=1, L'=free_43, M'=J, N'=free_43, O'=J, V'=free_40, W'=free_38, Z'=free_45, [ 0>=1+J ], cost: 1 5.66/2.44 5.66/2.44 8: f0 -> f5 : A'=free_51, A1'=free_52, B'=free_46, C'=free_54, D'=free_49, E'=free_47, K'=1, L'=free_53, M'=J, N'=free_53, O'=J, V'=free_50, W'=free_48, Z'=free_55, [ J>=1 ], cost: 1 5.66/2.44 5.66/2.44 5.66/2.44 5.66/2.44 ### Simplification by acceleration and chaining ### 5.66/2.44 5.66/2.44 5.66/2.44 5.66/2.44 Accelerating simple loops of location 0. 5.66/2.44 5.66/2.44 Accelerating the following rules: 5.66/2.44 5.66/2.44 0: f11 -> f11 : B'=1+B, C'=D, D'=free_1, E'=D, F'=free, G'=B, H'=Q, [ A>=1+B && B>=0 ], cost: 1 5.66/2.44 5.66/2.44 5.66/2.44 5.66/2.44 Accelerated rule 0 with metering function -B+A, yielding the new rule 11. 5.66/2.44 5.66/2.44 Removing the simple loops: 0. 5.66/2.44 5.66/2.44 5.66/2.44 5.66/2.44 Accelerating simple loops of location 1. 5.66/2.44 5.66/2.44 Accelerating the following rules: 5.66/2.44 5.66/2.44 1: f2 -> f2 : K'=free_3, L'=free_2, M'=J, N'=free_2, O'=J, P'=Q_1, R'=Q, [ 0>=1+J && free_3>=2 ], cost: 1 5.66/2.44 5.66/2.44 2: f2 -> f2 : K'=free_5, L'=free_4, M'=J, N'=free_4, O'=J, P'=Q_1, R'=Q, [ J>=1 && free_5>=2 ], cost: 1 5.66/2.44 5.66/2.44 5.66/2.44 5.66/2.44 Accelerated rule 1 with NONTERM, yielding the new rule 12. 5.66/2.44 5.66/2.44 Accelerated rule 2 with NONTERM, yielding the new rule 13. 5.66/2.44 5.66/2.44 Removing the simple loops: 1 2. 5.66/2.44 5.66/2.44 5.66/2.44 5.66/2.44 Accelerating simple loops of location 2. 5.66/2.44 5.66/2.44 Accelerating the following rules: 5.66/2.44 5.66/2.44 3: f5 -> f5 : K'=1, L'=free_6, M'=J, N'=free_6, O'=J, S'=Q, T'=U, [ 0>=1+J ], cost: 1 5.66/2.44 5.66/2.44 4: f5 -> f5 : K'=1, L'=free_7, M'=J, N'=free_7, O'=J, S'=Q, T'=U, [ J>=1 ], cost: 1 5.66/2.44 5.66/2.44 5.66/2.44 5.66/2.44 Accelerated rule 3 with NONTERM, yielding the new rule 14. 5.66/2.44 5.66/2.44 Accelerated rule 4 with NONTERM, yielding the new rule 15. 5.66/2.44 5.66/2.44 Removing the simple loops: 3 4. 5.66/2.44 5.66/2.44 5.66/2.44 5.66/2.44 Accelerated all simple loops using metering functions (where possible): 5.66/2.44 5.66/2.44 Start location: f0 5.66/2.44 5.66/2.44 9: f11 -> f2 : A'=free_62, A1'=free_63, B'=free_56, C'=free_65, D'=free_60, E'=free_58, K'=free_64, L'=free_61, M'=J, N'=free_61, O'=J, W'=free_59, Z'=free_67, [ B>=A && B>=0 && free_64>=2 && 0>=1+J && 2<=H1 ], cost: 1 5.66/2.44 5.66/2.44 10: f11 -> f2 : A'=free_74, A1'=free_75, B'=free_68, C'=free_77, D'=free_72, E'=free_70, K'=free_76, L'=free_73, M'=J, N'=free_73, O'=J, W'=free_71, Z'=free_79, [ B>=A && B>=0 && free_76>=2 && J>=1 && 2<=H1 ], cost: 1 5.66/2.44 5.66/2.44 11: f11 -> f11 : B'=A, C'=free_1, D'=free_1, E'=free_1, F'=free, G'=-1+A, H'=Q, [ A>=1+B && B>=0 ], cost: -B+A 5.66/2.44 5.66/2.44 12: f2 -> [6] : [ 0>=1+J && free_3>=2 ], cost: INF 5.66/2.44 5.66/2.44 13: f2 -> [6] : [ J>=1 && free_5>=2 ], cost: INF 5.66/2.44 5.66/2.44 14: f5 -> [7] : [ 0>=1+J ], cost: INF 5.66/2.44 5.66/2.44 15: f5 -> [7] : [ J>=1 ], cost: INF 5.66/2.44 5.66/2.44 5: f0 -> f11 : A'=free_11, B'=2, C'=free_8, D'=free_12, E'=free_8, K'=free_11, V'=free_10, W'=free_8, X'=free_9, [ free_11>=2 ], cost: 1 5.66/2.44 5.66/2.44 7: f0 -> f5 : A'=free_41, A1'=free_42, B'=free_36, C'=free_44, D'=free_39, E'=free_37, K'=1, L'=free_43, M'=J, N'=free_43, O'=J, V'=free_40, W'=free_38, Z'=free_45, [ 0>=1+J ], cost: 1 5.66/2.44 5.66/2.44 8: f0 -> f5 : A'=free_51, A1'=free_52, B'=free_46, C'=free_54, D'=free_49, E'=free_47, K'=1, L'=free_53, M'=J, N'=free_53, O'=J, V'=free_50, W'=free_48, Z'=free_55, [ J>=1 ], cost: 1 5.66/2.44 5.66/2.44 5.66/2.44 5.66/2.44 Chained accelerated rules (with incoming rules): 5.66/2.44 5.66/2.44 Start location: f0 5.66/2.44 5.66/2.44 9: f11 -> f2 : A'=free_62, A1'=free_63, B'=free_56, C'=free_65, D'=free_60, E'=free_58, K'=free_64, L'=free_61, M'=J, N'=free_61, O'=J, W'=free_59, Z'=free_67, [ B>=A && B>=0 && free_64>=2 && 0>=1+J && 2<=H1 ], cost: 1 5.66/2.44 5.66/2.44 10: f11 -> f2 : A'=free_74, A1'=free_75, B'=free_68, C'=free_77, D'=free_72, E'=free_70, K'=free_76, L'=free_73, M'=J, N'=free_73, O'=J, W'=free_71, Z'=free_79, [ B>=A && B>=0 && free_76>=2 && J>=1 && 2<=H1 ], cost: 1 5.66/2.44 5.66/2.44 17: f11 -> [6] : A'=free_62, A1'=free_63, B'=free_56, C'=free_65, D'=free_60, E'=free_58, K'=free_64, L'=free_61, M'=J, N'=free_61, O'=J, W'=free_59, Z'=free_67, [ B>=A && B>=0 && free_64>=2 && 0>=1+J && 2<=H1 ], cost: INF 5.66/2.44 5.66/2.44 18: f11 -> [6] : A'=free_74, A1'=free_75, B'=free_68, C'=free_77, D'=free_72, E'=free_70, K'=free_76, L'=free_73, M'=J, N'=free_73, O'=J, W'=free_71, Z'=free_79, [ B>=A && B>=0 && free_76>=2 && J>=1 && 2<=H1 ], cost: INF 5.66/2.44 5.66/2.44 5: f0 -> f11 : A'=free_11, B'=2, C'=free_8, D'=free_12, E'=free_8, K'=free_11, V'=free_10, W'=free_8, X'=free_9, [ free_11>=2 ], cost: 1 5.66/2.44 5.66/2.44 7: f0 -> f5 : A'=free_41, A1'=free_42, B'=free_36, C'=free_44, D'=free_39, E'=free_37, K'=1, L'=free_43, M'=J, N'=free_43, O'=J, V'=free_40, W'=free_38, Z'=free_45, [ 0>=1+J ], cost: 1 5.66/2.44 5.66/2.44 8: f0 -> f5 : A'=free_51, A1'=free_52, B'=free_46, C'=free_54, D'=free_49, E'=free_47, K'=1, L'=free_53, M'=J, N'=free_53, O'=J, V'=free_50, W'=free_48, Z'=free_55, [ J>=1 ], cost: 1 5.66/2.44 5.66/2.44 16: f0 -> f11 : A'=free_11, B'=free_11, C'=free_1, D'=free_1, E'=free_1, F'=free, G'=-1+free_11, H'=Q, K'=free_11, V'=free_10, W'=free_8, X'=free_9, [ free_11>=3 ], cost: -1+free_11 5.66/2.44 5.66/2.44 19: f0 -> [7] : A'=free_41, A1'=free_42, B'=free_36, C'=free_44, D'=free_39, E'=free_37, K'=1, L'=free_43, M'=J, N'=free_43, O'=J, V'=free_40, W'=free_38, Z'=free_45, [ 0>=1+J ], cost: INF 5.66/2.44 5.66/2.44 20: f0 -> [7] : A'=free_51, A1'=free_52, B'=free_46, C'=free_54, D'=free_49, E'=free_47, K'=1, L'=free_53, M'=J, N'=free_53, O'=J, V'=free_50, W'=free_48, Z'=free_55, [ J>=1 ], cost: INF 5.66/2.44 5.66/2.44 5.66/2.44 5.66/2.44 Removed unreachable locations (and leaf rules with constant cost): 5.66/2.44 5.66/2.44 Start location: f0 5.66/2.44 5.66/2.44 17: f11 -> [6] : A'=free_62, A1'=free_63, B'=free_56, C'=free_65, D'=free_60, E'=free_58, K'=free_64, L'=free_61, M'=J, N'=free_61, O'=J, W'=free_59, Z'=free_67, [ B>=A && B>=0 && free_64>=2 && 0>=1+J && 2<=H1 ], cost: INF 5.66/2.44 5.66/2.44 18: f11 -> [6] : A'=free_74, A1'=free_75, B'=free_68, C'=free_77, D'=free_72, E'=free_70, K'=free_76, L'=free_73, M'=J, N'=free_73, O'=J, W'=free_71, Z'=free_79, [ B>=A && B>=0 && free_76>=2 && J>=1 && 2<=H1 ], cost: INF 5.66/2.44 5.66/2.44 5: f0 -> f11 : A'=free_11, B'=2, C'=free_8, D'=free_12, E'=free_8, K'=free_11, V'=free_10, W'=free_8, X'=free_9, [ free_11>=2 ], cost: 1 5.66/2.44 5.66/2.44 16: f0 -> f11 : A'=free_11, B'=free_11, C'=free_1, D'=free_1, E'=free_1, F'=free, G'=-1+free_11, H'=Q, K'=free_11, V'=free_10, W'=free_8, X'=free_9, [ free_11>=3 ], cost: -1+free_11 5.66/2.44 5.66/2.44 19: f0 -> [7] : A'=free_41, A1'=free_42, B'=free_36, C'=free_44, D'=free_39, E'=free_37, K'=1, L'=free_43, M'=J, N'=free_43, O'=J, V'=free_40, W'=free_38, Z'=free_45, [ 0>=1+J ], cost: INF 5.66/2.44 5.66/2.44 20: f0 -> [7] : A'=free_51, A1'=free_52, B'=free_46, C'=free_54, D'=free_49, E'=free_47, K'=1, L'=free_53, M'=J, N'=free_53, O'=J, V'=free_50, W'=free_48, Z'=free_55, [ J>=1 ], cost: INF 5.66/2.44 5.66/2.44 5.66/2.44 5.66/2.44 Eliminated locations (on tree-shaped paths): 5.66/2.44 5.66/2.44 Start location: f0 5.66/2.44 5.66/2.44 19: f0 -> [7] : A'=free_41, A1'=free_42, B'=free_36, C'=free_44, D'=free_39, E'=free_37, K'=1, L'=free_43, M'=J, N'=free_43, O'=J, V'=free_40, W'=free_38, Z'=free_45, [ 0>=1+J ], cost: INF 5.66/2.44 5.66/2.44 20: f0 -> [7] : A'=free_51, A1'=free_52, B'=free_46, C'=free_54, D'=free_49, E'=free_47, K'=1, L'=free_53, M'=J, N'=free_53, O'=J, V'=free_50, W'=free_48, Z'=free_55, [ J>=1 ], cost: INF 5.66/2.44 5.66/2.44 21: f0 -> [6] : A'=free_62, A1'=free_63, B'=free_56, C'=free_65, D'=free_60, E'=free_58, K'=free_64, L'=free_61, M'=J, N'=free_61, O'=J, V'=free_10, W'=free_59, X'=free_9, Z'=free_67, [ free_11>=2 && 2>=free_11 && free_64>=2 && 0>=1+J && 2<=H1 ], cost: INF 5.66/2.44 5.66/2.44 22: f0 -> [6] : A'=free_74, A1'=free_75, B'=free_68, C'=free_77, D'=free_72, E'=free_70, K'=free_76, L'=free_73, M'=J, N'=free_73, O'=J, V'=free_10, W'=free_71, X'=free_9, Z'=free_79, [ free_11>=2 && 2>=free_11 && free_76>=2 && J>=1 && 2<=H1 ], cost: INF 5.66/2.44 5.66/2.44 23: f0 -> [6] : A'=free_62, A1'=free_63, B'=free_56, C'=free_65, D'=free_60, E'=free_58, F'=free, G'=-1+free_11, H'=Q, K'=free_64, L'=free_61, M'=J, N'=free_61, O'=J, V'=free_10, W'=free_59, X'=free_9, Z'=free_67, [ free_11>=3 && free_64>=2 && 0>=1+J && 2<=H1 ], cost: INF 5.66/2.44 5.66/2.44 24: f0 -> [6] : A'=free_74, A1'=free_75, B'=free_68, C'=free_77, D'=free_72, E'=free_70, F'=free, G'=-1+free_11, H'=Q, K'=free_76, L'=free_73, M'=J, N'=free_73, O'=J, V'=free_10, W'=free_71, X'=free_9, Z'=free_79, [ free_11>=3 && free_76>=2 && J>=1 && 2<=H1 ], cost: INF 5.66/2.44 5.66/2.44 5.66/2.44 5.66/2.44 ### Computing asymptotic complexity ### 5.66/2.44 5.66/2.44 5.66/2.44 5.66/2.44 Fully simplified ITS problem 5.66/2.44 5.66/2.44 Start location: f0 5.66/2.44 5.66/2.44 19: f0 -> [7] : A'=free_41, A1'=free_42, B'=free_36, C'=free_44, D'=free_39, E'=free_37, K'=1, L'=free_43, M'=J, N'=free_43, O'=J, V'=free_40, W'=free_38, Z'=free_45, [ 0>=1+J ], cost: INF 5.66/2.44 5.66/2.44 20: f0 -> [7] : A'=free_51, A1'=free_52, B'=free_46, C'=free_54, D'=free_49, E'=free_47, K'=1, L'=free_53, M'=J, N'=free_53, O'=J, V'=free_50, W'=free_48, Z'=free_55, [ J>=1 ], cost: INF 5.66/2.44 5.66/2.44 21: f0 -> [6] : A'=free_62, A1'=free_63, B'=free_56, C'=free_65, D'=free_60, E'=free_58, K'=free_64, L'=free_61, M'=J, N'=free_61, O'=J, V'=free_10, W'=free_59, X'=free_9, Z'=free_67, [ free_11>=2 && 2>=free_11 && free_64>=2 && 0>=1+J && 2<=H1 ], cost: INF 5.66/2.44 5.66/2.44 22: f0 -> [6] : A'=free_74, A1'=free_75, B'=free_68, C'=free_77, D'=free_72, E'=free_70, K'=free_76, L'=free_73, M'=J, N'=free_73, O'=J, V'=free_10, W'=free_71, X'=free_9, Z'=free_79, [ free_11>=2 && 2>=free_11 && free_76>=2 && J>=1 && 2<=H1 ], cost: INF 5.66/2.44 5.66/2.44 23: f0 -> [6] : A'=free_62, A1'=free_63, B'=free_56, C'=free_65, D'=free_60, E'=free_58, F'=free, G'=-1+free_11, H'=Q, K'=free_64, L'=free_61, M'=J, N'=free_61, O'=J, V'=free_10, W'=free_59, X'=free_9, Z'=free_67, [ free_11>=3 && free_64>=2 && 0>=1+J && 2<=H1 ], cost: INF 5.66/2.44 5.66/2.44 24: f0 -> [6] : A'=free_74, A1'=free_75, B'=free_68, C'=free_77, D'=free_72, E'=free_70, F'=free, G'=-1+free_11, H'=Q, K'=free_76, L'=free_73, M'=J, N'=free_73, O'=J, V'=free_10, W'=free_71, X'=free_9, Z'=free_79, [ free_11>=3 && free_76>=2 && J>=1 && 2<=H1 ], cost: INF 5.66/2.44 5.66/2.44 5.66/2.44 5.66/2.44 Computing asymptotic complexity for rule 19 5.66/2.44 5.66/2.44 Resulting cost INF has complexity: Nonterm 5.66/2.44 5.66/2.44 5.66/2.44 5.66/2.44 Found new complexity Nonterm. 5.66/2.44 5.66/2.44 5.66/2.44 5.66/2.44 Obtained the following overall complexity (w.r.t. the length of the input n): 5.66/2.44 5.66/2.44 Complexity: Nonterm 5.66/2.44 5.66/2.44 Cpx degree: Nonterm 5.66/2.44 5.66/2.44 Solved cost: INF 5.66/2.44 5.66/2.44 Rule cost: INF 5.66/2.44 5.66/2.44 Rule guard: [ 0>=1+J ] 5.66/2.44 5.66/2.44 5.66/2.44 5.66/2.44 NO 5.66/2.44 5.66/2.44 5.66/2.44 ---------------------------------------- 5.66/2.44 5.66/2.44 (2) 5.66/2.44 BOUNDS(INF, INF) 5.66/2.47 EOF