/export/starexec/sandbox2/solver/bin/starexec_run_complexity /export/starexec/sandbox2/benchmark/theBenchmark.koat /export/starexec/sandbox2/output/output_files


--------------------------------------------------------------------------------


WORST_CASE(Omega(n^4), O(n^5))
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^4, 3 + max(1, 1 + 3 * Arg_1 * max(1, -1 + 3 * Arg_1) + min(2 + -6 * Arg_1, -2)) * nat(-1 + Arg_1) * max(3, -1 + 2 * Arg_1) * max(1, -1 + 3 * Arg_1) + nat(-4 * Arg_4) * max(1, -1 + 3 * Arg_1) + max(1, 1 + 3 * Arg_1 * max(1, -1 + 3 * Arg_1) + min(2 + -6 * Arg_1, -2)) + max(1, 1 + 3 * Arg_1 * max(1, -1 + 3 * Arg_1) + min(2 + -6 * Arg_1, -2)) * nat(-1 + Arg_1) + max(1, 1 + 3 * Arg_1 * max(1, -1 + 3 * Arg_1) + min(2 + -6 * Arg_1, -2)) * nat(-1 + Arg_1) * max(3, -1 + 2 * Arg_1) + max(1, 1 + 3 * Arg_1 * max(1, -1 + 3 * Arg_1) + min(2 + -6 * Arg_1, -2)) * max(9, -2 + 11 * Arg_1) + max(1, 1 + 3 * Arg_1 * max(1, -1 + 3 * Arg_1) + min(2 + -6 * Arg_1, -2)) * nat(-2 + 2 * Arg_1) + nat(-4 * Arg_4) + max(4 + 6 * Arg_1 * max(-2 + 6 * Arg_1, 4) + min(8 + -24 * Arg_1, -8), 4) + nat(-2 + 3 * Arg_1) + max(1, 1 + Arg_1)).

(0) CpxIntTrs
(1) Koat2 Proof [FINISHED, 10.4 s]
(2) BOUNDS(1, 3 + max(1, 1 + 3 * Arg_1 * max(1, -1 + 3 * Arg_1) + min(2 + -6 * Arg_1, -2)) * nat(-1 + Arg_1) * max(3, -1 + 2 * Arg_1) * max(1, -1 + 3 * Arg_1) + nat(-4 * Arg_4) * max(1, -1 + 3 * Arg_1) + max(1, 1 + 3 * Arg_1 * max(1, -1 + 3 * Arg_1) + min(2 + -6 * Arg_1, -2)) + max(1, 1 + 3 * Arg_1 * max(1, -1 + 3 * Arg_1) + min(2 + -6 * Arg_1, -2)) * nat(-1 + Arg_1) + max(1, 1 + 3 * Arg_1 * max(1, -1 + 3 * Arg_1) + min(2 + -6 * Arg_1, -2)) * nat(-1 + Arg_1) * max(3, -1 + 2 * Arg_1) + max(1, 1 + 3 * Arg_1 * max(1, -1 + 3 * Arg_1) + min(2 + -6 * Arg_1, -2)) * max(9, -2 + 11 * Arg_1) + max(1, 1 + 3 * Arg_1 * max(1, -1 + 3 * Arg_1) + min(2 + -6 * Arg_1, -2)) * nat(-2 + 2 * Arg_1) + nat(-4 * Arg_4) + max(4 + 6 * Arg_1 * max(-2 + 6 * Arg_1, 4) + min(8 + -24 * Arg_1, -8), 4) + nat(-2 + 3 * Arg_1) + max(1, 1 + Arg_1))
(3) Loat Proof [FINISHED, 2115 ms]
(4) BOUNDS(n^4, INF)


----------------------------------------

(0)
Obligation:
Complexity Int TRS consisting of the following rules:
evalfstart(A, B, C, D, E) -> Com_1(evalfentryin(A, B, C, D, E)) :|: TRUE
evalfentryin(A, B, C, D, E) -> Com_1(evalfbb10in(1, B, C, D, E)) :|: TRUE
evalfbb10in(A, B, C, D, E) -> Com_1(evalfbb8in(A, B, 1, D, E)) :|: B >= A
evalfbb10in(A, B, C, D, E) -> Com_1(evalfreturnin(A, B, C, D, E)) :|: A >= B + 1
evalfbb8in(A, B, C, D, E) -> Com_1(evalfbb6in(A, B, C, A + 1, E)) :|: A >= C
evalfbb8in(A, B, C, D, E) -> Com_1(evalfbb10in(A + 1, B, C, D, E)) :|: C >= A + 1
evalfbb6in(A, B, C, D, E) -> Com_1(evalfbb4in(A, B, C, D, 1)) :|: B >= D
evalfbb6in(A, B, C, D, E) -> Com_1(evalfbb7in(A, B, C, D, E)) :|: D >= B + 1
evalfbb4in(A, B, C, D, E) -> Com_1(evalfbb3in(A, B, C, D, E)) :|: D >= E
evalfbb4in(A, B, C, D, E) -> Com_1(evalfbb5in(A, B, C, D, E)) :|: E >= D + 1
evalfbb3in(A, B, C, D, E) -> Com_1(evalfbb4in(A, B, C, D, E + 1)) :|: TRUE
evalfbb5in(A, B, C, D, E) -> Com_1(evalfbb6in(A, B, C, D + 1, E)) :|: TRUE
evalfbb7in(A, B, C, D, E) -> Com_1(evalfbb8in(A, B, C + 1, D, E)) :|: TRUE
evalfreturnin(A, B, C, D, E) -> Com_1(evalfstop(A, B, C, D, E)) :|: TRUE

The start-symbols are:[evalfstart_5]


----------------------------------------

(1) Koat2 Proof (FINISHED)
YES( ?, 3+max([1, 1+(-2+3*Arg_1)*max([1, -1+3*Arg_1])])*max([0, -1+Arg_1])+max([1, 1+(-2+3*Arg_1)*max([1, -1+3*Arg_1])])*max([9, -2+11*Arg_1])+max([1, 1+(-2+3*Arg_1)*max([1, -1+3*Arg_1])])*max([0, -2+2*Arg_1])+(max([1, 1+(-2+3*Arg_1)*max([1, -1+3*Arg_1])])*max([0, -1+Arg_1])*max([3, -1+2*Arg_1])+max([0, -4*Arg_4]))*max([1, -1+3*Arg_1])+max([1, 1+(-2+3*Arg_1)*max([1, -1+3*Arg_1])])*max([0, -1+Arg_1])*max([3, -1+2*Arg_1])+max([1, 1+(-2+3*Arg_1)*max([1, -1+3*Arg_1])])+max([2, 2+(-2+3*Arg_1)*max([4, 2*max([1, -1+3*Arg_1])])])+max([0, -2+3*Arg_1])+max([1, 1+Arg_1])+max([2, 2+(-2+3*Arg_1)*max([4, 2*max([1, -1+3*Arg_1])])])+max([0, -4*Arg_4]) {O(n^5)})



