Clock (model checking)
≈ 6 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 subfield of computer science, a clock is a mathematical object used to model time. More precisely, a clock measures how much time passed since a particular event occurs, in this sense, a clock is more precisely an abstraction of a stopwatch. In a model of some particular program, the value of the clock may either be the time since the program was started, or the time since a particular event occurred in the program. Those clocks are used in the definition of timed automaton, signal automaton, timed propositional temporal logic and clock temporal logic. They are also used in programs such as UPPAAL which implement timed automata. Generally, the model of a system uses many clocks. Those multiple clocks are required in order to track a bounded number of events. All of those clocks are synchronized. That means that the difference in value between two fixed clocks is constant until one of them is restarted. In the language of electronics, it means that clock's jitter is null.
In model checking, a subfield of computer science, a clock is a mathematical object used to model time. More precisely, a clock measures how much time passed since a particular event occurs, in this sense, a clock is more precisely an abstraction of a stopwatch. In a model of some particular program, the value of the clock may either be the time since the program was started, or the time since a particular event occurred in the program. Those clocks are used in the definition of timed automaton, signal automaton, timed propositional temporal logic and clock temporal logic. They are also used in programs such as UPPAAL which implement timed automata. Generally, the model of a system uses many clocks. Those multiple clocks are required in order to track a bounded number of events. All of those clocks are synchronized. That means that the difference in value between two fixed clocks is constant until one of them is restarted. In the language of electronics, it means that clock's jitter is null. A clock valuation or clock interpretation \nu over X=\{x_1,\dots,x_n\} is usually defined as a function from X to the set of non-negative reals. Equivalently, a valuation can be considered as a point in \mathbb R_{\ge0}^n . The initial assignment \nu_0 is the constant function sending each clock to 0. Intuitively, it represents the initial time of the program, where all clocks are initialized simultaneously. Given a clock assignment \nu , and a real t\ge0 , \nu+t denotes the clock assignment sending each clock x\in C to \nu(x)+t . Intuitively, it represents the valuation \nu after which t time units passed. Given a subset r\subseteq C of clocks, \nu[r\rightarrow 0] denotes the assignment similar to \nu in which the clocks of r are reset. Formally, \nu[r\rightarrow 0] sends each clock x\in r to 0 and each clock x\not\in r to \nu(x) . When allowing for inactive clocks, a valuation may associate a clock x to some special value \bot to indicate that it is inactive. If \nu(x)=\bot then (\nu+t)(x) also equals \bot . An atomic clock constraint is simply a term of the form x\sim c , where x is a clock, \sim is a comparison operator, such as <, ≤, = ≥, or >, and c\in\mathbb N is an integral constant. In our previous example, we may use the atomic clock constraints c_i\le180 to state that the person at floor i waited for less than three minutes, and s>15 to state that the elevator stayed at some floor for more than fifteen seconds. A valuation \nu satisfies an atomic clock valuation x\sim c if and only if \nu(x)\sim c . A clock constraint is either a finite conjunction of atomic clock constraint or is the constant "true" (which can be considered as the empty conjunction). A valuation \nu satisfies a clock constraint \bigwedge_{i=1}^nx_i\sim_ic_i if it satisfies each atomic clock constraint x_i\sim_ic_i . Depending on the context, an atomic clock constraint may also be of the form x_i\sim x_j+c . Such a constraint is called a diagonal constraint, because x_1=x_2+c defines a diagonal line in \mathbb R_{\ge0}^2 . Allowing diagonal constraints may allow to decrease the size of a formula or of an automaton used to describe a system. However, algorithm's complexity may increase when diagonal constraints are allowed. In most system using clocks, allowing diagonal constraint does not increase the expressivity of the logic. We now explain how to encode such a constraint with Boolean variables and non-diagonal constraints. A diagonal constraint x_i\sim x_j+c may be simulated using non-diagonal constraints as follows. When x_j is reset, check whether x_i\sim c holds or not. Recall this information in a Boolean variable b_{i,j,c} and replace x_i\sim x_j+c by this variable. When x_i is reset, set b_{i,j,c} to true if \sim is < or ≤ or if \sim is = and c=0 . The way to encode a Boolean variable depends on the system which uses the clock. For example, UPPAAL supports Boolean variables directly. Timed automata and signal automata can encode a Boolean value in their locations. In clock temporal logic over timed words, the Boolean variable may be encoded using a new clock x_{i,j,c} , whose value is 0 if and only if b_{i,j,c} is false. That is, x_{i,j,c} is reset as long as x_{i,j,c} is supposed to be false. In timed propositional temporal logic, the formula x_i.\phi , which restart x_i and then evaluates \phi , can be replaced by the formula x_i.((x_i\sim x_j+c\implies\phi_\top)\land(\neg x_i\sim x_j+c\implies\phi\bot)) , where \phi_\top and \phi_\bot are copies of the formulas \phi , where x_i\sim x_j+c are replaced by the true and false constant respectively.
Text derived from https://en.wikipedia.org/w/index.php?oldid=1318179231 under CC BY-SA 4.0; modifications have been made.