3.63/1.78 WORST_CASE(NON_POLY, ?) 3.63/1.79 proof of /export/starexec/sandbox/benchmark/theBenchmark.koat 3.63/1.79 # AProVE Commit ID: 48fb2092695e11cc9f56e44b17a92a5f88ffb256 marcel 20180622 unpublished dirty 3.63/1.79 3.63/1.79 3.63/1.79 The runtime complexity of the given CpxIntTrs could be proven to be BOUNDS(INF, INF). 3.63/1.79 3.63/1.79 (0) CpxIntTrs 3.63/1.79 (1) Loat Proof [FINISHED, 4 ms] 3.63/1.79 (2) BOUNDS(INF, INF) 3.63/1.79 3.63/1.79 3.63/1.79 ---------------------------------------- 3.63/1.79 3.63/1.79 (0) 3.63/1.79 Obligation: 3.63/1.79 Complexity Int TRS consisting of the following rules: 3.63/1.79 f20(A, B) -> Com_1(f1(0, 0)) :|: TRUE 3.63/1.79 f1(A, B) -> Com_1(f1(A + 1, B + 1)) :|: TRUE 3.63/1.79 f1(A, B) -> Com_1(f30(A, B)) :|: A >= B + 1 3.63/1.79 3.63/1.79 The start-symbols are:[f20_2] 3.63/1.79 3.63/1.79 3.63/1.79 ---------------------------------------- 3.63/1.79 3.63/1.79 (1) Loat Proof (FINISHED) 3.63/1.79 3.63/1.79 3.63/1.79 ### Pre-processing the ITS problem ### 3.63/1.79 3.63/1.79 3.63/1.79 3.63/1.79 Initial linear ITS problem 3.63/1.79 3.63/1.79 Start location: f20 3.63/1.79 3.63/1.79 0: f20 -> f1 : A'=0, B'=0, [], cost: 1 3.63/1.79 3.63/1.79 1: f1 -> f1 : A'=1+A, B'=1+B, [], cost: 1 3.63/1.79 3.63/1.79 2: f1 -> f30 : [ A>=1+B ], cost: 1 3.63/1.79 3.63/1.79 3.63/1.79 3.63/1.79 Removed unreachable and leaf rules: 3.63/1.79 3.63/1.79 Start location: f20 3.63/1.79 3.63/1.79 0: f20 -> f1 : A'=0, B'=0, [], cost: 1 3.63/1.79 3.63/1.79 1: f1 -> f1 : A'=1+A, B'=1+B, [], cost: 1 3.63/1.79 3.63/1.79 3.63/1.79 3.63/1.79 ### Simplification by acceleration and chaining ### 3.63/1.79 3.63/1.79 3.63/1.79 3.63/1.79 Accelerating simple loops of location 1. 3.63/1.79 3.63/1.79 Accelerating the following rules: 3.63/1.79 3.63/1.79 1: f1 -> f1 : A'=1+A, B'=1+B, [], cost: 1 3.63/1.79 3.63/1.79 3.63/1.79 3.63/1.79 Accelerated rule 1 with NONTERM, yielding the new rule 3. 3.63/1.79 3.63/1.79 Removing the simple loops: 1. 3.63/1.79 3.63/1.79 3.63/1.79 3.63/1.79 Accelerated all simple loops using metering functions (where possible): 3.63/1.79 3.63/1.79 Start location: f20 3.63/1.79 3.63/1.79 0: f20 -> f1 : A'=0, B'=0, [], cost: 1 3.63/1.79 3.63/1.79 3: f1 -> [3] : [], cost: INF 3.63/1.79 3.63/1.79 3.63/1.79 3.63/1.79 Chained accelerated rules (with incoming rules): 3.63/1.79 3.63/1.79 Start location: f20 3.63/1.79 3.63/1.79 0: f20 -> f1 : A'=0, B'=0, [], cost: 1 3.63/1.79 3.63/1.79 4: f20 -> [3] : A'=0, B'=0, [], cost: INF 3.63/1.79 3.63/1.79 3.63/1.79 3.63/1.79 Removed unreachable locations (and leaf rules with constant cost): 3.63/1.79 3.63/1.79 Start location: f20 3.63/1.79 3.63/1.79 4: f20 -> [3] : A'=0, B'=0, [], cost: INF 3.63/1.79 3.63/1.79 3.63/1.79 3.63/1.79 ### Computing asymptotic complexity ### 3.63/1.79 3.63/1.79 3.63/1.79 3.63/1.79 Fully simplified ITS problem 3.63/1.79 3.63/1.79 Start location: f20 3.63/1.79 3.63/1.79 4: f20 -> [3] : A'=0, B'=0, [], cost: INF 3.63/1.79 3.63/1.79 3.63/1.79 3.63/1.79 Computing asymptotic complexity for rule 4 3.63/1.79 3.63/1.79 Resulting cost INF has complexity: Nonterm 3.63/1.79 3.63/1.79 3.63/1.79 3.63/1.79 Found new complexity Nonterm. 3.63/1.79 3.63/1.79 3.63/1.79 3.63/1.79 Obtained the following overall complexity (w.r.t. the length of the input n): 3.63/1.79 3.63/1.79 Complexity: Nonterm 3.63/1.79 3.63/1.79 Cpx degree: Nonterm 3.63/1.79 3.63/1.79 Solved cost: INF 3.63/1.79 3.63/1.79 Rule cost: INF 3.63/1.79 3.63/1.79 Rule guard: [] 3.63/1.79 3.63/1.79 3.63/1.79 3.63/1.79 NO 3.63/1.79 3.63/1.79 3.63/1.79 ---------------------------------------- 3.63/1.79 3.63/1.79 (2) 3.63/1.79 BOUNDS(INF, INF) 3.71/1.82 EOF