Ceilings of Monotone Boolean Functions
Дата
Авторы
Dunne,Paul
Journal Title
Journal ISSN
Volume Title
Издатель
Journal of Universal Computer Science
Аннотация
Описание
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.
Ключевые слова
Complexity measures , combinational networks , monotone Boolean functions