/export/starexec/sandbox2/solver/bin/starexec_run_complexity /export/starexec/sandbox2/benchmark/theBenchmark.koat /export/starexec/sandbox2/output/output_files


--------------------------------------------------------------------------------


WORST_CASE(Omega(n^2), O(n^2))
proof of /export/starexec/sandbox2/benchmark/theBenchmark.koat
# AProVE Commit ID: 794c25de1cacf0d048858bcd21c9a779e1221865 marcel 20200619 unpublished dirty


The runtime complexity of the given CpxIntTrs could be proven to be BOUNDS(n^2, n^2).

(0) CpxIntTrs
(1) Koat Proof [FINISHED, 11 ms]
(2) BOUNDS(1, n^2)
(3) Loat Proof [FINISHED, 491 ms]
(4) BOUNDS(n^2, INF)


----------------------------------------

(0)
Obligation:
Complexity Int TRS consisting of the following rules:
evalaxstart(A, B, C) -> Com_1(evalaxentryin(A, B, C)) :|: TRUE
evalaxentryin(A, B, C) -> Com_1(evalaxbbin(0, B, C)) :|: TRUE
evalaxbbin(A, B, C) -> Com_1(evalaxbb2in(A, 0, C)) :|: TRUE
evalaxbb2in(A, B, C) -> Com_1(evalaxbb1in(A, B, C)) :|: C >= 2 + B
evalaxbb2in(A, B, C) -> Com_1(evalaxbb3in(A, B, C)) :|: B + 1 >= C
evalaxbb1in(A, B, C) -> Com_1(evalaxbb2in(A, B + 1, C)) :|: TRUE
evalaxbb3in(A, B, C) -> Com_1(evalaxbbin(A + 1, B, C)) :|: B + 1 >= C && C >= 3 + A
evalaxbb3in(A, B, C) -> Com_1(evalaxreturnin(A, B, C)) :|: C >= 2 + B
evalaxbb3in(A, B, C) -> Com_1(evalaxreturnin(A, B, C)) :|: A + 2 >= C
evalaxreturnin(A, B, C) -> Com_1(evalaxstop(A, B, C)) :|: TRUE

The start-symbols are:[evalaxstart_3]


----------------------------------------

(1) Koat Proof (FINISHED)
YES(?, 5*Ar_2 + 2*Ar_2^2 + 8)



Initial complexity problem:

1:	T:

		(Comp: ?, Cost: 1)    evalaxstart(Ar_0, Ar_1, Ar_2) -> Com_1(evalaxentryin(Ar_0, Ar_1, Ar_2))

		(Comp: ?, Cost: 1)    evalaxentryin(Ar_0, Ar_1, Ar_2) -> Com_1(evalaxbbin(0, Ar_1, Ar_2))

		(Comp: ?, Cost: 1)    evalaxbbin(Ar_0, Ar_1, Ar_2) -> Com_1(evalaxbb2in(Ar_0, 0, Ar_2))

		(Comp: ?, Cost: 1)    evalaxbb2in(Ar_0, Ar_1, Ar_2) -> Com_1(evalaxbb1in(Ar_0, Ar_1, Ar_2)) [ Ar_2 >= Ar_1 + 2 ]

		(Comp: ?, Cost: 1)    evalaxbb2in(Ar_0, Ar_1, Ar_2) -> Com_1(evalaxbb3in(Ar_0, Ar_1, Ar_2)) [ Ar_1 + 1 >= Ar_2 ]

		(Comp: ?, Cost: 1)    evalaxbb1in(Ar_0, Ar_1, Ar_2) -> Com_1(evalaxbb2in(Ar_0, Ar_1 + 1, Ar_2))

		(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 ]

		(Comp: ?, Cost: 1)    evalaxbb3in(Ar_0, Ar_1, Ar_2) -> Com_1(evalaxreturnin(Ar_0, Ar_1, Ar_2)) [ Ar_2 >= Ar_1 + 2 ]

		(Comp: ?, Cost: 1)    evalaxbb3in(Ar_0, Ar_1, Ar_2) -> Com_1(evalaxreturnin(Ar_0, Ar_1, Ar_2)) [ Ar_0 + 2 >= Ar_2 ]

		(Comp: ?, Cost: 1)    evalaxreturnin(Ar_0, Ar_1, Ar_2) -> Com_1(evalaxstop(Ar_0, Ar_1, Ar_2))

		(Comp: 1, Cost: 0)    koat_start(Ar_0, Ar_1, Ar_2) -> Com_1(evalaxstart(Ar_0, Ar_1, Ar_2)) [ 0 <= 0 ]

	start location:	koat_start

	leaf cost:	0



