31.18/18.15	WORST_CASE(Omega(n^1), ?)
31.18/18.16	proof of /export/starexec/sandbox/benchmark/theBenchmark.koat
31.18/18.16	# AProVE Commit ID: 48fb2092695e11cc9f56e44b17a92a5f88ffb256 marcel 20180622 unpublished dirty
31.18/18.16	
31.18/18.16	
31.18/18.16	The runtime complexity of the given CpxIntTrs could be proven to be BOUNDS(n^1, INF).
31.18/18.16	
31.18/18.16	(0) CpxIntTrs
31.18/18.16	(1) Loat Proof [FINISHED, 2522 ms]
31.18/18.16	(2) BOUNDS(n^1, INF)
31.18/18.16	
31.18/18.16	
31.18/18.16	----------------------------------------
31.18/18.16	
31.18/18.16	(0)
31.18/18.16	Obligation:
31.18/18.16	Complexity Int TRS consisting of the following rules:
31.18/18.16	eval_rank1_start(v_2, v_5, v_8, v_m, v_x_0, v_x_1, v_y_0, v_y_1, v_y_2) -> Com_1(eval_rank1_bb0_in(v_2, v_5, v_8, v_m, v_x_0, v_x_1, v_y_0, v_y_1, v_y_2)) :|: TRUE
31.18/18.16	eval_rank1_bb0_in(v_2, v_5, v_8, v_m, v_x_0, v_x_1, v_y_0, v_y_1, v_y_2) -> Com_1(eval_rank1_0(v_2, v_5, v_8, v_m, v_x_0, v_x_1, v_y_0, v_y_1, v_y_2)) :|: TRUE
31.18/18.16	eval_rank1_0(v_2, v_5, v_8, v_m, v_x_0, v_x_1, v_y_0, v_y_1, v_y_2) -> Com_1(eval_rank1_1(v_2, v_5, v_8, v_m, v_x_0, v_x_1, v_y_0, v_y_1, v_y_2)) :|: TRUE
31.18/18.16	eval_rank1_1(v_2, v_5, v_8, v_m, v_x_0, v_x_1, v_y_0, v_y_1, v_y_2) -> Com_1(eval_rank1_2(v_2, v_5, v_8, v_m, v_x_0, v_x_1, v_y_0, v_y_1, v_y_2)) :|: TRUE
31.18/18.16	eval_rank1_2(v_2, v_5, v_8, v_m, v_x_0, v_x_1, v_y_0, v_y_1, v_y_2) -> Com_1(eval_rank1_3(v_2, v_5, v_8, v_m, v_x_0, v_x_1, v_y_0, v_y_1, v_y_2)) :|: TRUE
31.18/18.16	eval_rank1_3(v_2, v_5, v_8, v_m, v_x_0, v_x_1, v_y_0, v_y_1, v_y_2) -> Com_1(eval_rank1_4(v_2, v_5, v_8, v_m, v_x_0, v_x_1, v_y_0, v_y_1, v_y_2)) :|: TRUE
31.18/18.16	eval_rank1_4(v_2, v_5, v_8, v_m, v_x_0, v_x_1, v_y_0, v_y_1, v_y_2) -> Com_1(eval_rank1_5(v_2, v_5, v_8, v_m, v_x_0, v_x_1, v_y_0, v_y_1, v_y_2)) :|: TRUE
31.18/18.16	eval_rank1_5(v_2, v_5, v_8, v_m, v_x_0, v_x_1, v_y_0, v_y_1, v_y_2) -> Com_1(eval_rank1_bb1_in(v_2, v_5, v_8, v_m, v_m, v_x_1, 0, v_y_1, v_y_2)) :|: TRUE
31.18/18.16	eval_rank1_bb1_in(v_2, v_5, v_8, v_m, v_x_0, v_x_1, v_y_0, v_y_1, v_y_2) -> Com_1(eval_rank1_bb2_in(v_2, v_5, v_8, v_m, v_x_0, v_x_1, v_y_0, v_y_1, v_y_2)) :|: v_x_0 >= 0 && v_y_0 >= 0
31.18/18.16	eval_rank1_bb1_in(v_2, v_5, v_8, v_m, v_x_0, v_x_1, v_y_0, v_y_1, v_y_2) -> Com_1(eval_rank1_bb7_in(v_2, v_5, v_8, v_m, v_x_0, v_x_1, v_y_0, v_y_1, v_y_2)) :|: v_x_0 < 0
31.18/18.16	eval_rank1_bb1_in(v_2, v_5, v_8, v_m, v_x_0, v_x_1, v_y_0, v_y_1, v_y_2) -> Com_1(eval_rank1_bb7_in(v_2, v_5, v_8, v_m, v_x_0, v_x_1, v_y_0, v_y_1, v_y_2)) :|: v_y_0 < 0
31.18/18.16	eval_rank1_bb2_in(v_2, v_5, v_8, v_m, v_x_0, v_x_1, v_y_0, v_y_1, v_y_2) -> Com_1(eval_rank1_6(v_2, v_5, v_8, v_m, v_x_0, v_x_1, v_y_0, v_y_1, v_y_2)) :|: TRUE
31.18/18.16	eval_rank1_6(v_2, v_5, v_8, v_m, v_x_0, v_x_1, v_y_0, v_y_1, v_y_2) -> Com_1(eval_rank1_7(nondef_0, v_5, v_8, v_m, v_x_0, v_x_1, v_y_0, v_y_1, v_y_2)) :|: TRUE
31.18/18.16	eval_rank1_7(v_2, v_5, v_8, v_m, v_x_0, v_x_1, v_y_0, v_y_1, v_y_2) -> Com_1(eval_rank1_bb3_in(v_2, v_5, v_8, v_m, v_x_0, v_x_1, v_y_0, v_y_0, v_y_2)) :|: v_2 > 0
31.18/18.16	eval_rank1_7(v_2, v_5, v_8, v_m, v_x_0, v_x_1, v_y_0, v_y_1, v_y_2) -> Com_1(eval_rank1_bb6_in(v_2, v_5, v_8, v_m, v_x_0, v_x_0, v_y_0, v_y_1, v_y_0)) :|: v_2 <= 0
31.18/18.16	eval_rank1_bb3_in(v_2, v_5, v_8, v_m, v_x_0, v_x_1, v_y_0, v_y_1, v_y_2) -> Com_1(eval_rank1_bb4_in(v_2, v_5, v_8, v_m, v_x_0, v_x_1, v_y_0, v_y_1, v_y_2)) :|: v_y_1 <= v_m
31.18/18.16	eval_rank1_bb3_in(v_2, v_5, v_8, v_m, v_x_0, v_x_1, v_y_0, v_y_1, v_y_2) -> Com_1(eval_rank1__critedge_in(v_2, v_5, v_8, v_m, v_x_0, v_x_1, v_y_0, v_y_1, v_y_2)) :|: v_y_1 > v_m
31.18/18.16	eval_rank1_bb4_in(v_2, v_5, v_8, v_m, v_x_0, v_x_1, v_y_0, v_y_1, v_y_2) -> Com_1(eval_rank1_8(v_2, v_5, v_8, v_m, v_x_0, v_x_1, v_y_0, v_y_1, v_y_2)) :|: TRUE
31.18/18.16	eval_rank1_8(v_2, v_5, v_8, v_m, v_x_0, v_x_1, v_y_0, v_y_1, v_y_2) -> Com_1(eval_rank1_9(v_2, nondef_1, v_8, v_m, v_x_0, v_x_1, v_y_0, v_y_1, v_y_2)) :|: TRUE
31.18/18.16	eval_rank1_9(v_2, v_5, v_8, v_m, v_x_0, v_x_1, v_y_0, v_y_1, v_y_2) -> Com_1(eval_rank1_bb5_in(v_2, v_5, v_8, v_m, v_x_0, v_x_1, v_y_0, v_y_1, v_y_2)) :|: v_5 > 0
31.18/18.16	eval_rank1_9(v_2, v_5, v_8, v_m, v_x_0, v_x_1, v_y_0, v_y_1, v_y_2) -> Com_1(eval_rank1__critedge_in(v_2, v_5, v_8, v_m, v_x_0, v_x_1, v_y_0, v_y_1, v_y_2)) :|: v_5 <= 0
31.18/18.16	eval_rank1_bb5_in(v_2, v_5, v_8, v_m, v_x_0, v_x_1, v_y_0, v_y_1, v_y_2) -> Com_1(eval_rank1_bb3_in(v_2, v_5, v_8, v_m, v_x_0, v_x_1, v_y_0, v_y_1 + 1, v_y_2)) :|: TRUE
31.18/18.16	eval_rank1__critedge_in(v_2, v_5, v_8, v_m, v_x_0, v_x_1, v_y_0, v_y_1, v_y_2) -> Com_1(eval_rank1_13(v_2, v_5, v_x_0 - 1, v_m, v_x_0, v_x_1, v_y_0, v_y_1, v_y_2)) :|: TRUE
31.18/18.16	eval_rank1_13(v_2, v_5, v_8, v_m, v_x_0, v_x_1, v_y_0, v_y_1, v_y_2) -> Com_1(eval_rank1_14(v_2, v_5, v_8, v_m, v_x_0, v_x_1, v_y_0, v_y_1, v_y_2)) :|: TRUE
31.18/18.16	eval_rank1_14(v_2, v_5, v_8, v_m, v_x_0, v_x_1, v_y_0, v_y_1, v_y_2) -> Com_1(eval_rank1_bb6_in(v_2, v_5, v_8, v_m, v_x_0, v_8, v_y_0, v_y_1, v_y_1)) :|: TRUE
31.18/18.16	eval_rank1_bb6_in(v_2, v_5, v_8, v_m, v_x_0, v_x_1, v_y_0, v_y_1, v_y_2) -> Com_1(eval_rank1_bb1_in(v_2, v_5, v_8, v_m, v_x_1, v_x_1, v_y_2 - 1, v_y_1, v_y_2)) :|: TRUE
31.18/18.16	eval_rank1_bb7_in(v_2, v_5, v_8, v_m, v_x_0, v_x_1, v_y_0, v_y_1, v_y_2) -> Com_1(eval_rank1_stop(v_2, v_5, v_8, v_m, v_x_0, v_x_1, v_y_0, v_y_1, v_y_2)) :|: TRUE
31.18/18.16	
31.18/18.16	The start-symbols are:[eval_rank1_start_9]
31.18/18.16	
31.18/18.16	
31.18/18.16	----------------------------------------
31.18/18.16	
31.18/18.16	(1) Loat Proof (FINISHED)
31.18/18.16	
31.18/18.16	
31.18/18.16	### Pre-processing the ITS problem ###
31.18/18.16	
31.18/18.16	
31.18/18.16	
31.18/18.16	Initial linear ITS problem
31.18/18.16	
31.18/18.16	   Start location: evalrank1start
31.18/18.16	
31.18/18.16	      0: evalrank1start -> evalrank1bb0in : [], cost: 1
31.18/18.16	
31.18/18.16	      1: evalrank1bb0in -> evalrank10 : [], cost: 1
31.18/18.16	
31.18/18.16	      2: evalrank10 -> evalrank11 : [], cost: 1
31.18/18.16	
31.18/18.16	      3: evalrank11 -> evalrank12 : [], cost: 1
31.18/18.16	
31.18/18.16	      4: evalrank12 -> evalrank13 : [], cost: 1
31.18/18.16	
31.18/18.16	      5: evalrank13 -> evalrank14 : [], cost: 1
31.18/18.16	
31.18/18.16	      6: evalrank14 -> evalrank15 : [], cost: 1
31.18/18.16	
31.18/18.16	      7: evalrank15 -> evalrank1bb1in : A'=B, C'=0, [], cost: 1
31.18/18.16	
31.18/18.16	      8: evalrank1bb1in -> evalrank1bb2in : [ A>=0 && C>=0 ], cost: 1
31.18/18.16	
31.18/18.16	      9: evalrank1bb1in -> evalrank1bb7in : [ 0>=1+A ], cost: 1
31.18/18.16	
31.18/18.16	     10: evalrank1bb1in -> evalrank1bb7in : [ 0>=1+C ], cost: 1
31.18/18.16	
31.18/18.16	     11: evalrank1bb2in -> evalrank16 : [], cost: 1
31.18/18.16	
31.18/18.16	     12: evalrank16 -> evalrank17 : D'=free, [], cost: 1
31.18/18.16	
31.18/18.16	     13: evalrank17 -> evalrank1bb3in : E'=C, [ D>=1 ], cost: 1
31.18/18.16	
31.18/18.16	     14: evalrank17 -> evalrank1bb6in : F'=A, G'=C, [ 0>=D ], cost: 1
31.18/18.16	
31.18/18.16	     15: evalrank1bb3in -> evalrank1bb4in : [ B>=E ], cost: 1
31.18/18.16	
31.18/18.16	     16: evalrank1bb3in -> evalrank1critedgein : [ E>=1+B ], cost: 1
31.18/18.16	
31.18/18.16	     17: evalrank1bb4in -> evalrank18 : [], cost: 1
31.18/18.16	
31.18/18.16	     18: evalrank18 -> evalrank19 : H'=free_1, [], cost: 1
31.18/18.16	
31.18/18.16	     19: evalrank19 -> evalrank1bb5in : [ H>=1 ], cost: 1
31.18/18.16	
31.18/18.16	     20: evalrank19 -> evalrank1critedgein : [ 0>=H ], cost: 1
31.18/18.16	
31.18/18.16	     21: evalrank1bb5in -> evalrank1bb3in : E'=1+E, [], cost: 1
31.18/18.16	
31.18/18.16	     22: evalrank1critedgein -> evalrank113 : Q'=-1+A, [], cost: 1
31.18/18.16	
31.18/18.16	     23: evalrank113 -> evalrank114 : [], cost: 1
31.18/18.16	
31.18/18.16	     24: evalrank114 -> evalrank1bb6in : F'=Q, G'=E, [], cost: 1
31.18/18.16	
31.18/18.16	     25: evalrank1bb6in -> evalrank1bb1in : A'=F, C'=-1+G, [], cost: 1
31.18/18.16	
31.18/18.16	     26: evalrank1bb7in -> evalrank1stop : [], cost: 1
31.18/18.16	
31.18/18.16	
31.18/18.16	
31.18/18.16	Removed unreachable and leaf rules:
31.18/18.16	
31.18/18.16	   Start location: evalrank1start
31.18/18.16	
31.18/18.16	      0: evalrank1start -> evalrank1bb0in : [], cost: 1
31.18/18.16	
31.18/18.16	      1: evalrank1bb0in -> evalrank10 : [], cost: 1
31.18/18.16	
31.18/18.16	      2: evalrank10 -> evalrank11 : [], cost: 1
31.18/18.16	
31.18/18.16	      3: evalrank11 -> evalrank12 : [], cost: 1
31.18/18.16	
31.18/18.16	      4: evalrank12 -> evalrank13 : [], cost: 1
31.18/18.16	
31.18/18.16	      5: evalrank13 -> evalrank14 : [], cost: 1
31.18/18.16	
31.18/18.16	      6: evalrank14 -> evalrank15 : [], cost: 1
31.18/18.16	
31.18/18.16	      7: evalrank15 -> evalrank1bb1in : A'=B, C'=0, [], cost: 1
31.18/18.16	
31.18/18.16	      8: evalrank1bb1in -> evalrank1bb2in : [ A>=0 && C>=0 ], cost: 1
31.18/18.16	
31.18/18.16	     11: evalrank1bb2in -> evalrank16 : [], cost: 1
31.18/18.16	
31.18/18.16	     12: evalrank16 -> evalrank17 : D'=free, [], cost: 1
31.18/18.16	
31.18/18.16	     13: evalrank17 -> evalrank1bb3in : E'=C, [ D>=1 ], cost: 1
31.18/18.16	
31.18/18.16	     14: evalrank17 -> evalrank1bb6in : F'=A, G'=C, [ 0>=D ], cost: 1
31.18/18.16	
31.18/18.16	     15: evalrank1bb3in -> evalrank1bb4in : [ B>=E ], cost: 1
31.18/18.16	
31.18/18.16	     16: evalrank1bb3in -> evalrank1critedgein : [ E>=1+B ], cost: 1
31.18/18.16	
31.18/18.16	     17: evalrank1bb4in -> evalrank18 : [], cost: 1
31.18/18.16	
31.18/18.16	     18: evalrank18 -> evalrank19 : H'=free_1, [], cost: 1
31.18/18.16	
31.18/18.16	     19: evalrank19 -> evalrank1bb5in : [ H>=1 ], cost: 1
31.18/18.16	
31.18/18.16	     20: evalrank19 -> evalrank1critedgein : [ 0>=H ], cost: 1
31.18/18.16	
31.18/18.16	     21: evalrank1bb5in -> evalrank1bb3in : E'=1+E, [], cost: 1
31.18/18.16	
31.18/18.16	     22: evalrank1critedgein -> evalrank113 : Q'=-1+A, [], cost: 1
31.18/18.16	
31.18/18.16	     23: evalrank113 -> evalrank114 : [], cost: 1
31.18/18.16	
31.18/18.16	     24: evalrank114 -> evalrank1bb6in : F'=Q, G'=E, [], cost: 1
31.18/18.16	
31.18/18.16	     25: evalrank1bb6in -> evalrank1bb1in : A'=F, C'=-1+G, [], cost: 1
31.18/18.16	
31.18/18.16	
31.18/18.16	
31.18/18.16	### Simplification by acceleration and chaining ###
31.18/18.16	
31.18/18.16	
31.18/18.16	
31.18/18.16	Eliminated locations (on linear paths):
31.18/18.16	
31.18/18.16	   Start location: evalrank1start
31.18/18.16	
31.18/18.16	     33: evalrank1start -> evalrank1bb1in : A'=B, C'=0, [], cost: 8
31.18/18.16	
31.18/18.16	     35: evalrank1bb1in -> evalrank17 : D'=free, [ A>=0 && C>=0 ], cost: 3
31.18/18.16	
31.18/18.16	     13: evalrank17 -> evalrank1bb3in : E'=C, [ D>=1 ], cost: 1
31.18/18.16	
31.18/18.16	     14: evalrank17 -> evalrank1bb6in : F'=A, G'=C, [ 0>=D ], cost: 1
31.18/18.16	
31.18/18.16	     16: evalrank1bb3in -> evalrank1critedgein : [ E>=1+B ], cost: 1
31.18/18.16	
31.18/18.16	     37: evalrank1bb3in -> evalrank19 : H'=free_1, [ B>=E ], cost: 3
31.18/18.16	
31.18/18.16	     20: evalrank19 -> evalrank1critedgein : [ 0>=H ], cost: 1
31.18/18.16	
31.18/18.16	     38: evalrank19 -> evalrank1bb3in : E'=1+E, [ H>=1 ], cost: 2
31.18/18.16	
31.18/18.16	     40: evalrank1critedgein -> evalrank1bb6in : F'=-1+A, G'=E, Q'=-1+A, [], cost: 3
31.18/18.16	
31.18/18.16	     25: evalrank1bb6in -> evalrank1bb1in : A'=F, C'=-1+G, [], cost: 1
31.18/18.16	
31.18/18.16	
31.18/18.16	
31.18/18.16	Eliminated locations (on tree-shaped paths):
31.18/18.16	
31.18/18.16	   Start location: evalrank1start
31.18/18.16	
31.18/18.16	     33: evalrank1start -> evalrank1bb1in : A'=B, C'=0, [], cost: 8
31.18/18.16	
31.18/18.16	     41: evalrank1bb1in -> evalrank1bb3in : D'=free, E'=C, [ A>=0 && C>=0 && free>=1 ], cost: 4
31.18/18.16	
31.18/18.16	     42: evalrank1bb1in -> evalrank1bb6in : D'=free, F'=A, G'=C, [ A>=0 && C>=0 && 0>=free ], cost: 4
31.18/18.16	
31.18/18.16	     44: evalrank1bb3in -> evalrank1bb3in : E'=1+E, H'=free_1, [ B>=E && free_1>=1 ], cost: 5
31.18/18.16	
31.18/18.16	     45: evalrank1bb3in -> evalrank1bb6in : F'=-1+A, G'=E, Q'=-1+A, [ E>=1+B ], cost: 4
31.18/18.16	
31.18/18.16	     46: evalrank1bb3in -> evalrank1bb6in : F'=-1+A, G'=E, H'=free_1, Q'=-1+A, [ B>=E && 0>=free_1 ], cost: 7
31.18/18.16	
31.18/18.16	     25: evalrank1bb6in -> evalrank1bb1in : A'=F, C'=-1+G, [], cost: 1
31.18/18.16	
31.18/18.16	
31.18/18.16	
31.18/18.16	Accelerating simple loops of location 12.
31.18/18.16	
31.18/18.16	   Accelerating the following rules:
31.18/18.16	
31.18/18.16	     44: evalrank1bb3in -> evalrank1bb3in : E'=1+E, H'=free_1, [ B>=E && free_1>=1 ], cost: 5
31.18/18.16	
31.18/18.16	
31.18/18.16	
31.18/18.16	   Accelerated rule 44 with metering function 1-E+B, yielding the new rule 47.
31.18/18.16	
31.18/18.16	   Removing the simple loops: 44.
31.18/18.16	
31.18/18.16	
31.18/18.16	
31.18/18.16	Accelerated all simple loops using metering functions (where possible):
31.18/18.16	
31.18/18.16	   Start location: evalrank1start
31.18/18.16	
31.18/18.16	     33: evalrank1start -> evalrank1bb1in : A'=B, C'=0, [], cost: 8
31.18/18.16	
31.18/18.16	     41: evalrank1bb1in -> evalrank1bb3in : D'=free, E'=C, [ A>=0 && C>=0 && free>=1 ], cost: 4
31.18/18.16	
31.18/18.16	     42: evalrank1bb1in -> evalrank1bb6in : D'=free, F'=A, G'=C, [ A>=0 && C>=0 && 0>=free ], cost: 4
31.18/18.16	
31.18/18.16	     45: evalrank1bb3in -> evalrank1bb6in : F'=-1+A, G'=E, Q'=-1+A, [ E>=1+B ], cost: 4
31.18/18.16	
31.18/18.16	     46: evalrank1bb3in -> evalrank1bb6in : F'=-1+A, G'=E, H'=free_1, Q'=-1+A, [ B>=E && 0>=free_1 ], cost: 7
31.18/18.16	
31.18/18.16	     47: evalrank1bb3in -> evalrank1bb3in : E'=1+B, H'=free_1, [ B>=E && free_1>=1 ], cost: 5-5*E+5*B
31.18/18.16	
31.18/18.16	     25: evalrank1bb6in -> evalrank1bb1in : A'=F, C'=-1+G, [], cost: 1
31.18/18.16	
31.18/18.16	
31.18/18.16	
31.18/18.16	Chained accelerated rules (with incoming rules):
31.18/18.16	
31.18/18.16	   Start location: evalrank1start
31.18/18.16	
31.18/18.16	     33: evalrank1start -> evalrank1bb1in : A'=B, C'=0, [], cost: 8
31.18/18.16	
31.18/18.16	     41: evalrank1bb1in -> evalrank1bb3in : D'=free, E'=C, [ A>=0 && C>=0 && free>=1 ], cost: 4
31.18/18.16	
31.18/18.16	     42: evalrank1bb1in -> evalrank1bb6in : D'=free, F'=A, G'=C, [ A>=0 && C>=0 && 0>=free ], cost: 4
31.18/18.16	
31.18/18.16	     48: evalrank1bb1in -> evalrank1bb3in : D'=free, E'=1+B, H'=free_1, [ A>=0 && C>=0 && free>=1 && B>=C && free_1>=1 ], cost: 9-5*C+5*B
31.18/18.16	
31.18/18.16	     45: evalrank1bb3in -> evalrank1bb6in : F'=-1+A, G'=E, Q'=-1+A, [ E>=1+B ], cost: 4
31.18/18.16	
31.18/18.16	     46: evalrank1bb3in -> evalrank1bb6in : F'=-1+A, G'=E, H'=free_1, Q'=-1+A, [ B>=E && 0>=free_1 ], cost: 7
31.18/18.16	
31.18/18.16	     25: evalrank1bb6in -> evalrank1bb1in : A'=F, C'=-1+G, [], cost: 1
31.18/18.16	
31.18/18.16	
31.18/18.16	
31.18/18.16	Eliminated locations (on tree-shaped paths):
31.18/18.16	
31.18/18.16	   Start location: evalrank1start
31.18/18.16	
31.18/18.16	     33: evalrank1start -> evalrank1bb1in : A'=B, C'=0, [], cost: 8
31.18/18.16	
31.18/18.16	     52: evalrank1bb1in -> [24] : [ A>=0 && C>=0 && free>=1 && B>=C && free_1>=1 ], cost: 9-5*C+5*B
31.18/18.16	
31.18/18.16	     53: evalrank1bb1in -> evalrank1bb1in : A'=A, C'=-1+C, D'=free, F'=A, G'=C, [ A>=0 && C>=0 && 0>=free ], cost: 5
31.18/18.16	
31.18/18.16	     54: evalrank1bb1in -> evalrank1bb1in : A'=-1+A, C'=-1+C, D'=free, E'=C, F'=-1+A, G'=C, Q'=-1+A, [ A>=0 && C>=0 && free>=1 && C>=1+B ], cost: 9
31.18/18.16	
31.18/18.16	     55: evalrank1bb1in -> evalrank1bb1in : A'=-1+A, C'=-1+C, D'=free, E'=C, F'=-1+A, G'=C, H'=free_1, Q'=-1+A, [ A>=0 && C>=0 && free>=1 && B>=C && 0>=free_1 ], cost: 12
31.18/18.16	
31.18/18.16	     56: evalrank1bb1in -> evalrank1bb1in : A'=-1+A, C'=B, D'=free, E'=1+B, F'=-1+A, G'=1+B, H'=free_1, Q'=-1+A, [ A>=0 && C>=0 && free>=1 && B>=C && free_1>=1 ], cost: 14-5*C+5*B
31.18/18.16	
31.18/18.16	
31.18/18.16	
31.18/18.16	Accelerating simple loops of location 8.
31.18/18.16	
31.18/18.16	   Simplified some of the simple loops (and removed duplicate rules).
31.18/18.16	
31.18/18.16	   Accelerating the following rules:
31.18/18.16	
31.18/18.16	     53: evalrank1bb1in -> evalrank1bb1in : C'=-1+C, D'=free, F'=A, G'=C, [ A>=0 && C>=0 && 0>=free ], cost: 5
31.18/18.16	
31.18/18.16	     54: evalrank1bb1in -> evalrank1bb1in : A'=-1+A, C'=-1+C, D'=free, E'=C, F'=-1+A, G'=C, Q'=-1+A, [ A>=0 && C>=0 && free>=1 && C>=1+B ], cost: 9
31.18/18.16	
31.18/18.16	     55: evalrank1bb1in -> evalrank1bb1in : A'=-1+A, C'=-1+C, D'=free, E'=C, F'=-1+A, G'=C, H'=free_1, Q'=-1+A, [ A>=0 && C>=0 && free>=1 && B>=C && 0>=free_1 ], cost: 12
31.18/18.16	
31.18/18.16	     56: evalrank1bb1in -> evalrank1bb1in : A'=-1+A, C'=B, D'=free, E'=1+B, F'=-1+A, G'=1+B, H'=free_1, Q'=-1+A, [ A>=0 && C>=0 && free>=1 && B>=C && free_1>=1 ], cost: 14-5*C+5*B
31.18/18.16	
31.18/18.16	
31.18/18.16	
31.18/18.16	   Accelerated rule 53 with metering function 1+C, yielding the new rule 57.
31.18/18.16	
31.18/18.16	   Accelerated rule 54 with backward acceleration, yielding the new rule 58.
31.18/18.16	
31.18/18.16	   Accelerated rule 54 with backward acceleration, yielding the new rule 59.
31.18/18.16	
31.18/18.16	   Accelerated rule 54 with backward acceleration, yielding the new rule 60.
31.18/18.16	
31.18/18.16	   Accelerated rule 55 with metering function 1+C (after adding A>=C), yielding the new rule 61.
31.18/18.16	
31.18/18.16	   Accelerated rule 55 with metering function 1+A (after adding A<=C), yielding the new rule 62.
31.18/18.16	
31.18/18.16	   Accelerated rule 56 with metering function 1+A, yielding the new rule 63.
31.18/18.16	
31.18/18.16	   Removing the simple loops: 53 54 55 56.
31.18/18.16	
31.18/18.16	
31.18/18.16	
31.18/18.16	Accelerated all simple loops using metering functions (where possible):
31.18/18.16	
31.18/18.16	   Start location: evalrank1start
31.18/18.16	
31.18/18.16	     33: evalrank1start -> evalrank1bb1in : A'=B, C'=0, [], cost: 8
31.18/18.16	
31.18/18.16	     52: evalrank1bb1in -> [24] : [ A>=0 && C>=0 && free>=1 && B>=C && free_1>=1 ], cost: 9-5*C+5*B
31.18/18.16	
31.18/18.16	     57: evalrank1bb1in -> evalrank1bb1in : C'=-1, D'=free, F'=A, G'=0, [ A>=0 && C>=0 && 0>=free ], cost: 5+5*C
31.18/18.16	
31.18/18.16	     58: evalrank1bb1in -> evalrank1bb1in : A'=-1, C'=-1+C-A, D'=free, E'=C-A, F'=-1, G'=C-A, Q'=-1, [ A>=0 && C>=0 && free>=1 && C>=1+B && C-A>=0 && C-A>=1+B ], cost: 9+9*A
31.18/18.16	
31.18/18.16	     59: evalrank1bb1in -> evalrank1bb1in : A'=-1-C+A, C'=-1, D'=free, E'=0, F'=-1-C+A, G'=0, Q'=-1-C+A, [ A>=0 && C>=0 && free>=1 && C>=1+B && -C+A>=0 && 0>=1+B ], cost: 9+9*C
31.18/18.16	
31.18/18.16	     60: evalrank1bb1in -> evalrank1bb1in : A'=-C+A+B, C'=B, D'=free, E'=1+B, F'=-C+A+B, G'=1+B, Q'=-C+A+B, [ A>=0 && C>=0 && free>=1 && C>=1+B && 1-C+A+B>=0 && 1+B>=0 ], cost: 9*C-9*B
31.18/18.16	
31.18/18.16	     61: evalrank1bb1in -> evalrank1bb1in : A'=-1-C+A, C'=-1, D'=free, E'=0, F'=-1-C+A, G'=0, H'=free_1, Q'=-1-C+A, [ A>=0 && C>=0 && free>=1 && B>=C && 0>=free_1 && A>=C ], cost: 12+12*C
31.18/18.16	
31.18/18.16	     62: evalrank1bb1in -> evalrank1bb1in : A'=-1, C'=-1+C-A, D'=free, E'=C-A, F'=-1, G'=C-A, H'=free_1, Q'=-1, [ A>=0 && C>=0 && free>=1 && B>=C && 0>=free_1 && A<=C ], cost: 12+12*A
31.18/18.16	
31.18/18.16	     63: evalrank1bb1in -> evalrank1bb1in : A'=-1, C'=B, D'=free, E'=1+B, F'=-1, G'=1+B, H'=free_1, Q'=-1, [ A>=0 && C>=0 && free>=1 && B>=C && free_1>=1 ], cost: 14+14*A
31.18/18.16	
31.18/18.16	
31.18/18.16	
31.18/18.16	Chained accelerated rules (with incoming rules):
31.18/18.16	
31.18/18.16	   Start location: evalrank1start
31.18/18.16	
31.18/18.16	     33: evalrank1start -> evalrank1bb1in : A'=B, C'=0, [], cost: 8
31.18/18.16	
31.18/18.16	     64: evalrank1start -> evalrank1bb1in : A'=B, C'=-1, D'=free, F'=B, G'=0, [ B>=0 && 0>=free ], cost: 13
31.18/18.16	
31.18/18.16	     65: evalrank1start -> evalrank1bb1in : A'=-1+B, C'=-1, D'=free, E'=0, F'=-1+B, G'=0, H'=free_1, Q'=-1+B, [ B>=0 && free>=1 && 0>=free_1 ], cost: 20
31.18/18.16	
31.18/18.16	     66: evalrank1start -> evalrank1bb1in : A'=-1, C'=-1-B, D'=free, E'=-B, F'=-1, G'=-B, H'=free_1, Q'=-1, [ -B==0 && free>=1 && 0>=free_1 ], cost: 20+12*B
31.18/18.16	
31.18/18.16	     67: evalrank1start -> evalrank1bb1in : A'=-1, C'=B, D'=free, E'=1+B, F'=-1, G'=1+B, H'=free_1, Q'=-1, [ B>=0 && free>=1 && free_1>=1 ], cost: 22+14*B
31.18/18.16	
31.18/18.16	     52: evalrank1bb1in -> [24] : [ A>=0 && C>=0 && free>=1 && B>=C && free_1>=1 ], cost: 9-5*C+5*B
31.18/18.16	
31.18/18.16	
31.18/18.16	
31.18/18.16	Eliminated locations (on tree-shaped paths):
31.18/18.16	
31.18/18.16	   Start location: evalrank1start
31.18/18.16	
31.18/18.16	     68: evalrank1start -> [24] : A'=B, C'=0, [ B>=0 && free>=1 && free_1>=1 ], cost: 17+5*B
31.18/18.16	
31.18/18.16	     69: evalrank1start -> [26] : [ -B==0 && free>=1 && 0>=free_1 ], cost: 20+12*B
31.18/18.16	
31.18/18.16	     70: evalrank1start -> [26] : [ B>=0 && free>=1 && free_1>=1 ], cost: 22+14*B
31.18/18.16	
31.18/18.16	
31.18/18.16	
31.18/18.16	### Computing asymptotic complexity ###
31.18/18.16	
31.18/18.16	
31.18/18.16	
31.18/18.16	Fully simplified ITS problem
31.18/18.16	
31.18/18.16	   Start location: evalrank1start
31.18/18.16	
31.18/18.16	     68: evalrank1start -> [24] : A'=B, C'=0, [ B>=0 && free>=1 && free_1>=1 ], cost: 17+5*B
31.18/18.16	
31.18/18.16	     69: evalrank1start -> [26] : [ -B==0 && free>=1 && 0>=free_1 ], cost: 20+12*B
31.18/18.16	
31.18/18.16	     70: evalrank1start -> [26] : [ B>=0 && free>=1 && free_1>=1 ], cost: 22+14*B
31.18/18.16	
31.18/18.16	
31.18/18.16	
31.18/18.16	Computing asymptotic complexity for rule 68
31.18/18.16	
31.18/18.16	   Solved the limit problem by the following transformations:
31.18/18.16	
31.18/18.16	      Created initial limit problem:
31.18/18.16	
31.18/18.16	      free_1 (+/+!), 1+B (+/+!), 17+5*B (+), free (+/+!) [not solved]
31.18/18.16	
31.18/18.16	
31.18/18.16	
31.18/18.16	      removing all constraints (solved by SMT)
31.18/18.16	
31.18/18.16	      resulting limit problem: [solved]
31.18/18.16	
31.18/18.16	
31.18/18.16	
31.18/18.16	      applying transformation rule (C) using substitution {free_1==n,free==n,B==n}
31.18/18.16	
31.18/18.16	      resulting limit problem:
31.18/18.16	
31.18/18.16	      [solved]
31.18/18.16	
31.18/18.16	
31.18/18.16	
31.18/18.16	   Solution:
31.18/18.16	
31.18/18.16	      free_1 / n
31.18/18.16	
31.18/18.16	      free / n
31.18/18.16	
31.18/18.16	      B / n
31.18/18.16	
31.18/18.16	   Resulting cost 17+5*n has complexity: Poly(n^1)
31.18/18.16	
31.18/18.16	
31.18/18.16	
31.18/18.16	Found new complexity Poly(n^1).
31.18/18.16	
31.18/18.16	
31.18/18.16	
31.18/18.16	Obtained the following overall complexity (w.r.t. the length of the input n):
31.18/18.16	
31.18/18.16	   Complexity:  Poly(n^1)
31.18/18.16	
31.18/18.16	   Cpx degree:  1
31.18/18.16	
31.18/18.16	   Solved cost: 17+5*n
31.18/18.16	
31.18/18.16	   Rule cost:   17+5*B
31.18/18.16	
31.18/18.16	   Rule guard:  [ B>=0 && free>=1 && free_1>=1 ]
31.18/18.16	
31.18/18.16	
31.18/18.16	
31.18/18.16	WORST_CASE(Omega(n^1),?)
31.18/18.16	
31.18/18.16	
31.18/18.16	----------------------------------------
31.18/18.16	
31.18/18.16	(2)
31.18/18.16	BOUNDS(n^1, INF)
31.18/18.20	EOF