Ceilings of Monotone Boolean Functions
Paul E. Dunne (University of Liverpool, UK)
Abstract: This paper considers a particular relationship defined overpairs of n-argument monotone Boolean functions. The relationship is of interest since we can show that if ( g, h ) satisfy it then for any n-argument monotone Boolean function f there is a close relationship between the combinational and monotone network complexities of the function (f/\g) \/ h. We characterise the class of pairs of functions satisfying the relationship and show that it extends and encapsulates previous results concerning translations from combinational to monotone networks.
Keywords: Complexity measures, combinational networks, monotone Boolean functions
Categories: F.1.1, F.1.3