Go home now Header Background Image
Submission Procedure
share: |
Follow us
Volume 2 / Issue 7

available in:   PDF (75 kB) PS (49 kB)
Similar Docs BibTeX   Write a comment
Links into Future
DOI:   10.3217/jucs-002-07-0533


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