/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: 48fb2092695e11cc9f56e44b17a92a5f88ffb256 marcel 20180622 unpublished dirty The runtime complexity of the given CpxIntTrs could be proven to be BOUNDS(INF, INF). (0) CpxIntTrs (1) Loat Proof [FINISHED, 530 ms] (2) BOUNDS(INF, INF) ---------------------------------------- (0) Obligation: Complexity Int TRS consisting of the following rules: f0(A, B, C, D, E, F) -> Com_1(f12(G, G, G, 0, E, F)) :|: TRUE f12(A, B, C, D, E, F) -> Com_1(f12(A, B, C, D + 1, G, F)) :|: C >= D + 1 f27(A, B, C, D, E, F) -> Com_1(f27(A, B, C, D, E, G)) :|: 0 >= H + 1 f27(A, B, C, D, E, F) -> Com_1(f27(A, B, C, D, E, G)) :|: TRUE f42(A, B, C, D, E, F) -> Com_1(f42(A, B, C, D, E, F)) :|: G >= H + 1 f42(A, B, C, D, E, F) -> Com_1(f42(A, B, C, D, E, F)) :|: TRUE f55(A, B, C, D, E, F) -> Com_1(f55(A, B, C, D, E, F)) :|: G >= H + 1 f55(A, B, C, D, E, F) -> Com_1(f55(A, B, C, D, E, F)) :|: TRUE f55(A, B, C, D, E, F) -> Com_1(f66(A, B, C, D, E, F)) :|: TRUE f42(A, B, C, D, E, F) -> Com_1(f55(A, B, C, D, E, F)) :|: TRUE f27(A, B, C, D, E, F) -> Com_1(f42(A, B, C, D, E, F)) :|: TRUE f12(A, B, C, D, E, F) -> Com_1(f27(A, B, C, D, E, F)) :|: D >= C The start-symbols are:[f0_6] ---------------------------------------- (1) Loat Proof (FINISHED) ### Pre-processing the ITS problem ### Initial linear ITS problem Start location: f0 0: f0 -> f12 : A'=free, B'=free, C'=free, D'=0, [], cost: 1 1: f12 -> f12 : D'=1+D, E'=free_1, [ C>=1+D ], cost: 1 11: f12 -> f27 : [ D>=C ], cost: 1 2: f27 -> f27 : F'=free_2, [ 0>=1+free_3 ], cost: 1 3: f27 -> f27 : F'=free_4, [], cost: 1 10: f27 -> f42 : [], cost: 1 4: f42 -> f42 : [ free_5>=1+free_6 ], cost: 1 5: f42 -> f42 : [], cost: 1 9: f42 -> f55 : [], cost: 1 6: f55 -> f55 : [ free_7>=1+free_8 ], cost: 1 7: f55 -> f55 : [], cost: 1 8: f55 -> f66 : [], cost: 1 Removed unreachable and leaf rules: Start location: f0 0: f0 -> f12 : A'=free, B'=free, C'=free, D'=0, [], cost: 1 1: f12 -> f12 : D'=1+D, E'=free_1, [ C>=1+D ], cost: 1 11: f12 -> f27 : [ D>=C ], cost: 1 2: f27 -> f27 : F'=free_2, [ 0>=1+free_3 ], cost: 1 3: f27 -> f27 : F'=free_4, [], cost: 1 10: f27 -> f42 : [], cost: 1 4: f42 -> f42 : [ free_5>=1+free_6 ], cost: 1 5: f42 -> f42 : [], cost: 1 9: f42 -> f55 : [], cost: 1 6: f55 -> f55 : [ free_7>=1+free_8 ], cost: 1 7: f55 -> f55 : [], cost: 1 Simplified all rules, resulting in: Start location: f0 0: f0 -> f12 : A'=free, B'=free, C'=free, D'=0, [], cost: 1 1: f12 -> f12 : D'=1+D, E'=free_1, [ C>=1+D ], cost: 1 11: f12 -> f27 : [ D>=C ], cost: 1 2: f27 -> f27 : F'=free_2, [], cost: 1 3: f27 -> f27 : F'=free_4, [], cost: 1 10: f27 -> f42 : [], cost: 1 5: f42 -> f42 : [], cost: 1 9: f42 -> f55 : [], cost: 1 7: f55 -> f55 : [], cost: 1 ### Simplification by acceleration and chaining ### Accelerating simple loops of location 1. Accelerating the following rules: 1: f12 -> f12 : D'=1+D, E'=free_1, [ C>=1+D ], cost: 1 Accelerated rule 1 with metering function C-D, yielding the new rule 12. Removing the simple loops: 1. Accelerating simple loops of location 2. Accelerating the following rules: 2: f27 -> f27 : F'=free_2, [], cost: 1 3: f27 -> f27 : F'=free_4, [], cost: 1 Accelerated rule 2 with NONTERM, yielding the new rule 13. Accelerated rule 3 with NONTERM, yielding the new rule 14. Removing the simple loops: 2 3. Also removing duplicate rules:. Accelerating simple loops of location 3. Accelerating the following rules: 5: f42 -> f42 : [], cost: 1 Accelerated rule 5 with NONTERM, yielding the new rule 15. Removing the simple loops: 5. Also removing duplicate rules:. Accelerating simple loops of location 4. Accelerating the following rules: 7: f55 -> f55 : [], cost: 1 Accelerated rule 7 with NONTERM, yielding the new rule 16. Removing the simple loops: 7. Also removing duplicate rules:. Accelerated all simple loops using metering functions (where possible): Start location: f0 0: f0 -> f12 : A'=free, B'=free, C'=free, D'=0, [], cost: 1 11: f12 -> f27 : [ D>=C ], cost: 1 12: f12 -> f12 : D'=C, E'=free_1, [ C>=1+D ], cost: C-D 10: f27 -> f42 : [], cost: 1 14: f27 -> [7] : [], cost: INF 9: f42 -> f55 : [], cost: 1 15: f42 -> [8] : [], cost: INF 16: f55 -> [9] : [], cost: INF Chained accelerated rules (with incoming rules): Start location: f0 0: f0 -> f12 : A'=free, B'=free, C'=free, D'=0, [], cost: 1 17: f0 -> f12 : A'=free, B'=free, C'=free, D'=free, E'=free_1, [ free>=1 ], cost: 1+free 11: f12 -> f27 : [ D>=C ], cost: 1 18: f12 -> [7] : [ D>=C ], cost: INF 10: f27 -> f42 : [], cost: 1 19: f27 -> [8] : [], cost: INF 9: f42 -> f55 : [], cost: 1 20: f42 -> [9] : [], cost: INF Removed unreachable locations (and leaf rules with constant cost): Start location: f0 0: f0 -> f12 : A'=free, B'=free, C'=free, D'=0, [], cost: 1 17: f0 -> f12 : A'=free, B'=free, C'=free, D'=free, E'=free_1, [ free>=1 ], cost: 1+free 11: f12 -> f27 : [ D>=C ], cost: 1 18: f12 -> [7] : [ D>=C ], cost: INF 10: f27 -> f42 : [], cost: 1 19: f27 -> [8] : [], cost: INF 20: f42 -> [9] : [], cost: INF Eliminated locations (on linear paths): Start location: f0 0: f0 -> f12 : A'=free, B'=free, C'=free, D'=0, [], cost: 1 17: f0 -> f12 : A'=free, B'=free, C'=free, D'=free, E'=free_1, [ free>=1 ], cost: 1+free 11: f12 -> f27 : [ D>=C ], cost: 1 18: f12 -> [7] : [ D>=C ], cost: INF 19: f27 -> [8] : [], cost: INF 21: f27 -> [9] : [], cost: INF Eliminated locations (on tree-shaped paths): Start location: f0 22: f0 -> f27 : A'=free, B'=free, C'=free, D'=0, [ 0>=free ], cost: 2 23: f0 -> [7] : A'=free, B'=free, C'=free, D'=0, [ 0>=free ], cost: INF 24: f0 -> f27 : A'=free, B'=free, C'=free, D'=free, E'=free_1, [ free>=1 ], cost: 2+free 25: f0 -> [7] : A'=free, B'=free, C'=free, D'=free, E'=free_1, [ free>=1 ], cost: INF 19: f27 -> [8] : [], cost: INF 21: f27 -> [9] : [], cost: INF Eliminated locations (on tree-shaped paths): Start location: f0 23: f0 -> [7] : A'=free, B'=free, C'=free, D'=0, [ 0>=free ], cost: INF 25: f0 -> [7] : A'=free, B'=free, C'=free, D'=free, E'=free_1, [ free>=1 ], cost: INF 26: f0 -> [8] : A'=free, B'=free, C'=free, D'=0, [ 0>=free ], cost: INF 27: f0 -> [9] : A'=free, B'=free, C'=free, D'=0, [ 0>=free ], cost: INF 28: f0 -> [8] : A'=free, B'=free, C'=free, D'=free, E'=free_1, [ free>=1 ], cost: INF 29: f0 -> [9] : A'=free, B'=free, C'=free, D'=free, E'=free_1, [ free>=1 ], cost: INF ### Computing asymptotic complexity ### Fully simplified ITS problem Start location: f0 27: f0 -> [9] : A'=free, B'=free, C'=free, D'=0, [ 0>=free ], cost: INF 29: f0 -> [9] : A'=free, B'=free, C'=free, D'=free, E'=free_1, [ free>=1 ], cost: INF Computing asymptotic complexity for rule 27 Resulting cost INF 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: INF Rule cost: INF Rule guard: [ 0>=free ] NO ---------------------------------------- (2) BOUNDS(INF, INF)