/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^1)) 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^1). (0) CpxIntTrs (1) Koat Proof [FINISHED, 283 ms] (2) BOUNDS(1, n^1) (3) Loat Proof [FINISHED, 818 ms] (4) BOUNDS(n^1, INF) ---------------------------------------- (0) Obligation: Complexity Int TRS consisting of the following rules: evalEx4start(A, B, C, D) -> Com_1(evalEx4entryin(A, B, C, D)) :|: TRUE evalEx4entryin(A, B, C, D) -> Com_1(evalEx4bb4in(1, A, C, D)) :|: TRUE evalEx4bb4in(A, B, C, D) -> Com_1(evalEx4bb2in(A, B, 0, B)) :|: A >= 1 && A <= 1 evalEx4bb4in(A, B, C, D) -> Com_1(evalEx4returnin(A, B, C, D)) :|: 0 >= A evalEx4bb4in(A, B, C, D) -> Com_1(evalEx4returnin(A, B, C, D)) :|: A >= 2 evalEx4bb2in(A, B, C, D) -> Com_1(evalEx4bb4in(C, D, C, D)) :|: 0 >= D evalEx4bb2in(A, B, C, D) -> Com_1(evalEx4bb3in(A, B, C, D)) :|: D >= 1 evalEx4bb3in(A, B, C, D) -> Com_1(evalEx4bb1in(A, B, C, D)) :|: 0 >= E + 1 evalEx4bb3in(A, B, C, D) -> Com_1(evalEx4bb1in(A, B, C, D)) :|: E >= 1 evalEx4bb3in(A, B, C, D) -> Com_1(evalEx4bb4in(C, D, C, D)) :|: TRUE evalEx4bb1in(A, B, C, D) -> Com_1(evalEx4bb2in(A, B, 1, D - 1)) :|: TRUE evalEx4returnin(A, B, C, D) -> Com_1(evalEx4stop(A, B, C, D)) :|: TRUE The start-symbols are:[evalEx4start_4] ---------------------------------------- (1) Koat Proof (FINISHED) YES(?, 75*Ar_0 + 42) Initial complexity problem: 1: T: (Comp: ?, Cost: 1) evalEx4start(Ar_0, Ar_1, Ar_2, Ar_3) -> Com_1(evalEx4entryin(Ar_0, Ar_1, Ar_2, Ar_3)) (Comp: ?, Cost: 1) evalEx4entryin(Ar_0, Ar_1, Ar_2, Ar_3) -> Com_1(evalEx4bb4in(1, Ar_0, Ar_2, Ar_3)) (Comp: ?, Cost: 1) evalEx4bb4in(Ar_0, Ar_1, Ar_2, Ar_3) -> Com_1(evalEx4bb2in(Ar_0, Ar_1, 0, Ar_1)) [ Ar_0 = 1 ] (Comp: ?, Cost: 1) evalEx4bb4in(Ar_0, Ar_1, Ar_2, Ar_3) -> Com_1(evalEx4returnin(Ar_0, Ar_1, Ar_2, Ar_3)) [ 0 >= Ar_0 ] (Comp: ?, Cost: 1) evalEx4bb4in(Ar_0, Ar_1, Ar_2, Ar_3) -> Com_1(evalEx4returnin(Ar_0, Ar_1, Ar_2, Ar_3)) [ Ar_0 >= 2 ] (Comp: ?, Cost: 1) evalEx4bb2in(Ar_0, Ar_1, Ar_2, Ar_3) -> Com_1(evalEx4bb4in(Ar_2, Ar_3, Ar_2, Ar_3)) [ 0 >= Ar_3 ] (Comp: ?, Cost: 1) evalEx4bb2in(Ar_0, Ar_1, Ar_2, Ar_3) -> Com_1(evalEx4bb3in(Ar_0, Ar_1, Ar_2, Ar_3)) [ Ar_3 >= 1 ] (Comp: ?, Cost: 1) evalEx4bb3in(Ar_0, Ar_1, Ar_2, Ar_3) -> Com_1(evalEx4bb1in(Ar_0, Ar_1, Ar_2, Ar_3)) [ 0 >= E + 1 ] (Comp: ?, Cost: 1) evalEx4bb3in(Ar_0, Ar_1, Ar_2, Ar_3) -> Com_1(evalEx4bb1in(Ar_0, Ar_1, Ar_2, Ar_3)) [ E >= 1 ] (Comp: ?, Cost: 1) evalEx4bb3in(Ar_0, Ar_1, Ar_2, Ar_3) -> Com_1(evalEx4bb4in(Ar_2, Ar_3, Ar_2, Ar_3)) (Comp: ?, Cost: 1) evalEx4bb1in(Ar_0, Ar_1, Ar_2, Ar_3) -> Com_1(evalEx4bb2in(Ar_0, Ar_1, 1, Ar_3 - 1)) (Comp: ?, Cost: 1) evalEx4returnin(Ar_0, Ar_1, Ar_2, Ar_3) -> Com_1(evalEx4stop(Ar_0, Ar_1, Ar_2, Ar_3)) (Comp: 1, Cost: 0) koat_start(Ar_0, Ar_1, Ar_2, Ar_3) -> Com_1(evalEx4start(Ar_0, Ar_1, Ar_2, Ar_3)) [ 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) evalEx4start(Ar_0, Ar_1, Ar_2, Ar_3) -> Com_1(evalEx4entryin(Ar_0, Ar_1, Ar_2, Ar_3)) (Comp: 1, Cost: 1) evalEx4entryin(Ar_0, Ar_1, Ar_2, Ar_3) -> Com_1(evalEx4bb4in(1, Ar_0, Ar_2, Ar_3)) (Comp: ?, Cost: 1) evalEx4bb4in(Ar_0, Ar_1, Ar_2, Ar_3) -> Com_1(evalEx4bb2in(Ar_0, Ar_1, 0, Ar_1)) [ Ar_0 = 1 ] (Comp: ?, Cost: 1) evalEx4bb4in(Ar_0, Ar_1, Ar_2, Ar_3) -> Com_1(evalEx4returnin(Ar_0, Ar_1, Ar_2, Ar_3)) [ 0 >= Ar_0 ] (Comp: ?, Cost: 1) evalEx4bb4in(Ar_0, Ar_1, Ar_2, Ar_3) -> Com_1(evalEx4returnin(Ar_0, Ar_1, Ar_2, Ar_3)) [ Ar_0 >= 2 ] (Comp: ?, Cost: 1) evalEx4bb2in(Ar_0, Ar_1, Ar_2, Ar_3) -> Com_1(evalEx4bb4in(Ar_2, Ar_3, Ar_2, Ar_3)) [ 0 >= Ar_3 ] (Comp: ?, Cost: 1) evalEx4bb2in(Ar_0, Ar_1, Ar_2, Ar_3) -> Com_1(evalEx4bb3in(Ar_0, Ar_1, Ar_2, Ar_3)) [ Ar_3 >= 1 ] (Comp: ?, Cost: 1) evalEx4bb3in(Ar_0, Ar_1, Ar_2, Ar_3) -> Com_1(evalEx4bb1in(Ar_0, Ar_1, Ar_2, Ar_3)) [ 0 >= E + 1 ] (Comp: ?, Cost: 1) evalEx4bb3in(Ar_0, Ar_1, Ar_2, Ar_3) -> Com_1(evalEx4bb1in(Ar_0, Ar_1, Ar_2, Ar_3)) [ E >= 1 ] (Comp: ?, Cost: 1) evalEx4bb3in(Ar_0, Ar_1, Ar_2, Ar_3) -> Com_1(evalEx4bb4in(Ar_2, Ar_3, Ar_2, Ar_3)) (Comp: ?, Cost: 1) evalEx4bb1in(Ar_0, Ar_1, Ar_2, Ar_3) -> Com_1(evalEx4bb2in(Ar_0, Ar_1, 1, Ar_3 - 1)) (Comp: ?, Cost: 1) evalEx4returnin(Ar_0, Ar_1, Ar_2, Ar_3) -> Com_1(evalEx4stop(Ar_0, Ar_1, Ar_2, Ar_3)) (Comp: 1, Cost: 0) koat_start(Ar_0, Ar_1, Ar_2, Ar_3) -> Com_1(evalEx4start(Ar_0, Ar_1, Ar_2, Ar_3)) [ 0 <= 0 ] start location: koat_start leaf cost: 0 A polynomial rank function with Pol(evalEx4start) = 2 Pol(evalEx4entryin) = 2 Pol(evalEx4bb4in) = 2 Pol(evalEx4bb2in) = 2 Pol(evalEx4returnin) = 1 Pol(evalEx4bb3in) = 2 Pol(evalEx4bb1in) = 2 Pol(evalEx4stop) = 0 Pol(koat_start) = 2 orients all transitions weakly and the transitions evalEx4returnin(Ar_0, Ar_1, Ar_2, Ar_3) -> Com_1(evalEx4stop(Ar_0, Ar_1, Ar_2, Ar_3)) evalEx4bb4in(Ar_0, Ar_1, Ar_2, Ar_3) -> Com_1(evalEx4returnin(Ar_0, Ar_1, Ar_2, Ar_3)) [ Ar_0 >= 2 ] evalEx4bb4in(Ar_0, Ar_1, Ar_2, Ar_3) -> Com_1(evalEx4returnin(Ar_0, Ar_1, Ar_2, Ar_3)) [ 0 >= Ar_0 ] strictly and produces the following problem: 3: T: (Comp: 1, Cost: 1) evalEx4start(Ar_0, Ar_1, Ar_2, Ar_3) -> Com_1(evalEx4entryin(Ar_0, Ar_1, Ar_2, Ar_3)) (Comp: 1, Cost: 1) evalEx4entryin(Ar_0, Ar_1, Ar_2, Ar_3) -> Com_1(evalEx4bb4in(1, Ar_0, Ar_2, Ar_3)) (Comp: ?, Cost: 1) evalEx4bb4in(Ar_0, Ar_1, Ar_2, Ar_3) -> Com_1(evalEx4bb2in(Ar_0, Ar_1, 0, Ar_1)) [ Ar_0 = 1 ] (Comp: 2, Cost: 1) evalEx4bb4in(Ar_0, Ar_1, Ar_2, Ar_3) -> Com_1(evalEx4returnin(Ar_0, Ar_1, Ar_2, Ar_3)) [ 0 >= Ar_0 ] (Comp: 2, Cost: 1) evalEx4bb4in(Ar_0, Ar_1, Ar_2, Ar_3) -> Com_1(evalEx4returnin(Ar_0, Ar_1, Ar_2, Ar_3)) [ Ar_0 >= 2 ] (Comp: ?, Cost: 1) evalEx4bb2in(Ar_0, Ar_1, Ar_2, Ar_3) -> Com_1(evalEx4bb4in(Ar_2, Ar_3, Ar_2, Ar_3)) [ 0 >= Ar_3 ] (Comp: ?, Cost: 1) evalEx4bb2in(Ar_0, Ar_1, Ar_2, Ar_3) -> Com_1(evalEx4bb3in(Ar_0, Ar_1, Ar_2, Ar_3)) [ Ar_3 >= 1 ] (Comp: ?, Cost: 1) evalEx4bb3in(Ar_0, Ar_1, Ar_2, Ar_3) -> Com_1(evalEx4bb1in(Ar_0, Ar_1, Ar_2, Ar_3)) [ 0 >= E + 1 ] (Comp: ?, Cost: 1) evalEx4bb3in(Ar_0, Ar_1, Ar_2, Ar_3) -> Com_1(evalEx4bb1in(Ar_0, Ar_1, Ar_2, Ar_3)) [ E >= 1 ] (Comp: ?, Cost: 1) evalEx4bb3in(Ar_0, Ar_1, Ar_2, Ar_3) -> Com_1(evalEx4bb4in(Ar_2, Ar_3, Ar_2, Ar_3)) (Comp: ?, Cost: 1) evalEx4bb1in(Ar_0, Ar_1, Ar_2, Ar_3) -> Com_1(evalEx4bb2in(Ar_0, Ar_1, 1, Ar_3 - 1)) (Comp: 2, Cost: 1) evalEx4returnin(Ar_0, Ar_1, Ar_2, Ar_3) -> Com_1(evalEx4stop(Ar_0, Ar_1, Ar_2, Ar_3)) (Comp: 1, Cost: 0) koat_start(Ar_0, Ar_1, Ar_2, Ar_3) -> Com_1(evalEx4start(Ar_0, Ar_1, Ar_2, Ar_3)) [ 0 <= 0 ] start location: koat_start leaf cost: 0 Applied AI with 'oct' on problem 3 to obtain the following invariants: For symbol evalEx4bb1in: X_2 - X_4 >= 0 /\ X_4 - 1 >= 0 /\ X_3 + X_4 - 1 >= 0 /\ X_2 + X_4 - 2 >= 0 /\ X_1 + X_4 - 2 >= 0 /\ -X_1 + X_4 >= 0 /\ X_3 >= 0 /\ X_2 + X_3 - 1 >= 0 /\ X_1 + X_3 - 1 >= 0 /\ -X_1 + X_3 + 1 >= 0 /\ X_2 - 1 >= 0 /\ X_1 + X_2 - 2 >= 0 /\ -X_1 + X_2 >= 0 /\ -X_1 + 1 >= 0 /\ X_1 - 1 >= 0 For symbol evalEx4bb2in: X_2 - X_4 >= 0 /\ X_3 >= 0 /\ X_1 + X_3 - 1 >= 0 /\ -X_1 + X_3 + 1 >= 0 /\ -X_1 + 1 >= 0 /\ X_1 - 1 >= 0 For symbol evalEx4bb3in: X_2 - X_4 >= 0 /\ X_4 - 1 >= 0 /\ X_3 + X_4 - 1 >= 0 /\ X_2 + X_4 - 2 >= 0 /\ X_1 + X_4 - 2 >= 0 /\ -X_1 + X_4 >= 0 /\ X_3 >= 0 /\ X_2 + X_3 - 1 >= 0 /\ X_1 + X_3 - 1 >= 0 /\ -X_1 + X_3 + 1 >= 0 /\ X_2 - 1 >= 0 /\ X_1 + X_2 - 2 >= 0 /\ -X_1 + X_2 >= 0 /\ -X_1 + 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, Ar_3) -> Com_1(evalEx4start(Ar_0, Ar_1, Ar_2, Ar_3)) [ 0 <= 0 ] (Comp: 2, Cost: 1) evalEx4returnin(Ar_0, Ar_1, Ar_2, Ar_3) -> Com_1(evalEx4stop(Ar_0, Ar_1, Ar_2, Ar_3)) (Comp: ?, Cost: 1) evalEx4bb1in(Ar_0, Ar_1, Ar_2, Ar_3) -> Com_1(evalEx4bb2in(Ar_0, Ar_1, 1, Ar_3 - 1)) [ Ar_1 - Ar_3 >= 0 /\ Ar_3 - 1 >= 0 /\ Ar_2 + Ar_3 - 1 >= 0 /\ Ar_1 + Ar_3 - 2 >= 0 /\ Ar_0 + Ar_3 - 2 >= 0 /\ -Ar_0 + Ar_3 >= 0 /\ Ar_2 >= 0 /\ Ar_1 + Ar_2 - 1 >= 0 /\ Ar_0 + Ar_2 - 1 >= 0 /\ -Ar_0 + Ar_2 + 1 >= 0 /\ Ar_1 - 1 >= 0 /\ Ar_0 + Ar_1 - 2 >= 0 /\ -Ar_0 + Ar_1 >= 0 /\ -Ar_0 + 1 >= 0 /\ Ar_0 - 1 >= 0 ] (Comp: ?, Cost: 1) evalEx4bb3in(Ar_0, Ar_1, Ar_2, Ar_3) -> Com_1(evalEx4bb4in(Ar_2, Ar_3, Ar_2, Ar_3)) [ Ar_1 - Ar_3 >= 0 /\ Ar_3 - 1 >= 0 /\ Ar_2 + Ar_3 - 1 >= 0 /\ Ar_1 + Ar_3 - 2 >= 0 /\ Ar_0 + Ar_3 - 2 >= 0 /\ -Ar_0 + Ar_3 >= 0 /\ Ar_2 >= 0 /\ Ar_1 + Ar_2 - 1 >= 0 /\ Ar_0 + Ar_2 - 1 >= 0 /\ -Ar_0 + Ar_2 + 1 >= 0 /\ Ar_1 - 1 >= 0 /\ Ar_0 + Ar_1 - 2 >= 0 /\ -Ar_0 + Ar_1 >= 0 /\ -Ar_0 + 1 >= 0 /\ Ar_0 - 1 >= 0 ] (Comp: ?, Cost: 1) evalEx4bb3in(Ar_0, Ar_1, Ar_2, Ar_3) -> Com_1(evalEx4bb1in(Ar_0, Ar_1, Ar_2, Ar_3)) [ Ar_1 - Ar_3 >= 0 /\ Ar_3 - 1 >= 0 /\ Ar_2 + Ar_3 - 1 >= 0 /\ Ar_1 + Ar_3 - 2 >= 0 /\ Ar_0 + Ar_3 - 2 >= 0 /\ -Ar_0 + Ar_3 >= 0 /\ Ar_2 >= 0 /\ Ar_1 + Ar_2 - 1 >= 0 /\ Ar_0 + Ar_2 - 1 >= 0 /\ -Ar_0 + Ar_2 + 1 >= 0 /\ Ar_1 - 1 >= 0 /\ Ar_0 + Ar_1 - 2 >= 0 /\ -Ar_0 + Ar_1 >= 0 /\ -Ar_0 + 1 >= 0 /\ Ar_0 - 1 >= 0 /\ E >= 1 ] (Comp: ?, Cost: 1) evalEx4bb3in(Ar_0, Ar_1, Ar_2, Ar_3) -> Com_1(evalEx4bb1in(Ar_0, Ar_1, Ar_2, Ar_3)) [ Ar_1 - Ar_3 >= 0 /\ Ar_3 - 1 >= 0 /\ Ar_2 + Ar_3 - 1 >= 0 /\ Ar_1 + Ar_3 - 2 >= 0 /\ Ar_0 + Ar_3 - 2 >= 0 /\ -Ar_0 + Ar_3 >= 0 /\ Ar_2 >= 0 /\ Ar_1 + Ar_2 - 1 >= 0 /\ Ar_0 + Ar_2 - 1 >= 0 /\ -Ar_0 + Ar_2 + 1 >= 0 /\ Ar_1 - 1 >= 0 /\ Ar_0 + Ar_1 - 2 >= 0 /\ -Ar_0 + Ar_1 >= 0 /\ -Ar_0 + 1 >= 0 /\ Ar_0 - 1 >= 0 /\ 0 >= E + 1 ] (Comp: ?, Cost: 1) evalEx4bb2in(Ar_0, Ar_1, Ar_2, Ar_3) -> Com_1(evalEx4bb3in(Ar_0, Ar_1, Ar_2, Ar_3)) [ Ar_1 - Ar_3 >= 0 /\ Ar_2 >= 0 /\ Ar_0 + Ar_2 - 1 >= 0 /\ -Ar_0 + Ar_2 + 1 >= 0 /\ -Ar_0 + 1 >= 0 /\ Ar_0 - 1 >= 0 /\ Ar_3 >= 1 ] (Comp: ?, Cost: 1) evalEx4bb2in(Ar_0, Ar_1, Ar_2, Ar_3) -> Com_1(evalEx4bb4in(Ar_2, Ar_3, Ar_2, Ar_3)) [ Ar_1 - Ar_3 >= 0 /\ Ar_2 >= 0 /\ Ar_0 + Ar_2 - 1 >= 0 /\ -Ar_0 + Ar_2 + 1 >= 0 /\ -Ar_0 + 1 >= 0 /\ Ar_0 - 1 >= 0 /\ 0 >= Ar_3 ] (Comp: 2, Cost: 1) evalEx4bb4in(Ar_0, Ar_1, Ar_2, Ar_3) -> Com_1(evalEx4returnin(Ar_0, Ar_1, Ar_2, Ar_3)) [ Ar_0 >= 2 ] (Comp: 2, Cost: 1) evalEx4bb4in(Ar_0, Ar_1, Ar_2, Ar_3) -> Com_1(evalEx4returnin(Ar_0, Ar_1, Ar_2, Ar_3)) [ 0 >= Ar_0 ] (Comp: ?, Cost: 1) evalEx4bb4in(Ar_0, Ar_1, Ar_2, Ar_3) -> Com_1(evalEx4bb2in(Ar_0, Ar_1, 0, Ar_1)) [ Ar_0 = 1 ] (Comp: 1, Cost: 1) evalEx4entryin(Ar_0, Ar_1, Ar_2, Ar_3) -> Com_1(evalEx4bb4in(1, Ar_0, Ar_2, Ar_3)) (Comp: 1, Cost: 1) evalEx4start(Ar_0, Ar_1, Ar_2, Ar_3) -> Com_1(evalEx4entryin(Ar_0, Ar_1, Ar_2, Ar_3)) start location: koat_start leaf cost: 0 A polynomial rank function with Pol(koat_start) = 5*V_1 + 2 Pol(evalEx4start) = 5*V_1 + 2 Pol(evalEx4returnin) = 2*V_1 + 5*V_2 Pol(evalEx4stop) = 2*V_1 + 5*V_2 Pol(evalEx4bb1in) = 5*V_4 Pol(evalEx4bb2in) = 2*V_1 + 2*V_3 + 5*V_4 Pol(evalEx4bb3in) = V_1 + 2*V_3 + 5*V_4 Pol(evalEx4bb4in) = 2*V_1 + 5*V_2 Pol(evalEx4entryin) = 5*V_1 + 2 orients all transitions weakly and the transitions evalEx4bb3in(Ar_0, Ar_1, Ar_2, Ar_3) -> Com_1(evalEx4bb4in(Ar_2, Ar_3, Ar_2, Ar_3)) [ Ar_1 - Ar_3 >= 0 /\ Ar_3 - 1 >= 0 /\ Ar_2 + Ar_3 - 1 >= 0 /\ Ar_1 + Ar_3 - 2 >= 0 /\ Ar_0 + Ar_3 - 2 >= 0 /\ -Ar_0 + Ar_3 >= 0 /\ Ar_2 >= 0 /\ Ar_1 + Ar_2 - 1 >= 0 /\ Ar_0 + Ar_2 - 1 >= 0 /\ -Ar_0 + Ar_2 + 1 >= 0 /\ Ar_1 - 1 >= 0 /\ Ar_0 + Ar_1 - 2 >= 0 /\ -Ar_0 + Ar_1 >= 0 /\ -Ar_0 + 1 >= 0 /\ Ar_0 - 1 >= 0 ] evalEx4bb3in(Ar_0, Ar_1, Ar_2, Ar_3) -> Com_1(evalEx4bb1in(Ar_0, Ar_1, Ar_2, Ar_3)) [ Ar_1 - Ar_3 >= 0 /\ Ar_3 - 1 >= 0 /\ Ar_2 + Ar_3 - 1 >= 0 /\ Ar_1 + Ar_3 - 2 >= 0 /\ Ar_0 + Ar_3 - 2 >= 0 /\ -Ar_0 + Ar_3 >= 0 /\ Ar_2 >= 0 /\ Ar_1 + Ar_2 - 1 >= 0 /\ Ar_0 + Ar_2 - 1 >= 0 /\ -Ar_0 + Ar_2 + 1 >= 0 /\ Ar_1 - 1 >= 0 /\ Ar_0 + Ar_1 - 2 >= 0 /\ -Ar_0 + Ar_1 >= 0 /\ -Ar_0 + 1 >= 0 /\ Ar_0 - 1 >= 0 /\ E >= 1 ] evalEx4bb3in(Ar_0, Ar_1, Ar_2, Ar_3) -> Com_1(evalEx4bb1in(Ar_0, Ar_1, Ar_2, Ar_3)) [ Ar_1 - Ar_3 >= 0 /\ Ar_3 - 1 >= 0 /\ Ar_2 + Ar_3 - 1 >= 0 /\ Ar_1 + Ar_3 - 2 >= 0 /\ Ar_0 + Ar_3 - 2 >= 0 /\ -Ar_0 + Ar_3 >= 0 /\ Ar_2 >= 0 /\ Ar_1 + Ar_2 - 1 >= 0 /\ Ar_0 + Ar_2 - 1 >= 0 /\ -Ar_0 + Ar_2 + 1 >= 0 /\ Ar_1 - 1 >= 0 /\ Ar_0 + Ar_1 - 2 >= 0 /\ -Ar_0 + Ar_1 >= 0 /\ -Ar_0 + 1 >= 0 /\ Ar_0 - 1 >= 0 /\ 0 >= E + 1 ] evalEx4bb2in(Ar_0, Ar_1, Ar_2, Ar_3) -> Com_1(evalEx4bb3in(Ar_0, Ar_1, Ar_2, Ar_3)) [ Ar_1 - Ar_3 >= 0 /\ Ar_2 >= 0 /\ Ar_0 + Ar_2 - 1 >= 0 /\ -Ar_0 + Ar_2 + 1 >= 0 /\ -Ar_0 + 1 >= 0 /\ Ar_0 - 1 >= 0 /\ Ar_3 >= 1 ] evalEx4bb1in(Ar_0, Ar_1, Ar_2, Ar_3) -> Com_1(evalEx4bb2in(Ar_0, Ar_1, 1, Ar_3 - 1)) [ Ar_1 - Ar_3 >= 0 /\ Ar_3 - 1 >= 0 /\ Ar_2 + Ar_3 - 1 >= 0 /\ Ar_1 + Ar_3 - 2 >= 0 /\ Ar_0 + Ar_3 - 2 >= 0 /\ -Ar_0 + Ar_3 >= 0 /\ Ar_2 >= 0 /\ Ar_1 + Ar_2 - 1 >= 0 /\ Ar_0 + Ar_2 - 1 >= 0 /\ -Ar_0 + Ar_2 + 1 >= 0 /\ Ar_1 - 1 >= 0 /\ Ar_0 + Ar_1 - 2 >= 0 /\ -Ar_0 + Ar_1 >= 0 /\ -Ar_0 + 1 >= 0 /\ Ar_0 - 1 >= 0 ] strictly and produces the following problem: 5: T: (Comp: 1, Cost: 0) koat_start(Ar_0, Ar_1, Ar_2, Ar_3) -> Com_1(evalEx4start(Ar_0, Ar_1, Ar_2, Ar_3)) [ 0 <= 0 ] (Comp: 2, Cost: 1) evalEx4returnin(Ar_0, Ar_1, Ar_2, Ar_3) -> Com_1(evalEx4stop(Ar_0, Ar_1, Ar_2, Ar_3)) (Comp: 5*Ar_0 + 2, Cost: 1) evalEx4bb1in(Ar_0, Ar_1, Ar_2, Ar_3) -> Com_1(evalEx4bb2in(Ar_0, Ar_1, 1, Ar_3 - 1)) [ Ar_1 - Ar_3 >= 0 /\ Ar_3 - 1 >= 0 /\ Ar_2 + Ar_3 - 1 >= 0 /\ Ar_1 + Ar_3 - 2 >= 0 /\ Ar_0 + Ar_3 - 2 >= 0 /\ -Ar_0 + Ar_3 >= 0 /\ Ar_2 >= 0 /\ Ar_1 + Ar_2 - 1 >= 0 /\ Ar_0 + Ar_2 - 1 >= 0 /\ -Ar_0 + Ar_2 + 1 >= 0 /\ Ar_1 - 1 >= 0 /\ Ar_0 + Ar_1 - 2 >= 0 /\ -Ar_0 + Ar_1 >= 0 /\ -Ar_0 + 1 >= 0 /\ Ar_0 - 1 >= 0 ] (Comp: 5*Ar_0 + 2, Cost: 1) evalEx4bb3in(Ar_0, Ar_1, Ar_2, Ar_3) -> Com_1(evalEx4bb4in(Ar_2, Ar_3, Ar_2, Ar_3)) [ Ar_1 - Ar_3 >= 0 /\ Ar_3 - 1 >= 0 /\ Ar_2 + Ar_3 - 1 >= 0 /\ Ar_1 + Ar_3 - 2 >= 0 /\ Ar_0 + Ar_3 - 2 >= 0 /\ -Ar_0 + Ar_3 >= 0 /\ Ar_2 >= 0 /\ Ar_1 + Ar_2 - 1 >= 0 /\ Ar_0 + Ar_2 - 1 >= 0 /\ -Ar_0 + Ar_2 + 1 >= 0 /\ Ar_1 - 1 >= 0 /\ Ar_0 + Ar_1 - 2 >= 0 /\ -Ar_0 + Ar_1 >= 0 /\ -Ar_0 + 1 >= 0 /\ Ar_0 - 1 >= 0 ] (Comp: 5*Ar_0 + 2, Cost: 1) evalEx4bb3in(Ar_0, Ar_1, Ar_2, Ar_3) -> Com_1(evalEx4bb1in(Ar_0, Ar_1, Ar_2, Ar_3)) [ Ar_1 - Ar_3 >= 0 /\ Ar_3 - 1 >= 0 /\ Ar_2 + Ar_3 - 1 >= 0 /\ Ar_1 + Ar_3 - 2 >= 0 /\ Ar_0 + Ar_3 - 2 >= 0 /\ -Ar_0 + Ar_3 >= 0 /\ Ar_2 >= 0 /\ Ar_1 + Ar_2 - 1 >= 0 /\ Ar_0 + Ar_2 - 1 >= 0 /\ -Ar_0 + Ar_2 + 1 >= 0 /\ Ar_1 - 1 >= 0 /\ Ar_0 + Ar_1 - 2 >= 0 /\ -Ar_0 + Ar_1 >= 0 /\ -Ar_0 + 1 >= 0 /\ Ar_0 - 1 >= 0 /\ E >= 1 ] (Comp: 5*Ar_0 + 2, Cost: 1) evalEx4bb3in(Ar_0, Ar_1, Ar_2, Ar_3) -> Com_1(evalEx4bb1in(Ar_0, Ar_1, Ar_2, Ar_3)) [ Ar_1 - Ar_3 >= 0 /\ Ar_3 - 1 >= 0 /\ Ar_2 + Ar_3 - 1 >= 0 /\ Ar_1 + Ar_3 - 2 >= 0 /\ Ar_0 + Ar_3 - 2 >= 0 /\ -Ar_0 + Ar_3 >= 0 /\ Ar_2 >= 0 /\ Ar_1 + Ar_2 - 1 >= 0 /\ Ar_0 + Ar_2 - 1 >= 0 /\ -Ar_0 + Ar_2 + 1 >= 0 /\ Ar_1 - 1 >= 0 /\ Ar_0 + Ar_1 - 2 >= 0 /\ -Ar_0 + Ar_1 >= 0 /\ -Ar_0 + 1 >= 0 /\ Ar_0 - 1 >= 0 /\ 0 >= E + 1 ] (Comp: 5*Ar_0 + 2, Cost: 1) evalEx4bb2in(Ar_0, Ar_1, Ar_2, Ar_3) -> Com_1(evalEx4bb3in(Ar_0, Ar_1, Ar_2, Ar_3)) [ Ar_1 - Ar_3 >= 0 /\ Ar_2 >= 0 /\ Ar_0 + Ar_2 - 1 >= 0 /\ -Ar_0 + Ar_2 + 1 >= 0 /\ -Ar_0 + 1 >= 0 /\ Ar_0 - 1 >= 0 /\ Ar_3 >= 1 ] (Comp: ?, Cost: 1) evalEx4bb2in(Ar_0, Ar_1, Ar_2, Ar_3) -> Com_1(evalEx4bb4in(Ar_2, Ar_3, Ar_2, Ar_3)) [ Ar_1 - Ar_3 >= 0 /\ Ar_2 >= 0 /\ Ar_0 + Ar_2 - 1 >= 0 /\ -Ar_0 + Ar_2 + 1 >= 0 /\ -Ar_0 + 1 >= 0 /\ Ar_0 - 1 >= 0 /\ 0 >= Ar_3 ] (Comp: 2, Cost: 1) evalEx4bb4in(Ar_0, Ar_1, Ar_2, Ar_3) -> Com_1(evalEx4returnin(Ar_0, Ar_1, Ar_2, Ar_3)) [ Ar_0 >= 2 ] (Comp: 2, Cost: 1) evalEx4bb4in(Ar_0, Ar_1, Ar_2, Ar_3) -> Com_1(evalEx4returnin(Ar_0, Ar_1, Ar_2, Ar_3)) [ 0 >= Ar_0 ] (Comp: ?, Cost: 1) evalEx4bb4in(Ar_0, Ar_1, Ar_2, Ar_3) -> Com_1(evalEx4bb2in(Ar_0, Ar_1, 0, Ar_1)) [ Ar_0 = 1 ] (Comp: 1, Cost: 1) evalEx4entryin(Ar_0, Ar_1, Ar_2, Ar_3) -> Com_1(evalEx4bb4in(1, Ar_0, Ar_2, Ar_3)) (Comp: 1, Cost: 1) evalEx4start(Ar_0, Ar_1, Ar_2, Ar_3) -> Com_1(evalEx4entryin(Ar_0, Ar_1, Ar_2, Ar_3)) start location: koat_start leaf cost: 0 A polynomial rank function with Pol(evalEx4bb4in) = 2*V_1 Pol(evalEx4bb2in) = 2*V_3 + 1 and size complexities S("evalEx4start(Ar_0, Ar_1, Ar_2, Ar_3) -> Com_1(evalEx4entryin(Ar_0, Ar_1, Ar_2, Ar_3))", 0-0) = Ar_0 S("evalEx4start(Ar_0, Ar_1, Ar_2, Ar_3) -> Com_1(evalEx4entryin(Ar_0, Ar_1, Ar_2, Ar_3))", 0-1) = Ar_1 S("evalEx4start(Ar_0, Ar_1, Ar_2, Ar_3) -> Com_1(evalEx4entryin(Ar_0, Ar_1, Ar_2, Ar_3))", 0-2) = Ar_2 S("evalEx4start(Ar_0, Ar_1, Ar_2, Ar_3) -> Com_1(evalEx4entryin(Ar_0, Ar_1, Ar_2, Ar_3))", 0-3) = Ar_3 S("evalEx4entryin(Ar_0, Ar_1, Ar_2, Ar_3) -> Com_1(evalEx4bb4in(1, Ar_0, Ar_2, Ar_3))", 0-0) = 1 S("evalEx4entryin(Ar_0, Ar_1, Ar_2, Ar_3) -> Com_1(evalEx4bb4in(1, Ar_0, Ar_2, Ar_3))", 0-1) = Ar_0 S("evalEx4entryin(Ar_0, Ar_1, Ar_2, Ar_3) -> Com_1(evalEx4bb4in(1, Ar_0, Ar_2, Ar_3))", 0-2) = Ar_2 S("evalEx4entryin(Ar_0, Ar_1, Ar_2, Ar_3) -> Com_1(evalEx4bb4in(1, Ar_0, Ar_2, Ar_3))", 0-3) = Ar_3 S("evalEx4bb4in(Ar_0, Ar_1, Ar_2, Ar_3) -> Com_1(evalEx4bb2in(Ar_0, Ar_1, 0, Ar_1)) [ Ar_0 = 1 ]", 0-0) = 1 S("evalEx4bb4in(Ar_0, Ar_1, Ar_2, Ar_3) -> Com_1(evalEx4bb2in(Ar_0, Ar_1, 0, Ar_1)) [ Ar_0 = 1 ]", 0-1) = Ar_0 S("evalEx4bb4in(Ar_0, Ar_1, Ar_2, Ar_3) -> Com_1(evalEx4bb2in(Ar_0, Ar_1, 0, Ar_1)) [ Ar_0 = 1 ]", 0-2) = 0 S("evalEx4bb4in(Ar_0, Ar_1, Ar_2, Ar_3) -> Com_1(evalEx4bb2in(Ar_0, Ar_1, 0, Ar_1)) [ Ar_0 = 1 ]", 0-3) = Ar_0 S("evalEx4bb4in(Ar_0, Ar_1, Ar_2, Ar_3) -> Com_1(evalEx4returnin(Ar_0, Ar_1, Ar_2, Ar_3)) [ 0 >= Ar_0 ]", 0-0) = 1 S("evalEx4bb4in(Ar_0, Ar_1, Ar_2, Ar_3) -> Com_1(evalEx4returnin(Ar_0, Ar_1, Ar_2, Ar_3)) [ 0 >= Ar_0 ]", 0-1) = Ar_0 S("evalEx4bb4in(Ar_0, Ar_1, Ar_2, Ar_3) -> Com_1(evalEx4returnin(Ar_0, Ar_1, Ar_2, Ar_3)) [ 0 >= Ar_0 ]", 0-2) = 1 S("evalEx4bb4in(Ar_0, Ar_1, Ar_2, Ar_3) -> Com_1(evalEx4returnin(Ar_0, Ar_1, Ar_2, Ar_3)) [ 0 >= Ar_0 ]", 0-3) = Ar_0 S("evalEx4bb4in(Ar_0, Ar_1, Ar_2, Ar_3) -> Com_1(evalEx4returnin(Ar_0, Ar_1, Ar_2, Ar_3)) [ Ar_0 >= 2 ]", 0-0) = 1 S("evalEx4bb4in(Ar_0, Ar_1, Ar_2, Ar_3) -> Com_1(evalEx4returnin(Ar_0, Ar_1, Ar_2, Ar_3)) [ Ar_0 >= 2 ]", 0-1) = Ar_0 S("evalEx4bb4in(Ar_0, Ar_1, Ar_2, Ar_3) -> Com_1(evalEx4returnin(Ar_0, Ar_1, Ar_2, Ar_3)) [ Ar_0 >= 2 ]", 0-2) = 1 S("evalEx4bb4in(Ar_0, Ar_1, Ar_2, Ar_3) -> Com_1(evalEx4returnin(Ar_0, Ar_1, Ar_2, Ar_3)) [ Ar_0 >= 2 ]", 0-3) = Ar_0 S("evalEx4bb2in(Ar_0, Ar_1, Ar_2, Ar_3) -> Com_1(evalEx4bb4in(Ar_2, Ar_3, Ar_2, Ar_3)) [ Ar_1 - Ar_3 >= 0 /\\ Ar_2 >= 0 /\\ Ar_0 + Ar_2 - 1 >= 0 /\\ -Ar_0 + Ar_2 + 1 >= 0 /\\ -Ar_0 + 1 >= 0 /\\ Ar_0 - 1 >= 0 /\\ 0 >= Ar_3 ]", 0-0) = 1 S("evalEx4bb2in(Ar_0, Ar_1, Ar_2, Ar_3) -> Com_1(evalEx4bb4in(Ar_2, Ar_3, Ar_2, Ar_3)) [ Ar_1 - Ar_3 >= 0 /\\ Ar_2 >= 0 /\\ Ar_0 + Ar_2 - 1 >= 0 /\\ -Ar_0 + Ar_2 + 1 >= 0 /\\ -Ar_0 + 1 >= 0 /\\ Ar_0 - 1 >= 0 /\\ 0 >= Ar_3 ]", 0-1) = Ar_0 S("evalEx4bb2in(Ar_0, Ar_1, Ar_2, Ar_3) -> Com_1(evalEx4bb4in(Ar_2, Ar_3, Ar_2, Ar_3)) [ Ar_1 - Ar_3 >= 0 /\\ Ar_2 >= 0 /\\ Ar_0 + Ar_2 - 1 >= 0 /\\ -Ar_0 + Ar_2 + 1 >= 0 /\\ -Ar_0 + 1 >= 0 /\\ Ar_0 - 1 >= 0 /\\ 0 >= Ar_3 ]", 0-2) = 1 S("evalEx4bb2in(Ar_0, Ar_1, Ar_2, Ar_3) -> Com_1(evalEx4bb4in(Ar_2, Ar_3, Ar_2, Ar_3)) [ Ar_1 - Ar_3 >= 0 /\\ Ar_2 >= 0 /\\ Ar_0 + Ar_2 - 1 >= 0 /\\ -Ar_0 + Ar_2 + 1 >= 0 /\\ -Ar_0 + 1 >= 0 /\\ Ar_0 - 1 >= 0 /\\ 0 >= Ar_3 ]", 0-3) = Ar_0 S("evalEx4bb2in(Ar_0, Ar_1, Ar_2, Ar_3) -> Com_1(evalEx4bb3in(Ar_0, Ar_1, Ar_2, Ar_3)) [ Ar_1 - Ar_3 >= 0 /\\ Ar_2 >= 0 /\\ Ar_0 + Ar_2 - 1 >= 0 /\\ -Ar_0 + Ar_2 + 1 >= 0 /\\ -Ar_0 + 1 >= 0 /\\ Ar_0 - 1 >= 0 /\\ Ar_3 >= 1 ]", 0-0) = 1 S("evalEx4bb2in(Ar_0, Ar_1, Ar_2, Ar_3) -> Com_1(evalEx4bb3in(Ar_0, Ar_1, Ar_2, Ar_3)) [ Ar_1 - Ar_3 >= 0 /\\ Ar_2 >= 0 /\\ Ar_0 + Ar_2 - 1 >= 0 /\\ -Ar_0 + Ar_2 + 1 >= 0 /\\ -Ar_0 + 1 >= 0 /\\ Ar_0 - 1 >= 0 /\\ Ar_3 >= 1 ]", 0-1) = Ar_0 S("evalEx4bb2in(Ar_0, Ar_1, Ar_2, Ar_3) -> Com_1(evalEx4bb3in(Ar_0, Ar_1, Ar_2, Ar_3)) [ Ar_1 - Ar_3 >= 0 /\\ Ar_2 >= 0 /\\ Ar_0 + Ar_2 - 1 >= 0 /\\ -Ar_0 + Ar_2 + 1 >= 0 /\\ -Ar_0 + 1 >= 0 /\\ Ar_0 - 1 >= 0 /\\ Ar_3 >= 1 ]", 0-2) = 1 S("evalEx4bb2in(Ar_0, Ar_1, Ar_2, Ar_3) -> Com_1(evalEx4bb3in(Ar_0, Ar_1, Ar_2, Ar_3)) [ Ar_1 - Ar_3 >= 0 /\\ Ar_2 >= 0 /\\ Ar_0 + Ar_2 - 1 >= 0 /\\ -Ar_0 + Ar_2 + 1 >= 0 /\\ -Ar_0 + 1 >= 0 /\\ Ar_0 - 1 >= 0 /\\ Ar_3 >= 1 ]", 0-3) = Ar_0 S("evalEx4bb3in(Ar_0, Ar_1, Ar_2, Ar_3) -> Com_1(evalEx4bb1in(Ar_0, Ar_1, Ar_2, Ar_3)) [ Ar_1 - Ar_3 >= 0 /\\ Ar_3 - 1 >= 0 /\\ Ar_2 + Ar_3 - 1 >= 0 /\\ Ar_1 + Ar_3 - 2 >= 0 /\\ Ar_0 + Ar_3 - 2 >= 0 /\\ -Ar_0 + Ar_3 >= 0 /\\ Ar_2 >= 0 /\\ Ar_1 + Ar_2 - 1 >= 0 /\\ Ar_0 + Ar_2 - 1 >= 0 /\\ -Ar_0 + Ar_2 + 1 >= 0 /\\ Ar_1 - 1 >= 0 /\\ Ar_0 + Ar_1 - 2 >= 0 /\\ -Ar_0 + Ar_1 >= 0 /\\ -Ar_0 + 1 >= 0 /\\ Ar_0 - 1 >= 0 /\\ 0 >= E + 1 ]", 0-0) = 1 S("evalEx4bb3in(Ar_0, Ar_1, Ar_2, Ar_3) -> Com_1(evalEx4bb1in(Ar_0, Ar_1, Ar_2, Ar_3)) [ Ar_1 - Ar_3 >= 0 /\\ Ar_3 - 1 >= 0 /\\ Ar_2 + Ar_3 - 1 >= 0 /\\ Ar_1 + Ar_3 - 2 >= 0 /\\ Ar_0 + Ar_3 - 2 >= 0 /\\ -Ar_0 + Ar_3 >= 0 /\\ Ar_2 >= 0 /\\ Ar_1 + Ar_2 - 1 >= 0 /\\ Ar_0 + Ar_2 - 1 >= 0 /\\ -Ar_0 + Ar_2 + 1 >= 0 /\\ Ar_1 - 1 >= 0 /\\ Ar_0 + Ar_1 - 2 >= 0 /\\ -Ar_0 + Ar_1 >= 0 /\\ -Ar_0 + 1 >= 0 /\\ Ar_0 - 1 >= 0 /\\ 0 >= E + 1 ]", 0-1) = Ar_0 S("evalEx4bb3in(Ar_0, Ar_1, Ar_2, Ar_3) -> Com_1(evalEx4bb1in(Ar_0, Ar_1, Ar_2, Ar_3)) [ Ar_1 - Ar_3 >= 0 /\\ Ar_3 - 1 >= 0 /\\ Ar_2 + Ar_3 - 1 >= 0 /\\ Ar_1 + Ar_3 - 2 >= 0 /\\ Ar_0 + Ar_3 - 2 >= 0 /\\ -Ar_0 + Ar_3 >= 0 /\\ Ar_2 >= 0 /\\ Ar_1 + Ar_2 - 1 >= 0 /\\ Ar_0 + Ar_2 - 1 >= 0 /\\ -Ar_0 + Ar_2 + 1 >= 0 /\\ Ar_1 - 1 >= 0 /\\ Ar_0 + Ar_1 - 2 >= 0 /\\ -Ar_0 + Ar_1 >= 0 /\\ -Ar_0 + 1 >= 0 /\\ Ar_0 - 1 >= 0 /\\ 0 >= E + 1 ]", 0-2) = 1 S("evalEx4bb3in(Ar_0, Ar_1, Ar_2, Ar_3) -> Com_1(evalEx4bb1in(Ar_0, Ar_1, Ar_2, Ar_3)) [ Ar_1 - Ar_3 >= 0 /\\ Ar_3 - 1 >= 0 /\\ Ar_2 + Ar_3 - 1 >= 0 /\\ Ar_1 + Ar_3 - 2 >= 0 /\\ Ar_0 + Ar_3 - 2 >= 0 /\\ -Ar_0 + Ar_3 >= 0 /\\ Ar_2 >= 0 /\\ Ar_1 + Ar_2 - 1 >= 0 /\\ Ar_0 + Ar_2 - 1 >= 0 /\\ -Ar_0 + Ar_2 + 1 >= 0 /\\ Ar_1 - 1 >= 0 /\\ Ar_0 + Ar_1 - 2 >= 0 /\\ -Ar_0 + Ar_1 >= 0 /\\ -Ar_0 + 1 >= 0 /\\ Ar_0 - 1 >= 0 /\\ 0 >= E + 1 ]", 0-3) = Ar_0 S("evalEx4bb3in(Ar_0, Ar_1, Ar_2, Ar_3) -> Com_1(evalEx4bb1in(Ar_0, Ar_1, Ar_2, Ar_3)) [ Ar_1 - Ar_3 >= 0 /\\ Ar_3 - 1 >= 0 /\\ Ar_2 + Ar_3 - 1 >= 0 /\\ Ar_1 + Ar_3 - 2 >= 0 /\\ Ar_0 + Ar_3 - 2 >= 0 /\\ -Ar_0 + Ar_3 >= 0 /\\ Ar_2 >= 0 /\\ Ar_1 + Ar_2 - 1 >= 0 /\\ Ar_0 + Ar_2 - 1 >= 0 /\\ -Ar_0 + Ar_2 + 1 >= 0 /\\ Ar_1 - 1 >= 0 /\\ Ar_0 + Ar_1 - 2 >= 0 /\\ -Ar_0 + Ar_1 >= 0 /\\ -Ar_0 + 1 >= 0 /\\ Ar_0 - 1 >= 0 /\\ E >= 1 ]", 0-0) = 1 S("evalEx4bb3in(Ar_0, Ar_1, Ar_2, Ar_3) -> Com_1(evalEx4bb1in(Ar_0, Ar_1, Ar_2, Ar_3)) [ Ar_1 - Ar_3 >= 0 /\\ Ar_3 - 1 >= 0 /\\ Ar_2 + Ar_3 - 1 >= 0 /\\ Ar_1 + Ar_3 - 2 >= 0 /\\ Ar_0 + Ar_3 - 2 >= 0 /\\ -Ar_0 + Ar_3 >= 0 /\\ Ar_2 >= 0 /\\ Ar_1 + Ar_2 - 1 >= 0 /\\ Ar_0 + Ar_2 - 1 >= 0 /\\ -Ar_0 + Ar_2 + 1 >= 0 /\\ Ar_1 - 1 >= 0 /\\ Ar_0 + Ar_1 - 2 >= 0 /\\ -Ar_0 + Ar_1 >= 0 /\\ -Ar_0 + 1 >= 0 /\\ Ar_0 - 1 >= 0 /\\ E >= 1 ]", 0-1) = Ar_0 S("evalEx4bb3in(Ar_0, Ar_1, Ar_2, Ar_3) -> Com_1(evalEx4bb1in(Ar_0, Ar_1, Ar_2, Ar_3)) [ Ar_1 - Ar_3 >= 0 /\\ Ar_3 - 1 >= 0 /\\ Ar_2 + Ar_3 - 1 >= 0 /\\ Ar_1 + Ar_3 - 2 >= 0 /\\ Ar_0 + Ar_3 - 2 >= 0 /\\ -Ar_0 + Ar_3 >= 0 /\\ Ar_2 >= 0 /\\ Ar_1 + Ar_2 - 1 >= 0 /\\ Ar_0 + Ar_2 - 1 >= 0 /\\ -Ar_0 + Ar_2 + 1 >= 0 /\\ Ar_1 - 1 >= 0 /\\ Ar_0 + Ar_1 - 2 >= 0 /\\ -Ar_0 + Ar_1 >= 0 /\\ -Ar_0 + 1 >= 0 /\\ Ar_0 - 1 >= 0 /\\ E >= 1 ]", 0-2) = 1 S("evalEx4bb3in(Ar_0, Ar_1, Ar_2, Ar_3) -> Com_1(evalEx4bb1in(Ar_0, Ar_1, Ar_2, Ar_3)) [ Ar_1 - Ar_3 >= 0 /\\ Ar_3 - 1 >= 0 /\\ Ar_2 + Ar_3 - 1 >= 0 /\\ Ar_1 + Ar_3 - 2 >= 0 /\\ Ar_0 + Ar_3 - 2 >= 0 /\\ -Ar_0 + Ar_3 >= 0 /\\ Ar_2 >= 0 /\\ Ar_1 + Ar_2 - 1 >= 0 /\\ Ar_0 + Ar_2 - 1 >= 0 /\\ -Ar_0 + Ar_2 + 1 >= 0 /\\ Ar_1 - 1 >= 0 /\\ Ar_0 + Ar_1 - 2 >= 0 /\\ -Ar_0 + Ar_1 >= 0 /\\ -Ar_0 + 1 >= 0 /\\ Ar_0 - 1 >= 0 /\\ E >= 1 ]", 0-3) = Ar_0 S("evalEx4bb3in(Ar_0, Ar_1, Ar_2, Ar_3) -> Com_1(evalEx4bb4in(Ar_2, Ar_3, Ar_2, Ar_3)) [ Ar_1 - Ar_3 >= 0 /\\ Ar_3 - 1 >= 0 /\\ Ar_2 + Ar_3 - 1 >= 0 /\\ Ar_1 + Ar_3 - 2 >= 0 /\\ Ar_0 + Ar_3 - 2 >= 0 /\\ -Ar_0 + Ar_3 >= 0 /\\ Ar_2 >= 0 /\\ Ar_1 + Ar_2 - 1 >= 0 /\\ Ar_0 + Ar_2 - 1 >= 0 /\\ -Ar_0 + Ar_2 + 1 >= 0 /\\ Ar_1 - 1 >= 0 /\\ Ar_0 + Ar_1 - 2 >= 0 /\\ -Ar_0 + Ar_1 >= 0 /\\ -Ar_0 + 1 >= 0 /\\ Ar_0 - 1 >= 0 ]", 0-0) = 1 S("evalEx4bb3in(Ar_0, Ar_1, Ar_2, Ar_3) -> Com_1(evalEx4bb4in(Ar_2, Ar_3, Ar_2, Ar_3)) [ Ar_1 - Ar_3 >= 0 /\\ Ar_3 - 1 >= 0 /\\ Ar_2 + Ar_3 - 1 >= 0 /\\ Ar_1 + Ar_3 - 2 >= 0 /\\ Ar_0 + Ar_3 - 2 >= 0 /\\ -Ar_0 + Ar_3 >= 0 /\\ Ar_2 >= 0 /\\ Ar_1 + Ar_2 - 1 >= 0 /\\ Ar_0 + Ar_2 - 1 >= 0 /\\ -Ar_0 + Ar_2 + 1 >= 0 /\\ Ar_1 - 1 >= 0 /\\ Ar_0 + Ar_1 - 2 >= 0 /\\ -Ar_0 + Ar_1 >= 0 /\\ -Ar_0 + 1 >= 0 /\\ Ar_0 - 1 >= 0 ]", 0-1) = Ar_0 S("evalEx4bb3in(Ar_0, Ar_1, Ar_2, Ar_3) -> Com_1(evalEx4bb4in(Ar_2, Ar_3, Ar_2, Ar_3)) [ Ar_1 - Ar_3 >= 0 /\\ Ar_3 - 1 >= 0 /\\ Ar_2 + Ar_3 - 1 >= 0 /\\ Ar_1 + Ar_3 - 2 >= 0 /\\ Ar_0 + Ar_3 - 2 >= 0 /\\ -Ar_0 + Ar_3 >= 0 /\\ Ar_2 >= 0 /\\ Ar_1 + Ar_2 - 1 >= 0 /\\ Ar_0 + Ar_2 - 1 >= 0 /\\ -Ar_0 + Ar_2 + 1 >= 0 /\\ Ar_1 - 1 >= 0 /\\ Ar_0 + Ar_1 - 2 >= 0 /\\ -Ar_0 + Ar_1 >= 0 /\\ -Ar_0 + 1 >= 0 /\\ Ar_0 - 1 >= 0 ]", 0-2) = 1 S("evalEx4bb3in(Ar_0, Ar_1, Ar_2, Ar_3) -> Com_1(evalEx4bb4in(Ar_2, Ar_3, Ar_2, Ar_3)) [ Ar_1 - Ar_3 >= 0 /\\ Ar_3 - 1 >= 0 /\\ Ar_2 + Ar_3 - 1 >= 0 /\\ Ar_1 + Ar_3 - 2 >= 0 /\\ Ar_0 + Ar_3 - 2 >= 0 /\\ -Ar_0 + Ar_3 >= 0 /\\ Ar_2 >= 0 /\\ Ar_1 + Ar_2 - 1 >= 0 /\\ Ar_0 + Ar_2 - 1 >= 0 /\\ -Ar_0 + Ar_2 + 1 >= 0 /\\ Ar_1 - 1 >= 0 /\\ Ar_0 + Ar_1 - 2 >= 0 /\\ -Ar_0 + Ar_1 >= 0 /\\ -Ar_0 + 1 >= 0 /\\ Ar_0 - 1 >= 0 ]", 0-3) = Ar_0 S("evalEx4bb1in(Ar_0, Ar_1, Ar_2, Ar_3) -> Com_1(evalEx4bb2in(Ar_0, Ar_1, 1, Ar_3 - 1)) [ Ar_1 - Ar_3 >= 0 /\\ Ar_3 - 1 >= 0 /\\ Ar_2 + Ar_3 - 1 >= 0 /\\ Ar_1 + Ar_3 - 2 >= 0 /\\ Ar_0 + Ar_3 - 2 >= 0 /\\ -Ar_0 + Ar_3 >= 0 /\\ Ar_2 >= 0 /\\ Ar_1 + Ar_2 - 1 >= 0 /\\ Ar_0 + Ar_2 - 1 >= 0 /\\ -Ar_0 + Ar_2 + 1 >= 0 /\\ Ar_1 - 1 >= 0 /\\ Ar_0 + Ar_1 - 2 >= 0 /\\ -Ar_0 + Ar_1 >= 0 /\\ -Ar_0 + 1 >= 0 /\\ Ar_0 - 1 >= 0 ]", 0-0) = 1 S("evalEx4bb1in(Ar_0, Ar_1, Ar_2, Ar_3) -> Com_1(evalEx4bb2in(Ar_0, Ar_1, 1, Ar_3 - 1)) [ Ar_1 - Ar_3 >= 0 /\\ Ar_3 - 1 >= 0 /\\ Ar_2 + Ar_3 - 1 >= 0 /\\ Ar_1 + Ar_3 - 2 >= 0 /\\ Ar_0 + Ar_3 - 2 >= 0 /\\ -Ar_0 + Ar_3 >= 0 /\\ Ar_2 >= 0 /\\ Ar_1 + Ar_2 - 1 >= 0 /\\ Ar_0 + Ar_2 - 1 >= 0 /\\ -Ar_0 + Ar_2 + 1 >= 0 /\\ Ar_1 - 1 >= 0 /\\ Ar_0 + Ar_1 - 2 >= 0 /\\ -Ar_0 + Ar_1 >= 0 /\\ -Ar_0 + 1 >= 0 /\\ Ar_0 - 1 >= 0 ]", 0-1) = Ar_0 S("evalEx4bb1in(Ar_0, Ar_1, Ar_2, Ar_3) -> Com_1(evalEx4bb2in(Ar_0, Ar_1, 1, Ar_3 - 1)) [ Ar_1 - Ar_3 >= 0 /\\ Ar_3 - 1 >= 0 /\\ Ar_2 + Ar_3 - 1 >= 0 /\\ Ar_1 + Ar_3 - 2 >= 0 /\\ Ar_0 + Ar_3 - 2 >= 0 /\\ -Ar_0 + Ar_3 >= 0 /\\ Ar_2 >= 0 /\\ Ar_1 + Ar_2 - 1 >= 0 /\\ Ar_0 + Ar_2 - 1 >= 0 /\\ -Ar_0 + Ar_2 + 1 >= 0 /\\ Ar_1 - 1 >= 0 /\\ Ar_0 + Ar_1 - 2 >= 0 /\\ -Ar_0 + Ar_1 >= 0 /\\ -Ar_0 + 1 >= 0 /\\ Ar_0 - 1 >= 0 ]", 0-2) = 1 S("evalEx4bb1in(Ar_0, Ar_1, Ar_2, Ar_3) -> Com_1(evalEx4bb2in(Ar_0, Ar_1, 1, Ar_3 - 1)) [ Ar_1 - Ar_3 >= 0 /\\ Ar_3 - 1 >= 0 /\\ Ar_2 + Ar_3 - 1 >= 0 /\\ Ar_1 + Ar_3 - 2 >= 0 /\\ Ar_0 + Ar_3 - 2 >= 0 /\\ -Ar_0 + Ar_3 >= 0 /\\ Ar_2 >= 0 /\\ Ar_1 + Ar_2 - 1 >= 0 /\\ Ar_0 + Ar_2 - 1 >= 0 /\\ -Ar_0 + Ar_2 + 1 >= 0 /\\ Ar_1 - 1 >= 0 /\\ Ar_0 + Ar_1 - 2 >= 0 /\\ -Ar_0 + Ar_1 >= 0 /\\ -Ar_0 + 1 >= 0 /\\ Ar_0 - 1 >= 0 ]", 0-3) = Ar_0 S("evalEx4returnin(Ar_0, Ar_1, Ar_2, Ar_3) -> Com_1(evalEx4stop(Ar_0, Ar_1, Ar_2, Ar_3))", 0-0) = 1 S("evalEx4returnin(Ar_0, Ar_1, Ar_2, Ar_3) -> Com_1(evalEx4stop(Ar_0, Ar_1, Ar_2, Ar_3))", 0-1) = Ar_0 S("evalEx4returnin(Ar_0, Ar_1, Ar_2, Ar_3) -> Com_1(evalEx4stop(Ar_0, Ar_1, Ar_2, Ar_3))", 0-2) = 1 S("evalEx4returnin(Ar_0, Ar_1, Ar_2, Ar_3) -> Com_1(evalEx4stop(Ar_0, Ar_1, Ar_2, Ar_3))", 0-3) = Ar_0 S("koat_start(Ar_0, Ar_1, Ar_2, Ar_3) -> Com_1(evalEx4start(Ar_0, Ar_1, Ar_2, Ar_3)) [ 0 <= 0 ]", 0-0) = Ar_0 S("koat_start(Ar_0, Ar_1, Ar_2, Ar_3) -> Com_1(evalEx4start(Ar_0, Ar_1, Ar_2, Ar_3)) [ 0 <= 0 ]", 0-1) = Ar_1 S("koat_start(Ar_0, Ar_1, Ar_2, Ar_3) -> Com_1(evalEx4start(Ar_0, Ar_1, Ar_2, Ar_3)) [ 0 <= 0 ]", 0-2) = Ar_2 S("koat_start(Ar_0, Ar_1, Ar_2, Ar_3) -> Com_1(evalEx4start(Ar_0, Ar_1, Ar_2, Ar_3)) [ 0 <= 0 ]", 0-3) = Ar_3 orients the transitions evalEx4bb4in(Ar_0, Ar_1, Ar_2, Ar_3) -> Com_1(evalEx4bb2in(Ar_0, Ar_1, 0, Ar_1)) [ Ar_0 = 1 ] evalEx4bb2in(Ar_0, Ar_1, Ar_2, Ar_3) -> Com_1(evalEx4bb4in(Ar_2, Ar_3, Ar_2, Ar_3)) [ Ar_1 - Ar_3 >= 0 /\ Ar_2 >= 0 /\ Ar_0 + Ar_2 - 1 >= 0 /\ -Ar_0 + Ar_2 + 1 >= 0 /\ -Ar_0 + 1 >= 0 /\ Ar_0 - 1 >= 0 /\ 0 >= Ar_3 ] weakly and the transitions evalEx4bb4in(Ar_0, Ar_1, Ar_2, Ar_3) -> Com_1(evalEx4bb2in(Ar_0, Ar_1, 0, Ar_1)) [ Ar_0 = 1 ] evalEx4bb2in(Ar_0, Ar_1, Ar_2, Ar_3) -> Com_1(evalEx4bb4in(Ar_2, Ar_3, Ar_2, Ar_3)) [ Ar_1 - Ar_3 >= 0 /\ Ar_2 >= 0 /\ Ar_0 + Ar_2 - 1 >= 0 /\ -Ar_0 + Ar_2 + 1 >= 0 /\ -Ar_0 + 1 >= 0 /\ Ar_0 - 1 >= 0 /\ 0 >= Ar_3 ] strictly and produces the following problem: 6: T: (Comp: 1, Cost: 0) koat_start(Ar_0, Ar_1, Ar_2, Ar_3) -> Com_1(evalEx4start(Ar_0, Ar_1, Ar_2, Ar_3)) [ 0 <= 0 ] (Comp: 2, Cost: 1) evalEx4returnin(Ar_0, Ar_1, Ar_2, Ar_3) -> Com_1(evalEx4stop(Ar_0, Ar_1, Ar_2, Ar_3)) (Comp: 5*Ar_0 + 2, Cost: 1) evalEx4bb1in(Ar_0, Ar_1, Ar_2, Ar_3) -> Com_1(evalEx4bb2in(Ar_0, Ar_1, 1, Ar_3 - 1)) [ Ar_1 - Ar_3 >= 0 /\ Ar_3 - 1 >= 0 /\ Ar_2 + Ar_3 - 1 >= 0 /\ Ar_1 + Ar_3 - 2 >= 0 /\ Ar_0 + Ar_3 - 2 >= 0 /\ -Ar_0 + Ar_3 >= 0 /\ Ar_2 >= 0 /\ Ar_1 + Ar_2 - 1 >= 0 /\ Ar_0 + Ar_2 - 1 >= 0 /\ -Ar_0 + Ar_2 + 1 >= 0 /\ Ar_1 - 1 >= 0 /\ Ar_0 + Ar_1 - 2 >= 0 /\ -Ar_0 + Ar_1 >= 0 /\ -Ar_0 + 1 >= 0 /\ Ar_0 - 1 >= 0 ] (Comp: 5*Ar_0 + 2, Cost: 1) evalEx4bb3in(Ar_0, Ar_1, Ar_2, Ar_3) -> Com_1(evalEx4bb4in(Ar_2, Ar_3, Ar_2, Ar_3)) [ Ar_1 - Ar_3 >= 0 /\ Ar_3 - 1 >= 0 /\ Ar_2 + Ar_3 - 1 >= 0 /\ Ar_1 + Ar_3 - 2 >= 0 /\ Ar_0 + Ar_3 - 2 >= 0 /\ -Ar_0 + Ar_3 >= 0 /\ Ar_2 >= 0 /\ Ar_1 + Ar_2 - 1 >= 0 /\ Ar_0 + Ar_2 - 1 >= 0 /\ -Ar_0 + Ar_2 + 1 >= 0 /\ Ar_1 - 1 >= 0 /\ Ar_0 + Ar_1 - 2 >= 0 /\ -Ar_0 + Ar_1 >= 0 /\ -Ar_0 + 1 >= 0 /\ Ar_0 - 1 >= 0 ] (Comp: 5*Ar_0 + 2, Cost: 1) evalEx4bb3in(Ar_0, Ar_1, Ar_2, Ar_3) -> Com_1(evalEx4bb1in(Ar_0, Ar_1, Ar_2, Ar_3)) [ Ar_1 - Ar_3 >= 0 /\ Ar_3 - 1 >= 0 /\ Ar_2 + Ar_3 - 1 >= 0 /\ Ar_1 + Ar_3 - 2 >= 0 /\ Ar_0 + Ar_3 - 2 >= 0 /\ -Ar_0 + Ar_3 >= 0 /\ Ar_2 >= 0 /\ Ar_1 + Ar_2 - 1 >= 0 /\ Ar_0 + Ar_2 - 1 >= 0 /\ -Ar_0 + Ar_2 + 1 >= 0 /\ Ar_1 - 1 >= 0 /\ Ar_0 + Ar_1 - 2 >= 0 /\ -Ar_0 + Ar_1 >= 0 /\ -Ar_0 + 1 >= 0 /\ Ar_0 - 1 >= 0 /\ E >= 1 ] (Comp: 5*Ar_0 + 2, Cost: 1) evalEx4bb3in(Ar_0, Ar_1, Ar_2, Ar_3) -> Com_1(evalEx4bb1in(Ar_0, Ar_1, Ar_2, Ar_3)) [ Ar_1 - Ar_3 >= 0 /\ Ar_3 - 1 >= 0 /\ Ar_2 + Ar_3 - 1 >= 0 /\ Ar_1 + Ar_3 - 2 >= 0 /\ Ar_0 + Ar_3 - 2 >= 0 /\ -Ar_0 + Ar_3 >= 0 /\ Ar_2 >= 0 /\ Ar_1 + Ar_2 - 1 >= 0 /\ Ar_0 + Ar_2 - 1 >= 0 /\ -Ar_0 + Ar_2 + 1 >= 0 /\ Ar_1 - 1 >= 0 /\ Ar_0 + Ar_1 - 2 >= 0 /\ -Ar_0 + Ar_1 >= 0 /\ -Ar_0 + 1 >= 0 /\ Ar_0 - 1 >= 0 /\ 0 >= E + 1 ] (Comp: 5*Ar_0 + 2, Cost: 1) evalEx4bb2in(Ar_0, Ar_1, Ar_2, Ar_3) -> Com_1(evalEx4bb3in(Ar_0, Ar_1, Ar_2, Ar_3)) [ Ar_1 - Ar_3 >= 0 /\ Ar_2 >= 0 /\ Ar_0 + Ar_2 - 1 >= 0 /\ -Ar_0 + Ar_2 + 1 >= 0 /\ -Ar_0 + 1 >= 0 /\ Ar_0 - 1 >= 0 /\ Ar_3 >= 1 ] (Comp: 25*Ar_0 + 12, Cost: 1) evalEx4bb2in(Ar_0, Ar_1, Ar_2, Ar_3) -> Com_1(evalEx4bb4in(Ar_2, Ar_3, Ar_2, Ar_3)) [ Ar_1 - Ar_3 >= 0 /\ Ar_2 >= 0 /\ Ar_0 + Ar_2 - 1 >= 0 /\ -Ar_0 + Ar_2 + 1 >= 0 /\ -Ar_0 + 1 >= 0 /\ Ar_0 - 1 >= 0 /\ 0 >= Ar_3 ] (Comp: 2, Cost: 1) evalEx4bb4in(Ar_0, Ar_1, Ar_2, Ar_3) -> Com_1(evalEx4returnin(Ar_0, Ar_1, Ar_2, Ar_3)) [ Ar_0 >= 2 ] (Comp: 2, Cost: 1) evalEx4bb4in(Ar_0, Ar_1, Ar_2, Ar_3) -> Com_1(evalEx4returnin(Ar_0, Ar_1, Ar_2, Ar_3)) [ 0 >= Ar_0 ] (Comp: 25*Ar_0 + 12, Cost: 1) evalEx4bb4in(Ar_0, Ar_1, Ar_2, Ar_3) -> Com_1(evalEx4bb2in(Ar_0, Ar_1, 0, Ar_1)) [ Ar_0 = 1 ] (Comp: 1, Cost: 1) evalEx4entryin(Ar_0, Ar_1, Ar_2, Ar_3) -> Com_1(evalEx4bb4in(1, Ar_0, Ar_2, Ar_3)) (Comp: 1, Cost: 1) evalEx4start(Ar_0, Ar_1, Ar_2, Ar_3) -> Com_1(evalEx4entryin(Ar_0, Ar_1, Ar_2, Ar_3)) start location: koat_start leaf cost: 0 Complexity upper bound 75*Ar_0 + 42 Time: 0.356 sec (SMT: 0.277 sec) ---------------------------------------- (2) BOUNDS(1, n^1) ---------------------------------------- (3) Loat Proof (FINISHED) ### Pre-processing the ITS problem ### Initial linear ITS problem Start location: evalEx4start 0: evalEx4start -> evalEx4entryin : [], cost: 1 1: evalEx4entryin -> evalEx4bb4in : A'=1, B'=A, [], cost: 1 2: evalEx4bb4in -> evalEx4bb2in : C'=0, D'=B, [ A==1 ], cost: 1 3: evalEx4bb4in -> evalEx4returnin : [ 0>=A ], cost: 1 4: evalEx4bb4in -> evalEx4returnin : [ A>=2 ], cost: 1 5: evalEx4bb2in -> evalEx4bb4in : A'=C, B'=D, [ 0>=D ], cost: 1 6: evalEx4bb2in -> evalEx4bb3in : [ D>=1 ], cost: 1 7: evalEx4bb3in -> evalEx4bb1in : [ 0>=1+free ], cost: 1 8: evalEx4bb3in -> evalEx4bb1in : [ free_1>=1 ], cost: 1 9: evalEx4bb3in -> evalEx4bb4in : A'=C, B'=D, [], cost: 1 10: evalEx4bb1in -> evalEx4bb2in : C'=1, D'=-1+D, [], cost: 1 11: evalEx4returnin -> evalEx4stop : [], cost: 1 Checking for constant complexity: The following rule is satisfiable with cost >= 1, yielding constant complexity: 0: evalEx4start -> evalEx4entryin : [], cost: 1 Removed unreachable and leaf rules: Start location: evalEx4start 0: evalEx4start -> evalEx4entryin : [], cost: 1 1: evalEx4entryin -> evalEx4bb4in : A'=1, B'=A, [], cost: 1 2: evalEx4bb4in -> evalEx4bb2in : C'=0, D'=B, [ A==1 ], cost: 1 5: evalEx4bb2in -> evalEx4bb4in : A'=C, B'=D, [ 0>=D ], cost: 1 6: evalEx4bb2in -> evalEx4bb3in : [ D>=1 ], cost: 1 7: evalEx4bb3in -> evalEx4bb1in : [ 0>=1+free ], cost: 1 8: evalEx4bb3in -> evalEx4bb1in : [ free_1>=1 ], cost: 1 9: evalEx4bb3in -> evalEx4bb4in : A'=C, B'=D, [], cost: 1 10: evalEx4bb1in -> evalEx4bb2in : C'=1, D'=-1+D, [], cost: 1 Simplified all rules, resulting in: Start location: evalEx4start 0: evalEx4start -> evalEx4entryin : [], cost: 1 1: evalEx4entryin -> evalEx4bb4in : A'=1, B'=A, [], cost: 1 2: evalEx4bb4in -> evalEx4bb2in : C'=0, D'=B, [ A==1 ], cost: 1 5: evalEx4bb2in -> evalEx4bb4in : A'=C, B'=D, [ 0>=D ], cost: 1 6: evalEx4bb2in -> evalEx4bb3in : [ D>=1 ], cost: 1 8: evalEx4bb3in -> evalEx4bb1in : [], cost: 1 9: evalEx4bb3in -> evalEx4bb4in : A'=C, B'=D, [], cost: 1 10: evalEx4bb1in -> evalEx4bb2in : C'=1, D'=-1+D, [], cost: 1 ### Simplification by acceleration and chaining ### Eliminated locations (on linear paths): Start location: evalEx4start 12: evalEx4start -> evalEx4bb4in : A'=1, B'=A, [], cost: 2 2: evalEx4bb4in -> evalEx4bb2in : C'=0, D'=B, [ A==1 ], cost: 1 5: evalEx4bb2in -> evalEx4bb4in : A'=C, B'=D, [ 0>=D ], cost: 1 6: evalEx4bb2in -> evalEx4bb3in : [ D>=1 ], cost: 1 9: evalEx4bb3in -> evalEx4bb4in : A'=C, B'=D, [], cost: 1 13: evalEx4bb3in -> evalEx4bb2in : C'=1, D'=-1+D, [], cost: 2 Eliminated locations (on tree-shaped paths): Start location: evalEx4start 12: evalEx4start -> evalEx4bb4in : A'=1, B'=A, [], cost: 2 2: evalEx4bb4in -> evalEx4bb2in : C'=0, D'=B, [ A==1 ], cost: 1 5: evalEx4bb2in -> evalEx4bb4in : A'=C, B'=D, [ 0>=D ], cost: 1 14: evalEx4bb2in -> evalEx4bb4in : A'=C, B'=D, [ D>=1 ], cost: 2 15: evalEx4bb2in -> evalEx4bb2in : C'=1, D'=-1+D, [ D>=1 ], cost: 3 Accelerating simple loops of location 3. Accelerating the following rules: 15: evalEx4bb2in -> evalEx4bb2in : C'=1, D'=-1+D, [ D>=1 ], cost: 3 Accelerated rule 15 with metering function D, yielding the new rule 16. Removing the simple loops: 15. Accelerated all simple loops using metering functions (where possible): Start location: evalEx4start 12: evalEx4start -> evalEx4bb4in : A'=1, B'=A, [], cost: 2 2: evalEx4bb4in -> evalEx4bb2in : C'=0, D'=B, [ A==1 ], cost: 1 5: evalEx4bb2in -> evalEx4bb4in : A'=C, B'=D, [ 0>=D ], cost: 1 14: evalEx4bb2in -> evalEx4bb4in : A'=C, B'=D, [ D>=1 ], cost: 2 16: evalEx4bb2in -> evalEx4bb2in : C'=1, D'=0, [ D>=1 ], cost: 3*D Chained accelerated rules (with incoming rules): Start location: evalEx4start 12: evalEx4start -> evalEx4bb4in : A'=1, B'=A, [], cost: 2 2: evalEx4bb4in -> evalEx4bb2in : C'=0, D'=B, [ A==1 ], cost: 1 17: evalEx4bb4in -> evalEx4bb2in : C'=1, D'=0, [ A==1 && B>=1 ], cost: 1+3*B 5: evalEx4bb2in -> evalEx4bb4in : A'=C, B'=D, [ 0>=D ], cost: 1 14: evalEx4bb2in -> evalEx4bb4in : A'=C, B'=D, [ D>=1 ], cost: 2 Eliminated locations (on tree-shaped paths): Start location: evalEx4start 12: evalEx4start -> evalEx4bb4in : A'=1, B'=A, [], cost: 2 18: evalEx4bb4in -> evalEx4bb4in : A'=0, B'=B, C'=0, D'=B, [ A==1 && 0>=B ], cost: 2 19: evalEx4bb4in -> evalEx4bb4in : A'=0, B'=B, C'=0, D'=B, [ A==1 && B>=1 ], cost: 3 20: evalEx4bb4in -> evalEx4bb4in : A'=1, B'=0, C'=1, D'=0, [ A==1 && B>=1 ], cost: 2+3*B 21: evalEx4bb4in -> [9] : [ A==1 && B>=1 ], cost: 1+3*B Accelerating simple loops of location 2. Simplified some of the simple loops (and removed duplicate rules). Accelerating the following rules: 18: evalEx4bb4in -> evalEx4bb4in : A'=0, C'=0, D'=B, [ A==1 && 0>=B ], cost: 2 19: evalEx4bb4in -> evalEx4bb4in : A'=0, C'=0, D'=B, [ A==1 && B>=1 ], cost: 3 20: evalEx4bb4in -> evalEx4bb4in : A'=1, B'=0, C'=1, D'=0, [ A==1 && B>=1 ], cost: 2+3*B Accelerated rule 18 with metering function A, yielding the new rule 22. Accelerated rule 19 with metering function A, yielding the new rule 23. Found no metering function for rule 20. Removing the simple loops: 18 19. Accelerated all simple loops using metering functions (where possible): Start location: evalEx4start 12: evalEx4start -> evalEx4bb4in : A'=1, B'=A, [], cost: 2 20: evalEx4bb4in -> evalEx4bb4in : A'=1, B'=0, C'=1, D'=0, [ A==1 && B>=1 ], cost: 2+3*B 21: evalEx4bb4in -> [9] : [ A==1 && B>=1 ], cost: 1+3*B 22: evalEx4bb4in -> evalEx4bb4in : A'=0, C'=0, D'=B, [ A==1 && 0>=B ], cost: 2*A 23: evalEx4bb4in -> evalEx4bb4in : A'=0, C'=0, D'=B, [ A==1 && B>=1 ], cost: 3*A Chained accelerated rules (with incoming rules): Start location: evalEx4start 12: evalEx4start -> evalEx4bb4in : A'=1, B'=A, [], cost: 2 24: evalEx4start -> evalEx4bb4in : A'=1, B'=0, C'=1, D'=0, [ A>=1 ], cost: 4+3*A 25: evalEx4start -> evalEx4bb4in : A'=0, B'=A, C'=0, D'=A, [ 0>=A ], cost: 4 26: evalEx4start -> evalEx4bb4in : A'=0, B'=A, C'=0, D'=A, [ A>=1 ], cost: 5 21: evalEx4bb4in -> [9] : [ A==1 && B>=1 ], cost: 1+3*B Eliminated locations (on tree-shaped paths): Start location: evalEx4start 27: evalEx4start -> [9] : A'=1, B'=A, [ A>=1 ], cost: 3+3*A 28: evalEx4start -> [11] : [ A>=1 ], cost: 4+3*A ### Computing asymptotic complexity ### Fully simplified ITS problem Start location: evalEx4start 28: evalEx4start -> [11] : [ A>=1 ], cost: 4+3*A Computing asymptotic complexity for rule 28 Solved the limit problem by the following transformations: Created initial limit problem: 4+3*A (+), 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 4+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: 4+3*n Rule cost: 4+3*A Rule guard: [ A>=1 ] WORST_CASE(Omega(n^1),?) ---------------------------------------- (4) BOUNDS(n^1, INF)