4.55/2.05 WORST_CASE(NON_POLY, ?) 4.55/2.06 proof of /export/starexec/sandbox/benchmark/theBenchmark.koat 4.55/2.06 # AProVE Commit ID: 48fb2092695e11cc9f56e44b17a92a5f88ffb256 marcel 20180622 unpublished dirty 4.55/2.06 4.55/2.06 4.55/2.06 The runtime complexity of the given CpxIntTrs could be proven to be BOUNDS(INF, INF). 4.55/2.06 4.55/2.06 (0) CpxIntTrs 4.55/2.06 (1) Loat Proof [FINISHED, 414 ms] 4.55/2.06 (2) BOUNDS(INF, INF) 4.55/2.06 4.55/2.06 4.55/2.06 ---------------------------------------- 4.55/2.06 4.55/2.06 (0) 4.55/2.06 Obligation: 4.55/2.06 Complexity Int TRS consisting of the following rules: 4.55/2.06 f3(A, B, C) -> Com_1(f2(A, B, C)) :|: TRUE 4.55/2.06 f2(A, B, C) -> Com_1(f2(-(1) + A, D, C)) :|: D >= 1 && A >= 0 4.55/2.06 f2(A, B, C) -> Com_1(f2(-(1) + A, D, C)) :|: 0 >= D + 1 && A >= 0 4.55/2.06 f2(A, B, C) -> Com_1(f2(A, 0, C)) :|: A >= 0 4.55/2.06 f2(A, B, C) -> Com_1(f300(A, B, D)) :|: 0 >= A + 1 4.55/2.06 4.55/2.06 The start-symbols are:[f3_3] 4.55/2.06 4.55/2.06 4.55/2.06 ---------------------------------------- 4.55/2.06 4.55/2.06 (1) Loat Proof (FINISHED) 4.55/2.06 4.55/2.06 4.55/2.06 ### Pre-processing the ITS problem ### 4.55/2.06 4.55/2.06 4.55/2.06 4.55/2.06 Initial linear ITS problem 4.55/2.06 4.55/2.06 Start location: f3 4.55/2.06 4.55/2.06 0: f3 -> f2 : [], cost: 1 4.55/2.06 4.55/2.06 1: f2 -> f2 : A'=-1+A, B'=free, [ free>=1 && A>=0 ], cost: 1 4.55/2.06 4.55/2.06 2: f2 -> f2 : A'=-1+A, B'=free_1, [ 0>=1+free_1 && A>=0 ], cost: 1 4.55/2.06 4.55/2.06 3: f2 -> f2 : B'=0, [ A>=0 ], cost: 1 4.55/2.06 4.55/2.06 4: f2 -> f300 : C'=free_2, [ 0>=1+A ], cost: 1 4.55/2.06 4.55/2.06 4.55/2.06 4.55/2.06 Removed unreachable and leaf rules: 4.55/2.06 4.55/2.06 Start location: f3 4.55/2.06 4.55/2.06 0: f3 -> f2 : [], cost: 1 4.55/2.06 4.55/2.06 1: f2 -> f2 : A'=-1+A, B'=free, [ free>=1 && A>=0 ], cost: 1 4.55/2.06 4.55/2.06 2: f2 -> f2 : A'=-1+A, B'=free_1, [ 0>=1+free_1 && A>=0 ], cost: 1 4.55/2.06 4.55/2.06 3: f2 -> f2 : B'=0, [ A>=0 ], cost: 1 4.55/2.06 4.55/2.06 4.55/2.06 4.55/2.06 ### Simplification by acceleration and chaining ### 4.55/2.06 4.55/2.06 4.55/2.06 4.55/2.06 Accelerating simple loops of location 1. 4.55/2.06 4.55/2.06 Accelerating the following rules: 4.55/2.06 4.55/2.06 1: f2 -> f2 : A'=-1+A, B'=free, [ free>=1 && A>=0 ], cost: 1 4.55/2.06 4.55/2.06 2: f2 -> f2 : A'=-1+A, B'=free_1, [ 0>=1+free_1 && A>=0 ], cost: 1 4.55/2.06 4.55/2.06 3: f2 -> f2 : B'=0, [ A>=0 ], cost: 1 4.55/2.06 4.55/2.06 4.55/2.06 4.55/2.06 Accelerated rule 1 with metering function 1+A, yielding the new rule 5. 4.55/2.06 4.55/2.06 Accelerated rule 2 with metering function 1+A, yielding the new rule 6. 4.55/2.06 4.55/2.06 Accelerated rule 3 with NONTERM, yielding the new rule 7. 4.55/2.06 4.55/2.06 Removing the simple loops: 1 2 3. 4.55/2.06 4.55/2.06 4.55/2.06 4.55/2.06 Accelerated all simple loops using metering functions (where possible): 4.55/2.06 4.55/2.06 Start location: f3 4.55/2.06 4.55/2.06 0: f3 -> f2 : [], cost: 1 4.55/2.06 4.55/2.06 5: f2 -> f2 : A'=-1, B'=free, [ free>=1 && A>=0 ], cost: 1+A 4.55/2.06 4.55/2.06 6: f2 -> f2 : A'=-1, B'=free_1, [ 0>=1+free_1 && A>=0 ], cost: 1+A 4.55/2.06 4.55/2.06 7: f2 -> [3] : [ A>=0 ], cost: INF 4.55/2.06 4.55/2.06 4.55/2.06 4.55/2.06 Chained accelerated rules (with incoming rules): 4.55/2.06 4.55/2.06 Start location: f3 4.55/2.06 4.55/2.06 0: f3 -> f2 : [], cost: 1 4.55/2.06 4.55/2.06 8: f3 -> f2 : A'=-1, B'=free, [ free>=1 && A>=0 ], cost: 2+A 4.55/2.06 4.55/2.06 9: f3 -> f2 : A'=-1, B'=free_1, [ 0>=1+free_1 && A>=0 ], cost: 2+A 4.55/2.06 4.55/2.06 10: f3 -> [3] : [ A>=0 ], cost: INF 4.55/2.06 4.55/2.06 4.55/2.06 4.55/2.06 Removed unreachable locations (and leaf rules with constant cost): 4.55/2.06 4.55/2.06 Start location: f3 4.55/2.06 4.55/2.06 8: f3 -> f2 : A'=-1, B'=free, [ free>=1 && A>=0 ], cost: 2+A 4.55/2.06 4.55/2.06 9: f3 -> f2 : A'=-1, B'=free_1, [ 0>=1+free_1 && A>=0 ], cost: 2+A 4.55/2.06 4.55/2.06 10: f3 -> [3] : [ A>=0 ], cost: INF 4.55/2.06 4.55/2.06 4.55/2.06 4.55/2.06 ### Computing asymptotic complexity ### 4.55/2.06 4.55/2.06 4.55/2.06 4.55/2.06 Fully simplified ITS problem 4.55/2.06 4.55/2.06 Start location: f3 4.55/2.06 4.55/2.06 8: f3 -> f2 : A'=-1, B'=free, [ free>=1 && A>=0 ], cost: 2+A 4.55/2.06 4.55/2.06 9: f3 -> f2 : A'=-1, B'=free_1, [ 0>=1+free_1 && A>=0 ], cost: 2+A 4.55/2.06 4.55/2.06 10: f3 -> [3] : [ A>=0 ], cost: INF 4.55/2.06 4.55/2.06 4.55/2.06 4.55/2.06 Computing asymptotic complexity for rule 8 4.55/2.06 4.55/2.06 Solved the limit problem by the following transformations: 4.55/2.06 4.55/2.06 Created initial limit problem: 4.55/2.06 4.55/2.06 2+A (+), free (+/+!), 1+A (+/+!) [not solved] 4.55/2.06 4.55/2.06 4.55/2.06 4.55/2.06 removing all constraints (solved by SMT) 4.55/2.06 4.55/2.06 resulting limit problem: [solved] 4.55/2.06 4.55/2.06 4.55/2.06 4.55/2.06 applying transformation rule (C) using substitution {A==n,free==n} 4.55/2.06 4.55/2.06 resulting limit problem: 4.55/2.06 4.55/2.06 [solved] 4.55/2.06 4.55/2.06 4.55/2.06 4.55/2.06 Solution: 4.55/2.06 4.55/2.06 A / n 4.55/2.06 4.55/2.06 free / n 4.55/2.06 4.55/2.06 Resulting cost 2+n has complexity: Poly(n^1) 4.55/2.06 4.55/2.06 4.55/2.06 4.55/2.06 Found new complexity Poly(n^1). 4.55/2.06 4.55/2.06 4.55/2.06 4.55/2.06 Computing asymptotic complexity for rule 10 4.55/2.06 4.55/2.06 Resulting cost INF has complexity: Nonterm 4.55/2.06 4.55/2.06 4.55/2.06 4.55/2.06 Found new complexity Nonterm. 4.55/2.06 4.55/2.06 4.55/2.06 4.55/2.06 Obtained the following overall complexity (w.r.t. the length of the input n): 4.55/2.06 4.55/2.06 Complexity: Nonterm 4.55/2.06 4.55/2.06 Cpx degree: Nonterm 4.55/2.06 4.55/2.06 Solved cost: INF 4.55/2.06 4.55/2.06 Rule cost: INF 4.55/2.06 4.55/2.06 Rule guard: [ A>=0 ] 4.55/2.06 4.55/2.06 4.55/2.06 4.55/2.06 NO 4.55/2.06 4.55/2.06 4.55/2.06 ---------------------------------------- 4.55/2.06 4.55/2.06 (2) 4.55/2.06 BOUNDS(INF, INF) 4.69/2.56 EOF