Numerical Power Analysis

By: Isabella Mastroeni

Isabella Mastroeni
Dip. di Informatica
Univ. di Verona
Strada Le Grazie a Ca' Vignal 2
I-37134 Verona, Italy


In this paper we design abstract domains for numerical power analysis. These domains are conceived to discover properties of the following type: `The integer (or rational) variable X at a given program point is the numerical power of c with the exponent having a given property P'', where c and P are automatically determined. A family of domains is presented, two of these consider that the exponent can be any natural or integer value, the others include also the analysis of properties of the exponent set. Relevant lattice-theoretic properties of these domains are proved such as the absence of infinite ascending chains and the structure of their meet-irreducible elements. These domains are applied in the analysis of integer powers of imperative programs and in the analysis of probabilistic concurrent programming, with probabilistic non-deterministic choice.
Related papers:
  • Algebraic Power Analysis by Abstract Interpretation (Submitted for publication, 2002)

  • Available: DVI, PostScript, BibTeX Entry.