JUCS - Journal of Universal Computer Science 2(7): 533-548, doi: 10.3217/jucs-002-07-0533
Ceilings of Monotone Boolean Functions
expand article infoPaul E. Dunne‡
‡ University of Liverpool, United Kingdom

Corresponding author: Paul Dunne ( ped@csc.liv.ac.uk )

© Paul Dunne.
This article is freely available under the J.UCS Open Content License.
Citation: Dunne PE (1996) Ceilings of Monotone Boolean Functions. JUCS - Journal of Universal Computer Science 2(7): 533-548. https://doi.org/10.3217/jucs-002-07-0533
Open Access
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