4.36/2.16	WORST_CASE(Omega(n^1), O(n^1))
4.36/2.17	proof of /export/starexec/sandbox/benchmark/theBenchmark.koat
4.36/2.17	# AProVE Commit ID: 48fb2092695e11cc9f56e44b17a92a5f88ffb256 marcel 20180622 unpublished dirty
4.36/2.17	
4.36/2.17	
4.36/2.17	The runtime complexity of the given CpxIntTrs could be proven to be BOUNDS(n^1, n^1).
4.36/2.17	
4.36/2.17	(0) CpxIntTrs
4.36/2.17	(1) Koat Proof [FINISHED, 36 ms]
4.36/2.17	(2) BOUNDS(1, n^1)
4.36/2.17	(3) Loat Proof [FINISHED, 522 ms]
4.36/2.17	(4) BOUNDS(n^1, INF)
4.36/2.17	
4.36/2.17	
4.36/2.17	----------------------------------------
4.36/2.17	
4.36/2.17	(0)
4.36/2.17	Obligation:
4.36/2.17	Complexity Int TRS consisting of the following rules:
4.36/2.17	eval_random1d_start(v_2, v_max, v_x_0) -> Com_1(eval_random1d_bb0_in(v_2, v_max, v_x_0)) :|: TRUE
4.36/2.17	eval_random1d_bb0_in(v_2, v_max, v_x_0) -> Com_1(eval_random1d_0(v_2, v_max, v_x_0)) :|: TRUE
4.36/2.17	eval_random1d_0(v_2, v_max, v_x_0) -> Com_1(eval_random1d_1(v_2, v_max, v_x_0)) :|: TRUE
4.36/2.17	eval_random1d_1(v_2, v_max, v_x_0) -> Com_1(eval_random1d_bb1_in(v_2, v_max, 1)) :|: v_max > 0
4.36/2.17	eval_random1d_1(v_2, v_max, v_x_0) -> Com_1(eval_random1d_bb3_in(v_2, v_max, v_x_0)) :|: v_max <= 0
4.36/2.17	eval_random1d_bb1_in(v_2, v_max, v_x_0) -> Com_1(eval_random1d_bb2_in(v_2, v_max, v_x_0)) :|: v_x_0 <= v_max
4.36/2.17	eval_random1d_bb1_in(v_2, v_max, v_x_0) -> Com_1(eval_random1d_bb3_in(v_2, v_max, v_x_0)) :|: v_x_0 > v_max
4.36/2.17	eval_random1d_bb2_in(v_2, v_max, v_x_0) -> Com_1(eval_random1d_2(v_2, v_max, v_x_0)) :|: TRUE
4.36/2.17	eval_random1d_2(v_2, v_max, v_x_0) -> Com_1(eval_random1d_3(nondef_0, v_max, v_x_0)) :|: TRUE
4.36/2.17	eval_random1d_3(v_2, v_max, v_x_0) -> Com_1(eval_random1d_bb1_in(v_2, v_max, v_x_0 + 1)) :|: v_2 > 0
4.36/2.17	eval_random1d_3(v_2, v_max, v_x_0) -> Com_1(eval_random1d_bb1_in(v_2, v_max, v_x_0 + 1)) :|: v_2 <= 0
4.36/2.17	eval_random1d_bb3_in(v_2, v_max, v_x_0) -> Com_1(eval_random1d_stop(v_2, v_max, v_x_0)) :|: TRUE
4.36/2.17	
4.36/2.17	The start-symbols are:[eval_random1d_start_3]
4.36/2.17	
4.36/2.17	
4.36/2.17	----------------------------------------
4.36/2.17	
4.36/2.17	(1) Koat Proof (FINISHED)
4.36/2.17	YES(?, 5*ar_0 + 19)
4.36/2.17	
4.36/2.17	
4.36/2.17	
4.36/2.17	Initial complexity problem:
4.36/2.17	
4.36/2.17	1:	T:
4.36/2.17	
4.36/2.17			(Comp: ?, Cost: 1)    evalrandom1dstart(ar_0, ar_1, ar_2) -> Com_1(evalrandom1dbb0in(ar_0, ar_1, ar_2))
4.36/2.17	
4.36/2.17			(Comp: ?, Cost: 1)    evalrandom1dbb0in(ar_0, ar_1, ar_2) -> Com_1(evalrandom1d0(ar_0, ar_1, ar_2))
4.36/2.17	
4.36/2.17			(Comp: ?, Cost: 1)    evalrandom1d0(ar_0, ar_1, ar_2) -> Com_1(evalrandom1d1(ar_0, ar_1, ar_2))
4.36/2.17	
4.36/2.17			(Comp: ?, Cost: 1)    evalrandom1d1(ar_0, ar_1, ar_2) -> Com_1(evalrandom1dbb1in(ar_0, 1, ar_2)) [ ar_0 >= 1 ]
4.36/2.17	
4.36/2.17			(Comp: ?, Cost: 1)    evalrandom1d1(ar_0, ar_1, ar_2) -> Com_1(evalrandom1dbb3in(ar_0, ar_1, ar_2)) [ 0 >= ar_0 ]
4.36/2.17	
4.36/2.17			(Comp: ?, Cost: 1)    evalrandom1dbb1in(ar_0, ar_1, ar_2) -> Com_1(evalrandom1dbb2in(ar_0, ar_1, ar_2)) [ ar_0 >= ar_1 ]
4.36/2.17	
4.36/2.17			(Comp: ?, Cost: 1)    evalrandom1dbb1in(ar_0, ar_1, ar_2) -> Com_1(evalrandom1dbb3in(ar_0, ar_1, ar_2)) [ ar_1 >= ar_0 + 1 ]
4.36/2.17	
4.36/2.17			(Comp: ?, Cost: 1)    evalrandom1dbb2in(ar_0, ar_1, ar_2) -> Com_1(evalrandom1d2(ar_0, ar_1, ar_2))
4.36/2.17	
4.36/2.17			(Comp: ?, Cost: 1)    evalrandom1d2(ar_0, ar_1, ar_2) -> Com_1(evalrandom1d3(ar_0, ar_1, d))
4.36/2.17	
4.36/2.17			(Comp: ?, Cost: 1)    evalrandom1d3(ar_0, ar_1, ar_2) -> Com_1(evalrandom1dbb1in(ar_0, ar_1 + 1, ar_2)) [ ar_2 >= 1 ]
4.36/2.17	
4.36/2.17			(Comp: ?, Cost: 1)    evalrandom1d3(ar_0, ar_1, ar_2) -> Com_1(evalrandom1dbb1in(ar_0, ar_1 + 1, ar_2)) [ 0 >= ar_2 ]
4.36/2.17	
4.36/2.17			(Comp: ?, Cost: 1)    evalrandom1dbb3in(ar_0, ar_1, ar_2) -> Com_1(evalrandom1dstop(ar_0, ar_1, ar_2))
4.36/2.17	
4.36/2.17			(Comp: 1, Cost: 0)    koat_start(ar_0, ar_1, ar_2) -> Com_1(evalrandom1dstart(ar_0, ar_1, ar_2)) [ 0 <= 0 ]
4.36/2.17	
4.36/2.17		start location:	koat_start
4.36/2.17	
4.36/2.17		leaf cost:	0
4.36/2.17	
4.36/2.17	
4.36/2.17	
4.36/2.17	Repeatedly propagating knowledge in problem 1 produces the following problem:
4.36/2.17	
4.36/2.17	2:	T:
4.36/2.17	
4.36/2.17			(Comp: 1, Cost: 1)    evalrandom1dstart(ar_0, ar_1, ar_2) -> Com_1(evalrandom1dbb0in(ar_0, ar_1, ar_2))
4.36/2.17	
4.36/2.17			(Comp: 1, Cost: 1)    evalrandom1dbb0in(ar_0, ar_1, ar_2) -> Com_1(evalrandom1d0(ar_0, ar_1, ar_2))
4.36/2.17	
4.36/2.17			(Comp: 1, Cost: 1)    evalrandom1d0(ar_0, ar_1, ar_2) -> Com_1(evalrandom1d1(ar_0, ar_1, ar_2))
4.36/2.17	
4.36/2.17			(Comp: 1, Cost: 1)    evalrandom1d1(ar_0, ar_1, ar_2) -> Com_1(evalrandom1dbb1in(ar_0, 1, ar_2)) [ ar_0 >= 1 ]
4.36/2.17	
4.36/2.17			(Comp: 1, Cost: 1)    evalrandom1d1(ar_0, ar_1, ar_2) -> Com_1(evalrandom1dbb3in(ar_0, ar_1, ar_2)) [ 0 >= ar_0 ]
4.36/2.17	
4.36/2.17			(Comp: ?, Cost: 1)    evalrandom1dbb1in(ar_0, ar_1, ar_2) -> Com_1(evalrandom1dbb2in(ar_0, ar_1, ar_2)) [ ar_0 >= ar_1 ]
4.36/2.17	
4.36/2.17			(Comp: ?, Cost: 1)    evalrandom1dbb1in(ar_0, ar_1, ar_2) -> Com_1(evalrandom1dbb3in(ar_0, ar_1, ar_2)) [ ar_1 >= ar_0 + 1 ]
4.36/2.17	
4.36/2.17			(Comp: ?, Cost: 1)    evalrandom1dbb2in(ar_0, ar_1, ar_2) -> Com_1(evalrandom1d2(ar_0, ar_1, ar_2))
4.36/2.17	
4.36/2.17			(Comp: ?, Cost: 1)    evalrandom1d2(ar_0, ar_1, ar_2) -> Com_1(evalrandom1d3(ar_0, ar_1, d))
4.36/2.17	
4.36/2.17			(Comp: ?, Cost: 1)    evalrandom1d3(ar_0, ar_1, ar_2) -> Com_1(evalrandom1dbb1in(ar_0, ar_1 + 1, ar_2)) [ ar_2 >= 1 ]
4.36/2.17	
4.36/2.17			(Comp: ?, Cost: 1)    evalrandom1d3(ar_0, ar_1, ar_2) -> Com_1(evalrandom1dbb1in(ar_0, ar_1 + 1, ar_2)) [ 0 >= ar_2 ]
4.36/2.17	
4.36/2.17			(Comp: ?, Cost: 1)    evalrandom1dbb3in(ar_0, ar_1, ar_2) -> Com_1(evalrandom1dstop(ar_0, ar_1, ar_2))
4.36/2.17	
4.36/2.17			(Comp: 1, Cost: 0)    koat_start(ar_0, ar_1, ar_2) -> Com_1(evalrandom1dstart(ar_0, ar_1, ar_2)) [ 0 <= 0 ]
4.36/2.17	
4.36/2.17		start location:	koat_start
4.36/2.17	
4.36/2.17		leaf cost:	0
4.36/2.17	
4.36/2.17	
4.36/2.17	
4.36/2.17	A polynomial rank function with
4.36/2.17	
4.36/2.17		Pol(evalrandom1dstart) = 2
4.36/2.17	
4.36/2.17		Pol(evalrandom1dbb0in) = 2
4.36/2.17	
4.36/2.17		Pol(evalrandom1d0) = 2
4.36/2.17	
4.36/2.17		Pol(evalrandom1d1) = 2
4.36/2.17	
4.36/2.17		Pol(evalrandom1dbb1in) = 2
4.36/2.17	
4.36/2.17		Pol(evalrandom1dbb3in) = 1
4.36/2.17	
4.36/2.17		Pol(evalrandom1dbb2in) = 2
4.36/2.17	
4.36/2.17		Pol(evalrandom1d2) = 2
4.36/2.17	
4.36/2.17		Pol(evalrandom1d3) = 2
4.36/2.17	
4.36/2.17		Pol(evalrandom1dstop) = 0
4.36/2.17	
4.36/2.17		Pol(koat_start) = 2
4.36/2.17	
4.36/2.17	orients all transitions weakly and the transitions
4.36/2.17	
4.36/2.17		evalrandom1dbb3in(ar_0, ar_1, ar_2) -> Com_1(evalrandom1dstop(ar_0, ar_1, ar_2))
4.36/2.17	
4.36/2.17		evalrandom1dbb1in(ar_0, ar_1, ar_2) -> Com_1(evalrandom1dbb3in(ar_0, ar_1, ar_2)) [ ar_1 >= ar_0 + 1 ]
4.36/2.17	
4.36/2.17	strictly and produces the following problem:
4.36/2.17	
4.36/2.17	3:	T:
4.36/2.17	
4.36/2.17			(Comp: 1, Cost: 1)    evalrandom1dstart(ar_0, ar_1, ar_2) -> Com_1(evalrandom1dbb0in(ar_0, ar_1, ar_2))
4.36/2.17	
4.36/2.17			(Comp: 1, Cost: 1)    evalrandom1dbb0in(ar_0, ar_1, ar_2) -> Com_1(evalrandom1d0(ar_0, ar_1, ar_2))
4.36/2.17	
4.36/2.17			(Comp: 1, Cost: 1)    evalrandom1d0(ar_0, ar_1, ar_2) -> Com_1(evalrandom1d1(ar_0, ar_1, ar_2))
4.36/2.17	
4.36/2.17			(Comp: 1, Cost: 1)    evalrandom1d1(ar_0, ar_1, ar_2) -> Com_1(evalrandom1dbb1in(ar_0, 1, ar_2)) [ ar_0 >= 1 ]
4.36/2.17	
4.36/2.17			(Comp: 1, Cost: 1)    evalrandom1d1(ar_0, ar_1, ar_2) -> Com_1(evalrandom1dbb3in(ar_0, ar_1, ar_2)) [ 0 >= ar_0 ]
4.36/2.17	
4.36/2.17			(Comp: ?, Cost: 1)    evalrandom1dbb1in(ar_0, ar_1, ar_2) -> Com_1(evalrandom1dbb2in(ar_0, ar_1, ar_2)) [ ar_0 >= ar_1 ]
4.36/2.17	
4.36/2.17			(Comp: 2, Cost: 1)    evalrandom1dbb1in(ar_0, ar_1, ar_2) -> Com_1(evalrandom1dbb3in(ar_0, ar_1, ar_2)) [ ar_1 >= ar_0 + 1 ]
4.36/2.17	
4.36/2.17			(Comp: ?, Cost: 1)    evalrandom1dbb2in(ar_0, ar_1, ar_2) -> Com_1(evalrandom1d2(ar_0, ar_1, ar_2))
4.36/2.17	
4.36/2.17			(Comp: ?, Cost: 1)    evalrandom1d2(ar_0, ar_1, ar_2) -> Com_1(evalrandom1d3(ar_0, ar_1, d))
4.36/2.17	
4.36/2.17			(Comp: ?, Cost: 1)    evalrandom1d3(ar_0, ar_1, ar_2) -> Com_1(evalrandom1dbb1in(ar_0, ar_1 + 1, ar_2)) [ ar_2 >= 1 ]
4.36/2.17	
4.36/2.17			(Comp: ?, Cost: 1)    evalrandom1d3(ar_0, ar_1, ar_2) -> Com_1(evalrandom1dbb1in(ar_0, ar_1 + 1, ar_2)) [ 0 >= ar_2 ]
4.36/2.17	
4.36/2.17			(Comp: 2, Cost: 1)    evalrandom1dbb3in(ar_0, ar_1, ar_2) -> Com_1(evalrandom1dstop(ar_0, ar_1, ar_2))
4.36/2.17	
4.36/2.17			(Comp: 1, Cost: 0)    koat_start(ar_0, ar_1, ar_2) -> Com_1(evalrandom1dstart(ar_0, ar_1, ar_2)) [ 0 <= 0 ]
4.36/2.17	
4.36/2.17		start location:	koat_start
4.36/2.17	
4.36/2.17		leaf cost:	0
4.36/2.17	
4.36/2.17	
4.36/2.17	
4.36/2.17	A polynomial rank function with
4.36/2.17	
4.36/2.17		Pol(evalrandom1dbb2in) = V_1 - V_2
4.36/2.17	
4.36/2.17		Pol(evalrandom1d2) = V_1 - V_2
4.36/2.17	
4.36/2.17		Pol(evalrandom1dbb1in) = V_1 - V_2 + 1
4.36/2.17	
4.36/2.17		Pol(evalrandom1d3) = V_1 - V_2
4.36/2.17	
4.36/2.17	and size complexities
4.36/2.17	
4.36/2.17		S("koat_start(ar_0, ar_1, ar_2) -> Com_1(evalrandom1dstart(ar_0, ar_1, ar_2)) [ 0 <= 0 ]", 0-0) = ar_0
4.36/2.17	
4.36/2.17		S("koat_start(ar_0, ar_1, ar_2) -> Com_1(evalrandom1dstart(ar_0, ar_1, ar_2)) [ 0 <= 0 ]", 0-1) = ar_1
4.36/2.17	
4.36/2.17		S("koat_start(ar_0, ar_1, ar_2) -> Com_1(evalrandom1dstart(ar_0, ar_1, ar_2)) [ 0 <= 0 ]", 0-2) = ar_2
4.36/2.17	
4.36/2.17		S("evalrandom1dbb3in(ar_0, ar_1, ar_2) -> Com_1(evalrandom1dstop(ar_0, ar_1, ar_2))", 0-0) = ar_0
4.36/2.17	
4.36/2.17		S("evalrandom1dbb3in(ar_0, ar_1, ar_2) -> Com_1(evalrandom1dstop(ar_0, ar_1, ar_2))", 0-1) = ?
4.36/2.17	
4.36/2.17		S("evalrandom1dbb3in(ar_0, ar_1, ar_2) -> Com_1(evalrandom1dstop(ar_0, ar_1, ar_2))", 0-2) = ?
4.36/2.17	
4.36/2.17		S("evalrandom1d3(ar_0, ar_1, ar_2) -> Com_1(evalrandom1dbb1in(ar_0, ar_1 + 1, ar_2)) [ 0 >= ar_2 ]", 0-0) = ar_0
4.36/2.17	
4.36/2.17		S("evalrandom1d3(ar_0, ar_1, ar_2) -> Com_1(evalrandom1dbb1in(ar_0, ar_1 + 1, ar_2)) [ 0 >= ar_2 ]", 0-1) = ?
4.36/2.17	
4.36/2.17		S("evalrandom1d3(ar_0, ar_1, ar_2) -> Com_1(evalrandom1dbb1in(ar_0, ar_1 + 1, ar_2)) [ 0 >= ar_2 ]", 0-2) = ?
4.36/2.17	
4.36/2.17		S("evalrandom1d3(ar_0, ar_1, ar_2) -> Com_1(evalrandom1dbb1in(ar_0, ar_1 + 1, ar_2)) [ ar_2 >= 1 ]", 0-0) = ar_0
4.36/2.17	
4.36/2.17		S("evalrandom1d3(ar_0, ar_1, ar_2) -> Com_1(evalrandom1dbb1in(ar_0, ar_1 + 1, ar_2)) [ ar_2 >= 1 ]", 0-1) = ?
4.36/2.17	
4.36/2.17		S("evalrandom1d3(ar_0, ar_1, ar_2) -> Com_1(evalrandom1dbb1in(ar_0, ar_1 + 1, ar_2)) [ ar_2 >= 1 ]", 0-2) = ?
4.36/2.17	
4.36/2.17		S("evalrandom1d2(ar_0, ar_1, ar_2) -> Com_1(evalrandom1d3(ar_0, ar_1, d))", 0-0) = ar_0
4.36/2.17	
4.36/2.17		S("evalrandom1d2(ar_0, ar_1, ar_2) -> Com_1(evalrandom1d3(ar_0, ar_1, d))", 0-1) = ?
4.36/2.17	
4.36/2.17		S("evalrandom1d2(ar_0, ar_1, ar_2) -> Com_1(evalrandom1d3(ar_0, ar_1, d))", 0-2) = ?
4.36/2.17	
4.36/2.17		S("evalrandom1dbb2in(ar_0, ar_1, ar_2) -> Com_1(evalrandom1d2(ar_0, ar_1, ar_2))", 0-0) = ar_0
4.36/2.17	
4.36/2.17		S("evalrandom1dbb2in(ar_0, ar_1, ar_2) -> Com_1(evalrandom1d2(ar_0, ar_1, ar_2))", 0-1) = ?
4.36/2.17	
4.36/2.17		S("evalrandom1dbb2in(ar_0, ar_1, ar_2) -> Com_1(evalrandom1d2(ar_0, ar_1, ar_2))", 0-2) = ?
4.36/2.17	
4.36/2.17		S("evalrandom1dbb1in(ar_0, ar_1, ar_2) -> Com_1(evalrandom1dbb3in(ar_0, ar_1, ar_2)) [ ar_1 >= ar_0 + 1 ]", 0-0) = ar_0
4.36/2.17	
4.36/2.17		S("evalrandom1dbb1in(ar_0, ar_1, ar_2) -> Com_1(evalrandom1dbb3in(ar_0, ar_1, ar_2)) [ ar_1 >= ar_0 + 1 ]", 0-1) = ?
4.36/2.17	
4.36/2.17		S("evalrandom1dbb1in(ar_0, ar_1, ar_2) -> Com_1(evalrandom1dbb3in(ar_0, ar_1, ar_2)) [ ar_1 >= ar_0 + 1 ]", 0-2) = ?
4.36/2.17	
4.36/2.17		S("evalrandom1dbb1in(ar_0, ar_1, ar_2) -> Com_1(evalrandom1dbb2in(ar_0, ar_1, ar_2)) [ ar_0 >= ar_1 ]", 0-0) = ar_0
4.36/2.17	
4.36/2.17		S("evalrandom1dbb1in(ar_0, ar_1, ar_2) -> Com_1(evalrandom1dbb2in(ar_0, ar_1, ar_2)) [ ar_0 >= ar_1 ]", 0-1) = ?
4.36/2.17	
4.36/2.17		S("evalrandom1dbb1in(ar_0, ar_1, ar_2) -> Com_1(evalrandom1dbb2in(ar_0, ar_1, ar_2)) [ ar_0 >= ar_1 ]", 0-2) = ?
4.36/2.17	
4.36/2.17		S("evalrandom1d1(ar_0, ar_1, ar_2) -> Com_1(evalrandom1dbb3in(ar_0, ar_1, ar_2)) [ 0 >= ar_0 ]", 0-0) = ar_0
4.36/2.17	
4.36/2.17		S("evalrandom1d1(ar_0, ar_1, ar_2) -> Com_1(evalrandom1dbb3in(ar_0, ar_1, ar_2)) [ 0 >= ar_0 ]", 0-1) = ar_1
4.36/2.17	
4.36/2.17		S("evalrandom1d1(ar_0, ar_1, ar_2) -> Com_1(evalrandom1dbb3in(ar_0, ar_1, ar_2)) [ 0 >= ar_0 ]", 0-2) = ar_2
4.36/2.17	
4.36/2.17		S("evalrandom1d1(ar_0, ar_1, ar_2) -> Com_1(evalrandom1dbb1in(ar_0, 1, ar_2)) [ ar_0 >= 1 ]", 0-0) = ar_0
4.36/2.17	
4.36/2.17		S("evalrandom1d1(ar_0, ar_1, ar_2) -> Com_1(evalrandom1dbb1in(ar_0, 1, ar_2)) [ ar_0 >= 1 ]", 0-1) = 1
4.36/2.17	
4.36/2.17		S("evalrandom1d1(ar_0, ar_1, ar_2) -> Com_1(evalrandom1dbb1in(ar_0, 1, ar_2)) [ ar_0 >= 1 ]", 0-2) = ar_2
4.36/2.17	
4.36/2.17		S("evalrandom1d0(ar_0, ar_1, ar_2) -> Com_1(evalrandom1d1(ar_0, ar_1, ar_2))", 0-0) = ar_0
4.36/2.17	
4.36/2.17		S("evalrandom1d0(ar_0, ar_1, ar_2) -> Com_1(evalrandom1d1(ar_0, ar_1, ar_2))", 0-1) = ar_1
4.36/2.17	
4.36/2.17		S("evalrandom1d0(ar_0, ar_1, ar_2) -> Com_1(evalrandom1d1(ar_0, ar_1, ar_2))", 0-2) = ar_2
4.36/2.17	
4.36/2.17		S("evalrandom1dbb0in(ar_0, ar_1, ar_2) -> Com_1(evalrandom1d0(ar_0, ar_1, ar_2))", 0-0) = ar_0
4.36/2.17	
4.36/2.17		S("evalrandom1dbb0in(ar_0, ar_1, ar_2) -> Com_1(evalrandom1d0(ar_0, ar_1, ar_2))", 0-1) = ar_1
4.36/2.17	
4.36/2.17		S("evalrandom1dbb0in(ar_0, ar_1, ar_2) -> Com_1(evalrandom1d0(ar_0, ar_1, ar_2))", 0-2) = ar_2
4.36/2.17	
4.36/2.17		S("evalrandom1dstart(ar_0, ar_1, ar_2) -> Com_1(evalrandom1dbb0in(ar_0, ar_1, ar_2))", 0-0) = ar_0
4.36/2.17	
4.36/2.17		S("evalrandom1dstart(ar_0, ar_1, ar_2) -> Com_1(evalrandom1dbb0in(ar_0, ar_1, ar_2))", 0-1) = ar_1
4.36/2.17	
4.36/2.17		S("evalrandom1dstart(ar_0, ar_1, ar_2) -> Com_1(evalrandom1dbb0in(ar_0, ar_1, ar_2))", 0-2) = ar_2
4.36/2.17	
4.36/2.17	orients the transitions
4.36/2.17	
4.36/2.17		evalrandom1dbb2in(ar_0, ar_1, ar_2) -> Com_1(evalrandom1d2(ar_0, ar_1, ar_2))
4.36/2.17	
4.36/2.17		evalrandom1dbb1in(ar_0, ar_1, ar_2) -> Com_1(evalrandom1dbb2in(ar_0, ar_1, ar_2)) [ ar_0 >= ar_1 ]
4.36/2.17	
4.36/2.17		evalrandom1d3(ar_0, ar_1, ar_2) -> Com_1(evalrandom1dbb1in(ar_0, ar_1 + 1, ar_2)) [ ar_2 >= 1 ]
4.36/2.17	
4.36/2.17		evalrandom1d3(ar_0, ar_1, ar_2) -> Com_1(evalrandom1dbb1in(ar_0, ar_1 + 1, ar_2)) [ 0 >= ar_2 ]
4.36/2.17	
4.36/2.17		evalrandom1d2(ar_0, ar_1, ar_2) -> Com_1(evalrandom1d3(ar_0, ar_1, d))
4.36/2.17	
4.36/2.17	weakly and the transition
4.36/2.17	
4.36/2.17		evalrandom1dbb1in(ar_0, ar_1, ar_2) -> Com_1(evalrandom1dbb2in(ar_0, ar_1, ar_2)) [ ar_0 >= ar_1 ]
4.36/2.17	
4.36/2.17	strictly and produces the following problem:
4.36/2.17	
4.36/2.17	4:	T:
4.36/2.17	
4.36/2.17			(Comp: 1, Cost: 1)           evalrandom1dstart(ar_0, ar_1, ar_2) -> Com_1(evalrandom1dbb0in(ar_0, ar_1, ar_2))
4.36/2.17	
4.36/2.17			(Comp: 1, Cost: 1)           evalrandom1dbb0in(ar_0, ar_1, ar_2) -> Com_1(evalrandom1d0(ar_0, ar_1, ar_2))
4.36/2.17	
4.36/2.17			(Comp: 1, Cost: 1)           evalrandom1d0(ar_0, ar_1, ar_2) -> Com_1(evalrandom1d1(ar_0, ar_1, ar_2))
4.36/2.17	
4.36/2.17			(Comp: 1, Cost: 1)           evalrandom1d1(ar_0, ar_1, ar_2) -> Com_1(evalrandom1dbb1in(ar_0, 1, ar_2)) [ ar_0 >= 1 ]
4.36/2.17	
4.36/2.17			(Comp: 1, Cost: 1)           evalrandom1d1(ar_0, ar_1, ar_2) -> Com_1(evalrandom1dbb3in(ar_0, ar_1, ar_2)) [ 0 >= ar_0 ]
4.36/2.17	
4.36/2.17			(Comp: ar_0 + 2, Cost: 1)    evalrandom1dbb1in(ar_0, ar_1, ar_2) -> Com_1(evalrandom1dbb2in(ar_0, ar_1, ar_2)) [ ar_0 >= ar_1 ]
4.36/2.17	
4.36/2.17			(Comp: 2, Cost: 1)           evalrandom1dbb1in(ar_0, ar_1, ar_2) -> Com_1(evalrandom1dbb3in(ar_0, ar_1, ar_2)) [ ar_1 >= ar_0 + 1 ]
4.36/2.17	
4.36/2.17			(Comp: ?, Cost: 1)           evalrandom1dbb2in(ar_0, ar_1, ar_2) -> Com_1(evalrandom1d2(ar_0, ar_1, ar_2))
4.36/2.17	
4.36/2.17			(Comp: ?, Cost: 1)           evalrandom1d2(ar_0, ar_1, ar_2) -> Com_1(evalrandom1d3(ar_0, ar_1, d))
4.36/2.17	
4.36/2.17			(Comp: ?, Cost: 1)           evalrandom1d3(ar_0, ar_1, ar_2) -> Com_1(evalrandom1dbb1in(ar_0, ar_1 + 1, ar_2)) [ ar_2 >= 1 ]
4.36/2.17	
4.36/2.17			(Comp: ?, Cost: 1)           evalrandom1d3(ar_0, ar_1, ar_2) -> Com_1(evalrandom1dbb1in(ar_0, ar_1 + 1, ar_2)) [ 0 >= ar_2 ]
4.36/2.17	
4.36/2.17			(Comp: 2, Cost: 1)           evalrandom1dbb3in(ar_0, ar_1, ar_2) -> Com_1(evalrandom1dstop(ar_0, ar_1, ar_2))
4.36/2.17	
4.36/2.17			(Comp: 1, Cost: 0)           koat_start(ar_0, ar_1, ar_2) -> Com_1(evalrandom1dstart(ar_0, ar_1, ar_2)) [ 0 <= 0 ]
4.36/2.17	
4.36/2.17		start location:	koat_start
4.36/2.17	
4.36/2.17		leaf cost:	0
4.36/2.17	
4.36/2.17	
4.36/2.17	
4.36/2.17	Repeatedly propagating knowledge in problem 4 produces the following problem:
4.36/2.17	
4.36/2.17	5:	T:
4.36/2.17	
4.36/2.17			(Comp: 1, Cost: 1)           evalrandom1dstart(ar_0, ar_1, ar_2) -> Com_1(evalrandom1dbb0in(ar_0, ar_1, ar_2))
4.36/2.17	
4.36/2.17			(Comp: 1, Cost: 1)           evalrandom1dbb0in(ar_0, ar_1, ar_2) -> Com_1(evalrandom1d0(ar_0, ar_1, ar_2))
4.36/2.17	
4.36/2.17			(Comp: 1, Cost: 1)           evalrandom1d0(ar_0, ar_1, ar_2) -> Com_1(evalrandom1d1(ar_0, ar_1, ar_2))
4.36/2.17	
4.36/2.17			(Comp: 1, Cost: 1)           evalrandom1d1(ar_0, ar_1, ar_2) -> Com_1(evalrandom1dbb1in(ar_0, 1, ar_2)) [ ar_0 >= 1 ]
4.36/2.17	
4.36/2.17			(Comp: 1, Cost: 1)           evalrandom1d1(ar_0, ar_1, ar_2) -> Com_1(evalrandom1dbb3in(ar_0, ar_1, ar_2)) [ 0 >= ar_0 ]
4.36/2.17	
4.36/2.17			(Comp: ar_0 + 2, Cost: 1)    evalrandom1dbb1in(ar_0, ar_1, ar_2) -> Com_1(evalrandom1dbb2in(ar_0, ar_1, ar_2)) [ ar_0 >= ar_1 ]
4.36/2.17	
4.36/2.17			(Comp: 2, Cost: 1)           evalrandom1dbb1in(ar_0, ar_1, ar_2) -> Com_1(evalrandom1dbb3in(ar_0, ar_1, ar_2)) [ ar_1 >= ar_0 + 1 ]
4.36/2.17	
4.36/2.17			(Comp: ar_0 + 2, Cost: 1)    evalrandom1dbb2in(ar_0, ar_1, ar_2) -> Com_1(evalrandom1d2(ar_0, ar_1, ar_2))
4.36/2.17	
4.36/2.17			(Comp: ar_0 + 2, Cost: 1)    evalrandom1d2(ar_0, ar_1, ar_2) -> Com_1(evalrandom1d3(ar_0, ar_1, d))
4.36/2.17	
4.36/2.17			(Comp: ar_0 + 2, Cost: 1)    evalrandom1d3(ar_0, ar_1, ar_2) -> Com_1(evalrandom1dbb1in(ar_0, ar_1 + 1, ar_2)) [ ar_2 >= 1 ]
4.36/2.17	
4.36/2.17			(Comp: ar_0 + 2, Cost: 1)    evalrandom1d3(ar_0, ar_1, ar_2) -> Com_1(evalrandom1dbb1in(ar_0, ar_1 + 1, ar_2)) [ 0 >= ar_2 ]
4.36/2.17	
4.36/2.17			(Comp: 2, Cost: 1)           evalrandom1dbb3in(ar_0, ar_1, ar_2) -> Com_1(evalrandom1dstop(ar_0, ar_1, ar_2))
4.36/2.17	
4.36/2.17			(Comp: 1, Cost: 0)           koat_start(ar_0, ar_1, ar_2) -> Com_1(evalrandom1dstart(ar_0, ar_1, ar_2)) [ 0 <= 0 ]
4.36/2.17	
4.36/2.17		start location:	koat_start
4.36/2.17	
4.36/2.17		leaf cost:	0
4.36/2.17	
4.36/2.17	
4.36/2.17	
4.36/2.17	Complexity upper bound 5*ar_0 + 19
4.36/2.17	
4.36/2.17	
4.36/2.17	
4.36/2.17	Time: 0.093 sec (SMT: 0.080 sec)
4.36/2.17	
4.36/2.17	
4.36/2.17	----------------------------------------
4.36/2.17	
4.36/2.17	(2)
4.36/2.17	BOUNDS(1, n^1)
4.36/2.17	
4.36/2.17	----------------------------------------
4.36/2.17	
4.36/2.17	(3) Loat Proof (FINISHED)
4.36/2.17	
4.36/2.17	
4.36/2.17	### Pre-processing the ITS problem ###
4.36/2.17	
4.36/2.17	
4.36/2.17	
4.36/2.17	Initial linear ITS problem
4.36/2.17	
4.36/2.17	   Start location: evalrandom1dstart
4.36/2.17	
4.36/2.17	      0: evalrandom1dstart -> evalrandom1dbb0in : [], cost: 1
4.36/2.17	
4.36/2.17	      1: evalrandom1dbb0in -> evalrandom1d0 : [], cost: 1
4.36/2.17	
4.36/2.17	      2: evalrandom1d0 -> evalrandom1d1 : [], cost: 1
4.36/2.17	
4.36/2.17	      3: evalrandom1d1 -> evalrandom1dbb1in : B'=1, [ A>=1 ], cost: 1
4.36/2.17	
4.36/2.17	      4: evalrandom1d1 -> evalrandom1dbb3in : [ 0>=A ], cost: 1
4.36/2.17	
4.36/2.17	      5: evalrandom1dbb1in -> evalrandom1dbb2in : [ A>=B ], cost: 1
4.36/2.17	
4.36/2.17	      6: evalrandom1dbb1in -> evalrandom1dbb3in : [ B>=1+A ], cost: 1
4.36/2.17	
4.36/2.17	      7: evalrandom1dbb2in -> evalrandom1d2 : [], cost: 1
4.36/2.17	
4.36/2.17	      8: evalrandom1d2 -> evalrandom1d3 : C'=free, [], cost: 1
4.36/2.17	
4.36/2.17	      9: evalrandom1d3 -> evalrandom1dbb1in : B'=1+B, [ C>=1 ], cost: 1
4.36/2.17	
4.36/2.17	     10: evalrandom1d3 -> evalrandom1dbb1in : B'=1+B, [ 0>=C ], cost: 1
4.36/2.17	
4.36/2.17	     11: evalrandom1dbb3in -> evalrandom1dstop : [], cost: 1
4.36/2.17	
4.36/2.17	
4.36/2.17	
4.36/2.17	Removed unreachable and leaf rules:
4.36/2.17	
4.36/2.17	   Start location: evalrandom1dstart
4.36/2.17	
4.36/2.17	      0: evalrandom1dstart -> evalrandom1dbb0in : [], cost: 1
4.36/2.17	
4.36/2.17	      1: evalrandom1dbb0in -> evalrandom1d0 : [], cost: 1
4.36/2.17	
4.36/2.17	      2: evalrandom1d0 -> evalrandom1d1 : [], cost: 1
4.36/2.17	
4.36/2.17	      3: evalrandom1d1 -> evalrandom1dbb1in : B'=1, [ A>=1 ], cost: 1
4.36/2.17	
4.36/2.17	      5: evalrandom1dbb1in -> evalrandom1dbb2in : [ A>=B ], cost: 1
4.36/2.17	
4.36/2.17	      7: evalrandom1dbb2in -> evalrandom1d2 : [], cost: 1
4.36/2.17	
4.36/2.17	      8: evalrandom1d2 -> evalrandom1d3 : C'=free, [], cost: 1
4.36/2.17	
4.36/2.17	      9: evalrandom1d3 -> evalrandom1dbb1in : B'=1+B, [ C>=1 ], cost: 1
4.36/2.17	
4.36/2.17	     10: evalrandom1d3 -> evalrandom1dbb1in : B'=1+B, [ 0>=C ], cost: 1
4.36/2.17	
4.36/2.17	
4.36/2.17	
4.36/2.17	### Simplification by acceleration and chaining ###
4.36/2.17	
4.36/2.17	
4.36/2.17	
4.36/2.17	Eliminated locations (on linear paths):
4.36/2.17	
4.36/2.17	   Start location: evalrandom1dstart
4.36/2.17	
4.36/2.17	     14: evalrandom1dstart -> evalrandom1dbb1in : B'=1, [ A>=1 ], cost: 4
4.36/2.17	
4.36/2.17	     16: evalrandom1dbb1in -> evalrandom1d3 : C'=free, [ A>=B ], cost: 3
4.36/2.17	
4.36/2.17	      9: evalrandom1d3 -> evalrandom1dbb1in : B'=1+B, [ C>=1 ], cost: 1
4.36/2.17	
4.36/2.17	     10: evalrandom1d3 -> evalrandom1dbb1in : B'=1+B, [ 0>=C ], cost: 1
4.36/2.17	
4.36/2.17	
4.36/2.17	
4.36/2.17	Eliminated locations (on tree-shaped paths):
4.36/2.17	
4.36/2.17	   Start location: evalrandom1dstart
4.36/2.17	
4.36/2.17	     14: evalrandom1dstart -> evalrandom1dbb1in : B'=1, [ A>=1 ], cost: 4
4.36/2.17	
4.36/2.17	     17: evalrandom1dbb1in -> evalrandom1dbb1in : B'=1+B, C'=free, [ A>=B && free>=1 ], cost: 4
4.36/2.17	
4.36/2.17	     18: evalrandom1dbb1in -> evalrandom1dbb1in : B'=1+B, C'=free, [ A>=B && 0>=free ], cost: 4
4.36/2.17	
4.36/2.17	
4.36/2.17	
4.36/2.17	Accelerating simple loops of location 4.
4.36/2.17	
4.36/2.17	   Accelerating the following rules:
4.36/2.17	
4.36/2.17	     17: evalrandom1dbb1in -> evalrandom1dbb1in : B'=1+B, C'=free, [ A>=B && free>=1 ], cost: 4
4.36/2.17	
4.36/2.17	     18: evalrandom1dbb1in -> evalrandom1dbb1in : B'=1+B, C'=free, [ A>=B && 0>=free ], cost: 4
4.36/2.17	
4.36/2.17	
4.36/2.17	
4.36/2.17	   Accelerated rule 17 with metering function 1+A-B, yielding the new rule 19.
4.36/2.17	
4.36/2.17	   Accelerated rule 18 with metering function 1+A-B, yielding the new rule 20.
4.36/2.17	
4.36/2.17	   Removing the simple loops: 17 18.
4.36/2.17	
4.36/2.17	
4.36/2.17	
4.36/2.17	Accelerated all simple loops using metering functions (where possible):
4.36/2.17	
4.36/2.17	   Start location: evalrandom1dstart
4.36/2.17	
4.36/2.17	     14: evalrandom1dstart -> evalrandom1dbb1in : B'=1, [ A>=1 ], cost: 4
4.36/2.17	
4.36/2.17	     19: evalrandom1dbb1in -> evalrandom1dbb1in : B'=1+A, C'=free, [ A>=B && free>=1 ], cost: 4+4*A-4*B
4.36/2.18	
4.36/2.18	     20: evalrandom1dbb1in -> evalrandom1dbb1in : B'=1+A, C'=free, [ A>=B && 0>=free ], cost: 4+4*A-4*B
4.36/2.18	
4.36/2.18	
4.36/2.18	
4.36/2.18	Chained accelerated rules (with incoming rules):
4.36/2.18	
4.36/2.18	   Start location: evalrandom1dstart
4.36/2.18	
4.36/2.18	     14: evalrandom1dstart -> evalrandom1dbb1in : B'=1, [ A>=1 ], cost: 4
4.36/2.18	
4.36/2.18	     21: evalrandom1dstart -> evalrandom1dbb1in : B'=1+A, C'=free, [ A>=1 && free>=1 ], cost: 4+4*A
4.36/2.18	
4.36/2.18	     22: evalrandom1dstart -> evalrandom1dbb1in : B'=1+A, C'=free, [ A>=1 && 0>=free ], cost: 4+4*A
4.36/2.18	
4.36/2.18	
4.36/2.18	
4.36/2.18	Removed unreachable locations (and leaf rules with constant cost):
4.36/2.18	
4.36/2.18	   Start location: evalrandom1dstart
4.36/2.18	
4.36/2.18	     21: evalrandom1dstart -> evalrandom1dbb1in : B'=1+A, C'=free, [ A>=1 && free>=1 ], cost: 4+4*A
4.36/2.18	
4.36/2.18	     22: evalrandom1dstart -> evalrandom1dbb1in : B'=1+A, C'=free, [ A>=1 && 0>=free ], cost: 4+4*A
4.36/2.18	
4.36/2.18	
4.36/2.18	
4.36/2.18	### Computing asymptotic complexity ###
4.36/2.18	
4.36/2.18	
4.36/2.18	
4.36/2.18	Fully simplified ITS problem
4.36/2.18	
4.36/2.18	   Start location: evalrandom1dstart
4.36/2.18	
4.36/2.18	     21: evalrandom1dstart -> evalrandom1dbb1in : B'=1+A, C'=free, [ A>=1 && free>=1 ], cost: 4+4*A
4.36/2.18	
4.36/2.18	     22: evalrandom1dstart -> evalrandom1dbb1in : B'=1+A, C'=free, [ A>=1 && 0>=free ], cost: 4+4*A
4.36/2.18	
4.36/2.18	
4.36/2.18	
4.36/2.18	Computing asymptotic complexity for rule 21
4.36/2.18	
4.36/2.18	   Solved the limit problem by the following transformations:
4.36/2.18	
4.36/2.18	      Created initial limit problem:
4.36/2.18	
4.36/2.18	      A (+/+!), free (+/+!), 4+4*A (+) [not solved]
4.36/2.18	
4.36/2.18	
4.36/2.18	
4.36/2.18	      removing all constraints (solved by SMT)
4.36/2.18	
4.36/2.18	      resulting limit problem: [solved]
4.36/2.18	
4.36/2.18	
4.36/2.18	
4.36/2.18	      applying transformation rule (C) using substitution {A==n,free==1}
4.36/2.18	
4.36/2.18	      resulting limit problem:
4.36/2.18	
4.36/2.18	      [solved]
4.36/2.18	
4.36/2.18	
4.36/2.18	
4.36/2.18	   Solution:
4.36/2.18	
4.36/2.18	      A / n
4.36/2.18	
4.36/2.18	      free / 1
4.36/2.18	
4.36/2.18	   Resulting cost 4+4*n has complexity: Poly(n^1)
4.36/2.18	
4.36/2.18	
4.36/2.18	
4.36/2.18	Found new complexity Poly(n^1).
4.36/2.18	
4.36/2.18	
4.36/2.18	
4.36/2.18	Obtained the following overall complexity (w.r.t. the length of the input n):
4.36/2.18	
4.36/2.18	   Complexity:  Poly(n^1)
4.36/2.18	
4.36/2.18	   Cpx degree:  1
4.36/2.18	
4.36/2.18	   Solved cost: 4+4*n
4.36/2.18	
4.36/2.18	   Rule cost:   4+4*A
4.36/2.18	
4.36/2.18	   Rule guard:  [ A>=1 && free>=1 ]
4.36/2.18	
4.36/2.18	
4.36/2.18	
4.36/2.18	WORST_CASE(Omega(n^1),?)
4.36/2.18	
4.36/2.18	
4.36/2.18	----------------------------------------
4.36/2.18	
4.36/2.18	(4)
4.36/2.18	BOUNDS(n^1, INF)
4.56/2.19	EOF