کد مقاله کد نشریه سال انتشار مقاله انگلیسی نسخه تمام متن
437929 690209 2015 32 صفحه PDF دانلود رایگان
عنوان انگلیسی مقاله ISI
Associative and commutative tree representations for Boolean functions
ترجمه فارسی عنوان
تظاهرات درختی متحرک و تعاملی برای توابع بولین
کلمات کلیدی
توابع بولین، توزیع احتمال، فرمول بولی تصادفی درختان تصادفی، نسبت آستیگماتیسم، ترکیبیات تحلیلی
موضوعات مرتبط
مهندسی و علوم پایه مهندسی کامپیوتر نظریه محاسباتی و ریاضیات
چکیده انگلیسی

Since the 1990s, the probability distribution on Boolean functions, induced by some random formulas built upon the connectives And and Or, has been intensively studied. These formulas rely on plane binary trees. We extend all the results, in particular the relation between the probability and the complexity of a function, to more general formula structures: non-binary or non-plane trees. These formulas satisfy the natural properties of associativity and commutativity.

ناشر
Database: Elsevier - ScienceDirect (ساینس دایرکت)
Journal: Theoretical Computer Science - Volume 570, 9 March 2015, Pages 70–101
نویسندگان
, , , ,