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.
≈ 5 min read
Names in other languages
No names in other languages are held for this entry yet.
Article bodies are English and are not machine-translated. A name in another language is not a translation of the article.
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.
Given n variables, there are exactly n(n+1) different non-redundant constraints possible, n constraints which use a single variable and an upper bound, n constraints which uses a single variable and a lower bound, and for each of the n^2 ordered pairs of variable (x,y) , an upper bound on x-y . However, an arbitrary convex polytope in \mathbb R^n may require an arbitrarily great number of constraints. Even when n=2 , there can be an arbitrary great number of non-redundant constraints (x , for c_i some constants.
This is the reason why DBMs can not be extended from zones to convex polytopes. First, the set \{ is considered as an ordered set, with < being inferior to ≤.
Intuitively, this order is chosen because the set defined by x is strictly included in the set defined by x\le c . We then state that the constraint (\prec_1,m_1) is smaller than (\prec_2,m_2) if either m_1 or ( m_1=m_2 and \prec_1 is less than \prec_2 ). That is, the order on constraints is the lexicographical order applied from right to left. Note that this order is a total order.
If M has the least-upper-bound property (or greatest-lower-bound property) then the set of constraints also have it. The DBM \left(\begin{array}{ll}( also encodes the empty set. Indeed, it contains the constraints 0 and x_1\le -1 which are contradictory.
More generally, this show that, for each C,R\in\{0,x_1,\dots,x_n\} , if m_{C,R}=-m_{R,C} , then \prec_{R,C} and \prec_{C,R} are both equal to ≤. The DBM \left(\begin{array}{ll}( also encodes the empty set. Indeed, it contains the constraints 0\le x_1+1 and x_1\le -2 which are contradictory.
More generally, this show that for each C,R\in\{0,x_1,\dots,x_n\} , -m_{C,R}\le m_{R,C} , unless m_{C,R} is -\infty . Given a vector \vec x=(x_1,\dots,x_n) , and an index 1\le i\le n , the projection of the i -th component of \vec x to d is the vector (x_1,\dots,x_{i-1},d,x_{i+1},\dots,x_n) . In the language of clock, for d=0 , this corresponds to resetting the i -th clock.
Projecting the i -th component of a zone Z to d consists simply in the set of vectors of Z with their i -th component to d . This is implemented on DBM by setting the components (x_{i},a) to (\le,d)+D(0,a) and the components (a,x_{i}) to (\le,-d)+D(0,a) Let us call the future the zone F=\{(t,\dots,t)\mid t\in\mathbb R_{\ge0}\} and the past the zone P=\{(-t,\dots,-t)\mid t\in\mathbb R_{\ge0}\} . Given a point \vec x=(x_1,\dots,x_n)\in\mathbb R^n , the future of \vec x is defined as \{(x_1+t,\dots,x_n+t)\mid t\in\mathbb R_{\ge0}\}=F+\{\vec x\} , and the past of \vec x is defined as P+\{\vec x\} .
The names future and past comes from the notion of clock. If a set of n clocks are assigned to the values x_1 , x_2 , etc. then in their future, the set of assignment they'll have is the future of \vec x . Given a zone Z , the future of Z are the union of the future of each points of the zone. The definition of the past of a zone is similar.
The future of a zone can thus be defined as F+Z , and hence can easily be implemented as a sum of DBMs. However, there is even a simpler algorithm to apply to DBM. It suffices to change every entries (x_i,0) to ( .
Similarly, the past of a zone can be computed by setting every entries (0,x_i) to ( .
Text derived from https://en.wikipedia.org/w/index.php?oldid=1330540222 under CC BY-SA 4.0; modifications have been made.