Publication at Faculty of Mathematics and Physics |
2006
Abstract
Threshold, 2-monotonic and interval Boolean functions constitute special classes of Boolean functions for which it is easy to decide many problems which are intractable for general Boolean functions. In our article we show that positive interval functions are a proper subset of positive threshold functions.
Then we prove one property of 2-monotonic functions which is related to testing whether a 2-monotonic function is an interval function. Based on this we construct an algorithm which recognizes in linear time whether given positive threshold function is a positive interval function.