3.63/1.98 WORST_CASE(NON_POLY, ?) 3.63/1.99 proof of /export/starexec/sandbox/benchmark/theBenchmark.koat 3.63/1.99 # AProVE Commit ID: 48fb2092695e11cc9f56e44b17a92a5f88ffb256 marcel 20180622 unpublished dirty 3.63/1.99 3.63/1.99 3.63/1.99 The runtime complexity of the given CpxIntTrs could be proven to be BOUNDS(INF, INF). 3.63/1.99 3.63/1.99 (0) CpxIntTrs 3.63/1.99 (1) Loat Proof [FINISHED, 311 ms] 3.63/1.99 (2) BOUNDS(INF, INF) 3.63/1.99 3.63/1.99 3.63/1.99 ---------------------------------------- 3.63/1.99 3.63/1.99 (0) 3.63/1.99 Obligation: 3.63/1.99 Complexity Int TRS consisting of the following rules: 3.63/1.99 f2(A, B, C, D, E, F, G, H, I, J, K, L, M, N, O, P, Q, R, S, T, U, V, W) -> Com_1(f1(X, X, X, X, X, X, X, X, X, J, K, L, M, N, O, P, Q, R, S, T, U, V, W)) :|: TRUE 3.63/1.99 f1(A, B, C, D, E, F, G, H, I, J, K, L, M, N, O, P, Q, R, S, T, U, V, W) -> Com_1(f1(A, B, C, D, E, F, G, H, I, J, X, Z, A1, B1, C1, D1, Q, R, S, T, U, V, W)) :|: 0 >= Y && 0 >= J + 1 3.63/1.99 f1(A, B, C, D, E, F, G, H, I, J, K, L, M, N, O, P, Q, R, S, T, U, V, W) -> Com_1(f1(A, B, C, D, E, F, G, H, I, J, X, Z, A1, B1, O, P, C1, D1, Y, T, U, V, W)) :|: 0 >= J + 1 && E1 >= 1 && F1 >= 2 3.63/1.99 f1(A, B, C, D, E, F, G, H, I, J, K, L, M, N, O, P, Q, R, S, T, U, V, W) -> Com_1(f1(A, B, C, D, E, F, G, H, I, J, X, L, M, Z, A1, B1, Q, R, S, C1, D1, Y, W)) :|: 0 >= 2 + E1 && J >= 1 3.63/1.99 f1(A, B, C, D, E, F, G, H, I, J, K, L, M, N, O, P, Q, R, S, T, U, V, W) -> Com_1(f1(A, B, C, D, E, F, G, H, I, J, X, L, M, Z, O, P, A1, B1, C1, D1, Y, E1, W)) :|: J >= 1 && F1 >= 0 && G1 + 1 >= 0 3.63/1.99 f1(A, B, C, D, E, F, G, H, I, J, K, L, M, N, O, P, Q, R, S, T, U, V, W) -> Com_1(f300(A, B, C, D, E, F, G, H, I, J, X, Z, A1, B1, O, P, C1, R, S, T, U, V, D1)) :|: 1 >= Y && 0 >= J + 1 && E1 >= 1 3.63/1.99 f1(A, B, C, D, E, F, G, H, I, J, K, L, M, N, O, P, Q, R, S, T, U, V, W) -> Com_1(f300(A, B, C, D, E, F, G, H, I, J, X, L, M, Z, O, P, A1, R, S, B1, C1, D1, Y)) :|: 0 >= E1 + 1 && J >= 1 && F1 + 1 >= 0 3.63/1.99 f1(A, B, C, D, E, F, G, H, I, J, K, L, M, N, O, P, Q, R, S, T, U, V, W) -> Com_1(f300(A, B, C, D, E, F, G, H, I, J, X, L, M, N, O, P, Q, R, S, Z, U, V, A1)) :|: J >= 0 && J <= 0 3.63/1.99 3.63/1.99 The start-symbols are:[f2_23] 3.63/1.99 3.63/1.99 3.63/1.99 ---------------------------------------- 3.63/1.99 3.63/1.99 (1) Loat Proof (FINISHED) 3.63/1.99 3.63/1.99 3.63/1.99 ### Pre-processing the ITS problem ### 3.63/1.99 3.63/1.99 3.63/1.99 3.63/1.99 Initial linear ITS problem 3.63/1.99 3.63/1.99 Start location: f2 3.63/1.99 3.63/1.99 0: f2 -> f1 : A'=free, B'=free, C'=free, D'=free, E'=free, F'=free, G'=free, H'=free, Q'=free, [], cost: 1 3.63/1.99 3.63/1.99 1: f1 -> f1 : K'=free_1, L'=free_5, M'=free_7, N'=free_4, O'=free_2, P'=free_6, [ 0>=free_3 && 0>=1+J ], cost: 1 3.63/1.99 3.63/1.99 2: f1 -> f1 : K'=free_9, L'=free_14, M'=free_16, N'=free_13, Q_1'=free_10, R'=free_15, S'=free_12, [ 0>=1+J && free_11>=1 && free_8>=2 ], cost: 1 3.63/1.99 3.63/1.99 3: f1 -> f1 : K'=free_17, N'=free_22, O'=free_24, P'=free_21, T'=free_18, U'=free_23, V'=free_20, [ 0>=2+free_19 && J>=1 ], cost: 1 3.63/1.99 3.63/1.99 4: f1 -> f1 : K'=free_26, N'=free_32, Q_1'=free_34, R'=free_30, S'=free_27, T'=free_33, U'=free_29, V'=free_28, [ J>=1 && free_25>=0 && 1+free_31>=0 ], cost: 1 3.63/1.99 3.63/1.99 5: f1 -> f300 : A1'=B, B'=C, B1'=D, C'=E, C1'=F, D'=G, D1'=H, E'=Q, E1'=J, F'=free_35, F1'=free_40, G'=free_42, G1'=free_39, H'=O, Q'=P, J'=free_36, K'=R, L'=S, M'=T, N'=U, O'=V, P'=free_41, [ 1>=free_38 && 0>=1+J && free_37>=1 ], cost: 1 3.63/1.99 3.63/1.99 6: f1 -> f300 : A1'=B, B'=C, B1'=D, C'=E, C1'=F, D'=G, D1'=H, E'=Q, E1'=J, F'=free_44, F1'=L, G'=M, G1'=free_49, H'=O, Q'=P, J'=free_51, K'=R, L'=S, M'=free_48, N'=free_45, O'=free_50, P'=free_47, [ 0>=1+free_46 && J>=1 && 1+free_43>=0 ], cost: 1 3.63/1.99 3.63/1.99 7: f1 -> f300 : A1'=B, B'=C, B1'=D, C'=E, C1'=F, D'=G, D1'=H, E'=Q, E1'=J, F'=free_52, F1'=L, G'=M, G1'=N, H'=O, Q'=P, J'=Q_1, K'=R, L'=S, M'=free_53, N'=U, O'=V, P'=free_54, [ J==0 ], cost: 1 3.63/1.99 3.63/1.99 3.63/1.99 3.63/1.99 Removed unreachable and leaf rules: 3.63/1.99 3.63/1.99 Start location: f2 3.63/1.99 3.63/1.99 0: f2 -> f1 : A'=free, B'=free, C'=free, D'=free, E'=free, F'=free, G'=free, H'=free, Q'=free, [], cost: 1 3.63/1.99 3.63/1.99 1: f1 -> f1 : K'=free_1, L'=free_5, M'=free_7, N'=free_4, O'=free_2, P'=free_6, [ 0>=free_3 && 0>=1+J ], cost: 1 3.63/1.99 3.63/1.99 2: f1 -> f1 : K'=free_9, L'=free_14, M'=free_16, N'=free_13, Q_1'=free_10, R'=free_15, S'=free_12, [ 0>=1+J && free_11>=1 && free_8>=2 ], cost: 1 3.63/1.99 3.63/1.99 3: f1 -> f1 : K'=free_17, N'=free_22, O'=free_24, P'=free_21, T'=free_18, U'=free_23, V'=free_20, [ 0>=2+free_19 && J>=1 ], cost: 1 3.63/1.99 3.63/1.99 4: f1 -> f1 : K'=free_26, N'=free_32, Q_1'=free_34, R'=free_30, S'=free_27, T'=free_33, U'=free_29, V'=free_28, [ J>=1 && free_25>=0 && 1+free_31>=0 ], cost: 1 3.63/1.99 3.63/1.99 3.63/1.99 3.63/1.99 Simplified all rules, resulting in: 3.63/1.99 3.63/1.99 Start location: f2 3.63/1.99 3.63/1.99 0: f2 -> f1 : A'=free, B'=free, C'=free, D'=free, E'=free, F'=free, G'=free, H'=free, Q'=free, [], cost: 1 3.63/1.99 3.63/1.99 1: f1 -> f1 : K'=free_1, L'=free_5, M'=free_7, N'=free_4, O'=free_2, P'=free_6, [ 0>=1+J ], cost: 1 3.63/1.99 3.63/1.99 2: f1 -> f1 : K'=free_9, L'=free_14, M'=free_16, N'=free_13, Q_1'=free_10, R'=free_15, S'=free_12, [ 0>=1+J ], cost: 1 3.63/1.99 3.63/1.99 3: f1 -> f1 : K'=free_17, N'=free_22, O'=free_24, P'=free_21, T'=free_18, U'=free_23, V'=free_20, [ J>=1 ], cost: 1 3.63/1.99 3.63/1.99 4: f1 -> f1 : K'=free_26, N'=free_32, Q_1'=free_34, R'=free_30, S'=free_27, T'=free_33, U'=free_29, V'=free_28, [ J>=1 ], cost: 1 3.63/1.99 3.63/1.99 3.63/1.99 3.63/1.99 ### Simplification by acceleration and chaining ### 3.63/1.99 3.63/1.99 3.63/1.99 3.63/1.99 Accelerating simple loops of location 1. 3.63/1.99 3.63/1.99 Accelerating the following rules: 3.63/1.99 3.63/1.99 1: f1 -> f1 : K'=free_1, L'=free_5, M'=free_7, N'=free_4, O'=free_2, P'=free_6, [ 0>=1+J ], cost: 1 3.63/1.99 3.63/1.99 2: f1 -> f1 : K'=free_9, L'=free_14, M'=free_16, N'=free_13, Q_1'=free_10, R'=free_15, S'=free_12, [ 0>=1+J ], cost: 1 3.63/1.99 3.63/1.99 3: f1 -> f1 : K'=free_17, N'=free_22, O'=free_24, P'=free_21, T'=free_18, U'=free_23, V'=free_20, [ J>=1 ], cost: 1 3.63/1.99 3.63/1.99 4: f1 -> f1 : K'=free_26, N'=free_32, Q_1'=free_34, R'=free_30, S'=free_27, T'=free_33, U'=free_29, V'=free_28, [ J>=1 ], cost: 1 3.63/1.99 3.63/1.99 3.63/1.99 3.63/1.99 Accelerated rule 1 with NONTERM, yielding the new rule 8. 3.63/1.99 3.63/1.99 Accelerated rule 2 with NONTERM, yielding the new rule 9. 3.63/1.99 3.63/1.99 Accelerated rule 3 with NONTERM, yielding the new rule 10. 3.63/1.99 3.63/1.99 Accelerated rule 4 with NONTERM, yielding the new rule 11. 3.63/1.99 3.63/1.99 Removing the simple loops: 1 2 3 4. 3.63/1.99 3.63/1.99 Also removing duplicate rules:. 3.63/1.99 3.63/1.99 3.63/1.99 3.63/1.99 Accelerated all simple loops using metering functions (where possible): 3.63/1.99 3.63/1.99 Start location: f2 3.63/1.99 3.63/1.99 0: f2 -> f1 : A'=free, B'=free, C'=free, D'=free, E'=free, F'=free, G'=free, H'=free, Q'=free, [], cost: 1 3.63/1.99 3.63/1.99 9: f1 -> [3] : [ 0>=1+J ], cost: INF 3.63/1.99 3.63/1.99 11: f1 -> [3] : [ J>=1 ], cost: INF 3.63/1.99 3.63/1.99 3.63/1.99 3.63/1.99 Chained accelerated rules (with incoming rules): 3.63/1.99 3.63/1.99 Start location: f2 3.63/1.99 3.63/1.99 0: f2 -> f1 : A'=free, B'=free, C'=free, D'=free, E'=free, F'=free, G'=free, H'=free, Q'=free, [], cost: 1 3.63/1.99 3.63/1.99 12: f2 -> [3] : A'=free, B'=free, C'=free, D'=free, E'=free, F'=free, G'=free, H'=free, Q'=free, [ 0>=1+J ], cost: INF 3.63/1.99 3.63/1.99 13: f2 -> [3] : A'=free, B'=free, C'=free, D'=free, E'=free, F'=free, G'=free, H'=free, Q'=free, [ J>=1 ], cost: INF 3.63/1.99 3.63/1.99 3.63/1.99 3.63/1.99 Removed unreachable locations (and leaf rules with constant cost): 3.63/1.99 3.63/1.99 Start location: f2 3.63/1.99 3.63/1.99 12: f2 -> [3] : A'=free, B'=free, C'=free, D'=free, E'=free, F'=free, G'=free, H'=free, Q'=free, [ 0>=1+J ], cost: INF 3.63/1.99 3.63/1.99 13: f2 -> [3] : A'=free, B'=free, C'=free, D'=free, E'=free, F'=free, G'=free, H'=free, Q'=free, [ J>=1 ], cost: INF 3.63/1.99 3.63/1.99 3.63/1.99 3.63/1.99 ### Computing asymptotic complexity ### 3.63/1.99 3.63/1.99 3.63/1.99 3.63/1.99 Fully simplified ITS problem 3.63/1.99 3.63/1.99 Start location: f2 3.63/1.99 3.63/1.99 12: f2 -> [3] : A'=free, B'=free, C'=free, D'=free, E'=free, F'=free, G'=free, H'=free, Q'=free, [ 0>=1+J ], cost: INF 3.63/1.99 3.63/1.99 13: f2 -> [3] : A'=free, B'=free, C'=free, D'=free, E'=free, F'=free, G'=free, H'=free, Q'=free, [ J>=1 ], cost: INF 3.63/1.99 3.63/1.99 3.63/1.99 3.63/1.99 Computing asymptotic complexity for rule 12 3.63/1.99 3.63/1.99 Resulting cost INF has complexity: Nonterm 3.63/1.99 3.63/1.99 3.63/1.99 3.63/1.99 Found new complexity Nonterm. 3.63/1.99 3.63/1.99 3.63/1.99 3.63/1.99 Obtained the following overall complexity (w.r.t. the length of the input n): 3.63/1.99 3.63/1.99 Complexity: Nonterm 3.63/1.99 3.63/1.99 Cpx degree: Nonterm 3.63/1.99 3.63/1.99 Solved cost: INF 3.63/1.99 3.63/1.99 Rule cost: INF 3.63/1.99 3.63/1.99 Rule guard: [ 0>=1+J ] 3.63/1.99 3.63/1.99 3.63/1.99 3.63/1.99 NO 3.63/1.99 3.63/1.99 3.63/1.99 ---------------------------------------- 3.63/1.99 3.63/1.99 (2) 3.63/1.99 BOUNDS(INF, INF) 4.27/2.01 EOF