The Two Variable Per Inequality Abstract Domain

Simon, Axel and King, Andy and Howe, Jacob M. (2010) The Two Variable Per Inequality Abstract Domain. Higher-Order and Symbolic Computation, 31 (1). pp. 182-196. (Full text available)

PDF
Download (1MB) Preview
[img]
Preview
Official URL
http://www.cs.kent.ac.uk/pubs/2010/3167

Abstract

This article presents the Two Variable Per Inequality abstract domain (TVPI domain for short). This so-called weakly-relational domain is able to express systems of linear inequalities where each inequality has at most two variables. The domain represents a sweet-point in the performance-cost tradeoff between the faster Octagon domain and the more expressive domain of general convex polyhedra. In particular, we detail techniques to closely approximate integral TVPI systems, thereby finessing the problem of excessively growing coefficients, yielding -- to our knowledge -- the only relational domain that combines linear relations with arbitrary coefficients and strongly polynomial performance.

Item Type: Article
Additional information: Note the Springer published the *wrong* version of this paper in HOSC and this on-line version of the paper should be taken as final.
Subjects: Q Science > QA Mathematics (inc Computing science) > QA 76 Software, computer programming,
Divisions: Faculties > Science Technology and Medical Studies > School of Computing > Programming Languages and Systems Group
Depositing User: Andy King
Date Deposited: 21 Sep 2012 09:49
Last Modified: 16 Dec 2013 12:47
Resource URI: http://kar.kent.ac.uk/id/eprint/30678 (The current URI for this page, for reference purposes)
  • Depositors only (login required):

Downloads

Downloads per month over past year