کد مقاله کد نشریه سال انتشار مقاله انگلیسی نسخه تمام متن
420252 683913 2011 6 صفحه PDF دانلود رایگان
عنوان انگلیسی مقاله ISI
Any 2-asummable bipartite function is weighted threshold
موضوعات مرتبط
مهندسی و علوم پایه مهندسی کامپیوتر نظریه محاسباتی و ریاضیات
پیش نمایش صفحه اول مقاله
Any 2-asummable bipartite function is weighted threshold
چکیده انگلیسی

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.

ناشر
Database: Elsevier - ScienceDirect (ساینس دایرکت)
Journal: Discrete Applied Mathematics - Volume 159, Issue 11, 6 July 2011, Pages 1079–1084
نویسندگان
,