The University of Arizona
banner image

  Understanding Finiteness Analysis using Abstract Interpretation

Peter Bigot   Saumya Debray   Kim Marriott
 

Abstract
Finiteness analyses are compile-time techniques to determine (sufficient) conditions for the finiteness of relations computed during the bottom-up execution of a logic program. We examine finiteness analyses from the perspective of abstract interpretation. However, problems arise when trying to use standard abstract interpretation theory for finiteness analysis. They occur because finiteness is not an admissible property and so naive application of abstract interpretation leads to incorrect analyses. Here we develop three simple techniques based on abstract interpretation theory which allow inadmissible properties to be handled. Existing approaches to finiteness analysis may be explained and compared in terms of our extension to abstract interpretation theory, and we claim that their correctness is more easily argued in it. To support our claim we use our techniques to develop and prove correct a finiteness analysis which is more accurate than any that we are aware of.