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