15.67/11.13 WORST_CASE(Omega(n^4), O(n^7)) 15.67/11.15 proof of /export/starexec/sandbox/benchmark/theBenchmark.koat 15.67/11.15 # AProVE Commit ID: 48fb2092695e11cc9f56e44b17a92a5f88ffb256 marcel 20180622 unpublished dirty 15.67/11.15 15.67/11.15 15.67/11.15 The runtime complexity of the given CpxIntTrs could be proven to be BOUNDS(n^4, nat(3 * Arg_0 * max(3 * Arg_1, min(3, 3 * Arg_1))) * nat(Arg_0 + Arg_1) + 2 * nat(3 * Arg_0 * max(3 * Arg_1, min(3, 3 * Arg_1))) * nat(Arg_0 + Arg_1) * nat(Arg_1) + nat(3 * Arg_0 * max(3 * Arg_1, min(3, 3 * Arg_1))) * nat(Arg_0 + Arg_1) * max(4, -2 + 6 * Arg_0 + 6 * nat(3 * Arg_0 * max(3 * Arg_1, min(3, 3 * Arg_1))) * nat(Arg_0 + Arg_1) * nat(Arg_1) + 6 * nat(3 * Arg_1) * nat(Arg_0 + Arg_1) * nat(Arg_1) + 6 * nat(-10 * Arg_3) * nat(Arg_1)) + nat(3 * Arg_0 * max(3 * Arg_1, min(3, 3 * Arg_1))) * nat(Arg_0 + Arg_1) * max(1, -1 + 2 * Arg_0 + 2 * nat(3 * Arg_1) * nat(Arg_0 + Arg_1) * nat(Arg_1) + 2 * nat(3 * Arg_0 * max(3 * Arg_1, min(3, 3 * Arg_1))) * nat(Arg_0 + Arg_1) * nat(Arg_1) + 2 * nat(-10 * Arg_3) * nat(Arg_1)) + 2 * nat(3 * Arg_1) * nat(Arg_0 + Arg_1) * nat(Arg_1) + nat(3 * Arg_1) * nat(Arg_0 + Arg_1) + nat(3 * Arg_1) * nat(Arg_0 + Arg_1) * max(1, -1 + 2 * Arg_0 + 2 * nat(3 * Arg_1) * nat(Arg_0 + Arg_1) * nat(Arg_1) + 2 * nat(3 * Arg_0 * max(3 * Arg_1, min(3, 3 * Arg_1))) * nat(Arg_0 + Arg_1) * nat(Arg_1) + 2 * nat(-10 * Arg_3) * nat(Arg_1)) + nat(3 * Arg_1) * nat(Arg_0 + Arg_1) * max(4, -2 + 6 * Arg_0 + 6 * nat(3 * Arg_1) * nat(Arg_0 + Arg_1) * nat(Arg_1) + 6 * nat(3 * Arg_0 * max(3 * Arg_1, min(3, 3 * Arg_1))) * nat(Arg_0 + Arg_1) * nat(Arg_1) + 6 * nat(-10 * Arg_3) * nat(Arg_1)) + 2 * nat(-10 * Arg_3) * nat(Arg_1) + nat(-10 * Arg_3) + nat(-10 * Arg_3) * max(1, -1 + 2 * Arg_0 + 2 * nat(3 * Arg_1) * nat(Arg_0 + Arg_1) * nat(Arg_1) + 2 * nat(3 * Arg_0 * max(3 * Arg_1, min(3, 3 * Arg_1))) * nat(Arg_0 + Arg_1) * nat(Arg_1) + 2 * nat(-10 * Arg_3) * nat(Arg_1)) + nat(-10 * Arg_3) * max(4, -2 + 6 * Arg_0 + 6 * nat(3 * Arg_1) * nat(Arg_0 + Arg_1) * nat(Arg_1) + 6 * nat(3 * Arg_0 * max(3 * Arg_1, min(3, 3 * Arg_1))) * nat(Arg_0 + Arg_1) * nat(Arg_1) + 6 * nat(-10 * Arg_3) * nat(Arg_1)) + nat(6 * Arg_0) + nat(-2 * Arg_4) + nat(3 * Arg_0 * max(min(4, 4 * Arg_1), 4 * Arg_1)) + nat(4 * Arg_1) + max(1, 2 + Arg_0) + nat(-9 * Arg_4) + max(3 + 6 * Arg_1, 3) + nat(6 * Arg_0 * max(3 * Arg_1, min(3, 3 * Arg_1)))). 15.67/11.15 15.67/11.15 (0) CpxIntTrs 15.67/11.15 (1) Koat2 Proof [FINISHED, 9087 ms] 15.67/11.15 (2) BOUNDS(1, nat(3 * Arg_0 * max(3 * Arg_1, min(3, 3 * Arg_1))) * nat(Arg_0 + Arg_1) + 2 * nat(3 * Arg_0 * max(3 * Arg_1, min(3, 3 * Arg_1))) * nat(Arg_0 + Arg_1) * nat(Arg_1) + nat(3 * Arg_0 * max(3 * Arg_1, min(3, 3 * Arg_1))) * nat(Arg_0 + Arg_1) * max(4, -2 + 6 * Arg_0 + 6 * nat(3 * Arg_0 * max(3 * Arg_1, min(3, 3 * Arg_1))) * nat(Arg_0 + Arg_1) * nat(Arg_1) + 6 * nat(3 * Arg_1) * nat(Arg_0 + Arg_1) * nat(Arg_1) + 6 * nat(-10 * Arg_3) * nat(Arg_1)) + nat(3 * Arg_0 * max(3 * Arg_1, min(3, 3 * Arg_1))) * nat(Arg_0 + Arg_1) * max(1, -1 + 2 * Arg_0 + 2 * nat(3 * Arg_1) * nat(Arg_0 + Arg_1) * nat(Arg_1) + 2 * nat(3 * Arg_0 * max(3 * Arg_1, min(3, 3 * Arg_1))) * nat(Arg_0 + Arg_1) * nat(Arg_1) + 2 * nat(-10 * Arg_3) * nat(Arg_1)) + 2 * nat(3 * Arg_1) * nat(Arg_0 + Arg_1) * nat(Arg_1) + nat(3 * Arg_1) * nat(Arg_0 + Arg_1) + nat(3 * Arg_1) * nat(Arg_0 + Arg_1) * max(1, -1 + 2 * Arg_0 + 2 * nat(3 * Arg_1) * nat(Arg_0 + Arg_1) * nat(Arg_1) + 2 * nat(3 * Arg_0 * max(3 * Arg_1, min(3, 3 * Arg_1))) * nat(Arg_0 + Arg_1) * nat(Arg_1) + 2 * nat(-10 * Arg_3) * nat(Arg_1)) + nat(3 * Arg_1) * nat(Arg_0 + Arg_1) * max(4, -2 + 6 * Arg_0 + 6 * nat(3 * Arg_1) * nat(Arg_0 + Arg_1) * nat(Arg_1) + 6 * nat(3 * Arg_0 * max(3 * Arg_1, min(3, 3 * Arg_1))) * nat(Arg_0 + Arg_1) * nat(Arg_1) + 6 * nat(-10 * Arg_3) * nat(Arg_1)) + 2 * nat(-10 * Arg_3) * nat(Arg_1) + nat(-10 * Arg_3) + nat(-10 * Arg_3) * max(1, -1 + 2 * Arg_0 + 2 * nat(3 * Arg_1) * nat(Arg_0 + Arg_1) * nat(Arg_1) + 2 * nat(3 * Arg_0 * max(3 * Arg_1, min(3, 3 * Arg_1))) * nat(Arg_0 + Arg_1) * nat(Arg_1) + 2 * nat(-10 * Arg_3) * nat(Arg_1)) + nat(-10 * Arg_3) * max(4, -2 + 6 * Arg_0 + 6 * nat(3 * Arg_1) * nat(Arg_0 + Arg_1) * nat(Arg_1) + 6 * nat(3 * Arg_0 * max(3 * Arg_1, min(3, 3 * Arg_1))) * nat(Arg_0 + Arg_1) * nat(Arg_1) + 6 * nat(-10 * Arg_3) * nat(Arg_1)) + nat(6 * Arg_0) + nat(-2 * Arg_4) + nat(3 * Arg_0 * max(min(4, 4 * Arg_1), 4 * Arg_1)) + nat(4 * Arg_1) + max(1, 2 + Arg_0) + nat(-9 * Arg_4) + max(3 + 6 * Arg_1, 3) + nat(6 * Arg_0 * max(3 * Arg_1, min(3, 3 * Arg_1)))) 15.67/11.15 (3) Loat Proof [FINISHED, 2127 ms] 15.67/11.15 (4) BOUNDS(n^4, INF) 15.67/11.15 15.67/11.15 15.67/11.15 ---------------------------------------- 15.67/11.15 15.67/11.15 (0) 15.67/11.15 Obligation: 15.67/11.15 Complexity Int TRS consisting of the following rules: 15.67/11.15 evalfstart(A, B, C, D, E) -> Com_1(evalfentryin(A, B, C, D, E)) :|: TRUE 15.67/11.15 evalfentryin(A, B, C, D, E) -> Com_1(evalfbb10in(B, A, C, D, E)) :|: TRUE 15.67/11.15 evalfbb10in(A, B, C, D, E) -> Com_1(evalfbb8in(A, B, 1, D, E)) :|: B >= 1 15.67/11.15 evalfbb10in(A, B, C, D, E) -> Com_1(evalfreturnin(A, B, C, D, E)) :|: 0 >= B 15.67/11.15 evalfbb8in(A, B, C, D, E) -> Com_1(evalfbb6in(A, B, C, B, E)) :|: A >= C 15.67/11.15 evalfbb8in(A, B, C, D, E) -> Com_1(evalfbb9in(A, B, C, D, E)) :|: C >= A + 1 15.67/11.15 evalfbb6in(A, B, C, D, E) -> Com_1(evalfbb4in(A, B, C, D, 1)) :|: B + C >= D 15.67/11.15 evalfbb6in(A, B, C, D, E) -> Com_1(evalfbb7in(A, B, C, D, E)) :|: D >= B + C + 1 15.67/11.15 evalfbb4in(A, B, C, D, E) -> Com_1(evalfbb3in(A, B, C, D, E)) :|: D >= E 15.67/11.15 evalfbb4in(A, B, C, D, E) -> Com_1(evalfbb5in(A, B, C, D, E)) :|: E >= D + 1 15.67/11.15 evalfbb3in(A, B, C, D, E) -> Com_1(evalfbb4in(A, B, C, D, E + 1)) :|: TRUE 15.67/11.15 evalfbb5in(A, B, C, D, E) -> Com_1(evalfbb6in(A, B, C, D + 1, E)) :|: TRUE 15.67/11.15 evalfbb7in(A, B, C, D, E) -> Com_1(evalfbb8in(A, B, C + 1, D, E)) :|: TRUE 15.67/11.15 evalfbb9in(A, B, C, D, E) -> Com_1(evalfbb10in(A, B - 1, C, D, E)) :|: TRUE 15.67/11.15 evalfreturnin(A, B, C, D, E) -> Com_1(evalfstop(A, B, C, D, E)) :|: TRUE 15.67/11.15 15.67/11.15 The start-symbols are:[evalfstart_5] 15.67/11.15 15.67/11.15 15.67/11.15 ---------------------------------------- 15.67/11.15 15.67/11.15 (1) Koat2 Proof (FINISHED) 15.67/11.15 YES( ?, 3+(max([0, 3*Arg_1])+max([0, 3*Arg_0*max([3*min([1, Arg_1]), 3*Arg_1])]))*max([0, Arg_0+Arg_1])+2*((max([0, 3*Arg_1])+max([0, 3*Arg_0*max([3*min([1, Arg_1]), 3*Arg_1])]))*max([0, Arg_0+Arg_1])+max([0, -10*Arg_3]))*max([0, Arg_1])+((max([0, 3*Arg_1])+max([0, 3*Arg_0*max([3*min([1, Arg_1]), 3*Arg_1])]))*max([0, Arg_0+Arg_1])+max([0, -10*Arg_3]))*max([4, -2+6*(Arg_0+((max([0, 3*Arg_1])+max([0, 3*Arg_0*max([3*min([1, Arg_1]), 3*Arg_1])]))*max([0, Arg_0+Arg_1])+max([0, -10*Arg_3]))*max([0, Arg_1]))])+((max([0, 3*Arg_1])+max([0, 3*Arg_0*max([3*min([1, Arg_1]), 3*Arg_1])]))*max([0, Arg_0+Arg_1])+max([0, -10*Arg_3]))*max([1, -1+2*(Arg_0+((max([0, 3*Arg_1])+max([0, 3*Arg_0*max([3*min([1, Arg_1]), 3*Arg_1])]))*max([0, Arg_0+Arg_1])+max([0, -10*Arg_3]))*max([0, Arg_1]))])+max([0, 3*Arg_0])+max([0, -2*Arg_4])+max([0, 3*Arg_0])+max([0, 3*Arg_0*max([3*min([1, Arg_1]), 3*Arg_1])])+max([0, 3*Arg_1])+max([0, 3*Arg_0*max([4*min([1, Arg_1]), 4*Arg_1])])+max([0, 4*Arg_1])+max([0, 3*Arg_0*max([3*min([1, Arg_1]), 3*Arg_1])])+max([0, 3*Arg_1])+max([0, -10*Arg_3])+max([1, 2+Arg_0])+max([0, -9*Arg_4]) {O(n^7)}) 15.67/11.15 15.67/11.15 15.67/11.15 15.67/11.15 Initial Complexity Problem: 15.67/11.15 15.67/11.15 Start: evalfstart 15.67/11.15 15.67/11.15 Program_Vars: Arg_0, Arg_1, Arg_2, Arg_3, Arg_4 15.67/11.15 15.67/11.15 Temp_Vars: 15.67/11.15 15.67/11.15 Locations: evalfbb10in, evalfbb3in, evalfbb4in, evalfbb5in, evalfbb6in, evalfbb7in, evalfbb8in, evalfbb9in, evalfentryin, evalfreturnin, evalfstart, evalfstop 15.67/11.15 15.67/11.15 Transitions: 15.67/11.15 15.67/11.15 evalfbb10in(Arg_0,Arg_1,Arg_2,Arg_3,Arg_4) -> evalfbb8in(Arg_0,Arg_1,1,Arg_3,Arg_4):|:1 <= Arg_1 15.67/11.15 15.67/11.15 evalfbb10in(Arg_0,Arg_1,Arg_2,Arg_3,Arg_4) -> evalfreturnin(Arg_0,Arg_1,Arg_2,Arg_3,Arg_4):|:Arg_1 <= 0 15.67/11.15 15.67/11.15 evalfbb3in(Arg_0,Arg_1,Arg_2,Arg_3,Arg_4) -> evalfbb4in(Arg_0,Arg_1,Arg_2,Arg_3,Arg_4+1):|:Arg_4 <= Arg_3 && 1 <= Arg_4 && 2 <= Arg_3+Arg_4 && 2 <= Arg_2+Arg_4 && 2 <= Arg_1+Arg_4 && 2 <= Arg_0+Arg_4 && 1 <= Arg_3 && 2 <= Arg_2+Arg_3 && 2 <= Arg_1+Arg_3 && Arg_1 <= Arg_3 && 2 <= Arg_0+Arg_3 && Arg_2 <= Arg_0 && 1 <= Arg_2 && 2 <= Arg_1+Arg_2 && 2 <= Arg_0+Arg_2 && 1 <= Arg_1 && 2 <= Arg_0+Arg_1 && 1 <= Arg_0 15.67/11.15 15.67/11.15 evalfbb4in(Arg_0,Arg_1,Arg_2,Arg_3,Arg_4) -> evalfbb3in(Arg_0,Arg_1,Arg_2,Arg_3,Arg_4):|:1 <= Arg_4 && 2 <= Arg_3+Arg_4 && 2 <= Arg_2+Arg_4 && 2 <= Arg_1+Arg_4 && 2 <= Arg_0+Arg_4 && 1 <= Arg_3 && 2 <= Arg_2+Arg_3 && 2 <= Arg_1+Arg_3 && Arg_1 <= Arg_3 && 2 <= Arg_0+Arg_3 && Arg_2 <= Arg_0 && 1 <= Arg_2 && 2 <= Arg_1+Arg_2 && 2 <= Arg_0+Arg_2 && 1 <= Arg_1 && 2 <= Arg_0+Arg_1 && 1 <= Arg_0 && Arg_4 <= Arg_3 15.67/11.15 15.67/11.15 evalfbb4in(Arg_0,Arg_1,Arg_2,Arg_3,Arg_4) -> evalfbb5in(Arg_0,Arg_1,Arg_2,Arg_3,Arg_4):|:1 <= Arg_4 && 2 <= Arg_3+Arg_4 && 2 <= Arg_2+Arg_4 && 2 <= Arg_1+Arg_4 && 2 <= Arg_0+Arg_4 && 1 <= Arg_3 && 2 <= Arg_2+Arg_3 && 2 <= Arg_1+Arg_3 && Arg_1 <= Arg_3 && 2 <= Arg_0+Arg_3 && Arg_2 <= Arg_0 && 1 <= Arg_2 && 2 <= Arg_1+Arg_2 && 2 <= Arg_0+Arg_2 && 1 <= Arg_1 && 2 <= Arg_0+Arg_1 && 1 <= Arg_0 && Arg_3+1 <= Arg_4 15.67/11.15 15.67/11.15 evalfbb5in(Arg_0,Arg_1,Arg_2,Arg_3,Arg_4) -> evalfbb6in(Arg_0,Arg_1,Arg_2,Arg_3+1,Arg_4):|:2 <= Arg_4 && 3 <= Arg_3+Arg_4 && 1+Arg_3 <= Arg_4 && 3 <= Arg_2+Arg_4 && 3 <= Arg_1+Arg_4 && 1+Arg_1 <= Arg_4 && 3 <= Arg_0+Arg_4 && 1 <= Arg_3 && 2 <= Arg_2+Arg_3 && 2 <= Arg_1+Arg_3 && Arg_1 <= Arg_3 && 2 <= Arg_0+Arg_3 && Arg_2 <= Arg_0 && 1 <= Arg_2 && 2 <= Arg_1+Arg_2 && 2 <= Arg_0+Arg_2 && 1 <= Arg_1 && 2 <= Arg_0+Arg_1 && 1 <= Arg_0 15.67/11.15 15.67/11.15 evalfbb6in(Arg_0,Arg_1,Arg_2,Arg_3,Arg_4) -> evalfbb4in(Arg_0,Arg_1,Arg_2,Arg_3,1):|:1 <= Arg_3 && 2 <= Arg_2+Arg_3 && 2 <= Arg_1+Arg_3 && Arg_1 <= Arg_3 && 2 <= Arg_0+Arg_3 && Arg_2 <= Arg_0 && 1 <= Arg_2 && 2 <= Arg_1+Arg_2 && 2 <= Arg_0+Arg_2 && 1 <= Arg_1 && 2 <= Arg_0+Arg_1 && 1 <= Arg_0 && Arg_3 <= Arg_1+Arg_2 15.67/11.15 15.67/11.15 evalfbb6in(Arg_0,Arg_1,Arg_2,Arg_3,Arg_4) -> evalfbb7in(Arg_0,Arg_1,Arg_2,Arg_3,Arg_4):|:1 <= Arg_3 && 2 <= Arg_2+Arg_3 && 2 <= Arg_1+Arg_3 && Arg_1 <= Arg_3 && 2 <= Arg_0+Arg_3 && Arg_2 <= Arg_0 && 1 <= Arg_2 && 2 <= Arg_1+Arg_2 && 2 <= Arg_0+Arg_2 && 1 <= Arg_1 && 2 <= Arg_0+Arg_1 && 1 <= Arg_0 && Arg_1+Arg_2+1 <= Arg_3 15.67/11.15 15.67/11.15 evalfbb7in(Arg_0,Arg_1,Arg_2,Arg_3,Arg_4) -> evalfbb8in(Arg_0,Arg_1,Arg_2+1,Arg_3,Arg_4):|:3 <= Arg_3 && 4 <= Arg_2+Arg_3 && 2+Arg_2 <= Arg_3 && 4 <= Arg_1+Arg_3 && 2+Arg_1 <= Arg_3 && 4 <= Arg_0+Arg_3 && Arg_2 <= Arg_0 && 1 <= Arg_2 && 2 <= Arg_1+Arg_2 && 2 <= Arg_0+Arg_2 && 1 <= Arg_1 && 2 <= Arg_0+Arg_1 && 1 <= Arg_0 15.67/11.15 15.67/11.15 evalfbb8in(Arg_0,Arg_1,Arg_2,Arg_3,Arg_4) -> evalfbb6in(Arg_0,Arg_1,Arg_2,Arg_1,Arg_4):|:1 <= Arg_2 && 2 <= Arg_1+Arg_2 && 1 <= Arg_1 && Arg_2 <= Arg_0 15.67/11.15 15.67/11.15 evalfbb8in(Arg_0,Arg_1,Arg_2,Arg_3,Arg_4) -> evalfbb9in(Arg_0,Arg_1,Arg_2,Arg_3,Arg_4):|:1 <= Arg_2 && 2 <= Arg_1+Arg_2 && 1 <= Arg_1 && Arg_0+1 <= Arg_2 15.67/11.15 15.67/11.15 evalfbb9in(Arg_0,Arg_1,Arg_2,Arg_3,Arg_4) -> evalfbb10in(Arg_0,Arg_1-1,Arg_2,Arg_3,Arg_4):|:1 <= Arg_2 && 2 <= Arg_1+Arg_2 && 1+Arg_0 <= Arg_2 && 1 <= Arg_1 15.67/11.15 15.67/11.15 evalfentryin(Arg_0,Arg_1,Arg_2,Arg_3,Arg_4) -> evalfbb10in(Arg_1,Arg_0,Arg_2,Arg_3,Arg_4):|: 15.67/11.15 15.67/11.15 evalfreturnin(Arg_0,Arg_1,Arg_2,Arg_3,Arg_4) -> evalfstop(Arg_0,Arg_1,Arg_2,Arg_3,Arg_4):|:Arg_1 <= 0 15.67/11.15 15.67/11.15 evalfstart(Arg_0,Arg_1,Arg_2,Arg_3,Arg_4) -> evalfentryin(Arg_0,Arg_1,Arg_2,Arg_3,Arg_4):|: 15.67/11.15 15.67/11.15 15.67/11.15 15.67/11.15 Timebounds: 15.67/11.15 15.67/11.15 Overall timebound: 3+(max([0, 3*Arg_1])+max([0, 3*Arg_0*max([3*min([1, Arg_1]), 3*Arg_1])]))*max([0, Arg_0+Arg_1])+2*((max([0, 3*Arg_1])+max([0, 3*Arg_0*max([3*min([1, Arg_1]), 3*Arg_1])]))*max([0, Arg_0+Arg_1])+max([0, -10*Arg_3]))*max([0, Arg_1])+((max([0, 3*Arg_1])+max([0, 3*Arg_0*max([3*min([1, Arg_1]), 3*Arg_1])]))*max([0, Arg_0+Arg_1])+max([0, -10*Arg_3]))*max([4, -2+6*(Arg_0+((max([0, 3*Arg_1])+max([0, 3*Arg_0*max([3*min([1, Arg_1]), 3*Arg_1])]))*max([0, Arg_0+Arg_1])+max([0, -10*Arg_3]))*max([0, Arg_1]))])+((max([0, 3*Arg_1])+max([0, 3*Arg_0*max([3*min([1, Arg_1]), 3*Arg_1])]))*max([0, Arg_0+Arg_1])+max([0, -10*Arg_3]))*max([1, -1+2*(Arg_0+((max([0, 3*Arg_1])+max([0, 3*Arg_0*max([3*min([1, Arg_1]), 3*Arg_1])]))*max([0, Arg_0+Arg_1])+max([0, -10*Arg_3]))*max([0, Arg_1]))])+max([0, 3*Arg_0])+max([0, -2*Arg_4])+max([0, 3*Arg_0])+max([0, 3*Arg_0*max([3*min([1, Arg_1]), 3*Arg_1])])+max([0, 3*Arg_1])+max([0, 3*Arg_0*max([4*min([1, Arg_1]), 4*Arg_1])])+max([0, 4*Arg_1])+max([0, 3*Arg_0*max([3*min([1, Arg_1]), 3*Arg_1])])+max([0, 3*Arg_1])+max([0, -10*Arg_3])+max([1, 2+Arg_0])+max([0, -9*Arg_4]) {O(n^7)} 15.67/11.15 15.67/11.15 2: evalfbb10in->evalfbb8in: max([0, 1+Arg_0]) {O(n)} 15.67/11.15 15.67/11.15 3: evalfbb10in->evalfreturnin: 1 {O(1)} 15.67/11.15 15.67/11.15 10: evalfbb3in->evalfbb4in: ((max([0, 3*Arg_1])+max([0, 3*Arg_0*max([3*min([1, Arg_1]), 3*Arg_1])]))*max([0, Arg_0+Arg_1])+max([0, -10*Arg_3]))*max([1, -1+2*(Arg_0+((max([0, 3*Arg_1])+max([0, 3*Arg_0*max([3*min([1, Arg_1]), 3*Arg_1])]))*max([0, Arg_0+Arg_1])+max([0, -10*Arg_3]))*max([0, Arg_1]))])+max([0, -9*Arg_4]) {O(n^7)} 15.67/11.15 15.67/11.15 8: evalfbb4in->evalfbb3in: ((max([0, 3*Arg_1])+max([0, 3*Arg_0*max([3*min([1, Arg_1]), 3*Arg_1])]))*max([0, Arg_0+Arg_1])+max([0, -10*Arg_3]))*max([4, -2+6*(Arg_0+((max([0, 3*Arg_1])+max([0, 3*Arg_0*max([3*min([1, Arg_1]), 3*Arg_1])]))*max([0, Arg_0+Arg_1])+max([0, -10*Arg_3]))*max([0, Arg_1]))])+max([0, -2*Arg_4]) {O(n^7)} 15.67/11.15 15.67/11.15 9: evalfbb4in->evalfbb5in: ((max([0, 3*Arg_1])+max([0, 3*Arg_0*max([3*min([1, Arg_1]), 3*Arg_1])]))*max([0, Arg_0+Arg_1])+max([0, -10*Arg_3]))*max([0, Arg_1]) {O(n^4)} 15.67/11.15 15.67/11.15 11: evalfbb5in->evalfbb6in: ((max([0, 3*Arg_1])+max([0, 3*Arg_0*max([3*min([1, Arg_1]), 3*Arg_1])]))*max([0, Arg_0+Arg_1])+max([0, -10*Arg_3]))*max([0, Arg_1]) {O(n^4)} 15.67/11.15 15.67/11.15 6: evalfbb6in->evalfbb4in: (max([0, 3*Arg_1])+max([0, 3*Arg_0*max([3*min([1, Arg_1]), 3*Arg_1])]))*max([0, Arg_0+Arg_1])+max([0, -10*Arg_3]) {O(n^3)} 15.67/11.15 15.67/11.15 7: evalfbb6in->evalfbb7in: max([0, 3*Arg_1])+max([0, 3*Arg_0*max([3*min([1, Arg_1]), 3*Arg_1])]) {O(n^2)} 15.67/11.15 15.67/11.15 12: evalfbb7in->evalfbb8in: max([0, 4*Arg_1])+max([0, 3*Arg_0*max([4*min([1, Arg_1]), 4*Arg_1])]) {O(n^2)} 15.67/11.15 15.67/11.15 4: evalfbb8in->evalfbb6in: max([0, 3*Arg_1])+max([0, 3*Arg_0*max([3*min([1, Arg_1]), 3*Arg_1])]) {O(n^2)} 15.67/11.15 15.67/11.15 5: evalfbb8in->evalfbb9in: max([0, 3*Arg_0]) {O(n)} 15.67/11.15 15.67/11.15 13: evalfbb9in->evalfbb10in: max([0, 3*Arg_0]) {O(n)} 15.67/11.15 15.67/11.15 1: evalfentryin->evalfbb10in: 1 {O(1)} 15.67/11.15 15.67/11.15 14: evalfreturnin->evalfstop: 1 {O(1)} 15.67/11.15 15.67/11.15 0: evalfstart->evalfentryin: 1 {O(1)} 15.67/11.15 15.67/11.15 15.67/11.15 15.67/11.15 Costbounds: 15.67/11.15 15.67/11.15 Overall costbound: 3+(max([0, 3*Arg_1])+max([0, 3*Arg_0*max([3*min([1, Arg_1]), 3*Arg_1])]))*max([0, Arg_0+Arg_1])+2*((max([0, 3*Arg_1])+max([0, 3*Arg_0*max([3*min([1, Arg_1]), 3*Arg_1])]))*max([0, Arg_0+Arg_1])+max([0, -10*Arg_3]))*max([0, Arg_1])+((max([0, 3*Arg_1])+max([0, 3*Arg_0*max([3*min([1, Arg_1]), 3*Arg_1])]))*max([0, Arg_0+Arg_1])+max([0, -10*Arg_3]))*max([4, -2+6*(Arg_0+((max([0, 3*Arg_1])+max([0, 3*Arg_0*max([3*min([1, Arg_1]), 3*Arg_1])]))*max([0, Arg_0+Arg_1])+max([0, -10*Arg_3]))*max([0, Arg_1]))])+((max([0, 3*Arg_1])+max([0, 3*Arg_0*max([3*min([1, Arg_1]), 3*Arg_1])]))*max([0, Arg_0+Arg_1])+max([0, -10*Arg_3]))*max([1, -1+2*(Arg_0+((max([0, 3*Arg_1])+max([0, 3*Arg_0*max([3*min([1, Arg_1]), 3*Arg_1])]))*max([0, Arg_0+Arg_1])+max([0, -10*Arg_3]))*max([0, Arg_1]))])+max([0, 3*Arg_0])+max([0, -2*Arg_4])+max([0, 3*Arg_0])+max([0, 3*Arg_0*max([3*min([1, Arg_1]), 3*Arg_1])])+max([0, 3*Arg_1])+max([0, 3*Arg_0*max([4*min([1, Arg_1]), 4*Arg_1])])+max([0, 4*Arg_1])+max([0, 3*Arg_0*max([3*min([1, Arg_1]), 3*Arg_1])])+max([0, 3*Arg_1])+max([0, -10*Arg_3])+max([1, 2+Arg_0])+max([0, -9*Arg_4]) {O(n^7)} 15.67/11.15 15.67/11.15 2: evalfbb10in->evalfbb8in: max([0, 1+Arg_0]) {O(n)} 15.67/11.15 15.67/11.15 3: evalfbb10in->evalfreturnin: 1 {O(1)} 15.67/11.15 15.67/11.15 10: evalfbb3in->evalfbb4in: ((max([0, 3*Arg_1])+max([0, 3*Arg_0*max([3*min([1, Arg_1]), 3*Arg_1])]))*max([0, Arg_0+Arg_1])+max([0, -10*Arg_3]))*max([1, -1+2*(Arg_0+((max([0, 3*Arg_1])+max([0, 3*Arg_0*max([3*min([1, Arg_1]), 3*Arg_1])]))*max([0, Arg_0+Arg_1])+max([0, -10*Arg_3]))*max([0, Arg_1]))])+max([0, -9*Arg_4]) {O(n^7)} 15.67/11.15 15.67/11.15 8: evalfbb4in->evalfbb3in: ((max([0, 3*Arg_1])+max([0, 3*Arg_0*max([3*min([1, Arg_1]), 3*Arg_1])]))*max([0, Arg_0+Arg_1])+max([0, -10*Arg_3]))*max([4, -2+6*(Arg_0+((max([0, 3*Arg_1])+max([0, 3*Arg_0*max([3*min([1, Arg_1]), 3*Arg_1])]))*max([0, Arg_0+Arg_1])+max([0, -10*Arg_3]))*max([0, Arg_1]))])+max([0, -2*Arg_4]) {O(n^7)} 15.67/11.15 15.67/11.15 9: evalfbb4in->evalfbb5in: ((max([0, 3*Arg_1])+max([0, 3*Arg_0*max([3*min([1, Arg_1]), 3*Arg_1])]))*max([0, Arg_0+Arg_1])+max([0, -10*Arg_3]))*max([0, Arg_1]) {O(n^4)} 15.67/11.15 15.67/11.15 11: evalfbb5in->evalfbb6in: ((max([0, 3*Arg_1])+max([0, 3*Arg_0*max([3*min([1, Arg_1]), 3*Arg_1])]))*max([0, Arg_0+Arg_1])+max([0, -10*Arg_3]))*max([0, Arg_1]) {O(n^4)} 15.67/11.15 15.67/11.15 6: evalfbb6in->evalfbb4in: (max([0, 3*Arg_1])+max([0, 3*Arg_0*max([3*min([1, Arg_1]), 3*Arg_1])]))*max([0, Arg_0+Arg_1])+max([0, -10*Arg_3]) {O(n^3)} 15.67/11.15 15.67/11.15 7: evalfbb6in->evalfbb7in: max([0, 3*Arg_1])+max([0, 3*Arg_0*max([3*min([1, Arg_1]), 3*Arg_1])]) {O(n^2)} 15.67/11.15 15.67/11.15 12: evalfbb7in->evalfbb8in: max([0, 4*Arg_1])+max([0, 3*Arg_0*max([4*min([1, Arg_1]), 4*Arg_1])]) {O(n^2)} 15.67/11.15 15.67/11.15 4: evalfbb8in->evalfbb6in: max([0, 3*Arg_1])+max([0, 3*Arg_0*max([3*min([1, Arg_1]), 3*Arg_1])]) {O(n^2)} 15.67/11.15 15.67/11.15 5: evalfbb8in->evalfbb9in: max([0, 3*Arg_0]) {O(n)} 15.67/11.15 15.67/11.15 13: evalfbb9in->evalfbb10in: max([0, 3*Arg_0]) {O(n)} 15.67/11.15 15.67/11.15 1: evalfentryin->evalfbb10in: 1 {O(1)} 15.67/11.15 15.67/11.15 14: evalfreturnin->evalfstop: 1 {O(1)} 15.67/11.15 15.67/11.15 0: evalfstart->evalfentryin: 1 {O(1)} 15.67/11.15 15.67/11.15 15.67/11.15 15.67/11.15 Sizebounds: 15.67/11.15 15.67/11.15 `Lower: 15.67/11.15 15.67/11.15 2: evalfbb10in->evalfbb8in, Arg_0: min([1, Arg_1]) {O(n)} 15.67/11.15 15.67/11.15 2: evalfbb10in->evalfbb8in, Arg_1: 1 {O(1)} 15.67/11.15 15.67/11.15 2: evalfbb10in->evalfbb8in, Arg_2: 1 {O(1)} 15.67/11.15 15.67/11.15 2: evalfbb10in->evalfbb8in, Arg_3: min([3, Arg_3]) {O(n)} 15.67/11.15 15.67/11.15 2: evalfbb10in->evalfbb8in, Arg_4: min([2, Arg_4]) {O(n)} 15.67/11.15 15.67/11.15 3: evalfbb10in->evalfreturnin, Arg_0: min([1, Arg_1]) {O(n)} 15.67/11.15 15.67/11.15 3: evalfbb10in->evalfreturnin, Arg_1: min([0, Arg_0]) {O(n)} 15.67/11.15 15.67/11.15 3: evalfbb10in->evalfreturnin, Arg_2: min([1, Arg_2]) {O(n)} 15.67/11.15 15.67/11.15 3: evalfbb10in->evalfreturnin, Arg_3: min([3, Arg_3]) {O(n)} 15.67/11.15 15.67/11.15 3: evalfbb10in->evalfreturnin, Arg_4: min([2, Arg_4]) {O(n)} 15.67/11.15 15.67/11.15 10: evalfbb3in->evalfbb4in, Arg_0: 1 {O(1)} 15.67/11.15 15.67/11.15 10: evalfbb3in->evalfbb4in, Arg_1: 1 {O(1)} 15.67/11.15 15.67/11.15 10: evalfbb3in->evalfbb4in, Arg_2: 1 {O(1)} 15.67/11.15 15.67/11.15 10: evalfbb3in->evalfbb4in, Arg_3: 1 {O(1)} 15.67/11.15 15.67/11.15 10: evalfbb3in->evalfbb4in, Arg_4: 2 {O(1)} 15.67/11.15 15.67/11.15 8: evalfbb4in->evalfbb3in, Arg_0: 1 {O(1)} 15.67/11.15 15.67/11.15 8: evalfbb4in->evalfbb3in, Arg_1: 1 {O(1)} 15.67/11.15 15.67/11.15 8: evalfbb4in->evalfbb3in, Arg_2: 1 {O(1)} 15.67/11.15 15.67/11.15 8: evalfbb4in->evalfbb3in, Arg_3: 1 {O(1)} 15.67/11.15 15.67/11.15 8: evalfbb4in->evalfbb3in, Arg_4: 1 {O(1)} 15.67/11.15 15.67/11.15 9: evalfbb4in->evalfbb5in, Arg_0: 1 {O(1)} 15.67/11.15 15.67/11.15 9: evalfbb4in->evalfbb5in, Arg_1: 1 {O(1)} 15.67/11.15 15.67/11.15 9: evalfbb4in->evalfbb5in, Arg_2: 1 {O(1)} 15.67/11.15 15.67/11.15 9: evalfbb4in->evalfbb5in, Arg_3: 1 {O(1)} 15.67/11.15 15.67/11.15 9: evalfbb4in->evalfbb5in, Arg_4: 2 {O(1)} 15.67/11.15 15.67/11.15 11: evalfbb5in->evalfbb6in, Arg_0: 1 {O(1)} 15.67/11.15 15.67/11.15 11: evalfbb5in->evalfbb6in, Arg_1: 1 {O(1)} 15.67/11.15 15.67/11.15 11: evalfbb5in->evalfbb6in, Arg_2: 1 {O(1)} 15.67/11.15 15.67/11.15 11: evalfbb5in->evalfbb6in, Arg_3: 2 {O(1)} 15.67/11.15 15.67/11.15 11: evalfbb5in->evalfbb6in, Arg_4: 2 {O(1)} 15.67/11.15 15.67/11.15 6: evalfbb6in->evalfbb4in, Arg_0: 1 {O(1)} 15.67/11.15 15.67/11.15 6: evalfbb6in->evalfbb4in, Arg_1: 1 {O(1)} 15.67/11.15 15.67/11.15 6: evalfbb6in->evalfbb4in, Arg_2: 1 {O(1)} 15.67/11.15 15.67/11.15 6: evalfbb6in->evalfbb4in, Arg_3: 1 {O(1)} 15.67/11.15 15.67/11.15 6: evalfbb6in->evalfbb4in, Arg_4: 1 {O(1)} 15.67/11.15 15.67/11.15 7: evalfbb6in->evalfbb7in, Arg_0: 1 {O(1)} 15.67/11.15 15.67/11.15 7: evalfbb6in->evalfbb7in, Arg_1: 1 {O(1)} 15.67/11.15 15.67/11.15 7: evalfbb6in->evalfbb7in, Arg_2: 1 {O(1)} 15.67/11.15 15.67/11.15 7: evalfbb6in->evalfbb7in, Arg_3: 3 {O(1)} 15.67/11.15 15.67/11.15 7: evalfbb6in->evalfbb7in, Arg_4: 2 {O(1)} 15.67/11.15 15.67/11.15 12: evalfbb7in->evalfbb8in, Arg_0: 1 {O(1)} 15.67/11.15 15.67/11.15 12: evalfbb7in->evalfbb8in, Arg_1: 1 {O(1)} 15.67/11.15 15.67/11.15 12: evalfbb7in->evalfbb8in, Arg_2: 2 {O(1)} 15.67/11.15 15.67/11.15 12: evalfbb7in->evalfbb8in, Arg_3: 3 {O(1)} 15.67/11.15 15.67/11.15 12: evalfbb7in->evalfbb8in, Arg_4: 2 {O(1)} 15.67/11.15 15.67/11.15 4: evalfbb8in->evalfbb6in, Arg_0: 1 {O(1)} 15.67/11.15 15.67/11.15 4: evalfbb8in->evalfbb6in, Arg_1: 1 {O(1)} 15.67/11.15 15.67/11.15 4: evalfbb8in->evalfbb6in, Arg_2: 1 {O(1)} 15.67/11.15 15.67/11.15 4: evalfbb8in->evalfbb6in, Arg_3: 1 {O(1)} 15.67/11.15 15.67/11.15 4: evalfbb8in->evalfbb6in, Arg_4: min([2, min([2, Arg_4])]) {O(n)} 15.67/11.15 15.67/11.15 5: evalfbb8in->evalfbb9in, Arg_0: min([1, Arg_1]) {O(n)} 15.67/11.15 15.67/11.15 5: evalfbb8in->evalfbb9in, Arg_1: 1 {O(1)} 15.67/11.15 15.67/11.15 5: evalfbb8in->evalfbb9in, Arg_2: 1 {O(1)} 15.67/11.15 15.67/11.15 5: evalfbb8in->evalfbb9in, Arg_3: min([3, Arg_3]) {O(n)} 15.67/11.15 15.67/11.15 5: evalfbb8in->evalfbb9in, Arg_4: min([2, Arg_4]) {O(n)} 15.67/11.15 15.67/11.15 13: evalfbb9in->evalfbb10in, Arg_0: min([1, Arg_1]) {O(n)} 15.67/11.15 15.67/11.15 13: evalfbb9in->evalfbb10in, Arg_1: 0 {O(1)} 15.67/11.15 15.67/11.15 13: evalfbb9in->evalfbb10in, Arg_2: 1 {O(1)} 15.67/11.15 15.67/11.15 13: evalfbb9in->evalfbb10in, Arg_3: min([3, Arg_3]) {O(n)} 15.67/11.15 15.67/11.15 13: evalfbb9in->evalfbb10in, Arg_4: min([2, Arg_4]) {O(n)} 15.67/11.15 15.67/11.15 1: evalfentryin->evalfbb10in, Arg_0: Arg_1 {O(n)} 15.67/11.15 15.67/11.15 1: evalfentryin->evalfbb10in, Arg_1: Arg_0 {O(n)} 15.67/11.15 15.67/11.15 1: evalfentryin->evalfbb10in, Arg_2: Arg_2 {O(n)} 15.67/11.15 15.67/11.15 1: evalfentryin->evalfbb10in, Arg_3: Arg_3 {O(n)} 15.67/11.15 15.67/11.15 1: evalfentryin->evalfbb10in, Arg_4: Arg_4 {O(n)} 15.67/11.15 15.67/11.15 14: evalfreturnin->evalfstop, Arg_0: min([1, Arg_1]) {O(n)} 15.67/11.15 15.67/11.15 14: evalfreturnin->evalfstop, Arg_1: min([0, Arg_0]) {O(n)} 15.67/11.15 15.67/11.15 14: evalfreturnin->evalfstop, Arg_2: min([1, Arg_2]) {O(n)} 15.67/11.15 15.67/11.15 14: evalfreturnin->evalfstop, Arg_3: min([3, Arg_3]) {O(n)} 15.67/11.15 15.67/11.15 14: evalfreturnin->evalfstop, Arg_4: min([2, Arg_4]) {O(n)} 15.67/11.15 15.67/11.15 0: evalfstart->evalfentryin, Arg_0: Arg_0 {O(n)} 15.67/11.15 15.67/11.15 0: evalfstart->evalfentryin, Arg_1: Arg_1 {O(n)} 15.67/11.15 15.67/11.15 0: evalfstart->evalfentryin, Arg_2: Arg_2 {O(n)} 15.67/11.15 15.67/11.15 0: evalfstart->evalfentryin, Arg_3: Arg_3 {O(n)} 15.67/11.15 15.67/11.15 0: evalfstart->evalfentryin, Arg_4: Arg_4 {O(n)} 15.67/11.15 15.67/11.15 `Upper: 15.67/11.15 15.67/11.15 2: evalfbb10in->evalfbb8in, Arg_0: Arg_1 {O(n)} 15.67/11.15 15.67/11.15 2: evalfbb10in->evalfbb8in, Arg_1: Arg_0 {O(n)} 15.67/11.15 15.67/11.15 2: evalfbb10in->evalfbb8in, Arg_2: 1 {O(1)} 15.67/11.15 15.67/11.15 2: evalfbb10in->evalfbb8in, Arg_3: max([Arg_3, Arg_0+((max([0, 3*Arg_1])+max([0, 3*Arg_0*max([3*min([1, Arg_1]), 3*Arg_1])]))*max([0, Arg_0+Arg_1])+max([0, -10*Arg_3]))*max([0, Arg_1])]) {O(n^4)} 15.67/11.15 15.67/11.15 2: evalfbb10in->evalfbb8in, Arg_4: max([Arg_4, 1+((max([0, 3*Arg_1])+max([0, 3*Arg_0*max([3*min([1, Arg_1]), 3*Arg_1])]))*max([0, Arg_0+Arg_1])+max([0, -10*Arg_3]))*max([1, -1+2*(Arg_0+((max([0, 3*Arg_1])+max([0, 3*Arg_0*max([3*min([1, Arg_1]), 3*Arg_1])]))*max([0, Arg_0+Arg_1])+max([0, -10*Arg_3]))*max([0, Arg_1]))])+max([0, -9*Arg_4])]) {O(n^7)} 15.67/11.15 15.67/11.15 3: evalfbb10in->evalfreturnin, Arg_0: Arg_1 {O(n)} 15.67/11.15 15.67/11.15 3: evalfbb10in->evalfreturnin, Arg_1: 0 {O(1)} 15.67/11.15 15.67/11.15 3: evalfbb10in->evalfreturnin, Arg_2: max([1, max([Arg_2, 1+max([0, 4*Arg_1])+max([0, 3*Arg_0*max([4*min([1, Arg_1]), 4*Arg_1])])])]) {O(n^2)} 15.67/11.15 15.67/11.15 3: evalfbb10in->evalfreturnin, Arg_3: max([Arg_3, max([Arg_3, Arg_0+((max([0, 3*Arg_1])+max([0, 3*Arg_0*max([3*min([1, Arg_1]), 3*Arg_1])]))*max([0, Arg_0+Arg_1])+max([0, -10*Arg_3]))*max([0, Arg_1])])]) {O(n^4)} 15.67/11.15 15.67/11.15 3: evalfbb10in->evalfreturnin, Arg_4: max([Arg_4, max([Arg_4, 1+((max([0, 3*Arg_1])+max([0, 3*Arg_0*max([3*min([1, Arg_1]), 3*Arg_1])]))*max([0, Arg_0+Arg_1])+max([0, -10*Arg_3]))*max([1, -1+2*(Arg_0+((max([0, 3*Arg_1])+max([0, 3*Arg_0*max([3*min([1, Arg_1]), 3*Arg_1])]))*max([0, Arg_0+Arg_1])+max([0, -10*Arg_3]))*max([0, Arg_1]))])+max([0, -9*Arg_4])])]) {O(n^7)} 15.67/11.15 15.67/11.15 10: evalfbb3in->evalfbb4in, Arg_0: Arg_1 {O(n)} 15.67/11.15 15.67/11.15 10: evalfbb3in->evalfbb4in, Arg_1: Arg_0 {O(n)} 15.67/11.15 15.67/11.15 10: evalfbb3in->evalfbb4in, Arg_2: 1+max([0, 4*Arg_1])+max([0, 3*Arg_0*max([4*min([1, Arg_1]), 4*Arg_1])]) {O(n^2)} 15.67/11.15 15.67/11.15 10: evalfbb3in->evalfbb4in, Arg_3: Arg_0+((max([0, 3*Arg_1])+max([0, 3*Arg_0*max([3*min([1, Arg_1]), 3*Arg_1])]))*max([0, Arg_0+Arg_1])+max([0, -10*Arg_3]))*max([0, Arg_1]) {O(n^4)} 15.67/11.15 15.67/11.15 10: evalfbb3in->evalfbb4in, Arg_4: 1+((max([0, 3*Arg_1])+max([0, 3*Arg_0*max([3*min([1, Arg_1]), 3*Arg_1])]))*max([0, Arg_0+Arg_1])+max([0, -10*Arg_3]))*max([1, -1+2*(Arg_0+((max([0, 3*Arg_1])+max([0, 3*Arg_0*max([3*min([1, Arg_1]), 3*Arg_1])]))*max([0, Arg_0+Arg_1])+max([0, -10*Arg_3]))*max([0, Arg_1]))])+max([0, -9*Arg_4]) {O(n^7)} 15.67/11.15 15.67/11.15 8: evalfbb4in->evalfbb3in, Arg_0: Arg_1 {O(n)} 15.67/11.15 15.67/11.15 8: evalfbb4in->evalfbb3in, Arg_1: Arg_0 {O(n)} 15.67/11.15 15.67/11.15 8: evalfbb4in->evalfbb3in, Arg_2: 1+max([0, 4*Arg_1])+max([0, 3*Arg_0*max([4*min([1, Arg_1]), 4*Arg_1])]) {O(n^2)} 15.67/11.15 15.67/11.15 8: evalfbb4in->evalfbb3in, Arg_3: Arg_0+((max([0, 3*Arg_1])+max([0, 3*Arg_0*max([3*min([1, Arg_1]), 3*Arg_1])]))*max([0, Arg_0+Arg_1])+max([0, -10*Arg_3]))*max([0, Arg_1]) {O(n^4)} 15.67/11.15 15.67/11.15 8: evalfbb4in->evalfbb3in, Arg_4: 1+((max([0, 3*Arg_1])+max([0, 3*Arg_0*max([3*min([1, Arg_1]), 3*Arg_1])]))*max([0, Arg_0+Arg_1])+max([0, -10*Arg_3]))*max([1, -1+2*(Arg_0+((max([0, 3*Arg_1])+max([0, 3*Arg_0*max([3*min([1, Arg_1]), 3*Arg_1])]))*max([0, Arg_0+Arg_1])+max([0, -10*Arg_3]))*max([0, Arg_1]))])+max([0, -9*Arg_4]) {O(n^7)} 15.67/11.15 15.67/11.15 9: evalfbb4in->evalfbb5in, Arg_0: Arg_1 {O(n)} 15.67/11.15 15.67/11.15 9: evalfbb4in->evalfbb5in, Arg_1: Arg_0 {O(n)} 15.67/11.15 15.67/11.15 9: evalfbb4in->evalfbb5in, Arg_2: 1+max([0, 4*Arg_1])+max([0, 3*Arg_0*max([4*min([1, Arg_1]), 4*Arg_1])]) {O(n^2)} 15.67/11.15 15.67/11.15 9: evalfbb4in->evalfbb5in, Arg_3: Arg_0+((max([0, 3*Arg_1])+max([0, 3*Arg_0*max([3*min([1, Arg_1]), 3*Arg_1])]))*max([0, Arg_0+Arg_1])+max([0, -10*Arg_3]))*max([0, Arg_1]) {O(n^4)} 15.67/11.15 15.67/11.15 9: evalfbb4in->evalfbb5in, Arg_4: 1+((max([0, 3*Arg_1])+max([0, 3*Arg_0*max([3*min([1, Arg_1]), 3*Arg_1])]))*max([0, Arg_0+Arg_1])+max([0, -10*Arg_3]))*max([1, -1+2*(Arg_0+((max([0, 3*Arg_1])+max([0, 3*Arg_0*max([3*min([1, Arg_1]), 3*Arg_1])]))*max([0, Arg_0+Arg_1])+max([0, -10*Arg_3]))*max([0, Arg_1]))])+max([0, -9*Arg_4]) {O(n^7)} 15.67/11.15 15.67/11.15 11: evalfbb5in->evalfbb6in, Arg_0: Arg_1 {O(n)} 15.67/11.15 15.67/11.15 11: evalfbb5in->evalfbb6in, Arg_1: Arg_0 {O(n)} 15.67/11.15 15.67/11.15 11: evalfbb5in->evalfbb6in, Arg_2: 1+max([0, 4*Arg_1])+max([0, 3*Arg_0*max([4*min([1, Arg_1]), 4*Arg_1])]) {O(n^2)} 15.67/11.15 15.67/11.15 11: evalfbb5in->evalfbb6in, Arg_3: Arg_0+((max([0, 3*Arg_1])+max([0, 3*Arg_0*max([3*min([1, Arg_1]), 3*Arg_1])]))*max([0, Arg_0+Arg_1])+max([0, -10*Arg_3]))*max([0, Arg_1]) {O(n^4)} 15.67/11.15 15.67/11.15 11: evalfbb5in->evalfbb6in, Arg_4: 1+((max([0, 3*Arg_1])+max([0, 3*Arg_0*max([3*min([1, Arg_1]), 3*Arg_1])]))*max([0, Arg_0+Arg_1])+max([0, -10*Arg_3]))*max([1, -1+2*(Arg_0+((max([0, 3*Arg_1])+max([0, 3*Arg_0*max([3*min([1, Arg_1]), 3*Arg_1])]))*max([0, Arg_0+Arg_1])+max([0, -10*Arg_3]))*max([0, Arg_1]))])+max([0, -9*Arg_4]) {O(n^7)} 15.67/11.15 15.67/11.15 6: evalfbb6in->evalfbb4in, Arg_0: Arg_1 {O(n)} 15.67/11.15 15.67/11.15 6: evalfbb6in->evalfbb4in, Arg_1: Arg_0 {O(n)} 15.67/11.15 15.67/11.15 6: evalfbb6in->evalfbb4in, Arg_2: 1+max([0, 4*Arg_1])+max([0, 3*Arg_0*max([4*min([1, Arg_1]), 4*Arg_1])]) {O(n^2)} 15.67/11.15 15.67/11.15 6: evalfbb6in->evalfbb4in, Arg_3: Arg_0+((max([0, 3*Arg_1])+max([0, 3*Arg_0*max([3*min([1, Arg_1]), 3*Arg_1])]))*max([0, Arg_0+Arg_1])+max([0, -10*Arg_3]))*max([0, Arg_1]) {O(n^4)} 15.67/11.15 15.67/11.15 6: evalfbb6in->evalfbb4in, Arg_4: 1 {O(1)} 15.67/11.15 15.67/11.15 7: evalfbb6in->evalfbb7in, Arg_0: Arg_1 {O(n)} 15.67/11.15 15.67/11.15 7: evalfbb6in->evalfbb7in, Arg_1: Arg_0 {O(n)} 15.67/11.15 15.67/11.15 7: evalfbb6in->evalfbb7in, Arg_2: 1+max([0, 4*Arg_1])+max([0, 3*Arg_0*max([4*min([1, Arg_1]), 4*Arg_1])]) {O(n^2)} 15.67/11.15 15.67/11.15 7: evalfbb6in->evalfbb7in, Arg_3: Arg_0+((max([0, 3*Arg_1])+max([0, 3*Arg_0*max([3*min([1, Arg_1]), 3*Arg_1])]))*max([0, Arg_0+Arg_1])+max([0, -10*Arg_3]))*max([0, Arg_1]) {O(n^4)} 15.67/11.15 15.67/11.15 7: evalfbb6in->evalfbb7in, Arg_4: 1+((max([0, 3*Arg_1])+max([0, 3*Arg_0*max([3*min([1, Arg_1]), 3*Arg_1])]))*max([0, Arg_0+Arg_1])+max([0, -10*Arg_3]))*max([1, -1+2*(Arg_0+((max([0, 3*Arg_1])+max([0, 3*Arg_0*max([3*min([1, Arg_1]), 3*Arg_1])]))*max([0, Arg_0+Arg_1])+max([0, -10*Arg_3]))*max([0, Arg_1]))])+max([0, -9*Arg_4]) {O(n^7)} 15.67/11.15 15.67/11.15 12: evalfbb7in->evalfbb8in, Arg_0: Arg_1 {O(n)} 15.67/11.15 15.67/11.15 12: evalfbb7in->evalfbb8in, Arg_1: Arg_0 {O(n)} 15.67/11.15 15.67/11.15 12: evalfbb7in->evalfbb8in, Arg_2: 1+max([0, 4*Arg_1])+max([0, 3*Arg_0*max([4*min([1, Arg_1]), 4*Arg_1])]) {O(n^2)} 15.67/11.15 15.67/11.15 12: evalfbb7in->evalfbb8in, Arg_3: Arg_0+((max([0, 3*Arg_1])+max([0, 3*Arg_0*max([3*min([1, Arg_1]), 3*Arg_1])]))*max([0, Arg_0+Arg_1])+max([0, -10*Arg_3]))*max([0, Arg_1]) {O(n^4)} 15.67/11.15 15.67/11.15 12: evalfbb7in->evalfbb8in, Arg_4: 1+((max([0, 3*Arg_1])+max([0, 3*Arg_0*max([3*min([1, Arg_1]), 3*Arg_1])]))*max([0, Arg_0+Arg_1])+max([0, -10*Arg_3]))*max([1, -1+2*(Arg_0+((max([0, 3*Arg_1])+max([0, 3*Arg_0*max([3*min([1, Arg_1]), 3*Arg_1])]))*max([0, Arg_0+Arg_1])+max([0, -10*Arg_3]))*max([0, Arg_1]))])+max([0, -9*Arg_4]) {O(n^7)} 15.67/11.15 15.67/11.15 4: evalfbb8in->evalfbb6in, Arg_0: Arg_1 {O(n)} 15.67/11.15 15.67/11.15 4: evalfbb8in->evalfbb6in, Arg_1: Arg_0 {O(n)} 15.67/11.15 15.67/11.15 4: evalfbb8in->evalfbb6in, Arg_2: 1+max([0, 4*Arg_1])+max([0, 3*Arg_0*max([4*min([1, Arg_1]), 4*Arg_1])]) {O(n^2)} 15.67/11.15 15.67/11.15 4: evalfbb8in->evalfbb6in, Arg_3: Arg_0 {O(n)} 15.67/11.15 15.67/11.15 4: evalfbb8in->evalfbb6in, Arg_4: max([Arg_4, 1+((max([0, 3*Arg_1])+max([0, 3*Arg_0*max([3*min([1, Arg_1]), 3*Arg_1])]))*max([0, Arg_0+Arg_1])+max([0, -10*Arg_3]))*max([1, -1+2*(Arg_0+((max([0, 3*Arg_1])+max([0, 3*Arg_0*max([3*min([1, Arg_1]), 3*Arg_1])]))*max([0, Arg_0+Arg_1])+max([0, -10*Arg_3]))*max([0, Arg_1]))])+max([0, -9*Arg_4])]) {O(n^7)} 15.67/11.15 15.67/11.15 5: evalfbb8in->evalfbb9in, Arg_0: Arg_1 {O(n)} 15.67/11.15 15.67/11.15 5: evalfbb8in->evalfbb9in, Arg_1: Arg_0 {O(n)} 15.67/11.15 15.67/11.15 5: evalfbb8in->evalfbb9in, Arg_2: max([1, 1+max([0, 4*Arg_1])+max([0, 3*Arg_0*max([4*min([1, Arg_1]), 4*Arg_1])])]) {O(n^2)} 15.67/11.15 15.67/11.15 5: evalfbb8in->evalfbb9in, Arg_3: max([Arg_3, Arg_0+((max([0, 3*Arg_1])+max([0, 3*Arg_0*max([3*min([1, Arg_1]), 3*Arg_1])]))*max([0, Arg_0+Arg_1])+max([0, -10*Arg_3]))*max([0, Arg_1])]) {O(n^4)} 15.67/11.15 15.67/11.15 5: evalfbb8in->evalfbb9in, Arg_4: max([Arg_4, 1+((max([0, 3*Arg_1])+max([0, 3*Arg_0*max([3*min([1, Arg_1]), 3*Arg_1])]))*max([0, Arg_0+Arg_1])+max([0, -10*Arg_3]))*max([1, -1+2*(Arg_0+((max([0, 3*Arg_1])+max([0, 3*Arg_0*max([3*min([1, Arg_1]), 3*Arg_1])]))*max([0, Arg_0+Arg_1])+max([0, -10*Arg_3]))*max([0, Arg_1]))])+max([0, -9*Arg_4])]) {O(n^7)} 15.67/11.15 15.67/11.15 13: evalfbb9in->evalfbb10in, Arg_0: Arg_1 {O(n)} 15.67/11.15 15.67/11.15 13: evalfbb9in->evalfbb10in, Arg_1: Arg_0 {O(n)} 15.67/11.15 15.67/11.15 13: evalfbb9in->evalfbb10in, Arg_2: max([1, 1+max([0, 4*Arg_1])+max([0, 3*Arg_0*max([4*min([1, Arg_1]), 4*Arg_1])])]) {O(n^2)} 15.67/11.15 15.67/11.15 13: evalfbb9in->evalfbb10in, Arg_3: max([Arg_3, Arg_0+((max([0, 3*Arg_1])+max([0, 3*Arg_0*max([3*min([1, Arg_1]), 3*Arg_1])]))*max([0, Arg_0+Arg_1])+max([0, -10*Arg_3]))*max([0, Arg_1])]) {O(n^4)} 15.67/11.15 15.67/11.15 13: evalfbb9in->evalfbb10in, Arg_4: max([Arg_4, 1+((max([0, 3*Arg_1])+max([0, 3*Arg_0*max([3*min([1, Arg_1]), 3*Arg_1])]))*max([0, Arg_0+Arg_1])+max([0, -10*Arg_3]))*max([1, -1+2*(Arg_0+((max([0, 3*Arg_1])+max([0, 3*Arg_0*max([3*min([1, Arg_1]), 3*Arg_1])]))*max([0, Arg_0+Arg_1])+max([0, -10*Arg_3]))*max([0, Arg_1]))])+max([0, -9*Arg_4])]) {O(n^7)} 15.67/11.15 15.67/11.15 1: evalfentryin->evalfbb10in, Arg_0: Arg_1 {O(n)} 15.67/11.15 15.67/11.15 1: evalfentryin->evalfbb10in, Arg_1: Arg_0 {O(n)} 15.67/11.15 15.67/11.15 1: evalfentryin->evalfbb10in, Arg_2: Arg_2 {O(n)} 15.67/11.15 15.67/11.15 1: evalfentryin->evalfbb10in, Arg_3: Arg_3 {O(n)} 15.67/11.15 15.67/11.15 1: evalfentryin->evalfbb10in, Arg_4: Arg_4 {O(n)} 15.67/11.15 15.67/11.15 14: evalfreturnin->evalfstop, Arg_0: Arg_1 {O(n)} 15.67/11.15 15.67/11.15 14: evalfreturnin->evalfstop, Arg_1: 0 {O(1)} 15.67/11.15 15.67/11.15 14: evalfreturnin->evalfstop, Arg_2: max([1, max([Arg_2, 1+max([0, 4*Arg_1])+max([0, 3*Arg_0*max([4*min([1, Arg_1]), 4*Arg_1])])])]) {O(n^2)} 15.67/11.15 15.67/11.15 14: evalfreturnin->evalfstop, Arg_3: max([Arg_3, max([Arg_3, Arg_0+((max([0, 3*Arg_1])+max([0, 3*Arg_0*max([3*min([1, Arg_1]), 3*Arg_1])]))*max([0, Arg_0+Arg_1])+max([0, -10*Arg_3]))*max([0, Arg_1])])]) {O(n^4)} 15.67/11.15 15.67/11.15 14: evalfreturnin->evalfstop, Arg_4: max([Arg_4, max([Arg_4, 1+((max([0, 3*Arg_1])+max([0, 3*Arg_0*max([3*min([1, Arg_1]), 3*Arg_1])]))*max([0, Arg_0+Arg_1])+max([0, -10*Arg_3]))*max([1, -1+2*(Arg_0+((max([0, 3*Arg_1])+max([0, 3*Arg_0*max([3*min([1, Arg_1]), 3*Arg_1])]))*max([0, Arg_0+Arg_1])+max([0, -10*Arg_3]))*max([0, Arg_1]))])+max([0, -9*Arg_4])])]) {O(n^7)} 15.67/11.15 15.67/11.15 0: evalfstart->evalfentryin, Arg_0: Arg_0 {O(n)} 15.67/11.15 15.67/11.15 0: evalfstart->evalfentryin, Arg_1: Arg_1 {O(n)} 15.67/11.15 15.67/11.15 0: evalfstart->evalfentryin, Arg_2: Arg_2 {O(n)} 15.67/11.15 15.67/11.15 0: evalfstart->evalfentryin, Arg_3: Arg_3 {O(n)} 15.67/11.15 15.67/11.15 0: evalfstart->evalfentryin, Arg_4: Arg_4 {O(n)} 15.67/11.15 15.67/11.15 15.67/11.15 ---------------------------------------- 15.67/11.15 15.67/11.15 (2) 15.67/11.15 BOUNDS(1, nat(3 * Arg_0 * max(3 * Arg_1, min(3, 3 * Arg_1))) * nat(Arg_0 + Arg_1) + 2 * nat(3 * Arg_0 * max(3 * Arg_1, min(3, 3 * Arg_1))) * nat(Arg_0 + Arg_1) * nat(Arg_1) + nat(3 * Arg_0 * max(3 * Arg_1, min(3, 3 * Arg_1))) * nat(Arg_0 + Arg_1) * max(4, -2 + 6 * Arg_0 + 6 * nat(3 * Arg_0 * max(3 * Arg_1, min(3, 3 * Arg_1))) * nat(Arg_0 + Arg_1) * nat(Arg_1) + 6 * nat(3 * Arg_1) * nat(Arg_0 + Arg_1) * nat(Arg_1) + 6 * nat(-10 * Arg_3) * nat(Arg_1)) + nat(3 * Arg_0 * max(3 * Arg_1, min(3, 3 * Arg_1))) * nat(Arg_0 + Arg_1) * max(1, -1 + 2 * Arg_0 + 2 * nat(3 * Arg_1) * nat(Arg_0 + Arg_1) * nat(Arg_1) + 2 * nat(3 * Arg_0 * max(3 * Arg_1, min(3, 3 * Arg_1))) * nat(Arg_0 + Arg_1) * nat(Arg_1) + 2 * nat(-10 * Arg_3) * nat(Arg_1)) + 2 * nat(3 * Arg_1) * nat(Arg_0 + Arg_1) * nat(Arg_1) + nat(3 * Arg_1) * nat(Arg_0 + Arg_1) + nat(3 * Arg_1) * nat(Arg_0 + Arg_1) * max(1, -1 + 2 * Arg_0 + 2 * nat(3 * Arg_1) * nat(Arg_0 + Arg_1) * nat(Arg_1) + 2 * nat(3 * Arg_0 * max(3 * Arg_1, min(3, 3 * Arg_1))) * nat(Arg_0 + Arg_1) * nat(Arg_1) + 2 * nat(-10 * Arg_3) * nat(Arg_1)) + nat(3 * Arg_1) * nat(Arg_0 + Arg_1) * max(4, -2 + 6 * Arg_0 + 6 * nat(3 * Arg_1) * nat(Arg_0 + Arg_1) * nat(Arg_1) + 6 * nat(3 * Arg_0 * max(3 * Arg_1, min(3, 3 * Arg_1))) * nat(Arg_0 + Arg_1) * nat(Arg_1) + 6 * nat(-10 * Arg_3) * nat(Arg_1)) + 2 * nat(-10 * Arg_3) * nat(Arg_1) + nat(-10 * Arg_3) + nat(-10 * Arg_3) * max(1, -1 + 2 * Arg_0 + 2 * nat(3 * Arg_1) * nat(Arg_0 + Arg_1) * nat(Arg_1) + 2 * nat(3 * Arg_0 * max(3 * Arg_1, min(3, 3 * Arg_1))) * nat(Arg_0 + Arg_1) * nat(Arg_1) + 2 * nat(-10 * Arg_3) * nat(Arg_1)) + nat(-10 * Arg_3) * max(4, -2 + 6 * Arg_0 + 6 * nat(3 * Arg_1) * nat(Arg_0 + Arg_1) * nat(Arg_1) + 6 * nat(3 * Arg_0 * max(3 * Arg_1, min(3, 3 * Arg_1))) * nat(Arg_0 + Arg_1) * nat(Arg_1) + 6 * nat(-10 * Arg_3) * nat(Arg_1)) + nat(6 * Arg_0) + nat(-2 * Arg_4) + nat(3 * Arg_0 * max(min(4, 4 * Arg_1), 4 * Arg_1)) + nat(4 * Arg_1) + max(1, 2 + Arg_0) + nat(-9 * Arg_4) + max(3 + 6 * Arg_1, 3) + nat(6 * Arg_0 * max(3 * Arg_1, min(3, 3 * Arg_1)))) 15.67/11.15 15.67/11.15 ---------------------------------------- 15.67/11.15 15.67/11.15 (3) Loat Proof (FINISHED) 15.67/11.15 15.67/11.15 15.67/11.15 ### Pre-processing the ITS problem ### 15.67/11.15 15.67/11.15 15.67/11.15 15.67/11.15 Initial linear ITS problem 15.67/11.15 15.67/11.15 Start location: evalfstart 15.67/11.15 15.67/11.15 0: evalfstart -> evalfentryin : [], cost: 1 15.67/11.15 15.67/11.15 1: evalfentryin -> evalfbb10in : A'=B, B'=A, [], cost: 1 15.67/11.15 15.67/11.15 2: evalfbb10in -> evalfbb8in : C'=1, [ B>=1 ], cost: 1 15.67/11.15 15.67/11.15 3: evalfbb10in -> evalfreturnin : [ 0>=B ], cost: 1 15.67/11.15 15.67/11.15 4: evalfbb8in -> evalfbb6in : D'=B, [ A>=C ], cost: 1 15.67/11.15 15.67/11.15 5: evalfbb8in -> evalfbb9in : [ C>=1+A ], cost: 1 15.67/11.15 15.67/11.15 6: evalfbb6in -> evalfbb4in : E'=1, [ C+B>=D ], cost: 1 15.67/11.15 15.67/11.15 7: evalfbb6in -> evalfbb7in : [ D>=1+C+B ], cost: 1 15.67/11.15 15.67/11.15 8: evalfbb4in -> evalfbb3in : [ D>=E ], cost: 1 15.67/11.15 15.67/11.15 9: evalfbb4in -> evalfbb5in : [ E>=1+D ], cost: 1 15.67/11.15 15.67/11.15 10: evalfbb3in -> evalfbb4in : E'=1+E, [], cost: 1 15.67/11.15 15.67/11.15 11: evalfbb5in -> evalfbb6in : D'=1+D, [], cost: 1 15.67/11.15 15.67/11.15 12: evalfbb7in -> evalfbb8in : C'=1+C, [], cost: 1 15.67/11.15 15.67/11.15 13: evalfbb9in -> evalfbb10in : B'=-1+B, [], cost: 1 15.67/11.15 15.67/11.15 14: evalfreturnin -> evalfstop : [], cost: 1 15.67/11.15 15.67/11.15 15.67/11.15 15.67/11.15 Removed unreachable and leaf rules: 15.67/11.15 15.67/11.15 Start location: evalfstart 15.67/11.15 15.67/11.15 0: evalfstart -> evalfentryin : [], cost: 1 15.67/11.15 15.67/11.15 1: evalfentryin -> evalfbb10in : A'=B, B'=A, [], cost: 1 15.67/11.15 15.67/11.15 2: evalfbb10in -> evalfbb8in : C'=1, [ B>=1 ], cost: 1 15.67/11.15 15.67/11.15 4: evalfbb8in -> evalfbb6in : D'=B, [ A>=C ], cost: 1 15.67/11.15 15.67/11.15 5: evalfbb8in -> evalfbb9in : [ C>=1+A ], cost: 1 15.67/11.15 15.67/11.15 6: evalfbb6in -> evalfbb4in : E'=1, [ C+B>=D ], cost: 1 15.67/11.15 15.67/11.15 7: evalfbb6in -> evalfbb7in : [ D>=1+C+B ], cost: 1 15.67/11.15 15.67/11.15 8: evalfbb4in -> evalfbb3in : [ D>=E ], cost: 1 15.67/11.15 15.67/11.15 9: evalfbb4in -> evalfbb5in : [ E>=1+D ], cost: 1 15.67/11.15 15.67/11.15 10: evalfbb3in -> evalfbb4in : E'=1+E, [], cost: 1 15.67/11.15 15.67/11.15 11: evalfbb5in -> evalfbb6in : D'=1+D, [], cost: 1 15.67/11.15 15.67/11.15 12: evalfbb7in -> evalfbb8in : C'=1+C, [], cost: 1 15.67/11.15 15.67/11.15 13: evalfbb9in -> evalfbb10in : B'=-1+B, [], cost: 1 15.67/11.15 15.67/11.15 15.67/11.15 15.67/11.15 ### Simplification by acceleration and chaining ### 15.67/11.15 15.67/11.15 15.67/11.15 15.67/11.15 Eliminated locations (on linear paths): 15.67/11.15 15.67/11.15 Start location: evalfstart 15.67/11.15 15.67/11.15 15: evalfstart -> evalfbb10in : A'=B, B'=A, [], cost: 2 15.67/11.15 15.67/11.15 2: evalfbb10in -> evalfbb8in : C'=1, [ B>=1 ], cost: 1 15.67/11.15 15.67/11.15 4: evalfbb8in -> evalfbb6in : D'=B, [ A>=C ], cost: 1 15.67/11.15 15.67/11.15 16: evalfbb8in -> evalfbb10in : B'=-1+B, [ C>=1+A ], cost: 2 15.67/11.15 15.67/11.15 6: evalfbb6in -> evalfbb4in : E'=1, [ C+B>=D ], cost: 1 15.67/11.15 15.67/11.15 17: evalfbb6in -> evalfbb8in : C'=1+C, [ D>=1+C+B ], cost: 2 15.67/11.15 15.67/11.15 18: evalfbb4in -> evalfbb4in : E'=1+E, [ D>=E ], cost: 2 15.67/11.15 15.67/11.15 19: evalfbb4in -> evalfbb6in : D'=1+D, [ E>=1+D ], cost: 2 15.67/11.15 15.67/11.15 15.67/11.15 15.67/11.15 Accelerating simple loops of location 5. 15.67/11.15 15.67/11.15 Accelerating the following rules: 15.67/11.15 15.67/11.15 18: evalfbb4in -> evalfbb4in : E'=1+E, [ D>=E ], cost: 2 15.67/11.15 15.67/11.15 15.67/11.15 15.67/11.15 Accelerated rule 18 with metering function 1+D-E, yielding the new rule 20. 15.67/11.15 15.67/11.15 Removing the simple loops: 18. 15.67/11.15 15.67/11.15 15.67/11.15 15.67/11.15 Accelerated all simple loops using metering functions (where possible): 15.67/11.15 15.67/11.15 Start location: evalfstart 15.67/11.15 15.67/11.15 15: evalfstart -> evalfbb10in : A'=B, B'=A, [], cost: 2 15.67/11.15 15.67/11.15 2: evalfbb10in -> evalfbb8in : C'=1, [ B>=1 ], cost: 1 15.67/11.15 15.67/11.15 4: evalfbb8in -> evalfbb6in : D'=B, [ A>=C ], cost: 1 15.67/11.15 15.67/11.15 16: evalfbb8in -> evalfbb10in : B'=-1+B, [ C>=1+A ], cost: 2 15.67/11.15 15.67/11.15 6: evalfbb6in -> evalfbb4in : E'=1, [ C+B>=D ], cost: 1 15.67/11.15 15.67/11.15 17: evalfbb6in -> evalfbb8in : C'=1+C, [ D>=1+C+B ], cost: 2 15.67/11.15 15.67/11.15 19: evalfbb4in -> evalfbb6in : D'=1+D, [ E>=1+D ], cost: 2 15.67/11.15 15.67/11.15 20: evalfbb4in -> evalfbb4in : E'=1+D, [ D>=E ], cost: 2+2*D-2*E 15.67/11.15 15.67/11.15 15.67/11.15 15.67/11.15 Chained accelerated rules (with incoming rules): 15.67/11.15 15.67/11.15 Start location: evalfstart 15.67/11.15 15.67/11.15 15: evalfstart -> evalfbb10in : A'=B, B'=A, [], cost: 2 15.67/11.15 15.67/11.15 2: evalfbb10in -> evalfbb8in : C'=1, [ B>=1 ], cost: 1 15.67/11.15 15.67/11.15 4: evalfbb8in -> evalfbb6in : D'=B, [ A>=C ], cost: 1 15.67/11.15 15.67/11.15 16: evalfbb8in -> evalfbb10in : B'=-1+B, [ C>=1+A ], cost: 2 15.67/11.15 15.67/11.15 6: evalfbb6in -> evalfbb4in : E'=1, [ C+B>=D ], cost: 1 15.67/11.15 15.67/11.15 17: evalfbb6in -> evalfbb8in : C'=1+C, [ D>=1+C+B ], cost: 2 15.67/11.15 15.67/11.15 21: evalfbb6in -> evalfbb4in : E'=1+D, [ C+B>=D && D>=1 ], cost: 1+2*D 15.67/11.15 15.67/11.15 19: evalfbb4in -> evalfbb6in : D'=1+D, [ E>=1+D ], cost: 2 15.67/11.15 15.67/11.15 15.67/11.15 15.67/11.15 Eliminated locations (on tree-shaped paths): 15.67/11.15 15.67/11.15 Start location: evalfstart 15.67/11.15 15.67/11.15 15: evalfstart -> evalfbb10in : A'=B, B'=A, [], cost: 2 15.67/11.15 15.67/11.15 2: evalfbb10in -> evalfbb8in : C'=1, [ B>=1 ], cost: 1 15.67/11.15 15.67/11.15 4: evalfbb8in -> evalfbb6in : D'=B, [ A>=C ], cost: 1 15.67/11.15 15.67/11.15 16: evalfbb8in -> evalfbb10in : B'=-1+B, [ C>=1+A ], cost: 2 15.67/11.15 15.67/11.15 17: evalfbb6in -> evalfbb8in : C'=1+C, [ D>=1+C+B ], cost: 2 15.67/11.15 15.67/11.15 22: evalfbb6in -> evalfbb6in : D'=1+D, E'=1, [ C+B>=D && 1>=1+D ], cost: 3 15.67/11.15 15.67/11.15 23: evalfbb6in -> evalfbb6in : D'=1+D, E'=1+D, [ C+B>=D && D>=1 ], cost: 3+2*D 15.67/11.15 15.67/11.15 15.67/11.15 15.67/11.15 Accelerating simple loops of location 4. 15.67/11.15 15.67/11.15 Accelerating the following rules: 15.67/11.15 15.67/11.15 22: evalfbb6in -> evalfbb6in : D'=1+D, E'=1, [ C+B>=D && 1>=1+D ], cost: 3 15.67/11.15 15.67/11.15 23: evalfbb6in -> evalfbb6in : D'=1+D, E'=1+D, [ C+B>=D && D>=1 ], cost: 3+2*D 15.67/11.15 15.67/11.15 15.67/11.15 15.67/11.15 Accelerated rule 22 with backward acceleration, yielding the new rule 24. 15.67/11.15 15.67/11.15 Accelerated rule 22 with backward acceleration, yielding the new rule 25. 15.67/11.15 15.67/11.15 Accelerated rule 23 with metering function 1+C-D+B, yielding the new rule 26. 15.67/11.15 15.67/11.15 Removing the simple loops: 22 23. 15.67/11.15 15.67/11.15 15.67/11.15 15.67/11.15 Accelerated all simple loops using metering functions (where possible): 15.67/11.15 15.67/11.15 Start location: evalfstart 15.67/11.15 15.67/11.15 15: evalfstart -> evalfbb10in : A'=B, B'=A, [], cost: 2 15.67/11.15 15.67/11.15 2: evalfbb10in -> evalfbb8in : C'=1, [ B>=1 ], cost: 1 15.67/11.15 15.67/11.15 4: evalfbb8in -> evalfbb6in : D'=B, [ A>=C ], cost: 1 15.67/11.15 15.67/11.15 16: evalfbb8in -> evalfbb10in : B'=-1+B, [ C>=1+A ], cost: 2 15.67/11.15 15.67/11.15 17: evalfbb6in -> evalfbb8in : C'=1+C, [ D>=1+C+B ], cost: 2 15.67/11.15 15.67/11.15 24: evalfbb6in -> evalfbb6in : D'=1+C+B, E'=1, [ C+B>=D && 1>=1+D && 1>=1+C+B ], cost: 3+3*C-3*D+3*B 15.67/11.15 15.67/11.15 25: evalfbb6in -> evalfbb6in : D'=1, E'=1, [ C+B>=D && 1>=1+D && C+B>=0 ], cost: 3-3*D 15.67/11.15 15.67/11.15 26: evalfbb6in -> evalfbb6in : D'=1+C+B, E'=1+C+B, [ C+B>=D && D>=1 ], cost: 2+2*C+(1+C-D+B)^2-2*D+2*(1+C-D+B)*D+2*B 15.67/11.15 15.67/11.15 15.67/11.15 15.67/11.15 Chained accelerated rules (with incoming rules): 15.67/11.15 15.67/11.15 Start location: evalfstart 15.67/11.15 15.67/11.15 15: evalfstart -> evalfbb10in : A'=B, B'=A, [], cost: 2 15.67/11.15 15.67/11.15 2: evalfbb10in -> evalfbb8in : C'=1, [ B>=1 ], cost: 1 15.67/11.15 15.67/11.15 4: evalfbb8in -> evalfbb6in : D'=B, [ A>=C ], cost: 1 15.67/11.15 15.67/11.15 16: evalfbb8in -> evalfbb10in : B'=-1+B, [ C>=1+A ], cost: 2 15.67/11.15 15.67/11.15 27: evalfbb8in -> evalfbb6in : D'=1+C+B, E'=1, [ A>=C && C+B>=B && 1>=1+B && 1>=1+C+B ], cost: 4+3*C 15.67/11.15 15.67/11.15 28: evalfbb8in -> evalfbb6in : D'=1, E'=1, [ A>=C && C+B>=B && 1>=1+B && C+B>=0 ], cost: 4-3*B 15.67/11.15 15.67/11.15 29: evalfbb8in -> evalfbb6in : D'=1+C+B, E'=1+C+B, [ A>=C && C+B>=B && B>=1 ], cost: 3+2*C+2*(1+C)*B+(1+C)^2 15.67/11.15 15.67/11.15 17: evalfbb6in -> evalfbb8in : C'=1+C, [ D>=1+C+B ], cost: 2 15.67/11.15 15.67/11.15 15.67/11.15 15.67/11.15 Eliminated locations (on tree-shaped paths): 15.67/11.15 15.67/11.15 Start location: evalfstart 15.67/11.15 15.67/11.15 15: evalfstart -> evalfbb10in : A'=B, B'=A, [], cost: 2 15.67/11.15 15.67/11.15 2: evalfbb10in -> evalfbb8in : C'=1, [ B>=1 ], cost: 1 15.67/11.15 15.67/11.15 16: evalfbb8in -> evalfbb10in : B'=-1+B, [ C>=1+A ], cost: 2 15.67/11.15 15.67/11.15 30: evalfbb8in -> evalfbb8in : C'=1+C, D'=B, [ A>=C && B>=1+C+B ], cost: 3 15.67/11.15 15.67/11.15 31: evalfbb8in -> evalfbb8in : C'=1+C, D'=1+C+B, E'=1, [ A>=C && C+B>=B && 1>=1+B && 1>=1+C+B ], cost: 6+3*C 15.67/11.15 15.67/11.15 32: evalfbb8in -> evalfbb8in : C'=1+C, D'=1, E'=1, [ A>=C && C+B>=B && 1>=1+B && C+B>=0 && 1>=1+C+B ], cost: 6-3*B 15.67/11.15 15.67/11.15 33: evalfbb8in -> evalfbb8in : C'=1+C, D'=1+C+B, E'=1+C+B, [ A>=C && C+B>=B && B>=1 ], cost: 5+2*C+2*(1+C)*B+(1+C)^2 15.67/11.15 15.67/11.15 15.67/11.15 15.67/11.15 Accelerating simple loops of location 3. 15.67/11.15 15.67/11.15 Simplified some of the simple loops (and removed duplicate rules). 15.67/11.15 15.67/11.15 Accelerating the following rules: 15.67/11.15 15.67/11.15 30: evalfbb8in -> evalfbb8in : C'=1+C, D'=B, [ A>=C && B>=1+C+B ], cost: 3 15.67/11.15 15.67/11.15 31: evalfbb8in -> evalfbb8in : C'=1+C, D'=1+C+B, E'=1, [ A>=C && C+B>=B && 1>=1+B && 1>=1+C+B ], cost: 6+3*C 15.67/11.15 15.67/11.15 32: evalfbb8in -> evalfbb8in : C'=1+C, D'=1, E'=1, [ A>=C && C+B>=B && 1>=1+B && -C-B==0 ], cost: 6-3*B 15.67/11.15 15.67/11.15 33: evalfbb8in -> evalfbb8in : C'=1+C, D'=1+C+B, E'=1+C+B, [ A>=C && C+B>=B && B>=1 ], cost: 5+2*C+2*(1+C)*B+(1+C)^2 15.67/11.15 15.67/11.15 15.67/11.15 15.67/11.15 Accelerated rule 30 with backward acceleration, yielding the new rule 34. 15.67/11.15 15.67/11.15 Accelerated rule 30 with backward acceleration, yielding the new rule 35. 15.67/11.15 15.67/11.15 Accelerated rule 31 with backward acceleration, yielding the new rule 36. 15.67/11.15 15.67/11.15 Accelerated rule 31 with backward acceleration, yielding the new rule 37. 15.67/11.15 15.67/11.15 Accelerated rule 32 with metering function -C-B, yielding the new rule 38. 15.67/11.16 15.67/11.16 Accelerated rule 33 with metering function 1-C+A, yielding the new rule 39. 15.67/11.16 15.67/11.16 Nested simple loops 32 (outer loop) and 35 (inner loop) with metering function -B, resulting in the new rules: 40. 15.67/11.16 15.67/11.16 Removing the simple loops: 30 31 32 33. 15.67/11.16 15.67/11.16 15.67/11.16 15.67/11.16 Accelerated all simple loops using metering functions (where possible): 15.67/11.16 15.67/11.16 Start location: evalfstart 15.67/11.16 15.67/11.16 15: evalfstart -> evalfbb10in : A'=B, B'=A, [], cost: 2 15.67/11.16 15.67/11.16 2: evalfbb10in -> evalfbb8in : C'=1, [ B>=1 ], cost: 1 15.67/11.16 15.67/11.16 16: evalfbb8in -> evalfbb10in : B'=-1+B, [ C>=1+A ], cost: 2 15.67/11.16 15.67/11.16 34: evalfbb8in -> evalfbb8in : C'=1+A, D'=B, [ A>=C && B>=1+C+B && B>=1+A+B ], cost: 3-3*C+3*A 15.67/11.16 15.67/11.16 35: evalfbb8in -> evalfbb8in : C'=0, D'=B, [ A>=C && B>=1+C+B && A>=-1 ], cost: -3*C 15.67/11.16 15.67/11.16 36: evalfbb8in -> evalfbb8in : C'=1+A, D'=1+A+B, E'=1, [ A>=C && C+B>=B && 1>=1+B && 1>=1+C+B && A+B>=B && 1>=1+A+B ], cost: 9/2-3*(-1+C-A)*C-9/2*C+3/2*(-1+C-A)^2+9/2*A 15.67/11.16 15.67/11.16 37: evalfbb8in -> evalfbb8in : C'=1-B, D'=1, E'=1, [ A>=C && C+B>=B && 1>=1+B && 1>=1+C+B && A>=-B ], cost: 9/2-9/2*C+3/2*(-1+C+B)^2-3*C*(-1+C+B)-9/2*B 15.67/11.16 15.67/11.16 38: evalfbb8in -> evalfbb8in : C'=-B, D'=1, E'=1, [ A>=C && C+B>=B && 1>=1+B && -C-B==0 && -C-B>=1 ], cost: -6*C+3*(C+B)*B-6*B 15.67/11.16 15.67/11.16 39: evalfbb8in -> evalfbb8in : C'=1+A, D'=1+A+B, E'=1+A+B, [ A>=C && C+B>=B && B>=1 ], cost: 25/6-3*(-1+C-A)*C-(-1+C-A)*C^2-25/6*C-(-1+C-A)*B+3/2*(-1+C-A)^2+25/6*A+(-1+C-A)^2*B-1/3*(-1+C-A)^3-2*(-1+C-A)*C*B+(-1+C-A)^2*C 15.67/11.16 15.67/11.16 40: evalfbb8in -> evalfbb8in : C'=1, D'=1, E'=1, [ A>=C && B>=1+C+B && A>=0 && -B==0 && -B>=1 ], cost: 3*B^2-3*B 15.67/11.16 15.67/11.16 15.67/11.16 15.67/11.16 Chained accelerated rules (with incoming rules): 15.67/11.16 15.67/11.16 Start location: evalfstart 15.67/11.16 15.67/11.16 15: evalfstart -> evalfbb10in : A'=B, B'=A, [], cost: 2 15.67/11.16 15.67/11.16 2: evalfbb10in -> evalfbb8in : C'=1, [ B>=1 ], cost: 1 15.67/11.16 15.67/11.16 41: evalfbb10in -> evalfbb8in : C'=1+A, D'=1+A+B, E'=1+A+B, [ B>=1 && A>=1 ], cost: 1+A^2*B+49/6*A+3*A*B+5/2*A^2+1/3*A^3 15.67/11.16 15.67/11.16 16: evalfbb8in -> evalfbb10in : B'=-1+B, [ C>=1+A ], cost: 2 15.67/11.16 15.67/11.16 15.67/11.16 15.67/11.16 Eliminated locations (on tree-shaped paths): 15.67/11.16 15.67/11.16 Start location: evalfstart 15.67/11.16 15.67/11.16 15: evalfstart -> evalfbb10in : A'=B, B'=A, [], cost: 2 15.67/11.16 15.67/11.16 42: evalfbb10in -> evalfbb10in : B'=-1+B, C'=1, [ B>=1 && 1>=1+A ], cost: 3 15.67/11.16 15.67/11.16 43: evalfbb10in -> evalfbb10in : B'=-1+B, C'=1+A, D'=1+A+B, E'=1+A+B, [ B>=1 && A>=1 ], cost: 3+A^2*B+49/6*A+3*A*B+5/2*A^2+1/3*A^3 15.67/11.16 15.67/11.16 15.67/11.16 15.67/11.16 Accelerating simple loops of location 2. 15.67/11.16 15.67/11.16 Accelerating the following rules: 15.67/11.16 15.67/11.16 42: evalfbb10in -> evalfbb10in : B'=-1+B, C'=1, [ B>=1 && 1>=1+A ], cost: 3 15.67/11.16 15.67/11.16 43: evalfbb10in -> evalfbb10in : B'=-1+B, C'=1+A, D'=1+A+B, E'=1+A+B, [ B>=1 && A>=1 ], cost: 3+A^2*B+49/6*A+3*A*B+5/2*A^2+1/3*A^3 15.67/11.16 15.67/11.16 15.67/11.16 15.67/11.16 Accelerated rule 42 with metering function B, yielding the new rule 44. 15.67/11.16 15.67/11.16 Accelerated rule 43 with metering function B, yielding the new rule 45. 15.67/11.16 15.67/11.16 Removing the simple loops: 42 43. 15.67/11.16 15.67/11.16 15.67/11.16 15.67/11.16 Accelerated all simple loops using metering functions (where possible): 15.67/11.16 15.67/11.16 Start location: evalfstart 15.67/11.16 15.67/11.16 15: evalfstart -> evalfbb10in : A'=B, B'=A, [], cost: 2 15.67/11.16 15.67/11.16 44: evalfbb10in -> evalfbb10in : B'=0, C'=1, [ B>=1 && 1>=1+A ], cost: 3*B 15.67/11.16 15.67/11.16 45: evalfbb10in -> evalfbb10in : B'=0, C'=1+A, D'=2+A, E'=2+A, [ B>=1 && A>=1 ], cost: 3*A^2*B+1/2*A^2*B^2+1/3*A^3*B+3/2*A*B^2+29/3*A*B+3*B 15.67/11.16 15.67/11.16 15.67/11.16 15.67/11.16 Chained accelerated rules (with incoming rules): 15.67/11.16 15.67/11.16 Start location: evalfstart 15.67/11.16 15.67/11.16 15: evalfstart -> evalfbb10in : A'=B, B'=A, [], cost: 2 15.67/11.16 15.67/11.16 46: evalfstart -> evalfbb10in : A'=B, B'=0, C'=1, [ A>=1 && 1>=1+B ], cost: 2+3*A 15.67/11.16 15.67/11.16 47: evalfstart -> evalfbb10in : A'=B, B'=0, C'=1+B, D'=2+B, E'=2+B, [ A>=1 && B>=1 ], cost: 2+3/2*A^2*B+1/2*A^2*B^2+1/3*A*B^3+3*A*B^2+3*A+29/3*A*B 15.67/11.16 15.67/11.16 15.67/11.16 15.67/11.16 Removed unreachable locations (and leaf rules with constant cost): 15.67/11.16 15.67/11.16 Start location: evalfstart 15.67/11.16 15.67/11.16 46: evalfstart -> evalfbb10in : A'=B, B'=0, C'=1, [ A>=1 && 1>=1+B ], cost: 2+3*A 15.67/11.16 15.67/11.16 47: evalfstart -> evalfbb10in : A'=B, B'=0, C'=1+B, D'=2+B, E'=2+B, [ A>=1 && B>=1 ], cost: 2+3/2*A^2*B+1/2*A^2*B^2+1/3*A*B^3+3*A*B^2+3*A+29/3*A*B 15.67/11.16 15.67/11.16 15.67/11.16 15.67/11.16 ### Computing asymptotic complexity ### 15.67/11.16 15.67/11.16 15.67/11.16 15.67/11.16 Fully simplified ITS problem 15.67/11.16 15.67/11.16 Start location: evalfstart 15.67/11.16 15.67/11.16 46: evalfstart -> evalfbb10in : A'=B, B'=0, C'=1, [ A>=1 && 1>=1+B ], cost: 2+3*A 15.67/11.16 15.67/11.16 47: evalfstart -> evalfbb10in : A'=B, B'=0, C'=1+B, D'=2+B, E'=2+B, [ A>=1 && B>=1 ], cost: 2+3/2*A^2*B+1/2*A^2*B^2+1/3*A*B^3+3*A*B^2+3*A+29/3*A*B 15.67/11.16 15.67/11.16 15.67/11.16 15.67/11.16 Computing asymptotic complexity for rule 46 15.67/11.16 15.67/11.16 Solved the limit problem by the following transformations: 15.67/11.16 15.67/11.16 Created initial limit problem: 15.67/11.16 15.67/11.16 1-B (+/+!), A (+/+!), 2+3*A (+) [not solved] 15.67/11.16 15.67/11.16 15.67/11.16 15.67/11.16 removing all constraints (solved by SMT) 15.67/11.16 15.67/11.16 resulting limit problem: [solved] 15.67/11.16 15.67/11.16 15.67/11.16 15.67/11.16 applying transformation rule (C) using substitution {A==n,B==0} 15.67/11.16 15.67/11.16 resulting limit problem: 15.67/11.16 15.67/11.16 [solved] 15.67/11.16 15.67/11.16 15.67/11.16 15.67/11.16 Solution: 15.67/11.16 15.67/11.16 A / n 15.67/11.16 15.67/11.16 B / 0 15.67/11.16 15.67/11.16 Resulting cost 2+3*n has complexity: Poly(n^1) 15.67/11.16 15.67/11.16 15.67/11.16 15.67/11.16 Found new complexity Poly(n^1). 15.67/11.16 15.67/11.16 15.67/11.16 15.67/11.16 Computing asymptotic complexity for rule 47 15.67/11.16 15.67/11.16 Solved the limit problem by the following transformations: 15.67/11.16 15.67/11.16 Created initial limit problem: 15.67/11.16 15.67/11.16 2+3/2*A^2*B+1/2*A^2*B^2+1/3*A*B^3+3*A*B^2+3*A+29/3*A*B (+), A (+/+!), B (+/+!) [not solved] 15.67/11.16 15.67/11.16 15.67/11.16 15.67/11.16 removing all constraints (solved by SMT) 15.67/11.16 15.67/11.16 resulting limit problem: [solved] 15.67/11.16 15.67/11.16 15.67/11.16 15.67/11.16 applying transformation rule (C) using substitution {A==n,B==n} 15.67/11.16 15.67/11.16 resulting limit problem: 15.67/11.16 15.67/11.16 [solved] 15.67/11.16 15.67/11.16 15.67/11.16 15.67/11.16 Solution: 15.67/11.16 15.67/11.16 A / n 15.67/11.16 15.67/11.16 B / n 15.67/11.16 15.67/11.16 Resulting cost 2+9/2*n^3+29/3*n^2+5/6*n^4+3*n has complexity: Poly(n^4) 15.67/11.16 15.67/11.16 15.67/11.16 15.67/11.16 Found new complexity Poly(n^4). 15.67/11.16 15.67/11.16 15.67/11.16 15.67/11.16 Obtained the following overall complexity (w.r.t. the length of the input n): 15.67/11.16 15.67/11.16 Complexity: Poly(n^4) 15.67/11.16 15.67/11.16 Cpx degree: 4 15.67/11.16 15.67/11.16 Solved cost: 2+9/2*n^3+29/3*n^2+5/6*n^4+3*n 15.67/11.16 15.67/11.16 Rule cost: 2+3/2*A^2*B+1/2*A^2*B^2+1/3*A*B^3+3*A*B^2+3*A+29/3*A*B 15.67/11.16 15.67/11.16 Rule guard: [ A>=1 && B>=1 ] 15.67/11.16 15.67/11.16 15.67/11.16 15.67/11.16 WORST_CASE(Omega(n^4),?) 15.67/11.16 15.67/11.16 15.67/11.16 ---------------------------------------- 15.67/11.16 15.67/11.16 (4) 15.67/11.16 BOUNDS(n^4, INF) 15.91/11.19 EOF