33.05/19.40	WORST_CASE(Omega(n^1), ?)
33.05/19.41	proof of /export/starexec/sandbox/benchmark/theBenchmark.koat
33.05/19.41	# AProVE Commit ID: 48fb2092695e11cc9f56e44b17a92a5f88ffb256 marcel 20180622 unpublished dirty
33.05/19.41	
33.05/19.41	
33.05/19.41	The runtime complexity of the given CpxIntTrs could be proven to be BOUNDS(n^1, INF).
33.05/19.41	
33.05/19.41	(0) CpxIntTrs
33.05/19.41	(1) Loat Proof [FINISHED, 2422 ms]
33.05/19.41	(2) BOUNDS(n^1, INF)
33.05/19.41	
33.05/19.41	
33.05/19.41	----------------------------------------
33.05/19.41	
33.05/19.41	(0)
33.05/19.41	Obligation:
33.05/19.41	Complexity Int TRS consisting of the following rules:
33.05/19.41	eval_counterex1a_start(v__0, v__01, v__04, v_4, v_5, v_7, v_8, v_b, v_n, v_x, v_y) -> Com_1(eval_counterex1a_bb0_in(v__0, v__01, v__04, v_4, v_5, v_7, v_8, v_b, v_n, v_x, v_y)) :|: TRUE
33.05/19.41	eval_counterex1a_bb0_in(v__0, v__01, v__04, v_4, v_5, v_7, v_8, v_b, v_n, v_x, v_y) -> Com_1(eval_counterex1a_0(v__0, v__01, v__04, v_4, v_5, v_7, v_8, v_b, v_n, v_x, v_y)) :|: TRUE
33.05/19.41	eval_counterex1a_0(v__0, v__01, v__04, v_4, v_5, v_7, v_8, v_b, v_n, v_x, v_y) -> Com_1(eval_counterex1a_1(v__0, v__01, v__04, v_4, v_5, v_7, v_8, v_b, v_n, v_x, v_y)) :|: TRUE
33.05/19.41	eval_counterex1a_1(v__0, v__01, v__04, v_4, v_5, v_7, v_8, v_b, v_n, v_x, v_y) -> Com_1(eval_counterex1a_2(v__0, v__01, v__04, v_4, v_5, v_7, v_8, v_b, v_n, v_x, v_y)) :|: TRUE
33.05/19.41	eval_counterex1a_2(v__0, v__01, v__04, v_4, v_5, v_7, v_8, v_b, v_n, v_x, v_y) -> Com_1(eval_counterex1a_3(v__0, v__01, v__04, v_4, v_5, v_7, v_8, v_b, v_n, v_x, v_y)) :|: TRUE
33.05/19.41	eval_counterex1a_3(v__0, v__01, v__04, v_4, v_5, v_7, v_8, v_b, v_n, v_x, v_y) -> Com_1(eval_counterex1a_4(v__0, v__01, v__04, v_4, v_5, v_7, v_8, v_b, v_n, v_x, v_y)) :|: TRUE
33.05/19.41	eval_counterex1a_4(v__0, v__01, v__04, v_4, v_5, v_7, v_8, v_b, v_n, v_x, v_y) -> Com_1(eval_counterex1a_5(v__0, v__01, v__04, v_4, v_5, v_7, v_8, v_b, v_n, v_x, v_y)) :|: TRUE
33.05/19.41	eval_counterex1a_5(v__0, v__01, v__04, v_4, v_5, v_7, v_8, v_b, v_n, v_x, v_y) -> Com_1(eval_counterex1a_6(v__0, v__01, v__04, v_4, v_5, v_7, v_8, v_b, v_n, v_x, v_y)) :|: TRUE
33.05/19.41	eval_counterex1a_6(v__0, v__01, v__04, v_4, v_5, v_7, v_8, v_b, v_n, v_x, v_y) -> Com_1(eval_counterex1a_7(v__0, v__01, v__04, v_4, v_5, v_7, v_8, v_b, v_n, v_x, v_y)) :|: TRUE
33.05/19.41	eval_counterex1a_7(v__0, v__01, v__04, v_4, v_5, v_7, v_8, v_b, v_n, v_x, v_y) -> Com_1(eval_counterex1a_8(v__0, v__01, v__04, v_4, v_5, v_7, v_8, v_b, v_n, v_x, v_y)) :|: TRUE
33.05/19.41	eval_counterex1a_8(v__0, v__01, v__04, v_4, v_5, v_7, v_8, v_b, v_n, v_x, v_y) -> Com_1(eval_counterex1a_9(v__0, v__01, v__04, v_4, v_5, v_7, v_8, v_b, v_n, v_x, v_y)) :|: TRUE
33.05/19.41	eval_counterex1a_9(v__0, v__01, v__04, v_4, v_5, v_7, v_8, v_b, v_n, v_x, v_y) -> Com_1(eval_counterex1a_bb1_in(v_b, v_x, v_y, v_4, v_5, v_7, v_8, v_b, v_n, v_x, v_y)) :|: TRUE
33.05/19.41	eval_counterex1a_bb1_in(v__0, v__01, v__04, v_4, v_5, v_7, v_8, v_b, v_n, v_x, v_y) -> Com_1(eval_counterex1a_bb2_in(v__0, v__01, v__04, v_4, v_5, v_7, v_8, v_b, v_n, v_x, v_y)) :|: v__01 >= 0 && 0 <= v__04 && v__04 <= v_n
33.05/19.41	eval_counterex1a_bb1_in(v__0, v__01, v__04, v_4, v_5, v_7, v_8, v_b, v_n, v_x, v_y) -> Com_1(eval_counterex1a__critedge_in(v__0, v__01, v__04, v_4, v_5, v_7, v_8, v_b, v_n, v_x, v_y)) :|: v__01 < 0
33.05/19.41	eval_counterex1a_bb1_in(v__0, v__01, v__04, v_4, v_5, v_7, v_8, v_b, v_n, v_x, v_y) -> Com_1(eval_counterex1a__critedge_in(v__0, v__01, v__04, v_4, v_5, v_7, v_8, v_b, v_n, v_x, v_y)) :|: 0 > v__04
33.05/19.41	eval_counterex1a_bb1_in(v__0, v__01, v__04, v_4, v_5, v_7, v_8, v_b, v_n, v_x, v_y) -> Com_1(eval_counterex1a__critedge_in(v__0, v__01, v__04, v_4, v_5, v_7, v_8, v_b, v_n, v_x, v_y)) :|: v__04 > v_n
33.05/19.41	eval_counterex1a_bb2_in(v__0, v__01, v__04, v_4, v_5, v_7, v_8, v_b, v_n, v_x, v_y) -> Com_1(eval_counterex1a_bb3_in(v__0, v__01, v__04, v_4, v_5, v_7, v_8, v_b, v_n, v_x, v_y)) :|: v__0 >= 0 && v__0 <= 0
33.05/19.41	eval_counterex1a_bb2_in(v__0, v__01, v__04, v_4, v_5, v_7, v_8, v_b, v_n, v_x, v_y) -> Com_1(eval_counterex1a_bb4_in(v__0, v__01, v__04, v_4, v_5, v_7, v_8, v_b, v_n, v_x, v_y)) :|: v__0 < 0
33.05/19.41	eval_counterex1a_bb2_in(v__0, v__01, v__04, v_4, v_5, v_7, v_8, v_b, v_n, v_x, v_y) -> Com_1(eval_counterex1a_bb4_in(v__0, v__01, v__04, v_4, v_5, v_7, v_8, v_b, v_n, v_x, v_y)) :|: v__0 > 0
33.05/19.41	eval_counterex1a_bb3_in(v__0, v__01, v__04, v_4, v_5, v_7, v_8, v_b, v_n, v_x, v_y) -> Com_1(eval_counterex1a_11(v__0, v__01, v__04, v__04 + 1, v_5, v_7, v_8, v_b, v_n, v_x, v_y)) :|: TRUE
33.05/19.41	eval_counterex1a_11(v__0, v__01, v__04, v_4, v_5, v_7, v_8, v_b, v_n, v_x, v_y) -> Com_1(eval_counterex1a_12(v__0, v__01, v__04, v_4, nondef_0, v_7, v_8, v_b, v_n, v_x, v_y)) :|: TRUE
33.05/19.41	eval_counterex1a_12(v__0, v__01, v__04, v_4, v_5, v_7, v_8, v_b, v_n, v_x, v_y) -> Com_1(eval_counterex1a_bb1_in(1, v__01, v_4, v_4, v_5, v_7, v_8, v_b, v_n, v_x, v_y)) :|: v_5 > 0
33.05/19.41	eval_counterex1a_12(v__0, v__01, v__04, v_4, v_5, v_7, v_8, v_b, v_n, v_x, v_y) -> Com_1(eval_counterex1a_bb1_in(v__0, v__01, v_4, v_4, v_5, v_7, v_8, v_b, v_n, v_x, v_y)) :|: v_5 <= 0
33.05/19.41	eval_counterex1a_bb4_in(v__0, v__01, v__04, v_4, v_5, v_7, v_8, v_b, v_n, v_x, v_y) -> Com_1(eval_counterex1a_15(v__0, v__01, v__04, v_4, v_5, v__04 - 1, v_8, v_b, v_n, v_x, v_y)) :|: TRUE
33.05/19.41	eval_counterex1a_15(v__0, v__01, v__04, v_4, v_5, v_7, v_8, v_b, v_n, v_x, v_y) -> Com_1(eval_counterex1a_16(v__0, v__01, v__04, v_4, v_5, v_7, nondef_1, v_b, v_n, v_x, v_y)) :|: TRUE
33.05/19.41	eval_counterex1a_16(v__0, v__01, v__04, v_4, v_5, v_7, v_8, v_b, v_n, v_x, v_y) -> Com_1(eval_counterex1a_bb1_in(0, v__01 - 1, v_7, v_4, v_5, v_7, v_8, v_b, v_n, v_x, v_y)) :|: v_8 > 0
33.05/19.41	eval_counterex1a_16(v__0, v__01, v__04, v_4, v_5, v_7, v_8, v_b, v_n, v_x, v_y) -> Com_1(eval_counterex1a_bb1_in(v__0, v__01 - 1, v_7, v_4, v_5, v_7, v_8, v_b, v_n, v_x, v_y)) :|: v_8 > 0 && v_8 <= 0
33.05/19.41	eval_counterex1a_16(v__0, v__01, v__04, v_4, v_5, v_7, v_8, v_b, v_n, v_x, v_y) -> Com_1(eval_counterex1a_bb1_in(0, v__01, v_7, v_4, v_5, v_7, v_8, v_b, v_n, v_x, v_y)) :|: v_8 <= 0 && v_8 > 0
33.05/19.41	eval_counterex1a_16(v__0, v__01, v__04, v_4, v_5, v_7, v_8, v_b, v_n, v_x, v_y) -> Com_1(eval_counterex1a_bb1_in(v__0, v__01, v_7, v_4, v_5, v_7, v_8, v_b, v_n, v_x, v_y)) :|: v_8 <= 0
33.05/19.41	eval_counterex1a__critedge_in(v__0, v__01, v__04, v_4, v_5, v_7, v_8, v_b, v_n, v_x, v_y) -> Com_1(eval_counterex1a_stop(v__0, v__01, v__04, v_4, v_5, v_7, v_8, v_b, v_n, v_x, v_y)) :|: TRUE
33.05/19.41	
33.05/19.41	The start-symbols are:[eval_counterex1a_start_11]
33.05/19.41	
33.05/19.41	
33.05/19.41	----------------------------------------
33.05/19.41	
33.05/19.41	(1) Loat Proof (FINISHED)
33.05/19.41	
33.05/19.41	
33.05/19.41	### Pre-processing the ITS problem ###
33.05/19.41	
33.05/19.41	
33.05/19.41	
33.05/19.41	Initial linear ITS problem
33.05/19.41	
33.05/19.41	   Start location: evalcounterex1astart
33.05/19.41	
33.05/19.41	      0: evalcounterex1astart -> evalcounterex1abb0in : [], cost: 1
33.05/19.41	
33.05/19.41	      1: evalcounterex1abb0in -> evalcounterex1a0 : [], cost: 1
33.05/19.41	
33.05/19.41	      2: evalcounterex1a0 -> evalcounterex1a1 : [], cost: 1
33.05/19.41	
33.05/19.41	      3: evalcounterex1a1 -> evalcounterex1a2 : [], cost: 1
33.05/19.41	
33.05/19.41	      4: evalcounterex1a2 -> evalcounterex1a3 : [], cost: 1
33.05/19.41	
33.05/19.41	      5: evalcounterex1a3 -> evalcounterex1a4 : [], cost: 1
33.05/19.41	
33.05/19.41	      6: evalcounterex1a4 -> evalcounterex1a5 : [], cost: 1
33.05/19.41	
33.05/19.41	      7: evalcounterex1a5 -> evalcounterex1a6 : [], cost: 1
33.05/19.41	
33.05/19.41	      8: evalcounterex1a6 -> evalcounterex1a7 : [], cost: 1
33.05/19.41	
33.05/19.41	      9: evalcounterex1a7 -> evalcounterex1a8 : [], cost: 1
33.05/19.41	
33.05/19.41	     10: evalcounterex1a8 -> evalcounterex1a9 : [], cost: 1
33.05/19.41	
33.05/19.41	     11: evalcounterex1a9 -> evalcounterex1abb1in : A'=B, C'=D, E'=F, [], cost: 1
33.05/19.41	
33.05/19.41	     12: evalcounterex1abb1in -> evalcounterex1abb2in : [ C>=0 && E>=0 && G>=E ], cost: 1
33.05/19.41	
33.05/19.41	     13: evalcounterex1abb1in -> evalcounterex1acritedgein : [ 0>=1+C ], cost: 1
33.05/19.41	
33.05/19.41	     14: evalcounterex1abb1in -> evalcounterex1acritedgein : [ 0>=1+E ], cost: 1
33.05/19.41	
33.05/19.41	     15: evalcounterex1abb1in -> evalcounterex1acritedgein : [ E>=1+G ], cost: 1
33.05/19.41	
33.05/19.41	     16: evalcounterex1abb2in -> evalcounterex1abb3in : [ A==0 ], cost: 1
33.05/19.41	
33.05/19.41	     17: evalcounterex1abb2in -> evalcounterex1abb4in : [ 0>=1+A ], cost: 1
33.05/19.41	
33.05/19.41	     18: evalcounterex1abb2in -> evalcounterex1abb4in : [ A>=1 ], cost: 1
33.05/19.41	
33.05/19.41	     19: evalcounterex1abb3in -> evalcounterex1a11 : H'=1+E, [], cost: 1
33.05/19.41	
33.05/19.41	     20: evalcounterex1a11 -> evalcounterex1a12 : Q'=free, [], cost: 1
33.05/19.41	
33.05/19.41	     21: evalcounterex1a12 -> evalcounterex1abb1in : A'=1, E'=H, [ Q>=1 ], cost: 1
33.05/19.41	
33.05/19.41	     22: evalcounterex1a12 -> evalcounterex1abb1in : E'=H, [ 0>=Q ], cost: 1
33.05/19.41	
33.05/19.41	     23: evalcounterex1abb4in -> evalcounterex1a15 : J'=-1+E, [], cost: 1
33.05/19.41	
33.05/19.41	     24: evalcounterex1a15 -> evalcounterex1a16 : K'=free_1, [], cost: 1
33.05/19.41	
33.05/19.41	     25: evalcounterex1a16 -> evalcounterex1abb1in : A'=0, C'=-1+C, E'=J, [ K>=1 ], cost: 1
33.05/19.41	
33.05/19.41	     26: evalcounterex1a16 -> evalcounterex1abb1in : C'=-1+C, E'=J, [ K>=1 && 0>=K ], cost: 1
33.05/19.41	
33.05/19.41	     27: evalcounterex1a16 -> evalcounterex1abb1in : A'=0, E'=J, [ 0>=K && K>=1 ], cost: 1
33.05/19.41	
33.05/19.41	     28: evalcounterex1a16 -> evalcounterex1abb1in : E'=J, [ 0>=K ], cost: 1
33.05/19.41	
33.05/19.41	     29: evalcounterex1acritedgein -> evalcounterex1astop : [], cost: 1
33.05/19.41	
33.05/19.41	
33.05/19.41	
33.05/19.41	Removed unreachable and leaf rules:
33.05/19.41	
33.05/19.41	   Start location: evalcounterex1astart
33.05/19.41	
33.05/19.41	      0: evalcounterex1astart -> evalcounterex1abb0in : [], cost: 1
33.05/19.41	
33.05/19.41	      1: evalcounterex1abb0in -> evalcounterex1a0 : [], cost: 1
33.05/19.41	
33.05/19.41	      2: evalcounterex1a0 -> evalcounterex1a1 : [], cost: 1
33.05/19.41	
33.05/19.41	      3: evalcounterex1a1 -> evalcounterex1a2 : [], cost: 1
33.05/19.41	
33.05/19.41	      4: evalcounterex1a2 -> evalcounterex1a3 : [], cost: 1
33.05/19.41	
33.05/19.41	      5: evalcounterex1a3 -> evalcounterex1a4 : [], cost: 1
33.05/19.41	
33.05/19.41	      6: evalcounterex1a4 -> evalcounterex1a5 : [], cost: 1
33.05/19.41	
33.05/19.41	      7: evalcounterex1a5 -> evalcounterex1a6 : [], cost: 1
33.05/19.41	
33.05/19.41	      8: evalcounterex1a6 -> evalcounterex1a7 : [], cost: 1
33.05/19.41	
33.05/19.41	      9: evalcounterex1a7 -> evalcounterex1a8 : [], cost: 1
33.05/19.41	
33.05/19.41	     10: evalcounterex1a8 -> evalcounterex1a9 : [], cost: 1
33.05/19.41	
33.05/19.41	     11: evalcounterex1a9 -> evalcounterex1abb1in : A'=B, C'=D, E'=F, [], cost: 1
33.05/19.41	
33.05/19.41	     12: evalcounterex1abb1in -> evalcounterex1abb2in : [ C>=0 && E>=0 && G>=E ], cost: 1
33.05/19.41	
33.05/19.41	     16: evalcounterex1abb2in -> evalcounterex1abb3in : [ A==0 ], cost: 1
33.05/19.41	
33.05/19.41	     17: evalcounterex1abb2in -> evalcounterex1abb4in : [ 0>=1+A ], cost: 1
33.05/19.41	
33.05/19.41	     18: evalcounterex1abb2in -> evalcounterex1abb4in : [ A>=1 ], cost: 1
33.05/19.41	
33.05/19.41	     19: evalcounterex1abb3in -> evalcounterex1a11 : H'=1+E, [], cost: 1
33.05/19.41	
33.05/19.41	     20: evalcounterex1a11 -> evalcounterex1a12 : Q'=free, [], cost: 1
33.05/19.41	
33.05/19.41	     21: evalcounterex1a12 -> evalcounterex1abb1in : A'=1, E'=H, [ Q>=1 ], cost: 1
33.05/19.41	
33.05/19.41	     22: evalcounterex1a12 -> evalcounterex1abb1in : E'=H, [ 0>=Q ], cost: 1
33.05/19.41	
33.05/19.41	     23: evalcounterex1abb4in -> evalcounterex1a15 : J'=-1+E, [], cost: 1
33.05/19.41	
33.05/19.41	     24: evalcounterex1a15 -> evalcounterex1a16 : K'=free_1, [], cost: 1
33.05/19.41	
33.05/19.41	     25: evalcounterex1a16 -> evalcounterex1abb1in : A'=0, C'=-1+C, E'=J, [ K>=1 ], cost: 1
33.05/19.41	
33.05/19.41	     26: evalcounterex1a16 -> evalcounterex1abb1in : C'=-1+C, E'=J, [ K>=1 && 0>=K ], cost: 1
33.05/19.41	
33.05/19.41	     27: evalcounterex1a16 -> evalcounterex1abb1in : A'=0, E'=J, [ 0>=K && K>=1 ], cost: 1
33.05/19.41	
33.05/19.41	     28: evalcounterex1a16 -> evalcounterex1abb1in : E'=J, [ 0>=K ], cost: 1
33.05/19.41	
33.05/19.41	
33.05/19.41	
33.05/19.41	Removed rules with unsatisfiable guard:
33.05/19.41	
33.05/19.41	   Start location: evalcounterex1astart
33.05/19.41	
33.05/19.41	      0: evalcounterex1astart -> evalcounterex1abb0in : [], cost: 1
33.05/19.41	
33.05/19.41	      1: evalcounterex1abb0in -> evalcounterex1a0 : [], cost: 1
33.05/19.41	
33.05/19.41	      2: evalcounterex1a0 -> evalcounterex1a1 : [], cost: 1
33.05/19.41	
33.05/19.41	      3: evalcounterex1a1 -> evalcounterex1a2 : [], cost: 1
33.05/19.41	
33.05/19.41	      4: evalcounterex1a2 -> evalcounterex1a3 : [], cost: 1
33.05/19.41	
33.05/19.41	      5: evalcounterex1a3 -> evalcounterex1a4 : [], cost: 1
33.05/19.41	
33.05/19.41	      6: evalcounterex1a4 -> evalcounterex1a5 : [], cost: 1
33.05/19.41	
33.05/19.41	      7: evalcounterex1a5 -> evalcounterex1a6 : [], cost: 1
33.05/19.41	
33.05/19.41	      8: evalcounterex1a6 -> evalcounterex1a7 : [], cost: 1
33.05/19.41	
33.05/19.41	      9: evalcounterex1a7 -> evalcounterex1a8 : [], cost: 1
33.05/19.41	
33.05/19.41	     10: evalcounterex1a8 -> evalcounterex1a9 : [], cost: 1
33.05/19.41	
33.05/19.41	     11: evalcounterex1a9 -> evalcounterex1abb1in : A'=B, C'=D, E'=F, [], cost: 1
33.05/19.41	
33.05/19.41	     12: evalcounterex1abb1in -> evalcounterex1abb2in : [ C>=0 && E>=0 && G>=E ], cost: 1
33.05/19.41	
33.05/19.41	     16: evalcounterex1abb2in -> evalcounterex1abb3in : [ A==0 ], cost: 1
33.05/19.41	
33.05/19.41	     17: evalcounterex1abb2in -> evalcounterex1abb4in : [ 0>=1+A ], cost: 1
33.05/19.41	
33.05/19.41	     18: evalcounterex1abb2in -> evalcounterex1abb4in : [ A>=1 ], cost: 1
33.05/19.41	
33.05/19.41	     19: evalcounterex1abb3in -> evalcounterex1a11 : H'=1+E, [], cost: 1
33.05/19.41	
33.05/19.41	     20: evalcounterex1a11 -> evalcounterex1a12 : Q'=free, [], cost: 1
33.05/19.41	
33.05/19.41	     21: evalcounterex1a12 -> evalcounterex1abb1in : A'=1, E'=H, [ Q>=1 ], cost: 1
33.05/19.41	
33.05/19.41	     22: evalcounterex1a12 -> evalcounterex1abb1in : E'=H, [ 0>=Q ], cost: 1
33.05/19.41	
33.05/19.41	     23: evalcounterex1abb4in -> evalcounterex1a15 : J'=-1+E, [], cost: 1
33.05/19.41	
33.05/19.41	     24: evalcounterex1a15 -> evalcounterex1a16 : K'=free_1, [], cost: 1
33.05/19.41	
33.05/19.41	     25: evalcounterex1a16 -> evalcounterex1abb1in : A'=0, C'=-1+C, E'=J, [ K>=1 ], cost: 1
33.05/19.41	
33.05/19.41	     28: evalcounterex1a16 -> evalcounterex1abb1in : E'=J, [ 0>=K ], cost: 1
33.05/19.41	
33.05/19.41	
33.05/19.41	
33.05/19.41	### Simplification by acceleration and chaining ###
33.05/19.41	
33.05/19.41	
33.05/19.41	
33.05/19.41	Eliminated locations (on linear paths):
33.05/19.41	
33.05/19.41	   Start location: evalcounterex1astart
33.05/19.41	
33.05/19.41	     40: evalcounterex1astart -> evalcounterex1abb1in : A'=B, C'=D, E'=F, [], cost: 12
33.05/19.41	
33.05/19.41	     12: evalcounterex1abb1in -> evalcounterex1abb2in : [ C>=0 && E>=0 && G>=E ], cost: 1
33.05/19.41	
33.05/19.41	     17: evalcounterex1abb2in -> evalcounterex1abb4in : [ 0>=1+A ], cost: 1
33.05/19.41	
33.05/19.41	     18: evalcounterex1abb2in -> evalcounterex1abb4in : [ A>=1 ], cost: 1
33.05/19.41	
33.05/19.41	     42: evalcounterex1abb2in -> evalcounterex1a12 : H'=1+E, Q'=free, [ A==0 ], cost: 3
33.05/19.41	
33.05/19.41	     21: evalcounterex1a12 -> evalcounterex1abb1in : A'=1, E'=H, [ Q>=1 ], cost: 1
33.05/19.41	
33.05/19.41	     22: evalcounterex1a12 -> evalcounterex1abb1in : E'=H, [ 0>=Q ], cost: 1
33.05/19.41	
33.05/19.41	     43: evalcounterex1abb4in -> evalcounterex1a16 : J'=-1+E, K'=free_1, [], cost: 2
33.05/19.41	
33.05/19.41	     25: evalcounterex1a16 -> evalcounterex1abb1in : A'=0, C'=-1+C, E'=J, [ K>=1 ], cost: 1
33.05/19.41	
33.05/19.41	     28: evalcounterex1a16 -> evalcounterex1abb1in : E'=J, [ 0>=K ], cost: 1
33.05/19.41	
33.05/19.41	
33.05/19.41	
33.05/19.41	Eliminated locations (on tree-shaped paths):
33.05/19.41	
33.05/19.41	   Start location: evalcounterex1astart
33.05/19.41	
33.05/19.41	     40: evalcounterex1astart -> evalcounterex1abb1in : A'=B, C'=D, E'=F, [], cost: 12
33.05/19.41	
33.05/19.41	     44: evalcounterex1abb1in -> evalcounterex1abb4in : [ C>=0 && E>=0 && G>=E && 0>=1+A ], cost: 2
33.05/19.41	
33.05/19.41	     45: evalcounterex1abb1in -> evalcounterex1abb4in : [ C>=0 && E>=0 && G>=E && A>=1 ], cost: 2
33.05/19.41	
33.05/19.41	     46: evalcounterex1abb1in -> evalcounterex1a12 : H'=1+E, Q'=free, [ C>=0 && E>=0 && G>=E && A==0 ], cost: 4
33.05/19.41	
33.05/19.41	     21: evalcounterex1a12 -> evalcounterex1abb1in : A'=1, E'=H, [ Q>=1 ], cost: 1
33.05/19.41	
33.05/19.41	     22: evalcounterex1a12 -> evalcounterex1abb1in : E'=H, [ 0>=Q ], cost: 1
33.05/19.41	
33.05/19.41	     47: evalcounterex1abb4in -> evalcounterex1abb1in : A'=0, C'=-1+C, E'=-1+E, J'=-1+E, K'=free_1, [ free_1>=1 ], cost: 3
33.05/19.41	
33.05/19.41	     48: evalcounterex1abb4in -> evalcounterex1abb1in : E'=-1+E, J'=-1+E, K'=free_1, [ 0>=free_1 ], cost: 3
33.05/19.41	
33.05/19.41	
33.05/19.41	
33.05/19.41	Eliminated locations (on tree-shaped paths):
33.05/19.41	
33.05/19.41	   Start location: evalcounterex1astart
33.05/19.41	
33.05/19.41	     40: evalcounterex1astart -> evalcounterex1abb1in : A'=B, C'=D, E'=F, [], cost: 12
33.05/19.41	
33.05/19.41	     49: evalcounterex1abb1in -> evalcounterex1abb1in : A'=1, E'=1+E, H'=1+E, Q'=free, [ C>=0 && E>=0 && G>=E && A==0 && free>=1 ], cost: 5
33.05/19.41	
33.05/19.41	     50: evalcounterex1abb1in -> evalcounterex1abb1in : E'=1+E, H'=1+E, Q'=free, [ C>=0 && E>=0 && G>=E && A==0 && 0>=free ], cost: 5
33.05/19.41	
33.05/19.41	     51: evalcounterex1abb1in -> evalcounterex1abb1in : A'=0, C'=-1+C, E'=-1+E, J'=-1+E, K'=free_1, [ C>=0 && E>=0 && G>=E && 0>=1+A && free_1>=1 ], cost: 5
33.05/19.41	
33.05/19.41	     52: evalcounterex1abb1in -> evalcounterex1abb1in : E'=-1+E, J'=-1+E, K'=free_1, [ C>=0 && E>=0 && G>=E && 0>=1+A && 0>=free_1 ], cost: 5
33.05/19.41	
33.05/19.41	     53: evalcounterex1abb1in -> evalcounterex1abb1in : A'=0, C'=-1+C, E'=-1+E, J'=-1+E, K'=free_1, [ C>=0 && E>=0 && G>=E && A>=1 && free_1>=1 ], cost: 5
33.05/19.41	
33.05/19.41	     54: evalcounterex1abb1in -> evalcounterex1abb1in : E'=-1+E, J'=-1+E, K'=free_1, [ C>=0 && E>=0 && G>=E && A>=1 && 0>=free_1 ], cost: 5
33.05/19.41	
33.05/19.41	
33.05/19.41	
33.05/19.41	Accelerating simple loops of location 12.
33.05/19.41	
33.05/19.41	   Accelerating the following rules:
33.05/19.41	
33.05/19.41	     49: evalcounterex1abb1in -> evalcounterex1abb1in : A'=1, E'=1+E, H'=1+E, Q'=free, [ C>=0 && E>=0 && G>=E && A==0 && free>=1 ], cost: 5
33.05/19.41	
33.05/19.41	     50: evalcounterex1abb1in -> evalcounterex1abb1in : E'=1+E, H'=1+E, Q'=free, [ C>=0 && E>=0 && G>=E && A==0 && 0>=free ], cost: 5
33.05/19.41	
33.05/19.41	     51: evalcounterex1abb1in -> evalcounterex1abb1in : A'=0, C'=-1+C, E'=-1+E, J'=-1+E, K'=free_1, [ C>=0 && E>=0 && G>=E && 0>=1+A && free_1>=1 ], cost: 5
33.05/19.41	
33.05/19.41	     52: evalcounterex1abb1in -> evalcounterex1abb1in : E'=-1+E, J'=-1+E, K'=free_1, [ C>=0 && E>=0 && G>=E && 0>=1+A && 0>=free_1 ], cost: 5
33.05/19.41	
33.05/19.41	     53: evalcounterex1abb1in -> evalcounterex1abb1in : A'=0, C'=-1+C, E'=-1+E, J'=-1+E, K'=free_1, [ C>=0 && E>=0 && G>=E && A>=1 && free_1>=1 ], cost: 5
33.05/19.41	
33.05/19.41	     54: evalcounterex1abb1in -> evalcounterex1abb1in : E'=-1+E, J'=-1+E, K'=free_1, [ C>=0 && E>=0 && G>=E && A>=1 && 0>=free_1 ], cost: 5
33.05/19.41	
33.05/19.41	
33.05/19.41	
33.05/19.41	   Accelerated rule 49 with metering function -A, yielding the new rule 55.
33.05/19.41	
33.05/19.41	   Accelerated rule 50 with metering function 1+G-E, yielding the new rule 56.
33.05/19.41	
33.05/19.41	   Found no metering function for rule 51.
33.05/19.41	
33.05/19.41	   Accelerated rule 52 with metering function 1+E, yielding the new rule 57.
33.05/19.41	
33.05/19.41	   Found no metering function for rule 53.
33.05/19.41	
33.05/19.41	   Accelerated rule 54 with metering function 1+E, yielding the new rule 58.
33.05/19.41	
33.05/19.41	   Removing the simple loops: 49 50 52 54.
33.05/19.41	
33.05/19.41	
33.05/19.41	
33.05/19.41	Accelerated all simple loops using metering functions (where possible):
33.05/19.41	
33.05/19.41	   Start location: evalcounterex1astart
33.05/19.41	
33.05/19.41	     40: evalcounterex1astart -> evalcounterex1abb1in : A'=B, C'=D, E'=F, [], cost: 12
33.05/19.41	
33.05/19.41	     51: evalcounterex1abb1in -> evalcounterex1abb1in : A'=0, C'=-1+C, E'=-1+E, J'=-1+E, K'=free_1, [ C>=0 && E>=0 && G>=E && 0>=1+A && free_1>=1 ], cost: 5
33.05/19.41	
33.05/19.41	     53: evalcounterex1abb1in -> evalcounterex1abb1in : A'=0, C'=-1+C, E'=-1+E, J'=-1+E, K'=free_1, [ C>=0 && E>=0 && G>=E && A>=1 && free_1>=1 ], cost: 5
33.05/19.41	
33.05/19.41	     55: evalcounterex1abb1in -> evalcounterex1abb1in : A'=1, E'=-A+E, H'=-A+E, Q'=free, [ C>=0 && E>=0 && G>=E && A==0 && free>=1 && -A>=1 ], cost: -5*A
33.05/19.41	
33.05/19.41	     56: evalcounterex1abb1in -> evalcounterex1abb1in : E'=1+G, H'=1+G, Q'=free, [ C>=0 && E>=0 && G>=E && A==0 && 0>=free ], cost: 5+5*G-5*E
33.05/19.41	
33.05/19.41	     57: evalcounterex1abb1in -> evalcounterex1abb1in : E'=-1, J'=-1, K'=free_1, [ C>=0 && E>=0 && G>=E && 0>=1+A && 0>=free_1 ], cost: 5+5*E
33.05/19.41	
33.05/19.41	     58: evalcounterex1abb1in -> evalcounterex1abb1in : E'=-1, J'=-1, K'=free_1, [ C>=0 && E>=0 && G>=E && A>=1 && 0>=free_1 ], cost: 5+5*E
33.05/19.41	
33.05/19.41	
33.05/19.41	
33.05/19.41	Chained accelerated rules (with incoming rules):
33.05/19.41	
33.05/19.41	   Start location: evalcounterex1astart
33.05/19.41	
33.05/19.41	     40: evalcounterex1astart -> evalcounterex1abb1in : A'=B, C'=D, E'=F, [], cost: 12
33.05/19.41	
33.05/19.41	     59: evalcounterex1astart -> evalcounterex1abb1in : A'=0, C'=-1+D, E'=-1+F, J'=-1+F, K'=free_1, [ D>=0 && F>=0 && G>=F && 0>=1+B && free_1>=1 ], cost: 17
33.05/19.41	
33.05/19.41	     60: evalcounterex1astart -> evalcounterex1abb1in : A'=0, C'=-1+D, E'=-1+F, J'=-1+F, K'=free_1, [ D>=0 && F>=0 && G>=F && B>=1 && free_1>=1 ], cost: 17
33.05/19.41	
33.05/19.41	     61: evalcounterex1astart -> evalcounterex1abb1in : A'=B, C'=D, E'=1+G, H'=1+G, Q'=free, [ D>=0 && F>=0 && G>=F && B==0 && 0>=free ], cost: 17-5*F+5*G
33.05/19.41	
33.05/19.41	     62: evalcounterex1astart -> evalcounterex1abb1in : A'=B, C'=D, E'=-1, J'=-1, K'=free_1, [ D>=0 && F>=0 && G>=F && 0>=1+B && 0>=free_1 ], cost: 17+5*F
33.05/19.41	
33.05/19.41	     63: evalcounterex1astart -> evalcounterex1abb1in : A'=B, C'=D, E'=-1, J'=-1, K'=free_1, [ D>=0 && F>=0 && G>=F && B>=1 && 0>=free_1 ], cost: 17+5*F
33.05/19.41	
33.05/19.41	
33.05/19.41	
33.05/19.41	Removed unreachable locations (and leaf rules with constant cost):
33.05/19.41	
33.05/19.41	   Start location: evalcounterex1astart
33.05/19.41	
33.05/19.41	     61: evalcounterex1astart -> evalcounterex1abb1in : A'=B, C'=D, E'=1+G, H'=1+G, Q'=free, [ D>=0 && F>=0 && G>=F && B==0 && 0>=free ], cost: 17-5*F+5*G
33.05/19.41	
33.05/19.41	     62: evalcounterex1astart -> evalcounterex1abb1in : A'=B, C'=D, E'=-1, J'=-1, K'=free_1, [ D>=0 && F>=0 && G>=F && 0>=1+B && 0>=free_1 ], cost: 17+5*F
33.05/19.41	
33.05/19.41	     63: evalcounterex1astart -> evalcounterex1abb1in : A'=B, C'=D, E'=-1, J'=-1, K'=free_1, [ D>=0 && F>=0 && G>=F && B>=1 && 0>=free_1 ], cost: 17+5*F
33.05/19.41	
33.05/19.41	
33.05/19.41	
33.05/19.41	### Computing asymptotic complexity ###
33.05/19.41	
33.05/19.41	
33.05/19.41	
33.05/19.41	Fully simplified ITS problem
33.05/19.41	
33.05/19.41	   Start location: evalcounterex1astart
33.05/19.41	
33.05/19.41	     61: evalcounterex1astart -> evalcounterex1abb1in : A'=B, C'=D, E'=1+G, H'=1+G, Q'=free, [ D>=0 && F>=0 && G>=F && B==0 && 0>=free ], cost: 17-5*F+5*G
33.05/19.41	
33.05/19.41	     62: evalcounterex1astart -> evalcounterex1abb1in : A'=B, C'=D, E'=-1, J'=-1, K'=free_1, [ D>=0 && F>=0 && G>=F && 0>=1+B && 0>=free_1 ], cost: 17+5*F
33.05/19.41	
33.05/19.41	     63: evalcounterex1astart -> evalcounterex1abb1in : A'=B, C'=D, E'=-1, J'=-1, K'=free_1, [ D>=0 && F>=0 && G>=F && B>=1 && 0>=free_1 ], cost: 17+5*F
33.05/19.41	
33.05/19.41	
33.05/19.41	
33.05/19.41	Computing asymptotic complexity for rule 61
33.05/19.41	
33.05/19.41	   Solved the limit problem by the following transformations:
33.05/19.41	
33.05/19.41	      Created initial limit problem:
33.05/19.41	
33.05/19.41	      1-F+G (+/+!), 1+B (+/+!), 17-5*F+5*G (+), 1-B (+/+!), 1+D (+/+!), 1-free (+/+!), 1+F (+/+!) [not solved]
33.05/19.41	
33.05/19.41	
33.05/19.41	
33.05/19.41	      applying transformation rule (C) using substitution {B==0}
33.05/19.41	
33.05/19.41	      resulting limit problem:
33.05/19.41	
33.05/19.41	      1 (+/+!), 1-F+G (+/+!), 17-5*F+5*G (+), 1+D (+/+!), 1-free (+/+!), 1+F (+/+!) [not solved]
33.05/19.41	
33.05/19.41	
33.05/19.41	
33.05/19.41	      applying transformation rule (C) using substitution {D==0}
33.05/19.41	
33.05/19.41	      resulting limit problem:
33.05/19.41	
33.05/19.41	      1 (+/+!), 1-F+G (+/+!), 17-5*F+5*G (+), 1-free (+/+!), 1+F (+/+!) [not solved]
33.05/19.41	
33.05/19.41	
33.05/19.41	
33.05/19.41	      applying transformation rule (C) using substitution {F==0}
33.05/19.41	
33.05/19.41	      resulting limit problem:
33.05/19.41	
33.05/19.41	      1 (+/+!), 17+5*G (+), 1+G (+/+!), 1-free (+/+!) [not solved]
33.05/19.41	
33.05/19.41	
33.05/19.41	
33.05/19.41	      applying transformation rule (C) using substitution {G==F}
33.05/19.41	
33.05/19.41	      resulting limit problem:
33.05/19.41	
33.05/19.41	      1 (+/+!), 1-free (+/+!), 1+F (+/+!), 17+5*F (+) [not solved]
33.05/19.41	
33.05/19.41	
33.05/19.41	
33.05/19.41	      applying transformation rule (C) using substitution {free==0}
33.05/19.41	
33.05/19.41	      resulting limit problem:
33.05/19.41	
33.05/19.41	      1 (+/+!), 1+F (+/+!), 17+5*F (+) [not solved]
33.05/19.41	
33.05/19.41	
33.05/19.41	
33.05/19.41	      applying transformation rule (B), deleting 1 (+/+!)
33.05/19.41	
33.05/19.41	      resulting limit problem:
33.05/19.41	
33.05/19.41	      1+F (+/+!), 17+5*F (+) [not solved]
33.05/19.41	
33.05/19.41	
33.05/19.41	
33.05/19.41	      applying transformation rule (D), replacing 1+F (+/+!) by F (+)
33.05/19.41	
33.05/19.41	      resulting limit problem:
33.05/19.41	
33.05/19.41	      F (+), 17+5*F (+) [not solved]
33.05/19.41	
33.05/19.41	
33.05/19.41	
33.05/19.41	      applying transformation rule (D), replacing 17+5*F (+) by 5*F (+)
33.05/19.41	
33.05/19.41	      resulting limit problem:
33.05/19.41	
33.05/19.41	      F (+), 5*F (+) [not solved]
33.05/19.41	
33.05/19.41	
33.05/19.41	
33.05/19.41	      applying transformation rule (A), replacing 5*F (+) by F (+) and 5 (+!) using + limit vector (+,+!)
33.05/19.41	
33.05/19.41	      resulting limit problem:
33.05/19.41	
33.05/19.41	      F (+), 5 (+!) [not solved]
33.05/19.41	
33.05/19.41	
33.05/19.41	
33.05/19.41	      applying transformation rule (B), deleting 5 (+!)
33.05/19.41	
33.05/19.41	      resulting limit problem:
33.05/19.41	
33.05/19.41	      F (+) [solved]
33.05/19.41	
33.05/19.41	
33.05/19.41	
33.05/19.41	   Solution:
33.05/19.41	
33.05/19.41	      F / 0
33.05/19.41	
33.05/19.41	      free / 0
33.05/19.41	
33.05/19.41	      G / n
33.05/19.41	
33.05/19.41	      D / 0
33.05/19.41	
33.05/19.41	      B / 0
33.05/19.41	
33.05/19.41	   Resulting cost 17+5*n has complexity: Poly(n^1)
33.05/19.41	
33.05/19.41	
33.05/19.41	
33.05/19.41	Found new complexity Poly(n^1).
33.05/19.41	
33.05/19.41	
33.05/19.41	
33.05/19.41	Obtained the following overall complexity (w.r.t. the length of the input n):
33.05/19.41	
33.05/19.41	   Complexity:  Poly(n^1)
33.05/19.41	
33.05/19.41	   Cpx degree:  1
33.05/19.41	
33.05/19.41	   Solved cost: 17+5*n
33.05/19.41	
33.05/19.41	   Rule cost:   17-5*F+5*G
33.05/19.41	
33.05/19.41	   Rule guard:  [ D>=0 && F>=0 && G>=F && B==0 && 0>=free ]
33.05/19.41	
33.05/19.41	
33.05/19.41	
33.05/19.41	WORST_CASE(Omega(n^1),?)
33.05/19.41	
33.05/19.41	
33.05/19.41	----------------------------------------
33.05/19.41	
33.05/19.41	(2)
33.05/19.41	BOUNDS(n^1, INF)
33.13/19.44	EOF