Testing for reachability in the complexity graph removes the following transition from problem 1:

	evalaxbb3in(Ar_0, Ar_1, Ar_2) -> Com_1(evalaxreturnin(Ar_0, Ar_1, Ar_2)) [ Ar_2 >= Ar_1 + 2 ]

We thus obtain the following problem:

2:	T:

		(Comp: ?, Cost: 1)    evalaxreturnin(Ar_0, Ar_1, Ar_2) -> Com_1(evalaxstop(Ar_0, Ar_1, Ar_2))

		(Comp: ?, Cost: 1)    evalaxbb3in(Ar_0, Ar_1, Ar_2) -> Com_1(evalaxreturnin(Ar_0, Ar_1, Ar_2)) [ Ar_0 + 2 >= Ar_2 ]

		(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 ]

		(Comp: ?, Cost: 1)    evalaxbb1in(Ar_0, Ar_1, Ar_2) -> Com_1(evalaxbb2in(Ar_0, Ar_1 + 1, Ar_2))

		(Comp: ?, Cost: 1)    evalaxbb2in(Ar_0, Ar_1, Ar_2) -> Com_1(evalaxbb3in(Ar_0, Ar_1, Ar_2)) [ Ar_1 + 1 >= Ar_2 ]

		(Comp: ?, Cost: 1)    evalaxbb2in(Ar_0, Ar_1, Ar_2) -> Com_1(evalaxbb1in(Ar_0, Ar_1, Ar_2)) [ Ar_2 >= Ar_1 + 2 ]

		(Comp: ?, Cost: 1)    evalaxbbin(Ar_0, Ar_1, Ar_2) -> Com_1(evalaxbb2in(Ar_0, 0, Ar_2))

		(Comp: ?, Cost: 1)    evalaxentryin(Ar_0, Ar_1, Ar_2) -> Com_1(evalaxbbin(0, Ar_1, Ar_2))

		(Comp: ?, Cost: 1)    evalaxstart(Ar_0, Ar_1, Ar_2) -> Com_1(evalaxentryin(Ar_0, Ar_1, Ar_2))

		(Comp: 1, Cost: 0)    koat_start(Ar_0, Ar_1, Ar_2) -> Com_1(evalaxstart(Ar_0, Ar_1, Ar_2)) [ 0 <= 0 ]

	start location:	koat_start

	leaf cost:	0



Repeatedly propagating knowledge in problem 2 produces the following problem:

3:	T:

		(Comp: ?, Cost: 1)    evalaxreturnin(Ar_0, Ar_1, Ar_2) -> Com_1(evalaxstop(Ar_0, Ar_1, Ar_2))

		(Comp: ?, Cost: 1)    evalaxbb3in(Ar_0, Ar_1, Ar_2) -> Com_1(evalaxreturnin(Ar_0, Ar_1, Ar_2)) [ Ar_0 + 2 >= Ar_2 ]

		(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 ]

		(Comp: ?, Cost: 1)    evalaxbb1in(Ar_0, Ar_1, Ar_2) -> Com_1(evalaxbb2in(Ar_0, Ar_1 + 1, Ar_2))

		(Comp: ?, Cost: 1)    evalaxbb2in(Ar_0, Ar_1, Ar_2) -> Com_1(evalaxbb3in(Ar_0, Ar_1, Ar_2)) [ Ar_1 + 1 >= Ar_2 ]

		(Comp: ?, Cost: 1)    evalaxbb2in(Ar_0, Ar_1, Ar_2) -> Com_1(evalaxbb1in(Ar_0, Ar_1, Ar_2)) [ Ar_2 >= Ar_1 + 2 ]

		(Comp: ?, Cost: 1)    evalaxbbin(Ar_0, Ar_1, Ar_2) -> Com_1(evalaxbb2in(Ar_0, 0, Ar_2))

		(Comp: 1, Cost: 1)    evalaxentryin(Ar_0, Ar_1, Ar_2) -> Com_1(evalaxbbin(0, Ar_1, Ar_2))

		(Comp: 1, Cost: 1)    evalaxstart(Ar_0, Ar_1, Ar_2) -> Com_1(evalaxentryin(Ar_0, Ar_1, Ar_2))

		(Comp: 1, Cost: 0)    koat_start(Ar_0, Ar_1, Ar_2) -> Com_1(evalaxstart(Ar_0, Ar_1, Ar_2)) [ 0 <= 0 ]

	start location:	koat_start

	leaf cost:	0



A polynomial rank function with

	Pol(evalaxreturnin) = 1

	Pol(evalaxstop) = 0

	Pol(evalaxbb3in) = 2

	Pol(evalaxbbin) = 2

	Pol(evalaxbb1in) = 2

	Pol(evalaxbb2in) = 2

	Pol(evalaxentryin) = 2

	Pol(evalaxstart) = 2

	Pol(koat_start) = 2

