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, GianfrancoPreparata, Franco P. Keywords: computer sciencetechnical 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