The Library
Monotone Boolean functions as combinatorially piecewise linear maps
Tools
Tools
Tools
Beynon, Meurig (1987) Monotone Boolean functions as combinatorially piecewise linear maps. University of Warwick. Department of Computer Science. (Department of Computer Science research report). (Unpublished)
|
PDF (Department of Computer Science Research Report)
WRAP_cs-rr-109.pdf - Other - Requires a PDF viewer. Download (2587Kb) | Preview |
Abstract
The class of combinatorially piecewise linear (cpl) maps was first introduced to solve a geometric problem concerning the representability of piecewise linear functions as pointwise maxima of minima of linear functions. Such maps correspond in a canonical fashion to monotone boolean functions. This paper describes how a monotone boolean function in n variables whose prime implicants and prime clauses are non-rivial defines a partition of the symmetric group on n symbols into a set of "singular cycles" representing relations between transpositions of adjacent symbols. Several possible approaches to the classification of such cycles are described, and some characteristic properties of singular cycles are identified. The potential computational significance of singular cycles is indicated with reference to new combinatorial models for monotone boolean formulae and circuits that arise directly form the
appropriate theory of computational equivalence and replaceability. The prospects for application to monotone boolean complexity are briefly examined. A catalogue of known relations is included as an Appendix.
| Item Type: | Report | ||||
|---|---|---|---|---|---|
| Subjects: | Q Science > QA Mathematics | ||||
| Divisions: | Faculty of Science, Engineering and Medicine > Science > Computer Science | ||||
| Library of Congress Subject Headings (LCSH): | Linear operators, Functions | ||||
| Series Name: | Department of Computer Science research report | ||||
| Publisher: | University of Warwick. Department of Computer Science | ||||
| Official Date: | November 1987 | ||||
| Dates: |
|
||||
| Number: | Number 109 | ||||
| DOI: | CS-RR-109 | ||||
| Institution: | University of Warwick | ||||
| Theses Department: | Department of Computer Science | ||||
| Status: | Not Peer Reviewed | ||||
| Publication Status: | Unpublished | ||||
| Related URLs: |
Request changes or add full text files to a record
Repository staff actions (login required)
 |
View Item |
Downloads
Downloads per month over past year
