4.74/2.27 WORST_CASE(NON_POLY, ?) 4.74/2.28 proof of /export/starexec/sandbox/benchmark/theBenchmark.koat 4.74/2.28 # AProVE Commit ID: 48fb2092695e11cc9f56e44b17a92a5f88ffb256 marcel 20180622 unpublished dirty 4.74/2.28 4.74/2.28 4.74/2.28 The runtime complexity of the given CpxIntTrs could be proven to be BOUNDS(INF, INF). 4.74/2.28 4.74/2.28 (0) CpxIntTrs 4.74/2.28 (1) Loat Proof [FINISHED, 613 ms] 4.74/2.28 (2) BOUNDS(INF, INF) 4.74/2.28 4.74/2.28 4.74/2.28 ---------------------------------------- 4.74/2.28 4.74/2.28 (0) 4.74/2.28 Obligation: 4.74/2.28 Complexity Int TRS consisting of the following rules: 4.74/2.28 f2(A, B) -> Com_1(f2(-(1) + D, B)) :|: 0 >= C && 0 >= A + 1 4.74/2.28 f2(A, B) -> Com_1(f2(1 + D, B)) :|: C >= 2 && 0 >= A + 1 4.74/2.28 f2(A, B) -> Com_1(f2(-(1) + D, B)) :|: 0 >= 2 + C && A >= 1 4.74/2.28 f2(A, B) -> Com_1(f2(1 + D, B)) :|: C >= 0 && A >= 1 4.74/2.28 f3(A, B) -> Com_1(f2(A, B)) :|: TRUE 4.74/2.28 f2(A, B) -> Com_1(f300(0, D)) :|: 0 >= A + 1 4.74/2.28 f2(A, B) -> Com_1(f300(0, D)) :|: A >= 1 4.74/2.28 f2(A, B) -> Com_1(f300(A, D)) :|: A >= 0 && A <= 0 4.74/2.28 4.74/2.28 The start-symbols are:[f3_2] 4.74/2.28 4.74/2.28 4.74/2.28 ---------------------------------------- 4.74/2.28 4.74/2.28 (1) Loat Proof (FINISHED) 4.74/2.28 4.74/2.28 4.74/2.28 ### Pre-processing the ITS problem ### 4.74/2.28 4.74/2.28 4.74/2.28 4.74/2.28 Initial linear ITS problem 4.74/2.28 4.74/2.28 Start location: f3 4.74/2.28 4.74/2.28 0: f2 -> f2 : A'=-1+free_1, [ 0>=free && 0>=1+A ], cost: 1 4.74/2.28 4.74/2.28 1: f2 -> f2 : A'=1+free_3, [ free_2>=2 && 0>=1+A ], cost: 1 4.74/2.28 4.74/2.28 2: f2 -> f2 : A'=-1+free_5, [ 0>=2+free_4 && A>=1 ], cost: 1 4.74/2.28 4.74/2.28 3: f2 -> f2 : A'=1+free_7, [ free_6>=0 && A>=1 ], cost: 1 4.74/2.28 4.74/2.28 5: f2 -> f300 : A'=0, B'=free_8, [ 0>=1+A ], cost: 1 4.74/2.28 4.74/2.28 6: f2 -> f300 : A'=0, B'=free_9, [ A>=1 ], cost: 1 4.74/2.28 4.74/2.28 7: f2 -> f300 : B'=free_10, [ A==0 ], cost: 1 4.74/2.28 4.74/2.28 4: f3 -> f2 : [], cost: 1 4.74/2.28 4.74/2.28 4.74/2.28 4.74/2.28 Removed unreachable and leaf rules: 4.74/2.28 4.74/2.28 Start location: f3 4.74/2.28 4.74/2.28 0: f2 -> f2 : A'=-1+free_1, [ 0>=free && 0>=1+A ], cost: 1 4.74/2.28 4.74/2.28 1: f2 -> f2 : A'=1+free_3, [ free_2>=2 && 0>=1+A ], cost: 1 4.74/2.28 4.74/2.28 2: f2 -> f2 : A'=-1+free_5, [ 0>=2+free_4 && A>=1 ], cost: 1 4.74/2.28 4.74/2.28 3: f2 -> f2 : A'=1+free_7, [ free_6>=0 && A>=1 ], cost: 1 4.74/2.28 4.74/2.28 4: f3 -> f2 : [], cost: 1 4.74/2.28 4.74/2.28 4.74/2.28 4.74/2.28 Simplified all rules, resulting in: 4.74/2.28 4.74/2.28 Start location: f3 4.74/2.28 4.74/2.28 0: f2 -> f2 : A'=-1+free_1, [ 0>=1+A ], cost: 1 4.74/2.28 4.74/2.28 1: f2 -> f2 : A'=1+free_3, [ 0>=1+A ], cost: 1 4.74/2.28 4.74/2.28 2: f2 -> f2 : A'=-1+free_5, [ A>=1 ], cost: 1 4.74/2.28 4.74/2.28 3: f2 -> f2 : A'=1+free_7, [ A>=1 ], cost: 1 4.74/2.28 4.74/2.28 4: f3 -> f2 : [], cost: 1 4.74/2.28 4.74/2.28 4.74/2.28 4.74/2.28 ### Simplification by acceleration and chaining ### 4.74/2.28 4.74/2.28 4.74/2.28 4.74/2.28 Accelerating simple loops of location 0. 4.74/2.28 4.74/2.28 Accelerating the following rules: 4.74/2.28 4.74/2.28 0: f2 -> f2 : A'=-1+free_1, [ 0>=1+A ], cost: 1 4.74/2.28 4.74/2.28 1: f2 -> f2 : A'=1+free_3, [ 0>=1+A ], cost: 1 4.74/2.28 4.74/2.28 2: f2 -> f2 : A'=-1+free_5, [ A>=1 ], cost: 1 4.74/2.28 4.74/2.28 3: f2 -> f2 : A'=1+free_7, [ A>=1 ], cost: 1 4.74/2.28 4.74/2.28 4.74/2.28 4.74/2.28 Accelerated rule 0 with NONTERM (after strengthening guard), yielding the new rule 8. 4.74/2.28 4.74/2.28 Accelerated rule 1 with NONTERM (after strengthening guard), yielding the new rule 9. 4.74/2.28 4.74/2.28 Accelerated rule 2 with NONTERM (after strengthening guard), yielding the new rule 10. 4.74/2.28 4.74/2.28 Accelerated rule 3 with NONTERM (after strengthening guard), yielding the new rule 11. 4.74/2.28 4.74/2.28 Removing the simple loops:. 4.74/2.28 4.74/2.28 4.74/2.28 4.74/2.28 Accelerated all simple loops using metering functions (where possible): 4.74/2.28 4.74/2.28 Start location: f3 4.74/2.28 4.74/2.28 0: f2 -> f2 : A'=-1+free_1, [ 0>=1+A ], cost: 1 4.74/2.28 4.74/2.28 1: f2 -> f2 : A'=1+free_3, [ 0>=1+A ], cost: 1 4.74/2.28 4.74/2.28 2: f2 -> f2 : A'=-1+free_5, [ A>=1 ], cost: 1 4.74/2.28 4.74/2.28 3: f2 -> f2 : A'=1+free_7, [ A>=1 ], cost: 1 4.74/2.28 4.74/2.28 8: f2 -> [3] : [ 0>=1+A && 0>=free_1 ], cost: INF 4.74/2.28 4.74/2.28 9: f2 -> [3] : [ 0>=1+A && 0>=2+free_3 ], cost: INF 4.74/2.28 4.74/2.28 10: f2 -> [3] : [ A>=1 && -1+free_5>=1 ], cost: INF 4.74/2.28 4.74/2.28 11: f2 -> [3] : [ A>=1 && 1+free_7>=1 ], cost: INF 4.74/2.28 4.74/2.28 4: f3 -> f2 : [], cost: 1 4.74/2.28 4.74/2.28 4.74/2.28 4.74/2.28 Chained accelerated rules (with incoming rules): 4.74/2.28 4.74/2.28 Start location: f3 4.74/2.28 4.74/2.28 4: f3 -> f2 : [], cost: 1 4.74/2.28 4.74/2.28 12: f3 -> f2 : A'=-1+free_1, [ 0>=1+A ], cost: 2 4.74/2.28 4.74/2.28 13: f3 -> f2 : A'=1+free_3, [ 0>=1+A ], cost: 2 4.74/2.28 4.74/2.28 14: f3 -> f2 : A'=-1+free_5, [ A>=1 ], cost: 2 4.74/2.28 4.74/2.28 15: f3 -> f2 : A'=1+free_7, [ A>=1 ], cost: 2 4.74/2.28 4.74/2.28 16: f3 -> [3] : [ 0>=1+A ], cost: INF 4.74/2.28 4.74/2.28 17: f3 -> [3] : [ 0>=1+A ], cost: INF 4.74/2.28 4.74/2.28 18: f3 -> [3] : [ A>=1 ], cost: INF 4.74/2.28 4.74/2.28 19: f3 -> [3] : [ A>=1 ], cost: INF 4.74/2.28 4.74/2.28 4.74/2.28 4.74/2.28 Removed unreachable locations (and leaf rules with constant cost): 4.74/2.28 4.74/2.28 Start location: f3 4.74/2.28 4.74/2.28 16: f3 -> [3] : [ 0>=1+A ], cost: INF 4.74/2.28 4.74/2.28 17: f3 -> [3] : [ 0>=1+A ], cost: INF 4.74/2.28 4.74/2.28 18: f3 -> [3] : [ A>=1 ], cost: INF 4.74/2.28 4.74/2.28 19: f3 -> [3] : [ A>=1 ], cost: INF 4.74/2.28 4.74/2.28 4.74/2.28 4.74/2.28 ### Computing asymptotic complexity ### 4.74/2.28 4.74/2.28 4.74/2.28 4.74/2.28 Fully simplified ITS problem 4.74/2.28 4.74/2.28 Start location: f3 4.74/2.28 4.74/2.28 17: f3 -> [3] : [ 0>=1+A ], cost: INF 4.74/2.28 4.74/2.28 19: f3 -> [3] : [ A>=1 ], cost: INF 4.74/2.28 4.74/2.28 4.74/2.28 4.74/2.28 Computing asymptotic complexity for rule 17 4.74/2.28 4.74/2.28 Resulting cost INF has complexity: Nonterm 4.74/2.28 4.74/2.28 4.74/2.28 4.74/2.28 Found new complexity Nonterm. 4.74/2.28 4.74/2.28 4.74/2.28 4.74/2.28 Obtained the following overall complexity (w.r.t. the length of the input n): 4.74/2.28 4.74/2.28 Complexity: Nonterm 4.74/2.28 4.74/2.28 Cpx degree: Nonterm 4.74/2.28 4.74/2.28 Solved cost: INF 4.74/2.28 4.74/2.28 Rule cost: INF 4.74/2.28 4.74/2.28 Rule guard: [ 0>=1+A ] 4.74/2.28 4.74/2.28 4.74/2.28 4.74/2.28 NO 4.74/2.28 4.74/2.28 4.74/2.28 ---------------------------------------- 4.74/2.28 4.74/2.28 (2) 4.74/2.28 BOUNDS(INF, INF) 4.74/2.29 EOF