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