In
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 syst ...
, a subfield of
computer science
Computer science is the study of computation, information, and automation. Computer science spans Theoretical computer science, theoretical disciplines (such as algorithms, theory of computation, and information theory) to Applied science, ...
, a signal or timed state sequence is an extension of the notion of words in a
formal language
In logic, mathematics, computer science, and linguistics, a formal language is a set of strings whose symbols are taken from a set called "alphabet".
The alphabet of a formal language consists of symbols that concatenate into strings (also c ...
, in which letters are continuously emitted. While a word is traditionally defined as a function from a set of non-negative integers to letters, a signal is a function from a set of real numbers to letters. This allow the use of formalisms similar to the ones of
automata theory
Automata theory is the study of abstract machines and automata, as well as the computational problems that can be solved using them. It is a theory in theoretical computer science with close connections to cognitive science and mathematical l ...
to deal with continuous signals.
Example
Consider an elevator. What is formally called a letter could be in fact information such as "someone is pressing the button on the 2nd floor", or "the doors are currently open on the third floor". In this case, a signal indicates, at each time, which is the current state of the elevator and its buttons. The signal can then be analyzed using
formal methods
In computer science, formal methods are mathematics, mathematically rigorous techniques for the formal specification, specification, development, Program analysis, analysis, and formal verification, verification of software and computer hardware, ...
to check whether a property such that "each time the elevator is called, it arrives in less than three minutes, assuming that no one held the door for more than fifteen seconds" holds. A statement such as this one is usually expressed in
metric temporal logic, an extension of
linear temporal logic
In logic, linear temporal logic or linear-time temporal logic (LTL) is a modal logic, modal temporal logic with modalities referring to time. In LTL, one can encode formula (logic), formulae about the future of path (graph theory), paths, e.g., a c ...
that allows the expression of time constraints.
A signal may be passed to a model, such as a
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 ...
, which will decide, given the letters or actions that already occurred, what is the next action that should be performed, in our example, to which floor the elevator must go. Then a program may test this signal and check the above-mentioned property. That is, it will try to generate a signal in which the door is never held open for more than fifteen seconds, and in which a user must wait more than three minutes after calling the elevator.
Definition
Given an
alphabet
An alphabet is a standard set of letter (alphabet), letters written to represent particular sounds in a spoken language. Specifically, letters largely correspond to phonemes as the smallest sound segments that can distinguish one word from a ...
''A'', a signal
is a sequence
, finite or infinite, such that
, each
are pairwise disjoint intervals,
, and
is also an interval. Given
for some
,
represents
.
Properties
Some authors restrict the kind of signals they consider. We list here some standard properties that a signal may or may not satisfy.
Finite variability
Intuitively, a signal is said to be finitely variable, or to have the finite variability property, if during each bounded interval, the letter change a finite number of times. In our previous elevator example, this property would mean that a user may only press a button a finite number of times during a finite time. And similarly, in a finite time, the elevator can only open and close its door a finite number of times.
Formally, a signal is said to have the finite variability property, unless the sequence is infinite and
is bounded. Intuitively, the finite variability property states that there is not an infinite number of changes in a finite time. Having the finite variability property is similar to the notion of being non-Zeno for a
timed word.
Bounded variability
The notion of bounded variability is a restriction to the notion of finite variability. A signal has the bounded variability property if there exists a lower bound between the beginning of two intervals with the same letter.
Before giving a formal definition, we give an example of signal which
is finitely variable but not boundedly variable. Take the alphabet
. Take the interval
which sends the reals of the form
with
and
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 ...
, which need to recall everything which occurred in the last time units. If we know that the signal is boundedly variable, we can compute an upper bound on the number of action which occurred during one time unit. Thus, we can create such a system and ensure that it only requires a finite memory.
For example, for an arbitrary predicate
e, the signal stating whether the statement "
p holds sometime in the next time unit" holds has the bounded variability property. Indeed, when this statement becomes true, it remains true for a full time unit. Thus the difference between two occurrences where this statement becomes true is greater than a time unit.
Bipartite signal
A signal is said to be ''bipartite'' if the sequence of intervals start with a singular interval – i.e. a closed interval whose lower and upper bound are equal, hence a set which is a singleton. And if the sequence alternate between singular intervals and open intervals.
Each signal is equivalent to a bipartite signal. Indeed, any interval which is closed on the left is the union of a singular interval and of an interval open on the left, in this order. And similarly for intervals closed on the right.
A
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 ...
reading a bipartite signal has a special form. Its set of locations can be partitioned into locations for singular interval, and locations for open intervals. Each transition goes from a singular location to an open one and reciprocally.
See also
*
Timed word
References
*
{{DEFAULTSORT:Model Checking
*