3.26/1.64	WORST_CASE(?, O(1))
3.26/1.65	proof of /export/starexec/sandbox/benchmark/theBenchmark.koat
3.26/1.65	# AProVE Commit ID: 48fb2092695e11cc9f56e44b17a92a5f88ffb256 marcel 20180622 unpublished dirty
3.26/1.65	
3.26/1.65	
3.26/1.65	The runtime complexity of the given CpxIntTrs could be proven to be BOUNDS(1, 1).
3.26/1.65	
3.26/1.65	(0) CpxIntTrs
3.26/1.65	(1) Koat Proof [FINISHED, 11 ms]
3.26/1.65	(2) BOUNDS(1, 1)
3.26/1.65	
3.26/1.65	
3.26/1.65	----------------------------------------
3.26/1.65	
3.26/1.65	(0)
3.26/1.65	Obligation:
3.26/1.65	Complexity Int TRS consisting of the following rules:
3.26/1.65	evalndloopstart(A) -> Com_1(evalndloopentryin(A)) :|: TRUE
3.26/1.65	evalndloopentryin(A) -> Com_1(evalndloopbbin(0)) :|: TRUE
3.26/1.65	evalndloopbbin(A) -> Com_1(evalndloopbbin(B)) :|: 2 + A >= B && B >= A + 1 && 9 >= B
3.26/1.65	evalndloopbbin(A) -> Com_1(evalndloopreturnin(A)) :|: B >= A + 3
3.26/1.65	evalndloopbbin(A) -> Com_1(evalndloopreturnin(A)) :|: A >= B
3.26/1.65	evalndloopbbin(A) -> Com_1(evalndloopreturnin(A)) :|: B >= 10
3.26/1.65	evalndloopreturnin(A) -> Com_1(evalndloopstop(A)) :|: TRUE
3.26/1.65	
3.26/1.65	The start-symbols are:[evalndloopstart_1]
3.26/1.65	
3.26/1.65	
3.26/1.65	----------------------------------------
3.26/1.65	
3.26/1.65	(1) Koat Proof (FINISHED)
3.26/1.65	YES(?, 19)
3.26/1.65	
3.26/1.65	
3.26/1.65	
3.26/1.65	Initial complexity problem:
3.26/1.65	
3.26/1.65	1:	T:
3.26/1.65	
3.26/1.65			(Comp: ?, Cost: 1)    evalndloopstart(ar_0) -> Com_1(evalndloopentryin(ar_0))
3.26/1.65	
3.26/1.65			(Comp: ?, Cost: 1)    evalndloopentryin(ar_0) -> Com_1(evalndloopbbin(0))
3.26/1.65	
3.26/1.65			(Comp: ?, Cost: 1)    evalndloopbbin(ar_0) -> Com_1(evalndloopbbin(b)) [ ar_0 + 2 >= b /\ b >= ar_0 + 1 /\ 9 >= b ]
3.26/1.65	
3.26/1.65			(Comp: ?, Cost: 1)    evalndloopbbin(ar_0) -> Com_1(evalndloopreturnin(ar_0)) [ b >= ar_0 + 3 ]
3.26/1.65	
3.26/1.65			(Comp: ?, Cost: 1)    evalndloopbbin(ar_0) -> Com_1(evalndloopreturnin(ar_0)) [ ar_0 >= b ]
3.26/1.65	
3.26/1.65			(Comp: ?, Cost: 1)    evalndloopbbin(ar_0) -> Com_1(evalndloopreturnin(ar_0)) [ b >= 10 ]
3.26/1.65	
3.26/1.65			(Comp: ?, Cost: 1)    evalndloopreturnin(ar_0) -> Com_1(evalndloopstop(ar_0))
3.26/1.65	
3.26/1.65			(Comp: 1, Cost: 0)    koat_start(ar_0) -> Com_1(evalndloopstart(ar_0)) [ 0 <= 0 ]
3.26/1.65	
3.26/1.65		start location:	koat_start
3.26/1.65	
3.26/1.65		leaf cost:	0
3.26/1.65	
3.26/1.65	
3.26/1.65	
3.26/1.65	Repeatedly propagating knowledge in problem 1 produces the following problem:
3.26/1.65	
3.26/1.65	2:	T:
3.26/1.65	
3.26/1.65			(Comp: 1, Cost: 1)    evalndloopstart(ar_0) -> Com_1(evalndloopentryin(ar_0))
3.26/1.65	
3.26/1.65			(Comp: 1, Cost: 1)    evalndloopentryin(ar_0) -> Com_1(evalndloopbbin(0))
3.26/1.65	
3.26/1.65			(Comp: ?, Cost: 1)    evalndloopbbin(ar_0) -> Com_1(evalndloopbbin(b)) [ ar_0 + 2 >= b /\ b >= ar_0 + 1 /\ 9 >= b ]
3.26/1.65	
3.26/1.65			(Comp: ?, Cost: 1)    evalndloopbbin(ar_0) -> Com_1(evalndloopreturnin(ar_0)) [ b >= ar_0 + 3 ]
3.26/1.65	
3.26/1.65			(Comp: ?, Cost: 1)    evalndloopbbin(ar_0) -> Com_1(evalndloopreturnin(ar_0)) [ ar_0 >= b ]
3.26/1.65	
3.26/1.65			(Comp: ?, Cost: 1)    evalndloopbbin(ar_0) -> Com_1(evalndloopreturnin(ar_0)) [ b >= 10 ]
3.26/1.65	
3.26/1.65			(Comp: ?, Cost: 1)    evalndloopreturnin(ar_0) -> Com_1(evalndloopstop(ar_0))
3.26/1.65	
3.26/1.65			(Comp: 1, Cost: 0)    koat_start(ar_0) -> Com_1(evalndloopstart(ar_0)) [ 0 <= 0 ]
3.26/1.65	
3.26/1.65		start location:	koat_start
3.26/1.65	
3.26/1.65		leaf cost:	0
3.26/1.65	
3.26/1.65	
3.26/1.65	
3.26/1.65	A polynomial rank function with
3.26/1.65	
3.26/1.65		Pol(evalndloopstart) = 2
3.26/1.65	
3.26/1.65		Pol(evalndloopentryin) = 2
3.26/1.65	
3.26/1.65		Pol(evalndloopbbin) = 2
3.26/1.65	
3.26/1.65		Pol(evalndloopreturnin) = 1
3.26/1.65	
3.26/1.65		Pol(evalndloopstop) = 0
3.26/1.65	
3.26/1.65		Pol(koat_start) = 2
3.26/1.65	
3.26/1.65	orients all transitions weakly and the transitions
3.26/1.65	
3.26/1.65		evalndloopreturnin(ar_0) -> Com_1(evalndloopstop(ar_0))
3.26/1.65	
3.26/1.65		evalndloopbbin(ar_0) -> Com_1(evalndloopreturnin(ar_0)) [ b >= 10 ]
3.26/1.65	
3.26/1.65		evalndloopbbin(ar_0) -> Com_1(evalndloopreturnin(ar_0)) [ b >= ar_0 + 3 ]
3.26/1.65	
3.26/1.65		evalndloopbbin(ar_0) -> Com_1(evalndloopreturnin(ar_0)) [ ar_0 >= b ]
3.26/1.65	
3.26/1.65	strictly and produces the following problem:
3.26/1.65	
3.26/1.65	3:	T:
3.26/1.65	
3.26/1.65			(Comp: 1, Cost: 1)    evalndloopstart(ar_0) -> Com_1(evalndloopentryin(ar_0))
3.26/1.65	
3.26/1.65			(Comp: 1, Cost: 1)    evalndloopentryin(ar_0) -> Com_1(evalndloopbbin(0))
3.26/1.65	
3.26/1.65			(Comp: ?, Cost: 1)    evalndloopbbin(ar_0) -> Com_1(evalndloopbbin(b)) [ ar_0 + 2 >= b /\ b >= ar_0 + 1 /\ 9 >= b ]
3.26/1.65	
3.26/1.65			(Comp: 2, Cost: 1)    evalndloopbbin(ar_0) -> Com_1(evalndloopreturnin(ar_0)) [ b >= ar_0 + 3 ]
3.26/1.65	
3.26/1.65			(Comp: 2, Cost: 1)    evalndloopbbin(ar_0) -> Com_1(evalndloopreturnin(ar_0)) [ ar_0 >= b ]
3.26/1.65	
3.26/1.65			(Comp: 2, Cost: 1)    evalndloopbbin(ar_0) -> Com_1(evalndloopreturnin(ar_0)) [ b >= 10 ]
3.26/1.65	
3.26/1.65			(Comp: 2, Cost: 1)    evalndloopreturnin(ar_0) -> Com_1(evalndloopstop(ar_0))
3.26/1.65	
3.26/1.65			(Comp: 1, Cost: 0)    koat_start(ar_0) -> Com_1(evalndloopstart(ar_0)) [ 0 <= 0 ]
3.26/1.65	
3.26/1.65		start location:	koat_start
3.26/1.65	
3.26/1.65		leaf cost:	0
3.26/1.65	
3.26/1.65	
3.26/1.65	
3.26/1.65	A polynomial rank function with
3.26/1.65	
3.26/1.65		Pol(evalndloopstart) = 9
3.26/1.65	
3.26/1.65		Pol(evalndloopentryin) = 9
3.26/1.65	
3.26/1.65		Pol(evalndloopbbin) = -V_1 + 9
3.26/1.65	
3.26/1.65		Pol(evalndloopreturnin) = -V_1
3.26/1.65	
3.26/1.65		Pol(evalndloopstop) = -V_1
3.26/1.65	
3.26/1.65		Pol(koat_start) = 9
3.26/1.65	
3.26/1.65	orients all transitions weakly and the transition
3.26/1.65	
3.26/1.65		evalndloopbbin(ar_0) -> Com_1(evalndloopbbin(b)) [ ar_0 + 2 >= b /\ b >= ar_0 + 1 /\ 9 >= b ]
3.26/1.65	
3.26/1.65	strictly and produces the following problem:
3.26/1.65	
3.26/1.65	4:	T:
3.26/1.65	
3.26/1.65			(Comp: 1, Cost: 1)    evalndloopstart(ar_0) -> Com_1(evalndloopentryin(ar_0))
3.26/1.65	
3.26/1.65			(Comp: 1, Cost: 1)    evalndloopentryin(ar_0) -> Com_1(evalndloopbbin(0))
3.26/1.65	
3.26/1.65			(Comp: 9, Cost: 1)    evalndloopbbin(ar_0) -> Com_1(evalndloopbbin(b)) [ ar_0 + 2 >= b /\ b >= ar_0 + 1 /\ 9 >= b ]
3.26/1.65	
3.26/1.65			(Comp: 2, Cost: 1)    evalndloopbbin(ar_0) -> Com_1(evalndloopreturnin(ar_0)) [ b >= ar_0 + 3 ]
3.26/1.65	
3.26/1.65			(Comp: 2, Cost: 1)    evalndloopbbin(ar_0) -> Com_1(evalndloopreturnin(ar_0)) [ ar_0 >= b ]
3.26/1.65	
3.26/1.65			(Comp: 2, Cost: 1)    evalndloopbbin(ar_0) -> Com_1(evalndloopreturnin(ar_0)) [ b >= 10 ]
3.26/1.65	
3.26/1.65			(Comp: 2, Cost: 1)    evalndloopreturnin(ar_0) -> Com_1(evalndloopstop(ar_0))
3.26/1.65	
3.26/1.65			(Comp: 1, Cost: 0)    koat_start(ar_0) -> Com_1(evalndloopstart(ar_0)) [ 0 <= 0 ]
3.26/1.65	
3.26/1.65		start location:	koat_start
3.26/1.65	
3.26/1.65		leaf cost:	0
3.26/1.65	
3.26/1.65	
3.26/1.65	
3.26/1.65	Complexity upper bound 19
3.26/1.65	
3.26/1.65	
3.26/1.65	
3.26/1.65	Time: 0.060 sec (SMT: 0.056 sec)
3.26/1.65	
3.26/1.65	
3.26/1.65	----------------------------------------
3.26/1.65	
3.26/1.65	(2)
3.26/1.65	BOUNDS(1, 1)
3.26/1.66	EOF