16.67/7.80	WORST_CASE(Omega(n^2), ?)
16.67/7.81	proof of /export/starexec/sandbox2/benchmark/theBenchmark.koat
16.67/7.81	# AProVE Commit ID: 48fb2092695e11cc9f56e44b17a92a5f88ffb256 marcel 20180622 unpublished dirty
16.67/7.81	
16.67/7.81	
16.67/7.81	The runtime complexity of the given CpxIntTrs could be proven to be BOUNDS(n^2, INF).
16.67/7.81	
16.67/7.81	(0) CpxIntTrs
16.67/7.81	(1) Loat Proof [FINISHED, 2946 ms]
16.67/7.81	(2) BOUNDS(n^2, INF)
16.67/7.81	
16.67/7.81	
16.67/7.81	----------------------------------------
16.67/7.81	
16.67/7.81	(0)
16.67/7.81	Obligation:
16.67/7.81	Complexity Int TRS consisting of the following rules:
16.67/7.81	evalfstart(A, B, C, D, E, F) -> Com_1(evalfentryin(A, B, C, D, E, F)) :|: TRUE
16.67/7.81	evalfentryin(A, B, C, D, E, F) -> Com_1(evalfbb8in(B, A, C, D, E, F)) :|: TRUE
16.67/7.81	evalfbb8in(A, B, C, D, E, F) -> Com_1(evalfbb2in(A, B, A, D, E, F)) :|: B >= 0
16.67/7.81	evalfbb8in(A, B, C, D, E, F) -> Com_1(evalfreturnin(A, B, C, D, E, F)) :|: 0 >= B + 1
16.67/7.81	evalfbb2in(A, B, C, D, E, F) -> Com_1(evalfbb4in(A, B, C, D, E, F)) :|: 0 >= C + 1
16.67/7.81	evalfbb2in(A, B, C, D, E, F) -> Com_1(evalfbb3in(A, B, C, D, E, F)) :|: C >= 0
16.67/7.81	evalfbb3in(A, B, C, D, E, F) -> Com_1(evalfbb1in(A, B, C, D, E, F)) :|: 0 >= G + 1
16.67/7.81	evalfbb3in(A, B, C, D, E, F) -> Com_1(evalfbb1in(A, B, C, D, E, F)) :|: G >= 1
16.67/7.81	evalfbb3in(A, B, C, D, E, F) -> Com_1(evalfbb4in(A, B, C, D, E, F)) :|: TRUE
16.67/7.81	evalfbb1in(A, B, C, D, E, F) -> Com_1(evalfbb2in(A, B, C - 1, D, E, F)) :|: TRUE
16.67/7.81	evalfbb4in(A, B, C, D, E, F) -> Com_1(evalfbb6in(A, B, C, B - 1, C, F)) :|: TRUE
16.67/7.81	evalfbb6in(A, B, C, D, E, F) -> Com_1(evalfbb8in(E, D, C, D, E, F)) :|: E >= F + 1
16.67/7.81	evalfbb6in(A, B, C, D, E, F) -> Com_1(evalfbb7in(A, B, C, D, E, F)) :|: F >= E
16.67/7.81	evalfbb7in(A, B, C, D, E, F) -> Com_1(evalfbb5in(A, B, C, D, E, F)) :|: 0 >= G + 1
16.67/7.81	evalfbb7in(A, B, C, D, E, F) -> Com_1(evalfbb5in(A, B, C, D, E, F)) :|: G >= 1
16.67/7.81	evalfbb7in(A, B, C, D, E, F) -> Com_1(evalfbb8in(E, D, C, D, E, F)) :|: TRUE
16.67/7.81	evalfbb5in(A, B, C, D, E, F) -> Com_1(evalfbb6in(A, B, C, D, E + 1, F)) :|: TRUE
16.67/7.81	evalfreturnin(A, B, C, D, E, F) -> Com_1(evalfstop(A, B, C, D, E, F)) :|: TRUE
16.67/7.81	
16.67/7.81	The start-symbols are:[evalfstart_6]
16.67/7.81	
16.67/7.81	
16.67/7.81	----------------------------------------
16.67/7.81	
16.67/7.81	(1) Loat Proof (FINISHED)
16.67/7.81	
16.67/7.81	
16.67/7.81	### Pre-processing the ITS problem ###
16.67/7.81	
16.67/7.81	
16.67/7.81	
16.67/7.81	Initial linear ITS problem
16.67/7.81	
16.67/7.81	   Start location: evalfstart
16.67/7.81	
16.67/7.81	      0: evalfstart -> evalfentryin : [], cost: 1
16.67/7.81	
16.67/7.81	      1: evalfentryin -> evalfbb8in : A'=B, B'=A, [], cost: 1
16.67/7.81	
16.67/7.81	      2: evalfbb8in -> evalfbb2in : C'=A, [ B>=0 ], cost: 1
16.67/7.81	
16.67/7.81	      3: evalfbb8in -> evalfreturnin : [ 0>=1+B ], cost: 1
16.67/7.81	
16.67/7.81	      4: evalfbb2in -> evalfbb4in : [ 0>=1+C ], cost: 1
16.67/7.81	
16.67/7.81	      5: evalfbb2in -> evalfbb3in : [ C>=0 ], cost: 1
16.67/7.81	
16.67/7.81	      6: evalfbb3in -> evalfbb1in : [ 0>=1+free ], cost: 1
16.67/7.81	
16.67/7.81	      7: evalfbb3in -> evalfbb1in : [ free_1>=1 ], cost: 1
16.67/7.81	
16.67/7.81	      8: evalfbb3in -> evalfbb4in : [], cost: 1
16.67/7.81	
16.67/7.81	      9: evalfbb1in -> evalfbb2in : C'=-1+C, [], cost: 1
16.67/7.81	
16.67/7.81	     10: evalfbb4in -> evalfbb6in : D'=-1+B, E'=C, [], cost: 1
16.67/7.81	
16.67/7.81	     11: evalfbb6in -> evalfbb8in : A'=E, B'=D, [ E>=1+F ], cost: 1
16.67/7.81	
16.67/7.81	     12: evalfbb6in -> evalfbb7in : [ F>=E ], cost: 1
16.67/7.81	
16.67/7.81	     13: evalfbb7in -> evalfbb5in : [ 0>=1+free_2 ], cost: 1
16.67/7.81	
16.67/7.81	     14: evalfbb7in -> evalfbb5in : [ free_3>=1 ], cost: 1
16.67/7.81	
16.67/7.81	     15: evalfbb7in -> evalfbb8in : A'=E, B'=D, [], cost: 1
16.67/7.81	
16.67/7.81	     16: evalfbb5in -> evalfbb6in : E'=1+E, [], cost: 1
16.67/7.81	
16.67/7.81	     17: evalfreturnin -> evalfstop : [], cost: 1
16.67/7.81	
16.67/7.81	
16.67/7.81	
16.67/7.81	Removed unreachable and leaf rules:
16.67/7.81	
16.67/7.81	   Start location: evalfstart
16.67/7.81	
16.67/7.81	      0: evalfstart -> evalfentryin : [], cost: 1
16.67/7.81	
16.67/7.81	      1: evalfentryin -> evalfbb8in : A'=B, B'=A, [], cost: 1
16.67/7.81	
16.67/7.81	      2: evalfbb8in -> evalfbb2in : C'=A, [ B>=0 ], cost: 1
16.67/7.81	
16.67/7.81	      4: evalfbb2in -> evalfbb4in : [ 0>=1+C ], cost: 1
16.67/7.81	
16.67/7.81	      5: evalfbb2in -> evalfbb3in : [ C>=0 ], cost: 1
16.67/7.81	
16.67/7.81	      6: evalfbb3in -> evalfbb1in : [ 0>=1+free ], cost: 1
16.67/7.81	
16.67/7.81	      7: evalfbb3in -> evalfbb1in : [ free_1>=1 ], cost: 1
16.67/7.81	
16.67/7.81	      8: evalfbb3in -> evalfbb4in : [], cost: 1
16.67/7.81	
16.67/7.81	      9: evalfbb1in -> evalfbb2in : C'=-1+C, [], cost: 1
16.67/7.81	
16.67/7.81	     10: evalfbb4in -> evalfbb6in : D'=-1+B, E'=C, [], cost: 1
16.67/7.81	
16.67/7.81	     11: evalfbb6in -> evalfbb8in : A'=E, B'=D, [ E>=1+F ], cost: 1
16.67/7.81	
16.67/7.81	     12: evalfbb6in -> evalfbb7in : [ F>=E ], cost: 1
16.67/7.81	
16.67/7.81	     13: evalfbb7in -> evalfbb5in : [ 0>=1+free_2 ], cost: 1
16.67/7.81	
16.67/7.81	     14: evalfbb7in -> evalfbb5in : [ free_3>=1 ], cost: 1
16.67/7.81	
16.67/7.81	     15: evalfbb7in -> evalfbb8in : A'=E, B'=D, [], cost: 1
16.67/7.81	
16.67/7.81	     16: evalfbb5in -> evalfbb6in : E'=1+E, [], cost: 1
16.67/7.81	
16.67/7.81	
16.67/7.81	
16.67/7.81	Simplified all rules, resulting in:
16.67/7.81	
16.67/7.81	   Start location: evalfstart
16.67/7.81	
16.67/7.81	      0: evalfstart -> evalfentryin : [], cost: 1
16.67/7.81	
16.67/7.81	      1: evalfentryin -> evalfbb8in : A'=B, B'=A, [], cost: 1
16.67/7.81	
16.67/7.81	      2: evalfbb8in -> evalfbb2in : C'=A, [ B>=0 ], cost: 1
16.67/7.81	
16.67/7.81	      4: evalfbb2in -> evalfbb4in : [ 0>=1+C ], cost: 1
16.67/7.81	
16.67/7.81	      5: evalfbb2in -> evalfbb3in : [ C>=0 ], cost: 1
16.67/7.81	
16.67/7.81	      7: evalfbb3in -> evalfbb1in : [], cost: 1
16.67/7.81	
16.67/7.81	      8: evalfbb3in -> evalfbb4in : [], cost: 1
16.67/7.81	
16.67/7.81	      9: evalfbb1in -> evalfbb2in : C'=-1+C, [], cost: 1
16.67/7.81	
16.67/7.81	     10: evalfbb4in -> evalfbb6in : D'=-1+B, E'=C, [], cost: 1
16.67/7.81	
16.67/7.81	     11: evalfbb6in -> evalfbb8in : A'=E, B'=D, [ E>=1+F ], cost: 1
16.67/7.81	
16.67/7.81	     12: evalfbb6in -> evalfbb7in : [ F>=E ], cost: 1
16.67/7.81	
16.67/7.81	     14: evalfbb7in -> evalfbb5in : [], cost: 1
16.67/7.81	
16.67/7.81	     15: evalfbb7in -> evalfbb8in : A'=E, B'=D, [], cost: 1
16.67/7.81	
16.67/7.81	     16: evalfbb5in -> evalfbb6in : E'=1+E, [], cost: 1
16.67/7.81	
16.67/7.81	
16.67/7.81	
16.67/7.81	### Simplification by acceleration and chaining ###
16.67/7.81	
16.67/7.81	
16.67/7.81	
16.67/7.81	Eliminated locations (on linear paths):
16.67/7.81	
16.67/7.81	   Start location: evalfstart
16.67/7.81	
16.67/7.81	     18: evalfstart -> evalfbb8in : A'=B, B'=A, [], cost: 2
16.67/7.81	
16.67/7.81	      2: evalfbb8in -> evalfbb2in : C'=A, [ B>=0 ], cost: 1
16.67/7.81	
16.67/7.81	      4: evalfbb2in -> evalfbb4in : [ 0>=1+C ], cost: 1
16.67/7.81	
16.67/7.81	      5: evalfbb2in -> evalfbb3in : [ C>=0 ], cost: 1
16.67/7.81	
16.67/7.81	      8: evalfbb3in -> evalfbb4in : [], cost: 1
16.67/7.81	
16.67/7.81	     19: evalfbb3in -> evalfbb2in : C'=-1+C, [], cost: 2
16.67/7.81	
16.67/7.81	     10: evalfbb4in -> evalfbb6in : D'=-1+B, E'=C, [], cost: 1
16.67/7.81	
16.67/7.81	     11: evalfbb6in -> evalfbb8in : A'=E, B'=D, [ E>=1+F ], cost: 1
16.67/7.81	
16.67/7.81	     12: evalfbb6in -> evalfbb7in : [ F>=E ], cost: 1
16.67/7.81	
16.67/7.81	     15: evalfbb7in -> evalfbb8in : A'=E, B'=D, [], cost: 1
16.67/7.81	
16.67/7.81	     20: evalfbb7in -> evalfbb6in : E'=1+E, [], cost: 2
16.67/7.81	
16.67/7.81	
16.67/7.81	
16.67/7.81	Eliminated locations (on tree-shaped paths):
16.67/7.81	
16.67/7.81	   Start location: evalfstart
16.67/7.81	
16.67/7.81	     18: evalfstart -> evalfbb8in : A'=B, B'=A, [], cost: 2
16.67/7.81	
16.67/7.81	      2: evalfbb8in -> evalfbb2in : C'=A, [ B>=0 ], cost: 1
16.67/7.81	
16.67/7.81	     22: evalfbb2in -> evalfbb2in : C'=-1+C, [ C>=0 ], cost: 3
16.67/7.81	
16.67/7.81	     23: evalfbb2in -> evalfbb6in : D'=-1+B, E'=C, [ 0>=1+C ], cost: 2
16.67/7.81	
16.67/7.81	     24: evalfbb2in -> evalfbb6in : D'=-1+B, E'=C, [ C>=0 ], cost: 3
16.67/7.81	
16.67/7.81	     11: evalfbb6in -> evalfbb8in : A'=E, B'=D, [ E>=1+F ], cost: 1
16.67/7.81	
16.67/7.81	     25: evalfbb6in -> evalfbb8in : A'=E, B'=D, [ F>=E ], cost: 2
16.67/7.81	
16.67/7.81	     26: evalfbb6in -> evalfbb6in : E'=1+E, [ F>=E ], cost: 3
16.67/7.81	
16.67/7.81	
16.67/7.81	
16.67/7.81	Accelerating simple loops of location 3.
16.67/7.81	
16.67/7.81	   Accelerating the following rules:
16.67/7.81	
16.67/7.81	     22: evalfbb2in -> evalfbb2in : C'=-1+C, [ C>=0 ], cost: 3
16.67/7.81	
16.67/7.81	
16.67/7.81	
16.67/7.81	   Accelerated rule 22 with metering function 1+C, yielding the new rule 27.
16.67/7.81	
16.67/7.81	   Removing the simple loops: 22.
16.67/7.81	
16.67/7.81	
16.67/7.81	
16.67/7.81	Accelerating simple loops of location 7.
16.67/7.81	
16.67/7.81	   Accelerating the following rules:
16.67/7.81	
16.67/7.81	     26: evalfbb6in -> evalfbb6in : E'=1+E, [ F>=E ], cost: 3
16.67/7.81	
16.67/7.81	
16.67/7.81	
16.67/7.81	   Accelerated rule 26 with metering function 1+F-E, yielding the new rule 28.
16.67/7.81	
16.67/7.81	   Removing the simple loops: 26.
16.67/7.81	
16.67/7.81	
16.67/7.81	
16.67/7.81	Accelerated all simple loops using metering functions (where possible):
16.67/7.81	
16.67/7.81	   Start location: evalfstart
16.67/7.81	
16.67/7.81	     18: evalfstart -> evalfbb8in : A'=B, B'=A, [], cost: 2
16.67/7.81	
16.67/7.81	      2: evalfbb8in -> evalfbb2in : C'=A, [ B>=0 ], cost: 1
16.67/7.81	
16.67/7.81	     23: evalfbb2in -> evalfbb6in : D'=-1+B, E'=C, [ 0>=1+C ], cost: 2
16.67/7.81	
16.67/7.81	     24: evalfbb2in -> evalfbb6in : D'=-1+B, E'=C, [ C>=0 ], cost: 3
16.67/7.81	
16.67/7.81	     27: evalfbb2in -> evalfbb2in : C'=-1, [ C>=0 ], cost: 3+3*C
16.67/7.81	
16.67/7.81	     11: evalfbb6in -> evalfbb8in : A'=E, B'=D, [ E>=1+F ], cost: 1
16.67/7.81	
16.67/7.81	     25: evalfbb6in -> evalfbb8in : A'=E, B'=D, [ F>=E ], cost: 2
16.67/7.81	
16.67/7.81	     28: evalfbb6in -> evalfbb6in : E'=1+F, [ F>=E ], cost: 3+3*F-3*E
16.67/7.81	
16.67/7.81	
16.67/7.81	
16.67/7.81	Chained accelerated rules (with incoming rules):
16.67/7.81	
16.67/7.81	   Start location: evalfstart
16.67/7.81	
16.67/7.81	     18: evalfstart -> evalfbb8in : A'=B, B'=A, [], cost: 2
16.67/7.81	
16.67/7.81	      2: evalfbb8in -> evalfbb2in : C'=A, [ B>=0 ], cost: 1
16.67/7.81	
16.67/7.81	     29: evalfbb8in -> evalfbb2in : C'=-1, [ B>=0 && A>=0 ], cost: 4+3*A
16.67/7.81	
16.67/7.81	     23: evalfbb2in -> evalfbb6in : D'=-1+B, E'=C, [ 0>=1+C ], cost: 2
16.67/7.81	
16.67/7.81	     24: evalfbb2in -> evalfbb6in : D'=-1+B, E'=C, [ C>=0 ], cost: 3
16.67/7.81	
16.67/7.81	     30: evalfbb2in -> evalfbb6in : D'=-1+B, E'=1+F, [ 0>=1+C && F>=C ], cost: 5+3*F-3*C
16.67/7.81	
16.67/7.81	     31: evalfbb2in -> evalfbb6in : D'=-1+B, E'=1+F, [ C>=0 && F>=C ], cost: 6+3*F-3*C
16.67/7.81	
16.67/7.81	     11: evalfbb6in -> evalfbb8in : A'=E, B'=D, [ E>=1+F ], cost: 1
16.67/7.81	
16.67/7.81	     25: evalfbb6in -> evalfbb8in : A'=E, B'=D, [ F>=E ], cost: 2
16.67/7.81	
16.67/7.81	
16.67/7.81	
16.67/7.81	Eliminated locations (on tree-shaped paths):
16.67/7.81	
16.67/7.81	   Start location: evalfstart
16.67/7.81	
16.67/7.81	     18: evalfstart -> evalfbb8in : A'=B, B'=A, [], cost: 2
16.67/7.81	
16.67/7.81	     32: evalfbb8in -> evalfbb6in : C'=A, D'=-1+B, E'=A, [ B>=0 && 0>=1+A ], cost: 3
16.67/7.81	
16.67/7.81	     33: evalfbb8in -> evalfbb6in : C'=A, D'=-1+B, E'=A, [ B>=0 && A>=0 ], cost: 4
16.67/7.81	
16.67/7.81	     34: evalfbb8in -> evalfbb6in : C'=A, D'=-1+B, E'=1+F, [ B>=0 && 0>=1+A && F>=A ], cost: 6+3*F-3*A
16.67/7.81	
16.67/7.81	     35: evalfbb8in -> evalfbb6in : C'=A, D'=-1+B, E'=1+F, [ B>=0 && A>=0 && F>=A ], cost: 7+3*F-3*A
16.67/7.81	
16.67/7.81	     36: evalfbb8in -> evalfbb6in : C'=-1, D'=-1+B, E'=-1, [ B>=0 && A>=0 ], cost: 6+3*A
16.67/7.81	
16.67/7.81	     37: evalfbb8in -> evalfbb6in : C'=-1, D'=-1+B, E'=1+F, [ B>=0 && A>=0 && F>=-1 ], cost: 12+3*F+3*A
16.67/7.81	
16.67/7.81	     38: evalfbb8in -> [14] : [ B>=0 && A>=0 ], cost: 4+3*A
16.67/7.81	
16.67/7.81	     11: evalfbb6in -> evalfbb8in : A'=E, B'=D, [ E>=1+F ], cost: 1
16.67/7.81	
16.67/7.81	     25: evalfbb6in -> evalfbb8in : A'=E, B'=D, [ F>=E ], cost: 2
16.67/7.81	
16.67/7.81	
16.67/7.81	
16.67/7.81	Applied pruning (of leafs and parallel rules):
16.67/7.81	
16.67/7.81	   Start location: evalfstart
16.67/7.81	
16.67/7.81	     18: evalfstart -> evalfbb8in : A'=B, B'=A, [], cost: 2
16.67/7.81	
16.67/7.81	     32: evalfbb8in -> evalfbb6in : C'=A, D'=-1+B, E'=A, [ B>=0 && 0>=1+A ], cost: 3
16.67/7.81	
16.67/7.81	     34: evalfbb8in -> evalfbb6in : C'=A, D'=-1+B, E'=1+F, [ B>=0 && 0>=1+A && F>=A ], cost: 6+3*F-3*A
16.67/7.81	
16.67/7.81	     35: evalfbb8in -> evalfbb6in : C'=A, D'=-1+B, E'=1+F, [ B>=0 && A>=0 && F>=A ], cost: 7+3*F-3*A
16.67/7.81	
16.67/7.81	     36: evalfbb8in -> evalfbb6in : C'=-1, D'=-1+B, E'=-1, [ B>=0 && A>=0 ], cost: 6+3*A
16.67/7.81	
16.67/7.81	     37: evalfbb8in -> evalfbb6in : C'=-1, D'=-1+B, E'=1+F, [ B>=0 && A>=0 && F>=-1 ], cost: 12+3*F+3*A
16.67/7.81	
16.67/7.81	     38: evalfbb8in -> [14] : [ B>=0 && A>=0 ], cost: 4+3*A
16.67/7.81	
16.67/7.81	     11: evalfbb6in -> evalfbb8in : A'=E, B'=D, [ E>=1+F ], cost: 1
16.67/7.81	
16.67/7.81	     25: evalfbb6in -> evalfbb8in : A'=E, B'=D, [ F>=E ], cost: 2
16.67/7.81	
16.67/7.81	
16.67/7.81	
16.67/7.81	Eliminated locations (on tree-shaped paths):
16.67/7.81	
16.67/7.81	   Start location: evalfstart
16.67/7.81	
16.67/7.81	     18: evalfstart -> evalfbb8in : A'=B, B'=A, [], cost: 2
16.67/7.81	
16.67/7.81	     38: evalfbb8in -> [14] : [ B>=0 && A>=0 ], cost: 4+3*A
16.67/7.81	
16.67/7.81	     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
16.67/7.81	
16.67/7.81	     40: evalfbb8in -> evalfbb8in : A'=A, B'=-1+B, C'=A, D'=-1+B, E'=A, [ B>=0 && 0>=1+A && F>=A ], cost: 5
16.67/7.81	
16.67/7.81	     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
16.67/7.81	
16.67/7.81	     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
16.67/7.81	
16.67/7.81	     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
16.67/7.81	
16.67/7.81	     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
16.67/7.81	
16.67/7.81	     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
16.67/7.81	
16.67/7.81	     46: evalfbb8in -> [15] : [ B>=0 && 0>=1+A && F>=A ], cost: 6+3*F-3*A
16.67/7.81	
16.67/7.81	     47: evalfbb8in -> [15] : [ B>=0 && A>=0 && F>=A ], cost: 7+3*F-3*A
16.67/7.81	
16.67/7.81	     48: evalfbb8in -> [15] : [ B>=0 && A>=0 && F>=-1 ], cost: 12+3*F+3*A
16.67/7.81	
16.67/7.81	
16.67/7.81	
16.67/7.81	Applied pruning (of leafs and parallel rules):
16.67/7.81	
16.67/7.81	   Start location: evalfstart
16.67/7.81	
16.67/7.81	     18: evalfstart -> evalfbb8in : A'=B, B'=A, [], cost: 2
16.67/7.81	
16.67/7.81	     38: evalfbb8in -> [14] : [ B>=0 && A>=0 ], cost: 4+3*A
16.67/7.81	
16.67/7.81	     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
16.67/7.81	
16.67/7.81	     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
16.67/7.81	
16.67/7.81	     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
16.67/7.81	
16.67/7.81	     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
16.67/7.81	
16.67/7.81	     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
16.67/7.81	
16.67/7.81	     46: evalfbb8in -> [15] : [ B>=0 && 0>=1+A && F>=A ], cost: 6+3*F-3*A
16.67/7.81	
16.67/7.81	     47: evalfbb8in -> [15] : [ B>=0 && A>=0 && F>=A ], cost: 7+3*F-3*A
16.67/7.81	
16.67/7.81	     48: evalfbb8in -> [15] : [ B>=0 && A>=0 && F>=-1 ], cost: 12+3*F+3*A
16.67/7.81	
16.67/7.81	
16.67/7.81	
16.67/7.81	Accelerating simple loops of location 2.
16.67/7.81	
16.67/7.81	   Accelerating the following rules:
16.67/7.81	
16.67/7.81	     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
16.67/7.81	
16.67/7.81	     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
16.67/7.81	
16.67/7.81	     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
16.67/7.81	
16.67/7.81	     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
16.67/7.81	
16.67/7.81	     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
16.67/7.81	
16.67/7.81	
16.67/7.81	
16.67/7.81	   Found no metering function for rule 41.
16.67/7.81	
16.67/7.81	   Found no metering function for rule 42.
16.67/7.81	
16.67/7.81	   Found no metering function for rule 43.
16.67/7.81	
16.67/7.81	   Found no metering function for rule 44.
16.67/7.81	
16.67/7.81	   Accelerated rule 45 with metering function 1+B, yielding the new rule 49.
16.67/7.81	
16.67/7.81	   Removing the simple loops: 45.
16.67/7.81	
16.67/7.81	
16.67/7.81	
16.67/7.81	Accelerated all simple loops using metering functions (where possible):
16.67/7.81	
16.67/7.81	   Start location: evalfstart
16.67/7.81	
16.67/7.81	     18: evalfstart -> evalfbb8in : A'=B, B'=A, [], cost: 2
16.67/7.81	
16.67/7.81	     38: evalfbb8in -> [14] : [ B>=0 && A>=0 ], cost: 4+3*A
16.67/7.81	
16.67/7.81	     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
16.67/7.81	
16.67/7.81	     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
16.67/7.81	
16.67/7.81	     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
16.67/7.81	
16.67/7.81	     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
16.67/7.81	
16.67/7.81	     46: evalfbb8in -> [15] : [ B>=0 && 0>=1+A && F>=A ], cost: 6+3*F-3*A
16.67/7.81	
16.67/7.81	     47: evalfbb8in -> [15] : [ B>=0 && A>=0 && F>=A ], cost: 7+3*F-3*A
16.67/7.81	
16.67/7.81	     48: evalfbb8in -> [15] : [ B>=0 && A>=0 && F>=-1 ], cost: 12+3*F+3*A
16.67/7.81	
16.67/7.81	     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
16.67/7.81	
16.67/7.81	
16.67/7.81	
16.67/7.81	Chained accelerated rules (with incoming rules):
16.67/7.81	
16.67/7.81	   Start location: evalfstart
16.67/7.81	
16.67/7.81	     18: evalfstart -> evalfbb8in : A'=B, B'=A, [], cost: 2
16.67/7.81	
16.67/7.81	     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
16.67/7.81	
16.67/7.81	     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
16.67/7.81	
16.67/7.81	     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
16.67/7.81	
16.67/7.81	     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
16.67/7.81	
16.67/7.81	     54: evalfstart -> evalfbb8in : A'=1+F, B'=-1, C'=-1, D'=-1, E'=1+F, [ A>=0 && B>=0 && F>=-1 ], cost: 18+6*F*(1+A)+16*A
16.67/7.81	
16.67/7.81	     38: evalfbb8in -> [14] : [ B>=0 && A>=0 ], cost: 4+3*A
16.67/7.81	
16.67/7.81	     46: evalfbb8in -> [15] : [ B>=0 && 0>=1+A && F>=A ], cost: 6+3*F-3*A
16.67/7.81	
16.67/7.81	     47: evalfbb8in -> [15] : [ B>=0 && A>=0 && F>=A ], cost: 7+3*F-3*A
16.67/7.81	
16.67/7.81	     48: evalfbb8in -> [15] : [ B>=0 && A>=0 && F>=-1 ], cost: 12+3*F+3*A
16.67/7.81	
16.67/7.81	
16.67/7.81	
16.67/7.81	Eliminated locations (on tree-shaped paths):
16.67/7.81	
16.67/7.81	   Start location: evalfstart
16.67/7.81	
16.67/7.81	     55: evalfstart -> [14] : A'=B, B'=A, [ A>=0 && B>=0 ], cost: 6+3*B
16.67/7.81	
16.67/7.81	     56: evalfstart -> [15] : A'=B, B'=A, [ A>=0 && 0>=1+B && F>=B ], cost: 8+3*F-3*B
16.67/7.81	
16.67/7.81	     57: evalfstart -> [15] : A'=B, B'=A, [ A>=0 && B>=0 && F>=B ], cost: 9+3*F-3*B
16.67/7.81	
16.67/7.81	     58: evalfstart -> [15] : A'=B, B'=A, [ A>=0 && B>=0 && F>=-1 ], cost: 14+3*F+3*B
16.67/7.81	
16.67/7.81	     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
16.67/7.81	
16.67/7.81	     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
16.67/7.81	
16.67/7.81	     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
16.67/7.81	
16.67/7.81	     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
16.67/7.81	
16.67/7.81	     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
16.67/7.81	
16.67/7.81	     64: evalfstart -> [17] : [ A>=0 && 0>=1+B && F>=B ], cost: 9+3*F-3*B
16.67/7.81	
16.67/7.81	     65: evalfstart -> [17] : [ A>=0 && B>=0 && F>=B ], cost: 10+3*F-3*B
16.67/7.81	
16.67/7.81	     66: evalfstart -> [17] : [ A>=0 && B>=0 && -1>=1+F ], cost: 9+3*B
16.67/7.81	
16.67/7.81	     67: evalfstart -> [17] : [ A>=0 && B>=0 && F>=-1 ], cost: 10+3*B
16.67/7.81	
16.67/7.81	     68: evalfstart -> [17] : [ A>=0 && B>=0 && F>=-1 ], cost: 18+6*F*(1+A)+16*A
16.67/7.81	
16.67/7.81	
16.67/7.81	
16.67/7.81	Applied pruning (of leafs and parallel rules):
16.67/7.81	
16.67/7.81	   Start location: evalfstart
16.67/7.81	
16.67/7.81	     55: evalfstart -> [14] : A'=B, B'=A, [ A>=0 && B>=0 ], cost: 6+3*B
16.67/7.81	
16.67/7.81	     56: evalfstart -> [15] : A'=B, B'=A, [ A>=0 && 0>=1+B && F>=B ], cost: 8+3*F-3*B
16.67/7.81	
16.67/7.81	     58: evalfstart -> [15] : A'=B, B'=A, [ A>=0 && B>=0 && F>=-1 ], cost: 14+3*F+3*B
16.67/7.81	
16.67/7.81	     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
16.67/7.81	
16.67/7.81	     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
16.67/7.81	
16.67/7.81	     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
16.67/7.81	
16.67/7.81	     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
16.67/7.81	
16.67/7.81	     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
16.67/7.81	
16.67/7.81	     64: evalfstart -> [17] : [ A>=0 && 0>=1+B && F>=B ], cost: 9+3*F-3*B
16.67/7.81	
16.67/7.81	     65: evalfstart -> [17] : [ A>=0 && B>=0 && F>=B ], cost: 10+3*F-3*B
16.67/7.81	
16.67/7.81	     66: evalfstart -> [17] : [ A>=0 && B>=0 && -1>=1+F ], cost: 9+3*B
16.67/7.81	
16.67/7.81	     67: evalfstart -> [17] : [ A>=0 && B>=0 && F>=-1 ], cost: 10+3*B
16.67/7.81	
16.67/7.81	     68: evalfstart -> [17] : [ A>=0 && B>=0 && F>=-1 ], cost: 18+6*F*(1+A)+16*A
16.67/7.81	
16.67/7.81	
16.67/7.81	
16.67/7.81	### Computing asymptotic complexity ###
16.67/7.81	
16.67/7.81	
16.67/7.81	
16.67/7.81	Fully simplified ITS problem
16.67/7.81	
16.67/7.81	   Start location: evalfstart
16.67/7.81	
16.67/7.81	     55: evalfstart -> [14] : A'=B, B'=A, [ A>=0 && B>=0 ], cost: 6+3*B
16.67/7.81	
16.67/7.81	     58: evalfstart -> [15] : A'=B, B'=A, [ A>=0 && B>=0 && F>=-1 ], cost: 14+3*F+3*B
16.67/7.81	
16.67/7.81	     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
16.67/7.81	
16.67/7.81	     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
16.67/7.81	
16.67/7.81	     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
16.67/7.81	
16.67/7.81	     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
16.67/7.81	
16.67/7.81	     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
16.67/7.81	
16.67/7.81	     64: evalfstart -> [17] : [ A>=0 && 0>=1+B && F>=B ], cost: 9+3*F-3*B
16.67/7.81	
16.67/7.81	     65: evalfstart -> [17] : [ A>=0 && B>=0 && F>=B ], cost: 10+3*F-3*B
16.67/7.81	
16.67/7.81	     66: evalfstart -> [17] : [ A>=0 && B>=0 && -1>=1+F ], cost: 9+3*B
16.67/7.81	
16.67/7.81	     67: evalfstart -> [17] : [ A>=0 && B>=0 && F>=-1 ], cost: 10+3*B
16.67/7.81	
16.67/7.81	     68: evalfstart -> [17] : [ A>=0 && B>=0 && F>=-1 ], cost: 18+6*F*(1+A)+16*A
16.67/7.81	
16.67/7.81	
16.67/7.81	
16.67/7.81	Computing asymptotic complexity for rule 55
16.67/7.81	
16.67/7.81	   Solved the limit problem by the following transformations:
16.67/7.81	
16.67/7.81	      Created initial limit problem:
16.67/7.81	
16.67/7.81	      1+B (+/+!), 6+3*B (+), 1+A (+/+!) [not solved]
16.67/7.81	
16.67/7.81	
16.67/7.81	
16.67/7.81	      removing all constraints (solved by SMT)
16.67/7.81	
16.67/7.81	      resulting limit problem: [solved]
16.67/7.81	
16.67/7.81	
16.67/7.81	
16.67/7.81	      applying transformation rule (C) using substitution {A==n,B==n}
16.67/7.81	
16.67/7.81	      resulting limit problem:
16.67/7.81	
16.67/7.81	      [solved]
16.67/7.81	
16.67/7.81	
16.67/7.81	
16.67/7.81	   Solution:
16.67/7.81	
16.67/7.81	      A / n
16.67/7.81	
16.67/7.81	      B / n
16.67/7.81	
16.67/7.81	   Resulting cost 6+3*n has complexity: Poly(n^1)
16.67/7.81	
16.67/7.81	
16.67/7.81	
16.67/7.81	Found new complexity Poly(n^1).
16.67/7.81	
16.67/7.81	
16.67/7.81	
16.67/7.81	Computing asymptotic complexity for rule 68
16.67/7.81	
16.67/7.81	   Solved the limit problem by the following transformations:
16.67/7.81	
16.67/7.81	      Created initial limit problem:
16.67/7.81	
16.67/7.81	      1+B (+/+!), 2+F (+/+!), 18+6*F*A+6*F+16*A (+), 1+A (+/+!) [not solved]
16.67/7.81	
16.67/7.81	
16.67/7.81	
16.67/7.81	      removing all constraints (solved by SMT)
16.67/7.81	
16.67/7.81	      resulting limit problem: [solved]
16.67/7.81	
16.67/7.81	
16.67/7.81	
16.67/7.81	      applying transformation rule (C) using substitution {F==n,A==n,B==n}
16.67/7.81	
16.67/7.81	      resulting limit problem:
16.67/7.81	
16.67/7.81	      [solved]
16.67/7.81	
16.67/7.81	
16.67/7.81	
16.67/7.81	   Solution:
16.67/7.81	
16.67/7.81	      F / n
16.67/7.81	
16.67/7.81	      A / n
16.67/7.81	
16.67/7.81	      B / n
16.67/7.81	
16.67/7.81	   Resulting cost 18+22*n+6*n^2 has complexity: Poly(n^2)
16.67/7.81	
16.67/7.81	
16.67/7.81	
16.67/7.81	Found new complexity Poly(n^2).
16.67/7.81	
16.67/7.81	
16.67/7.81	
16.67/7.81	Obtained the following overall complexity (w.r.t. the length of the input n):
16.67/7.81	
16.67/7.81	   Complexity:  Poly(n^2)
16.67/7.81	
16.67/7.81	   Cpx degree:  2
16.67/7.81	
16.67/7.81	   Solved cost: 18+22*n+6*n^2
16.67/7.81	
16.67/7.81	   Rule cost:   18+6*F*(1+A)+16*A
16.67/7.81	
16.67/7.81	   Rule guard:  [ A>=0 && B>=0 && F>=-1 ]
16.67/7.81	
16.67/7.81	
16.67/7.81	
16.67/7.81	WORST_CASE(Omega(n^2),?)
16.67/7.81	
16.67/7.81	
16.67/7.81	----------------------------------------
16.67/7.81	
16.67/7.81	(2)
16.67/7.81	BOUNDS(n^2, INF)
16.74/7.84	EOF