BIB-VERSION:: CS-TR-v2.0
          ID:: STAN//CS-TR-76-553
       ENTRY:: July 04, 1995
ORGANIZATION:: Stanford University, Department of Computer Science
       TITLE:: Complexity of monotone networks for computing conjunctions
        TYPE:: Technical Report
      AUTHOR:: Tarjan, Robert Endre
        DATE:: June 1976
       PAGES:: 25
    ABSTRACT:: Let $F_1$, $F_2$,..., $F_m$ be a set of Boolean functions of
               the form $F_i$ = $\wedge$ {x$\in X_i$}, where $\wedge$
               denotes conjunction and each $X_i$ is a subset of a set X of
               n Boolean variables. We study the size of monotone Boolean
               networks for computing such sets of functions. We exhibit
               anomalous sets of conujunctions whose smallest monotone
               networks contain disjunctions. We show that if |$F_i$| is
               sufficiently small for all i, such anomalies cannot happen.
               We exhibit sets of m conjunctions in n unknowns which require
               $c_2$m$\alpha$(m,n) binary conjunctions, where $\alpha$(m,n)
               is a very slowly growing function related to a functional
               inverse of Ackermann's function. This class of examples shows
               that an algorithm given in [STAN-CS-75-512] for computing
               functions defined on paths in trees is optimum to within a
               constant factor.
       NOTES:: [Adminitrivia V1/Prg/19950704]
         END:: STAN//CS-TR-76-553