orients all transitions weakly and the transitions

	evalaxreturnin(Ar_0, Ar_1, Ar_2) -> Com_1(evalaxstop(Ar_0, Ar_1, Ar_2))

	evalaxbb3in(Ar_0, Ar_1, Ar_2) -> Com_1(evalaxreturnin(Ar_0, Ar_1, Ar_2)) [ Ar_0 + 2 >= Ar_2 ]

strictly and produces the following problem:

4:	T:

		(Comp: 2, Cost: 1)    evalaxreturnin(Ar_0, Ar_1, Ar_2) -> Com_1(evalaxstop(Ar_0, Ar_1, Ar_2))

		(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 ]

		(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 ]

		(Comp: ?, Cost: 1)    evalaxbb1in(Ar_0, Ar_1, Ar_2) -> Com_1(evalaxbb2in(Ar_0, Ar_1 + 1, Ar_2))

		(Comp: ?, Cost: 1)    evalaxbb2in(Ar_0, Ar_1, Ar_2) -> Com_1(evalaxbb3in(Ar_0, Ar_1, Ar_2)) [ Ar_1 + 1 >= Ar_2 ]

		(Comp: ?, Cost: 1)    evalaxbb2in(Ar_0, Ar_1, Ar_2) -> Com_1(evalaxbb1in(Ar_0, Ar_1, Ar_2)) [ Ar_2 >= Ar_1 + 2 ]

		(Comp: ?, Cost: 1)    evalaxbbin(Ar_0, Ar_1, Ar_2) -> Com_1(evalaxbb2in(Ar_0, 0, Ar_2))

		(Comp: 1, Cost: 1)    evalaxentryin(Ar_0, Ar_1, Ar_2) -> Com_1(evalaxbbin(0, Ar_1, Ar_2))

		(Comp: 1, Cost: 1)    evalaxstart(Ar_0, Ar_1, Ar_2) -> Com_1(evalaxentryin(Ar_0, Ar_1, Ar_2))

		(Comp: 1, Cost: 0)    koat_start(Ar_0, Ar_1, Ar_2) -> Com_1(evalaxstart(Ar_0, Ar_1, Ar_2)) [ 0 <= 0 ]

	start location:	koat_start

	leaf cost:	0



A polynomial rank function with

	Pol(evalaxreturnin) = -V_1 + V_3

	Pol(evalaxstop) = -V_1 + V_3

	Pol(evalaxbb3in) = -V_1 + V_3

	Pol(evalaxbbin) = -V_1 + V_3

	Pol(evalaxbb1in) = -V_1 + V_3

	Pol(evalaxbb2in) = -V_1 + V_3

	Pol(evalaxentryin) = V_3

	Pol(evalaxstart) = V_3

	Pol(koat_start) = V_3

orients all transitions weakly and the transition

	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 ]

strictly and produces the following problem:

5:	T:

		(Comp: 2, Cost: 1)       evalaxreturnin(Ar_0, Ar_1, Ar_2) -> Com_1(evalaxstop(Ar_0, Ar_1, Ar_2))

		(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 ]

		(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 ]

		(Comp: ?, Cost: 1)       evalaxbb1in(Ar_0, Ar_1, Ar_2) -> Com_1(evalaxbb2in(Ar_0, Ar_1 + 1, Ar_2))

		(Comp: ?, Cost: 1)       evalaxbb2in(Ar_0, Ar_1, Ar_2) -> Com_1(evalaxbb3in(Ar_0, Ar_1, Ar_2)) [ Ar_1 + 1 >= Ar_2 ]

		(Comp: ?, Cost: 1)       evalaxbb2in(Ar_0, Ar_1, Ar_2) -> Com_1(evalaxbb1in(Ar_0, Ar_1, Ar_2)) [ Ar_2 >= Ar_1 + 2 ]

		(Comp: ?, Cost: 1)       evalaxbbin(Ar_0, Ar_1, Ar_2) -> Com_1(evalaxbb2in(Ar_0, 0, Ar_2))

		(Comp: 1, Cost: 1)       evalaxentryin(Ar_0, Ar_1, Ar_2) -> Com_1(evalaxbbin(0, Ar_1, Ar_2))

		(Comp: 1, Cost: 1)       evalaxstart(Ar_0, Ar_1, Ar_2) -> Com_1(evalaxentryin(Ar_0, Ar_1, Ar_2))

		(Comp: 1, Cost: 0)       koat_start(Ar_0, Ar_1, Ar_2) -> Com_1(evalaxstart(Ar_0, Ar_1, Ar_2)) [ 0 <= 0 ]

	start location:	koat_start

	leaf cost:	0



