document: A linear time algorithm for recognizing regular Boolean functions A positive -LRB- or monotone -RRB- Boolean function is regular if its variables are naturally ordered , left to fight , by decreasing strength , so that shifting the nonzero component of any true vector to the left always yields another true vector . This paper considers the problem of recognizing whether a positive function f is regular , where f is given by min T -LRB- f -RRB- -LRB- the set of all minimal true vectors of f -RRB- . We propose a simple linear time -LRB- i.e. , O -LRB- n | min T -LRB- f -RRB- | -RRB- - time -RRB- algorithm for it . This improves upon the previous algorithm by J.S. Provan and M.O. Ball -LRB- 1988 -RRB- which requires O -LRB- n/sup 2 / | min T -LRB- f -RRB- | -RRB- time . As a corollary , we also present an O -LRB- n -LRB- n + | min T -LRB- f -RRB- | -RRB- -RRB- - time algorithm for the recognition problem of 2-monotonic functions
doc_bio_tags: O B I I O O B I I O O O O O O O O O O O O O O O O O O O O O O O O O O O O O B I O O B I O O O O O O B I O O O O O O O O O O B I O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O