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