27.38/20.77	WORST_CASE(Omega(n^1), O(n^2))
27.38/20.78	proof of /export/starexec/sandbox2/benchmark/theBenchmark.koat
27.38/20.78	# AProVE Commit ID: 48fb2092695e11cc9f56e44b17a92a5f88ffb256 marcel 20180622 unpublished dirty
27.38/20.78	
27.38/20.78	
27.38/20.78	The runtime complexity of the given CpxIntTrs could be proven to be BOUNDS(n^1, max(23, 15 + 4 * Arg_0) + max(4, 2 * Arg_0) * nat(Arg_0) + nat(Arg_0) + nat(Arg_0 * max(4, 2 * Arg_0) + min(-2 * Arg_0, -4)) * nat(Arg_0) + nat(Arg_0 * max(4, 2 * Arg_0) + min(-2 * Arg_0, -4)) + max(3, 2 + Arg_0) + max(10, -10 + 10 * Arg_0) + max(9, -9 + 9 * Arg_0) + max(5, -5 + 5 * Arg_0) + nat(-2 + 2 * Arg_0) + max(-14 + 14 * Arg_0, 14) + max(8, -8 + 8 * Arg_0)).
27.38/20.78	
27.38/20.78	(0) CpxIntTrs
27.38/20.78	(1) Loat Proof [FINISHED, 2116 ms]
27.38/20.78	(2) BOUNDS(n^1, INF)
27.38/20.78	
27.38/20.78	
27.38/20.78	----------------------------------------
27.38/20.78	
27.38/20.78	(0)
27.38/20.78	Obligation:
27.38/20.78	Complexity Int TRS consisting of the following rules:
27.38/20.78	eval_perfect1_start(v__y3_0, v_1, v_6, v_7, v_x, v_y1_0, v_y2_1, v_y3_0) -> Com_1(eval_perfect1_bb0_in(v__y3_0, v_1, v_6, v_7, v_x, v_y1_0, v_y2_1, v_y3_0)) :|: TRUE
27.38/20.78	eval_perfect1_bb0_in(v__y3_0, v_1, v_6, v_7, v_x, v_y1_0, v_y2_1, v_y3_0) -> Com_1(eval_perfect1_0(v__y3_0, v_1, v_6, v_7, v_x, v_y1_0, v_y2_1, v_y3_0)) :|: TRUE
27.38/20.78	eval_perfect1_0(v__y3_0, v_1, v_6, v_7, v_x, v_y1_0, v_y2_1, v_y3_0) -> Com_1(eval_perfect1_1(v__y3_0, v_1, v_6, v_7, v_x, v_y1_0, v_y2_1, v_y3_0)) :|: TRUE
27.38/20.78	eval_perfect1_1(v__y3_0, v_1, v_6, v_7, v_x, v_y1_0, v_y2_1, v_y3_0) -> Com_1(eval_perfect1_bb7_in(v__y3_0, v_1, v_6, v_7, v_x, v_y1_0, v_y2_1, v_y3_0)) :|: v_x <= 1
27.38/20.78	eval_perfect1_1(v__y3_0, v_1, v_6, v_7, v_x, v_y1_0, v_y2_1, v_y3_0) -> Com_1(eval_perfect1_bb1_in(v__y3_0, v_1, v_6, v_7, v_x, v_y1_0, v_y2_1, v_y3_0)) :|: v_x > 1
27.38/20.78	eval_perfect1_bb1_in(v__y3_0, v_1, v_6, v_7, v_x, v_y1_0, v_y2_1, v_y3_0) -> Com_1(eval_perfect1_2(v__y3_0, v_1, v_6, v_7, v_x, v_y1_0, v_y2_1, v_y3_0)) :|: TRUE
27.38/20.78	eval_perfect1_2(v__y3_0, v_1, v_6, v_7, v_x, v_y1_0, v_y2_1, v_y3_0) -> Com_1(eval_perfect1_3(v__y3_0, v_1, v_6, v_7, v_x, v_y1_0, v_y2_1, v_y3_0)) :|: TRUE
27.38/20.78	eval_perfect1_3(v__y3_0, v_1, v_6, v_7, v_x, v_y1_0, v_y2_1, v_y3_0) -> Com_1(eval_perfect1_4(v__y3_0, v_1, v_6, v_7, v_x, v_y1_0, v_y2_1, v_y3_0)) :|: TRUE
27.38/20.78	eval_perfect1_4(v__y3_0, v_1, v_6, v_7, v_x, v_y1_0, v_y2_1, v_y3_0) -> Com_1(eval_perfect1_5(v__y3_0, v_1, v_6, v_7, v_x, v_y1_0, v_y2_1, v_y3_0)) :|: TRUE
27.38/20.78	eval_perfect1_5(v__y3_0, v_1, v_6, v_7, v_x, v_y1_0, v_y2_1, v_y3_0) -> Com_1(eval_perfect1_6(v__y3_0, v_x - 1, v_6, v_7, v_x, v_y1_0, v_y2_1, v_y3_0)) :|: TRUE
27.38/20.78	eval_perfect1_6(v__y3_0, v_1, v_6, v_7, v_x, v_y1_0, v_y2_1, v_y3_0) -> Com_1(eval_perfect1_7(v__y3_0, v_1, v_6, v_7, v_x, v_y1_0, v_y2_1, v_y3_0)) :|: TRUE
27.38/20.78	eval_perfect1_7(v__y3_0, v_1, v_6, v_7, v_x, v_y1_0, v_y2_1, v_y3_0) -> Com_1(eval_perfect1_8(v__y3_0, v_1, v_6, v_7, v_x, v_y1_0, v_y2_1, v_y3_0)) :|: TRUE
27.38/20.78	eval_perfect1_8(v__y3_0, v_1, v_6, v_7, v_x, v_y1_0, v_y2_1, v_y3_0) -> Com_1(eval_perfect1_bb2_in(v__y3_0, v_1, v_6, v_7, v_x, v_1, v_y2_1, v_x)) :|: TRUE
27.38/20.78	eval_perfect1_bb2_in(v__y3_0, v_1, v_6, v_7, v_x, v_y1_0, v_y2_1, v_y3_0) -> Com_1(eval_perfect1_bb3_in(v__y3_0, v_1, v_6, v_7, v_x, v_y1_0, v_x, v_y3_0)) :|: v_y1_0 > 0
27.38/20.78	eval_perfect1_bb2_in(v__y3_0, v_1, v_6, v_7, v_x, v_y1_0, v_y2_1, v_y3_0) -> Com_1(eval_perfect1_bb6_in(v__y3_0, v_1, v_6, v_7, v_x, v_y1_0, v_y2_1, v_y3_0)) :|: v_y1_0 <= 0
27.38/20.78	eval_perfect1_bb3_in(v__y3_0, v_1, v_6, v_7, v_x, v_y1_0, v_y2_1, v_y3_0) -> Com_1(eval_perfect1_bb4_in(v__y3_0, v_1, v_6, v_7, v_x, v_y1_0, v_y2_1, v_y3_0)) :|: v_y2_1 >= v_y1_0
27.38/20.78	eval_perfect1_bb3_in(v__y3_0, v_1, v_6, v_7, v_x, v_y1_0, v_y2_1, v_y3_0) -> Com_1(eval_perfect1_bb5_in(v__y3_0, v_1, v_6, v_7, v_x, v_y1_0, v_y2_1, v_y3_0)) :|: v_y2_1 < v_y1_0
27.38/20.78	eval_perfect1_bb4_in(v__y3_0, v_1, v_6, v_7, v_x, v_y1_0, v_y2_1, v_y3_0) -> Com_1(eval_perfect1_bb3_in(v__y3_0, v_1, v_6, v_7, v_x, v_y1_0, v_y2_1 - v_y1_0, v_y3_0)) :|: TRUE
27.38/20.78	eval_perfect1_bb5_in(v__y3_0, v_1, v_6, v_7, v_x, v_y1_0, v_y2_1, v_y3_0) -> Com_1(eval_perfect1_12(v__y3_0, v_1, v_y3_0 - v_y1_0, v_7, v_x, v_y1_0, v_y2_1, v_y3_0)) :|: TRUE
27.38/20.78	eval_perfect1_12(v__y3_0, v_1, v_6, v_7, v_x, v_y1_0, v_y2_1, v_y3_0) -> Com_1(eval_perfect1_13(v__y3_0, v_1, v_6, v_7, v_x, v_y1_0, v_y2_1, v_y3_0)) :|: TRUE
27.38/20.78	eval_perfect1_13(v__y3_0, v_1, v_6, v_7, v_x, v_y1_0, v_y2_1, v_y3_0) -> Com_1(eval_perfect1_14(v_6, v_1, v_6, v_7, v_x, v_y1_0, v_y2_1, v_y3_0)) :|: v_y2_1 >= 0 && v_y2_1 <= 0
27.38/20.78	eval_perfect1_13(v__y3_0, v_1, v_6, v_7, v_x, v_y1_0, v_y2_1, v_y3_0) -> Com_1(eval_perfect1_14(v_y3_0, v_1, v_6, v_7, v_x, v_y1_0, v_y2_1, v_y3_0)) :|: v_y2_1 < 0
27.38/20.78	eval_perfect1_13(v__y3_0, v_1, v_6, v_7, v_x, v_y1_0, v_y2_1, v_y3_0) -> Com_1(eval_perfect1_14(v_y3_0, v_1, v_6, v_7, v_x, v_y1_0, v_y2_1, v_y3_0)) :|: v_y2_1 > 0
27.38/20.78	eval_perfect1_14(v__y3_0, v_1, v_6, v_7, v_x, v_y1_0, v_y2_1, v_y3_0) -> Com_1(eval_perfect1_15(v__y3_0, v_1, v_6, v_7, v_x, v_y1_0, v_y2_1, v_y3_0)) :|: TRUE
27.38/20.78	eval_perfect1_15(v__y3_0, v_1, v_6, v_7, v_x, v_y1_0, v_y2_1, v_y3_0) -> Com_1(eval_perfect1_16(v__y3_0, v_1, v_6, v_y1_0 - 1, v_x, v_y1_0, v_y2_1, v_y3_0)) :|: TRUE
27.38/20.78	eval_perfect1_16(v__y3_0, v_1, v_6, v_7, v_x, v_y1_0, v_y2_1, v_y3_0) -> Com_1(eval_perfect1_17(v__y3_0, v_1, v_6, v_7, v_x, v_y1_0, v_y2_1, v_y3_0)) :|: TRUE
27.38/20.78	eval_perfect1_17(v__y3_0, v_1, v_6, v_7, v_x, v_y1_0, v_y2_1, v_y3_0) -> Com_1(eval_perfect1_bb2_in(v__y3_0, v_1, v_6, v_7, v_x, v_7, v_y2_1, v__y3_0)) :|: TRUE
27.38/20.78	eval_perfect1_bb6_in(v__y3_0, v_1, v_6, v_7, v_x, v_y1_0, v_y2_1, v_y3_0) -> Com_1(eval_perfect1_bb7_in(v__y3_0, v_1, v_6, v_7, v_x, v_y1_0, v_y2_1, v_y3_0)) :|: v_y3_0 < 0
27.38/20.78	eval_perfect1_bb6_in(v__y3_0, v_1, v_6, v_7, v_x, v_y1_0, v_y2_1, v_y3_0) -> Com_1(eval_perfect1_bb7_in(v__y3_0, v_1, v_6, v_7, v_x, v_y1_0, v_y2_1, v_y3_0)) :|: v_y3_0 > 0
27.38/20.78	eval_perfect1_bb6_in(v__y3_0, v_1, v_6, v_7, v_x, v_y1_0, v_y2_1, v_y3_0) -> Com_1(eval_perfect1_bb7_in(v__y3_0, v_1, v_6, v_7, v_x, v_y1_0, v_y2_1, v_y3_0)) :|: v_y3_0 >= 0 && v_y3_0 <= 0
27.38/20.78	eval_perfect1_bb7_in(v__y3_0, v_1, v_6, v_7, v_x, v_y1_0, v_y2_1, v_y3_0) -> Com_1(eval_perfect1_stop(v__y3_0, v_1, v_6, v_7, v_x, v_y1_0, v_y2_1, v_y3_0)) :|: TRUE
27.38/20.78	
27.38/20.78	The start-symbols are:[eval_perfect1_start_8]
27.38/20.78	
27.38/20.78	
27.38/20.78	----------------------------------------
27.38/20.78	
27.38/20.78	(1) Loat Proof (FINISHED)
27.38/20.78	
27.38/20.78	
27.38/20.78	### Pre-processing the ITS problem ###
27.38/20.78	
27.38/20.78	
27.38/20.78	
27.38/20.78	Initial linear ITS problem
27.38/20.78	
27.38/20.78	   Start location: evalperfect1start
27.38/20.78	
27.38/20.78	      0: evalperfect1start -> evalperfect1bb0in : [], cost: 1
27.38/20.78	
27.38/20.78	      1: evalperfect1bb0in -> evalperfect10 : [], cost: 1
27.38/20.78	
27.38/20.78	      2: evalperfect10 -> evalperfect11 : [], cost: 1
27.38/20.78	
27.38/20.78	      3: evalperfect11 -> evalperfect1bb7in : [ 1>=A ], cost: 1
27.38/20.78	
27.38/20.78	      4: evalperfect11 -> evalperfect1bb1in : [ A>=2 ], cost: 1
27.38/20.78	
27.38/20.78	      5: evalperfect1bb1in -> evalperfect12 : [], cost: 1
27.38/20.78	
27.38/20.78	      6: evalperfect12 -> evalperfect13 : [], cost: 1
27.38/20.78	
27.38/20.78	      7: evalperfect13 -> evalperfect14 : [], cost: 1
27.38/20.78	
27.38/20.78	      8: evalperfect14 -> evalperfect15 : [], cost: 1
27.38/20.78	
27.38/20.78	      9: evalperfect15 -> evalperfect16 : B'=-1+A, [], cost: 1
27.38/20.78	
27.38/20.78	     10: evalperfect16 -> evalperfect17 : [], cost: 1
27.38/20.78	
27.38/20.78	     11: evalperfect17 -> evalperfect18 : [], cost: 1
27.38/20.78	
27.38/20.78	     12: evalperfect18 -> evalperfect1bb2in : C'=B, D'=A, [], cost: 1
27.38/20.78	
27.38/20.78	     13: evalperfect1bb2in -> evalperfect1bb3in : E'=A, [ C>=1 ], cost: 1
27.38/20.78	
27.38/20.78	     14: evalperfect1bb2in -> evalperfect1bb6in : [ 0>=C ], cost: 1
27.38/20.78	
27.38/20.78	     15: evalperfect1bb3in -> evalperfect1bb4in : [ E>=C ], cost: 1
27.38/20.78	
27.38/20.78	     16: evalperfect1bb3in -> evalperfect1bb5in : [ C>=1+E ], cost: 1
27.38/20.78	
27.38/20.78	     17: evalperfect1bb4in -> evalperfect1bb3in : E'=-C+E, [], cost: 1
27.38/20.78	
27.38/20.78	     18: evalperfect1bb5in -> evalperfect112 : F'=-C+D, [], cost: 1
27.38/20.78	
27.38/20.78	     19: evalperfect112 -> evalperfect113 : [], cost: 1
27.38/20.78	
27.38/20.78	     20: evalperfect113 -> evalperfect114 : G'=F, [ E==0 ], cost: 1
27.38/20.78	
27.38/20.78	     21: evalperfect113 -> evalperfect114 : G'=D, [ 0>=1+E ], cost: 1
27.38/20.78	
27.38/20.78	     22: evalperfect113 -> evalperfect114 : G'=D, [ E>=1 ], cost: 1
27.38/20.78	
27.38/20.78	     23: evalperfect114 -> evalperfect115 : [], cost: 1
27.38/20.78	
27.38/20.78	     24: evalperfect115 -> evalperfect116 : H'=-1+C, [], cost: 1
27.38/20.78	
27.38/20.78	     25: evalperfect116 -> evalperfect117 : [], cost: 1
27.38/20.78	
27.38/20.78	     26: evalperfect117 -> evalperfect1bb2in : C'=H, D'=G, [], cost: 1
27.38/20.78	
27.38/20.78	     27: evalperfect1bb6in -> evalperfect1bb7in : [ 0>=1+D ], cost: 1
27.38/20.78	
27.38/20.78	     28: evalperfect1bb6in -> evalperfect1bb7in : [ D>=1 ], cost: 1
27.38/20.78	
27.38/20.78	     29: evalperfect1bb6in -> evalperfect1bb7in : [ D==0 ], cost: 1
27.38/20.78	
27.38/20.78	     30: evalperfect1bb7in -> evalperfect1stop : [], cost: 1
27.38/20.78	
27.38/20.78	
27.38/20.78	
27.38/20.78	Removed unreachable and leaf rules:
27.38/20.78	
27.38/20.78	   Start location: evalperfect1start
27.38/20.78	
27.38/20.78	      0: evalperfect1start -> evalperfect1bb0in : [], cost: 1
27.38/20.78	
27.38/20.78	      1: evalperfect1bb0in -> evalperfect10 : [], cost: 1
27.38/20.78	
27.38/20.78	      2: evalperfect10 -> evalperfect11 : [], cost: 1
27.38/20.78	
27.38/20.78	      4: evalperfect11 -> evalperfect1bb1in : [ A>=2 ], cost: 1
27.38/20.78	
27.38/20.78	      5: evalperfect1bb1in -> evalperfect12 : [], cost: 1
27.38/20.78	
27.38/20.78	      6: evalperfect12 -> evalperfect13 : [], cost: 1
27.38/20.78	
27.38/20.78	      7: evalperfect13 -> evalperfect14 : [], cost: 1
27.38/20.78	
27.38/20.78	      8: evalperfect14 -> evalperfect15 : [], cost: 1
27.38/20.78	
27.38/20.78	      9: evalperfect15 -> evalperfect16 : B'=-1+A, [], cost: 1
27.38/20.78	
27.38/20.78	     10: evalperfect16 -> evalperfect17 : [], cost: 1
27.38/20.78	
27.38/20.78	     11: evalperfect17 -> evalperfect18 : [], cost: 1
27.38/20.78	
27.38/20.78	     12: evalperfect18 -> evalperfect1bb2in : C'=B, D'=A, [], cost: 1
27.38/20.78	
27.38/20.78	     13: evalperfect1bb2in -> evalperfect1bb3in : E'=A, [ C>=1 ], cost: 1
27.38/20.78	
27.38/20.78	     15: evalperfect1bb3in -> evalperfect1bb4in : [ E>=C ], cost: 1
27.38/20.78	
27.38/20.78	     16: evalperfect1bb3in -> evalperfect1bb5in : [ C>=1+E ], cost: 1
27.38/20.78	
27.38/20.78	     17: evalperfect1bb4in -> evalperfect1bb3in : E'=-C+E, [], cost: 1
27.38/20.78	
27.38/20.78	     18: evalperfect1bb5in -> evalperfect112 : F'=-C+D, [], cost: 1
27.38/20.78	
27.38/20.78	     19: evalperfect112 -> evalperfect113 : [], cost: 1
27.38/20.78	
27.38/20.78	     20: evalperfect113 -> evalperfect114 : G'=F, [ E==0 ], cost: 1
27.38/20.78	
27.38/20.78	     21: evalperfect113 -> evalperfect114 : G'=D, [ 0>=1+E ], cost: 1
27.38/20.78	
27.38/20.78	     22: evalperfect113 -> evalperfect114 : G'=D, [ E>=1 ], cost: 1
27.38/20.78	
27.38/20.78	     23: evalperfect114 -> evalperfect115 : [], cost: 1
27.38/20.78	
27.38/20.78	     24: evalperfect115 -> evalperfect116 : H'=-1+C, [], cost: 1
27.38/20.78	
27.38/20.78	     25: evalperfect116 -> evalperfect117 : [], cost: 1
27.38/20.78	
27.38/20.78	     26: evalperfect117 -> evalperfect1bb2in : C'=H, D'=G, [], cost: 1
27.38/20.78	
27.38/20.78	
27.38/20.78	
27.38/20.78	### Simplification by acceleration and chaining ###
27.38/20.78	
27.38/20.78	
27.38/20.78	
27.38/20.78	Eliminated locations (on linear paths):
27.38/20.78	
27.38/20.78	   Start location: evalperfect1start
27.38/20.78	
27.38/20.78	     41: evalperfect1start -> evalperfect1bb2in : B'=-1+A, C'=-1+A, D'=A, [ A>=2 ], cost: 12
27.38/20.78	
27.38/20.78	     13: evalperfect1bb2in -> evalperfect1bb3in : E'=A, [ C>=1 ], cost: 1
27.38/20.78	
27.38/20.78	     42: evalperfect1bb3in -> evalperfect1bb3in : E'=-C+E, [ E>=C ], cost: 2
27.38/20.78	
27.38/20.78	     44: evalperfect1bb3in -> evalperfect113 : F'=-C+D, [ C>=1+E ], cost: 3
27.38/20.78	
27.38/20.78	     20: evalperfect113 -> evalperfect114 : G'=F, [ E==0 ], cost: 1
27.38/20.78	
27.38/20.78	     21: evalperfect113 -> evalperfect114 : G'=D, [ 0>=1+E ], cost: 1
27.38/20.78	
27.38/20.78	     22: evalperfect113 -> evalperfect114 : G'=D, [ E>=1 ], cost: 1
27.38/20.78	
27.38/20.78	     47: evalperfect114 -> evalperfect1bb2in : C'=-1+C, D'=G, H'=-1+C, [], cost: 4
27.38/20.78	
27.38/20.78	
27.38/20.78	
27.38/20.78	Accelerating simple loops of location 13.
27.38/20.78	
27.38/20.78	   Accelerating the following rules:
27.38/20.78	
27.38/20.78	     42: evalperfect1bb3in -> evalperfect1bb3in : E'=-C+E, [ E>=C ], cost: 2
27.38/20.78	
27.38/20.78	
27.38/20.78	
27.38/20.78	   Found no metering function for rule 42.
27.38/20.78	
27.38/20.78	   Removing the simple loops:.
27.38/20.78	
27.38/20.78	
27.38/20.78	
27.38/20.78	Accelerated all simple loops using metering functions (where possible):
27.38/20.78	
27.38/20.78	   Start location: evalperfect1start
27.38/20.78	
27.38/20.78	     41: evalperfect1start -> evalperfect1bb2in : B'=-1+A, C'=-1+A, D'=A, [ A>=2 ], cost: 12
27.38/20.78	
27.38/20.78	     13: evalperfect1bb2in -> evalperfect1bb3in : E'=A, [ C>=1 ], cost: 1
27.38/20.78	
27.38/20.78	     42: evalperfect1bb3in -> evalperfect1bb3in : E'=-C+E, [ E>=C ], cost: 2
27.38/20.78	
27.38/20.78	     44: evalperfect1bb3in -> evalperfect113 : F'=-C+D, [ C>=1+E ], cost: 3
27.38/20.78	
27.38/20.78	     20: evalperfect113 -> evalperfect114 : G'=F, [ E==0 ], cost: 1
27.38/20.78	
27.38/20.78	     21: evalperfect113 -> evalperfect114 : G'=D, [ 0>=1+E ], cost: 1
27.38/20.78	
27.38/20.78	     22: evalperfect113 -> evalperfect114 : G'=D, [ E>=1 ], cost: 1
27.38/20.78	
27.38/20.78	     47: evalperfect114 -> evalperfect1bb2in : C'=-1+C, D'=G, H'=-1+C, [], cost: 4
27.38/20.78	
27.38/20.78	
27.38/20.78	
27.38/20.78	Chained accelerated rules (with incoming rules):
27.38/20.78	
27.38/20.78	   Start location: evalperfect1start
27.38/20.78	
27.38/20.78	     41: evalperfect1start -> evalperfect1bb2in : B'=-1+A, C'=-1+A, D'=A, [ A>=2 ], cost: 12
27.38/20.78	
27.38/20.78	     13: evalperfect1bb2in -> evalperfect1bb3in : E'=A, [ C>=1 ], cost: 1
27.38/20.78	
27.38/20.78	     48: evalperfect1bb2in -> evalperfect1bb3in : E'=-C+A, [ C>=1 && A>=C ], cost: 3
27.38/20.78	
27.38/20.78	     44: evalperfect1bb3in -> evalperfect113 : F'=-C+D, [ C>=1+E ], cost: 3
27.38/20.78	
27.38/20.78	     20: evalperfect113 -> evalperfect114 : G'=F, [ E==0 ], cost: 1
27.38/20.78	
27.38/20.78	     21: evalperfect113 -> evalperfect114 : G'=D, [ 0>=1+E ], cost: 1
27.38/20.78	
27.38/20.78	     22: evalperfect113 -> evalperfect114 : G'=D, [ E>=1 ], cost: 1
27.38/20.78	
27.38/20.78	     47: evalperfect114 -> evalperfect1bb2in : C'=-1+C, D'=G, H'=-1+C, [], cost: 4
27.38/20.78	
27.38/20.78	
27.38/20.78	
27.38/20.78	Eliminated locations (on tree-shaped paths):
27.38/20.78	
27.38/20.78	   Start location: evalperfect1start
27.38/20.78	
27.38/20.78	     41: evalperfect1start -> evalperfect1bb2in : B'=-1+A, C'=-1+A, D'=A, [ A>=2 ], cost: 12
27.38/20.78	
27.38/20.78	     49: evalperfect1bb2in -> evalperfect113 : E'=A, F'=-C+D, [ C>=1 && C>=1+A ], cost: 4
27.38/20.78	
27.38/20.78	     50: evalperfect1bb2in -> evalperfect113 : E'=-C+A, F'=-C+D, [ C>=1 && A>=C && C>=1-C+A ], cost: 6
27.38/20.78	
27.38/20.78	     51: evalperfect113 -> evalperfect1bb2in : C'=-1+C, D'=F, G'=F, H'=-1+C, [ E==0 ], cost: 5
27.38/20.78	
27.38/20.78	     52: evalperfect113 -> evalperfect1bb2in : C'=-1+C, D'=D, G'=D, H'=-1+C, [ 0>=1+E ], cost: 5
27.38/20.78	
27.38/20.78	     53: evalperfect113 -> evalperfect1bb2in : C'=-1+C, D'=D, G'=D, H'=-1+C, [ E>=1 ], cost: 5
27.38/20.78	
27.38/20.78	
27.38/20.78	
27.38/20.78	Eliminated locations (on tree-shaped paths):
27.38/20.78	
27.38/20.78	   Start location: evalperfect1start
27.38/20.78	
27.38/20.78	     41: evalperfect1start -> evalperfect1bb2in : B'=-1+A, C'=-1+A, D'=A, [ A>=2 ], cost: 12
27.38/20.78	
27.38/20.78	     54: evalperfect1bb2in -> evalperfect1bb2in : C'=-1+C, D'=-C+D, E'=A, F'=-C+D, G'=-C+D, H'=-1+C, [ C>=1 && C>=1+A && A==0 ], cost: 9
27.38/20.78	
27.38/20.78	     55: evalperfect1bb2in -> evalperfect1bb2in : C'=-1+C, D'=D, E'=A, F'=-C+D, G'=D, H'=-1+C, [ C>=1 && C>=1+A && 0>=1+A ], cost: 9
27.38/20.78	
27.38/20.78	     56: evalperfect1bb2in -> evalperfect1bb2in : C'=-1+C, D'=D, E'=A, F'=-C+D, G'=D, H'=-1+C, [ C>=1 && C>=1+A && A>=1 ], cost: 9
27.38/20.78	
27.38/20.78	     57: evalperfect1bb2in -> evalperfect1bb2in : C'=-1+C, D'=-C+D, E'=-C+A, F'=-C+D, G'=-C+D, H'=-1+C, [ C>=1 && C>=1-C+A && -C+A==0 ], cost: 11
27.38/20.78	
27.38/20.78	     58: evalperfect1bb2in -> evalperfect1bb2in : C'=-1+C, D'=D, E'=-C+A, F'=-C+D, G'=D, H'=-1+C, [ C>=1 && C>=1-C+A && -C+A>=1 ], cost: 11
27.38/20.78	
27.38/20.78	
27.38/20.78	
27.38/20.78	Accelerating simple loops of location 12.
27.38/20.78	
27.38/20.78	   Simplified some of the simple loops (and removed duplicate rules).
27.38/20.78	
27.38/20.78	   Accelerating the following rules:
27.38/20.78	
27.38/20.78	     54: evalperfect1bb2in -> evalperfect1bb2in : C'=-1+C, D'=-C+D, E'=A, F'=-C+D, G'=-C+D, H'=-1+C, [ C>=1 && C>=1+A && A==0 ], cost: 9
27.38/20.78	
27.38/20.78	     55: evalperfect1bb2in -> evalperfect1bb2in : C'=-1+C, E'=A, F'=-C+D, G'=D, H'=-1+C, [ C>=1 && C>=1+A && 0>=1+A ], cost: 9
27.38/20.78	
27.38/20.78	     56: evalperfect1bb2in -> evalperfect1bb2in : C'=-1+C, E'=A, F'=-C+D, G'=D, H'=-1+C, [ C>=1 && C>=1+A && A>=1 ], cost: 9
27.38/20.78	
27.38/20.78	     57: evalperfect1bb2in -> evalperfect1bb2in : C'=-1+C, D'=-C+D, E'=-C+A, F'=-C+D, G'=-C+D, H'=-1+C, [ C>=1 && C>=1-C+A && -C+A==0 ], cost: 11
27.38/20.78	
27.38/20.78	     58: evalperfect1bb2in -> evalperfect1bb2in : C'=-1+C, E'=-C+A, F'=-C+D, G'=D, H'=-1+C, [ C>=1 && C>=1-C+A && -C+A>=1 ], cost: 11
27.38/20.78	
27.38/20.78	
27.38/20.78	
27.38/20.78	   Accelerated rule 54 with metering function C-A, yielding the new rule 59.
27.38/20.78	
27.38/20.78	   Accelerated rule 55 with metering function C, yielding the new rule 60.
27.38/20.78	
27.38/20.78	   Accelerated rule 56 with metering function C-A, yielding the new rule 61.
27.38/20.78	
27.38/20.78	   Accelerated rule 57 with metering function C-A, yielding the new rule 62.
27.38/20.78	
27.38/20.78	   Accelerated rule 58 with metering function meter (where 2*meter==2*C-A), yielding the new rule 63.
27.38/20.78	
27.38/20.78	      During metering: Instantiating temporary variables by {meter==1}
27.38/20.78	
27.38/20.78	   Removing the simple loops: 54 55 56 57 58.
27.38/20.78	
27.38/20.78	
27.38/20.78	
27.38/20.78	Accelerated all simple loops using metering functions (where possible):
27.38/20.78	
27.38/20.78	   Start location: evalperfect1start
27.38/20.78	
27.38/20.78	     41: evalperfect1start -> evalperfect1bb2in : B'=-1+A, C'=-1+A, D'=A, [ A>=2 ], cost: 12
27.38/20.78	
27.38/20.78	     59: evalperfect1bb2in -> evalperfect1bb2in : C'=A, D'=-1-C*(C-A)+1/2*(C-A)^2+1/2*C+D-1/2*A, E'=A, F'=-2-C*(C-A)+1/2*(C-A)^2+1/2*C+D-1/2*A, G'=-2-C*(C-A)+1/2*(C-A)^2+1/2*C+D-1/2*A, H'=A, [ C>=1 && C>=1+A && A==0 ], cost: 9*C-9*A
27.38/20.78	
27.38/20.78	     60: evalperfect1bb2in -> evalperfect1bb2in : C'=0, E'=A, F'=-1+D, G'=D, H'=0, [ C>=1 && C>=1+A && 0>=1+A ], cost: 9*C
27.38/20.78	
27.38/20.78	     61: evalperfect1bb2in -> evalperfect1bb2in : C'=A, E'=A, F'=-1+D-A, G'=D, H'=A, [ C>=1 && C>=1+A && A>=1 ], cost: 9*C-9*A
27.38/20.78	
27.38/20.78	     62: evalperfect1bb2in -> evalperfect1bb2in : C'=A, D'=-1-C*(C-A)+1/2*(C-A)^2+1/2*C+D-1/2*A, E'=-1, F'=-2-C*(C-A)+1/2*(C-A)^2+1/2*C+D-1/2*A, G'=-2-C*(C-A)+1/2*(C-A)^2+1/2*C+D-1/2*A, H'=A, [ C>=1 && C>=1-C+A && -C+A==0 && C-A>=1 ], cost: 11*C-11*A
27.38/20.78	
27.38/20.78	     63: evalperfect1bb2in -> evalperfect1bb2in : C'=-meter+C, E'=-1+meter-C+A, F'=-1+meter-C+D, G'=D, H'=-meter+C, [ C>=1 && C>=1-C+A && -C+A>=1 && 2*meter==2*C-A && meter>=1 ], cost: 11*meter
27.38/20.78	
27.38/20.78	
27.38/20.78	
27.38/20.78	Chained accelerated rules (with incoming rules):
27.38/20.78	
27.38/20.78	   Start location: evalperfect1start
27.38/20.78	
27.38/20.78	     41: evalperfect1start -> evalperfect1bb2in : B'=-1+A, C'=-1+A, D'=A, [ A>=2 ], cost: 12
27.38/20.78	
27.38/20.78	     64: evalperfect1start -> evalperfect1bb2in : B'=-1+A, C'=-1-meter+A, D'=A, E'=meter, F'=meter, G'=A, H'=-1-meter+A, [ -1+A>=2 && 2*meter==-2+A && meter>=1 ], cost: 12+11*meter
27.38/20.78	
27.38/20.78	
27.38/20.78	
27.38/20.78	Removed unreachable locations (and leaf rules with constant cost):
27.38/20.78	
27.38/20.78	   Start location: evalperfect1start
27.38/20.78	
27.38/20.78	     64: evalperfect1start -> evalperfect1bb2in : B'=-1+A, C'=-1-meter+A, D'=A, E'=meter, F'=meter, G'=A, H'=-1-meter+A, [ -1+A>=2 && 2*meter==-2+A && meter>=1 ], cost: 12+11*meter
27.38/20.78	
27.38/20.78	
27.38/20.78	
27.38/20.78	### Computing asymptotic complexity ###
27.38/20.78	
27.38/20.78	
27.38/20.78	
27.38/20.78	Fully simplified ITS problem
27.38/20.78	
27.38/20.78	   Start location: evalperfect1start
27.38/20.78	
27.38/20.78	     64: evalperfect1start -> evalperfect1bb2in : B'=-1+A, C'=-1-meter+A, D'=A, E'=meter, F'=meter, G'=A, H'=-1-meter+A, [ -1+A>=2 && 2*meter==-2+A && meter>=1 ], cost: 12+11*meter
27.38/20.78	
27.38/20.78	
27.38/20.78	
27.38/20.78	Computing asymptotic complexity for rule 64
27.38/20.78	
27.38/20.78	   Solved the limit problem by the following transformations:
27.38/20.78	
27.38/20.78	      Created initial limit problem:
27.38/20.78	
27.38/20.78	      3+2*meter-A (+/+!), -1-2*meter+A (+/+!), 12+11*meter (+), -2+A (+/+!) [not solved]
27.38/20.78	
27.38/20.78	
27.38/20.78	
27.38/20.78	      applying transformation rule (C) using substitution {A==2+2*meter}
27.38/20.78	
27.38/20.78	      resulting limit problem:
27.38/20.78	
27.38/20.78	      1 (+/+!), 2*meter (+/+!), 12+11*meter (+) [not solved]
27.38/20.78	
27.38/20.78	
27.38/20.78	
27.38/20.78	      applying transformation rule (B), deleting 1 (+/+!)
27.38/20.78	
27.38/20.78	      resulting limit problem:
27.38/20.78	
27.38/20.78	      2*meter (+/+!), 12+11*meter (+) [not solved]
27.38/20.78	
27.38/20.78	
27.38/20.78	
27.38/20.78	      removing all constraints (solved by SMT)
27.38/20.78	
27.38/20.78	      resulting limit problem: [solved]
27.38/20.78	
27.38/20.78	
27.38/20.78	
27.38/20.78	      applying transformation rule (C) using substitution {meter==n}
27.38/20.78	
27.38/20.78	      resulting limit problem:
27.38/20.78	
27.38/20.78	      [solved]
27.38/20.78	
27.38/20.78	
27.38/20.78	
27.38/20.78	   Solved the limit problem by the following transformations:
27.38/20.78	
27.38/20.78	      Created initial limit problem:
27.38/20.78	
27.38/20.78	      3+2*meter-A (+/+!), -1-2*meter+A (+/+!), 12+11*meter (+), -2+A (+/+!) [not solved]
27.38/20.78	
27.38/20.78	
27.38/20.78	
27.38/20.78	      applying transformation rule (C) using substitution {A==2+2*meter}
27.38/20.78	
27.38/20.78	      resulting limit problem:
27.38/20.78	
27.38/20.78	      1 (+/+!), 2*meter (+/+!), 12+11*meter (+) [not solved]
27.38/20.78	
27.38/20.78	
27.38/20.78	
27.38/20.78	      applying transformation rule (B), deleting 1 (+/+!)
27.38/20.78	
27.38/20.78	      resulting limit problem:
27.38/20.78	
27.38/20.78	      2*meter (+/+!), 12+11*meter (+) [not solved]
27.38/20.78	
27.38/20.78	
27.38/20.78	
27.38/20.78	      removing all constraints (solved by SMT)
27.38/20.78	
27.38/20.78	      resulting limit problem: [solved]
27.38/20.78	
27.38/20.78	
27.38/20.78	
27.38/20.78	      applying transformation rule (C) using substitution {meter==n}
27.38/20.78	
27.38/20.78	      resulting limit problem:
27.38/20.78	
27.38/20.78	      [solved]
27.38/20.78	
27.38/20.78	
27.38/20.78	
27.38/20.78	   Solution:
27.38/20.78	
27.38/20.78	      meter / n
27.38/20.78	
27.38/20.78	      A / 2+2*n
27.38/20.78	
27.38/20.78	   Resulting cost 12+11*n has complexity: Poly(n^1)
27.38/20.78	
27.38/20.78	
27.38/20.78	
27.38/20.78	Found new complexity Poly(n^1).
27.38/20.78	
27.38/20.78	
27.38/20.78	
27.38/20.78	Obtained the following overall complexity (w.r.t. the length of the input n):
27.38/20.78	
27.38/20.78	   Complexity:  Poly(n^1)
27.38/20.78	
27.38/20.78	   Cpx degree:  1
27.38/20.78	
27.38/20.78	   Solved cost: 12+11*n
27.38/20.78	
27.38/20.78	   Rule cost:   12+11*meter
27.38/20.78	
27.38/20.78	   Rule guard:  [ -1+A>=2 && 2*meter==-2+A ]
27.38/20.78	
27.38/20.78	
27.38/20.78	
27.38/20.78	WORST_CASE(Omega(n^1),?)
27.38/20.78	
27.38/20.78	
27.38/20.78	----------------------------------------
27.38/20.78	
27.38/20.78	(2)
27.38/20.78	BOUNDS(n^1, INF)
27.58/20.80	EOF