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