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


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


WORST_CASE(Omega(n^1), 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^1, n^2).

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


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

(0)
Obligation:
Complexity Int TRS consisting of the following rules:
evalEx7start(A, B, C) -> Com_1(evalEx7entryin(A, B, C)) :|: TRUE
evalEx7entryin(A, B, C) -> Com_1(evalEx7bb3in(A, B, A + 1)) :|: A >= 1 && B >= A + 1
evalEx7bb3in(A, B, C) -> Com_1(evalEx7bbin(A, B, C)) :|: A >= C + 1
evalEx7bb3in(A, B, C) -> Com_1(evalEx7bbin(A, B, C)) :|: C >= A + 1
evalEx7bb3in(A, B, C) -> Com_1(evalEx7returnin(A, B, C)) :|: C >= A && C <= A
evalEx7bbin(A, B, C) -> Com_1(evalEx7bb3in(A, B, 0)) :|: C >= B + 1
evalEx7bbin(A, B, C) -> Com_1(evalEx7bb3in(A, B, C + 1)) :|: B >= C
evalEx7returnin(A, B, C) -> Com_1(evalEx7stop(A, B, C)) :|: TRUE

The start-symbols are:[evalEx7start_3]


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

(1) Koat Proof (FINISHED)
YES(?, 20*Ar_1^2 + 62*Ar_1 + 35)



Initial complexity problem:

1:	T:

		(Comp: ?, Cost: 1)    evalEx7start(Ar_0, Ar_1, Ar_2) -> Com_1(evalEx7entryin(Ar_0, Ar_1, Ar_2))

		(Comp: ?, Cost: 1)    evalEx7entryin(Ar_0, Ar_1, Ar_2) -> Com_1(evalEx7bb3in(Ar_0, Ar_1, Ar_0 + 1)) [ Ar_0 >= 1 /\ Ar_1 >= Ar_0 + 1 ]

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

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

		(Comp: ?, Cost: 1)    evalEx7bb3in(Ar_0, Ar_1, Ar_2) -> Com_1(evalEx7returnin(Ar_0, Ar_1, Ar_2)) [ Ar_2 = Ar_0 ]

		(Comp: ?, Cost: 1)    evalEx7bbin(Ar_0, Ar_1, Ar_2) -> Com_1(evalEx7bb3in(Ar_0, Ar_1, 0)) [ Ar_2 >= Ar_1 + 1 ]

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

		(Comp: ?, Cost: 1)    evalEx7returnin(Ar_0, Ar_1, Ar_2) -> Com_1(evalEx7stop(Ar_0, Ar_1, Ar_2))

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

	start location:	koat_start

	leaf cost:	0



Repeatedly propagating knowledge in problem 1 produces the following problem:

2:	T:

		(Comp: 1, Cost: 1)    evalEx7start(Ar_0, Ar_1, Ar_2) -> Com_1(evalEx7entryin(Ar_0, Ar_1, Ar_2))

		(Comp: 1, Cost: 1)    evalEx7entryin(Ar_0, Ar_1, Ar_2) -> Com_1(evalEx7bb3in(Ar_0, Ar_1, Ar_0 + 1)) [ Ar_0 >= 1 /\ Ar_1 >= Ar_0 + 1 ]

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

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

		(Comp: ?, Cost: 1)    evalEx7bb3in(Ar_0, Ar_1, Ar_2) -> Com_1(evalEx7returnin(Ar_0, Ar_1, Ar_2)) [ Ar_2 = Ar_0 ]

		(Comp: ?, Cost: 1)    evalEx7bbin(Ar_0, Ar_1, Ar_2) -> Com_1(evalEx7bb3in(Ar_0, Ar_1, 0)) [ Ar_2 >= Ar_1 + 1 ]

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

		(Comp: ?, Cost: 1)    evalEx7returnin(Ar_0, Ar_1, Ar_2) -> Com_1(evalEx7stop(Ar_0, Ar_1, Ar_2))

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

	start location:	koat_start

	leaf cost:	0



A polynomial rank function with

	Pol(evalEx7start) = 2

	Pol(evalEx7entryin) = 2

	Pol(evalEx7bb3in) = 2

	Pol(evalEx7bbin) = 2

	Pol(evalEx7returnin) = 1

	Pol(evalEx7stop) = 0

	Pol(koat_start) = 2

orients all transitions weakly and the transitions

	evalEx7returnin(Ar_0, Ar_1, Ar_2) -> Com_1(evalEx7stop(Ar_0, Ar_1, Ar_2))

	evalEx7bb3in(Ar_0, Ar_1, Ar_2) -> Com_1(evalEx7returnin(Ar_0, Ar_1, Ar_2)) [ Ar_2 = Ar_0 ]

strictly and produces the following problem:

3:	T:

		(Comp: 1, Cost: 1)    evalEx7start(Ar_0, Ar_1, Ar_2) -> Com_1(evalEx7entryin(Ar_0, Ar_1, Ar_2))

		(Comp: 1, Cost: 1)    evalEx7entryin(Ar_0, Ar_1, Ar_2) -> Com_1(evalEx7bb3in(Ar_0, Ar_1, Ar_0 + 1)) [ Ar_0 >= 1 /\ Ar_1 >= Ar_0 + 1 ]

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

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

		(Comp: 2, Cost: 1)    evalEx7bb3in(Ar_0, Ar_1, Ar_2) -> Com_1(evalEx7returnin(Ar_0, Ar_1, Ar_2)) [ Ar_2 = Ar_0 ]

		(Comp: ?, Cost: 1)    evalEx7bbin(Ar_0, Ar_1, Ar_2) -> Com_1(evalEx7bb3in(Ar_0, Ar_1, 0)) [ Ar_2 >= Ar_1 + 1 ]

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

		(Comp: 2, Cost: 1)    evalEx7returnin(Ar_0, Ar_1, Ar_2) -> Com_1(evalEx7stop(Ar_0, Ar_1, Ar_2))

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

	start location:	koat_start

	leaf cost:	0



Applied AI with 'oct' on problem 3 to obtain the following invariants:

  For symbol evalEx7bb3in: X_2 - 2 >= 0 /\ X_1 + X_2 - 3 >= 0 /\ -X_1 + X_2 - 1 >= 0 /\ X_1 - 1 >= 0

  For symbol evalEx7bbin: X_2 - 2 >= 0 /\ X_1 + X_2 - 3 >= 0 /\ -X_1 + X_2 - 1 >= 0 /\ X_1 - 1 >= 0

  For symbol evalEx7returnin: X_2 - X_3 - 1 >= 0 /\ X_1 - X_3 >= 0 /\ X_3 - 1 >= 0 /\ X_2 + X_3 - 3 >= 0 /\ X_1 + X_3 - 2 >= 0 /\ -X_1 + X_3 >= 0 /\ X_2 - 2 >= 0 /\ X_1 + X_2 - 3 >= 0 /\ -X_1 + X_2 - 1 >= 0 /\ X_1 - 1 >= 0





This yielded the following problem:

