Access Restriction

Author Bilardi, G. ♦ Preparata, F. P.
Source ACM Digital Library
Content type Text
Publisher Association for Computing Machinery (ACM)
File Format PDF
Copyright Year ©1989
Language English
Subject Domain (in DDC) Computer science, information & general works ♦ Data processing & computer science
Abstract The prefix problem consists of computing all the products $\textit{x}0\textit{x}1$ … $\textit{xj}$ $(\textit{j}$ = 0, … , $\textit{N}$ - 1), given a sequence x = $(\textit{x}0,$ $\textit{x}1,$ … , $\textit{x}\textit{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 $\textit{S}$ and $\textit{T}$ size and computation time, respectively, we have S = $&THgr;((\textit{N}/\textit{T})log(\textit{N}/\textit{T}))$ for memory-inducive non-cycle-free semigroups, and S = $&THgr;(\textit{N}/\textit{T})$ for all other semigroups. We have $\textit{T}$ ε [&OHgr;(log $\textit{N}),$ $&Ogr;(\textit{N})]$ for all semigroups, with the exception of those whose recurrent subsemigroup is a right-zero semigroup, for which $\textit{T}$ ε [&OHgr;(1), $&Ogr;(\textit{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.
ISSN 00045411
Age Range 18 to 22 years ♦ above 22 year
Educational Use Research
Education Level UG and PG
Learning Resource Type Article
Publisher Date 1989-04-01
Publisher Place New York
e-ISSN 1557735X
Journal Journal of the ACM (JACM)
Volume Number 36
Issue Number 2
Page Count 21
Starting Page 362
Ending Page 382

Open content in new tab

   Open content in new tab
Source: ACM Digital Library