1980/10/01 by Richard E. Ladner, Michael J. Fischer · 7 citations
Computer Science · Biochemistry, Genetics and Molecular Biology · #Algorithms and Data Compression #Network Packet Processing and Optimization #DNA and Biological Computing
paper · pdf · doi:10.1145/322217.322232
openalex publication_date 1980/10/01 · openalex created_date 2025/10/10 · openalex updated_date 2026/08/01
The prefix problem is to compute all the products x t o x2 .... o xk for i ~ k .~ n, where o is an associative operation A recurstve construction IS used to obtain a product circuit for solving the prefix problem which has depth exactly [log:n] and size bounded by 4n An application yields fast, small Boolean ctrcmts to simulate fimte-state transducers. By simulating a sequentml adder, a Boolean clrcmt which has depth 2[Iog2n] + 2 and size bounded by 14n Is obtained for n-bit binary addmon The size can be decreased significantly by permitting the depth to increase by an addmve constant