Widening (computer science)

Widening techniques and the closely related acceleration techniques are used in the forward analysis of systems in the discipline of symbolic model checking. 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, channel systems or counter systems, subclasses amenable to so-called flat acceleration have been identified^[2] 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).

Cousot and Cousot ^[3] have introduced a notion of widening while defining the framework of abstract interpretation. An example for the widening of an abstract domain that appears in abstract interpretation^[4][5] would be replacing the upper bound of an interval by ${\displaystyle \infty }$.