Repeatedly propagating knowledge in problem 5 produces the following problem:

6:	T:

		(Comp: 2, Cost: 1)           evalaxreturnin(Ar_0, Ar_1, Ar_2) -> Com_1(evalaxstop(Ar_0, Ar_1, Ar_2))

		(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 ]

		(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 ]

		(Comp: ?, Cost: 1)           evalaxbb1in(Ar_0, Ar_1, Ar_2) -> Com_1(evalaxbb2in(Ar_0, Ar_1 + 1, Ar_2))

		(Comp: ?, Cost: 1)           evalaxbb2in(Ar_0, Ar_1, Ar_2) -> Com_1(evalaxbb3in(Ar_0, Ar_1, Ar_2)) [ Ar_1 + 1 >= Ar_2 ]

		(Comp: ?, Cost: 1)           evalaxbb2in(Ar_0, Ar_1, Ar_2) -> Com_1(evalaxbb1in(Ar_0, Ar_1, Ar_2)) [ Ar_2 >= Ar_1 + 2 ]

		(Comp: Ar_2 + 1, Cost: 1)    evalaxbbin(Ar_0, Ar_1, Ar_2) -> Com_1(evalaxbb2in(Ar_0, 0, Ar_2))

		(Comp: 1, Cost: 1)           evalaxentryin(Ar_0, Ar_1, Ar_2) -> Com_1(evalaxbbin(0, Ar_1, Ar_2))

		(Comp: 1, Cost: 1)           evalaxstart(Ar_0, Ar_1, Ar_2) -> Com_1(evalaxentryin(Ar_0, Ar_1, Ar_2))

		(Comp: 1, Cost: 0)           koat_start(Ar_0, Ar_1, Ar_2) -> Com_1(evalaxstart(Ar_0, Ar_1, Ar_2)) [ 0 <= 0 ]

	start location:	koat_start

	leaf cost:	0



A polynomial rank function with

	Pol(evalaxbb2in) = 1

	Pol(evalaxbb3in) = 0

	Pol(evalaxbb1in) = 1

and size complexities

	S("koat_start(Ar_0, Ar_1, Ar_2) -> Com_1(evalaxstart(Ar_0, Ar_1, Ar_2)) [ 0 <= 0 ]", 0-0) = Ar_0

	S("koat_start(Ar_0, Ar_1, Ar_2) -> Com_1(evalaxstart(Ar_0, Ar_1, Ar_2)) [ 0 <= 0 ]", 0-1) = Ar_1

	S("koat_start(Ar_0, Ar_1, Ar_2) -> Com_1(evalaxstart(Ar_0, Ar_1, Ar_2)) [ 0 <= 0 ]", 0-2) = Ar_2

	S("evalaxstart(Ar_0, Ar_1, Ar_2) -> Com_1(evalaxentryin(Ar_0, Ar_1, Ar_2))", 0-0) = Ar_0

	S("evalaxstart(Ar_0, Ar_1, Ar_2) -> Com_1(evalaxentryin(Ar_0, Ar_1, Ar_2))", 0-1) = Ar_1

	S("evalaxstart(Ar_0, Ar_1, Ar_2) -> Com_1(evalaxentryin(Ar_0, Ar_1, Ar_2))", 0-2) = Ar_2

	S("evalaxentryin(Ar_0, Ar_1, Ar_2) -> Com_1(evalaxbbin(0, Ar_1, Ar_2))", 0-0) = 0

	S("evalaxentryin(Ar_0, Ar_1, Ar_2) -> Com_1(evalaxbbin(0, Ar_1, Ar_2))", 0-1) = Ar_1

	S("evalaxentryin(Ar_0, Ar_1, Ar_2) -> Com_1(evalaxbbin(0, Ar_1, Ar_2))", 0-2) = Ar_2

	S("evalaxbbin(Ar_0, Ar_1, Ar_2) -> Com_1(evalaxbb2in(Ar_0, 0, Ar_2))", 0-0) = Ar_2

	S("evalaxbbin(Ar_0, Ar_1, Ar_2) -> Com_1(evalaxbb2in(Ar_0, 0, Ar_2))", 0-1) = 0

	S("evalaxbbin(Ar_0, Ar_1, Ar_2) -> Com_1(evalaxbb2in(Ar_0, 0, Ar_2))", 0-2) = Ar_2

	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

	S("evalaxbb2in(Ar_0, Ar_1, Ar_2) -> Com_1(evalaxbb1in(Ar_0, Ar_1, Ar_2)) [ Ar_2 >= Ar_1 + 2 ]", 0-1) = ?

	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

	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

	S("evalaxbb2in(Ar_0, Ar_1, Ar_2) -> Com_1(evalaxbb3in(Ar_0, Ar_1, Ar_2)) [ Ar_1 + 1 >= Ar_2 ]", 0-1) = ?

	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

	S("evalaxbb1in(Ar_0, Ar_1, Ar_2) -> Com_1(evalaxbb2in(Ar_0, Ar_1 + 1, Ar_2))", 0-0) = Ar_2

	S("evalaxbb1in(Ar_0, Ar_1, Ar_2) -> Com_1(evalaxbb2in(Ar_0, Ar_1 + 1, Ar_2))", 0-1) = ?

	S("evalaxbb1in(Ar_0, Ar_1, Ar_2) -> Com_1(evalaxbb2in(Ar_0, Ar_1 + 1, Ar_2))", 0-2) = Ar_2

	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

	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) = ?

	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

	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

	S("evalaxbb3in(Ar_0, Ar_1, Ar_2) -> Com_1(evalaxreturnin(Ar_0, Ar_1, Ar_2)) [ Ar_0 + 2 >= Ar_2 ]", 0-1) = ?

	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

	S("evalaxreturnin(Ar_0, Ar_1, Ar_2) -> Com_1(evalaxstop(Ar_0, Ar_1, Ar_2))", 0-0) = Ar_2

	S("evalaxreturnin(Ar_0, Ar_1, Ar_2) -> Com_1(evalaxstop(Ar_0, Ar_1, Ar_2))", 0-1) = ?

	S("evalaxreturnin(Ar_0, Ar_1, Ar_2) -> Com_1(evalaxstop(Ar_0, Ar_1, Ar_2))", 0-2) = Ar_2

