HOME
*





Clock (model Checking)
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 ...
[...More Info...]      
[...Related Items...]     OR:     [Wikipedia]   [Google]   [Baidu]  


picture info

Model Checking
In computer science, model checking or property checking is a method for checking whether a finite-state model of a system meets a given specification (also known as correctness). This is typically associated with hardware or software systems, where the specification contains liveness requirements (such as avoidance of livelock) as well as safety requirements (such as avoidance of states representing a system crash). In order to solve such a problem algorithmically, both the model of the system and its specification are formulated in some precise mathematical language. To this end, the problem is formulated as a task in logic, namely to check whether a structure satisfies a given logical formula. This general concept applies to many kinds of logic and many kinds of structures. A simple model-checking problem consists of verifying whether a formula in the propositional logic is satisfied by a given structure. Overview Property checking is used for verification when two d ...
[...More Info...]      
[...Related Items...]     OR:     [Wikipedia]   [Google]   [Baidu]  


picture info

Logical Conjunction
In logic, mathematics and linguistics, And (\wedge) is the truth-functional operator of logical conjunction; the ''and'' of a set of operands is true if and only if ''all'' of its operands are true. The logical connective that represents this operator is typically written as \wedge or . A \land B is true if and only if A is true and B is true, otherwise it is false. An operand of a conjunction is a conjunct. Beyond logic, the term "conjunction" also refers to similar concepts in other fields: * In natural language, the denotation of expressions such as English "and". * In programming languages, the short-circuit and control structure. * In set theory, intersection. * In lattice theory, logical conjunction ( greatest lower bound). * In predicate logic, universal quantification. Notation And is usually denoted by an infix operator: in mathematics and logic, it is denoted by \wedge, or ; in electronics, ; and in programming languages, &, &&, or and. In ...
[...More Info...]      
[...Related Items...]     OR:     [Wikipedia]   [Google]   [Baidu]  


Timed Propositional Temporal Logic
In model checking, a field of computer science, timed propositional temporal logic (TPTL) is an extension of propositional linear temporal logic (LTL) in which variables are introduced to measure times between two events. For example, while LTL allows to state that each event ''p'' is eventually followed by an event ''q'', TPTL furthermore allows to give a time limit for ''q'' to occur. Syntax The future fragment of TPTL is defined similarly to linear temporal logic, in which furthermore, clock variables can be introduced and compared to constants. Formally, given a set X of clocks, MTL is built up from: * a finite set of propositional variables ''AP'', * the logical operators ¬ and ∨, and * the temporal modal operator U, * a clock comparison x\sim c, with x\in X, c a number and \sim a comparison operator such as <, ≤, =, ≥ or >. * a freeze quantification operator x.\phi, for \phi a TPTL formula with set of clocks X\cup\. Furthermore, for I=(a,b) an interval, x\ ...
[...More Info...]      
[...Related Items...]     OR:     [Wikipedia]   [Google]   [Baidu]  


picture info

Clock Temporal Logic
A clock or a timepiece is a device used to measure and indicate time. The clock is one of the oldest human inventions, meeting the need to measure intervals of time shorter than the natural units such as the day, the lunar month and the year. Devices operating on several physical processes have been used over the millennia. Some predecessors to the modern clock may be considered as "clocks" that are based on movement in nature: A sundial shows the time by displaying the position of a shadow on a flat surface. There is a range of duration timers, a well-known example being the hourglass. Water clocks, along with the sundials, are possibly the oldest time-measuring instruments. A major advance occurred with the invention of the verge escapement, which made possible the first mechanical clocks around 1300 in Europe, which kept time with oscillating timekeepers like balance wheels., pp. 103–104., p. 31. Traditionally, in horology, the term ''clock'' was used for a strik ...
[...More Info...]      
[...Related Items...]     OR:     [Wikipedia]   [Google]   [Baidu]  


picture info

Signal Automaton
In automata theory, a field of computer science, a signal automaton is a finite automaton extended with a finite set of real-valued clocks. During a run of a signal automaton, clock values increase all with the same speed. Along the transitions of the automaton, clock values can be compared to integers. These comparisons form guards that may enable or disable transitions and by doing so constrain the possible behaviors of the automaton. Further, clocks can be reset. Example Before formally defining what a signal automaton is, an example will be given. Let one consider the language \mathcal L of signals, over a binary alphabet \, which contains signals \gamma such that: * A appears in singular intervals. That is, the set of times \ is discrete, and * A appears at least once during each interval of length one. This language can be accepted by the automaton pictured nearby. As for finite automaton, incoming arrows represents initial locations and double circle represents acceptin ...
[...More Info...]      
[...Related Items...]     OR:     [Wikipedia]   [Google]   [Baidu]  


