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