/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, 444 ms] (2) BOUNDS(INF, INF) ---------------------------------------- (0) Obligation: Complexity Int TRS consisting of the following rules: f0(A, B, C, D, E) -> Com_1(f9(F, F, F, 0, E)) :|: TRUE f9(A, B, C, D, E) -> Com_1(f9(A, B, C, D + 1, F)) :|: C >= D + 1 f24(A, B, C, D, E) -> Com_1(f24(A, B, C, D, E)) :|: 0 >= F + 1 f24(A, B, C, D, E) -> Com_1(f24(A, B, C, D, E)) :|: TRUE f37(A, B, C, D, E) -> Com_1(f37(A, B, C, D, E)) :|: F >= G + 1 f37(A, B, C, D, E) -> Com_1(f37(A, B, C, D, E)) :|: TRUE f37(A, B, C, D, E) -> Com_1(f48(A, B, C, D, E)) :|: TRUE f24(A, B, C, D, E) -> Com_1(f37(A, B, C, D, E)) :|: TRUE f9(A, B, C, D, E) -> Com_1(f24(A, B, C, D, E)) :|: D >= C The start-symbols are:[f0_5] ---------------------------------------- (1) Loat Proof (FINISHED) ### Pre-processing the ITS problem ### Initial linear ITS problem Start location: f0 0: f0 -> f9 : A'=free, B'=free, C'=free, D'=0, [], cost: 1 1: f9 -> f9 : D'=1+D, E'=free_1, [ C>=1+D ], cost: 1 8: f9 -> f24 : [ D>=C ], cost: 1 2: f24 -> f24 : [ 0>=1+free_2 ], cost: 1 3: f24 -> f24 : [], cost: 1 7: f24 -> f37 : [], cost: 1 4: f37 -> f37 : [ free_3>=1+free_4 ], cost: 1 5: f37 -> f37 : [], cost: 1 6: f37 -> f48 : [], cost: 1 Checking for constant complexity: The following rule is satisfiable with cost >= 1, yielding constant complexity: 0: f0 -> f9 : A'=free, B'=free, C'=free, D'=0, [], cost: 1 Removed unreachable and leaf rules: Start location: f0 0: f0 -> f9 : A'=free, B'=free, C'=free, D'=0, [], cost: 1 1: f9 -> f9 : D'=1+D, E'=free_1, [ C>=1+D ], cost: 1 8: f9 -> f24 : [ D>=C ], cost: 1 2: f24 -> f24 : [ 0>=1+free_2 ], cost: 1 3: f24 -> f24 : [], cost: 1 7: f24 -> f37 : [], cost: 1 4: f37 -> f37 : [ free_3>=1+free_4 ], cost: 1 5: f37 -> f37 : [], cost: 1 Simplified all rules, resulting in: Start location: f0 0: f0 -> f9 : A'=free, B'=free, C'=free, D'=0, [], cost: 1 1: f9 -> f9 : D'=1+D, E'=free_1, [ C>=1+D ], cost: 1 8: f9 -> f24 : [ D>=C ], cost: 1 3: f24 -> f24 : [], cost: 1 7: f24 -> f37 : [], cost: 1 5: f37 -> f37 : [], cost: 1 ### Simplification by acceleration and chaining ### Accelerating simple loops of location 1. Accelerating the following rules: 1: f9 -> f9 : D'=1+D, E'=free_1, [ C>=1+D ], cost: 1 Accelerated rule 1 with metering function C-D, yielding the new rule 9. Removing the simple loops: 1. Accelerating simple loops of location 2. Accelerating the following rules: 3: f24 -> f24 : [], cost: 1 Accelerated rule 3 with NONTERM, yielding the new rule 10. Removing the simple loops: 3. Accelerating simple loops of location 3. Accelerating the following rules: 5: f37 -> f37 : [], cost: 1 Accelerated rule 5 with NONTERM, yielding the new rule 11. Removing the simple loops: 5. Accelerated all simple loops using metering functions (where possible): Start location: f0 0: f0 -> f9 : A'=free, B'=free, C'=free, D'=0, [], cost: 1 8: f9 -> f24 : [ D>=C ], cost: 1 9: f9 -> f9 : D'=C, E'=free_1, [ C>=1+D ], cost: C-D 7: f24 -> f37 : [], cost: 1 10: f24 -> [6] : [], cost: NONTERM 11: f37 -> [7] : [], cost: NONTERM Chained accelerated rules (with incoming rules): Start location: f0 0: f0 -> f9 : A'=free, B'=free, C'=free, D'=0, [], cost: 1 12: f0 -> f9 : A'=free, B'=free, C'=free, D'=free, E'=free_1, [ free>=1 ], cost: 1+free 8: f9 -> f24 : [ D>=C ], cost: 1 13: f9 -> [6] : [ D>=C ], cost: NONTERM 7: f24 -> f37 : [], cost: 1 14: f24 -> [7] : [], cost: NONTERM Removed unreachable locations (and leaf rules with constant cost): Start location: f0 0: f0 -> f9 : A'=free, B'=free, C'=free, D'=0, [], cost: 1 12: f0 -> f9 : A'=free, B'=free, C'=free, D'=free, E'=free_1, [ free>=1 ], cost: 1+free 8: f9 -> f24 : [ D>=C ], cost: 1 13: f9 -> [6] : [ D>=C ], cost: NONTERM 14: f24 -> [7] : [], cost: NONTERM Eliminated locations (on linear paths): Start location: f0 0: f0 -> f9 : A'=free, B'=free, C'=free, D'=0, [], cost: 1 12: f0 -> f9 : A'=free, B'=free, C'=free, D'=free, E'=free_1, [ free>=1 ], cost: 1+free 13: f9 -> [6] : [ D>=C ], cost: NONTERM 15: f9 -> [7] : [ D>=C ], cost: NONTERM Eliminated locations (on tree-shaped paths): Start location: f0 16: f0 -> [6] : A'=free, B'=free, C'=free, D'=0, [ 0>=free ], cost: NONTERM 17: f0 -> [7] : A'=free, B'=free, C'=free, D'=0, [ 0>=free ], cost: NONTERM 18: f0 -> [6] : A'=free, B'=free, C'=free, D'=free, E'=free_1, [ free>=1 ], cost: NONTERM 19: f0 -> [7] : A'=free, B'=free, C'=free, D'=free, E'=free_1, [ free>=1 ], cost: NONTERM ### Computing asymptotic complexity ### Fully simplified ITS problem Start location: f0 17: f0 -> [7] : A'=free, B'=free, C'=free, D'=0, [ 0>=free ], cost: NONTERM 19: f0 -> [7] : A'=free, B'=free, C'=free, D'=free, E'=free_1, [ free>=1 ], cost: NONTERM Computing asymptotic complexity for rule 17 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>=free ] NO ---------------------------------------- (2) BOUNDS(INF, INF)