4:	T:

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

		(Comp: 2, Cost: 1)    evalEx7returnin(Ar_0, Ar_1, Ar_2) -> Com_1(evalEx7stop(Ar_0, Ar_1, Ar_2)) [ Ar_1 - Ar_2 - 1 >= 0 /\ Ar_0 - Ar_2 >= 0 /\ Ar_2 - 1 >= 0 /\ Ar_1 + Ar_2 - 3 >= 0 /\ Ar_0 + Ar_2 - 2 >= 0 /\ -Ar_0 + Ar_2 >= 0 /\ Ar_1 - 2 >= 0 /\ Ar_0 + Ar_1 - 3 >= 0 /\ -Ar_0 + Ar_1 - 1 >= 0 /\ Ar_0 - 1 >= 0 ]

		(Comp: ?, Cost: 1)    evalEx7bbin(Ar_0, Ar_1, Ar_2) -> Com_1(evalEx7bb3in(Ar_0, Ar_1, Ar_2 + 1)) [ Ar_1 - 2 >= 0 /\ Ar_0 + Ar_1 - 3 >= 0 /\ -Ar_0 + Ar_1 - 1 >= 0 /\ Ar_0 - 1 >= 0 /\ Ar_1 >= Ar_2 ]

		(Comp: ?, Cost: 1)    evalEx7bbin(Ar_0, Ar_1, Ar_2) -> Com_1(evalEx7bb3in(Ar_0, Ar_1, 0)) [ Ar_1 - 2 >= 0 /\ Ar_0 + Ar_1 - 3 >= 0 /\ -Ar_0 + Ar_1 - 1 >= 0 /\ Ar_0 - 1 >= 0 /\ Ar_2 >= Ar_1 + 1 ]

		(Comp: 2, Cost: 1)    evalEx7bb3in(Ar_0, Ar_1, Ar_2) -> Com_1(evalEx7returnin(Ar_0, Ar_1, Ar_2)) [ Ar_1 - 2 >= 0 /\ Ar_0 + Ar_1 - 3 >= 0 /\ -Ar_0 + Ar_1 - 1 >= 0 /\ Ar_0 - 1 >= 0 /\ Ar_2 = Ar_0 ]

		(Comp: ?, Cost: 1)    evalEx7bb3in(Ar_0, Ar_1, Ar_2) -> Com_1(evalEx7bbin(Ar_0, Ar_1, Ar_2)) [ Ar_1 - 2 >= 0 /\ Ar_0 + Ar_1 - 3 >= 0 /\ -Ar_0 + Ar_1 - 1 >= 0 /\ Ar_0 - 1 >= 0 /\ Ar_2 >= Ar_0 + 1 ]

		(Comp: ?, Cost: 1)    evalEx7bb3in(Ar_0, Ar_1, Ar_2) -> Com_1(evalEx7bbin(Ar_0, Ar_1, Ar_2)) [ Ar_1 - 2 >= 0 /\ Ar_0 + Ar_1 - 3 >= 0 /\ -Ar_0 + Ar_1 - 1 >= 0 /\ Ar_0 - 1 >= 0 /\ Ar_0 >= Ar_2 + 1 ]

		(Comp: 1, Cost: 1)    evalEx7entryin(Ar_0, Ar_1, Ar_2) -> Com_1(evalEx7bb3in(Ar_0, Ar_1, Ar_0 + 1)) [ Ar_0 >= 1 /\ Ar_1 >= Ar_0 + 1 ]

		(Comp: 1, Cost: 1)    evalEx7start(Ar_0, Ar_1, Ar_2) -> Com_1(evalEx7entryin(Ar_0, Ar_1, Ar_2))

	start location:	koat_start

	leaf cost:	0



By chaining the transition koat_start(Ar_0, Ar_1, Ar_2) -> Com_1(evalEx7start(Ar_0, Ar_1, Ar_2)) [ 0 <= 0 ] with all transitions in problem 4, the following new transition is obtained:

	koat_start(Ar_0, Ar_1, Ar_2) -> Com_1(evalEx7entryin(Ar_0, Ar_1, Ar_2)) [ 0 <= 0 ]

We thus obtain the following problem:

5:	T:

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

		(Comp: 2, Cost: 1)    evalEx7returnin(Ar_0, Ar_1, Ar_2) -> Com_1(evalEx7stop(Ar_0, Ar_1, Ar_2)) [ Ar_1 - Ar_2 - 1 >= 0 /\ Ar_0 - Ar_2 >= 0 /\ Ar_2 - 1 >= 0 /\ Ar_1 + Ar_2 - 3 >= 0 /\ Ar_0 + Ar_2 - 2 >= 0 /\ -Ar_0 + Ar_2 >= 0 /\ Ar_1 - 2 >= 0 /\ Ar_0 + Ar_1 - 3 >= 0 /\ -Ar_0 + Ar_1 - 1 >= 0 /\ Ar_0 - 1 >= 0 ]

		(Comp: ?, Cost: 1)    evalEx7bbin(Ar_0, Ar_1, Ar_2) -> Com_1(evalEx7bb3in(Ar_0, Ar_1, Ar_2 + 1)) [ Ar_1 - 2 >= 0 /\ Ar_0 + Ar_1 - 3 >= 0 /\ -Ar_0 + Ar_1 - 1 >= 0 /\ Ar_0 - 1 >= 0 /\ Ar_1 >= Ar_2 ]

		(Comp: ?, Cost: 1)    evalEx7bbin(Ar_0, Ar_1, Ar_2) -> Com_1(evalEx7bb3in(Ar_0, Ar_1, 0)) [ Ar_1 - 2 >= 0 /\ Ar_0 + Ar_1 - 3 >= 0 /\ -Ar_0 + Ar_1 - 1 >= 0 /\ Ar_0 - 1 >= 0 /\ Ar_2 >= Ar_1 + 1 ]

		(Comp: 2, Cost: 1)    evalEx7bb3in(Ar_0, Ar_1, Ar_2) -> Com_1(evalEx7returnin(Ar_0, Ar_1, Ar_2)) [ Ar_1 - 2 >= 0 /\ Ar_0 + Ar_1 - 3 >= 0 /\ -Ar_0 + Ar_1 - 1 >= 0 /\ Ar_0 - 1 >= 0 /\ Ar_2 = Ar_0 ]

		(Comp: ?, Cost: 1)    evalEx7bb3in(Ar_0, Ar_1, Ar_2) -> Com_1(evalEx7bbin(Ar_0, Ar_1, Ar_2)) [ Ar_1 - 2 >= 0 /\ Ar_0 + Ar_1 - 3 >= 0 /\ -Ar_0 + Ar_1 - 1 >= 0 /\ Ar_0 - 1 >= 0 /\ Ar_2 >= Ar_0 + 1 ]

		(Comp: ?, Cost: 1)    evalEx7bb3in(Ar_0, Ar_1, Ar_2) -> Com_1(evalEx7bbin(Ar_0, Ar_1, Ar_2)) [ Ar_1 - 2 >= 0 /\ Ar_0 + Ar_1 - 3 >= 0 /\ -Ar_0 + Ar_1 - 1 >= 0 /\ Ar_0 - 1 >= 0 /\ Ar_0 >= Ar_2 + 1 ]

		(Comp: 1, Cost: 1)    evalEx7entryin(Ar_0, Ar_1, Ar_2) -> Com_1(evalEx7bb3in(Ar_0, Ar_1, Ar_0 + 1)) [ Ar_0 >= 1 /\ Ar_1 >= Ar_0 + 1 ]

		(Comp: 1, Cost: 1)    evalEx7start(Ar_0, Ar_1, Ar_2) -> Com_1(evalEx7entryin(Ar_0, Ar_1, Ar_2))

	start location:	koat_start

	leaf cost:	0



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

	evalEx7start(Ar_0, Ar_1, Ar_2) -> Com_1(evalEx7entryin(Ar_0, Ar_1, Ar_2))

We thus obtain the following problem:

