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