/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, 220 ms] (2) BOUNDS(INF, INF) ---------------------------------------- (0) Obligation: Complexity Int TRS consisting of the following rules: f300(A, B, C, D, E, F, G, H, I, J, K, L, M, N, O, P, Q, R) -> Com_1(f1(S, T, U, V, W, F, G, H, I, J, K, L, M, N, O, P, Q, R)) :|: TRUE f1(A, B, C, D, E, F, G, H, I, J, K, L, M, N, O, P, Q, R) -> Com_1(f1(A, B, C, D, E, F, G, 256, S, T, U, V, W, Y, O, P, Q, R)) :|: G >= 1 + F && X >= 1 && H >= 256 && H <= 256 f1(A, B, C, D, E, F, G, H, I, J, K, L, M, N, O, P, Q, R) -> Com_1(f1(A, B, C, D, E, F, G, H, S, T, U, V, W, N, O, P, Q, R)) :|: G >= 1 + F && 0 >= H f1(A, B, C, D, E, F, G, H, I, J, K, L, M, N, O, P, Q, R) -> Com_1(f3(A, B, C, D, E, F, G, H, S, T, K, L, M, N, 0, 0, 0, R)) :|: F >= G f1(A, B, C, D, E, F, G, H, I, J, K, L, M, N, O, P, Q, R) -> Com_1(f2(A, B, C, D, E, F, G, H, S, T, U, V, W, Y, H, H, H, X)) :|: H >= 1 && G >= 1 + F && H >= 257 f1(A, B, C, D, E, F, G, H, I, J, K, L, M, N, O, P, Q, R) -> Com_1(f2(A, B, C, D, E, F, G, H, S, T, U, V, W, Y, H, H, H, X)) :|: H >= 1 && G >= 1 + F && 255 >= H The start-symbols are:[f300_18] ---------------------------------------- (1) Loat Proof (FINISHED) ### Pre-processing the ITS problem ### Initial linear ITS problem Start location: f300 0: f300 -> f1 : A'=free, B'=free_2, C'=free_3, D'=free_4, E'=free_1, [], cost: 1 1: f1 -> f1 : H'=256, Q'=free_5, J'=free_7, K'=free_9, L'=free_11, M'=free_6, N'=free_10, [ F>=1+G && free_8>=1 && H==256 ], cost: 1 2: f1 -> f1 : Q'=free_12, J'=free_14, K'=free_15, L'=free_16, M'=free_13, [ F>=1+G && 0>=H ], cost: 1 3: f1 -> f3 : Q'=free_17, J'=free_18, O'=0, P'=0, Q_1'=0, [ G>=F ], cost: 1 4: f1 -> f2 : Q'=free_19, J'=free_21, K'=free_23, L'=free_25, M'=free_20, N'=free_24, O'=H, P'=H, Q_1'=H, R'=free_22, [ H>=1 && F>=1+G && H>=257 ], cost: 1 5: f1 -> f2 : Q'=free_26, J'=free_28, K'=free_30, L'=free_32, M'=free_27, N'=free_31, O'=H, P'=H, Q_1'=H, R'=free_29, [ H>=1 && F>=1+G && 255>=H ], cost: 1 Checking for constant complexity: The following rule is satisfiable with cost >= 1, yielding constant complexity: 0: f300 -> f1 : A'=free, B'=free_2, C'=free_3, D'=free_4, E'=free_1, [], cost: 1 Removed unreachable and leaf rules: Start location: f300 0: f300 -> f1 : A'=free, B'=free_2, C'=free_3, D'=free_4, E'=free_1, [], cost: 1 1: f1 -> f1 : H'=256, Q'=free_5, J'=free_7, K'=free_9, L'=free_11, M'=free_6, N'=free_10, [ F>=1+G && free_8>=1 && H==256 ], cost: 1 2: f1 -> f1 : Q'=free_12, J'=free_14, K'=free_15, L'=free_16, M'=free_13, [ F>=1+G && 0>=H ], cost: 1 Simplified all rules, resulting in: Start location: f300 0: f300 -> f1 : A'=free, B'=free_2, C'=free_3, D'=free_4, E'=free_1, [], cost: 1 1: f1 -> f1 : H'=256, Q'=free_5, J'=free_7, K'=free_9, L'=free_11, M'=free_6, N'=free_10, [ F>=1+G && H==256 ], cost: 1 2: f1 -> f1 : Q'=free_12, J'=free_14, K'=free_15, L'=free_16, M'=free_13, [ F>=1+G && 0>=H ], cost: 1 ### Simplification by acceleration and chaining ### Accelerating simple loops of location 1. Accelerating the following rules: 1: f1 -> f1 : H'=256, Q'=free_5, J'=free_7, K'=free_9, L'=free_11, M'=free_6, N'=free_10, [ F>=1+G && H==256 ], cost: 1 2: f1 -> f1 : Q'=free_12, J'=free_14, K'=free_15, L'=free_16, M'=free_13, [ F>=1+G && 0>=H ], cost: 1 Accelerated rule 1 with NONTERM, yielding the new rule 6. Accelerated rule 2 with NONTERM, yielding the new rule 7. Removing the simple loops: 1 2. Accelerated all simple loops using metering functions (where possible): Start location: f300 0: f300 -> f1 : A'=free, B'=free_2, C'=free_3, D'=free_4, E'=free_1, [], cost: 1 6: f1 -> [4] : [ F>=1+G && H==256 ], cost: NONTERM 7: f1 -> [4] : [ F>=1+G && 0>=H ], cost: NONTERM Chained accelerated rules (with incoming rules): Start location: f300 0: f300 -> f1 : A'=free, B'=free_2, C'=free_3, D'=free_4, E'=free_1, [], cost: 1 8: f300 -> [4] : A'=free, B'=free_2, C'=free_3, D'=free_4, E'=free_1, [ F>=1+G && H==256 ], cost: NONTERM 9: f300 -> [4] : A'=free, B'=free_2, C'=free_3, D'=free_4, E'=free_1, [ F>=1+G && 0>=H ], cost: NONTERM Removed unreachable locations (and leaf rules with constant cost): Start location: f300 8: f300 -> [4] : A'=free, B'=free_2, C'=free_3, D'=free_4, E'=free_1, [ F>=1+G && H==256 ], cost: NONTERM 9: f300 -> [4] : A'=free, B'=free_2, C'=free_3, D'=free_4, E'=free_1, [ F>=1+G && 0>=H ], cost: NONTERM ### Computing asymptotic complexity ### Fully simplified ITS problem Start location: f300 8: f300 -> [4] : A'=free, B'=free_2, C'=free_3, D'=free_4, E'=free_1, [ F>=1+G && H==256 ], cost: NONTERM 9: f300 -> [4] : A'=free, B'=free_2, C'=free_3, D'=free_4, E'=free_1, [ F>=1+G && 0>=H ], cost: NONTERM Computing asymptotic complexity for rule 8 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: [ F>=1+G && H==256 ] NO ---------------------------------------- (2) BOUNDS(INF, INF)