2.18/1.39	WORST_CASE(?, O(n^1))
2.18/1.40	proof of /export/starexec/sandbox/output/output_files/bench.koat
2.18/1.40	# AProVE Commit ID: 48fb2092695e11cc9f56e44b17a92a5f88ffb256 marcel 20180622 unpublished dirty
2.18/1.40	
2.18/1.40	
2.18/1.40	The runtime complexity of the given CpxIntTrs could be proven to be BOUNDS(1, n^1).
2.18/1.40	
2.18/1.40	(0) CpxIntTrs
2.18/1.40	(1) Koat Proof [FINISHED, 173 ms]
2.18/1.40	(2) BOUNDS(1, n^1)
2.18/1.40	
2.18/1.40	
2.18/1.40	----------------------------------------
2.18/1.40	
2.18/1.40	(0)
2.18/1.40	Obligation:
2.18/1.40	Complexity Int TRS consisting of the following rules:
2.18/1.40	eval_speedSingleSingle_start(v_n, v_x.0) -> Com_1(eval_speedSingleSingle_bb0_in(v_n, v_x.0)) :|: TRUE
2.18/1.40	eval_speedSingleSingle_bb0_in(v_n, v_x.0) -> Com_1(eval_speedSingleSingle_bb1_in(v_n, 0)) :|: TRUE
2.18/1.40	eval_speedSingleSingle_bb1_in(v_n, v_x.0) -> Com_1(eval_speedSingleSingle_bb2_in(v_n, v_x.0)) :|: v_x.0 < v_n
2.18/1.40	eval_speedSingleSingle_bb1_in(v_n, v_x.0) -> Com_1(eval_speedSingleSingle_bb3_in(v_n, v_x.0)) :|: v_x.0 >= v_n
2.18/1.40	eval_speedSingleSingle_bb2_in(v_n, v_x.0) -> Com_1(eval_speedSingleSingle_0(v_n, v_x.0)) :|: TRUE
2.18/1.40	eval_speedSingleSingle_0(v_n, v_x.0) -> Com_2(eval_nondet_start(v_n, v_x.0), eval_speedSingleSingle_1(v_n, v_x.0)) :|: TRUE
2.18/1.40	eval_speedSingleSingle_1(v_n, v_x.0) -> Com_1(eval_speedSingleSingle_bb1_in(v_n, v_x.0 + 1)) :|: TRUE
2.18/1.40	eval_speedSingleSingle_bb3_in(v_n, v_x.0) -> Com_1(eval_speedSingleSingle_stop(v_n, v_x.0)) :|: TRUE
2.18/1.40	
2.18/1.40	The start-symbols are:[eval_speedSingleSingle_start_2]
2.18/1.40	
2.18/1.40	
2.18/1.40	----------------------------------------
2.18/1.40	
2.18/1.40	(1) Koat Proof (FINISHED)
2.18/1.40	YES(?, 16*ar_1 + 6)
2.18/1.40	
2.18/1.40	
2.18/1.40	
2.18/1.40	Initial complexity problem:
2.18/1.40	
2.18/1.40	1:	T:
2.18/1.40	
2.18/1.40			(Comp: ?, Cost: 1)    evalspeedSingleSinglestart(ar_0, ar_1) -> Com_1(evalspeedSingleSinglebb0in(ar_0, ar_1))
2.18/1.40	
2.18/1.40			(Comp: ?, Cost: 1)    evalspeedSingleSinglebb0in(ar_0, ar_1) -> Com_1(evalspeedSingleSinglebb1in(0, ar_1))
2.18/1.40	
2.18/1.40			(Comp: ?, Cost: 1)    evalspeedSingleSinglebb1in(ar_0, ar_1) -> Com_1(evalspeedSingleSinglebb2in(ar_0, ar_1)) [ ar_1 >= ar_0 + 1 ]
2.18/1.40	
2.18/1.40			(Comp: ?, Cost: 1)    evalspeedSingleSinglebb1in(ar_0, ar_1) -> Com_1(evalspeedSingleSinglebb3in(ar_0, ar_1)) [ ar_0 >= ar_1 ]
2.18/1.40	
2.18/1.40			(Comp: ?, Cost: 1)    evalspeedSingleSinglebb2in(ar_0, ar_1) -> Com_1(evalspeedSingleSingle0(ar_0, ar_1))
2.18/1.40	
2.18/1.40			(Comp: ?, Cost: 1)    evalspeedSingleSingle0(ar_0, ar_1) -> Com_2(evalnondetstart(ar_0, ar_1), evalspeedSingleSingle1(ar_0, ar_1))
2.18/1.40	
2.18/1.40			(Comp: ?, Cost: 1)    evalspeedSingleSingle1(ar_0, ar_1) -> Com_1(evalspeedSingleSinglebb1in(ar_0 + 1, ar_1))
2.18/1.40	
2.18/1.40			(Comp: ?, Cost: 1)    evalspeedSingleSinglebb3in(ar_0, ar_1) -> Com_1(evalspeedSingleSinglestop(ar_0, ar_1))
2.18/1.40	
2.18/1.40			(Comp: 1, Cost: 0)    koat_start(ar_0, ar_1) -> Com_1(evalspeedSingleSinglestart(ar_0, ar_1)) [ 0 <= 0 ]
2.18/1.40	
2.18/1.40		start location:	koat_start
2.18/1.40	
2.18/1.40		leaf cost:	0
2.18/1.40	
2.18/1.40	
2.18/1.40	
2.18/1.40	Repeatedly propagating knowledge in problem 1 produces the following problem:
2.18/1.40	
2.18/1.40	2:	T:
2.18/1.40	
2.18/1.40			(Comp: 1, Cost: 1)    evalspeedSingleSinglestart(ar_0, ar_1) -> Com_1(evalspeedSingleSinglebb0in(ar_0, ar_1))
2.18/1.40	
2.18/1.40			(Comp: 1, Cost: 1)    evalspeedSingleSinglebb0in(ar_0, ar_1) -> Com_1(evalspeedSingleSinglebb1in(0, ar_1))
2.18/1.40	
2.18/1.40			(Comp: ?, Cost: 1)    evalspeedSingleSinglebb1in(ar_0, ar_1) -> Com_1(evalspeedSingleSinglebb2in(ar_0, ar_1)) [ ar_1 >= ar_0 + 1 ]
2.18/1.40	
2.18/1.40			(Comp: ?, Cost: 1)    evalspeedSingleSinglebb1in(ar_0, ar_1) -> Com_1(evalspeedSingleSinglebb3in(ar_0, ar_1)) [ ar_0 >= ar_1 ]
2.18/1.40	
2.18/1.40			(Comp: ?, Cost: 1)    evalspeedSingleSinglebb2in(ar_0, ar_1) -> Com_1(evalspeedSingleSingle0(ar_0, ar_1))
2.18/1.40	
2.18/1.40			(Comp: ?, Cost: 1)    evalspeedSingleSingle0(ar_0, ar_1) -> Com_2(evalnondetstart(ar_0, ar_1), evalspeedSingleSingle1(ar_0, ar_1))
2.18/1.40	
2.18/1.40			(Comp: ?, Cost: 1)    evalspeedSingleSingle1(ar_0, ar_1) -> Com_1(evalspeedSingleSinglebb1in(ar_0 + 1, ar_1))
2.18/1.40	
2.18/1.40			(Comp: ?, Cost: 1)    evalspeedSingleSinglebb3in(ar_0, ar_1) -> Com_1(evalspeedSingleSinglestop(ar_0, ar_1))
2.18/1.40	
2.18/1.40			(Comp: 1, Cost: 0)    koat_start(ar_0, ar_1) -> Com_1(evalspeedSingleSinglestart(ar_0, ar_1)) [ 0 <= 0 ]
2.18/1.40	
2.18/1.40		start location:	koat_start
2.18/1.40	
2.18/1.40		leaf cost:	0
2.18/1.40	
2.18/1.40	
2.18/1.40	
2.18/1.40	A polynomial rank function with
2.18/1.40	
2.18/1.40		Pol(evalspeedSingleSinglestart) = 2
2.18/1.40	
2.18/1.40		Pol(evalspeedSingleSinglebb0in) = 2
2.18/1.40	
2.18/1.40		Pol(evalspeedSingleSinglebb1in) = 2
2.18/1.40	
2.18/1.40		Pol(evalspeedSingleSinglebb2in) = 2
2.18/1.40	
2.18/1.40		Pol(evalspeedSingleSinglebb3in) = 1
2.18/1.40	
2.18/1.40		Pol(evalspeedSingleSingle0) = 2
2.18/1.40	
2.18/1.40		Pol(evalnondetstart) = 0
2.18/1.40	
2.18/1.40		Pol(evalspeedSingleSingle1) = 2
2.18/1.40	
2.18/1.40		Pol(evalspeedSingleSinglestop) = 0
2.18/1.40	
2.18/1.40		Pol(koat_start) = 2
2.18/1.40	
2.18/1.40	orients all transitions weakly and the transitions
2.18/1.40	
2.18/1.40		evalspeedSingleSinglebb3in(ar_0, ar_1) -> Com_1(evalspeedSingleSinglestop(ar_0, ar_1))
2.18/1.40	
2.18/1.40		evalspeedSingleSinglebb1in(ar_0, ar_1) -> Com_1(evalspeedSingleSinglebb3in(ar_0, ar_1)) [ ar_0 >= ar_1 ]
2.18/1.40	
2.18/1.40	strictly and produces the following problem:
2.18/1.40	
2.18/1.40	3:	T:
2.18/1.40	
2.18/1.40			(Comp: 1, Cost: 1)    evalspeedSingleSinglestart(ar_0, ar_1) -> Com_1(evalspeedSingleSinglebb0in(ar_0, ar_1))
2.18/1.40	
2.18/1.40			(Comp: 1, Cost: 1)    evalspeedSingleSinglebb0in(ar_0, ar_1) -> Com_1(evalspeedSingleSinglebb1in(0, ar_1))
2.18/1.40	
2.18/1.40			(Comp: ?, Cost: 1)    evalspeedSingleSinglebb1in(ar_0, ar_1) -> Com_1(evalspeedSingleSinglebb2in(ar_0, ar_1)) [ ar_1 >= ar_0 + 1 ]
2.18/1.40	
2.18/1.40			(Comp: 2, Cost: 1)    evalspeedSingleSinglebb1in(ar_0, ar_1) -> Com_1(evalspeedSingleSinglebb3in(ar_0, ar_1)) [ ar_0 >= ar_1 ]
2.18/1.40	
2.18/1.40			(Comp: ?, Cost: 1)    evalspeedSingleSinglebb2in(ar_0, ar_1) -> Com_1(evalspeedSingleSingle0(ar_0, ar_1))
2.18/1.40	
2.18/1.40			(Comp: ?, Cost: 1)    evalspeedSingleSingle0(ar_0, ar_1) -> Com_2(evalnondetstart(ar_0, ar_1), evalspeedSingleSingle1(ar_0, ar_1))
2.18/1.40	
2.18/1.40			(Comp: ?, Cost: 1)    evalspeedSingleSingle1(ar_0, ar_1) -> Com_1(evalspeedSingleSinglebb1in(ar_0 + 1, ar_1))
2.18/1.40	
2.18/1.40			(Comp: 2, Cost: 1)    evalspeedSingleSinglebb3in(ar_0, ar_1) -> Com_1(evalspeedSingleSinglestop(ar_0, ar_1))
2.18/1.40	
2.18/1.40			(Comp: 1, Cost: 0)    koat_start(ar_0, ar_1) -> Com_1(evalspeedSingleSinglestart(ar_0, ar_1)) [ 0 <= 0 ]
2.18/1.40	
2.18/1.40		start location:	koat_start
2.18/1.40	
2.18/1.40		leaf cost:	0
2.18/1.40	
2.18/1.40	
2.18/1.40	
2.18/1.40	Applied AI with 'oct' on problem 3 to obtain the following invariants:
2.18/1.40	
2.18/1.40	  For symbol evalspeedSingleSingle0: X_2 - 1 >= 0 /\ X_1 + X_2 - 1 >= 0 /\ -X_1 + X_2 - 1 >= 0 /\ X_1 >= 0
2.18/1.40	
2.18/1.40	  For symbol evalspeedSingleSingle1: X_2 - 1 >= 0 /\ X_1 + X_2 - 1 >= 0 /\ -X_1 + X_2 - 1 >= 0 /\ X_1 >= 0
2.18/1.40	
2.18/1.40	  For symbol evalspeedSingleSinglebb1in: X_1 >= 0
2.18/1.40	
2.18/1.40	  For symbol evalspeedSingleSinglebb2in: X_2 - 1 >= 0 /\ X_1 + X_2 - 1 >= 0 /\ -X_1 + X_2 - 1 >= 0 /\ X_1 >= 0
2.18/1.40	
2.18/1.40	  For symbol evalspeedSingleSinglebb3in: X_1 - X_2 >= 0 /\ X_1 >= 0
2.18/1.40	
2.18/1.40	
2.18/1.40	
2.18/1.40	
2.18/1.40	
2.18/1.40	This yielded the following problem:
2.18/1.40	
2.18/1.40	4:	T:
2.18/1.40	
2.18/1.40			(Comp: 1, Cost: 0)    koat_start(ar_0, ar_1) -> Com_1(evalspeedSingleSinglestart(ar_0, ar_1)) [ 0 <= 0 ]
2.18/1.40	
2.18/1.40			(Comp: 2, Cost: 1)    evalspeedSingleSinglebb3in(ar_0, ar_1) -> Com_1(evalspeedSingleSinglestop(ar_0, ar_1)) [ ar_0 - ar_1 >= 0 /\ ar_0 >= 0 ]
2.18/1.40	
2.18/1.40			(Comp: ?, Cost: 1)    evalspeedSingleSingle1(ar_0, ar_1) -> Com_1(evalspeedSingleSinglebb1in(ar_0 + 1, ar_1)) [ ar_1 - 1 >= 0 /\ ar_0 + ar_1 - 1 >= 0 /\ -ar_0 + ar_1 - 1 >= 0 /\ ar_0 >= 0 ]
2.18/1.40	
2.18/1.40			(Comp: ?, Cost: 1)    evalspeedSingleSingle0(ar_0, ar_1) -> Com_2(evalnondetstart(ar_0, ar_1), evalspeedSingleSingle1(ar_0, ar_1)) [ ar_1 - 1 >= 0 /\ ar_0 + ar_1 - 1 >= 0 /\ -ar_0 + ar_1 - 1 >= 0 /\ ar_0 >= 0 ]
2.18/1.40	
2.18/1.40			(Comp: ?, Cost: 1)    evalspeedSingleSinglebb2in(ar_0, ar_1) -> Com_1(evalspeedSingleSingle0(ar_0, ar_1)) [ ar_1 - 1 >= 0 /\ ar_0 + ar_1 - 1 >= 0 /\ -ar_0 + ar_1 - 1 >= 0 /\ ar_0 >= 0 ]
2.18/1.40	
2.18/1.40			(Comp: 2, Cost: 1)    evalspeedSingleSinglebb1in(ar_0, ar_1) -> Com_1(evalspeedSingleSinglebb3in(ar_0, ar_1)) [ ar_0 >= 0 /\ ar_0 >= ar_1 ]
2.18/1.40	
2.18/1.40			(Comp: ?, Cost: 1)    evalspeedSingleSinglebb1in(ar_0, ar_1) -> Com_1(evalspeedSingleSinglebb2in(ar_0, ar_1)) [ ar_0 >= 0 /\ ar_1 >= ar_0 + 1 ]
2.18/1.40	
2.18/1.40			(Comp: 1, Cost: 1)    evalspeedSingleSinglebb0in(ar_0, ar_1) -> Com_1(evalspeedSingleSinglebb1in(0, ar_1))
2.18/1.40	
2.18/1.40			(Comp: 1, Cost: 1)    evalspeedSingleSinglestart(ar_0, ar_1) -> Com_1(evalspeedSingleSinglebb0in(ar_0, ar_1))
2.18/1.40	
2.18/1.40		start location:	koat_start
2.18/1.40	
2.18/1.40		leaf cost:	0
2.18/1.40	
2.18/1.40	
2.18/1.40	
2.18/1.40	A polynomial rank function with
2.18/1.40	
2.18/1.40		Pol(koat_start) = 4*V_2
2.18/1.40	
2.18/1.40		Pol(evalspeedSingleSinglestart) = 4*V_2
2.18/1.40	
2.18/1.40		Pol(evalspeedSingleSinglebb3in) = -4*V_1 + 4*V_2
2.18/1.40	
2.18/1.40		Pol(evalspeedSingleSinglestop) = -4*V_1 + 4*V_2
2.18/1.40	
2.18/1.40		Pol(evalspeedSingleSingle1) = -4*V_1 + 4*V_2 - 3
2.18/1.40	
2.18/1.40		Pol(evalspeedSingleSinglebb1in) = -4*V_1 + 4*V_2
2.18/1.40	
2.18/1.40		Pol(evalspeedSingleSingle0) = -4*V_1 + 4*V_2 - 2
2.18/1.40	
2.18/1.40		Pol(evalnondetstart) = -4*V_1
2.18/1.40	
2.18/1.40		Pol(evalspeedSingleSinglebb2in) = -4*V_1 + 4*V_2 - 1
2.18/1.40	
2.18/1.40		Pol(evalspeedSingleSinglebb0in) = 4*V_2
2.18/1.40	
2.18/1.40	orients all transitions weakly and the transitions
2.18/1.40	
2.18/1.40		evalspeedSingleSinglebb2in(ar_0, ar_1) -> Com_1(evalspeedSingleSingle0(ar_0, ar_1)) [ ar_1 - 1 >= 0 /\ ar_0 + ar_1 - 1 >= 0 /\ -ar_0 + ar_1 - 1 >= 0 /\ ar_0 >= 0 ]
2.18/1.40	
2.18/1.40		evalspeedSingleSinglebb1in(ar_0, ar_1) -> Com_1(evalspeedSingleSinglebb2in(ar_0, ar_1)) [ ar_0 >= 0 /\ ar_1 >= ar_0 + 1 ]
2.18/1.40	
2.18/1.40		evalspeedSingleSingle1(ar_0, ar_1) -> Com_1(evalspeedSingleSinglebb1in(ar_0 + 1, ar_1)) [ ar_1 - 1 >= 0 /\ ar_0 + ar_1 - 1 >= 0 /\ -ar_0 + ar_1 - 1 >= 0 /\ ar_0 >= 0 ]
2.18/1.40	
2.18/1.40		evalspeedSingleSingle0(ar_0, ar_1) -> Com_2(evalnondetstart(ar_0, ar_1), evalspeedSingleSingle1(ar_0, ar_1)) [ ar_1 - 1 >= 0 /\ ar_0 + ar_1 - 1 >= 0 /\ -ar_0 + ar_1 - 1 >= 0 /\ ar_0 >= 0 ]
2.18/1.40	
2.18/1.40	strictly and produces the following problem:
2.18/1.40	
2.18/1.40	5:	T:
2.18/1.40	
2.18/1.40			(Comp: 1, Cost: 0)         koat_start(ar_0, ar_1) -> Com_1(evalspeedSingleSinglestart(ar_0, ar_1)) [ 0 <= 0 ]
2.18/1.40	
2.18/1.40			(Comp: 2, Cost: 1)         evalspeedSingleSinglebb3in(ar_0, ar_1) -> Com_1(evalspeedSingleSinglestop(ar_0, ar_1)) [ ar_0 - ar_1 >= 0 /\ ar_0 >= 0 ]
2.18/1.40	
2.18/1.40			(Comp: 4*ar_1, Cost: 1)    evalspeedSingleSingle1(ar_0, ar_1) -> Com_1(evalspeedSingleSinglebb1in(ar_0 + 1, ar_1)) [ ar_1 - 1 >= 0 /\ ar_0 + ar_1 - 1 >= 0 /\ -ar_0 + ar_1 - 1 >= 0 /\ ar_0 >= 0 ]
2.18/1.40	
2.18/1.40			(Comp: 4*ar_1, Cost: 1)    evalspeedSingleSingle0(ar_0, ar_1) -> Com_2(evalnondetstart(ar_0, ar_1), evalspeedSingleSingle1(ar_0, ar_1)) [ ar_1 - 1 >= 0 /\ ar_0 + ar_1 - 1 >= 0 /\ -ar_0 + ar_1 - 1 >= 0 /\ ar_0 >= 0 ]
2.18/1.40	
2.18/1.40			(Comp: 4*ar_1, Cost: 1)    evalspeedSingleSinglebb2in(ar_0, ar_1) -> Com_1(evalspeedSingleSingle0(ar_0, ar_1)) [ ar_1 - 1 >= 0 /\ ar_0 + ar_1 - 1 >= 0 /\ -ar_0 + ar_1 - 1 >= 0 /\ ar_0 >= 0 ]
2.18/1.40	
2.18/1.40			(Comp: 2, Cost: 1)         evalspeedSingleSinglebb1in(ar_0, ar_1) -> Com_1(evalspeedSingleSinglebb3in(ar_0, ar_1)) [ ar_0 >= 0 /\ ar_0 >= ar_1 ]
2.18/1.40	
2.18/1.40			(Comp: 4*ar_1, Cost: 1)    evalspeedSingleSinglebb1in(ar_0, ar_1) -> Com_1(evalspeedSingleSinglebb2in(ar_0, ar_1)) [ ar_0 >= 0 /\ ar_1 >= ar_0 + 1 ]
2.18/1.40	
2.18/1.40			(Comp: 1, Cost: 1)         evalspeedSingleSinglebb0in(ar_0, ar_1) -> Com_1(evalspeedSingleSinglebb1in(0, ar_1))
2.18/1.40	
2.18/1.40			(Comp: 1, Cost: 1)         evalspeedSingleSinglestart(ar_0, ar_1) -> Com_1(evalspeedSingleSinglebb0in(ar_0, ar_1))
2.18/1.40	
2.18/1.40		start location:	koat_start
2.18/1.40	
2.18/1.40		leaf cost:	0
2.18/1.40	
2.18/1.40	
2.18/1.40	
2.18/1.40	Complexity upper bound 16*ar_1 + 6
2.18/1.40	
2.18/1.40	
2.18/1.40	
2.18/1.40	Time: 0.141 sec (SMT: 0.126 sec)
2.18/1.40	
2.18/1.40	
2.18/1.40	----------------------------------------
2.18/1.40	
2.18/1.40	(2)
2.18/1.40	BOUNDS(1, n^1)
2.22/1.42	EOF