4.14/1.93 WORST_CASE(NON_POLY, ?) 4.14/1.94 proof of /export/starexec/sandbox/benchmark/theBenchmark.koat 4.14/1.94 # AProVE Commit ID: 48fb2092695e11cc9f56e44b17a92a5f88ffb256 marcel 20180622 unpublished dirty 4.14/1.94 4.14/1.94 4.14/1.94 The runtime complexity of the given CpxIntTrs could be proven to be BOUNDS(INF, INF). 4.14/1.94 4.14/1.94 (0) CpxIntTrs 4.14/1.94 (1) Loat Proof [FINISHED, 190 ms] 4.14/1.94 (2) BOUNDS(INF, INF) 4.14/1.94 4.14/1.94 4.14/1.94 ---------------------------------------- 4.14/1.94 4.14/1.94 (0) 4.14/1.94 Obligation: 4.14/1.94 Complexity Int TRS consisting of the following rules: 4.14/1.94 f1(A, B, C, D, E, F, G, H) -> Com_1(f1(A, B, J, I, K, F, G, H)) :|: I >= 1 && A >= 1 + B 4.14/1.94 f1(A, B, C, D, E, F, G, H) -> Com_1(f1(A, B, J, I, K, F, G, H)) :|: 0 >= I + 1 && A >= 1 + B 4.14/1.94 f1(A, B, C, D, E, F, G, H) -> Com_1(f1(A, B, J, 0, E, F, G, H)) :|: A >= 1 + B 4.14/1.94 f1(A, B, C, D, E, F, G, H) -> Com_1(f300(A, B, J, D, E, I, G, H)) :|: B >= A 4.14/1.94 f2(A, B, C, D, E, F, G, H) -> Com_1(f1(A, B, C, D, E, F, J, J)) :|: TRUE 4.14/1.94 4.14/1.94 The start-symbols are:[f2_8] 4.14/1.94 4.14/1.94 4.14/1.94 ---------------------------------------- 4.14/1.94 4.14/1.94 (1) Loat Proof (FINISHED) 4.14/1.94 4.14/1.94 4.14/1.94 ### Pre-processing the ITS problem ### 4.14/1.94 4.14/1.94 4.14/1.94 4.14/1.94 Initial linear ITS problem 4.14/1.94 4.14/1.94 Start location: f2 4.23/1.99 4.23/1.99 0: f1 -> f1 : C'=free_1, D'=free, E'=free_2, [ free>=1 && A>=1+B ], cost: 1 4.23/1.99 4.23/1.99 1: f1 -> f1 : C'=free_4, D'=free_3, E'=free_5, [ 0>=1+free_3 && A>=1+B ], cost: 1 4.23/1.99 4.23/1.99 2: f1 -> f1 : C'=free_6, D'=0, [ A>=1+B ], cost: 1 4.23/1.99 4.23/1.99 3: f1 -> f300 : C'=free_8, F'=free_7, [ B>=A ], cost: 1 4.23/1.99 4.23/1.99 4: f2 -> f1 : G'=free_9, H'=free_9, [], cost: 1 4.23/1.99 4.23/1.99 4.23/1.99 4.23/1.99 Removed unreachable and leaf rules: 4.23/1.99 4.23/1.99 Start location: f2 4.23/1.99 4.23/1.99 0: f1 -> f1 : C'=free_1, D'=free, E'=free_2, [ free>=1 && A>=1+B ], cost: 1 4.23/1.99 4.23/1.99 1: f1 -> f1 : C'=free_4, D'=free_3, E'=free_5, [ 0>=1+free_3 && A>=1+B ], cost: 1 4.23/1.99 4.23/1.99 2: f1 -> f1 : C'=free_6, D'=0, [ A>=1+B ], cost: 1 4.23/1.99 4.23/1.99 4: f2 -> f1 : G'=free_9, H'=free_9, [], cost: 1 4.23/1.99 4.23/1.99 4.23/1.99 4.23/1.99 ### Simplification by acceleration and chaining ### 4.23/1.99 4.23/1.99 4.23/1.99 4.23/1.99 Accelerating simple loops of location 0. 4.23/1.99 4.23/1.99 Accelerating the following rules: 4.23/1.99 4.23/1.99 0: f1 -> f1 : C'=free_1, D'=free, E'=free_2, [ free>=1 && A>=1+B ], cost: 1 4.23/1.99 4.23/1.99 1: f1 -> f1 : C'=free_4, D'=free_3, E'=free_5, [ 0>=1+free_3 && A>=1+B ], cost: 1 4.23/1.99 4.23/1.99 2: f1 -> f1 : C'=free_6, D'=0, [ A>=1+B ], cost: 1 4.23/1.99 4.23/1.99 4.23/1.99 4.23/1.99 Accelerated rule 0 with NONTERM, yielding the new rule 5. 4.23/1.99 4.23/1.99 Accelerated rule 1 with NONTERM, yielding the new rule 6. 4.23/1.99 4.23/1.99 Accelerated rule 2 with NONTERM, yielding the new rule 7. 4.23/1.99 4.23/1.99 Removing the simple loops: 0 1 2. 4.23/1.99 4.23/1.99 4.23/1.99 4.23/1.99 Accelerated all simple loops using metering functions (where possible): 4.23/1.99 4.23/1.99 Start location: f2 4.23/1.99 4.23/1.99 5: f1 -> [3] : [ free>=1 && A>=1+B ], cost: INF 4.23/1.99 4.23/1.99 6: f1 -> [3] : [ 0>=1+free_3 && A>=1+B ], cost: INF 4.23/1.99 4.23/1.99 7: f1 -> [3] : [ A>=1+B ], cost: INF 4.23/1.99 4.23/1.99 4: f2 -> f1 : G'=free_9, H'=free_9, [], cost: 1 4.23/1.99 4.23/1.99 4.23/1.99 4.23/1.99 Chained accelerated rules (with incoming rules): 4.23/1.99 4.23/1.99 Start location: f2 4.23/1.99 4.23/1.99 4: f2 -> f1 : G'=free_9, H'=free_9, [], cost: 1 4.23/1.99 4.23/1.99 8: f2 -> [3] : G'=free_9, H'=free_9, [ A>=1+B ], cost: INF 4.23/1.99 4.23/1.99 9: f2 -> [3] : G'=free_9, H'=free_9, [ A>=1+B ], cost: INF 4.23/1.99 4.23/1.99 10: f2 -> [3] : G'=free_9, H'=free_9, [ A>=1+B ], cost: INF 4.23/1.99 4.23/1.99 4.23/1.99 4.23/1.99 Removed unreachable locations (and leaf rules with constant cost): 4.23/1.99 4.23/1.99 Start location: f2 4.23/1.99 4.23/1.99 8: f2 -> [3] : G'=free_9, H'=free_9, [ A>=1+B ], cost: INF 4.23/1.99 4.23/1.99 9: f2 -> [3] : G'=free_9, H'=free_9, [ A>=1+B ], cost: INF 4.23/1.99 4.23/1.99 10: f2 -> [3] : G'=free_9, H'=free_9, [ A>=1+B ], cost: INF 4.23/1.99 4.23/1.99 4.23/1.99 4.23/1.99 ### Computing asymptotic complexity ### 4.23/1.99 4.23/1.99 4.23/1.99 4.23/1.99 Fully simplified ITS problem 4.23/1.99 4.23/1.99 Start location: f2 4.23/1.99 4.23/1.99 10: f2 -> [3] : G'=free_9, H'=free_9, [ A>=1+B ], cost: INF 4.23/1.99 4.23/1.99 4.23/1.99 4.23/1.99 Computing asymptotic complexity for rule 10 4.23/1.99 4.23/1.99 Resulting cost INF has complexity: Nonterm 4.23/1.99 4.23/1.99 4.23/1.99 4.23/1.99 Found new complexity Nonterm. 4.23/1.99 4.23/1.99 4.23/1.99 4.23/1.99 Obtained the following overall complexity (w.r.t. the length of the input n): 4.23/1.99 4.23/1.99 Complexity: Nonterm 4.23/1.99 4.23/1.99 Cpx degree: Nonterm 4.23/1.99 4.23/1.99 Solved cost: INF 4.23/1.99 4.23/1.99 Rule cost: INF 4.23/1.99 4.23/1.99 Rule guard: [ A>=1+B ] 4.23/1.99 4.23/1.99 4.23/1.99 4.23/1.99 NO 4.23/1.99 4.23/1.99 4.23/1.99 ---------------------------------------- 4.23/1.99 4.23/1.99 (2) 4.23/1.99 BOUNDS(INF, INF) 4.24/2.05 EOF