6:	T:

		(Comp: 2, Cost: 1)    evalEx7returnin(Ar_0, Ar_1, Ar_2) -> Com_1(evalEx7stop(Ar_0, Ar_1, Ar_2)) [ Ar_1 - Ar_2 - 1 >= 0 /\ Ar_0 - Ar_2 >= 0 /\ Ar_2 - 1 >= 0 /\ Ar_1 + Ar_2 - 3 >= 0 /\ Ar_0 + Ar_2 - 2 >= 0 /\ -Ar_0 + Ar_2 >= 0 /\ Ar_1 - 2 >= 0 /\ Ar_0 + Ar_1 - 3 >= 0 /\ -Ar_0 + Ar_1 - 1 >= 0 /\ Ar_0 - 1 >= 0 ]

		(Comp: ?, Cost: 1)    evalEx7bb3in(Ar_0, Ar_1, Ar_2) -> Com_1(evalEx7bbin(Ar_0, Ar_1, Ar_2)) [ Ar_1 - 2 >= 0 /\ Ar_0 + Ar_1 - 3 >= 0 /\ -Ar_0 + Ar_1 - 1 >= 0 /\ Ar_0 - 1 >= 0 /\ Ar_0 >= Ar_2 + 1 ]

		(Comp: 2, Cost: 1)    evalEx7bb3in(Ar_0, Ar_1, Ar_2) -> Com_1(evalEx7returnin(Ar_0, Ar_1, Ar_2)) [ Ar_1 - 2 >= 0 /\ Ar_0 + Ar_1 - 3 >= 0 /\ -Ar_0 + Ar_1 - 1 >= 0 /\ Ar_0 - 1 >= 0 /\ Ar_2 = Ar_0 ]

		(Comp: ?, Cost: 1)    evalEx7bbin(Ar_0, Ar_1, Ar_2) -> Com_1(evalEx7bb3in(Ar_0, Ar_1, 0)) [ Ar_1 - 2 >= 0 /\ Ar_0 + Ar_1 - 3 >= 0 /\ -Ar_0 + Ar_1 - 1 >= 0 /\ Ar_0 - 1 >= 0 /\ Ar_2 >= Ar_1 + 1 ]

		(Comp: ?, Cost: 1)    evalEx7bbin(Ar_0, Ar_1, Ar_2) -> Com_1(evalEx7bb3in(Ar_0, Ar_1, Ar_2 + 1)) [ Ar_1 - 2 >= 0 /\ Ar_0 + Ar_1 - 3 >= 0 /\ -Ar_0 + Ar_1 - 1 >= 0 /\ Ar_0 - 1 >= 0 /\ Ar_1 >= Ar_2 ]

		(Comp: ?, Cost: 1)    evalEx7bb3in(Ar_0, Ar_1, Ar_2) -> Com_1(evalEx7bbin(Ar_0, Ar_1, Ar_2)) [ Ar_1 - 2 >= 0 /\ Ar_0 + Ar_1 - 3 >= 0 /\ -Ar_0 + Ar_1 - 1 >= 0 /\ Ar_0 - 1 >= 0 /\ Ar_2 >= Ar_0 + 1 ]

		(Comp: 1, Cost: 1)    evalEx7entryin(Ar_0, Ar_1, Ar_2) -> Com_1(evalEx7bb3in(Ar_0, Ar_1, Ar_0 + 1)) [ Ar_0 >= 1 /\ Ar_1 >= Ar_0 + 1 ]

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

	start location:	koat_start

	leaf cost:	0



By chaining the transition evalEx7bb3in(Ar_0, Ar_1, Ar_2) -> Com_1(evalEx7bbin(Ar_0, Ar_1, Ar_2)) [ Ar_1 - 2 >= 0 /\ Ar_0 + Ar_1 - 3 >= 0 /\ -Ar_0 + Ar_1 - 1 >= 0 /\ Ar_0 - 1 >= 0 /\ Ar_0 >= Ar_2 + 1 ] with all transitions in problem 6, the following new transition is obtained:

	evalEx7bb3in(Ar_0, Ar_1, Ar_2) -> Com_1(evalEx7bb3in(Ar_0, Ar_1, Ar_2 + 1)) [ Ar_1 - 2 >= 0 /\ Ar_0 + Ar_1 - 3 >= 0 /\ -Ar_0 + Ar_1 - 1 >= 0 /\ Ar_0 - 1 >= 0 /\ Ar_0 >= Ar_2 + 1 /\ Ar_1 >= Ar_2 ]

We thus obtain the following problem:

7:	T:

		(Comp: ?, Cost: 2)    evalEx7bb3in(Ar_0, Ar_1, Ar_2) -> Com_1(evalEx7bb3in(Ar_0, Ar_1, Ar_2 + 1)) [ Ar_1 - 2 >= 0 /\ Ar_0 + Ar_1 - 3 >= 0 /\ -Ar_0 + Ar_1 - 1 >= 0 /\ Ar_0 - 1 >= 0 /\ Ar_0 >= Ar_2 + 1 /\ Ar_1 >= Ar_2 ]

		(Comp: 2, Cost: 1)    evalEx7returnin(Ar_0, Ar_1, Ar_2) -> Com_1(evalEx7stop(Ar_0, Ar_1, Ar_2)) [ Ar_1 - Ar_2 - 1 >= 0 /\ Ar_0 - Ar_2 >= 0 /\ Ar_2 - 1 >= 0 /\ Ar_1 + Ar_2 - 3 >= 0 /\ Ar_0 + Ar_2 - 2 >= 0 /\ -Ar_0 + Ar_2 >= 0 /\ Ar_1 - 2 >= 0 /\ Ar_0 + Ar_1 - 3 >= 0 /\ -Ar_0 + Ar_1 - 1 >= 0 /\ Ar_0 - 1 >= 0 ]

		(Comp: 2, Cost: 1)    evalEx7bb3in(Ar_0, Ar_1, Ar_2) -> Com_1(evalEx7returnin(Ar_0, Ar_1, Ar_2)) [ Ar_1 - 2 >= 0 /\ Ar_0 + Ar_1 - 3 >= 0 /\ -Ar_0 + Ar_1 - 1 >= 0 /\ Ar_0 - 1 >= 0 /\ Ar_2 = Ar_0 ]

		(Comp: ?, Cost: 1)    evalEx7bbin(Ar_0, Ar_1, Ar_2) -> Com_1(evalEx7bb3in(Ar_0, Ar_1, 0)) [ Ar_1 - 2 >= 0 /\ Ar_0 + Ar_1 - 3 >= 0 /\ -Ar_0 + Ar_1 - 1 >= 0 /\ Ar_0 - 1 >= 0 /\ Ar_2 >= Ar_1 + 1 ]

		(Comp: ?, Cost: 1)    evalEx7bbin(Ar_0, Ar_1, Ar_2) -> Com_1(evalEx7bb3in(Ar_0, Ar_1, Ar_2 + 1)) [ Ar_1 - 2 >= 0 /\ Ar_0 + Ar_1 - 3 >= 0 /\ -Ar_0 + Ar_1 - 1 >= 0 /\ Ar_0 - 1 >= 0 /\ Ar_1 >= Ar_2 ]

		(Comp: ?, Cost: 1)    evalEx7bb3in(Ar_0, Ar_1, Ar_2) -> Com_1(evalEx7bbin(Ar_0, Ar_1, Ar_2)) [ Ar_1 - 2 >= 0 /\ Ar_0 + Ar_1 - 3 >= 0 /\ -Ar_0 + Ar_1 - 1 >= 0 /\ Ar_0 - 1 >= 0 /\ Ar_2 >= Ar_0 + 1 ]

		(Comp: 1, Cost: 1)    evalEx7entryin(Ar_0, Ar_1, Ar_2) -> Com_1(evalEx7bb3in(Ar_0, Ar_1, Ar_0 + 1)) [ Ar_0 >= 1 /\ Ar_1 >= Ar_0 + 1 ]

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

	start location:	koat_start

	leaf cost:	0



A polynomial rank function with

	Pol(evalEx7bbin) = V_2 - V_3 + 1

	Pol(evalEx7bb3in) = V_2 - V_3 + 1

