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