14.05/5.62 WORST_CASE(NON_POLY, ?) 14.20/5.92 proof of /export/starexec/sandbox/benchmark/theBenchmark.koat 14.20/5.92 # AProVE Commit ID: 48fb2092695e11cc9f56e44b17a92a5f88ffb256 marcel 20180622 unpublished dirty 14.20/5.92 14.20/5.92 14.20/5.92 The runtime complexity of the given CpxIntTrs could be proven to be BOUNDS(INF, INF). 14.20/5.92 14.20/5.92 (0) CpxIntTrs 14.20/5.92 (1) Loat Proof [FINISHED, 3824 ms] 14.20/5.92 (2) BOUNDS(INF, INF) 14.20/5.92 14.20/5.92 14.20/5.92 ---------------------------------------- 14.20/5.92 14.20/5.92 (0) 14.20/5.92 Obligation: 14.20/5.92 Complexity Int TRS consisting of the following rules: 14.20/5.92 f5(A, B, C, D, E) -> Com_1(f300(A, B, C, D, E)) :|: TRUE 14.20/5.92 f4(A, B, C, D, E) -> Com_1(f300(A, B, 1 + C, D, E)) :|: A >= B 14.20/5.92 f4(A, B, C, D, E) -> Com_1(f4(1 + A, B, C, F, E)) :|: F >= 1 && B >= 1 + A 14.20/5.92 f4(A, B, C, D, E) -> Com_1(f4(1 + A, B, C, F, E)) :|: 0 >= F + 1 && B >= 1 + A 14.20/5.92 f4(A, B, C, D, E) -> Com_1(f2(A, B, C, 0, E)) :|: B >= 1 + A 14.20/5.92 f2(A, B, C, D, E) -> Com_1(f4(1 + A, B, C, F, E)) :|: F >= 1 && B >= 1 + A 14.20/5.92 f2(A, B, C, D, E) -> Com_1(f4(1 + A, B, C, F, E)) :|: 0 >= F + 1 && B >= 1 + A 14.20/5.92 f2(A, B, C, D, E) -> Com_1(f2(A, B, C, 0, E)) :|: B >= 1 + A 14.20/5.92 f300(A, B, C, D, E) -> Com_1(f1(A, B, C, D, F)) :|: C >= A 14.20/5.92 f300(A, B, C, D, E) -> Com_1(f300(A, B, 1 + C, D, E)) :|: A >= 1 + C && A >= B 14.20/5.92 f300(A, B, C, D, E) -> Com_1(f4(1 + A, B, C, F, E)) :|: F >= 1 && A >= 1 + C && B >= 1 + A 14.20/5.92 f300(A, B, C, D, E) -> Com_1(f4(1 + A, B, C, F, E)) :|: 0 >= F + 1 && A >= 1 + C && B >= 1 + A 14.20/5.92 f300(A, B, C, D, E) -> Com_1(f2(A, B, C, 0, E)) :|: A >= 1 + C && B >= 1 + A 14.20/5.92 14.20/5.92 The start-symbols are:[f5_5] 14.20/5.92 14.20/5.92 14.20/5.92 ---------------------------------------- 14.20/5.92 14.20/5.92 (1) Loat Proof (FINISHED) 14.20/5.92 14.20/5.92 14.20/5.92 ### Pre-processing the ITS problem ### 14.20/5.92 14.20/5.92 14.20/5.92 14.20/5.92 Initial linear ITS problem 14.20/5.92 14.20/5.92 Start location: f5 14.20/5.92 14.20/5.92 0: f5 -> f300 : [], cost: 1 14.20/5.92 14.20/5.92 1: f4 -> f300 : C'=1+C, [ A>=B ], cost: 1 14.20/5.92 14.20/5.92 2: f4 -> f4 : A'=1+A, D'=free, [ free>=1 && B>=1+A ], cost: 1 14.20/5.92 14.20/5.92 3: f4 -> f4 : A'=1+A, D'=free_1, [ 0>=1+free_1 && B>=1+A ], cost: 1 14.20/5.92 14.20/5.92 4: f4 -> f2 : D'=0, [ B>=1+A ], cost: 1 14.20/5.92 14.20/5.92 5: f2 -> f4 : A'=1+A, D'=free_2, [ free_2>=1 && B>=1+A ], cost: 1 14.20/5.92 14.20/5.92 6: f2 -> f4 : A'=1+A, D'=free_3, [ 0>=1+free_3 && B>=1+A ], cost: 1 14.20/5.92 14.20/5.92 7: f2 -> f2 : D'=0, [ B>=1+A ], cost: 1 14.20/5.92 14.20/5.92 8: f300 -> f1 : E'=free_4, [ C>=A ], cost: 1 14.20/5.92 14.20/5.92 9: f300 -> f300 : C'=1+C, [ A>=1+C && A>=B ], cost: 1 14.20/5.92 14.20/5.92 10: f300 -> f4 : A'=1+A, D'=free_5, [ free_5>=1 && A>=1+C && B>=1+A ], cost: 1 14.20/5.92 14.20/5.92 11: f300 -> f4 : A'=1+A, D'=free_6, [ 0>=1+free_6 && A>=1+C && B>=1+A ], cost: 1 14.20/5.92 14.20/5.92 12: f300 -> f2 : D'=0, [ A>=1+C && B>=1+A ], cost: 1 14.20/5.92 14.20/5.92 14.20/5.92 14.20/5.92 Removed unreachable and leaf rules: 14.20/5.92 14.20/5.92 Start location: f5 14.20/5.92 14.20/5.92 0: f5 -> f300 : [], cost: 1 14.20/5.92 14.20/5.92 1: f4 -> f300 : C'=1+C, [ A>=B ], cost: 1 14.20/5.92 14.20/5.92 2: f4 -> f4 : A'=1+A, D'=free, [ free>=1 && B>=1+A ], cost: 1 14.20/5.92 14.20/5.92 3: f4 -> f4 : A'=1+A, D'=free_1, [ 0>=1+free_1 && B>=1+A ], cost: 1 14.20/5.92 14.20/5.92 4: f4 -> f2 : D'=0, [ B>=1+A ], cost: 1 14.20/5.92 14.20/5.92 5: f2 -> f4 : A'=1+A, D'=free_2, [ free_2>=1 && B>=1+A ], cost: 1 14.20/5.92 14.20/5.92 6: f2 -> f4 : A'=1+A, D'=free_3, [ 0>=1+free_3 && B>=1+A ], cost: 1 14.20/5.92 14.20/5.92 7: f2 -> f2 : D'=0, [ B>=1+A ], cost: 1 14.20/5.92 14.20/5.92 9: f300 -> f300 : C'=1+C, [ A>=1+C && A>=B ], cost: 1 14.20/5.92 14.20/5.92 10: f300 -> f4 : A'=1+A, D'=free_5, [ free_5>=1 && A>=1+C && B>=1+A ], cost: 1 14.20/5.92 14.20/5.92 11: f300 -> f4 : A'=1+A, D'=free_6, [ 0>=1+free_6 && A>=1+C && B>=1+A ], cost: 1 14.20/5.92 14.20/5.92 12: f300 -> f2 : D'=0, [ A>=1+C && B>=1+A ], cost: 1 14.20/5.92 14.20/5.92 14.20/5.92 14.20/5.92 ### Simplification by acceleration and chaining ### 14.20/5.92 14.20/5.92 14.20/5.92 14.20/5.92 Accelerating simple loops of location 1. 14.20/5.92 14.20/5.92 Accelerating the following rules: 14.20/5.92 14.20/5.92 2: f4 -> f4 : A'=1+A, D'=free, [ free>=1 && B>=1+A ], cost: 1 14.20/5.92 14.20/5.92 3: f4 -> f4 : A'=1+A, D'=free_1, [ 0>=1+free_1 && B>=1+A ], cost: 1 14.20/5.92 14.20/5.92 14.20/5.92 14.20/5.92 Accelerated rule 2 with metering function -A+B, yielding the new rule 13. 14.20/5.92 14.20/5.92 Accelerated rule 3 with metering function -A+B, yielding the new rule 14. 14.20/5.92 14.20/5.92 Removing the simple loops: 2 3. 14.20/5.92 14.20/5.92 14.20/5.92 14.20/5.92 Accelerating simple loops of location 2. 14.20/5.92 14.20/5.92 Accelerating the following rules: 14.20/5.92 14.20/5.92 7: f2 -> f2 : D'=0, [ B>=1+A ], cost: 1 14.20/5.92 14.20/5.92 14.20/5.92 14.20/5.92 Accelerated rule 7 with NONTERM, yielding the new rule 15. 14.20/5.92 14.20/5.92 Removing the simple loops: 7. 14.20/5.92 14.20/5.92 14.20/5.92 14.20/5.92 Accelerating simple loops of location 3. 14.20/5.92 14.20/5.92 Accelerating the following rules: 14.20/5.92 14.20/5.92 9: f300 -> f300 : C'=1+C, [ A>=1+C && A>=B ], cost: 1 14.20/5.92 14.20/5.92 14.20/5.92 14.20/5.92 Accelerated rule 9 with metering function -C+A, yielding the new rule 16. 14.20/5.92 14.20/5.92 Removing the simple loops: 9. 14.20/5.92 14.20/5.92 14.20/5.92 14.20/5.92 Accelerated all simple loops using metering functions (where possible): 14.20/5.92 14.20/5.92 Start location: f5 14.20/5.92 14.20/5.92 0: f5 -> f300 : [], cost: 1 14.20/5.92 14.20/5.92 1: f4 -> f300 : C'=1+C, [ A>=B ], cost: 1 14.20/5.92 14.20/5.92 4: f4 -> f2 : D'=0, [ B>=1+A ], cost: 1 14.20/5.92 14.20/5.92 13: f4 -> f4 : A'=B, D'=free, [ free>=1 && B>=1+A ], cost: -A+B 14.20/5.92 14.20/5.92 14: f4 -> f4 : A'=B, D'=free_1, [ 0>=1+free_1 && B>=1+A ], cost: -A+B 14.20/5.92 14.20/5.92 5: f2 -> f4 : A'=1+A, D'=free_2, [ free_2>=1 && B>=1+A ], cost: 1 14.20/5.92 14.20/5.92 6: f2 -> f4 : A'=1+A, D'=free_3, [ 0>=1+free_3 && B>=1+A ], cost: 1 14.20/5.92 14.20/5.92 15: f2 -> [6] : [ B>=1+A ], cost: INF 14.20/5.92 14.20/5.92 10: f300 -> f4 : A'=1+A, D'=free_5, [ free_5>=1 && A>=1+C && B>=1+A ], cost: 1 14.20/5.92 14.20/5.92 11: f300 -> f4 : A'=1+A, D'=free_6, [ 0>=1+free_6 && A>=1+C && B>=1+A ], cost: 1 14.20/5.92 14.20/5.92 12: f300 -> f2 : D'=0, [ A>=1+C && B>=1+A ], cost: 1 14.20/5.92 14.20/5.92 16: f300 -> f300 : C'=A, [ A>=1+C && A>=B ], cost: -C+A 14.20/5.92 14.20/5.92 14.20/5.92 14.20/5.92 Chained accelerated rules (with incoming rules): 14.20/5.92 14.20/5.92 Start location: f5 14.20/5.92 14.20/5.92 0: f5 -> f300 : [], cost: 1 14.20/5.92 14.20/5.92 27: f5 -> f300 : C'=A, [ A>=1+C && A>=B ], cost: 1-C+A 14.20/5.92 14.20/5.92 1: f4 -> f300 : C'=1+C, [ A>=B ], cost: 1 14.20/5.92 14.20/5.92 4: f4 -> f2 : D'=0, [ B>=1+A ], cost: 1 14.20/5.92 14.20/5.92 25: f4 -> [6] : D'=0, [ B>=1+A ], cost: INF 14.20/5.92 14.20/5.92 28: f4 -> f300 : C'=A, [ A>=B && A>=2+C ], cost: -C+A 14.20/5.92 14.20/5.92 5: f2 -> f4 : A'=1+A, D'=free_2, [ free_2>=1 && B>=1+A ], cost: 1 14.20/5.92 14.20/5.92 6: f2 -> f4 : A'=1+A, D'=free_3, [ 0>=1+free_3 && B>=1+A ], cost: 1 14.20/5.92 14.20/5.92 17: f2 -> f4 : A'=B, D'=free, [ free>=1 && B>=2+A ], cost: -A+B 14.20/5.92 14.20/5.92 18: f2 -> f4 : A'=B, D'=free, [ free>=1 && B>=2+A ], cost: -A+B 14.20/5.92 14.20/5.92 21: f2 -> f4 : A'=B, D'=free_1, [ 0>=1+free_1 && B>=2+A ], cost: -A+B 14.20/5.92 14.20/5.92 22: f2 -> f4 : A'=B, D'=free_1, [ 0>=1+free_1 && B>=2+A ], cost: -A+B 14.20/5.92 14.20/5.92 10: f300 -> f4 : A'=1+A, D'=free_5, [ free_5>=1 && A>=1+C && B>=1+A ], cost: 1 14.20/5.92 14.20/5.92 11: f300 -> f4 : A'=1+A, D'=free_6, [ 0>=1+free_6 && A>=1+C && B>=1+A ], cost: 1 14.20/5.92 14.20/5.92 12: f300 -> f2 : D'=0, [ A>=1+C && B>=1+A ], cost: 1 14.20/5.92 14.20/5.92 19: f300 -> f4 : A'=B, D'=free, [ A>=1+C && free>=1 && B>=2+A ], cost: -A+B 14.20/5.92 14.20/5.92 20: f300 -> f4 : A'=B, D'=free, [ A>=1+C && free>=1 && B>=2+A ], cost: -A+B 14.20/5.92 14.20/5.92 23: f300 -> f4 : A'=B, D'=free_1, [ A>=1+C && 0>=1+free_1 && B>=2+A ], cost: -A+B 14.20/5.92 14.20/5.92 24: f300 -> f4 : A'=B, D'=free_1, [ A>=1+C && 0>=1+free_1 && B>=2+A ], cost: -A+B 14.20/5.92 14.20/5.92 26: f300 -> [6] : D'=0, [ A>=1+C && B>=1+A ], cost: INF 14.20/5.92 14.20/5.92 14.20/5.92 14.20/5.92 Eliminated location f300 (as a last resort): 14.20/5.92 14.20/5.92 Start location: f5 14.20/5.92 14.20/5.92 29: f5 -> f4 : A'=1+A, D'=free_5, [ free_5>=1 && A>=1+C && B>=1+A ], cost: 2 14.20/5.92 14.20/5.92 30: f5 -> f4 : A'=1+A, D'=free_6, [ 0>=1+free_6 && A>=1+C && B>=1+A ], cost: 2 14.20/5.92 14.20/5.92 31: f5 -> f2 : D'=0, [ A>=1+C && B>=1+A ], cost: 2 14.20/5.92 14.20/5.92 32: f5 -> f4 : A'=B, D'=free, [ A>=1+C && free>=1 && B>=2+A ], cost: 1-A+B 14.20/5.92 14.20/5.92 33: f5 -> f4 : A'=B, D'=free, [ A>=1+C && free>=1 && B>=2+A ], cost: 1-A+B 14.20/5.92 14.20/5.92 34: f5 -> f4 : A'=B, D'=free_1, [ A>=1+C && 0>=1+free_1 && B>=2+A ], cost: 1-A+B 14.20/5.92 14.20/5.92 35: f5 -> f4 : A'=B, D'=free_1, [ A>=1+C && 0>=1+free_1 && B>=2+A ], cost: 1-A+B 14.20/5.92 14.20/5.92 36: f5 -> [6] : D'=0, [ A>=1+C && B>=1+A ], cost: INF 14.20/5.92 14.20/5.92 37: f5 -> [8] : [ A>=1+C && A>=B ], cost: 1-C+A 14.20/5.92 14.20/5.92 4: f4 -> f2 : D'=0, [ B>=1+A ], cost: 1 14.20/5.92 14.20/5.92 25: f4 -> [6] : D'=0, [ B>=1+A ], cost: INF 14.20/5.92 14.20/5.92 38: f4 -> [8] : [ A>=B && A>=2+C ], cost: -C+A 14.20/5.92 14.20/5.92 5: f2 -> f4 : A'=1+A, D'=free_2, [ free_2>=1 && B>=1+A ], cost: 1 14.20/5.92 14.20/5.92 6: f2 -> f4 : A'=1+A, D'=free_3, [ 0>=1+free_3 && B>=1+A ], cost: 1 14.20/5.92 14.20/5.92 17: f2 -> f4 : A'=B, D'=free, [ free>=1 && B>=2+A ], cost: -A+B 14.20/5.92 14.20/5.92 18: f2 -> f4 : A'=B, D'=free, [ free>=1 && B>=2+A ], cost: -A+B 14.20/5.92 14.20/5.92 21: f2 -> f4 : A'=B, D'=free_1, [ 0>=1+free_1 && B>=2+A ], cost: -A+B 14.20/5.92 14.20/5.92 22: f2 -> f4 : A'=B, D'=free_1, [ 0>=1+free_1 && B>=2+A ], cost: -A+B 14.20/5.92 14.20/5.92 14.20/5.92 14.20/5.92 Eliminated location f4 (as a last resort): 14.20/5.92 14.20/5.92 Start location: f5 14.20/5.92 14.20/5.92 31: f5 -> f2 : D'=0, [ A>=1+C && B>=1+A ], cost: 2 14.20/5.92 14.20/5.92 36: f5 -> [6] : D'=0, [ A>=1+C && B>=1+A ], cost: INF 14.20/5.92 14.20/5.92 37: f5 -> [8] : [ A>=1+C && A>=B ], cost: 1-C+A 14.20/5.92 14.20/5.92 47: f5 -> f2 : A'=1+A, D'=0, [ free_5>=1 && A>=1+C && B>=2+A ], cost: 3 14.20/5.92 14.20/5.92 48: f5 -> [6] : A'=1+A, D'=0, [ free_5>=1 && A>=1+C && B>=2+A ], cost: INF 14.20/5.92 14.20/5.92 49: f5 -> [8] : A'=1+A, D'=free_5, [ free_5>=1 && A>=1+C && B>=1+A && 1+A>=B ], cost: 3-C+A 14.20/5.92 14.20/5.92 50: f5 -> f2 : A'=1+A, D'=0, [ 0>=1+free_6 && A>=1+C && B>=2+A ], cost: 3 14.20/5.92 14.20/5.92 51: f5 -> [6] : A'=1+A, D'=0, [ 0>=1+free_6 && A>=1+C && B>=2+A ], cost: INF 14.20/5.92 14.20/5.92 52: f5 -> [8] : A'=1+A, D'=free_6, [ 0>=1+free_6 && A>=1+C && B>=1+A && 1+A>=B ], cost: 3-C+A 14.20/5.92 14.20/5.92 53: f5 -> [8] : A'=B, D'=free, [ A>=1+C && free>=1 && B>=2+A && B>=2+C ], cost: 1-C-A+2*B 14.20/5.92 14.20/5.92 54: f5 -> [8] : A'=B, D'=free_1, [ A>=1+C && 0>=1+free_1 && B>=2+A && B>=2+C ], cost: 1-C-A+2*B 14.20/5.92 14.20/5.92 57: f5 -> [9] : [ A>=1+C && free>=1 && B>=2+A ], cost: 1-A+B 14.20/5.92 14.20/5.92 58: f5 -> [9] : [ A>=1+C && 0>=1+free_1 && B>=2+A ], cost: 1-A+B 14.20/5.92 14.20/5.92 39: f2 -> f2 : A'=1+A, D'=0, [ free_2>=1 && B>=2+A ], cost: 2 14.20/5.92 14.20/5.92 40: f2 -> [6] : A'=1+A, D'=0, [ free_2>=1 && B>=2+A ], cost: INF 14.20/5.92 14.20/5.92 41: f2 -> [8] : A'=1+A, D'=free_2, [ free_2>=1 && B>=1+A && 1+A>=B && 1+A>=2+C ], cost: 2-C+A 14.20/5.92 14.20/5.92 42: f2 -> f2 : A'=1+A, D'=0, [ 0>=1+free_3 && B>=2+A ], cost: 2 14.20/5.92 14.20/5.92 43: f2 -> [6] : A'=1+A, D'=0, [ 0>=1+free_3 && B>=2+A ], cost: INF 14.20/5.92 14.20/5.92 44: f2 -> [8] : A'=1+A, D'=free_3, [ 0>=1+free_3 && B>=1+A && 1+A>=B && 1+A>=2+C ], cost: 2-C+A 14.20/5.92 14.20/5.92 45: f2 -> [8] : A'=B, D'=free, [ free>=1 && B>=2+A && B>=2+C ], cost: -C-A+2*B 14.20/5.92 14.20/5.92 46: f2 -> [8] : A'=B, D'=free_1, [ 0>=1+free_1 && B>=2+A && B>=2+C ], cost: -C-A+2*B 14.20/5.92 14.20/5.92 55: f2 -> [9] : [ free>=1 && B>=2+A ], cost: -A+B 14.20/5.92 14.20/5.92 56: f2 -> [9] : [ 0>=1+free_1 && B>=2+A ], cost: -A+B 14.20/5.92 14.20/5.92 14.20/5.92 14.20/5.92 Accelerating simple loops of location 2. 14.20/5.92 14.20/5.92 Simplified some of the simple loops (and removed duplicate rules). 14.20/5.92 14.20/5.92 Accelerating the following rules: 14.20/5.92 14.20/5.92 42: f2 -> f2 : A'=1+A, D'=0, [ B>=2+A ], cost: 2 14.20/5.92 14.20/5.92 14.20/5.92 14.20/5.92 Accelerated rule 42 with metering function -1-A+B, yielding the new rule 59. 14.20/5.92 14.20/5.92 Removing the simple loops: 42. 14.20/5.92 14.20/5.92 14.20/5.92 14.20/5.92 Accelerated all simple loops using metering functions (where possible): 14.20/5.92 14.20/5.92 Start location: f5 14.20/5.92 14.20/5.92 31: f5 -> f2 : D'=0, [ A>=1+C && B>=1+A ], cost: 2 14.20/5.92 14.20/5.92 36: f5 -> [6] : D'=0, [ A>=1+C && B>=1+A ], cost: INF 14.20/5.92 14.20/5.92 37: f5 -> [8] : [ A>=1+C && A>=B ], cost: 1-C+A 14.20/5.92 14.20/5.92 47: f5 -> f2 : A'=1+A, D'=0, [ free_5>=1 && A>=1+C && B>=2+A ], cost: 3 14.20/5.92 14.20/5.92 48: f5 -> [6] : A'=1+A, D'=0, [ free_5>=1 && A>=1+C && B>=2+A ], cost: INF 14.20/5.92 14.20/5.92 49: f5 -> [8] : A'=1+A, D'=free_5, [ free_5>=1 && A>=1+C && B>=1+A && 1+A>=B ], cost: 3-C+A 14.20/5.92 14.20/5.92 50: f5 -> f2 : A'=1+A, D'=0, [ 0>=1+free_6 && A>=1+C && B>=2+A ], cost: 3 14.20/5.92 14.20/5.92 51: f5 -> [6] : A'=1+A, D'=0, [ 0>=1+free_6 && A>=1+C && B>=2+A ], cost: INF 14.20/5.92 14.20/5.92 52: f5 -> [8] : A'=1+A, D'=free_6, [ 0>=1+free_6 && A>=1+C && B>=1+A && 1+A>=B ], cost: 3-C+A 14.20/5.92 14.20/5.92 53: f5 -> [8] : A'=B, D'=free, [ A>=1+C && free>=1 && B>=2+A && B>=2+C ], cost: 1-C-A+2*B 14.20/5.92 14.20/5.92 54: f5 -> [8] : A'=B, D'=free_1, [ A>=1+C && 0>=1+free_1 && B>=2+A && B>=2+C ], cost: 1-C-A+2*B 14.20/5.92 14.20/5.92 57: f5 -> [9] : [ A>=1+C && free>=1 && B>=2+A ], cost: 1-A+B 14.20/5.92 14.20/5.92 58: f5 -> [9] : [ A>=1+C && 0>=1+free_1 && B>=2+A ], cost: 1-A+B 14.20/5.92 14.20/5.92 40: f2 -> [6] : A'=1+A, D'=0, [ free_2>=1 && B>=2+A ], cost: INF 14.20/5.92 14.20/5.92 41: f2 -> [8] : A'=1+A, D'=free_2, [ free_2>=1 && B>=1+A && 1+A>=B && 1+A>=2+C ], cost: 2-C+A 14.20/5.92 14.20/5.92 43: f2 -> [6] : A'=1+A, D'=0, [ 0>=1+free_3 && B>=2+A ], cost: INF 14.20/5.92 14.20/5.92 44: f2 -> [8] : A'=1+A, D'=free_3, [ 0>=1+free_3 && B>=1+A && 1+A>=B && 1+A>=2+C ], cost: 2-C+A 14.20/5.92 14.20/5.92 45: f2 -> [8] : A'=B, D'=free, [ free>=1 && B>=2+A && B>=2+C ], cost: -C-A+2*B 14.20/5.92 14.20/5.92 46: f2 -> [8] : A'=B, D'=free_1, [ 0>=1+free_1 && B>=2+A && B>=2+C ], cost: -C-A+2*B 14.20/5.92 14.20/5.92 55: f2 -> [9] : [ free>=1 && B>=2+A ], cost: -A+B 14.20/5.92 14.20/5.92 56: f2 -> [9] : [ 0>=1+free_1 && B>=2+A ], cost: -A+B 14.20/5.92 14.20/5.92 59: f2 -> f2 : A'=-1+B, D'=0, [ B>=2+A ], cost: -2-2*A+2*B 14.20/5.92 14.20/5.92 14.20/5.92 14.20/5.92 Chained accelerated rules (with incoming rules): 14.20/5.92 14.20/5.92 Start location: f5 14.20/5.92 14.20/5.92 31: f5 -> f2 : D'=0, [ A>=1+C && B>=1+A ], cost: 2 14.20/5.92 14.20/5.92 36: f5 -> [6] : D'=0, [ A>=1+C && B>=1+A ], cost: INF 14.20/5.92 14.20/5.92 37: f5 -> [8] : [ A>=1+C && A>=B ], cost: 1-C+A 14.20/5.92 14.20/5.92 47: f5 -> f2 : A'=1+A, D'=0, [ free_5>=1 && A>=1+C && B>=2+A ], cost: 3 14.20/5.92 14.20/5.92 48: f5 -> [6] : A'=1+A, D'=0, [ free_5>=1 && A>=1+C && B>=2+A ], cost: INF 14.20/5.92 14.20/5.92 49: f5 -> [8] : A'=1+A, D'=free_5, [ free_5>=1 && A>=1+C && B>=1+A && 1+A>=B ], cost: 3-C+A 14.20/5.92 14.20/5.92 50: f5 -> f2 : A'=1+A, D'=0, [ 0>=1+free_6 && A>=1+C && B>=2+A ], cost: 3 14.20/5.92 14.20/5.92 51: f5 -> [6] : A'=1+A, D'=0, [ 0>=1+free_6 && A>=1+C && B>=2+A ], cost: INF 14.20/5.92 14.20/5.92 52: f5 -> [8] : A'=1+A, D'=free_6, [ 0>=1+free_6 && A>=1+C && B>=1+A && 1+A>=B ], cost: 3-C+A 14.20/5.92 14.20/5.92 53: f5 -> [8] : A'=B, D'=free, [ A>=1+C && free>=1 && B>=2+A && B>=2+C ], cost: 1-C-A+2*B 14.20/5.92 14.20/5.92 54: f5 -> [8] : A'=B, D'=free_1, [ A>=1+C && 0>=1+free_1 && B>=2+A && B>=2+C ], cost: 1-C-A+2*B 14.20/5.92 14.20/5.92 57: f5 -> [9] : [ A>=1+C && free>=1 && B>=2+A ], cost: 1-A+B 14.20/5.92 14.20/5.92 58: f5 -> [9] : [ A>=1+C && 0>=1+free_1 && B>=2+A ], cost: 1-A+B 14.20/5.92 14.20/5.92 60: f5 -> f2 : A'=-1+B, D'=0, [ A>=1+C && B>=2+A ], cost: -2*A+2*B 14.20/5.92 14.20/5.92 61: f5 -> f2 : A'=-1+B, D'=0, [ A>=1+C && B>=3+A ], cost: -1-2*A+2*B 14.20/5.92 14.20/5.92 62: f5 -> f2 : A'=-1+B, D'=0, [ A>=1+C && B>=3+A ], cost: -1-2*A+2*B 14.20/5.92 14.20/5.92 40: f2 -> [6] : A'=1+A, D'=0, [ free_2>=1 && B>=2+A ], cost: INF 14.20/5.92 14.20/5.92 41: f2 -> [8] : A'=1+A, D'=free_2, [ free_2>=1 && B>=1+A && 1+A>=B && 1+A>=2+C ], cost: 2-C+A 14.20/5.92 14.20/5.92 43: f2 -> [6] : A'=1+A, D'=0, [ 0>=1+free_3 && B>=2+A ], cost: INF 14.20/5.92 14.20/5.92 44: f2 -> [8] : A'=1+A, D'=free_3, [ 0>=1+free_3 && B>=1+A && 1+A>=B && 1+A>=2+C ], cost: 2-C+A 14.20/5.92 14.20/5.92 45: f2 -> [8] : A'=B, D'=free, [ free>=1 && B>=2+A && B>=2+C ], cost: -C-A+2*B 14.20/5.92 14.20/5.92 46: f2 -> [8] : A'=B, D'=free_1, [ 0>=1+free_1 && B>=2+A && B>=2+C ], cost: -C-A+2*B 14.20/5.92 14.20/5.92 55: f2 -> [9] : [ free>=1 && B>=2+A ], cost: -A+B 14.20/5.92 14.20/5.92 56: f2 -> [9] : [ 0>=1+free_1 && B>=2+A ], cost: -A+B 14.20/5.92 14.20/5.92 14.20/5.92 14.20/5.92 Eliminated locations (on tree-shaped paths): 14.20/5.92 14.20/5.92 Start location: f5 14.20/5.92 14.20/5.92 36: f5 -> [6] : D'=0, [ A>=1+C && B>=1+A ], cost: INF 14.20/5.92 14.20/5.92 37: f5 -> [8] : [ A>=1+C && A>=B ], cost: 1-C+A 14.20/5.92 14.20/5.92 48: f5 -> [6] : A'=1+A, D'=0, [ free_5>=1 && A>=1+C && B>=2+A ], cost: INF 14.20/5.92 14.20/5.92 49: f5 -> [8] : A'=1+A, D'=free_5, [ free_5>=1 && A>=1+C && B>=1+A && 1+A>=B ], cost: 3-C+A 14.20/5.92 14.20/5.92 51: f5 -> [6] : A'=1+A, D'=0, [ 0>=1+free_6 && A>=1+C && B>=2+A ], cost: INF 14.20/5.92 14.20/5.92 52: f5 -> [8] : A'=1+A, D'=free_6, [ 0>=1+free_6 && A>=1+C && B>=1+A && 1+A>=B ], cost: 3-C+A 14.20/5.92 14.20/5.92 53: f5 -> [8] : A'=B, D'=free, [ A>=1+C && free>=1 && B>=2+A && B>=2+C ], cost: 1-C-A+2*B 14.20/5.92 14.20/5.92 54: f5 -> [8] : A'=B, D'=free_1, [ A>=1+C && 0>=1+free_1 && B>=2+A && B>=2+C ], cost: 1-C-A+2*B 14.20/5.92 14.20/5.92 57: f5 -> [9] : [ A>=1+C && free>=1 && B>=2+A ], cost: 1-A+B 14.20/5.92 14.20/5.92 58: f5 -> [9] : [ A>=1+C && 0>=1+free_1 && B>=2+A ], cost: 1-A+B 14.20/5.92 14.20/5.92 63: f5 -> [6] : A'=1+A, D'=0, [ A>=1+C && free_2>=1 && B>=2+A ], cost: INF 14.20/5.92 14.20/5.92 64: f5 -> [8] : A'=1+A, D'=free_2, [ A>=1+C && B>=1+A && free_2>=1 && 1+A>=B ], cost: 4-C+A 14.20/5.92 14.20/5.92 65: f5 -> [6] : A'=1+A, D'=0, [ A>=1+C && 0>=1+free_3 && B>=2+A ], cost: INF 14.20/5.92 14.20/5.92 66: f5 -> [8] : A'=1+A, D'=free_3, [ A>=1+C && B>=1+A && 0>=1+free_3 && 1+A>=B ], cost: 4-C+A 14.20/5.92 14.20/5.92 67: f5 -> [8] : A'=B, D'=free, [ A>=1+C && free>=1 && B>=2+A && B>=2+C ], cost: 2-C-A+2*B 14.20/5.92 14.20/5.92 68: f5 -> [8] : A'=B, D'=free_1, [ A>=1+C && 0>=1+free_1 && B>=2+A && B>=2+C ], cost: 2-C-A+2*B 14.20/5.92 14.20/5.92 69: f5 -> [9] : D'=0, [ A>=1+C && free>=1 && B>=2+A ], cost: 2-A+B 14.20/5.92 14.20/5.92 70: f5 -> [9] : D'=0, [ A>=1+C && 0>=1+free_1 && B>=2+A ], cost: 2-A+B 14.20/5.92 14.20/5.92 71: f5 -> [6] : A'=2+A, D'=0, [ free_5>=1 && A>=1+C && free_2>=1 && B>=3+A ], cost: INF 14.20/5.92 14.20/5.92 72: f5 -> [8] : A'=2+A, D'=free_2, [ free_5>=1 && A>=1+C && B>=2+A && free_2>=1 && 2+A>=B ], cost: 6-C+A 14.20/5.92 14.20/5.92 73: f5 -> [6] : A'=2+A, D'=0, [ free_5>=1 && A>=1+C && 0>=1+free_3 && B>=3+A ], cost: INF 14.20/5.92 14.20/5.92 74: f5 -> [8] : A'=2+A, D'=free_3, [ free_5>=1 && A>=1+C && B>=2+A && 0>=1+free_3 && 2+A>=B ], cost: 6-C+A 14.20/5.92 14.20/5.92 75: f5 -> [8] : A'=B, D'=free, [ free_5>=1 && A>=1+C && free>=1 && B>=3+A && B>=2+C ], cost: 2-C-A+2*B 14.20/5.92 14.20/5.92 76: f5 -> [8] : A'=B, D'=free_1, [ free_5>=1 && A>=1+C && 0>=1+free_1 && B>=3+A && B>=2+C ], cost: 2-C-A+2*B 14.20/5.92 14.20/5.92 77: f5 -> [9] : A'=1+A, D'=0, [ free_5>=1 && A>=1+C && free>=1 && B>=3+A ], cost: 2-A+B 14.20/5.92 14.20/5.92 78: f5 -> [9] : A'=1+A, D'=0, [ free_5>=1 && A>=1+C && 0>=1+free_1 && B>=3+A ], cost: 2-A+B 14.20/5.92 14.20/5.92 79: f5 -> [6] : A'=2+A, D'=0, [ 0>=1+free_6 && A>=1+C && free_2>=1 && B>=3+A ], cost: INF 14.20/5.92 14.20/5.92 80: f5 -> [8] : A'=2+A, D'=free_2, [ 0>=1+free_6 && A>=1+C && B>=2+A && free_2>=1 && 2+A>=B ], cost: 6-C+A 14.20/5.92 14.20/5.92 81: f5 -> [6] : A'=2+A, D'=0, [ 0>=1+free_6 && A>=1+C && 0>=1+free_3 && B>=3+A ], cost: INF 14.20/5.92 14.20/5.92 82: f5 -> [8] : A'=2+A, D'=free_3, [ 0>=1+free_6 && A>=1+C && B>=2+A && 0>=1+free_3 && 2+A>=B ], cost: 6-C+A 14.20/5.92 14.20/5.92 83: f5 -> [8] : A'=B, D'=free, [ 0>=1+free_6 && A>=1+C && free>=1 && B>=3+A && B>=2+C ], cost: 2-C-A+2*B 14.20/5.92 14.20/5.92 84: f5 -> [8] : A'=B, D'=free_1, [ 0>=1+free_6 && A>=1+C && 0>=1+free_1 && B>=3+A && B>=2+C ], cost: 2-C-A+2*B 14.20/5.92 14.20/5.92 85: f5 -> [9] : A'=1+A, D'=0, [ 0>=1+free_6 && A>=1+C && free>=1 && B>=3+A ], cost: 2-A+B 14.20/5.92 14.20/5.92 86: f5 -> [9] : A'=1+A, D'=0, [ 0>=1+free_6 && A>=1+C && 0>=1+free_1 && B>=3+A ], cost: 2-A+B 14.20/5.92 14.20/5.92 87: f5 -> [8] : A'=B, D'=free_2, [ A>=1+C && B>=2+A && free_2>=1 && B>=2+C ], cost: 1-C-2*A+3*B 14.20/5.92 14.20/5.92 88: f5 -> [8] : A'=B, D'=free_3, [ A>=1+C && B>=2+A && 0>=1+free_3 && B>=2+C ], cost: 1-C-2*A+3*B 14.20/5.92 14.20/5.92 89: f5 -> [8] : A'=B, D'=free_2, [ A>=1+C && B>=3+A && free_2>=1 && B>=2+C ], cost: -C-2*A+3*B 14.20/5.92 14.20/5.92 90: f5 -> [8] : A'=B, D'=free_3, [ A>=1+C && B>=3+A && 0>=1+free_3 && B>=2+C ], cost: -C-2*A+3*B 14.20/5.92 14.20/5.92 91: f5 -> [8] : A'=B, D'=free_2, [ A>=1+C && B>=3+A && free_2>=1 && B>=2+C ], cost: -C-2*A+3*B 14.20/5.92 14.20/5.92 92: f5 -> [8] : A'=B, D'=free_3, [ A>=1+C && B>=3+A && 0>=1+free_3 && B>=2+C ], cost: -C-2*A+3*B 14.20/5.92 14.20/5.92 93: f5 -> [11] : [ A>=1+C && B>=2+A ], cost: -2*A+2*B 14.20/5.92 14.20/5.92 94: f5 -> [11] : [ A>=1+C && B>=3+A ], cost: -1-2*A+2*B 14.20/5.92 14.20/5.92 95: f5 -> [11] : [ A>=1+C && B>=3+A ], cost: -1-2*A+2*B 14.20/5.92 14.20/5.92 14.20/5.92 14.20/5.92 Applied pruning (of leafs and parallel rules): 14.20/5.92 14.20/5.92 Start location: f5 14.20/5.92 14.20/5.92 36: f5 -> [6] : D'=0, [ A>=1+C && B>=1+A ], cost: INF 14.20/5.92 14.20/5.92 48: f5 -> [6] : A'=1+A, D'=0, [ free_5>=1 && A>=1+C && B>=2+A ], cost: INF 14.20/5.92 14.20/5.92 58: f5 -> [9] : [ A>=1+C && 0>=1+free_1 && B>=2+A ], cost: 1-A+B 14.20/5.92 14.20/5.92 63: f5 -> [6] : A'=1+A, D'=0, [ A>=1+C && free_2>=1 && B>=2+A ], cost: INF 14.20/5.92 14.20/5.92 65: f5 -> [6] : A'=1+A, D'=0, [ A>=1+C && 0>=1+free_3 && B>=2+A ], cost: INF 14.20/5.92 14.20/5.92 70: f5 -> [9] : D'=0, [ A>=1+C && 0>=1+free_1 && B>=2+A ], cost: 2-A+B 14.20/5.92 14.20/5.92 72: f5 -> [8] : A'=2+A, D'=free_2, [ free_5>=1 && A>=1+C && B>=2+A && free_2>=1 && 2+A>=B ], cost: 6-C+A 14.20/5.92 14.20/5.92 73: f5 -> [6] : A'=2+A, D'=0, [ free_5>=1 && A>=1+C && 0>=1+free_3 && B>=3+A ], cost: INF 14.20/5.92 14.20/5.92 78: f5 -> [9] : A'=1+A, D'=0, [ free_5>=1 && A>=1+C && 0>=1+free_1 && B>=3+A ], cost: 2-A+B 14.20/5.92 14.20/5.92 82: f5 -> [8] : A'=2+A, D'=free_3, [ 0>=1+free_6 && A>=1+C && B>=2+A && 0>=1+free_3 && 2+A>=B ], cost: 6-C+A 14.20/5.92 14.20/5.92 83: f5 -> [8] : A'=B, D'=free, [ 0>=1+free_6 && A>=1+C && free>=1 && B>=3+A && B>=2+C ], cost: 2-C-A+2*B 14.20/5.92 14.20/5.92 84: f5 -> [8] : A'=B, D'=free_1, [ 0>=1+free_6 && A>=1+C && 0>=1+free_1 && B>=3+A && B>=2+C ], cost: 2-C-A+2*B 14.20/5.92 14.20/5.92 85: f5 -> [9] : A'=1+A, D'=0, [ 0>=1+free_6 && A>=1+C && free>=1 && B>=3+A ], cost: 2-A+B 14.20/5.92 14.20/5.92 86: f5 -> [9] : A'=1+A, D'=0, [ 0>=1+free_6 && A>=1+C && 0>=1+free_1 && B>=3+A ], cost: 2-A+B 14.20/5.92 14.20/5.92 88: f5 -> [8] : A'=B, D'=free_3, [ A>=1+C && B>=2+A && 0>=1+free_3 && B>=2+C ], cost: 1-C-2*A+3*B 14.20/5.92 14.20/5.92 93: f5 -> [11] : [ A>=1+C && B>=2+A ], cost: -2*A+2*B 14.20/5.92 14.20/5.92 95: f5 -> [11] : [ A>=1+C && B>=3+A ], cost: -1-2*A+2*B 14.20/5.92 14.20/5.92 14.20/5.92 14.20/5.92 ### Computing asymptotic complexity ### 14.20/5.92 14.20/5.92 14.20/5.92 14.20/5.92 Fully simplified ITS problem 14.20/5.92 14.20/5.92 Start location: f5 14.20/5.92 14.20/5.92 36: f5 -> [6] : D'=0, [ A>=1+C && B>=1+A ], cost: INF 14.20/5.92 14.20/5.92 48: f5 -> [6] : A'=1+A, D'=0, [ free_5>=1 && A>=1+C && B>=2+A ], cost: INF 14.20/5.92 14.20/5.92 63: f5 -> [6] : A'=1+A, D'=0, [ A>=1+C && free_2>=1 && B>=2+A ], cost: INF 14.20/5.92 14.20/5.92 65: f5 -> [6] : A'=1+A, D'=0, [ A>=1+C && 0>=1+free_3 && B>=2+A ], cost: INF 14.20/5.92 14.20/5.92 70: f5 -> [9] : D'=0, [ A>=1+C && 0>=1+free_1 && B>=2+A ], cost: 2-A+B 14.20/5.92 14.20/5.92 72: f5 -> [8] : A'=2+A, D'=free_2, [ free_5>=1 && A>=1+C && B>=2+A && free_2>=1 && 2+A>=B ], cost: 6-C+A 14.20/5.92 14.20/5.92 73: f5 -> [6] : A'=2+A, D'=0, [ free_5>=1 && A>=1+C && 0>=1+free_3 && B>=3+A ], cost: INF 14.20/5.92 14.20/5.92 78: f5 -> [9] : A'=1+A, D'=0, [ free_5>=1 && A>=1+C && 0>=1+free_1 && B>=3+A ], cost: 2-A+B 14.20/5.92 14.20/5.92 82: f5 -> [8] : A'=2+A, D'=free_3, [ 0>=1+free_6 && A>=1+C && B>=2+A && 0>=1+free_3 && 2+A>=B ], cost: 6-C+A 14.20/5.92 14.20/5.92 83: f5 -> [8] : A'=B, D'=free, [ 0>=1+free_6 && A>=1+C && free>=1 && B>=3+A && B>=2+C ], cost: 2-C-A+2*B 14.20/5.92 14.20/5.92 84: f5 -> [8] : A'=B, D'=free_1, [ 0>=1+free_6 && A>=1+C && 0>=1+free_1 && B>=3+A && B>=2+C ], cost: 2-C-A+2*B 14.20/5.92 14.20/5.92 85: f5 -> [9] : A'=1+A, D'=0, [ 0>=1+free_6 && A>=1+C && free>=1 && B>=3+A ], cost: 2-A+B 14.20/5.92 14.20/5.92 86: f5 -> [9] : A'=1+A, D'=0, [ 0>=1+free_6 && A>=1+C && 0>=1+free_1 && B>=3+A ], cost: 2-A+B 14.20/5.92 14.20/5.92 88: f5 -> [8] : A'=B, D'=free_3, [ A>=1+C && B>=2+A && 0>=1+free_3 && B>=2+C ], cost: 1-C-2*A+3*B 14.20/5.92 14.20/5.92 93: f5 -> [11] : [ A>=1+C && B>=2+A ], cost: -2*A+2*B 14.20/5.92 14.20/5.92 95: f5 -> [11] : [ A>=1+C && B>=3+A ], cost: -1-2*A+2*B 14.20/5.92 14.20/5.92 14.20/5.92 14.20/5.92 Computing asymptotic complexity for rule 36 14.20/5.92 14.20/5.92 Resulting cost INF has complexity: Nonterm 14.20/5.92 14.20/5.92 14.20/5.92 14.20/5.92 Found new complexity Nonterm. 14.20/5.92 14.20/5.92 14.20/5.92 14.20/5.92 Obtained the following overall complexity (w.r.t. the length of the input n): 14.20/5.92 14.20/5.92 Complexity: Nonterm 14.20/5.92 14.20/5.92 Cpx degree: Nonterm 14.20/5.92 14.20/5.92 Solved cost: INF 14.20/5.92 14.20/5.92 Rule cost: INF 14.20/5.92 14.20/5.92 Rule guard: [ A>=1+C && B>=1+A ] 14.20/5.92 14.20/5.92 14.20/5.92 14.20/5.92 NO 14.20/5.92 14.20/5.92 14.20/5.92 ---------------------------------------- 14.20/5.92 14.20/5.92 (2) 14.20/5.92 BOUNDS(INF, INF) 14.21/6.04 EOF