35.06/24.19	WORST_CASE(Omega(n^2), ?)
35.13/24.20	proof of /export/starexec/sandbox/benchmark/theBenchmark.koat
35.13/24.20	# AProVE Commit ID: 48fb2092695e11cc9f56e44b17a92a5f88ffb256 marcel 20180622 unpublished dirty
35.13/24.20	
35.13/24.20	
35.13/24.20	The runtime complexity of the given CpxIntTrs could be proven to be BOUNDS(n^2, INF).
35.13/24.20	
35.13/24.20	(0) CpxIntTrs
35.13/24.20	(1) Loat Proof [FINISHED, 2621 ms]
35.13/24.20	(2) BOUNDS(n^2, INF)
35.13/24.20	
35.13/24.20	
35.13/24.20	----------------------------------------
35.13/24.20	
35.13/24.20	(0)
35.13/24.20	Obligation:
35.13/24.20	Complexity Int TRS consisting of the following rules:
35.13/24.20	eval_serpent_start(v_3, v_6, v_8, v_n, v_x_0, v_y_0, v_y_1, v_y_2) -> Com_1(eval_serpent_bb0_in(v_3, v_6, v_8, v_n, v_x_0, v_y_0, v_y_1, v_y_2)) :|: TRUE
35.13/24.20	eval_serpent_bb0_in(v_3, v_6, v_8, v_n, v_x_0, v_y_0, v_y_1, v_y_2) -> Com_1(eval_serpent_0(v_3, v_6, v_8, v_n, v_x_0, v_y_0, v_y_1, v_y_2)) :|: TRUE
35.13/24.20	eval_serpent_0(v_3, v_6, v_8, v_n, v_x_0, v_y_0, v_y_1, v_y_2) -> Com_1(eval_serpent_1(v_3, v_6, v_8, v_n, v_x_0, v_y_0, v_y_1, v_y_2)) :|: TRUE
35.13/24.20	eval_serpent_1(v_3, v_6, v_8, v_n, v_x_0, v_y_0, v_y_1, v_y_2) -> Com_1(eval_serpent_bb7_in(v_3, v_6, v_8, v_n, v_x_0, v_y_0, v_y_1, v_y_2)) :|: v_n <= 0
35.13/24.20	eval_serpent_1(v_3, v_6, v_8, v_n, v_x_0, v_y_0, v_y_1, v_y_2) -> Com_1(eval_serpent__critedge1_in(v_3, v_6, v_8, v_n, v_n, v_n, v_y_1, v_y_2)) :|: v_n > 0
35.13/24.20	eval_serpent__critedge1_in(v_3, v_6, v_8, v_n, v_x_0, v_y_0, v_y_1, v_y_2) -> Com_1(eval_serpent_bb1_in(v_3, v_6, v_8, v_n, v_x_0, v_y_0, v_y_0, v_y_2)) :|: v_x_0 >= 0
35.13/24.20	eval_serpent__critedge1_in(v_3, v_6, v_8, v_n, v_x_0, v_y_0, v_y_1, v_y_2) -> Com_1(eval_serpent_bb7_in(v_3, v_6, v_8, v_n, v_x_0, v_y_0, v_y_1, v_y_2)) :|: v_x_0 < 0
35.13/24.20	eval_serpent_bb1_in(v_3, v_6, v_8, v_n, v_x_0, v_y_0, v_y_1, v_y_2) -> Com_1(eval_serpent_bb2_in(v_3, v_6, v_8, v_n, v_x_0, v_y_0, v_y_1, v_y_2)) :|: v_y_1 >= 0
35.13/24.20	eval_serpent_bb1_in(v_3, v_6, v_8, v_n, v_x_0, v_y_0, v_y_1, v_y_2) -> Com_1(eval_serpent__critedge_in(v_3, v_6, v_8, v_n, v_x_0, v_y_0, v_y_1, v_y_2)) :|: v_y_1 < 0
35.13/24.20	eval_serpent_bb2_in(v_3, v_6, v_8, v_n, v_x_0, v_y_0, v_y_1, v_y_2) -> Com_1(eval_serpent_2(v_3, v_6, v_8, v_n, v_x_0, v_y_0, v_y_1, v_y_2)) :|: TRUE
35.13/24.20	eval_serpent_2(v_3, v_6, v_8, v_n, v_x_0, v_y_0, v_y_1, v_y_2) -> Com_1(eval_serpent_3(nondef_0, v_6, v_8, v_n, v_x_0, v_y_0, v_y_1, v_y_2)) :|: TRUE
35.13/24.20	eval_serpent_3(v_3, v_6, v_8, v_n, v_x_0, v_y_0, v_y_1, v_y_2) -> Com_1(eval_serpent_bb3_in(v_3, v_6, v_8, v_n, v_x_0, v_y_0, v_y_1, v_y_2)) :|: v_3 > 0
35.13/24.20	eval_serpent_3(v_3, v_6, v_8, v_n, v_x_0, v_y_0, v_y_1, v_y_2) -> Com_1(eval_serpent__critedge_in(v_3, v_6, v_8, v_n, v_x_0, v_y_0, v_y_1, v_y_2)) :|: v_3 <= 0
35.13/24.20	eval_serpent_bb3_in(v_3, v_6, v_8, v_n, v_x_0, v_y_0, v_y_1, v_y_2) -> Com_1(eval_serpent_bb1_in(v_3, v_6, v_8, v_n, v_x_0, v_y_0, v_y_1 - 1, v_y_2)) :|: TRUE
35.13/24.20	eval_serpent__critedge_in(v_3, v_6, v_8, v_n, v_x_0, v_y_0, v_y_1, v_y_2) -> Com_1(eval_serpent_7(v_3, v_x_0 - 1, v_8, v_n, v_x_0, v_y_0, v_y_1, v_y_2)) :|: TRUE
35.13/24.20	eval_serpent_7(v_3, v_6, v_8, v_n, v_x_0, v_y_0, v_y_1, v_y_2) -> Com_1(eval_serpent_8(v_3, v_6, v_8, v_n, v_x_0, v_y_0, v_y_1, v_y_2)) :|: TRUE
35.13/24.20	eval_serpent_8(v_3, v_6, v_8, v_n, v_x_0, v_y_0, v_y_1, v_y_2) -> Com_1(eval_serpent_9(v_3, v_6, v_8, v_n, v_x_0, v_y_0, v_y_1, v_y_2)) :|: TRUE
35.13/24.20	eval_serpent_9(v_3, v_6, v_8, v_n, v_x_0, v_y_0, v_y_1, v_y_2) -> Com_1(eval_serpent_bb4_in(v_3, v_6, v_8, v_n, v_x_0, v_y_0, v_y_1, v_y_1)) :|: TRUE
35.13/24.20	eval_serpent_bb4_in(v_3, v_6, v_8, v_n, v_x_0, v_y_0, v_y_1, v_y_2) -> Com_1(eval_serpent_bb5_in(v_3, v_6, v_8, v_n, v_x_0, v_y_0, v_y_1, v_y_2)) :|: v_y_2 <= v_n
35.13/24.20	eval_serpent_bb4_in(v_3, v_6, v_8, v_n, v_x_0, v_y_0, v_y_1, v_y_2) -> Com_1(eval_serpent__critedge1_in(v_3, v_6, v_8, v_n, v_6, v_y_2, v_y_1, v_y_2)) :|: v_y_2 > v_n
35.13/24.20	eval_serpent_bb5_in(v_3, v_6, v_8, v_n, v_x_0, v_y_0, v_y_1, v_y_2) -> Com_1(eval_serpent_10(v_3, v_6, v_8, v_n, v_x_0, v_y_0, v_y_1, v_y_2)) :|: TRUE
35.13/24.20	eval_serpent_10(v_3, v_6, v_8, v_n, v_x_0, v_y_0, v_y_1, v_y_2) -> Com_1(eval_serpent_11(v_3, v_6, nondef_1, v_n, v_x_0, v_y_0, v_y_1, v_y_2)) :|: TRUE
35.13/24.20	eval_serpent_11(v_3, v_6, v_8, v_n, v_x_0, v_y_0, v_y_1, v_y_2) -> Com_1(eval_serpent_bb6_in(v_3, v_6, v_8, v_n, v_x_0, v_y_0, v_y_1, v_y_2)) :|: v_8 > 0
35.13/24.20	eval_serpent_11(v_3, v_6, v_8, v_n, v_x_0, v_y_0, v_y_1, v_y_2) -> Com_1(eval_serpent__critedge1_in(v_3, v_6, v_8, v_n, v_6, v_y_2, v_y_1, v_y_2)) :|: v_8 <= 0
35.13/24.20	eval_serpent_bb6_in(v_3, v_6, v_8, v_n, v_x_0, v_y_0, v_y_1, v_y_2) -> Com_1(eval_serpent_bb4_in(v_3, v_6, v_8, v_n, v_x_0, v_y_0, v_y_1, v_y_2 + 1)) :|: TRUE
35.13/24.20	eval_serpent_bb7_in(v_3, v_6, v_8, v_n, v_x_0, v_y_0, v_y_1, v_y_2) -> Com_1(eval_serpent_stop(v_3, v_6, v_8, v_n, v_x_0, v_y_0, v_y_1, v_y_2)) :|: TRUE
35.13/24.20	
35.13/24.20	The start-symbols are:[eval_serpent_start_8]
35.13/24.20	
35.13/24.20	
35.13/24.20	----------------------------------------
35.13/24.20	
35.13/24.20	(1) Loat Proof (FINISHED)
35.13/24.20	
35.13/24.20	
35.13/24.20	### Pre-processing the ITS problem ###
35.13/24.20	
35.13/24.20	
35.13/24.20	
35.13/24.20	Initial linear ITS problem
35.13/24.20	
35.13/24.20	   Start location: evalserpentstart
35.13/24.20	
35.13/24.20	      0: evalserpentstart -> evalserpentbb0in : [], cost: 1
35.13/24.20	
35.13/24.20	      1: evalserpentbb0in -> evalserpent0 : [], cost: 1
35.13/24.20	
35.13/24.20	      2: evalserpent0 -> evalserpent1 : [], cost: 1
35.13/24.20	
35.13/24.20	      3: evalserpent1 -> evalserpentbb7in : [ 0>=A ], cost: 1
35.13/24.20	
35.13/24.20	      4: evalserpent1 -> evalserpentcritedge1in : B'=A, C'=A, [ A>=1 ], cost: 1
35.13/24.20	
35.13/24.20	      5: evalserpentcritedge1in -> evalserpentbb1in : D'=C, [ B>=0 ], cost: 1
35.13/24.20	
35.13/24.20	      6: evalserpentcritedge1in -> evalserpentbb7in : [ 0>=1+B ], cost: 1
35.13/24.20	
35.13/24.20	      7: evalserpentbb1in -> evalserpentbb2in : [ D>=0 ], cost: 1
35.13/24.20	
35.13/24.20	      8: evalserpentbb1in -> evalserpentcritedgein : [ 0>=1+D ], cost: 1
35.13/24.20	
35.13/24.20	      9: evalserpentbb2in -> evalserpent2 : [], cost: 1
35.13/24.20	
35.13/24.20	     10: evalserpent2 -> evalserpent3 : E'=free, [], cost: 1
35.13/24.20	
35.13/24.20	     11: evalserpent3 -> evalserpentbb3in : [ E>=1 ], cost: 1
35.13/24.20	
35.13/24.20	     12: evalserpent3 -> evalserpentcritedgein : [ 0>=E ], cost: 1
35.13/24.20	
35.13/24.20	     13: evalserpentbb3in -> evalserpentbb1in : D'=-1+D, [], cost: 1
35.13/24.20	
35.13/24.20	     14: evalserpentcritedgein -> evalserpent7 : F'=-1+B, [], cost: 1
35.13/24.20	
35.13/24.20	     15: evalserpent7 -> evalserpent8 : [], cost: 1
35.13/24.20	
35.13/24.20	     16: evalserpent8 -> evalserpent9 : [], cost: 1
35.13/24.20	
35.13/24.20	     17: evalserpent9 -> evalserpentbb4in : G'=D, [], cost: 1
35.13/24.20	
35.13/24.20	     18: evalserpentbb4in -> evalserpentbb5in : [ A>=G ], cost: 1
35.13/24.20	
35.13/24.20	     19: evalserpentbb4in -> evalserpentcritedge1in : B'=F, C'=G, [ G>=1+A ], cost: 1
35.13/24.20	
35.13/24.20	     20: evalserpentbb5in -> evalserpent10 : [], cost: 1
35.13/24.20	
35.13/24.20	     21: evalserpent10 -> evalserpent11 : H'=free_1, [], cost: 1
35.13/24.20	
35.13/24.20	     22: evalserpent11 -> evalserpentbb6in : [ H>=1 ], cost: 1
35.13/24.20	
35.13/24.20	     23: evalserpent11 -> evalserpentcritedge1in : B'=F, C'=G, [ 0>=H ], cost: 1
35.13/24.20	
35.13/24.20	     24: evalserpentbb6in -> evalserpentbb4in : G'=1+G, [], cost: 1
35.13/24.20	
35.13/24.20	     25: evalserpentbb7in -> evalserpentstop : [], cost: 1
35.13/24.20	
35.13/24.20	
35.13/24.20	
35.13/24.20	Removed unreachable and leaf rules:
35.13/24.20	
35.13/24.20	   Start location: evalserpentstart
35.13/24.20	
35.13/24.20	      0: evalserpentstart -> evalserpentbb0in : [], cost: 1
35.13/24.20	
35.13/24.20	      1: evalserpentbb0in -> evalserpent0 : [], cost: 1
35.13/24.20	
35.13/24.20	      2: evalserpent0 -> evalserpent1 : [], cost: 1
35.13/24.20	
35.13/24.20	      4: evalserpent1 -> evalserpentcritedge1in : B'=A, C'=A, [ A>=1 ], cost: 1
35.13/24.20	
35.13/24.20	      5: evalserpentcritedge1in -> evalserpentbb1in : D'=C, [ B>=0 ], cost: 1
35.13/24.20	
35.13/24.20	      7: evalserpentbb1in -> evalserpentbb2in : [ D>=0 ], cost: 1
35.13/24.20	
35.13/24.20	      8: evalserpentbb1in -> evalserpentcritedgein : [ 0>=1+D ], cost: 1
35.13/24.20	
35.13/24.20	      9: evalserpentbb2in -> evalserpent2 : [], cost: 1
35.13/24.20	
35.13/24.20	     10: evalserpent2 -> evalserpent3 : E'=free, [], cost: 1
35.13/24.20	
35.13/24.20	     11: evalserpent3 -> evalserpentbb3in : [ E>=1 ], cost: 1
35.13/24.20	
35.13/24.20	     12: evalserpent3 -> evalserpentcritedgein : [ 0>=E ], cost: 1
35.13/24.20	
35.13/24.20	     13: evalserpentbb3in -> evalserpentbb1in : D'=-1+D, [], cost: 1
35.13/24.20	
35.13/24.20	     14: evalserpentcritedgein -> evalserpent7 : F'=-1+B, [], cost: 1
35.13/24.20	
35.13/24.20	     15: evalserpent7 -> evalserpent8 : [], cost: 1
35.13/24.20	
35.13/24.20	     16: evalserpent8 -> evalserpent9 : [], cost: 1
35.13/24.20	
35.13/24.20	     17: evalserpent9 -> evalserpentbb4in : G'=D, [], cost: 1
35.13/24.20	
35.13/24.20	     18: evalserpentbb4in -> evalserpentbb5in : [ A>=G ], cost: 1
35.13/24.20	
35.13/24.20	     19: evalserpentbb4in -> evalserpentcritedge1in : B'=F, C'=G, [ G>=1+A ], cost: 1
35.13/24.20	
35.13/24.20	     20: evalserpentbb5in -> evalserpent10 : [], cost: 1
35.13/24.20	
35.13/24.20	     21: evalserpent10 -> evalserpent11 : H'=free_1, [], cost: 1
35.13/24.20	
35.13/24.20	     22: evalserpent11 -> evalserpentbb6in : [ H>=1 ], cost: 1
35.13/24.20	
35.13/24.20	     23: evalserpent11 -> evalserpentcritedge1in : B'=F, C'=G, [ 0>=H ], cost: 1
35.13/24.20	
35.13/24.20	     24: evalserpentbb6in -> evalserpentbb4in : G'=1+G, [], cost: 1
35.13/24.20	
35.13/24.20	
35.13/24.20	
35.13/24.20	### Simplification by acceleration and chaining ###
35.13/24.20	
35.13/24.20	
35.13/24.20	
35.13/24.20	Eliminated locations (on linear paths):
35.13/24.20	
35.13/24.20	   Start location: evalserpentstart
35.13/24.20	
35.13/24.20	     28: evalserpentstart -> evalserpentcritedge1in : B'=A, C'=A, [ A>=1 ], cost: 4
35.13/24.20	
35.13/24.20	      5: evalserpentcritedge1in -> evalserpentbb1in : D'=C, [ B>=0 ], cost: 1
35.13/24.20	
35.13/24.20	      8: evalserpentbb1in -> evalserpentcritedgein : [ 0>=1+D ], cost: 1
35.13/24.20	
35.13/24.20	     30: evalserpentbb1in -> evalserpent3 : E'=free, [ D>=0 ], cost: 3
35.13/24.20	
35.13/24.20	     12: evalserpent3 -> evalserpentcritedgein : [ 0>=E ], cost: 1
35.13/24.20	
35.13/24.20	     31: evalserpent3 -> evalserpentbb1in : D'=-1+D, [ E>=1 ], cost: 2
35.13/24.20	
35.13/24.20	     34: evalserpentcritedgein -> evalserpentbb4in : F'=-1+B, G'=D, [], cost: 4
35.13/24.20	
35.13/24.20	     19: evalserpentbb4in -> evalserpentcritedge1in : B'=F, C'=G, [ G>=1+A ], cost: 1
35.13/24.20	
35.13/24.20	     36: evalserpentbb4in -> evalserpent11 : H'=free_1, [ A>=G ], cost: 3
35.13/24.20	
35.13/24.20	     23: evalserpent11 -> evalserpentcritedge1in : B'=F, C'=G, [ 0>=H ], cost: 1
35.13/24.20	
35.13/24.20	     37: evalserpent11 -> evalserpentbb4in : G'=1+G, [ H>=1 ], cost: 2
35.13/24.20	
35.13/24.20	
35.13/24.20	
35.13/24.20	Eliminated locations (on tree-shaped paths):
35.13/24.20	
35.13/24.20	   Start location: evalserpentstart
35.13/24.20	
35.13/24.20	     28: evalserpentstart -> evalserpentcritedge1in : B'=A, C'=A, [ A>=1 ], cost: 4
35.13/24.20	
35.13/24.20	      5: evalserpentcritedge1in -> evalserpentbb1in : D'=C, [ B>=0 ], cost: 1
35.13/24.20	
35.13/24.20	     39: evalserpentbb1in -> evalserpentbb1in : D'=-1+D, E'=free, [ D>=0 && free>=1 ], cost: 5
35.13/24.20	
35.13/24.20	     40: evalserpentbb1in -> evalserpentbb4in : F'=-1+B, G'=D, [ 0>=1+D ], cost: 5
35.13/24.20	
35.13/24.20	     41: evalserpentbb1in -> evalserpentbb4in : E'=free, F'=-1+B, G'=D, [ D>=0 && 0>=free ], cost: 8
35.13/24.20	
35.13/24.20	     19: evalserpentbb4in -> evalserpentcritedge1in : B'=F, C'=G, [ G>=1+A ], cost: 1
35.13/24.20	
35.13/24.20	     42: evalserpentbb4in -> evalserpentcritedge1in : B'=F, C'=G, H'=free_1, [ A>=G && 0>=free_1 ], cost: 4
35.13/24.20	
35.13/24.20	     43: evalserpentbb4in -> evalserpentbb4in : G'=1+G, H'=free_1, [ A>=G && free_1>=1 ], cost: 5
35.13/24.20	
35.13/24.20	
35.13/24.20	
35.13/24.20	Accelerating simple loops of location 5.
35.13/24.20	
35.13/24.20	   Accelerating the following rules:
35.13/24.20	
35.13/24.20	     39: evalserpentbb1in -> evalserpentbb1in : D'=-1+D, E'=free, [ D>=0 && free>=1 ], cost: 5
35.13/24.20	
35.13/24.20	
35.13/24.20	
35.13/24.20	   Accelerated rule 39 with metering function 1+D, yielding the new rule 44.
35.13/24.20	
35.13/24.20	   Removing the simple loops: 39.
35.13/24.20	
35.13/24.20	
35.13/24.20	
35.13/24.20	Accelerating simple loops of location 14.
35.13/24.20	
35.13/24.20	   Accelerating the following rules:
35.13/24.20	
35.13/24.20	     43: evalserpentbb4in -> evalserpentbb4in : G'=1+G, H'=free_1, [ A>=G && free_1>=1 ], cost: 5
35.13/24.20	
35.13/24.20	
35.13/24.20	
35.13/24.20	   Accelerated rule 43 with metering function 1-G+A, yielding the new rule 45.
35.13/24.20	
35.13/24.20	   Removing the simple loops: 43.
35.13/24.20	
35.13/24.20	
35.13/24.20	
35.13/24.20	Accelerated all simple loops using metering functions (where possible):
35.13/24.20	
35.13/24.20	   Start location: evalserpentstart
35.13/24.20	
35.13/24.20	     28: evalserpentstart -> evalserpentcritedge1in : B'=A, C'=A, [ A>=1 ], cost: 4
35.13/24.20	
35.13/24.20	      5: evalserpentcritedge1in -> evalserpentbb1in : D'=C, [ B>=0 ], cost: 1
35.13/24.20	
35.13/24.20	     40: evalserpentbb1in -> evalserpentbb4in : F'=-1+B, G'=D, [ 0>=1+D ], cost: 5
35.13/24.20	
35.13/24.20	     41: evalserpentbb1in -> evalserpentbb4in : E'=free, F'=-1+B, G'=D, [ D>=0 && 0>=free ], cost: 8
35.13/24.20	
35.13/24.20	     44: evalserpentbb1in -> evalserpentbb1in : D'=-1, E'=free, [ D>=0 && free>=1 ], cost: 5+5*D
35.13/24.20	
35.13/24.20	     19: evalserpentbb4in -> evalserpentcritedge1in : B'=F, C'=G, [ G>=1+A ], cost: 1
35.13/24.20	
35.13/24.20	     42: evalserpentbb4in -> evalserpentcritedge1in : B'=F, C'=G, H'=free_1, [ A>=G && 0>=free_1 ], cost: 4
35.13/24.20	
35.13/24.20	     45: evalserpentbb4in -> evalserpentbb4in : G'=1+A, H'=free_1, [ A>=G && free_1>=1 ], cost: 5-5*G+5*A
35.13/24.20	
35.13/24.20	
35.13/24.20	
35.13/24.20	Chained accelerated rules (with incoming rules):
35.13/24.20	
35.13/24.20	   Start location: evalserpentstart
35.13/24.20	
35.13/24.20	     28: evalserpentstart -> evalserpentcritedge1in : B'=A, C'=A, [ A>=1 ], cost: 4
35.13/24.20	
35.13/24.20	      5: evalserpentcritedge1in -> evalserpentbb1in : D'=C, [ B>=0 ], cost: 1
35.13/24.20	
35.13/24.20	     46: evalserpentcritedge1in -> evalserpentbb1in : D'=-1, E'=free, [ B>=0 && C>=0 && free>=1 ], cost: 6+5*C
35.13/24.20	
35.13/24.20	     40: evalserpentbb1in -> evalserpentbb4in : F'=-1+B, G'=D, [ 0>=1+D ], cost: 5
35.13/24.20	
35.13/24.20	     41: evalserpentbb1in -> evalserpentbb4in : E'=free, F'=-1+B, G'=D, [ D>=0 && 0>=free ], cost: 8
35.13/24.20	
35.13/24.20	     47: evalserpentbb1in -> evalserpentbb4in : F'=-1+B, G'=1+A, H'=free_1, [ 0>=1+D && A>=D && free_1>=1 ], cost: 10-5*D+5*A
35.13/24.20	
35.13/24.20	     48: evalserpentbb1in -> evalserpentbb4in : E'=free, F'=-1+B, G'=1+A, H'=free_1, [ D>=0 && 0>=free && A>=D && free_1>=1 ], cost: 13-5*D+5*A
35.13/24.20	
35.13/24.20	     19: evalserpentbb4in -> evalserpentcritedge1in : B'=F, C'=G, [ G>=1+A ], cost: 1
35.13/24.20	
35.13/24.20	     42: evalserpentbb4in -> evalserpentcritedge1in : B'=F, C'=G, H'=free_1, [ A>=G && 0>=free_1 ], cost: 4
35.13/24.20	
35.13/24.20	
35.13/24.20	
35.13/24.20	Eliminated locations (on tree-shaped paths):
35.13/24.20	
35.13/24.20	   Start location: evalserpentstart
35.13/24.20	
35.13/24.20	     28: evalserpentstart -> evalserpentcritedge1in : B'=A, C'=A, [ A>=1 ], cost: 4
35.13/24.20	
35.13/24.20	     49: evalserpentcritedge1in -> evalserpentbb4in : D'=C, F'=-1+B, G'=C, [ B>=0 && 0>=1+C ], cost: 6
35.13/24.20	
35.13/24.20	     50: evalserpentcritedge1in -> evalserpentbb4in : D'=C, E'=free, F'=-1+B, G'=C, [ B>=0 && C>=0 && 0>=free ], cost: 9
35.13/24.20	
35.13/24.20	     51: evalserpentcritedge1in -> evalserpentbb4in : D'=C, F'=-1+B, G'=1+A, H'=free_1, [ B>=0 && 0>=1+C && A>=C && free_1>=1 ], cost: 11-5*C+5*A
35.13/24.20	
35.13/24.20	     52: evalserpentcritedge1in -> evalserpentbb4in : D'=C, E'=free, F'=-1+B, G'=1+A, H'=free_1, [ B>=0 && C>=0 && 0>=free && A>=C && free_1>=1 ], cost: 14-5*C+5*A
35.13/24.20	
35.13/24.20	     53: evalserpentcritedge1in -> evalserpentbb4in : D'=-1, E'=free, F'=-1+B, G'=-1, [ B>=0 && C>=0 && free>=1 ], cost: 11+5*C
35.13/24.20	
35.13/24.20	     54: evalserpentcritedge1in -> evalserpentbb4in : D'=-1, E'=free, F'=-1+B, G'=1+A, H'=free_1, [ B>=0 && C>=0 && free>=1 && A>=-1 && free_1>=1 ], cost: 21+5*C+5*A
35.13/24.20	
35.13/24.20	     55: evalserpentcritedge1in -> [23] : [ B>=0 && C>=0 && free>=1 ], cost: 6+5*C
35.13/24.20	
35.13/24.20	     19: evalserpentbb4in -> evalserpentcritedge1in : B'=F, C'=G, [ G>=1+A ], cost: 1
35.13/24.20	
35.13/24.20	     42: evalserpentbb4in -> evalserpentcritedge1in : B'=F, C'=G, H'=free_1, [ A>=G && 0>=free_1 ], cost: 4
35.13/24.20	
35.13/24.20	
35.13/24.20	
35.13/24.20	Applied pruning (of leafs and parallel rules):
35.13/24.20	
35.13/24.20	   Start location: evalserpentstart
35.13/24.20	
35.13/24.20	     28: evalserpentstart -> evalserpentcritedge1in : B'=A, C'=A, [ A>=1 ], cost: 4
35.13/24.20	
35.13/24.20	     49: evalserpentcritedge1in -> evalserpentbb4in : D'=C, F'=-1+B, G'=C, [ B>=0 && 0>=1+C ], cost: 6
35.13/24.20	
35.13/24.20	     51: evalserpentcritedge1in -> evalserpentbb4in : D'=C, F'=-1+B, G'=1+A, H'=free_1, [ B>=0 && 0>=1+C && A>=C && free_1>=1 ], cost: 11-5*C+5*A
35.13/24.20	
35.13/24.20	     52: evalserpentcritedge1in -> evalserpentbb4in : D'=C, E'=free, F'=-1+B, G'=1+A, H'=free_1, [ B>=0 && C>=0 && 0>=free && A>=C && free_1>=1 ], cost: 14-5*C+5*A
35.13/24.20	
35.13/24.20	     53: evalserpentcritedge1in -> evalserpentbb4in : D'=-1, E'=free, F'=-1+B, G'=-1, [ B>=0 && C>=0 && free>=1 ], cost: 11+5*C
35.13/24.20	
35.13/24.20	     54: evalserpentcritedge1in -> evalserpentbb4in : D'=-1, E'=free, F'=-1+B, G'=1+A, H'=free_1, [ B>=0 && C>=0 && free>=1 && A>=-1 && free_1>=1 ], cost: 21+5*C+5*A
35.13/24.20	
35.13/24.20	     55: evalserpentcritedge1in -> [23] : [ B>=0 && C>=0 && free>=1 ], cost: 6+5*C
35.13/24.20	
35.13/24.20	     19: evalserpentbb4in -> evalserpentcritedge1in : B'=F, C'=G, [ G>=1+A ], cost: 1
35.13/24.20	
35.13/24.20	     42: evalserpentbb4in -> evalserpentcritedge1in : B'=F, C'=G, H'=free_1, [ A>=G && 0>=free_1 ], cost: 4
35.13/24.20	
35.13/24.20	
35.13/24.20	
35.13/24.20	Eliminated locations (on tree-shaped paths):
35.13/24.20	
35.13/24.20	   Start location: evalserpentstart
35.13/24.20	
35.13/24.20	     28: evalserpentstart -> evalserpentcritedge1in : B'=A, C'=A, [ A>=1 ], cost: 4
35.13/24.20	
35.13/24.20	     55: evalserpentcritedge1in -> [23] : [ B>=0 && C>=0 && free>=1 ], cost: 6+5*C
35.13/24.20	
35.13/24.20	     56: evalserpentcritedge1in -> evalserpentcritedge1in : B'=-1+B, C'=C, D'=C, F'=-1+B, G'=C, [ B>=0 && 0>=1+C && C>=1+A ], cost: 7
35.13/24.20	
35.13/24.20	     57: evalserpentcritedge1in -> evalserpentcritedge1in : B'=-1+B, C'=C, D'=C, F'=-1+B, G'=C, H'=free_1, [ B>=0 && 0>=1+C && A>=C && 0>=free_1 ], cost: 10
35.13/24.20	
35.13/24.20	     58: evalserpentcritedge1in -> evalserpentcritedge1in : B'=-1+B, C'=1+A, D'=C, F'=-1+B, G'=1+A, H'=free_1, [ B>=0 && 0>=1+C && A>=C && free_1>=1 ], cost: 12-5*C+5*A
35.13/24.20	
35.13/24.20	     59: evalserpentcritedge1in -> evalserpentcritedge1in : B'=-1+B, C'=1+A, D'=C, E'=free, F'=-1+B, G'=1+A, H'=free_1, [ B>=0 && C>=0 && 0>=free && A>=C && free_1>=1 ], cost: 15-5*C+5*A
35.13/24.20	
35.13/24.20	     60: evalserpentcritedge1in -> evalserpentcritedge1in : B'=-1+B, C'=-1, D'=-1, E'=free, F'=-1+B, G'=-1, [ B>=0 && C>=0 && free>=1 && -1>=1+A ], cost: 12+5*C
35.13/24.20	
35.13/24.20	     61: evalserpentcritedge1in -> evalserpentcritedge1in : B'=-1+B, C'=-1, D'=-1, E'=free, F'=-1+B, G'=-1, H'=free_1, [ B>=0 && C>=0 && free>=1 && A>=-1 && 0>=free_1 ], cost: 15+5*C
35.13/24.20	
35.13/24.20	     62: evalserpentcritedge1in -> evalserpentcritedge1in : B'=-1+B, C'=1+A, D'=-1, E'=free, F'=-1+B, G'=1+A, H'=free_1, [ B>=0 && C>=0 && free>=1 && A>=-1 && free_1>=1 ], cost: 22+5*C+5*A
35.13/24.20	
35.13/24.20	     63: evalserpentcritedge1in -> [24] : [ B>=0 && 0>=1+C && A>=C && free_1>=1 ], cost: 11-5*C+5*A
35.13/24.20	
35.13/24.20	     64: evalserpentcritedge1in -> [24] : [ B>=0 && C>=0 && 0>=free && A>=C && free_1>=1 ], cost: 14-5*C+5*A
35.13/24.20	
35.13/24.20	     65: evalserpentcritedge1in -> [24] : [ B>=0 && C>=0 && free>=1 && A>=-1 && free_1>=1 ], cost: 21+5*C+5*A
35.13/24.20	
35.13/24.20	
35.13/24.20	
35.13/24.20	Applied pruning (of leafs and parallel rules):
35.13/24.20	
35.13/24.20	   Start location: evalserpentstart
35.13/24.20	
35.13/24.20	     28: evalserpentstart -> evalserpentcritedge1in : B'=A, C'=A, [ A>=1 ], cost: 4
35.13/24.20	
35.13/24.20	     55: evalserpentcritedge1in -> [23] : [ B>=0 && C>=0 && free>=1 ], cost: 6+5*C
35.13/24.20	
35.13/24.20	     58: evalserpentcritedge1in -> evalserpentcritedge1in : B'=-1+B, C'=1+A, D'=C, F'=-1+B, G'=1+A, H'=free_1, [ B>=0 && 0>=1+C && A>=C && free_1>=1 ], cost: 12-5*C+5*A
35.13/24.20	
35.13/24.20	     59: evalserpentcritedge1in -> evalserpentcritedge1in : B'=-1+B, C'=1+A, D'=C, E'=free, F'=-1+B, G'=1+A, H'=free_1, [ B>=0 && C>=0 && 0>=free && A>=C && free_1>=1 ], cost: 15-5*C+5*A
35.13/24.20	
35.13/24.20	     60: evalserpentcritedge1in -> evalserpentcritedge1in : B'=-1+B, C'=-1, D'=-1, E'=free, F'=-1+B, G'=-1, [ B>=0 && C>=0 && free>=1 && -1>=1+A ], cost: 12+5*C
35.13/24.20	
35.13/24.20	     61: evalserpentcritedge1in -> evalserpentcritedge1in : B'=-1+B, C'=-1, D'=-1, E'=free, F'=-1+B, G'=-1, H'=free_1, [ B>=0 && C>=0 && free>=1 && A>=-1 && 0>=free_1 ], cost: 15+5*C
35.13/24.20	
35.13/24.20	     62: evalserpentcritedge1in -> evalserpentcritedge1in : B'=-1+B, C'=1+A, D'=-1, E'=free, F'=-1+B, G'=1+A, H'=free_1, [ B>=0 && C>=0 && free>=1 && A>=-1 && free_1>=1 ], cost: 22+5*C+5*A
35.13/24.20	
35.13/24.20	     63: evalserpentcritedge1in -> [24] : [ B>=0 && 0>=1+C && A>=C && free_1>=1 ], cost: 11-5*C+5*A
35.13/24.20	
35.13/24.20	     64: evalserpentcritedge1in -> [24] : [ B>=0 && C>=0 && 0>=free && A>=C && free_1>=1 ], cost: 14-5*C+5*A
35.13/24.20	
35.13/24.20	     65: evalserpentcritedge1in -> [24] : [ B>=0 && C>=0 && free>=1 && A>=-1 && free_1>=1 ], cost: 21+5*C+5*A
35.13/24.20	
35.13/24.20	
35.13/24.20	
35.13/24.20	Accelerating simple loops of location 4.
35.13/24.20	
35.13/24.20	   Accelerating the following rules:
35.13/24.20	
35.13/24.20	     58: evalserpentcritedge1in -> evalserpentcritedge1in : B'=-1+B, C'=1+A, D'=C, F'=-1+B, G'=1+A, H'=free_1, [ B>=0 && 0>=1+C && A>=C && free_1>=1 ], cost: 12-5*C+5*A
35.13/24.20	
35.13/24.20	     59: evalserpentcritedge1in -> evalserpentcritedge1in : B'=-1+B, C'=1+A, D'=C, E'=free, F'=-1+B, G'=1+A, H'=free_1, [ B>=0 && C>=0 && 0>=free && A>=C && free_1>=1 ], cost: 15-5*C+5*A
35.13/24.20	
35.13/24.20	     60: evalserpentcritedge1in -> evalserpentcritedge1in : B'=-1+B, C'=-1, D'=-1, E'=free, F'=-1+B, G'=-1, [ B>=0 && C>=0 && free>=1 && -1>=1+A ], cost: 12+5*C
35.13/24.20	
35.13/24.20	     61: evalserpentcritedge1in -> evalserpentcritedge1in : B'=-1+B, C'=-1, D'=-1, E'=free, F'=-1+B, G'=-1, H'=free_1, [ B>=0 && C>=0 && free>=1 && A>=-1 && 0>=free_1 ], cost: 15+5*C
35.13/24.20	
35.13/24.20	     62: evalserpentcritedge1in -> evalserpentcritedge1in : B'=-1+B, C'=1+A, D'=-1, E'=free, F'=-1+B, G'=1+A, H'=free_1, [ B>=0 && C>=0 && free>=1 && A>=-1 && free_1>=1 ], cost: 22+5*C+5*A
35.13/24.20	
35.13/24.20	
35.13/24.20	
35.13/24.20	   Found no metering function for rule 58.
35.13/24.20	
35.13/24.20	   Found no metering function for rule 59.
35.13/24.20	
35.13/24.20	   Found no metering function for rule 60.
35.13/24.20	
35.13/24.20	   Found no metering function for rule 61.
35.13/24.20	
35.13/24.20	   Accelerated rule 62 with metering function 1+B, yielding the new rule 66.
35.13/24.20	
35.13/24.20	   Removing the simple loops: 62.
35.13/24.20	
35.13/24.20	
35.13/24.20	
35.13/24.20	Accelerated all simple loops using metering functions (where possible):
35.13/24.20	
35.13/24.20	   Start location: evalserpentstart
35.13/24.20	
35.13/24.20	     28: evalserpentstart -> evalserpentcritedge1in : B'=A, C'=A, [ A>=1 ], cost: 4
35.13/24.20	
35.13/24.20	     55: evalserpentcritedge1in -> [23] : [ B>=0 && C>=0 && free>=1 ], cost: 6+5*C
35.13/24.20	
35.13/24.20	     58: evalserpentcritedge1in -> evalserpentcritedge1in : B'=-1+B, C'=1+A, D'=C, F'=-1+B, G'=1+A, H'=free_1, [ B>=0 && 0>=1+C && A>=C && free_1>=1 ], cost: 12-5*C+5*A
35.13/24.20	
35.13/24.20	     59: evalserpentcritedge1in -> evalserpentcritedge1in : B'=-1+B, C'=1+A, D'=C, E'=free, F'=-1+B, G'=1+A, H'=free_1, [ B>=0 && C>=0 && 0>=free && A>=C && free_1>=1 ], cost: 15-5*C+5*A
35.13/24.20	
35.13/24.20	     60: evalserpentcritedge1in -> evalserpentcritedge1in : B'=-1+B, C'=-1, D'=-1, E'=free, F'=-1+B, G'=-1, [ B>=0 && C>=0 && free>=1 && -1>=1+A ], cost: 12+5*C
35.13/24.20	
35.13/24.20	     61: evalserpentcritedge1in -> evalserpentcritedge1in : B'=-1+B, C'=-1, D'=-1, E'=free, F'=-1+B, G'=-1, H'=free_1, [ B>=0 && C>=0 && free>=1 && A>=-1 && 0>=free_1 ], cost: 15+5*C
35.13/24.20	
35.13/24.20	     63: evalserpentcritedge1in -> [24] : [ B>=0 && 0>=1+C && A>=C && free_1>=1 ], cost: 11-5*C+5*A
35.13/24.20	
35.13/24.20	     64: evalserpentcritedge1in -> [24] : [ B>=0 && C>=0 && 0>=free && A>=C && free_1>=1 ], cost: 14-5*C+5*A
35.13/24.20	
35.13/24.20	     65: evalserpentcritedge1in -> [24] : [ B>=0 && C>=0 && free>=1 && A>=-1 && free_1>=1 ], cost: 21+5*C+5*A
35.13/24.20	
35.13/24.20	     66: evalserpentcritedge1in -> evalserpentcritedge1in : B'=-1, C'=1+A, D'=-1, E'=free, F'=-1, G'=1+A, H'=free_1, [ B>=0 && C>=0 && free>=1 && A>=-1 && free_1>=1 ], cost: 27+10*(1+B)*A+27*B
35.13/24.20	
35.13/24.20	
35.13/24.20	
35.13/24.20	Chained accelerated rules (with incoming rules):
35.13/24.20	
35.13/24.20	   Start location: evalserpentstart
35.13/24.20	
35.13/24.20	     28: evalserpentstart -> evalserpentcritedge1in : B'=A, C'=A, [ A>=1 ], cost: 4
35.13/24.20	
35.13/24.20	     67: evalserpentstart -> evalserpentcritedge1in : B'=-1+A, C'=1+A, D'=A, E'=free, F'=-1+A, G'=1+A, H'=free_1, [ A>=1 && 0>=free && free_1>=1 ], cost: 19
35.13/24.20	
35.13/24.20	     68: evalserpentstart -> evalserpentcritedge1in : B'=-1+A, C'=-1, D'=-1, E'=free, F'=-1+A, G'=-1, H'=free_1, [ A>=1 && free>=1 && 0>=free_1 ], cost: 19+5*A
35.13/24.20	
35.13/24.20	     69: evalserpentstart -> evalserpentcritedge1in : B'=-1, C'=1+A, D'=-1, E'=free, F'=-1, G'=1+A, H'=free_1, [ A>=1 && free>=1 && free_1>=1 ], cost: 31+27*A+10*A*(1+A)
35.13/24.20	
35.13/24.20	     55: evalserpentcritedge1in -> [23] : [ B>=0 && C>=0 && free>=1 ], cost: 6+5*C
35.13/24.20	
35.13/24.20	     63: evalserpentcritedge1in -> [24] : [ B>=0 && 0>=1+C && A>=C && free_1>=1 ], cost: 11-5*C+5*A
35.13/24.20	
35.13/24.20	     64: evalserpentcritedge1in -> [24] : [ B>=0 && C>=0 && 0>=free && A>=C && free_1>=1 ], cost: 14-5*C+5*A
35.13/24.20	
35.13/24.20	     65: evalserpentcritedge1in -> [24] : [ B>=0 && C>=0 && free>=1 && A>=-1 && free_1>=1 ], cost: 21+5*C+5*A
35.13/24.20	
35.13/24.20	
35.13/24.20	
35.13/24.20	Eliminated locations (on tree-shaped paths):
35.13/24.20	
35.13/24.20	   Start location: evalserpentstart
35.13/24.20	
35.13/24.20	     70: evalserpentstart -> [23] : B'=A, C'=A, [ A>=1 && free>=1 ], cost: 10+5*A
35.13/24.20	
35.13/24.20	     71: evalserpentstart -> [24] : B'=A, C'=A, [ A>=1 && 0>=free && free_1>=1 ], cost: 18
35.13/24.20	
35.13/24.20	     72: evalserpentstart -> [24] : B'=A, C'=A, [ A>=1 && free>=1 && free_1>=1 ], cost: 25+10*A
35.13/24.20	
35.13/24.20	     73: evalserpentstart -> [26] : [ A>=1 && free>=1 && 0>=free_1 ], cost: 19+5*A
35.13/24.20	
35.13/24.20	     74: evalserpentstart -> [26] : [ A>=1 && free>=1 && free_1>=1 ], cost: 31+27*A+10*A*(1+A)
35.13/24.20	
35.13/24.20	
35.13/24.20	
35.13/24.20	Applied pruning (of leafs and parallel rules):
35.13/24.20	
35.13/24.20	   Start location: evalserpentstart
35.13/24.20	
35.13/24.20	     70: evalserpentstart -> [23] : B'=A, C'=A, [ A>=1 && free>=1 ], cost: 10+5*A
35.13/24.20	
35.13/24.20	     72: evalserpentstart -> [24] : B'=A, C'=A, [ A>=1 && free>=1 && free_1>=1 ], cost: 25+10*A
35.13/24.20	
35.13/24.20	     73: evalserpentstart -> [26] : [ A>=1 && free>=1 && 0>=free_1 ], cost: 19+5*A
35.13/24.20	
35.13/24.20	     74: evalserpentstart -> [26] : [ A>=1 && free>=1 && free_1>=1 ], cost: 31+27*A+10*A*(1+A)
35.13/24.20	
35.13/24.20	
35.13/24.20	
35.13/24.20	### Computing asymptotic complexity ###
35.13/24.20	
35.13/24.20	
35.13/24.20	
35.13/24.20	Fully simplified ITS problem
35.13/24.20	
35.13/24.20	   Start location: evalserpentstart
35.13/24.20	
35.13/24.20	     70: evalserpentstart -> [23] : B'=A, C'=A, [ A>=1 && free>=1 ], cost: 10+5*A
35.13/24.20	
35.13/24.20	     72: evalserpentstart -> [24] : B'=A, C'=A, [ A>=1 && free>=1 && free_1>=1 ], cost: 25+10*A
35.13/24.20	
35.13/24.20	     73: evalserpentstart -> [26] : [ A>=1 && free>=1 && 0>=free_1 ], cost: 19+5*A
35.13/24.20	
35.13/24.20	     74: evalserpentstart -> [26] : [ A>=1 && free>=1 && free_1>=1 ], cost: 31+27*A+10*A*(1+A)
35.13/24.20	
35.13/24.20	
35.13/24.20	
35.13/24.20	Computing asymptotic complexity for rule 70
35.13/24.20	
35.13/24.20	   Solved the limit problem by the following transformations:
35.13/24.20	
35.13/24.20	      Created initial limit problem:
35.13/24.20	
35.13/24.20	      free (+/+!), 10+5*A (+), A (+/+!) [not solved]
35.13/24.20	
35.13/24.20	
35.13/24.20	
35.13/24.20	      removing all constraints (solved by SMT)
35.13/24.20	
35.13/24.20	      resulting limit problem: [solved]
35.13/24.20	
35.13/24.20	
35.13/24.20	
35.13/24.20	      applying transformation rule (C) using substitution {free==1,A==n}
35.13/24.20	
35.13/24.20	      resulting limit problem:
35.13/24.20	
35.13/24.20	      [solved]
35.13/24.20	
35.13/24.20	
35.13/24.20	
35.13/24.20	   Solution:
35.13/24.20	
35.13/24.20	      free / 1
35.13/24.20	
35.13/24.20	      A / n
35.13/24.20	
35.13/24.20	   Resulting cost 10+5*n has complexity: Poly(n^1)
35.13/24.20	
35.13/24.20	
35.13/24.20	
35.13/24.20	Found new complexity Poly(n^1).
35.13/24.20	
35.13/24.20	
35.13/24.20	
35.13/24.20	Computing asymptotic complexity for rule 74
35.13/24.20	
35.13/24.20	   Solved the limit problem by the following transformations:
35.13/24.20	
35.13/24.20	      Created initial limit problem:
35.13/24.20	
35.13/24.20	      31+37*A+10*A^2 (+), free (+/+!), A (+/+!), free_1 (+/+!) [not solved]
35.13/24.20	
35.13/24.20	
35.13/24.20	
35.13/24.20	      removing all constraints (solved by SMT)
35.13/24.20	
35.13/24.20	      resulting limit problem: [solved]
35.13/24.20	
35.13/24.20	
35.13/24.20	
35.13/24.20	      applying transformation rule (C) using substitution {free==n,A==n,free_1==1}
35.13/24.20	
35.13/24.20	      resulting limit problem:
35.13/24.20	
35.13/24.20	      [solved]
35.13/24.20	
35.13/24.20	
35.13/24.20	
35.13/24.20	   Solution:
35.13/24.20	
35.13/24.20	      free / n
35.13/24.20	
35.13/24.20	      A / n
35.13/24.20	
35.13/24.20	      free_1 / 1
35.13/24.20	
35.13/24.20	   Resulting cost 31+37*n+10*n^2 has complexity: Poly(n^2)
35.13/24.20	
35.13/24.20	
35.13/24.20	
35.13/24.20	Found new complexity Poly(n^2).
35.13/24.20	
35.13/24.20	
35.13/24.20	
35.13/24.20	Obtained the following overall complexity (w.r.t. the length of the input n):
35.13/24.20	
35.13/24.20	   Complexity:  Poly(n^2)
35.13/24.20	
35.13/24.20	   Cpx degree:  2
35.13/24.20	
35.13/24.20	   Solved cost: 31+37*n+10*n^2
35.13/24.20	
35.13/24.20	   Rule cost:   31+27*A+10*A*(1+A)
35.13/24.20	
35.13/24.20	   Rule guard:  [ A>=1 && free>=1 && free_1>=1 ]
35.13/24.20	
35.13/24.20	
35.13/24.20	
35.13/24.20	WORST_CASE(Omega(n^2),?)
35.13/24.20	
35.13/24.20	
35.13/24.20	----------------------------------------
35.13/24.20	
35.13/24.20	(2)
35.13/24.20	BOUNDS(n^2, INF)
35.13/24.24	EOF