/export/starexec/sandbox2/solver/bin/starexec_run_complexity /export/starexec/sandbox2/benchmark/theBenchmark.koat /export/starexec/sandbox2/output/output_files -------------------------------------------------------------------------------- WORST_CASE(?, O(n^2)) 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(1, max(5, 5 + Arg_0) + nat(3 * Arg_0^2) + max(2 * Arg_0 * max(6, max(6, 6 + 6 * Arg_0^2)), 2 * Arg_0 * max(6, 6 + 6 * Arg_0^2), 0) + max(Arg_0 * max(5, 5 + 4 * Arg_0^2), Arg_0 * max(max(5, 5 + 4 * Arg_0^2), 5), 0)). (0) CpxIntTrs (1) Koat Proof [FINISHED, 319 ms] (2) BOUNDS(1, n^2) (3) Koat2 Proof [FINISHED, 2929 ms] (4) BOUNDS(1, max(5, 5 + Arg_0) + nat(3 * Arg_0^2) + max(2 * Arg_0 * max(6, max(6, 6 + 6 * Arg_0^2)), 2 * Arg_0 * max(6, 6 + 6 * Arg_0^2), 0) + max(Arg_0 * max(5, 5 + 4 * Arg_0^2), Arg_0 * max(max(5, 5 + 4 * Arg_0^2), 5), 0)) (5) Loat Proof [FINISHED, 14.9 s] (6) BOUNDS(1, INF) ---------------------------------------- (0) Obligation: Complexity Int TRS consisting of the following rules: evalrealheapsortstep1start(A, B, C) -> Com_1(evalrealheapsortstep1entryin(A, B, C)) :|: TRUE evalrealheapsortstep1entryin(A, B, C) -> Com_1(evalrealheapsortstep1bb6in(A, 1, C)) :|: A >= 3 evalrealheapsortstep1entryin(A, B, C) -> Com_1(evalrealheapsortstep1returnin(A, B, C)) :|: 2 >= A evalrealheapsortstep1bb6in(A, B, C) -> Com_1(evalrealheapsortstep1bb3in(A, B, B)) :|: A >= 1 + B evalrealheapsortstep1bb6in(A, B, C) -> Com_1(evalrealheapsortstep1returnin(A, B, C)) :|: B >= A evalrealheapsortstep1bb3in(A, B, C) -> Com_1(evalrealheapsortstep1bb5in(A, B, C)) :|: 0 >= C evalrealheapsortstep1bb3in(A, B, C) -> Com_1(evalrealheapsortstep1bb4in(A, B, C)) :|: C >= 1 evalrealheapsortstep1bb4in(A, B, C) -> Com_1(evalrealheapsortstep1bb2in(A, B, C)) :|: C + 1 >= 0 && C + 1 <= 0 evalrealheapsortstep1bb4in(A, B, C) -> Com_1(evalrealheapsortstep1bb2in(A, B, C)) :|: C >= 0 && D >= 0 && C + 1 >= 2 * D && 2 * D >= C evalrealheapsortstep1bb4in(A, B, C) -> Com_1(evalrealheapsortstep1bb2in(A, B, C)) :|: 0 >= C + 2 && 0 >= D && 2 * D >= C + 1 && 2 + C >= 2 * D evalrealheapsortstep1bb4in(A, B, C) -> Com_1(evalrealheapsortstep1bb5in(A, B, C)) :|: C + 1 >= 0 && C + 1 <= 0 evalrealheapsortstep1bb4in(A, B, C) -> Com_1(evalrealheapsortstep1bb5in(A, B, C)) :|: C >= 0 && D >= 0 && C + 1 >= 2 * D && 2 * D >= C evalrealheapsortstep1bb4in(A, B, C) -> Com_1(evalrealheapsortstep1bb5in(A, B, C)) :|: 0 >= C + 2 && 0 >= D && 2 * D >= C + 1 && 2 + C >= 2 * D evalrealheapsortstep1bb2in(A, B, C) -> Com_1(evalrealheapsortstep1bb3in(A, B, -(1))) :|: C + 1 >= 0 && C + 1 <= 0 evalrealheapsortstep1bb2in(A, B, C) -> Com_1(evalrealheapsortstep1bb3in(A, B, D - 1)) :|: 0 >= 1 && D >= 0 && 0 >= 2 * D && 1 + 2 * D >= 0 && C + 1 >= 0 && C + 1 <= 0 evalrealheapsortstep1bb2in(A, B, C) -> Com_1(evalrealheapsortstep1bb3in(A, B, D - 1)) :|: 0 >= 1 && 0 >= D && C + 1 >= 0 && C + 1 <= 0 && 2 * D >= C + 1 && 2 + C >= 2 * D evalrealheapsortstep1bb2in(A, B, C) -> Com_1(evalrealheapsortstep1bb3in(A, B, -(1))) :|: 0 >= 1 && D >= 0 && 0 >= 2 * D && 1 + 2 * D >= 0 && C + 1 >= 0 && C + 1 <= 0 evalrealheapsortstep1bb2in(A, B, C) -> Com_1(evalrealheapsortstep1bb3in(A, B, D - 1)) :|: 0 >= 1 && E >= 0 && 0 >= 2 * E && 1 + 2 * E >= 0 && D >= 0 && 0 >= 2 * D && 1 + 2 * D >= 0 && C + 1 >= 0 && C + 1 <= 0 evalrealheapsortstep1bb2in(A, B, C) -> Com_1(evalrealheapsortstep1bb3in(A, B, D - 1)) :|: 0 >= 1 && E >= 0 && 0 >= 2 * E && 1 + 2 * E >= 0 && 0 >= D && C + 1 >= 0 && C + 1 <= 0 && 2 * D >= C + 1 && 2 + C >= 2 * D evalrealheapsortstep1bb2in(A, B, C) -> Com_1(evalrealheapsortstep1bb3in(A, B, -(1))) :|: 0 >= 1 && 0 >= D && C + 1 >= 0 && C + 1 <= 0 && 2 * D >= C + 1 && 2 + C >= 2 * D evalrealheapsortstep1bb2in(A, B, C) -> Com_1(evalrealheapsortstep1bb3in(A, B, D - 1)) :|: 0 >= 1 && 0 >= E && D >= 0 && 0 >= 2 * D && 1 + 2 * D >= 0 && C + 1 >= 0 && C + 1 <= 0 && 2 * E >= C + 1 && 2 + C >= 2 * E evalrealheapsortstep1bb2in(A, B, C) -> Com_1(evalrealheapsortstep1bb3in(A, B, D - 1)) :|: 0 >= 1 && 0 >= E && 0 >= D && C + 1 >= 0 && C + 1 <= 0 && 2 * E >= C + 1 && 2 + C >= 2 * E && 2 * D >= C + 1 && 2 + C >= 2 * D evalrealheapsortstep1bb2in(A, B, C) -> Com_1(evalrealheapsortstep1bb3in(A, B, -(1))) :|: 0 >= 1 && D >= 0 && 0 >= 2 * D && 1 + 2 * D >= 0 && E >= 0 && 0 >= 2 * E && 1 + 2 * E >= 0 && C + 1 >= 0 && C + 1 <= 0 evalrealheapsortstep1bb2in(A, B, C) -> Com_1(evalrealheapsortstep1bb3in(A, B, D - 1)) :|: C >= 0 && E >= 0 && C + 1 >= 2 * E && 2 * E >= C && F >= 0 && C + 1 >= 2 * F && 2 * F >= C && D >= 0 && C + 1 >= 2 * D && 2 * D >= C evalrealheapsortstep1bb2in(A, B, C) -> Com_1(evalrealheapsortstep1bb3in(A, B, D - 1)) :|: C >= 0 && E >= 0 && C + 1 >= 2 * E && 2 * E >= C && F >= 0 && C + 1 >= 2 * F && 2 * F >= C && 0 >= C + 2 && 0 >= D && 2 * D >= C + 1 && 2 + C >= 2 * D evalrealheapsortstep1bb2in(A, B, C) -> Com_1(evalrealheapsortstep1bb3in(A, B, -(1))) :|: 0 >= 1 && D >= 0 && 0 >= 2 * D && 1 + 2 * D >= 0 && 0 >= E && C + 1 >= 0 && C + 1 <= 0 && 2 * E >= C + 1 && 2 + C >= 2 * E evalrealheapsortstep1bb2in(A, B, C) -> Com_1(evalrealheapsortstep1bb3in(A, B, D - 1)) :|: C >= 0 && E >= 0 && C + 1 >= 2 * E && 2 * E >= C && 0 >= C + 2 && 0 >= F && D >= 0 && C + 1 >= 2 * D && 2 * D >= C && 2 * F >= C + 1 && 2 + C >= 2 * F evalrealheapsortstep1bb2in(A, B, C) -> Com_1(evalrealheapsortstep1bb3in(A, B, D - 1)) :|: C >= 0 && E >= 0 && C + 1 >= 2 * E && 2 * E >= C && 0 >= C + 2 && 0 >= F && 0 >= D && 2 * F >= C + 1 && 2 + C >= 2 * F && 2 * D >= C + 1 && 2 + C >= 2 * D evalrealheapsortstep1bb2in(A, B, C) -> Com_1(evalrealheapsortstep1bb3in(A, B, -(1))) :|: 0 >= 1 && 0 >= D && E >= 0 && 0 >= 2 * E && 1 + 2 * E >= 0 && C + 1 >= 0 && C + 1 <= 0 && 2 * D >= C + 1 && 2 + C >= 2 * D evalrealheapsortstep1bb2in(A, B, C) -> Com_1(evalrealheapsortstep1bb3in(A, B, D - 1)) :|: 0 >= C + 2 && 0 >= E && C >= 0 && F >= 0 && C + 1 >= 2 * F && 2 * F >= C && D >= 0 && C + 1 >= 2 * D && 2 * D >= C && 2 * E >= C + 1 && 2 + C >= 2 * E evalrealheapsortstep1bb2in(A, B, C) -> Com_1(evalrealheapsortstep1bb3in(A, B, D - 1)) :|: 0 >= C + 2 && 0 >= E && C >= 0 && F >= 0 && C + 1 >= 2 * F && 2 * F >= C && 0 >= D && 2 * E >= C + 1 && 2 + C >= 2 * E && 2 * D >= C + 1 && 2 + C >= 2 * D evalrealheapsortstep1bb2in(A, B, C) -> Com_1(evalrealheapsortstep1bb3in(A, B, -(1))) :|: 0 >= 1 && 0 >= D && 0 >= E && C + 1 >= 0 && C + 1 <= 0 && 2 * D >= C + 1 && 2 + C >= 2 * D && 2 * E >= C + 1 && 2 + C >= 2 * E evalrealheapsortstep1bb2in(A, B, C) -> Com_1(evalrealheapsortstep1bb3in(A, B, D - 1)) :|: 0 >= C + 2 && 0 >= E && 0 >= F && C >= 0 && D >= 0 && C + 1 >= 2 * D && 2 * D >= C && 2 * E >= C + 1 && 2 + C >= 2 * E && 2 * F >= C + 1 && 2 + C >= 2 * F evalrealheapsortstep1bb2in(A, B, C) -> Com_1(evalrealheapsortstep1bb3in(A, B, D - 1)) :|: 0 >= C + 2 && 0 >= E && 0 >= F && 0 >= D && 2 * E >= C + 1 && 2 + C >= 2 * E && 2 * F >= C + 1 && 2 + C >= 2 * F && 2 * D >= C + 1 && 2 + C >= 2 * D evalrealheapsortstep1bb5in(A, B, C) -> Com_1(evalrealheapsortstep1bb6in(A, B + 1, C)) :|: TRUE evalrealheapsortstep1returnin(A, B, C) -> Com_1(evalrealheapsortstep1stop(A, B, C)) :|: TRUE The start-symbols are:[evalrealheapsortstep1start_3] ---------------------------------------- (1) Koat Proof (FINISHED) YES(?, 36*ar_0^2 + 841*ar_0 + 1545) Initial complexity problem: 1: T: (Comp: ?, Cost: 1) evalrealheapsortstep1start(ar_0, ar_1, ar_2) -> Com_1(evalrealheapsortstep1entryin(ar_0, ar_1, ar_2)) (Comp: ?, Cost: 1) evalrealheapsortstep1entryin(ar_0, ar_1, ar_2) -> Com_1(evalrealheapsortstep1bb6in(ar_0, 1, ar_2)) [ ar_0 >= 3 ] (Comp: ?, Cost: 1) evalrealheapsortstep1entryin(ar_0, ar_1, ar_2) -> Com_1(evalrealheapsortstep1returnin(ar_0, ar_1, ar_2)) [ 2 >= ar_0 ] (Comp: ?, Cost: 1) evalrealheapsortstep1bb6in(ar_0, ar_1, ar_2) -> Com_1(evalrealheapsortstep1bb3in(ar_0, ar_1, ar_1)) [ ar_0 >= ar_1 + 1 ] (Comp: ?, Cost: 1) evalrealheapsortstep1bb6in(ar_0, ar_1, ar_2) -> Com_1(evalrealheapsortstep1returnin(ar_0, ar_1, ar_2)) [ ar_1 >= ar_0 ] (Comp: ?, Cost: 1) evalrealheapsortstep1bb3in(ar_0, ar_1, ar_2) -> Com_1(evalrealheapsortstep1bb5in(ar_0, ar_1, ar_2)) [ 0 >= ar_2 ] (Comp: ?, Cost: 1) evalrealheapsortstep1bb3in(ar_0, ar_1, ar_2) -> Com_1(evalrealheapsortstep1bb4in(ar_0, ar_1, ar_2)) [ ar_2 >= 1 ] (Comp: ?, Cost: 1) evalrealheapsortstep1bb4in(ar_0, ar_1, ar_2) -> Com_1(evalrealheapsortstep1bb2in(ar_0, ar_1, ar_2)) [ ar_2 + 1 = 0 ] (Comp: ?, Cost: 1) evalrealheapsortstep1bb4in(ar_0, ar_1, ar_2) -> Com_1(evalrealheapsortstep1bb2in(ar_0, ar_1, ar_2)) [ ar_2 >= 0 /\ d >= 0 /\ ar_2 + 1 >= 2*d /\ 2*d >= ar_2 ] (Comp: ?, Cost: 1) evalrealheapsortstep1bb4in(ar_0, ar_1, ar_2) -> Com_1(evalrealheapsortstep1bb2in(ar_0, ar_1, ar_2)) [ 0 >= ar_2 + 2 /\ 0 >= d /\ 2*d >= ar_2 + 1 /\ ar_2 + 2 >= 2*d ] (Comp: ?, Cost: 1) evalrealheapsortstep1bb4in(ar_0, ar_1, ar_2) -> Com_1(evalrealheapsortstep1bb5in(ar_0, ar_1, ar_2)) [ ar_2 + 1 = 0 ] (Comp: ?, Cost: 1) evalrealheapsortstep1bb4in(ar_0, ar_1, ar_2) -> Com_1(evalrealheapsortstep1bb5in(ar_0, ar_1, ar_2)) [ ar_2 >= 0 /\ d >= 0 /\ ar_2 + 1 >= 2*d /\ 2*d >= ar_2 ] (Comp: ?, Cost: 1) evalrealheapsortstep1bb4in(ar_0, ar_1, ar_2) -> Com_1(evalrealheapsortstep1bb5in(ar_0, ar_1, ar_2)) [ 0 >= ar_2 + 2 /\ 0 >= d /\ 2*d >= ar_2 + 1 /\ ar_2 + 2 >= 2*d ] (Comp: ?, Cost: 1) evalrealheapsortstep1bb2in(ar_0, ar_1, ar_2) -> Com_1(evalrealheapsortstep1bb3in(ar_0, ar_1, -1)) [ ar_2 + 1 = 0 ] (Comp: ?, Cost: 1) evalrealheapsortstep1bb2in(ar_0, ar_1, ar_2) -> Com_1(evalrealheapsortstep1bb3in(ar_0, ar_1, d - 1)) [ 0 >= 1 /\ d >= 0 /\ 0 >= 2*d /\ 2*d + 1 >= 0 /\ ar_2 + 1 = 0 ] (Comp: ?, Cost: 1) evalrealheapsortstep1bb2in(ar_0, ar_1, ar_2) -> Com_1(evalrealheapsortstep1bb3in(ar_0, ar_1, d - 1)) [ 0 >= 1 /\ 0 >= d /\ 2*d >= 0 /\ 1 >= 2*d /\ ar_2 + 1 = 0 ] (Comp: ?, Cost: 1) evalrealheapsortstep1bb2in(ar_0, ar_1, ar_2) -> Com_1(evalrealheapsortstep1bb3in(ar_0, ar_1, -1)) [ 0 >= 1 /\ d >= 0 /\ 0 >= 2*d /\ 2*d + 1 >= 0 /\ ar_2 + 1 = 0 ] (Comp: ?, Cost: 1) evalrealheapsortstep1bb2in(ar_0, ar_1, ar_2) -> Com_1(evalrealheapsortstep1bb3in(ar_0, ar_1, d - 1)) [ 0 >= 1 /\ e >= 0 /\ 0 >= 2*e /\ 2*e + 1 >= 0 /\ d >= 0 /\ 0 >= 2*d /\ 2*d + 1 >= 0 /\ ar_2 + 1 = 0 ] (Comp: ?, Cost: 1) evalrealheapsortstep1bb2in(ar_0, ar_1, ar_2) -> Com_1(evalrealheapsortstep1bb3in(ar_0, ar_1, d - 1)) [ 0 >= 1 /\ e >= 0 /\ 0 >= 2*e /\ 2*e + 1 >= 0 /\ 0 >= d /\ 2*d >= 0 /\ 1 >= 2*d /\ ar_2 + 1 = 0 ] (Comp: ?, Cost: 1) evalrealheapsortstep1bb2in(ar_0, ar_1, ar_2) -> Com_1(evalrealheapsortstep1bb3in(ar_0, ar_1, -1)) [ 0 >= 1 /\ 0 >= d /\ 2*d >= 0 /\ 1 >= 2*d /\ ar_2 + 1 = 0 ] (Comp: ?, Cost: 1) evalrealheapsortstep1bb2in(ar_0, ar_1, ar_2) -> Com_1(evalrealheapsortstep1bb3in(ar_0, ar_1, d - 1)) [ 0 >= 1 /\ 0 >= e /\ d >= 0 /\ 0 >= 2*d /\ 2*d + 1 >= 0 /\ 2*e >= 0 /\ 1 >= 2*e /\ ar_2 + 1 = 0 ] (Comp: ?, Cost: 1) evalrealheapsortstep1bb2in(ar_0, ar_1, ar_2) -> Com_1(evalrealheapsortstep1bb3in(ar_0, ar_1, d - 1)) [ 0 >= 1 /\ 0 >= e /\ 0 >= d /\ 2*e >= 0 /\ 1 >= 2*e /\ 2*d >= 0 /\ 1 >= 2*d /\ ar_2 + 1 = 0 ] (Comp: ?, Cost: 1) evalrealheapsortstep1bb2in(ar_0, ar_1, ar_2) -> Com_1(evalrealheapsortstep1bb3in(ar_0, ar_1, -1)) [ 0 >= 1 /\ d >= 0 /\ 0 >= 2*d /\ 2*d + 1 >= 0 /\ e >= 0 /\ 0 >= 2*e /\ 2*e + 1 >= 0 /\ ar_2 + 1 = 0 ] (Comp: ?, Cost: 1) evalrealheapsortstep1bb2in(ar_0, ar_1, ar_2) -> Com_1(evalrealheapsortstep1bb3in(ar_0, ar_1, d - 1)) [ ar_2 >= 0 /\ e >= 0 /\ ar_2 + 1 >= 2*e /\ 2*e >= ar_2 /\ f >= 0 /\ ar_2 + 1 >= 2*f /\ 2*f >= ar_2 /\ d >= 0 /\ ar_2 + 1 >= 2*d /\ 2*d >= ar_2 ] (Comp: ?, Cost: 1) evalrealheapsortstep1bb2in(ar_0, ar_1, ar_2) -> Com_1(evalrealheapsortstep1bb3in(ar_0, ar_1, d - 1)) [ ar_2 >= 0 /\ e >= 0 /\ ar_2 + 1 >= 2*e /\ 2*e >= ar_2 /\ f >= 0 /\ ar_2 + 1 >= 2*f /\ 2*f >= ar_2 /\ 0 >= ar_2 + 2 /\ 0 >= d /\ 2*d >= ar_2 + 1 /\ ar_2 + 2 >= 2*d ] (Comp: ?, Cost: 1) evalrealheapsortstep1bb2in(ar_0, ar_1, ar_2) -> Com_1(evalrealheapsortstep1bb3in(ar_0, ar_1, -1)) [ 0 >= 1 /\ d >= 0 /\ 0 >= 2*d /\ 2*d + 1 >= 0 /\ 0 >= e /\ 2*e >= 0 /\ 1 >= 2*e /\ ar_2 + 1 = 0 ] (Comp: ?, Cost: 1) evalrealheapsortstep1bb2in(ar_0, ar_1, ar_2) -> Com_1(evalrealheapsortstep1bb3in(ar_0, ar_1, d - 1)) [ ar_2 >= 0 /\ e >= 0 /\ ar_2 + 1 >= 2*e /\ 2*e >= ar_2 /\ 0 >= ar_2 + 2 /\ 0 >= f /\ d >= 0 /\ ar_2 + 1 >= 2*d /\ 2*d >= ar_2 /\ 2*f >= ar_2 + 1 /\ ar_2 + 2 >= 2*f ] (Comp: ?, Cost: 1) evalrealheapsortstep1bb2in(ar_0, ar_1, ar_2) -> Com_1(evalrealheapsortstep1bb3in(ar_0, ar_1, d - 1)) [ ar_2 >= 0 /\ e >= 0 /\ ar_2 + 1 >= 2*e /\ 2*e >= ar_2 /\ 0 >= ar_2 + 2 /\ 0 >= f /\ 0 >= d /\ 2*f >= ar_2 + 1 /\ ar_2 + 2 >= 2*f /\ 2*d >= ar_2 + 1 /\ ar_2 + 2 >= 2*d ] (Comp: ?, Cost: 1) evalrealheapsortstep1bb2in(ar_0, ar_1, ar_2) -> Com_1(evalrealheapsortstep1bb3in(ar_0, ar_1, -1)) [ 0 >= 1 /\ 0 >= d /\ e >= 0 /\ 0 >= 2*e /\ 2*e + 1 >= 0 /\ 2*d >= 0 /\ 1 >= 2*d /\ ar_2 + 1 = 0 ] (Comp: ?, Cost: 1) evalrealheapsortstep1bb2in(ar_0, ar_1, ar_2) -> Com_1(evalrealheapsortstep1bb3in(ar_0, ar_1, d - 1)) [ 0 >= ar_2 + 2 /\ 0 >= e /\ ar_2 >= 0 /\ f >= 0 /\ ar_2 + 1 >= 2*f /\ 2*f >= ar_2 /\ d >= 0 /\ ar_2 + 1 >= 2*d /\ 2*d >= ar_2 /\ 2*e >= ar_2 + 1 /\ ar_2 + 2 >= 2*e ] (Comp: ?, Cost: 1) evalrealheapsortstep1bb2in(ar_0, ar_1, ar_2) -> Com_1(evalrealheapsortstep1bb3in(ar_0, ar_1, d - 1)) [ 0 >= ar_2 + 2 /\ 0 >= e /\ ar_2 >= 0 /\ f >= 0 /\ ar_2 + 1 >= 2*f /\ 2*f >= ar_2 /\ 0 >= d /\ 2*e >= ar_2 + 1 /\ ar_2 + 2 >= 2*e /\ 2*d >= ar_2 + 1 /\ ar_2 + 2 >= 2*d ] (Comp: ?, Cost: 1) evalrealheapsortstep1bb2in(ar_0, ar_1, ar_2) -> Com_1(evalrealheapsortstep1bb3in(ar_0, ar_1, -1)) [ 0 >= 1 /\ 0 >= d /\ 0 >= e /\ 2*d >= 0 /\ 1 >= 2*d /\ 2*e >= 0 /\ 1 >= 2*e /\ ar_2 + 1 = 0 ] (Comp: ?, Cost: 1) evalrealheapsortstep1bb2in(ar_0, ar_1, ar_2) -> Com_1(evalrealheapsortstep1bb3in(ar_0, ar_1, d - 1)) [ 0 >= ar_2 + 2 /\ 0 >= e /\ 0 >= f /\ ar_2 >= 0 /\ d >= 0 /\ ar_2 + 1 >= 2*d /\ 2*d >= ar_2 /\ 2*e >= ar_2 + 1 /\ ar_2 + 2 >= 2*e /\ 2*f >= ar_2 + 1 /\ ar_2 + 2 >= 2*f ] (Comp: ?, Cost: 1) evalrealheapsortstep1bb2in(ar_0, ar_1, ar_2) -> Com_1(evalrealheapsortstep1bb3in(ar_0, ar_1, d - 1)) [ 0 >= ar_2 + 2 /\ 0 >= e /\ 0 >= f /\ 0 >= d /\ 2*e >= ar_2 + 1 /\ ar_2 + 2 >= 2*e /\ 2*f >= ar_2 + 1 /\ ar_2 + 2 >= 2*f /\ 2*d >= ar_2 + 1 /\ ar_2 + 2 >= 2*d ] (Comp: ?, Cost: 1) evalrealheapsortstep1bb5in(ar_0, ar_1, ar_2) -> Com_1(evalrealheapsortstep1bb6in(ar_0, ar_1 + 1, ar_2)) (Comp: ?, Cost: 1) evalrealheapsortstep1returnin(ar_0, ar_1, ar_2) -> Com_1(evalrealheapsortstep1stop(ar_0, ar_1, ar_2)) (Comp: 1, Cost: 0) koat_start(ar_0, ar_1, ar_2) -> Com_1(evalrealheapsortstep1start(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 transitions from problem 1: evalrealheapsortstep1bb4in(ar_0, ar_1, ar_2) -> Com_1(evalrealheapsortstep1bb2in(ar_0, ar_1, ar_2)) [ ar_2 + 1 = 0 ] evalrealheapsortstep1bb4in(ar_0, ar_1, ar_2) -> Com_1(evalrealheapsortstep1bb2in(ar_0, ar_1, ar_2)) [ 0 >= ar_2 + 2 /\ 0 >= d /\ 2*d >= ar_2 + 1 /\ ar_2 + 2 >= 2*d ] evalrealheapsortstep1bb4in(ar_0, ar_1, ar_2) -> Com_1(evalrealheapsortstep1bb5in(ar_0, ar_1, ar_2)) [ ar_2 + 1 = 0 ] evalrealheapsortstep1bb4in(ar_0, ar_1, ar_2) -> Com_1(evalrealheapsortstep1bb5in(ar_0, ar_1, ar_2)) [ 0 >= ar_2 + 2 /\ 0 >= d /\ 2*d >= ar_2 + 1 /\ ar_2 + 2 >= 2*d ] evalrealheapsortstep1bb2in(ar_0, ar_1, ar_2) -> Com_1(evalrealheapsortstep1bb3in(ar_0, ar_1, -1)) [ ar_2 + 1 = 0 ] evalrealheapsortstep1bb2in(ar_0, ar_1, ar_2) -> Com_1(evalrealheapsortstep1bb3in(ar_0, ar_1, d - 1)) [ 0 >= 1 /\ d >= 0 /\ 0 >= 2*d /\ 2*d + 1 >= 0 /\ ar_2 + 1 = 0 ] evalrealheapsortstep1bb2in(ar_0, ar_1, ar_2) -> Com_1(evalrealheapsortstep1bb3in(ar_0, ar_1, d - 1)) [ 0 >= 1 /\ 0 >= d /\ 2*d >= 0 /\ 1 >= 2*d /\ ar_2 + 1 = 0 ] evalrealheapsortstep1bb2in(ar_0, ar_1, ar_2) -> Com_1(evalrealheapsortstep1bb3in(ar_0, ar_1, -1)) [ 0 >= 1 /\ d >= 0 /\ 0 >= 2*d /\ 2*d + 1 >= 0 /\ ar_2 + 1 = 0 ] evalrealheapsortstep1bb2in(ar_0, ar_1, ar_2) -> Com_1(evalrealheapsortstep1bb3in(ar_0, ar_1, d - 1)) [ 0 >= 1 /\ e >= 0 /\ 0 >= 2*e /\ 2*e + 1 >= 0 /\ d >= 0 /\ 0 >= 2*d /\ 2*d + 1 >= 0 /\ ar_2 + 1 = 0 ] evalrealheapsortstep1bb2in(ar_0, ar_1, ar_2) -> Com_1(evalrealheapsortstep1bb3in(ar_0, ar_1, d - 1)) [ 0 >= 1 /\ e >= 0 /\ 0 >= 2*e /\ 2*e + 1 >= 0 /\ 0 >= d /\ 2*d >= 0 /\ 1 >= 2*d /\ ar_2 + 1 = 0 ] evalrealheapsortstep1bb2in(ar_0, ar_1, ar_2) -> Com_1(evalrealheapsortstep1bb3in(ar_0, ar_1, -1)) [ 0 >= 1 /\ 0 >= d /\ 2*d >= 0 /\ 1 >= 2*d /\ ar_2 + 1 = 0 ] evalrealheapsortstep1bb2in(ar_0, ar_1, ar_2) -> Com_1(evalrealheapsortstep1bb3in(ar_0, ar_1, d - 1)) [ 0 >= 1 /\ 0 >= e /\ d >= 0 /\ 0 >= 2*d /\ 2*d + 1 >= 0 /\ 2*e >= 0 /\ 1 >= 2*e /\ ar_2 + 1 = 0 ] evalrealheapsortstep1bb2in(ar_0, ar_1, ar_2) -> Com_1(evalrealheapsortstep1bb3in(ar_0, ar_1, d - 1)) [ 0 >= 1 /\ 0 >= e /\ 0 >= d /\ 2*e >= 0 /\ 1 >= 2*e /\ 2*d >= 0 /\ 1 >= 2*d /\ ar_2 + 1 = 0 ] evalrealheapsortstep1bb2in(ar_0, ar_1, ar_2) -> Com_1(evalrealheapsortstep1bb3in(ar_0, ar_1, -1)) [ 0 >= 1 /\ d >= 0 /\ 0 >= 2*d /\ 2*d + 1 >= 0 /\ e >= 0 /\ 0 >= 2*e /\ 2*e + 1 >= 0 /\ ar_2 + 1 = 0 ] evalrealheapsortstep1bb2in(ar_0, ar_1, ar_2) -> Com_1(evalrealheapsortstep1bb3in(ar_0, ar_1, d - 1)) [ ar_2 >= 0 /\ e >= 0 /\ ar_2 + 1 >= 2*e /\ 2*e >= ar_2 /\ f >= 0 /\ ar_2 + 1 >= 2*f /\ 2*f >= ar_2 /\ 0 >= ar_2 + 2 /\ 0 >= d /\ 2*d >= ar_2 + 1 /\ ar_2 + 2 >= 2*d ] evalrealheapsortstep1bb2in(ar_0, ar_1, ar_2) -> Com_1(evalrealheapsortstep1bb3in(ar_0, ar_1, -1)) [ 0 >= 1 /\ d >= 0 /\ 0 >= 2*d /\ 2*d + 1 >= 0 /\ 0 >= e /\ 2*e >= 0 /\ 1 >= 2*e /\ ar_2 + 1 = 0 ] evalrealheapsortstep1bb2in(ar_0, ar_1, ar_2) -> Com_1(evalrealheapsortstep1bb3in(ar_0, ar_1, d - 1)) [ ar_2 >= 0 /\ e >= 0 /\ ar_2 + 1 >= 2*e /\ 2*e >= ar_2 /\ 0 >= ar_2 + 2 /\ 0 >= f /\ d >= 0 /\ ar_2 + 1 >= 2*d /\ 2*d >= ar_2 /\ 2*f >= ar_2 + 1 /\ ar_2 + 2 >= 2*f ] evalrealheapsortstep1bb2in(ar_0, ar_1, ar_2) -> Com_1(evalrealheapsortstep1bb3in(ar_0, ar_1, d - 1)) [ ar_2 >= 0 /\ e >= 0 /\ ar_2 + 1 >= 2*e /\ 2*e >= ar_2 /\ 0 >= ar_2 + 2 /\ 0 >= f /\ 0 >= d /\ 2*f >= ar_2 + 1 /\ ar_2 + 2 >= 2*f /\ 2*d >= ar_2 + 1 /\ ar_2 + 2 >= 2*d ] evalrealheapsortstep1bb2in(ar_0, ar_1, ar_2) -> Com_1(evalrealheapsortstep1bb3in(ar_0, ar_1, -1)) [ 0 >= 1 /\ 0 >= d /\ e >= 0 /\ 0 >= 2*e /\ 2*e + 1 >= 0 /\ 2*d >= 0 /\ 1 >= 2*d /\ ar_2 + 1 = 0 ] evalrealheapsortstep1bb2in(ar_0, ar_1, ar_2) -> Com_1(evalrealheapsortstep1bb3in(ar_0, ar_1, d - 1)) [ 0 >= ar_2 + 2 /\ 0 >= e /\ ar_2 >= 0 /\ f >= 0 /\ ar_2 + 1 >= 2*f /\ 2*f >= ar_2 /\ d >= 0 /\ ar_2 + 1 >= 2*d /\ 2*d >= ar_2 /\ 2*e >= ar_2 + 1 /\ ar_2 + 2 >= 2*e ] evalrealheapsortstep1bb2in(ar_0, ar_1, ar_2) -> Com_1(evalrealheapsortstep1bb3in(ar_0, ar_1, d - 1)) [ 0 >= ar_2 + 2 /\ 0 >= e /\ ar_2 >= 0 /\ f >= 0 /\ ar_2 + 1 >= 2*f /\ 2*f >= ar_2 /\ 0 >= d /\ 2*e >= ar_2 + 1 /\ ar_2 + 2 >= 2*e /\ 2*d >= ar_2 + 1 /\ ar_2 + 2 >= 2*d ] evalrealheapsortstep1bb2in(ar_0, ar_1, ar_2) -> Com_1(evalrealheapsortstep1bb3in(ar_0, ar_1, -1)) [ 0 >= 1 /\ 0 >= d /\ 0 >= e /\ 2*d >= 0 /\ 1 >= 2*d /\ 2*e >= 0 /\ 1 >= 2*e /\ ar_2 + 1 = 0 ] evalrealheapsortstep1bb2in(ar_0, ar_1, ar_2) -> Com_1(evalrealheapsortstep1bb3in(ar_0, ar_1, d - 1)) [ 0 >= ar_2 + 2 /\ 0 >= e /\ 0 >= f /\ ar_2 >= 0 /\ d >= 0 /\ ar_2 + 1 >= 2*d /\ 2*d >= ar_2 /\ 2*e >= ar_2 + 1 /\ ar_2 + 2 >= 2*e /\ 2*f >= ar_2 + 1 /\ ar_2 + 2 >= 2*f ] evalrealheapsortstep1bb2in(ar_0, ar_1, ar_2) -> Com_1(evalrealheapsortstep1bb3in(ar_0, ar_1, d - 1)) [ 0 >= ar_2 + 2 /\ 0 >= e /\ 0 >= f /\ 0 >= d /\ 2*e >= ar_2 + 1 /\ ar_2 + 2 >= 2*e /\ 2*f >= ar_2 + 1 /\ ar_2 + 2 >= 2*f /\ 2*d >= ar_2 + 1 /\ ar_2 + 2 >= 2*d ] We thus obtain the following problem: 2: T: (Comp: ?, Cost: 1) evalrealheapsortstep1bb6in(ar_0, ar_1, ar_2) -> Com_1(evalrealheapsortstep1returnin(ar_0, ar_1, ar_2)) [ ar_1 >= ar_0 ] (Comp: ?, Cost: 1) evalrealheapsortstep1bb2in(ar_0, ar_1, ar_2) -> Com_1(evalrealheapsortstep1bb3in(ar_0, ar_1, d - 1)) [ ar_2 >= 0 /\ e >= 0 /\ ar_2 + 1 >= 2*e /\ 2*e >= ar_2 /\ f >= 0 /\ ar_2 + 1 >= 2*f /\ 2*f >= ar_2 /\ d >= 0 /\ ar_2 + 1 >= 2*d /\ 2*d >= ar_2 ] (Comp: ?, Cost: 1) evalrealheapsortstep1bb4in(ar_0, ar_1, ar_2) -> Com_1(evalrealheapsortstep1bb5in(ar_0, ar_1, ar_2)) [ ar_2 >= 0 /\ d >= 0 /\ ar_2 + 1 >= 2*d /\ 2*d >= ar_2 ] (Comp: ?, Cost: 1) evalrealheapsortstep1bb4in(ar_0, ar_1, ar_2) -> Com_1(evalrealheapsortstep1bb2in(ar_0, ar_1, ar_2)) [ ar_2 >= 0 /\ d >= 0 /\ ar_2 + 1 >= 2*d /\ 2*d >= ar_2 ] (Comp: ?, Cost: 1) evalrealheapsortstep1bb5in(ar_0, ar_1, ar_2) -> Com_1(evalrealheapsortstep1bb6in(ar_0, ar_1 + 1, ar_2)) (Comp: ?, Cost: 1) evalrealheapsortstep1bb3in(ar_0, ar_1, ar_2) -> Com_1(evalrealheapsortstep1bb4in(ar_0, ar_1, ar_2)) [ ar_2 >= 1 ] (Comp: ?, Cost: 1) evalrealheapsortstep1bb3in(ar_0, ar_1, ar_2) -> Com_1(evalrealheapsortstep1bb5in(ar_0, ar_1, ar_2)) [ 0 >= ar_2 ] (Comp: ?, Cost: 1) evalrealheapsortstep1returnin(ar_0, ar_1, ar_2) -> Com_1(evalrealheapsortstep1stop(ar_0, ar_1, ar_2)) (Comp: ?, Cost: 1) evalrealheapsortstep1bb6in(ar_0, ar_1, ar_2) -> Com_1(evalrealheapsortstep1bb3in(ar_0, ar_1, ar_1)) [ ar_0 >= ar_1 + 1 ] (Comp: ?, Cost: 1) evalrealheapsortstep1entryin(ar_0, ar_1, ar_2) -> Com_1(evalrealheapsortstep1returnin(ar_0, ar_1, ar_2)) [ 2 >= ar_0 ] (Comp: ?, Cost: 1) evalrealheapsortstep1entryin(ar_0, ar_1, ar_2) -> Com_1(evalrealheapsortstep1bb6in(ar_0, 1, ar_2)) [ ar_0 >= 3 ] (Comp: ?, Cost: 1) evalrealheapsortstep1start(ar_0, ar_1, ar_2) -> Com_1(evalrealheapsortstep1entryin(ar_0, ar_1, ar_2)) (Comp: 1, Cost: 0) koat_start(ar_0, ar_1, ar_2) -> Com_1(evalrealheapsortstep1start(ar_0, ar_1, ar_2)) [ 0 <= 0 ] start location: koat_start leaf cost: 0 Repeatedly propagating knowledge in problem 2 produces the following problem: 3: T: (Comp: ?, Cost: 1) evalrealheapsortstep1bb6in(ar_0, ar_1, ar_2) -> Com_1(evalrealheapsortstep1returnin(ar_0, ar_1, ar_2)) [ ar_1 >= ar_0 ] (Comp: ?, Cost: 1) evalrealheapsortstep1bb2in(ar_0, ar_1, ar_2) -> Com_1(evalrealheapsortstep1bb3in(ar_0, ar_1, d - 1)) [ ar_2 >= 0 /\ e >= 0 /\ ar_2 + 1 >= 2*e /\ 2*e >= ar_2 /\ f >= 0 /\ ar_2 + 1 >= 2*f /\ 2*f >= ar_2 /\ d >= 0 /\ ar_2 + 1 >= 2*d /\ 2*d >= ar_2 ] (Comp: ?, Cost: 1) evalrealheapsortstep1bb4in(ar_0, ar_1, ar_2) -> Com_1(evalrealheapsortstep1bb5in(ar_0, ar_1, ar_2)) [ ar_2 >= 0 /\ d >= 0 /\ ar_2 + 1 >= 2*d /\ 2*d >= ar_2 ] (Comp: ?, Cost: 1) evalrealheapsortstep1bb4in(ar_0, ar_1, ar_2) -> Com_1(evalrealheapsortstep1bb2in(ar_0, ar_1, ar_2)) [ ar_2 >= 0 /\ d >= 0 /\ ar_2 + 1 >= 2*d /\ 2*d >= ar_2 ] (Comp: ?, Cost: 1) evalrealheapsortstep1bb5in(ar_0, ar_1, ar_2) -> Com_1(evalrealheapsortstep1bb6in(ar_0, ar_1 + 1, ar_2)) (Comp: ?, Cost: 1) evalrealheapsortstep1bb3in(ar_0, ar_1, ar_2) -> Com_1(evalrealheapsortstep1bb4in(ar_0, ar_1, ar_2)) [ ar_2 >= 1 ] (Comp: ?, Cost: 1) evalrealheapsortstep1bb3in(ar_0, ar_1, ar_2) -> Com_1(evalrealheapsortstep1bb5in(ar_0, ar_1, ar_2)) [ 0 >= ar_2 ] (Comp: ?, Cost: 1) evalrealheapsortstep1returnin(ar_0, ar_1, ar_2) -> Com_1(evalrealheapsortstep1stop(ar_0, ar_1, ar_2)) (Comp: ?, Cost: 1) evalrealheapsortstep1bb6in(ar_0, ar_1, ar_2) -> Com_1(evalrealheapsortstep1bb3in(ar_0, ar_1, ar_1)) [ ar_0 >= ar_1 + 1 ] (Comp: 1, Cost: 1) evalrealheapsortstep1entryin(ar_0, ar_1, ar_2) -> Com_1(evalrealheapsortstep1returnin(ar_0, ar_1, ar_2)) [ 2 >= ar_0 ] (Comp: 1, Cost: 1) evalrealheapsortstep1entryin(ar_0, ar_1, ar_2) -> Com_1(evalrealheapsortstep1bb6in(ar_0, 1, ar_2)) [ ar_0 >= 3 ] (Comp: 1, Cost: 1) evalrealheapsortstep1start(ar_0, ar_1, ar_2) -> Com_1(evalrealheapsortstep1entryin(ar_0, ar_1, ar_2)) (Comp: 1, Cost: 0) koat_start(ar_0, ar_1, ar_2) -> Com_1(evalrealheapsortstep1start(ar_0, ar_1, ar_2)) [ 0 <= 0 ] start location: koat_start leaf cost: 0 A polynomial rank function with Pol(evalrealheapsortstep1bb6in) = 2 Pol(evalrealheapsortstep1returnin) = 1 Pol(evalrealheapsortstep1bb2in) = 2 Pol(evalrealheapsortstep1bb3in) = 2 Pol(evalrealheapsortstep1bb4in) = 2 Pol(evalrealheapsortstep1bb5in) = 2 Pol(evalrealheapsortstep1stop) = 0 Pol(evalrealheapsortstep1entryin) = 2 Pol(evalrealheapsortstep1start) = 2 Pol(koat_start) = 2 orients all transitions weakly and the transitions evalrealheapsortstep1returnin(ar_0, ar_1, ar_2) -> Com_1(evalrealheapsortstep1stop(ar_0, ar_1, ar_2)) evalrealheapsortstep1bb6in(ar_0, ar_1, ar_2) -> Com_1(evalrealheapsortstep1returnin(ar_0, ar_1, ar_2)) [ ar_1 >= ar_0 ] strictly and produces the following problem: 4: T: (Comp: 2, Cost: 1) evalrealheapsortstep1bb6in(ar_0, ar_1, ar_2) -> Com_1(evalrealheapsortstep1returnin(ar_0, ar_1, ar_2)) [ ar_1 >= ar_0 ] (Comp: ?, Cost: 1) evalrealheapsortstep1bb2in(ar_0, ar_1, ar_2) -> Com_1(evalrealheapsortstep1bb3in(ar_0, ar_1, d - 1)) [ ar_2 >= 0 /\ e >= 0 /\ ar_2 + 1 >= 2*e /\ 2*e >= ar_2 /\ f >= 0 /\ ar_2 + 1 >= 2*f /\ 2*f >= ar_2 /\ d >= 0 /\ ar_2 + 1 >= 2*d /\ 2*d >= ar_2 ] (Comp: ?, Cost: 1) evalrealheapsortstep1bb4in(ar_0, ar_1, ar_2) -> Com_1(evalrealheapsortstep1bb5in(ar_0, ar_1, ar_2)) [ ar_2 >= 0 /\ d >= 0 /\ ar_2 + 1 >= 2*d /\ 2*d >= ar_2 ] (Comp: ?, Cost: 1) evalrealheapsortstep1bb4in(ar_0, ar_1, ar_2) -> Com_1(evalrealheapsortstep1bb2in(ar_0, ar_1, ar_2)) [ ar_2 >= 0 /\ d >= 0 /\ ar_2 + 1 >= 2*d /\ 2*d >= ar_2 ] (Comp: ?, Cost: 1) evalrealheapsortstep1bb5in(ar_0, ar_1, ar_2) -> Com_1(evalrealheapsortstep1bb6in(ar_0, ar_1 + 1, ar_2)) (Comp: ?, Cost: 1) evalrealheapsortstep1bb3in(ar_0, ar_1, ar_2) -> Com_1(evalrealheapsortstep1bb4in(ar_0, ar_1, ar_2)) [ ar_2 >= 1 ] (Comp: ?, Cost: 1) evalrealheapsortstep1bb3in(ar_0, ar_1, ar_2) -> Com_1(evalrealheapsortstep1bb5in(ar_0, ar_1, ar_2)) [ 0 >= ar_2 ] (Comp: 2, Cost: 1) evalrealheapsortstep1returnin(ar_0, ar_1, ar_2) -> Com_1(evalrealheapsortstep1stop(ar_0, ar_1, ar_2)) (Comp: ?, Cost: 1) evalrealheapsortstep1bb6in(ar_0, ar_1, ar_2) -> Com_1(evalrealheapsortstep1bb3in(ar_0, ar_1, ar_1)) [ ar_0 >= ar_1 + 1 ] (Comp: 1, Cost: 1) evalrealheapsortstep1entryin(ar_0, ar_1, ar_2) -> Com_1(evalrealheapsortstep1returnin(ar_0, ar_1, ar_2)) [ 2 >= ar_0 ] (Comp: 1, Cost: 1) evalrealheapsortstep1entryin(ar_0, ar_1, ar_2) -> Com_1(evalrealheapsortstep1bb6in(ar_0, 1, ar_2)) [ ar_0 >= 3 ] (Comp: 1, Cost: 1) evalrealheapsortstep1start(ar_0, ar_1, ar_2) -> Com_1(evalrealheapsortstep1entryin(ar_0, ar_1, ar_2)) (Comp: 1, Cost: 0) koat_start(ar_0, ar_1, ar_2) -> Com_1(evalrealheapsortstep1start(ar_0, ar_1, ar_2)) [ 0 <= 0 ] start location: koat_start leaf cost: 0 A polynomial rank function with Pol(evalrealheapsortstep1bb6in) = V_1 - V_2 + 1 Pol(evalrealheapsortstep1bb3in) = V_1 - V_2 Pol(evalrealheapsortstep1bb5in) = V_1 - V_2 Pol(evalrealheapsortstep1bb4in) = V_1 - V_2 Pol(evalrealheapsortstep1bb2in) = V_1 - V_2 and size complexities S("koat_start(ar_0, ar_1, ar_2) -> Com_1(evalrealheapsortstep1start(ar_0, ar_1, ar_2)) [ 0 <= 0 ]", 0-0) = ar_0 S("koat_start(ar_0, ar_1, ar_2) -> Com_1(evalrealheapsortstep1start(ar_0, ar_1, ar_2)) [ 0 <= 0 ]", 0-1) = ar_1 S("koat_start(ar_0, ar_1, ar_2) -> Com_1(evalrealheapsortstep1start(ar_0, ar_1, ar_2)) [ 0 <= 0 ]", 0-2) = ar_2 S("evalrealheapsortstep1start(ar_0, ar_1, ar_2) -> Com_1(evalrealheapsortstep1entryin(ar_0, ar_1, ar_2))", 0-0) = ar_0 S("evalrealheapsortstep1start(ar_0, ar_1, ar_2) -> Com_1(evalrealheapsortstep1entryin(ar_0, ar_1, ar_2))", 0-1) = ar_1 S("evalrealheapsortstep1start(ar_0, ar_1, ar_2) -> Com_1(evalrealheapsortstep1entryin(ar_0, ar_1, ar_2))", 0-2) = ar_2 S("evalrealheapsortstep1entryin(ar_0, ar_1, ar_2) -> Com_1(evalrealheapsortstep1bb6in(ar_0, 1, ar_2)) [ ar_0 >= 3 ]", 0-0) = ar_0 S("evalrealheapsortstep1entryin(ar_0, ar_1, ar_2) -> Com_1(evalrealheapsortstep1bb6in(ar_0, 1, ar_2)) [ ar_0 >= 3 ]", 0-1) = 1 S("evalrealheapsortstep1entryin(ar_0, ar_1, ar_2) -> Com_1(evalrealheapsortstep1bb6in(ar_0, 1, ar_2)) [ ar_0 >= 3 ]", 0-2) = ar_2 S("evalrealheapsortstep1entryin(ar_0, ar_1, ar_2) -> Com_1(evalrealheapsortstep1returnin(ar_0, ar_1, ar_2)) [ 2 >= ar_0 ]", 0-0) = ar_0 S("evalrealheapsortstep1entryin(ar_0, ar_1, ar_2) -> Com_1(evalrealheapsortstep1returnin(ar_0, ar_1, ar_2)) [ 2 >= ar_0 ]", 0-1) = ar_1 S("evalrealheapsortstep1entryin(ar_0, ar_1, ar_2) -> Com_1(evalrealheapsortstep1returnin(ar_0, ar_1, ar_2)) [ 2 >= ar_0 ]", 0-2) = ar_2 S("evalrealheapsortstep1bb6in(ar_0, ar_1, ar_2) -> Com_1(evalrealheapsortstep1bb3in(ar_0, ar_1, ar_1)) [ ar_0 >= ar_1 + 1 ]", 0-0) = ar_0 S("evalrealheapsortstep1bb6in(ar_0, ar_1, ar_2) -> Com_1(evalrealheapsortstep1bb3in(ar_0, ar_1, ar_1)) [ ar_0 >= ar_1 + 1 ]", 0-1) = ? S("evalrealheapsortstep1bb6in(ar_0, ar_1, ar_2) -> Com_1(evalrealheapsortstep1bb3in(ar_0, ar_1, ar_1)) [ ar_0 >= ar_1 + 1 ]", 0-2) = ? S("evalrealheapsortstep1returnin(ar_0, ar_1, ar_2) -> Com_1(evalrealheapsortstep1stop(ar_0, ar_1, ar_2))", 0-0) = ar_0 S("evalrealheapsortstep1returnin(ar_0, ar_1, ar_2) -> Com_1(evalrealheapsortstep1stop(ar_0, ar_1, ar_2))", 0-1) = ? S("evalrealheapsortstep1returnin(ar_0, ar_1, ar_2) -> Com_1(evalrealheapsortstep1stop(ar_0, ar_1, ar_2))", 0-2) = ? S("evalrealheapsortstep1bb3in(ar_0, ar_1, ar_2) -> Com_1(evalrealheapsortstep1bb5in(ar_0, ar_1, ar_2)) [ 0 >= ar_2 ]", 0-0) = ar_0 S("evalrealheapsortstep1bb3in(ar_0, ar_1, ar_2) -> Com_1(evalrealheapsortstep1bb5in(ar_0, ar_1, ar_2)) [ 0 >= ar_2 ]", 0-1) = ? S("evalrealheapsortstep1bb3in(ar_0, ar_1, ar_2) -> Com_1(evalrealheapsortstep1bb5in(ar_0, ar_1, ar_2)) [ 0 >= ar_2 ]", 0-2) = ? S("evalrealheapsortstep1bb3in(ar_0, ar_1, ar_2) -> Com_1(evalrealheapsortstep1bb4in(ar_0, ar_1, ar_2)) [ ar_2 >= 1 ]", 0-0) = ar_0 S("evalrealheapsortstep1bb3in(ar_0, ar_1, ar_2) -> Com_1(evalrealheapsortstep1bb4in(ar_0, ar_1, ar_2)) [ ar_2 >= 1 ]", 0-1) = ? S("evalrealheapsortstep1bb3in(ar_0, ar_1, ar_2) -> Com_1(evalrealheapsortstep1bb4in(ar_0, ar_1, ar_2)) [ ar_2 >= 1 ]", 0-2) = ? S("evalrealheapsortstep1bb5in(ar_0, ar_1, ar_2) -> Com_1(evalrealheapsortstep1bb6in(ar_0, ar_1 + 1, ar_2))", 0-0) = ar_0 S("evalrealheapsortstep1bb5in(ar_0, ar_1, ar_2) -> Com_1(evalrealheapsortstep1bb6in(ar_0, ar_1 + 1, ar_2))", 0-1) = ? S("evalrealheapsortstep1bb5in(ar_0, ar_1, ar_2) -> Com_1(evalrealheapsortstep1bb6in(ar_0, ar_1 + 1, ar_2))", 0-2) = ? S("evalrealheapsortstep1bb4in(ar_0, ar_1, ar_2) -> Com_1(evalrealheapsortstep1bb2in(ar_0, ar_1, ar_2)) [ ar_2 >= 0 /\\ d >= 0 /\\ ar_2 + 1 >= 2*d /\\ 2*d >= ar_2 ]", 0-0) = ar_0 S("evalrealheapsortstep1bb4in(ar_0, ar_1, ar_2) -> Com_1(evalrealheapsortstep1bb2in(ar_0, ar_1, ar_2)) [ ar_2 >= 0 /\\ d >= 0 /\\ ar_2 + 1 >= 2*d /\\ 2*d >= ar_2 ]", 0-1) = ? S("evalrealheapsortstep1bb4in(ar_0, ar_1, ar_2) -> Com_1(evalrealheapsortstep1bb2in(ar_0, ar_1, ar_2)) [ ar_2 >= 0 /\\ d >= 0 /\\ ar_2 + 1 >= 2*d /\\ 2*d >= ar_2 ]", 0-2) = ? S("evalrealheapsortstep1bb4in(ar_0, ar_1, ar_2) -> Com_1(evalrealheapsortstep1bb5in(ar_0, ar_1, ar_2)) [ ar_2 >= 0 /\\ d >= 0 /\\ ar_2 + 1 >= 2*d /\\ 2*d >= ar_2 ]", 0-0) = ar_0 S("evalrealheapsortstep1bb4in(ar_0, ar_1, ar_2) -> Com_1(evalrealheapsortstep1bb5in(ar_0, ar_1, ar_2)) [ ar_2 >= 0 /\\ d >= 0 /\\ ar_2 + 1 >= 2*d /\\ 2*d >= ar_2 ]", 0-1) = ? S("evalrealheapsortstep1bb4in(ar_0, ar_1, ar_2) -> Com_1(evalrealheapsortstep1bb5in(ar_0, ar_1, ar_2)) [ ar_2 >= 0 /\\ d >= 0 /\\ ar_2 + 1 >= 2*d /\\ 2*d >= ar_2 ]", 0-2) = ? S("evalrealheapsortstep1bb2in(ar_0, ar_1, ar_2) -> Com_1(evalrealheapsortstep1bb3in(ar_0, ar_1, d - 1)) [ ar_2 >= 0 /\\ e >= 0 /\\ ar_2 + 1 >= 2*e /\\ 2*e >= ar_2 /\\ f >= 0 /\\ ar_2 + 1 >= 2*f /\\ 2*f >= ar_2 /\\ d >= 0 /\\ ar_2 + 1 >= 2*d /\\ 2*d >= ar_2 ]", 0-0) = ar_0 S("evalrealheapsortstep1bb2in(ar_0, ar_1, ar_2) -> Com_1(evalrealheapsortstep1bb3in(ar_0, ar_1, d - 1)) [ ar_2 >= 0 /\\ e >= 0 /\\ ar_2 + 1 >= 2*e /\\ 2*e >= ar_2 /\\ f >= 0 /\\ ar_2 + 1 >= 2*f /\\ 2*f >= ar_2 /\\ d >= 0 /\\ ar_2 + 1 >= 2*d /\\ 2*d >= ar_2 ]", 0-1) = ? S("evalrealheapsortstep1bb2in(ar_0, ar_1, ar_2) -> Com_1(evalrealheapsortstep1bb3in(ar_0, ar_1, d - 1)) [ ar_2 >= 0 /\\ e >= 0 /\\ ar_2 + 1 >= 2*e /\\ 2*e >= ar_2 /\\ f >= 0 /\\ ar_2 + 1 >= 2*f /\\ 2*f >= ar_2 /\\ d >= 0 /\\ ar_2 + 1 >= 2*d /\\ 2*d >= ar_2 ]", 0-2) = ? S("evalrealheapsortstep1bb6in(ar_0, ar_1, ar_2) -> Com_1(evalrealheapsortstep1returnin(ar_0, ar_1, ar_2)) [ ar_1 >= ar_0 ]", 0-0) = ar_0 S("evalrealheapsortstep1bb6in(ar_0, ar_1, ar_2) -> Com_1(evalrealheapsortstep1returnin(ar_0, ar_1, ar_2)) [ ar_1 >= ar_0 ]", 0-1) = ? S("evalrealheapsortstep1bb6in(ar_0, ar_1, ar_2) -> Com_1(evalrealheapsortstep1returnin(ar_0, ar_1, ar_2)) [ ar_1 >= ar_0 ]", 0-2) = ? orients the transitions evalrealheapsortstep1bb6in(ar_0, ar_1, ar_2) -> Com_1(evalrealheapsortstep1bb3in(ar_0, ar_1, ar_1)) [ ar_0 >= ar_1 + 1 ] evalrealheapsortstep1bb5in(ar_0, ar_1, ar_2) -> Com_1(evalrealheapsortstep1bb6in(ar_0, ar_1 + 1, ar_2)) evalrealheapsortstep1bb4in(ar_0, ar_1, ar_2) -> Com_1(evalrealheapsortstep1bb5in(ar_0, ar_1, ar_2)) [ ar_2 >= 0 /\ d >= 0 /\ ar_2 + 1 >= 2*d /\ 2*d >= ar_2 ] evalrealheapsortstep1bb4in(ar_0, ar_1, ar_2) -> Com_1(evalrealheapsortstep1bb2in(ar_0, ar_1, ar_2)) [ ar_2 >= 0 /\ d >= 0 /\ ar_2 + 1 >= 2*d /\ 2*d >= ar_2 ] evalrealheapsortstep1bb3in(ar_0, ar_1, ar_2) -> Com_1(evalrealheapsortstep1bb5in(ar_0, ar_1, ar_2)) [ 0 >= ar_2 ] evalrealheapsortstep1bb3in(ar_0, ar_1, ar_2) -> Com_1(evalrealheapsortstep1bb4in(ar_0, ar_1, ar_2)) [ ar_2 >= 1 ] evalrealheapsortstep1bb2in(ar_0, ar_1, ar_2) -> Com_1(evalrealheapsortstep1bb3in(ar_0, ar_1, d - 1)) [ ar_2 >= 0 /\ e >= 0 /\ ar_2 + 1 >= 2*e /\ 2*e >= ar_2 /\ f >= 0 /\ ar_2 + 1 >= 2*f /\ 2*f >= ar_2 /\ d >= 0 /\ ar_2 + 1 >= 2*d /\ 2*d >= ar_2 ] weakly and the transition evalrealheapsortstep1bb6in(ar_0, ar_1, ar_2) -> Com_1(evalrealheapsortstep1bb3in(ar_0, ar_1, ar_1)) [ ar_0 >= ar_1 + 1 ] strictly and produces the following problem: 5: T: (Comp: 2, Cost: 1) evalrealheapsortstep1bb6in(ar_0, ar_1, ar_2) -> Com_1(evalrealheapsortstep1returnin(ar_0, ar_1, ar_2)) [ ar_1 >= ar_0 ] (Comp: ?, Cost: 1) evalrealheapsortstep1bb2in(ar_0, ar_1, ar_2) -> Com_1(evalrealheapsortstep1bb3in(ar_0, ar_1, d - 1)) [ ar_2 >= 0 /\ e >= 0 /\ ar_2 + 1 >= 2*e /\ 2*e >= ar_2 /\ f >= 0 /\ ar_2 + 1 >= 2*f /\ 2*f >= ar_2 /\ d >= 0 /\ ar_2 + 1 >= 2*d /\ 2*d >= ar_2 ] (Comp: ?, Cost: 1) evalrealheapsortstep1bb4in(ar_0, ar_1, ar_2) -> Com_1(evalrealheapsortstep1bb5in(ar_0, ar_1, ar_2)) [ ar_2 >= 0 /\ d >= 0 /\ ar_2 + 1 >= 2*d /\ 2*d >= ar_2 ] (Comp: ?, Cost: 1) evalrealheapsortstep1bb4in(ar_0, ar_1, ar_2) -> Com_1(evalrealheapsortstep1bb2in(ar_0, ar_1, ar_2)) [ ar_2 >= 0 /\ d >= 0 /\ ar_2 + 1 >= 2*d /\ 2*d >= ar_2 ] (Comp: ?, Cost: 1) evalrealheapsortstep1bb5in(ar_0, ar_1, ar_2) -> Com_1(evalrealheapsortstep1bb6in(ar_0, ar_1 + 1, ar_2)) (Comp: ?, Cost: 1) evalrealheapsortstep1bb3in(ar_0, ar_1, ar_2) -> Com_1(evalrealheapsortstep1bb4in(ar_0, ar_1, ar_2)) [ ar_2 >= 1 ] (Comp: ?, Cost: 1) evalrealheapsortstep1bb3in(ar_0, ar_1, ar_2) -> Com_1(evalrealheapsortstep1bb5in(ar_0, ar_1, ar_2)) [ 0 >= ar_2 ] (Comp: 2, Cost: 1) evalrealheapsortstep1returnin(ar_0, ar_1, ar_2) -> Com_1(evalrealheapsortstep1stop(ar_0, ar_1, ar_2)) (Comp: ar_0 + 2, Cost: 1) evalrealheapsortstep1bb6in(ar_0, ar_1, ar_2) -> Com_1(evalrealheapsortstep1bb3in(ar_0, ar_1, ar_1)) [ ar_0 >= ar_1 + 1 ] (Comp: 1, Cost: 1) evalrealheapsortstep1entryin(ar_0, ar_1, ar_2) -> Com_1(evalrealheapsortstep1returnin(ar_0, ar_1, ar_2)) [ 2 >= ar_0 ] (Comp: 1, Cost: 1) evalrealheapsortstep1entryin(ar_0, ar_1, ar_2) -> Com_1(evalrealheapsortstep1bb6in(ar_0, 1, ar_2)) [ ar_0 >= 3 ] (Comp: 1, Cost: 1) evalrealheapsortstep1start(ar_0, ar_1, ar_2) -> Com_1(evalrealheapsortstep1entryin(ar_0, ar_1, ar_2)) (Comp: 1, Cost: 0) koat_start(ar_0, ar_1, ar_2) -> Com_1(evalrealheapsortstep1start(ar_0, ar_1, ar_2)) [ 0 <= 0 ] start location: koat_start leaf cost: 0 A polynomial rank function with Pol(evalrealheapsortstep1bb5in) = 1 Pol(evalrealheapsortstep1bb6in) = 0 Pol(evalrealheapsortstep1bb4in) = 2 Pol(evalrealheapsortstep1bb2in) = 2 Pol(evalrealheapsortstep1bb3in) = 2 and size complexities S("koat_start(ar_0, ar_1, ar_2) -> Com_1(evalrealheapsortstep1start(ar_0, ar_1, ar_2)) [ 0 <= 0 ]", 0-0) = ar_0 S("koat_start(ar_0, ar_1, ar_2) -> Com_1(evalrealheapsortstep1start(ar_0, ar_1, ar_2)) [ 0 <= 0 ]", 0-1) = ar_1 S("koat_start(ar_0, ar_1, ar_2) -> Com_1(evalrealheapsortstep1start(ar_0, ar_1, ar_2)) [ 0 <= 0 ]", 0-2) = ar_2 S("evalrealheapsortstep1start(ar_0, ar_1, ar_2) -> Com_1(evalrealheapsortstep1entryin(ar_0, ar_1, ar_2))", 0-0) = ar_0 S("evalrealheapsortstep1start(ar_0, ar_1, ar_2) -> Com_1(evalrealheapsortstep1entryin(ar_0, ar_1, ar_2))", 0-1) = ar_1 S("evalrealheapsortstep1start(ar_0, ar_1, ar_2) -> Com_1(evalrealheapsortstep1entryin(ar_0, ar_1, ar_2))", 0-2) = ar_2 S("evalrealheapsortstep1entryin(ar_0, ar_1, ar_2) -> Com_1(evalrealheapsortstep1bb6in(ar_0, 1, ar_2)) [ ar_0 >= 3 ]", 0-0) = ar_0 S("evalrealheapsortstep1entryin(ar_0, ar_1, ar_2) -> Com_1(evalrealheapsortstep1bb6in(ar_0, 1, ar_2)) [ ar_0 >= 3 ]", 0-1) = 1 S("evalrealheapsortstep1entryin(ar_0, ar_1, ar_2) -> Com_1(evalrealheapsortstep1bb6in(ar_0, 1, ar_2)) [ ar_0 >= 3 ]", 0-2) = ar_2 S("evalrealheapsortstep1entryin(ar_0, ar_1, ar_2) -> Com_1(evalrealheapsortstep1returnin(ar_0, ar_1, ar_2)) [ 2 >= ar_0 ]", 0-0) = ar_0 S("evalrealheapsortstep1entryin(ar_0, ar_1, ar_2) -> Com_1(evalrealheapsortstep1returnin(ar_0, ar_1, ar_2)) [ 2 >= ar_0 ]", 0-1) = ar_1 S("evalrealheapsortstep1entryin(ar_0, ar_1, ar_2) -> Com_1(evalrealheapsortstep1returnin(ar_0, ar_1, ar_2)) [ 2 >= ar_0 ]", 0-2) = ar_2 S("evalrealheapsortstep1bb6in(ar_0, ar_1, ar_2) -> Com_1(evalrealheapsortstep1bb3in(ar_0, ar_1, ar_1)) [ ar_0 >= ar_1 + 1 ]", 0-0) = ar_0 S("evalrealheapsortstep1bb6in(ar_0, ar_1, ar_2) -> Com_1(evalrealheapsortstep1bb3in(ar_0, ar_1, ar_1)) [ ar_0 >= ar_1 + 1 ]", 0-1) = ? S("evalrealheapsortstep1bb6in(ar_0, ar_1, ar_2) -> Com_1(evalrealheapsortstep1bb3in(ar_0, ar_1, ar_1)) [ ar_0 >= ar_1 + 1 ]", 0-2) = ? S("evalrealheapsortstep1returnin(ar_0, ar_1, ar_2) -> Com_1(evalrealheapsortstep1stop(ar_0, ar_1, ar_2))", 0-0) = ar_0 S("evalrealheapsortstep1returnin(ar_0, ar_1, ar_2) -> Com_1(evalrealheapsortstep1stop(ar_0, ar_1, ar_2))", 0-1) = ? S("evalrealheapsortstep1returnin(ar_0, ar_1, ar_2) -> Com_1(evalrealheapsortstep1stop(ar_0, ar_1, ar_2))", 0-2) = ? S("evalrealheapsortstep1bb3in(ar_0, ar_1, ar_2) -> Com_1(evalrealheapsortstep1bb5in(ar_0, ar_1, ar_2)) [ 0 >= ar_2 ]", 0-0) = ar_0 S("evalrealheapsortstep1bb3in(ar_0, ar_1, ar_2) -> Com_1(evalrealheapsortstep1bb5in(ar_0, ar_1, ar_2)) [ 0 >= ar_2 ]", 0-1) = ? S("evalrealheapsortstep1bb3in(ar_0, ar_1, ar_2) -> Com_1(evalrealheapsortstep1bb5in(ar_0, ar_1, ar_2)) [ 0 >= ar_2 ]", 0-2) = ? S("evalrealheapsortstep1bb3in(ar_0, ar_1, ar_2) -> Com_1(evalrealheapsortstep1bb4in(ar_0, ar_1, ar_2)) [ ar_2 >= 1 ]", 0-0) = ar_0 S("evalrealheapsortstep1bb3in(ar_0, ar_1, ar_2) -> Com_1(evalrealheapsortstep1bb4in(ar_0, ar_1, ar_2)) [ ar_2 >= 1 ]", 0-1) = ? S("evalrealheapsortstep1bb3in(ar_0, ar_1, ar_2) -> Com_1(evalrealheapsortstep1bb4in(ar_0, ar_1, ar_2)) [ ar_2 >= 1 ]", 0-2) = ? S("evalrealheapsortstep1bb5in(ar_0, ar_1, ar_2) -> Com_1(evalrealheapsortstep1bb6in(ar_0, ar_1 + 1, ar_2))", 0-0) = ar_0 S("evalrealheapsortstep1bb5in(ar_0, ar_1, ar_2) -> Com_1(evalrealheapsortstep1bb6in(ar_0, ar_1 + 1, ar_2))", 0-1) = ? S("evalrealheapsortstep1bb5in(ar_0, ar_1, ar_2) -> Com_1(evalrealheapsortstep1bb6in(ar_0, ar_1 + 1, ar_2))", 0-2) = ? S("evalrealheapsortstep1bb4in(ar_0, ar_1, ar_2) -> Com_1(evalrealheapsortstep1bb2in(ar_0, ar_1, ar_2)) [ ar_2 >= 0 /\\ d >= 0 /\\ ar_2 + 1 >= 2*d /\\ 2*d >= ar_2 ]", 0-0) = ar_0 S("evalrealheapsortstep1bb4in(ar_0, ar_1, ar_2) -> Com_1(evalrealheapsortstep1bb2in(ar_0, ar_1, ar_2)) [ ar_2 >= 0 /\\ d >= 0 /\\ ar_2 + 1 >= 2*d /\\ 2*d >= ar_2 ]", 0-1) = ? S("evalrealheapsortstep1bb4in(ar_0, ar_1, ar_2) -> Com_1(evalrealheapsortstep1bb2in(ar_0, ar_1, ar_2)) [ ar_2 >= 0 /\\ d >= 0 /\\ ar_2 + 1 >= 2*d /\\ 2*d >= ar_2 ]", 0-2) = ? S("evalrealheapsortstep1bb4in(ar_0, ar_1, ar_2) -> Com_1(evalrealheapsortstep1bb5in(ar_0, ar_1, ar_2)) [ ar_2 >= 0 /\\ d >= 0 /\\ ar_2 + 1 >= 2*d /\\ 2*d >= ar_2 ]", 0-0) = ar_0 S("evalrealheapsortstep1bb4in(ar_0, ar_1, ar_2) -> Com_1(evalrealheapsortstep1bb5in(ar_0, ar_1, ar_2)) [ ar_2 >= 0 /\\ d >= 0 /\\ ar_2 + 1 >= 2*d /\\ 2*d >= ar_2 ]", 0-1) = ? S("evalrealheapsortstep1bb4in(ar_0, ar_1, ar_2) -> Com_1(evalrealheapsortstep1bb5in(ar_0, ar_1, ar_2)) [ ar_2 >= 0 /\\ d >= 0 /\\ ar_2 + 1 >= 2*d /\\ 2*d >= ar_2 ]", 0-2) = ? S("evalrealheapsortstep1bb2in(ar_0, ar_1, ar_2) -> Com_1(evalrealheapsortstep1bb3in(ar_0, ar_1, d - 1)) [ ar_2 >= 0 /\\ e >= 0 /\\ ar_2 + 1 >= 2*e /\\ 2*e >= ar_2 /\\ f >= 0 /\\ ar_2 + 1 >= 2*f /\\ 2*f >= ar_2 /\\ d >= 0 /\\ ar_2 + 1 >= 2*d /\\ 2*d >= ar_2 ]", 0-0) = ar_0 S("evalrealheapsortstep1bb2in(ar_0, ar_1, ar_2) -> Com_1(evalrealheapsortstep1bb3in(ar_0, ar_1, d - 1)) [ ar_2 >= 0 /\\ e >= 0 /\\ ar_2 + 1 >= 2*e /\\ 2*e >= ar_2 /\\ f >= 0 /\\ ar_2 + 1 >= 2*f /\\ 2*f >= ar_2 /\\ d >= 0 /\\ ar_2 + 1 >= 2*d /\\ 2*d >= ar_2 ]", 0-1) = ? S("evalrealheapsortstep1bb2in(ar_0, ar_1, ar_2) -> Com_1(evalrealheapsortstep1bb3in(ar_0, ar_1, d - 1)) [ ar_2 >= 0 /\\ e >= 0 /\\ ar_2 + 1 >= 2*e /\\ 2*e >= ar_2 /\\ f >= 0 /\\ ar_2 + 1 >= 2*f /\\ 2*f >= ar_2 /\\ d >= 0 /\\ ar_2 + 1 >= 2*d /\\ 2*d >= ar_2 ]", 0-2) = ? S("evalrealheapsortstep1bb6in(ar_0, ar_1, ar_2) -> Com_1(evalrealheapsortstep1returnin(ar_0, ar_1, ar_2)) [ ar_1 >= ar_0 ]", 0-0) = ar_0 S("evalrealheapsortstep1bb6in(ar_0, ar_1, ar_2) -> Com_1(evalrealheapsortstep1returnin(ar_0, ar_1, ar_2)) [ ar_1 >= ar_0 ]", 0-1) = ? S("evalrealheapsortstep1bb6in(ar_0, ar_1, ar_2) -> Com_1(evalrealheapsortstep1returnin(ar_0, ar_1, ar_2)) [ ar_1 >= ar_0 ]", 0-2) = ? orients the transitions evalrealheapsortstep1bb5in(ar_0, ar_1, ar_2) -> Com_1(evalrealheapsortstep1bb6in(ar_0, ar_1 + 1, ar_2)) evalrealheapsortstep1bb4in(ar_0, ar_1, ar_2) -> Com_1(evalrealheapsortstep1bb5in(ar_0, ar_1, ar_2)) [ ar_2 >= 0 /\ d >= 0 /\ ar_2 + 1 >= 2*d /\ 2*d >= ar_2 ] evalrealheapsortstep1bb4in(ar_0, ar_1, ar_2) -> Com_1(evalrealheapsortstep1bb2in(ar_0, ar_1, ar_2)) [ ar_2 >= 0 /\ d >= 0 /\ ar_2 + 1 >= 2*d /\ 2*d >= ar_2 ] evalrealheapsortstep1bb3in(ar_0, ar_1, ar_2) -> Com_1(evalrealheapsortstep1bb5in(ar_0, ar_1, ar_2)) [ 0 >= ar_2 ] evalrealheapsortstep1bb3in(ar_0, ar_1, ar_2) -> Com_1(evalrealheapsortstep1bb4in(ar_0, ar_1, ar_2)) [ ar_2 >= 1 ] evalrealheapsortstep1bb2in(ar_0, ar_1, ar_2) -> Com_1(evalrealheapsortstep1bb3in(ar_0, ar_1, d - 1)) [ ar_2 >= 0 /\ e >= 0 /\ ar_2 + 1 >= 2*e /\ 2*e >= ar_2 /\ f >= 0 /\ ar_2 + 1 >= 2*f /\ 2*f >= ar_2 /\ d >= 0 /\ ar_2 + 1 >= 2*d /\ 2*d >= ar_2 ] weakly and the transitions evalrealheapsortstep1bb5in(ar_0, ar_1, ar_2) -> Com_1(evalrealheapsortstep1bb6in(ar_0, ar_1 + 1, ar_2)) evalrealheapsortstep1bb4in(ar_0, ar_1, ar_2) -> Com_1(evalrealheapsortstep1bb5in(ar_0, ar_1, ar_2)) [ ar_2 >= 0 /\ d >= 0 /\ ar_2 + 1 >= 2*d /\ 2*d >= ar_2 ] evalrealheapsortstep1bb3in(ar_0, ar_1, ar_2) -> Com_1(evalrealheapsortstep1bb5in(ar_0, ar_1, ar_2)) [ 0 >= ar_2 ] strictly and produces the following problem: 6: T: (Comp: 2, Cost: 1) evalrealheapsortstep1bb6in(ar_0, ar_1, ar_2) -> Com_1(evalrealheapsortstep1returnin(ar_0, ar_1, ar_2)) [ ar_1 >= ar_0 ] (Comp: ?, Cost: 1) evalrealheapsortstep1bb2in(ar_0, ar_1, ar_2) -> Com_1(evalrealheapsortstep1bb3in(ar_0, ar_1, d - 1)) [ ar_2 >= 0 /\ e >= 0 /\ ar_2 + 1 >= 2*e /\ 2*e >= ar_2 /\ f >= 0 /\ ar_2 + 1 >= 2*f /\ 2*f >= ar_2 /\ d >= 0 /\ ar_2 + 1 >= 2*d /\ 2*d >= ar_2 ] (Comp: 2*ar_0 + 4, Cost: 1) evalrealheapsortstep1bb4in(ar_0, ar_1, ar_2) -> Com_1(evalrealheapsortstep1bb5in(ar_0, ar_1, ar_2)) [ ar_2 >= 0 /\ d >= 0 /\ ar_2 + 1 >= 2*d /\ 2*d >= ar_2 ] (Comp: ?, Cost: 1) evalrealheapsortstep1bb4in(ar_0, ar_1, ar_2) -> Com_1(evalrealheapsortstep1bb2in(ar_0, ar_1, ar_2)) [ ar_2 >= 0 /\ d >= 0 /\ ar_2 + 1 >= 2*d /\ 2*d >= ar_2 ] (Comp: 2*ar_0 + 4, Cost: 1) evalrealheapsortstep1bb5in(ar_0, ar_1, ar_2) -> Com_1(evalrealheapsortstep1bb6in(ar_0, ar_1 + 1, ar_2)) (Comp: ?, Cost: 1) evalrealheapsortstep1bb3in(ar_0, ar_1, ar_2) -> Com_1(evalrealheapsortstep1bb4in(ar_0, ar_1, ar_2)) [ ar_2 >= 1 ] (Comp: 2*ar_0 + 4, Cost: 1) evalrealheapsortstep1bb3in(ar_0, ar_1, ar_2) -> Com_1(evalrealheapsortstep1bb5in(ar_0, ar_1, ar_2)) [ 0 >= ar_2 ] (Comp: 2, Cost: 1) evalrealheapsortstep1returnin(ar_0, ar_1, ar_2) -> Com_1(evalrealheapsortstep1stop(ar_0, ar_1, ar_2)) (Comp: ar_0 + 2, Cost: 1) evalrealheapsortstep1bb6in(ar_0, ar_1, ar_2) -> Com_1(evalrealheapsortstep1bb3in(ar_0, ar_1, ar_1)) [ ar_0 >= ar_1 + 1 ] (Comp: 1, Cost: 1) evalrealheapsortstep1entryin(ar_0, ar_1, ar_2) -> Com_1(evalrealheapsortstep1returnin(ar_0, ar_1, ar_2)) [ 2 >= ar_0 ] (Comp: 1, Cost: 1) evalrealheapsortstep1entryin(ar_0, ar_1, ar_2) -> Com_1(evalrealheapsortstep1bb6in(ar_0, 1, ar_2)) [ ar_0 >= 3 ] (Comp: 1, Cost: 1) evalrealheapsortstep1start(ar_0, ar_1, ar_2) -> Com_1(evalrealheapsortstep1entryin(ar_0, ar_1, ar_2)) (Comp: 1, Cost: 0) koat_start(ar_0, ar_1, ar_2) -> Com_1(evalrealheapsortstep1start(ar_0, ar_1, ar_2)) [ 0 <= 0 ] start location: koat_start leaf cost: 0 A polynomial rank function with Pol(evalrealheapsortstep1bb4in) = 3*V_3 + 3 Pol(evalrealheapsortstep1bb2in) = 3*V_3 + 1 Pol(evalrealheapsortstep1bb3in) = 6*V_3 + 2 and size complexities S("koat_start(ar_0, ar_1, ar_2) -> Com_1(evalrealheapsortstep1start(ar_0, ar_1, ar_2)) [ 0 <= 0 ]", 0-0) = ar_0 S("koat_start(ar_0, ar_1, ar_2) -> Com_1(evalrealheapsortstep1start(ar_0, ar_1, ar_2)) [ 0 <= 0 ]", 0-1) = ar_1 S("koat_start(ar_0, ar_1, ar_2) -> Com_1(evalrealheapsortstep1start(ar_0, ar_1, ar_2)) [ 0 <= 0 ]", 0-2) = ar_2 S("evalrealheapsortstep1start(ar_0, ar_1, ar_2) -> Com_1(evalrealheapsortstep1entryin(ar_0, ar_1, ar_2))", 0-0) = ar_0 S("evalrealheapsortstep1start(ar_0, ar_1, ar_2) -> Com_1(evalrealheapsortstep1entryin(ar_0, ar_1, ar_2))", 0-1) = ar_1 S("evalrealheapsortstep1start(ar_0, ar_1, ar_2) -> Com_1(evalrealheapsortstep1entryin(ar_0, ar_1, ar_2))", 0-2) = ar_2 S("evalrealheapsortstep1entryin(ar_0, ar_1, ar_2) -> Com_1(evalrealheapsortstep1bb6in(ar_0, 1, ar_2)) [ ar_0 >= 3 ]", 0-0) = ar_0 S("evalrealheapsortstep1entryin(ar_0, ar_1, ar_2) -> Com_1(evalrealheapsortstep1bb6in(ar_0, 1, ar_2)) [ ar_0 >= 3 ]", 0-1) = 1 S("evalrealheapsortstep1entryin(ar_0, ar_1, ar_2) -> Com_1(evalrealheapsortstep1bb6in(ar_0, 1, ar_2)) [ ar_0 >= 3 ]", 0-2) = ar_2 S("evalrealheapsortstep1entryin(ar_0, ar_1, ar_2) -> Com_1(evalrealheapsortstep1returnin(ar_0, ar_1, ar_2)) [ 2 >= ar_0 ]", 0-0) = ar_0 S("evalrealheapsortstep1entryin(ar_0, ar_1, ar_2) -> Com_1(evalrealheapsortstep1returnin(ar_0, ar_1, ar_2)) [ 2 >= ar_0 ]", 0-1) = ar_1 S("evalrealheapsortstep1entryin(ar_0, ar_1, ar_2) -> Com_1(evalrealheapsortstep1returnin(ar_0, ar_1, ar_2)) [ 2 >= ar_0 ]", 0-2) = ar_2 S("evalrealheapsortstep1bb6in(ar_0, ar_1, ar_2) -> Com_1(evalrealheapsortstep1bb3in(ar_0, ar_1, ar_1)) [ ar_0 >= ar_1 + 1 ]", 0-0) = ar_0 S("evalrealheapsortstep1bb6in(ar_0, ar_1, ar_2) -> Com_1(evalrealheapsortstep1bb3in(ar_0, ar_1, ar_1)) [ ar_0 >= ar_1 + 1 ]", 0-1) = 2*ar_0 + 20 S("evalrealheapsortstep1bb6in(ar_0, ar_1, ar_2) -> Com_1(evalrealheapsortstep1bb3in(ar_0, ar_1, ar_1)) [ ar_0 >= ar_1 + 1 ]", 0-2) = 2*ar_0 + 42 S("evalrealheapsortstep1returnin(ar_0, ar_1, ar_2) -> Com_1(evalrealheapsortstep1stop(ar_0, ar_1, ar_2))", 0-0) = ar_0 S("evalrealheapsortstep1returnin(ar_0, ar_1, ar_2) -> Com_1(evalrealheapsortstep1stop(ar_0, ar_1, ar_2))", 0-1) = 2*ar_0 + 2*ar_1 + 80 S("evalrealheapsortstep1returnin(ar_0, ar_1, ar_2) -> Com_1(evalrealheapsortstep1stop(ar_0, ar_1, ar_2))", 0-2) = 2*ar_0 + 2*ar_2 + 1408 S("evalrealheapsortstep1bb3in(ar_0, ar_1, ar_2) -> Com_1(evalrealheapsortstep1bb5in(ar_0, ar_1, ar_2)) [ 0 >= ar_2 ]", 0-0) = ar_0 S("evalrealheapsortstep1bb3in(ar_0, ar_1, ar_2) -> Com_1(evalrealheapsortstep1bb5in(ar_0, ar_1, ar_2)) [ 0 >= ar_2 ]", 0-1) = 2*ar_0 + 20 S("evalrealheapsortstep1bb3in(ar_0, ar_1, ar_2) -> Com_1(evalrealheapsortstep1bb5in(ar_0, ar_1, ar_2)) [ 0 >= ar_2 ]", 0-2) = 2*ar_0 + 176 S("evalrealheapsortstep1bb3in(ar_0, ar_1, ar_2) -> Com_1(evalrealheapsortstep1bb4in(ar_0, ar_1, ar_2)) [ ar_2 >= 1 ]", 0-0) = ar_0 S("evalrealheapsortstep1bb3in(ar_0, ar_1, ar_2) -> Com_1(evalrealheapsortstep1bb4in(ar_0, ar_1, ar_2)) [ ar_2 >= 1 ]", 0-1) = 2*ar_0 + 20 S("evalrealheapsortstep1bb3in(ar_0, ar_1, ar_2) -> Com_1(evalrealheapsortstep1bb4in(ar_0, ar_1, ar_2)) [ ar_2 >= 1 ]", 0-2) = 2*ar_0 + 88 S("evalrealheapsortstep1bb5in(ar_0, ar_1, ar_2) -> Com_1(evalrealheapsortstep1bb6in(ar_0, ar_1 + 1, ar_2))", 0-0) = ar_0 S("evalrealheapsortstep1bb5in(ar_0, ar_1, ar_2) -> Com_1(evalrealheapsortstep1bb6in(ar_0, ar_1 + 1, ar_2))", 0-1) = 2*ar_0 + 20 S("evalrealheapsortstep1bb5in(ar_0, ar_1, ar_2) -> Com_1(evalrealheapsortstep1bb6in(ar_0, ar_1 + 1, ar_2))", 0-2) = 2*ar_0 + 352 S("evalrealheapsortstep1bb4in(ar_0, ar_1, ar_2) -> Com_1(evalrealheapsortstep1bb2in(ar_0, ar_1, ar_2)) [ ar_2 >= 0 /\\ d >= 0 /\\ ar_2 + 1 >= 2*d /\\ 2*d >= ar_2 ]", 0-0) = ar_0 S("evalrealheapsortstep1bb4in(ar_0, ar_1, ar_2) -> Com_1(evalrealheapsortstep1bb2in(ar_0, ar_1, ar_2)) [ ar_2 >= 0 /\\ d >= 0 /\\ ar_2 + 1 >= 2*d /\\ 2*d >= ar_2 ]", 0-1) = 2*ar_0 + 20 S("evalrealheapsortstep1bb4in(ar_0, ar_1, ar_2) -> Com_1(evalrealheapsortstep1bb2in(ar_0, ar_1, ar_2)) [ ar_2 >= 0 /\\ d >= 0 /\\ ar_2 + 1 >= 2*d /\\ 2*d >= ar_2 ]", 0-2) = 2*ar_0 + 88 S("evalrealheapsortstep1bb4in(ar_0, ar_1, ar_2) -> Com_1(evalrealheapsortstep1bb5in(ar_0, ar_1, ar_2)) [ ar_2 >= 0 /\\ d >= 0 /\\ ar_2 + 1 >= 2*d /\\ 2*d >= ar_2 ]", 0-0) = ar_0 S("evalrealheapsortstep1bb4in(ar_0, ar_1, ar_2) -> Com_1(evalrealheapsortstep1bb5in(ar_0, ar_1, ar_2)) [ ar_2 >= 0 /\\ d >= 0 /\\ ar_2 + 1 >= 2*d /\\ 2*d >= ar_2 ]", 0-1) = 2*ar_0 + 20 S("evalrealheapsortstep1bb4in(ar_0, ar_1, ar_2) -> Com_1(evalrealheapsortstep1bb5in(ar_0, ar_1, ar_2)) [ ar_2 >= 0 /\\ d >= 0 /\\ ar_2 + 1 >= 2*d /\\ 2*d >= ar_2 ]", 0-2) = 2*ar_0 + 176 S("evalrealheapsortstep1bb2in(ar_0, ar_1, ar_2) -> Com_1(evalrealheapsortstep1bb3in(ar_0, ar_1, d - 1)) [ ar_2 >= 0 /\\ e >= 0 /\\ ar_2 + 1 >= 2*e /\\ 2*e >= ar_2 /\\ f >= 0 /\\ ar_2 + 1 >= 2*f /\\ 2*f >= ar_2 /\\ d >= 0 /\\ ar_2 + 1 >= 2*d /\\ 2*d >= ar_2 ]", 0-0) = ar_0 S("evalrealheapsortstep1bb2in(ar_0, ar_1, ar_2) -> Com_1(evalrealheapsortstep1bb3in(ar_0, ar_1, d - 1)) [ ar_2 >= 0 /\\ e >= 0 /\\ ar_2 + 1 >= 2*e /\\ 2*e >= ar_2 /\\ f >= 0 /\\ ar_2 + 1 >= 2*f /\\ 2*f >= ar_2 /\\ d >= 0 /\\ ar_2 + 1 >= 2*d /\\ 2*d >= ar_2 ]", 0-1) = 2*ar_0 + 20 S("evalrealheapsortstep1bb2in(ar_0, ar_1, ar_2) -> Com_1(evalrealheapsortstep1bb3in(ar_0, ar_1, d - 1)) [ ar_2 >= 0 /\\ e >= 0 /\\ ar_2 + 1 >= 2*e /\\ 2*e >= ar_2 /\\ f >= 0 /\\ ar_2 + 1 >= 2*f /\\ 2*f >= ar_2 /\\ d >= 0 /\\ ar_2 + 1 >= 2*d /\\ 2*d >= ar_2 ]", 0-2) = 2*ar_0 + 88 S("evalrealheapsortstep1bb6in(ar_0, ar_1, ar_2) -> Com_1(evalrealheapsortstep1returnin(ar_0, ar_1, ar_2)) [ ar_1 >= ar_0 ]", 0-0) = ar_0 S("evalrealheapsortstep1bb6in(ar_0, ar_1, ar_2) -> Com_1(evalrealheapsortstep1returnin(ar_0, ar_1, ar_2)) [ ar_1 >= ar_0 ]", 0-1) = 2*ar_0 + 40 S("evalrealheapsortstep1bb6in(ar_0, ar_1, ar_2) -> Com_1(evalrealheapsortstep1returnin(ar_0, ar_1, ar_2)) [ ar_1 >= ar_0 ]", 0-2) = 2*ar_0 + 704 orients the transitions evalrealheapsortstep1bb4in(ar_0, ar_1, ar_2) -> Com_1(evalrealheapsortstep1bb2in(ar_0, ar_1, ar_2)) [ ar_2 >= 0 /\ d >= 0 /\ ar_2 + 1 >= 2*d /\ 2*d >= ar_2 ] evalrealheapsortstep1bb3in(ar_0, ar_1, ar_2) -> Com_1(evalrealheapsortstep1bb4in(ar_0, ar_1, ar_2)) [ ar_2 >= 1 ] evalrealheapsortstep1bb2in(ar_0, ar_1, ar_2) -> Com_1(evalrealheapsortstep1bb3in(ar_0, ar_1, d - 1)) [ ar_2 >= 0 /\ e >= 0 /\ ar_2 + 1 >= 2*e /\ 2*e >= ar_2 /\ f >= 0 /\ ar_2 + 1 >= 2*f /\ 2*f >= ar_2 /\ d >= 0 /\ ar_2 + 1 >= 2*d /\ 2*d >= ar_2 ] weakly and the transitions evalrealheapsortstep1bb4in(ar_0, ar_1, ar_2) -> Com_1(evalrealheapsortstep1bb2in(ar_0, ar_1, ar_2)) [ ar_2 >= 0 /\ d >= 0 /\ ar_2 + 1 >= 2*d /\ 2*d >= ar_2 ] evalrealheapsortstep1bb3in(ar_0, ar_1, ar_2) -> Com_1(evalrealheapsortstep1bb4in(ar_0, ar_1, ar_2)) [ ar_2 >= 1 ] evalrealheapsortstep1bb2in(ar_0, ar_1, ar_2) -> Com_1(evalrealheapsortstep1bb3in(ar_0, ar_1, d - 1)) [ ar_2 >= 0 /\ e >= 0 /\ ar_2 + 1 >= 2*e /\ 2*e >= ar_2 /\ f >= 0 /\ ar_2 + 1 >= 2*f /\ 2*f >= ar_2 /\ d >= 0 /\ ar_2 + 1 >= 2*d /\ 2*d >= ar_2 ] strictly and produces the following problem: 7: T: (Comp: 2, Cost: 1) evalrealheapsortstep1bb6in(ar_0, ar_1, ar_2) -> Com_1(evalrealheapsortstep1returnin(ar_0, ar_1, ar_2)) [ ar_1 >= ar_0 ] (Comp: 12*ar_0^2 + 278*ar_0 + 508, Cost: 1) evalrealheapsortstep1bb2in(ar_0, ar_1, ar_2) -> Com_1(evalrealheapsortstep1bb3in(ar_0, ar_1, d - 1)) [ ar_2 >= 0 /\ e >= 0 /\ ar_2 + 1 >= 2*e /\ 2*e >= ar_2 /\ f >= 0 /\ ar_2 + 1 >= 2*f /\ 2*f >= ar_2 /\ d >= 0 /\ ar_2 + 1 >= 2*d /\ 2*d >= ar_2 ] (Comp: 2*ar_0 + 4, Cost: 1) evalrealheapsortstep1bb4in(ar_0, ar_1, ar_2) -> Com_1(evalrealheapsortstep1bb5in(ar_0, ar_1, ar_2)) [ ar_2 >= 0 /\ d >= 0 /\ ar_2 + 1 >= 2*d /\ 2*d >= ar_2 ] (Comp: 12*ar_0^2 + 278*ar_0 + 508, Cost: 1) evalrealheapsortstep1bb4in(ar_0, ar_1, ar_2) -> Com_1(evalrealheapsortstep1bb2in(ar_0, ar_1, ar_2)) [ ar_2 >= 0 /\ d >= 0 /\ ar_2 + 1 >= 2*d /\ 2*d >= ar_2 ] (Comp: 2*ar_0 + 4, Cost: 1) evalrealheapsortstep1bb5in(ar_0, ar_1, ar_2) -> Com_1(evalrealheapsortstep1bb6in(ar_0, ar_1 + 1, ar_2)) (Comp: 12*ar_0^2 + 278*ar_0 + 508, Cost: 1) evalrealheapsortstep1bb3in(ar_0, ar_1, ar_2) -> Com_1(evalrealheapsortstep1bb4in(ar_0, ar_1, ar_2)) [ ar_2 >= 1 ] (Comp: 2*ar_0 + 4, Cost: 1) evalrealheapsortstep1bb3in(ar_0, ar_1, ar_2) -> Com_1(evalrealheapsortstep1bb5in(ar_0, ar_1, ar_2)) [ 0 >= ar_2 ] (Comp: 2, Cost: 1) evalrealheapsortstep1returnin(ar_0, ar_1, ar_2) -> Com_1(evalrealheapsortstep1stop(ar_0, ar_1, ar_2)) (Comp: ar_0 + 2, Cost: 1) evalrealheapsortstep1bb6in(ar_0, ar_1, ar_2) -> Com_1(evalrealheapsortstep1bb3in(ar_0, ar_1, ar_1)) [ ar_0 >= ar_1 + 1 ] (Comp: 1, Cost: 1) evalrealheapsortstep1entryin(ar_0, ar_1, ar_2) -> Com_1(evalrealheapsortstep1returnin(ar_0, ar_1, ar_2)) [ 2 >= ar_0 ] (Comp: 1, Cost: 1) evalrealheapsortstep1entryin(ar_0, ar_1, ar_2) -> Com_1(evalrealheapsortstep1bb6in(ar_0, 1, ar_2)) [ ar_0 >= 3 ] (Comp: 1, Cost: 1) evalrealheapsortstep1start(ar_0, ar_1, ar_2) -> Com_1(evalrealheapsortstep1entryin(ar_0, ar_1, ar_2)) (Comp: 1, Cost: 0) koat_start(ar_0, ar_1, ar_2) -> Com_1(evalrealheapsortstep1start(ar_0, ar_1, ar_2)) [ 0 <= 0 ] start location: koat_start leaf cost: 0 Complexity upper bound 36*ar_0^2 + 841*ar_0 + 1545 Time: 0.273 sec (SMT: 0.221 sec) ---------------------------------------- (2) BOUNDS(1, n^2) ---------------------------------------- (3) Koat2 Proof (FINISHED) YES( ?, 5+max([0, Arg_0])+max([0, Arg_0*Arg_0])+max([0, Arg_0*Arg_0])+max([0, max([Arg_0*max([5, 1-max([-4*max([1, max([1, 1+-(Arg_0)*-(Arg_0)])]), -4*max([1, max([1, 1+Arg_0*Arg_0])])])]), Arg_0*max([5, 1+max([4*max([1, max([1, 1+-(Arg_0)*-(Arg_0)])]), 4*max([1, max([1, 1+Arg_0*Arg_0])])])])])])+max([0, Arg_0*Arg_0])+max([0, max([Arg_0*max([6, min([-(-6*max([1, max([1, 1+-(Arg_0)*-(Arg_0)])])), -(-6*max([1, max([1, 1+Arg_0*Arg_0])]))])]), Arg_0*max([6, max([6*max([1, max([1, 1+-(Arg_0)*-(Arg_0)])]), 6*max([1, max([1, 1+Arg_0*Arg_0])])])])])])+max([0, max([Arg_0*max([6, min([-(-6*max([1, max([1, 1+-(Arg_0)*-(Arg_0)])])), -(-6*max([1, max([1, 1+Arg_0*Arg_0])]))])]), Arg_0*max([6, max([6*max([1, max([1, 1+-(Arg_0)*-(Arg_0)])]), 6*max([1, max([1, 1+Arg_0*Arg_0])])])])])]) {O(n^3)}) Initial Complexity Problem: Start: evalrealheapsortstep1start Program_Vars: Arg_0, Arg_1, Arg_2 Temp_Vars: D, E, F Locations: evalrealheapsortstep1bb2in, evalrealheapsortstep1bb3in, evalrealheapsortstep1bb4in, evalrealheapsortstep1bb5in, evalrealheapsortstep1bb6in, evalrealheapsortstep1entryin, evalrealheapsortstep1returnin, evalrealheapsortstep1start, evalrealheapsortstep1stop Transitions: evalrealheapsortstep1bb2in(Arg_0,Arg_1,Arg_2) -> evalrealheapsortstep1bb3in(Arg_0,Arg_1,D-1):|:Arg_2 <= Arg_1 && 1 <= Arg_2 && 2 <= Arg_1+Arg_2 && 4 <= Arg_0+Arg_2 && 1 <= Arg_1 && 4 <= Arg_0+Arg_1 && 3 <= Arg_0 && 0 <= Arg_2 && 0 <= E && (2)*E <= Arg_2+1 && Arg_2 <= (2)*E && 0 <= F && (2)*F <= Arg_2+1 && Arg_2 <= (2)*F && 0 <= D && (2)*D <= Arg_2+1 && Arg_2 <= (2)*D evalrealheapsortstep1bb3in(Arg_0,Arg_1,Arg_2) -> evalrealheapsortstep1bb4in(Arg_0,Arg_1,Arg_2):|:Arg_2 <= Arg_1 && 1 <= Arg_1 && 4 <= Arg_0+Arg_1 && 3 <= Arg_0 && 1 <= Arg_2 evalrealheapsortstep1bb3in(Arg_0,Arg_1,Arg_2) -> evalrealheapsortstep1bb5in(Arg_0,Arg_1,Arg_2):|:Arg_2 <= Arg_1 && 1 <= Arg_1 && 4 <= Arg_0+Arg_1 && 3 <= Arg_0 && Arg_2 <= 0 evalrealheapsortstep1bb4in(Arg_0,Arg_1,Arg_2) -> evalrealheapsortstep1bb2in(Arg_0,Arg_1,Arg_2):|:Arg_2 <= Arg_1 && 1 <= Arg_2 && 2 <= Arg_1+Arg_2 && 4 <= Arg_0+Arg_2 && 1 <= Arg_1 && 4 <= Arg_0+Arg_1 && 3 <= Arg_0 && 0 <= Arg_2 && 0 <= D && (2)*D <= Arg_2+1 && Arg_2 <= (2)*D evalrealheapsortstep1bb4in(Arg_0,Arg_1,Arg_2) -> evalrealheapsortstep1bb5in(Arg_0,Arg_1,Arg_2):|:Arg_2 <= Arg_1 && 1 <= Arg_2 && 2 <= Arg_1+Arg_2 && 4 <= Arg_0+Arg_2 && 1 <= Arg_1 && 4 <= Arg_0+Arg_1 && 3 <= Arg_0 && 0 <= Arg_2 && 0 <= D && (2)*D <= Arg_2+1 && Arg_2 <= (2)*D evalrealheapsortstep1bb5in(Arg_0,Arg_1,Arg_2) -> evalrealheapsortstep1bb6in(Arg_0,Arg_1+1,Arg_2):|:Arg_2 <= Arg_1 && 1 <= Arg_1 && 4 <= Arg_0+Arg_1 && 3 <= Arg_0 evalrealheapsortstep1bb6in(Arg_0,Arg_1,Arg_2) -> evalrealheapsortstep1bb3in(Arg_0,Arg_1,Arg_1):|:1 <= Arg_1 && 4 <= Arg_0+Arg_1 && 3 <= Arg_0 && 1+Arg_1 <= Arg_0 evalrealheapsortstep1bb6in(Arg_0,Arg_1,Arg_2) -> evalrealheapsortstep1returnin(Arg_0,Arg_1,Arg_2):|:1 <= Arg_1 && 4 <= Arg_0+Arg_1 && 3 <= Arg_0 && Arg_0 <= Arg_1 evalrealheapsortstep1entryin(Arg_0,Arg_1,Arg_2) -> evalrealheapsortstep1bb6in(Arg_0,1,Arg_2):|:3 <= Arg_0 evalrealheapsortstep1entryin(Arg_0,Arg_1,Arg_2) -> evalrealheapsortstep1returnin(Arg_0,Arg_1,Arg_2):|:Arg_0 <= 2 evalrealheapsortstep1returnin(Arg_0,Arg_1,Arg_2) -> evalrealheapsortstep1stop(Arg_0,Arg_1,Arg_2):|: evalrealheapsortstep1start(Arg_0,Arg_1,Arg_2) -> evalrealheapsortstep1entryin(Arg_0,Arg_1,Arg_2):|: Timebounds: Overall timebound: 5+max([0, Arg_0])+max([0, Arg_0*Arg_0])+max([0, Arg_0*Arg_0])+max([0, max([Arg_0*max([5, 1-max([-4*max([1, max([1, 1+-(Arg_0)*-(Arg_0)])]), -4*max([1, max([1, 1+Arg_0*Arg_0])])])]), Arg_0*max([5, 1+max([4*max([1, max([1, 1+-(Arg_0)*-(Arg_0)])]), 4*max([1, max([1, 1+Arg_0*Arg_0])])])])])])+max([0, Arg_0*Arg_0])+max([0, max([Arg_0*max([6, min([-(-6*max([1, max([1, 1+-(Arg_0)*-(Arg_0)])])), -(-6*max([1, max([1, 1+Arg_0*Arg_0])]))])]), Arg_0*max([6, max([6*max([1, max([1, 1+-(Arg_0)*-(Arg_0)])]), 6*max([1, max([1, 1+Arg_0*Arg_0])])])])])])+max([0, max([Arg_0*max([6, min([-(-6*max([1, max([1, 1+-(Arg_0)*-(Arg_0)])])), -(-6*max([1, max([1, 1+Arg_0*Arg_0])]))])]), Arg_0*max([6, max([6*max([1, max([1, 1+-(Arg_0)*-(Arg_0)])]), 6*max([1, max([1, 1+Arg_0*Arg_0])])])])])]) {O(n^3)} 23: evalrealheapsortstep1bb2in->evalrealheapsortstep1bb3in: max([0, max([Arg_0*max([6, min([-(-6*max([1, max([1, 1+-(Arg_0)*-(Arg_0)])])), -(-6*max([1, max([1, 1+Arg_0*Arg_0])]))])]), Arg_0*max([6, max([6*max([1, max([1, 1+-(Arg_0)*-(Arg_0)])]), 6*max([1, max([1, 1+Arg_0*Arg_0])])])])])]) {O(n^3)} 5: evalrealheapsortstep1bb3in->evalrealheapsortstep1bb5in: max([0, Arg_0*Arg_0]) {O(n^2)} 6: evalrealheapsortstep1bb3in->evalrealheapsortstep1bb4in: max([0, max([Arg_0*max([5, 1-max([-4*max([1, max([1, 1+-(Arg_0)*-(Arg_0)])]), -4*max([1, max([1, 1+Arg_0*Arg_0])])])]), Arg_0*max([5, 1+max([4*max([1, max([1, 1+-(Arg_0)*-(Arg_0)])]), 4*max([1, max([1, 1+Arg_0*Arg_0])])])])])]) {O(n^3)} 8: evalrealheapsortstep1bb4in->evalrealheapsortstep1bb2in: max([0, max([Arg_0*max([6, min([-(-6*max([1, max([1, 1+-(Arg_0)*-(Arg_0)])])), -(-6*max([1, max([1, 1+Arg_0*Arg_0])]))])]), Arg_0*max([6, max([6*max([1, max([1, 1+-(Arg_0)*-(Arg_0)])]), 6*max([1, max([1, 1+Arg_0*Arg_0])])])])])]) {O(n^3)} 11: evalrealheapsortstep1bb4in->evalrealheapsortstep1bb5in: max([0, Arg_0*Arg_0]) {O(n^2)} 34: evalrealheapsortstep1bb5in->evalrealheapsortstep1bb6in: max([0, Arg_0*Arg_0]) {O(n^2)} 3: evalrealheapsortstep1bb6in->evalrealheapsortstep1bb3in: max([0, Arg_0]) {O(n)} 4: evalrealheapsortstep1bb6in->evalrealheapsortstep1returnin: 1 {O(1)} 1: evalrealheapsortstep1entryin->evalrealheapsortstep1bb6in: 1 {O(1)} 2: evalrealheapsortstep1entryin->evalrealheapsortstep1returnin: 1 {O(1)} 35: evalrealheapsortstep1returnin->evalrealheapsortstep1stop: 1 {O(1)} 0: evalrealheapsortstep1start->evalrealheapsortstep1entryin: 1 {O(1)} Costbounds: Overall costbound: 5+max([0, Arg_0])+max([0, Arg_0*Arg_0])+max([0, Arg_0*Arg_0])+max([0, max([Arg_0*max([5, 1-max([-4*max([1, max([1, 1+-(Arg_0)*-(Arg_0)])]), -4*max([1, max([1, 1+Arg_0*Arg_0])])])]), Arg_0*max([5, 1+max([4*max([1, max([1, 1+-(Arg_0)*-(Arg_0)])]), 4*max([1, max([1, 1+Arg_0*Arg_0])])])])])])+max([0, Arg_0*Arg_0])+max([0, max([Arg_0*max([6, min([-(-6*max([1, max([1, 1+-(Arg_0)*-(Arg_0)])])), -(-6*max([1, max([1, 1+Arg_0*Arg_0])]))])]), Arg_0*max([6, max([6*max([1, max([1, 1+-(Arg_0)*-(Arg_0)])]), 6*max([1, max([1, 1+Arg_0*Arg_0])])])])])])+max([0, max([Arg_0*max([6, min([-(-6*max([1, max([1, 1+-(Arg_0)*-(Arg_0)])])), -(-6*max([1, max([1, 1+Arg_0*Arg_0])]))])]), Arg_0*max([6, max([6*max([1, max([1, 1+-(Arg_0)*-(Arg_0)])]), 6*max([1, max([1, 1+Arg_0*Arg_0])])])])])]) {O(n^3)} 23: evalrealheapsortstep1bb2in->evalrealheapsortstep1bb3in: max([0, max([Arg_0*max([6, min([-(-6*max([1, max([1, 1+-(Arg_0)*-(Arg_0)])])), -(-6*max([1, max([1, 1+Arg_0*Arg_0])]))])]), Arg_0*max([6, max([6*max([1, max([1, 1+-(Arg_0)*-(Arg_0)])]), 6*max([1, max([1, 1+Arg_0*Arg_0])])])])])]) {O(n^3)} 5: evalrealheapsortstep1bb3in->evalrealheapsortstep1bb5in: max([0, Arg_0*Arg_0]) {O(n^2)} 6: evalrealheapsortstep1bb3in->evalrealheapsortstep1bb4in: max([0, max([Arg_0*max([5, 1-max([-4*max([1, max([1, 1+-(Arg_0)*-(Arg_0)])]), -4*max([1, max([1, 1+Arg_0*Arg_0])])])]), Arg_0*max([5, 1+max([4*max([1, max([1, 1+-(Arg_0)*-(Arg_0)])]), 4*max([1, max([1, 1+Arg_0*Arg_0])])])])])]) {O(n^3)} 8: evalrealheapsortstep1bb4in->evalrealheapsortstep1bb2in: max([0, max([Arg_0*max([6, min([-(-6*max([1, max([1, 1+-(Arg_0)*-(Arg_0)])])), -(-6*max([1, max([1, 1+Arg_0*Arg_0])]))])]), Arg_0*max([6, max([6*max([1, max([1, 1+-(Arg_0)*-(Arg_0)])]), 6*max([1, max([1, 1+Arg_0*Arg_0])])])])])]) {O(n^3)} 11: evalrealheapsortstep1bb4in->evalrealheapsortstep1bb5in: max([0, Arg_0*Arg_0]) {O(n^2)} 34: evalrealheapsortstep1bb5in->evalrealheapsortstep1bb6in: max([0, Arg_0*Arg_0]) {O(n^2)} 3: evalrealheapsortstep1bb6in->evalrealheapsortstep1bb3in: max([0, Arg_0]) {O(n)} 4: evalrealheapsortstep1bb6in->evalrealheapsortstep1returnin: 1 {O(1)} 1: evalrealheapsortstep1entryin->evalrealheapsortstep1bb6in: 1 {O(1)} 2: evalrealheapsortstep1entryin->evalrealheapsortstep1returnin: 1 {O(1)} 35: evalrealheapsortstep1returnin->evalrealheapsortstep1stop: 1 {O(1)} 0: evalrealheapsortstep1start->evalrealheapsortstep1entryin: 1 {O(1)} Sizebounds: `Lower: 23: evalrealheapsortstep1bb2in->evalrealheapsortstep1bb3in, Arg_0: 3 {O(1)} 23: evalrealheapsortstep1bb2in->evalrealheapsortstep1bb3in, Arg_1: 1 {O(1)} 23: evalrealheapsortstep1bb2in->evalrealheapsortstep1bb3in, Arg_2: 0 {O(1)} 5: evalrealheapsortstep1bb3in->evalrealheapsortstep1bb5in, Arg_0: 3 {O(1)} 5: evalrealheapsortstep1bb3in->evalrealheapsortstep1bb5in, Arg_1: 1 {O(1)} 5: evalrealheapsortstep1bb3in->evalrealheapsortstep1bb5in, Arg_2: 0 {O(1)} 6: evalrealheapsortstep1bb3in->evalrealheapsortstep1bb4in, Arg_0: 3 {O(1)} 6: evalrealheapsortstep1bb3in->evalrealheapsortstep1bb4in, Arg_1: 1 {O(1)} 6: evalrealheapsortstep1bb3in->evalrealheapsortstep1bb4in, Arg_2: 1 {O(1)} 8: evalrealheapsortstep1bb4in->evalrealheapsortstep1bb2in, Arg_0: 3 {O(1)} 8: evalrealheapsortstep1bb4in->evalrealheapsortstep1bb2in, Arg_1: 1 {O(1)} 8: evalrealheapsortstep1bb4in->evalrealheapsortstep1bb2in, Arg_2: 1 {O(1)} 11: evalrealheapsortstep1bb4in->evalrealheapsortstep1bb5in, Arg_0: 3 {O(1)} 11: evalrealheapsortstep1bb4in->evalrealheapsortstep1bb5in, Arg_1: 1 {O(1)} 11: evalrealheapsortstep1bb4in->evalrealheapsortstep1bb5in, Arg_2: 1 {O(1)} 34: evalrealheapsortstep1bb5in->evalrealheapsortstep1bb6in, Arg_0: 3 {O(1)} 34: evalrealheapsortstep1bb5in->evalrealheapsortstep1bb6in, Arg_1: 2 {O(1)} 34: evalrealheapsortstep1bb5in->evalrealheapsortstep1bb6in, Arg_2: 0 {O(1)} 3: evalrealheapsortstep1bb6in->evalrealheapsortstep1bb3in, Arg_0: 3 {O(1)} 3: evalrealheapsortstep1bb6in->evalrealheapsortstep1bb3in, Arg_1: 1 {O(1)} 3: evalrealheapsortstep1bb6in->evalrealheapsortstep1bb3in, Arg_2: 1 {O(1)} 4: evalrealheapsortstep1bb6in->evalrealheapsortstep1returnin, Arg_0: 3 {O(1)} 4: evalrealheapsortstep1bb6in->evalrealheapsortstep1returnin, Arg_1: 3 {O(1)} 4: evalrealheapsortstep1bb6in->evalrealheapsortstep1returnin, Arg_2: 0 {O(1)} 1: evalrealheapsortstep1entryin->evalrealheapsortstep1bb6in, Arg_0: 3 {O(1)} 1: evalrealheapsortstep1entryin->evalrealheapsortstep1bb6in, Arg_1: 1 {O(1)} 1: evalrealheapsortstep1entryin->evalrealheapsortstep1bb6in, Arg_2: Arg_2 {O(n)} 2: evalrealheapsortstep1entryin->evalrealheapsortstep1returnin, Arg_0: Arg_0 {O(n)} 2: evalrealheapsortstep1entryin->evalrealheapsortstep1returnin, Arg_1: Arg_1 {O(n)} 2: evalrealheapsortstep1entryin->evalrealheapsortstep1returnin, Arg_2: Arg_2 {O(n)} 35: evalrealheapsortstep1returnin->evalrealheapsortstep1stop, Arg_0: min([3, Arg_0]) {O(n)} 35: evalrealheapsortstep1returnin->evalrealheapsortstep1stop, Arg_1: min([3, Arg_1]) {O(n)} 35: evalrealheapsortstep1returnin->evalrealheapsortstep1stop, Arg_2: min([0, Arg_2]) {O(n)} 0: evalrealheapsortstep1start->evalrealheapsortstep1entryin, Arg_0: Arg_0 {O(n)} 0: evalrealheapsortstep1start->evalrealheapsortstep1entryin, Arg_1: Arg_1 {O(n)} 0: evalrealheapsortstep1start->evalrealheapsortstep1entryin, Arg_2: Arg_2 {O(n)} `Upper: 23: evalrealheapsortstep1bb2in->evalrealheapsortstep1bb3in, Arg_0: Arg_0 {O(n)} 23: evalrealheapsortstep1bb2in->evalrealheapsortstep1bb3in, Arg_1: max([1, 1+Arg_0*Arg_0]) {O(n^2)} 5: evalrealheapsortstep1bb3in->evalrealheapsortstep1bb5in, Arg_0: Arg_0 {O(n)} 5: evalrealheapsortstep1bb3in->evalrealheapsortstep1bb5in, Arg_1: max([1, 1+Arg_0*Arg_0]) {O(n^2)} 5: evalrealheapsortstep1bb3in->evalrealheapsortstep1bb5in, Arg_2: 0 {O(1)} 6: evalrealheapsortstep1bb3in->evalrealheapsortstep1bb4in, Arg_0: Arg_0 {O(n)} 6: evalrealheapsortstep1bb3in->evalrealheapsortstep1bb4in, Arg_1: max([1, 1+Arg_0*Arg_0]) {O(n^2)} 8: evalrealheapsortstep1bb4in->evalrealheapsortstep1bb2in, Arg_0: Arg_0 {O(n)} 8: evalrealheapsortstep1bb4in->evalrealheapsortstep1bb2in, Arg_1: max([1, 1+Arg_0*Arg_0]) {O(n^2)} 11: evalrealheapsortstep1bb4in->evalrealheapsortstep1bb5in, Arg_0: Arg_0 {O(n)} 11: evalrealheapsortstep1bb4in->evalrealheapsortstep1bb5in, Arg_1: max([1, 1+Arg_0*Arg_0]) {O(n^2)} 34: evalrealheapsortstep1bb5in->evalrealheapsortstep1bb6in, Arg_0: Arg_0 {O(n)} 34: evalrealheapsortstep1bb5in->evalrealheapsortstep1bb6in, Arg_1: max([1, 1+Arg_0*Arg_0]) {O(n^2)} 3: evalrealheapsortstep1bb6in->evalrealheapsortstep1bb3in, Arg_0: Arg_0 {O(n)} 3: evalrealheapsortstep1bb6in->evalrealheapsortstep1bb3in, Arg_1: max([1, 1+Arg_0*Arg_0]) {O(n^2)} 3: evalrealheapsortstep1bb6in->evalrealheapsortstep1bb3in, Arg_2: max([1, max([1, 1+Arg_0*Arg_0])]) {O(n^2)} 4: evalrealheapsortstep1bb6in->evalrealheapsortstep1returnin, Arg_0: Arg_0 {O(n)} 4: evalrealheapsortstep1bb6in->evalrealheapsortstep1returnin, Arg_1: max([1, 1+Arg_0*Arg_0]) {O(n^2)} 1: evalrealheapsortstep1entryin->evalrealheapsortstep1bb6in, Arg_0: Arg_0 {O(n)} 1: evalrealheapsortstep1entryin->evalrealheapsortstep1bb6in, Arg_1: 1 {O(1)} 1: evalrealheapsortstep1entryin->evalrealheapsortstep1bb6in, Arg_2: Arg_2 {O(n)} 2: evalrealheapsortstep1entryin->evalrealheapsortstep1returnin, Arg_0: 2 {O(1)} 2: evalrealheapsortstep1entryin->evalrealheapsortstep1returnin, Arg_1: Arg_1 {O(n)} 2: evalrealheapsortstep1entryin->evalrealheapsortstep1returnin, Arg_2: Arg_2 {O(n)} 35: evalrealheapsortstep1returnin->evalrealheapsortstep1stop, Arg_0: max([2, Arg_0]) {O(n)} 35: evalrealheapsortstep1returnin->evalrealheapsortstep1stop, Arg_1: max([1, max([Arg_1, 1+Arg_0*Arg_0])]) {O(n^2)} 0: evalrealheapsortstep1start->evalrealheapsortstep1entryin, Arg_0: Arg_0 {O(n)} 0: evalrealheapsortstep1start->evalrealheapsortstep1entryin, Arg_1: Arg_1 {O(n)} 0: evalrealheapsortstep1start->evalrealheapsortstep1entryin, Arg_2: Arg_2 {O(n)} ---------------------------------------- (4) BOUNDS(1, max(5, 5 + Arg_0) + nat(3 * Arg_0^2) + max(2 * Arg_0 * max(6, max(6, 6 + 6 * Arg_0^2)), 2 * Arg_0 * max(6, 6 + 6 * Arg_0^2), 0) + max(Arg_0 * max(5, 5 + 4 * Arg_0^2), Arg_0 * max(max(5, 5 + 4 * Arg_0^2), 5), 0)) ---------------------------------------- (5) Loat Proof (FINISHED) ### Pre-processing the ITS problem ### Initial linear ITS problem Start location: evalrealheapsortstep1start 0: evalrealheapsortstep1start -> evalrealheapsortstep1entryin : [], cost: 1 1: evalrealheapsortstep1entryin -> evalrealheapsortstep1bb6in : B'=1, [ A>=3 ], cost: 1 2: evalrealheapsortstep1entryin -> evalrealheapsortstep1returnin : [ 2>=A ], cost: 1 3: evalrealheapsortstep1bb6in -> evalrealheapsortstep1bb3in : C'=B, [ A>=1+B ], cost: 1 4: evalrealheapsortstep1bb6in -> evalrealheapsortstep1returnin : [ B>=A ], cost: 1 5: evalrealheapsortstep1bb3in -> evalrealheapsortstep1bb5in : [ 0>=C ], cost: 1 6: evalrealheapsortstep1bb3in -> evalrealheapsortstep1bb4in : [ C>=1 ], cost: 1 7: evalrealheapsortstep1bb4in -> evalrealheapsortstep1bb2in : [ 1+C==0 ], cost: 1 8: evalrealheapsortstep1bb4in -> evalrealheapsortstep1bb2in : [ C>=0 && free>=0 && 1+C>=2*free && 2*free>=C ], cost: 1 9: evalrealheapsortstep1bb4in -> evalrealheapsortstep1bb2in : [ 0>=2+C && 0>=free_1 && 2*free_1>=1+C && 2+C>=2*free_1 ], cost: 1 10: evalrealheapsortstep1bb4in -> evalrealheapsortstep1bb5in : [ 1+C==0 ], cost: 1 11: evalrealheapsortstep1bb4in -> evalrealheapsortstep1bb5in : [ C>=0 && free_2>=0 && 1+C>=2*free_2 && 2*free_2>=C ], cost: 1 12: evalrealheapsortstep1bb4in -> evalrealheapsortstep1bb5in : [ 0>=2+C && 0>=free_3 && 2*free_3>=1+C && 2+C>=2*free_3 ], cost: 1 13: evalrealheapsortstep1bb2in -> evalrealheapsortstep1bb3in : C'=-1, [ 1+C==0 ], cost: 1 14: evalrealheapsortstep1bb2in -> evalrealheapsortstep1bb3in : C'=-1+free_4, [ 0>=1 && free_4>=0 && 0>=2*free_4 && 1+2*free_4>=0 && 1+C==0 ], cost: 1 15: evalrealheapsortstep1bb2in -> evalrealheapsortstep1bb3in : C'=-1+free_5, [ 0>=1 && 0>=free_5 && 2*free_5>=0 && 1>=2*free_5 && 1+C==0 ], cost: 1 16: evalrealheapsortstep1bb2in -> evalrealheapsortstep1bb3in : C'=-1, [ 0>=1 && free_6>=0 && 0>=2*free_6 && 1+2*free_6>=0 && 1+C==0 ], cost: 1 17: evalrealheapsortstep1bb2in -> evalrealheapsortstep1bb3in : C'=-1+free_7, [ 0>=1 && free_8>=0 && 0>=2*free_8 && 1+2*free_8>=0 && free_7>=0 && 0>=2*free_7 && 1+2*free_7>=0 && 1+C==0 ], cost: 1 18: evalrealheapsortstep1bb2in -> evalrealheapsortstep1bb3in : C'=-1+free_9, [ 0>=1 && free_10>=0 && 0>=2*free_10 && 1+2*free_10>=0 && 0>=free_9 && 2*free_9>=0 && 1>=2*free_9 && 1+C==0 ], cost: 1 19: evalrealheapsortstep1bb2in -> evalrealheapsortstep1bb3in : C'=-1, [ 0>=1 && 0>=free_11 && 2*free_11>=0 && 1>=2*free_11 && 1+C==0 ], cost: 1 20: evalrealheapsortstep1bb2in -> evalrealheapsortstep1bb3in : C'=-1+free_12, [ 0>=1 && 0>=free_13 && free_12>=0 && 0>=2*free_12 && 1+2*free_12>=0 && 2*free_13>=0 && 1>=2*free_13 && 1+C==0 ], cost: 1 21: evalrealheapsortstep1bb2in -> evalrealheapsortstep1bb3in : C'=-1+free_14, [ 0>=1 && 0>=free_15 && 0>=free_14 && 2*free_15>=0 && 1>=2*free_15 && 2*free_14>=0 && 1>=2*free_14 && 1+C==0 ], cost: 1 22: evalrealheapsortstep1bb2in -> evalrealheapsortstep1bb3in : C'=-1, [ 0>=1 && free_16>=0 && 0>=2*free_16 && 1+2*free_16>=0 && free_17>=0 && 0>=2*free_17 && 1+2*free_17>=0 && 1+C==0 ], cost: 1 23: evalrealheapsortstep1bb2in -> evalrealheapsortstep1bb3in : C'=-1+free_19, [ C>=0 && free_20>=0 && 1+C>=2*free_20 && 2*free_20>=C && free_18>=0 && 1+C>=2*free_18 && 2*free_18>=C && free_19>=0 && 1+C>=2*free_19 && 2*free_19>=C ], cost: 1 24: evalrealheapsortstep1bb2in -> evalrealheapsortstep1bb3in : C'=-1+free_22, [ C>=0 && free_23>=0 && 1+C>=2*free_23 && 2*free_23>=C && free_21>=0 && 1+C>=2*free_21 && 2*free_21>=C && 0>=2+C && 0>=free_22 && 2*free_22>=1+C && 2+C>=2*free_22 ], cost: 1 25: evalrealheapsortstep1bb2in -> evalrealheapsortstep1bb3in : C'=-1, [ 0>=1 && free_24>=0 && 0>=2*free_24 && 1+2*free_24>=0 && 0>=free_25 && 2*free_25>=0 && 1>=2*free_25 && 1+C==0 ], cost: 1 26: evalrealheapsortstep1bb2in -> evalrealheapsortstep1bb3in : C'=-1+free_27, [ C>=0 && free_28>=0 && 1+C>=2*free_28 && 2*free_28>=C && 0>=2+C && 0>=free_26 && free_27>=0 && 1+C>=2*free_27 && 2*free_27>=C && 2*free_26>=1+C && 2+C>=2*free_26 ], cost: 1 27: evalrealheapsortstep1bb2in -> evalrealheapsortstep1bb3in : C'=-1+free_30, [ C>=0 && free_31>=0 && 1+C>=2*free_31 && 2*free_31>=C && 0>=2+C && 0>=free_29 && 0>=free_30 && 2*free_29>=1+C && 2+C>=2*free_29 && 2*free_30>=1+C && 2+C>=2*free_30 ], cost: 1 28: evalrealheapsortstep1bb2in -> evalrealheapsortstep1bb3in : C'=-1, [ 0>=1 && 0>=free_32 && free_33>=0 && 0>=2*free_33 && 1+2*free_33>=0 && 2*free_32>=0 && 1>=2*free_32 && 1+C==0 ], cost: 1 29: evalrealheapsortstep1bb2in -> evalrealheapsortstep1bb3in : C'=-1+free_35, [ 0>=2+C && 0>=free_36 && C>=0 && free_34>=0 && 1+C>=2*free_34 && 2*free_34>=C && free_35>=0 && 1+C>=2*free_35 && 2*free_35>=C && 2*free_36>=1+C && 2+C>=2*free_36 ], cost: 1 30: evalrealheapsortstep1bb2in -> evalrealheapsortstep1bb3in : C'=-1+free_38, [ 0>=2+C && 0>=free_39 && C>=0 && free_37>=0 && 1+C>=2*free_37 && 2*free_37>=C && 0>=free_38 && 2*free_39>=1+C && 2+C>=2*free_39 && 2*free_38>=1+C && 2+C>=2*free_38 ], cost: 1 31: evalrealheapsortstep1bb2in -> evalrealheapsortstep1bb3in : C'=-1, [ 0>=1 && 0>=free_40 && 0>=free_41 && 2*free_40>=0 && 1>=2*free_40 && 2*free_41>=0 && 1>=2*free_41 && 1+C==0 ], cost: 1 32: evalrealheapsortstep1bb2in -> evalrealheapsortstep1bb3in : C'=-1+free_43, [ 0>=2+C && 0>=free_44 && 0>=free_42 && C>=0 && free_43>=0 && 1+C>=2*free_43 && 2*free_43>=C && 2*free_44>=1+C && 2+C>=2*free_44 && 2*free_42>=1+C && 2+C>=2*free_42 ], cost: 1 33: evalrealheapsortstep1bb2in -> evalrealheapsortstep1bb3in : C'=-1+free_46, [ 0>=2+C && 0>=free_47 && 0>=free_45 && 0>=free_46 && 2*free_47>=1+C && 2+C>=2*free_47 && 2*free_45>=1+C && 2+C>=2*free_45 && 2*free_46>=1+C && 2+C>=2*free_46 ], cost: 1 34: evalrealheapsortstep1bb5in -> evalrealheapsortstep1bb6in : B'=1+B, [], cost: 1 35: evalrealheapsortstep1returnin -> evalrealheapsortstep1stop : [], cost: 1 Removed unreachable and leaf rules: Start location: evalrealheapsortstep1start 0: evalrealheapsortstep1start -> evalrealheapsortstep1entryin : [], cost: 1 1: evalrealheapsortstep1entryin -> evalrealheapsortstep1bb6in : B'=1, [ A>=3 ], cost: 1 3: evalrealheapsortstep1bb6in -> evalrealheapsortstep1bb3in : C'=B, [ A>=1+B ], cost: 1 5: evalrealheapsortstep1bb3in -> evalrealheapsortstep1bb5in : [ 0>=C ], cost: 1 6: evalrealheapsortstep1bb3in -> evalrealheapsortstep1bb4in : [ C>=1 ], cost: 1 7: evalrealheapsortstep1bb4in -> evalrealheapsortstep1bb2in : [ 1+C==0 ], cost: 1 8: evalrealheapsortstep1bb4in -> evalrealheapsortstep1bb2in : [ C>=0 && free>=0 && 1+C>=2*free && 2*free>=C ], cost: 1 9: evalrealheapsortstep1bb4in -> evalrealheapsortstep1bb2in : [ 0>=2+C && 0>=free_1 && 2*free_1>=1+C && 2+C>=2*free_1 ], cost: 1 10: evalrealheapsortstep1bb4in -> evalrealheapsortstep1bb5in : [ 1+C==0 ], cost: 1 11: evalrealheapsortstep1bb4in -> evalrealheapsortstep1bb5in : [ C>=0 && free_2>=0 && 1+C>=2*free_2 && 2*free_2>=C ], cost: 1 12: evalrealheapsortstep1bb4in -> evalrealheapsortstep1bb5in : [ 0>=2+C && 0>=free_3 && 2*free_3>=1+C && 2+C>=2*free_3 ], cost: 1 13: evalrealheapsortstep1bb2in -> evalrealheapsortstep1bb3in : C'=-1, [ 1+C==0 ], cost: 1 14: evalrealheapsortstep1bb2in -> evalrealheapsortstep1bb3in : C'=-1+free_4, [ 0>=1 && free_4>=0 && 0>=2*free_4 && 1+2*free_4>=0 && 1+C==0 ], cost: 1 15: evalrealheapsortstep1bb2in -> evalrealheapsortstep1bb3in : C'=-1+free_5, [ 0>=1 && 0>=free_5 && 2*free_5>=0 && 1>=2*free_5 && 1+C==0 ], cost: 1 16: evalrealheapsortstep1bb2in -> evalrealheapsortstep1bb3in : C'=-1, [ 0>=1 && free_6>=0 && 0>=2*free_6 && 1+2*free_6>=0 && 1+C==0 ], cost: 1 17: evalrealheapsortstep1bb2in -> evalrealheapsortstep1bb3in : C'=-1+free_7, [ 0>=1 && free_8>=0 && 0>=2*free_8 && 1+2*free_8>=0 && free_7>=0 && 0>=2*free_7 && 1+2*free_7>=0 && 1+C==0 ], cost: 1 18: evalrealheapsortstep1bb2in -> evalrealheapsortstep1bb3in : C'=-1+free_9, [ 0>=1 && free_10>=0 && 0>=2*free_10 && 1+2*free_10>=0 && 0>=free_9 && 2*free_9>=0 && 1>=2*free_9 && 1+C==0 ], cost: 1 19: evalrealheapsortstep1bb2in -> evalrealheapsortstep1bb3in : C'=-1, [ 0>=1 && 0>=free_11 && 2*free_11>=0 && 1>=2*free_11 && 1+C==0 ], cost: 1 20: evalrealheapsortstep1bb2in -> evalrealheapsortstep1bb3in : C'=-1+free_12, [ 0>=1 && 0>=free_13 && free_12>=0 && 0>=2*free_12 && 1+2*free_12>=0 && 2*free_13>=0 && 1>=2*free_13 && 1+C==0 ], cost: 1 21: evalrealheapsortstep1bb2in -> evalrealheapsortstep1bb3in : C'=-1+free_14, [ 0>=1 && 0>=free_15 && 0>=free_14 && 2*free_15>=0 && 1>=2*free_15 && 2*free_14>=0 && 1>=2*free_14 && 1+C==0 ], cost: 1 22: evalrealheapsortstep1bb2in -> evalrealheapsortstep1bb3in : C'=-1, [ 0>=1 && free_16>=0 && 0>=2*free_16 && 1+2*free_16>=0 && free_17>=0 && 0>=2*free_17 && 1+2*free_17>=0 && 1+C==0 ], cost: 1 23: evalrealheapsortstep1bb2in -> evalrealheapsortstep1bb3in : C'=-1+free_19, [ C>=0 && free_20>=0 && 1+C>=2*free_20 && 2*free_20>=C && free_18>=0 && 1+C>=2*free_18 && 2*free_18>=C && free_19>=0 && 1+C>=2*free_19 && 2*free_19>=C ], cost: 1 24: evalrealheapsortstep1bb2in -> evalrealheapsortstep1bb3in : C'=-1+free_22, [ C>=0 && free_23>=0 && 1+C>=2*free_23 && 2*free_23>=C && free_21>=0 && 1+C>=2*free_21 && 2*free_21>=C && 0>=2+C && 0>=free_22 && 2*free_22>=1+C && 2+C>=2*free_22 ], cost: 1 25: evalrealheapsortstep1bb2in -> evalrealheapsortstep1bb3in : C'=-1, [ 0>=1 && free_24>=0 && 0>=2*free_24 && 1+2*free_24>=0 && 0>=free_25 && 2*free_25>=0 && 1>=2*free_25 && 1+C==0 ], cost: 1 26: evalrealheapsortstep1bb2in -> evalrealheapsortstep1bb3in : C'=-1+free_27, [ C>=0 && free_28>=0 && 1+C>=2*free_28 && 2*free_28>=C && 0>=2+C && 0>=free_26 && free_27>=0 && 1+C>=2*free_27 && 2*free_27>=C && 2*free_26>=1+C && 2+C>=2*free_26 ], cost: 1 27: evalrealheapsortstep1bb2in -> evalrealheapsortstep1bb3in : C'=-1+free_30, [ C>=0 && free_31>=0 && 1+C>=2*free_31 && 2*free_31>=C && 0>=2+C && 0>=free_29 && 0>=free_30 && 2*free_29>=1+C && 2+C>=2*free_29 && 2*free_30>=1+C && 2+C>=2*free_30 ], cost: 1 28: evalrealheapsortstep1bb2in -> evalrealheapsortstep1bb3in : C'=-1, [ 0>=1 && 0>=free_32 && free_33>=0 && 0>=2*free_33 && 1+2*free_33>=0 && 2*free_32>=0 && 1>=2*free_32 && 1+C==0 ], cost: 1 29: evalrealheapsortstep1bb2in -> evalrealheapsortstep1bb3in : C'=-1+free_35, [ 0>=2+C && 0>=free_36 && C>=0 && free_34>=0 && 1+C>=2*free_34 && 2*free_34>=C && free_35>=0 && 1+C>=2*free_35 && 2*free_35>=C && 2*free_36>=1+C && 2+C>=2*free_36 ], cost: 1 30: evalrealheapsortstep1bb2in -> evalrealheapsortstep1bb3in : C'=-1+free_38, [ 0>=2+C && 0>=free_39 && C>=0 && free_37>=0 && 1+C>=2*free_37 && 2*free_37>=C && 0>=free_38 && 2*free_39>=1+C && 2+C>=2*free_39 && 2*free_38>=1+C && 2+C>=2*free_38 ], cost: 1 31: evalrealheapsortstep1bb2in -> evalrealheapsortstep1bb3in : C'=-1, [ 0>=1 && 0>=free_40 && 0>=free_41 && 2*free_40>=0 && 1>=2*free_40 && 2*free_41>=0 && 1>=2*free_41 && 1+C==0 ], cost: 1 32: evalrealheapsortstep1bb2in -> evalrealheapsortstep1bb3in : C'=-1+free_43, [ 0>=2+C && 0>=free_44 && 0>=free_42 && C>=0 && free_43>=0 && 1+C>=2*free_43 && 2*free_43>=C && 2*free_44>=1+C && 2+C>=2*free_44 && 2*free_42>=1+C && 2+C>=2*free_42 ], cost: 1 33: evalrealheapsortstep1bb2in -> evalrealheapsortstep1bb3in : C'=-1+free_46, [ 0>=2+C && 0>=free_47 && 0>=free_45 && 0>=free_46 && 2*free_47>=1+C && 2+C>=2*free_47 && 2*free_45>=1+C && 2+C>=2*free_45 && 2*free_46>=1+C && 2+C>=2*free_46 ], cost: 1 34: evalrealheapsortstep1bb5in -> evalrealheapsortstep1bb6in : B'=1+B, [], cost: 1 Removed rules with unsatisfiable guard: Start location: evalrealheapsortstep1start 0: evalrealheapsortstep1start -> evalrealheapsortstep1entryin : [], cost: 1 1: evalrealheapsortstep1entryin -> evalrealheapsortstep1bb6in : B'=1, [ A>=3 ], cost: 1 3: evalrealheapsortstep1bb6in -> evalrealheapsortstep1bb3in : C'=B, [ A>=1+B ], cost: 1 5: evalrealheapsortstep1bb3in -> evalrealheapsortstep1bb5in : [ 0>=C ], cost: 1 6: evalrealheapsortstep1bb3in -> evalrealheapsortstep1bb4in : [ C>=1 ], cost: 1 7: evalrealheapsortstep1bb4in -> evalrealheapsortstep1bb2in : [ 1+C==0 ], cost: 1 8: evalrealheapsortstep1bb4in -> evalrealheapsortstep1bb2in : [ C>=0 && free>=0 && 1+C>=2*free && 2*free>=C ], cost: 1 9: evalrealheapsortstep1bb4in -> evalrealheapsortstep1bb2in : [ 0>=2+C && 0>=free_1 && 2*free_1>=1+C && 2+C>=2*free_1 ], cost: 1 10: evalrealheapsortstep1bb4in -> evalrealheapsortstep1bb5in : [ 1+C==0 ], cost: 1 11: evalrealheapsortstep1bb4in -> evalrealheapsortstep1bb5in : [ C>=0 && free_2>=0 && 1+C>=2*free_2 && 2*free_2>=C ], cost: 1 12: evalrealheapsortstep1bb4in -> evalrealheapsortstep1bb5in : [ 0>=2+C && 0>=free_3 && 2*free_3>=1+C && 2+C>=2*free_3 ], cost: 1 13: evalrealheapsortstep1bb2in -> evalrealheapsortstep1bb3in : C'=-1, [ 1+C==0 ], cost: 1 23: evalrealheapsortstep1bb2in -> evalrealheapsortstep1bb3in : C'=-1+free_19, [ C>=0 && free_20>=0 && 1+C>=2*free_20 && 2*free_20>=C && free_18>=0 && 1+C>=2*free_18 && 2*free_18>=C && free_19>=0 && 1+C>=2*free_19 && 2*free_19>=C ], cost: 1 33: evalrealheapsortstep1bb2in -> evalrealheapsortstep1bb3in : C'=-1+free_46, [ 0>=2+C && 0>=free_47 && 0>=free_45 && 0>=free_46 && 2*free_47>=1+C && 2+C>=2*free_47 && 2*free_45>=1+C && 2+C>=2*free_45 && 2*free_46>=1+C && 2+C>=2*free_46 ], cost: 1 34: evalrealheapsortstep1bb5in -> evalrealheapsortstep1bb6in : B'=1+B, [], cost: 1 Simplified all rules, resulting in: Start location: evalrealheapsortstep1start 0: evalrealheapsortstep1start -> evalrealheapsortstep1entryin : [], cost: 1 1: evalrealheapsortstep1entryin -> evalrealheapsortstep1bb6in : B'=1, [ A>=3 ], cost: 1 3: evalrealheapsortstep1bb6in -> evalrealheapsortstep1bb3in : C'=B, [ A>=1+B ], cost: 1 5: evalrealheapsortstep1bb3in -> evalrealheapsortstep1bb5in : [ 0>=C ], cost: 1 6: evalrealheapsortstep1bb3in -> evalrealheapsortstep1bb4in : [ C>=1 ], cost: 1 7: evalrealheapsortstep1bb4in -> evalrealheapsortstep1bb2in : [ 1+C==0 ], cost: 1 8: evalrealheapsortstep1bb4in -> evalrealheapsortstep1bb2in : [ C>=0 && free>=0 && 1+C>=2*free && 2*free>=C ], cost: 1 9: evalrealheapsortstep1bb4in -> evalrealheapsortstep1bb2in : [ 0>=2+C && 0>=free_1 && 2*free_1>=1+C && 2+C>=2*free_1 ], cost: 1 10: evalrealheapsortstep1bb4in -> evalrealheapsortstep1bb5in : [ 1+C==0 ], cost: 1 11: evalrealheapsortstep1bb4in -> evalrealheapsortstep1bb5in : [ C>=0 && free_2>=0 && 1+C>=2*free_2 && 2*free_2>=C ], cost: 1 12: evalrealheapsortstep1bb4in -> evalrealheapsortstep1bb5in : [ 0>=2+C && 0>=free_3 && 2*free_3>=1+C && 2+C>=2*free_3 ], cost: 1 13: evalrealheapsortstep1bb2in -> evalrealheapsortstep1bb3in : C'=-1, [ 1+C==0 ], cost: 1 23: evalrealheapsortstep1bb2in -> evalrealheapsortstep1bb3in : C'=-1+free_19, [ C>=0 && 1+C>=2*free_20 && 2*free_20>=C && 1+C>=2*free_18 && 2*free_18>=C && free_19>=0 && 1+C>=2*free_19 && 2*free_19>=C ], cost: 1 33: evalrealheapsortstep1bb2in -> evalrealheapsortstep1bb3in : C'=-1+free_46, [ 0>=2+C && 0>=free_46 && 2*free_47>=1+C && 2+C>=2*free_47 && 2*free_45>=1+C && 2+C>=2*free_45 && 2*free_46>=1+C && 2+C>=2*free_46 ], cost: 1 34: evalrealheapsortstep1bb5in -> evalrealheapsortstep1bb6in : B'=1+B, [], cost: 1 ### Simplification by acceleration and chaining ### Eliminated locations (on linear paths): Start location: evalrealheapsortstep1start 36: evalrealheapsortstep1start -> evalrealheapsortstep1bb6in : B'=1, [ A>=3 ], cost: 2 3: evalrealheapsortstep1bb6in -> evalrealheapsortstep1bb3in : C'=B, [ A>=1+B ], cost: 1 5: evalrealheapsortstep1bb3in -> evalrealheapsortstep1bb5in : [ 0>=C ], cost: 1 6: evalrealheapsortstep1bb3in -> evalrealheapsortstep1bb4in : [ C>=1 ], cost: 1 7: evalrealheapsortstep1bb4in -> evalrealheapsortstep1bb2in : [ 1+C==0 ], cost: 1 8: evalrealheapsortstep1bb4in -> evalrealheapsortstep1bb2in : [ C>=0 && free>=0 && 1+C>=2*free && 2*free>=C ], cost: 1 9: evalrealheapsortstep1bb4in -> evalrealheapsortstep1bb2in : [ 0>=2+C && 0>=free_1 && 2*free_1>=1+C && 2+C>=2*free_1 ], cost: 1 10: evalrealheapsortstep1bb4in -> evalrealheapsortstep1bb5in : [ 1+C==0 ], cost: 1 11: evalrealheapsortstep1bb4in -> evalrealheapsortstep1bb5in : [ C>=0 && free_2>=0 && 1+C>=2*free_2 && 2*free_2>=C ], cost: 1 12: evalrealheapsortstep1bb4in -> evalrealheapsortstep1bb5in : [ 0>=2+C && 0>=free_3 && 2*free_3>=1+C && 2+C>=2*free_3 ], cost: 1 13: evalrealheapsortstep1bb2in -> evalrealheapsortstep1bb3in : C'=-1, [ 1+C==0 ], cost: 1 23: evalrealheapsortstep1bb2in -> evalrealheapsortstep1bb3in : C'=-1+free_19, [ C>=0 && 1+C>=2*free_20 && 2*free_20>=C && 1+C>=2*free_18 && 2*free_18>=C && free_19>=0 && 1+C>=2*free_19 && 2*free_19>=C ], cost: 1 33: evalrealheapsortstep1bb2in -> evalrealheapsortstep1bb3in : C'=-1+free_46, [ 0>=2+C && 0>=free_46 && 2*free_47>=1+C && 2+C>=2*free_47 && 2*free_45>=1+C && 2+C>=2*free_45 && 2*free_46>=1+C && 2+C>=2*free_46 ], cost: 1 34: evalrealheapsortstep1bb5in -> evalrealheapsortstep1bb6in : B'=1+B, [], cost: 1 Eliminated locations (on tree-shaped paths): Start location: evalrealheapsortstep1start 36: evalrealheapsortstep1start -> evalrealheapsortstep1bb6in : B'=1, [ A>=3 ], cost: 2 3: evalrealheapsortstep1bb6in -> evalrealheapsortstep1bb3in : C'=B, [ A>=1+B ], cost: 1 37: evalrealheapsortstep1bb3in -> evalrealheapsortstep1bb2in : [ C>=1 && free>=0 && 1+C>=2*free && 2*free>=C ], cost: 2 39: evalrealheapsortstep1bb3in -> evalrealheapsortstep1bb6in : B'=1+B, [ 0>=C ], cost: 2 40: evalrealheapsortstep1bb3in -> evalrealheapsortstep1bb6in : B'=1+B, [ C>=1 && free_2>=0 && 1+C>=2*free_2 && 2*free_2>=C ], cost: 3 13: evalrealheapsortstep1bb2in -> evalrealheapsortstep1bb3in : C'=-1, [ 1+C==0 ], cost: 1 23: evalrealheapsortstep1bb2in -> evalrealheapsortstep1bb3in : C'=-1+free_19, [ C>=0 && 1+C>=2*free_20 && 2*free_20>=C && 1+C>=2*free_18 && 2*free_18>=C && free_19>=0 && 1+C>=2*free_19 && 2*free_19>=C ], cost: 1 33: evalrealheapsortstep1bb2in -> evalrealheapsortstep1bb3in : C'=-1+free_46, [ 0>=2+C && 0>=free_46 && 2*free_47>=1+C && 2+C>=2*free_47 && 2*free_45>=1+C && 2+C>=2*free_45 && 2*free_46>=1+C && 2+C>=2*free_46 ], cost: 1 Eliminated locations (on tree-shaped paths): Start location: evalrealheapsortstep1start 36: evalrealheapsortstep1start -> evalrealheapsortstep1bb6in : B'=1, [ A>=3 ], cost: 2 3: evalrealheapsortstep1bb6in -> evalrealheapsortstep1bb3in : C'=B, [ A>=1+B ], cost: 1 39: evalrealheapsortstep1bb3in -> evalrealheapsortstep1bb6in : B'=1+B, [ 0>=C ], cost: 2 40: evalrealheapsortstep1bb3in -> evalrealheapsortstep1bb6in : B'=1+B, [ C>=1 && free_2>=0 && 1+C>=2*free_2 && 2*free_2>=C ], cost: 3 41: evalrealheapsortstep1bb3in -> evalrealheapsortstep1bb3in : C'=-1+free_19, [ C>=1 && free>=0 && 1+C>=2*free && 2*free>=C && 1+C>=2*free_20 && 2*free_20>=C && 1+C>=2*free_18 && 2*free_18>=C && free_19>=0 && 1+C>=2*free_19 && 2*free_19>=C ], cost: 3 Accelerating simple loops of location 3. Accelerating the following rules: 41: evalrealheapsortstep1bb3in -> evalrealheapsortstep1bb3in : C'=-1+free_19, [ C>=1 && free>=0 && 1+C>=2*free && 2*free>=C && 1+C>=2*free_20 && 2*free_20>=C && 1+C>=2*free_18 && 2*free_18>=C && free_19>=0 && 1+C>=2*free_19 && 2*free_19>=C ], cost: 3 Accelerated rule 41 with NONTERM (after strengthening guard), yielding the new rule 42. Removing the simple loops:. Accelerated all simple loops using metering functions (where possible): Start location: evalrealheapsortstep1start 36: evalrealheapsortstep1start -> evalrealheapsortstep1bb6in : B'=1, [ A>=3 ], cost: 2 3: evalrealheapsortstep1bb6in -> evalrealheapsortstep1bb3in : C'=B, [ A>=1+B ], cost: 1 39: evalrealheapsortstep1bb3in -> evalrealheapsortstep1bb6in : B'=1+B, [ 0>=C ], cost: 2 40: evalrealheapsortstep1bb3in -> evalrealheapsortstep1bb6in : B'=1+B, [ C>=1 && free_2>=0 && 1+C>=2*free_2 && 2*free_2>=C ], cost: 3 41: evalrealheapsortstep1bb3in -> evalrealheapsortstep1bb3in : C'=-1+free_19, [ C>=1 && free>=0 && 1+C>=2*free && 2*free>=C && 1+C>=2*free_20 && 2*free_20>=C && 1+C>=2*free_18 && 2*free_18>=C && free_19>=0 && 1+C>=2*free_19 && 2*free_19>=C ], cost: 3 42: evalrealheapsortstep1bb3in -> [9] : [ C>=1 && free>=0 && 1+C>=2*free && 2*free>=C && 1+C>=2*free_20 && 2*free_20>=C && 1+C>=2*free_18 && 2*free_18>=C && 1+C>=2*free_19 && 2*free_19>=C && -1+free_19>=1 && free_19>=2*free && free_19>=2*free_20 && free_19>=2*free_18 && free_19>=2*free_19 ], cost: INF Chained accelerated rules (with incoming rules): Start location: evalrealheapsortstep1start 36: evalrealheapsortstep1start -> evalrealheapsortstep1bb6in : B'=1, [ A>=3 ], cost: 2 3: evalrealheapsortstep1bb6in -> evalrealheapsortstep1bb3in : C'=B, [ A>=1+B ], cost: 1 43: evalrealheapsortstep1bb6in -> evalrealheapsortstep1bb3in : C'=-1+free_19, [ A>=1+B && B>=1 && free>=0 && 1+B>=2*free && 2*free>=B && 1+B>=2*free_20 && 2*free_20>=B && 1+B>=2*free_18 && 2*free_18>=B && free_19>=0 && 1+B>=2*free_19 && 2*free_19>=B ], cost: 4 39: evalrealheapsortstep1bb3in -> evalrealheapsortstep1bb6in : B'=1+B, [ 0>=C ], cost: 2 40: evalrealheapsortstep1bb3in -> evalrealheapsortstep1bb6in : B'=1+B, [ C>=1 && free_2>=0 && 1+C>=2*free_2 && 2*free_2>=C ], cost: 3 Removed unreachable locations (and leaf rules with constant cost): Start location: evalrealheapsortstep1start 36: evalrealheapsortstep1start -> evalrealheapsortstep1bb6in : B'=1, [ A>=3 ], cost: 2 3: evalrealheapsortstep1bb6in -> evalrealheapsortstep1bb3in : C'=B, [ A>=1+B ], cost: 1 43: evalrealheapsortstep1bb6in -> evalrealheapsortstep1bb3in : C'=-1+free_19, [ A>=1+B && B>=1 && free>=0 && 1+B>=2*free && 2*free>=B && 1+B>=2*free_20 && 2*free_20>=B && 1+B>=2*free_18 && 2*free_18>=B && free_19>=0 && 1+B>=2*free_19 && 2*free_19>=B ], cost: 4 39: evalrealheapsortstep1bb3in -> evalrealheapsortstep1bb6in : B'=1+B, [ 0>=C ], cost: 2 40: evalrealheapsortstep1bb3in -> evalrealheapsortstep1bb6in : B'=1+B, [ C>=1 && free_2>=0 && 1+C>=2*free_2 && 2*free_2>=C ], cost: 3 Eliminated locations (on tree-shaped paths): Start location: evalrealheapsortstep1start 36: evalrealheapsortstep1start -> evalrealheapsortstep1bb6in : B'=1, [ A>=3 ], cost: 2 44: evalrealheapsortstep1bb6in -> evalrealheapsortstep1bb6in : B'=1+B, C'=B, [ A>=1+B && 0>=B ], cost: 3 45: evalrealheapsortstep1bb6in -> evalrealheapsortstep1bb6in : B'=1+B, C'=B, [ A>=1+B && B>=1 && free_2>=0 && 1+B>=2*free_2 && 2*free_2>=B ], cost: 4 46: evalrealheapsortstep1bb6in -> evalrealheapsortstep1bb6in : B'=1+B, C'=-1+free_19, [ A>=1+B && B>=1 && free>=0 && 1+B>=2*free && 2*free>=B && 1+B>=2*free_20 && 2*free_20>=B && 1+B>=2*free_18 && 2*free_18>=B && free_19>=0 && 1+B>=2*free_19 && 2*free_19>=B && 0>=-1+free_19 ], cost: 6 47: evalrealheapsortstep1bb6in -> evalrealheapsortstep1bb6in : B'=1+B, C'=-1+free_19, [ A>=1+B && B>=1 && free>=0 && 1+B>=2*free && 2*free>=B && 1+B>=2*free_20 && 2*free_20>=B && 1+B>=2*free_18 && 2*free_18>=B && 1+B>=2*free_19 && 2*free_19>=B && -1+free_19>=1 && free_2>=0 && free_19>=2*free_2 && 2*free_2>=-1+free_19 ], cost: 7 Accelerating simple loops of location 2. Accelerating the following rules: 44: evalrealheapsortstep1bb6in -> evalrealheapsortstep1bb6in : B'=1+B, C'=B, [ A>=1+B && 0>=B ], cost: 3 45: evalrealheapsortstep1bb6in -> evalrealheapsortstep1bb6in : B'=1+B, C'=B, [ A>=1+B && B>=1 && free_2>=0 && 1+B>=2*free_2 && 2*free_2>=B ], cost: 4 46: evalrealheapsortstep1bb6in -> evalrealheapsortstep1bb6in : B'=1+B, C'=-1+free_19, [ A>=1+B && B>=1 && free>=0 && 1+B>=2*free && 2*free>=B && 1+B>=2*free_20 && 2*free_20>=B && 1+B>=2*free_18 && 2*free_18>=B && free_19>=0 && 1+B>=2*free_19 && 2*free_19>=B && 0>=-1+free_19 ], cost: 6 47: evalrealheapsortstep1bb6in -> evalrealheapsortstep1bb6in : B'=1+B, C'=-1+free_19, [ A>=1+B && B>=1 && free>=0 && 1+B>=2*free && 2*free>=B && 1+B>=2*free_20 && 2*free_20>=B && 1+B>=2*free_18 && 2*free_18>=B && 1+B>=2*free_19 && 2*free_19>=B && -1+free_19>=1 && free_2>=0 && free_19>=2*free_2 && 2*free_2>=-1+free_19 ], cost: 7 Accelerated rule 44 with backward acceleration, yielding the new rule 48. Accelerated rule 44 with backward acceleration, yielding the new rule 49. Accelerated rule 45 with backward acceleration, yielding the new rule 50. Accelerated rule 45 with backward acceleration, yielding the new rule 51. Accelerated rule 46 with backward acceleration, yielding the new rule 52. Accelerated rule 47 with backward acceleration, yielding the new rule 53. Nested simple loops 44 (outer loop) and 52 (inner loop) with metering function meter_3 (where 3*meter_3==-B), resulting in the new rules: 54. Nested simple loops 45 (outer loop) and 52 (inner loop) with metering function meter_4 (where 2*meter_4==1-k_2+free_19-B), resulting in the new rules: 55. Nested simple loops 45 (outer loop) and 53 (inner loop) with metering function meter_5 (where 3*meter_5==3+free_2-free_19-B), resulting in the new rules: 56. Removing the simple loops: 44 45 46 47. Accelerated all simple loops using metering functions (where possible): Start location: evalrealheapsortstep1start 36: evalrealheapsortstep1start -> evalrealheapsortstep1bb6in : B'=1, [ A>=3 ], cost: 2 48: evalrealheapsortstep1bb6in -> evalrealheapsortstep1bb6in : B'=A, C'=-1+A, [ A>=1+B && 0>=B && 0>=-1+A ], cost: 3*A-3*B 49: evalrealheapsortstep1bb6in -> evalrealheapsortstep1bb6in : B'=1, C'=0, [ A>=1+B && 0>=B && A>=1 ], cost: 3-3*B 50: evalrealheapsortstep1bb6in -> evalrealheapsortstep1bb6in : B'=A, C'=-1+A, [ A>=1+B && B>=1 && free_2>=0 && 1+B>=2*free_2 && 2*free_2>=B && -1+A>=1 && A>=2*free_2 && 2*free_2>=-1+A ], cost: 4*A-4*B 51: evalrealheapsortstep1bb6in -> evalrealheapsortstep1bb6in : B'=1+2*free_2, C'=2*free_2, [ A>=1+B && B>=1 && free_2>=0 && 1+B>=2*free_2 && 2*free_2>=B && A>=1+2*free_2 && 2*free_2>=1 ], cost: 4+8*free_2-4*B 52: evalrealheapsortstep1bb6in -> evalrealheapsortstep1bb6in : B'=k_2+B, C'=-1+free_19, [ A>=1+B && B>=1 && free>=0 && 1+B>=2*free && 2*free>=B && 1+B>=2*free_20 && 2*free_20>=B && 1+B>=2*free_18 && 2*free_18>=B && free_19>=0 && 1+B>=2*free_19 && 2*free_19>=B && 0>=-1+free_19 && k_2>0 && A>=k_2+B && -1+k_2+B>=1 && k_2+B>=2*free && 2*free>=-1+k_2+B && k_2+B>=2*free_20 && 2*free_20>=-1+k_2+B && k_2+B>=2*free_18 && 2*free_18>=-1+k_2+B && k_2+B>=2*free_19 && 2*free_19>=-1+k_2+B ], cost: 6*k_2 53: evalrealheapsortstep1bb6in -> evalrealheapsortstep1bb6in : B'=k_3+B, C'=-1+free_19, [ A>=1+B && B>=1 && free>=0 && 1+B>=2*free && 2*free>=B && 1+B>=2*free_20 && 2*free_20>=B && 1+B>=2*free_18 && 2*free_18>=B && 1+B>=2*free_19 && 2*free_19>=B && -1+free_19>=1 && free_2>=0 && free_19>=2*free_2 && 2*free_2>=-1+free_19 && k_3>0 && A>=k_3+B && -1+k_3+B>=1 && k_3+B>=2*free && 2*free>=-1+k_3+B && k_3+B>=2*free_20 && 2*free_20>=-1+k_3+B && k_3+B>=2*free_18 && 2*free_18>=-1+k_3+B && k_3+B>=2*free_19 && 2*free_19>=-1+k_3+B ], cost: 7*k_3 54: evalrealheapsortstep1bb6in -> evalrealheapsortstep1bb6in : B'=k_2*meter_3+meter_3+B, C'=-1+free_19, [ B==0 && A>=2+B && free>=0 && 2+B>=2*free && 2*free>=1+B && 2+B>=2*free_20 && 2*free_20>=1+B && 2+B>=2*free_18 && 2*free_18>=1+B && free_19>=0 && 2+B>=2*free_19 && 2*free_19>=1+B && 0>=-1+free_19 && k_2>0 && A>=1+k_2+B && k_2+B>=1 && 1+k_2+B>=2*free && 2*free>=k_2+B && 1+k_2+B>=2*free_20 && 2*free_20>=k_2+B && 1+k_2+B>=2*free_18 && 2*free_18>=k_2+B && 1+k_2+B>=2*free_19 && 2*free_19>=k_2+B && 3*meter_3==-B && meter_3>=1 ], cost: 6*k_2*meter_3+3*meter_3 55: evalrealheapsortstep1bb6in -> evalrealheapsortstep1bb6in : B'=meter_4+k_2*meter_4+B, C'=-1+free_19, [ B>=1 && free_2>=0 && 1+B>=2*free_2 && 2*free_2>=B && A>=2+B && free>=0 && 2+B>=2*free && 2*free>=1+B && 2+B>=2*free_20 && 2*free_20>=1+B && 2+B>=2*free_18 && 2*free_18>=1+B && free_19>=0 && 2+B>=2*free_19 && 2*free_19>=1+B && 0>=-1+free_19 && k_2>0 && A>=1+k_2+B && k_2+B>=1 && 1+k_2+B>=2*free && 2*free>=k_2+B && 1+k_2+B>=2*free_20 && 2*free_20>=k_2+B && 1+k_2+B>=2*free_18 && 2*free_18>=k_2+B && 1+k_2+B>=2*free_19 && 2*free_19>=k_2+B && 2*meter_4==1-k_2+free_19-B && meter_4>=1 ], cost: 4*meter_4+6*k_2*meter_4 56: evalrealheapsortstep1bb6in -> evalrealheapsortstep1bb6in : B'=k_3*meter_5+meter_5+B, C'=-1+free_19, [ B>=1 && free_2>=0 && 1+B>=2*free_2 && 2*free_2>=B && A>=2+B && free>=0 && 2+B>=2*free && 2*free>=1+B && 2+B>=2*free_20 && 2*free_20>=1+B && 2+B>=2*free_18 && 2*free_18>=1+B && 2+B>=2*free_19 && 2*free_19>=1+B && -1+free_19>=1 && free_19>=2*free_2 && 2*free_2>=-1+free_19 && k_3>0 && A>=1+k_3+B && k_3+B>=1 && 1+k_3+B>=2*free && 2*free>=k_3+B && 1+k_3+B>=2*free_20 && 2*free_20>=k_3+B && 1+k_3+B>=2*free_18 && 2*free_18>=k_3+B && 1+k_3+B>=2*free_19 && 2*free_19>=k_3+B && 3*meter_5==3+free_2-free_19-B && meter_5>=1 ], cost: 7*k_3*meter_5+4*meter_5 Chained accelerated rules (with incoming rules): Start location: evalrealheapsortstep1start 36: evalrealheapsortstep1start -> evalrealheapsortstep1bb6in : B'=1, [ A>=3 ], cost: 2 57: evalrealheapsortstep1start -> evalrealheapsortstep1bb6in : B'=A, C'=-1+A, [ A>=3 && free_2>=0 && 2>=2*free_2 && 2*free_2>=1 && A>=2*free_2 && 2*free_2>=-1+A ], cost: -2+4*A 58: evalrealheapsortstep1start -> evalrealheapsortstep1bb6in : B'=1+2*free_2, C'=2*free_2, [ A>=3 && free_2>=0 && 2>=2*free_2 && 2*free_2>=1 && A>=1+2*free_2 ], cost: 2+8*free_2 59: evalrealheapsortstep1start -> evalrealheapsortstep1bb6in : B'=1+k_2, C'=-1+free_19, [ A>=3 && free>=0 && 2>=2*free && 2*free>=1 && 2>=2*free_20 && 2*free_20>=1 && 2>=2*free_18 && 2*free_18>=1 && free_19>=0 && 2>=2*free_19 && 2*free_19>=1 && 0>=-1+free_19 && k_2>0 && A>=1+k_2 && 1+k_2>=2*free && 2*free>=k_2 && 1+k_2>=2*free_20 && 2*free_20>=k_2 && 1+k_2>=2*free_18 && 2*free_18>=k_2 && 1+k_2>=2*free_19 && 2*free_19>=k_2 ], cost: 2+6*k_2 Removed unreachable locations (and leaf rules with constant cost): Start location: evalrealheapsortstep1start 57: evalrealheapsortstep1start -> evalrealheapsortstep1bb6in : B'=A, C'=-1+A, [ A>=3 && free_2>=0 && 2>=2*free_2 && 2*free_2>=1 && A>=2*free_2 && 2*free_2>=-1+A ], cost: -2+4*A 58: evalrealheapsortstep1start -> evalrealheapsortstep1bb6in : B'=1+2*free_2, C'=2*free_2, [ A>=3 && free_2>=0 && 2>=2*free_2 && 2*free_2>=1 && A>=1+2*free_2 ], cost: 2+8*free_2 59: evalrealheapsortstep1start -> evalrealheapsortstep1bb6in : B'=1+k_2, C'=-1+free_19, [ A>=3 && free>=0 && 2>=2*free && 2*free>=1 && 2>=2*free_20 && 2*free_20>=1 && 2>=2*free_18 && 2*free_18>=1 && free_19>=0 && 2>=2*free_19 && 2*free_19>=1 && 0>=-1+free_19 && k_2>0 && A>=1+k_2 && 1+k_2>=2*free && 2*free>=k_2 && 1+k_2>=2*free_20 && 2*free_20>=k_2 && 1+k_2>=2*free_18 && 2*free_18>=k_2 && 1+k_2>=2*free_19 && 2*free_19>=k_2 ], cost: 2+6*k_2 ### Computing asymptotic complexity ### Fully simplified ITS problem Start location: evalrealheapsortstep1start 57: evalrealheapsortstep1start -> evalrealheapsortstep1bb6in : B'=A, C'=-1+A, [ A>=3 && free_2>=0 && 2>=2*free_2 && 2*free_2>=1 && A>=2*free_2 && 2*free_2>=-1+A ], cost: -2+4*A 58: evalrealheapsortstep1start -> evalrealheapsortstep1bb6in : B'=1+2*free_2, C'=2*free_2, [ A>=3 && free_2>=0 && 2>=2*free_2 && 2*free_2>=1 && A>=1+2*free_2 ], cost: 2+8*free_2 59: evalrealheapsortstep1start -> evalrealheapsortstep1bb6in : B'=1+k_2, C'=-1+free_19, [ A>=3 && free>=0 && 2>=2*free && 2*free>=1 && 2>=2*free_20 && 2*free_20>=1 && 2>=2*free_18 && 2*free_18>=1 && free_19>=0 && 2>=2*free_19 && 2*free_19>=1 && 0>=-1+free_19 && k_2>0 && A>=1+k_2 && 1+k_2>=2*free && 2*free>=k_2 && 1+k_2>=2*free_20 && 2*free_20>=k_2 && 1+k_2>=2*free_18 && 2*free_18>=k_2 && 1+k_2>=2*free_19 && 2*free_19>=k_2 ], cost: 2+6*k_2 Computing asymptotic complexity for rule 57 Simplified the guard: 57: evalrealheapsortstep1start -> evalrealheapsortstep1bb6in : B'=A, C'=-1+A, [ A>=3 && 2>=2*free_2 && 2*free_2>=1 && 2*free_2>=-1+A ], cost: -2+4*A Could not solve the limit problem. Resulting cost 0 has complexity: Unknown Computing asymptotic complexity for rule 58 Simplified the guard: 58: evalrealheapsortstep1start -> evalrealheapsortstep1bb6in : B'=1+2*free_2, C'=2*free_2, [ A>=3 && 2>=2*free_2 && 2*free_2>=1 ], cost: 2+8*free_2 Could not solve the limit problem. Resulting cost 0 has complexity: Unknown Computing asymptotic complexity for rule 59 Simplified the guard: 59: evalrealheapsortstep1start -> evalrealheapsortstep1bb6in : B'=1+k_2, C'=-1+free_19, [ A>=3 && 2>=2*free && 2>=2*free_20 && 2*free_20>=1 && 2>=2*free_18 && 2*free_18>=1 && 2>=2*free_19 && 2*free_19>=1 && k_2>0 && A>=1+k_2 && 2*free>=k_2 ], cost: 2+6*k_2 Could not solve the limit problem. Resulting cost 0 has complexity: Unknown Obtained the following overall complexity (w.r.t. the length of the input n): Complexity: Unknown Cpx degree: ? Solved cost: 0 Rule cost: 0 Rule guard: [] WORST_CASE(Omega(0),?) ---------------------------------------- (6) BOUNDS(1, INF)