SEMANTICS (Q1,'06)
[ semantics | relevance | roles | structure | schedule | exercises | project | materials | classes | webboard ]

EXERCISE 1 (EQUIVALENCE RELATIONS)

Purpose: to understand the concept of an equivalence relation.
  • -) Which of the following relations are equivalence relations (i.e., reflexive, symmetric, and transitive) and which are not (and why not):

  • a) The "less-than-or-equal-to" relation: '<='

  • b) The almost-total-relation-on-integers, relating all numbers (except 42, but relating 42 with 42): '{ (n,m) | n,m in ( Z \ {42} ) } union { (42,42) }'

  • c) The "is-congruent-modulo-three" relation: '{ (n,m) | (n % 3) == (m % 3) }'

  • d) The "has-talked-with" relation: '{ (p,q) | p and q have talked together }'

  • e) The "is-in-the-same-exercise-class-as" relation: '{ (p,q) | p and q are in same exercise class }'

NOTE

  • I didn't have sufficient time to really cover enough bisimulation and bisimilarity for you to do the following exercises comfortably, but try to see if you can figure them out (with help from your TAs). Then, next week I'll tell you more about it all.

  • You can also spend the time on old exercises you didn't cover.

EXERCISE PRE-2

  • Read the rest of the slides that I didn't cover: [slides #27 - ...] before engaging exercises 2 and 3 (below).

EXERCISE 2 (STRONG BISIMULATIONS and STRONG BISIMILARITY)

Purpose: Strong bisimulations and strong bisimilarity.
  • -) Consider the following labelled transition systems:

  • a) Show that s ~ t by finding a strong bisimulation R containing the pair (s,t)

  • b) Discuss the general relationship to CCS processes (i.e. how does knowledge about relationships between two LTS transition diagrams affect our understanding of CCS processes).

EXERCISE 3 (STRONG BISIMULATIONS and THE STRONG BISIMULATION GAME)

Purpose: Strong bisimulations and the strong bisimulation game.
  • -) Consider the following labelled transition systems:

  • -) Decide whether the states(/processes) mentioned below are strongly bisimilar? Support your claim by giving a univeral winning strategy either for the attacker (in the negative case) or the defender (in the positive case). In the positive case, you can also exhibit a strong bisimulation relating the states.

  • a) s ~ t?

  • b) s ~ u?

  • c) s ~ v?

Claus Brabrand (October 5, 2006)