Skip to main content

An Isomorphism between Abstract Polyhedral Cones and Definite Boolean Functions

Benoy, Florence, King, Andy (1999) An Isomorphism between Abstract Polyhedral Cones and Definite Boolean Functions. University of Kent, School of Computing, University of Kent, 21 pp. (KAR id:21867)

Language: English
Click to download this file (478kB) Preview
[thumbnail of an_isomorphism_between_abstract_benoy.pdf]
This file may not be suitable for users of assistive technology.
Request an accessible format


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: Divisions > Division of Computing, Engineering and Mathematical Sciences > School of Computing
Depositing User: Andy King
Date Deposited: 20 Oct 2009 17:24 UTC
Last Modified: 16 Nov 2021 10:00 UTC
Resource URI: (The current URI for this page, for reference purposes)
King, Andy:
  • Depositors only (login required):

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