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