Initial Complexity Problem:

  Start:  evalfstart  

  Program_Vars:  Arg_0, Arg_1, Arg_2, Arg_3, Arg_4  

  Temp_Vars:    

  Locations:  evalfbb10in, evalfbb3in, evalfbb4in, evalfbb5in, evalfbb6in, evalfbb7in, evalfbb8in, evalfentryin, evalfreturnin, evalfstart, evalfstop  

  Transitions:

  evalfbb10in(Arg_0,Arg_1,Arg_2,Arg_3,Arg_4) -> evalfbb8in(Arg_0,Arg_1,1,Arg_3,Arg_4):|:1 <= Arg_0 && Arg_0 <= Arg_1

  evalfbb10in(Arg_0,Arg_1,Arg_2,Arg_3,Arg_4) -> evalfreturnin(Arg_0,Arg_1,Arg_2,Arg_3,Arg_4):|:1 <= Arg_0 && Arg_1+1 <= Arg_0

  evalfbb3in(Arg_0,Arg_1,Arg_2,Arg_3,Arg_4) -> evalfbb4in(Arg_0,Arg_1,Arg_2,Arg_3,Arg_4+1):|:1 <= Arg_4 && 3 <= Arg_3+Arg_4 && 2 <= Arg_2+Arg_4 && 3 <= Arg_1+Arg_4 && 2 <= Arg_0+Arg_4 && Arg_3 <= Arg_1 && 2 <= Arg_3 && 3 <= Arg_2+Arg_3 && 1+Arg_2 <= Arg_3 && 4 <= Arg_1+Arg_3 && 3 <= Arg_0+Arg_3 && 1+Arg_0 <= Arg_3 && 1+Arg_2 <= Arg_1 && Arg_2 <= Arg_0 && 1 <= Arg_2 && 3 <= Arg_1+Arg_2 && 2 <= Arg_0+Arg_2 && 2 <= Arg_1 && 3 <= Arg_0+Arg_1 && 1+Arg_0 <= Arg_1 && 1 <= Arg_0

  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 && 3 <= Arg_3+Arg_4 && 2 <= Arg_2+Arg_4 && 3 <= Arg_1+Arg_4 && 2 <= Arg_0+Arg_4 && Arg_3 <= Arg_1 && 2 <= Arg_3 && 3 <= Arg_2+Arg_3 && 1+Arg_2 <= Arg_3 && 4 <= Arg_1+Arg_3 && 3 <= Arg_0+Arg_3 && 1+Arg_0 <= Arg_3 && 1+Arg_2 <= Arg_1 && Arg_2 <= Arg_0 && 1 <= Arg_2 && 3 <= Arg_1+Arg_2 && 2 <= Arg_0+Arg_2 && 2 <= Arg_1 && 3 <= Arg_0+Arg_1 && 1+Arg_0 <= Arg_1 && 1 <= Arg_0 && Arg_4 <= Arg_3

  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 && 3 <= Arg_3+Arg_4 && 2 <= Arg_2+Arg_4 && 3 <= Arg_1+Arg_4 && 2 <= Arg_0+Arg_4 && Arg_3 <= Arg_1 && 2 <= Arg_3 && 3 <= Arg_2+Arg_3 && 1+Arg_2 <= Arg_3 && 4 <= Arg_1+Arg_3 && 3 <= Arg_0+Arg_3 && 1+Arg_0 <= Arg_3 && 1+Arg_2 <= Arg_1 && Arg_2 <= Arg_0 && 1 <= Arg_2 && 3 <= Arg_1+Arg_2 && 2 <= Arg_0+Arg_2 && 2 <= Arg_1 && 3 <= Arg_0+Arg_1 && 1+Arg_0 <= Arg_1 && 1 <= Arg_0 && Arg_3+1 <= Arg_4

  evalfbb5in(Arg_0,Arg_1,Arg_2,Arg_3,Arg_4) -> evalfbb6in(Arg_0,Arg_1,Arg_2,Arg_3+1,Arg_4):|:3 <= Arg_4 && 5 <= Arg_3+Arg_4 && 1+Arg_3 <= Arg_4 && 4 <= Arg_2+Arg_4 && 2+Arg_2 <= Arg_4 && 5 <= Arg_1+Arg_4 && 4 <= Arg_0+Arg_4 && 2+Arg_0 <= Arg_4 && Arg_3 <= Arg_1 && 2 <= Arg_3 && 3 <= Arg_2+Arg_3 && 1+Arg_2 <= Arg_3 && 4 <= Arg_1+Arg_3 && 3 <= Arg_0+Arg_3 && 1+Arg_0 <= Arg_3 && 1+Arg_2 <= Arg_1 && Arg_2 <= Arg_0 && 1 <= Arg_2 && 3 <= Arg_1+Arg_2 && 2 <= Arg_0+Arg_2 && 2 <= Arg_1 && 3 <= Arg_0+Arg_1 && 1+Arg_0 <= Arg_1 && 1 <= Arg_0

  evalfbb6in(Arg_0,Arg_1,Arg_2,Arg_3,Arg_4) -> evalfbb4in(Arg_0,Arg_1,Arg_2,Arg_3,1):|:Arg_3 <= 1+Arg_1 && 2 <= Arg_3 && 3 <= Arg_2+Arg_3 && 1+Arg_2 <= Arg_3 && 3 <= Arg_1+Arg_3 && 3 <= Arg_0+Arg_3 && 1+Arg_0 <= Arg_3 && Arg_2 <= Arg_1 && 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 && Arg_0 <= Arg_1 && 1 <= Arg_0 && Arg_3 <= Arg_1

  evalfbb6in(Arg_0,Arg_1,Arg_2,Arg_3,Arg_4) -> evalfbb7in(Arg_0,Arg_1,Arg_2,Arg_3,Arg_4):|:Arg_3 <= 1+Arg_1 && 2 <= Arg_3 && 3 <= Arg_2+Arg_3 && 1+Arg_2 <= Arg_3 && 3 <= Arg_1+Arg_3 && 3 <= Arg_0+Arg_3 && 1+Arg_0 <= Arg_3 && Arg_2 <= Arg_1 && 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 && Arg_0 <= Arg_1 && 1 <= Arg_0 && Arg_1+1 <= Arg_3

  evalfbb7in(Arg_0,Arg_1,Arg_2,Arg_3,Arg_4) -> evalfbb8in(Arg_0,Arg_1,Arg_2+1,Arg_3,Arg_4):|:Arg_3 <= 1+Arg_1 && 2 <= Arg_3 && 3 <= Arg_2+Arg_3 && 1+Arg_2 <= Arg_3 && 3 <= Arg_1+Arg_3 && 1+Arg_1 <= Arg_3 && 3 <= Arg_0+Arg_3 && 1+Arg_0 <= Arg_3 && Arg_2 <= Arg_1 && 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 && Arg_0 <= Arg_1 && 1 <= Arg_0

  evalfbb8in(Arg_0,Arg_1,Arg_2,Arg_3,Arg_4) -> evalfbb10in(Arg_0+1,Arg_1,Arg_2,Arg_3,Arg_4):|:1 <= Arg_2 && 2 <= Arg_1+Arg_2 && 2 <= Arg_0+Arg_2 && 1 <= Arg_1 && 2 <= Arg_0+Arg_1 && Arg_0 <= Arg_1 && 1 <= Arg_0 && Arg_0+1 <= Arg_2

  evalfbb8in(Arg_0,Arg_1,Arg_2,Arg_3,Arg_4) -> evalfbb6in(Arg_0,Arg_1,Arg_2,Arg_0+1,Arg_4):|:1 <= Arg_2 && 2 <= Arg_1+Arg_2 && 2 <= Arg_0+Arg_2 && 1 <= Arg_1 && 2 <= Arg_0+Arg_1 && Arg_0 <= Arg_1 && 1 <= Arg_0 && Arg_2 <= Arg_0

  evalfentryin(Arg_0,Arg_1,Arg_2,Arg_3,Arg_4) -> evalfbb10in(1,Arg_1,Arg_2,Arg_3,Arg_4):|:

  evalfreturnin(Arg_0,Arg_1,Arg_2,Arg_3,Arg_4) -> evalfstop(Arg_0,Arg_1,Arg_2,Arg_3,Arg_4):|:1+Arg_1 <= Arg_0 && 1 <= Arg_0

  evalfstart(Arg_0,Arg_1,Arg_2,Arg_3,Arg_4) -> evalfentryin(Arg_0,Arg_1,Arg_2,Arg_3,Arg_4):|:  



