/export/starexec/sandbox2/solver/bin/starexec_run_complexity /export/starexec/sandbox2/benchmark/theBenchmark.koat /export/starexec/sandbox2/output/output_files -------------------------------------------------------------------------------- WORST_CASE(NON_POLY, ?) proof of /export/starexec/sandbox2/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, 316 ms] (2) BOUNDS(INF, INF) ---------------------------------------- (0) Obligation: Complexity Int TRS consisting of the following rules: f2(A, B, C, D, E, F) -> Com_1(f2(1 + A, G, G, D, E, F)) :|: G >= 1 && A >= 1 f2(A, B, C, D, E, F) -> Com_1(f2(1 + A, G, G, D, E, F)) :|: 0 >= G + 1 && A >= 1 f2(A, B, C, D, E, F) -> Com_1(f0(A, 0, 0, G, E, F)) :|: TRUE f3(A, B, C, D, E, F) -> Com_1(f2(1 + A, G, G, D, E, F)) :|: G >= 1 && A >= 1 f3(A, B, C, D, E, F) -> Com_1(f2(1 + A, G, G, D, E, F)) :|: 0 >= G + 1 && A >= 1 f3(A, B, C, D, E, F) -> Com_1(f0(A, 0, 0, G, E, F)) :|: TRUE f4(A, B, C, D, E, F) -> Com_1(f2(1 + H, G, G, D, H, H)) :|: G >= 1 && H >= 1 f4(A, B, C, D, E, F) -> Com_1(f2(1 + H, G, G, D, H, H)) :|: 0 >= G + 1 && H >= 1 f4(A, B, C, D, E, F) -> Com_1(f0(G, 0, 0, H, G, G)) :|: TRUE The start-symbols are:[f4_6] ---------------------------------------- (1) Loat Proof (FINISHED) ### Pre-processing the ITS problem ### Initial linear ITS problem Start location: f4 0: f2 -> f2 : A'=1+A, B'=free, C'=free, [ free>=1 && A>=1 ], cost: 1 1: f2 -> f2 : A'=1+A, B'=free_1, C'=free_1, [ 0>=1+free_1 && A>=1 ], cost: 1 2: f2 -> f0 : B'=0, C'=0, D'=free_2, [], cost: 1 3: f3 -> f2 : A'=1+A, B'=free_3, C'=free_3, [ free_3>=1 && A>=1 ], cost: 1 4: f3 -> f2 : A'=1+A, B'=free_4, C'=free_4, [ 0>=1+free_4 && A>=1 ], cost: 1 5: f3 -> f0 : B'=0, C'=0, D'=free_5, [], cost: 1 6: f4 -> f2 : A'=1+free_6, B'=free_7, C'=free_7, E'=free_6, F'=free_6, [ free_7>=1 && free_6>=1 ], cost: 1 7: f4 -> f2 : A'=1+free_8, B'=free_9, C'=free_9, E'=free_8, F'=free_8, [ 0>=1+free_9 && free_8>=1 ], cost: 1 8: f4 -> f0 : A'=free_10, B'=0, C'=0, D'=free_11, E'=free_10, F'=free_10, [], cost: 1 Checking for constant complexity: The following rule is satisfiable with cost >= 1, yielding constant complexity: 6: f4 -> f2 : A'=1+free_6, B'=free_7, C'=free_7, E'=free_6, F'=free_6, [ free_7>=1 && free_6>=1 ], cost: 1 Removed unreachable and leaf rules: Start location: f4 0: f2 -> f2 : A'=1+A, B'=free, C'=free, [ free>=1 && A>=1 ], cost: 1 1: f2 -> f2 : A'=1+A, B'=free_1, C'=free_1, [ 0>=1+free_1 && A>=1 ], cost: 1 6: f4 -> f2 : A'=1+free_6, B'=free_7, C'=free_7, E'=free_6, F'=free_6, [ free_7>=1 && free_6>=1 ], cost: 1 7: f4 -> f2 : A'=1+free_8, B'=free_9, C'=free_9, E'=free_8, F'=free_8, [ 0>=1+free_9 && free_8>=1 ], cost: 1 Removed unreachable and leaf rules: Start location: f4 0: f2 -> f2 : A'=1+A, B'=free, C'=free, [ free>=1 && A>=1 ], cost: 1 1: f2 -> f2 : A'=1+A, B'=free_1, C'=free_1, [ 0>=1+free_1 && A>=1 ], cost: 1 6: f4 -> f2 : A'=1+free_6, B'=free_7, C'=free_7, E'=free_6, F'=free_6, [ free_7>=1 && free_6>=1 ], cost: 1 7: f4 -> f2 : A'=1+free_8, B'=free_9, C'=free_9, E'=free_8, F'=free_8, [ 0>=1+free_9 && free_8>=1 ], cost: 1 ### Simplification by acceleration and chaining ### Accelerating simple loops of location 0. Accelerating the following rules: 0: f2 -> f2 : A'=1+A, B'=free, C'=free, [ free>=1 && A>=1 ], cost: 1 1: f2 -> f2 : A'=1+A, B'=free_1, C'=free_1, [ 0>=1+free_1 && A>=1 ], cost: 1 Accelerated rule 0 with NONTERM, yielding the new rule 9. Accelerated rule 1 with NONTERM, yielding the new rule 10. Removing the simple loops: 0 1. Accelerated all simple loops using metering functions (where possible): Start location: f4 9: f2 -> [4] : [ free>=1 && A>=1 ], cost: NONTERM 10: f2 -> [4] : [ 0>=1+free_1 && A>=1 ], cost: NONTERM 6: f4 -> f2 : A'=1+free_6, B'=free_7, C'=free_7, E'=free_6, F'=free_6, [ free_7>=1 && free_6>=1 ], cost: 1 7: f4 -> f2 : A'=1+free_8, B'=free_9, C'=free_9, E'=free_8, F'=free_8, [ 0>=1+free_9 && free_8>=1 ], cost: 1 Chained accelerated rules (with incoming rules): Start location: f4 6: f4 -> f2 : A'=1+free_6, B'=free_7, C'=free_7, E'=free_6, F'=free_6, [ free_7>=1 && free_6>=1 ], cost: 1 7: f4 -> f2 : A'=1+free_8, B'=free_9, C'=free_9, E'=free_8, F'=free_8, [ 0>=1+free_9 && free_8>=1 ], cost: 1 11: f4 -> [4] : A'=1+free_6, B'=free_7, C'=free_7, E'=free_6, F'=free_6, [ free_7>=1 && free_6>=1 ], cost: NONTERM 12: f4 -> [4] : A'=1+free_8, B'=free_9, C'=free_9, E'=free_8, F'=free_8, [ 0>=1+free_9 && free_8>=1 ], cost: NONTERM 13: f4 -> [4] : A'=1+free_6, B'=free_7, C'=free_7, E'=free_6, F'=free_6, [ free_7>=1 && free_6>=1 ], cost: NONTERM 14: f4 -> [4] : A'=1+free_8, B'=free_9, C'=free_9, E'=free_8, F'=free_8, [ 0>=1+free_9 && free_8>=1 ], cost: NONTERM Removed unreachable locations (and leaf rules with constant cost): Start location: f4 11: f4 -> [4] : A'=1+free_6, B'=free_7, C'=free_7, E'=free_6, F'=free_6, [ free_7>=1 && free_6>=1 ], cost: NONTERM 12: f4 -> [4] : A'=1+free_8, B'=free_9, C'=free_9, E'=free_8, F'=free_8, [ 0>=1+free_9 && free_8>=1 ], cost: NONTERM 13: f4 -> [4] : A'=1+free_6, B'=free_7, C'=free_7, E'=free_6, F'=free_6, [ free_7>=1 && free_6>=1 ], cost: NONTERM 14: f4 -> [4] : A'=1+free_8, B'=free_9, C'=free_9, E'=free_8, F'=free_8, [ 0>=1+free_9 && free_8>=1 ], cost: NONTERM ### Computing asymptotic complexity ### Fully simplified ITS problem Start location: f4 13: f4 -> [4] : A'=1+free_6, B'=free_7, C'=free_7, E'=free_6, F'=free_6, [ free_7>=1 && free_6>=1 ], cost: NONTERM 14: f4 -> [4] : A'=1+free_8, B'=free_9, C'=free_9, E'=free_8, F'=free_8, [ 0>=1+free_9 && free_8>=1 ], cost: NONTERM Computing asymptotic complexity for rule 13 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: [ free_7>=1 && free_6>=1 ] NO ---------------------------------------- (2) BOUNDS(INF, INF)