5.36/2.45	WORST_CASE(Omega(n^1), O(n^1))
5.36/2.46	proof of /export/starexec/sandbox/benchmark/theBenchmark.koat
5.36/2.46	# AProVE Commit ID: 48fb2092695e11cc9f56e44b17a92a5f88ffb256 marcel 20180622 unpublished dirty
5.36/2.46	
5.36/2.46	
5.36/2.46	The runtime complexity of the given CpxIntTrs could be proven to be BOUNDS(n^1, n^1).
5.36/2.46	
5.36/2.46	(0) CpxIntTrs
5.36/2.46	(1) Koat Proof [FINISHED, 208 ms]
5.36/2.46	(2) BOUNDS(1, n^1)
5.36/2.46	(3) Loat Proof [FINISHED, 811 ms]
5.36/2.46	(4) BOUNDS(n^1, INF)
5.36/2.46	
5.36/2.46	
5.36/2.46	----------------------------------------
5.36/2.46	
5.36/2.46	(0)
5.36/2.46	Obligation:
5.36/2.46	Complexity Int TRS consisting of the following rules:
5.36/2.46	evalfstart(A, B, C) -> Com_1(evalfentryin(A, B, C)) :|: TRUE
5.36/2.46	evalfentryin(A, B, C) -> Com_1(evalfbb3in(B, A, 0)) :|: A >= 1 && B >= 1
5.36/2.46	evalfbb3in(A, B, C) -> Com_1(evalfreturnin(A, B, C)) :|: 0 >= B
5.36/2.46	evalfbb3in(A, B, C) -> Com_1(evalfbb4in(A, B, C)) :|: B >= 1
5.36/2.46	evalfbb4in(A, B, C) -> Com_1(evalfbbin(A, B, C)) :|: 0 >= D + 1
5.36/2.46	evalfbb4in(A, B, C) -> Com_1(evalfbbin(A, B, C)) :|: D >= 1
5.36/2.46	evalfbb4in(A, B, C) -> Com_1(evalfreturnin(A, B, C)) :|: TRUE
5.36/2.46	evalfbbin(A, B, C) -> Com_1(evalfbb1in(A, B, C)) :|: A >= C + 1
5.36/2.46	evalfbbin(A, B, C) -> Com_1(evalfbb3in(A, B, 0)) :|: C >= A
5.36/2.46	evalfbb1in(A, B, C) -> Com_1(evalfbb3in(A, B - 1, C + 1)) :|: TRUE
5.36/2.46	evalfreturnin(A, B, C) -> Com_1(evalfstop(A, B, C)) :|: TRUE
5.36/2.46	
5.36/2.46	The start-symbols are:[evalfstart_3]
5.36/2.46	
5.36/2.46	
5.36/2.46	----------------------------------------
5.36/2.46	
5.36/2.46	(1) Koat Proof (FINISHED)
5.36/2.46	YES(?, 42*ar_0 + 14)
5.36/2.46	
5.36/2.46	
5.36/2.46	
5.36/2.46	Initial complexity problem:
5.36/2.46	
5.36/2.46	1:	T:
5.36/2.46	
5.36/2.46			(Comp: ?, Cost: 1)    evalfstart(ar_0, ar_1, ar_2) -> Com_1(evalfentryin(ar_0, ar_1, ar_2))
5.36/2.46	
5.36/2.46			(Comp: ?, Cost: 1)    evalfentryin(ar_0, ar_1, ar_2) -> Com_1(evalfbb3in(ar_1, ar_0, 0)) [ ar_0 >= 1 /\ ar_1 >= 1 ]
5.36/2.46	
5.36/2.46			(Comp: ?, Cost: 1)    evalfbb3in(ar_0, ar_1, ar_2) -> Com_1(evalfreturnin(ar_0, ar_1, ar_2)) [ 0 >= ar_1 ]
5.36/2.46	
5.36/2.46			(Comp: ?, Cost: 1)    evalfbb3in(ar_0, ar_1, ar_2) -> Com_1(evalfbb4in(ar_0, ar_1, ar_2)) [ ar_1 >= 1 ]
5.36/2.46	
5.36/2.46			(Comp: ?, Cost: 1)    evalfbb4in(ar_0, ar_1, ar_2) -> Com_1(evalfbbin(ar_0, ar_1, ar_2)) [ 0 >= d + 1 ]
5.36/2.46	
5.36/2.46			(Comp: ?, Cost: 1)    evalfbb4in(ar_0, ar_1, ar_2) -> Com_1(evalfbbin(ar_0, ar_1, ar_2)) [ d >= 1 ]
5.36/2.46	
5.36/2.46			(Comp: ?, Cost: 1)    evalfbb4in(ar_0, ar_1, ar_2) -> Com_1(evalfreturnin(ar_0, ar_1, ar_2))
5.36/2.46	
5.36/2.46			(Comp: ?, Cost: 1)    evalfbbin(ar_0, ar_1, ar_2) -> Com_1(evalfbb1in(ar_0, ar_1, ar_2)) [ ar_0 >= ar_2 + 1 ]
5.36/2.46	
5.36/2.46			(Comp: ?, Cost: 1)    evalfbbin(ar_0, ar_1, ar_2) -> Com_1(evalfbb3in(ar_0, ar_1, 0)) [ ar_2 >= ar_0 ]
5.36/2.46	
5.36/2.46			(Comp: ?, Cost: 1)    evalfbb1in(ar_0, ar_1, ar_2) -> Com_1(evalfbb3in(ar_0, ar_1 - 1, ar_2 + 1))
5.36/2.46	
5.36/2.46			(Comp: ?, Cost: 1)    evalfreturnin(ar_0, ar_1, ar_2) -> Com_1(evalfstop(ar_0, ar_1, ar_2))
5.36/2.46	
5.36/2.46			(Comp: 1, Cost: 0)    koat_start(ar_0, ar_1, ar_2) -> Com_1(evalfstart(ar_0, ar_1, ar_2)) [ 0 <= 0 ]
5.36/2.46	
5.36/2.46		start location:	koat_start
5.36/2.46	
5.36/2.46		leaf cost:	0
5.36/2.46	
5.36/2.46	
5.36/2.46	
5.36/2.46	Repeatedly propagating knowledge in problem 1 produces the following problem:
5.36/2.46	
5.36/2.46	2:	T:
5.36/2.46	
5.36/2.46			(Comp: 1, Cost: 1)    evalfstart(ar_0, ar_1, ar_2) -> Com_1(evalfentryin(ar_0, ar_1, ar_2))
5.36/2.46	
5.36/2.46			(Comp: 1, Cost: 1)    evalfentryin(ar_0, ar_1, ar_2) -> Com_1(evalfbb3in(ar_1, ar_0, 0)) [ ar_0 >= 1 /\ ar_1 >= 1 ]
5.36/2.46	
5.36/2.46			(Comp: ?, Cost: 1)    evalfbb3in(ar_0, ar_1, ar_2) -> Com_1(evalfreturnin(ar_0, ar_1, ar_2)) [ 0 >= ar_1 ]
5.36/2.46	
5.36/2.46			(Comp: ?, Cost: 1)    evalfbb3in(ar_0, ar_1, ar_2) -> Com_1(evalfbb4in(ar_0, ar_1, ar_2)) [ ar_1 >= 1 ]
5.36/2.46	
5.36/2.46			(Comp: ?, Cost: 1)    evalfbb4in(ar_0, ar_1, ar_2) -> Com_1(evalfbbin(ar_0, ar_1, ar_2)) [ 0 >= d + 1 ]
5.36/2.46	
5.36/2.46			(Comp: ?, Cost: 1)    evalfbb4in(ar_0, ar_1, ar_2) -> Com_1(evalfbbin(ar_0, ar_1, ar_2)) [ d >= 1 ]
5.36/2.46	
5.36/2.46			(Comp: ?, Cost: 1)    evalfbb4in(ar_0, ar_1, ar_2) -> Com_1(evalfreturnin(ar_0, ar_1, ar_2))
5.36/2.46	
5.36/2.46			(Comp: ?, Cost: 1)    evalfbbin(ar_0, ar_1, ar_2) -> Com_1(evalfbb1in(ar_0, ar_1, ar_2)) [ ar_0 >= ar_2 + 1 ]
5.36/2.46	
5.36/2.46			(Comp: ?, Cost: 1)    evalfbbin(ar_0, ar_1, ar_2) -> Com_1(evalfbb3in(ar_0, ar_1, 0)) [ ar_2 >= ar_0 ]
5.36/2.46	
5.36/2.46			(Comp: ?, Cost: 1)    evalfbb1in(ar_0, ar_1, ar_2) -> Com_1(evalfbb3in(ar_0, ar_1 - 1, ar_2 + 1))
5.36/2.46	
5.36/2.46			(Comp: ?, Cost: 1)    evalfreturnin(ar_0, ar_1, ar_2) -> Com_1(evalfstop(ar_0, ar_1, ar_2))
5.36/2.46	
5.36/2.46			(Comp: 1, Cost: 0)    koat_start(ar_0, ar_1, ar_2) -> Com_1(evalfstart(ar_0, ar_1, ar_2)) [ 0 <= 0 ]
5.36/2.46	
5.36/2.46		start location:	koat_start
5.36/2.46	
5.36/2.46		leaf cost:	0
5.36/2.46	
5.36/2.46	
5.36/2.46	
5.36/2.46	A polynomial rank function with
5.36/2.46	
5.36/2.46		Pol(evalfstart) = 2
5.36/2.46	
5.36/2.46		Pol(evalfentryin) = 2
5.36/2.46	
5.36/2.46		Pol(evalfbb3in) = 2
5.36/2.46	
5.36/2.46		Pol(evalfreturnin) = 1
5.36/2.46	
5.36/2.46		Pol(evalfbb4in) = 2
5.36/2.46	
5.36/2.46		Pol(evalfbbin) = 2
5.36/2.46	
5.36/2.46		Pol(evalfbb1in) = 2
5.36/2.46	
5.36/2.46		Pol(evalfstop) = 0
5.36/2.46	
5.36/2.46		Pol(koat_start) = 2
5.36/2.46	
5.36/2.46	orients all transitions weakly and the transitions
5.36/2.46	
5.36/2.46		evalfreturnin(ar_0, ar_1, ar_2) -> Com_1(evalfstop(ar_0, ar_1, ar_2))
5.36/2.46	
5.36/2.46		evalfbb4in(ar_0, ar_1, ar_2) -> Com_1(evalfreturnin(ar_0, ar_1, ar_2))
5.36/2.46	
5.36/2.46		evalfbb3in(ar_0, ar_1, ar_2) -> Com_1(evalfreturnin(ar_0, ar_1, ar_2)) [ 0 >= ar_1 ]
5.36/2.46	
5.36/2.46	strictly and produces the following problem:
5.36/2.46	
5.36/2.46	3:	T:
5.36/2.46	
5.36/2.46			(Comp: 1, Cost: 1)    evalfstart(ar_0, ar_1, ar_2) -> Com_1(evalfentryin(ar_0, ar_1, ar_2))
5.36/2.46	
5.36/2.46			(Comp: 1, Cost: 1)    evalfentryin(ar_0, ar_1, ar_2) -> Com_1(evalfbb3in(ar_1, ar_0, 0)) [ ar_0 >= 1 /\ ar_1 >= 1 ]
5.36/2.46	
5.36/2.46			(Comp: 2, Cost: 1)    evalfbb3in(ar_0, ar_1, ar_2) -> Com_1(evalfreturnin(ar_0, ar_1, ar_2)) [ 0 >= ar_1 ]
5.36/2.46	
5.36/2.46			(Comp: ?, Cost: 1)    evalfbb3in(ar_0, ar_1, ar_2) -> Com_1(evalfbb4in(ar_0, ar_1, ar_2)) [ ar_1 >= 1 ]
5.36/2.46	
5.36/2.46			(Comp: ?, Cost: 1)    evalfbb4in(ar_0, ar_1, ar_2) -> Com_1(evalfbbin(ar_0, ar_1, ar_2)) [ 0 >= d + 1 ]
5.36/2.46	
5.36/2.46			(Comp: ?, Cost: 1)    evalfbb4in(ar_0, ar_1, ar_2) -> Com_1(evalfbbin(ar_0, ar_1, ar_2)) [ d >= 1 ]
5.36/2.46	
5.36/2.46			(Comp: 2, Cost: 1)    evalfbb4in(ar_0, ar_1, ar_2) -> Com_1(evalfreturnin(ar_0, ar_1, ar_2))
5.36/2.46	
5.36/2.46			(Comp: ?, Cost: 1)    evalfbbin(ar_0, ar_1, ar_2) -> Com_1(evalfbb1in(ar_0, ar_1, ar_2)) [ ar_0 >= ar_2 + 1 ]
5.36/2.46	
5.36/2.46			(Comp: ?, Cost: 1)    evalfbbin(ar_0, ar_1, ar_2) -> Com_1(evalfbb3in(ar_0, ar_1, 0)) [ ar_2 >= ar_0 ]
5.36/2.46	
5.36/2.46			(Comp: ?, Cost: 1)    evalfbb1in(ar_0, ar_1, ar_2) -> Com_1(evalfbb3in(ar_0, ar_1 - 1, ar_2 + 1))
5.36/2.46	
5.36/2.46			(Comp: 2, Cost: 1)    evalfreturnin(ar_0, ar_1, ar_2) -> Com_1(evalfstop(ar_0, ar_1, ar_2))
5.36/2.46	
5.36/2.46			(Comp: 1, Cost: 0)    koat_start(ar_0, ar_1, ar_2) -> Com_1(evalfstart(ar_0, ar_1, ar_2)) [ 0 <= 0 ]
5.36/2.46	
5.36/2.46		start location:	koat_start
5.36/2.46	
5.36/2.46		leaf cost:	0
5.36/2.46	
5.36/2.46	
5.36/2.46	
5.36/2.46	Applied AI with 'oct' on problem 3 to obtain the following invariants:
5.36/2.46	
5.36/2.46	  For symbol evalfbb1in: X_1 - X_3 - 1 >= 0 /\ X_3 >= 0 /\ X_2 + X_3 - 1 >= 0 /\ X_1 + X_3 - 1 >= 0 /\ X_2 - 1 >= 0 /\ X_1 + X_2 - 2 >= 0 /\ X_1 - 1 >= 0
5.36/2.46	
5.36/2.46	  For symbol evalfbb3in: X_3 >= 0 /\ X_2 + X_3 - 1 >= 0 /\ X_1 + X_3 - 1 >= 0 /\ X_1 - 1 >= 0
5.36/2.46	
5.36/2.46	  For symbol evalfbb4in: X_3 >= 0 /\ X_2 + X_3 - 1 >= 0 /\ X_1 + X_3 - 1 >= 0 /\ X_2 - 1 >= 0 /\ X_1 + X_2 - 2 >= 0 /\ X_1 - 1 >= 0
5.36/2.46	
5.36/2.46	  For symbol evalfbbin: X_3 >= 0 /\ X_2 + X_3 - 1 >= 0 /\ X_1 + X_3 - 1 >= 0 /\ X_2 - 1 >= 0 /\ X_1 + X_2 - 2 >= 0 /\ X_1 - 1 >= 0
5.36/2.46	
5.36/2.46	  For symbol evalfreturnin: X_3 >= 0 /\ X_2 + X_3 - 1 >= 0 /\ X_1 + X_3 - 1 >= 0 /\ X_1 - 1 >= 0
5.36/2.46	
5.36/2.46	
5.36/2.46	
5.36/2.46	
5.36/2.46	
5.36/2.46	This yielded the following problem:
5.36/2.46	
5.36/2.46	4:	T:
5.36/2.46	
5.36/2.46			(Comp: 1, Cost: 0)    koat_start(ar_0, ar_1, ar_2) -> Com_1(evalfstart(ar_0, ar_1, ar_2)) [ 0 <= 0 ]
5.36/2.46	
5.36/2.46			(Comp: 2, Cost: 1)    evalfreturnin(ar_0, ar_1, ar_2) -> Com_1(evalfstop(ar_0, ar_1, ar_2)) [ ar_2 >= 0 /\ ar_1 + ar_2 - 1 >= 0 /\ ar_0 + ar_2 - 1 >= 0 /\ ar_0 - 1 >= 0 ]
5.36/2.46	
5.36/2.46			(Comp: ?, Cost: 1)    evalfbb1in(ar_0, ar_1, ar_2) -> Com_1(evalfbb3in(ar_0, ar_1 - 1, ar_2 + 1)) [ ar_0 - ar_2 - 1 >= 0 /\ ar_2 >= 0 /\ ar_1 + ar_2 - 1 >= 0 /\ ar_0 + ar_2 - 1 >= 0 /\ ar_1 - 1 >= 0 /\ ar_0 + ar_1 - 2 >= 0 /\ ar_0 - 1 >= 0 ]
5.36/2.46	
5.36/2.46			(Comp: ?, Cost: 1)    evalfbbin(ar_0, ar_1, ar_2) -> Com_1(evalfbb3in(ar_0, ar_1, 0)) [ ar_2 >= 0 /\ ar_1 + ar_2 - 1 >= 0 /\ ar_0 + ar_2 - 1 >= 0 /\ ar_1 - 1 >= 0 /\ ar_0 + ar_1 - 2 >= 0 /\ ar_0 - 1 >= 0 /\ ar_2 >= ar_0 ]
5.36/2.46	
5.36/2.46			(Comp: ?, Cost: 1)    evalfbbin(ar_0, ar_1, ar_2) -> Com_1(evalfbb1in(ar_0, ar_1, ar_2)) [ ar_2 >= 0 /\ ar_1 + ar_2 - 1 >= 0 /\ ar_0 + ar_2 - 1 >= 0 /\ ar_1 - 1 >= 0 /\ ar_0 + ar_1 - 2 >= 0 /\ ar_0 - 1 >= 0 /\ ar_0 >= ar_2 + 1 ]
5.36/2.46	
5.36/2.46			(Comp: 2, Cost: 1)    evalfbb4in(ar_0, ar_1, ar_2) -> Com_1(evalfreturnin(ar_0, ar_1, ar_2)) [ ar_2 >= 0 /\ ar_1 + ar_2 - 1 >= 0 /\ ar_0 + ar_2 - 1 >= 0 /\ ar_1 - 1 >= 0 /\ ar_0 + ar_1 - 2 >= 0 /\ ar_0 - 1 >= 0 ]
5.36/2.46	
5.36/2.46			(Comp: ?, Cost: 1)    evalfbb4in(ar_0, ar_1, ar_2) -> Com_1(evalfbbin(ar_0, ar_1, ar_2)) [ ar_2 >= 0 /\ ar_1 + ar_2 - 1 >= 0 /\ ar_0 + ar_2 - 1 >= 0 /\ ar_1 - 1 >= 0 /\ ar_0 + ar_1 - 2 >= 0 /\ ar_0 - 1 >= 0 /\ d >= 1 ]
5.36/2.46	
5.36/2.46			(Comp: ?, Cost: 1)    evalfbb4in(ar_0, ar_1, ar_2) -> Com_1(evalfbbin(ar_0, ar_1, ar_2)) [ ar_2 >= 0 /\ ar_1 + ar_2 - 1 >= 0 /\ ar_0 + ar_2 - 1 >= 0 /\ ar_1 - 1 >= 0 /\ ar_0 + ar_1 - 2 >= 0 /\ ar_0 - 1 >= 0 /\ 0 >= d + 1 ]
5.36/2.46	
5.36/2.46			(Comp: ?, Cost: 1)    evalfbb3in(ar_0, ar_1, ar_2) -> Com_1(evalfbb4in(ar_0, ar_1, ar_2)) [ ar_2 >= 0 /\ ar_1 + ar_2 - 1 >= 0 /\ ar_0 + ar_2 - 1 >= 0 /\ ar_0 - 1 >= 0 /\ ar_1 >= 1 ]
5.36/2.46	
5.36/2.46			(Comp: 2, Cost: 1)    evalfbb3in(ar_0, ar_1, ar_2) -> Com_1(evalfreturnin(ar_0, ar_1, ar_2)) [ ar_2 >= 0 /\ ar_1 + ar_2 - 1 >= 0 /\ ar_0 + ar_2 - 1 >= 0 /\ ar_0 - 1 >= 0 /\ 0 >= ar_1 ]
5.36/2.46	
5.36/2.46			(Comp: 1, Cost: 1)    evalfentryin(ar_0, ar_1, ar_2) -> Com_1(evalfbb3in(ar_1, ar_0, 0)) [ ar_0 >= 1 /\ ar_1 >= 1 ]
5.36/2.46	
5.36/2.46			(Comp: 1, Cost: 1)    evalfstart(ar_0, ar_1, ar_2) -> Com_1(evalfentryin(ar_0, ar_1, ar_2))
5.36/2.46	
5.36/2.46		start location:	koat_start
5.36/2.46	
5.36/2.46		leaf cost:	0
5.36/2.46	
5.36/2.46	
5.36/2.46	
5.36/2.46	A polynomial rank function with
5.36/2.46	
5.36/2.46		Pol(koat_start) = 7*V_1 + 1
5.36/2.46	
5.36/2.46		Pol(evalfstart) = 7*V_1 + 1
5.36/2.46	
5.36/2.46		Pol(evalfreturnin) = 7*V_2 + 3*V_3
5.36/2.46	
5.36/2.46		Pol(evalfstop) = 7*V_2 + 3*V_3
5.36/2.46	
5.36/2.46		Pol(evalfbb1in) = 7*V_2 + 3*V_3 - 2
5.36/2.46	
5.36/2.46		Pol(evalfbb3in) = 7*V_2 + 3*V_3 + 1
5.36/2.46	
5.36/2.46		Pol(evalfbbin) = 7*V_2 + 3*V_3 - 1
5.36/2.46	
5.36/2.46		Pol(evalfbb4in) = 7*V_2 + 3*V_3
5.36/2.46	
5.36/2.46		Pol(evalfentryin) = 7*V_1 + 1
5.36/2.46	
5.36/2.46	orients all transitions weakly and the transitions
5.36/2.46	
5.36/2.46		evalfbbin(ar_0, ar_1, ar_2) -> Com_1(evalfbb3in(ar_0, ar_1, 0)) [ ar_2 >= 0 /\ ar_1 + ar_2 - 1 >= 0 /\ ar_0 + ar_2 - 1 >= 0 /\ ar_1 - 1 >= 0 /\ ar_0 + ar_1 - 2 >= 0 /\ ar_0 - 1 >= 0 /\ ar_2 >= ar_0 ]
5.36/2.46	
5.36/2.46		evalfbbin(ar_0, ar_1, ar_2) -> Com_1(evalfbb1in(ar_0, ar_1, ar_2)) [ ar_2 >= 0 /\ ar_1 + ar_2 - 1 >= 0 /\ ar_0 + ar_2 - 1 >= 0 /\ ar_1 - 1 >= 0 /\ ar_0 + ar_1 - 2 >= 0 /\ ar_0 - 1 >= 0 /\ ar_0 >= ar_2 + 1 ]
5.36/2.46	
5.36/2.46		evalfbb4in(ar_0, ar_1, ar_2) -> Com_1(evalfbbin(ar_0, ar_1, ar_2)) [ ar_2 >= 0 /\ ar_1 + ar_2 - 1 >= 0 /\ ar_0 + ar_2 - 1 >= 0 /\ ar_1 - 1 >= 0 /\ ar_0 + ar_1 - 2 >= 0 /\ ar_0 - 1 >= 0 /\ d >= 1 ]
5.36/2.46	
5.36/2.46		evalfbb4in(ar_0, ar_1, ar_2) -> Com_1(evalfbbin(ar_0, ar_1, ar_2)) [ ar_2 >= 0 /\ ar_1 + ar_2 - 1 >= 0 /\ ar_0 + ar_2 - 1 >= 0 /\ ar_1 - 1 >= 0 /\ ar_0 + ar_1 - 2 >= 0 /\ ar_0 - 1 >= 0 /\ 0 >= d + 1 ]
5.36/2.46	
5.36/2.46		evalfbb3in(ar_0, ar_1, ar_2) -> Com_1(evalfbb4in(ar_0, ar_1, ar_2)) [ ar_2 >= 0 /\ ar_1 + ar_2 - 1 >= 0 /\ ar_0 + ar_2 - 1 >= 0 /\ ar_0 - 1 >= 0 /\ ar_1 >= 1 ]
5.36/2.46	
5.36/2.46		evalfbb1in(ar_0, ar_1, ar_2) -> Com_1(evalfbb3in(ar_0, ar_1 - 1, ar_2 + 1)) [ ar_0 - ar_2 - 1 >= 0 /\ ar_2 >= 0 /\ ar_1 + ar_2 - 1 >= 0 /\ ar_0 + ar_2 - 1 >= 0 /\ ar_1 - 1 >= 0 /\ ar_0 + ar_1 - 2 >= 0 /\ ar_0 - 1 >= 0 ]
5.36/2.46	
5.36/2.46	strictly and produces the following problem:
5.36/2.46	
5.36/2.46	5:	T:
5.36/2.46	
5.36/2.46			(Comp: 1, Cost: 0)             koat_start(ar_0, ar_1, ar_2) -> Com_1(evalfstart(ar_0, ar_1, ar_2)) [ 0 <= 0 ]
5.36/2.46	
5.36/2.46			(Comp: 2, Cost: 1)             evalfreturnin(ar_0, ar_1, ar_2) -> Com_1(evalfstop(ar_0, ar_1, ar_2)) [ ar_2 >= 0 /\ ar_1 + ar_2 - 1 >= 0 /\ ar_0 + ar_2 - 1 >= 0 /\ ar_0 - 1 >= 0 ]
5.36/2.46	
5.36/2.46			(Comp: 7*ar_0 + 1, Cost: 1)    evalfbb1in(ar_0, ar_1, ar_2) -> Com_1(evalfbb3in(ar_0, ar_1 - 1, ar_2 + 1)) [ ar_0 - ar_2 - 1 >= 0 /\ ar_2 >= 0 /\ ar_1 + ar_2 - 1 >= 0 /\ ar_0 + ar_2 - 1 >= 0 /\ ar_1 - 1 >= 0 /\ ar_0 + ar_1 - 2 >= 0 /\ ar_0 - 1 >= 0 ]
5.36/2.46	
5.36/2.46			(Comp: 7*ar_0 + 1, Cost: 1)    evalfbbin(ar_0, ar_1, ar_2) -> Com_1(evalfbb3in(ar_0, ar_1, 0)) [ ar_2 >= 0 /\ ar_1 + ar_2 - 1 >= 0 /\ ar_0 + ar_2 - 1 >= 0 /\ ar_1 - 1 >= 0 /\ ar_0 + ar_1 - 2 >= 0 /\ ar_0 - 1 >= 0 /\ ar_2 >= ar_0 ]
5.36/2.46	
5.36/2.46			(Comp: 7*ar_0 + 1, Cost: 1)    evalfbbin(ar_0, ar_1, ar_2) -> Com_1(evalfbb1in(ar_0, ar_1, ar_2)) [ ar_2 >= 0 /\ ar_1 + ar_2 - 1 >= 0 /\ ar_0 + ar_2 - 1 >= 0 /\ ar_1 - 1 >= 0 /\ ar_0 + ar_1 - 2 >= 0 /\ ar_0 - 1 >= 0 /\ ar_0 >= ar_2 + 1 ]
5.36/2.46	
5.36/2.46			(Comp: 2, Cost: 1)             evalfbb4in(ar_0, ar_1, ar_2) -> Com_1(evalfreturnin(ar_0, ar_1, ar_2)) [ ar_2 >= 0 /\ ar_1 + ar_2 - 1 >= 0 /\ ar_0 + ar_2 - 1 >= 0 /\ ar_1 - 1 >= 0 /\ ar_0 + ar_1 - 2 >= 0 /\ ar_0 - 1 >= 0 ]
5.36/2.46	
5.36/2.46			(Comp: 7*ar_0 + 1, Cost: 1)    evalfbb4in(ar_0, ar_1, ar_2) -> Com_1(evalfbbin(ar_0, ar_1, ar_2)) [ ar_2 >= 0 /\ ar_1 + ar_2 - 1 >= 0 /\ ar_0 + ar_2 - 1 >= 0 /\ ar_1 - 1 >= 0 /\ ar_0 + ar_1 - 2 >= 0 /\ ar_0 - 1 >= 0 /\ d >= 1 ]
5.36/2.46	
5.36/2.46			(Comp: 7*ar_0 + 1, Cost: 1)    evalfbb4in(ar_0, ar_1, ar_2) -> Com_1(evalfbbin(ar_0, ar_1, ar_2)) [ ar_2 >= 0 /\ ar_1 + ar_2 - 1 >= 0 /\ ar_0 + ar_2 - 1 >= 0 /\ ar_1 - 1 >= 0 /\ ar_0 + ar_1 - 2 >= 0 /\ ar_0 - 1 >= 0 /\ 0 >= d + 1 ]
5.36/2.46	
5.36/2.46			(Comp: 7*ar_0 + 1, Cost: 1)    evalfbb3in(ar_0, ar_1, ar_2) -> Com_1(evalfbb4in(ar_0, ar_1, ar_2)) [ ar_2 >= 0 /\ ar_1 + ar_2 - 1 >= 0 /\ ar_0 + ar_2 - 1 >= 0 /\ ar_0 - 1 >= 0 /\ ar_1 >= 1 ]
5.36/2.46	
5.36/2.46			(Comp: 2, Cost: 1)             evalfbb3in(ar_0, ar_1, ar_2) -> Com_1(evalfreturnin(ar_0, ar_1, ar_2)) [ ar_2 >= 0 /\ ar_1 + ar_2 - 1 >= 0 /\ ar_0 + ar_2 - 1 >= 0 /\ ar_0 - 1 >= 0 /\ 0 >= ar_1 ]
5.36/2.46	
5.36/2.46			(Comp: 1, Cost: 1)             evalfentryin(ar_0, ar_1, ar_2) -> Com_1(evalfbb3in(ar_1, ar_0, 0)) [ ar_0 >= 1 /\ ar_1 >= 1 ]
5.36/2.46	
5.36/2.46			(Comp: 1, Cost: 1)             evalfstart(ar_0, ar_1, ar_2) -> Com_1(evalfentryin(ar_0, ar_1, ar_2))
5.36/2.46	
5.36/2.46		start location:	koat_start
5.36/2.46	
5.36/2.46		leaf cost:	0
5.36/2.46	
5.36/2.46	
5.36/2.46	
5.36/2.46	Complexity upper bound 42*ar_0 + 14
5.36/2.46	
5.36/2.46	
5.36/2.46	
5.36/2.46	Time: 0.261 sec (SMT: 0.227 sec)
5.36/2.46	
5.36/2.46	
5.36/2.46	----------------------------------------
5.36/2.46	
5.36/2.46	(2)
5.36/2.46	BOUNDS(1, n^1)
5.36/2.46	
5.36/2.46	----------------------------------------
5.36/2.46	
5.36/2.46	(3) Loat Proof (FINISHED)
5.36/2.46	
5.36/2.46	
5.36/2.46	### Pre-processing the ITS problem ###
5.36/2.46	
5.36/2.46	
5.36/2.46	
5.36/2.46	Initial linear ITS problem
5.36/2.46	
5.36/2.46	   Start location: evalfstart
5.36/2.46	
5.36/2.46	      0: evalfstart -> evalfentryin : [], cost: 1
5.36/2.46	
5.36/2.46	      1: evalfentryin -> evalfbb3in : A'=B, B'=A, C'=0, [ A>=1 && B>=1 ], cost: 1
5.36/2.46	
5.36/2.46	      2: evalfbb3in -> evalfreturnin : [ 0>=B ], cost: 1
5.36/2.46	
5.36/2.46	      3: evalfbb3in -> evalfbb4in : [ B>=1 ], cost: 1
5.36/2.46	
5.36/2.46	      4: evalfbb4in -> evalfbbin : [ 0>=1+free ], cost: 1
5.36/2.46	
5.36/2.46	      5: evalfbb4in -> evalfbbin : [ free_1>=1 ], cost: 1
5.36/2.46	
5.36/2.46	      6: evalfbb4in -> evalfreturnin : [], cost: 1
5.36/2.46	
5.36/2.46	      7: evalfbbin -> evalfbb1in : [ A>=1+C ], cost: 1
5.36/2.46	
5.36/2.46	      8: evalfbbin -> evalfbb3in : C'=0, [ C>=A ], cost: 1
5.36/2.46	
5.36/2.46	      9: evalfbb1in -> evalfbb3in : B'=-1+B, C'=1+C, [], cost: 1
5.36/2.46	
5.36/2.46	     10: evalfreturnin -> evalfstop : [], cost: 1
5.36/2.46	
5.36/2.46	
5.36/2.46	
5.36/2.46	Removed unreachable and leaf rules:
5.36/2.46	
5.36/2.46	   Start location: evalfstart
5.36/2.46	
5.36/2.46	      0: evalfstart -> evalfentryin : [], cost: 1
5.36/2.46	
5.36/2.46	      1: evalfentryin -> evalfbb3in : A'=B, B'=A, C'=0, [ A>=1 && B>=1 ], cost: 1
5.36/2.46	
5.36/2.46	      3: evalfbb3in -> evalfbb4in : [ B>=1 ], cost: 1
5.36/2.46	
5.36/2.46	      4: evalfbb4in -> evalfbbin : [ 0>=1+free ], cost: 1
5.36/2.46	
5.36/2.46	      5: evalfbb4in -> evalfbbin : [ free_1>=1 ], cost: 1
5.36/2.46	
5.36/2.46	      7: evalfbbin -> evalfbb1in : [ A>=1+C ], cost: 1
5.36/2.46	
5.36/2.46	      8: evalfbbin -> evalfbb3in : C'=0, [ C>=A ], cost: 1
5.36/2.46	
5.36/2.46	      9: evalfbb1in -> evalfbb3in : B'=-1+B, C'=1+C, [], cost: 1
5.36/2.46	
5.36/2.46	
5.36/2.46	
5.36/2.46	Simplified all rules, resulting in:
5.36/2.46	
5.36/2.46	   Start location: evalfstart
5.36/2.46	
5.36/2.46	      0: evalfstart -> evalfentryin : [], cost: 1
5.36/2.46	
5.36/2.46	      1: evalfentryin -> evalfbb3in : A'=B, B'=A, C'=0, [ A>=1 && B>=1 ], cost: 1
5.36/2.46	
5.36/2.46	      3: evalfbb3in -> evalfbb4in : [ B>=1 ], cost: 1
5.36/2.46	
5.36/2.46	      5: evalfbb4in -> evalfbbin : [], cost: 1
5.36/2.46	
5.36/2.46	      7: evalfbbin -> evalfbb1in : [ A>=1+C ], cost: 1
5.36/2.46	
5.36/2.46	      8: evalfbbin -> evalfbb3in : C'=0, [ C>=A ], cost: 1
5.36/2.46	
5.36/2.46	      9: evalfbb1in -> evalfbb3in : B'=-1+B, C'=1+C, [], cost: 1
5.36/2.46	
5.36/2.46	
5.36/2.46	
5.36/2.46	### Simplification by acceleration and chaining ###
5.36/2.46	
5.36/2.46	
5.36/2.46	
5.36/2.46	Eliminated locations (on linear paths):
5.36/2.46	
5.36/2.46	   Start location: evalfstart
5.36/2.46	
5.36/2.46	     11: evalfstart -> evalfbb3in : A'=B, B'=A, C'=0, [ A>=1 && B>=1 ], cost: 2
5.36/2.46	
5.36/2.46	     12: evalfbb3in -> evalfbbin : [ B>=1 ], cost: 2
5.36/2.46	
5.36/2.46	      8: evalfbbin -> evalfbb3in : C'=0, [ C>=A ], cost: 1
5.36/2.46	
5.36/2.46	     13: evalfbbin -> evalfbb3in : B'=-1+B, C'=1+C, [ A>=1+C ], cost: 2
5.36/2.46	
5.36/2.46	
5.36/2.46	
5.36/2.46	Eliminated locations (on tree-shaped paths):
5.36/2.46	
5.36/2.46	   Start location: evalfstart
5.36/2.46	
5.36/2.46	     11: evalfstart -> evalfbb3in : A'=B, B'=A, C'=0, [ A>=1 && B>=1 ], cost: 2
5.36/2.46	
5.36/2.46	     14: evalfbb3in -> evalfbb3in : C'=0, [ B>=1 && C>=A ], cost: 3
5.36/2.46	
5.36/2.46	     15: evalfbb3in -> evalfbb3in : B'=-1+B, C'=1+C, [ B>=1 && A>=1+C ], cost: 4
5.36/2.46	
5.36/2.46	
5.36/2.46	
5.36/2.46	Accelerating simple loops of location 2.
5.36/2.46	
5.36/2.46	   Accelerating the following rules:
5.36/2.46	
5.36/2.46	     14: evalfbb3in -> evalfbb3in : C'=0, [ B>=1 && C>=A ], cost: 3
5.36/2.46	
5.36/2.46	     15: evalfbb3in -> evalfbb3in : B'=-1+B, C'=1+C, [ B>=1 && A>=1+C ], cost: 4
5.36/2.46	
5.36/2.46	
5.36/2.46	
5.36/2.46	   Accelerated rule 14 with NONTERM (after strengthening guard), yielding the new rule 16.
5.36/2.46	
5.36/2.46	   Accelerated rule 15 with backward acceleration, yielding the new rule 17.
5.36/2.46	
5.36/2.46	   Accelerated rule 15 with backward acceleration, yielding the new rule 18.
5.36/2.46	
5.36/2.46	   Removing the simple loops: 15.
5.36/2.46	
5.36/2.46	
5.36/2.46	
5.36/2.46	Accelerated all simple loops using metering functions (where possible):
5.36/2.46	
5.36/2.46	   Start location: evalfstart
5.36/2.46	
5.36/2.46	     11: evalfstart -> evalfbb3in : A'=B, B'=A, C'=0, [ A>=1 && B>=1 ], cost: 2
5.36/2.46	
5.36/2.46	     14: evalfbb3in -> evalfbb3in : C'=0, [ B>=1 && C>=A ], cost: 3
5.36/2.46	
5.36/2.46	     16: evalfbb3in -> [8] : [ B>=1 && C>=A && 0>=A ], cost: INF
5.36/2.46	
5.36/2.46	     17: evalfbb3in -> evalfbb3in : B'=0, C'=C+B, [ B>=1 && A>=1+C && A>=C+B ], cost: 4*B
5.36/2.46	
5.36/2.46	     18: evalfbb3in -> evalfbb3in : B'=C-A+B, C'=A, [ B>=1 && A>=1+C && 1+C-A+B>=1 ], cost: -4*C+4*A
5.36/2.46	
5.36/2.46	
5.36/2.46	
5.36/2.46	Chained accelerated rules (with incoming rules):
5.36/2.46	
5.36/2.46	   Start location: evalfstart
5.36/2.46	
5.36/2.46	     11: evalfstart -> evalfbb3in : A'=B, B'=A, C'=0, [ A>=1 && B>=1 ], cost: 2
5.36/2.46	
5.36/2.46	     19: evalfstart -> evalfbb3in : A'=B, B'=0, C'=A, [ A>=1 && B>=1 && B>=A ], cost: 2+4*A
5.36/2.46	
5.36/2.46	     20: evalfstart -> evalfbb3in : A'=B, B'=A-B, C'=B, [ A>=1 && B>=1 && 1+A-B>=1 ], cost: 2+4*B
5.36/2.46	
5.36/2.46	
5.36/2.46	
5.36/2.46	Removed unreachable locations (and leaf rules with constant cost):
5.36/2.46	
5.36/2.46	   Start location: evalfstart
5.36/2.46	
5.36/2.46	     19: evalfstart -> evalfbb3in : A'=B, B'=0, C'=A, [ A>=1 && B>=1 && B>=A ], cost: 2+4*A
5.36/2.46	
5.36/2.46	     20: evalfstart -> evalfbb3in : A'=B, B'=A-B, C'=B, [ A>=1 && B>=1 && 1+A-B>=1 ], cost: 2+4*B
5.36/2.46	
5.36/2.46	
5.36/2.46	
5.36/2.46	### Computing asymptotic complexity ###
5.36/2.46	
5.36/2.46	
5.36/2.46	
5.36/2.46	Fully simplified ITS problem
5.36/2.46	
5.36/2.46	   Start location: evalfstart
5.36/2.46	
5.36/2.46	     19: evalfstart -> evalfbb3in : A'=B, B'=0, C'=A, [ A>=1 && B>=1 && B>=A ], cost: 2+4*A
5.36/2.46	
5.36/2.46	     20: evalfstart -> evalfbb3in : A'=B, B'=A-B, C'=B, [ A>=1 && B>=1 && 1+A-B>=1 ], cost: 2+4*B
5.36/2.46	
5.36/2.46	
5.36/2.46	
5.36/2.46	Computing asymptotic complexity for rule 19
5.36/2.46	
5.36/2.46	   Solved the limit problem by the following transformations:
5.36/2.46	
5.36/2.46	      Created initial limit problem:
5.36/2.46	
5.36/2.46	      2+4*A (+), A (+/+!), 1-A+B (+/+!), B (+/+!) [not solved]
5.36/2.46	
5.36/2.46	
5.36/2.46	
5.36/2.46	      removing all constraints (solved by SMT)
5.36/2.46	
5.36/2.46	      resulting limit problem: [solved]
5.36/2.46	
5.36/2.46	
5.36/2.46	
5.36/2.46	      applying transformation rule (C) using substitution {A==n,B==2*n}
5.36/2.46	
5.36/2.46	      resulting limit problem:
5.36/2.46	
5.36/2.46	      [solved]
5.36/2.46	
5.36/2.46	
5.36/2.46	
5.36/2.46	   Solution:
5.36/2.46	
5.36/2.46	      A / n
5.36/2.46	
5.36/2.46	      B / 2*n
5.36/2.46	
5.36/2.46	   Resulting cost 2+4*n has complexity: Poly(n^1)
5.36/2.46	
5.36/2.46	
5.36/2.46	
5.36/2.46	Found new complexity Poly(n^1).
5.36/2.46	
5.36/2.46	
5.36/2.46	
5.36/2.46	Obtained the following overall complexity (w.r.t. the length of the input n):
5.36/2.46	
5.36/2.46	   Complexity:  Poly(n^1)
5.36/2.46	
5.36/2.46	   Cpx degree:  1
5.36/2.46	
5.36/2.46	   Solved cost: 2+4*n
5.36/2.46	
5.36/2.46	   Rule cost:   2+4*A
5.36/2.46	
5.36/2.46	   Rule guard:  [ A>=1 && B>=1 && B>=A ]
5.36/2.46	
5.36/2.46	
5.36/2.46	
5.36/2.46	WORST_CASE(Omega(n^1),?)
5.36/2.46	
5.36/2.46	
5.36/2.46	----------------------------------------
5.36/2.46	
5.36/2.46	(4)
5.36/2.46	BOUNDS(n^1, INF)
5.36/2.48	EOF