Benoy, Florence and King, Andy (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)
Download (472kB)
Preview


Abstract
Polyhedral cones can be represented by sets of linear inequalities that express intervariable relationships. These inequalities express intervariable relationships that are quantified by the ratios between the variable coefficients. However, linear inequalities over a nonnegative variable domain with only unit variable coefficients and no constants other than zero can represent relationships that can be valid in nonnumeric domains. For instance, if variables are either nonnegative or zero itself, that is, a strictly twopoint 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 intervariable 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 399 
Uncontrolled keywords:  Boolean functions, polyhedra, abstract interpretation 
Subjects:  Q Science > QA Mathematics (inc Computing science) > QA 76 Software, computer programming, 
Divisions:  Faculties > Sciences > School of Computing > Theoretical Computing Group 
Depositing User:  Andy King 
Date Deposited:  20 Oct 2009 17:24 UTC 
Last Modified:  28 May 2014 08:54 UTC 
Resource URI:  https://kar.kent.ac.uk/id/eprint/21867 (The current URI for this page, for reference purposes) 
 Export to:
 RefWorks
 EPrints3 XML
 BibTeX
 CSV
 Depositors only (login required):
Downloads
Downloads per month over past year