© University of Kent - Contact | Feedback | Legal | FOI | Cookies
Integer Polyhedra for Program Analysis
Philip Charles, Jacob Howe, and Andy King
In Andrew Goldberg and Yunhong Zhou, editors, Proceedings of the Fifth International Conference on Algorithmic Aspects in Information and Management, Lecture Notes in Computer Science, pages 182-196. Springer-Verlag, June 2009.Abstract
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.
Download publication 283 kbytes (PDF)Bibtex Record
@inproceedings{2892,
author = {Philip Charles and Jacob Howe and Andy King},
title = {Integer {P}olyhedra for {P}rogram {A}nalysis},
month = {June},
year = {2009},
pages = {182-196},
keywords = {determinacy analysis, Craig interpolants},
note = {},
doi = {},
url = {http://www.cs.kent.ac.uk/pubs/2009/2892},
publication_type = {inproceedings},
submission_id = {4513_1238613304},
booktitle = {Proceedings of the Fifth International Conference on Algorithmic Aspects in Information and Management},
editor = {Andrew Goldberg and Yunhong Zhou},
series = {Lecture Notes in Computer Science},
publisher = {Springer-Verlag},
refereed = {yes},
}