/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: 48fb2092695e11cc9f56e44b17a92a5f88ffb256 marcel 20180622 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, 329 ms] (2) BOUNDS(1, n^1) (3) Loat Proof [FINISHED, 746 ms] (4) BOUNDS(n^1, INF) ---------------------------------------- (0) Obligation: Complexity Int TRS consisting of the following rules: eval_speedpldi2_start(v_m, v_n, v_v1_0, v_v2_0) -> Com_1(eval_speedpldi2_bb0_in(v_m, v_n, v_v1_0, v_v2_0)) :|: TRUE eval_speedpldi2_bb0_in(v_m, v_n, v_v1_0, v_v2_0) -> Com_1(eval_speedpldi2_0(v_m, v_n, v_v1_0, v_v2_0)) :|: TRUE eval_speedpldi2_0(v_m, v_n, v_v1_0, v_v2_0) -> Com_1(eval_speedpldi2_1(v_m, v_n, v_v1_0, v_v2_0)) :|: TRUE eval_speedpldi2_1(v_m, v_n, v_v1_0, v_v2_0) -> Com_1(eval_speedpldi2_2(v_m, v_n, v_v1_0, v_v2_0)) :|: TRUE eval_speedpldi2_2(v_m, v_n, v_v1_0, v_v2_0) -> Com_1(eval_speedpldi2_bb1_in(v_m, v_n, v_n, 0)) :|: v_n >= 0 && v_m > 0 eval_speedpldi2_2(v_m, v_n, v_v1_0, v_v2_0) -> Com_1(eval_speedpldi2_bb4_in(v_m, v_n, v_v1_0, v_v2_0)) :|: v_n < 0 eval_speedpldi2_2(v_m, v_n, v_v1_0, v_v2_0) -> Com_1(eval_speedpldi2_bb4_in(v_m, v_n, v_v1_0, v_v2_0)) :|: v_m <= 0 eval_speedpldi2_bb1_in(v_m, v_n, v_v1_0, v_v2_0) -> Com_1(eval_speedpldi2_bb2_in(v_m, v_n, v_v1_0, v_v2_0)) :|: v_v1_0 > 0 eval_speedpldi2_bb1_in(v_m, v_n, v_v1_0, v_v2_0) -> Com_1(eval_speedpldi2_bb4_in(v_m, v_n, v_v1_0, v_v2_0)) :|: v_v1_0 <= 0 eval_speedpldi2_bb2_in(v_m, v_n, v_v1_0, v_v2_0) -> Com_1(eval_speedpldi2_bb3_in(v_m, v_n, v_v1_0, v_v2_0)) :|: v_v2_0 < v_m eval_speedpldi2_bb2_in(v_m, v_n, v_v1_0, v_v2_0) -> Com_1(eval_speedpldi2_bb1_in(v_m, v_n, v_v1_0, 0)) :|: v_v2_0 >= v_m eval_speedpldi2_bb3_in(v_m, v_n, v_v1_0, v_v2_0) -> Com_1(eval_speedpldi2_bb1_in(v_m, v_n, v_v1_0 - 1, v_v2_0 + 1)) :|: TRUE eval_speedpldi2_bb4_in(v_m, v_n, v_v1_0, v_v2_0) -> Com_1(eval_speedpldi2_stop(v_m, v_n, v_v1_0, v_v2_0)) :|: TRUE The start-symbols are:[eval_speedpldi2_start_4] ---------------------------------------- (1) Koat Proof (FINISHED) YES(?, 28*ar_0 + 15) Initial complexity problem: 1: T: (Comp: ?, Cost: 1) evalspeedpldi2start(ar_0, ar_1, ar_2, ar_3) -> Com_1(evalspeedpldi2bb0in(ar_0, ar_1, ar_2, ar_3)) (Comp: ?, Cost: 1) evalspeedpldi2bb0in(ar_0, ar_1, ar_2, ar_3) -> Com_1(evalspeedpldi20(ar_0, ar_1, ar_2, ar_3)) (Comp: ?, Cost: 1) evalspeedpldi20(ar_0, ar_1, ar_2, ar_3) -> Com_1(evalspeedpldi21(ar_0, ar_1, ar_2, ar_3)) (Comp: ?, Cost: 1) evalspeedpldi21(ar_0, ar_1, ar_2, ar_3) -> Com_1(evalspeedpldi22(ar_0, ar_1, ar_2, ar_3)) (Comp: ?, Cost: 1) evalspeedpldi22(ar_0, ar_1, ar_2, ar_3) -> Com_1(evalspeedpldi2bb1in(ar_0, ar_1, ar_0, 0)) [ ar_0 >= 0 /\ ar_1 >= 1 ] (Comp: ?, Cost: 1) evalspeedpldi22(ar_0, ar_1, ar_2, ar_3) -> Com_1(evalspeedpldi2bb4in(ar_0, ar_1, ar_2, ar_3)) [ 0 >= ar_0 + 1 ] (Comp: ?, Cost: 1) evalspeedpldi22(ar_0, ar_1, ar_2, ar_3) -> Com_1(evalspeedpldi2bb4in(ar_0, ar_1, ar_2, ar_3)) [ 0 >= ar_1 ] (Comp: ?, Cost: 1) evalspeedpldi2bb1in(ar_0, ar_1, ar_2, ar_3) -> Com_1(evalspeedpldi2bb2in(ar_0, ar_1, ar_2, ar_3)) [ ar_2 >= 1 ] (Comp: ?, Cost: 1) evalspeedpldi2bb1in(ar_0, ar_1, ar_2, ar_3) -> Com_1(evalspeedpldi2bb4in(ar_0, ar_1, ar_2, ar_3)) [ 0 >= ar_2 ] (Comp: ?, Cost: 1) evalspeedpldi2bb2in(ar_0, ar_1, ar_2, ar_3) -> Com_1(evalspeedpldi2bb3in(ar_0, ar_1, ar_2, ar_3)) [ ar_1 >= ar_3 + 1 ] (Comp: ?, Cost: 1) evalspeedpldi2bb2in(ar_0, ar_1, ar_2, ar_3) -> Com_1(evalspeedpldi2bb1in(ar_0, ar_1, ar_2, 0)) [ ar_3 >= ar_1 ] (Comp: ?, Cost: 1) evalspeedpldi2bb3in(ar_0, ar_1, ar_2, ar_3) -> Com_1(evalspeedpldi2bb1in(ar_0, ar_1, ar_2 - 1, ar_3 + 1)) (Comp: ?, Cost: 1) evalspeedpldi2bb4in(ar_0, ar_1, ar_2, ar_3) -> Com_1(evalspeedpldi2stop(ar_0, ar_1, ar_2, ar_3)) (Comp: 1, Cost: 0) koat_start(ar_0, ar_1, ar_2, ar_3) -> Com_1(evalspeedpldi2start(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) evalspeedpldi2start(ar_0, ar_1, ar_2, ar_3) -> Com_1(evalspeedpldi2bb0in(ar_0, ar_1, ar_2, ar_3)) (Comp: 1, Cost: 1) evalspeedpldi2bb0in(ar_0, ar_1, ar_2, ar_3) -> Com_1(evalspeedpldi20(ar_0, ar_1, ar_2, ar_3)) (Comp: 1, Cost: 1) evalspeedpldi20(ar_0, ar_1, ar_2, ar_3) -> Com_1(evalspeedpldi21(ar_0, ar_1, ar_2, ar_3)) (Comp: 1, Cost: 1) evalspeedpldi21(ar_0, ar_1, ar_2, ar_3) -> Com_1(evalspeedpldi22(ar_0, ar_1, ar_2, ar_3)) (Comp: 1, Cost: 1) evalspeedpldi22(ar_0, ar_1, ar_2, ar_3) -> Com_1(evalspeedpldi2bb1in(ar_0, ar_1, ar_0, 0)) [ ar_0 >= 0 /\ ar_1 >= 1 ] (Comp: 1, Cost: 1) evalspeedpldi22(ar_0, ar_1, ar_2, ar_3) -> Com_1(evalspeedpldi2bb4in(ar_0, ar_1, ar_2, ar_3)) [ 0 >= ar_0 + 1 ] (Comp: 1, Cost: 1) evalspeedpldi22(ar_0, ar_1, ar_2, ar_3) -> Com_1(evalspeedpldi2bb4in(ar_0, ar_1, ar_2, ar_3)) [ 0 >= ar_1 ] (Comp: ?, Cost: 1) evalspeedpldi2bb1in(ar_0, ar_1, ar_2, ar_3) -> Com_1(evalspeedpldi2bb2in(ar_0, ar_1, ar_2, ar_3)) [ ar_2 >= 1 ] (Comp: ?, Cost: 1) evalspeedpldi2bb1in(ar_0, ar_1, ar_2, ar_3) -> Com_1(evalspeedpldi2bb4in(ar_0, ar_1, ar_2, ar_3)) [ 0 >= ar_2 ] (Comp: ?, Cost: 1) evalspeedpldi2bb2in(ar_0, ar_1, ar_2, ar_3) -> Com_1(evalspeedpldi2bb3in(ar_0, ar_1, ar_2, ar_3)) [ ar_1 >= ar_3 + 1 ] (Comp: ?, Cost: 1) evalspeedpldi2bb2in(ar_0, ar_1, ar_2, ar_3) -> Com_1(evalspeedpldi2bb1in(ar_0, ar_1, ar_2, 0)) [ ar_3 >= ar_1 ] (Comp: ?, Cost: 1) evalspeedpldi2bb3in(ar_0, ar_1, ar_2, ar_3) -> Com_1(evalspeedpldi2bb1in(ar_0, ar_1, ar_2 - 1, ar_3 + 1)) (Comp: ?, Cost: 1) evalspeedpldi2bb4in(ar_0, ar_1, ar_2, ar_3) -> Com_1(evalspeedpldi2stop(ar_0, ar_1, ar_2, ar_3)) (Comp: 1, Cost: 0) koat_start(ar_0, ar_1, ar_2, ar_3) -> Com_1(evalspeedpldi2start(ar_0, ar_1, ar_2, ar_3)) [ 0 <= 0 ] start location: koat_start leaf cost: 0 A polynomial rank function with Pol(evalspeedpldi2start) = 2 Pol(evalspeedpldi2bb0in) = 2 Pol(evalspeedpldi20) = 2 Pol(evalspeedpldi21) = 2 Pol(evalspeedpldi22) = 2 Pol(evalspeedpldi2bb1in) = 2 Pol(evalspeedpldi2bb4in) = 1 Pol(evalspeedpldi2bb2in) = 2 Pol(evalspeedpldi2bb3in) = 2 Pol(evalspeedpldi2stop) = 0 Pol(koat_start) = 2 orients all transitions weakly and the transitions evalspeedpldi2bb4in(ar_0, ar_1, ar_2, ar_3) -> Com_1(evalspeedpldi2stop(ar_0, ar_1, ar_2, ar_3)) evalspeedpldi2bb1in(ar_0, ar_1, ar_2, ar_3) -> Com_1(evalspeedpldi2bb4in(ar_0, ar_1, ar_2, ar_3)) [ 0 >= ar_2 ] strictly and produces the following problem: 3: T: (Comp: 1, Cost: 1) evalspeedpldi2start(ar_0, ar_1, ar_2, ar_3) -> Com_1(evalspeedpldi2bb0in(ar_0, ar_1, ar_2, ar_3)) (Comp: 1, Cost: 1) evalspeedpldi2bb0in(ar_0, ar_1, ar_2, ar_3) -> Com_1(evalspeedpldi20(ar_0, ar_1, ar_2, ar_3)) (Comp: 1, Cost: 1) evalspeedpldi20(ar_0, ar_1, ar_2, ar_3) -> Com_1(evalspeedpldi21(ar_0, ar_1, ar_2, ar_3)) (Comp: 1, Cost: 1) evalspeedpldi21(ar_0, ar_1, ar_2, ar_3) -> Com_1(evalspeedpldi22(ar_0, ar_1, ar_2, ar_3)) (Comp: 1, Cost: 1) evalspeedpldi22(ar_0, ar_1, ar_2, ar_3) -> Com_1(evalspeedpldi2bb1in(ar_0, ar_1, ar_0, 0)) [ ar_0 >= 0 /\ ar_1 >= 1 ] (Comp: 1, Cost: 1) evalspeedpldi22(ar_0, ar_1, ar_2, ar_3) -> Com_1(evalspeedpldi2bb4in(ar_0, ar_1, ar_2, ar_3)) [ 0 >= ar_0 + 1 ] (Comp: 1, Cost: 1) evalspeedpldi22(ar_0, ar_1, ar_2, ar_3) -> Com_1(evalspeedpldi2bb4in(ar_0, ar_1, ar_2, ar_3)) [ 0 >= ar_1 ] (Comp: ?, Cost: 1) evalspeedpldi2bb1in(ar_0, ar_1, ar_2, ar_3) -> Com_1(evalspeedpldi2bb2in(ar_0, ar_1, ar_2, ar_3)) [ ar_2 >= 1 ] (Comp: 2, Cost: 1) evalspeedpldi2bb1in(ar_0, ar_1, ar_2, ar_3) -> Com_1(evalspeedpldi2bb4in(ar_0, ar_1, ar_2, ar_3)) [ 0 >= ar_2 ] (Comp: ?, Cost: 1) evalspeedpldi2bb2in(ar_0, ar_1, ar_2, ar_3) -> Com_1(evalspeedpldi2bb3in(ar_0, ar_1, ar_2, ar_3)) [ ar_1 >= ar_3 + 1 ] (Comp: ?, Cost: 1) evalspeedpldi2bb2in(ar_0, ar_1, ar_2, ar_3) -> Com_1(evalspeedpldi2bb1in(ar_0, ar_1, ar_2, 0)) [ ar_3 >= ar_1 ] (Comp: ?, Cost: 1) evalspeedpldi2bb3in(ar_0, ar_1, ar_2, ar_3) -> Com_1(evalspeedpldi2bb1in(ar_0, ar_1, ar_2 - 1, ar_3 + 1)) (Comp: 2, Cost: 1) evalspeedpldi2bb4in(ar_0, ar_1, ar_2, ar_3) -> Com_1(evalspeedpldi2stop(ar_0, ar_1, ar_2, ar_3)) (Comp: 1, Cost: 0) koat_start(ar_0, ar_1, ar_2, ar_3) -> Com_1(evalspeedpldi2start(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 evalspeedpldi2bb1in: X_4 >= 0 /\ X_3 + X_4 >= 0 /\ X_2 + X_4 - 1 >= 0 /\ X_1 + X_4 >= 0 /\ X_1 - X_3 >= 0 /\ X_3 >= 0 /\ X_2 + X_3 - 1 >= 0 /\ X_1 + X_3 >= 0 /\ X_2 - 1 >= 0 /\ X_1 + X_2 - 1 >= 0 /\ X_1 >= 0 For symbol evalspeedpldi2bb2in: X_4 >= 0 /\ X_3 + X_4 - 1 >= 0 /\ X_2 + X_4 - 1 >= 0 /\ X_1 + X_4 - 1 >= 0 /\ X_1 - X_3 >= 0 /\ X_3 - 1 >= 0 /\ X_2 + X_3 - 2 >= 0 /\ X_1 + X_3 - 2 >= 0 /\ X_2 - 1 >= 0 /\ X_1 + X_2 - 2 >= 0 /\ X_1 - 1 >= 0 For symbol evalspeedpldi2bb3in: X_2 - X_4 - 1 >= 0 /\ X_4 >= 0 /\ X_3 + X_4 - 1 >= 0 /\ X_2 + X_4 - 1 >= 0 /\ X_1 + X_4 - 1 >= 0 /\ X_1 - X_3 >= 0 /\ X_3 - 1 >= 0 /\ X_2 + X_3 - 2 >= 0 /\ X_1 + X_3 - 2 >= 0 /\ X_2 - 1 >= 0 /\ X_1 + X_2 - 2 >= 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(evalspeedpldi2start(ar_0, ar_1, ar_2, ar_3)) [ 0 <= 0 ] (Comp: 2, Cost: 1) evalspeedpldi2bb4in(ar_0, ar_1, ar_2, ar_3) -> Com_1(evalspeedpldi2stop(ar_0, ar_1, ar_2, ar_3)) (Comp: ?, Cost: 1) evalspeedpldi2bb3in(ar_0, ar_1, ar_2, ar_3) -> Com_1(evalspeedpldi2bb1in(ar_0, ar_1, ar_2 - 1, ar_3 + 1)) [ ar_1 - ar_3 - 1 >= 0 /\ ar_3 >= 0 /\ ar_2 + ar_3 - 1 >= 0 /\ ar_1 + ar_3 - 1 >= 0 /\ ar_0 + ar_3 - 1 >= 0 /\ ar_0 - ar_2 >= 0 /\ ar_2 - 1 >= 0 /\ ar_1 + ar_2 - 2 >= 0 /\ ar_0 + ar_2 - 2 >= 0 /\ ar_1 - 1 >= 0 /\ ar_0 + ar_1 - 2 >= 0 /\ ar_0 - 1 >= 0 ] (Comp: ?, Cost: 1) evalspeedpldi2bb2in(ar_0, ar_1, ar_2, ar_3) -> Com_1(evalspeedpldi2bb1in(ar_0, ar_1, ar_2, 0)) [ ar_3 >= 0 /\ ar_2 + ar_3 - 1 >= 0 /\ ar_1 + ar_3 - 1 >= 0 /\ ar_0 + ar_3 - 1 >= 0 /\ ar_0 - ar_2 >= 0 /\ ar_2 - 1 >= 0 /\ ar_1 + ar_2 - 2 >= 0 /\ ar_0 + ar_2 - 2 >= 0 /\ ar_1 - 1 >= 0 /\ ar_0 + ar_1 - 2 >= 0 /\ ar_0 - 1 >= 0 /\ ar_3 >= ar_1 ] (Comp: ?, Cost: 1) evalspeedpldi2bb2in(ar_0, ar_1, ar_2, ar_3) -> Com_1(evalspeedpldi2bb3in(ar_0, ar_1, ar_2, ar_3)) [ ar_3 >= 0 /\ ar_2 + ar_3 - 1 >= 0 /\ ar_1 + ar_3 - 1 >= 0 /\ ar_0 + ar_3 - 1 >= 0 /\ ar_0 - ar_2 >= 0 /\ ar_2 - 1 >= 0 /\ ar_1 + ar_2 - 2 >= 0 /\ ar_0 + ar_2 - 2 >= 0 /\ ar_1 - 1 >= 0 /\ ar_0 + ar_1 - 2 >= 0 /\ ar_0 - 1 >= 0 /\ ar_1 >= ar_3 + 1 ] (Comp: 2, Cost: 1) evalspeedpldi2bb1in(ar_0, ar_1, ar_2, ar_3) -> Com_1(evalspeedpldi2bb4in(ar_0, ar_1, ar_2, ar_3)) [ ar_3 >= 0 /\ ar_2 + ar_3 >= 0 /\ ar_1 + ar_3 - 1 >= 0 /\ ar_0 + ar_3 >= 0 /\ ar_0 - ar_2 >= 0 /\ ar_2 >= 0 /\ ar_1 + ar_2 - 1 >= 0 /\ ar_0 + ar_2 >= 0 /\ ar_1 - 1 >= 0 /\ ar_0 + ar_1 - 1 >= 0 /\ ar_0 >= 0 /\ 0 >= ar_2 ] (Comp: ?, Cost: 1) evalspeedpldi2bb1in(ar_0, ar_1, ar_2, ar_3) -> Com_1(evalspeedpldi2bb2in(ar_0, ar_1, ar_2, ar_3)) [ ar_3 >= 0 /\ ar_2 + ar_3 >= 0 /\ ar_1 + ar_3 - 1 >= 0 /\ ar_0 + ar_3 >= 0 /\ ar_0 - ar_2 >= 0 /\ ar_2 >= 0 /\ ar_1 + ar_2 - 1 >= 0 /\ ar_0 + ar_2 >= 0 /\ ar_1 - 1 >= 0 /\ ar_0 + ar_1 - 1 >= 0 /\ ar_0 >= 0 /\ ar_2 >= 1 ] (Comp: 1, Cost: 1) evalspeedpldi22(ar_0, ar_1, ar_2, ar_3) -> Com_1(evalspeedpldi2bb4in(ar_0, ar_1, ar_2, ar_3)) [ 0 >= ar_1 ] (Comp: 1, Cost: 1) evalspeedpldi22(ar_0, ar_1, ar_2, ar_3) -> Com_1(evalspeedpldi2bb4in(ar_0, ar_1, ar_2, ar_3)) [ 0 >= ar_0 + 1 ] (Comp: 1, Cost: 1) evalspeedpldi22(ar_0, ar_1, ar_2, ar_3) -> Com_1(evalspeedpldi2bb1in(ar_0, ar_1, ar_0, 0)) [ ar_0 >= 0 /\ ar_1 >= 1 ] (Comp: 1, Cost: 1) evalspeedpldi21(ar_0, ar_1, ar_2, ar_3) -> Com_1(evalspeedpldi22(ar_0, ar_1, ar_2, ar_3)) (Comp: 1, Cost: 1) evalspeedpldi20(ar_0, ar_1, ar_2, ar_3) -> Com_1(evalspeedpldi21(ar_0, ar_1, ar_2, ar_3)) (Comp: 1, Cost: 1) evalspeedpldi2bb0in(ar_0, ar_1, ar_2, ar_3) -> Com_1(evalspeedpldi20(ar_0, ar_1, ar_2, ar_3)) (Comp: 1, Cost: 1) evalspeedpldi2start(ar_0, ar_1, ar_2, ar_3) -> Com_1(evalspeedpldi2bb0in(ar_0, ar_1, ar_2, ar_3)) start location: koat_start leaf cost: 0 A polynomial rank function with Pol(evalspeedpldi2bb3in) = 7*V_3 + 4*V_4 - 1 Pol(evalspeedpldi2bb1in) = 7*V_3 + 4*V_4 + 1 Pol(evalspeedpldi2bb2in) = 7*V_3 + 4*V_4 and size complexities S("evalspeedpldi2start(ar_0, ar_1, ar_2, ar_3) -> Com_1(evalspeedpldi2bb0in(ar_0, ar_1, ar_2, ar_3))", 0-0) = ar_0 S("evalspeedpldi2start(ar_0, ar_1, ar_2, ar_3) -> Com_1(evalspeedpldi2bb0in(ar_0, ar_1, ar_2, ar_3))", 0-1) = ar_1 S("evalspeedpldi2start(ar_0, ar_1, ar_2, ar_3) -> Com_1(evalspeedpldi2bb0in(ar_0, ar_1, ar_2, ar_3))", 0-2) = ar_2 S("evalspeedpldi2start(ar_0, ar_1, ar_2, ar_3) -> Com_1(evalspeedpldi2bb0in(ar_0, ar_1, ar_2, ar_3))", 0-3) = ar_3 S("evalspeedpldi2bb0in(ar_0, ar_1, ar_2, ar_3) -> Com_1(evalspeedpldi20(ar_0, ar_1, ar_2, ar_3))", 0-0) = ar_0 S("evalspeedpldi2bb0in(ar_0, ar_1, ar_2, ar_3) -> Com_1(evalspeedpldi20(ar_0, ar_1, ar_2, ar_3))", 0-1) = ar_1 S("evalspeedpldi2bb0in(ar_0, ar_1, ar_2, ar_3) -> Com_1(evalspeedpldi20(ar_0, ar_1, ar_2, ar_3))", 0-2) = ar_2 S("evalspeedpldi2bb0in(ar_0, ar_1, ar_2, ar_3) -> Com_1(evalspeedpldi20(ar_0, ar_1, ar_2, ar_3))", 0-3) = ar_3 S("evalspeedpldi20(ar_0, ar_1, ar_2, ar_3) -> Com_1(evalspeedpldi21(ar_0, ar_1, ar_2, ar_3))", 0-0) = ar_0 S("evalspeedpldi20(ar_0, ar_1, ar_2, ar_3) -> Com_1(evalspeedpldi21(ar_0, ar_1, ar_2, ar_3))", 0-1) = ar_1 S("evalspeedpldi20(ar_0, ar_1, ar_2, ar_3) -> Com_1(evalspeedpldi21(ar_0, ar_1, ar_2, ar_3))", 0-2) = ar_2 S("evalspeedpldi20(ar_0, ar_1, ar_2, ar_3) -> Com_1(evalspeedpldi21(ar_0, ar_1, ar_2, ar_3))", 0-3) = ar_3 S("evalspeedpldi21(ar_0, ar_1, ar_2, ar_3) -> Com_1(evalspeedpldi22(ar_0, ar_1, ar_2, ar_3))", 0-0) = ar_0 S("evalspeedpldi21(ar_0, ar_1, ar_2, ar_3) -> Com_1(evalspeedpldi22(ar_0, ar_1, ar_2, ar_3))", 0-1) = ar_1 S("evalspeedpldi21(ar_0, ar_1, ar_2, ar_3) -> Com_1(evalspeedpldi22(ar_0, ar_1, ar_2, ar_3))", 0-2) = ar_2 S("evalspeedpldi21(ar_0, ar_1, ar_2, ar_3) -> Com_1(evalspeedpldi22(ar_0, ar_1, ar_2, ar_3))", 0-3) = ar_3 S("evalspeedpldi22(ar_0, ar_1, ar_2, ar_3) -> Com_1(evalspeedpldi2bb1in(ar_0, ar_1, ar_0, 0)) [ ar_0 >= 0 /\\ ar_1 >= 1 ]", 0-0) = ar_0 S("evalspeedpldi22(ar_0, ar_1, ar_2, ar_3) -> Com_1(evalspeedpldi2bb1in(ar_0, ar_1, ar_0, 0)) [ ar_0 >= 0 /\\ ar_1 >= 1 ]", 0-1) = ar_1 S("evalspeedpldi22(ar_0, ar_1, ar_2, ar_3) -> Com_1(evalspeedpldi2bb1in(ar_0, ar_1, ar_0, 0)) [ ar_0 >= 0 /\\ ar_1 >= 1 ]", 0-2) = ar_0 S("evalspeedpldi22(ar_0, ar_1, ar_2, ar_3) -> Com_1(evalspeedpldi2bb1in(ar_0, ar_1, ar_0, 0)) [ ar_0 >= 0 /\\ ar_1 >= 1 ]", 0-3) = 0 S("evalspeedpldi22(ar_0, ar_1, ar_2, ar_3) -> Com_1(evalspeedpldi2bb4in(ar_0, ar_1, ar_2, ar_3)) [ 0 >= ar_0 + 1 ]", 0-0) = ar_0 S("evalspeedpldi22(ar_0, ar_1, ar_2, ar_3) -> Com_1(evalspeedpldi2bb4in(ar_0, ar_1, ar_2, ar_3)) [ 0 >= ar_0 + 1 ]", 0-1) = ar_1 S("evalspeedpldi22(ar_0, ar_1, ar_2, ar_3) -> Com_1(evalspeedpldi2bb4in(ar_0, ar_1, ar_2, ar_3)) [ 0 >= ar_0 + 1 ]", 0-2) = ar_2 S("evalspeedpldi22(ar_0, ar_1, ar_2, ar_3) -> Com_1(evalspeedpldi2bb4in(ar_0, ar_1, ar_2, ar_3)) [ 0 >= ar_0 + 1 ]", 0-3) = ar_3 S("evalspeedpldi22(ar_0, ar_1, ar_2, ar_3) -> Com_1(evalspeedpldi2bb4in(ar_0, ar_1, ar_2, ar_3)) [ 0 >= ar_1 ]", 0-0) = ar_0 S("evalspeedpldi22(ar_0, ar_1, ar_2, ar_3) -> Com_1(evalspeedpldi2bb4in(ar_0, ar_1, ar_2, ar_3)) [ 0 >= ar_1 ]", 0-1) = ar_1 S("evalspeedpldi22(ar_0, ar_1, ar_2, ar_3) -> Com_1(evalspeedpldi2bb4in(ar_0, ar_1, ar_2, ar_3)) [ 0 >= ar_1 ]", 0-2) = ar_2 S("evalspeedpldi22(ar_0, ar_1, ar_2, ar_3) -> Com_1(evalspeedpldi2bb4in(ar_0, ar_1, ar_2, ar_3)) [ 0 >= ar_1 ]", 0-3) = ar_3 S("evalspeedpldi2bb1in(ar_0, ar_1, ar_2, ar_3) -> Com_1(evalspeedpldi2bb2in(ar_0, ar_1, ar_2, ar_3)) [ ar_3 >= 0 /\\ ar_2 + ar_3 >= 0 /\\ ar_1 + ar_3 - 1 >= 0 /\\ ar_0 + ar_3 >= 0 /\\ ar_0 - ar_2 >= 0 /\\ ar_2 >= 0 /\\ ar_1 + ar_2 - 1 >= 0 /\\ ar_0 + ar_2 >= 0 /\\ ar_1 - 1 >= 0 /\\ ar_0 + ar_1 - 1 >= 0 /\\ ar_0 >= 0 /\\ ar_2 >= 1 ]", 0-0) = ar_0 S("evalspeedpldi2bb1in(ar_0, ar_1, ar_2, ar_3) -> Com_1(evalspeedpldi2bb2in(ar_0, ar_1, ar_2, ar_3)) [ ar_3 >= 0 /\\ ar_2 + ar_3 >= 0 /\\ ar_1 + ar_3 - 1 >= 0 /\\ ar_0 + ar_3 >= 0 /\\ ar_0 - ar_2 >= 0 /\\ ar_2 >= 0 /\\ ar_1 + ar_2 - 1 >= 0 /\\ ar_0 + ar_2 >= 0 /\\ ar_1 - 1 >= 0 /\\ ar_0 + ar_1 - 1 >= 0 /\\ ar_0 >= 0 /\\ ar_2 >= 1 ]", 0-1) = ar_1 S("evalspeedpldi2bb1in(ar_0, ar_1, ar_2, ar_3) -> Com_1(evalspeedpldi2bb2in(ar_0, ar_1, ar_2, ar_3)) [ ar_3 >= 0 /\\ ar_2 + ar_3 >= 0 /\\ ar_1 + ar_3 - 1 >= 0 /\\ ar_0 + ar_3 >= 0 /\\ ar_0 - ar_2 >= 0 /\\ ar_2 >= 0 /\\ ar_1 + ar_2 - 1 >= 0 /\\ ar_0 + ar_2 >= 0 /\\ ar_1 - 1 >= 0 /\\ ar_0 + ar_1 - 1 >= 0 /\\ ar_0 >= 0 /\\ ar_2 >= 1 ]", 0-2) = ar_0 S("evalspeedpldi2bb1in(ar_0, ar_1, ar_2, ar_3) -> Com_1(evalspeedpldi2bb2in(ar_0, ar_1, ar_2, ar_3)) [ ar_3 >= 0 /\\ ar_2 + ar_3 >= 0 /\\ ar_1 + ar_3 - 1 >= 0 /\\ ar_0 + ar_3 >= 0 /\\ ar_0 - ar_2 >= 0 /\\ ar_2 >= 0 /\\ ar_1 + ar_2 - 1 >= 0 /\\ ar_0 + ar_2 >= 0 /\\ ar_1 - 1 >= 0 /\\ ar_0 + ar_1 - 1 >= 0 /\\ ar_0 >= 0 /\\ ar_2 >= 1 ]", 0-3) = ar_1 S("evalspeedpldi2bb1in(ar_0, ar_1, ar_2, ar_3) -> Com_1(evalspeedpldi2bb4in(ar_0, ar_1, ar_2, ar_3)) [ ar_3 >= 0 /\\ ar_2 + ar_3 >= 0 /\\ ar_1 + ar_3 - 1 >= 0 /\\ ar_0 + ar_3 >= 0 /\\ ar_0 - ar_2 >= 0 /\\ ar_2 >= 0 /\\ ar_1 + ar_2 - 1 >= 0 /\\ ar_0 + ar_2 >= 0 /\\ ar_1 - 1 >= 0 /\\ ar_0 + ar_1 - 1 >= 0 /\\ ar_0 >= 0 /\\ 0 >= ar_2 ]", 0-0) = ar_0 S("evalspeedpldi2bb1in(ar_0, ar_1, ar_2, ar_3) -> Com_1(evalspeedpldi2bb4in(ar_0, ar_1, ar_2, ar_3)) [ ar_3 >= 0 /\\ ar_2 + ar_3 >= 0 /\\ ar_1 + ar_3 - 1 >= 0 /\\ ar_0 + ar_3 >= 0 /\\ ar_0 - ar_2 >= 0 /\\ ar_2 >= 0 /\\ ar_1 + ar_2 - 1 >= 0 /\\ ar_0 + ar_2 >= 0 /\\ ar_1 - 1 >= 0 /\\ ar_0 + ar_1 - 1 >= 0 /\\ ar_0 >= 0 /\\ 0 >= ar_2 ]", 0-1) = ar_1 S("evalspeedpldi2bb1in(ar_0, ar_1, ar_2, ar_3) -> Com_1(evalspeedpldi2bb4in(ar_0, ar_1, ar_2, ar_3)) [ ar_3 >= 0 /\\ ar_2 + ar_3 >= 0 /\\ ar_1 + ar_3 - 1 >= 0 /\\ ar_0 + ar_3 >= 0 /\\ ar_0 - ar_2 >= 0 /\\ ar_2 >= 0 /\\ ar_1 + ar_2 - 1 >= 0 /\\ ar_0 + ar_2 >= 0 /\\ ar_1 - 1 >= 0 /\\ ar_0 + ar_1 - 1 >= 0 /\\ ar_0 >= 0 /\\ 0 >= ar_2 ]", 0-2) = 0 S("evalspeedpldi2bb1in(ar_0, ar_1, ar_2, ar_3) -> Com_1(evalspeedpldi2bb4in(ar_0, ar_1, ar_2, ar_3)) [ ar_3 >= 0 /\\ ar_2 + ar_3 >= 0 /\\ ar_1 + ar_3 - 1 >= 0 /\\ ar_0 + ar_3 >= 0 /\\ ar_0 - ar_2 >= 0 /\\ ar_2 >= 0 /\\ ar_1 + ar_2 - 1 >= 0 /\\ ar_0 + ar_2 >= 0 /\\ ar_1 - 1 >= 0 /\\ ar_0 + ar_1 - 1 >= 0 /\\ ar_0 >= 0 /\\ 0 >= ar_2 ]", 0-3) = ar_1 S("evalspeedpldi2bb2in(ar_0, ar_1, ar_2, ar_3) -> Com_1(evalspeedpldi2bb3in(ar_0, ar_1, ar_2, ar_3)) [ ar_3 >= 0 /\\ ar_2 + ar_3 - 1 >= 0 /\\ ar_1 + ar_3 - 1 >= 0 /\\ ar_0 + ar_3 - 1 >= 0 /\\ ar_0 - ar_2 >= 0 /\\ ar_2 - 1 >= 0 /\\ ar_1 + ar_2 - 2 >= 0 /\\ ar_0 + ar_2 - 2 >= 0 /\\ ar_1 - 1 >= 0 /\\ ar_0 + ar_1 - 2 >= 0 /\\ ar_0 - 1 >= 0 /\\ ar_1 >= ar_3 + 1 ]", 0-0) = ar_0 S("evalspeedpldi2bb2in(ar_0, ar_1, ar_2, ar_3) -> Com_1(evalspeedpldi2bb3in(ar_0, ar_1, ar_2, ar_3)) [ ar_3 >= 0 /\\ ar_2 + ar_3 - 1 >= 0 /\\ ar_1 + ar_3 - 1 >= 0 /\\ ar_0 + ar_3 - 1 >= 0 /\\ ar_0 - ar_2 >= 0 /\\ ar_2 - 1 >= 0 /\\ ar_1 + ar_2 - 2 >= 0 /\\ ar_0 + ar_2 - 2 >= 0 /\\ ar_1 - 1 >= 0 /\\ ar_0 + ar_1 - 2 >= 0 /\\ ar_0 - 1 >= 0 /\\ ar_1 >= ar_3 + 1 ]", 0-1) = ar_1 S("evalspeedpldi2bb2in(ar_0, ar_1, ar_2, ar_3) -> Com_1(evalspeedpldi2bb3in(ar_0, ar_1, ar_2, ar_3)) [ ar_3 >= 0 /\\ ar_2 + ar_3 - 1 >= 0 /\\ ar_1 + ar_3 - 1 >= 0 /\\ ar_0 + ar_3 - 1 >= 0 /\\ ar_0 - ar_2 >= 0 /\\ ar_2 - 1 >= 0 /\\ ar_1 + ar_2 - 2 >= 0 /\\ ar_0 + ar_2 - 2 >= 0 /\\ ar_1 - 1 >= 0 /\\ ar_0 + ar_1 - 2 >= 0 /\\ ar_0 - 1 >= 0 /\\ ar_1 >= ar_3 + 1 ]", 0-2) = ar_0 S("evalspeedpldi2bb2in(ar_0, ar_1, ar_2, ar_3) -> Com_1(evalspeedpldi2bb3in(ar_0, ar_1, ar_2, ar_3)) [ ar_3 >= 0 /\\ ar_2 + ar_3 - 1 >= 0 /\\ ar_1 + ar_3 - 1 >= 0 /\\ ar_0 + ar_3 - 1 >= 0 /\\ ar_0 - ar_2 >= 0 /\\ ar_2 - 1 >= 0 /\\ ar_1 + ar_2 - 2 >= 0 /\\ ar_0 + ar_2 - 2 >= 0 /\\ ar_1 - 1 >= 0 /\\ ar_0 + ar_1 - 2 >= 0 /\\ ar_0 - 1 >= 0 /\\ ar_1 >= ar_3 + 1 ]", 0-3) = ar_1 S("evalspeedpldi2bb2in(ar_0, ar_1, ar_2, ar_3) -> Com_1(evalspeedpldi2bb1in(ar_0, ar_1, ar_2, 0)) [ ar_3 >= 0 /\\ ar_2 + ar_3 - 1 >= 0 /\\ ar_1 + ar_3 - 1 >= 0 /\\ ar_0 + ar_3 - 1 >= 0 /\\ ar_0 - ar_2 >= 0 /\\ ar_2 - 1 >= 0 /\\ ar_1 + ar_2 - 2 >= 0 /\\ ar_0 + ar_2 - 2 >= 0 /\\ ar_1 - 1 >= 0 /\\ ar_0 + ar_1 - 2 >= 0 /\\ ar_0 - 1 >= 0 /\\ ar_3 >= ar_1 ]", 0-0) = ar_0 S("evalspeedpldi2bb2in(ar_0, ar_1, ar_2, ar_3) -> Com_1(evalspeedpldi2bb1in(ar_0, ar_1, ar_2, 0)) [ ar_3 >= 0 /\\ ar_2 + ar_3 - 1 >= 0 /\\ ar_1 + ar_3 - 1 >= 0 /\\ ar_0 + ar_3 - 1 >= 0 /\\ ar_0 - ar_2 >= 0 /\\ ar_2 - 1 >= 0 /\\ ar_1 + ar_2 - 2 >= 0 /\\ ar_0 + ar_2 - 2 >= 0 /\\ ar_1 - 1 >= 0 /\\ ar_0 + ar_1 - 2 >= 0 /\\ ar_0 - 1 >= 0 /\\ ar_3 >= ar_1 ]", 0-1) = ar_1 S("evalspeedpldi2bb2in(ar_0, ar_1, ar_2, ar_3) -> Com_1(evalspeedpldi2bb1in(ar_0, ar_1, ar_2, 0)) [ ar_3 >= 0 /\\ ar_2 + ar_3 - 1 >= 0 /\\ ar_1 + ar_3 - 1 >= 0 /\\ ar_0 + ar_3 - 1 >= 0 /\\ ar_0 - ar_2 >= 0 /\\ ar_2 - 1 >= 0 /\\ ar_1 + ar_2 - 2 >= 0 /\\ ar_0 + ar_2 - 2 >= 0 /\\ ar_1 - 1 >= 0 /\\ ar_0 + ar_1 - 2 >= 0 /\\ ar_0 - 1 >= 0 /\\ ar_3 >= ar_1 ]", 0-2) = ar_0 S("evalspeedpldi2bb2in(ar_0, ar_1, ar_2, ar_3) -> Com_1(evalspeedpldi2bb1in(ar_0, ar_1, ar_2, 0)) [ ar_3 >= 0 /\\ ar_2 + ar_3 - 1 >= 0 /\\ ar_1 + ar_3 - 1 >= 0 /\\ ar_0 + ar_3 - 1 >= 0 /\\ ar_0 - ar_2 >= 0 /\\ ar_2 - 1 >= 0 /\\ ar_1 + ar_2 - 2 >= 0 /\\ ar_0 + ar_2 - 2 >= 0 /\\ ar_1 - 1 >= 0 /\\ ar_0 + ar_1 - 2 >= 0 /\\ ar_0 - 1 >= 0 /\\ ar_3 >= ar_1 ]", 0-3) = 0 S("evalspeedpldi2bb3in(ar_0, ar_1, ar_2, ar_3) -> Com_1(evalspeedpldi2bb1in(ar_0, ar_1, ar_2 - 1, ar_3 + 1)) [ ar_1 - ar_3 - 1 >= 0 /\\ ar_3 >= 0 /\\ ar_2 + ar_3 - 1 >= 0 /\\ ar_1 + ar_3 - 1 >= 0 /\\ ar_0 + ar_3 - 1 >= 0 /\\ ar_0 - ar_2 >= 0 /\\ ar_2 - 1 >= 0 /\\ ar_1 + ar_2 - 2 >= 0 /\\ ar_0 + ar_2 - 2 >= 0 /\\ ar_1 - 1 >= 0 /\\ ar_0 + ar_1 - 2 >= 0 /\\ ar_0 - 1 >= 0 ]", 0-0) = ar_0 S("evalspeedpldi2bb3in(ar_0, ar_1, ar_2, ar_3) -> Com_1(evalspeedpldi2bb1in(ar_0, ar_1, ar_2 - 1, ar_3 + 1)) [ ar_1 - ar_3 - 1 >= 0 /\\ ar_3 >= 0 /\\ ar_2 + ar_3 - 1 >= 0 /\\ ar_1 + ar_3 - 1 >= 0 /\\ ar_0 + ar_3 - 1 >= 0 /\\ ar_0 - ar_2 >= 0 /\\ ar_2 - 1 >= 0 /\\ ar_1 + ar_2 - 2 >= 0 /\\ ar_0 + ar_2 - 2 >= 0 /\\ ar_1 - 1 >= 0 /\\ ar_0 + ar_1 - 2 >= 0 /\\ ar_0 - 1 >= 0 ]", 0-1) = ar_1 S("evalspeedpldi2bb3in(ar_0, ar_1, ar_2, ar_3) -> Com_1(evalspeedpldi2bb1in(ar_0, ar_1, ar_2 - 1, ar_3 + 1)) [ ar_1 - ar_3 - 1 >= 0 /\\ ar_3 >= 0 /\\ ar_2 + ar_3 - 1 >= 0 /\\ ar_1 + ar_3 - 1 >= 0 /\\ ar_0 + ar_3 - 1 >= 0 /\\ ar_0 - ar_2 >= 0 /\\ ar_2 - 1 >= 0 /\\ ar_1 + ar_2 - 2 >= 0 /\\ ar_0 + ar_2 - 2 >= 0 /\\ ar_1 - 1 >= 0 /\\ ar_0 + ar_1 - 2 >= 0 /\\ ar_0 - 1 >= 0 ]", 0-2) = ar_0 S("evalspeedpldi2bb3in(ar_0, ar_1, ar_2, ar_3) -> Com_1(evalspeedpldi2bb1in(ar_0, ar_1, ar_2 - 1, ar_3 + 1)) [ ar_1 - ar_3 - 1 >= 0 /\\ ar_3 >= 0 /\\ ar_2 + ar_3 - 1 >= 0 /\\ ar_1 + ar_3 - 1 >= 0 /\\ ar_0 + ar_3 - 1 >= 0 /\\ ar_0 - ar_2 >= 0 /\\ ar_2 - 1 >= 0 /\\ ar_1 + ar_2 - 2 >= 0 /\\ ar_0 + ar_2 - 2 >= 0 /\\ ar_1 - 1 >= 0 /\\ ar_0 + ar_1 - 2 >= 0 /\\ ar_0 - 1 >= 0 ]", 0-3) = ar_1 S("evalspeedpldi2bb4in(ar_0, ar_1, ar_2, ar_3) -> Com_1(evalspeedpldi2stop(ar_0, ar_1, ar_2, ar_3))", 0-0) = ar_0 S("evalspeedpldi2bb4in(ar_0, ar_1, ar_2, ar_3) -> Com_1(evalspeedpldi2stop(ar_0, ar_1, ar_2, ar_3))", 0-1) = ar_1 S("evalspeedpldi2bb4in(ar_0, ar_1, ar_2, ar_3) -> Com_1(evalspeedpldi2stop(ar_0, ar_1, ar_2, ar_3))", 0-2) = ar_2 S("evalspeedpldi2bb4in(ar_0, ar_1, ar_2, ar_3) -> Com_1(evalspeedpldi2stop(ar_0, ar_1, ar_2, ar_3))", 0-3) = ar_1 + ar_3 S("koat_start(ar_0, ar_1, ar_2, ar_3) -> Com_1(evalspeedpldi2start(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(evalspeedpldi2start(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(evalspeedpldi2start(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(evalspeedpldi2start(ar_0, ar_1, ar_2, ar_3)) [ 0 <= 0 ]", 0-3) = ar_3 orients the transitions evalspeedpldi2bb3in(ar_0, ar_1, ar_2, ar_3) -> Com_1(evalspeedpldi2bb1in(ar_0, ar_1, ar_2 - 1, ar_3 + 1)) [ ar_1 - ar_3 - 1 >= 0 /\ ar_3 >= 0 /\ ar_2 + ar_3 - 1 >= 0 /\ ar_1 + ar_3 - 1 >= 0 /\ ar_0 + ar_3 - 1 >= 0 /\ ar_0 - ar_2 >= 0 /\ ar_2 - 1 >= 0 /\ ar_1 + ar_2 - 2 >= 0 /\ ar_0 + ar_2 - 2 >= 0 /\ ar_1 - 1 >= 0 /\ ar_0 + ar_1 - 2 >= 0 /\ ar_0 - 1 >= 0 ] evalspeedpldi2bb2in(ar_0, ar_1, ar_2, ar_3) -> Com_1(evalspeedpldi2bb3in(ar_0, ar_1, ar_2, ar_3)) [ ar_3 >= 0 /\ ar_2 + ar_3 - 1 >= 0 /\ ar_1 + ar_3 - 1 >= 0 /\ ar_0 + ar_3 - 1 >= 0 /\ ar_0 - ar_2 >= 0 /\ ar_2 - 1 >= 0 /\ ar_1 + ar_2 - 2 >= 0 /\ ar_0 + ar_2 - 2 >= 0 /\ ar_1 - 1 >= 0 /\ ar_0 + ar_1 - 2 >= 0 /\ ar_0 - 1 >= 0 /\ ar_1 >= ar_3 + 1 ] evalspeedpldi2bb2in(ar_0, ar_1, ar_2, ar_3) -> Com_1(evalspeedpldi2bb1in(ar_0, ar_1, ar_2, 0)) [ ar_3 >= 0 /\ ar_2 + ar_3 - 1 >= 0 /\ ar_1 + ar_3 - 1 >= 0 /\ ar_0 + ar_3 - 1 >= 0 /\ ar_0 - ar_2 >= 0 /\ ar_2 - 1 >= 0 /\ ar_1 + ar_2 - 2 >= 0 /\ ar_0 + ar_2 - 2 >= 0 /\ ar_1 - 1 >= 0 /\ ar_0 + ar_1 - 2 >= 0 /\ ar_0 - 1 >= 0 /\ ar_3 >= ar_1 ] evalspeedpldi2bb1in(ar_0, ar_1, ar_2, ar_3) -> Com_1(evalspeedpldi2bb2in(ar_0, ar_1, ar_2, ar_3)) [ ar_3 >= 0 /\ ar_2 + ar_3 >= 0 /\ ar_1 + ar_3 - 1 >= 0 /\ ar_0 + ar_3 >= 0 /\ ar_0 - ar_2 >= 0 /\ ar_2 >= 0 /\ ar_1 + ar_2 - 1 >= 0 /\ ar_0 + ar_2 >= 0 /\ ar_1 - 1 >= 0 /\ ar_0 + ar_1 - 1 >= 0 /\ ar_0 >= 0 /\ ar_2 >= 1 ] weakly and the transitions evalspeedpldi2bb3in(ar_0, ar_1, ar_2, ar_3) -> Com_1(evalspeedpldi2bb1in(ar_0, ar_1, ar_2 - 1, ar_3 + 1)) [ ar_1 - ar_3 - 1 >= 0 /\ ar_3 >= 0 /\ ar_2 + ar_3 - 1 >= 0 /\ ar_1 + ar_3 - 1 >= 0 /\ ar_0 + ar_3 - 1 >= 0 /\ ar_0 - ar_2 >= 0 /\ ar_2 - 1 >= 0 /\ ar_1 + ar_2 - 2 >= 0 /\ ar_0 + ar_2 - 2 >= 0 /\ ar_1 - 1 >= 0 /\ ar_0 + ar_1 - 2 >= 0 /\ ar_0 - 1 >= 0 ] evalspeedpldi2bb2in(ar_0, ar_1, ar_2, ar_3) -> Com_1(evalspeedpldi2bb3in(ar_0, ar_1, ar_2, ar_3)) [ ar_3 >= 0 /\ ar_2 + ar_3 - 1 >= 0 /\ ar_1 + ar_3 - 1 >= 0 /\ ar_0 + ar_3 - 1 >= 0 /\ ar_0 - ar_2 >= 0 /\ ar_2 - 1 >= 0 /\ ar_1 + ar_2 - 2 >= 0 /\ ar_0 + ar_2 - 2 >= 0 /\ ar_1 - 1 >= 0 /\ ar_0 + ar_1 - 2 >= 0 /\ ar_0 - 1 >= 0 /\ ar_1 >= ar_3 + 1 ] evalspeedpldi2bb2in(ar_0, ar_1, ar_2, ar_3) -> Com_1(evalspeedpldi2bb1in(ar_0, ar_1, ar_2, 0)) [ ar_3 >= 0 /\ ar_2 + ar_3 - 1 >= 0 /\ ar_1 + ar_3 - 1 >= 0 /\ ar_0 + ar_3 - 1 >= 0 /\ ar_0 - ar_2 >= 0 /\ ar_2 - 1 >= 0 /\ ar_1 + ar_2 - 2 >= 0 /\ ar_0 + ar_2 - 2 >= 0 /\ ar_1 - 1 >= 0 /\ ar_0 + ar_1 - 2 >= 0 /\ ar_0 - 1 >= 0 /\ ar_3 >= ar_1 ] evalspeedpldi2bb1in(ar_0, ar_1, ar_2, ar_3) -> Com_1(evalspeedpldi2bb2in(ar_0, ar_1, ar_2, ar_3)) [ ar_3 >= 0 /\ ar_2 + ar_3 >= 0 /\ ar_1 + ar_3 - 1 >= 0 /\ ar_0 + ar_3 >= 0 /\ ar_0 - ar_2 >= 0 /\ ar_2 >= 0 /\ ar_1 + ar_2 - 1 >= 0 /\ ar_0 + ar_2 >= 0 /\ ar_1 - 1 >= 0 /\ ar_0 + ar_1 - 1 >= 0 /\ ar_0 >= 0 /\ ar_2 >= 1 ] strictly and produces the following problem: 5: T: (Comp: 1, Cost: 0) koat_start(ar_0, ar_1, ar_2, ar_3) -> Com_1(evalspeedpldi2start(ar_0, ar_1, ar_2, ar_3)) [ 0 <= 0 ] (Comp: 2, Cost: 1) evalspeedpldi2bb4in(ar_0, ar_1, ar_2, ar_3) -> Com_1(evalspeedpldi2stop(ar_0, ar_1, ar_2, ar_3)) (Comp: 7*ar_0 + 1, Cost: 1) evalspeedpldi2bb3in(ar_0, ar_1, ar_2, ar_3) -> Com_1(evalspeedpldi2bb1in(ar_0, ar_1, ar_2 - 1, ar_3 + 1)) [ ar_1 - ar_3 - 1 >= 0 /\ ar_3 >= 0 /\ ar_2 + ar_3 - 1 >= 0 /\ ar_1 + ar_3 - 1 >= 0 /\ ar_0 + ar_3 - 1 >= 0 /\ ar_0 - ar_2 >= 0 /\ ar_2 - 1 >= 0 /\ ar_1 + ar_2 - 2 >= 0 /\ ar_0 + ar_2 - 2 >= 0 /\ ar_1 - 1 >= 0 /\ ar_0 + ar_1 - 2 >= 0 /\ ar_0 - 1 >= 0 ] (Comp: 7*ar_0 + 1, Cost: 1) evalspeedpldi2bb2in(ar_0, ar_1, ar_2, ar_3) -> Com_1(evalspeedpldi2bb1in(ar_0, ar_1, ar_2, 0)) [ ar_3 >= 0 /\ ar_2 + ar_3 - 1 >= 0 /\ ar_1 + ar_3 - 1 >= 0 /\ ar_0 + ar_3 - 1 >= 0 /\ ar_0 - ar_2 >= 0 /\ ar_2 - 1 >= 0 /\ ar_1 + ar_2 - 2 >= 0 /\ ar_0 + ar_2 - 2 >= 0 /\ ar_1 - 1 >= 0 /\ ar_0 + ar_1 - 2 >= 0 /\ ar_0 - 1 >= 0 /\ ar_3 >= ar_1 ] (Comp: 7*ar_0 + 1, Cost: 1) evalspeedpldi2bb2in(ar_0, ar_1, ar_2, ar_3) -> Com_1(evalspeedpldi2bb3in(ar_0, ar_1, ar_2, ar_3)) [ ar_3 >= 0 /\ ar_2 + ar_3 - 1 >= 0 /\ ar_1 + ar_3 - 1 >= 0 /\ ar_0 + ar_3 - 1 >= 0 /\ ar_0 - ar_2 >= 0 /\ ar_2 - 1 >= 0 /\ ar_1 + ar_2 - 2 >= 0 /\ ar_0 + ar_2 - 2 >= 0 /\ ar_1 - 1 >= 0 /\ ar_0 + ar_1 - 2 >= 0 /\ ar_0 - 1 >= 0 /\ ar_1 >= ar_3 + 1 ] (Comp: 2, Cost: 1) evalspeedpldi2bb1in(ar_0, ar_1, ar_2, ar_3) -> Com_1(evalspeedpldi2bb4in(ar_0, ar_1, ar_2, ar_3)) [ ar_3 >= 0 /\ ar_2 + ar_3 >= 0 /\ ar_1 + ar_3 - 1 >= 0 /\ ar_0 + ar_3 >= 0 /\ ar_0 - ar_2 >= 0 /\ ar_2 >= 0 /\ ar_1 + ar_2 - 1 >= 0 /\ ar_0 + ar_2 >= 0 /\ ar_1 - 1 >= 0 /\ ar_0 + ar_1 - 1 >= 0 /\ ar_0 >= 0 /\ 0 >= ar_2 ] (Comp: 7*ar_0 + 1, Cost: 1) evalspeedpldi2bb1in(ar_0, ar_1, ar_2, ar_3) -> Com_1(evalspeedpldi2bb2in(ar_0, ar_1, ar_2, ar_3)) [ ar_3 >= 0 /\ ar_2 + ar_3 >= 0 /\ ar_1 + ar_3 - 1 >= 0 /\ ar_0 + ar_3 >= 0 /\ ar_0 - ar_2 >= 0 /\ ar_2 >= 0 /\ ar_1 + ar_2 - 1 >= 0 /\ ar_0 + ar_2 >= 0 /\ ar_1 - 1 >= 0 /\ ar_0 + ar_1 - 1 >= 0 /\ ar_0 >= 0 /\ ar_2 >= 1 ] (Comp: 1, Cost: 1) evalspeedpldi22(ar_0, ar_1, ar_2, ar_3) -> Com_1(evalspeedpldi2bb4in(ar_0, ar_1, ar_2, ar_3)) [ 0 >= ar_1 ] (Comp: 1, Cost: 1) evalspeedpldi22(ar_0, ar_1, ar_2, ar_3) -> Com_1(evalspeedpldi2bb4in(ar_0, ar_1, ar_2, ar_3)) [ 0 >= ar_0 + 1 ] (Comp: 1, Cost: 1) evalspeedpldi22(ar_0, ar_1, ar_2, ar_3) -> Com_1(evalspeedpldi2bb1in(ar_0, ar_1, ar_0, 0)) [ ar_0 >= 0 /\ ar_1 >= 1 ] (Comp: 1, Cost: 1) evalspeedpldi21(ar_0, ar_1, ar_2, ar_3) -> Com_1(evalspeedpldi22(ar_0, ar_1, ar_2, ar_3)) (Comp: 1, Cost: 1) evalspeedpldi20(ar_0, ar_1, ar_2, ar_3) -> Com_1(evalspeedpldi21(ar_0, ar_1, ar_2, ar_3)) (Comp: 1, Cost: 1) evalspeedpldi2bb0in(ar_0, ar_1, ar_2, ar_3) -> Com_1(evalspeedpldi20(ar_0, ar_1, ar_2, ar_3)) (Comp: 1, Cost: 1) evalspeedpldi2start(ar_0, ar_1, ar_2, ar_3) -> Com_1(evalspeedpldi2bb0in(ar_0, ar_1, ar_2, ar_3)) start location: koat_start leaf cost: 0 Complexity upper bound 28*ar_0 + 15 Time: 0.318 sec (SMT: 0.250 sec) ---------------------------------------- (2) BOUNDS(1, n^1) ---------------------------------------- (3) Loat Proof (FINISHED) ### Pre-processing the ITS problem ### Initial linear ITS problem Start location: evalspeedpldi2start 0: evalspeedpldi2start -> evalspeedpldi2bb0in : [], cost: 1 1: evalspeedpldi2bb0in -> evalspeedpldi20 : [], cost: 1 2: evalspeedpldi20 -> evalspeedpldi21 : [], cost: 1 3: evalspeedpldi21 -> evalspeedpldi22 : [], cost: 1 4: evalspeedpldi22 -> evalspeedpldi2bb1in : C'=A, D'=0, [ A>=0 && B>=1 ], cost: 1 5: evalspeedpldi22 -> evalspeedpldi2bb4in : [ 0>=1+A ], cost: 1 6: evalspeedpldi22 -> evalspeedpldi2bb4in : [ 0>=B ], cost: 1 7: evalspeedpldi2bb1in -> evalspeedpldi2bb2in : [ C>=1 ], cost: 1 8: evalspeedpldi2bb1in -> evalspeedpldi2bb4in : [ 0>=C ], cost: 1 9: evalspeedpldi2bb2in -> evalspeedpldi2bb3in : [ B>=1+D ], cost: 1 10: evalspeedpldi2bb2in -> evalspeedpldi2bb1in : D'=0, [ D>=B ], cost: 1 11: evalspeedpldi2bb3in -> evalspeedpldi2bb1in : C'=-1+C, D'=1+D, [], cost: 1 12: evalspeedpldi2bb4in -> evalspeedpldi2stop : [], cost: 1 Removed unreachable and leaf rules: Start location: evalspeedpldi2start 0: evalspeedpldi2start -> evalspeedpldi2bb0in : [], cost: 1 1: evalspeedpldi2bb0in -> evalspeedpldi20 : [], cost: 1 2: evalspeedpldi20 -> evalspeedpldi21 : [], cost: 1 3: evalspeedpldi21 -> evalspeedpldi22 : [], cost: 1 4: evalspeedpldi22 -> evalspeedpldi2bb1in : C'=A, D'=0, [ A>=0 && B>=1 ], cost: 1 7: evalspeedpldi2bb1in -> evalspeedpldi2bb2in : [ C>=1 ], cost: 1 9: evalspeedpldi2bb2in -> evalspeedpldi2bb3in : [ B>=1+D ], cost: 1 10: evalspeedpldi2bb2in -> evalspeedpldi2bb1in : D'=0, [ D>=B ], cost: 1 11: evalspeedpldi2bb3in -> evalspeedpldi2bb1in : C'=-1+C, D'=1+D, [], cost: 1 ### Simplification by acceleration and chaining ### Eliminated locations (on linear paths): Start location: evalspeedpldi2start 16: evalspeedpldi2start -> evalspeedpldi2bb1in : C'=A, D'=0, [ A>=0 && B>=1 ], cost: 5 7: evalspeedpldi2bb1in -> evalspeedpldi2bb2in : [ C>=1 ], cost: 1 10: evalspeedpldi2bb2in -> evalspeedpldi2bb1in : D'=0, [ D>=B ], cost: 1 17: evalspeedpldi2bb2in -> evalspeedpldi2bb1in : C'=-1+C, D'=1+D, [ B>=1+D ], cost: 2 Eliminated locations (on tree-shaped paths): Start location: evalspeedpldi2start 16: evalspeedpldi2start -> evalspeedpldi2bb1in : C'=A, D'=0, [ A>=0 && B>=1 ], cost: 5 18: evalspeedpldi2bb1in -> evalspeedpldi2bb1in : D'=0, [ C>=1 && D>=B ], cost: 2 19: evalspeedpldi2bb1in -> evalspeedpldi2bb1in : C'=-1+C, D'=1+D, [ C>=1 && B>=1+D ], cost: 3 Accelerating simple loops of location 5. Accelerating the following rules: 18: evalspeedpldi2bb1in -> evalspeedpldi2bb1in : D'=0, [ C>=1 && D>=B ], cost: 2 19: evalspeedpldi2bb1in -> evalspeedpldi2bb1in : C'=-1+C, D'=1+D, [ C>=1 && B>=1+D ], cost: 3 Accelerated rule 18 with NONTERM (after strengthening guard), yielding the new rule 20. Accelerated rule 19 with backward acceleration, yielding the new rule 21. Accelerated rule 19 with backward acceleration, yielding the new rule 22. Removing the simple loops: 19. Accelerated all simple loops using metering functions (where possible): Start location: evalspeedpldi2start 16: evalspeedpldi2start -> evalspeedpldi2bb1in : C'=A, D'=0, [ A>=0 && B>=1 ], cost: 5 18: evalspeedpldi2bb1in -> evalspeedpldi2bb1in : D'=0, [ C>=1 && D>=B ], cost: 2 20: evalspeedpldi2bb1in -> [10] : [ C>=1 && D>=B && 0>=B ], cost: INF 21: evalspeedpldi2bb1in -> evalspeedpldi2bb1in : C'=0, D'=C+D, [ C>=1 && B>=1+D && B>=C+D ], cost: 3*C 22: evalspeedpldi2bb1in -> evalspeedpldi2bb1in : C'=C+D-B, D'=B, [ C>=1 && B>=1+D && 1+C+D-B>=1 ], cost: -3*D+3*B Chained accelerated rules (with incoming rules): Start location: evalspeedpldi2start 16: evalspeedpldi2start -> evalspeedpldi2bb1in : C'=A, D'=0, [ A>=0 && B>=1 ], cost: 5 23: evalspeedpldi2start -> evalspeedpldi2bb1in : C'=0, D'=A, [ B>=1 && A>=1 && B>=A ], cost: 5+3*A 24: evalspeedpldi2start -> evalspeedpldi2bb1in : C'=A-B, D'=B, [ B>=1 && A>=1 && 1+A-B>=1 ], cost: 5+3*B Removed unreachable locations (and leaf rules with constant cost): Start location: evalspeedpldi2start 23: evalspeedpldi2start -> evalspeedpldi2bb1in : C'=0, D'=A, [ B>=1 && A>=1 && B>=A ], cost: 5+3*A 24: evalspeedpldi2start -> evalspeedpldi2bb1in : C'=A-B, D'=B, [ B>=1 && A>=1 && 1+A-B>=1 ], cost: 5+3*B ### Computing asymptotic complexity ### Fully simplified ITS problem Start location: evalspeedpldi2start 23: evalspeedpldi2start -> evalspeedpldi2bb1in : C'=0, D'=A, [ B>=1 && A>=1 && B>=A ], cost: 5+3*A 24: evalspeedpldi2start -> evalspeedpldi2bb1in : C'=A-B, D'=B, [ B>=1 && A>=1 && 1+A-B>=1 ], cost: 5+3*B Computing asymptotic complexity for rule 23 Simplified the guard: 23: evalspeedpldi2start -> evalspeedpldi2bb1in : C'=0, D'=A, [ A>=1 && B>=A ], cost: 5+3*A Solved the limit problem by the following transformations: Created initial limit problem: 5+3*A (+), A (+/+!), 1-A+B (+/+!) [not solved] removing all constraints (solved by SMT) resulting limit problem: [solved] applying transformation rule (C) using substitution {A==n,B==2*n} resulting limit problem: [solved] Solution: A / n B / 2*n Resulting cost 5+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: 5+3*n Rule cost: 5+3*A Rule guard: [ A>=1 && B>=A ] WORST_CASE(Omega(n^1),?) ---------------------------------------- (4) BOUNDS(n^1, INF)