3.31/1.71	WORST_CASE(?, O(1))
3.31/1.72	proof of /export/starexec/sandbox/benchmark/theBenchmark.koat
3.31/1.72	# AProVE Commit ID: 48fb2092695e11cc9f56e44b17a92a5f88ffb256 marcel 20180622 unpublished dirty
3.31/1.72	
3.31/1.72	
3.31/1.72	The runtime complexity of the given CpxIntTrs could be proven to be BOUNDS(1, 1).
3.31/1.72	
3.31/1.72	(0) CpxIntTrs
3.31/1.72	(1) Koat Proof [FINISHED, 12 ms]
3.31/1.72	(2) BOUNDS(1, 1)
3.31/1.72	
3.31/1.72	
3.31/1.72	----------------------------------------
3.31/1.72	
3.31/1.72	(0)
3.31/1.72	Obligation:
3.31/1.72	Complexity Int TRS consisting of the following rules:
3.31/1.72	eval_nd_loop_start(v_0, v_x_0) -> Com_1(eval_nd_loop_bb0_in(v_0, v_x_0)) :|: TRUE
3.31/1.72	eval_nd_loop_bb0_in(v_0, v_x_0) -> Com_1(eval_nd_loop_0(v_0, v_x_0)) :|: TRUE
3.31/1.72	eval_nd_loop_0(v_0, v_x_0) -> Com_1(eval_nd_loop_1(v_0, v_x_0)) :|: TRUE
3.31/1.72	eval_nd_loop_1(v_0, v_x_0) -> Com_1(eval_nd_loop_2(v_0, v_x_0)) :|: TRUE
3.31/1.72	eval_nd_loop_2(v_0, v_x_0) -> Com_1(eval_nd_loop_3(v_0, v_x_0)) :|: TRUE
3.31/1.72	eval_nd_loop_3(v_0, v_x_0) -> Com_1(eval_nd_loop_bb1_in(v_0, 0)) :|: TRUE
3.31/1.72	eval_nd_loop_bb1_in(v_0, v_x_0) -> Com_1(eval_nd_loop_4(v_0, v_x_0)) :|: TRUE
3.31/1.72	eval_nd_loop_4(v_0, v_x_0) -> Com_1(eval_nd_loop_5(nondef_0, v_x_0)) :|: TRUE
3.31/1.72	eval_nd_loop_5(v_0, v_x_0) -> Com_1(eval_nd_loop_bb1_in(v_0, v_0)) :|: v_0 - v_x_0 <= 2 && v_0 - v_x_0 >= 1 && v_0 < 10
3.31/1.72	eval_nd_loop_5(v_0, v_x_0) -> Com_1(eval_nd_loop_bb2_in(v_0, v_x_0)) :|: v_0 - v_x_0 > 2
3.31/1.72	eval_nd_loop_5(v_0, v_x_0) -> Com_1(eval_nd_loop_bb2_in(v_0, v_x_0)) :|: v_0 - v_x_0 < 1
3.31/1.72	eval_nd_loop_5(v_0, v_x_0) -> Com_1(eval_nd_loop_bb2_in(v_0, v_x_0)) :|: v_0 >= 10
3.31/1.72	eval_nd_loop_bb2_in(v_0, v_x_0) -> Com_1(eval_nd_loop_stop(v_0, v_x_0)) :|: TRUE
3.31/1.72	
3.31/1.72	The start-symbols are:[eval_nd_loop_start_2]
3.31/1.72	
3.31/1.72	
3.31/1.72	----------------------------------------
3.31/1.72	
3.31/1.72	(1) Koat Proof (FINISHED)
3.31/1.72	YES(?, 43)
3.31/1.72	
3.31/1.72	
3.31/1.72	
3.31/1.72	Initial complexity problem:
3.31/1.72	
3.31/1.72	1:	T:
3.31/1.72	
3.31/1.72			(Comp: ?, Cost: 1)    evalndloopstart(ar_0, ar_1) -> Com_1(evalndloopbb0in(ar_0, ar_1))
3.31/1.72	
3.31/1.72			(Comp: ?, Cost: 1)    evalndloopbb0in(ar_0, ar_1) -> Com_1(evalndloop0(ar_0, ar_1))
3.31/1.72	
3.31/1.72			(Comp: ?, Cost: 1)    evalndloop0(ar_0, ar_1) -> Com_1(evalndloop1(ar_0, ar_1))
3.31/1.72	
3.31/1.72			(Comp: ?, Cost: 1)    evalndloop1(ar_0, ar_1) -> Com_1(evalndloop2(ar_0, ar_1))
3.31/1.72	
3.31/1.72			(Comp: ?, Cost: 1)    evalndloop2(ar_0, ar_1) -> Com_1(evalndloop3(ar_0, ar_1))
3.31/1.72	
3.31/1.72			(Comp: ?, Cost: 1)    evalndloop3(ar_0, ar_1) -> Com_1(evalndloopbb1in(0, ar_1))
3.31/1.72	
3.31/1.72			(Comp: ?, Cost: 1)    evalndloopbb1in(ar_0, ar_1) -> Com_1(evalndloop4(ar_0, ar_1))
3.31/1.72	
3.31/1.72			(Comp: ?, Cost: 1)    evalndloop4(ar_0, ar_1) -> Com_1(evalndloop5(ar_0, c))
3.31/1.72	
3.31/1.72			(Comp: ?, Cost: 1)    evalndloop5(ar_0, ar_1) -> Com_1(evalndloopbb1in(ar_1, ar_1)) [ ar_0 + 2 >= ar_1 /\ ar_1 >= ar_0 + 1 /\ 9 >= ar_1 ]
3.31/1.72	
3.31/1.72			(Comp: ?, Cost: 1)    evalndloop5(ar_0, ar_1) -> Com_1(evalndloopbb2in(ar_0, ar_1)) [ ar_1 >= ar_0 + 3 ]
3.31/1.72	
3.31/1.72			(Comp: ?, Cost: 1)    evalndloop5(ar_0, ar_1) -> Com_1(evalndloopbb2in(ar_0, ar_1)) [ ar_0 >= ar_1 ]
3.31/1.72	
3.31/1.72			(Comp: ?, Cost: 1)    evalndloop5(ar_0, ar_1) -> Com_1(evalndloopbb2in(ar_0, ar_1)) [ ar_1 >= 10 ]
3.31/1.72	
3.31/1.72			(Comp: ?, Cost: 1)    evalndloopbb2in(ar_0, ar_1) -> Com_1(evalndloopstop(ar_0, ar_1))
3.31/1.72	
3.31/1.72			(Comp: 1, Cost: 0)    koat_start(ar_0, ar_1) -> Com_1(evalndloopstart(ar_0, ar_1)) [ 0 <= 0 ]
3.31/1.72	
3.31/1.72		start location:	koat_start
3.31/1.72	
3.31/1.72		leaf cost:	0
3.31/1.72	
3.31/1.72	
3.31/1.72	
3.31/1.72	Repeatedly propagating knowledge in problem 1 produces the following problem:
3.31/1.72	
3.31/1.72	2:	T:
3.31/1.72	
3.31/1.72			(Comp: 1, Cost: 1)    evalndloopstart(ar_0, ar_1) -> Com_1(evalndloopbb0in(ar_0, ar_1))
3.31/1.72	
3.31/1.72			(Comp: 1, Cost: 1)    evalndloopbb0in(ar_0, ar_1) -> Com_1(evalndloop0(ar_0, ar_1))
3.31/1.72	
3.31/1.72			(Comp: 1, Cost: 1)    evalndloop0(ar_0, ar_1) -> Com_1(evalndloop1(ar_0, ar_1))
3.31/1.72	
3.31/1.72			(Comp: 1, Cost: 1)    evalndloop1(ar_0, ar_1) -> Com_1(evalndloop2(ar_0, ar_1))
3.31/1.72	
3.31/1.72			(Comp: 1, Cost: 1)    evalndloop2(ar_0, ar_1) -> Com_1(evalndloop3(ar_0, ar_1))
3.31/1.72	
3.31/1.72			(Comp: 1, Cost: 1)    evalndloop3(ar_0, ar_1) -> Com_1(evalndloopbb1in(0, ar_1))
3.31/1.72	
3.31/1.72			(Comp: ?, Cost: 1)    evalndloopbb1in(ar_0, ar_1) -> Com_1(evalndloop4(ar_0, ar_1))
3.31/1.72	
3.31/1.72			(Comp: ?, Cost: 1)    evalndloop4(ar_0, ar_1) -> Com_1(evalndloop5(ar_0, c))
3.31/1.72	
3.31/1.72			(Comp: ?, Cost: 1)    evalndloop5(ar_0, ar_1) -> Com_1(evalndloopbb1in(ar_1, ar_1)) [ ar_0 + 2 >= ar_1 /\ ar_1 >= ar_0 + 1 /\ 9 >= ar_1 ]
3.31/1.72	
3.31/1.72			(Comp: ?, Cost: 1)    evalndloop5(ar_0, ar_1) -> Com_1(evalndloopbb2in(ar_0, ar_1)) [ ar_1 >= ar_0 + 3 ]
3.31/1.72	
3.31/1.72			(Comp: ?, Cost: 1)    evalndloop5(ar_0, ar_1) -> Com_1(evalndloopbb2in(ar_0, ar_1)) [ ar_0 >= ar_1 ]
3.31/1.72	
3.31/1.72			(Comp: ?, Cost: 1)    evalndloop5(ar_0, ar_1) -> Com_1(evalndloopbb2in(ar_0, ar_1)) [ ar_1 >= 10 ]
3.31/1.72	
3.31/1.72			(Comp: ?, Cost: 1)    evalndloopbb2in(ar_0, ar_1) -> Com_1(evalndloopstop(ar_0, ar_1))
3.31/1.72	
3.31/1.72			(Comp: 1, Cost: 0)    koat_start(ar_0, ar_1) -> Com_1(evalndloopstart(ar_0, ar_1)) [ 0 <= 0 ]
3.31/1.72	
3.31/1.72		start location:	koat_start
3.31/1.72	
3.31/1.72		leaf cost:	0
3.31/1.72	
3.31/1.72	
3.31/1.72	
3.31/1.72	A polynomial rank function with
3.31/1.72	
3.31/1.72		Pol(evalndloopstart) = 2
3.31/1.72	
3.31/1.72		Pol(evalndloopbb0in) = 2
3.31/1.72	
3.31/1.72		Pol(evalndloop0) = 2
3.31/1.72	
3.31/1.72		Pol(evalndloop1) = 2
3.31/1.72	
3.31/1.72		Pol(evalndloop2) = 2
3.31/1.72	
3.31/1.72		Pol(evalndloop3) = 2
3.31/1.72	
3.31/1.72		Pol(evalndloopbb1in) = 2
3.31/1.72	
3.31/1.72		Pol(evalndloop4) = 2
3.31/1.72	
3.31/1.72		Pol(evalndloop5) = 2
3.31/1.72	
3.31/1.72		Pol(evalndloopbb2in) = 1
3.31/1.72	
3.31/1.72		Pol(evalndloopstop) = 0
3.31/1.72	
3.31/1.72		Pol(koat_start) = 2
3.31/1.72	
3.31/1.72	orients all transitions weakly and the transitions
3.31/1.72	
3.31/1.72		evalndloopbb2in(ar_0, ar_1) -> Com_1(evalndloopstop(ar_0, ar_1))
3.31/1.72	
3.31/1.72		evalndloop5(ar_0, ar_1) -> Com_1(evalndloopbb2in(ar_0, ar_1)) [ ar_1 >= 10 ]
3.31/1.72	
3.31/1.72		evalndloop5(ar_0, ar_1) -> Com_1(evalndloopbb2in(ar_0, ar_1)) [ ar_1 >= ar_0 + 3 ]
3.31/1.72	
3.31/1.72		evalndloop5(ar_0, ar_1) -> Com_1(evalndloopbb2in(ar_0, ar_1)) [ ar_0 >= ar_1 ]
3.31/1.72	
3.31/1.72	strictly and produces the following problem:
3.31/1.72	
3.31/1.72	3:	T:
3.31/1.72	
3.31/1.72			(Comp: 1, Cost: 1)    evalndloopstart(ar_0, ar_1) -> Com_1(evalndloopbb0in(ar_0, ar_1))
3.31/1.72	
3.31/1.72			(Comp: 1, Cost: 1)    evalndloopbb0in(ar_0, ar_1) -> Com_1(evalndloop0(ar_0, ar_1))
3.31/1.72	
3.31/1.72			(Comp: 1, Cost: 1)    evalndloop0(ar_0, ar_1) -> Com_1(evalndloop1(ar_0, ar_1))
3.31/1.72	
3.31/1.72			(Comp: 1, Cost: 1)    evalndloop1(ar_0, ar_1) -> Com_1(evalndloop2(ar_0, ar_1))
3.31/1.72	
3.31/1.72			(Comp: 1, Cost: 1)    evalndloop2(ar_0, ar_1) -> Com_1(evalndloop3(ar_0, ar_1))
3.31/1.72	
3.31/1.72			(Comp: 1, Cost: 1)    evalndloop3(ar_0, ar_1) -> Com_1(evalndloopbb1in(0, ar_1))
3.31/1.72	
3.31/1.72			(Comp: ?, Cost: 1)    evalndloopbb1in(ar_0, ar_1) -> Com_1(evalndloop4(ar_0, ar_1))
3.31/1.72	
3.31/1.72			(Comp: ?, Cost: 1)    evalndloop4(ar_0, ar_1) -> Com_1(evalndloop5(ar_0, c))
3.31/1.72	
3.31/1.72			(Comp: ?, Cost: 1)    evalndloop5(ar_0, ar_1) -> Com_1(evalndloopbb1in(ar_1, ar_1)) [ ar_0 + 2 >= ar_1 /\ ar_1 >= ar_0 + 1 /\ 9 >= ar_1 ]
3.31/1.72	
3.31/1.72			(Comp: 2, Cost: 1)    evalndloop5(ar_0, ar_1) -> Com_1(evalndloopbb2in(ar_0, ar_1)) [ ar_1 >= ar_0 + 3 ]
3.31/1.72	
3.31/1.72			(Comp: 2, Cost: 1)    evalndloop5(ar_0, ar_1) -> Com_1(evalndloopbb2in(ar_0, ar_1)) [ ar_0 >= ar_1 ]
3.31/1.72	
3.31/1.72			(Comp: 2, Cost: 1)    evalndloop5(ar_0, ar_1) -> Com_1(evalndloopbb2in(ar_0, ar_1)) [ ar_1 >= 10 ]
3.31/1.72	
3.31/1.72			(Comp: 2, Cost: 1)    evalndloopbb2in(ar_0, ar_1) -> Com_1(evalndloopstop(ar_0, ar_1))
3.31/1.72	
3.31/1.72			(Comp: 1, Cost: 0)    koat_start(ar_0, ar_1) -> Com_1(evalndloopstart(ar_0, ar_1)) [ 0 <= 0 ]
3.31/1.72	
3.31/1.72		start location:	koat_start
3.31/1.72	
3.31/1.72		leaf cost:	0
3.31/1.72	
3.31/1.72	
3.31/1.72	
3.31/1.72	A polynomial rank function with
3.31/1.72	
3.31/1.72		Pol(evalndloopstart) = 9
3.31/1.72	
3.31/1.72		Pol(evalndloopbb0in) = 9
3.31/1.72	
3.31/1.72		Pol(evalndloop0) = 9
3.31/1.72	
3.31/1.72		Pol(evalndloop1) = 9
3.31/1.72	
3.31/1.72		Pol(evalndloop2) = 9
3.31/1.72	
3.31/1.72		Pol(evalndloop3) = 9
3.31/1.72	
3.31/1.72		Pol(evalndloopbb1in) = -V_1 + 9
3.31/1.72	
3.31/1.72		Pol(evalndloop4) = -V_1 + 9
3.31/1.72	
3.31/1.72		Pol(evalndloop5) = -V_1 + 9
3.31/1.72	
3.31/1.72		Pol(evalndloopbb2in) = -V_1
3.31/1.72	
3.31/1.72		Pol(evalndloopstop) = -V_1
3.31/1.72	
3.31/1.72		Pol(koat_start) = 9
3.31/1.72	
3.31/1.72	orients all transitions weakly and the transition
3.31/1.72	
3.31/1.72		evalndloop5(ar_0, ar_1) -> Com_1(evalndloopbb1in(ar_1, ar_1)) [ ar_0 + 2 >= ar_1 /\ ar_1 >= ar_0 + 1 /\ 9 >= ar_1 ]
3.31/1.72	
3.31/1.72	strictly and produces the following problem:
3.31/1.72	
3.31/1.72	4:	T:
3.31/1.72	
3.31/1.72			(Comp: 1, Cost: 1)    evalndloopstart(ar_0, ar_1) -> Com_1(evalndloopbb0in(ar_0, ar_1))
3.31/1.72	
3.31/1.72			(Comp: 1, Cost: 1)    evalndloopbb0in(ar_0, ar_1) -> Com_1(evalndloop0(ar_0, ar_1))
3.31/1.72	
3.31/1.72			(Comp: 1, Cost: 1)    evalndloop0(ar_0, ar_1) -> Com_1(evalndloop1(ar_0, ar_1))
3.31/1.72	
3.31/1.72			(Comp: 1, Cost: 1)    evalndloop1(ar_0, ar_1) -> Com_1(evalndloop2(ar_0, ar_1))
3.31/1.72	
3.31/1.72			(Comp: 1, Cost: 1)    evalndloop2(ar_0, ar_1) -> Com_1(evalndloop3(ar_0, ar_1))
3.31/1.72	
3.31/1.72			(Comp: 1, Cost: 1)    evalndloop3(ar_0, ar_1) -> Com_1(evalndloopbb1in(0, ar_1))
3.31/1.72	
3.31/1.72			(Comp: ?, Cost: 1)    evalndloopbb1in(ar_0, ar_1) -> Com_1(evalndloop4(ar_0, ar_1))
3.31/1.72	
3.31/1.72			(Comp: ?, Cost: 1)    evalndloop4(ar_0, ar_1) -> Com_1(evalndloop5(ar_0, c))
3.31/1.72	
3.31/1.72			(Comp: 9, Cost: 1)    evalndloop5(ar_0, ar_1) -> Com_1(evalndloopbb1in(ar_1, ar_1)) [ ar_0 + 2 >= ar_1 /\ ar_1 >= ar_0 + 1 /\ 9 >= ar_1 ]
3.31/1.72	
3.31/1.72			(Comp: 2, Cost: 1)    evalndloop5(ar_0, ar_1) -> Com_1(evalndloopbb2in(ar_0, ar_1)) [ ar_1 >= ar_0 + 3 ]
3.31/1.72	
3.31/1.72			(Comp: 2, Cost: 1)    evalndloop5(ar_0, ar_1) -> Com_1(evalndloopbb2in(ar_0, ar_1)) [ ar_0 >= ar_1 ]
3.31/1.72	
3.31/1.72			(Comp: 2, Cost: 1)    evalndloop5(ar_0, ar_1) -> Com_1(evalndloopbb2in(ar_0, ar_1)) [ ar_1 >= 10 ]
3.31/1.72	
3.31/1.72			(Comp: 2, Cost: 1)    evalndloopbb2in(ar_0, ar_1) -> Com_1(evalndloopstop(ar_0, ar_1))
3.31/1.72	
3.31/1.72			(Comp: 1, Cost: 0)    koat_start(ar_0, ar_1) -> Com_1(evalndloopstart(ar_0, ar_1)) [ 0 <= 0 ]
3.31/1.72	
3.31/1.72		start location:	koat_start
3.31/1.72	
3.31/1.72		leaf cost:	0
3.31/1.72	
3.31/1.72	
3.31/1.72	
3.31/1.72	Repeatedly propagating knowledge in problem 4 produces the following problem:
3.31/1.72	
3.31/1.72	5:	T:
3.31/1.72	
3.31/1.72			(Comp: 1, Cost: 1)     evalndloopstart(ar_0, ar_1) -> Com_1(evalndloopbb0in(ar_0, ar_1))
3.31/1.72	
3.31/1.72			(Comp: 1, Cost: 1)     evalndloopbb0in(ar_0, ar_1) -> Com_1(evalndloop0(ar_0, ar_1))
3.31/1.72	
3.31/1.72			(Comp: 1, Cost: 1)     evalndloop0(ar_0, ar_1) -> Com_1(evalndloop1(ar_0, ar_1))
3.31/1.72	
3.31/1.72			(Comp: 1, Cost: 1)     evalndloop1(ar_0, ar_1) -> Com_1(evalndloop2(ar_0, ar_1))
3.31/1.72	
3.31/1.72			(Comp: 1, Cost: 1)     evalndloop2(ar_0, ar_1) -> Com_1(evalndloop3(ar_0, ar_1))
3.31/1.72	
3.31/1.72			(Comp: 1, Cost: 1)     evalndloop3(ar_0, ar_1) -> Com_1(evalndloopbb1in(0, ar_1))
3.31/1.72	
3.31/1.72			(Comp: 10, Cost: 1)    evalndloopbb1in(ar_0, ar_1) -> Com_1(evalndloop4(ar_0, ar_1))
3.31/1.72	
3.31/1.72			(Comp: 10, Cost: 1)    evalndloop4(ar_0, ar_1) -> Com_1(evalndloop5(ar_0, c))
3.31/1.72	
3.31/1.72			(Comp: 9, Cost: 1)     evalndloop5(ar_0, ar_1) -> Com_1(evalndloopbb1in(ar_1, ar_1)) [ ar_0 + 2 >= ar_1 /\ ar_1 >= ar_0 + 1 /\ 9 >= ar_1 ]
3.31/1.72	
3.31/1.72			(Comp: 2, Cost: 1)     evalndloop5(ar_0, ar_1) -> Com_1(evalndloopbb2in(ar_0, ar_1)) [ ar_1 >= ar_0 + 3 ]
3.31/1.72	
3.31/1.72			(Comp: 2, Cost: 1)     evalndloop5(ar_0, ar_1) -> Com_1(evalndloopbb2in(ar_0, ar_1)) [ ar_0 >= ar_1 ]
3.31/1.72	
3.31/1.72			(Comp: 2, Cost: 1)     evalndloop5(ar_0, ar_1) -> Com_1(evalndloopbb2in(ar_0, ar_1)) [ ar_1 >= 10 ]
3.31/1.72	
3.31/1.72			(Comp: 2, Cost: 1)     evalndloopbb2in(ar_0, ar_1) -> Com_1(evalndloopstop(ar_0, ar_1))
3.31/1.72	
3.31/1.72			(Comp: 1, Cost: 0)     koat_start(ar_0, ar_1) -> Com_1(evalndloopstart(ar_0, ar_1)) [ 0 <= 0 ]
3.31/1.72	
3.31/1.72		start location:	koat_start
3.31/1.72	
3.31/1.72		leaf cost:	0
3.31/1.72	
3.31/1.72	
3.31/1.72	
3.31/1.72	Complexity upper bound 43
3.31/1.72	
3.31/1.72	
3.31/1.72	
3.31/1.72	Time: 0.065 sec (SMT: 0.056 sec)
3.31/1.72	
3.31/1.72	
3.31/1.72	----------------------------------------
3.31/1.72	
3.31/1.72	(2)
3.31/1.72	BOUNDS(1, 1)
3.31/1.74	EOF