orients the transitions

	evalaxbb2in(Ar_0, Ar_1, Ar_2) -> Com_1(evalaxbb3in(Ar_0, Ar_1, Ar_2)) [ Ar_1 + 1 >= Ar_2 ]

	evalaxbb2in(Ar_0, Ar_1, Ar_2) -> Com_1(evalaxbb1in(Ar_0, Ar_1, Ar_2)) [ Ar_2 >= Ar_1 + 2 ]

	evalaxbb1in(Ar_0, Ar_1, Ar_2) -> Com_1(evalaxbb2in(Ar_0, Ar_1 + 1, Ar_2))

weakly and the transition

	evalaxbb2in(Ar_0, Ar_1, Ar_2) -> Com_1(evalaxbb3in(Ar_0, Ar_1, Ar_2)) [ Ar_1 + 1 >= Ar_2 ]

strictly and produces the following problem:

7:	T:

		(Comp: 2, Cost: 1)           evalaxreturnin(Ar_0, Ar_1, Ar_2) -> Com_1(evalaxstop(Ar_0, Ar_1, Ar_2))

		(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 ]

		(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 ]

		(Comp: ?, Cost: 1)           evalaxbb1in(Ar_0, Ar_1, Ar_2) -> Com_1(evalaxbb2in(Ar_0, Ar_1 + 1, Ar_2))

		(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 ]

		(Comp: ?, Cost: 1)           evalaxbb2in(Ar_0, Ar_1, Ar_2) -> Com_1(evalaxbb1in(Ar_0, Ar_1, Ar_2)) [ Ar_2 >= Ar_1 + 2 ]

		(Comp: Ar_2 + 1, Cost: 1)    evalaxbbin(Ar_0, Ar_1, Ar_2) -> Com_1(evalaxbb2in(Ar_0, 0, Ar_2))

		(Comp: 1, Cost: 1)           evalaxentryin(Ar_0, Ar_1, Ar_2) -> Com_1(evalaxbbin(0, Ar_1, Ar_2))

		(Comp: 1, Cost: 1)           evalaxstart(Ar_0, Ar_1, Ar_2) -> Com_1(evalaxentryin(Ar_0, Ar_1, Ar_2))

		(Comp: 1, Cost: 0)           koat_start(Ar_0, Ar_1, Ar_2) -> Com_1(evalaxstart(Ar_0, Ar_1, Ar_2)) [ 0 <= 0 ]

	start location:	koat_start

	leaf cost:	0



A polynomial rank function with

	Pol(evalaxbb2in) = -V_2 + V_3

	Pol(evalaxbb1in) = -V_2 + V_3 - 1

