کد مقاله | کد نشریه | سال انتشار | مقاله انگلیسی | نسخه تمام متن |
---|---|---|---|---|
420252 | 683913 | 2011 | 6 صفحه PDF | دانلود رایگان |

Possible characterizations of which positive boolean functions are weighted threshold were studied in the 60s and 70s. It is known that a boolean function is weighted threshold if and only if it is kk-asummable for every value of kk. Furthermore, for some particular subfamilies of functions (those with up to eight variables, and graph functions), it is known that a function is weighted threshold if and only if it is 2-asummable.In this work we prove that bipartite functions also satisfy this property: a bipartite function is weighted threshold if and only if it is 2-asummable. In a bipartite function the set of variables can be partitioned in two classes, such that all the variables in the same class play exactly the same role in the function.
Journal: Discrete Applied Mathematics - Volume 159, Issue 11, 6 July 2011, Pages 1079–1084