Timebounds: 

  Overall timebound: 3+max([1, 1+(-2+3*Arg_1)*max([1, -1+3*Arg_1])])*max([0, -1+Arg_1])+max([1, 1+(-2+3*Arg_1)*max([1, -1+3*Arg_1])])*max([9, -2+11*Arg_1])+max([1, 1+(-2+3*Arg_1)*max([1, -1+3*Arg_1])])*max([0, -2+2*Arg_1])+(max([1, 1+(-2+3*Arg_1)*max([1, -1+3*Arg_1])])*max([0, -1+Arg_1])*max([3, -1+2*Arg_1])+max([0, -4*Arg_4]))*max([1, -1+3*Arg_1])+max([1, 1+(-2+3*Arg_1)*max([1, -1+3*Arg_1])])*max([0, -1+Arg_1])*max([3, -1+2*Arg_1])+max([1, 1+(-2+3*Arg_1)*max([1, -1+3*Arg_1])])+max([2, 2+(-2+3*Arg_1)*max([4, 2*max([1, -1+3*Arg_1])])])+max([0, -2+3*Arg_1])+max([1, 1+Arg_1])+max([2, 2+(-2+3*Arg_1)*max([4, 2*max([1, -1+3*Arg_1])])])+max([0, -4*Arg_4]) {O(n^5)}

  2: evalfbb10in->evalfbb8in: max([0, Arg_1]) {O(n)}

  3: evalfbb10in->evalfreturnin: 1 {O(1)}

  10: evalfbb3in->evalfbb4in: (max([1, 1+(-2+3*Arg_1)*max([1, -1+3*Arg_1])])*max([0, -1+Arg_1])*max([3, -1+2*Arg_1])+max([0, -4*Arg_4]))*max([1, -1+3*Arg_1]) {O(n^5)}

  8: evalfbb4in->evalfbb3in: max([1, 1+(-2+3*Arg_1)*max([1, -1+3*Arg_1])])*max([0, -1+Arg_1])*max([3, -1+2*Arg_1])+max([0, -4*Arg_4]) {O(n^4)}

  9: evalfbb4in->evalfbb5in: max([1, 1+(-2+3*Arg_1)*max([1, -1+3*Arg_1])])*max([0, -2+2*Arg_1]) {O(n^3)}

  11: evalfbb5in->evalfbb6in: max([1, 1+(-2+3*Arg_1)*max([1, -1+3*Arg_1])])*max([9, -2+11*Arg_1]) {O(n^3)}

  6: evalfbb6in->evalfbb4in: max([1, 1+(-2+3*Arg_1)*max([1, -1+3*Arg_1])])*max([0, -1+Arg_1]) {O(n^3)}

  7: evalfbb6in->evalfbb7in: max([2, 2+(-2+3*Arg_1)*max([4, 2*max([1, -1+3*Arg_1])])]) {O(n^2)}

  12: evalfbb7in->evalfbb8in: max([2, 2+(-2+3*Arg_1)*max([4, 2*max([1, -1+3*Arg_1])])]) {O(n^2)}

  4: evalfbb8in->evalfbb6in: max([1, 1+(-2+3*Arg_1)*max([1, -1+3*Arg_1])]) {O(n^2)}

  5: evalfbb8in->evalfbb10in: max([0, -2+3*Arg_1]) {O(n)}

  1: evalfentryin->evalfbb10in: 1 {O(1)}

  13: evalfreturnin->evalfstop: 1 {O(1)}

  0: evalfstart->evalfentryin: 1 {O(1)}



Costbounds:

  Overall costbound: 3+max([1, 1+(-2+3*Arg_1)*max([1, -1+3*Arg_1])])*max([0, -1+Arg_1])+max([1, 1+(-2+3*Arg_1)*max([1, -1+3*Arg_1])])*max([9, -2+11*Arg_1])+max([1, 1+(-2+3*Arg_1)*max([1, -1+3*Arg_1])])*max([0, -2+2*Arg_1])+(max([1, 1+(-2+3*Arg_1)*max([1, -1+3*Arg_1])])*max([0, -1+Arg_1])*max([3, -1+2*Arg_1])+max([0, -4*Arg_4]))*max([1, -1+3*Arg_1])+max([1, 1+(-2+3*Arg_1)*max([1, -1+3*Arg_1])])*max([0, -1+Arg_1])*max([3, -1+2*Arg_1])+max([1, 1+(-2+3*Arg_1)*max([1, -1+3*Arg_1])])+max([2, 2+(-2+3*Arg_1)*max([4, 2*max([1, -1+3*Arg_1])])])+max([0, -2+3*Arg_1])+max([1, 1+Arg_1])+max([2, 2+(-2+3*Arg_1)*max([4, 2*max([1, -1+3*Arg_1])])])+max([0, -4*Arg_4]) {O(n^5)}

  2: evalfbb10in->evalfbb8in: max([0, Arg_1]) {O(n)}

  3: evalfbb10in->evalfreturnin: 1 {O(1)}

  10: evalfbb3in->evalfbb4in: (max([1, 1+(-2+3*Arg_1)*max([1, -1+3*Arg_1])])*max([0, -1+Arg_1])*max([3, -1+2*Arg_1])+max([0, -4*Arg_4]))*max([1, -1+3*Arg_1]) {O(n^5)}

  8: evalfbb4in->evalfbb3in: max([1, 1+(-2+3*Arg_1)*max([1, -1+3*Arg_1])])*max([0, -1+Arg_1])*max([3, -1+2*Arg_1])+max([0, -4*Arg_4]) {O(n^4)}

  9: evalfbb4in->evalfbb5in: max([1, 1+(-2+3*Arg_1)*max([1, -1+3*Arg_1])])*max([0, -2+2*Arg_1]) {O(n^3)}

  11: evalfbb5in->evalfbb6in: max([1, 1+(-2+3*Arg_1)*max([1, -1+3*Arg_1])])*max([9, -2+11*Arg_1]) {O(n^3)}

  6: evalfbb6in->evalfbb4in: max([1, 1+(-2+3*Arg_1)*max([1, -1+3*Arg_1])])*max([0, -1+Arg_1]) {O(n^3)}

  7: evalfbb6in->evalfbb7in: max([2, 2+(-2+3*Arg_1)*max([4, 2*max([1, -1+3*Arg_1])])]) {O(n^2)}

  12: evalfbb7in->evalfbb8in: max([2, 2+(-2+3*Arg_1)*max([4, 2*max([1, -1+3*Arg_1])])]) {O(n^2)}

  4: evalfbb8in->evalfbb6in: max([1, 1+(-2+3*Arg_1)*max([1, -1+3*Arg_1])]) {O(n^2)}

  5: evalfbb8in->evalfbb10in: max([0, -2+3*Arg_1]) {O(n)}

  1: evalfentryin->evalfbb10in: 1 {O(1)}

  13: evalfreturnin->evalfstop: 1 {O(1)}

  0: evalfstart->evalfentryin: 1 {O(1)}



Sizebounds:

