ALICe documentation

Model slam

«  Model sipmabubble   ::   Contents   ::   Model slam_bad  »

Model slam

Cited in: [GulavaniHKNR06] fig. 3 p. 5, [GulwaniJK09] fig. 10d p. 10, [GulwaniZ10] fig. 9 p. 12, [HenzingerJMS02] fig. 1 p. 2.

Tag: termination.

Figure

../_images/slam.png

Source code

model gulavani_henzinger_kannan_nori_rajamani_sigsoft06_05 {

  var lock_state, x, y;

  states q1, q2, q3, q4;

  transition t1 := {
    from   := q1;
    to     := q2;
    guard  := true;
    action := lock_state' = 0, x' = y;
  };

  transition t3 := {
    from   := q2;
    to     := q3;
    guard  := true;
    action := ;
  };

  transition t2 := {
    from   := q2;
    to     := q3;
    guard  := true;
    action := lock_state' = 1, y' = y + 1;
  };

  transition t5 := {
    from   := q3;
    to     := q4;
    guard  := x = y;
    action := ;
  };

  transition t4 := {
    from   := q3;
    to     := q2;
    guard  := x != y;
    action := ;
  };

}

strategy gulavani_henzinger_kannan_nori_rajamani_sigsoft06_05_s {

  Region init := {state = q1 && lock_state = 1};

}

Expected invariant

{ q4[0, v2, v3] }

Results

  • With Aspic: { q3[lock_state, x, y] : lock_state <= 1; q4[lock_state, x, x] : lock_state <= 1; q2[lock_state, x, y] : lock_state <= 1; q1[1, x, y] } (0.08s), failed.
  • With ISL: { q3[1, x__1, y__1] : y__1 >= 1 + x__1; q3[1, x__1, 1 + x__1]; q3[0, x__1, x__1]; q2[1, x__1, y__1] : y__1 >= 1 + x__1 or y__1 >= 1 + x__1; q2[0, x__1, x__1]; q4[0, x__1, x__1]; q1[1, x, y] } (0.08s), OK.

«  Model sipmabubble   ::   Contents   ::   Model slam_bad  »