Delay optimization of linear depth boolean circuits with prescribed input arrival times Export

@article{citeulike:938296, abstract = {We consider boolean circuits C over the basis [Omega]={[logical or],[logical and]} with inputs x1, x2,...,xn for which arrival times are given. For 1[less-than-or-equals, slant]i[less-than-or-equals, slant]n we define the delay of xi in C as the sum of ti and the number of gates on a longest directed path in C starting at xi. The delay of C is defined as the maximum delay of an input.Given a function of the formf(x1,x2,...,xn)=gn-1(gn-2(...g3(g2(g1(x1,x2),x3),x4)...,xn-1),xn) where gj[set membership, variant][Omega] for 1[less-than-or-equals, slant]j[less-than-or-equals, slant]n-1 and arrival times for x1,x2,...,xn, we describe a cubic-time algorithm that determines a circuit for f over [Omega] that is of linear size and whose delay is at most 1.44 times the optimum delay plus some small constant.}, author = {Rautenbach, Dieter and Szegedy, Christian and Werber, Jurgen}, citeulike-article-id = {938296}, citeulike-linkout-0 = {http://dx.doi.org/10.1016/j.jda.2005.06.006}, citeulike-linkout-1 = {http://www.sciencedirect.com/science/article/B758J-4GKW7B1-2/2/f0b61065c2fbc37897949a4ae8f0b551}, doi = {10.1016/j.jda.2005.06.006}, journal = {Journal of Discrete Algorithms}, keywords = {algorithm, boolean}, month = {December}, number = {4}, pages = {526--537}, posted-at = {2006-11-09 20:24:22}, priority = {3}, title = {Delay optimization of linear depth boolean circuits with prescribed input arrival times}, url = {http://dx.doi.org/10.1016/j.jda.2005.06.006}, volume = {4}, year = {2006} }

TY - JOUR ID - citeulike:938296 L3 - citeulike-article-id:938296 N2 - We consider boolean circuits C over the basis [Omega]={[logical or],[logical and]} with inputs x1, x2,...,xn for which arrival times are given. For 1[less-than-or-equals, slant]i[less-than-or-equals, slant]n we define the delay of xi in C as the sum of ti and the number of gates on a longest directed path in C starting at xi. The delay of C is defined as the maximum delay of an input.Given a function of the formf(x1,x2,...,xn)=gn-1(gn-2(...g3(g2(g1(x1,x2),x3),x4)...,xn-1),xn) where gj[set membership, variant][Omega] for 1[less-than-or-equals, slant]j[less-than-or-equals, slant]n-1 and arrival times for x1,x2,...,xn, we describe a cubic-time algorithm that determines a circuit for f over [Omega] that is of linear size and whose delay is at most 1.44 times the optimum delay plus some small constant. IS - 4 JF - Journal of Discrete Algorithms EP - 537 TI - Delay optimization of linear depth boolean circuits with prescribed input arrival times VL - 4 SP - 526 KW - algorithm KW - boolean AU - Rautenbach, Dieter AU - Szegedy, Christian AU - Werber, Jurgen PY - 2006/12// UR - http://dx.doi.org/10.1016/j.jda.2005.06.006 ER -