2.26/1.28	WORST_CASE(?, O(1))
2.26/1.29	proof of /export/starexec/sandbox/output/output_files/bench.koat
2.26/1.29	# AProVE Commit ID: 48fb2092695e11cc9f56e44b17a92a5f88ffb256 marcel 20180622 unpublished dirty
2.26/1.29	
2.26/1.29	
2.26/1.29	The runtime complexity of the given CpxIntTrs could be proven to be BOUNDS(1, 1).
2.26/1.29	
2.26/1.29	(0) CpxIntTrs
2.26/1.29	(1) Koat Proof [FINISHED, 75 ms]
2.26/1.29	(2) BOUNDS(1, 1)
2.26/1.29	
2.26/1.29	
2.26/1.29	----------------------------------------
2.26/1.29	
2.26/1.29	(0)
2.26/1.29	Obligation:
2.26/1.29	Complexity Int TRS consisting of the following rules:
2.26/1.29	eval_easy1_start(v_0, v_x.0) -> Com_1(eval_easy1_bb0_in(v_0, v_x.0)) :|: TRUE
2.26/1.29	eval_easy1_bb0_in(v_0, v_x.0) -> Com_1(eval_easy1_bb1_in(nondef.0, 0)) :|: TRUE
2.26/1.29	eval_easy1_bb1_in(v_0, v_x.0) -> Com_1(eval_easy1_bb2_in(v_0, v_x.0)) :|: v_x.0 < 40
2.26/1.29	eval_easy1_bb1_in(v_0, v_x.0) -> Com_1(eval_easy1_bb3_in(v_0, v_x.0)) :|: v_x.0 >= 40
2.26/1.29	eval_easy1_bb2_in(v_0, v_x.0) -> Com_1(eval_easy1_bb1_in(v_0, v_x.0 + 1)) :|: v_0 >= 0 && v_0 <= 0
2.26/1.29	eval_easy1_bb2_in(v_0, v_x.0) -> Com_1(eval_easy1_bb1_in(v_0, v_x.0 + 2)) :|: v_0 < 0
2.26/1.29	eval_easy1_bb2_in(v_0, v_x.0) -> Com_1(eval_easy1_bb1_in(v_0, v_x.0 + 2)) :|: v_0 > 0
2.26/1.29	eval_easy1_bb3_in(v_0, v_x.0) -> Com_1(eval_easy1_stop(v_0, v_x.0)) :|: TRUE
2.26/1.29	
2.26/1.29	The start-symbols are:[eval_easy1_start_2]
2.26/1.29	
2.26/1.29	
2.26/1.29	----------------------------------------
2.26/1.29	
2.26/1.29	(1) Koat Proof (FINISHED)
2.26/1.29	YES(?, 166)
2.26/1.29	
2.26/1.29	
2.26/1.29	
2.26/1.29	Initial complexity problem:
2.26/1.29	
2.26/1.29	1:	T:
2.26/1.29	
2.26/1.29			(Comp: ?, Cost: 1)    evaleasy1start(ar_0, ar_1) -> Com_1(evaleasy1bb0in(ar_0, ar_1))
2.26/1.29	
2.26/1.29			(Comp: ?, Cost: 1)    evaleasy1bb0in(ar_0, ar_1) -> Com_1(evaleasy1bb1in(c, 0))
2.26/1.29	
2.26/1.29			(Comp: ?, Cost: 1)    evaleasy1bb1in(ar_0, ar_1) -> Com_1(evaleasy1bb2in(ar_0, ar_1)) [ 39 >= ar_1 ]
2.26/1.29	
2.26/1.29			(Comp: ?, Cost: 1)    evaleasy1bb1in(ar_0, ar_1) -> Com_1(evaleasy1bb3in(ar_0, ar_1)) [ ar_1 >= 40 ]
2.26/1.29	
2.26/1.29			(Comp: ?, Cost: 1)    evaleasy1bb2in(ar_0, ar_1) -> Com_1(evaleasy1bb1in(ar_0, ar_1 + 1)) [ ar_0 = 0 ]
2.26/1.29	
2.26/1.29			(Comp: ?, Cost: 1)    evaleasy1bb2in(ar_0, ar_1) -> Com_1(evaleasy1bb1in(ar_0, ar_1 + 2)) [ 0 >= ar_0 + 1 ]
2.26/1.29	
2.26/1.29			(Comp: ?, Cost: 1)    evaleasy1bb2in(ar_0, ar_1) -> Com_1(evaleasy1bb1in(ar_0, ar_1 + 2)) [ ar_0 >= 1 ]
2.26/1.29	
2.26/1.29			(Comp: ?, Cost: 1)    evaleasy1bb3in(ar_0, ar_1) -> Com_1(evaleasy1stop(ar_0, ar_1))
2.26/1.29	
2.26/1.29			(Comp: 1, Cost: 0)    koat_start(ar_0, ar_1) -> Com_1(evaleasy1start(ar_0, ar_1)) [ 0 <= 0 ]
2.26/1.29	
2.26/1.29		start location:	koat_start
2.26/1.29	
2.26/1.29		leaf cost:	0
2.26/1.29	
2.26/1.29	
2.26/1.29	
2.26/1.29	Repeatedly propagating knowledge in problem 1 produces the following problem:
2.26/1.29	
2.26/1.29	2:	T:
2.26/1.29	
2.26/1.29			(Comp: 1, Cost: 1)    evaleasy1start(ar_0, ar_1) -> Com_1(evaleasy1bb0in(ar_0, ar_1))
2.26/1.29	
2.26/1.29			(Comp: 1, Cost: 1)    evaleasy1bb0in(ar_0, ar_1) -> Com_1(evaleasy1bb1in(c, 0))
2.26/1.29	
2.26/1.29			(Comp: ?, Cost: 1)    evaleasy1bb1in(ar_0, ar_1) -> Com_1(evaleasy1bb2in(ar_0, ar_1)) [ 39 >= ar_1 ]
2.26/1.29	
2.26/1.29			(Comp: ?, Cost: 1)    evaleasy1bb1in(ar_0, ar_1) -> Com_1(evaleasy1bb3in(ar_0, ar_1)) [ ar_1 >= 40 ]
2.26/1.29	
2.26/1.29			(Comp: ?, Cost: 1)    evaleasy1bb2in(ar_0, ar_1) -> Com_1(evaleasy1bb1in(ar_0, ar_1 + 1)) [ ar_0 = 0 ]
2.26/1.29	
2.26/1.29			(Comp: ?, Cost: 1)    evaleasy1bb2in(ar_0, ar_1) -> Com_1(evaleasy1bb1in(ar_0, ar_1 + 2)) [ 0 >= ar_0 + 1 ]
2.26/1.29	
2.26/1.29			(Comp: ?, Cost: 1)    evaleasy1bb2in(ar_0, ar_1) -> Com_1(evaleasy1bb1in(ar_0, ar_1 + 2)) [ ar_0 >= 1 ]
2.26/1.29	
2.26/1.29			(Comp: ?, Cost: 1)    evaleasy1bb3in(ar_0, ar_1) -> Com_1(evaleasy1stop(ar_0, ar_1))
2.26/1.29	
2.26/1.29			(Comp: 1, Cost: 0)    koat_start(ar_0, ar_1) -> Com_1(evaleasy1start(ar_0, ar_1)) [ 0 <= 0 ]
2.26/1.29	
2.26/1.29		start location:	koat_start
2.26/1.29	
2.26/1.29		leaf cost:	0
2.26/1.29	
2.26/1.29	
2.26/1.29	
2.26/1.29	A polynomial rank function with
2.26/1.29	
2.26/1.29		Pol(evaleasy1start) = 2
2.26/1.29	
2.26/1.29		Pol(evaleasy1bb0in) = 2
2.26/1.29	
2.26/1.29		Pol(evaleasy1bb1in) = 2
2.26/1.29	
2.26/1.29		Pol(evaleasy1bb2in) = 2
2.26/1.29	
2.26/1.29		Pol(evaleasy1bb3in) = 1
2.26/1.29	
2.26/1.29		Pol(evaleasy1stop) = 0
2.26/1.29	
2.26/1.29		Pol(koat_start) = 2
2.26/1.29	
2.26/1.29	orients all transitions weakly and the transitions
2.26/1.29	
2.26/1.29		evaleasy1bb3in(ar_0, ar_1) -> Com_1(evaleasy1stop(ar_0, ar_1))
2.26/1.29	
2.26/1.29		evaleasy1bb1in(ar_0, ar_1) -> Com_1(evaleasy1bb3in(ar_0, ar_1)) [ ar_1 >= 40 ]
2.26/1.29	
2.26/1.29	strictly and produces the following problem:
2.26/1.29	
2.26/1.29	3:	T:
2.26/1.29	
2.26/1.29			(Comp: 1, Cost: 1)    evaleasy1start(ar_0, ar_1) -> Com_1(evaleasy1bb0in(ar_0, ar_1))
2.26/1.29	
2.26/1.29			(Comp: 1, Cost: 1)    evaleasy1bb0in(ar_0, ar_1) -> Com_1(evaleasy1bb1in(c, 0))
2.26/1.29	
2.26/1.29			(Comp: ?, Cost: 1)    evaleasy1bb1in(ar_0, ar_1) -> Com_1(evaleasy1bb2in(ar_0, ar_1)) [ 39 >= ar_1 ]
2.26/1.29	
2.26/1.29			(Comp: 2, Cost: 1)    evaleasy1bb1in(ar_0, ar_1) -> Com_1(evaleasy1bb3in(ar_0, ar_1)) [ ar_1 >= 40 ]
2.26/1.29	
2.26/1.29			(Comp: ?, Cost: 1)    evaleasy1bb2in(ar_0, ar_1) -> Com_1(evaleasy1bb1in(ar_0, ar_1 + 1)) [ ar_0 = 0 ]
2.26/1.29	
2.26/1.29			(Comp: ?, Cost: 1)    evaleasy1bb2in(ar_0, ar_1) -> Com_1(evaleasy1bb1in(ar_0, ar_1 + 2)) [ 0 >= ar_0 + 1 ]
2.26/1.29	
2.26/1.29			(Comp: ?, Cost: 1)    evaleasy1bb2in(ar_0, ar_1) -> Com_1(evaleasy1bb1in(ar_0, ar_1 + 2)) [ ar_0 >= 1 ]
2.26/1.29	
2.26/1.29			(Comp: 2, Cost: 1)    evaleasy1bb3in(ar_0, ar_1) -> Com_1(evaleasy1stop(ar_0, ar_1))
2.26/1.29	
2.26/1.29			(Comp: 1, Cost: 0)    koat_start(ar_0, ar_1) -> Com_1(evaleasy1start(ar_0, ar_1)) [ 0 <= 0 ]
2.26/1.29	
2.26/1.29		start location:	koat_start
2.26/1.29	
2.26/1.29		leaf cost:	0
2.26/1.29	
2.26/1.29	
2.26/1.29	
2.26/1.29	A polynomial rank function with
2.26/1.29	
2.26/1.29		Pol(evaleasy1start) = 40
2.26/1.29	
2.26/1.29		Pol(evaleasy1bb0in) = 40
2.26/1.29	
2.26/1.29		Pol(evaleasy1bb1in) = -V_2 + 40
2.26/1.29	
2.26/1.29		Pol(evaleasy1bb2in) = -V_2 + 39
2.26/1.29	
2.26/1.29		Pol(evaleasy1bb3in) = -V_2
2.26/1.29	
2.26/1.29		Pol(evaleasy1stop) = -V_2
2.26/1.29	
2.26/1.29		Pol(koat_start) = 40
2.26/1.29	
2.26/1.29	orients all transitions weakly and the transition
2.26/1.29	
2.26/1.29		evaleasy1bb1in(ar_0, ar_1) -> Com_1(evaleasy1bb2in(ar_0, ar_1)) [ 39 >= ar_1 ]
2.26/1.29	
2.26/1.29	strictly and produces the following problem:
2.26/1.29	
2.26/1.29	4:	T:
2.26/1.29	
2.26/1.29			(Comp: 1, Cost: 1)     evaleasy1start(ar_0, ar_1) -> Com_1(evaleasy1bb0in(ar_0, ar_1))
2.26/1.30	
2.26/1.30			(Comp: 1, Cost: 1)     evaleasy1bb0in(ar_0, ar_1) -> Com_1(evaleasy1bb1in(c, 0))
2.26/1.30	
2.26/1.30			(Comp: 40, Cost: 1)    evaleasy1bb1in(ar_0, ar_1) -> Com_1(evaleasy1bb2in(ar_0, ar_1)) [ 39 >= ar_1 ]
2.26/1.30	
2.26/1.30			(Comp: 2, Cost: 1)     evaleasy1bb1in(ar_0, ar_1) -> Com_1(evaleasy1bb3in(ar_0, ar_1)) [ ar_1 >= 40 ]
2.26/1.30	
2.26/1.30			(Comp: ?, Cost: 1)     evaleasy1bb2in(ar_0, ar_1) -> Com_1(evaleasy1bb1in(ar_0, ar_1 + 1)) [ ar_0 = 0 ]
2.26/1.30	
2.26/1.30			(Comp: ?, Cost: 1)     evaleasy1bb2in(ar_0, ar_1) -> Com_1(evaleasy1bb1in(ar_0, ar_1 + 2)) [ 0 >= ar_0 + 1 ]
2.26/1.30	
2.26/1.30			(Comp: ?, Cost: 1)     evaleasy1bb2in(ar_0, ar_1) -> Com_1(evaleasy1bb1in(ar_0, ar_1 + 2)) [ ar_0 >= 1 ]
2.26/1.30	
2.26/1.30			(Comp: 2, Cost: 1)     evaleasy1bb3in(ar_0, ar_1) -> Com_1(evaleasy1stop(ar_0, ar_1))
2.26/1.30	
2.26/1.30			(Comp: 1, Cost: 0)     koat_start(ar_0, ar_1) -> Com_1(evaleasy1start(ar_0, ar_1)) [ 0 <= 0 ]
2.26/1.30	
2.26/1.30		start location:	koat_start
2.26/1.30	
2.26/1.30		leaf cost:	0
2.26/1.30	
2.26/1.30	
2.26/1.30	
2.26/1.30	Repeatedly propagating knowledge in problem 4 produces the following problem:
2.26/1.30	
2.26/1.30	5:	T:
2.26/1.30	
2.26/1.30			(Comp: 1, Cost: 1)     evaleasy1start(ar_0, ar_1) -> Com_1(evaleasy1bb0in(ar_0, ar_1))
2.26/1.30	
2.26/1.30			(Comp: 1, Cost: 1)     evaleasy1bb0in(ar_0, ar_1) -> Com_1(evaleasy1bb1in(c, 0))
2.26/1.30	
2.26/1.30			(Comp: 40, Cost: 1)    evaleasy1bb1in(ar_0, ar_1) -> Com_1(evaleasy1bb2in(ar_0, ar_1)) [ 39 >= ar_1 ]
2.26/1.30	
2.26/1.30			(Comp: 2, Cost: 1)     evaleasy1bb1in(ar_0, ar_1) -> Com_1(evaleasy1bb3in(ar_0, ar_1)) [ ar_1 >= 40 ]
2.26/1.30	
2.26/1.30			(Comp: 40, Cost: 1)    evaleasy1bb2in(ar_0, ar_1) -> Com_1(evaleasy1bb1in(ar_0, ar_1 + 1)) [ ar_0 = 0 ]
2.26/1.30	
2.26/1.30			(Comp: 40, Cost: 1)    evaleasy1bb2in(ar_0, ar_1) -> Com_1(evaleasy1bb1in(ar_0, ar_1 + 2)) [ 0 >= ar_0 + 1 ]
2.26/1.30	
2.26/1.30			(Comp: 40, Cost: 1)    evaleasy1bb2in(ar_0, ar_1) -> Com_1(evaleasy1bb1in(ar_0, ar_1 + 2)) [ ar_0 >= 1 ]
2.26/1.30	
2.26/1.30			(Comp: 2, Cost: 1)     evaleasy1bb3in(ar_0, ar_1) -> Com_1(evaleasy1stop(ar_0, ar_1))
2.26/1.30	
2.26/1.30			(Comp: 1, Cost: 0)     koat_start(ar_0, ar_1) -> Com_1(evaleasy1start(ar_0, ar_1)) [ 0 <= 0 ]
2.26/1.30	
2.26/1.30		start location:	koat_start
2.26/1.30	
2.26/1.30		leaf cost:	0
2.26/1.30	
2.26/1.30	
2.26/1.30	
2.26/1.30	Complexity upper bound 166
2.26/1.30	
2.26/1.30	
2.26/1.30	
2.26/1.30	Time: 0.074 sec (SMT: 0.067 sec)
2.26/1.30	
2.26/1.30	
2.26/1.30	----------------------------------------
2.26/1.30	
2.26/1.30	(2)
2.26/1.30	BOUNDS(1, 1)
2.26/1.31	EOF