Widening (computer science)
In computer science, especially model checking and abstract interpretation, widening refers to at least two different techniques in the analysis of abstract transition systems where infinite progressions of abstract states are replaced by a (computed or guessed) least fixed point. The use of the term in "model checking" is closely related to "acceleration" techniques, some authors reserving "acceleration" for exact computations. 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. 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 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