An Isomorphism between Abstract Polyhedral Cones and Definite Boolean Functions

Benoy, F. and King, A. (1999) An Isomorphism between Abstract Polyhedral Cones and Definite Boolean Functions. University of Kent, School of Computing, University of Kent, 21 pp. (Full text available)

PDF
Download (453kB)
[img]
Preview

Abstract

Polyhedral cones can be represented by sets of linear inequalities that express inter-variable relationships. These inequalities express inter-variable relationships that are quantified by the ratios between the variable coefficients. However, linear inequalities over a non-negative variable domain with only unit variable coefficients and no constants other than zero can represent relationships that can be valid in non-numeric domains. For instance, if variables are either non-negative or zero itself, that is, a strictly two-point domain, then 0 <= x, 0 <= y, x <= y, expresses a dependency between x and y, since if y is known to be zero, then so is x. By defining an abstraction operator that effectively puts aside the scaling coefficients whilst retaining the inter-variable aspect of these relationships polyhedral cones can express the same dependency information as Def, a class of Boolean function. Boolean functions are considered over a fixed finite set of variables and Def is a subset of the positive Boolean functions, which return the value true when every variable returns true. Def is a complete lattice ordered by logical consequence and it will be shown that the abstract cones also form a complete lattice, ordered by set inclusion, that is isomorphic to Def.

Item Type: Research report (external)
Additional information: Technical Report 3-99
Uncontrolled keywords: Boolean functions, polyhedra, abstract interpretation
Subjects: Q Science > QA Mathematics (inc Computing science) > QA 76 Software, computer programming,
Divisions: Faculties > Science Technology and Medical Studies > School of Computing > Theoretical Computing Group
Depositing User: Andy King
Date Deposited: 20 Oct 2009 17:24
Last Modified: 13 Dec 2013 12:08
Resource URI: http://kar.kent.ac.uk/id/eprint/21867 (The current URI for this page, for reference purposes)
  • Depositors only (login required):

Downloads

Downloads per month over past year