ALICe documentation

Model realheapsort_step2

«  Model realheapsort_step1   ::   Contents   ::   Model realselect  »

Model realheapsort_step2

Cited in: [AliasDFG10].

Tag: complexity.

Figure

../_images/realheapsort_step2.png

Source code

model main {

  var N, j, k, m, tmp;

  states start, lbl_20_1, lbl_21_1, lbl_4_3, stop;

  transition t_79 := {
    from   := start;
    to     := lbl_20_1;
    guard  := 4 <= N;
    action := j' = 2, k' = 0, m' = 2;
  };

  transition t_78 := {
    from   := start;
    to     := lbl_21_1;
    guard  := 4 <= N;
    action := j' = N, k' = 0, m' = 2;
  };

  transition t_77 := {
    from   := start;
    to     := lbl_20_1;
    guard  := 3 <= N;
    action := j' = 1, k' = 0, m' = 1;
  };

  transition t_76 := {
    from   := start;
    to     := lbl_21_1;
    guard  := 3 <= N;
    action := j' = N, k' = 0, m' = 1;
  };

  transition t_51 := {
    from   := start;
    to     := stop;
    guard  := N <= 2;
    action := ;
  };

  transition t_63 := {
    from   := lbl_20_1;
    to     := lbl_21_1;
    guard  := 2 * j + k + 4 <= N;
    action := j' = N, m' = 2 * j + 2;
  };

  transition t_61 := {
    from   := lbl_20_1;
    to     := lbl_21_1;
    guard  := 2 * j + k + 3 <= N;
    action := j' = N, m' = 2 * j + 1;
  };

  transition t_60 := {
    from   := lbl_20_1;
    to     := lbl_4_3;
    guard  := N <= 2 * j + k + 2;
    action := k' = k + 1, tmp' = k;
  };

  transition t_64 := {
    from   := lbl_20_1;
    to     := lbl_20_1;
    guard  := 2 * j + k + 4 <= N;
    action := j' = 2 * j + 2, m' = 2 * j + 2;
  };

  transition t_62 := {
    from   := lbl_20_1;
    to     := lbl_20_1;
    guard  := 2 * j + k + 3 <= N;
    action := j' = 2 * j + 1, m' = 2 * j + 1;
  };

  transition t_69 := {
    from   := lbl_21_1;
    to     := lbl_20_1;
    guard  := 2 * j + k + 4 <= N;
    action := j' = 2 * j + 2, m' = 2 * j + 2;
  };

  transition t_67 := {
    from   := lbl_21_1;
    to     := lbl_20_1;
    guard  := 2 * j + k + 3 <= N;
    action := j' = 2 * j + 1, m' = 2 * j + 1;
  };

  transition t_65 := {
    from   := lbl_21_1;
    to     := lbl_4_3;
    guard  := N <= 2 * j + k + 2;
    action := k' = k + 1, tmp' = k;
  };

  transition t_68 := {
    from   := lbl_21_1;
    to     := lbl_21_1;
    guard  := 2 * j + k + 4 <= N;
    action := j' = N, m' = 2 * j + 2;
  };

  transition t_66 := {
    from   := lbl_21_1;
    to     := lbl_21_1;
    guard  := 2 * j + k + 3 <= N;
    action := j' = N, m' = 2 * j + 1;
  };

  transition t_74 := {
    from   := lbl_4_3;
    to     := lbl_20_1;
    guard  := k + 4 <= N;
    action := j' = 2, m' = 2;
  };

  transition t_73 := {
    from   := lbl_4_3;
    to     := lbl_21_1;
    guard  := k + 4 <= N;
    action := j' = N, m' = 2;
  };

  transition t_72 := {
    from   := lbl_4_3;
    to     := lbl_20_1;
    guard  := k + 3 <= N;
    action := j' = 1, m' = 1;
  };

  transition t_71 := {
    from   := lbl_4_3;
    to     := lbl_21_1;
    guard  := k + 3 <= N;
    action := j' = N, m' = 1;
  };

  transition t_56 := {
    from   := lbl_4_3;
    to     := stop;
    guard  := N <= k + 1;
    action := ;
  };

  transition t_70 := {
    from   := lbl_4_3;
    to     := lbl_4_3;
    guard  := k + 2 = N;
    action := j' = 0, k' = k + 1, m' = 0, tmp' = k;
  };

}

strategy main_s {

  Region init := {state = start};

}

Expected invariant

{ lbl_20_1[v1, v2, v3, v2, v5] : v3 >= 0 and v3 <= -2 + v1 - v2 and v2 >= 1; lbl_21_1[v1, v1, v3, v4, v5] : v3 >= 0 and v4 <= -2 + v1 - v3 and v4 >= 1; lbl_4_3[v1, v2, v3, v4, -1 + v3] : 3v4 >= 3 - v1 + v2 and v4 <= -1 + v1 - v3 and v4 >= -1 + v1 - v2 - v3 and v3 >= 1 and v4 <= v2 and v2 <= v1 }

Results

  • With Aspic: { start[N, j, k, m, tmp]; lbl_21_1[N, N, k, m, tmp] : m >= 1 and k >= 0 and m <= -2 + N - k; lbl_4_3[N, j, k, m, -1 + k] : m >= -1 + N - j - k and k >= 1 and m >= 2 - k and m <= j and j <= N and 3m >= 3 - N + j and m <= -1 + N - k; stop[N, j, k, m, tmp]; lbl_20_1[N, j, k, j, tmp] : j >= 1 and k >= 0 and k <= -2 + N - j } (0.20s), OK.
  • With ISL: timeout.

«  Model realheapsort_step1   ::   Contents   ::   Model realselect  »