and size complexities

	S("koat_start(Ar_0, Ar_1, Ar_2) -> Com_1(evalaxstart(Ar_0, Ar_1, Ar_2)) [ 0 <= 0 ]", 0-0) = Ar_0

	S("koat_start(Ar_0, Ar_1, Ar_2) -> Com_1(evalaxstart(Ar_0, Ar_1, Ar_2)) [ 0 <= 0 ]", 0-1) = Ar_1

	S("koat_start(Ar_0, Ar_1, Ar_2) -> Com_1(evalaxstart(Ar_0, Ar_1, Ar_2)) [ 0 <= 0 ]", 0-2) = Ar_2

	S("evalaxstart(Ar_0, Ar_1, Ar_2) -> Com_1(evalaxentryin(Ar_0, Ar_1, Ar_2))", 0-0) = Ar_0

	S("evalaxstart(Ar_0, Ar_1, Ar_2) -> Com_1(evalaxentryin(Ar_0, Ar_1, Ar_2))", 0-1) = Ar_1

	S("evalaxstart(Ar_0, Ar_1, Ar_2) -> Com_1(evalaxentryin(Ar_0, Ar_1, Ar_2))", 0-2) = Ar_2

	S("evalaxentryin(Ar_0, Ar_1, Ar_2) -> Com_1(evalaxbbin(0, Ar_1, Ar_2))", 0-0) = 0

	S("evalaxentryin(Ar_0, Ar_1, Ar_2) -> Com_1(evalaxbbin(0, Ar_1, Ar_2))", 0-1) = Ar_1

	S("evalaxentryin(Ar_0, Ar_1, Ar_2) -> Com_1(evalaxbbin(0, Ar_1, Ar_2))", 0-2) = Ar_2

	S("evalaxbbin(Ar_0, Ar_1, Ar_2) -> Com_1(evalaxbb2in(Ar_0, 0, Ar_2))", 0-0) = Ar_2

	S("evalaxbbin(Ar_0, Ar_1, Ar_2) -> Com_1(evalaxbb2in(Ar_0, 0, Ar_2))", 0-1) = 0

	S("evalaxbbin(Ar_0, Ar_1, Ar_2) -> Com_1(evalaxbb2in(Ar_0, 0, Ar_2))", 0-2) = Ar_2

	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

	S("evalaxbb2in(Ar_0, Ar_1, Ar_2) -> Com_1(evalaxbb1in(Ar_0, Ar_1, Ar_2)) [ Ar_2 >= Ar_1 + 2 ]", 0-1) = ?

	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

	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

	S("evalaxbb2in(Ar_0, Ar_1, Ar_2) -> Com_1(evalaxbb3in(Ar_0, Ar_1, Ar_2)) [ Ar_1 + 1 >= Ar_2 ]", 0-1) = ?

	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

	S("evalaxbb1in(Ar_0, Ar_1, Ar_2) -> Com_1(evalaxbb2in(Ar_0, Ar_1 + 1, Ar_2))", 0-0) = Ar_2

	S("evalaxbb1in(Ar_0, Ar_1, Ar_2) -> Com_1(evalaxbb2in(Ar_0, Ar_1 + 1, Ar_2))", 0-1) = ?

	S("evalaxbb1in(Ar_0, Ar_1, Ar_2) -> Com_1(evalaxbb2in(Ar_0, Ar_1 + 1, Ar_2))", 0-2) = Ar_2

	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

	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) = ?

	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

	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

	S("evalaxbb3in(Ar_0, Ar_1, Ar_2) -> Com_1(evalaxreturnin(Ar_0, Ar_1, Ar_2)) [ Ar_0 + 2 >= Ar_2 ]", 0-1) = ?

	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

	S("evalaxreturnin(Ar_0, Ar_1, Ar_2) -> Com_1(evalaxstop(Ar_0, Ar_1, Ar_2))", 0-0) = Ar_2

	S("evalaxreturnin(Ar_0, Ar_1, Ar_2) -> Com_1(evalaxstop(Ar_0, Ar_1, Ar_2))", 0-1) = ?

	S("evalaxreturnin(Ar_0, Ar_1, Ar_2) -> Com_1(evalaxstop(Ar_0, Ar_1, Ar_2))", 0-2) = Ar_2

orients the transitions

	evalaxbb2in(Ar_0, Ar_1, Ar_2) -> Com_1(evalaxbb1in(Ar_0, Ar_1, Ar_2)) [ Ar_2 >= Ar_1 + 2 ]

	evalaxbb1in(Ar_0, Ar_1, Ar_2) -> Com_1(evalaxbb2in(Ar_0, Ar_1 + 1, Ar_2))

weakly and the transition

	evalaxbb2in(Ar_0, Ar_1, Ar_2) -> Com_1(evalaxbb1in(Ar_0, Ar_1, Ar_2)) [ Ar_2 >= Ar_1 + 2 ]

strictly and produces the following problem:

