5.12/2.28 WORST_CASE(NON_POLY, ?) 5.12/2.29 proof of /export/starexec/sandbox/benchmark/theBenchmark.koat 5.12/2.29 # AProVE Commit ID: 48fb2092695e11cc9f56e44b17a92a5f88ffb256 marcel 20180622 unpublished dirty 5.12/2.29 5.12/2.29 5.12/2.29 The runtime complexity of the given CpxIntTrs could be proven to be BOUNDS(INF, INF). 5.12/2.29 5.12/2.29 (0) CpxIntTrs 5.12/2.29 (1) Loat Proof [FINISHED, 598 ms] 5.12/2.29 (2) BOUNDS(INF, INF) 5.12/2.29 5.12/2.29 5.12/2.29 ---------------------------------------- 5.12/2.29 5.12/2.29 (0) 5.12/2.29 Obligation: 5.12/2.29 Complexity Int TRS consisting of the following rules: 5.12/2.29 f9(A, B, C, D) -> Com_1(f14(A, 0, E, D)) :|: 0 >= A 5.12/2.29 f14(A, B, C, D) -> Com_1(f14(A, B, C - 1, D)) :|: C >= 1 5.12/2.29 f22(A, B, C, D) -> Com_1(f22(A, B, C, D)) :|: TRUE 5.12/2.29 f24(A, B, C, D) -> Com_1(f27(A, B, C, D)) :|: TRUE 5.12/2.29 f14(A, B, C, D) -> Com_1(f9(E, B, C, 0)) :|: 0 >= C 5.12/2.29 f9(A, B, C, D) -> Com_1(f22(A, B, C, D)) :|: A >= 1 5.12/2.29 f0(A, B, C, D) -> Com_1(f9(E, 0, C, 0)) :|: TRUE 5.12/2.29 5.12/2.29 The start-symbols are:[f0_4] 5.12/2.29 5.12/2.29 5.12/2.29 ---------------------------------------- 5.12/2.29 5.12/2.29 (1) Loat Proof (FINISHED) 5.12/2.29 5.12/2.29 5.12/2.29 ### Pre-processing the ITS problem ### 5.12/2.29 5.12/2.29 5.12/2.29 5.12/2.29 Initial linear ITS problem 5.12/2.29 5.12/2.29 Start location: f0 5.12/2.29 5.12/2.29 0: f9 -> f14 : B'=0, C'=free, [ 0>=A ], cost: 1 5.12/2.29 5.12/2.29 5: f9 -> f22 : [ A>=1 ], cost: 1 5.12/2.29 5.12/2.29 1: f14 -> f14 : C'=-1+C, [ C>=1 ], cost: 1 5.12/2.29 5.12/2.29 4: f14 -> f9 : A'=free_1, D'=0, [ 0>=C ], cost: 1 5.12/2.29 5.12/2.29 2: f22 -> f22 : [], cost: 1 5.12/2.29 5.12/2.29 3: f24 -> f27 : [], cost: 1 5.12/2.29 5.12/2.29 6: f0 -> f9 : A'=free_2, B'=0, D'=0, [], cost: 1 5.12/2.29 5.12/2.29 5.12/2.29 5.12/2.29 Removed unreachable and leaf rules: 5.12/2.29 5.12/2.29 Start location: f0 5.12/2.29 5.12/2.29 0: f9 -> f14 : B'=0, C'=free, [ 0>=A ], cost: 1 5.12/2.29 5.12/2.29 5: f9 -> f22 : [ A>=1 ], cost: 1 5.12/2.29 5.12/2.29 1: f14 -> f14 : C'=-1+C, [ C>=1 ], cost: 1 5.12/2.29 5.12/2.29 4: f14 -> f9 : A'=free_1, D'=0, [ 0>=C ], cost: 1 5.12/2.29 5.12/2.29 2: f22 -> f22 : [], cost: 1 5.12/2.29 5.12/2.29 6: f0 -> f9 : A'=free_2, B'=0, D'=0, [], cost: 1 5.12/2.29 5.12/2.29 5.12/2.29 5.12/2.29 ### Simplification by acceleration and chaining ### 5.12/2.29 5.12/2.29 5.12/2.29 5.12/2.29 Accelerating simple loops of location 1. 5.12/2.29 5.12/2.29 Accelerating the following rules: 5.12/2.29 5.12/2.29 1: f14 -> f14 : C'=-1+C, [ C>=1 ], cost: 1 5.12/2.29 5.12/2.29 5.12/2.29 5.12/2.29 Accelerated rule 1 with metering function C, yielding the new rule 7. 5.12/2.29 5.12/2.29 Removing the simple loops: 1. 5.12/2.29 5.12/2.29 5.12/2.29 5.12/2.29 Accelerating simple loops of location 2. 5.12/2.29 5.12/2.29 Accelerating the following rules: 5.12/2.29 5.12/2.29 2: f22 -> f22 : [], cost: 1 5.12/2.29 5.12/2.29 5.12/2.29 5.12/2.29 Accelerated rule 2 with NONTERM, yielding the new rule 8. 5.12/2.29 5.12/2.29 Removing the simple loops: 2. 5.12/2.29 5.12/2.29 5.12/2.29 5.12/2.29 Accelerated all simple loops using metering functions (where possible): 5.12/2.29 5.12/2.29 Start location: f0 5.12/2.29 5.12/2.29 0: f9 -> f14 : B'=0, C'=free, [ 0>=A ], cost: 1 5.12/2.29 5.12/2.29 5: f9 -> f22 : [ A>=1 ], cost: 1 5.12/2.29 5.12/2.29 4: f14 -> f9 : A'=free_1, D'=0, [ 0>=C ], cost: 1 5.12/2.29 5.12/2.29 7: f14 -> f14 : C'=0, [ C>=1 ], cost: C 5.12/2.29 5.12/2.29 8: f22 -> [7] : [], cost: INF 5.12/2.29 5.12/2.29 6: f0 -> f9 : A'=free_2, B'=0, D'=0, [], cost: 1 5.12/2.29 5.12/2.29 5.12/2.29 5.12/2.29 Chained accelerated rules (with incoming rules): 5.12/2.29 5.12/2.29 Start location: f0 5.12/2.29 5.12/2.29 0: f9 -> f14 : B'=0, C'=free, [ 0>=A ], cost: 1 5.12/2.29 5.12/2.29 5: f9 -> f22 : [ A>=1 ], cost: 1 5.12/2.29 5.12/2.29 9: f9 -> f14 : B'=0, C'=0, [ 0>=A && free>=1 ], cost: 1+free 5.12/2.29 5.12/2.29 10: f9 -> [7] : [ A>=1 ], cost: INF 5.12/2.29 5.12/2.29 4: f14 -> f9 : A'=free_1, D'=0, [ 0>=C ], cost: 1 5.12/2.29 5.12/2.29 6: f0 -> f9 : A'=free_2, B'=0, D'=0, [], cost: 1 5.12/2.29 5.12/2.29 5.12/2.29 5.12/2.29 Removed unreachable locations (and leaf rules with constant cost): 5.12/2.29 5.12/2.29 Start location: f0 5.12/2.29 5.12/2.29 0: f9 -> f14 : B'=0, C'=free, [ 0>=A ], cost: 1 5.12/2.29 5.12/2.29 9: f9 -> f14 : B'=0, C'=0, [ 0>=A && free>=1 ], cost: 1+free 5.12/2.29 5.12/2.29 10: f9 -> [7] : [ A>=1 ], cost: INF 5.12/2.29 5.12/2.29 4: f14 -> f9 : A'=free_1, D'=0, [ 0>=C ], cost: 1 5.12/2.29 5.12/2.29 6: f0 -> f9 : A'=free_2, B'=0, D'=0, [], cost: 1 5.12/2.29 5.12/2.29 5.12/2.29 5.12/2.29 Eliminated locations (on tree-shaped paths): 5.12/2.29 5.12/2.29 Start location: f0 5.12/2.29 5.12/2.29 10: f9 -> [7] : [ A>=1 ], cost: INF 5.12/2.29 5.12/2.29 11: f9 -> f9 : A'=free_1, B'=0, C'=free, D'=0, [ 0>=A && 0>=free ], cost: 2 5.12/2.29 5.12/2.29 12: f9 -> f9 : A'=free_1, B'=0, C'=0, D'=0, [ 0>=A && free>=1 ], cost: 2+free 5.12/2.29 5.12/2.29 6: f0 -> f9 : A'=free_2, B'=0, D'=0, [], cost: 1 5.12/2.29 5.12/2.29 5.12/2.29 5.12/2.29 Accelerating simple loops of location 0. 5.12/2.29 5.12/2.29 Accelerating the following rules: 5.12/2.29 5.12/2.29 11: f9 -> f9 : A'=free_1, B'=0, C'=free, D'=0, [ 0>=A && 0>=free ], cost: 2 5.12/2.29 5.12/2.29 12: f9 -> f9 : A'=free_1, B'=0, C'=0, D'=0, [ 0>=A && free>=1 ], cost: 2+free 5.12/2.29 5.12/2.29 5.12/2.29 5.12/2.29 Accelerated rule 11 with NONTERM (after strengthening guard), yielding the new rule 13. 5.12/2.29 5.12/2.29 Accelerated rule 12 with NONTERM (after strengthening guard), yielding the new rule 14. 5.12/2.29 5.12/2.29 Removing the simple loops:. 5.12/2.29 5.12/2.29 5.12/2.29 5.12/2.29 Accelerated all simple loops using metering functions (where possible): 5.12/2.29 5.12/2.29 Start location: f0 5.12/2.29 5.12/2.29 10: f9 -> [7] : [ A>=1 ], cost: INF 5.12/2.29 5.12/2.29 11: f9 -> f9 : A'=free_1, B'=0, C'=free, D'=0, [ 0>=A && 0>=free ], cost: 2 5.12/2.29 5.12/2.29 12: f9 -> f9 : A'=free_1, B'=0, C'=0, D'=0, [ 0>=A && free>=1 ], cost: 2+free 5.12/2.29 5.12/2.29 13: f9 -> [8] : [ 0>=A && 0>=free && 0>=free_1 ], cost: INF 5.12/2.29 5.12/2.29 14: f9 -> [8] : [ 0>=A && free>=1 && 0>=free_1 ], cost: INF 5.12/2.29 5.12/2.29 6: f0 -> f9 : A'=free_2, B'=0, D'=0, [], cost: 1 5.12/2.29 5.12/2.29 5.12/2.29 5.12/2.29 Chained accelerated rules (with incoming rules): 5.12/2.29 5.12/2.29 Start location: f0 5.12/2.29 5.12/2.29 10: f9 -> [7] : [ A>=1 ], cost: INF 5.12/2.29 5.12/2.29 6: f0 -> f9 : A'=free_2, B'=0, D'=0, [], cost: 1 5.12/2.29 5.12/2.29 15: f0 -> f9 : A'=free_1, B'=0, C'=free, D'=0, [ 0>=free ], cost: 3 5.12/2.29 5.12/2.29 16: f0 -> f9 : A'=free_1, B'=0, C'=0, D'=0, [ free>=1 ], cost: 3+free 5.12/2.29 5.12/2.29 17: f0 -> [8] : A'=free_2, B'=0, D'=0, [ 0>=free_2 ], cost: INF 5.12/2.29 5.12/2.29 18: f0 -> [8] : A'=free_2, B'=0, D'=0, [ 0>=free_2 ], cost: INF 5.12/2.29 5.12/2.29 5.12/2.29 5.12/2.29 Eliminated locations (on tree-shaped paths): 5.12/2.29 5.12/2.29 Start location: f0 5.12/2.29 5.12/2.29 17: f0 -> [8] : A'=free_2, B'=0, D'=0, [ 0>=free_2 ], cost: INF 5.12/2.29 5.12/2.29 18: f0 -> [8] : A'=free_2, B'=0, D'=0, [ 0>=free_2 ], cost: INF 5.12/2.29 5.12/2.29 19: f0 -> [7] : A'=free_2, B'=0, D'=0, [ free_2>=1 ], cost: INF 5.12/2.29 5.12/2.29 20: f0 -> [7] : A'=free_1, B'=0, C'=free, D'=0, [ 0>=free && free_1>=1 ], cost: INF 5.12/2.29 5.12/2.29 21: f0 -> [7] : A'=free_1, B'=0, C'=0, D'=0, [ free>=1 && free_1>=1 ], cost: INF 5.12/2.29 5.12/2.29 5.12/2.29 5.12/2.29 ### Computing asymptotic complexity ### 5.12/2.29 5.12/2.29 5.12/2.29 5.12/2.29 Fully simplified ITS problem 5.12/2.29 5.12/2.29 Start location: f0 5.12/2.29 5.12/2.29 18: f0 -> [8] : A'=free_2, B'=0, D'=0, [ 0>=free_2 ], cost: INF 5.12/2.29 5.12/2.29 19: f0 -> [7] : A'=free_2, B'=0, D'=0, [ free_2>=1 ], cost: INF 5.12/2.29 5.12/2.29 20: f0 -> [7] : A'=free_1, B'=0, C'=free, D'=0, [ 0>=free && free_1>=1 ], cost: INF 5.12/2.29 5.12/2.29 21: f0 -> [7] : A'=free_1, B'=0, C'=0, D'=0, [ free>=1 && free_1>=1 ], cost: INF 5.12/2.29 5.12/2.29 5.12/2.29 5.12/2.29 Computing asymptotic complexity for rule 18 5.12/2.29 5.12/2.29 Resulting cost INF has complexity: Nonterm 5.12/2.29 5.12/2.29 5.12/2.29 5.12/2.29 Found new complexity Nonterm. 5.12/2.29 5.12/2.29 5.12/2.29 5.12/2.29 Obtained the following overall complexity (w.r.t. the length of the input n): 5.12/2.29 5.12/2.29 Complexity: Nonterm 5.12/2.29 5.12/2.29 Cpx degree: Nonterm 5.12/2.29 5.12/2.29 Solved cost: INF 5.12/2.29 5.12/2.29 Rule cost: INF 5.12/2.29 5.12/2.29 Rule guard: [ 0>=free_2 ] 5.12/2.29 5.12/2.29 5.12/2.29 5.12/2.29 NO 5.12/2.29 5.12/2.29 5.12/2.29 ---------------------------------------- 5.12/2.29 5.12/2.29 (2) 5.12/2.29 BOUNDS(INF, INF) 5.22/2.31 EOF