City Research Online

Integer polyhedra for program analysis

Charles, P. J., Howe, J. M. & King, A. (2009). Integer polyhedra for program analysis. Algorithmic Aspects in Information and Management, Lecture Notes in Computer Science, 5564, pp. 85-99. doi: 10.1007/978-3-642-02158-9_9


Polyhedra are widely used in model checking and abstract interpretation. Polyhedral analysis is effective when the relationships between variables are linear, but suffers from imprecision when it is necessary to take into account the integrality of the represented space. Imprecision also arises when non-linear constraints occur. Moreover, in terms of tractability, even a space defined by linear constraints can become unmanageable owing to the excessive number of inequalities. Thus it is useful to identify those inequalities whose omission has least impact on the represented space. This paper shows how these issues can be addressed in a novel way by growing the integer hull of the space and approximating the number of integral points within a bounded polyhedron.

Publication Type: Article
Additional Information: The final publication is available at Springer via
Subjects: Q Science > QA Mathematics > QA75 Electronic computers. Computer science
Departments: School of Science & Technology > Computer Science
[thumbnail of Integer_Polyhedra_for_Program_Analysis.pdf]
Text - Accepted Version
Download (290kB) | Preview


Add to AnyAdd to TwitterAdd to FacebookAdd to LinkedinAdd to PinterestAdd to Email


Downloads per month over past year

View more statistics

Actions (login required)

Admin Login Admin Login