8:	T:

		(Comp: 2, Cost: 1)                evalaxreturnin(Ar_0, Ar_1, Ar_2) -> Com_1(evalaxstop(Ar_0, Ar_1, Ar_2))

		(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 ]

		(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 ]

		(Comp: ?, Cost: 1)                evalaxbb1in(Ar_0, Ar_1, Ar_2) -> Com_1(evalaxbb2in(Ar_0, Ar_1 + 1, Ar_2))

		(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 ]

		(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 ]

		(Comp: Ar_2 + 1, Cost: 1)         evalaxbbin(Ar_0, Ar_1, Ar_2) -> Com_1(evalaxbb2in(Ar_0, 0, Ar_2))

		(Comp: 1, Cost: 1)                evalaxentryin(Ar_0, Ar_1, Ar_2) -> Com_1(evalaxbbin(0, Ar_1, Ar_2))

		(Comp: 1, Cost: 1)                evalaxstart(Ar_0, Ar_1, Ar_2) -> Com_1(evalaxentryin(Ar_0, Ar_1, Ar_2))

		(Comp: 1, Cost: 0)                koat_start(Ar_0, Ar_1, Ar_2) -> Com_1(evalaxstart(Ar_0, Ar_1, Ar_2)) [ 0 <= 0 ]

	start location:	koat_start

	leaf cost:	0



Repeatedly propagating knowledge in problem 8 produces the following problem:

9:	T:

		(Comp: 2, Cost: 1)                evalaxreturnin(Ar_0, Ar_1, Ar_2) -> Com_1(evalaxstop(Ar_0, Ar_1, Ar_2))

		(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 ]

		(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 ]

		(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))

		(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 ]

		(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 ]

		(Comp: Ar_2 + 1, Cost: 1)         evalaxbbin(Ar_0, Ar_1, Ar_2) -> Com_1(evalaxbb2in(Ar_0, 0, Ar_2))

		(Comp: 1, Cost: 1)                evalaxentryin(Ar_0, Ar_1, Ar_2) -> Com_1(evalaxbbin(0, Ar_1, Ar_2))

		(Comp: 1, Cost: 1)                evalaxstart(Ar_0, Ar_1, Ar_2) -> Com_1(evalaxentryin(Ar_0, Ar_1, Ar_2))

		(Comp: 1, Cost: 0)                koat_start(Ar_0, Ar_1, Ar_2) -> Com_1(evalaxstart(Ar_0, Ar_1, Ar_2)) [ 0 <= 0 ]

	start location:	koat_start

	leaf cost:	0



Complexity upper bound 5*Ar_2 + 2*Ar_2^2 + 8



Time: 0.087 sec (SMT: 0.068 sec)


----------------------------------------

(2)
BOUNDS(1, n^2)

----------------------------------------

(3) Loat Proof (FINISHED)


### Pre-processing the ITS problem ###



Initial linear ITS problem

   Start location: evalaxstart

      0: evalaxstart -> evalaxentryin : [], cost: 1

      1: evalaxentryin -> evalaxbbin : A'=0, [], cost: 1

      2: evalaxbbin -> evalaxbb2in : B'=0, [], cost: 1

      3: evalaxbb2in -> evalaxbb1in : [ C>=2+B ], cost: 1

      4: evalaxbb2in -> evalaxbb3in : [ 1+B>=C ], cost: 1

      5: evalaxbb1in -> evalaxbb2in : B'=1+B, [], cost: 1

      6: evalaxbb3in -> evalaxbbin : A'=1+A, [ 1+B>=C && C>=3+A ], cost: 1

      7: evalaxbb3in -> evalaxreturnin : [ C>=2+B ], cost: 1

      8: evalaxbb3in -> evalaxreturnin : [ 2+A>=C ], cost: 1

      9: evalaxreturnin -> evalaxstop : [], cost: 1



Checking for constant complexity:

   The following rule is satisfiable with cost >= 1, yielding constant complexity:

      0: evalaxstart -> evalaxentryin : [], cost: 1



Removed unreachable and leaf rules:

   Start location: evalaxstart

      0: evalaxstart -> evalaxentryin : [], cost: 1

      1: evalaxentryin -> evalaxbbin : A'=0, [], cost: 1

      2: evalaxbbin -> evalaxbb2in : B'=0, [], cost: 1

      3: evalaxbb2in -> evalaxbb1in : [ C>=2+B ], cost: 1

      4: evalaxbb2in -> evalaxbb3in : [ 1+B>=C ], cost: 1

      5: evalaxbb1in -> evalaxbb2in : B'=1+B, [], cost: 1

      6: evalaxbb3in -> evalaxbbin : A'=1+A, [ 1+B>=C && C>=3+A ], cost: 1



### Simplification by acceleration and chaining ###



Eliminated locations (on linear paths):

   Start location: evalaxstart

     10: evalaxstart -> evalaxbbin : A'=0, [], cost: 2

      2: evalaxbbin -> evalaxbb2in : B'=0, [], cost: 1

     11: evalaxbb2in -> evalaxbb2in : B'=1+B, [ C>=2+B ], cost: 2

     12: evalaxbb2in -> evalaxbbin : A'=1+A, [ 1+B>=C && C>=3+A ], cost: 2



