4.00/1.89 WORST_CASE(NON_POLY, ?) 4.00/1.89 proof of /export/starexec/sandbox/benchmark/theBenchmark.koat 4.00/1.89 # AProVE Commit ID: 48fb2092695e11cc9f56e44b17a92a5f88ffb256 marcel 20180622 unpublished dirty 4.00/1.89 4.00/1.89 4.00/1.89 The runtime complexity of the given CpxIntTrs could be proven to be BOUNDS(INF, INF). 4.00/1.89 4.00/1.89 (0) CpxIntTrs 4.00/1.89 (1) Loat Proof [FINISHED, 199 ms] 4.00/1.89 (2) BOUNDS(INF, INF) 4.00/1.89 4.00/1.89 4.00/1.89 ---------------------------------------- 4.00/1.89 4.00/1.89 (0) 4.00/1.89 Obligation: 4.00/1.89 Complexity Int TRS consisting of the following rules: 4.00/1.89 f0(A, B, C, D) -> Com_1(f14(E, E, 0, D)) :|: 0 >= E 4.00/1.89 f0(A, B, C, D) -> Com_1(f14(E, E, 0, D)) :|: E >= 1024 4.00/1.89 f0(A, B, C, D) -> Com_1(f14(E, E, 0, F)) :|: 1023 >= E && E >= 1 4.00/1.89 f14(A, B, C, D) -> Com_1(f14(A, B, C + 1, D)) :|: E >= C + 1 4.00/1.89 f14(A, B, C, D) -> Com_1(f22(A, B, C, D)) :|: C >= E 4.00/1.89 4.00/1.89 The start-symbols are:[f0_4] 4.00/1.89 4.00/1.89 4.00/1.89 ---------------------------------------- 4.00/1.89 4.00/1.89 (1) Loat Proof (FINISHED) 4.00/1.89 4.00/1.89 4.00/1.89 ### Pre-processing the ITS problem ### 4.00/1.89 4.00/1.89 4.00/1.89 4.00/1.89 Initial linear ITS problem 4.00/1.89 4.00/1.89 Start location: f0 4.00/1.89 4.00/1.89 0: f0 -> f14 : A'=free, B'=free, C'=0, [ 0>=free ], cost: 1 4.00/1.89 4.00/1.89 1: f0 -> f14 : A'=free_1, B'=free_1, C'=0, [ free_1>=1024 ], cost: 1 4.00/1.89 4.00/1.89 2: f0 -> f14 : A'=free_3, B'=free_3, C'=0, D'=free_2, [ 1023>=free_3 && free_3>=1 ], cost: 1 4.00/1.89 4.00/1.89 3: f14 -> f14 : C'=1+C, [ free_4>=1+C ], cost: 1 4.00/1.89 4.00/1.89 4: f14 -> f22 : [ C>=free_5 ], cost: 1 4.00/1.89 4.00/1.89 4.00/1.89 4.00/1.89 Removed unreachable and leaf rules: 4.00/1.89 4.00/1.89 Start location: f0 4.00/1.89 4.00/1.89 0: f0 -> f14 : A'=free, B'=free, C'=0, [ 0>=free ], cost: 1 4.00/1.89 4.00/1.89 1: f0 -> f14 : A'=free_1, B'=free_1, C'=0, [ free_1>=1024 ], cost: 1 4.00/1.89 4.00/1.89 2: f0 -> f14 : A'=free_3, B'=free_3, C'=0, D'=free_2, [ 1023>=free_3 && free_3>=1 ], cost: 1 4.00/1.89 4.00/1.89 3: f14 -> f14 : C'=1+C, [ free_4>=1+C ], cost: 1 4.00/1.89 4.00/1.89 4.00/1.89 4.00/1.89 Simplified all rules, resulting in: 4.00/1.89 4.00/1.89 Start location: f0 4.00/1.89 4.00/1.89 0: f0 -> f14 : A'=free, B'=free, C'=0, [ 0>=free ], cost: 1 4.00/1.89 4.00/1.89 1: f0 -> f14 : A'=free_1, B'=free_1, C'=0, [ free_1>=1024 ], cost: 1 4.00/1.89 4.00/1.89 2: f0 -> f14 : A'=free_3, B'=free_3, C'=0, D'=free_2, [ 1023>=free_3 && free_3>=1 ], cost: 1 4.00/1.89 4.00/1.89 3: f14 -> f14 : C'=1+C, [], cost: 1 4.00/1.89 4.00/1.89 4.00/1.89 4.00/1.89 ### Simplification by acceleration and chaining ### 4.00/1.89 4.00/1.89 4.00/1.89 4.00/1.89 Accelerating simple loops of location 1. 4.00/1.89 4.00/1.89 Accelerating the following rules: 4.00/1.89 4.00/1.89 3: f14 -> f14 : C'=1+C, [], cost: 1 4.00/1.89 4.00/1.89 4.00/1.89 4.00/1.89 Accelerated rule 3 with NONTERM, yielding the new rule 5. 4.00/1.89 4.00/1.89 Removing the simple loops: 3. 4.00/1.89 4.00/1.89 4.00/1.89 4.00/1.89 Accelerated all simple loops using metering functions (where possible): 4.00/1.89 4.00/1.89 Start location: f0 4.00/1.89 4.00/1.89 0: f0 -> f14 : A'=free, B'=free, C'=0, [ 0>=free ], cost: 1 4.00/1.89 4.00/1.89 1: f0 -> f14 : A'=free_1, B'=free_1, C'=0, [ free_1>=1024 ], cost: 1 4.00/1.89 4.00/1.89 2: f0 -> f14 : A'=free_3, B'=free_3, C'=0, D'=free_2, [ 1023>=free_3 && free_3>=1 ], cost: 1 4.00/1.89 4.00/1.89 5: f14 -> [3] : [], cost: INF 4.00/1.89 4.00/1.89 4.00/1.89 4.00/1.89 Chained accelerated rules (with incoming rules): 4.00/1.89 4.00/1.89 Start location: f0 4.00/1.89 4.00/1.89 0: f0 -> f14 : A'=free, B'=free, C'=0, [ 0>=free ], cost: 1 4.00/1.89 4.00/1.89 1: f0 -> f14 : A'=free_1, B'=free_1, C'=0, [ free_1>=1024 ], cost: 1 4.00/1.89 4.00/1.89 2: f0 -> f14 : A'=free_3, B'=free_3, C'=0, D'=free_2, [ 1023>=free_3 && free_3>=1 ], cost: 1 4.00/1.89 4.00/1.89 6: f0 -> [3] : A'=free, B'=free, C'=0, [ 0>=free ], cost: INF 4.00/1.89 4.00/1.89 7: f0 -> [3] : A'=free_1, B'=free_1, C'=0, [ free_1>=1024 ], cost: INF 4.00/1.89 4.00/1.89 8: f0 -> [3] : A'=free_3, B'=free_3, C'=0, D'=free_2, [ 1023>=free_3 && free_3>=1 ], cost: INF 4.00/1.89 4.00/1.89 4.00/1.89 4.00/1.89 Removed unreachable locations (and leaf rules with constant cost): 4.00/1.89 4.00/1.89 Start location: f0 4.00/1.89 4.00/1.89 6: f0 -> [3] : A'=free, B'=free, C'=0, [ 0>=free ], cost: INF 4.00/1.89 4.00/1.89 7: f0 -> [3] : A'=free_1, B'=free_1, C'=0, [ free_1>=1024 ], cost: INF 4.00/1.89 4.00/1.89 8: f0 -> [3] : A'=free_3, B'=free_3, C'=0, D'=free_2, [ 1023>=free_3 && free_3>=1 ], cost: INF 4.00/1.89 4.00/1.89 4.00/1.89 4.00/1.89 ### Computing asymptotic complexity ### 4.00/1.89 4.00/1.89 4.00/1.89 4.00/1.89 Fully simplified ITS problem 4.00/1.89 4.00/1.89 Start location: f0 4.00/1.89 4.00/1.89 6: f0 -> [3] : A'=free, B'=free, C'=0, [ 0>=free ], cost: INF 4.00/1.89 4.00/1.89 7: f0 -> [3] : A'=free_1, B'=free_1, C'=0, [ free_1>=1024 ], cost: INF 4.00/1.89 4.00/1.89 8: f0 -> [3] : A'=free_3, B'=free_3, C'=0, D'=free_2, [ 1023>=free_3 && free_3>=1 ], cost: INF 4.00/1.89 4.00/1.89 4.00/1.89 4.00/1.89 Computing asymptotic complexity for rule 6 4.00/1.89 4.00/1.89 Resulting cost INF has complexity: Nonterm 4.00/1.89 4.00/1.89 4.00/1.89 4.00/1.89 Found new complexity Nonterm. 4.00/1.89 4.00/1.89 4.00/1.89 4.00/1.89 Obtained the following overall complexity (w.r.t. the length of the input n): 4.00/1.89 4.00/1.89 Complexity: Nonterm 4.00/1.89 4.00/1.89 Cpx degree: Nonterm 4.00/1.89 4.00/1.89 Solved cost: INF 4.00/1.89 4.00/1.89 Rule cost: INF 4.00/1.89 4.00/1.89 Rule guard: [ 0>=free ] 4.00/1.89 4.00/1.89 4.00/1.89 4.00/1.89 NO 4.00/1.89 4.00/1.89 4.00/1.89 ---------------------------------------- 4.00/1.89 4.00/1.89 (2) 4.00/1.89 BOUNDS(INF, INF) 4.22/1.90 EOF