Size-Time Complexity of Boolean Networks for Prefix Computations
| dc.contributor.author | Bilardi, Gianfranco | en_US |
| dc.contributor.author | Preparata, Franco P. | en_US |
| dc.date.accessioned | 2007-04-23T17:17:47Z | |
| dc.date.available | 2007-04-23T17:17:47Z | |
| dc.date.issued | 1987-01 | en_US |
| dc.description.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)]$. | en_US |
| dc.format.extent | 1195249 bytes | |
| dc.format.extent | 310178 bytes | |
| dc.format.mimetype | application/pdf | |
| dc.format.mimetype | application/postscript | |
| dc.identifier.citation | http://techreports.library.cornell.edu:8081/Dienst/UI/1.0/Display/cul.cs/TR87-805 | en_US |
| dc.identifier.uri | https://hdl.handle.net/1813/6645 | |
| dc.language.iso | en_US | en_US |
| dc.publisher | Cornell University | en_US |
| dc.subject | computer science | en_US |
| dc.subject | technical report | en_US |
| dc.title | Size-Time Complexity of Boolean Networks for Prefix Computations | en_US |
| dc.type | technical report | en_US |