5.46/2.62	WORST_CASE(Omega(n^1), O(n^1))
5.46/2.63	proof of /export/starexec/sandbox/benchmark/theBenchmark.koat
5.46/2.63	# AProVE Commit ID: 48fb2092695e11cc9f56e44b17a92a5f88ffb256 marcel 20180622 unpublished dirty
5.46/2.63	
5.46/2.63	
5.46/2.63	The runtime complexity of the given CpxIntTrs could be proven to be BOUNDS(n^1, n^1).
5.46/2.63	
5.46/2.63	(0) CpxIntTrs
5.46/2.63	(1) Koat Proof [FINISHED, 127 ms]
5.46/2.63	(2) BOUNDS(1, n^1)
5.46/2.63	(3) Loat Proof [FINISHED, 937 ms]
5.46/2.63	(4) BOUNDS(n^1, INF)
5.46/2.63	
5.46/2.63	
5.46/2.63	----------------------------------------
5.46/2.63	
5.46/2.63	(0)
5.46/2.63	Obligation:
5.46/2.63	Complexity Int TRS consisting of the following rules:
5.46/2.63	eval_start_start(v__0, v__0_sink, v_1, v_3, v_n) -> Com_1(eval_start_bb0_in(v__0, v__0_sink, v_1, v_3, v_n)) :|: TRUE
5.46/2.63	eval_start_bb0_in(v__0, v__0_sink, v_1, v_3, v_n) -> Com_1(eval_start_0(v__0, v__0_sink, v_1, v_3, v_n)) :|: TRUE
5.46/2.63	eval_start_0(v__0, v__0_sink, v_1, v_3, v_n) -> Com_1(eval_start_1(v__0, v__0_sink, v_1, v_3, v_n)) :|: TRUE
5.46/2.63	eval_start_1(v__0, v__0_sink, v_1, v_3, v_n) -> Com_1(eval_start_2(v__0, v__0_sink, v_1, v_3, v_n)) :|: TRUE
5.46/2.63	eval_start_2(v__0, v__0_sink, v_1, v_3, v_n) -> Com_1(eval_start_bb1_in(v_n, v__0_sink, v_1, v_3, v_n)) :|: TRUE
5.46/2.63	eval_start_bb1_in(v__0, v__0_sink, v_1, v_3, v_n) -> Com_1(eval_start_bb2_in(v__0, v__0, v_1, v_3, v_n)) :|: v__0 > 0
5.46/2.63	eval_start_bb1_in(v__0, v__0_sink, v_1, v_3, v_n) -> Com_1(eval_start_bb4_in(v__0, v__0_sink, v_1, v_3, v_n)) :|: v__0 <= 0
5.46/2.63	eval_start_bb2_in(v__0, v__0_sink, v_1, v_3, v_n) -> Com_1(eval_start_bb3_in(v__0, v__0_sink, v__0_sink - 1, v_3, v_n)) :|: v__0_sink - 1 > 0
5.46/2.63	eval_start_bb2_in(v__0, v__0_sink, v_1, v_3, v_n) -> Com_1(eval_start_bb1_in(v__0_sink - 1, v__0_sink, v_1, v_3, v_n)) :|: v__0_sink - 1 <= 0
5.46/2.63	eval_start_bb3_in(v__0, v__0_sink, v_1, v_3, v_n) -> Com_1(eval_start_5(v__0, v__0_sink, v_1, v_3, v_n)) :|: TRUE
5.46/2.63	eval_start_5(v__0, v__0_sink, v_1, v_3, v_n) -> Com_1(eval_start_6(v__0, v__0_sink, v_1, nondef_0, v_n)) :|: TRUE
5.46/2.63	eval_start_6(v__0, v__0_sink, v_1, v_3, v_n) -> Com_1(eval_start_bb1_in(v_1, v__0_sink, v_1, v_3, v_n)) :|: v_3 > 0
5.46/2.63	eval_start_6(v__0, v__0_sink, v_1, v_3, v_n) -> Com_1(eval_start_bb2_in(v__0, v_1, v_1, v_3, v_n)) :|: v_3 <= 0
5.46/2.63	eval_start_bb4_in(v__0, v__0_sink, v_1, v_3, v_n) -> Com_1(eval_start_stop(v__0, v__0_sink, v_1, v_3, v_n)) :|: TRUE
5.46/2.63	
5.46/2.63	The start-symbols are:[eval_start_start_5]
5.46/2.63	
5.46/2.63	
5.46/2.63	----------------------------------------
5.46/2.63	
5.46/2.63	(1) Koat Proof (FINISHED)
5.46/2.63	YES(?, 16*ar_1 + 9)
5.46/2.63	
5.46/2.63	
5.46/2.63	
5.46/2.63	Initial complexity problem:
5.46/2.63	
5.46/2.63	1:	T:
5.46/2.63	
5.46/2.63			(Comp: ?, Cost: 1)    evalstartstart(ar_0, ar_1, ar_2, ar_3, ar_4) -> Com_1(evalstartbb0in(ar_0, ar_1, ar_2, ar_3, ar_4))
5.46/2.63	
5.46/2.63			(Comp: ?, Cost: 1)    evalstartbb0in(ar_0, ar_1, ar_2, ar_3, ar_4) -> Com_1(evalstart0(ar_0, ar_1, ar_2, ar_3, ar_4))
5.46/2.63	
5.46/2.63			(Comp: ?, Cost: 1)    evalstart0(ar_0, ar_1, ar_2, ar_3, ar_4) -> Com_1(evalstart1(ar_0, ar_1, ar_2, ar_3, ar_4))
5.46/2.63	
5.46/2.63			(Comp: ?, Cost: 1)    evalstart1(ar_0, ar_1, ar_2, ar_3, ar_4) -> Com_1(evalstart2(ar_0, ar_1, ar_2, ar_3, ar_4))
5.46/2.63	
5.46/2.63			(Comp: ?, Cost: 1)    evalstart2(ar_0, ar_1, ar_2, ar_3, ar_4) -> Com_1(evalstartbb1in(ar_1, ar_1, ar_2, ar_3, ar_4))
5.46/2.63	
5.46/2.63			(Comp: ?, Cost: 1)    evalstartbb1in(ar_0, ar_1, ar_2, ar_3, ar_4) -> Com_1(evalstartbb2in(ar_0, ar_1, ar_0, ar_3, ar_4)) [ ar_0 >= 1 ]
5.46/2.63	
5.46/2.63			(Comp: ?, Cost: 1)    evalstartbb1in(ar_0, ar_1, ar_2, ar_3, ar_4) -> Com_1(evalstartbb4in(ar_0, ar_1, ar_2, ar_3, ar_4)) [ 0 >= ar_0 ]
5.46/2.63	
5.46/2.63			(Comp: ?, Cost: 1)    evalstartbb2in(ar_0, ar_1, ar_2, ar_3, ar_4) -> Com_1(evalstartbb3in(ar_0, ar_1, ar_2, ar_2 - 1, ar_4)) [ ar_2 >= 2 ]
5.46/2.63	
5.46/2.63			(Comp: ?, Cost: 1)    evalstartbb2in(ar_0, ar_1, ar_2, ar_3, ar_4) -> Com_1(evalstartbb1in(ar_2 - 1, ar_1, ar_2, ar_3, ar_4)) [ 1 >= ar_2 ]
5.46/2.63	
5.46/2.63			(Comp: ?, Cost: 1)    evalstartbb3in(ar_0, ar_1, ar_2, ar_3, ar_4) -> Com_1(evalstart5(ar_0, ar_1, ar_2, ar_3, ar_4))
5.46/2.63	
5.46/2.63			(Comp: ?, Cost: 1)    evalstart5(ar_0, ar_1, ar_2, ar_3, ar_4) -> Com_1(evalstart6(ar_0, ar_1, ar_2, ar_3, f))
5.46/2.63	
5.46/2.63			(Comp: ?, Cost: 1)    evalstart6(ar_0, ar_1, ar_2, ar_3, ar_4) -> Com_1(evalstartbb1in(ar_3, ar_1, ar_2, ar_3, ar_4)) [ ar_4 >= 1 ]
5.46/2.63	
5.46/2.63			(Comp: ?, Cost: 1)    evalstart6(ar_0, ar_1, ar_2, ar_3, ar_4) -> Com_1(evalstartbb2in(ar_0, ar_1, ar_3, ar_3, ar_4)) [ 0 >= ar_4 ]
5.46/2.63	
5.46/2.63			(Comp: ?, Cost: 1)    evalstartbb4in(ar_0, ar_1, ar_2, ar_3, ar_4) -> Com_1(evalstartstop(ar_0, ar_1, ar_2, ar_3, ar_4))
5.46/2.63	
5.46/2.63			(Comp: 1, Cost: 0)    koat_start(ar_0, ar_1, ar_2, ar_3, ar_4) -> Com_1(evalstartstart(ar_0, ar_1, ar_2, ar_3, ar_4)) [ 0 <= 0 ]
5.46/2.63	
5.46/2.63		start location:	koat_start
5.46/2.63	
5.46/2.63		leaf cost:	0
5.46/2.63	
5.46/2.63	
5.46/2.63	
5.46/2.63	Repeatedly propagating knowledge in problem 1 produces the following problem:
5.46/2.63	
5.46/2.63	2:	T:
5.46/2.63	
5.46/2.63			(Comp: 1, Cost: 1)    evalstartstart(ar_0, ar_1, ar_2, ar_3, ar_4) -> Com_1(evalstartbb0in(ar_0, ar_1, ar_2, ar_3, ar_4))
5.46/2.63	
5.46/2.63			(Comp: 1, Cost: 1)    evalstartbb0in(ar_0, ar_1, ar_2, ar_3, ar_4) -> Com_1(evalstart0(ar_0, ar_1, ar_2, ar_3, ar_4))
5.46/2.63	
5.46/2.63			(Comp: 1, Cost: 1)    evalstart0(ar_0, ar_1, ar_2, ar_3, ar_4) -> Com_1(evalstart1(ar_0, ar_1, ar_2, ar_3, ar_4))
5.46/2.63	
5.46/2.63			(Comp: 1, Cost: 1)    evalstart1(ar_0, ar_1, ar_2, ar_3, ar_4) -> Com_1(evalstart2(ar_0, ar_1, ar_2, ar_3, ar_4))
5.46/2.63	
5.46/2.63			(Comp: 1, Cost: 1)    evalstart2(ar_0, ar_1, ar_2, ar_3, ar_4) -> Com_1(evalstartbb1in(ar_1, ar_1, ar_2, ar_3, ar_4))
5.46/2.63	
5.46/2.63			(Comp: ?, Cost: 1)    evalstartbb1in(ar_0, ar_1, ar_2, ar_3, ar_4) -> Com_1(evalstartbb2in(ar_0, ar_1, ar_0, ar_3, ar_4)) [ ar_0 >= 1 ]
5.46/2.63	
5.46/2.63			(Comp: ?, Cost: 1)    evalstartbb1in(ar_0, ar_1, ar_2, ar_3, ar_4) -> Com_1(evalstartbb4in(ar_0, ar_1, ar_2, ar_3, ar_4)) [ 0 >= ar_0 ]
5.46/2.63	
5.46/2.63			(Comp: ?, Cost: 1)    evalstartbb2in(ar_0, ar_1, ar_2, ar_3, ar_4) -> Com_1(evalstartbb3in(ar_0, ar_1, ar_2, ar_2 - 1, ar_4)) [ ar_2 >= 2 ]
5.46/2.63	
5.46/2.63			(Comp: ?, Cost: 1)    evalstartbb2in(ar_0, ar_1, ar_2, ar_3, ar_4) -> Com_1(evalstartbb1in(ar_2 - 1, ar_1, ar_2, ar_3, ar_4)) [ 1 >= ar_2 ]
5.46/2.63	
5.46/2.63			(Comp: ?, Cost: 1)    evalstartbb3in(ar_0, ar_1, ar_2, ar_3, ar_4) -> Com_1(evalstart5(ar_0, ar_1, ar_2, ar_3, ar_4))
5.46/2.63	
5.46/2.63			(Comp: ?, Cost: 1)    evalstart5(ar_0, ar_1, ar_2, ar_3, ar_4) -> Com_1(evalstart6(ar_0, ar_1, ar_2, ar_3, f))
5.46/2.63	
5.46/2.63			(Comp: ?, Cost: 1)    evalstart6(ar_0, ar_1, ar_2, ar_3, ar_4) -> Com_1(evalstartbb1in(ar_3, ar_1, ar_2, ar_3, ar_4)) [ ar_4 >= 1 ]
5.46/2.63	
5.46/2.63			(Comp: ?, Cost: 1)    evalstart6(ar_0, ar_1, ar_2, ar_3, ar_4) -> Com_1(evalstartbb2in(ar_0, ar_1, ar_3, ar_3, ar_4)) [ 0 >= ar_4 ]
5.46/2.63	
5.46/2.63			(Comp: ?, Cost: 1)    evalstartbb4in(ar_0, ar_1, ar_2, ar_3, ar_4) -> Com_1(evalstartstop(ar_0, ar_1, ar_2, ar_3, ar_4))
5.46/2.63	
5.46/2.63			(Comp: 1, Cost: 0)    koat_start(ar_0, ar_1, ar_2, ar_3, ar_4) -> Com_1(evalstartstart(ar_0, ar_1, ar_2, ar_3, ar_4)) [ 0 <= 0 ]
5.46/2.63	
5.46/2.63		start location:	koat_start
5.46/2.63	
5.46/2.63		leaf cost:	0
5.46/2.63	
5.46/2.63	
5.46/2.63	
5.46/2.63	A polynomial rank function with
5.46/2.63	
5.46/2.63		Pol(evalstartstart) = 2
5.46/2.63	
5.46/2.63		Pol(evalstartbb0in) = 2
5.46/2.63	
5.46/2.63		Pol(evalstart0) = 2
5.46/2.63	
5.46/2.63		Pol(evalstart1) = 2
5.46/2.63	
5.46/2.63		Pol(evalstart2) = 2
5.46/2.63	
5.46/2.63		Pol(evalstartbb1in) = 2
5.46/2.63	
5.46/2.63		Pol(evalstartbb2in) = 2
5.46/2.63	
5.46/2.63		Pol(evalstartbb4in) = 1
5.46/2.63	
5.46/2.63		Pol(evalstartbb3in) = 2
5.46/2.63	
5.46/2.63		Pol(evalstart5) = 2
5.46/2.63	
5.46/2.63		Pol(evalstart6) = 2
5.46/2.63	
5.46/2.63		Pol(evalstartstop) = 0
5.46/2.63	
5.46/2.63		Pol(koat_start) = 2
5.46/2.63	
5.46/2.63	orients all transitions weakly and the transitions
5.46/2.63	
5.46/2.63		evalstartbb4in(ar_0, ar_1, ar_2, ar_3, ar_4) -> Com_1(evalstartstop(ar_0, ar_1, ar_2, ar_3, ar_4))
5.46/2.63	
5.46/2.63		evalstartbb1in(ar_0, ar_1, ar_2, ar_3, ar_4) -> Com_1(evalstartbb4in(ar_0, ar_1, ar_2, ar_3, ar_4)) [ 0 >= ar_0 ]
5.46/2.63	
5.46/2.63	strictly and produces the following problem:
5.46/2.63	
5.46/2.63	3:	T:
5.46/2.63	
5.46/2.63			(Comp: 1, Cost: 1)    evalstartstart(ar_0, ar_1, ar_2, ar_3, ar_4) -> Com_1(evalstartbb0in(ar_0, ar_1, ar_2, ar_3, ar_4))
5.46/2.63	
5.46/2.63			(Comp: 1, Cost: 1)    evalstartbb0in(ar_0, ar_1, ar_2, ar_3, ar_4) -> Com_1(evalstart0(ar_0, ar_1, ar_2, ar_3, ar_4))
5.46/2.63	
5.46/2.63			(Comp: 1, Cost: 1)    evalstart0(ar_0, ar_1, ar_2, ar_3, ar_4) -> Com_1(evalstart1(ar_0, ar_1, ar_2, ar_3, ar_4))
5.46/2.63	
5.46/2.63			(Comp: 1, Cost: 1)    evalstart1(ar_0, ar_1, ar_2, ar_3, ar_4) -> Com_1(evalstart2(ar_0, ar_1, ar_2, ar_3, ar_4))
5.46/2.63	
5.46/2.63			(Comp: 1, Cost: 1)    evalstart2(ar_0, ar_1, ar_2, ar_3, ar_4) -> Com_1(evalstartbb1in(ar_1, ar_1, ar_2, ar_3, ar_4))
5.46/2.63	
5.46/2.63			(Comp: ?, Cost: 1)    evalstartbb1in(ar_0, ar_1, ar_2, ar_3, ar_4) -> Com_1(evalstartbb2in(ar_0, ar_1, ar_0, ar_3, ar_4)) [ ar_0 >= 1 ]
5.46/2.63	
5.46/2.63			(Comp: 2, Cost: 1)    evalstartbb1in(ar_0, ar_1, ar_2, ar_3, ar_4) -> Com_1(evalstartbb4in(ar_0, ar_1, ar_2, ar_3, ar_4)) [ 0 >= ar_0 ]
5.46/2.63	
5.46/2.63			(Comp: ?, Cost: 1)    evalstartbb2in(ar_0, ar_1, ar_2, ar_3, ar_4) -> Com_1(evalstartbb3in(ar_0, ar_1, ar_2, ar_2 - 1, ar_4)) [ ar_2 >= 2 ]
5.46/2.63	
5.46/2.63			(Comp: ?, Cost: 1)    evalstartbb2in(ar_0, ar_1, ar_2, ar_3, ar_4) -> Com_1(evalstartbb1in(ar_2 - 1, ar_1, ar_2, ar_3, ar_4)) [ 1 >= ar_2 ]
5.46/2.63	
5.46/2.63			(Comp: ?, Cost: 1)    evalstartbb3in(ar_0, ar_1, ar_2, ar_3, ar_4) -> Com_1(evalstart5(ar_0, ar_1, ar_2, ar_3, ar_4))
5.46/2.63	
5.46/2.63			(Comp: ?, Cost: 1)    evalstart5(ar_0, ar_1, ar_2, ar_3, ar_4) -> Com_1(evalstart6(ar_0, ar_1, ar_2, ar_3, f))
5.46/2.63	
5.46/2.63			(Comp: ?, Cost: 1)    evalstart6(ar_0, ar_1, ar_2, ar_3, ar_4) -> Com_1(evalstartbb1in(ar_3, ar_1, ar_2, ar_3, ar_4)) [ ar_4 >= 1 ]
5.46/2.63	
5.46/2.63			(Comp: ?, Cost: 1)    evalstart6(ar_0, ar_1, ar_2, ar_3, ar_4) -> Com_1(evalstartbb2in(ar_0, ar_1, ar_3, ar_3, ar_4)) [ 0 >= ar_4 ]
5.46/2.63	
5.46/2.63			(Comp: 2, Cost: 1)    evalstartbb4in(ar_0, ar_1, ar_2, ar_3, ar_4) -> Com_1(evalstartstop(ar_0, ar_1, ar_2, ar_3, ar_4))
5.46/2.63	
5.46/2.63			(Comp: 1, Cost: 0)    koat_start(ar_0, ar_1, ar_2, ar_3, ar_4) -> Com_1(evalstartstart(ar_0, ar_1, ar_2, ar_3, ar_4)) [ 0 <= 0 ]
5.46/2.63	
5.46/2.63		start location:	koat_start
5.46/2.63	
5.46/2.63		leaf cost:	0
5.46/2.63	
5.46/2.63	
5.46/2.63	
5.46/2.63	A polynomial rank function with
5.46/2.63	
5.46/2.63		Pol(evalstartstart) = 2*V_2
5.46/2.63	
5.46/2.63		Pol(evalstartbb0in) = 2*V_2
5.46/2.63	
5.46/2.63		Pol(evalstart0) = 2*V_2
5.46/2.63	
5.46/2.63		Pol(evalstart1) = 2*V_2
5.46/2.63	
5.46/2.63		Pol(evalstart2) = 2*V_2
5.46/2.63	
5.46/2.63		Pol(evalstartbb1in) = 2*V_1
5.46/2.63	
5.46/2.63		Pol(evalstartbb2in) = 2*V_3 - 1
5.46/2.63	
5.46/2.63		Pol(evalstartbb4in) = 2*V_1
5.46/2.63	
5.46/2.63		Pol(evalstartbb3in) = 2*V_4
5.46/2.63	
5.46/2.63		Pol(evalstart5) = 2*V_4
5.46/2.63	
5.46/2.63		Pol(evalstart6) = 2*V_4
5.46/2.63	
5.46/2.63		Pol(evalstartstop) = 2*V_1
5.46/2.63	
5.46/2.63		Pol(koat_start) = 2*V_2
5.46/2.63	
5.46/2.63	orients all transitions weakly and the transitions
5.46/2.63	
5.46/2.63		evalstartbb2in(ar_0, ar_1, ar_2, ar_3, ar_4) -> Com_1(evalstartbb3in(ar_0, ar_1, ar_2, ar_2 - 1, ar_4)) [ ar_2 >= 2 ]
5.46/2.63	
5.46/2.63		evalstartbb1in(ar_0, ar_1, ar_2, ar_3, ar_4) -> Com_1(evalstartbb2in(ar_0, ar_1, ar_0, ar_3, ar_4)) [ ar_0 >= 1 ]
5.46/2.63	
5.46/2.63	strictly and produces the following problem:
5.46/2.63	
5.46/2.63	4:	T:
5.46/2.63	
5.46/2.63			(Comp: 1, Cost: 1)         evalstartstart(ar_0, ar_1, ar_2, ar_3, ar_4) -> Com_1(evalstartbb0in(ar_0, ar_1, ar_2, ar_3, ar_4))
5.46/2.63	
5.46/2.63			(Comp: 1, Cost: 1)         evalstartbb0in(ar_0, ar_1, ar_2, ar_3, ar_4) -> Com_1(evalstart0(ar_0, ar_1, ar_2, ar_3, ar_4))
5.46/2.63	
5.46/2.63			(Comp: 1, Cost: 1)         evalstart0(ar_0, ar_1, ar_2, ar_3, ar_4) -> Com_1(evalstart1(ar_0, ar_1, ar_2, ar_3, ar_4))
5.46/2.63	
5.46/2.63			(Comp: 1, Cost: 1)         evalstart1(ar_0, ar_1, ar_2, ar_3, ar_4) -> Com_1(evalstart2(ar_0, ar_1, ar_2, ar_3, ar_4))
5.46/2.63	
5.46/2.63			(Comp: 1, Cost: 1)         evalstart2(ar_0, ar_1, ar_2, ar_3, ar_4) -> Com_1(evalstartbb1in(ar_1, ar_1, ar_2, ar_3, ar_4))
5.46/2.63	
5.46/2.63			(Comp: 2*ar_1, Cost: 1)    evalstartbb1in(ar_0, ar_1, ar_2, ar_3, ar_4) -> Com_1(evalstartbb2in(ar_0, ar_1, ar_0, ar_3, ar_4)) [ ar_0 >= 1 ]
5.46/2.63	
5.46/2.63			(Comp: 2, Cost: 1)         evalstartbb1in(ar_0, ar_1, ar_2, ar_3, ar_4) -> Com_1(evalstartbb4in(ar_0, ar_1, ar_2, ar_3, ar_4)) [ 0 >= ar_0 ]
5.46/2.63	
5.46/2.63			(Comp: 2*ar_1, Cost: 1)    evalstartbb2in(ar_0, ar_1, ar_2, ar_3, ar_4) -> Com_1(evalstartbb3in(ar_0, ar_1, ar_2, ar_2 - 1, ar_4)) [ ar_2 >= 2 ]
5.46/2.63	
5.46/2.63			(Comp: ?, Cost: 1)         evalstartbb2in(ar_0, ar_1, ar_2, ar_3, ar_4) -> Com_1(evalstartbb1in(ar_2 - 1, ar_1, ar_2, ar_3, ar_4)) [ 1 >= ar_2 ]
5.46/2.63	
5.46/2.63			(Comp: ?, Cost: 1)         evalstartbb3in(ar_0, ar_1, ar_2, ar_3, ar_4) -> Com_1(evalstart5(ar_0, ar_1, ar_2, ar_3, ar_4))
5.46/2.63	
5.46/2.63			(Comp: ?, Cost: 1)         evalstart5(ar_0, ar_1, ar_2, ar_3, ar_4) -> Com_1(evalstart6(ar_0, ar_1, ar_2, ar_3, f))
5.46/2.63	
5.46/2.63			(Comp: ?, Cost: 1)         evalstart6(ar_0, ar_1, ar_2, ar_3, ar_4) -> Com_1(evalstartbb1in(ar_3, ar_1, ar_2, ar_3, ar_4)) [ ar_4 >= 1 ]
5.46/2.63	
5.46/2.63			(Comp: ?, Cost: 1)         evalstart6(ar_0, ar_1, ar_2, ar_3, ar_4) -> Com_1(evalstartbb2in(ar_0, ar_1, ar_3, ar_3, ar_4)) [ 0 >= ar_4 ]
5.46/2.63	
5.46/2.63			(Comp: 2, Cost: 1)         evalstartbb4in(ar_0, ar_1, ar_2, ar_3, ar_4) -> Com_1(evalstartstop(ar_0, ar_1, ar_2, ar_3, ar_4))
5.46/2.63	
5.46/2.63			(Comp: 1, Cost: 0)         koat_start(ar_0, ar_1, ar_2, ar_3, ar_4) -> Com_1(evalstartstart(ar_0, ar_1, ar_2, ar_3, ar_4)) [ 0 <= 0 ]
5.46/2.63	
5.46/2.63		start location:	koat_start
5.46/2.63	
5.46/2.63		leaf cost:	0
5.46/2.63	
5.46/2.63	
5.46/2.63	
5.46/2.63	Repeatedly propagating knowledge in problem 4 produces the following problem:
5.46/2.63	
5.46/2.63	5:	T:
5.46/2.63	
5.46/2.63			(Comp: 1, Cost: 1)         evalstartstart(ar_0, ar_1, ar_2, ar_3, ar_4) -> Com_1(evalstartbb0in(ar_0, ar_1, ar_2, ar_3, ar_4))
5.46/2.63	
5.46/2.63			(Comp: 1, Cost: 1)         evalstartbb0in(ar_0, ar_1, ar_2, ar_3, ar_4) -> Com_1(evalstart0(ar_0, ar_1, ar_2, ar_3, ar_4))
5.46/2.63	
5.46/2.63			(Comp: 1, Cost: 1)         evalstart0(ar_0, ar_1, ar_2, ar_3, ar_4) -> Com_1(evalstart1(ar_0, ar_1, ar_2, ar_3, ar_4))
5.46/2.63	
5.46/2.63			(Comp: 1, Cost: 1)         evalstart1(ar_0, ar_1, ar_2, ar_3, ar_4) -> Com_1(evalstart2(ar_0, ar_1, ar_2, ar_3, ar_4))
5.46/2.63	
5.46/2.63			(Comp: 1, Cost: 1)         evalstart2(ar_0, ar_1, ar_2, ar_3, ar_4) -> Com_1(evalstartbb1in(ar_1, ar_1, ar_2, ar_3, ar_4))
5.46/2.63	
5.46/2.63			(Comp: 2*ar_1, Cost: 1)    evalstartbb1in(ar_0, ar_1, ar_2, ar_3, ar_4) -> Com_1(evalstartbb2in(ar_0, ar_1, ar_0, ar_3, ar_4)) [ ar_0 >= 1 ]
5.46/2.63	
5.46/2.63			(Comp: 2, Cost: 1)         evalstartbb1in(ar_0, ar_1, ar_2, ar_3, ar_4) -> Com_1(evalstartbb4in(ar_0, ar_1, ar_2, ar_3, ar_4)) [ 0 >= ar_0 ]
5.46/2.63	
5.46/2.63			(Comp: 2*ar_1, Cost: 1)    evalstartbb2in(ar_0, ar_1, ar_2, ar_3, ar_4) -> Com_1(evalstartbb3in(ar_0, ar_1, ar_2, ar_2 - 1, ar_4)) [ ar_2 >= 2 ]
5.46/2.63	
5.46/2.63			(Comp: 4*ar_1, Cost: 1)    evalstartbb2in(ar_0, ar_1, ar_2, ar_3, ar_4) -> Com_1(evalstartbb1in(ar_2 - 1, ar_1, ar_2, ar_3, ar_4)) [ 1 >= ar_2 ]
5.46/2.63	
5.46/2.63			(Comp: 2*ar_1, Cost: 1)    evalstartbb3in(ar_0, ar_1, ar_2, ar_3, ar_4) -> Com_1(evalstart5(ar_0, ar_1, ar_2, ar_3, ar_4))
5.46/2.63	
5.46/2.63			(Comp: 2*ar_1, Cost: 1)    evalstart5(ar_0, ar_1, ar_2, ar_3, ar_4) -> Com_1(evalstart6(ar_0, ar_1, ar_2, ar_3, f))
5.46/2.63	
5.46/2.63			(Comp: 2*ar_1, Cost: 1)    evalstart6(ar_0, ar_1, ar_2, ar_3, ar_4) -> Com_1(evalstartbb1in(ar_3, ar_1, ar_2, ar_3, ar_4)) [ ar_4 >= 1 ]
5.46/2.63	
5.46/2.63			(Comp: 2*ar_1, Cost: 1)    evalstart6(ar_0, ar_1, ar_2, ar_3, ar_4) -> Com_1(evalstartbb2in(ar_0, ar_1, ar_3, ar_3, ar_4)) [ 0 >= ar_4 ]
5.46/2.63	
5.46/2.63			(Comp: 2, Cost: 1)         evalstartbb4in(ar_0, ar_1, ar_2, ar_3, ar_4) -> Com_1(evalstartstop(ar_0, ar_1, ar_2, ar_3, ar_4))
5.46/2.63	
5.46/2.63			(Comp: 1, Cost: 0)         koat_start(ar_0, ar_1, ar_2, ar_3, ar_4) -> Com_1(evalstartstart(ar_0, ar_1, ar_2, ar_3, ar_4)) [ 0 <= 0 ]
5.46/2.63	
5.46/2.63		start location:	koat_start
5.46/2.63	
5.46/2.63		leaf cost:	0
5.46/2.63	
5.46/2.63	
5.46/2.63	
5.46/2.63	Complexity upper bound 16*ar_1 + 9
5.46/2.63	
5.46/2.63	
5.46/2.63	
5.46/2.63	Time: 0.160 sec (SMT: 0.135 sec)
5.46/2.63	
5.46/2.63	
5.46/2.63	----------------------------------------
5.46/2.63	
5.46/2.63	(2)
5.46/2.63	BOUNDS(1, n^1)
5.46/2.63	
5.46/2.63	----------------------------------------
5.46/2.63	
5.46/2.63	(3) Loat Proof (FINISHED)
5.46/2.63	
5.46/2.63	
5.46/2.63	### Pre-processing the ITS problem ###
5.46/2.63	
5.46/2.63	
5.46/2.63	
5.46/2.63	Initial linear ITS problem
5.46/2.63	
5.46/2.63	   Start location: evalstartstart
5.46/2.63	
5.46/2.63	      0: evalstartstart -> evalstartbb0in : [], cost: 1
5.46/2.63	
5.46/2.63	      1: evalstartbb0in -> evalstart0 : [], cost: 1
5.46/2.63	
5.46/2.63	      2: evalstart0 -> evalstart1 : [], cost: 1
5.46/2.63	
5.46/2.63	      3: evalstart1 -> evalstart2 : [], cost: 1
5.46/2.63	
5.46/2.63	      4: evalstart2 -> evalstartbb1in : A'=B, [], cost: 1
5.46/2.63	
5.46/2.63	      5: evalstartbb1in -> evalstartbb2in : C'=A, [ A>=1 ], cost: 1
5.46/2.63	
5.46/2.63	      6: evalstartbb1in -> evalstartbb4in : [ 0>=A ], cost: 1
5.46/2.63	
5.46/2.63	      7: evalstartbb2in -> evalstartbb3in : D'=-1+C, [ C>=2 ], cost: 1
5.46/2.63	
5.46/2.63	      8: evalstartbb2in -> evalstartbb1in : A'=-1+C, [ 1>=C ], cost: 1
5.46/2.63	
5.46/2.63	      9: evalstartbb3in -> evalstart5 : [], cost: 1
5.46/2.63	
5.46/2.63	     10: evalstart5 -> evalstart6 : E'=free, [], cost: 1
5.46/2.63	
5.46/2.63	     11: evalstart6 -> evalstartbb1in : A'=D, [ E>=1 ], cost: 1
5.46/2.63	
5.46/2.63	     12: evalstart6 -> evalstartbb2in : C'=D, [ 0>=E ], cost: 1
5.46/2.63	
5.46/2.63	     13: evalstartbb4in -> evalstartstop : [], cost: 1
5.46/2.63	
5.46/2.63	
5.46/2.63	
5.46/2.63	Removed unreachable and leaf rules:
5.46/2.63	
5.46/2.63	   Start location: evalstartstart
5.46/2.63	
5.46/2.63	      0: evalstartstart -> evalstartbb0in : [], cost: 1
5.46/2.63	
5.46/2.63	      1: evalstartbb0in -> evalstart0 : [], cost: 1
5.46/2.63	
5.46/2.63	      2: evalstart0 -> evalstart1 : [], cost: 1
5.46/2.63	
5.46/2.63	      3: evalstart1 -> evalstart2 : [], cost: 1
5.46/2.63	
5.46/2.63	      4: evalstart2 -> evalstartbb1in : A'=B, [], cost: 1
5.46/2.63	
5.46/2.63	      5: evalstartbb1in -> evalstartbb2in : C'=A, [ A>=1 ], cost: 1
5.46/2.63	
5.46/2.63	      7: evalstartbb2in -> evalstartbb3in : D'=-1+C, [ C>=2 ], cost: 1
5.46/2.63	
5.46/2.63	      8: evalstartbb2in -> evalstartbb1in : A'=-1+C, [ 1>=C ], cost: 1
5.46/2.63	
5.46/2.63	      9: evalstartbb3in -> evalstart5 : [], cost: 1
5.46/2.63	
5.46/2.63	     10: evalstart5 -> evalstart6 : E'=free, [], cost: 1
5.46/2.63	
5.46/2.63	     11: evalstart6 -> evalstartbb1in : A'=D, [ E>=1 ], cost: 1
5.46/2.63	
5.46/2.63	     12: evalstart6 -> evalstartbb2in : C'=D, [ 0>=E ], cost: 1
5.46/2.63	
5.46/2.63	
5.46/2.63	
5.46/2.63	### Simplification by acceleration and chaining ###
5.46/2.63	
5.46/2.63	
5.46/2.63	
5.46/2.63	Eliminated locations (on linear paths):
5.46/2.63	
5.46/2.63	   Start location: evalstartstart
5.46/2.63	
5.46/2.63	     17: evalstartstart -> evalstartbb1in : A'=B, [], cost: 5
5.46/2.63	
5.46/2.63	      5: evalstartbb1in -> evalstartbb2in : C'=A, [ A>=1 ], cost: 1
5.46/2.63	
5.46/2.63	      8: evalstartbb2in -> evalstartbb1in : A'=-1+C, [ 1>=C ], cost: 1
5.46/2.63	
5.46/2.63	     19: evalstartbb2in -> evalstart6 : D'=-1+C, E'=free, [ C>=2 ], cost: 3
5.46/2.63	
5.46/2.63	     11: evalstart6 -> evalstartbb1in : A'=D, [ E>=1 ], cost: 1
5.46/2.63	
5.46/2.63	     12: evalstart6 -> evalstartbb2in : C'=D, [ 0>=E ], cost: 1
5.46/2.63	
5.46/2.63	
5.46/2.63	
5.46/2.63	Eliminated locations (on tree-shaped paths):
5.46/2.63	
5.46/2.63	   Start location: evalstartstart
5.46/2.63	
5.46/2.63	     17: evalstartstart -> evalstartbb1in : A'=B, [], cost: 5
5.46/2.63	
5.46/2.63	      5: evalstartbb1in -> evalstartbb2in : C'=A, [ A>=1 ], cost: 1
5.46/2.63	
5.46/2.63	      8: evalstartbb2in -> evalstartbb1in : A'=-1+C, [ 1>=C ], cost: 1
5.46/2.63	
5.46/2.63	     20: evalstartbb2in -> evalstartbb1in : A'=-1+C, D'=-1+C, E'=free, [ C>=2 && free>=1 ], cost: 4
5.46/2.63	
5.46/2.63	     21: evalstartbb2in -> evalstartbb2in : C'=-1+C, D'=-1+C, E'=free, [ C>=2 && 0>=free ], cost: 4
5.46/2.63	
5.46/2.63	
5.46/2.63	
5.46/2.63	Accelerating simple loops of location 6.
5.46/2.63	
5.46/2.63	   Accelerating the following rules:
5.46/2.63	
5.46/2.63	     21: evalstartbb2in -> evalstartbb2in : C'=-1+C, D'=-1+C, E'=free, [ C>=2 && 0>=free ], cost: 4
5.46/2.63	
5.46/2.63	
5.46/2.63	
5.46/2.63	   Accelerated rule 21 with metering function -1+C, yielding the new rule 22.
5.46/2.63	
5.46/2.63	   Removing the simple loops: 21.
5.46/2.63	
5.46/2.63	
5.46/2.63	
5.46/2.63	Accelerated all simple loops using metering functions (where possible):
5.46/2.63	
5.46/2.63	   Start location: evalstartstart
5.46/2.63	
5.46/2.63	     17: evalstartstart -> evalstartbb1in : A'=B, [], cost: 5
5.46/2.63	
5.46/2.63	      5: evalstartbb1in -> evalstartbb2in : C'=A, [ A>=1 ], cost: 1
5.46/2.63	
5.46/2.63	      8: evalstartbb2in -> evalstartbb1in : A'=-1+C, [ 1>=C ], cost: 1
5.46/2.63	
5.46/2.63	     20: evalstartbb2in -> evalstartbb1in : A'=-1+C, D'=-1+C, E'=free, [ C>=2 && free>=1 ], cost: 4
5.46/2.63	
5.46/2.63	     22: evalstartbb2in -> evalstartbb2in : C'=1, D'=1, E'=free, [ C>=2 && 0>=free ], cost: -4+4*C
5.46/2.63	
5.46/2.63	
5.46/2.63	
5.46/2.63	Chained accelerated rules (with incoming rules):
5.46/2.63	
5.46/2.63	   Start location: evalstartstart
5.46/2.63	
5.46/2.63	     17: evalstartstart -> evalstartbb1in : A'=B, [], cost: 5
5.46/2.63	
5.46/2.63	      5: evalstartbb1in -> evalstartbb2in : C'=A, [ A>=1 ], cost: 1
5.46/2.63	
5.46/2.63	     23: evalstartbb1in -> evalstartbb2in : C'=1, D'=1, E'=free, [ A>=2 && 0>=free ], cost: -3+4*A
5.46/2.63	
5.46/2.63	      8: evalstartbb2in -> evalstartbb1in : A'=-1+C, [ 1>=C ], cost: 1
5.46/2.63	
5.46/2.63	     20: evalstartbb2in -> evalstartbb1in : A'=-1+C, D'=-1+C, E'=free, [ C>=2 && free>=1 ], cost: 4
5.46/2.63	
5.46/2.63	
5.46/2.63	
5.46/2.63	Eliminated locations (on tree-shaped paths):
5.46/2.63	
5.46/2.63	   Start location: evalstartstart
5.46/2.63	
5.46/2.63	     17: evalstartstart -> evalstartbb1in : A'=B, [], cost: 5
5.46/2.63	
5.46/2.63	     24: evalstartbb1in -> evalstartbb1in : A'=-1+A, C'=A, [ A>=1 && 1>=A ], cost: 2
5.46/2.63	
5.46/2.63	     25: evalstartbb1in -> evalstartbb1in : A'=-1+A, C'=A, D'=-1+A, E'=free, [ A>=2 && free>=1 ], cost: 5
5.46/2.63	
5.46/2.63	     26: evalstartbb1in -> evalstartbb1in : A'=0, C'=1, D'=1, E'=free, [ A>=2 && 0>=free ], cost: -2+4*A
5.46/2.63	
5.46/2.63	     27: evalstartbb1in -> [13] : [ A>=2 && 0>=free ], cost: -3+4*A
5.46/2.63	
5.46/2.63	
5.46/2.63	
5.46/2.63	Accelerating simple loops of location 5.
5.46/2.63	
5.46/2.63	   Simplified some of the simple loops (and removed duplicate rules).
5.46/2.63	
5.46/2.63	   Accelerating the following rules:
5.46/2.63	
5.46/2.63	     24: evalstartbb1in -> evalstartbb1in : A'=-1+A, C'=A, [ 1-A==0 ], cost: 2
5.46/2.63	
5.46/2.63	     25: evalstartbb1in -> evalstartbb1in : A'=-1+A, C'=A, D'=-1+A, E'=free, [ A>=2 && free>=1 ], cost: 5
5.46/2.63	
5.46/2.63	     26: evalstartbb1in -> evalstartbb1in : A'=0, C'=1, D'=1, E'=free, [ A>=2 && 0>=free ], cost: -2+4*A
5.46/2.63	
5.46/2.63	
5.46/2.63	
5.46/2.63	   Accelerated rule 24 with metering function A, yielding the new rule 28.
5.46/2.63	
5.46/2.63	   Accelerated rule 25 with metering function -1+A, yielding the new rule 29.
5.46/2.63	
5.46/2.63	   Found no metering function for rule 26.
5.46/2.63	
5.46/2.63	   Removing the simple loops: 24 25.
5.46/2.63	
5.46/2.63	
5.46/2.63	
5.46/2.63	Accelerated all simple loops using metering functions (where possible):
5.46/2.63	
5.46/2.63	   Start location: evalstartstart
5.46/2.63	
5.46/2.63	     17: evalstartstart -> evalstartbb1in : A'=B, [], cost: 5
5.46/2.63	
5.46/2.63	     26: evalstartbb1in -> evalstartbb1in : A'=0, C'=1, D'=1, E'=free, [ A>=2 && 0>=free ], cost: -2+4*A
5.46/2.63	
5.46/2.63	     27: evalstartbb1in -> [13] : [ A>=2 && 0>=free ], cost: -3+4*A
5.46/2.63	
5.46/2.63	     28: evalstartbb1in -> evalstartbb1in : A'=0, C'=1, [ 1-A==0 ], cost: 2*A
5.46/2.63	
5.46/2.63	     29: evalstartbb1in -> evalstartbb1in : A'=1, C'=2, D'=1, E'=free, [ A>=2 && free>=1 ], cost: -5+5*A
5.46/2.63	
5.46/2.63	
5.46/2.63	
5.46/2.63	Chained accelerated rules (with incoming rules):
5.46/2.63	
5.46/2.63	   Start location: evalstartstart
5.46/2.63	
5.46/2.63	     17: evalstartstart -> evalstartbb1in : A'=B, [], cost: 5
5.46/2.63	
5.46/2.63	     30: evalstartstart -> evalstartbb1in : A'=0, C'=1, D'=1, E'=free, [ B>=2 && 0>=free ], cost: 3+4*B
5.46/2.63	
5.46/2.63	     31: evalstartstart -> evalstartbb1in : A'=0, C'=1, [ 1-B==0 ], cost: 5+2*B
5.46/2.63	
5.46/2.63	     32: evalstartstart -> evalstartbb1in : A'=1, C'=2, D'=1, E'=free, [ B>=2 && free>=1 ], cost: 5*B
5.46/2.63	
5.46/2.63	     27: evalstartbb1in -> [13] : [ A>=2 && 0>=free ], cost: -3+4*A
5.46/2.63	
5.46/2.63	
5.46/2.63	
5.46/2.63	Eliminated locations (on tree-shaped paths):
5.46/2.63	
5.46/2.63	   Start location: evalstartstart
5.46/2.63	
5.46/2.63	     33: evalstartstart -> [13] : A'=B, [ B>=2 && 0>=free ], cost: 2+4*B
5.46/2.63	
5.46/2.63	     34: evalstartstart -> [15] : [ B>=2 && 0>=free ], cost: 3+4*B
5.46/2.63	
5.46/2.63	     35: evalstartstart -> [15] : [ 1-B==0 ], cost: 5+2*B
5.46/2.63	
5.46/2.63	     36: evalstartstart -> [15] : [ B>=2 && free>=1 ], cost: 5*B
5.46/2.63	
5.46/2.63	
5.46/2.63	
5.46/2.63	### Computing asymptotic complexity ###
5.46/2.63	
5.46/2.63	
5.46/2.63	
5.46/2.63	Fully simplified ITS problem
5.46/2.63	
5.46/2.63	   Start location: evalstartstart
5.46/2.63	
5.46/2.63	     34: evalstartstart -> [15] : [ B>=2 && 0>=free ], cost: 3+4*B
5.46/2.63	
5.46/2.63	     35: evalstartstart -> [15] : [ 1-B==0 ], cost: 5+2*B
5.46/2.63	
5.46/2.63	     36: evalstartstart -> [15] : [ B>=2 && free>=1 ], cost: 5*B
5.46/2.63	
5.46/2.63	
5.46/2.63	
5.46/2.63	Computing asymptotic complexity for rule 34
5.46/2.63	
5.46/2.63	   Solved the limit problem by the following transformations:
5.46/2.63	
5.46/2.63	      Created initial limit problem:
5.46/2.63	
5.46/2.63	      1-free (+/+!), -1+B (+/+!), 3+4*B (+) [not solved]
5.46/2.63	
5.46/2.63	
5.46/2.63	
5.46/2.63	      removing all constraints (solved by SMT)
5.46/2.63	
5.46/2.63	      resulting limit problem: [solved]
5.46/2.63	
5.46/2.63	
5.46/2.63	
5.46/2.63	      applying transformation rule (C) using substitution {free==0,B==n}
5.46/2.63	
5.46/2.63	      resulting limit problem:
5.46/2.63	
5.46/2.63	      [solved]
5.46/2.63	
5.46/2.63	
5.46/2.63	
5.46/2.63	   Solution:
5.46/2.63	
5.46/2.63	      free / 0
5.46/2.63	
5.46/2.63	      B / n
5.46/2.63	
5.46/2.63	   Resulting cost 3+4*n has complexity: Poly(n^1)
5.46/2.63	
5.46/2.63	
5.46/2.63	
5.46/2.63	Found new complexity Poly(n^1).
5.46/2.63	
5.46/2.63	
5.46/2.63	
5.46/2.63	Obtained the following overall complexity (w.r.t. the length of the input n):
5.46/2.63	
5.46/2.63	   Complexity:  Poly(n^1)
5.46/2.63	
5.46/2.63	   Cpx degree:  1
5.46/2.63	
5.46/2.63	   Solved cost: 3+4*n
5.46/2.63	
5.46/2.63	   Rule cost:   3+4*B
5.46/2.63	
5.46/2.63	   Rule guard:  [ B>=2 && 0>=free ]
5.46/2.63	
5.46/2.63	
5.46/2.63	
5.46/2.63	WORST_CASE(Omega(n^1),?)
5.46/2.63	
5.46/2.63	
5.46/2.63	----------------------------------------
5.46/2.63	
5.46/2.63	(4)
5.46/2.63	BOUNDS(n^1, INF)
5.46/2.66	EOF