Region (model checking)

Uses your system voice; voice and rate in settings.

Snapshot

≈ 9 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 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.

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. Let C=\{x_1,\dots,x_d\} a set of clocks. For each x\in\mathbb N let c_x\in\mathbb N . Intuitively, this number represents an upper bound on the values to which the clock x can be compared. The definition of a region over the clocks of C uses those numbers c_x 's. Three equivalent definitions are now given. Given a clock assignment \nu , [\nu] denotes the region in which \nu belongs. The set of regions is denoted by \mathcal R . \nu_1(x)\sim c iff \nu_2(x)\sim c , for each x\in C and 0\le c\le c_x an integer, and ~ being one of the following relation =, < or ≤. \{\nu_1(x)\}\sim \{\nu_1(y)\} iff \{\nu_2(x)\}\sim \{\nu_2(y)\} , for each x,y\in C , \nu_1(x)\le c_x , \nu_1(y)\le c_y , \{r\} being the fractional part of the real r , and ~ being one of the following relation =, < or ≤. The first kind of constraints ensures that \nu_1 and \nu_2 satisfies the same constraints. Indeed, if \nu_1(x)=0.5 and \nu_2(x)=1 , then only the second assignment satisfies x=1 . On the other hand, if \nu_1(x)=0.5 and \nu_2(x)=0.6 , both assignment satisfies exactly the same set of constraint, since the constraints use only integral constants. The second kind of constraints ensures that the future of two assignments satisfy the same constraints. For example, let \nu_1=\{x\mapsto 0.5, y\mapsto 0.6\} and \nu_2=\{x\mapsto 0.5, y\mapsto 0.4\} . Then, the constraint y=1\land x is eventually satisfied by the future of \nu_1 without clock reset, but not by the future of \nu_2 without clock reset. x=c for some integer 0\le c\le c_x x\in(c,c+1) for some integer 0\le c , x> c_x , furthermore, for each pair of clocks x,y\in C , where S contains constraints of the form x\in (c,c+1) and y\in (c',c'+1) , then S contains an (in) equality of the form \{x\}\sim \{y\} with \sim being either =, < or ≤. Since, when c and c' are fixed, the last constraint is equivalent to x\sim y+c-c' . This definition allow to encode a region as a data structure. It suffices, for each clock, to state to which interval it belongs and to recall the order of the fractional part of the clocks which belong in an open interval of length 1. It follows that the size of this structure is O\left(\sum\log(c_k)+|C|\log(|C|)\right) with |C| the number of clocks. the constraints x=0 for x\in C' . The set of assignments defined by \alpha[C'\mapsto 0] is exactly the set of assignments \nu[C'\mapsto0] for \nu\in\alpha . Note that it does not mean that \alpha+t_{\nu,\alpha'}=\alpha' . For example, the region \alpha defined by the set of constraint \{0 has the time-successor \alpha' defined by the set of constraint \{0 . Indeed, for each \nu\in\alpha , it suffices to take t_{\nu,\alpha'}=1-\nu(y) . However, there exists no real t such that \alpha+t=\alpha' or even such that \alpha+t\subseteq\alpha' ; indeed, \alpha defines a triangle while \alpha' defines a segment. Given a region \alpha defined as a set of constraints S , let us define its set of time-successors. In order to do so, the following variables are required. Let T\subseteq S the set of constraints of S of the form x_i=c_i . Let Y\subseteq C the set of clocks y such that S contains the constraint y>c_y . Let Z\subseteq C\setminus Y the set of clocks \{z\} such that there are no constraints of the form \{x\} in S . If T is empty, \alpha is its own time successor. If Y=C , then \alpha is the only time-successor of \alpha . Otherwise, there is a least time-successor of \alpha not equal to \alpha . The least time-successor, if T is non-empty, contains: the constraints of S\setminus T x_i>c_i , \{x_i\}=\{x_j\} , and for each y such that y>c_y does not belong to S , the constraint x_i . If T is empty, the least time-successor is defined by the following constraints: the constraints of S not using the clocks of Z , the constraint z=c+1 , for each constraint c in S , with z\in Z . its root is the initial region \alpha_0 , defined by the set of constraints \{x=0\mid x\in C\} , the set of edges are (\alpha,\alpha'[C'\mapsto 0]) , for \alpha' a time-successor of \alpha . Let \mathcal A=\langle \Sigma,L,L_0,C,F,E\rangle a timed automaton. For each clock x\in C , let c_x the greatest number c such that there exists a guard of the form x\sim c in \mathcal A . The region automaton of \mathcal A , denoted by R(\mathcal A) is a finite or Büchi automaton which is essentially a product of \mathcal A and of the region graph defined above. That is, each state of the region automaton is a pair containing a location of \mathcal A and a region. Since two clocks assignment belonging to the same region satisfies the same guard, each region contains enough information to decide which transitions can be taken. Formally, the region automaton is defined as follows: its alphabet is \Sigma , its set of states is L\times\mathcal R , its set of states is L_0\times\{\alpha_0\} with \alpha_0 the initial region, its set of accepting states is F\times\mathcal R , its transition relation \delta contains ((\ell,\alpha),a,(\ell',\alpha'[C'\mapsto0])) , for (\ell,a,g,C',\ell')\in E , such that \gamma\models\alpha' and \alpha' is a time-successor of \alpha . Given any run r=(\ell_0,\nu_0)\xrightarrow[t_1]{\sigma_1}(\ell_1,\nu_1)\dots of \mathcal A , the sequence (\ell_0,[\nu_0])\xrightarrow{\sigma_1}(\ell_1,[\nu_1])\dots is denoted [r] , it is a run of R(\mathcal A) and is accepting if and only if r is accepting . It follows that L(R(\mathcal A))=\operatorname{Untime}(L(\mathcal A)) . In particular, \mathcal A accepts a timed-word if and only if R(\mathcal A) accepts a word. Furthermore, an accepting run of \mathcal A can be computed from an accepting run of R(\mathcal A) .

Text derived from https://en.wikipedia.org/w/index.php?oldid=1314950907 under CC BY-SA 4.0; modifications have been made.

Sources cited in this revision

2 named source(s) extracted from the cited revision. A source with no author is shown by its publication; nothing is invented.