`Lower:

  2: evalfbb10in->evalfbb8in, Arg_0: 1 {O(1)}

  2: evalfbb10in->evalfbb8in, Arg_1: 1 {O(1)}

  2: evalfbb10in->evalfbb8in, Arg_2: 1 {O(1)}

  2: evalfbb10in->evalfbb8in, Arg_3: min([2, Arg_3]) {O(n)}

  2: evalfbb10in->evalfbb8in, Arg_4: min([3, Arg_4]) {O(n)}

  3: evalfbb10in->evalfreturnin, Arg_0: 1 {O(1)}

  3: evalfbb10in->evalfreturnin, Arg_1: min([1, Arg_1]) {O(n)}

  3: evalfbb10in->evalfreturnin, Arg_2: min([2, Arg_2]) {O(n)}

  3: evalfbb10in->evalfreturnin, Arg_3: min([2, Arg_3]) {O(n)}

  3: evalfbb10in->evalfreturnin, Arg_4: min([3, Arg_4]) {O(n)}

  10: evalfbb3in->evalfbb4in, Arg_0: 1 {O(1)}

  10: evalfbb3in->evalfbb4in, Arg_1: 2 {O(1)}

  10: evalfbb3in->evalfbb4in, Arg_2: 1 {O(1)}

  10: evalfbb3in->evalfbb4in, Arg_3: 2 {O(1)}

  10: evalfbb3in->evalfbb4in, Arg_4: 2 {O(1)}

  8: evalfbb4in->evalfbb3in, Arg_0: 1 {O(1)}

  8: evalfbb4in->evalfbb3in, Arg_1: 2 {O(1)}

  8: evalfbb4in->evalfbb3in, Arg_2: 1 {O(1)}

  8: evalfbb4in->evalfbb3in, Arg_3: 2 {O(1)}

  8: evalfbb4in->evalfbb3in, Arg_4: 1 {O(1)}

  9: evalfbb4in->evalfbb5in, Arg_0: 1 {O(1)}

  9: evalfbb4in->evalfbb5in, Arg_1: 2 {O(1)}

  9: evalfbb4in->evalfbb5in, Arg_2: 1 {O(1)}

  9: evalfbb4in->evalfbb5in, Arg_3: 2 {O(1)}

  9: evalfbb4in->evalfbb5in, Arg_4: 3 {O(1)}

  11: evalfbb5in->evalfbb6in, Arg_0: 1 {O(1)}

  11: evalfbb5in->evalfbb6in, Arg_1: 2 {O(1)}

  11: evalfbb5in->evalfbb6in, Arg_2: 1 {O(1)}

  11: evalfbb5in->evalfbb6in, Arg_3: 3 {O(1)}

  11: evalfbb5in->evalfbb6in, Arg_4: 3 {O(1)}

  6: evalfbb6in->evalfbb4in, Arg_0: 1 {O(1)}

  6: evalfbb6in->evalfbb4in, Arg_1: 2 {O(1)}

  6: evalfbb6in->evalfbb4in, Arg_2: 1 {O(1)}

  6: evalfbb6in->evalfbb4in, Arg_3: 2 {O(1)}

  6: evalfbb6in->evalfbb4in, Arg_4: 1 {O(1)}

  7: evalfbb6in->evalfbb7in, Arg_0: 1 {O(1)}

  7: evalfbb6in->evalfbb7in, Arg_1: 1 {O(1)}

  7: evalfbb6in->evalfbb7in, Arg_2: 1 {O(1)}

  7: evalfbb6in->evalfbb7in, Arg_3: 2 {O(1)}

  7: evalfbb6in->evalfbb7in, Arg_4: min([3, Arg_4]) {O(n)}

  12: evalfbb7in->evalfbb8in, Arg_0: 1 {O(1)}

  12: evalfbb7in->evalfbb8in, Arg_1: 1 {O(1)}

  12: evalfbb7in->evalfbb8in, Arg_2: 2 {O(1)}

  12: evalfbb7in->evalfbb8in, Arg_3: 2 {O(1)}

  12: evalfbb7in->evalfbb8in, Arg_4: min([3, Arg_4]) {O(n)}

  4: evalfbb8in->evalfbb6in, Arg_0: 1 {O(1)}

  4: evalfbb8in->evalfbb6in, Arg_1: 1 {O(1)}

  4: evalfbb8in->evalfbb6in, Arg_2: 1 {O(1)}

  4: evalfbb8in->evalfbb6in, Arg_3: 2 {O(1)}

  4: evalfbb8in->evalfbb6in, Arg_4: min([3, Arg_4]) {O(n)}

  5: evalfbb8in->evalfbb10in, Arg_0: 2 {O(1)}

  5: evalfbb8in->evalfbb10in, Arg_1: 1 {O(1)}

  5: evalfbb8in->evalfbb10in, Arg_2: 2 {O(1)}

  5: evalfbb8in->evalfbb10in, Arg_3: 2 {O(1)}

  5: evalfbb8in->evalfbb10in, Arg_4: min([3, Arg_4]) {O(n)}

  1: evalfentryin->evalfbb10in, Arg_0: 1 {O(1)}

  1: evalfentryin->evalfbb10in, Arg_1: Arg_1 {O(n)}

  1: evalfentryin->evalfbb10in, Arg_2: Arg_2 {O(n)}

  1: evalfentryin->evalfbb10in, Arg_3: Arg_3 {O(n)}

  1: evalfentryin->evalfbb10in, Arg_4: Arg_4 {O(n)}

  13: evalfreturnin->evalfstop, Arg_0: 1 {O(1)}

  13: evalfreturnin->evalfstop, Arg_1: min([1, Arg_1]) {O(n)}

  13: evalfreturnin->evalfstop, Arg_2: min([2, Arg_2]) {O(n)}

  13: evalfreturnin->evalfstop, Arg_3: min([2, Arg_3]) {O(n)}

  13: evalfreturnin->evalfstop, Arg_4: min([3, Arg_4]) {O(n)}

  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)}

`Upper:

  2: evalfbb10in->evalfbb8in, Arg_0: max([1, -1+3*Arg_1]) {O(n)}

  2: evalfbb10in->evalfbb8in, Arg_1: Arg_1 {O(n)}

  2: evalfbb10in->evalfbb8in, Arg_2: 1 {O(1)}

  2: evalfbb10in->evalfbb8in, Arg_3: max([2, max([Arg_3, max([max([1, 1+(-2+3*Arg_1)*max([1, -1+3*Arg_1])])*max([9, -2+11*Arg_1])+max([2, 3*Arg_1]), 3*Arg_1])])]) {O(n^3)}

  2: evalfbb10in->evalfbb8in, Arg_4: max([Arg_4, 1+(max([1, 1+(-2+3*Arg_1)*max([1, -1+3*Arg_1])])*max([0, -1+Arg_1])*max([3, -1+2*Arg_1])+max([0, -4*Arg_4]))*max([1, -1+3*Arg_1])]) {O(n^5)}

  3: evalfbb10in->evalfreturnin, Arg_0: max([1, max([1, -1+3*Arg_1])]) {O(n)}

  3: evalfbb10in->evalfreturnin, Arg_1: Arg_1 {O(n)}

  3: evalfbb10in->evalfreturnin, Arg_2: max([3, max([Arg_2, 3+(-2+3*Arg_1)*max([4, 2*max([1, -1+3*Arg_1])])])]) {O(n^2)}

  3: evalfbb10in->evalfreturnin, Arg_3: max([2, max([Arg_3, max([max([1, 1+(-2+3*Arg_1)*max([1, -1+3*Arg_1])])*max([9, -2+11*Arg_1])+max([2, 3*Arg_1]), 3*Arg_1])])]) {O(n^3)}

  3: evalfbb10in->evalfreturnin, Arg_4: max([Arg_4, max([Arg_4, 1+(max([1, 1+(-2+3*Arg_1)*max([1, -1+3*Arg_1])])*max([0, -1+Arg_1])*max([3, -1+2*Arg_1])+max([0, -4*Arg_4]))*max([1, -1+3*Arg_1])])]) {O(n^5)}

  10: evalfbb3in->evalfbb4in, Arg_0: max([1, -1+3*Arg_1]) {O(n)}

  10: evalfbb3in->evalfbb4in, Arg_1: Arg_1 {O(n)}

  10: evalfbb3in->evalfbb4in, Arg_2: max([3, 3+(-2+3*Arg_1)*max([4, 2*max([1, -1+3*Arg_1])])]) {O(n^2)}

  10: evalfbb3in->evalfbb4in, Arg_3: max([1, 1+(-2+3*Arg_1)*max([1, -1+3*Arg_1])])*max([9, -2+11*Arg_1])+max([2, 3*Arg_1]) {O(n^3)}

  10: evalfbb3in->evalfbb4in, Arg_4: 1+(max([1, 1+(-2+3*Arg_1)*max([1, -1+3*Arg_1])])*max([0, -1+Arg_1])*max([3, -1+2*Arg_1])+max([0, -4*Arg_4]))*max([1, -1+3*Arg_1]) {O(n^5)}

  8: evalfbb4in->evalfbb3in, Arg_0: max([1, -1+3*Arg_1]) {O(n)}

  8: evalfbb4in->evalfbb3in, Arg_1: Arg_1 {O(n)}

  8: evalfbb4in->evalfbb3in, Arg_2: max([3, 3+(-2+3*Arg_1)*max([4, 2*max([1, -1+3*Arg_1])])]) {O(n^2)}

  8: evalfbb4in->evalfbb3in, Arg_3: max([1, 1+(-2+3*Arg_1)*max([1, -1+3*Arg_1])])*max([9, -2+11*Arg_1])+max([2, 3*Arg_1]) {O(n^3)}

  8: evalfbb4in->evalfbb3in, Arg_4: 1+(max([1, 1+(-2+3*Arg_1)*max([1, -1+3*Arg_1])])*max([0, -1+Arg_1])*max([3, -1+2*Arg_1])+max([0, -4*Arg_4]))*max([1, -1+3*Arg_1]) {O(n^5)}

  9: evalfbb4in->evalfbb5in, Arg_0: max([1, -1+3*Arg_1]) {O(n)}

  9: evalfbb4in->evalfbb5in, Arg_1: Arg_1 {O(n)}

  9: evalfbb4in->evalfbb5in, Arg_2: max([3, 3+(-2+3*Arg_1)*max([4, 2*max([1, -1+3*Arg_1])])]) {O(n^2)}

  9: evalfbb4in->evalfbb5in, Arg_3: max([1, 1+(-2+3*Arg_1)*max([1, -1+3*Arg_1])])*max([9, -2+11*Arg_1])+max([2, 3*Arg_1]) {O(n^3)}

  9: evalfbb4in->evalfbb5in, Arg_4: 1+(max([1, 1+(-2+3*Arg_1)*max([1, -1+3*Arg_1])])*max([0, -1+Arg_1])*max([3, -1+2*Arg_1])+max([0, -4*Arg_4]))*max([1, -1+3*Arg_1]) {O(n^5)}

  11: evalfbb5in->evalfbb6in, Arg_0: max([1, -1+3*Arg_1]) {O(n)}

  11: evalfbb5in->evalfbb6in, Arg_1: Arg_1 {O(n)}

  11: evalfbb5in->evalfbb6in, Arg_2: max([3, 3+(-2+3*Arg_1)*max([4, 2*max([1, -1+3*Arg_1])])]) {O(n^2)}

  11: evalfbb5in->evalfbb6in, Arg_3: max([1, 1+(-2+3*Arg_1)*max([1, -1+3*Arg_1])])*max([9, -2+11*Arg_1])+max([2, 3*Arg_1]) {O(n^3)}

  11: evalfbb5in->evalfbb6in, Arg_4: 1+(max([1, 1+(-2+3*Arg_1)*max([1, -1+3*Arg_1])])*max([0, -1+Arg_1])*max([3, -1+2*Arg_1])+max([0, -4*Arg_4]))*max([1, -1+3*Arg_1]) {O(n^5)}

  6: evalfbb6in->evalfbb4in, Arg_0: max([1, -1+3*Arg_1]) {O(n)}

  6: evalfbb6in->evalfbb4in, Arg_1: Arg_1 {O(n)}

  6: evalfbb6in->evalfbb4in, Arg_2: max([3, 3+(-2+3*Arg_1)*max([4, 2*max([1, -1+3*Arg_1])])]) {O(n^2)}

  6: evalfbb6in->evalfbb4in, Arg_3: max([1, 1+(-2+3*Arg_1)*max([1, -1+3*Arg_1])])*max([9, -2+11*Arg_1])+max([2, 3*Arg_1]) {O(n^3)}

  6: evalfbb6in->evalfbb4in, Arg_4: 1 {O(1)}

  7: evalfbb6in->evalfbb7in, Arg_0: max([1, -1+3*Arg_1]) {O(n)}

  7: evalfbb6in->evalfbb7in, Arg_1: Arg_1 {O(n)}

  7: evalfbb6in->evalfbb7in, Arg_2: max([3, 3+(-2+3*Arg_1)*max([4, 2*max([1, -1+3*Arg_1])])]) {O(n^2)}

  7: evalfbb6in->evalfbb7in, Arg_3: max([2, max([max([1, 1+(-2+3*Arg_1)*max([1, -1+3*Arg_1])])*max([9, -2+11*Arg_1])+max([2, 3*Arg_1]), 3*Arg_1])]) {O(n^3)}

  7: evalfbb6in->evalfbb7in, Arg_4: max([Arg_4, 1+(max([1, 1+(-2+3*Arg_1)*max([1, -1+3*Arg_1])])*max([0, -1+Arg_1])*max([3, -1+2*Arg_1])+max([0, -4*Arg_4]))*max([1, -1+3*Arg_1])]) {O(n^5)}

  12: evalfbb7in->evalfbb8in, Arg_0: max([1, -1+3*Arg_1]) {O(n)}

  12: evalfbb7in->evalfbb8in, Arg_1: Arg_1 {O(n)}

  12: evalfbb7in->evalfbb8in, Arg_2: max([3, 3+(-2+3*Arg_1)*max([4, 2*max([1, -1+3*Arg_1])])]) {O(n^2)}

  12: evalfbb7in->evalfbb8in, Arg_3: max([2, max([max([1, 1+(-2+3*Arg_1)*max([1, -1+3*Arg_1])])*max([9, -2+11*Arg_1])+max([2, 3*Arg_1]), 3*Arg_1])]) {O(n^3)}

  12: evalfbb7in->evalfbb8in, Arg_4: max([Arg_4, 1+(max([1, 1+(-2+3*Arg_1)*max([1, -1+3*Arg_1])])*max([0, -1+Arg_1])*max([3, -1+2*Arg_1])+max([0, -4*Arg_4]))*max([1, -1+3*Arg_1])]) {O(n^5)}

  4: evalfbb8in->evalfbb6in, Arg_0: max([1, -1+3*Arg_1]) {O(n)}

  4: evalfbb8in->evalfbb6in, Arg_1: Arg_1 {O(n)}

  4: evalfbb8in->evalfbb6in, Arg_2: max([3, 3+(-2+3*Arg_1)*max([4, 2*max([1, -1+3*Arg_1])])]) {O(n^2)}

  4: evalfbb8in->evalfbb6in, Arg_3: max([2, 3*Arg_1]) {O(n)}

  4: evalfbb8in->evalfbb6in, Arg_4: max([Arg_4, 1+(max([1, 1+(-2+3*Arg_1)*max([1, -1+3*Arg_1])])*max([0, -1+Arg_1])*max([3, -1+2*Arg_1])+max([0, -4*Arg_4]))*max([1, -1+3*Arg_1])]) {O(n^5)}

  5: evalfbb8in->evalfbb10in, Arg_0: max([1, -1+3*Arg_1]) {O(n)}

  5: evalfbb8in->evalfbb10in, Arg_1: Arg_1 {O(n)}

  5: evalfbb8in->evalfbb10in, Arg_2: max([3, 3+(-2+3*Arg_1)*max([4, 2*max([1, -1+3*Arg_1])])]) {O(n^2)}

  5: evalfbb8in->evalfbb10in, Arg_3: max([2, max([max([1, 1+(-2+3*Arg_1)*max([1, -1+3*Arg_1])])*max([9, -2+11*Arg_1])+max([2, 3*Arg_1]), 3*Arg_1])]) {O(n^3)}

  5: evalfbb8in->evalfbb10in, Arg_4: max([Arg_4, 1+(max([1, 1+(-2+3*Arg_1)*max([1, -1+3*Arg_1])])*max([0, -1+Arg_1])*max([3, -1+2*Arg_1])+max([0, -4*Arg_4]))*max([1, -1+3*Arg_1])]) {O(n^5)}

  1: evalfentryin->evalfbb10in, Arg_0: 1 {O(1)}

  1: evalfentryin->evalfbb10in, Arg_1: Arg_1 {O(n)}

  1: evalfentryin->evalfbb10in, Arg_2: Arg_2 {O(n)}

  1: evalfentryin->evalfbb10in, Arg_3: Arg_3 {O(n)}

  1: evalfentryin->evalfbb10in, Arg_4: Arg_4 {O(n)}

  13: evalfreturnin->evalfstop, Arg_0: max([1, max([1, -1+3*Arg_1])]) {O(n)}

  13: evalfreturnin->evalfstop, Arg_1: Arg_1 {O(n)}

  13: evalfreturnin->evalfstop, Arg_2: max([3, max([Arg_2, 3+(-2+3*Arg_1)*max([4, 2*max([1, -1+3*Arg_1])])])]) {O(n^2)}

  13: evalfreturnin->evalfstop, Arg_3: max([2, max([Arg_3, max([max([1, 1+(-2+3*Arg_1)*max([1, -1+3*Arg_1])])*max([9, -2+11*Arg_1])+max([2, 3*Arg_1]), 3*Arg_1])])]) {O(n^3)}

  13: evalfreturnin->evalfstop, Arg_4: max([Arg_4, max([Arg_4, 1+(max([1, 1+(-2+3*Arg_1)*max([1, -1+3*Arg_1])])*max([0, -1+Arg_1])*max([3, -1+2*Arg_1])+max([0, -4*Arg_4]))*max([1, -1+3*Arg_1])])]) {O(n^5)}

  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)}


