Beynon, Meurig (1984) Monotone Boolean functions computable by planar circuits. Coventry, UK: University of Warwick. Department of Computer Science. (Department of Computer Science Research Report). (Unpublished)

Preview

PDF WRAP_067.pdf - Other - Requires a PDF viewer. Download (5Mb) | Preview

Request Changes to record.

Abstract

A criterion for testing whether a given monotone boolean function f is planar monotone computable from the sequence of inputs xi,x2, . . . , xn, is developed in conjunction with an algorithm which (in principle) can construct a planar monotone circuit for f whenever one exists. Both the algorithm and the criterion require precomputation of the prime implicants and clauses of f.

As an application of the theory, it is shown that monotone boolean functions whose prime implicants and clauses contain configurations of a particular type cannot be computed by planar monotone circuits. All monotone boolean functions on 4 (or fewer) inputs are shown to be planar monotone computable.

Item Type:	Report
Subjects:	Q Science > QA Mathematics > QA76 Electronic computers. Computer science. Computer software
Divisions:	Faculty of Science, Engineering and Medicine > Science > Computer Science
Library of Congress Subject Headings (LCSH):	Algebra, Boolean, Computers -- Circuits
Series Name:	Department of Computer Science Research Report
Publisher:	University of Warwick. Department of Computer Science
Place of Publication:	Coventry, UK
Official Date:	September 1984
Dates:	Date Event September 1984 Collection
Number:	Number 67
Number of Pages:	10
DOI:	CS-RR-067
Institution:	University of Warwick
Theses Department:	Department of Computer Science
Status:	Not Peer Reviewed
Publication Status:	Unpublished
Related URLs:	Organisation

Request changes or add full text files to a record

Repository staff actions (login required)

View Item

Downloads