/export/starexec/sandbox/solver/bin/starexec_run_complexity /export/starexec/sandbox/benchmark/theBenchmark.koat /export/starexec/sandbox/output/output_files -------------------------------------------------------------------------------- WORST_CASE(Omega(n^1), O(n^2)) proof of /export/starexec/sandbox/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, 719 ms] (2) BOUNDS(1, n^2) (3) Loat Proof [FINISHED, 539 ms] (4) BOUNDS(n^1, INF) ---------------------------------------- (0) Obligation: Complexity Int TRS consisting of the following rules: evalrsdstart(A, B, C) -> Com_1(evalrsdentryin(A, B, C)) :|: TRUE evalrsdentryin(A, B, C) -> Com_1(evalrsdbbin(A, B, C)) :|: A >= 0 evalrsdentryin(A, B, C) -> Com_1(evalrsdreturnin(A, B, C)) :|: 0 >= A + 1 evalrsdbbin(A, B, C) -> Com_1(evalrsdbb4in(A, 2 * A, 2 * A)) :|: TRUE evalrsdbb4in(A, B, C) -> Com_1(evalrsdbb1in(A, B, C)) :|: C >= A evalrsdbb4in(A, B, C) -> Com_1(evalrsdreturnin(A, B, C)) :|: A >= C + 1 evalrsdbb1in(A, B, C) -> Com_1(evalrsdbb2in(A, B, C)) :|: 0 >= D + 1 evalrsdbb1in(A, B, C) -> Com_1(evalrsdbb2in(A, B, C)) :|: D >= 1 evalrsdbb1in(A, B, C) -> Com_1(evalrsdbb3in(A, B, C)) :|: TRUE evalrsdbb2in(A, B, C) -> Com_1(evalrsdbb4in(A, B, C - 1)) :|: TRUE evalrsdbb3in(A, B, C) -> Com_1(evalrsdbb4in(A, B - 1, B - 1)) :|: TRUE evalrsdreturnin(A, B, C) -> Com_1(evalrsdstop(A, B, C)) :|: TRUE The start-symbols are:[evalrsdstart_3] ---------------------------------------- (1) Koat Proof (FINISHED) YES(?, 36*Ar_0 + 40*Ar_0^2 + 19) Initial complexity problem: 1: T: (Comp: ?, Cost: 1) evalrsdstart(Ar_0, Ar_1, Ar_2) -> Com_1(evalrsdentryin(Ar_0, Ar_1, Ar_2)) (Comp: ?, Cost: 1) evalrsdentryin(Ar_0, Ar_1, Ar_2) -> Com_1(evalrsdbbin(Ar_0, Ar_1, Ar_2)) [ Ar_0 >= 0 ] (Comp: ?, Cost: 1) evalrsdentryin(Ar_0, Ar_1, Ar_2) -> Com_1(evalrsdreturnin(Ar_0, Ar_1, Ar_2)) [ 0 >= Ar_0 + 1 ] (Comp: ?, Cost: 1) evalrsdbbin(Ar_0, Ar_1, Ar_2) -> Com_1(evalrsdbb4in(Ar_0, 2*Ar_0, 2*Ar_0)) (Comp: ?, Cost: 1) evalrsdbb4in(Ar_0, Ar_1, Ar_2) -> Com_1(evalrsdbb1in(Ar_0, Ar_1, Ar_2)) [ Ar_2 >= Ar_0 ] (Comp: ?, Cost: 1) evalrsdbb4in(Ar_0, Ar_1, Ar_2) -> Com_1(evalrsdreturnin(Ar_0, Ar_1, Ar_2)) [ Ar_0 >= Ar_2 + 1 ] (Comp: ?, Cost: 1) evalrsdbb1in(Ar_0, Ar_1, Ar_2) -> Com_1(evalrsdbb2in(Ar_0, Ar_1, Ar_2)) [ 0 >= D + 1 ] (Comp: ?, Cost: 1) evalrsdbb1in(Ar_0, Ar_1, Ar_2) -> Com_1(evalrsdbb2in(Ar_0, Ar_1, Ar_2)) [ D >= 1 ] (Comp: ?, Cost: 1) evalrsdbb1in(Ar_0, Ar_1, Ar_2) -> Com_1(evalrsdbb3in(Ar_0, Ar_1, Ar_2)) (Comp: ?, Cost: 1) evalrsdbb2in(Ar_0, Ar_1, Ar_2) -> Com_1(evalrsdbb4in(Ar_0, Ar_1, Ar_2 - 1)) (Comp: ?, Cost: 1) evalrsdbb3in(Ar_0, Ar_1, Ar_2) -> Com_1(evalrsdbb4in(Ar_0, Ar_1 - 1, Ar_1 - 1)) (Comp: ?, Cost: 1) evalrsdreturnin(Ar_0, Ar_1, Ar_2) -> Com_1(evalrsdstop(Ar_0, Ar_1, Ar_2)) (Comp: 1, Cost: 0) koat_start(Ar_0, Ar_1, Ar_2) -> Com_1(evalrsdstart(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) evalrsdstart(Ar_0, Ar_1, Ar_2) -> Com_1(evalrsdentryin(Ar_0, Ar_1, Ar_2)) (Comp: 1, Cost: 1) evalrsdentryin(Ar_0, Ar_1, Ar_2) -> Com_1(evalrsdbbin(Ar_0, Ar_1, Ar_2)) [ Ar_0 >= 0 ] (Comp: 1, Cost: 1) evalrsdentryin(Ar_0, Ar_1, Ar_2) -> Com_1(evalrsdreturnin(Ar_0, Ar_1, Ar_2)) [ 0 >= Ar_0 + 1 ] (Comp: 1, Cost: 1) evalrsdbbin(Ar_0, Ar_1, Ar_2) -> Com_1(evalrsdbb4in(Ar_0, 2*Ar_0, 2*Ar_0)) (Comp: ?, Cost: 1) evalrsdbb4in(Ar_0, Ar_1, Ar_2) -> Com_1(evalrsdbb1in(Ar_0, Ar_1, Ar_2)) [ Ar_2 >= Ar_0 ] (Comp: ?, Cost: 1) evalrsdbb4in(Ar_0, Ar_1, Ar_2) -> Com_1(evalrsdreturnin(Ar_0, Ar_1, Ar_2)) [ Ar_0 >= Ar_2 + 1 ] (Comp: ?, Cost: 1) evalrsdbb1in(Ar_0, Ar_1, Ar_2) -> Com_1(evalrsdbb2in(Ar_0, Ar_1, Ar_2)) [ 0 >= D + 1 ] (Comp: ?, Cost: 1) evalrsdbb1in(Ar_0, Ar_1, Ar_2) -> Com_1(evalrsdbb2in(Ar_0, Ar_1, Ar_2)) [ D >= 1 ] (Comp: ?, Cost: 1) evalrsdbb1in(Ar_0, Ar_1, Ar_2) -> Com_1(evalrsdbb3in(Ar_0, Ar_1, Ar_2)) (Comp: ?, Cost: 1) evalrsdbb2in(Ar_0, Ar_1, Ar_2) -> Com_1(evalrsdbb4in(Ar_0, Ar_1, Ar_2 - 1)) (Comp: ?, Cost: 1) evalrsdbb3in(Ar_0, Ar_1, Ar_2) -> Com_1(evalrsdbb4in(Ar_0, Ar_1 - 1, Ar_1 - 1)) (Comp: ?, Cost: 1) evalrsdreturnin(Ar_0, Ar_1, Ar_2) -> Com_1(evalrsdstop(Ar_0, Ar_1, Ar_2)) (Comp: 1, Cost: 0) koat_start(Ar_0, Ar_1, Ar_2) -> Com_1(evalrsdstart(Ar_0, Ar_1, Ar_2)) [ 0 <= 0 ] start location: koat_start leaf cost: 0 A polynomial rank function with Pol(evalrsdstart) = 2 Pol(evalrsdentryin) = 2 Pol(evalrsdbbin) = 2 Pol(evalrsdreturnin) = 1 Pol(evalrsdbb4in) = 2 Pol(evalrsdbb1in) = 2 Pol(evalrsdbb2in) = 2 Pol(evalrsdbb3in) = 2 Pol(evalrsdstop) = 0 Pol(koat_start) = 2 orients all transitions weakly and the transitions evalrsdreturnin(Ar_0, Ar_1, Ar_2) -> Com_1(evalrsdstop(Ar_0, Ar_1, Ar_2)) evalrsdbb4in(Ar_0, Ar_1, Ar_2) -> Com_1(evalrsdreturnin(Ar_0, Ar_1, Ar_2)) [ Ar_0 >= Ar_2 + 1 ] strictly and produces the following problem: 3: T: (Comp: 1, Cost: 1) evalrsdstart(Ar_0, Ar_1, Ar_2) -> Com_1(evalrsdentryin(Ar_0, Ar_1, Ar_2)) (Comp: 1, Cost: 1) evalrsdentryin(Ar_0, Ar_1, Ar_2) -> Com_1(evalrsdbbin(Ar_0, Ar_1, Ar_2)) [ Ar_0 >= 0 ] (Comp: 1, Cost: 1) evalrsdentryin(Ar_0, Ar_1, Ar_2) -> Com_1(evalrsdreturnin(Ar_0, Ar_1, Ar_2)) [ 0 >= Ar_0 + 1 ] (Comp: 1, Cost: 1) evalrsdbbin(Ar_0, Ar_1, Ar_2) -> Com_1(evalrsdbb4in(Ar_0, 2*Ar_0, 2*Ar_0)) (Comp: ?, Cost: 1) evalrsdbb4in(Ar_0, Ar_1, Ar_2) -> Com_1(evalrsdbb1in(Ar_0, Ar_1, Ar_2)) [ Ar_2 >= Ar_0 ] (Comp: 2, Cost: 1) evalrsdbb4in(Ar_0, Ar_1, Ar_2) -> Com_1(evalrsdreturnin(Ar_0, Ar_1, Ar_2)) [ Ar_0 >= Ar_2 + 1 ] (Comp: ?, Cost: 1) evalrsdbb1in(Ar_0, Ar_1, Ar_2) -> Com_1(evalrsdbb2in(Ar_0, Ar_1, Ar_2)) [ 0 >= D + 1 ] (Comp: ?, Cost: 1) evalrsdbb1in(Ar_0, Ar_1, Ar_2) -> Com_1(evalrsdbb2in(Ar_0, Ar_1, Ar_2)) [ D >= 1 ] (Comp: ?, Cost: 1) evalrsdbb1in(Ar_0, Ar_1, Ar_2) -> Com_1(evalrsdbb3in(Ar_0, Ar_1, Ar_2)) (Comp: ?, Cost: 1) evalrsdbb2in(Ar_0, Ar_1, Ar_2) -> Com_1(evalrsdbb4in(Ar_0, Ar_1, Ar_2 - 1)) (Comp: ?, Cost: 1) evalrsdbb3in(Ar_0, Ar_1, Ar_2) -> Com_1(evalrsdbb4in(Ar_0, Ar_1 - 1, Ar_1 - 1)) (Comp: 2, Cost: 1) evalrsdreturnin(Ar_0, Ar_1, Ar_2) -> Com_1(evalrsdstop(Ar_0, Ar_1, Ar_2)) (Comp: 1, Cost: 0) koat_start(Ar_0, Ar_1, Ar_2) -> Com_1(evalrsdstart(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 evalrsdbb1in: X_3 >= 0 /\ X_1 + X_3 >= 0 /\ -X_1 + X_3 >= 0 /\ X_1 >= 0 For symbol evalrsdbb2in: X_3 >= 0 /\ X_1 + X_3 >= 0 /\ -X_1 + X_3 >= 0 /\ X_1 >= 0 For symbol evalrsdbb3in: X_3 >= 0 /\ X_1 + X_3 >= 0 /\ -X_1 + X_3 >= 0 /\ X_1 >= 0 For symbol evalrsdbb4in: X_1 >= 0 For symbol evalrsdbbin: X_1 >= 0 This yielded the following problem: 4: T: (Comp: 1, Cost: 0) koat_start(Ar_0, Ar_1, Ar_2) -> Com_1(evalrsdstart(Ar_0, Ar_1, Ar_2)) [ 0 <= 0 ] (Comp: 2, Cost: 1) evalrsdreturnin(Ar_0, Ar_1, Ar_2) -> Com_1(evalrsdstop(Ar_0, Ar_1, Ar_2)) (Comp: ?, Cost: 1) evalrsdbb3in(Ar_0, Ar_1, Ar_2) -> Com_1(evalrsdbb4in(Ar_0, Ar_1 - 1, Ar_1 - 1)) [ Ar_2 >= 0 /\ Ar_0 + Ar_2 >= 0 /\ -Ar_0 + Ar_2 >= 0 /\ Ar_0 >= 0 ] (Comp: ?, Cost: 1) evalrsdbb2in(Ar_0, Ar_1, Ar_2) -> Com_1(evalrsdbb4in(Ar_0, Ar_1, Ar_2 - 1)) [ Ar_2 >= 0 /\ Ar_0 + Ar_2 >= 0 /\ -Ar_0 + Ar_2 >= 0 /\ Ar_0 >= 0 ] (Comp: ?, Cost: 1) evalrsdbb1in(Ar_0, Ar_1, Ar_2) -> Com_1(evalrsdbb3in(Ar_0, Ar_1, Ar_2)) [ Ar_2 >= 0 /\ Ar_0 + Ar_2 >= 0 /\ -Ar_0 + Ar_2 >= 0 /\ Ar_0 >= 0 ] (Comp: ?, Cost: 1) evalrsdbb1in(Ar_0, Ar_1, Ar_2) -> Com_1(evalrsdbb2in(Ar_0, Ar_1, Ar_2)) [ Ar_2 >= 0 /\ Ar_0 + Ar_2 >= 0 /\ -Ar_0 + Ar_2 >= 0 /\ Ar_0 >= 0 /\ D >= 1 ] (Comp: ?, Cost: 1) evalrsdbb1in(Ar_0, Ar_1, Ar_2) -> Com_1(evalrsdbb2in(Ar_0, Ar_1, Ar_2)) [ Ar_2 >= 0 /\ Ar_0 + Ar_2 >= 0 /\ -Ar_0 + Ar_2 >= 0 /\ Ar_0 >= 0 /\ 0 >= D + 1 ] (Comp: 2, Cost: 1) evalrsdbb4in(Ar_0, Ar_1, Ar_2) -> Com_1(evalrsdreturnin(Ar_0, Ar_1, Ar_2)) [ Ar_0 >= 0 /\ Ar_0 >= Ar_2 + 1 ] (Comp: ?, Cost: 1) evalrsdbb4in(Ar_0, Ar_1, Ar_2) -> Com_1(evalrsdbb1in(Ar_0, Ar_1, Ar_2)) [ Ar_0 >= 0 /\ Ar_2 >= Ar_0 ] (Comp: 1, Cost: 1) evalrsdbbin(Ar_0, Ar_1, Ar_2) -> Com_1(evalrsdbb4in(Ar_0, 2*Ar_0, 2*Ar_0)) [ Ar_0 >= 0 ] (Comp: 1, Cost: 1) evalrsdentryin(Ar_0, Ar_1, Ar_2) -> Com_1(evalrsdreturnin(Ar_0, Ar_1, Ar_2)) [ 0 >= Ar_0 + 1 ] (Comp: 1, Cost: 1) evalrsdentryin(Ar_0, Ar_1, Ar_2) -> Com_1(evalrsdbbin(Ar_0, Ar_1, Ar_2)) [ Ar_0 >= 0 ] (Comp: 1, Cost: 1) evalrsdstart(Ar_0, Ar_1, Ar_2) -> Com_1(evalrsdentryin(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(evalrsdstart(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(evalrsdentryin(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(evalrsdentryin(Ar_0, Ar_1, Ar_2)) [ 0 <= 0 ] (Comp: 2, Cost: 1) evalrsdreturnin(Ar_0, Ar_1, Ar_2) -> Com_1(evalrsdstop(Ar_0, Ar_1, Ar_2)) (Comp: ?, Cost: 1) evalrsdbb3in(Ar_0, Ar_1, Ar_2) -> Com_1(evalrsdbb4in(Ar_0, Ar_1 - 1, Ar_1 - 1)) [ Ar_2 >= 0 /\ Ar_0 + Ar_2 >= 0 /\ -Ar_0 + Ar_2 >= 0 /\ Ar_0 >= 0 ] (Comp: ?, Cost: 1) evalrsdbb2in(Ar_0, Ar_1, Ar_2) -> Com_1(evalrsdbb4in(Ar_0, Ar_1, Ar_2 - 1)) [ Ar_2 >= 0 /\ Ar_0 + Ar_2 >= 0 /\ -Ar_0 + Ar_2 >= 0 /\ Ar_0 >= 0 ] (Comp: ?, Cost: 1) evalrsdbb1in(Ar_0, Ar_1, Ar_2) -> Com_1(evalrsdbb3in(Ar_0, Ar_1, Ar_2)) [ Ar_2 >= 0 /\ Ar_0 + Ar_2 >= 0 /\ -Ar_0 + Ar_2 >= 0 /\ Ar_0 >= 0 ] (Comp: ?, Cost: 1) evalrsdbb1in(Ar_0, Ar_1, Ar_2) -> Com_1(evalrsdbb2in(Ar_0, Ar_1, Ar_2)) [ Ar_2 >= 0 /\ Ar_0 + Ar_2 >= 0 /\ -Ar_0 + Ar_2 >= 0 /\ Ar_0 >= 0 /\ D >= 1 ] (Comp: ?, Cost: 1) evalrsdbb1in(Ar_0, Ar_1, Ar_2) -> Com_1(evalrsdbb2in(Ar_0, Ar_1, Ar_2)) [ Ar_2 >= 0 /\ Ar_0 + Ar_2 >= 0 /\ -Ar_0 + Ar_2 >= 0 /\ Ar_0 >= 0 /\ 0 >= D + 1 ] (Comp: 2, Cost: 1) evalrsdbb4in(Ar_0, Ar_1, Ar_2) -> Com_1(evalrsdreturnin(Ar_0, Ar_1, Ar_2)) [ Ar_0 >= 0 /\ Ar_0 >= Ar_2 + 1 ] (Comp: ?, Cost: 1) evalrsdbb4in(Ar_0, Ar_1, Ar_2) -> Com_1(evalrsdbb1in(Ar_0, Ar_1, Ar_2)) [ Ar_0 >= 0 /\ Ar_2 >= Ar_0 ] (Comp: 1, Cost: 1) evalrsdbbin(Ar_0, Ar_1, Ar_2) -> Com_1(evalrsdbb4in(Ar_0, 2*Ar_0, 2*Ar_0)) [ Ar_0 >= 0 ] (Comp: 1, Cost: 1) evalrsdentryin(Ar_0, Ar_1, Ar_2) -> Com_1(evalrsdreturnin(Ar_0, Ar_1, Ar_2)) [ 0 >= Ar_0 + 1 ] (Comp: 1, Cost: 1) evalrsdentryin(Ar_0, Ar_1, Ar_2) -> Com_1(evalrsdbbin(Ar_0, Ar_1, Ar_2)) [ Ar_0 >= 0 ] (Comp: 1, Cost: 1) evalrsdstart(Ar_0, Ar_1, Ar_2) -> Com_1(evalrsdentryin(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: evalrsdstart(Ar_0, Ar_1, Ar_2) -> Com_1(evalrsdentryin(Ar_0, Ar_1, Ar_2)) We thus obtain the following problem: 6: T: (Comp: 2, Cost: 1) evalrsdbb4in(Ar_0, Ar_1, Ar_2) -> Com_1(evalrsdreturnin(Ar_0, Ar_1, Ar_2)) [ Ar_0 >= 0 /\ Ar_0 >= Ar_2 + 1 ] (Comp: ?, Cost: 1) evalrsdbb2in(Ar_0, Ar_1, Ar_2) -> Com_1(evalrsdbb4in(Ar_0, Ar_1, Ar_2 - 1)) [ Ar_2 >= 0 /\ Ar_0 + Ar_2 >= 0 /\ -Ar_0 + Ar_2 >= 0 /\ Ar_0 >= 0 ] (Comp: ?, Cost: 1) evalrsdbb3in(Ar_0, Ar_1, Ar_2) -> Com_1(evalrsdbb4in(Ar_0, Ar_1 - 1, Ar_1 - 1)) [ Ar_2 >= 0 /\ Ar_0 + Ar_2 >= 0 /\ -Ar_0 + Ar_2 >= 0 /\ Ar_0 >= 0 ] (Comp: ?, Cost: 1) evalrsdbb1in(Ar_0, Ar_1, Ar_2) -> Com_1(evalrsdbb2in(Ar_0, Ar_1, Ar_2)) [ Ar_2 >= 0 /\ Ar_0 + Ar_2 >= 0 /\ -Ar_0 + Ar_2 >= 0 /\ Ar_0 >= 0 /\ 0 >= D + 1 ] (Comp: ?, Cost: 1) evalrsdbb1in(Ar_0, Ar_1, Ar_2) -> Com_1(evalrsdbb2in(Ar_0, Ar_1, Ar_2)) [ Ar_2 >= 0 /\ Ar_0 + Ar_2 >= 0 /\ -Ar_0 + Ar_2 >= 0 /\ Ar_0 >= 0 /\ D >= 1 ] (Comp: ?, Cost: 1) evalrsdbb1in(Ar_0, Ar_1, Ar_2) -> Com_1(evalrsdbb3in(Ar_0, Ar_1, Ar_2)) [ Ar_2 >= 0 /\ Ar_0 + Ar_2 >= 0 /\ -Ar_0 + Ar_2 >= 0 /\ Ar_0 >= 0 ] (Comp: ?, Cost: 1) evalrsdbb4in(Ar_0, Ar_1, Ar_2) -> Com_1(evalrsdbb1in(Ar_0, Ar_1, Ar_2)) [ Ar_0 >= 0 /\ Ar_2 >= Ar_0 ] (Comp: 1, Cost: 1) evalrsdbbin(Ar_0, Ar_1, Ar_2) -> Com_1(evalrsdbb4in(Ar_0, 2*Ar_0, 2*Ar_0)) [ Ar_0 >= 0 ] (Comp: 2, Cost: 1) evalrsdreturnin(Ar_0, Ar_1, Ar_2) -> Com_1(evalrsdstop(Ar_0, Ar_1, Ar_2)) (Comp: 1, Cost: 1) evalrsdentryin(Ar_0, Ar_1, Ar_2) -> Com_1(evalrsdbbin(Ar_0, Ar_1, Ar_2)) [ Ar_0 >= 0 ] (Comp: 1, Cost: 1) evalrsdentryin(Ar_0, Ar_1, Ar_2) -> Com_1(evalrsdreturnin(Ar_0, Ar_1, Ar_2)) [ 0 >= Ar_0 + 1 ] (Comp: 1, Cost: 1) koat_start(Ar_0, Ar_1, Ar_2) -> Com_1(evalrsdentryin(Ar_0, Ar_1, Ar_2)) [ 0 <= 0 ] start location: koat_start leaf cost: 0 By chaining the transition evalrsdbb4in(Ar_0, Ar_1, Ar_2) -> Com_1(evalrsdreturnin(Ar_0, Ar_1, Ar_2)) [ Ar_0 >= 0 /\ Ar_0 >= Ar_2 + 1 ] with all transitions in problem 6, the following new transition is obtained: evalrsdbb4in(Ar_0, Ar_1, Ar_2) -> Com_1(evalrsdstop(Ar_0, Ar_1, Ar_2)) [ Ar_0 >= 0 /\ Ar_0 >= Ar_2 + 1 ] We thus obtain the following problem: 7: T: (Comp: 2, Cost: 2) evalrsdbb4in(Ar_0, Ar_1, Ar_2) -> Com_1(evalrsdstop(Ar_0, Ar_1, Ar_2)) [ Ar_0 >= 0 /\ Ar_0 >= Ar_2 + 1 ] (Comp: ?, Cost: 1) evalrsdbb2in(Ar_0, Ar_1, Ar_2) -> Com_1(evalrsdbb4in(Ar_0, Ar_1, Ar_2 - 1)) [ Ar_2 >= 0 /\ Ar_0 + Ar_2 >= 0 /\ -Ar_0 + Ar_2 >= 0 /\ Ar_0 >= 0 ] (Comp: ?, Cost: 1) evalrsdbb3in(Ar_0, Ar_1, Ar_2) -> Com_1(evalrsdbb4in(Ar_0, Ar_1 - 1, Ar_1 - 1)) [ Ar_2 >= 0 /\ Ar_0 + Ar_2 >= 0 /\ -Ar_0 + Ar_2 >= 0 /\ Ar_0 >= 0 ] (Comp: ?, Cost: 1) evalrsdbb1in(Ar_0, Ar_1, Ar_2) -> Com_1(evalrsdbb2in(Ar_0, Ar_1, Ar_2)) [ Ar_2 >= 0 /\ Ar_0 + Ar_2 >= 0 /\ -Ar_0 + Ar_2 >= 0 /\ Ar_0 >= 0 /\ 0 >= D + 1 ] (Comp: ?, Cost: 1) evalrsdbb1in(Ar_0, Ar_1, Ar_2) -> Com_1(evalrsdbb2in(Ar_0, Ar_1, Ar_2)) [ Ar_2 >= 0 /\ Ar_0 + Ar_2 >= 0 /\ -Ar_0 + Ar_2 >= 0 /\ Ar_0 >= 0 /\ D >= 1 ] (Comp: ?, Cost: 1) evalrsdbb1in(Ar_0, Ar_1, Ar_2) -> Com_1(evalrsdbb3in(Ar_0, Ar_1, Ar_2)) [ Ar_2 >= 0 /\ Ar_0 + Ar_2 >= 0 /\ -Ar_0 + Ar_2 >= 0 /\ Ar_0 >= 0 ] (Comp: ?, Cost: 1) evalrsdbb4in(Ar_0, Ar_1, Ar_2) -> Com_1(evalrsdbb1in(Ar_0, Ar_1, Ar_2)) [ Ar_0 >= 0 /\ Ar_2 >= Ar_0 ] (Comp: 1, Cost: 1) evalrsdbbin(Ar_0, Ar_1, Ar_2) -> Com_1(evalrsdbb4in(Ar_0, 2*Ar_0, 2*Ar_0)) [ Ar_0 >= 0 ] (Comp: 2, Cost: 1) evalrsdreturnin(Ar_0, Ar_1, Ar_2) -> Com_1(evalrsdstop(Ar_0, Ar_1, Ar_2)) (Comp: 1, Cost: 1) evalrsdentryin(Ar_0, Ar_1, Ar_2) -> Com_1(evalrsdbbin(Ar_0, Ar_1, Ar_2)) [ Ar_0 >= 0 ] (Comp: 1, Cost: 1) evalrsdentryin(Ar_0, Ar_1, Ar_2) -> Com_1(evalrsdreturnin(Ar_0, Ar_1, Ar_2)) [ 0 >= Ar_0 + 1 ] (Comp: 1, Cost: 1) koat_start(Ar_0, Ar_1, Ar_2) -> Com_1(evalrsdentryin(Ar_0, Ar_1, Ar_2)) [ 0 <= 0 ] start location: koat_start leaf cost: 0 By chaining the transition evalrsdbb1in(Ar_0, Ar_1, Ar_2) -> Com_1(evalrsdbb2in(Ar_0, Ar_1, Ar_2)) [ Ar_2 >= 0 /\ Ar_0 + Ar_2 >= 0 /\ -Ar_0 + Ar_2 >= 0 /\ Ar_0 >= 0 /\ 0 >= D + 1 ] with all transitions in problem 7, the following new transition is obtained: evalrsdbb1in(Ar_0, Ar_1, Ar_2) -> Com_1(evalrsdbb4in(Ar_0, Ar_1, Ar_2 - 1)) [ Ar_2 >= 0 /\ Ar_0 + Ar_2 >= 0 /\ -Ar_0 + Ar_2 >= 0 /\ Ar_0 >= 0 /\ 0 >= D + 1 ] We thus obtain the following problem: 8: T: (Comp: ?, Cost: 2) evalrsdbb1in(Ar_0, Ar_1, Ar_2) -> Com_1(evalrsdbb4in(Ar_0, Ar_1, Ar_2 - 1)) [ Ar_2 >= 0 /\ Ar_0 + Ar_2 >= 0 /\ -Ar_0 + Ar_2 >= 0 /\ Ar_0 >= 0 /\ 0 >= D + 1 ] (Comp: 2, Cost: 2) evalrsdbb4in(Ar_0, Ar_1, Ar_2) -> Com_1(evalrsdstop(Ar_0, Ar_1, Ar_2)) [ Ar_0 >= 0 /\ Ar_0 >= Ar_2 + 1 ] (Comp: ?, Cost: 1) evalrsdbb2in(Ar_0, Ar_1, Ar_2) -> Com_1(evalrsdbb4in(Ar_0, Ar_1, Ar_2 - 1)) [ Ar_2 >= 0 /\ Ar_0 + Ar_2 >= 0 /\ -Ar_0 + Ar_2 >= 0 /\ Ar_0 >= 0 ] (Comp: ?, Cost: 1) evalrsdbb3in(Ar_0, Ar_1, Ar_2) -> Com_1(evalrsdbb4in(Ar_0, Ar_1 - 1, Ar_1 - 1)) [ Ar_2 >= 0 /\ Ar_0 + Ar_2 >= 0 /\ -Ar_0 + Ar_2 >= 0 /\ Ar_0 >= 0 ] (Comp: ?, Cost: 1) evalrsdbb1in(Ar_0, Ar_1, Ar_2) -> Com_1(evalrsdbb2in(Ar_0, Ar_1, Ar_2)) [ Ar_2 >= 0 /\ Ar_0 + Ar_2 >= 0 /\ -Ar_0 + Ar_2 >= 0 /\ Ar_0 >= 0 /\ D >= 1 ] (Comp: ?, Cost: 1) evalrsdbb1in(Ar_0, Ar_1, Ar_2) -> Com_1(evalrsdbb3in(Ar_0, Ar_1, Ar_2)) [ Ar_2 >= 0 /\ Ar_0 + Ar_2 >= 0 /\ -Ar_0 + Ar_2 >= 0 /\ Ar_0 >= 0 ] (Comp: ?, Cost: 1) evalrsdbb4in(Ar_0, Ar_1, Ar_2) -> Com_1(evalrsdbb1in(Ar_0, Ar_1, Ar_2)) [ Ar_0 >= 0 /\ Ar_2 >= Ar_0 ] (Comp: 1, Cost: 1) evalrsdbbin(Ar_0, Ar_1, Ar_2) -> Com_1(evalrsdbb4in(Ar_0, 2*Ar_0, 2*Ar_0)) [ Ar_0 >= 0 ] (Comp: 2, Cost: 1) evalrsdreturnin(Ar_0, Ar_1, Ar_2) -> Com_1(evalrsdstop(Ar_0, Ar_1, Ar_2)) (Comp: 1, Cost: 1) evalrsdentryin(Ar_0, Ar_1, Ar_2) -> Com_1(evalrsdbbin(Ar_0, Ar_1, Ar_2)) [ Ar_0 >= 0 ] (Comp: 1, Cost: 1) evalrsdentryin(Ar_0, Ar_1, Ar_2) -> Com_1(evalrsdreturnin(Ar_0, Ar_1, Ar_2)) [ 0 >= Ar_0 + 1 ] (Comp: 1, Cost: 1) koat_start(Ar_0, Ar_1, Ar_2) -> Com_1(evalrsdentryin(Ar_0, Ar_1, Ar_2)) [ 0 <= 0 ] start location: koat_start leaf cost: 0 By chaining the transition evalrsdbb1in(Ar_0, Ar_1, Ar_2) -> Com_1(evalrsdbb2in(Ar_0, Ar_1, Ar_2)) [ Ar_2 >= 0 /\ Ar_0 + Ar_2 >= 0 /\ -Ar_0 + Ar_2 >= 0 /\ Ar_0 >= 0 /\ D >= 1 ] with all transitions in problem 8, the following new transition is obtained: evalrsdbb1in(Ar_0, Ar_1, Ar_2) -> Com_1(evalrsdbb4in(Ar_0, Ar_1, Ar_2 - 1)) [ Ar_2 >= 0 /\ Ar_0 + Ar_2 >= 0 /\ -Ar_0 + Ar_2 >= 0 /\ Ar_0 >= 0 /\ D >= 1 ] We thus obtain the following problem: 9: T: (Comp: ?, Cost: 2) evalrsdbb1in(Ar_0, Ar_1, Ar_2) -> Com_1(evalrsdbb4in(Ar_0, Ar_1, Ar_2 - 1)) [ Ar_2 >= 0 /\ Ar_0 + Ar_2 >= 0 /\ -Ar_0 + Ar_2 >= 0 /\ Ar_0 >= 0 /\ D >= 1 ] (Comp: ?, Cost: 2) evalrsdbb1in(Ar_0, Ar_1, Ar_2) -> Com_1(evalrsdbb4in(Ar_0, Ar_1, Ar_2 - 1)) [ Ar_2 >= 0 /\ Ar_0 + Ar_2 >= 0 /\ -Ar_0 + Ar_2 >= 0 /\ Ar_0 >= 0 /\ 0 >= D + 1 ] (Comp: 2, Cost: 2) evalrsdbb4in(Ar_0, Ar_1, Ar_2) -> Com_1(evalrsdstop(Ar_0, Ar_1, Ar_2)) [ Ar_0 >= 0 /\ Ar_0 >= Ar_2 + 1 ] (Comp: ?, Cost: 1) evalrsdbb2in(Ar_0, Ar_1, Ar_2) -> Com_1(evalrsdbb4in(Ar_0, Ar_1, Ar_2 - 1)) [ Ar_2 >= 0 /\ Ar_0 + Ar_2 >= 0 /\ -Ar_0 + Ar_2 >= 0 /\ Ar_0 >= 0 ] (Comp: ?, Cost: 1) evalrsdbb3in(Ar_0, Ar_1, Ar_2) -> Com_1(evalrsdbb4in(Ar_0, Ar_1 - 1, Ar_1 - 1)) [ Ar_2 >= 0 /\ Ar_0 + Ar_2 >= 0 /\ -Ar_0 + Ar_2 >= 0 /\ Ar_0 >= 0 ] (Comp: ?, Cost: 1) evalrsdbb1in(Ar_0, Ar_1, Ar_2) -> Com_1(evalrsdbb3in(Ar_0, Ar_1, Ar_2)) [ Ar_2 >= 0 /\ Ar_0 + Ar_2 >= 0 /\ -Ar_0 + Ar_2 >= 0 /\ Ar_0 >= 0 ] (Comp: ?, Cost: 1) evalrsdbb4in(Ar_0, Ar_1, Ar_2) -> Com_1(evalrsdbb1in(Ar_0, Ar_1, Ar_2)) [ Ar_0 >= 0 /\ Ar_2 >= Ar_0 ] (Comp: 1, Cost: 1) evalrsdbbin(Ar_0, Ar_1, Ar_2) -> Com_1(evalrsdbb4in(Ar_0, 2*Ar_0, 2*Ar_0)) [ Ar_0 >= 0 ] (Comp: 2, Cost: 1) evalrsdreturnin(Ar_0, Ar_1, Ar_2) -> Com_1(evalrsdstop(Ar_0, Ar_1, Ar_2)) (Comp: 1, Cost: 1) evalrsdentryin(Ar_0, Ar_1, Ar_2) -> Com_1(evalrsdbbin(Ar_0, Ar_1, Ar_2)) [ Ar_0 >= 0 ] (Comp: 1, Cost: 1) evalrsdentryin(Ar_0, Ar_1, Ar_2) -> Com_1(evalrsdreturnin(Ar_0, Ar_1, Ar_2)) [ 0 >= Ar_0 + 1 ] (Comp: 1, Cost: 1) koat_start(Ar_0, Ar_1, Ar_2) -> Com_1(evalrsdentryin(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 9: evalrsdbb2in(Ar_0, Ar_1, Ar_2) -> Com_1(evalrsdbb4in(Ar_0, Ar_1, Ar_2 - 1)) [ Ar_2 >= 0 /\ Ar_0 + Ar_2 >= 0 /\ -Ar_0 + Ar_2 >= 0 /\ Ar_0 >= 0 ] We thus obtain the following problem: 10: T: (Comp: 2, Cost: 2) evalrsdbb4in(Ar_0, Ar_1, Ar_2) -> Com_1(evalrsdstop(Ar_0, Ar_1, Ar_2)) [ Ar_0 >= 0 /\ Ar_0 >= Ar_2 + 1 ] (Comp: ?, Cost: 1) evalrsdbb3in(Ar_0, Ar_1, Ar_2) -> Com_1(evalrsdbb4in(Ar_0, Ar_1 - 1, Ar_1 - 1)) [ Ar_2 >= 0 /\ Ar_0 + Ar_2 >= 0 /\ -Ar_0 + Ar_2 >= 0 /\ Ar_0 >= 0 ] (Comp: ?, Cost: 2) evalrsdbb1in(Ar_0, Ar_1, Ar_2) -> Com_1(evalrsdbb4in(Ar_0, Ar_1, Ar_2 - 1)) [ Ar_2 >= 0 /\ Ar_0 + Ar_2 >= 0 /\ -Ar_0 + Ar_2 >= 0 /\ Ar_0 >= 0 /\ D >= 1 ] (Comp: ?, Cost: 2) evalrsdbb1in(Ar_0, Ar_1, Ar_2) -> Com_1(evalrsdbb4in(Ar_0, Ar_1, Ar_2 - 1)) [ Ar_2 >= 0 /\ Ar_0 + Ar_2 >= 0 /\ -Ar_0 + Ar_2 >= 0 /\ Ar_0 >= 0 /\ 0 >= D + 1 ] (Comp: ?, Cost: 1) evalrsdbb1in(Ar_0, Ar_1, Ar_2) -> Com_1(evalrsdbb3in(Ar_0, Ar_1, Ar_2)) [ Ar_2 >= 0 /\ Ar_0 + Ar_2 >= 0 /\ -Ar_0 + Ar_2 >= 0 /\ Ar_0 >= 0 ] (Comp: ?, Cost: 1) evalrsdbb4in(Ar_0, Ar_1, Ar_2) -> Com_1(evalrsdbb1in(Ar_0, Ar_1, Ar_2)) [ Ar_0 >= 0 /\ Ar_2 >= Ar_0 ] (Comp: 1, Cost: 1) evalrsdbbin(Ar_0, Ar_1, Ar_2) -> Com_1(evalrsdbb4in(Ar_0, 2*Ar_0, 2*Ar_0)) [ Ar_0 >= 0 ] (Comp: 2, Cost: 1) evalrsdreturnin(Ar_0, Ar_1, Ar_2) -> Com_1(evalrsdstop(Ar_0, Ar_1, Ar_2)) (Comp: 1, Cost: 1) evalrsdentryin(Ar_0, Ar_1, Ar_2) -> Com_1(evalrsdbbin(Ar_0, Ar_1, Ar_2)) [ Ar_0 >= 0 ] (Comp: 1, Cost: 1) evalrsdentryin(Ar_0, Ar_1, Ar_2) -> Com_1(evalrsdreturnin(Ar_0, Ar_1, Ar_2)) [ 0 >= Ar_0 + 1 ] (Comp: 1, Cost: 1) koat_start(Ar_0, Ar_1, Ar_2) -> Com_1(evalrsdentryin(Ar_0, Ar_1, Ar_2)) [ 0 <= 0 ] start location: koat_start leaf cost: 0 By chaining the transition evalrsdbb1in(Ar_0, Ar_1, Ar_2) -> Com_1(evalrsdbb3in(Ar_0, Ar_1, Ar_2)) [ Ar_2 >= 0 /\ Ar_0 + Ar_2 >= 0 /\ -Ar_0 + Ar_2 >= 0 /\ Ar_0 >= 0 ] with all transitions in problem 10, the following new transition is obtained: evalrsdbb1in(Ar_0, Ar_1, Ar_2) -> Com_1(evalrsdbb4in(Ar_0, Ar_1 - 1, Ar_1 - 1)) [ Ar_2 >= 0 /\ Ar_0 + Ar_2 >= 0 /\ -Ar_0 + Ar_2 >= 0 /\ Ar_0 >= 0 ] We thus obtain the following problem: 11: T: (Comp: ?, Cost: 2) evalrsdbb1in(Ar_0, Ar_1, Ar_2) -> Com_1(evalrsdbb4in(Ar_0, Ar_1 - 1, Ar_1 - 1)) [ Ar_2 >= 0 /\ Ar_0 + Ar_2 >= 0 /\ -Ar_0 + Ar_2 >= 0 /\ Ar_0 >= 0 ] (Comp: 2, Cost: 2) evalrsdbb4in(Ar_0, Ar_1, Ar_2) -> Com_1(evalrsdstop(Ar_0, Ar_1, Ar_2)) [ Ar_0 >= 0 /\ Ar_0 >= Ar_2 + 1 ] (Comp: ?, Cost: 1) evalrsdbb3in(Ar_0, Ar_1, Ar_2) -> Com_1(evalrsdbb4in(Ar_0, Ar_1 - 1, Ar_1 - 1)) [ Ar_2 >= 0 /\ Ar_0 + Ar_2 >= 0 /\ -Ar_0 + Ar_2 >= 0 /\ Ar_0 >= 0 ] (Comp: ?, Cost: 2) evalrsdbb1in(Ar_0, Ar_1, Ar_2) -> Com_1(evalrsdbb4in(Ar_0, Ar_1, Ar_2 - 1)) [ Ar_2 >= 0 /\ Ar_0 + Ar_2 >= 0 /\ -Ar_0 + Ar_2 >= 0 /\ Ar_0 >= 0 /\ D >= 1 ] (Comp: ?, Cost: 2) evalrsdbb1in(Ar_0, Ar_1, Ar_2) -> Com_1(evalrsdbb4in(Ar_0, Ar_1, Ar_2 - 1)) [ Ar_2 >= 0 /\ Ar_0 + Ar_2 >= 0 /\ -Ar_0 + Ar_2 >= 0 /\ Ar_0 >= 0 /\ 0 >= D + 1 ] (Comp: ?, Cost: 1) evalrsdbb4in(Ar_0, Ar_1, Ar_2) -> Com_1(evalrsdbb1in(Ar_0, Ar_1, Ar_2)) [ Ar_0 >= 0 /\ Ar_2 >= Ar_0 ] (Comp: 1, Cost: 1) evalrsdbbin(Ar_0, Ar_1, Ar_2) -> Com_1(evalrsdbb4in(Ar_0, 2*Ar_0, 2*Ar_0)) [ Ar_0 >= 0 ] (Comp: 2, Cost: 1) evalrsdreturnin(Ar_0, Ar_1, Ar_2) -> Com_1(evalrsdstop(Ar_0, Ar_1, Ar_2)) (Comp: 1, Cost: 1) evalrsdentryin(Ar_0, Ar_1, Ar_2) -> Com_1(evalrsdbbin(Ar_0, Ar_1, Ar_2)) [ Ar_0 >= 0 ] (Comp: 1, Cost: 1) evalrsdentryin(Ar_0, Ar_1, Ar_2) -> Com_1(evalrsdreturnin(Ar_0, Ar_1, Ar_2)) [ 0 >= Ar_0 + 1 ] (Comp: 1, Cost: 1) koat_start(Ar_0, Ar_1, Ar_2) -> Com_1(evalrsdentryin(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 11: evalrsdbb3in(Ar_0, Ar_1, Ar_2) -> Com_1(evalrsdbb4in(Ar_0, Ar_1 - 1, Ar_1 - 1)) [ Ar_2 >= 0 /\ Ar_0 + Ar_2 >= 0 /\ -Ar_0 + Ar_2 >= 0 /\ Ar_0 >= 0 ] We thus obtain the following problem: 12: T: (Comp: 2, Cost: 2) evalrsdbb4in(Ar_0, Ar_1, Ar_2) -> Com_1(evalrsdstop(Ar_0, Ar_1, Ar_2)) [ Ar_0 >= 0 /\ Ar_0 >= Ar_2 + 1 ] (Comp: ?, Cost: 2) evalrsdbb1in(Ar_0, Ar_1, Ar_2) -> Com_1(evalrsdbb4in(Ar_0, Ar_1 - 1, Ar_1 - 1)) [ Ar_2 >= 0 /\ Ar_0 + Ar_2 >= 0 /\ -Ar_0 + Ar_2 >= 0 /\ Ar_0 >= 0 ] (Comp: ?, Cost: 2) evalrsdbb1in(Ar_0, Ar_1, Ar_2) -> Com_1(evalrsdbb4in(Ar_0, Ar_1, Ar_2 - 1)) [ Ar_2 >= 0 /\ Ar_0 + Ar_2 >= 0 /\ -Ar_0 + Ar_2 >= 0 /\ Ar_0 >= 0 /\ D >= 1 ] (Comp: ?, Cost: 2) evalrsdbb1in(Ar_0, Ar_1, Ar_2) -> Com_1(evalrsdbb4in(Ar_0, Ar_1, Ar_2 - 1)) [ Ar_2 >= 0 /\ Ar_0 + Ar_2 >= 0 /\ -Ar_0 + Ar_2 >= 0 /\ Ar_0 >= 0 /\ 0 >= D + 1 ] (Comp: ?, Cost: 1) evalrsdbb4in(Ar_0, Ar_1, Ar_2) -> Com_1(evalrsdbb1in(Ar_0, Ar_1, Ar_2)) [ Ar_0 >= 0 /\ Ar_2 >= Ar_0 ] (Comp: 1, Cost: 1) evalrsdbbin(Ar_0, Ar_1, Ar_2) -> Com_1(evalrsdbb4in(Ar_0, 2*Ar_0, 2*Ar_0)) [ Ar_0 >= 0 ] (Comp: 2, Cost: 1) evalrsdreturnin(Ar_0, Ar_1, Ar_2) -> Com_1(evalrsdstop(Ar_0, Ar_1, Ar_2)) (Comp: 1, Cost: 1) evalrsdentryin(Ar_0, Ar_1, Ar_2) -> Com_1(evalrsdbbin(Ar_0, Ar_1, Ar_2)) [ Ar_0 >= 0 ] (Comp: 1, Cost: 1) evalrsdentryin(Ar_0, Ar_1, Ar_2) -> Com_1(evalrsdreturnin(Ar_0, Ar_1, Ar_2)) [ 0 >= Ar_0 + 1 ] (Comp: 1, Cost: 1) koat_start(Ar_0, Ar_1, Ar_2) -> Com_1(evalrsdentryin(Ar_0, Ar_1, Ar_2)) [ 0 <= 0 ] start location: koat_start leaf cost: 0 By chaining the transition evalrsdbbin(Ar_0, Ar_1, Ar_2) -> Com_1(evalrsdbb4in(Ar_0, 2*Ar_0, 2*Ar_0)) [ Ar_0 >= 0 ] with all transitions in problem 12, the following new transition is obtained: evalrsdbbin(Ar_0, Ar_1, Ar_2) -> Com_1(evalrsdbb1in(Ar_0, 2*Ar_0, 2*Ar_0)) [ Ar_0 >= 0 /\ 2*Ar_0 >= Ar_0 ] We thus obtain the following problem: 13: T: (Comp: 1, Cost: 2) evalrsdbbin(Ar_0, Ar_1, Ar_2) -> Com_1(evalrsdbb1in(Ar_0, 2*Ar_0, 2*Ar_0)) [ Ar_0 >= 0 /\ 2*Ar_0 >= Ar_0 ] (Comp: 2, Cost: 2) evalrsdbb4in(Ar_0, Ar_1, Ar_2) -> Com_1(evalrsdstop(Ar_0, Ar_1, Ar_2)) [ Ar_0 >= 0 /\ Ar_0 >= Ar_2 + 1 ] (Comp: ?, Cost: 2) evalrsdbb1in(Ar_0, Ar_1, Ar_2) -> Com_1(evalrsdbb4in(Ar_0, Ar_1 - 1, Ar_1 - 1)) [ Ar_2 >= 0 /\ Ar_0 + Ar_2 >= 0 /\ -Ar_0 + Ar_2 >= 0 /\ Ar_0 >= 0 ] (Comp: ?, Cost: 2) evalrsdbb1in(Ar_0, Ar_1, Ar_2) -> Com_1(evalrsdbb4in(Ar_0, Ar_1, Ar_2 - 1)) [ Ar_2 >= 0 /\ Ar_0 + Ar_2 >= 0 /\ -Ar_0 + Ar_2 >= 0 /\ Ar_0 >= 0 /\ D >= 1 ] (Comp: ?, Cost: 2) evalrsdbb1in(Ar_0, Ar_1, Ar_2) -> Com_1(evalrsdbb4in(Ar_0, Ar_1, Ar_2 - 1)) [ Ar_2 >= 0 /\ Ar_0 + Ar_2 >= 0 /\ -Ar_0 + Ar_2 >= 0 /\ Ar_0 >= 0 /\ 0 >= D + 1 ] (Comp: ?, Cost: 1) evalrsdbb4in(Ar_0, Ar_1, Ar_2) -> Com_1(evalrsdbb1in(Ar_0, Ar_1, Ar_2)) [ Ar_0 >= 0 /\ Ar_2 >= Ar_0 ] (Comp: 2, Cost: 1) evalrsdreturnin(Ar_0, Ar_1, Ar_2) -> Com_1(evalrsdstop(Ar_0, Ar_1, Ar_2)) (Comp: 1, Cost: 1) evalrsdentryin(Ar_0, Ar_1, Ar_2) -> Com_1(evalrsdbbin(Ar_0, Ar_1, Ar_2)) [ Ar_0 >= 0 ] (Comp: 1, Cost: 1) evalrsdentryin(Ar_0, Ar_1, Ar_2) -> Com_1(evalrsdreturnin(Ar_0, Ar_1, Ar_2)) [ 0 >= Ar_0 + 1 ] (Comp: 1, Cost: 1) koat_start(Ar_0, Ar_1, Ar_2) -> Com_1(evalrsdentryin(Ar_0, Ar_1, Ar_2)) [ 0 <= 0 ] start location: koat_start leaf cost: 0 By chaining the transition evalrsdentryin(Ar_0, Ar_1, Ar_2) -> Com_1(evalrsdbbin(Ar_0, Ar_1, Ar_2)) [ Ar_0 >= 0 ] with all transitions in problem 13, the following new transition is obtained: evalrsdentryin(Ar_0, Ar_1, Ar_2) -> Com_1(evalrsdbb1in(Ar_0, 2*Ar_0, 2*Ar_0)) [ Ar_0 >= 0 /\ 2*Ar_0 >= Ar_0 ] We thus obtain the following problem: 14: T: (Comp: 1, Cost: 3) evalrsdentryin(Ar_0, Ar_1, Ar_2) -> Com_1(evalrsdbb1in(Ar_0, 2*Ar_0, 2*Ar_0)) [ Ar_0 >= 0 /\ 2*Ar_0 >= Ar_0 ] (Comp: 1, Cost: 2) evalrsdbbin(Ar_0, Ar_1, Ar_2) -> Com_1(evalrsdbb1in(Ar_0, 2*Ar_0, 2*Ar_0)) [ Ar_0 >= 0 /\ 2*Ar_0 >= Ar_0 ] (Comp: 2, Cost: 2) evalrsdbb4in(Ar_0, Ar_1, Ar_2) -> Com_1(evalrsdstop(Ar_0, Ar_1, Ar_2)) [ Ar_0 >= 0 /\ Ar_0 >= Ar_2 + 1 ] (Comp: ?, Cost: 2) evalrsdbb1in(Ar_0, Ar_1, Ar_2) -> Com_1(evalrsdbb4in(Ar_0, Ar_1 - 1, Ar_1 - 1)) [ Ar_2 >= 0 /\ Ar_0 + Ar_2 >= 0 /\ -Ar_0 + Ar_2 >= 0 /\ Ar_0 >= 0 ] (Comp: ?, Cost: 2) evalrsdbb1in(Ar_0, Ar_1, Ar_2) -> Com_1(evalrsdbb4in(Ar_0, Ar_1, Ar_2 - 1)) [ Ar_2 >= 0 /\ Ar_0 + Ar_2 >= 0 /\ -Ar_0 + Ar_2 >= 0 /\ Ar_0 >= 0 /\ D >= 1 ] (Comp: ?, Cost: 2) evalrsdbb1in(Ar_0, Ar_1, Ar_2) -> Com_1(evalrsdbb4in(Ar_0, Ar_1, Ar_2 - 1)) [ Ar_2 >= 0 /\ Ar_0 + Ar_2 >= 0 /\ -Ar_0 + Ar_2 >= 0 /\ Ar_0 >= 0 /\ 0 >= D + 1 ] (Comp: ?, Cost: 1) evalrsdbb4in(Ar_0, Ar_1, Ar_2) -> Com_1(evalrsdbb1in(Ar_0, Ar_1, Ar_2)) [ Ar_0 >= 0 /\ Ar_2 >= Ar_0 ] (Comp: 2, Cost: 1) evalrsdreturnin(Ar_0, Ar_1, Ar_2) -> Com_1(evalrsdstop(Ar_0, Ar_1, Ar_2)) (Comp: 1, Cost: 1) evalrsdentryin(Ar_0, Ar_1, Ar_2) -> Com_1(evalrsdreturnin(Ar_0, Ar_1, Ar_2)) [ 0 >= Ar_0 + 1 ] (Comp: 1, Cost: 1) koat_start(Ar_0, Ar_1, Ar_2) -> Com_1(evalrsdentryin(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 14: evalrsdbbin(Ar_0, Ar_1, Ar_2) -> Com_1(evalrsdbb1in(Ar_0, 2*Ar_0, 2*Ar_0)) [ Ar_0 >= 0 /\ 2*Ar_0 >= Ar_0 ] We thus obtain the following problem: 15: T: (Comp: 2, Cost: 2) evalrsdbb4in(Ar_0, Ar_1, Ar_2) -> Com_1(evalrsdstop(Ar_0, Ar_1, Ar_2)) [ Ar_0 >= 0 /\ Ar_0 >= Ar_2 + 1 ] (Comp: ?, Cost: 1) evalrsdbb4in(Ar_0, Ar_1, Ar_2) -> Com_1(evalrsdbb1in(Ar_0, Ar_1, Ar_2)) [ Ar_0 >= 0 /\ Ar_2 >= Ar_0 ] (Comp: ?, Cost: 2) evalrsdbb1in(Ar_0, Ar_1, Ar_2) -> Com_1(evalrsdbb4in(Ar_0, Ar_1 - 1, Ar_1 - 1)) [ Ar_2 >= 0 /\ Ar_0 + Ar_2 >= 0 /\ -Ar_0 + Ar_2 >= 0 /\ Ar_0 >= 0 ] (Comp: ?, Cost: 2) evalrsdbb1in(Ar_0, Ar_1, Ar_2) -> Com_1(evalrsdbb4in(Ar_0, Ar_1, Ar_2 - 1)) [ Ar_2 >= 0 /\ Ar_0 + Ar_2 >= 0 /\ -Ar_0 + Ar_2 >= 0 /\ Ar_0 >= 0 /\ D >= 1 ] (Comp: ?, Cost: 2) evalrsdbb1in(Ar_0, Ar_1, Ar_2) -> Com_1(evalrsdbb4in(Ar_0, Ar_1, Ar_2 - 1)) [ Ar_2 >= 0 /\ Ar_0 + Ar_2 >= 0 /\ -Ar_0 + Ar_2 >= 0 /\ Ar_0 >= 0 /\ 0 >= D + 1 ] (Comp: 2, Cost: 1) evalrsdreturnin(Ar_0, Ar_1, Ar_2) -> Com_1(evalrsdstop(Ar_0, Ar_1, Ar_2)) (Comp: 1, Cost: 3) evalrsdentryin(Ar_0, Ar_1, Ar_2) -> Com_1(evalrsdbb1in(Ar_0, 2*Ar_0, 2*Ar_0)) [ Ar_0 >= 0 /\ 2*Ar_0 >= Ar_0 ] (Comp: 1, Cost: 1) evalrsdentryin(Ar_0, Ar_1, Ar_2) -> Com_1(evalrsdreturnin(Ar_0, Ar_1, Ar_2)) [ 0 >= Ar_0 + 1 ] (Comp: 1, Cost: 1) koat_start(Ar_0, Ar_1, Ar_2) -> Com_1(evalrsdentryin(Ar_0, Ar_1, Ar_2)) [ 0 <= 0 ] start location: koat_start leaf cost: 0 By chaining the transition evalrsdentryin(Ar_0, Ar_1, Ar_2) -> Com_1(evalrsdreturnin(Ar_0, Ar_1, Ar_2)) [ 0 >= Ar_0 + 1 ] with all transitions in problem 15, the following new transition is obtained: evalrsdentryin(Ar_0, Ar_1, Ar_2) -> Com_1(evalrsdstop(Ar_0, Ar_1, Ar_2)) [ 0 >= Ar_0 + 1 ] We thus obtain the following problem: 16: T: (Comp: 1, Cost: 2) evalrsdentryin(Ar_0, Ar_1, Ar_2) -> Com_1(evalrsdstop(Ar_0, Ar_1, Ar_2)) [ 0 >= Ar_0 + 1 ] (Comp: 2, Cost: 2) evalrsdbb4in(Ar_0, Ar_1, Ar_2) -> Com_1(evalrsdstop(Ar_0, Ar_1, Ar_2)) [ Ar_0 >= 0 /\ Ar_0 >= Ar_2 + 1 ] (Comp: ?, Cost: 1) evalrsdbb4in(Ar_0, Ar_1, Ar_2) -> Com_1(evalrsdbb1in(Ar_0, Ar_1, Ar_2)) [ Ar_0 >= 0 /\ Ar_2 >= Ar_0 ] (Comp: ?, Cost: 2) evalrsdbb1in(Ar_0, Ar_1, Ar_2) -> Com_1(evalrsdbb4in(Ar_0, Ar_1 - 1, Ar_1 - 1)) [ Ar_2 >= 0 /\ Ar_0 + Ar_2 >= 0 /\ -Ar_0 + Ar_2 >= 0 /\ Ar_0 >= 0 ] (Comp: ?, Cost: 2) evalrsdbb1in(Ar_0, Ar_1, Ar_2) -> Com_1(evalrsdbb4in(Ar_0, Ar_1, Ar_2 - 1)) [ Ar_2 >= 0 /\ Ar_0 + Ar_2 >= 0 /\ -Ar_0 + Ar_2 >= 0 /\ Ar_0 >= 0 /\ D >= 1 ] (Comp: ?, Cost: 2) evalrsdbb1in(Ar_0, Ar_1, Ar_2) -> Com_1(evalrsdbb4in(Ar_0, Ar_1, Ar_2 - 1)) [ Ar_2 >= 0 /\ Ar_0 + Ar_2 >= 0 /\ -Ar_0 + Ar_2 >= 0 /\ Ar_0 >= 0 /\ 0 >= D + 1 ] (Comp: 2, Cost: 1) evalrsdreturnin(Ar_0, Ar_1, Ar_2) -> Com_1(evalrsdstop(Ar_0, Ar_1, Ar_2)) (Comp: 1, Cost: 3) evalrsdentryin(Ar_0, Ar_1, Ar_2) -> Com_1(evalrsdbb1in(Ar_0, 2*Ar_0, 2*Ar_0)) [ Ar_0 >= 0 /\ 2*Ar_0 >= Ar_0 ] (Comp: 1, Cost: 1) koat_start(Ar_0, Ar_1, Ar_2) -> Com_1(evalrsdentryin(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 16: evalrsdreturnin(Ar_0, Ar_1, Ar_2) -> Com_1(evalrsdstop(Ar_0, Ar_1, Ar_2)) We thus obtain the following problem: 17: T: (Comp: 2, Cost: 2) evalrsdbb4in(Ar_0, Ar_1, Ar_2) -> Com_1(evalrsdstop(Ar_0, Ar_1, Ar_2)) [ Ar_0 >= 0 /\ Ar_0 >= Ar_2 + 1 ] (Comp: ?, Cost: 1) evalrsdbb4in(Ar_0, Ar_1, Ar_2) -> Com_1(evalrsdbb1in(Ar_0, Ar_1, Ar_2)) [ Ar_0 >= 0 /\ Ar_2 >= Ar_0 ] (Comp: ?, Cost: 2) evalrsdbb1in(Ar_0, Ar_1, Ar_2) -> Com_1(evalrsdbb4in(Ar_0, Ar_1 - 1, Ar_1 - 1)) [ Ar_2 >= 0 /\ Ar_0 + Ar_2 >= 0 /\ -Ar_0 + Ar_2 >= 0 /\ Ar_0 >= 0 ] (Comp: ?, Cost: 2) evalrsdbb1in(Ar_0, Ar_1, Ar_2) -> Com_1(evalrsdbb4in(Ar_0, Ar_1, Ar_2 - 1)) [ Ar_2 >= 0 /\ Ar_0 + Ar_2 >= 0 /\ -Ar_0 + Ar_2 >= 0 /\ Ar_0 >= 0 /\ D >= 1 ] (Comp: ?, Cost: 2) evalrsdbb1in(Ar_0, Ar_1, Ar_2) -> Com_1(evalrsdbb4in(Ar_0, Ar_1, Ar_2 - 1)) [ Ar_2 >= 0 /\ Ar_0 + Ar_2 >= 0 /\ -Ar_0 + Ar_2 >= 0 /\ Ar_0 >= 0 /\ 0 >= D + 1 ] (Comp: 1, Cost: 2) evalrsdentryin(Ar_0, Ar_1, Ar_2) -> Com_1(evalrsdstop(Ar_0, Ar_1, Ar_2)) [ 0 >= Ar_0 + 1 ] (Comp: 1, Cost: 3) evalrsdentryin(Ar_0, Ar_1, Ar_2) -> Com_1(evalrsdbb1in(Ar_0, 2*Ar_0, 2*Ar_0)) [ Ar_0 >= 0 /\ 2*Ar_0 >= Ar_0 ] (Comp: 1, Cost: 1) koat_start(Ar_0, Ar_1, Ar_2) -> Com_1(evalrsdentryin(Ar_0, Ar_1, Ar_2)) [ 0 <= 0 ] start location: koat_start leaf cost: 0 By chaining the transition evalrsdbb1in(Ar_0, Ar_1, Ar_2) -> Com_1(evalrsdbb4in(Ar_0, Ar_1 - 1, Ar_1 - 1)) [ Ar_2 >= 0 /\ Ar_0 + Ar_2 >= 0 /\ -Ar_0 + Ar_2 >= 0 /\ Ar_0 >= 0 ] with all transitions in problem 17, the following new transitions are obtained: evalrsdbb1in(Ar_0, Ar_1, Ar_2) -> Com_1(evalrsdstop(Ar_0, Ar_1 - 1, Ar_1 - 1)) [ Ar_2 >= 0 /\ Ar_0 + Ar_2 >= 0 /\ -Ar_0 + Ar_2 >= 0 /\ Ar_0 >= 0 /\ Ar_0 >= Ar_1 ] evalrsdbb1in(Ar_0, Ar_1, Ar_2) -> Com_1(evalrsdbb1in(Ar_0, Ar_1 - 1, Ar_1 - 1)) [ Ar_2 >= 0 /\ Ar_0 + Ar_2 >= 0 /\ -Ar_0 + Ar_2 >= 0 /\ Ar_0 >= 0 /\ Ar_1 - 1 >= Ar_0 ] We thus obtain the following problem: 18: T: (Comp: ?, Cost: 4) evalrsdbb1in(Ar_0, Ar_1, Ar_2) -> Com_1(evalrsdstop(Ar_0, Ar_1 - 1, Ar_1 - 1)) [ Ar_2 >= 0 /\ Ar_0 + Ar_2 >= 0 /\ -Ar_0 + Ar_2 >= 0 /\ Ar_0 >= 0 /\ Ar_0 >= Ar_1 ] (Comp: ?, Cost: 3) evalrsdbb1in(Ar_0, Ar_1, Ar_2) -> Com_1(evalrsdbb1in(Ar_0, Ar_1 - 1, Ar_1 - 1)) [ Ar_2 >= 0 /\ Ar_0 + Ar_2 >= 0 /\ -Ar_0 + Ar_2 >= 0 /\ Ar_0 >= 0 /\ Ar_1 - 1 >= Ar_0 ] (Comp: 2, Cost: 2) evalrsdbb4in(Ar_0, Ar_1, Ar_2) -> Com_1(evalrsdstop(Ar_0, Ar_1, Ar_2)) [ Ar_0 >= 0 /\ Ar_0 >= Ar_2 + 1 ] (Comp: ?, Cost: 1) evalrsdbb4in(Ar_0, Ar_1, Ar_2) -> Com_1(evalrsdbb1in(Ar_0, Ar_1, Ar_2)) [ Ar_0 >= 0 /\ Ar_2 >= Ar_0 ] (Comp: ?, Cost: 2) evalrsdbb1in(Ar_0, Ar_1, Ar_2) -> Com_1(evalrsdbb4in(Ar_0, Ar_1, Ar_2 - 1)) [ Ar_2 >= 0 /\ Ar_0 + Ar_2 >= 0 /\ -Ar_0 + Ar_2 >= 0 /\ Ar_0 >= 0 /\ D >= 1 ] (Comp: ?, Cost: 2) evalrsdbb1in(Ar_0, Ar_1, Ar_2) -> Com_1(evalrsdbb4in(Ar_0, Ar_1, Ar_2 - 1)) [ Ar_2 >= 0 /\ Ar_0 + Ar_2 >= 0 /\ -Ar_0 + Ar_2 >= 0 /\ Ar_0 >= 0 /\ 0 >= D + 1 ] (Comp: 1, Cost: 2) evalrsdentryin(Ar_0, Ar_1, Ar_2) -> Com_1(evalrsdstop(Ar_0, Ar_1, Ar_2)) [ 0 >= Ar_0 + 1 ] (Comp: 1, Cost: 3) evalrsdentryin(Ar_0, Ar_1, Ar_2) -> Com_1(evalrsdbb1in(Ar_0, 2*Ar_0, 2*Ar_0)) [ Ar_0 >= 0 /\ 2*Ar_0 >= Ar_0 ] (Comp: 1, Cost: 1) koat_start(Ar_0, Ar_1, Ar_2) -> Com_1(evalrsdentryin(Ar_0, Ar_1, Ar_2)) [ 0 <= 0 ] start location: koat_start leaf cost: 0 A polynomial rank function with Pol(evalrsdbb1in) = 1 Pol(evalrsdstop) = 0 Pol(evalrsdbb4in) = 1 Pol(evalrsdentryin) = 1 Pol(koat_start) = 1 orients all transitions weakly and the transition evalrsdbb1in(Ar_0, Ar_1, Ar_2) -> Com_1(evalrsdstop(Ar_0, Ar_1 - 1, Ar_1 - 1)) [ Ar_2 >= 0 /\ Ar_0 + Ar_2 >= 0 /\ -Ar_0 + Ar_2 >= 0 /\ Ar_0 >= 0 /\ Ar_0 >= Ar_1 ] strictly and produces the following problem: 19: T: (Comp: 1, Cost: 4) evalrsdbb1in(Ar_0, Ar_1, Ar_2) -> Com_1(evalrsdstop(Ar_0, Ar_1 - 1, Ar_1 - 1)) [ Ar_2 >= 0 /\ Ar_0 + Ar_2 >= 0 /\ -Ar_0 + Ar_2 >= 0 /\ Ar_0 >= 0 /\ Ar_0 >= Ar_1 ] (Comp: ?, Cost: 3) evalrsdbb1in(Ar_0, Ar_1, Ar_2) -> Com_1(evalrsdbb1in(Ar_0, Ar_1 - 1, Ar_1 - 1)) [ Ar_2 >= 0 /\ Ar_0 + Ar_2 >= 0 /\ -Ar_0 + Ar_2 >= 0 /\ Ar_0 >= 0 /\ Ar_1 - 1 >= Ar_0 ] (Comp: 2, Cost: 2) evalrsdbb4in(Ar_0, Ar_1, Ar_2) -> Com_1(evalrsdstop(Ar_0, Ar_1, Ar_2)) [ Ar_0 >= 0 /\ Ar_0 >= Ar_2 + 1 ] (Comp: ?, Cost: 1) evalrsdbb4in(Ar_0, Ar_1, Ar_2) -> Com_1(evalrsdbb1in(Ar_0, Ar_1, Ar_2)) [ Ar_0 >= 0 /\ Ar_2 >= Ar_0 ] (Comp: ?, Cost: 2) evalrsdbb1in(Ar_0, Ar_1, Ar_2) -> Com_1(evalrsdbb4in(Ar_0, Ar_1, Ar_2 - 1)) [ Ar_2 >= 0 /\ Ar_0 + Ar_2 >= 0 /\ -Ar_0 + Ar_2 >= 0 /\ Ar_0 >= 0 /\ D >= 1 ] (Comp: ?, Cost: 2) evalrsdbb1in(Ar_0, Ar_1, Ar_2) -> Com_1(evalrsdbb4in(Ar_0, Ar_1, Ar_2 - 1)) [ Ar_2 >= 0 /\ Ar_0 + Ar_2 >= 0 /\ -Ar_0 + Ar_2 >= 0 /\ Ar_0 >= 0 /\ 0 >= D + 1 ] (Comp: 1, Cost: 2) evalrsdentryin(Ar_0, Ar_1, Ar_2) -> Com_1(evalrsdstop(Ar_0, Ar_1, Ar_2)) [ 0 >= Ar_0 + 1 ] (Comp: 1, Cost: 3) evalrsdentryin(Ar_0, Ar_1, Ar_2) -> Com_1(evalrsdbb1in(Ar_0, 2*Ar_0, 2*Ar_0)) [ Ar_0 >= 0 /\ 2*Ar_0 >= Ar_0 ] (Comp: 1, Cost: 1) koat_start(Ar_0, Ar_1, Ar_2) -> Com_1(evalrsdentryin(Ar_0, Ar_1, Ar_2)) [ 0 <= 0 ] start location: koat_start leaf cost: 0 A polynomial rank function with Pol(evalrsdbb4in) = V_2 Pol(evalrsdbb1in) = V_2 and size complexities S("koat_start(Ar_0, Ar_1, Ar_2) -> Com_1(evalrsdentryin(Ar_0, Ar_1, Ar_2)) [ 0 <= 0 ]", 0-0) = Ar_0 S("koat_start(Ar_0, Ar_1, Ar_2) -> Com_1(evalrsdentryin(Ar_0, Ar_1, Ar_2)) [ 0 <= 0 ]", 0-1) = Ar_1 S("koat_start(Ar_0, Ar_1, Ar_2) -> Com_1(evalrsdentryin(Ar_0, Ar_1, Ar_2)) [ 0 <= 0 ]", 0-2) = Ar_2 S("evalrsdentryin(Ar_0, Ar_1, Ar_2) -> Com_1(evalrsdbb1in(Ar_0, 2*Ar_0, 2*Ar_0)) [ Ar_0 >= 0 /\\ 2*Ar_0 >= Ar_0 ]", 0-0) = Ar_0 S("evalrsdentryin(Ar_0, Ar_1, Ar_2) -> Com_1(evalrsdbb1in(Ar_0, 2*Ar_0, 2*Ar_0)) [ Ar_0 >= 0 /\\ 2*Ar_0 >= Ar_0 ]", 0-1) = 2*Ar_0 S("evalrsdentryin(Ar_0, Ar_1, Ar_2) -> Com_1(evalrsdbb1in(Ar_0, 2*Ar_0, 2*Ar_0)) [ Ar_0 >= 0 /\\ 2*Ar_0 >= Ar_0 ]", 0-2) = 2*Ar_0 S("evalrsdentryin(Ar_0, Ar_1, Ar_2) -> Com_1(evalrsdstop(Ar_0, Ar_1, Ar_2)) [ 0 >= Ar_0 + 1 ]", 0-0) = Ar_0 S("evalrsdentryin(Ar_0, Ar_1, Ar_2) -> Com_1(evalrsdstop(Ar_0, Ar_1, Ar_2)) [ 0 >= Ar_0 + 1 ]", 0-1) = Ar_1 S("evalrsdentryin(Ar_0, Ar_1, Ar_2) -> Com_1(evalrsdstop(Ar_0, Ar_1, Ar_2)) [ 0 >= Ar_0 + 1 ]", 0-2) = Ar_2 S("evalrsdbb1in(Ar_0, Ar_1, Ar_2) -> Com_1(evalrsdbb4in(Ar_0, Ar_1, Ar_2 - 1)) [ Ar_2 >= 0 /\\ Ar_0 + Ar_2 >= 0 /\\ -Ar_0 + Ar_2 >= 0 /\\ Ar_0 >= 0 /\\ 0 >= D + 1 ]", 0-0) = Ar_0 S("evalrsdbb1in(Ar_0, Ar_1, Ar_2) -> Com_1(evalrsdbb4in(Ar_0, Ar_1, Ar_2 - 1)) [ Ar_2 >= 0 /\\ Ar_0 + Ar_2 >= 0 /\\ -Ar_0 + Ar_2 >= 0 /\\ Ar_0 >= 0 /\\ 0 >= D + 1 ]", 0-1) = 2*Ar_0 S("evalrsdbb1in(Ar_0, Ar_1, Ar_2) -> Com_1(evalrsdbb4in(Ar_0, Ar_1, Ar_2 - 1)) [ Ar_2 >= 0 /\\ Ar_0 + Ar_2 >= 0 /\\ -Ar_0 + Ar_2 >= 0 /\\ Ar_0 >= 0 /\\ 0 >= D + 1 ]", 0-2) = 2*Ar_0 + 8 S("evalrsdbb1in(Ar_0, Ar_1, Ar_2) -> Com_1(evalrsdbb4in(Ar_0, Ar_1, Ar_2 - 1)) [ Ar_2 >= 0 /\\ Ar_0 + Ar_2 >= 0 /\\ -Ar_0 + Ar_2 >= 0 /\\ Ar_0 >= 0 /\\ D >= 1 ]", 0-0) = Ar_0 S("evalrsdbb1in(Ar_0, Ar_1, Ar_2) -> Com_1(evalrsdbb4in(Ar_0, Ar_1, Ar_2 - 1)) [ Ar_2 >= 0 /\\ Ar_0 + Ar_2 >= 0 /\\ -Ar_0 + Ar_2 >= 0 /\\ Ar_0 >= 0 /\\ D >= 1 ]", 0-1) = 2*Ar_0 S("evalrsdbb1in(Ar_0, Ar_1, Ar_2) -> Com_1(evalrsdbb4in(Ar_0, Ar_1, Ar_2 - 1)) [ Ar_2 >= 0 /\\ Ar_0 + Ar_2 >= 0 /\\ -Ar_0 + Ar_2 >= 0 /\\ Ar_0 >= 0 /\\ D >= 1 ]", 0-2) = 2*Ar_0 + 8 S("evalrsdbb4in(Ar_0, Ar_1, Ar_2) -> Com_1(evalrsdbb1in(Ar_0, Ar_1, Ar_2)) [ Ar_0 >= 0 /\\ Ar_2 >= Ar_0 ]", 0-0) = Ar_0 S("evalrsdbb4in(Ar_0, Ar_1, Ar_2) -> Com_1(evalrsdbb1in(Ar_0, Ar_1, Ar_2)) [ Ar_0 >= 0 /\\ Ar_2 >= Ar_0 ]", 0-1) = 2*Ar_0 S("evalrsdbb4in(Ar_0, Ar_1, Ar_2) -> Com_1(evalrsdbb1in(Ar_0, Ar_1, Ar_2)) [ Ar_0 >= 0 /\\ Ar_2 >= Ar_0 ]", 0-2) = 2*Ar_0 + 8 S("evalrsdbb4in(Ar_0, Ar_1, Ar_2) -> Com_1(evalrsdstop(Ar_0, Ar_1, Ar_2)) [ Ar_0 >= 0 /\\ Ar_0 >= Ar_2 + 1 ]", 0-0) = Ar_0 S("evalrsdbb4in(Ar_0, Ar_1, Ar_2) -> Com_1(evalrsdstop(Ar_0, Ar_1, Ar_2)) [ Ar_0 >= 0 /\\ Ar_0 >= Ar_2 + 1 ]", 0-1) = 2*Ar_0 S("evalrsdbb4in(Ar_0, Ar_1, Ar_2) -> Com_1(evalrsdstop(Ar_0, Ar_1, Ar_2)) [ Ar_0 >= 0 /\\ Ar_0 >= Ar_2 + 1 ]", 0-2) = 2*Ar_0 + 16 S("evalrsdbb1in(Ar_0, Ar_1, Ar_2) -> Com_1(evalrsdbb1in(Ar_0, Ar_1 - 1, Ar_1 - 1)) [ Ar_2 >= 0 /\\ Ar_0 + Ar_2 >= 0 /\\ -Ar_0 + Ar_2 >= 0 /\\ Ar_0 >= 0 /\\ Ar_1 - 1 >= Ar_0 ]", 0-0) = Ar_0 S("evalrsdbb1in(Ar_0, Ar_1, Ar_2) -> Com_1(evalrsdbb1in(Ar_0, Ar_1 - 1, Ar_1 - 1)) [ Ar_2 >= 0 /\\ Ar_0 + Ar_2 >= 0 /\\ -Ar_0 + Ar_2 >= 0 /\\ Ar_0 >= 0 /\\ Ar_1 - 1 >= Ar_0 ]", 0-1) = 2*Ar_0 S("evalrsdbb1in(Ar_0, Ar_1, Ar_2) -> Com_1(evalrsdbb1in(Ar_0, Ar_1 - 1, Ar_1 - 1)) [ Ar_2 >= 0 /\\ Ar_0 + Ar_2 >= 0 /\\ -Ar_0 + Ar_2 >= 0 /\\ Ar_0 >= 0 /\\ Ar_1 - 1 >= Ar_0 ]", 0-2) = 2*Ar_0 S("evalrsdbb1in(Ar_0, Ar_1, Ar_2) -> Com_1(evalrsdstop(Ar_0, Ar_1 - 1, Ar_1 - 1)) [ Ar_2 >= 0 /\\ Ar_0 + Ar_2 >= 0 /\\ -Ar_0 + Ar_2 >= 0 /\\ Ar_0 >= 0 /\\ Ar_0 >= Ar_1 ]", 0-0) = Ar_0 S("evalrsdbb1in(Ar_0, Ar_1, Ar_2) -> Com_1(evalrsdstop(Ar_0, Ar_1 - 1, Ar_1 - 1)) [ Ar_2 >= 0 /\\ Ar_0 + Ar_2 >= 0 /\\ -Ar_0 + Ar_2 >= 0 /\\ Ar_0 >= 0 /\\ Ar_0 >= Ar_1 ]", 0-1) = 2*Ar_0 + 2 S("evalrsdbb1in(Ar_0, Ar_1, Ar_2) -> Com_1(evalrsdstop(Ar_0, Ar_1 - 1, Ar_1 - 1)) [ Ar_2 >= 0 /\\ Ar_0 + Ar_2 >= 0 /\\ -Ar_0 + Ar_2 >= 0 /\\ Ar_0 >= 0 /\\ Ar_0 >= Ar_1 ]", 0-2) = 2*Ar_0 + 2 orients the transitions evalrsdbb4in(Ar_0, Ar_1, Ar_2) -> Com_1(evalrsdbb1in(Ar_0, Ar_1, Ar_2)) [ Ar_0 >= 0 /\ Ar_2 >= Ar_0 ] evalrsdbb1in(Ar_0, Ar_1, Ar_2) -> Com_1(evalrsdbb4in(Ar_0, Ar_1, Ar_2 - 1)) [ Ar_2 >= 0 /\ Ar_0 + Ar_2 >= 0 /\ -Ar_0 + Ar_2 >= 0 /\ Ar_0 >= 0 /\ D >= 1 ] evalrsdbb1in(Ar_0, Ar_1, Ar_2) -> Com_1(evalrsdbb4in(Ar_0, Ar_1, Ar_2 - 1)) [ Ar_2 >= 0 /\ Ar_0 + Ar_2 >= 0 /\ -Ar_0 + Ar_2 >= 0 /\ Ar_0 >= 0 /\ 0 >= D + 1 ] evalrsdbb1in(Ar_0, Ar_1, Ar_2) -> Com_1(evalrsdbb1in(Ar_0, Ar_1 - 1, Ar_1 - 1)) [ Ar_2 >= 0 /\ Ar_0 + Ar_2 >= 0 /\ -Ar_0 + Ar_2 >= 0 /\ Ar_0 >= 0 /\ Ar_1 - 1 >= Ar_0 ] weakly and the transition evalrsdbb1in(Ar_0, Ar_1, Ar_2) -> Com_1(evalrsdbb1in(Ar_0, Ar_1 - 1, Ar_1 - 1)) [ Ar_2 >= 0 /\ Ar_0 + Ar_2 >= 0 /\ -Ar_0 + Ar_2 >= 0 /\ Ar_0 >= 0 /\ Ar_1 - 1 >= Ar_0 ] strictly and produces the following problem: 20: T: (Comp: 1, Cost: 4) evalrsdbb1in(Ar_0, Ar_1, Ar_2) -> Com_1(evalrsdstop(Ar_0, Ar_1 - 1, Ar_1 - 1)) [ Ar_2 >= 0 /\ Ar_0 + Ar_2 >= 0 /\ -Ar_0 + Ar_2 >= 0 /\ Ar_0 >= 0 /\ Ar_0 >= Ar_1 ] (Comp: 2*Ar_0, Cost: 3) evalrsdbb1in(Ar_0, Ar_1, Ar_2) -> Com_1(evalrsdbb1in(Ar_0, Ar_1 - 1, Ar_1 - 1)) [ Ar_2 >= 0 /\ Ar_0 + Ar_2 >= 0 /\ -Ar_0 + Ar_2 >= 0 /\ Ar_0 >= 0 /\ Ar_1 - 1 >= Ar_0 ] (Comp: 2, Cost: 2) evalrsdbb4in(Ar_0, Ar_1, Ar_2) -> Com_1(evalrsdstop(Ar_0, Ar_1, Ar_2)) [ Ar_0 >= 0 /\ Ar_0 >= Ar_2 + 1 ] (Comp: ?, Cost: 1) evalrsdbb4in(Ar_0, Ar_1, Ar_2) -> Com_1(evalrsdbb1in(Ar_0, Ar_1, Ar_2)) [ Ar_0 >= 0 /\ Ar_2 >= Ar_0 ] (Comp: ?, Cost: 2) evalrsdbb1in(Ar_0, Ar_1, Ar_2) -> Com_1(evalrsdbb4in(Ar_0, Ar_1, Ar_2 - 1)) [ Ar_2 >= 0 /\ Ar_0 + Ar_2 >= 0 /\ -Ar_0 + Ar_2 >= 0 /\ Ar_0 >= 0 /\ D >= 1 ] (Comp: ?, Cost: 2) evalrsdbb1in(Ar_0, Ar_1, Ar_2) -> Com_1(evalrsdbb4in(Ar_0, Ar_1, Ar_2 - 1)) [ Ar_2 >= 0 /\ Ar_0 + Ar_2 >= 0 /\ -Ar_0 + Ar_2 >= 0 /\ Ar_0 >= 0 /\ 0 >= D + 1 ] (Comp: 1, Cost: 2) evalrsdentryin(Ar_0, Ar_1, Ar_2) -> Com_1(evalrsdstop(Ar_0, Ar_1, Ar_2)) [ 0 >= Ar_0 + 1 ] (Comp: 1, Cost: 3) evalrsdentryin(Ar_0, Ar_1, Ar_2) -> Com_1(evalrsdbb1in(Ar_0, 2*Ar_0, 2*Ar_0)) [ Ar_0 >= 0 /\ 2*Ar_0 >= Ar_0 ] (Comp: 1, Cost: 1) koat_start(Ar_0, Ar_1, Ar_2) -> Com_1(evalrsdentryin(Ar_0, Ar_1, Ar_2)) [ 0 <= 0 ] start location: koat_start leaf cost: 0 A polynomial rank function with Pol(evalrsdbb4in) = 2*V_3 + 2 Pol(evalrsdbb1in) = 2*V_3 + 1 and size complexities S("koat_start(Ar_0, Ar_1, Ar_2) -> Com_1(evalrsdentryin(Ar_0, Ar_1, Ar_2)) [ 0 <= 0 ]", 0-0) = Ar_0 S("koat_start(Ar_0, Ar_1, Ar_2) -> Com_1(evalrsdentryin(Ar_0, Ar_1, Ar_2)) [ 0 <= 0 ]", 0-1) = Ar_1 S("koat_start(Ar_0, Ar_1, Ar_2) -> Com_1(evalrsdentryin(Ar_0, Ar_1, Ar_2)) [ 0 <= 0 ]", 0-2) = Ar_2 S("evalrsdentryin(Ar_0, Ar_1, Ar_2) -> Com_1(evalrsdbb1in(Ar_0, 2*Ar_0, 2*Ar_0)) [ Ar_0 >= 0 /\\ 2*Ar_0 >= Ar_0 ]", 0-0) = Ar_0 S("evalrsdentryin(Ar_0, Ar_1, Ar_2) -> Com_1(evalrsdbb1in(Ar_0, 2*Ar_0, 2*Ar_0)) [ Ar_0 >= 0 /\\ 2*Ar_0 >= Ar_0 ]", 0-1) = 2*Ar_0 S("evalrsdentryin(Ar_0, Ar_1, Ar_2) -> Com_1(evalrsdbb1in(Ar_0, 2*Ar_0, 2*Ar_0)) [ Ar_0 >= 0 /\\ 2*Ar_0 >= Ar_0 ]", 0-2) = 2*Ar_0 S("evalrsdentryin(Ar_0, Ar_1, Ar_2) -> Com_1(evalrsdstop(Ar_0, Ar_1, Ar_2)) [ 0 >= Ar_0 + 1 ]", 0-0) = Ar_0 S("evalrsdentryin(Ar_0, Ar_1, Ar_2) -> Com_1(evalrsdstop(Ar_0, Ar_1, Ar_2)) [ 0 >= Ar_0 + 1 ]", 0-1) = Ar_1 S("evalrsdentryin(Ar_0, Ar_1, Ar_2) -> Com_1(evalrsdstop(Ar_0, Ar_1, Ar_2)) [ 0 >= Ar_0 + 1 ]", 0-2) = Ar_2 S("evalrsdbb1in(Ar_0, Ar_1, Ar_2) -> Com_1(evalrsdbb4in(Ar_0, Ar_1, Ar_2 - 1)) [ Ar_2 >= 0 /\\ Ar_0 + Ar_2 >= 0 /\\ -Ar_0 + Ar_2 >= 0 /\\ Ar_0 >= 0 /\\ 0 >= D + 1 ]", 0-0) = Ar_0 S("evalrsdbb1in(Ar_0, Ar_1, Ar_2) -> Com_1(evalrsdbb4in(Ar_0, Ar_1, Ar_2 - 1)) [ Ar_2 >= 0 /\\ Ar_0 + Ar_2 >= 0 /\\ -Ar_0 + Ar_2 >= 0 /\\ Ar_0 >= 0 /\\ 0 >= D + 1 ]", 0-1) = 2*Ar_0 S("evalrsdbb1in(Ar_0, Ar_1, Ar_2) -> Com_1(evalrsdbb4in(Ar_0, Ar_1, Ar_2 - 1)) [ Ar_2 >= 0 /\\ Ar_0 + Ar_2 >= 0 /\\ -Ar_0 + Ar_2 >= 0 /\\ Ar_0 >= 0 /\\ 0 >= D + 1 ]", 0-2) = 2*Ar_0 + 8 S("evalrsdbb1in(Ar_0, Ar_1, Ar_2) -> Com_1(evalrsdbb4in(Ar_0, Ar_1, Ar_2 - 1)) [ Ar_2 >= 0 /\\ Ar_0 + Ar_2 >= 0 /\\ -Ar_0 + Ar_2 >= 0 /\\ Ar_0 >= 0 /\\ D >= 1 ]", 0-0) = Ar_0 S("evalrsdbb1in(Ar_0, Ar_1, Ar_2) -> Com_1(evalrsdbb4in(Ar_0, Ar_1, Ar_2 - 1)) [ Ar_2 >= 0 /\\ Ar_0 + Ar_2 >= 0 /\\ -Ar_0 + Ar_2 >= 0 /\\ Ar_0 >= 0 /\\ D >= 1 ]", 0-1) = 2*Ar_0 S("evalrsdbb1in(Ar_0, Ar_1, Ar_2) -> Com_1(evalrsdbb4in(Ar_0, Ar_1, Ar_2 - 1)) [ Ar_2 >= 0 /\\ Ar_0 + Ar_2 >= 0 /\\ -Ar_0 + Ar_2 >= 0 /\\ Ar_0 >= 0 /\\ D >= 1 ]", 0-2) = 2*Ar_0 + 8 S("evalrsdbb4in(Ar_0, Ar_1, Ar_2) -> Com_1(evalrsdbb1in(Ar_0, Ar_1, Ar_2)) [ Ar_0 >= 0 /\\ Ar_2 >= Ar_0 ]", 0-0) = Ar_0 S("evalrsdbb4in(Ar_0, Ar_1, Ar_2) -> Com_1(evalrsdbb1in(Ar_0, Ar_1, Ar_2)) [ Ar_0 >= 0 /\\ Ar_2 >= Ar_0 ]", 0-1) = 2*Ar_0 S("evalrsdbb4in(Ar_0, Ar_1, Ar_2) -> Com_1(evalrsdbb1in(Ar_0, Ar_1, Ar_2)) [ Ar_0 >= 0 /\\ Ar_2 >= Ar_0 ]", 0-2) = 2*Ar_0 + 8 S("evalrsdbb4in(Ar_0, Ar_1, Ar_2) -> Com_1(evalrsdstop(Ar_0, Ar_1, Ar_2)) [ Ar_0 >= 0 /\\ Ar_0 >= Ar_2 + 1 ]", 0-0) = Ar_0 S("evalrsdbb4in(Ar_0, Ar_1, Ar_2) -> Com_1(evalrsdstop(Ar_0, Ar_1, Ar_2)) [ Ar_0 >= 0 /\\ Ar_0 >= Ar_2 + 1 ]", 0-1) = 2*Ar_0 S("evalrsdbb4in(Ar_0, Ar_1, Ar_2) -> Com_1(evalrsdstop(Ar_0, Ar_1, Ar_2)) [ Ar_0 >= 0 /\\ Ar_0 >= Ar_2 + 1 ]", 0-2) = 2*Ar_0 + 16 S("evalrsdbb1in(Ar_0, Ar_1, Ar_2) -> Com_1(evalrsdbb1in(Ar_0, Ar_1 - 1, Ar_1 - 1)) [ Ar_2 >= 0 /\\ Ar_0 + Ar_2 >= 0 /\\ -Ar_0 + Ar_2 >= 0 /\\ Ar_0 >= 0 /\\ Ar_1 - 1 >= Ar_0 ]", 0-0) = Ar_0 S("evalrsdbb1in(Ar_0, Ar_1, Ar_2) -> Com_1(evalrsdbb1in(Ar_0, Ar_1 - 1, Ar_1 - 1)) [ Ar_2 >= 0 /\\ Ar_0 + Ar_2 >= 0 /\\ -Ar_0 + Ar_2 >= 0 /\\ Ar_0 >= 0 /\\ Ar_1 - 1 >= Ar_0 ]", 0-1) = 2*Ar_0 S("evalrsdbb1in(Ar_0, Ar_1, Ar_2) -> Com_1(evalrsdbb1in(Ar_0, Ar_1 - 1, Ar_1 - 1)) [ Ar_2 >= 0 /\\ Ar_0 + Ar_2 >= 0 /\\ -Ar_0 + Ar_2 >= 0 /\\ Ar_0 >= 0 /\\ Ar_1 - 1 >= Ar_0 ]", 0-2) = 2*Ar_0 S("evalrsdbb1in(Ar_0, Ar_1, Ar_2) -> Com_1(evalrsdstop(Ar_0, Ar_1 - 1, Ar_1 - 1)) [ Ar_2 >= 0 /\\ Ar_0 + Ar_2 >= 0 /\\ -Ar_0 + Ar_2 >= 0 /\\ Ar_0 >= 0 /\\ Ar_0 >= Ar_1 ]", 0-0) = Ar_0 S("evalrsdbb1in(Ar_0, Ar_1, Ar_2) -> Com_1(evalrsdstop(Ar_0, Ar_1 - 1, Ar_1 - 1)) [ Ar_2 >= 0 /\\ Ar_0 + Ar_2 >= 0 /\\ -Ar_0 + Ar_2 >= 0 /\\ Ar_0 >= 0 /\\ Ar_0 >= Ar_1 ]", 0-1) = 2*Ar_0 + 2 S("evalrsdbb1in(Ar_0, Ar_1, Ar_2) -> Com_1(evalrsdstop(Ar_0, Ar_1 - 1, Ar_1 - 1)) [ Ar_2 >= 0 /\\ Ar_0 + Ar_2 >= 0 /\\ -Ar_0 + Ar_2 >= 0 /\\ Ar_0 >= 0 /\\ Ar_0 >= Ar_1 ]", 0-2) = 2*Ar_0 + 2 orients the transitions evalrsdbb4in(Ar_0, Ar_1, Ar_2) -> Com_1(evalrsdbb1in(Ar_0, Ar_1, Ar_2)) [ Ar_0 >= 0 /\ Ar_2 >= Ar_0 ] evalrsdbb1in(Ar_0, Ar_1, Ar_2) -> Com_1(evalrsdbb4in(Ar_0, Ar_1, Ar_2 - 1)) [ Ar_2 >= 0 /\ Ar_0 + Ar_2 >= 0 /\ -Ar_0 + Ar_2 >= 0 /\ Ar_0 >= 0 /\ D >= 1 ] evalrsdbb1in(Ar_0, Ar_1, Ar_2) -> Com_1(evalrsdbb4in(Ar_0, Ar_1, Ar_2 - 1)) [ Ar_2 >= 0 /\ Ar_0 + Ar_2 >= 0 /\ -Ar_0 + Ar_2 >= 0 /\ Ar_0 >= 0 /\ 0 >= D + 1 ] weakly and the transitions evalrsdbb4in(Ar_0, Ar_1, Ar_2) -> Com_1(evalrsdbb1in(Ar_0, Ar_1, Ar_2)) [ Ar_0 >= 0 /\ Ar_2 >= Ar_0 ] evalrsdbb1in(Ar_0, Ar_1, Ar_2) -> Com_1(evalrsdbb4in(Ar_0, Ar_1, Ar_2 - 1)) [ Ar_2 >= 0 /\ Ar_0 + Ar_2 >= 0 /\ -Ar_0 + Ar_2 >= 0 /\ Ar_0 >= 0 /\ D >= 1 ] evalrsdbb1in(Ar_0, Ar_1, Ar_2) -> Com_1(evalrsdbb4in(Ar_0, Ar_1, Ar_2 - 1)) [ Ar_2 >= 0 /\ Ar_0 + Ar_2 >= 0 /\ -Ar_0 + Ar_2 >= 0 /\ Ar_0 >= 0 /\ 0 >= D + 1 ] strictly and produces the following problem: 21: T: (Comp: 1, Cost: 4) evalrsdbb1in(Ar_0, Ar_1, Ar_2) -> Com_1(evalrsdstop(Ar_0, Ar_1 - 1, Ar_1 - 1)) [ Ar_2 >= 0 /\ Ar_0 + Ar_2 >= 0 /\ -Ar_0 + Ar_2 >= 0 /\ Ar_0 >= 0 /\ Ar_0 >= Ar_1 ] (Comp: 2*Ar_0, Cost: 3) evalrsdbb1in(Ar_0, Ar_1, Ar_2) -> Com_1(evalrsdbb1in(Ar_0, Ar_1 - 1, Ar_1 - 1)) [ Ar_2 >= 0 /\ Ar_0 + Ar_2 >= 0 /\ -Ar_0 + Ar_2 >= 0 /\ Ar_0 >= 0 /\ Ar_1 - 1 >= Ar_0 ] (Comp: 2, Cost: 2) evalrsdbb4in(Ar_0, Ar_1, Ar_2) -> Com_1(evalrsdstop(Ar_0, Ar_1, Ar_2)) [ Ar_0 >= 0 /\ Ar_0 >= Ar_2 + 1 ] (Comp: 8*Ar_0^2 + 6*Ar_0 + 1, Cost: 1) evalrsdbb4in(Ar_0, Ar_1, Ar_2) -> Com_1(evalrsdbb1in(Ar_0, Ar_1, Ar_2)) [ Ar_0 >= 0 /\ Ar_2 >= Ar_0 ] (Comp: 8*Ar_0^2 + 6*Ar_0 + 1, Cost: 2) evalrsdbb1in(Ar_0, Ar_1, Ar_2) -> Com_1(evalrsdbb4in(Ar_0, Ar_1, Ar_2 - 1)) [ Ar_2 >= 0 /\ Ar_0 + Ar_2 >= 0 /\ -Ar_0 + Ar_2 >= 0 /\ Ar_0 >= 0 /\ D >= 1 ] (Comp: 8*Ar_0^2 + 6*Ar_0 + 1, Cost: 2) evalrsdbb1in(Ar_0, Ar_1, Ar_2) -> Com_1(evalrsdbb4in(Ar_0, Ar_1, Ar_2 - 1)) [ Ar_2 >= 0 /\ Ar_0 + Ar_2 >= 0 /\ -Ar_0 + Ar_2 >= 0 /\ Ar_0 >= 0 /\ 0 >= D + 1 ] (Comp: 1, Cost: 2) evalrsdentryin(Ar_0, Ar_1, Ar_2) -> Com_1(evalrsdstop(Ar_0, Ar_1, Ar_2)) [ 0 >= Ar_0 + 1 ] (Comp: 1, Cost: 3) evalrsdentryin(Ar_0, Ar_1, Ar_2) -> Com_1(evalrsdbb1in(Ar_0, 2*Ar_0, 2*Ar_0)) [ Ar_0 >= 0 /\ 2*Ar_0 >= Ar_0 ] (Comp: 1, Cost: 1) koat_start(Ar_0, Ar_1, Ar_2) -> Com_1(evalrsdentryin(Ar_0, Ar_1, Ar_2)) [ 0 <= 0 ] start location: koat_start leaf cost: 0 Complexity upper bound 36*Ar_0 + 40*Ar_0^2 + 19 Time: 0.715 sec (SMT: 0.600 sec) ---------------------------------------- (2) BOUNDS(1, n^2) ---------------------------------------- (3) Loat Proof (FINISHED) ### Pre-processing the ITS problem ### Initial linear ITS problem Start location: evalrsdstart 0: evalrsdstart -> evalrsdentryin : [], cost: 1 1: evalrsdentryin -> evalrsdbbin : [ A>=0 ], cost: 1 2: evalrsdentryin -> evalrsdreturnin : [ 0>=1+A ], cost: 1 3: evalrsdbbin -> evalrsdbb4in : B'=2*A, C'=2*A, [], cost: 1 4: evalrsdbb4in -> evalrsdbb1in : [ C>=A ], cost: 1 5: evalrsdbb4in -> evalrsdreturnin : [ A>=1+C ], cost: 1 6: evalrsdbb1in -> evalrsdbb2in : [ 0>=1+free ], cost: 1 7: evalrsdbb1in -> evalrsdbb2in : [ free_1>=1 ], cost: 1 8: evalrsdbb1in -> evalrsdbb3in : [], cost: 1 9: evalrsdbb2in -> evalrsdbb4in : C'=-1+C, [], cost: 1 10: evalrsdbb3in -> evalrsdbb4in : B'=-1+B, C'=-1+B, [], cost: 1 11: evalrsdreturnin -> evalrsdstop : [], cost: 1 Checking for constant complexity: The following rule is satisfiable with cost >= 1, yielding constant complexity: 0: evalrsdstart -> evalrsdentryin : [], cost: 1 Removed unreachable and leaf rules: Start location: evalrsdstart 0: evalrsdstart -> evalrsdentryin : [], cost: 1 1: evalrsdentryin -> evalrsdbbin : [ A>=0 ], cost: 1 3: evalrsdbbin -> evalrsdbb4in : B'=2*A, C'=2*A, [], cost: 1 4: evalrsdbb4in -> evalrsdbb1in : [ C>=A ], cost: 1 6: evalrsdbb1in -> evalrsdbb2in : [ 0>=1+free ], cost: 1 7: evalrsdbb1in -> evalrsdbb2in : [ free_1>=1 ], cost: 1 8: evalrsdbb1in -> evalrsdbb3in : [], cost: 1 9: evalrsdbb2in -> evalrsdbb4in : C'=-1+C, [], cost: 1 10: evalrsdbb3in -> evalrsdbb4in : B'=-1+B, C'=-1+B, [], cost: 1 Simplified all rules, resulting in: Start location: evalrsdstart 0: evalrsdstart -> evalrsdentryin : [], cost: 1 1: evalrsdentryin -> evalrsdbbin : [ A>=0 ], cost: 1 3: evalrsdbbin -> evalrsdbb4in : B'=2*A, C'=2*A, [], cost: 1 4: evalrsdbb4in -> evalrsdbb1in : [ C>=A ], cost: 1 7: evalrsdbb1in -> evalrsdbb2in : [], cost: 1 8: evalrsdbb1in -> evalrsdbb3in : [], cost: 1 9: evalrsdbb2in -> evalrsdbb4in : C'=-1+C, [], cost: 1 10: evalrsdbb3in -> evalrsdbb4in : B'=-1+B, C'=-1+B, [], cost: 1 ### Simplification by acceleration and chaining ### Eliminated locations (on linear paths): Start location: evalrsdstart 13: evalrsdstart -> evalrsdbb4in : B'=2*A, C'=2*A, [ A>=0 ], cost: 3 4: evalrsdbb4in -> evalrsdbb1in : [ C>=A ], cost: 1 14: evalrsdbb1in -> evalrsdbb4in : C'=-1+C, [], cost: 2 15: evalrsdbb1in -> evalrsdbb4in : B'=-1+B, C'=-1+B, [], cost: 2 Eliminated locations (on tree-shaped paths): Start location: evalrsdstart 13: evalrsdstart -> evalrsdbb4in : B'=2*A, C'=2*A, [ A>=0 ], cost: 3 16: evalrsdbb4in -> evalrsdbb4in : C'=-1+C, [ C>=A ], cost: 3 17: evalrsdbb4in -> evalrsdbb4in : B'=-1+B, C'=-1+B, [ C>=A ], cost: 3 Accelerating simple loops of location 3. Accelerating the following rules: 16: evalrsdbb4in -> evalrsdbb4in : C'=-1+C, [ C>=A ], cost: 3 17: evalrsdbb4in -> evalrsdbb4in : B'=-1+B, C'=-1+B, [ C>=A ], cost: 3 Accelerated rule 16 with metering function 1+C-A, yielding the new rule 18. Found no metering function for rule 17. Removing the simple loops: 16. Accelerated all simple loops using metering functions (where possible): Start location: evalrsdstart 13: evalrsdstart -> evalrsdbb4in : B'=2*A, C'=2*A, [ A>=0 ], cost: 3 17: evalrsdbb4in -> evalrsdbb4in : B'=-1+B, C'=-1+B, [ C>=A ], cost: 3 18: evalrsdbb4in -> evalrsdbb4in : C'=-1+A, [ C>=A ], cost: 3+3*C-3*A Chained accelerated rules (with incoming rules): Start location: evalrsdstart 13: evalrsdstart -> evalrsdbb4in : B'=2*A, C'=2*A, [ A>=0 ], cost: 3 19: evalrsdstart -> evalrsdbb4in : B'=-1+2*A, C'=-1+2*A, [ A>=0 ], cost: 6 20: evalrsdstart -> evalrsdbb4in : B'=2*A, C'=-1+A, [ A>=0 ], cost: 6+3*A Removed unreachable locations (and leaf rules with constant cost): Start location: evalrsdstart 20: evalrsdstart -> evalrsdbb4in : B'=2*A, C'=-1+A, [ A>=0 ], cost: 6+3*A ### Computing asymptotic complexity ### Fully simplified ITS problem Start location: evalrsdstart 20: evalrsdstart -> evalrsdbb4in : B'=2*A, C'=-1+A, [ A>=0 ], cost: 6+3*A Computing asymptotic complexity for rule 20 Solved the limit problem by the following transformations: Created initial limit problem: 6+3*A (+), 1+A (+/+!) [not solved] removing all constraints (solved by SMT) resulting limit problem: [solved] applying transformation rule (C) using substitution {A==n} resulting limit problem: [solved] Solution: A / n Resulting cost 6+3*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: 6+3*n Rule cost: 6+3*A Rule guard: [ A>=0 ] WORST_CASE(Omega(n^1),?) ---------------------------------------- (4) BOUNDS(n^1, INF)