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)
PDF
Language: English |
|
Download this file (PDF/478kB) |
Preview |
Request a format suitable for use with assistive technology e.g. a screenreader |
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) |
- Link to SensusAccess
- Export to:
- RefWorks
- EPrints3 XML
- BibTeX
- CSV
- Depositors only (login required):