Size-time complexity of Boolean networks for prefix computations

Publisher Website
Google Scholar
Abstract
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 two properties of the underlying semigroup, which we call cycle-freedom (no cycle of length greater than one in the Cayley graph of the semigroup), and memory-induciveness (arbitrarily long products of semigroup elements are true functions of all their factors). A nontrivial characterization is given of non-memory-inducive semigroups as those whose recurrent subsemigroup (formed by the elements with self-loops in the Cayley graph) is the direct product of a left-zero semigroup and a right-zero semigroup. Denoting by S and T size and computation time, respectively, we have S = Θ(( N / T )log( N / T )) for memory-inducive non-cycle-free semigroups, and S = Θ( N / T ) for all other semigroups. We have T ε [Ω(log N ), Ο( N )] for all semigroups, with the exception of those whose recurrent subsemigroup is a right-zero semigroup, for which T ε [Ω(1), Ο( N )]. The preceding results are also extended to the VLSI model of computation. Area-time optimal circuits are obtained for both boundary and nonboundary I/O protocols.

This publication has 9 references indexed in Scilit: