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