title: A linear time algorithm for recognizing regular Boolean functions
abstract: A positive (or monotone) 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(f) (the set of all minimal true vectors of f). We propose a simple linear time (i.e., O(n|min T(f)|)-time) algorithm for it. This improves upon the previous algorithm by J.S. Provan and M.O. Ball (1988) which requires O(n/sup 2/|min T(f)|) time. As a corollary, we also present an O(n(n+|min T(f)|))-time algorithm for the recognition problem of 2-monotonic functions
keyphrases: linear time algorithm regular Boolean functions nonzero component true vector positive function 2-monotonic functions monotone Boolean function