Skip to main content
Kent Academic Repository

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)

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: 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: 05 Nov 2024 10:00 UTC
Resource URI: https://kar.kent.ac.uk/id/eprint/21867 (The current URI for this page, for reference purposes)

University of Kent Author Information

  • Depositors only (login required):

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