4.04/1.92 WORST_CASE(NON_POLY, ?) 4.04/1.92 proof of /export/starexec/sandbox/benchmark/theBenchmark.koat 4.04/1.92 # AProVE Commit ID: 48fb2092695e11cc9f56e44b17a92a5f88ffb256 marcel 20180622 unpublished dirty 4.04/1.92 4.04/1.92 4.04/1.92 The runtime complexity of the given CpxIntTrs could be proven to be BOUNDS(INF, INF). 4.04/1.92 4.04/1.92 (0) CpxIntTrs 4.04/1.92 (1) Loat Proof [FINISHED, 200 ms] 4.04/1.92 (2) BOUNDS(INF, INF) 4.04/1.92 4.04/1.92 4.04/1.92 ---------------------------------------- 4.04/1.92 4.04/1.92 (0) 4.04/1.92 Obligation: 4.04/1.92 Complexity Int TRS consisting of the following rules: 4.04/1.92 f0(A, B, C, D, E, F, G, H, I, J, K) -> Com_1(f5(A, B, C, D, E, F, G, H, I, J, K)) :|: TRUE 4.04/1.92 f0(A, B, C, D, E, F, G, H, I, J, K) -> Com_1(f12(M, B, C, D, E, F, G, H, I, J, K)) :|: 15 >= L 4.04/1.92 f12(A, B, C, D, E, F, G, H, I, J, K) -> Com_1(f20(A, M, M, D, E, F, G, H, I, J, K)) :|: 0 >= A + 1 4.04/1.92 f12(A, B, C, D, E, F, G, H, I, J, K) -> Com_1(f20(A, M, M, D, E, F, G, H, I, J, K)) :|: A >= 1 4.04/1.92 f0(A, B, C, D, E, F, G, H, I, J, K) -> Com_1(f5(A, B, C, 1, 1, F, G, H, I, J, K)) :|: 15 >= M 4.04/1.92 f20(A, B, C, D, E, F, G, H, I, J, K) -> Com_1(f12(A - 1, B, C, D, E, 0, 0, H, I, J, K)) :|: TRUE 4.04/1.92 f12(A, B, C, D, E, F, G, H, I, J, K) -> Com_1(f5(0, B, C, 0, 0, F, G, M, M, 0, 0)) :|: A >= 0 && A <= 0 4.04/1.92 4.04/1.92 The start-symbols are:[f0_11] 4.04/1.92 4.04/1.92 4.04/1.92 ---------------------------------------- 4.04/1.92 4.04/1.92 (1) Loat Proof (FINISHED) 4.04/1.92 4.04/1.92 4.04/1.92 ### Pre-processing the ITS problem ### 4.04/1.92 4.04/1.92 4.04/1.92 4.04/1.92 Initial linear ITS problem 4.04/1.92 4.04/1.92 Start location: f0 4.04/1.92 4.04/1.92 0: f0 -> f5 : [], cost: 1 4.04/1.92 4.04/1.92 1: f0 -> f12 : A'=free_1, [ 15>=free ], cost: 1 4.04/1.92 4.04/1.92 4: f0 -> f5 : D'=1, E'=1, [ 15>=free_4 ], cost: 1 4.04/1.92 4.04/1.92 2: f12 -> f20 : B'=free_2, C'=free_2, [ 0>=1+A ], cost: 1 4.04/1.92 4.04/1.92 3: f12 -> f20 : B'=free_3, C'=free_3, [ A>=1 ], cost: 1 4.04/1.92 4.04/1.92 6: f12 -> f5 : A'=0, D'=0, E'=0, H'=free_5, Q'=free_5, J'=0, K'=0, [ A==0 ], cost: 1 4.04/1.92 4.04/1.92 5: f20 -> f12 : A'=-1+A, F'=0, G'=0, [], cost: 1 4.04/1.92 4.04/1.92 4.04/1.92 4.04/1.92 Removed unreachable and leaf rules: 4.04/1.92 4.04/1.92 Start location: f0 4.04/1.92 4.04/1.92 1: f0 -> f12 : A'=free_1, [ 15>=free ], cost: 1 4.04/1.92 4.04/1.92 2: f12 -> f20 : B'=free_2, C'=free_2, [ 0>=1+A ], cost: 1 4.04/1.92 4.04/1.92 3: f12 -> f20 : B'=free_3, C'=free_3, [ A>=1 ], cost: 1 4.04/1.92 4.04/1.92 5: f20 -> f12 : A'=-1+A, F'=0, G'=0, [], cost: 1 4.04/1.92 4.04/1.92 4.04/1.92 4.04/1.92 Simplified all rules, resulting in: 4.04/1.92 4.04/1.92 Start location: f0 4.04/1.92 4.04/1.92 1: f0 -> f12 : A'=free_1, [], cost: 1 4.04/1.92 4.04/1.92 2: f12 -> f20 : B'=free_2, C'=free_2, [ 0>=1+A ], cost: 1 4.04/1.92 4.04/1.92 3: f12 -> f20 : B'=free_3, C'=free_3, [ A>=1 ], cost: 1 4.04/1.92 4.04/1.92 5: f20 -> f12 : A'=-1+A, F'=0, G'=0, [], cost: 1 4.04/1.92 4.04/1.92 4.04/1.92 4.04/1.92 ### Simplification by acceleration and chaining ### 4.04/1.92 4.04/1.92 4.04/1.92 4.04/1.92 Eliminated locations (on tree-shaped paths): 4.04/1.92 4.04/1.92 Start location: f0 4.04/1.92 4.04/1.92 1: f0 -> f12 : A'=free_1, [], cost: 1 4.04/1.92 4.04/1.92 7: f12 -> f12 : A'=-1+A, B'=free_2, C'=free_2, F'=0, G'=0, [ 0>=1+A ], cost: 2 4.04/1.92 4.04/1.92 8: f12 -> f12 : A'=-1+A, B'=free_3, C'=free_3, F'=0, G'=0, [ A>=1 ], cost: 2 4.04/1.92 4.04/1.92 4.04/1.92 4.04/1.92 Accelerating simple loops of location 1. 4.04/1.92 4.04/1.92 Accelerating the following rules: 4.04/1.92 4.04/1.92 7: f12 -> f12 : A'=-1+A, B'=free_2, C'=free_2, F'=0, G'=0, [ 0>=1+A ], cost: 2 4.04/1.92 4.04/1.92 8: f12 -> f12 : A'=-1+A, B'=free_3, C'=free_3, F'=0, G'=0, [ A>=1 ], cost: 2 4.04/1.92 4.04/1.92 4.04/1.92 4.04/1.92 Accelerated rule 7 with NONTERM, yielding the new rule 9. 4.04/1.92 4.04/1.92 Accelerated rule 8 with metering function A, yielding the new rule 10. 4.04/1.92 4.04/1.92 Removing the simple loops: 7 8. 4.04/1.92 4.04/1.92 4.04/1.92 4.04/1.92 Accelerated all simple loops using metering functions (where possible): 4.04/1.92 4.04/1.92 Start location: f0 4.04/1.92 4.04/1.92 1: f0 -> f12 : A'=free_1, [], cost: 1 4.04/1.92 4.04/1.92 9: f12 -> [4] : [ 0>=1+A ], cost: INF 4.04/1.92 4.04/1.92 10: f12 -> f12 : A'=0, B'=free_3, C'=free_3, F'=0, G'=0, [ A>=1 ], cost: 2*A 4.04/1.92 4.04/1.92 4.04/1.92 4.04/1.92 Chained accelerated rules (with incoming rules): 4.04/1.92 4.04/1.92 Start location: f0 4.04/1.92 4.04/1.92 1: f0 -> f12 : A'=free_1, [], cost: 1 4.04/1.92 4.04/1.92 11: f0 -> [4] : A'=free_1, [ 0>=1+free_1 ], cost: INF 4.04/1.92 4.04/1.92 12: f0 -> f12 : A'=0, B'=free_3, C'=free_3, F'=0, G'=0, [ free_1>=1 ], cost: 1+2*free_1 4.04/1.92 4.04/1.92 4.04/1.92 4.04/1.92 Removed unreachable locations (and leaf rules with constant cost): 4.04/1.92 4.04/1.92 Start location: f0 4.04/1.92 4.04/1.92 11: f0 -> [4] : A'=free_1, [ 0>=1+free_1 ], cost: INF 4.04/1.92 4.04/1.92 12: f0 -> f12 : A'=0, B'=free_3, C'=free_3, F'=0, G'=0, [ free_1>=1 ], cost: 1+2*free_1 4.04/1.92 4.04/1.92 4.04/1.92 4.04/1.92 ### Computing asymptotic complexity ### 4.04/1.92 4.04/1.92 4.04/1.92 4.04/1.92 Fully simplified ITS problem 4.04/1.92 4.04/1.92 Start location: f0 4.04/1.92 4.04/1.92 11: f0 -> [4] : A'=free_1, [ 0>=1+free_1 ], cost: INF 4.04/1.92 4.04/1.92 12: f0 -> f12 : A'=0, B'=free_3, C'=free_3, F'=0, G'=0, [ free_1>=1 ], cost: 1+2*free_1 4.04/1.92 4.04/1.92 4.04/1.92 4.04/1.92 Computing asymptotic complexity for rule 11 4.04/1.92 4.04/1.92 Resulting cost INF has complexity: Nonterm 4.04/1.92 4.04/1.92 4.04/1.92 4.04/1.92 Found new complexity Nonterm. 4.04/1.92 4.04/1.92 4.04/1.92 4.04/1.92 Obtained the following overall complexity (w.r.t. the length of the input n): 4.04/1.92 4.04/1.92 Complexity: Nonterm 4.04/1.92 4.04/1.92 Cpx degree: Nonterm 4.04/1.92 4.04/1.92 Solved cost: INF 4.04/1.92 4.04/1.92 Rule cost: INF 4.04/1.92 4.04/1.92 Rule guard: [ 0>=1+free_1 ] 4.04/1.92 4.04/1.92 4.04/1.92 4.04/1.92 NO 4.04/1.92 4.04/1.92 4.04/1.92 ---------------------------------------- 4.04/1.92 4.04/1.92 (2) 4.04/1.92 BOUNDS(INF, INF) 4.04/1.96 EOF