and size complexities

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

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

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

	S("evalEx7entryin(Ar_0, Ar_1, Ar_2) -> Com_1(evalEx7bb3in(Ar_0, Ar_1, Ar_0 + 1)) [ Ar_0 >= 1 /\\ Ar_1 >= Ar_0 + 1 ]", 0-0) = Ar_0

	S("evalEx7entryin(Ar_0, Ar_1, Ar_2) -> Com_1(evalEx7bb3in(Ar_0, Ar_1, Ar_0 + 1)) [ Ar_0 >= 1 /\\ Ar_1 >= Ar_0 + 1 ]", 0-1) = Ar_1

	S("evalEx7entryin(Ar_0, Ar_1, Ar_2) -> Com_1(evalEx7bb3in(Ar_0, Ar_1, Ar_0 + 1)) [ Ar_0 >= 1 /\\ Ar_1 >= Ar_0 + 1 ]", 0-2) = Ar_1

	S("evalEx7bb3in(Ar_0, Ar_1, Ar_2) -> Com_1(evalEx7bbin(Ar_0, Ar_1, Ar_2)) [ Ar_1 - 2 >= 0 /\\ Ar_0 + Ar_1 - 3 >= 0 /\\ -Ar_0 + Ar_1 - 1 >= 0 /\\ Ar_0 - 1 >= 0 /\\ Ar_2 >= Ar_0 + 1 ]", 0-0) = Ar_0

	S("evalEx7bb3in(Ar_0, Ar_1, Ar_2) -> Com_1(evalEx7bbin(Ar_0, Ar_1, Ar_2)) [ Ar_1 - 2 >= 0 /\\ Ar_0 + Ar_1 - 3 >= 0 /\\ -Ar_0 + Ar_1 - 1 >= 0 /\\ Ar_0 - 1 >= 0 /\\ Ar_2 >= Ar_0 + 1 ]", 0-1) = Ar_1

	S("evalEx7bb3in(Ar_0, Ar_1, Ar_2) -> Com_1(evalEx7bbin(Ar_0, Ar_1, Ar_2)) [ Ar_1 - 2 >= 0 /\\ Ar_0 + Ar_1 - 3 >= 0 /\\ -Ar_0 + Ar_1 - 1 >= 0 /\\ Ar_0 - 1 >= 0 /\\ Ar_2 >= Ar_0 + 1 ]", 0-2) = ?

	S("evalEx7bbin(Ar_0, Ar_1, Ar_2) -> Com_1(evalEx7bb3in(Ar_0, Ar_1, Ar_2 + 1)) [ Ar_1 - 2 >= 0 /\\ Ar_0 + Ar_1 - 3 >= 0 /\\ -Ar_0 + Ar_1 - 1 >= 0 /\\ Ar_0 - 1 >= 0 /\\ Ar_1 >= Ar_2 ]", 0-0) = Ar_0

	S("evalEx7bbin(Ar_0, Ar_1, Ar_2) -> Com_1(evalEx7bb3in(Ar_0, Ar_1, Ar_2 + 1)) [ Ar_1 - 2 >= 0 /\\ Ar_0 + Ar_1 - 3 >= 0 /\\ -Ar_0 + Ar_1 - 1 >= 0 /\\ Ar_0 - 1 >= 0 /\\ Ar_1 >= Ar_2 ]", 0-1) = Ar_1

	S("evalEx7bbin(Ar_0, Ar_1, Ar_2) -> Com_1(evalEx7bb3in(Ar_0, Ar_1, Ar_2 + 1)) [ Ar_1 - 2 >= 0 /\\ Ar_0 + Ar_1 - 3 >= 0 /\\ -Ar_0 + Ar_1 - 1 >= 0 /\\ Ar_0 - 1 >= 0 /\\ Ar_1 >= Ar_2 ]", 0-2) = ?

	S("evalEx7bbin(Ar_0, Ar_1, Ar_2) -> Com_1(evalEx7bb3in(Ar_0, Ar_1, 0)) [ Ar_1 - 2 >= 0 /\\ Ar_0 + Ar_1 - 3 >= 0 /\\ -Ar_0 + Ar_1 - 1 >= 0 /\\ Ar_0 - 1 >= 0 /\\ Ar_2 >= Ar_1 + 1 ]", 0-0) = Ar_0

	S("evalEx7bbin(Ar_0, Ar_1, Ar_2) -> Com_1(evalEx7bb3in(Ar_0, Ar_1, 0)) [ Ar_1 - 2 >= 0 /\\ Ar_0 + Ar_1 - 3 >= 0 /\\ -Ar_0 + Ar_1 - 1 >= 0 /\\ Ar_0 - 1 >= 0 /\\ Ar_2 >= Ar_1 + 1 ]", 0-1) = Ar_1

	S("evalEx7bbin(Ar_0, Ar_1, Ar_2) -> Com_1(evalEx7bb3in(Ar_0, Ar_1, 0)) [ Ar_1 - 2 >= 0 /\\ Ar_0 + Ar_1 - 3 >= 0 /\\ -Ar_0 + Ar_1 - 1 >= 0 /\\ Ar_0 - 1 >= 0 /\\ Ar_2 >= Ar_1 + 1 ]", 0-2) = 0

	S("evalEx7bb3in(Ar_0, Ar_1, Ar_2) -> Com_1(evalEx7returnin(Ar_0, Ar_1, Ar_2)) [ Ar_1 - 2 >= 0 /\\ Ar_0 + Ar_1 - 3 >= 0 /\\ -Ar_0 + Ar_1 - 1 >= 0 /\\ Ar_0 - 1 >= 0 /\\ Ar_2 = Ar_0 ]", 0-0) = Ar_0

	S("evalEx7bb3in(Ar_0, Ar_1, Ar_2) -> Com_1(evalEx7returnin(Ar_0, Ar_1, Ar_2)) [ Ar_1 - 2 >= 0 /\\ Ar_0 + Ar_1 - 3 >= 0 /\\ -Ar_0 + Ar_1 - 1 >= 0 /\\ Ar_0 - 1 >= 0 /\\ Ar_2 = Ar_0 ]", 0-1) = Ar_1

	S("evalEx7bb3in(Ar_0, Ar_1, Ar_2) -> Com_1(evalEx7returnin(Ar_0, Ar_1, Ar_2)) [ Ar_1 - 2 >= 0 /\\ Ar_0 + Ar_1 - 3 >= 0 /\\ -Ar_0 + Ar_1 - 1 >= 0 /\\ Ar_0 - 1 >= 0 /\\ Ar_2 = Ar_0 ]", 0-2) = ?

	S("evalEx7returnin(Ar_0, Ar_1, Ar_2) -> Com_1(evalEx7stop(Ar_0, Ar_1, Ar_2)) [ Ar_1 - Ar_2 - 1 >= 0 /\\ Ar_0 - Ar_2 >= 0 /\\ Ar_2 - 1 >= 0 /\\ Ar_1 + Ar_2 - 3 >= 0 /\\ Ar_0 + Ar_2 - 2 >= 0 /\\ -Ar_0 + Ar_2 >= 0 /\\ Ar_1 - 2 >= 0 /\\ Ar_0 + Ar_1 - 3 >= 0 /\\ -Ar_0 + Ar_1 - 1 >= 0 /\\ Ar_0 - 1 >= 0 ]", 0-0) = Ar_0

	S("evalEx7returnin(Ar_0, Ar_1, Ar_2) -> Com_1(evalEx7stop(Ar_0, Ar_1, Ar_2)) [ Ar_1 - Ar_2 - 1 >= 0 /\\ Ar_0 - Ar_2 >= 0 /\\ Ar_2 - 1 >= 0 /\\ Ar_1 + Ar_2 - 3 >= 0 /\\ Ar_0 + Ar_2 - 2 >= 0 /\\ -Ar_0 + Ar_2 >= 0 /\\ Ar_1 - 2 >= 0 /\\ Ar_0 + Ar_1 - 3 >= 0 /\\ -Ar_0 + Ar_1 - 1 >= 0 /\\ Ar_0 - 1 >= 0 ]", 0-1) = Ar_1

	S("evalEx7returnin(Ar_0, Ar_1, Ar_2) -> Com_1(evalEx7stop(Ar_0, Ar_1, Ar_2)) [ Ar_1 - Ar_2 - 1 >= 0 /\\ Ar_0 - Ar_2 >= 0 /\\ Ar_2 - 1 >= 0 /\\ Ar_1 + Ar_2 - 3 >= 0 /\\ Ar_0 + Ar_2 - 2 >= 0 /\\ -Ar_0 + Ar_2 >= 0 /\\ Ar_1 - 2 >= 0 /\\ Ar_0 + Ar_1 - 3 >= 0 /\\ -Ar_0 + Ar_1 - 1 >= 0 /\\ Ar_0 - 1 >= 0 ]", 0-2) = ?

	S("evalEx7bb3in(Ar_0, Ar_1, Ar_2) -> Com_1(evalEx7bb3in(Ar_0, Ar_1, Ar_2 + 1)) [ Ar_1 - 2 >= 0 /\\ Ar_0 + Ar_1 - 3 >= 0 /\\ -Ar_0 + Ar_1 - 1 >= 0 /\\ Ar_0 - 1 >= 0 /\\ Ar_0 >= Ar_2 + 1 /\\ Ar_1 >= Ar_2 ]", 0-0) = Ar_0

	S("evalEx7bb3in(Ar_0, Ar_1, Ar_2) -> Com_1(evalEx7bb3in(Ar_0, Ar_1, Ar_2 + 1)) [ Ar_1 - 2 >= 0 /\\ Ar_0 + Ar_1 - 3 >= 0 /\\ -Ar_0 + Ar_1 - 1 >= 0 /\\ Ar_0 - 1 >= 0 /\\ Ar_0 >= Ar_2 + 1 /\\ Ar_1 >= Ar_2 ]", 0-1) = Ar_1

	S("evalEx7bb3in(Ar_0, Ar_1, Ar_2) -> Com_1(evalEx7bb3in(Ar_0, Ar_1, Ar_2 + 1)) [ Ar_1 - 2 >= 0 /\\ Ar_0 + Ar_1 - 3 >= 0 /\\ -Ar_0 + Ar_1 - 1 >= 0 /\\ Ar_0 - 1 >= 0 /\\ Ar_0 >= Ar_2 + 1 /\\ Ar_1 >= Ar_2 ]", 0-2) = ?

