38.11/32.52	WORST_CASE(Omega(n^1), O(n^2))
38.11/32.54	proof of /export/starexec/sandbox2/benchmark/theBenchmark.koat
38.11/32.54	# AProVE Commit ID: 48fb2092695e11cc9f56e44b17a92a5f88ffb256 marcel 20180622 unpublished dirty
38.11/32.54	
38.11/32.54	
38.11/32.54	The runtime complexity of the given CpxIntTrs could be proven to be BOUNDS(n^1, max(11 + 2 * Arg_3, 11) + nat(4 * Arg_3^2) + nat(3 * Arg_3) + max(2, 2 + Arg_3) + nat(21 * Arg_3) + nat(12 * Arg_3) + nat(1 + 7 * Arg_3) + nat(13 * Arg_3) + nat(4 * Arg_3^2) * nat(Arg_3) + nat(Arg_3)^2 + 2 * nat(4 * Arg_3^2) * nat(Arg_3) + 2 * nat(Arg_3)^2 + nat(4 * Arg_3)).
38.11/32.54	
38.11/32.54	(0) CpxIntTrs
38.11/32.54	(1) Loat Proof [FINISHED, 2229 ms]
38.11/32.54	(2) BOUNDS(n^1, INF)
38.11/32.54	
38.11/32.54	
38.11/32.54	----------------------------------------
38.11/32.54	
38.11/32.54	(0)
38.11/32.54	Obligation:
38.11/32.54	Complexity Int TRS consisting of the following rules:
38.11/32.54	eval_xnu_start(v__end_0, v_1, v_2, v_4, v_7, v_beg_0, v_end_0, v_i_0, v_k_0, v_len) -> Com_1(eval_xnu_bb0_in(v__end_0, v_1, v_2, v_4, v_7, v_beg_0, v_end_0, v_i_0, v_k_0, v_len)) :|: TRUE
38.11/32.54	eval_xnu_bb0_in(v__end_0, v_1, v_2, v_4, v_7, v_beg_0, v_end_0, v_i_0, v_k_0, v_len) -> Com_1(eval_xnu_0(v__end_0, v_1, v_2, v_4, v_7, v_beg_0, v_end_0, v_i_0, v_k_0, v_len)) :|: TRUE
38.11/32.54	eval_xnu_0(v__end_0, v_1, v_2, v_4, v_7, v_beg_0, v_end_0, v_i_0, v_k_0, v_len) -> Com_1(eval_xnu_1(v__end_0, v_1, v_2, v_4, v_7, v_beg_0, v_end_0, v_i_0, v_k_0, v_len)) :|: TRUE
38.11/32.54	eval_xnu_1(v__end_0, v_1, v_2, v_4, v_7, v_beg_0, v_end_0, v_i_0, v_k_0, v_len) -> Com_1(eval_xnu_2(v__end_0, v_1, v_2, v_4, v_7, v_beg_0, v_end_0, v_i_0, v_k_0, v_len)) :|: TRUE
38.11/32.54	eval_xnu_2(v__end_0, v_1, v_2, v_4, v_7, v_beg_0, v_end_0, v_i_0, v_k_0, v_len) -> Com_1(eval_xnu_3(v__end_0, v_1, v_2, v_4, v_7, v_beg_0, v_end_0, v_i_0, v_k_0, v_len)) :|: TRUE
38.11/32.54	eval_xnu_3(v__end_0, v_1, v_2, v_4, v_7, v_beg_0, v_end_0, v_i_0, v_k_0, v_len) -> Com_1(eval_xnu_4(v__end_0, v_1, v_2, v_4, v_7, v_beg_0, v_end_0, v_i_0, v_k_0, v_len)) :|: TRUE
38.11/32.54	eval_xnu_4(v__end_0, v_1, v_2, v_4, v_7, v_beg_0, v_end_0, v_i_0, v_k_0, v_len) -> Com_1(eval_xnu_5(v__end_0, v_1, v_2, v_4, v_7, v_beg_0, v_end_0, v_i_0, v_k_0, v_len)) :|: TRUE
38.11/32.54	eval_xnu_5(v__end_0, v_1, v_2, v_4, v_7, v_beg_0, v_end_0, v_i_0, v_k_0, v_len) -> Com_1(eval_xnu_6(v__end_0, v_1, v_2, v_4, v_7, v_beg_0, v_end_0, v_i_0, v_k_0, v_len)) :|: TRUE
38.11/32.54	eval_xnu_6(v__end_0, v_1, v_2, v_4, v_7, v_beg_0, v_end_0, v_i_0, v_k_0, v_len) -> Com_1(eval_xnu_7(v__end_0, v_1, v_2, v_4, v_7, v_beg_0, v_end_0, v_i_0, v_k_0, v_len)) :|: TRUE
38.11/32.54	eval_xnu_7(v__end_0, v_1, v_2, v_4, v_7, v_beg_0, v_end_0, v_i_0, v_k_0, v_len) -> Com_1(eval_xnu_8(v__end_0, v_1, v_2, v_4, v_7, v_beg_0, v_end_0, v_i_0, v_k_0, v_len)) :|: TRUE
38.11/32.54	eval_xnu_8(v__end_0, v_1, v_2, v_4, v_7, v_beg_0, v_end_0, v_i_0, v_k_0, v_len) -> Com_1(eval_xnu_bb1_in(v__end_0, v_1, v_2, v_4, v_7, 0, 0, 0, v_k_0, v_len)) :|: TRUE
38.11/32.54	eval_xnu_bb1_in(v__end_0, v_1, v_2, v_4, v_7, v_beg_0, v_end_0, v_i_0, v_k_0, v_len) -> Com_1(eval_xnu_bb2_in(v__end_0, v_1, v_2, v_4, v_7, v_beg_0, v_end_0, v_i_0, v_k_0, v_len)) :|: v_i_0 < v_len
38.11/32.54	eval_xnu_bb1_in(v__end_0, v_1, v_2, v_4, v_7, v_beg_0, v_end_0, v_i_0, v_k_0, v_len) -> Com_1(eval_xnu_bb5_in(v__end_0, v_1, v_2, v_4, v_7, v_beg_0, v_end_0, v_i_0, v_k_0, v_len)) :|: v_i_0 >= v_len
38.11/32.54	eval_xnu_bb2_in(v__end_0, v_1, v_2, v_4, v_7, v_beg_0, v_end_0, v_i_0, v_k_0, v_len) -> Com_1(eval_xnu_10(v__end_0, v_i_0 + 1, v_2, v_4, v_7, v_beg_0, v_end_0, v_i_0, v_k_0, v_len)) :|: TRUE
38.11/32.54	eval_xnu_10(v__end_0, v_1, v_2, v_4, v_7, v_beg_0, v_end_0, v_i_0, v_k_0, v_len) -> Com_1(eval_xnu_11(v__end_0, v_1, nondef_0, v_4, v_7, v_beg_0, v_end_0, v_i_0, v_k_0, v_len)) :|: TRUE
38.11/32.54	eval_xnu_11(v__end_0, v_1, v_2, v_4, v_7, v_beg_0, v_end_0, v_i_0, v_k_0, v_len) -> Com_1(eval_xnu_12(v_1, v_1, v_2, v_4, v_7, v_beg_0, v_end_0, v_i_0, v_k_0, v_len)) :|: v_2 > 0
38.11/32.54	eval_xnu_11(v__end_0, v_1, v_2, v_4, v_7, v_beg_0, v_end_0, v_i_0, v_k_0, v_len) -> Com_1(eval_xnu_12(v_end_0, v_1, v_2, v_4, v_7, v_beg_0, v_end_0, v_i_0, v_k_0, v_len)) :|: v_2 <= 0
38.11/32.54	eval_xnu_12(v__end_0, v_1, v_2, v_4, v_7, v_beg_0, v_end_0, v_i_0, v_k_0, v_len) -> Com_1(eval_xnu_13(v__end_0, v_1, v_2, nondef_1, v_7, v_beg_0, v_end_0, v_i_0, v_k_0, v_len)) :|: TRUE
38.11/32.54	eval_xnu_13(v__end_0, v_1, v_2, v_4, v_7, v_beg_0, v_end_0, v_i_0, v_k_0, v_len) -> Com_1(eval_xnu_bb3_in(v__end_0, v_1, v_2, v_4, v_7, v_beg_0, v_end_0, v_i_0, v_beg_0, v_len)) :|: v_4 > 0
38.11/32.54	eval_xnu_13(v__end_0, v_1, v_2, v_4, v_7, v_beg_0, v_end_0, v_i_0, v_k_0, v_len) -> Com_1(eval_xnu_bb1_in(v__end_0, v_1, v_2, v_4, v_7, v_beg_0, v__end_0, v_1, v_k_0, v_len)) :|: v_4 <= 0
38.11/32.54	eval_xnu_bb3_in(v__end_0, v_1, v_2, v_4, v_7, v_beg_0, v_end_0, v_i_0, v_k_0, v_len) -> Com_1(eval_xnu_bb4_in(v__end_0, v_1, v_2, v_4, v_7, v_beg_0, v_end_0, v_i_0, v_k_0, v_len)) :|: v_k_0 < v__end_0
38.11/32.54	eval_xnu_bb3_in(v__end_0, v_1, v_2, v_4, v_7, v_beg_0, v_end_0, v_i_0, v_k_0, v_len) -> Com_1(eval_xnu_bb1_in(v__end_0, v_1, v_2, v_4, v_7, v_1, v_1, v_1, v_k_0, v_len)) :|: v_k_0 >= v__end_0
38.11/32.54	eval_xnu_bb4_in(v__end_0, v_1, v_2, v_4, v_7, v_beg_0, v_end_0, v_i_0, v_k_0, v_len) -> Com_1(eval_xnu_15(v__end_0, v_1, v_2, v_4, v_k_0 + 1, v_beg_0, v_end_0, v_i_0, v_k_0, v_len)) :|: TRUE
38.11/32.54	eval_xnu_15(v__end_0, v_1, v_2, v_4, v_7, v_beg_0, v_end_0, v_i_0, v_k_0, v_len) -> Com_1(eval_xnu_16(v__end_0, v_1, v_2, v_4, v_7, v_beg_0, v_end_0, v_i_0, v_k_0, v_len)) :|: TRUE
38.11/32.54	eval_xnu_16(v__end_0, v_1, v_2, v_4, v_7, v_beg_0, v_end_0, v_i_0, v_k_0, v_len) -> Com_1(eval_xnu_bb3_in(v__end_0, v_1, v_2, v_4, v_7, v_beg_0, v_end_0, v_i_0, v_7, v_len)) :|: TRUE
38.11/32.54	eval_xnu_bb5_in(v__end_0, v_1, v_2, v_4, v_7, v_beg_0, v_end_0, v_i_0, v_k_0, v_len) -> Com_1(eval_xnu_stop(v__end_0, v_1, v_2, v_4, v_7, v_beg_0, v_end_0, v_i_0, v_k_0, v_len)) :|: TRUE
38.11/32.54	
38.11/32.54	The start-symbols are:[eval_xnu_start_10]
38.11/32.54	
38.11/32.54	
38.11/32.54	----------------------------------------
38.11/32.54	
38.11/32.54	(1) Loat Proof (FINISHED)
38.11/32.54	
38.11/32.54	
38.11/32.54	### Pre-processing the ITS problem ###
38.11/32.54	
38.11/32.54	
38.11/32.54	
38.11/32.54	Initial linear ITS problem
38.11/32.54	
38.11/32.54	   Start location: evalxnustart
38.11/32.54	
38.11/32.54	      0: evalxnustart -> evalxnubb0in : [], cost: 1
38.11/32.54	
38.11/32.54	      1: evalxnubb0in -> evalxnu0 : [], cost: 1
38.11/32.54	
38.11/32.54	      2: evalxnu0 -> evalxnu1 : [], cost: 1
38.11/32.54	
38.11/32.54	      3: evalxnu1 -> evalxnu2 : [], cost: 1
38.11/32.54	
38.11/32.54	      4: evalxnu2 -> evalxnu3 : [], cost: 1
38.11/32.54	
38.11/32.54	      5: evalxnu3 -> evalxnu4 : [], cost: 1
38.11/32.54	
38.11/32.54	      6: evalxnu4 -> evalxnu5 : [], cost: 1
38.11/32.54	
38.11/32.54	      7: evalxnu5 -> evalxnu6 : [], cost: 1
38.11/32.54	
38.11/32.54	      8: evalxnu6 -> evalxnu7 : [], cost: 1
38.11/32.54	
38.11/32.54	      9: evalxnu7 -> evalxnu8 : [], cost: 1
38.11/32.54	
38.11/32.54	     10: evalxnu8 -> evalxnubb1in : A'=0, B'=0, C'=0, [], cost: 1
38.11/32.54	
38.11/32.54	     11: evalxnubb1in -> evalxnubb2in : [ D>=1+C ], cost: 1
38.11/32.54	
38.11/32.54	     12: evalxnubb1in -> evalxnubb5in : [ C>=D ], cost: 1
38.11/32.54	
38.11/32.54	     13: evalxnubb2in -> evalxnu10 : E'=1+C, [], cost: 1
38.11/32.54	
38.11/32.54	     14: evalxnu10 -> evalxnu11 : F'=free, [], cost: 1
38.11/32.54	
38.11/32.54	     15: evalxnu11 -> evalxnu12 : G'=E, [ F>=1 ], cost: 1
38.11/32.54	
38.11/32.54	     16: evalxnu11 -> evalxnu12 : G'=B, [ 0>=F ], cost: 1
38.11/32.54	
38.11/32.54	     17: evalxnu12 -> evalxnu13 : H'=free_1, [], cost: 1
38.11/32.54	
38.11/32.54	     18: evalxnu13 -> evalxnubb3in : Q'=A, [ H>=1 ], cost: 1
38.11/32.54	
38.11/32.54	     19: evalxnu13 -> evalxnubb1in : B'=G, C'=E, [ 0>=H ], cost: 1
38.11/32.54	
38.11/32.54	     20: evalxnubb3in -> evalxnubb4in : [ G>=1+Q ], cost: 1
38.11/32.54	
38.11/32.54	     21: evalxnubb3in -> evalxnubb1in : A'=E, B'=E, C'=E, [ Q>=G ], cost: 1
38.11/32.54	
38.11/32.54	     22: evalxnubb4in -> evalxnu15 : J'=1+Q, [], cost: 1
38.11/32.54	
38.11/32.54	     23: evalxnu15 -> evalxnu16 : [], cost: 1
38.11/32.54	
38.11/32.54	     24: evalxnu16 -> evalxnubb3in : Q'=J, [], cost: 1
38.11/32.54	
38.11/32.54	     25: evalxnubb5in -> evalxnustop : [], cost: 1
38.11/32.54	
38.11/32.54	
38.11/32.54	
38.11/32.54	Removed unreachable and leaf rules:
38.11/32.54	
38.11/32.54	   Start location: evalxnustart
38.11/32.54	
38.11/32.54	      0: evalxnustart -> evalxnubb0in : [], cost: 1
38.11/32.54	
38.11/32.54	      1: evalxnubb0in -> evalxnu0 : [], cost: 1
38.11/32.54	
38.11/32.54	      2: evalxnu0 -> evalxnu1 : [], cost: 1
38.11/32.54	
38.11/32.54	      3: evalxnu1 -> evalxnu2 : [], cost: 1
38.11/32.54	
38.11/32.54	      4: evalxnu2 -> evalxnu3 : [], cost: 1
38.11/32.54	
38.11/32.54	      5: evalxnu3 -> evalxnu4 : [], cost: 1
38.11/32.54	
38.11/32.54	      6: evalxnu4 -> evalxnu5 : [], cost: 1
38.11/32.54	
38.11/32.54	      7: evalxnu5 -> evalxnu6 : [], cost: 1
38.11/32.54	
38.11/32.54	      8: evalxnu6 -> evalxnu7 : [], cost: 1
38.11/32.54	
38.11/32.54	      9: evalxnu7 -> evalxnu8 : [], cost: 1
38.11/32.54	
38.11/32.54	     10: evalxnu8 -> evalxnubb1in : A'=0, B'=0, C'=0, [], cost: 1
38.11/32.54	
38.11/32.54	     11: evalxnubb1in -> evalxnubb2in : [ D>=1+C ], cost: 1
38.11/32.54	
38.11/32.54	     13: evalxnubb2in -> evalxnu10 : E'=1+C, [], cost: 1
38.11/32.54	
38.11/32.54	     14: evalxnu10 -> evalxnu11 : F'=free, [], cost: 1
38.11/32.54	
38.11/32.54	     15: evalxnu11 -> evalxnu12 : G'=E, [ F>=1 ], cost: 1
38.11/32.54	
38.11/32.54	     16: evalxnu11 -> evalxnu12 : G'=B, [ 0>=F ], cost: 1
38.11/32.54	
38.11/32.54	     17: evalxnu12 -> evalxnu13 : H'=free_1, [], cost: 1
38.11/32.54	
38.11/32.54	     18: evalxnu13 -> evalxnubb3in : Q'=A, [ H>=1 ], cost: 1
38.11/32.54	
38.11/32.54	     19: evalxnu13 -> evalxnubb1in : B'=G, C'=E, [ 0>=H ], cost: 1
38.11/32.54	
38.11/32.54	     20: evalxnubb3in -> evalxnubb4in : [ G>=1+Q ], cost: 1
38.11/32.54	
38.11/32.54	     21: evalxnubb3in -> evalxnubb1in : A'=E, B'=E, C'=E, [ Q>=G ], cost: 1
38.11/32.54	
38.11/32.54	     22: evalxnubb4in -> evalxnu15 : J'=1+Q, [], cost: 1
38.11/32.54	
38.11/32.54	     23: evalxnu15 -> evalxnu16 : [], cost: 1
38.11/32.54	
38.11/32.54	     24: evalxnu16 -> evalxnubb3in : Q'=J, [], cost: 1
38.11/32.54	
38.11/32.54	
38.11/32.54	
38.11/32.54	### Simplification by acceleration and chaining ###
38.11/32.54	
38.11/32.54	
38.11/32.54	
38.11/32.54	Eliminated locations (on linear paths):
38.11/32.54	
38.11/32.54	   Start location: evalxnustart
38.11/32.54	
38.11/32.54	     35: evalxnustart -> evalxnubb1in : A'=0, B'=0, C'=0, [], cost: 11
38.11/32.54	
38.11/32.54	     37: evalxnubb1in -> evalxnu11 : E'=1+C, F'=free, [ D>=1+C ], cost: 3
38.11/32.54	
38.11/32.54	     15: evalxnu11 -> evalxnu12 : G'=E, [ F>=1 ], cost: 1
38.11/32.54	
38.11/32.54	     16: evalxnu11 -> evalxnu12 : G'=B, [ 0>=F ], cost: 1
38.11/32.54	
38.11/32.54	     17: evalxnu12 -> evalxnu13 : H'=free_1, [], cost: 1
38.11/32.54	
38.11/32.54	     18: evalxnu13 -> evalxnubb3in : Q'=A, [ H>=1 ], cost: 1
38.11/32.54	
38.11/32.54	     19: evalxnu13 -> evalxnubb1in : B'=G, C'=E, [ 0>=H ], cost: 1
38.11/32.54	
38.11/32.54	     21: evalxnubb3in -> evalxnubb1in : A'=E, B'=E, C'=E, [ Q>=G ], cost: 1
38.11/32.54	
38.11/32.54	     40: evalxnubb3in -> evalxnubb3in : Q'=1+Q, J'=1+Q, [ G>=1+Q ], cost: 4
38.11/32.54	
38.11/32.54	
38.11/32.54	
38.11/32.54	Accelerating simple loops of location 17.
38.11/32.54	
38.11/32.54	   Accelerating the following rules:
38.11/32.54	
38.11/32.54	     40: evalxnubb3in -> evalxnubb3in : Q'=1+Q, J'=1+Q, [ G>=1+Q ], cost: 4
38.11/32.54	
38.11/32.54	
38.11/32.54	
38.11/32.54	   Accelerated rule 40 with metering function -Q+G, yielding the new rule 41.
38.11/32.54	
38.11/32.54	   Removing the simple loops: 40.
38.11/32.54	
38.11/32.54	
38.11/32.54	
38.11/32.54	Accelerated all simple loops using metering functions (where possible):
38.11/32.54	
38.11/32.54	   Start location: evalxnustart
38.11/32.54	
38.11/32.54	     35: evalxnustart -> evalxnubb1in : A'=0, B'=0, C'=0, [], cost: 11
38.11/32.54	
38.11/32.54	     37: evalxnubb1in -> evalxnu11 : E'=1+C, F'=free, [ D>=1+C ], cost: 3
38.11/32.54	
38.11/32.54	     15: evalxnu11 -> evalxnu12 : G'=E, [ F>=1 ], cost: 1
38.11/32.54	
38.11/32.54	     16: evalxnu11 -> evalxnu12 : G'=B, [ 0>=F ], cost: 1
38.11/32.54	
38.11/32.54	     17: evalxnu12 -> evalxnu13 : H'=free_1, [], cost: 1
38.11/32.54	
38.11/32.54	     18: evalxnu13 -> evalxnubb3in : Q'=A, [ H>=1 ], cost: 1
38.11/32.54	
38.11/32.54	     19: evalxnu13 -> evalxnubb1in : B'=G, C'=E, [ 0>=H ], cost: 1
38.11/32.54	
38.11/32.54	     21: evalxnubb3in -> evalxnubb1in : A'=E, B'=E, C'=E, [ Q>=G ], cost: 1
38.11/32.54	
38.11/32.54	     41: evalxnubb3in -> evalxnubb3in : Q'=G, J'=G, [ G>=1+Q ], cost: -4*Q+4*G
38.11/32.54	
38.11/32.54	
38.11/32.54	
38.11/32.54	Chained accelerated rules (with incoming rules):
38.11/32.54	
38.11/32.54	   Start location: evalxnustart
38.11/32.54	
38.11/32.54	     35: evalxnustart -> evalxnubb1in : A'=0, B'=0, C'=0, [], cost: 11
38.11/32.54	
38.11/32.54	     37: evalxnubb1in -> evalxnu11 : E'=1+C, F'=free, [ D>=1+C ], cost: 3
38.11/32.54	
38.11/32.54	     15: evalxnu11 -> evalxnu12 : G'=E, [ F>=1 ], cost: 1
38.11/32.54	
38.11/32.54	     16: evalxnu11 -> evalxnu12 : G'=B, [ 0>=F ], cost: 1
38.11/32.54	
38.11/32.54	     17: evalxnu12 -> evalxnu13 : H'=free_1, [], cost: 1
38.11/32.54	
38.11/32.54	     18: evalxnu13 -> evalxnubb3in : Q'=A, [ H>=1 ], cost: 1
38.11/32.54	
38.11/32.54	     19: evalxnu13 -> evalxnubb1in : B'=G, C'=E, [ 0>=H ], cost: 1
38.11/32.54	
38.11/32.54	     42: evalxnu13 -> evalxnubb3in : Q'=G, J'=G, [ H>=1 && G>=1+A ], cost: 1+4*G-4*A
38.11/32.54	
38.11/32.54	     21: evalxnubb3in -> evalxnubb1in : A'=E, B'=E, C'=E, [ Q>=G ], cost: 1
38.11/32.54	
38.11/32.54	
38.11/32.54	
38.11/32.54	Eliminated locations (on tree-shaped paths):
38.11/32.54	
38.11/32.54	   Start location: evalxnustart
38.11/32.54	
38.11/32.54	     35: evalxnustart -> evalxnubb1in : A'=0, B'=0, C'=0, [], cost: 11
38.11/32.54	
38.11/32.54	     43: evalxnubb1in -> evalxnu12 : E'=1+C, F'=free, G'=1+C, [ D>=1+C && free>=1 ], cost: 4
38.11/32.54	
38.11/32.54	     44: evalxnubb1in -> evalxnu12 : E'=1+C, F'=free, G'=B, [ D>=1+C && 0>=free ], cost: 4
38.11/32.54	
38.11/32.54	     45: evalxnu12 -> evalxnubb3in : H'=free_1, Q'=A, [ free_1>=1 ], cost: 2
38.11/32.54	
38.11/32.54	     46: evalxnu12 -> evalxnubb1in : B'=G, C'=E, H'=free_1, [ 0>=free_1 ], cost: 2
38.11/32.54	
38.11/32.54	     47: evalxnu12 -> evalxnubb3in : H'=free_1, Q'=G, J'=G, [ free_1>=1 && G>=1+A ], cost: 2+4*G-4*A
38.11/32.54	
38.11/32.54	     21: evalxnubb3in -> evalxnubb1in : A'=E, B'=E, C'=E, [ Q>=G ], cost: 1
38.11/32.54	
38.11/32.54	
38.11/32.54	
38.11/32.54	Eliminated locations (on tree-shaped paths):
38.11/32.54	
38.11/32.54	   Start location: evalxnustart
38.11/32.54	
38.11/32.54	     35: evalxnustart -> evalxnubb1in : A'=0, B'=0, C'=0, [], cost: 11
38.11/32.54	
38.11/32.54	     48: evalxnubb1in -> evalxnubb3in : E'=1+C, F'=free, G'=1+C, H'=free_1, Q'=A, [ D>=1+C && free>=1 && free_1>=1 ], cost: 6
38.11/32.54	
38.11/32.54	     49: evalxnubb1in -> evalxnubb1in : B'=1+C, C'=1+C, E'=1+C, F'=free, G'=1+C, H'=free_1, [ D>=1+C && free>=1 && 0>=free_1 ], cost: 6
38.11/32.54	
38.11/32.54	     50: evalxnubb1in -> evalxnubb3in : E'=1+C, F'=free, G'=1+C, H'=free_1, Q'=1+C, J'=1+C, [ D>=1+C && free>=1 && free_1>=1 && 1+C>=1+A ], cost: 10+4*C-4*A
38.11/32.54	
38.11/32.54	     51: evalxnubb1in -> evalxnubb3in : E'=1+C, F'=free, G'=B, H'=free_1, Q'=A, [ D>=1+C && 0>=free && free_1>=1 ], cost: 6
38.11/32.54	
38.11/32.54	     52: evalxnubb1in -> evalxnubb1in : B'=B, C'=1+C, E'=1+C, F'=free, G'=B, H'=free_1, [ D>=1+C && 0>=free && 0>=free_1 ], cost: 6
38.11/32.54	
38.11/32.54	     53: evalxnubb1in -> evalxnubb3in : E'=1+C, F'=free, G'=B, H'=free_1, Q'=B, J'=B, [ D>=1+C && 0>=free && free_1>=1 && B>=1+A ], cost: 6-4*A+4*B
38.11/32.54	
38.11/32.54	     21: evalxnubb3in -> evalxnubb1in : A'=E, B'=E, C'=E, [ Q>=G ], cost: 1
38.11/32.54	
38.11/32.54	
38.11/32.54	
38.11/32.54	Accelerating simple loops of location 11.
38.11/32.54	
38.11/32.54	   Simplified some of the simple loops (and removed duplicate rules).
38.11/32.54	
38.11/32.54	   Accelerating the following rules:
38.11/32.54	
38.11/32.54	     49: evalxnubb1in -> evalxnubb1in : B'=1+C, C'=1+C, E'=1+C, F'=free, G'=1+C, H'=free_1, [ D>=1+C && free>=1 && 0>=free_1 ], cost: 6
38.11/32.54	
38.11/32.54	     52: evalxnubb1in -> evalxnubb1in : C'=1+C, E'=1+C, F'=free, G'=B, H'=free_1, [ D>=1+C && 0>=free && 0>=free_1 ], cost: 6
38.11/32.54	
38.11/32.54	
38.11/32.54	
38.11/32.54	   Accelerated rule 49 with metering function -C+D, yielding the new rule 54.
38.11/32.54	
38.11/32.54	   Accelerated rule 52 with metering function -C+D, yielding the new rule 55.
38.11/32.54	
38.11/32.54	   Removing the simple loops: 49 52.
38.11/32.54	
38.11/32.54	
38.11/32.54	
38.11/32.54	Accelerated all simple loops using metering functions (where possible):
38.11/32.54	
38.11/32.54	   Start location: evalxnustart
38.11/32.54	
38.11/32.54	     35: evalxnustart -> evalxnubb1in : A'=0, B'=0, C'=0, [], cost: 11
38.11/32.54	
38.11/32.54	     48: evalxnubb1in -> evalxnubb3in : E'=1+C, F'=free, G'=1+C, H'=free_1, Q'=A, [ D>=1+C && free>=1 && free_1>=1 ], cost: 6
38.11/32.54	
38.11/32.54	     50: evalxnubb1in -> evalxnubb3in : E'=1+C, F'=free, G'=1+C, H'=free_1, Q'=1+C, J'=1+C, [ D>=1+C && free>=1 && free_1>=1 && 1+C>=1+A ], cost: 10+4*C-4*A
38.11/32.54	
38.11/32.54	     51: evalxnubb1in -> evalxnubb3in : E'=1+C, F'=free, G'=B, H'=free_1, Q'=A, [ D>=1+C && 0>=free && free_1>=1 ], cost: 6
38.11/32.54	
38.11/32.54	     53: evalxnubb1in -> evalxnubb3in : E'=1+C, F'=free, G'=B, H'=free_1, Q'=B, J'=B, [ D>=1+C && 0>=free && free_1>=1 && B>=1+A ], cost: 6-4*A+4*B
38.11/32.54	
38.11/32.54	     54: evalxnubb1in -> evalxnubb1in : B'=D, C'=D, E'=D, F'=free, G'=D, H'=free_1, [ D>=1+C && free>=1 && 0>=free_1 ], cost: -6*C+6*D
38.11/32.54	
38.11/32.54	     55: evalxnubb1in -> evalxnubb1in : C'=D, E'=D, F'=free, G'=B, H'=free_1, [ D>=1+C && 0>=free && 0>=free_1 ], cost: -6*C+6*D
38.11/32.54	
38.11/32.54	     21: evalxnubb3in -> evalxnubb1in : A'=E, B'=E, C'=E, [ Q>=G ], cost: 1
38.11/32.54	
38.11/32.54	
38.11/32.54	
38.11/32.54	Chained accelerated rules (with incoming rules):
38.11/32.54	
38.11/32.54	   Start location: evalxnustart
38.11/32.54	
38.11/32.54	     35: evalxnustart -> evalxnubb1in : A'=0, B'=0, C'=0, [], cost: 11
38.11/32.54	
38.11/32.54	     57: evalxnustart -> evalxnubb1in : A'=0, B'=D, C'=D, E'=D, F'=free, G'=D, H'=free_1, [ D>=1 && free>=1 && 0>=free_1 ], cost: 11+6*D
38.11/32.54	
38.11/32.54	     59: evalxnustart -> evalxnubb1in : A'=0, B'=0, C'=D, E'=D, F'=free, G'=0, H'=free_1, [ D>=1 && 0>=free && 0>=free_1 ], cost: 11+6*D
38.11/32.54	
38.11/32.54	     48: evalxnubb1in -> evalxnubb3in : E'=1+C, F'=free, G'=1+C, H'=free_1, Q'=A, [ D>=1+C && free>=1 && free_1>=1 ], cost: 6
38.11/32.54	
38.11/32.54	     50: evalxnubb1in -> evalxnubb3in : E'=1+C, F'=free, G'=1+C, H'=free_1, Q'=1+C, J'=1+C, [ D>=1+C && free>=1 && free_1>=1 && 1+C>=1+A ], cost: 10+4*C-4*A
38.11/32.54	
38.11/32.54	     51: evalxnubb1in -> evalxnubb3in : E'=1+C, F'=free, G'=B, H'=free_1, Q'=A, [ D>=1+C && 0>=free && free_1>=1 ], cost: 6
38.11/32.54	
38.11/32.54	     53: evalxnubb1in -> evalxnubb3in : E'=1+C, F'=free, G'=B, H'=free_1, Q'=B, J'=B, [ D>=1+C && 0>=free && free_1>=1 && B>=1+A ], cost: 6-4*A+4*B
38.11/32.54	
38.11/32.54	     21: evalxnubb3in -> evalxnubb1in : A'=E, B'=E, C'=E, [ Q>=G ], cost: 1
38.11/32.54	
38.11/32.54	     56: evalxnubb3in -> evalxnubb1in : A'=E, B'=D, C'=D, E'=D, F'=free, G'=D, H'=free_1, [ Q>=G && D>=1+E && free>=1 && 0>=free_1 ], cost: 1+6*D-6*E
38.11/32.54	
38.11/32.54	     58: evalxnubb3in -> evalxnubb1in : A'=E, B'=E, C'=D, E'=D, F'=free, G'=E, H'=free_1, [ Q>=G && D>=1+E && 0>=free && 0>=free_1 ], cost: 1+6*D-6*E
38.11/32.54	
38.11/32.54	
38.11/32.54	
38.11/32.54	Eliminated locations (on tree-shaped paths):
38.11/32.54	
38.11/32.54	   Start location: evalxnustart
38.11/32.54	
38.11/32.54	     35: evalxnustart -> evalxnubb1in : A'=0, B'=0, C'=0, [], cost: 11
38.11/32.54	
38.11/32.54	     57: evalxnustart -> evalxnubb1in : A'=0, B'=D, C'=D, E'=D, F'=free, G'=D, H'=free_1, [ D>=1 && free>=1 && 0>=free_1 ], cost: 11+6*D
38.11/32.54	
38.11/32.54	     59: evalxnustart -> evalxnubb1in : A'=0, B'=0, C'=D, E'=D, F'=free, G'=0, H'=free_1, [ D>=1 && 0>=free && 0>=free_1 ], cost: 11+6*D
38.11/32.54	
38.11/32.54	     60: evalxnubb1in -> evalxnubb1in : A'=1+C, B'=1+C, C'=1+C, E'=1+C, F'=free, G'=1+C, H'=free_1, Q'=A, [ D>=1+C && free>=1 && free_1>=1 && A>=1+C ], cost: 7
38.11/32.54	
38.11/32.54	     61: evalxnubb1in -> evalxnubb1in : A'=1+C, B'=1+C, C'=1+C, E'=1+C, F'=free, G'=1+C, H'=free_1, Q'=1+C, J'=1+C, [ D>=1+C && free>=1 && free_1>=1 && 1+C>=1+A ], cost: 11+4*C-4*A
38.11/32.54	
38.11/32.54	     62: evalxnubb1in -> evalxnubb1in : A'=1+C, B'=1+C, C'=1+C, E'=1+C, F'=free, G'=B, H'=free_1, Q'=A, [ D>=1+C && 0>=free && free_1>=1 && A>=B ], cost: 7
38.11/32.54	
38.11/32.54	     63: evalxnubb1in -> evalxnubb1in : A'=1+C, B'=1+C, C'=1+C, E'=1+C, F'=free, G'=B, H'=free_1, Q'=B, J'=B, [ D>=1+C && 0>=free && free_1>=1 && B>=1+A ], cost: 7-4*A+4*B
38.11/32.54	
38.11/32.54	     64: evalxnubb1in -> [25] : [ D>=1+C && free>=1 && free_1>=1 && 1+C>=1+A ], cost: 10+4*C-4*A
38.11/32.54	
38.11/32.54	     65: evalxnubb1in -> [25] : [ D>=1+C && 0>=free && free_1>=1 && B>=1+A ], cost: 6-4*A+4*B
38.11/32.54	
38.11/32.54	
38.11/32.54	
38.11/32.54	Accelerating simple loops of location 11.
38.11/32.54	
38.11/32.54	   Accelerating the following rules:
38.11/32.54	
38.11/32.54	     60: evalxnubb1in -> evalxnubb1in : A'=1+C, B'=1+C, C'=1+C, E'=1+C, F'=free, G'=1+C, H'=free_1, Q'=A, [ D>=1+C && free>=1 && free_1>=1 && A>=1+C ], cost: 7
38.11/32.54	
38.11/32.54	     61: evalxnubb1in -> evalxnubb1in : A'=1+C, B'=1+C, C'=1+C, E'=1+C, F'=free, G'=1+C, H'=free_1, Q'=1+C, J'=1+C, [ D>=1+C && free>=1 && free_1>=1 && 1+C>=1+A ], cost: 11+4*C-4*A
38.11/32.54	
38.11/32.54	     62: evalxnubb1in -> evalxnubb1in : A'=1+C, B'=1+C, C'=1+C, E'=1+C, F'=free, G'=B, H'=free_1, Q'=A, [ D>=1+C && 0>=free && free_1>=1 && A>=B ], cost: 7
38.11/32.54	
38.11/32.54	     63: evalxnubb1in -> evalxnubb1in : A'=1+C, B'=1+C, C'=1+C, E'=1+C, F'=free, G'=B, H'=free_1, Q'=B, J'=B, [ D>=1+C && 0>=free && free_1>=1 && B>=1+A ], cost: 7-4*A+4*B
38.11/32.54	
38.11/32.54	
38.11/32.54	
38.11/32.54	   Found no metering function for rule 60.
38.11/32.54	
38.11/32.54	   Accelerated rule 61 with metering function -C+D, yielding the new rule 66.
38.11/32.54	
38.11/32.54	   Accelerated rule 62 with metering function -C+D, yielding the new rule 67.
38.11/32.54	
38.11/32.54	   Found no metering function for rule 63.
38.11/32.54	
38.11/32.54	   Removing the simple loops: 61 62.
38.11/32.54	
38.11/32.54	
38.11/32.54	
38.11/32.54	Accelerated all simple loops using metering functions (where possible):
38.11/32.54	
38.11/32.54	   Start location: evalxnustart
38.11/32.54	
38.11/32.54	     35: evalxnustart -> evalxnubb1in : A'=0, B'=0, C'=0, [], cost: 11
38.11/32.54	
38.11/32.54	     57: evalxnustart -> evalxnubb1in : A'=0, B'=D, C'=D, E'=D, F'=free, G'=D, H'=free_1, [ D>=1 && free>=1 && 0>=free_1 ], cost: 11+6*D
38.11/32.54	
38.11/32.54	     59: evalxnustart -> evalxnubb1in : A'=0, B'=0, C'=D, E'=D, F'=free, G'=0, H'=free_1, [ D>=1 && 0>=free && 0>=free_1 ], cost: 11+6*D
38.11/32.54	
38.11/32.54	     60: evalxnubb1in -> evalxnubb1in : A'=1+C, B'=1+C, C'=1+C, E'=1+C, F'=free, G'=1+C, H'=free_1, Q'=A, [ D>=1+C && free>=1 && free_1>=1 && A>=1+C ], cost: 7
38.11/32.54	
38.11/32.54	     63: evalxnubb1in -> evalxnubb1in : A'=1+C, B'=1+C, C'=1+C, E'=1+C, F'=free, G'=B, H'=free_1, Q'=B, J'=B, [ D>=1+C && 0>=free && free_1>=1 && B>=1+A ], cost: 7-4*A+4*B
38.11/32.54	
38.11/32.54	     64: evalxnubb1in -> [25] : [ D>=1+C && free>=1 && free_1>=1 && 1+C>=1+A ], cost: 10+4*C-4*A
38.11/32.54	
38.11/32.54	     65: evalxnubb1in -> [25] : [ D>=1+C && 0>=free && free_1>=1 && B>=1+A ], cost: 6-4*A+4*B
38.11/32.54	
38.11/32.54	     66: evalxnubb1in -> evalxnubb1in : A'=D, B'=D, C'=D, E'=D, F'=free, G'=D, H'=free_1, Q'=D, J'=D, [ D>=1+C && free>=1 && free_1>=1 && 1+C>=1+A ], cost: -11*C+11*D
38.11/32.54	
38.11/32.54	     67: evalxnubb1in -> evalxnubb1in : A'=D, B'=D, C'=D, E'=D, F'=free, G'=-1+D, H'=free_1, Q'=-1+D, [ D>=1+C && 0>=free && free_1>=1 && A>=B ], cost: -7*C+7*D
38.11/32.54	
38.11/32.54	
38.11/32.54	
38.11/32.54	Chained accelerated rules (with incoming rules):
38.11/32.54	
38.11/32.54	   Start location: evalxnustart
38.11/32.54	
38.11/32.54	     35: evalxnustart -> evalxnubb1in : A'=0, B'=0, C'=0, [], cost: 11
38.11/32.54	
38.11/32.54	     57: evalxnustart -> evalxnubb1in : A'=0, B'=D, C'=D, E'=D, F'=free, G'=D, H'=free_1, [ D>=1 && free>=1 && 0>=free_1 ], cost: 11+6*D
38.11/32.54	
38.11/32.54	     59: evalxnustart -> evalxnubb1in : A'=0, B'=0, C'=D, E'=D, F'=free, G'=0, H'=free_1, [ D>=1 && 0>=free && 0>=free_1 ], cost: 11+6*D
38.11/32.54	
38.11/32.54	     68: evalxnustart -> evalxnubb1in : A'=D, B'=D, C'=D, E'=D, F'=free, G'=D, H'=free_1, Q'=D, J'=D, [ D>=1 && free>=1 && free_1>=1 ], cost: 11+11*D
38.11/32.54	
38.11/32.54	     69: evalxnustart -> evalxnubb1in : A'=D, B'=D, C'=D, E'=D, F'=free, G'=-1+D, H'=free_1, Q'=-1+D, [ D>=1 && 0>=free && free_1>=1 ], cost: 11+7*D
38.11/32.54	
38.11/32.54	     64: evalxnubb1in -> [25] : [ D>=1+C && free>=1 && free_1>=1 && 1+C>=1+A ], cost: 10+4*C-4*A
38.11/32.54	
38.11/32.54	     65: evalxnubb1in -> [25] : [ D>=1+C && 0>=free && free_1>=1 && B>=1+A ], cost: 6-4*A+4*B
38.11/32.54	
38.11/32.54	
38.11/32.54	
38.11/32.54	Eliminated locations (on tree-shaped paths):
38.11/32.54	
38.11/32.54	   Start location: evalxnustart
38.11/32.54	
38.11/32.54	     70: evalxnustart -> [25] : A'=0, B'=0, C'=0, [ D>=1 && free>=1 && free_1>=1 ], cost: 21
38.11/32.54	
38.11/32.54	     71: evalxnustart -> [27] : [ D>=1 && free>=1 && 0>=free_1 ], cost: 11+6*D
38.11/32.54	
38.11/32.54	     72: evalxnustart -> [27] : [ D>=1 && 0>=free && 0>=free_1 ], cost: 11+6*D
38.11/32.54	
38.11/32.54	     73: evalxnustart -> [27] : [ D>=1 && free>=1 && free_1>=1 ], cost: 11+11*D
38.11/32.54	
38.11/32.54	     74: evalxnustart -> [27] : [ D>=1 && 0>=free && free_1>=1 ], cost: 11+7*D
38.11/32.54	
38.11/32.54	
38.11/32.54	
38.11/32.54	Applied pruning (of leafs and parallel rules):
38.11/32.54	
38.11/32.54	   Start location: evalxnustart
38.11/32.54	
38.11/32.54	     71: evalxnustart -> [27] : [ D>=1 && free>=1 && 0>=free_1 ], cost: 11+6*D
38.11/32.54	
38.11/32.54	     72: evalxnustart -> [27] : [ D>=1 && 0>=free && 0>=free_1 ], cost: 11+6*D
38.11/32.54	
38.11/32.54	     73: evalxnustart -> [27] : [ D>=1 && free>=1 && free_1>=1 ], cost: 11+11*D
38.11/32.54	
38.11/32.54	     74: evalxnustart -> [27] : [ D>=1 && 0>=free && free_1>=1 ], cost: 11+7*D
38.11/32.54	
38.11/32.54	
38.11/32.54	
38.11/32.54	### Computing asymptotic complexity ###
38.11/32.54	
38.11/32.54	
38.11/32.54	
38.11/32.54	Fully simplified ITS problem
38.11/32.54	
38.11/32.54	   Start location: evalxnustart
38.11/32.54	
38.11/32.54	     71: evalxnustart -> [27] : [ D>=1 && free>=1 && 0>=free_1 ], cost: 11+6*D
38.11/32.54	
38.11/32.54	     72: evalxnustart -> [27] : [ D>=1 && 0>=free && 0>=free_1 ], cost: 11+6*D
38.11/32.54	
38.11/32.54	     73: evalxnustart -> [27] : [ D>=1 && free>=1 && free_1>=1 ], cost: 11+11*D
38.11/32.54	
38.11/32.54	     74: evalxnustart -> [27] : [ D>=1 && 0>=free && free_1>=1 ], cost: 11+7*D
38.11/32.54	
38.11/32.54	
38.11/32.54	
38.11/32.54	Computing asymptotic complexity for rule 71
38.11/32.54	
38.11/32.54	   Solved the limit problem by the following transformations:
38.11/32.54	
38.11/32.54	      Created initial limit problem:
38.11/32.54	
38.11/32.54	      free (+/+!), 11+6*D (+), D (+/+!), 1-free_1 (+/+!) [not solved]
38.11/32.54	
38.11/32.54	
38.11/32.54	
38.11/32.54	      removing all constraints (solved by SMT)
38.11/32.54	
38.11/32.54	      resulting limit problem: [solved]
38.11/32.54	
38.11/32.54	
38.11/32.54	
38.11/32.54	      applying transformation rule (C) using substitution {free==n,free_1==-n,D==n}
38.11/32.54	
38.11/32.54	      resulting limit problem:
38.11/32.54	
38.11/32.54	      [solved]
38.11/32.54	
38.11/32.54	
38.11/32.54	
38.11/32.54	   Solution:
38.11/32.54	
38.11/32.54	      free / n
38.11/32.54	
38.11/32.54	      free_1 / -n
38.11/32.54	
38.11/32.54	      D / n
38.11/32.54	
38.11/32.54	   Resulting cost 11+6*n has complexity: Poly(n^1)
38.11/32.54	
38.11/32.54	
38.11/32.54	
38.11/32.54	Found new complexity Poly(n^1).
38.11/32.54	
38.11/32.54	
38.11/32.54	
38.11/32.54	Obtained the following overall complexity (w.r.t. the length of the input n):
38.11/32.54	
38.11/32.54	   Complexity:  Poly(n^1)
38.11/32.54	
38.11/32.54	   Cpx degree:  1
38.11/32.54	
38.11/32.54	   Solved cost: 11+6*n
38.11/32.54	
38.11/32.54	   Rule cost:   11+6*D
38.11/32.54	
38.11/32.54	   Rule guard:  [ D>=1 && free>=1 && 0>=free_1 ]
38.11/32.54	
38.11/32.54	
38.11/32.54	
38.11/32.54	WORST_CASE(Omega(n^1),?)
38.11/32.54	
38.11/32.54	
38.11/32.54	----------------------------------------
38.11/32.54	
38.11/32.54	(2)
38.11/32.54	BOUNDS(n^1, INF)
38.25/32.72	EOF