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