Skip to main content

Integer Polyhedra for Program Analysis: 5th International Conference, AAIM 2009, San Francisco, CA, USA, June 15-17, 2009. Proceedings

Charles, Philip and King, Andy and Howe, Jacob M. (2009) Integer Polyhedra for Program Analysis: 5th International Conference, AAIM 2009, San Francisco, CA, USA, June 15-17, 2009. Proceedings. In: Goldberg, Andrew and Zhou, Yunhong, eds. Algorithmic Aspects in Information and Management,. Lecture Notes in Computer Science, 5564 . Springer, pp. 85-99. ISBN 978-3-642-02157-2. (doi:10.1007/978-3-642-02158-9_9) (KAR id:37592)

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.

Item Type: Book section
DOI/Identification number: 10.1007/978-3-642-02158-9_9
Subjects: A General Works
Divisions: Divisions > Division of Computing, Engineering and Mathematical Sciences > School of Computing
Depositing User: Andy King
Date Deposited: 12 Dec 2013 21:39 UTC
Last Modified: 16 Nov 2021 10:14 UTC
Resource URI: https://kar.kent.ac.uk/id/eprint/37592 (The current URI for this page, for reference purposes)

University of Kent Author Information

  • Depositors only (login required):

Total unique views for this document in KAR since July 2020. For more details click on the image.