Skip to main content


eCommons@Cornell

eCommons@Cornell >
College of Engineering >
Computer Science >
Computer Science Technical Reports >

Please use this identifier to cite or link to this item: http://hdl.handle.net/1813/6645
Title: Size-Time Complexity of Boolean Networks for Prefix Computations
Authors: Bilardi, Gianfranco
Preparata, Franco P.
Keywords: computer science
technical report
Issue Date: Jan-1987
Publisher: Cornell University
Citation: http://techreports.library.cornell.edu:8081/Dienst/UI/1.0/Display/cul.cs/TR87-805
Abstract: The prefix problem consists of computing all the products $x_{0}x_{1}\ldots x_{j} (j=0,\ldots,N-1)$, given a sequence $X = (x_{0},x_{1},\ldots,x_{N-1})$ of elements in a semigroup. In this paper we completely characterize the size-time complexity of computing prefixes with boolean networks, which are synchronized interconnections of boolean gates and one-bit storage devices. This complexity crucially depends upon a property of the underlying semigroup, which we call cycle-freedom (no cycle of length greater than one in the Cayley graph of the semigroup). Denoting by $S$ and $T$ size and computation time, respectively, we have $S = \Theta((N/T) \log(N/T))$, for non-cycle-free semigroups, and $S = \Theta((N/T)$, for cycle-free semigroups. In both cases, $T \in [\Omega(\logN),O(N)]$.
URI: http://hdl.handle.net/1813/6645
Appears in Collections:Computer Science Technical Reports

Files in This Item:

File Description SizeFormat
87-805.pdf1.17 MBAdobe PDFView/Open
87-805.ps302.91 kBPostscriptView/Open

Refworks Export

Items in eCommons are protected by copyright, with all rights reserved, unless otherwise indicated.

 

© 2014 Cornell University Library Contact Us