New generation computing vol:13 issue:2 pages:117-154
We propose an automatic method for deriving linear size relations, which specify, with respect to some given norm, linear relationships between the sizes of the arguments of atoms in the least Herbrand model of a definite Horn clause program. The method is presented as an application of abstract interpretation. Its abstract domain consists of affine subspaces or linear varieties, and operations on elements of the domain are expressed in terms of operations from linear algebra. The main application of the technique is situated in automatic termination analysis. Others are complexity and granularity analysis and the specialisation of constraints in constraint logic languages.