Lesson plan

Region (model checking)

In model checking, a field of computer science, a region is a convex polytope in \mathbb R^d for some dimension d , and more precisely a zone, satisfying some minimality property. The regions partition \mathbb R^d . The set of zones depends on a set K of constraints of the form x\le c , x\ge c , x_1\le x_2+c and x_1\ge x_2+c , with x_1 and x_2 some variables, and c a constant. The regions are defined such that if two vectors \vec x and \vec x' belong to the same region, then they satisfy the same constraints of K . Furthermore, when those vectors are considered as a tuple of clocks, both vectors have the same set of possible futures. Intuitively, it means that any timed propositional temporal logic-formula, or timed automaton or signal automaton using only the constraints of K can not distinguish both vectors. The set of region allows to create the region automaton, which is a directed graph in which each node is a region, and each edge r\to r' ensure that r' is a possible future of r . Taking a product of this region automaton and of a timed automaton \mathcal A which accepts a language L creates a finite automaton or a Büchi automaton which accepts untimed L . In particular, it allows to reduce the emptiness problem for \mathcal A to the emptiness problem for a finite or Büchi automaton. This technique is used for example by the software UPPAAL.

Back to article

Article summary

In model checking, a field of computer science, a region is a convex polytope in \mathbb R^d for some dimension d , and more precisely a zone, satisfying some minimality property. The regions partition \mathbb R^d . The set of zones depends on a set K of constraints of the form x\le c , x\ge c , x_1\le x_2+c and x_1\ge x_2+c , with x_1 and x_2 some variables, and c a constant. The regions are defined such that if two vectors \vec x and \vec x' belong to the same region, then they satisfy the same constraints of K . Furthermore, when those vectors are considered as a tuple of clocks, both vectors have the same set of possible futures. Intuitively, it means that any timed propositional temporal logic-formula, or timed automaton or signal automaton using only the constraints of K can not distinguish both vectors. The set of region allows to create the region automaton, which is a directed graph in which each node is a region, and each edge r\to r' ensure that r' is a possible future of r . Taking a product of this region automaton and of a timed automaton \mathcal A which accepts a language L creates a finite automaton or a Büchi automaton which accepts untimed L . In particular, it allows to reduce the emptiness problem for \mathcal A to the emptiness problem for a finite or Büchi automaton. This technique is used for example by the software UPPAAL.

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.