4.65/2.19	WORST_CASE(Omega(n^2), O(n^2))
4.65/2.20	proof of /export/starexec/sandbox/benchmark/theBenchmark.koat
4.65/2.20	# AProVE Commit ID: 48fb2092695e11cc9f56e44b17a92a5f88ffb256 marcel 20180622 unpublished dirty
4.65/2.20	
4.65/2.20	
4.65/2.20	The runtime complexity of the given CpxIntTrs could be proven to be BOUNDS(n^2, n^2).
4.65/2.20	
4.65/2.20	(0) CpxIntTrs
4.65/2.20	(1) Koat Proof [FINISHED, 53 ms]
4.65/2.20	(2) BOUNDS(1, n^2)
4.65/2.20	(3) Loat Proof [FINISHED, 507 ms]
4.65/2.20	(4) BOUNDS(n^2, INF)
4.65/2.20	
4.65/2.20	
4.65/2.20	----------------------------------------
4.65/2.20	
4.65/2.20	(0)
4.65/2.20	Obligation:
4.65/2.20	Complexity Int TRS consisting of the following rules:
4.65/2.20	evalaxstart(A, B, C) -> Com_1(evalaxentryin(A, B, C)) :|: TRUE
4.65/2.20	evalaxentryin(A, B, C) -> Com_1(evalaxbbin(0, B, C)) :|: TRUE
4.65/2.20	evalaxbbin(A, B, C) -> Com_1(evalaxbb2in(A, 0, C)) :|: TRUE
4.65/2.20	evalaxbb2in(A, B, C) -> Com_1(evalaxbb1in(A, B, C)) :|: C >= 2 + B
4.65/2.20	evalaxbb2in(A, B, C) -> Com_1(evalaxbb3in(A, B, C)) :|: B + 1 >= C
4.65/2.20	evalaxbb1in(A, B, C) -> Com_1(evalaxbb2in(A, B + 1, C)) :|: TRUE
4.65/2.20	evalaxbb3in(A, B, C) -> Com_1(evalaxbbin(A + 1, B, C)) :|: B + 1 >= C && C >= 3 + A
4.65/2.20	evalaxbb3in(A, B, C) -> Com_1(evalaxreturnin(A, B, C)) :|: C >= 2 + B
4.65/2.20	evalaxbb3in(A, B, C) -> Com_1(evalaxreturnin(A, B, C)) :|: A + 2 >= C
4.65/2.20	evalaxreturnin(A, B, C) -> Com_1(evalaxstop(A, B, C)) :|: TRUE
4.65/2.20	
4.65/2.20	The start-symbols are:[evalaxstart_3]
4.65/2.20	
4.65/2.20	
4.65/2.20	----------------------------------------
4.65/2.20	
4.65/2.20	(1) Koat Proof (FINISHED)
4.65/2.20	YES(?, 5*ar_2 + 2*ar_2^2 + 8)
4.65/2.20	
4.65/2.20	
4.65/2.20	
4.65/2.20	Initial complexity problem:
4.65/2.20	
4.65/2.20	1:	T:
4.65/2.20	
4.65/2.20			(Comp: ?, Cost: 1)    evalaxstart(ar_0, ar_1, ar_2) -> Com_1(evalaxentryin(ar_0, ar_1, ar_2))
4.65/2.20	
4.65/2.20			(Comp: ?, Cost: 1)    evalaxentryin(ar_0, ar_1, ar_2) -> Com_1(evalaxbbin(0, ar_1, ar_2))
4.65/2.20	
4.65/2.20			(Comp: ?, Cost: 1)    evalaxbbin(ar_0, ar_1, ar_2) -> Com_1(evalaxbb2in(ar_0, 0, ar_2))
4.65/2.20	
4.65/2.20			(Comp: ?, Cost: 1)    evalaxbb2in(ar_0, ar_1, ar_2) -> Com_1(evalaxbb1in(ar_0, ar_1, ar_2)) [ ar_2 >= ar_1 + 2 ]
4.65/2.20	
4.65/2.20			(Comp: ?, Cost: 1)    evalaxbb2in(ar_0, ar_1, ar_2) -> Com_1(evalaxbb3in(ar_0, ar_1, ar_2)) [ ar_1 + 1 >= ar_2 ]
4.65/2.20	
4.65/2.20			(Comp: ?, Cost: 1)    evalaxbb1in(ar_0, ar_1, ar_2) -> Com_1(evalaxbb2in(ar_0, ar_1 + 1, ar_2))
4.65/2.20	
4.65/2.20			(Comp: ?, Cost: 1)    evalaxbb3in(ar_0, ar_1, ar_2) -> Com_1(evalaxbbin(ar_0 + 1, ar_1, ar_2)) [ ar_1 + 1 >= ar_2 /\ ar_2 >= ar_0 + 3 ]
4.65/2.20	
4.65/2.20			(Comp: ?, Cost: 1)    evalaxbb3in(ar_0, ar_1, ar_2) -> Com_1(evalaxreturnin(ar_0, ar_1, ar_2)) [ ar_2 >= ar_1 + 2 ]
4.65/2.20	
4.65/2.20			(Comp: ?, Cost: 1)    evalaxbb3in(ar_0, ar_1, ar_2) -> Com_1(evalaxreturnin(ar_0, ar_1, ar_2)) [ ar_0 + 2 >= ar_2 ]
4.65/2.20	
4.65/2.20			(Comp: ?, Cost: 1)    evalaxreturnin(ar_0, ar_1, ar_2) -> Com_1(evalaxstop(ar_0, ar_1, ar_2))
4.65/2.20	
4.65/2.20			(Comp: 1, Cost: 0)    koat_start(ar_0, ar_1, ar_2) -> Com_1(evalaxstart(ar_0, ar_1, ar_2)) [ 0 <= 0 ]
4.65/2.20	
4.65/2.20		start location:	koat_start
4.65/2.20	
4.65/2.20		leaf cost:	0
4.65/2.20	
4.65/2.20	
4.65/2.20	
4.65/2.20	Testing for reachability in the complexity graph removes the following transition from problem 1:
4.65/2.20	
4.65/2.20		evalaxbb3in(ar_0, ar_1, ar_2) -> Com_1(evalaxreturnin(ar_0, ar_1, ar_2)) [ ar_2 >= ar_1 + 2 ]
4.65/2.20	
4.65/2.20	We thus obtain the following problem:
4.65/2.20	
4.65/2.20	2:	T:
4.65/2.20	
4.65/2.20			(Comp: ?, Cost: 1)    evalaxreturnin(ar_0, ar_1, ar_2) -> Com_1(evalaxstop(ar_0, ar_1, ar_2))
4.65/2.20	
4.65/2.20			(Comp: ?, Cost: 1)    evalaxbb3in(ar_0, ar_1, ar_2) -> Com_1(evalaxreturnin(ar_0, ar_1, ar_2)) [ ar_0 + 2 >= ar_2 ]
4.65/2.20	
4.65/2.20			(Comp: ?, Cost: 1)    evalaxbb3in(ar_0, ar_1, ar_2) -> Com_1(evalaxbbin(ar_0 + 1, ar_1, ar_2)) [ ar_1 + 1 >= ar_2 /\ ar_2 >= ar_0 + 3 ]
4.65/2.20	
4.65/2.20			(Comp: ?, Cost: 1)    evalaxbb1in(ar_0, ar_1, ar_2) -> Com_1(evalaxbb2in(ar_0, ar_1 + 1, ar_2))
4.65/2.20	
4.65/2.20			(Comp: ?, Cost: 1)    evalaxbb2in(ar_0, ar_1, ar_2) -> Com_1(evalaxbb3in(ar_0, ar_1, ar_2)) [ ar_1 + 1 >= ar_2 ]
4.65/2.20	
4.65/2.20			(Comp: ?, Cost: 1)    evalaxbb2in(ar_0, ar_1, ar_2) -> Com_1(evalaxbb1in(ar_0, ar_1, ar_2)) [ ar_2 >= ar_1 + 2 ]
4.65/2.20	
4.65/2.20			(Comp: ?, Cost: 1)    evalaxbbin(ar_0, ar_1, ar_2) -> Com_1(evalaxbb2in(ar_0, 0, ar_2))
4.65/2.20	
4.65/2.20			(Comp: ?, Cost: 1)    evalaxentryin(ar_0, ar_1, ar_2) -> Com_1(evalaxbbin(0, ar_1, ar_2))
4.65/2.20	
4.65/2.20			(Comp: ?, Cost: 1)    evalaxstart(ar_0, ar_1, ar_2) -> Com_1(evalaxentryin(ar_0, ar_1, ar_2))
4.65/2.20	
4.65/2.20			(Comp: 1, Cost: 0)    koat_start(ar_0, ar_1, ar_2) -> Com_1(evalaxstart(ar_0, ar_1, ar_2)) [ 0 <= 0 ]
4.65/2.20	
4.65/2.20		start location:	koat_start
4.65/2.20	
4.65/2.20		leaf cost:	0
4.65/2.20	
4.65/2.20	
4.65/2.20	
4.65/2.20	Repeatedly propagating knowledge in problem 2 produces the following problem:
4.65/2.20	
4.65/2.20	3:	T:
4.65/2.20	
4.65/2.20			(Comp: ?, Cost: 1)    evalaxreturnin(ar_0, ar_1, ar_2) -> Com_1(evalaxstop(ar_0, ar_1, ar_2))
4.65/2.20	
4.65/2.20			(Comp: ?, Cost: 1)    evalaxbb3in(ar_0, ar_1, ar_2) -> Com_1(evalaxreturnin(ar_0, ar_1, ar_2)) [ ar_0 + 2 >= ar_2 ]
4.65/2.20	
4.65/2.20			(Comp: ?, Cost: 1)    evalaxbb3in(ar_0, ar_1, ar_2) -> Com_1(evalaxbbin(ar_0 + 1, ar_1, ar_2)) [ ar_1 + 1 >= ar_2 /\ ar_2 >= ar_0 + 3 ]
4.65/2.20	
4.65/2.20			(Comp: ?, Cost: 1)    evalaxbb1in(ar_0, ar_1, ar_2) -> Com_1(evalaxbb2in(ar_0, ar_1 + 1, ar_2))
4.65/2.20	
4.65/2.20			(Comp: ?, Cost: 1)    evalaxbb2in(ar_0, ar_1, ar_2) -> Com_1(evalaxbb3in(ar_0, ar_1, ar_2)) [ ar_1 + 1 >= ar_2 ]
4.65/2.20	
4.65/2.20			(Comp: ?, Cost: 1)    evalaxbb2in(ar_0, ar_1, ar_2) -> Com_1(evalaxbb1in(ar_0, ar_1, ar_2)) [ ar_2 >= ar_1 + 2 ]
4.65/2.20	
4.65/2.20			(Comp: ?, Cost: 1)    evalaxbbin(ar_0, ar_1, ar_2) -> Com_1(evalaxbb2in(ar_0, 0, ar_2))
4.65/2.20	
4.65/2.20			(Comp: 1, Cost: 1)    evalaxentryin(ar_0, ar_1, ar_2) -> Com_1(evalaxbbin(0, ar_1, ar_2))
4.65/2.20	
4.65/2.20			(Comp: 1, Cost: 1)    evalaxstart(ar_0, ar_1, ar_2) -> Com_1(evalaxentryin(ar_0, ar_1, ar_2))
4.65/2.20	
4.65/2.20			(Comp: 1, Cost: 0)    koat_start(ar_0, ar_1, ar_2) -> Com_1(evalaxstart(ar_0, ar_1, ar_2)) [ 0 <= 0 ]
4.65/2.20	
4.65/2.20		start location:	koat_start
4.65/2.20	
4.65/2.20		leaf cost:	0
4.65/2.20	
4.65/2.20	
4.65/2.20	
4.65/2.20	A polynomial rank function with
4.65/2.20	
4.65/2.20		Pol(evalaxreturnin) = 1
4.65/2.20	
4.65/2.20		Pol(evalaxstop) = 0
4.65/2.20	
4.65/2.20		Pol(evalaxbb3in) = 2
4.65/2.20	
4.65/2.20		Pol(evalaxbbin) = 2
4.65/2.20	
4.65/2.20		Pol(evalaxbb1in) = 2
4.65/2.20	
4.65/2.20		Pol(evalaxbb2in) = 2
4.65/2.20	
4.65/2.20		Pol(evalaxentryin) = 2
4.65/2.20	
4.65/2.20		Pol(evalaxstart) = 2
4.65/2.20	
4.65/2.20		Pol(koat_start) = 2
4.65/2.20	
4.65/2.20	orients all transitions weakly and the transitions
4.65/2.20	
4.65/2.20		evalaxreturnin(ar_0, ar_1, ar_2) -> Com_1(evalaxstop(ar_0, ar_1, ar_2))
4.65/2.20	
4.65/2.20		evalaxbb3in(ar_0, ar_1, ar_2) -> Com_1(evalaxreturnin(ar_0, ar_1, ar_2)) [ ar_0 + 2 >= ar_2 ]
4.65/2.20	
4.65/2.20	strictly and produces the following problem:
4.65/2.20	
4.65/2.20	4:	T:
4.65/2.20	
4.65/2.20			(Comp: 2, Cost: 1)    evalaxreturnin(ar_0, ar_1, ar_2) -> Com_1(evalaxstop(ar_0, ar_1, ar_2))
4.65/2.20	
4.65/2.20			(Comp: 2, Cost: 1)    evalaxbb3in(ar_0, ar_1, ar_2) -> Com_1(evalaxreturnin(ar_0, ar_1, ar_2)) [ ar_0 + 2 >= ar_2 ]
4.65/2.20	
4.65/2.20			(Comp: ?, Cost: 1)    evalaxbb3in(ar_0, ar_1, ar_2) -> Com_1(evalaxbbin(ar_0 + 1, ar_1, ar_2)) [ ar_1 + 1 >= ar_2 /\ ar_2 >= ar_0 + 3 ]
4.65/2.20	
4.65/2.20			(Comp: ?, Cost: 1)    evalaxbb1in(ar_0, ar_1, ar_2) -> Com_1(evalaxbb2in(ar_0, ar_1 + 1, ar_2))
4.65/2.20	
4.65/2.20			(Comp: ?, Cost: 1)    evalaxbb2in(ar_0, ar_1, ar_2) -> Com_1(evalaxbb3in(ar_0, ar_1, ar_2)) [ ar_1 + 1 >= ar_2 ]
4.65/2.20	
4.65/2.20			(Comp: ?, Cost: 1)    evalaxbb2in(ar_0, ar_1, ar_2) -> Com_1(evalaxbb1in(ar_0, ar_1, ar_2)) [ ar_2 >= ar_1 + 2 ]
4.65/2.20	
4.65/2.20			(Comp: ?, Cost: 1)    evalaxbbin(ar_0, ar_1, ar_2) -> Com_1(evalaxbb2in(ar_0, 0, ar_2))
4.65/2.20	
4.65/2.20			(Comp: 1, Cost: 1)    evalaxentryin(ar_0, ar_1, ar_2) -> Com_1(evalaxbbin(0, ar_1, ar_2))
4.65/2.20	
4.65/2.20			(Comp: 1, Cost: 1)    evalaxstart(ar_0, ar_1, ar_2) -> Com_1(evalaxentryin(ar_0, ar_1, ar_2))
4.65/2.20	
4.65/2.20			(Comp: 1, Cost: 0)    koat_start(ar_0, ar_1, ar_2) -> Com_1(evalaxstart(ar_0, ar_1, ar_2)) [ 0 <= 0 ]
4.65/2.20	
4.65/2.20		start location:	koat_start
4.65/2.20	
4.65/2.20		leaf cost:	0
4.65/2.20	
4.65/2.20	
4.65/2.20	
4.65/2.20	A polynomial rank function with
4.65/2.20	
4.65/2.20		Pol(evalaxreturnin) = -V_1 + V_3
4.65/2.20	
4.65/2.20		Pol(evalaxstop) = -V_1 + V_3
4.65/2.20	
4.65/2.20		Pol(evalaxbb3in) = -V_1 + V_3
4.65/2.20	
4.65/2.20		Pol(evalaxbbin) = -V_1 + V_3
4.65/2.20	
4.65/2.20		Pol(evalaxbb1in) = -V_1 + V_3
4.65/2.20	
4.65/2.20		Pol(evalaxbb2in) = -V_1 + V_3
4.65/2.20	
4.65/2.20		Pol(evalaxentryin) = V_3
4.65/2.20	
4.65/2.20		Pol(evalaxstart) = V_3
4.65/2.20	
4.65/2.20		Pol(koat_start) = V_3
4.65/2.20	
4.65/2.20	orients all transitions weakly and the transition
4.65/2.20	
4.65/2.20		evalaxbb3in(ar_0, ar_1, ar_2) -> Com_1(evalaxbbin(ar_0 + 1, ar_1, ar_2)) [ ar_1 + 1 >= ar_2 /\ ar_2 >= ar_0 + 3 ]
4.65/2.20	
4.65/2.20	strictly and produces the following problem:
4.65/2.20	
4.65/2.20	5:	T:
4.65/2.20	
4.65/2.20			(Comp: 2, Cost: 1)       evalaxreturnin(ar_0, ar_1, ar_2) -> Com_1(evalaxstop(ar_0, ar_1, ar_2))
4.65/2.20	
4.65/2.20			(Comp: 2, Cost: 1)       evalaxbb3in(ar_0, ar_1, ar_2) -> Com_1(evalaxreturnin(ar_0, ar_1, ar_2)) [ ar_0 + 2 >= ar_2 ]
4.65/2.20	
4.65/2.20			(Comp: ar_2, Cost: 1)    evalaxbb3in(ar_0, ar_1, ar_2) -> Com_1(evalaxbbin(ar_0 + 1, ar_1, ar_2)) [ ar_1 + 1 >= ar_2 /\ ar_2 >= ar_0 + 3 ]
4.65/2.20	
4.65/2.20			(Comp: ?, Cost: 1)       evalaxbb1in(ar_0, ar_1, ar_2) -> Com_1(evalaxbb2in(ar_0, ar_1 + 1, ar_2))
4.65/2.20	
4.65/2.20			(Comp: ?, Cost: 1)       evalaxbb2in(ar_0, ar_1, ar_2) -> Com_1(evalaxbb3in(ar_0, ar_1, ar_2)) [ ar_1 + 1 >= ar_2 ]
4.65/2.20	
4.65/2.20			(Comp: ?, Cost: 1)       evalaxbb2in(ar_0, ar_1, ar_2) -> Com_1(evalaxbb1in(ar_0, ar_1, ar_2)) [ ar_2 >= ar_1 + 2 ]
4.65/2.20	
4.65/2.20			(Comp: ?, Cost: 1)       evalaxbbin(ar_0, ar_1, ar_2) -> Com_1(evalaxbb2in(ar_0, 0, ar_2))
4.65/2.20	
4.65/2.20			(Comp: 1, Cost: 1)       evalaxentryin(ar_0, ar_1, ar_2) -> Com_1(evalaxbbin(0, ar_1, ar_2))
4.65/2.20	
4.65/2.20			(Comp: 1, Cost: 1)       evalaxstart(ar_0, ar_1, ar_2) -> Com_1(evalaxentryin(ar_0, ar_1, ar_2))
4.65/2.21	
4.65/2.21			(Comp: 1, Cost: 0)       koat_start(ar_0, ar_1, ar_2) -> Com_1(evalaxstart(ar_0, ar_1, ar_2)) [ 0 <= 0 ]
4.65/2.21	
4.65/2.21		start location:	koat_start
4.65/2.21	
4.65/2.21		leaf cost:	0
4.65/2.21	
4.65/2.21	
4.65/2.21	
4.65/2.21	Repeatedly propagating knowledge in problem 5 produces the following problem:
4.65/2.21	
4.65/2.21	6:	T:
4.65/2.21	
4.65/2.21			(Comp: 2, Cost: 1)           evalaxreturnin(ar_0, ar_1, ar_2) -> Com_1(evalaxstop(ar_0, ar_1, ar_2))
4.65/2.21	
4.65/2.21			(Comp: 2, Cost: 1)           evalaxbb3in(ar_0, ar_1, ar_2) -> Com_1(evalaxreturnin(ar_0, ar_1, ar_2)) [ ar_0 + 2 >= ar_2 ]
4.65/2.21	
4.65/2.21			(Comp: ar_2, Cost: 1)        evalaxbb3in(ar_0, ar_1, ar_2) -> Com_1(evalaxbbin(ar_0 + 1, ar_1, ar_2)) [ ar_1 + 1 >= ar_2 /\ ar_2 >= ar_0 + 3 ]
4.65/2.21	
4.65/2.21			(Comp: ?, Cost: 1)           evalaxbb1in(ar_0, ar_1, ar_2) -> Com_1(evalaxbb2in(ar_0, ar_1 + 1, ar_2))
4.65/2.21	
4.65/2.21			(Comp: ?, Cost: 1)           evalaxbb2in(ar_0, ar_1, ar_2) -> Com_1(evalaxbb3in(ar_0, ar_1, ar_2)) [ ar_1 + 1 >= ar_2 ]
4.65/2.21	
4.65/2.21			(Comp: ?, Cost: 1)           evalaxbb2in(ar_0, ar_1, ar_2) -> Com_1(evalaxbb1in(ar_0, ar_1, ar_2)) [ ar_2 >= ar_1 + 2 ]
4.65/2.21	
4.65/2.21			(Comp: ar_2 + 1, Cost: 1)    evalaxbbin(ar_0, ar_1, ar_2) -> Com_1(evalaxbb2in(ar_0, 0, ar_2))
4.65/2.21	
4.65/2.21			(Comp: 1, Cost: 1)           evalaxentryin(ar_0, ar_1, ar_2) -> Com_1(evalaxbbin(0, ar_1, ar_2))
4.65/2.21	
4.65/2.21			(Comp: 1, Cost: 1)           evalaxstart(ar_0, ar_1, ar_2) -> Com_1(evalaxentryin(ar_0, ar_1, ar_2))
4.65/2.21	
4.65/2.21			(Comp: 1, Cost: 0)           koat_start(ar_0, ar_1, ar_2) -> Com_1(evalaxstart(ar_0, ar_1, ar_2)) [ 0 <= 0 ]
4.65/2.21	
4.65/2.21		start location:	koat_start
4.65/2.21	
4.65/2.21		leaf cost:	0
4.65/2.21	
4.65/2.21	
4.65/2.21	
4.65/2.21	A polynomial rank function with
4.65/2.21	
4.65/2.21		Pol(evalaxbb2in) = 1
4.65/2.21	
4.65/2.21		Pol(evalaxbb3in) = 0
4.65/2.21	
4.65/2.21		Pol(evalaxbb1in) = 1
4.65/2.21	
4.65/2.21	and size complexities
4.65/2.21	
4.65/2.21		S("koat_start(ar_0, ar_1, ar_2) -> Com_1(evalaxstart(ar_0, ar_1, ar_2)) [ 0 <= 0 ]", 0-0) = ar_0
4.65/2.21	
4.65/2.21		S("koat_start(ar_0, ar_1, ar_2) -> Com_1(evalaxstart(ar_0, ar_1, ar_2)) [ 0 <= 0 ]", 0-1) = ar_1
4.65/2.21	
4.65/2.21		S("koat_start(ar_0, ar_1, ar_2) -> Com_1(evalaxstart(ar_0, ar_1, ar_2)) [ 0 <= 0 ]", 0-2) = ar_2
4.65/2.21	
4.65/2.21		S("evalaxstart(ar_0, ar_1, ar_2) -> Com_1(evalaxentryin(ar_0, ar_1, ar_2))", 0-0) = ar_0
4.65/2.21	
4.65/2.21		S("evalaxstart(ar_0, ar_1, ar_2) -> Com_1(evalaxentryin(ar_0, ar_1, ar_2))", 0-1) = ar_1
4.65/2.21	
4.65/2.21		S("evalaxstart(ar_0, ar_1, ar_2) -> Com_1(evalaxentryin(ar_0, ar_1, ar_2))", 0-2) = ar_2
4.65/2.21	
4.65/2.21		S("evalaxentryin(ar_0, ar_1, ar_2) -> Com_1(evalaxbbin(0, ar_1, ar_2))", 0-0) = 0
4.65/2.21	
4.65/2.21		S("evalaxentryin(ar_0, ar_1, ar_2) -> Com_1(evalaxbbin(0, ar_1, ar_2))", 0-1) = ar_1
4.65/2.21	
4.65/2.21		S("evalaxentryin(ar_0, ar_1, ar_2) -> Com_1(evalaxbbin(0, ar_1, ar_2))", 0-2) = ar_2
4.65/2.21	
4.65/2.21		S("evalaxbbin(ar_0, ar_1, ar_2) -> Com_1(evalaxbb2in(ar_0, 0, ar_2))", 0-0) = ar_2
4.65/2.21	
4.65/2.21		S("evalaxbbin(ar_0, ar_1, ar_2) -> Com_1(evalaxbb2in(ar_0, 0, ar_2))", 0-1) = 0
4.65/2.21	
4.65/2.21		S("evalaxbbin(ar_0, ar_1, ar_2) -> Com_1(evalaxbb2in(ar_0, 0, ar_2))", 0-2) = ar_2
4.65/2.21	
4.65/2.21		S("evalaxbb2in(ar_0, ar_1, ar_2) -> Com_1(evalaxbb1in(ar_0, ar_1, ar_2)) [ ar_2 >= ar_1 + 2 ]", 0-0) = ar_2
4.65/2.21	
4.65/2.21		S("evalaxbb2in(ar_0, ar_1, ar_2) -> Com_1(evalaxbb1in(ar_0, ar_1, ar_2)) [ ar_2 >= ar_1 + 2 ]", 0-1) = ?
4.65/2.21	
4.65/2.21		S("evalaxbb2in(ar_0, ar_1, ar_2) -> Com_1(evalaxbb1in(ar_0, ar_1, ar_2)) [ ar_2 >= ar_1 + 2 ]", 0-2) = ar_2
4.65/2.21	
4.65/2.21		S("evalaxbb2in(ar_0, ar_1, ar_2) -> Com_1(evalaxbb3in(ar_0, ar_1, ar_2)) [ ar_1 + 1 >= ar_2 ]", 0-0) = ar_2
4.65/2.21	
4.65/2.21		S("evalaxbb2in(ar_0, ar_1, ar_2) -> Com_1(evalaxbb3in(ar_0, ar_1, ar_2)) [ ar_1 + 1 >= ar_2 ]", 0-1) = ?
4.65/2.21	
4.65/2.21		S("evalaxbb2in(ar_0, ar_1, ar_2) -> Com_1(evalaxbb3in(ar_0, ar_1, ar_2)) [ ar_1 + 1 >= ar_2 ]", 0-2) = ar_2
4.65/2.21	
4.65/2.21		S("evalaxbb1in(ar_0, ar_1, ar_2) -> Com_1(evalaxbb2in(ar_0, ar_1 + 1, ar_2))", 0-0) = ar_2
4.65/2.21	
4.65/2.21		S("evalaxbb1in(ar_0, ar_1, ar_2) -> Com_1(evalaxbb2in(ar_0, ar_1 + 1, ar_2))", 0-1) = ?
4.65/2.21	
4.65/2.21		S("evalaxbb1in(ar_0, ar_1, ar_2) -> Com_1(evalaxbb2in(ar_0, ar_1 + 1, ar_2))", 0-2) = ar_2
4.65/2.21	
4.65/2.21		S("evalaxbb3in(ar_0, ar_1, ar_2) -> Com_1(evalaxbbin(ar_0 + 1, ar_1, ar_2)) [ ar_1 + 1 >= ar_2 /\\ ar_2 >= ar_0 + 3 ]", 0-0) = ar_2
4.65/2.21	
4.65/2.21		S("evalaxbb3in(ar_0, ar_1, ar_2) -> Com_1(evalaxbbin(ar_0 + 1, ar_1, ar_2)) [ ar_1 + 1 >= ar_2 /\\ ar_2 >= ar_0 + 3 ]", 0-1) = ?
4.65/2.21	
4.65/2.21		S("evalaxbb3in(ar_0, ar_1, ar_2) -> Com_1(evalaxbbin(ar_0 + 1, ar_1, ar_2)) [ ar_1 + 1 >= ar_2 /\\ ar_2 >= ar_0 + 3 ]", 0-2) = ar_2
4.65/2.21	
4.65/2.21		S("evalaxbb3in(ar_0, ar_1, ar_2) -> Com_1(evalaxreturnin(ar_0, ar_1, ar_2)) [ ar_0 + 2 >= ar_2 ]", 0-0) = ar_2
4.65/2.21	
4.65/2.21		S("evalaxbb3in(ar_0, ar_1, ar_2) -> Com_1(evalaxreturnin(ar_0, ar_1, ar_2)) [ ar_0 + 2 >= ar_2 ]", 0-1) = ?
4.65/2.21	
4.65/2.21		S("evalaxbb3in(ar_0, ar_1, ar_2) -> Com_1(evalaxreturnin(ar_0, ar_1, ar_2)) [ ar_0 + 2 >= ar_2 ]", 0-2) = ar_2
4.65/2.21	
4.65/2.21		S("evalaxreturnin(ar_0, ar_1, ar_2) -> Com_1(evalaxstop(ar_0, ar_1, ar_2))", 0-0) = ar_2
4.65/2.21	
4.65/2.21		S("evalaxreturnin(ar_0, ar_1, ar_2) -> Com_1(evalaxstop(ar_0, ar_1, ar_2))", 0-1) = ?
4.65/2.21	
4.65/2.21		S("evalaxreturnin(ar_0, ar_1, ar_2) -> Com_1(evalaxstop(ar_0, ar_1, ar_2))", 0-2) = ar_2
4.65/2.21	
4.65/2.21	orients the transitions
4.65/2.21	
4.65/2.21		evalaxbb2in(ar_0, ar_1, ar_2) -> Com_1(evalaxbb3in(ar_0, ar_1, ar_2)) [ ar_1 + 1 >= ar_2 ]
4.65/2.21	
4.65/2.21		evalaxbb2in(ar_0, ar_1, ar_2) -> Com_1(evalaxbb1in(ar_0, ar_1, ar_2)) [ ar_2 >= ar_1 + 2 ]
4.65/2.21	
4.65/2.21		evalaxbb1in(ar_0, ar_1, ar_2) -> Com_1(evalaxbb2in(ar_0, ar_1 + 1, ar_2))
4.65/2.21	
4.65/2.21	weakly and the transition
4.65/2.21	
4.65/2.21		evalaxbb2in(ar_0, ar_1, ar_2) -> Com_1(evalaxbb3in(ar_0, ar_1, ar_2)) [ ar_1 + 1 >= ar_2 ]
4.65/2.21	
4.65/2.21	strictly and produces the following problem:
4.65/2.21	
4.65/2.21	7:	T:
4.65/2.21	
4.65/2.21			(Comp: 2, Cost: 1)           evalaxreturnin(ar_0, ar_1, ar_2) -> Com_1(evalaxstop(ar_0, ar_1, ar_2))
4.65/2.21	
4.65/2.21			(Comp: 2, Cost: 1)           evalaxbb3in(ar_0, ar_1, ar_2) -> Com_1(evalaxreturnin(ar_0, ar_1, ar_2)) [ ar_0 + 2 >= ar_2 ]
4.65/2.21	
4.65/2.21			(Comp: ar_2, Cost: 1)        evalaxbb3in(ar_0, ar_1, ar_2) -> Com_1(evalaxbbin(ar_0 + 1, ar_1, ar_2)) [ ar_1 + 1 >= ar_2 /\ ar_2 >= ar_0 + 3 ]
4.65/2.21	
4.65/2.21			(Comp: ?, Cost: 1)           evalaxbb1in(ar_0, ar_1, ar_2) -> Com_1(evalaxbb2in(ar_0, ar_1 + 1, ar_2))
4.65/2.21	
4.65/2.21			(Comp: ar_2 + 1, Cost: 1)    evalaxbb2in(ar_0, ar_1, ar_2) -> Com_1(evalaxbb3in(ar_0, ar_1, ar_2)) [ ar_1 + 1 >= ar_2 ]
4.65/2.21	
4.65/2.21			(Comp: ?, Cost: 1)           evalaxbb2in(ar_0, ar_1, ar_2) -> Com_1(evalaxbb1in(ar_0, ar_1, ar_2)) [ ar_2 >= ar_1 + 2 ]
4.65/2.21	
4.65/2.21			(Comp: ar_2 + 1, Cost: 1)    evalaxbbin(ar_0, ar_1, ar_2) -> Com_1(evalaxbb2in(ar_0, 0, ar_2))
4.65/2.21	
4.65/2.21			(Comp: 1, Cost: 1)           evalaxentryin(ar_0, ar_1, ar_2) -> Com_1(evalaxbbin(0, ar_1, ar_2))
4.65/2.21	
4.65/2.21			(Comp: 1, Cost: 1)           evalaxstart(ar_0, ar_1, ar_2) -> Com_1(evalaxentryin(ar_0, ar_1, ar_2))
4.65/2.21	
4.65/2.21			(Comp: 1, Cost: 0)           koat_start(ar_0, ar_1, ar_2) -> Com_1(evalaxstart(ar_0, ar_1, ar_2)) [ 0 <= 0 ]
4.65/2.21	
4.65/2.21		start location:	koat_start
4.65/2.21	
4.65/2.21		leaf cost:	0
4.65/2.21	
4.65/2.21	
4.65/2.21	
4.65/2.21	A polynomial rank function with
4.65/2.21	
4.65/2.21		Pol(evalaxbb2in) = -V_2 + V_3
4.65/2.21	
4.65/2.21		Pol(evalaxbb1in) = -V_2 + V_3 - 1
4.65/2.21	
4.65/2.21	and size complexities
4.65/2.21	
4.65/2.21		S("koat_start(ar_0, ar_1, ar_2) -> Com_1(evalaxstart(ar_0, ar_1, ar_2)) [ 0 <= 0 ]", 0-0) = ar_0
4.65/2.21	
4.65/2.21		S("koat_start(ar_0, ar_1, ar_2) -> Com_1(evalaxstart(ar_0, ar_1, ar_2)) [ 0 <= 0 ]", 0-1) = ar_1
4.65/2.21	
4.65/2.21		S("koat_start(ar_0, ar_1, ar_2) -> Com_1(evalaxstart(ar_0, ar_1, ar_2)) [ 0 <= 0 ]", 0-2) = ar_2
4.65/2.21	
4.65/2.21		S("evalaxstart(ar_0, ar_1, ar_2) -> Com_1(evalaxentryin(ar_0, ar_1, ar_2))", 0-0) = ar_0
4.65/2.21	
4.65/2.21		S("evalaxstart(ar_0, ar_1, ar_2) -> Com_1(evalaxentryin(ar_0, ar_1, ar_2))", 0-1) = ar_1
4.65/2.21	
4.65/2.21		S("evalaxstart(ar_0, ar_1, ar_2) -> Com_1(evalaxentryin(ar_0, ar_1, ar_2))", 0-2) = ar_2
4.65/2.21	
4.65/2.21		S("evalaxentryin(ar_0, ar_1, ar_2) -> Com_1(evalaxbbin(0, ar_1, ar_2))", 0-0) = 0
4.65/2.21	
4.65/2.21		S("evalaxentryin(ar_0, ar_1, ar_2) -> Com_1(evalaxbbin(0, ar_1, ar_2))", 0-1) = ar_1
4.65/2.21	
4.65/2.21		S("evalaxentryin(ar_0, ar_1, ar_2) -> Com_1(evalaxbbin(0, ar_1, ar_2))", 0-2) = ar_2
4.65/2.21	
4.65/2.21		S("evalaxbbin(ar_0, ar_1, ar_2) -> Com_1(evalaxbb2in(ar_0, 0, ar_2))", 0-0) = ar_2
4.65/2.21	
4.65/2.21		S("evalaxbbin(ar_0, ar_1, ar_2) -> Com_1(evalaxbb2in(ar_0, 0, ar_2))", 0-1) = 0
4.65/2.21	
4.65/2.21		S("evalaxbbin(ar_0, ar_1, ar_2) -> Com_1(evalaxbb2in(ar_0, 0, ar_2))", 0-2) = ar_2
4.65/2.21	
4.65/2.21		S("evalaxbb2in(ar_0, ar_1, ar_2) -> Com_1(evalaxbb1in(ar_0, ar_1, ar_2)) [ ar_2 >= ar_1 + 2 ]", 0-0) = ar_2
4.65/2.21	
4.65/2.21		S("evalaxbb2in(ar_0, ar_1, ar_2) -> Com_1(evalaxbb1in(ar_0, ar_1, ar_2)) [ ar_2 >= ar_1 + 2 ]", 0-1) = ?
4.65/2.21	
4.65/2.21		S("evalaxbb2in(ar_0, ar_1, ar_2) -> Com_1(evalaxbb1in(ar_0, ar_1, ar_2)) [ ar_2 >= ar_1 + 2 ]", 0-2) = ar_2
4.65/2.21	
4.65/2.21		S("evalaxbb2in(ar_0, ar_1, ar_2) -> Com_1(evalaxbb3in(ar_0, ar_1, ar_2)) [ ar_1 + 1 >= ar_2 ]", 0-0) = ar_2
4.65/2.21	
4.65/2.21		S("evalaxbb2in(ar_0, ar_1, ar_2) -> Com_1(evalaxbb3in(ar_0, ar_1, ar_2)) [ ar_1 + 1 >= ar_2 ]", 0-1) = ?
4.65/2.21	
4.65/2.21		S("evalaxbb2in(ar_0, ar_1, ar_2) -> Com_1(evalaxbb3in(ar_0, ar_1, ar_2)) [ ar_1 + 1 >= ar_2 ]", 0-2) = ar_2
4.65/2.21	
4.65/2.21		S("evalaxbb1in(ar_0, ar_1, ar_2) -> Com_1(evalaxbb2in(ar_0, ar_1 + 1, ar_2))", 0-0) = ar_2
4.65/2.21	
4.65/2.21		S("evalaxbb1in(ar_0, ar_1, ar_2) -> Com_1(evalaxbb2in(ar_0, ar_1 + 1, ar_2))", 0-1) = ?
4.65/2.21	
4.65/2.21		S("evalaxbb1in(ar_0, ar_1, ar_2) -> Com_1(evalaxbb2in(ar_0, ar_1 + 1, ar_2))", 0-2) = ar_2
4.65/2.21	
4.65/2.21		S("evalaxbb3in(ar_0, ar_1, ar_2) -> Com_1(evalaxbbin(ar_0 + 1, ar_1, ar_2)) [ ar_1 + 1 >= ar_2 /\\ ar_2 >= ar_0 + 3 ]", 0-0) = ar_2
4.65/2.21	
4.65/2.21		S("evalaxbb3in(ar_0, ar_1, ar_2) -> Com_1(evalaxbbin(ar_0 + 1, ar_1, ar_2)) [ ar_1 + 1 >= ar_2 /\\ ar_2 >= ar_0 + 3 ]", 0-1) = ?
4.65/2.21	
4.65/2.21		S("evalaxbb3in(ar_0, ar_1, ar_2) -> Com_1(evalaxbbin(ar_0 + 1, ar_1, ar_2)) [ ar_1 + 1 >= ar_2 /\\ ar_2 >= ar_0 + 3 ]", 0-2) = ar_2
4.65/2.21	
4.65/2.21		S("evalaxbb3in(ar_0, ar_1, ar_2) -> Com_1(evalaxreturnin(ar_0, ar_1, ar_2)) [ ar_0 + 2 >= ar_2 ]", 0-0) = ar_2
4.65/2.21	
4.65/2.21		S("evalaxbb3in(ar_0, ar_1, ar_2) -> Com_1(evalaxreturnin(ar_0, ar_1, ar_2)) [ ar_0 + 2 >= ar_2 ]", 0-1) = ?
4.65/2.21	
4.65/2.21		S("evalaxbb3in(ar_0, ar_1, ar_2) -> Com_1(evalaxreturnin(ar_0, ar_1, ar_2)) [ ar_0 + 2 >= ar_2 ]", 0-2) = ar_2
4.65/2.21	
4.65/2.21		S("evalaxreturnin(ar_0, ar_1, ar_2) -> Com_1(evalaxstop(ar_0, ar_1, ar_2))", 0-0) = ar_2
4.65/2.21	
4.65/2.21		S("evalaxreturnin(ar_0, ar_1, ar_2) -> Com_1(evalaxstop(ar_0, ar_1, ar_2))", 0-1) = ?
4.65/2.21	
4.65/2.21		S("evalaxreturnin(ar_0, ar_1, ar_2) -> Com_1(evalaxstop(ar_0, ar_1, ar_2))", 0-2) = ar_2
4.65/2.21	
4.65/2.21	orients the transitions
4.65/2.21	
4.65/2.21		evalaxbb2in(ar_0, ar_1, ar_2) -> Com_1(evalaxbb1in(ar_0, ar_1, ar_2)) [ ar_2 >= ar_1 + 2 ]
4.65/2.21	
4.65/2.21		evalaxbb1in(ar_0, ar_1, ar_2) -> Com_1(evalaxbb2in(ar_0, ar_1 + 1, ar_2))
4.65/2.21	
4.65/2.21	weakly and the transition
4.65/2.21	
4.65/2.21		evalaxbb2in(ar_0, ar_1, ar_2) -> Com_1(evalaxbb1in(ar_0, ar_1, ar_2)) [ ar_2 >= ar_1 + 2 ]
4.65/2.21	
4.65/2.21	strictly and produces the following problem:
4.65/2.21	
4.65/2.21	8:	T:
4.65/2.21	
4.65/2.21			(Comp: 2, Cost: 1)                evalaxreturnin(ar_0, ar_1, ar_2) -> Com_1(evalaxstop(ar_0, ar_1, ar_2))
4.65/2.21	
4.65/2.21			(Comp: 2, Cost: 1)                evalaxbb3in(ar_0, ar_1, ar_2) -> Com_1(evalaxreturnin(ar_0, ar_1, ar_2)) [ ar_0 + 2 >= ar_2 ]
4.65/2.21	
4.65/2.21			(Comp: ar_2, Cost: 1)             evalaxbb3in(ar_0, ar_1, ar_2) -> Com_1(evalaxbbin(ar_0 + 1, ar_1, ar_2)) [ ar_1 + 1 >= ar_2 /\ ar_2 >= ar_0 + 3 ]
4.65/2.21	
4.65/2.21			(Comp: ?, Cost: 1)                evalaxbb1in(ar_0, ar_1, ar_2) -> Com_1(evalaxbb2in(ar_0, ar_1 + 1, ar_2))
4.65/2.21	
4.65/2.21			(Comp: ar_2 + 1, Cost: 1)         evalaxbb2in(ar_0, ar_1, ar_2) -> Com_1(evalaxbb3in(ar_0, ar_1, ar_2)) [ ar_1 + 1 >= ar_2 ]
4.65/2.21	
4.65/2.21			(Comp: ar_2^2 + ar_2, Cost: 1)    evalaxbb2in(ar_0, ar_1, ar_2) -> Com_1(evalaxbb1in(ar_0, ar_1, ar_2)) [ ar_2 >= ar_1 + 2 ]
4.65/2.21	
4.65/2.21			(Comp: ar_2 + 1, Cost: 1)         evalaxbbin(ar_0, ar_1, ar_2) -> Com_1(evalaxbb2in(ar_0, 0, ar_2))
4.65/2.21	
4.65/2.21			(Comp: 1, Cost: 1)                evalaxentryin(ar_0, ar_1, ar_2) -> Com_1(evalaxbbin(0, ar_1, ar_2))
4.65/2.21	
4.65/2.21			(Comp: 1, Cost: 1)                evalaxstart(ar_0, ar_1, ar_2) -> Com_1(evalaxentryin(ar_0, ar_1, ar_2))
4.65/2.21	
4.65/2.21			(Comp: 1, Cost: 0)                koat_start(ar_0, ar_1, ar_2) -> Com_1(evalaxstart(ar_0, ar_1, ar_2)) [ 0 <= 0 ]
4.65/2.21	
4.65/2.21		start location:	koat_start
4.65/2.21	
4.65/2.21		leaf cost:	0
4.65/2.21	
4.65/2.21	
4.65/2.21	
4.65/2.21	Repeatedly propagating knowledge in problem 8 produces the following problem:
4.65/2.21	
4.65/2.21	9:	T:
4.65/2.21	
4.65/2.21			(Comp: 2, Cost: 1)                evalaxreturnin(ar_0, ar_1, ar_2) -> Com_1(evalaxstop(ar_0, ar_1, ar_2))
4.65/2.21	
4.65/2.21			(Comp: 2, Cost: 1)                evalaxbb3in(ar_0, ar_1, ar_2) -> Com_1(evalaxreturnin(ar_0, ar_1, ar_2)) [ ar_0 + 2 >= ar_2 ]
4.65/2.21	
4.65/2.21			(Comp: ar_2, Cost: 1)             evalaxbb3in(ar_0, ar_1, ar_2) -> Com_1(evalaxbbin(ar_0 + 1, ar_1, ar_2)) [ ar_1 + 1 >= ar_2 /\ ar_2 >= ar_0 + 3 ]
4.65/2.21	
4.65/2.21			(Comp: ar_2^2 + ar_2, Cost: 1)    evalaxbb1in(ar_0, ar_1, ar_2) -> Com_1(evalaxbb2in(ar_0, ar_1 + 1, ar_2))
4.65/2.21	
4.65/2.21			(Comp: ar_2 + 1, Cost: 1)         evalaxbb2in(ar_0, ar_1, ar_2) -> Com_1(evalaxbb3in(ar_0, ar_1, ar_2)) [ ar_1 + 1 >= ar_2 ]
4.65/2.21	
4.65/2.21			(Comp: ar_2^2 + ar_2, Cost: 1)    evalaxbb2in(ar_0, ar_1, ar_2) -> Com_1(evalaxbb1in(ar_0, ar_1, ar_2)) [ ar_2 >= ar_1 + 2 ]
4.65/2.21	
4.65/2.21			(Comp: ar_2 + 1, Cost: 1)         evalaxbbin(ar_0, ar_1, ar_2) -> Com_1(evalaxbb2in(ar_0, 0, ar_2))
4.65/2.21	
4.65/2.21			(Comp: 1, Cost: 1)                evalaxentryin(ar_0, ar_1, ar_2) -> Com_1(evalaxbbin(0, ar_1, ar_2))
4.65/2.21	
4.65/2.21			(Comp: 1, Cost: 1)                evalaxstart(ar_0, ar_1, ar_2) -> Com_1(evalaxentryin(ar_0, ar_1, ar_2))
4.65/2.21	
4.65/2.21			(Comp: 1, Cost: 0)                koat_start(ar_0, ar_1, ar_2) -> Com_1(evalaxstart(ar_0, ar_1, ar_2)) [ 0 <= 0 ]
4.65/2.21	
4.65/2.21		start location:	koat_start
4.65/2.21	
4.65/2.21		leaf cost:	0
4.65/2.21	
4.65/2.21	
4.65/2.21	
4.65/2.21	Complexity upper bound 5*ar_2 + 2*ar_2^2 + 8
4.65/2.21	
4.65/2.21	
4.65/2.21	
4.65/2.21	Time: 0.146 sec (SMT: 0.131 sec)
4.65/2.21	
4.65/2.21	
4.65/2.21	----------------------------------------
4.65/2.21	
4.65/2.21	(2)
4.65/2.21	BOUNDS(1, n^2)
4.65/2.21	
4.65/2.21	----------------------------------------
4.65/2.21	
4.65/2.21	(3) Loat Proof (FINISHED)
4.65/2.21	
4.65/2.21	
4.65/2.21	### Pre-processing the ITS problem ###
4.65/2.21	
4.65/2.21	
4.65/2.21	
4.65/2.21	Initial linear ITS problem
4.65/2.21	
4.65/2.21	   Start location: evalaxstart
4.65/2.21	
4.65/2.21	      0: evalaxstart -> evalaxentryin : [], cost: 1
4.65/2.21	
4.65/2.21	      1: evalaxentryin -> evalaxbbin : A'=0, [], cost: 1
4.65/2.21	
4.65/2.21	      2: evalaxbbin -> evalaxbb2in : B'=0, [], cost: 1
4.65/2.21	
4.65/2.21	      3: evalaxbb2in -> evalaxbb1in : [ C>=2+B ], cost: 1
4.65/2.21	
4.65/2.21	      4: evalaxbb2in -> evalaxbb3in : [ 1+B>=C ], cost: 1
4.65/2.21	
4.65/2.21	      5: evalaxbb1in -> evalaxbb2in : B'=1+B, [], cost: 1
4.65/2.21	
4.65/2.21	      6: evalaxbb3in -> evalaxbbin : A'=1+A, [ 1+B>=C && C>=3+A ], cost: 1
4.65/2.21	
4.65/2.21	      7: evalaxbb3in -> evalaxreturnin : [ C>=2+B ], cost: 1
4.65/2.21	
4.65/2.21	      8: evalaxbb3in -> evalaxreturnin : [ 2+A>=C ], cost: 1
4.65/2.21	
4.65/2.21	      9: evalaxreturnin -> evalaxstop : [], cost: 1
4.65/2.21	
4.65/2.21	
4.65/2.21	
4.65/2.21	Removed unreachable and leaf rules:
4.65/2.21	
4.65/2.21	   Start location: evalaxstart
4.65/2.21	
4.65/2.21	      0: evalaxstart -> evalaxentryin : [], cost: 1
4.65/2.21	
4.65/2.21	      1: evalaxentryin -> evalaxbbin : A'=0, [], cost: 1
4.65/2.21	
4.65/2.21	      2: evalaxbbin -> evalaxbb2in : B'=0, [], cost: 1
4.65/2.21	
4.65/2.21	      3: evalaxbb2in -> evalaxbb1in : [ C>=2+B ], cost: 1
4.65/2.21	
4.65/2.21	      4: evalaxbb2in -> evalaxbb3in : [ 1+B>=C ], cost: 1
4.65/2.21	
4.65/2.21	      5: evalaxbb1in -> evalaxbb2in : B'=1+B, [], cost: 1
4.65/2.21	
4.65/2.21	      6: evalaxbb3in -> evalaxbbin : A'=1+A, [ 1+B>=C && C>=3+A ], cost: 1
4.65/2.21	
4.65/2.21	
4.65/2.21	
4.65/2.21	### Simplification by acceleration and chaining ###
4.65/2.21	
4.65/2.21	
4.65/2.21	
4.65/2.21	Eliminated locations (on linear paths):
4.65/2.21	
4.65/2.21	   Start location: evalaxstart
4.65/2.21	
4.65/2.21	     10: evalaxstart -> evalaxbbin : A'=0, [], cost: 2
4.65/2.21	
4.65/2.21	      2: evalaxbbin -> evalaxbb2in : B'=0, [], cost: 1
4.65/2.21	
4.65/2.21	     11: evalaxbb2in -> evalaxbb2in : B'=1+B, [ C>=2+B ], cost: 2
4.65/2.21	
4.65/2.21	     12: evalaxbb2in -> evalaxbbin : A'=1+A, [ 1+B>=C && C>=3+A ], cost: 2
4.65/2.21	
4.65/2.21	
4.65/2.21	
4.65/2.21	Accelerating simple loops of location 3.
4.65/2.21	
4.65/2.21	   Accelerating the following rules:
4.65/2.21	
4.65/2.21	     11: evalaxbb2in -> evalaxbb2in : B'=1+B, [ C>=2+B ], cost: 2
4.65/2.21	
4.65/2.21	
4.65/2.21	
4.65/2.21	   Accelerated rule 11 with metering function -1+C-B, yielding the new rule 13.
4.65/2.21	
4.65/2.21	   Removing the simple loops: 11.
4.65/2.21	
4.65/2.21	
4.65/2.21	
4.65/2.21	Accelerated all simple loops using metering functions (where possible):
4.65/2.21	
4.65/2.21	   Start location: evalaxstart
4.65/2.21	
4.65/2.21	     10: evalaxstart -> evalaxbbin : A'=0, [], cost: 2
4.65/2.21	
4.65/2.21	      2: evalaxbbin -> evalaxbb2in : B'=0, [], cost: 1
4.65/2.21	
4.65/2.21	     12: evalaxbb2in -> evalaxbbin : A'=1+A, [ 1+B>=C && C>=3+A ], cost: 2
4.65/2.21	
4.65/2.21	     13: evalaxbb2in -> evalaxbb2in : B'=-1+C, [ C>=2+B ], cost: -2+2*C-2*B
4.65/2.21	
4.65/2.21	
4.65/2.21	
4.65/2.21	Chained accelerated rules (with incoming rules):
4.65/2.21	
4.65/2.21	   Start location: evalaxstart
4.65/2.21	
4.65/2.21	     10: evalaxstart -> evalaxbbin : A'=0, [], cost: 2
4.65/2.21	
4.65/2.21	      2: evalaxbbin -> evalaxbb2in : B'=0, [], cost: 1
4.65/2.21	
4.65/2.21	     14: evalaxbbin -> evalaxbb2in : B'=-1+C, [ C>=2 ], cost: -1+2*C
4.65/2.21	
4.65/2.21	     12: evalaxbb2in -> evalaxbbin : A'=1+A, [ 1+B>=C && C>=3+A ], cost: 2
4.65/2.21	
4.65/2.21	
4.65/2.21	
4.65/2.21	Eliminated locations (on tree-shaped paths):
4.65/2.21	
4.65/2.21	   Start location: evalaxstart
4.65/2.21	
4.65/2.21	     10: evalaxstart -> evalaxbbin : A'=0, [], cost: 2
4.65/2.21	
4.65/2.21	     15: evalaxbbin -> evalaxbbin : A'=1+A, B'=0, [ 1>=C && C>=3+A ], cost: 3
4.65/2.21	
4.65/2.21	     16: evalaxbbin -> evalaxbbin : A'=1+A, B'=-1+C, [ C>=2 && C>=3+A ], cost: 1+2*C
4.65/2.21	
4.65/2.21	
4.65/2.21	
4.65/2.21	Accelerating simple loops of location 2.
4.65/2.21	
4.65/2.21	   Accelerating the following rules:
4.65/2.21	
4.65/2.21	     15: evalaxbbin -> evalaxbbin : A'=1+A, B'=0, [ 1>=C && C>=3+A ], cost: 3
4.65/2.21	
4.65/2.21	     16: evalaxbbin -> evalaxbbin : A'=1+A, B'=-1+C, [ C>=2 && C>=3+A ], cost: 1+2*C
4.65/2.21	
4.65/2.21	
4.65/2.21	
4.65/2.21	   Accelerated rule 15 with metering function -2+C-A, yielding the new rule 17.
4.65/2.21	
4.65/2.21	   Accelerated rule 16 with metering function -2+C-A, yielding the new rule 18.
4.65/2.21	
4.65/2.21	   Removing the simple loops: 15 16.
4.65/2.21	
4.65/2.21	
4.65/2.21	
4.65/2.21	Accelerated all simple loops using metering functions (where possible):
4.65/2.21	
4.65/2.21	   Start location: evalaxstart
4.65/2.21	
4.65/2.21	     10: evalaxstart -> evalaxbbin : A'=0, [], cost: 2
4.65/2.21	
4.65/2.21	     17: evalaxbbin -> evalaxbbin : A'=-2+C, B'=0, [ 1>=C && C>=3+A ], cost: -6+3*C-3*A
4.65/2.21	
4.65/2.21	     18: evalaxbbin -> evalaxbbin : A'=-2+C, B'=-1+C, [ C>=2 && C>=3+A ], cost: -2+C+2*C*(-2+C-A)-A
4.65/2.21	
4.65/2.21	
4.65/2.21	
4.65/2.21	Chained accelerated rules (with incoming rules):
4.65/2.21	
4.65/2.21	   Start location: evalaxstart
4.65/2.21	
4.65/2.21	     10: evalaxstart -> evalaxbbin : A'=0, [], cost: 2
4.65/2.21	
4.65/2.21	     19: evalaxstart -> evalaxbbin : A'=-2+C, B'=-1+C, [ C>=3 ], cost: 2*(-2+C)*C+C
4.65/2.21	
4.65/2.21	
4.65/2.21	
4.65/2.21	Removed unreachable locations (and leaf rules with constant cost):
4.65/2.21	
4.65/2.21	   Start location: evalaxstart
4.65/2.21	
4.65/2.21	     19: evalaxstart -> evalaxbbin : A'=-2+C, B'=-1+C, [ C>=3 ], cost: 2*(-2+C)*C+C
4.65/2.21	
4.65/2.21	
4.65/2.21	
4.65/2.21	### Computing asymptotic complexity ###
4.65/2.21	
4.65/2.21	
4.65/2.21	
4.65/2.21	Fully simplified ITS problem
4.65/2.21	
4.65/2.21	   Start location: evalaxstart
4.65/2.21	
4.65/2.21	     19: evalaxstart -> evalaxbbin : A'=-2+C, B'=-1+C, [ C>=3 ], cost: 2*(-2+C)*C+C
4.65/2.21	
4.65/2.21	
4.65/2.21	
4.65/2.21	Computing asymptotic complexity for rule 19
4.65/2.21	
4.65/2.21	   Solved the limit problem by the following transformations:
4.65/2.21	
4.65/2.21	      Created initial limit problem:
4.65/2.21	
4.65/2.21	      -2+C (+/+!), 2*C^2-3*C (+) [not solved]
4.65/2.21	
4.65/2.21	
4.65/2.21	
4.65/2.21	      removing all constraints (solved by SMT)
4.65/2.21	
4.65/2.21	      resulting limit problem: [solved]
4.65/2.21	
4.65/2.21	
4.65/2.21	
4.65/2.21	      applying transformation rule (C) using substitution {C==n}
4.65/2.21	
4.65/2.21	      resulting limit problem:
4.65/2.21	
4.65/2.21	      [solved]
4.65/2.21	
4.65/2.21	
4.65/2.21	
4.65/2.21	   Solution:
4.65/2.21	
4.65/2.21	      C / n
4.65/2.21	
4.65/2.21	   Resulting cost 2*n^2-3*n has complexity: Poly(n^2)
4.65/2.21	
4.65/2.21	
4.65/2.21	
4.65/2.21	Found new complexity Poly(n^2).
4.65/2.21	
4.65/2.21	
4.65/2.21	
4.65/2.21	Obtained the following overall complexity (w.r.t. the length of the input n):
4.65/2.21	
4.65/2.21	   Complexity:  Poly(n^2)
4.65/2.21	
4.65/2.21	   Cpx degree:  2
4.65/2.21	
4.65/2.21	   Solved cost: 2*n^2-3*n
4.65/2.21	
4.65/2.21	   Rule cost:   2*(-2+C)*C+C
4.65/2.21	
4.65/2.21	   Rule guard:  [ C>=3 ]
4.65/2.21	
4.65/2.21	
4.65/2.21	
4.65/2.21	WORST_CASE(Omega(n^2),?)
4.65/2.21	
4.65/2.21	
4.65/2.21	----------------------------------------
4.65/2.21	
4.65/2.21	(4)
4.65/2.21	BOUNDS(n^2, INF)
4.65/2.23	EOF