In
computer science, especially
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 ...
and
abstract interpretation
In computer science, abstract interpretation is a theory of sound approximation of the semantics of computer programs, based on monotonic functions over ordered sets, especially lattices. It can be viewed as a partial execution of a computer prog ...
, widening refers to at least two different techniques in the analysis of abstract
transition system
In theoretical computer science, a transition system is a concept used in the study of computation. It is used to describe the potential behavior of discrete systems. It consists of states and transitions between states, which may be labeled wi ...
s where infinite progressions of abstract states are replaced by a (computed or guessed
[Ahmed Bouajjani and Tayssir Touili (2012), "Widening techniques for regular tree model checking", ''STTT'', Vol. 14, No. 2, pp. 145 -- 16]
/ref>) least fixed point. The use of the term in ''model checking'' is closely related to ''acceleration'' techniques, some authors reserving ''acceleration'' for exact computations.[Sébastien Bardin, Alain Finkel, Jérôme Leroux and Philippe Schnoebelen, ''Flat acceleration in symbolic model checking'' (2005), Automated Technology for Verification and Analysis, pp. 474--488, Springer]
Intuition
While many computer programs can be understood in terms of machine states and transitions (see formal semantics of programming languages), their state spaces may be too large to fully represent and analyse. Modern analysis techniques therefore try to reason about abstract states, which correspond to many concrete states.
Often, the abstract states are structured in such a way that by repeatedly following the effect of program steps or by coarsening the abstraction, one obtains a chain of abstractions that is proven to terminate.
Use in Model Checking
Widening techniques and the closely related ''acceleration'' techniques are used in the ''forward analysis'' of systems in the discipline of symbolic 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 syste ...
. The techniques detect cycles, i.e. sequences of abstract state transitions that could be repeated. When such a sequence can be repeated over and over, yielding new states (e.g. a variable might be incremented at every repetition), the symbolic analysis of the program will not explore all of these states in finite time. For several important families of systems such as pushdown systems Pushdown may refer to:
* Pushdown automaton, a concept in theoretical computer science
** More generally, anything relating to a stack
Stack may refer to:
Places
* Stack Island, an island game reserve in Bass Strait, south-eastern Australia, in ...
, channel systems
Channel, channels, channeling, etc., may refer to:
Geography
* Channel (geography), in physical geography, a landform consisting of the outline (banks) of the path of a narrow body of water.
Australia
* Channel Country, region of outback Austr ...
or counter systems
Counter may refer to:
Mathematics and computing
* Counter machine, a subclass of register machines
* Counter (digital), an electronic device, mechanical device, or computer program for counting
* Loop counter, the variable that controls the ite ...
, subclasses amenable to so-called ''flat acceleration'' have been identified for which a complete analysis procedure exists that computes the whole set of reachable states. This type of forward analysis is also related to well structured transition systems, but well-structuredness alone is not sufficient for such procedures to be complete (for example, the coverability graph of a Petri net is always finite but in general, it overapproximates the true state space).
Use in Abstract Interpretation
Cousot and Cousot
[Patrick Cousot and Radhia Cousot]
''Abstract Interpretation: Unified Lattice Model for Static Analysis of Programs by Construction or Approximation of Fixpoints'' (1977)
Conference Record of the Fourth Symposium on Principles of Programming Languages, Los Angeles, California, USA, January 1977, pp. 238 -- 252 have introduced a notion of widening while defining the framework of abstract interpretation
In computer science, abstract interpretation is a theory of sound approximation of the semantics of computer programs, based on monotonic functions over ordered sets, especially lattices. It can be viewed as a partial execution of a computer prog ...
. An example for the widening of an abstract domain that appears in abstract interpretation would be replacing the upper bound of an interval by .
References
{{reflist
Model checking