7.64/3.98 MAYBE 7.66/3.99 proof of /export/starexec/sandbox/benchmark/theBenchmark.koat 7.66/3.99 # AProVE Commit ID: 48fb2092695e11cc9f56e44b17a92a5f88ffb256 marcel 20180622 unpublished dirty 7.66/3.99 7.66/3.99 7.66/3.99 The runtime complexity of the given CpxIntTrs could be proven to be BOUNDS(1, INF). 7.66/3.99 7.66/3.99 (0) CpxIntTrs 7.66/3.99 (1) Loat Proof [FINISHED, 1728 ms] 7.66/3.99 (2) BOUNDS(1, INF) 7.66/3.99 7.66/3.99 7.66/3.99 ---------------------------------------- 7.66/3.99 7.66/3.99 (0) 7.66/3.99 Obligation: 7.66/3.99 Complexity Int TRS consisting of the following rules: 7.66/3.99 evalfstart(A, B, C, D) -> Com_1(evalfentryin(A, B, C, D)) :|: TRUE 7.66/3.99 evalfentryin(A, B, C, D) -> Com_1(evalfbb7in(0, B, C, D)) :|: TRUE 7.66/3.99 evalfbb7in(A, B, C, D) -> Com_1(evalfbb5in(A, B, 0, D)) :|: B * B * B >= 0 && 0 >= B * B * B && 0 >= 1 + A 7.66/3.99 evalfbb7in(A, B, C, D) -> Com_1(evalfbb5in(A, B, 0, D)) :|: B * B * B >= 1 && E >= 0 && B * B * B >= 2 * E && 1 + 2 * E >= B * B * B && E >= 1 + A 7.66/3.99 evalfbb7in(A, B, C, D) -> Com_1(evalfbb5in(A, B, 0, D)) :|: 0 >= B * B * B + 1 && 0 >= E && E >= 1 + A && 2 * E >= B * B * B && 1 + B * B * B >= 2 * E 7.66/3.99 evalfbb7in(A, B, C, D) -> Com_1(evalfreturnin(A, B, C, D)) :|: B * B * B >= 0 && 0 >= B * B * B && A >= 0 7.66/3.99 evalfbb7in(A, B, C, D) -> Com_1(evalfreturnin(A, B, C, D)) :|: B * B * B >= 1 && E >= 0 && B * B * B >= 2 * E && 1 + 2 * E >= B * B * B && A >= E 7.66/3.99 evalfbb7in(A, B, C, D) -> Com_1(evalfreturnin(A, B, C, D)) :|: 0 >= B * B * B + 1 && 0 >= E && A >= E && 2 * E >= B * B * B && 1 + B * B * B >= 2 * E 7.66/3.99 evalfbb5in(A, B, C, D) -> Com_1(evalfbb3in(A, B, C, 0)) :|: B >= 1 + C 7.66/3.99 evalfbb5in(A, B, C, D) -> Com_1(evalfbb6in(A, B, C, D)) :|: C >= B 7.66/3.99 evalfbb3in(A, B, C, D) -> Com_1(evalfbb2in(A, B, C, D)) :|: C >= 1 + D 7.66/3.99 evalfbb3in(A, B, C, D) -> Com_1(evalfbb4in(A, B, C, D)) :|: D >= C 7.66/3.99 evalfbb2in(A, B, C, D) -> Com_1(evalfbb3in(A, B, C, D + 1)) :|: TRUE 7.66/3.99 evalfbb4in(A, B, C, D) -> Com_1(evalfbb5in(A, B, C + 1, D)) :|: TRUE 7.66/3.99 evalfbb6in(A, B, C, D) -> Com_1(evalfbb7in(A + 1, B, C, D)) :|: TRUE 7.66/3.99 evalfreturnin(A, B, C, D) -> Com_1(evalfstop(A, B, C, D)) :|: TRUE 7.66/3.99 7.66/3.99 The start-symbols are:[evalfstart_4] 7.66/3.99 7.66/3.99 7.66/3.99 ---------------------------------------- 7.66/3.99 7.66/3.99 (1) Loat Proof (FINISHED) 7.66/3.99 7.66/3.99 7.66/3.99 ### Pre-processing the ITS problem ### 7.66/3.99 7.66/3.99 7.66/3.99 7.66/3.99 Initial linear ITS problem 7.66/3.99 7.66/3.99 Start location: evalfstart 7.66/3.99 7.66/3.99 0: evalfstart -> evalfentryin : [], cost: 1 7.66/3.99 7.66/3.99 1: evalfentryin -> evalfbb7in : A'=0, [], cost: 1 7.66/3.99 7.66/3.99 2: evalfbb7in -> evalfbb5in : C'=0, [ B^3>=0 && 0>=B^3 && 0>=1+A ], cost: 1 7.66/3.99 7.66/3.99 3: evalfbb7in -> evalfbb5in : C'=0, [ B^3>=1 && free>=0 && B^3>=2*free && 1+2*free>=B^3 && free>=1+A ], cost: 1 7.66/3.99 7.66/3.99 4: evalfbb7in -> evalfbb5in : C'=0, [ 0>=1+B^3 && 0>=free_1 && free_1>=1+A && 2*free_1>=B^3 && 1+B^3>=2*free_1 ], cost: 1 7.66/3.99 7.66/3.99 5: evalfbb7in -> evalfreturnin : [ B^3>=0 && 0>=B^3 && A>=0 ], cost: 1 7.66/3.99 7.66/3.99 6: evalfbb7in -> evalfreturnin : [ B^3>=1 && free_2>=0 && B^3>=2*free_2 && 1+2*free_2>=B^3 && A>=free_2 ], cost: 1 7.66/3.99 7.66/3.99 7: evalfbb7in -> evalfreturnin : [ 0>=1+B^3 && 0>=free_3 && A>=free_3 && 2*free_3>=B^3 && 1+B^3>=2*free_3 ], cost: 1 7.66/3.99 7.66/3.99 8: evalfbb5in -> evalfbb3in : D'=0, [ B>=1+C ], cost: 1 7.66/3.99 7.66/3.99 9: evalfbb5in -> evalfbb6in : [ C>=B ], cost: 1 7.66/3.99 7.66/3.99 10: evalfbb3in -> evalfbb2in : [ C>=1+D ], cost: 1 7.66/3.99 7.66/3.99 11: evalfbb3in -> evalfbb4in : [ D>=C ], cost: 1 7.66/3.99 7.66/3.99 12: evalfbb2in -> evalfbb3in : D'=1+D, [], cost: 1 7.66/3.99 7.66/3.99 13: evalfbb4in -> evalfbb5in : C'=1+C, [], cost: 1 7.66/3.99 7.66/3.99 14: evalfbb6in -> evalfbb7in : A'=1+A, [], cost: 1 7.66/3.99 7.66/3.99 15: evalfreturnin -> evalfstop : [], cost: 1 7.66/3.99 7.66/3.99 7.66/3.99 7.66/3.99 Removed unreachable and leaf rules: 7.66/3.99 7.66/3.99 Start location: evalfstart 7.66/3.99 7.66/3.99 0: evalfstart -> evalfentryin : [], cost: 1 7.66/3.99 7.66/3.99 1: evalfentryin -> evalfbb7in : A'=0, [], cost: 1 7.66/3.99 7.66/3.99 2: evalfbb7in -> evalfbb5in : C'=0, [ B^3>=0 && 0>=B^3 && 0>=1+A ], cost: 1 7.66/3.99 7.66/3.99 3: evalfbb7in -> evalfbb5in : C'=0, [ B^3>=1 && free>=0 && B^3>=2*free && 1+2*free>=B^3 && free>=1+A ], cost: 1 7.66/3.99 7.66/3.99 4: evalfbb7in -> evalfbb5in : C'=0, [ 0>=1+B^3 && 0>=free_1 && free_1>=1+A && 2*free_1>=B^3 && 1+B^3>=2*free_1 ], cost: 1 7.66/3.99 7.66/3.99 8: evalfbb5in -> evalfbb3in : D'=0, [ B>=1+C ], cost: 1 7.66/3.99 7.66/3.99 9: evalfbb5in -> evalfbb6in : [ C>=B ], cost: 1 7.66/3.99 7.66/3.99 10: evalfbb3in -> evalfbb2in : [ C>=1+D ], cost: 1 7.66/3.99 7.66/3.99 11: evalfbb3in -> evalfbb4in : [ D>=C ], cost: 1 7.66/3.99 7.66/3.99 12: evalfbb2in -> evalfbb3in : D'=1+D, [], cost: 1 7.66/3.99 7.66/3.99 13: evalfbb4in -> evalfbb5in : C'=1+C, [], cost: 1 7.66/3.99 7.66/3.99 14: evalfbb6in -> evalfbb7in : A'=1+A, [], cost: 1 7.66/3.99 7.66/3.99 7.66/3.99 7.66/3.99 Simplified all rules, resulting in: 7.66/3.99 7.66/3.99 Start location: evalfstart 7.66/3.99 7.66/3.99 0: evalfstart -> evalfentryin : [], cost: 1 7.66/3.99 7.66/3.99 1: evalfentryin -> evalfbb7in : A'=0, [], cost: 1 7.66/3.99 7.66/3.99 2: evalfbb7in -> evalfbb5in : C'=0, [ -B^3==0 && 0>=1+A ], cost: 1 7.66/3.99 7.66/3.99 3: evalfbb7in -> evalfbb5in : C'=0, [ B^3>=1 && free>=0 && B^3>=2*free && 1+2*free>=B^3 && free>=1+A ], cost: 1 7.66/3.99 7.66/3.99 4: evalfbb7in -> evalfbb5in : C'=0, [ 0>=1+B^3 && 0>=free_1 && free_1>=1+A && 2*free_1>=B^3 && 1+B^3>=2*free_1 ], cost: 1 7.66/3.99 7.66/3.99 8: evalfbb5in -> evalfbb3in : D'=0, [ B>=1+C ], cost: 1 7.66/3.99 7.66/3.99 9: evalfbb5in -> evalfbb6in : [ C>=B ], cost: 1 7.66/3.99 7.66/3.99 10: evalfbb3in -> evalfbb2in : [ C>=1+D ], cost: 1 7.66/3.99 7.66/3.99 11: evalfbb3in -> evalfbb4in : [ D>=C ], cost: 1 7.66/3.99 7.66/3.99 12: evalfbb2in -> evalfbb3in : D'=1+D, [], cost: 1 7.66/3.99 7.66/3.99 13: evalfbb4in -> evalfbb5in : C'=1+C, [], cost: 1 7.66/3.99 7.66/3.99 14: evalfbb6in -> evalfbb7in : A'=1+A, [], cost: 1 7.66/3.99 7.66/3.99 7.66/3.99 7.66/3.99 ### Simplification by acceleration and chaining ### 7.66/3.99 7.66/3.99 7.66/3.99 7.66/3.99 Eliminated locations (on linear paths): 7.66/3.99 7.66/3.99 Start location: evalfstart 7.66/3.99 7.66/3.99 16: evalfstart -> evalfbb7in : A'=0, [], cost: 2 7.66/3.99 7.66/3.99 2: evalfbb7in -> evalfbb5in : C'=0, [ -B^3==0 && 0>=1+A ], cost: 1 7.66/3.99 7.66/3.99 3: evalfbb7in -> evalfbb5in : C'=0, [ B^3>=1 && free>=0 && B^3>=2*free && 1+2*free>=B^3 && free>=1+A ], cost: 1 7.66/3.99 7.66/3.99 4: evalfbb7in -> evalfbb5in : C'=0, [ 0>=1+B^3 && 0>=free_1 && free_1>=1+A && 2*free_1>=B^3 && 1+B^3>=2*free_1 ], cost: 1 7.66/3.99 7.66/3.99 8: evalfbb5in -> evalfbb3in : D'=0, [ B>=1+C ], cost: 1 7.66/3.99 7.66/3.99 17: evalfbb5in -> evalfbb7in : A'=1+A, [ C>=B ], cost: 2 7.66/3.99 7.66/3.99 18: evalfbb3in -> evalfbb3in : D'=1+D, [ C>=1+D ], cost: 2 7.66/3.99 7.66/3.99 19: evalfbb3in -> evalfbb5in : C'=1+C, [ D>=C ], cost: 2 7.66/3.99 7.66/3.99 7.66/3.99 7.66/3.99 Accelerating simple loops of location 4. 7.66/3.99 7.66/3.99 Accelerating the following rules: 7.66/3.99 7.66/3.99 18: evalfbb3in -> evalfbb3in : D'=1+D, [ C>=1+D ], cost: 2 7.66/3.99 7.66/3.99 7.66/3.99 7.66/3.99 Accelerated rule 18 with metering function C-D, yielding the new rule 20. 7.66/3.99 7.66/3.99 Removing the simple loops: 18. 7.66/3.99 7.66/3.99 7.66/3.99 7.66/3.99 Accelerated all simple loops using metering functions (where possible): 7.66/3.99 7.66/3.99 Start location: evalfstart 7.66/3.99 7.66/3.99 16: evalfstart -> evalfbb7in : A'=0, [], cost: 2 7.66/3.99 7.66/3.99 2: evalfbb7in -> evalfbb5in : C'=0, [ -B^3==0 && 0>=1+A ], cost: 1 7.66/3.99 7.66/3.99 3: evalfbb7in -> evalfbb5in : C'=0, [ B^3>=1 && free>=0 && B^3>=2*free && 1+2*free>=B^3 && free>=1+A ], cost: 1 7.66/3.99 7.66/3.99 4: evalfbb7in -> evalfbb5in : C'=0, [ 0>=1+B^3 && 0>=free_1 && free_1>=1+A && 2*free_1>=B^3 && 1+B^3>=2*free_1 ], cost: 1 7.66/3.99 7.66/3.99 8: evalfbb5in -> evalfbb3in : D'=0, [ B>=1+C ], cost: 1 7.66/3.99 7.66/3.99 17: evalfbb5in -> evalfbb7in : A'=1+A, [ C>=B ], cost: 2 7.66/3.99 7.66/3.99 19: evalfbb3in -> evalfbb5in : C'=1+C, [ D>=C ], cost: 2 7.66/3.99 7.66/3.99 20: evalfbb3in -> evalfbb3in : D'=C, [ C>=1+D ], cost: 2*C-2*D 7.66/3.99 7.66/3.99 7.66/3.99 7.66/3.99 Chained accelerated rules (with incoming rules): 7.66/3.99 7.66/3.99 Start location: evalfstart 7.66/3.99 7.66/3.99 16: evalfstart -> evalfbb7in : A'=0, [], cost: 2 7.66/3.99 7.66/3.99 2: evalfbb7in -> evalfbb5in : C'=0, [ -B^3==0 && 0>=1+A ], cost: 1 7.66/3.99 7.66/3.99 3: evalfbb7in -> evalfbb5in : C'=0, [ B^3>=1 && free>=0 && B^3>=2*free && 1+2*free>=B^3 && free>=1+A ], cost: 1 7.66/3.99 7.66/3.99 4: evalfbb7in -> evalfbb5in : C'=0, [ 0>=1+B^3 && 0>=free_1 && free_1>=1+A && 2*free_1>=B^3 && 1+B^3>=2*free_1 ], cost: 1 7.66/3.99 7.66/3.99 8: evalfbb5in -> evalfbb3in : D'=0, [ B>=1+C ], cost: 1 7.66/3.99 7.66/3.99 17: evalfbb5in -> evalfbb7in : A'=1+A, [ C>=B ], cost: 2 7.66/3.99 7.66/3.99 21: evalfbb5in -> evalfbb3in : D'=C, [ B>=1+C && C>=1 ], cost: 1+2*C 7.66/3.99 7.66/3.99 19: evalfbb3in -> evalfbb5in : C'=1+C, [ D>=C ], cost: 2 7.66/3.99 7.66/3.99 7.66/3.99 7.66/3.99 Eliminated locations (on tree-shaped paths): 7.66/3.99 7.66/3.99 Start location: evalfstart 7.66/3.99 7.66/3.99 16: evalfstart -> evalfbb7in : A'=0, [], cost: 2 7.66/3.99 7.66/3.99 2: evalfbb7in -> evalfbb5in : C'=0, [ -B^3==0 && 0>=1+A ], cost: 1 7.66/3.99 7.66/3.99 3: evalfbb7in -> evalfbb5in : C'=0, [ B^3>=1 && free>=0 && B^3>=2*free && 1+2*free>=B^3 && free>=1+A ], cost: 1 7.66/3.99 7.66/3.99 4: evalfbb7in -> evalfbb5in : C'=0, [ 0>=1+B^3 && 0>=free_1 && free_1>=1+A && 2*free_1>=B^3 && 1+B^3>=2*free_1 ], cost: 1 7.66/3.99 7.66/3.99 17: evalfbb5in -> evalfbb7in : A'=1+A, [ C>=B ], cost: 2 7.66/3.99 7.66/3.99 22: evalfbb5in -> evalfbb5in : C'=1+C, D'=0, [ B>=1+C && 0>=C ], cost: 3 7.66/3.99 7.66/3.99 23: evalfbb5in -> evalfbb5in : C'=1+C, D'=C, [ B>=1+C && C>=1 ], cost: 3+2*C 7.66/3.99 7.66/3.99 7.66/3.99 7.66/3.99 Accelerating simple loops of location 3. 7.66/3.99 7.66/3.99 Accelerating the following rules: 7.66/3.99 7.66/3.99 22: evalfbb5in -> evalfbb5in : C'=1+C, D'=0, [ B>=1+C && 0>=C ], cost: 3 7.66/3.99 7.66/3.99 23: evalfbb5in -> evalfbb5in : C'=1+C, D'=C, [ B>=1+C && C>=1 ], cost: 3+2*C 7.66/3.99 7.66/3.99 7.66/3.99 7.66/3.99 Accelerated rule 22 with backward acceleration, yielding the new rule 24. 7.66/3.99 7.66/3.99 Accelerated rule 22 with backward acceleration, yielding the new rule 25. 7.66/3.99 7.66/3.99 Accelerated rule 23 with metering function -C+B, yielding the new rule 26. 7.66/3.99 7.66/3.99 Removing the simple loops: 22 23. 7.66/3.99 7.66/3.99 7.66/3.99 7.66/3.99 Accelerated all simple loops using metering functions (where possible): 7.66/3.99 7.66/3.99 Start location: evalfstart 7.66/3.99 7.66/3.99 16: evalfstart -> evalfbb7in : A'=0, [], cost: 2 7.66/3.99 7.66/3.99 2: evalfbb7in -> evalfbb5in : C'=0, [ -B^3==0 && 0>=1+A ], cost: 1 7.66/3.99 7.66/3.99 3: evalfbb7in -> evalfbb5in : C'=0, [ B^3>=1 && free>=0 && B^3>=2*free && 1+2*free>=B^3 && free>=1+A ], cost: 1 7.66/3.99 7.66/3.99 4: evalfbb7in -> evalfbb5in : C'=0, [ 0>=1+B^3 && 0>=free_1 && free_1>=1+A && 2*free_1>=B^3 && 1+B^3>=2*free_1 ], cost: 1 7.66/3.99 7.66/3.99 17: evalfbb5in -> evalfbb7in : A'=1+A, [ C>=B ], cost: 2 7.66/3.99 7.66/3.99 24: evalfbb5in -> evalfbb5in : C'=B, D'=0, [ B>=1+C && 0>=C && 0>=-1+B ], cost: -3*C+3*B 7.66/3.99 7.66/3.99 25: evalfbb5in -> evalfbb5in : C'=1, D'=0, [ B>=1+C && 0>=C && B>=1 ], cost: 3-3*C 7.66/3.99 7.66/3.99 26: evalfbb5in -> evalfbb5in : C'=B, D'=-1+B, [ B>=1+C && C>=1 ], cost: -2*C-2*C*(C-B)+(C-B)^2+2*B 7.66/3.99 7.66/3.99 7.66/3.99 7.66/3.99 Chained accelerated rules (with incoming rules): 7.66/3.99 7.66/3.99 Start location: evalfstart 7.66/3.99 7.66/3.99 16: evalfstart -> evalfbb7in : A'=0, [], cost: 2 7.66/3.99 7.66/3.99 2: evalfbb7in -> evalfbb5in : C'=0, [ -B^3==0 && 0>=1+A ], cost: 1 7.66/3.99 7.66/3.99 3: evalfbb7in -> evalfbb5in : C'=0, [ B^3>=1 && free>=0 && B^3>=2*free && 1+2*free>=B^3 && free>=1+A ], cost: 1 7.66/3.99 7.66/3.99 4: evalfbb7in -> evalfbb5in : C'=0, [ 0>=1+B^3 && 0>=free_1 && free_1>=1+A && 2*free_1>=B^3 && 1+B^3>=2*free_1 ], cost: 1 7.66/3.99 7.66/3.99 27: evalfbb7in -> evalfbb5in : C'=B, D'=0, [ B^3>=1 && free>=0 && B^3>=2*free && 1+2*free>=B^3 && free>=1+A && 1-B==0 ], cost: 1+3*B 7.66/3.99 7.66/3.99 28: evalfbb7in -> evalfbb5in : C'=1, D'=0, [ B^3>=1 && free>=0 && B^3>=2*free && 1+2*free>=B^3 && free>=1+A && B>=1 ], cost: 4 7.66/3.99 7.66/3.99 17: evalfbb5in -> evalfbb7in : A'=1+A, [ C>=B ], cost: 2 7.66/3.99 7.66/3.99 7.66/3.99 7.66/3.99 Eliminated locations (on tree-shaped paths): 7.66/3.99 7.66/3.99 Start location: evalfstart 7.66/3.99 7.66/3.99 16: evalfstart -> evalfbb7in : A'=0, [], cost: 2 7.66/3.99 7.66/3.99 29: evalfbb7in -> evalfbb7in : A'=1+A, C'=0, [ -B^3==0 && 0>=1+A && 0>=B ], cost: 3 7.66/3.99 7.66/3.99 30: evalfbb7in -> evalfbb7in : A'=1+A, C'=0, [ 0>=1+B^3 && 0>=free_1 && free_1>=1+A && 2*free_1>=B^3 && 1+B^3>=2*free_1 && 0>=B ], cost: 3 7.66/3.99 7.66/3.99 31: evalfbb7in -> evalfbb7in : A'=1+A, C'=B, D'=0, [ B^3>=1 && free>=0 && B^3>=2*free && 1+2*free>=B^3 && free>=1+A && 1-B==0 ], cost: 3+3*B 7.66/3.99 7.66/3.99 32: evalfbb7in -> evalfbb7in : A'=1+A, C'=1, D'=0, [ B^3>=1 && free>=0 && B^3>=2*free && 1+2*free>=B^3 && free>=1+A && B>=1 && 1>=B ], cost: 6 7.66/3.99 7.66/3.99 7.66/3.99 7.66/3.99 Accelerating simple loops of location 2. 7.66/3.99 7.66/3.99 Simplified some of the simple loops (and removed duplicate rules). 7.66/3.99 7.66/3.99 Accelerating the following rules: 7.66/3.99 7.66/3.99 29: evalfbb7in -> evalfbb7in : A'=1+A, C'=0, [ -B^3==0 && 0>=1+A && 0>=B ], cost: 3 7.66/3.99 7.66/3.99 30: evalfbb7in -> evalfbb7in : A'=1+A, C'=0, [ 0>=1+B^3 && 0>=free_1 && free_1>=1+A && 2*free_1>=B^3 && 1+B^3>=2*free_1 && 0>=B ], cost: 3 7.66/3.99 7.66/3.99 31: evalfbb7in -> evalfbb7in : A'=1+A, C'=B, D'=0, [ B^3>=1 && free>=0 && B^3>=2*free && 1+2*free>=B^3 && free>=1+A && 1-B==0 ], cost: 3+3*B 7.66/3.99 7.66/3.99 32: evalfbb7in -> evalfbb7in : A'=1+A, C'=1, D'=0, [ B^3>=1 && free>=0 && B^3>=2*free && 1+2*free>=B^3 && free>=1+A && 1-B==0 ], cost: 6 7.66/3.99 7.66/3.99 7.66/3.99 7.66/3.99 Accelerated rule 29 with metering function -A, yielding the new rule 33. 7.66/3.99 7.66/3.99 During metering: Linearized rule by temporarily substituting {B3==B^3} 7.66/3.99 7.66/3.99 Accelerated rule 30 with metering function free_1-A, yielding the new rule 34. 7.66/3.99 7.66/3.99 During metering: Linearized rule by temporarily substituting {B3_1==B^3} 7.66/3.99 7.66/3.99 Accelerated rule 31 with metering function free-A, yielding the new rule 35. 7.66/3.99 7.66/3.99 During metering: Linearized rule by temporarily substituting {B3_2==B^3} 7.66/3.99 7.66/3.99 Accelerated rule 32 with metering function free-A, yielding the new rule 36. 7.66/3.99 7.66/3.99 During metering: Instantiating temporary variables by {free==2+A} 7.66/3.99 7.66/3.99 During metering: Instantiating temporary variables by {free==2+A} 7.66/3.99 7.66/3.99 Removing the simple loops: 29 30 31 32. 7.66/3.99 7.66/3.99 7.66/3.99 7.66/3.99 Accelerated all simple loops using metering functions (where possible): 7.66/3.99 7.66/3.99 Start location: evalfstart 7.66/3.99 7.66/3.99 16: evalfstart -> evalfbb7in : A'=0, [], cost: 2 7.66/3.99 7.66/3.99 33: evalfbb7in -> evalfbb7in : A'=0, C'=0, [ -B^3==0 && 0>=1+A && 0>=B ], cost: -3*A 7.66/3.99 7.66/3.99 34: evalfbb7in -> evalfbb7in : A'=free_1, C'=0, [ 0>=1+B^3 && 0>=free_1 && free_1>=1+A && 2*free_1>=B^3 && 1+B^3>=2*free_1 && 0>=B ], cost: 3*free_1-3*A 7.66/3.99 7.66/3.99 35: evalfbb7in -> evalfbb7in : A'=free, C'=B, D'=0, [ B^3>=1 && free>=0 && B^3>=2*free && 1+2*free>=B^3 && free>=1+A && 1-B==0 ], cost: 3*free-3*A+3*(free-A)*B 7.66/3.99 7.66/3.99 36: evalfbb7in -> evalfbb7in : A'=free, C'=1, D'=0, [ B^3>=1 && free>=0 && B^3>=2*free && 1+2*free>=B^3 && free>=1+A && 1-B==0 ], cost: 6*free-6*A 7.66/3.99 7.66/3.99 7.66/3.99 7.66/3.99 Chained accelerated rules (with incoming rules): 7.66/3.99 7.66/3.99 Start location: evalfstart 7.66/3.99 7.66/3.99 16: evalfstart -> evalfbb7in : A'=0, [], cost: 2 7.66/3.99 7.66/3.99 7.66/3.99 7.66/3.99 Removed unreachable locations (and leaf rules with constant cost): 7.66/3.99 7.66/3.99 Start location: evalfstart 7.66/3.99 7.66/3.99 7.66/3.99 7.66/3.99 ### Computing asymptotic complexity ### 7.66/3.99 7.66/3.99 7.66/3.99 7.66/3.99 Fully simplified ITS problem 7.66/3.99 7.66/3.99 Start location: evalfstart 7.66/3.99 7.66/3.99 7.66/3.99 7.66/3.99 Obtained the following overall complexity (w.r.t. the length of the input n): 7.66/3.99 7.66/3.99 Complexity: Unknown 7.66/3.99 7.66/3.99 Cpx degree: ? 7.66/3.99 7.66/3.99 Solved cost: 0 7.66/3.99 7.66/3.99 Rule cost: 0 7.66/3.99 7.66/3.99 Rule guard: [] 7.66/3.99 7.66/3.99 7.66/3.99 7.66/3.99 WORST_CASE(Omega(0),?) 7.66/3.99 7.66/3.99 7.66/3.99 ---------------------------------------- 7.66/3.99 7.66/3.99 (2) 7.66/3.99 BOUNDS(1, INF) 7.70/4.02 EOF