Accelerating simple loops of location 3.

   Accelerating the following rules:

     11: evalaxbb2in -> evalaxbb2in : B'=1+B, [ C>=2+B ], cost: 2



   Accelerated rule 11 with metering function -1+C-B, yielding the new rule 13.

   Removing the simple loops: 11.



Accelerated all simple loops using metering functions (where possible):

   Start location: evalaxstart

     10: evalaxstart -> evalaxbbin : A'=0, [], cost: 2

      2: evalaxbbin -> evalaxbb2in : B'=0, [], cost: 1

     12: evalaxbb2in -> evalaxbbin : A'=1+A, [ 1+B>=C && C>=3+A ], cost: 2

     13: evalaxbb2in -> evalaxbb2in : B'=-1+C, [ C>=2+B ], cost: -2+2*C-2*B



Chained accelerated rules (with incoming rules):

   Start location: evalaxstart

     10: evalaxstart -> evalaxbbin : A'=0, [], cost: 2

      2: evalaxbbin -> evalaxbb2in : B'=0, [], cost: 1

     14: evalaxbbin -> evalaxbb2in : B'=-1+C, [ C>=2 ], cost: -1+2*C

     12: evalaxbb2in -> evalaxbbin : A'=1+A, [ 1+B>=C && C>=3+A ], cost: 2



Eliminated locations (on tree-shaped paths):

   Start location: evalaxstart

     10: evalaxstart -> evalaxbbin : A'=0, [], cost: 2

     15: evalaxbbin -> evalaxbbin : A'=1+A, B'=0, [ 1>=C && C>=3+A ], cost: 3

     16: evalaxbbin -> evalaxbbin : A'=1+A, B'=-1+C, [ C>=2 && C>=3+A ], cost: 1+2*C



Accelerating simple loops of location 2.

   Accelerating the following rules:

     15: evalaxbbin -> evalaxbbin : A'=1+A, B'=0, [ 1>=C && C>=3+A ], cost: 3

     16: evalaxbbin -> evalaxbbin : A'=1+A, B'=-1+C, [ C>=2 && C>=3+A ], cost: 1+2*C



   Accelerated rule 15 with metering function -2+C-A, yielding the new rule 17.

   Accelerated rule 16 with metering function -2+C-A, yielding the new rule 18.

   Removing the simple loops: 15 16.



Accelerated all simple loops using metering functions (where possible):

   Start location: evalaxstart

     10: evalaxstart -> evalaxbbin : A'=0, [], cost: 2

     17: evalaxbbin -> evalaxbbin : A'=-2+C, B'=0, [ 1>=C && C>=3+A ], cost: -6+3*C-3*A

     18: evalaxbbin -> evalaxbbin : A'=-2+C, B'=-1+C, [ C>=2 && C>=3+A ], cost: -2+C-A+2*C*(-2+C-A)



Chained accelerated rules (with incoming rules):

   Start location: evalaxstart

     10: evalaxstart -> evalaxbbin : A'=0, [], cost: 2

     19: evalaxstart -> evalaxbbin : A'=-2+C, B'=-1+C, [ C>=3 ], cost: C+2*(-2+C)*C



Removed unreachable locations (and leaf rules with constant cost):

   Start location: evalaxstart

     19: evalaxstart -> evalaxbbin : A'=-2+C, B'=-1+C, [ C>=3 ], cost: C+2*(-2+C)*C



### Computing asymptotic complexity ###



Fully simplified ITS problem

   Start location: evalaxstart

     19: evalaxstart -> evalaxbbin : A'=-2+C, B'=-1+C, [ C>=3 ], cost: C+2*(-2+C)*C



Computing asymptotic complexity for rule 19

   Solved the limit problem by the following transformations:

      Created initial limit problem:

      -2+C (+/+!), -3*C+2*C^2 (+) [not solved]



      removing all constraints (solved by SMT)

      resulting limit problem: [solved]



      applying transformation rule (C) using substitution {C==n}

      resulting limit problem:

      [solved]



   Solution:

      C / n

   Resulting cost -3*n+2*n^2 has complexity: Poly(n^2)



Found new complexity Poly(n^2).



Obtained the following overall complexity (w.r.t. the length of the input n):

   Complexity:  Poly(n^2)

   Cpx degree:  2

   Solved cost: -3*n+2*n^2

   Rule cost:   C+2*(-2+C)*C

   Rule guard:  [ C>=3 ]



WORST_CASE(Omega(n^2),?)


----------------------------------------

(4)
BOUNDS(n^2, INF)