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