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


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


WORST_CASE(Omega(n^2), ?)
proof of /export/starexec/sandbox/benchmark/theBenchmark.koat
# AProVE Commit ID: 794c25de1cacf0d048858bcd21c9a779e1221865 marcel 20200619 unpublished dirty


The runtime complexity of the given CpxIntTrs could be proven to be BOUNDS(n^2, INF).

(0) CpxIntTrs
(1) Loat Proof [FINISHED, 2098 ms]
(2) BOUNDS(n^2, 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(evalfbb8in(B, A, C, D, E, F)) :|: TRUE
evalfbb8in(A, B, C, D, E, F) -> Com_1(evalfbb2in(A, B, A, D, E, F)) :|: B >= 0
evalfbb8in(A, B, C, D, E, F) -> Com_1(evalfreturnin(A, B, C, D, E, F)) :|: 0 >= B + 1
evalfbb2in(A, B, C, D, E, F) -> Com_1(evalfbb4in(A, B, C, D, E, F)) :|: 0 >= C + 1
evalfbb2in(A, B, C, D, E, F) -> Com_1(evalfbb3in(A, B, C, D, E, F)) :|: C >= 0
evalfbb3in(A, B, C, D, E, F) -> Com_1(evalfbb1in(A, B, C, D, E, F)) :|: 0 >= G + 1
evalfbb3in(A, B, C, D, E, F) -> Com_1(evalfbb1in(A, B, C, D, E, F)) :|: G >= 1
evalfbb3in(A, B, C, D, E, F) -> Com_1(evalfbb4in(A, B, C, D, E, F)) :|: TRUE
evalfbb1in(A, B, C, D, E, F) -> Com_1(evalfbb2in(A, B, C - 1, D, E, F)) :|: TRUE
evalfbb4in(A, B, C, D, E, F) -> Com_1(evalfbb6in(A, B, C, B - 1, C, F)) :|: TRUE
evalfbb6in(A, B, C, D, E, F) -> Com_1(evalfbb8in(E, D, C, D, E, F)) :|: E >= F + 1
evalfbb6in(A, B, C, D, E, F) -> Com_1(evalfbb7in(A, B, C, D, E, F)) :|: F >= E
evalfbb7in(A, B, C, D, E, F) -> Com_1(evalfbb5in(A, B, C, D, E, F)) :|: 0 >= G + 1
evalfbb7in(A, B, C, D, E, F) -> Com_1(evalfbb5in(A, B, C, D, E, F)) :|: G >= 1
evalfbb7in(A, B, C, D, E, F) -> Com_1(evalfbb8in(E, D, C, D, E, F)) :|: TRUE
evalfbb5in(A, B, C, D, E, F) -> Com_1(evalfbb6in(A, B, C, D, E + 1, 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) Loat Proof (FINISHED)


### Pre-processing the ITS problem ###



Initial linear ITS problem

   Start location: evalfstart

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

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

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

      3: evalfbb8in -> evalfreturnin : [ 0>=1+B ], cost: 1

      4: evalfbb2in -> evalfbb4in : [ 0>=1+C ], cost: 1

      5: evalfbb2in -> evalfbb3in : [ C>=0 ], cost: 1

      6: evalfbb3in -> evalfbb1in : [ 0>=1+free ], cost: 1

      7: evalfbb3in -> evalfbb1in : [ free_1>=1 ], cost: 1

      8: evalfbb3in -> evalfbb4in : [], cost: 1

      9: evalfbb1in -> evalfbb2in : C'=-1+C, [], cost: 1

     10: evalfbb4in -> evalfbb6in : D'=-1+B, E'=C, [], cost: 1

     11: evalfbb6in -> evalfbb8in : A'=E, B'=D, [ E>=1+F ], cost: 1

     12: evalfbb6in -> evalfbb7in : [ F>=E ], cost: 1

     13: evalfbb7in -> evalfbb5in : [ 0>=1+free_2 ], cost: 1

     14: evalfbb7in -> evalfbb5in : [ free_3>=1 ], cost: 1

     15: evalfbb7in -> evalfbb8in : A'=E, B'=D, [], cost: 1

     16: evalfbb5in -> evalfbb6in : E'=1+E, [], cost: 1

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



Checking for constant complexity:

   The following rule is satisfiable with cost >= 1, yielding constant complexity:

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



Removed unreachable and leaf rules:

   Start location: evalfstart

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

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

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

      4: evalfbb2in -> evalfbb4in : [ 0>=1+C ], cost: 1

      5: evalfbb2in -> evalfbb3in : [ C>=0 ], cost: 1

      6: evalfbb3in -> evalfbb1in : [ 0>=1+free ], cost: 1

      7: evalfbb3in -> evalfbb1in : [ free_1>=1 ], cost: 1

      8: evalfbb3in -> evalfbb4in : [], cost: 1

      9: evalfbb1in -> evalfbb2in : C'=-1+C, [], cost: 1

     10: evalfbb4in -> evalfbb6in : D'=-1+B, E'=C, [], cost: 1

     11: evalfbb6in -> evalfbb8in : A'=E, B'=D, [ E>=1+F ], cost: 1

     12: evalfbb6in -> evalfbb7in : [ F>=E ], cost: 1

     13: evalfbb7in -> evalfbb5in : [ 0>=1+free_2 ], cost: 1

     14: evalfbb7in -> evalfbb5in : [ free_3>=1 ], cost: 1

     15: evalfbb7in -> evalfbb8in : A'=E, B'=D, [], cost: 1

     16: evalfbb5in -> evalfbb6in : E'=1+E, [], cost: 1



Simplified all rules, resulting in:

   Start location: evalfstart

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

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

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

      4: evalfbb2in -> evalfbb4in : [ 0>=1+C ], cost: 1

      5: evalfbb2in -> evalfbb3in : [ C>=0 ], cost: 1

      7: evalfbb3in -> evalfbb1in : [], cost: 1

      8: evalfbb3in -> evalfbb4in : [], cost: 1

      9: evalfbb1in -> evalfbb2in : C'=-1+C, [], cost: 1

     10: evalfbb4in -> evalfbb6in : D'=-1+B, E'=C, [], cost: 1

     11: evalfbb6in -> evalfbb8in : A'=E, B'=D, [ E>=1+F ], cost: 1

     12: evalfbb6in -> evalfbb7in : [ F>=E ], cost: 1

     14: evalfbb7in -> evalfbb5in : [], cost: 1

     15: evalfbb7in -> evalfbb8in : A'=E, B'=D, [], cost: 1

     16: evalfbb5in -> evalfbb6in : E'=1+E, [], cost: 1



### Simplification by acceleration and chaining ###



Eliminated locations (on linear paths):

   Start location: evalfstart

     18: evalfstart -> evalfbb8in : A'=B, B'=A, [], cost: 2

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

      4: evalfbb2in -> evalfbb4in : [ 0>=1+C ], cost: 1

      5: evalfbb2in -> evalfbb3in : [ C>=0 ], cost: 1

      8: evalfbb3in -> evalfbb4in : [], cost: 1

     19: evalfbb3in -> evalfbb2in : C'=-1+C, [], cost: 2

     10: evalfbb4in -> evalfbb6in : D'=-1+B, E'=C, [], cost: 1

     11: evalfbb6in -> evalfbb8in : A'=E, B'=D, [ E>=1+F ], cost: 1

     12: evalfbb6in -> evalfbb7in : [ F>=E ], cost: 1

     15: evalfbb7in -> evalfbb8in : A'=E, B'=D, [], cost: 1

     20: evalfbb7in -> evalfbb6in : E'=1+E, [], cost: 2



Eliminated locations (on tree-shaped paths):

   Start location: evalfstart

     18: evalfstart -> evalfbb8in : A'=B, B'=A, [], cost: 2

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

     22: evalfbb2in -> evalfbb2in : C'=-1+C, [ C>=0 ], cost: 3

     23: evalfbb2in -> evalfbb6in : D'=-1+B, E'=C, [ 0>=1+C ], cost: 2

     24: evalfbb2in -> evalfbb6in : D'=-1+B, E'=C, [ C>=0 ], cost: 3

     11: evalfbb6in -> evalfbb8in : A'=E, B'=D, [ E>=1+F ], cost: 1

     25: evalfbb6in -> evalfbb8in : A'=E, B'=D, [ F>=E ], cost: 2

     26: evalfbb6in -> evalfbb6in : E'=1+E, [ F>=E ], cost: 3



Accelerating simple loops of location 3.

   Accelerating the following rules:

     22: evalfbb2in -> evalfbb2in : C'=-1+C, [ C>=0 ], cost: 3



   Accelerated rule 22 with metering function 1+C, yielding the new rule 27.

   Removing the simple loops: 22.



Accelerating simple loops of location 7.

   Accelerating the following rules:

     26: evalfbb6in -> evalfbb6in : E'=1+E, [ F>=E ], cost: 3



   Accelerated rule 26 with metering function 1+F-E, yielding the new rule 28.

   Removing the simple loops: 26.



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

   Start location: evalfstart

     18: evalfstart -> evalfbb8in : A'=B, B'=A, [], cost: 2

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

     23: evalfbb2in -> evalfbb6in : D'=-1+B, E'=C, [ 0>=1+C ], cost: 2

     24: evalfbb2in -> evalfbb6in : D'=-1+B, E'=C, [ C>=0 ], cost: 3

     27: evalfbb2in -> evalfbb2in : C'=-1, [ C>=0 ], cost: 3+3*C

     11: evalfbb6in -> evalfbb8in : A'=E, B'=D, [ E>=1+F ], cost: 1

     25: evalfbb6in -> evalfbb8in : A'=E, B'=D, [ F>=E ], cost: 2

     28: evalfbb6in -> evalfbb6in : E'=1+F, [ F>=E ], cost: 3+3*F-3*E



Chained accelerated rules (with incoming rules):

   Start location: evalfstart

     18: evalfstart -> evalfbb8in : A'=B, B'=A, [], cost: 2

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

     29: evalfbb8in -> evalfbb2in : C'=-1, [ B>=0 && A>=0 ], cost: 4+3*A

     23: evalfbb2in -> evalfbb6in : D'=-1+B, E'=C, [ 0>=1+C ], cost: 2

     24: evalfbb2in -> evalfbb6in : D'=-1+B, E'=C, [ C>=0 ], cost: 3

     30: evalfbb2in -> evalfbb6in : D'=-1+B, E'=1+F, [ 0>=1+C && F>=C ], cost: 5+3*F-3*C

     31: evalfbb2in -> evalfbb6in : D'=-1+B, E'=1+F, [ C>=0 && F>=C ], cost: 6+3*F-3*C

     11: evalfbb6in -> evalfbb8in : A'=E, B'=D, [ E>=1+F ], cost: 1

     25: evalfbb6in -> evalfbb8in : A'=E, B'=D, [ F>=E ], cost: 2



Eliminated locations (on tree-shaped paths):

   Start location: evalfstart

     18: evalfstart -> evalfbb8in : A'=B, B'=A, [], cost: 2

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

     33: evalfbb8in -> evalfbb6in : C'=A, D'=-1+B, E'=A, [ B>=0 && A>=0 ], cost: 4

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

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

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

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

     38: evalfbb8in -> [14] : [ B>=0 && A>=0 ], cost: 4+3*A

     11: evalfbb6in -> evalfbb8in : A'=E, B'=D, [ E>=1+F ], cost: 1

     25: evalfbb6in -> evalfbb8in : A'=E, B'=D, [ F>=E ], cost: 2



Applied pruning (of leafs and parallel rules):

   Start location: evalfstart

     18: evalfstart -> evalfbb8in : A'=B, B'=A, [], cost: 2

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

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

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

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

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

     38: evalfbb8in -> [14] : [ B>=0 && A>=0 ], cost: 4+3*A

     11: evalfbb6in -> evalfbb8in : A'=E, B'=D, [ E>=1+F ], cost: 1

     25: evalfbb6in -> evalfbb8in : A'=E, B'=D, [ F>=E ], cost: 2



Eliminated locations (on tree-shaped paths):

   Start location: evalfstart

     18: evalfstart -> evalfbb8in : A'=B, B'=A, [], cost: 2

     38: evalfbb8in -> [14] : [ B>=0 && A>=0 ], cost: 4+3*A

     39: evalfbb8in -> evalfbb8in : A'=A, B'=-1+B, C'=A, D'=-1+B, E'=A, [ B>=0 && 0>=1+A && A>=1+F ], cost: 4

     40: evalfbb8in -> evalfbb8in : A'=A, B'=-1+B, C'=A, D'=-1+B, E'=A, [ B>=0 && 0>=1+A && F>=A ], cost: 5

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

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

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

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

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

     46: evalfbb8in -> [15] : [ B>=0 && 0>=1+A && F>=A ], cost: 6+3*F-3*A

     47: evalfbb8in -> [15] : [ B>=0 && A>=0 && F>=A ], cost: 7+3*F-3*A

     48: evalfbb8in -> [15] : [ B>=0 && A>=0 && F>=-1 ], cost: 12+3*F+3*A



Applied pruning (of leafs and parallel rules):

   Start location: evalfstart

     18: evalfstart -> evalfbb8in : A'=B, B'=A, [], cost: 2

     38: evalfbb8in -> [14] : [ B>=0 && A>=0 ], cost: 4+3*A

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

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

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

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

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

     46: evalfbb8in -> [15] : [ B>=0 && 0>=1+A && F>=A ], cost: 6+3*F-3*A

     47: evalfbb8in -> [15] : [ B>=0 && A>=0 && F>=A ], cost: 7+3*F-3*A

     48: evalfbb8in -> [15] : [ B>=0 && A>=0 && F>=-1 ], cost: 12+3*F+3*A



Accelerating simple loops of location 2.

   Accelerating the following rules:

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

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

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

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

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



   Found no metering function for rule 41.

   Found no metering function for rule 42.

   Found no metering function for rule 43.

   Found no metering function for rule 44.

   Accelerated rule 45 with metering function 1+B, yielding the new rule 49.

   Removing the simple loops: 45.



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

   Start location: evalfstart

     18: evalfstart -> evalfbb8in : A'=B, B'=A, [], cost: 2

     38: evalfbb8in -> [14] : [ B>=0 && A>=0 ], cost: 4+3*A

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

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

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

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

     46: evalfbb8in -> [15] : [ B>=0 && 0>=1+A && F>=A ], cost: 6+3*F-3*A

     47: evalfbb8in -> [15] : [ B>=0 && A>=0 && F>=A ], cost: 7+3*F-3*A

     48: evalfbb8in -> [15] : [ B>=0 && A>=0 && F>=-1 ], cost: 12+3*F+3*A

     49: evalfbb8in -> evalfbb8in : A'=1+F, B'=-1, C'=-1, D'=-1, E'=1+F, [ B>=0 && A>=0 && F>=-1 ], cost: 16+6*F*(1+B)+16*B



Chained accelerated rules (with incoming rules):

   Start location: evalfstart

     18: evalfstart -> evalfbb8in : A'=B, B'=A, [], cost: 2

     50: evalfstart -> evalfbb8in : A'=1+F, B'=-1+A, C'=B, D'=-1+A, E'=1+F, [ A>=0 && 0>=1+B && F>=B ], cost: 9+3*F-3*B

     51: evalfstart -> evalfbb8in : A'=1+F, B'=-1+A, C'=B, D'=-1+A, E'=1+F, [ A>=0 && B>=0 && F>=B ], cost: 10+3*F-3*B

     52: evalfstart -> evalfbb8in : A'=-1, B'=-1+A, C'=-1, D'=-1+A, E'=-1, [ A>=0 && B>=0 && -1>=1+F ], cost: 9+3*B

     53: evalfstart -> evalfbb8in : A'=-1, B'=-1+A, C'=-1, D'=-1+A, E'=-1, [ A>=0 && B>=0 && F>=-1 ], cost: 10+3*B

     54: evalfstart -> evalfbb8in : A'=1+F, B'=-1, C'=-1, D'=-1, E'=1+F, [ A>=0 && B>=0 && F>=-1 ], cost: 18+16*A+6*F*(1+A)

     38: evalfbb8in -> [14] : [ B>=0 && A>=0 ], cost: 4+3*A

     46: evalfbb8in -> [15] : [ B>=0 && 0>=1+A && F>=A ], cost: 6+3*F-3*A

     47: evalfbb8in -> [15] : [ B>=0 && A>=0 && F>=A ], cost: 7+3*F-3*A

     48: evalfbb8in -> [15] : [ B>=0 && A>=0 && F>=-1 ], cost: 12+3*F+3*A



Eliminated locations (on tree-shaped paths):

   Start location: evalfstart

     55: evalfstart -> [14] : A'=B, B'=A, [ A>=0 && B>=0 ], cost: 6+3*B

     56: evalfstart -> [15] : A'=B, B'=A, [ A>=0 && 0>=1+B && F>=B ], cost: 8+3*F-3*B

     57: evalfstart -> [15] : A'=B, B'=A, [ A>=0 && B>=0 && F>=B ], cost: 9+3*F-3*B

     58: evalfstart -> [15] : A'=B, B'=A, [ A>=0 && B>=0 && F>=-1 ], cost: 14+3*F+3*B

     59: evalfstart -> [14] : A'=1+F, B'=-1+A, C'=B, D'=-1+A, E'=1+F, [ 0>=1+B && F>=B && -1+A>=0 && 1+F>=0 ], cost: 16+6*F-3*B

     60: evalfstart -> [15] : A'=1+F, B'=-1+A, C'=B, D'=-1+A, E'=1+F, [ 0>=1+B && F>=B && -1+A>=0 && 1+F>=0 ], cost: 24+9*F-3*B

     61: evalfstart -> [14] : A'=1+F, B'=-1+A, C'=B, D'=-1+A, E'=1+F, [ B>=0 && F>=B && -1+A>=0 && 1+F>=0 ], cost: 17+6*F-3*B

     62: evalfstart -> [15] : A'=1+F, B'=-1+A, C'=B, D'=-1+A, E'=1+F, [ B>=0 && F>=B && -1+A>=0 && 1+F>=0 ], cost: 25+9*F-3*B

     63: evalfstart -> [15] : A'=-1, B'=-1+A, C'=-1, D'=-1+A, E'=-1, [ B>=0 && F>=-1 && -1+A>=0 ], cost: 19+3*F+3*B

     64: evalfstart -> [17] : [ A>=0 && 0>=1+B && F>=B ], cost: 9+3*F-3*B

     65: evalfstart -> [17] : [ A>=0 && B>=0 && F>=B ], cost: 10+3*F-3*B

     66: evalfstart -> [17] : [ A>=0 && B>=0 && -1>=1+F ], cost: 9+3*B

     67: evalfstart -> [17] : [ A>=0 && B>=0 && F>=-1 ], cost: 10+3*B

     68: evalfstart -> [17] : [ A>=0 && B>=0 && F>=-1 ], cost: 18+16*A+6*F*(1+A)



Applied pruning (of leafs and parallel rules):

   Start location: evalfstart

     55: evalfstart -> [14] : A'=B, B'=A, [ A>=0 && B>=0 ], cost: 6+3*B

     56: evalfstart -> [15] : A'=B, B'=A, [ A>=0 && 0>=1+B && F>=B ], cost: 8+3*F-3*B

     57: evalfstart -> [15] : A'=B, B'=A, [ A>=0 && B>=0 && F>=B ], cost: 9+3*F-3*B

     58: evalfstart -> [15] : A'=B, B'=A, [ A>=0 && B>=0 && F>=-1 ], cost: 14+3*F+3*B

     59: evalfstart -> [14] : A'=1+F, B'=-1+A, C'=B, D'=-1+A, E'=1+F, [ 0>=1+B && F>=B && -1+A>=0 && 1+F>=0 ], cost: 16+6*F-3*B

     60: evalfstart -> [15] : A'=1+F, B'=-1+A, C'=B, D'=-1+A, E'=1+F, [ 0>=1+B && F>=B && -1+A>=0 && 1+F>=0 ], cost: 24+9*F-3*B

     61: evalfstart -> [14] : A'=1+F, B'=-1+A, C'=B, D'=-1+A, E'=1+F, [ B>=0 && F>=B && -1+A>=0 && 1+F>=0 ], cost: 17+6*F-3*B

     63: evalfstart -> [15] : A'=-1, B'=-1+A, C'=-1, D'=-1+A, E'=-1, [ B>=0 && F>=-1 && -1+A>=0 ], cost: 19+3*F+3*B

     64: evalfstart -> [17] : [ A>=0 && 0>=1+B && F>=B ], cost: 9+3*F-3*B

     65: evalfstart -> [17] : [ A>=0 && B>=0 && F>=B ], cost: 10+3*F-3*B

     66: evalfstart -> [17] : [ A>=0 && B>=0 && -1>=1+F ], cost: 9+3*B

     67: evalfstart -> [17] : [ A>=0 && B>=0 && F>=-1 ], cost: 10+3*B

     68: evalfstart -> [17] : [ A>=0 && B>=0 && F>=-1 ], cost: 18+16*A+6*F*(1+A)



### Computing asymptotic complexity ###



Fully simplified ITS problem

   Start location: evalfstart

     55: evalfstart -> [14] : A'=B, B'=A, [ A>=0 && B>=0 ], cost: 6+3*B

     58: evalfstart -> [15] : A'=B, B'=A, [ A>=0 && B>=0 && F>=-1 ], cost: 14+3*F+3*B

     59: evalfstart -> [14] : A'=1+F, B'=-1+A, C'=B, D'=-1+A, E'=1+F, [ 0>=1+B && F>=B && -1+A>=0 && 1+F>=0 ], cost: 16+6*F-3*B

     60: evalfstart -> [15] : A'=1+F, B'=-1+A, C'=B, D'=-1+A, E'=1+F, [ 0>=1+B && F>=B && -1+A>=0 && 1+F>=0 ], cost: 24+9*F-3*B

     61: evalfstart -> [14] : A'=1+F, B'=-1+A, C'=B, D'=-1+A, E'=1+F, [ B>=0 && F>=B && -1+A>=0 && 1+F>=0 ], cost: 17+6*F-3*B

     63: evalfstart -> [15] : A'=-1, B'=-1+A, C'=-1, D'=-1+A, E'=-1, [ B>=0 && F>=-1 && -1+A>=0 ], cost: 19+3*F+3*B

     64: evalfstart -> [17] : [ A>=0 && 0>=1+B && F>=B ], cost: 9+3*F-3*B

     65: evalfstart -> [17] : [ A>=0 && B>=0 && F>=B ], cost: 10+3*F-3*B

     66: evalfstart -> [17] : [ A>=0 && B>=0 && -1>=1+F ], cost: 9+3*B

     67: evalfstart -> [17] : [ A>=0 && B>=0 && F>=-1 ], cost: 10+3*B

     68: evalfstart -> [17] : [ A>=0 && B>=0 && F>=-1 ], cost: 18+16*A+6*F*(1+A)



Computing asymptotic complexity for rule 55

   Solved the limit problem by the following transformations:

      Created initial limit problem:

      6+3*B (+), 1+B (+/+!), 1+A (+/+!) [not solved]



      removing all constraints (solved by SMT)

      resulting limit problem: [solved]



      applying transformation rule (C) using substitution {A==n,B==n}

      resulting limit problem:

      [solved]



   Solution:

      A / n

      B / n

   Resulting cost 6+3*n has complexity: Poly(n^1)



Found new complexity Poly(n^1).



Computing asymptotic complexity for rule 68

   Solved the limit problem by the following transformations:

      Created initial limit problem:

      18+6*F+16*A+6*F*A (+), 2+F (+/+!), 1+B (+/+!), 1+A (+/+!) [not solved]



      removing all constraints (solved by SMT)

      resulting limit problem: [solved]



      applying transformation rule (C) using substitution {F==n,A==n,B==n}

      resulting limit problem:

      [solved]



   Solution:

      F / n

      A / n

      B / n

   Resulting cost 18+22*n+6*n^2 has complexity: Poly(n^2)



Found new complexity Poly(n^2).



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

   Complexity:  Poly(n^2)

   Cpx degree:  2

   Solved cost: 18+22*n+6*n^2

   Rule cost:   18+16*A+6*F*(1+A)

   Rule guard:  [ A>=0 && B>=0 && F>=-1 ]



WORST_CASE(Omega(n^2),?)


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

(2)
BOUNDS(n^2, INF)