orients the transitions

	evalEx7bbin(Ar_0, Ar_1, Ar_2) -> Com_1(evalEx7bb3in(Ar_0, Ar_1, Ar_2 + 1)) [ Ar_1 - 2 >= 0 /\ Ar_0 + Ar_1 - 3 >= 0 /\ -Ar_0 + Ar_1 - 1 >= 0 /\ Ar_0 - 1 >= 0 /\ Ar_1 >= Ar_2 ]

	evalEx7bb3in(Ar_0, Ar_1, Ar_2) -> Com_1(evalEx7bbin(Ar_0, Ar_1, Ar_2)) [ Ar_1 - 2 >= 0 /\ Ar_0 + Ar_1 - 3 >= 0 /\ -Ar_0 + Ar_1 - 1 >= 0 /\ Ar_0 - 1 >= 0 /\ Ar_2 >= Ar_0 + 1 ]

weakly and the transition

	evalEx7bbin(Ar_0, Ar_1, Ar_2) -> Com_1(evalEx7bb3in(Ar_0, Ar_1, Ar_2 + 1)) [ Ar_1 - 2 >= 0 /\ Ar_0 + Ar_1 - 3 >= 0 /\ -Ar_0 + Ar_1 - 1 >= 0 /\ Ar_0 - 1 >= 0 /\ Ar_1 >= Ar_2 ]

strictly and produces the following problem:

