School of Computing

Polyhedral Analysis using Parametric Objectives

Jacob M. Howe and Andy King

In Antoine Min'e and David A. Schmidt, editors, Nineteenth Static Analysis Symposium, volume 7460 of Lecture Notes in Computer Science, pages 41-57. Springer, September 2012 ARCoSS subline.

Abstract

The abstract domain of polyhedra lies at the heart of many program analysis techniques. However, its operations can be expensive, precluding their application to polyhedra that involve many variables. This paper describes a new approach to computing polyhedral domain operations. The core of this approach is an algorithm to calculate variable elimination (projection) based on parametric linear programming. The algorithm enumerates only non-redundant inequalities of the projection space, hence permits anytime approximation of the output.

Download publication 227 kbytes (PDF)

Bibtex Record

@inproceedings{3223,
author = {Jacob M. Howe and Andy King},
title = {Polyhedral {A}nalysis using {P}arametric {O}bjectives},
month = {September},
year = {2012},
pages = {41-57},
keywords = {abstract interpretation, linear constraints, projection},
note = {ARCoSS subline},
doi = {},
url = {http://www.cs.kent.ac.uk/pubs/2012/3223},
    publication_type = {inproceedings},
    submission_id = {18181_1339156536},
    booktitle = {Nineteenth Static Analysis Symposium},
    editor = {Antoine Min'e and David A. Schmidt},
    volume = {7460},
    series = {Lecture Notes in Computer Science},
    publisher = {Springer},
    refereed = {yes},
}

School of Computing, University of Kent, Canterbury, Kent, CT2 7NF

Enquiries: +44 (0)1227 824180 or contact us.

Last Updated: 21/03/2014