Bounded Fixed Point Iteration

Forfattere

  • Hanne Riis Nielson
  • Flemming Nielson

DOI:

https://doi.org/10.7146/dpb.v20i359.6589

Resumé

In the context of abstract interpretation for languages without higher-order features we study the number of times a functional need to be unfolded in order to give the least fixed point. For the cases of total or monotone functions we obtain an exponential bound and in the case of strict and additive (or distributive) functions we obtain a quadratic bound. These bounds are shown to be tight in that sufficiently long chains of functions can be shown to exist. Specializing the case of strict and additive functions to functionals of a form that would correspond to iterative programs we show that a linear bound is tight. This is related to several analyses studied in the literature (including strictness analysis).

Forfatterbiografier

Hanne Riis Nielson

Flemming Nielson

Downloads

Publiceret

1991-07-01

Citation/Eksport

Nielson, H. R., & Nielson, F. (1991). Bounded Fixed Point Iteration. DAIMI Report Series, 20(359). https://doi.org/10.7146/dpb.v20i359.6589