Lesson plan

Difference bound matrix

In model checking, a field of computer science, a difference bound matrix (DBM) is a data structure used to represent some convex polytopes called zones. This structure can be used to efficiently implement some geometrical operations over zones, such as testing emptiness, inclusion, equality, and computing the intersection and the sum of two zones. It is, for example, used in the Uppaal model checker; where it is also distributed as an independent library. More precisely, there is a notion of canonical DBM; there is a one-to-one relation between canonical DBMs and zones and from each DBM a canonical equivalent DBM can be efficiently computed. Thus, equality of zone can be tested by checking for equality of canonical DBMs.

Back to article

Article summary

In model checking, a field of computer science, a difference bound matrix (DBM) is a data structure used to represent some convex polytopes called zones. This structure can be used to efficiently implement some geometrical operations over zones, such as testing emptiness, inclusion, equality, and computing the intersection and the sum of two zones. It is, for example, used in the Uppaal model checker; where it is also distributed as an independent library. More precisely, there is a notion of canonical DBM; there is a one-to-one relation between canonical DBMs and zones and from each DBM a canonical equivalent DBM can be efficiently computed. Thus, equality of zone can be tested by checking for equality of canonical DBMs.

Key claims

No claims recorded.

Discussion questions

  1. Summarise the article in your own words. Which single claim would you verify first, and why?
  2. Which claim in this article is most likely to be revised as the sources update? How would you check its current status?
  3. If two sources disagreed about one of these facts, what would you need in order to trust one over the other?

Bibliography

No sources recorded.

Key claims and bibliography are generated from the same tracked claims and sources as the article page.