----------------------------------------

(2)
BOUNDS(1, 3 + max(1, 1 + 3 * Arg_1 * max(1, -1 + 3 * Arg_1) + min(2 + -6 * Arg_1, -2)) * nat(-1 + Arg_1) * max(3, -1 + 2 * Arg_1) * max(1, -1 + 3 * Arg_1) + nat(-4 * Arg_4) * max(1, -1 + 3 * Arg_1) + max(1, 1 + 3 * Arg_1 * max(1, -1 + 3 * Arg_1) + min(2 + -6 * Arg_1, -2)) + max(1, 1 + 3 * Arg_1 * max(1, -1 + 3 * Arg_1) + min(2 + -6 * Arg_1, -2)) * nat(-1 + Arg_1) + max(1, 1 + 3 * Arg_1 * max(1, -1 + 3 * Arg_1) + min(2 + -6 * Arg_1, -2)) * nat(-1 + Arg_1) * max(3, -1 + 2 * Arg_1) + max(1, 1 + 3 * Arg_1 * max(1, -1 + 3 * Arg_1) + min(2 + -6 * Arg_1, -2)) * max(9, -2 + 11 * Arg_1) + max(1, 1 + 3 * Arg_1 * max(1, -1 + 3 * Arg_1) + min(2 + -6 * Arg_1, -2)) * nat(-2 + 2 * Arg_1) + nat(-4 * Arg_4) + max(4 + 6 * Arg_1 * max(-2 + 6 * Arg_1, 4) + min(8 + -24 * Arg_1, -8), 4) + nat(-2 + 3 * Arg_1) + max(1, 1 + 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 -> evalfbb10in : A'=1, [], cost: 1

      2: evalfbb10in -> evalfbb8in : C'=1, [ B>=A ], cost: 1

      3: evalfbb10in -> evalfreturnin : [ A>=1+B ], cost: 1

      4: evalfbb8in -> evalfbb6in : D'=1+A, [ A>=C ], cost: 1

      5: evalfbb8in -> evalfbb10in : A'=1+A, [ C>=1+A ], cost: 1

      6: evalfbb6in -> evalfbb4in : E'=1, [ B>=D ], cost: 1

      7: evalfbb6in -> evalfbb7in : [ D>=1+B ], cost: 1

      8: evalfbb4in -> evalfbb3in : [ D>=E ], cost: 1

      9: evalfbb4in -> evalfbb5in : [ E>=1+D ], cost: 1

     10: evalfbb3in -> evalfbb4in : E'=1+E, [], cost: 1

     11: evalfbb5in -> evalfbb6in : D'=1+D, [], cost: 1

     12: evalfbb7in -> evalfbb8in : C'=1+C, [], cost: 1

     13: evalfreturnin -> evalfstop : [], cost: 1



Removed unreachable and leaf rules:

   Start location: evalfstart

      0: evalfstart -> evalfentryin : [], cost: 1

      1: evalfentryin -> evalfbb10in : A'=1, [], cost: 1

      2: evalfbb10in -> evalfbb8in : C'=1, [ B>=A ], cost: 1

      4: evalfbb8in -> evalfbb6in : D'=1+A, [ A>=C ], cost: 1

      5: evalfbb8in -> evalfbb10in : A'=1+A, [ C>=1+A ], cost: 1

      6: evalfbb6in -> evalfbb4in : E'=1, [ B>=D ], cost: 1

      7: evalfbb6in -> evalfbb7in : [ D>=1+B ], cost: 1

      8: evalfbb4in -> evalfbb3in : [ D>=E ], cost: 1

      9: evalfbb4in -> evalfbb5in : [ E>=1+D ], cost: 1

     10: evalfbb3in -> evalfbb4in : E'=1+E, [], cost: 1

     11: evalfbb5in -> evalfbb6in : D'=1+D, [], cost: 1

     12: evalfbb7in -> evalfbb8in : C'=1+C, [], cost: 1



### Simplification by acceleration and chaining ###



Eliminated locations (on linear paths):

   Start location: evalfstart

     14: evalfstart -> evalfbb10in : A'=1, [], cost: 2

      2: evalfbb10in -> evalfbb8in : C'=1, [ B>=A ], cost: 1

      4: evalfbb8in -> evalfbb6in : D'=1+A, [ A>=C ], cost: 1

      5: evalfbb8in -> evalfbb10in : A'=1+A, [ C>=1+A ], cost: 1

      6: evalfbb6in -> evalfbb4in : E'=1, [ B>=D ], cost: 1

     15: evalfbb6in -> evalfbb8in : C'=1+C, [ D>=1+B ], cost: 2

     16: evalfbb4in -> evalfbb4in : E'=1+E, [ D>=E ], cost: 2

     17: evalfbb4in -> evalfbb6in : D'=1+D, [ E>=1+D ], cost: 2



Accelerating simple loops of location 5.

   Accelerating the following rules:

     16: evalfbb4in -> evalfbb4in : E'=1+E, [ D>=E ], cost: 2



   Accelerated rule 16 with metering function 1+D-E, yielding the new rule 18.

   Removing the simple loops: 16.



Accelerated all simple loops using metering functions (where possible):

   Start location: evalfstart

     14: evalfstart -> evalfbb10in : A'=1, [], cost: 2

      2: evalfbb10in -> evalfbb8in : C'=1, [ B>=A ], cost: 1

      4: evalfbb8in -> evalfbb6in : D'=1+A, [ A>=C ], cost: 1

      5: evalfbb8in -> evalfbb10in : A'=1+A, [ C>=1+A ], cost: 1

      6: evalfbb6in -> evalfbb4in : E'=1, [ B>=D ], cost: 1

     15: evalfbb6in -> evalfbb8in : C'=1+C, [ D>=1+B ], cost: 2

     17: evalfbb4in -> evalfbb6in : D'=1+D, [ E>=1+D ], cost: 2

     18: evalfbb4in -> evalfbb4in : E'=1+D, [ D>=E ], cost: 2+2*D-2*E



Chained accelerated rules (with incoming rules):

   Start location: evalfstart

     14: evalfstart -> evalfbb10in : A'=1, [], cost: 2

      2: evalfbb10in -> evalfbb8in : C'=1, [ B>=A ], cost: 1

      4: evalfbb8in -> evalfbb6in : D'=1+A, [ A>=C ], cost: 1

      5: evalfbb8in -> evalfbb10in : A'=1+A, [ C>=1+A ], cost: 1

      6: evalfbb6in -> evalfbb4in : E'=1, [ B>=D ], cost: 1

     15: evalfbb6in -> evalfbb8in : C'=1+C, [ D>=1+B ], cost: 2

     19: evalfbb6in -> evalfbb4in : E'=1+D, [ B>=D && D>=1 ], cost: 1+2*D

     17: evalfbb4in -> evalfbb6in : D'=1+D, [ E>=1+D ], cost: 2



Eliminated locations (on tree-shaped paths):

   Start location: evalfstart

     14: evalfstart -> evalfbb10in : A'=1, [], cost: 2

      2: evalfbb10in -> evalfbb8in : C'=1, [ B>=A ], cost: 1

      4: evalfbb8in -> evalfbb6in : D'=1+A, [ A>=C ], cost: 1

      5: evalfbb8in -> evalfbb10in : A'=1+A, [ C>=1+A ], cost: 1

     15: evalfbb6in -> evalfbb8in : C'=1+C, [ D>=1+B ], cost: 2

     20: evalfbb6in -> evalfbb6in : D'=1+D, E'=1, [ B>=D && 1>=1+D ], cost: 3

     21: evalfbb6in -> evalfbb6in : D'=1+D, E'=1+D, [ B>=D && D>=1 ], cost: 3+2*D



Accelerating simple loops of location 4.

   Accelerating the following rules:

     20: evalfbb6in -> evalfbb6in : D'=1+D, E'=1, [ B>=D && 1>=1+D ], cost: 3

     21: evalfbb6in -> evalfbb6in : D'=1+D, E'=1+D, [ B>=D && D>=1 ], cost: 3+2*D



   Accelerated rule 20 with backward acceleration, yielding the new rule 22.

   Accelerated rule 20 with backward acceleration, yielding the new rule 23.

   Accelerated rule 21 with metering function 1-D+B, yielding the new rule 24.

   Removing the simple loops: 20 21.



Accelerated all simple loops using metering functions (where possible):

   Start location: evalfstart

     14: evalfstart -> evalfbb10in : A'=1, [], cost: 2

      2: evalfbb10in -> evalfbb8in : C'=1, [ B>=A ], cost: 1

      4: evalfbb8in -> evalfbb6in : D'=1+A, [ A>=C ], cost: 1

      5: evalfbb8in -> evalfbb10in : A'=1+A, [ C>=1+A ], cost: 1

     15: evalfbb6in -> evalfbb8in : C'=1+C, [ D>=1+B ], cost: 2

     22: evalfbb6in -> evalfbb6in : D'=1+B, E'=1, [ B>=D && 1>=1+D && 1>=1+B ], cost: 3-3*D+3*B

     23: evalfbb6in -> evalfbb6in : D'=1, E'=1, [ B>=D && 1>=1+D && B>=0 ], cost: 3-3*D

     24: evalfbb6in -> evalfbb6in : D'=1+B, E'=1+B, [ B>=D && D>=1 ], cost: 2-2*D*(-1+D-B)+(-1+D-B)^2-2*D+2*B



Chained accelerated rules (with incoming rules):

   Start location: evalfstart

     14: evalfstart -> evalfbb10in : A'=1, [], cost: 2

      2: evalfbb10in -> evalfbb8in : C'=1, [ B>=A ], cost: 1

      4: evalfbb8in -> evalfbb6in : D'=1+A, [ A>=C ], cost: 1

      5: evalfbb8in -> evalfbb10in : A'=1+A, [ C>=1+A ], cost: 1

     25: evalfbb8in -> evalfbb6in : D'=1+B, E'=1, [ A>=C && B>=1+A && 1>=2+A && 1>=1+B ], cost: 1-3*A+3*B

     26: evalfbb8in -> evalfbb6in : D'=1, E'=1, [ A>=C && B>=1+A && 1>=2+A && B>=0 ], cost: 1-3*A

     27: evalfbb8in -> evalfbb6in : D'=1+B, E'=1+B, [ A>=C && B>=1+A && 1+A>=1 ], cost: 1+(A-B)^2-2*(A-B)*(1+A)-2*A+2*B

     15: evalfbb6in -> evalfbb8in : C'=1+C, [ D>=1+B ], cost: 2



Eliminated locations (on tree-shaped paths):

   Start location: evalfstart

     14: evalfstart -> evalfbb10in : A'=1, [], cost: 2

      2: evalfbb10in -> evalfbb8in : C'=1, [ B>=A ], cost: 1

      5: evalfbb8in -> evalfbb10in : A'=1+A, [ C>=1+A ], cost: 1

     28: evalfbb8in -> evalfbb8in : C'=1+C, D'=1+A, [ A>=C && 1+A>=1+B ], cost: 3

     29: evalfbb8in -> evalfbb8in : C'=1+C, D'=1+B, E'=1, [ A>=C && B>=1+A && 1>=2+A && 1>=1+B ], cost: 3-3*A+3*B

     30: evalfbb8in -> evalfbb8in : C'=1+C, D'=1, E'=1, [ A>=C && B>=1+A && 1>=2+A && B>=0 && 1>=1+B ], cost: 3-3*A

     31: evalfbb8in -> evalfbb8in : C'=1+C, D'=1+B, E'=1+B, [ A>=C && B>=1+A && 1+A>=1 ], cost: 3+(A-B)^2-2*(A-B)*(1+A)-2*A+2*B



Accelerating simple loops of location 3.

   Simplified some of the simple loops (and removed duplicate rules).

   Accelerating the following rules:

     28: evalfbb8in -> evalfbb8in : C'=1+C, D'=1+A, [ A>=C && 1+A>=1+B ], cost: 3

     29: evalfbb8in -> evalfbb8in : C'=1+C, D'=1+B, E'=1, [ A>=C && B>=1+A && 1>=2+A && 1>=1+B ], cost: 3-3*A+3*B

     30: evalfbb8in -> evalfbb8in : C'=1+C, D'=1, E'=1, [ A>=C && B>=1+A && 1>=2+A && -B==0 ], cost: 3-3*A

     31: evalfbb8in -> evalfbb8in : C'=1+C, D'=1+B, E'=1+B, [ A>=C && B>=1+A && 1+A>=1 ], cost: 3+(A-B)^2-2*(A-B)*(1+A)-2*A+2*B



   Accelerated rule 28 with metering function 1-C+A, yielding the new rule 32.

   Accelerated rule 29 with metering function 1-C+A, yielding the new rule 33.

   Accelerated rule 30 with metering function 1-C+A, yielding the new rule 34.

   Accelerated rule 31 with metering function 1-C+A, yielding the new rule 35.

   Removing the simple loops: 28 29 30 31.



Accelerated all simple loops using metering functions (where possible):

   Start location: evalfstart

     14: evalfstart -> evalfbb10in : A'=1, [], cost: 2

      2: evalfbb10in -> evalfbb8in : C'=1, [ B>=A ], cost: 1

      5: evalfbb8in -> evalfbb10in : A'=1+A, [ C>=1+A ], cost: 1

     32: evalfbb8in -> evalfbb8in : C'=1+A, D'=1+A, [ A>=C && 1+A>=1+B ], cost: 3-3*C+3*A

     33: evalfbb8in -> evalfbb8in : C'=1+A, D'=1+B, E'=1, [ A>=C && B>=1+A && 1>=2+A && 1>=1+B ], cost: 3-3*C-3*(-1+C-A)*B+3*A+3*(-1+C-A)*A

     34: evalfbb8in -> evalfbb8in : C'=1+A, D'=1, E'=1, [ A>=C && B>=1+A && 1>=2+A && -B==0 ], cost: 3-3*C+3*A+3*(-1+C-A)*A

     35: evalfbb8in -> evalfbb8in : C'=1+A, D'=1+B, E'=1+B, [ A>=C && B>=1+A && 1+A>=1 ], cost: 3-(-1+C-A)*B^2-3*C-4*(-1+C-A)*B+(-1+C-A)*A^2+3*A+4*(-1+C-A)*A



Chained accelerated rules (with incoming rules):

   Start location: evalfstart

     14: evalfstart -> evalfbb10in : A'=1, [], cost: 2

      2: evalfbb10in -> evalfbb8in : C'=1, [ B>=A ], cost: 1

     36: evalfbb10in -> evalfbb8in : C'=1+A, D'=1+A, [ A-B==0 && A>=1 ], cost: 1+3*A

     37: evalfbb10in -> evalfbb8in : C'=1+A, D'=1+B, E'=1+B, [ A>=1 && B>=1+A ], cost: 1+A*B^2+3*A+4*A*B-4*A^2-A^3

      5: evalfbb8in -> evalfbb10in : A'=1+A, [ C>=1+A ], cost: 1



Eliminated locations (on tree-shaped paths):

   Start location: evalfstart

     14: evalfstart -> evalfbb10in : A'=1, [], cost: 2

     38: evalfbb10in -> evalfbb10in : A'=1+A, C'=1, [ B>=A && 1>=1+A ], cost: 2

     39: evalfbb10in -> evalfbb10in : A'=1+A, C'=1+A, D'=1+A, [ A-B==0 && A>=1 ], cost: 2+3*A

     40: evalfbb10in -> evalfbb10in : A'=1+A, C'=1+A, D'=1+B, E'=1+B, [ A>=1 && B>=1+A ], cost: 2+A*B^2+3*A+4*A*B-4*A^2-A^3



Accelerating simple loops of location 2.

   Accelerating the following rules:

     38: evalfbb10in -> evalfbb10in : A'=1+A, C'=1, [ B>=A && 1>=1+A ], cost: 2

     39: evalfbb10in -> evalfbb10in : A'=1+A, C'=1+A, D'=1+A, [ A-B==0 && A>=1 ], cost: 2+3*A

     40: evalfbb10in -> evalfbb10in : A'=1+A, C'=1+A, D'=1+B, E'=1+B, [ A>=1 && B>=1+A ], cost: 2+A*B^2+3*A+4*A*B-4*A^2-A^3



   Accelerated rule 38 with backward acceleration, yielding the new rule 41.

   Accelerated rule 38 with backward acceleration, yielding the new rule 42.

   Accelerated rule 39 with metering function 1-A+B, yielding the new rule 43.

   Accelerated rule 40 with metering function -A+B, yielding the new rule 44.

   Nested simple loops 40 (outer loop) and 43 (inner loop) with metering function meter_1 (where 2*meter_1==-A+B), resulting in the new rules: 45.

   Removing the simple loops: 38 39 40.



Accelerated all simple loops using metering functions (where possible):

   Start location: evalfstart

     14: evalfstart -> evalfbb10in : A'=1, [], cost: 2

     41: evalfbb10in -> evalfbb10in : A'=1+B, C'=1, [ B>=A && 1>=1+A && 1>=1+B ], cost: 2-2*A+2*B

     42: evalfbb10in -> evalfbb10in : A'=1, C'=1, [ B>=A && 1>=1+A && B>=0 ], cost: 2-2*A

     43: evalfbb10in -> evalfbb10in : A'=1+B, C'=1+B, D'=1+B, [ A-B==0 && A>=1 ], cost: 1/2-3*(-1+A-B)*A-1/2*A+3/2*(-1+A-B)^2+1/2*B

     44: evalfbb10in -> evalfbb10in : A'=B, C'=B, D'=1+B, E'=1+B, [ A>=1 && B>=1+A ], cost: -A*(A-B)*B^2+1/2*(A-B)^2*B^2+5/2*A^2*(A-B)-3/2*A^2*(A-B)^2+5/6*(A-B)^3+A^3*(A-B)-4*A*(A-B)*B+13/4*(A-B)^2+2*(A-B)^2*B+A*(A-B)^3+2*(A-B)*B-1/4*(A-B)^4-5/2*A*(A-B)^2+1/6*A-13/2*A*(A-B)+1/2*(A-B)*B^2-1/6*B

     45: evalfbb10in -> evalfbb10in : A'=1+B, C'=1+B, D'=1+B, E'=1+B, [ A>=1 && 1+A-B==0 && 2*meter_1==-A+B && meter_1>=1 ], cost: -5*meter_1-2*meter_1*B^2-7*meter_1*B



Chained accelerated rules (with incoming rules):

   Start location: evalfstart

     14: evalfstart -> evalfbb10in : A'=1, [], cost: 2

     46: evalfstart -> evalfbb10in : A'=1+B, C'=1+B, D'=1+B, [ 1-B==0 ], cost: 2+3/2*B^2+7/2*B

     47: evalfstart -> evalfbb10in : A'=B, C'=B, D'=1+B, E'=1+B, [ B>=2 ], cost: -5/6+2*(-1+B)*B-1/4*(-1+B)^4+1/2*(-1+B)*B^2+1/2*(-1+B)^2*B^2-11/6*(-1+B)^3-3/4*(-1+B)^2+17/6*B+2*(-1+B)^2*B



Removed unreachable locations (and leaf rules with constant cost):

   Start location: evalfstart

     46: evalfstart -> evalfbb10in : A'=1+B, C'=1+B, D'=1+B, [ 1-B==0 ], cost: 2+3/2*B^2+7/2*B

     47: evalfstart -> evalfbb10in : A'=B, C'=B, D'=1+B, E'=1+B, [ B>=2 ], cost: -5/6+2*(-1+B)*B-1/4*(-1+B)^4+1/2*(-1+B)*B^2+1/2*(-1+B)^2*B^2-11/6*(-1+B)^3-3/4*(-1+B)^2+17/6*B+2*(-1+B)^2*B



### Computing asymptotic complexity ###



Fully simplified ITS problem

   Start location: evalfstart

     46: evalfstart -> evalfbb10in : A'=1+B, C'=1+B, D'=1+B, [ 1-B==0 ], cost: 2+3/2*B^2+7/2*B

     47: evalfstart -> evalfbb10in : A'=B, C'=B, D'=1+B, E'=1+B, [ B>=2 ], cost: -5/6+2*(-1+B)*B-1/4*(-1+B)^4+1/2*(-1+B)*B^2+1/2*(-1+B)^2*B^2-11/6*(-1+B)^3-3/4*(-1+B)^2+17/6*B+2*(-1+B)^2*B



Computing asymptotic complexity for rule 46

   Could not solve the limit problem.

   Resulting cost 0 has complexity: Unknown



Computing asymptotic complexity for rule 47

   Solved the limit problem by the following transformations:

      Created initial limit problem:

      2/3*B^3+5/4*B^2+1/4*B^4-1/6*B (+), -1+B (+/+!) [not solved]



      removing all constraints (solved by SMT)

      resulting limit problem: [solved]



      applying transformation rule (C) using substitution {B==-1+n}

      resulting limit problem:

      [solved]



   Solution:

      B / -1+n

   Resulting cost 1+3/4*n^2-1/3*n^3-5/3*n+1/4*n^4 has complexity: Poly(n^4)



Found new complexity Poly(n^4).



Obtained the following overall complexity (w.r.t. the length of the input n):

   Complexity:  Poly(n^4)

   Cpx degree:  4

   Solved cost: 1+3/4*n^2-1/3*n^3-5/3*n+1/4*n^4

   Rule cost:   -5/6+2*(-1+B)*B-1/4*(-1+B)^4+1/2*(-1+B)*B^2+1/2*(-1+B)^2*B^2-11/6*(-1+B)^3-3/4*(-1+B)^2+17/6*B+2*(-1+B)^2*B

   Rule guard:  [ B>=2 ]



WORST_CASE(Omega(n^4),?)


----------------------------------------

(4)
BOUNDS(n^4, INF)