McColl, William Finlay and Paterson, Michael S. (1988) Planar acyclic computation. University of Warwick. Department of Computer Science. (Department of Computer Science research report). (Unpublished)

Preview

PDF (Department of Computer Science Research Report) WRAP_cs-rr-122.pdf - Other - Requires a PDF viewer. Download (5Mb) | Preview

Request Changes to record.

Abstract

This paper considers the following problem: given a specification consisting of a set of variables X, a multiset of functions F on those variables, and a cyclic ordering on X U F, determine whether or not there exists a planar acyclic circuit which realises the specification. An algorithm is given which produces such a circuit whenever one exists. In proving that our algorithm meets this requirement we provide a simple mathematical characterisation of those specifications which are realisable.

Item Type:	Report
Subjects:	Q Science > QA Mathematics > QA76 Electronic computers. Computer science. Computer software
Divisions:	Faculty of Science > Computer Science
Library of Congress Subject Headings (LCSH):	Electronic digital computers -- Circuits
Series Name:	Department of Computer Science research report
Publisher:	University of Warwick. Department of Computer Science
Official Date:	May 1988
Dates:	Date Event May 1988 Completion
Number:	Number 122
Number of Pages:	11
DOI:	CS-RR-122
Institution:	University of Warwick
Theses Department:	Department of Computer Science
Status:	Not Peer Reviewed
Publication Status:	Unpublished
Publisher Statement:	W.F.&nbsp;McColl, M.S.&nbsp;Paterson and B.H.&nbsp;Bowditch, &ldquo;Planar Acyclic Computation&rdquo;, <i>Information and Computation</i> <b>90</b>, pp.&nbsp;178-193 (1991)
Funder:	Science and Engineering Research Council (Great Britain) (SERC)
Related URLs:	Organisation

Request changes or add full text files to a record

Repository staff actions (login required)

View Item

Downloads