size-time complexity of boolean networks for prefix computations
The prefix problem consists of computing all the products x 0 x 1  x j ( j =0, , N - 1), given a sequence x = ( x 0 , x 1 , , 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 = &THgr;(( N/T ) log( N/T )), for non-cycle-free semigroups, and S = &THgr;( N/T ), for cycle-free semigroups. In both cases, T ? [&OHgr;(log N ), O ( N )].
size complexity network computation product sequence paper characterization synchronization interconnect storage device graph timing log optimality factor direct memorialized exception time complexity model of computation circuits