8:	T:

		(Comp: ?, Cost: 2)             evalEx7bb3in(Ar_0, Ar_1, Ar_2) -> Com_1(evalEx7bb3in(Ar_0, Ar_1, Ar_2 + 1)) [ Ar_1 - 2 >= 0 /\ Ar_0 + Ar_1 - 3 >= 0 /\ -Ar_0 + Ar_1 - 1 >= 0 /\ Ar_0 - 1 >= 0 /\ Ar_0 >= Ar_2 + 1 /\ Ar_1 >= Ar_2 ]

		(Comp: 2, Cost: 1)             evalEx7returnin(Ar_0, Ar_1, Ar_2) -> Com_1(evalEx7stop(Ar_0, Ar_1, Ar_2)) [ Ar_1 - Ar_2 - 1 >= 0 /\ Ar_0 - Ar_2 >= 0 /\ Ar_2 - 1 >= 0 /\ Ar_1 + Ar_2 - 3 >= 0 /\ Ar_0 + Ar_2 - 2 >= 0 /\ -Ar_0 + Ar_2 >= 0 /\ Ar_1 - 2 >= 0 /\ Ar_0 + Ar_1 - 3 >= 0 /\ -Ar_0 + Ar_1 - 1 >= 0 /\ Ar_0 - 1 >= 0 ]

		(Comp: 2, Cost: 1)             evalEx7bb3in(Ar_0, Ar_1, Ar_2) -> Com_1(evalEx7returnin(Ar_0, Ar_1, Ar_2)) [ Ar_1 - 2 >= 0 /\ Ar_0 + Ar_1 - 3 >= 0 /\ -Ar_0 + Ar_1 - 1 >= 0 /\ Ar_0 - 1 >= 0 /\ Ar_2 = Ar_0 ]

		(Comp: ?, Cost: 1)             evalEx7bbin(Ar_0, Ar_1, Ar_2) -> Com_1(evalEx7bb3in(Ar_0, Ar_1, 0)) [ Ar_1 - 2 >= 0 /\ Ar_0 + Ar_1 - 3 >= 0 /\ -Ar_0 + Ar_1 - 1 >= 0 /\ Ar_0 - 1 >= 0 /\ Ar_2 >= Ar_1 + 1 ]

		(Comp: 2*Ar_1 + 1, Cost: 1)    evalEx7bbin(Ar_0, Ar_1, Ar_2) -> Com_1(evalEx7bb3in(Ar_0, Ar_1, Ar_2 + 1)) [ Ar_1 - 2 >= 0 /\ Ar_0 + Ar_1 - 3 >= 0 /\ -Ar_0 + Ar_1 - 1 >= 0 /\ Ar_0 - 1 >= 0 /\ Ar_1 >= Ar_2 ]

		(Comp: ?, Cost: 1)             evalEx7bb3in(Ar_0, Ar_1, Ar_2) -> Com_1(evalEx7bbin(Ar_0, Ar_1, Ar_2)) [ Ar_1 - 2 >= 0 /\ Ar_0 + Ar_1 - 3 >= 0 /\ -Ar_0 + Ar_1 - 1 >= 0 /\ Ar_0 - 1 >= 0 /\ Ar_2 >= Ar_0 + 1 ]

		(Comp: 1, Cost: 1)             evalEx7entryin(Ar_0, Ar_1, Ar_2) -> Com_1(evalEx7bb3in(Ar_0, Ar_1, Ar_0 + 1)) [ Ar_0 >= 1 /\ Ar_1 >= Ar_0 + 1 ]

		(Comp: 1, Cost: 1)             koat_start(Ar_0, Ar_1, Ar_2) -> Com_1(evalEx7entryin(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: ?, Cost: 2)             evalEx7bb3in(Ar_0, Ar_1, Ar_2) -> Com_1(evalEx7bb3in(Ar_0, Ar_1, Ar_2 + 1)) [ Ar_1 - 2 >= 0 /\ Ar_0 + Ar_1 - 3 >= 0 /\ -Ar_0 + Ar_1 - 1 >= 0 /\ Ar_0 - 1 >= 0 /\ Ar_0 >= Ar_2 + 1 /\ Ar_1 >= Ar_2 ]

		(Comp: 2, Cost: 1)             evalEx7returnin(Ar_0, Ar_1, Ar_2) -> Com_1(evalEx7stop(Ar_0, Ar_1, Ar_2)) [ Ar_1 - Ar_2 - 1 >= 0 /\ Ar_0 - Ar_2 >= 0 /\ Ar_2 - 1 >= 0 /\ Ar_1 + Ar_2 - 3 >= 0 /\ Ar_0 + Ar_2 - 2 >= 0 /\ -Ar_0 + Ar_2 >= 0 /\ Ar_1 - 2 >= 0 /\ Ar_0 + Ar_1 - 3 >= 0 /\ -Ar_0 + Ar_1 - 1 >= 0 /\ Ar_0 - 1 >= 0 ]

		(Comp: 2, Cost: 1)             evalEx7bb3in(Ar_0, Ar_1, Ar_2) -> Com_1(evalEx7returnin(Ar_0, Ar_1, Ar_2)) [ Ar_1 - 2 >= 0 /\ Ar_0 + Ar_1 - 3 >= 0 /\ -Ar_0 + Ar_1 - 1 >= 0 /\ Ar_0 - 1 >= 0 /\ Ar_2 = Ar_0 ]

		(Comp: 2*Ar_1 + 2, Cost: 1)    evalEx7bbin(Ar_0, Ar_1, Ar_2) -> Com_1(evalEx7bb3in(Ar_0, Ar_1, 0)) [ Ar_1 - 2 >= 0 /\ Ar_0 + Ar_1 - 3 >= 0 /\ -Ar_0 + Ar_1 - 1 >= 0 /\ Ar_0 - 1 >= 0 /\ Ar_2 >= Ar_1 + 1 ]

		(Comp: 2*Ar_1 + 1, Cost: 1)    evalEx7bbin(Ar_0, Ar_1, Ar_2) -> Com_1(evalEx7bb3in(Ar_0, Ar_1, Ar_2 + 1)) [ Ar_1 - 2 >= 0 /\ Ar_0 + Ar_1 - 3 >= 0 /\ -Ar_0 + Ar_1 - 1 >= 0 /\ Ar_0 - 1 >= 0 /\ Ar_1 >= Ar_2 ]

		(Comp: 2*Ar_1 + 2, Cost: 1)    evalEx7bb3in(Ar_0, Ar_1, Ar_2) -> Com_1(evalEx7bbin(Ar_0, Ar_1, Ar_2)) [ Ar_1 - 2 >= 0 /\ Ar_0 + Ar_1 - 3 >= 0 /\ -Ar_0 + Ar_1 - 1 >= 0 /\ Ar_0 - 1 >= 0 /\ Ar_2 >= Ar_0 + 1 ]

		(Comp: 1, Cost: 1)             evalEx7entryin(Ar_0, Ar_1, Ar_2) -> Com_1(evalEx7bb3in(Ar_0, Ar_1, Ar_0 + 1)) [ Ar_0 >= 1 /\ Ar_1 >= Ar_0 + 1 ]

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

	start location:	koat_start

	leaf cost:	0



A polynomial rank function with

	Pol(evalEx7bb3in) = V_2 - V_3 + 1

and size complexities

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

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

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

	S("evalEx7entryin(Ar_0, Ar_1, Ar_2) -> Com_1(evalEx7bb3in(Ar_0, Ar_1, Ar_0 + 1)) [ Ar_0 >= 1 /\\ Ar_1 >= Ar_0 + 1 ]", 0-0) = Ar_0

	S("evalEx7entryin(Ar_0, Ar_1, Ar_2) -> Com_1(evalEx7bb3in(Ar_0, Ar_1, Ar_0 + 1)) [ Ar_0 >= 1 /\\ Ar_1 >= Ar_0 + 1 ]", 0-1) = Ar_1

	S("evalEx7entryin(Ar_0, Ar_1, Ar_2) -> Com_1(evalEx7bb3in(Ar_0, Ar_1, Ar_0 + 1)) [ Ar_0 >= 1 /\\ Ar_1 >= Ar_0 + 1 ]", 0-2) = Ar_1

	S("evalEx7bb3in(Ar_0, Ar_1, Ar_2) -> Com_1(evalEx7bbin(Ar_0, Ar_1, Ar_2)) [ Ar_1 - 2 >= 0 /\\ Ar_0 + Ar_1 - 3 >= 0 /\\ -Ar_0 + Ar_1 - 1 >= 0 /\\ Ar_0 - 1 >= 0 /\\ Ar_2 >= Ar_0 + 1 ]", 0-0) = Ar_0

	S("evalEx7bb3in(Ar_0, Ar_1, Ar_2) -> Com_1(evalEx7bbin(Ar_0, Ar_1, Ar_2)) [ Ar_1 - 2 >= 0 /\\ Ar_0 + Ar_1 - 3 >= 0 /\\ -Ar_0 + Ar_1 - 1 >= 0 /\\ Ar_0 - 1 >= 0 /\\ Ar_2 >= Ar_0 + 1 ]", 0-1) = Ar_1

	S("evalEx7bb3in(Ar_0, Ar_1, Ar_2) -> Com_1(evalEx7bbin(Ar_0, Ar_1, Ar_2)) [ Ar_1 - 2 >= 0 /\\ Ar_0 + Ar_1 - 3 >= 0 /\\ -Ar_0 + Ar_1 - 1 >= 0 /\\ Ar_0 - 1 >= 0 /\\ Ar_2 >= Ar_0 + 1 ]", 0-2) = 3*Ar_1 + 9

	S("evalEx7bbin(Ar_0, Ar_1, Ar_2) -> Com_1(evalEx7bb3in(Ar_0, Ar_1, Ar_2 + 1)) [ Ar_1 - 2 >= 0 /\\ Ar_0 + Ar_1 - 3 >= 0 /\\ -Ar_0 + Ar_1 - 1 >= 0 /\\ Ar_0 - 1 >= 0 /\\ Ar_1 >= Ar_2 ]", 0-0) = Ar_0

	S("evalEx7bbin(Ar_0, Ar_1, Ar_2) -> Com_1(evalEx7bb3in(Ar_0, Ar_1, Ar_2 + 1)) [ Ar_1 - 2 >= 0 /\\ Ar_0 + Ar_1 - 3 >= 0 /\\ -Ar_0 + Ar_1 - 1 >= 0 /\\ Ar_0 - 1 >= 0 /\\ Ar_1 >= Ar_2 ]", 0-1) = Ar_1

	S("evalEx7bbin(Ar_0, Ar_1, Ar_2) -> Com_1(evalEx7bb3in(Ar_0, Ar_1, Ar_2 + 1)) [ Ar_1 - 2 >= 0 /\\ Ar_0 + Ar_1 - 3 >= 0 /\\ -Ar_0 + Ar_1 - 1 >= 0 /\\ Ar_0 - 1 >= 0 /\\ Ar_1 >= Ar_2 ]", 0-2) = 3*Ar_1 + 9

	S("evalEx7bbin(Ar_0, Ar_1, Ar_2) -> Com_1(evalEx7bb3in(Ar_0, Ar_1, 0)) [ Ar_1 - 2 >= 0 /\\ Ar_0 + Ar_1 - 3 >= 0 /\\ -Ar_0 + Ar_1 - 1 >= 0 /\\ Ar_0 - 1 >= 0 /\\ Ar_2 >= Ar_1 + 1 ]", 0-0) = Ar_0

	S("evalEx7bbin(Ar_0, Ar_1, Ar_2) -> Com_1(evalEx7bb3in(Ar_0, Ar_1, 0)) [ Ar_1 - 2 >= 0 /\\ Ar_0 + Ar_1 - 3 >= 0 /\\ -Ar_0 + Ar_1 - 1 >= 0 /\\ Ar_0 - 1 >= 0 /\\ Ar_2 >= Ar_1 + 1 ]", 0-1) = Ar_1

	S("evalEx7bbin(Ar_0, Ar_1, Ar_2) -> Com_1(evalEx7bb3in(Ar_0, Ar_1, 0)) [ Ar_1 - 2 >= 0 /\\ Ar_0 + Ar_1 - 3 >= 0 /\\ -Ar_0 + Ar_1 - 1 >= 0 /\\ Ar_0 - 1 >= 0 /\\ Ar_2 >= Ar_1 + 1 ]", 0-2) = 0

	S("evalEx7bb3in(Ar_0, Ar_1, Ar_2) -> Com_1(evalEx7returnin(Ar_0, Ar_1, Ar_2)) [ Ar_1 - 2 >= 0 /\\ Ar_0 + Ar_1 - 3 >= 0 /\\ -Ar_0 + Ar_1 - 1 >= 0 /\\ Ar_0 - 1 >= 0 /\\ Ar_2 = Ar_0 ]", 0-0) = Ar_0

	S("evalEx7bb3in(Ar_0, Ar_1, Ar_2) -> Com_1(evalEx7returnin(Ar_0, Ar_1, Ar_2)) [ Ar_1 - 2 >= 0 /\\ Ar_0 + Ar_1 - 3 >= 0 /\\ -Ar_0 + Ar_1 - 1 >= 0 /\\ Ar_0 - 1 >= 0 /\\ Ar_2 = Ar_0 ]", 0-1) = Ar_1

	S("evalEx7bb3in(Ar_0, Ar_1, Ar_2) -> Com_1(evalEx7returnin(Ar_0, Ar_1, Ar_2)) [ Ar_1 - 2 >= 0 /\\ Ar_0 + Ar_1 - 3 >= 0 /\\ -Ar_0 + Ar_1 - 1 >= 0 /\\ Ar_0 - 1 >= 0 /\\ Ar_2 = Ar_0 ]", 0-2) = ?

	S("evalEx7returnin(Ar_0, Ar_1, Ar_2) -> Com_1(evalEx7stop(Ar_0, Ar_1, Ar_2)) [ Ar_1 - Ar_2 - 1 >= 0 /\\ Ar_0 - Ar_2 >= 0 /\\ Ar_2 - 1 >= 0 /\\ Ar_1 + Ar_2 - 3 >= 0 /\\ Ar_0 + Ar_2 - 2 >= 0 /\\ -Ar_0 + Ar_2 >= 0 /\\ Ar_1 - 2 >= 0 /\\ Ar_0 + Ar_1 - 3 >= 0 /\\ -Ar_0 + Ar_1 - 1 >= 0 /\\ Ar_0 - 1 >= 0 ]", 0-0) = Ar_0

	S("evalEx7returnin(Ar_0, Ar_1, Ar_2) -> Com_1(evalEx7stop(Ar_0, Ar_1, Ar_2)) [ Ar_1 - Ar_2 - 1 >= 0 /\\ Ar_0 - Ar_2 >= 0 /\\ Ar_2 - 1 >= 0 /\\ Ar_1 + Ar_2 - 3 >= 0 /\\ Ar_0 + Ar_2 - 2 >= 0 /\\ -Ar_0 + Ar_2 >= 0 /\\ Ar_1 - 2 >= 0 /\\ Ar_0 + Ar_1 - 3 >= 0 /\\ -Ar_0 + Ar_1 - 1 >= 0 /\\ Ar_0 - 1 >= 0 ]", 0-1) = Ar_1

	S("evalEx7returnin(Ar_0, Ar_1, Ar_2) -> Com_1(evalEx7stop(Ar_0, Ar_1, Ar_2)) [ Ar_1 - Ar_2 - 1 >= 0 /\\ Ar_0 - Ar_2 >= 0 /\\ Ar_2 - 1 >= 0 /\\ Ar_1 + Ar_2 - 3 >= 0 /\\ Ar_0 + Ar_2 - 2 >= 0 /\\ -Ar_0 + Ar_2 >= 0 /\\ Ar_1 - 2 >= 0 /\\ Ar_0 + Ar_1 - 3 >= 0 /\\ -Ar_0 + Ar_1 - 1 >= 0 /\\ Ar_0 - 1 >= 0 ]", 0-2) = ?

	S("evalEx7bb3in(Ar_0, Ar_1, Ar_2) -> Com_1(evalEx7bb3in(Ar_0, Ar_1, Ar_2 + 1)) [ Ar_1 - 2 >= 0 /\\ Ar_0 + Ar_1 - 3 >= 0 /\\ -Ar_0 + Ar_1 - 1 >= 0 /\\ Ar_0 - 1 >= 0 /\\ Ar_0 >= Ar_2 + 1 /\\ Ar_1 >= Ar_2 ]", 0-0) = Ar_0

	S("evalEx7bb3in(Ar_0, Ar_1, Ar_2) -> Com_1(evalEx7bb3in(Ar_0, Ar_1, Ar_2 + 1)) [ Ar_1 - 2 >= 0 /\\ Ar_0 + Ar_1 - 3 >= 0 /\\ -Ar_0 + Ar_1 - 1 >= 0 /\\ Ar_0 - 1 >= 0 /\\ Ar_0 >= Ar_2 + 1 /\\ Ar_1 >= Ar_2 ]", 0-1) = Ar_1

	S("evalEx7bb3in(Ar_0, Ar_1, Ar_2) -> Com_1(evalEx7bb3in(Ar_0, Ar_1, Ar_2 + 1)) [ Ar_1 - 2 >= 0 /\\ Ar_0 + Ar_1 - 3 >= 0 /\\ -Ar_0 + Ar_1 - 1 >= 0 /\\ Ar_0 - 1 >= 0 /\\ Ar_0 >= Ar_2 + 1 /\\ Ar_1 >= Ar_2 ]", 0-2) = ?

orients the transitions

	evalEx7bb3in(Ar_0, Ar_1, Ar_2) -> Com_1(evalEx7bb3in(Ar_0, Ar_1, Ar_2 + 1)) [ Ar_1 - 2 >= 0 /\ Ar_0 + Ar_1 - 3 >= 0 /\ -Ar_0 + Ar_1 - 1 >= 0 /\ Ar_0 - 1 >= 0 /\ Ar_0 >= Ar_2 + 1 /\ Ar_1 >= Ar_2 ]

weakly and the transition

	evalEx7bb3in(Ar_0, Ar_1, Ar_2) -> Com_1(evalEx7bb3in(Ar_0, Ar_1, Ar_2 + 1)) [ Ar_1 - 2 >= 0 /\ Ar_0 + Ar_1 - 3 >= 0 /\ -Ar_0 + Ar_1 - 1 >= 0 /\ Ar_0 - 1 >= 0 /\ Ar_0 >= Ar_2 + 1 /\ Ar_1 >= Ar_2 ]

strictly and produces the following problem:

10:	T:

		(Comp: 10*Ar_1^2 + 28*Ar_1 + 12, Cost: 2)    evalEx7bb3in(Ar_0, Ar_1, Ar_2) -> Com_1(evalEx7bb3in(Ar_0, Ar_1, Ar_2 + 1)) [ Ar_1 - 2 >= 0 /\ Ar_0 + Ar_1 - 3 >= 0 /\ -Ar_0 + Ar_1 - 1 >= 0 /\ Ar_0 - 1 >= 0 /\ Ar_0 >= Ar_2 + 1 /\ Ar_1 >= Ar_2 ]

		(Comp: 2, Cost: 1)                           evalEx7returnin(Ar_0, Ar_1, Ar_2) -> Com_1(evalEx7stop(Ar_0, Ar_1, Ar_2)) [ Ar_1 - Ar_2 - 1 >= 0 /\ Ar_0 - Ar_2 >= 0 /\ Ar_2 - 1 >= 0 /\ Ar_1 + Ar_2 - 3 >= 0 /\ Ar_0 + Ar_2 - 2 >= 0 /\ -Ar_0 + Ar_2 >= 0 /\ Ar_1 - 2 >= 0 /\ Ar_0 + Ar_1 - 3 >= 0 /\ -Ar_0 + Ar_1 - 1 >= 0 /\ Ar_0 - 1 >= 0 ]

		(Comp: 2, Cost: 1)                           evalEx7bb3in(Ar_0, Ar_1, Ar_2) -> Com_1(evalEx7returnin(Ar_0, Ar_1, Ar_2)) [ Ar_1 - 2 >= 0 /\ Ar_0 + Ar_1 - 3 >= 0 /\ -Ar_0 + Ar_1 - 1 >= 0 /\ Ar_0 - 1 >= 0 /\ Ar_2 = Ar_0 ]

		(Comp: 2*Ar_1 + 2, Cost: 1)                  evalEx7bbin(Ar_0, Ar_1, Ar_2) -> Com_1(evalEx7bb3in(Ar_0, Ar_1, 0)) [ Ar_1 - 2 >= 0 /\ Ar_0 + Ar_1 - 3 >= 0 /\ -Ar_0 + Ar_1 - 1 >= 0 /\ Ar_0 - 1 >= 0 /\ Ar_2 >= Ar_1 + 1 ]

		(Comp: 2*Ar_1 + 1, Cost: 1)                  evalEx7bbin(Ar_0, Ar_1, Ar_2) -> Com_1(evalEx7bb3in(Ar_0, Ar_1, Ar_2 + 1)) [ Ar_1 - 2 >= 0 /\ Ar_0 + Ar_1 - 3 >= 0 /\ -Ar_0 + Ar_1 - 1 >= 0 /\ Ar_0 - 1 >= 0 /\ Ar_1 >= Ar_2 ]

		(Comp: 2*Ar_1 + 2, Cost: 1)                  evalEx7bb3in(Ar_0, Ar_1, Ar_2) -> Com_1(evalEx7bbin(Ar_0, Ar_1, Ar_2)) [ Ar_1 - 2 >= 0 /\ Ar_0 + Ar_1 - 3 >= 0 /\ -Ar_0 + Ar_1 - 1 >= 0 /\ Ar_0 - 1 >= 0 /\ Ar_2 >= Ar_0 + 1 ]

		(Comp: 1, Cost: 1)                           evalEx7entryin(Ar_0, Ar_1, Ar_2) -> Com_1(evalEx7bb3in(Ar_0, Ar_1, Ar_0 + 1)) [ Ar_0 >= 1 /\ Ar_1 >= Ar_0 + 1 ]

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

	start location:	koat_start

	leaf cost:	0



Complexity upper bound 20*Ar_1^2 + 62*Ar_1 + 35



Time: 0.240 sec (SMT: 0.196 sec)


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

(2)
BOUNDS(1, n^2)

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

(3) Loat Proof (FINISHED)


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



Initial linear ITS problem

   Start location: evalEx7start

      0: evalEx7start -> evalEx7entryin : [], cost: 1

      1: evalEx7entryin -> evalEx7bb3in : C'=1+A, [ A>=1 && B>=1+A ], cost: 1

      2: evalEx7bb3in -> evalEx7bbin : [ A>=1+C ], cost: 1

      3: evalEx7bb3in -> evalEx7bbin : [ C>=1+A ], cost: 1

      4: evalEx7bb3in -> evalEx7returnin : [ C==A ], cost: 1

      5: evalEx7bbin -> evalEx7bb3in : C'=0, [ C>=1+B ], cost: 1

      6: evalEx7bbin -> evalEx7bb3in : C'=1+C, [ B>=C ], cost: 1

      7: evalEx7returnin -> evalEx7stop : [], cost: 1



Checking for constant complexity:

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

      0: evalEx7start -> evalEx7entryin : [], cost: 1



Removed unreachable and leaf rules:

   Start location: evalEx7start

      0: evalEx7start -> evalEx7entryin : [], cost: 1

      1: evalEx7entryin -> evalEx7bb3in : C'=1+A, [ A>=1 && B>=1+A ], cost: 1

      2: evalEx7bb3in -> evalEx7bbin : [ A>=1+C ], cost: 1

      3: evalEx7bb3in -> evalEx7bbin : [ C>=1+A ], cost: 1

      5: evalEx7bbin -> evalEx7bb3in : C'=0, [ C>=1+B ], cost: 1

      6: evalEx7bbin -> evalEx7bb3in : C'=1+C, [ B>=C ], cost: 1



### Simplification by acceleration and chaining ###



Eliminated locations (on linear paths):

   Start location: evalEx7start

      8: evalEx7start -> evalEx7bb3in : C'=1+A, [ A>=1 && B>=1+A ], cost: 2

      2: evalEx7bb3in -> evalEx7bbin : [ A>=1+C ], cost: 1

      3: evalEx7bb3in -> evalEx7bbin : [ C>=1+A ], cost: 1

      5: evalEx7bbin -> evalEx7bb3in : C'=0, [ C>=1+B ], cost: 1

      6: evalEx7bbin -> evalEx7bb3in : C'=1+C, [ B>=C ], cost: 1



Eliminated locations (on tree-shaped paths):

   Start location: evalEx7start

      8: evalEx7start -> evalEx7bb3in : C'=1+A, [ A>=1 && B>=1+A ], cost: 2

      9: evalEx7bb3in -> evalEx7bb3in : C'=0, [ A>=1+C && C>=1+B ], cost: 2

     10: evalEx7bb3in -> evalEx7bb3in : C'=1+C, [ A>=1+C && B>=C ], cost: 2

     11: evalEx7bb3in -> evalEx7bb3in : C'=0, [ C>=1+A && C>=1+B ], cost: 2

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



Accelerating simple loops of location 2.

   Accelerating the following rules:

      9: evalEx7bb3in -> evalEx7bb3in : C'=0, [ A>=1+C && C>=1+B ], cost: 2

     10: evalEx7bb3in -> evalEx7bb3in : C'=1+C, [ A>=1+C && B>=C ], cost: 2

     11: evalEx7bb3in -> evalEx7bb3in : C'=0, [ C>=1+A && C>=1+B ], cost: 2

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



   Accelerated rule 9 with NONTERM (after strengthening guard), yielding the new rule 13.

   Found no metering function for rule 10.

   Accelerated rule 11 with NONTERM (after strengthening guard), yielding the new rule 14.

   Accelerated rule 12 with metering function 1-C+B, yielding the new rule 15.

   Nested simple loops 11 (outer loop) and 15 (inner loop) with NONTERM, resulting in the new rules: 16, 17.

   Removing the simple loops: 11 12.



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

   Start location: evalEx7start

      8: evalEx7start -> evalEx7bb3in : C'=1+A, [ A>=1 && B>=1+A ], cost: 2

      9: evalEx7bb3in -> evalEx7bb3in : C'=0, [ A>=1+C && C>=1+B ], cost: 2

     10: evalEx7bb3in -> evalEx7bb3in : C'=1+C, [ A>=1+C && B>=C ], cost: 2

     13: evalEx7bb3in -> [6] : [ A>=1+C && C>=1+B && A>=1 && 0>=1+B ], cost: NONTERM

     14: evalEx7bb3in -> [6] : [ C>=1+A && C>=1+B && 0>=1+A && 0>=1+B ], cost: NONTERM

     15: evalEx7bb3in -> evalEx7bb3in : C'=1+B, [ C>=1+A && B>=C ], cost: 2-2*C+2*B

     16: evalEx7bb3in -> [6] : [ C>=1+A && C>=1+B && 0>=1+A && B>=0 && 4+2*B>=1 ], cost: NONTERM

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



Chained accelerated rules (with incoming rules):

   Start location: evalEx7start

      8: evalEx7start -> evalEx7bb3in : C'=1+A, [ A>=1 && B>=1+A ], cost: 2

     18: evalEx7start -> evalEx7bb3in : C'=1+B, [ A>=1 && B>=1+A ], cost: 2-2*A+2*B



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

   Start location: evalEx7start

     18: evalEx7start -> evalEx7bb3in : C'=1+B, [ A>=1 && B>=1+A ], cost: 2-2*A+2*B



### Computing asymptotic complexity ###



Fully simplified ITS problem

   Start location: evalEx7start

     18: evalEx7start -> evalEx7bb3in : C'=1+B, [ A>=1 && B>=1+A ], cost: 2-2*A+2*B



Computing asymptotic complexity for rule 18

   Solved the limit problem by the following transformations:

      Created initial limit problem:

      2-2*A+2*B (+), A (+/+!), -A+B (+/+!) [not solved]



      removing all constraints (solved by SMT)

      resulting limit problem: [solved]



      applying transformation rule (C) using substitution {A==1,B==n}

      resulting limit problem:

      [solved]



   Solution:

      A / 1

      B / n

   Resulting cost 2*n has complexity: Poly(n^1)



Found new complexity Poly(n^1).



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

   Complexity:  Poly(n^1)

   Cpx degree:  1

   Solved cost: 2*n

   Rule cost:   2-2*A+2*B

   Rule guard:  [ A>=1 && B>=1+A ]



WORST_CASE(Omega(n^1),?)


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

(4)
BOUNDS(n^1, INF)