To Infinity... and Beyond!Report as inadecuate




To Infinity... and Beyond! - Download this document for free, or read online. Document in PDF available to download.

1 ANTIQUE - Analyse Statique par Interprétation Abstraite DI-ENS - Département d-informatique de l-École normale supérieure, Inria Paris-Rocquencourt

Abstract : The traditional method for proving program termination consists in inferring a ranking function. In many cases i.e. programs with unbounded non-determinism, a single ranking function over natural numbers is not sufficient. Hence, we propose a new abstract domain to automatically infer ranking functions over ordinals. We extend an existing domain for piecewise-defined natural-valued ranking functions to polynomials in ω, where the polynomial coefficients are natural-valued functions of the program variables. The abstract domain is parametric in the choice of the state partitioning inducing the piecewise-definition and the type of functions used as polynomial coefficients. To our knowledge this is the first abstract domain able to reason about ordinals. Handling ordinals leads to a powerful approach for proving termination of imperative programs, which in particular allows us to take a first step in the direction of proving termination under fairness constraints and proving liveness properties of sequential and concurrent programs.

Keywords : Ordinals Ranking Function Termination Abstract Interpretation





Author: Caterina Urban - Antoine Miné -

Source: https://hal.archives-ouvertes.fr/



DOWNLOAD PDF




Related documents