picture info

Timed Automaton
In automata theory, a timed automaton is a finite automaton extended with a finite set of real-valued clocks. During a run of a timed automaton, clock values increase all with the same speed. Along the transitions of the automaton, clock values can be compared to integers. These comparisons form guards that may enable or disable transitions and by doing so constrain the possible behaviors of the automaton. Further, clocks can be reset. Timed automata are a sub-class of a type hybrid automata. Timed automata can be used to model and analyse the timing behavior of computer systems, e.g., real-time systems or networks. Methods for checking both safety and liveness properties have been developed and intensively studied over the last 20 years. It has been shown that the state reachability problem for timed automata is decidable,Rajeev Alur, David L. Dill. 199A Theory of Timed Automata In Theoretical Computer Science, vol. 126, 183–235, pp. 194–1955 which makes this an interesting s ...
[...More Info...]      
[...Related Items...]     OR:     [Wikipedia]   [Google]   [Baidu]  


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. ...
[...More Info...]      
[...Related Items...]     OR:     [Wikipedia]   [Google]   [Baidu]  


picture info

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 emptyness, 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. Zone A difference bound matrix is used to represents some kind of convex polytopes. Those polytopes are called zone. They are now defined. Formally, a zone is defined by equations 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 ...
[...More Info...]      
[...Related Items...]     OR:     [Wikipedia]   [Google]   [Baidu]  


picture info

First-order Logic
First-order logic—also known as predicate logic, quantificational logic, and first-order predicate calculus—is a collection of formal systems used in mathematics, philosophy, linguistics, and computer science. First-order logic uses quantified variables over non-logical objects, and allows the use of sentences that contain variables, so that rather than propositions such as "Socrates is a man", one can have expressions in the form "there exists x such that x is Socrates and x is a man", where "there exists''"'' is a quantifier, while ''x'' is a variable. This distinguishes it from propositional logic, which does not use quantifiers or relations; in this sense, propositional logic is the foundation of first-order logic. A theory about a topic is usually a first-order logic together with a specified domain of discourse (over which the quantified variables range), finitely many functions from that domain to itself, finitely many predicates defined on that domain, and a set ...
[...More Info...]      
[...Related Items...]     OR:     [Wikipedia]   [Google]   [Baidu]  


picture info

Computer Science
Computer science is the study of computation, automation, and information. Computer science spans theoretical disciplines (such as algorithms, theory of computation, information theory, and automation) to practical disciplines (including the design and implementation of hardware and software). Computer science is generally considered an area of academic research and distinct from computer programming. Algorithms and data structures are central to computer science. The theory of computation concerns abstract models of computation and general classes of problems that can be solved using them. The fields of cryptography and computer security involve studying the means for secure communication and for preventing security vulnerabilities. Computer graphics and computational geometry address the generation of images. Programming language theory considers different ways to describe computational processes, and database theory concerns the management of repositories ...
[...More Info...]      
[...Related Items...]     OR:     [Wikipedia]   [Google]   [Baidu]  


Jitter
In electronics and telecommunications, jitter is the deviation from true periodicity of a presumably periodic signal, often in relation to a reference clock signal. In clock recovery applications it is called timing jitter. Jitter is a significant, and usually undesired, factor in the design of almost all communications links. Jitter can be quantified in the same terms as all time-varying signals, e.g., root mean square (RMS), or peak-to-peak displacement. Also, like other time-varying signals, jitter can be expressed in terms of spectral density. Jitter period is the interval between two times of maximum effect (or minimum effect) of a signal characteristic that varies regularly with time. Jitter frequency, the more commonly quoted figure, is its inverse. ITU-T G.810 classifies jitter frequencies below 10 Hz as wander and frequencies at or above 10 Hz as jitter. Jitter may be caused by electromagnetic interference and crosstalk with carriers of other signals. Jitte ...
[...More Info...]      
[...Related Items...]     OR:     [Wikipedia]   [Google]   [Baidu]